Содержание к диссертации
Введение
Глава 1. Обзор методов сегментации цветных изображений . 10
1.1. Представление цветовых характеристик точек изображения . 11
1.2. Методы, основанные на анализе гистограмм изображений . 14
1.3. Методы кластерного анализа 19
1.4. Методы роста регионов 21
1.5. Методы, основанные на определении границ областей 24
1.6. Методы, использующие элементы вариационного анализа, теории графов 27
1.7. Методы, использующие элементы теории нечётких множеств . 30
1.8. Методы, использующие искусственные нейронные сети 32
1.9. Методы, использующие физические модели освещения объектов и отражения объектами света 35
Глава 2. Сегментация цветных изображений 37
2.1. Постановка задачи диссертационной работы 37
2.2. Основные определения, сегментация методом водоразделов . 40
2.3. Общая схема работы предлагаемого метода сегментации . 45
2.4. Многомасштабный анализ линейных срезов 48
2.5. Вычисление аппроксимирующей производной линейных срезов 56
2.6. Определение внутренних областей объектов малого размера . 64
2.7. Модификация преобразования водоразделов 70
Глава 3. Анализ цветных изображений документов 80
3.1. Классификация объектов изображения 82
3.2. Бинаризация внутрифоновых областей 84
3.3. Вычислительная сложность алгоритма 87
3.4. Практические результаты и обсуждение 89
Заключение 91
Приложение А 93
Литература 104
- Представление цветовых характеристик точек изображения
- Методы, основанные на анализе гистограмм изображений
- Постановка задачи диссертационной работы
- Классификация объектов изображения
Введение к работе
Сегментацией называется разбиение изображения на прилегающие друг к другу области, которые являются однородными относительно некоторых характеристик изображения. Сегментация изображений является неотъемлемой частью зрительного восприятия человека. Человек, в своей повседневной жизни, эффективно разделяет свое визуальное окружение на объекты, которые он в дальнейшем распознает, контролирует их движение и т.д. В этом сложном процессе учитывается множество визуальных характеристик объектов — цвет, форма, движение, текстура. Однако для зрительной системы человека сегментация является естественным и спонтанным процессом. К сожалению, реализовать алгоритмы сегментации, чья эффективность работы была бы сравнима с эффективностью работы зрительной системы человека, далеко не простая задача. Сложность процессов, происходящих в зрительной системе человека при сегментации, часто недооценивается, возможно, потому, что большинство из них происходят на подсознательном уровне.
Сегментация является, как правило, первым этапом в работе систем анализа изображений и, возможно, самым важным и сложным. Все последующие этапы анализа изображений, такие как извлечение признаков или распознавание объектов, напрямую зависят от качества сегментации. Так, излишне сегментированное изображение может привести к разделению распознаваемого объекта на части, а недостаточно сегментированное изображение — к группировке различных объектов.
В последние годы появляется все больше прикладных областей, в которых актуально применение методов сегментации изображений — это системы распознавания документов, мультимедийные базы данных, передача видео через сеть Интернет, цифровая фотография, сжатие изображений и другие. Особенно велик интерес исследователей к сегментации цветных изображений,
так как цветное изображение несёт значительно больше информации, чем полутоновое. Известно, что человеческий глаз в состоянии различать одновременно лишь небольшой интервал яркости — данное явление известно в психофизиологии зрения как «адаптация к освещённости» — но, в то же время, воспринимает тысячи цветовых оттенков [1]. Бурное развитие вычислительной техники, а именно, повышение быстродействия и объёмов хранения оперативной информации, позволяет увеличить скорость обработки изображений и перейти к обработке в реальном времени не только полутоновых, но и цветных изображений, требующих анализа большего количества информации.
Представленные в литературе работы по сегментации изображений посвящены, главным образом, сегментации полутоновых изображений [2-4]. Методы сегментации полутоновых изображений в общем случае не позволяют получить удовлетворительные результаты при применении их к цветным изображениям, так как в данных методах рассматривается только уровень яркости точек изображения и не учитываются цветовые (хроматические) характеристики точек.
Все вышесказанное показывает, что разработка эффективных методов сегментации цветных изображений является актуальной задачей.
Одной из прикладных областей, в которых традиционно применяется сегментация изображений, являются системы анализа изображений документов. Эта категория интеллектуальных систем включает в себя как задачи распознавания текста, так и задачи определения макета (layout) и графических элементов страниц документа. Неотъемлемой частью таких систем является процесс сегментации изображения. Как правило, данные системы ориентированы на обработку полутоновых изображений, и для сегментации в них используются методы бинаризации или порога (thresholding) [8]. Целью бинаризации является разделение точек изображения, путём определения разде-
ляющего значения яркости, на два класса: на точки, принадлежащие фону и точки, принадлежащие объектам изображения. Порог яркости может определяться как один для всего изображения, тогда такой метод называют глобальным, так и для разных областей изображения могут определяться различные пороги, тогда такие методы называют адаптивными. Однако, при сегментации полутоновых изображений как глобальный, так и адаптивный методы бинаризации не всегда могут быть эффективны. Например, если в соседних частях изображения яркость фона и объектов инвертирована относительно друг друга или во внутренней области фона яркость плавно меняется. Ошибки сегментации в данных случаях являются следствием основного принципа бинаризации, который предполагает, что яркость всех объектов, для изображения в целом (глобальный подход) или в конкретной области (адаптивный подход), больше некоторого порога яркости, а яркость фона ниже этого порога. По этой же причине — принципу разделения точек изображения на две группы по уровню яркости — бинаризация работает неэффективно при обработке цветных изображений, так как для успешной сегментации цветного изображения, кроме уровня яркости, необходимо учитывать и хроматические характеристики точек.
Перечислим некоторые характерные особенности цветных изображений печатных документов. Как правило, такие изображения содержат как объекты малого размера (буквы, цифры и другие символы), так и объекты, размеры которых значительны по сравнению с размером страницы (фоны, таблицы, логотипы, иллюстрации) (рис. 1). Границы между соседними объектами могут быть как резкими (рис. 2а), то есть, фактически не иметь толщины, так и плавными (рис. 26), и иметь некоторый поперечный размер. Причём, размер малых объектов на изображении порой сопоставим с размерами плавных границ между большими объектами. Иногда на изображениях документов встречается градиентный фон, то есть фон, цвет которого плавно
—
fe
Рис. 1. Примеры цветных изображений страниц журналов (масштаб 1:3).
изменяется в плоскости изображения (рис. 2в). Все перечисленные особенности изображений документов могут приводить к ошибкам сегментации при обработке изображения стандартными методами сегментации цветных изображений. Подробный анализ существующих методов сегментации цветных изображений выполнен в первой главе данной работы.
Целью диссертационной работы являлась разработка эффективного метода сегментации цветных изображений печатных документов. В соответствие с целью исследования были определены задачи качественной сегментации следующих объектов цветных изображений документов: сплошных и градиентных фонов многостатейного документа, символов основного текста статей, заголовков, буквиц, многострочных таблиц, содержимого таблиц, графических элементов документа.
Научная новизна работы обусловлена впервые предложенными методами обработки цветных изображений — методом многомасштабной сегментации линейных срезов изображения, методом определения внутренних областей 7
There's always a copy
available with
OnlineBooks
ifffllilTTT
Рис. 2. Примеры резкой (а) и плавной (б) границ, разделяющих однородные цветовые области; (в) градиентного фона.
объектов малого размера и модификацией метода водоразделов.
Практическая значимость работы заключается в широких возможностях применения разработанного метода сегментации цветных изображений документов. Предлагаемый метод может использоваться как самостоятельное средство сегментации, так и применяться в составе систем обработки и анализа цветных и полутоновых изображений документов, например, в OCR-системах, системах сжатия изображений. Кроме того, совокупность методов, представленных во второй главе данной работы, является законченным методом сегментации произвольных цветных изображений и может использоваться в различных интеллектуальных системах компьютерного зрения.
Основные результаты диссертации докладывались на следующих международных конференциях: 17"' International Conference on Pattern Recognition ICPR2004 (Cambridge, UK); 3rd IASTED International Conference on Visualization, Imaging, and Image Processing (Benalmadena, Spain); международной конференции студентов и аспирантов по фундаментальным наукам «Ломоносов-2004», и опубликованы в работах [9-14].
Диссертационная работа включает в себя 3 главы, введение и заключение.
Первая глава содержит обзор литературы по методам сегментации цветных изображений. Вторую главу открывает постановка задач данной дисертаци-онной работы, за которой следует общее описание предлагаемого метода и подробное теоретическое описание его этапов, совокупность которых представляет собой законченный метод сегментации произвольных цветных изображений. В третьем разделе описывается приложение разработанного метода к обработке цветных изображений документов, реализация предлагаемого алгоритма и проводится анализ полученных практических результатов. В заключении представлены основные результаты диссертационной работы. Завершает диссертационную работу список используемой литературы, включающий 96 наименований. Диссертационная работа содержит 25 иллюстраций.
Представление цветовых характеристик точек изображения
Практически каждый алгоритм сегментации базируется на определённом представлении цветовых характеристик точек (пикселей) исходного изображения, которое используется, в зависимости от типа алгоритма, для вычисления меры их сходства или различия. Существует несколько вариантов представления цветовых характеристик, выражающихся, как правило, в выборе типа цветового пространства, в котором измеряются цветовые свойства точек изображения. Одно из цветовых пространств, наиболее часто используемое при обработке цветных изображений, — пространство RGB. Цвет в данном пространстве представлен в виде компонент красного (red), зелёного (green) и синего (blue) цветов, что согласовывается с представлениями о восприятии цветов зрительной системой человека [15]. Известно, что в сетчатой оболочке человеческого глаза — ретине, находятся три вида фоторецепторов, называемых колбочками, чувствительных к световым волнам определённой длины — лучам красного, зелёного и синего цвета соответственно. Также известно, что любой цвет возможно получить путём смешивания, в определённых пропорциях, лучей трёх основных цветов. Геометрически цветовое пространство RGB можно представить как трёхмерный куб. Координаты каждой точки внутри куба задаются значениями трёх основных компонент — красной, зелёной и синей соответственно. Однако представление цвета как суммы компонент красного, зелёного и синего цветов различной интенсивности, не соответствует последующим уровням обработки информации в зрительной системе человека. С этой точки зрения более естественным является представление цветовых характеристик в терминах цвета, насыщенности и яркости.
Примером такого представления цветовых характеристик является пространство HSI (Hue, Saturation, Intensity), которое может быть получено из „ » ( УЦв-В) \ . R + G + B . min(R,G,B) H = Ct{(R-G) + (R-B))-I = 3 S=1 1 Тон (Hue) и насыщенность (Saturation) определяют хроматическую ин-4 ормацик , в то время как яркость (Intensity) является мерой освещённости. Геометрически цветовое пространство HSI представлено в виде цилиндрической координатной системы. Значение тона (Hue) точки в данном цветовом пространстве определяется как угол между нулевой осью, обычно задаваемой направлением красного цвета, и проекцией на плоскость, перпендикулярную оси яркости (Intensity), которая является осью цилиндра. Значение насыщенности (Saturation) вычисляется как радиальное расстояние от оси цилиндра (оси яркости) до точки. И, наконец, значение яркости (Intensity) определяется как расстояние от основания цилиндра до точки. Цветовое пространство HSI удобно для применения во многих случаях. Так, полутоновые алгоритмы могут быть без изменений применимы к цветному изображению, если они будут рассматривать только одну компоненту цветовых характери-12 стик точек — компоненту яркости (Intensity). Во многих случаях сегментация может быть успешно выполнена при рассмотрении только компоненты тона (Hue) и компоненты насыщенности (Saturation), игнорируя компоненту яркости (Intensity), так как известно, что внутренние точки изображения реальных объектов, которые имеют различную степень освещения вдоль поверхности, различаются по значению яркости, но сходны по значениям хроматических компонент (Hue,Saturation). Один из недостатков представления цветовой информации в пространстве HSI — нестабильность значений цвета при малых значениях насыщенности и яркости, то есть, около оси цилиндра, представляющего пространство HSI. Так небольшие изменения во входных данных, представленных в системе RGB, могут значительно изменить значение компоненты тона (Hue) в системе HSI.
Существенным недостатком пространств RGB и HSI является то, что данные пространства не являются зрительно однородными, это означает что, к примеру, две пары цветов, различия между которыми воспринимаются человеческим глазом как примерно одинаковые, могут иметь значительно различающиеся расстояния между точками, представляющими эти цвета в цветовом пространстве. Данная проблема была практически разрешена после представления Международной Комиссией по Освещению (CIE — Communication Internationale de l Eclairage) зрительно однородных цветовых пространств, наиболее распространёнными из которых являются CIE L a b и CIE L u v . Преобразования в данные пространства осуществляются через промежуточный этап, на котором с помощью линейных преобразований подсчитываются значения основных цветовых составляющих, названных X,Y и Z. Дальнейшие же преобразования в системы CIE L a b и CIE L u v являются нелинейными.
Так как пространства CIE L a b и CIE L u v также являются трёхмерными, то мы можем определить разницу между двумя цветами как евклидово расстояние между точками, представляющими данные цвета в цветовом пространстве. Возможность выразить различия между двумя цветами, воспринимаемыми человеческим глазом, в виде цифрового значения евклидова расстояния между точками в трёхмерном цветовом пространстве, является важным фактом, который широко используется в алгоритмах сегментации изображений.
Методы, основанные на анализе гистограмм изображений
В литературе, посвященной теме сегментации полутоновых изображений, широко распространены методы, основанные на анализе гистограмм изображений. Аналогичные методы разработаны и для сегментации цветных изображений. Гистограмма полутонового изображения отображает для каждого значения полутона количество соответствующих точек на изображении. В простейшем случае, когда изображение содержит некий объект и фон, отображаемые различными полутонами, гистограмма имеет ярко выраженные максимумы (в литературе — пики гистограммы») около средних значений полутонов объекта и фона. Обычно решение задачи сегментации для такого случая сводится к нахождению значения полутона, который делит ось полутонов гистограммы на два интервала: первый, соответствующий значениям полутонов точек объекта, и второй, соответствующий значениям полутонов точек фона. В случае, когда на изображении предполагается наличие п однородных областей разного цвета (оттенка серого), то решение задачи сегментации сводится к разделению оси полутонов на п интервалов, или, что аналогично, нахождению п максимумов или, так называемых «пиков» гистограммы, соответствующих конкретным объектам на изображении.
Гистограмма цветного изображения также отображает количество точек на изображении для каждого значения цвета. Такую гистограмму сложно представить визуально, так как она является четырёхмерной — одно измерение соответствует оси количества точек, а три оставшиеся — осям компонент цвета. К данной гистограмме также применимы методы, используемые для полутоновых изображений, с той лишь разницей, что в данном случае вместо разделения оси полутонов на интервалы решается задача разделения цветового пространства на области.
Рассмотрим, представленные в литературе по анализу изображений и распознаванию образов методы сегментации цветных изображений, основанные на анализе гистограмм изображений. Гуо и др. [16] разделяют цветовое пространство на кубические ячейки малого размера. Для каждой ячейки под-считывается количество попавших в неё точек изображения. Далее, ячейки, в которых количество точек превышает некий заранее заданный порог, помечаются как принадлежащие к «пикам» гистограммы, то есть, относящиеся к цветам значимых объектов, представленных на изображении. Остальные ячейки помечаются как ячейки, относящиеся к «долинам» гистограммы, то есть, соответственно, к цветам, не относящимся к цветам значимых объектов, представленных на изображении. Далее, касающиеся друг друга ячейки «пиков», объединяются в пространственные области, и на изображении выделяются относящиеся к ним точки, т.е. точки, цвет которых принадлежит данной пространственной области. Таким образом, осуществляется разбиение изображения на области.
Шафаренко и др. [17] применяют алгоритм преобразования водоразделов (watershed algorithm) для анализа гистограммы изображения. Авторы предлагают два алгоритма сегментации: первый, работающий с двухмерной (включающей только хроматические оси) гистограммой изображения, и второй - работающий с трёхмерной гистограммой. Выбор алгоритма осуществляется в зависимости от области применения метода — в тех случаях, когда области одного цвета, имеющие различную яркость не следует трактовать как отдельные области, может использоваться первый метод, в противном случае — второй. Первоначально к гистограммам применяется сглаживающий фильтр, позволяющий снизить уровень шума и получить гистограмму, которая максимально соответствует человеческой способности к различению цветов: другими словами, два пика близких значений цветов на гистограмме должны быть сглажены в один, если человеческий глаз не способен воспринимать их как различные цвета. На следующем этапе к полученной гистограмме применяется алгоритм водоразделов, позволяющий разделить гистограмму на интервалы, соответствующие сегментируемым областям на исходном изображении.
Многие исследователи рассматривают отдельно гистограммы, построенные для трёх осей цветового пространства, а затем различным образом совмещают полученные результаты. Так, Целенк [18] рассматривает отдельно каждую из гистограмм осей R,G,B соответствующего цветового пространства и выделяет на гистограммах интервалы, на которых количество точек превышает некий, определённый заранее, количественный порог.
Постановка задачи диссертационной работы
Анализ работ по теме сегментации цветных изображений показывает, что среди представленных в литературе методов отсутствуют методы, обладающие одновременно следующими характеристиками, критичными для процесса обработки цветных изображений документов: возможностью сегментации объектов, имеющих как резкие так и плавные границы; точностью сегментации как объектов, чей размер значителен по отношению к размеру изображения, так и объектов малого размера; возможностью сегментации объектов с градиентной внутренней областью.
Задачей данной диссертационной работы являлось разработка метода сегментации цветных изображений, обладающего вышеперечисленными характеристиками.
Определим формальную постановку задачи диссертационной работы. Для этого первоначально дадим определение понятия связного множества точек изображения.
Определение. Множество точек изображения F называют связным, если любые две точки этого множества fi и fj можно соединить прямой или ломаной, проходящей только через точки, принадлежащие данной области.
Далее, будем называть связное множество точек изображения связной областью. А связными областями будем называть множество областей, каждая из которых является связной, и объединение которых также является связным множеством точек изображения.
Теперь дадим определение сегментации изображения [4].
Определение. Пусть F - множество всех точек изображения. Р() - предикат однородности, заданный для связанной области. Сегментацией называется разделение множества F на множество связных областей {5i, S2, -, Sn], такое, что 1. U Si F и SiDSj = (/),1 j 2. VSi,P(Si) = TRUE 3. P(Si U Sj) = FALSE, если Si и Sj граничат друг с другом.
Напомним, что предикатом называется функция, принимающая значение ИСТИНА (TRUE) в случае выполнения условия, соответствующего данному предикату. Первое условие определения сегментации говорит о том, что множество сегментированных областей должно покрывать всю плоскость изображения. Второе говорит о том, что каждая сегментированная область удовлетворяет условию предиката однородности области Р(). И, третье условие, говорит о том, что область, получаемая слиянием любых двух граничащих областей, не может удовлетворять условию предиката однородности.
Формальное определение предиката однородности области практически невозможно по причине того, что задача сегментации изображения является феноменом психофизического восприятия и не имеет точного аналитического решения [3]. Под однородностью области понимается однородность относительно заданных характеристик изображения [2]. В данной работе однородность областей будет рассматриваться относительно цветовых характеристик точек изображения. Кроме того, область, в которой происходит плавное из менения цвета в плоскости изображения, также будет рассматриваться как однородная.
Рассмотрим исходную идеальную версию цветного изображения документа, существующую до выполнения процессов печати и перевода в новую цифровую версию изображения посредством сканирования. Данная версия исходного изображения описывается непрерывной векторной функцией, определённой в плоскости изображения С (я;,у):М2 М3, где К3 представляет собой конкретное цветовое пространство (RGB, HSI, ...). Будем считать, что в областях {Si,S2,.--,Sn}, соответствующих следующим объектам изображения — фонам, символам основного текста, буквицам, графическим элементам (исключая иллюстрации) — данная функция либо принимает постоянное значение V&, VpJ = (яо,Уо), Vpl = (хі,у\) : Щ,рї Є Sit CoHfl(po) = С рї), (2.1) либо градиенты всех компонент данной векторной функции постоянны Vfif,Vpo = Ы,Уо),Ш = (яі,3/і) : Ро,Ш Є Shgrad{C ig){щ) = grad{C ig)(pl) (2.2) и их модули не превышают заранее заданное пороговое значение Tgrad Ij2(9d(clig)(m)y Tgrad, (2.3) где к = {1,2,3} — компоненты пространства М3. Таким образом, предикат однородности Р( %) области Si принимает значение TRUE при выполнении условия 2.1 или условий 2.2-2.3, и значение FALSE при нарушении данных условий.
Классификация объектов изображения
Целью классификации объектов изображения является определение фонов статей для дальнейшего выполнения в их внутренней области бинаризации, исключая, при этом, из области фона объекты, не относящиеся к символам основного текста статей. Для выполнения классификации на основе анализа нескольких десятков реальных изображений было разработано дерево решения [91], разбивающее все объекты изображения на три класса: фоны (класс BACKGROUND), символы основного текста (класс CHARACTER) и все остальные объекты изображения (класс OTHER). Характеристиками объектов, используемыми при классификации, были выбраны площадь объекта и количество других объектов во внутренней области рассматриваемого объекта.
Указанное дерево решений было построено с помощью алгоритма CART [91. Данные для обучения выбирались на основе 50-ти произвольно выбранных цветных изображений документов. После сегментации указанных изображений было выбрано и обработано (назначен класс объекта) около 3000 объектов и на их основе была составлена обучающая выборка. Данная выборка содержала для каждого объекта его класс, значение площади и количество внутренних объектов.
Построенное дерево решений для классификации объектов изображения приведено на рис. 3.2. Верхний уровень дерева разделяет по значению площади класс символов основного текста и остальные классы. Это объясняется тем, что фоны статей, буквицы и заголовки, как правило, имеют значительно большую площадь, по сравнению с площадью букв основного текста. Следующий уровень дерева разделяет фоны и другие объекты изображения. Дей ствительно, фоны статей практически всегда содержат большое количество объектов, в отличие от буквиц и букв заголовков. Разделяющие значения площади объектов и количества внутренних объектов, вычисленные при автоматическом создании дерева решений, оказались равными ST = 30мм2 и Ст = 4, соответственно.
Для проверки эффективности работы полученной модели классификации была составлена выборка для тестирования, построенная аналогично обучающей выборке. При тестировании указанной модели классификации ошибочных случаев классификации объектов зафиксировано не было.
Предварительно, перед выполнением бинаризации во внутренней области объектов изображения, классифицированных как фоны, необходимо преобразовать внутреннюю область каждого фона, включая символы основного текста, в полутоновое изображение. Так как характеристикой точки на полутоновом изображении является скалярная величина, то данное преобразование может быть определено как отображение точек трехмерного цветового пространства на прямую, вдоль которой варьируется значение полутона. Очевидно, что для эффективного выполнения бинаризации данное преобразование должно являться проекцией цветов пикселей изображения области бинаризации в трехмерном цветовом пространстве на прямую, вдоль которой происходит максимальное изменение цветов пикселей. Данная прямая может быть приближённо определена как прямая, проведённая через две точки цветового пространства — точку среднего цвета пикселей фона Мв и точку суммарного среднего цвета пикселей букв основного текста Мр (рис. 3.3).
Рассмотрим произвольный фон и содержащиеся в нем символы основного текста. Выполнив проецирование цветов точек фона и символов основного текста на вышеупомянутую ось, возможно определить крайние точки отрезка [i?,W], на который проецируются цвета всех пикселей данных объектов. Преобразование области фона и букв основного текста из цветного в полутоновое изображение можно определить как проекцию точек цветов на отрезок [Оі,Ог]. Пикселям изображения, спроецированным на концы отрезка будут назначены черный (точка В) и белый (точка W) цвета, а точкам, спроецированным во внутреннюю область отрезка — соответствующие промежуточные цвета. Каждому фону и его внутренним объектам будет соответствовать своё преобразование, так как вид преобразования зависит от цветовых характеристик точек данных объектов.
