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

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

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

История

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

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

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

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

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

Обозначение

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

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

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

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

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

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

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

${\ Displaystyle \ Pr (х \ середина S) = K ^ {- E}}$

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

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

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

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

Гистограмма

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

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

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

Texon

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

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

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

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

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

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

Критика

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

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

Алгоритм

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

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

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

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

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

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

• 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 с массовым параллелизмом.

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