ÿþG e o m e t r i c A l g e b r a a n d C o m p u t e r V i s i o n
T h e A u t o - c a l i b r a t i o n P r o b l e m
C h r i s D o r a n
D e p a r t m e n t o f P h y s i c s
M a d i n g l e y R o a d , C a m b r i d g e
C . D o r a n @ m r a o . c a m . a c . u k
w w w . m r a o . c a m . a c . u k / c l i f f o r d /
S U M M A R Y
1 . R o t o r s , b i v e c t o r s a n d r o t a t i o n s . W a y s o f r e p r e s e n t i n g
r o t a t i o n s a n d t h e g r o u p m a n i f o l d .
2 . E x t r a p o l a t i n g r o t o r s a n d r o t o r c a l c u l u s . T h e l i n e a r s p a c e
a s s o c i a t e d w i t h r o t o r s , e x t r a p o l a t i n g a n d a v e r a g i n g
r o t a t i o n s .
3 . T h e k n o w n r a n g e d a t a p r o b l e m . L e a s t s q u a r e s , i t s
B a y e s i a n o r i g i n a n d s o l u t i o n f o r 2 a n d c a m e r a s .
4 . U n k n o w n r a n g e d a t a p r o b l e m . B a y e s i a n a n a l y s i s a g a i n
a n d i t s g e o m e t r i c s o l u t i o n . 2 c a m e r a d a t a a n d t h e
- c a m e r a p r o b l e m .
1
G E O M E T R I C A L G E B R A I N 3 - D
1 s c a l a r 3 v e c t o r s 3 b i v e c t o r s 1 t r i v e c t o r
N B f o r t h e p s e u d o s c a l a r . G e o m e t r i c p r o d u c t h a s
Æ
D o t a n d w e d g e s y m b o l s h a v e u s u a l m e a n i n g
A r o t o r i s a n o r m a l i s e d e l e m e n t o f t h e e v e n s u b a l g e b r a ,
T h e t i l d e i s t h e r e v e r s e o p e r a t i o n . R o t o r s g e n e r a t e r o t a t i o n s
v i a
W e c a n a l s o w r i t e
R g e n e r a t e s a r o t a t i o n o f i n a p o s i t i v e ( r i g h t h a n d e d )
s e n s e i n t h e p l a n e . I n 3 - d w e c a n a l s o w r i t e
w h e r e i s t h e u n i t v e c t o r r e p r e s e n t i n g t h e a x i s .
2
T H E G R O U P M A N I F O L D
R o t o r s a r e e l e m e n t s o f a 4 - d s p a c e , n o r m a l i s e d t o 1 . T h e y l i e
o n a 3 - s p h e r e . T h i s i s t h e g r o u p m a n i f o l d . A n y p a t h s b e t w e e n
r o t o r s m u s t l i e o n t h i s m a n i f o l d .
A t a n y p o i n t o n t h e m a n i f o l d , t h e t a n g e n t s p a c e i s
3 - d i m e n s i o n a l . J u s t l i k e t h e 2 - s p h e r e i n 3 - d :
T a n g e n t p l a n e
R o t o r s r e q u i r e 3 p a r a m e t e r s , e g . E u l e r a n g l e s
B u t o f t e n m o r e c o n v e n i e n t t o u s e t h e s e t o f b i v e c t o r
g e n e r a t o r s w i t h
S m a l l C o m p l i c a t i o n : T h e r o t o r s a n d g e n e r a t e t h e
s a m e r o t a t i o n . T h e r o t a t i o n g r o u p m a n i f o l d i s m o r e
c o m p l i c a t e d i t i s a p r o j e c t i v e 3 - s p h e r e w i t h a n d
i d e n t i f i e d . U s u a l l y e a s i e r t o w o r k w i t h r o t o r s .
3
E X T R A P O L A T I N G B E T W E E N R O T A T I O N S
G i v e n t w o e s t i m a t e s o f a r o t a t i o n , a n d , h o w d o w e f i n d
t h e m i d - p o i n t ? W i t h r o t o r s t h i s i s r e m a r k a b l y e a s y ! M a k e s u r e
t h e y h a v e s m a l l e s t 4 - d a n g l e o n 3 - s p h e r e . P a t h b e t w e e n t h e m
i s
s o f i n d f r o m
T h i s p a t h i s i n v a r i a n t . I f b o t h e n d p o i n t s a r e t r a n s f o r m e d , t h e
p a t h t r a n s f o r m s i n t h e s a m e w a y . T h e m i d p o i n t i s
T h i s i s g e n e r a l w o r k s f o r a n y L i e g r o u p . F o r r o t a t i o n s i n 3 - d
c a n d o e v e n b e t t e r . a n d c a n b e v i e w e d a s t w o u n i t
v e c t o r s i n 4 - d . T h e a b o v e c o n s t r u c t i o n g i v e s t h e p a t h i n t h e
p l a n e s p e c i f i e d b y t h e s e v e c t o r s
4
T h e r o t o r p a t h c a n t h e r e f o r e b e w r i t t e n a s ( s i m p l e t r i g )
a n d t h e m i d p o i n t r o t o r i s s i m p l y
G i v e s a v e r y s i m p l e p r e s c r i p t i o n f o r f i n d i n g t h e m i d p o i n t :
A d d t h e r o t o r s a n d n o r m a l i s e t h e r e s u l t
E x t r e m e l y s i m p l e ! C o m p a r e w i t h t h e e q u i v a l e n t m a t r i x
q u a d r a t i c i n , s o t h e e x p r e s s i o n i s a m e s s .
T h e s e f o r m u l a e a r e v e r y u s e f u l i n d y n a m i c s .
A v e r a g i n g R o t a t i o n s
S u p p o s e n o w t h a t w e h a d a n u m b e r o f e s t i m a t e s f o r a r o t a t i o n
a n d w a n t e d t o t a k e t h e a v e r a g e . A g a i n t h e a n s w e r i s s i m p l e
a d d u p a l l o f t h e r o t o r s a n d n o r m a l i s e ( t a k i n g c a r e t o m a k e
s u r e t h e y a r e a l l i n t h e c l o s e s t c o n f i g u r a t i o n ) . U s e f u l i n
c o m p u t e r v i s i o n .
L e s s o n
C a n s i m p l i f y p r o b l e m s w i t h r o t a t i o n s b y r e l a x i n g t h e
n o r m a l i s a t i o n c r i t e r i a f o r r o t o r s a n d w o r k i n g i n t h e 4 - d l i n e a r
s p a c e . T h i s p r o v i d e s u s w i t h o n e f u r t h e r a d d i t i o n a l t o o l :
5
R O T O R C A L C U L U S
C a n v i e w a f u n c t i o n o f a r o t a t i o n a s t a k i n g v a l u e s o v e r t h e
g r o u p m a n i f o l d . C a l c u l u s i n t h e s e c a s e s i s p o s s i b l e , b u t a b i t
m e s s y . ( O f t e n r e s o r t t o E u l e r a n g l e s . )
N o w h a v e a m o r e e l e g a n t a n d s i m p l e r a l t e r n a t i v e : r e l a x t h e
n o r m a l i s a t i o n c o n s t r a i n t a n d r e p l a c e b y a g e n e r a l
e l e m e n t o f t h e e v e n s u b a l g e b r a . S t a r t w i t h s i m p l e r e s u l t
w h e r e c o n t a i n s o n l y e v e n - g r a d e t e r m s . T r i c k n o w i s t o w r i t e
T y p i c a l a p p l i c a t i o n i s o n s c a l a r
w h e r e p r o j e c t s o n t o s c a l a r p a r t . N o w h a v e
w h e r e o v e r d o t d e n o t e s s c o p e .
6
N e e d a f o r m u l a f o r t h e i n v e r s e t e r m . U s e
C a n n o w c o m p l e t e d e r i v a t i o n
C o n v e n i e n t t o p r e m u l t i p l y b y
N o t e t h e g e o m e t r i c p r o d u c t . T h e r e s u l t i s a b i v e c t o r a
3 - p a r a m e t e r s p a c e , a s e x p e c t e d .
T h i s s i m p l e d e r i v a t i o n t u r n s o u t t o b e v e r y u s e f u l i n a r a n g e o f
a p p l i c a t i o n s .
7
C O M P U T E R V I S I O N
B a s i c p r o b l e m o f i n t e r e s t i s t h e a u t o - c a l i b r a t i o n p r o b l e m .
S u p p o s e w e h a v e d i f f e r e n t c a m e r a v i e w s o f t h e s a m e s c e n e .
O b j e c t
C a m e r a 2
C a m e r a 1
G i v e n p o i n t m a t c h e s ( + n o i s e ) c a n w e f i g u r e o u t t h e r e l a t i v e
t r a n s l a t i o n a n d r o t a t i o n b e t w e e n t h e c a m e r a s ( t o c a l i b r a t e ) .
T h e n u s e t h e c a l i b r a t e d c a m e r a s t o r e c o n s t r u c t a 3 - d s c e n e .
A p p l i c a t i o n s
1 . G a i t a n a l y s i s r u n n i n g e t c .
2 . M o t i o n a n a l y s i s s p o r t s a n a l y s i s a n d R S I i n m u s i c i a n s
3 . R e a c h i n g a n d N e u r o g e o m e t r y .
4 . 3 - d R e c o n s t r u c t i o n e g . u s i n g a s i n g l e m o v i n g c a m e r a
a t t a c h e d t o a r o b o t a r m .
T w o d i s t i n c t p r o b l e m s t o s t u d y .
8
K N O W N R A N G E D A T A
S u p p o s e w e k n o w t h e f u l l 3 - d p o s i t i o n s o f e a c h p o i n t m a t c h
( n o t v e r y l i k e l y i n p r a c t i c e ) . H a v e c o o r d i n a t e s a n d
r e l a t i v e t o f i r s t a n d s e c o n d c a m e r a . W i t h t h e f i r s t c a m e r a
f r a m e , d e f i n e
a n d h a v e
S h o u l d h a v e
W a n t b e s t f i t a n d w i t h v a r i o u s p o i n t m a t c h e s . M i n i m i s e
l e a s t s q u a r e s e r r o r
T h e r e i s a B a y e s i a n d e r i v a t i o n o f t h i s r e s u l t . S t a r t w i t h
G a u s s i a n d i s t r i b u t i o n f o r t h e c o o r d i n a t e s
( b a r f o r t r u e p o s i t i o n ) . M a r g i n a l i s e o v e r a c t u a l p o s i t i o n s t o g e t
l i k e l i h o o d f u n c t i o n i n t e r m s o f d a t a , a n d . A l w a y s u s e f u l t o
s e e h o w e x p r e s s i o n s a r i s e f r o m a s i m p l e p r o b a b i l i s t i c
a r g u m e n t .
9
S o l u t i o n
D i f f e r e n t i a t i n g w r t a n d i s s t r a i g h t f o r w a r d
s o b e s t f i t , , g i v e n b y
i e d i f f e r e n c e i n c e n t r o i d s . F o r d e r i v a t i v e w r i t e
s o j u s t n e e d
S u b s t i t u t e s o l u t i o n f o r , g e t s i m p l y
w h e r e
E a s i l y s o l v e d w i t h a n S V D o f . C o m p u t a t i o n a l l y v e r y
e f f i c i e n t . A u s e f u l c h e c k o n a n y r e c o n s t r u c t i o n .
1 0
E X T E N S I O N T O C A M E R A S
G e t t h e g e n e r a l i d e a b y c o n s i d e r i n g 3 c a m e r a s . E x p r e s s
e v e r y t h i n g i n a g l o b a l f r a m e .
O b j e c t
C a m e r a 1 C a m e r a 3
C a m e r a 2
W e c o u l d m i n i m i s e
b u t t h i s i s n o t s y m m e t r i c . I n s t e a d c o n s i d e r e a c h p a i r i n t u r n
w i t h a s e p a r a t e r o t o r f o r e a c h p a i r .
T h e r o t o r s a n d t r a n s l a t i o n s s h o u l d b e c o n s i s t e n t .
1 1
I m p o s e c o n s t r a i n t s
C a n p r o c e e d a s a b o v e f o r t h e t r a n s l a t i o n s . F i n d t h a t ,
a n d a r e s t i l l d i f f e r e n c e o f c e n t r o i d s . T h e c o n s t r a i n t i s
a u t o m a t i c a l l y s a t i s f i e d .
T o f i n d c e n t r o i d s w e s t i l l n e e d t h e r o t o r s . E n f o r c e r o t o r
c o n s t r a i n t w i t h a L a g r a n g e M u l t i p l i e r o f f o r m
m u s t b e a m u l t i v e c t o r L a g r a n g e m u l t i p l i e r t o e n s u r e
c o n s i s t e n c y ( B e c a u s e n o r m a l i s a t i o n i s r e l a x e d ) . N o w t a k e
, s o f i n a l e x p r e s s i o n t o m i n i m i s e i s
G e t t h r e e e q u a t i o n s , a s p r e c e d i n g , e a c h o f f o r m
1 2
F o r r i g h t - h a n d s i d e u s e
s o g e t s a m e b i v e c t o r f o r e a c h o f t h e t h r e e e q u a t i o n s .
I n t r o d u c i n g t h r e e t e n s o r , o n e f o r e a c h p a i r , g e t s y m m e t r i c s e t
o f e q u a t i o n s
W a n t t o f i n d r o t o r s t o m i n i m i s e m u t u a l a n t i s y m m e t r i c
c o n t r i b u t i o n , s u b j e c t t o c o n s t r a i n t . S l i g h t l y
m o r e c o m p l i c a t e d b u t n o t h a r d t o s o l v e n u m e r i c a l l y ,
p a r t i c u l a r l y a s t h e i n d i v i d u a l p a i r w i s e m i n i m i s e r s a r e a g o o d
s t a r t i n g p o i n t .
1 3
U N K N O W N R A N G E D A T A
U s u a l l y w e d o n o t k n o w t h e r a n g e d a t a i n s t e a d w e j u s t
k n o w t h e p r o j e c t i v e v e c t o r s o n t h e c a m e r a p l a n e
I m a g e P l a n e
a n d c h o o s e s c a l e w i t h , ,
R e p r e s e n t l i n e i n 2 - d w i t h t h e b i v e c t o r
( t a k i n g ) . C o m p o n e n t s a r e
h o m o g e n e o u s c o o r d i n a t e s i n d e p e n d e n t o f s c a l e . T y p i c a l l y
t h e s e a r e m e a s u r e d .
1 4
T w o m a i n s o u r c e s o f n o i s e :
1 . P i x e l i s a t i o n N o i s e d u e t o f i n i t e r e s o l u t i o n .
2 . R a n d o m N o i s e d u e t o c a m e r a m o t i o n , e t c . A s s u m e t o b e
G a u s s i a n .
C a n g e t a l i k e l i h o o d f u n c t i o n b y m a r g i n a l i s i n g o v e r t h e
u n k n o w n r a n g e d a t a . D o t h i s w i t h i n t e g r a l s o f t h e t y p e
w h i c h g i v e s a l i k e l i h o o d f u n c t i o n g o i n g w i t h
H a s a s i m p l e g e o m e t r i c i n t e r p r e t a t i o n
C a m e r a 2
L i n e D i s t a n c e
C a m e r a 1
C a m e r a p l a n e v e c t o r s e x t e n d e d o u t t o 3 - d s p a c e .
1 5
F i n d t h e r o t o r w h i c h m i n i m i s e s t h e s q u a r e d d i s t a n c e b e t w e e n
t h e l i n e s f o r e a c h p o i n t m a t c h .
T h e s e t u p i s s c a l e - i n v a r i a n t , s o n e e d t o i m p o s e a s c a l e . D o
t h i s b y f i x i n g w i t h a L a g r a n g e m u l t i p l i e r . O u r f i n a l
f u n c t i o n i s
T h i s i s s t i l l q u a d r a t i c i n a n d m i n i m i s i n g g i v e s t h e e q u a t i o n
W e t h e r e f o r e c o n s t r u c t t h e s y m m e t r i c , p o s i t i v e d e f i n i t e
f u n c t i o n
T h i s i s a f u n c t i o n o f t h e d a t a a n d t h e r o t a t i o n o n l y . T h e
t r a n s l a t i o n i s t h e e i g e n v e c t o r c o r r e s p o n d i n g t o t h e m i n i m u m
e i g e n v a l u e . T h i s e i g e n v a l u e i s
s o t h e e i g e n v a l u e g i v e s t h e e r r o r f u n c t i o n . A l l n e e d d o i s
m i n i m i s e t h e l o w e s t e i g e n v a l u e o f w i t h r e s p e c t t o t h e r o t o r
. A f a i r l y s i m p l e o p t i m i s a t i o n p r o b l e m .
1 6
N U M E R I C A L R E S U L T S
3 - d c o n t o u r p l o t s o f t h e f u n c t i o n n e a r t h e m i n i m u m l o o k
r e a s s u r i n g :
T h e p l o t s s h o w s u r f a c e s o f i n c r e a s i n g i n t h e b i v e c t o r s p a c e .
A c l e a r t r e n d t o w a r d s a m i n i m u m . T h e s e p l o t s u s e d 8 , 0 0 0
f u n c t i o n e v a l u a t i o n s e a c h . E a c h p l o t s t a k e s o n l y 1 s e c . o n
a P e n t i u m I I .
1 7
S m a l l P r o b l e m
T h e f u n c t i o n h a s a n u m b e r o f l o c a l m i n i m a . D o w n h i l l s i m p l e x
r o u t i n e s d o n o t a l w a y s f i n d t h e g l o b a l m i n i m u m . N e e d
a n n e a l i n g m e t h o d s , o r j u s t u s e b r u t e f o r c e .
A l s o s e e t h a t f u n c t i o n b e h a v e s v e r y d i f f e r e n t l y a l o n g d i r e c t i o n
o f r o t a t i o n . F r o m
S u g g e s t s a n u m b e r o f p o t e n t i a l i m p r o v e m e n t s e . g . r e d u c e
t o a 2 - d f u n c t i o n b y m i n i m i s i n g f o r a n g l e .
1 8
E X T E N S I O N T O C A M E R A S
A g a i n t h i s i s e a s y . C a n i m m e d i a t e l y w r i t e d o w n a n e x p r e s s i o n
t o m i n i m i s e f o r t h e t r a n s l a t i o n v e c t o r s
N o r m a l i s a t i o n k e e p s e v e r y t h i n g s y m m e t r i c . N o w g e t t h r e e
e q u a t i o n s
w i t h t h e t w o c o n s t r a i n t s
T h e l a t t e r e n s u r e s t h a t w e s t i l l h a v e . C a n r e c a s t a s a
m a t r i x e q u a t i o n o f f o r m
H e n c e f i n d . A g a i n , l o o k f o r b e s t f i t n u m e r i c a l l y .
1 9
C O N C L U S I O N S
1 . G e o m e t r i c A l g e b r a i s e x t r e m e l y p o w e r f u l f o r h a n d l i n g
r o t a t i o n s i n 3 - d .
2 . G e o m e t r i c C a l c u l u s i s e x t r e m e l y u s e f u l f o r e x t r e m i s a t i o n
p r o b l e m s i n v o l v i n g r o t a t i o n s .
3 . M a n y c o m p u t e r v i s i o n p r o b l e m s b e s t t a c k l e d b y w o r k i n g
d i r e c t l y w i t h r o t a t i o n s a n d t r a n s l a t i o n s .
4 . A u t o - c a l i b r a t i n g c a m e r a s f o r p o i n t m a t c h e s w i t h u n k n o w n
r a n g e d a t a i s n o t h a r d , e v e n i n t h e p r e s e n c e o f n o i s e .
5 . T h e B a y e s i a n d e r i v a t i o n h i g h l i g h t s t h e a s s u m p t i o n s g o i n g
i n t o t h e a l g o r i t h m s . C a n c h a n g e a s s u m p t i o n s t o m o d e l
n o i s e b e t t e r . S h o u l d g i v e e v e n b e t t e r r e s u l t s
2 0
Wyszukiwarka
Podobne podstrony:
Dorst GA the Framework 4 Geom Computing (2002) [sharethefiles com]Doran New Advances in Geometric Algebra (2001) [sharethefiles com]Doran & Lasenby PHYSICAL APPLICATIONS OF geometrical algebra [sharethefiles com]Hestenes New Algebraic Framework 4 Comp Geometry [sharethefiles com]Czichowski Computer algebra [sharethefiles com]Doran Beyond Euclidean Geometry (2001) [sharethefiles com]Soroka Linear Odd Poisson Bracket on Grassmann Algebra (2000) [sharethefiles com]Cuartero et al Linearly Compact Algebraic Lie Algebras (1997) [sharethefiles com]Doran Grassmann Mechanics Multivector?rivatives & GA (1992) [sharethefiles com]Vershik Graded Lie Algebras & Dynamical Systems (2001) [sharethefiles com]Applications of linear algebra to differential equation [sharethefiles com]Moya Metric Clifford Algebra (2002) [sharethefiles com]Doran New Form of the Kerr Solution [sharethefiles com]Hestenes Hamiltonian Mechanics with Geometric?lculus (1993) [sharethefiles com]Timorin Circles & Clifford Algebras (2002) [sharethefiles com]Hestenes Grassmann s Vision (1996) [sharethefiles com]Doran & Lasenby, Geometric Algebra New Foundations, New InsightsKollar The Topology of Real & Complex Algebraic Varietes [sharethefiles com]więcej podobnych podstron