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

• Автор: Кийко, Владимир Михайлович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Киев
• Количество страниц: 209 c. : ил

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

Глава I. ОБЗОР СТРУКТУРШХ МЕТОДОВ РАСПОЗНАВАНИЯ ГРАФИ

ЧЕСКИХ ИЗОБРАЖЕНИЙ.

Глава П. БЛОЧНЫЕ ДВУМЕРНЫЕ ГРАММАТИКИ И ИХ ИСПОЛЬЗОВАНИЕ ДЛЯ ЗАДАЧ СПИСАНИЯ И АНАЛИЗА ИЗОБРАЖЕНИЙ

2.1. Описание блочных двумерных грамматик

2.2. Постановка и способы решения задач распознавания изображений с применением блочных двумерных грамматик
2.3. Алгоритм распознавания изображений на наилучшее соответствие с использованием блочных двумерных грамматик и результаты его экспериментальной проверки.
Глава Ш. АЛГОРИТМЫ РАСПОЗНАВАНИЯ ГРАФИЧЕСКИХ ИЗОБРАЖЕНИЙ С ИСПОЛЬЗОВАНИЕМ БЛОЧНЫХ ДВУМЕРНЫХ ГРАММАТИК

КАК МОДЕЛИ ПРИ СПИСАНИИ КЛАССА ИЗОБРАЖЕНИЙ

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

знаков на утоньшенных изображениях
3.2. Алгоритмы выделения и анализа структуры изображений печатных плат
3.2.1. Описание алгоритма структурной сегмента
ции
3.2.2. Описание алгоритма анализа структуры изображений печатных плат.
Глава 1У.АЛГОРИТМЫ КОДИРОВАНИЯ ГРАФИЧЕСКИХ ИЗОБРАЖЕНИЙ
НА ОСНОВЕ ОПРЕДЕЛЕНИЯ СРЕДНИХ ОСЕЙ ИХ ЛИНИЙ..
4.1. Описание итерационного алгоритма
4.2. Описание однопроходного алгоритма
4.3. Описание параллельнопоследовательного алгоритма
4.4. Сравнительный анализ алгоритмов составления описания графических изображений на основе определения средних осей их линий
4.5. Реализация и практическое использование разработанных алгоритмов
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ


Известно также много других алгоритмов, основанных на выделении геометрических и топологических признаков изображения. Так, напри/ер, в работах [? П,-,,Юз] использовалось выделение штрихов и криволинейных выступов различных направлений, а в работах [-,,,,] обнаруживались точки окончания и разветвления линий, петли и другие цризнаки. В работах ? Г] выделение признаков осуществляется в процессе прослежи-вания контура изображения - границы межцу его черными и белыми клетками. К этим признакам относятся отрезки полигона, представляющего собой кусочно-линейную аппроксимацию контура, угловые характеристики контура, его выпуклости и вогнутости. Н.В. Завалишина и И. Б. Мучника ? В тех случаях, когда общее количество допустимых структурных описаний является значительно большим по сравнению с количеством выделяемых признаков и допустимых отношений между ними, для задания множества описаний целесообразно использовать грамматические конструкции, или просто грамматики. В соответствии с определениями, которые приведены в работах ? Первые работы ? Один из недостатков алгоритмов распознавания, использующих эти грамматики, заключается в их непомехоустойчивости. Влияние помех может проявиться в том, что цепочка, соответствующая распознаваемому изображению, или не удовлетворяет ни одной из грамматик, или может быть порождена сразу несколькими из них. Для более правдоподобного моделирования таких ситуаций К. Фу было предложено использовать стохастические формальные языки ? Другой подход к распознаванию последовательностей изображений был сформулирован В. А.Ковалевским ? МЭИ). Основная особенность этого метода заключается в том, что с помощью грамматики (т задается не множество распознаваемых изображений X, а множество УЩ специальным образом подобранных эталонных изображений. Отличительной особенностью работ К. А.К. Валужиса с соавторами [,зо] является учет влияния случайных помех не на уровне исходного изображения, а на уровне его структурного представления. Описываемый в работе ? Описанные выше грамматики по сути являются одномерными и поэтому плохо приспособленными для описания многих свойств изображений. Ниже кратко описываются результаты, полученные при разработке грамматик, позволяющих более естественно и экономно отражать двумерный характер распознаваемых изображений. Простое обобщение грамматик, порождающих цепочки, состоит в замене цепочек матрицами []. Грамматики такого вида названы грамматиками таблиц. Непроизводными элементами этой грамматики являются элементы матриц, а отношения между ними задаются с помощью двумерной конкатенации. Основываясь на идеях работы Нарасимхана [^4^, Федер разработал "плекс-грамматику" [зз]. Основные символы этой грамматики соответствуют непроизводным элементам с произвольным числом точек примыкания, в которых их можно соединить с другими подобра-зами. Правила подстановки грамматики записаны в бесконтекстной форме. Каждое из них имеет явно заданные списки соединений, в которых описаны все соединения непроизводных элементов. Был разработан также ряд других грамматик [~,,3б1, отличающихся как по типу используемых непроизводных элементов, так и по способу их соединения мевду собой. Особое место среди них занимают веб-грамматики, предложенные Пфальцем и Розенфель-дом []. Предложения, порождаемые веб-грамматиками, - это ориентированные графы с символами на вершинах ("вебы"). Л - множество начальных вебов и Р - множество правил подстановки. I, б. Известны примеры использования веб-грамматик при обработке изображений последовательно-параллельных двухполюсников 2Ь}9 изображений нейронных сетей ? Земли ? Используемые в этих работах алгоритмы позволяют выделить те участки изображения, которые являются синтаксически правильными по отношению к той или иной веб-грамматике. Надежность работы алгоритмов в значительной мере определяется уровнем помех и может быть существенно увеличена только в том случае, если в алгоритмах будет предусмотрена возможность решения задачи не только на полное, но и на лучшее соответствие по отношению к множеству структурных описаний или изображений, порождаемых грамматикой. Рис. Рис.