Сегментация изображений

Сегментация изображения — это задача поиска групп пикселей, каждая из которых характеризует один смысловой объект. В статистике эта проблема известна как кластерный анализ и является широко изученной областью с сотнями различных алгоритмов. В компьютерном зрении сегментация изображения является одной из старейших и широко изучаемых проблем.

В более ранних техниках используется расщепление и слияние регионов, что соответствует разделительным и агломерационным алгоритмам в литературе по кластеризации [|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%7C]. Современные алгоритмы чаще оптимизируют некоторые глобальные критерии, такие как внутрирегиональная согласованность и межрегиональные длины границ.

Ниже будут рассмотрены два алгоритма — графо-ориентированная сегментация и метод нормализованных срезов. Первый из них является базовым алгоритмом сегментации, который прост и понятен в реализации, но медленный и результаты недостаточно хороши. Второй алгоритм является продвинутой версией первого со множеством эвристик. Что отражается, как на производительности, так и на результатах.

Графо-ориентированная сегментация (англ. Graph-based segmentation)

Это алгоритм объединения, который использует относительные различия между регионами, чтобы определить, какие из них следует объединить. Кроме того, он доказуемо оптимизирует глобальную метрику группировки. Введем меру отличия одного пикселя от другого [math]w(e)[/math], где [math]e = (v_1, v_2)[/math] — пара соседних по стороне или по углу пикселей. Мера отличия может показывать, например, разницу цветовой интенсивности между соседями, которых у пикселя максимум восемь.

Для любого региона R, его внутренняя разница определяется как наибольшая мера отличия в минимальном остовном дереве региона,

[math]Int(R) = \displaystyle\min_{e \in MST(R)} w(e).[/math]

Для любых двух соседних областей, по крайней мере, с одним смежным ребром, соединяющим их вершины, разность между этими регионами определяется как ребро минимального веса, соединяющее эти два региона,

[math]Dif(R_1, R_2) = \displaystyle\min_{e = (v_1, v_2) | v_1 \in R_1, v_2 \in R_2} w(e).[/math]

Алгоритм объединяет любые две соседние области, разница которых меньше минимальной внутренней разности этих двух областей,

[math]MInt(R_1, R_2) = \min(Int(R_1) + \tau(R_1), Int(R_2) +\tau(R_2)),[/math]

где [math]\tau(R)[/math] — это эвристический штраф по региону, который был установлен [math]k / |R|[/math], однако, он может быть установлен как любая специфическая для области применения мера.

Объединяя области в порядке убывания разделяющих их ребер (можно эффективно оценить с использованием алгоритма минимального остовного дерева Крускала), они доказуемо дают сегментацию. Причем такую, в которой присутствуют как области, которые могли бы быть объединены, так и те, которые могут быть разделены, но в небольших количествах. Для окрестностей пикселей фиксированного размера время работы этого алгоритма составляет [math]O (N \log N)[/math], где [math]N[/math] - количество пикселей изображения, что делает его одним из самых быстрых алгоритмов сегментации.

Источник: Felzenszwalb, P. F. and Huttenlocher, D. P. «Efficient graph-based image segmentation.»[1]

На рисунке слева - исходное изображение, справа - сегментированное после применения данного алгоритма.

Метод нормализованных срезов (англ. Normalized cuts)

Mетод нормализованных срезов, исследует сходство между соседними пикселями и пытается разделить их на группы, которые в свою очередь связаны слабо. Рассмотрим простой пример.

Источник: Richard Szeliski «Computer Vision: Algorithms and Applications.»[2]

Все пиксели в группе A имеют высокое сходство, показаное в виде толстых красных линий, как и пиксели в группе B. Соединения между этими двумя группами, показанные в виде более тонких синих линий, намного слабее. Нормализованный разрез между двумя группами, показанный пунктирной линией, разделяет их на два кластера.

Разрез между двумя группами A и B определяется как сумма всех взвешенных весов,

[math]cut(A, B) = \displaystyle\sum_{i \in A, j \in B}w_{ij},[/math]

где веса между двумя пикселями [math]i[/math] и [math]j[/math] соответствуют их сходству. Однако использование минимального среза в качестве критерия сегментации не приводит к разумным кластерам, поскольку наименьшие срезы обычно предусматривают выделение одного пикселя.

Лучшей мерой сегментации является нормализованный срез, который определяется как

[math]Ncut(A,B)=\frac{cut(A,B)}{assoc(A, V)}+\frac{cut(A,B)}{assoc(B,V)},[/math]

где [math]assoc(A,A)=\sum_{i \in A, j \in A}w_{ij}[/math] это ассоциациея (сумма всех весов) в кластере и [math]assoc(A,V)=assoc(A,A)+cut(A,B)[/math] это сумма всех весов ассоциированных с [math]А[/math].
Нормализованные разрезы могут быть довольно медленными, поскольку это требует решения больших разреженных задач. Однако существует способ ускорить вычисление нормализованных разрезов, используя подход, основанный на алгебраической сетке. Можно выбирать меньшее количество переменных, чтобы оставшиеся переменные более нижнего уровня были сильно связаны по крайней мере с одной переменной грубого уровня. Подмножество [math]C \subset V[/math] считается сильно связаным, если выполняется

[math]\frac{\sum_{j \in C}w_{ij}}{\sum_{j \in V}w_{ij}} \gt \phi, [*][/math]

обычно [math]\phi = 0.2.[/math] Данный рисунок схематично показывает этот процесс.

на первом изображении — исходная пиксельная сетка черно-белого изображения; на втором — межпиксельные связи, где более толстые линии указывают на более сильные связи; на третьем — сетка после одного уровня огрубления, когда каждый исходный пиксель сильно связан с одним из узлов грубого уровня; на четвертом — после двух уровней огрубления. Источник: Shaw, D. and Barnes, N. «Perspective rectangle detection. In Workshop on Applications of Computer Vision.» [3]

Каждый пиксель на первом изображении соответствует вершине графа на втором изображении, которая связа с каждым из ее четырех соседей в соответствии с их сходством по уровню яркости. Цель состоит в том, чтобы «разрезать» этот граф на части. Далее можно найти сильно связное подмножество, которое минимизирует отношение [math][*][/math]. Но несмотря на свою концептуальную значимость, минимизация этого нормализованного разреза является вычислительно непомерной, а стоимость увеличивается экспоненциально с размером изображения. Приближения к оптимальному разрезу могут быть получены с использованием спектральных методов, при этом наиболее эффективное на сегодняшний день приближение имеет вычислительную стоимость, пропорциональную [math]n^{\frac{2}{3}}[/math], где [math]n[/math] — количество пикселей. Эта сверхлинейная сложность может быть чрезвычайно полезна, когда дело касается очень больших изображений.

Так как количество вершин графа на втором изображении велико и работать с каждым из них чрезвычайно дорого, необходимо выделить подмножество вершин-предводителей для каждого из подможеств и далее работать уже с ними. Мы начнем с выбора примерно половины пикселей в качестве представителей, которые назовем начальными числами: они выбираются таким образом, чтобы каждый пиксель в исходном изображении был сильно связан по крайней мере с одним соседним с ним начальным числом (см. третье изображение). Далее процесс продолжается рекурсивно (см. четвертое изображжение), количество вершин на каждом новом более грубом уровне уменьшается. Значения узлов более нижнего уровня вычисляются путем интерполяции родительских значений и сопоставления значений [math] \epsilon = 0,1[/math] в пределах от 0 и 1 до Boolean значений. Выраженные сегменты появляются на соответствующем уровне как узлы, которые слабо связаны со своими соседями. Следовательно, задача минимизации упрощается до поиска вершин-предводителей на всех уровнях.

Результат работы данного алгоритма:

Источник: Shaw, D. and Barnes, N. «Perspective rectangle detection. In Workshop on Applications of Computer Vision.» [4]

См. также

Задача нахождения объектов на изображении

Источники информации

• Richard Szeliski «Computer Vision: Algorithms and Applications.» - «Springer», 2010. - С. 286-300
• Felzenszwalb, P. F. and Huttenlocher, D. P. (2004b). Efficient graph-based image segmentation.[5]
• Shaw, D. and Barnes, N. (2006). Perspective rectangle detection. In Workshop on Applications of Computer Vision at ECCV’2006.
• Brandt, A. (1986). Algebraic multigrid theory: The symmetric case. Applied Mathematics and Computation, 19(1-4):23–56.