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

Segmentation-based object categorization

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

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

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

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

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

Набор точек в произвольном пространстве признаков может быть представлен как взвешенный неориентированный полный граф G = (V, E), где узлы графа являются точками в пространстве признаков. Вес края является функцией подобия между узлами и . В этом контексте мы можем сформулировать проблему сегментации изображения как проблему разделения графа, которая требует разделения множества вершин , где по некоторой мере вершины любого множества имеют большое сходство, а вершины в двух разных множествах имеют низкое сходство.

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

Позволять г = (V, E, ш) - взвешенный граф. Позволять и - два подмножества вершин.

Позволять:

В подходе нормализованных разрезов[2] для любого разреза в , измеряет сходство между разными частями, и измеряет общее сходство вершин в одной части.

поскольку , порез что сводит к минимуму также максимизирует .

Вычисление разреза что сводит к минимуму является NP-жесткий проблема. Однако мы можем найти за полиномиальное время разрез малой нормированной массы с помощью спектральные методы.

Алгоритм ncut

Позволять:

Кроме того, пусть D быть диагональная матрица с по диагонали, и пусть быть симметричная матрица с .

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

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

  • , для некоторой постоянной

Сведение к минимуму с учетом указанных выше ограничений NP-жесткий. Чтобы сделать проблему разрешимой, мы ослабляем ограничения на , и позвольте ему принимать реальные значения. Расслабленная задача может быть решена путем решения обобщенной задачи на собственные значения для второго наименьшего обобщенного собственного значения.

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

  1. Учитывая набор функций, настройте взвешенный график , вычислим вес каждого ребра и суммируем информацию в и .
  2. Решить для собственных векторов со вторыми наименьшими собственными значениями.
  3. Используйте собственный вектор со вторым наименьшим собственным значением, чтобы разбить граф на две части (например, группировать по знаку).
  4. Решите, следует ли разделить текущий раздел.
  5. При необходимости рекурсивно разбейте сегментированные части.

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

Решение стандартной задачи на собственные значения для всех собственных векторов (с использованием QR-алгоритм, например) берет время. Это непрактично для приложений сегментации изображений, где количество пикселей в изображении.

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

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

ОБРЕЗАТЬ

ОБРЕЗАТЬ[3] - эффективный метод, который автоматически сегментирует объект. Метод OBJ CUT - это общий метод, поэтому он применим к любой модели категории объектов. Дано изображение D, содержащее экземпляр известной категории объектов, например cows алгоритм OBJ CUT вычисляет сегментацию объекта, то есть выводит набор метокм.

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

(1)

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

Лучшая маркировка сводит к минимуму , где - вес параметра .

(2)

Алгоритм

  1. Для изображения D выбирается категория объекта, например коровы или лошади.
  2. Соответствующая модель LPS сопоставляется с D для получения образцов
  3. Целевая функция, задаваемая уравнением (2), определяется путем вычисления и используя
  4. Целевая функция минимизируется с помощью одного MINCUT операция для получения сегментации м.

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

использованная литература

  1. ^ Лопес, Клелия; Леклерк, Людовик; Кришнакумари, Панчами; Чиабаут, Николас; Ван Линт, Ханс (25 октября 2017 г.). «Выявление повседневной закономерности городских заторов с помощью трехмерных карт скорости». Научные отчеты. 7 (14029): 14029. Дои:10.1038 / s41598-017-14237-8. ЧВК 5656590. PMID 29070859.
  2. ^ Цзяньбо Ши и Джитендра Малик (1997): «Нормализованные разрезы и сегментация изображений», Конференция IEEE по компьютерному зрению и распознаванию образов, стр. 731–737.
  3. ^ М. П. Кумар, П. Х. С. Торр и А. Зиссерман. Obj вырезано. В Труды конференции IEEE по компьютерному зрению и распознаванию образов, Сан-Диего, страницы 18–25, 2005 г.
  4. ^ Э. Боренштейн, С. Ульман: Специфичная для класса сегментация сверху вниз. В материалах 7-й Европейской конференции по компьютерному зрению, Копенгаген, Дания, страницы 109–124, 2002.
  5. ^ З. Ту, Х. Чен, А. Л. Юилле, С. К. Чжу: Анализ изображений: объединение сегментации, обнаружения и распознавания. К распознаванию объектов на уровне категорий 2006: 545–576
  6. ^ Б. Лейбе, А. Леонардис, Б. Шиле: Неявная модель формы для комбинированной категоризации и сегментации объектов. К распознаванию объектов на уровне категорий 2006: 508–524
  7. ^ Дж. Винн, Н. Джойджик. Локус: изучение классов объектов с неконтролируемой сегментацией. В материалах Международной конференции IEEE по компьютерному зрению, Пекин, 2005 г.
  8. ^ Дж. М. Винн, Дж. Шоттон: Согласованное случайное поле макета для распознавания и сегментации частично закрытых объектов. CVPR (1) 2006: 37–44