СПОСОБ АВТОМАТИЧЕСКОЙ СЕГМЕНТАЦИИ ПОЛУТОНОВОГО ИЗОБРАЖЕНИЯ ПО ФОРМЕ ЯРКОСТНОЙ ГИСТОГРАММЫ Российский патент 2000 года по МПК G06K9/00 

Изобретение относится к способам цифровой обработки изображений.

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

Известен способ сегментации изображения, называемый наращиванием областей (см., например, Якушенков Ю.Г. Техническое зрение роботов. - М.: Машиностроение, 1990, - с. 49-51; Путятин Е.П., Аверин С.И. Обработка изображений в робототехнике. - М.: Машиностроение, 1990, с. 18-25). Суть его заключается в том, что соседние элементы изображения с одинаковыми или близкими уровнями яркости группируют, объединяя в однородные области. Для этого на исходном изображении ищут элементарные области, где пикселы объединяются в группы, если они обладают одинаковым уровнем яркости и являются соседями в смысле четырехсвязности. Затем элементарные области, имеющие общие границы, сливаются воедино согласно различным эвристическим правилам. Недостатком этого способа является необходимость подбора яркостных порогов в интерактивном режиме.

Еще известен способ сегментации, основанный на выделении контурных линий, образуемых из видимых участков границ объектов и фона, сложных поверхностей одного и того же объекта (см., например, Якушенков Ю.Г. Техническое зрение роботов. - М.: Машиностроение, 1990, - с. 51-60; Путятин Е.П., Аверин С. И. Обработка изображений в робототехнике. - М.: Машиностроение, 1990, с. 34-41). Суть его заключается в определении значений яркостных переходов и последующем сравнении их с назначенным порогом. Яркостные переходы, превышающие порог, принимаются за границы исходных сегментов. При этом используются известные методы численного дифференцирования функций двух переменных на дискретной решетке. Недостатками этого способа являются его низкие помехоустойчивость и эффективность при недостаточной контрастности изображения, а также проблема назначения порога.

Известен также способ сегментации изображения, основанный на принципе порогового ограничения по яркости (см., например, Путятин Е.П., Аверин С.И. Обработка изображений в робототехнике. - М.: Машиностроение, 1990, с. 12-18). Он заключается в том, что на изображении выделяют сегменты, имеющие достаточно однородную яркость. Пороговые значения яркости, определяющие диапазоны изменения значений яркости для отдельных сегментов изображения, как правило, назначаются на основе априорной информации о содержании изображения. При отсутствии априорной информации существует подход к определению порогов, связанный с нахождением экстремумов гистограммы распределения яркости. Для этого на гистограмме находят глобальный и локальный максимумы, а затем располагаемую между ними точку минимума гистограммы. Отыскание глобального максимума обычно не вызывает затруднений. Локальные максимумы на реальной гистограмме отыскать значительно сложнее из-за большого количества ложных экстремумов. Эта задача решается на основе использования априорной информации об окрестности точки глобального максимума. Задача нахождения минимума обычно решается путем аппроксимации части гистограммы аналитической функцией и отысканием математическими методами ее минимума на заданном отрезке.

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

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

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

Изобретение поясняется чертежом. Способ автоматической сегментации полутонового изображения по форме яркостной гистограммы. Определение точки (порога I_n) разделения яркостной бимодальной гистограммы полутонового изображения на два унимодальных фрагмента.

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

Шаг 1. Начальная установка всех элементов управляющей бинарной маски в единицу.

Шаг 2. Формирование яркостной гистограммы исходного изображения.

Шаг З. Определение вида яркостной гистограммы: унимодальная или бимодальная.

Шаг 4. Если гистограмма унимодальная, то переход к шагу 8.

Шаг 5. Определение уровня яркости I_n, обладающего свойством разделения исходной бимодальной гистограммы на два унимодальных фрагмента.

Шаг 6. Модификация управляющей бинарной маски посредством операции порогового среза (по уровню I_n) исходного изображения.

Шаг 7. Удаление шума из управляющей бинарной маски.

Шаг 8. Конец.

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

Автоматическое принятие решений (шаги 3 и 5) базируется на эффективных эвристических приемах, имитирующих особенности зрительного восприятия человеком яркостных гистограмм.

Сначала аппроксимируется исходная гистограмма, имеющая ступенчатый характер. Это позволяет исключить значительное количество ложных экстремумов и получить сглаженную оценку распределения вероятностей уровней яркости в обрабатываемом изображении. Исследования, проведенные авторами предлагаемого изобретения, показали, что наилучшее приближение (минимальное число и амплитуда выбросов, малые вычислительная погрешность и общий объем вычислений) дает аппроксимация методом наименьших квадратов, где в качестве базисных функций используются ортогональные многочлены дискретной переменной Хана-Чебышева (Мудров А.Е. Численные методы для ПЭВМ на языках Бейсик, Фортран и Паскаль. - Томск: МП "Раско", 1991, - с. 122-128). Степень итогового полинома выбирается не более 16, аппроксимация осуществляется в яркостном интервале i = [i_min, i_max], где i_min, i_max - соответственно минимальное и максимальное значения яркости.

Для реализации процессов автоматического принятия решений о наличии и месте расположения на яркостной гистограмме сегментируемого изображения значимых модальностей, а также о месте разбиения исходной бимодальной гистограммы на два унимодальных фрагмента, введем понятие центра гистограммного фрагмента (ЦГФ). Таковым является центр тяжести фигуры, ограниченной осью абсцисс гистограммы (0,i), аппроксимирующим полиномом p(i) и линиями i=i₁, i=i₂ (значения i₁ < i₂ определяют яркостной интервал фрагмента). Как известно, центр тяжести (x_ц, y_ц) плоской фигуры, заданной в прямоугольной системе координат (x, 0, y) линиями y = f₁(x), y = f₂(x), x=x₁, x = x₂, определяется следующим образом (Пискунов Н.С. Дифференциальное и интегральное исчисления. - М.: Наука, 1968, - с. 414-416):


Тогда дискретный вариант для ЦГФ будет иметь вид:


Определим правила формирования кривой динамики центра гистограммы (КДЦГ) - d(i).

Правило α1 (движение слева): для всех фрагментов, где i₁ = i_min, i₂= [i_min, i_max], по формулам (3) и (4) вычисляются соответствующие ЦГФ.

Правило α2 (движение справа): для всех фрагментов, где i₂ = i_max, i₁= [i_min, i_max], по формулам (3) и (4) вычисляются соответствующие ЦГФ.

Правило α3 (объединение): точки ЦГФ, полученные по правилам α1 и α2, соединяются ломаной (кусочно-линейная интерполяция).

Построенная таким образом кривая (КДЦГ) позволяет автоматизировать процессы принятия решений о числе значимых модальностей и месте разбиения бимодальной гистограммы на два унимодальных фрагмента. С психофизической точки зрения, поведение КДЦГ отражает особенности визуального взвешивания и кластеризации внешнего вида гистограммы человеком. Участки гистограммы, претендующие на роль областей разделения значимых модальностей, всегда идентифицируются взаимным расположением аппроксимирующего полинома p(i) и кривой d(i). А именно, для таких областей справедливо:
p(i) ≥ d(i) (5)
Однако выполнение условия (5), особенно на участках, близких к i_max и i_min, может быть связано с наличием модальностей, имеющих малый относительный вес в гистограмме. Такие модальности при визуальном анализе интерпретируются как шум. Кроме того, даже при отсутствии шума соблюдение условия (5) не гарантирует принятия правильного решения. Поэтому данное условие дополнено критерием порогового типа (назначение порога обязательно, т.к. речь идет о выборе на дискретном множестве альтернатив), обладающим следующими свойствами. Во-первых, он максимальным образом учитывает особенности человеческих суждений при визуальной кластеризации, и при этом сводится к простым аналитическим выражениям. Во-вторых, надежное использование назначаемого постоянного порога требует значительного относительного удаления аналитически формируемых кластеров друг от друга. Указанными свойствами обладает площадь фигуры, образуемой кривыми d(i) p(i) на каждом участке гистограммы, где выполняется (5). Действительно, данная площадь растет: 1) при увеличении вытянутости по оси ординат модальностей, располагающихся по обе стороны предполагаемой области разделения; 2) при выравнивании относительных весов в гистограмме этих модальностей; 3) при увеличении яркостного интервала области разделения. А это именно те основные признаки, на основании которых принимаются решения при визуальном анализе. Предлагаемый критерий назовем весом области разделения (ВОР), он вычисляется достаточно просто:

где s - номер области разделения;
[i_s, i_s ^*] - яркостной интервал области разделения, т.е. интервал, где для всех i справедливо (5);
V_s - вес s-й области разделения.

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

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

Шаг 1. Аппроксимация исходной гистограммы многочленами дискретной переменной Хана-Чебышева. Степень итогового полинома p(i) равна 16, аппроксимация осуществляется в яркостном интервале [i_min, i_max].

Шаг 2. Построение КДЦГ d(i) в соответствии с описанными ранее правилами α1,α2,α3.
Шаг 3. Определение яркостных интервалов [i_s, i_s ^*], для которых p(i)≤d(i). Если таковые отсутствуют, то принимается решение об унимодальности гистограммы и переход к шагу 7.

Шаг 4. Вычисление ВОР V_s для каждого интервала [i_s, i_s ^*] по формуле (6).

Шаг 5. Идентификация яркостного интервала S_max, соответствующего области разделения с максимальным весом:

Шаг 6. Если V_Smax > V_n, то принимается решение о бимодальности гистограммы, иначе - о ее унимодальности.

Шаг 7. Конец.

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

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

Сложности алгоритмизации процесса удаления шума из управляющей бинарной маски связаны с нестабильностью размеров и формы шумовых пятен. В связи с этим были приняты следующие ограничения для яркостной организации маски: площадь сегмента больше площади любого шумового пятна на поле другого сегмента. Под площадью здесь понимается количество пиксел, составляющих восьмисвязную однородную по яркости область. Данное ограничение отражает специфику разделения значимых гистограммных модальностей и позволяет полностью формализовать процесс удаления шума. Предлагаемый алгоритм базируется на классических методах разметки точек (см., например, Путятин Е.П. Обработка изображений в робототехнике. - М.: Машиностроение, 1990, - с. 43-51) и рассчитан на два последовательных сканирования обрабатываемого растра (G_ij), где G_ij - значение точки растра (0 или 1 в исходной маске), , m - число строк, n - число точек в строке.

Шаг 1. Установка в начало растра (i = 1, j = 1).

Шаг 2. Просмотр очередной точки G_ij. Переход к шагу 5 по окончании сканирования всего растра.

Шаг 3. Если точка уже размечена (G_ij ≠ 0, G_ij ≠ 1); переход к шагу 2.

Шаг 4. Осуществляется разметка восьмисвязной однородной области (например, методом рекурсивного автовызова, широко применяемым в машинной графике), включающей точку G_ij. Элементы области, ранее имевшие нулевые или единичные (в зависимости от G_ij) значения, получают новую уникальную индексированную метку T_r, где r - "родительский" индекс, равный G_ij, a T_r не может быть равной 0 или 1. Одновременно подсчитывается площадь области - W_Tr. Переход к шагу 2.

Шаг 5. Установка в начало растра (i = 1, j = 1). Для каждого "родительского" индекса определяются области с максимальными площадями, т.е. T_0max и T_1max , для которых:

Шаг 6. Просмотр очередной точки G_ij. Переход к шагу 8 по окончании сканирования всего растра.

Шаг 7. Если точка G_ij имеет метку T_0max или T₁ ≠ T_1max , то ей присваивается нулевое значение, иначе - единичное. Переход к шагу 6.

Шаг 8. Конец.

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

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

Апробирование этого способа показало его высокую эффективность при обработке телевизионных изображений объектов на естественных фонах.

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

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