2010 Лекции МОТП (Ветров) (1185317), страница 17
Текст из файла (страница 17)
Использованиеграфических моделей позволяет учесть, что соседниепиксели чаще всего относятся к одному классуРепараметризацияРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение• Рассмотрим две соседние вершины ti и tj , каждая из которыхможет принимать два значения• Тогда функция Ei (xi , ti ) задается двумя значениями (приизвестном xi ), а функция Eij (ti , tj ) — четырьмя• Для сведения к задаче о поиске минимального разреза нампонадобится выполнить т.н.
репараметризацию, сделав «веса»горизонтальных ребер нулевымиРепараметризацияРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение• Вычитая одинаковые значения из двух ребер, сходящихся в однувершину и прибавляя это же значение к весу самой вершины,мы получаем эквивалентный функционал энергии• Значения такой энергии в каждой точке совпадает со значениемисходной энергии• Применение этой процедуры позволяет путем измененияфункции Ei получить эквивалентный энергетическийфункционал, в котором Eij (0, 0) = Eij (1, 1) = 0 и Eij (0, 1) = Eij (1, 0)для всех (i, j) ∈ EСведение к разрезу графовРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение• Определим на следующем графе пропускную способность такимобразом:c(S, ti ) = Ei (xi , 0),c(T, ti ) = Ei (xi , 1),c(ti , tj ) = Eij (0, 1), ∀(i, j) ∈ E• Поиск минимального разреза в таком графе отвечаетминимизации энергииE(T|X) =X(i,j)∈EEij (ti , tj ) +Xiт.е.
поиску наиболее вероятных значений TEi (xi , ti )Сегментация с семенамиРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение• Часто для некоторых пикселей известно заранее, ккакому классу они принадлежат• Например, пользователь может задать фрагментыизображения и фона (семена)Сведение к разрезу графовРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение• Пусть O — семена объекта (ti = 1), а B — семена фона (ti = 0)• Тогда достаточно задать c(S, ti ) = +∞, ∀ti ∈ O и c(T, ti ) = +∞,∀ti ∈ B• Этим мы запретим соответствующие разрезы, сделавневозможным отнесение семян объекта к фону и наоборотСпособы введения унарного слагаемогоРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширениеПо смыслу унарное (относительно скрытых переменных)слагаемое Ei (xi , ti ) задает насколько данный пиксельсоответствует тому или иному классу.
Оно может отражатьследующую информацию:• Цветовая модель — показывает насколько появлениетех или иных цветов более вероятно в данном классе• Позиционная модель — показывает априорныепредположения о положении данного класса наизображении• Текстурная модель — показывает насколько текстураокрестности пикселя вероятна для данного пикселяСпособы введения парного слагаемогоРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширениеПарное слагаемое Eij (ti , tj ) отражает степеньвзаимозависимостей классов соседних пикселей. Наиболеераспространенными примерами являются• Модель Поттса: Eij (ti , tj ) = 1 − δ(ti , tj ) — штраф занесовпадение классов соседних пикселей• Штраф за несовпадение классов с учетом контраст൶(xi − xj )2Eij (ti , tj ) = exp −(1 − δ(ti , tj ))2σ 2Чем сильнее различаются цвета (интенсивности)пикселей xi , тем меньше штраф за несовпадениеклассов• Заметим, что во втором случае парное слагаемоезависит от наблюдаемых переменных xi и xj - такаяконструкция называется условным случайным полемСубмодулярностьРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение• Назовем энергию субмодулярной, если для всех еепарных слагаемых верноEij (0, 0) + Eij (1, 1) ≤ Eij (0, 1) + Eij (1, 0)• Условие субмодулярности является в некоторомсмысле аналогом выпуклости для функций бинарногопеременного• Унарное слагаемое при этом может бытьпроизвольным• Легко показать, что с помощью разрезов графовможно оптимизировать именно субмодулярнуюэнергиюДоказательство необходимостиРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункции0Альфарасширение• Пусть имеется парное слагаемое, не являющеесясубмодулярной функциейEij (0, 0) + Eij (1, 1) > Eij (0, 1) + Eij (1, 0)• Тогда и только тогда в результате репараметризациинулевые веса горизонтальных связей приведут квозникновению отрицательных диагональных связейДоказательство необходимостиРазрезы графовВетровЛикбез-6Марковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение010• Но это означает, что пропускная способность некоторых ребер вграфе, разрез которого мы будем минимизировать, станетотрицательной!• В этой ситуации классические полиномиальные алгоритмыпоиска минимального разреза в графе неприменимы• Задача оптимизации энергии стала NP-трудной• Существуют некоторые обобщения полиномиального алгоритмана случаи, когда энергия может быть сведена в субмодулярнойпутем замены части переменных на свои отрицания: ti → (1 − ti )Случай небинарных переменныхРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение• До сих пор рассматривался случай, когда скрытыепеременные бинарные• Теперь рассмотрим ситуацию, когда скрытыепеременные ti могут принимать одно из K значений• Физически это соответствует делению изображения наK областей• Такие задачи возникают при построении картдиспаритетов, коллажах, семантической сегментации ипр.Семантическая сегментацияРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширениеПример задачи семантической сегментацииАнатомическая разметкаРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширениеПример задачи автоматического выделения анатомическихзон головного мозга мышиИтерационная схемаРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширениеE(T|X) =X(i,j)∈EXEij (ti , tj )+Ei (xi , ti ) → min, ti ∈ {0, 1, .
. . , K−1}iT• Задача оптимизации энергии по K-значным скрытымпеременным (K > 2) является NP-трудной• Тем не менее, в ряде случаев можно построитьитерационную процедуру, сходящуюся к близкому кглобальному оптимуму ответу• Наибольшее распространение получил алгоритм т.н.α-расширенияИтерационная схемаРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение• Начинаем с произвольного начального приближения• В цикле для каждой метки α ∈ {0, . . .
, K − 1} заменяем частьдругих меток на данную, так чтобы минимизировать энергию(выполняем α-расширение)• Если хотя бы для одной метки энергию удалось уменьшить, топереходим в предыдущему шагу, иначе выходДля сходимости такого алгоритма необходимо, чтобы каждое парноеслагаемое было метрикой в пространстве {0, . . . , K − 1}, т.е.удовлетворяло следующим условиям ∀α, β, γ ∈ {0, . .
. , K − 1}• Eij (α, β) = Eij (β, α) (симметричность)• Eij (α, β) = 0 ⇔ α = β (аксиома тождества)• Eij (α, γ) ≤ Eij (α, β) + Eij (β, γ) (неравенство треугольника)α-расширениеРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение• В ходе альфа-расширения часть других метокпринимает значение α, стремясь минимизироватьэнергию• Введем вспомогательную марковскую решетку сбинарными переменными sj , в которой значение 0будет соответствовать тому, что исходные скрытыепеременные tj не изменились, а значение 1 будетозначать, что исходные переменные приняли значениеα∀j : tjold = α ⇒ sj ≡ 0(sj = 0 ⇒ tjnew = tjold∀j : tjold 6= α ⇒sj = 1 ⇒ tjnew = α• Теперь относительно новых переменных можнопостроить минимальный разрез графа,минимизирующий энергию по всевозможнымα-расширениямα-расширениеРазрезы графовs=0is=0j(t=g)jEij(b,g)Ветров(t=b)i-6ЛикбезEij(a,g)Марковские сетиРазрезы графовСубмодулярныефункцииАльфарасширениеEij(b,a)s=1i0Eij(a,a)(t=a)i10s=1j(t=a)j• Рассмотрим некоторую пару скрытых переменных (ti , tj ),соединенную ребром• Предположим, что старые значения переменных равнялись β и γсоответственно• Для корректной репараметризации необходимо выполнениенеравенства треугольникаEij (β, γ) ≤ Eij (α, γ) + Eij (β, α)• Теперь относительно новых переменных можно построитьминимальный разрез графа, минимизирующий энергию повсевозможным α-расширениямα-расширениеРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение• Запретим изменять метки класса αc(S, ti ) = Ei (xi , α),c(T, ti ) = +∞c(ti , tj ) = Eij (α, α) = 0, ∀(i, j) ∈ E : ti = tj = α• Для остальных вершин (tiold 6= α) определим пропускнуюспособность следующим образом:c(S, ti ) = Ei (xi , α),c(ti , tj ) = E(α, tiold ),c(T, ti ) = Ei (xi , tiold )c(tj , ti ) = E(α, tjold ), ∀(i, j) ∈ E• Вершинам, попавшим в тот же подграф, что и исток S, будетприсвоена метка α, энергия при этом уменьшитсяТочность получающегося решенияРазрезы графовВетровЛикбезМарковские сетиРазрезы графовСубмодулярныефункцииАльфарасширение• Алгоритм α-расширения является итерационным,полиномиальным, поэтому не гарантирует достижениеглобального оптимума (NP-трудная задача)• Можно показать, что значение энергии, получившейсяв результате альфа-расширения, лежит в интервалеE(T ∗ ) ≤ E(T) ≤ 2kE(T ∗ ),где T ∗ — оптимальное (наиболее вероятное) значениескрытых переменных, аk=max Eij (β, γ)minβ6=γ Eij (β, γ)степень контрастности парной энергииМосковский государственный университетимени М.
В. ЛомоносоваФакультет вычислительной математики и кибернетикиМатематические основытеории прогнозирования(курс лекций)лектор — академик РАН Ю. И. Журавлев2008Оглавление1Стандартная задача распознавания . . . . . . . . . . . . . . . . . . . . . . . .Алгоритм “Кора” (Вайнцвайг, Бонгарт) .
. . . . . . . . . . . . . . . . . . . . .Тестовый алгоритм (Ю. И. Журавлев) . . . . . . . . . . . . . . . . . . . . . .33462.1Логические алгоритмы распознавания . . . . . . . . . . . . . . . . . . . . . .993.13.216Алгоритмы вычисления оценок . . . . . . . . . . . . . . . . . . . . . . . . . . 16Эффективные формулы вычисления оценок . . . . . . . . . . .
. . . . . . . . 204.14.224Вычисление характеристик, определяющих алгоритм вычисления оценок . . 24Алгебры над алгоритмами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261.11.21.32345285.1Построение алгоритмов распознавания, корректных для заданной контрольной выборки . . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
