Сегментация локально однородных сцен

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

В 5.1 исследуется метода пятна для сегментации зон интереса локально однородных сцен. В 5.2 предлагается модификация метода квантилей. Наконец, в 5.3 представлены результаты экспериментальных исследований ряда известных методов для сегментации зон интереса скалярных локально однородных сцен различной сложности.

5.1 Метод пятна

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

, .

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

Теорема 5.1.1. Если - зона интереса для светлого пятна на локально однородной сцене, то для любого фиксированного

1 при .

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

.

А теперь вновь вернемся к сценам, полученным скользящим суммированием по квадратной окрестности с радиусом . Пусть - квадрат на такой сцене и пусть , . Очевидно, что подобные квадраты не содержат объектов. Пусть - подмножество из , со­стоящее из таких точек , окрестности которых содержатся в . То есть, = . Справедливо следующее утверждение.

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

0 при .

Из теорем 5.1.1 и 5.1.2 следует простой способ сегментации зон интереса на сценах, полученных скользящим суммированием. В самом деле, если - зона интереса объекта , то вначале по проекции требуется определить значение . Затем выбрать на границе зоны интереса фрагментов , , таким образом, чтобы = и . Заметим, что в случае модельных сцен, практически всегда для получения нужного значения , можно воспользоваться вместо границы ее расширением до нужной величины. Далее по изображению границы (или ее расширения) вычисляются , , и для каждого вычисляется . Если , , то принимается решение о том, что пиксель принадлежит объекту . В противном случае – фону .

Определим на множестве изображений сцены признак вида

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

.

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

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

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

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

= .

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

Для иллюстрации возможностей предлагаемого метода сегментации воспользуемся фрагментом бернуллиевской сцены с проекцией в форме квадрата и стороной равной 255 масштабным единицам. Фрагмент состоит из пяти объектов. Проекции четырех объектов являются прямоугольниками со сторонами равными 39 и 29 масштабным единицам и площадью в 1200 пикселей. Остальные пиксели образуют пятый объект, который по традиции будет называться фоном. Дисперсия каждого пикселя сцены равняется 225. Пиксели имеют нормальные распределения. Координаты левого верхнего пикселя объекта, его ориентация, среднее значение и величина отношения сигнал/шум приведены в таблице 5.1. Исходное изображение фрагмента сцены и результаты сег­ментации в графической форме без удаления граничных пикселей приве­дены на рисунках 5.1-5.3.

В первом эксперименте применялось сглаживание с радиусом , во втором – с . Так как , то в обоих экспериментах используется

Рисунок 5.1 - Изображение исходного фрагмента беруллиевской сцены	Рисунок 5.2 – Сегментация методом пятна без удаления граничных пикселей ()	Рисунок 5.3 – Сегментация методом пятна без удаления граничных пикселей ()

Таблица 5.1 - Свойства бернуллиевской сцены

	Номера объектов сцены
0 (фон)
	-	(30, 30)	(180, 30)	(180, 180)	(30, 180)
Ориентация	-	горизонт.	вертик.	горизонт.	вертик.
	-	0.5		1.5

расширение границы. В первом случае оно состоит из 270 пикселей, во втором – из 750. Хорошо видно, что с увеличением радиуса сглаживания

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

Таблица 5.2 - Сегментация скалярным методом пятна с уда­лением

граничных пикселей бернуллиевских сцен

Параметры сегментации	Номера объектов
	0.5	1.0	1.5	2.0
	0.210	0.061	0.037	0.009
	0.108	0.051	0.016	0.014

А теперь рассмотрим результаты экспериментов с фрагментом локально однородной сцены, полученной скользящим суммированием по окрестности с . Зависимость между пикселями описывается корреляционной функцией (она одна и та же для объекта и фона), приведенной в таблице 2.2. Исходное изображение фрагмента и результаты сегментации (с удалением граничных пикселей) в графической форме представлены на рисунках 5.7-5.9. Оценки вероятностей ошибок сегментации для =1 и 2 после удаления граничных пикселей содержатся в таблице 5.3. По условиям эксперимента значения отношения сигнал/шум были одними и теми же для сцен обоих типов. Однако результаты сегментации на локально однородных сценах оказались заметно хуже. Заметим, что в ходе коррекции результатов сегментации сведения о площади объекта не использовались.

Рисунок 5.4 - Изображение исходного фрагмента бернуллиевской сцены	Рисунок 5.5 – Сегментация методом пятна с удалением граничных пикселей ()	Рисунок 5.6 – Сегментация методом пятна с удалением граничных пикселей ()

Рисунок 5.7 - Изображение исходного фрагмента локально однородной сцены	Рисунок 5.8 – сегментация методом пятна с удалением граничных пикселей ()	Рисунок 5.9 - сегментация методом пятна с удалением граничных пикселей ()

Таблица 5.3 - Сегментация скалярным методом пятна с удалением

граничных пикселей локально однородных сцен

Параметры сегментации	Номера объектов
	0.5	1.0	1.5	2.0
	0.440	0.187	0.057	0.031
	0.415	0.128	0.081	0.040

5.2 Метод квантилей

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

=1 (соответственно =1).

(5.3.1)

Из этого предположения следует существование значения регистрируемого признака, удовлетворяющего неравенству

(соответсвенно ), , .

Очевидно, что решающее правило вида

,

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

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

,

и выбрать в качестве = .

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

= .

Из него следует, что является решением уравнения

= = ,

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

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

Таблица 6.5 - Сегментация скалярным методом квантилей бернуллиевских

и локально однородных сцен

Параметры сцены	Номера объектов
	0.5	1.0	1.5	2.0
	0.306	0.146	0.078	0.020
	0.315	0.162	0.060	0.014
	0.308	0.159	0.067	0.023

В третьей строке указано отношение сигнал/шум, в четвертой и пятой - результаты сегментации для бернуллиевской сцены и сцены, полученной скользящим суммированием с , соответственно. В последней строке приведены значения байесовских вероятностей ошибок для случая равенства априорных вероятностей, появления пикселя объекта и фона. Следует обратить внимание на высокое сходство теоретических и экспериментальных результатов. Разница между ними и относительными частотами не превышает 0.013. Как и следовало ожидать, с улучшением качества изображения, описываемого значением отношения сигнал/шум, результат сегментации заметно улучшается. В графической форме результаты сегментации методом квантилей представлены на рисунках 5.16-5.17. Как и раньше, пиксели объекта обозначены максимальной яркостью, а пиксели фона - минимальной.

При решении прикладных задач довольно часто приходится иметь

Рисунок 5.16 - Сегментация бернуллиевской сцены скалярным методом квантилей	Рисунок 5.17 - Сегментация локально однородной сцены скалярным методом квантилей

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

(соответсвенно ), , .

(6.3.2)

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

для которых выполняются условия теоремы Слуцкого. Поэтому, если ок -

рестность точки принадлежит проекции объекта, то

,

будет оценкой среднего значения объекта. Если окрестность принадлежит , то будет оценкой среднего значения фона.

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

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

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

Таблица 5.5 - Сегментация скалярным методом квантилей

со сглаживанием

Параметры сегментации	Номера объектов
	0.5	1.0	1.5	2.0
Бернуллиевская сцена
	0.081	0.025	0.003	0.003
	0.056	0.019	0.003	0.006
Локально однородная сцена
	0.260	0.092	0.026	0.011
	0.228	0.056	0.031	0.020

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

Рисунок 5.18 - Исходное изображение бернуллиевской сцены	Рисунок 5.19 - Сегментация скалярным методом квантилей ()	Рисунок 5.20 – Сегментация скалярным методом квантилей ()

Рисунок 6.21 - Исходное изображение локально однородной сцены	Рисунок 6.22 – Сегментация скалярным методом квантилей ()	Рисунок 6.23 – Сегментация скалярным методом квантилей ()

оказалось ниже, чем в методе пятна. Очевидно, что количество ошибок уменьшается с увеличением отношения сигнал/шум.

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

5.3 Экспериментальное сравнение эффективности некоторых

методов сегментации

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

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

= ,

где , - орты. Далее этот метод будет называться кратко методом градиентов.

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

В качестве исходной информации для проведения экспериментов использовались зоны интереса, проекции которых являются квадратами со стороной, равной 60 пикселям. Левая верхняя вершина зоны интереса находится в начале системы координат. Горизонтальная ось направлена вправо, вертикальная – вниз. Проекция объекта является квадратом со стороной, равной 42 пикселям. Ее левая верхняя вершина имеет координаты (9,9). Остальные пиксели образуют окрестность объекта, которая по давно сложившейся традиции будет называться фоном. Легко видеть, что =1764. Это составляет 0.490 площади всей зоны интереса.

Сложность сцен, отобранных для экспериментов, определяется девятью значениями =0.13, 0.25, 0.50, 0.75, 1.00, 1.25, 1.50, 1.75, 2.00 отношения сигнал/шум. Для каждого значения скользящим суммированием по квадратной окрестности строятся три зоны интереса, соответствующие значениям радиуса сглаживания =0, 1 и 2 или трем значениям радиуса корреляции. Таким образом, общее количество участвующих в экспе­риментах зон интереса равняется 27. Оценки вероятностей ошибок классификации осреднялись по десяти изображениям каждой зоны.

Полученные в ходе экспериментов оценки вероятностей ошибок для методов пятна и квантилей в зависимости от значения отношения сигнал/шум (для сцен различной сложности) представлены на рисунках 5.30-5.32 для =0, 1 и 2 соответственно. На этих же рисунках приведены кривые вида , построенные методом наименьших квадратов по экспериментальным данным. К сожалению, для указанных значений результаты сегментации методами градиентов и водоразделов оказались значительно

Рисунок 6.30 - Радиус сглаживания =0	Рисунок 6.31 - Радиус сглаживания =1	Рисунок 6.32 - Радиус сглаживания =2

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

Для визуальной оценки исходных данных на рисунке 5.33 приведено по одному изображению 12 зон интереса из 27, участвующих в экспериментах. Они сгруппированны в таблицу из трех строк и четырех столбцов. В верхней строке находятся изображения сцен с =0 (бернуллиеские сцены), во второй и третьей строках - изображения сцен, полученных скользящим суммированием с =1 и =2 соответственно. Для всех изображений первого столбца =0.25, второго - 0.75, третьего - 1.25, а четвертого - 1.75. Как и ожидалось, визуальная заметность объектов в каждой строке увеличивается с ростом , а в каждом столбце снижается с увеличением . Отметим, что с ростом увеличивается и радиус корреляции.

Рисунок 5.33 – Примеры изображений зон интереса

В качестве примера в таблице 5.6 приведены оценки для вероятностей ошибки классификации пикселей, полученные в ходе сегментации 12 зон интереса с рисунка 5.33. Оценки для методов градиентов, водоразделов, квантилей и пятна указаны в столбцах с названиями «г», «в», «к» и «п» соответственно.

Таблица 6.8 – Результаты сегментация

	=0	=1	=2
г	в	к	п	г	в	к	п	г	в	к	п
0.25	0.288	0.473	0.173	0.266	0.282	0.472	0.291	0.452	0.237	0.439	0.322	0.478
0.75	0.279	0.480	0.025	0.019	0.238	0.480	0.103	0.164	0.189	0.471	0.151	0.269
1.25	0.150	0.472	0.010	0.010	0.180	0.388	0.042	0.034	0.149	0.429	0.060	0.086
1.75	0.075	0.258	0.004	0.006	0.105	0.337	0.017	0.020	0.082	0.287	0.026	0.032

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

Рисунок 5.34 – Сегментация методом градиентов	Рисунок 5.35 - Сегментация методом водоразделов
Рисунок 5.36 - Сегментация методом квантилей	Рисунок 5.37 – Сегментации методом пятна

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

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

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