Максимально устойчивые экстремальные регионы - Википедия - Maximally stable extremal regions

В компьютерное зрение, максимально устойчивые экстремальные области (MSER) используются как метод обнаружение капли в изображениях. Этот метод был предложен Матас и другие.^[1] найти корреспонденции между элементами изображения из двух изображений с разными точками обзора. Этот метод извлечения исчерпывающего количества соответствующих элементов изображения способствует согласованию широкой базовой линии и приводит к лучшему стерео согласованию и распознавание объекта алгоритмы.

Понятия и определения

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

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

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

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

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

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

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

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

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

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

Экстремальные регионы в этом контексте есть два важных свойства, которые закрываются под ...

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

Преимущества MSER

Поскольку регионы определяются исключительно функцией интенсивности в регионе и внешней границе, это приводит ко многим ключевым характеристикам регионов, которые делают их полезными. В большом диапазоне пороговых значений локальная бинаризация стабильна в определенных регионах и имеет свойства, перечисленные ниже.
Инвариантность к аффинное преобразование интенсивности изображения
Ковариация с сохранением смежности (непрерывный)трансформация ${ displaystyle T: D to D}$ в области изображений
Стабильность: выбираются только регионы, поддержка которых примерно одинакова в диапазоне пороговых значений.
Многоуровневое обнаружение без сглаживания обнаруживаются как мелкие, так и крупные структуры.
Однако обратите внимание, что обнаружение MSER в масштабной пирамиде улучшает повторяемость и количество соответствий при изменении масштаба.^[4]
Множество всех экстремальных областей можно перечисленный в худшем случае ${ Displaystyle О (п)}$ , куда ${ displaystyle n}$ количество пикселей в изображении.^[5]
Сравнение с другими детекторами регионов
В Mikolajczyk et al.,^[6] Изучаются шесть детекторов областей (аффинная по Харрису, аффинная по Гесси, MSER, краевые области, экстремумы интенсивности и заметные области). Ниже приводится сводка производительности MSER по сравнению с другими пятью.
Плотность региона - по сравнению с другими MSER предлагает наибольшее разнообразие, обнаруживая около 2600 областей для сцены с текстурированным размытием и 230 областей для сцены с измененным освещением, и разнообразие обычно считается хорошим. Также MSER имел повторяемость 92% для этого теста.
Размер области - MSER имел тенденцию обнаруживать множество небольших областей по сравнению с большими областями, которые с большей вероятностью будут закрыты или не покрывают плоскую часть сцены. Хотя сопоставление крупных регионов может быть немного проще.
Изменение точки зрения - MSER превосходит пять других детекторов регионов как в исходных изображениях, так и в изображениях с повторяющимися текстурами.
Изменение масштаба - После аффинного детектора Гессе, MSER идет вторым по изменению масштаба и вращению в плоскости.
Размытие - MSER оказался наиболее чувствительным к такому типу изменения изображения, что является единственной областью, в которой отсутствует этот тип обнаружения.
Однако обратите внимание, что в этой оценке не использовалось обнаружение с несколькими разрешениями, которое, как было показано, улучшает повторяемость при размытии.^[4]
Изменение света - MSER показал наивысшую оценку повторяемости для этого типа сцены, а все остальные также имели хорошую надежность.
MSER стабильно давал наивысшие баллы во многих тестах, доказывая, что это надежный детектор области.^[6]
Выполнение

Исходный алгоритм Matas et al.^[1] является ${ Displaystyle О (п , журнал ( журнал (п)))}$ в числе ${ Displaystyle п ,}$ пикселей. Сначала происходит сортировка пикселей по интенсивности. Это займет ${ Displaystyle О (п) ,}$ время, используя БИНСОРТ. После сортировки на изображении помечаются пиксели, а список растущих и объединяемых связанных компонентов и их областей поддерживается с помощью союз-находка алгоритм. Это займет ${ Displaystyle О (п , журнал ( журнал (п)))}$ время. На практике эти шаги очень быстрые. Во время этого процесса площадь каждого подключенного компонента как функция интенсивности сохраняется, создавая структуру данных. Слияние двух компонентов рассматривается как прекращение существования меньшего компонента и вставка всех пикселей меньшего компонента в больший. В экстремальных областях «максимально стабильными» являются те, которые соответствуют пороговым значениям, где относительное изменение площади как функция относительного изменения порога находится на локальном минимуме, то есть MSER - это части изображения, где локальная бинаризация стабильна в течение большой ассортимент порогов.^[1]^[6]
Дерево компонентов - это совокупность всех связанных компонентов порогов изображения, упорядоченных по включению. Эффективные (квазилинейные независимо от диапазона весов) алгоритмы его вычисления существуют.^[2] Таким образом, эта структура предлагает простой способ реализации MSER.^[3]
Совсем недавно Нистер и Стюениус предложили поистине (если вес - маленькие целые числа) наихудший случай. ${ Displaystyle О (п) ,}$ метод в,^[5] что также намного быстрее на практике. Этот алгоритм аналогичен алгоритму Ph. Salembier et al.^[7]
Надежный алгоритм с широкой базой

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

^ ^а ^б ^c Дж. Матас, О. Чум, М. Урбан и Т. Пайдла. «Надежное стереозвук с широкой базой из максимально устойчивых экстремальных областей». Proc. Британской конференции по машинному зрению, страницы 384-396, 2002.
^ ^а ^б Л. Найман и М. Купри: «Построение дерева компонентов за квазилинейное время» В архиве 2011-04-09 на Wayback Machine; IEEE Transactions по обработке изображений, том 15, номера 11, 2006 г., стр. 3531-3539
^ ^а ^б ^c Донозер М. и Бишоф Х. Эффективное отслеживание максимально стабильной экстремальной области (MSER) CVPR, 2006.
^ ^а ^б ^c Форссен, П.Е. и Лоу, Д. «Дескрипторы формы для максимально устойчивых экстремальных областей» В архиве 2011-06-10 на Wayback Machine ICCV, 2007.
^ ^а ^б Нистер, Д. и Стюениус, Х., «Максимально устойчивые экстремальные области по линейному времени», ECCV, 2008.
^ ^а ^б ^c К. Миколайчик, Т. Туйтелаарс, К. Шмид, А. Зиссерман, Т. Кадир и Л. Ван Гул: «Сравнение детекторов аффинной области»; Международный журнал компьютерного зрения, том 65, номера 1-2 / ноябрь 2005 г., стр. 43-72
^ Салембье, Филипп; А. Оливерас; Л. Гарридо (1998). «Анти-обширные подключенные операторы для обработки изображений и последовательностей». IEEE Transactions по обработке изображений. 7 (4): 555–570. Дои:10.1109/83.663500. HDL:2117/90134. PMID 18276273. Архивировано из оригинал на 2012-04-25. Получено 2011-11-17.
^ Чен, Хуэйчжун; Цай, Сэм; Шрот, Георг; Чен, Дэвид; Гжещук, Радек; Жирод, Бернд. «Надежное обнаружение текста в естественных изображениях с максимально стабильными экстремальными областями с улучшенными краями». Proc. Международная конференция IEEE по обработке изображений, 2011 г..
^ Ши, Цуньчжао; Ван, Чунхэн; Сяо, Байхуа; Гао, Сун (15 января 2013 г.). «Обнаружение текста сцены с использованием графической модели, построенной на максимально устойчивых экстремальных областях». Письма с распознаванием образов. 34 (2): 107–116. Дои:10.1016 / j.patrec.2012.09.019.
^ Нойман, Лукас; Матас, Иржи (2011). «Метод локализации и распознавания текста в изображениях реального мира». Accv 2010: 770–783.
^ Форссен, П.Е. Максимально стабильные цветовые области для распознавания и сопоставления В архиве 2011-06-10 на Wayback Machine, CVPR, 2007.
^ Чавес, Аарон; Густафсон, Дэвид (2011). «Расширения на основе цвета для MSER». ISVC 2011. Конспект лекций по информатике. 6939: 358–366. Дои:10.1007/978-3-642-24031-7_36. ISBN 978-3-642-24030-0.

[matas-1] а ^б ^c Дж. Матас, О. Чум, М. Урбан и Т. Пайдла. «Надежное стереозвук с широкой базой из максимально устойчивых экстремальных областей». Proc. Британской конференции по машинному зрению, страницы 384-396, 2002.

[compTree-2] а ^б Л. Найман и М. Купри: «Построение дерева компонентов за квазилинейное время» В архиве 2011-04-09 на Wayback Machine; IEEE Transactions по обработке изображений, том 15, номера 11, 2006 г., стр. 3531-3539

[tracking-3] а ^б ^c Донозер М. и Бишоф Х. Эффективное отслеживание максимально стабильной экстремальной области (MSER) CVPR, 2006.

[descriptor-4] а ^б ^c Форссен, П.Е. и Лоу, Д. «Дескрипторы формы для максимально устойчивых экстремальных областей» В архиве 2011-06-10 на Wayback Machine ICCV, 2007.

[stewenius_nister-5] а ^б Нистер, Д. и Стюениус, Х., «Максимально устойчивые экстремальные области по линейному времени», ECCV, 2008.

[compare-6] а ^б ^c К. Миколайчик, Т. Туйтелаарс, К. Шмид, А. Зиссерман, Т. Кадир и Л. Ван Гул: «Сравнение детекторов аффинной области»; Международный журнал компьютерного зрения, том 65, номера 1-2 / ноябрь 2005 г., стр. 43-72

[AntiExt-7] Салембье, Филипп; А. Оливерас; Л. Гарридо (1998). «Анти-обширные подключенные операторы для обработки изображений и последовательностей». IEEE Transactions по обработке изображений. 7 (4): 555–570. Дои:10.1109/83.663500. HDL:2117/90134. PMID 18276273. Архивировано из оригинал на 2012-04-25. Получено 2011-11-17.

[chen-8] Чен, Хуэйчжун; Цай, Сэм; Шрот, Георг; Чен, Дэвид; Гжещук, Радек; Жирод, Бернд. «Надежное обнаружение текста в естественных изображениях с максимально стабильными экстремальными областями с улучшенными краями». Proc. Международная конференция IEEE по обработке изображений, 2011 г..

[shi-9] Ши, Цуньчжао; Ван, Чунхэн; Сяо, Байхуа; Гао, Сун (15 января 2013 г.). «Обнаружение текста сцены с использованием графической модели, построенной на максимально устойчивых экстремальных областях». Письма с распознаванием образов. 34 (2): 107–116. Дои:10.1016 / j.patrec.2012.09.019.

[neumann-10] Нойман, Лукас; Матас, Иржи (2011). «Метод локализации и распознавания текста в изображениях реального мира». Accv 2010: 770–783.

[mscr-11] Форссен, П.Е. Максимально стабильные цветовые области для распознавания и сопоставления В архиве 2011-06-10 на Wayback Machine, CVPR, 2007.

[chavez-12] Чавес, Аарон; Густафсон, Дэвид (2011). «Расширения на основе цвета для MSER». ISVC 2011. Конспект лекций по информатике. 6939: 358–366. Дои:10.1007/978-3-642-24031-7_36. ISBN 978-3-642-24030-0.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]