Задача

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

Обозначим V множество пикселов анализируемого изображения. Некоторые пары пикселов объявляются соседями; пусть E — множество всех пар соседних пикселов. Таким образом будет получен ненаправленный граф G = (V, E). Здесь мы намеренно не даем четкого определения того, что подразумевается под «пикселом» или «соседским» отношением. Для любого графа G будет получено эффективное решение задачи, поэтому мы можем определять эти концепции так, как считаем

нужным. Конечно, пикселы естественно представлять как точки, образующие сет- ку; при этом соседями считаются пикселы, занимающие смежные позиции в этой сетке, как показано на рис. 7.18, а.

Рис. 7.18. а — матрица пикселов; b — схема соответствующего потокового графа; на схеме изображены не все ребра от источника к стоку


Для каждого пиксела i имеется степень правдоподобия а. того, что он принад- лежит переднему плану, и степень правдоподобия bi того, что он принадлежит фону. Условно будем считать, что величины правдоподобия представляют собой произвольные неотрицательные числа, содержащиеся в постановке задачи, и они указывают, насколько желательно, чтобы пиксел i считался относящимся к перед- нему плану или фону.

В остальном не так важно, какие физические свойства изо- бражения оценивают эти характеристики и как они вычисляются.

Каждой отдельный пиксел i было бы разумно отнести к переднему плану, если а. > b,, или к фону в противном случае. Однако решение относительно i зависит от решений, принимаемых относительно соседей i. Например, если многие соседи i помечены как относящиеся к фону, то у нас появляется больше оснований отнести к фону i; это приводит к «сглаживанию» границ между фоном и передним планом, и снижению длины границы. Для каждой пары соседних пикселов (i, j) вводится штраф за разделение p.j > 0, применяемый в том случае, если один пиксел пары от- носится к переднему плану, а другой к фону.

А теперь мы можем точно определить задачу сегментации в контексте пара- метров правдоподобия и штрафа за разделение. Требуется найти разбиение мно-

жества пикселов на подмножества A и B (передний план и фон соответственно), максимизирующее

Таким образом, высокие значения правдоподобия награждаются, а соседние пары (i, j), в которых один пиксел принадлежит A, а другой принадлежит B, штра- фуются. Задача заключается в вычислении оптимальной разметки — разбиения (A, B), максимизирующей q(A, B).

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

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. 3. Задачи и функции социологии