Разрезы графов в компьютерном зрении

Применительно к компьютерному зрению оптимизация разреза графа может использоваться для эффективного решения широкого спектра задач компьютерного зрения низкого уровня ( раннее зрение) . ^[1]), такие как сглаживание изображения , проблема стереосоответствия , сегментация изображения , совместная сегментация объектов и многие другие задачи компьютерного зрения, которые можно сформулировать в терминах минимизации энергии . Многие из этих задач минимизации энергии можно аппроксимировать, решив задачу максимального потока в виде графа. ^[2] (и, таким образом, по теореме о максимальном потоке и минимальном разрезе определите минимальный разрез графа). В большинстве формулировок таких задач компьютерного зрения решение с минимальной энергией соответствует максимальной апостериорной оценке решения. Хотя многие алгоритмы компьютерного зрения включают разрезание графа (например, нормализованные разрезы), термин «разрезы графа» применяется специально к тем моделям, которые используют оптимизацию максимального потока/минимального разреза (другие алгоритмы разрезания графа можно рассматривать как разбиение графа). алгоритмы).

«Двоичные» проблемы (например, шумоподавление ) двоичного изображения можно решить именно с помощью этого подхода; Проблемы, когда пиксели могут быть помечены более чем двумя разными метками (например, стереосоответствие или шумоподавление изображения в оттенках серого ), не могут быть решены точно, но получаемые решения обычно близки к глобальному оптимуму.

История [ править ]

Теория разрезов графа , используемая в качестве метода оптимизации, была впервые применена в компьютерном зрении в основополагающей статье Грейга, Портеуса и Сехолта. ^[3] Даремского университета . Аллан Сехулт и Брюс Портеус были членами прославленной группы статистики Дарема того времени, возглавляемой Джулианом Бесагом и Питером Грином , а эксперт по оптимизации Маргарет Грейг была известна как первая женщина-сотрудник факультета математических наук Дарема.

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

Хотя общий $k$ - проблема цвета остается нерешенной $k>2,$ подход Грейга, Портеуса и Сехолта ^[3] оказалось ^[6]^[7] иметь широкое применение в общих задачах компьютерного зрения. Подходы Грейга, Портеуса и Сехолта часто применяются итеративно к последовательности бинарных задач, обычно давая решения, близкие к оптимальным.

В 2011 году C. Couprie et al . ^[8] с действительным знаком предложил общую структуру сегментации изображений, названную «Power Watershed», которая минимизирует индикаторную функцию от [0,1] на графике, ограниченную пользовательскими начальными числами (или унарными терминами), установленными на 0 или 1, в которой минимизация индикаторной функции на графике оптимизирована по показателю степени $p$ . Когда $p=1$ , Power Watershed оптимизируется путем разрезания графика, когда $p=0$ Power Watershed оптимизирован кратчайшими путями, $p=2$ оптимизируется алгоритмом случайного блуждания и $p=\infty$ оптимизируется алгоритмом водораздела . Таким образом, Power Watershed можно рассматривать как обобщение разрезов графа, которое обеспечивает прямую связь с другими алгоритмами сегментации/кластеризации оптимизации энергопотребления.

Бинарная сегментация изображений [ править ]

Обозначения [ править ]

Изображение: $x\in \{R,G,B\}^{N}$
Результат: сегментация (также называемая непрозрачностью) $S\in R^{N}$ (мягкая сегментация). Для жесткой сегментации $S\in \{0{\text{ for background}},1{\text{ for foreground/object to be detected}}\}^{N}$
Энергетическая функция : $E(x,S,C,\lambda )$ где C — параметр цвета, а λ — параметр когерентности.
$E(x,S,C,\lambda )=E_{\rm {color}}+E_{\rm {coherence}}$
Оптимизация: сегментацию можно оценить как глобальный минимум по S: ${\arg \min }_{S}E(x,S,C,\lambda )$

Существующие методы [ править ]

Стандартные сокращения графика: оптимизация энергетической функции при сегментации (неизвестное значение S).
Итерированные сокращения графа:

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

Эти два шага повторяются рекурсивно до сходимости.

Динамические сокращения графика:
Позволяет гораздо быстрее перезапустить алгоритм после изменения проблемы (например, после того, как пользователь добавил новые начальные числа).

Энергетическая функция [ править ]

\Pr(x\mid S)=K^{-E}

где энергия $E$ состоит из двух разных моделей ( $E_{\rm {color}}$ и $E_{\rm {coherence}}$ ):

Вероятность/Цветовая модель/Региональный термин [ править ]

$E_{\rm {color}}$ — унарный термин, описывающий вероятность каждого цвета.

Этот термин можно смоделировать с использованием различных локальных (например, тексонов) или глобальных (например, гистограмм, GMM, вероятности Adaboost) подходов, которые описаны ниже.

Гистограмма [ править ]

Мы используем интенсивности пикселей, помеченных как начальные, чтобы получить гистограммы для распределения интенсивности объекта (переднего плана) и фона: P(I|O) и P(I|B).
Затем мы используем эти гистограммы, чтобы установить региональные штрафы как отрицательные логарифмические вероятности.

GMM (модель смеси Гаусса) [ править ]

Обычно мы используем два распределения: одно для моделирования фона, а другое — для пикселей переднего плана.
Используйте модель гауссовой смеси (с 5–8 компонентами), чтобы смоделировать эти два распределения.
Цель: попытаться разделить эти два дистрибутива.

Тексон [ править ]

Тексон (или текстон) — это набор пикселей, обладающий определенными характеристиками и повторяющийся в изображении.
Шаги:

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

Примеры:
- Сегментация текстурированных объектов на основе деформируемой модели
- Анализ контуров и текстур для сегментации изображений

Априор / Модель когерентности / Граничный термин [ править ]

$E_{\rm {coherence}}$ — двоичный термин, описывающий согласованность между соседними пикселями.

На практике пиксели определяются как соседи, если они соседствуют по горизонтали, вертикали или диагонали (4-сторонняя связь или 8-сторонняя связь для 2D-изображений).
Затраты могут быть основаны на локальном градиенте интенсивности, лапласовском пересечении нуля, направлении градиента, модели смешения цветов и т. д.
Определены различные энергетические функции:
- Стандартное марковское случайное поле : назначьте штраф за несогласованные пиксели путем оценки разницы между их метками сегментации (грубая мера длины границ). См. Бойков и Колмогоров ICCV 2003.
- Условное случайное поле : если цвет сильно отличается, возможно, это хорошее место для установки границы. См. Лафферти и др. 2001 г.; Кумар и Хеберт 2003 г.

Критика [ править ]

Методы разрезов графа стали популярной альтернативой подходам, основанным на наборе уровней, для оптимизации местоположения контура (см. ^[9] для подробного сравнения). Однако подходы к разрезанию графа подвергались критике в литературе по нескольким вопросам:

Артефакты метрики. Когда изображение представлено 4-связной решеткой, методы разреза графа могут демонстрировать нежелательные артефакты «блочности». Для решения этой проблемы были предложены различные методы, например, использование дополнительных ребер. ^[10] или сформулировав задачу о максимальном потоке в непрерывном пространстве. ^[11]
Сокращение смещения: поскольку при разрезах графа обнаруживается минимальный разрез, алгоритм может быть смещен в сторону создания небольшого контура. ^[12] Например, алгоритм не очень подходит для сегментации тонких объектов, таких как кровеносные сосуды (см. ^[13] предлагаемое исправление).
Множественные метки: разрезы графа позволяют найти глобальный оптимум только для задач двоичной разметки (т. е. двух меток), таких как сегментация изображения переднего и заднего планов. Были предложены расширения, которые могут находить приближенные решения для проблем разрезания графа с несколькими метками. ^[7]
Память: использование памяти для разрезов графа быстро увеличивается по мере увеличения размера изображения. В качестве иллюстрации алгоритм максимального потока Бойкова-Колмогорова v2.2 выделяет $24n+14m$ байты ( $n$ и $m$ — соответственно количество узлов и ребер в графе). Тем не менее, в последнее время в этом направлении была проделана некоторая работа по сокращению графиков перед вычислением максимального потока. ^[14]^[15]^[16]

Алгоритм [ править ]

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

Реализация (точная) [ править ]

Алгоритм Бойкова-Колмогорова ^[17] — это эффективный способ вычисления максимального потока для графов, связанных с компьютерным зрением.

Реализация (приближение) [ править ]

Алгоритм Sim Cut ^[18] аппроксимирует минимальный разрез графа. Алгоритм реализует решение путем моделирования электрической сети. Это подход, предложенный теоремой Седербаума о максимальном потоке . ^[19]^[20] Ускорение работы алгоритма возможно за счет параллельных вычислений .

Программное обеспечение [ править ]

http://pub.ist.ac.at/~vnk/software.html — реализация алгоритма maxflow, описанная в книге Владимира Колмогорова «Экспериментальное сравнение алгоритмов Min-Cut/Max-Flow для минимизации энергии в компьютерном зрении».
http://vision.csd.uwo.ca/code/ — некоторые библиотеки вырезания графов и оболочки MATLAB.
http://gridcut.com/ — быстрый многоядерный решатель max-flow/min-cut, оптимизированный для графиков в виде сетки.
http://virtualscalpel.com/ — реализация Sim Cut ; алгоритм для вычисления приближенного решения минимального разреза с массовым параллелизмом.

Ссылки [ править ]

^ Адельсон, Эдвард Х. и Джеймс Р. Берген (1991), « Пленоптическая функция и элементы раннего зрения », Вычислительные модели визуальной обработки 1.2 (1991).
^ Бойков Ю., Векслер О. и Забих Р. (2001), « Быстрая приближенная минимизация энергии посредством разрезов графа », Транзакции IEEE по анализу шаблонов и машинному интеллекту, 23 (11): 1222-1239.
^ Jump up to: Перейти обратно: ^а ^б Д.М. Грейг, Б.Т. Портеус и А.Х. Сехолт (1989), Точная максимальная апостериорная оценка для бинарных изображений , Журнал Королевского статистического общества, Серия B, 51 , 271–279.
^ Д. Геман и С. Геман (1984), Стохастическая релаксация, распределения Гиббса и байесовское восстановление изображений , IEEE Trans. Паттерн Анал. Мах. Интел., 6 , 721–741.
^ Дж. Э. Бесаг (1986), О статистическом анализе грязных фотографий (с обсуждением) , Журнал Королевского статистического общества, серия B, 48 , 259–302.
^ Ю. Бойков, О. Векслер и Р. Забих (1998), « Марковские случайные поля с эффективными аппроксимациями », Международная конференция по компьютерному зрению и распознаванию образов (CVPR) .
^ Jump up to: Перейти обратно: ^а ^б Ю. Бойков, О. Векслер и Р. Забих (2001), « Быстрая приближенная минимизация энергии посредством разрезов графа », Транзакции IEEE по анализу шаблонов и машинному интеллекту , 29 , 1222–1239.
^ Камилла Купри, Лео Грейди, Лоран Наджман и Хью Талбот, « Водоразделы власти: унифицированная структура оптимизации на основе графов », Транзакции IEEE по анализу шаблонов и машинному интеллекту, том 33, № 7, стр. 1384-1399, июль 2011 год
^ Лео Грейди и Кристофер Альвино (2009), « Кусочно-гладкий функционал Мамфорда-Шаха на произвольном графе », IEEE Trans. по обработке изображений, стр. 2547–2561.
^ Юрий Бойков и Владимир Колмогоров (2003), « Вычисление геодезических и минимальных поверхностей с помощью разрезов графа », Proc. ICCV
^ Бен Эпплтон и Хьюг Талбот (2006), « Глобально минимальные поверхности с помощью непрерывных максимальных потоков », Транзакции IEEE по анализу закономерностей и машинному интеллекту, стр. 106–118
^ Али Кемаль Синоп и Лео Грейди, « Среда сегментации затравленных изображений, объединяющая разрезы графа и случайное перемещение, что дает новый алгоритм », Proc. ICCV, 2007 г.
^ Владимир Колмогоров и Юрий Бойков (2005), « Какие показатели могут быть аппроксимированы с помощью географических разрезов или глобальная оптимизация длины / площади и потока », Proc. ICCV, стр. 564–571.
^ Николя Лерме, Франсуа Малгуир и Лукас Летокар (2010), « Сокращение графиков при сегментации разреза графа. Архивировано 27 марта 2012 г. в Wayback Machine », Proc. ICIP, стр. 3045–3048.
^ Эрве Ломберт, Июн Сунь, Лео Грейди, Чэньян Сюй (2005), « Метод многоуровневых полосовых графических разрезов для быстрой сегментации изображений », Proc. ICCV, стр. 259–265.
^ Инь Ли, Цзянь Сан, Чи-Кын Тан и Хын-Юнг Шум (2004), « Ленивая привязка », Транзакции ACM в графике, стр. 303–308
^ Юрий Бойков, Владимир Колмогоров: Экспериментальное сравнение алгоритмов минимального/максимального потока для минимизации энергии в зрении . IEEE Транс. Паттерн Анал. Мах. Интел. 26 (9): 1124–1137 (2004).
^ Пи Джей Йим: « Метод и система сегментации изображений », патент США US8929636, 6 января 2016 г.
^ Седербаум, И. (1 августа 1962 г.). «Об оптимальной эксплуатации сетей связи». Журнал Института Франклина . 274 (2): 130–141. дои : 10.1016/0016-0032(62)90401-5 . ISSN 0016-0032 .
^ IT Фриш, «Об электрических аналогах проточных сетей», Труды IEEE, 57:2, стр. 209–210, 1969.

[1] Адельсон, Эдвард Х. и Джеймс Р. Берген (1991), « Пленоптическая функция и элементы раннего зрения », Вычислительные модели визуальной обработки 1.2 (1991).

[2] Бойков Ю., Векслер О. и Забих Р. (2001), « Быстрая приближенная минимизация энергии посредством разрезов графа », Транзакции IEEE по анализу шаблонов и машинному интеллекту, 23 (11): 1222-1239.

[D.M._Greig,_B.T_1989-3] Jump up to: Перейти обратно: ^а ^б Д.М. Грейг, Б.Т. Портеус и А.Х. Сехолт (1989), Точная максимальная апостериорная оценка для бинарных изображений , Журнал Королевского статистического общества, Серия B, 51 , 271–279.

[4] Д. Геман и С. Геман (1984), Стохастическая релаксация, распределения Гиббса и байесовское восстановление изображений , IEEE Trans. Паттерн Анал. Мах. Интел., 6 , 721–741.

[5] Дж. Э. Бесаг (1986), О статистическом анализе грязных фотографий (с обсуждением) , Журнал Королевского статистического общества, серия B, 48 , 259–302.

[6] Ю. Бойков, О. Векслер и Р. Забих (1998), « Марковские случайные поля с эффективными аппроксимациями », Международная конференция по компьютерному зрению и распознаванию образов (CVPR) .

[boykov2001fast-7] Jump up to: Перейти обратно: ^а ^б Ю. Бойков, О. Векслер и Р. Забих (2001), « Быстрая приближенная минимизация энергии посредством разрезов графа », Транзакции IEEE по анализу шаблонов и машинному интеллекту , 29 , 1222–1239.

[8] Камилла Купри, Лео Грейди, Лоран Наджман и Хью Талбот, « Водоразделы власти: унифицированная структура оптимизации на основе графов », Транзакции IEEE по анализу шаблонов и машинному интеллекту, том 33, № 7, стр. 1384-1399, июль 2011 год

[9] Лео Грейди и Кристофер Альвино (2009), « Кусочно-гладкий функционал Мамфорда-Шаха на произвольном графе », IEEE Trans. по обработке изображений, стр. 2547–2561.

[10] Юрий Бойков и Владимир Колмогоров (2003), « Вычисление геодезических и минимальных поверхностей с помощью разрезов графа », Proc. ICCV

[11] Бен Эпплтон и Хьюг Талбот (2006), « Глобально минимальные поверхности с помощью непрерывных максимальных потоков », Транзакции IEEE по анализу закономерностей и машинному интеллекту, стр. 106–118

[12] Али Кемаль Синоп и Лео Грейди, « Среда сегментации затравленных изображений, объединяющая разрезы графа и случайное перемещение, что дает новый алгоритм », Proc. ICCV, 2007 г.

[13] Владимир Колмогоров и Юрий Бойков (2005), « Какие показатели могут быть аппроксимированы с помощью географических разрезов или глобальная оптимизация длины / площади и потока », Proc. ICCV, стр. 564–571.

[14] Николя Лерме, Франсуа Малгуир и Лукас Летокар (2010), « Сокращение графиков при сегментации разреза графа. Архивировано 27 марта 2012 г. в Wayback Machine », Proc. ICIP, стр. 3045–3048.

[15] Эрве Ломберт, Июн Сунь, Лео Грейди, Чэньян Сюй (2005), « Метод многоуровневых полосовых графических разрезов для быстрой сегментации изображений », Proc. ICCV, стр. 259–265.

[16] Инь Ли, Цзянь Сан, Чи-Кын Тан и Хын-Юнг Шум (2004), « Ленивая привязка », Транзакции ACM в графике, стр. 303–308

[17] Юрий Бойков, Владимир Колмогоров: Экспериментальное сравнение алгоритмов минимального/максимального потока для минимизации энергии в зрении . IEEE Транс. Паттерн Анал. Мах. Интел. 26 (9): 1124–1137 (2004).

[18] Пи Джей Йим: « Метод и система сегментации изображений », патент США US8929636, 6 января 2016 г.

[19] Седербаум, И. (1 августа 1962 г.). «Об оптимальной эксплуатации сетей связи». Журнал Института Франклина . 274 (2): 130–141. дои : 10.1016/0016-0032(62)90401-5 . ISSN 0016-0032 .

[20] IT Фриш, «Об электрических аналогах проточных сетей», Труды IEEE, 57:2, стр. 209–210, 1969.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]