close

Вход

Забыли?

вход по аккаунту

?

bd000103210

код для вставкиСкачать
На правах рукописи
Нефёдов Алексей Валентинович
Эффективные алгоритмы, основанные на вычислении оценок,
с прямоугольными опорными множествами,
для задач распознавания изображений
01.01.09 - "Дискретная математика и математическая кибернетика"
АВТОРЕФЕРАТ
диссертации на соискание учёной степени
кандидата физико-математических наук
Г--
к
Москва - 2005
Работа выполнена на кафедре "Математические методы прогнозирования"
факультета вычислительной математики и кибернетики
Московского государственного университета им. М.В.Ломоносова
Научный руководитель:
кандидат физико-математических наук
Гуревич Игорь Борисович
Официальные оппоненты:
доктор физико-математических наук
Рязанов Владимир Васильевич
кандидат физико-математических наук
Кольцов Пётр Петрович
Институт систем обработки изображений
Ведущая организация:
Р А Н (г. Самара)
Защита диссертации состоится 9 декабря 2005 г. в
77
часов на заседании
диссертационного совета Д 501.001.44 в Московском государственном университете им.
М В Ломоносова по адресу: 119992, ГСП-2, г. Москва, Ленинские горы, МГУ, 2-й учебный
корпус, факультет ВМиК, аудитория 685.
С диссертацией можно ознакомтъся в библиотеке факультета В М и К М Г У
Автореферат разослан "
".
2005 г.
Ученый секретарь
диссертационного совета
профессор
^iOf- ' ^
Н.П.Трифонов
Ц ^
^^ > 7^^в
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Задача распознавания (классификации) образов
заключается в отнесении объекта к тому или иному классу объектов на основе
прецедентной информации, заданной совокупностью объектов с известной
классификацией. Объекты представлены своими признаковыми описаниями как правило, векторами или матрицами чисел; природа объектов может быть
самой разной (предмет, состояние, ситуация, процесс и т.д.)- Характерной
чертой
задачи
распознавания
образов
является
то,
что
решение
о
классификации объекта необходимо принять на основе неформализованной,
неполной, косвенной, разнородной, иногда противоречивой информации.
Можно утверждать, что с задачами распознавания образов человек
сталкивался с древнейхпих времен, начиная с первых шагов своего развития.
Сегодня, в эпоху информационных технологий, задачи распознавания образов
возникают и успешно решаются в самых различных областях человеческой
деятельности - в медицине, экологии, социологии, геологии, в технике и на
производстве, в военных разработках, криминалистике, управлении, и т.д.
Начиная
с
первой
половины
прошлого
века -
времени
зарождения
математической теории распознавания образов, - создано и исследовано
большое количество разнообразных методов и подходов к решению этих задач.
В
целом,
можно
выделить
пять
основных
типов
алгоритмов
распознавания образов:
1) алгоритмы, основанные на принципе разделения,
2) статистические алгоритмы,
3) алгоритмы, основанные на принципе потенциалов,
4) алгоритмы, основанные на исчислении высказываний,
5) алгоритмы, основанные на вычислении оценок.
Алгоритмы первого типа основаны на построении в признаковом
пространстве,
соответствующем
числовым
описаниям
объектов,
гиперплоскости (или более сложной Нй^йАН^Ш^^'Ь^зделяющей объекты
разных
классов.
Эти
алгоритмы
различаются
типами
разделяющих
поверхностей и методами их построения.
Статистические алгоритмы принимают решение о классификации
объекта на основе тех или иных принципов математической статистики. Как
правило, используется информация о вероятностных характеристиках классов,
например, соответствующие функции распределения.
В алгоритмах третьего типа для определения меры сходства объектов
используется
функция
близости,
значение
которой
пропорционально
произведению "масс" объектов (определяемых, например, соответственно
степени их представительности), и обратно пропорционально расстоянию
между их описаниями в признаковом пространстве.
В
алгоритмах, основанных на исчислении высказываний, объекгы
описываются логическими переменными, а юхассы объектов - булевыми
соотношениями между этими переменными. Классификация объекта сводится к
проверке для его описания булевых условий, описывающих классы.
Для решения большого количества задач распознавания образов
успешно использовалась предложенная Ю.И.Журавлёвым модель алгоритмов
распознавания, основанных на вычислении оценок (модель АВО). Модель
описывает вычислительную структуру алгоритма распознавания, работающего
с одномерными признаковыми описаниями объектов (числовыми векторами), и
параметры,
которые
необходимо
задать
для
определения
конкретного
алгоритма в модели.
Алгоритм АВО классифицирует объект в два этапа. На первом этапе
строится вектор оценок объекта по заданным классам; на втором этапе на
основе этого вектора принимается решение о зачислении объекта в тот или
иной класс. Обычно объект заносится в класс, по которому получена
максимальная оценка. Оценка объекта по классу вычисляется на основе
последовательного сравнения и вычисления меры сходства признакового
описания объекта с признаковыми описаниями объектов обучающей выборки,
принадлежащих этому классу. Метод вычисления меры сходства между
классифицируемым объектом и прецедентом основан на сравнении значений
различных комбинаций признаков двух объектов или, другими словами, на
сравнении различных фрагментов их признаковых описаний.
Модель А В О оказалась весьма полезной не только для решения
прикладных задач, но также и для теории распознавания образов, где на её
примере было предпринято первое глубокое исследование возможностей
некорректных (эвристических) алгоритмов обработки данных.
Одной из важных задач, связанных с практическим использованием
модели АВО,
алгоритмов
является задача уменьшения вычислительной
для
различных
типов
параметров
модели.
сложности
Алгоритмы
с
практически приемлемой вычислительной сложностью строятся на основе
эффективных формул вычисления оценок, моделирующих работу алгоритма формул вычисления оценок близости распознаваемых объектов и прецедентов.
Параметрами
АВО,
существенно
влияющими
на
сложность
формул
вычисления оценок, являются система опорных множеств и вид функции
близости. Система опорных множеств представляет собой набор подмножеств
признаков, по которым распознающий алгоритм производит
сравнение
описаний объектов; функция близости определяет, будут ли сравниваемые
объекты считаться "близкими" или нет. К настоящему времени довольно полно
исследованы
задачи,
связанные
с
получением
эффективных
формул
вычисления оценок для случая, когда объекты в задаче описываются векторами
признаков, а опорные множества представляют части этих описаний. После
построения эффектив1п.1Х формул вычисления оценок может быть рещена
задача выбора в модели алгоритма, экстремального по функционалу качества
классификации.
В
большом числе задач распознавания образов исходные данные
представляют собой изображения или включают их наряду с другими видами
данных.
Такие
задачи
обладают
рядом
существенных
особенностей.
обусловленных свойствами изображения как носителя информации, и требуют
для своего решения использования специальных
методов и подходов,
изучаемых в рамках теории обработки и анализа изображений.
Модель алгоритмов вычисления оценок по "двухмерной" информации
(модель
ДАВО)
была
определена
И.Б.Гуревичем
как
специализация
классической модели АВО для задач распознавания изображений, в которых
исходным описанием объекта распознавания - изображения - является
числовая матрица (матрица пикселов изображения). Несмотря на то, что
эффективные формулы построены почти для всех интересных на практике
моделей АВО, эти результаты оказываются неприменимыми для модели ДАВО.
Это происходит потому, что при распознавании изображений использование
многих популярных в модели АВО видов опорных множеств оказывается в
большинстве случаев лишённым смысла. Вместе с тем, в модели ДАВО с
учётом специфики исходного описания изображения в задаче естественным
образом возникают новые типы опорных множеств (а также и функций
близости), не рассматривавшиеся ранее в исследованиях модели АВО. Этим
объяснятся актуальность исследования модели ДАВО с целью построения
эффективных алгоритмов с новыми типами опорных множеств и функций
близости.
Исследование алгоритмов ДАВО представляет интерес также и в
другом
аспекте.
Все
используемые
в
настоящее
время
алгоритмы
распознавания изображений предназначены для работы с признаковыми
описаниями или моделями изображений. При этом в большинстве задач
распознавания изображений выбор адекватного признакового описания или
модели изображения имеет важнейшее значение для успешного решения задачи
и представляет отдельную трудную проблему. В связи с этим представляет
интерес исследование алгоритмов распознавания изображений, работающих
напрямую с изображениями и не использующих каких-либо производных
описаний изображений. Нам известна только одна модель алгоритмов
распознавания, ориентированных на прямую работу с изображениями - модель
ДАВО. Алгоритмы модели ДАВО сопоставляют изображения непосредственно
по их фрагментам без использования каких-либо признаков.
Целями работы являются:
1. Разработка и исследование эффективных алгоритмов модели ДАВО с
различными видами систем прямоугольных опорных множеств и функций
близости.
2. Исследование на примере ДАВО возможности решения задач распознавания
изображений алгоритмами, работающими с изображениями напрямую, без
использования их признаковых описаний и моделей.
Научная
новизна.
В
диссертации
предложены
новые
методы
эффективных реализаций алгоритмов ДАВО с системами прямоугольных
опорных множеств и системами опорных множеств, являющихся композицией
прямоугольников.
Рассмотрены
новые
типы
функций
близости,
ориентированные на работу с изображениями. Значение этих функций близости
вычисляется на основе сравнения независимых фрагментов двух матриц.
Предложены
эффективные
реализации
алгоритмов
ДАВО
с
системой
прямоугольных опорных множеств и функциями близости нового типа.
Введено определение многошаговой процедуры поиска шаблона на
растре, предназначенной для исследования сложности алгоритмов ДАВО с
системами
опорньк
множеств,
порождённых
шаблоном.
Предложены
эффективные двухшаговые процедуры поиска прямоугольника, а также метод
комбинирования этих процедур для поиска шаблона, представляющего собой
объединение прямоугольников. Определены классы двухшаговых процедур, в
которых построенные процедуры поиска прямоугольника имеют наименьшую
сложность. Получена нижняя оценка сложности двухшаговой процедуры
поиска прямоугольника. Впервые при помощи алгоритмов, работающих
напрямую с изображениями и не использующих в явном виде какие-либо
признаки, решена практическая задача распознавания.
Методика
исследования:
методы
дискретной
математики
и
комбинаторного анализа, теории обработки и анализа изображений, численные
эксперименты на Э В М .
Практическая ценность. Полученные в диссертационной работе
результаты позволяют создавать имеющие приемлемую вычислительную
сложность
алгоритмы
распознавания
изображений,
не
использующие
признаков и моделей изображений (традиционного типа).
Апробация
работы.
Результаты
диссертационной
работы
докладывались на
-
5-й Международной конференции "Распознавание образов и анализ
изображений: новые информационные технологии" (2000, Самара, ИСОИ
РАН),
-
Всероссийской с участием стран СНГ конференции "Методы и средства
обработки сложной графической информации" (2001, Нижний Новгород,
НижГУ),
-
Международной
конференции
студентов
и
аспирантов
по
фундаментальным наукам "Ломоносов 2001", "Ломоносов 2003" (Москва,
МГУ),
6-й Международной конференции "Распознавание образов и анализ
изображений: новые информационные
технологии" (2002,
Великий
Новгород, НовГУ),
-
the 13* Scandinavian conference on image analysis (2003, Гётеборг, Швеция,
Halmstad University),
6-M Открытом российско-немецком семинаре "Распознавание образов и
понимание изображений" (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
Федеральной
целевой научно-технической
программы
"Исследования
и
разработки по приоритетным направлениям развития науки и техники" на 20022006 гг., проектов Программы фундаментальных исследований отделения
математических
наук
РАН
"Алгебраические
и
комбинаторные
методы
математической кибернетики" 2003-2005 гг.. Комплексной программы научных
исследований Р А Н "Математическое моделирование и интеллектуальные
системы" 2001-2005 гг., проекта 03-55-1759INTAS Young Scientist Fellowship.
Личный вклад. Результаты работы, выносимые на защиту, получены
диссертантом самостоятельно.
Публикации. По теме диссертации опубликовано 11 работ. Некоторые
результаты работы включены в научные отчёты по указанным выше проектам.
Структура и объём работы. Диссертация состоит из введения, четырёх
глав, заключения и списка литературы. Определения, примеры, утверждения,
леммы, теоремы, следствия, рисунки и таблицы нумеруются в пределах главы.
Объём текста работы - 132 страницы.
СОДЕРЖАНИЕ РАБОТЫ
Во введении описывается актуальность работы и определяются цели
исследования.
В первой главе в §1.1 описывается модель алгоритмов вычисления
оценок и рассматриваются примеры наиболее употребимых типов систем
опорных множеств и функций близости - основных параметров модели.
Вводятся основные обозначения и понятия, используемые в исследованиях
АВО.
Известно, что в общем случае всякий алгоритм распознавания может
быть представлен в виде композиции распознающего оператора и решающего
7
правила. В АВО распознающий оператор переводит стандартное описание
объекта S, подлежащего классификации, в набор числовых оценок (Г|(5), Г2(5),
... , r^S)), где / - число классов в задаче. С помощью решающего правила по
этому набору строится информационный вектор (а,, Oj, ..., а^), а^ е{0,1, Д},
где а^ = 0 , если алгоритм не относит объект 5 к у'-му классу; а^ = 1 , если
алгоритм относит объект S к у-му классу; а^ = Д, если алгоритм не смог
классифицировать объект S по_/-му классу.
Для определения распознающего оператора в АВО необходимо задать
систему опорных множеств, функцию близости объектов, веса признаков и веса
прецедентов.
1. Система опорных множеств Q^ представляет собой некоторую совокупность
непустых подмножеств множества признаков N = {I, 2, ... , п}, значениями
которых описывается объект. Примерами систем опорных множеств в АВО
могут служить класс всех непустых подмножеств множества N; класс изо всех
подмножеств
множества Л'' заданной мощности к; класс
подмножеств
множества Л' мощности не более заданной, и т.д. Любое опорное множество Q
может быть закодировано двоичным вектором S длины п следующим образом:
i-я координата га равна единице тогда и только тогда, когда /-Й признак входит
в
П.
Вектор
S,
построенный
по
такому
правилу,
тгазываегся
характеристическим вектором опорного множества Q.
2. Пусть/(5)=(ai, а2, ... , а„) есть признаковое описание объектаS,Q= {/), г'г,...,
4},
й
есть характеристический вектор fi. Символом ZI(S)
или 5 5
обозначается подописание объекта S вида (а,|,а,^,...,а,^), называемое 3подописанием. Функцией близости B^(S, 5") называется функция, зависящая от
й-подописаний объектов S, 5", и принимающая значение О (объекты "не
близки") или 1 (объекты "близки").
3.
Веса
признаков
задаются
вектором
р = {р^,р2,...,р„), р,>0, i = \,n.
Символом р(а) обозначается вес опорного множества Q с характеристическим
вектором й , равный сумме весов признаков, входящих в Q.
4. Веса прецедентов задаются вектором '( = {Ух,У1,—,у„), где у, = y(S^ > О,
q = \,тп,т- общее число прецедентов.
Оценка Г,(5) объекта 5 поу-му классу определяется формулой
^I'^jls'&H'j
аеПу,
где К - нормирующий коэффициент, Wj - множество прецедентов из у-го
класса.
В
§1.2 определяется проблема построения эффективных формул
вычисления оценок, т.е. формул, в которых снимается перебор всех опорных
множеств, за счёт чего комбинаторная сложность вычисления оценки
понижается до сложности, пропорциональной площади обучающей таблицы
(т.е. числу прецедентов, умноженному на число признаков). Приводится
подробный
обзор
основных
результатов,
связанных
с
построением
эффективных формул вычисления оценок в АВО при различных способах
задания систем одномерньпс опорных множеств.
Во второй главе описывается модель ДАВО как специализация модели
АВО для случая распознавания изображений. Алгоритм модели ДАВО
отличается от алгоритма модели А В О тем, что работает не со строками,
описывающими объекты в задаче распознавания, а с матрицами. Система
опорных множеств ДАВО представляет собой совокупность подмножеств
множества { 1 , 2, ... , и]х{\, 2
v}, где и и v - размеры матриц, которыми
описываются изображения в задаче. Остальные параметры модели вместе с
формулой для вычисления оценки Г/5) объекта S по J-му классу остаются
прежними. Приводятся специфические особенности задач распознавания
изображений,
отличающие
их
от
задач
распознавания
с
начальной
информацией другого типа. Описывается идея подхода к построению и оценке
вычислительной сложности широкого класса алгоритмов ДАВО с опорными
множествами, порождёнными произвольным
шаблоном, основанного на
решении задачи поиска данного шаблона на растре при помопда многошаговых
процедур поиска (определение многошаговых процедур поиска даётся в
третьей главе диссертации). Предлагается метод эффективной реализации
алгоритмов
ДАВО
с
системами прямоугольных
опорных
множеств с
использованием эффективных двухшаговых процедур поиска прямоугольника.
На основе комбинированного использования эффективных двухшаговых
процедур
поиска
прямоугольников
предлагается
метод
эффективной
реализации алгоритмов с опорными множествами, представляющими собой
композицию
прямоугольников.
реализации алгоритмов
ДАВО
Для
описанных
даются точные
методов
оценки
эффективной
вычислительной
сложности, показывающие, что сложность предложенных алгоритмов меньше
сложности алгоритмов, основанных на поиске прямоугольника методом
перебора (более подробному и полному исследованию сложности введённых
двухшаговых процедур поиска прямоугольников посвящена третья глава
диссертации).
Для
задач,
в
которых
объекты
описываются
признаками,
принимающими значения из одного множества, вводится новый тип функции
близости, зависящей от результата сопоставления разных подописаний двух
объектов. Рассматриваются примеры функций близости нового типа. Пусть
множество допустимых объектов в задаче классификации есть множество R"""
числовых
матриц
размера
MXV, S\ е R""",
St = (a,j), S2 e R""",
52 = (Z>j,),
ffl,S, = (a,,^,, a,^,^,..., a,^,^), fflj^^ = (b^,^, b^,^,..., b,^^,^).
1. Зафиксируем числа e>Q,q>0,q- целое. Рассмотрим систему неравенств
\а,, -b^, \<£, \а^, -Ь., I<е, ..., Iа, , -Ь^, \<е
И обозначим через у число невыполненных неравенств в этой системе.
Положим
5,(5,5,, SjSj)^-,
1у^я,
О, y>q.
Эта функция близости является непосредственным обобщением одной из
классических функций близости.
10
2. Зафиксируем числа е> О, q >0, q - целое. Пусть G - некоторое множесаво
подстановок
на
множестве
g('^2S2) = (Kfi,>K,^,,->K„0'
{ 1 , 2, ... , ти},
g е G.
Положим
где ( a * . P J = (V'(-t)'V'w^' ^ = 1 ^ - Тогда
S2(w,5,,U252)= ^fiiCcSiS'i.gCSjSj)). Эта функция близости позволяет в
процессе по-пиксельного сравнения двух фрагментов изображения изменять
один из фрагментов, участвующих в сравнении - например, поворачивать его
по часовой стрелке. При помощи этой функции близости могут быть
определены
модели
ДАВО,
инвариантные
относительно
некоторых
преобразований изображений (например, поворота на 90,180, 270 градусов).
3. Зафиксируем число 8 > 0. Пусть a{aS) есть сумма элементов матрицы S,
стоящих в позициях, заданных опорным множеством й , Положим
53(3i5„S2Sj) = -
1, если I aCwji',) - а{&2^2 )\^тг.
' О, иначе.
Сопоставление фрагментов двух изображений при помощи этой функции
близости состоит в сравнении яркостных масс этих фрагментов. Такое
сравнение
также
является
инвариантным
относительно
некоторых
преобразований изображения.
Предлагается эффективный метод вычисления оценок в ДАВО с
функциями близости
B^(S^S^,(62^2)'
^2(^А''^2^2)'
и прямоугольными
опорными множествами. При больших размерах изображений и, v сложность
эффективной реализации алгоритма ДАВО с функцией близости 5, (ш,5,, coj^j)
меньше сложности его прямой реализации в i?i/?2 раз, где Ri, Ri - размеры
прямоугольного опорного множества. Для построения эффективной реализации
алгоритмов
модели
рассматривается
ДАВО
множество
с
функцией
подстановок
G,
близости B2{(b\S^,^2^2)
обладающих
специальным
свойством относительно системы опорных множеств - т.н. а-свойством. Для
множества
подстановок
G,
обладающих
а-свойством,
построение
эффективного метода вычисления оценок в алгоритмах с функцией близости
fi2(S]5,,32-^2) сводится к случаю функции близости В,(3,5,,Ш252)- При
11
больших размерах изображений и, v сложность эффективной реализации
алгоритма ДАВО с функцией близости B2(™i'^i'^2"5'2) меньше сложности его
прямой реализации в \G\RiR2Третья глава работы посвящена определению многошаговых процедур
поиска шаблона на растре и исследованию вычислительной сложности
двухшаговых процедур поиска прямоугольника. На процедурах поиска основан
предложенный во второй главе подход к реализации алгоритмов ДАВО с
опорными
множествами,
порождёнными
заданным
шаблоном.
В
§3.1
формулируется задача поиска шаблона на растре и определяется многошаговая
процедура решения этой задачи. Пусть м, v - натуральные числа, М{и, v) = ( 1 , 2,
..,,м}х{1,2, ...,v}.
Определение. Под двоичным растром размера мху понимается пара
Л„,, = (М(м,у),{0,1}).
Произвольная двоичная матрица C„xv называется значением растра .^„xv
Обозначим символом Е""" множество всех матриц размера мху с элементами из
множества {О, 1}.
Определение. Матрица Ф = (фр,) е Е"'""^ называется матрицей шаблона
(шаблоном), если 1 < i?i < н, 1 < i?2 < v, и существуют такие номера/7;,/?2. 9i, Яг,
что
(Рр^, = (р^^R^ ='P\q, -<PR,q = 1 • Обозначим
множество
индексов
единичных элементов матрицы Ф символом Мф-.
Мф={(р,Ч)\(?рд= 1,1
<P^Rul<q<R2}-
Определение. Шаблон Ф правильно налагается на матрицу С в позиции
(z,y)e М{и - Л, +1, у - ^2 +1), если У(р,д)е
Мф с,^^,.,,^^,., = 1.
Определение. Задачей поиска шаблона Ф^„„^ на растре размера uxv
называется тройка
Г=(и,у, Ф„_хя,).
(1)
Определение. Поисковым отображением для задачи (1) называется
отображение
12
вс
такое, что если F(C) = С , где С еE""",C = ic,j)e £(''-«.+'M-«2+i), то с^ = 1, если
шаблон Ф правильно налагается на матрицу С в позиции (г, j), и с^ =0, в
противном случае.
Понятие
и-шаговой
процедуры
поиска
возникает
в
связи
с
необходимостью реализации поискового отображения и оценки сложности этой
реализации. Структура «-шаговой процедуры поиска задается набором
параметров
((М|, Vi), (М2, V2), . . . , ( « „ ) , V„_|), 5ь 52, ..., S„),
(2)
где Uk, Vi - натуральные числа,
Sk = {S(i,j, к) I (1,/}еМ{щ, v*)},SOJ, к) сМ{щ-1, v^.,), к = \,п,
и
(M(„VO) = ( « , V ) , ( М „ , У „ ) = : ( « - Л , + 1 , V - / ? 2 + 1 ) .
Набор параметров (2) должен удовлетворять четырём условиям,
которые
будут
сформулированы
ниже.
Функционирование
процедуры
описывается следующим образом. Для заданного значения CQ =(с°)е£"°'"'°
растра Ruxv «-шаговая процедура поиска определяет последовательность матриц
в
которой
Q ££"*'"'*,Q =/j(Q_,),
где /i
-
функция,
задаваемая
соотношением
с*=
&
с''\
' = l , " * , 7 = l.Vt,A: = l,W-
Определение. Набор параметров (2) определяет «-шаговую процедуру
F" поиска шаблона Фд ^^
на растре размера uxv («-шаговую процедуру
решения задачи (1)), если справедливы следующие условия:
1) V Со 6 £"»'"'» С„ = F(Co), где F - поисковое отображение для задачи (1);
2) \S(i,j, k)\>2,i = 1Щ, ] = 1Ук,к = йг;
3) 8{ц,]^,к)ф8{}2,]2,к),
при любых допустимых {hji),
k = l7n;
13
{iiji)-- {и,}\У{к,]г\
4)
[jSii,J,k)
= M(u,_„v,_,).
Множество Sk называется множеством связей А:-го уровня процедуры поиска.
Очевидно, процедура поиска шаблона Ф на растре R реализует
поисковое отображение для соответствующий задачи. Пусть F" - и-шаговая
процедура поиска, определенная набором параметров (2)
Определение. Сложностью процедуры F" называется число
\Р''\ = Ъ
Ы
Сложность
процедуры
1(150-/Д) 1-1).
(,,7)eW(«j,vj)
¥"
совпадает
с
числом
конъюнкций,
необходимых для ее реализации, и является мерой ее вычислительной
сложности.
В §3.2 в рамках введённого формализма для описания многошаговых
процедур поиска рассматриваются эффективные двухшаговые процедуры
поиска прямоугольника. Устройство процедур основано на следующей идее: в
задаче поиска прямоугольника размера J?ixJ?2 для получения матрицы С
достаточно на первом шаге сжать столбцы матрицы С в Л] раз (при этом
непрерывные последовательности единиц длины R\ в столбцах матрицы С
переходят в одну единицу), а на втором шаге у полученной матрицы С\ сжать
строки в Ri раз (при этом непрерывные последовательности единиц длины Лг в
строках матрицы С\ переходят в одну единицу). Описанная процедура поиска
обозначается символом F„- Если в этой процедуре поменять порядок сжатия
столбцов и строк, то получится другая двухшаговая процедура поиска
прямоугольника, обозначаемая символом F^^. Для сложности введенных
процедур справедливы равенства:
i F „ | = (м-Л,+1)у(Л,-1) + (м-Л,+1)(у-Л2+1X^2-1)t F , J = «(V - ^2 + 1)(Й2 -1) + (« - Л, + l)(v - Лз + 1)(Л, -1).
При этом \F^\ < |Frc| тогда и только тогда, когда и - R\ < v - Ri ■ Также,
справедливы равенства:
14
\F\-\F„\^iu-R,+l){R,-\){R,-\){v-R,),
\F\-\F^J =
{v-R,+l)iR,-l){R,-\){u-R,),
которые означают, что сложность введенных двухшаговых процедур поиска
меньше
сложности
одношаговой
процедуры
поиска
F,
реализующей
переборный метод поиска прямоугольника. Описан класс двухшаговых
процедур поиска прямоугольника, в котором процедуры F „ , F „ являются
оптимальными, т.е. имеют минимальную сложность (теорема 3.1).
В §3,4 получены условия оптимальности процедуры F „ для одномерной
задачи поиска прямоугольника (теоремы 3.2, 3.5; см. таблицу). Задача поиска
прямоугольника размера RixRi на растре MXV называется одномерной, если R^ =
и, /?2 < V. В случае, когда v < 2/?2 - 1, вместо процедуры Fcr рассматривается её
модифицированный вариант - процедура F/^.
Определение. Набор
параметров (2) определяет обобщённую п-
шаговую процедуру поиска шаблона Фд^д на растре размера иху, если
справедливы условия 1, 2, 4 в определении многошаговой процедуры поиска, а
вместо условия 3 выполнено более слабое условие: S{ij,j^,k)^Siij,J2,k),
любых допустимых {и,]\), {12, ji): {hj'iMiiJi),
при
k = l,n.
Таблица. Условия оптимальности процедуры F^^
Процедура
Условия на параметры
задачи поиска прямоугольника
V > 2^2 - 1
F'
V < 2^2 - 1
v>2R2-l,Ri>R2
F'
v<2R2-l,Ri>R2
15
Класс оптимальности
Двухшаговые процедуры с
непересекающимися связями
1-го уровня
Двухшаговые процедуры с
непересекающимися связями
1-го уровня
Обобщённые двухшаговые
процедуры
Обобщённые двухшаговые
процедуры
в §3.5 получена нижняя оценка сложности двухпшговой процедуры
одномерного поиска прямоугольника, являющаяся следствием теоремы 3.6:
Следствие 3.1. Для сложности двухгааговой процедуры F решения
одномерной задачи поиска прямоугольника справедливо неравенство:
|F|>v(i?,-i?2+l) + (^2-l)'в четвёртой главе описывается применение разработанных алгоритмов
ДАВО для решения трёх задач распознавания изображений с двумя классами.
Первые две задачи демонстрируют возможности алгоритмов ДАВО различать
модельные текстурные изображения, образованные элементами различного
размера, структуры и локализации, и легко разделяемые человеком. Третья
задача заключается в классификации изображений ядер лимфоидных клеток
больных реактивным лимфаденитом и лимфосаркомой. Она демонстрирует
возможности алгоритмов ДАВО различать достаточно сложные текстуры
реальных изображений, классификация которых уже не является столь простым
делом для человека и требует специального обучения и опыта.
ЗАКЛЮЧЕНИЕ
На защиту выносятся:
1.
Метод
эффективной
реализации
алгоритмов
ДАВО
с
системами
прямоугольных опорных множеств, основанный на двухшаговых процедурах
поиска прямоугольника.
2. Метод эффективной реализации алгоритмов ДАВО с системами опорных
множеств, представляющих собой композицию прямоугольников, основанный
на
комбинированном
использовании
двухшаговых
процедур
поиска
прямоугольников.
3. Методы
эффективной реализации
алгоритмов
ДАВО
с
системами
прямоугольных опорных множеств и функциями близости, зависящими от двух
опорных множеств.
16
4. Определение многошаговой
процедуры поиска шаблона на растре,
предназначенной для исследования сложности алгоритмов ДАВО с системами
опорных множеств, порождённых шаблоном.
5. Условия оптимальности эффективной двухшаговои процедуры поиска
прямоугольника. Нижняя оценка сложности двухшаговых процедур поиска
прямоугольника для одномерной задачи.
ПУБЛИКА1ЩИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ
1. Гуревич И.Б., Нефёдов А.В. Метод эффективного вычисления функций
близости
для
двухмерного
подкласса
алгоритмов,
основанных
на
вычислении оценок, с прямоугольными опорными множествами // Труды 5-й
Международной
конференции
"Распознавание
изображений: новые информационные
Самарского
государственного
образов
технологии". -
аэрокосмического
и
анализ
Самара: Изд.
университета
им.
академика С.П.Королёва, 2000. - Т.2. - С.269-274.
2. Нефёдов А.В. Об одном подходе к построению эффективных алгоритмов
вычисления оценок с двухмерными опорными множествами // Тезисы
докладов Всероссийской с участием стран СНГ конференции "Методы и
средства
обработки сложной графической
информации". -
Нижний
Новгород: Изд. НИИ прикладной математики и кибернетики ННГУ, 2001. С.115-116.
3. Нефёдов А.В. Метод сокращения перебора при использовании алгоритмов
вычисления оценок с прямоугольными опорными множествами // Труды 6-й
Международной
конференции
"Распознавание
образов
и
анализ
изображений: новые информационные технологии". - Великий Новгород:
Изд. НовГУ им. Ярослава Мудрого, 2002. - Т.2. - С.426-430.
4. Нефёдов
А.В.
одномерного
Нижняя
поиска
оценка
сложности
прямоугольника
17
двухшаговои
// Материалы
процедуры
Международной
конференции студентов
и аспирантов
по фундаментальным
наукам
"Ломоносов 2003". - Изд. отдел фак. ВМиК МГУ, 2003. - С.12-13.
5. Gurevich I.B., Nefedov A.V. An efficient technique for calculating proximity
functions in the 2D family of algorithms based on estimate calculations with
rectangular support sets // Pattern recognition and image analysis: advances in
mathematical theory and applications. - 2001. -Vol.11. - Хг 1. - pp. 175-178.
6. Gurevich I.B., Nefyodov A.V. Algorithms for estimate calculations designed for
2D support sets. Part 1: rectangular support sets // Pattern recognition and image
analysis, advances in mathematical theory and applications. - 2001. - Vol.11. № 4. -pp.662-689.
7. Nefyodov A.V. A search reducing method in algorithms for an estimate
calculation with rectangular support sets // Pattern recognition and image analysis:
advances in mathematical theory and applications. - 2003. - Vol 13. - № 1. pp.155-157.
8. Nefyodov A.V. Efficient image matching algorithms based on procedures of
searching for 2D templates // Proceedings of the 13* Scandinavian conference on
image analysis. - Springer publ., 2003. -pp.991-997.
9. Gurevich I.B., Nefyodov A.V. Efficient implementation of 2D-AEC algorithms //
Proceedings of the б"" German-Russian workshop "Pattern recognition and image
understanding". - 2003. - pp.96-99.
lO.Gurevich I.B., Nefyodov A.V. Model of 2D-AEC algorithms with rectangular
support sets // Proceedings of the 7* International conference on pattern
recognition and image analysis: new information technologies. - 2004. - Vol.1. pp.235-239.
11.Gurevich I.B., Nefyodov A.V. Block diagram representation of a 2D-AEC
algorithm with rectangular support sets // Pattern recognition and image analysis:
advances in mathematical theory and applications. - 2005. - Vol.15. - № 1. pp.187-191.
18
Напечатано с готового оригинал-макета
Издательство ООО "МАКС Пресс"
Лицензия ИД N 00510 от01.12.99 г
Подписано к печати 02 11 2005 г.
Формат 60x90 1/16. Усл.печл. 1Д5. Тираж 80 экз. Заказ 732.
Тел. 939-3890. Тел./факс 939-3891.
119992, ГСП-2, Москва, Ленинские горы, М Г У им. М.В. Ломоносова,
2-й учебный корпус, 627 к.
05
24590
РНБ Русский фонд
2006-4
24464
Документ
Категория
Без категории
Просмотров
0
Размер файла
769 Кб
Теги
bd000103210
1/--страниц
Пожаловаться на содержимое документа