Редактирование: Алгоритм Штор-Вагнера нахождения минимального разреза

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 29: Строка 29:
 
   v[i] - список вершин, которые были сжаты в i-тую (сначала заполняется i);
 
   v[i] - список вершин, которые были сжаты в i-тую (сначала заполняется i);
 
   for i = 1..n-1
 
   for i = 1..n-1
     A = Ø;
+
     обнуляем мн-во A;
     fill(w, 0);
+
     обнуляем w(связности всех вершин);
 
     for j = 1..n-1
 
     for j = 1..n-1
       s = {s <tex>\in</tex> V | s <tex>\notin</tex> A, w[s] - max};
+
       s = вершина не из A, для которой w[s] - максимальна;
 
       if (j != n-1)
 
       if (j != n-1)
         A += s;
+
         добавляем s в A;
 
         пересчитываем связность w[i] для остальных вершин;  
 
         пересчитываем связность w[i] для остальных вершин;  
 
         prev = s;
 
         prev = s;
Строка 41: Строка 41:
 
           minCost = w[s];
 
           minCost = w[s];
 
           minCut = v[s];
 
           minCut = v[s];
         s' = s <tex>\cup</tex> prev;
+
         s и prev объединяются в одну вершину;
 
   return minCut - список вершин в минимальном разрезе;
 
   return minCut - список вершин в минимальном разрезе;
  
Строка 101: Строка 101:
  
 
Изображение представляется в виде взвешенного графа, вершинами которого являются точки изображения (как правило, пиксели, но, возможно, и большие области, от этого зависит качество сегментации, а также скорость её построения). Вес ребра представляет отражает "разницу" между точками (расстояние в некоторой метрике). Разбиение изображения на однородные области сводится к задаче поиска минимального разреза в графе. Специально для такого рода задач был предложен метод нахождения разреза минимальной стоимости [https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CDQQFjAB&url=http%3A%2F%2Fwww.cs.berkeley.edu%2F~malik%2Fpapers%2FSM-ncut.pdf&ei=cP2-UuqhAuSJ4gTnhYCwAg&usg=AFQjCNFn9GZPlFjDUgDofCScu6Wm47qMWQ&sig2=Yufd8LreEQKHe3NGnFVm7A&bvm=bv.58187178,d.bGE&cad=rjt Normalized Cut (J. Shi, J. Malik (1997))]
 
Изображение представляется в виде взвешенного графа, вершинами которого являются точки изображения (как правило, пиксели, но, возможно, и большие области, от этого зависит качество сегментации, а также скорость её построения). Вес ребра представляет отражает "разницу" между точками (расстояние в некоторой метрике). Разбиение изображения на однородные области сводится к задаче поиска минимального разреза в графе. Специально для такого рода задач был предложен метод нахождения разреза минимальной стоимости [https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CDQQFjAB&url=http%3A%2F%2Fwww.cs.berkeley.edu%2F~malik%2Fpapers%2FSM-ncut.pdf&ei=cP2-UuqhAuSJ4gTnhYCwAg&usg=AFQjCNFn9GZPlFjDUgDofCScu6Wm47qMWQ&sig2=Yufd8LreEQKHe3NGnFVm7A&bvm=bv.58187178,d.bGE&cad=rjt Normalized Cut (J. Shi, J. Malik (1997))]
 +
 +
  
 
== Источники ==
 
== Источники ==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: