Alinhamento de nuvens de
pontos
Problema de alinhamento
• Dadas duas nuvens de pontos P e Q, encontrar o
movimento rígido (R, t) que minimiza o erro de
ajuste
min  || q ( pi )  ( Rpi  t ) ||
2
i
onde q(pi) é o ponto em Q correspondente ao
ponto pi de P.
• Dificuldade: não se sabe, a priori, qual é o ponto
em Q que corresponde a pi
Algoritmo ICP (Iterative Closest Point)
• inicia com estimativa grosseira para R e t
• a cada iteração, q(pi) é escolhido como o
ponto em Q mais próximo de Rpi + t
• R e t são recalculados de modo a minimizar
o erro de ajuste
[Besl e McKay, 92]
Algoritmo ICP (Iterative Closest Point)
Algoritmo ICP (Iterative Closest Point)
• Também se aplica a ajuste de nuvens de
pontos a modelos (por exemplo, cilindros)
Subproblema fundamental: alinhamento
de pontos correspondentes
• Dados os pares de pontos correspondentes pi, qi (i
= 1, ..., n), determinar R e t que minimizam
min  || qi  ( Rpi  t ) ||
2
i
• Resolvido por Horn[88, 89]
Alinhamento de pontos correspondentes
min  || qi  ( Rpi  t ) ||2
i
– Obter os centróides p0 e q0
– Definir pi’= pi – p0 , qi’= qi – q0
– Definir
onde
 S xx

M   S yx

 S zx
S xy
S yy
S zy
S xz 

S yz 

S zz 
, ,
, ,
S xx   pix
qix , S xy   pix
qiy , etc
i
i
Alinhamento de pontos correspondentes
min  || qi  ( Rpi  t ) ||2
i
– Rotação: R = M(MT M) –1/2
– Translação: t = q0– Rp0
– Observação: se a transformação é escrita
na forma R(p + t), R não muda e t é
simplesmente q0– p0
Alinhamento de pontos correspondentes
– Pode ser incluído um fator de escala:
1
min  ||
qi  ( s Rpi  t ) ||2
s
i
– Rotação: R = M(MT M) –1/2
– Escala: s 
, 2
, 2
 || qi || /  || pi ||
i
i
– Translação: t = q0– sRp0
Exemplo (2D)
 20 218
 136 208




p   18 114, q   170 121
 78 114
 219 131




Exemplo (2D)
p0  (38.66, 148.66), q0  (175, 153.33)
 0.9460 - 0.3241

R  
 0.3241 0.9460
(q = 18o)
Exemplo (2D)
 134.8 212.87
 136 208




Rp  t   166.7 113.8 , q   170 121
 223.4 133.3 
 219 131




Variantes do ICP
• ICP funciona melhor quando todo ponto em
P corresponde a algum ponto em Q (não é o
caso no alinhamento de malhas obtidas por
fotografia 3D)
• Diversas estratégias para melhorar o
desempenho para alinhamento de malhas
com superposição parcial
Variantes do ICP
• Tomar pontos em ambas as malhas
• Usar outros critérios para casamento
(textura, normal)
• Atribuir pesos às correspondências
• Rejeitar outliers
• Alterar a medida de distância (pontosuperfície no lugar de ponto-ponto)