logo资料库

Minimum cross entropy thresholding.pdf

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