Проблема сегментации изображения связана с разделением изображения на несколько областей в соответствии с некоторым критерием однородности. Эта статья в первую очередь посвящена теоретико-графическим подходам к сегментации изображений, использующим разбиение графа с помощью минимального или максимального отсечения . Категоризацию объектов на основе сегментации можно рассматривать как частный случай спектральной кластеризации, применяемой к сегментации изображения.
Приложения сегментации изображений
- Сжатие изображения
- Сегментируйте изображение на однородные компоненты и используйте наиболее подходящий алгоритм сжатия для каждого компонента, чтобы улучшить сжатие.
- Медицинский диагноз
- Автоматическая сегментация изображений МРТ для выявления раковых участков.
- Картирование и измерение
- Автоматический анализ данных дистанционного зондирования со спутников для определения и измерения интересующих регионов.
- Транспорт
- Разделение транспортной сети позволяет выделить регионы, характеризующиеся однородным состоянием движения. [1]
Сегментация с использованием нормализованных разрезов
Теоретико-графическая формулировка
Набор точек в произвольном пространстве признаков может быть представлен как взвешенный неориентированный полный граф G = (V, E), где узлы графа являются точками в пространстве признаков. Вес края является функцией подобия между узлами а также . В этом контексте мы можем сформулировать проблему сегментации изображения как проблему разделения графа, которая требует разделения множества вершин , где по некоторой мере вершины любого множества имеют большое сходство, а вершины в двух разных множествах имеют низкое сходство.
Нормализованные разрезы
Пусть G = ( V , E , w ) - взвешенный граф. Позволять а также - два подмножества вершин.
Позволять:
В подходе нормализованных разрезов [2] для любого разреза в , измеряет сходство между разными частями, и измеряет общее сходство вершин в одной и той же части.
С , порез что сводит к минимуму также максимизирует .
Расчет разреза что сводит к минимуму это NP-сложная проблема. Однако мы можем найти за полиномиальное время разрез малой нормированной массы с использованием спектральных методов .
Алгоритм ncut
Позволять:
Кроме того, пусть D будет диагональная матрица с по диагонали, и пусть быть симметричная матрица с .
После некоторых алгебраических манипуляций получаем:
с учетом ограничений:
- , для некоторой постоянной
Сведение к минимуму с учетом указанных выше ограничений является NP-трудным . Чтобы сделать проблему разрешимой, мы ослабляем ограничения на, и позвольте ему принимать реальные значения. Расслабленная задача может быть решена путем решения обобщенной задачи на собственные значения для второго наименьшего обобщенного собственного значения.
Алгоритм разбиения:
- Учитывая набор функций, настройте взвешенный график , вычислим вес каждого ребра и суммируем информацию в а также .
- Решать для собственных векторов со вторыми наименьшими собственными значениями.
- Используйте собственный вектор со вторым наименьшим собственным значением для разделения графа на две части (например, группировку по знаку).
- Решите, следует ли разделить текущий раздел.
- При необходимости рекурсивно разбейте сегментированные части.
Вычислительная сложность
Решение стандартной задачи на собственные значения для всех собственных векторов (например, с использованием алгоритма QR ) требуетвремя. Это непрактично для приложений сегментации изображений, в которых количество пикселей в изображении.
Поскольку в неразрезанном алгоритме используется только один собственный вектор, соответствующий второму наименьшему обобщенному собственному значению, эффективность может быть значительно повышена, если решение соответствующей проблемы собственных значений выполняется безматричным способом , т. Е. Без явных манипуляций с или даже вычисление матрицы W, как, например, в алгоритме Ланцоша . Для безматричных методов требуется только функция, которая выполняет произведение матрица-вектор для заданного вектора на каждой итерации. Для сегментации изображения матрица W обычно разреженная, с несколькими ненулевыми элементами., поэтому такое произведение матрицы на вектор принимает время.
Для изображений с высоким разрешением второе собственное значение часто плохо обусловлено , что приводит к медленной сходимости итерационных решателей собственных значений, таких как алгоритм Ланцоша . Предварительная подготовка - это ключевая технология, ускоряющая сходимость, например, в безматричном методе LOBPCG . Вычисление собственного вектора с использованием безматричного метода с оптимальным предварительным условием требует время, что является оптимальной сложностью, поскольку собственный вектор имеет составные части.
ОБРЕЗАТЬ
OBJ CUT [3] - эффективный метод, который автоматически сегментирует объект. Метод OBJ CUT - это универсальный метод, поэтому он применим к любой модели категории объектов. Для данного изображения D, содержащего экземпляр известной категории объекта, например коровы, алгоритм OBJ CUT вычисляет сегментацию объекта, то есть выводит набор меток m .
Пусть m - набор двоичных меток, и пусть быть параметром формы (является формой, предшествующей этикеткам из модели слоистой графической структуры (LPS)). Энергетическая функция определяется следующим образом.
- (1)
Термин называется унарным термином, а термин называется попарным членом. Унарный термин состоит из вероятности на основе цвета и унарного потенциала в зависимости от расстояния от . Парный член состоит из априорного и контрастный термин .
Лучшая маркировка сводит к минимуму , где вес параметра .
- (2)
Алгоритм
- Для изображения D выбирается категория объекта, например, коровы или лошади.
- Соответствующая модель LPS сопоставляется с D для получения образцов
- Целевая функция, задаваемая уравнением (2), определяется путем вычисления и используя
- Целевая функция минимизируется с помощью одной операции MINCUT для получения сегментации m .
Другие подходы
Рекомендации
- ^ Лопес, Клелия; Леклерк, Людовик; Кришнакумари, Панчами; Чиабаут, Николас; Ван Линт, Ханс (25 октября 2017 г.). «Выявление повседневной закономерности городских заторов с помощью трехмерных карт скорости» . Научные отчеты . 7 (14029): 14029. DOI : 10.1038 / s41598-017-14237-8 . PMC 5656590 . PMID 29070859 .
- ^ Jianbo Shi и Jitendra Malik (1997): «Нормализованные разрезы и сегментация изображений», Конференция IEEE по компьютерному зрению и распознаванию образов, стр. 731–737
- ↑ MP Kumar, PHS Torr и A. Zisserman. Obj вырезано. В материалах конференции IEEE по компьютерному зрению и распознаванию образов , Сан-Диего, страницы 18–25, 2005 г.
- ^ Э. Боренштейн, С. Ульман: сегментация сверху вниз по классам . В материалах 7-й Европейской конференции по компьютерному зрению, Копенгаген, Дания, страницы 109–124, 2002.
- ^ Z. Tu, X. Chen, AL Yuille, SC Zhu: Анализ изображений: объединение сегментации, обнаружения и распознавания . К распознаванию объектов на уровне категорий 2006: 545–576
- ^ Б. Лейбе, А. Леонардис, Б. Шиле: неявная модель формы для комбинированной категоризации и сегментации объектов . К распознаванию объектов на уровне категорий 2006: 508–524
- ^ Дж. Винн, Н. Джойджик. Локус: классы объектов обучения с неконтролируемой сегментацией . В материалах Международной конференции IEEE по компьютерному зрению, Пекин, 2005 г.
- ^ JM Winn, J. Shotton: Согласованное случайное поле макета для распознавания и сегментации частично закрытых объектов . CVPR (1) 2006: 37–44