En visión artificial , las regiones extremas máximamente estables ( MSER ) se utilizan como método de detección de manchas en imágenes. Esta técnica fue propuesta por Matas et al. [1] para encontrar correspondencias entre elementos de imagen de dos imágenes con diferentes puntos de vista. Este método de extraer un número completo de elementos de imagen correspondientes contribuye a la coincidencia de línea de base amplia y ha conducido a mejores algoritmos de coincidencia estéreo y reconocimiento de objetos .
Términos y definiciones
Imagen es un mapeo . Las regiones extremas están bien definidas en las imágenes si:
- está totalmente ordenado (relaciones binarias totales, antisimétricas y transitivas existe).
- Una relación de adyacencia se define. Denotaremos que dos puntos son adyacentes como.
Región es un subconjunto contiguo (también conocido como conectado) de . (Para cada hay una secuencia como .) Tenga en cuenta 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 la parte de ).
Límite de la región (exterior) , que significa el límite de es el conjunto de píxeles adyacentes a al menos un píxel de pero no perteneciendo a . Nuevamente, en el caso de regiones con "huecos", el límite de la región no está obligado a estar conectado como subconjunto de (un anillo tiene un límite interior y otro exterior que no se cruzan).
Región extrema es una región tal que para todos (región de máxima intensidad) o para todos (región de mínima intensidad). Hasta está totalmente ordenado, podemos reformular estas condiciones como para la región de máxima intensidad y para la región de intensidad mínima, respectivamente. De esta forma podemos utilizar la noción de un valor umbral de intensidad que separa la región y su límite.
Región extremal máximamente estable Sea una región extrema como todos los puntos en ella tienen una intensidad menor que . Nota para todo positivo . Región extrema es máximamente estable si y solo si tiene un mínimo local en . (Aquí denota cardinalidad). es aquí un parámetro del método.
La ecuación busca regiones que permanezcan estables sobre un cierto número de umbrales. Si una región no es significativamente más grande que una región , región se toma como una región máximamente estable.
El concepto se puede explicar de forma más sencilla mediante la creación de umbrales . Todos los píxeles por debajo de un umbral determinado son 'negros' y todos los que están por encima o iguales son 'blancos'. Dada una imagen de origen, si una secuencia de imágenes de resultado con umbral se genera donde cada imagen corresponde a un umbral t creciente, primero se vería una imagen blanca, luego aparecerían puntos 'negros' correspondientes a los mínimos de intensidad local y luego se agrandarían. Se encuentra una región extremamente estable máxima cuando el tamaño de una de estas áreas negras es el mismo (o casi el mismo) que en la imagen anterior.
Estos puntos 'negros' eventualmente se fusionarán, 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á ligado al de árbol componente de la imagen. [2] De hecho, el árbol de componentes proporciona una forma sencilla de implementar MSER. [3]
Regiones extremas
Las regiones extremas en este contexto tienen dos propiedades importantes, que el conjunto se cierra bajo ...
- 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 sesgada.
- transformación monótona de intensidades de imagen. El enfoque es, por supuesto, sensible a los efectos de la iluminación natural como el cambio de luz del día o las sombras en movimiento.
Ventajas de MSER
Debido a que las regiones están definidas exclusivamente por la función de intensidad en la región y el borde exterior, esto conduce a muchas características clave de las regiones que las hacen útiles. En una amplia gama de umbrales, la binarización local es estable en determinadas regiones y tiene las propiedades que se enumeran a continuación.
- Invarianza a la transformación afín de las intensidades de la imagen
- Transformación (continua) de conservación de covarianza con adyacencia en el dominio de la imagen
- Estabilidad : solo se seleccionan las regiones cuyo soporte es casi el mismo en un rango de umbrales.
- Detección de múltiples escalas sin ningún suavizado involucrado, se detecta tanto la estructura fina como la grande.
Sin embargo, tenga en cuenta que la detección de MSER en una pirámide de escala mejora la repetibilidad y el número de correspondencias entre los cambios de escala. [4] - El conjunto de todas las regiones extremas se puede enumerar en el peor de los casos, dónde es el número de píxeles de la imagen. [5]
Comparación con otros detectores de región
En Mikolajczyk et al., [6] se estudian seis detectores de regiones (afines de Harris, afines de Hesse, MSER, regiones basadas en bordes, extremos de intensidad y regiones salientes). A continuación se muestra un resumen del rendimiento de MSER en comparación con los otros cinco.
- Densidad de región : en comparación con los demás, MSER ofrece la mayor variedad al detectar alrededor de 2600 regiones para una escena con textura borrosa y 230 para una escena con cambios de luz, y la variedad generalmente se considera buena. Además, MSER tuvo una repetibilidad del 92% para esta prueba.
- Tamaño de la región : el MSER tendía a detectar muchas regiones pequeñas, frente a las regiones grandes que tienen más probabilidades de estar ocluidas o de no cubrir una parte plana de la escena. Aunque las regiones grandes pueden ser un poco más fáciles de combinar.
- 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 hessiano, MSER ocupa el segundo lugar bajo un cambio de escala y rotación en el plano.
- Desenfoque : MSER demostró ser el más sensible a este tipo de cambio en la imagen, que es la única área en la que carece este tipo de detección.
Sin embargo, tenga en cuenta que esta evaluación no hizo uso de la detección de resolución múltiple, que se ha demostrado para mejorar la repetibilidad bajo desenfoque. [4] - Cambio de luz : MSER mostró el puntaje de repetibilidad más alto para este tipo de escena, y todas las demás también tuvieron una buena robustez.
MSER obtuvo constantemente la puntuación más alta 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] es en el numero de píxeles. Continúa clasificando primero los píxeles por intensidad. Esto tomaríatiempo, utilizando BINSORT . Después de ordenar, los píxeles se marcan en la imagen y la lista de componentes conectados que crecen y se fusionan y sus áreas se mantiene mediante el algoritmo de búsqueda de unión . Esto tomaríahora. En la práctica, estos pasos son muy rápidos. Durante este proceso, el área de cada componente conectado en función de la intensidad se almacena produciendo una estructura de datos. Una fusión de dos componentes se considera la terminación de la existencia del componente más pequeño y la 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 correspondientes a los umbrales donde el cambio de área relativa en función del cambio relativo de umbral está en un mínimo local, es decir, las MSER son las partes de la imagen donde la binarización local es estable durante una amplia gama de umbrales. [1] [6]
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 que sea el rango de pesos) para calcularlo. [2] Por tanto, esta estructura ofrece una forma sencilla de implementar MSER. [3]
Más recientemente, Nister y Stewenius han propuesto un verdadero (si el peso son números enteros pequeños) en el peor de los casos método 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]
Algoritmo robusto de línea de base amplia
El propósito de este algoritmo es hacer coincidir los MSER para establecer puntos de correspondencia entre imágenes. Las primeras regiones de MSER se calculan en la imagen de intensidad (MSER +) y en la imagen invertida (MSER-). Las regiones de medición se seleccionan a múltiples escalas: el tamaño de la región real, el casco convexo a escala de 1.5x, 2x y 3x de la región. El emparejamiento se logra de manera sólida, por lo que es mejor aumentar el carácter distintivo de grandes regiones sin verse gravemente afectado por el desorden o la falta de planitud de la imagen previa de la región. Una medida tomada de un parche casi plano de la escena con una descripción invariante estable se denomina "buena medida". Las inestables o las que se encuentran en superficies no planas o discontinuidades se denominan "medidas corruptas". Se calcula la similitud robusta: Para cada en la región regiones de la otra imagen con la i-ésima medida correspondiente más cercano a se encuentran y se emite un voto que sugiere la correspondencia de A y cada uno de . Los votos se suman en todas las mediciones y, mediante el análisis de probabilidad, se pueden seleccionar 'buenas mediciones' ya que las 'mediciones corruptas' probablemente distribuirán sus votos al azar. 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. A continuación, se filtran las regiones y se eligen las que tienen correlación de sus imágenes transformadas por encima de un umbral. RANSAC se aplica de nuevo con un umbral más estrecho y la geometría epipolar final se estima mediante el algoritmo de ocho puntos .
Este algoritmo se puede probar aquí (coincidencias con restricciones de geometría epipolar o de homografía): WBS Image Matcher
Usar en la detección de texto
Chen ha utilizado el algoritmo MSER en la detección de texto combinando MSER con bordes Canny. Los bordes astutos se utilizan para ayudar a lidiar con la debilidad de MSER para desenfocar. MSER se aplica primero 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 los últimos proporcionada por los bordes aumenta en gran medida la usabilidad de MSER en la extracción de texto borroso. [8] Un uso alternativo de MSER en la detección de texto es el trabajo de Shi usando un modelo gráfico. Este método vuelve a aplicar MSER a la imagen para generar regiones preliminares. Luego, estos se utilizan para construir un modelo de 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 en segundo plano mediante funciones de coste. Una función de costo es relacionar la distancia desde el nodo hasta el primer plano y el fondo. El otro penaliza a los nodos por ser significativamente diferentes de su vecino. Cuando se minimizan, el gráfico se corta para separar los nodos de texto de los nodos que no son de texto. [9] Para habilitar la detección de texto en una escena general, Neumann usa el algoritmo MSER en una variedad de proyecciones. Además de la proyección de la intensidad de la escala de grises, utiliza los canales de color rojo, azul y verde para detectar regiones de texto que son de colores distintos pero no necesariamente distintos en la intensidad de la escala de grises. Este método permite la detección de más texto que utilizando únicamente las funciones MSER + y MSER- discutidas anteriormente. [10]
Extensiones 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 según el color en lugar de la intensidad. Esto lo hace Chávez mediante la creación de 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 pseudo-intensidades 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 solidez al desenfoque y el cambio de escala. [4]
Otras aplicaciones
- Descriptores de forma para regiones extremas máximamente estables
- Seguimiento eficiente de la región extrema extremadamente estable (MSER)
- Bosques de conjuntos disjuntos de N árboles para regiones extremas máximamente estables
- Google de video y agrupación a nivel de objeto para tomas de video
- Extracción en tiempo real de regiones extremas máximamente estables en una FPGA
- Regiones de color máximamente estables para reconocimiento y coincidencia
Ver también
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 Linear Time MSER
- Estudio de repetibilidad del detector , Kristian Mikolajczyk Binaries (Win / Linux para calcular MSER / HarrisAffine ... Binario utilizado en su estudio de repetibilidad.
- Implementación de MSER en tiempo lineal , Charles Dubout, implementación en C ++ de MSER como detector de manchas
Referencias
- ^ a b c J. Matas, O. Chum, M. Urban y T. Pajdla. "Estéreo de línea de base amplia y robusto de regiones extremas de máxima estabilidad". Proc. of British Machine Vision Conference, páginas 384-396, 2002.
- ^ a b L. Najman y M. Couprie: "Construyendo el árbol de componentes en tiempo cuasi-lineal" Archivado 2011-04-09 en Wayback Machine ; Transacciones IEEE sobre procesamiento de imágenes, volumen 15, números 11, 2006, págs. 3531-3539
- ^ a b c Donoser, M. y Bischof, H. Seguimiento de la región extrema extremadamente estable y eficiente (MSER) CVPR , 2006.
- ^ a b c Forssen, PE. y Lowe, DG "Descriptores de forma para regiones extremas máximamente estables" Archivado el 10 de junio de 2011 en la Wayback Machine ICCV, 2007.
- ^ a b Nister, D. y Stewenius, H., "Regiones extremas máximamente estables en tiempo lineal" , ECCV, 2008.
- ^ a b c K. Mikolajczyk, T. Tuytelaars, C. Schmid, A. Zisserman, T. Kadir y L. Van Gool: "Una comparación de detectores de regiones afines" ; Revista Internacional de Visión por Computadora, Volumen 65, Números 1-2 / Noviembre de 2005, págs. 43-72
- ^ Salembier, Philippe; A. Oliveras; L. Garrido (1998). "Operadores conectados anti-extensivos para procesamiento de imágenes y secuencias" . Transacciones IEEE sobre procesamiento de imágenes . 7 (4): 555–570. 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 .
- ^ Chen, Huizhong; Tsai, Sam; Schroth, Georg; Chen, David; Grzeszczuk, Radek; Girod, Bernd . "Detección de texto robusta en imágenes naturales con regiones extremas máximamente estables mejoradas en los bordes" . Proc. Conferencia internacional IEEE sobre procesamiento de imágenes 2011 .
- ^ Shi, Cunzhao; Wang, Chunheng; Xiao, Baihua; Gao, Song (15 de enero de 2013). "Detección de texto de escena usando un modelo de gráfico construido sobre regiones extremas máximamente estables". Cartas de reconocimiento de patrones . 34 (2): 107-116. doi : 10.1016 / j.patrec.2012.09.019 .
- ^ 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.
- ^ Forssen, PE. Regiones de color máximamente estables para el reconocimiento y la coincidencia. Archivado el 10 dejunio de 2011en Wayback Machine , CVPR, 2007.
- ^ Chávez, Aaron; Gustafson, David (2011). "Extensiones basadas en color para MSER". Isvc 2011 . Apuntes de conferencias en informática. 6939 : 358–366. doi : 10.1007 / 978-3-642-24031-7_36 . ISBN 978-3-642-24030-0.