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




Скачать 66.59 Kb.
НазваниеЗадача заключается в восстановлении скрытого случайного поля классов объектов по реализации поля, например, на основе байесовского решающего правила в виде
Дата публикации10.09.2014
Размер66.59 Kb.
ТипЗадача
shkolnie.ru > Информатика > Задача




эффективное распознавание взаимосвязанных объектов на основе ацикличеСких марковских моделей1

Д. Савенков2, С. Двоенко2
2 Тульский государственный университет, 300600, Россия, Тула, пр. Ленина, 92,

DenisSavenkov@home.tula.net

dsd@uic.tula.ru

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

Введение

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

Скрытые марковские модели оказались очень эффективными для массивов линейно упорядоченных объектов с цепочечными графами соседства. Но возникают теоретические и практические трудности при их применении для массивов данных с произвольными графами соседства их элементов [1–3].

^ Древовидные марковские модели и процедура распознавания

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

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

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

.

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

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



.

Для решения данной задачи в случае, когда граф соседства является древовидным, т.е. ациклическим графом, и скрытое поле классов является марковским, была предложена эффективная процедура распознавания [4, 5].

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

,

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

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

Ациклическое представление решетчатого графа соседства

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

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

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

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

Возьмем некоторый граф из данного набора, например ступенчатое дерево (рис.1). Применим процедуру распознавания [4], описанную выше, и получим апостериорные распределения , на основе распределений в соответствии со скрытым полем и наблюдениями Далее, снова для того же графа соседства (или другого графа, например, для спирали на рис. 1), применим процедуру распознавания [4], взяв в качестве исходных только что вычисленные распределения вместо распределений , чтобы получить новые апостериорные распределения, которые снова обозначим как и т.д.
Ступенч. дерево Спираль Гориз. змейка



Верт. змейка Диаг. змейка

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

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

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


а б в



г д е



ж з и

Рис. 2. Результаты распознавания. Два цвета смешаны пропорционально апостериорным вероятностям классов:

a – классификация учителя,

б – независимое распознавание с 13548 ошибками,

в – ступенчатое дерево дважды с 2806 ошибками,

г – спираль дважды с 4605 ошибками,

д – горизонт. змейка трижды с 2966 ошибками,

е – верт. змейка дважды с 3024 ошибками,

ж – диаг. змейка дважды с 2769 ошибками,

з – однократное чередование всех графов с 987

ошибками,

и – повторение дважды комбинации всех графов с

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

Заключение

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

  1. Лебедев Д.С., Безрук A.A., Новиков В.M. Марковская вероятностная модель изображения и рисунка. М.: ИППИ АН СССР, 1983.

  2. Geman S., Geman D. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images// IEEE Trans. on PAMI. – 1984. Vol. 6. - P. 721-741.

  3. Li S.Z. Markov Random Field Modeling in Computer Vision. Springer-Verlag, 1995.

  4. Двоенко С.Д., Копылов А.В., Моттль В.В. Задача распознавания образов в массивах взаимосвязанных объектов. Постановка задачи и основные предположения// Автоматика и телемеханика. - 2004. – No 1. - C.143-158.

  5. Двоенко С.Д., Копылов А.В., Моттль В.В. Задача распознавания образов в массивах взаимосвязанных объектов. Алгоритм распознавания // Автоматика и телемеханика. - 2005. – No.12. - C.162-176.

  6. Mottl V.V., Dvoenko S.D., Levyant V.B., Muchnik I.B. Pattern recognition in spatial data: a new method of seismic explorations for oil and gas in crystalline basement rocks// Proc. 15th ICPR. – 2000. Vol. 3. – P. 210-213.

  7. Kittler J., Hatef E., Duin R.P. Combining classifiers// Proc. 13th ICPR. – 1996. Vol. 2. P. 897-901.

________________________________________________________________________

1Работа поддержана грантами INTAS 04-77-7347 и РФФИ 06-01-00412.

Похожие:

Задача заключается в восстановлении скрытого случайного поля классов объектов по реализации поля, например, на основе байесовского решающего правила в виде iconПравила пейтбольного тактического турнира стандарт поля 0 Все игровые...
На поле не должно быть участков или объектов (за исключением укрытий и коллекторов), затрудняющих свободное передвижение
Задача заключается в восстановлении скрытого случайного поля классов объектов по реализации поля, например, на основе байесовского решающего правила в виде iconКонтрольная работа по теме: «Теория поля»
Задача Найти производную скалярного поля по направлению нормали к поверхности в точке
Задача заключается в восстановлении скрытого случайного поля классов объектов по реализации поля, например, на основе байесовского решающего правила в виде iconИнструкция пользователя сайта
В открывшейся форме заполнить все поля, особое внимание необходимо обратить на поля, отмеченные красной точкой (поля, обязательные...
Задача заключается в восстановлении скрытого случайного поля классов объектов по реализации поля, например, на основе байесовского решающего правила в виде iconВедение
Обсуждается причина появления инерциальных свойств у электромагнитной массы. Делается вывод о том, что поля заряда и поля электромагнитных...
Задача заключается в восстановлении скрытого случайного поля классов объектов по реализации поля, например, на основе байесовского решающего правила в виде iconГипотеза о форме поля окружающего постоянный магнит или торсмагнитное поле
Гнетизма и магнитного поля в частности. Касается она, формы поля постоянного магнита, т е конфигурации поля, которое окружает постоянный...
Задача заключается в восстановлении скрытого случайного поля классов объектов по реализации поля, например, на основе байесовского решающего правила в виде iconЛабораторная работа №2 Программирование в Matcad, дополнительные возможности
Условный оператор if может использоваться для реализации достаточно сложных разветвляющихся алгоритмов в теле операторов цикла. Поэтому...
Задача заключается в восстановлении скрытого случайного поля классов объектов по реализации поля, например, на основе байесовского решающего правила в виде icon3. Расчеты экранирования
В этом случае расчет экранирования сводится к определению ослабления электрической либо магнитной составляющей поля. В дальней зоне...
Задача заключается в восстановлении скрытого случайного поля классов объектов по реализации поля, например, на основе байесовского решающего правила в виде iconГипотеза о форме поля окружающего постоянный магнит или торсмагнитное поле
Во второй части работы о магнетизме, я предлагаю рассмотреть известные явления природы, которые гармонично согласуются с гипотезой...
Задача заключается в восстановлении скрытого случайного поля классов объектов по реализации поля, например, на основе байесовского решающего правила в виде iconЗадача Используя теорему Гаусса, найдите напряженность электрического...
Кл/ Постройте график зависимости напряженности поля е от расстояния r до центра шара от рассматриваемой точки. Диэлектрическая проницаемость...
Задача заключается в восстановлении скрытого случайного поля классов объектов по реализации поля, например, на основе байесовского решающего правила в виде iconИсследование влияния формируемого пирамидой поля на материальные объекты введение
Ооо "Радиант" с целью разработки подхо­дов к систематическому изучению воздействия поля пирамидальных конструкций на материаль­ные...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
shkolnie.ru
Главная страница