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

 

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

Назовем группой единиц множество единиц в одной строке матрицы, не разделенной нулями. Две группы единиц, лежащие в соседних строках изображения, с координатами концов по оси абсцисс a, b и c, d называются связными, если справедливо хотя бы одно из соотношений:

 

          a Ü c Ü b;

           a Ü d Ü b;

            c - 1 = b;

           d + 1 = a.

 

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

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

 

 

 

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

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

 

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

 

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

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

 

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

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

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

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

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

 

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

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

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

 

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

 

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

   

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

 

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

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

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

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

Угол поворота граничного контура обозначим a_{i .}

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

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

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

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

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

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

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

                 1      2      3      4     5      6      7      8

 

           а)

 

№ угла	x	y	L1	L2	V
1	4	5	0	90	90
2	5	3	90	0	90

 

           б)

 

Рис. 11. а) фрагмент изображения, б) таблица значений параметров элементов граничного контура.

 

Достоинства полигональной формы:

           - не вносит искажений;

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

           - требует меньшего объема памяти (по сравнению с дискретной первичной формой в 10 - 20 раз).

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

 

Отделение символов

 

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

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

 

К символьным g_i будем относить такой граничный контур, для любых двух соседних элементов a_k, a_k+1 которого выполняется условие

R (a_k, a_k+1) < D ,

где R (a_k, a_k+1) - расстояние между центрами углов a_k, a_k+1;

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

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

Это не создает трудностей при построении соответствующего алгоритма.

 

ЛЕКЦИЯ №5

 

           Тема: “Специализированная обработка изображений для эскизов слоев
                   топологии плат печатного монтажа”

 

Специализированная обработка изображений выполняется после универсальной обработки. Она зависит от типа документа.

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

Задачи специализированной обработки:

           - обработка базовой линии,

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

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

           - выделение контуров границ областей металлизации,

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

           - обнаружение отрезков трасс печатных проводников,

           - формирование файла для описания изображения.

Кратко рассмотрим отмеченные задачи.

1) Обработка базовой линии

Выполняется в два этапа:

           - обнаружение базой линии;

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

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

           - все вертикальные элементарные отрезки, имеющие крайнее правое и крайнее левое положения;

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

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

2) Корректировка положения узловых точек

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

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

Значения y_п и y_л, являются ординатами правого и левого концов линии координатной сетки.

Документ имеет левый (правый) перекос, если для каждой горизонтальной линии координатной сетки выполняется условие

            y_п < y_л , ( y_п > y_л ) .

На рис.12 приведена иллюстрация левого перекоса изображения.

 

c

a

b

b’

d

yп yл yа y

xл                xа  xп                         x

 

 

Рис.12. Определение расстояния от точки на эскизе слоя топологии до горизонтальной линии координатной сетки

 

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

При небольшом перекосе изображения в качестве расстояния от точки а до линии координатной сетки можно взять длину вертикального отрезка аb, где b - точка пересечения вертикального отрезка с линией координатной сетки. Точка а привязывается к той линии координатной сетки, расcтояние до которой минимально.

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

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

3) Выделение контактных площадок

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

4) Выделение произвольных конфигураций типа контуров

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

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

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

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

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

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

5) Генерация завершающего файла

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

 

 

ЛЕКЦИЯ №6

 

Тема: “Основные проектные процедуры в САПР”

 

ВВЕДЕНИЕ

 

Достаточно очевидным является вывод относительно экспертного сопрождения подсистемы моделирования объекта проектирования.

Рассмотрим множество операций, которые совершает коллектив проектантов над этой подсистемой.

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

 

ОСНОВНАЯ ЧАСТЬ

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

В результате решения задачи синтеза может возникнуть счетное

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

Для большинства объектов низшим уровнем проектирования можно считать компонентный.

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

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

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

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

 

Тактирование

Распараллеливание

Смешанная

Конвеерная

Последовательная

Каскадная

Параллельная

Технических требований

Допусков

Параметров

Параметрическое

Структурное

Композиция

Декомпозиция

Параметричес-кий

Структурный

Идентификация

Преобразова-ние

Параметричес-кая

Структурная

Многовариант-ный

Одновариант-ный

Оптимизация

Синтез

Анализ

Алгоритмов

Параметров

Структуры

Проектные процедуры

 

Рис.1. Основные проектные процедуры в САПР

 

В процессе выполнения проектных процедур приходится всегда приводить в соответствие способ описания ТЗ, проектного решения (которое часто является ТЗ для более низкого уровня структуры проектирования) способу модельного представления объекта проектирования.

Преобразованию может быть подвергнуто либо ТЗ, либо собственно модельное представление.

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

Многие проектные решения принимаются в среде САПР в формализованном виде, зачастую на метаязыке системы. Поэтому для преобразования описания проектного решения (а иногда и ТЗ) используют процедуру идентификации проектного решения (ТЗ).

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

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

L_a   : X Þ Y ; a Î A,

здесь X и Y описывают множество входных и выходных сигналов .

Данное соотношение устанавливает связь между фазовыми переменными над множеством {A} конструктивных параметров a.

Теоретико-множественный анализ этого оператора и его отображения для модельного представления объекта проектирования показал, что существует счетное множество его преобразований, а также операций над ним: декомпозиция и композиция (преобразование) синтез и анализ. Операции над множеством {A} связаны с поиском единственного a_i , которое определяет L_a .

Возможно также либо определение Y при определенных L_a {} ,{A} и X, либо L_a{} при заданных Y и X .

Поскольку Y и X зачастую инвариантны к классу объектов проектирования в данной САПР, неизбежно преобразование описаний (представлений) Y , X , {A}. Формализм представления L_a {} требует решения задачи идентификации.

 

АНАЛИЗ ПРОЦЕДУР

 

Процедура анализа

 

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

 

Процедура синтеза

 

Решение задачи синтеза обеспечивает получение описания объекта проектирования по ТЗ на объект в виде структуры и совокупности значений конструктивных параметров. Параметрический синтез проводится конечное множество проектных решений. Если решение одно, синтезируемый объект будем называть "оптимальным по ТЗ". Оптимизация конструктивных параметров приводит к полному описанию объекта проектирования.

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