РАЗДЕЛ 2
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МЕТОДА МОДЕЛИРОВАНИЯ ЗНАКОВ
В ДИСКРЕТНЫХ ПРЕДСТАВЛЕНИЯХ
Автоматическое моделирование изображений предполагает разработку методов, которые реализуются в соответствующем блоке системы обработки изображений. Как следует из разд. 1, при моделировании знаков с применением аналитических аналогов разработчики систем распознавания изображений столкнулись с рядом проблем. С целью их устранения в данной работе для моделирования знаков предложено использовать дискретные аналоги аналитически заданных объектов. В настоящем разделе вводится множество атомарных элементов, на котором в дальнейшем будут определены модели опознаваемых знаков (разд. 3), рассматриваются основные свойства и подмножества данного множества. Для последующего определения знаков объектов опознавания предложены определения связных атомарных элементов и пути как связного множества атомарных элементов. Введена метрика на множестве атомарных элементов и определены две меры путей, позволяющие их сравнивать по количеству связок и "весу". С целью определения дискретного отрезка рассмотрены множества путей, обладающих метрическими свойствами отрезков прямых. Доказаны необходимые и достаточные условия принадлежности путей этим множествам, исследованы их свойства.
2.1. Дискретное множество атомарных элементов и его метрические свойства
В соответствии с постановкой задачи настоящего исследования (п. 1.5), с целью определения знаков планиметрических фигур в дискретных представлениях и, в частности, отрезка прямой, зададим множество атомарных элементов [68, 69, 120]. Будем полагать, что каждый из них, согласно п. 1.4, представляет собой квадрат со стороной а?R, а>0, и центры "соседних" АЭ удалены друг от друга по вертикали и горизонтали на некоторое расстояние, равное а+?, ?<<а, ??R, ?>0 (структура множества АЭ и его топологические свойства описаны в п. 1.4).
Предположим, что количество АЭ определяется установленной разрешающей способностью некоторого монитора, используемого для отображения прообраза концепта, хранящегося в видеопамяти системы (см. п. 1.4). Пусть разрешающая способность монитора и размеры матрицы видеопамяти одинаковы и равны (I?J), где I,J?? - количества элементов в столбцах и строках соответственно. Для определения АЭ построим два семейства прямых:
xu= yv= ?u?[1,2J], v?[1,2I],
которые будут ограничивать АЭ.
Определение 2.1. Атомарным элементом (АЭ) будем называть множество ?(i,j)?Е2, ?(i,j)={(x,y)?Е2| x2j-1?x?x2j, y2i-1?y?y2i}, ?i?[1,I], j?[1,J].
Как следует из определения, каждый АЭ однозначно определяется парой индексов, указывающих порядковые номера строки и столбца, в которых он находится, что подтверждает корректность его выбора в качестве модели минимальной составляющей поверхности знаков, отображаемых устройством вывода системы - монитором. АЭ является также элементом модели прообраза концепта, содержащегося в видеопамяти, и его определение не противоречит формам представления данных в ЦЭВМ (п. 1.4).
В соответствии с определением 2.1 введем в рассмотрение конечное множество А атомарных элементов ?h: А={?h}, где ?h=?(ih,jh), ih?[1,I], jh?[1,J], h?[1,H], H?N [79-81, 126-128]. В рамках дифференциации атомарных элементов, установленной в разд. 1, будем полагать, что ?h?А, является активным, если ?(ih,jh)=1, и пассивным, если ?(ih,jh)=0, где ?(ih,jh) - соответствующий ему элемент матрицы видеопамяти, содержащей концепт знака.
На множестве А зададим функцию ?:(?a,?b)?N?{0}, которая каждой паре АЭ из А ставит в соответствие единственное целое неотрицательное число ?(?a,?b) по правилу:
?(?a,?b)=|ia-ib|+|ja-jb|. (2.1)
Число ?(?a,?b) будем трактовать как расстояние между АЭ ?a,?b.
Покажем, что ? удовлетворяет всем свойствам метрики.
Действительно, для любых двух АЭ ?a,?b?А верно ?(?a,?b)?0, причём ?(?a,?b)=0 тогда и только тогда, когда ?a=?b. Второе свойство метрики также выполнено: ?(?a,?b)=?(?b,?a).
Для любой тройки АЭ ?a,?b,?c?А верно ?(?a,?b)=|ia-ib|+|ja-jb|=|ia-ib+ic-ic|+ +|ja-jb+jc-jc|?|ia-ic|+|ib-ic|+|ja-jc|+|jb-jc|=?(?a,?c)+?(?b,?c), откуда следует, что ?(?a,?b)? ??(?a,?c)+?(?b,?c), то есть для функции ? выполняется третье свойство метрики.
Одной из задач настоящего исследования является определение отрезка прямой на множестве АЭ, который будем трактовать как "переход" из некоторого начального АЭ в конечный, осуществленный по "кратчайшему пути". С этой целью выделим подмножества АЭ, на которых можно указать некий аналог "движения" как совокупности "переходов" между АЭ. Для этого определим минимальный элемент движения как пару связных АЭ.
Определение 2.2. АЭ ?a,?b?A будем называть связными, если
max{|ia-ib|,|ja-jb|}?1. (2.2)
Заметим, что если АЭ ?a и ?b связны, то |ia-ib|?|ja-jb|?1, обратное не всегда верно. Примеры связных АЭ приведены на рис. 2.1.
Рис. 2.1. Пары связных АЭ: s1 - горизонтальная связка; s2 - вертикальная связка; s3, s4 - диагональные связки
На множестве пар связных АЭ определим функцию ? следующим образом:
?(?a,?b)= (2.3)
Если ?(?a,?b)=sm, то при m=1 будем говорить, что пара (?a,?b) является горизонтальной связкой, при m=2 - вертикальной, при m=3 - диагональной связкой первого типа, при m=4 - диагональной связкой второго типа (см. рис. 2.1).
Условимся о следующем: если ?(?a,?b)=sm, m?M={1,2,3,4}, то записи sm и (?a,?b)m, m?M, будем отождествлять.
Каждую связку sm будем трактовать как "переход" из АЭ в связный с ним. На множестве связок пустым множеством (?) будем считать один АЭ, поскольку в этом случае "переход" не имеет места. При этом для того, чтобы говорить о последовательности "переходов", необходимо определить, какие связки считать связными.
Определение 2.3. (?а,?b)m и (?а,?b)m, m1, m2?M, будем называть связными, если или ?b=?а, ?b??а, или ?b=?а, ?b??а.
Используя введенные определения, зададим подмножества АЭ, на которых можно говорить о "движении" как совокупности "переходо