logo资料库

椭圆检测过程中的证明步骤.pdf

第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
第6页 / 共13页
第7页 / 共13页
第8页 / 共13页
资料共13页,剩余部分请下载后查看
P e r g a m o n P a t t e r n R e c o g n i t i o n , V o l . 2 9 , N o . 3 , p p . 3 6 9 3 8 1 , 1 9 9 6 E l s e v i e r S c i e n c e L t d P a t t e r n R e c o g n i t i o n S o c i e t y P r i n t e d i n G r e a t B r i t a i n . 0 0 3 1 - 3 2 0 3 / 9 6 $ 1 5 . 0 0 + . 0 0 0 0 3 1 - 3 2 0 3 ( 9 4 ) 0 0 0 9 6 - 8 O N U S I N G D I R E C T I O N A L I N F O R M A T I O N F O R P A R A M E T E R S P A C E D E C O M P O S I T I O N I N E L L I P S E D E T E C T I O N A L B E R T O S . A G U A D O , M . E U G E N I A M O N T I E L a n d M A R K S . N I X O N * D e p a r t m e n t o f E l e c t r o n i c s a n d C o m p u t e r S c i e n c e , U n i v e r s i t y o f S o u t h a m p t o n , H i g h f i e l d , S o u t h a m p t o n S 0 1 7 I B J , U . K . ( R e c e i v e d 1 9 J a n u a r y 1 9 9 5 ; i n r e v i s e d f o r m 5 J u n e 1 9 9 5 ; r e c e i v e d f o r p u b l i c a t i o n 3 J u l y 1 9 9 5 ) A b s t r a c t - - I n t h i s p a p e r w e u s e t h e p a r a m e t e r i c p o l a r r e p r e s e n t a t i o n t o e x t e n d t h e a p p l i c a t i o n o f e d g e d i r e c t i o n a l i n f o r m a t i o n f r o m c i r c l e t o e l l i p s e e x t r a c t i o n . A s a r e s u l t w e o b t a i n a m a p p i n g w h i c h d e c o m p o s e s t h e p a r a m e t e r s p a c e r e q u i r e d f o r e l l i p s e e x t r a c t i o n i n t o t w o i n d e p e n d e n t s u b - s p a c e s a n d o n e f i n a l h i s t o g r a m a c c u m u l a t o r . T h e m a p p i n g i n c l u d e s t h e t a n g e n t o f t h e a n g l e o f t h e f i r s t a n d s e c o n d d i r e c t i o n a l d e r i v a t i v e s . T h e s e t a n g e n t s a r e c o m p u t e d b y c o n s i d e r i n g e d g e d i r e c t i o n a t t w o b o r d e r p o i n t s . W e s h o w t h a t t h e u s e o f g r a d i e n t i n f o r m a t i o n f o r p a r a m e t e r s p a c e d e c o m p o s i t i o n a v o i d s t h e i n t e n s i v e p o i n t l a b e l l i n g i m p o s e d b y g e o m e t r i c c o n s t r a i n t s u s e d b y o t h e r a p p r o a c h e s . C o m p u t e r v i s i o n E l l i p s e d e t e c t i o n I m a g e s e g m e n t a t i o n F e a t u r e e x t r a c t i o n P a r a m e t e r s p a c e d e c o m p o s i t i o n H o u g h t r a n s f o r m l . I N T R O D U C T I O N T h e d e t e c t i o n o f g e o m e t r i c p r i m i t i v e s f r o m a n i m a g e i s o n e o f t h e b a s i c t a s k s o f c o m p u t e r v i s i o n . A g e o m e t r i c p r i m i t i v e i s r e p r e s e n t e d b y a m a t h e m a t i c a l e x p r e s s i o n w i t h a n u m b e r o f f r e e p a r a m e t e r s w h i c h d e f i n e i n s t a n - c e s o f a s h a p e . H e n c e , t h e e x t r a c t i o n p r o b l e m c e n t r e s o n o b t a i n i n g a n e s t i m a t e o f t h e f r e e p a r a m e t e r s a c - c o r d i n g t o t h e i n f o r m a t i o n o n a n i m a g e . T h e H o u g h t r a n s f o r m ( H T ) i s a w e l l - k n o w n m e t h o d t o d e t e c t s h a p e s b y i n d e p e n d e n t l y c o n s i d e r i n g g e o m e t r i c d a t a c o m p o s e d o f e d g e p o i n t s . T h e i n d e p e n d e n t e v i d e n c e a c c u m u l a t i o n o f t h e H T m a k e s i t r o b u s t , p r o v i d i n g a d e q u a t e r e s u l t s e v e n f o r o v e r l a p p i n g o r p a r t i a l l y o c - c l u d e d o b j e c t s . I n o r d e r t o g a t h e r e v i d e n c e , t h e H T d e f i n e s a m a p - p i n g f r o m t h e i m a g e s p a c e i n t o a p a r a m e t e r s p a c e . B y c o n s i d e r i n g e a c h b o r d e r p o i n t i n a n i m a g e , t h e m a p - p i n g a d d s a v o t e t o c h o s e n c e l l s i n a n a c c u m u l a t o r w h i c h r e p r e s e n t s t h e p a r a m e t e r s p a c e . T h e c e l l s i n - c r e a s e d a r e t h o s e w h o s e a s s o c i a t e d p a r a m e t e r s d e f i n e t h e g e o m e t r i c p r i m i t i v e w h i c h p a s s e s t h r o u g h t h e i m - a g e p o i n t . T h e r e f o r e , l o c a l m a x i m a i n t h e a c c u m u l a t o r a r r a y c o r r e s p o n d t o t h e p a r a m e t e r s o f d e t e c t e d s h a p e s . T h e H T w a s o r i g i n a l l y p r o p o s e d t o f i t s t r a i g h t l i n e s a n d t h e n e x t e n d e d t o a n a l y t i c a l c u r v e s 3 1 ~ A l t h o u g h t h e t e c h n i q u e c a n b e u s e d d i r e c t l y f o r a n y p a r a m e t e r i z e d c u r v e , t h e g e n e r a l i z a t i o n i m p l i e s a n e x p o n e n t i a l i n - c r e a s e i n c o m p u t a t i o n a l t i m e a n d s p a c e r e q u i r e m e n t s . f o r t h i s r e a s o n , n e w m e t h o d s b a s e d o n t h e o r i g i n a l H T h a v e b e e n p r o p o s e d ( a r e v i e w o f t h e m e t h o d s c a n b e s e e n i n I l l i n g w o r t h & K i t t l e r ~ 2 ~ a n d L e a v e r s t a ~ ) . * A u t h o r t o w h o m c o r r e s p o n d e n c e s h o u l d b e a d d r e s s e d . © C r o w n c o p y r i g h t ( 1 9 9 6 ) . T h e a i m o f t h i s p a p e r i s t o s h o w h o w d i r e c t i o n a l i n f o r m a t i o n c a n b e u s e d t o d e r i v e a m a p p i n g w h i c h d e c o m p o s e s t h e p a r a m e t e r s p a c e r e q u i r e d f o r t h e i m - p l e m e n t a t i o n o f t h e H T . I n a d d i t i o n t o i m a g e p o i n t s , w e c o n s i d e r e d g e d i r e c t i o n a s g e o m e t r i c d a t a p r o v i d - i n g a n i m p o r t a n t c l u e f o r e v i d e n c e g a t h e r i n g i n t h e p a r a m e t e r s p a c e . E d g e d i r e c t i o n i n f o r m a t i o n h a s b e e n u s e d s u c c e s s - f u l l y t o r e d u c e t h e c o m p u t a t i o n a l r e q u i r e m e n t s o f t h e H T i n c i r c l e e x t r a c t i o n , c a ' 5 ) T h e g e n e r a l a p p r o a c h i s t o i n c l u d e g r a d i e n t d i r e c t i o n i n f o r m a t i o n i n o r d e r t o c o n s t r a i n t h e p a r a m e t e r s p a c e . H e r e w e s h o w h o w t h e p a r a m e t r i c p o l a r r e p r e s e n t a t i o n c a n b e u s e d t o c o m - b i n e e d g e p o i n t s a n d g r a d i e n t d i r e c t i o n i n f o r m a t i o n i n o r d e r t o e s t a b l i s h a n e x p l i c i t a n a l y t i c d e s c r i p t i o n o f t h e m a p p i n g s b e t w e e n t h e i m a g e a n d p a r a m e t e r s p a c e s , w h i c h o n l y i n v o l v e a s u b - s e t o f t h e c o m p l e t e p a r a m e t e r s e t . W e e x t e n d t h e i d e a s o f c i r c l e p a r a m e t e r d e c o m p o - s i t i o n t o e l l i p s e s b y c o m b i n i n g t h e p a r a - m e t r i c p o l a r f o r m w i t h t h e f i r s t - a n d s e c o n d - o r d e r d i r e c t i o n a l d e r i v a t i v e s . T h i s a l l o w s u s t o o b t a i n t w o i n d e p e n d e n t b i - d i m e n s i o n a l s u b - s p a c e s , e a c h o f w h i c h r e l a t e s t w o e l l i p s e p a r a m e t e r s . A f i n a l h i s t o g r a m a c c u - m u l a t o r i s u s e d t o e v a l u a t e t h e r e m a i n i n g p a r a m e t e r . P r e v i o u s m e t h o d s f o r e l l i p s e e x t r a c t i o n ~ 6 - 1 1 1 h a v e s h o w n t h a t i t i s p o s s i b l e t o r e d u c e t h e d i m e n s i o n s o f t h e p a r a m e t e r s p a c e b y , u s i n g g e o m e t r i c p r o p e r t i e s o f a n e l l i p s e . T h e s e p r o p e r t i e s i n v o l v e g e o m e t r i c c o n - s t r a i n t s b e t w e e n e d g e p o i n t s a n d a r e u s e d t o f i n d e x p r e s s i o n s w h i c h r e l a t e o n l y c h o s e n e l l i p s e p a r a - m e t e r s . T h e g e o m e t r i c c o n s t r a i n t s i n c l u d e d i s t a n c e o r a n g l e r e l a t i o n s h i p s t h a t d e f i n e t h e r e l a t i v e p o s i t i o n b e t w e e n a s e t o f p o i n t s . H e n c e , t h e p a r a m e t e r s o f a n e l l i p s e a r e c o m p u t e d a f t e r s e a r c h i n g f o r e d g e p o i n t s 3 6 9
3 7 0 A . S . A G U A D O e t a l . w h i c h s a t i s f y t h e c o n s t r a i n t s . T h e m a j o r d i f f e r e n c e b e t w e e n p r e v i o u s a p p r o a c h e s a n d o u r a p p r o a c h i s t h e c o n s i d e r a t i o n t h a t t w o e d g e p o i n t s d e f i n e t h e r a t i o b e t w e e n d i r e c t i o n a l d e r i v a t i v e s , o f f i r s t a n d s e c o n d o r d e r , o f t h e p a r a m e t r i c p o l a r f u n c t i o n s o f a n o t h e r p o i n t . T h e m o s t i m p o r t a n t r e s u l t o f t h i s p a p e r i s t h a t t h e c o n s t r a i n t s , w h i c h d e f i n e r e l a t i v e p o s i t i o n s b e - t w e e n p o i n t s ( a s r e q u i r e d b y o t h e r a p p r o a c h e s ) , a r e a v o i d e d b y t a k i n g o n l y t w o p o i n t s o n a n e l l i p s e a n d t h e g r a d i e n t d i r e c t i o n i n f o r m a t i o n . I n c o n t r a s t t o t h e p o l a r r e p r e s e n t a t i o n ~ 9 , 1 0 ) a n d t h e t a n g e n t r e p r e s e n t a t i o n o f c u r v e s , ~ 8 ) t h e p a r a m e t r i c p o l a r r e p r e s e n t a t i o n e x - p r e s s e s , i n a n e x p l i c i t f o r m , t h e r e l a t i o n s h i p b e t w e e n t h e p a r a m e t e r s o f a n e l l i p s e a n d t h e d i r e c t i o n a l d e r i v a - t i v e s . T h i s i s u s e d t o s o l v e a n a l y t i c a l l y t h e e q u a t i o n s w h i c h d e c o m p o s e t h e p a r a m e t e r s p a c e . T h i s p a p e r i s o r g a n i z e d a s f o l l o w s . I n S e c t i o n 2 w e c o n s i d e r t h e p a r a m e t r i c p o l a r r e p r e s e n t a t i o n o f a n e l l i p s e a n d i t s d e r i v a t i v e s . I n S e c t i o n 3 w e p r e s e n t t h e g e n e r a l i z a t i o n o f t h e t w o - p l a n e H T f o r c i r c l e s t o e l l i p s - e s . I t i s s h o w n t h a t t h e u s e o f t h e f i r s t d i r e c t i o n a l d e r i v a t i v e a l o n e d o e s n o t o f f e r a c o m p u t a t i o n a l l y a t - t r a c t i v e r e s u l t , m a k i n g n e c e s s a r y t h e i n c l u s i o n o f t h e s e c o n d d i r e c t i o n a l d e r i v a t i v e i n a n e l l i p s e d e f i n i t i o n . I n S e c t i o n 4 w e s h o w h o w t h i s i n f o r m a t i o n c a n b e c o m - p u t e d f r o m g e o m e t r i c d a t a o n a n i m a g e . S e c t i o n 5 p r e s - e n t s t h e i m p l e m e n t a t i o n a n d e x p e r i m e n t a l r e s u l t s . I n o r d e r t o r e d u c e a c c u m u l a t o r n o i s e f o r c o m p l e x i m a g e s , s o m e c o n s i d e r a t i o n s w h i c h p r e v e n t n u m e r i c a l i m p r e c i - a n d t h e i r d e r i v a t i v e s a r e d e f i n e d b y : x ( O ) = a o + r c o s ( 0 ) , y ( O ) = b o + r s i n ( 0 ) , x ' ( O ) = - r s i n ( 0 ) , y ' ( O ) = r c o s ( 0 ) , ( 1 ) x " ( O ) = - r c o s ( 0 ) , y " ( O ) = - r s i n ( 0 ) , w h e r e 0 ~ ( 0 , 2 n a n d t h e p a r a m e t e r s ( a o , b o ) a r e t h e c o o r d i n a t e s o f t h e c i r c l e ' s c e n t r e w i t h r a d i u s r . I f a c i r c l e i s s c a l e d b y c h o o s i n g d i f f e r e n t v a l u e s o f r i n t h e e x p r e s s i o n s f o r x ( O ) a n d y ( O ) , t h e n t h e c u r v e c o r r e - s p o n d s t o a n e l l i p s e : x ( O ) = a o + a C o s ( O ) , y ( O ) = b o + b s i n ( O ) , ( 2 ) w h e r e a a n d b a r e t h e l e n g t h o f t h e a x i s i n t h e x a n d y d i r e c t i o n s , r e s p e c t i v e l y . A n a d d i t i o n a l p a r a m e t e r p d e f i n e s t h e r o t a t i o n o f t h e e l l i p s e w i t h r e s p e c t t o t h e x a x i s . T h e l o c u s o f a r o t a t e d e l l i p s e i s t h e n d e f i n e d b y ( x p ( O ) , y p ( 0 ) ) : - ( x p ( 0 ) - a o ) , ( y p ( O ) - b o ) = ( x ( 0 ) - a o ) , c o s ( p ) s i n ( p ) ( Y ( O ) - b ° ) - s i n ( p ) c o s ( p ) ' ( 3 ) w h e r e p c ( 0 , 2 n . D e f i n i n g : a ~ , = a c o s ( p ) , b x = - b s i n ( p ) , ( 4 ) a y = a s i n ( p ) , b y = b c o s ( p ) , t h e p o l a r r e p r e s e n t a t i o n o f a r o t a t e d e l l i p s e a n d t h e f i r s t a n d s e c o n d d i r e c t i o n a l d e r i v a t i v e s a r e : x p ( O ) = a o + a ~ c o s ( 0 ) + b x s i n ( 0 ) , x ' p ( O ) = - a x s i n ( 0 ) + b x c o s ( 0 ) , x ' ~ ( O ) = - a ~ c o s ( 0 ) - b x s i n ( 0 ) , y p ( O ) = b o + a r c o s ( 0 ) + b y s i n ( 0 ) , y ' p ( O ) = - a r s i n ( 0 ) + b r c o s ( 0 ) , y ' ~ ( O ) = - a r c o s ( 0 ) - b r s i n ( 0 ) , ( 5 ) s i o n a n d w h i c h a t t e m p t t o a c c u m u l a t e t r u e e v i d e n c e o f t h e e l l i p s e s i n a n i m a g e a r e i n c l u d e d i n t h e i m p l e m e n t a - t i o n . S e c t i o n 6 p r e s e n t s t h e c o n c l u s i o n s . 2 . P A R A M E T R I C P O L A R R E P R E S E N T A T I O N O F A N E L L I P S E T h e m o s t d i r e c t d e s c r i p t i o n o f a c u r v e i n t h e p l a n e i s a p a r a m e t r i c r e p r e s e n t a t i o n w h e r e t w o f u n c t i o n s , x ( t ) a n d y ( t ) , d e f i n e t h e c o o r d i n a t e s o f p o i n t s i n t h e C a r - t e s i a n s p a c e f o r e a c h v a l u e o f t . T h e p a r a m e t e r i z a t i o n o f a c u r v e c a n b e a c h i e v e d i n d i f f e r e n t w a y s , h e r e w e r e p r e s e n t e l l i p s e s b y e x t e n d i n g t h e p o l a r p a r a m e t e r i z - a t i o n o f c i r c l e s . T h e p o l a r f o r m o f a c i r c l e p a r a m e t e r i z e d b y t h e a n g l e ( 0 ) b e t w e e n t h e x a x i s a n d a p o i n t ( x , y ) i s d e f i n e d b y t h e p o s i t i o n v e c t o r f u n c t i o n z = x ( O ) U ~ + y ( O ) U r , w h e r e U ~ = 0 , 1 , U r = 1 , 0 1 a r e t w o o r t h o g o n a l u n i t v e c t o r s . T h e f i r s t d i r e c t i o n a l d e r i v a t i v e o f a f u n c t i o n ( z ' = x ' U x + y ' U y ) i s d e f i n e d b y t h e d e r i v a t i v e o f t h e v e c t o r - v a l u e d f u n c t i o n w i t h r e s p e c t t o 0 . B y r e p e a t e d d i f f e r e n t i a t i o n w e o b t a i n t h e s e c o n d d i r e c t i o n a l d e - r i v a t i v e ( z " = x " U x + y " U r ) . T h e v a l u e s o f x ( 0 ) , y ( O ) T h e s e e q u a t i o n s d e f i n e t h e i m a g e o f a c o n t i n u o u s m a p p i n g f o r t h e i n t e r v a l ( 0 , 2 n o n t o a c u r v e i n t h e p l a n e . E a c h p o i n t c o r r e s p o n d s t o t h e l o c u s o f e n d p o i n t s o f t h e d i f f e r e n t i a b l e v e c t o r - v a l u e d f u n c t i o n z ( 0 ) . T h e s i g n o f b x i s c h o s e n a r b i t r a r i l y w h e n t h e s i g n s o f t h e r o t a t i o n m a t r i x a r e d e f i n e d . T h e s e s i g n s i m p l y t h a t t h r e e o f t h e a x i s p a r a m e t e r s ( a x , a y , b x , b y ) m u s t b e o f o p p o s i t e s i g n t o t h e f o u r t h . T h e g e o m e t r i c i n t e r p r e t a - t i o n o f t h e p a r a m e t e r s c a n b e s e e n i n F i g . 1 . W i t h t h i s r e p r e s e n t a t i o n t h e c o o r d i n a t e s o f a r o t a t e d e l l i p s e a r e d e f i n e d b y t w o e l l i p s e s w i t h o u t r o t a t i o n w h o s e c e n t r e s l i e o n t h e x a n d y a x e s , r e s p e c t i v e l y . T h e s e e l l i p s e s a r e u s e d t o r e l a t e d t h e p a r a m e t e r 0 t o t w o o f t h e a x i s p a r a m e t e r s . T h e n t h e r e s u l t s a r e e x t e n d e d f o r a g e n e r a l e l l i p s e d e s c r i p t i o n b y c o n s i d e r i n g t h e r o t a t i o n . F o r s i m p l i c i t y , x p ( 0 ) a n d y p ( 0 ) w i l l n o w b e d e n o t e d a s x a n d y . T h e p o l a r r e p r e s e n t a t i o n c o n t a i n s s i x p a r a m e t e r s ( a o , b o , a x , a y , b x , b y ) , w h i c h c h a r a c t e r i z e t h e s h a p e o f a n e l l i p s e . 0 i s n o t p a r a m e t e r b e c a u s e i t o n l y a d d r e s s e s a p a r t i c u l a r p o i n t o n t h e l o c u s o f a n e l l i p s e . I n o r d e r t o d e f i n e a n e l l i p s e i t i s o n l y n e c e s s a r y t o s p e c i f y t h e c e n t r e a n d t h r e e o f t h e a x i s p a r a m e t e r s . T h e r e -
P a r a m e t e r s p a c e d e c o m p o s i t i o n 3 7 1 Y , • . b o + a , c o s e + b s s i n e Y 2 = b o + b . s i n e , " % ~ i j x l = a o ÷ a . c o s o Y , = b y s i n e ( x , , y , ) F i g . 1 . D e f i n i t i o n o f e l l i p s e p a r a m e t e r s . m a i n i n g p a r a m e t e r c a n b e c o m p u t e d c o n s i d e r i n g t h e o r t h o g o n a l i t y o f t h e a x e s : a " b = a x b x + a y b y = 0 . ( 6 ) T h e o r i e n t a t i o n , p , a n d t h e a x i s ( a , b ) o f t h e n a t u r a l p a r a m e t e r i z a t i o n o f a n e l l i p s e a r e r e l a t e d t o t h e p o l a r p a r a m e t e r i z a t i o n b y : t a n ( p ) = a ~ , , a x a = x / - ~ + a 2 , b = ~ + b ~ . ( 7 ) 3 . F I R S T D I R E C T I O N A L D E R I V A T I V E O N C I R C L E S A N D E L L I P S E S T h e t w o - p l a n e H T f o r c i r c l e s d e c o m p o s e s t h e t h r e e - d i m e n s i o n a l p a r a m e t e r s p a c e , b y u s i n g e d g e t a n g e n t n o r m a l d i r e c t i o n , t o m a p p o i n t s i n t o t w o a c c u m u l a t o r p l a n e s . I n t h i s s e c t i o n w e c o n s i d e r t h e d i r e c t e x t e n s i o n o f t h e t e c h n i q u e t o e l l i p s e s b y u s i n g t h e p a r a m e t r i c p o l a r f o r m d e f i n e d b y e q u a t i o n ( 6 ) . F i r s t w e s h o w h o w i t i s p o s s i b l e t o o b t a i n a r e p r e s e n - t a t i o n o f a c i r c l e f r o m d i r e c t i o n a l d e r i v a t i v e s o f p o l a r f u n c t i o n s b y i n v o l v i n g t h e e d g e t a n g e n t n o r m a l d i r e c - t i o n c o m p u t e d f r o m a n i m a g e . T h e n , t h i s r e s u l t i s d i r e c t l y g e n e r a l i z e d f o r e l l i p s e s , e s t a b l i s h i n g t h e n e e d f o r u s i n g t h e s e c o n d d i r e c t i o n a l d e r i v a t i v e t o o b t a i n a u s e a b l e d e c o m p o s i t i o n o f t h e p a r a m e t e r s p a c e . I n s e c t i o n f o u r t h e t w o e x p r e s s i o n s o f t h e t w o p l a n e H T f o r e l l i p s e s a r e p r e s e n t e d . 3 . 1 . T w o - p l a n e H T f o r c i r c l e s E d g e d i r e c t i o n i n f o r m a t i o n c o m p u t e d f r o m a n i m - a g e w i l l b e d e n o t e d b y q ~ ' x a n d ~ b ' y , w h i c h c o r r e s p o n d t o t h e t a n g e n t a n d c o t a n g e n t o f t h e a n g l e i n c l i n a t i o n ( q S ) o f t h e t a n g e n t l i n e t o t h e e l l i p s e w i t h t h e p o s i t i v e x a x i s , a s i l l u s t r a t e d i n F i g . 2 . d y d x 4 " x = ~ = t a n ( 4 ~ ) , ~ b ' r = ~ y y = c o t ( 4 ~ ) . ( 8 ) T h e r e l a t i o n s h i p b e t w e e n t h e p o l a r r e p r e s e n t a t i o n o f a c i r c l e i n e q u a t i o n ( 1 ) a n d t h e n o r m a l g r a d i e n t c o m p u t e d f r o m a n i m a g e c a n b e f o u n d t h r o u g h t h e c h a i n r u l e o f d i f f e r e n t i a t i o n . T h e t a n g e n t o f t h e a n g l e o f t h e p o s i t i o n v e c t o r f u n c t i o n z ' i s : d y y ' d O d y = - c o t ( 0 ) , ( 9 ) x ' d x d x d O y ' Z C y d y p o s i t i o n v e c t o r f u n c U o n a n d d e r i v a t i v e s Z = x U x + y U ~ U × = ( 0 , 1 ) Z ' = x ' U x + y ' U s 4 = ( 1 . 0 ) x d e r i v a t i v e s c o m p u t e d l o c a l l y d ~ t a n ~ = ~ - d × c o t ~ = ~ - F i g . 2 . G e o m e t r y o f t h e d e r i v a t i v e s o f a n e l l i p s e . P R 2 9 / 3 - B
3 7 2 A . S . A G U A D O e t a l . t h u s ~ b ~ , = t a n ( q ~ ) = - c o t ( 0 ) , ~ b ' y = c o t ( ~ b ) = - t a n ( 0 ) . ( 1 0 ) I n o r d e r t o o b t a i n a n e x p r e s s i o n f o r x a n d y a s a f u n c t i o n o f ~ b , w e s u b s t i t u t e t h e v a l u e o f c o s ( 0 ) i n e q u a t i o n ( 1 ) w h i c h d e f i n e s x v i a t h e e x p r e s s i o n f o r x ' . H e n c e : N / x ' 2 ( 1 1 ) r = ( x - a o ) 1 + ( x - a o ) - - - - - ~ " S i n c e t h e n X ' 2 r 2 s i n 2 ( 0 ) ( x - a o ) 2 = ~ 5 c o s 2 ( 0 ) - t a n 2 ( 0 ) = ~ b ~ , ( 1 2 ) r = ( x - a o ) ` / 1 + q ~ z . ( 1 3 ) A n a l o g o u s l y , b y u s i n g t h e d e f i n i t i o n o f y a n d y ' i n e q u a t i o n ( 1 ) , w e o b t a i n r = ( y - b o ) x ~ . 1 + q ~ , 2 . ( 1 4 ) T h e n , b a s e d o n e q u a t i o n s ( 1 3 ) a n d ( 1 4 ) i t i s p o s s i b l e t o r e d u c e t h e 3 D a c c u m u l t o r r e q u i r e d f o r c i r c l e e x t r a c - t i o n t o t w o 2 D a c c u m u l a t o r s d e f i n e d b y t h e ( a o , r ) a n d ( b o , r ) p a r a m e t e r s p a c e s . B y c o n s i d e r i n g t h e t r i g o n o m e t r i c i d e n t i t i e s c s c 2 ( ~ b ) - - 1 + c o t 2 ( ~ b ) a n d s e c 2 ( ~ b ) = 1 + t a n 2 ( $ ) i n e q u a t i o n s ( 1 3 ) a n d ( 1 4 ) , t h e r e p r e s e n t a t i o n o f a c i r c l e i n v o l v i n g e d g e . t a n g e n t i n f o r m a t i o n i s p e r p e n d i c u l a r t o i t s p o l a r r e p r e s e n t a t i o n . T h a t i s : x = a o + r s i n ( d p ) , y = b o + r C o s ( d ~ ) . ( 1 5 ) T h i s r e s u l t i s c l e a r s i n c e e q u a t i o n ( 1 0 ) i m p l i e s t h a t t h e a n g l e s 4 ~ a n d 0 a r e r e l a t e d b y $ = 0 + n / 2 . C o n s e - q u e n t l y , c o s ( 0 ) = c o s ( 4 ~ + n / 2 ) = s i n ( q ~ ) a n d s i n 0 = s i n ( ~ b + n / 2 ) = c o s ( q ~ ) . A l t e r n a t i v e l y , e q u a t i o n s ( 1 3 ) a n d ( 1 4 ) c a n b e c o m - b i n e d w i t h e q u a t i o n ( 1 5 ) i n o r d e r t o d e f i n e a c i r c l e e x t r a c t i o n p r o c e s s d e c o m p o s e d i n t o t w o s e q u e n t i a l s t a g e s , w i t h t h e a c c u m u l a t o r s ( a o , b o ) a n d ( r ) . T h e m a p p i n g f o r t h e c i r c l e c e n t r e i s t h e n d e f i n e d b y : y - b o , / 1 + ~ ' } x - - a o ~ = q ~ ' y ' ( 1 6 ) a n d a f t e r a o a n d b o a r e c o m p u t e d , e q u a t i o n s ( 1 3 ) o r ( 1 4 ) c a n b e u s e d t o c o m p u t e t h e r a d i u s r . 3 . 2 . E x t e n s i o n o f t h e t w o - p l a n e H T f r o m c i r c l e s t o e l l i p s e s T h e t w o - p l a n e H T p r e s e n t e d i n t h e p r e v i o u s s e c t i o n c a n b e d i r e c t l y e x t e n d e d t o t h e p o l a r d e f i n i t o n o f a n e l l i p s e . F i r s t , w e s h a l l i n c l u d e t h e i n f o r m a t i o n o f t h e f i r s t d i r e c t i o n a l d e r i v a t i v e o n t h e u n r o t a t e d e l l i p s e o n t h e x a x i s i n F i g . 1 . T h e n t h e r o t a t i o n p a r a m e t e r i s i n c l u d e d t o o b t a i n t h e c o m p l e t e d e f i n i t i o n o f a n e l l i p s e . T h e e x p r e s s i o n s f o r t h e e l l i p s e w i t h o u t r o t a t i o n , c e n t r e d o n t h e x a x i s , a n d i t s f i r s t a n d s e c o n d d i r e c - t i o n a l d e r i v a t i v e s a r e : x l = a o + a x C O S ( 0 ) , Y l = b y s i n ( 0 ) , x ' l = - a x s i n ( 0 ) , y ~ = b y c o s ( 0 ) , ( 1 7 ) x ~ = - a x c o s ( 0 ) , y ~ = - b y s i n ( 0 ) . A n a l o g o u s l y t o e q u a t i o n s ( 1 1 ) a n d ( 1 4 ) : a x = ( x I - a o ) ` / 1 + t a n 2 ( 0 ) , b x = ( Y 2 - b o ) ` / 1 + c o t 2 ( 0 ) • ( 1 8 ) F o r a n e l l i p s e t h e a n g l e 0 a n d ~ b a r e r e l a t e d b y t h e v a l u e o f b / a x . E d g e d i r e c t i o n i n f o r m a t i o n c o m p u t e d f r o m a n i m a g e f o r a n e l l i p s e w i t h o u t r o t a t i o n i s : y ' _ ~ l = _ b y c o t ( O ) ' x ' l a x t a n ( 0 ) " ( 1 9 ) x ' l a x Y ' I b y T h e n t h e e x p r e s s i o n s t h a t i n c l u d e t h e f i r s t d i r e c - t i o n a l d e r i v a t i v e i n t h e d e f i n i t i o n o f a n e l l i p s e a r e o b t a i n e d b y c o m b i n i n g e q u a t i o n s ( 1 8 ) a n d ( 1 9 ) , J x , 1 2 b 2 a x = ( x 1 - - a o ) 1 + , - - 2 - - 2 , Y l a x j 2 y l 2 a r ( 2 0 ) b x = ( Y 2 - b o ) 1 q x ~ 2 b 2 . I f t h e e l l i p s e i s r o t a t e d b y a n a n g l e p t h e v a l u e s o f y ' l / x ' l a n d y ' 2 / x ' 2 c o r r e s p o n d t o t h e t a n g e n t a n d c o t a n - g e n t o f t h e a n g l e ( 0 - p ) ( s e e A p p e n d i x A ) : - a x c k ' y - 1 , a y C ~ , x x ' l _ a y , Y - - £ = - - a x ( 2 1 ) Y ' I a x q ~ , x ~ l + a y q b " y a y a x T h e r e f o r e , e q u a t i o n s ( 2 0 ) f o r a r o t a t e d e l l i p s e b e c o m e : 4 / a x ' C " , + a , l ~ b ~ a 2 , a x = ( X x - - a o ) 1 + l _ a x - - - - ~ a v c k - - - - ~ y j x / - a y e b x = ( Y 2 - b o ) 1 + F a y a x ~ b ~ ' 2 ( 2 2 ) t " ~ " 2 " L a x + a / k x d b x A l t h o u g h w h e n i n c l u d i n g t h e f i r s t d e r i v a t i v e i n t h e d e f i n i t i o n o f a n e l l i p s e w e o b t a i n a d e c o m p o s i t i o n o f t h e p a r a m e t e r s p a c e i n t o t w o f o u r - d i m e n s i o n a l a c c u - m u l a t o r s ( a o , b y , a x , a y ) a n d ( b o , b x , a x , a y ) , t h i s r e s u l t d o e s n o t r e p r e s e n t a u s e a b l e d e c o m p o s i t o n o f t h e p a r a m e t e r s p a c e b e c a u s e t h e d i m e n s i o n s s t i l l i m p l y l a r g e c o m p u t a t i o n a l a n d s t o r a g e r e q u i r e m e n t s . I n o r - d e r t o h a n d l e t h i s , i t i s n e c e s s a r y t o i n c l u d e m o r e i n f o r m a t i o n w i t h i n t h e p o l a r d e f i n i t i o n o f a n e l l i p s e . 4 . T W O P L A N E H T F O R E L L 1 P S E S I n t h i s s e c t i o n w e s h a l l c o n s i d e r t h e i n f o r m a t i o n p r o v i d e d b y t h e s e c o n d d i r e c t i o n a l d e r i v a t i v e o f a n e l l i p s e . T h i s i n f o r m a t i o n w i l l b e u s e d t o d e s c r i b e a n e l l i p s e b y u s i n g f e w e r p a r a m e t e r s .
P a r a m e t e r s p a c e d e c o m p o s i t i o n 3 7 3 4 . 1 . S e c o n d d i r e c t i o n a l d e r i v a t i v e o n a n e l l i p s e I n o r d e r t o o b t a i n a n e x p r e s s i o n w h i c h i n v o l v e s t h e t w o p a r a m e t e r s w h i c h d e f i n e t h e c e n t r e o f a n e l l i p s e , w e f o l l o w e q u a t i o n ( 1 6 ) w h i c h r e l a t e s t h e t w o c e n t r e p a r a m e t e r s o f a c i r c l e . I n t h e c a s e o f a n e l l i p s e d e f i n e d b y e q u a t i o n ( 5 ) t h i s r e l a t o n s h i p b e c o m e s : y - b o = a y c o s ( 0 ) + b y s i n ( 0 ) ( 2 3 ) x - a o a x c o s ( 0 ) + b ~ s i n ( 0 ) " T h i s e x p r e s s i o n i s n o t e q u a l t o t h e a n g l e o f t h e f i r s t d e r i v a t i v e b u t o f t h e s e c o n d d e r i v a t i v e . H e n c e t h e r e l a t i o n s h i p o f t h e p a r a m e t e r s o f t h e c e n t r e o f a n e l l i p s e i s a c h i e v e d b y i n c l u d i n g t h e s e c o n d d i r e c t i o n a l d e r i v a t i v e : y - b o y " q ~ ( 2 4 ) x - - a o x " N o t i c e t h a t t h i s i s a g e n e r a l c a s e o f e q u a t i o n ( 1 6 ) b e c a u s e f o r a c i r c l e ~ b ' y = ~ b ~ ( i s o t r o p y ) . I t i s e a s y t o s h o w t h a t t h i s e q u a t i o n c o m b i n e s t h e g e o m e t r i c a l p r o p e r t i e s o f t w o e l l i p s e p o i n t s a n d t h e i r t a n g e n t s ( s e e F i g . 3 ) , a n d i t h a s b e e n p r e v i o u s l y u s e d t o e s t i m a t e e l l i p s e c e n t r e s . ~ 1 2 ) S i n c e t h e r e l a t i o n s h i p b e t w e n 0 a n d q ~ d e p e n d s o n t h e v a l u e o f b i G , t h e a x i s p a r a m e t e r s c a n n o t b e o b t a i n e d f o l l o w i n g a s u b s t i t u t i o n a s i n e q u a t i o n ( 1 1 ) . N e v e r t h e l e s s , t h e o r t h o g o n a l i t y o f t h e e l l i p s e ' s a x e s c a n b e u s e d t o e l i m i n a t e 0 . B y c o n s i d e r i n g t h e u n r o t a t e d e l l i p s e d e f i n e d i n e q u a t i o n ( 1 7 ) , w e o b t a i n t h e e x p r e s s - i o n s w h i c h d e f i n e t h e t a n g e n t o f t h e a n g l e s o f t h e f i r s t a n d s e c o n d d e r i v a t i v e s : b Y c o t ( 0 ) , " y ' l _ y _ _ L ~ = b ~ t a n ( 0 ) . ( 2 5 ) x ' l a x x ' ~ a x T h e s e e q u a t i o n s c a n b e c o m b i n e d i n o r d e r t o o b t a i n a n e x p r e s s i o n t h a t c o n t a i n s t h e a x i s p a r a m e t e r s o f a n e l l i p s e : y ' ~ y ' ~ b ~ ( 2 6 ) x ' l x ' ~ a 2 " W e g e n e r a l i z e t h i s e q u a t i o n t o i n c l u d e t h e o r i e n t a - t i o n b y m e a n s o f t h e a n g l e s o f t h e d i r e c t i o n a l d e r i v a - y . . / " ~ T × F i g . 3 . G e o m e t r i c a l r e l a t i o n s h i p b e t w e e n t w o p o i n t s o n a n e l l i p s e a n d t h e i r t a n g e n t s . t i v e s c o m p u t e d o n a r o t a t e d e l l i p s e ( A p p e n d i x A ) : 4 " x - a ~ ~ a y a x a x b ~ ( 2 7 ) 1 + a Y G 1 + a Y 4 , : a ~ " a x a x A l t h o u g h t h i s e x p r e s s i o n c o n t a i n s t h r e e a x i s p a r a - m e t e r s i t o n l y r e l a t e s t h e r a t i o b e t w e e n e l l i p s e a x i s p a r a m e t e r s d e f i n e d b y : a r ( 2 8 ) N = b r K = - - , a x a x t h e n e q u a t i o n ( 2 7 ) d e f i n e s a n e x p r e s s i o n f o r a n a c c u - m u l a t o r ( N , K ) a s : ~ b ' x - K ~ : - K = - N Z " ( 2 9 ) 1 + K G 1 + K 4 , " E q u a t i o n s ( 2 4 ) a n d ( 2 9 ) a l l o w t h e c o m p u t a t i o n o f t h e p a r a m e t e r s o f a n e l l i p s e b y u s n g t w o i n d e p e n d e n t a c c u m u l a t o r s , ( a o , b o ) a n d ( K , N ) . A f t e r c o m p u t i n g t h e v a l u e s f o r a o , b o , K a n d N , t h e r e m a i n i n g p a r a m e t e r s o f t h e e l l i p s e w h i c h c o r r e s p o n d s t o t h e v a l u e o f o n e a x i s , c a n b e u s e d t o m a t c h t h e v a l u e s o b t a i n e d f o r ( a o , b o ) w i t h t h e v a l u e s o b t a i n e d f o r ( K , N ) . I n o r d e r t o o b t a i n t h e v a l u e o f a x f r o m t h e v a l u e s o f ( a o , b o , K , N ) w e c o n s i d e r t h e c a s e o f a n e l l i p s e w i t h o u t r o t a t i o n c e n t r e d i n t h e o r i g i n d e f i n e d b y : x o = a c o s ( 0 ) , Y o = b s i n ( 0 ) . ( 3 0 ) D u e t o t h e o r t h o g o n a l i t y o f t h e a x e s w e k n o w t h a t b x = - N a x a n d b y = N G . B y c o n s i d e r i n g e q u a t i o n ( 7 ) w e h a v e : b = N a . ( 3 1 ) S o l v i n g s i n ( O ) f r o m t h e e q u a t i o n w h i c h d e f i n e s x o i n e q u a t i o n ( 3 0 ) w e r e w r i t e Y o a s : Y o = N ~ X 2 o . ( 3 2 ) F o r a g e n e r a l e l l i p s e w e k n o w t h a t a = ~ + a 2 ) w i t h a y = K a x , c o n s e q u e n t l y : / y 2 + _ x 2 N 2 ( 3 3 ) a x = x / S 2 ( 1 + K 2 ) " D u e t o t h e d e f i n i t i o n o f x o a n d Y o t h e s e v a l u e s i n a g e n e r a l e l l i p s e m u s t b e o b t a i n e d b y t r a n s l a t i n g t o t h e o r i g i n a n d b y r o t a t i n g b y - p d e g r e e s . S i n c e t a n ( p ) = a j a x = K , t h e n : 1 K c o s ( p ) ~ , s i n ( p ) = ~ , ( 3 4 ) a n d t h e v a l u e s o f x o a n d Y o a r e d e f i n e d b y : ( x - - a o ) ( y - - b o ) K X o ~ ~ , ( x - a o ) K ( y - - b o ) + - - ( 3 5 ) Y ° - + l + 1
3 7 4 A . S . A G U A D O e t a l . A f t e r a x h a s b e e n c o m p u t e d , t h e o t h e r p a r a m e t e r s c a n b e o b t a i n e d b y : a y = a x t a n ( K ) , b r = a ~ t a n ( N ) . ( 3 6 ) T h e n , b a s e d o n t h e s e c o n d d i r e c t i o n a l d e r i v a t i v e , i t i s p o s s i b l e t o d e c o m p o s e t h e p a r a m e t e r s p a c e i n t o t w o i n d e p e n d e n t a c c u m u l a t o r s w h i c h d e f i n e t h e c e n t r e p a r a m e t e r s ( a o , b o ) a n d a x i s p a r a m e t e r s ( K , N ) , e q u a t i o n s ( 2 4 ) a n d ( 2 9 ) , r e s p e c t i v e l y . A f i n a l h i s t o g r a m a c c u m u l a t o r e q u a t i o n ( 3 3 ) a l l o w s c o m p u t a t i o n o f t h e r e m a i n i n g e l l i p s e p a r a m e t e r . T h e c o m p l e t e d e f i n i t i o n o f t h e e l l i p s e i n p a r a m e t r i c o r n o r m a l f o r m c a n b e o b t a i n e d f o l l o w i n g e q u a t i o n s ( 3 4 ) , ( 3 6 ) a n d ( 7 ) . 4 . 2 . C o m p u t a t i o n o f t h e f i r s t a n d s e c o n d d i r e c t i o n a l d e r i v a t i v e s f r o m a n i m a g e I n t h i s s e c t i o n w e c o n s i d e r t h e c o m p u t a t i o n o f t h e a n g l e o f t h e f i r s t a n d s e c o n d d i r e c t i o n a l d e r i v a t i v e s b y s t u d y i n g i m a g e i n f o r m a t i o n . I t i s i m p o r t a n t t o n o t i c e t h a t t h e r e i s n o r e l a t i o n s h i p b e t w e e n t h e s e c o n d d e - r i v a t i v e c o m p u t e d f r o m a n i m a g e a n d t h e s e c o n d d i r e c t i o n a l d e r i v a t i v e . I t i s n o t p o s s i b l e t o c o m p u t e i n f o r m a t i o n a b o u t d i r e c t i o n a l d e r i v a t i v e s o f h i g h o r - d e r f r o m d e r i v a t i v e s c o m p u t e d f r o m a n i m a g e . H e r e , i n o r d e r t o c o m p u t e t h e a n g l e o f t h e s e c o n d d i r e c t i o n a l d e r i v a t i v e , w e c o n s i d e r t w o p o i n t s o n a n e l l i p s e . W e e s t a b l i s h t h a t t h e r a t i o b e t w e e n s e c o n d d i r e c t i o n a l d e r i v a t i v e s o f p a r a m e t r i c p o l a r f u n c t i o n s i s c o m p l e t e l y d e f i n e d b y t w o p o i n t s o n t h e e l l i p s e a n d t h e i r d e r i v a - t i v e s c o m p u t e d f r o m a n i m a g e . T h e b a s i c i d e a i s t h a t f o r e a c h p a i r o f b o r d e r p o i n t s o n t h e e l l i p s e ( P 1 , P 2 ) , t h e r e e x i s t s . a n o t h e r p o i n t P f o r w h i c h i t i s p o s s i b l e t o c o m p u t e t h e v a l u e s o f t h e a n g l e o f t h e f i r s t a n d s e c o n d d e r i v a t i v e s . T h e r e f o r e , e q u a t i o n s ( 2 4 ) , ( 2 9 ) a n d ( 3 3 ) c a n b e u s e d t o c o m p u t e t h e e l l i p s e p a r a m e t e r s . T h e t a n g e n t l i n e s o f t w o a r b i t r a r y e l l i p s e p o i n t s P ~ a n d P 2 a r e d e f i n e d b y ( s e e F i g . 3 ) : Y I = c ~ ' x ~ x l + b l , Y 2 = ( 9 ' x 2 x 2 + b 2 . ( 3 7 ) B a s e d o n t h e p o l a r p o i n t T , g i v e n b y t h e i n t e r s e c t i o n o f t h e s e l i n e s : Y 2 - ~ , : x 2 - Y l + 4 ~ , ~ x l t X T = C x l - - ( D ' X 2 y l ¢ ' x ~ - y 2 4 ~ x , + 4 ; ~ 4 ; ~ : ( x 2 - x O Y r - ~ b ' ~ - q ~ ' x ~ , ( 3 8 ) a n d t h e m i d d l e p o i n t M , w e d e r i v e t h e r e l a t i o n s h i p b e t w e e n t h e p o i n t s P 1 , P 2 a n d P . S i n c e t h i s r e l a t i o n - s h i p d o e s n o t d e p e n d o n t h e r o t a t i o n a n d p o s i t i o n ( t r a n s l a t i o n ) o f a n e l l i p s e , i t c a n b e o b t a i n e d b y c o n - s i d e r i n g a n e l l i p s e w i t h o u t r o t a t i o n c e n t r e d o n t h e o r i g i n . I n t h i s c a s e t h e p o i n t s a r e d e f i n e d b y : x a = a x C O S ( O a ) , x 2 = a x C O S ( 0 2 ) , X e = a ~ c o s ( O e ) , Y l = b y s i n ( 0 0 , Y 2 = b y s i n ( 0 2 ) , Y e = b y s i n ( 0 e ) . ( 3 9 ) I n o r d e r t o o b t a i n t h e v a l u e o f 0 e , w e c o m p u t e t h e i n t e r s e c t i o n o f t h e l i n e M T w i t h t h e e l l i p s e . T h a t i s : t a n ( 0 r ) = a : , Y M . ( 4 0 ) b y x M B y s u b s t i t u t i o n o f t h e v a l u e s o f Y u a n d x u , d e f i n e d a s t h e a v e r a g e o f t h e c o o r d i n a t e s o f t h e p o i n t s P ~ a n d P z . t a n ( 0 e ) _ a x b y s i n ( 0 0 + b y s i n ( 0 2 ) b r a x C O S ( O 1 ) + a x C O S ( 0 2 ) , ( 4 1 ) a n d t a n ( O r ) = t a n ( ½ ( O 1 + 0 2 ) ) , ( 4 2 ) c o n s e q u e n t l y : 0 e = I ( 0 1 + 0 2 ) . ( 4 3 ) A n e x p r e s s i o n f o r t h e a n g l e o f t h e f i r s t d i r e c t i o n a l d e r i v a t i v e i n P i s o b t a i n e d b y s u b s t i t u t i o n o f t h i s e x p r e s s i o n i n ( 2 5 ) : y - - = _ b y c o t ( O e ) = _ b y c o t ( ½ ( O 1 _ 0 2 ) ) X r a x a x b y c o s ( k ( 0 1 + 0 2 ) ) s i n ( ½ ( O ~ - 0 2 ) ) a x s i n ( l ( 0 1 - 0 2 ) ) s i n ( ½ ( O 2 - 0 1 ) ) = b y ( s i n ( 0 2 ) - s i n ( 0 0 a : , \ c o s ( 0 2 ) - c o s ( 0 1 ) J ' ( 4 4 ) t h e n t h e a n g l e i s : Y ' Y 2 - - Y l - - - . ( 4 5 ) X r X 2 - - X 1 S i m i l a r l y , a n e x p r e s s i o n f o r t h e a n g l e o f t h e s e c o n d d i r e c t i o n a l d e r i v a t i v e i s : y ~ ; _ b y t a n ( 0 v ) , ( 4 6 ) X ~ , a x a n d c o n s i d e r i n g e q u a t i o n ( 4 0 ) : Y ~ ; Y M - = t a n ( 7 ) . ( 4 7 ) X p X M w h e r e ~ , i s t h e a n g l e f r o m t h e e l l i p s e c e n t r e t o t h e p o i n t P . N o t i c e t h a t t h i s r e s u l t i s t r u e f o r a n e l l i p s e c e n t r e d o n t h e o r i g i n . I f t h e c e n t r e o f t h e e l l i p s e i s ( a o , b o ) t h e n : Y M - b o t a n ( y ) . ( 4 8 ) X M - - a 0 S i n c e w e w a n t t o u s e t h i s e q u a t i o n i n a n e x p r e s s i o n t h a t r e l a t e s t h e v a l u e s o f t h e a x e s a n d n o t t h e c e n t r e w e p r e f e r t o w r i t e t h i s a n g l e i n t e r m s o f t h e p o i n t s M a n d T ( s e e F i g . 4 ) . T h u s , t t Y e Y T - - Y M ( 4 9 ) X p X T - - X M B y s u b s t i t u t i o n o f t h e v a l u e s o f M a n d T w e f i n d a s i m p l i f i e d v e r s i o n o f t h i s e q u a t i o n : y ~ , A C + 2 B D ( 5 0 ) x ' , 2 A + B C '
P a r a m e t e r s p a c e d e c o m p o s i t i o n 3 7 5 ( a ) ( ' o ) ( c ) ( d ) ( e ) i a x ( n F i g . 4 . E l l i p s e d e t e c t i o n e x a m p l e o n a s y n t h e t i c e l l i p s e . ( a ) R a w i m a g e ; ( b ) r e s u l t o f t h e e d g e d e t e c t o r o p e r a t o r ; ( c ) r e s u l t e l l i p s e s u p e r i m p o s e d ; ( d ) c e n t r e a c c u m u l a t o r ; ( e ) a x i s r a t i o a c c u m u l a t o r ; ( f ) a x h i s t o g r a m .
3 7 6 A . S . A G U A D O e t a l . w h e r e A = y ~ - y 2 , C = C x , + ¢ ~ , B = x z - x I , D = ¢ ' , o ¢ ~ , r E q u a t i o n s ( 4 5 ) a n d ( 5 0 ) c a n b e u s e d t o c o m p u t e t h e d i r e c t i o n a l i n f o r m a t i o n r e q u i r e d i n t h e p a r a m e t e r s p a c e d e c o m p o s i t i o n p r e s e n t e d i n S e c t i o n 4 . 1 . 5 . I M P L E M E N T A T I O N A N D R E S U L T S I n t h i s s e c t i o n w e p r e s e n t t h e i m p l e m e n t a t i o n a n d r e s u l t s o f a n e l l i p s e d e t e c t i o n a l g o r i t h m f o l l o w i n g t h e s p a c e d e c o m p o s i t i o n a c h i e v e d b y u s i n g d i r e c t i o n a l i n f o r m a t i o n . I t i s i m p o r t a n t t o n o t i c e t h a t t h e e x p r e s - s i o n s p r e v i o u s l y p r e s e n t e d o n l y d e f i n e a v o t i n g r u l e f o r m a p p i n g t h e i m a g e s p a c e i n t o a p a r a m e t e r s p a c e . O u r i m p l e m e n t a t i o n i n c l u d e s c o n s i d e r a t i o n s w h i c h p r e - v e n t b i a s i n t h e c o m p u t e d v a l u e s , a n d w h i c h r e d u c e n o i s e i n t h e a c c u m u l a t o r s c a u s e d b y p a i r i n g p o i n t s f r o m d i f f e r e n t o b j e c t s i n a n i m a g e . I n o r d e r t o i m p l e m e n t e q u a t i o n s ( 2 4 ) a n d ( 2 9 ) i t i s n e c e s s a r y t o d e f i n e t h e s i z e a n d r e s o l u t i o n o f t h e a c c u m u l a t o r s . T h e a c c u m u l a t o r ( a o , b o ) a n d t h e l a s t h i s t o g r a m ( a x ) a r e c o n g r u e n t t o t h e i m a g e s p a c e , t h e r e - f o r e , i f w e e x p e c t t h a t t h e e l l i p s e i s c o m p l e t e l y c o n - t a i n e d i n t h e i m a g e , t h e y a r e b o u n d e d b y t h e i m a g e d i m e n s i o n a n d t h e i r m a x i m u m r e s o l u t i o n i s o n e p i x e l . A s t h e ( N , K ) a c c u m u l a t o r r e l a t e s t w o t a n g e n t s , i t i n v o l v e s a n i n f i n i t e r a n g e o f v a l u e s a n d t h e r e f o r e i t d o e s n o t s u i t t h e H T a p p r o a c h d i r e c t l y . I n o r d e r t o h a n d l e t h e r a n g e o f t h e v a l u e s o f K , N w e b o u n d t h e a c c u m u l a t o r b y s t o r i n g t h e a n g l e s d e f i n e d b y t h e v a l u e s o f a t a n ( K ) a n d a t a n ( N ) . T h i s n e w a c c u - m u l a t o r h a s a s i z e o f n a n d i t s r e s o l u t i o n c a n b e r e l a t e d t o t h e i m a g e d i m e n s i o n s b y c o n s i d e r i n g t h e a c c u r a c y o f a n g l e s a l l o w e d i n t h e d i s c r e t e i r f i p l e m e n t a t i o n . H e r e w e d e f i n e t h e r a n g e f o r a t a n ( k ) a n d a t a n ( N ) a s - - ~ t / 2 , ~ / 2 ) a n d 0 , 7 t ) r e s p e c t i v e l y . W i t h t h i s d e f i n i t i o n K l i e s b e t w e e n - 1 t o 1 , a n d t h e v a l u e o f a y i s c o m p u t e d a s a f r a c t i o n o f t h e v a l u e o f a x . T h i s i s c o n v e n i e n t b e c a u s e s m a l l e r r o r s i n t h e v a l u e o b t a i n e d f o r a ~ , d o n o t c h a n g e t h e e l l i p s e ' s s h a p e s i g n i f i c a n t l y . T h e m a i n s t e p s i n t h e i m p l e m e n t a t i o n a r e : ( 1 ) A p p l i c a t i o n o f a n e d g e d e t e c t o r t o o b t a i n g r a d i - e n t m a g n i t u d e a n d d i r e c t i o n . ( 2 ) F o r p a i r s o f e d g e p o i n t s d e t e c t e d C o m p u t e t h e a n g l e o f d i r e c t i o n a l d e r i v a t i v e s b y u s i n g e q u a t i o n s ( 4 5 ) a n d ( 5 0 ) . I n c r e m e n t c e l l s i n t h e p a r a m e t e r s s p a c e s ( a o , b o ) a n d ( K , N ) a c c o r d i n g t o e q u a t i o n s ( 2 4 ) a n d ( 2 9 ) . T h e c e l l s i n c r e a s e d a r e t h o s e d e f i n e d b y t h e v o t i n g c u r v e s o b t a i n e d v a r y i n g t h e v a l u e s o f a o a n d N . ( 3 ) D e t e c t a n d s t o r e l o c a l m a x i m a f o r e a c h a c c u m u - l a t o r a r r a y . ( 4 ) F o r e a c h s t o r e d v a l u e o f ( a o , b o ) s e l e c t t h e s t o r e d v a l u e ( K , N ) w h i c h p r o d u c e s t h e m a x i m u m v a l u e o f a x c o m p u t e d b y u s n g e q u a t i o n s ( 3 3 ) a n d ( 3 5 ) . ( 5 ) F o r e a c h e l l i p s e d e t e c t e d e a c h p a i r ( a o , b o ) , ( K , N ) c o m p u t e t h e v a l u e o f t h e a x i s l e n g t h u s i n g e q u a t i o n s ( 3 6 ) . T h i s a l g o r i t h m i s t h e o r e t i c a l l y e x a c t a n d i n t h e c a s e o f e d g e d i r e c t i o n o b t a i n e d b y m e a n s o f a m a t h e m a t i c a l e x p r e s s i o n f o r a n e l l i p s e , i t p r o d u c e s a p e r f e c t p e a k i n t h e a c c u m u l a t o r s . T h i s i s t h e r e f o r e e q u i v a l e n t t o t h e r e s u l t o b t a i n e d b y u s i n g a c o n v e n t i o n a l H T . N e v e r t h e - l e s s , f o r d i g i t a l i m a g e s , n u m e r i c a l i m p r e c i s i o n a n d n o i s e c a n c a u s e d i s t o r t i o n w i t h i n t h e a c c u m u l a t o r s i n c o m p l e x i m a g e s . I n o r d e r t o a m e l i o r a t e t h i s , w e r e d u c e t h e p o s s i b l e p a i r s o f p o i n t s i n t h e a l g o r i t h m b y t w o p r o c e d u r e s . F i r s t , i n o r d e r t o c o m p u t e a n a c c u r a t e n u m e r i c a l v a l u e o f t h e a n g l e o f d i r e c t i o n a l d e r i ~ , a t i v e s w e m u s t a v o i d p a i r s w h i c h d e f i n e t h e p o i n t s M a n d T w h i c h a r e t o o c l o s e , a s w e l l a s p a i r s o f p o i n t s w h o s e t a n g e n t d i f f e r s b y a s m a l l a m o u n t . S e c o n d , i n o r d e r t o a c c u m u - l a t e t r u e e l l i p s e e v i d e n c e , w e m u s t e n s u r e t h a t e a c h e d g e p o i n t i n a p a i r d e f i n e s t h e s a m e g e o m e t r i c f e a t u r e . T h e f i r s t r e q u i r e m e n t i s a c h i e v e d i m p o s i n g a f i l t e r s t e p t o v e r i f y t h a t p a i r s o f p o i n t s u s e d i n t h e v o t i n g s t e p ( 2 ) d e f i n e a d i s t a n c e b e t w e e n t h e p o i n t s M a n d T t o b e w i t h i n a c e r t a i n r a n g e . T h i s r a n g e c a n b e d e t e r m i n e d a c c o r d i n g t o t h e i m a g e r e s o l u t i o n . T h e s e c o n d c o n - s i d e r a t i o n i s m o r e d i f f i c u l t t o r e a l i z e a n d c a n b e b a s e d o n c o m p l e x a n a l y s i s o f a n i m a g e . H e r e w e u s e t w o s i m p l e i n t u i t i v e i d e a s b a s e d o n d i s t a n c e a n d c o n c a v i t y . W e i m p o s e a d i s t a n c e r e s t r i c t i o n b e t w e e n p a i r e d p o i n t s s i n c e c l o s e r p o i n t s a r e m o r e l i k e l y t o b e l o n g t o t h e s a m e p r i m i t i v e . T h e d e f i n i t i o n o f t h i s d i s t a n c e i s b a s e d o n a t r a d e - o f f b e t w e e n a s m a l l v a l u e w h i c h g i v e s a h i g h p r o b a b i l i t y t h a t e a c h p o i n t i n a s e l e c t e d p a i r b e l o n g s t o t h e s a m e o b j e c t a n d a l a r g e v a l u e w h i c h a l l o w s t h e c o m p u t a t i o n o f a c c u r a t e n u m e r i c a l q u a n t i - t i e s i n t h e a l g o r i t h m . I n a d d i t i o n t o d i s t a n c e , w e c o n s i d e r t h a t a p o i n t o n a n e l l i p s e r e p r e s e n t s a n e x t r e m u m , c o n s e q u e n t l y , p a i r s o f p o i n t s b e l o n g i n g t o t h e s a m e e l l i p s e m u s t b e i n - c l u d e d i n t h e r e g i o n s d e f i n e d a c c o r d i n g t o t h e c o n c a v - i t y o f t h e c u r v e . W e a v o i d c o m p l e x c o m p u t a t i o n s o f c u r v a t u r e a n d s i m p l y c o n s i d e r t h e l i m i t o f t h e r e g i o n o f c o n c a v i t y i n e a c h p o i n t b y t h e l i n e w h o s e s l o p e i s d e f i n e d b y t h e g r a d i e n t d i r e c t i o n c o m p u t e d b y t h e e d g e d e t e c t o r o f s t e p ( 1 ) . I n o r d e r t o e s t i m a t e w h e t h e r t h e r e g i o n o f c o n c a v i t y i s e i t h e r u p o r d o w n t h e l i n e d e f i n e d , w e o b s e r v e t h e s i g n o f t h e l i n e e q u a t i o n w h e n p o i n t s i n a s m a l l w i n d o w a r e e v a l u a t e d . O n c e t h e a p p r o p r i a t e p a i r s f o r t h e i m p l e m e n t a t i o n a l g o r i t h m h a v e b e e n d e f i n e d , i t i s n e c e s s a r y t o s e a r c h f o r p a i r s o f p o i n t s i n o r d e r t o a c c u m u l a t e e v i d e n c e . A s a p a i r o f p o i n t s d e f i n e s a n o t h e r p o i n t o n a n e l l i p s e , i n o r d e r t o a c c u m u l a t e c o m p l e t e e v i d e n c e i t w o u l d b e e n o u g h t o c a r r y o u t s t e p ( 2 ) a s m a n y t i m e s a s t h e n u m b e r o f p o i n t s o n a n i m a g e . N e v e r t h e l e s s , i m a g e n o i s e a n d i m p r e c i s i o n i n t h e c o m p u t e d v a l u e s m a k e i t n e c e s s a r y t o i n c r e a s e t h e n u m b e r o f p o i n t s p e r e d g e t o b e a c c u m u l a t e d . E x p e r i m e n t a l r e s u l t s h a v e b e e n a s s e s s e d b o t h o n s y n t h e t i c a n d r e a l i m a g e s . F i g u r e 4 s h o w s t h e i n f l u e n c e o f t h e e d g e d i r e c t i o n c o m p u t a t i o n i n t h e p e r f o r m a n c e o f t h e H T . D i s c r e t e e d g e c o m p u t a t i o n r e d u c e s r e s o l u - t i o n w h i c h i s m o r e s e v e r e i n t h e a x i s a c c u m u l a t o r . F i n a l l y q u a n t i z e d a c c u m u l a t o r s p r o d u c e a p e a k s p r e a d
分享到:
收藏