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

Красным отмечен мотоциклист, синим — то, что его окружает: забор, зрители, машина, асфальт. Программа обвела мотоцикл и человека по контуру, хотя ей показали всего несколько мазков. Никакой нейросети: снимок превращён в граф, где каждый пиксель связан с соседями, и программа нашла в нём самый дешёвый разрез между красным и синим. Рисуйте сами — добавьте мазок там, где разрез ошибся, и он пересчитается за десятки миллисекунд. Ползунок «вес цвета» меняет то, за что разрез платит, а на второй фотографии разрез отделяет небо от гор.

Белая линия — граница разреза, всё за ней притемнено. Она идёт там, где соседние пиксели сильно отличаются: по краю куртки, по колесу, по тени под мотоциклом. Это не случайность и не подстроенная настройка: так устроена цена, которую разрез минимизирует.

Идея

Разметить снимок на «предмет» и «фон» — то же, что разрезать граф. Добавим к пикселям две вершины: исток (предмет) и сток (фон). Каждый пиксель соединим с ними рёбрами, цена которых говорит, насколько пиксель похож на предмет и на фон, и с четырьмя соседями — ребром тем дороже, чем соседи похожее. Любой разрез между истоком и стоком — это разметка: что осталось с истоком, то предмет. Цена разреза равна «штрафу» разметки: за пиксели не своего цвета и за границу между похожими соседями. Самая дешёвая разметка — минимальный разрез, а его находит максимальный поток.

Строже. Обозначим метку пикселя L_p ∈ {предмет, фон}. Штраф разметки — её энергия

$$E(L) = \sum_{p} D_p(L_p) + \sum_{\{p, q\}} w_{pq}\,[L_p \ne L_q].$$

Первая сумма — за данные: D_p(предмет) велико, если цвет пикселя p редко встречается под красными мазками, D_p(фон) — если редко под синими. Вторая — за гладкость: за каждую пару соседей, которых разметка разлучила, платим w_pq, и w_pq велико у похожих соседей и мало у непохожих. Пиксели под мазками приклеены к своему концу рёбрами бесконечной цены. Вариантов разметки — 2 в степени числа пикселей, на снимке шириной 320 пикселей это 2^{64 960}. Перебирать их не нужно.

Энергия может быть устроена и сложнее, но не любая годится. Владимир Колмогоров и Рамин Забих в 2004 году выяснили, какие двоичные энергии с попарными слагаемыми сводятся к разрезу: те, где штраф за несогласие соседей не меньше штрафа за согласие, — w(0, 1) + w(1, 0) ≥ w(0, 0) + w(1, 1). Такие энергии называют субмодулярными. Наша — частный случай: за согласие платим ноль, за несогласие w_pq ≥ 0.

Цвет против границ

Два слагаемых тянут в разные стороны. Гладкость любит короткие границы по резким переходам; данные любят, чтобы каждый пиксель достался тому, на кого он похож цветом. Листинг ниже считает разрез того же снимка, уменьшенного до 120 пикселей в ширину, при четырёх весах цвета. Без цвета разрез отдаёт предмету 695 пикселей — человека с мотоциклом. С весом 20 предмету достаётся уже 2181 пиксель, со 100 — 3441: к мотоциклисту прилипают тёмные деревья в углу и тёмный бампер машины. Мотоцикл зелёный, куртка чёрная, а деревья — тёмно-зелёные: цветовая модель по нескольким мазкам честно считает их похожими.

На второй фотографии цвет и границы согласны: небо отличается от гор и цветом, и резким переходом. Разрез идёт точно по хребту, даже там, где мазков нет, и почти не меняется, если двигать вес цвета от нуля до сорока. Настоящие программы выделения предметов строят цветовую модель сложнее — смесь нескольких нормальных распределений — и уточняют её по очереди с разрезом. Так устроен алгоритм GrabCut Карстена Розера, Владимира Колмогорова и Эндрю Блейка (2004), который есть в OpenCV.

Как найти разрез: две встречные волны

По теореме о потоке и разрезе, доказанной в статье о максимальном потоке, цена минимального разреза равна величине наибольшего потока, а сам разрез — граница множества вершин, достижимых из истока по ненасыщенным рёбрам. Значит, нужен быстрый поток на сетке пикселей. Алгоритм Эдмондса — Карпа из той статьи для каждого пути заново пускает поиск в ширину от истока и на снимках тонет: путей тысячи, а каждый поиск обходит десятки тысяч пикселей.

Юрий Бойков и Владимир Колмогоров сделали иначе (первая версия — 2001 год, подробная журнальная статья — 2004-й), и их способ похож на двунаправленный поиск. Растут два дерева: одно от истока, другое от стока. Дерево истока захватывает свободного соседа, если ребро к нему ещё не заполнено, дерево стока — если не заполнено ребро от соседа. Когда деревья соприкоснулись, найден путь: исток — по дереву — граничное ребро — по другому дереву — сток. По нему пускается поток, и какие-то рёбра пути заполняются.

Главное — что дальше. Эдмондс — Карп выбросил бы оба дерева и начал заново. Здесь деревья живут: вершины, чьё ребро к родителю заполнилось, становятся сиротами, и каждая сирота ищет нового родителя в своём дереве — соседа, который сам ещё держится за корень и ребро от которого не заполнено. Нашла — дерево цело. Не нашла — сирота становится свободной, а её дети тоже осиротели. Потом деревья снова растут. Когда расти некуда, а деревья так и не встретились, поток наибольший, и дерево истока — это сторона предмета.

На этом кусочке в 160 пикселей деревьям понадобилось 27 путей, чтобы упереться друг в друга, и наибольший поток — 42. Обратите внимание, где прошла граница: по краю шлема, где красный переходит в синий, — там рёбра между соседями дешёвые, и их заполнили первыми.

Разрез без истока и стока

Часто концов нет: нужно самое слабое место всего графа — наименьший набор рёбер, без которого он распадается на две части, всё равно какие. Это глобальный минимальный разрез. Его можно найти и потоками — перебрать в роли стока все вершины при одном и том же истоке, — но в 1993 году Дэвид Каргер предложил способ, в котором вообще нет потоков.

Возьмём случайное ребро и сожмём его: два конца сливаются в одну вершину, рёбра между ними исчезают (они стали бы петлями), остальные рёбра сохраняются, даже если стали параллельными. Повторяем, пока не останется две вершины. Каждая из них — группа исходных вершин, и рёбра между ними — разрез. Вот как это выглядит на сети рейсов между 21 аэропортом: вес связи — число позывных, которые летают между двумя городами, и случайное ребро берётся пропорционально весу.

Первый прогон отрезал Балхаш: в него и из него летают всего два позывных. Нажмите «2000 прогонов»: в 76 % случаев сжатия заканчиваются разрезом веса 2 — это минимум, и таких разрезов два, Балхаш и Ушарал, — а в остальных случаях получаются разрезы потяжелее. Почему вообще так часто? Потому что рёбер минимального разреза мало, а случайное ребро чаще всего берётся из толстых связок вроде Алматы — Астаны, и сжимать их безопасно.

Для 21 аэропорта оценка — 0,48 %, а на деле — 76 %: теорема говорит о худшем графе, а сеть рейсов к нему далека. Но и худший случай не страшен. Повторим прогоны независимо T раз и возьмём лучший разрез. Вероятность, что все T промахнулись, не больше (1 − p)^T ≤ e^−pT, где p = 2/(n(n − 1)). При T = n(n − 1)/2 · ln 100 это меньше 1 %: для 21 аэропорта — 968 прогонов. Получается алгоритм Монте-Карло: быстрый, но с маленькой вероятностью ошибки, которую повторами можно сделать сколь угодно малой.

Из теоремы следует и неожиданный факт без всякого алгоритма. События «прогон закончился разрезом C₁» и «… разрезом C₂» для разных минимальных разрезов несовместны, а вероятность каждого не меньше 2/(n(n − 1)). Сумма вероятностей не больше единицы, значит, минимальных разрезов в графе не больше n(n − 1)/2. У цикла из n вершин их ровно столько — любая пара рёбер.

Прогонов нужно много, и каждый стоит O(m) — всего около n²m log n. В 1996 году Каргер и Клиффорд Стайн ускорили схему: первые сжатия почти безопасны, поэтому граф сжимают до n/√2 вершин один раз, а дальше рекурсивно запускают две независимые копии. Получается O(n² log³ n). А детерминированный способ, без случайности, дали Мехтильд Штор и Франк Вагнер в 1997 году. Он тоже сжимает вершины, но выбирает пару не случайно: на каждой фазе вершины выстраиваются в порядке «наибольшей связности» — каждая следующая сильнее всех связана с уже выбранными, — и разрез «последняя вершина против остальных» оказывается минимальным среди разрезов, разделяющих две последние. Время — O(nm + n² log n). Листинг использует его, чтобы проверить ответ Каргера.

Код

Сегментация мотоциклиста целиком: мазки, граф с ценами, алгоритм Бойкова — Колмогорова на сетке пикселей. Граф не строится явно: у пикселя четыре соседа, и пропускная способность ребра к соседу в направлении d лежит в cap[4p + d]. Рёбра к истоку и стоку хранятся одним числом tr[p]: путь «исток → p → сток» сразу насыщается на меньшую из двух цен, и остаётся только разность. Программа проверяет на себе теорему: цена найденного разреза равна энергии разметки, посчитанной отдельно.

colour weight   cut = energy   object pixels   augmentations
            0           1079             695             423
           20          86895            2181            4228
           50         208895            3092            4257
          100         407370            3441            5085

Глобальный разрез сети рейсов: точный ответ алгоритмом Штор — Вагнера и 2000 прогонов случайных сжатий. Каждый позывной — отдельное ребро мультиграфа, и случайный позывной выбирается равновероятно, то есть связь — пропорционально весу. Если выпала петля — позывной внутри уже слитой группы, — его просто тянут заново: это то же, что выбрать случайное ребро среди непетель.

Сколько это стоит

Для потока Бойкова — Колмогорова хорошей оценки нет, это сказано выше. Зато замер на сетках того же снимка, уменьшенного до разной ширины, показывает разницу с Эдмондсом — Карпом лучше любой оценки. Оси логарифмические.

На снимке шириной 120 пикселей Бойков — Колмогоров в Go быстрее в 170 раз, и разрыв растёт с размером: время Эдмондса — Карпа растёт быстрее квадрата числа пикселей, а время Бойкова — Колмогорова — ненамного быстрее линейного. Эдмондс — Карп на каждый путь обходит заново весь граф, а у Бойкова — Колмогорова деревья переживают пути, и большая часть работы не повторяется. В браузере разрез снимка шириной 320 пикселей сцена выше считает за десятки миллисекунд — достаточно быстро, чтобы пересчитывать после каждого мазка.

Где работает

• Выделение предметов на фото. Алгоритм GrabCut — прямоугольник вокруг предмета, мазки-поправки и разрез графа пикселей — есть в OpenCV как cv.grabCut.
• Медицинские снимки. Врач отмечает несколько точек органа и фона, разрез трёхмерной сетки вокселей обводит орган целиком — та же энергия, только соседей у вокселя шесть.
• Зрение вообще. Стерео, склейка панорам по невидимому шву, удаление шума — задачи с метками, которые сводят к цепочке разрезов. Юрий Бойков, Ольга Векслер и Рамин Забих в 2001 году показали, как многометочную задачу решать последовательностью двоичных разрезов, и это стало стандартом.
• Надёжность сетей. Глобальный разрез — это наименьшее число связей, обрыв которых делит сеть: каналов связи, трубопроводов, рейсов. В сети выше это всего две связи — и обе ведут в один аэропорт.

История

В 1989 году статистики Д. Грейг, Б. Портеус и А. Сихьюлт решали задачу восстановления двоичного изображения по зашумлённому — найти самую вероятную картинку при модели, где соседние пиксели склонны совпадать. Такие задачи тогда решали приближённо, например отжигом. Авторы заметили, что задача сводится к минимальному разрезу, и решили её точно. Статья вышла в журнале по математической статистике, и исследователи компьютерного зрения больше десяти лет её почти не замечали.

В конце 1990-х Юрий Бойков, Ольга Векслер и Рамин Забих вернули разрезы в зрение — для многих меток и для настоящих задач. В 2001 году Бойков и Мари-Пьер Жолли показали интерактивную сегментацию мазками, ровно как в сцене выше. А в 2004 году вышли сразу три работы: алгоритм потока Бойкова и Колмогорова, ответ Колмогорова и Забиха на вопрос, какие энергии вообще минимизируются разрезом, и GrabCut Розера, Колмогорова и Блейка.

Глобальный разрез долго искали потоками. В 1992 году Хироси Нагамоти и Тосихидэ Ибараки нашли способ без потоков, на «порядке наибольшей связности», а Штор и Вагнер в 1997 году довели его до короткого алгоритма с простым доказательством. Между ними, в 1993 году, Дэвид Каргер, тогда аспирант, показал, что случайные сжатия находят разрез с хорошей вероятностью, и анализ занимает полстраницы. Этот алгоритм стал одним из стандартных первых примеров вероятностных алгоритмов в учебниках.

Задачи

В первой задаче разрез ничего не режет на картинке: он выбирает, какие статьи этого каталога прочитать ради задач, и бесконечные рёбра делают невозможным «решить задачу, не прочитав статью». Во второй истока и стока нет, а самый слабо связанный узел — не всегда самое слабое место.