И.М.Журавель "Краткий курс теории обработки изображений"

В оглавление книги \ К следующему разделу \ К предыдущему разделу

Бинарные изображения: топологические характеристики

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

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

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

Сложные объекты

Иногда в поле зрения попадает более одного объекта (рис. 1). В этом случае вычисление площади, геометрического центра и ориентации приведет к значениям, “усредненным” по всем компонентам бинарного изображения. Как правило, это не то, что требуется. Желательно как-то пометить отдельные компоненты изображения и вычислить значения площади, первых и вторых моментов для каждой компоненты в отдельности.

Разметка компонент

Будем считать две точки изображения связанными, если существует путь между ними, вдоль которого характеристическая функция постоянна. Так, на рис. 1 точка А связана с точкой В, но не связана с точкой С. Связная компонента бинарного изображения есть максимальное множество связанных точек, т. е. множество, состоящее из всех тех точек, между любыми двумя из которых существует связывающий их путь.

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

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

Один из способов разметки объектов на дискретном бинарном изображении состоит в выборе произвольной точки, в которой , и приписывании метки этой точке и ее соседям. На следующем шаге помечаются соседи этих соседей (кроме уже помеченных) и т. д. По завершении этой рекурсивной процедуры одна компонента будет полностью помечена, и процесс можно будет продолжить, выбрав новую начальную точку. Чтобы ее отыскать, достаточно каким-либо систематическим образом перемещаться по изображению до тех пор, пока не встретится первая еще непомеченная точка, в которой . Когда на этом этапе не останется ни одного такого элемента, все объекты изображения окажутся размеченными.

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

Связность

Теперь нужно аккуратно рассмотреть смысл термина сосед. Если мы имеем дело с квадратным растром, то, по-видимому, соседями следует считать четыре элемента изображения, касающиеся сторон данного элемента. Но как быть с теми, которые касаются его в углах? Существуют две возможности:

— четырехсвязность – соседями считаются только элементы, примыкающие к сторонам;

— восьмисвязность – элементы, касающиеся в углах, также считаются соседями. Указанные возможности приведены на следующих диаграммах:

Оказывается, ни одна из этих схем не является полностью удовлетворительной. В этом можно убедиться, если вспомнить, что фон также можно разбить на несколько связных компонент. Здесь нам хотелось бы применить наши интуитивные представления о связности областей на непрерывном бинарном изображении. Так, например, простая замкнутая кривая должна разделять изображение на две связные области (рис. 2). Это так называемая теорема Жордана о кривой.

Рис. 2. Простая замкнутая кривая, разбивающая плоскость на две связные области.

Теперь рассмотрим простое изображение, содержащее четыре элемента со значением “единица”, которые примыкают к центральному элементу со значением “нуль”:

Это — крест с выброшенным центром. Если принять соглашение о четырехсвязности, то на изображении окажутся четыре различные компоненты (,, и ):

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

Итак, мы получили замкнутую кривую и только одну связную компоненту фона.

Одно из решений возникшей проблемы состоит в выборе четырехсвязности для объекта и восьмисвязности для фона (или наоборот). Подобная асимметрия в трактовке объекта и фона часто нежелательна, и ее можно избежать путем введения другого типа асимметрии. Будем считать соседями четыре элемента изображения, примыкающие к данному по сторонам, а также два из четырех элементов, касающихся в углах:

или

Для обеспечения симметричности отношения связности два угловых элемента должны находиться на одной и той же диагонали: если элемент А — сосед элемента В, то элемент В должен быть соседом элемента А. В дальнейшем мы будем пользоваться первым из двух возможных вариантов, приведенных выше, считая соседями элементы в направлениях N, E, SE, S, W и NW. С помощью шестисвязности как объект, так и фон можно трактовать единообразно без каких-либо дальнейших неувязок. Для изображений на квадратном растре мы примем именно такое соглашение.

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

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

Локальные вычисления и итеративная модификация

До сих пор основное внимание уделялось последовательной обработке информации, содержащейся в бинарном изображении. Чтобы повысить скорость обработки и использовать возможности больших интегральных схем (БИС), необходимо также рассмотреть, какие результаты можно получить с помощью параллельно выполняемых локальных операций. Под локальной мы понимаем то, что на вход каждой такой операции поступает информация лишь с небольшого участка изображения.

Имеются два типа вычислений, выполнимых таким образом. Мы можем скомбинировать (сложить) результаты всех локальных операций и завершить тем самым работу в один шаг (рис. 5) или создать новое изображение на основе этих результатов.

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

Локальные вычисления.

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

Какие другие характеристики представимы в виде суммы результатов локальных операций? Например, периметр: достаточно просто подсчитать количество участков на изображении, где рядом с нулями стоят единицы. Имеются два типа локальных операторов (рис. 6): операторы одного типа просматривают два соседних элемента, расположенных в одной строке, а операторы другого типа — два соседних элемента, расположенных в одном столбце. В обоих случаях результат есть ИСКЛЮЧАЮЩЕЕ ИЛИ (аÄb) двух значений на входе. Сумма всех получаемых выходов представляет собой оценку периметра.

Рис. 6. Возможность использования операции ИСКЛЮЧАЮЩЕЕ ИЛИ к двум соседним элементам изображения для выделения участков, находящихся на границе областей.

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

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

Усреднение по всем углам наклона дает среднее значение коэффициента, показывающего, во сколько раз увеличено полученное значение. Оно составляет 4/=1,273.... Разделив на это число, можно улучшить оценку периметра.

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

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

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

Итеративная модификация

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

В пакете Image Processing Toolbox системы Matlab существует много функций, осуществляющих обработку бинарных изображений, в частности, морфологические операции. Среди них – BWMORPH, DILATE, ERODE, BWPERIM, MAKELUT, BWFILL, BWSELECT, IMFEATURE и другие.

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

• Arcelli C., Pattern Thinning by Contour Tracing, Computer Graphics and Image Processing, 17, № 3, 130 – 144 (1981).
• Dyer C.R., Rosenfeld A., Thinning Algorithms for Gray–Scale Picture, IEEE Trans. on Pattern Analysis and Machine Intelligence, 1, №1, 88 – 89 (1979).
• Stefanelli R., Some Parallel Thinning Algorithms for Digital Pictures, Jornal of the ACM, 18, № 2, 255–264 (1971).
• Хорн Б.К.П. Зрение роботов: Пер. с англ. – М.: Мир, 1989. – 487 с., ил. ISBN 5–03–000570–6.

В оглавление книги \ К следующему разделу \ К предыдущему разделу