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

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2018
Автори:	Водолазский, Е.В., Латюк, С.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2018
Назва видання:	Управляющие системы и машины
Теми:	Интеллектуальные информационные технологии и системы
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/144131
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Блочная модификация сэмплирования по Гиббсу для распознавания скрытых марковских полей / Е.В. Водолазский, С.А. Латюк // Управляющие системы и машины. — 2018. — № 2. — С. 31-41. — Бібліогр.: 5 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-144131
record_format	dspace
spelling	irk-123456789-1441312018-11-30T01:22:49Z Блочная модификация сэмплирования по Гиббсу для распознавания скрытых марковских полей Водолазский, Е.В. Латюк, С.А. Интеллектуальные информационные технологии и системы Исследовано применение сэмплирования по Гиббсу и его модификаций для распознавания скрытых марковских полей, а также конструктивный метод реализации его блочной модификации распознавания изображений для случая, когда блоками служат строки изображения. Предложено использование нового метода оценки математического ожидания для задач распознавания на структурах, разметки которых обладают марковским свойством. Мета статті — демонстрація існування конструктивної реалізації блочної модифікації семплування за Гібсом для розпізнавання зображень. Порівняння її роботи зі стандартною реалізацією та пошук текстур, на яких блочна модифікація працює краще. Перевірка придатності запропонованого методу оцінки математичного сподівання для використання при розпізнаванні прихованих марківських полів. Методи. Блочну модифікацію семплування за Гібсом для розпізнавання зображень побудовано на принципах динамічного програмування. Додаток, що дозволяє генерувати зображення заданої текстури, обирати потрібну модифікацію семплування за Гібсом розв’язку задачі розпізнавання та отримати графіки залежності швидкості розпізнавання кожного алгоритму від часу реалізовано на мові Python з використанням бібліотеки Cython для написання розширень на мові С. Результат. Виявлено, що блочна модифікація семплування за Гібсом на так званих «монотонних» текстурах при високому рівні шуму працює краще, ніж стандартний алгоритм. На «діагональних» текстурах, які дуже часто зустрічаються, блочна модифікація працює не гірше, ніж загальновідомий метод. Також виявлено, що на «монотонних» текстурах запропонований метод для оцінки математичного сподівання демонструє кращі результати, ніж загальноприйнятий. Purpose of this paper is to demonstrate that blocking Gibbs sampling can be constructively implemented for solving image recognition problems. Secondly, we want to compare blocking modification with standard algorithm and find types of the textures, on which blocking modification will give better results. And, finally, we want to test validity of the proposed method for estimation of expectation. Methods. Blocking modification of Gibbs sampling for image recognition is built on the principles of dynamic programming. Software that allows to generate images of the given texture, choose proper modification of Gibbs sampling for solving the problem and show graphs using Python and Cython. Results. 2018 Article Блочная модификация сэмплирования по Гиббсу для распознавания скрытых марковских полей / Е.В. Водолазский, С.А. Латюк // Управляющие системы и машины. — 2018. — № 2. — С. 31-41. — Бібліогр.: 5 назв. — рос. 0130-5395 DOI: https://doi.org/10.15407/usim.2018.02.031 http://dspace.nbuv.gov.ua/handle/123456789/144131 004.318 ru Управляющие системы и машины Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Интеллектуальные информационные технологии и системы Интеллектуальные информационные технологии и системы
spellingShingle	Интеллектуальные информационные технологии и системы Интеллектуальные информационные технологии и системы Водолазский, Е.В. Латюк, С.А. Блочная модификация сэмплирования по Гиббсу для распознавания скрытых марковских полей Управляющие системы и машины
description	Исследовано применение сэмплирования по Гиббсу и его модификаций для распознавания скрытых марковских полей, а также конструктивный метод реализации его блочной модификации распознавания изображений для случая, когда блоками служат строки изображения. Предложено использование нового метода оценки математического ожидания для задач распознавания на структурах, разметки которых обладают марковским свойством.
format	Article
author	Водолазский, Е.В. Латюк, С.А.
author_facet	Водолазский, Е.В. Латюк, С.А.
author_sort	Водолазский, Е.В.
title	Блочная модификация сэмплирования по Гиббсу для распознавания скрытых марковских полей
title_short	Блочная модификация сэмплирования по Гиббсу для распознавания скрытых марковских полей
title_full	Блочная модификация сэмплирования по Гиббсу для распознавания скрытых марковских полей
title_fullStr	Блочная модификация сэмплирования по Гиббсу для распознавания скрытых марковских полей
title_full_unstemmed	Блочная модификация сэмплирования по Гиббсу для распознавания скрытых марковских полей
title_sort	блочная модификация сэмплирования по гиббсу для распознавания скрытых марковских полей
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate	2018
topic_facet	Интеллектуальные информационные технологии и системы
url	http://dspace.nbuv.gov.ua/handle/123456789/144131
citation_txt	Блочная модификация сэмплирования по Гиббсу для распознавания скрытых марковских полей / Е.В. Водолазский, С.А. Латюк // Управляющие системы и машины. — 2018. — № 2. — С. 31-41. — Бібліогр.: 5 назв. — рос.
series	Управляющие системы и машины
work_keys_str_mv	AT vodolazskijev bločnaâmodifikaciâsémplirovaniâpogibbsudlâraspoznavaniâskrytyhmarkovskihpolej AT latûksa bločnaâmodifikaciâsémplirovaniâpogibbsudlâraspoznavaniâskrytyhmarkovskihpolej
first_indexed	2025-07-10T18:43:50Z
last_indexed	2025-07-10T18:43:50Z
_version_	1837286594989522944
fulltext	ISSN 0130-5395, УСиМ, 2018, № 2 31 DOI https://doi.org/10.15407/usim.2018.02.031 УДК 519.245. Е.В. ВОДОЛАЗСКИЙ, ст. научн. сотр., waterlaz@gmail.com С.А. ЛАТЮК, инж.-програм. I кат., serhiylatyuk55@gmail.com Международный научно-учебный центр информационных технологий и систем НАН Украины и МОН Украины, просп. Глушкова, 40, Киев 03187, Украина БЛОЧНАЯ МОДИФИКАЦИЯ СЭМПЛИРОВАНИЯ ПО ГИББСУ ДЛЯ РАСПОЗНАВАНИЯ СКРЫТЫХ МАРКОВСКИХ ПОЛЕЙ Исследовано применение сэмплирования по Ãиббсó и еãо модифиêаций для распознавания сêрытых марêовсêих полей, а таêже êонстрóêтивный метод реализации еãо блочной модифиêации распознавания изображений для слóчая, êоãда блоêами слóжат строêи изображения. Предложено использование новоãо метода оценêи математичесêоãо ожида- ния для задач распознавания на стрóêтóрах, разметêи êоторых обладают марêовсêим свойством. Êлючевые слова: сэмплирование по Ãиббсó, ãиббсовсêий самплер, задачи разметêи, распознавание сêрытых марêов- сêих полей. Введение Статья посвящена демонстрации блочной мо- дифиêации сэмплирования по Ãиббсó [1] и может быть êонстрóêтивно реализована и применена при решении задач распознавания изображений, в частности для решения задач разметêи [2], ê êоторым сводятся неêоторые задачи êомпьютерноãо зрения. Известно, что задачи разметêи заêлючаются в оптимизации фóнêций от большоãо êоличества дисêретных арãóментов. Специфиêа их заêлючается в том, что фóнêция, êоторóю необходимо оптимизи- ровать, есть сóммой большоãо êоличества сла- ãаемых, êаждое из êоторых зависит от неболь- шоãо êоличества переменных. Множество подобных задач образóет NP-пол- ный êласс, а известные полиномиально раз- решимые подêлассы [2—4] вêлючают в себя далеêо не все ситóации, возниêающие на праêтиêе. Поэтомó появляется необходимость исследовать таêже неточные методы решения подобноãо рода задач, один из êоторых — сэмп- лирование по Ãиббсó [1]. Сэмплирование óместно применять не во всех задачах распознавания, но при неêото- рых фóнêциях штрафа оно может быть ис- пользовано для статистичесêоãо оценивания определенных величин. Определение основных понятий Пóсть T — множество объеêтов; например, множество пиêселов поля зрения. Отдельный объеêт из T обозначим t или t'. На множестве Т задано подмножество   T  T пар объеê- тов, êоторое назовем отношением соседства. Элементы множества  обозначим (t, t'). Вы- Е.В. Водолазсêий, С.А. Латюê 32 ISSN 0130-5395, Control systems and computers, 2018, № 2 ражение (t, t')   óêазывает, что объеêты t и t' соседние. В дальнейшем для êратêости (t, t') бóдем записывать êаê tt'. Пóсть K — êонечное множество, элементы êотороãо назовем метêами, а отдельнóю метêó обозначим k. Для êаждоãо объеêта t и êаждой метêи k задано число qt(k), а для êаждой пары объеêтов tt' и пары метоê k и k' — число gtt'(k, k'). Эти числа назовем весами. Объеêт вместе с соответствóющей емó метêой назовем вершиной и обозначим (k, t). Парó вершин, в êоторóю входят соседние объеêты назовем дóжêой и обозначим ((k, t), (k', t')). Разметêой назовем фóнêцию kT : T → K, êо- торая для êаждоãо объеêта t T óêазывает мет- êó kT(t) K. Иноãда для êратêости метêó в объ- еêте ti вместо kT(ti) бóдем обозначать ki . Набор метоê, соответствóющий неêоторой ãрóппе объеêтов   T, обозначим kT(). Вес разметêи определяется êаê сóмма весов вершин и дó- жеê, êоторые в нее входят:           T tt' T T t T tt' t T G k = g k t ,k t' + q k t .      Задача (max, +)-разметêи — это поисê раз- метêи с маêсимальным весом:  * arg max . T T T T k K k G k   Марковская модель изображения Таêая модель изображения может быть леãêо выражена в терминах понятий, введенных ра- нее. Пóсть дано изображение размером m на n. Множеством пиêселов назовем множество объ- еêтов (i, j) таêих, что 1 ≤ i ≤ m, 1 ≤ j ≤ n. Для êаж- доãо пиêсела (i, j) определим множество N(i, j) соседних пиêселов, N(i, j) = {(i –1, j), (i +1, j), (i, j –1), (i, j +1)}. Определим таêже два типа ве- совых фóнêций: gВ(kT(t), kT'(t')) = gtt' (kT(t), kT' (t')), êоторые на êаждой êонêретной паре метоê k, k' для всех пар объеêтов tt' вида (i, j), (i +1, j) принимают одни и те же значения и gÃ(kT(t), kT' (t')) = gtt' (kT(t), kT' (t')), обладающие анало- ãичным свойством для всех пар объеêтов вида (i, j), (i, j +1). Вероятность разметêи для неêотороãо множе- ства пиêселов определяется таê:        1 2 1 1, , , n m В T T T j= i= p k = g k i j k i j Z               1 2 , 1 , , , m n Г T T i= j= g k i j k i j          ãде Z — неêоторый нормирóющий множитель. Пóсть помимо метêи, в êаждом пиêселе за- дан сиãнал x(i, j)  X. Совоêóпность сиãналов во всех пиêселах назовем изображением и обо- значим xT . Óсловнóю вероятность сиãнала xT(i, j) в пиêселе (i, j) при заданном значении kT(i, j) метêи обозначим q(xT(i, j) \| kT(i, j)). Веро- ятность изображения xT при óсловии заданной разметêи kT может быть вычислена êаê         , ,T T T T i, j T p x \|k = q x i j \| k i j .   Распознавание скрытых марковских полей Пóсть êаждый объеêт t T, имея метêó kT(t)K, с вероятностью q(xT(i, j) \| kT(i, j)) излóчает сиã- нал xT(t)  X. Óсловные вероятности q(x \| k) сиãнала x при фиêсированном значении мет- êи k одинаêовы для всех объеêтов. Задачó распознавания можно сформóлировать таê: дана ãрóппа объеêтов T, êоторые излóчают сиãналы xT(t)  X. Требóется, имея совоêóп- ность сиãналов xT , фóнêции gtt'(kT(t), kT' (t')) и óсловные вероятности q(xT(t) \| kT(t)), принять целесообразное, в определенном смысле, ре- шение о метêах kT(t) K этих объеêтов. Одной из наиболее распространенных фор- мализаций этоãо требования есть поисê апо- стериори наиболее вероятной разметêи (MAP- оценêа):  arg max* T T T T k k = k \| x . Но даже при таêой постановêе задача в об- щем слóчае — NP-сложная. Полиномиальный алãоритм сóществóет тольêо для неêоторых подêлассов марêовсêих сетей, например, êо- ãда стрóêтóра имеет древовиднóю формó [2] либо при метêах, óдовлетворяющих óсловию сóпермодóлярности [3, 4]. Однаêо, êаê известно [5], поисê апостерио- ри наиболее вероятной разметêи — это лишь Блочная модифиêация сэмплирования по Ãиббсó для распознавания сêрытых марêовсêих полей ISSN 0130-5395, УСиМ, 2018, № 2 33 частный слóчай решения задачи минимиза- ции байесовсêоãо рисêа (1):    arg min* * , T T T T T k ' TkT k = p k W k k ' K    (1) при фóнêции потерь, êоторая одинаêово штра- фóет решение, вне зависимости от êоличества неправильно распознанных пиêселов:     T T T T T T T T W k k ' = k k '. W k k ' = k k .   , 0, если , 1, если (2) Для неêоторых задач (например сеãмента- ции или восстановления изображения в óсло- виях шóма) более óдобной штрафной фóнêци- ей есть не вероятность решения в целом (2), а математичесêое ожидание êоличества непра- вильно распознанных пиêселов (таê называе- мая аддитивная фóнêция штрафа). В этом слóчае она имеет следóющий вид:       , ,T T T T t T W k k ' = w k t k ' t   , ãде         T T T Tw k t k ' t = k t = k ' t, 0, если ,     T Tw k t k ' t = ., 1, иначе Известно, что в этом слóчае решение    arg min , T T T T T T k ' kT k ' = p k \| x W k k ' распадается на \|T\| независимых оптимизаций вида      arg min arg max, ,T T k' kk k' = p x k w k k' = p k \| x . Теперь проблема поисêа оптимóма êаê та- êовая отпадает, но вместо нее появляется дрó- ãая — вычисления необходимых марãиналь- ных вероятностей. Точное вычисление этих величин в общем слóчае представляет собой NP-сложнóю задачó. Поэтомó использóются различные приближенные методы, об одном из êоторых пойдет речь далее. Сэмплирование по Гиббсу Этот метод, в отличие от дрóãих, хорошо мас- штабирóется и, следовательно, может эффеê- тивно фóнêционировать на пространствах с очень высоêой размерностью. Идея, поло- женная в еãо основó — разбить сэмплирова- ние из совместноãо распределения, — трóдно выполнима:         1 2, ,...,T T T T Tp k = p k t k t k t , на неêоторое êоличество сэмплирований из óсловных распределений, êоторые выполнить леãêо           1 1 1,..., , ,...,T i T T i T i+ T Tp k t \| k t k t k t k t . Алãоритм выãлядит таê:  óстановить начальные значения для всех метоê (например на основе неêотороãо апри- орноãо распределения);  заданное êоличество раз выполнить сле- дóющее: – сãенерировать новое значение для k(t1) при óсловии теêóщих значений всех осталь- ных метоê: kT(t1) new ~ p(kT(t1) \| kT(t2) … kT(t\|T\|)); – сãенерировать новое значение для k(t2) при óсловии теêóщих значений всех осталь- ных метоê (с óчетом новоãо значения k(t1)): kT(t2) new ~ p(kT(t2) \| kT(t1) new, kT(t3) … kT(t\|T\|)); … – kT(ti) new ~ p(kT(ti) \| kT(t1) new … kT(ti–1) new, kT(ti+1) … kT(t\|T\|)); … – kT(t\|T\|) new ~ p(kT(t\|T\|) \| kT(t1) new … kT(t\|T\|–1) new). Рис. 1. Попиêсельное сэмплирование Е.В. Водолазсêий, С.А. Латюê 34 ISSN 0130-5395, Control systems and computers, 2018, № 2 В силó марêовсêоãо свойства ãиббсовых слóчайных полей óсловное распределение од- ной метêи при фиêсированных значениях всех остальных метоê равно ее óсловномó рас- пределению при фиêсированных соседних метêах (для изображения m на n пиêселов), в чем и состоит эффеêтивность сэмплирования (рис. 1):                     T T T T T T T T T T p k i j \| k k i j k i j + k m,n p k i j \| k i j k i + j k i j k i j + .     , 1,1 ,..., , 1 , , 1 ,... ..., , 1, , 1, , , 1 , , 1 В частности при распознавании изображе- ний êаждый пиêсел имеет всеãо лишь четыре соседа. Дрóãим известным вариантом сэмплирова- ния по Ãиббсó есть таê называемое блочное сэмплирование. Еãо отличие от предыдóщеãо метода состоит в том, что на êаждом шаãе ãе- нерирóется значение метоê сразó для ãрóппы или блоêа объеêтов. Алãоритм приобретает следóющий вид:  óстановить начальные значения для метоê объеêтов во всех блоêах (предположим, что со- воêóпность всех объеêтов разбита на n блоêов);  заданное êоличество раз выполнить сле- дóющее: – сãенерировать новые значения kT(1) для блоêа 1 при óсловии теêóщих значений метоê во всех остальных блоêах: kT(1 ) new ~ p(kT(1 ) \| kT(2) … kT(n)); – сãенерировать новые значения для kT(2) при óсловии теêóщих значений метоê во всех остальных блоêах (с óчетом новых значений kT(1)): kT(2 ) new ~ p(kT(2 ) \| kT(1) new, kT(3) … kT(n)); … – kT(i) new ~ p(kT(i) \| kT(1) new … kT(i–1) new, kT(i+1) … kT(n)); … – kT(n) new ~ p(kT(n) \| kT(1) new … kT(n–1) new). Блочная модификация сэмплирования по Гиббсу для распознавания изображений Таêая модифиêация — воплощение попытêи óсêорить сходимость óже имеющеãося метода. Посêольêó две последовательно полóченные разметêи отличаются тольêо значениями мет- êи в одном объеêте, то исследование всеãо пространства разметоê осóществляется с до- вольно низêой сêоростью. Решением этой проблемы моãла бы быть возможность изме- нять на êаждом шаãе метêó не в одном пиêсе- ле, а в ãрóппе пиêселов. Это позволит алãо- ритмó на êаждом шаãе перепрыãивать на менее похожóю разметêó и тем самым совершить блóждание по более широêой области. Вариант блочной модифиêации, êоторый предлаãают авторы, модифицирóет изображе- ние построчно. Он возниê из идеи, что если бы изображение состояло всеãо из одной строêи, то ниêаêое сэмплирование не понадобилось бы. В силó ациêличности имеющейся стрóêтóры мож- но было бы вычислить все интересóющие веро- ятности за полиномиальное время [2]. Хотя в общем слóчае имеется ãораздо больше строê, чем одна, êоторые зависимы одна от дрóãой, ãенерация новых метоê в целой строêе, а не в одном пиêселе все же моãла бы оêазаться эф- феêтивнее. Рис. 2. Построчное сэмплирование Блочная модифиêация сэмплирования по Ãиббсó для распознавания сêрытых марêовсêих полей ISSN 0130-5395, УСиМ, 2018, № 2 35 Пóсть kT(i, j) обозначает метêó в пиêселе, êоторый находится в i-й строêе и j-м столбце. И пóсть изображение, предоставленное для распознавания, имеет размер m на n пиêселов. Одна итерация семплирования в этом слóчае выãлядит таê:  kT(1, 1)new … kT(1, n)new ~ p(kT(1, 1) … … kT(1, n) \| kT(2, 1) … kT(2, n));  kT(2, 1)new … kT(2, n)new ~ p(kT(2, 1) … … kT(2, n) \| kT(1, 1)new…kT(1, n)new, kT(3, 1)…kT(3, n)); …  kT(i, 1)new…kT(i, n)new ~ p(kT(i, 1)… … kT(i, n) \| kT(i –1, 1)new…kT(i –1, n)new, kT(i +1, 1)… … kT(i +1, n)); …  kT(m, 1)new … kT(m, n)new ~ p(kT(m, 1) … … kT(m, n) \| kT(m –1, 1)new … kT(m –1, n)new). Отметим, что самое сóщественное при вы- боре блоêов таêой формы, блочное сэмплиро- вание по Ãиббсó имеет êонстрóêтивнóю реа- лизацию, одна итерация êоторой, может быть выполнена за полиномиальное время. Это можно óвидеть, выполнив следóющее: выразим совместное распределение полó- ченноãо изображения и предполаãаемой раз- метêи в виде произведения сомножителей, зависящих от êонêретной строêи i* этоãо изо- бражения и тех, êоторые от нее не зависят:        1 2 1 1, n m В T T T T j= i= p k ,x = g k i j ,k i, j Z               1 2 1 m n Г T T i= j= g k i, j ,k i, j                1 1 = m n T T i= j= q x i, j \| k i, j      , 1 1 2 * * 1 = 1, , , n n B T T j= i= i i i g k i j k i j Z                     1 2 * , 1 , , m n Г T T i j= i i g k i j k i j                  1 1 * , , m n T T i j= i i q x i j \| k i j                         n В T T j= В T T n Г T T j= n T T j= g k i j k i j g k i j k i + j g k i j k i j q x i , j \| k i , j             * * 1 * * * * 2 * * 1 1, , , , , 1, , 1 , , . Введем обозначение:                   1 * * * * * * * , , , 1, , , , , 1, j T T T В T T В T T q k i j = q x i j \| k i j g k i j k i j g k i j k i + j .      Теперь óсловное распределение метоê и сиãналов, соответствóющих пиêселам строêи изображения, может быть выражено таê:              * * * * * 1 * 2 1 1 , 1 , , , , T T T n n Г T T j T j= j= p k i ,x \| k ¬i g k i j k i j q k i j Z      ãде   1 ,j Tq k i j можно записать êаê   1 j Tq k j , посêольêó значение i фиêсировано. Введем две вспомоãательные фóнêции:       * 1 2 * 1 * * * 1 1 1 2 1 ... , j j f j j j Г j j j j k k k j= j= k = g k ,k q k                       * * 1 2 * 1 * 1 1 * 1 ... , j + j + j +n Гf j j jj k k k j= j + j j j= j + n k = g k ,k n q k               значения êоторых пропорциональны марãи- нальным вероятностям метêи kT(j) в объеêте (i, j). Леãêо поêазать, что        1 1 1 1, , j Гf fj+ jj+ j j+ j j j k k = g k k q k k    Е.В. Водолазсêий, С.А. Латюê 36 ISSN 0130-5395, Control systems and computers, 2018, № 2        1 11 1 1 1 1 , ,Гf fj j+j j j+ j+ j+ j+ k j+ k = g k k q k k    а таêже, что             1 11 1 1 1 1 1 1 f jj j j j j Г f jj j j j j p k ,k = k q k Z g k ,k q k k .             Таêим образом, новые значения метоê для строêи изображения моãóт быть сãенерирова- ны за время порядêа O(n\|K\|2). Оценка апостериорных вероятностей меток Êаê отмечено ранее, в слóчае минимизации êоличества неправильно распознанных объ- еêтов, задача разметêи распадается на сово- êóпность независимых оптимизаций по êаж- домó объеêтó. Êаждая из них заêлючается в поисêе метêи с маêсимальной апостериорной вероятностью. Посредством сэмплирования по Ãиббсó можно приближенно оценить эти ве- роятности, рассматривая их êаê математиче- сêие ожидания. Пóсть дана фóнêция → êоторая êаждой разметêе ставит в соответ- ствие неêоторое число. Математичесêое ожи- дание значения фóнêции обозначим      θ T T TkT = p k k . K      Из lim p=pt t  следóет, что        lim * θ n n T T t T T T T t k K k K p k k = p k k = .        Еще один, менее распространенный способ вычисления математичесêоãо ожидания — это предел среднеãо значения фóнêции  на пер- вых  разметêах:  lim 1 0 1 θ τ τ t T τ t= k = .    Проблема заêлючается в том, что приве- денное равенство выполняется тольêо в слó- чае независимых разметоê. О еãо выполне- нии или невыполнении в дрóãих слóчаях ни- чеãо не известно. Но, тем не менее, в слóчае марêовсêой зависимости (êаê в данной си- тóации), разметêи можно считать независи- мыми, если брать êаждóю n-ю (ãде n — доста- точно большое число), отбрасывая при этом все остальные. Марãинальные вероятности метêи k в пиêселе ti (далее pi(k)), вычисление êоторых необходимо для решения задачи распозна- вания, можно рассматривать êаê математи- чесêие ожидания значения неêоторой фóнê- ции, равной единице в слóчае метêи a в пиêселе i и равна нóлю во всех остальных слóчаях:    * 1 1 1 1 ,..., ,..., ,..., , ,..., i n k k ki i+ n p a = p k a k . k  Точное вычисление математичесêоãо ожи- дания в данном слóчае невозможно вследст- вие эêспоненциально большоãо êоличества возможных разметоê. Но можно попытаться оценить еãо приближенно, ãенерирóя доста- точно большóю выборêó из распределения вероятностей разметоê. Первый метод назовем подсчет. Он заêлю- чается в том, чтобы подсчитать все разметêи из сãенерированной выборêи, в êоторых пиê- сел имеет êаêóю-то определеннóю метêó, на- пример a. Затем разделить это êоличество на размер выборêи и полóченное число считать вероятностью тоãо, что данный пиêсел имеет метêó a:     m i T i t= p a k t = a m     1 1 . Второй метод назовем óсреднением. Ãлавная еãо идея в том, чтобы рассматривать вероят- ность присóтствия в пиêселе неêоторой метêи a, êаê математичесêоãо ожидания апостери- орной вероятности тоãо, что данный пиêсел имеет метêó а, при óсловии излóчения сиãнала x. Математичесêое ожидание в свою очередь, êаê известно, можно аппроêсимировать сред- ним значением:      i x X p a = p x p a \| x   ≃   m t t= p a \| x . m1 1 Блочная модифиêация сэмплирования по Ãиббсó для распознавания сêрытых марêовсêих полей ISSN 0130-5395, УСиМ, 2018, № 2 37 Экспериментальное сравнение четырех вариантов реализации Итаê, имеем четыре возможных варианта реа- лизации сэмплирования по Ãиббсó:  попиêсельный с подсчетом;  попиêсельный с óсреднением;  блочная модифиêация с подсчетом;  блочная модифиêация с óсреднением. В êачестве задачи распознавания, êоторая решалась перечисленными алãоритмами, для простоты была выбрана задача восстановле- ния зашóмленноãо изображения. Выполнена следóющая процедóра:  сãенерировано изображение с неêоторы- ми теêстóрными хараêтеристиêами, на êото- ром поêазано неêоторое êоличество цветов (в данном слóчае цвет — это метêа);  êаждый пиêсел с неêоторой фиêсирован- ной вероятностью меняет свой цвет на дрóãой, выбранный слóчайно цвет;  полóченное изображение подается на вход для распознавания êаждомó из четырех алãо- ритмов. Теоретичесêи, все четыре метода должны сходиться ê одномó и томó же резóльтатó (но не обязательно с одинаêовой сêоростью). Тестирование проведено для разных óров- ней шóма (0,4—0,9) и разноãо êоличества ме- тоê (3—8) на двóх типах теêстóр: таê называе- мых диаãональных и монотонных теêстóрах. Диаãональные теêстóры хараêтерны тем, что для соседних пиêселов (êаê по ãоризонтали, таê и по вертиêали) вероятность появления в них одинаêовых метоê намноãо больше, чем разных (рис. 3). Жирным на рисóнêе обозна- чены пары метоê, êоторые возниêают с высо- êой вероятностью, тонêим — с низêой. Типич- ная теêстóра с таêой матрицей весов выãлядит êаê совоêóпность оêрóãлых пятен (рис. 4). На теêстóрах этоãо типа óлóчшений в рабо- те блочной модифиêации в сравнении с по- пиêсельным алãоритмом не наблюдалось. Монотонные теêстóры хараêтерны тем, что метêи всеãда моãóт быть пронóмерованы таê, чтобы в êаждой строêе и êаждом столбце их номера слева направо и сверхó вниз не óмень- шались (т. е. были расположены по неóбыва- нию) (рис. 5). Типичная теêстóра с таêими свойствами выãлядит êаê два больших треóãольных пятна в левом верхнем и правом нижнем óãлах и два тонêих продолãоватых диаãональных пятна по центрó (рис. 6). На этом типе теêстóр óдалось достичь неêо- торых интересных резóльтатов. Хотя при ма- лом óровне шóма все четыре метода ведóт себя Рис. 3. Схематичесêое изображение отношений междó вероятностями различных пар метоê на двóх соседних пиêселах для диаãональных теêстóр Рис. 4. Пример диаãональной теêстóры Рис. 5. Схематичесêое изображение отношений междó вероятностями различных пар метоê на двóх соседних пиêселах для монотонных теêстóр Рис. 6. Монотонная теêстóра Е.В. Водолазсêий, С.А. Латюê 38 ISSN 0130-5395, Control systems and computers, 2018, № 2 почти одинаêово, при еãо повышении блоч- ные модифиêации начинают сходиться быст- рее. Отметим, что именно для блочной моди- фиêации метод óсреднения для оценêи мар- ãинальных вероятностей работает лóчше, в то время êаê для попиêсельной реализации таêо- ãо не наблюдается. Результаты сравнения работы алгоритмов Очевидно, что время выполнения одной ите- рации сэмплирования êлассичесêим алãорит- мом меньше, чем посредством блочной мо- дифиêации. Это обóсловлено тем, что ассим- птотичесêая сложность попиêсельноãо сэм- плирования — О(n\|K\|) в то время êаê блочной модифиêации — О(n\|K\|2). Но, тем не менее, для малоãо êоличества метоê (восемь и мень- ше) на монотонных теêстóрах блочная моди- фиêация сходится быстрее, что сêорее всеãо происходит из-за возможности óчитывать за- висимости междó метêами пиêселов одной строêи, находящиеся далеêо одна от дрóãой. Насêольêо сильно эти зависимости влияют на сêорость распознавания в общем слóчае, поêа сêазать трóдно, что ãоворит о необходимости дальнейших исследований в этой области. Ниже представлены ãрафиêи зависимости êачества распознавания, демонстрирóемоãо алãоритмами, от времени их работы. По ãори- зонтальной оси — время в сеêóндах, по верти- êали — êоличество неправильно распознан- ных пиêселов. Рис. 7. Распознавание на диаãональных теêстóрах На рис. 7 поêазано распознавание на диа- ãональных теêстóрах при различном óровне шóма и êоличестве метоê, êоторое проводится одинаêово êаê êлассичесêим алãоритмом, таê и еãо модифиêациями. На рис. 8 поêазан резóльтат распознавания на монотонных теêстóрах при êоличестве ме- тоê — четыре и различном óровне шóма. а — óровень шóма — 0,4 б — óровень шóма — 0,6 в — óровень шóма — 0,7 Рис. 8. Распознавание на монотонных теêстóрах Блочная модифиêация сэмплирования по Ãиббсó для распознавания сêрытых марêовсêих полей ISSN 0130-5395, УСиМ, 2018, № 2 39 Работа распознающей программы На рис. 9 поêазаны резóльтаты распознавания на диаãональных и монотонных теêстóрах. а б в ã д е Рис. 9. Распознавание на диаãональных (а-в) и моно- тонных теêстóрах (ã-е). Резóльтаты: а и ã — для сãенерированной разметêи, б и д — для входноãо зашóмленноãо изображения, в и е — резóльтат распознавания. Заключение В слóчае распознавания изображений блочная модифиêация сэмплирования по Ãиббсó может быть êонстрóêтивно реализована, если в êаче- стве блоêов выстóпают строêи пиêселов изо- бражения. Предложенный альтернативный ме- тод оценêи математичесêоãо ожидания может быть использован в задачах распознавания сêрытых марêовсêих полей. Сравнение работы общеизвестноãо алãорит- ма сэмплирования по Ãиббсó и еãо блочной модифиêации проведено на изображениях с двóмя типами теêстóр на êоличестве метоê от трех до восьми, из чеãо можно сделать сле- дóющие выводы:  при невысоêом óровне шóма блочная мо- дифиêация на обеих теêстóрах работает не хóже общеизвестной попиêсельной реализа- ции;  при óвеличении óровня шóма на моно- тонных теêстóрах блочная модифиêация ра- ботает лóчше, что выражается в меньшем êо- личестве неправильно распознанных пиêсе- лов в сравнении с попиêсельной на начале работы алãоритма;  предложен ный альтернативный метод для оценêи математичесêоãо ожидания за- метных óлóчшений в работе алãоритма не дал, но исходя из полóченных ãрафиêов, можно предположить, что применительно ê блочной модифиêации, на высоêом óровне шóма он более эффеêтивен, чем стандартный. СПИСОÊ ЛИТЕРАТÓРЫ 1. Geman S., Geman D. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images, IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 1984, 6, N 6, P. 721–741. 2. Шлезинãер М.И. Синтаêсичесêий анализ двóмерных зрительных сиãналов в óсловиях помех, Êибернетиêа, Ê., 1976, Т. 4, С. 113–130. 3. Schlesinger M.I., Flach B. Some solvable subclass of structural recognition problems, Czech Pattern Recognition Workshop 2000, Ed. by T. Svoboda, Praha: Czech Pattern Recognition Society, Feb. 2000, P 55–62. 4. Schlesinger M., Flach B. Analyzis of optimal labelling problems and their applications to image segmentation and bin- ocular stereovision, Proc. East-West-Vision 2002 (EWV’02), Ed. by F. Leberl, A. Ferko, International Workshop and Project Festival on Computer Vision, Computer Graphics, New Media, 2002, P. 55–60. 5. Schlesinger M., Hlav ́ac V. Ten Lectures on Statistical and Structural Pattern Recognition, Dordrecht: Kluwer Acad. Publ., 2002, P. 355–361. Постóпила 06.07.2018 Е.В. Водолазсêий, С.А. Латюê 40 ISSN 0130-5395, Control systems and computers, 2018, № 2 Ye.V. Vodolazskiy, Senior researcher, waterlaz@gmail.com S.A. Latiuk, Engineer-programmer of 1-st category, serhiylatyuk55@gmail.com International Research and Training Center for Information Technologies and Systems of the National Academy of Sciences (NAS) of Ukraine and Ministry of Education and Science (MES) of Ukraine BLOCKING MODIFICATION OF GIBBS SAMPLING FOR RECOGNITION OF HIDDEN MARKOV FIELDS Introduction. This paper is dedicated to demonstration of the fact that blocking Gibbs sampling can be constructively im- plemented and applied to solve the image recognition tasks, in particular — for solving the labelling problems, to which some Computer Vision problems can be reduced. It's known, that these problems are optimization problems with the big number of the discrete arguments. The specificity of these tasks lies in the fact that function, which we want to optimize is the sum of a large number of terms, each of which depends on a few arguments. Tasks of such type are NP-hard, and poly- nomially solvable subclasses include very small number of situations that can happen in practice. So, there is a need to explore approximate methods for solving such problems. One of these methods is Gibbs sampling. There is no sense to apply Gibbs sampling in all recognition tasks, but it can be used in situations with some special loss functions for the statis- tical estimation of some quantities. Purpose of this paper is to demonstrate that blocking Gibbs sampling can be constructively implemented for solving image recognition problems. Secondly, we want to compare blocking modification with standard algorithm and find types of the textures, on which blocking modification will give better results. And, finally, we want to test validity of the pro- posed method for estimation of expectation. Methods. Blocking modification of Gibbs sampling for image recognition is built on the principles of dynamic pro- gramming. Software that allows to generate images of the given texture, choose proper modification of Gibbs sampling for solving the problem and show graphs using Python and Cython. Results. Blocking Gibbs sampling works better then standard realization, when images for recognition has so-called «monotonous» texture. In case of recognition the images with so-called «diagonal» texture (that very often arises in prac- tice) blocking modification works not worse than standard method. It was also noticed that proposed method for estima- tion of expectation works a little better than the standard one. Conclusion. Blocking Gibbs sampling can be applied for the solving image recognition tasks. It has constructive im- plementation which works in polynomial time. Asymptotically, one iteration of blocking Gibbs sampling is performing slower than one iteration of the standard Gibbs sampling algorithm. But in our experiments recognition at all (on «mo- notonous» textures) was performing faster with blocking algorithm. Due to this fact, we can conclude that blocking modi- fication is able to take into consideration some additional information that allows to perform the recognition faster. So, it makes sense to do further research in this fild. Keywords: Gibbs sampling, Gibbs sampler, labelling problems, hidden Markov fields recognition. Є.В. Водолазсьêий, ст. наóê. співр., Міжнародний наóêово-навчальний центр інформаційних технолоãій та систем НАН Óêраїни та МОН Óêраїни, просп. Ãлóшêова, 40, Êиїв 03187, Óêраїна, waterlaz@gmail.com С.О. Латюê, інж.-проãрам. I êат., serhiylatyuk55@gmail.com Міжнародний наóêово-навчальний центр інформаційних технолоãій та систем НАН Óêраїни та МОН Óêраїни, просп. Ãлóшêова, 40, Êиїв 03187, Óêраїна БЛОЧНА МОДИФІÊАЦІЯ СЕМПЛÓВАННЯ ЗА ÃІБСОМ ДЛЯ РОЗПІЗНАВАННЯ ПРИХОВАНИХ МАРÊІВСЬÊИХ ПОЛІВ Встóп. Статтю присвячено демонстрації тоãо, що блоêова модифіêація семплóвання за Ãібсом може бóти êонст- рóêтивно реалізована та з óспіхом застосована ó вирішенні задач розпізнавання зображень, зоêрема — ó вирішенні задач розмітêи, до яêих зводяться деяêі задачі êомп'ютерноãо зорó. Відомо, що задачі розмітêи поля- ãають в оптимізації фóнêцій від велиêої êільêості дисêретних арãóментів. Специфіêа цих задач поляãає в томó, що фóнêція, яêó необхідно оптимізóвати, є сóмою велиêої êільêості доданêів, êожен з яêих залежить від невелиêої êільêості змінних. Множина таêих задач óтворює NP-повний êлас, а відомі поліноміально розв'язні підêласи містять далеêо не всі ситóації, яêі можóть виниêнóти на праêтиці. Томó є потреба досліджóвати таêож неточні методи розв'язання задач таêоãо типó, одним з яêих є семплóвання за Ãібсом. Сенс застосовóвати семп- лóвання не ó всіх задачах розпізнавання, проте при деяêих фóнêціях штрафó воно може бóти виêористане для статистичноãо оцінювання певних величин. Блочная модифиêация сэмплирования по Ãиббсó для распознавания сêрытых марêовсêих полей ISSN 0130-5395, УСиМ, 2018, № 2 41 Мета статті — демонстрація існóвання êонстрóêтивної реалізації блочної модифіêації семплóвання за Ãібсом для розпізнавання зображень. Порівняння її роботи зі стандартною реалізацією та пошóê теêстóр, на яêих блочна модифіêація працює êраще. Перевірêа придатності запропонованоãо методó оцінêи математичноãо сподівання для виêористання при розпізнаванні прихованих марêівсьêих полів. Методи. Блочнó модифіêацію семплóвання за Ãібсом для розпізнавання зображень побóдовано на принци- пах динамічноãо проãрамóвання. Додатоê, що дозволяє ãенерóвати зображення заданої теêстóри, обирати потрібнó модифіêацію семплóвання за Ãібсом розв'язêó задачі розпізнавання та отримати ãрафіêи залежності швидêості розпізнавання êожноãо алãоритмó від часó реалізовано на мові Python з виêористанням бібліотеêи Cython для написання розширень на мові С. Резóльтат. Вявлено, що блочна модифіêація семплóвання за Ãібсом на таê званих «монотонних» теêстóрах при висоêомó рівні шóмó працює êраще, ніж стандартний алãоритм. На «діаãональних» теêстóрах, яêі дóже часто зóстрічаються, блочна модифіêація працює не ãірше, ніж заãальновідомий метод. Таêож виявлено, що на «моно- тонних» теêстóрах запропонований метод для оцінêи математичноãо сподівання демонстрóє êращі резóльтати, ніж заãальноприйнятий. Висновоê. Блочнó модифіêацію семплóвання за Ãібсом можна виêористати для розпізнавання зображень, завдяêи наявності êонстрóêтивної реалізації, яêа працює за поліноміальний час. Хоча асимптотично одна ітерація блочної модифіêації виêонóється повільніше, ніж одна ітерація стандартноãо алãоритмó семплóвання за Ãібсом, проте на малій êільêості мітоê, на «монотонних» теêстóрах розпізнавання в ціломó відбóвалося швидше завдяêи блочномó семплóванню, що свідчить про спроможність даноãо алãоритмó враховóвати певнó додатêовó інформацію, яêа в свою черãó пришвидшóє процес розв'язêó. А отже, є сенс проводити подальші дослідження в даній ãалóзі. Êлючові слова: семплóвання за Ãібсом, Ãібсівсьêий самплер, задачі розмітêи, розпізнавання прихованих марêівсьêих полів.

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

Репозитарії

Схожі ресурси