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

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

Егоров Станислав Феликсович

УДК 621.391:681.142

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

гциальность 05.13.14 - Системы обработки информации и управления

АВТОРЕФЕРАТ

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

Ижевск 1998

Работа выполнена в Ижевском государственном техническом

университете, г.Ижевск

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

доцент P.M. Гафаров

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

профессор В.Н. Кучуганов

кандидат технических наук В.А. Широков

Ведущая организация — Физико-технический институт

УрО РАН г.Ижевск

Защита состоится 1998 г. в ^Р^^часов

на заседании диссертационного совета К 064.35.02 в Ижевском государственном техническом университете по адресу: 426069, г.Ижевск, ул.Студенческая, 7, ИжГТУ.

С диссертацией можно ознакомиться в библиотеке ИжГТУ. Автореферат разослан "/3 1998 г.

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

диссертационного совета, /J^l^^

к.т.н., доцент [у <7 В.Н.Сяктерев

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

Актуальность темы. Интенсификация и автоматизация процессов

оизводства изделии радиоэлектроники (РЭА) требует_______

вершснствования обработки информации в -системах""управления и

нтроля------Технология печатных плат (ПП), обеспечивающая

готовление надёжных проводниковых соединений, является дешёвой, остой и гибкой. Основным сдерживающим фактором производства ляется большое число неавтоматизированных операций оптического нтроля (от 20 до 80 % трудозатрат). До сих пор на многих едприятиях визуальный контроль качества топологии ПП уществляется человеком. Основные недостатки использования ительного анализатора человека на контрольных операциях в оизводственном цикле — малая производительность и быстрая омляемость, низкая надежность и высокая трудоемкость. Так стоверность проверки составляет в среднем не более 65 %, а при ществующей тенденции к изготовлению всё более тонких и всё более гно расположенных проводников достоверность такого контроля одолжает падать.

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

Широкий круг задач, таких как измерение ширины проводников и [ределение координат контактных площадок при контроле печатных ат и фотошаблонов (ФШ), сводится к выделению объектов в юсгранстве с помощью СТЗ и их описанию — получению вокупности количественных и качественных характеристик, |разующих набор признаков, который в дальнейшем используется для опознавания объектов и их классификации; также при описании юисходит значительное сжатие информации.

Основные подходы к решению задачи описания изображения ПП и ФШ для их дальнейшего анализа и контроля на дефекты

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

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

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

Таким образом, актуальной является разработка структурны; методов описания объектов, обеспечивающих высокие точность 1 быстродействие, и допускающих простую реализацию. В данной работ разрабатываются и исследуются алгоритмы обработки информации ] СТЗ для контроля топологических рисунков ПП и ФШ, основанные н! структурно-измерительном описании топологии на базе выделена скелета изображения.

Целью работы является разработка и исследована быстродействующих и простых в реализации методов и алгоритмо! описания и контроля топологии изделий РЭА скоростны; контролирующих систем технического зрения для выявления дефекто! топологии и обеспечения требуемой достоверности распознавания I низкой стоимости.

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

Разработка модели представления дефектов дня всех классов топологии и размерностей дефектов на базе скслешот о описания. Разработка эффективного однопроходного постро'пю-сканпрующсго. алгоритма реализующего скелетное, описание-в - режиме"реального времени_____________________________________

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

Проверка достоверности результатов распознавания дефектов для определения её соответствия заданным критериям оценки СТЗ оптического контроля.

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

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

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

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

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

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

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

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

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

Реализаиия в промышленности. Результаты работь

использованы в автоматизированной системе визуального контрол ФШ и ПП "Микрон", внедренной на различных предприятиях Описываемый алгоритм скелетизации лег в основу разработанно] программы векторизации чертёжной и картографической информаци! УЕОА-ехргеэз, используемой на предприятиях г.Ижевска.

Апробация работы. Основные положения диссертационно] работы докладывались на 5 конференциях и семинарах.

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

Структура и объем диссертации. Работа изложена на 12' страницах основного текста, иллюстрируется 38 рисунками, 1 таблицами и состоит из введения, четырех глав, заключения, списк; литературы из 135 наименований и 3 приложений на 18 страницах.

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

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

Отмечается, что контроль ФШ и ПП всё еще выполняете человеком-контролёром, не обеспечивающим требуемую достоверност распознавания дефектов. Выделены основные дефекты топологи (табл. 1): качественные (разрывы и закоротки) и количественны (сужения, сближения, вкрапления, "дыры"), для идентификации которы необходимо провести сравнение их размеров с допуском. Анали методов и систем контроля на базе СТЗ выявил многообрази существующих подходов к описанию и анализу топологии ФШ и П1 как на основе сравнения описания топологии с эталонной, так ] сравнением с проектными нормами. Сделан вывод о необходимост) дальнейшего совершенствования автоматизации операции контрол топологии ПП средствами СТЗ и сформулированы основны требования: высокая достоверность распознавания дефектов, гибкость 1 переналаживаемость системы контроля, работа в масштабе реальной времени, низкая стоимость.

Основные традиционные методы описания топологии ПП и ФШ и опознавания дефектов, реализуемые в СГЗ, — это растровое или

ггурпое описание изображения и последующее его сравнение с---------

тоном или с проектными нормами.-При этом может использоваться иное описание топологии или описание только её характерных мест.

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

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

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

Таким образом формулируется цель исследования: требует разработать быстрые и эффективные методы выделения характернь мест топологии на базе скелетного описания и распознавания дефект« для систем контроля топологии ФШ и ПП.

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

Предлагается хранить скелет топологии и фона, сохраняющий каждой точке информацию о текущей ширине изображения, в ви, плоского неориентированного конечного графа G. Вершинами (узлам такого графа (aeG) являются характерные точки скелета — точки числом соседних не равным двум или описывающие ширину мены допуска (признак "малый размер") — и характеризуются координата» на плоскости х и у, шириной рисунка s в данной точке, типом t ( фон/1-рисунок топологии), р(а) — локальной степенью — количестве инцидентных вершине а рёбер. Рёбрами графа служат топологическ связи между характерными точками скелета. Кроме этого вводятс d(a,b) — расстояние на плоскости между вершинами а и b, m(a,b) определяет существование маршрута из вершины а в Ь.

Полученный граф состоит из непересекающихся подграс топологии Gt (Va:Gi(t(a)=l)) и подграфа фона Go> (Va:Go(t(a)=0)): G = GT U G® (GT nG$ = 0).

Каждый из дефектов (табл. 1) в рамках скелетной графовой моде.1 имеет чёткое структурное представление в терминах графа: узлов определёнными степенями и связями между ними. При контро сравнением с эталоном дефекты выступают как лишние элемент графоописания, а при контроле по проектным нормам каждый из вид* дефектов характеризуется ещё и узлами с "малыми размерами" (т размерами менее допуска на минимальное сужение/сближен; проводников топологии Dmin), что и позволяет их независш идентифицировать. Некоторые элементы описания могут носи вероятностный характер Р:

1) разрыв: (3a,b:GT)(3c:G<i>:P*0) [р(а)=1 & p(b)=l & -,ш(а,Ь) &

s(c)<Dmin & d(a,c)<DMiN] - существуют узлы графа топологии а и b степени =1 и не имеющие связывающего их маршрута, а также возможен (с вероятностью P^i узел с графа фона с признаком "малый размер" и находящийся на изображении между а и Ь;

2) закоротка (3a,b:GT)(3c:GT:P*0) [р(а)>3 & p(b)>3 & m(a,b) &

p(c)=2 & s(c)<Dmin & cem(a,b)]

Примеры дефектов топологии

Таблица

"ии дефекта

Описание без дефектов

Описание

дефектов

Примечания

13рыв юводника

I

Лишние два узла степени один и по фону узлы "малый размер"

еремычка гжду

)оводниками

:ороткое

мыкание

2

Лишние два связных узла степени три и узлы "малый размер"

едопустимое

оньшение

юводника,

.1кол

УЯШШяШШвЛ.

На скелете лишние узлы степени два с признаком "малый размер''

едопустимое

¡лижение

эоводников,

фОСТ

Лишние узлы степени три и один (отросток) и по фону узлы "малый размер"

гковина в эоводнике, 1ыра", ;ретрав

С

Лишние два двухсвязных узла степени три(цикл) и по фону узлы "малый размер"

крапление на эне, лишний [емент, :протрав

ш

гЫ

¥

Пи

Лишние два связных узла степени один и узлы "малый размер" (в т.ч. и по фону)

арушение шостности жтактной ющадки

П и ФШ

Лишние два связных узла степени три и один (отросток) и

узлы "малый размер"

нарушение "+" конфигурации

мещение гверстий

Лишние два узла степени один, нет цикла на графе скелета

3) сужение (Ba:Gi) [s(a)<dmin]

- существует узел графа топологии а с признаком "малый размер"

4) сближение (3a:G<j>) [s(a)<DMiN]

5) "дыра" (3a,b:Cb)(ac:Gr:Pi^)(3f,g:G«»:P2*0) [р(а)>3 & p(b)

& mi(a,b) & шг(а,Ь) & s(c)<Dmin & cem(a,b) & s(í)<Dmin & s(g)<Dmin]

- существуют узлы графа топологии а и b степени >3 и имеющие д связывающих их маршрута (mi и тг), а также возможны

(с вероятностями Р^Рг^О) узел с графа топологии находящийся на маршруте от а до b и узлы f и g с признаками "малый размер";

6) вкрапление (3a,b:GT)(3c:G®:P^0) [р(а)= 1 & p(b)= 1 & ш(а,Ь) &

s(a)<DMw:Pi*0 & s(b)<DMiN:P2*0 & s(c)<Dmin & d(a,c)<Dmin]

7) дефекты контактных площадок (КШ:

а) нарушение целостности (для ПП) (3a:GT)(3b,c:GT:P*0) [р(а)>3 & ш(а,а) & р(Ъ)>3 & bem(a,a) & s(c)<Dmin & cem(a,a)]

- на эталонном описании КП ПП (3a:GT> [р(а)>3 & m(a,a)] - цию возможны узлы степени >3 или с признаком "малый размер";

б) нарушение целостности (для ФШ) - на эталонном описании: (3a:GTK3e,f,g:GT) [р(а)=4 & р(е)=1 & m(a,e) & p(Q=l & m(a,f) & p(g)= 1 & m(a,g)] - крестообразном участке

графоописания, когда центральный узел а степени =4 связан маршрутами с тремя узлами e,f,g степени =1, - возникают искажения или дополнения:

(3b:GT)[p(a)*4 & p(b)=3 & (bem(a,e) v bem(a,f) v bem(a,g))]

- на описании появляется узел b, искажающий "+"-образную конфигурацию в "х"-образную;

в) смещение отверстия (За,Ь:Ст) [р(а)= 1 & p(b)= 1 & ш(а,Ь

- существуют узлы графа топологии а и b степени =1 и связанные маршрутом, тогда как на эталоне на этом месте присутствует другое описание: (3a:GT> [р(а)>3 & ш(а,а)] - цию

Предложенная структурно-измерительная модель представлен] топологии ФШ и ПП и методы её анализа отличаются простот« представления и универсальностью использования, т.е. возможность проводить контроль как сравнением с эталоном, так и по проектнь нормам.

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

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

) вписывание квадратов, центры вписанных квадратов образуют

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

Вписывание квадратов осуществляется утём анализа бинарного изображения кном 2x2 (рис. 1) слева направо и сверху низ. При этом в точке с! окна вычисляется азмер £ очередного вписываемого квадрата ак минимального расстояния от левой и ерхней границы объекта по формуле:

в точке Ь проверяется условие вписанности:

-вписан = ^ву+О&С&л £81+и)&(8и

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

1) а

с а

1-1 ¿-1

У-1 в и У+1

¡+1,]

Рис. 1

7 7 7 7 7 7

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

Связывание соседних

вписанных квадратов осуществляется за счёт введения понятия ухода из каждого вписанного квадрата. Уход — это априорное предположение о следующем вписанном квадрате, т.е. находясь в точке Ь выбирается максимальный по размеру квадрат а, с или с!, который и помечается как имеющий приход (понятие обратное уходу), такой квадрат называется добавленным. Кроме этого два ухода всегда формируются из "особого" случая комбинации в окне 2x2.

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

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

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

щ в

щ

"особый" случа

Рис. 3. Связывание квадратов

Рис. 4. Шумовые ветви скелета и их удаление

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

рактерного места, размер вписанного квадрата, массив номеров--------------

ылок на предыдущие связные узлы.---------------------

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

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

Исходными данными для предикатов алгоритма выделения елетных вписанных/добавленных квадратов являются условия тарного сравнения размеров квадратов А, В и С (рис. 1), признаки 1адрата Ь, а также код комбинации окна 2x2 (рис. 5):

[> = «А+1> & Ь(А>С)&~,(А=С)1 V <С+1> & [(А>С) V А=С)&(В>А)1 V <В+1> & |(А=С)&-,(В>А)|} & (КО V К15) V <1> & -,К0 & -пК15), — размер квадрата Б для граничных

<омбинаций равен 1, для внутренних (КО и К15) - вычисляется.

В-вписан = |(В=А)&(В>С) V (В>А)&(В=С) V (В>А)&(В>С)] & (КО V К15) V Ь(В<А)&-1(В<С)|&(К1 V К14) V -,(В<А)&(К2 V К13 V КЗ V К12) V ->(В<С)&(К4 V К11 V К5 V К10) V (Кб V К9 V К7 V К8),

— условие вписанности квадрата Ь, как локального максимума.

В-добавлеи = К1 V К14 V Кб V К9 V К7 V К8, — данные комбинации всегда порождают уходы.

4,-доб = [(В>С)&(А>С)1&(К0 V К15) V (К1 V К14) V (К2 V К13) V [КЗ v К12)

С-доб = [(В>А)&(А<С)1&(К0 V К15) V (К1 V К14) V (К4уК11) V (К5 V К10)

□-доб = [(А=С) V (В<А)&(В=С) V (В<С)&(В=А)]&(К0 V К15)

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

1®

ш Ш

ко

к15

ш

Щ

к1

"З'к

к14

к2

к13

ж

кз

Щ.

к12

ш Ш Ш

к4

кп

м

к7

»

и,

к8

Рис. 5. Комбинации изображения в окне

7. СМБкеЫоп == В-доб & В-вписан V В-нмеет_приходы V К1 V К14

V Кб V К9 V К7 V К8, — условие существования

скелетного квадрата Ь после фильтрации, сигнализирует о выделении очередной скелетной точки, как центра этого квадрата.

8. В->А = Ои18ке1е1оп & А-доб, — условие ухода из квадрата Ь в а

9. В—>С = СМЭкеЫоп & С-доб, — условие ухода из квадрата Ь в с.

10.В-Я) = СМБкеМоп & Б-доб, — условие ухода из квадрата Ь в (1 Далее в работе рассматриваются вопросы аппаратной реализац]

алгоритма выделения скелета на базе предложенных предикат! (рис. 6). Основу структуры аппаратного обеспечения составляют четы регистра А, В, С и 6, содержащие размеры соответствующих квадрат^ и признаки (вписан/добавлен, приходы и т.п.), три схемы сравнена комбинационная схема для реализации предикатов и буфер на строку формате регистров. Работа схемы описывается тремя тактами. I первом такте очередная точка бинарного изображения поступает регистр Б. Затем, признаки квадратов и результаты схем сравнен] подаются на комбинационную схему для реализации предикатов. 1 время второго такта вычисленные значения предикатов сохраняются регистрах. На третьем такте работы происходит подготовка к перехо, к следующей точке изображения. Если в регистре

Рис. 6. Функциональная схема автомата

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

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

В четвёртой главе представлено описание аппаратных и эограммных средств СТЗ "Микрон" для контроля топологии ФШ и П, приведены их технические характеристики, дан анализ проблем 1ализа скелетной модели топологии.

Структура СТЗ "Микрон" представлена на рис. 7, из неё следует, го ФШ сканируется на просвет ПЗС линейкой, а ПП на отражение иером и ФЭУ. Перемещение объекта контроля осуществляется олом на ЛШД с программным управлением.

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

Рис. 7. Структурная схема системы контроля

Аппаратный ввод

видеоданных ^-

Аппаратное вписывание квадратов и их связывание

X

Программное вписывание квадратов и их связывание

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

Параметры контроля топологии

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

| Эталонно^!

описание | топологии I

Нормализация представления графа связности характерных мест топологии

I

Сравнение графа связности с эталонным описанием

I

I

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

Выделение дефектных участков, их отображение и документирование

Рис. 8 . Структура программного обеспечения системы контроля

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

В ходе испытаний решались следующие проблемы анали: описания топологии:

1. Контурный шум. Флуктуация функции яркости при бинаризац изображения приводит к множественному искривлению грани! проводник/подложка. Хотя большинство шумовых скелетных ветв (95%) удаётся удалить ещё на этапе описания, но оставшиеся внос

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

Проводники под углом 45°.---------При списывании ортогональных

квадратов в проводники, идущие под углом~ 45V-наблюдаются ложные сужения связанные с тем, что ширина проводника определяется диагональю квадрата, а не стороной. Осуществляется выделение таких квадратов и коррекция их размера в V2 раз. Контактные площадки. Из-за отсутствия характерных точек на скелете кольца контактной площадки описание её носит грубый характер, что затрудняет точное определение центра. Сужение и разрывы кольца легко идентифицировать, но трудно оценить количественно на дефектность. Решение этой проблемы осуществляется путём усреднения параметров группы контактных площадок.

Полосы сканирования. Из-за недостаточности ширины

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

Оценка быстродействия алгоритма показала возможность зместить высокую скорость контроля с низкой стоимостью системы, к на реализацию графоописания на языке ассемблера IBM PC требовалось в среднем менее 30 команд на точку изображения, что зволяет при частоте видеоданных 5 МГц ограничиться процессором el Pentium 166.

При проведении испытаний системы контроля "Микрон" лучены следующие основные характеристики для ПП:

Вероятность пропуска дефектов 0,25 %

Вероятность ложной тревоги 2 %

Скорость контроля 18см2/сек

В приложении 1 приведена программа для формирования логики мбинационной схемы аппаратной реализации алгоритма вписывания вязывания квадратов при представлении её в виде ПЗУ.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Предложена структурно-измерительная модель представление характерных мест топологии и дефектов ФШ и ПП на базе скелетного описания. Показана её адекватность для всех классов топологии у размерностей дефектов. Требуемая достоверность распознавание дефектов топологии обеспечивается структурным характере?» описания.

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

4. Разработаны аппаратный и программный варианты реализации получения описания топологии. На их основе разработанс программное обеспечение системы контроля ФШ и ПП "Микрон" которое обеспечивает сканирование объекта, описание характерны? мест топологии, анализ описания и выявление дефектов.

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

6. Опытные испытания системы контроля топологии ФШ и ПП "Микрон" показали соответствие достоверности распознавания дефектов, как основного критерия оценки разработанных методик и средств описания и анализа изображений, требованиям производства.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ ИЗЛОЖЕНЫ В СЛЕДУЮЩИХ ПУБЛИКАЦИЯХ:

афаров P.M., Егоров С.Ф. Векторизатор чертежно-графической ^формации // Тез. докл. Ученые ИжГТУ - производству. Науч.-техн. энф. (Ижевск, 4-8 апр. 1994 г.) — Ижевск: ИжГТУ, 1994. — с. 105.

афаров P.M., - Афанасьев А.Н., Егоров С.Ф. Автоматическая система энтроля фотошаблонов И Тез. докл. Распознавание образов и анализ юбражений: новые информационные технологии. 2-я Всеросс. конф. ОАИ-2-95 (Ульяновск, 28 авг.-1 сен. 1995 г.) — Ульяновск: УГТУ, 1995. — . 4. — с.97-99.

афаров P.M., Афанасьев А.Н., Егоров С.Ф. Контроль фотошаблонов и ечатных плат // Тез. докл. Распознавание-95. 2-я Междунар. конф. (Курск, •13 окт. 1995 г.) — Курск, 1995. — с.105.

афаров P.M., Егоров С.Ф. Контроль изделий РЭА на базе СТЗ // Тез. экл. Ученые ИжГТУ - производству. Науч.-техн. конф. Кафедра ВТ Тжевск, 2-6 апр. 1996 г.) — Ижевск: Экспертиза, 1996. — с.26.

афаров P.M., Егоров С.Ф. Векторизация картографической информации // ез. докл. Ученые ИжГТУ - производству. Науч.-техн. конф. Кафедра ВТ Ижевск, 2-6 апр. 1996 г.) — Ижевск: Экспертиза, 1996. — с.27.

афаров P.M., Афанасьев А.Н., Егоров С.Ф. Автоматическая система онтроля фотошаблонов и печатных плат // Известия Тульского эсударственного университета. Информатика. — Тула:ТГУ, 1996. — Т. i. — №3. — с.21-24.

афаров P.M., Егоров С.Ф. Автоматическая система контроля отошаблонов и печатных плат на базе скелетного описания // Применение ычислительной техники в измерительных системах. Межвузовский эорник. — Ижевск: Экспертиза, 1997. — с.38-40.

афаров P.M., Егоров С.Ф. Модель представления топологии на базе келетного описания // Тез. докл. Распознавание образов и анализ зображений: новые информационные технологии. 3-я Всеросс. конф. Нижний Новгород, 1-7 декабря 1997) — Нижний Новгород, 1997. — 4.1. - с.45-47.

афаров P.M., Афанасьев А.Н., Егоров С.Ф. Система контроля топологии зделий РЭА на базе скелетного описания // Тез. докл. Распознавание бразов и анализ изображений: новые информационные технологии. 3-я ¡серосс. конф. (Нижний Новгород, 1-7 декабря 1997) — Нижний 1овгород, 1997. — 4.2. — с.65-67.

Jafarov R.M., Afanas'ev A.N., Egorov S.F. A Control System of the Topology f an Article of Radioelectronic Equipment Based on a Skeleton Description // 'attern Recognition and Image Analysis. — 1998. — Vol.8. — № 3. — p.387. jafarov R.M., Egorov S.F. A Topology Representation Model Based on a keleton Description // Pattern Recognition and Image Analysis. — 1998. — 'ol.8. — № 2. — pp.180-181.

¿г:

ИЖЕВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

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

Егоров Станислав Феликсович

УДК 621.391:681.142

ИССЛЕДОВАНИЕ И РАЗРАБОТКА АЛГОРИТМОВ

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

Специальность: 05.13.14 — Системы обработки информации

и управления

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

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

доцент Р. М.Гафаров

Ижевск -1998

СОДЕРЖАНИЕ

ВВЕДЕНИЕ...................................................................................................

1. ОБРАБОТКА ИНФОРМАЦИИ В СИСТЕМАХ

КОНТРОЛЯ ТОПОЛОГИИ ФОТОШАБЛОНОВ И ПЕЧАТНЫХ ПЛАТ..........................................................................13

1.1. ОСОБЕННОСТИ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ ПРОИЗВОДСТВА И КОНТРОЛЯ ПЕЧАТНЫХ ПЛАТ..........................................................................13

1.2. МЕТОДЫ И СИСТЕМЫ КОНТРОЛЯ ТОПОЛОГИИ...............20

1.3. МЕТОДЫ ОПИСАНИЯ ТОПОЛОГИИ.........................................29

1.4. МЕТОДЫ ВЫДЕЛЕНИЯ СКЕЛЕТА

ИЗОБРАЖЕНИЯ................................................................................35

1.5. ЦЕЛЬ И ЗАДАЧИ ИССЛЕДОВАНИЯ..........................................42

ВЫВОДЫ ПО ПЕРВОЙ ГЛАВЕ............................................................45

2. ВЫДЕЛЕНИЕ ХАРАКТЕРНЫХ ПРИЗНАКОВ

ТОПОЛОГИИ ФШИПП ПО СКЕЛЕТУ

ИЗОБРАЖЕНИЯ...............................................................................46

2.1. МОДЕЛЬ ТОПОЛОГИИ И ЕЁ АНАЛИЗ....................................46

2.2. ПОЛУЧЕНИЕ И ИССЛЕДОВАНИЕ СКЕЛЕТА ИЗОБРАЖЕНИЯ................................................................................53

2.3. ВЫДЕЛЕНИЕ ЭЛЕМЕНТОВ СКЕЛЕТА......................................64

2.4. СВЯЗЫВАНИЕ СКЕЛЕТНЫХ ТОЧЕК.........................................65

2.5. ФИЛЬТРАЦИЯ КОНТУРНОГО ШУМА.......................................67

2.6. ГРАФООПИСАНИЕ СКЕЛЕТА.....................................................71

ВЫВОДЫ ПО ВТОРОЙ ГЛАВЕ............................................................73

3. АППАРАТНАЯ И ПРОГРАММНАЯ РЕАЛИЗАЦИИ

АЛГОРИТМА СКЕЛЕТНОГО ОПИСАНИЯ

ТОПОЛОГИИ ФШ И ПП................................................................74

3.1. ПРЕДИКАТЫ ПЕРВИЧНОГО ВЫДЕЛЕНИЯ

СКЕЛЕТА...........................................................................................74

3.2. АППАРАТУРА ПЕРВИЧНОГО ВЫДЕЛЕНИЯ

СКЕЛЕТА...........................................................................................82

3.3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ВЫДЕЛЕНИЯ

СКЕЛЕТА И ЕГО ГРАФООПИСАНИЯ.......................................92

ВЫВОДЫ ПО ТРЕТЬЕЙ ГЛАВЕ.........................................................101

4. СИСТЕМА КОНТРОЛЯ ТОПОЛОГИИ "МИКРОН"................102

4.1. СОСТАВ АППАРАТНЫХ И ПРОГРАММНЫХ

СРЕДСТВ СИСТЕМЫ "МИКРОН"..............................................102

4.2. ОСНОВНЫЕ ПРОБЛЕМЫ АНАЛИЗА СКЕЛЕТНОЙ МОДЕЛИ ТОПОЛОГИИ.................................................................109

4.3. ОЦЕНКА ПРОИЗВОДИТЕЛЬНОСТИ СИСТЕМЫ КОНТРОЛЯ.......................................................................................112

4.4. ИСПЫТАНИЯ СИСТЕМЫ КОНТРОЛЯ

ТОПОЛОГИИ "МИКРОН".............................................................114

ВЫВОДЫ ПО ЧЕТВЕРТОЙ ГЛАВЕ...................................................121

ЗАКЛЮЧЕНИЕ......................................................................................122

СПИСОК ЛИТЕРАТУРЫ......................................................................125

ПРИЛОЖЕНИЯ.....................................................................................138

1. Программа формирования ПЗУ-логики

операционного автомата .............................................................139

2. Программа графоописания скелета полученного

вписыванием квадратов в бинарное изображение................141

3. Акты внедрения............................................................................156

ВВЕДЕНИЕ

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

Технология печатных плат, обеспечивающая изготовление надёжных проводниковых соединений, является дешёвой, простой, гибкой и представляет широкие возможности для автоматизации производства. Основным сдерживающим фактором является большое число неавтоматизированных операций оптического контроля (от 20 до 80 % трудозатрат) [98]. До сих пор на многих предприятиях контроль качества осуществляется человеком, оснащенным различными мерительными инструментами. Такой контроль, в условиях массового и крупносерийного производства, особенно в таких отраслях промышленности, как приборостроение, вычислительная техника, электронная и радиопромышленность является сдерживающим фактором, поскольку возникает явное противоречие между высокопроизводительным оборудованием, используемом для изготовления изделий и способами "ручного" контроля качества.

Основные недостатки использования зрительного анализатора человека на контрольных операциях в производственном цикле — малая производительность и быстрая утомляемость, низкая надежность и высокая трудоемкость. Поэтому достоверность проверки составляет в среднем не более 65 % [22], а при существующей тенденции к изготовлению всё более тонких и всё более тесно расположенных

проводников печатных плат достоверность такого контроля продолжает падать.

В связи с этим является перспективным разработка систем технического зрения (СТЗ) для замены зрительного анализатора человека или, по крайней мере, освобождение его от однообразной, вредной и утомительной работы. Одно из основных достоинств, которые открывают СТЗ, заключается в реализации практически 100 % контроля, что позволяет строить системы автоматического контроля качества продукции всего производственного комплекса. Потенциальные возможности автоматических систем распознавания почти безграничны. В настоящее время машинное зрение — уже реальность, хотя его возможности элементарны по сравнению со зрением человека. Однако уже имеются области, в которых машинное зрение способно заменить человеческое и даже по ряду характеристик превосходит его. Потребность в автоматическом визуальном контроле постоянно увеличивается и возрастает необходимость применения соответствующих анализаторов, обладающих требуемым быстродействием и способностью контролировать объекты с изменяющимися сложными структурами [102].

Работы в области создания СТЗ ведутся за рубежом с конца 60-х годов, первые образцы разрабатывались, главным образом, в университетах и научно-исследовательских институтах и имели академическую направленность. Теоретической основой для создания СТЗ были методы обработки изображений. Алгоритмы выделения и распознавания объектов конструировались универсальными, т.е. пригодными для анализа практически любых объектов. Первые серийно выпускаемые СТЗ появились в конце 70-х годов и предназначались для анализа трехмерных сцен в робототехнике [43,52]. Системы были дорогостоящими, сложными в изготовлении и эксплуатации, что не позволяло их использовать в реальных производственных условиях.

Сейчас в мире насчитывается множество фирм выпускающих СТЗ, но центр тяжести постепенно смещается из США в Азию (Япония, Корея, Тайвань, Малайзия и т.д.). Наибольшим успехом в производстве высокопроизводительных СТЗ для контроля качества печатных плат достигли следующие фирмы: Optrotech Inc. (Израиль), Orbot System (Израиль), Visionetics Corp. (США), AOI System (США), Lincoln Laser Comp (США), TI (США), Cambridge Robotic Systems (США), KLA-Tencor Corp. (США), Hitachi (Япония), Fujitsu (Япония), Vicheek (Англия), Vastra Flolunda (Швеция), Mania (Германия). Стоимость производимых ими систем составляет от 50 тыс. до 300 тыс. долларов [5,37,98].

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

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

Таким образом, автоматизация оптического контроля печатных плат необходима:

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

• для повышения производительности труда;

• для устранения утомительного для человека монотонного труда (число контролёров достигает 30% от числа рабочих);

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

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

Таким образом, системы автоматического контроля (САК), как разновидность СОИ, характеризуются существенным сжатием информации об объекте контроля за счет его описания (выделения количественно-качественных признаков изображения), которое сопоставляется с установленной нормой — эталоном. Основными проблемами разработки САК остаются повышение достоверности и быстродействия контроля. Вместе с тем, недопустимо чрезмерное увеличение стоимости систем. Рациональное сочетание характеристик качества и стоимости требует выбора приемлемых средств контроля или разработки новых [80].

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

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

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

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

соответственно промышленных САК на их основе.

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

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

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

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

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

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

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

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

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

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

7. Проверка достоверности результатов распознавания дефектов для определения её соответствия заданным критериям оценки СТЗ оптического контроля.

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

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

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

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

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

2. Эффективный сканирующий алгоритм выделения скелета изображения и представления его в виде графа связности в режиме реального времени.

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

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

Реализация в промышленности. Результаты работы использованы в автоматизированной системе визуального контроля ФШ и ПП "Микрон", внедренной на различных предприятиях (Приложение 3. Акты внедрения). Описываемый алгоритм скелетизации лёг в основу разработанной программы векторизации чертёжной и картографической информации VEG A-express [23,27], используемой на предприятиях города.

Структура и объем диссертации. Работа изложена на 124 страницах основного текста, иллюстрируется 38 рисунками, 8 таблицами и состоит из введения, четырех глав, заключения, списка литературы из 135 наименований и 3 приложений на 18 страницах.

Апробация работы. Основные положения диссертационной работы докладывались на 5 конференциях и семинарах.

Публикации. По материалам диссертации опубликовано 11 работ [23-31,113,114], аппаратная часть находится на стадии патен�