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

Нефёдов, Алексей Валентинович

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

Нефёдов, Алексей Валентинович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2005 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

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

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

На правах рукописи

Нефёдов Алексей Валентинович

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

01.01.09 - "Дискретная математика и математическая кибернетика"

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Москва - 2005

г- '

Работа выполнена на кафедре "Математические методы прогнозирования" факультета вычислительной математики и кибернетики Московского государственного университета им. М.В.Ломоносова

Научный руководитель:

кандидат физико-математических наук Гуревич Игорь Борисович

Официальные оппоненты:

доктор физико-математических наук Рязанов Владимир Васильевич

кандидат физико-математических наук Кольцов Пётр Петрович

Ведущая организация:

Институт систем обработки изображений РАН (г. Самара)

Защита диссертации состоится 9 декабря 2005 г. в часов на заседании

диссертационного совета Д 501.001.44 в Московском государственном университете им. М В Ломоносова по адресу: 119992, ГСП-2, г. Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ

Автореферат разослан " ".

2005 г.

Ученый секретарь диссертационного совета профессор

^Ьа^-ч^ Н.П.Трифонов

МЧбЧ

№ >

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

В целом, можно выделить пять основных типов алгоритмов распознавания образов:

1) алгоритмы, основанные на принципе разделения,

2) статистические алгоритмы,

3) алгоритмы, основанные на принципе потенциалов,

4) алгоритмы, основанные на исчислении высказываний,

5) алгоритмы, основанные на вычислении оценок.

Алгоритмы первого типа основаны на построении в признаковом пространстве, соответствующем числовым описаниям объектов,

гиперплоскости (или более

объекты

разных классов. Эти алгоритмы различаются типами разделяющих поверхностей и методами их построения.

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

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

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

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

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

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

Модель ABO оказалась весьма полезной не только для решения прикладных задач, но также и для теории распознавания образов, где на её примере было предпринято первое глубокое исследование возможностей некорректных (эвристических) алгоритмов обработки данных.

Одной из важных задач, связанных с практическим использованием модели ABO, является задача уменьшения вычислительной сложности алгоритмов для различных типов параметров модели. Алгоритмы с практически приемлемой вычислительной сложностью строятся на основе эффективных формул вычисления оценок, моделирующих работу алгоритма -формул вычисления оценок близости распознаваемых объектов и прецедентов. Параметрами ABO, существенно влияющими на сложность формул вычисления оценок, являются система опорных множеств и вид функции близости. Система опорных множеств представляет собой набор подмножеств признаков, по которым распознающий алгоритм производит сравнение описаний объектов; функция близости определяет, будут ли сравниваемые объекты считаться "близкими" или нет. К настоящему времени довольно полно исследованы задачи, связанные с получением эффективных формул вычисления оценок для случая, когда объекты в задаче описываются векторами признаков, а опорные множества представляют части этих описаний. После построения эффективных формул вычисления оценок может быть решена задача выбора в модели алгоритма, экстремального по функционалу качества классификации.

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

Модель алгоритмов вычисления оценок по "двухмерной" информации (модель ДАВО) была определена И.Б.Гуревичем как специализация классической модели ABO для задач распознавания изображений, в которых исходным описанием объекта распознавания - изображения - является числовая матрица (матрица пикселов изображения). Несмотря на то, что эффективные формулы построены почти для всех интересных на практике моделей ABO, эти результаты оказываются неприменимыми для модели ДАВО. Это происходит потому, что при распознавании изображений использование многих популярных в модели ABO видов опорных множеств оказывается в большинстве случаев лишённым смысла. Вместе с тем, в модели ДАВО с учётом специфики исходного описания изображения в задаче естественным образом возникают новые типы опорных множеств (а также и функций близости), не рассматривавшиеся ранее в исследованиях модели ABO. Этим объяснятся актуальность исследования модели ДАВО с целью построения эффективных алгоритмов с новыми типами опорных множеств и функций близости.

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

распознавания, ориентированных на прямую работу с изображениями - модель ДАВО. Алгоритмы модели ДАВО сопоставляют изображения непосредственно по их фрагментам без использования каких-либо признаков.

Целями работы являются:

1. Разработка и исследование эффективных алгоритмов модели ДАВО с различными видами систем прямоугольных опорных множеств и функций близости.

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

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

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

Методика исследования: методы дискретной математики и комбинаторного анализа, теории обработки и анализа изображений, численные эксперименты на ЭВМ.

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

Апробация работы. Результаты диссертационной работы докладывались на

- 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 Федеральной целевой научно-технической программы "Исследования и разработки по приоритетным направлениям развития науки и техники" на 20022006 гг., проектов Программы фундаментальных исследований отделения математических наук РАН "Алгебраические и комбинаторные методы математической кибернетики" 2003-2005 гг., Комплексной программы научных исследований РАН "Математическое моделирование и интеллектуальные системы" 2001-2005 гг., проекта 03-55-1759INTAS Young Scientist Fellowship.

Личный вклад. Результаты работы, выносимые на защиту, получены диссертантом самостоятельно.

Публикации. По теме диссертации опубликовано 11 работ. Некоторые результаты работы включены в научные отчёты по указанным выше проектам.

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

СОДЕРЖАНИЕ РАБОТЫ

Во введении описывается актуальность работы и определяются цели исследования.

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

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

правила. В ABO распознающий оператор переводит стандартное описание объекта S, подлежащего классификации, в набор числовых оценок (Г,(5), ^(5"), ... , Г/(5)), где I - число классов в задаче. С помощью решающего правила по этому набору строится информационный вектор (а,, а2, ..., а;), а] е {0,1, А}, где а; =0, если алгоритм не относит объект S к у'-му классу; а] =1, если алгоритм относит объект 5 к j-му классу; = А, если алгоритм не смог классифицировать объект S по j-му классу.

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

1. Система опорных множеств QA представляет собой некоторую совокупность непустых подмножеств множества признаков N = {1, 2, ... , и}, значениями которых описывается объект. Примерами систем опорных множеств в ABO могут служить класс всех непустых подмножеств множества N; класс изо всех подмножеств множества N заданной мощности к; класс подмножеств множества N мощности не более заданной, и т.д. Любое опорное множество Q может быть закодировано двоичным вектором S длины п следующим образом: i-я координата 3 равна единице тогда и только тогда, когда /-й признак входит в П. Вектор 3, построенный по такому правилу, называется характеристическим вектором опорного множества Q.

2. ПустьI(S)=(a¡, а2, ... , а„) есть признаковое описание объектаS, П = {/i2,..., iк}, 3 есть характеристический вектор Q. Символом ш/(S) или 5S обозначается подописание объекта S вида (a ,al2,...,a¡k), называемое 3-подописанием. Функцией близости BB(S, S') называется функция, зависящая от 3 -подописаний объектов S, S', и принимающая значение 0 (объекты "не близки") или 1 (объекты "близки").

3. Веса признаков задаются вектором p = (p]tр2,...,рп), pt >0, / = 1,п. Символом р(5) обозначается вес опорного множества Q с характеристическим вектором 5, равный сумме весов признаков, входящих в Q.

4. Веса прецедентов задаются вектором у = (7],у2>—>Ут)< г#е Y? = > 0> q = 1, т, т - общее число прецедентов.

Оценка Г;(5) объекта 5 по у'-му классу определяется формулой

где К - нормирующий коэффициент, Wj - множество прецедентов из j-го класса.

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

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

множества {1, 2, ... , и}х{\, 2.....v}, где и и v - размеры матриц, которыми

описываются изображения в задаче. Остальные параметры модели вместе с формулой для вычисления оценки Г/5) объекта S по j-му классу остаются прежними. Приводятся специфические особенности задач распознавания изображений, отличающие их от задач распознавания с начальной информацией другого типа. Описывается идея подхода к построению и оценке вычислительной сложности широкого класса алгоритмов ДАВО с опорными множествами, порождёнными произвольным шаблоном, основанного на решении задачи поиска данного шаблона на растре при помощи многошаговых

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

Для задач, в которых объекты описываются признаками, принимающими значения из одного множества, вводится новый тип функции близости, зависящей от результата сопоставления разных подописаний двух объектов. Рассматриваются примеры функций близости нового типа. Пусть множество допустимых объектов в задаче классификации есть множество К""" числовых матриц размера мху, 51] е Я1""', 5| = (ау), ^ е Я'""', 52 = (Ьу),

1. Зафиксируем числа г>0,д>0,д-целое. Рассмотрим систему неравенств |а,, -Ь„, I<е, I, -Ъм I<е, ..., Iа, , -Ь.. I< е

1 '1Л VI 1 1 1 ' ' 1 1т1т гт'т 1

и обозначим через у число невыполненных неравенств в этой системе. Положим

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

= (а,ц>, аН]г,..., а1а]т), й252 = (Ь^, Ъ,

ГА' — »

2. Зафиксируем числа s > 0, q > О, q - целое. Пусть G - некоторое множество подстановок на множестве {1, 2, ... , т}, g е G. Положим g(w2S2) = (bafii,ba2h,...,baA), где (aA.PJ = (V(it)'VlW)' к = Тогда 52(й151,й252)= ^ЛДй^и^Сйз^)). Эта функция близости позволяет в процессе по-пиксельного сравнения двух фрагментов изображения изменять один из фрагментов, участвующих в сравнении - например, поворачивать его по часовой стрелке. При помощи этой функции близости могут быть определены модели ДАВО, инвариантные относительно некоторых преобразований изображений (например, поворота на 90,180, 270 градусов).

3. Зафиксируем число 8 > 0. Пусть 0(55) есть сумма элементов матрицы S, стоящих в позициях, заданных опорным множеством й. Положим

1, если | а(й151) - а(й252) | < тг,

5з(й,5„й252) = -

1 0, иначе.

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

Предлагается эффективный метод вычисления оценок в ДАВО с функциями близости ^(й^.й^з), В2(ш,51,й252), и прямоугольными опорными множествами. При больших размерах изображений и, V сложность эффективной реализации алгоритма ДАВО с функцией близости 2?, (й,5,, й252) меньше сложности его прямой реализации в Я]Я2 раз, где Яг - размеры прямоугольного опорного множества. Для построения эффективной реализации алгоритмов модели ДАВО с функцией близости В2( й15),й25'2) рассматривается множество подстановок С, обладающих специальным свойством относительно системы опорных множеств - т.н. а-свойством. Для множества подстановок С, обладающих а-свойством, построение эффективного метода вычисления оценок в алгоритмах с функцией близости 52(Й151,Й252) сводится к случаю функции близости В,(515,,й252). При

больших размерах изображений и, V сложность эффективной реализации алгоритма ДАВО с функцией близости , ш25'2) меньше сложности его

прямой реализации в \G\R\Ri-

Определение. Под двоичным растром размера ихV понимается пара ^ = {0,1}). Произвольная двоичная матрица С„ху называется значением растра Дих>. Обозначим символом Е"множество всех матриц размера мху с элементами из множества {0, 1}.

Определение. Матрица Ф = (фР9) е ЕЯ]Х"7 называется матрицей шаблона (шаблоном), если 1 < Л) < и, 1 < Я2 < v, и существуют такие номерар\,р2, дг, что (рт, = (рр1 Лз = (рх щ - фщ Я2 = 1. Обозначим множество индексов всех единичных элементов матрицы Ф символом Мф:

Мф= {(р, ч) | Фм = 1,1 <р <Яи 1 < <? <Л2}.

Определение. Шаблон Ф правильно налагается на матрицу С в позиции (/,у)е М{и - Я, +1, V - Д2 +1), если V (р, д) е МФ = 1.

Определение. Задачей поиска шаблона Ф^ на растре размера мху называется тройка

Т- (и, V, Фц1Хц2). (1)

Определение. Поисковым отображением для задачи (1) называется отображение

р. ^(а-/г1+1)х(у-Я2+1)

такое, что если Р(С) = С, где С е Еи", С = (с„) е , то су = 1, если

шаблон Ф правильно налагается на матрицу С в позиции (г, у), и су = 0, в противном случае.

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

(О,, VI), {щ, у2),..., (ип ,, у„_,), 5Ь 52,..., 5„), (2)

где ик, ук - натуральные числа,

8к = {5(7,7, Л) | (г',/)еА/(и*, у*)}, Л) с М(иы, у*_,), к = \,п,

(м0,у0) = («,у), (ип, У„ ) = (« - + 1, V - /?2 + 1) .

Набор параметров (2) должен удовлетворять четырём условиям, которые будут сформулированы ниже. Функционирование процедуры описывается следующим образом. Для заданного значения С0={с^)еЕщХГ° растра Яи„ «-шаговая процедура поиска определяет последовательность матриц = (с'у > С2 = (су )И2Х„2, ..., Сп — (су )„яХУп,

в которой Ск е Е"к"п ,Ск =/к(Ск^), где /к - функция, задаваемая соотношением

с*= & с4"',

» = 1, = 1» =

Определение. Набор параметров (2) определяет «-шаговую процедуру Е" поиска шаблона Фд1хЛ2 на растре размера мху («-шаговую процедуру решения задачи (1)), если справедливы следующие условия:

1) V С0 е .Е"0*"0 Сп = Р(С0), где Р - поисковое отображение для задачи (1);

2) \SfjJ, к)|*2,/ = у = * = Цй;

3) 8(ц,]},к)&8{}2,]2,к), при любых допустимых (г'ьУО, ('2,7г): ОьУ'О"('г.л),

4) =

(I ])еМ(ик,*к)

Множество называется множеством связей к-го уровня процедуры поиска.

Очевидно, процедура поиска шаблона Ф на растре Я реализует поисковое отображение для соответствующий задачи. Пусть - л-шаговая процедура поиска, определенная набором параметров (2)

Определение. Сложностью процедуры называется число

1^1 = 1 1(|50,/Д) 1-1).

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

В §3.2 в рамках введённого формализма для описания многошаговых процедур поиска рассматриваются эффективные двухшаговые процедуры поиска прямоугольника. Устройство процедур основано на следующей идее: в задаче поиска прямоугольника размера Я\хЯ2 для получения матрицы С достаточно на первом шаге сжать столбцы матрицы С в Л] раз (при этом непрерывные последовательности единиц длины Л) в столбцах матрицы С переходят в одну единицу), а на втором шаге у полученной матрицы С1 сжать строки в Я2 раз (при этом непрерывные последовательности единиц длины Я2 в строках матрицы С\ переходят в одну единицу). Описанная процедура поиска обозначается символом Рсг. Если в этой процедуре поменять порядок сжатия столбцов и строк, то получится другая двухшаговая процедура поиска прямоугольника, обозначаемая символом Ргс. Для сложности введенных процедур справедливы равенства:

| ^ I = (и - Д, + 1МД, -1) + (и - Л, + 1)(у - Я2 + IXя2 -1), 1/^1 = ф -Я2 + 1)(й2 -1) + (и - Л, + 1)(у - Я2 + 1ХЛ, -1). При этом < тогда и только тогда, когда и - Я\ < V - Я2 . Также, справедливы равенства:

|F |-1Fcr | = («-*,+ 1)(Д, - 1)(Я2 -l)(v-R2), IFH^Mv-^+lXJli-lX^-lX«-*,),

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

В §3.4 получены условия оптимальности процедуры Fcr для одномерной задачи поиска прямоугольника (теоремы 3.2, 3.5; см. таблицу). Задача поиска прямоугольника размера R{xR2 на растре uxv называется одномерной, если Ri = и, R2 < v. В случае, когда v < 2R2 - 1, вместо процедуры Fcr рассматривается её модифицированный вариант - процедура Fc'r.

Определение. Набор параметров (2) определяет обобщённую п-шаговую процедуру поиска шаблона ФЛ1ХЙ2 на растре размера uxv, если справедливы условия 1, 2, 4 в определении многошаговой процедуры поиска, а вместо условия 3 выполнено более слабое условие: S(it, у, Д) * S(i2,J2,k), при любых допустимых {i\,]\), (¿2,72): (hj'iMiij'i), к = 1,п.

Таблица. Условия оптимальности процедуры Fc

Процедура Условия на параметры задачи поиска прямоугольника Класс оптимальности

Fcr v > 2R2 - 1 Двухшаговые процедуры с непересекающимися связями 1-го уровня

F'cr v<2R2-l Двухшаговые процедуры с непересекающимися связями 1-го уровня

Fcr v>2R2-l,Rt>R2 Обобщённые двухшаговые процедуры

Fïr v<2R2-l,Ri >R2 Обобщённые двухшаговые процедуры

В §3.5 получена нижняя оценка сложности двухшаговой процедуры одномерного поиска прямоугольника, являющаяся следствием теоремы 3.6:

Следствие 3.1. Для сложности двухшаговой процедуры F решения одномерной задачи поиска прямоугольника справедливо неравенство:

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

ЗАКЛЮЧЕНИЕ

На защиту выносятся:

1. Метод эффективной реализации алгоритмов ДАВО с системами прямоугольных опорных множеств, основанный на двухшаговых процедурах поиска прямоугольника.

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

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

4. Определение многошаговой процедуры поиска шаблона на растре, предназначенной для исследования сложности алгоритмов ДАВО с системами опорных множеств, порождённых шаблоном.

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

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Гуревич И.Б., Нефёдов A.B. Метод эффективного вычисления функций близости для двухмерного подкласса алгоритмов, основанных на вычислении оценок, с прямоугольными опорными множествами // Труды 5-й Международной конференции "Распознавание образов и анализ изображений: новые информационные технологии". - Самара: Изд. Самарского государственного аэрокосмического университета им. академика С.П.Королёва, 2000. - Т.2. - С.269-274.

2. Нефёдов A.B. Об одном подходе к построению эффективных алгоритмов вычисления оценок с двухмерными опорными множествами // Тезисы докладов Всероссийской с участием стран СНГ конференции "Методы и средства обработки сложной графической информации". - Нижний Новгород: Изд. НИИ прикладной математики и кибернетики ННГУ, 2001. -С.115-116.

3. Нефёдов A.B. Метод сокращения перебора при использовании алгоритмов вычисления оценок с прямоугольными опорными множествами // Труды 6-й Международной конференции "Распознавание образов и анализ изображений: новые информационные технологии". - Великий Новгород: Изд. НовГУ им. Ярослава Мудрого, 2002. - Т.2. - С.426-430.

4. Нефёдов A.B. Нижняя оценка сложности двухшаговой процедуры одномерного поиска прямоугольника // Материалы Международной

конференции студентов и аспирантов по фундаментальным наукам "Ломоносов 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 13th 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 6th German-Russian workshop "Pattern recognition and image understanding". - 2003. - pp.96-99.

10.Gurevich I.B., Nefyodov A.V. Model of 2D-AEC algorithms with rectangular support sets // Proceedings of the 7th 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.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N00510 от01.12.99 г Подписано к печати 02 11 2005 г. Формат 60x90 1/16. Усл.печл. 1,25. Тираж 80 экз. Заказ 732. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

(

» f

/ I

05 24590

РНБ Русский фонд

2006-4 24464

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Нефёдов, Алексей Валентинович

Введение.

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

1.1. Определение модели АВО.

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. Эффективный способ вычисления оценок для функции близости Bl(fblSli&2S2).

2.5.3. Подстановки, обладающие а-свойством относительно системы опорных множеств.

2.5.4. Эффективный способ вычисления оценок для функции близости B2(&iSl,(b2S2) и множества 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].

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

Для решения большого количества задач распознавания образов успешно использовалась предложенная Ю.И.Журавлёвым модель алгоритмов распознавания, основанных на вычислении оценок (модель АВО). Модель описывает вычислительную структуру алгоритма распознавания, работающего с одномерными признаковыми описаниями объектов (числовыми векторами), и параметры, которые необходимо задать для определения конкретного алгоритма в модели.

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

Модель АВО оказалась весьма полезной не только для решения прикладных задач, но также и для теории распознавания образов, где на её примере было предпринято первое глубокое исследование возможностей некорректных (эвристических) алгоритмов обработки данных.

Одной из важных задач, связанных с практическим использованием модели АВО, является задача уменьшения вычислительной сложности алгоритмов для различных типов параметров модели. Алгоритмы с практически приемлемой вычислительной сложностью строятся на основе эффективных формул вычисления оценок, моделирующих работу алгоритма -формул вычисления оценок близости распознаваемых объектов и прецедентов. Параметрами АВО, существенно влияющими на сложность формул вычисления оценок, являются система опорных множеств и вид функции близости. Система опорных множеств представляет собой набор подмножеств признаков, по которым распознающий алгоритм производит сравнение описаний объектов; функция близости определяет, будут ли сравниваемые объекты считаться "близкими" или нет. К настоящему времени довольно полно исследованы задачи, связанные с получением эффективных формул вычисления оценок для случая, когда объекты в задаче описываются векторами признаков, а опорные множества представляют части этих описаний. После построения эффективных формул вычисления оценок может быть решена задача выбора в модели алгоритма, экстремального по функционалу качества классификации [12, 11, 14, 16, 20-24, 26-36].

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

Модель алгоритмов вычисления оценок по "двухмерной" информации (модель ДАВО) была определена И.Б.Гуревичем как специализация классической модели АВО для задач распознавания изображений, в которых исходным описанием объекта распознавания - изображения - является числовая матрица (матрица пикселов изображения) [7]. Несмотря на то, что эффективные формулы построены почти для всех интересных на практике моделей АВО, эти результаты оказываются неприменимыми для модели ДАВО. Это проиходит потому, что при распознавании изображений использование многих популярных в модели АВО видов опорных множеств оказывается в большинстве случаев лишённым смысла. Вместе с тем, в модели ДАВО с учётом специфики исходного описания изображения в задаче естественным образом возникают новые типы опорных множеств (а также и функций близости), не рассматривавшиеся ранее в исследованиях модели АВО. Этим объяснятся актуальность исследования модели ДАВО с целью построения эффективных алгоритмов с новыми типами опорных множеств и функций близости.

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

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

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

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

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

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

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

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

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

2. Метод эффективной реализации алгоритмов ДАВО с системами прямоугольных опорных множеств, основанный на двухшаговых процедурах поиска прямоугольника.

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

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

5. Формализм, описывающий многошаговые процедуры поиска шаблона на растре, предназначенный для исследования сложности алгоритмов ДАВО с системами опорных множеств, порождённых данным шаблоном.

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

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

Результаты диссертационной работы докладывались на

5-й Международной конференции "Распознавание образов и анализ изображений: новые информационные технологии" (2000, Самара, ИСОИ РАН),

Всероссийской с участием стран СНГ конференции "Методы и средства обработки сложной графической информации" (2001, Нижний Новгород, НижГУ),

Международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов 2001", "Ломоносов 2003" (Москва, МГУ),

6-й Международной конференции "Распознавание образов и анализ изображений: новые информационные технологии" (2002, Великий Новгород, НовГУ), the 13th Scandinavian conference on image analysis (2003, Гётеборг, Швеция, Halmstad University),

7-й Международной конференции "Распознавание образов и анализ изображений: новые информационные технологии" (2004, Санкт-Петербург, СПГЭУ).

По теме диссертации опубликовано 11 работ. Некоторые результаты работы включены в научные отчёты по указанным выше проектам.

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

Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

Заключение

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

5. Определение многошаговой процедуры поиска шаблона на растре, предназначенной для исследования сложности алгоритмов ДАВО с системами опорных множеств, порождённых шаблоном.

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

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

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Нефёдов, Алексей Валентинович, Москва

1. Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. М.: Наука, 1970. - 320 с.

2. Алексанян А.А., Журавлёв Ю.И. Об одном подходе к вопросу построения эффективных алгоритмов распознавания // Ж. вычисл. матем. и матем. физ. 1985. -Т.25. -№ 2. - С.283-291.

3. Вапник В.Н., Червоненкис А .Я. Теория распознавания образов. М.: Наука, 1974.-418 с.

4. Горелик А.Л., Гуревич И.Б., Скрипкин В.А. Современное состояние проблемы распознавания. Некоторые аспекты. М.: Радио и связь, 1985. -160 с.

5. Гуревич И.Б. О выборе ансамбля признаков распознающих систем по принципу распознавания // Автоматика. Киев, 1974. - № 5. - С.43-52.

6. Гуревич И.Б. Проблема распознавания изображений // Распознавание, классификация, прогноз. 1989. - Вып. 2. - С.280-329.

7. Гуревич И.Б. Эффективные распознающие операторы в классе алгоритмов вычисления оценок по двухмерной информации // Цифровые методы в обработке изображений: Межвузовский сборник научных трудов.

8. Свердловск: Изд. Уральского политехнического института им. С.М. Кирова, 1986.-С.З-15.

9. Гуревич И.Б., Журавлёв Ю.И. Минимизация булевых функций и эффективные алгоритмы распознавания // Кибернетика. Киев, 1974. - № 3. -С. 16-20.

10. Докторович А.Б. Задача выбора оптимального алгоритма распознавания в одном классе алгоритмов голосования // Кибернетика. Киев, 1974. - № 4.

11. Дьяконов А.Г. О выборе системы опорных множеств для эффективной реализации алгоритмов распознавания типа вычисления оценок // Ж. вычисл. матем. и матем. физ. 2000. - Т.40. - № 7. - С.1104-1118.

12. Дьяконов А.Г. Эффективные формулы вычисления оценок для алгоритмов распознавания с произвольными системами опорных множеств // Ж. вычисл. матем. и матем. физ. 1999. - Т.39. -№11.- С.1904-1918.

13. Енч В. Алгоритм оптимизации параметров одного класса распознающих алгоритмов // Труды Международного симпозиума по практическому применению методов распознавания образов. Изд. ВЦ АН СССР, 1973. -С.23 7-245.

14. Журавлёв Ю.И. Алгоритмы распознавания, основанные на вычислении оценок. Содержательный смысл параметров, задающих алгоритм // Труды Международного симпозиума по практическому применению методов распознавания образов. Изд. ВЦ АН СССР, 1973.

15. Журавлёв Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. 1978. - Вып. 33. - G.5-68.

16. Журавлёв Ю.И. Экстремальные алгоритмы в математических моделях для задач распознавания и классификации // ДАН СССР. 1976. - Т.231. - № 3. - С.532-535.

17. Журавлёв Ю.И. Экстремальные задачи, возникающие при обосновании эвристических процедур // Проблемы прикладной математики и механики. -1971. С.67-75.

18. Журавлёв Ю.И., Камилов М.М., Туляганов Ш.Е. Алгоритмы вычисления оценок и их применение. Ташкент: Изд. "Фан", 1974.

19. Журавлёв Ю.И., Михалевич B.C. Алгоритмы распознавания, основанные на вычислении оценок для задач с пересекающимися классами // Труды ВЦ Польской АН. Варшава, 1974. - Вып. 145.

20. Журавлёв Ю.И., Никифоров В.В. Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика. 1971. - № 3. - С. 1-11.

21. Задорожный В.В. Алгоритмы вычисления оценок для распознавания изображений // Кибернетика. 1985. - № 1. - С. 103-107.

22. Ищук В.И. О поиске оптимальных весовых коэффициентов для одного класса алгоритмов вычисления оценок // Сборник работ по математической кибернетике. Изд. ВЦ АН СССР, 1976. - Вып.1. - С. 186-194.

23. Камилов М.М. Об оптимизации и некоторых применениях алгоритмов вычисления оценок // Труды Международного симпозиума попрактическому применению методов распознавания образов. Изд. ВЦ АН СССР, 1973.

24. Камилов М.М., Алиев Э.М. Выбор длины голосующих наборов в алгоритмах вычисления оценок // Вопросы кибернетики. Ташкент, 1971. — Вып. 44.

25. Камилов М.М., Алиев Э.М., Ким А.Н. О вычислении в-порогов при распознавании объектов алгоритмами голосования // Вопросы кибернетики. Ташкент, 1971. - Вып. 43.

26. Кульянов Е.Г. Об оптимизации одного класса алгоритмов распознавания // Ж. вычисл. матем. и матем. физ. 1974. - Т. 14. - № 3. - С.756-767.

27. Мазуров В.Д., Казанцев B.C., Белецкий Н.Г, Кривоногов А.И., Смирнов А.И. Вопросы обоснования и применения комитетных алгоритмов распознавания // Распознавание, классификация, прогноз. 1988. - Вып. 1. -С.114-148.

28. Нефёдов А.В. Нижняя оценка сложности двухшаговой процедуры одномерного поиска прямоугольника // Материалы Международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов 2003". Изд. отдел фак. ВМиК МГУ, 2003. - С.12-13.

29. Рязанов В.В. Оптимизация алгоритмов вычисления оценок по параметрам, характеризующим представительность эталонных строк // Ж. вычисл. матем. и матем. физ. 1976. -Т.16. -№ 6. - С. 1559-1570.

30. Слуцкая Т.Д. Алгоритм вычисления информационных весов признаков // Дискретный анализ. Новосибирск, 1968. - Вып. 12. - С.75-90.

31. Слуцкая Т.Д. Об эффективности алгоритмов голосования для одного класса бинарных таблиц // Кибернетика. Киев, 1973. - № 2.

32. Ту Дж., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978. -416 с.

33. Хилков А.В. Формулы вычисления оценок для алгоритмов распознавания с опорными множествами // Ж. вычисл. матем. и матем. физ. 1989. - Т.29. -№ 10. - С.1565-1571.

34. Gurevich I.B., Jernova I.A., Trykova A.A., Nefyodov A.V., and Vorobjev I.A.

35. Automation of hematopoietic tumor diagnostics: an approach to extraction of• th diagnostic data from cytological specimens // Proceedings of the 6 German

36. Russian workshop "Pattern recognition and image understanding". 2003.pp. 167-170.

37. Gurevich I.B., Nefyodov A.V. Efficient implementation of 2D-AEC algorithms. // Proceedings of the 6th German-Russian workshop "Pattern recognition and image understanding". 2003. - pp.96-99.

38. 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.

39. Nefyodov A.V. Efficient image matching algorithms based on procedures of searching for 2D templates // Proceedings of the 13 th Scandinavian conference on image analysis. Springer publ., 2003. - pp.991-997.