Программные продукты и системы

Настоящая работа посвящена описанию результатов построения основных модулей системы обработки топологических планов (топопланов) [1], которые предназначены для преобразования 2D-информации, записанной на твердом носителе, к ее электронному виду в ЭВМ.

Под топопланом мы будем понимать графическую схему, представленную в виде набора линий и условных знаков. Характерным представителем топоплана можно назвать машиностроительный чертеж - на нем нет сплошных закрашенных областей, все элементы обозначены линиями или штриховкой, то есть также линиями. На чертеже проставлены размеры, и он сопровождается пояснительным текстом. Все элементы пояснительного текста и размеры относятся к условным знакам. Несколько других примеров приведены в рабо- те [1]. К ним относятся задачи, связанные со строительными чертежами, фотошаблонами, слоями печатных плат, топографическими планшетами.

АРХИТЕКТУРА СИСТЕМЫ

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

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

БАЗОВЫЙ ПРИНЦИП СИСТЕМЫ

В основу системы как АРМ оператора-тополога положен принцип постоянного участия человека в процессе преобразования с минимальными усилиями. Основным критерием функционирования системы является адекватное преобразование информации от представления на твердом носителе к представлению в электронном виде без потерь и в форме, пригодной для использования в векторном редакторе САПР - базовом инструменте для электронной обработки топоплана.

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

РЕАЛИЗАЦИЯ ПОЭТАПНОЙ

ОБРАБОТКИ: ВВОД И ОЦИФРОВКА

ТОПОПЛАНА

Эта задача носит технический характер и в рамках данной работы не рассматривается. Проблемы, возникающие при ее решении, подробно описаны в [2]. Большинство областей приложения системы позволяет вводить изображение в бинарной форме, что позволяет исключить из обработки такие этапы, как сегментация и бинаризация. Некоторые области приложения в качестве объектов обработки предлагают цветные изображения (линии изображаются разными цветами). Наблюдения автора и некоторые теоретические подсчеты позволяют утверждать, что достаточно выполнить оцифровку изображения в полутоновой форме. Тогда цвета в силу их неоднозначного видения в черно-белом спектре будут иметь разные градации серого. Если цветов все же достаточно много (более десятка), то необходимо использовать цветовые фильтры для выделения отдельных цветов. В системе, описываемой в настоящей работе, обрабатывалось полутоновое изображение с толщиной пикселя 8 бит (256 градаций яркости, а реально использовалось около 220), которых хватало на сегментацию семи цветов.

СЕГМЕНТАЦИЯ И БИНАРИЗАЦИЯ

В системе предусмотрена возможность как ручного, так и автоматического выполнения процедуры. Для оперативного вмешательства оператора-тополога предусмотрены возможность просмотра всего изображения (полутонового) в любом диапазоне полутонов (например со 198 по 225), что позволяет отобрать ту информацию, которая относится к определенному логическому слою топоплана (например соответствующую оранжевому цвету).

Автоматическое выполнение процедуры предусматривает построение гистограммы изображения (рис. 1), которая представляет собой сумму гауссовских распределений пикселов по полутонам. Затем из этой суммы выделяются отдельные распределения, для которых вычислены среднее значение, среднеквадратичное отклонение и вес (высота пика). Далее полученные значения используются для сегментации изображения по слоям. Характерно, что наличие в сумме всего двух распределений позволяет назвать этот процесс бинаризацией.

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

-  Бумажный носитель информации со сроком службы не менее 10-20 лет.

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

- Стертые линии (например лезвием), от которых остался въевшийся в носитель след, образуют отдельные распределения пикселов.

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

Если оцифровать пустой носитель (без нанесенной на него информации), тогда гистограмма изображения представляет собой единственное распределение пикселов по полутонам. При нанесении на носитель информации единым технологическим способом при оцифровке дается изображение, гистограмма которого состоит из суммы двух нормальных распределений с различными средними значениями, высотами пиков (весом) и среднеквадратичным отклонением. В работе [2] рассматривается вариант бинаризации такого изображения по точке пересечения кривых распределений, на которые разбивается гистограмма.

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

1) Распределения, соответствующие пикселам фона и информационным пикселам, могут

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

2) Точки экстремумов на гистограмме не соответствуют средним значениям распределений пикселов, что связано со вкладом в эти пики других распределений.

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

4)  Участки носителя, подвергшиеся обработке (например чистке), образуют на гистограмме отдельное распределение, которое в большинстве случаев полностью покрывается основным распределением (рис. 2). Аналогичная ситуация возникает с загрязненными участками, только распределение смещено в другую сторону.

5) Линии, как правило, являются однородными, но разные линии могли быть нанесены в разное время, поэтому процесс "старения" приводит к выцветанию чернил и, следовательно, появлению нескольких распределений пиксеов линий. Иногда эти распределения имеют выраженные пики на гистограмме(рис. 3), нередко одно распределение покрывается другим, что приводит к возникновению ситуации, иллюстрированной рисунком 2.

Перечисленные зависимости позволили построить алгоритм разбиения гистограммы изображения на отдельные распределения пикселов. Его блок-схема отображена на рисунке 4. Каждая итерация глобального цикла приводит к выделению из гистограммы очередного распределения. Основой для него является наличие пика на гистограмме, который принимается за наивысшее значение плотности   распределения пикселов. По нескольким соседним точкам строится приближение к нормальному распределению, после чего происходит корректировка параметров предыдущих выделенных распределений. Если выделенное распределение покрывается одним или двумя распределениями (как в ситуации на рис. 2), то параметры этого распределения принимаются сразу, без корректировки параметров остальных распределений.

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

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

СКЕЛЕТИЗАЦИЯ

Эта процедура выполняется в автоматическом режиме над бинаризованным изображением для последующего использования на этапе векторизации и распознавания. Для решения этого этапа разработан и реализован алгоритм утончения MPSTA, описанный в [4]. Он дает хорошие результаты, но по своей структуре больше подходит к реализации на векторно-параллельной архитектуре. Более качественные результаты может дать алгоритм "движения воздушного шарика" [5], который рассчитан на применение архитектуры с последовательным процессором.

ВЫДЕЛЕНИЕ УСЛОВНЫХ ЗНАКОВ

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

ВЕКТОРИЗАЦИЯ

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

РАСПОЗНАВАНИЕ УСЛОВНЫХ ЗНАКОВ

Характерной чертой условных знаков, представленных на топопланах, является их промежуточное положение между рукописным и печатным текстом. Их английское название - handdrawn или handprinted. Здесь влияние характерных особенностей письма человека значительно уменьшено. Другой особенностью является их произвольная ориентация, что не позволяет применять широкий класс алгоритмов для решения задач распознавания.

При исследовании этой задачи автором был найден на основе работы [7] новый алгоритм, который определяет для любого знака

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

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

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

Автор выражает благодарность своему научному руководителю профессору, академику РАЕН Решетникову В.Н. за постановку задачи и постоянное внимание к работе.

Список литературы

1.    Решетников В.Н., Сотников А.Н. Проблемно-ориентированные системы обработки графических изображений сложной структуры в задачах визуализации //Программные продукты и системы. -1992. - №1. - С.48-51.

2. Фу К., Гонсалес Р., Ли К. Робототехника. - М.: • Мир, 1989.

3. Chalmond В. An «iterative gibbsian technique for reconstruction of m-ary images //Pattern recognition. - Vol.22. -№6.-p.747-761.

4. Еременко Г.В. Модифицированный параллельно-симметричный алгоритм утончения //Программные продукты и системы. -1994. - №4. - С.43-47.

5. Orit В. Line thinning by line following //Pattern recognition letters. -1988. - Vol.8. - № 4. - p.271 -276.

6. Kropatsch W.G., Tockner H. Detecting the straightness of digital curves in 0(N) steps //Computer vision, graphics, and image processing. -1989. - Vol.45. - № 1. - p. 1-21.

7. Leu J.-G., Huang I.-N. Planar shapoe matching based on binary tree shape representation.