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

распределения их между человеком и ЭВМ должны также на основе анализа

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

Последнее предполагает выбор подходящих средств диалога и установление

языков общения.

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

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

Желательно, чтобы оператор, находящийся за терминалами АРМа, общался с

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

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

производительности труда.

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

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

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

схемами размещения элементов, эскизами топологии слоев печатного монтажа и

др.).

Другие способы описания того, что изображено на графическом

документе, затрудняют процесс восприятия информации человеком.

Очевидно, что и в случае, когда информация графического типа

передается от человека к ЭВМ , этот процесс должен быть для человека

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

САПР технология ввода графической информации представляет собой

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

предназначенные для обеспечения процесса ввода в ЭВМ графической

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

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

оператор при помощи специального устройства (щупа) обошел все

характерные точки документа и сообщил машине характеристики этих точек.

Данный труд лишен признаков творчества и его обычно поручали оператору.

Такое разделение труда между разработчиком и оператором сколочного автомата

нарушает единство творческого процесса и создает дополнительное звено в

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

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

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

полуавтоматическом режиме ввода графической информации с чертежа печатной

платы размером 150*300 мм, содержащей до 1500 контактных площадок и до

1200 соединяющих их линий. Время ввода информации в этом случае - 16 часов.

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

изображения.

Альтернативой технологии считывания графической информации и

использованием сколочных планшетов является технология, основанная на

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

графического документа.

В этом случае достигается существенный выигрыш во времени ввода

информации. Применительно к устройству ТС-6030 (автоматического

считывания и кодирования графической информации) ввод осуществляется в 12

раз быстрее.

Рассмотрим различные аспекты построения системы автоматического чтения

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

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

высокой достоверности считывания информации.

2.Требования к документам, автоматически считываемым системой

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

Документ является носителем информации, которая должна быть введена в

ЭВМ в качестве исходных данных для той или иной программы, входящей в

пакет прикладных программ САПР.

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

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

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

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

реализован узел и др.

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

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

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

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

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

человека.

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

обозначения элементов схемы, обозначения электрических связей, символы и

строки символов, регламентируемыми соответствующими ГОСТами.

Необходимо отметить, что документы, предназначенные для ввода в ЭВМ, как

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

может существенно отличаться от идеального. Конкретные отклонения от

идеального появляются, в частности, в том, что вместо прямой линии на

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

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

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

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

восприятии информации.

В свою очередь системы автоматического чтения графической информации

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

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

дефекты.

Однако следует отдавать отчет в том, что сложность систем,

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

и правильно считывать информацию, существенно выше по сравнению с

системами, такими способностями не обладающими.

Конкретно это может трансформироваться в более высокие аппаратурные

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

Тем не менее никакая из технических систем сегодняшнего дня или ближайшего

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

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

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

исполнения, что она не справится с его обработкой, в то время как человек

легко прочитает этот документ.

На основе отмеченного можно сделать вывод о том, что документы,

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

требований.

При разработке требований необходимо учитывать:

- технические характеристики растровой аппаратуры считывания,

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

разрабатывающего,

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

Опишем требования к изображениям на эскизах слоев топологии плат

печатного монтажа.

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

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

их фотошаблонов.

Изображение на эскизе слоя топологии платы печатного монтажа состоит

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

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

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

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

любой платы.

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

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

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

координатной сетки равен 5 или 2.5 мм, если для исполнения эскиза слоя

топологии выбран масштаб 4:1 или 2:1 соответственно. Метрическая привязка

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

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

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

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

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

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

рисунка на эскизах слоев топологии.

а) Контактные площадки

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

которых совпадают с узлами координатной сетки. Горизонтальный и

вертикальный штрихи креста имеют длину 1 дискреты.

Различают контактные площадки нескольких типов в зависимости от

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

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

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

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

Размер стороны квадрата - 2 дискреты . Число точек в группе указывает тип

координатной площадки.

а) б) в) г)

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

топологии.

Таблица 1.

|Количество |Тип |Диаметр, |

|точек | |мм |

|1 |2 |2,125 |

|2 |3 |2,5 |

|3 |7 |2,75 |

|4 |4 |3 |

|5 |8 |3,25 |

|6 |31 |3,5 |

|7 |80 |4 |

Таблица 2

|Число точек |Ширина |

| |проводника |

|1 |0,625 |

|2 |1,25 |

|3 |1,875 |

|4 |2,5 |

б) Печатные проводники

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

направлений: горизонтальное, вертикальное и два диагональных, т.е.

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

Горизонтальные и вертикальные отрезки проводятся только по линиям

координатной сетки, а диагональные - через узлы координатной сетки.

Точки изломов, разветвлений линий, изображающих печатные проводники

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

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

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

этом имеются в виду участки одинаковой ширины, они снабжаются

указателями ширины.

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

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

условными и абсолютными. Условными могут служить излом проводника и

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

Абсолютный указатель границ однородности представляет собой отрезок

прямой линии, имеющий длину 1 дискрету. Такой отрезок одним концом исходит

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

однородности. Граница изменения однородности обязательно должна

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

штриха абсолютного указателя границы однородности должно выбираться

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

В случае, если в точке нарушения однородности проводник претерпевает

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

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

этой точке.

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

линии печатного проводника. Число точек связано со значением ширины

(табл.2). Если одна из точек группы заменена штрихом (длина 1 дискреты),

направленным перпендикулярно линии проводника, то тогда указатель ширины

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

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

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

условный указатель, содержащий простой указатель ширины.

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

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

встрече с абсолютным указателем и при встрече с условным указателем, если

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

На рис.2 показан фрагмент эскиза слоя топологии для печатного проводника

и соответствующий ему фрагмент вида печатного проводника.

Рис. 2. Печатный проводник, а - фрагмент эскиза, б - фрагмент печатной

платы.

Особенностью реальных плат печатного монтажа является то, что в

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

ширины. С учетом этого обстоятельства любая указанная в табл.2 ширина может

быть объявлена основной. Объявление ширины печатного проводника основного

типа осуществляется пользователем перед сеансом ввода документа в форме

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

Аналогично для контактных площадок.

в) Области металлизации

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

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

В качестве его служит отрезок прямой линии длиной в 1 дискрету. Один из

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

составлять с ней угол 45 градусов. Свободный конец указателя контура

показывает область металлизации.

Линии контуров изображаются отрезками вертикальных, горизонтальных и

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

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

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

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

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

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

Под ними подразумеваются группы элементов, форма и взаимное расположение

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

площадок, микросхемы определенного типа или совокупность контактных

площадок для разъема. На эскизе такие группы изображаются в виде площадки,

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

подразумеваемая группа.

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

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

планарными выводами.

Рис. 3. Изображение области металлизации

Границы элементов библиотечного типа одного ряда контактных площадок

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

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

Рис . 4. Элементы библиотечного типа для контактных площадок

(фрагмент эскиза).

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

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

на 1 дискрету. Если какие-либо смежные контакты группы соединены между

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

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

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

площадкам.

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

особенности аппаратуры растрового считывания. В частности разрешающая

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

изображения. При этом необходимо, что на интервале длины, равной

минимальной толщине линии, укладывалось два отсчета устройства. Так,

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

менее 0.5 мм.

Существенную роль играет цвет красителя, которым наносятся линии на

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

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

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

как белый.

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

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

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

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

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

составленного из базовых линий, отходят риски длиной 5 мм. Расстояние между

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

шагу координатной сетки. Назначение рисок -обозначать линии координатной

сетки.

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

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

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

допускает углов схождения линий, меньших 45 градусов. Это существенно

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

вершине. Последнее упрощает обработку изображений после растрового

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

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

Причем эти прямые могут иметь только одно из четырех направлений, что

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

обработки.

При формировании требований к эскизам слоев топологии конкретизация

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

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

исполнителя эскиза. При этом разрывы в линиях не должны превышать 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