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

005533397

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

Динь Вьет Шанг

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

Специальность 05.13.17 - «Теоретические основы информатики»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

г 6 СЕН 2013

Тула 2013

005533397

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении Высшего профессионального образования «Тульский государственный университет» (ТулГУ) на кафедре автоматики и телемеханики.

Научный руководитель: доктор физико-математических наук, профессор Двоенко Сергей Данилович

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

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

Мурашов Дмитрий Михайлович кандидат технических наук, старый научный сотрудник (Федеральное государственное бюджетное учреждение науки «Вычислительный центр имени A.A. Дородницына Российской академии наук»)

Ведущая организация: Федеральное государственное бюджетное учреждение науки «Институт проблем управления имени В.А. Трапезникова Российской академии наук»

Защита состоится "24" октября 2013г. в 14 часов на заседании диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки «Вычислительный центр имени A.A. Дородницына Российской академии наук» по адресу: 119333, Москва, ул. Валилова, 40, конферен-зал.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН. Автореферат разослан "18" сентября 2013 г.

Ученый секретарь диссертационного совета Д 002.017.02, д.ф.-м.н., профессор

В.В. Рязанов

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

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

Задачами обработки массивов данных и, в частности, обработкой изображений занимаются многие исследователи: Besag J., Geirtan S., Geman D., Barnard S., Pearl J.,Yedidia J., Freeman W., Weiss Y., Kolmogorov V., BoyKov Y., Wainwright M., Zabih R., Schlesinger M. I., Flach В. и др. В настоящее время разработаны вполне эффективные алгоритмы обработки, обладающие различными достоинствами и недостатками, наиболее известными из которых являются: Iterated Conditional Mode (ICM), Simulated Annealing, Belief Propagation (BP), Graph Cuts, Tree Re-weighted message passing Sequential (TRWS).

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

Ранее была предложена односторонняя модель марковского случайного поля в виде марковской цепи и разработан эффективный алгоритм распознавания, который выполняется за три прохода по графу соседства элементов взаимосвязанного массива, когда граф соседства не содержит циклов (Двоенко С.Д., Копылов A.B., Моттль В.В.). Свойства такой модели марковского поля можно задать обычной марковской матрицей условных вероятностей переходов между классами ее состояний. Марковская матрица условных вероятностей переходов является параметром предложенной модели. Ранее также было показано, что такая матрица может быть задана только одним значением ее диагонального элемента.

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

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

алгоритм комбинирования ациклических графов, который основан на общей идеологии комплексирования операторов обработки, развиваемой научной школой Ю.И. Журавлева. Для нахождения оптимальных весов графов в их линейной комбинации был разработан алгоритм определения весов графов, основанный на методе Гаусса-Зайделя.

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

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

Цель работы. Целью данной диссертационной работы является разработка алгоритмов подбора диагонального элемента для некоторого заданного ациклического графа соседства и включение поиска значения диагонального элемента марковской матрицы переходов в схему Гаусса-Зайделя при подборе весов графов в их линейной комбинации.

Задачи исследования. Для достижения поставленной цели в работе сформулированы и решены следующие задачи:

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

2. Исследование вырожденных свойств базового алгоритма распознавания при предельных значениях диагонального элемента.

3. Исследование свойств ранее предложенного алгоритма подбора весов при комбинировании ациклических графов соседства.

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

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

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

Объект и предмет исследования. Объектом исследования являются массивы взаимосвязанных данных с графом соседства произвольного вида.

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

Научная новизна положений, выносимых на защиту:

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

2. Алгоритмы подбора диагонального элемента для единственного ациклического графа соседства.

3. Алгоритм подбора единственного диагонального элемента и весов линейной комбинации заданного множества ациклического графов соседства.

4. Алгоритмы подбора для заданного множества ациклических графов соседства диагональных элементов и весов линейной комбинации (схема 1 и схема 2).

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

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

Достоверность полученных результатов подтверждается доказанными математическими утверждениями и модельными экспериментами.

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

Реализация и внедрение результатов работы. Результаты исследований использованы во вьетнамских компаниях «FPT Software JSC», «Vietnam TeleCommunication Corporation», «FTS company» для обработки реальных изображений.

Апробация работы. Основные результаты работы докладывались на 14-ой всероссийской конференции «Математические методы распознавания образов» (г. Суздаль, 2009 г.); VI-ой магистерской конференции ТулГУ (г. Тула, 2011 г.); 21-ой международной конференции студентов, аспирантов и молодых ученых «Ломоносов 2012» (г. Москва, 2012 г.); 9-ой конференции «Интеллектуализация обработки информации» (Черногория, г. Будва, 2012 г.); 22-ой международной конференции по компьютерной графики и зрению «ГрафиКон-2012» (г. Москва, 2012 г.); на заседаниях кафедры ATM ТулГУ (Тула, 20102012 гг.).

Публикации. По материалам диссертации опубликовано 7 статей, из них 3 - в научных изданиях, рекомендованных ВАК Минобрнауки России.

Структура и объем работы. Диссертация состоит из введения, 6 разделов и заключения, изложенных на 156 страницах машинописного текста, содержит 111 рисунков, 2 таблицы, список использованной литературы из 60 наименований и 2 приложения.

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

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

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

Задача распознавания массивов данных и базовый алгоритм

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

Пусть I е Т - элемент массива данных Т. На множестве элементов ? е Т массива данных определено симметричное антирефлексивное бинарное отношение, представленное в виде неориентированного графа С без петель, ребра которого (5,0 б С соединяют соседние элементы массива данных 5 е Т и / е Т. Важно отметить, что хотя обычное бинарное отношение соседства рефлексивно, в данном случае это не так, т.к. (*,/) г б.

В вероятностной постановке такой задачи распознавания предполагается, что массив данных представлен двухкомпонентным случайным полем (X, У). Наблюдаемая компонента У состоит из векторов у,, I е Т, принимающих значения из множества у, е ©, определенного природой источника данных. Элементы х,,/еГ скрытой компоненты X принимают значения из множества х, б П, специфичного для конкретной задачи анализа данных. Например, для задачи распознавания образов О = {1,2,..., тп) - это номера классов объектов.

Задача обработки массива (X, У) представлена как задача преобразования исходного массива У = (у,, Г е Г) в результирующий массив X = (дг,, / е Т).

Такая задача ранее была названа задачей распознавания массивов взаимосвязанных данных.

Пусть | Т | - число элементов массива данных, тогда декартовы степени

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

Тогда априорное распределение вероятностей на множестве комбинаций целевых переменных имеет вид априорной плотности £(Х), X е Q171, а их вероятностная связь с исходными переменными выражена как условная плотность r/(Y\X), Уе©1П.

Задача обработки сводится к численному определению апостериорной плотности распределения вероятностей

Я(Х ] У) = 'Х) * С(Х) rj(Y\Х). (1)

Для массивов взаимосвязанных объектов минимизация уровня ошибок приводит к задаче максимизации апостериорной вероятности

.£(У) = arg max 7г(Х | У), (2)

ИЛИ

x,(Y) = argmaxpl(xl \Y),te.T, (3)

х

где р,(х, | У) - апостериорное маргинальное распределение вероятностей скрытых классов в элементе массива / е Т.

Пусть граф соседства G является ациклическим, т.е. не содержит циклов (рис. 1), а скрытое поле классов X является марковским относительно графа G. Тогда 9((x,|X(0) = 9,(xr|X(0,)), t еТ, где X(l)=(x„seT\t),

X(°0 = (xs,seT\/,(s,/)eG). Аналогичные обозначения относительно графа G

используются для наблюдаемого поля У и массива Т в целом.

Древовидный граф G разбивает окрестность (рис. 1а) нетерминального элемента х, на две произвольные части Любая вершина fe Т в качестве корня t немедленно задает естественный нисходящий порядок просмотра вершин от корня и восходящий порядок к корню, определяя окрестность X^ =хг из одного элемента (рис. 16),

предшествующего х,, и окрестность Х^ непосредственных потомков х(. Ранее было показано, что такое априорное случайное поле является односторонним марковским q,(x, \ Х°}) = q,{x, \хг).

Пусть поле У = (у,,/еГ) образовано случайными наблюдениями у(, условно независимыми относительно поля X = (х,, / е Г), где ¥,(У/ 1^)=Ч/<(Уг I*/)- Ранее было показано, что апостериорное скрытое поле относительно того же графа й остается односторонним марковским р,(х, | Хт, У) = р, (х, | хг, У,+), где У* - поддерево с корнем в у,, включая его.

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

Скрытое поле X при определенных условиях распознается за два прохода по графу в. Сначала вычисляются апостериорные маргинальные распределения классов р,(х, | У,*) при восходящем просмотре от терминальных вершин, для которых принимается р,{х, \У*) = р,(х, |у,). Восходящий просмотр заканчивается в корне дерева, где р,(х, 1*7) = р,{х, | У). При нисходящем просмотре из корня вычисляются апостериорные маргинальные распределения классов р,(х, | У), на основе которых определяются решения о классах.

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

Частная модель марковского случайного поля

Марковская модель априорного скрытого случайного поля классов X определяет его одностороннее свойство в виде условных распределений вероятностей на множестве значений переменной хотносительно любой переменной хЛ е Х°{:) из марковской окрестности х,. Для каждой пары вершин г,/еС, соединенных ребром в дереве й, формально всегда определена пара условных распределений вероятностей д,(х, \хг) и дг(хг\х:). Выбор некоторой вершины дерева <3 в качестве корневой /* е Т задает два направления просмотра этого дерева, объявляя одно из этих распределений «нисходящим» распределением, а другое «восходящим».

С целью упрощения ранее был введен ряд предположений о модели марковского случайного поля X.

Во-первых, односторонняя марковская модель поля X является однородной конечной марковской цепью с неизменными условными распределениями в прямом (восходящем) и обратном (нисходящем) направлениях. Такая модель поля X полностью определена двумя матрицами прямых <2(т х т) и обратных

х т) условных вероятностей переходов.

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

Для неразложимой марковской цели элементы матриц Q и б связаны через финальное распределение вероятностей р(х) на множестве значений скрытых переменных х&О. : с/(х1 |хг) = д(хг | х,)р(х1) / р{хг).

Корень { естественно связать с началом обработки, а начальное распределение сделать корневым е Í2.

Тогда маргинальные априорные распределения во всех остальных элементах также являются равномерными.

В этом случае Ц(х, | хг) = д(хг \ х,). И остается только одна симметричная и дважды стохастичная матрица переходов Q. В частной модели предполагается, что матрица <2 имеет одинаковые диагональные элементы и одинаковые недиагональные элементы. Тогда матрица Q задается только одним значением ее диагонального элемента д.

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

Алгоритмы комбинирования ациклических графов соседства

Как правило, в прикладных задачах графы соседства элементов массива данных содержат циклы. Например, в растровых изображениях естественное отношение соседства пикселей является решеткой, которая не является ациклическим графом. Очевидно, что произвольный граф соседства не может быть заменен древовидным графом Б без потери фундаментального свойства исходного графа представлять полную информацию о каждом элементе I еТ относительно других элементов. Ранее было предложено скомпенсировать редуцированное множество взаимосвязей расширением самого множества 1рафов. В алгоритме комбинирования неизвестные апостериорные маргинальные распределения вероятностей скрытых классов относительно исходного графа соседства заменяются линейной комбинацией распределений относительно некоторого набора ациклических графов соседства. Например, для растровых текстурных изображений было предложено использовать графы на рис. 2.

¡ш

Ступенч. дерево Спираль Горю, змейка Верт. змейка Диаг. змейка

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

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

Задача настройки структурных параметров

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

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

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

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

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

Ранее было показано, что для массивов взаимосвязанных объектов минимизация уровня ошибок приводит к задаче максимизации совместной апостериорной вероятности л(Х\ У) в целом или апостериорных вероятностей Р,(х, еТ для отдельных элементов массива на основе байесовского решающего правила в виде (2) или (3).

Пусть наблюдаемое поле Г = (у,,1еТ) образовано случайными векторами у,, условно независимыми у, (у, |Х) = у, (у, |х,) относительно скрытого поля X = (х„ Г е Г). Тогда апостериорное скрытое поле классов формально из (2) определяется по следующей формуле:

Для каждой реализации случайного поля (X, Г), маргинальные апостериорные вероятности />„(*„ | у„), V е Т известны как результат независимого обучения. С другой стороны, в частной модели случайного марковского поля все

(4)

маргинальные априорные распределения равномерны д„(х„) = 1/л|, уе7\

Таким образом, каждой реализации случайного поля (Л", У) задача максимизации апостериорной совместной вероятности тг{Х | У) сводится к задаче максимизации априорного совместного распределения £(X).

Ранее было показано, что для марковского скрытого случайного поля X и заданного ациклического графа соседства совместное распределение скрытых классов £(Х) можно вычислить по формуле (рис. 16):

П П ^К^дх.лГи^(5)

В частной модели условные вероятности переходов для всех элементов массива задаются в виде матрицы д(тхт) одним значением 0<с/<] для всех ее диагональных элементов и одним значением (1-д)/(т-1) для всех ее недиагональных элементов.

Следовательно, для каждой реализации случайного поля Х~(х„(еГ), соответствующая априорная совместная вероятность £(Х) полностью определяется по формуле (5) значением диагонального элемента </, где

Пусть ^={ие7;„|*.=х„УбО. ^ = {« еТ(П\ха *хг, »еТ^}. Очевидно, что Г, п У2 = 0, V, и У2 = т(п.

Тогда (5) имеет вид:

V. т — 1

Таким образом, для данной реализации поля X = (х„ / е Г) максимизация апостериорной совместной вероятности л-(Х|У) сводится к максимизации априорной совместной вероятности £(Х), что, в свою очередь, ведет к поиску значения диагонального элемента д, доставляющего максимум априорной вероятности:

^Х)=агётахС(Х,д). (8)

0<?<)

Заметим, что формула (8), на самом деле, является принципом максимизации правдоподобия данной реализации Х = (х„ГеТ) относительно параметра Я-

Для поиска экстремума (7) продифференцируем функцию С(Х,<]) по д. После преобразований, получим:

9=1^1/(17-1-1). (9)

Если задана точная сегментация изображения, то на основе (9) можно непосредственно оценить значение диагонального элемента ц. Такая оценка дает истинное значение <?. Тем не менее, такая оценка не обеспечивает наилучшего качества работы базового алгоритма распознавания. Это объясняется тем, что базовый алгоритм был построен с целью корректировки результата независимого распознавания. На этапе независимого распознавания используется информация о наблюдениях и никакой информации об истинном значении марковского параметра не учитывается.

Более того, на практике учитель, как правило, частично указывает области классов для обучения. Тогда не будет хватать информации, чтобы непосредственно дать оценку диагонального элемента по (9).

Поэтому вместо точной сегментации, в данной работе предложено оценить значение по промежуточной сегментации, полученной при решении задачи (3).

Решение задачи (3) дает оценку скрытого поля Х(У) = (х,(К),/еГ), т.е. промежуточную сегментацию изображения. Тогда соответствующая оценка (¡{X) имеет следующий вид:

д(Х) = ащтах£(Х,я). (Ю)

0<9<|

Очевидно, решение задачи поиска диагонального элемента (10) заключается в итеративном решении двух взаимосвязанных задач: при фиксированных <7 и У решить задачу (3); при фиксированном X решить задачу (8).

Вырожденные свойства базового алгоритма

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

Свойство 1. Если значение диагонального элемента ц =\/т, то результат базового алгоритма полностью совпадает с независимым распознаванием.

Свойство 2. Если значение диагонального элемента ц = 1, то фильтрационное распределение на множестве классов для каждого элемента массива эквивалентно произведению маргинальных апостериорных распределений, восстановленных на этапе обучения для всех элементов массива, принадлежащих поддереву с корнем в данном элементе:

Р,{х, = 11 У;)ос П р,(х, = /1 у,), где «е П = {1,2,...,«}. (11)

геТ,'

Свойство 3. Если значение диагонального элемента ц = 1, то интерполяционное апостериорное распределение на множестве классов каждого элемента массива вычисляется по следующей формуле:

рДх, = / (Г) « П П А, =' I У„) ^ е е " - <12>

ГеГ/ ыеГ*

где Т°- множество предков элементов $ е Т, включая его самого, относительно корня /*.

Из (11) и (12) следует, что при д = 1 такая скрытая марковская модель является вырожденной и никак не влияет на качество результата распознавания. Результат распознавания полностью опирается на комбинации апостериорных распределений, полученных на этапе независимого обучения. Рассмотрим, например, цепь как частный случай ациклического графа соседства. Если распределения р!{х1 еТ,\1 еТ резко неравномерны (хорошее качество независимого обучения), то форма (11) начального распределения р,(хг = /\У*),1 = 1 и далее I > 1 поддерживается при х, = г на объектах этого же класса и немедленно начинает выравниваться при появлении серии отчетов другого класса

Если последовательность подряд идущих объектов другого класса х, * /' оказывается достаточно длинной, то распределения р,(х, =i\Y*) снова становятся резко неравномерными, но в пользу уже другого класса х, * / и т.д.

Если распределения р£х, |у.) более равномерны (плохое качество независимого обучения), то, в целом, они примерно и остаются такими же.

Аналогично можно описать характер изменения распределений Р,(х* ~»IП, согласно (12).

Таким образом, результаты распознавания при предельных значениях диагонального элемента (д = 11 ш и <у = 1) оказываются хуже, чем при промежуточных случаях когда 1 / ш < ^ < 1.

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

Алгоритм 1. Подбор диагонального элемента для ациклического графа, основанный на независимом обучении.

1. Выбрать ациклический граф соседства из заранее заданного набора.

2. Оценить д = | К, | /(| Т | -1), где V, = {и е Т(П | = х„ V е .

3. Однократным применением базового алгоритма распознавания с пересчитанным диагональным элементом перейти от распределений р,(х, |у(), полученных ранее для независимого обучения, к апостериорным распределениям р,(х, | е Т, соответствующим реализации X при наблюдении У.

4. Оценить д =| V, | /(| Т \ -1), где V, = {и е Т{П \ х„ = х„ V е 7^}.

5. Вновь применить алгоритм распознавания с пересчитанным диагональным элементом д, где вместо распределений р,(х, I >",) рассмотреть только что полученные распределения р, (х, | У), и перейти к новым апостериорным распределениям, которые снова обозначить как р,(х, I. Снова оценить диагональный элемент д.

6. Повторять шаг 5 до тех пор, пока решения о классах не перестанут меняться или начнут циклически повторяться.

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

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

1. Выбрать ациклический граф соседства из заранее заданного набора.

2. Варьировать значение д в диапазоне 1 / т < д < 1. Для каждого значения д применить базовый алгоритм итерационно до тех пор, пока число ошибок не перестанет изменяться, и оценить число ошибок,

3. Найти значение д, которое обеспечило минимальное число ошибок.

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

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

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

Алгоритм 1. Подбор единственного диагонального элемента и весов.

В этом алгоритме считается, что все ациклические марковские модели, соответствующие графам йк,к = \,...,К, определяются одним общим диагональным элементом д. Сначала все веса одинаковы и>* = {мл = 1 /К, г = 1,...,.£}.

1. Проварьируем д и найдем его значение при минимальном числе ошибок Е: д =аг£штЕ(и>',д).

2. Шаг варьирования весов по всем графам. Варьируется вес и^ очередного графа Ск в диапазоне О < м>к < 1 при масштабировании весов остальных графов. Каждое пробное варьирование проверяется многократным распознава-

нием с подсчетом числа ошибок E(w,q'). Для каждого графа Gk определим число ошибок и вектор весов w*k = (wl,...wk,...,wK):

Е'к = min E(w,q'), w*k = argminEO,^).

OiWjSl 05»! <1

3. Среди всех наборов w'k, к-1,...,К найдем набор w' = w'k., к' = arg min Е*к, обеспечивший наименьшее число ошибок.

\<к<К

4. Повторим шаги 1-3 до тех пор, пока число ошибок распознавания не перестанет изменяться.

Алгоритм 2. Первая схема подбора диагональных элементов и весов.

Каждому графу Gk,k = соответствует отдельная ациклическая мар-

ковская модель со своим диагональным элементом qk,k = \,...,K. Сначала все веса одинаковы н>' = {wi = 1 /К, i= 1,..., А"}.

1. Проварьируем одновременно все диагональные элементы qk=q,k = \,...,K и найдем значение q при минимальном числе ошибок Е - q =(?',...,?*) = argmin.£'(H>*,q).

\/m<q<\

2. Шаг варьирования весов по всем графам. Варьируется вес wk очередного графа Gk в диапазоне 0 < wk < 1 при масштабировании весов остальных графов. Каждое пробное варьирование проверяется многократным распознаванием с подсчетом числа ошибок E(w,q'). Для каждого графа Gk определим число ошибок и вектор весов w'k = (w1,...TVj,...,wJi):

E'k = min E(w,q'\ w'k =srgmiaE{w,q').

os»i£1 0<w4<J

3. Среди всех наборов w'k, k = \,...,K найдем набор w' = w*k,, k' = arg min E*k, обеспечивший наименьшее число ошибок.

1<*4ЛГ

4. Шаг варьирования всех диагональных элементов. В диапазоне 1 / т < qk < 1 варьируется диагональный элемент qk, соответствующий графу Gk. Остальным графам соответствуют элементы qt,i = \,...,K, i^k, найденные до варьирования qk, которые остаются постоянными. Найдем значение qk при минимальном числе ошибок: q'k = argmin^iw*, q).

1 tmSqk <1

Новое значение q'k применяется при варьировании остальных диагональных элементов qkH,qM,-,qK■ В итоге, получим оптимальный вектор q'.

5. Повторим шаги 2-4 до тех пор, пока число ошибок распознавания не перестанет изменяться.

Алгоритм 3. Вторая схема подбора диагональных элементов и весов.

Каждому графу Gk,k = \...K соответствует отдельная ациклическая марковская модель со своим диагональным элементом qk,k = 1..JC. Отличие от второго алгоритма заключается в порядке варьирования параметров. Здесь мы

варьируем вес каждого графа и потом сразу соответствующий ему диагональный элемент. Сначала все веса одинаковы и>* = {м>. = 1 / К, i = 1,...,К}.

1. Проварьируем одновременно все диагональные элементы qk=q,k = l,...,K и найдем значение q' при минимальном числе ошибок Е: q' =(q',...,q') = axgmmE(w',q) .

Ут<д<1

2. Шаг варьирования весов и диагональных элементов по всем графам. Варьируется вес wk очередного графа Gk в диапазоне 0 < wk < 1 при масштабировании весов остальных графов. Каждое пробное варьирование проверяется многократным распознаванием с подсчетом числа ошибок E{w,q ). Для каждого графа Gk определим число ошибок и вектор весов w"k =(w1,...wt,...,wJC):

E'k = min E(w,q'), w'k = argminE(w,q') .

Далее варьируется элемент qk, соответствуюхций графу Gk, в диапазоне m<qk<\. Остальным графам соответствуют элементы qt,i = \,...,K,i*k, найденные до варьирования qk, которые остаются постоянными. Найдем значение qk при минимальном числе ошибок: q\ = argminE(w*, q).

l/mlqk <1

Значение q'k определяет вектор q'k ={qx,...,q'k,...,qK).

3. Среди полученных пар (w"k,q'k),k-l,...,K найдем пару (w* ,q') = (wl„q'k,),k'=aigmmE(w'k,q'k), обеспечившую наименьшее число

l<k<K

ошибок.

4. Повторим шаги 2-3 до тех пор, пока число ошибок распознавания не перестанет изменяться.

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

■ дЛгяИм JH

Рис. 3. Пример текстуры и заданных сегментаций

Решалась задача сегментации 100 модельных растровых изображений (рис. 3) размером 201x201 пикселей. Текстуры трех классов были представлены реализациями трех нормально распределенных случайных величин с немного отличающимися средними в пространстве красной и зеленой компонент (на

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

Результаты независимого распознавания дают не менее 30% ошибок сегментирования поля растра.

Исследование алгоритмов подбора диагонального элемента для заданного ациклического графа

Сравнивались все алгоритмы подбора диагонального элемента для пяти видов ациклических графов соседства (см. рис. 2). Результат сравнения среднего числа ошибок распознавания на 100 изображениях приведен на рис. 4.

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

Баз. алг-т Баз. алг-т Баз. алг-т Баз. алг-т Баз. алг-т Подбор на Подбор Подбор Схема Г-3

4=0.7 q=0.9 с; 0.95 ц=0.99 ^=0.995 основе диа. ал-га, дна. эл-та,

незав. начиная с начиная с обучения 4=0.9 4=0.95

□ Ступен. Дерево В Спираль В Гориз. Змейка ИВерт.Змейка ИДиаг. Змейка

Рис. 4. Среднее число ошибок распознавания (%) Алгоритм по схеме Гаусса-Зайделя дает лучший результат и выигрывает у остальных алгоритмов. Оптимальное значение близко к единице (0.97-0.99).

В свою очередь, оптимальное значение диагонального элемента резко уменьшает число итераций (до одной-двух) базового алгоритма.

Исследование алгоритмов подбора параметров комбинирования ациклического графа соседства

Сравнивались четыре алгоритма подбора параметров комбинирования ациклических графов соседства (Г-3 - схема Гаусса-Зайделя поиска весов без поиска диагонального элемента, А1 - поиск единственного диагонального элемента и весов, А2 - первая схема поиска диагональных элементов и весов, АЗ -вторая схема поиска диагональных элементов и весов) и алгоритм Т1Ш^.

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

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

Рис. 5. Среднее число ошибок

Легко увидеть одинаковый характер линий ошибок для всех алгоритмов. Алгоритмы с подбором диагонального элемента резко улучшают качество распознавания по сравнению с алгоритмом без его подбора. Алгоритм ТЫ1^ не является однозначно лучшим, т.к. на части изображений он уступает по качеству распознавания.

Очевидно, что характер поведения таких кумулятивных характеристик изменяется с увеличением размера выборки, становясь более плавным. На рис. 5 видно, что алгоритм А1 систематически проигрывает по средней ошибке остальными алгоритмам. Тем не менее, на начальном участке видно, что на каждом отдельном изображении он может выигрывать в качестве, давая меньше число ошибок. Так и происходит: все сравниваемые алгоритмы (А1-АЗ, ТКЛУБ) достаточно часто уступали друг другу в качестве на различных отдельных изображениях.

В частности, при сравнении с алгоритмом ТИЛУв оказалось, что алгоритм А1 был лучше только в 35 случаях из 100, сделав суммарно на 1721 ошибку больше; алгоритм А2 был лучше уже в 55 случаях, сделав на 17 ошибок больше; алгоритм АЗ был лучше в 50 случаях, сделав на 43 ошибки больше.

В итоге, оказалось, что алгоритмы подбора параметров комбинирования ациклических графов соседства сравнимы по качеству между собой и с алгоритмом Т11\¥8, который сегодня считается одним из эффективных алгоритмов обработки изображений. Например, при уровнях значимости а = 0,001; 0,01; 0,05 гипотеза о равенстве среднего уровня ошибок алгоритмов подбора параметров комбинирования ациклических графов соседства (А1-АЗ) и ТИЛУЗ не отвергается.

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

Ниже в табл. 1 показаны параметры настройки алгоритмов на примере некоторых изображений из 100.

Таблица 1. Параметры настройки алгоритмов

зображе-ние А1 А2 АЗ

Веса Ч Веса ... а______ Веса Я

0,04282 0,03947 0,90 0,02000 0,75

0,20338 0,23684 0,89 0,09287 0,93

1 0.24000 0,86 0,25000 0.91 0,36836 0.92

0,25690 0,23684 0,90 0,25939 0,89

0,25690 0,23684 0,89 0,25939 0,89

0,16894 0,17000 0.89 0,16000 0,89

0,09034 0,17000 0,80 0,12643 0,89

2 0,18863 0,89 0,17000 0,90 0,20205 0,87

0.36209 0,32000 0,90 0,33540 0,88

0,19000 0,17000 0,91 0,17612 0,90

0,16486 0,46511 0,37 0,15000 «¿6

0,23356 0,13000 0,61 0,21329 0,89

52 0,23356 0,89 0,14111 0.90 0,21329 0,89

0,25000 0,14111 0,92 0,21329 0,89

0.П8ОЗ 0.12267 0,82 0,21012 0,94

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

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

Распознавание неподходящих изображений

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

Рис. 6. Неподходящие изображения: а) неэргодический случай; б) неравномерное финальное распределение; в) результаты распознавания

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

Применены разработанные алгоритмы комбинирования ациклических графов на таких изображениях. Результаты распознавания приведены на рис. 6в. Число ошибок распознавания составляет 1.745% для неэргодического случая и 1.789% для случая неравномерного финального распределения.

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

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

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

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

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

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

1. Исключить очередное изображение из заданной совокупности изображений и использовать его в качестве тестового.

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

3. С помощью полученного набора параметров распознать тестовое изображение.

4. Усреднить тестовую ошибку. Эта ошибка считается ошибкой распознавания на генеральной совокупности.

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

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

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

На рис. 7 видно, что по результатам скользящего контроля алгоритм подбора диагонального элемента на основе независимого обучения по-прежнему является наихудшим. Раньше по результатам распознавания на индивидуальных изображениях алгоритм подбора диагонального элемента по схеме Гаусса-Зайделя выиграл у всех остальных по качеству средней ошибки. Однако по ре-

зультатам скользящего контроля алгоритм по схеме Гаусса-Зайделя проигрывает алгоритму подбора, основанного на заданном значении диагонального элемента д = 0.95, хотя и немного.

Ступенч. дерево

О Подбор диаг. эл-та на основе незав. обучений □ Подбор диаг. эл-та, начинай с 4=0.9

I Подбор диаг. эл-та, начинал с 4-0.95

Спираль Горизонт. Вертик. змейиа Диаг. змейка

змейка □ Схема Г_3

Рис. 7. Ошибки распознавания на генеральной совокупности

Скользящий контроль для алгоритмов подбора параметров комбинирования ациклических графов соседства

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

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

Рис. 8. Ошибки распознавания на генеральной совокупности

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

В шестой главе выполнены эксперименты по обработке реальных изображений.

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

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

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

Эксперименты показывают, что наилучшим является набор параметров, полученных алгоритмом А2 на 52-ом изображении (см. табл. 1).

Примеры обработки реальных изображений показаны на рис. 9-10.

Рис. 9. Изображение «река-лес-небо»: а) исходное изображение; б) результат распознавания

Рис. 10. Изображение «человек»: а) исходное изображение; б) результат распознавания

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

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

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

3. Исследованы свойств ранее предложенного алгоритма подбора весов при комбинировании ациклических графов соседства.

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

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

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

Основные публикации по работе

1. Двоепко С.Д., Савенков Д. С., Шанг Д.В. Ациклические марковские модели в анализе массивов взаимосвязанных данных // Известия ТулГУ. Естественные науки. - Тула: ТулГУ, 2010. - Вып. 2.-С.173-185.

2. Двоенко С.Д., Шанг Д.В. Алгоритмы подбора параметров древовидного марковского случайного поля в задаче распознавания растровых текстурных иэобразкений // Известия ТулГУ. Естественные науки. - Тула: ТулГУ, 2012. -Вып. 1.-С. 98-109.

3. Двоенко СЛ., Шанг Д.В. Алгоритмы подбора параметров комбинирования ациклических графов соседства в задаче распознавания текстурных изображений // Известия ТулГУ. Технические науки. - Тула: ТулГУ, 2012. -Вып. 3. - С. 253-262.

4. Двоенко С.Д., Савенков Д.С., Шанг Д.В. Комбинирование ациклических графов соседства в задаче распознавания марковских случайных полей // Сборник докладов 14-ой конференции «Математические методы распознавания образов». -М.: МАКС Пресс, 2009. - С. 441^444.

5. Двоенко С.Д., Шанг Д.В. Параметрические ациклические марковские модели в задаче распознавания взаимосвязанных объектов // Сборник докладов 9-ой международной конференции «Интеллектуализация обработки информации». -М.: Торус Пресс, 2012. - С. 18-21.

6. Двоенко С.Д., Шанг Д.В. Распознавание растровых текстурных изображений на основе параметрических ациклических марковских полей // Труды 22-ой международной конференции по компьютерной графики и зрению «ГрафиКон-2012». -М.: МАКС Пресс, 2012. - С. 139-143.

7. Шанг Д.В. Алгоритмы подбора параметров комбинирования ациклических графов соседства в задаче распознавания текстурных изображений // Сборник докладов 21-ой конференции «Ломоносов - 2012» секции «Вычислительная математика и кибернетика». - М.: МАКС Пресс, 2012. - С. 20-21.

Подписано в печать 12.09.2013. Формат 60x84 1/16. Бумага офсетная. Усл. печ. л. 1,5. Тираж 100 экз. Заказ 040

Тульский государственный университет 300012, г. Тула, пр. Ленина, 92 Отпечатано в Издательстве ТулГУ 300012, г. Тула, пр. Ленина, 95

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Тульский государственный университет» Факультет Кибернетики Кафедра автоматики и телемеханики

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

04201362660

Динь Вьет Шанг

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

05.13.17 - Теоретические основы информатики

диссертация на соискание ученой степени кандидата технических наук

Тула, 2013

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ..................................................................................................................................4

1 ЗАДАЧА РАСПОЗНАВАНИЯ ОБРАЗОВ В МАССИВАХ ВЗАИМОСВЯЗАННЫХ ДАННЫХ.........8

1.1 Классическая задача распознавания образов...................................................8

1.2 Задача распознавания в массивах взаимосвязанных данных и минимизация среднего риска.........................................................................................................10

1.3 Распознавание образов в массивах взаимосвязанных данных в случае ациклического графа соседства.............................................................................19

1.4 Частная модель скрытого марковского случайного поля принадлежностей объектов к классам..................................................................................................22

1.5 Итерационный алгоритм повторения ациклического графа и комбинирование ациклических графов соседства.............................................................................26

1.6 Натуральные и структурные параметры модели в задаче выбора модели ..31

1.7 Минимизация гиббсовской энергии взаимодействия элементов марковского случайного поля.......................................................................................................35

1.8 Основные цели и задачи исследования...........................................................40

2 ЗАДАЧА ПОДБОРА ПАРАМЕТРОВ ДРЕВОВИДНОГО МАРКОВСКОГО СЛУЧАЙНОГО ПОЛЯ .................................................................................................................................................42

2.1 Постановка задачи подбора диагонального элемента в случае ациклического графа соседства.............................................................................42

2.2 Предельные значения диагонального элемента.............................................47

2.3 Алгоритм подбора диагонального элемента для ациклического графа,

основанный на независимом обучении..................................................................54

2.5 Алгоритм подбора диагонального элемента для ациклического графа по схеме Гаусса-Зайделя.............................................................................................55

3 ЗАДАЧА ПОДБОРА ПАРАМЕТРОВ КОМБИНИРОВАНИЯ АЦИКЛИЧЕСКИХ ГРАФОВ СОСЕДСТВА..............................................................................................................................57

3.1 Свойства алгоритма подбора весов ациклических графов в их линейной комбинации...............................................................................................................57

3.1.1 Предварительные эксперименты в случае однократного распознавания...........59

3.1.2 Предварительные эксперименты в случае многократного распознавания.........64

3.2 Алгоритмы подбора параметров комбинирования ациклических графов соседства..................................................................................................................68

3.2.1 Алгоритм подбора единственного диагонального элемента и весов ациклических

графов соседства............................................................................................................68

3.2.2 Первая схема подбора диагональных элементов и весов ациклических графов соседства.........................................................................................................................69

3.2.3 Вторая схема подбора диагональных элементов и весов ациклических графов соседства.........................................................................................................................71

3.2.4 Сходимость алгоритмов подбора параметров комбинирования ациклических графов соседства............................................................................................................72

4 ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ АЛГОРИТМОВ...................................................73

4.1 Модельные текстурные изображения..............................................................73

4.2 Сравнение алгоритмов подбора диагонального элемента для ациклического графа........................................................................................................................75

4.3 Зависимость скорости сходимости от значения диагонального элемента....84

4.4 Сравнение алгоритмов подбора параметров комбинирования ациклических графов соседства.....................................................................................................85

4.5 Проверка статистической гипотезы о равенстве средних уровня ошибок распознавания........................................................................................................100

4.6 Распознавание неподходящих изображений.................................................102

5 ОЦЕНКА ОШИБКИ РАСПОЗНАВАНИЯ МЕТОДОМ СКОЛЬЗЯЩЕГО КОНТРОЛЯ...............104

5.1 Упрощенная схема скользящего контроля.....................................................104

5.2 Алгоритмы подбора диагонального элемента по ациклическому графу.....107

5.3 Алгоритмы подбора параметров комбинирования ациклических графов соседства................................................................................................................108

6 РАСПОЗНАВАНИЕ РЕАЛЬНЫХ ИЗОБРАЖЕНИЙ.................................................................110

6.1 Интерактивная схема выбора данных учителя..............................................110

6.2 Схема независимого обучения с использованием информации о расположении объектов классов в поле носителя..............................................116

6.3 Сравнение алгоритмов при распознавании реальных изображении...........118

6.4 Обновление апостериорных маргинальных распределений........................120

6.5 Обработка изображений известных баз.........................................................139

ЗАКЛЮЧЕНИЕ........................................................................................................................145

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ........................................................................148

ПРИЛОЖЕНИЕ.......................................................................................................................153

ВВЕДЕНИЕ

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

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

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

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

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

В данной задаче необходимо принять решение о принадлежности каждой точки изображения к тому или иному классу текстуры. В классической теории распознавания образов [2, 16, 26] объекты, подлежащие распознаванию, рассматриваются независимо друг от друга. Поэтому в классической задаче распознавания, в частности, не делается никаких предположений о порядке предъявления объектов. Однако во многих задачах объектами, под-

4

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

Применение скрытых марковских моделей для изучения зависимых наблюдений показало их высокую эффективность при обработке массивов линейно упорядоченных объектов с цепочечной смежностью их элементов [15,42]. Однако применение данной идеи для отношений соседства произвольного вида выявило существенные теоретические и практически трудности. Для графов соседства общего вида, содержащих, как правило, циклы, задача распознавания марковских случайных полей является весьма трудоемкой [31, 37, 45, 49] и обладает свойствами задачи класса ИР. Поэтому в интеллектуальном анализе данных и машинном обучении в настоящее время интенсивно развивается область, получившая название графических моделей [21, 22, 32, 36, 37, 49-52] которые опираются на графы соседства элементов множества для построения эффективных алгоритмов обработки данных, в том числе и для изображений. В частности, если граф соседства является ациклическим, то ранее был предложен базовый алгоритм, выполняемый всего за два или три прохода по ациклическому графу [7, 8, 9].

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

5

тов. Чтобы уменьшить потери, связанные с древовидной аппроксимацией исходного графа соседства, в предыдущих работах был предложен алгоритм комбинирования ациклических графов, каждый из которых обладает коэффициентом важности, называемым его весом [11, 12]. Однако оказывается, что разные наборы весов ациклических графов дадут разные результаты распознавания. Для нахождения оптимальных весов графов был разработан алгоритм определения весов графов [12].

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

Однако это значение ранее задавалось эвристически без поиска его оптимального значения диагонального элемента.

В данной работе предложены алгоритмы подбора диагонального элемента для заданного ациклического графа и алгоритмы подбора параметров комбинирования ациклических графов соседства, т.е. алгоритмы подбора весов графов, дополненные подбором значения диагонального элемента. Цель данной работы - это разработка алгоритмов подбора диагонального элемента для ациклического графа и включение поиска значения диагонального элемента в схему Гаусса-Зайделя [3] при подборе весов графов.

Для достижения указанной цели в данной работе поставлены следующие задачи:

• сформулировать задачу подбора диагонального элемента;

• разработать алгоритмы подбора диагонального элемента для заданного ациклического графа;

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

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

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

Данная работа состоит из введения, шести глав и заключения.

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

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

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

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

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

В шестой главе выполнены эксперименты по обработке реальных изображений.

1 ЗАДАЧА РАСПОЗНАВАНИЯ ОБРАЗОВ В МАССИВАХ ВЗАИМОСВЯЗАННЫХ ДАННЫХ

1.1 Классическая задача распознавания образов

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

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

Образ - это описание любого объекта как представителя соответствующего класса образов [16]. Наиболее удобным математическим описанием объектов считается векторное описание. В этом случае каждому объекту г ставится в соответствие некоторый вектор признаков уг этого объекта, который является элементом векторного пространства у, е 0, определенного природой источника данных. Такое векторное пространство 0 называется пространством признаков. Как правило, это пространство является конечномерным и метрическим. Если признаки такого пространства являются вещественными величинами, то такое пространство изоморфно метрическому

8

пространству Ы", где п - размерность пространства признаков. Тогда вектор признаков имеет вид у, = (ух,у2>—,уп)т\?\- Выбор наиболее информативных признаков - это одна из основных и важных задач в теории распознавания образов [2]. Однако в данной работе эта проблема не рассматривается.

В [2] была введена математическая постановка задачи распознавания образов. Пусть Т - множество объектов. Отдельный объект из этого множества будем обозначать символом г. Каждый объект обладает своим вектором признаков у,, принимающим значения из пространства признаков 0, которое, чаще всего, является конечномерным и метрическим. Пусть Р: Т —» 0 -оператор, отображающий объект £ е Г в вектор признаков у, е 0 .

Предполагается, что на множестве объектов Т в данной задаче распознавания нас интересуют некоторые подмножества - классы. В классической задаче распознавания образов считается, что множество классов является конечным, и классы образуют полную группу подмножеств из множества объектов Т. В классической задаче рассматриваются обособленные объекты, каждый из которых объективно принадлежит к одному классу, и предъявляется для распознавания независимо от других объектов [8, 9]. В общем случае классов может быть и бесконечно много, и они могут составлять полную группу множеств. Задачу распознавания образов в этом случае называют обобщенной [2], и в данной работе она не рассматривается.

Пусть О. = {сох,со2,...,б)т} - это множество меток классов, где т - число классов. Как правило, метки классов понимаются как номера классов С1 = {1,2,...,т}. Классифицировать объект ¿еГ относительно классов с метками сох,сог,...,сот - это значит найти т.н. индикаторную функцию g :Т С1, которая ставит в соответствие