Разработка и анализ алгоритма

Нетрудно заметить сходство между задачей о минимальном разрезе и задачей нахождения оптимальной разметки. Тем не менее между этими задачами также существует ряд важных различий. Во-первых, целевая функция максимизируется, а не минимизируется.
Во-вторых, в задаче разметки нет источника и стока; кроме того, нам приходится иметь дело со значениями а. и b узлов. В-третьих, граф G является ненаправленным, тогда как в задаче о минимальном разрезе используется направленный граф. Все эти проблемы кратко рассмотрены ниже.

Первая проблема — тот факт, что задача сегментации направлена на макси- мизацию — решается следующим наблюдением. ПустьСумма

не отличается от суммы, что позволяет

записать

Таким образом, мы видим, что задача максимизации q(A, B) эквивалентна задаче максимизации величины

Что касается отсутствия источника и стока, мы поступим так же, как в других предшествующих построениях: создадим новый «суперисточник» s, представля- ющий передний план, и новый «суперсток», представляющий фон. Заодно это позволит разобраться со значениями ai и bi, находящимися в узлах (тогда как ми- нимальные разрезы ограничиваются числами, связанными с ребрами). А именно, каждый из узлов s и t соединяется с каждым пикселом, а а. и b используются для определения соответствующих пропускных способностей ребер между пикселом i и источником и стоком соответственно.

Наконец, чтобы разобраться с направленностью ребер, мы смоделируем каждую из соседних пар (i, j) двумя направленными ребрами (i,j) и (j, i), как было сделано в ненаправленной задаче о непересекающихся путях. Этот прием очень хорошо работает в данном случае, так как в любом разрезе s-t не более одного из двух противоположно направленных ребер может переходить со стороны s на сторону t разреза (потому что другое ребро в этом случае должно переходить со стороны t на сторону s).

Конкретнее, мы определяем следующую потоковую сеть G' = ( V', E'), изображен- ную на рис. 7.18, b. Множество узлов V' состоит из множества пикселов Vс двумя дополнительными узлами s и t. Для каждой соседней пары пикселов i и j добав- ляются направленные ребра (i, j) и ( j, i), каждое из которых обладает пропускной способностью p Для каждого пиксела i добавляются ребро (s, i) с пропускной способностью а, и ребро (i, t) с пропускной способностью b

Теперь разрез s-t (A, B) соответствует разбиению пикселов на множества A и B.

Рассмотрим, как пропускная способность разреза c(A, B) связана с величиной q'(A, B), которую мы пытаемся минимизировать Ребра, пересекающие разрез (A, B), делятся на три естественные категории.

♦ Ребра (s, j), для которых j B; такое ребро вносит вклад а в пропускную спо- собность разреза.

♦ Ребра (i, t), для которых i A; такое ребро вносит вклад b в пропускную спо- собность разреза.

♦ Ребра (i, j), для которых i A и j B; такое ребро вносит вклад p.. в пропускную способность разреза.

На рис. 7.19 на примере с четырьмя пикселами показано, как выглядит каждый из трех видов ребер относительно разреза.

Рис. 7.19. Разрез s-t на графе, построенном для четырех пикселов. Обратите внимание на то, как в разрезе отражены три типа слагаемых в выражении q'(A, B)




Итак, все идеально складывается. Потоковая сеть устроена так, что пропускная способность разреза (A, B) в точности соответствует величине q'(A, B): три типа ребер, пересекающих разрез (A, B), которые мы определили (ребра от источника, ребра к стоку и ребра, не связанные ни с источником, ни со стоком), соответствуют трем типам слагаемых в выражении q'(A, B).

Следовательно, если мы хотим минимизировать q'(A, B) (что, как было показано ранее, эквивалентно максимизации q(A, B)), достаточно найти разрез с минималь- ной пропускной способностью — а мы уже знаем, как эффективно решить эту задачу.

Таким образом, решение задачи о минимальном разрезе дает оптимальный ал- горитм для решения задачи об отделении фона от переднего плана.

(7.55) Решение задачи сегментации может быть получено при помощи алго- ритма нахождения минимального разреза в графе G', построенного ранее. Для минимального разреза (A', B') разбиение (A, B), полученное удалением 5* и f, мак- симизирует метрику сегментации q(A, B).

7.11.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Разработка и анализ алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  3. § 2.ФУНКЦИИ МЕТОДОЛОГИИ В РАЗРАБОТКЕ МЕТОДИК АНАЛИЗА СОЦИАЛЬНЫХ ФАКТОВ
  4. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  5. АЛГОРИТМ
  6. АЛГОРИТМ УДАЧИ
  7. Алгоритм исцеления:
  8. Алгоритм избавления от боли
  9. 2. Специфика и алгоритмы работы с источниками.
  10. Алгоритм обработки результатов.
  11. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  12. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  13. 2.7. Разработка анкеты
  14. Разработка Плана
  15. 6. Разработка перспектив