Rendimiento de OpenCV en la plantilla que coincide con

Question

Estoy intentando hacer una coincidencia de plantillas básicamente en Java. Utilicé un algoritmo sencillo para encontrar el partido. Aquí está el código:

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

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

       pixel p_SearchIMG = S[x+i][y+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 VALUE_MAX 
     position.bestRow = x; 
     position.bestCol = y; 
     position.bestSAD = SAD; 
    } 
} 

Pero este es un enfoque muy lento. Probé 2 imágenes (768 × 1280) y subimagen (384 x 640). Esto dura por eras. ¿OpenCV realiza la coincidencia de plantillas mucho más rápido o no con la función preparada cvMatchTemplate()?

Answer 1

Encontrará openCV cvMatchTemplate() es mucho más rápido que el método que ha implementado. Lo que ha creado es un método de coincidencia de plantilla estadística. Es el más común y el más fácil de implementar; sin embargo, es extremadamente lento en imágenes grandes. Echemos un vistazo a las matemáticas básicas que tiene una imagen que es 768x1280 que recorre cada uno de estos píxeles menos el borde, ya que esta es su plantilla, por lo que (768 - 384) x (1280 - 640) 384 x 640 = 245 ' 760 operaciones en las que recorre cada píxel de la plantilla (otras 245'760 operaciones), por lo tanto, antes de agregar las matemáticas en el ciclo que ya tiene (245'760 x 245'760) 60'397'977'600 operaciones. Más de 60 mil millones de operaciones solo para recorrer su imagen. Es más sorprendente cómo las máquinas rápidas pueden hacer esto.

Recuerde, sin embargo, es 245'760 x (245'760 x operaciones matemáticas) por lo que hay muchas más operaciones.

Ahora cvMatchTemplate() realmente usa la operación de concordancia de Fourier Analysis Template. Esto funciona aplicando una Transformada de Fourier rápida (FFT) en la imagen en la que las señales que componen los píxeles cambian en intensidad se segmentan en cada una de las formas de onda correspondientes. El método es difícil de explicar bien, pero la imagen se transforma en una representación de señal de números complejos. Si desea comprender más, busque en gafas el fast fourier transform. Ahora que se realiza la misma operación en la plantilla, las señales que forman la plantilla se utilizan para filtrar cualquier otra señal de su imagen.

En simple, suprime todas las funciones de la imagen que no tienen las mismas características que su plantilla. La imagen se vuelve a convertir utilizando una transformada de Fourier rápida inversa para producir imágenes donde los valores altos significan una coincidencia y los valores bajos significan lo contrario. Esta imagen a menudo se normaliza, por lo que 1 representa una coincidencia y 0 o más significa que el objeto no está cerca.

Tenga en cuenta que si su objeto no está en la imagen y está normalizado, se producirá una detección falsa ya que el valor más alto calculado se tratará como una coincidencia. Podría continuar durante años sobre cómo funciona el método y sus beneficios o problemas que pueden ocurrir pero ...

La razón por la cual este método es tan rápido es: 1) opencv es código C++ altamente optimizado. 2) La función fft es fácil de manejar para su procesador ya que la mayoría tiene la capacidad de realizar esta operación en hardware. Las tarjetas gráficas GPU están diseñadas para realizar millones de operaciones fft cada segundo, ya que estos cálculos son tan importantes en gráficos de videojuegos o codificación de video de alto rendimiento. 3) La cantidad de operaciones requeridas es mucho menor.

En verano, el método de concordancia de plantilla estadística es lento y toma años, mientras que opencv FFT o cvMatchTemplate() es rápido y está altamente optimizado.

La coincidencia estadística de plantillas no producirá errores si un objeto no está allí, mientras que Opencv FFT puede hacerlo a menos que se tenga cuidado en su aplicación.

Espero que esto le proporcione un entendimiento básico y responda a su pregunta.

Saludos

Chris

[EDIT]

Para responder a sus preguntas más:

Hola,

cvMatchTemplate puede trabajar con CCOEFF_NORMED y CCORR_NORMED y SQDIFF_NORMED incluyendo la no versión normalizada de estos. Here muestra el tipo de resultados que puede esperar y le da su código para jugar.

http://dasl.mem.drexel.edu/~noahKuntz/openCVTut6.html#Step%202

Los tres métodos son bien citados y muchos documentos están disponibles a través Google scholar. He proporcionado algunos documentos a continuación. Cada uno simplemente usa una ecuación diferente para encontrar la correlación entre las señales FFT que forman la plantilla y las señales FFT que están presentes dentro de la imagen. El Coeficiente de Correlación tiende a producir mejores resultados en mi experiencia y es más fácil encontrar referencias. La suma de la diferencia cuadrada es otro método que se puede usar con resultados comparables. Espero que algunos de estos ayuden:

Fast normalized cross correlation for defect detection Du-Ming Tsai; Chien-Ta Lin; Patrón Recognition Letters Volumen 24, Número 15, noviembre de 2003, páginas 2625-2631

Template Matching using Fast Normalised Cross Correlation Kai Briechle; Uwe D. Hanebeck;

Relative performance of two-dimensional speckle-tracking techniques: normalized correlation, non-normalized correlation and sum-absolute-difference Friemel, B.H .; Bohs, L.N .; Trahey, G.E .; Ultrasonidos Simposio, 1995. Proceedings., 1995 IEEE

A Class of Algorithms for Fast Digital Image Registration Barnea, Daniel I .; Silverman, Harvey F .;
Ordenadores, IEEE Transactions on de febrero 1972

A menudo se ve favorecida a utilizar la versión normalizada de estos métodos como todo lo que es igual a un 1 es un partido sin embargo, si no está presente objeto se puede obtener falsos positivos. El método funciona rápido simplemente debido a la forma en que se instiga en el lenguaje de la computadora. Las operaciones involucradas son ideales para la arquitectura del procesador, lo que significa que puede completar cada operación con unos pocos ciclos de reloj en lugar de cambiar la memoria y la información a lo largo de varios ciclos de reloj. Los procesadores han estado resolviendo problemas de FFT durante muchos años, y como dije, hay hardware incorporado para hacerlo. El hardware basado siempre es más rápido que el software y el método estadístico de coincidencia de plantillas se basa en software básico.Buena lectura para el hardware se puede encontrar aquí:

Digital signal processor Aunque una página Wiki las referencias son Vale la pena verlo una eficacia este es el hardware que realiza cálculos de FFT

A new Approach to Pipeline FFT Processor Shousheng Él; Mats Torkelson; Una de mis favoritas, ya que muestra lo que está sucediendo dentro del procesador

An Efficient Locally Pipelined FFT Processor Liang Yang; Kewei Zhang; Hongxia Liu; Jin Huang; Shitan Huang;

Estos documentos muestran realmente cuán compleja es la FFT cuando se implementa, sin embargo, el revestimiento del proceso es lo que permite que la operación se realice en unos pocos ciclos de reloj. Esta es la razón por la cual los sistemas basados ​​en visión en tiempo real utilizan FPGA (específicamente procesadores de diseño que usted puede diseñar para implementar una tarea determinada) ya que pueden diseñarse de forma extremadamente paralela en la arquitectura y el revestimiento de tuberías es más fácil de implementar.

Aunque debo mencionar que para la FFT de una imagen en realidad está usando FFT2 que es la FFT de la llanura horizontal y la FFT de la llanura vertical simplemente para que no haya confusión cuando encuentre referencia a ella. No puedo decir que tengo un conocimiento experto sobre cómo se implementaron las ecuaciones y cómo se implementó la FFT. He intentado encontrar buenas guías; sin embargo, encontrar una buena guía es muy difícil; todavía no he encontrado una (ninguna que pueda comprender). menos). Algún día puedo entenderlos, pero sé que entiendo muy bien cómo funcionan y qué tipo de resultados se pueden esperar.

Aparte de esto, no puedo ayudarte más si quieres implementar tu propia versión o entender cómo funciona, es hora de ir a la biblioteca, pero te advierto que el código opencv está tan bien optimizado que tendrás problemas para aumentar su rendimiento, sin embargo, quién sabe usted puede encontrar una manera de obtener mejores resultados todo lo mejor y buena suerte

Chris