The ICP algorithm and its extensions Local, Rigid, Pairwise

(1)

Local, Rigid, Pairwise

The ICP algorithm and its extensions

(2)

(3)

•

(4)

(5)

(6)

•

(7)

k

 ^ ^

2

 Rp

_i

t q

_i

E

(8)

1. Selecting source points (from one or both meshes) 2. Matching to points in the other mesh

3. Weighting the correspondences

4. Rejecting certain (outlier) point pairs

5. Assigning an error metric to the current transform 6. Minimizing the error metric w.r.t. transformation

(9)

•

(10)

(11)

(12)

R

    

 ⁽ ⁾ 

²

 ^ ^ ^

 Rp

_i

t q

_i

n

_i

E

 



 







 





















 

z y x i

i i

i

r r r r

n t n

p r

n q

p

E ( ) ( )

²

, where

(13)

 





 



 

 







 







 







 



 

































2 2

1 1 1 2

2 2

1 1

2) (

) 1 (

, ,

,

n q p

t t t r r r

n n

p

n n

p

b x

z y x z y x

A

  ^b

x

b x

1 T T

T T

A A

A A A

A







(14)

(15)

(16)

•

(17)

(18)

•

(19)

Uniform Sampling Stable Sampling

(20)

A

^T

Ax = A

^T

b

C = A

^T

A

 





 



 

 







 







 







 



 

^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^



2 2

1 1 1 2

2 2

1 1

2) (

) 1 (

,

^p ^q ⁿ

n q p

t t t r r r

n n

p

n n

p

b x

z y x z y x

A

(21)

C

3 small eigenvalues 3 rotation

3 small eigenvalues 2 translation

1 rotation

2 small eigenvalues 1 translation

1 rotation

1 small eigenvalue 1 rotation

1 small eigenvalue 1 translation

[Gelfand et al. ‘04]

(22)

Key: 3 DOFs stable 4 DOFs stable

5 DOFs stable 6 DOFs stable

(23)

• C

•

(24)

Random sampling Normal-space sampling

(25)

(26)

(27)

•

(28)

•

(29)

(30)

•

(31)

(32)

(33)

(34)

(35)

•

f(x)

(36)

•

f’(x)

(37)

•

(38)

(39)

(40)

(41)

(42)

(43)



(44)

2D 3D [Mitra et al. 2004]

(45)

•

(46)

Translation in x-z plane.

Rotation about y-axis.

Converges

Does not converge

(47)

distance-field

formulation

Plane-to-plane ICP

The ICP algorithm and its extensions Local, Rigid, Pairwise

Local, Rigid, Pairwise