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

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

ЧЕРЕМИСИН Илья Николаевич

и

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

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

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

Екатеринбург, 2005

Работа выполнена в Институте машиноведения УрО РАН.

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

Г.Б. Захарова

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

доктор технических наук, профессор Б.Б. Зобнин

кандидат технических наук, доцент В.П. Битюцкий

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

ОАО «НИИ точной механики», г. Санкт-Петербург

Защита состоится «10» февраля 2006 г. в 15 час. в аудитории Р-217 на заседании диссертационного совета К 212.285.02 при ГОУ ВПО Уральский государственный технический университет «УГТУ-УПИ».

Отзывы на автореферат в двух экземплярах, заверенные печатью учреждения, просим направлять по адресу: 620002, Екатеринбург, ул. Мира, 19, УГТУ-УПИ, Ученому секретарю.

С диссертацией можно ознакомиться в библиотеке УГТУ-УПИ.

Автореферат разослан иЗ&» Ученый секретарь диссертационного совета, кандидат технических наук, доцент

2005г.

Морозова В.А.

\%ЪОу общая характеристика работы

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

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

3 I библиотека"

С "ТО? :

" Л

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

Предмет исследования. Предметом исследования являются модели и алгоритмы построения векторных описаний ПП.

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

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

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

2. Разработать модели и алгоритмы выделения и анализа скелетного описания топологии ПП для восстановления ее векторного представления.

3. Разработать методологию автоматизированного восстановления ПП.

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

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

Научная новизна. В результате проведённых исследований получены следующие новые научные результаты:

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

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

2. Построена функционально-структурная модель системы восстановления векторных описаний ПП.

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

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

5. Разработан комплекс алгоритмов анализа топологии на основе скелетного описания с целью идентификации примитивов ПП, в том числе алгоритм аппроксимации сегментов с помощью линейной регрессии. Практическая ценность. На основании разработанных моделей и алгоритмов создана программа Drupht для восстановления топологии ПП в стандартном технологическом формате Gerber RS-274X, использующая в качестве входного изображения сканированное и затем бинаризованное и отфильтрованное изображение ПП. Программа внедрена на предприятии ЗАО «Тех-носвязь» (г. Екатеринбург) и ОАО «НИИ Точной механики» (г. Санкт-Петербург), что подтверждается соответствующими актами.

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

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

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

3. Алгоритм анализа топологии на основе скелетного описания с целью идентификации примитивов ПП.

Апробация работы. Основные результаты работы докладывались и обсуждались на XII международной конференции по вычислительной механике и современным прикладным программным системам (г. Владимир, 2003), международной научно-технической конференции "Интеллектуальные системы" (Дивноморское, 2003), всероссийской научно-практической конференции "Новые информационные технологии и системы" (Пенза, 2004).

Основные положения работы опубликованы в центральных журналах «Гироскопия и навигация», «Технологии в электронной промышленности», «Вестник Томского государственного университета». Всего по теме диссертации опубликовано 7 научных работ.

Объем и структура диссертации. Диссертация состоит из введения, трех глав, заключения, библиографического списка и приложений. Общий объем работы составляет 133 страницы машинописного текста. Диссертация содержит 44 рисунка и 7 таблиц. Библиография включает 80 источников.

содержание работы

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

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

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

чертежом

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

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

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

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

Рис. 2. Методы описания топологии

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

сти к контурным, структурно-скелетным и методам сегментации.

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

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

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

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

В работе приводится обзор существующих средств векторизации изображений ПП. Из множества систем для сравнения были выбраны характерные представители каждого класса - от универсальных решений до специализированных программно-аппаратных комплексов. Сравнение производилось путем выставления каждой системе оценки от 0 до 5 баллов по ряду параметров. Результаты сравнения приведены в таблице 1.

Raster Vect, Algolab Raster To Vector, Raster Desk 6 относятся к классу универсальных систем, PCB Artwork Scanner (ETS) - специализированный сканер-векторизатор ПП. Drupht - продукт, разработанный в ходе диссертационной работы. Drupht характеризуется высокими показателями по параметрам, имеющим наибольший приоритет для российских производителей, что свидетельствуют об эффективности разработанных моделей и алгоритмов.

Таблица 1

Сравнение систем векторизации

Параметры НазгетУеЫ А^о1аЬ Яаз1ег То Уейог РСВ АП\УОгк $саппег (ЕТБ) ЯаэигОезк 6 Ш-ирЫ

Поиск прямоугольных, восьмиугольных контактных площадок 0 0 4 3 5

Поиск контактных площадок, соединенных с проводником 1 1 3 3 4

Точное измерение ширины проводника 2 1 5 4 5

Аппроксимация примитивов по направлению 3 3 4 4 5

Быстродействие 4 4 5 5 2

Распознавание проводников в виде кривой 4 3 5 5 0

Распознавание сложных полигонов 0 0 2 1 0

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

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

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

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

Заданы базовые структурные элементы (рис. 3), из которых образуются всевозможные структурные элементы путем последовательного поворота на 90° градусов, транспонирования и отражения слева-направо и сверху-вниз. Всего для сужения данным методом применяется 24 структурных элемента.

1 1 1

3 1 3

0 0 0

3 1 3

0 1 1

0 0 3

1 1 1

1 1 1

2 0 0

3 1 1

2 1 1

0 0 3

А В С О

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

Е1етепфд,А,В) =

1, если

= \,пЛ<р-к + 1<\УА\<д-к+ у ¿Ял Щи]) = В(р-к + ич-к + у) V /1(1, У) = 3) 0 в противном случае где IV - иширина изображения В,Н - высота изображения В, к - индекс основного пиксела структурного элемента А

(1)

Функция Е1етеп{(р,д,А,В) вычисляет результат наложения структурно-

го элемента А, имеющего размерность п, на изображение В в точке M(p,q).

В ходе сужения изображения производится вычисление матрицы индексов сужения каждого пиксела (2), равных минимальному числу итераций сужения, в результате которых при дальнейших итерациях сужения код соседних пикселов не изменяется. Индекс сужения некоторой точки скелета изображения несет в себе полезную информацию относительно толщины и формы проводника в данной точке, что позволяет делать приблизительную оценку ширины проводника в каждой точке скелета, а также более точно определять места поворота проводников в процессе их разрезания. п, если Вi,j: Sntit>((p,q),(i,j)) = True л B(i,j) = 2

Т' ■■

'' в противном случае

где Т - матрица индексов сужения до итерации, (2)

7" - матрица индексов сужения после итерации, п - номер итерации сужения,

5мл({р, q), (/, /)) - функция, определяющая, являются ли точки соседними

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

Удаление шумовых ветвей скелета также основано на последовательном

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

3 0 0

1 1 0

3 0 0

0 0 0

3 1 0

1 3 0

Е Р

Рис. 4. Базовые структурные элементы удаления шумовых ветвей

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

|ЛГ, если ац < 2 л В(/, у) = I л ат = N л БпеИз&р,д), (г, у'))| 1 ¿»у в противном случае |

4+1 =Ц> (3)

где - результат наращивания на шаге /, В - исходное изображение

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

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

Рис. 5. Наложение шаблона на контактную площадку

в виде растра.

,1 = 1,Г.

В каждой точке скелета (МХ,МУ) для подшаблона Ь| размера 1 вычисляется параметр а,. Данный параметр равен количеству пикселов проводника исследуемого изображения, совпадающих с точками шаблона, наложенного на изображение в точке (МХ,МУ):

\(х,у) \(х,у) <=Ы : [А(х + Мх,у + Му) = 1)

Таким образом, для каждого типа шаблона Ь получено упорядоченное множество V = {а\,...,аг}. В случае, если шаблон был наложен на объект, форма которого близка к форме шаблона и размер не превышает заданный максимум, то график функции У(д) имеет резкое падение значений в некоторой окрестности. Предложен критерий для обнаружении падения значения функции на некотором отрезке (4), т.е. объект относится к контактной площадке радиуса ¡, если некоторая критическая доля точек его границы отстоит от соответствующих точек шаблона данного радиуса на суммарное расстояние меньше заданного.

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

= ЯоигиШ^ • (1 + е))

3;:

Ч/1--— >г_'тт>/тах

(4)

V/ =тах(у/,-) 4 1

(j/j > (1 - Я) ■ п

где ЯоигкШр(х) - функция округления до следующего целого

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

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

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

«„ил = тах(0, / - >ет1п), птах =тт(п,/ + м'лип), А = •июКЯпш), В = и•ау(птт ), С = ъау(Г) АС2 + ВС2 - АВ2

а = ZBCA = arceos

arceos

2-АС-ВС (Сх - Ах) ■ (Сх - Вх)+(Су-Ау)■ (Су - Ву)

■yj(Cx-Ax)2 + (Су- Ay)2 -^(Сх-Вх)2 +(Су-Ву)2

(5)

S _ Thinlndex(yvay(i)) - w mm ^ ft = cos(arccos(a)-J) Wrnm

где way - цепь сегмента, Т] - коэфф. степени влияния индекса сужения

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

поворота Р (рис. 6) с учетом индексов сужения в исследуемой окрестности

(5), и находится точка с максимальным

Участок скелета

—— значением этого параметра. Если ß пре-

П-

вышает заданный критический угол изло-в ма, в данной точке производится разделение сегмента на два, в противном случае сегмент помечается как завершенный.

_. Дальнейшая задача - аппроксимация

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

А = ¿W ~Уд2 = -»min (6)

i=l i=l

/2 = —Ц- -|>; - Л)2 = -Ц- • ¿0Vi- kxi - b)2 -> min (7)

1 + к2 Й 1 + к2 й

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

2

а-к +d■ к+ с = 0, где коэффициенты задаются следующими выражениями:

а = х ■ У у + п ху

ä-n^-^J-n^/^yb c=Hxlly-nlixy

Для обеспечения ортогональности направлений, если необходимо, производится корректировка направлений сегментов, и, соответственно, изменение координат их концов. Для каждого из концов сегмента находится ближайшая точка, лежащая на регрессионной прямой. Для этой цели определена функция GetCrossPoint(Pj,Vj,P2,V2) (8), возвращающая координаты пересечения двух прямых. Каждая прямая задается вектором-направлением и точкой, через которую она проходит. Л = УIx' (<°2у • V2x ~ Pix • V2y) + V2x ■ (Pu ■ V\y - PXy ■ VU) ß=V\У (Ply ■ Ъх - Pix -Vly) + Vly ■ (Plx ■ V\y - f\y ■ ylx) fl = V\y-V2x-Vu-V2y

GetCrossPomt(P] У],РгУ2) =

(8)

л л ]

round{y^),round(y^) [, если/3 * О

null в противном случае где к,Ь-коэффициенты в уравнении линейной регрессии у = kx + Ь, п - количество точек скелета отрезка

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

можно представить как -С^2) + (Яу2 -О^) < м>$ + и>д, где

(8х,5у) ,(Сх,Су) -координаты начала каждого сегмента, ,и^ - радиусы

апертур сегментов. Вычисление координат точки пересечения также выполняется по формуле (8).

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

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

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

Приводится общее описание Е)гирЫ, последовательность его работы как самостоятельного продукта и как модуля, встроенного в систему контроля. Для описания процессов векторизации построены функционально-структурные модели разработанной системы в рамках методологии ШЕРО.

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

ВМР24Ь«

ВМР2Ы1

4'% г-^У^&Л Блокскелвтиэации

Ил

БТО АрШе

Рис. 7. Структура системы

Приводятся результаты испытаний и технические характеристики, позволяющие оценить эффективность системы и ресурсы, требуемые для ее функционирования. Отмечается, что общая доля верно распознанных примитивов составляет от 60 до 95 %, что позволяет приблизительно в 5-10 раз быстрее производить восстановление векторных описаний ПП по сравнению со сколкой вручную.

Приложение 1 содержит копии документов, подтверждающих внедрение системы. В приложении 2 приведены фрагменты исходного кода Е)гирМ.

(

заключение

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

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

г

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

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

4. Разработан комплекс алгоритмов анализа топологии на основе скелетного описания с целью идентификации примитивов ПП:

• Алгоритм сегментации скелета по узловым точкам и изменению направления цепей.

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

• Алгоритм аппроксимации сегментов с помощью линейной регрессии.

• Алгоритм определения ширины сегментов по индексу сужения и по секущим.

< 5. Разработанные математические модели и алгоритмы реализованы в про-

грамме 1>гир1Л, которая может использоваться самостоятельно или в качестве модуля, встроенного в систему контроля ПП.

6. Осуществлено внедрение программы ОгирЫ на предприятий занимающиеся производством печатных плат, что позволило в 5-10 раз ускорить восстановление векторных описаний ПП.

список публикаций по теме работы

1. Задорин А.Ю., Захарова Г.Б., Черемисин И.Н. Алгоритмы анализа и синтеза изображений при автоматизации автоматического контроля изделий микроэлектроники // Тезисы докладов XII международной конференции по вычислительной механике и современным прикладным программным системам (ВМСППС 2003, 1-5 июля). Россия, г. Владимир, 2003. - Т.1, с. 281-282.

2. Задорин А.Ю., Захарова Г.Б., Черемисин И.Н. Система построения электронных эталонов печатных плат на основе восстановления их изображений // Труды конференций IEEE AIS'03, CAD-2003 ("Интеллектуальные системы", "Интеллектуальные САПР", 3-10 сентября). Россия, пос. Дивноморское, 2003. - Т.2, с. 177-180.

3. Задорин А.Ю., Захарова Г.Б., Черемисин И.Н. Система анализа изображений печатных плат с элементами интерактивного обучения // Труды конференций IEEE AIS'03, CAD-2003 ("Интеллектуальные системы", "Интеллектуальные САПР", 3-10 сентября). Россия, пос. Дивноморское, 2003.-Т.2, с. 328-342.

4. Задорин А.Ю., Захарова Г.Б., Черемисин И.Н. Автоматизация визуального контроля печатных плат // Прогрессивная технология и вопросы экологии в гальванотехнике и в производстве печатных плат. Материалы всероссийской научно-практической конференции. - Пенза. - 2004, с. 6567.

5. Черемисин И.Н., Захарова Г.Б., Задорин А.Ю. Разработка алгоритмов и средств автоматизации визуального контроля интегральных микросхем // Вестник Томского государственного университета. - 2004. - № 9(1).

6. Черемисин И.Н., Захарова Г.Б., Задорин А.Ю. Создание электронного представления печатной платы по ее сканированному изображению // Технологии в электронной промышленности. - 2005. - №2, с. 31-34.

7. Черемисин И.Н., Захарова Г.Б. Реконструкция технологических файлов по изображениям печатных плат // Гироскопия и навигация. - 2004. - №4, с. 97-98.

Подписано в печать 23.12.2005. Формат 60x84 1/16. Объем 1,4 п.л. Тираж 100 экз. Заказ 114

Размножено с готового оригинал-макета в типографии "Уральский центр академического обслуживания". 620219, г. Екатеринбург, ул. Первомайская, 91.

2.0 Qg ft

лгзе

1 236

ВВЕДЕНИЕ.

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

1.1. Введение.

1.2. CALS-технологии.

1.3. Векторизация изображений ПП.

1.4. Особенности топологии ПП.

1.5. Алгоритмы векторизации изображения.

1.5.1. Формирование бинаризованного изображения.

1.5.2. Методы описания топологии.

1.5.3. Выделение скелета изображения.

1.6. Обзор систем векторизации ПП и их сравнение.

1.7. Выводы.

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

1.1. Введение.

2.1. Представление изображений.

2.2. Основные понятия и функции.

• 2.3. Скелетизация изображения.

2.4. Удаление шумовых ветвей скелета.

2.5. Наращивание сегментов.

2.6. Шаблоны контактных площадок.

2.7. Поиск контактных площадок на основе шаблонов.

2.7.1. Поиск прямоугольных контактных площадок.

2.8. Сегментация скелета.

2.8.1. Сегментация по узловым точкам.

2.8.2. Сегментация по изменению направления цепи.

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

2.9. Соединение сегментов между собой и с контактными площадками.

2.10. Определение ширины проводника.

2.11. Выводы.

ГЛАВА 3. СИСТЕМА ВОССТАНОВЛЕНИЯ ВЕКТОРНЫХ ОПИСАНИЙ ПП.

3.1. Введение.

3.2. Особенности программной реализации.

3.2.1. Процедура скелетизации.

3.2.2. Удаление шумовых ветвей скелета.

3.2.3. Разбиение скелета на сегменты.

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

3.4. Аппаратная часть системы.

3.5. Общее описание программы Drupht.

3.5.1. Встраивание модуля Drupht в систему автоматизированного оптического контроля Aplite.

3.5.2. Структура системы восстановления векторных описаний ПП.

3.6. Технические характеристики Drupht.

3.7. Результаты испытаний.

3.8. Выводы.

Актуальность проблемы

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

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

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

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

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

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

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

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

Цели и задачи исследования

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

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

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

2. Разработать модели и алгоритмы для выделения и анализа скелетного описания топологии ПП для восстановления ее векторного представления.

3. Разработать методологию автоматизированного восстановления ПП.

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

Методы исследований

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

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

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

В результате проведённых исследований получены следующие ф новые научные результаты:

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

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

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

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

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

На основании разработанных моделей и алгоритмов создана программа восстановления векторного описания ПП Drupht, использующая в качестве входного изображения сканированное и затем бинаризованое и отфильтрованное изображение ПП, а также система векторизации ПП на основе Drupht. Программа внедрена на • предприятиях ЗАО «Техносвязь» (г. Екатеринбург) и ОАО «НИИ

Точной механики» (г. Санкт-Петербург), что подтверждается соответствующими актами.

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

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

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

3. Алгоритмы анализа топологии на основе скелетного описания с целью идентификации примитивов ПП.

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

Основные результаты работы докладывались и обсуждались на XII международной конференции по вычислительной механике и современным прикладным программным системам (г. Владимир, 2003), международной научно-технической конференции "Интеллектуальные системы" (Дивноморское, 2003), всероссийской научно-практической конференции "Новые информационные технологии и системы" (Пенза, 2004), V Всероссийской конференции с международным участием "Новые информационные технологии в исследовании сложных структур - ICAM'04" (Иркутск 2004), XVII Российской научно-технической конференции с международным участием "Неразрушающий контроль и диагностика" (Екатеринбург, 2005).

Публикации

Основные положения работы опубликованы в рецензируемых журналах «Гироскопия и навигация» [39], «Технологии в электронной промышленности» [38], «Вестник Томского государственного университета» [37]. Всего по теме диссертации опубликовано 7 научных работ [13-16, 37-39].

Объем и структура диссертации

Диссертация состоит из введения, трех глав, заключения, библиографического списка и приложений. Общий объем работы составляет 133 страницы машинописного текста. Диссертация содержит 44 рисунка и 7 таблиц. Библиография включает 80 источников.

3.8. Выводы

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

4. Разработан комплекс алгоритмов анализа топологии на основе скелетного описания с целью идентификации примитивов ПП:

• Алгоритм сегментации скелета по узловым точкам и изменению направления цепей .

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

• Алгоритм аппроксимации сегментов с помощью линейной регрессии.

• Алгоритм определения ширины сегментов по индексу сужения и по секущим.

5. Разработанные математические модели и алгоритмы реализованы в программе Drupht, которая может использоваться самостоятельно или в качестве модуля, встроенного в систему контроля ПП.

6. Осуществлено внедрение программы Drupht на предприятиях, занимающихся производством печатных плат, что позволило в 510 раз ускорить восстановление векторных описаний ПП.

1. Александров В.В., Горский Н. Д. Алгоритмы и программы структурного метода обработки данных. Л.: Наука, 1983. -205с.

2. Александров В.В., Горский Н.Д. Представление и обработка изображений: Рекурсивный подход. / Отв. ред. В.М. Пономарев. -Л.: Наука, 1985. 192с.

3. Аммерал, Л. Принципы программирования в машинной графике. — М.: Сол Систем, 1992. 224 с.

4. Башкиров О.А. Преобразование графа изображения, заданного в виде списковой структуры, в линейный массив // Методы и средства обработки сложной графической информации: Тез. докл. l-ой Всесоюзной конф. — Горький, 1983. — с.57-58.

5. Бобылев С.Н., Островский В.И. Инструментальные средства для разработки прикладных СТЗ // Системы технического зрения. Сборник статей. — Севастополь, 1992. — с.20-22.

6. Бутаков Е.А., Островский В.И., Фадеев И.Л. Обработка изображений на ЭВМ. — М.: Радио и связь, 1987. — 240 с.

7. Вакульский О.А. Построение остовов цифровых изображений. // Отбор и обработка информации. (Киев) — 1991. — №6. — с. 71-74.

8. Грановская P.M., Березная И.Я., Григорьева А.Н. Восприятие и признаки формы. — М.: Наука, 1981. — 208 с.

9. Дмитров В.И., Макаренков Ю.М. "CALS-стандарты" // Автоматизация Проектирования, №2-№4, 1997.

10. Дуда Р., Харт П. Распознавание образов и анализ сцен: Пер. с англ. — М.: Мир, 1976. — 512 с.

11. Задорин А.Ю., Захарова Г.Б. Система автоматизации оптического контроля фотошаблонов и печатных плат с использованием стандартного сканера // Гироскопия и навигация. 2001. - №1.

12. Задорин А.Ю., Захарова Г.Б. Система автоматизированного визуального контроля печатных плат Aplite // Chip News. Инженерная микроэлектроника. 2002. - №10 (73).

13. Кийко В.М., Шлезингер М.И. Алгоритм выделения отрезков осевых линий на графических изображениях. — Киев: АН УССР. — 1983.— 117 с.

14. Краснухин A. TeamPDM. Система управления жизненным циклом, которую действительно можно внедрить // САПР и графика, № 7, 2001. с.54-58.

15. Курочкин С. Возможные пути внедрения CALS-технологий // САПР и графика, № 8, 2001. с.77-79.

16. Лукашенко Г. Применение волнового алгоритма для нахождения скелета растрового изображения. http://www.ocrai.narod.ru/vectorv.html

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

18. Мартинес Ф. Синтез изображений. М.: Радио и связь, 1990. -192 с.

19. Норенков И.П. PDM управление данными в системах проектирования и электронного бизнеса // Информационные технологии, № 2, 2001. - с. 14-19.

20. Оптические методы контроля интегральных схем: Состояние и перспективы совершенствования / Вартанян Ю.С., Розиньков Н.С., Дубицкий Л.Г. и др. — М.: Радио и связь, 1982.136 с.

21. Павлидис Т. Алгоритмы машинной графики и обработки изображений: Пер. с англ. — М.: Радио и связь, 1986. — 400 с.

22. Патрик Э. Основы распознавания образов: Пер. с англ. (Левин Б.Р.), Советское радио, 1980 г. 408 с.

23. Платы печатные. Основные параметры конструкции: ГОСТ 23751-86. Введ. 1.07.87. - М. Изд-во стандартов, 1986.

24. Прэтт У. Цифровая обработка изображений: Пер. с англ. М.: Мир, 1982-Кн. 2-480с.

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

26. Садыков С.С., Кан В.Н., Самандаров И.Р. Методы выделения структурных признаков изображений. — Ташкент: Фан., 1990101 с.

27. Садыков С.С., Самандаров И.Р. Скелетизация бинарных изображений. // Зарубежная радиоэлектроника. — 1985. — №11. — с.30-37.

28. Себастиан Г. Процессы принятия решения при распознавании образов. Киев, 1965 г., 151 с.

29. Семенков О.И., Абламейко С.В., Берейшик В.И., Старовойтов В.В. Обработка и отображение информации в растровых графических системах. Мн.: Наука и техника, 1989. - 181 с.

30. Симонович С.В., Евсеев Г.А. Специальная информатика. Учебное пособие, ACT, 2004. 480 с.

31. Славин О.А., Корольков Г.В., Болотин П.В. Методы распознавания грубых объектов. В сб. "Развитие безбумажных технологий в организациях", 1999 г., с. 290-311.

32. Тептин Ю.Л., Нагаев Б.В., Климова И.И. Применение структурно-измерительного анализа для векторизации графической информации // В сб. "Системы технического зрения", Ижевск. -1999 г., с. 94-100.

33. Черемисин И.Н., Захарова Г.Б., Задорин А.Ю. Разработка алгоритмов и средств автоматизации визуального контроля интегральных микросхем // Вестник Томского государственного университета. 2004. №9(1).

34. Черемисин И.Н., Захарова Г.Б., Задорин А.Ю. Создание электронного представления печатной платы по ее сканированному изображению // Технологии в электронной промышленности, 2005. № 2.

35. Черемисин И.Н., Захарова Г.Б. Реконструкция технологических файлов по изображениям печатных плат // Гироскопия и навигация, 2004. №4.

36. Черемных С.В. и др. Моделирование и анализ систем. IDEF-технологии: практикум / С.В Черемных, И.О.Семенов, В.С.Ручкин.- М.: Финансы и статистика, 2003.-192 с.

37. Яншин В.В., Калинин Г.А. Обработка изображений на языке Си для IBM PC: Алгоритмы и программы. М.: Мир, 1994. - 240 с.

38. Arcelli С., Cordelia L.P., Levialdi S. From local maxima to connected skeleton // IEEE Trans. Pattern Analysis Machine Intelligence. — 1981. — PAMI-3. — pp.134-143.

39. Blum H. A transformation for extracting new descriptions of shape. // Sysmposium on Models for the Perception of Speech and Visual Form. — M.l.T. Press, 1964.

40. Borba J., Facon J. A printed circuit board automated inspection system // Proc. IEEE Midwest Symposium on Circuits and Systems. Rio de Janeiro, Brazil. - Aug. 1996. - p. 69-72.

41. Bowskill J., Katz Т., Downie J. Solder Inspection using an Object-Oriented Approach to Machine Vision. // SPIE Proceedings, Machine Vision Applications in Industrial inspection III. 1995. - pp. 34-45.

42. Calabi L., Hartnett W.E. Shape recognition, prairie fires, convex deficiencies and skeletons. // Amer. Math. Monthly, April 1968. — 1968. — №75. — pp.335-342.

43. Darwish A., Jain A. A rule based approach for visual pattern inspection // IEEE transactions on pattern analysis and machine intelligence.-Vol. 10, No. 1January 1998.

44. Delphi. Советы программистов / Под. ред. В. Озерова. Санкт-Петербург: Символ-Плюс, 2002. - 912 с.

45. Duda R.O., Hart Р.Е., Stork D.G. Pattern Classification / 2nd edition , John Wiley and Sons, 2000 r. 738 c.

46. Ercal F., Bunyak F., Feng H., Zheng L. Fast modular RLE-based inspection scheme for PCBs // Proc. SPIE Conf. On Architectures, networks, and intelligent systems for manufacturing integration. -Pittsburg. Oct. 1997. - SPIE Vol. 3203-06.

47. Freeman H. Computer processing of line-drawing images // Computing Survey. Vol. 6, No. 1. - March 1974.

48. Gerber RX-274 Format User's Guide / Gerber Systems Corp. -http://www.gerbersystemscorp.com

49. IEEE Standard No.: 1320.1-1998. Standard for Functional Modeling Language Syntax and Semantics for IDEF0. - 1998.

50. Jain A. Fundamentals of Digital Image Processing. — Prentice-Hall, 1989.-592 c.

51. Jarvis J.F. A method for automating the visual inspection of printedwiring boards // IEEE trans, on PAMI. — 1980. — Vol.2. — № 1. — pp.77-82.

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

53. Lam L., Lee S.W, Suen C.Y., Thinning Methodologies: A Comprehensive Survey. IEEE Trans. Pattern Analysis and Machine Intelligence, vol.14, pp.869-885, 1992.

54. Landau U. Estimation of a Circular arc Center and Its Radius // ® Computer Vision Graphics and Image Processing. 1987. - Vol. 38.-pp. 317-326.

55. Lee C. L., Wang P. S. P. A new thinning algorithm // Proceedings, 12th IAPR International Conference on Pattern Recognition. -Jerusalem, Israel, October 9-13. 1994, IEEE Comput. Soc. Press, Los Alamitos, CA, 1994, pp. 546-548.

56. Liang J., Piper J., Jing-Yan T. Erosion and dilation of binary images by arbitrary structuring elements using interval coding // Pattern Recognition Letters. April 1989. - Vol. 9, No. 3. - p. 201-209.

57. Mandeville R. Novel method for analysis of printed circuit images // 1MB J. Res. Dev. 1985. - 29 (1)0'Gorman L. KxK thinning //ф Comput. Vision, Graph, and Image Process. — 1990. — 51, №2.pp.195-215.

58. Moganti M. PCB inspection using differential competitive learning and Fuzzy associative memories . Master thesis. University of Missouri-Rolla. - May 1994.

59. Moganti M., Ercal F. A subpattern level inspection system for printed circuit boards // Computer vision and image understanding. 1998.- №1 (70).

60. Moganti M., Ercal F. Segmentation of printed circuit board images into basic patterns // Computer vision and image understanding.• 1998.-№1 (70).

61. Moganti M., Ercal F., Dagli C. Automatic PCB inspection algorithms: a survey // Computer vision and image understanding. 1996. - №2 (63).

62. Montanari U. A method for obtaining skeletons using a quasi-Euclidean distance. // J. ACM, October 1968. — 1968. — № 15. — pp.600-624.

63. Paven K., Deepak B. Pseudo one pass thinning algorithm // Pattern Recogn. Lett. — 1991. — 12, №9. — pp.543-555.

64. Pavlidis T. A thinning algorithm for discrete binary images // CGIP. — 1980. — Vol.13. — pp.142-157.

65. Pfaltz J.L., Rosenfeld A. Computer representation of planar regions by their skeletons // CACM. — 1972. — Vol.10. — pp. 119-125.

66. Plamondon R., Suen C.Y., Bourdeau M., Barriere C. Methodologies for Evaluating Thinning Algorithms for Character Recognition. Int'l. J. Pattern Recognition and Artificial Intelligence, special issue thinning algorithms, vol 7, no.5, pp.1247-1270, 1993.

67. Plamondon R., Srinari S. On-Line and Off-Line Handwriting Recognition: A Comprehensive Survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.22, № 1, January 2000.

68. RasterToVector systems / RasterVect Software. -www.rastervect.com

69. RasterToVector systems / AlgoLab Raster to Vector Conversion Toolkit. www.alqolab.com

70. RasterToVector systems / ScanFAB: PCB Artwork Scanning. -www.scancad.com

71. RasterToVector systems / RasterDesk (Consistent Software). -www.rasterarts.ru

72. Rosenfeld A. A characterization of parallel thinning algorithms // Information and Control. — 1975. — Vol.29. — pp.286-291.

73. Rosenfeld А., Как A.C. Digital picture processing. 2nd. Academic Press. — N.York, 1982. — pp. 85-190.

74. Serra J. Image Analysis and Mathematical Morphology. San Diego.- Academic Press. - 1982.

75. Smith S.J., Bourgoin M.O., Sims K., Voorhees H.L. Handwritten character classification using nearest neighbor in large databases. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.22, no. 9, pp.915-919, Sept. 1994.