Изменения
→Графо-ориентированная сегментация
<br>На рисунке слева - исходное изображение, справа - сегментированное после применения данного алгоритма.
<br>Данный алгоритм был представлен в статье Felzenszwalb, P. F. and Huttenlocher, D. P. (2004b). Efficient graph-based image segmentation.[http://people.cs.uchicago.edu/~pff/papers/seg-ijcv.pdf]
== Метод нормализованных срезов ==
Mетод нормализованных срезов, исследует сходство между соседними пикселями и пытается разделить их на группы, которые в свою очередь связаны слабо.
Рассмотрим простой пример.
[[Файл:graphNormalizedCut.png]]
<br>Все пиксели в группе A имеют высокое сходство, показаное в виде толстых красных линий, как и пиксели в группе B. Соединения между этими двумя группами, показанные в виде более тонких синих линий, намного слабее. ''Нормализованный разрез'' между двумя группами, показанный пунктирной линией, разделяет их на два кластера.
Разрез между двумя группами A и B определяется как сумма всех взвешенных весов,
<br><center><tex>cut(A, B) = \displaystyle\sum_{i \in A, j \in B}w_{ij},</tex></center>
где веса между двумя пикселями <tex>i</tex> и <tex>j</tex> соответствуют их сходству. Однако использование минимального среза в качестве критерия сегментации не приводит к разумным кластерам, поскольку наименьшие срезы обычно предусматривают выделение одного пикселя.
Лучшей мерой сегментации является нормализованный срез, который определяется как
<br><center><tex>Ncut(A,B)=\frac{cut(A,B)}{assoc(A, V)}+\frac{cut(A,B)}{assoc(B,V)},</tex></center>
где <tex>assoc(A,A)=\sum_{i \in A, j \in A}w_{ij}</tex> это ''ассоциациея'' (сумма всех весов) в кластере и <tex>assoc(A,V)=assoc(A,A)+cut(A,B)</tex>
