WikiDer > Оптимизация вырезки графика

Оптимизация вырезки графика это комбинаторная оптимизация метод применимый к семейству функции из дискретные переменные, названный в честь концепции резать в теории проточные сети. Благодаря теорема о максимальном потоке и минимальном отсечении, определяя минимальный разрез через график представление потоковой сети эквивалентно вычислению максимальный поток по сети. Учитывая псевдобулева функция ${ displaystyle f}$, если возможно построить потоковую сеть с положительными весами такую, что

• каждый разрез ${ displaystyle C}$ сети можно сопоставить с присвоением переменных ${ displaystyle mathbf {x}}$ к ${ displaystyle f}$ (и наоборот), и
• цена ${ displaystyle C}$ равно ${ Displaystyle е ( mathbf {х})}$ (с точностью до аддитивной постоянной)

тогда можно найти глобальный оптимум из ${ displaystyle f}$ в полиномиальное время вычисляя минимальный разрез графа. Сопоставление разрезов и присвоений переменных осуществляется путем представления каждой переменной одним узлом в графе, и, при разрезе, каждая переменная будет иметь значение 0, если соответствующий узел принадлежит компоненту, связанному с источником, или 1, если он принадлежат компоненту, подключенному к раковине.

Не все псевдобулевы функции могут быть представлены потоковой сетью, и в общем случае проблема глобальной оптимизации имеет вид NP-жесткий. Существуют достаточные условия для характеристики семейств функций, которые можно оптимизировать с помощью разрезов графа, например субмодулярные квадратичные функции. Оптимизация разреза графа может быть расширена до функций дискретных переменных с конечным числом значений, к которым можно подойти с помощью итерационных алгоритмов с сильными свойствами оптимальности, вычисляющих один разрез графа на каждой итерации.

Оптимизация графической обрезки - важный инструмент для вывода графические модели такие как Марковские случайные поля или условные случайные поля, и у него есть приложения в задачах компьютерного зрения такие как сегментация изображения,^[1][2] шумоподавление,^[3] постановка на учет^[4][5] и стерео согласование.^[6][7]

Представимость

А псевдобулева функция ${ displaystyle f: {0,1 } ^ {n} to mathbb {R}}$ как говорят представимый если существует граф ${ Displaystyle G = (V, E)}$ с неотрицательными весами и с узлами источника и приемника ${ displaystyle s}$ и ${ displaystyle t}$ соответственно, и существует набор узлов ${ displaystyle V_ {0} = {v_ {1}, dots, v_ {n} } subset V - {s, t }}$ так что для каждого набора значений ${ displaystyle (x_ {1}, dots, x_ {n}) in {0,1 } ^ {n}}$ присвоенные переменным, ${ displaystyle f (x_ {1}, dots, x_ {n})}$ равняется (с точностью до константы) величине расхода, определяемой минимумом резать ${ Displaystyle C = (S, T)}$ графика ${ displaystyle G}$ такой, что ${ displaystyle v_ {i} in S}$ если ${ displaystyle x_ {i} = 0}$ и ${ displaystyle v_ {i} in T}$ если ${ displaystyle x_ {i} = 1}$.^[8]

Можно классифицировать псевдобулевы функции в соответствии с их порядком, определяемым максимальным количеством переменных, составляющих каждый отдельный член. Все функции первого порядка, где каждый член зависит не более чем от одной переменной, всегда представимы. Квадратичные функции

${ displaystyle f ( mathbf {x}) = w_ {0} + sum _ {i} w_ {i} (x_ {i}) + sum _ {i$

представимы тогда и только тогда, когда они субмодулярны, т.е. для каждого квадратичного члена ${ displaystyle w_ {ij}}$ выполняется следующее условие

${ displaystyle w_ {ij} (0,0) + w_ {ij} (1,1) leq w_ {ij} (0,1) + w_ {ij} (1,0).}$

Кубические функции

${ displaystyle f ( mathbf {x}) = w_ {0} + sum _ {i} w_ {i} (x_ {i}) + sum _ {i$

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

Построение графа

Построение графа для представимой функции упрощается тем, что сумма двух представимых функций ${ displaystyle f '}$ и ${ displaystyle f ''}$ представима, а его граф ${ Displaystyle G = (V ' чашка V' ', E' cup E '')}$ является объединением графов ${ Displaystyle G '= (V', E ')}$ и ${ displaystyle G '' = (V '', E '')}$ представляющие две функции. Такая теорема позволяет построить отдельные графики, представляющие каждый член, и объединить их, чтобы получить график, представляющий всю функцию.^[8]

График, представляющий квадратичную функцию от ${ displaystyle n}$ переменные содержат ${ displaystyle n + 2}$ вершины, две из которых представляют источник и сток, а другие - переменные. При представлении функций высшего порядка граф содержит вспомогательные узлы, позволяющие моделировать взаимодействия более высокого порядка.

Унарные термины

Унарный термин ${ displaystyle w_ {i}}$ зависит только от одной переменной ${ displaystyle x_ {i}}$ и может быть представлен графом с одним нетерминальным узлом ${ displaystyle v_ {i}}$ и один край ${ displaystyle s rightarrow v_ {i}}$ с весом ${ displaystyle w_ {i} (1) -w_ {i} (0)}$ если ${ Displaystyle ш_ {я} (1) geq ш_ {я} (0)}$, или ${ displaystyle v_ {i} rightarrow t}$ с весом ${ displaystyle w_ {i} (0) -w_ {i} (1)}$ если ${ Displaystyle ш_ {я} (1) <ш_ {я} (0)}$.^[8]

Бинарные условия

Пример графика, представляющего квадратичный член ${ displaystyle w_ {ij} (x_ {i}, x_ {j})}$ в случае ${ displaystyle w_ {ij} (1,0) -w_ {ij} (0,0)> 0}$ и ${ displaystyle w_ {ij} (1,1) -w_ {ij} (1,0) <0}$.

Квадратичный (или двоичный) член ${ displaystyle w_ {ij}}$ может быть представлен графом, содержащим два нетерминальных узла ${ displaystyle v_ {i}}$ и ${ displaystyle v_ {j}}$. Термин можно переписать как

${ Displaystyle w_ {ij} (x_ {i}, x_ {j}) = w_ {ij} (0,0) + k_ {i} x_ {i} + k_ {j} x_ {j} + k_ {ij } left ((1-x_ {i}) x_ {j} + x_ {i} (1-x_ {j}) right)}$

с участием

${ displaystyle { begin {align} k_ {i} & = { frac {1} {2}} (w_ {ij} (1,0) -w_ {ij} (0,0)) k_ { j} & = { frac {1} {2}} (w_ {ij} (1,1) -w_ {ij} (1,0)) k_ {ij} & = { frac {1} { 2}} (w_ {ij} (0,1) + w_ {ij} (1,0) -w_ {ij} (0,0) -w_ {ij} (1,1)). End {выравнивается} }}$

В этом выражении первый член является постоянным и не представлен никаким ребром, два следующих члена зависят от одной переменной и представлены одним ребром, как показано в предыдущем разделе для унарных членов, а третий член представлен как край ${ displaystyle v_ {i} rightarrow v_ {j}}$ с весом ${ displaystyle w_ {ij} (0,1) + w_ {ij} (1,0) -w_ {ij} (0,0) -w_ {ij} (1,1)}$ (субмодульность гарантирует неотрицательность веса).^[8]

Тернарные термины

Кубический (или тернарный) член ${ displaystyle w_ {ijk}}$ можно представить в виде графа с четырьмя нетерминальными узлами, три из которых (${ displaystyle v_ {i}}$, ${ displaystyle v_ {j}}$ и ${ displaystyle v_ {k}}$) связанный с тремя переменными плюс один четвертый вспомогательный узел ${ displaystyle v_ {ijk}}$.^{[примечание 1]} Общий тернарный член можно переписать как сумму константы, трех унарных членов, трех двоичных членов и тернарного члена в упрощенной форме. Может быть два разных случая, в зависимости от признака ${ displaystyle p = w_ {ijk} (0,0,0) + w_ {ijk} (0,1,1) + w_ {ijk} (1,0,1) + w_ {ijk} (1,1, 0)}$. Если ${ displaystyle p> 0}$ тогда

${ displaystyle w_ {ijk} (x_ {i}, x_ {j}, x_ {k}) = w_ {ijk} (0,0,0) + p_ {1} (x_ {i} -1) + p_ {2} (x_ {j} -1) + p_ {3} (x_ {k} -1) + p_ {23} (x_ {j} -1) x_ {k} + p_ {31} x_ {i} (x_ {k} -1) + p_ {12} (x_ {i} -1) x_ {j} -px_ {i} x_ {j} x_ {k}}$

Пример графа, представляющего тернарный член ${ displaystyle px_ {i} x_ {j} x_ {k}}$ когда ${ displaystyle p> 0}$ (слева) и когда ${ displaystyle p <0}$ (правильно).

с участием

${ displaystyle { begin {align} p_ {1} & = w_ {ijk} (1,0,1) -w_ {ijk} (0,0,1) p_ {2} & = w_ {ijk} (1,1,0) -w_ {ijk} (1,0,1) p_ {3} & = w_ {ijk} (0,1,1) -w_ {ijk} (0,1,0) p_ {23} & = w_ {ijk} (0,0,1) + w_ {ijk} (0,1,0) -w_ {ijk} (0,0,0) -w_ {ijk} (0 , 1,1) p_ {31} & = w_ {ijk} (0,0,1) + w_ {ijk} (1,0,0) -w_ {ijk} (0,0,0) -w_ {ijk} (1,0,1) p_ {12} & = w_ {ijk} (0,1,0) + w_ {ijk} (1,0,0) -w_ {ijk} (0,0 , 0) -w_ {ijk} (1,1,0). End {align}}}$

Если ${ displaystyle p <0}$ конструкция аналогична, но переменные будут иметь противоположное значение. Если функция регулярна, то все ее проекции двух переменных будут субмодулярными, что означает, что ${ displaystyle p_ {23}}$, ${ displaystyle p_ {31}}$ и ${ displaystyle p_ {12}}$ положительны, и тогда все члены в новом представлении субмодулярны.

В этом разложении постоянные, унарные и двоичные члены могут быть представлены, как показано в предыдущих разделах. Если ${ displaystyle p> 0}$ тернарный член может быть представлен графом с четырьмя ребрами ${ displaystyle v_ {i} rightarrow v_ {ijk}}$, ${ displaystyle v_ {j} rightarrow v_ {ijk}}$, ${ displaystyle v_ {k} rightarrow v_ {ijk}}$, ${ displaystyle v_ {ijk} rightarrow t}$, все с весом ${ displaystyle p}$, а если ${ displaystyle p <0}$ термин может быть представлен четырьмя гранями ${ displaystyle v_ {ijk} rightarrow v_ {i}}$, ${ displaystyle v_ {ijk} rightarrow v_ {j}}$, ${ displaystyle v_ {ijk} rightarrow v_ {k}}$, ${ displaystyle s rightarrow v_ {ijk}}$ с весом ${ displaystyle -p}$.^[8]

Минимальный разрез

После построения графика, представляющего псевдобулеву функцию, можно вычислить минимальный разрез, используя один из различных алгоритмов, разработанных для потоковых сетей, таких как Форд – Фулкерсон, Эдмондс-Карп, и Алгоритм Бойкова – Колмогорова. Результатом является разбиение графа на две связные компоненты. ${ displaystyle S}$ и ${ displaystyle T}$ такой, что ${ displaystyle s in S}$ и ${ displaystyle t in T}$, а функция достигает своего глобального минимума, когда ${ displaystyle x_ {i} = 0}$ для каждого ${ displaystyle i}$ такой, что соответствующий узел ${ displaystyle v_ {i} in S}$, и ${ displaystyle x_ {i} = 1}$ для каждого ${ displaystyle i}$ такой, что соответствующий узел ${ displaystyle v_ {i} in T}$.

Алгоритмы максимального потока, такие как алгоритм Бойкова – Колмогорова, на практике очень эффективны для последовательных вычислений, но их трудно распараллелить, что делает их непригодными для распределенных вычислений приложений и не позволяя им использовать потенциал современных Процессоры. Были разработаны параллельные алгоритмы максимального потока, такие как переименовать^[9] и скачок,^[1] которые также могут использовать преимущества аппаратного ускорения в ГПГПУ реализации.^[10][1][11]

Функции дискретных переменных с более чем двумя значениями

Предыдущая конструкция допускает глобальную оптимизацию только псевдобулевых функций, но ее можно распространить на квадратичные функции дискретных переменных с конечным числом значений в виде

${ displaystyle f ( mathbf {x}) = sum _ {i in V} D (x_ {i}) + sum _ {(i, j) in E} S (x_ {i}, x_ {j})}$

где ${ Displaystyle E substeq V times V}$ и ${ displaystyle x_ {i} in Lambda = {1, dots, k }}$. Функция ${ displaystyle D (x_ {i})}$ представляет собой унарный вклад каждой переменной (часто называемой срок данных), а функция ${ Displaystyle S (x_ {i}, x_ {j})}$ представляет бинарные взаимодействия между переменными (срок плавности). В общем случае оптимизация таких функций представляет собой NP-жесткий проблема, и стохастическая оптимизация такие методы как имитация отжига чувствительны к локальные минимумы и на практике они могут давать произвольно неоптимальные результаты.^{[заметка 2]} С помощью разрезов графа можно построить алгоритмы перемещения, которые позволяют достичь за полиномиальное время локальных минимумов с сильными свойствами оптимальности для широкого семейства квадратичных функций, представляющих практический интерес (когда бинарное взаимодействие ${ Displaystyle S (x_ {i}, x_ {j})}$ это метрика или полуметрический), так что значение функции в решении лежит в пределах постоянного и известного множителя от глобального оптимума.^[12]

Учитывая функцию ${ displaystyle f: Lambda ^ {n} to mathbb {R}}$ с участием ${ Displaystyle Lambda = {1, точки, к }}$, и определенное присвоение значений ${ displaystyle mathbf {x} = (x_ {1}, dots, x_ {n}) in Lambda ^ {n}}$ с переменными можно связать каждое присвоение ${ displaystyle mathbf {x}}$ к разделу ${ Displaystyle P = {P_ {l} | l in Lambda }}$ набора переменных, таких что, ${ Displaystyle P_ {l} = {x_ {i} | x_ {i} = l in Lambda }}$. Дайте два разных задания ${ displaystyle P}$ и ${ displaystyle P '}$ и ценность ${ displaystyle alpha in Lambda}$, ход, который преобразует ${ displaystyle P}$ в ${ displaystyle P '}$ считается ${ displaystyle alpha}$-расширение, если ${ displaystyle P _ { alpha} subset P '_ { alpha}}$ и ${ displaystyle P '_ {l} subset P_ {l} ; forall l in Lambda - { alpha }}$. Учитывая пару значений ${ displaystyle alpha}$ и ${ displaystyle beta}$, ход называется ${ displaystyle alpha beta}$-swap, если ${ displaystyle P_ {l} = P '_ {l} ; forall l in Lambda - { alpha, beta }}$. Интуитивно ${ displaystyle alpha}$-расширение перейти от ${ displaystyle mathbf {x}}$ присваивает значение ${ displaystyle alpha}$ к некоторым переменным, которые имеют другое значение в ${ displaystyle mathbf {x}}$, а ${ displaystyle alpha beta}$-swap move назначает ${ displaystyle alpha}$ к некоторым переменным, имеющим значение ${ displaystyle beta}$ в ${ displaystyle mathbf {x}}$ и наоборот.

Для каждой итерации ${ displaystyle alpha}$-Алгоритм расширения вычисляет для каждого возможного значения ${ displaystyle alpha}$, минимум функции среди всех присвоений ${ Displaystyle mathrm {A} ( mathbf {x})}$ что может быть достигнуто с помощью одного ${ displaystyle alpha}$-расширение перейти от текущего временного решения ${ displaystyle mathbf {x}}$, и принимает его как новое временное решение.

${ displaystyle  mathbf {x}: = { text {произвольное значение в}}  Lambda ^ {n}}$${ displaystyle { text {exit}}: = 0}$в то время как ${ displaystyle { text {exit}}  neq 1}$:    ${ displaystyle { text {exit}} = 1}$    для каждого ${ displaystyle  alpha  in  Lambda}$:        ${ displaystyle  mathbf { hat {x}}: =  arg  min _ { mathbf {y}  in  mathrm {A} ( mathbf {x})} f ( mathbf {y})}$        если ${ Displaystyle е ( mathbf { шляпа {х}}) < mathbf {x}}$:            ${ displaystyle  mathbf {x} =  mathbf { hat {x}}}$            ${ displaystyle { text {exit}}: = 0}$

В ${ displaystyle alpha beta}$-swap алгоритм похож, но ищет минимум среди всех назначений ${ Displaystyle mathrm {A} mathrm {B} ( mathbf {x})}$ достижимый с помощью одного ${ displaystyle alpha beta}$-swap перейти от ${ displaystyle mathbf {x}}$.

${ displaystyle  mathbf {x}: = { text {произвольное значение в}}  Lambda ^ {n}}$${ displaystyle { text {exit}}: = 0}$в то время как ${ displaystyle { text {exit}}  neq 1}$:    ${ displaystyle { text {exit}} = 1}$    для каждого ${ Displaystyle ( альфа,  бета)  в  Lambda ^ {2}}$:        ${ displaystyle  mathbf { hat {x}}: =  arg  min _ { mathbf {y}  in  mathrm {A}  mathrm {B} ( mathbf {x})} f ( mathbf { y})}$        если ${ Displaystyle е ( mathbf { шляпа {х}}) < mathbf {x}}$:            ${ displaystyle  mathbf {x} =  mathbf { hat {x}}}$            ${ displaystyle { text {exit}}: = 0}$

В обоих случаях проблема оптимизации в самом внутреннем цикле может быть решена точно и эффективно с разрезанием графа. Оба алгоритма обязательно завершаются конечным числом итераций внешнего цикла, и на практике такое количество невелико, и большая часть улучшений происходит на первой итерации. Алгоритмы могут генерировать различные решения в зависимости от первоначального предположения, но на практике они устойчивы в отношении инициализации, и для получения результатов хорошего качества обычно достаточно начать с момента, когда всем переменным присваивается одно и то же случайное значение.^[12]

Решение, генерируемое такими алгоритмами, не обязательно является глобальным оптимумом, но оно имеет надежные гарантии оптимальности. Если ${ Displaystyle S (x_ {i}, x_ {j})}$ это метрика и ${ displaystyle mathbf {x}}$ является решением, порожденным ${ displaystyle alpha}$-расширение алгоритма, или если ${ Displaystyle S (x_ {i}, x_ {j})}$ это полуметрический и ${ displaystyle mathbf {x}}$ решение, порожденное ${ displaystyle alpha beta}$-swap алгоритм, затем ${ Displaystyle е ( mathbf {х})}$ лежит в пределах известного и постоянного множителя от глобального минимума ${ Displaystyle е ( mathbf {х} ^ {*})}$:^[12]

${ Displaystyle е ( mathbf {x}) Leq 2 { frac { max _ { alpha neq beta in Lambda} S ( alpha, beta)} { min _ { alpha neq beta in Lambda} S ( alpha, beta)}} f ( mathbf {x} ^ {*}).}$

Несубмодульные функции

Вообще говоря, проблема оптимизации несубмодулярной псевдобулевой функции состоит в следующем: NP-жесткий и не может быть решена за полиномиальное время простым разрезанием графа. Самый простой подход - аппроксимировать функцию похожей, но субмодульной функцией, например, усекая все несубмодульные термины или заменяя их подобными субмодульными выражениями. Такой подход обычно неоптимален и дает приемлемые результаты только в том случае, если количество непубмодульных членов относительно невелико.^[13]

В случае квадратичных непубмодулярных функций можно вычислить за полиномиальное время частичное решение, используя такие алгоритмы, как QPBO.^[13] Функции высшего порядка могут быть сведены за полиномиальное время к квадратичной форме, которая может быть оптимизирована с помощью QPBO.^[14]

Функции высшего порядка

Квадратичные функции широко изучаются и были подробно охарактеризованы, но более общие результаты были получены и для функций более высокого порядка. Хотя квадратичные функции действительно могут моделировать многие проблемы, представляющие практический интерес, они ограничены тем фактом, что могут представлять только бинарные взаимодействия между переменными. Возможность фиксировать взаимодействия более высокого порядка позволяет лучше понять природу проблемы и может обеспечить более качественные результаты, которых трудно достичь с помощью квадратичных моделей. Например, в компьютерное зрение приложений, где каждая переменная представляет собой пиксель или воксель Взаимодействия более высокого порядка могут использоваться для моделирования текстурной информации, которую было бы трудно зафиксировать, используя только квадратичные функции.^[15]

Достаточные условия, аналогичные субмодулярности, были разработаны для характеристики псевдобулевых функций высшего порядка, которые могут быть оптимизированы за полиномиальное время,^[16] и существуют алгоритмы, аналогичные ${ displaystyle alpha}$-расширение и ${ displaystyle alpha beta}$-замена для некоторых семейств функций высшего порядка.^[15] Задача в общем случае NP-сложна, и были разработаны приближенные методы быстрой оптимизации функций, не удовлетворяющих таким условиям.^[16][17]

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

• Бойков, Юрий; Векслер, Ольга; Забих, Рамин (2001). «Быстрая приблизительная минимизация энергии с помощью разрезов графика». IEEE Transactions по анализу шаблонов и машинному анализу. 23 (11): 1222–1239. CiteSeerX 10.1.1.439.2071. Дои:10.1109/34.969114.
• Фридман, Даниэль; Дриней, Петрос (2005). Минимизация энергии с помощью разрезов графиков: определение того, что возможно (PDF). Конференция компьютерного общества IEEE по компьютерному зрению и распознаванию образов. 2. С. 939–946.
• Гольдберг, Эндрю V; Тарджан, Роберт Э (1988). «Новый подход к задаче о максимальном расходе» (PDF). Журнал ACM. 35 (4): 921–940. Дои:10.1145/48014.61051. S2CID 52152408.
• Исикава, Хироши (2014). Редукция клики высшего порядка без вспомогательных переменных (PDF). Конференция IEEE по компьютерному зрению и распознаванию образов. IEEE. С. 1362–1369.
• Хун, Ли; Чен, Джордж (2004). Стерео сопоставление на основе сегментов с использованием разрезов графика (PDF). Материалы конференции компьютерного общества IEEE 2004 года по компьютерному зрению и распознаванию образов. 1. С. 74–81.
• Коли, Пушмит; Кумар, М. Паван; Торр, Филип Х.С. (2009). "П³ И за его пределами: алгоритмы продвижения для решения функций высшего порядка » (PDF). IEEE Transactions по анализу шаблонов и машинному анализу. 31 (9): 1645–1656. Дои:10.1109 / тпами.2008.217. PMID 19574624. S2CID 91470.
• Ким, Джунхван; Колмогоров Владимир; Забих, Рамин (2003). Визуальная переписка с использованием минимизации энергии и взаимной информации (PDF). Труды Девятой Международной конференции IEEE по компьютерному зрению. С. 1033–1040.
• Коли, Пушмит; Ladicky, Lubor; Торр, PHS (2008). Разрезы графа для минимизации надежных потенциалов более высокого порядка (PDF) (Технический отчет). Оксфордский университет Брукса. С. 1–9.
• Колмогоров Владимир; Ротер, Карстен (2007). «Минимизация несубмодульных функций: обзор». IEEE Transactions по анализу шаблонов и машинному анализу. 29 (7): 1274–1279. Дои:10.1109 / тпами.2007.1031. PMID 17496384. S2CID 15319364.
• Колмогоров Владимир; Забин, Рамин (2004). «Какие энергетические функции можно минимизировать с помощью разрезов графиков?» (PDF). IEEE Transactions по анализу шаблонов и машинному анализу. 26 (2): 1645–1656. Дои:10.1109 / TPAMI.2004.1262177. HDL:1813/5842. PMID 15376891.
• Ломберт, Эрве; Cheriet, Фарида (2012). Одновременное устранение шумов и регистрация изображений с помощью разрезов графиков: применение для поврежденных медицинских изображений (PDF). 11-я Международная конференция по информатике, обработке сигналов и их приложениям. С. 264–268.
• Пэн, Йи; Чен, Ли; Оу-Ян, Фан-Синь; Чен, Вэй; Юн, Джун-Хай (2015). «JF-Cut: подход параллельного вырезания графиков для крупномасштабных изображений и видео». IEEE Transactions по обработке изображений. 24 (2): 655–666. Bibcode:2015ITIP ... 24..655P. Дои:10.1109 / TIP.2014.2378060. PMID 25494510. S2CID 1665580.
• Ротер, Карстен; Колмогоров Владимир; Блейк, Эндрю (2004). Grabcut: интерактивное извлечение переднего плана с использованием итерационных разрезов графиков (PDF). Транзакции ACM на графике. 23. С. 309–314.
• Итак, Рональд В.К .; Тан, Томми WH; Чанг, Альберт CS (2011). «Нежесткая регистрация изображений магнитно-резонансных изображений головного мозга с использованием графических разрезов». Распознавание образов. 44 (10–11): 2450–2467. Дои:10.1016 / j.patcog.2011.04.008.
• Стич, Тимо (2009). Вырезание графа с помощью CUDA (PDF). Конференция по технологиям GPU.
• Тан, Томми WH; Чанг, Альберт CS (2007). Нежесткая регистрация изображения с использованием разрезов графа (PDF). Международная конференция по медицинской обработке изображений и компьютерному вмешательству. С. 916–924. Дои:10.1007/978-3-540-75757-3_111.
• Винит, Вибхав; Нараянан, П.Дж. (2008). CUDA cuts: быстрое вырезание графиков на GPU (PDF). Конференция IEEE Computer Society по компьютерному зрению и семинарам по распознаванию образов. С. 1–8.

Заметки

внешние ссылки

• Реализация (C ++) нескольких алгоритмов вырезания графа Владимира Колмогорова.
• GCO, библиотека оптимизации вырезания графа от Ольги Векслер и Эндрю Делонга.