77
правок
Изменения
Нет описания правки
'''Сегментация изображения''' {{---}} это задача поиска групп пикселей, каждая из которых характеризует один смысловой объект. В статистике эта проблема известна как кластерный анализ и является широко изученной областью с сотнями различных алгоритмов. В компьютерном зрении сегментация изображения является одной из старейших и широко изучаемых проблем.
В более ранних техниках используется ''расщепление'' и ''слияние'' регионов, что соответствует ''разделительным'' и ''агломерационным'' алгоритмам в литературе по [[Кластеризация|кластеризации]]. Современные алгоритмы чаще оптимизируют некоторые глобальные критерии, такие как внутрирегиональная согласованность и межрегиональные длины границ.
Для любого региона ''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|Источник: Felzenszwalb, P. F. and Huttenlocher, D. P. «Efficient graph-based image segmentation.»[http://people.cs.uchicago.edu/~pff/papers/seg-ijcv.pdf]]]</center>
<br>На рисунке слева {{- --}} исходное изображение, справа {{--- }} сегментированное после применения данного алгоритма.
== Метод нормализованных срезов (англ. Normalized cuts) ==
Рассмотрим простой пример.
[[Файл: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]]]
Каждый пиксель на первом изображении соответствует вершине графа на втором изображении, которая связа связана с каждым из ее четырех соседей в соответствии с их сходством по уровню яркости. Цель состоит в том, чтобы «разрезать» этот граф на части. Далее можно найти ''сильно связное'' подмножество, которое минимизирует отношение <tex>[*]</tex>. Но несмотря на свою концептуальную значимость, минимизация этого ''нормализованного разреза'' является вычислительно непомерной, а стоимость увеличивается экспоненциально с размером изображения. Приближения к оптимальному разрезу могут быть получены с использованием спектральных методов, при этом наиболее эффективное на сегодняшний день приближение имеет вычислительную стоимость, пропорциональную <tex>n^{\frac{2}{3}}</tex>, где <tex>n</tex> {{---}} количество пикселей. Эта сверхлинейная сложность может быть чрезвычайно полезна, когда дело касается очень больших изображений.
Так как количество вершин графа на втором изображении велико и работать с каждым из них чрезвычайно дорого, необходимо выделить подмножество вершин-предводителей для каждого из подможеств подмножеств и далее работать уже с ними. Мы начнем с выбора примерно половины пикселей в качестве представителей, которые назовем ''начальными числами'': они выбираются таким образом, чтобы каждый пиксель в исходном изображении был ''сильно связан'' по крайней мере с одним соседним с ним ''начальным числом'' (см. третье изображение). Далее процесс продолжается рекурсивно (см. четвертое изображжениеизображение), количество вершин на каждом новом более грубом уровне уменьшается. Значения узлов более нижнего уровня вычисляются путем интерполяции родительских значений и сопоставления значений <tex> \epsilon = 0,1</tex> в пределах от 0 и 1 до Boolean значений. Выраженные сегменты появляются на соответствующем уровне как узлы, которые слабо связаны со своими соседями. Следовательно, задача минимизации упрощается до поиска вершин-предводителей на всех уровнях.
Результат работы данного алгоритма:
