В области компьютерного зрения , максимально стабильные экстремальные области ( MSER ) используются в качестве метода обнаружения двоичных объектов в изображениях. Этот метод был предложен Matas et al. [1], чтобы найти соответствия между элементами изображения из двух изображений с разными точками обзора. Этот метод извлечения исчерпывающего количества соответствующих элементов изображения способствует сопоставлению с широкой базовой линией и приводит к лучшему стерео сопоставлению и алгоритмам распознавания объектов .
Термины и определения
Изображение это отображение . Экстремальные области хорошо видны на изображениях, если:
- полностью упорядочен (тотальные, антисимметричные и транзитивные бинарные отношения существовать).
- Отношение смежности определено. Обозначим, что две точки смежные, как.
Область, край является смежным (также известным как связным) подмножеством . (Для каждого есть последовательность такой как .) Обратите внимание, что согласно этому определению область может содержать «дыры» (например, кольцевая область соединена, но ее внутренняя окружность не является частью ).
(Внешняя) граница области , что означает границу из - это набор пикселей, примыкающих хотя бы к одному пикселю но не принадлежащий . Опять же, в случае областей с «дырами» граница области не обязана соединять подмножество (кольцо имеет внутреннюю и внешнюю границы, которые не пересекаются).
Экстремальный регион такой регион, что либо для всех (область максимальной интенсивности) или для всех (область минимальной интенсивности). Поскольку полностью упорядочен, мы можем переформулировать эти условия как для области максимальной интенсивности и для области минимальной интенсивности соответственно. В этой форме мы можем использовать понятие порогового значения интенсивности, которое разделяет область и ее границу.
Максимально устойчивая экстремальная область Пусть экстремальная область, такая как все точки на ней, имеет интенсивность меньше, чем . Примечание для всех положительных . Экстремальный регион максимально устойчива тогда и только тогда, когда имеет местный минимум на уровне . (Здесь обозначает мощность). здесь параметр метода.
Уравнение проверяет области, которые остаются стабильными при достижении определенного количества пороговых значений. Если регион не намного больше, чем регион , область, край принимается за максимально устойчивую область.
Эту концепцию проще объяснить с помощью пороговой обработки . Все пиксели ниже заданного порога являются «черными», а все пиксели выше или равными - «белыми». Для исходного изображения, если последовательность изображений результатов с пороговым значением генерируется, где каждое изображение соответствует возрастающему порогу t, сначала будет видно белое изображение, затем появятся «черные» пятна, соответствующие локальным минимумам интенсивности, а затем они станут больше. Максимально стабильная экстремальная область обнаруживается, когда размер одной из этих черных областей такой же (или почти такой же), как на предыдущем изображении.
Эти «черные» пятна со временем сольются, пока все изображение не станет черным. Множество всех компонент связности в последовательности - это множество всех экстремальных областей. В этом смысле концепция MSER связана с деревом компонентов изображения. [2] Дерево компонентов действительно обеспечивает простой способ реализации MSER. [3]
Экстремальные регионы
Экстремальные области в этом контексте обладают двумя важными свойствами: множество замкнуто под ...
- непрерывное преобразование координат изображения. Это означает, что он аффинно инвариантен, и не имеет значения, искажено изображение или перекошено.
- монотонное преобразование яркости изображения. Этот подход, конечно, чувствителен к эффектам естественного освещения, таким как изменение дневного света или движущиеся тени.
Преимущества MSER
Поскольку регионы определяются исключительно функцией интенсивности в регионе и внешней границе, это приводит ко многим ключевым характеристикам регионов, которые делают их полезными. В широком диапазоне пороговых значений локальная бинаризация стабильна в определенных регионах и имеет свойства, перечисленные ниже.
- Инвариантность к аффинному преобразованию интенсивностей изображений
- Ковариантность к сохраняющему смежность (непрерывному) преобразованию в области изображений
- Стабильность : выбираются только регионы, поддержка которых примерно одинакова в диапазоне пороговых значений.
- Обнаружение в нескольких масштабах без какого-либо сглаживания, обнаруживаются как мелкие, так и крупные структуры.
Обратите внимание, однако, что обнаружение MSER в масштабной пирамиде улучшает повторяемость и количество соответствий между масштабными изменениями. [4] - Множество всех экстремальных областей можно перечислить в наихудшем случае., где количество пикселей в изображении. [5]
Сравнение с другими детекторами регионов
В Mikolajczyk et al. [6] изучаются шесть детекторов областей (аффинная по Харрису, аффинная по Гессе, MSER, краевые области, экстремумы интенсивности и заметные области). Ниже приводится сводка производительности MSER по сравнению с другими пятью.
- Плотность областей - по сравнению с другими MSER предлагает наибольшее разнообразие, обнаруживая около 2600 областей для текстурированной сцены размытия и 230 областей для сцены с измененным освещением, и разнообразие обычно считается хорошим. Также MSER имел повторяемость 92% для этого теста.
- Размер области - MSER имел тенденцию обнаруживать множество небольших областей по сравнению с большими областями, которые с большей вероятностью будут закрыты или не покрывают плоскую часть сцены. Хотя сопоставление больших регионов может быть немного проще.
- Изменение точки обзора - MSER превосходит пять других детекторов регионов как на исходных изображениях, так и на изображениях с повторяющимися текстурами.
- Изменение масштаба - после аффинного детектора Гессе, MSER занимает второе место при изменении масштаба и вращении в плоскости.
- Размытие - MSER оказался наиболее чувствительным к этому типу изменения изображения, что является единственной областью, в которой отсутствует этот тип обнаружения.
Однако обратите внимание, что в этой оценке не использовалось обнаружение с несколькими разрешениями, которое было показано для улучшения повторяемости при размытии. [4] - Изменение освещенности - MSER показал наивысшую оценку повторяемости для этого типа сцены, а все остальные также имели хорошую надежность.
MSER неизменно дает наивысший балл во многих тестах, доказывая, что он является надежным детектором области. [6]
Выполнение
Исходный алгоритм Matas et al. [1] - это в числе пикселей. Сначала происходит сортировка пикселей по интенсивности. Это займетраз, используя BINSORT . После сортировки на изображении помечаются пиксели, а список растущих и объединяемых связанных компонентов и их площадей поддерживается с помощью алгоритма поиска-объединения . Это займетвремя. На практике эти шаги очень быстрые. Во время этого процесса площадь каждого подключенного компонента как функция интенсивности сохраняется, создавая структуру данных. Слияние двух компонентов рассматривается как прекращение существования меньшего компонента и вставка всех пикселей меньшего компонента в больший. В экстремальных областях «максимально стабильными» являются те, которые соответствуют порогам, где относительное изменение площади как функция относительного изменения порога находится на локальном минимуме, то есть MSER - это части изображения, где локальная бинаризация стабильна в течение большой ассортимент порогов. [1] [6]
Дерево компонентов - это совокупность всех связанных компонентов порогов изображения, упорядоченных по включению. Эффективные (квазилинейные независимо от диапазона весов) алгоритмы его вычисления существуют. [2] Таким образом, эта структура предлагает простой способ реализации MSER. [3]
Совсем недавно Нистер и Стюениус предложили поистине (если вес - маленькие целые числа) наихудший случай. метод [5], который также намного быстрее на практике. Этот алгоритм аналогичен алгоритму Ph. Salembier et al. [7]
Надежный алгоритм с широкой базой
Целью этого алгоритма является сопоставление MSER для установления точек соответствия между изображениями. Первые области MSER вычисляются на изображении интенсивности (MSER +) и на инвертированном изображении (MSER-). Области измерения выбираются в нескольких масштабах: размер фактической области, 1,5x, 2x и 3x масштабируемая выпуклая оболочка области. Согласование выполняется надежным образом, поэтому лучше увеличить различимость больших областей, не подвергаясь сильному влиянию помех или непланарности предварительного изображения области. Измерение, проведенное с почти плоского участка сцены со стабильным инвариантным описанием, называется «хорошим измерением». Нестабильные измерения, измерения на неплоских поверхностях или неоднородностях называются «искаженными измерениями». Вычисляется робастное подобие: для каждого по региону регионы с другого изображения с соответствующим i-м измерением ближайший к найдены, и проводится голосование, предлагающее соответствие А и каждого из . Голоса суммируются по всем измерениям, и с помощью вероятностного анализа можно выбрать «хорошие измерения», поскольку «искаженные измерения», вероятно, распределят голоса случайным образом. Применяя RANSAC к центрам тяжести регионов, можно вычислить грубую эпиполярную геометрию . Вычисляется аффинное преобразование между парами потенциально соответствующих областей, и соответствия определяют его с точностью до поворота, который затем определяется эпиполярными линиями. Затем области фильтруются, и выбираются те, у которых корреляция их преобразованных изображений выше порогового значения. RANSAC применяется снова с более узким порогом, и окончательная эпиполярная геометрия оценивается с помощью алгоритма из восьми точек .
Этот алгоритм можно протестировать здесь (совпадения с эпиполярной или гомографической геометрией): WBS Image Matcher
Использование при обнаружении текста
Алгоритм MSER был использован Ченом при обнаружении текста путем объединения MSER с краями Canny. Изящные края используются, чтобы помочь справиться со слабостью MSER к размытию. MSER сначала применяется к рассматриваемому изображению, чтобы определить области символов. Для улучшения областей MSER удаляются любые пиксели за пределами границ, образованных краями Canny. Разделение последних, обеспечиваемое краями, значительно увеличивает удобство использования MSER при извлечении размытого текста. [8] Альтернативным использованием MSER при обнаружении текста является работа Ши с использованием графовой модели. Этот метод снова применяет MSER к изображению для создания предварительных областей. Затем они используются для построения модели графа на основе расстояния между позициями и цветового расстояния между каждым MSER, который рассматривается как узел. Затем узлы разделяются на передний и задний план с помощью функций стоимости. Одна из стоимостных функций состоит в том, чтобы связать расстояние от узла до переднего и заднего планов. Другой наказывает узлы за то, что они значительно отличаются от своего соседа. Когда они минимизированы, граф затем обрезается, чтобы отделить текстовые узлы от нетекстовых узлов. [9] Чтобы включить обнаружение текста в общей сцене, Нойман использует алгоритм MSER в различных проекциях. В дополнение к проекции интенсивности в градациях серого он использует каналы красного, синего и зеленого цветов для обнаружения областей текста, которые отличаются по цвету, но не обязательно отличаются по интенсивности в градациях серого. Этот метод позволяет обнаруживать больше текста, чем только с помощью функций MSER + и MSER-, описанных выше. [10]
Расширения и адаптации
- Алгоритм MSER был адаптирован для цветных изображений путем замены порога функции интенсивности агломеративной кластеризацией на основе цветовых градиентов. [11]
- Алгоритм MSER может использоваться для обнаружения областей на основе цвета, а не интенсивности. Это сделал Чавес, создав функцию интенсивности для красного, зеленого и синего цветов в цветовом пространстве HSV. Затем алгоритм MSER запускается пять раз; над тремя цветовыми псевдоинтенсивностями, а затем над интенсивностями серой шкалы с использованием стандартных функций MSER + и MSER-. [12]
- Алгоритм MSER может использоваться для отслеживания цветных объектов, выполняя обнаружение MSER на расстоянии Махаланобиса до цветового распределения. [3]
- Обнаруживая MSER в нескольких разрешениях, можно улучшить устойчивость к размытию и изменению масштаба. [4]
Другие приложения
- Дескрипторы формы для максимально устойчивых экстремальных областей
- Эффективное отслеживание максимально стабильной экстремальной области (MSER)
- N-образные непересекающиеся леса для максимально устойчивых экстремальных областей
- Видео Google и группировка на уровне объектов для видеороликов
- Извлечение в реальном времени максимально устойчивых экстремальных областей на ПЛИС
- Максимально стабильные цветовые области для распознавания и сопоставления
Смотрите также
Внешние ссылки
- VLFeat , библиотека компьютерного зрения с открытым исходным кодом на C (с интерфейсом MEX для MATLAB), включая реализацию MSER
- OpenCV , библиотека компьютерного зрения с открытым исходным кодом на C / C ++, включая реализацию Linear Time MSER
- Исследование повторяемости детектора , двоичные файлы Кристиана Миколайчика (Win / Linux для вычисления MSER / HarrisAffine ... двоичные файлы, использованные в его исследовании повторяемости.
- Реализация MSER с линейным временем , Charles Dubout, реализация MSER на C ++ в качестве детектора blob
Рекомендации
- ^ a b c Дж. Матас, О. Чум, М. Урбан и Т. Пайдла. «Надежное стерео с широкой базой из максимально устойчивых экстремальных областей». Proc. Британской конференции по машинному зрению, страницы 384-396, 2002.
- ^ a b Л. Найман и М. Купри: «Построение дерева компонентов в квазилинейном времени». Архивировано 9 апреля 2011 г. в Wayback Machine ; IEEE Transactions по обработке изображений, том 15, номера 11, 2006 г., стр. 3531-3539
- ^ a b c Донозер М. и Бишоф Х. Отслеживание эффективной максимально стабильной экстремальной области (MSER) CVPR , 2006.
- ^ a b c Форссен, ЧП. и Лоу, Д.Г. «Дескрипторы формы для максимально стабильных экстремальных областей». Архивировано 10 июня 2011 г. на Wayback Machine ICCV, 2007.
- ^ a b Нистер Д. и Стюениус Х., "Максимально устойчивые экстремальные области с линейным временем" , ECCV, 2008.
- ^ a b c К. Миколайчик, Т. Туйтелаарс, К. Шмид, А. Зиссерман, Т. Кадир и Л. Ван Гул: «Сравнение детекторов аффинных областей» ; Международный журнал компьютерного зрения, том 65, номера 1-2 / ноябрь 2005 г., стр. 43-72
- ^ Салембье, Филипп; А. Оливерас; Л. Гарридо (1998). «Анти-обширные подключенные операторы для обработки изображений и последовательностей» . IEEE Transactions по обработке изображений . 7 (4): 555–570. DOI : 10.1109 / 83.663500 . ЛВП : 2117/90134 . PMID 18276273 . Архивировано из оригинала на 2012-04-25 . Проверено 17 ноября 2011 .
- ^ Чен, Хуэйчжун; Цай, Сэм; Шрот, Георг; Чен, Дэвид; Гжещук, Радек; Жирод, Бернд . «Надежное обнаружение текста в естественных изображениях с максимально стабильными экстремальными областями с улучшенными краями» . Proc. IEEE Международная конференция по Image Processing 2011 .
- ^ Ши, Цуньчжао; Ван, Чунхэн; Сяо, Байхуа; Гао, Сун (15 января 2013 г.). «Обнаружение текста сцены с использованием графической модели, построенной на максимально устойчивых экстремальных областях». Письма о распознавании образов . 34 (2): 107–116. DOI : 10.1016 / j.patrec.2012.09.019 .
- ^ Нойман, Лукас; Матас, Иржи (2011). «Метод локализации и распознавания текста в изображениях реального мира». Accv 2010 : 770–783.
- ^ Форссен, ЧП. Максимально стабильные цветовые области для распознавания и сопоставления. Архивировано 10 июня 2011 г.в Wayback Machine , CVPR, 2007.
- ^ Чавес, Аарон; Густафсон, Дэвид (2011). «Расширения на основе цвета для MSER». Isvc 2011 . Конспект лекций по информатике. 6939 : 358–366. DOI : 10.1007 / 978-3-642-24031-7_36 . ISBN 978-3-642-24030-0.