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

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

Темнов Кирилл Анатольевич

МЕТОДЫ ПОСТРОЕНИЯ СПЕЦИАЛИЗИРОВАННЫХ ВЕКТОРИЗАТОРОВ ДЛЯ КОНСТРУКТОРСКОЙ ДОКУМЕНТАЦИИ ЭЛЕКТРОННЫХ СРЕДСТВ

Специальность 05.13.12 — «Системы автоматизации проектирования» (электроника, радиотехника п связь)

АВТОРЕФЕРАТ

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

004617438

Работа выполнена на кафедре «Конструирование, технология и производство радиоэлектронных средств» Московского Авиационного Института.

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

Ушкар Михаил Николаевич

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

Защита диссертации состоится 21 декабря в 10— на заседании диссертационного совета Д 212.125.02 Московского Авиационного Института по адресу: 125993, Москва, А-80, ГСП-3, Волоколамское шоссе, д. 4, ауд-_•

С диссертацией можно ознакомится в научной библиотеке Московского Авиационного Института.

Отзывы на автореферат в двух экземплярах, заверенные печатью, просьба направлять по адресу совета института: 125993, Москва, А-80, ГСП-3, Волоколамское шоссе, д. 4, ученому секретарю диссертационного совета Д 212.125.02.

Руфицкип Михаил Всеволодович — доктор технических наук, профессор Школьников Владимир Михайлович

Ведущая организация: — ОАО НПО «Лианозовский электромеханический завод»

Автореферат разослан « ÍS

»

2010 г.

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

А.М. Петраков

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

Актуальность работы. Ведущей тенденцией развития современных средств автоматизированного проектирования является непрерывная информационная поддержка поставок и жизненного цикла изделия (Continuous Acquisition and Life cycle Support, CALS). Для эффективной работы CALS-технологий на предприятиях необходимо внедрение систем управления данными об изделии (Product Data Management, PDM), обеспечивающих поддержку электронного документооборота. Вместе с тем, значительная часть конструкторской документации электронных средств (КД ЭС) на предприятиях отечественной промышленности по-прежнему хранится в бумажном виде или в виде сканированных изображений непригодных для полноценного использования в системах автоматизированного проектирования (САПР). Со временем лишь небольшая часть бумажных документов была переведена в электронный вид посредством полного воссоздания в САПР.

Для электронного документирования КД ЭС могут быть использованы специализированные векторизаторы, однако оценка эффективности работы современных векторизаторов R2V Toolkit, VPHybridCAD, RasterVect, MagicTracer и Scan2CAD показала, что они не позволяют добиться существенного повышения производительности при переводе больших объёмов КД ЭС. Это объясняется недостаточной эффективностью рассмотренных векторизаторов на графических объектах КД ЭС и требованиями, предъявляемыми к выходным векторным документам, например, необходимостью последующего редактирования полученных документов.

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

поэтому работа, посвященная исследованию повышения эффективности векторизации КД ЭС, является актуальной.

Изучением задач векторизации, фильтрации, сегментации частей изображения и оптического распознавания символов (Optical Character Recognition, OCR) занимались известные ученые, в том числе А.А. Марков, X. Самет (Н. Samet), Л.Р. Рабинер (L.R. Rabiner), Ч. Ли (C.Y. Lee), С. Форчун (S. Fortune), Р. Гонсалес (R.C. Gonzalez), Р. Вудс (R.E. Woods), Л.М. Местецкий, Т. Кохонен (Т. Kohonen), Д. Роджерс (D. Rodgers) и др. Однако их исследования посвящены общим принципам реализации векторизаторов, фильтров и систем OCR и не в полной мере учитывают специфику и методы построения специализированных векторизаторов. Поэтому целью работы является повышение эффективности векторизации КД ЭС путём разработки специализированного векторизатора.

Объектом исследования являются методы построения специализированных векторизаторов для КД ЭС.

Задачи исследования:

1. Разработка алгоритмической модели векторизатора.

2. Разработка методики классификации символов на изображениях КД ЭС.

3. Разработка методов корректировки ошибок, возникающих при OCR КД ЭС.

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

5. Разработка алгоритмов поиска окружностей на изображениях КД ЭС, имеющих меньшую сложность, чем алгоритм Хафа для окружностей.

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

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

Признаками научной новизны обладают полученная автором

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

Практическую ценность представляет разработанная программная платформа, эффективно решающая задачи векторизации КД ЭС.

Реализация результатов работы.

Основные результаты работы были использованы в НПО «Лианозовский электромеханический завод» г. Москва.

Апробация работы.

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

— Всероссийская Научная Конференция, посвященная 75-летию Казанского государственного технического университета им. А.Н. Туполева (КАИ), г. Казань 2007,

— Конференция молодых ученых ФРЕЛА, Московский Авиационный Институт (МАИ), г. Москва 2007,

— Конференция молодых ученых ФРЕЛА, Московский Авиационный Институт (МАИ), г. Москва 2009.

Публикации по работе.

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

Структура и объем диссертации.

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

На защиту выносятся:

— функционально-полный набор графических объектов, используемых для изображения КД ЭС,

— методика выявления и распознавания символов на изображениях КД ЭС,

— алгоритмическая модель векторизатора КД ЭС,

— алгоритм для корректировки ошибок, возникающих при OCR КД ЭС, основанный на вычислении расстояния Левснштейна по двум словарям,

— алгоритм полурекурсивной маркировки на квадрантных деревьях,

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

— алгоритм поиска окружностей на изображениях КД ЭС.

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

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

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

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

— линии,

— символы,

— специальные знаки,

— стрелки,

— кривые второго порядка,

— дуги и окружности,

— штриховки.

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

На тестовой выборке проанализирована эффективность работы векторизаторов VPHybridCAD, RasterVect, MagicTracer, Scan2CAD, R2V Toolkit по выявлению графических объектов из разработанного набора. По результатам тестирования были сделаны выводы:

— Векторизатор MagicTracer не способен выявлять графические объекты.

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

— Векторизаторы показали удовлетворительные результаты по выявлению линий (см. рис. 1).

— Результаты выявления символов неудовлетворительные (см. рис. 2).

— Векторизатор VPHybridCAD показал очень хорошие результаты при выявлении окружностей, остальные векторизаторы — неудовлетворительные (см. рис. 3).

— Результаты выявления штриховок неудовлетворительные (см. рис. 4).

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

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

Рассмотрены алгоритмы скелетизации: волновой алгоритм Ли, алгоритм Зонга-Суня и алгоритм Форчуна.

Рассмотрены методы выделения сложных графических объектов:

VPHybridCAD

R2V Toolkit ге^та RasterVect vzzzm Scan2CAD им

Рисунок 1: Выявление векторизаторами линий из тестовой выборки.

100

01 Ь

о х

X >.

о.

о

VPHybridCAD hi

R2V Toolkit г^х^

RasterVect vzzzzzi

Scan2CAD in

Рисунок 3: Выявление векторизаторами окружностей из тестовой выборки.

VPHybridCAD мм

R2V Toolkit Гч^я

RasterVect vzzzzn Scan2CAD

Рисунок 2: Выявление векторизаторами символов из тестовой выборки.

100

80

о

о 60

s

1 40

-в

0х 20

0

VPHybridCAD

R2V Toolkit Г\\\\\\ч

RasterVect vuw\

Scan2CAD —

Рисунок 4: Выявление векторизаторами штриховок из тестовой выборки.

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

Проанализированы алгоритмические модели, применяемые при векторизации и OCR. На основе этих моделей была разработана алгоритмическая модель, представленная на рис. 5.

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

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

Обработка текста состоит из этапов:

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

2. OCR. В представленной модели система OCR построена на основе многослойной нейронной сети (перцептрона Румельхарта).

3. Объединение символов в слова.

4. Коррекция слов. В коррекции слов участвуют два словаря — общий словарь (русского или английского языка) и словарь специальных терминов и обозначений из предметной области (КД ЭС). Для каждого слова вычисляется минимальное расстояние Левенштейна со словами из общего и специализированного словарей. Если минимальное из двух расстояний равно нулю, слово считается корректным, если минимальное расстояние больше нуля, слово исправляется на слово из словаря, для которого посчитано расстояние Левенштейна. При равенстве расстояний Левенштейна предпочтение отдается слову из словаря специальных терминов.

Извлечение графических данных состоит из этапов:

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

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

Рисунок 5: Алгоритмическая модель специализированного векторизатора КД ЭС.

ритмы.

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

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

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

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

В третьей главе производится разработка алгоритмов для специализированного векторизатора.

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

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

Разработанный алгоритм полурекурсивной маркировки обрабатывает только чёрные пикселы бинарного изображения и имеет сложность 0(п1од(п)). Для корректной маркировки при разрешении 150 точек на линейный дюйм и выше достаточно обрабатывать узлы дерева, объединяющие 16 пикселов. Среднее количество узлов, обрабатываемых алгоритмом, рассчитывается по формуле:

где Н — высота квадрантного дерева,

Ь — количество пикселов переднего плана на изображении.

2

По формуле можно провести сравнительный анализ алгоритма полурекурсивной маркировки и алгоритма Run Length Smoothing Algorithm (RLSA). В ходе анализа показано, что алгоритм полурекурсивной маркировки расходует меньше памяти на тестовой выборке изображений КД ЭС и выполняется быстрее, т.к. обходит меньшее количество пикселов, чем алгоритм RLSA.

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

Алгоритм Хафа не позволяет обрабатывать большие объёмы данных, присутствующие в чертежах тестовой выборки, т.к. его сложност-ная оценка 0{п3). Алгоритм был модифицирован с учетом специфики КД ЭС: большие окружности всегда имеют осевые линии, поэтому их можно выявить, проанализировав спектры гистограммы изображения по осям абсцисс и ординат; малые окружности выявляются алгоритмом Хафа, анализирующим не все изображение, а небольшое окно, размеры которого в 2 и более раз превышают ожидаемые радиусы искомых окружностей. В местах большого скопления линий, например, частых штриховок, алгоритм Хафа дает ложные срабатывания, поэтому выявленные окружности необходимо дополнительно проверять на непрерывность линий контура. Время выполнения модифицированного алгоритма меньше, чем время выполнения алгоритма Хафа в 8 и более раз.

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

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

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

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

В четвертой главе разработана архитектура программной платформы специализированного векторизатора, состоящая из трёх внешних приложений (ImageMagick, cl-png, Cuneiform), библиотеки sb-dxf и векторизатора cl-vectorizer. ImageMagick — библиотека для обработки изображений, предоставляющая функции фильтрации, перевода изображений в различные графические форматы, масштабирования, поворота и др. Cuneiform это система OCR, использование которой позволило значительно снизить время разработки специализированного векторизатора. Библиотека cl-png используется для чтения и записи изображений в формате PNG напрямую из Common Lisp. Библиотека sb-dxf предназначена для экспорта векторных данных в формат dxf. Векторизатор cl-vectorizer представляет собой набор модулей, реализующих алгоритмы, рассмотренные в главе 3. Программная платформа была полностью реализована на языке Common Lisp.

Проверка эффективности и скорости работы алгоритмов специализированного векторизатора проводилась на тестовой выборке, разработанной в главе 1. На рис. 6, 7, 8, 9 представлены результаты работы специализированного векторизатора (cl-vectorizer) в сравнении с результатами исследованных векторизаторов, полученными в главе 1.

Разработанный векторизатор определил на тестовой выборке 70,1 % прямых, 38 % штриховок, 45 % окружностей и 57,6 % символов. По ре-

VPHybrldCAD mi

R2V Toolkit юлчччч

RasterVect v//////\ cl-vectorizer

Scan2CAD штшш

Рисунок 6: Выявление векторизаторами линий из тестовой выборки.

>«

о. *

о

VPHybrldCAD

R2V Toolkit KVAVAi RasterVect */////л cl-vectorizer шч Scan2CAD иш/шм

Рисунок 7: Выявление векторизаторами символов из тестовой выборки.

100

80

о

□ X 60

31

i 40

чО

20

0

VPHybrldCAD мн R2V Toolkit f^x^] RasterVect v//////x cl-vectorizer Scan2CAD mnmmm

Рисунок 8: Выявление векторизаторами окружностей из тестовой выборки.

VPHybrldCAD штш R2V Toolkit кчччччч RasterVect г/улул cl-vectorizer Scan2CAD тнттт

Рисунок 9: Выявление векторизаторами штриховок из тестовой выборки.

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

Работу модифицированного алгоритма Зонга-Суня и алгоритма

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

Нелинейная зависимость времени работы алгоритма оптимизации скелета объясняется тем, что алгоритм оперирует линиями скелета, количество которых не имеет прямой корреляции с количеством пикселов на исходном изображении. Еще одной особенностью алгоритма оптимизации скелета является то, что количество итераций определяется в процессе выполнения алгоритма, поэтому невозможно произвести его слож-ностную оценку. Среднее время работы алгоритма на тестовой выборке 4,20 с, максимальное — 32,46 с.

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

Результаты работы алгоритма поиска окружностей (рис. 12) не отражают реальной теоретической сложности алгоритма. Сложность алгоритма Хафа, взятого за основу, — 0(п3). В результате правильного выбора окна, скорость работы модифицированного автором алгоритма Хафа значительно повышается, однако при этом ухудшается процент распознанных окружностей. Поиск окружностей на основе гистограмм подходит только для больших окружностей с осевыми линиями. На тестовых прогонах алгоритм был настроен на максимальную скорость, поэтому оценка, представленная на рисунке является лучшим случаем с точки зрения скорости и худшим, с точки зрения качества полученных

результатов.

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

Если параметры алгоритма настроены на максимальное количество выявляемых окружностей, на тестовой выборке время работы алгоритма увеличивается в 80 - 120 раз, что приближается к оценке 0(п3).

Общее время работы специализированного векторизатора растет нелинейно (см. рис 13. ). Основные составляющие общего времени работы: предварительная обработка и фильтрация, скелетизация и оптимизация скелета, построение квадрантного дерева.

Предварительная обработка и фильтрация изображений осуществляются утилитой ImageMagick, алгоритмы фильтрации и предварительной обработки имеют сложность 0(п).

Алгоритмы скелетизации и оптимизация скелета вносят наибольший вклад в общее время векторизации. Время работы алгоритма оптимизации определяет локальные спады среднего значения времени векторизации в диапазоне 7-9 млн. пикселов.

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

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

Рисунок 11: Время работы алгоритма поиска символов на изображениях тестовой выборки.

Количество линий, полученных в результате векторизации

Рисунок 12: Время работы алгоритма поиска окружностей на изображениях тестовой выборки.

Количество пикселов на изображении, млн.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ

1. Функционально-полный набор графических объектов, используемых для изображения КД ЭС. Для каждого тина графических объектов был описан вектор метрических свойств.

2. Представительная тестовая выборка, состоящая из 71 изображения КД ЭС, включает достаточное количество объектов для статистически полного представления всех графических объектов из разработанного набора.

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

4. Алгоритмическая модель специализированного векторизатора, учитывающая особенности векторизации КД ЭС. Модель основана па совместном использовании алгоритмов векторизации и OCR.

5. Алгоритм для корректировки ошибок, возникающих при OCR КД ЭС. Особенностью алгоритма является использования двух словарей для поиска корректных слов.

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

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

8. Модифицированный алгоритм Хафа. Модифицированный алгоритм имеет меньшее время выполнения на изображениях КД ЭС, по сравнению с оригинальным.

9. Оригинальные алгоритмы поиска стрелок и штриховок. Алгоритм штриховок показывает более эффективные результаты, чем алгоритмы в исследованных векторизаторах.

10. Эффективный формат внутреннего представления данных для век-

торпзатора. позволяющий повысить скорость доступа к данным.

11. Специализированный векторизатор в виде программной платформы.

12. Основные результаты использованы па ОАО НПО «Лианозовский электромеханический завод», где была показана высокая эффективность разработанного специализированного векторизатора.

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

1. Темпов К.А., Репнев Д.Н., Полпцарнов Г.К. Анализ возможности использования существующих векторизаторов для распознавания электрических принципиальных схем. / «Информационно-измерительные и управляющие системы». — 2007. — Т. 5. .V- 11 — С. 49 - 54.

2. Темпов К.А., Галкин C.B., Кириллов A.B. Алгоритм скелетпзации растрового монохромного изображения. / ' «Информационно-измерительные и управляющие системы». — 2009. — Т. 7, № 8. — С. 4-5 - 50.

3. Темпов К.А. Повышение эффективности векторизации конструкторской документации электронных средств / «Вестник МАИ», — 2010 Т. 17. № 13 - С. 213 - 221.

4. Темпов К.А., Репнев Д.Н., Полпцарнов Г.К. Анализ возможности использования существующих векторизаторов для распознавания электрических принципиальных схем. Тезисы. /,< Информационные технологии в науке, образовании и производстве. Материалы Всероссийской Научной Конференции. — 2007 — С. 421 -- 422.

Обозначения и сокращения

Введение

Глава 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.2.4. Оценка работы векторизаторов на тестовой выборке.

1.2.5. Выводы.

1.3. Анализ подходов к векторизации.

1.3.1. Предварительная обработка.

1.3.2. Распознавание текста.

1.3.3. Скелетизация изображения и выделение контуров.

1.3.4. Объединение текстовых и графических данных.

1.3.5. Выводы.

1.4. Постановка задачи разработки специализированного векторизатора для КД ЭС

1.5. Выводы.

Глава 2. Разработка модели специализированного векторизатора

2.1. Методы классификации.

2.1.1. Классификация на основе дерева решений.

2.1.2. Классификация на основе искусственных нейронных сетей.

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

2.2.1. Классификация с использованием перцептрона Румельхарта.

2.3. Повышение качества распознаваемого текста за счет использования дополнительного классификатора.

2.4. Скелетизация и оптимизация скелета.

2.4.1. Методы скелетизации.

2.4.2. Оптимизация скелета.

2.5. Выделение сложных графических объектов.

2.5.1. Аппроксимация ребер сплайнами.

2.5.2. Нахождение окружностей и дуг на изображении.

2.5.3. Эвристические алгоритмы для выявления сложных графических объектов.

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

2.7. Выводы.

Глава 3. Разработка алгоритмов специального векторизатора

3.1. Маркировка бинарного изображения.

3.1.1. Представление бинарного изображения в виде квадрантного дерева.

3.1.2. Построение и обход квадрантного дерева.

3.1.3. Алгоритм нахождения смежных узлов квадрантного дерева.

3.1.4. Алгоритм полурекурсивной маркировки.

3.1.5. Выделение текстовых компонент в квадрантном дереве.

3.1.6. Эвристический анализ на основе расстояния Левенштейна.

3.2. Построение и оптимизация скелета.

3.2.1. Алгоритм построения скелета изображения.

3.2.2. Алгоритм построения сплайнов на ребрах скелета.

3.3. Выявление сложных графических объектов.

3.3.1. Алгоритм поиска штриховок на изображении.

3.3.2. Алгоритм поиска стрелок.

3.3.3. Алгоритм поиска окружностей.

3.4. Разработка структур данных.

3.4.1. Экспорт в формат сМ.

3.4.2. Экспорт в формат svg.

3.5. Выводы.

Глава 4. Реализация и апробация специализированного векторизатора ИЗ

4.1. Архитектура программной платформы.ИЗ

4.1.1. Требования к реализации специализированного векторизатора.

4.1.2. Выбор языка реализации.

4.1.3. Архитектура программной платформы.

4.2. Тестирование специализированного векторизатора.

4.2.1. Результаты работы с тестовой выборкой.

4.3. Эффективность разработанного векторизатора.

4.4. Основные результаты.

Список иллюстраций

Список таблиц.

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

Для электронного документирования КД ЭС могут быть использованы специализированные векторизаторы, однако оценка эффективности работы современных векторизаторов R2V Toolkit, VPHybridCAD, RasterVect, MagicTracer и Scan2CAD показала, что они не позволяют добиться существенного повышения производительности при переводе больших объемов КД ЭС. Это объясняется недостаточной эффективностью рассмотренных векторизаторов на графических объектах КД ЭС и требованиями, предъявляемыми к выходным векторным документам, например, необходимостью последующего редактирования полученных документов.

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

Изучением задач векторизации, фильтрации, сегментации частей изображения и оптического распознавания символов (Optical Character Recognition, OCR) занимались известные ученые, в том числе А.А. Марков, X. Самет (Н. Samet), JI.R Рабинер (L.R. Rabiner), С. Форчун (S. Fortune), Ч. Ли (C.Y. Lee), Р. Гонсалес (R.C. Gonzalez), Р. Вудс (R.E. Woods), Л.М. Ме-стецкий, Т. Кохонен (Т. Kohonen), Д. Роджерс (D. Rodgers) и др. Однако их исследования посвящены общим принципам реализации векторизаторов, фильтров и систем OCR и не в полной мере учитывают специфику и методы построения специализированных векторизаторов. Целью работы является повышение эффективности векторизации КД ЭС путем разработки специализированного векторизатора.

Существует несколько методов перевода бумажных документов в электронный вид:

Создание электронного документа в необходимом формате по соответствующему бумажному документу.

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

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

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

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

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

Метод преобразования текстовых бумажных документов в электронный формат - оптическое распознавание символов (OCR) давно существует, поэтому применение такого метода преобразования документов является предпочтительным и почти полностью автоматизированным для текстовой информации, процент распознавания документа колеблется в пределах от 70 до 98 %.

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

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

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

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

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

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

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

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

Объектом исследования являются методы построения специализированных векторизаторов для КД ЭС.

Задачи исследования:

1. Разработка алгоритмической модели векторизатора.

2. Разработка методики классификации символов на изображениях КД ЭС.

3. Разработка методов корректировки ошибок, возникающих при OCR КД ЭС.

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

5. Разработка алгоритмов поиска окружностей на изображениях КД ЭС, имеющих меньшую сложность, чем алгоритм Хафа для окружностей.

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

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

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

Практическую ценность представляет разработанная программная платформа, эффективно решающая задачи векторизации КД ЭС.

Реализация результатов работы.

Основные результаты работы были использованы в НПО «Лианозовский электромеханический завод» г. Москва.

Апробация работы.

Основные положения и результаты работы обсуждались на следующих конференциях: Всероссийская Научная Конференция, посвященная 75-летию Казанского государственного технического университета им. А.Н. Туполева (КАИ), г. Казань 2007,

Конференция молодых ученых ФРЕЛА, Московский Авиационный Институт (МАИ), г. Москва 2007,

Конференция молодых ученых ФРЕЛА, Московский Авиационный Институт (МАИ), г. Москва 2009.

Публикации по работе.

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

Структура диссертации.

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

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

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

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

В.1 Результаты работы векторизаторов на тестовой выборке . 146

0.1 Отображение графических объектов в объекты svg.153

Е.1 Параметры тестовых изображений и время работы алгоритмов 158

1. Арагпа К.H. , Chakravarthy V.S. A complete ocr system developement of tamil magazine documents // Tamil 1.ternet. — 2003. — Pp. 45-51.

2. Yuan Q. , Tan C.L. Page segmentation and text extraction from gray scale image in microfilm format // Document Recognition and Retrieval VIII Proc. SPIE. 2001. - Pp. 323-332.

3. Behera A. , Lalanne D. , Ingold R. Visual signature based identification of low-resolution document images // The 2004 ACM symposium on Document engineering. — 2004. — Pp. 178-187.

4. Anigbogu J.C. , Belaïd A. Hidden markov models in text recognition // International Journal of Pattern Recognition and Artificial Intelligence. — 1995,-Vol. 9, no. 95-153.

5. Xu Y. , Nagy G. Prototype extraction and adaptive ocr // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 1999.— Vol. 21, no. 1280-1296.

6. Chen Q. — Evaluation of OCR Algorithms for Images with Different Spatial Resolutions and Noises. — Master's thesis, Ottawa, 2003.

7. Taghva K. , Borsack J. , Condit A. An expert system for automatically correcting ocr output // In Proceedings of the IS&T/SPIE 1994 International Symposium on Electronic Imaging Science and Technology. — 1994. — Pp. 270-278.

8. Park J. , Govindaraju V. , Srihari S. Ocr in a hierarchical feature space // IEEE Trans, on Pattern Analysis and Machine Intelligence. — 1998. — Vol. 22. Pp. 400-407.

9. Арлазаров В. JI. , Троянкер В.В. , Котович Н.В. Адаптивное распознавание символов. — http: //www. cuneiform.ru/tech/adaptive .html.

10. Кат Но Т. , Baird H. Evaluation of ocr accuracy using synthetic data // The 4th Annual Symposium on Document Analysis and Information Retrieval. — 1995. — Pp. 412-422.

11. Кат Но Т. , Nagy G. Осг with no shape training // 15th International Conference on Pattern Recognition. — Vol. 4. — 2000. — Pp. 27-30.

12. Lee C.Y. An algorithm for path connections and its applications // IRE Transactions on Electronic Computers. — 1961.— Vol. EC-10, no. 2.— Pp. 364-365.

13. Заугольнова E.B. , Юрин Д.В. Алгоритм уточнения предварительной сегментации изображений с нечеткими, слабоконтрастными границами двумерных объектов // International Conference Graphicon. — 2006.

14. Лагно Д. , Соболев А. Модифицированные алгоритмы Форчуна и Ли скелетизации многоугольной фигуры // International Conference Graphicon. — 2001.

15. Местецкий JI.M. Непрерывный скелет бинарного растрового изображения. // International Conference Graphicon. — 1998.

16. Местецкий JI.M. Векторизация растровых бинарных изображений на основе апроксимации // 10-я Всероссийская конференция Математические Методы Распознавания Образов. — 2001. — С. 249 252.

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

18. Местецкий JI.M. , Нефедов А.Г. Восстановление следа пера при анализе сканированных рукописных документов // 11-я Всероссийская конференция Математические Методы Распознавания Образов. — 2003. — С. 364-367.

19. Местецкий JI.M. Скелет многосвязной многоугольной фигуры // International Conference Graphicon.— 2005.

20. Масалович А.А. Кластеризация изображения графем на основе непрерывного гранично-скелетного представления // 12-я Всероссийская конференция Математические Методы Распознавания Образов. — 2005. — С. 374 -378.

21. Peng J. An efficient algorithm of thinning scanned pencil drawings // Journal of Image and Graphics. — 2000. — Vol. 5. — Pp. 434-439.

22. Темное К.A. , Репнев Д.Н. , Полицарнов Т.К. Анализ возможности использования существующих векторизаторов для распознавания электрических принципиальных схем. // Информационно-измерительные и управляющие системы. — 2007. — Т. 5, № 11. — С. 49-54.

23. Темное К.А. , Кириллов А.В. , Галкин С. В. Алгоритм скеле-тизации растрового монохромного изображения // Информационно-измерительные и управляющие системы. — 2009. — Ш 8. — С. 45 49.

24. Zhou R. W. , Quek С. , Ng G.S. A novel single-pass thinning algorithm and an effective set of performance criteria // Pattern Recognition Letter. — 1995. March. - Pp. 1267-1275.

25. Fortune S. Computing in Euclidean Geometry. — 1 edition. — World Scientific, 1992. Pp. 193-233.

26. Ogniewicz R. , Ilg M. Voronoi skeletons: Theory and applications // Conference on Computer Vision and Pattern Recognition. — 1992. — Pp. 63-69.

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

28. Marr D. , Hildreth Е. Theory of edge detection // The Royal Society. — 1980.

29. A new skeletonization method based on connected component approach / Kumar V.V., Srikrishna A., ShaikS.A., Trinath S.// International Journalof Computer Science and Network Security. — 2008.— February. — Vol. 8, no. 2. Pp. 133-137.

30. Blum H. A transformation for extracting new descriptors of shape // Models for the Perception of Speech and Visual Form. — 1967. — Pp. 362-380.

31. ЕСКД. Виды и комплектность конструкторских документов. — ГОСТ 2.102-68.

32. ЕСКД. Схемы. Виды и типы. Общие требования к выполнению. — ГОСТ 2.701-84.

33. Text classification from labeled and unlabeled documents using em / Nigam K., Mccallum A.K., Thrun S., Mitchell T. // Machine Learning. — 1999. Vol. 39. - Pp. 103 - 134.

34. ЕСКД. Шрифты чертежные. ГОСТ 2.304-81.

35. Феличи Дж. Типографика: шрифт, верстка, дизайн. — M:BHV, 2004.

36. ЕСКД. Общие правила оформления чертежей. Нанесение размеров. — ГОСТ 2.307-68.

37. ЕСКД. Линии. — ГОСТ 2.303-68.

38. ЕСКД. Обозначения графических материалов и правила их нанесения на чертежах. ГОСТ 2.306-68.

39. Comparison of raster to vector conversion software Электронный ресурс. — http://en.wikipedia.org/wiki/Comparisonofrasterto vectorconversionsoftware.

40. Adobe Corp. Tiff specification Электронный ресурс.— http:// partners.adobe.com/public/developer/en/tiff/TIFF6.pdf. — 1993. — 6.

41. Oracle Corp. Jpeg metadata format specification and usage notes Электронный ресурс.— http://download.oracle.eom/javase/6/ docs/api/javax/imageio/metadata/doc-files/jpegmetadata.html.

42. Otsu N. A treshold selection method from gray-level histograms // IEEE Trans. Systems, Man, and Cybernetics. — 1979. — Vol. 9, no. 1. — Pp. 62-66.

43. Шапиро JI. , Стокман Дж. Компьютерное зрение. — М:БИНОМ, 2006.

44. Liu Q.H. , Tan C.L. Automatic indexing of newspaper microfilm images // The 5th International Workshop on Document Analysis Systems V. 2002. - Pp. 365-375.

45. Hse H. , Newton A.R. Sketched symbol recognition using zernike moments // ICPR 2004. Proceedings of the 17th International Conference. — Vol. 1. 2004. - Pp. 367 - 370.

46. Hew P. Recognition of printed digits using zernike moments and gaussian models.

47. Singh H. , Sharma R.K. Moment in online handwritten character recognition // Proceedings of National Conference on Challenges & Opportunities in Information Technology. — 2007.

48. Accurate and efficient computation of high order zernike moments / Amayeh G.R., Erol A., Bebis G., Nicolescu M. // First International Symposium, ISVC 2005, Lake Tahoe, NV, USA. 2005. - Pp. 462-469.

49. Nixon M.S. , Aguado A.S. Feature Extraction and Image Processing. — 2 edition. — Academic Press, 2008.

50. Rabiner L.R. , Juang B.H. An introduction to hidden markov models // IEEE ASSP Magazine. — 1986. Pp. 4 - 16.

51. Rabiner L.R. A tutorial on hidden markov models and selected applications in speech recognition // Proceedings of the IEEE. — 1989. — Pp. 257-286.

52. Kannan R.J. Accuracy augmentation of tamil ocr using algorithm fusion // International Journal of Computer Science and Network Security. — Vol. 8. — 2008. Pp. 51-56.

53. Colin A. Building decision trees with the id3 algorithm // Dr. Dobbs Journal. — 1996.

54. Quinlan J.R. C4.5 Programs for Machine Learning. — Morgan Kaufmann, 1993.

55. Classification and Regression Trees / Breiman L., Friedman J., Stone C.J., Olshen R.A. — Chapman and Hall, 1984.

56. Кохонен Т. Самоорганизующиеся карты. — Бином. Лаборатория знаний, 2008.

57. Hopfield J.J. Neural networks and physical systems with emergent collective computational abilitie // Proceedings of National Academy of Sciences. — 1982.-April.-Vol. 79, no. 8.—Pp. 2554-2558.

58. Розенблатт Ф. Принципы нейродинамики: Перцептроны и теория механизмов мозга. — М:Мир, 1965.

59. Rumelhart D.E. , McClelland J.L. Parallel distributed processing: Explorations in the microstructures of cognition // Cambridge, MA: MIT Press. — 1986.

60. Verma B. , Blumenstein M. Pattern Recognition Technologies and Applications: Recent Advances. — Information Science Reference, 2008.

61. Короткий С. Нейронные сети: алгоритм обратного распространения. — М:Мир, 1997.

62. Галушкин А. И. Синтез многослойных систем распознавания образов.— М:Энергия, 1974.

63. Werbos P.J. Beyond regression: New tools for prediction and analysis in the behavioral sciences: Ph.D. thesis / Harvard University, Cambridge, MA. — 1974.

64. Pal S.K. , Mitra S. Multilayer perception, fuzzy sets, and classification // IEEE Transactions on Neural Networks. — 1992. — Vol. 3, no. 5. — Pp. 683696.

65. Мисюрев А.В. Использование искусственных нейронных сетей для распознавания рукопечатных символов Электронный ресурс.— http:// www.cuneiform.ru/tech/handprinted.html.

66. Левенштейн В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов. // Доклады Академий Наук СССР. — Т. 163. — 1966. С. 845-848.

67. Kukich К. Techniques for automatically correcting words in text // ACM ComputingSurveys. — 1992. — December. — Vol. 24, no. 4. — Pp. 377-439.

68. Introduction to Algorithms / Cormen Т.Н., Leiserson C.E., Rivest R.L., Stein C. — 2 edition. MIT, 2001.

69. Дегтярева A. , Вежневец В. Преобразование Хафа (hough transform) // CGM. 2003.

70. Мариничев К. , Вежневец В. Алгоритмы выделения параметрических кривых на основе преобразование Хафа // Компьютерная графика и мультимедиа. — 2006. — Т. 4, № 1.

71. Лебедев С. А. , О сосков Г. А. Быстрые алгоритмы распознавания колец и идентификация электронов в детекторе rich эксперимента СВМ // Письма в ЭЧАЯ. 2009. — Т. 6, № 2. - С. 260-284.

72. Lu Z. , Bazzi I. , Kornai A. et al. A robust, language-independent ocr system.

73. Sun H.M. Enhanced constrained run-length algorithm for complex layout document processing // International Journal of Applied Science and Engineering. — 2006. — Pp. 297-309.

74. AutoCad 2000 dxf reference Электронный ресурс.— http://www. autodesk.com/techpubs/autocad/acad2000/dxf/.

75. Scalable vector graphics (svg) 1.1 (second edition) Электронный ресурс. — http://www.w3.org/TR/SVG/.

76. Finkel R.A. , Bentley J.L. Quad trees a data structure for retrieval on composite keys // Acta Informatica. — 1974.— Vol. 4.— Pp. 1-9.— 10.1007/BF00288933. http: //dx. doi. org/10.1007/BF00288933.

77. Темное К.А. Повышение эффективности векторизации конструкторской документации электронных средств. // Вестник МАИ. — 2010. — Т. 17, № 13,- С. 213 221.

78. Yoder R. , Bloniarz P. A practical algorithm for computing neighbors in quadtrees, octrees, and hyperoctrees Электронный ресурс. — http: //wwl. ucmss.com/books/LFS/CSREA2006/MSV4517.pdf.

79. Tanimoto S.L. The elements of artificial intelligence using common LISP. — 2 edition. — W.H. Freeman & Company, 1995. — April.

80. Pal U. , Sinha S. , Chaudhuri B.B. Multi-script line identification from indian documents // Seventh International Conference on Document Analysis and Recognition. — 2003. — Pp. 880-884.

81. Skew detection, page segmentation, and script classification of printed document images / Waked В., Bergler S., Suen C.Y., Khoury S. // In IEEE International Conference on Systems, Man, and Cybernetics. — IEEE Computer Society, 1998. Pp. 4470-4475.

82. Abbass Y.M. , Fakher W. , Rashwan M. Arabic / english identification in a hybrid complex documents images // GVIP 05 Conference. — 2005.— Pp. 189-194.

83. Темное К.А. Библиотека для генерации файлов в формате dxf Электронный ресурс. — http: //github. com/selead/sb-dxf. — 2010.85. gnuplot Программа для создания двухмерных и трехмерных графиков Электронный ресурс. — http: //www. gnuplot. info/.

84. Imagemagick(R) Библиотека для обработки изображений Электронный ресурс. — http: //www. imagemagick. org/script/index.php.