Максимально устойчивые экстремальные области

В компьютерном зрении техника максимально стабильных экстремальных областей ( MSER ) ​​используется как метод обнаружения пятен на изображениях. Этот метод был предложен Matas et al. найти соответствия между элементами изображения, взятыми из двух изображений с разных точек зрения. Этот метод извлечения полного количества соответствующих элементов изображения способствует сопоставлению с широкой базой и привел к улучшению стереосопоставления и распознавания объектов алгоритмов .

Термины и определения

Изображение $I$ это отображение $I:D\subset \mathbb {Z} ^{2}\to S$. Экстремальные области хорошо выделяются на изображениях, если:

1. $S$ полностью упорядочен (полные, антисимметричные и транзитивные бинарные отношения $\leq$ существовать).
2. Отношение смежности $A\subset D\times D$ определяется. Обозначим, что две точки смежны как $pAq$.

Область $Q$ представляет собой непрерывное (то есть связанное) подмножество $D$. (Для каждого $p,q\in Q$ есть последовательность $p,a_{1},a_{2},..,a_{n},q$ такой как $pAa_{1},a_{1}Aa_{2},\dots ,a_{n-1}Aa_{n},a_{n}Aq$.) Обратите внимание, что согласно этому определению область может содержать «дырки» (например, кольцеобразная область соединена, но ее внутренняя окружность не является частью $Q$).

(Внешняя) граница региона $\partial Q=\{q\in D\setminus Q:\exists p\in Q:qAp\}$, что означает границу $\partial Q$ из $Q$ это набор пикселей, смежных хотя бы с одним пикселем $Q$ но не принадлежащий $Q$. Опять же, в случае регионов с «дырками» граница региона не обязательно должна быть связана подмножеством $D$ (у кольца есть внутренняя и внешняя границы, которые не пересекаются).

Экстремальный регион $Q\subset D$ регион такой, что либо для всех $p\in Q,q\in \partial Q:I(p)>I(q)$ (область максимальной интенсивности) или для всех $p\in Q,q\in \partial Q:I(p)<I(q)$ (область минимальной интенсивности). Насколько $S$ полностью упорядочен, мы можем переформулировать эти условия как $\min(I(p))>\max(I(q))$ для области максимальной интенсивности и $\max(I(p))<\min(I(q))$ для области минимальной интенсивности соответственно. В этой форме мы можем использовать понятие порогового значения интенсивности, разделяющего область и ее границу.

Максимально устойчивая экстремальная область Пусть $Q_{i}$ экстремальная область, такая как все точки в ней, имеют интенсивность меньше, чем $i\in S$. Примечание $Q_{i}\subset Q_{i+\Delta }$ за все позитивное $\Delta \in S$. Экстремальный регион $Q_{i*}$ максимально устойчив тогда и только тогда, когда $|Q_{i+\Delta }\setminus Q_{i-\Delta }|/|Q_{i}|$ имеет локальный минимум в $i*$. (Здесь $|\cdot |$ обозначает мощность). $\Delta \in S$ здесь параметр метода.

Уравнение проверяет регионы, которые остаются стабильными в течение определенного количества порогов. Если регион $Q_{i+\Delta }$ не значительно больше региона $Q_{i-\Delta }$, регион $Q_{i}$ принимается как максимально устойчивая область.

Более просто эту концепцию можно объяснить с помощью порогового значения . Все пиксели ниже заданного порога являются «черными», а все пиксели выше или равные — «белыми». Учитывая исходное изображение, если последовательность пороговых изображений результатов $I_{t}$ генерируется, где каждое изображение $t$ соответствует увеличению порога t, сначала будет видно белое изображение, затем появятся «черные» пятна, соответствующие локальным минимумам интенсивности, а затем они станут больше. Максимально стабильная экстремальная область обнаруживается, когда размер одной из этих черных областей такой же (или почти такой же), как на предыдущем изображении.

Эти «черные» пятна со временем сольются, пока все изображение не станет черным. Множество всех компонент связности последовательности — это множество всех экстремальных областей. В этом смысле понятие MSER связано с понятием дерева компонентов изображения. Дерево компонентов действительно обеспечивает простой способ реализации MSER.

Экстремальные регионы

Экстремальные области в этом контексте обладают двумя важными свойствами: множество замкнуто относительно...

1. непрерывное преобразование координат изображения. Это означает, что он аффинно-инвариантен, и не имеет значения, искажено или искажено изображение.
2. монотонное преобразование интенсивностей изображения. Этот подход, конечно, чувствителен к эффектам естественного освещения, таким как изменение дневного света или движущиеся тени.

Преимущества МСЭР

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

• Инвариантность к аффинному преобразованию интенсивностей изображений.
• сохраняющему смежность (непрерывному) Ковариация к преобразованию, $T:D\to D$ в области изображений
• Стабильность : выбираются только регионы, поддержка которых практически одинакова в диапазоне пороговых значений.
• Многомасштабное обнаружение без какого-либо сглаживания, обнаруживается как мелкая, так и крупная структура.
  Однако обратите внимание, что обнаружение MSER в пирамиде масштаба улучшает повторяемость и количество соответствий при изменении масштаба.
• Множество всех экстремальных регионов можно перечислить в худшем случае. $O(n)$, где $n$ это количество пикселей в изображении.

Сравнение с другими детекторами регионов

Миколайчик и др., изучаются шесть детекторов областей ( аффинные по Харрису , аффинные по Гессиану , MSER, области на основе краев, экстремумы интенсивности и заметные области ). Ниже приводится сводная информация о производительности MSER по сравнению с остальными пятью.

• Плотность регионов – по сравнению с другими MSER предлагает наибольшее разнообразие, обнаруживая около 2600 регионов для сцены с текстурированным размытием и 230 для сцены с измененным светом, и разнообразие обычно считается хорошим. Также MSER имел повторяемость этого теста 92%.
• Размер региона . MSER имел тенденцию обнаруживать множество небольших областей по сравнению с большими областями, которые с большей вероятностью были закрыты или не покрывали плоскую часть сцены. Хотя крупные регионы может быть немного легче сопоставить.
• Изменение точки обзора — MSER превосходит пять других детекторов областей как на исходных изображениях, так и на изображениях с повторяющимися текстурными мотивами.
• Изменение масштаба . После гессиано-аффинного детектора MSER занимает второе место по изменению масштаба и вращению в плоскости.
• Размытие — MSER оказался наиболее чувствительным к такому типу изменения изображения, это единственная область, в которой этот тип обнаружения отсутствует.
  Однако обратите внимание, что в этой оценке не использовалось обнаружение с несколькими разрешениями, которое, как было показано, улучшает повторяемость при размытии.
• Изменение освещения – MSER показал самый высокий показатель повторяемости для этого типа сцены, при этом все остальные также имели хорошую надежность.

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

Выполнение

Оригинальный алгоритм Мэтаса и др. является $O(n\,\log(\log(n)))$ в номере $n\,$ пикселей. Сначала происходит сортировка пикселей по интенсивности. Это потребует $O(n)\,$ время, используя BINSORT . После сортировки на изображении размечаются пиксели, а список растущих и сливающихся связанных компонентов и их площадей поддерживается с помощью алгоритма объединения-поиска . Это потребует $O(n\,\log(\log(n)))$ время. На практике эти шаги выполняются очень быстро. В ходе этого процесса площадь каждого подключенного компонента в зависимости от интенсивности сохраняется, образуя структуру данных. Слияние двух компонентов рассматривается как прекращение существования меньшего компонента и вставка всех пикселей меньшего компонента в больший. В экстремальных областях «максимально стабильными» являются те, которые соответствуют порогам, где относительное изменение площади как функция относительного изменения порога находится на локальном минимуме, т.е. MSER — это части изображения, где локальная бинаризация стабильна в течение большой диапазон порогов.

Дерево компонентов представляет собой совокупность всех связных компонентов порогов изображения, упорядоченных по включению. Эффективные (квазилинейные, независимо от диапазона весов) алгоритмы его вычисления существуют. Таким образом, эта структура предлагает простой способ реализации MSER.

Совсем недавно Нистер и Стевениус предложили действительно (если веса являются небольшими целыми числами) наихудший случай. $O(n)\,$ метод в, что также намного быстрее на практике. Этот алгоритм аналогичен алгоритму Ф. Салембье и др.

Надежный алгоритм с широкой базой

Целью этого алгоритма является сопоставление MSER для установления точек соответствия между изображениями. Первые области MSER вычисляются на изображении интенсивности (MSER+) и на инвертированном изображении (MSER-). Области измерения выбираются в нескольких масштабах: размер фактической области, выпуклая оболочка области в масштабе 1,5x, 2x и 3x. Сопоставление выполняется надежным образом, поэтому лучше повысить различимость больших регионов, не подвергаясь серьезному влиянию беспорядка или непланарности прообраза региона. Измерение, выполненное на почти плоском участке сцены со стабильным инвариантным описанием, называется «хорошим измерением». Нестабильные измерения или измерения на неплоских поверхностях или разрывах называются «испорченными измерениями». Робастное подобие вычисляется:Для каждого $M_{A}^{i}$ по региону $A,k$ регионы $B_{1},\dots ,B_{k}$ из другого изображения с соответствующим i-м измерением $M_{B_{1}}^{i},\dots ,M_{B_{k}}^{i}$ ближайший к $M_{A}^{i}$ найдены и проводится голосование, предполагающее соответствие A и каждого из $B_{1},\dots ,B_{k}$. Голоса суммируются по всем измерениям, и с помощью вероятностного анализа можно выбрать «хорошие измерения», поскольку «некорректные измерения», скорее всего, распределят свои голоса случайным образом. Применяя RANSAC к центрам тяжести регионов, грубую эпиполярную геометрию можно вычислить . Вычисляется аффинное преобразование между парами потенциально соответствующих областей, и соответствия определяют его с точностью до поворота, который затем определяется эпиполярными линиями. Затем регионы фильтруются и выбираются те, у которых корреляция преобразованных изображений превышает пороговое значение. RANSAC применяется снова с более узким порогом, а окончательная эпиполярная геометрия оценивается с помощью восьмиточечного алгоритма .

Этот алгоритм можно протестировать здесь (соответствия с ограничениями по эпиполярной или гомографической геометрии): WBS Image Matcher

Использование при обнаружении текста

Алгоритм MSER использовался Ченом для обнаружения текста путем объединения MSER с краями Canny . Осторожные края используются, чтобы помочь справиться с слабостью MSER к размытию. MSER сначала применяется к рассматриваемому изображению для определения областей символов. Для улучшения областей MSER все пиксели за пределами границ, образованных краями Кэнни, удаляются. Разделение последних по краям значительно повышает удобство использования MSER при извлечении размытого текста.

Альтернативным использованием MSER для обнаружения текста является работа Ши с использованием графовой модели. Этот метод снова применяет MSER к изображению для создания предварительных областей. Затем они используются для построения графовой модели на основе позиционного расстояния и цветового расстояния между каждым MSER, который рассматривается как узел. Затем узлы разделяются на передний план и фон с помощью функций стоимости. Одна функция стоимости состоит в том, чтобы связать расстояние от узла до переднего и заднего планов. Другой наказывает узлы за существенное отличие от своего соседа. Когда они свернуты, граф разрезается , чтобы отделить текстовые узлы от нетекстовых узлов.

Чтобы обеспечить обнаружение текста в общей сцене, Нейманн использует алгоритм MSER в различных проекциях. В дополнение к проекции интенсивности оттенков серого он использует каналы красного, синего и зеленого цветов для обнаружения текстовых областей, которые различаются по цвету, но не обязательно различаются по интенсивности оттенков серого. Этот метод позволяет обнаруживать больше текста, чем просто использование функций MSER+ и MSER-, описанных выше.

Расширения и адаптации

• Алгоритм MSER был адаптирован для цветных изображений путем замены пороговой функции интенсивности на агломеративную кластеризацию на основе цветовых градиентов.
• Алгоритм MSER можно использовать для обнаружения областей на основе цвета, а не интенсивности. Это сделано Чавесом путем создания функции интенсивности для красного, зеленого и синего цвета в цветовом пространстве HSV . Затем алгоритм MSER запускается пять раз; по трем псевдоинтенсивностям цветов, а затем по интенсивностям серой шкалы с использованием стандартных функций MSER+ и MSER-.
• Алгоритм MSER можно использовать для отслеживания цветных объектов, выполняя обнаружение MSER на расстоянии Махаланобиса до распределения цвета.
• Обнаружив MSER в нескольких разрешениях, можно повысить устойчивость к размытию и изменению масштаба.

Другие приложения

• Дескрипторы формы для максимально устойчивых экстремальных областей
• Эффективное отслеживание максимально стабильной экстремальной области (MSER)
• N-деревьевые непересекающиеся леса для максимально устойчивых экстремальных областей
• Видео Google и группировка на уровне объектов для видеокадров
• Извлечение в реальном времени максимально стабильных экстремальных областей на FPGA
• Максимально стабильные цветовые области для распознавания и сопоставления

См. также

• Обнаружение больших двоичных объектов
• Обнаружение функций (компьютерное зрение)

Внешние ссылки

• VLFeat , библиотека компьютерного зрения с открытым исходным кодом на языке C (с MEX- интерфейсом для MATLAB ), включая реализацию MSER.
• OpenCV , библиотека компьютерного зрения с открытым исходным кодом на C/ C++ , включая реализацию Linear Time MSER.
• Исследование повторяемости детектора , Кристиан Миколайчик Двоичные файлы (Win/Linux для вычисления MSER/HarrisAffine.... Двоичные файлы, использованные в его исследовании повторяемости.
• Реализация MSER с линейным временем , Шарль Дюбу, реализация MSER на C++ в качестве детектора больших двоичных объектов