08. Sistemas Eletrônicos Inteligentes - emplate matching simplificado

Prévia do material em texto

Explicação simplificada de template matching 
(casamento de máscara, ou casamento de modelo) 
 
 
I R 
T R(x,y) 
 
Template matching percorre a imagem I comparando template T com cada posição (x,y) de I. 
O resultado da comparação é armazenado em R(x,y). A saída R é menor que a entrada I. 
 
 
Template matching é uma técnica usada para achar as instâncias de uma máscara T dentro de 
uma imagem I. Nesta explicação simplificada, vamos aprender como usar a função match-
Template do OpenCV. A função matchTemplate é altamente otimizada para velocidade. Uti-
liza FFT (Fast Fourier Transform) e imagem integral para acelerar o processamento (na apos-
tila tmatch.doc há explicação de como isto é possível). Copiando do manual do OpenCV: 
 
matchTemplate - Compares a template against overlapped image regions. 
 
void matchTemplate(InputArray image, InputArray templ, OutputArray result, int method) 
 
Parameters 
image – Image where the search is running. It must be 8-bit or 32-bit floating-point. 
templ – Searched template. It must be not greater than the source image and have the same 
data type. 
result – Map of comparison results. It must be single-channel 32-bit floating-point. If ima-
ge is W × H and templ is w × h , then result is (W − w + 1) × (H − h + 1) . 
method – Parameter specifying the comparison method. 
 
The function slides through image, compares the overlapped patches of size w × h against 
templ using the specified method and stores the comparison results in result. 
 
OpenCV fornece seis métodos diferentes de comparação. Desses, destaco os três que julgo 
serem mais úteis: 
 
1) method=CV_TM_SQDIFF (squared difference) 
 
 


yx
yyxxIyxTyxR
,
2
),(),(),(
 
Calcula a soma das diferenças quadráticas. Não é invariante a brilho/contraste. Se quiser limi-
tar a saída de R ao mesmo intervalo de intensidade de I, calcule como pós-processamento: 
 
hw
yxR

),( 
 
2) method=CV_TM_CCORR (cross correlation) 
 
 


yx
yyxxIyxTyxR
,
),(),(),(
 
Calcula correlação cruzada. Antes de chamar este método, deve pré-processar o template T 
para que tenha média zero (subtrair a média de T de todos os pixels de T, ou seja, fazer “dcRe-
ject”). Além disso, para limitar o intervalo de intensidades de R ao mesmo intervalo de I, de-
vemos fazer com que a somatória absoluta dos pixels do template T seja dois (“somaAbs-
Dois”). Sendo T matriz de ponto flutuante, na biblioteca Cekeikon: 
 T=somaAbsDois(dcReject(T)) 
efetua esse pré-processamento. É invariante à mudança de brilho, mas não é invariante à mu-
dança de contraste. 
 
3) method=CV_TM_CCOEFF_NORMED (normalized correlation coefficient) 
 
 
   

  
 



x yx y
x y
yyxxIyxT
yyxxIyxT
yxR
22
)),(
~
)),(
~
),(
~
),(
~
),( 
onde 
T
~ é template T pré-processado para que tenha média zero. Esta operação é invariante a 
brilho e contraste. 
 
Nota: Neste caso, não precisa pré-processar nada, pois a função matchTemplate se encarrega-
rá de tudo. 
Nota: No manual de OpenCV, cita que 
I
~ também foi pré-processado para ter média zero. O 
resultado dá exatamente igual usando I ou 
I
~ (desde que pré-processe template T para ter mé-
dia zero). 
 
 
 
Invariância à mudança de brilho e contraste: 
Definimos que duas imagens x e y são equivalentes sob variação de brilho e contraste se exis-
tem fatores de correção de contraste 0 (ou >0 se não admite imagens negativas) e de bri-
lho  tais que 
1xy 
, onde 1 é a matriz de 1s. 
 
 
 
Uma outra forma de descrever os três métodos, para facilitar a compreensão, é usar a notação 
de vetor. Sejam dados vetores x e y (x é o conteúdo dentro da janela da imagem I. y é o conte-
údo da imagem T escrito na forma de vetor). Vamos denotar esses vetores após correção de 
média (dcReject) de 
x~
 e 
y~
. Isto é, 
xxx ~
, onde 
x
 é a média de x e o mesmo vale para y. 
 
1) method=CV_TM_SQDIFF (squared difference) 
 
  22 yxyxr
i
ii 
 
Este método calcula o comprimento do vetor-diferença (ao quadrado). 
 
2) method=CV_TM_CCORR (cross correlation) 
 
yxyxr
i
ii 
 
onde  indica o produto escalar. Fazendo “dcReject” como pré-processamento, temos: 
 
yxyxr ~~~ 
 
Este método calcula o produto escalar dos dois vetores. 
 
3) method=CV_TM_CCOEFF_NORMED (normalized correlation coefficient) 
 
)cos(~
~
~~
~~





yx
yx
yx
yx
r
 
onde  é o ângulo formado por dois vetores. Este método calcula o cosseno do ângulo forma-
do pelos dois vetores. 
 
Estes métodos são populares, pois é possível acelerar (muito) o processamento usando FFT e 
imagem integral. 
 
1) method=CV_TM_SQDIFF (squared difference) 
 
//sqdiff.cpp - grad2017 
#include <cekeikon.h> 
int main(int argc, char** argv) { 
 Mat_<FLT> image; le(image,"a03.jpg"); 
 Mat_<FLT> templ; le(templ,"q00.jpg"); 
 Mat_<FLT> result; 
 matchTemplate(image,templ,result,CV_TM_SQDIFF); 
 result=raiz(result/templ.total()); 
 Mat_<GRY> t=binariza(result,0.08); 
 imp(result,"sqdiff-r.pgm"); 
 imp(t,"sqdiff-t.pgm"); 
} 
 
 
a03.jpg 
 
q00.jpg 
 
sqdiff-r.pgm 
 
sqdiff-t.pgm 
Template matching usando quadrado da diferença 
 
Problema: Não é invariante a mudança de brilho e contraste. Se ajustar um pouco o bri-
lho/contraste, não acha mais as instâncias. 
O que acontece se escrever um template matching, sem usar a função de OpenCV? 
 
//sqdiff2.cpp - grad2017 
#include <cekeikon.h> 
 
void nossoMatchTemplate(Mat_<FLT> image, Mat_<FLT> templ, Mat_<FLT>& result) { 
 result.create(image.rows-templ.rows+1,image.cols-templ.cols+1); 
 for (int l=0; l<result.rows; l++) 
 for (int c=0; c<result.cols; c++) { 
 float somaquad=0.0; 
 for (int l2=0; l2<templ.rows; l2++) 
 for (int c2=0; c2<templ.cols; c2++) 
 somaquad = somaquad + elev2(image(l+l2,c+c2) - templ(l2,c2)); 
 result(l,c)=somaquad; 
 } 
} 
 
int main() { 
 Mat_<FLT> image; le(image,"a03.jpg"); 
 Mat_<FLT> templ; le(templ,"q00.jpg"); 
 Mat_<FLT> result; 
 for (unsigned i=0; i<10; i++) 
 nossoMatchTemplate(image,templ,result); 
 //result no intervalo de 0 a desconhecido 
 result=raiz(result/templ.total()); //result no intervalo de 0 a 1 
 Mat_<GRY> t=binariza(result,0.08); 
 imp(result,"sqdiff2-r.pgm"); 
 imp(t,"sqdiff2-t.pgm"); 
} 
 
Esta função é aproximadamente 100 vezes mais lento do que a da OpenCV! 
 
Roda em 34s, enquanto que a versão que usa a função do OpenCV roda em 0,34s. Nos dois 
casos, a função foi chamada 10 vezes para poder medir o tempo com mais precisão. 
2) method=CV_TM_CCORR (cross correlation) 
 
Este método é invariante ao brilho mas não ao contraste. Este método é útil se quiser encon-
trar instâncias com alto contraste. Instâncias de alto contraste resultarão em picos mais altos. 
 
 
op00.jpg com cinco instâncias em diferentes contras-
tes. 
 
padrao.png 
 
result (imagem negativa) 
 
binarizado (imagem negativa) 
Método CV_TM_CCORR dá pico mais alto em instância com maior contraste. 
 
//ccorr.cpp - grad2017 
#include <cekeikon.h> 
int main(int argc, char** argv) { 
 Mat_<FLT> image; le(image,"op00.jpg"); 
 Mat_<FLT> templ; le(templ,"padrao.png"); 
 resize(templ,templ,Size(43,43),0,0,INTER_AREA); 
 templ=somaAbsDois(dcReject(templ)); 
 Mat_<FLT> result; 
 matchTemplate(image,templ,result,CV_TM_CCORR); 
 Mat_<GRY> binarizado=binariza(result,0.70); 
 imp(result,"result.pgm"); 
 imp(binarizado,"binarizado.pgm");} 
 
Como não ser invariante ao contraste pode atrapalhar a busca? 
 
 
figurinhas.jpg 
 
dumbo.jpg 
 
 
 
 
A saída não indica a localização de Dumbo, pois Dumbo tem baixo contraste enquanto que 
Pumba possui maior contraste. 
 
Pixels mais 
brilhantes 
3) method=CV_TM_CCOEFF_NORMED (normalized correlation coeffici-
ent) 
 
// dumbo2.cpp 2012. So funciona a partir de Cekeikon 2.04 
#include <cekeikon.h> 
int main() 
{ Mat_<FLT> a; le(a,"figurinhas.jpg"); 
 Mat_<FLT> q; le(q,"dumbo.jpg"); 
 Mat_<FLT> sai; 
 matchTemplate(a, q, sai, CV_TM_CCOEFF_NORMED); 
 //sai=aumentaCanvas(sai,a.rows,a.cols,(q.rows-1)/2,(q.cols-1)/2,0.0); 
 imp(sai,"dumbo2.pgm"); 
} 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Ocorrência verdadeira de Dumbo: 
Correlação não-normalizada: 50 
Correlação normalizada: 1 
 
 
 
 
 
 
 
 
 
 
 
 
 
Falsa ocorrência de Dumbo: 
Correlação não-normalizada:100 
Correlação normalizada: 0,7 
Pixels mais 
brilhantes 
dumbo padrão 
ocorrência de 
dumbo 
10 
5 
dumbo padrão 
10 
14 
falsa ocorrên-
cia de dumbo 
 
 
a.tga 
 
q.tga 
 
ncc.tga 
 
ncc.png 
 
cc.tga 
 
cc.png 
Usando coeficiente de correlação normalizada, o algoritmo achou corretamente os 4 ursos. 
Usando correlação cruzada, achou 3 ursos (um falso negativo) e detectou um urso onde não 
tinha (um falso positivo). Isto não pode ser consertado mudando o valor de threshold. 
 
 
Como obter invariância à escala: Veja a apostila rstmatch.