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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\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 компонентами) для моделирования этих двух распределений.
Цель: попытаться разделить эти два дистрибутива.

Texon [ править ]

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

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

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

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

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

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

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

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

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

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

Минимизация выполняется с использованием стандартного алгоритма минимального сокращения.
Благодаря теореме о максимальном потоке и минимальном отсечении мы можем решить проблему минимизации энергии, максимизируя поток по сети. Задача 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 ; алгоритм для вычисления приближенного решения минимального прохода st с массовым параллелизмом.

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

^ Адельсон, Эдвард Х. и Джеймс Р. Берген (1991), " Пленоптическая функция и элементы раннего видения ", Вычислительные модели обработки изображений 1.2 (1991).
^ Бойков, Ю., Векслер, О., и Забих, Р. (2001), « приблизительная минимизация энергии с помощью разрезов графа », IEEE Transactions on Pattern Analysis and Machine Intelligence, 23 (11): 1222-1239.
^ а б Д. Грейг, Б.Т. Портеус и А.Х. Сеулт (1989), Точная максимальная апостериорная оценка для двоичных изображений , Журнал Королевского статистического общества, серия B, 51 , 271–279.
^ D. Geman и S. Geman (1984), Стохастическая релаксация, распределения Гиббса и байесовское восстановление изображений , IEEE Trans. Pattern Anal. Мах. Интеллект., 6 , 721–741.
^ JE Besag (1986), О статистическом анализе грязных картинок (с обсуждением) , Журнал Королевского статистического общества, серия B, 48 , 259–302
^ Ю. Бойков, О. Векслер и Р. Забих (1998), " Марковские случайные поля с эффективными приближениями ", Международная конференция по компьютерному зрению и распознаванию образов (CVPR) .
^ a b Ю. Бойков, О. Векслер и Р. Забих (2001), « Быстрая приблизительная минимизация энергии с помощью разрезов графа », IEEE Transactions on Pattern Analysis and Machine Intelligence , 29 , 1222–1239.
^ Камиль Couprie, Лео Грейди, Лоран Найман и Гюг Talbot, " Сила Водоразделы: объединительная , основанная на графах Оптимизация рамка », IEEE Transactions на шаблон анализе и Machine Intelligence, Vol 33, N 7, стр 1384-1399, июль.. 2011 г.
^ Лео Грэди и Кристофер Альвино (2009), « Кусочно-гладкий функционал Мамфорда-Шаха на произвольном графе », IEEE Trans. по обработке изображений, стр. 2547–2561.
^ Юрий Бойков и Владимир Колмогоров (2003), " Вычисление геодезических и минимальных поверхностей с помощью графических разрезов ", Proc. ICCV
↑ Бен Эпплтон и Хьюг Талбот (2006), « Глобально минимальные поверхности с помощью непрерывных максимальных потоков », IEEE Transactions on Pattern Analysis and Machine Intelligence, стр. 106–118
^ Али Кемаль Синоп и Лео Грэди, « Фреймворк для сегментации засеянных изображений, объединяющий вырезки графа и случайный ходок, который дает новый алгоритм », Proc. ICCV, 2007 г.
↑ Владимир Колмогоров и Юрий Бойков (2005), « Какие метрики можно аппроксимировать с помощью георазрезов или глобальной оптимизации длины / площади и потока », Proc. of ICCV стр. 564–571
^ Николя Lermé, Франсуа Malgouyres и Лукас Létocart (2010), " Сокращение графиков в графике разрез сегментации Архивированных 2012-03-27 в Wayback Machine ", Proc. ICIP, стр. 3045–3048
^ Herve Lombaert, Yiyong ВС, Лев Грейди, Chenyang Xu (2005), " многоуровневая Пластинчатые Graph Cuts метода для быстрого изображения Сегментации ", Proc. of ICCV, стр. 259–265
^ Инь Ли Цзянь ВС, Чи-Keung Тан, и Хонг-Енг Shum (2004), " Ленивый Замыкание ", ACM Сделки на графике, стр. 303-308
^ Юрий Бойков, Владимир Колмогоров: экспериментальное сравнение алгоритмов Min-Cut / Max-Flow для минимизации энергии в видении . IEEE Trans. Pattern Anal. Мах. Intell. 26 (9): 1124–1137 (2004).
↑ PJ Yim: « Метод и система сегментации изображений », Патент США US8929636, 6 января 2016 г.
^ Цедербаума, I. (1962-08-01). «Об оптимальной работе сетей связи». Журнал Института Франклина . 274 (2): 130–141. DOI : 10.1016 / 0016-0032 (62) 90401-5 . ISSN 0016-0032 .
^ IT Frisch, "Об электрических аналогах для потоковых сетей", Труды IEEE, 57: 2, стр. 209-210, 1969

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

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

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

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

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

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

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

[8] Камиль Couprie, Лео Грейди, Лоран Найман и Гюг Talbot, " Сила Водоразделы: объединительная , основанная на графах Оптимизация рамка », IEEE Transactions на шаблон анализе и Machine Intelligence, Vol 33, N 7, стр 1384-1399, июль.. 2011 г.

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

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

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

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

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

[14] Николя Lermé, Франсуа Malgouyres и Лукас Létocart (2010), " Сокращение графиков в графике разрез сегментации Архивированных 2012-03-27 в Wayback Machine ", Proc. ICIP, стр. 3045–3048

[15] Herve Lombaert, Yiyong ВС, Лев Грейди, Chenyang Xu (2005), " многоуровневая Пластинчатые Graph Cuts метода для быстрого изображения Сегментации ", Proc. of ICCV, стр. 259–265

[16] Инь Ли Цзянь ВС, Чи-Keung Тан, и Хонг-Енг Shum (2004), " Ленивый Замыкание ", ACM Сделки на графике, стр. 303-308

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

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

[19] Цедербаума, 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

[1]