Содержание к диссертации
Введение
ГЛАВА 1. Алгоритмы вычисления оценок 14
1.1. Определение модели АВО 14
1.2. Обзор эффективных формул для модели АВО 20
1.2.1. Системы опорных множеств комбинаторного типа 22
1.2.2. Системы опорных множеств, являющиеся интервалами булева куба .24
1.2.3. Симметрические функции близости 30
1.2.4. Ранги систем опорных множеств 34
1.2.5. Абсолютно симметрические системы опорных множеств 39
1.2.6. Атомарные системы опорных множеств 42
1.3. Общая характеристика результатов исследований модели АВО 46
ГЛАВА 2. Алгоритмы вычисления оценок с двухмерными опорными множествами 49
2.1. Определение модели ДАВО 49
2.2. Специфика задачи распознавания изображений 50
2.3. Эффективные алгоритмы ДАВО с прямоугольными опорными множествами 52
2.4. Эффективные алгоритмы ДАВО с опорными множествами, являющимися композицией прямоугольников 60
2.5. Эффективные алгоритмы ДАВО с прямоугольными опорными множествами и функциями близости, зависящими от двух опорных множеств 63
2.5.1. Функции близости, зависящие от двух опорных множеств 63
2.5.2. Эффективный способ вычисления оценок для функции близости 65
2.5.3. Подстановки, обладающие а-свойством относительно системы опорных множеств 73
2.5.4. Эффективный способ вычисления оценок для функции близости и множества G, обладающего а-свойством 75
ГЛАВА 3. Многошаговые процедуры поиска 79
3.1. Задача поиска шаблона на растре. Многошаговые процедуры поиска 79
3.2. Эффективные двухшаговые процедуры поиска прямоугольника 87
3.3. Одномерная задача поиска прямоугольника. Элементарные двухшаговые процедуры поиска 96
3.4. Условия оптимальности процедуры Fcr для одномерной задачи поиска прямоугольника 103
3.5. Нижняя оценка сложности двухшаговой процедуры одномерного поиска прямоугольника 112
ГЛАВА 4. Вычислительные эксперименты 116
4.1. Предварительные замечания 116
4.2. Модельные задачи 117
4.3. Гематологическая задача 121
Заключение 126
Список литературы 127
- Системы опорных множеств, являющиеся интервалами булева куба
- Эффективные алгоритмы ДАВО с опорными множествами, являющимися композицией прямоугольников
- Одномерная задача поиска прямоугольника. Элементарные двухшаговые процедуры поиска
- Нижняя оценка сложности двухшаговой процедуры одномерного поиска прямоугольника
Введение к работе
Задача распознавания (классификации) образов заключается в отнесении объекта к тому или иному классу объектов на основе прецедентной информации, заданной совокупностью объектов с известной классификацией. Объекты представлены своими признаковыми описаниями - как правило, векторами или матрицами чисел; природа объектов может быть самой разной (предмет, состояние, ситуация, процесс и т.д.). Характерной чертой задачи распознавания образов является то, что решение о классификации объекта необходимо принять на основе неформализованной, неполной, косвенной, разнородной, иногда противоречивой информации.
Можно утверждать, что с задачами распознавания образов человек сталкивался с древнейших времен, начиная с первых шагов своего развития. Сегодня, в эпоху информационных технологий, задачи распознавания образов возникают и успешно решаются в самых различных областях человеческой деятельности - в медицине, экологии, социологии, геологии, в технике и на производстве, в военных разработках, криминалистике, управлении, и т.д. Начиная с первой половины прошлого века - времени зарождения математической теории распознавания образов, - создано и исследовано большое количество разнообразных методов и подходов к решению этих задач.
В целом, можно выделить пять основных типов алгоритмов распознавания образов [17]:
алгоритмы, основанные на принципе разделения [37, 30],
статистические алгоритмы [37, 3],
алгоритмы, основанные на принципе потенциалов [1],
алгоритмы, основанные на исчислении высказываний [5],
алгоритмы, основанные на вычислении оценок [19, 22].
Алгоритмы первого типа основаны на построении в признаковом пространстве, соответствующем числовым описаниям объектов, гиперплоскости (или более сложной поверхности), разделяющей объекты
разных классов. Эти алгоритмы различаются типами разделяющих поверхностей и методами их построения.
Статистические алгоритмы принимают решение о классификации объекта на основе тех или иных принципов математической статистики. Как правило, используется информация о вероятностных характеристиках классов, например, соответствующие функции распределения.
В алгоритмах третьего типа для определения меры сходства объектов используется функция близости, значение которой пропорционально произведению "масс" объектов (определяемых, например, соответственно степени их представительности), и обратно пропорционально расстоянию между их описаниями в признаковом пространстве.
В алгоритмах, основанных на исчислении высказываний, объекты описываются логическими переменными, а классы объектов - булевыми соотношениями между этими переменными. Классификация объекта сводится к проверке для его описания булевых условий, описывающих классы.
Для решения большого количества задач распознавания образов успешно использовалась предложенная Ю.И.Журавлёвым модель алгоритмов распознавания, основанных на вычислении оценок (модель АВО). Модель описывает вычислительную структуру алгоритма распознавания, работающего с одномерными признаковыми описаниями объектов (числовыми векторами), и параметры, которые необходимо задать для определения конкретного алгоритма в модели.
Алгоритм АВО классифицирует объект в два этапа. На первом этапе строится вектор оценок объекта по заданным классам; на втором этапе на основе этого вектора принимается решение о зачислении объекта в тот или иной класс. Обычно объект заносится в класс, по которому получена максимальная оценка. Оценка объекта по классу вычисляется на основе последовательного сравнения и вычисления меры сходства признакового описания объекта с признаковыми описаниями объектов обучающей выборки,
принадлежащих этому классу. Метод вычисления меры сходства между классифицируемым объектом и прецедентом основан на сравнении значений различных комбинаций признаков двух объектов или, другими словами, на сравнении различных фрагментов их признаковых описаний.
Модель АВО оказалась весьма полезной не только для решения прикладных задач, но также и для теории распознавания образов, где на её примере было предпринято первое глубокое исследование возможностей некорректных (эвристических) алгоритмов обработки данных.
Одной из важных задач, связанных с практическим использованием модели АВО, является задача уменьшения вычислительной сложности алгоритмов для различных типов параметров модели. Алгоритмы с практически приемлемой вычислительной сложностью строятся на основе эффективных формул вычисления оценок, моделирующих работу алгоритма -формул вычисления оценок близости распознаваемых объектов и прецедентов. Параметрами АВО, существенно влияющими на сложность формул вычисления оценок, являются система опорных множеств и вид функции близости. Система опорных множеств представляет собой набор подмножеств признаков, по которым распознающий алгоритм производит сравнение описаний объектов; функция близости определяет, будут ли сравниваемые объекты считаться "близкими" или нет. К настоящему времени довольно полно исследованы задачи, связанные с получением эффективных формул вычисления оценок для случая, когда объекты в задаче описываются векторами признаков, а опорные множества представляют части этих описаний. После построения эффективных формул вычисления оценок может быть решена задача выбора в модели алгоритма, экстремального по функционалу качества классификации [12, 11, 14, 16, 20-24, 26-36].
В большом числе задач распознавания образов исходные данные представляют собой изображения или включают их наряду с другими видами данных. Такие задачи обладают рядом существенных особенностей,
обусловленных свойствами изображения как носителя информации, и требуют для своего решения использования специальных методов и подходов, изучаемых в рамках теории обработки и анализа изображений.
Модель алгоритмов вычисления оценок по "двухмерной" информации (модель ДАВО) была определена И.Б.Гуревичем как специализация классической модели АВО для задач распознавания изображений, в которых исходным описанием объекта распознавания - изображения - является числовая матрица (матрица пикселов изображения) [7]. Несмотря на то, что эффективные формулы построены почти для всех интересных на практике моделей АВО, эти результаты оказываются неприменимыми для модели ДАВО. Это проиходит потому, что при распознавании изображений использование многих популярных в модели АВО видов опорных множеств оказывается в большинстве случаев лишённым смысла. Вместе с тем, в модели ДАВО с учётом специфики исходного описания изображения в задаче естественным образом возникают новые типы опорных множеств (а также и функций близости), не рассматривавшиеся ранее в исследованиях модели АВО. Этим объяснятся актуальность исследования модели ДАВО с целью построения эффективных алгоритмов с новыми типами опорных множеств и функций близости.
Исследование алгоритмов ДАВО представляет интерес также и в другом аспекте. Все используемые в настоящее время алгоритмы распознавания изображений предназначены для работы с признаковыми описаниями или моделями изображений. При этом в большинстве задач распознавания изображений выбор адекватного признакового описания или модели изображения имеет важнейшее значение для успешного решения задачи и представляет отдельную трудную проблему. В связи с этим представляет интерес исследование алгоритмов распознавания изображений, работающих, напрямую с изображениями и не использующих каких-либо производных описаний изображений. Нам известна только одна модель алгоритмов
І-
распознавания, ориентированных на прямую работу с изображениями - модель ДАВО. Алгоритмы модели ДАВО сопоставляют изображения непосредственно по их фрагментам без использования каких-либо признаков.
Настоящая диссертационная работа посвящена постановке и решению математических задач, возникающих в связи с исследованием и эффективной реализацией моделей ДАВО с системами прямоугольных опорных множеств. В работе проведен аналитический обзор и систематизация результатов, обеспечивающих построение эффективных формул для различных моделей АВО. Предложены новые методы эффективных реализаций алгоритмов ДАВО с системами прямоугольных опорных множеств и системами опорных множеств, являющихся композицией прямоугольников. Рассмотрены новые типы функций близости, ориентированные на работу с изображениями. Значение этих функций близости вычисляется на основе сравнения независимых фрагментов двух матриц. Предложены эффективные реализации алгоритмов ДАВО с системой прямоугольных опорных множеств и функциями близости нового типа.
Введено определение многошаговой процедуры поиска шаблона на растре, предназначенной для исследования сложности алгоритмов ДАВО с системами опорных множеств, порождённых шаблоном. Предложены эффективные двухшаговые процедуры поиска прямоугольника, а также метод комбинирования этих процедур для поиска шаблона, представляющего собой объединение прямоугольников. Определены классы двухшаговых процедур, в которых построенные процедуры поиска прямоугольника имеют наименьшую сложность. Получена нижняя оценка сложности двухшаговой процедуры поиска прямоугольника. Впервые при помощи алгоритмов, работающих напрямую с изображениями и не использующих в явном виде какие-либо признаки, решена практическая задача распознавания.
Полученные в диссертационной работе результаты позволяют создавать имеющие приемлемую вычислительную сложность алгоритмы распознавания
изображений, не использующие признаков и моделей изображений (традиционного типа).
Работа состоит из введения, четырёх глав, заключения и списка литературы. Определения, примеры, утверждения, леммы, теоремы, следствия, рисунки и таблицы нумеруются в пределах главы.
В первой главе описывается модель алгоритмов вычисления оценок и рассматриваются примеры наиболее распространённых видов систем опорных множеств и функций близости - основных параметров модели. Вводятся основные обозначения и понятия, используемые в исследованиях АВО. Определяется проблема построения эффективных формул вычисления оценок, т.е. формул, в которых снимается перебор всех опорных множеств, за счёт чего комбинаторная сложность вычисления оценки понижается до сложности, пропорциональной площади обучающей таблицы (т.е. числу прецедентов, умноженному на число признаков). Приводится подробный обзор основных результатов, связанных с построением эффективных формул вычисления оценок в АВО при различных способах задания систем одномерных опорных множеств.
Во второй главе описывается модель ДАВО - специализация модели АВО для случая распознавания изображений. Приводятся специфические особенности задач распознавания изображений, отличающие их от задач распознавания с начальной информацией другого типа. Описывается идея подхода к построению и оценке вычислительной сложности широкого класса алгоритмов ДАВО с опорными множествами, порождёнными произвольным шаблоном, основанного на решении задачи поиска данного шаблона на растре при помощи многошаговых процедур поиска (определение многошаговых процедур поиска даётся в третьей главе диссертации). Предлагается метод эффективной реализации алгоритмов ДАВО с системами прямоугольных опорных множеств с использованием эффективных двухшаговых процедур поиска прямоугольника. На основе комбинированного использования
эффективных двухшаговых процедур поиска прямоугольников предлагается метод эффективной реализации алгоритмов с системами опорных множеств, представляющими собой композицию прямоугольников. Для описанных методов эффективной реализации алгоритмов ДАВО даются точные оценки вычислительной сложности, показывающие, что сложность предложенных алгоритмов меньше сложности алгоритмов, основанных на поиске прямоугольника методом перебора (более подробному и полному исследованию сложности введённых двухшаговых процедур поиска прямоугольников посвящена третья глава диссертации). Вводится новый тип функции близости, зависящей от результата сопоставления разных подописаний двух объектов. Рассматриваются примеры функций близости нового типа. Предлагаются эффективные методы вычисления оценок в ДАВО для двух функций близости нового типа.
Третья глава работы посвящена определению многошаговых процедур поиска шаблона на растре и исследованию вычислительной сложности двухшаговых процедур поиска прямоугольника. На процедурах поиска основан предложенный во второй главе подход к реализации алгоритмов ДАВО с опорными множествами, порождёнными заданным шаблоном. Формулируется задача поиска шаблона на растре, вводится определение многошаговой процедуры поиска, рассматриваются её свойства. В рамках введённого формализма для описания многошаговых процедур поиска рассматриваются эффективные двухшаговые процедуры поиска прямоугольника. Определяются классы процедур, в которых построенные эффективные процедуры имеют наименьшую сложность. Приводится нижняя оценка сложности двухшаговой процедуры поиска прямоугольника.
В четвёртой главе описывается применение разработанных алгоритмов ДАВО для решения трёх задач распознавания изображений с двумя классами. Первые две задачи демонстрируют возможности алгоритмов ДАВО различать модельные текстурные изображения, образованные элементами различного
размера, структуры и локализации, и легко разделяемые человеком. Третья задача заключается в классификации изображений ядер лимфоидных клеток больных реактивным лимфаденитом и лимфосаркомой. Она демонстрирует возможности алгоритмов ДАВО различать достаточно сложные текстуры реальных изображений, классификация которых уже не является столь простым делом для человека и требует специального обучения и опыта. Основными результатами работы являются:
1. Аналитический обзор и систематизация результатов, обеспечивающих
построение эффективных формул для различных моделей АВО.
2. Метод эффективной реализации алгоритмов ДАВО с системами
прямоугольных опорных множеств, основанный на двухшаговых процедурах
поиска прямоугольника.
3. Метод эффективной реализации алгоритмов ДАВО с системами опорных
множеств, представляющих собой композицию прямоугольников, основанный
на комбинированном использовании двухшаговых процедур поиска
прямоугольников.
4. Методы эффективной реализации алгоритмов ДАВО с системами
прямоугольных опорных множеств и функциями близости, зависящими от двух
опорных множеств.
Формализм, описывающий многошаговые процедуры поиска шаблона на растре, предназначенный для исследования сложности алгоритмов ДАВО с системами опорных множеств, порождённых данным шаблоном.
Условия оптимальности эффективной двухшаговой процедуры поиска прямоугольника для одномерной задачи. Нижняя оценка сложности двухшаговых процедур поиска прямоугольника для одномерной задачи.
Возможность практического использования разработанных алгоритмов проиллюстрирована на модельных задачах и на реальной задаче классификации ядер лимфоидных клеток человека.
Результаты диссертационной работы докладывались на
5-й Международной конференции "Распознавание образов и анализ
изображений: новые информационные технологии" (2000, Самара, ИСОИ
РАН),
Всероссийской с участием стран СНГ конференции "Методы и средства
обработки сложной графической информации" (2001, Нижний Новгород,
НижГУ),
Международной конференции студентов и аспирантов по
фундаментальным наукам "Ломоносов 2001", "Ломоносов 2003" (Москва,
МГУ),
6-й Международной конференции "Распознавание образов и анализ
изображений: новые информационные технологии" (2002, Великий
Новгород, НовГУ),
the 13th Scandinavian conference on image analysis (2003, Ґетеборг, Швеция,
Halmstad University),
6-м Открытом российско-немецком семинаре "Распознавание образов и
понимание изображений" (2003, посёлок Катунь Алтайского края),
7-й Международной конференции "Распознавание образов и анализ
изображений: новые информационные технологии" (2004, Санкт-Петербург,
СПГЭУ).
Результаты работы использовались при выполнении проектов РФФИ (98-07-90180, 99-01-00470, 99-07-90411, 00-07-90004, 01-07-06035, 01-07-90016, 02-01-06479, 02-01-00182, 03-01-06294, 03-07-90406), проекта 37.011.11.0016 Федеральной целевой научно-технической программы "Исследования и разработки по приоритетным направлениям развития науки и техники" на 2002-2006 гг., проектов Программы фундаментальных исследований отделения математических наук РАН "Алгебраические и комбинаторные методы математической кибернетики" 2003-2005 гг., Комплексной программы научных исследований РАН "Математическое моделирование и интеллектуальные системы" 2001-2005 гг., проекта 03-55-1759 INTAS Young Scientist Fellowship.
По теме диссертации опубликовано 11 работ. Некоторые результаты работы включены в научные отчёты по указанным выше проектам.
В диссертационном исследовании использовались методы дискретной математики и комбинаторного анализа, теории обработки и анализа изображений. Проведены машинные эксперименты, посвященные исследованию разработанных алгоритмов ДАВО.
Системы опорных множеств, являющиеся интервалами булева куба
Для описанных методов эффективной реализации алгоритмов ДАВО даются точные оценки вычислительной сложности, показывающие, что сложность предложенных алгоритмов меньше сложности алгоритмов, основанных на поиске прямоугольника методом перебора (более подробному и полному исследованию сложности введённых двухшаговых процедур поиска прямоугольников посвящена третья глава диссертации). Вводится новый тип функции близости, зависящей от результата сопоставления разных подописаний двух объектов. Рассматриваются примеры функций близости нового типа. Предлагаются эффективные методы вычисления оценок в ДАВО для двух функций близости нового типа.
Третья глава работы посвящена определению многошаговых процедур поиска шаблона на растре и исследованию вычислительной сложности двухшаговых процедур поиска прямоугольника. На процедурах поиска основан предложенный во второй главе подход к реализации алгоритмов ДАВО с опорными множествами, порождёнными заданным шаблоном. Формулируется задача поиска шаблона на растре, вводится определение многошаговой процедуры поиска, рассматриваются её свойства. В рамках введённого формализма для описания многошаговых процедур поиска рассматриваются эффективные двухшаговые процедуры поиска прямоугольника. Определяются классы процедур, в которых построенные эффективные процедуры имеют наименьшую сложность. Приводится нижняя оценка сложности двухшаговой процедуры поиска прямоугольника.
В четвёртой главе описывается применение разработанных алгоритмов ДАВО для решения трёх задач распознавания изображений с двумя классами. Первые две задачи демонстрируют возможности алгоритмов ДАВО различать модельные текстурные изображения, образованные элементами различного размера, структуры и локализации, и легко разделяемые человеком. Третья задача заключается в классификации изображений ядер лимфоидных клеток больных реактивным лимфаденитом и лимфосаркомой. Она демонстрирует возможности алгоритмов ДАВО различать достаточно сложные текстуры реальных изображений, классификация которых уже не является столь простым делом для человека и требует специального обучения и опыта. Основными результатами работы являются: 1. Аналитический обзор и систематизация результатов, обеспечивающих построение эффективных формул для различных моделей АВО. 2. Метод эффективной реализации алгоритмов ДАВО с системами прямоугольных опорных множеств, основанный на двухшаговых процедурах поиска прямоугольника. 3. Метод эффективной реализации алгоритмов ДАВО с системами опорных множеств, представляющих собой композицию прямоугольников, основанный на комбинированном использовании двухшаговых процедур поиска прямоугольников. 4. Методы эффективной реализации алгоритмов ДАВО с системами прямоугольных опорных множеств и функциями близости, зависящими от двух опорных множеств. 5. Формализм, описывающий многошаговые процедуры поиска шаблона на растре, предназначенный для исследования сложности алгоритмов ДАВО с системами опорных множеств, порождённых данным шаблоном. 6. Условия оптимальности эффективной двухшаговой процедуры поиска прямоугольника для одномерной задачи. Нижняя оценка сложности двухшаговых процедур поиска прямоугольника для одномерной задачи. Возможность практического использования разработанных алгоритмов проиллюстрирована на модельных задачах и на реальной задаче классификации ядер лимфоидных клеток человека. Результаты диссертационной работы докладывались на 5-й Международной конференции "Распознавание образов и анализ изображений: новые информационные технологии" (2000, Самара, ИСОИ РАН), Всероссийской с участием стран СНГ конференции "Методы и средства обработки сложной графической информации" (2001, Нижний Новгород, НижГУ), Международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов 2001", "Ломоносов 2003" (Москва, МГУ), 6-й Международной конференции "Распознавание образов и анализ изображений: новые информационные технологии" (2002, Великий Новгород, НовГУ), the 13th Scandinavian conference on image analysis (2003, Ґетеборг, Швеция, Halmstad University), 6-м Открытом российско-немецком семинаре "Распознавание образов и понимание изображений" (2003, посёлок Катунь Алтайского края), 7-й Международной конференции "Распознавание образов и анализ изображений: новые информационные технологии" (2004, Санкт-Петербург, СПГЭУ). Результаты работы использовались при выполнении проектов РФФИ (98-07-90180, 99-01-00470, 99-07-90411, 00-07-90004, 01-07-06035, 01-07-90016, 02-01-06479, 02-01-00182, 03-01-06294, 03-07-90406), проекта 37.011.11.0016 Федеральной целевой научно-технической программы "Исследования и разработки по приоритетным направлениям развития науки и техники" на 2002-2006 гг., проектов Программы фундаментальных исследований отделения математических наук РАН "Алгебраические и комбинаторные методы математической кибернетики" 2003-2005 гг., Комплексной программы научных исследований РАН "Математическое моделирование и интеллектуальные системы" 2001-2005 гг., проекта 03-55-1759 INTAS Young Scientist Fellowship. По теме диссертации опубликовано 11 работ. Некоторые результаты работы включены в научные отчёты по указанным выше проектам.
В диссертационном исследовании использовались методы дискретной математики и комбинаторного анализа, теории обработки и анализа изображений. Проведены машинные эксперименты, посвященные исследованию разработанных алгоритмов ДАВО.
Эффективные алгоритмы ДАВО с опорными множествами, являющимися композицией прямоугольников
По поводу вычислительной сложности формулы (1.16) справедливо замечание, сделанное после формулировки теоремы 1.2, с той лишь поправкой, что формула (1.16) имеет место для случая объединения произвольных интервалов (не требуется ортогональности конъюнкций, соответствующих интервалам).
Общий подход к получению эффективных формул вычисления оценок основан на следующем представлении выражения (1.11) [2, 17]: где Vt(S, S ) - число опорных множеств Q из QA , содержащих признак teN и таких, что B&(S, 5") = 1. В результате такого представления задача эффективного вычисления значения выражения (1.12) заменяется задачей эффективного вычисления значения выражения Если считать, что функция Vt(S, S ) при варьировании параметра t и фиксированных объектах S, S принимает к различных значений, 1 к п, то множество признаков ./V разбивается на к непересекающихся групп N\, N2, ... , Nk таких, что Vt{S, S ) = Vй при teNu, 1 и к. Для установления значения Vй из группы признаков Nu выбирается произвольный признак /„, для которого осуществляется перебор всех опорных множеств 0.єСіА таких, что z„eQ, и вычисляется значение функции близости Be(S, S ). Итак, если известно, что функция Vt принимает к различных значений, то для подсчета значения выражения (1.18) потребуется перебор не всех опорных множеств, а только тех, которые содержат хотя бы один признак из множества {ц, i2, ... , it}- Следовательно, в случае, когда число к различных значений функции Vt мало по сравнению сии, кроме того, число опорных множеств, не содержащих ни одного признака из множества {/ь i2, ... , 4} относительно велико, значение выражения (1.18) может быть вычислено со значительным сокращением перебора опорных множеств. В работе [17] рассмотрены некоторые типы функций близости и так называемые правильные системы опорных множеств, для которых число различных значений Vt(S, S ) невелико. Определение 1.4 [17]. Система опорных множеств QA называется правильной, если из условия QeQA и Q = к, 1 к п-\ следует, что все опорные множества мощности к принадлежат QA. Представление правильной системы опорных множеств в булевом кубе есть объединение некоторых его слоев. Системы опорных множеств (1.1)-(1.4) являются правильными. Определение 1.5 [17]. Функция близости B$(S,S ), принимающая значения 0, 1, называется симметрической, если V5, V юІ5 с52 є Q.A из условия 11(55,-5)11 = (52-5) следует, что 5-(5)=(8). Здесь (ос-р) - вектор, полученный покоординатным произведением векторов а и 3. Данное определение предполагает два допущения. 1. Be(S,S ) = Bfo(b(S, S )), т.е. при заданном способе построения характеристического вектора близости 5 функция близости не зависит от конкретных значений признаков в описаниях объектов S, S , а зависит от вида соответствующего характеристического вектора близости, и формально является функцией двух «-мерных двоичных векторов: 65 и 5 . Это свойство функции близости является весьма естественным, им обладают все функции близости, рассмотренные в 1.1. 2. Имеются такие обучающая выборка и объект S, что функция 5( , S ) при варьировании S принимает все значения из Е" кроме, быть может, нулевого значения (0, 0, ... , 0). Из определения 1.5 следует, что: 1) симметрическая функция зависит только от числа признаков, по которым близки рассматриваемые подописания двух объектов, но не зависит, например, от индексов таких признаков; 2) свойство симметричности функции близости зависит, вообще говоря, от вида системы опорных множеств: так, например, функция близости (1.9) является симметрической, если выбрана система опорных множеств (1.2), и не является симметрической, если выбрана система опорных множеств (1.1). Теорема 1.7 [17]. Пусть система опорных множеств является правильной, а функция близости - симметрической. Тогда функция Vt(S, S ) принимает не более двух различных значений при t \n , V S, S . Из доказательства теоремы следует, что все признаки, которым в векторе b(S, S ) соответствуют нулевые (единичные) координаты, входят в одинаковое число V0 (Vі) опорных множеств С1єСіА таких, что BQ(S,S ) = 1. Тогда в условиях теоремы 2.7 выражение (1.18) может быть записано в виде где 5 - вектор, полученный из 5 покоординатным отрицанием. Теорема 1.7 справедлива, в частности, для случая функции близости (1.8) и системы опорных множеств (1.2). Утверждение 1.3 [17]. Для системы опорных множеств (1.2) и функции близости (1.8) справедливы выражения Так, величина Vі равна числу подмножеств N мощности к, содержащих признак t, которому соответствует единичная координата вектора S(S,S ), и не более 8 признаков, которым соответствуют нулевые координаты вектора 6(5,5 ). Обобщением понятия симметрической функции близости является понятие функции близости, симметрической по разбиению. Пусть задано V разбиение R множества признаков N на подмножества N\, N2, ... ,NV, N = [J Ni. Определение 1.6 [17]. Опорные множества Qb Q2 с характеристическими векторами 65l5 52 называются эквивалентными по разбиению R ( -эквивалентными), если (5, со ) = (52 со ) , і = 1, v, со характеристический вектор подмножества N{. -эквивалентность опорных множеств Qb Q2 (характеристических векторов со,, о52) обозначается записью R R Определение 1.7 [17]. Функция близости 5ffi(5,5 ) называется симметрической по разбиению R, если V 8, V со,, со2 є Q.A, из условия со\ со2 следует, что 5Si(5) = ЯЙ2(5).
Одномерная задача поиска прямоугольника. Элементарные двухшаговые процедуры поиска
Рассмотренные в предыдущем параграфе результаты исследований модели АВО можно разделить на четыре группы. 1. Эффективные формулы вычисления оценок для моделей АВО с различными видами опорных множеств и функций близости (таблица 1.1). Для АВО с атомарными системами опорных множеств, а также для АВО с симметрическими функциями близости эффективные формулы строятся на основе функции Vt(S, S ) (см. подпараграф 1.2.3). 2. Оценка сложности формул вычисления оценок для моделей АВО, параметры которых обладают некоторыми свойствами (работа [17], подпараграф 1.2.3). Для правильной системы опорных множеств и симметрической функции близости функция Vt принимает не более двух различных значений. Для правильной системы опорных множеств и функции близости, симметрической по некоторому разбиению R, функция Vt принимает не более 2r{R) различных значений, где г{К) - число классов -эквивалентности. 3. Оценка того, как будет изменяться сложность формул вычисления оценок при применении к системе опорных множеств изометрических подстановок и теоретико-множественных операций (работа [2], подпараграф 1.2.4, теоремы 1.11-1.14). 4. Определение свойств параметров алгоритмов АВО, для которых формулы вычисления оценок имеют заданную сложность (работа [13], подпараграф 1.2.5). Доказано, что если для данной модели АВО функция Vt принимает не более двух значений, то система опорных множеств QA модели является либо системой (1.4), либо система ОЛ{(0, 0, ... , 0), (1, 1, ... , 1)} может быть сведена некоторыми преобразованиями к системе Q A с Е1п или к Q. A с: Е -1. В таблице 1.1 показано, для каких систем опорных множеств и функций близости получены результаты, относящиеся к первой группе.
Стрелки в таблице 1.1 показывают, что на основе эффективных формул вычисления оценок, полученных для одних систем опорных множеств и функций близости, могут быть получены эффективные формулы вычисления оценок для других систем опорных множеств и функций близости. Так, например, на основе эффективных формул для системы опорных множеств (1.2) и функции близости (1.8) можно путём выбора параметров функции близости (1.8) получить эффективные формулы для той же системы опорных множеств и функции близости (1.6). С другой стороны, на основе этого же результата и свойства аддитивности оценки Г}(5) по объединению непересекающихся систем опорных множеств могут быть получены эффективные формулы для систем опорных множеств (1.3), (1.4) и функции близости (1.8).
Некоторые системы опорных множеств, рассмотренные в работах [10, 14, 17, 22, 38], являются обобщением, или же могут быть получены объединением других систем опорных множеств. Эти связи представлены на рис. 1.1.
Запись "А-+В" означает, что множество вида А можно описать множеством вида В. Так, например, к-й слой булева куба является сферой с центром в точке (0, 0, ... , 0) и радиусом к. Очевидно, отношение "- " транзитивно: к-й слой куба, являющийся сферой, может быть представлен в виде объединения непересекающихся атомарных множеств.
Из рис. 1.1 следует, что, вообще говоря, на основе формул вычисления оценок для систем опорных множеств, являющихся атомарными, могут быть построены формулы вычисления оценок для систем опорных множеств любого вида, представленного на этом рисунке.
Модель алгоритмов вычисления оценок по двухмерной информации (ДАВО) представляет собой модификацию классической модели АВО для случая, когда описанием объекта в задаче распознавания является изображение, представленное матрицей [7]. Алгоритм модели ДАВО отличается от алгоритма модели АВО тем, что работает не со строками, описывающими объекты в задаче распознавания, а с матрицами. Таким образом, если объекты описываются матрицами размера мху, и 1, v 1, то система опорных множеств ДАВО представляет собой совокупность подмножеств множества {1, 2, ... , и}х{1, 2, ... , v}. При этом каждое опорное множество Q может быть описано характеристической матрицей со, в которой единица в позиции (/, у) указывает, что двойной индекс (/, у) входит в Q (аналогично тому, как в АВО "одномерное" опорное множество кодировалось характеристическим вектором со). Остальные параметры модели вместе с формулой для вычисления оценки Гу(5) объекта S по у -му классу остаются прежними. Для удобства, приведём здесь формулу (1.11), заменив характеристический вектор со опорного множества характеристической матрицей.
Нижняя оценка сложности двухшаговой процедуры одномерного поиска прямоугольника
Под изображением физического объекта в настоящей работе понимается полученная некоторым устройством матрица, кодирующая значения амплитуды электромагнитных или звуковых (ультразвуковых) волн определённой частоты, отражённых или испущенных этим объектом. Элементы этой матрицы называются пикселами.
Подавляющее большинство задач распознавания, в которых описание объекта есть изображение, обладают следующими специфическими свойствами. Все признаки, описывающие объект (пикселы изображения), представляют собой дискретизированные значения одной и той же физической величины (уровня некоторого сигнала, поступившего от объекта), и принимают значения из одного множества. Это позволяет рассматривать функции близости, в которых производится сравнение значений разных признаков (т.е. признаков с разными номерами). В тех задачах распознавания, где описанием объекта является не изображение, различные признаки описания представляют собой, как правило, результаты измерения разных физических величин (вес, длина, возраст и т.д.). Поэтому в таких задачах сравнение значений различных признаков является бессмысленным. На основе описанного свойства далее, в подпараграфе 2.5.1, будет обобщено определение функции близости, принятое для модели АВО, и рассмотрены новые типы функций близости.
Если на множестве признаков естественным образом ввести отношение соседства, то найдётся большое количество групп соседних признаков, имеющих близкие значения. Этот факт объясняется тем, что во многих изображаемых сценах существуют объекты с поверхностями, имеющими зоны постоянного цвета, освещённость которых также постоянна или изменяется медленно (в масштабе используемого пространственного разрешения).
Если за описание объекта принять матрицу, полученную из исходного изображения "перемешиванием" его пикселов, то исходная задача может стать неразрешимой. Этот факт объясняется тем, что во многих задачах распознавания изображений нарушение пространственной организации, взаимного расположения признаков в исходной матрице приводит к невозможности выделения и анализа компонент изображения (связных областей, границ объектов, остовов объектов и др.), имеющих принципиальное значение для решения задачи.
Могут существовать преобразования исходных изображений, применение которых улучшит качество решения задачи при фиксированном алгоритме распознавания. Такие преобразования зависят от условий получения изображений и существа задачи. Например, во многих задачах к исходным изображениям применяются процедуры подавления шумов или процедуры, приводящие гистограмму яркости изображений к необходимому виду.
Для задач распознавания, в которых описание объекта не есть дискретизированный одномерный или двухмерный сигнал (т.е. изображение), ни одно из свойств 1-4, как правило, не выполняется.
Ещё одна специфическая черта задачи распознавания изображений заключается в следующем. Исходя из традиционной постановки задачи распознавания (см., например, [17]) изображение Y(S) объекта S следует считать его признаковым описанием I(S), к которому будет применяться тот или другой алгоритм распознавания. В большинстве практических случаев, однако, изображение Y(S) объекта S рассматривается как новый объект S , для которого, соответственно содержанию задачи, выбирается подходящее признаковое описание-строка Д5"). В области обработки и анализа изображений создано большое число методов, позволяющих вычислять самые разнообразные числовые характеристики изображений и их фрагментов. Алгоритм распознавания применяется, далее, к описанию Д") = I(Y(S)). Таким образом, подавляющее большинство используемых алгоритмов распознавания изображений работают с признаковыми описаниями изображений, но не с самими изображениями. Нам известна только одна модель алгоритмов распознавания, ориентированных на непосредственную работы с изображениями - модель ДАВО. Для классификации объекта S алгоритм модели ДАВО применяется к изображению Y(S); решение о зачислении объекта S в тот или другой класс принимается только на основе сопоставления значений пикселов (групп пикселов) изображения Y(S) и изображений обучающей выборки.
При переходе от модели АВО к модели ДАВО задача построения эффективных реализаций алгоритмов модели сохраняет свою актуальность, поскольку выражение (2.1) для оценки объекта по классу не изменяется. Эффективные формулы, полученные для некоторых параметров модели АВО, могут, конечно же, использоваться и в модели ДАВО с такими же параметрами. Вместе с тем, в модели ДАВО естественным образом возникают новые типы опорных множеств и функций близости, не рассматривавшиеся ранее в исследованиях модели АВО.
Как в теоретическом, так и в практическом отношениях, наиболее естественным типом опорного множества для модели ДАВО представляется прямоугольный фрагмент изображения. Все известные нам результаты, связанные с эффективными реализациями алгоритмов модели ДАВО, касаются случая прямоугольных опорных множеств. Вместе с тем, на основе так называемых двухшаговых процедур поиска прямоугольника [41] могут быть построены эффективные реализации ДАВО для случая опорных множеств, представляющих собой композицию прямоугольников. Пусть в стандартной задаче классификации множество допустимых объектов есть множество матриц размера uxv с элементами из множества.
Похожие диссертации на Эффективные алгоритмы, основанные на вычислении оценок, с прямоугольными опорными множествами, для задач распознавания изображений
