Введение к работе
Задачи, связанные с анализом формы изображений, возникают в большинстве разработок современных систем машинного зрения. К таким задачам относятся, например, поиск заданных слов в рукописных документах; поиск определенных символов на географических картах и схемах; автоматическое чтение этикеток, маркировок; идентификация, классификация и сортировка деталей; обнаружение и опознавание цели в телевизионных системах наблюдения и т. д.
Анализ формы изображения включает в себя два этапа: собственно выделение формы объекта и составление его признакового описания. Для выделения формы используются различные методы обработки изображений. Результатом их применения является растровое бинарное изображение, представляющее собой силуэт объекта (рис. 1а). Это изображение является исходным для получения признакового описания формы объекта. Методы составления такого описания являются предметом настоящего исследования.
з) * 6) ^ в) і
Рисі.
Можно выделить два традиционных подхода к построению
признакового описания формы. Первый основывается на выделении
границы объекта, а второй - на построении его скелета. Под границей
понимается множество точек (пикселей) изображения, имеющих точки
фона в качестве соседних (рис. 16). Скелет представляет собой множество
точек (пикселей) объекта, равноудаленных от двух или более его
граничных точек, т.е. так называемые серединные оси объекта (рис. 1в).
Традиционно граница и скелет строятся на основе морфологических преобразований растрового изображения и имеют вид растровых линий шириной в один пиксель. Построение признаковых описаний на основе такого дискретного представления границы и скелета характеризуется следующими недостатками.
Дискретные представления плохо приспособлены для вычисления признаков, имеющих непрерывную природу, связанных с оценкой-гладкости и кривизны линий, а также с оценкой "ширины" объекта относительно серединных осей.
Дискретные представления границы и скелета не позволяют учесть их взаимосвязи между собой. В результате построение признаков, основанных на совместных свойствах границы и скелета, весьма затруднительно. Речь идет о таких признаках, как, например, гладкость сопряжения штрихов в рукописном тексте.
Эти недостатки снижают информативность получаемого признакового описания формы. Один из путей их преодоления состоит в построении непрерывной модели границы и скелета изображения. Необходимость разработки такой модели и численных методов ее расчета и анализа определяет актуальность темы.
Целью диссертации является повышение качества обработки и распознавания изображений за счет применения непрерывной гранично-скелетной модели изображения.
Научной задачей является построение теоретически корректной модели непрерывного гранично-скелетного представления формы изображения и разработка эффективных методов ее расчета и анализа.
Сложность этой задачи обусловлена, в первую очередь, неоднозначностью непрерывного представления границы и скелета и отсутствием строгих критериев его выбора. Кроме того, непросто удовлетворить высокие требования к эффективности алгоритмов
построения и анализа границы, и скелета (включающих до 104-105 элементов) в системах реального времени.
Предлагаемое решение задачи основывается на следующем подходе:
Разработка концепции скелетного ядра дискретного образа и базового скелета непрерывной фигуры, аппроксимирующей этот образ. Скелетное ядро - это множество точек, входящих в окрестность скелета любой непрерывной фигуры, аппроксимирующей с заданной точностью исходный дискретный образ. Базовый скелет непрерывной фигуры -подмножество её скелета, приближающее с заданной точностью скелетное ядро;
дискретно-непрерывное преобразование растрового бинарного изображения, включающее: аппроксимацию границы растрового бинарного изображения многоугольниками минимального периметра; построение непрерывного скелета полученной многоугольной фигуры; построение базового скелета многоугольной фигуры;
сегментация формы изображения на отдельные структурные элементы (штрихи) с учетом гладкости соединения штрихов. Оценка гладкости соединений штрихов осуществляется на основе гранично-скелетного представления;
сравнение формы объектов на основе морфинга - гомеоморфного отображения элементов гранично-скелетного представления, минимизирующего заданный критерий.
Новые научпые результаты, выносимые на защиту: метод построения скелетного представления с контролируемой точностью аппроксимации. Известные методы строят скелетное представление по эвристическим правилам, что не позволяет однозначно определить скелет и оценить точность представления. В отличие от них предлагаемый метод позволяет корректно определить "базовый скелет", аппроксимирующий образ с заданной точностью;
метод штриховой сегментации гранично-скелетного представления. Сегментация сводится к выделению в непрерывном скелете, который можно рассматривать как граф, подграфов, степень вершин которых не превышает 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". Методы построения скелетного представления с контролируемой точностью
аппроксимации и сегментации гранично-скелетного представления применялись при решении задачи поиска заданного слова в рукописном документе. Процедура сравнения контуров изображений на. основе гомеоморфного преобразования применялась при решении задач-распознавания печатных и рукописных букв и символов, определения типа вертолета по силуэту корпуса, распознавания профилей человеческих лиц.
