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

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

Москаленко Станислав Владимирович

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

Специальность: 05.13.12 - Системы автоматизации проектирования (приборостроение)

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

9 11 ЮН 2011

Санкт-Петербург - 2011

4849058

Работа выполнена в Санкт-Петербургском государственном университете информационных технологий, механики и оптики.

Научный руководитель д.т.н, проф. Гатчин Ю.А.

Официальные оппоненты д.т.н, проф. Дегтярев В.М.

к.т.н, доц. Меженин А.В.

Ведущая организация Санкт-Петербургский государственный

университет аэрокосмического приборостроения

Защита состоится 31 мая 2011 г. в 15 часов 50 минут на заседании диссертационного совета Д212.227.05 в Санкт-Петербургском государственном университете информационных технологий, механики и оптики по адресу: 197101, г. Санкт-Петербург, Кронверкский пр., 49.

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

Автореферат разослан « 30 » апреля 2011 г.

Ученый секретарь

диссертационного совета Д212.227.05, к.т.н., доцент /Р-О ^ ""7 Поляков В.И.

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

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

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

Цели и задачи диссертационной работы. Цель диссертационной работы состоит в разработке новых эффективных методов и алгоритмов векторизации графических документов в САПР.

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

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

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

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

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

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

6. Реализована программная версия предложенных алгоритмов, методов, и моделей, проведена оценка их эффективности.

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

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

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

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

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

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

Практическая ценность. Теоретические и практические результаты, полученные в диссертационной работе, использованы в НИР №21084 «Модернизация программных компонентов системы геоинформационной поддержки на основе использования 3-0 моделирования».

Также результаты работы внедрены в Комитет по молодежной политике и взаимодействию с общественными организациями, являющийся исполнительным органом государственной власти Санкт-Петербурга, в составе модуля сканирования проекта электронного документооборота СЭДЦ ИОГВ.

Выполнена реализация основных результатов в системе оцифровки проектно-конструкторской документации для ЗАО «Институт телекоммуникаций», Санкт-Петербург.

Выполнено внедрение результатов в учебный процесс на кафедре Проектирования компьютерных систем СПбГУ ИТМО, дисциплина «Основы проектирования электронных средств».

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

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

2. Группа векторных моделей описания графических документов и эффективные алгоритмы их построения.

3. Алгоритм вычисления пороговых значений для автоматизации процессов построения векторного представления и сегментации графических объектов на растре.

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

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

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

Апробация работы и публикации. Основные положения работы докладывались на 9 научных конференциях, включая IV Межвузовскую конференцию молодых ученых (Санкт-Петербург, 2007), Всероссийскую научно-практическую конференцию «Информационные технологии в профессиональной

деятельности и научной работе» (Йошкар-Ола, 2007), XXXVII Научную и учебно-методическую конференцию СПбГУ ИТМО (Санкт-Петербург, 2008),

V Всероссийскую межвузовскую конференцию молодых ученых (Санкт-Петербург, 2008), XXXVIII Научную и учебно-методическую конференцию СПбГУ ИТМО (Санкт-Петербург, 2009),

VI Всероссийскую межвузовскую конференцию молодых ученых (Санкт-Петербург, 2009), XXXIX Научную и учебно-методическую конференцию СПбГУ ИТМО, посвященную 100-летию со дня рождения выдающего ученого и талантливого педагога М.М. Русинова (Санкт-Петербург, 2010),

VII Всероссийскую межвузовскую конференцию молодых ученых (Санкт-Петербург, 2010), ХЬ Научную учебно-методическую конференцию СПбГУ ИТМО (Санкт-Петербург, 2011).

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

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

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

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

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

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

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

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

чего выполняется линейная аппроксимация найденных осевых линий. В результате формируется модель изображения в виде наборов ломаных, стыкующихся в своих концевых точках. Для данной схемы методы выделения осевых линий можно разделить на пять групп: (1) основанные на утоньшении линий, (2) основанные на сопоставлении контуров, (3) основанные на графах объектных штрихов, (4) основанные на разбиении изображения регулярной сеткой, (5) основанные на разреженном просмотре растра. Также существуют другие схемы построения векторных моделей: основанные на преобразовании Хафа, основанные на аппроксимации объектов растра площадными геометрическими фигурами.

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

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

Подходы к улучшению векторных моделей можно разбить на 4 группы: 1. для обработки большого числа однотипных документов эффективным вариантом служит разработка специализированных векггоризационных систем; 2. использование специальных параметров, описывающих «идеальную» геометрию желаемого результата; 3. использование простых эвристик для корректировки векторных моделей; 4. подходы, основанный на применении моделей описания «идеальных» соединений: Т-соединений, Ь-соединений, У-сосдинешш, X-соединеннй.

Основная проблема, стоящая при применении данных подходов -необходимость задания пороговых значений и других параметров.

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

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

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

3. Существующие векторные модели описания растровых графических документов не являются достаточно эффективными.

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

5. Необходима разработка программного обеспечения реализующего решение вышепредставлениых проблем.

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

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

Итак, векторная модель изображения сводится к набору ориентированных графов. Все векторные объекты можно разделить на типы: линия или площадной объект. Соответственно, видов отношений между типами может быть три: «линия <-> площадной объект», «площадной объект «-» линия», «пиния *-* линия». Отношение «площадной объект <-> площадной объест» игнорируется по причине отсутствия информации о связях между объектами данного типа, получаемой в процессе векторизации. Пусть L2 - рассматриваемый отрезок, a L: для типа «линия *-*■ линия» - отрезок смежный с f,;', когда для типа «линия <-> площадной объект» Lj будет отрезком, соединяющим точку пересечения данных объектов с точкой центра масс площадного объекта. Отношения между объектами можно характеризовать следующими величинами:

• относительный угол а - величина острого утла между L2 и L;:

• относительная длина rl - величина отношения длины L? к

• относительная точка пересечения двух отрезков ri. Здесь для L2 величина п будет отношением наименьшего сегмента отрезка L2, полученного в результате пересечения Ь2 и Lh к наибольшему сегменту.

Сами объекты можно характеризовать следующими величинами:

• тип объекта type, который для линейного объекта равен 1, для площадного объекта равен 2;

• вид объекта (стиль) st, который в случае линейного объекта может быть принят равным ! для тонкой линии, равным 2 для основной линии.

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

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

• Graphs - таблица, хранящая все сущности графов в системе, где edgeld соответствует ссылкам на все дуги, принадлежащие графу; nodeld - ссылкам на все вершины графов;

• Nodes - таблица, хранящая все сущности вершин графов в системе, которая имеет ссылки на тип и на стиль примитива; также содержит ссылки на дуги графа, сопряженные с отдельной вершиной;

• Edges - таблица, хранящая все сущности дуг графов в системе, которая содержит ссылки на вершины, с которыми данное ребро сопряжено; также таблица содержит характеристики отношений (a, rl, ri) между примитивами;

• Types - таблица, хранящая все типы объектов в системе; также содержит ссылки на подтипы - стили;

• Styles - таблица, описывающая все стили в системе.

Рис. 1. Структура данных для описания графических объектов

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

описательными величинами изображен на рис. 3.

•>._ 3

Л

1 7 4 _

Рис. 2. Фрагмент растрового чертежа

Следует отметить, что помимо атрибутов дуг (а, И, п), изображенных на рис.3, каждой вершине графа приписаны атрибуты туре = 1 и ¡т = 2.

г! ТТ7Л

К Л

« 1 г/ 1 ;■/1 « 771

45 | 0 11/4|45 а1

^ -пт ч | п

п: 4Т|_0

Рис. 3. Описание растрового объекта в виде графа

Задача распознавания графических образов может быть решена путем реализации вычисления степени соответствия между входными и эталонными графами. Процесс сравнения графов есть последовательное сопоставление дуг и вершин двух графов. Для сопоставления двух графов могут быть применены метрики, описывающие графические объекты, которые представлены выше. Пусть даны 2 графа g = (уа, еаЬ), где а,Ь - и С = (V,-, £,;,-), где Ц = 1,..., I. Здесь представляют вершины обоих графов, еаЬ, - дуги обоих графов, g н С - граф растрового объекта и эталонный граф в БД соответственно.

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

= М „,ЕП) + Ц(у„,V,), (1)

«»1 1*1 у=[ о=1 «1

где ; здесь Ма1 означает наличие или отсутствие соответствия

ы "

вершины va графа § вершине V, графа С.

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

а -а, I п, - п. I и_г/1

Dis(e^E|j) = ^-- + ^-+ П (2)

л7 2 2

Расстояние между двумя вершинами:

^¡(П'ре, - 1урег)- + -хи)- (3)

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

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

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

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

Следуя в одном направлении необходимо провести через одну из полученных пар точек прямую таким образом, чтобы образовалось поперечное сечение (рис. 5).

Рис 4. Схема алгоритма определения пороговых значений

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

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

• окружность ни разу не пересекла растровый объект, что говорит о конце линейного примитива;

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

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

Обозначения Ширина линии <_»

Точка средней линии •

Сканирующая линия обнаруживает объект в точке То

Превышение толщины пинии сигнализирует о ветвлении

Рис. 5. Вычисление точек средней линии растрового объекта

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

Для площадных объектов, оценка методов первичной векторизации выявила актуальность разработки улучшенного решения для задачи определения границ. В контексте бинарных изображений типовой метод проверки на причастность точки (пикселя) границе области объекта таков: точка с координатами (¿, у) считается граничной, если /д = 1; и в 8-окрестностях точки (/',;') имеются как объектные, так и фоновые точки. Здесь /у - функция определения цвета в точке с координатами (/, Д /у = 1 для черного пикселя, /¡, = 0 для белого. Трудоемкость работы метода пропорциональна объему растра {~М*М). Используя данный метод можно выделять граничные пиксели (контуры) на растре, формируя из них последовательные цепочки. У представленного типового метода есть ряд недостатков. Во-первых, его трудоемкость достаточно велика, можно вместо попиксельного сканирования растра использовать разреженную выборку. Во-

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

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

1. Ложное направление следования процедуры отслеживания контура

Обозначения

Направление "

Начальная точка «

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

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

2. Верное направление следования

Рис.7. Схема алгоритма векторизации площадных объектов на растровом изображении

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

Оценка результативности векторизации происходит на двух уровнях: • На пиксельном уровне выявляется степень сохранения формы

объектов после преобразований. Для этого используется ряд коэффициентов.

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

|Р„пР(,|

Показатель ложного соответствия пикселей. Данный показатель вычисляется по формуле:

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

PC = aDp+(\-a)(\-Fp), (3)

где 0 < а < 1 является степенью важности подлинного соответствия пикселей относительно ложного соответствия (1 - а).

• На векторном уровне выявляется степень подобня исходных

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

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

Q^c) = Qpl{c)QK{c)Qst{c)Qlype{c)l*-, (4)

Коэффициент качества определения концевых точек: MiA*tk(c)}

Qp,(c) = e ™ , (5)

где с/,(с) ((' = 1, 2) являются расстояниями от концевых точек сегмента с по перпендикулярам к средней линии объекта g. W(g) - линейная ширина объекта g. Коэффициент качества определения линейной ширины:

Qv(c) = e~ ; (6)

Коэффициент качества определения стиля линейного объекта:

= (7)

где Style(I) является значением равным 1 для основной линии, 2 для пунктирной, 3 для иприхпунктирной.

Коэффициент качества определения типа линейного объекта:

Q^M-e^*™**, (8)

где Туре{1) является значением равным 1 для линейного объекта, 2 - для площадного.

Единичный линейный растровый объект может быть задан несколькими векторами. Пусть D(g) - набор результирующих векторов, определяющих исходный линейный объект g. Пусть /(г>) - длина любого линейного сегмента и. В таком случае качество векторизации объекта g:

zteDig)<e0(kng)Kkng)) Qv(g) =-; (9)

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

QJg)l(g)

D —s-J:---(10)

Ошибка определения вектора. Дня начала необходимо определить величину Q,(k), которая рассчитывается схожим с Qdg) образом, только расчет идет относительно, результирующего вектора к, а не относительно фонового объекта g. Предположим, что G(k) является набором всех растровых линейных объектов, которые имеют пересечения с данным вектором /с, тогда:

> и и

ma x(l(k),Z giG(k)l(k п g))

Показатель 0„(к) огражает степень соответствия к исходному линейному объекту. Следовательно, ошибка определения вектора:

17

= 1 - ОХк);

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

Р„=-^-; (13)

I иу„Кк)

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

ГС = /Ю0+(1-/?Х1-^и), (14)

где /? - отношение степеней важности качества и ошибки, величина аналогичная а из формулы 3. В данном контексте величинам а и /? приписаны значения 0,5. Тем самым задается эквивалентность важности истинного определения и ложного.

В итоге РС и УС формируют комбинированный индекс оценки алгоритма:

Се/ = /РС + (1-г)КС, (15)

где у — 0,5 в текущем контексте.

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

Таблица 1 «Оценка работы современных алгоритмов векторизации»

Решение ТрейсИкс КхЗро^^П Рго 8 ОТХ1шаяе САБ

<1р1 150 300 450 150 300 450 150 300 450

эр 0,77 0,84 0,87 0,67 0,76 0,80 0,69 0,76 0,83

Рр 0,20 0,15 0,13 0,30 0,25 0,21 0,27 0,21 0,17

РС 0,79 0,85 0,87 0,69 0,76 0,83 0,71 0,79 0,84

а (с) 0,80 1 1 0,80 0,83 0,84 0,80 0,43 0,84

0,74 0,87 0,95 0,72 0,85 0,90 0,74 0,88 0,94

0,26 0,14 0,05 0,28 0,14 0,10 0,26 0,13 0,08

УС 0,74 0,87 0,95 0,74 0,86 0,90 0,73 0,84 0,89

€(¿1 0,77 0,86 0,91 0,72 0,81 0,87 0,73 0,82 0,88

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

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

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

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

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

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

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

6. Проведены экспериментальные исследования, подтверждающие работоспособность и эффективность предложенных подходов и решений.

Публикации автора по теме диссертационно» работы

1. Москаленко C.B., Гатчин Ю.А. Алгоритм вычисления пороговых значений для повышения автоматизма систем распознавания графических образов // Научно-технический весгник. СПб: СПбГУ ИТМО, 2010. Вып. б. - С. 89-94. (статья из перечня ВАК)

2. Москаленко СВ., Гатчин Ю.А. Оптимизация алгоритмов идентификации графового изоморфизма// Научно-технический вестник. СПб: СПбГУ ИТМО, 2010. Вып. 2. - С. 98-104. (статья из перечня ВАК)

3. Москаленко C.B., Гатчин Ю.А Помехоустойчивый волновой алгоритм векторизации линейных растровых объектов // Вестник компьютерных и информационных технологий. М., Машиностроение, 2009. Вып.5. - С. 16-21. (статья из перечня ВАК)

4. Москаленко С. В. Волной алгоритм векторизации линейных растровых изображений Научно-технический вестник СПбГУ ИТМО. Выпуск 51. -СПб: СПбГУ ИТМО, 2008. - С. 16-21.

5. Москаленко С. В. Волной алгоритм векторизации линейных растровых изображений // Сб. тезисов V Межвузовской конф. молодых ученых.-СПб: СПбГУ ИТМО, 2008. - С.295.

6. Москаленко С. В. Алгоритм векторизации примитивов бинарных растровых изображений // Сборник материалов всероссийской научно-практической конференции с международным участием "Информационные технологии в профессиональной деятельности и научной работе". - Йошкар-Ола: Марийский государственный технический университет, 2007. - С.221-224.

7. Москаленко С. В. Система автоматизированной векторизации чертежей // Сб. тезисов IV Межвузовской конф. молодых ученых, - СПб: СПбГУ ИТМО, 2007.-С, 117.

Тиражирование и брошюровка выполнены в учреждении «Университетские телекоммуникации» 197101, Санкт-Петербург, Саблинская ул., 14 Тел. (812) 233 4669 объем 1 п.л. Тираж 100 экз.

ВВЕДЕНИЕ.

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

1.1 Этапы преобразования изображений из растровой формы в векторную.

1.2 Основные определения: Виды изображений.:.

I 1.3 Сегментация изображений.'.

1.4 Обзор существующих методов первичной векторизации.

1.4.1 Методы выделения осевых линий, основанные' на преобразовании Хафа.

1.4.2 Методы выделения осевых линий, основанные на сопоставлении контуров.

1.4.3 Методы выделения осевых линий, основанные на графах объектных штрихов растра.

1.4.4 Методы выделения осевых линий, основанные на разбиении растра регулярной сеткой.

1.4.5 Методы выделения осевых линий, основанные на разреженном просмотре растра.

1.4.6 - Методы определения осевых линий, основанные на утоньшении линий (методы скелетизации).

1.4.7 Линейная аппроксимация.

1.5 Постобработка результатов первичной векторизации.

1.6 Выводы.

ГЛАВА 2. ПОСТРОЕНИЕ ВЕКТОРНЫХ МОДЕЛЕЙ ОПИСАНИЯ ГРАФИЧЕСКИХ ДОКУМЕНТОВ.

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

2.2 Технология сопоставления графов для задач распознавания графических образов.

2.3 Оптимизирующие критерии для процесса идентификации изоморфизма графов.

2.4 Функция вычисления степени соответствия графов.

2.5 Выводы.

ГЛАВА 3. РАЗРАБОТКА АЛГОРИТМОВ ПЕРВИЧНОЙ ВЕКТОРИЗАЦИИ.

3.1 Алгоритм первичной векторизации линейных графических объектов.

3.2 Алгоритм первичной векторизации площадных графических объектов.

3.3 Алгоритм вычисления пороговых значений.

3.4 Выводы.

ГЛАВА 4. РЕАЛИЗАЦИЯ ПРЕДЛОЖЕННЫХ МЕТОДОВ И АЛГОРИТМОВ, ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА ИХ ЭФФЕКТИВНОСТИ.

4.1 Функционально-структурные модели системы.

4.2 Описание программной реализации модуля ТрейсИкс.

4.2.1 Модульность системы за счет технологии ]ауа-апплетов.

4.2.2 Обзор общей логической схемы работы программы.

4.2.3 Оценка производительности алгоритма вычисления пороговых значений.

4.3 Оценка эффективности разработанных методов и алгоритмов.

4.4 Выводы.

Актуальность темы.

Технологии преобразования растровых чертежей, полученных путем оцифровки традиционных источников - бумажных носителей, векторную, форму в настоящий момент являются'весьма востребованными* Это:связанос развитием систем автоматизированного проектирования, которые способны ■ интерпретировать векторный формат, а такжё с существенными преимуществами векторной1 формы по сравнению с растровым представлением: простота манипуляций и- управления, необходимость в меньшем объеме памяти и др. Под векторной формой понимается модель (структура) данных, представляющая собой упорядоченный набор* слоев объектов, которые моделируются точками, ломаными либо-многоугольниками, расположенными на плоскости или сфере с заданной системой координат. Процесс преобразования изображений из растровой формы в векторную называется векторизацией.

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

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

Цели и задачи диссертационной работы.

Цель диссертационной работы состоит в разработке новых эффективных методов и алгоритмов векторизации графических документов в САПР.

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

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

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

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

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

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

6. Реализована программная версия предложенных алгоритмов, методов, и моделей, проведена оценка их эффективности.

Научная новизна.

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

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

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

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

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

Практическая ценность.

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

Теоретические и практические результаты, полученные в диссертационной работе, использованы в НИР №21084 «Модернизация программных компонентов системы геоинформационной поддержки на основе использования 3-Б моделирования».

Также результаты работы внедрены в Комитет по молодежной политике и взаимодействию с общественными организациями, являющийся исполнительным органом государственной власти Санкт-Петербурга, в составе модуля сканирования проекта электронного документооборота СЭДДИОГВ.

Выполнена реализация основных результатов в системе оцифровки проектно-конструкторской документации для ЗАО «Институт телекоммуникаций», Санкт-Петербург.

Выполнено внедрение результатов в учебный процесс на кафедре Проектирования компьютерных систем СПбГУ ИТМО, дисциплина «Основы проектирования электронных средств».

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

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

2. Группа векторных моделей описания графических документов и эффективные алгоритмы их построения:

3. Алгоритм вычисления пороговых значений для автоматизации процессов построения векторного представления и сегментации графических объектов на растре.

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

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

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

Апробациялработы и публикации;

Основные положения работы докладывались на следующих научных конференциях:

1. IV Межвузовская конференция молодых ученых (Санкт-Петербург,

2007).

2. Всероссийская научно-практическая конференция «Информационные технологии в профессиональной деятельности и научной работе» (Йошкар-Ола, 2007).

3. XXXVII научная и учебно-методическая конференция СПбГУ ИТМО (Санкт-Петербург, 2008).

4. V Всероссийская межвузовская конференция молодых ученых (Санкт-Петербург, 2008).

5. XXXVIII научная и учебно-методическая конференция СПбГУ ИТМО (Санкт-Петербург, 2009).

6. VI Всероссийская межвузовская конференция молодых ученых (Санкт-Петербург, 2009).

7. XXXIX научная и учебно-методическая конференция СПбГУ ИТМО, посвященная 100-летию со дня рождения выдающего ученого и талантливого педагога М.М. Русинова (Санкт-Петербург, 2010).

8. VII Всероссийская межвузовская конференция молодых ученых (Санкт-Петербург, 2010).

- 9. XL научная и учебно-методическая конференция СПбГУ ИТМО (Санкт-Петербург, 2011).

Публикации.

По теме диссертационной работы опубликовано 7 печатных работ, 3 из которых из перечня журналов ВАК:

1. Москаленко C.B., ГатчинЮ.А. Алгоритм вычисления пороговых значений для повышения автоматизма систем распознавания графических образов // Научно-технический вестник. СПб: СПбГУ ИТМО, 2010. Вып. 6. -С. 89-94. (статья из перечня ВАК)

2. Москаленко C.B., Гатчин Ю.А. Оптимизация алгоритмов идентификации графового изоморфизма // Научно-технический вестник. СПб: СПбГУ ИТМО, 2010. Вып. 2. - С. 98-104. (статья из перечня ВАК)

3. Москаленко C.B., ГатчинЮ.А. Помехоустойчивый волновой алгоритм векторизации линейных растровых объектов // Вестник компьютерных и информационных технологий. М., Машиностроение, 2009. Вып.5. - С. 16-21. (статья из перечня ВАК)

4. Москаленко С. В. Волной алгоритм векторизации линейных растровых изображений Научно-технический вестник СПбГУ ИТМО. Выпуск 51. - СПб: СПбГУ ИТМО, 2008. - С. 16-21.

5. Москаленко С. В. Волной алгоритм векторизации линейных растровых изображений // Сб. тезисов V Межвузовской конф. молодых ученых.- СПб: СПбГУ ИТМО, 2008. - С.295.

6. Москаленко С. В. Алгоритм векторизации примитивов бинарных растровых изображений // Сборник материалов всероссийской научно-практической конференции с международным участием "Информационные технологии в профессиональной деятельности и научной работе". - Йошкар-Ола: Марийский государственный технический университет, 2007. — С.221-224.

7. Москаленко С. В. Система автоматизированной векторизации чертежей // Сб. тезисов IV Межвузовской конф. молодых ученых. - СПб: СПбГУ ИТМО, 2007. - С.117.

4.4 Выводы

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

Рассматривается функционально-структурная модель программного модуля ТрейсИкс, описание пользовательского интерфейса, также прилагается краткая инструкция по работе в данном модуле.

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

ЗАКЛЮЧЕНИЕ

В диссертационной работе:

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

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

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

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

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

1. Tombre Karl, Graphics Recognition: The Last Ten Years and the Next Ten Years // W. Liu and J. Llad'os (Eds.): GREC 2005, LNCS 3926, 2006, pp. 422-426.t

2. Tombre K., Graphics Recognition—What Else? // J.-M. Ogier, W. Liu, and J. Llados (Eds.): GREC 2009, LNCS 6020, 2009, pp. 272-277.

3. Amin T.J., R. Kasturi, Recognition of Lines-and Symbols in Maps // SPIE Hybrid Image*Processing, 1986, Vol. 639, pp. 117-122.

4. Kasturi R., R. Raman, Document Image Analysis: An overview of techniques for Graphics Recognition // Springer-Verlag, Structured Document Image Analysis, 1992, pp. 285-324.

5. Kolesnikov A.N., V.V. Belekhov, Vectorization of Raster Images // Pattern Recognition and Image Analysis, 1996, Vol. 6(4), pp. 786-794.

6. Tombre К., C. Ah-Soon, Stable and Robust Vectorization: How to Make the Right Choices // Springer-Verlag, Graphics Recognition« Recent Advances, 2000,- pp. 3-Г8.

7. Абламейко C.Bt, О.И. Семенков, Обработка и, отображение информации в растровых графических системах. Минск: ИТК АН БССР. - 1989, с. 180.

8. Tombre К., Analysis of Engineering Drawings: State of the Art and Challenges // Springer Verlag, Lecture Notes in Computer Science, 1998, Vol. 1389, pp. 257-264.

9. Сойфер В.А. Методы компьютерной обработки изображений. М: ФИЗМАТЛИТ. - 2003, с. 784.

10. Москаленко С.В. Система автоматизированной векторизации чертежей. Сб. тезисов IV Межвузовской конф. молодых ученых. -СПб: СПбГУ ИТМО. - 2007.

11. Куконин А. Г. Автоматизация проектирования в машиностроении. -Мн.,- 1983, с. 130-133.

12. Кучуганов В. П: Автоматизация обработки сложной графической информации. Горький, - 1984, с. 78-91.

13. Форсайт Дэвид А., Жан Понс Компьютерное зрение. Современный подход. : Пер. с англ. М.: Издательский дом "Вильяме". - 2004, с. 424-427.

14. Tombre К.,: Salvatore Tabbone, Text/Graphics Separation Revisited», // D. Lopresti, J. Hu; and R.Kashi (Eds.): DAS 2002, LNCS 2423, SpringerVerlag, 2002, pp. 200-211.

15. Wong K.Y., R.G. Casey,. Document Analysis System // IBM Journal of Research and Development, 1982, Vol: 26(6), pp. 647-656.

16. Appiani E;, F. Cesarini, Automatic document, classification and indexing in high-volume applications // International Journal on Document Analysis and Recognition; Vol; 4(2),pp; 69—83:

17. Kaneko Т., Line Structure Extraction from Line-Drawing Images // Pattern Recognition, 1992, Vol. 25(9), pp. 963-973.

18. Dori D., L. Wenyin, Vector-Based^ Segmentation: of Text Connected to Graphics in Engineering Drawings // Lecture Notes in Computer Science, 1996, Vol. 1121, pp: 322-331.

19. Fletcher L. A., R. Kasturi, A Robust Algorithm for Text String Separation from Mixed Text/Graphics Images // IEEE Transactions on PAMI, 1988, Vol. 10(6), pp. 910-918.

20. Heijmans H.J., Morphological Image Operators // Boston, Academic Press, 1994.

21. Serra J., Image Analysis and Mathematical Morphology // London, Academic Press, 1982.

22. Tombre К., C. Ah-Soon, Stable, Robust and Off-the-Shelf Methods for Graphic Recognition // Proceedings of 14th International, Conference on-Pattern Recognition, Brisbane, Australia, 1998, pp. 406-408.

23. Wenyin Liu, Jian Zhai, Extended Summary of the Arc Segmentation Contest // D. Blostein and Y.-B! Kwon (Eds.): GREG 2002, LNCS 2390, 2002, pp. 343-349.

24. Feng Su, Jiqiang Song, A Vectorization System- for Architecture Engineering Drawings // GREG' 2005-, 2005(11-12).

25. Новиков Ю. JI. Эффективные алгоритмы векторизации растровых изображений и их реализациям геоинформационной'системе Диссер. работа. - Томск: Томский гос. университет. - 2002.

26. Wenyin Liu, Dov Dori; A Survey of Non-thinning Based Vectorization Methods // Faculty of Industrial Engineering ands Management'Technicon -Israel Institute of Technology, 1996, pp. 230-241.

27. Шапиро JI., Дж. Стокман Компьютерное зрение. Пер; С англ. - М.: БИНОМ'. - 2006; с. 752'.

28. O'Gorman F., М.В. Clowes, Finding picture edges through collinearity of future points // IEEE Trans. Comput., 1976, Vol. C-25, pp. 449-454.

29. Jimenez J;, J.L. Navalon, Some Experiments in Image Vectorization // IBM J. Res. Develop., 1982, Vol. 26, pp. 724-734.

30. Antoine D., S. Collin, Analysis of Technical Documents: The REDRAW System // Springer-Verlag, Structured Document Image Analysis, 1992, pp. 385-402.

31. Ghang F., N.A. Langrana, Perfecting Vectorized Mechanical Drawings // Computer Vision and Image Understanding, 1996, Vol. 63(2), pp. 273-286.

32. Fan K.C., D:F. Chen, Skeletonization of Binary Images with Nonuniform Width via Block Decomposition and Contour Vector Matching // Pattern Recognition, 1998, Vol. 31(7), pp. 823-838.

33. Han C.C., K.G. Fahn, Skeleton Generation of Engineering Drawings via Contour Matching//Pattern Recognition, 1994, Vol. 27(2), pp. 261-275.

34. Boatto L., An. Interpretation System for Land Register Maps // IEEE Computer, 1992, Vol. 25(7), pp. 25-32.

35. Zenzo S. Di, A. Morelli, Useful Image Representation7/ Proceedings of the 5th International Conference. on Image Analysis and Processing, Word Science Publishing, Singapore, 1989, pp. 170-178.

36. Monagan G., M; Roosli, Appropriate Base Representation Using a Run Graph // Proceedings of the 2nd International Conference on Document Analysis anf Recognition, Tsukuba, Japan, 1993, pp. 623-626.

37. Zenzo S. Di, L. Cinque, Run-Based Algorithms for Binary Image Analysis and Processing // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, Vol. 18(1), pp. 83-89. .

38. Ramachandran K., A Coding Method, for Vector Representation of Engeneering Drawings // IEEE Proceedings, 1980; Vol. 68;. pp. 813-817.

39. Lin X., S. Shimotsuj i, Efficient Diagram: Understanding with Characteristic Pattern Detection // Computer Vision, Graphics andi Image Provessing, 1985, Vol. 30, pp. 84-96.

40. Vaxiviere P., K. Tombre, Subsampling: A Structural Approach to Technical, Document Vectorization // Shape; Structure and Pattern Recognition, World Scientific, 1995, Vol. 323-332. '

41. Vaxiviere P., K. Tombre, Cellestin: CAD Conversion of Mechanical Drawings //IEEE Computer,.1992, Vol. 25(5), pp. 46-54.53; Chiang J., S.C. Tue, A New Algorithm for Line Image Vectorization // Pattern Recognition, 1998, Vol. 31(10), pp. 1541-15491

42. Chai Ii, D; Dori, Orthogonal Zig-Zag: An Efficient Method for Extracting Lines from Engineering Drawings // Visual Form, Plenum Press, New York -London, 1992, pp. 127-136.

43. Dori D., Y. Liang, Space Pixel Recognition of Primitives in Engineering Draiwings // Machine Vision and Applications, 1993; Vol. 6, pp. 79-82.

44. Liu W., D. Dori, Sparce Pixel Tracking: A Fast Vectorization Algorithm-Applied to Engineering Drawings // Proceedings of the 13th International Conference on Pattern Recognition Volume 3 (Robotics and Applications), Vienna, Austria, 1996, pp. 808-811.

45. Dori D., Orthogonal Zig-Zag: an Algorithm for Vectorizing Engineering Drawings Oonmpared with Hough Transfrom* // Advances in Engineering Software, 1997, Vol. 28(1), pp. 11-24.

46. Deutsch E.S., Thinning Algorithms on Rectangular, Hexagonal, and Triangular Arrays // Comm. ACM, 1972, Vol; 15(9), pp. 827-837.

47. Govindan V.K., A.P: Shivaprasad, A Pattern Adaptive Thinning Algorithm //Pattern Recognition, 1987, Vol. 20, pp. 623-637.

48. Kwok P.C.K., A Thinning Algorithm by Contour Generation // Communications of the ACM; 1988, Vol. 31', pp; 1314-1324.

49. Rosenfeld A., A Characterization of Parallel: Thinning Algorithms // Information and Control, 1975, Vol. 29(286-291);

50. Rosenfeld A., A.C. Как, Digital Picture Processing // 2nd Academic Press, New York, 1982, pp. 85-190.

51. Розенфельд А. Распознавание и обработка изображений: Пер. с англ.-М.: Мир. 1972, с. 232.

52. Arcelli С., L.P. Cordelia, From Local Maxima to Connected Skeleton // IEEE Trans. Pattern Analysis Machine Intelligence, 1981(PAMI-3), pp. 134-143.

53. Paven К., B. Deepak, Pseudo One Pass Thinning Algorithm // Pattern Recognition Lett., 1991, Vol. 12(9), pp. 543-555.

54. Montanary U., Continuous Skeletons from Digitized Images // Journal of the ACM 1969, Vol. 16, pp. 534-549.

55. Sklansky J., V. Gonzalez, Fast Polygonal Approximation of Digitized Curves//Pattern Recognition, 1980, Vol. 12, pp. 327-331.

56. Montanary U., A Note on the Minimal Length Polygonal, Approximation to a Digitized Contour. // Comunications of the ACM, 1970, Vol. 13(1), pp. 41-47.

57. Hung S.H.Y., T. Kasvand, Critical Points on a Perfectly 8- or Perfectly 6-Connected Thin Binary Line // Pattern Recognition, 1983, Vol. 16, pp. 297284.

58. Chhabra А. К., V. Misra, Detection of Horizontal Lines in Noisy Run Length Encoded Images: The FAST Method // Kasturi and Tombre, 1996, pp. 35-48.

59. Roosli M., G. Monagan, Adding Geometric Constraints to the Vectorization of Line Drawings // Springer-Verlag, Lecture Notes in Computer, Science, 1996, Vol. 1072, pp. 49-56.

60. Chen Y., N.A. Langrana, Perfecting Vectorized Mechanical Drawings // Computer Vision andr Image Understanding, 1996, Vol. 63(2), pp. 273-286.

61. Чернов A.B., H.B. Чупшев Автоматическое распознавание контуров зданий на картографических изображениях. Компьютерная оптика, том,31, №4,- 2007, с. 101-103.

62. Rosenfeld A., J.L. Pfaltz, Sequential operations in digital picture processing //ACM; 1966, Vol. 13, pp. 471-494.

63. Hilaire Xavier, Karl Tombre, Improving the Accuracy of Skeleton-Based Vectorization // D. Blostein and Y.-B. Kwon (Eds.): GREC 2002, LNCS 2390, Springer-Verlag, pp. 273-288.

64. Dori D., W. Liu, How to Win a Dashed Line Detection Contest // Graphics Recognition — Methods and Application, eds. R. Kasturi and K.Tombre, (LNCS, vol. 1072), Springer, Berlin, 1996, pp. 286-300.

65. Gonzalez R.C., R.E. Woods, Digital Image Processing // Prentice Hall, 2004, pp. 624.

66. Janssen R.D.T., A.M. Vossepoel, Adaptive Vectorization of Line Drawing Images // Computer Vision and Image Understanding, 1997, Vol. 65(1), pp. 38-56.

67. Liu Rujie, Takayuki Baba, Attributed Graph Matching Based Engineering Drawings Retrieval // S. Marinai and A. Dengel (Eds.): DAS 2004, LNCS 3163, Springer-Verlag, 2004, pp. 378-388.

68. Marfil R., F. Escolano, Graph-Based Representations in Pattern Recognition // J. Cabestany et al. (Eds.): IWANN 2009, Part I, LNCS 5517, SpringerVerlag, 2009, pp. 399-406.

69. Chhabra Atul K., Graphic Symbol Recognition: An Overview // Bell Atlantic Network Systems, Advanced Technology, 1997, pp. 68-79.

70. Чэн Ш.-К. Принципы проектирования систем визульаной информации: Пер. с англ. М.: Мир. - 1994, с. 184-188.

71. Xu J., GMA: A Generic Match Algorithm for structural homomorphism, isomorphism, and1 maximal common substructure match and its applications // Journal Chem. Infor. Comput. Sci., 1996, Vol. 36(1); pp. 25-34.

72. Rao A.C., Raju D: Varada, Application of the Hamming number technique to detect isomorphism among kinematic chains and inversions- // Mech. Mach. Theory, 1991, Vol. 26(1), pp. 55-75.

73. Spielman DA., Faster isomorphism testing of strongly regular graphs- // Technical report, University of California, Computer Science Division, Berkeley, California, 1996.

74. Abdulrahim M., M. Misra, A Graph Isomorphism Algorithm for Object. Recognition//Analysis and,Applications, 1998, Vol. 1(3), pp. 189-201.

75. Москаленко C.B., Ю.А. Гатчин Оптимизация алгоритмов идентификации графового изоморфизма. Научно-технический вестник. СПб: СПбГУ ИТМО. - 2010, с. 98-104.

76. Москаленко С.В., Ю.А. Гатчин Помехоустойчивый волновой алгоритм векторизации линейных растровых объектов Вестник компьютерных и информационных технологий. М.: Машиностроение. -2009, с. 16-21. 4

77. Москаленко G.B. Волной алгоритм векторизации линейных растровых изображений. Научно-технический вестник СПб: СПбГУ ИТМО. -2008, с. 16-21.

78. Москаленко С.В. Волной алгоритм векторизации линейных растровых изображений. Сб. тезисов V Межвузовской конф. молодых ученых.-СПб: СПбГУ ИТМО. - 2008, с. 295.

79. Gribov Alexander, Eugene Bodansky, Automatic Measuring the Local Thickness of Raster Lines // J. Llados and Y.-B. Kwon (Eds.): GREC 2003, LNCS 3088m Springer-Verlag, 2004, pp. 188-192.V

80. Bresenham J.E., Algorithm for Computer Control of a Digital Plotter // IBM Systems Journal, 1965, Vol. 4(1), pp. 25-30.

81. Москаленко C.B., Ю.А. Гатчин Алгоритм вычисления пороговых значений для повышения автоматизма систем распознавания графических образов. Научно-технический вестник. СПб: СПбГУ ИТМО. - 2010, с. 89-94.

82. Дюбуа П. MySQL, 3-е издание. : Пер. с англ. М.: ООО "И.Д. Вильяме". - 2007, с. 23.

83. Wenyin Liu, Dov Dori, A protocol for performance evaluation of line detection algorithms // Machine Vision and Applications, Springer-Verlag, 1997, Vol. 9, pp. 240-250.

84. Liu Wenyin, Xiaoyu Wang, Impact of Sparse Pixel Vectorization Algorithm Parameters on Line Segmentation Performance // Atul K. Chhabra and D. Dori (Eds.): GREC'99, LNCS 1941, Springer-Verlag, 2000, pp. 335-344.