Разработка алгоритмов восстановления векторных описаний печатных плат на основе их растровых изображений тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Черемисин, Илья Николаевич

• Черемисин, Илья Николаевич
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Черемисин, Илья Николаевич

ВВЕДЕНИЕ.

• ГЛАВА 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 раз ускорить восстановление векторных описаний ПП.

Список литературы диссертационного исследования кандидат технических наук Черемисин, Илья Николаевич, 2005 год

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.