Графические разрезы в компьютерном зрении - Graph cuts in computer vision

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

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

История

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

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

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

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

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

Обозначение

Образ: ${displaystyle xin {R, G, B} ^ {N}}$
Вывод: сегментация (также называемая непрозрачностью). ${displaystyle Sin R ^ {N}}$ (мягкая сегментация). Для жесткой сегментации ${displaystyle Sin {0 {ext {для фона}}, 1 {ext {для переднего плана / объекта, который будет обнаружен}}} ^ {N}}$
Энергетическая функция: ${displaystyle E (x, S, C, lambda)}$ где C - параметр цвета, а λ - параметр когерентности.
${displaystyle E (x, S, C, lambda) = E_ {m {color}} + E_ {m {coherence}}}$
Оптимизация: сегментацию можно оценить как глобальный минимум по S: ${displaystyle {arg min} _ {S} E (x, S, C, lambda)}$

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

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

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

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

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

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

{displaystyle Pr (xmid S) = K ^ {- E}}

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

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

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

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

Гистограмма

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

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

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

Texon

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

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

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

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

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

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

Критика

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

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

Алгоритм

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

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

Алгоритм Бойкова-Колмогорова^[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; алгоритм для вычисления приближенного решения минимального разреза s-t с массовым параллелизмом.

использованная литература

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

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

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

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

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

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

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

[boykov2001fast-7] а ^б Ю. Бойков, О. Векслер, Р. Забих (2001 г.) "Быстрая приблизительная минимизация энергии с помощью разрезов графика ", IEEE Transactions по анализу шаблонов и машинному анализу, 29, 1222–1239.

[8] Камилла Купри, Лео Грейди, Лоран Наджман и Хьюг Талбот "Power Watershads: единая платформа оптимизации на основе графов ”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 33, No. 7, pp. 1384-1399, июль 2011 г.

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

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

[11] Бен Эпплтон и Хьюг Талбот (2006) "Глобально минимальные поверхности при непрерывных максимальных потоках ", IEEE Transactions on Pattern Analysis and Machine Intelligence, стр. 106–118.

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

[13] Владимир Колмогоров и Юрий Бойков (2005 г.) "Какие показатели можно аппроксимировать с помощью гео-разрезов или глобальной оптимизации длины / площади и потока ", Proc. Of ICCV pp. 564–571.

[14] Николя Лерме, Франсуа Мальгуайрес и Лукас Летокарт (2010 г.) "Сокращение графиков при сегментации среза графа В архиве 2012-03-27 в Wayback Machine ", Материалы ИЦИП, с. 3045–3048.

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

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

[17] Юрий Бойков, Владимир Колмогоров: Экспериментальное сравнение алгоритмов Min-Cut / Max-Flow для минимизации энергии в зрении. IEEE Trans. Pattern Anal. Мах. Intell. 26 (9): 1124–1137 (2004).

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

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

[20] ЭТО. Фриш, "Об электрических аналогах проточных сетей", Труды 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]