4.7. ОБНАРУЖЕНИЕ И ПРОСЛЕЖИВАНИЕ КОНТУРОВ БИНАРНЫХ ИЗОБРАЖЕНИЙ

Пусть в бинарной сцене содержится совокупность изображений. Начальной точкой изображения назовем принадлежащую ему точку с минимальным номером строки и номером столбца, минимальным в этой строке. Упорядочивание изображений выполним по правилу: если проранжировать линейные адреса в ОЗУИ всех их начальных точек, то номер начальной точки будет равен номеру изображения. Линейный адрес точки связан с номером ее строки и номером ее столбца следующим образом:

где количество точек в строке изображения.

Наиболее просто путем строчного поиска в порядке нарастания линейных адресов находится начальная точка изображения Для определения ЭВ контура необходимо найти следующую точку контура, которая определяется осмотром окружающих точку точек (рис. 4.16).

Алгоритм поиска точки как первой заполненной ячейки ОЗУИ, дает правильные результаты лишь для изображения Поиск начальных точек изображений связан с исключением из рассмотрения точек изображений

С этой целью формируется сопряженное по адресам

Рис. 4.16. Формы стробов для выделения контурных точек

ячеек ОЗУИ другое ОЗУК (ОЗУ контуров), в котором хранятся контуры ранее обнаруженных изображений.

Система поиска изображений в бинарной сцене работает как конечный автомат с памятью. В табл. 4.1 приведены возможные состояния автомата поиска, а на рис. 4.17 — его граф.

Рис. 4.17. Упрощении» граф автомата поиска первой точки контура нового изображения

Таблица 4.1. Состояние автомата поиска начальной точки нового изображения

В качестве базового алгоритма прослеживания линии контура, при котором последовательно, без разрывов выделяются контурные точки изображения и формируется код контура, целесообразно использовать алгоритм, предложенный Розенфельдом [49]. По сравнению с другими алгоритмами (например, алгоритмом «жука» [21]), он не приводит к зацикливанию при любых конфигурациях контура и допускает простую реализацию. По Данному алгоритму на n-м шаге прослеживания формируется строб размером 3X3 элемента (рис. 4.16, б). Его центр совмещается с текущей точкой контура (рис. 4.18). Благодаря непрерывности линии контура предыдущая, текущая и последующая точки контура всегда находятся в пределах этого строба, т. е.

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

Рис. 4.18. Выделение контурной точки

Рис. 4.19. Конфигурация строба для базового алгоритма прослеживания контура

строба тоже всегда будет относиться к фону, но при условии, что предыдущий ЭВ не был диагональным.

На рис. 4.19 показаны конфигурации строба прослеживания, которые в соответствии с базовым алгоритмом будут оптимальными с позиции минимального требуемого количества просматриваемых ячеек. Рассмотрим получающееся при этом сокращение времени прослеживания.

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

Для среднего времени прослеживания линии контура из k ЭВ можно записать:

где априорная вероятность изображения класса, ; — безусловная вероятность ЭВ переходная вероятность смены вектора вектором для изображения класса.

Весовые коэффициенты равные количеству шагов, которые надо совершить в стробе от до определяются алгоритмом поиска точки и задаются в виде матрицы Для алгоритмов ПТВЭ и ПВЭ эти матрицы имеют, соответственно, вид:

Сравним характеристики алгоритмов для двух крайних случаев. В первом случае смена ЭВ есть независимый процесс, все векторы равновероятны, т. е.

Во втором случае смена ЭВ представляет сильно коррелированный процесс, причем по-прежнему все векторы равновероятны, т. е.

В табл. 4.2 приведены значения среднего времени поиска контурной точки, рассчитанные по формуле (4.7.1) для случая, когда все классы равновероятны. Как и следовало ожидать, наличие корреляции снижает время поиска, так как при сильной корреляции ЭВ сохраняют свое значение, т. е. и количество элементов в стробе от точки до точки равно четырем для алгоритма ПВЭ и двум или трем — для ПТВЭ.

Таблица 4.2. Среднее число шагов поиска в стробе последующей точки контура

Если смена ЭВ представляет собой независимый процесс, то точка с одинаковой вероятностью может находиться в любом элементе строба. Алгоритм ПТВЭ (табл. 4.2) обеспечивает по сравнению с алгоритмом ПВЭ ускорение процесса прослеживания линии контура примерно в полтора раза.

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

При обнаружении и прослеживании контуров бинарных изображений перепады яркостей на границах были идеальными. Это дает возможность получить контуры изображений и их комплекснозначные коды, минуя стадию формирования силуэтных изображений. При решении аналогичных задач для многоградационных изображений перепад яркости на границах фон/изображение или изображение/изображение становится в реальных случаях чаще всего пологим и зашумленным. Из-за растянутости и переменного характера крутизны линия контура как линия внешней границы изображения становится неопределенной в пределах ширины этого перепада, а действие шумов приводит к ошибкам выделения контуров. Подавление таких ошибок связано с использованием методов борьбы с шумами. В этом случае строб для прослеживания линии контура будет иметь более сложную структуру: каждый его элемент представляет собой квадратное окно из пикселей (рис. 4.20).

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

где яркости предыдущих контурных точек; N — число этих точек; некоторая константа, превышающая приращение средней яркости сцены за один шаг.

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

Рис. 4.20. Строб для прослеживания контуров изображений в зашумленной многоградационной сцене

На рис. 4.21, а показаны два положения строба, формирующего линию контура, причем это строб на предшествующем шаге, а на текущем. Буквами «Ф» здесь отмечены точки фона, «к» - контурные точки и «О» - точки изображения объекта.

Этим точкам соответствуют полученные на предшествующих шагах средние значения яркостей (рис. 4.21, б): яркость объекта контурных точек и точек фона Центр строба находится в точке На шаге центр строба переместится в точку найденную также на шаге.

Порядок просмотра строба показан стрелками (рис. 4.21, а). Анализ базируется на допущении, что контурные точки относятся к объекту. В процессе анализа для каждой непроклассифицированной точки строба вычисляется расстояние по яркости точки от средней яркости контурных и фоновых точек, полученных на шаге (рис. 4.21, б):

Решение о принадлежности точки к контуру выносится при выполнении условия

Рис. 4.21. Классификация точек строба по яркостному расстоянию

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

В заключение рассмотрим один из подходов к формированию силуэтных изображений при наличии только их контуров.

До сих пор рассматривались вопросы, связанные с контуром изображения, образованным граничными точками

Рис. 4.22. Внешний и внутренний контуры изображений объекта

изображения. Пусть — множество точек изображения. Внутренняя точка этого множества обладает свойством четырех-связности, т. е. смежные с ней точки — правая, левая, нижняя и верхняя — тоже принадлежат Точка этого множества будем граничной в том случае, когда не все эти смежные точки относятся к Q [49].

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

Рассмотрим, каким образом наличие внешнего контура облегчает решение задачи формирования силуэтного изображения при наличии внешнего и внутреннего контуров [89]. На рис. 4.22 показана ситуация, связанная с наличием узкого участка толщиной в один элемент. При сканировании изображения по строке А после первой точки внутреннего контура всем последующим ячейкам строки присваивается единичная яркость до тех пор, пока не встретится следующая точка внутреннего контура При сканировании по строке

В точки внутреннего контура совмещены. Поэтому значение единичной яркости будет присвоено всем точкам фона, находящимся правее точки

Наличие внешнего контура меняет ситуацию. При сканировании по строке заполнение точек единичной яркостью начинается после появления первой точки внешнего контура и прекращается при появлении второй точки внешнего контура.