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

• Автор: Нефёдов, Алексей Валентинович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 132 с. : ил.

ГЛАВА 1. Алгоритмы вычисления оценок

1Л. Определение модели ABO

1.2. Обзор эффективных формул для модели АВО

1.2.1. Системы опорных множеств комбинаторного типа

1.2.2. Системы опорных мйожеств, являющиеся интервалами булева куба

1.2.3. Симметрические функции близости

1.2.4. Ранги систем опорных множеств

1.2.5. Абсолютно симметрические системы опорных множеств

1.2.6. Атомарные системы опорных множеств

1.3. Общая характеристика результатов исследований модели АВО

ГЛАВА 2. Алгоритмы вычисления оценок с двухмерными опорными множествами

2.1. Определение модели ДАВО
2.2. Специфика задачи распознавания изображений
2.3. Эффективные алгоритмы ДАВО с прямоугольными опорными множествами
2.4. Эффективные алгоритмы ДАВО с опорными множествами, являющимися композицией прямоугольников
2.5. Эффективные алгоритмы ДАВО с прямоугольными опорными множествами и функциями близости, зависящими от двух опорных множеств
2.5.1. Функции близости, зависящие от двух опорных множеств
2.5.2. Эффективный способ вычисления оценок для функции близости
/ij (со ^5), 0)26*2)
2.5.3. Подстановки, обладающие a-свойством относительно системы опорных множеств
2.5.4. Эффективный способ вычисления оценок для функции близости
B2(&iSi,&2S2) и множества G, обладающего а-свойством
ГЛАВА 3. Многошаговые процедуры поиска
3.1. Задача поиска шаблона на растре. Многошаговые процедуры поиска
3.2. Эффективные двухшаговые процедуры поиска прямоугольника
3.3. Одномерная задача поиска прямоугольника. Элементарные двухшаговые процедуры поиска
3.4. Условия оптимальности процедуры Fcr для одномерной задачи поиска прямоугольника
3.5. Нижняя оценка сложности двухшаговой процедуры одномерного поиска прямоугольника
ГЛАВА 4. Вычислительные эксперименты
4.1. Предварительные замечания
4.2. Модельные задачи
4.3. Гематологическая задача
Заключение
Список литературы

Задача распознавания (классификации) образов заключается в отнесении объекта к тому или иному классу объектов на основе прецедентной информации, заданной совокупностью объектов с известной классификацией. Объекты представлены своими признаковыми описаниями - как правило, векторами или матрицами чисел; природа объектов может быть самой разной (предмет, состояние, ситуация, процесс и т.д.). Характерной чертой задачи распознавания образов является то, что решение о классификации объекта необходимо принять на основе неформализованной, неполной, косвенной, разнородной, иногда противоречивой информации.
Можно утверждать, что с задачами распознавания образов человек сталкивался с древнейших времен, начиная с первых шагов своего развития. Сегодня, в эпоху информационных технологий, задачи распознавания образов возникают и успешно решаются в самых различных областях человеческой деятельности - в медицине, экологии, социологии, геологии, в технике и на производстве, в военных разработках, криминалистике, управлении, и т.д. Начиная с первой половины прошлого века - времени зарождения математической теории распознавания образов, - создано и исследовано большое количество разнообразных методов и подходов к решению этих задач.
В целом, можно выделить пять основных типов алгоритмов распознавания образов [17]:
1) алгоритмы, основанные на принципе разделения [37, 30],
2) статистические алгоритмы [37, 3],
3) алгоритмы, основанные на принципе потенциалов [1],
4) алгоритмы, основанные на исчислении высказываний [5],
5) алгоритмы, основанные на вычислении оценок [19, 22].
Алгоритмы первого типа основаны на построении в признаковом пространстве, соответствующем числовым описаниям объектов, гиперплоскости (или более сложной поверхности), разделяющей объекты

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