Shape Matching

전체 글

(1)

Shape Matching

Wanho Choi

(wanochoi.com)

(2)

What is the

best

4 by 4

similarity transformation

matrix

between two point clouds which have same # of points?

Shape Matching Problem

P

= p

{ }

i

Q

= q

{ }

i

i

= 1,0,!,n

(

)

(

i

= 1,0,!,n

)

(translation, rotation, and isotropic scale)

argmin

M

Mp

i

− q

i

2

i

=1

n

⎣⎢

⎦⎥

(3)

Shape Matching Problem

argmin

M

Mp

i

− q

i

2

i

=1

n

⎣⎢

⎦⎥

A : 3 by 3 matrix rotation & scale

(

)

t : 3D translation

(4)

Translation is easy!

A : 3 by 3 matrix rotation & scale

(

)

t : 3D translation

c

p

=

1

n

i

=1

p

i

n

c

q

=

1

n

i

=1

q

i

n

t

= c

q

− c

p

Mp

i

= q

i

⇔ Ap

i

+ t = q

i

argmin

M

Mp

i

− q

i

2

i

=1

n

⎣⎢

⎦⎥

(5)

Relative Positions

p

i

= p

i

− c

p

q

i

= q

i

− c

q

A : 3 by 3 matrix rotation & scale

(

)

t : 3D translation

Mp

i

= q

i

⇔ Ap

i

+ t = q

i

argmin

M

Mp

i

− q

i

2

i

=1

n

⎣⎢

⎦⎥

Ap

i

= q

i

(6)

Minimization

argmin

A

Ap

i

− q

i

2

i

=1

n

⎣⎢

⎦⎥

(7)

Minimization

∂A

Ap

i

− q

i 2 i=1 n

⎣⎢

⎦⎥

argmin

A

Ap

i

− q

i

2

i

=1

n

⎣⎢

⎦⎥

(8)

Minimization

∂A

Ap

i

− q

i 2 i=1 n

⎣⎢

⎦⎥

= ∂

∂A

Ap

1

− q

1 2

⎦ +

∂A

Ap

2

− q

2 2

⎦ +!+

∂A

Ap

n

− q

n 2

argmin

A

Ap

i

− q

i

2

i

=1

n

⎣⎢

⎦⎥

(9)

Minimization

∂A

Ap

i

− q

i 2 i=1 n

⎣⎢

⎦⎥

= ∂

∂A

Ap

1

− q

1 2

⎦ +

∂A

Ap

2

− q

2 2

⎦ +!+

∂A

Ap

n

− q

n 2

∵ ∂ ∂A Api − qi 2 ⎡ ⎣ ⎤⎦ = 2 Ap

(

i − qi

)

pi T ⎛ ⎝⎜ ⎞⎠⎟

= 2 Ap

(

1

− q

1

)

p

1T

+ 2 Ap

(

2

− q

2

)

p

2T

+!+ 2 Ap

(

n

− q

n

)

p

nT

argmin

A

Ap

i

− q

i

2

i

=1

n

⎣⎢

⎦⎥

(10)

Minimization

∂A

Ap

i

− q

i 2 i=1 n

⎣⎢

⎦⎥

= ∂

∂A

Ap

1

− q

1 2

⎦ +

∂A

Ap

2

− q

2 2

⎦ +!+

∂A

Ap

n

− q

n 2

∵ ∂ ∂A Api − qi 2 ⎡ ⎣ ⎤⎦ = 2 Ap

(

i − qi

)

pi T ⎛ ⎝⎜ ⎞⎠⎟

= 2 Ap

(

1

− q

1

)

p

1T

+ 2 Ap

(

2

− q

2

)

p

2T

+!+ 2 Ap

(

n

− q

n

)

p

nT

= 2 A p

⎡⎣

( )

1

p

1T

− q

( )

1

p

1T

⎤⎦+ 2 A p

⎡⎣

(

2

p

2T

)

− q

( )

2

p

2T

⎤⎦+!+ 2 A p

⎡⎣

(

n

p

nT

)

− q

( )

n

p

nT

⎤⎦

argmin

A

Ap

i

− q

i

2

i

=1

n

⎣⎢

⎦⎥

(11)

Minimization

∂A

Ap

i

− q

i 2 i=1 n

⎣⎢

⎦⎥

= ∂

∂A

Ap

1

− q

1 2

⎦ +

∂A

Ap

2

− q

2 2

⎦ +!+

∂A

Ap

n

− q

n 2

∵ ∂ ∂A Api − qi 2 ⎡ ⎣ ⎤⎦ = 2 Ap

(

i − qi

)

pi T ⎛ ⎝⎜ ⎞⎠⎟

= 2 Ap

(

1

− q

1

)

p

1T

+ 2 Ap

(

2

− q

2

)

p

2T

+!+ 2 Ap

(

n

− q

n

)

p

nT

= 2 A p

⎡⎣

( )

1

p

1T

− q

( )

1

p

1T

⎤⎦+ 2 A p

⎡⎣

(

2

p

2T

)

− q

( )

2

p

2T

⎤⎦+!+ 2 A p

⎡⎣

(

n

p

nT

)

− q

( )

n

p

nT

⎤⎦

= 2A

p

i

p

iT i=1 n

⎝⎜

⎠⎟

− 2

q

i

p

i T i=1 n

⎝⎜

⎠⎟

argmin

A

Ap

i

− q

i

2

i

=1

n

⎣⎢

⎦⎥

(12)

Minimization

argmin

A

Ap

i

− q

i

2

i

=1

n

⎣⎢

⎦⎥

∂A

Ap

i

− q

i 2 i=1 n

⎣⎢

⎦⎥

= ∂

∂A

Ap

1

− q

1 2

⎦ +

∂A

Ap

2

− q

2 2

⎦ +!+

∂A

Ap

n

− q

n 2

∵ ∂ ∂A Api − qi 2 ⎡ ⎣ ⎤⎦ = 2 Ap

(

i − qi

)

pi T ⎛ ⎝⎜ ⎞⎠⎟

= 2 Ap

(

1

− q

1

)

p

1T

+ 2 Ap

(

2

− q

2

)

p

2T

+!+ 2 Ap

(

n

− q

n

)

p

nT

= 2 A p

⎡⎣

( )

1

p

1T

− q

( )

1

p

1T

⎤⎦+ 2 A p

⎡⎣

(

2

p

2T

)

− q

( )

2

p

2T

⎤⎦+!+ 2 A p

⎡⎣

(

n

p

nT

)

− q

( )

n

p

nT

⎤⎦

= 2A

p

i

p

iT i=1 n

⎝⎜

⎠⎟

− 2

q

i

p

i T i=1 n

⎝⎜

⎠⎟

= 0

(13)

Minimization

∂A

Ap

i

− q

i 2 i=1 n

⎣⎢

⎦⎥

= ∂

∂A

Ap

1

− q

1 2

⎦ +

∂A

Ap

2

− q

2 2

⎦ +!+

∂A

Ap

n

− q

n 2

∵ ∂ ∂A Api − qi 2 ⎡ ⎣ ⎤⎦ = 2 Ap

(

i − qi

)

pi T ⎛ ⎝⎜ ⎞⎠⎟

= 2 Ap

(

1

− q

1

)

p

1T

+ 2 Ap

(

2

− q

2

)

p

2T

+!+ 2 Ap

(

n

− q

n

)

p

nT

= 2 A p

⎡⎣

( )

1

p

1T

− q

( )

1

p

1T

⎤⎦+ 2 A p

⎡⎣

(

2

p

2T

)

− q

( )

2

p

2T

⎤⎦+!+ 2 A p

⎡⎣

(

n

p

nT

)

− q

( )

n

p

nT

⎤⎦

= 2A

p

i

p

iT i=1 n

⎝⎜

⎠⎟

− 2

q

i

p

i T i=1 n

⎝⎜

⎠⎟

= 0

∴A =

q

i

p

iT i=1 n

⎝⎜

⎠⎟

p

i

p

i T i=1 n

⎝⎜

⎠⎟

−1

argmin

A

Ap

i

− q

i

2

i

=1

n

⎣⎢

⎦⎥

(14)
(15)

A Simple Proof On

∂A

⎡⎣

Ap

− q

2

⎤⎦ = 2 Ap−q

(

)

p

T

(16)

A Simple Proof On

∂A

⎡⎣

Ap

− q

2

⎤⎦ = 2 Ap−q

(

)

p

T Let A= a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥, p =xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥, and q= uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥.

(17)

A Simple Proof On

∂A

⎡⎣

Ap

− q

2

⎤⎦ = 2 Ap−q

(

)

p

T Let A= a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥, p =xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥, and q= uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥.

For simplicity, let's just look at the 2D case.

When θ∈!, ∂θ ∂A ≡ ∂θ ∂a ∂θ ∂b ∂θ ∂c ∂θ ∂d ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ .

(18)

A Simple Proof On

∂A

⎡⎣

Ap

− q

2

⎤⎦ = 2 Ap−q

(

)

p

T Let A= a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥, p =xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥, and q= uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥.

For simplicity, let's just look at the 2D case.

When θ∈!, ∂θ ∂A ≡ ∂θ ∂a ∂θ ∂b ∂θ ∂c ∂θ ∂d ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ . ∂ ∂A Ap− q 2 ⎡⎣ ⎤⎦

(19)

A Simple Proof On

∂A

⎡⎣

Ap

− q

2

⎤⎦ = 2 Ap−q

(

)

p

T Let A= a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥, p =xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥, and q= uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥.

For simplicity, let's just look at the 2D case.

When θ∈!, ∂θ ∂A ≡ ∂θ ∂a ∂θ ∂b ∂θ ∂c ∂θ ∂d ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ . ∂ ∂A Ap− q 2 ⎡⎣ ⎤⎦ = ∂A∂ ⎡a bc d ⎤ ⎦ ⎥⎡ xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥

(20)

A Simple Proof On

∂A

⎡⎣

Ap

− q

2

⎤⎦ = 2 Ap−q

(

)

p

T Let A= a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥, p =xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥, and q= uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥.

For simplicity, let's just look at the 2D case.

When θ∈!, ∂θ ∂A ≡ ∂θ ∂a ∂θ ∂b ∂θ ∂c ∂θ ∂d ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ . ∂ ∂A Ap− q 2 ⎡⎣ ⎤⎦ = ∂A∂ ⎡a bc d ⎤ ⎦ ⎥⎡ xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂∂A ax+ by cx+ dy ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥

(21)

A Simple Proof On

∂A

⎡⎣

Ap

− q

2

⎤⎦ = 2 Ap−q

(

)

p

T Let A= a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥, p =xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥, and q= uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥.

For simplicity, let's just look at the 2D case.

When θ∈!, ∂θ ∂A ≡ ∂θ ∂a ∂θ ∂b ∂θ ∂c ∂θ ∂d ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ . ∂ ∂A Ap− q 2 ⎡⎣ ⎤⎦ = ∂A∂ ⎡a bc d ⎤ ⎦ ⎥⎡ xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂∂A ax+ by cx+ dy ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂Aax+ by − u cx+ dy − v ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥

(22)

A Simple Proof On

∂A

⎡⎣

Ap

− q

2

⎤⎦ = 2 Ap−q

(

)

p

T Let A= a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥, p =xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥, and q= uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥.

For simplicity, let's just look at the 2D case.

When θ∈!, ∂θ ∂A ≡ ∂θ ∂a ∂θ ∂b ∂θ ∂c ∂θ ∂d ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ . ∂ ∂A Ap− q 2 ⎡⎣ ⎤⎦ = ∂A∂ ⎡a bc d ⎤ ⎦ ⎥⎡ xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂∂A ax+ by cx+ dy ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂Aax+ by − u cx+ dy − v ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂ ∂A

(

ax+ by − u

)

2 + cx + dy − v

(

)

2 ⎡⎣ ⎤⎦

(23)

A Simple Proof On

∂A

⎡⎣

Ap

− q

2

⎤⎦ = 2 Ap−q

(

)

p

T Let A= a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥, p =xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥, and q= uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥.

For simplicity, let's just look at the 2D case.

When θ∈!, ∂θ ∂A ≡ ∂θ ∂a ∂θ ∂b ∂θ ∂c ∂θ ∂d ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ . ∂ ∂A Ap− q 2 ⎡⎣ ⎤⎦ = ∂A∂ ⎡a bc d ⎤ ⎦ ⎥⎡ xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂∂A ax+ by cx+ dy ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂Aax+ by − u cx+ dy − v ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂ ∂A

(

ax+ by − u

)

2 + cx + dy − v

(

)

2 ⎡⎣ ⎤⎦ = ∂ ∂a(ax+ by − u) 2 ∂ ∂b(ax+ by − u) 2 ∂ ∂c(cx+ dy − v) 2 ∂ ∂d(cx+ dy − v) 2 ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥

(24)

A Simple Proof On

∂A

⎡⎣

Ap

− q

2

⎤⎦ = 2 Ap−q

(

)

p

T Let A= a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥, p =xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥, and q= uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥.

For simplicity, let's just look at the 2D case.

When θ∈!, ∂θ ∂A ≡ ∂θ ∂a ∂θ ∂b ∂θ ∂c ∂θ ∂d ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ . ∂ ∂A Ap− q 2 ⎡⎣ ⎤⎦ = ∂A∂ ⎡a bc d ⎤ ⎦ ⎥⎡ xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂∂A ax+ by cx+ dy ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂Aax+ by − u cx+ dy − v ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂ ∂A

(

ax+ by − u

)

2 + cx + dy − v

(

)

2 ⎡⎣ ⎤⎦ = ∂ ∂a(ax+ by − u) 2 ∂ ∂b(ax+ by − u) 2 ∂ ∂c(cx+ dy − v) 2 ∂ ∂d(cx+ dy − v) 2 ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ = 2(ax+ by − u)x 2(ax + by − u)y

2(cx+ dy − v)x 2(cx + dy − v)y ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥

(25)

A Simple Proof On

∂A

⎡⎣

Ap

− q

2

⎤⎦ = 2 Ap−q

(

)

p

T Let A= a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥, p =xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥, and q= uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥.

For simplicity, let's just look at the 2D case.

When θ∈!, ∂θ ∂A ≡ ∂θ ∂a ∂θ ∂b ∂θ ∂c ∂θ ∂d ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ . ∂ ∂A Ap− q 2 ⎡⎣ ⎤⎦ = ∂A∂ ⎡a bc d ⎤ ⎦ ⎥⎡ xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂∂A ax+ by cx+ dy ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂Aax+ by − u cx+ dy − v ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂ ∂A

(

ax+ by − u

)

2 + cx + dy − v

(

)

2 ⎡⎣ ⎤⎦ = ∂ ∂a(ax+ by − u) 2 ∂ ∂b(ax+ by − u) 2 ∂ ∂c(cx+ dy − v) 2 ∂ ∂d(cx+ dy − v) 2 ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ = 2(ax+ by − u)x 2(ax + by − u)y

2(cx+ dy − v)x 2(cx + dy − v)y ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = 2

(ax+ by − u)x (ax + by − u)y (cx+ dy − v)x (cx + dy − v)y ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥

(26)

A Simple Proof On

∂A

⎡⎣

Ap

− q

2

⎤⎦ = 2 Ap−q

(

)

p

T Let A= a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥, p =xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥, and q= uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥.

For simplicity, let's just look at the 2D case.

When θ∈!, ∂θ ∂A ≡ ∂θ ∂a ∂θ ∂b ∂θ ∂c ∂θ ∂d ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ . ∂ ∂A Ap− q 2 ⎡⎣ ⎤⎦ = ∂A∂ ⎡a bc d ⎤ ⎦ ⎥⎡ xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂∂A ax+ by cx+ dy ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂Aax+ by − u cx+ dy − v ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂ ∂A

(

ax+ by − u

)

2 + cx + dy − v

(

)

2 ⎡⎣ ⎤⎦ = ∂ ∂a(ax+ by − u) 2 ∂ ∂b(ax+ by − u) 2 ∂ ∂c(cx+ dy − v) 2 ∂ ∂d(cx+ dy − v) 2 ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ = 2(ax+ by − u)x 2(ax + by − u)y

2(cx+ dy − v)x 2(cx + dy − v)y ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = 2

(ax+ by − u)x (ax + by − u)y (cx+ dy − v)x (cx + dy − v)y ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = 2 ax+ by − u cx+ dy − v ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥⎡⎣ x y ⎤⎦

(27)

A Simple Proof On

∂A

⎡⎣

Ap

− q

2

⎤⎦ = 2 Ap−q

(

)

p

T Let A= a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥, p =xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥, and q= uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥.

For simplicity, let's just look at the 2D case.

When θ∈!, ∂θ ∂A ≡ ∂θ ∂a ∂θ ∂b ∂θ ∂c ∂θ ∂d ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ . ∂ ∂A Ap− q 2 ⎡⎣ ⎤⎦ = ∂A∂ ⎡a bc d ⎤ ⎦ ⎥⎡ xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂∂A ax+ by cx+ dy ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂Aax+ by − u cx+ dy − v ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂ ∂A

(

ax+ by − u

)

2 + cx + dy − v

(

)

2 ⎡⎣ ⎤⎦ = ∂ ∂a(ax+ by − u) 2 ∂ ∂b(ax+ by − u) 2 ∂ ∂c(cx+ dy − v) 2 ∂ ∂d(cx+ dy − v) 2 ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ = 2(ax+ by − u)x 2(ax + by − u)y

2(cx+ dy − v)x 2(cx + dy − v)y ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = 2

(ax+ by − u)x (ax + by − u)y (cx+ dy − v)x (cx + dy − v)y ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = 2 ax+ by − u cx+ dy − v ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥⎡⎣ x y ⎤⎦ = 2 a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ x y

(28)

A Simple Proof On

∂A

⎡⎣

Ap

− q

2

⎤⎦ = 2 Ap−q

(

)

p

T Let A= a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥, p =xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥, and q= uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥.

For simplicity, let's just look at the 2D case.

When θ∈!, ∂θ ∂A ≡ ∂θ ∂a ∂θ ∂b ∂θ ∂c ∂θ ∂d ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ . ∂ ∂A Ap− q 2 ⎡⎣ ⎤⎦ = ∂A∂ ⎡a bc d ⎤ ⎦ ⎥⎡ xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂∂A ax+ by cx+ dy ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂Aax+ by − u cx+ dy − v ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ 2 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = ∂ ∂A

(

ax+ by − u

)

2 + cx + dy − v

(

)

2 ⎡⎣ ⎤⎦ = ∂ ∂a(ax+ by − u) 2 ∂ ∂b(ax+ by − u) 2 ∂ ∂c(cx+ dy − v) 2 ∂ ∂d(cx+ dy − v) 2 ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ = 2(ax+ by − u)x 2(ax + by − u)y

2(cx+ dy − v)x 2(cx + dy − v)y ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = 2

(ax+ by − u)x (ax + by − u)y (cx+ dy − v)x (cx + dy − v)y ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = 2 ax+ by − u cx+ dy − v ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥⎡⎣ x y ⎤⎦ = 2 a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ xy ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥− uv ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ x y = 2 Ap − q

(

)

pT

(29)

Rotation Matrix

A

=

q

i

p

i

T

i

=1

n

⎝⎜

⎠⎟

p

i

p

i

T

i

=1

n

⎝⎜

⎠⎟

−1

(30)

Rotation Matrix

A

qp

A

pp

A

=

q

i

p

i

T

i

=1

n

⎝⎜

⎠⎟

p

i

p

i

T

i

=1

n

⎝⎜

⎠⎟

−1

(31)

Rotation Matrix

A

qp

A

pp

A

pp

: only scaling but no rotation

(

∵symmetric matrix

)

A

=

q

i

p

i

T

i

=1

n

⎝⎜

⎠⎟

p

i

p

i

T

i

=1

n

⎝⎜

⎠⎟

−1

(32)

Rotation Matrix

A

qp

A

pp

A

pp

: only scaling but no rotation

(

∵symmetric matrix

)

The optimal rotation R is the rotational part of A

qp

.

A

=

q

i

p

i

T

i

=1

n

⎝⎜

⎠⎟

p

i

p

i

T

i

=1

n

⎝⎜

⎠⎟

−1

(33)

Rotation Matrix

A

qp

A

pp

A

pp

: only scaling but no rotation

(

∵symmetric matrix

)

The optimal rotation R is the rotational part of A

qp

.

A

qp

= RS → A

qp

T

A

qp

= RS

( )

T

( )

RS

= S

T

R

T

RS

= S

T

S

= SS

A

=

q

i

p

i

T

i

=1

n

⎝⎜

⎠⎟

p

i

p

i

T

i

=1

n

⎝⎜

⎠⎟

−1

∴S = A

qp

T

A

qp

(34)

Rotation Matrix

A

qp

A

pp

A

pp

: only scaling but no rotation

(

∵symmetric matrix

)

The optimal rotation R is the rotational part of A

qp

.

A

qp

= RS → A

qp

T

A

qp

= RS

( )

T

( )

RS

= S

T

R

T

RS

= S

T

S

= SS

A

=

q

i

p

i

T

i

=1

n

⎝⎜

⎠⎟

p

i

p

i

T

i

=1

n

⎝⎜

⎠⎟

−1

∴S = A

qp

T

A

qp

: sqrt by SVD

(35)

Rotation Matrix

A

qp

A

pp

A

pp

: only scaling but no rotation

(

∵symmetric matrix

)

The optimal rotation R is the rotational part of A

qp

.

A

=

q

i

p

i

T

i

=1

n

⎝⎜

⎠⎟

p

i

p

i

T

i

=1

n

⎝⎜

⎠⎟

−1

A

qp

= RS → A

qp

T

A

qp

= RS

( )

T

( )

RS

= S

T

R

T

RS

= S

T

S

= SS

∴R = A

qp

S

−1

(36)
(37)

Rigid body

Soft body

(38)
(39)

수치

Updating...

참조

  1. wanochoi.com)
관련 주제 :