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

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

Приложения сегментации изображений

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

Сегментация с использованием нормализованных разрезов

Теоретико-графовая формулировка

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

Нормализованные разрезы

Пусть G = ( V , E , w ) — взвешенный граф. Позволять $A$ и $B$ быть двумя подмножествами вершин.

Позволять:

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

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

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

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

С $\operatorname {ncut} (S,{\overline {S}})=2-\operatorname {nassoc} (S,{\overline {S}})$ , разрез $(S^{*},{\overline {S}}^{*})$ что сводит к минимуму $\operatorname {ncut} (S,{\overline {S}})$ также максимизирует $\operatorname {nassoc} (S,{\overline {S}})$ .

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

Алгоритм ncut

Позволять:

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

Кроме того, пусть D будет $n\times n$ диагональная матрица с $d$ по диагонали, и пусть $W$ быть $n\times n$ симметричная матрица с $w_{ij}=w_{ji}$ .

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

\min \limits _{(S,{\overline {S}})}\operatorname {ncut} (S,{\overline {S}})=\min \limits _{y}{\frac {y^{T}(D-W)y}{y^{T}Dy}}

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

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

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

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

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

Вычислительная сложность

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

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

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

Реализации программного обеспечения

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

ОБЖ ВЫРЕЗАТЬ

ОБЖ ВЫРЕЗАТЬ ^[7] — эффективный метод, который автоматически сегментирует объект. Метод OBJ CUT является универсальным методом и поэтому применим к любой модели категории объектов. Учитывая изображение D, содержащее экземпляр известной категории объектов, например коров, алгоритм OBJ CUT вычисляет сегментацию объекта, то есть выводит набор меток m .

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

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)

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

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

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

(2)

Алгоритм

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

Другие подходы

Головоломный подход ^[8]
Разбор изображений ^[9]
Чередованная сегментация ^[10]
ЛОКУС ^[11]
МакетCRF ^[12]
Сегментация на основе минимального связующего дерева

Ссылки

^ Лопес, Клелия; Леклерк, Людовик; Кришнакумари, Панчами; Чиабо, Николя; Ван Линт, Ганс (25 октября 2017 г.). «Выявление повседневной регулярности городских заторов с помощью 3D-карт скорости» . Научные отчеты . 7 (14029): 14029. Бибкод : 2017NatSR...714029L . дои : 10.1038/s41598-017-14237-8 . ПМЦ 5656590 . ПМИД 29070859 .
^ Цзянбо Ши и Джитендра Малик (1997): «Нормализованные разрезы и сегментация изображений», Конференция IEEE по компьютерному зрению и распознаванию образов, стр. 731–737.
^ «Спектральная кластеризация — учебная документация» .
^ Князев, Андрей Васильевич (2003). Боли; Диллон; Гоша; Коган (ред.). Современные предварительно подготовленные собственные решатели для спектральной сегментации изображений и деления графа пополам . Кластеризация больших наборов данных; Третья Международная конференция IEEE по интеллектуальному анализу данных (ICDM 2003) Мельбурн, Флорида: Компьютерное общество IEEE. стр. 59–62.
^ Князев, Андрей В. (2006). Многомасштабная сегментация спектрального изображения. Многомасштабная предварительная подготовка для вычисления собственных значений лапласианов графа при сегментации изображений . Семинар по быстрому изучению многообразий, В.М. Вильямбург, Вирджиния. дои : 10.13140/RG.2.2.35280.02565 .
^ Князев, Андрей В. (2006). Многомасштабное разбиение спектрального графа и сегментация изображений . Семинар по алгоритмам обработки современных массивных наборов данных Стэнфордского университета и Yahoo! Исследовать.
^ Член парламента Кумар, PHS Торр и А. Зиссерман. Объект вырезается. В материалах конференции IEEE по компьютерному зрению и распознаванию образов , Сан-Диего, страницы 18–25, 2005 г.
^ Э. Боренштейн, С. Ульман: Классовая сегментация сверху вниз . В материалах 7-й Европейской конференции по компьютерному зрению, Копенгаген, Дания, страницы 109–124, 2002 г.
^ З. Ту, X. Чен, А. Л. Юйл, С. К. Чжу: Анализ изображений: объединение сегментации, обнаружения и распознавания . На пути к распознаванию объектов на уровне категорий, 2006 г.: 545–576.
^ Б. Лейбе, А. Леонардис, Б. Шиле: неявная модель формы для комбинированной категоризации и сегментации объектов . На пути к распознаванию объектов на уровне категорий, 2006 г.: 508–524.
^ Дж. Винн, Н. Йойич. Локус: изучение классов объектов с неконтролируемой сегментацией . В материалах Международной конференции IEEE по компьютерному зрению, Пекин, 2005 г.
^ Дж. М. Винн, Дж. Шоттон: Согласованное по макету случайное поле для распознавания и сегментации частично закрытых объектов . ЦВПР (1) 2006: 37–44.

[1] Лопес, Клелия; Леклерк, Людовик; Кришнакумари, Панчами; Чиабо, Николя; Ван Линт, Ганс (25 октября 2017 г.). «Выявление повседневной регулярности городских заторов с помощью 3D-карт скорости» . Научные отчеты . 7 (14029): 14029. Бибкод : 2017NatSR...714029L . дои : 10.1038/s41598-017-14237-8 . ПМЦ 5656590 . ПМИД 29070859 .

[2] Цзянбо Ши и Джитендра Малик (1997): «Нормализованные разрезы и сегментация изображений», Конференция IEEE по компьютерному зрению и распознаванию образов, стр. 731–737.

[3] «Спектральная кластеризация — учебная документация» .

[4] Князев, Андрей Васильевич (2003). Боли; Диллон; Гоша; Коган (ред.). Современные предварительно подготовленные собственные решатели для спектральной сегментации изображений и деления графа пополам . Кластеризация больших наборов данных; Третья Международная конференция IEEE по интеллектуальному анализу данных (ICDM 2003) Мельбурн, Флорида: Компьютерное общество IEEE. стр. 59–62.

[5] Князев, Андрей В. (2006). Многомасштабная сегментация спектрального изображения. Многомасштабная предварительная подготовка для вычисления собственных значений лапласианов графа при сегментации изображений . Семинар по быстрому изучению многообразий, В.М. Вильямбург, Вирджиния. дои : 10.13140/RG.2.2.35280.02565 .

[6] Князев, Андрей В. (2006). Многомасштабное разбиение спектрального графа и сегментация изображений . Семинар по алгоритмам обработки современных массивных наборов данных Стэнфордского университета и Yahoo! Исследовать.

[7] Член парламента Кумар, PHS Торр и А. Зиссерман. Объект вырезается. В материалах конференции IEEE по компьютерному зрению и распознаванию образов , Сан-Диего, страницы 18–25, 2005 г.

[8] Э. Боренштейн, С. Ульман: Классовая сегментация сверху вниз . В материалах 7-й Европейской конференции по компьютерному зрению, Копенгаген, Дания, страницы 109–124, 2002 г.

[9] З. Ту, X. Чен, А. Л. Юйл, С. К. Чжу: Анализ изображений: объединение сегментации, обнаружения и распознавания . На пути к распознаванию объектов на уровне категорий, 2006 г.: 545–576.

[10] Б. Лейбе, А. Леонардис, Б. Шиле: неявная модель формы для комбинированной категоризации и сегментации объектов . На пути к распознаванию объектов на уровне категорий, 2006 г.: 508–524.

[11] Дж. Винн, Н. Йойич. Локус: изучение классов объектов с неконтролируемой сегментацией . В материалах Международной конференции IEEE по компьютерному зрению, Пекин, 2005 г.

[12] Дж. М. Винн, Дж. Шоттон: Согласованное по макету случайное поле для распознавания и сегментации частично закрытых объектов . ЦВПР (1) 2006: 37–44.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]