Avgift på olje til framdrift av motorvogn – autodieselavgift (post 77)

Os keypoints (também referidos como pontos de interesse) são pontos numa imagem ou nuvem de pontos que são estáveis, distintos, e podem ser identificados através de um critério de deteção bem definido [83]. Não há uma definição rigorosa para o que constitui um bom método de deteção de pontos de interesse, no entanto este necessita de possuir as seguintes características:

1. Dispersão entre pontos: apenas um pequeno subconjunto de pontos na cena são pontos de interesse;

2. Distinção entre pontos: a área em redor de cada ponto de interesse deve ter uma forma ou aparência única;

3. Repetibilidade: se um ponto foi determinado como sendo um ponto de interesse de uma nuvem de pontos, esse ponto de interesse também deve ser encontrado no local correspondente numa nuvem de pontos semelhante.

Os métodos de deteção de pontos de interesse são vantajosos porque permitem reduzir o custo computacional associados à procura dos descritores de características (apenas operam

do erro de correspondência entre pontos (evita a ambiguidade de correspondências em pontos que não sejam de interesse) [109].

Nesta secção dois algoritmos de deteção de pontos de interesse são descritos: SIFT (Scale

Invariant Feature Transform) Keypoints e Harris Keypoints. Na documentação da biblioteca PCL é referido que ambos os métodos são adaptados de algoritmos de visão por computador

que operam sobre imagens 2D. No entanto, o funcionamento destes métodos em nuvens de pontos 3D não se encontra devidamente documentada na biblioteca PCL.

3.6.1 SIFT Keypoints

O método SIFT (Scale Invariant Feature Transform) proposto por David G. Lowe [110] é um algoritmo desenvolvido para sistemas 2D de visão por computador. Os descritores de características (features) detetados são altamente distintos e estáveis, com a vantagem de serem invariantes à escala, à rotação da imagem e à iluminação global. Existem muitos projetos de investigação que pretendem transferir o conceito para o espaço tridimensional, tais como os trabalhos [111], [112]. Na biblioteca PCL, este algoritmo é utilizado como módulo de deteção de pontos de interesse (keypoints) [83]. Esta implementação adapta o algoritmo original a partir de imagens para nuvem de pontos. Como mencionado anteriormente, por falta de documentação referente a este algoritmo no sistema 3D por parte da biblioteca PCL, o método

SITF será descrito resumidamente sob o ponto de vista de uma imagem 2D.

Segundo David G. Lowe [110], o algoritmo SIFT pode ser dividido em 4 etapas principais:

 Deteção de extremos no espaço de escala;

 Localização dos pontos de interesse;

 Definição da orientação dos pontos de interesse;

 Descrição dos pontos de interesse.

As duas primeiras etapas descrevem a parte do detetor e as duas seguintes correspondem a formação do descritor. No âmbito da deteção dos pontos de interesse, as duas primeiras etapas são fundamentais para compreender a implementação deste algoritmo na PCL.

A primeira etapa da técnica SIFT consiste em identificar os pontos que são invariantes a mudanças de escala e a diferentes posições de visualização do mesmo objeto. Tal objetivo é alcançado através da procura de características estáveis em diferentes escalas, recorrendo a uma

função de espaço de escala (função Gaussiana). Uma imagem 𝐼 (𝑥, 𝑦) passa a ser definida por 𝐿 (𝑥, 𝑦, 𝜎) no espaço de escala. Esta função é obtida pela convolução de uma função Gaussiana, 𝐺(𝑥, 𝑦, 𝜎) com a imagem 𝐼 (𝑥, 𝑦) (equação 3.2) [110], [113].

𝐿 (𝑥, 𝑦, 𝜎) = 𝐺 (𝑥, 𝑦, 𝜎) ∗ 𝐼 (𝑥, 𝑦) em que,

𝐺(𝑥, 𝑦, 𝜎) = 1 2𝜋𝜎𝑒−(𝑥

2_+𝑦2_/2𝜎2₎

A eficiência da deteção dos pontos de interesse é aumentada com a utilização de uma função DoG (Difference of Gaussian) formada pela diferença de imagens filtradas em escalas próximas, separadas por uma constante de escala k. A função DoG é definida por:

𝐷𝑜𝐺 (𝑥, 𝑦, 𝜎) = (𝐺(𝑥, 𝑦, 𝑘𝜎) − 𝐺(𝑥, 𝑦, 𝜎)) ∗ 𝐼(𝑥, 𝑦) = 𝐿(𝑥, 𝑦, 𝑘𝜎) − 𝐿(𝑥, 𝑦, 𝜎)

Esta função DoG tem como objetivo suavizar as imagens, por forma a obter imagens onde os detalhes indesejados e ruído são eliminados, reforçando as características desejáveis. Com a variação do valor 𝜎 é possível encontrar tais características em diferentes escalas. O próximo passo envolve a deteção de extremos em cada intervalo de cada oitava. Um extremo é definido como qualquer valor de DoG maior do que todos os seus vizinhos no espaço de escala.

Para detetar os valores de máximo ou mínimo locais da função DoG, a intensidade de cada ponto é comparada com as intensidades dos seus 8 vizinhos na sua escala e com 9 pontos vizinhos da escala superior e inferior (Figura 37) [110], [113].

(3.3) (3.2)

Se este valor é mínimo ou máximo de todos os pontos testados, então este ponto pode ser considerado um extremo, ou seja um candidato a ponto de interesse. A próxima etapa consiste na identificação da localização exata destes pontos detetados como extremos. A partir de uma expansão de Taylor da função DoG aplicada à imagem, 𝐷𝑜𝐺 (𝑥, 𝑦, 𝜎), deslocada de modo a que a origem desta expansão esteja localizada no ponto de amostragem, é possível determinar uma localização interpolada desse extremo (equação 3.6) [110], [113].

𝐷(𝑥̅) = 𝐷 +𝜕𝐷𝑇 𝜕𝑥̅ 𝑥̅ + 1 2𝑥̅𝑇 𝜕 𝐷2 𝜕𝑥2𝑥̅ + ⋯ em que 𝑥̅ = (x, y, σ)𝑇

A localização em sub-píxeis do ponto de interesse é dada pelo extremo da função apresentada na equação 3.5. Esta localização, 𝑥̂ , é determinada ao se calcular a derivada de 𝐷(𝑥̅), em relação a 𝑥 , e igualando o resultado a zero. Portanto, a posição do extremo é dada por:

𝑥̂ = −𝜕 𝐷2 𝑇−1 𝜕𝑥̅2

𝜕 𝐷2

𝜕𝑥̅

O valor da função no extremo, 𝐷(𝑥̅), é útil para a rejeição de pontos com baixo contraste (instáveis), que seriam sensíveis ao ruído. Segundo David G. Lowe é aconselhável rejeitar os valores de |𝐷(𝑥̅)| inferiores a um determinado limiar. Além deste procedimento para eliminar os pontos instáveis, a função DoG possui uma forte resposta ao longo das arestas, isto é, os pontos em arestas poderiam ser escolhidos como pontos de interesse, o que é indesejável. Para solucionar este problema, a deteção e eliminação destes pontos pode ser feita recorrendo a uma matriz Hessiana 2x2 [110], [113].

3.6.2 Harris Keypoints

O método proposto por Chris Harris e Mike Stephens [114], o Harris Keypoints, é um algoritmo desenvolvido para detetar cantos e extremidades em sistemas 2D de visão por computador. Este método é caracterizado pela elevada mudança de intensidade nas direções horizontal e vertical. Esta característica pode ser utilizada na análise da forma e de movimento, diretamente detetadas a partir de imagens em tons de cinza (grayscale) [115]. Para o caso em

(3.5)

3D, a implementação na biblioteca PCL substitui os gradientes da matriz de covariância pelas

normais da superfície. Assim como no método anterior, este algoritmo é utilizado na biblioteca

PCL como módulo de deteção de pontos de interesse (keypoints) [83]. Como a documentação

na biblioteca PCL acerca deste algoritmo de deteção é reduzida, o método Harris será descrito resumidamente sob o ponto de vista de uma imagem 2D.

Harris e Stephens, propuseram um método de deteção de pontos de interesse para imagens

que se tornou muito conhecido devido à sua forte invariância à rotação, escala, variação de iluminação e ruído presente na imagem. Este método é baseado numa função local de auto- correlação de um sinal, que mede as alterações locais do sinal devido a pequenos deslocamentos de uma janela em diferentes direções [116].

A auto-correlação local é definida como:

𝑒 (𝑥, 𝑦) = ∑ 𝑊(𝑥𝑖, 𝑦𝑖 𝑥𝑖, 𝑦𝑖

)[𝐼(𝑥𝑖 + ∆𝑥, 𝑦𝑖 + ∆𝑦) − 𝐼(𝑥𝑖, 𝑦𝑖)] 2

em que I representa a função da imagem e (𝑥_𝑖, 𝑦_𝑖) são os pontos da função Gaussiana 𝑊, centrada no ponto (𝑥, 𝑦), que define a área da vizinhança em análise.

Através da utilização de uma expansão de Taylor truncada para os primeiros termos da ordem para aproximar a imagem deslocada, é obtido o seguinte:

𝑒 (𝑥, 𝑦) = 𝑆 [ ∑ 𝑊. 𝐼𝑥2 𝑥_𝑖, 𝑦_𝑖 ∑𝑥_𝑖, 𝑦_𝑖𝑊. 𝐼𝑥. 𝐼𝑦 ∑ 𝑊. 𝐼_𝑥. 𝐼_𝑦 𝑥𝑖, 𝑦𝑖 ∑ 𝑊. 𝐼_𝑦2 𝑥𝑖, 𝑦𝑖 ] 𝑆𝑇 = 𝑆. 𝐸(𝑥, 𝑦). 𝑆𝑇

onde 𝑆 = [∆𝑥, ∆𝑦] é o vetor de deslocamento, 𝐼_𝑥 e 𝐼_𝑦 denotam as derivadas parciais de x e y, respetivamente, e juntamente com 𝑊 são avaliadas em (𝑥_𝑖, 𝑦_𝑖) pontos.

Harris e Stephens propuseram analisar os valores próprios da matriz E, que contem

informação local suficiente relacionado com a estrutura da vizinhança (pontos de interesse). (3.7)

Além disso, para evitar um cálculo dispendioso de valores próprios, atribuíram a cada píxel da imagem o seguinte valor:

ℎ(𝑥, 𝑦) = det(𝐸) − 𝑘(𝑡𝑟(𝐸)) 2

em que k é uma constante, det e tr são o determinante e o trace (função que soma os elementos diagonais de uma matriz n x n) da matriz E, respetivamente.

Este algoritmo tem sido utilizado em muitas aplicações no processamento de imagens e em sistemas de visão por computador devido a sua simplicidade e eficácia [116].