Regiones extremas de máxima estabilidad

En la visión artificial , la técnica de regiones extremas de máxima estabilidad ( MSER ) ​​se utiliza como método de detección de manchas en imágenes. Matas et al. ^[1] propuso esta técnica para encontrar correspondencias entre elementos de imagen tomados de dos imágenes con diferentes puntos de vista. Este método de extracción de una cantidad completa de elementos de imagen correspondientes contribuye a la coincidencia de línea base amplia y ha dado lugar a mejores algoritmos de reconocimiento de objetos y coincidencia estéreo .

Términos y definiciones

La imagen es un mapeo . Las regiones extremas están bien definidas en las imágenes si: ${\displaystyle I}$ ${\displaystyle I:D\subset \mathbb {Z} ^{2}\to S}$

1. ${\displaystyle S}$está totalmente ordenada (existen relaciones binarias totales, antisimétricas y transitivas ). ${\displaystyle \leq }$
2. Se define una relación de adyacencia . Denotaremos que dos puntos son adyacentes como . ${\displaystyle A\subset D\times D}$ ${\displaystyle pAq}$

Una región es un subconjunto contiguo (también conocido como conectado) de . (Para cada uno existe una secuencia como ). Nótese que, según esta definición, la región puede contener "agujeros" (por ejemplo, una región en forma de anillo está conectada, pero su círculo interno no es parte de ). ${\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}$

Límite de región (exterior) , lo que significa que el límite de es el conjunto de píxeles adyacentes a al menos un píxel de pero que no pertenecen a . Nuevamente, en el caso de regiones con "agujeros", el límite de región no está obligado a ser un subconjunto conectado de (un anillo tiene un límite interno y un límite externo que no se intersecan). ${\displaystyle \partial Q=\{q\in D\setminus Q:\exists p\in Q:qAp\}}$ ${\displaystyle \partial Q}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle D}$

La región extrema es una región tal que, ya sea para todos (región de máxima intensidad) o para todos (región de mínima intensidad), siempre que esté totalmente ordenada, podemos reformular estas condiciones como para la región de máxima intensidad y para la región de mínima intensidad, respectivamente. En esta forma podemos utilizar una noción de valor de intensidad umbral que separa la región y su límite. ${\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))}$

Región extremal de máxima estabilidad Sea una región extremal tal que todos sus puntos tengan una intensidad menor que . Nótese que para todos los positivos , la región extremal es de máxima estabilidad si y solo si tiene un mínimo local en . (Aquí denota cardinalidad). es aquí un parámetro del método. ${\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}$

La ecuación busca regiones que permanezcan estables a lo largo de un cierto número de umbrales. Si una región no es significativamente más grande que una región , se considera que la región es una región de máxima estabilidad. ${\displaystyle Q_{i+\Delta }}$ ${\displaystyle Q_{i-\Delta }}$ ${\displaystyle Q_{i}}$

El concepto se puede explicar de forma más sencilla mediante la definición de umbral . Todos los píxeles que se encuentran por debajo de un umbral determinado son "negros" y todos los que se encuentran por encima o por encima son "blancos". Dada una imagen de origen, si se genera una secuencia de imágenes resultantes con umbral donde cada imagen corresponde a un umbral creciente t, primero se verá una imagen blanca, luego aparecerán puntos "negros" correspondientes a los mínimos de intensidad local y luego se harán más grandes. Se encuentra una región extremal de máxima estabilidad cuando el tamaño de una de estas áreas negras es el mismo (o casi el mismo) que en la imagen anterior. ${\displaystyle I_{t}}$ ${\displaystyle t}$

Estos puntos "negros" se irán fusionando hasta que toda la imagen sea negra. El conjunto de todos los componentes conectados en la secuencia es el conjunto de todas las regiones extremas. En ese sentido, el concepto de MSER está vinculado al de árbol de componentes de la imagen. ^[2] El árbol de componentes proporciona, de hecho, una forma sencilla de implementar MSER. ^[3]

Regiones extremas

Las regiones extremas en este contexto tienen dos propiedades importantes: que el conjunto está cerrado bajo...

1. Transformación continua de las coordenadas de la imagen. Esto significa que es invariante afín y no importa si la imagen está deformada o torcida.
2. Transformación monótona de las intensidades de la imagen. El enfoque es, por supuesto, sensible a los efectos de la iluminación natural, como el cambio de la luz del día o las sombras en movimiento.

Ventajas del MSER

Dado que las regiones se definen exclusivamente por la función de intensidad en la región y el borde exterior, esto da lugar a muchas características clave de las regiones que las hacen útiles. En un amplio rango de umbrales, la binarización local es estable en ciertas regiones y tiene las propiedades que se enumeran a continuación.

• Invariancia a la transformación afín de las intensidades de la imagen
• Transformación (continua) que preserva la covarianza de la adyacencia en el dominio de la imagen ${\displaystyle T:D\to D}$
• Estabilidad : sólo se seleccionan las regiones cuyo apoyo es casi el mismo en un rango de umbrales.
• Detección multiescala sin suavizado, se detectan tanto estructuras finas como grandes.
  Sin embargo, cabe señalar que la detección de MSER en una pirámide de escala mejora la repetibilidad y la cantidad de correspondencias entre los cambios de escala. ^[4]
• El conjunto de todas las regiones extremas se puede enumerar en el peor de los casos , donde es el número de píxeles en la imagen. ^[5] ${\displaystyle O(n)}$ ${\displaystyle n}$

Comparación con otros detectores de regiones

En Mikolajczyk et al., ^[6] se estudian seis detectores de región ( afín a Harris , afín a Hess , MSER, regiones basadas en bordes, extremos de intensidad y regiones salientes ). A continuación se presenta un resumen del rendimiento del MSER en comparación con los otros cinco.

• Densidad de regiones : en comparación con otros, MSER ofrece la mayor variedad, ya que detecta aproximadamente 2600 regiones para una escena con desenfoque texturizado y 230 para una escena con cambios de luz. En general, se considera que la variedad es buena. Además, MSER tuvo una repetibilidad del 92 % para esta prueba.
• Tamaño de la región : MSER tendió a detectar muchas regiones pequeñas, en comparación con regiones grandes que tienen más probabilidades de estar ocluidas o de no cubrir una parte plana de la escena. Sin embargo, las regiones grandes pueden ser un poco más fáciles de igualar.
• Cambio de punto de vista : MSER supera a los otros cinco detectores de región tanto en las imágenes originales como en aquellas con motivos de textura repetidos.
• Cambio de escala : después del detector afín a Hess, el MSER ocupa el segundo lugar en cuanto a cambio de escala y rotación en el plano.
• Desenfoque : MSER demostró ser el método más sensible a este tipo de cambio en la imagen, la única área en la que este tipo de detección es deficiente.
  Sin embargo, cabe señalar que en esta evaluación no se utilizó la detección multirresolución, que ha demostrado mejorar la repetibilidad en condiciones de desenfoque. ^[4]
• Cambio de luz : MSER mostró el puntaje de repetibilidad más alto para este tipo de escena, mientras que todos los demás también tuvieron una buena robustez.

MSER obtuvo consistentemente el puntaje más alto a través de muchas pruebas, lo que demuestra que es un detector de región confiable. ^[6]

Implementación

El algoritmo original de Matas et al. ^[1] se basa en el número de píxeles. Primero se ordenan los píxeles por intensidad. Esto llevaría tiempo, utilizando BINSORT . Después de la ordenación, los píxeles se marcan en la imagen y se mantiene la lista de componentes conectados en crecimiento y fusión y sus áreas utilizando el algoritmo union-find . Esto llevaría tiempo. En la práctica, estos pasos son muy rápidos. Durante este proceso, se almacena el área de cada componente conectado en función de la intensidad, lo que produce una estructura de datos. La fusión de dos componentes se considera como la terminación de la existencia del componente más pequeño y una inserción de todos los píxeles del componente más pequeño en el más grande. En las regiones extremas, las "máximamente estables" son las que corresponden a los umbrales donde el cambio de área relativa en función del cambio relativo del umbral está en un mínimo local, es decir, las MSER son las partes de la imagen donde la binarización local es estable en un amplio rango de umbrales. ^{[1] [6]} ${\displaystyle O(n\,\log(\log(n)))}$ ${\displaystyle n\,}$ ${\displaystyle O(n)\,}$ ${\displaystyle O(n\,\log(\log(n)))}$

El árbol de componentes es el conjunto de todos los componentes conectados de los umbrales de la imagen, ordenados por inclusión. Existen algoritmos eficientes (cuasi-lineales cualquiera sea el rango de los pesos) para calcularlo. ^[2] Por lo tanto, esta estructura ofrece una manera fácil de implementar MSER. ^[3]

Más recientemente, Nister y Stewenius propusieron un método verdaderamente para el peor de los casos (si los pesos son números enteros pequeños) en ^[5] , que también es mucho más rápido en la práctica. Este algoritmo es similar al de Ph. Salembier et al. ^[7]. ${\displaystyle O(n)\,}$

Algoritmo robusto de base amplia

El propósito de este algoritmo es hacer coincidir los MSER para establecer puntos de correspondencia entre imágenes. Primero, se calculan las regiones MSER en la imagen de intensidad (MSER+) y en la imagen invertida (MSER-). Las regiones de medición se seleccionan en múltiples escalas: el tamaño de la región real, la envoltura convexa escalada a 1,5x, 2x y 3x de la región. La coincidencia se logra de manera robusta, por lo que es mejor aumentar la distinción de regiones grandes sin verse gravemente afectado por el desorden o la no planaridad de la preimagen de la región. Una medición tomada de un parche casi plano de la escena con una descripción invariante estable se denomina "buena medición". Las inestables o aquellas en superficies no planas o discontinuidades se denominan "mediciones corruptas". La similitud robusta se calcula: para cada región en se encuentran las regiones de la otra imagen con la i-ésima medición correspondiente más cercana a y se emite un voto que sugiere la correspondencia de A y cada uno de . Los votos se suman sobre todas las mediciones y, utilizando el análisis de probabilidad, se pueden seleccionar las "mediciones buenas", ya que las "mediciones corruptas" probablemente distribuirán sus votos de manera aleatoria. Al aplicar RANSAC a los centros de gravedad de las regiones, se puede calcular una geometría epipolar aproximada . Se calcula una transformación afín entre pares de regiones potencialmente correspondientes y las correspondencias la definen hasta una rotación, que luego se determina mediante líneas epipolares. Luego, se filtran las regiones y se eligen aquellas con correlación de sus imágenes transformadas por encima de un umbral. Se aplica RANSAC nuevamente con un umbral más estrecho y se estima la geometría epipolar final mediante el algoritmo de ocho puntos . ${\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}}$

Este algoritmo se puede probar aquí (coincidencias restringidas por geometría epipolar o de homografía): WBS Image Matcher

Uso en detección de texto

Chen ha utilizado el algoritmo MSER en la detección de texto combinando MSER con los bordes Canny . Los bordes Canny se utilizan para ayudar a hacer frente a la debilidad del MSER para desenfocar. Primero se aplica MSER a la imagen en cuestión para determinar las regiones de caracteres. Para mejorar las regiones MSER, se eliminan los píxeles fuera de los límites formados por los bordes Canny. La separación de estos últimos proporcionada por los bordes aumenta en gran medida la utilidad del MSER en la extracción de texto desenfocado. ^[8]

Un uso alternativo de MSER en la detección de texto es el trabajo de Shi que utiliza un modelo gráfico. Este método aplica nuevamente MSER a la imagen para generar regiones preliminares. Estas se utilizan luego para construir un modelo gráfico basado en la distancia de posición y la distancia de color entre cada MSER, que se trata como un nodo. A continuación, los nodos se separan en primer plano y fondo utilizando funciones de costo. Una función de costo relaciona la distancia desde el nodo hasta el primer plano y el fondo. La otra penaliza a los nodos por ser significativamente diferentes de su vecino. Cuando estos se minimizan, el gráfico se corta para separar los nodos de texto de los nodos que no son de texto. ^[9]

Para permitir la detección de texto en una escena general, Neumann utiliza el algoritmo MSER en una variedad de proyecciones. Además de la proyección de intensidad en escala de grises, utiliza los canales de color rojo, azul y verde para detectar regiones de texto que son distintas en color pero no necesariamente distintas en intensidad en escala de grises. Este método permite la detección de más texto que utilizando únicamente las funciones MSER+ y MSER- analizadas anteriormente. ^[10]

Ampliaciones y adaptaciones

• El algoritmo MSER se ha adaptado a imágenes en color, reemplazando el umbral de la función de intensidad con agrupamiento aglomerativo , basado en gradientes de color. ^[11]
• El algoritmo MSER se puede utilizar para detectar regiones en función del color en lugar de la intensidad. Chavez lo hace creando una función de intensidad para el rojo, el verde y el azul en el espacio de color HSV . Luego, el algoritmo MSER se ejecuta cinco veces; sobre las tres pseudointensidades de color y luego sobre las intensidades de la escala de grises utilizando las funciones estándar MSER+ y MSER-. ^[12]
• El algoritmo MSER se puede utilizar para rastrear objetos de color, realizando la detección MSER en la distancia de Mahalanobis a una distribución de color. ^[3]
• Al detectar MSER en múltiples resoluciones, se puede mejorar la robustez al desenfoque y al cambio de escala. ^[4]

Otras aplicaciones

• Descriptores de forma para regiones extremas de máxima estabilidad
• Seguimiento eficiente de la región extrema de máxima estabilidad (MSER)
• Bosques disjuntos de árboles N para regiones extremas de máxima estabilidad
• Vídeo Google y agrupación a nivel de objeto para tomas de vídeo
• Extracción en tiempo real de regiones extremas de máxima estabilidad en un FPGA
• Regiones de color de máxima estabilidad para reconocimiento y comparación

Véase también

• Detección de manchas
• Detección de características (visión por computadora)

Enlaces externos

• VLFeat, una biblioteca de visión por computadora de código abierto en C (con una interfaz MEX para MATLAB ), que incluye una implementación de MSER
• OpenCV, una biblioteca de visión por computadora de código abierto en C/ C++ , que incluye una implementación de MSER de tiempo lineal
• Estudio de repetibilidad del detector, binarios de Kristian Mikolajczyk (Win/Linux para calcular MSER/HarrisAffine... Binario utilizado en su estudio de repetibilidad.
• Implementación de MSER en tiempo lineal, Charles Dubout, implementación de MSER en C++ como detector de blobs

Referencias

1. J. Matas, O. Chum, M. Urban y T. Pajdla. "Estéreo de línea de base amplia y robusta a partir de regiones extremas de máxima estabilidad". Actas de la British Machine Vision Conference, páginas 384-396, 2002.
2. L. Najman y M. Couprie: "Construcción del árbol de componentes en tiempo cuasi-lineal" Archivado el 9 de abril de 2011 en Wayback Machine ; IEEE Transactions on Image Processing, Volumen 15, Números 11, 2006, pp 3531-3539
3. Donoser, M. y Bischof, H. Seguimiento eficiente de la región extrema máximamente estable (MSER) ​​CVPR , 2006.
4. Forssen, PE. y Lowe, DG "Descriptores de forma para regiones extremas máximamente estables" Archivado el 10 de junio de 2011 en Wayback Machine. ICCV, 2007.
5. Nister, D. y Stewenius, H., "Regiones extremas máximamente estables en el tiempo lineal", ECCV, 2008.
6. K. Mikolajczyk, T. Tuytelaars, C. Schmid, A. Zisserman, T. Kadir y L. Van Gool: "Una comparación de detectores de regiones afines"; International Journal of Computer Vision, volumen 65, números 1-2 / noviembre de 2005, págs. 43-72
7. Salembier, Philippe; A. Oliveras; L. Garrido (1998). "Operadores conectados antiextensivos para procesamiento de imágenes y secuencias". IEEE Transactions on Image Processing . 7 (4): 555–570. Bibcode :1998ITIP....7..555S. doi :10.1109/83.663500. hdl : 2117/90134 . PMID  18276273. Archivado desde el original el 25 de abril de 2012 . Consultado el 17 de noviembre de 2011 .
8. Chen, Huizhong; Tsai, Sam; Schroth, Georg; Chen, David; Grzeszczuk, Radek; Girod, Bernd . "Detección de texto robusta en imágenes naturales con regiones extremas de máxima estabilidad mejoradas en los bordes". Proc. Conferencia internacional IEEE sobre procesamiento de imágenes 2011 .
9. Shi, Cunzhao; Wang, Chunheng; Xiao, Baihua; Gao, Song (15 de enero de 2013). "Detección de texto en escenas utilizando un modelo gráfico construido sobre regiones extremas de máxima estabilidad". Pattern Recognition Letters . 34 (2): 107–116. Bibcode :2013PaReL..34..107S. doi :10.1016/j.patrec.2012.09.019.
10. Neumann, Lukas; Matas, Jiri (2011). "Un método para la localización y el reconocimiento de texto en imágenes del mundo real". Accv 2010 : 770–783.
11. Forssen, PE. Regiones de color de máxima estabilidad para reconocimiento y correspondencia Archivado el 10 de junio de 2011 en Wayback Machine , CVPR, 2007.
12. Chavez, Aaron; Gustafson, David (2011). "Extensiones basadas en color para MSER". Isvc 2011. Apuntes de clase en informática. 6939 : 358–366. doi :10.1007/978-3-642-24031-7_36. ISBN . 978-3-642-24030-0.