Содержание к диссертации
Введение
ГЛАВА 1. Методы и средства автоматического восстановления векторных описаний ПП 11
1.1. Введение 11
1.2. CALS-технологии 11
1.3. Векторизация изображений ПП 15
1.4. Особенности топологии ПП 19
1.5. Алгоритмы векторизации изображения 22
1.5.1. Формирование бинаризованного изображения 22
1.5.2. Методы описания топологии 24
1.5.3. Выделение скелета изображения 29
1.6. Обзор систем векторизации ПП и их сравнение 35
1.7. Выводы 39
ГЛАВА 2. Разработка математических моделей и алгоритмов построения векторных описаний ПП 41
1.1. Введение 41
2.1. Представление изображений 41
2.2. Основные понятия и функции 42
2.3. Скелетизация изображения 43
2.4. Удаление шумовых ветвей скелета 56
2.5. Наращивание сегментов 58
2.6. Шаблоны контактных площадок 60
2.7. Поиск контактных площадок на основе шаблонов 64
2.7.1. Поиск прямоугольных контактных площадок 67
2.8. Сегментация скелета 70
2.8.1. Сегментация по узловым точкам 70
2.8.2. Сегментация по изменению направления цепи 72
2.8.3. Аппроксимация сегментов 74
2.9. Соединение сегментов между собой и с контактными площадками 80
2.10. Определение ширины проводника 82
2.11. Выводы 83
ГЛАВА 3. Система восстановления векторных описаний 85
3.1. Введение 85
3.2. Особенности программной реализации 85
3.2.1. Процедура скелетизации 86
3.2.2. Удаление шумовых ветвей скелета 91
3.2.3. Разбиение скелета на сегменты 92
3.3. Функционально-структурные модели системы 93
3.4. Аппаратная часть системы 95
3.5. Общее описание программы Drupht 97
3.5.1. Встраивание модуля Drupht в систему автоматизированного оптического контроля Aplite 104
3.5.2. Структура системы восстановления векторных описаний ПП 106
3.6. Технические характеристики Drupht 109
3.7. Результаты испытаний 112
3.8. Выводы 113
Заключение 115
Библиографический список
- Векторизация изображений ПП
- Обзор систем векторизации ПП и их сравнение
- Поиск контактных площадок на основе шаблонов
- Функционально-структурные модели системы
Введение к работе
Актуальность проблемы
Технологическая цепочка проектирования-изготовления печатных плат предполагает разработку принципиальной схемы средствами конструкторской САПР, ее размещение на заданном конструктиве и формирование управляющих программ для фотоплоттеров и сверлильных станков с применением автоматизированных систем подготовки к производству. В результате вся проектная информация по изделиям накапливается в архивах в виде векторных описаний, что позволяет при необходимости возвращаться к любой стадии разработки для внесения изменений или просто для воспроизведения старых образцов в новых условиях.
Векторное описание изображения представляет собой представление топологии как множества некоторых базовых примитивов с указанием типа, размера, координат осей и вершин и других параметров. При этом элементы изображения хранятся в виде математически описанных образов, таких как контуры, графические примитивы и подобные простые объекты.
Если на предприятии реализовано единое информационное пространство, в которое интегрированы управленческие системы класса ERP, конструкторско-технологические CAD/CAM-системы, системы управления данными - PDM, то все это становится элементами CALS-технологии, позволяющей осуществлять непрерывную информационную поддержку изделий на всех этапах жизненного цикла. В таких условиях не возникает проблем при поиске информации для перепроектирования или возобновления производства.
Внедрение подобных комплексных решений на сегодняшних российских предприятиях является единичным. Как следствие, архивы не всегда доступны, тогда и возникает задача восстановления векторного описания фотошаблона или печатной платы с целью ее воспроизведения. Также актуальна задача повторить плату неизвестного производителя, сделать ее аналог.
Восстановление векторного описания печатной платы вручную (сколка), которое используется на многих предприятиях, обладает рядом недостатков. Основными отрицательными сторонами в этом случае являются трудоемкость, малая производительность и низкая достоверность, особенно при малом размере изделий. Данная операция очень сильно утомляет зрение операторов, что, несомненно, представляет опасность для их здоровья.
Традиционно проблема восстановления векторного описания печатной платы решается применением программно-аппаратных комплексов, относящихся к классу систем технического зрения. На сегодняшний день разработаны зарубежные установки, выполняющие эту задачу, но вследствие их высокой стоимости и специфики отечественных производств их применение на наших предприятиях экономически не оправдано.
Существуют также недорогие универсальные программы, предназначенные для векторизации различных изображений. Данные программы недостаточно учитывают специфику изображений изделий электроники и корректно восстанавливают лишь небольшую часть изображения. Кроме того, многие векторизаторы отслеживают контуры изображений и не формируют технологических файлов для прямого погружения в САМ-систему.
В этом свете создание системы восстановления векторного описания представления ПП, использующей недорогую вычислительную технику - планшетный сканер для ввода изображений и персональный компьютер для обработки данных -является актуальным.
Цели и задачи исследования
Основной целью работы является решение проблемы восстановления векторного описания ПП в формате технологического файла. Практическим результатом диссертации является система восстановления векторного описания ПП, удовлетворяющая нуждам отечественных производителей ПП.
Для достижения указанной цели ставятся следующие задачи:
Исследовать методы анализа изображений ПП, построить их классификацию для выявления наиболее эффективных при векторизации топологии ПП.
Разработать модели и алгоритмы для выделения и анализа скелетного описания топологии ПП для восстановления ее векторного представления.
Разработать методологию автоматизированного восстановления ПП.
Программно реализовать разработанные модели и алгоритмы и провести соответствующие испытания.
Методы исследований
Методика исследований основана на использовании теории множеств, математической логики, теории графов, математической статистики, теории распознавания образов, эвристических алгоритмических решений.
Программная реализация системы основывается на методологии объектно-ориентированного программирования.
Научная новизна
В результате проведённых исследований получены следующие новые научные результаты:
Построена функционально-структурная модель процесса восстановления векторных описаний ПП в контексте CALS-технологий, с позиций которых процесс проектирования-изготовления ПП рассмотрен как элемент интегрированной информационной среды предприятия.
Построена функционально-структурная модель системы восстановления векторных описаний ПП.
Разработан алгоритм выделения скелета изображения с применением новых структурных элементов и вычислением индекса сужения для симметричного утонения.
Разработан алгоритм распознавания объектов изображения по предварительно заданным шаблонам, инвариантный к их ориентации, размерам и примыканию к другим объектам, основанный на вписывании шаблонов различного размера в исследуемые объекты.
Разработан комплекс алгоритмов анализа топологии на основе скелетного описания с целью идентификации примитивов ПП, в том числе алгоритм аппроксимации сегментов с помощью линейной регрессии.
Практическая ценность
На основании разработанных моделей и алгоритмов создана программа восстановления векторного описания ПП Drupht, использующая в качестве входного изображения сканированное и затем бинаризованое и отфильтрованное изображение ПП, а также система векторизации ПП на основе Drupht. Программа внедрена на предприятиях ЗАО «Техносвязь» (г. Екатеринбург) и ОАО «НИИ
Точной механики» (г. Санкт-Петербург), что подтверждается соответствующими актами.
На защиту выносятся:
Алгоритм распознавания объектов изображения по предварительно заданным шаблонам, инвариантный к их ориентации, размерам и примыканию к другим объектам, основанный на вписывании шаблонов различного размера в исследуемые объекты.
Модифицированный алгоритм выделения скелета изображения с применением новых структурных элементов и вычислением индекса сужения.
Алгоритмы анализа топологии на основе скелетного описания с целью идентификации примитивов ПП.
Апробация работы
Основные результаты работы докладывались и обсуждались на XII международной конференции по вычислительной механике и современным прикладным программным системам (г. Владимир, 2003), международной научно-технической конференции "Интеллектуальные системы" (Дивноморское, 2003), всероссийской научно-практической конференции "Новые информационные технологии и системы" (Пенза, 2004), V Всероссийской конференции с международным участием "Новые информационные технологии в исследовании сложных структур - ICAM'04" (Иркутск 2004), XVII Российской научно-технической конференции с международным участием "Неразрушающий контроль и диагностика" (Екатеринбург, 2005).
Публикации
Основные положения работы опубликованы в рецензируемых журналах «Гироскопия и навигация» [39], «Технологии в электронной промышленности» [38], «Вестник Томского государственного университета» [37]. Всего по теме диссертации опубликовано 7 научных работ [13-16, 37-39].
Объем и структура диссертации
Диссертация состоит из введения, трех глав, заключения, библиографического списка и приложений. Общий объем работы составляет 133 страницы машинописного текста. Диссертация содержит 44 рисунка и 7 таблиц. Библиография включает 80 источников.
Векторизация изображений ПП
Визуальная информация может быть представлена в аналоговом и цифровом видах. Цифровая, или компьютерная графика, в свою очередь, подразделяется на растровую, векторную и фрактальную [34]. Они отличаются принципами хранения и формирования изображения.
Основой растрового представления графики является пиксел (точка) с указанием ее цвета. Растровое изображение обычно представляется в виде некоторого множества точек, образующих прямоугольник, для каждой из которых задан цвет. Качество растра и размер файла определяется количеством этих точек, то есть изображение, описывающее один и тот же объект, может быть представлено с лучшим или худшим качеством в соответствии с количеством точек на единицу длины - разрешением. Разрешение обычно задается в точках на дюйм (dpi) или в пикселах на дюйм (ppi).
Кроме того, качество характеризуется еще и количеством цветов и оттенков, которые может принимать каждая точка изображения. Чем большим количеством оттенков характеризуется изображения, тем большее количество разрядов требуется для их описания.
Растровое представление обычно используют для изображений фотографического типа с большим количеством деталей или оттенков. К сожалению, масштабирование таких картинок в любую сторону обычно ухудшает качество. При уменьшении количества точек теряются мелкие детали и деформируются надписи (правда, это может быть не так заметно при уменьшении визуальных размеров самой картинки - т.е. сохранении разрешения). Добавление пикселов приводит к ухудшению резкости и яркости изображения, т.к. новым точкам приходится давать оттенки путем интерполяции, средние между двумя и более граничащими цветами.
Растровое изображение образца изделия, получаемое, например, с помощью сканера или видеокамеры, характеризуется избыточностью информации.
Векторная графика - это способ представления графических изображений, при использовании которого различные элементы изображения хранятся в виде математически описанных образов. Элементарный объект векторной графики - линия (прямая или кривая), и все, что есть в векторной иллюстрации, состоит из линий. Простейшие объекты векторного изображения объединяются в более сложные, например, объект четырехугольник можно рассматривать как четыре связанные линии, а объект куб еще более сложен: его можно рассматривать либо как двенадцать связанных линий, либо как шесть связанных четырехугольников. Из-за такого подхода векторную графику часто называют объектно-ориентированной графикой. Каждый из элементов характеризуется набором таких параметров, как цвет заливки, цвет и толщина обводки и пр. Главным преимуществом векторной графики является то, что при ее масштабировании не ухудшается качество выходного изображения, и в полном отсутствии эффекта пикселизации, который хорошо виден при увеличении размеров растровых графических данных. Также, для векторной графики характерно то, что при изменении размеров изображения не меняется размер выходного хранимого дискового файла в векторном формате и не увеличивается число контуров и точек изображения, а лишь корректируется выходной физический размер картинки изображения с увеличенным фрагментом.
Еще одним позитивным моментом векторной графики является то, что она обрабатывается растровым процессором по возможности с его максимальным разрешением, в результате чего контуры получаются более качественно прорисованными, чем эти же изображения, сделанные в растровом представлении. Кроме того, при небольшом числе элементов векторные файлы обрабатываются очень быстро, что уменьшает время, необходимое на его растеризацию в растровом процессоре. Векторный формат становится невыгодным при передаче изображений с большим количеством оттенков или мелких деталей (например, фотографий).
Фрактальная графика характеризуется тем, что в первую очередь генерирует новое изображение, а не описывает совокупность реальных объектов. Фрактальная графика, как и векторная — вычисляемая, но отличается от нее тем, что никакие объекты в памяти компьютера не хранятся. Фрактальное изображение строится по уравнению (или по системе уравнений), поэтому ничего, кроме формулы, хранить не надо. Изменив коэффициенты в уравнении, можно получить совершенно другую фрактальную картину. В данном исследовании фрактальной графикой заданы шаблоны контактных площадок.
Обзор систем векторизации ПП и их сравнение
Существующие системы (программы), применяющиеся для векторизации изображений изделий электроники, можно разделить на универсальные и специализированные. Универсальные системы разработаны для персональных компьютеров, недороги и используются в самых разных областях: векторизация чертежей, схем, картографических изображений и т.д. Данная универсальность не предусматривает специфики топологии изделий электроники, что сказывается на достоверности получаемого векторного изображения. Вдобавок, у данных программ отсутствует гибкость, возможность быстрой переналадки системы при появлении изделий с новой топологией.
Зарубежные специализированные системы, разработанные специально для распознавания растровых изображений изделий электроники, в большинстве случаев включают сложное оборудование, вследствие чего дороги и их использование экономически нецелесообразно в отечественных условиях, особенно на предприятиях с небольшим объемом производства. Детальное исследование методов, применяющихся в них, невозможно, так как данная информация не публикуется.
Рассмотрение некоторых систем и программ векторизации растровых изображений позволило выявить и конкретизировать основные недостатки существующих продуктов. Из всего множества систем были выбраны характерные представители каждого класса -от недорогих универсальных решений до специализированных программно-аппаратных комплексов [73-76]. Ниже приведены краткие описания рассмотренных систем.
Algolab Raster То Vector [74] - простой универсальный векторизатор. Предназначен для выделения осевых линий и границ самых различных изображений.
RasterVect [73] - универсальный векторизатор с мощными встроенными средствами работы с векторными изображениями. Предназначен для обработки различных чертежей, черно-белых рисунков, картографической информации и т.д.
ScanFAB РСВ Artwork Scanner [75] - программно-аппаратный комплекс, созданный специально для преобразования растрового изображения ПП в векторное, отличающийся быстротой работы и высоким качеством восстановления векторного описания. Из недостатков можно отметить высокую стоимость внедрения и обслуживания, сложность модификации при использовании в российских условиях, некорректное восстановление некоторых участков, выражающееся в появлении избыточных, накладывающихся друг на друга примитивов.
RasterDesk 6 [76] - многофункциональная отечественная система обработки технических чертежей, планов, схем, геодезических и картографических материалов, в том числе выполняющая векторизацию растровых изображений. Система не ориентирована специально на работу с изображениями ПП. Drupht - система восстановления векторных описаний, предлагаемая в диссертации, подробное описание которой приведено в главе 3. Сравнение производилось путем выставления каждой системе оценки от 0 до 5 баллов по ряду параметров. Результаты сравнения приведены в табл. 1. При сравнении были сформулированы следующие параметры:
Поиск прямоугольных и восьмиугольных площадок. Многие существующие системы ограничиваются возможностью поиска только круглых контактных площадок. Поиск контактных площадок прямоугольной формы реализуется сложнее, так как они задаются двумя размерами. Данный параметр также показывает качество поиска контактных площадок, форма которых искажена.
Поиск контактных площадок, соединенных с проводником. Данный параметр отражает качество поиска контактных площадок, границы которых пересекает примыкающий к ним проводник, и, соответственно, искажает форму распознаваемого объекта.
Точное измерение ширины проводника. Данный параметр показывает, насколько точно воспроизведена ширина участков проводника по сравнению с растром. Так как ширина проводника на растровом изображении колеблется в некоторых пределах, требуются алгоритмы ее оценки на всем участке.
Аппроксимация примитивов по направлению. Данный параметр показывает, насколько точно распознаются координаты концов проводников. Основная проблема многих существующих систем -смещение проводника и отклонение его направления относительно изображения на растре.
Быстродействие. Параметр показывает время, затрачиваемое на векторизацию тестового изображения.
Поиск контактных площадок на основе шаблонов
Анализ на наличие контактной площадки определенного типа производится в каждой точке скелетного изображения. В каждой точке (МХ,МУ) для подшаблона bj размера і вычисляется параметр а-,. Данный параметр равен количеству пикселов проводника исследуемого изображения, совпадающих с точками подшаблона, наложенного на изображение в точке (МХ,МУ):
Таким образом, для каждого типа шаблона получено упорядоченное множество V = {a1,...,aR} . В случае, если шаблон был наложен на объект, форма которого близка к форме шаблона и размер не превышает заданный максимум, то диаграмма V(i) будет иметь резкое падение значений в некоторой окрестности j (рис. 2.15).
Таким образом, признаком для распознавания контактной площадки является функция V(i). Классификация основана на обнаружении падения значения функции на некотором отрезке.
Пусть задан параметр е, обозначающий допустимое среднее отклонение расстояния от центра контактной площадки до ее границы s в процентах, то есть среднеквадратическое отклонение s, деленное er(s) на радиус: е =
Пусть также задан параметр Л є [0,1], равный максимальному допустимому отношению числа граничных точек контактной площадки, через которые проходит примыкающий к ней проводник, к общему числу точек ее границы. Тогда критерий обнаружения контактной площадки определенного типа можно сформулировать так: к,. = RoundUp{i (1 + е)) _У(к,)-У(і) ._-——— ті \rt-\ ,l min max Ki з; V(l) y/1 = max(y/j) y/j (1 - Я) w где RoimdUp(x) - функция округлення до следующего голого
Данный критерий имеет следующий геометрический смысл: объект относится к контактной площадке радиуса і, если некоторая критическая доля точек его границы отстоит от соответствующих точек шаблона данного радиуса на суммарное расстояние меньше заданного. Параметр Я имеет смысл задавать с таким расчетом, чтобы распознавались контактные площадки, к которым примыкает 2 проводника. Округление в (2.8), связанное с дискретным характером V(i), дает небольшое завышение у/., сказывающееся лишь на площадках с малым радиусом (г 5 при е=0,1), поэтому при наличии таких малых примитивов целесообразно проводить сканирование с большим разрешением.
Для описания общего алгоритма поиска контактных площадок необходимо определить операцию расширения изображения по коду N. Данная операция расширяет объекты изображения А, состоящие из пикселов с заданным кодом N, на непомеченные соседние пикселы (имеющие код 1), используя вспомогательное множество В: GmwN(A,B,N) = C D = {(p,q) 13/,7 : S»cib((p,q),(i,j)) = True л A{i,j) = N л A(p,q) = l} (N,ec\iu(p,q)eD C{p,q) = \ \A(p,q) в противном случае]
Введем описание контактных площадок как множество Seg = (N,(Sx,Sy),r,T,y/), где N - номер, (Sx,Sy) - координаты центра, г радиус, Т - индекс типа площадки, у/ - коэффициент схожести с шаблоном данного типа. Общий алгоритм поиска контактных площадок состоит из следующих шагов: 1) В процессе последовательного перебора всех точек скелета выбрать точку (х,у). 2) Построить множество максимальных значений Ч х, ) каждого типа контактных площадок, используя (2.8). При этом, если такое значение не найдено, присвоить соответствующему элементу 0. Ч (х,у) = {і//}, где і - индекс типа площадки 3) Выбрать максимальное ненулевое значение у/тгіХ =Ч (х,у). Если оно существует, то в данной точке найдена контактная площадка соответствующего типа. 4) Если данная точка не помечена контактной площадкой, пометить ее по текущему счетчику N d, и произвести расширение изображение в это точке по коду Npad столько раз, чтобы все пикселы контактной площадки были помечены. Если точка уже помечена площадкой, то есть А{х,у) \, то нужно проверить, являются ли предыдущий найденный центр и тип этой площадки оптимальным. Если y/mdX больше значения этого параметра у старой площадки, она удаляется из множества найденных площадок, а новая площадка туда добавляется.
Функционально-структурные модели системы
Для формализации поставленной задачи построены функционально-структурные модели разрабатываемой системы векторизации ПП с помощью языка IDEF0. На рис. 3.4 - 3.6 представлены функционально-структурные модели системы восстановления векторных описаний.
Система восстановления векторных описаний (рис. 3.4) анализирует полученное на входе растровое изображение ПП, результатом чего является векторное представление изделия, при этом процесс контролируют и корректируют людские ресурсы, руководствующиеся требованиями заказчика и стандартами на ПП (для краткости управление блоков представлено на рисунках схематично). На рис. 3.5 функция восстановления А-0 декомпозирована на основные этапы: сканирование изделия, его бинаризация и фильтрация, непосредственно автоматическое построение векторного описания, сравнение с растром и доработка вручную. Результат автоматического построения анализируется оператором системы путем наложения на растр, принимающим решение о доработке векторного описания вручную либо перезапуска автоматического построения с корректировкой параметров (рис. 3.5). В процессе анализа бинаризованного изображения производится инициализация параметров, скелетизация, поиск контактных площадок, удаление шумовых ветвей, разрезание скелета на сегменты, определение размеров сегментов, соединение примитивов и генерация векторного файла (рис. 3.6).
Для решения задачи построения электронных эталонов ПП время, затрачиваемое на получение и анализ изображения, не является критичным параметром системы, так как в большинстве случаев требуется восстановить электронные эталоны нескольких различных по топологии образцов, что не связано с обработкой постоянного потока продукции.
Наиболее дешевая из универсальных вычислительных систем, позволяющих выполнять ввод и обработку больших изображений -это персональный компьютер и планшетный сканер. Эксперименты показали, что планшетный сканер, выполненный по технологии CCD (ПЗС-линейка), позволяет получать реалистичные изображения ФШ и ПП. Оптическая разрешающая способность современных сканеров среднего класса изменяется от 600 до 2400 точек на дюйм, что дает размер пиксела от 42 до 10 мкм. Минимальная ширина проводников ПП и расстояний между ними изменяется от 750 до 100 мкм, в зависимости от класса точности. Следовательно, после дискретизации узкие проводники и расстояния будут иметь ширину от 2 до 75 пикселов. При наличии сканера с оптическим разрешением 1200 точек на дюйм минимальная ширина проводников и расстояний между ними будет изменяться в пределах от 4 до 35 пикселов. Данные положения были подтверждены экспериментами.
Размер бинарного изображения формата А4, то есть при глубине цвета 1 бит на пиксел, при разрешении от 600 до 2400 точек на дюйм изменяется от 4 до 67 МБ. Учитывая, что средний объем оперативной памяти, устанавливаемой в современный персональный компьютер, равняется 256 МБ, приведенные цифры свидетельствуют о принципиальной возможности обработки бинарных, полутоновых и цветных изображений ПП за приемлемое время.
Среднее время сканирования изображения ФШ размера А4 при глубине цвета 1 бит на пиксел и разрешении от 600 до 1200 точек на дюйм составило от 40 секунд до 2 минут. Время построения векторного описания варьируется от 2 до 10 минут.
Примерное время ручного восстановления ПП формата А4 средней сложности - 4-8 часов. Таким образом, время автоматического выполнения данной операции, равное нескольким минутам, является вполне приемлемым.
Таким образом, применение персонального компьютера и планшетного сканера для построения системы построения векторных описаний ПП оправдано как с технической, так и с экономической точек зрения.
Похожие диссертации на Разработка алгоритмов восстановления векторных описаний печатных плат на основе их растровых изображений
