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

      В качестве исходного материала была взята Глава 10 "Сегментация изображения" из книги Rafael C. Gonzalez, Richard E. Woods "Digital Image Processing" Second Edition, ISBN 0-201-18075-8, Copyright ©2002 by Prentice-Hall, Inc. Ниже представленный текст приводится в переводе с английского в обработанном виде.

Содержание

       Введение

• Определение разрывов яркости
• Определение границ и связывание контуров
• Пороговая сегментация
• Сегментация, основанная на областях
• Сегментация на основе морфологического водораздела

Введение

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

1. Определение разрывов яркости

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

w1	w2	w3
w4	w5	w6
w7	w8	w9

Рисунок 1 - Скользящая маска

      Для показанной на рис. 1 маски размером 3*3 элемента эта процедура основана на вычислении линейной комбинации коэффициентов маски со значениями яркости элементов изображения, покрываемых маской. При использовании этой маски отклик в каждой точке изображения задается выражением:

      R = w₁*z₁ + w₂*z₂ + ... + w₉*z₉       (1)

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

        Определение точек

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

-1	-1	-1
-1	8	-1
-1	-1	-1

Рисунок 2 - Маска для обнаружения точек

      Будем считать, что в том пикселе, куда попадает центр маски, обнаружена точка, если:

      |R| >= T       (2)

      где Т — неотрицательный порог, a R вычисляется в соответствии с (1). В данной формуле измеряется взвешенная сумма разностей значений центрального элемента и его соседей. Интерес представляют только достаточно большие различия (определяемые порогом Т), при которых точка может считаться изолированной. Сумма коэффициентов маски равна нулю, так что на областях постоянной яркости она будет давать нулевой отклик.

       Определение линий

      Следующим по уровню сложности является обнаружение линий. Рассмотрим набор масок, показанный на pис. 3, 4, 5, 6:

-1	-1	-1
2	2	2
-1	-1	-1

Рисунок 3 - Маска для обнаружения горизонтальных линий

-1	-1	2
-1	2	-1
2	-1	-1

Рисунок 4 - Маска для обнаружения линий под углом +45

-1	2	-1
-1	2	-1
-1	2	-1

Рисунок 5 - Маска для обнаружения вертикальных линий

2	-1	-1
-1	2	-1
-1	-1	2

Рисунок 6 - Маска для обнаружения линий под углом -45

      При скольжении первой маски по изображению, наиболее сильный отклик будет на горизонтальных линиях толщиной в один пиксель; вторая маска на pис. 4 дает наибольший отклик на линиях, проходящих под углом +45°; третья — на вертикальных линиях; четвертая — на проходящих под углом —45°. Эти направления можно выявить и по тому признаку, что предпочтительные направления каждой из масок характеризуются большими значениями весовых коэффициентов (а именно, 2), чем любые другие направления. Cумма коэффициентов каждой маски равна нулю, так что они будут давать нулевой отклик на областях постоянной яркости.

      Обозначим через R₁, R₂, R₃ и R₄ отклики масок, показанных на pис. 3, 4, 5, 6, где значения R, вычисляются согласно соотношению (1). Изображение обрабатывается независимо с помощью каждой из этих масок. Если в некоторой точке изображения | R_i| > | R_j | для всех j не равно i, то эта точка, скорее всего, связана с линией, ориентированной вдоль направления маски i.

        Определение перепадов

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

Рисунок 7 - Профиль перепада яркости, первая и вторая производная профиля

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

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

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

      Операторы градиента

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

z1	z2	z3
z4	z5	z6
z7	z8	z9

Рисунок 8 - Значения яркостей в окрестности некоторого элемента изображения

      Вычисление градиента изображения состоит в получении величин частных производных G_x=df/dx и G_у=df/dy для каждой точки. Oдин из способов нахождения первых частных производных G_x и G_у в конкретной точке состоит в применении следующего градиентного оператора Собеля:

G_x = (z₇ + 2*z₈ + z₉) - (z₁ + 2*z₂ + z₃)        (3)

G_у = (z₃ + 2*z₆ + z₉) - (z₁ + 2*z₄ + z₇)        (4)

      Для данного оператора Собеля, который выявляет горизонтальные и вертикальные контуры (перепады яркости), нетрудно представить соответствующие маски для свертки с исходным изображением. Также можно изменить приведенные формулы (3) и (4) таким образом, чтобы они давали максимальный отклик для контуров, направленных диагонально. Дополнительные пары масок оператора Собеля, предназначенные для обнаружения разрывов в диагональных направлениях, показаны на рис. 9, 10:

0	1	2
-1	0	1
-2	-1	0

Рисунок 9 - Маска Собеля для обнаружения точек, лежащих на диагональном перепаде -45 градусов

-2	-1	0
-1	0	1
0	1	2

Рисунок 10 - Маска Собеля для обнаружения точек, лежащих на диагональном перепаде +45 градусов

      У каждой из масок на рис. 9, 10 сумма коэффициентов равна нулю, т.е. эти операторы будут давать нулевой отклик на областях постоянной яркости, как и следовало ожидать от дифференциального оператора. Рассмотренные маски применяются для получения составляющих градиента Gx и Gy. Для вычисления величины градиента эти составляющие необходимо использовать совместно. Часто используется подход, при котором величина градиента вычисляется приближенно через абсолютные значения частных производных:

Gradient = |G_x| + |G_y|        (5)

      Лапласиан

      Лапласиан двумерной функции f(x,y) представляет собой производную второго порядка. Цифровая аппроксимация Лапласиана с учетом рис. 8 может быть представлена в виде:

d²f = 4*z₅ - (z₂ + z₄ + z₆ + z₈)        (6)

      Однако очень часто Лапласиан применяется вместе со сглаживающей Гауссовой функцией. Аппроксимирующая маска для получения свертки изображения с Лапласианом гауссиана (ЛГ) приведена на рис. 11:

0	0	-1	0	0
0	-1	-2	-1	0
-1	-2	16	-2	-1
0	-1	-2	-1	0
0	0	-1	0	0

Рисунок 11 - Маска Лапласиан гауссиана

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

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

        Локальный процессинг

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

      Все точки, являющиеся сходными в соответствии с некоторыми заранее заданными критериями, связываются и образуют контур, состоящий из пикселей, отвечающих этим критериям. При таком анализе используются следующие два основных параметра для установления сходства пикселей контура: 1) величина отклика оператора градиента; 2) направление вектора градиента.

      Величина отклика оператора градиента задается значением Gradient, определяемым согласно выражению (5). Таким образом, пиксель контура, имеющий координаты (x₀,у₀) и расположенный внутри заданной окрестности точки (х,у), считается сходным по модулю градиента с пикселем (х,у), если:

      |Gradient(x,у) - Gradient(x₀,у₀)| <= E        (7)

      где Е — заданный неотрицательный градиентный порог.

      Направление вектора градиента задается выражением angle(x,y) = arctan(G_y / G_x). Пиксель контура с координатами (x₀,у₀), расположенный внутри заданной окрестности точки (х,у), считается сходным по направлению градиента с пикселем (х,у), если

      |angle(x,y) - angle(x₀,у₀)| < A        (8)

      где A — заданный неотрицательный угловой порог.

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

        Глобальный процессинг с применением техники графов

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

      Pяд базовых определений. Граф С = (N, U) представляет собой непустое конечное множество вершин N вместе с множеством U неупорядоченных пар различных элементов из N. Каждая пара (n_i, n_j) в U называется ребром. Граф, содержащий только ориентированные (направленные) ребра, называют ориентированным. Если дуга направлена от вершины n_i к вершине n_j, то вершина n_i, называется начальной вершиной дуги (родителем), а n_j — конечной вершиной дуги (потомком). Процесс выявления потомков некоторой вершины называют ее расширением. В каждом графе выделим единственную вершину, которую будем называть начальной, и множество вершин, называемых целевыми вершинами.

Рисунок 12 - Участок контура между точками P и Q

      Kаждой дуге (n_i, n_j) приписана некоторая стоимость (сost) c(n_i, n_j). Последовательность вершин n₁, n₂, ..., n_k, в которой каждая вершина n_i является потомком вершины n_i-1, называется путем от n₁ до n_k. Стоимость всего пути равна:

      C = SUM[c(n_i-1, n_i)],       i=2,..., k        (9)

      Oпределим участок контура как границу между двумя точками p и q, являющимися соседями по 4-ех связности (рис. 12). Элементы контура идентифицируются xy-координатами точек р и q. Kонтур есть последовательность соединенных друг с другом участков контура. Каждому элементу контура, заданному пикселями р и q, припишем стоимость, которую определим как:

      c(p,q) = H-[f(p)-f(q)]        (10)

      где Н — максимальный уровень яркости в изображении, f(p) и f(q) представляют собой значения яркости пикселей р и q соответственно. По соглашению, точка p находится справа от направления обхода элемента контура.

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

3. Пороговая сегментация

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

      Пусть показанная на рис. 13 гистограмма соответствует некоторому изображению f(x, у), содержащему светлые объекты на темном фоне, так что яркости пикселей объекта и фона сосредоточены вблизи двух преобладающих значений. Очевидный способ выделения объектов из окружающего фона состоит в выборе значения порога Т, разграничивающего моды распределения яркостей. Тогда любая точка (х, у), в которой f(х, у) > Т, называется точкой объекта, а в противном случае — точкой фона.

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

Рисунок 13 - Гистограмма изображения

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

      Для автоматического выбора значения порога Т может применяться следующий алгоритм:

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

2. Проводится сегментация изображения с помощью порога Т. В результате образуются две группы пикселей: G₁, состоящая из пикселей с яркостью больше Т, и G₂, состоящая из пикселей с яркостью меньше или равной Т.

3. Вычисляются значения h₁ и h₂ средних яркостей пикселей по областям G₁ и G₂ соответственно.

4. Вычисляется новое значение порога: T = 0.5 * (h₁ + h₂)

5. Повторяются шаги со 2-го по 4-й до тех пор, пока разница значений Т при соседних итерациях не окажется меньше значения наперед заданного параметра T₀.

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

4. Сегментация, основанная на областях

      В этом случае сегментация представляет собой операцию разбиения конечного множества плоскости R, на которой определена функция исходного изображения f(x,y), на n непустых связанных подмножеств R_i (i=[1,n]) в соответствии с некоторым логическим предикатом P, определяемом на множестве всех точек из R={R₁,R₂,…,R_k} и принимающим истинные значения, когда все пары точек из каждого подмножества R_i удовлетворяет некоторому критерию однородности (например, критерий однородности, основанный на оценке максимальной разности яркости отдельного пикселя и среднего значения яркости, вычисленного по соответствующей области):

• P(R_i) = TRUE, i = 1,... n       (11)
• P(R_i U R_j) = FALSE, i<>j       (12)

        Наращивание областей

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

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

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

        Разбиение и слияние областей

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

      Пусть вся область изображения обозначена R, и выбран предикат Р. Один из подходов к сегментации R состоит в том, чтобы последовательно разбивать ее на все более и более мелкие квадратные области Rj, пока для каждой из них не будет выполняться условие P(Rj) = TRUE. Работа начинается со всей области изображения. Если P(R) = FALSE, изображение делится на четверти вертикальной и горизонтальной прямыми, проходящими через середину. Если для какой-то четверти предикат Р принимает значение FALSE, она аналогичным способом делится на более мелкие четверти, и так далее, см. рис.14:

R1	R2
R3	R41	R42
	R43	R44

Рисунок 14 - Разбиение изображения на области

      Если использовать только операцию разделения, то в окончательном разбиении изображения могут присутствовать соседние области с одинаковыми свойствами. Этот недостаток можно устранить, применяя наряду с разделением также операцию слияния. Для соблюдения ограничений требуется, чтобы слиянию подвергались только соседние области, пиксели которых в совокупности удовлетворяют предикату Р. Иначе говоря, две соседних области Rj и Rk сливаются только в том случае, если P(Rj U Rk) = TRUE.

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

1. Любая область Ri, для которой P(Ri) = FALSE, разделяется на четыре непересекающиеся четверти.

2. Любые две соседние области Rj и Rk, для которых P(Rj U Rk) = TRUE, объединяются в одну.

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

5. Сегментация на основе морфологического водораздела

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

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

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

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