Графические сокращения в компьютерном зрении

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

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

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

Хотя многие алгоритмы компьютерного зрения предполагают разрезание графа (например, нормализованные разрезы), термин «разрезы графа» применяется конкретно к тем моделям, которые используют оптимизацию максимального потока/минимального разреза (другие алгоритмы разрезания графа можно рассматривать как алгоритмы разбиения графа ).

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

История

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

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

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

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

Бинарная сегментация изображений

Обозначение

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

Существующие методы

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

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

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

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

Энергетическая функция

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

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

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

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

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

Гистограмма

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

GMM (модель смеси Гаусса)

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

Тексон

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

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

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

Предшествующая модель / Модель когерентности / Граничный термин

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

• На практике пиксели определяются как соседние, если они смежны по горизонтали, вертикали или диагонали (4-сторонняя связность или 8-сторонняя связность для 2D-изображений).
• Стоимость может быть основана на локальном градиенте интенсивности, нулевом пересечении Лапласа, направлении градиента, модели смешения цветов,...
• Определены различные энергетические функции:
  • Стандартное марковское случайное поле : связывает штраф с несогласованными пикселями, оценивая разницу между их метками сегментации (грубая мера длины границ). См. Boykov and Kolmogorov ICCV 2003
  • Условное случайное поле : если цвет сильно отличается, это может быть хорошим местом для установки границы. См. Lafferty et al. 2001; Kumar and Hebert 2003

Критика

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

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

Алгоритм

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

Реализация (точная)

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

Реализация (приближение)

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

Программное обеспечение

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

Ссылки

1. Адельсон, Эдвард Х. и Джеймс Р. Берген (1991), «Пленоптическая функция и элементы раннего зрения», Вычислительные модели визуальной обработки 1.2 (1991).
2. Бойков, Ю., Векслер, О. и Забих, Р. (2001), «Быстрая приближенная минимизация энергии с помощью разрезов графа», IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(11): 1222-1239.
3. DM Greig, BT Porteous и AH Seheult (1989), Точная максимальная апостериорная оценка для бинарных изображений , Журнал Королевского статистического общества, Серия B, 51 , 271–279.
4. Д. Геман и С. Геман (1984), Стохастическая релаксация, распределения Гиббса и байесовское восстановление изображений , IEEE Trans. Pattern Anal. Mach. Intell., 6 , 721–741.
5. JE Besag (1986), О статистическом анализе грязных изображений (с обсуждением) , Журнал Королевского статистического общества, серия B, 48 , 259–302
6. Ю. Бойков, О. Векслер и Р. Забих (1998), «Марковские случайные поля с эффективными аппроксимациями», Международная конференция по компьютерному зрению и распознаванию образов (CVPR) .
7. Y. Boykov, O. Veksler и R. Zabih (2001), «Быстрая приближенная минимизация энергии с помощью разрезов графа», IEEE Transactions on Pattern Analysis and Machine Intelligence , 29 , 1222–1239.
8. Камиль Купри, Лео Грейди, Лоран Наджман и Хьюз Талбот, «Энергетические водоразделы: унифицированная графовая оптимизационная структура», Труды IEEE по анализу шаблонов и машинному интеллекту, том 33, № 7, стр. 1384-1399, июль 2011 г.
9. Лео Грейди и Кристофер Альвино (2009), «Кусочно-гладкий функционал Мамфорда-Шаха на произвольном графе», IEEE Trans. on Image Processing, стр. 2547–2561
10. Юрий Бойков и Владимир Колмогоров (2003), «Вычисление геодезических и минимальных поверхностей с помощью графовых разрезов», Труды ICCV
11. Бен Эпплтон и Хьюз Тальбот (2006), «Глобально минимальные поверхности с помощью непрерывных максимальных потоков», IEEE Transactions on Pattern Analysis and Machine Intelligence, стр. 106–118
12. Али Кемаль Синоп и Лео Грейди, «Структура сегментации изображений с затравкой, объединяющая разрезы графа и случайный обходчик, которая дает новый алгоритм», Труды ICCV, 2007 г.
13. Владимир Колмогоров и Юрий Бойков (2005), «Какие метрики могут быть аппроксимированы с помощью георазрезов, или глобальная оптимизация длины/площади и потока», Труды ICCV, стр. 564–571
14. Николя Лерме, Франсуа Мальгуйрес и Люка Летокар (2010), «Сокращение графов при сегментации разреза графа». Архивировано 27 марта 2012 г. в Wayback Machine , Труды ICIP, стр. 3045–3048.
15. Эрве Ломберт, Ийонг Сан, Лео Грейди, Чэньян Сюй (2005), «Метод многоуровневых ленточных графовых разрезов для быстрой сегментации изображений», Труды ICCV, стр. 259–265
16. Инь Ли, Цзянь Сан, Чи-Кенг Тан и Хынг-Йенг Шум (2004), «Ленивое щелканье», ACM Transactions on Graphics, стр. 303–308
17. Юрий Бойков, Владимир Колмогоров: Экспериментальное сравнение алгоритмов Min-Cut/Max-Flow для минимизации энергии в зрении. IEEE Trans. Pattern Anal. Mach. Intell. 26(9): 1124–1137 (2004)
18. PJ Yim: «Метод и система сегментации изображения», патент США US8929636, 6 января 2016 г.
19. Cederbaum, I. (1962-08-01). «Об оптимальной работе сетей связи». Журнал Института Франклина . 274 (2): 130–141. doi :10.1016/0016-0032(62)90401-5. ISSN  0016-0032.
20. IT Frisch, «Об электрических аналогах для сетей потоков», Труды IEEE, 57:2, стр. 209-210, 1969