Efficient Graph-Based Image Segmentation

Связано с этой статьей

Paper Summary:GitHub.com/FD U-vt S/CV P…
Code:GitHub.com/FD U-vt S/CVC…

Оригинальная ссылка

У-у-у, в это время, Корнелл, квота/~динамический баланс/бумаги…

Базовые знания

Изображение состоит из разных точек пикселей Расчет и построение этой статьи основаны на работе точек пикселей, т.е.(RGB)ценность
Размытие по Гауссу/Преобразование Лапласа: алгоритмы сглаживания для преобразования изображений, уменьшения шума изображения.
минимальное остовное дерево(Minimum Spanning Tree | MST)Относится к установлению связного графа в графе, и ни одна петля не является остовным деревом, а минимальное остовное дерево относится к минимальному весу результата.
Разница между разными пикселями: а именноRGBЕвклидово расстояние между значениями
- $\sqrt{(R_1-R_2)^2+(G_1-G_2)^2+(B_1-B_2)^2}$
Алгоритм набора поиска объединения (набор поиска объединения) и алгоритм Краскала (Крускал), используйте край для построения набора поиска объединения и используйте kruskal для поиска и слияния

Методы ранней сегментации

Зан предложил * метод сегментации минимального остовного дерева (MST) * на основе графа для кластеризации точек и сегментации изображения.Первый вес - это расстояние между точками, а второй вес - разница в пикселях.
Недостаток: в зависимости от порога, это приведет к тому, что область с высокой изменчивостью (около области с сильным цветовым контрастом) будет разделена на несколько областей; линейная и постоянная области объединяются вместе.
Уркхарт предложил нормировать точки с наименьшим весом ребра среди точек, соединенных ребром, и находить окружение подобным.
В зависимости от того, соответствует ли каждая область определенному стандарту однородности, она делится на области с одинаковой интенсивностью или градиентом, что не подходит для области с большим разбросом.
Кластеризация с использованием пространства признаков: путем сглаживания данных — гиперсфера заданного радиуса расширяет свой связанный компонент в каждой точке, находит кластеры, сохраняет границы региона и преобразует данные.

Сегментация на основе графа

определение

G: преобразование изображения из пикселей в графики.
V: каждый пиксель представляет собой точку на изображении.
E: граница между любыми двумя соседними пикселями
C: разделенныйSegmentation,ОдинCимеет по крайней мере 1 пиксель
Int(C): Ребро с наибольшим весом минимального остовного дерева в регионе, что означает, что оно записывается как
- $Int(C) = \max{w(e)} , e∈MST(C，E)$
Dif(C1,C2): представляет собой расстояние между C1 и C2, обозначаемое как
- $Dif(C1,C2) = \min{w(vi,vj)} ,vi∈C1,vj∈C2,(vi,vj)∈E$
Окончательное требование к группировке, которое необходимо сформировать (с указанием того, что минимальное расстояние между всеми регионами больше, чем сумма максимального расстояния и веса в пределах региона)
- $D(C1,C2)=\left\{\begin{aligned}true, & & \ ifDif(C1,C2)>MInt(C1,C2) \\false, & & \ otherwise\end{aligned}\right.$
вMInt(C1,C2)Значение:
Причина настройки порога заключается в том, что в начале, поскольку имеется только одна точка пикселя, расстояние внутри точки равно 0, а расстояние между точками все еще существует, поэтому их нельзя объединить. Так что добавь порог.

Алгоритм разделения (тесно связанный с алгоритмом Крускала для построения минимального остовного дерева).

Вход — граф G с n узлами и m ребрами, а выход — последовательность областей. Действуйте следующим образом:
0. Сортировать ребра по значению веса в неубывающем порядке
1. Начальная сегментация обозначается как S(0), т. е. каждый узел принадлежит области.
2. Постройте S(q) из S(q-1) следующим образом: обозначим два узла, соединенных q-м ребром, как vi и vj, если в S(q-1) vi и vj принадлежат двум двум областям и вес q-го ребра меньше, чем внутрирегиональное расстояние между двумя областями, затем объединить две области. В противном случае пусть S(q) = S(q-1).
3. Повторите шаг 2 от q=1 до q=m.
4. Возвратите S(m) как требуемый набор разделенных областей.

Пополнить

фильтр Гаусса

Преобразование Гаусса заключается в свертывании изображения с помощью функции Гаусса.Фильтр Гаусса представляет собой линейный фильтр, который может эффективно подавлять шум и сглаживать изображение. Суть его в том, чтобы на выходе взять среднее значение пикселей в окне фильтра.
Формула функции Гаусса выглядит следующим образом:
- $f(x) = \frac{1}{\sigma\sqrt{2\pi}}e^{\frac{(x-\mu)^2}{2\sigma^2}}$ в,uдаxсреднее значение ,σэто дисперсия.
Из одномерной функции мы можем вывести формулу двумерной функции следующим образом:
- $f(x,y) = \frac{1}{2\pi \sigma^2} e^{-\frac{(x^2+y^2)}{2\sigma^2} }$
Использование функции Гаусса при обработке изображений фактически заключается в том, чтобы взять среднее значение окружающих пикселей каждого пикселя, чтобы добиться эффекта сглаживания.Размытость сильнее. В реальных вычислениях размытие по Гауссу используется для распределения веса окружающих пикселей в соответствии с кривой нормали, чтобы получить средневзвешенное значение центральной точки.
Конкретный метод расчета размытия по Гауссу выглядит следующим образом:
- 1. Внесите восемь точек вокруг центральной точки в функцию Гаусса, чтобы получить весовую матрицу A1;
- 2. Для нормализации разделить каждую точку в матрице A1 на сумму весов всех точек (9 баллов), чтобы получить нормализованную матрицу весов A2;
- 3. Исходная пиксельная матрица изображения умножается на соответствующие значения веса в A2, а полученные значения всех точек складываются и усредняются для получения значения размытия по Гауссу центральной точки. Аналогично рассчитываются остальные точки на изображении.
- Примечание: 1. Для цветных изображений размытие по Гауссу может быть применено к трем каналам RGB соответственно.
2.σпредставляет собой степень разброса данных,σЧем больше значение, тем меньше центральный коэффициент и тем ровнее изображение, и наоборот.

Преобразование Лапласа: оно предназначено для устранения недостатков преобразования Фурье равноамплитудных колебаний.

Сначала поймите преобразование Фурье: преобразование Фурье — это способ физического исследования спектра.Тригонометрическая формула:
- $f(t) = \sum_{n=1}^\infty A_ncos(nw_0t+\varphi_n)+B$
- в,w0представляет основную волну.
По формуле Эйлера:
- $\left\{\begin{aligned}e^{ix} =cosx+isinx, \\e^{-ix} =cosx -isinx,\end{aligned}\right.$
Функции синуса и косинуса в формуле треугольника Фурье выражаются экспоненциальными функциями и переписываются в виде формул, выраженных комплексными экспонентами, следующим образом:
- $f(t) = \sum_{-\infty}^\infty F(nw_0)e^{jw_0t}$
Преобразуйте приведенную выше формулу в интегральную форму, то есть формулу сложной экспоненциальной формы:
- $F(w) =\int_{-\infty}^\infty f(t)e^{-jwt}dt$
Однако, поскольку преобразование Фурье представляет собой синусоиду с колебаниями постоянной амплитуды, когда f(t) продолжает стремиться к бесконечности, функция больше не будет сходиться в это время, и в это время больше нельзя использовать преобразование Фурье. . Поэтому мы вводим коэффициент затухания, чтобы преобразовать его. Умножьте функцию y=f(t) на единицу,в,σ>0.
- $F(w) =\int_{-\infty}^\infty f(t)e^{-\sigma t}e^{-jwt}dt$
Комбинируя подобные члены в приведенной выше формуле, мы можем получить $F(w) =\int_{-\infty}^\infty f(t)e^{-t(\sigma+jw)}dt$
Мы проиндексируемσ+jwНачальное деление обозначается как S, поэтому получается формула Лапласа:
- $\Rightarrow$ $F(w) =\int_{-\infty}^\infty f(t)e^{-st}dt$
Из приведенной выше формулы ясно, что когда s=jw, функция Лапласа становится функцией Фурье, что эквивалентно тому, что у Лапласа больше нет функции затухания.
Из приведенной выше формулы интуитивно видно, что при значении $\sigma_0$ Когда только сошлись, то $\sigma$ > $\sigma_0$ все регионы сходятся.