77
правок
Изменения
Нет описания правки
'''Сегментация изображения''' {{---}} это задача поиска групп пикселей, каждая из которых характеризует один смысловой объект. В статистике эта проблема известна как кластерный анализ и является широко изученной областью с сотнями различных алгоритмов. В компьютерном зрении сегментация изображения является одной из старейших и широко изучаемых проблем.
В более ранних техниках используется ''расщепление'' и ''слияние'' регионов, что соответствует ''разделительным'' и ''агломерационным'' алгоритмам в литературе по кластеризации [[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8FКластеризация|кластеризации]]. Современные алгоритмы чаще оптимизируют некоторые глобальные критерии, такие как внутрирегиональная согласованность и межрегиональные длины границ. Ниже будут рассмотрены два алгоритма {{---}} графо-ориентированная сегментация и метод нормализованных срезов. Первый из них является базовым алгоритмом сегментации, который прост и понятен в реализации, но медленный и результаты недостаточно хороши. Второй алгоритм является продвинутой версией первого со множеством эвристик. Что отражается, как на производительности, так и на результатах.
== Графо-ориентированная сегментация (англ. Graph-based segmentation) ==
Для любого региона ''R'', его внутренняя разница определяется как наибольшая ''мера отличия'' в минимальном остовном дереве региона,
<br><center><tex>Int(R) = \displaystyle\min_{e \in MST(R)} w(e).</tex></center>,
Для любых двух соседних областей, по крайней мере, с одним смежным ребром, соединяющим их вершины, разность между этими регионами определяется как ребро минимального веса, соединяющее эти два региона,
<br><center><tex>Dif(R_1, R_2) = \displaystyle\min_{e = (v_1, v_2) | v_1 \in R_1, v_2 \in R_2} w(e).</tex></center>,
Алгоритм объединяет любые две соседние области, разница которых меньше минимальной внутренней разности этих двух областей,
<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> {{- --}} количество пикселей изображения, что делает его одним из самых быстрых алгоритмов сегментации.<br><center>[[Файл:beforeAfterGraphBased.png]]</|800px|thumb|center><br>На рисунке слева - исходное изображение, справа - сегментированное после применения данного алгоритма.<br>Данный алгоритм был представлен в статье |Источник: Felzenszwalb, P. F. and Huttenlocher, D. P. (2004b). Efficient «Efficient graph-based image segmentation.»[http://people.cs.uchicago.edu/~pff/papers/seg-ijcv.pdf]]]</center><br>На рисунке слева {{---}} исходное изображение, справа {{---}} сегментированное после применения данного алгоритма.
== Метод нормализованных срезов (англ. Normalized cuts) ==
Mетод нормализованных срезов, исследует сходство между соседними пикселями и пытается разделить их на группы, которые в свою очередь связаны слабо.
Рассмотрим простой пример.
[[Файл:graphNormalizedCut.png|800px|thumb|center|Источник: Richard Szeliski «Computer Vision: Algorithms and Applications.»[http://szeliski.org/Book/drafts/SzeliskiBook_20100903_draft.pdf]]]<br>Все пиксели в группе A имеют высокое сходство, показаное показанное в виде толстых красных линий, как и пиксели в группе B. Соединения между этими двумя группами, показанные в виде более тонких синих линий, намного слабее. ''Нормализованный разрез'' между двумя группами, показанный пунктирной линией, разделяет их на два кластера.
Разрез между двумя группами A и B определяется как сумма всех взвешенных весов,
Лучшей мерой сегментации является нормализованный срез, который определяется как
<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> это сумма всех весов ассоциированных с <tex>А</tex>. <br>Нормализованные разрезы могут быть довольно медленными, поскольку это требует решения больших разреженных задач. Однако существует способ ускорить вычисление нормализованных разрезов, используя подход, основанный на алгебраической сетке. Можно выбирать меньшее количество переменных, чтобы оставшиеся переменные более нижнего уровня были ''сильно связаны'' по крайней мере с одной переменной грубого уровня. Подмножество <tex>C \subset V</tex> считается ''сильно связанымсвязанным'', если выполняется<br><center><tex>\frac{\sum_{j \in C}w_{ij}}{\sum_{j \in V}w_{ij}} > \phi,[*]</tex></center>
обычно <tex>\phi = 0.2.</tex> Данный рисунок схематично показывает этот процесс.
[[Файл:grephEdges.png]], где |880px|thumb|center|''на первом изображении'' {{--- }} исходная пиксельная сетка черно-белого изображения; ''на втором'' {{-- -}} межпиксельные связи, где более толстые линии указывают на более сильные связи; ''на третьем'' {{--- }} сетка после одного уровня огрубления, когда каждый исходный пиксель сильно связан с одним из узлов грубого уровня; ''на четвертом'' {{- --}} после двух уровней огрубления.Источник: Shaw, D. and Barnes, N. «Perspective rectangle detection. In Workshop on Applications of Computer Vision.» [https://www.researchgate.net/publication/6975028_Hierarchy_and_adaptivity_in_segmenting_visual_scenes]]]
Результат работы данного алгоритма:
[[Файл:bear1watches.png]] |880px|thumb|center|Источник: Shaw, D. and Barnes, N. «Perspective rectangle detection. In Workshop on Applications of Computer Vision.» [[Файлhttps:bear2//www.pngresearchgate.net/publication/6975028_Hierarchy_and_adaptivity_in_segmenting_visual_scenes]]]
== См. также ==
[[Категория: Машинное обучение]]
[[Категория: Computer visionКомпьютерное зрение]]