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

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

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

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

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

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

МОСКВА, 2004 г.

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

Научный руководитель:

доктор физико-математических наук, профессор

Чуличков Алексей Иванович

Консультант:

доктор биологических наук, профессор

Рожкова Галина Ивановна

Официальные оппоненты:

доктор физико-математических наук, профессор

Голубцов Пётр Викторович

Ведущая организация:

Защита состоится

кандидат физико-математических наук Юрин Дмитрий Владимирович

Институт системного анализа РАН

2004 года в

¿Г

часов на заседании

диссертационного совета К 501.001.17 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992 ГСП-2, г. Москва, Воробьёвы горы, дом 1, строение

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

Автореферат разослан «_»

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 и поданы на патентование. На базе предложенных алгоритмов разработан фильтр бинаризации изображений цветных документов, вошедший в ядро сканирования и распознавания печатных и рукопечатных документов "Scarify" компании Cognitive Technologies, Ltd (Россия).

Основные результаты и положения, выдвигаемые на защиту

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

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

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

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

Апробация работы

Основные результаты диссертации докладывались на международных конференциях "Искусственные интеллектуальные системы" и "Интеллектуальные САПР" (IEEE AIS и CAD) (пос. Дивноморское, Россия, сентябрь 2002, сентябрь 2003 и сентябрь 2004), на международном симпозиуме "25th European conference on Visual Perception" (г. Глазго, Великобритания, август 2002), на международном семинаре "6th 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 приведен обзор экспериментальных и теоретических работ, относящихся к проблеме цветовой сегментации. В конце главы ставится задача настоящего исследования.

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

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

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

В разделе ИЛ. кратко приводятся определения морфологического анализа и вводится общая модель изображения. Изображение определяется как вектор-функция заданная на некотором поле зрения - подмножестве

плоскости заданная в виде:

где N - число изображённых объектов, - индикаторная функция 1-го

объекта, - его цветовое распределение,

определяются следующим образом: поле зрение О разбито на области А, С. О соответствующие изображениям отдельных объектов

принадлежащими некоторому классу функций С, определяемому из специфики задачи.

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

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

При этом функции цветового распределения

считаются

Рис 1. Схема формирования изображения сцены. Точечные источники света со спектральной яркостью излучения В^ {X, 7, ) = (Л) • В, (й,) ■ 5(г — ?0() (здесь - координаты ьго источника) освещают плоскость Ф с СДФОС f^= ¿{г ё,) (3Десь ёг - орт вертикальной оси).

Сенсор со спектральной чувствительностью датчиков регистрирует в

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

Здесь - интегральная мощность излучения в диапазоне длин волн (Л,А + ЗЛ), излучаемая площадкой SS источника из точки г внутри телесного угла в направлении, заданном вектором - нормаль к площадке

¿К. В большинстве случаев распределение спектральной яркости может быть переписано в виде:

Здесь - интегральная яркость излучения, а - относительное

спектральное распределение излучения (Рис. 1).

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

спектральной яркости поверхности к её освещённости в диапазоне длин волн в каждой точке поверхности тела при освещении в направлении и наблюдении в направлении в системе координат, связанной с элементарной площадкой поверхности в точке (Рис. 1). При рассмотренных

ограничениях ДФОС иредставима в виде суммы следующего вида:

/А*.?."*■»«, ) = (Д)'/* ('-"т '"ш ).

где [«„[ = 1, ¡Л„„,| = 1, |ф4 (я)(1я = 1,иФ * (Л) - линейно независимы.

Здесь - интегральные ДФОС, Ф4(Л)а- относительные

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

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

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

(*)+ (*)• ф„,

' МЛ

где 5, (X) - относительное спектральное распределение излучения ¡-того источника света; Ф„^ (Я) — Л -тое относительное спектральное распределение коэффициента отражения в разложении СДФОС п-ной поверхности, а £дамежичге.ский) фактор для луча света от ¡-того

источника света, последовательно отраженного от т поверхностей И,,^.....Пт.

Геометрические факторы зависят от мощности источника света, интегральных ДФОС поверхностей и взаимного расположения источников, объектов и сенсора в сцене.

Ранг объекта на изображении определяется через рассмотрение совокупности спектральных функций Ь, элементами которой являются разности между спектральными стимулами от каждой точки объекта и спектрального стимула от произвольной фиксированной точки объекта Ь = {/"(Л,?)—^(Л,^)}. Пусть ранг Ь в линейном пространстве относительных спектральных функций равен п, тогда (2) можно переписать в виде:

Вс-мМЬЫгУмХл), (3)

где {Л/,(Я)} - ортонормированный базис £, а МС(Х) ортогональна этому базису. Таким образом, спектральный стимул от каждой точки объекта

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

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

с{х,у)=)р{^{х,у))-х№Х, (4) о

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

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

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

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

явном виде:

к и

м ы

где Тем самым получено определение формы цветного

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

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

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

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

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

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

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

ИрОО-

л1! V

где (с(у , а Я - ранг линейного подмногообразия. В свою очередь,

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

¿1г = -> тт ,

I'

& тах,

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

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

где &

- угловые координаты подмногообразия, а

- его пространственные координаты. При этом

Кроме того, в разделе предложена простая быстрая схема суммирования для преобразования Хафа (0{п2 Ло%п} операций ДЛЯ не использующая

преобразование Фурье. В массиве с линейными размерами яхи=2°х20 суммирование вдоль прямой, соединяющей точки (Х,у) И (х + ьЫ/1,у + 2'1е8 —1) в

горизонтальную полоску с вертикальным смещением

проводится по рекуррентной формуле

1х+\МА/2[у + 2"1-,](х+*М;Ъу+2,к1 -1)]

(6)

что и обеспечивает (при порядке суммирования по deg от 0 до D-1) увеличение быстродействия за счёт отсутствия повторного суммирования для фрагментов дискретного представления прямых, входящих в несколько сумм.

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

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

прямая, и вектора задающего ее направление

Квадрат невязки рг[х,у) между пикселем изображения с координатами (х,у) и моделью равен:

р2{х,у) = ¡¡с(г,,у)-£0 • с0( ~(с(х,у) с^2 .

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

1. Методом обобщённого преобразования Хафа найти приближение

параметров модели

начального сегмента заданного на

входе. Задать как среднюю невязку по области

2. Построить карту невязок />,(*,}'), которая представляет собой массив расхождений между моделью с параметрами и пикселями исходного изображения с(х,у) (для первой итерации i = 1).

3. Произвести заливку карты р,{х,у) по уровню р,™" ИЗ области 50. Результат заливки - новое приближение рассматриваемой области, покрывает все изображение, перейти к (7).

4. Вычислить среднее отношение невязок б, =/2|сИ//?™ для оценки "качества границы". Здесь Д1"1 - средняя невязка среди пикселей, входящих в

- средняя невязка среди пограничных с пикселей.

5. Методом пристрелки вычислить новые параметры модели {р,»!.^} для области 5,.

6. Увеличить порог заливки и перейти к (2) для следующего г

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

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

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

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

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

Здесь СДл:,,^) - цветовые компоненты изображения в линейном ЦП, п -размерность ЦП (для ЯОВ-пространства - 3), а О - модуль цветового градиента (максимум модуля изменения вектора С, по всем направлениям).

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

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

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

= •«,(?), С1Фс1 против альтернативы с,=с2. Показано, что в этом случае оптимальным является следующий критерий:

где I - единичный оператор, Рв - проектор на подпространство изображений

изображений с(г)=^с(-^(г), (¡¡Фс2, а Р0 - на подпространство пустых изображений.

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

Ыри) ¿рЫ ^ЕмМ-*-+--.

п, пк

где -вес ребра, связывающего узлы, соответствующие сегментам к и 1,

у - ранг модельного распределения, р){р) - отклонение пикселей р от идеальной модели для области, объединяющей сегменты к И I, рк1 - пиксель 1 сегмента к, а пк - кол-во пикселей в сегменте к.

Собственно алгоритм включает следующие этапы:

1. Применение техники СЛИЯНИЯ областей с весовой функцией £/0[£,/] и порогом О",,, соответствующим по порядку уровню шума на изображении.

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

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

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

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

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

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

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

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

Например: тень, отброшенная на матовый ООъект, освещенньт

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

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

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

что каждый однородно окрашенный объект при таком освещении, в безрефлексном приближении проецируется в нелинейное ЦП как точечный кластер или кластер в форме отрезка кривой с преимущественной ориентацией

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

Рис. 5. Примеры сечения цветовой гистограммы плоскостями L = (R + G + B)/3 = const. а) Исходная гистограмма, б) - е) Сечения гистограммы (L = 16, L = 48, L = 80, L = 130, L = 170, соответственно).

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

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

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

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

где - количество пикселей в сравниваемых сегментах, а -

средние значения к -той цветовой компоненты по соответствующим сегментам. Результат применения этого варианта алгоритма приведен на рис. 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 Al. 2002.25 p.

3. Nikolaev D.P., Nikolayev P.P. Linear color segmentation and its implementation // Computer Vision and Image Understanding. 2004. V. 94 (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. M.: Изд-во Физико-математической литературы. 2003. С. 321-327.

8. Nikolaev D.P. Segmentation-based binarization method for color document images // Pattern recognition and image understanding. Proceedings of 6th 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. M.: Изд-во Физматлит. 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.

Подписано в печать 17.11.2004 Формат 60x88 1/16. Объем 1.5 усл.пл.

Тираж 100 экз. Заказ № 189 Отпечатано в ООО «Соцветие красок» 119992 гМосква, Ленинские горы, д. 1 Главное здание МГУ, к. 102

Ht 25 О 20

Введение

Глава I. Обзор современных моделей и методов цветовой сегментации

1.1. Основные понятия цветовой теории

1.2. Цветовая сегментация изображения в зрительной системе человека

1.3. Наиболее распространенные методы сегментации изображения - эвристический подход

1.4. Цветовая сегментация на основе линейной модели формирования спектрального стимула

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

11.1. Цветовая объектная сегментация изображения как 35 задача морфологического анализа

11.2. Линейная модель формирования спектрального стимула и постановка задачи цветовой сегментации в терминах модели

II. 3. Ранговая классификация и редукция цветового пространства

И.4. Численные методы детекции несущих линейных подмногообразий в цветовом пространстве

Глава III. Итерационный алгоритм быстрого выделения объектов

Глава IV. Алгоритм автоматической цветовой сегментации, основанный на линейной модели формирования 78 спектрального стимула

IV. 1. Предварительная сегментация изображения

IV.2. Критерии слияния областей

IV.3. Окончательная сегментация с использованием метода слияния областей

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

V. 1. Типы и ориентация кластеров в нелинейном цветовом пространстве

У.2. Алгоритм сегментации в нелинейном цветовом пространстве для изображений сцен с малым числом объектов

У.З. Алгоритм сегментации с «полем внимания» для изображений произвольных сцен

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

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

Вместе с тем, с учетом природы оптических явлений, порождающих на изображении границы различных типов, и ориентируясь на определенную модель сцены (с ее ограничениями и приближениями), можно развивать алгоритмы сегментации, гарантированно приводящие к правильному результату в случаях, когда изображение следует принятой модели. Примером простейшего метода ЦОС такого рода является алгоритм, позволяющий для изображений однородно окрашенных матовых объектов, имеющих ребра (линии скачка ориентации поверхности и, соответственно, освещенности) и освещенных единственным источником, определить истинные границы окрасок и проигнорировать мнимые границы типа ребер [2, 3]. Чтобы нивелировать перепады мощности спектрального стимула на ребрах, алгоритм использует в каждой точке изображения процедуру деления цветовых компонент, получаемых по разным цветовым каналам (например, по красному и зеленому). В рамках подобного подхода, использующего модель наблюдаемой сцены, цветовая сегментация приобретает "объектный" смысл. И смысл этот связывается со свойствами наблюдаемой сцены, а не со свойствами (пусть и статистически достоверными) самого изображения.

Задача сегментации как задача цветоразличения объектов вне зависимости от условий освещения и регистрации была впервые сформулирована еще в 1975 г. [4], а впоследствии такая трактовка задачи сегментирования изображения стала общепринятой [5-9]. Таким образом,

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

В такой постановке задача ЦОС может быть рассмотрена как задача морфологического анализа изображения [10-13]. Методология морфологического анализа предполагает построение математической модели формирования изображения, построение максимального инварианта изображения относительно всевозможных изменений условий наблюдения. Этот инвариант называется формой изображения. После такой формализации становится возможным строить наилучшие (в некотором смысле) алгоритмы анализа формы изображения, сводя задачу к вариационной. Ранее уже удалось получить такие алгоритмы для сегментации монохромных изображений объектов достаточно простых сцен [14]. Вместе с тем, задача всё ещё не решена для цветных изображений реальных сцен со сложными условиями освещения. Это, в первую очередь, объясняется тем, что физико-математические модели таких сцен достаточно сложны и мало изучены. Цель настоящей работы -в значительной степени заполнить этот пробел.

Рассмотрим подробнее сложности построения формы изображения в задаче ЦОС. Очевидный инвариант цветного изображения - это спектральные отражательные свойства поверхности. Однако, восстановление информации об этих свойствах по изображению -практически невыполнимая задача. К счастью, такое восстановление является необходимым только для задачи идентификации окрасок, но не для задачи ЦОС. Алгоритмы ЦОС должны детектировать скачки параметров отражательных свойств, а не вычислять или оценивать сами значения. Эта задача существенно проще. Теоретическое рассмотрение законов светорассеяния позволило некоторым исследователям построить квазиинвариантные (по отношению к условиям освещения и наблюдения) функции компонент изображения, характеризующие оптические свойства самого объекта [9, 15]. Практическое использование этих цветовых инвариантов затрудняет то обстоятельство, что различным условиям освещения, физическим свойствам поверхностей и условиям регистрации удовлетворяют значительно различающиеся выражения для инвариантов, поскольку они опираются на характеристики сцены и физическую модель формирования спектрального стимула. Например, цветовой тон и нормализованные значения цветовых координат в пространстве 1ЮВ являются постоянными характеристиками однородно окрашенного объекта только в случае освещения сцены белым светом [9]. При цветном освещении нужно искать другие инварианты [4, 15, 17].

Наиболее универсальным в этой связи представляется метод сегментации, который основывается на геометрических особенностях цветовых распределений, выявленных при анализе структуры спектрального стимула в определенных физических моделях. Впервые такая модель была рассмотрена П.П. Николаевым для нескольких типов сцен разной степени сложности и названа "Линейной моделью формирования спектрального стимула" [4, 17] (см. также интерпретацию модели в [8]). В середине 80 гг. близкую модель предложил С. Шефер для случая однородно окрашенной поверхности, освещенной одним точечным источником или двумя (точечным и диффузным) источниками [7, 18, 19]. Модель Шефера, названную "Дихроматической моделью отражения", можно рассматривать как частный случай более общей модели Николаева [8]. В случаях, когда линейная модель адекватна, решить задачу цветоразличения объектов можно посредством кластерного анализа цветового распределения в цветовом пространстве (ЦП) сенсора, регистрирующего изображение. Если сцена содержит объекты определенных типов, то их цветовые распределения представлены или отдельными точками, или прямолинейными отрезками, или совокупностями точек, компактно расположенными в произвольно ориентированных плоскостях. П.П. Николаев и С. Шефер показали, что благодаря этому свойству задача ЦОС корректна и разрешима при некоторых ограничениях на сложность сцены.

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

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

Рис. 21. Результаты сегментации методом кластеризации в нелинейном цветовом пространстве, а) изображение «Башня»; б) результат сегментации изображения «Башня»; в) изображение «Игрушки»; г) результат сегментации изображения «Игрушки»,

У.З. Алгоритм сегментации с «полем внимания» для изображений произвольных сцен

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

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

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

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

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

У.1)

Рис. 22. Результаты сегментации методом кластеризации с полем внимания. Размер поля внимания - 32*32 пикселя, а) изображение «Башня»; б) комбинированный результат сегментации изображения «Башня» по всем полям; в) окончательный результат сегментации изображения «Башня»; г) изображение «Игрушки»; д) комбинированный результат сегментации изображения «Игрушки» по всем полям; е) окончательный результат сегментации изображения «Игрушки».

Заключение

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

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

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

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

Предложенный для обработки видеопоследовательностей комплекс программ ЦОС не является узкоспециализированным. Развитые в нем методы могут быть успешно применены и для решения сегментационных задач в других областях обработки изображения, например, в медицинской диагностике (см. Рис. 10д, 10е) и в задачах автоматизации документооборота. На базе предложенных алгоритмов, в частности, разработан фильтр бинаризации изображений цветных документов, позволяющий сегментировать изображение документов на текст и область фона. Как показало сравнение нашей программы с ранее предложенными, она обеспечивает более высокое качество бинаризации. Работа была представлена на Международной конференции по распознаванию образов и пониманию сцен [120] и вошла в ядро распознавания пакета распознавания печатных и рукопечатных документов "Cognitive Forms" компании Cognitive Technologies (Россия).

1. Gonzalez R., Woods R. Digital image processing. New Jersey: Prentice Hall, 2002. 793 p.

2. Максимов B.B., Николаев П.П. Цветовая оппонентность и константность цветовосприятия // Биофизика. 1974. Т. XIX. Вып. 1. С.151-157.3 . Schowengerdt R., 19 8 3, цит. по 8].

3. Николаев П.П. Некоторые алгоритмы узнавания окраски поверхностей // Моделирование обучения и поведения. М.: Наука, 1975.С. 121-151.

4. Kanade Т. Region segmentation: Signal vs. semantics // Proc. 4th Intern. Joint Conf. Pattern Recog. Kyoto, Japan: IEEE, 1978. P. 95-105.

5. Rubin J., Richards W. Color vision and image intensities: When are changes material // Biological Cybernetics. 1982. V. 45. P. 215-226.

6. Shafer S. Using color to separate reflection components // Color Reserch and Application. 1985. V. 10. P. 210-218.

7. Brill M. Image segmentation by object color: a unifying framework and connection to color constancy it J. Opt. Soc. A. 1990. V. 7. P. 2041-2047.

8. Gevers Т., Smeulders A. Color-based object recognition // Pattern Recognit. 1999. V. 32. P. 453-464.

9. Пытьев Ю.М. Морфологический анализ изображений // Докл. АН СССР, 1983. Т. 269. С. 1061-1064.

10. Пытьев Ю.М., Чуличков А.И. Морфологические методы анализа изображений. 2004. (подготовлено к печати).

11. Pyt'ev Yu.P. The morphology of color (multispectral) images // Pattern Recogn. Image Analysis. 1997. V. 7. P. 467-473.

12. Pyt'ev Yu.P. Methods of morphological analysis of color images // Pattern Recogn. Image Analysis. 1998. V. 8. P. 517-531.

13. Устинин Д.М. Морфологические методы оценивания параметров микрообъектов // Автореферат диссертации на соискание ученой степени кандидата физико-математических наук. МГУ, М.: 2004.

14. Geusebroek J.-M., van den Boomgaard R., Smeulders A. et al. Color invariance // IEEE Trans. Pattern Anal. Mach. Intell. 2001. V. 23. P. 1338-1350.

15. Николаев П.П. Монокулярное цветоразличение объемных предметов в разных условиях освещения // Биофизика. 1988. Т. 33. №1. С. 148-153.

16. Klinker G., Shafer S., Kanade Т. A physical approach to color image understanding // Int. J. Сотр. Vision. 1990. V. 4. P. 7-38.

17. Novak C., Shafer S. Method for estimating scene parameters from color histograms // J. Optic. Soc. America. A. 1994. V. 11, P. 3020-3036.

18. Максимов В.В. Трансформация цвета при изменении освещения. М: Наука, 1984. 160 с.

19. Нюберг Н.Д. Цветовые измерения // Физический энциклопедический словарь. М.: Советская энциклопедия, 1966. Т. 5. С. 387-389.

20. Dartnall Н. J. A., Bowmaker J. К., Mollon J. D. Human visual pigments: microspectrophotometric results from the eyes of seven persons. // Proc. of Royal Soc. of London. 1983. B220. P. 115-130.

21. Forsyth D. A novel algorithm for color constancy // Int. J. Comput. Vision. 1990. V. 5. P. 5-36.

22. Finlayson G. Color in perspective // IEEE Trans. Pattern Analysis Mach. Intel. 1996. V. 18. P. 1034-1038.

23. Haralick K., Kelly G. Pattern recognition with measurement space and spatial clustering for multiple images. // Proc. IEEE. 1969. V. 57. P. 654665. (Русский перевод в журнале "Труды ИИЭР". 1969. Т. 57. № 4).

24. Ohlander R., Price К., Reddy D. Picture segmentation using a recursive region splitting method // Comput. Graphics Image Process. 1978. V. 8. P. 313-333.

25. Huang C., Cheng Т., Chen C. Color image segmentation using scale space filter and Markov random fields // Pattern Recognit. 1992. V. 25. P. 1217-1229.

26. Shafarenko L., Petrou M., Kittler J. Histogram-based segmentation in a perceptually uniform color space // IEEE Trans, on Image Process. 1998. V. 7. P. 1354-1358.

27. Shafer S., Kanade Т., 1982, цит. no Klinker et al„ 1990.

28. Liu J., Yang Y.-H. Multiresolution color image segmentation // IEEE Trans. Pattern Analysis Mach. Intel. 1994. V. 16. №7. P. 689-700.

29. Healey G. Segmenting images using normalized color // IEEE Trans. Systems Man. Cybernet. 1992. V. 22. №1. P. 64-73.

30. Zhu S., Yuille A. Region competition // IEEE Trans. Pattern Analysis Mach. Intel. 1996. V. 18. № 19. P. 880-913.

31. Koch C., Ullman S. Shifts in selective visual attention: towards the underlying neural circuitry // Human Neurobiol. 1985. V. 4. P. 219-227.

32. Moller P., Hurlbert A. Psychophysical evidence for fast region-based segmentation processes in motion and color // Proc. Nat. Acad. Sci. USA. 1996. V. 93. P. 7421-7426.

33. Kohler I. The formation and transformation of the visual world // Contemporary theory and research in visual perception. N.Y: Holt, Rinehart, Winston, 1968. P. 474-497.

34. Moller P., Hurlbert A. Interactions between colour and motion in image segmentation//Curr. Biol. 1997. V. 7. P. 105-111.

35. Leung Т., Malik J. Contour continuity in region based image segmentation // 5th Euro. Conf. Computer Vision. Freiburg, 1998. P. 116.

36. Mumford D., Kosslyn S., Hillger L. et al. Discriminating figure from ground: The role of edge detection and region growing H Proc. Nat. Acad. Sci. USA. 1987. V. 84. P. 7354-7358.

37. Хьюбел Д., Визель Т. Центральные механизмы зрения // Мозг. М.: Мир, 1982. С. 167-198.41. von der Malsburg С. Binding in models of perception and brain function // Curr. Opin. Neurobiol. 1995. V. 5. P. 520-526.

38. Engel S., Zhang X., Wandell B. Colour tuning in human visual cortex measured with functional magnetic resonance imaging // Nature. 1997. V. 388. №6637. P. 68-71.

39. Cannon M., Fullenkamp S. A model for inhibitory lateral interaction effects in perceived contrast // Vision Res. 1996. V. 36. P.l 115-1125.

40. Itti L., Koch Ch., Niebur E. A model of saliency-based visual attention for rapid scene analysis // IEEE Trans. Pattern Analysis Mach. Intel. 1998. V. 20. P. 1254-1259.

41. Андреев В.П., Белов Д.А., Вайнштейн Г.Г. и др. Эксперименты с машинным зрением. М.: Наука, 1987. 127 с.

42. Pal N., Pal S. A review on image segmentation techniques // Pattern Recogn. 1993. V. 26. P. 1277-1294.

43. Nevatia R. A color edge detector and its use in scene segmentation // IEEE Trans. Systems Man. Cybernet. 1977. V. 7. P. 820-826.

44. Robinson G. Color edge detection // Optical Eng. 1977. V. 16. № 5. P. 479-484.

45. Marr D., Hildreth E. Theory of edge detection // Proc. Royal Soc. L. 1980. V. 207. P. 187-217.

46. Canny J. A computational approach to edge detection // IEEE Trans. Pattern Analysis Mach. Intel. 1986. V. 8. P. 34-43.

47. Dron L. The multiscale veto model: A two-stage analog network for edge detection and image reconstruction // Int. J. Comput. Vision. 1993. V. 11. P. 45-61.

48. Huttenlocher D. // Edge detection. TR of Cornell University. Computer Science, 664. Computer vision. 1995. P. 1-32.

49. Zugaj D., Lattuati Y. A new approach of color image segmentation based on fusing region and edge segmentation outputs // Pattern Recog. 1998. V. 31. №2. P. 105-113.

50. Parent P., Zucker S. Trace inference, curvature consistency and curve detection // IEEE Trans. Pattern Analysis Mach. Intel. 1989. V. 11. № 8. P. 623-639.

51. Cox I., Regh J., Hingorani S. A bayesian multiple-hypothesis approach to edge grouping and contour segmentation // Int. J. Comput. Vision. 1993. V. 11. №1. P. 47-56.

52. Guy G., Medioni G. Inferring global perceptual contours from local features // Int. J. Comput. Vision. 1996. V. 20. № 1-2. P. 56-67.

53. Jacobs D. Robust and efficient detection of salient convex groups // IEEE Trans. Pattern Analysis Mach. Intel. 1996. V. 18. №1. P. 24-39.

54. Deriche R. Using Canny's criteria to derive a recursively implemented optimal edge detector // Int. J. Comput. Vision. 1987. V. 5. P. 167-187.

55. Monga O., Deriche R., Malandain G. et al. Recursive filtering and edge tracking: Two primary tool for 3D edge detection // Int. J. Comput. Vision. 1991. V. 9. P. 203-214.

56. Levine M., Shaheen S. A modular computer vision system for picture segmentation and interpretation // IEEE Trans. Pattern Analysis Mach. Intel. 1981. V.3. №. 5. P. 588-597.

57. Gambotto J. A new approach to combining region growing and edge detection // Pattern Recognition Lett. 1993. V. 14. P. 869-875.

58. Schettini R. A segmentation algorithm for color images // Pattern Recogn. Letters. 1993. V. 14. P. 499-506.

59. Adams R., Bischof L. Seeded region growing // IEEE Trans. Pattern Analysis Mach. Intel. 1994. V. 16. № 6. P. 609-628.

60. Leonardis A., Gupta A., Bajcsy R. Segmentation of range images as the search for geometric parametric models // Int. J. Computer Vision. 1995. V. 14. №3. P. 253-277.

61. Pietikainen M., Rosenfeld A., Walter I. Split and link algorithm for image segmentation// Pattern Recogn. 1982. V. 15. P. 287-298.

62. Chen S., Lin W., Chen C. Split-and-merge image segmentation based on the localized feature analysis and statistical test // Comput. Vision Graphics Image Process. 1991. V. 53. P. 457-475.

63. Wu X. Adaptive split-and-merge segmentation based on piecewise least-square approximation // IEEE Trans. Pattern Analysis Mach. Intel. 1993. V. 15. P. 808-815.

64. Peleg S. A new probabilistic relaxation scheme // IEEE Trans. Pattern Analysis Mach. Intel. 1980. V. 2. P. 362-369.

65. Ohta Y., Kanade T., Sakai T. Color information for region segmentation // Comput. Graphics and Image Proces. 1980. V. 13. P. 222-241.

66. Lin X., Chen S. Color image segmentation using modified HSI system for road following H Proc. IEEE Conf. on Robotics and Automation. Sacramento, California, 1991. P. 1998-2003.

67. Tominaga S. A color classification method for color images using a uniform color space // Proc. 10th. Int. Conf. on Pattern Recogn. Atlantic City, New Jersey, 1990. V. 1. P. 803-807.

68. Sinclair D. Voronoi seeded colour image segmentation // Technical Report 1999.3, AT&T Laboratories Cambridge, 1999. http.7/www-lce.eng.cam.ac.uk/publications/files/tr.1999.3.pdf.

69. Meyer F., Beucher S. Morphological segmentation II J. Vis. Commun. Image Represent. 1990. V. 1. P. 21-46.

70. Vincent L., Soille P. Watersheds in digital space: an efficient algorithm based on immersion simulation // IEEE Trans. Pattern Analysis Mach. Intel. 1991. V. 13. P. 583-598.

71. Jackway P. Gradient watersheds in morphological scale-space // IEEE Trans. Image Procès. 1996. V. 5. № 6. P. 913-921.

72. Harris K., Efstratiadis N., Maglaveras N. et al. Hybrid image segmentation using watersheds and fast region merging // IEEE Trans. Image Procès. 1998. V. 7. № 12. P. 1684-1699.

73. Gauch J. Image segmentation and analysis via multiscale gradient watershed hierarchies // IEEE Trans. Image Procès. 1999. V. 8. № 1. P. 69-79.

74. Bieniek A., Moda A. An efficient wathershed algorithm based on connected components // Pattern Recognit. 2000. V. 33. N 6. P. 907-914.

75. Meyer F. Colour image segmentation // Proc. IEEE Int. Conf. On Image Proc. and its Applic. Maastricht, Netherlands, 1992. P. 303-306.

76. Fairfield J. // Toboggan contrast enhancement for contrast segmentation. Proc. 10th Int. Conf. Pattern Recog. (Atlantic City, 1990), IEEE Computer Soc. Press, Los Alamitos, 1990. V. 1. P. 712-719.

77. Najman L., Schmitt M. Geodesic saliency of watershed contours and hierarchical segmentation // IEEE Trans. Pattern Analysis Mach. Intel.1996. V. 18. P. 1163-1173.

78. Hartigan J. Clustering algorithms. U.S.A.: J. Wiley and sons, 1975.

79. Дуда P., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976. 511 с.

80. Celenk М. A color clustering technique for image segmentation // Сотр. Vision Graphics and Image Process. 1990. V. 52. P. 145-170.

81. Shi J., Malik J. Normalized cuts and image segmentation // Proc. IEEE Conf. Computer Vision and Pattern Recogn. San Juan, Puerto Rico,1997.

82. АН M., Martin W., Aggarwal J. Color-based computer analysis of aerial photographs // Comput. Graphics and Image Process. 1979. V. 9. P. 282293.

83. Frigui H., Krishnapuram R. A robust competitive clustering algorithm with applications in computer vision // IEEE Trans. Pattern Analysis Mach. Intel. 1999. V. 21. P. 450-464.

84. Huntsberger Т., Jacobs C., Cannon R. Iterative fuzzy image segmentation //Pattern Recogn. 1985. V. 18. №2. P. 131-138.

85. Trivedi M., Bezdek J. Low-level segmentation of aerial image with fuzzy clustering // IEEE Trans. Systems, Man and Cybernetics. 1986. V. 16. P. 589-598.

86. Lim Y., Lee S. On the color image segmentation algorithm based on the thesholding and the fuzzy c-means techniques // IEEE Trans. Pattern Analysis Mach. Intel. 1990. V. 12. P. 609-628.

87. Gupta L., Sortrakul T. A gaussian-mixture-based image segmentation algorithm // Pattern Recognition. 1998. V. 31. P. 315-325.

88. Хорн Б.К. Зрение роботов. M.: Мир, 1989. 488 с.

89. Healey G. Using color for geometry-insensitive segmentation. // J. Opt. Soc. Am. A. 1989. V. 6. № 6. P. 920-937.

90. Nicodemus F., Richmond J., Hsia J. et al. Geometrical considerations and nomenclature for reflectance. U.S. Bureau Standards (U.S.). Monograph 160. 1977.

91. Judd D. B., Wyszecki G. Color in business, science and industry. New York: Wiley, 1975.

92. Tagare H., DeFigueiredo R. A framework for the construction of reflectance maps for machine vision // Comput. Vision Graphics Image Process: Image Understanding. 1993. V. 57. P. 265-282.

93. Tominaga S., Wandell D. The standard surface reflectance model and illumination estimation // J. Opt. Soc. Am. A. 1989. V. 6. № 4. P. 576584.

94. Tominaga S. Surface identification using the dichromatic reflection model // IEEE Trans. Pattern Analysis Mach. Intel. 1991. V. 13. P. 658670.

95. Funt B., Drew M. Color space analysis of mutual illumination // IEEE Trans. Pattern Anal. Mach. Intell. 1993. V. 15. P. 1319-1326.

96. Lee H., Breneman E., Shulte C. Modeling light reflection for computer color vision // IEEE Trans. Pattern Analysis Mach. Intel. 1990. V. 12. P. 402-409.

97. Lee H.-C. Method for computing the scene-illuminant chromaticity from specular highlights // J. Opt. Soc. Am. A. 1986. V. 3. P. 1694-1699.

98. Lee S., Chung S. A comparative performance study of several global thresholding techniques for segmentation // Comput. Vision Graphics Image Process. 1990. V. 52. P. 171-190.

99. Hough P. V. // Methods and means for recognizing complex patterns. U.S. Patent 069654.1962.

100. Ballard D. Generalizing the Hough Transform to detect arbitrary shapes //Pattern Recognit. 1981. V. 13. P. 111-122.

101. Nagendra Ch., Borah M., Vishwanath M. et al. // Edge detection using fine-grain parallelism in VLSI. Proc. IEEE Int. Conference on Acoustics, Speech and Signal Processing. Minneapolis, 1993. V. 1. P. 401-404.

102. Гельфанд И.М., Гиндикин С.Г., Граев М.И. Избранные задачи интегральной геометрии. М.: Добросвет, 2000. 208 с.

103. Rousseeuw P., Leroy A. Robust Regression and Outlier Detection., New York: Wiley, 1987.

104. Olson C. Constrained Hough transforms for curve detection // Сотр. Vision and Image Understand. 1999. V. 73.

105. Lawton W. A new polar Fourier transform for computer-aided tomography and spotlight synthetic aperture radar // IEEE Trans. Acoustics Speech Signal Process. 1988. V. 36(6).

106. Donoho D., Huo X. Beamlet pyramids: A new form of multiresolution analysis, suited for extracting lines, curves, and objects from very noisy image data // Proc. SPIE. 2000. V. 4119.

107. Mortensen E., Reese L., Barrett W. Intelligent selection tools // Proc. IEEE Conference on Computer Vision, 2000. -http://rivit.cs.byu.edu/~enm/.

108. Tan K.-H., Ahuja N. Selecting objects with freehand sketches // Proc. IEEE Int. Conference on Computer Vision (ICCV 2001). 2001 -http.//vision.ai.uiuc.edu/~tankh/Selection/selection-iccv2001-72dpi.pdf.

109. Di Zenzo S. A note on the gradient of multi-image // Comput. Vision Graphics Image Process. 1986. V. 33. P. 116-125.

110. Sapiro G., Ringach D. Anisotropic diffusion of multivalued images with applications to color filtering // IEEE Trans, on Image Process. 1996. V. 5. P. 1582-1586.

111. Пытьев Ю.М. Методы анализа и интерпретации эксперимента. М.: Изд-во МГУ. 1990.

112. Леман Э. Проверка статистических гипотез. М.: Наука, 1979.

113. Otsu N. A threshold selection method from gray-level histograms // IEEE Trans. Systems Man Cybern. 1979. V.9. P. 62-66.

114. 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.

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

116. Грассман X., 1854 (цит. по 21]).