автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Разработка и исследование методов анализа и обработки графической информации в условиях неопределенности

ВВЕДЕНИЕ.

Глава 1. РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ

ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ ПОЛУТОНОВЫХ ИЗОБРАЖЕНИЙ.

1.1. Основные определения.

1.2. Постановка задачи и анализ известных алгоритмов предварительной обработки изображений.

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

1.3.1. Постановка вариационной задачи выбора наиболее гладкой функции яркости.

1.3.2. Дискретная модель для выбора наиболее гладкой функции яркости.

1.3.3. Решение вариационной задачи методом сопряженных градиентов.

1.3.4. Выделение характерных точек изображения.

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

1.4.1. Вероятностная модель края. Дискриминантная функция.

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

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

1.5. Разработка метода выделения движущихся объектов по серии кадров.

1.6. Оценка характеристик движения объектов по серии кадров.

1.7. Выводы.

Глава 2. РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ

ОБРАБОТКИ И ВЫДЕЛЕНИЯ ИНФОРМАТИВНЫХ

ПРИЗНАКОВ КОНТУРНЫХ ИЗОБРАЖЕНИЙ.

2.1. Постановка задачи. Анализ известных алгоритмов.

2.2. Теоретико-графовая модель получения связного контура.

2.2.1. Основные определения.

2.2.2. Постановка оптимизационной задачи.

2.2.3. Алгоритм выделения контурного изображения.

2.3. Выделение базового контура объекта.!.

2.4. Разработка и исследование метода сглаживания контурного изображения.

2.4.1. Постановка и описание задачи.

2.4.2. Минимизация функционала методом сопряженных градиентов.

2.4.3. Задача сглаживания контура при нечетких ограничениях.

2.5. Выделение контрольных точек контура.

2.6. Выводы.

Глава 3. РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ И

АЛГОРИТМОВ РАСПОЗНАВАНИЯ ПЛОСКИХ ПРОЕКЦИЙ ТРЕХМЕРНЫХ ОБЪЕКТОВ.

3.1. Постановка задачи. Анализ известных алгоритмов.

3.2. Модели описания формы трехмерных объектов.

3.3. Генерирование плоских проекций трехмерных объектов.

3.4. Оценка положения трехмерных объектов в пространстве по их контурным изображениям.

3.5. Применение различных мер близости для классификации контурных изображений.,.

3.6. Разработка и исследование теоретико-множественного метода классификации контурных изображений.

3.6.1. Вероятностная модель контурного изображения.

3.6.2. Теоретико-множественные операции над изображениями. Меры включения и равенства.

3.7. Выводы.

Глава 4. РАЗРАБОТКА МОДЕЛИ ИНТЕЛЛЕКТУАЛЬНОЙ СИСТЕМЫ ОБРАБОТКИ И КЛАССИФИКАЦИИ МАЛОРАЗМЕРНЫХ ИЗОБРАЖЕНИЙ.

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

4.2. Общий алгоритм решения задачи обработки и классификации графической информации.

4.3. Алгоритмическое обеспечение интеллектуальной системы обработки изображений.

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

4.5. Выводы.

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

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

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

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

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

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

Изображение Решение

Рис. 1. Система технического зрения

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

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

Проанализируем несколько основных систем описания и распознавания объектов сцены, применяющихся в настоящее время за рубежом. В работах [6-8] сравнение объекта с эталоном происходит с помощью сравнения их отображений на гауссову сферу - расширенных гауссовых изображений (РГИ). Данный метод отличается простотой описания сцены и получения РГИ изображения. Однако имеется существенный недостаток -неоднозначность РГИ изображения для невыпуклых тел. Кроме того, такое описание чувствительно к перекрытиям объектов сцены и трудно сегментируется на отдельные части.

В работах [9,10] для описания объектов сцены и модельных объектов использовались результаты локальных измерений сцены и нормалей к поверхностям. Центральным понятием данных систем является интерпретация. Интерпретации заключаются в сопоставлении каждой считанной точки объекта сцены с некоторой поверхностью модельного объекта. Если интерпретация сохраняется при преобразовании, изменяющем положение всех точек поверхности объекта, то считается, что соответствие между объектом сцены и модельным объектом установлено. Недостатком данного метода распознавания является сильная чувствительность к помехам и шуму.

1кесЫ в работе [11] развил метод распознавания объектов в задачах двоичного перебора. В силу особенности метода двоичного перебора данная система может идентифицировать только один объект на сцене. Решение задачи сопоставления объекта сцены и модельного объекта производится с помощью так называемого дерева интерпретаций, которое является представлением различных видов одной модели. В качестве недостатка данного метода можно отметить низкое быстродействие алгоритма за счет большого числа операций сравнения (в общем случае - полного перебора).

В [12] приведена система для распознавания и локализации твердых объектов в пространстве. Описание объектов сцены и модельных объектов осуществляется в терминах линейных особенностей геометрических объектов, таких как точки, прямые, плоскости. Преобразование сцены оценивается с помощью кватернионов. Алгоритм сравнения данной системы не допускет наличия на сцене других объектов, за исключением модельных. Кроме того, описываемая система оказалась очень чувствительной к малым изменениям поверхности.

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

Система распознавания на основе обобщенных конусов и использования индексной схемы описания особенностей приведена в работе [15].

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

В [16,17] предложена система понимания изображений ACRONYM, использующая для описания модельных объектов и объектов сцены обобщенные цилиндры. Данная система является интерактивной, т. е. предполагает участие человека в процессе принятия решений. Пользователь должен построить графы модельных объектов и так называемый граф ограничений, описывающий множества ограничений для различных классов объектов и используемый далее для направления вычислительного процесса сравнения модельных объектов с объектом сцены. Основное ограничение на применение данной системы заключено в том, что модельные объекты и объекты сцены должны быть представлены обобщенными цилиндрами. Кроме того, необходимость присутствия человека сужает возможность использования системы для автоматического распознавания.

В работе [18] описание объекта модели или сцены осуществляется с помощью так называемых атрибутных графов. Построение этих графов начинается с сегментации поверхностей объектов. Простые идеи сегментации поверхностей описаны в работах [19,20]. В качестве границ сегментации используются скачки границы, т.е. кривые, где поверхность терпит разрыв, и изломы, т.е. кривые, где терпит разрыв нормаль к поверхности. Результатом такого процесса является символьное представление сцены в виде графа, вершины которого соответствуют частям поверхности, а ребра - существующим связям между этими частями. Сравнение объектов сцены с модельными объектами базы данных осуществляется в трех модулях: модуле отбора, модуле сравнения графов и модуле-анализаторе. Из всех вышеперечисленных систем данная система распознавания представляется наиболее корректной и имеющей достаточно высокое быстродействие.

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

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

Основной задачей любой СТЗ является распознавание объекта на сцене. В многоплановой задаче анализа сцен можно выделить несколько основных подзадач [21]:

1) приведение исходного изображения к удобному для дальнейшего распознавания виду - фильтрация, сглаживание, повышение контрастности исходного изображения;

2) локализация объектов сцены - выделение контуров и отделение от фона каждого целеподобного объекта сцены;

3) выделение ключевых признаков анализируемых объектов, наилучшим образом характеризующих каждый объект;

4) определение ориентации локализованных объектов в пространстве;

5) построение модели анализируемого объекта;

6) сопоставление локализованного объекта сцены с эталонным объектом.

Перечисленным техническим задачам можно поставить в соответствие математические задачи анализа и классификации изображения:

- задача предварительной обработки изображений;

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

- задача классификация изображений.

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

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

Задача предварительной обработки изображений. Под предварительной обработкой изображений понимается совокупность процедур, приводящих изображение к виду, удобному для анализа, и улучшающему его качество: фильтрация случайных помех, сглаживание, восстановление резкости расфокусированных изображений, выделение контуров целеподобных объектов и отделение их от общего фона изображения. В данную математическую задачу включаются технические задачи 1) и 2).

Двумя существенными проблемами на этапе предварительной обработки являются следующие: какие входные данные можно считать пригодными для обработки и распознавания, и какая именно обработка исходных данных (обычно отличающихся чрезвычайной избыточностью) приводит к получению признаков, позволяющих проводить классификацию. Решению этих проблем в литературе [1,2,4,22] уделяется много внимания, но на сегодняшний день неизвестны формализованные методы, позволяющие получить ответ на эти вопросы. Априорные знания, интуиция, метод проб и ошибок, экспериментальные данные так или иначе используются при определении признаков [2].

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

Наиболее распространенным методом борьбы с шумом является метод усреднения [5,23-25]. В данном методе сглаженное изображение получается путем усреднения значения функции яркости в каждой точке исходного изображения в зависимости от значений функции яркости соседних с обрабатываемой точкой. Недостатком такого подхода является появление расплывчатых краев изображения. Для уменьшении такой расплывчатости применяются усредняющие фильтры [26,27], в которых вместо усреднения интенсивность каждой точки заменяется средним значением интенсивности в заданной окрестности точки. Также для этой цели применяются нелинейные фильтры [27,28], которые позволяют предотвратить уничтожение резких границ объектов при глобальном сглаживании изображения.

После процедуры глобального сглаживания изображения, как показано в [29], с целью уменьшения вычислительных затрат на распознавание отдельных объектов необходимо произвести редукцию сцены путем разделения ее на ряд отдельных субсцен, содержащих один объект (или несколько в случае перекрытия изображений). Для выполнения данной задачи необходимо провести операцию отделения целеподобных объектов от фона. В работах [30,31] предлагается распространенный метод порогового разделения, основанный на построении гистограммы функции яркости и нахождении на ней точек локальных минимумов.

Для движущихся объектов для решения данной проблемы применяется анализ нескольких последовательных кадров данного изображения. Под анализом в данном контексте понимается процедура формирования разностного кадра и дальнейшая его обработка с целью выделения объектов движения. В работе [32] предлагается метод максимальных площадей выделения целеподобных объектов в рамку. В [33] - альтернативный метод минимальных площадей. Кроме того, на данном этапе существенный интерес представляет информация о параметрах движения [30], например, относительной скорости и направлении перемещения. В дальнейшем полученная информация является входными данными для процедуры выделения контуров объекта.

Процедура выделения краев объектов занимает центральное место при предварительной обработке изображений, представляя собой начальный этап реализации многочисленных алгоритмов классификации объектов. Большинство применяемых методов выделения краев основываются на вычислении градиента, т.к. при переходе от более светлой области к более темной происходит скачок первой производной функции яркости. Описание подобных методов приводится в работах [30,34-36]. В некоторых трудах [30,37,38] предлагается применение второй производной для определения внутренней или внешней области объекта.

Одним из широко применяемых методов выделения стандартных примитивов на изображениях сложных сцен является преобразование Хау (НТ) [39]. Методика НТ распространена весьма широко. Классическая схема применения НТ основывается на возможности аналитического описания некоторых примитивов (прямые, эллипсы и т.д.). Для этого задается аналитически множество возможных прямых на плоскости, а затем ищется отображение плоскости изображения в пространство преобразования Хау. Пример применения НТ для выделения краев объекта приведен на рис 2.

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

Данный контур получен с помощью пересечения множества прямых в точках локальных максимумов пространства НТ. Более подробно данное преобразование рассмотрено в разделе 1.6. главы 1.

Следует отметить, что в случае невозможности получения аналитических выражений для распознаваемых примитивов применяются методики, развивающие идею классического - обобщенное преобразование Хау [40,41]. В диссертационной работе предлагается применение преобразования Хау для оценки характеристик движения и его обобщение на основе теоретико-множественного метода для классификации изображений.

Еще один способ выделения краев объектов базируется на построении математических моделей областей перехода между различными уровнями яркости изображения, что позволяет найти оптимальное решение задачи выделения края. Подробнее данный метод описан в работах [42,43].

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

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

Анализ методов сглаживания контурных изображений [44-47] позволяет выделить их основные особенности, которые связаны с выбором

1) критерия гладкости контура;

2) меры близости исходного контура к соответствующему ему сглаженному контуру.

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

Для замкнутых контуров применяется семейство методов, основанных на связанном представлении отдельных элементов контура, называемых цепными кодами [41]. Преимуществом данного класса методов является простота реализации с помощью элементарных операций процессора.

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

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

Минимальный набор признаков, наилучшим образом характеризующий объект и его положение в пространстве, будем называть ключевыми признаками распознаваемых объектов [48]. Например, в известной системе HYPER [49] в качестве ключевых признаков использовались отрезки прямых линий, классифицируемые по длине.

Аналогичный подход был использован и при распознавании с помощью структурных моделей, когда изображение описывалось с помощью некоторого количества примитивов [50].

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

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

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

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

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

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

• Быстрота представления данного математического представления.

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

• Устойчивость изображения к помехам и шуму.

• Адекватность представления.

• Простота сравнения математических представлений.

• Инвариантность модели относительно сдвигов, поворотов, масштабирования.

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

В [50] модели для распознавания представляются с помощью уравнений, а затем используется метод поиска по двоичному дереву для установления соответствия между изображением и образцом.

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

В последнее время значительное внимание уделяется структурному анализу пространственных объектов [4,27,52] и т.д. Данный подход основывается на определении некоторых основных частей анализируемого объекта, обладающих легко выделяемыми особенностями. К числу таких особенностей или признаков относят контуры составных частей объекта, дифференциальные характеристики указанных частей и т.д. В дальнейшем на основании топологических понятий решается задача построения некоторого графа, характеризующего смежность элементов объекта (или некоторые другие виды отношений между элементами).

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

Для классификации и распознавания трехмерных контуров можно использовать различного рода меры близости [44,45]. Наиболее распространенной является мера близости, основанная на евклидовой метрике имеет вид где Ь,А - анализируемый и эталонный контуры.

Задача выбора параметров в правой части последнего равенства трудоемка и сложна, поэтому в ряде специальных случаев [44,532

55] ее решают косвенным путем или используют другой подход [38,45,56,57], основанный на выборе полной и неизбыточной системы инвариантов трехмерных контуров относительно указанных аффинных преобразований координат. Кроме того, часто пользуются дискретным аналогом евклидовой меры близости, аппроксимируя интегральное выражение конечной суммой [44]:

2я7

ЛГ-1

Ь, Л) = шт У я,» ¿Го р

-Яг

2/п р

-V N

Однако при анализе изображений трехмерных объектов следует учитывать неопределенность, неточность и неполноту информации, что может быть обусловлено частичным перекрытием объектов в области сцены, подробностью описания эталонных и наблюдаемых объектов, качеством анализируемых изображений и пр. Как показал опыт разработки интеллектуальных систем, в данной ситуации плохо работают модели, основанные на теории вероятностей, и возникает необходимость разработки других моделей, в большинстве случаев основанных на теории нечетких множеств [58], теории возможностей [59], теории Демпстера-Шейфера [60,61].

Опыт разработки распознающих систем, обобщенный в [28,52,61] показывает, что задача классификации плоских зашумленных изображений трехмерных динамических объектов связана с рассмотрением следующих важных проблем:

• выбором преобразования полутоновых изображений в представление, инвариантное относительно степени освещенности сцены, окраски поверхностей объектов и пр.[62];

• выбором модели трехмерного объекта, позволяющей искусственно генерировать плоские изображения объектов из заданного класса в зависимости от положения точки наблюдения [30];

• выбором меры близости между изображениями, позволяющей решить задачу классификации исследуемого изображения на основе сравнения его с эталонами [63];

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

Рис. 3. Структура системы классификации изображений

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

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

Основными задачами исследования, определяемые поставленной целью, являются:

- разработка эффективных методов сглаживания и аппроксимации полутоновых изображений;

- разработка алгоритмов выделения контуров объекта;

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

- разработка и исследование методов обработки контурных изображений объекта и выделения их информативных признаков;

- построение метода классификации и алгоритма распознавания плоских проекций трехмерных объектов.

Методы исследования основываются на использовании аппарата

- теории вероятностей;

- математической статистики;

- методов оптимизации;

- теории графов;

- теории возможностей;

- теории распознавания образов.

Материалы диссертационной работы распределены по главам в соответствии с перечисленными задачами.

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

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

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

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

В диссертационной работе получены следующие новые научные результаты:

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

• разработан и исследован локальный метод выделения краев, основанный на использовании дискриминантных функций;

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

• разработан и апробирован метод определения ориентации объекта в пространстве, основанный на построении оператора проектирования по информативным признакам;

• разработан теоретико-множественный метод классификации контурных изображений объектов, основанный на мерах включения нечетких множеств.

По теме диссертационной работы опубликовано 8 печатных работ, кроме того, практические и теоретические результаты работы отражены в четырех отчетах по научно-исследовательской работе «Разработка методов распознавания изображений ограниченного класса сцен для задачи «Автопоиск».

Основные результаты работы докладывались и обсуждались на:

- Всероссийской научно-технической конференции «Интеллектуальные САПР» с участием зарубежных представителей (г. Геленджик, 1998);

- Всесоюзной научно-технической конференции с международным участием SCM-98 (г. Санкт-Петербург, 1998);

- научно-технической конференции «Интеллектуальные САПР-97» (г. Таганрог, 1998);

- научно-технической конференции «ИМС-99» (г. Таганрог, 1999);

- Conference «Proc. of the Fourth European Congress on Intelligent Techniques and Soft Computing» (Germany, Aachen, 1999);

- научно-технических конференциях профессорско- преподавательского состава ТРТУ (1998-2000).

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

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

Для оценки теоретических результатов, полученных в данной диссертационной работе, был создан пакет прикладных программ в среде MathCad 7.0. В качестве исходного материала были использованы полутоновые изображения сцен, полученные путем дискретизации кадров видеозаписи. Предполагается, что исходное изображение квантуется по уровню на 256 значений. Размеры обрабатываемого изображения варьируются по ширине до 400 точек, по высоте - до 300 точек. Изображения являются динамическими, т.е. объекты перемещаются относительно неподвижного фона при смене последовательности кадров. Пример трех последовательных полутоновых изображений из серии кадров, на которых можно заметить перемещение целеподобных объектов, приведен на рис 4.1.

-л 4. Л ш

Рис.4.1. Серия последовательных кадров

4.2. Общий алгоритм решения задачи обработки и классификации графической информации

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

1. Построение математической модели класса распознаваемых объектов.

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

3. Разработка мер, позволяющих оценивать степень близости распознаваемого и эталонного изображений.

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

Математические модели объектов по способу представления можно разделить на два основных класса - дискретные (в виде конечных множеств образующих элементов) и аналитические (в вйде различных видов параметризованных функций). Логично также провести разделение для методов построения плоских и пространственных моделей. В результате экспериментов удалось установить, что оптимальным с точки зрения универсальности является использование плоских проекций трехмерных моделей, т.к. такие модели позволяют решать широкий класс задач классификации различных типов изображений объектов. В литературе [106-108] указывается, что при распознавании сложных изображений человек использует информацию как о контурах изображений, так и о структуре окраски объекта. Поэтому трехмерные модели следует разделить по виду базовых признаков объектов на модели контурных изображений и на модели полутоновых (раскрашенных) изображений проекций объектов. На рис 4.2. приводится общая схема возможных решений подзадачи построения математической модели объектов.

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

В случае малой площади изображения объекта (<5%) поиск признаков объекта на всей площади изображения может приводить к значительным затратам времени. Для большинства реальных задач это является недопустимым [109]. Поэтому возникает задача выделения объектов из общего изображения сцены по различным признакам, например, по значениям функции яркости или по скорости движения. После этапа отделения объектов от общего фона анализируемые изображения представляют собой прямоугольники минимальной площади, внутри которых заключен исследуемый объект.

Бинарное Полутоновое изображение изображение

Рис.4.2. Построение математических моделей объектов

Следующей задачей является поиск информативных признаков изображений объектов. Для полутоновых изображений такие признаки можно получить с помощью выделения связных областей (раскраски) или получения контурных изображений объекта. Т.к. в результате дискретизации края объектов являются размытыми, то представляется необходимым последующий этап улучшения полученного контурного изображения. В дальнейшем полученные контурные бинарные изображения можно использовать непосредственно для распознавания по аналитическим моделям, не требующим связности контуров. Однако в случае высоких требований к быстродействию системы распознавания более эффективным может оказаться векторное представление контура изображения, строящееся на основании выбора системы «контрольных» точек контура [110].

Общий алгоритм предварительной обработки изображений приведен на рис. 4.3. - 4.5.

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

Полутоновое изображение сцены

Полутоновое изображение отдельного объекта

Рис.4.3. Предварительная обработка изображения и выделение объектов сцены

Улучшенное полутоновое изображение объекта объекта Векторное представление изображения объекта

Рис.4.4, Формирование различных представлений объектов

Раскрашенное Бинарное полутоновое изображение изображение контуров объекта объекта

Векторное представление изображения объекта О

Построение полигонального представления исходного изображения

Удаление неинформативных точек

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

Утоньшение контуров изображения объекта

1 г

Восстановление положения объекта в пространстве по контрольным точкам

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

Рис.4.5, Завершающий этап предварительной обработки изображения

Рис. 4.7. Общая схема системы классификации изображений

4.3. Алгоритмическое обеспечение интеллектуальной системы обработки изображений

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

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

На втором этапе выделения участников сцены для выделения движущихся объектов формируется и анализируется кадр разности (см. раздел 1.6), получаемый с помощью поточечного вычитания двух последовательных по времени кадров. Производится сглаживание полученного полутонового кадра разности и выделение областей сцены, подверженных перемещению. Затем производится отбор только тех областей, которые с наибольшей вероятностью принадлежат целеподобным объектам. Теоретическое обоснование данного этапа приведено в разделе 1.5. главы 1.

На третьем этапе отделения объектов от фона производится анализ полученных параметров движения: направления и относительной скорости перемещения объекта от кадра к кадру. На основании данного анализа производится отбор наиболее важных целеподобных объектов, например тех, которые движутся с очень высокой скоростью или в направлении наблюдателя (см. раздел 1.6. главы 1). На данном этапе возможно параллельное проведение процедуры восстановления первичного полутонового изображения. В результате данной процедуры повышается контрастность исходного изображения и устраняется нечеткость и размытость границ. Подробно данная процедура описана в подразделе 1.4.3. главы 1.

На четвертом этапе выделения информативных признаков изображения объекта производится выделение границ объекта и построение его связного контурного изображения. Оптимальные методы выделения краев основываются на использовании математических моделей областей перехода между различными уровнями яркости изображения, что позволяет найти оптимальное решение задачи выделения края. В данной работе предлагается использовать статистическую модель края на базе идеологии дискриминантных функций. Ее преимущество перед известными в литературе моделями, заключается в оптимальном выделении краев произвольной формы для зашумленных полутоновых изображений. Локальный метод выделения краев описан в разделе 1.4 главы 1. Для получения связных контуров предлагается использовать метод, основанный на построении графовой модели полученного изображения. Подробное описание алгоритма приведено в разделе 2.2 главы 2.

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

Полутоновое изображение сцены

Изображение, в готовом для классификации виде

Полутоновое изображение сцены

Изображение, в готовом для классификации виде

4.4. Практические результаты, полученные с помощью .

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

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

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

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

ВАЗ-2110

ВАЗ-2106

ВАЗ-2111

ПАЗ-3205

УАЗ-ЗЗОЗ

УАЗ-31512

Рис. 4.11. Эталонные модели базы данных

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

4. разработан и апробирован метод определения ориентации объекта в пространстве, основанный на построении оператора проектирования по информативным признакам;

139

5. разработан теоретико-множественный метод классификации контурных изображений объектов, основанный на мерах включения нечетких множеств.

1. Эйрес Р., Миллер С. Перспективы развития робототехники: Пер. с англ. М.: Мир, 1986. - 280 с.

2. Распознавание образов: состояние и перспективы: Пер. с англ./К. Вер-хаген, Р. Дёйн, Ф. Грун и др. -М.: Радио и связь, 1985. 104 с.

3. Техническое зрение роботов: Пер. с англ./Под ред. Г.П. Катаев М.: Машиностроение, 1987. - 320 с.

4. Катыс Г.П. Обработка визуальной информации. М.: Машиностроение 1988-320 с.

5. Василенко Г.И., Тараторин A.M. Восстановление изображений. М.: Радио и связь, 1986. - 304 с.

6. Horn В.К.Р. Extended Gaussian images, Proc. IEEE, vol.72, pp. 1656-1678, Dec. 1984.

7. Horn B.K.P., Ikechi K., The mechanical manipulation of randomly oriented parts, Science America, vol.251, no.2, pp. 100-111, Aug.24-28, 1984.

8. Ikechi K., Recognition of 3D objects using the extended Gaussian images, in Proc. 7th Int. Joint Conf. Artificial Intelligence, Vancouver, B.C., Canada, Aug. 24-28, 1981, pp.595-600.

9. Grimson W.E.L., Lozano-Perez T. Model-based recognition and localization from sparse range or tactile data, Int. J. Robotics Res., vol.3, no.3, pp.335, Feb. 1984.

10. Grimson W.E.L., Lozano-Perez T. Localization overlapping parts by searching the interpretation tree, IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-9, no.4, July 1987.

11. Ikechi K. Precompiling a geometrical model into an inerpretation tree for object recognition in bin-picking tasks, Proc. DARPA Image Understanding Workshop, pp. 321-339, Feb. 1987.

12. M.Oshima M., Shirai Y. Object recognition using three-dimensional information, IEEE Trans. Pattern Anal. Machine Intell., vol.3, no.4, pp. 353-361, July 1983.

13. Nevatia R., Binford Т.О. Description and recognition of complex-curved objects, Artificial Intell., vol.8, pp. 77-98, 1977.

14. Broocs R.A. Symbolic reasoning among 3-D models and 2-D images, Artificial Intell., vol.17, pp. 285-348, 1981.

15. Broocs R.A. Model-based three-dimensional interpretations of two-dimensional images, IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-5, no.2, pp. 140-150, Mar. 1983.

16. Fan N.J., Medioni G., Nevatia R. Recognizing 3-D objects using surface descriptions, IEEE Trans. Pattern Anal. Machine Intell., vol.11, no.ll, pp. 1140-1157, Nov. 1989.

17. Besl P.J., Jain R.C. Segmentation through variable-order surface fitting, IEEE Trans. Pattern Anal. Machine Intell., vol.10, no.2, pp. 167-192, Mar. 1988.

18. Brady M., Ponce J., Yuille A., Asada H. Describing surfaces, In H.Hanafusa and H.Inoue, editors, Proc. 2nd Int. Symp. Robotics Research, H.Hanafusa and H.Inoue, Eds. Cambridge, MA: M.I.T.Press, 1985.

19. Гренандер У. Лекции по теории образов. Т.2. Анализ образов: Пер. с англ. -М.: Мир, 1981. -448с.

20. Chaudhuri В.В. A Note on East Algogithms for Spatial Domain Techniques in Image Processing IEEE Trans. System, Man, Cybern., SMC-13, no.6, pp. 1166-1169,1983.

21. Huang T.S., Yang G.T., Tang G.Y. A Fast Two-Dimensional Median Filtering Algorithms, IEEE Trans. Pattern Anal. Machine Intell., vol. ASSP -27,pp. 13-18, 1979.

22. Wolfe G.J., Mannos J.L. Fast Médian Filter Implementation, Proc. Soc. Photo-Optical Inst. Engr., 207, pp. 154-160, 1979.

23. Ахмед H., Pao K.P. Ортогональные преобразования при обработке цифровых сигналов: Пер. с англ. М.: Связь, 1980. - 248 с.

24. Прэтт У. Цифровая обработка изображений. Пер. с англ. М.: Мир, 1982.-Кн. 1.-312 с.

25. Харалик Р. Структурное распознавание образов, гомоморфизмы и размещения. Кибернетический сборник. Новая серия: Пер. с. англ. - М.: Мир, 1983, вып. 19, с. 170-199.

26. Промежуточный отчет о научно-исследовательской работе «Разработка методов распознавания изображений ограниченного класса сцен для задачи «Автопоиск». Таганрог, 1998. - 138 с.

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

28. Павлидис Т. Алгоритмы машинной графики и обработки изображений.- М.: Радио и связь, 1986 357 с.

29. Бутенков С.А. Об одной теоретико-графовой модели для анализа бинарных изображений. Сборник трудов Всероссийской научно-технической конференции с международным участием. Таганрог, 1998.-с. 38-43.

30. Семерий О. Метод максимальных площадей для выделения движущихся объектов по серии изображений. Сборник трудов Всероссийской научно-технической конференции с международным участием. Таганрог, 1998.-с. 26-31.

31. Гузман A. Décomposition of a visual scene into bodies/nep. с англ. -Сборник трудов «Интегральные работы», вып.1, М.: Мир, 1973. -с.291-304.

32. Roberts L.G. Machine perception of three-dimensional solids/Пер. с англ. -Сборник трудов «Интегральные работы», вып.1, М.: Мир, 1973. -с. 162-208.

33. Forsen G.E. Processing visual data with an automaton еуе/Пер. с англ. -Сборник трудов «Кибернетические проблемы бионики», М.: Мир, 1972. -с.317-343.

34. Kenal L., Rendal N., ed. Recantation system design by statistical analysis. Proc. ASM National Conference, no.2, pp. 166-169, 1971.

35. Дуда P., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976. -с.33

36. Hough P. Methods and Means for Recognizing Complex Patterns, U. S. Patents 3069654, 1962.

37. Liu D., Yamashita Y., Ogawa H. Pattern Recognition in the Presence of Noise //Pattern Recognition, vol.28, N 7, pp.989-995, 1995.

38. Freeman H. Computer processing of line drawing images// Comput. Surveys 6,pp.57-98, 1974.

39. Lee D. Coping with Discontinuities in Computer Vision : Their Detection, Classification and Measurement and// IEEE Trans. On Pattern Analysis Machine Intelligence, vol. 12, N 4, 1990, p.321-344.

40. Анисимов Б.В., Курганов В.Д., Злобин B.K. Распознавание и цифровая обработка изображений. М.: Радио и связь, 1986. - с. 44.

41. Cohen S.C., Wang J.V. Modeling Image Curves Using Invariant 3-D Object Curve Models- A Path to 3-D Recognition and Shape Estimation from Image Contours. Part 1 // IEEE Trans. On Pattern Analysis Machine Intelligence, vol. 16, N 1, 1994, p.1-12.

42. Cohen S.C., Wang J.V. 3-D Object Recognition and Shape Estimation from Image Contours Using B-Splines , Shape Invariant Matching and Neural Network. Part 2// IEEE Trans. On Pattern Analysis Machine Intelligence, vol. 16, N 1, 1990, p.13-23.

43. Pikaz A., Dinstein I. Using Simple Decomposition for Smoothing and Feature Point Detection of Noisy Digital Curves// IEEE Trans. On Pattern Analysis Machine Intelligence, vol. 16, N 8, 1994, p.808-813.

44. Yu D., Yan H. An Efficient Algorithm for Smoothing, Linearization and Detection of Structural Feature Points of Binary Image Contours// Pattern Recognition, vol.30,N1, p.57-69.

45. Thomas E. D., Atam P. D. Chord-Tangent transformation for object recognition// Pa. Rec., Vol. 28, No 9, pp.1321-1332, 1995.

46. Fefche N., Faugeras O.D. Hyper a new approach for the recognition and positioning of two-dimensional objects// IEEE Trans. Pattern Anal. Mach. Intel. 8, pp.44-54, 1986.

47. Shapiro L.G. A structural model of shape// IEEE Trans. Pattern Anal. Mach Intel. 2, pp.111-126, 1980.

48. Васильев В.И. Распознающие системы. Справочник. Киев: Наукова думка, 1983.-418 с.

49. Cohen F.S., Huang Z. Affine-invariant moments and B-splines for object recognition from image curves// Proc. 93 SPIE Conf. Applications jf Artificial Intelligence XI: Machine Vision and Robotics Orlando. FL., April, pp. 12-16, 1993.

50. Cohen F.S., Patel M. Modeling and synthesis of images of 3D textured surfaces // Computer Vision, Graphics and Image Processing,vol. 53, N 6, pp.501-506, 1991.

51. Lin C.-S. and Jungthiapanich C. Invariants of three dimensional contours// Pattern recognition, vol.23, N 8, pp.833-842, 1990.

52. Hu M.R. Visual pattern recognition by moments invariants // IRE Trans. Inform. Theory, N 8, pp. 179-187, 1962.

53. Нечеткие множества в моделях управления и искусственного интеллек-та./Под ред. Д.А. Поспелова. М.: Мир, 1986.

54. Дюбуа Д., Прад А. Теория возможностей. Приложения к представлению знаний в информатике. М.: Радио и связь, 1990.

55. Dempster А.Р. Upper and lower probabilities induced by a multivalued mapping. Ann. Math. Statist., 1967, vol. 38, pp.325-356.

56. Shaffer G. A. Mathematical Theory of evidence. Princeton University Press, Princeton, N.J., 1976.

57. Отчет о научно-исследовательской работе « Разработка методов распознавания изображений изображений ограниченного класса сцен для задачи «Автопоиск»». Таганрог, 1999. - 70 с.

58. Зрительные системы. Материалы Всесоюзного симпозиума «Зрение организмов и роботов». Вильнюс, 1987. - 270 с.

59. Быстрые алгоритмы в цифровой обработке изображений: Пер. с англ./Под ред. Т. Хуанга. М.: Радио и связь 1984. 221 с.

60. Ковалевский В.А. Методы оптимальных решений в распознавании изображений. М.: «Наука», 1976. - 328 с.

61. Красильников Н.Н. Теория передачи и восприятия изображений. М.: Радио и связь, 1986. - 248 с.

62. Petrou М., Kittler J. Optimal Edge Detectors for Ramp Edges// IEEE Trans. On Pattern Analysis Machine Intelligence, vol. 13, N 5, 1991, p.483-491.

63. Пискунов H.C. Дифференциальное и интегральное исчисления. Учебник для ВТУЗов. Том 1.-М.: «Наука», 1972. с. 247

64. Оптико-структурный машинный анализ изображения/Под ред. К.А. Яновского. М.: Машиностроение, 1984. 280 с.

65. Nagao М., Matsuyama Т. Edge preserving smoothing, Proc. Fourth Intern. Joint Conf. Jn Pattern Recognition, Nov., 1978, pp.518-520.

66. Abramatic J.F., Silverman L.M. Non-Stationary Linear Restoration of Noisy Images, Proc. 18 IEEE Decision and Control Conference, vol.l Dec. 1979, pp.92-99.

67. Бутаков E.A. и др. Обработка изображений на ЭВМ.- М.: Радио и связь, 1987.-с.24

68. Gheen G. Distortion invariant Volterra filters, Pattern Recognition, 27, N4,1994, pp.569-576.

69. Spacek L.A. Edge Detection and Motion Detection// Image Vision Comput., vol.4,1986, p.49-52.

70. Canny J.A. Computational approach to edge detection// IEEE Trans. On Pattern Analysis Machine Intelligence, vol. PAMI-8, N 11, 1986, p.679-691.

71. Броневич А.Г., Зюзерова H.C., Каркищенко A.H. Вариационный подход к сглаживанию и определению характерных точек черно-белого изображения. Материалы конференции «Интеллектуальные САПР-97», том 2 Таганрог, 1998. - с.117-121.

72. Hecker Y.C., Bolle R.M. On geometric hashing and the generalizen Hough transform// IEEE Transactions on Systems, Man, and Cybernetics, vol 24, №9, 1994.

73. Эндрюс Г. Применение вычислительных машин для обработки изображений: Пер. с англ. М.: Мир, 1978. - с.53.

74. Bryant A., Bryant J. Following Boundaries of Discrete Binary Objects in Space// Pattern Recognition, vol. 23, N 6, 1990, p.547-552.

75. David L. Coping with Discontinuities in Computer Vision: Their Detection, Classification, and Measurement// IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, №5, 1991.

76. Pikaz A., Dinstein I. Using Simple Decomposition for Smoothing and Feature Point Detection of Noisy Digital Curves// IEEE Trans. On Pattern Analysis Machine Intelligence, vol. 16, N 8, 1994, p.808-813.

77. Donggang Y., Hong Y., An efficient algorithm for smoothing, linearization and detection of structural feature points of binary image contours// Pattern Recognition, 30, №1,1997, pp. 57-69.

78. Броневич А.Г., Зюзерова H.C. Модели теории графов для выделения контуров по градиентному изображению. Сборник трудов «Интеллектуальные САПР-97», №2, Таганрог, 1998. - с. 103-106.

79. Фишер Р. От поверхностей к объектам. Машинное зрение и анализ трёхмерных сцен: Пер с англ. М.: Радио и связь, 1993. - 88 с.

80. Шлезингер М.И. Математические средства обработки изображений. -Киев: Наукова думка, 1989. с.11287.0ре О. Теория графов\Пер. с англ. М.: «Наука», 1980. - 336 с.

81. Кристофидес Н. Теория графов. Алгоритмический подход\Пер. с англ. М.: «Мир», 1978. - 432 с.

82. Андонова Н.С., Броневич А.Г., Каркищенко А.Н. Градиентные методы предварительной обработки изображений при нечетких ограничениях. Сборник трудов научно-технической конференции «ИМС-99». -Таганрог, 1999. с. 46-51.

83. Кульбак С. Теория информации и статистика: Пер. с англ. М.: «Наука», 1967.-408 с.

84. Лепский А.Е. Оценка числовых характеристик случайного веса в одномерной модели зашумления контура плоского изображения. . «Интел. САПР-98», Таганрог: ТРТУД999.

85. Горелик A.JI. и др. Современное состояние проблемы распознавания: некоторые аспекты. М.: Радио и связь, 1986. - с.56.

86. Данилов А.А. Сенсорные устройства автоматов контроля и сборки. -М.: Машиностроение, 1984. с. 113-125.

87. Hall E.L., Tio J.V.K., McPherson С.А. and Sadjadi F.A. Measuring curved surfaces for robot vision// Computer, vol.15, pp.42-54, 1982.

88. Jarvis R.A. A laser time of flight range scanner for robotic vision// IEEE Trans. Pattern Analysis and Machine Intellig . PAMI-5, p.505-512, 1987.

89. Lin C.-S. and Jungthiapanich C. Invariants of three dimensional contours// Pattern recognition, vol.23, N 8, pp.833-842, 1990.

90. Sadjadi F.A., Hall E.I. Three dimension moments invariants // IEE Trans. Pattern Analysis and Machine Intelligence, PAMI-2, pp. 127-136,1980.

91. Richard C.W., Hemani Jr., Hemeni H. Identification of 3-dimensonal objects using Fourier descriptors of the boundary curve// IEEE Trans. Syst. Man Cybern. SMC-4, pp.371-378, 1974.

92. Kuhi E.P. Giardina C.R. Elliptic Fourier features of a closed contour// Computer Graphics Image Process, N 18, pp. 236-258, 1982.

93. Nishida H. A Structural Approach to Representation of Curved Objects, in Pattern Recognition, Vol. 30, No. 1, pp. 45-56.

94. Ponce J., Hoogs A. and Kriegman D.J. On Using CAD Models to Compute the Pose of Curved 3-D objects, CVGIP: Image Understanding 55, 1992. pp. 184-197.

95. Ting-Jun Fan, Medioni G., Nevada R. Recognizing 3-D Using Surface Descriptions, IEEE Trans. Pat. Anal and MI, Vol. 11, No. 11, pp. 1140-1157.

96. Зюзерова H.C. Анализ формы трехмерных объектов по их плоским проекциям с помощью обобщения преобразования Хау. Материалы ВНК студентов и аспирантов, Таганрог, 1997. -с. 143-144.149

97. Робототехника и гибкие автоматизированные производства. В 9-ти кн. Кн. 6. Техническая имитация интеллекта: Учеб. пособие для втузов / В.М. Назаретов, Д.П. Ким; Под ред. И.М. Макарова. М.: Высш. шк., 1986.- 144 с.

98. Василенко Г.И. Голографическое опознавание образов. М.: Сов. радио, 1977.-328 с.

99. Хант Э. Искусственный интеллект: Пер. с англ. М.: «Мир», 1978. -559 с.

100. Тимохин В.И. Применение ЭВМ для решения задач распознавания образов: Учеб. пособие. JL: Изд.-во Ленинградского ун-та, 1983. - 216 с.

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

102. Вызов исходных данных: 112 базовый контур, МЫд - исходное полутоновое изображение

103. Мсо1 раскрашенное сегментированное изображение, Мсоп - контурное изображениеи2 := ЯЕДОРЯМ ( "1:\аи1о2акЬУг«а31>\еопГ )1.2 := ЯЕАОВМР ( "I:\autozakh\images2\Carl05basecon.bmp" )

104. Мсо1 := Р.ЕАОВМР ( "I:\autozakh\images2\Carl05col.bmp" ) Мсоп := ВЕАОВМР ( "I:\autozakh\images2\Carl05con.bmp"

105. МЫд := ЯЕАОВМР ("I:\autozakh\images2\Carl05big.bmp" )яннянняинняннк?раскра шенное сегментированное изображениеконтурное изображение

106. V := Апс1соп( 112 , 7, 8) 27131

107. V<— findpoint ( V, M , U ) ¡<-¡1-1 K<-V„voviwhilei = 0) + x.*x.i i-i1. Y,*Yi i1. V<- findpoint (V,M, Ui«-i + i y¡«—v,1. U <—0 V0'V.Xborderi 0. rows( x) 12001. У.0 200 400 600 800200 400 600 800

108. Изменение координат точек контура вдоль направления х.

109. Изменение координат точек контура вдоль направления у.

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

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

112. Функция дгай находит направление градиента, при этом минимизируется функционал, доставляющий наименьшую длину полигонального представления контура.grad (х, N ) := for i 6 1. N 11. Gr x +x 2-х1.i+l i-l i1. Gr0^XN+Xl ' 2'X01. N N 1 о N1. Gr

113. Процедура condgrad осуществляет коррекцию градиента с учетом накладываемых граничных условий.condgrad ( Gr, х, border , N ) :=for i е 0. N

114. Gr <— 0 if ; Gr.> 0 ■ x.= border i i i 1,1

115. Gr.<— 0 if ; Gr.< 0 • x= border.оcond ( х, border , N )for i € 0. Nх <— border if x.> border. i i,i i 1,1x.<—border. if x.< border.1.1,0 I 1,0

116. Входные параметры: массив х должен содержать х или у координаты контура; массив border определяет граничные условия для сглаживания; N длина массивах, число Num задает число итераций.

117. Выходные параметры: х координаты х или у уже сглаженного контура; массивы nrm и ALF позволяют судить о скорости сходимости итерационного процесса.main ( х, border , N , Num ) :=for k e 0. Num Gr«— grad ( x, N )

118. Gr<—condgrad ( Gr,x, border , N ) nrm norm( Gr, N )1. N 1

119. A<— У ; Gr Gr 2 + ; Gr - GrA 2 i +- l iNi = 0 N ISi = 0-B- Gr • x. x. + Gr - Gr - : x 1 i