Изменения
→Графо-ориентированная сегментация (англ. Graph-based segmentation)
== Графо-ориентированная сегментация (англ. Graph-based segmentation) ==
Это алгоритм объединения, который использует относительные различия между регионами, чтобы определить, какие из них следует объединить. Кроме того, он доказуемо оптимизирует глобальную метрику группировки. Введем ''меру отличия'' одного пикселя от другого <tex>w(e)</tex>, где <tex>e = (v_1, v_2)</tex> {{---}} пара соседних по стороне или по углу пикселей. ''Мера отличия'' может показывать, например, разницу цветовой интенсивности между соседями, которых у пикселя максимум восемь.
Для любого региона ''R'', его внутренняя разница определяется как наибольшая ''мера отличия'' в минимальном остовном дереве региона,
Алгоритм объединяет любые две соседние области, разница которых меньше минимальной внутренней разности этих двух областей,
<br><center><tex>MInt(R_1, R_2) = \min(Int(R_1) + \tau(R_1), Int(R_2) +\tau(R_2)),</tex></center>
где <tex>\tau(R)</tex> {{---}} это эвристический штраф по региону, который был установлен <tex>k / |R|</tex>, однако, он может быть установлен как любая специфическая для области применения мера.
Объединяя области в порядке убывания разделяющих их ребер (можно эффективно оценить с использованием алгоритма минимального остовного дерева Крускала), они доказуемо дают сегментацию. Причем такую, в которой присутствуют как области, которые могли бы быть объединены, так и те, которые могут быть разделены, но в небольших количествах. Для окрестностей пикселей фиксированного размера время работы этого алгоритма составляет <tex>O (N \log N)</tex>, где <tex>N</tex> - количество пикселей изображения, что делает его одним из самых быстрых алгоритмов сегментации.
