38
правок
Изменения
→Метод нормализованных срезов (англ. Normalized cuts)
где <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>n^{\frac{2}{3}}</tex>.
Как только набор грубых переменных был выбран, межуровневая интерполяционная матрица с элементами, подобными <tex>\frac{\sum_{j \in C}w_{ij}}{\sum_{j \in V}w_{ij}}</tex>, используется для определения сокращенной версии задачи ''нормализованных разрезов''. В дополнение к вычислению матрицы весов с использованием интерполяции используются дополнительные статистические данные области для модуляции весов. После того, как ''нормализованный разрез'' был вычислен на самом грубом уровне, значения узлов более нижнего уровня вычисляются путем интерполяции родительских значений и сопоставления значений <tex> \epsilon = 0,1</tex> в пределах от 0 и 1 до Boolean значений.
