Книги по разным темам Pages:     | 1 |   ...   | 8 | 9 | 10 | 11 | 12 |   ...   | 82 |

В большинстве случаев изображение можно рассматривать как часть плоскости, разделенную на области с постоянными или меняющимися по некоторому закону параметрами, например, оптической плотностью, цветом, текстурой. Граница, то есть контур, является неотъемлемым свойством каждой из этих областей и представляет собой односвязную последовательность, состоящую из отрезков прямых и дуг кривых.

Изображение, как правило, рассматривается в дискретном виде. Соответственно, отрезки прямых и дуги кривых, образующие контуры изображений, являются отрезками цифровых прямых и дугами цифровых кривых.

Сегментация произвольного контура на отрезки цифровых прямых и/или дуги цифровых кривых является целью настоящей работы.

В работах [1,2] приведены алгоритмы, позволяющие выделить отрезок цифровой прямой в контуре.

Криволинейные элементы изображений, представленные в виде сплайнов, кривых Безье и т.п., используются в большом количестве приложений.

Однако дуги произвольных кривых, как элементы описания контуров не часто Рис.1 Выделение дуг эллипсов в трех одинаковых, повернутых друг используются при относительно друга объектах средствами Corel Draw распознавании контуров изображений в основном по причине отсутствия общего определения дуги произвольной цифровой кривой. Использование дуг кривых как структурных элементов описания контуров изображений приблизило бы его описание к интуитивному, естественному представлению изображений человеком, существенно сократило бы затраты памяти для хранения изображения и времени его обработки. В качестве примера приведем описание контуров, полученных для бинарных изображений в распространенном графическом редакторе Corel Draw. На рис.представлены контуры трех одинаковых объектов без помех, содержащих дугу эллипса, отличающихся положением в пространстве и углом поворота относительно центра каждого из объектов. Граничные точки, которые разделяют контуры на дуги кривых и отрезки прямых, обозначены квадратиками.

Одинаковые дуги представлены последовательностями, содержащими неодинаковое количество различных дуг кривых, то есть каждый из одинаковых объектов представлен различными элементами.

Такое описание объектов не может быть непосредственно использовано в системах искусственного интеллекта для интерпретации изображений, поскольку предполагает еще достаточно сложную обработку. Приведенный пример показывает существование проблемы даже при обработке изображений, не искаженных помехами и актуальность ее решения.

Контур как последовательность L-элементов Дуги цифровых кривых, как и отрезки цифровых прямых образуются при дискретизации изображений, содержащих контуры, состоящие из отрезков прямых и дуг кривых. Пикселы изображения имеют форму квадрата, образованного соседними парами вертикальных и горизонтальных линий решетки, использованной при дискретизации изображений. Будем рассматривать дискретное изображение, как двумерный клеточный комплекс [1]. В данном случае двумерные элементы - это пикселы. Помимо пикселов имеются креки (crac) и точки. Креки - это стороны пикселов, являющиеся одномерными элементами. Точки являются конечными точками креков и угловыми точками пикселов. Контур объекта в XII-th International Conference "Knowledge - Dialogue - Solution" таком случае - это связная замкнутая последовательность контурных креков, граничных между пикселами объекта и фоном. Характерные признаки отрезков прямых и дуг кривых в результате дискретизации утрачиваются.

На рис. 2 приведен пример исходного контура объекта, образованного дугой кривой и отрезком прямой, а также его цифровой эквивалент как последовательность креков. Связные части 12 последовательности креков можно объединить в 7 8 L-элементы.

Под L-элементом будем понимать связную 3 последовательность креков вертикальной (горизонтальной) ориентации, которая содержит не более одного крека горизонтальной (вертикальной) ориентации.

Как и работе [2], будем использовать такие Lэлементы, в которых отличный по ориентации 0 крек (если он имеется) содержится в конце последовательности. Каждый L-элемент характеризуется такими параметрами:

направлением относительно начальной его точки g (принято g= 0 - для направления вверх, 1 - Рис.2 Пример дискретизации контура объекта вправо, 2 - вниз, 3 - влево); l - количеством креков направления g (l = 1,2,Е); направлением последнего крека q относительно направления g предыдущих креков (q = Ц1 - последний крек направлен влево относительно направления g, +1 - вправо, 0 - совпадает с направлением g). Для L-элемента (0-2) g=0, l=3, q=+1. Для L-элемента (27-0) g=3, l=1, q=0.

Смысл использования L-элементов при обработке визуальной информации, в частности, в процессе структурного анализа контуров заключается в том, что L-элементы являются минимально возможными структурными объектами, еще сохраняющими после дискретизации пространственную ориентацию исходного объекта - отрезка прямой или сегмента дуги кривой. Анализ пространственных свойств Lэлементов (направлений, длин) в последовательности позволяет судить об их принадлежности к одному и тому же отрезку прямой.

Очевидно, что последовательность L-элементов, соответствующая отрезку прямой состоит из Lэлементов с одинаковыми значениями g, q, которые определяют направление отрезка цифровой прямой в пределах их значений.

Определение отрезков цифровых прямых в последовательности L-элементов контура Определить отрезок цифровой прямой в последовательности L-элементов контура - значит указать координаты его начальной и конечной точек. Пусть (х,у ), (х,у ) - целочисленные координаты начальной 1 1 2 и конечной точек отрезка прямой. Угол наклона отрезка определяется отношением разностей его координат n= x=|х1-х2| и m=y=|у1-у2|, которое в общем случае не является целым числом. Положим для определенности, что n > m. Очевидно, что отображение отрезка прямой произвольного угла наклона посредством L-элементов, имеющих целочисленные значения длины l, осуществляется путем чередования L-элементов, длины которых отличаются на 1, например, равны соответственно l,l+1, n причем l / l+1. Порядок их чередования определяет структуру отрезка цифровой прямой и m определяется значениями членов цепной дроби [l; k1, k2,Е, kt] или n r 1 1 1 1 1 1 r r 1 (1) = l + = l + =... = l + =... = l +, + + + m m r + + +... + k k k r k k k k 1 1 2 1 1 2 3 t получаемой при делении целых чисел n и m. Для определенности и без нарушения общности будем полагать, что r

Neural and Growing Networks k подряд идущих L-элементов длины l и один L-элемент длины l+1, если он имеется в последовательности, образуют K 1-элемент, состоящий из k L-элементов, иначе говоря, K 1 1элемент УдлиныФ k. Аналогично, k подряд идущих К 1 2 1-элементов длины k и один К 1 1-элемент длины k +1, если он имеется в последовательности, образуют К 1 2-элемент длины k и так далее до исчерпания членов цепной дроби. Числитель r определяет количество L-элементов длины l+1 в данном отрезке цифровой прямой, а также и количество K 1-элементов, каждый из которых содержит k или k +1 L1 элементов, один из которых имеет длину l+1. В свою очередь числитель r1 определяет количество K 2элементов длины k +1 в данном отрезке цифровой прямой, а также и количество К 1 1-элементов, каждый из которых содержит k или k +1 L-элементов, один из которых имеет длину l+1, а остальные - длину l.

1 Вообще числитель rt-1 определяет количество K t-1-элементов длины k +1 в данном отрезке цифровой t-прямой, а также и количество К t-элементов, каждый из которых содержит k или k +1 K t-1 t-1 t-1-элементов, один из которых имеет длину k +1, а остальные - длину k.

t-1 t-К t-элемент, содержащий в своем составе среди K t-1-элементов длины k (L-элементов длины l) t-один K t-1-элемент длины k +1(один L-элемент длины l+1), называется завершенным.

t-Под отрезком цифровой прямой с координатами начальной и конечной точек (х,у ), (х,у ) будем 1 1 2 понимать последовательность L-элементов, имеющих одинаковые направления g,q, n целочисленные длины которых равны соответственно l, l+1, а l / l+1, где n = |х | и m 1-х m = |у |, причем порядок чередования L-элементов разных длин определяется цепной дробью 1-у n /.

m 4 уровень 3 уровень 1 2 3 4 5 2 уровень 1 уровень 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Вершины L-элементы К 1К 2-элементы К 3-элементы Р Е - Е П Т О Р Ы (С И Г Н А Л Ы К Р Е К О В ) Рис.3 Формирование образа отрезка цифровой прямой в терминах растущей пирамидальной сети Алгоритм выделения отрезков прямых в последовательности был сформулирован Т.М.Власовой при участии автора [3]. Процесс формирования образа отрезка цифровой прямой упомянутым алгоритмом можно представить в терминах растущих пирамидальных сетей [5] (рис.3) с учетом работ З.Л.Рабиновича [4]. Рассматривается частный случай растущей пирамидальной сети, при котором пирамиды вершин не имеют пересечений. В качестве рецепторов используются сигналы креков, которые формируют XII-th International Conference "Knowledge - Dialogue - Solution" L-элементы. Множество вершин сети связаны концепторами и обратными связями. Концепторы представлены восходящими прямыми стрелками и линиями без стрелок. Обратные связи представлены нисходящими стрелками. Рассматривается последовательная процедура процесса формирования образа - слева направо. Алгоритм формирования образа произвольного отрезка прямой заключается в следующем.

Начальные условия. Счетчик L-элементов s =1; общее количество L-элементов в последовательности N;

счетчики вершин t уровня s = 1, s = 1,Е, s = 1; t = 1; рабочая константа p = 0.

1 2 t 1. Определяются параметры L-элемента с номером s и передаются концептором в вершину номер s.

0 Выбор следующего L-элемента s := s +1; Переход к операции 2. Если s >N, запоминание значения s и 0 0 0 установка s в исходное состояние p = s ; s =1; Переход к операции 3.

1 1 2. Посредством дуги обратной связи параметры L-элементов из вершины номер s сравнивают с параметрами следующего по порядку L-элемента номер s. При положительном результате сравнения (рассматриваемые L-элементы образуют K 1-элемент) Переход к операции 1. Иначе Конец построения K 1элемента. Если построенный K 1-элемент является завершенным, то выбор новой вершины первого уровня s := s +1; Переход к операции 1. Иначе конец отрезка цифровой прямой, установка счетчиков 1 вершин в исходное состояние, запоминание координат концов отрезка; Переход к операции 1.

3. Передача параметров K t-элемента из вершины t-го уровня номер s в вершину t+1-го уровня номер s t t+посредством концептора, переход к новой вершине t-го уровня s := s +1; Переход к операции 4. Если s > p, t t t запоминание значения s и установка s в исходное состояние p = s ; s =1; выбор следующего уровня t:=t+1.

t t t t Если количество вершин следующего уровня s >1, то Переход к операции 3, иначе Конец работы t алгоритма.

4. Посредством дуги обратной связи параметры K -элементов из вершины номер s сравнивают с t t+параметрами K -элемента из вершины номер s. При положительном результате сравнения t t (рассматриваемые K t-элементы образуют K t+1-элемент) Переход к операции 3. Иначе конец построения K t+1-элемента. Если построенный K t+1-элемент является завершенным, то переход к новой вершине t-го уровня s := s +1; Переход к операции 3. Иначе конец отрезка цифровой прямой, установка счетчиков t+1 t+вершин в исходное состояние, запоминание координат концов отрезка; Переход к операции 3.

Определение дуги цифровой кривой В данном разделе будет сформулировано такое определение дуги цифровой кривой, которое T n+позволяет установить или отвергнуть факт: часть последовательности отрезков цифровых прямых T s-контура образована в результате дискретизации дуги h n некоторой произвольной кривой. Будем исходит из T n того, что дуги кривых, используемых в графических изображениях, отображают сегменты непрерывных функций с непрерывными производными. Под B непрерывными кривыми линиями [6], заданными уравнениями x = (t), y = (t), будем понимать кривые Жордана без кратных точек или простые дуги, то есть такие, что для любых двух разных значений t' и t' соответствующие им точки на плоскости M' [(t'), (t')] Рис.4 Дуга кривой с вписанной и M [(t), (t)] - разные. Пусть x = (t), y = (t), где ломаной линией (t), (t) - непрерывные функции параметра t, A определенные на отрезке [a, b].

При возрастании t от a к b точка с координатами х, y описывает дугу АВ (рис.4). Рассмотрим разбиение отрезка [a, b] точками деления a = t < t < Е < t < t = b, (2) 0 1 s-1 s и пусть этим точкам деления соотвествуют точки кривой А, T1, Е, T, В. Соединив последовательно s-отрезками прямых точку А с точкой T, точку T с точкой T, Е, точку T, с точкой B, построим ломанную 1 1 2 s-Neural and Growing Networks линию, и назовем ее ломаной, вписанной в дугу АВ. Фигуру, ограниченную отрезком ломаной линии T,T n n+и соответствующим звеном дуги Tn,Tn будем называть сегментом дуги T,T, а максимальную длину +1 n n+линии между отрезком T,T и T,T, перпендикулярной к отрезку T,T n n+1 n n+1 n n+1 - высотой сегмента дуги h.

n Пусть,Tn+1 (3) ( ) T = max l n n=0,1,...,s-Если будет стремиться к нулю при соответствующем увеличении s, то к нулю будет стремиться длина любого из звеньев вписанной ломаной, также как и высота каждого сегмента дуги, благодаря непрерывност функций (t), (t).

При отображении дуги и вписанной ломаной линии в дискретном пространстве дискретности d, отрезки вписанной ломаной будут отображаться отрезками цифровых прямых. Поскольку в дискретном пространстве значения координат принимают целочисленные значения, кратные d, то, начиная с момента, когда h < d, объекты, меньшие величины дискретности, в частности, высоты сегментов не будут n отображены в этом пространстве, - длины их станут равными нулю. Итак, при h < d дискретные n отображения частей дуги совпадут с соответствующими звеньями вписанной ломаной - отрезками цифровых прямых. Таким образом, контур, который состоит из отрезков прямых и дуг произвольных кривых, после дискретизации определен как последовательность отрезков цифровых прямых.

Последовательности отрезков цифровых прямых, которые соотвествуют дугам кривых, могут рассматриваться как ломанные линии, вписанные в эти дуги кривых. Такие вписанные ломаные линии будем называть дугами цифровых кривых. Контур может включать как отдельные отрезки прямых, так и последовательности таких отрезков - ломаные линии, которые не являются дугами цифровых кривых.

Pages:     | 1 |   ...   | 8 | 9 | 10 | 11 | 12 |   ...   | 82 |    Книги по разным темам