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

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

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

переводы линий не должны быть больше 1 мм, отрезки прямых не должны

отклоняться от идеальных прямых более чем на 1 мм.

Отмеченное относительно эскизов слоев топологии плат печатного монтажа

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

автоматического чтения. Создание системы автоматического чтения для другого

типа документа в каждом случае требует, как отмечено ранее, специального

рассмотрения.

Линии координатной сетки Базовые линии

a

Поле изображения

c d

Риски

b

Базовые линии Край листа бумаги

Рис. 5. Базовые линии на эскизе топологии

3. Экспериментальная система автоматического чтения эскизов

слоев топологии плат печатного монтажа

Экспериментальные системы автоматического чтения документов

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

вводимых в ЭВМ с реальных документов аппаратурой растрового ввода. Такой

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

единая методика создания подобных систем.

Рассмотрим одну из таких систем, предназначенную для чтения эскизов

слоев топологии плат печатного монтажа.

3.1. Организация данных в памяти ЭВМ.

Графическая информация, считываемая с помощью фототелеграфного аппарата,

вначале образует в памяти ЭВМ двумерную двоичную матрицу I , в которой

единичные значения соответствуют зачерненным элементарным участкам растра

изображения, а нулевые - белым участкам.

В процессе обработки исходная матрица I трансформируется в промежуточное

описание, состоящее из матрицы линий и матрицы точек.

Каждый элемент матрицы линий и матрицы точек соответствует одному узлу

координатной сетки изображения. Элементы матрицы линий являются 8-ми

разрядными. Наличие единицы в каком-либо разряде указывает на прохождение

через узел координатной сетки линии, имеющей направление, закрепленное за

данным разрядом (см. рис. 6)

Элемент матрицы линий

1 2 3 4 5 6 7 8

Рис. 6. Cтруктура записи элемента матрицы линий

Рис 6.1 Cтруктура записи, описывающей прямолинейный

отрезок печатного проводника.

Элементы матрицы точек указывают наличие точки на изображении в узле

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

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

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

7.

Тип печатного проводника определяется в соответствии с табл.1.

В первом 32-разрядном слове описания указывается номер узла координатной

сетки (элемента матрицы линий), в котором находится один из концов

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

концом отрезка (рис.7) .

Описание контактной площадки может иметь один из трех форматов,

показанных на рис.7. Для контактной группы микросхемы описание

представляется в формате 1, если большая сторона прямоугольника,

изображающего группу, горизонтальна или в формате 2, если большая сторона

прямоугольника, изображающего группу вертикальна. В формате 1 номер узла

указывает на нижний конец отрезка единичной длины, изображающего контактную

площадку, в формате 2 - на левый конец такого отрезка. Формат 3

используется для описания контактных площадок круглой формы.

Параметр "количество точек" определяет тип контактной площадки в

соответствии с табл.2, а номер узла указывает на центр контактной площадки

Формат 1

0 1 2 3 15 16 17 31

0 0 0 . . . 0 Номер узла

Формат 2

0 1 2 3 15 16 17 31

0 0 0 . . . 1 Номер узла

Формат 3

0 2 3 31

Количество точек Номер узла

Рис.7. Структура записей описания контактных площадок

3.2. Этапы обработки эскиза платы

Процесс ввода и программной обработки эскиза платы печатного монтажа

разбит на два этапа. На первом - выполняется ввод изображения и

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

более компактное по сравнению с черно-белой мозаикой описание эскиза. На

втором -осуществляется коррекция матриц линий и точек, распознавание

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

3.2.1. Формирование матриц линий и точек.

Охарактеризуем более подробно первичную обработку эскиза, т.е. процесс

перехода от матрицы I к матрицам линий и точек. Первичная обработка эскиза

осуществляется в три этапа:

- обработка линий координатной сетки,

- обработка горизонтальных линий эскиза,

- обработка вертикальных и наклонных линий.

Программная обработка изображения базовых линий дает возможность

получить информацию о положении линий сетки на поле изображения. Это

позволяет на последующих этапах программной обработки производить

корректировку значений координат точек изображения в случае перекоса при

установке изображения.

Результатом обработки горизонтальных линий изображения должно быть их

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

выполняется следующим образом. Двоичная матрица I делится на зоны. Каждая

зона содержит три строки изображения. При этом положение центральной строки

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

задающей соответствующую горизонтальную линию координатной сетки. Каждая

центральная строка вместе с примыкающими к ней соседними строками

образует трехстрочную зону поиска горизонтальных линий. Поиск линии

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

входящих в эту зону строк. При этом минимальная длина линии считается

равной расстоянию между двумя соседними рисками координатной сетки.

Для каждой из выделенных в зоне горизонтальных линий находится

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

Соответствующие этим узлам элементы матрицы линии снабжаются описанием

горизонтальных линий.

В процессе поиска горизонтальных линий в зоне поиска могут

обнаруживаться участки, содержащие отходящие в вертикальном или

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

соответствующим образом и используется на следующем этапе первичной

обработки.

Описания вертикальных и наклонных линий изображения выполняются после

анализа фрагментов изображения, содержащих следы этих линий, обнаруженных

на предыдущем этапе первичной обработки. Окрестность узла координатной

сетки, близ которой были обнаружены следы линий, зондируется в шести

направлениях: вверх, вниз, вверх и влево, вверх и вправо, вниз и влево,

вниз и вправо от узла. Описания обнаруженных в окрестности данного узла

отрезков линий добавляется в соответствующий этому узлу элемент матрицу

линий. В случае, если зондирование, инициированное следом линии, не

обнаруживает вертикального или горизонтального отрезка, то это означает,

что точка выявлена и необходимо внести изменения в матрицу точек.

3.2.2. Выделение множеств фрагментов изображений

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

определенного типа и построение описаний для них.

Такими фрагментами являются условные графические изображения:

- контактных площадок круглой формы,

- библиотечных групп,

- областей металлизации,

- участков печатных проводников.

Распознавание перечисленных объектов основано на выделении локальных

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

признаками являются:

- штрихи соответствующей длины и направления в изображении

контактных площадок круглой формы,

- специфическое расположение штриха-указателя контура областей

металлизации.

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

в виде матриц линий и точек распознавание элементов изображения

осуществляется в следующем порядке:

- контактные площадки,

- элементы библиотечного типа,

3.2.4. Результаты эксплуатации системы

1. При использовании масштаба документа 2:1 возникают неудобства. Они

обусловлены трудностями изготовления эскиза человеком. Кроме того,

уровень ошибок, допускаемых системой, примерно в 3 раза выше,

чем при использовании масштаба 4:1.

2. При вводе эскизов размерами 250 х 400 мм, выполненных в масштабе 4:1 на

листе миллиметровой бумаги с помощью черного фломастера, среднее -

границы областей металлизации,

- печатные проводники.

Описания распознанных элементов представляются в виде таблиц. Они

содержат информацию о типах элементов и их координатах на поле изображения

эскиза.

По мере распознавания элементов изображения описание соответствующих

линий и точек удаляется из матриц линий и точек.

Для распознавания элементов библиотечного типа предварительно

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

изображении платы осуществляется наложением построенного таким образом

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

описываются как множество контактных площадок. Связи между соседними

контактами представляются в виде печатных проводников длиной 1 дискрет

координатной сетки.

После распознавания контуров зоны металлизации "покрываются" печатными

проводниками, описание которых заносится в массив печатных проводников.

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

библиотечного типа и границ областей металлизации в матрицах линий и

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

На нем выделяются прямолинейные участки печатных проводников,

определятся их типы. Соответствующие описания заносятся в массив печатных

проводников.

3.2.3. Методы обеспечения достоверности

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

системы считывания изображения. К их числу относятся следующие:

- на основе эвристических процедур,

- на основе генерации контрольного изображения.

Кратко рассмотрим существо этих методов.

1. В системе предусмотрены эвристические процедуры, основанные на

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

Система обращается к этим процедурам в случаях, когда не удается

завершить построение того или иного типа фрагмента изображения. Она

сообщает оператору о внесенных коррекциях.

2. Порождаемое системой контрольное изображение при безошибочном вводе и

обработке должно выглядеть как исходное. Генерация контрольного

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

обнаружения несоответствий вносятся исправления. Их ввод осуществляется с

помощью директив коррекции.

В директиве коррекции указываются координаты узла координатной

сетки и предписывается либо удалить либо поместить линию или точку в этот

узел. В случае, если корректировка касается линии, то в директиве должна

содержаться информация о ее направлении.

число ошибок было равным 3-4. При этом оператор вносит исправления,

относящиеся к 3-4 узлам

координатной сетки. Программная обработка на ЭВМ в среднем составляла

величину 30 мин. Время сверки контрольного документа - 10 мин.

3. По сравнению со сколочными системами время ввода информации в ЭВМ

сокрашалось в несколько раз. Однако программная обработка имеет узко

специализированный характер. Это обусловлено жесткими требованиями,

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

средств распознавания символов.

ЛЕКЦИЯ (4

Тема: “Обработка изображений, автоматически считанных с документации”

4.1. Общие сведения

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

информационного преобразования, в ходе которого осуществляется

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

В качестве дискретной первичной формы будем рассматривать черно-белую

мозаику, получаемую в памяти ЭВМ.

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

одних и тех же изобразительных средств(линий, символов),поэтому имеет смысл

выделить специально этап обработки для получения описания отрезков

линий. Они задаются координатами его концов и кодов символов с указанием

координат их расположения на поле изображения.

Результирующая форма для универсального этапа, которую мы назовем

дискретной вторичной формой, состоит из списка отрезков и списка

символов.

Запись первого списка состоит из полей, предназначенных для задания

координат концов отрезков.

Запись второго списка служит для координатной привязки символа к полю

документа и указания кода символа.

Универсальный этап обработки должен обеспечить решение двух задач:

- отделение символов,

- разделение несимвольной части изображения на отдельные элементарные

отрезки.

Указанные задачи являются разнородными, поэтому перед их решением

целесообразно разложить изображение на символьную и несимвольную части.

Каждая из частей подвергается специализированной обработке.

Рассмотрим задачу отделения символов.

4.2. Отделение символов в дискретной первичной форме

Предварительно определим понятие символа.

Назовем группой единиц множество единиц в одной строке матрицы, не

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

изображения, с координатами концов по оси абсцисс a, b и c, d называются

связными, если справедливо хотя бы одно из соотношений:

a ( c ( b;

a ( d ( b;

c - 1 = b;

d + 1 = a.

На рис.9.a приведены примеры связных групп единиц, а на рис. 9.б -

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

которых минимальный охватывающий их прямоугольник имеет размеры,

принадлежащие интервалам размеров символов по высоте и ширине (рис.10

). Подобное определение символа создает риск отделения части несимвольной

информации.

Сущность задачи отделения символов из исходной матрицы I, описывающей

изображение в дискретной первичной форме, сводится к нахождению в исходной

матрице фрагмента, который содержит символы. Далее каждый такой фрагмент

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

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

Затем, содержимое этих матриц анализируется в блоке распознавания.

Рис. 9. Отношение связности групп единиц:

a - связные группы; б - несвязные группы.

Рис. 10. Символ как фрагмент связных групп единиц

4.3. Алгоритм отделения

Выполняется однократный просмотр матрицы I .

При этом осуществляется :

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

превышают размеры символов.

2. Проверка связности между группами единиц (на основе указанных

соотношений).

3. Фиксация результатов.

Для фиксации результатов такого просмотра используются маски, каждая из

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

единиц. При этом используется поле масок M. Поле масок представляет собой

двоичную матрицу, совпадающую по размерам с исходным полем изображения I.

При совмещении поля изображения с полем масок каждая маска покрывает

фрагмент поля I, содержащий связную конфигурацию единиц.

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

размеры, т.е. играет роль минимального охватывающего прямоугольника.

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

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

распоряжении имеется соответствующая маска.

Более подходящей для решения задачи разделения изображения на символьную

и несимвольную части является полигональная форма описания изображения.

4.4. Полигональная форма.

4.4.1. Граничный контур

Введем понятие граничного контура.

Граничный контур - циклическая последовательность углов поворота границы

между черной и белой областями.

Пусть граничный контур обозначен gi.

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

Угол поворота граничного контура обозначим ai .

Угол поворота ai характеризуется следующим набором параметров:

- координаты центра угла - x(ai), y(ai) ;

- направления L1 (ai), L2 (ai) первого и второго луча;

- величина угла V (ai).

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

что при обходе границы между черным и белым область черного остается

справа от направления движения.

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

контуров.

На рис.11представлен фрагмент изображения.

1 2 3 4 5 6 7 8

| | | | | | | | |

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9