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

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

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

1. ${\displaystyle S}$полностью упорядочен ( существуют полные, антисимметричные и транзитивные бинарные отношения).${\displaystyle \leq }$
2. Определено отношение смежности . Будем обозначать, что две точки смежны, как .${\displaystyle A\subset D\times 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\subset D}$${\displaystyle p\in Q,q\in \partial Q:I(p)>I(q)}$${\displaystyle p\in Q,q\in \partial Q:I(p)<I(q)}$${\displaystyle S}$${\displaystyle \min(I(p))>\max(I(q))}$${\displaystyle \max(I(p))<\min(I(q))}$

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

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

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

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

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

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

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

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

В работе Миколайчика и др. ^[6] изучаются шесть детекторов областей ( Harris-affine , Hessian-affine , MSER, области на основе краев, экстремумы интенсивности и заметные области ). Ниже приводится сводка производительности MSER по сравнению с пятью другими.

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

MSER неизменно показывал наивысшие результаты во многих тестах, доказав, что он является надежным детектором регионов. ^[6]

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

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

Совсем недавно Нистер и Стевениус предложили действительно (если вес — это малые целые числа) метод худшего случая в ^[5], который также намного быстрее на практике. Этот алгоритм похож на алгоритм Ф. Салембьера и др. ^[7]${\displaystyle O(n)\,}$

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

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

Алгоритм MSER использовался Ченом для обнаружения текста путем объединения MSER с границами Canny . Границы 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++ , включающая реализацию линейного времени MSER
• Исследование повторяемости детектора, Кристиан Миколайчик Двоичные файлы (Win/Linux для вычисления MSER/HarrisAffine... . Двоичный файл, используемый в его исследовании повторяемости.
• Реализация MSER с линейной реализацией времени, Чарльз Дюбу, реализация MSER на C++ в качестве детектора больших двоичных объектов