Выделение и описание областей

Материал из Техническое зрение
Перейти к: навигация, поиск

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

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

Содержание

Выделение связных областей на бинарных изображениях.

Соседство и связность на цифровых изображениях. Понятия "соседства" и "связности" тесно связаны с естественной топологией и геометрией дискретного цифрового изображения.

Как мы уже отмечали ранее, каждый пиксел изображения с координатами $\langle x,y \rangle$ имеет восемь $\textit{соседей}$, то есть примыкающих к нему ($\textit{граничащих}$ с ним) ближайших пикселов, составляющих прямоугольную окрестность $3\times 3$ (см. 2).

Прямоугольная окрестность

$(x-1,y-1)$ $(x,y-1)$ $(x+1,y-1)$
$(x-1,y)$ $(x,y)$ $(x+1,y)$
$(x-1,y+1)$ $(x,y+1)$ $(x+1,y+1)$

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


  1. соседство "по кресту" и $4$-связность;
  2. соседство "по квадрату" и $8$-связность.

Чаще используется отношение $8$-связности, при котором считается, что на прямоугольной решетке каждая точка изображения имеет восемь соседей.

$\textit{Связной областью}$ изображения считается такая его область (множество точек), в которой:


  1. все точки области имеют одинаковое значение (яркости или любого другого рассматриваемого признака);
  2. между любыми двумя точками, принадлежащими данной области, существует непрерывный путь, состоящий из точек, также принадлежащих данной области и являющихся при этом "соседями" в смысле заданного отношения соседства ($8$- или $4$-связности).


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

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

Метод "лесного пожара".

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

Пусть дано изображение Im размера $\textrm{DimX} \times \textrm{DimY}$ и меточное изображение LAB такого же размера. Массив переменного размера RegionList содержит списки (массивы) точек, принадлежащих областям. Переменная RegionListSize содержит текущий размер массива RegionList. Используется стек точек PSTACK (на стек кладутся координаты каждой новой "подожженной" точки с тем, чтобы в будущем, будучи снятой со стека, она "подожгла", то есть положила на стек координаты всех своих подходящих соседей).


Стековый алгоритм прослеживания связных областей:

Обнулить массив LAB;


$RegionListSize:=0;$

$\textbf{for} J=0 \textbf{to} DIMY-1 \textbf{do}$

$\textbf{for} I=0 \textbf{to} DIMX-1 \textbf{do}$

$\quad \textbf{if} (LAB[I,J]=0) \textbf{then}$

$\quad\quad \textbf{begin}$

$\quad\quad\quad Увеличить RegionListSize;$

$\quad\quad\quad LAB[I,J]:=RegionListSize;$

$\quad\quad\quad POINT:=(I,J);$

$\quad\quad\quad CURRENT:=Im[I,J];$

$\quad\quad\quad\quad Добавить{\_}точку(RegionList[RegionListSize],POINT);$

$\quad\quad\quad Поместить{\_}в{\_}стек(PSTACK,POINT);$

$\quad\quad\quad \textbf{while} (PSTACK не пуст) \textbf{do}$

$\quad\quad\quad\quad \textbf{begin}$

$\quad\quad\quad\quad\quad POINT:=Достать{\_}из{\_}стека(PSTACK);$

$\quad\quad\quad\quad\quad\quad \textbf{for} K:=POINT.X-1 \textbf{to} POINT.X+1 \textbf{do}$

$\quad\quad\quad\quad\quad\quad\quad \textbf{for} L:=POINT.Y-1 \textbf{to} POINT.Y+1$

$\quad\quad\quad\quad\quad\quad\quad\quad\textbf{do}$

$\quad\quad\quad\quad\quad\quad\quad\quad\quad \textbf{if}$

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad (IM[K,L]=CURRENT)\textbf{and}(LAB[K,L]=0) \textbf{then}$

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \textbf{begin}$

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad LAB[K,L]:=RegionListSize;$

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad POINT:=(K,L);$

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad Добавить{\_}точку$

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad (RegionList[RegionListSize],POINT);$

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad Поместить{\_}в{\_}стек(PSTACK,POINT);$

$\quad\quad\quad\quad\quad\quad\quad \textbf{end};$

$\quad\quad\quad\quad\quad \textbf{end};$

$\quad\quad \textbf{end;}$


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

Двухпроходный алгоритм выделения связных областей.

Данный алгоритм также предназначен для выделения $4$-связанных или $8$-связанных областей. Идея его заключается в том, что единицей просмотра изображения является уже не отдельный пиксел, а связный отрезок строки ($\textit{сегмент}$). При этом на $\textit{первом проходе}$ по изображению вновь обнаруженный связный сегмент помечается либо новой оригинальной меткой - если он ни одним пикселом не касается какого-либо уже помеченного сегмента в предыдущей по ходу анализа строке, либо меткой той области, которой принадлежит граничащий с ним отрезок предыдущей строки. Такой 4-1-16.jpg

Маски обнаружения областей: слева - в случае $4$-связности, в центре - в случае 8-связности, справа - случай "столкновения" номеров

алгоритм построчного просмотра изображения обеспечивает существенно более высокое быстродействие по сравнению с описанным выше "стековым" алгоритмом, однако в процессе пометки сегментов могут возникать так называемые $\textit{коллизии}$ или "столкновения" меток. Это происходит в том случае, если отрезок граничит одновременно с несколькими сегментами предыдущей строки, причем эти сегменты принадлежат разным областям (случай $V$-образных и $Y$-образных фигур). 4-1-17.jpg

Нахождение объектов в случае $8$-связности: $\textit{а}$, $\textit{б}$, $\textit{в}$ - шаги алгоритма. Таблица эквивалентности после шага $\textit{б}$: $2$ - $5$, $5$ - $5$, $2$ - $4$

Для устранения таких коллизий используется $\textit{второй проход}$ по изображению. На втором проходе повторно размечаются те области, для которых на первом проходе были обнаружены коллизии и занесены в специальную $\textit{таблицу эквивалентности}$ пары индексов областей, подлежащих объединению.

Рассмотрим алгоритмическую реализацию этого метода более подробно.


Первый проход.

Просматриваем содержимое изображения $f$ столбец за столбцом и присваиваем целую ненулевую метку $v$ каждому ненулевому пикселу $f(i,j)$. Значение метки $v$ выбирается в соответствии со значениями меток соседних пикселов (соседи вне изображения $f$ не рассматриваются).


  1. Если все соседи - пикселы фона (со значением равным нулю), то $f(i,j)$ присваивается новая, ранее не использовавшаяся метка.
  2. Если имеется в точности один соседний пиксел с ненулевой меткой, присваиваем эту метку пикселу $f(i,j)$.
  3. Если имеется больше чем один ненулевой пиксел среди соседей, присваиваем метку любого из уже пронумерованных пикселов.

Если метки соседей различаются ("столкновение" номеров), сохраняем такие пары номеров, как эквивалентные метки в отдельной структуре данных (таблице эквивалентности).

Второй проход.

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

4-1-18.jpg 4-1-19.jpg
Исходное бинарное изображение Размеченные связные области на бинарном изображении

Данный алгоритм единообразно реализуется и в случае четырех-, и в случае восьмисвязности. Различия заключаются только в способе формирования маски опроса соседей (рис. 16).

Поскольку оба описанных метода опираются на одно и то же определение связной области, результаты их работы будут, естественно, одинаковы. Пример разметки связных областей на бинарном изображении показан на рис. 18, 19. На меточном изображении все пикселы каждый связной области исходного изображения помечены одним и тем же значением - уникальным индексом (номером) данной области.

Сегментация полутоновых изображений.

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

Дадим формальное определение.

Пусть вся область кадра обозначается как $R$. Тогда $\textit{сегментацией изображения}$ называется процесс разбиения $R$ на такую совокупность связных областей \{$R_{i}$\}, $i=1, \ldots, n$, что для них выполняются следующие основные условия:

(а) $R = \cup_{i = 1,\ldots, n} R_{i}$,

(б) $R_{i} \cap R_{j}=\emptyset $, $\forall i \ne j$,

(в) Pred($R_{i}) = \textrm{TRUE}$, $i=1,\ldots, n$,

(г) $\textrm{Pred}(R_{i} \cup R_{j}) = \textrm{FALSE},\quad \forall i \ne j \hspace{6.2cm}$


$$ \begin{gather}\tag{1} \end{gather} $$ где Pred($R$) - булевский предикат однородности области в некотором заданном смысле.

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

Рассмотрим теперь основные методы сегментации изображений, используемые в современном машинном зрении.

Пороговая и мультипороговая сегментация.

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

Пороговая сегментация выполняется следующим образом:


\begin{gather*} g(i,j) = 1, \quad \textrm{для} \quad f(i,j) \le T,\cr g(i,j) = 0, \quad \textrm{для} \quad f(i,j) < T, \end{gather*} где $g(i,j)$ - элемент результирующего бинарного изображения, $f(i,j)$ - элемент исходного изображения.

Успех пороговой сегментации зависит от способа выбора порога. В главе 3.1 мы рассматривали методы адаптивного выбора порога как функции глобальной или локальной гистограммы изображения.

Существуют следующие основные виды пороговой сегментации.


$\textit{Диапазонная}$ пороговая сегментация. Сегмент изображения считается "областью", если его уровни яркости находятся в заданном диапазоне $D$, или "фоном" в противном случае:

$g(i,j) = 1$, для $f(i,j)\in D$,

$g(i,j) = 0$, в противном случае.

$\textit{Мультипороговая сегментация.}$ Используется в том случае, если исходное изображение обладает не бимодальной, а мультимодальной гистограммой. В этом случае результирующее изображение не является бинарным:

$g(i,j) = 1$, для $f(i,j)\in D_{1}$,

$g(i,j) = 2$, для $f(i,j)\in D_{2}$,

$g(i,j) = 3$, для $f(i,j)\in D_{3}$,

${\ldots}{\ldots}{\ldots}{\ldots}{\ldots}{\ldots}{\ldots}{\ldots}{\ldots}{\ldots}$

$g(i,j)=n$, для $f(i,j)\in D_{n}$,

$g(i,j) = 0$, в противном случае.

Адаптивная мультипороговая сегментация также рассматривалась ранее в главе 3.1. На рис. 20 - 23 приводятся примеры такой сегментации.

4-1-20.jpg 4-1-21.jpg
Исходное изображение Адаптивная мульти-

пороговая сегментация изображе-

ния по гистограмме (три диапазо-

на яркости)

4-1-22.jpg 4-1-23.jpg
Исходное изображение Адаптивная мульти-

пороговая сегментация изображе-

ния по гистограмме (пять диапа-

зонов яркости)

Методы слияния, разбиения и слияния/разбиения областей.

$\textit{Слияние областей}$. Определение (5) фактически определяет некий итеративный алгоритм $\textit{слияния областей}$, который начинается с минимальных областей размером в один пиксел, которые затем в повторяющихся циклах опроса изображения "сливаются" (объединяются) с соседними областями, если для объединенной области выполняется условие Pred($R_{i}) = \textrm{TRUE}$. Условием останова такого алгоритма слияния служит выполнение всех четырех условий выражения. Это означает, что достигнут такой шаг процесса, на котором больше нельзя найти ни одной пары областей, которые можно было бы подвергнуть слиянию.

Описанный выше метод приводит к качественным результатам сегментации. Основным его недостатком является то, что такая сегментация, начинающаяся с уровня отдельных пикселов, как правило, требует для своего осуществления значительного количества времени. Причем большая часть времени тратится именно на начальных этапах работы алгоритма, когда размеры объединяемых областей малы, а количество вариантов объединения - велико. В связи с этим соблазнительной является идея начать итеративный процесс анализа списка областей с некоторого обоснованного начального приближения, которое сразу давало бы существенно меньшее количество кандидатов. В качестве такого начального приближения могут выбираться, например, результаты выделения контуров оператором Марра (контуры оператора Марра всегда замкнуты, следовательно, как раз задают разбиение кадра на непересекающиеся области). Однако такая предварительная сегментация ($\textit{пресегментация}$) не гарантирует, что для всех предварительно выделенных областей будут выполняться условия Pred($R_{i}) = \textrm{TRUE}$ (ведь выделение предварительных областей происходило не на базе Pred($R_{i})$, а по другим критериям). В этом случае неудовлетворительные области вновь приходится подвергать разбиению. Таким образом, мы приходим к следующему алгоритму сегментации.


${Алгоритм 1.}$ ${Слияние областей}$ (общая структура).


  1. Осуществить пресегментацию изображения на "стартовые" области каким-либо неитеративным (однократным) методом.
  2. Определить критерий слияния двух соседних областей.
  3. Итеративно находить и объединять все пары соседних областей, удовлетворяющие критерию слияния.
  4. Если на очередном шаге ни одной пары кандидатов на объединение не найдено - остановиться и выйти из алгоритма.

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


$\textit{Разбиение областей}$ - метод сегментации, противоположный слиянию. Разбиение начинают с представления всего изображения как простой области, которая не всегда соответствует условию однородности. В процессе сегментации текущие области изображения последовательно расщепляются в соответствии с заданными условиями однородности. Методы слияния и разбиения областей далеко не всегда приводят к одним и тем же результатам сегментации, даже если в них используется один и тот критерий однородности.


$\textit{Слияние/разбиение областей}$. В большинстве случаев используется комбинация методов слияния и разделения. При этом часто используют пирамидальное представление изображения и области-квадранты. При этом элементы квадродерева областей соответствуют уровням пирамиды изображений. Процессы слияния и разбиения областей идут поочередно на каждой итерации. Если какая-либо область на каком-либо пирамидальном уровне неоднородна, она разделяется на четыре подобласти. Напротив, если на каком-либо уровне пирамиды наблюдаются четыре соседние области с приблизительно одинаковой величиной однородности, они сливаются в простую область на более высоком уровне пирамиды.

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

Описанное дерево сегментации легко реализуемо программно.


${Алгоритм 2}$. ${Слияние/разбиение}$ (рис. 24).


  1. Провести начальную сегментацию областей, определить критерий однородности и пирамиду структуры данных.
  2. Если какая-либо область $R$ в пирамиде структуры данных неоднородна

($\textrm{Pred}(R)=\textrm{FALSE}$), разделяем ее на четыре дочерние области. Если любые четыре

4-1-24.jpg

Разделение и слияние в иерархической структуре данных

области, имеющие одинаковых родителей, могут быть слиты в простую однородную область, слияние областей осуществляется. Если нет больше областей, которые могли бы быть разделены или слиты на данном шаге, переходим к шагу ($3$).

  1. Если имеются какие-либо две соседние области $R_{i}$, $R_{j}$ (даже если они

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

  1. Производим слияние малых областей с самой большой подобной соседней

областью, если необходимо, устраняем области с размерами меньше заданных.


На рис. 25 показана схема сегментации изображения при помощи дерева квадрантов.

4-1-25.jpg

Сегментация с помощью дерева квадрантов

На рис. 26 - 27 приводятся примеры сегментации изображений методом слияния и методом слияния/разбиения. Как видно из приведенных примеров, результаты сегментации различными методами не всегда совпадают.

4-1-26.jpg

Примеры сегментации: $\textit{а}$ - исходное изображение; $\textit{б}$ - результат сегментации изображения методом слияния; $\textit{в}$ - результат сегментации изображения методом слияния/разбиения

4-1-27.jpg

Примеры сегментации: $\textit{а}$ - исходное изображение; $\textit{б}$ - результат сегментации изображения методом слияния; $\textit{в}$ - результат сегментации изображения методом слияния/разбиения


Способы описания выделенных областей.

Топологические признаки:

  1. число несвязных компонент (число отдельных объектов в составе образа);
  2. число дыр (есть ли дыры внутри объекта);
  3. число Эйлера (число объектов минус число дыр).

Геометрические признаки:

В задачах распознавания образов для классификации и селекции выделенных областей часто используются интегральные геометрические признаки. Обычно эти признаки задаются эвристически и характеризуют форму образа. К ним относятся следующие основные $\textit{эвристики}$:

  1. площадь образа;
  2. положение центра тяжести образа;
  3. положение центра тяжести образа, рассматриваемого как бинарный;
  4. периметр образа;
  5. отношение квадрата периметра к площади образа;
  6. формат;
  7. компактность;
  8. периметр и площадь описанного прямоугольника минимальной площади;
  9. отношение площади описанного прямоугольника к площади образа;
  10. отношение квадрата периметра описанного прямоугольника к его площади;
  11. формат описанного прямоугольника;
  12. относительные длина и ширина образа.

$\textit{Площадь}$ $S$ считается как число ненулевых элементов образа.

Координаты $\textit{центра тяжести}$ образа рассчитываются через статические моменты: $$ x_c =\frac{\int\limits_\Omega {B(x,y)xdx} }{\int\!\!\!\int\limits_\Omega {B(x,y)dxdy} };\qquad y_c =\frac{\int\limits_\Omega {B(x,y)ydy} }{\int\!\!\!\int\limits_\Omega {B(} x,y)dxdy}, $$ что для бинарной матрицы имеет вид $$ x_{c} =\frac{\sum\limits_\Omega x }{S}; \qquad y_{c} =\frac{\sum\limits_\Omega y }{S}, $$ а для полутонового изображения $$ x_{c} =\frac{\sum\limits_\Omega {xB(x,y)} }{\sum\limits_\Omega {B(x,y)} }; \qquad y_{c} =\frac{\sum\limits_\Omega {yB(x,y)} }{\sum\limits_\Omega {B(x,y)} }. $$ $\textit{Периметр}$ образа равен сумме модулей элементарных векторов контура, соединяющих два соседних элемента (по 8-связности), $$ P_2 =\sum\limits_{k=1}^{N1} {\vert P\vert +\sqrt 2 } \sum\limits_{k=N1+1}^N {\vert P_1 \vert } , $$ где $P$ и $P_{1}$ - элементарные векторы, ориентированные соответственно по сетке и под углом $45$°.

Для вычисления значения признака $F$ ($\textit{формата}$) по контурным точкам образа строится матрица рассеяния $$ E=\left( {{\begin{array}{*{20}c} {S_{20} } & {S_{11} } \\ {S_{11} } & {S_{02} } \\ \end{array} }} \right), $$ где $$ S_{pq} =\sum\limits_{\langle x,y \rangle\in \Gamma _\Omega } {(x -x_c )} ^p(y -y_c )^q $$ и находятся собственные числа этой матрицы: $$ \lambda { }_i=\frac{S_{20} +S_{02} }{2}\pm \sqrt {\frac{\left( {S_{20} +S_{02} } \right)^2}{4}+S_{11}^2 } . $$ Очевидно, что $\lambda _{1,2}$ - действительные положительные числа ($\lambda $ может обращаться в $0$, если образ представляет собой прямую линию).

Формат рассчитывается по формуле (для $\lambda _{1} \ge \lambda _{2})$ $$ F=\frac{\lambda _1 }{\lambda _2 }. $$ $\textit{Компактность} рассчитывается по формуле$ $$ Z=\frac{S}{S_u -S}, $$ где $S$ - площадь образа, $S_{u}$ - площадь описанного прямоугольника, ориентированного как эквивалентный эллипс.

Для определения $\textit{ориентации}$ находятся собственные векторы матрицы рассеяния: $$ \left( {{\begin{array}{*{20}c} {S{ }_{20}-\lambda _1 } & {S_{11} } \\ {S_{11} } & {S_{02} -\lambda _2 } \\ \end{array} }} \right)\left( {{\begin{array}{*{20}c} x \\ y \\ \end{array} }} \right)=0. $$ Чтобы найти величины сторон $\textit{описанного прямоугольника}$, ориентированного по собственным векторам, достаточно определить проекции образа на эти векторы. Величина проекции контурной точки образа $\langle x,y \rangle$ на один из собственных векторов (например, $\langle x_1, y_1 \rangle$, соответствующий собственному числу $\lambda _{2})$ определяется по формуле $$ R=\sqrt {x^2+y^2} \sin \left( {\rm{arctg}\frac{y}{x}-\rm{arctg}\frac{y_1 }{x{ }_1}} \right). $$ Подставляя значения собственных векторов, получаем $$ R_1 =\left( {y-\frac{\lambda _1 -S_{20} }{S_{11} }x} \right)\frac{1}{\sqrt {x_1^2 +y_1^2 } }; $$ $$ R_2 =\left( {y-\frac{\lambda _2 -S_{02} }{S_{11} }x} \right)\frac{1}{\sqrt {x_2^2 +y_2^2 } }. $$ $\textit{Периметр и площадь минимального описанного прямоугольника}$ рассчитываются по следующим формулам: $$ P_{3} = 2 \cdot (T_{1} + T_{2}); $$ $$ S_{u} = T_{1} \cdot T_{2}, $$ где $T_{1}$ и $T_{2}$ - стороны описанного прямоугольника.

$\textit{Отношение площади описанного прямоугольника к площади образа}$ рассчитывается по формуле $$ Z_1 =\frac{S_u }{S}. $$ Отношение квадрата периметра описанного прямоугольника к его площади рассчитывается по формуле $$ Z_2 =\frac{P_3^2 }{S_u }. $$ $\textit{Формат описанного прямоугольника}$ $$ F_1 =\frac{T_1 }{T_2 }. $$ $\textit{Относительные длина и ширина}$ $$ P_4 =\frac{P_2 }{T_2 }; \qquad P_5 =\frac{P_2 }{T_1 }. $$

Моменты.

Другой группой признаков являются $\textit{моменты}$:$$ m_{\alpha \beta } =\int\!\!\!\int\limits_\Omega {B(x,y)x^\alpha y^\beta } dx dy, $$ где $\Omega$ - образ в декартовой системе координат $\langle x,y \rangle$; $B(x,y)$ - значение функции интенсивности в точке $\langle x,y \rangle$.

Для дискретного изображения имеем $$ m_{pq} =\sum\limits_{\langle x,y \rangle \in \Omega } {x^p y^q B(x,y)} . $$ Специальными приемами удается получить величины, инвариантные к смещению, изменению размера и повороту изображения:


1. $\textit{моменты, инвариантные к смещению}$, $$ \mu _{pq} =\sum\limits_{\langle x,y \rangle \in \Omega } {(x -x_c )^p(y -y_c )^qB(x,y)} , $$ где $x_{\textrm{c}}$, $y_{\textrm{c}}$ - координаты центра тяжести образа;

2. $\textit{моменты, инвариантные к изменению масштаба}$, $$ \eta_{pq} =\frac{\mu _{pq} }{\sum\limits_{i+j=p+q} {\vert \mu _{ij} \vert } }. $$ Действительно, при изменении масштаба в $k$ раз значение всех центральных моментов изменится в $k^{p+q+2}$ раз. Но так как все моменты имеют $p + q = \rm{const}$, то величина $\eta _{pq}$ не изменится;

3. $\textit{моменты, инвариантные к повороту}$,

\begin{align*} M_1 &= \eta _{02} +\eta _{20} ; \\ M_2 &= a_1^2 +4\eta _{11}^2 ; \\ M_3 &= a_2^2 +a_4^2 ; \\ M_4 &= a_3^2 +a_5^2 ; \\ M_5 &= a_2 a_3 (a_3^2 -3a_5^2 )+a_4 a_5 (3a_3^2 -a_5^2 ); \\ M_6 &= a_1 (a_3^2 -a_5^2 )+4\eta _{11} a_3 a_5 ; \\ M_7 &= a_4 a_3 (a_5^2 -3a_3^2 )+a_2 a_5 (a_3^2 -a_5^2 ),\\ \end{align*} где \begin{align*} a_1 &= \eta _{20} -\eta _{02} ; \\ a_2 &= \eta _{30} -3\eta _{12} ; \\ a_3 &= \eta _{30} +\eta _{12} ; \\ a_4 &= 3\eta _{21} -\eta _{03} ; \\ a_5 &= \eta _{21} -\eta _{03} . \end{align*} Используются также и другие системы инвариантных признаков.

Текстурные признаки.

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


4-1-28.jpg

Примеры изображений с несколькими текстурными областями

В качестве характеристик текстуры используются $\textit{статистические, структурные и спектральные}$ характеристики.

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

$\textit{Характеристики, вычисляемые по гистограмме яркости изображения (области)}$, опираются на центральные моменты порядка $n$: $$ \mu _{n}=\sum _{i} (i-m)^{n }\cdot {\rm Hist}[i] , $$ где $m$ - $\textit{средняя яркость}$ изображения:

$$ m =\sum _{i} i^{ }\cdot {\rm Hist}[i] . $$

Для описания текстуры часто используют второй момент, или $\textit{дисперсию}$: $\sigma ^{2}={\mu }_{2}$. Величина дисперсии характеризует "негладкость" изображения области. Дескриптор $$ R=1 - \frac {1} {1+\sigma ^{2}} $$ равен нулю для областей постоянной яркости и приближается к 1 для "негладких" областей.

Момент $\mu _{3 }$ характеризует $\textit{асимметрию}$ гистограммы (преобладание областей одной яркости над другой). Момент $\mu_{4}$ харатеризует т.н. $\textit{эксцесс}$, или "остроту" распределения яркости.

По яркостной гистограмме также часто вычисляют $\textit{однородность}$ $$ U = \sum_{i}{\rm Hist}^{2}[i] $$ и $\textit{среднюю энтропию}$

$$ e = - \sum_{i} {\rm Hist}[i]\cdot \textrm{log}_{2}({\rm Hist}[i]) . $$

В текстурном анализе также часто используются $\textit{двумерные гистограммы (матрицы смежности)}$.

Рассмотрим сначала $\textit{бинарную матрицу смежности}$ типа ($1$ - $1$). Эта матрица размера $\textrm{WinX} \times \textrm{WinY}$ вычисляется для бинарных изображений, пикселы которых принимают значения на множестве {$0,1$}. Элемент матрицы $H[k,l]$ содержит число пар пикселов изображения $A$, удовлетворяющих условию $A[x,y]=A[x+k,y+l]=1$.

Можно также построить $\textit{матрицу попарной совместной встречаемости цветов (значений яркости) для заданного значения смещения}$ $\langle k,l \rangle$. При этом каждый элемент матрицы вычисляется как $$ P[I_1,I_2]={\rm count}_{x=1,\ldots, \textrm{WinX} , y=1,\ldots, \textrm{WinY} }(A[x,y]=I_1, A[x+k,y+l]=I_2), $$ то есть для любых двух значений интенсивности $I_1,I_2 \in \{0,\ldots, 255\}$, ячейка матрицы совместной встречаемости $P[I_1,I_2]$ содержит подсчитанное количество раз, когда на изображении выполняется условие $(A[x,y]=I_1$, $A[x+k,y+l]=I_2)$.

$\textit{Яркостная матрица смежности}$ строится далее как $$ C[I_1, I_2]= \frac {P[I_1, I_2]} {n}, $$ где $n$ - число всех возможных пар элементов изображения, разнесенных на вектор $\langle k,l \rangle$.

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

По матрице смежности строятся следующие полезные $\textit{дескрипторы текстуры}$:


1. Макcимум вероятности $$\max_{ij} C[i,j] ,$$

2. Момент порядка $k$ разности элементов $$\sum_{i}\sum_{j } (i-j)^{k}\cdot C[i,j] ,$$

3. Обратный момент разности порядка $k$ $$ \sum_i \sum_j C[i,j] / (i-i)^{k} , $$

4. Смежная однородность $$\sum_{i}\sum_{j } C[i,j]^{2 } ,$$

5. Смежная энтропия $$ -\sum_{i}\sum_{j} C[i,j]\cdot \textrm{log}_{2}(C[i,j]) . $$

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

Морфологические дескрипторы.

Морфологические дескрипторы областей и фигур - морфологические спектры и скелеты - подробно описаны в "Морфологическом анализе изображений".

Полезные ссылки

  1. ☝ К началу
  2. ☜ Выделение и описание характерных элементов изображения
Личные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты