Nesta seção apresenta-se um método desenvolvido neste trabalho para o rastreamento baseado na similaridade de regiões. As referências [13] e [31] foram as principais fontes inspiradoras para o método. Para medida da correspondência entre janelas utiliza-se a função de custo SSD, somatória das diferenças quadráticas. O rastreamento consiste na minimização desta função entre imagens subsequentes.
3.3.1 A função Somatória das Diferenças Quadráticas (Sum of Square Differences -
SSD
A função de custo SSD foi empregada (Eq. 3.2), como medida de similaridade entre regiões de imagens, devido à sua adequação às metodologias de rastreamento visual. Uma característica diz respeito à sua integração à estrutura de movimento (seguindo as hipotéses apresentadas na seção 3.2) voltadas à estabilidade e estrutura computacional incremental. Com respeito à estabilidade, a função SSD possibilita, devido ao termo quadrática, que pe- quenos valores de similaridade entre regiões passem a ter menor influência no processo de correspondência, diminuindo a quantidade de regiões ambígüas entre as regiões da imagem. Esta característica não é encontrada nas funções com estruturas a partir das SADs. Com re- lação à idéia de estrutura computacional incremental, pode se notar que ao se adquirir novas informações com respeito a área de aplicação a função SSD, estas são atualizadas de forma a manter as reais características do movimento, permitindo assim processos que abrangem todo o campo visível da imagem.
A equação 3.2 constituirá neste trabalho a função custo de similaridade, e deverá ser mi- nimizada, logo o procedimento consiste em encontrar na imagem subsequente uma região que seja semelhante àquela da imagem anterior. Aplicando essa metodologia, pode-se alcan- çar a solução para o rastreamento visual. Entretanto alguns detalhes devem ser considerados para realização do rastreamento visual, seguindo as características apresentadas na seção 3.2. Maiores detalhes da utilização da função SSD para o rastreamento serão apresentados na seção 3.4.
3.3.2 Variações da função SSD - Domínio da Freqüência
Algoritmos de rastreamento que empregam a similaridade de regiões (principalmente o algoritmo Window-matching), utilizam funções de custo - neste caso o interesse é na função SSD, podendo facilmente ser estendido às demais funções de custo apresentadas na tabela 3.1 - para correlacionar possíveis regiões que se assemelham à determinada região da ima- gem anterior (padrão da região de interesse), pode-se realizar uma abordagem definindo, independente da função de custo, que todo o processo nada mais é que um processo de
correlação bidimensional.
Algoritmos de rastreamento baseados na similaridade de regiões utilizam funções de custo, como aquelas da Tabela 3.1, onde a formulação da função de custo se dá no domí- nio espacial da imagem. Independentemente da função de custo utilizada, a procura pela similaridade de regiões entre imagens sequenciais, consiste na solução de um problema de correlação bidimensional.
O problema da correlação bidimensional pode ser resolvido também no domínio da frequência transformando a função de custo pela aplicação da Transformada de Fourier Bidi- mensional [18]. Como um dos objetivos deste trabalho é o desenvolvimento de um algoritmo de rastreamento, decidiu-se investigar a alternativa de trabalhar no domínio da frequência. Para que seja possível o desenvolvimento da estrutura no domínio da freqüência, foi empre- gada abordagem apresentada em [62].
3.3.2.1 Definição do Problema
Partindo do princípio que algoritmos de rastreamento que empregam a similaridade de regiões (baseado na metodologia Window-matching), na verdade utilizam uma função de custo - neste caso o interesse é na função SSD, podendo facilmente ser estendido às demais funções de custo apresentadas na tabela 3.1 - para correlacionar possíveis regiões que se assemelham à determinada região da imagem anterior (padrão da região de interesse), pode- se realizar uma abordagem definindo, independente da função de custo, que todo o processo nada mais é que um processo de correlação bidimensional. Partindo desta abordagem, pode- se reescrever a equação 3.2 como:
R(x, y) = N 2 X i,j=−N2 ρ (x, y) (3.3)
Em que ρ é uma função bidimensional que representa a estrutura da função de custo do SSD, têm-se: R(x, y) = N 2 X i,j=−N 2 ρ (dx,y(i, j)) (3.4)
onde dx,y(i, j) = (I1(x + i, y + j) − I2(x + i + dx, y + j + dy))2é uma função que uti-
liza valores reais dos pixels da imagem. Sabe-se que imagens digitais, independente do es- paço de cores em que se trabalhe, faz por convenção o uso de pixels com valores no intervalo de [0, 255], representando na forma digital valores quantizados de 8(oito) bits. Desta forma, com a finalidade de simplificar problemas relativos ao condicionamento numérico, os valores para a função da equação 3.4 são normalizados no intervalos entre [0, 1].
De acordo com [63] a correlação bidimensional pode ser expressa pela equação 3.5. R(x, y) = N 2 X i,j=−N2 (f (x, y) − g (x + dx, y + dy))2 (3.5)
Observa-se, que a equação 3.5 representa uma convolução com estrutura quadrática. Pas- sando para a notação de convolução, têm-se:
(f ∗ g)(i, j) = N 2 X i,j=−N 2 f (x, y) g∗(x + d x, y + dy) (3.6)
onde∗ representa a função complexa conjugada. Aplicando na equação 3.6 a Transfor-
mada Discreta de Fourier - DFT - bidimensional, pode-se obter a relação entre a estrutura da função SSD com a correlação bidmensional no domínio da freqüência (Eq. 3.7).
R(x, y) = F (x, y)G∗(x, y) (3.7)
em que F (x, y) representa a região de intesse da imagem no instante k aplicado a trans-
formada de Fourier Discreta bidimensional e G∗(x, y) o complexo conjugado da região de
interesse da imagem em k + 1, também no domínio discreto da transformada de Fourier bidimensional.
Neste trabalho implementou-se a procura pela similaridade de regiões no domínio da frequência e observou-se o seguinte:
• Elevado custo computacional - antes da procura pela similaridade há necessidade de apli- car a Transformada Discreta de Fourier, isto representa uma carga computacional adicio- nal. Se comparado com a função de custo no domínio espacial, o número de operações em ponto flutuante, para uma imagem de dimensões m × n pixels, passa para 2 × m × n. • Rotação da Imagem - Uma propriedade importante da tranformada discreta de Fourier, quando aplicada à imagens, é a imunidade à rotação da imagem [18]. Esta característica implica no aumento de regiões na imagem, que no domínio da freqüência, implicam no aumento do grau de ambigüidade entre regiões da imagem, dificultando o processo de minimização da função de custo;
Em vista dessas observações, optou-se pela utilização da função de custo SSD no domí- nio espacial.
3.4 DESENVOLVIMENTO DE UM ALGORITMO DE RASTREAMENTO BASE-