Comparación de plantillas - Template matching

La coincidencia de plantillas es una técnica en el procesamiento de imágenes digitales para encontrar pequeñas partes de una imagen que coincidan con una imagen de plantilla. Se puede utilizar en la fabricación como parte del control de calidad, una forma de navegar por un robot móvil o como una forma de detectar bordes en imágenes.

Los principales desafíos en la tarea de comparación de plantillas son: oclusión, detección de transformaciones no rígidas, iluminación y cambios de fondo, desorden de fondo y cambios de escala.

Enfoque basado en características

La capa oculta genera un vector que contiene información de clasificación sobre la imagen y se utiliza en el algoritmo de coincidencia de plantillas como las características de la imagen.

El enfoque basado en características se basa en la extracción de características de la imagen, es decir, formas, texturas, colores, para que coincidan con la imagen o el marco de destino. Este enfoque se consigue actualmente mediante el uso de redes neuronales y profundo aprendizaje clasificadores como VGG, AlexNet , ResNet . Las redes neuronales convolucionales profundas procesan la imagen pasándola a través de diferentes capas ocultas y en cada capa producen un vector con información de clasificación sobre la imagen. Estos vectores se extraen de la red y se utilizan como características de la imagen. La extracción de características mediante el uso de redes neuronales profundas es extremadamente eficaz y, por lo tanto, es el estándar en los algoritmos de coincidencia de plantillas de última generación.

Este método se considera más robusto y es de última generación, ya que puede hacer coincidir plantillas con transformaciones no rígidas y fuera del plano , puede coincidir con un alto desorden de fondo y cambios de iluminación.

Enfoque basado en plantillas

Para plantillas sin características sólidas, o para cuando la mayor parte de la imagen de la plantilla constituye la imagen coincidente, un enfoque basado en plantillas puede ser eficaz. Como se mencionó anteriormente, dado que la coincidencia basada en plantillas puede potencialmente requerir el muestreo de una gran cantidad de puntos, es posible reducir la cantidad de puntos de muestreo reduciendo la resolución de las imágenes de búsqueda y plantilla por el mismo factor y realizando la operación en el resultado imágenes reducidas (multiresolución o pirámide ), que proporcionan una ventana de búsqueda de puntos de datos dentro de la imagen de búsqueda para que la plantilla no tenga que buscar todos los puntos de datos viables, o una combinación de ambos.

Seguimiento de movimiento y manejo de oclusiones

En los casos en que la plantilla no proporcione una coincidencia directa, puede ser útil implementar el uso de espacios propios : plantillas que detallan el objeto coincidente en una serie de condiciones diferentes, como diferentes perspectivas, iluminaciones, contrastes de color u objetos coincidentes aceptables. "Poses". Por ejemplo, si el usuario buscaba un rostro, los espacios propios pueden consistir en imágenes (plantillas) de rostros en diferentes posiciones de la cámara, en diferentes condiciones de iluminación o con diferentes expresiones.

También es posible que la imagen coincidente quede oscurecida u ocluida por un objeto; en estos casos, no es razonable proporcionar una multitud de plantillas para cubrir cada posible oclusión. Por ejemplo, la imagen de búsqueda puede ser una carta de juego, y en algunas de las imágenes de búsqueda, la carta está oscurecida por los dedos de alguien que sostiene la carta, o por otra carta encima de ella, o cualquier objeto frente a la cámara. para esa materia. En los casos en que el objeto es maleable o posable, el movimiento también se convierte en un problema y los problemas que involucran tanto el movimiento como la oclusión se vuelven ambiguos. En estos casos, una posible solución es dividir la imagen de la plantilla en varias subimágenes y realizar una coincidencia en cada subdivisión.

Plantillas deformables en anatomía computacional

La coincidencia de plantillas es una herramienta central en anatomía computacional (CA). El modelo de plantilla deformable modela el espacio de anatomías y órbitas humanas bajo la acción grupal de difeomorfismos. La coincidencia de plantillas surge como un problema al hacer coincidir el difeomorfismo desconocido que actúa sobre la plantilla para coincidir con la imagen de destino.

Los algoritmos de coincidencia de plantillas en CA se han denominado mapeo métrico difeomórfico de grandes deformaciones (LDDMM); ahora existen algoritmos de coincidencia de plantillas LDDMM para hacer coincidir puntos de referencia, curvas, superficies y volúmenes .

Concordancia basada en plantillas explicada mediante correlación cruzada o suma de diferencias absolutas

Un método básico de coincidencia de plantillas utiliza un parche de imagen (plantilla), adaptado a una característica específica de la imagen de búsqueda, que queremos detectar. Esta técnica se puede realizar fácilmente en imágenes grises o imágenes de bordes . La salida de correlación cruzada será más alta en los lugares donde la estructura de la imagen coincide con la estructura de la máscara, donde los valores grandes de la imagen se multiplican por los valores grandes de la máscara.

Este método normalmente se implementa seleccionando primero una parte de la imagen de búsqueda para usar como plantilla: llamaremos a la imagen de búsqueda S (x, y) , donde (x, y) representan las coordenadas de cada píxel en la imagen de búsqueda. . Llamaremos a la plantilla T (x _t , y _t ) , donde (x _t , y _t ) representan las coordenadas de cada píxel en la plantilla. Luego simplemente movemos el centro (o el origen) de la plantilla T (x _t , y _t ) sobre cada punto (x, y) en la imagen de búsqueda y calculamos la suma de productos entre los coeficientes en S (x, y) y T (x _t , y _t ) en toda el área abarcada por la plantilla. Como se consideran todas las posiciones posibles de la plantilla con respecto a la imagen de búsqueda, la posición con la puntuación más alta es la mejor posición. Este método a veces se denomina "filtrado espacial lineal" y la plantilla se denomina máscara de filtro .

Otra forma de manejar los problemas de traducción en imágenes usando la coincidencia de plantillas es comparar las intensidades de los píxeles , usando la medida SAD ( Suma de diferencias absolutas ).

Un píxel en la imagen de búsqueda con coordenadas (x _s , y _s ) tiene intensidad I _s (x _s , y _s ) y un píxel en la plantilla con coordenadas (x _t , y _t ) tiene intensidad I _t (x _t , y _t ) . Por tanto, la diferencia absoluta en las intensidades de píxeles se define como Diff (x _s , y _s , x _t , y _t ) = | Yo _s (x _s , y _s ) - I _t (x _t , y _t ) | .

${\ Displaystyle SAD (x, y) = \ sum _ {i = 0} ^ {T _ {\ text {rows}}} \ sum _ {j = 0} ^ {T _ {\ text {cols}}} {{ \ text {Diferencia}} (x + i, y + j, i, j)}}$

La representación matemática de la idea de recorrer los píxeles en la imagen de búsqueda a medida que traducimos el origen de la plantilla en cada píxel y tomamos la medida SAD es la siguiente:

${\ Displaystyle \ sum _ {x = 0} ^ {S _ {\ text {filas}}} \ sum _ {y = 0} ^ {S _ {\ text {cols}}} {SAD (x, y)}}$

S _filas y S _cols denotan las filas y las columnas de la búsqueda de imágenes de y T _filas y T _cols denotan las filas y las columnas de la imagen de la plantilla, respectivamente. En este método, la puntuación SAD más baja proporciona la estimación de la mejor posición de la plantilla dentro de la imagen de búsqueda. El método es simple de implementar y comprender, pero es uno de los métodos más lentos.

Implementación

En esta implementación simple, se asume que el método descrito anteriormente se aplica en imágenes grises: por eso se usa Gray como intensidad de píxel. La posición final en esta implementación proporciona la ubicación superior izquierda donde la imagen de la plantilla coincide mejor con la imagen de búsqueda.

minSAD = VALUE_MAX;

// loop through the search image
for ( size_t x = 0; x <= S_cols - T_cols; x++ ) {
    for ( size_t y = 0; y <= S_rows - T_rows; y++ ) {
        SAD = 0.0;

        // loop through the template image
        for ( size_t j = 0; j < T_cols; j++ )
            for ( size_t i = 0; i < T_rows; i++ ) {

                pixel p_SearchIMG = S[y+i][x+j];
                pixel p_TemplateIMG = T[i][j];
		
                SAD += abs( p_SearchIMG.Grey - p_TemplateIMG.Grey );
            }

        // save the best found position 
        if ( minSAD > SAD ) { 
            minSAD = SAD;
            // give me min SAD
            position.bestRow = y;
            position.bestCol = x;
            position.bestSAD = SAD;
        }
    }
    
}

Una forma de realizar la coincidencia de plantillas en imágenes en color es descomponer los píxeles en sus componentes de color y medir la calidad de coincidencia entre la plantilla de color y la imagen de búsqueda utilizando la suma del SAD calculado para cada color por separado.

Acelerando el proceso

En el pasado, este tipo de filtrado espacial normalmente solo se usaba en soluciones de hardware dedicado debido a la complejidad computacional de la operación; sin embargo, podemos reducir esta complejidad al filtrarlo en el dominio de frecuencia de la imagen, lo que se conoce como 'filtrado en el dominio de frecuencia'. , 'esto se hace mediante el uso del teorema de convolución .

Otra forma de acelerar el proceso de emparejamiento es mediante el uso de una pirámide de imágenes. Se trata de una serie de imágenes, a diferentes escalas, que se forman filtrando y submuestreando repetidamente la imagen original para generar una secuencia de imágenes de resolución reducida. Estas imágenes de resolución más baja se pueden buscar en la plantilla (con una resolución igualmente reducida), con el fin de obtener posibles posiciones de inicio para la búsqueda a escalas más grandes. Las imágenes más grandes se pueden buscar en una pequeña ventana alrededor de la posición de inicio para encontrar la mejor ubicación de la plantilla.

Otros métodos pueden manejar problemas como traducción, escala, rotación de imágenes e incluso todas las transformaciones afines.

Mejorando la precisión del emparejamiento

Se pueden realizar mejoras en el método de emparejamiento utilizando más de una plantilla (espacios propios), estas otras plantillas pueden tener diferentes escalas y rotaciones.

También es posible mejorar la precisión del método de emparejamiento mediante la hibridación de los enfoques basados en características y basados en plantillas. Naturalmente, esto requiere que las imágenes de búsqueda y plantilla tengan características que sean lo suficientemente evidentes como para admitir la coincidencia de características.

Métodos similares

Otros métodos que son similares incluyen ' Coincidencia estéreo ', ' Registro de imagen ' y ' Transformación de características invariantes de escala '.

Ejemplos de uso

La coincidencia de plantillas tiene varias aplicaciones y se utiliza en campos como el reconocimiento facial (ver sistema de reconocimiento facial ) y el procesamiento de imágenes médicas. Se han desarrollado y utilizado sistemas en el pasado para contar el número de caras que caminan por una parte de un puente en un período de tiempo determinado. Otros sistemas incluyen la detección automatizada de nódulos calcificados dentro de las radiografías digitales de tórax. Recientemente, este método se implementó en simulación geoestadística que podría proporcionar un algoritmo rápido.

Languages

In other projects