СПОСОБ СЕГМЕНТАЦИИ СЛОЖНОСТРУКТУРИРОВАННЫХ РАСТРОВЫХ ПОЛУТОНОВЫХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ СОСТАВНЫХ МОРФОЛОГИЧЕСКИХ ОПЕРАТОРОВ
METHOD FOR SEGMENTATION OF COMPLEX-STRUCTURE HALF-TONE IMAGES BASED ON COMPOSITE MORPHOLOGIC OPERATORS

Предлагаемое изобретение относится к области цифровой обработки изображений. Сегментация, то есть выделение однородных областей на исходном цифровом изображении, является одной из наиболее важных задач в системах машинного зрения, которые применяются во многих научно-технических и производственных отраслях: медицине, металлографии, аэрофотосъемке, робототехнике, дефектоскопии, системах безопасности и охраны правопорядка и других.
Реальные растровые изображения, получаемые с ПЗС-матриц видеокамер, могут содержать затененные и засвеченные участки. На одном и том же изображении могут встречаться светлые объекты на темном фоне и, наоборот, темные объекты на светлом фоне с различной степенью затененности. В результате получается сложноструктурируемое изображение, разбиение которого на сегменты является неоднозначной задачей. В этом случае для повышения качества сегментации необходимо использовать технологии выделения сегментов, основанные на моделировании процессов сегментации, реализующихся в зрительном анализаторе человека.
На сегодня известно множество различных методов сегментации, среди которых можно выделить методы, использующие информацию о связности областей: выращивание областей, объединение областей по заданному правилу, разделение и слияние областей, сегментация по морфологическим водоразделам, приложения методов теории графов.
Метод выращивания областей в простейшей его реализации [Гонсалес Р.С. Цифровая обработка изображений [Текст] / Р.С.Гонсалес, Р.Э.Вудс. - М.: Техносфера, 2005. - 1072 с. - ISBN 5-94836-028-8. - С.875] можно описать так:
- на исходном изображении выбираются точки (центры кристаллизации), предположительно принадлежащие выделяемым областям, например, это могут быть точки с максимальным уровнем яркости;
- далее из этих точек начинается рост областей, то есть присоединение к уже имеющимся точкам области соседних, при этом используется определенный критерий их близости, например разница в яркости, заданная некоторой пороговой величиной;
- остановка роста областей по какому-либо условию, например максимальному отклонению яркости новых точек области от уровня яркости центра кристаллизации или максимальной площади сегментов.
Недостатком данного способа является то, что пиксели одного и того же сегмента могут иметь уровни яркости, разность которых превосходит априорно заданную, а на других фрагментах этого же изображения может быть противоположная ситуация, когда пиксели разных сегментов будут идентифицироваться как пиксели одного и того же сегмента, так как их разности уровней яркости не превосходят априорно заданную.
Другим способом, близким к предыдущему, является алгоритм слияния областей [Baatz, М. Multiresolution Segmentation: an optimization approach for high quality multi-scale image segmentation [Text] / M.Baatz, A.Schape. - Journal of Photogrammetry and Remote Sensing. Volume 58. Issue 3-4. - Herbert Wichmann Verlag, 2004, р.239-258]. В его основу заложена идея о том, что пиксели исходного изображения уже по сути являются гомогенными областями, но при этом обладают равно минимальными размерами. В этом случае способ сегментации должен выполнять объединение соседних областей, наиболее близких по какому-либо параметру (например, по цвету или текстуре), определенному на основе анализа расстояния (гетерогенности, функцией стоимости слияния), до тех пор, пока не будет выполнено (либо нарушено) некоторое заданное условие (например, на размер сегментов или их количество). Для данного алгоритма целиком отпадает проблема определения центров кристаллизации, но особенно актуальной становится проблема определения момента завершения процесса слияний. В указанной реализации, как и во многих других, для этого используется ограничение на размер и количество сегментов, которое сильно снижает гибкость метода.
7
При проведении выращивания и слияний областей часто используется текстурная информация [Pat. US2009080773 (A1), IPC G06K 9/34. Image segmentation using dynamic color gradient threshold, texture, and multimodal-merging [Text] / Shaw M. [US]; Bhaskar R. [US]; Ugarriza L.G. [US]; Saber E. [US]; Amuso V. [US]]. Однако использование текстурной информации при выращивании ограничивается тем, что для анализа текстуры (обычно это вычисление различных признаков, описанных в математической статистике), как правило, уже требуется иметь область размером более одного пикселя, что при выращивании (добавление единственного пикселя к области) невозможно.
Близким к заявленному является способ сегментации [Pat. WO 2009143651 (A1), IPC G06T 5/00. Fast image segmentation using region merging with a k-nearest neighbor graph [Text] / Mantao X. [CN], Qiyong G. [CN], Hongzhi L. [CN], Jiwu Z. [CN]], принципиально состоящий из двух этапов: выращивания и последующего слияния сегментов. Выращивание областей в данном случае используется для выполнения начальной заведомо избыточной сегментации (initial oversegmentation), а слияние областей, основанное на методах теории графов, имеет своей целью достижение окончательного оптимального состояния сегментации. Определение центров кристаллизации в данном методе происходит в автоматическом режиме на основе градиентного изображения, полученного из исходного с помощью масочного оператора Кирша (Kirsch). Использование здесь градиентного изображения позволяет достаточно универсально решить проблему автоматического обнаружения центров кристаллизации, так как минимумам функции градиентного изображения будут соответствовать точки с максимально однородной окрестностью (потенциальные центры роста сегментов). Однако недостатком применения оператора Кирша в данной ситуации является его пространственная ограниченность (анализируется окрестность только 3×3 пикселей), тогда как при поиске центров кристаллизации было бы полезным исследовать окрестность точки на больших масштабах, чтобы учесть низкочастотные изменения функции яркости изображения и, таким образом, провести более точное последующее определение центров роста. Данного недостатка лишен подход [Минченков М.В. Алгоритм автоматической сегментации растровых изображений, основанный на росте кластеров от максимумов R-величины [Электронный ресурс] / М.В.Минченков. - Материалы конференции Graphicon 2004. - Режим доступа:  /2004/ Proceedings /Technical_ru/sl[2].pdf. - с.2], основанный на релеевском детекторе границ площадных объектов, который использует области анализа различных размеров.
Общим недостатком всех указанных способов является жесткое правило для завершения процесса слияний, основанное на количестве сегментов на изображении либо их размерах. Такое условие резко снижает универсальность метода при заданной конфигурации.
Выделение контуров объектов на полутоновых растровых изображениях можно осуществлять совместно с выделением самих объектов. Для этого обычно используют пороговые методы сегментации на основе среднего значения яркости пикселей, например [патент РФ №2325044 «Градиентный способ выделения контуров объектов на матрице полутонового растрового изображения»] предложен градиентный способ выделения контуров объектов на матрице полутонового растрового изображения, заключающийся в том, что для всех пикселей растрового изображения вычисляют норму или квадрат нормы градиента изменения их яркости, затем на новой черно-белой монохромной матрице черным цветом на белом фоне выделяют все элементы, у которых значение нормы или квадрата нормы градиента больше порогового значения, а в качестве контуров объектов на монохромной матрице принимают связные конфигурации элементов черного цвета, для выбранного способа вычисления градиента экспериментально определяют коэффициент, затем рассчитывают пороговое значение квадрата нормы градиента как произведение данного коэффициента на сумму квадратов средних величин модулей изменения яркости соседних пикселей по строкам и столбцам, у которых значения превышают общие средние уровни ненулевых изменений соответственно по строкам и столбцам, а среди связных конфигураций элементов черного цвета на монохромной матрице сразу отбрасывают конфигурации, у которых число входящих элементов менее 5-7 элементов, для оставшихся конфигураций вычисляют среднюю степень соседства - частное от деления суммы по всем элементам конфигурации соседних с ним элементов на сумму элементов в конфигурации, причем те конфигурации, у которых средняя степень соседства менее 3, отбрасывают, а оставшиеся принимают в качестве искомых контуров объектов.
К недостаткам данного способа можно отнести слишком большое число эмпирически настраиваемых параметров, что не позволяет получить решающие правила, пригодные для изображений одного и того же класса, полученных при различных условиях или при различных уровнях помех. При нечетких сегментах такие параметры подобрать практически невозможно.
Наиболее близким к заявленному является способ обработки изображения по патенту США N 5351305, опубликованному 27.09.94, МКИ G06К 9/40, в котором из исходного изображения путем частотной фильтрации получают множество изображений, фильтрованных по направлению. Выходное изображение формируют путем выборки каждого элемента изображения либо из одного из фильтрованных по направлению изображений, либо из исходного изображения в зависимости от наличия или отсутствия контрастной границы, соседней с выбранным (обрабатываемым) элементом исходного изображения. При этом наличие контрастной границы для выбранного элемента изображения определяют путем вычисления собственного вектора и сравнения его длины с предопределенным пороговым значением. При отсутствии границы соответствующий элемент выходного изображения принимается равным соответствующему элементу входного изображения. При наличии границы соответствующий элемент выходного изображения принимают равным соответствующему элементу того фильтрованного по направлению изображения, в котором направление фильтрации наиболее близко определенному направлению границы.
В описанном выше способе обработки изображения при определении границы изображения возможен случай, когда длина собственного вектора для соседних элементов изображения изменяется вблизи порогового значения. В этом случае может произойти избирательное усиление шума, вызванное выборкой соседних элементов изображения из разных изображений (исходного и фильтрованного по направлению), что приводит к ухудшению качества выходного изображения.
Кроме того, исходные изображения с различным уровнем шума требуют существенно различных пороговых значений, в то время как данный способ не предусматривает адаптивного изменения этого порогового значения, что приводит к невозможности качественной обработки изображений с различным уровнем шума.
Выборку элементов выходного изображения при наличии границы производят только из одного из фильтрованных по направлению изображений, что приводит к полному подавлению всех деталей исходного изображения, которые отличаются по направлению от обнаруженной границы, даже в случае, когда эти детали хорошо видны в исходном изображении.
Технической задачей предлагаемого способа является повышение точности выделения границ сегментов сложноструктурируемых изображений и, как следствие, повышение качества сегментации (большее соответствие восприятию изображения человеком), а также повышение степени автоматизации процесса анализа и классификации сегментов изображения.
р
Поставленная задача достигается тем, что из исходного полутонового изображения путем локальной обработки составным морфологическим оператором формируют множество изображений, фильтрованных по направлению. Выходное изображение образуется из фильтрованных изображений, получаемых в результате обработки исходного изображения составным морфологическим оператором. При этом составной морфологический оператор формируют из линейных структурообразующих элементов равной длины V, но с различными параметрами ориентации  относительно растра изображения. Каждое фильтрованное изображение получают посредством взаимодействия линейного структурообразующего элемента составного морфологического оператора с исходным изображением F. Яркости пикселей в фильтрованном изображении получают следующим образом. При помещении центра линейного структурообразующего элемента в пиксель р с координатами ij исходного изображения F линейный структурообразующий элемент В(θ) выделяет из множества пикселей изображения F три подмножества:
<mrow><mi>A</mi><mn>1</mn><mo>=</mo><mi>F</mi><mo>∩</mo><msub><mi>B</mi><mi>p</mi></msub><mrow><mo>(</mo><mi>θ</mi><mo>)</mo></mrow></mrow>
1)
;
<mrow><mi>A</mi><mn>2</mn><mo>=</mo><mi>F</mi><mo>∩</mo><mover accent="true"><mrow><mo stretchy="false">(</mo><msub><mi>B</mi><mi>p</mi></msub></mrow><mo stretchy="true">¯</mo></mover><mo>\</mo><mo stretchy="false">(</mo><mi>A</mi><mn>1</mn><mo>∪</mo><mo stretchy="false">(</mo><mi>F</mi><mo>∩</mo><mo>{</mo><mover accent="true"><mrow><msubsup><mi>b</mi><mi>p</mi><mrow><mi>q</mi><mi>x</mi></mrow></msubsup></mrow><mo stretchy="true">¯</mo></mover><mo>}</mo><mo stretchy="false">)</mo><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow>
2)
;
<mrow><mi>A</mi><mn>3</mn><mo>=</mo><mi>F</mi><mo>∩</mo><mo stretchy="false">(</mo><mover accent="true"><mrow><msub><mi>B</mi><mi>p</mi></msub></mrow><mo stretchy="true">¯</mo></mover><mo>\</mo><mo stretchy="false">(</mo><mi>A</mi><mn>1</mn><mo>∪</mo><mo stretchy="false">(</mo><mi>F</mi><mo>∩</mo><mo>{</mo><mover accent="true"><mrow><msubsup><mi>b</mi><mi>p</mi><mrow><mi>l</mi><mi>k</mi></mrow></msubsup></mrow><mo stretchy="true">¯</mo></mover><mo>}</mo><mo stretchy="false">)</mo><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow>
3)
,
где V>q,s>1; s<q; V>l,k>1; k>l.
lk
lk
qs
qs
После определения трех подмножеств вычисляют суммарное значение яркости пикселей в подмножествах A1:S1 и А2:S2. Затем вычисляют разность D=S1-S2. Новое значение яркости пикселей определяют по рекуррентным формулам, в множестве А2: ƒ=ƒ+D и в множестве A3: ƒ=ƒ-D.
После того, как маска составного морфологического оператора пройдет все пиксели исходного изображения F, то есть после определения фильтрованных изображений для всех линейных структурообразующих элементов составного морфологического оператора, определяют итоговое изображение G путем суммирования яркостей пикселей фильтрованных изображений с одинаковыми координатами, определяют минимальную яркость пикселя итогового изображения Gmin и максимальную яркость итогового изображения Gmax и смещают и нормируют его согласно формуле
<mrow><msub><mi>g</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo>=</mo><mrow><mo>(</mo><mrow><msub><mi>g</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo>−</mo><mi>G</mi><mi>min</mi></mrow><mo>)</mo></mrow><mfrac><mrow><mi>G</mi><mi>max</mi><mo>−</mo><mi>G</mi><mi>min</mi></mrow><mrow><mn>255</mn></mrow></mfrac></mrow>
.
На фиг.1 представлена схема алгоритма, реализующего представленный способ.
На фиг.2 представлено продолжение схемы алгоритма, реализующего представленный способ.
На фиг.3 представлен пример линейного структурообразующего элемента составного морфологического оператора В(θ, V) при θ=1, V=3, ξ=3.
На фиг.4 показан пример обработки бинарного изображения составным морфологическим оператором, представленным на фиг.3 согласно схеме алгоритма, представленного на фиг.1 и фиг.2.
На фиг.5 показан пример обработки бинарного изображения составным морфологическим оператором, представленным на фиг.3 согласно схеме алгоритма, представленного на фиг.1 и фиг.2.
На фиг.6 показан пример обработки изображений, представленных на фиг.4, посредством детектора Превитта.
<mrow><mover accent="true"><mi>B</mi><mo stretchy="true">¯</mo></mover></mrow>
Способ осуществляется согласно схеме алгоритма, представленной на фиг.1 и фиг.2. В блоке 1 осуществляется ввод в компьютер пикселей исходного растрового полутонового изображения F, размер которого по вертикали N, а по горизонтали М. В блоке 2 формируется составной морфологический оператор
, включающий ξ линейных структурообразующих элементов длиной V. Блок 3 организует цикл по структурообразующим элементам составного морфологического оператора. В результате этого цикла получаем ξ фильтрованных по направлению изображений.
На фиг.3 представлен пример формирования составного морфологического оператора. На ней выделен единицами один структурообразующий элемент составного морфологического оператора, соответствующей направлению фильтрации θ=1 для V=3 и ξ=3.
р
Для каждого значения θ в блоках 4-19 определяется изображение F(θ), фильтрованное по направлению θ. Сущность фильтрации по направлению состоит в следующем. При помещении центра линейного структурообразующего элемента в пиксель р с координатами ij исходного изображения F линейный структурообразующий элемент В(θ) выделяет из множества пикселей F три подмножества:
<mrow><mi>A</mi><mn>1</mn><mo>=</mo><mi>F</mi><mo>∩</mo><msub><mi>B</mi><mi>p</mi></msub><mrow><mo>(</mo><mi>θ</mi><mo>)</mo></mrow></mrow>
1)
;
<mrow><mi>A</mi><mn>2</mn><mo>=</mo><mi>F</mi><mo>∩</mo><mover accent="true"><mrow><mo stretchy="false">(</mo><msub><mi>B</mi><mi>p</mi></msub></mrow><mo stretchy="true">¯</mo></mover><mo>\</mo><mo stretchy="false">(</mo><mi>A</mi><mn>1</mn><mo>∪</mo><mo stretchy="false">(</mo><mi>F</mi><mo>∩</mo><mo>{</mo><mover accent="true"><mrow><msubsup><mi>b</mi><mi>p</mi><mrow><mi>q</mi><mi>x</mi></mrow></msubsup></mrow><mo stretchy="true">¯</mo></mover><mo>}</mo><mo stretchy="false">)</mo><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow>
2)
;
<mrow><mi>A</mi><mn>3</mn><mo>=</mo><mi>F</mi><mo>∩</mo><mo stretchy="false">(</mo><mover accent="true"><mrow><msub><mi>B</mi><mi>p</mi></msub></mrow><mo stretchy="true">¯</mo></mover><mo>\</mo><mo stretchy="false">(</mo><mi>A</mi><mn>1</mn><mo>∪</mo><mo stretchy="false">(</mo><mi>F</mi><mo>∩</mo><mo>{</mo><mover accent="true"><mrow><msubsup><mi>b</mi><mi>p</mi><mrow><mi>l</mi><mi>k</mi></mrow></msubsup></mrow><mo stretchy="true">¯</mo></mover><mo>}</mo><mo stretchy="false">)</mo><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow>
3)
,
где V>q,s>1; s<q; V>l,k>1; k>l.
Каждый составной морфологический оператор дает триаду множеств А1, А2 и A3 для каждого значения параметра θ и пикселя р. Подмножество A1 - это подмножество элементов множества F, которые лежат на структурообразующем элементе В(θ). Подмножество А2 - это подмножество элементов множества F, которые лежат выше или левее структурообразующего элемента В(θ). Подмножество A3 - это подмножество элементов множества F, которые лежат ниже или правее структурообразующего элемента В(θ). Полагаем, что существует вероятность, что каждый структурообразующий элемент составного морфологического оператора является элементом границы сегмента. Тогда средние яркости пикселей по обе стороны границы сегмента должны отличаться друг от друга. Сравнение этих яркостей может подтвердить или опровергнуть выдвинутую гипотезу. Элементы изображения F, которые находятся по обеим сторонам границы сегмента, определяют подмножества А2 и A3.
р
В блоках 6-9 определяется сумма S1 яркостей пикселей подмножества А2 для линейного стрктурообразующего элемента В(θ). При этом параметры циклов k и l в блоках 7 и 8 принимают в зависимости от параметра θ для пикселя с координатами ij следующие значения:
0
Θ: k=i-int(V/2),…i-1; l=j-int(V/2),…j-int(V/2)+V-1;
1
Θ: k=i-int(V/2),…i+int(V/2)-1; l=j-int(V/2),…j+int(V/2)+V-1-k;
2
Θ: k=i-int(V/2),…i+int(V/2); l=j-int(V/2),…j-1;
3
Θ: k=i-int(V/2)-1,…i+int(V/2); l=k-1,…j+int(V/2)-1.
р
В блоках 10-12 определяется сумма S2 яркостей пикселей множества A3 для линейного стрктурообразующего элемента В(θ). При этом параметры циклов s и q в блоках 10 и 11 принимают в зависимости от параметра θ для пикселя с координатами ij следующие значения:
0
Θ: s=i-1,…i+int(V/2); q=j-int(V/2),…j-int(V/2)+V-1;
1
Θ: s=i-int(V/2),…i+int(V/2)-1; q=j+int(V/2)-k-1,…j-int(V/2)+V-2;
2
Θ: s=i-int(V/2),…i+int(V/2); q=j+1,…j+int(V/2);
3
Θ: s=i-int(V/2),…i+int(V/2); q=j-int(V/2)-1,…k-1.
В блоке 13 вычисляется параметр D=S1-S2, который определяет, насколько значимо различие яркости пикселей множества А2 и множества A3. Для накопления этой значимости к яркости пикселей множества А2 добавляют параметр D, а из яркости пикселей множества A3 вычитают параметр D. Эти процедуры реализуется в блоках 14-16 и 17-19 соответственно.
В блоках 20-26 определяют выходное изображение G. Для этого суммируют яркости в пикселях с одноименными координатами в полученных фильтрованных изображениях (блоки 20-23). Определяют максимальный Gmax и минимальный Gmin элементы полученного изображения и затем смещают и нормируют его согласно формуле
<mrow><msub><mi>g</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo>=</mo><mrow><mo>(</mo><mrow><msub><mi>g</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo>−</mo><mi>G</mi><mi>min</mi></mrow><mo>)</mo></mrow><mfrac><mrow><mi>G</mi><mi>max</mi><mo>−</mo><mi>G</mi><mi>min</mi></mrow><mrow><mn>255</mn></mrow></mfrac></mrow>
.
Процесс обработки тестовых изображений предлагаемым способом иллюстрируют фиг.4-6. На фиг.4а показано тестовое бинарное изображение, имеющее четкую границу сегментов, со спектром, лежащим в области нижних пространственных частот. На фиг.4б показано это изображение после обработки составным морфологическим оператором, реализованным согласно алгоритму фиг.1 и фиг.2 и со структурообразующими элементами, показанными на фиг.3.
На фиг.5а показано тестовое бинарное изображение, имеющее четкую границу сегментов, со спектром, лежащим в области верхних пространственных частот. На фиг.5б показано это изображение после обработки составным морфологическим оператором, реализованным согласно алгоритму фиг.1 и фиг.2 и со структурообразующими элементами, показанными на фиг.3.
Проведем на экспертном уровне сравнительную оценку эффективности выделения краев предложенным составным морфологическим оператором и оператором, основанным на детекторе краев Превитта. На фиг.6а показано изображение (фиг.4а), полученное после обработки его детектором краев Превитта, а на фиг.6б показано изображение (фиг.5а), полученное после обработки его детектором краев Превитта.
Тестовое изображение фиг.4а относится к изображениям, спектр которых лежит в области нижних пространственных частот. Тестовое изображение фиг.5а относится к изображениям, спектр которых лежит в области верхних пространственных частот. Таким образом, мы можем получить сравнительные характеристики обработки изображений с различными пространственными спектрами.
При экспертном оценивании качества сегментации учитывался динамический диапазон между средней яркостью пикселей исходного изображения (фоном) и средней яркостью пикселей на действительной границе сегмента в обработанных изображениях. При этом полагалось, что чем больше этот динамический диапазон, тем устойчивее процесс сегментации к влиянию помех.
Анализ экспериментальных результатов по обработке тестовых изображений посредством предложенного морфологического оператора показал, что границы сегментов имеют вид «мексиканская шляпа» независимо от пространственных частот, которые занимает изображение, что значительно повышает динамический диапазон на границах сегмента и тем самым увеличивает помехозащищенность процесса сегментации.