Категоризация объектов на основе сегментации

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

• Сжатие изображения
  • Сегментируйте изображение на однородные компоненты и используйте наиболее подходящий алгоритм сжатия для каждого компонента, чтобы улучшить сжатие.
• Медицинская диагностика
  • Автоматическая сегментация МРТ-изображений для выявления раковых участков.
• Картографирование и измерение
  • Автоматический анализ данных дистанционного зондирования со спутников для определения и измерения интересующих регионов.
• Транспорт
  • Разделение транспортной сети позволяет выделить регионы, характеризующиеся однородным состоянием трафика. ^[1]

Набор точек в произвольном пространстве признаков можно представить как взвешенный неориентированный полный граф G = (V, E), где узлы графа являются точками в пространстве признаков. Вес ребра является функцией сходства между узлами и . В этом контексте мы можем сформулировать задачу сегментации изображения как задачу разбиения графа, которая требует разбиения множества вершин , где, согласно некоторой мере, вершины в любом наборе имеют высокое сходство, а вершины в двух различных наборах имеют низкое сходство.${\displaystyle w_{ij}}$${\displaystyle (i,j)\in E}$${\displaystyle я}$${\displaystyle j}$${\displaystyle V_{1},\cdots,V_{k}}$${\displaystyle V}$${\displaystyle V_{i}}$${\displaystyle V_{i},V_{j}}$

Пусть G = ( V , E , w ) — взвешенный граф. Пусть и — два подмножества вершин.${\displaystyle А}$${\displaystyle Б}$

Позволять:

${\displaystyle w(A,B)=\sum \limits _{i\in A,j\in B}w_{ij}}$

${\displaystyle \operatorname {ncut} (A,B)={\frac {w(A,B)}{w(A,V)}}+{\frac {w(A,B)}{w(B ,В)}}}$

${\displaystyle \operatorname {nassoc} (A,B)={\frac {w(A,A)}{w(A,V)}}+{\frac {w(B,B)}{w(B ,В)}}}$

В подходе нормализованных разрезов ^[2] для любого разреза в измеряется сходство между различными частями и измеряется общее сходство вершин в одной и той же части.${\displaystyle (S,{\overline {S}})}$${\displaystyle G}$${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$${\displaystyle \operatorname {nassoc} (S,{\overline {S}})}$

Так как , разрез , который минимизирует, также максимизирует .${\displaystyle \operatorname {ncut} (S,{\overline {S}})=2-\operatorname {nassoc} (S,{\overline {S}})}$${\displaystyle (S^{*},{\overline {S}}^{*})}$${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$${\displaystyle \operatorname {nassoc} (S,{\overline {S}})}$

Вычисление разреза , который минимизирует, является NP-трудной задачей. Однако мы можем найти разрез с малым нормализованным весом за полиномиальное время, используя спектральные методы .${\displaystyle (S^{*},{\overline {S}}^{*})}$${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$${\displaystyle (S,{\overline {S}})}$${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$

Позволять:

${\displaystyle d(i)=\sum \limits _{j}w_{ij}}$

Также пусть D — диагональная матрица с на диагонали, и пусть — симметричная матрица с .${\displaystyle n\times n}$${\displaystyle д}$${\displaystyle W}$${\displaystyle n\times n}$${\displaystyle w_{ij}=w_{ji}}$

После некоторых алгебраических преобразований получаем:

${\displaystyle \min \limits _{(S,{\overline {S}})}\operatorname {ncut} (S,{\overline {S}})=\min \limits _{y}{\frac {y^{T}(DW)y}{y^{T}Dy}}}$

с учетом ограничений:

• ${\displaystyle y_{i}\in \{1,-b\}}$, для некоторой константы${\displaystyle -b}$
• ${\displaystyle y^{t}D1=0}$

Минимизация с учетом ограничений выше является NP-трудной . Чтобы сделать задачу разрешимой, мы ослабляем ограничения на и позволяем ей принимать действительные значения. Ослабленная задача может быть решена путем решения обобщенной задачи собственных значений для второго наименьшего обобщенного собственного значения.${\displaystyle {\frac {y^{T}(DW)y}{y^{T}Dy}}}$${\displaystyle у}$${\displaystyle (DW)y=\lambda Dy}$

Алгоритм разбиения:

1. Учитывая набор признаков, создайте взвешенный граф , вычислите вес каждого ребра и суммируйте информацию в и .${\displaystyle G=(V,E)}$${\displaystyle D}$${\displaystyle W}$
2. Найдите собственные векторы со вторыми наименьшими собственными значениями.${\displaystyle (D-W)y=\lambda Dy}$
3. Используйте собственный вектор со вторым по величине собственным значением для разбиения графа на две части (например, группировка по знаку).
4. Решите, следует ли разделить текущий раздел.
5. При необходимости рекурсивно разбейте сегментированные части.

Решение стандартной задачи собственных значений для всех собственных векторов ( например, с использованием алгоритма QR ) требует времени. Это непрактично для приложений сегментации изображений, где — количество пикселей в изображении.${\displaystyle O(n^{3})}$${\displaystyle n}$

Поскольку неразрезанный алгоритм использует только один собственный вектор, соответствующий второму наименьшему обобщенному собственному значению, эффективность может быть значительно улучшена, если решение соответствующей задачи на собственные значения выполняется безматричным способом , т. е. без явного манипулирования или даже вычисления матрицы W, как, например, в алгоритме Ланцоша . Методы без матриц требуют только функции, которая выполняет произведение матрицы на вектор для заданного вектора на каждой итерации. Для сегментации изображений матрица W обычно разрежена, с числом ненулевых элементов , поэтому такое произведение матрицы на вектор занимает время.${\displaystyle O(n)}$${\displaystyle O(n)}$

Для изображений с высоким разрешением второе собственное значение часто плохо обусловлено , что приводит к медленной сходимости итеративных решателей собственных значений, таких как алгоритм Ланцоша . Предварительная подготовка является ключевой технологией, ускоряющей сходимость, например, в методе LOBPCG без матриц . Вычисление собственного вектора с использованием оптимально предобусловленного метода без матриц требует времени, что является оптимальной сложностью, поскольку собственный вектор имеет компоненты.${\displaystyle O(n)}$${\displaystyle n}$

scikit-learn ^[3] использует LOBPCG из SciPy с алгебраической многосеточной предварительной подготовкой для решения задачи собственных значений для графового лапласиана, чтобы выполнить сегментацию изображения с помощью спектрального разбиения графа , как впервые было предложено в ^[4] и фактически протестировано в ^[5] и ^{[6] .}

OBJ CUT ^[7] — эффективный метод, который автоматически сегментирует объект. Метод OBJ CUT является универсальным методом, и поэтому он применим к любой модели категории объектов. При наличии изображения D, содержащего экземпляр известной категории объектов, например, коров, алгоритм OBJ CUT вычисляет сегментацию объекта, то есть выводит набор меток  m .

Пусть m — набор двоичных меток, а — параметр формы ( это априорная форма меток из модели слоистой графической структуры (LPS)). Функция энергии определяется следующим образом.${\displaystyle \Theta }$${\displaystyle \Theta }$${\displaystyle E(m,\Theta )}$

${\displaystyle E(m,\Theta )=\sum \phi _{x}(D|m_{x})+\phi _{x}(m_{x}|\Theta )+\sum \Psi _{xy}(m_{x},m_{y})+\phi (D|m_{x},m_{y})}$ (1)

Термин называется унарным термином, а термин называется парным термином. Унарный термин состоит из вероятности, основанной на цвете, и унарного потенциала, основанного на расстоянии от . Парный термин состоит из предшествующего и контрастного терминов .${\displaystyle \phi _{x}(D|m_{x})+\phi _{x}(m_{x}|\Theta )}$${\displaystyle \Psi _{xy}(m_{x},m_{y})+\phi (D|m_{x},m_{y})}$${\displaystyle \phi _{x}(D|m_{x})}$${\displaystyle \phi _{x}(m_{x}|\Theta )}$${\displaystyle \Theta }$${\displaystyle \Psi _{xy}(m_{x},m_{y})}$${\displaystyle \phi (D|m_{x},m_{y})}$

Лучшая маркировка минимизирует , где — вес параметра .${\displaystyle m^{*}}$${\displaystyle \sum \limits _{i}w_{i}E(m,\Theta _{i})}$${\displaystyle w_{i}}$${\displaystyle \Theta _{i}}$

${\displaystyle m^{*}=\arg \min \limits _{m}\sum \limits _{i}w_{i}E(m,\Theta _{i})}$ (2)

1. Для изображения D выбирается категория объекта, например, коровы или лошади.
2. Соответствующая модель ЛПС сопоставляется с D для получения образцов${\displaystyle \Theta _{1},\cdots ,\Theta _{s}}$
3. Целевая функция, заданная уравнением (2), определяется путем вычисления и использования${\displaystyle E(m,\Theta _{i})}$${\displaystyle w_{i}=g(\Theta _{i}|Z)}$
4. Целевая функция минимизируется с помощью одной операции MINCUT для получения сегментации m .

• Подход «пазла» ^[8]
• Анализ изображения ^[9]
• Перемежающаяся сегментация ^[10]
• ЛОКУС ^[11]
• МакетCRF ^[12]
• Сегментация на основе минимального остовного дерева