Template Matching | Presstorms

Estás aquí:Inicio «Guía de Visión Artificial «Template Matching

Introducción

El Template Matching es una técnica de visión artificial de alto nivel que identifica las partes de una imagen que coinciden con una plantilla predefinida. Los algoritmos avanzados de concordancia de plantillas permiten encontrar apariciones de la plantilla independientemente de su orientación y brillo local.

Las técnicas de concordancia de plantillas son flexibles y relativamente sencillas de utilizar, lo que las convierte en uno de los métodos más populares de localización de objetos. Su aplicabilidad está limitada principalmente por la potencia de cálculo disponible, ya que la identificación de plantillas grandes y complejas puede llevar mucho tiempo.

Concepto

Se espera que las técnicas de comparación de plantillas aborden la siguiente necesidad: si se proporciona una imagen de referencia de un objeto (la imagen de la plantilla) y una imagen que se va a inspeccionar (la imagen de entrada), queremos identificar todas las ubicaciones de la imagen de entrada en las que está presente el objeto de la imagen de la plantilla. Dependiendo del problema específico, podemos (o no) querer identificar las apariciones rotadas o escaladas.

Empezaremos con una demostración de un método ingenuo de Template Matching, que es insuficiente para las aplicaciones de la vida real, pero que ilustra el concepto central del que parten los algoritmos actuales de Template Matching. Después explicaremos cómo este método es mejorado y extendido en rutinas avanzadas de Emparejamiento Basado en Escala de Grises y Emparejamiento Basado en Bordes.

Emparejamiento Ingenuo de Plantillas

Imagina que vamos a inspeccionar una imagen de un enchufe y nuestro objetivo es encontrar sus pines. Se nos proporciona una imagen de plantilla que representa el objeto de referencia que buscamos y la imagen de entrada a inspeccionar.


Imagen de la plantilla	Imagen de entrada

Realizaremos la búsqueda real de una manera bastante directa – posicionaremos la plantilla sobre la imagen en cada ubicación posible, y cada vez calcularemos alguna medida numérica de similitud entre la plantilla y el segmento de la imagen con el que se solapa. Por último, identificaremos las posiciones que arrojen las mejores medidas de similitud como las probables ocurrencias de la plantilla.

Correlación de imágenes

Uno de los subproblemas que se plantean en la especificación anterior es el cálculo de la medida de similitud de la imagen de la plantilla alineada y el segmento superpuesto de la imagen de entrada, lo que equivale a calcular una medida de similitud de dos imágenes de iguales dimensiones. Esta es una tarea clásica, y una medida numérica de similitud de imágenes se suele llamar correlación de imágenes.

Correlación cruzada

.Correlación

Imagen1	Imagen2	Correlación cruzada
		19404780
		23316890
		24715810

El método fundamental de cálculo de la correlación de la imagen es el llamado cross-correlación, que esencialmente es una simple suma de multiplicaciones por pares de los valores de los píxeles correspondientes de las imágenes.

Aunque podemos observar que el valor de la correlación parece reflejar la similitud de las imágenes comparadas, el método de correlación cruzada está lejos de ser robusto. Su principal inconveniente es que está sesgado por los cambios en el brillo global de las imágenes – el brillo de una imagen puede disparar su correlación cruzada con otra imagen, incluso si la segunda imagen no es en absoluto similar.

$\mbox{Correlación cruzada}(\mbox{Imagen1}, \mbox{Imagen2})= \sum_{x,y} \mbox{Image1}(x,y) \mbox{Image2}(x,y)$

Correlación cruzada normalizada

Imagen1	Imagen2	NCC
		-0.417
		0.553
		0,844

La correlación cruzada normalizada es una versión mejorada del método clásico de correlación cruzada que introduce dos mejoras con respecto al original:

Los resultados son invariables a los cambios de luminosidad global, es decir, el aclaramiento u oscurecimiento consistente.es decir, el aclaramiento u oscurecimiento consistente de cualquiera de las dos imágenes no tiene efecto sobre el resultado (esto se consigue restando el brillo medio de la imagen del valor de cada píxel).
El valor final de la correlación se escala al rango, de modo que el NCC de dos imágenes idénticas es igual a 1,0, mientras que el NCC de una imagen y su negación es igual a -1,0.

$\mbox{NCC}(\mbox{Imagen1}, \mbox{Imagen2})= \frac{1}{N\sigma_1 \sigma_2} \sum_{x,y} (\mbox{Imagen1}(x,y)-\microespacio{\mbox{Imagen1}) }) \(\mbox{Image2}(x,y)-\más de una línea{\mbox{Image2}) })}$

Imagen de Correlación Ejemplar

Volvamos al problema que nos ocupa. Habiendo introducido la Correlación Cruzada Normalizada -medida robusta de la similitud de la imagen- ahora somos capaces de determinar lo bien que encaja la plantilla en cada una de las posiciones posibles. Podemos representar los resultados en forma de una imagen, donde el brillo de cada píxel representa el valor NCC de la plantilla posicionada sobre este píxel (el color negro representa la correlación mínima de -1,0, el color blanco representa la correlación máxima de 1,0).


Imagen de la plantilla	Imagen de entrada	Imagen de correlación de la plantilla

Identificación de coincidencias

Todo lo que hay que hacer en este punto es decidir qué puntos de la imagen de correlación de plantillas son lo suficientemente buenos como para ser considerados coincidencias reales. Normalmente identificamos como coincidencias las posiciones que (simultáneamente) representan la correlación de la plantilla:

más fuerte que algún valor de umbral predefinido (es decir, más fuerte que 0.5)
máxima localmente (más fuerte que la correlación de la plantilla en los píxeles vecinos)


Áreas de correlación de la plantilla por encima de 0.75	Puntos de correlación de plantilla localmente máxima	Puntos de correlación de plantilla localmente máxima por encima de 0,75

Resumen

Es bastante fácil expresar el método descrito en Adaptive Vision Studio – sólo necesitaremos dos filtros incorporados. Calcularemos la imagen de correlación de la plantilla usando el filtro ImageCorrelationImage, y luego identificaremos las coincidencias usando ImageLocalMaxima – sólo necesitamos establecer el parámetro inMinValue que cortará los máximos locales débiles de los resultados, como se discutió en la sección anterior.

Aunque la técnica introducida era suficiente para resolver el problema considerado, podemos observar sus importantes inconvenientes:

Las ocurrencias de la plantilla tienen que preservar la orientación de la imagen de la plantilla de referencia.
El método es ineficaz, ya que el cálculo de la imagen de correlación de la plantilla para imágenes medianas y grandes requiere mucho tiempo.

En las próximas secciones discutiremos cómo se abordan estos problemas en las técnicas avanzadas de comparación de plantillas: Emparejamiento basado en la escala de grises y emparejamiento basado en los bordes.

Emparejamiento basado en la escala de grises, emparejamiento basado en los bordes

El emparejamiento basado en la escala de grises es un algoritmo avanzado de emparejamiento de plantillas que amplía la idea original de la detección de plantillas basada en la correlación, mejorando su eficiencia y permitiendo la búsqueda de ocurrencias de plantillas independientemente de su orientación. El emparejamiento basado en los bordes mejora aún más este método al limitar el cálculo a las áreas de los bordes del objeto.

En esta sección describiremos los detalles intrínsecos de ambos algoritmos. En la siguiente sección (Conjunto de herramientas de filtrado) explicaremos cómo utilizar estas técnicas en Adaptive Vision Studio.

Pirámide de imágenes

La pirámide de imágenes es una serie de imágenes, siendo cada una de ellas el resultado de un downsampling (reducción de escala, por el factor de dos en este caso) del elemento anterior.


Nivel 0 (imagen de entrada)	Nivel 1	Nivel 2

Procesamiento de pirámides

Se pueden aplicar pirámides de imágenes para mejorar la eficiencia de la correlación-de correlación. La observación importante es que la plantilla representada en la imagen de referencia suele seguir siendo discernible después de una reducción significativa de la imagen (aunque, naturalmente, los detalles finos se pierden en el proceso). Por lo tanto, podemos identificar a los candidatos a coincidir en la imagen reducida (y por lo tanto mucho más rápido de procesar) en el nivel más alto de nuestra pirámide, y luego repetir la búsqueda en los niveles inferiores de la pirámide, cada vez teniendo en cuenta sólo las posiciones de la plantilla que obtuvieron una puntuación alta en el nivel anterior.

En cada nivel de la pirámide necesitaremos una imagen adecuadamente reducida de la plantilla de referencia, es decir, tanto la pirámide de la imagen de entrada como la pirámide de la imagen de la plantilla deben ser calculadas.


Nivel 0 (imagen de referencia de la plantilla)	Nivel 1	Nivel 2

Emparejamiento basado en la escala de grises

.based Matching

Aunque en algunas de las aplicaciones la orientación de los objetos es uniforme y fija (como hemos visto en el ejemplo del enchufe), es frecuente que los objetos a detectar aparezcan girados. En los algoritmos de concordancia de plantillas, la búsqueda clásica de pirámides se adapta para permitir la concordancia multiángulo, es decir, la identificación de instancias rotadas de la plantilla.

Esto se consigue calculando no sólo una pirámide de la imagen de la plantilla, sino un conjunto de pirámides, una para cada posible rotación de la plantilla. Durante la búsqueda de la pirámide en la imagen de entrada, el algoritmo identifica los pares (posición de la plantilla, orientación de la plantilla) en lugar de las únicas posiciones de la plantilla. Al igual que en el esquema original, en cada nivel de la búsqueda el algoritmo verifica sólo los pares (posición, orientación) que obtuvieron una buena puntuación en el nivel anterior (es decir, que parecían coincidir con la plantilla en la imagen de menor resolución).


Imagen de la plantilla	Imagen de entrada	Resultados de la coincidencia multiángulos

La técnica de coincidencia de pirámides junto con la búsqueda de ángulos múltiples constituyen el método de coincidencia de plantillas basado en la escala de grises.

Comparación basada en los bordes

La Comparación basada en los bordes mejora la Comparación basada en la escala de grises anteriormente comentada utilizando una observación crucial: que la forma de cualquier objeto se define principalmente por la forma de sus bordes. Por lo tanto, en lugar de hacer coincidir toda la plantilla, podemos extraer sus bordes y hacer coincidir sólo los píxeles cercanos, evitando así algunos cálculos innecesarios. En las aplicaciones comunes, la velocidad conseguida suele ser significativa.

Comparación basada en la escala de grises:
Comparación basada en los bordes:
Diferentes tipos de pirámides de plantillas utilizadas en los algoritmos de Template Matching.

El emparejamiento de los bordes del objeto en lugar de un objeto en su conjunto requiere una ligera modificación del método original de emparejamiento de pirámides: imaginemos que estamos emparejando un objeto de color uniforme colocado sobre un fondo uniforme. Todos los píxeles de los bordes del objeto tendrían la misma intensidad y el algoritmo original emparejaría el objeto en cualquier lugar en el que hubiera una mancha suficientemente grande del color apropiado, y esto claramente no es lo que queremos conseguir. Para resolver este problema, en la correspondencia basada en los bordes es la dirección del gradiente (representada como un color en el espacio HSV para fines ilustrativos) de los píxeles de los bordes, y no su intensidad, lo que se iguala.

Herramientas de filtro

Adaptive Vision Studio proporciona un conjunto de filtros que implementan tanto la correspondencia basada en la escala de grises como la correspondencia basada en los bordes. Para ver la lista de los filtros vea Template Matching filters.

Como la imagen de la plantilla tiene que ser preprocesada antes de la coincidencia de pirámides (necesitamos calcular las pirámides de la imagen de la plantilla para todas las rotaciones posibles), los algoritmos se dividen en dos partes:

Creación del modelo – en este paso se calculan las pirámides de la imagen de la plantilla y los resultados se almacenan en un modelo – objeto atómico que representa todos los datos necesarios para ejecutar la coincidencia de pirámides.
Coincidencia – en este paso el modelo de plantilla se utiliza para coincidir con la plantilla en la imagen de entrada.

Esta organización del procesamiento hace posible computar el modelo una vez y reutilizarlo múltiples veces.

Filtros disponibles

Para ambos métodos de Template Matching se proporcionan dos filtros, uno para cada paso del algoritmo.

	Comparación basada en la escala de grises	Comparación basada en los bordes
Creación de modelos:
Comparación:

Tenga en cuenta que el uso de los filtros CreateGrayModel y CreateEdgeModel sólo será necesario en aplicaciones más avanzadas. En caso contrario, bastará con utilizar un único filtro del paso Matching y crear el modelo estableciendo el parámetro inGrayModel o inEdgeModel del filtro. Para obtener más información, consulte Creación de modelos para la correspondencia de plantillas.

El principal reto de la aplicación de la técnica de correspondencia de plantillas reside en el ajuste cuidadoso de los parámetros del filtro, más que en el diseño de la estructura del programa.

Esquema de aplicación avanzada

Hay varios tipos de aplicaciones avanzadas, para las que la GUI interactiva para Template Matching no es suficiente y el usuario necesita utilizar el filtro CreateGrayModel o CreateEdgeModel directamente. Por ejemplo:

Cuando la creación del modelo requiere un preprocesamiento de imágenes no trivial.
Cuando necesitamos un conjunto completo de modelos creados automáticamente a partir de un conjunto de imágenes.
Cuando el usuario final debe ser capaz de definir sus propias plantillas en la aplicación en tiempo de ejecución (por ejemplo, haciendo una selección en una imagen de entrada).

Esquema 1: Creación del modelo en un programa separado

Para los casos 1 y 2 es aconsejable implementar la creación del modelo en un macrofiltro de Tarea separado, guardar el modelo en un archivo AVDATA y luego vincular ese archivo a la entrada del filtro de correspondencia en el programa principal:

Creación del modelo:	Programa principal:

Cuando este programa está listo, se puede ejecutar la tarea «CreateModel» como un programa en cualquier momento que desee recrear el modelo. El enlace al fichero de datos en la entrada del filtro de correspondencia no necesita entonces ninguna modificación, ya que se trata sólo de un enlace y lo que se está modificando es únicamente el fichero en el disco.

Esquema 2: Creación dinámica del modelo

Para el caso 3, cuando el modelo tiene que ser creado dinámicamente, tanto el filtro de creación del modelo como el de correspondencia tienen que estar en la misma tarea. El primero, sin embargo, debe ser ejecutado condicionalmente, cuando un respectivo evento HMI se plantea (por ejemplo, el usuario hace clic en un ImpulseButton o hace alguna acción del ratón en un VideoBox). Para representar el modelo, se debe utilizar un registro de tipo EdgeModel?, que almacenará el último modelo (otra opción es utilizar el filtro LastNotNil).A continuación se muestra un ejemplo de realización con el modelo que se crea a partir de una caja predefinida en una imagen de entrada cuando se hace clic en un botón en la HMI:

Creación del modelo

Altura de la pirámide

El parámetro inPyramidHeight determina el número de niveles de la pirámide que coinciden y debe establecerse en el número más grande para el que la plantilla es todavía reconocible en el nivel más alto de la pirámide. Este valor debe ser seleccionado a través de la experimentación interactiva utilizando la salida de diagnóstico diagPatternPyramid (Grayscale-based Matching) o diagEdgePyramid (Edge-based Matching).

En el siguiente ejemplo el valor inPyramidHeight de 4 sería demasiado alto (para ambos métodos), ya que la estructura de la plantilla se pierde por completo en este nivel de la pirámide. También el valor de 3 parece un poco excesivo (especialmente en el caso de Edge-based Matching) mientras que el valor de 2 sería definitivamente una opción segura.

	Nivel 0	Nivel 1	Nivel 2	Nivel 3	Nivel 4
Concordancia basada en escala de grises (diagPatternPyramid):
Concordancia basada en los bordes (diagEdgePyramid):

Rango de ángulos

Los parámetros inMinAngle, inMaxAngle determinan el rango de orientaciones de las plantillas que se considerarán en el proceso de emparejamiento. Por ejemplo (los valores entre paréntesis representan los pares de valores inMinAngle, inMaxAngle):

(0,0, 360,0): se consideran todas las rotaciones (valor por defecto)
(-15,0, 15,0): se permite que las ocurrencias de la plantilla se desvíen de la orientación de la plantilla de referencia como máximo 15,0 grados (en cada dirección)
(0,0, 0.0): se espera que las ocurrencias de la plantilla conserven la orientación de la plantilla de referencia

Una amplia gama de orientaciones posibles introduce una cantidad significativa de sobrecarga (tanto en el uso de la memoria como en el tiempo de computación), por lo que es aconsejable limitar la gama siempre que sea posible.

Configuración de la detección de bordes (sólo coincidencia basada en bordes)

Los parámetros inEdgeMagnitudeThreshold, inEdgeHysteresis del filtro CreateEdgeModel determinan la configuración del umbral de histéresis utilizado para detectar los bordes en la imagen plantilla. Cuanto menor sea el valor de inEdgeMagnitudeThreshold, más bordes se detectarán en la imagen plantilla. Estos parámetros deben ajustarse de manera que se detecten todos los bordes significativos de la plantilla y que la cantidad de bordes redundantes (ruido) en el resultado sea lo más limitada posible. De forma similar a la altura de la pirámide, los umbrales de detección de bordes deben seleccionarse a través de la experimentación interactiva utilizando la salida de diagnóstico diagEdgePyramid – esta vez tenemos que mirar sólo la imagen en el nivel más bajo.


(15.0, 30.0) – cantidad excesiva de ruido	(40.0, 60.0) – OK	(60.0, 70.0) – bordes significativos perdidos

El filtro CreateEdgeModel no permitirá crear un modelo en el que no se hayan detectado bordes en la parte superior de la pirámide (lo que significa que no sólo se han perdido algunos bordes significativos, sino todos), produciendo un error en tal caso. Cuando esto sucede, la altura de la pirámide, o los umbrales de los bordes, o ambos, deben ser reducidos.

Matching

El parámetro inMinScore determina cuán permisivo será el algoritmo en la verificación de los candidatos a coincidir – cuanto más alto sea el valor, menos resultados serán devueltos. Este parámetro debe ajustarse mediante experimentación interactiva a un valor lo suficientemente bajo como para asegurar que se devuelvan todas las coincidencias correctas, pero no mucho más bajo, ya que un valor demasiado bajo ralentiza el algoritmo y puede hacer que aparezcan falsas coincidencias en los resultados.

Consejos y mejores prácticas

¿Cómo seleccionar un método?

Para la gran mayoría de las aplicaciones, el método de coincidencia basado en bordes será más robusto y más eficiente que la coincidencia basada en la escala de grises. Este último debe ser considerado sólo si la plantilla que se está considerando tiene áreas de transición de color suave que no están definidos por los bordes discernibles, pero todavía debe ser emparejado.

Anterior: Ajuste de la forma

Siguiente: Sistemas de coordenadas locales