G r a p h i c s a n d W . N e w m a n I m a g e P r o c e s s i n g E d i t o r U s e o f t h e H o u g h T r a n s f o r m a t i o n T o D e t e c t L i n e s a n d C u r v e s i n P i c t u r e s R i c h a r d O . D u d a a n d P e t e r E . H a r t S t a n f o r d R e s e a r c h I n s t i t u t e , M e n l o P a r k , C a l i f o r n i a H o u g h h a s p r o p o s e d a n i n t e r e s t i n g a n d c o m p u t a t i o n a l l y e f f i c i e n t p r o c e d u r e f o r d e t e c t i n g l i n e s i n p i c t u r e s . T h i s p a p e r p o i n t s o u t t h a t t h e u s e o f a n g l e - r a d i u s r a t h e r t h a n s l o p e - i n t e r c e p t p a r a m e t e r s s i m p l i f i e s t h e c o m p u t a t i o n f u r t h e r . I t a l s o s h o w s h o w t h e m e t h o d c a n b e u s e d f o r m o r e g e n e r a l c u r v e f i t t i n g , a n d g i v e s a l t e r n a t i v e i n t e r p r e t a t i o n s t h a t e x p l a i n t h e s o u r c e o f i t s e f f i c i e n c y . K e y W o r d s a n d P h r a s e s : p i c t u r e p r o c e s s i n g , p a t t e r n r e c o g n i t i o n , l i n e d e t e c t i o n , c u r v e d e t e c t i o n , c o l i n e a r p o i n t s , p o i n t - l i n e t r a n s f o r m a t i o n , H o u g h t r a n s f o r m a t i o n C R C a t e g o r i e s : 3 . 6 3 C o p y r i g h t ( ~ 1 9 7 2 , A s s o c i a t i o n f o r C o m p u t i n g M a c h i n e r y , I n c . G e n e r a l p e r m i s s i o n t o r e p u b l i s h , b u t n o t f o r p r o f i t , a l l o r p a r t o f t h i s m a t e r i a l i s g r a n t e d , p r o v i d e d t h a t r e f e r e n c e i s m a d e t o t h i s p u b l i c a t i o n , t o i t s d a t e o f i s s u e , a n d t o t h e f a c t t h a t r e p r i n t i n g p r i v i l e g e s w e r e g r a n t e d b y p e r m i s s i o n o f t h e A s s o c i a t i o n f o r C o r n p u t i n g M a c h i n e r y . T h i s w o r k w a s s u p p o r t e d b y t h e A d v a n c e d R e s e a r c h P r o j e c t s A g e n c y a n d t h e N a t i o n a l A e r o n a u t i c s a n d S p a c e A d m i n i s t r a t i o n u n d e r C o n t r a c t N A S 1 2 - 2 2 2 1 . 1 1 1 . I n t r o d u c t i o n A r e c u r r i n g p r o b l e m i n c o m p u t e r p i c t u r e p r o c e s s i n g i s t h e d e t e c t i o n o f s t r a i g h t l i n e s i n d i g i t i z e d i m a g e s . I n t h e s i m p l e s t c a s e , t h e p i c t u r e c o n t a i n s a n u m b e r o f d i s - c r e t e , b l a c k f i g u r e p o i n t s l y i n g o n a w h i t e b a c k g r o u n d . T h e p r o b l e m i s t o d e t e c t t h e p r e s e n c e o f g r o u p s o f c o - l i n e a r o r a l m o s t c o l i n e a r f i g u r e p o i n t s . I t i s c l e a r t h a t ~ h e p r o b l e m c a n b e s o l v e d t o a n y d e s i r e d d e g r e e o f a c - c u r a c y b y t e s t i n g t h e l i n e s f o r m e d b y a l l p a i r s o f p o i n t s . H o w e v e r , t h e c o m p u t a t i o n r e q u i r e d f o r n p o i n t s i s a p - p r o x i m a t e l y p r o p o r t i o n a l t o n 2 , a n d m a y b e p r o h i b i t i v e f o r l a r g e n . R o s e n f e l d 1 h a s d e s c r i b e d a n i n g e n i o u s m e t h o d d u e t o H o u g h 2 f o r r e p l a c i n g t h e o r i g i n a l p r o b l e m o f f i n d - i n g c o l i n e a r p o i n t s b y a m a t h e m a t i c a l l y e q u i v a l e n t p r o b - l e m o f f i n d i n g c o n c u r r e n t l i n e s . T h i s m e t h o d i n v o l v e s t r a n s f o r m i n g e a c h o f t h e f i g u r e p o i n t s i n t o a s t r a i g h t l i n e i n a p a r a m e t e r s p a c e . T h e p a r a m e t e r s p a c e i s d e f i n e d b y t h e p a r a m e t r i c r e p r e s e n t a t i o n u s e d t o d e s c r i b e l i n e s i n t h e p i c t u r e p l a n e . H o u g h c h o s e t o u s e t h e f a m i l i a r s l o p e - i n t e r c e p t p a r a m e t e r s , a n d t h u s h i s p a r a m e t e r s p a c e w a s t h e t w o - d i m e n s i o n a l s l o p e - i n t e r c e p t p l a n e . U n f o r t u n a t e l y , b o t h t h e s l o p e a n d t h e i n t e r c e p t a r e u n - b o u n d e d , w h i c h c o m p l i c a t e s t h e a p p l i c a t i o n o f t h e t e c h - n i q u e . I n t h i s n o t e w e s u g g e s t a n a l t e r n a t i v e p a r a m e t e r i - z a t i o n t h a t e l i m i n a t e s t h i s p r o b l e m . W e a l s o g i v e t w o a l - t e r n a t i v e i n t e r p r e t a t i o n s o f H o u g h ' s m e t h o d , o n e o f w h i c h r e v e a l s p l a i n l y t h e s o u r c e o f i t s e f f i c i e n c y . F i n a l l y , w e s h o w h o w t h e m e t h o d c a n b e e x t e n d e d t o f i n d m o r e g e n e r a l c l a s s e s o f c u r v e s i n p i c t u r e s . 2 . F u n d a m e n t a l s T h e s e t o f a l l s t r a i g h t l i n e s i n t h e p i c t u r e p l a n e c o n - s t i t u t e s a t w o - p a r a m e t e r f a m i l y . I f w e f i x a p a r a m e t e r i z a - C o m m u n i c a t i o n s J a n u a r y 1 9 7 2 o f V o l u m e 1 5 t h e A C M N u m b e r 1 

t i o n f o r t h e f a m i l y , t h e n a n a r b i t r a r y s t r a i g h t l i n e c a n b e r e p r e s e n t e d b y a s i n g l e p o i n t i n t h e p a r a m e t e r s p a c e . F o r r e a s o n s t h a t b e c o m e o b v i o u s , w e p r e f e r t h e s o - c a l l e d n o r m a l p a r a m e t e r i z a t i o n . A s i l l u s t r a t e d i o F i g u r e 1 , t h i s p a r a m e t e r i z a t i o n s p e c i f i e s a s t r a i g h t l i n e b y t h e a n g l e 0 o f i t s n o r m a l a n d i t s a l g e b r a i c d i s t a n c e p f r o m t h e o r i g i n . T h e e q u a t i o n o f a l i n e c o r r e s p o n d i n g t o t h i s g e o m e t r y i s x c o s O + y s i n O = p . I f w e r e s t r i c t 0 t o t h e i n t e r v a l 0 , ~ - , t h e n t h e n o r m a l p a r a m e t e r s f o r a l i n e a r e u n i q u e . W i t h t h i s r e s t r i c t i o n , e v e r y l i n e i n t h e x - y p l a n e c o r r e s p o n d s t o a u n i q u e p o i n t i n t h e 0 - o p l a n e . S u p p o s e n o w , t h a t w e h a v e s o m e s e t { ( x a , y a ) , . . . , ( x , , y , ) } o f n f i g u r e p o i n t s a n d w e w a n t t o f i n d a s e t o f s t r a i g h t l i n e s t h a t f i t t h e m . W e t r a n s f o r m t h e p o i n t s ( x ~ , y ~ ) i n t o t h e s i n u s o i d a l c u r v e s i n t h e 0 - p p l a n e d e - f i n e d b y o = x ~ c o s 0 + y ~ s i n 0 . ( 1 ) I t i s e a s y t o s h o w t h a t t h e c u r v e s c o r r e s p o n d i n g t o c o - l i n e a r f i g u r e p o i n t s h a v e a c o m m o n p o i n t o f i n t e r s e c - t i o n . T h i s p o i n t i n t h e 0 - p p l a n e , s a y ( 0 0 , o 0 ) , d e f i n e s t h e l i n e p a s s i n g t h r o u g h t h e c o l i n e a r p o i n t s . T h u s t h e p r o b - l e m o f d e t e c t i n g c o l i n e a r p o i n t s c a n b e c o n v e r t e d t o t h e p r o b l e m o f f i n d i n g c o n c u r r e n t c u r v e s . A d u a l p r o p e r t y o f t h e p o i n t - t o - c u r v e t r a n s f o r m a - t i o n c a n a l s o b e e s t a b l i s h e d . S u p p o s e w e h a v e a s e t { ( 0 1 , o i ) , . . . , ( O k , O k ) } o f p o i n t s i n t h e 0 - o p l a n e , a l l l y i n g o n t h e c u r v e o = X o C O S O + y o s i n O . T h e n r t i s e a s y t o s h o w t h a t a l l t h e s e p o i n t s c o r r e s p o n d t o l i n e s i n t h e x - y p l a n e p a s s i n g t h r o u g h t h e p o i n t ( x 0 , y 0 ) . W e c a n s u m m a r i z e t h e s e i n t e r e s t i n g p r o p e r t i e s o f t h e p o i n t - t o - c u r v e t r a n s f o r m a t i o n a s f o l l o w s : P r o p e r t y 1 . A p o i n t i n t h e p i c t u r e p l a n e c o r r e s p o n d s t o a s i n u s o i d a l c u r v e i n t h e p a r a m e t e r p l a n e . P r o p e r t y 2 . A p o i n t i n t h e p a r a m e t e r p l a n e c o r r e - s p o n d s t o a s t r a i g h t l i n e i n t h e p i c t u r e p l a n e . P r o p e r t y 3 . P o i n t s l y i n g o n t h e s a m e s t r a i g h t l i n e i n t h e p i c t u r e p l a n e c o r r e s p o n d t o c u r v e s t h r o u g h a c o m - m o n p o i n t i n t h e p a r a m e t e r p l a n e . P r o p e r t y 4 . P o i n t s l y i n g o n t h e s a m e c u r v e i n t h e p a r a m e t e r p l a n e c o r r e s p o n d t o l i n e s t h r o u g h t h e s a m e p o i n t i n t h e p i c t u r e p l a n e . I n S e c t i o n 3 w e a p p l y t h e s e r e s u l t s t o t h e p r o b l e m o f d e t e c t i n g c o l i n e a r p o i n t s i n t h e p i c t u r e p l a n e a n d s h o w h o w s i g n i f i c a n t c o m p u t a t i o n a l e c o n o m i e s c a n b e r e a l i z e d i n c e r t a i n s i t u a t i o n s . 3 . A p p l i c a t i o n s a n d A l t e r n a t i v e I n t e r p r e t a t i o n s S u p p o s e w e m a p a l l o f t h e p o i n t s i n t h e p i c t u r e p l a n e i n t o t h e i r c o r r e s p o n d i n g c u r v e s i n t h e p a r a m e t e r p l a n e . I n g e n e r a l , t h e s e n c u r v e s w i l l i n t e r s e c t i n n ( n - - 1 ) / 2 p o i n t s c o r r e s p o n d i n g t o t h e l i n e s b e t w e e n a l l p a i r s o f F i g . 1 . T h e n o r m a l p a r a m e t e r s f o r a l i n e . F i g . 2 . P r o j e c t i o n o f c o l i n e a r p o i n t s o n t o a l i n e . X ( x 2 . Y 2 } 1 2 C o m m u n i c a t i o n s o f t h e A C M J a n u a r y 1 9 7 2 V o l u m e 1 5 N u m b e r 1 

f i g u r e p o i n t s . E x a c t l y c o l i n e a r s u b s e t s o f f i g u r e p o i n t s c a n b e f o u n d , a t l e a s t i n p r i n c i p l e , b y f i n d i n g c o i n c i d e n t p o i n t s o f i n t e r s e c t i o n i n t h e p a r a m e t e r p l a n e . U n f o r - t u n a t e l y , t h i s a p p r o a c h i s e s s e n t i a l l y e x h a u s t i v e , a n d t h e c o m p u t a t i o n r e q u i r e d g r o w s q u a d r a t i c a l l y w i t h t h e n u m - b e r o f p i c t u r e p o i n t s . W h e n i t i s n o t n e c e s s a r y t o d e t e r m i n e t h e l i n e s e x - a c t l y , t h e c o m p u t a t i o n a l b u r d e n c a n b e r e d u c e d c o n - s i d e r a b l y . F o l l o w i n g H o u g h ' s b a s i c p r o p o s a l , w e s p e c i f y t h e a c c e p t a b l e e r r o r i n 0 a n d p a n d q u a n t i z e t h e O - p p l a n e i n t o a q u a d r u l e d g r i d . T h i s q u a n t i z a t i o n c a n b e c o n f i n e d t o t h e r e g i o n 0 _ < 0 < 7 r , - R _ < p _ < R , w h e r e R i s t h e s i z e o f t h e r e t i n a , s i n c e p o i n t s o u t s i d e t h i s r e c t a n g l e c o r r e s p o n d t o l i n e s i n t h e p i c t u r e p l a n e t h a t d o n o t c r o s s t h e r e t i n a . T h e q u a n t i z e d r e g i o n i s t r e a t e d a s a t w o - d i m e n s i o n a l a r r a y o f a c c u m u l a t o r s . F o r e a c h p o i n t ( x ~ , y ~ ) i n t h e p i c t u r e p l a n e , t h e c o r - r e s p o n d i n g c u r v e g i v e n b y ( l ) i s e n t e r e d i n t h e a r r a y b y i n c r e m e n t i n g t h e c o u n t i n e a c h c e l l a l o n g t h e c u r v e . T h u s , a g i v e n c e l l i n t h e t w o - d i m e n s i o n a l a c c u m u l a t o r e v e n t u a l l y r e c o r d s t h e t o t a l n u m b e r o f c u r v e s p a s s i n g t h r o u g h i t . A f t e r a l l f i g u r e p o i n t s h a v e b e e n t r e a t e d , t h e a r r a y i s i n s p e c t e d t o f i n d c e l l s h a v i n g h i g h c o u n t s . I f t h e c o u n t i n a g i v e n c e l l ( 0 i , p i ) i s k , t h e n p r e c i s e l y k f i g u r e p o i n t s l i e ( t o w i t h i n q u a n t i z a t i o n e r r o r ) a l o n g t h e l i n e w h o s e n o r m a l p a r a m e t e r s a r e ( 0 ; , p j ) . A n a l t e r n a t i v e i n t e r p r e t a t i o n o f t h e p o i n t - c u r v e t r a n s - f o r m a t i o n c a n b e o b t a i n e d b y r e c o g n i z i n g t h a t t h e p c o m p u t e d b y ( 1 ) l o c a t e s t h e p r o j e c t i o n o f t h e p o i n t ( x ~ , y ~ ) o n t o a l i n e t h r o u g h t h e o r i g i n w i t h s l o p e a n g l e 0 . T h u s , i f a n u m b e r o f f i g u r e p o i n t s l i e c l o s e t o s o m e l i n e 1 , t h e i r p r o j e c t i o n s o n t o t h e l i n e n o r m a l t o I a r e n e a r l y c o i n c i d e n t ( s e e F i g u r e 2 ) . A g i v e n c o l u m n i n t h e O - p a c c u m u l a t o r a r r a y i s j u s t a h i s t o g r a m f o r t h e s e p r o j e c t i o n s , s o a h i g h c o u n t i n a g i v e n c e l l c l e a r l y c o r r e s p o n d s t o a n e a r l y c o l i n e a r s u b s e t o f f i g u r e p o i n t s . A v a r i a t i o n o f t h i s a p p r o a c h w a s u s e d b y G r i f f i t h 3 t o f i n d l o n g l i n e s i n a p i c t u r e . L e t u s i n v e s t i g a t e h o w t h e c o m p u t a t i o n r e q u i r e d b y t h e a c c u m u l a t o r i m p l e m e n t a t i o n v a r i e s w i t h t h e n u m b e r o f f i g u r e p o i n t s . T o b e m o r e s p e c i f i c a b o u t t h e q u a n t i z a - t i o n , s u p p o s e t h a t w e r e s t r i c t o u r a t t e n t i o n t o d ~ v a l u e s o f 0 u n i f o r m l y s p a c e d i n t h e i n t e r v a l 0 , 7 r ) . S u p p o s e f u r t h e r t h a t t h e p a x i s i n t h e i n t e r v a l - - R , R i s q u a n t i z e d i n t o ~ c e l l s . F o r e a c h f i g u r e p o i n t ( x ~ , y ~ ) , w e u s e ( 1 ) t o c o m p u t e t h e d ~ d i f f e r e n t v a l u e s o f p c o r r e s p o n d i n g t o t h e d l p o s s i b l e v a l u e s o f t h e i n d e p e n d e n t v a r i a b l e 0 . S i n c e t h e r e a r e n f i g u r e p o i n t s , w e n e e d t o c a r r y o u t t h i s c o m p u t a t i o n n d ~ t i m e s . W h e n t h e s e c o m p u t a t i o n s a r e c o m p l e t e , t h e d l d . 2 c e l l s o f t h e t w o - d i m e n s i o n a l a c c u m u l a t o r a r e i n s p e c t e d t o f i n d h i g h c o u n t s . T h u s t h e c o m p u t a t i o n r e q u i r e d g r o w s l i n e a r l y w i t h t h e n u m b e r o f f i g u r e p o i n t s . C l e a r l y , w h e n n i s l a r g e c o m p a r e d t o d l , t h i s a p p r o a c h i s p r e f e r a b l e t o a n e x h a u s t i v e p r o - c e d u r e t h a t r e q u i r e s c o n s i d e r i n g t h e l i n e s b e t w e e n a l l n ( n - 1 ) / 2 p a i r s o f f i g u r e p o i n t s . A n o t h e r a l t e r n a t i v e i n t e r p r e t a t i o n e x p o s e s t h e s o u r c e o f t h i s e f f i c i e n c y . C o n s i d e r a g a i n P r o p e r t y 4 i n S e c t i o n 1 3 2 : P o i n t s l y i n g o n t h e s a m e c u r v e i n t h e O - p p l a n e c o r - r e s p o n d t o l i n e s t h r o u g h t h e s a m e p o i n t i n t h e p i c t u r e p l a n e . W h e n t h e c u r v e c o r r e s p o n d i n g t o f i g u r e p o i n t ( x ~ , y i ) i s " a d d e d " t o t h e a c c u m u l a t o r , w e a r e r e a l l y c o m p u t i n g a n d r e c o r d i n g t h e p a r a m e t e r s o f t h e d : l i n e s i n t h e p i c t u r e p l a n e p a s s i n g t h r o u g h ( x , , y ~ ) , a n d b e c a u s e 0 i s q u a n t i z e d , t h e s e a r e " a l l t h e l i n e s i n t h e p l a n e " p a s s i n g t h r o u g h ( x l , y i ) . S h o u l d a g i v e n p a r a m - e t e r p a i r e v e r r e c u r a s a r e s u l t o f c o m p u t i n g t h e d l l i n e s t h r o u g h s o m e o t h e r f i g u r e p o i n t , t h e r e c u r r e n c e w i l l b e r e f l e c t e d i n a n i n c r e a s e d c o u n t i n t h e a p p r o - p r i a t e a c c u m u l a t o r c e l l . R o u g h l y s p e a k i n g , t h e n , f o r e a c h f i g u r e p o i n t t h e q u a n t i z e d t r a n s f o r m m e t h o d c o n - s i d e r s o n l y t h e s e t o f a l l d ~ l i n e s t h r o u g h t h a t p o i n t , w h e r e a s m o r e e x h a u s t i v e m e t h o d s c o n s i d e r a l l ( n - 1 ) l i n e s b e t w e e n t h e g i v e n p o i n t a n d a l l o t h e r f i g u r e p o i n t s . 4 . E x a m p l e T h e f o l l o w i n g e x a m p l e i l l u s t r a t e s s o m e o f t h e f e a t u r e s o f t h e t r a n s f o r m a p p r o a c h . F i g u r e 3 ( a ) s h o w s a t e l e v i - s i o n m o n i t o r v i e w o f a b o x , a n d F i g u r e 3 ( b ) s h o w s a d i g i t i z e d v e r s i o n o f t h a t v i e w . A s i m p l e d i f f e r e n c i n g o p e r a t i o n l o c a t e s s i g n i f i c a n t i n t e n s i t y c h a n g e s a n d p r o - d u c e s t h e b i n a r y p i c t u r e s h o w n i n F i g u r e 3 ( c ) . T h i s 1 2 0 X 1 2 0 p i c t u r e c o n t a i n s m a n y n e a r l y c o l i n e a r f i g u r e p o i n t s t h a t c a n b e f i t w e l l b y a f e w s t r a i g h t l i n e s . S a m p l i n g 0 a t d ~ = 9 t w e n t y - d e g r e e i n c r e m e n t s i n 0 a n d , q u a n t i z i n g p i n t o d 2 = 8 6 t w o - e l e m e n t c e l l s , w e o b t a i n t h e t w o - d i m e n s i o n a l a c c u m u l a t o r a r r a y s h o w n i n T a b l e I . I f t h e a r r a y e n t r y a t ( 0 0 , p 0 ) i s k 0 , t h e n k 0 f i g u r e p o i n t s l i e o n p a r a l l e l l i n e s f o r w h i c h 0 = 0 0 , a n d p l i e s b e t w e e n p 0 a n d p 0 d - 2 . W h e n m a n y p o i n t s a r e n e a r l y c o l i n e a r , t h e e n t r y f o r t h e l i n e t h a t f i t s t h e m b e s t i s l a r g e . T h e l a r g e s t e n t r y i n T a b l e I o c c u r s a t ( 0 ° , - 5 ) a n d c o r r e s p o n d s t o t h e m i d d l e v e r t i c a l e d g e o f t h e b o x . T h e n i n e c i r c l e d e n t r i e s c o r r e s p o n d t o l o c a l l y m a x i m u m v a l u e s t h a t e x c e e d t h e a r b i t r a r y t h r e s h o l d o f 3 5 . T h e c o r r e s p o n d i n g n i n e g r o u p s o f n e a r l y c o l i n e a r f i g u r e p o i n t s a r e s h o w n i n F i g u r e 3 ( d ) . I n t h i s e x a m p l e , i t h a p p e n s t h a t e v e r y g r o u p c o r r e s p o n d s t o s o m e p h y s - i c a l l y m e a n i n g f u l l i n e i n t h e p i c t u r e . H o w e v e r , t w o s i g n i f i c a n t l i n e s o n t h e t o p o f t h e b o x w e r e n o t f o u n d - - o n e , b e c a u s e i t c o n t a i n e d v e r y f e w p o i n t s , a n d t h e o t h e r , b e c a u s e i t f e l l b e t w e e n t h e l i n e s a t 0 = 8 0 ° a n d 0 = 1 0 0 ° . T h e 2 0 ° a n g u l a r q u a n t i z a t i o n i n t e r v a l w a s c h o s e n t o k e e p t h e a c c u m u l a t o r a r r a y s m a l l . C l e a r l y , w e w e r e f o r t u n a t e t o h a v e f o u n d a s m a n y l i n e s a s w e d i d , a n d a s m a l l e r q u a n t i z a t i o n i n t e r v a l w o u l d h a v e t o b e u s e d i n p r a c t i c e . A f e w r e m a r k s c o n c e r n i n g s o m e l i m i t a t i o n s o f t h e t r a n s f o r m a p p r o a c h a r e i n o r d e r . F i r s t , t h e r e s u l t s a r e s e n s i t i v e t o t h e q u a n t i z a t i o n o f b o t h 0 a n d p . F i n e r q u a n t i z a t i o n g i v e s b e t t e r r e s o l u t i o n , b u t i n c r e a s e s t h e c o m p u t a t i o n t i m e a n d e x p o s e s t h e p r o b l e m o f c l u s t e r i n g e n t r i e s c o r r e s p o n d i n g t o n e a r l y c o l i n e a r p o i n t s . S e c o n d , C o m m u n i c a t i o n s J a n u a r y 1 9 7 2 o f V o l u m e 1 5 t h e A C M N u m b e r 1 

t h e t e c h n i q u e f i n d s c o l i n e a r p o i n t s w i t h o u t r e g a r d t o c o n t i g u i t y . T h u s t h e p o s i t i o n o f a b e s t - f i t l i n e c a n b e d i s t o r t e d b y t h e p r e s e n c e o f u n r e l a t e d f i g u r e p o i n t s i n a n o t h e r p a r t o f t h e p i c t u r e . A r e l a t e d p r o b l e m i s t h a t o f m e a n i n g l e s s g r o u p s o f c o l i n e a r p o i n t s b e i n g d e t e c t e d . I n o u r e x a m p l e , a f a l s e l i n e w o u l d b e d e t e c t e d i f t h e t h r e s h o l d w e r e r e d u c e d f r o m 3 5 t o 2 4 , t h e v a l u e n e e d e d t o d e t e c t t h e t o p l e f t - h a n d e d g e o f t h e b o x . T h e t r a n s f o r m a p p r o a c h d o e s s u c c e s s f u l l y f i n d g r o u p s o f c o l i n e a r o r n e a r l y c o l i n e a r f i g u r e p o i n t s . I f t h e m i n i - m u m s i z e o f a s i g n i f i c a n t g r o u p i s k n o w n , a l l s u c h g r o u p s c a n b e d e t e c t e d . I f a d d i t i o n a l p r o p e r t i e s s u c h a s c o n - t i g u i t y a r e k n o w n , t h e y c a n b e u s e d t o r e j e c t m e a n i n g - l e s s r e s u l t s . I n g e n e r a l , t h e t r a n s f o r m a p p r o a c h s h o u l d b e v i e w e d p r i m a r i l y a s 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 w a y o f a c c o m p l i s h i n g a c o n c e p t u a l l y s i m p l e s t e p i n s c e n e a n a l y s i s . F i g . 3 A n i l l u s t r a t i v e e x a m p l e . l I ( a ) M o n i t o r 5 . E x t e n s i o n s a n d C o n c l u s i o n s T h e t r a n s f o r m m e t h o d c a n b e g e n e r a l i z e d a n d s p e - c i a l i z e d i n s e v e r a l w a y s . W e n o t e i m m e d i a t e l y t h a t a n y p a r a m e t r i z a t i o n o f t h e f a m i l y o f s t r a i g h t l i n e s c a n b e u s e d . A s w e h a v e m e n t i o n e d , H o u g h u s e d t h e s l o p e - i n t e r c e p t p a r a m e t e r i z a t i o n . H o w e v e r , t h i s p a r a m e t e r i z a - t i o n h a s t h e d i s a d v a n t a g e o f b e i n g s e n s i t i v e t o t h e c h o i c e o f c o o r d i n a t e a x e s i n t h e p i c t u r e p l a n e . I f s e v e r a l f i g u r e p o i n t s l i e o n a n e a r l y v e r t i c a l l i n e , f o r e x a m p l e , b o t h t h e s l o p e a n d t h e i n t e r c e p t m a y b e a r b i t r a r i l y l a r g e . T h u s t h e e n t i r e t w o - d i m e n s i o n a l p a r a m e t e r p l a n e m u s t b e c o n s i d e r e d . A s R o s e n f e l d [ 1 ] h a s p o i n t e d o u t , o n e c o u l d d o t h e e n t i r e p r o b l e m t w i c e , i n t e r c h a n g i n g t h e x - a n d y - a x e s , b u t t h i s w o u l d i n t r o d u c e a d d i t i o n a l c o m p l i c a - t i o n s . T h e n o r m a l p a r a m e t r i z a t i o n a v o i d s t h e s e d i s - a d v a n t a g e s , f u n d a m e n t a l l y f o r t h e s a m e r e a s o n s t h a t m a k e i t u s e f u l i n i n t e g r a l g e o m e t r y : I t a l l o w s u s t o p l a c e a n i n v a r i a n t m e a s u r e o n t h e s e t o f a l l s t r a i g h t l i n e s . A n i m p o r t a n t s p e c i a l u s e o f t h e t r a n s f o r m m e t h o d i s t o d e t e c t t h e o c c u r r e n c e o f f i g u r e p o i n t s l y i n g o n a s t r a i g h t l i n e a n d p o s s e s s i n g s o m e s p e c i f i e d p r o p e r t y . F o r e x a m p l e , s u p p o s e w e w a n t t o f i n d w h e t h e r a s i g - n i f i c a n t n u m b e r o f f i g u r e p o i n t s l i e o n a l i n e t h r o u g h t h e p o i n t ( x 0 , y 0 ) i n t h e p i c t u r e p l a n e . A s w e h a v e s e e n f r o m P r o p e r t y 4 , t h e n o r m a l c o o r d i n a t e s o f a n y s u c h l i n e m u s t l i e o n ( o r , i n p r a c t i c e a t l e a s t n e a r ) t h e c u r v e n = x 0 c o s 0 + y 0 s i n 0 . H e n c e , t h e t r a n s f o r m p r o c e s s c a n b e c a r r i e d o u t i n t h e u s u a l w a y , b u t a t t e n t i o n c a n b e r e s t r i c t e d t o t h e r e g i o n o f t h e 0 - p p l a n e n e a r t h i s c u r v e . I f w e f i n d a c e l l w i t h c o u n t k n e a r t h i s c u r v e , t h e n w e a r e a s s u r e d t h a t k f i g u r e p o i n t s l i e o n a l i n e p a s s i n g ( n e a r l y ) t h r o u g h t h e p o i n t ( x 0 , y 0 ) . S i m i l a r l y , s u p p o s e w e a r e i n t e r e s t e d o n l y i n l i n e s h a v i n g a g i v e n d i r e c t i o n , s a y 0 0 . A g a i n , w e c a r r y o u t t h e p r o c e s s i n t h e u s u a l w a y , b u t r e s t r i c t o u r a t t e n t i o n t o a s u b s e t o f t h e 0 - p p l a n e i n t h e v i c i n i t y o f 0 = 0 0 . I t i s c l e a r t h a t t h e g e n e r a l t r a n s f o r m a p p r o a c h c a n b e ( b ) D i g i t i z e d ( c ) G r a d i e n t i i , ( d ) L i n e s 1 4 C o m m u n i c a t i o n s o f t h e A C M J a n u a r y 1 9 7 2 V o l u m e 1 5 N u m b e r 1 

T a b l e I . A c c u m u l a t o r A r r a y f o r F i g u r e 3 ( c ) \ 0 ~ - - ~ 0 : 2 0 : 4 0 : 6 0 : 8 0 ° z o o : 1 2 0 : 1 4 0 : 1 6 0 : 8 5 2 8 3 1 2 8 1 4 4 7 9 2 6 5 7 7 2 8 4 2 7 5 6 6 2 7 3 4 3 3 7 1 2 1 1 4 2 3 6 9 1 4 1 2 4 3 5 6 7 3 2 1 4 2 3 4 6 5 1 1 1 1 2 4 6 3 5 2 2 4 6 1 1 3 9 5 9 4 1 1 1 9 1 8 1 2 5 7 4 3 3 1 0 1 2 3 1 0 1 5 5 5 9 5 4 5 4 5 1 1 1 2 5 3 6 6 4 1 0 1 1 9 1 4 5 1 4 9 4 2 0 2 1 1 1 0 8 4 9 5 6 2 1 0 3 1 1 1 3 8 4 7 8 4 4 4 2 1 3 1 0 1 0 4 5 4 7 1 4 3 1 1 6 8 4 3 4 1 8 2 1 5 I 1 2 1 0 8 4 1 9 1 7 2 1 1 5 2 5 1 8 7 8 3 9 8 2 0 2 1 1 3 2 2 1 1 1 1 7 3 7 1 2 1 7 2 2 1 7 9 1 0 9 1 0 ( 3 ~ 1 4 1 7 1 7 3 8 8 7 9 6 3 5 3 3 3 7 1 6 2 2 2 1 1 0 5 9 9 3 1 3 5 1 1 2 1 2 3 2 3 8 1 1 9 1 0 2 9 1 3 1 8 1 8 2 3 2 0 1 4 1 3 9 9 2 7 7 1 6 1 2 3 0 2 0 2 0 7 9 6 2 5 7 1 8 1 2 3 2 1 9 2 7 8 7 8 2 3 8 1 2 1 1 2 0 1 7 5 ~ 1 1 6 7 2 1 7 1 7 1 2 2 3 8 1 1 1 5 1 1 1 0 1 9 9 1 4 1 2 1 6 7 7 1 4 6 7 1 7 9 1 2 1 2 1 6 6 9 1 6 1 2 7 1 5 8 1 3 1 3 1 1 7 1 0 1 6 1 4 1 0 1 3 1 0 9 1 5 1 1 7 1 0 1 6 1 3 6 ! 2 1 1 1 3 1 4 ( ~ 1 0 1 6 1 3 1 3 1 1 9 1 0 1 0 1 6 1 4 8 9 1 4 2 1 2 2 7 1 0 8 2 2 1 2 Q ~ 6 7 1 2 2 1 5 1 1 1 2 1 5 1 1 2 3 6 1 1 1 4 1 4 3 1 3 1 5 1 5 8 1 8 7 1 1 1 6 1 5 1 1 0 1 4 1 7 1 1 7 8 9 1 0 1 2 o o ~ 0 = 2 0 = 4 0 : 6 0 : 8 0 : 1 0 0 = 1 2 0 ° 1 4 0 : 1 6 0 ° - - 8 5 - - 8 3 - - 8 1 - - 7 9 3 1 - - 7 7 i 3 - - 7 5 - - 7 3 - - 7 1 2 - - 6 9 2 - - 6 7 - - 6 5 1 2 - - 6 3 1 2 - - 6 1 5 - - 5 9 7 2 l 1 - - 5 7 6 2 1 2 - - 5 5 0 I 0 6 l l 4 - - 5 3 1 6 1 3 1 2 1 8 4 1 6 t ~ 1 5 I I 1 5 1 6 6 ~ 5 ~ ( ~ ) 1 5 2 3 I 1 5 ~ 4 9 3 2 1 8 1 1 - 4 7 1 0 1 6 i 1 2 2 1 4 1 6 2 1 9 5 - - 4 5 7 1 7 1 1 1 1 1 6 1 8 4 ~ 2 1 6 - - 4 3 8 1 2 1 4 1 0 1 3 1 7 1 2 1 7 6 - - 4 l 6 7 1 4 1 1 1 4 1 4 7 1 9 1 2 - - 3 9 7 1 0 9 8 1 2 8 1 1 2 0 2 3 - - 3 7 7 7 1 4 8 1 7 9 1 2 1 8 2 4 - - 3 5 8 9 1 7 8 1 0 7 1 0 2 3 2 3 - - 3 3 6 1 2 1 5 8 1 2 9 1 1 2 2 2 6 - - 3 1 5 9 1 9 9 8 1 1 1 6 1 8 1 5 - - 2 9 9 1 0 1 2 9 8 9 1 8 1 8 1 5 - - 2 7 7 1 2 1 0 8 6 9 1 8 1 9 1 9 - - 2 5 5 1 0 8 8 7 7 2 2 9 1 4 - - 2 3 6 I 1 9 9 6 1 1 1 9 1 2 9 - - 2 1 7 1 5 9 7 1 0 1 0 1 6 1 0 1 1 - - 1 9 ~ 1 3 8 1 6 9 1 1 1 7 9 1 0 - - 1 7 7 1 7 9 1 5 7 I 1 1 6 1 4 1 3 - - 1 5 6 1 5 1 0 1 7 8 1 3 1 0 1 4 9 - - 1 3 1 0 1 5 9 1 5 9 1 7 1 1 1 3 1 2 - - 1 1 1 0 1 3 1 0 7 8 1 7 9 1 1 1 5 - - 9 7 1 4 8 7 8 2 3 8 1 2 1 5 - - 7 9 1 5 1 2 7 8 2 1 7 1 3 1 2 ( ~ 1 3 1 5 9 7 1 4 1 0 1 2 1 5 ~ 5 - - 3 2 6 1 4 1 4 6 8 1 2 9 1 1 1 8 - - 1 1 0 1 3 1 8 9 8 8 1 1 1 2 1 5 e x t e n d e d t o c u r v e s o t h e r t h a n s t r a i g h t l i n e s . F o r e x - a m p l e , s u p p o s e w e w a n t a m e t h o d t o d e t e c t c i r c u l a r c o n f i g u r a t i o n s o f f i g u r e p o i n t s . W e c a n c h o o s e 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 f o r t h e f a m i l y o f a l l c i r c l e s ( w i t h i n a r e t i n a ) a n d t r a n s f o r m e a c h f i g u r e p o i n t i n t h e o b v i o u s w a y . I f , a 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 e d e s c r i b e a c i r c l e i n t h e p i c t u r e p l a n e b y ( x - a ) 2 - + - ( y - b ) 2 = c ~ , t h e n a n a r b i t r a r y f i g u r e p o i n t ( x ~ , y ~ ) w i l l b e t r a n s - f o r m e d i n t o a s u r f a c e i n t h e a - b - c p a r a m e t e r s p a c e d e - f i n e d b y ( X i - - a ) 2 - q - ( y i - - b ) ~ = c 2 . i n t h i s e x a m p l e , t h e n , e a c h f i g u r e p o i n t w i l l b e t r a n s - f o r m e d i n t o a r i g h t c i r c u l a r c o n e i n a 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 . I f t h e c o n e s c o r r e s p o n d i n g t o m a n y f i g u r e p o i n t s i n t e r s e c t a t a s i n g l e p o i n t , s a y t h e p o i n t ( a 0 , b 0 , c o ) , t h e n a l l t h e f i g u r e p o i n t s l i e o n t h e c i r c l e d e f i n e d b y t h o s e t h r e e p a r a m e t e r s . A s i n t h e p r e c e d i n g c a s e o f s t r a i g h t l i n e s , n o s a v i n g i s e f f e c t e d i f t h e e n t i r e p r o c e s s i s p e r f o r m e d a n a l y t i c a l l y . H o w e v e r , t h e p r o c e s s c a n b e i m p l e m e n t e d e f f i c i e n t l y b y u s i n g a t h r e e - d i m e n - 1 5 s i o n a l a r r a y o f a c c u m u l a t o r s r e p r e s e n t i n g 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 . I n p r i n c i p l e , t h e n , t h e t r a n s f o r m m e t h o d e x t e n d s t o a r b i t r a r y c u r v e s . W e n e e d o n l y p i c k a c o n v e n i e n t p a r a m - e t e r i z a t i o n f o r t h e f a m i l y o f c u r v e s o f i n t e r e s t a n d t h e n p r o c e e d i n t h e o b v i o u s w a y . A p a r a m e t e r i z a t i o n h a v i n g b o u n d e d p a r a m e t e r s i s o b v i o u s l y p r e f e r a b l e , a l t h o u g h t h i s i s n o t e s s e n t i a l . I t i s m u c h m o r e i m p o r t a n t t o h a v e a s m a l l n u m b e r o f p a r a m e t e r s s i n c e t h e a c c u m u l a t o r i m p l e m e n t a t i o n r e q u i r e s q u a n t i z a t i o n o f t h e e n t i r e p a - r a m e t e r s p a c e a n d t h e c o m p u t a t i o n g r o w n e x p o n e n t i a l l y w i t h t h e n u m b e r o f p a r a m e t e r s . R e c e i v e d N o v e m b e r 1 9 7 0 , r e v i s e d A p r i l 1 9 7 1 R e f e r e n c e s 1 . R o s e n f e l d , A . P i c t u r e P r o c e s s i n g b y C o m p u t e r . A c a d e m i c P r e s s , N e w Y o r k , 1 9 6 9 . 2 . H o u g h , P . V . C . M e t h o d a n d m e a n s f o r r e c o g n i z i n g c o m p l e x p a t t e r n s . U . S . P a t e n t 3 , 0 6 9 , 6 5 4 , D e c . 1 8 , 1 9 6 2 . 3 . G r i f f i t h , A . K . C o m p u t e r r e c o g n i t i o n o f p r i s m a t i c s o l i d s . P h . D . T h . , D e p . o f M a t h . , M I T , J u n e 1 9 7 0 . C o m m u n i c a t i o n s J a n u a r y 1 9 7 2 o f V o l u m e 1 5 t h e A C M N u m b e r l