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

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

Рейер Иван Александрович

МЕТОДЫ АНАЛИЗА ФОРМЫ ИЗОБРАЖЕНИЙ НА ОСНОВЕ НЕПРЕРЫВНОГО ГРАНИЧНО-СКЕЛЕТНОГО ПРЕДСТАВЛЕНИЯ

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

Москва - 2004

Работа выполнена в Вычислительном центре имени А.А. Дородницына Российской академии наук.

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

доктор технических наук, профессор Л.М. Местецкий

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

доктор физико-математических наук, профессор В.Н. Козлов доктор технических наук, профессор В.В. Моттль

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

Институт радиотехники и электроники Российской академии наук

Защита состоится "_"_2004 г. в_часов на заседании

диссертационного совета Д002.017.02 Вычислительного центра имени А.А. Дородницына РАН по адресу: 119991, Москва, ГСП-1, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке Вычислительного центра имени А.А. Дородницына РАН.

Автореферат разослан "_"_2004г.

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

д.ф.-м.н.

В.В. Рязанов

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

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

Анализ формы изображения включает в себя два этапа: собственно выделение формы объекта и составление его признакового описания. Для выделения формы используются различные методы обработки изображений. Результатом их применения является растровое бинарное изображение, представляющее собой силуэт объекта (рис. 1а). Это изображение является исходным для получения признакового описания формы объекта. Методы составления такого описания являются предметом настоящего исследования.

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

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

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

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

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

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

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

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

построения и анализа границы, и скелета (включающих до 104-105 элементов) в системах реального времени.

Предлагаемое решение задачи основывается на следующем подходе:

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

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

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

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

Новые научпые результаты, выносимые на защиту: • метод построения скелетного представления с контролируемой точностью аппроксимации. Известные методы строят скелетное представление по эвристическим правилам, что не позволяет однозначно определить скелет и оценить точность представления. В отличие от них предлагаемый метод позволяет корректно определить "базовый скелет", аппроксимирующий образ с заданной точностью;

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

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

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

Предлагается метод сравнения изображений на основе гомеоморфного преобразования контуров. В заключении подводятся итоги работы. Диссертация содержит 121 страницу машинописного текста, 77 рисунков. Список литературы включает 115 наименований.

Апробация. Представленные в работе результаты докладывались и обсуждались на 9-й, 10-й и 11-й всероссийских конференциях "Математические методы распознавания образов"; 9-й, 10-й и 13-й международных конференциях по компьютерной графике и машинному зрению "Графикой"; международных конференциях "Интеллектуализация обработки информации - 2000" и "Интеллектуализация обработки информации - 2002"; 5-й международной конференции "Распознавание образов и анализ, изображений"; 8-й международной конференции "International Workshop on Frontiers in Handwriting Recognition"; научных семинарах отдела вычислительных методов прогнозирования Вычислительного центра им. А.А. Дородницына РАН; научно-исследовательском семинаре департамента информатики университета г. Йоэнсуу (Финляндия).

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

Внедрение результатов. Выносимые на защиту методы были реализованы, исследованы и использованы для решения прикладных задач в ходе работ по проектам Российского Фонда фундаментальных исследований (РФФИ) 99-01-00829 "Методы распознавания формы объектов на основе морфинга изображений"; 02-01-00667 "Дискретно-непрерывные преобразования формы геометрических объектов в задачах обработки и анализа изображений"; а также по гранту Американского Фонда гражданских исследований и развития (CRDF) RM2-2245 "Computer-assisted querying of digitazed handwritten archives". Методы построения скелетного представления с контролируемой точностью

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

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

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

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

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

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

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

Определение 1: Скелетным £-ядром множества областей Мназывается множество всех точек xeR2 таких, что для любой области

евклидово расстояние от. точки х до скелета области ц, с1{х,скелет¿1), не превышает £, т.е.

Пусть Р - некоторая полигональная область, а е - некоторое положительное число.

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

Определение 3: Нормальная область Л называется Л-близкой нормальной области если выполнены следующие условия:

1) хаусдорфово расстояние между областями Ли £2', ЩС^П1) <е,

2) хаусдорфово расстояние между границами областей, ЩбО.дЛ') <е.

Определение 4: ^-коридором области Р называется замкнутая е-окрестность границы области.

Определение 5: ¿-расширением Ре+ полигональной области Р (рис. 2а) называется объединение Р и 1-коридора Р.

а)

б)

Рис.2.

Ре+ =Р II {£ - коридор Р}.

Пусть а - выпуклый угол полигональной области Р, р - вершина этого угла, В - биссектриса этого угла. Рассмотрим а - точку на В, удаленную от вершины угла р на Е, и Ь - точку пересечения прямых, параллельных сторонам угла и находящихся на расстоянии от сторон угла (рис. 26).

Определение 6: отрезок аЬ называется шипом Ба выпуклого угла а.

Определение 7: ^-сужением Ре _ полигональной области Р (рис. 2а) называется объединение разности области Р и ¿'-коридора Р с шипами всех выпуклых углов Р.

Ре- =(Р\{е- коридор Р}) У

и

[аеСопс(,Р)

где - множество всех выпуклых углов Р.

Рис. 3.

Определение 8: круг С будем называть ^-допустимым кругом для Р, если: (1) Н(Р,РЦС)йе\(2) ЩдРшд(,Р\)С))£в.

Определение 9: круг С будем называть максимальным ^-допустимым кругом для Р (рис. За), если: (1) С является ¿-допустимым кругом для Р; (2) С не содержится целиком ни в каком другом е-допустимом для Р круге. Доказаны следующие утверждения.

Утверждение!: Если С=(р,г) - максимальный Г-допустимый круг для Р, то С'=(р,г-е) - максимальный круг для Р.

Утверждение 2: Если С=(р,г) — максимальный круг для Р, то С'=(р,г+е) - максимальный 1-допустимый круг для Р. Следствием этих утверждений является следующая Теорема 1: Множество центров максимальных ¿-допустимых кругов для Р совпадает со множеством центров максимальных кругов для Р.

Определение 10: круг С будем называть базовым кругом для полигональной области Р, если выполнено следующее: (1) С является максимальным ¿-допустимым кругом для Р; (2) пересечение С с Р- не содержится целиком ни в одном максимальном для Р круге,

не совпадающем с кругом С.

Определение 11: множество центров всех базовых кругов для Р будем называть базовым скелетом Р и обозначать

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

Рассмотрим С~(р,г) - произвольный базовый круг для Р радиуса г с центром в точке р. С этим кругом связан круг С'=(р,г—е), который является максимальным для Р и касается границы Р по крайней мере в двух точках (рис. 36). Пусть круг С' касается границы Р в точках А и В. Рассмотрим проходящие через А и В радиусы круга С,рА+ ИрВ*. Доказаны следующие

Теорема 2: Скелет произвольной ¿-близкой Р области П пересекает хотя бы один из радиусов

Теорема 3: Точка пересечения скелета произвольной ¿-близкой Р области с одним из радиусов базового круга С удалена от

центра круга/) не более чем на

е/сов 2(а /2),

где а - угол между сторонами полигональной области, которых касается круг С'=(р,г-е).

Теоремы 2 и 3 позволяют сделать следующие выводы о свойствах базового скелета. Для каждого ребра базового скелета существует некоторое 5 >£, такое, что в ^окрестности ребра находятся точки скелета любой ¿-близкой Р области. Следовательно, это ребро базового скелета принадлежит скелетному &ядру множества ¿-близких Р областей и это ядро не является пустым множеством. Если же взять <5^ - максимальное из всех таких то получим, что базовый скелет принадлежит скелетному ¿^пах-ядру множества ¿-близких Р областей. Кроме того, через 5-окрестность каждого ребра базового скелета для любой Р

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

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

Базовый круг С с центром на бисекторе пары сайтов, образующей выпуклый угол, не должен иметь пересечений с ¿-окрестностью вершины угла, то есть должен пересекать соответствующий шип. В противном случае он не был бы базовым, так как нашелся бы другой для Р круг, содержащий пересечение С с /V (рис. 4а). Соответственно, возникает следующая идея построения базового скелета. Выберем одну из терминальных вершин скелета и начнем движение по инцидентному этой

вершине ребру вглубь области, "стирая" ребро. При этом мы рассматриваем поведение максимального круга, центр

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

Рис. 4.

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

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

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

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

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

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

Способы соединения штрихов можно разделить на несколько категорий, разница между которыми легко определяется глазом. Рассматриваются четыре типа соединения штрихов. Два типа соединения простых штрихов: пересечение (рис. 5а), когда один простой штрих явно входит в другой; сопряжение (рис. 56), когда- два простых штриха сливаются в один. А также два типа соединения циклических штрихов: циклического штриха с одним или несколькими простыми штрихами (рис. 5в); и соединение нескольких циклических штрихов (рис. 5г).

Для каждого из этих типов соединения формулируется свое правило рассечения.

Правило 1. При рассечении пересечения отделяем штрих-ствол от штриха-ветви (рис. 5д).

Правило 2. При рассечении сопряжения отделяем штрихи-ветви от штриха-ствола (рис. 5е).

Правило 3. В случае соединения циклического и простого штрихов отсекаем цикл от простого штриха (рис. 5ж).

Правило 4. В случае соединения несколько циклов выделяем один "внешний" цикл и штрихи-хорды (рис. 5з).

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

Определение 12: Штрихом называется связный подграф скелетного графа, такой, что степень любой его вершины не превышает 2, вместе с множеством своих максимальных кругов.

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

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

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

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

Условие 3. если же вершина-развилка не принадлежит циклам, то рассечение этой развилки должно проводиться в соответствии с правилами рассечения пересечений и сопряжений.

В зависимости от типа соединения вершина-развилка заменяется соответствующим числом вершин степеней 1 и 2. Способ соединения штрихов определяется на основе особенностей границы в окрестности места соединения.

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

а) б)

Рис.6.

Для анализа гладкости границы в месте соединения штрихов применяется следующий критерий. Рассмотрим полигональное представление границы. Пусть V- произвольный сайт-точка границы а У'и V- его соседние сайты-точки (рис. 66). Считается, что граница в точке V является гладкой, если отношение радиуса окружности, проведенной через точки к сумме длин отрезков превышает некоторую

пороговую величину задаваемую пользователем:

В противном случае считается, что граница имеет в точке Кизлом.

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

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

Определим ломаную С как последовательность вершин С = {С0 ,..., сп}. Ломаная может быть замкнутой (в этом случае С0 = сп).

Определение 13: Секцией ломаной называется связный фрагмент данной ломаной с концами в ее вершинах. Секция может состоять из одного отрезка ломаной (простая секция) или из нескольких (составная секция).

Пусть даны две ломаных Р = {^о.....Рт) и б =

Гомеоморфное отображение Р в 0 строится на основе следующих правил:

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

2) разбиения проводятся таким образом, что в каждой паре секций с одинаковым номером хотя бы одна являлась простой;

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

Определение 14: Трансформацией ломаной Р в ломаную 0 называется

упорядоченное множество - секция

из Р, б' - секция из удовлетворяющее следующим требованиям:

1) каждое из ребер ломаных Р и 0 входит в одну и только одну секцию;

2) в каждой паре(Р', из 5 хотя бы одна секция является простой. Пример такого соответствия секций приведен на рис. 7.

Вводятся следующие "элементарные" деформации секций:

1) "распрямление" ломаной в отрезок или изгиб отрезка в ломаную (рис. 8а);

2) растяжение (сжатие) отрезка в отрезок (рис. 86);

3) изгиб в концевых точках секций (рис. 8в).

Р2 3

1 4

б) В) Рис. 8.

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

При проведении каждой из деформаций совершается механическая работа. Работа, соответствующая трансформации S ломаной Р в ломаную Q, определяется как сумма всех деформаций/

Определение 15: Работой W(s) трансформации S ломаной Р в ломаную Q называется величина

ZWbend ((Pr,Qr))+ Е Wstr((Pr,Qr))+

здесь ^¿еЛ£/((-РГ,бГ)) - работа по распрямлению секций Рг и Qr;

- работа по растяжению (сжатию) секции Рг в секцию Qr ; ^kink ((^>Г"'»2Г""')>(^>Г«бР)) - работа по изгибу в смежной точке секций

при переходе в секции Определение 16: Минимальной работой по преобразованию ломаной Р в ломаную Q называется величина

^пип(Ле) = min{iF(5)| 5 e Q{P,Q)};

здесь W(S) - работа, соответствующая трансформации S, а n{P,Q) -множество допустимых трансформаций Р в Q.

Вычисление минимальной работы трансформации проводится следующим способом. Представим все соответствия между вершинами Р и Q с помощью матрицы размерности (от + 1)х(и + 1) или вершин графа (рис. 9а). Вертикалям в этом случае соответствуют вершины ломаной Р, а горизонталям - вершины ломаной Q. Точка на пересечении вертикали i и горизонтали j соответствует паре . Обозначим эту точку как

Теперь зададим ребра графа. Будем считать, что вершины (z'i,./i) и (j2>l2)

wstr{(Pr,er))

соединены ребром в том и только том случае, если выполнены следующие условия: (1)либо /'1 =¡2-1 и у'2 > Л> либо /2 > »1 и д = у'2 — 1; (2) если »1=0, то д = 0; если ¡\=п,то д=т.

Каждому такому ребру соответствует пара секций (секция из Р, с концевыми вершинами ри р^, и секция из с концевыми вершинами

дл и Чн ), из которых хотя бы одна является простой. Таким образом,

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

Любую допустимую трансформацию 5 Р в 0 можно представить в виде монотонного пути на этом графе, начинающегося в точке (0,0) и заканчивающегося в точке (т,п) и наоборот — любой путь на графе, удовлетворяющий приведенным выше условиям, соответствует некой допустимой трансформации Р в На рис. 96 приведен пример такого представления для трансформации, изображенной на рис. 7.

Таким образом, задача о нахождении минимальной работы по преобразованию ломаной Р в ломаную 0 сводится к задаче о поиске кратчайшего пути на графе. Задача такого поиска решается с применением методов динамического программирования. Вычислительная сложность алгоритма поиска - 0(тп(т + и)).

Заключение содержит основные результаты диссертации.

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

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

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

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

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

1. Местецкий Л.М., Рейер И.А. Поиск ключевых слов в рукописном контексте. Математические методы распознавания образов // Тезисы докладов 9-й Всероссийской конференции, Москва, 1999, С. 213-215.

2. Местецкий Л.М., Рейер И.А Распознавание формы растровых бинарных изображений плоских фигур с использованием морфинга контуров границы // Интеллектуализация обработки информации: тезисы докладов Международной конференции, Симферополь, 2000, С. 111-112.

3. Местецкий Л.М., Рейер И.А. Распознавание формы растровых бинарных изображений плоских фигур с использованием морфинга контуров границы //Искусственный интеллект, 2000, №2, С. 401-406.

4. Местецкий Л.М., Рейер И.А. Построение скелета области с кусочно-гладкой границей на основе полигональной аппроксимации // Доклады X Всероссийской конференции "Математические методы распознавания образов", Москва, 2001, С. 252-256.

5. Местецкий Л.М., Рейер И.А. Программное обеспечение для работы с непрерывным гранично-скелетным представлением дискретных изображений // Интеллектуализация обработки информации: тезисы докладов Международной конференции, Симферополь, 2002, С. 137138.

6. Местецкий Л.М., Рейер И.А. Непрерывное скелетное представление изображения с контролируемой точностью // Труды 13-й межд. конф. Трафикон-2003И, Москва, 2003, С. 246-249.

7. Местецкий Л.М., Рейер И.А. Непрерывная гранично-скелетная модель дискретного изображения с контролируемой точностью аппроксимации // Доклады XI Всероссийской конференции "Математические методы распознавания образов", Москва, 2003, С. 367-370.

8. Местецкий Л.М., Рейер И.А., Седерберг Т.У. Анализ рукописного текста на основе непрерывного гранично-скелетного представления // Искусственный интеллект, 2002, №2, С. 501-509.

9. Петровцева М.А., Рейер И.А. Язык гранично-скелетного представления бинарных изображений // Труды 13-й межд. конф. "Графикон-2003", Москва, 2003, С. 228-234.

Ю.Рейер И.А. Сегментация штрихов и их соединений при распознавании рукописного текста // Труды 9-й межд. конф. Трафикон-99", Москва,

1999, С. 151-155.

11.Рейер И.А. Распознавание формы объектов с использованием морфинга контуров границы // Математические методы распознавания образов. Тезисы докладов 9-й Всероссийской конференции, Москва, 1999, С. 222-223.

12.Рейер И.А. Сравнение формы объектов с использованием морфинга контуров границы // Труды 10-й межд. конф. "Графикон-2000", Москва,

2000, С. 179-180.

13.Рейер И.А. Распознавание формы плоских объектов на основе гомеоморфного отображения границы // Труды 5-й межд. конф. "Распознавание образов и анализ изображений: новые информационные технологии", Самара, 2000, т. 2, С. 377-381.

14.Mestetskii L.M., Reyer I.A., Sederberg T.W. Continuous approach to segmentation of handwritten text // Proc. 8th Int. Workshop on Frontiers in Handwriting Recognition, 2002. - P. 440-445.

15.Reyer I.A. Plane figure recognition based on contour homeomorphism // Pattern Recognition and Image Analysis. - 2001. - Vol. 11, No. 1. - P. 242-

Щ- С74 4

Издательство ООО "МАКС Пресс". Лицензия ИД № 00510 от 01.12.99 г. Подписано к печати 09.03.2004 г. Формат 60x90 1/16. Усл.печл. 1,25. Тираж 100 экз. Заказ 256. Тел. 939-3890,939-3891,928-1042. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В Ломоносова.

ВВЕДЕНИЕ.

ГЛАВА 1. МЕТОДЫ ПРЕДСТАВЛЕНИЯ ФОРМЫ ИЗОБРАЖЕНИЯ НА ОСНОВЕ ГРАНИЦЫ И СКЕЛЕТА.

1.1. Задача анализа формы изображений.

1.2. Граничные представления формы изображений.

1.3. Скелетные представления формы изображений.

1.4. Выводы.

ГЛАВА 2. НЕПРЕРЫВНОЕ ГРАНИЧНО-СКЕЛЕТНОЕ ПРЕДСТАВЛЕНИЕ ИЗОБРАЖЕНИЯ С КОНТРОЛИРУЕМОЙ ТОЧНОСТЬЮ.

2.1. Точность непрерывного гранично-скелетного представления.

2.2. Скелет области с кусочно-гладкой границей и скелетный граф.

2.3. Скелет полигональной области.

2.4. Аппроксимирующая полигональная область минимального периметра.

2.5. Базовый скелет полигональной области и его свойства.

2. б. Структура данных для реализации непрерывного гранично-скелетного представления.

2.7. Ачгоритм построения базового скелета полигональной области.

2.8. Построение гранично-скелетного представления с контролируемой точностью аппроксимации.

2.9. Выводы.

ГЛАВА 3. ШТРИХОВАЯ СЕГМЕНТАЦИЯ ИЗОБРАЖЕНИЯ.

3.1. Задача штриховой сегментации с учетом гладкости границы.

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

3.3. Определение типа соединения штрихов.

3.4. Алгоритм штриховой сегментации с учетом локальных свойств границы.

3.5. Применение алгоритма штриховой сегментации к прикладным задачам.

3.6. Выводы.

ГЛАВА 4. СРАВНЕНИЕ ФОРМЫ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ГОМЕОМОРФНОГО ПРЕОБРАЗОВАНИЯ.

4.1. Анализ формы на основе сравнения контуров объектов.

4.2. Построение гомеоморфного отображения.

4.3. Вычисление механической работы "элементарных " деформаций.

4.4. Вычисление минимальной работы трансформации.904.5. Пример сравнения контуров.

4.6. Применение сравнения контуров к прикладным задачам.

4.6.1 Задача распознавания печатных букв.

4.6.2 Задача идентификации вертолета по силуэту корпуса.

4.6.3 Задача распознавания лиц по линии профиля.

4.7. Выводы.

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

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

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

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

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

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

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

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

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

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

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

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

Решение задачи основывается на следующем подходе:

1) дискретно-непрерывное преобразование бинарного изображения в непрерывное гранично-скелетное представление. Исходное дискретное изображение вначале аппроксимируется непрерывным бинарным образом, т.е. некоторой фигурой, имеющей непрерывную границу. Эта аппроксимация может быть осуществлена неоднозначно в пределах точности, определяемой разрешающей способностью дискретного изображения. При аппроксимации границы дискретного образа непрерывной линией кривизна этой линии может очень сильно меняться при сохранении в нужных пределах точности аппроксимации границы. Это приводит к тому, что получаемые скелеты для непрерывных образов с близкой границей сильно различаются в смысле их топологической структуры. Для того чтобы выделить общие существенные структурные свойства всего множества таких скелетов, в работе вводится понятие "скелетного ядра" - множества точек, входящих в окрестность скелета любого непрерывного объекта, аппроксимирующего с заданной точностью исходный дискретный образ. В скелете каждого аппроксимирующего непрерывного объекта можно выделить так называемый «базовый скелет» - подмножество, аппроксимирующее с заданной точностью скелетное ядро. В работе приводится метод построения базового скелета для аппроксимирующей полигональной области. Таким образом, дискретно-непрерывное преобразование осуществляется по следующей схеме: граница растрового бинарного изображения аппроксимируется многоугольниками минимального периметра; строится непрерывный скелет полученной многоугольной фигуры; в полученном непрерывном скелете выделяется "базовый скелет".

2) сегментация скелета на отдельные структурные элементы (штрихи) с учетом гладкости и кривизны сопряженных элементов границы;

3) сравнение элементов гранично-скелетного представления на основе морфинга -гомеоморфного отображения, минимизирующего заданный критерий.

Новые научные результаты, выносимые на защиту:

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

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

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

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

4.7. Выводы

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

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

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

Заключение

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

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

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

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

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

1. Абламейко С.В., Лагуновский Д.М. Обработка изображений. Технология, методы, применение. Минск. Амалфея, 2000.

2. Буренков Д.С., Храпов П.В. Физическая модель гладкой трансформации контуров // Труды межд. конф. Трафикон-2001", Нижний Новгород, 2001. С. 199-202.

3. Введение в контурный анализ и его приложения к обработке изображений. Под ред. Фурмана Я.А. -М.: ФИЗМАТЛИТ, 2002.

4. Журавлев Ю.И., Гуревич И.Б. Распознавание образов и распознавание изображений // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 2. М.: Наука, 1989. С. 5-72.

5. Иванов Д., Кузьмин Е. Эффективный алгоритм построения остова растрового изображения//Труды межд. конф. "Графикон-98", Москва, 1998. С. 65-68.

6. Катыс Г.П. Обработка визуальной информации. М.: Машиностроение, 1990.

7. Лагно Д., Соболев А. Модифицированные алгоритмы Форчуна и Ли скелетизации многоугольной фигуры // Труды межд. конф. "Графикон-2001", Нижний Новгород, 2001. С. 120-125.

8. Местецкий Л.М. Непрерывный скелет бинарного растрового изображения // Труды межд. конф. "Графикон-98", Москва, 1998.

9. Местецкий Л.М., Рейер И.А. Поиск ключевых слов в рукописном контексте. Математические методы распознавания образов // Тезисы докладов 9-й Всероссийской конференции (ММРО-9), Москва, 1999, С. 213-215.

10. Местецкий Л.М., Рейер И.А. Распознавание формы растровых бинарных изображений плоских фигур с использованием морфинга контуров границы // Интеллектуализация обработки информации: тезисы докладов Международной конференции, Симферополь, 2000, С. 111-112.

11. Местецкий JI.M., Рейер И. А. Распознавание формы растровых бинарных изображений плоских фигур с использованием морфинга контуров границы // Искусственный интеллект. Журнал НАН Украины, 2000, №2, С. 401-406.

12. Местецкий JI.M., Рейер И.А. Построение скелета области с кусочно-гладкой границей на основе полигональной аппроксимации // Доклады X Всероссийской конференции "Математические методы распознавания образов" (ММРО-Ю), Москва, 2001, С. 252-256.

13. Местецкий JI.M., Рейер И.А. Программное обеспечение для работы с непрерывнымгранично-скелетным представлением дискретных изображений // Интеллектуализация обработки информации: тезисы докладов Международной конференции, Симферополь, 2002, С. 137-138.

14. Местецкий JI.M., Рейер И.А. Непрерывное скелетное представление изображения с контролируемой точностью // Труды 13-й международной конференции по компьютерной графике и машинному зрению "Графикон-2003", Москва, 2003, С. 246-249.

15. Местецкий JI.M., Рейер И.А., Седерберг Т.У. Анализ рукописного текста на основенепрерывного гранично-скелетного представления // Искусственный интеллект. Журнал НАН Украины, 2002, №2, С. 501-509.

16. Петровцева М.А., Рейер И.А. Язык гранично-скелетного представления бинарных изображений // Труды 13-й международной конференции по компьютерной графике и машинному зрению "Графикон-2003", Москва, 2003, С. 228-234.

17. Прэтт У. Цифровая обработка изображений. Кн. 1,2.- М.: Мир, 1982.

18. Рейер И.А. Сегментация штрихов и их соединений при распознавании рукописного текста // Труды 9-й международной конференции по компьютерной графике и машинному зрению "Графикон-99", Москва, 1999, С. 151-155.

19. Рейер И.А. Распознавание формы объектов с использованием морфинга контуров границы // Математические методы распознавания образов. Тезисы докладов 9-й Всероссийской конференции (ММРО-9), Москва, 1999, С. 222-223.

20. Рейер И.А. Сравнение формы объектов с использованием морфинга контуров ^ границы // Труды 10-й международной конференции по компьютерной графике имашинному зрению "Графикон-2000", Москва, 2000, С. 179-180.

21. Старовойтов В.В. Локальные геометрические методы цифровой обработки и анализа изображений.- Минск: Институт технической кибернетики НАН Беларуси, 1997.

22. Ту Д., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978.

23. Фор А. Восприятие и распознавание образов. М.: Машиностроение, 1989.

24. Albano A. Representation of digitized contours in terms of conic arcs and straight-line segments // Comput. Gr. and Image Proc. 1974. - Vol. 3, No. 1. - P. 23-33.

25. Arcelli C., Sannity di Baja G. A width-independent fast thinning algorithm // IEEE Trans,on PAMI. 1985. - Vol. 7, No. 4. - P. 463-474.

26. Attali D., Sannity di Baja G., and Thiel E. Pruning discrete and semicontinuous skeletons // Proc. of 8th ЮАР, San Remo, September 1995.

27. Badi'i F., Peikari B. Functional approximation of planar curves via adaptive segmentation // Int. J. Syst. Sci. 1982. - Vol. 13, No. 6. - P. 667-674.30