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

На правах р^ копией

Казанов Марат Джамалудинович

Сегментация цветных изображений печатных документов

05 13 01 - Системный анализ, управление и обработка информации (информационно-вычислительное обеспечение)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 2008

003172180

Работа выполнена в Учреждении Российской академии наук Институте системного анализа РАН, лаборатории Системного программирования

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

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

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

доктор технических наук, профессор, член-корреспондент РАН, Арлазаров Владимир Львович доктор физ -мат наук, Берзигияров Парваз Куламович кандидат физ -мат наук, Усков Анатолий Васильевич Учреждение Российской академии наук Институт проблем информатики РАН

Защита состоится 30 июня 2008 г в 11 часов на заседании диссертационного совета Д 002 086 02 при Учреждении Российской академии наук Институте системного анализа РАН, расположенном по адресу 117312, г Москва, пр-т 60-летия Октября, 9

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Института системного анализа РАН

Автореферат разослан 29 мая 2008 г

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

Ученый секретарь диссертационного совета,

дтн, профессор

А И Пропой

Общая характеристика работы

Актуальность работы. В последние годы появляется все больше прикладных областей, п которых актуально применение методов сегментации изображений — это системы распознавания документов, мультимедийные базы данных, передача видео через сеть Интернет, цифровая фотография, сжатие изображений и другие Особенно велик интерес исследователей к сегментации цветных изображений, так как цветное изображение несет значительно больше информации, чем полутоновое Известно, что человеческий глаз в состоянии различать одновременно лишь небольшой интервал яркости — данное явление известно в психофизиологии зрения как «адаптация к освещенности» — но, в то же время, воспринимает тысячи цветовых оттенков [1] Бурное развитие вычислительной техники, а именно, повышение быстродействия и объемов хранения оперативной информации, позволяет увеличить скорость обработки изображений и перейти к обработке в реальном времени не только полутоновых, но и цветных изображений, требующих анализа большего количества информации

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

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

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

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

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

Апробация работы. Основные резучьтаты диссертации докладывались на следующих международных конференциях 17гЛ International Conference on Pattern Recognition ICPR 2004 (Cambridge, UK), 3rd IASTED International Conference on Visualization, Imaging, and Image Processing (Benalmadena, Spain), международной конференции студентов и аспирантов по фундаментальным наукам «Ломопосов-2004», и опубликованы в работах, перечисленных в конце автореферата, среди которых 2 статьи в ведущих российских журналах, 3 статьи в трудах международных конференций и одни тезисы доклада на всероссийской конференции

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

96 наименований Работа изложена на 115 страницах машинописного текста, содержит 25 рису нков

Содержание работы

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

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

В разделе 1 1 обзор методов сегментации предваряет описание возможных вариантов представления цветовых характеристик точек изображения Рассматриваются представления точек в цветовых пространствах RGB, HSI, CIE L*a*b* и CIE L*u*v*, позволяющие выражать воспринимаемые человеческим глазом различия между двумя цветами в виде цифрового значения евклидова расстояния между точками в данных трехмерных пространствах В разделах 1 2-1.9 обсуждаются преимущества и недостатки следующих групп методов сегментации цветных изображений

— методов, основанных на анализе гистограмм изображении,

— методов кластерного анализа,

— методов роста регионов,

— методов, основанных на определении границ областей,

— методов, использующих элементы вариационного анализа, теории графов,

— методов, использующих элементы теории нечетких множеств,

— методов, использующих искусственные нейронные сети,

— методов, использующих физические модели освещения объектов и отражения объектами света

На основе анализа существующих методов делается вывод об отсутствии

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

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

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

— возможностью сегментации объектов с градиентной внутренней областью

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

В разделе 2 1 выполняется формальная постановка задачи диссертационной работы

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

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

Ътд{х,у) Ж2-*М3,

где М3 представляет собой выбранное цветовое пространство (RGB, HSI, ) Будем считать, чю в областях {£1, Si, , Sn}, соответствующих следующим объектам изображения — фонам, символам основного текста, буквицам, графическим элементам (исключая иллюстрации), данная функция либо принимает постоянное значение

VSt,Vpo = (х0,у0),Щ= {xuVi) Щ,р\ 6 8г,Стд(Щ) = Cor,,(pl), (1)

либо градиенты трех цветовых компонент данной векторной функции постоянны

\/5„Ур? = (хо,уо),Ур1 = (хь 2/1) Щ,ш е 5„дга<1(Ск0Г1д)(М) = 9гаё,(С1ОТ1д){р1)

(2)

и их модули не превышают заранее заданное пороговое значение Тдтш1

^{дгай{с119Ш))2 <Тдта^ (3)

где к = {1,2,3} - компоненты пространства И3

Несовершенство устройств ввода-вывода приводит к искажению исходного изображения в процессе печати и сканирования [3] Вследствие этого, исходное цветное изображение документа, описываемое непрерывной функцией С0пд(х,у), преобразуется в искаженное результирующее цифровое изображение, описываемое векторной функцией дискретного аргумента Стеа1(т,у) Далее в работе предполагается, что данное преобразование, в общем случае, имеет следующий вид [4]

д{х, у) = ф(НЦ(х, у)}) + ф, у),

где д(х, у) — искаженное изображение, /(ж, у) — исходное изображение, Н() — линейный оператор «размытия» изображения, ф() — нелинейное преобразование, т](х, у) — аддитивный шум Задачей данной диссертационной работы являлось определение множества областей объектов {5,}, совокупность которых составляет исходное изображение I = {ий^}, на основе анализа результирующего цифрового изображения Стеа1(х,у), искаженного, относительно его исходной версии Соггд(х,у)

В разделе 2 2 приводятся определения основных понятий, используемых далее в работе линеиного среза изображения, дифференциального оператора, градиентного изображения, масштаба изображения, масштаба дифферен-

Цветное изображение документа

Сегментированное изображение

Рис 1 Общая схема работы предтагаечого метода сегментации цветных изображений печатных документов

циального оператора, аппроксимирующей производной Представлено формальное определение преобразования водоразделов (watershed transformation) В разделе 2.3 представлена общая схема работы предлагаемого метода сегментации, разработанного на основе метода сегментации водоразделами (watershed segmentation) (рис 1)

В разделе 2.4 представлен метод многомасштабного анализа линейных срезов изображения

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

а) |(х) *

х„ х,

6) Щх,8)' т

в) ЯСх.з,)^

г) ВД

X

X„ X,

гА;

Хц X,

1

X. X,

X, X,

УЛ.

Хг X,

ха х„

х, х.

Рис 2 а) Линейный срез исходною изображения (х1 - позиция резкой границы, Х2 -позиция плавной 1раницы) б) Аппроксимирующая производная масштаба ¿1 (Т порог на принадлежность к траничпыы точкам) в) Аппроксимирующая производная масштаба я2 ($1 < вг) г) Предлагаемая комбинированная аппроксимирующая производная

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

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

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

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

Я, (г) = 1{г) * М„

где Яа — аппроксимирующая производная масштаба в, Ма — маска дифференциального оператора масштаба в, * — операция свертки Далее, методом порогов опредетяется множество граничных точек Е Причем, дифференциальный оператор применяется только в тех точках {г}, где его маска не пересекается с позициями границ, зафиксированными на предыдущих масштабах

{г} (г — а,г + а) П £ = 0,

где а = (тп —1)/2, т - размер маски В качество конечного значения аппроксимирующей производном в неграничной точке выбирается максимальное из значений результатов применения дифференциального оператора в данной точке по всем масштабам

Л (г) = тах Ля(г)

л

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

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

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

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

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

Указанный метод вычисления аппроксимирующей производной /'¡(х) первоначально излагается только для одной цветовой компоненты точек, представленных в системе HSI, — интенсивности (Intensity), что соответствует полутоновой версиии исходного изображения Значение аппроксимирующей производной для случая цветного изображения может быть вычислено методом, предложенным в [о] Для этого необходимо получить аналогичным образом значения аппроксимирующих производных /¿(х) и }'н(х) для оставшихся двух компонент — насыщенности и тона (Saturation, Hue) и вычислить

результирующее значение аппроксимирующей производной

л*) = \1(ш?+(.т?+{т)2

В разделе 2 6 представлен метод, позволяющий определять дополнительные точки минимумов аппроксимирующей производной, соответствующие внутренним областям обьектов малого размера

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

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

Пусть линейный срез цветного изображения С{х) содержит прилегающие объекты 01 и О2, имеющие цвета С\ = (ДьС?!,.^) и С% = (Дг, С^,-^), соответственно Также, пусть между рассматриваемыми объектами располагается плавная граница, точки которой состав тяют множество граничных точек Е Пронумеруем граничные точки в направлении от первого объекта ко второму е„ г € 1 п, где п - количество точек рассматриваемого мно-

У

(С.,М,ЛМ

¿г ' 1с.. М_ V.!

С

Рис. 3. Распределение цветов граничных точек в цветовом пространстве СМУ.

жества. Цвета точек границ между объектами О\ и Ог, учитывая то, что при печати мог возникнуть эффект неточного совмещения, будут являться смесью цветов первого объекта (С^М^Ух), второго объекта (С2,М2,Уг) и цвета межграничной полосы (Сь,Мь,Уь)- Цвет межграничной полосы заранее неизвестен, однако, можно утверждать, что цвета граничных точек в пространстве СМУ будут располагаться внутри параллепипеда, построенного на вершинах {Сг,М^,Ук)-: где г = 1, 2: 3 = 1, 2; к — 1,2. Координаты данных вершин являются всевозможными сочетаниями цветовых компонент двух объектов. Две из восьми вершин параллелепипеда являются цветами первого и второго объектов, соответственно. Шесть остальных представляют собой возможные цвета граничной полосы в случае возникновения эффекта неточного совмещения.

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

мой, соединяющей цвета первого и второго объектов В случае наличия эффекта неточного совмещения цвета граничных точек образуют дугу, построенную на вершинах (С^МьУ!) и (С^Мг,^) параллелепипеда Р Причем, дуга выгнута в сторону вершины параллелепипеда Р соответствующей цвету межграничной полосы (рис 3) Изменение цветов вдоль указанного направления, как для случая наличия эффекта неточного совмещения так и для случая его отсутствия (при этом Уг аг = А = 7,), можно описать следующими равенствами

а = + (1 - аг)С2,

Мг = Р,М1 + (1-0,)М2, (4)

Уг = 7.*1 + (1-7.)Уа,

где

а, е (0,1), г = 1,2, ,п и 0 < а.\ < <Ог< < сеп -1<ап< 1,

А е (0,1),г = 1,2, ,п и 0 < р1 < < А < <г£ VI -1 < Аг < 1,

7. € (0,1),г II ь-* , п и 0 < 71 < <7г< < 7п- ■1 < 1п < 1

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

определяются как точки минимума производном и, соответственно, рассматриваются как внутренние области объектов малого размера

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

Первоначально показана нецелесообразность применения традиционного варианта метода водоразделов к совокупности аппроксимирующих производных, полученных с помощью методов, представленных в разделах 2 4-2 6 Предлагаемая модификация метода водораздетов заключается в выполнении процесса наводнения поверхности только в межпиксельиых позициях {р^} исходною изображения, находящихся на горизонтальных, вертикальных и диагональных линейных срезах изображения

Ы = {(¿р;,Урь)} = <

гориз позиции (2г,2(] - 1) + 1) верт позиции (2(г — 1) + 1,2j) диаг позиции (2г, 2j)

где г = 1, , М — 1, j = 1, , N — 1, М и N - ширина и высота изображения, соответственно В данных позициях значения аппроксимирующих производных вычислены по соответствующим типу позиций нанравтениям Предлагаемая модификация метода водоразделов имеет аналогию с известным методом роста регионов — методом роста регионов путем кластеризации по наименьшему расстоянию (single linkage region growing, SLGR) [8] Метод SLRG осуществляет объединение в кластеры соседних точек изображения, разница цветовых характеристик которых, вычисленная в определенной метрике, не превышает некоторый порог В отличие от метода SLRG, в котором пиксели изображения объединяются в произвольном порядке, предлагаемый метод выполняет объединение пикселей в порядке увеличения разницы их цветовых характеристик Такой подход позволяет уже на низких уровнях опреде-

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

Для устранения излишней сегментации, характерной для преобразования водоразделов и возникающей в следствие шума, в данной работе предлагается подход, аналогичный преде хавленному в [9], заключающийся в объединении соприкасающихся бассейнов в процессе наводнения поверхности, для итераций наводнения ниже некоего заданного уровня Ит Таким образом, операция наводнения для каждой межпиксельной позиции рь заключается в рассмотрении соответствующих точек изображения РьРг. таких, что

Р1.2 = {Хр^Ур^)

(хрь ^ 1,уРь), если р/, - гориз позиция (хрь>Урь ^ если Рь ~ верт позиция

(хРь ^ 1, Урь Т 1), если рь - левая диаг позиция (хрь 1, уРь ± 1), если рь - правая диаг позиция и, выполнении, в зависимости от принадлежности точек РиР2 к существующим бассейнам {Сг(р)}, следующих операций

1) создания бассейна — С(р\) = рг 1>Р2, если р\ £ {С^} и рг $ {С^},

2) присоединения точки к существующему бассейну —

СЫ = С(Р1) и р2, если р2 $ {Сг}, или С(р2) = Р\ и С(р2), если рг £ {Сг},

3) объединения бассейнов — С{р\) = С{р\) иС(р2), если Щрь) < Ьт

Для исключения ошибочного объединения бассейнов был разработан дополнительный критерий контроля слияния бассейнов Предлагаемый крите-

рий основан на использовании информации о сегментации линейных срезов, полученной на этапе работы алгоритма, представленного в разделах 2 4-2 6 Пусть Са и Сг — объединяемые бассейны, Р\ и Р2 - множества точек контуров первого и второго бассейнов, соответственно Найдем все прямолинейные отрезки, лежащие па горизонтальных, вертикальных или диагональных прямых, соединяющие попарно точки кошуров двух бассейнов и не содержащие внутренних точек бассейнов р1 € Рг,р} € Рг,Ур € и С2/Р1 и Р2} у £ (РпРу) Если через определенную точку контура проходят несколько отрезков, то будем рассматривать только отрезок, имеющий минимальную длину, что, по-возможности, позволит рассматривать отрезки, близкие к нормальным направлениям к контурам бассейнов Введем функцию 5(5*,), определенную на множестве отрезков {я^} = {{рг,р^}, к = 1, ,К, где К — количество отрезков, и принимающую значение 1 — в случае, если данный отрезок содержит одну граничило точку сегментов линейною среза, 0 — в остальных случаях — когда отрезок либо не содержит граничных точек, либо содержит более одной граничной точки Данная ф^ нкция представляет собой индикатор существования границы в данном направлении между двумя областями В первом случае, бассейны, соединяемые рассматриваемым отрезком, граничат друг с другом по данному направлению, во втором — не граничат друг с другом по причине наличия между ними других бассейнов или же по причине того, что они принадлежат одной однородной области Подсчитаем (7

А

— сумму значении д{вк) по всем рассматриваемым отрезкам С = X! з(ьк)

г—\

Отношение С/К может рассматриваться как оценка вероятности того, что объединяемые бассейны не являются одной однородной областью

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

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

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

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

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

1 Классификация объектов изображения

2 Бинаризация внутрифоновых обласхей

В разделе 3 1 представлена разработанная схема классификации объектов изображения, основанная на методе деревьев решений [10] Полученное при помощи алюригма CART [10] дерево решении было построено на основе анализа нескольких десятков реальных изображений Дерево классификации разбивает все объекты изображения на три класса фоны, символы основного текста и все остальные объекты изображения Характеристиками обьскюв, используемыми при классификации, были выбраны площадь объекта и количество других объектов во внутренней области рассматриваемого объекта В разделе 3 2 рассматривается преобразование в полутоновое изображение областей, составленных из объектов только двух типов — фона и текста, и последующее выполнение в данных областях процесса бинаризации

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

Обосновывается выбор адаптивного метода определения порога бинаризации, предложенною Сауволой и соавторами [12] и являющегося развитием метода Ниблэка [11], в качестве используемого метода бинаризации

где Т - пороговое значение полутона, m - среднее значение полутонов точек рассматриваемого окна, s - стандартное отклонение, R — параметр, нормализующий величину стандартного отклонения, как правило задаваемый равным

128, а к — константа равная 0 5

В разделе 3.3 оценивается вычислительная сложность предлагаемого метода Вычислительная сложность большинства этапов представленного метода сегментации не превышает O(N) операции, где N - количество точек изображения Вычислительная сложность этапа применения модифицированного преобразования водоразделов в наихудшем случае может быть оценена как 0(N2) операций

В разделе 3.4 обсуждаются результаты применения предложенного метода к цветным изображениям печатных документов Представленный метод был реализован на языке С— для операционной системы Windows Результатом работы алгоритма является сегментированное изображение, которое может быть представлено в одном из двух видов в первом случае, каждая сегментированная область изображения полностью окрашивается средним цветом принадлежащих ей точек, во втором случае, области раскрашиваются произвольными цветами, но так, что любые две соприкасающиеся области не окрашены в один цвет Результаты сегментации цветных изображений документов, полученные предлагаемым методом, сравниваются с результатами работы традиционного алгоритма сегментации водоразделами [13] и алгоритма среднего сдвига [14] Продемонстрировано, что основными преимуществами предлагаемого метода являются высокая точность сегментации, способность алгоритма сегментировать объекты, имеющие как плавные, так и резкие границы, устойчивость к шуму на границах областей, способность сегментировать области с градиентным фоном, корректная обработка областей, имеющих эффект неточного совмещения

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

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

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

В приложении А представлены примеры сегментации цветных изображении печатных документов предлагаемым методом в сравнении с другими методами сегментации [13-14]

Основные результаты работы

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

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

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

4 Предложен метод определения внутренних областей объектов малого

размера Данный метод обобщен до возможности обработки изображений, имеющих эффект неточного совмещения

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

Список публикаций

1 Арлазаров В Л, Казанов М Д Сегментация объектов малого размера на цветных изображениях // Программирование —2008 —Том 34, № 3 -Стр 173-182

2 Казанов М Д Многомасштабный подход к определению контуров объектов на цифровых изображениях // Организационное управление и искусгпвенный интеллект, Труды Института Системного Анализа РАН -2003 -Стр 228-238

3 Kazanov М D A new color image segmentation algorithm based on watershed transformation // Proceedings of the 17th International Conference on Pattern Recognition (ICPR 2004), Cambridge, United Kingdom - Vol II -2004 -Pp 590-593

4 Kazanov M D Modification of watershed transformation for images containing small objects // Proceedings of the 17th International Conference on Pattern Recognition (ICPR 2004), Cambridge, United Kingdom - Vol I -2004 -Pp 612-615

5 Казанов М Д Сегментация изображений страниц цветных печатных документов // Материалы Международной конференции студентов и аспирантов по фундаментальным паукам <Лочоносов-2004> — 2004

6 Kazanov М D One approach to multi-scale edge detection //' Proceedings of the 3rd IASTED International Conference on Visualization, Imaging, and Image Processing, Benalmadena, Spain — 2003 — Pp 356-360

Цитируемая литература

1 Gonzalez R С, Woods R E Digital Image Processing — Upper Saddle River, New Jeiscy Pientice Hall, 2002

2 Pal N R , PalS К A review on image segmentation techniques // Pattern Recognition -1993 - Vol 26, no 9 -Pp 1277-1294

3 Baird H S The state of the art of document image degradation modeling // Digital Document Processing / Ed by В В Chaudhun — Guildford,Suney,UK Springer-Verlag, 2007

4 Rosenfeld A , Как А С Digital Picture Processing — New York Academic Press 1982

5 Di Zenzo S A note on the gradient of a multi-image // Computer Vision, Graphics, and Image Processing —1986 — Vol 33 — Pp 116-125

6 White J M, D R G Image thresholding for optical character recognition and other applications requiring character image extractraction // IBM J Res Devel -1983 - Vol 27, no 4 - Pp 400-411

7 Sharma G Digital Color Imaging Handbook, Chapter 7 — BocaRaton, FL CRC Press, 2003 - Pp 491-558

8 Brunner D , Soille P Iterative area filtering of multichannel linages // Image and Vision Computing -2007 - Vol 25, no 8 — Pp 1352-1364

9 S Derwaux, S Lefevre, C Wemmert, J Korczak On machine learning in watershed segmentation // IEEE Workshop on Machine Learning for Signal Processing — 2007

10 L J Breiman, H Friedman, C J Stone, R A Olshen Classification and Regression Trees / — Belmont, CA Wandsworth, Inc , 1984

11 Niblack W An Introduction to Digital Image Processing — Englewood Cliffs, N J Prentice Hall, 1986 -Pp 115-116

12 J Sauvola, T Seppanen, S Haapakoski, M Pietikamen Adaptive document bmarization 11 International Conference in Document Analysis and Recognition — Vol 1 -1997 - Pp 147-152

13 Vincent L , Soille P Watersheds m digital spaces An efficient algorithm based on immersion simulation // IEEE Transactions on Pattern Analysis and Machine Intelligence -1991 —Vol 13, no 6 — Pp 583-598

14 Comaniciu D, Meer P Mean shift A robust approach toward feature space analysis // IEEE Transactions on Pattern Analysis and Machine Intelligence - 2002 - Vol 24 - Pp 603-619

Подписано в печать 29 05 2008 г Печать трафаретная

Заказ № 489 Тираж 100экз

Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш , 36 (495) 975-78-56, (499) 788-78-56 www autoreferat ru

Введение

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

1.1. Представление цветовых характеристик точек изображения

1.2. Методы, основанные на анализе гистограмм изображений

1.3. Методы кластерного анализа.

1.4. Методы роста регионов.

1.5. Методы, основанные на определении границ областей

1.6. Методы, использующие элементы вариационного анализа, теории графов.

1.7. Методы, использующие элементы теории нечётких множеств

1.8. Методы, использующие искусственные нейронные сети.

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

Глава 2. Сегментация цветных изображений.

2.1. Постановка задачи диссертационной работы

2.2. Основные определения, сегментация методом водоразделов

2.3. Общая схема работы предлагаемого метода сегментации

2.4. Многомасштабный анализ линейных срезов

2.5. Вычисление аппроксимирующей производной линейных срезов

2.6. Определение внутренних областей объектов малого размера

2.7. Модификация преобразования водоразделов.

Глава 3. Анализ цветных изображений документов

3.1. Классификация объектов изображения.

3.2. Бинаризация внутрифоновых областей

3.3. Вычислительная сложность алгоритма

3.4. Практические результаты и обсуждение

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

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

В последние годы появляется все больше прикладных областей, в которых актуально применение методов сегментации изображений — это системы распознавания документов, мультимедийные базы данных, передача видео через сеть Интернет, цифровая фотография, сжатие изображений и другие. Особенно велик интерес исследователей к сегментации цветных изображений, так как цветное изображение несёт значительно больше информации, чем полутоновое. Известно, что человеческий глаз в состоянии различать одновременно лишь небольшой интервал яркости — данное явление известно в психофизиологии зрения как «адаптация к освещённости» — но, в то же время, воспринимает тысячи цветовых оттенков [1]. Бурное развитие вычислительной техники, а именно, повышение быстродействия и объёмов хранения оперативной информации, позволяет увеличить скорость обработки изображений и перейти к обработке в реальном времени не только полутоновых, но и цветных изображений, требующих анализа большего количества информации.

Представленные в литературе работы по сегментации изображений посвящены, главным образом, сегментации полутоновых изображений [2-4]. Методы сегментации полутоновых изображений в общем случае не позволяют получить удовлетворительные результаты при применении их к цветным изображениям, так как в данных методах рассматривается только уровень яркости точек изображения и не учитываются цветовые (хроматические) характеристики точек.

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

Одной из прикладных областей, в которых традиционно применяется сегментация изображений, являются системы анализа изображений документов. Эта категория интеллектуальных систем включает в себя как задачи распознавания текста, так и задачи определения макета (layout) и графических элементов страниц документа. Неотъемлемой частью таких систем является процесс сегментации изображения. Как правило, данные системы ориентированы на обработку полутоновых изображений, и для сегментации в них используются методы бинаризации или порога (thresholding) [8]. Целью бинаризации является разделение точек изображения, путём определения разделяющего значения яркости, на два класса: на точки, принадлежащие фону и точки, принадлежащие объектам изображения. Порог яркости может определяться как один для всего изображения, тогда такой метод называют глобальным, так и для разных областей изображения могут определяться различные пороги, тогда такие методы называют адаптивными. Однако, при сегментации полутоновых изображений как глобальный, так и адаптивный методы бинаризации не всегда могут быть эффективны. Например, если в соседних частях изображения яркость фона и объектов инвертирована относительно друг друга или во внутренней области фона яркость плавно меняется. Ошибки сегментации в данных случаях являются следствием основного принципа бинаризации, который предполагает, что яркость всех объектов, для изображения в целом (глобальный подход) или в конкретной области (адаптивный подход), больше некоторого порога яркости, а яркость фона ниже этого порога. По этой же причине — принципу разделения точек изображения на две группы по уровню яркости — бинаризация работает неэффективно при обработке цветных изображений, так как для успешной сегментации цветного изображения, кроме уровня яркости, необходимо учитывать и хроматические характеристики точек.

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

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

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

Научная новизна работы обусловлена впервые предложенными методами обработки цветных изображений — методом многомасштабной сегментации линейных срезов изображения, методом определения внутренних областей а) в)

There's always a copy available with

OnlineBooks www.interscience.wiley.com/onlinebooks

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

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

Основные результаты диссертации докладывались на следующих международных конференциях: 17th International Conference on Pattern Recognition ICPR 2004 (Cambridge, UK); 3rd IASTED International Conference on Visualization, Imaging, and Image Processing (Benalmadena, Spain); международной конференции студентов и аспирантов по фундаментальным наукам «Ломоносов-2004», и опубликованы в работах [9-14].

Диссертационная работа включает в себя 3 главы, введение и заключение.

Основные результаты диссертационной работы

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

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

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

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

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

Благодарности

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

Заключение

1. Gonzalez R. С., Woods R. E. Digital 1.age Processing.— Upper Saddle River, New Jersey: Prentice Hall, 2002.

2. Haralick R. M., Shapiro L. G. Image segmentation techniques // Computer Vision, Graphics, and Image Processing. — 1985. — Vol. 29, no. 1. — Pp. 100132.

3. Fu K. S., Mu J. K. A survey on image segmentation // PatternRecognition. — 1981. Vol. 13, no. 1. - Pp. 3-16.

4. Pal N. R., Pal S. K. A review on image segmentation techniques // Pattern Recognition. — 1993. — Vol. 26, no. 9. — Pp. 1277-1294.

5. Lucchese L., Mitra S. К. Color image segmentation: A state-of-the-art survey // Proc. of the Indian National Science Academy (INSA-A), Image Processing, Vision, and PatternRecognition, New Delhi, India. — Vol. 67 A. — 2001.-Pp. 207-221.

6. Color image segmentation: advances and prospects / H. D. Cheng, X. H. Jiang, Y. Sun, J. Wang // Pattern Recognition. — 2001.— Vol. 34, no. 12. — Pp. 2259-2281.

7. Skarbek W., Koschan A. Colour image segmentation a survey // Technical Report 94-32, Technical University Berlin. — 1994.

8. Sezgin M., Sankur B. Survey over image thresholding techniques andquan-titative performance evaluation // Journal of Electronic Imaging. — 2004. — Vol. 13, no. 1. Pp. 146-165.

9. Kazanov M. D. A new color image segmentation algorithm based on watershed transformation // Proceedings of the 17th International Conference on

10. Pattern Recognition (ICPR 2004), Cambridge, United Kingdom. — Vol. II. — 2004. Pp. 590-593.

11. Kazanov M. D. Modification of watershed transformation for images containing small objects // Proceedings of the 17th International Conference on Pattern Recognition (ICPR 2004), Cambridge, United Kingdom. — Vol. I.— 2004.-Pp. 612-615.

12. Kazanov M. D. One approach to multi-scale edge detection // Proceedings of the 3rd IASTED International Conference on Visualization, Imaging, and Image Processing, Benalmadena, Spain. — 2003. — Pp. 356-360.

13. Казанов M. Д. Сегментация изображений страниц цветных печатных документов // Материалы Международной конференции студентов и аспирантов по фундаментальным наукам <Ломоносов-2004>.— 2004.

14. Казанов М. Д. Многомасштабный подход к определению контуров объектов на цифровых изображениях // Организационное управление и искуственный интеллект, Труды Института Системного Анализа РАН. 2003. - Pp. 228-238.

15. В. Л. Арлазаров, Казанов М. Д. Сегментация объектов малого размера на цветных изображениях // Программирование. — 2008. — Vol. 3. — Pp. 1-13.

16. Wyszecki G., Stiles W. S. Color Science: Concepts and Methods, Quantitative Data and Formulae. — New York, NY: Wiley, 1982.

17. Guo G., Yu S., Ma S. Unsupervised segmentation of colorimages // Proc. of 1998 Internationall Conference on Image Processing(ICIP'98), Chicago, IL. Vol. III. - 1998. - Pp. 299-302.

18. Shafarenko L., Petrou M., Kittler J. Histogram-based segmentationin a perceptually uniform color space // IEEE Transactions on ImageProcessing. — 1998. Vol. 7, no. 9. - Pp. 1354-1358.

19. Celenk M., Uijt de Haag M. Optimal thresholding for color images // Proc. of the SPIE The International Soc. for Optical Eng.,Nonlinear Image Processing IX, San Cose, CA. — 1998. — Pp. 250-259.

20. Tominaga S. A color classification method for color images using auniform color space // Proceedings of the 10th Int. Conf. on Pattern Recognition.— 1990. Pp. 803-807.

21. Lucchese L., Mitra S. K. Unsupervised low-frequency drivensegmentation of color images // Proc. of International Conference on Image Processing (ICIP'99), Kobe, Japan. 1999. - Pp. 240-244.

22. Herodotou N., Plataniotis K. N., Venetsanopoulos A. N. A colorsegmentation scheme for object-based video coding // Proc. of 1998 IEEE Symposium on Advances in Digital Filtering and Signal Processing, Victoria, BC, Canada. — 1998. Pp. 25-29.

23. Scheering C., Knoll A. Fast colour image segmentation using a pre-clustered chromaticity-plane // Proc. Of 1997 IEEE Internationall Conference on Acoustics, Speech, and Signal Processing (ICASSP'97), Munich, Germany.— Vol. 4. 1997. - Pp. 3145-3147.

24. Androutsos D., Plataniotis K. N., Venetsanopoulos A. N. Distance measures for color image retrieval // Proc. of 1998 International Conference on Image Processing (ICIP'98), Chicago, IL. Vol. II. - 1998. - Pp. 770-774.

25. Sobottka K., Pitas I. Segmentation and tracking of faces in color images //

26. Proc. of the 2nd International Conference on Automatic Faceand Gesture Recognition, Killington, VT. 1996. - Pp. 236-241.

27. Chai D., Ngan K. N. Face segmentation using skin-color map in videophone applications // IEEE Trans, on Circuits and Systems for Video Technology. 1999. - Vol. CASVT-9, no. 4. - Pp. 551-564.

28. Lim Y. W., Lee S. U. On the color image segmentation algorithm based on the thresholding and the fuzzy c-means techniques // Pattern Recognition. — 1990. Vol. 23, no. 9. - Pp. 935-952.

29. Schmid P., Fischer S. Colour segmentation for the analysis of pigmented skin lesions // Proc. of the 6th International Conferenceon Image Processing and Its Applications, Dublin, Ireland. — Vol. 2. — 1997. — Pp. 688-692.

30. Lucchese L., Mitra S. K. Unsupervised segmentation of color images based on k-means clustering in the chromaticity plane // Proc. of IEEE Workshop on Content-Based Access of Images and Video Libraries (CBAIVL'99), Fort Collins, CO. 1999.

31. Rui Y., She A. C., Huang T. S. Automated region segmentation using attraction-based grouping in spatial-color-texture space // Proc. of 1996 International Conference on Image Processing (ICIP'96), Lausanne, Switzerland. Vol. I. - 1996. - Pp. 53-56.

32. Sobel I. Neighborhood coding of binary images for fast contour following and general array binary processing // Computer Graphics Image Processing. — 1978. Vol. 8, no. 1. - Pp. 127-135.

33. Pappas T. N. An adaptive clustering algorithm for image segmentation // IEEE Transactions on Signal Processing. — 1992. — Vol. 40, no. 4. — Pp. 901914.

34. Comaniciu D., Meer P. Robust analysis of feature spaces: Color image segmentation // Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, San Juan, Puerto Rico. — 1997. — Pp. 750-755.

35. Takahashi K., Nakatani H., Abe K. Color image segmentation using isodata clustering method // Proceedings of the 2nd Asian Conf. on Computer Vision (ACCV'95), Singapore. Vol. I. - 1995. - Pp. 523-527.

36. Uchiyama T., Arbib M. A. Color image segmentation using competitive learning // IEEE Transactions on Pattern Analysis and, Machine Intelligence. — 1994. Vol. 16, no. 12. - Pp. 1197-1206.

37. Ikonomakis N., Plataniotis K. N., Venetsanopoulos A. N. Aregion-based color image segmentation scheme // Proceedings of Electrical Imaging '99, vol. 3653 of SPIE, (San Jose, California). 1999. - Pp. 1202-1209.

38. Tseng D. C.; Chang C. H. Color segmentation using perceptual attributes // Proc. 11th International Conference on Pattern Recognition. — 1992. — Pp. 228-231.

39. Tremeau A., Borel N. A region growing and merging algorithm to color segmentation // Pattern Recognition. — 1997. — Vol. 30, no. 7. — Pp. 1191-1203.

40. Beucher S., Lantuéjoul C. Use of watersheds in contour detection // Proc. International Workshop on Image Processing, Real-Time Edge and Motion Detection/Estimation, Rennes. — 1979.

41. Roberts L. G. Machine perception of three-dimensional solids //In Optical and Electrooptical Information Processing, MIT Press, Cambridge, MA. — 1965.

42. Prewitt J. M. S. Object enhancement and extraction, in: B.S. Lipkin,A. Rosenfeld (Eds.), Picture Analysis and Psychopictorics. — New York: Aca-demicPress, 1970.

43. Rehrmann V., Priese L. Fast and robust segmentation of natural color scenes // Proceedings of the 3rd Asian Conference on ComputerVision (AC-CV'98), Hong Kong. Vol. 1. - 1998. - Pp. 598-606.

44. Carron T., Lambert P. Color edge detector using jointly hue, saturation and intensity // Proceedings of International Conferenceon Image Processing (ICIP'94), Austin, TX. Vol. III. - 1994. - Pp. 977-981.

45. Macaire L., Ultre V., Postaire J. G. Determination of compatibility coefficients for color edge detection by relaxation // International Conference on Image Processing. — 1996. — Pp. 1045-1048.

46. Rosenfeld A., Hummel R., Zucker S. Scene labeling by relaxation operations // IEEE Transactions on Systems, Man and Cybernetics. — 1976. — Vol. 6. Pp. 420-433.

47. Ma W. Y., Manjunath B. S. Edge flow: A framework of boundary detection and image segmentation // Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition (CVPR'97), Puerto Rico.—1997. Pp. 744-749.

48. Zugaj D., Lattuati V. A new approach of color images segmentation based on fusing region and edge segmentations outputs // Pattern Recognition. —1998. Vol. 31, no. 2. - Pp. 105-113.

49. Mumford D., J S. Boundary detection by minimizing functional // Proceedings of IEEE Internationall Conference on Computer Vision and Pattern Recognition (CVPR'85), San Francisco, CA, USA. 1985. - Pp. 22-26.

50. Koepfler G., Lopez C., Morel J. A multiscale algorithm for image segmentation by variational method // SI AM Journal of Numerical Analysis.— 1994. Vol. 31, no. 1. - Pp. 282-299.

51. Kass M., Witkin A., Terzopoulos D. Snakes: Active contour models // International Journal of Computer Vision. — 1988. — Vol. 1. — Pp. 321-331.

52. Gevers T., Ghebreab S., Smeulders A. Color invariant snakes // Proceedings of the 9th British Machine Vision Conference, Southampton, UK. — Vol. 2. — 1998. Pp. 578-588.

53. Pavlidis T., Liow Y. T. Integrating region growing and edge detection // IEEE Transactions Pattern Analysis Machine Intelligence. — 1990. — Vol. 12, no. 3. Pp. 225-233.

54. Shi J., Malik J. Normalized cuts and image segmentation // Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition, San Juan, Puerto Rico. — 1997. — Pp. 731-737.

55. Pedrycz W. Fuzzy sets in pattern recognition: methodology and methods // Pattern Recognition. — 1990. — Vol. 23, no. 1/2. Pp. 121-146.

56. Carron T., Lambert P. Fuzzy color edge extraction by inference rules quantitative study and evaluation of performances // International Conference on Image Processing. — 1995. — Pp. 181-184.

57. Cheng H. D., Jiguang L. Fuzzy homogeneity and scale-space approach tocolor image segmentation // Pattern Recognition. — 2003. — Vol. 36, no. 7. — Pp. 1545-1562.

58. Moghaddamzadeh A., Bourbakis N. A fuzzy region growing approach for segmentation of color images // Pattern Recognition. — 1997. — Vol. 30, no. 6. — Pp. 867-881.

59. Campadelli P., Medici D., Schettini R. Color image segmentation using hop-field networks // Image and Vision Computing. — 1997.— Vol. 15, no. 3.— Pp. 161-166.

60. Kurugollu F., Sankur B. Map segmentation of color images using constraint satisfaction neural network // IEEE International Conference on Image Processing, KOBE, Japan. 1999. — Pp. 236-239.

61. Lin W. C., Tsao E. C., Chen C. T. Constraint satisfaction neural networks for image segmentation // Pattern Recognition. — 1992.— Vol. 25, no. 7.— Pp. 679-693.

62. Verikas A., Malmqvist K., Bergman L. Colour image segmentation by modular neural network // Pattern Recognition Letters. — 1997. — Vol. 18, no. 2. — Pp. 173-185.

63. Ji S., Park H. W. Image segmentation of color image based on region coherency // International Conference on Image Processing, Chicago, Illinois, USA. 1998. - Pp. 80-83.

64. Klinker G. J., Shafer S. A., Kanade T. A physical approach to color image understanding // International Journal Computer Vision. — 1990. — Vol. 4. — Pp. 7-38.

65. Segmentation of colour images with highlights and shadows using fuzzy-like reasoning / X. Yuan, D. Goldman, A. Moghaddamzadeh, N. Bourbakis // Pattern Analysis and Applications. — 2001. — Vol. 4. — Pp. 272-282.

66. Baird H. S. The state of the art of document image degradation modeling // Digital Document Processing / Ed. by B. B. Chaudhuri. — Guildford,Surrey,UK: Springer-Verlag, 2007.

67. Rosenfeld A., Kak A. C. Digital Picture Processing. — New York: Academic Press, 1982.

68. Vincent L., Soille P. Watersheds in digital spaces: An efficient algorithm based on immersion simulation // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 1991. — Vol. 13, no. 6. — Pp. 583-598.

69. Meyer F. Topographic distance and watershed lines // Signal Processing. — 1994. Vol. 38. - Pp. 113-125.

70. Roerdink J., Meijster A. The watershed transform: Denitions, algorithms and parallelization strategies // Fundamenta Informati-cae. 2001. - Vol. 41. - Pp. 187-228.

71. Lantuejoul C., Maisonneuve F. Geodesic methods in quantitative image analysis // Pattern Recognition. — 1984. — Vol. 17. — Pp. 177-187.

72. Beucher S., Meyer F. The Morphological approach of segmentation: the watershed transformation, In Dougherty E. (Editor), Mathematical Morphology in Image Processing. — New York: Marcel Dekker, 1992.

73. Serra J. Image Analysis and Mathematical Morphology. — New York: Academic Press, 1982.

74. Bergholm F. Edge focusing // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 1987. — Vol. 9, no. 6. — Pp. 726-741.

75. Williams D. J., Shas M. Edge contours using multiple scales // Computer Vision, Graphics and Image Processing. — 1990. — Vol. 51. — Pp. 256-274.

76. Lacroix V The primary raster: A multiresolution image description //In Proceedings of the 10th International Conference on Pattern Recognition. — 1990. Pp. 903-907.

77. Canny J. F. A computational approach to edge detection // IEEE Transactions on Pattern Analysis and Machine Intelligence.— 1986.— Vol. 8, no. 6. Pp. 679-698.

78. Ziou D., Tabbone S. A multi-scale edge detector // Pattern Recognition.— 1993. Vol. 26, no. 9. - Pp. 1305-1314.

79. Lindeberg T. Edge detection and ridge detection with automatic scale selection //In Proceedings of IEEE, International Conference on Computer Vision and Pattern Recognition, San Francisco. — 1996. — Pp. 465-470.

80. Koenderink J. The structure of images // Biological Cybernetics. — 1984. — Vol. 50. Pp. 363-370.

81. Uniqueness of the gaussian kernel for scale-space filtering / J. Babaud, A. P. Witkin, M. Baudin, R. O. Duda // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 1986. — Vol. 8, no. 1. — Pp. 26-33.

82. Lindeberg T. Scale-Space Theory in Computer Vision. — Kluwer, 1994.

83. White J. M., D R. G. Image thresholding for optical character recognition and other applications requiring character image extractraction // IBM J. Res. Devel. — 1983. — Vol. 27, no. 4.- Pp. 400-411.

84. Di Zenzo S. A note on the gradient of a multi-image // Computer Vision, Graphics, and Image Processing. — 1986. — Vol. 33. — Pp. 116-125.

85. Sharma G. Digital Color Imaging Handbook, Chapter 7. — BocaRaton, FL: CRC Press, 2003. Pp. 491-558.

86. Brunner D., Soille P. Iterative area filtering of multichannel images // Image and Vision Computing. — 2007. Vol. 25, no. 8. — Pp. 1352-1364.

87. Baraldi A., Parmiggiani F. Single linkage region growing algorithms based on the vector degreeof match // IEEE Transactions on Geoscience and Remote Sensing. — Vol. 34, no. 1. — Pp. 137-148.

88. Meyer F., Beucher S. Morphological segmentation // Journal of Visual Communication and Image Representation. — 1990. — Vol. 11. — Pp. 21-45.

89. On machine learning in watershed segmentation / S. Derivaux, S. Lefevre, C. Wemmert, J. Korczak // IEEE Workshop on Machine Learning for Signal Processing. — 2007.

90. Najman L., Schmitt M. Geodesic saliency of watershed contours and hierarchical segmentation // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1996. — Vol. 18, no. 12. - Pp. 1163-1173.

91. Trier 0. D., Jain A. K. Goal-directed evaluation of binarization methods // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 1995. — Vol. 17, no. 12.- Pp. 1191-1201.

92. Classification and Regression Trees / L. J. Breiman, H. Friedman, C. J. Stone, R. A. Olshen. — Belmont, CA: Wandsworth, Inc., 1984.

93. Niblack W. An Introduction to Digital Image Processing. — Englewood Cliffs, N. J.: Prentice Hall, 1986. Pp. 115-116.

94. Adaptive document binarization / J. Sauvola, T. Seppanen, S. Haapakos-ki, M. Pietikainen // International Conference in Document Analysis and Recognition. Vol. 1. - 1997. - Pp. 147-152.

95. Insight segmentation and registration toolkit, http://www.itk.org.

96. Comaniciu D., Meer P. Mean shift: A robust approach toward feature space analysis // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2002. — Vol. 24. — Pp. 603-619.

97. Edge detection and image segmentation (edison) system, http : //www. caip. rutgers.edu/riul/research/code/EDISON/index.html.