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

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

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

ГЛАВА I. Задачи кусочнолинейной аппроксимации и анализа

графических изображений

1.1. Задачи кусочнолинейной аппроксимации графических

изображений

1.2. Задачи структурного анализа графических

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

ГЛАВА П. Кусочнолинейная аппроксимация последовательностей

точек на плоскости

2.1. Основные определения к постановка задачи.

2.2. Решение оптимизационной задачи
2.3. Алгоритмы оптимальной аппроксимации.
2.4. Исследование алгоритмов.
2.5. Быстродействующий однопроходный алгоритм кусочно
линейной аппроксимации последовательностей точек на плоскости
ГЛАВА Ш. Структурный анализ изображений с помощью звездных
конструкции
3.1. Представление изображений звездочками.
3.2. Звездные конструкции. Общее определение и постановка задачи анализа
3.3. Алгоритмы анализа изображений на основе звездных
конструкций.
3.4. Исследование алгоритаов.
3.5. Разновидности звездных конструкций
ГЛАВА 1У. Решение практических задач обработки и анализа
изображений .
4.1. Система ввода и обработки графической информации
4.2. Практическая реализация однопроходного алгоритма
кусочнолинейной аппроксимации алгоритма 2.3.
4.3. Экспериментальная система анализа изображений блоксхем логических устройств
ЗАКПКНШИЕ.
СПИСОК ЛИТЕРАТУРЫ


Среди других работ первого типа отметим также работу Фримэна и Сахри [] . Фриглэна [] для кодировки чертежио~ -графической информации. Однако этот алгоритм является модельным и далек от практического использования. Среди работ второго типа, т. Ричард Беллман, который в небольшой работе [] впервые применил свои знаменитые функциональные уравнения к задачам кусочно-линейной аппроксимации. В работе Стоуна [9б] приведена постановка задачи. Считается заданной некоторая функция и число отрезков, которыми необходимо ее аппроксимировать. Необходимо найти аналитическое выражение каждого из этих отрезков, при котором минимизируется суша квадратов ошибок. В этой же работе приведено строгое решение задачи, которое сводится к решению системы интегральных уравнений. Р.Беллман, как уже говорилось, применил к этой схеме аппарат функциональных уравнений динамического программирования, чем упростил достижение решения. Веллмана. Эти работы также тлеют чисто теоретический интерес и к обработке изображений неприменимы. Во-первых, здесь рассматриваются не последовательности точек произвольной природы, а только функции одной переменной. Во-вторых, отрезки аппроксимирующей ломаной представляются в аналитическом виде, что не соответствует формату данных, требуемому в обработке изображений. Тем не менее эта тройка работ является очень ценной с методологической точки зрения. Структурному анализу графических изображений посвящено больше работ, чем кусочно-линейной аппроксимации. Это можно объяснить, вероятно, более интригующим характером задачи, а также большим количеством прикладных задач, требующих применения методов структурного анализа. П — мерном пространстве признаков. В качестве признаков выбирались, например,яркости изображения в клетках прямоугольного растра или какие-либо другие измерения на изображении. Сегодня уже стало очевидным, что представление изображения в таком виде является неудобным и скрывает многие важные топологические и структурные свойства изображений. К тому же, например, как правило двум изображениям одного класса в П -мерном пространстве вовсе не соответствуют две близкие точки. Из этого можно сделать вывод, что изображения необходимо представлять в принципиально ином виде. И исходя из такого представления, алгоритмы структурного анализа должны проверять выполнение тех или иных заданных соотношений на подмножествах непроизводных элементов. Наиболее известной монографией, посвященной структурным методам распознавания (или анализа) изображений является книга [J . В ней подробно описаны как сами методы теории формальных грамматик [V], так и возможные их применения к анализу изображений. Структурны! На этой основе строятся алгоритмы автоматического выделения непроизводных элементов на изображении и последующего их анализа. Алгебраический подход к решению задач распознавания образов и анализа изображений развит в работах Ю. Рассмотрит. В первых работах по структурному анализу изображений, появившихся в -е годы заметно желание перенести развитый к тому времени аппарат теории формальных грамматик Хомского М , [] на случаи цепочек непроизводных элементов изображения. При этом аппарат пытались применить практически без изменений, т. Вслед за самыми первыми работами Нарасимхана [зо], [зї] появились работы Шоу [], [] , Федера [],[5б] и других. Работа по непосредственному использованию методов теории формальных грамматик в обработке и анализе изображений делятся в свою очередь ка две группы. К первой группе относятся работы, в которых формальные грамматики используются для порождения и анализа изображений, представленных в виде множеств отрезков и дуг. Изображение представляется в виде цепочки прямолинейных отрезков либо,дуг, являющихся терминальными символами. В точках примыкания элемент монет соединяться с другими терминальными или нетерминальны™ элементами. Анализ изображения сводится к грамматическому разбору предложения, представляющего собой последовательность терминальных элементов. Несколько более общая структура предлагается в работах Федера [] ,[5б] . Нарасимхана[з(д|,[зї|.