Современные технологии обработки изображений 24

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

В этой работе рассматриваются черно–белые (бинарные) изображения [1]. Их легче получать, хранить и обрабатывать, чем изображения, в которых имеется много уровней яркости. Однако, поскольку в бинарных изображениях кодируется информация лишь о силуэте объекта, область их применения ограничена. В дальнейшем будут сформулированы условия, необходимые для успешного использования методов обработки бинарных изображений. Здесь же внимание акцентируется на таких простых геометрических характеристиках изображений, как площадь объекта, его положение и ориентация. Подобные величины могут использоваться, например, в процессе управления механическим манипулятором при его работе с деталями.

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

Бинарные изображения

Начнем со случая, когда в поле зрения находится объект, а все остальное считается “фоном”. Если объект оказывается заметно темнее (или светлее), чем фон, то легко определить характеристическую функцию , которая равна нулю для всех точек изображения, соответствующих фону, и единице для точек на объекте (рис.1) или наоборот.

Рис. 1. Бинарное изображение, определяемое характеристической функцией , которая принимает значение “нуль” и “единица”.

Часто бинарное изображение получают пороговым разделением обычного изображения. К нему также можно прийти путем порогового разделения расстояния на “изображении”, полученном на основе измерений расстояний.

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

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

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

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

Пример:

Этой операции соответствует функция BWEULER – вычисление чисел Эйлера в пакете Image Processing Toolbox:
L=imread(‘test.bmp’);
L=double(L);
imshow(L);

e=bweuler(L(:,:,1), 4)
e =
1; % На объекте действительно одно отверстие.

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

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

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

Простые геометрические характеристики

Допустим снова, что в поле зрения находится лишь один объект. Если известна характеристическая функция то площадь объекта вычисляется следующим образом:

,

где интегрирование осуществляется по всему изображению I. При наличии более одного объекта эта формула дает возможность определить их суммарную площадь.

Пример:

В системе Matlab этой операции соответствует функция BWAREA – вычисление площади объектов.
L=imread(‘test.bmp’);
L=double(L);
imshow(L);

S=bwarea(L(:,:,1))
e =
24926; %Площадь объекта в пикселах (размер изображения 236х236).

 

Площадь и положение

Как определить положение объекта на изображении? Поскольку объект, как правило, состоит не из одной единственной точки, мы должны четко определить смысл термина “положение”. Обычно в качестве характерной точки объекта выбирают его геометрический центр (рис. 2).

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

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

,

а относительно оси  — по формуле

,

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

Ориентация

Мы также хотим определить, как расположен объект в поле зрения, т. е. его ориентацию. Сделать это несколько сложнее. Допустим, что объект немного вытянут вдоль некоторой оси; тогда ее ориентацию можно принять за ориентацию объекта. Как точно определить ось, вдоль которой вытянут объект? Обычно выбирают ось минимального второго момента. Она представляет собой двумерный аналог оси наименьшей инерции. Нам необходимо найти прямую, для которой интеграл от квадратов расстояний до точек объекта минимален; этот интеграл имеет вид

,

где  — расстояние вдоль перпендикуляра от точки с координатами  до искомой прямой.

Иной путь решения проблемы состоит в попытке найти угол поворота , при котором матрица вторых моментов размера 2×2 имеет диагональный вид.

(В пакете Matlab операции определения центра масс, ориентации а также другие морфометрические признаки вычисляются с помощью функции IMFEATURE.)

Проекции

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

Дискретные бинарные изображения

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

,

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

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

Кодирование с переменной длиной

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

0

1

1

1

1

0

0

0

1

1

0

0

0

0

Для обозначения начала каждой строки нужно ввести специальный признак. Кроме того, принимается соглашение относительно того, с чего начинается строка (с нуля или единицы). Если строка начинается с противоположного символа, то первым символом кода устанавливается нуль.

Другой подход к обработке изображений описан в книге [2]. Книга [3] содержит сведения о некоторых работах в области обработки бинарных изображений. Много интересных бинарных изображений, полученных художниками, можно найти в книге [4].

Кодирование с переменной длиной кодовой последовательности основывается на избыточности лишь в одном измерении. В целях уменьшения затрат на передачу и хранение данных было предпринято несколько попыток использовать пространственную взаимосвязь между элементами изображения в обоих направлениях. Быть может наиболее удачной среди схем такого рода является схема, разработанная фирмой IBM и описанная в отчете [5].

В системе Matlab также рассматривается один из видов кодирования, который содержится в описании функции BWPACK.

Литература

 

  • Хорн Б.К.П. Зрение роботов: Пер. с англ. – М.: Мир, 1989. – 487 с., ил. ISBN 5–03–000570–6.
  • Rosenfeld A., Kak A.C., Digital Picture Processing, Vols. 1, 2, Second Edition, Academic Press, New York, 1982.
  • Stoffel J.C. (ed.), Graphical and Binary Image Processing and Applications, Artech House, Inc., Massachusetts, 1982.
  • Grafton C.B. (ed.), Silhouettes – A Pictorial Archive of Varied Illustrations, Dover Publications, New York, 1979.
  • Mitchell J.L., Goertzel G., Two–Dimensional Facsimile Coding Scheme, IBM Reserch Report RC 7499, Jan., 1979.

 

 

 

Наверх

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

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

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

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

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

Иногда в поле зрения попадает более одного объекта (рис. 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.