WWW.PDF.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Разные материалы
 

«Алгоритмы подбора параметров древовидного марковского случайного поля в задаче распознавания растровых текстурных изображений С. Д. Двоенко, Д. В. Шанг ...»

Известия Тульского государственного университета

Естественные науки. 2012. Вып. 1. С. 98–110

Информатика

УДК 004.93

Алгоритмы подбора параметров

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

в задаче распознавания растровых

текстурных изображений

С. Д. Двоенко, Д. В. Шанг

Аннотация. Рассмотрена задача распознавания массивов

взаимосвязанных данных, представленных как двухкомпонентное

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

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

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

Ключевые слова: распознавание образов, машинное обучение, марковское случайное поле, марковская цепь.

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

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

Взаимосвязи между ними представлены графом соседства с ненаправленными * Работа выполнена при финансовой поддержке РФФИ (проекты № 10-07-00489, № 11-07-00634).

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

Скрытые марковские модели оказались эффективны при обработке линейно упорядоченных массивов с цепочечным соседством их элементов [1]. Но для графов соседства общего вида, содержащих, как правило, циклы, задача распознавания марковских случайных полей является весьма трудоемкой [2–5] и обладает свойствами задачи класса N P.

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

Марковская матрица условных вероятностей переходов является параметром предложенной в [6–9] модели. В [8, 9] было показано, что в частном случае такая матрица может быть задана только одним значением ее диагонального элемента. Но диагональный элемент задавался эвристически без поиска его оптимального значения.

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

1. Задача распознавания массивов взаимосвязанных данных и базовый алгоритм распознавания Пусть [6–9] массив взаимосвязанных данных T состоит из элементов t T и представлен как двухкомпонентное поле (X, Y ). Наблюдаемая компонента Y состоит из векторов yt, заданных на множестве элементов массива t T и принимающих значения из некоторого подходящего множества yt, определенного природой источника данных. Элементы xt, t T скрытой компоненты X принимают значения из некоторого множества xt, специфичного для конкретной задачи анализа данных. Например, для задачи распознавания образов = {1, 2,..., m} это конечное множество номеров классов объектов.

На множестве элементов t T массива данных определим симметричное антирефлексивное бинарное отношение, которое удобно представлять в виде неориентированного графа G без петель, ребра которого (s, t) G соединяют соседние элементы массива данных s T и t T.

Задачу обработки массива (X, Y ) представим как задачу преобразования исходного массива Y = (yt, t T ) в результирующий массив X = (xt, t T ).

Пусть |T | число элементов массива данных, тогда декартовы степени |T | и |T | образуют множества всех комбинаций значений исходных и результирующих (целевых) переменных, представляя все массивы данных и все результаты их обработки. Алгоритм обработки реализует преобразование 100 С. Д. Двоенко, Д. В. Шанг |T | |T | каждого исходного массива Y |T | в результат его анализа X(Y ) |T |.

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

В вероятностной задаче распознавания взаимосвязанных объектов предполагается, что двухкомпонентное поле (X, Y ) является случайным.

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

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

Пусть на множествах значений, |T | и, |T | переменных массивов X и Y определены соответствующие плотности распределения вероятностей. Пусть (X) априорное распределение вероятностей на множестве комбинаций целевых переменных, а их вероятностная связь с исходными переменными представлена условной плотностью (X|Y ), Y |T |. Задача обработки в общем случае сводится к численному определению апостериорного распределения вероятностей (X|Y ) = (X)(Y |X)/f (Y ) (X)(Y |X).

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

–  –  –

где pt (xt |Y ) апостериорное маргинальное распределение вероятностей скрытых классов в элементе массива t T.

Пусть граф соседства G не содержит циклов (рис.1), а скрытое поле классов X является марковским [6–9]. Тогда для элемента t T условное распределение qt xt |X(t) на множестве значений xt относительно остальных элементов X(t) = (xs, s T \t) зависит qt xt |X(t) = qt xt |X(t) только от значений соседних по графу G переменных X(t) = (xs, s T \t, (s, t) G).

Будем применять аналогичные обозначения относительно графа G для соответствующих подмножеств элементов наблюдаемого поля Y и массива T в целом.

Алгоритмы подбора параметров древовидного марковского случайного поля 101 Древовидный граф G разбивает окрестность (рис. 1а) нетерминального 0 +0 элемента xt на две произвольные части X(t) = X(t) X(t). Любая вершина t T в качестве корня немедленно задает естественный нисходящий порядок просмотра вершин от корня и восходящий порядок к корню, определяя окрестность X(t) = xr из одного элемента (рис. 1б), +0 предшествующего xt, и окрестность X(t) непосредственных потомков xt. В [8, 9] показано, что такое априорное случайное поле является односторонним марковским qt xt |X(t) = qt (xt |xr ).

Рис. 1. Ациклический граф соседства

Пусть поле Y = (yt, t T ) образовано случайными наблюдениями yt, условно независимыми относительно поля X = (xt, t T ), где t (yt |X) = = t (yt |xt ). В [8, 9] показано, что апостериорное скрытое поле относительно того же графа G остается односторонним марковским pt xt |X(t), Y = = pt xt |xr, Yt+, где Yt+ поддерево с корнем в yt, включая его.

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

Базовый алгоритм:

1. Задается корень t как начало обработки и априорное распределение qt (xt ), xt. Нисходящим просмотром для всех t T вычисляются априорные распределения классов qs (xs ) = qs (xs |xt ) qt (xt ), xs, s xt +0 T(t).

2. Восходящим просмотром от терминальных вершин к корню вычисляются фильтрационные апостериорные маргинальные распределения классов pt xt |Yt+ pt xt |Y(t) pt (xt |yt ), xt, t T, + 102 С. Д. Двоенко, Д. В. Шанг

–  –  –

2. Частная модель марковского случайного поля Марковское априорное случайного поле классов X определяет его одностороннее свойство в виде условных распределений вероятностей на множестве значений переменной xt относительно любой переменной xr X(t) из марковской окрестности xt. Для каждой пары вершин r, t G, соединенных ребром в дереве G, определена пара условных распределений вероятностей qt (xt |xr ) и qr (xr |xt ). Выбор некоторой вершины дерева G в качестве корня t T задает нисходящее и восходящее направления просмотра, объявляя одно из распределений нисходящим, а другое восходящим. В [6–9] был введен ряд предположений о такой модели марковского поля, в том числе следующие.

Предложение 1. Односторонняя марковская модель поля X является однородной конечной марковской цепью с неизменными условными распределениями в прямом (восходящем) и обратном (нисходящем) направлениях, где qr (xr |xt ) = q(xr |xt ), qt (xt |xr ) = q(xt |xr ); t, r T ; xt, xr.

Такая модель поля X полностью определена матрицами прямых Q(m m) и обратных Q(m m) условных вероятностей переходов.

Предложение 2. Односторонняя марковская модель случайного поля X является эргодической неразложимой марковской цепью и имеет финальное распределение p(x), x в корне t. Для неразложимой марковской цепи матрицы Q и Q связаны через финальное распределение Алгоритмы подбора параметров древовидного марковского случайного поля 103 вероятностей p(x), x : q(xt |xr ) = q(xr |xt )p(xt )/p(xr ). Очевидно, что в односторонней марковской модели начальное априорное маргинальное распределение вероятностей qt (xt ) можно задать в любой вершине t T, тогда соответствующие маргинальные распределения оказываются известными во всех остальных вершинах дерева G, в том числе и в его корне. Корень t естественно связать с началом обработки, а начальное распределение сделать корневым qt (xt ), xt.

Предложение 3. Априорное распределение классов в корне t является равномерным финальным распределением qt (xt ) = p(xt ) = 1/m.

Тогда маргинальные априорные распределения вероятностей скрытых классов во всех остальных объектах также равномерны. В этом случае q(xt |xr ) = q(xr |xt ). В итоге, остается только одна симметричная и дважды стохастичная матрица переходов Q. В частной модели [8, 9] предполагается, что матрица Q имеет одинаковые диагональные элементы и одинаковые недиагональные элементы. Тогда матрица Q задается только одним значением ее диагонального элемента q.

3. Задача поиска диагонального элемента В задаче классификации стремятся к поиску решающего правила, достигающего наименьшей средней вероятности ошибок. Ранее показано [6–9], что для массивов взаимосвязанных объектов минимизация уровня ошибок приводит к задаче максимизации совместной апостериорной вероятности (X|Y ) в целом или апостериорных вероятностей pt (xt |Y ), t T для отдельных элементов массива на основе байесовского решающего правила в виде (1) или (2).

Пусть наблюдаемое поле Y = (yt, t T ) образовано случайными векторами yt, условно независимыми t (yt |X) = t (yt |xt ) относительно скрытого поля X = (xt, t T ).

Тогда апостериорное скрытое поле классов формально определяется по следующей формуле:

–  –  –

4. Алгоритмы подбора значения диагонального элемента

Алгоритм 1. Подбор, основанный на независимом обучении (10):

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

2. Оценить q = |V1 |/(|T | 1), где V1 = {u T(t) |xu = xv, v T(u) }.

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

4. Оценить q = |V1 |/(|T | 1), где V1 = {u T(t) |xu = xv, v T(u) }.

5. Вновь применить алгоритм распознавания с пересчитанным диагональным элементом q, где вместо распределений pt (xt |yt ) рассмотреть только что полученные распределения pt (xt |Y ), и перейти к новым 106 С. Д. Двоенко, Д. В. Шанг апостериорным распределениям, которые снова обозначить как pt (xt |Y ), t T. Снова оценить диагональный элемент q.

6. Повторять шаг 5 до тех пор, пока решения x t = arg max pt (xt |Y ) не xt перестанут меняться или начнут циклически повторяться.

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

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

Алгоритм 3. Подбор диагонального элемента по схеме Гаусса-Зейделя.

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

Алгоритм состоит из шагов:

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

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

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

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

Сравнивались все алгоритмы распознавания для пяти видов ациклических графов соседства (рис.3). Результаты распознавания показаны в табл. 1–5.

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

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

В алгоритмах 1 и 2 фактически дважды пересчитывается диагональный элемент: из-за слияния областей и непосредственно по (10). Это быстро 108 С. Д. Двоенко, Д. В. Шанг увеличивает диагональный элемент и приводит к быстрому слиянию областей. Видно, что ускорение слияния областей отрицательно влияет на качество распознавания. Алгоритм по схеме Гаусса-Зейделя дает лучший результат и выигрывает у остальных алгоритмов. Оптимальное значение близко к единице (0.97-0.99).

–  –  –

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

Список литературы

1. Rabiner L.R. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition // Proc. IEEE, 77. 1977. V.2. P.257–286.

2. Geman S., Geman D. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images // IEEE Trans. on PAMI. 1984. V.6. P.721–741.

3. Li S.Z. Markov Random Field Modeling in Image Analysis. L: Springer–Verlag, 2009. 371 p.

4. Bishop C.M. Pattern Recognition and Machine Learning. N.Y.: Springer, 2006.

738 p.

5. Wainwright M.J., Jordan M.I. Graphical Models, Exponential Families, and Variational Inference // Foundations and Trends R in Machine Learning. 2008. V.1.

P.1–305.

6. Pattern Recognition in Spatial Data: A New Method of Seismic Explorations for Oil and Gas in Crystalline Basement Rocks / V.V. Mottl [et al.] // Proc. 15th ICPR’2000.

Spain, Barcelona, 2000. V.3. P.210–213.

7. Mottl V.V., Dvoenko S.D., and Kopylov A.V. Pattern Recognition in Interrelated Data: The Problem, Fundamental Assumptions, Recognition Algorithms // Proc.

17th ICPR’2004. Cambridge, England, UK, 2004. V.1. P.188–191.

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

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

10. Двоенко С.Д., Савенков Д.С., Шанг Д.В. Ациклические марковские модели в анализе массивов взаимосвязанных данных // Изв. ТулГУ. Естественные науки.

2010. Вып.2. С.173–185.

Двоенко Сергей Данилович (dsd@tsu.tula.ru, http://lda.tsu.tula.ru/sta.

html), д.ф.-м.н., профессор, кафедра автоматики и телемеханики, Тульский государственный университет.

Шанг Динь Вьет (dvietsang@gmail.com), аспирант, кафедра автоматики и телемеханики, Тульский государственный университет.

110 С. Д. Двоенко, Д. В. Шанг

–  –  –

Abstract. The recognition problem of interrelated data arrays represented as a two-component Markov random eld of observations and hidden object classes, for which the tree-like model of neighborhood elements of a hidden Markov random eld of the belonging of objects to classes was previously proposed, is under investigation. Model of hidden classes is considered as a Markov chain and is given by a matrix of conditional probabilities of transitions between its states. For a given acyclic adjacency graph of data array elements that matrix is the model parameter. It is shown that in the particular case it is sucient to determine only the value of the single diagonal element of the transition matrix.

Formulation of the problem to nd the optimal value of the diagonal element is given and the corresponding algorithms are developed. In the example of the problem of a segmentation of the raster textured images, the proposed algorithms are compared and results of experiments are shown.

Keywords: pattern recognition, machine learning, Markov random elds, Markov chain.

Dvoenko Sergey (dsd@tsu.tula.ru, http://lda.tsu.tula.ru/sta.html), doctor of physical and mathematical sciences, professor, department of automation and remote control, Tula State University.

Sang Dinh Viet (dvietsang@gmail.com), postgraduate student, department of automation and remote control, Tula State University.

–  –  –



Похожие работы:

«Том 7, №3 (май июнь 2015) Интернет-журнал «НАУКОВЕДЕНИЕ» publishing@naukovedenie.ru http://naukovedenie.ru Интернет-журнал «Науковедение» ISSN 2223-5167 http://naukovedenie.ru/ Том 7, №3 (2015) http://naukovedenie.ru/index.php?p=vol7-3 URL статьи: http://naukovedenie.ru/...»

«TNC 620 Руководствопользователя Программированиециклов Программное обеспечение с ЧПУ 817600-02 817601-02 817605-02 Русский (ru) 5/2015 Основные положения Основные положения О данном руководстве О данном руководстве Ниже приведен список символов-указаний, используемых в данном руково...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ УНИВЕРСИТЕТ ИТМО А. Ю. Щеглов МОДЕЛИ, МЕТОДЫ И СРЕДСТВА КОНТРОЛЯ ДОСТУПА К РЕСУРСАМ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ Учебное пособие Санкт-Петербург Щеглов А.Ю. Модели, методы и средства контроля доступа к...»

«Геоинформатика-2012 Т. 19. № 2. С. 29 39 УДК 519.2+550.34+681.3(04) Н.А.Сычева, Л.М. Богомолов, В.Н. Сычев В.Н. ГЕОИНФОРМАЦИОННЫЕ АСПЕКТЫ АНАЛИЗА ПОТОКОВ СЕЙСМИЧЕСКИХ И АКУСТОЭМИССИОННЫХ СОБЫТИЙ КАК РЕАЛИЗАЦИЙ СЛУЧАЙНЫХ ПРОЦЕССОВ На основе современных Case-те...»

«Выпуск 6 (25), ноябрь – декабрь 2014 Интернет-журнал «НАУКОВЕДЕНИЕ» publishing@naukovedenie.ru http://naukovedenie.ru Интернет-журнал «Науковедение» ISSN 2223-5167 http://naukovedenie.ru/ Выпуск 6 (25) 2014 ноябрь – декабрь http://naukovedenie.ru/index.php?p=issue-6-14 URL статьи:...»

«РАЗРАБОТКА МЕТОДИКИ АНАЛИЗА ЭФФЕКТА ЛОЖНОГО ОКОНТУРИВАНИЯ НА ИЗОБРАЖЕНИЯХ м.н.с. Насонов А.В.1, проф. Крылов А.С.1, асп. Черноморец А.А.1, проф. Динг Йонг2 Московский государственный университет имени М.В.Ломоносова Факультет вычислительной математики и кибернетик...»

«Министерство образования Республики Беларусь Учреждение образования «Белорусский государственный университет информатики и радиоэлектроники» Кафедра физического воспитания ТЕХНИКА И ТАКТИКА ИГРЫ ВРАТАРЯ В ГАНДБОЛЕ...»

«Министерство образования Республики Беларусь Учреждение образования «Белорусский государственный университет информатики и радиоэлектроники» Кафедра химии Забелина И. А., Молочко А. П., Соловей Н. П., Ясюкевич Л. В. ХИМИЯ ЛАБОРАТОРНЫЙ ПРАКТИ...»

«БЛ.СОВЕТОВ САЖОВЛЕВ Моделирование систем Издание третье, переработанное и дополненное Рекомендовано Министерством образования Российской Федерации в качестве учебника для студентов высших учебных заведений, обучающихся по направлениям «Инф...»

«МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОСТОВСКОЙ ОБЛАСТИ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ПРОФЕССИОНАЛЬНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ РОСТОВСКОЙ ОБЛАСТИ «РОСТОВСКИЙ-НА-ДОНУ КОЛЛЕДЖ СВЯЗИ И ИНФОРМАТИКИ» (ГБПОУ РО «РКСИ») ПРИКАЗ «17» августа 2016 № 110/ст Ростов-на-Дону Зачислить в число студентов государственного бюджетно...»





















 
2017 www.pdf.knigi-x.ru - «Бесплатная электронная библиотека - разные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.