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

На правах рукописи Быстрое Максим Юрьевич

СТРУКТУРНОЕ РАСПОЗНАВАНИЕ БИНАРНЫХ ИЗОБРАЖЕНИЙ С ИСПОЛЬЗОВАНИЕМ СКЕЛЕТОВ

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

АВТОРЕФЕРАТ

4852091

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

1 1 АВГ 2011

Петрозаводск 2011

4852091

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Петрозаводский государственный университет»

Научный руководитель: доктор технических наук, профессор

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

Официальные оппоненты: доктор физико-математических наук,

профессор

Камачкин Александр Михайлович

Ведущая организация: Институт информатики и математического

моделирования технологических процессов Кольского НЦ РАН

Защита состоится 30 сентября 2011 г. в 11:00 часов на заседании диссертационного совета Д 212.190.03 при Петрозаводском государственном университете по адресу: 185910, г. Петрозаводск, пр. Ленина, 33.

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

Автореферат разослан « » МД^^л-С_2011 г.

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

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

Р. В. Воронов

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

Актуальность темы. Развитие вычислительной техники в 20 веке стало одним из величайших достижений человека. Оказалось, что компьютер способен решать огромное количество задач, и человек поручил ему значительную часть своей повседневной работы. Однако достижения в решении некоторых классов решаемых компьютером задач являются достаточно скромными. К ним, прежде всего, относятся задачи, требующие интеллектуальной обработки и в частности задача распознавания образов. Постановка данной задачи появилась в конце 50-х годов 20 века. Большой вклад в развитие теории распознавания образов внесли отечественные ученые В. Н. Вапник, В. М. Глушков, А. Л. Горелик, Ю. И. Журавлев, Н. Г. Загоруйко и др., а также зарубежные Ф. Розенблатт, Б. Уидроу, Л. Рабинер, К. Фукунага, П. Харт, А. Ро-зенфельд, Дж. Хопфилд и др.

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

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

Одним из вариантов описания изображений является представление их в виде скелетов. Впервые данная идея была предложена X. Блюмом. Большой вклад в развитие принципов построения и использования скелетов также внесли У. Монтанари, Э. Калаби, С. Форчуне, Д. Ли и др. С момента выхода первой работы по скелетам опубликованы сотни статей, показывающие широкие возможности их использования при анализе и распознавании изображений.

Цель работы: разработка и реализация алгоритмов поиска в электронных коллекциях бинарных изображений.

Для достижения цели были поставлены следующие задачи:

1) исследование и анализ существующих методов на предмет эффективного построения и обработки скелетов бинарных изображений;

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

3) разработка алгоритма структурного поиска в коллекции бинарных изображений с использованием скелетов;

4) компьютерная реализация алгоритма структурно го поиска.

Методы исследования. В диссертационной работе используются

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

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

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

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

3) определены значения параметров алгоритма поиска для коллекции изображений петроглифов Карелии и показаны его преимущества перед известными методами;

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

Научная новизна работы заключается в следующем:

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

2) получены численные характеристики параметров алгоритмов на коллекции изображений петроглифов Карелии;

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

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

Публикации и апробация работы. Материалы диссертационного исследования докладывались и обсуждались на XIII Всероссийской научной конференции «Математические методы распознавания образов» (Санкт-Петербург, 2007); X Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции «RCDL'2008» (Дубна, 2008); XI Всероссийской конференции ассоциации «История и компьютер» (Москва, 2008); Ежегодном международном научном семинаре «Передовые методы информационных и коммуникационных технологий» (Петрозаводск, 2008); XI Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции «RCDL'2009» (Петрозаводск, 2009); XL научной конференции аспирантов и студентов «Процессы управления и устойчивость» (Санкт-Петербург, 2009); XII Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные'коллекции «RCDL'2010» (Казань, 2010). По теме диссертации опубликовано двенадцать научных работ, из них две входят в список ВАК. Разработанное программное обеспечение было апробировано на коллекции бинарных изображений петроглифов Карелии и зарегистрировано в Объединенном фонде электронных ресурсов «Наука и образование» (ОФЭРНиО) № 16964 от 07.04.2011 г. Работа поддержана грантами РГНФ № 05-01-12118в, № 08-01-12116в (руководитель Н. В. Лобанова).

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, библиографического списка использованной литературы (102 наименования) и двух приложений, имеет объем 125 страниц машинописного текста и 6 страниц приложений, содержит 58 рисунков и 5 таблиц.

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

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

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

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

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

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

(а)

(б)

(в)

Рис. 1. Дискретная фигура без «дыр» (а); граничное представление (б); скелет (в)

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

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

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

В § 1 производится постановка задачи. В работе бинарные изображения рассматриваются как исходный материал. Под бинарными изображениями понимаются такие изображения, на которых содержится только одна фигура без «дыр» (рис. 1, а).

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

Р1 Р2 РЗ

Р8 РО Р4

Р7 Рб Р5

Рис. 2. Обозначение исследуемой точки (Р0) и ее соседей в алгоритме Зонга-Суня

Вводятся следующие переменные: А — число конфигураций 01 в последовательности Р1, Р2, РЗ, РА, Р5, Р6, Р1, Р8,Р1.

В — количество ненулевых соседей РО, то есть:

В = Р\ + Р2 + РЗ + Р4 + Р5 + Р6 + Р1 + Р8. На первом шаге для каждой черной точки проверяется условие:

(2 < = В < = 6) И (А = 1) И (Р2 х Р4 х Р6 = 0) И (Р4 х Р6 х Р8 = 0), на втором условие:

(2 < = В < = 6) И (А = 1) И (Р2 х Р4 х Р8 = 0) И (Р2 х Р6 х Р8 = 0). Если условие, соответствующее текущему шагу выполняется, то исследуемая точка перекрашивается в 0.

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

Рис. 3. Построение скелета фигуры с помощью алгоритма Зонга-Суня: (а) исходная фигура; (б), (в) шаги первой итерации; (г), (д) шаги второй итерации (на втором шаге второй итерации (д) пи одна точка не была перекрашена); (е) скелет фигуры

Далее описываются варианты улучшения скелета, полученного алгоритмом Зонга-Суня, а также приводится сравнение с другим аналогичным методом, и указываются его преимущества.

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

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

Пусть FQ — восстановленная по скелету фигура, а ее площадь — SQ. Под площадью фигуры понимается количество точек, из которых она состоит. Удалим какое-либо терминальное ребро i из скелета и снова восстановим фигуру, используя оставшиеся ребра и старые радиусы (фигура F.), обозначим ее площадь Sr Форма и площадь фигуры F будет отличаться от фигуры Ff¡. При этом если S отличается от S() незначительно, то удаленное терминальное ребро является шумовым, т. к. не сильно повлияло (или вообще не повлияло) на площадь. Стоит отметить, что критерий сравнения площадей является достаточным, т. к. F. всегда будет лежать внутри F().

Основываясь на данной идее, предлагается следующий алгоритм регуляризации скелета:

1) составляется список всех терминальных ребер скелета Т;

2) по скелету восстанавливается исходная фигура и вычисляется ее площадь S ;

3) выбирается i-e терминальное ребро скелета из списка Т\

4) по скелету без ребра i восстанавливается фигура и считается ее площадь S-

5) если (S0 - S) / S0 < Р , где PR — пороговая величина, то ребро i удаляется из скелета, иначе переход к п. 7;

6) если после удаления ребра возникли новые терминальные ребра, то поместить их в список Т\

7) если остались нерассмотренные терминальные ребра — переход к п. 3, иначе конец алгоритма.

Пример работы алгоритма регуляризации представлен на рис. 4.

Л*

(а) (б) (в)

Рис. 4. Работа алгоритма регуляризации скелета: (а) исходное изображение; (б) скелет; (в) скелет после регуляризации

В § 4 описывается используемый метод аппроксимации скелета. На данном этапе происходит аппроксимация ребер скелета прямыми линиями (рис. 5, а, б). При этом, в случае небольшой кривизны ребра, оно преобразовывается в одно ребро — отрезок, с теми же вершинами, иначе ребро преобразовывается в набора отрезков.

(а) (б) (в)

Рис. 5. Аппроксимация скелета: (а) скелет фигуры; (б) аппроксимация скелета; (в) вычисление кривизны ребра

Для проведения аппроксимации используется метод, основанный на поиске точек максимальной кривизны и делении ребер на две части в этих точках. Кривизна ребра С измеряется максимальным евклидовым расстоянием от точек ребра скелета до прямой, проведенной через его концы А и В (рис. 5, в):

С = тах (с!(Хг АВ)), / = 1,..., и, где X. — /-я точка ребра, п — количество ребер в скелете, с1(Х., АВ) — расстояние от точки X до отрезка АВ. Далее вводится условие:

С > Р, х Д

А '

где Р — пороговая величина, £> — диаметр минимальной окружности, описанной вокруг скелета. Если условие выполняется, то ребро

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

На основе данной идеи предлагается алгоритм аппроксимации ребер скелета. Для удобства ребра с концами в точках А и В будем обозначать {А, В}. Алгоритм заключается в следующем:

1) составляется список ребер скелета Я;

2) выбирается 1-е ребро из Я и обозначается {А., В.};

3) через точки А. и В. проводится прямая

4) вычисляется кривизна ребра С и находится соответствующая ей точка 0\

5) если С > Рд * Д то переход на п. 6, иначе переход на п. 7;

6) ребро {А., В.} делится на два новых ребра: {А., О} и {О, В.], которые заносятся в список Я. Переход на п. 2;

7) отрезок А В записывается в строку результатов;

8) если остались нерассмотренные ребра — переход на п. 2, иначе конец алгоритма.

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

Здесь стрелками обозначено направление обхода скелета, О — точка, в которой начинается обход. Следующий алгоритм реализует данную идею и получает цепочку для скелета, состоящего из п ребер:

1) выбирается терминальная вершина скелета и инцидентное ей терминальное ребро / = 1. Вторая нетерминальная вершина, инцидентная ребру / объявляется текущей;

2) вычисляется длина г-го ребра / и записывается в цепочку;

3) среди ребер, инцидентных текущей вершине, выбирается то, которое составляет наименьший угол относительно /-го ребра против часовой стрелки (ребро i + 1). Рассматривается также само г-е ребро с углом, равным 360°;

О

Рис. 6. Получение цепочки примитивов

4) угол а. между ребрами / и / + 1 записывается в цепочку;

5) если / + 1 = 2п + 1, то конец алгоритма. Иначе вершина, инцидентная ребру / + 1, не являющаяся текущей, объявляется текущей, / увеличивается на 1 и переход на п. 2.

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

{1па}, /= 1,..., 2п,

где /. — длина /-го элемента, а — угол между ;-м и /' + 1-м элементами, п — количество ребер в скелете.

Длина /. является относительной величиной к диаметру минимальной окружности, описанной вокруг скелета:

где с1(А., В) — евклидово расстояние между вершинами ребер А. и В., т. е. абсолютное значение длины г-го ребра.

Цепочка примитивов, описывающая скелет на рис. 6, имеет вид:

{70 ; 95} {50 ; 360} {50 ; 90} {40 ; 360} {40 ; 175} {70 ; 360}.

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

1) цепочки устойчивы к масштабированию;

2) цепочки устойчивы к повороту фигуры;

3) изменение начала обхода соответствует циклическому сдвигу элементов в цепочке;

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

'1 ~* 'гп> ¿2 ¿2п-1 •■• Ь Ьп-1+1 — 'гп-1 Ьп '1 а1 «2П-1. а2 -» а2п-г - -» а2п-; - ат-\ -»

а2п а2п-

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

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

{/,.,<*.},/=!,..., 2п, {£.,£.},/= 1,..., 2п.

Тогда введем следующее условие равенства: цепочки равны, если для V i = 1,..., 2п выполняются условия:

где PlhPc — пороговые величины.

С учетом того, что начало обхода сравниваемых скелетов выбирается произвольным образом и может не совпадать, требуется корректировка данного условия. Для этого достаточно зафиксировать одну из цепочек и сравнить с 2п циклическими сдвигами второй. Если хотя бы одна пара сравниваемых цепочек будет равна, то и исходные цепочки равны между собой. То есть, если найдется такой сдвиг на у б [1, 2п] элементов, что для V / = 1,..., 2п выполняется: \l-k\<PL, |а.-/?.| <РС,

. _ Г i + у, если i + у < 2п; гДе J _ (£ + у - 2п, если i + у > 2п.

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

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

3—14 и /,, а также угол, связывающий их между собой а/.

*- + -*

{70 ; 95} {50; 360} {50; 90} {40; Зёв} {40; 175} {70; 360}.

Заметим далее, что угол между ребрами 1 и 2 (невыпуклый) равняется сумме углов между ребрами 1 и 3 и ребрами 2 и 3 в скелете, а это углы а3 и а5 соответственно. Сложив и объединив эти два угла между собой, получим искомую цепочку.

В общем случае процесс удаления терминального ребра из цепочки {/., а.}, i = 1, ..., 2п можно записать следующей последовательностью действий:

1) ребро на позиции к в цепочке является терминальным, если ак = 360°, иначе — не терминальным, и удаление невозможно;

2) для того, чтобы удалить терминальное ребро к, необходимо из

цепочки удалить !к, 1к+, и ак, а ак _, и ак+, сложить между собой:

*- + -*

{lü «i} - [ik-i: ffk-i) fe(W; «fe+i) - ihn, a2n}.

Пусть необходимо найти общую часть длины 2г цепочек {/., ct.}, i = 1,..., 2п и {к., ß.}, / = 1,..., 2т (г < min (и,т)). Для этого нужно сравнить всевозможные их подцепочки длины 2г, которые можно получить последовательным удалением терминальных ребер. Если хотя бы одна пара сравниваемых подцепочек будет равна, то общая часть найдена.

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

{/'., i = 1,..., 2г, {£'.,/?'.}, i = 1,2г.

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

к» - к' х 1=1 '

к [ - /С t Л .

1 K-j

После чего сравнивать описанным ранее способом: {/',.,<},/= 1,..., 2г и {&",/?'.}, /= 1,..., 2г.

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

С помощью разработанного программного комплекса были проведены исследования метода скелетизации Зонга-Суня. Выявлено устойчивое поведение алгоритма при масштабировании и повороте фигур. Рассмотрен вариант оптимизации выполнения алгоритма. В зависимости от размеров прирост скорости составил 3—И раз.

Описанный во второй главе алгоритм структурного поиска в коллекции бинарных изображений с использованием скелетов был полностью реализован в виде программного комплекса, который был зарегистрирован в Объединенном фонде электронных ресурсов «Наука и образование» (ОФЭРНиО). Данный программный комплекс позволяет строить скелеты, производить поиск в коллекциях бинарных изображений, а также вручную настраивать параметры алгоритма.

Апробация разработанного программного комплекса структурного поиска происходила на коллекции изображений петроглифов Карелии.

Для тестирования были отобраны 200 черно-белых изображений петроглифов.

Разработанный алгоритм структурного поиска в электронной коллекции бинарных изображений состоит из нескольких этапов. На некоторых из них результат обработки зависит от выбора значений параметров, необходимых для их функционирования. Для коллекции петроглифов Карелии были подобраны оптимальные значения параметров работы алгоритма (таблица 1).

Таблица 1

Параметры алгоритма для коллекции петроглифов Карелии

Параметр Обозначение Значение

Регуляризация Р* 0,02

Аппроксимация Ра 0,25

Сравнение (ребра) PL 20

Сравнение (углы) Рс 30

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

В таблице 2 представлена информация о средней скорости работы алгоритма для изображения размером точек. Эксперименты проводились на компьютере с процессором Intel Core 2 Duo Е4500, частотой 2,2 Ггц и оперативной памятью 2 Гб.

Таблица 2

Скорость работы алгоритма структурного поиска

Этан Время (мсек)

Получение скелета 15

Регуляризация скелета 100

Аппроксимация скелета 1

Получение цепочки примитивов 1

Сравнение двух цепочек 0,01

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

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

= | Рге1 п Рге(г\ = \Рге1 п Рге(г\ lDr.tr! IDr.il '

где Иге1 — множество релевантных документов в базе, Отг — множество найденных документов.

Для совместной оценки точности и полноты в виде единой величины, характеризующей систему поиска, используется ^-мера, которая определяется как сбалансированное среднее точности Р и полноты Я:

2Рй

^"р + я-

Были получены следующие оценки:

Р = 0,65; Л = 0,9; = 0,75.

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

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

Таблица 3

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

Параметр Обозначение Диапазон

Регуляризация г, 0,01 0,1

Аппроксимация Ра 0,1 0,4

Сравнение (ребра) Р1 5 30

Сравнение (углы) Рс 5 45

В конце главы сделан обзор основных преимуществ и недостатков разработанного метода. Также приведено сравнение алгоритма структурного поиска с другим методом и показаны его преимущества. Среди основных преимуществ предлагаемого подхода можно выделить следующие:

1) устойчивость к масштабированию;

2) устойчивость к повороту фигуры;

3) возможность сравнения фигуры со своим зеркальным отображением;

4) возможность сравнения изображений частями;

5) высокая скорость работы.

Основной недостаток: невысокая точность поиска.

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

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

2. Разработан алгоритм структурного поиска в коллекции бинарных изображений с использованием скелетов, состоящий из этапов: получение скелета; регуляризация (удаление «шумовых» ребер скелета); аппроксимация скелета прямыми линиями; выделение цепочки примитивов, описывающих данный скелет; сравнение цепочек различных изображений между собой. На каждом из этапов предложено решение с использованием существующих или разработанных новых методов.

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

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

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

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

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

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

1. Быстрое, М. Ю. Применение структурного подхода к распознаванию скелетов бинарных изображений / М. Ю. Быстрое // Ученые записки Петрозаводского Государственного Университета. — Петрозаводск: ПетрГУ, 2011. — № 2 (115). — С. 76—80.

2. Рогов, А. А. Информационно-поисковая система петроглифов Карелии / А. А. Рогов, К. А. Рогова, К. Н. Спиридонов, М. Ю. Быстрое // Вестник компьютерных и информационных технологий. — Москва, 2008. — № 6. — С. 6—12.

3. Быстрое, М. Ю. Комплекс программ для структурного распознавания бинарных изображений с использованием скелетов [Электронный ресурс] / М. Ю. Быстрое // Хроники объединенного фонда электронных ресурсов «Наука и образование», № 4, — 2011. — Режим доступа: http://ofernio.ru/portal/newspaper/ofernio/201 l/4.doc, свободный

4. Кириков, П. В. Некоторые особенности создания и анализа электронных коллекций графических документов / П. В. Кириков, М. Ю. Быстрое // Процессы управления и устойчивость: труды XL международной научной конференции аспирантов и студентов. — Спб., 2009. — С. 435—440.

5. Кириков, П. В. Об опыте создания системы управления коллекциями графических документов [Электронный ресурс] / П. В. Кириков, М. Ю. Быстрое, К. А. Рогова, А. А. Рогов // Электронные библиотеки. — Электрон, ст. — 2010. — Т. 13, № 1. — Режим доступа к ст.: http://www. elbib.ru/index.phtml?page=elbib/rus/journal/2010/partl/KBRR, свободный

6. Рогов, А. А. Информационная система для создания и управления электронными коллекциями графических документов / А. А. Рогов, К. А. Рогова, П. В. Кириков, М. Ю. Быстрое // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды XI Всероссийской научной конференции «RCDL'2009». — Петрозаводск: КарНЦ РАН, 2009. — С. 433—438.

7. Рогов, А. А. Информационная система для создания и управления электронными коллекциями графических документов / А. А. Рогов, К. А. Рогова, П. В. Кириков, М. Ю. Быстрое // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды XII Всероссийской научной конференции «RCDL'2010». — Казань, 2010. —С. 409—414.

8. Рогов, А. А. Информационно-поисковая система «Петроглифы Карелии» / А. А. Рогов, К. А. Рогова, К. Н. Спиридонов, М. Ю. Быстрое // Материалы XI конференции ассоциации «История и компьютер». —; Москва: Азбука, 2008.

9. Рогов, А. А. Система поиска в электронной коллекции изображений петроглифов Карелии / А. А. Рогов, К. А. Рогова, К. Н. Спиридонов, М. Ю. Быстров // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды X Всероссийской научной конференции «RCDL-2008». — Дубна: ОИЯИ, 2008. — С. 246—251.

10. Рогова, К. А. Информационная система для создания и управления электронными коллекциями графических документов / К. А. Рогова, П. В. Кириков, М. Ю. Быстров, А. А. Рогов // Молодежь и высокие технологии: материалы всероссийской студенческой олимпиады (Всероссийский конкурс компьютерных программ). — Вологда: ВолГТУ, 2010,—С. 77—79.

11. Рогова, К. А. Задачи анализа изображений в информационно-поисковой системе PIRS / К. А. Рогова, М. Ю. Быстров // Математические методы распознавания образов: 13-я Всероссийская конференция. — М.: МАКС Пресс, 2007. — С. 528—530.

12. Rogova, К. A. Application of modern information technologies to the study of Karelian petroglyphs / K. A. Rogova, Y. Bystrov, K. N. Spiridonov // Advances in Method of Information and Communication Technology. — Petrozavodsk: PetrSlT, 2008. — C. 233—234.

Подписано в печать 05.07.11. Формат 60x84 '/ . Уч.-изд. л. I. Тираж 100 экз. Изд. № 168.

Государственное образовательное учреждение высшего профессионального образования ПЕТРОЗАВОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Отпечатано в типографии Издательства ПетрГУ 185910, Петрозаводск, пр. Ленина, 33

ВВЕДЕНИЕ.

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

§1.1 Распознавание изображений.

1.1.1 Постановки задачи.

1.1.2 Методы сегментация изображений.

1.1.3 Методы распознавания.

1.1.4. Задача поиска в коллекциях графических документов.

§ 1.2 Скелет бинарного изображения.

1.2.1 Бинарные изображения.

1.2.2 Непрерывное представление скелета.

1.2.3 Дискретный скелет.

§ 1.3 Скелетизация непрерывных фигур.

1.3.1 Аппроксимация границ.

1.3.2 Скелетизация многоугольника.

1.3.3 Регуляризация скелета.

§ 1.4 Скелетизация дискретных фигур.1.

1.4.1 Алгоритмы топологического утончения.!.

1.4.2 Скелетизация на основе дистанционной карты.'.

§ 1.5 Структурные методы распознавания.

1.5.1 Выбор непроизводных элементов.

1.5.2 Структурное распознавание.

1.5.3 Синтаксические методы распознавания.

Выводы.

ГЛАВА 2. СТРУКТУРНЫЙ МЕТОД ПОИСКА В ЭЛЕКТРОННЫХ КОЛЛЕКЦИЯХ БИНАРНЫХ ИЗОБРАЖЕНИЙ ПРИ ПОМОЩИ СКЕЛЕТОВ.

§2.1 Постановка задачи

§2.2 Получение скелета.

2.2.1 Алгоритм Зонга-Суня.

2.2.2 Постобработка скелета.

2.2.3 Эффективность метода.

§2.3 Регуляризация скелета.

2.3.1 Обоснование необходимости регуляризации.

2.3.2 Восстановление фигуры по скелету.

2.3.3 Описание алгоритма регуляризации.

§2.4 Аппроксимация скелета.

2.4.1 Цель аппроксимации.

2.4.2 Обзор методов аппроксимации.

2.4.3 Аппроксимация ребер скелета отрезками прямых линий.

2.4.4 Минимальная описанная окружность.

§2.5 Получение цепочки примитивов.

2.5.1 Цепочка примитивов.

2.5.2 Описание алгоритма.

2.5.3 Свойства цепочек.

§2.6 Сравнение цепочек примитивов.

2.6.1 Алгоритм сравнения цепочек.

2.6.2. Сравнение цепочек частями.

Выводы.

ГЛАВА 3. ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ СТРУКТУРНОГО ПОИСКА В КОЛЛЕКЦИИ БИНАРНЫХ ИЗОБРАЖЕНИЙ.

§3.1 Некоторые особенности реализации метода структурного поиска.

3.1.1 Прослеживание скелета.

3.1.2 Восстановление фигуры и регуляризация.

3.1.3 Получение цепочек примитивов.

§3.2 Описание программного комплекса.

§3.3 Исследование метода построение скелета.

3.3.1 Устойчивость метода к масштабированию и поворотам.

3.3.2 Оптимизация выполнения.

§3.4 Апробация программного комплекса.

3.4.1 Описание предметной области.

3.4.2 Подбор параметров алгоритма.

3.4.3 Оценка скорости и эффективности работы.

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

3.5.1 Произвольная коллекция бинарных изображений.

3.5.2 Рекомендации по подбору параметров алгоритма.

§3.6 Анализ алгоритма.

3.6.1 Общие преимущества и недостатки.

3.6.2 Сравнение с другими методами.

3.6.3 Двухуровневый поиск.

Выводы.,.

Развитие вычислительной техники в 20 веке стало одним из величайших достижений человека. Оказалось, что компьютер способен решать огромное количество задач, и человек поручил ему значительную часть своей повседневной работы. Однако достижения в решении некоторых классов решаемых компьютером задач являются достаточно скромными. К ним, прежде всего, относятся задачи, требующие интеллектуальной обработки и в частности задача распознавания образов. Постановка данной задачи появилась в конце 50-х годов 20 века. Большой вклад в развитие теории распознавания образов внесли отечественные ученые В. Н. Вапник, В. М. Глушков, А. Л. Горелик, Ю. И. Журавлёв, Н. Г. Загоруйко и др., а также зарубежные Ф. Розенблатт, Б. Уидроу, Л. Рабинер, К. Фукунага, П. Харт, А. Розенфельд, Дж. Хопфилд и др.

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

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

Одним из вариантов описания изображений является представление их в виде скелетов. Впервые данная идея была предложена X. Блюмом. Большой вклад в развитие принципов построения и использования скелетов также внесли У. Монтанари, Э. Калаби, С. Форчуне, Д. Ли и др. С момента выхода в свет первой работы по скелетам опубликованы сотни статей, показывающие широкие возможности их использования при анализе и распознавании изображений.

Цель работы: разработка и реализация алгоритмов поиска в электронных коллекциях бинарных изображений.

Для достижения цели были поставлены следующие задачи:

1. Исследование и анализ существующих методов на предмет эффективного построения и обработки скелетов бинарных изображений;

2. Разработка модели представления скелетов бинарных изображений;

3. Разработка алгоритма структурного поиска в коллекции бинарных изображений с использованием скелетов;

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

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

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

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

3. Определены значения параметров алгоритма поиска для коллекции изображений петроглифов Карелии и показаны его преимущества перед известными методами;

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

Научная новизна работы заключается в следующем:

1. Разработан алгоритм структурного поиска в коллекции бинарных изображений с использованием скелетов;

2. Получены численные характеристики параметров алгоритмов на коллекции изображений петроглифов Карелии;

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

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

В первой главе содержатся общие сведения о задаче распознавания изображений [59], основных методах ее решения, в том числе структурных [62], формулируется задача поиска в электронных графических коллекциях, дается понятие скелетов бинарных изображений [28] и приводятся известные методы их получения:

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

1. получение скелета;

2. обработка скелета (регуляризация);

3. аппроксимация скелета прямыми линиями;

4. выделение цепочки примитивов, описывающих скелет;

5. сравнение цепочек различных изображений между собой.

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

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

Смысл этапа регуляризации заключается удалении шумовых ребер скелета, которые не являются существенными при описании общей формы фигуры [16]. Предлагается алгоритм регуляризации, основанный на процедуре восстановления исходной фигуры по ¡скелету и сравнении площадей восстанавливаемых фигур.

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

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

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

1. Цепочки устойчивы к масштабированию;

2. Цепочки устойчивы к повороту фигуры;

3. Изменение начала обхода соответствует циклическому сдвигу элементов в цепочке;

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

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

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

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

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

С помощью разработанного программного комплекса были проведены исследования метода построения скелетов Зонга-Суня. Выявлено устойчивое поведение алгоритма при масштабировании и повороте изображений. Рассмотрен вариант оптимизации выполнения алгоритма. В зависимости от размеров прирост скорости составил 3 — 11 раз.

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

Апробация разработанного программного комплекса структурного поиска происходила на коллекции изображений петроглифов Карелии. Для тестирования были отобраны 200 черно-белых изображений.

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

Приводится информация о средней скорости работы алгоритма, а также оценка эффективности работы алгоритма.

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

Среди основных преимуществ предлагаемого подхода можно выделить следующие:

1. устойчивость к масштабированию;

2. устойчивость к повороту фигуры;

3. возможность сравнения фигуры со своим зеркальным отображением;

4. возможность сравнения изображений частями;

5. высокая скорость работы.

Основной недостаток:

1. невысокая точность поиска.

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

Для коллекции изображений петроглифов Карелии были подобраны оптимальные значения параметров работы алгоритма (таблица 3.3). Также даны практические рекомендации по подбору данных параметров для других коллекций бинарных изображений (таблица 3.5). I

ЗАКЛЮЧЕНИЕ

В результате выполнения диссертационной работы получены сле

I ' дующие результаты:

1. Разработана математическая модель представления скелетов бинарных изображений в виде цепочки примитивов, состоящей из прямых ребер аппроксимированного скелета и углов' между ребрами. Для получения такого описание делается обход скелета «против, часовой стрелки». В результате обхода каждое ребро рассматривается; два раза. Получаемые цепочки примитивов обладают рядом полезных свойств: цепочки устойчивы! к: масштабированию; цепочки устойчи-. вы к повороту фигуры; изменение начала обхода скелета соответствует циклическому сдвигу элементов в цепочке; цепочка, записанная^ в обратном порядке, соответствует зеркальному отображению;, исходного скелета. ■.'■ ;. . ; .

2. Разработан алгоритм структурного поиска , в коллекции бинарных изображений с использованием скелетов, состоящий из этапов: получение скелета; регуляризация (удаление: «шумовых» ребер; скелета); аппроксимация скелета прямыми линиями; выделение цепочки примитивов;' описывающих; данный! скелет; сравнение цепочек различных изображений между собой. На каждом из этапов предложено решение с использованием существующих или разработанных новых методов. Данный алгоритм обладает рядом преимуществ и позволяет сравнивать изображения, как целиком; так и частями, с учетом их внутренней структуры.

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

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

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

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

1. Адамар, Ж. Элементарная геометрия : в 2 ч. / Ж. Адамар. Ч. 1: Планиметрия. — М.: Учпедгиз, 1948. - 608 с. Ч. 2: Стереометрия. - М.: Учпедгиз, 1951. - 760 с.

2. Афонасенко, А. В. Распознавание структурированных символов на основании методов морфологического анализа / А. В. Афонасенко // Известия Томского политехнического университета. — 2007. — Т. 311. №5.-С. 119-123.5

3. Бакут, П. А. Сегментация изображений: методы пороговой обработки / П. А. Бакут, Г. С. Колмогоров, И. Э. Ворновицкий // Зарубежная радиоэлектроника. 1987. - №10. - С. 6-24.

4. Биометрические технологии для систем распознавания человека поiизображению лица Электронный ресурс. — Электрон, ст. — Режим доступа к ст.: http://www.asia-soft.com/frs/ru/products/, свободный. -Загл. с экрана.

5. Брилюк, Д. В. Распознавание человека по изображению лица нейросе-тевыми методами / Д. В. Брилюк, В. В. Старовойтов. — Минск, 2002. — 54 с.

6. Быстров, М. Ю. Поиск изображений в графических базах данных на примере петроглифов Карелии / М. Ю. Быстров // Материалы 59-й научной студенческой конференции. Петрозаводск: ПетрГУ, 2006. - С. 87-88.

7. Вапник, В. Н. Теория распознавания образов / В. Н. Вапник, А. Я: Червоненкис. М.: Наука, 1974. - 416 с.

8. Вёрденская, Н. В. Сегментация изображений статистические модели и методы / Н. В. Верденская // Зарубежная радиоэлектроника. Успехи современной радиоэлектроники. — 2002. — № 12. — С. 33-47.I

9. Геоинформационная система ОАО РЖД Электронный ресурс. / Электрон, дан. Режим доступа: http://www.css-mps.ru/, свободный.

10. Гладкий, А. В. Формальные грамматики и языки / А. В. Гладкий. М.: Наука, 1973.

11. Гонсалес, Р. Цифровая обработка изображений У Р. Гонсалес, Р. Вудс. -М: Техносфера, 2005. 1072 с.

12. Государственный музей архитектуры имени A.B. Щусева Электронjный ресурс. / Электрон, ст. — Режим? доступа к ст.: http://www.muar.ru/ve/lconidov/prosoil/ind J .htm, свободный.

13. Гросс, М. Теория формальных грамматик / М. Гросс, А. Лантен. М.: МИР, 197,1.

14. Домахина, Л: Г. Изоморфные скелеты растровых изображений! / Л: Г. Домахина, А. Д. Охлопков // Труды меж'д. конф. "Графикон-2003".-2003.

15. Домахина, Л. Г. Регуляризация скелета для задачи сравнения формы / Л: Г. Домахина // Математические методьг распознавания образов; доклады XIV всероссийской конференции. — М.: Макс-Пресс, 20091 — С. 342-345.

16. Дуда, Р. Распознавание образов и анализ сцен / Р. Дуда, П. Харт ; перевод с англ. Г. Г. Вайештейнв и А. М. Васьковского. — М.: Мир, 1976. 509 с. .

17. Журавлев, Ю.И. Избранные научные труды // Ю.И. Журавлев. М.: Магистр, 2002. - 420 с.

18. Зозуля, Е. П. Методы автоматического анализа биосигналов с хаотическими свойствами для медицинских компьютерных систем: авто-реф. дис.канд. техн. наук: 05.11.17 / Зозуля Елена Павловна. — СПб., 2009.-18 с.

19. Кириков П. В. Об опыте создания системы управления коллекциями графических документов Электронный ресурс. / П. В. Кириков, М. Ю. Быстров, К. А. Рогова, А. А. Рогов // Электронные библиотеки.

20. Электрон, ст. — 2010. — Т. 13. № 1. — Режим доступа к ст.:http://www.elbib.ru/index.phtml?page=elbib/шs/j оигпа1/2010/рагИ /КВЫК, свободный.

21. Котович, Н. В. Распознавание скелетных образов Электронный ресурс. / Н. В. Котович, О. А. Славин. — Электрон, ст. — Режим доступа к ст.: http://ocrai.narod.ru/skeletrecognize.html, свободный.

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

23. Марр, Д. Зрение. Информационный подход к изучению представления и обработки зрительных образов / Д. Марр. М.: Радио и связь, 1987. -400 с.

24. Местецкий, Л. М. Компьютерная графика на основе жирных линий / Л. М. Местецкий // Труды межд. конф. "Графикон-2000". — М.: МГУ, 2000.-С. 165-173.

25. Местецкий, Л. М. Математические методы распознавания образов. Курс лекций / Л. М. Местецкий М.: МГУ, 2002.I

26. Местецкий, Л. М. Непрерывная морфология бинарных изображений. Фигуры. Скелеты. Циркуляры / Л. М. Местецкий. — М.: ФИЗМАТ-ЛИТ, 2009.-287 с.

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

28. Местецкий, Л. М. Скелетизация многоугольной фигуры на основе обобщенной триангуляции Делоне / Л. М. Местецкий // Программирование. 1999. -№ 3. - С. 16-31.

29. Минимальная охватывающая окружность Электронный ресурс. / Электрон. ст. Режим доступа к ст.: http://www.prografix.narod.ru/mincircle.html, свободный.

30. Новиков, Ф. А. Дискретная математика для программистов / Ф. А. Новиков. СПб.: Питер, 2000.

31. Окулов, С. М. Программирование в алгоритмах / С. М. Окулов. М.: БИНОМ. Лаборатория знаний, 2002. - 341 с.

32. Павлидис, Т. Иерархические методы в структурном распознавании образов / Т. Павлидис // Труды института инженеров по электротехнике и радиоэлектронике. 1979. - Т. 67. № 5. - С. 39-49.

33. Петроглифы Карелии Электронный ресурс. / Электрон, дан. Режим доступа: http://petroglyphs.ru/, свободный.

34. Потапов, А. С. Математические методы и алгоритмическое обеспечение анализа и распознавания изображений в информационно-телекоммуникационных системах / А. С. Потапов, И. П. Гуров,

35. B. Н. Васильев // Всероссийский конкурсный отбор обзорно-аналитических статей по приоритетному направлению "Информационно-телекоммуникационные системы". — 2008. — 46 с.1

36. Прасолов, В. В. Элементы комбинаторной и дифференциальной топологии / В. В. Прасолов. М.: МЦНМО, 2004.

37. Препарата, Ф. Вычислительная геометрия: Введение / Ф. Препарата, М. Шеймос. М.: Мир, 1989. - 478 с.

38. Равдоникас В. И. Наскальные изображения Онежского озера и Белого моря / В. И. Равдоникас. М.: Акад. наук СССР, 1936.

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

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

41. Рогов, А. А. Возможности современных информационных технологий при изучении петроглифов Беломорья / А. А. Рогов, К. А. Рогова // Сборник научных статей и докладов. Архангельск: СОЛТИ, 2006. —1. C. 473-479.

42. Труды XII Всероссийской научной конференции КСБЬ'20Ю (Казань, Россия, 13-17 октября; 2010 г.). Казань, 2010. - С. 409-414.

43. Рогов, А. А. Информационно-поисковая система петроглифов Карелии / А. А. Рогов, К. А. Рогова, К. Н. Спиридонов, М. Ю. Быстров // Вестник компьютерных и информационных технологий. — Москва, 2008.-№6,- С. 6-12.

44. Рогов, А. А. Применение методов теории распознавания для анализа петроглифов Карелии / А. А. Рогов // Материалы IX международной конференции «Интеллектуальные системы и компьютерные науки». — М.: ЦПИ МГУ, 2006. Т.2, ч. 2. - С. 260-262.

45. Рогов, А. А. Система поиска в электронной коллекции изображений петроглифов Карелии / А. А. Рогов, К. А. Рогова, К. Н. Спиридонов, М. Ю. Быстров // 10-Я1 Всероссийская конференция КСОЬ. Дубна: ОИЯИ, 2008. - С. 246-251.

46. Рогова, К. А. Задачи анализа изображений в информационно-поисковой системе РЖ8 / К. А. Рогова, М. Ю. Быстров // Математические методы, распознавания образов: 13-я Всероссийская конференция. М.: МАКС Пресс, 2007. - С. 528-530.

47. Рогова, К. А. Информационно-поисковая система «Петроглифы Карелии» / К. А. Рогова // Материалы' IX международной конференции «Интеллектуальные системы и компьютерные науки» ». — М.: ЦПИ

48. МГУ, 2006. Т.2, ч. 2. - С. 262-264.

49. Рогова, К. А. Применение компьютерных технологий при исследовании Карельских петроглифов / К. А. Рогова // Сборник научных тезисов тринадцатой международной конференции «Математика. Компьютер. Образование». —Ижевск: НИЦ, 2006. — С. 175.

50. Роджерс, Д. Математические основы машинной графики / Д. Роджерс, Дж. Адаме. М.: Мир, 2001.I120I

51. Российский семинар по оценке методов информационного поиска Электронный ресурс. / Электрон, дан. — Режим доступа: http://www.romip.ru/, свободный.

52. Савватеев, Ю. А. Каменная летопись Карелии: Петроглифы Онежского Озера и Белого моря / Ю. А. Савватеев. Петрозаводск: Карелия, 1990.- 118 с.J

53. Система распознавания автомобильных номеров «ДИГНУМ АВТО» Электронный ресурс. — Электрон, текстовые дан. — Режим доступа: http://www.dignum.ru/dignumauto/, свободный. Загл. с экрана.

54. Спиридонов, К. Н. Применение спектра обобщенных фрактальных размерностей Ренье для сравнения текстур , изображений: автореф. дис.канд. техн. наук: 05.13.18 / Спиридонов Константин Николаевич. Петрозаводск., 2008. - 19 с.1

55. Старовойтов, В. В. Локальные геометрические методы цифровой об-работки и анализа изображений / В. В. Старовойтов. — Минск, 1997.

56. Старовойтов, В. В. Методы сегментации цветных изображений / В. В. Старовойтов, М. А. Талеб. Минск: Препринт, 1999. - 44с.

57. Теория автоматов / Э. А. Якубайтис и др. // Теория вероятностей. Математическая статистика. Теоретическая кибернетика. — М.: ВИНИТИ, 1976.-Т. 13.-С. 109-188.

58. Ту, Дж. Принципы распознавания образов / Дж. Ту, Р. Гонсалес. Перевод с англ.: И. Б. Гуревича. — М.: Наука, 1979. 368 с.

59. Уоссермен, Ф. Нейрокомпьютерная техника: теория и практика / Ф. Уоссермен. Перевод: Ю. А. Зуев, В. А. Точенов. М.: ИНИОН, 1992.

60. Форсайт, Д. А. Компьютерное зрение. Современный подход / Д. А. Форсайт, Д. Понс. -М.: Вильяме, 2004. 928 с.

61. Фу, К. Структурные методы в распознавании образов / К. Фу. — М.: Мир, 1977. -.320 с.

62. Цифровая обработка изображений в информационных системах. Учебное пособие / И. С. Грузман и др. — Новосибирск: НПТУ, 2002.

63. Электронные музейные коллекции: Электронный ресурс. / Режим доступа: http://www.museum.ru/W370/, свободный.

64. Электронные библиотеки: Перспективные Методы и Технологии, Электронные коллекции: Электронный ресурс.: / Режим доступа: http://www.rcdl.ru/, свободный.

65. Ян, Д. Е. Новая технология распознавания- символов: Теория, практическая реализация; перспективы- / Д. Е. Ян, К.В.Анисимович; А. Л: Шамис.-М.: Препринт, 1995.

66. ABBYY FineReader: Интеллектуальная система: оптического, распознавания текста или OCR Электронный ресурс.17 Компания ABBYY. — Электрош дан: и прогр. . Режим доступа: http://www.abbyy.ru/finereader.

67. Attneave, F. Some Informational Aspects of Visual Perception / F. Attneave // PsychologicalReview, 61. -1954; №6l-PU83-193.

68. Bai, X. Skeletonipruning by contour partitioning with discrete curve; evolution / X. Bai; L. Jc Latecki, W.-Y. Liu II IEEE Transactions on Pattern Analysis and Machine Intelligence. 2007. - Vol. 29, № 3.— P.449-462.

69. Blum, H. A transformation for extracting new descriptors of shape / IT. Blum // In Proc. Symposium Models for the perception of speech and visual form. Cambridge: MIT Press, 1967. -P. 362-380.

70. Castelman, K. R. Digital image processing / K. R. Castelman // Prentice hall.- 1996.

71. Chen, L. II. An Animation Synthesis System. Based on 2D Skeleton Structures of Images,/ L.H.Chen, C. J. Yu, Т. C. Lo // Сотр. Graphic Workshop. 2004.

72. Cognitive OpenOCR (Cuneiform): Система оптического распознавания Электронный ресурс. /. Компания Cognitive Technologies. — Электрон.дан. и прогр. — Режим доступа:http://www.cognitive.ru/products/cuneiform.

73. De Mori, R. A descriptive technique for automatic speech recognition /

74. R. De Mori // IEEE Transactions on Audio and Electroacoustics. — 1973.i

75. Vol. Au-21, №. 2. P. 89-100.

76. Dehne, F. The big sweep: On the power of the wavefront approach to Vo-ronoi Diagrams / F. Dehne, R. Klein // Algorithmica. 1997. - Vol. 17(1). -P. 19-32.

77. Deng, W. A fast parallel thinning algorithm for the binary image skeletonization / W. Deng, S. Iyengar, N. Brener // The International Journal of High Performance Computing Applications. 2000. — Vol. 14, № 1. -P. 65-81.

78. Fortune, S. A sweepline algorithm for Voronoi diagrams / S. Fortune // Algorithmica. -1987. Vol. 2. - P. 153-174.

79. Freeman, H. On the encoding of arbitrary geometric configurations /i t

80. H. Freeman // IEEE Transactions on Electronic Computers. — 1961. Vol.i1. EC-10,-№6.-P. 260-268.

81. Fu, K. A survey on image segmentation / K. Fu, J. Mui // Pattern Recognition. 1981.-№13.-P. 3-16.

82. Haralick, R. M. Statistical and Structural approaches to texture / R. M. Haralick // Proceedings of the IEEE. 1979. - P. 786-804.

83. Kirkpatrick, D. G. Efficient computation of continuous skeletons / D. G. Kirkpatrick // In Proceedings of the 20th Annual IEEE Symposium on FOCS. 1979. - P. 18-27.

84. Klein, R. Fast skeleton construction / R. Klein, A. Lingas // In Proc. 3rd Europ Symp on Alg. (ESA'95). -- 1995.

85. Lam, L. An Evaluation of Parallel Thinning Algorithms for Character Recognition / L. Lam, C. Y. Suen // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1995. - Vol. 17, №9. - P. 914-919.

86. Lee, D. T. Medial axes transform of planar shape / D. T. Lee // IEEE Trans. Patt. Anal. Mach. Intell. PAMI-4. 1982. - №4. - P. 363-369.

87. Lu, H. E. A comment on «A Fast Parallel Algorithm for Thinning Digital Patterns» / H. E. Lu, P. S. P. Wang // Commun. ACM. 1986. - Vol. 19, №3. — P. 239-242.

88. Lutsiv, V. Hierarchical structural matching algorithms for registration of aerospace images / V. Lutsiv, I. Malyshev, A. Potapov // Proc. SPIE. -2003.-Vol. 5238.-P. 164-175.

89. Manning, C. D. An Introduction to Information Retrieval / C. D. Manning, P. Raghavan, H. Schütze. — Cambridge: Cambridge University Press, 2009. 544 p.

90. Mestetskii, L. M. Continuous approach to segmentation of handwritten text / L. M. Mestetskii, I. A. Reyer, T. W. Sederberg // Proceedings of-8th International Workshop on Frontiers in Handwriting Recognition (IWFHR-8).-2002.-P. 440-445.

91. Mestetskii, L. Binary image skeleton continuous approach // L. Mestetskiy, A. Semenov // Proceedings of the Third International conference on computer vision theory and applications (VISAPP 2008). — Portugal, 2008.-Vol. l.-P. 251-258.

92. Montanari, U. A note on minimal length polygonal approximation of a digitized contour / U. Montanari // Communications of ACM. — 1970. -Vol. 13, № l.-P. 41-47. 1

93. Montanari, U. Continuous skeletons from digitalized images / U. Montanari // Journal ACM. 1969. - Vol. 16, № 4. - P. 534-549.

94. Rosenfeld, A. A characterization of parallel thinning algorithms / A. Rosenfeld // Information and control. 1975. - Vol. 29. - P. 286-291.

95. Shaked, D. Pruning medial axes / D. Shaked, A. M. Bruckstein // Computer Vision and Image Understanding. 1998. - Vol. 69, № 2 - P. 156-169.

96. Sklansky, J. Minimal-perimeter polygons of digitized silhouettes / J. Sklansky, R. L. Chazin, B. J. Hansen // IEEE transactions of computers. 1972. - Vol. C-21, №3. - P. 260-268.

97. Sobel, I. A 3x3 isotropic gradient operator for image processing / I. Sobel, G. Feldman // Stanford Artificial Project. 1968.

98. Stallings, W. W. Recognition of printed Chinese characters by automatic pattern analysis / W. W. Stallings // Computer Graphics and Image Processing. 1972. - Vol. 1. - P. 47-65.

99. Strzodka, R. Generalized Distance Transforms and Skeletons in Graphics Hardware / R. Strzodka, A. Telea // Joint Eurographics IEEE TCVG Symposium on Visualization. - 2004.

100. Tanase, M Shape Decomposition and Retrieval / M. Tanase // PhD Thesis, Utrecht University. — 2005. ' 1

101. Telea, A. An augmented fast marching method; for computing skeletons and centerlines / A. Telea, J. J. Van Wijk // Joint EUROGRAPI1ICS-IEEE TCVG Symposium on Visualization.- 2002.- P. 251-260.

102. Verma, B. Pattern Recognition Technologies and Applications: Recent Advances / B. Verma, M. Blumenstein. USA: IGI Global Press, 2008; -453 p.

103. Yap, C. K. An 0(n log n) algorithm for the Voronoi diagram of the set of simple curve segments / C. K. Yap // Discrete Computational Geometry. -1987.-Vol. 2.-P. 365-393.

104. Zhang, T.Y. A fast parallel algorithm for thinning digital patterns / T. Y. Zhang, C. Y. Suen // Commun. ACM. 1984. - Vol. 27, №3. -P. 236-239,