На правах рукописи

Николаев Дмитрий Петрович

Алгоритмы цветовой сегментации, применимые в условиях

сложного освещения сцены

Специальность 05.13.18 – математическое моделирование,

численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата

физико-математических наук

МОСКВА, 2004 г.

Работа выполнена в Институте проблем передачи информации РАН

Научный руководитель: доктор физико-математических наук, профессор Чуличков Алексей Иванович Консультант: доктор биологических наук, профессор Рожкова Галина Ивановна

Официальные оппоненты: доктор физико-математических наук, профессор Голубцов Пётр Викторович кандидат физико-математических наук Юрин Дмитрий Владимирович

Ведущая организация: Институт системного анализа РАН

Защита состоится «_» _ 2004 года в _ часов на заседании диссертационного совета К 501.001.17 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992 ГСП-2, г. Москва, Воробьёвы горы, дом 1, строение 2.

С диссертацией можно ознакомиться в библиотеке физического факультета МГУ.

Автореферат разослан «_» _ 2004 года.

Учёный секретарь диссертационного совета К 501.001.17, д.ф.-м.н, профессор П.А. Поляков  

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Хотя уже давно понятно, что алгоритмы цветовой сегментации можно развивать, только ориентируясь на физическую модель сцены (с ее ограничениями и приближениями), число таких алгоритмов, тем более реализованных программно, исчисляется единицами (Николаев, 1988; Klinker et al., 1990; Gevers and Smeulders, 1999). В то же время потребность в устойчиво работающих алгоритмах цветовой сегментации велика. Таким образом, актуальность создания новых методов и алгоритмов обработки цветного изображения (основывающихся на физическом подходе) вполне очевидна.

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

В работе решались следующие научные задачи:

1. Физическое обоснование линейной модели формирования цветного изображения и определение пределов её применимости.

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

3. Создание математической и алгоритмической базы для решения задачи цветовой сегментации в пределах применимости линейной модели.

4. Создание библиотеки алгоритмов автоматической и полуавтоматической объектной сегментации цветных изображений трёхмерных сцен со сложным освещением для использования прикладными программами обработки и сжатия изображений.

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

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

Достоверность также подтверждается численным экспериментом.

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

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

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

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

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

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

Практическая ценность и реализация результатов работы Разработанные схемы и алгоритмы сегментации могут применяться для обработки видеопоследовательностей изображений с целью их анализа, редактирования и сжатия. В дополнение к этому они могут быть использованы для обработки статических изображений, таких как фотографии, журнальные страницы и документы. Отдельные варианты предлагаемых алгоритмов цветовой сегментации были внедрены в качестве части программного обеспечения Института перспективных технологий Самсунг (SAIT, Южная Корея) в рамках проекта по реализации стандарта MPEG-4 и поданы на патентование. На базе предложенных алгоритмов разработан фильтр бинаризации изображений цветных документов, вошедший в ядро сканирования и распознавания печатных и рукопечатных документов “Scanify” компании Cognitive Technologies, Ltd (Россия).

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

2. Адекватность линейной модели формирования изображения может быть проверена с помощью теории надежности статистических гипотез.

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

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

Апробация работы Основные результаты диссертации докладывались на международных “Интеллектуальные САПР” (IEEE AIS и CAD) (пос. Дивноморское, Россия, сентябрь 2002, сентябрь 2003 и сентябрь 2004), на международном симпозиуме “25 European conference on Visual Perception” (г. Глазго, Великобритания, август 2002), на международном семинаре “6 German-Russian Workshop on Pattern Recognition and Image Understanding” (OGRW-6-2003) (пос. Катунь, Россия, август 2003), а также неоднократно обсуждались на семинарах лаборатории обработки сенсорной информации Института проблем передачи информации РАН, на семинарах отдела когнитивных и компьютерных технологий Института системного анализа РАН и мультимедийной лаборатории Института перспективных технологий Самсунг (SAIT, Южная Корея).

Публикации, личный вклад автора По материалам диссертации опубликовано 12 научных работ, из них 2 – тезисы докладов, 2 – патентные публикации.

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

Структура и объём диссертации Диссертация состоит из введения, трех частей: литературного обзора (глава I), теоретической части (глава II), алгоритмической и экспериментальной части (главы III, IV и V) и заключения. Работа изложена на 125 страницах, включающих 22 рисунка и список литературы из 120 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

В главе I приведен обзор экспериментальных и теоретических работ, относящихся к проблеме цветовой сегментации. В конце главы ставится задача настоящего исследования.

В разделе I.1. приводятся основные понятия цветовой теории, такие как пространство спектрального распределения, цветовые пространства (ЦП), цветовые координаты и гистограммы цветового распределения, и рассматривается возможность перехода к квазиинвариантным цветовым координатам как способа избежать анализа многомерных цветовых распределений. В разделе I.2. рассматриваются наиболее часто используемые на основывающиеся, как правило, на некоторых локальных свойствах самого изображения и не использующие информацию о процессах, лежащих в основе взаимодействия света с объектами сцены, – процессов, которые собственно и формируют изображение. Анализируются причины неудовлетворительности конечных результатов работы существующих алгоритмов и отмечается ценность некоторых из них как сервисных алгоритмов обработки изображения (в том числе и для разработанных в данной работе схем сегментации). В разделе I.3. кратко описаны физические явления, лежащие в основе формирования изображения, и линейная модель формирования спектрального стимула, положенная в основу настоящего подхода к проблеме цветовой сегментации.

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

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

В разделе II.1. кратко приводятся определения морфологического анализа и вводится общая модель изображения. Изображение определяется как векторфункция c (r ), заданная на некотором поле зрения – подмножестве плоскости, заданная в виде:

где – число изображённых объектов, (r ) – индикаторная функция i -го объекта, а c (r ) – его цветовое распределение. Индикаторные функции При этом функции цветового распределения c (r ) считаются задачи.

Раздел II.2. посвящён определению класса цветовых распределений, возникающих при регистрации изображений различных сцен. В этом разделе строится более общая, чем в других работах (Николаев, 1988; Klinker et al., 1990; Brill, 1990), модель формирования спектрального стимула, что позволяет распространить её на более широкий круг реальных сцен. Обобщенная линейная модель основывается на трёх допущениях. Первое – адекватность спектральную яркость источников света в сцене в виде произведения спектрального и геометрического сомножителей. Третье – возможность представить спектральную двухлучевую функцию отражательной способности (ДФОС) поверхности объектов сцены в виде произведения спектрального и геометрического сомножителей или суммы таких произведений. На основе анализа известных экспериментальных данных демонстрируется адекватность этих допущений.

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

со спектральной яркостью излучения B (, r, n ) = S ( ) B (n ) (r r ) (здесь r – координаты i -го источника) освещают плоскость с СДФОС Сенсор со спектральной чувствительностью датчиков ( ) регистрирует в точке светочувствительной матрицы некоторый спектральный стимул F ( ), преобразуя его в вектор-стимул, соответствующий данному элементу изображения.

Здесь – интегральная мощность излучения в диапазоне длин волн (, + ), излучаемая площадкой источника из точки r внутри телесного угла в направлении, заданном вектором n ; n – нормаль к площадке. В большинстве случаев распределение спектральной яркости может быть переписано в виде:

Здесь B (r, n – интегральная яркость излучения, а S ( ) – относительное спектральное распределение излучения (Рис. 1).

отражательные свойства тел, образующих сцену, можно охарактеризовать спектральной ДФОС (СДФОС) f (, r, n, n ), задающей отношение спектральной яркости поверхности к её освещённости в диапазоне длин волн (, + d ) в каждой точке r поверхности тела при освещении в направлении n и наблюдении в направлении n в системе координат, связанной с элементарной площадкой поверхности в точке r (Рис. 1). При рассмотренных ограничениях ДФОС представима в виде суммы следующего вида:

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

При этих условиях, спектральный стимул F (, r ) от сцены, содержащей различными СДФОС, с учетом интеррефлексов может быть записан в следующем виде:

где S ( ) – относительное спектральное распределение излучения i -того коэффициента отражения в разложении СДФОС n -ной поверхности, а g (r ) – геометрический фактор для луча света от i -того Геометрические факторы зависят от мощности источника света, интегральных ДФОС поверхностей и взаимного расположения источников, объектов и сенсора в сцене.

Ранг объекта на изображении определяется через рассмотрение совокупности спектральных функций L, элементами которой являются разности между спектральными стимулами от каждой точки объекта и спектрального стимула от произвольной фиксированной точки объекта r : L = {F (, r ) F (, r )}. Пусть ранг L в линейном пространстве относительных спектральных функций равен n, тогда (2) можно переписать в виде:

где {M ( )} – ортонормированный базис L, а M ( ) ортогональна этому базису. Таким образом, спектральный стимул F ( ) от каждой точки объекта является элементом линейного подмногообразия размерности n пространства спектральных функций. Эта размерность и называется рангом данного объекта.

Ранг объекта зависит и от типа его поверхности, и от условий его освещения и наблюдения.

светочувствительной матрицы из спектрального стимула F ( ) в т.н. цветовой вектор-стимул c (x, y ):

где ( ) – вектор спектральных чувствительностей сенсора (трёхмерный в случае RGB-камеры или, в определённых условиях, глаза человека). Таким образом, сенсор проецирует вектор-стимул из пространства функций в конечномерное ЦП, сохраняя линейные свойства распределения для случаев рангов меньших размерности ЦП. Из (4) также следует, что на формирование изображения не влияют спектральные особенности стимула F (, r ) в тех областях спектра, где все компоненты вектора ( ) близки к нулю. Таким образом, все требования линейной теории, сформулированные выше, должны выполняться только в видимой для сенсора части спектра.

Для изображений, удовлетворяющих линейной модели, класс функций цветового распределения c (r ) представления (1) можно записать в явном виде:

изображения трёхмерной статичной сцены при сложных условиях освещения.

Форма (5) является конусом в пространстве изображений, а задача цветовой объектной сегментации заключается в построении проекции на этот конус.

На рис. 2 показано, как выглядят уединённые кластеры цветовых распределений реальных сцен.

Рис. 2. Примеры цветовых гистограмм реальных изображений в RGBпространстве. а) Объект ранга 1 (клубок синей шерсти при дневном освещении).

б), в) Проекции кластера ранга 1 в ЦП. г) Объект ранга 2 (глянцевый красный цилиндр при освещении лампой накаливания). д), е) Проекции кластера ранга в ЦП.

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

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

Метод наименьших квадратов решает задачу аппроксимации формы одного сегмента оптимально в квадратичной метрике при наличии нормального шума:

метод ОПХ решает ту же задачу, оптимизируя другой функционал, что (выбросовому) шуму:

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

где G ( p ) = ( ), p – угловые координаты подмногообразия, а p – его пространственные координаты. При этом dim(p ) = k (n k ), Кроме того, в разделе предложена простая быстрая схема суммирования для преобразования Хафа ( O (n log n ) операций для Н ), не использующая преобразование Фурье. В массиве с линейными размерами n n = [(x + shift / 2, y + 2 ), (x + shift, y + 2 1)] что и обеспечивает (при порядке суммирования по deg от 0 до D-1) увеличение быстродействия за счёт отсутствия повторного суммирования для фрагментов дискретного представления прямых, входящих в несколько сумм.

В главе III описан алгоритм быстрого выделения маски объекта на цветном изображении сцены со сложными условиями освещения под частичным контролем пользователя. Алгоритм позволяет определять искомую однородно окрашенную область по указанному малому участку области.

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

Кластер ранга 1 задаётся уравнением прямой в канонической форме.

Параметры модели – координаты точки g c, через которую проходит эта прямая, и вектора c, задающего ее направление ( c = 1 c = моделью равен:

Собственно алгоритм состоит в следующем:

1. Методом обобщённого преобразования Хафа найти приближение параметров модели {g, c, c } для начального сегмента S, заданного на входе. Задать, как среднюю невязку по области S.

2. Построить карту невязок (x, y ), которая представляет собой массив расхождений между моделью с параметрами {g, c, c } и пикселями исходного изображения c (x, y ) (для первой итерации = ).   Результат заливки – новое приближение рассматриваемой области, S. Если S покрывает все изображение, перейти к (7).

“качества границы”. Здесь – средняя невязка среди пикселей, входящих в S,а – средняя невязка среди пограничных с S пикселей.

области S.

следующего i.

удовлетворяющего условию (G G < G + ), пометить S в качестве кандидата на искомое выделение.

В результате работы данного алгоритма определяется несколько гипотез о границах объекта. Пользователь выбирает из них искомый. Пример работы алгоритма выделения объекта приведен на Рис. 3.

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

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

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

В разделе IV.1. описывается алгоритм предварительной сегментации, позволяющий существенно сократить время обработки изображения основным алгоритмом. Задача предварительной сегментации – разделить изображение на области площадью хотя бы в несколько пикселей так, чтобы истинные границы объектов не пересекали этих областей. В работе используется обобщённый на случай цветных изображений алгоритм поиска водоразделов (ранее он применялся только для случая монохромных изображений). Основная посылка алгоритма поиска водоразделов состоит в том, что каждый сегмент должен содержать точно один минимум значения некоторого детектора границ, и градиентный спуск от любого пикселя сегмента по карте детектора границ должен приводить к этому минимуму. Это условие реализуется проведением градиентного спуска из каждой точки изображения и группированием точек по их принадлежности к минимумам. В результате границы сегментов (групп пикселей) проходят вдоль «хребтов» значений детектора краев. Поскольку классический оператор градиента может быть применен только для скалярного, но не для векторного поля, в цветовой версии алгоритма используется векторный аналог градиента (т.н. цветовой градиент). Его модуль записывается следующим образом:

Здесь C (x, x – цветовые компоненты изображения в линейном ЦП, n – размерность ЦП (для RGB-пространства – 3), а – модуль цветового градиента (максимум модуля изменения вектора C по всем направлениям).

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

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

где I – единичный оператор, P – проектор на подпространство изображений изображений c (r ) = c (r ), c c, а P – на подпространство пустых изображений.

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

где d [k,l ] – вес ребра, связывающего узлы, соответствующие сегментам и, j – ранг модельного распределения, ( p ) – отклонение пикселей p от Собственно алгоритм включает следующие этапы:

1. Применение техники слияния областей с весовой функцией d¦[k,l ] и порогом, соответствующим по порядку уровню шума на изображении.

2. Маркирование изолированных сегментов ранга 0, то есть тех, для которых минимальное d для всех прилегающих рёбер сильно больше порога:

3. Применение техники слияния областей с весовой функцией d [k, l ]и  порогом, с исключением из рассмотрения рёбер, ведущих к изолированным сегментам.

4. Применение техники слияния областей с весовой функцией d [k, l ] и  порогом, с исключением из рассмотрения рёбер, соединяющих два изолированных сегмента.

5. Дополнительное маркирование изолированных сегментов ранга 1 с порогом.

6. Применение техники слияния областей с весовой функцией d [k,l ] и порогом, с исключением из рассмотрения рёбер, ведущих к изолированным сегментам.

7. Применение техники слияния областей с весовой функцией d [k,l ] и порогом, с исключением из рассмотрения рёбер, соединяющих два изолированных сегмента.

В работе показано, что подобная схема при правильно выбранных порогах и позволяет получить верную сегментацию, не решая задачу определения ранга конкретного сегмента изображения. Идея состоит в том, что слияние с весовой функцией ранга i не разрушает границ зоны ранга j, если i < j. Таким образом, ранние этапы обработки не вносят искажений в работу более поздних (Рис. 4). Однако, этого недостаточно. Через любые две точки можно провести прямую, через любую точку и прямую – плоскость. Таким образом, на более поздних этапах обработки мы имеем шанс разрушить правильно построенные участки сегментационной карты. Чтобы этого не произошло, на этапах 2 и 5 происходит изоляция сегментов, которые могут оказаться верно найденными зонами объектов младших рангов. С другой стороны, такие сегменты могут быть порождены условиями освещения.

Например: тень, отброшенная на матовый объект, освещённый двумя источниками, – изолированный сегмент ранга 1. Но теневые сегменты имеют отличительный признак: это сегменты, соседствующие с сегментом более высокого ранга, объединение с которым не повышает ранг этого последнего.

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

Рис. 4. Пример сегментации линейным методом. а) Исходное изображение. б) Результат предварительной сегментации. в), г), д) Промежуточные этапы сегментации (после шагов 2, 4, и 6 алгоритма, соответственно). Границы с весом, большим, помечены чёрным. е) Окончательный результат.

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

Рис. 5. Примеры сечения цветовой гистограммы плоскостями L = (R + G + B ) 3 = const. а) Исходная гистограмма. б) – е) Сечения Предлагаемый алгоритм состоит из этапа разбиения цветового пространства на слои семейством плоскостей, нормальных к главной диагонали цветового пространства, послойной кластеризации с помощью алгоритма поиска водоразделов, сборки кластеров и обратного проецирования на плоскость изображения с целью получения карты сегментации. Такой алгоритм показывает хорошие результаты при обработке сцен с малым количеством объектов, так как в каждом слое сечение кластера хорошо локализовано на поверхности сечения (Рис. 5). Однако, на сложных изображениях при использовании приведенного выше алгоритма не исключена вероятность ошибок сегментации, если два объекта, не имеющие общей границы, порождают в цветовом пространстве перекрывающиеся распределения. Для таких изображений предложена версия алгоритма, учитывающая геометрическое соседство точек. В ней используется разбиение изображения на небольшие, плотно покрывающие изображение, прямоугольные области, каждая из которых сегментируется независимо. При этом при сегментации текущей области анализируется цветовое распределение, взятое по большей области. При этом объект, далёкий от текущей области, уже не зашумляет её локальное цветовое распределение, а близкие объекты вносят существенный вклад, даже если их вклад по площади в сегментируемую область мал.

Рис. 6. Пример сегментации изображения, полученного с некалиброванного сенсора. а) Исходное изображение. б) Две проекции цветового распределения исходного изображения. Цифрой 1 помечен кластер, соответствующий на изображении шару, 2 – цилиндру. в) Результат сегментации с разбиением на зоны. г) результат сегментации после слияния областей.

Для устранения границ между «областями внимания» в алгоритме используется процедура слияния областей с помощью ГСО. В качестве меры несходства d при этом взята следующая функция:

средние значения -той цветовой компоненты по соответствующим сегментам.

Результат применения этого варианта алгоритма приведен на рис. 6.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В диссертации предложена информационная технология анализа цветных изображений сцен со сложным освещением. Для реализации этой технологии:

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

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

2. На основе теории надежности статистических гипотез разработаны формирования изображения.

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

4. Предложены новые алгоритмы обработки изображений, в частности:

алгоритм пресегментации методом водоразделов на цветном изображении, алгоритм кластеризации цветовой гистограммы путём сегментации двумерных сечений и быстрый безартефактный алгоритм преобразования Хафа.

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Николаев П.П., Николаев Д.П. Модели константного зрительного восприятия. III. Спектральные и перцептивные инварианты в процедурах зрительной обработки // Сенсорные системы. 1997. Т. 11. N 2. С. 181-204.

2. Kim S.K., Nikolayev D.P. Method and apparatus for sectioning image into plurality of regions // US patent application publication. Application No.

09/983032. Publication No. US 2002/0102017 A1. 2002. 25 p.

3. Nikolaev D.P., Nikolayev P.P. Linear color segmentation and its implementation // Computer Vision and Image Understanding. 2004. V. (Special issue on colour for image indexing and retrieval). P. 115-139.

4. Kim S.G., Nikolayev D.P. Method and device for classifying areas of image // Korean patent abstracts. Application No. 1020000069490. Publication No.

1020020039721. KIPO. 2002. 1 p.

5. Николаев Д.П., Николаев П.П. Быстрый алгоритм выделения объектов, основанный на линейной модели формирования спектрального стимула // Искусственные интеллектуальные системы и Интеллектуальные САПР. Труды международной конференции IEEE AIS'02 и CAD-2002.

М.: Изд-во Физико-математической литературы. 2002. С. 410-416.

6. Николаев Д.П., Божкова В.П., Николаев П.П. Кластеризация в цветовом пространстве как метод сегментации изображения, полученного с нелинейного сенсора // Искусственные интеллектуальные системы и Интеллектуальные САПР. Труды международной конференции IEEE AIS'03 и CAD-2003. М.: Изд-во Физико-математической литературы.

2003. С. 314-321.

7. Николаев Д.П., Николаев П.П. Гауссовская спектральная модель и её особенности в задаче цветовой константности // Искусственные международной конференции IEEE AIS'03 и CAD-2003. М.: Изд-во Физико-математической литературы. 2003. С. 321-327.

8. Nikolaev D.P. Segmentation-based binarization method for color document images // Pattern recognition and image understanding. Proceedings of German-Russian Workshop (OGRW-6). Novosibirsk 2003. P. 190-193.

9. Николаев П.П., Николаев Д.П. Сравнительный анализ гауссовской и Искусственные интеллектуальные системы и Интеллектуальные САПР.

Труды международной конференции IEEE AIS'04 и CAD-2004. М.: Издво Физматлит. 2004. Т. 2. С. 323-328.

10. Карпенко С.М., Николаев Д.П., Николаев П.П., Постников В.В. Быстрое преобразование Хафа с управляемой робастностью // Искусственные международной конференции IEEE AIS'04 и CAD-2004. М.: Изд-во Физматлит. 2004. Т. 2. С. 303-309.

11. Nikolaev D.P., Bozhkova V.P., Nikolayev P.P. Linear color segmentation and its implementation // Perception. 2002. V. 31 (Supplement). P. 67-68.

12. Nikolaev D.P., Nikolayev P.P. Estimation of reflectance properties following color segmentation (Colour constancy model using colour segmentation data) // Perception. 2002. V. 31 (Supplement). P. 138.