Parallel architectures for image processing

PARALLEL ARCHITECTURES FOR INAGE PROCESSING

S t a n l e y R. S t e r n b e r g

Environmental Research I n s t i t u t e of Michigan Ann Arbor, Michigan A b s t r a c t - Image p r o c e s s i n g o p e r a t i o n s a r e d e f i n e d which permit image p r o c e s s i n g a l g o r i t h m s t o b e w r i t t e n as a l g e b r a i c e x p r e s s i o n s whose v a r i a b l e s are whole images. Highly p a r a l l e l computing a r c h i t e c t u r e s f o r e v a l u a t i n g t h e s e e x p r e s s i o n s are presented.

y i n t h e plane. A b i n a r y image is normaLly desc r i b e d by a f o r m u l a t i o n which s p e c i f i e s t h e locat i o n of a l l of i t s b l a c k p o i n t s . A b i n a r y image i s f u l l y s p e c i f i e d by t h e s e t of i t s b l a c k p o i n t s .

X,

A b i n a r y image t r a n s f o r m a t i o n i s a r u l e f o r mapping one b i n a r y image i n t o a n o t h e r b i n a r y image. A b i n a r y image o p e r a t i o n i s a r u l e f o r mapping an o r d e r e d p a i r of b i n a r y images i n t o a b i n a r y image. Binary image o p e r a t i o n s combine b i n a r y images.

Conventional computers do n o t r e a d i l y l e n d themselves t o p i c t u r e p r o c e s s i n g . D i g i t a l image manipulation by c o n v e n t i o n a l computer is a c c o m p l i s h e d only a t a tremendous c o s t i n t i m e and conc e p t u a l d i s t r a c t i o n . Computer image p r o c e s s i n g i s t h e a c t i v i t y of modifying a p i c t u r e such t h a t ret r i e v a l of r e l e v a n t p i c t o r i a l l y encoded informat i o n becomes t r i v i a l . Algorithm development f o r image p r o c e s s i n g i s a n a l t e r n a t i n g sequence of i n s p i r e d c r e a t i v e v i s u a l i z a t i o n s of d e s i r e d proc e s s e d r e s u l t s and t h e formal procedures implementing t h e d e s i r e d p r o c e s s on a p a r t i c u l a r image p r o c e s s i n g system. But o u r p r o c e s s of c r e a t i v e v i s u a l i z a t i o n i s of p i c t u r e s as a whole. Implementation of t h e v i s u a l i z e d image m a n i p u l a t i o n by c o n v e n t i o n a l computer r e q u i r e s f r a g m e n t a t i o n o f t h e p i c t o r i a l concept i n t o i n f o r m a t i o n u n i t s matched t o t h e word o r i e n t e d c a p a b i l i t i e s of g e n e r a l purpose machines. Conventional computer image p r o c e s s i n g could b e b r o a d l y c a t e g o r i z e d as manipulation of p i x e l states r a t h e r t h a n p i c t o r i a l content.

Binary image t r a n s f o r m a t i o n s and o p e r a t i o n s are e i t h e r l o g i c a l o r geometric. I f t h e c o l o r of a p o i n t P i n t h e r e s u l t a n t image can b e f o r a u l a t e d from t h e c o l o r s o f p o i n t P i n t h e transformzd o r combining images, t h e n t h e t r a n s f o r m a t i o n o r operat i o n i s l o g i c a l . Otherwise, i t i s geometri:. Geometric o p e r a t i o n s on b i n a r y images add and subtract points vectorially. A point P i n the p l a n e i s t h e sum o r d i f f e r e n c e of t h e p o i n t s (xl, Y,) and (x,, Y,) if P = (xl + x2, yl + Y,) o r P = (xl

-

x,,

y1

-

y,)

respectively.

Complement i s t h e l o g i c a l t r a n s f o r m a t i o n of a b i n a r y image which i n t e r c h a n g e s t h e r o l e s of f o r e ground and background by exchanging t h e c o l o r s b l a c k and w h i t e . R e f l e c t i o n i s t h e geometric t r a n s formation which r e v e r s e s t h e o r i e n t a t i o n of a b i n a r y image by a s s i g n i n g t h e c o l o r b l a c k t o a p o i n t P i n t h e r e f l e c t e d image, i f and o n l y i f t h e p o i n t -P i s b l a c k i n t h e b i n a r y image undergoing r e f l e c t i o n . R e f l e c t i o n of p l a n a r b i n a r y images r o t a t e s them 180 degrees about t h e i r o r i g i n o r t u r n s them u p s i d e down.

The image p r o c e s s i n g approach p r e s e n t e d i n t h i s p a p e r d i f f e r s from c o n v e n t i o n a l methods i n t h a t t h e b a s i c manipulative informational u n i t i s p i c t o r i a l . Image p r o c e s s i n g is t r e a t e d as a comp u t a t i o n i n v o l v i n g images as v a r i a b l e s i n a l g e b r a i c e x p r e s s i o n s . These e x p r e s s i o n s may combine s e v e r a l images through b o t h l o g i c a l and geometric r e l a t i o n s h i p s . F i n a l l y , h i g h l y e f f i c i e n t p a r a l l e l computer a r c h i t e c t u r e s are proposed f o r implementing t h e computation a u t o m a t i c a l l y .

Union and i n t e r s e c t i o n are t h e l o g i c a l operat i o n s on b i n a r y images. A p o i n t i s b l a c k i n t h e union of a p a i r of b i n a r y images, i f and o n l y i f i t is black i n either. A point is black i n the inters e c t i o n of two b i n a r y images, i f and only i f i t i s black i n both.

The b i n a r y image i s t h e fundamental u n i t of p i c t o r i a l i n f o r m a t i o n . A b i n a r y image i s a p i c t u r e which is p a r t i t i o n e d i n t o r e g i o n s of foreground and background. By convention, foreground r e g i o n s are c o l o r e d b l a c k , background r e g i o n s are c o l o r e d w h i t e . A b i n a r y image i n Euclidean twospace i s a n unbounded p l a n a r composition of i n t e r l o c k i n g b l a c k and w h i t e regions.

D i l a t i o n and e r o s i o n are t h e geometric operat i o n s on b i n a r y images. A p o i n t P i s b l a c k i n t h e d i l a t i o n of a n o r d e r e d p a i r of b i n a r y images, i f and o n l y i f t h e r e e x i s t s a b l a c k p o i n t i n t h e f i r s t and a b l a c k p o i n t i n t h e second whose sum i s P. A p o i n t P i s b l a c k i n t h e e r o s i o n of a n o r d e r e d p a i r o f b i n a r y images, i f and o n l y i f f o r e v e r y b l a c k p o i n t i n t h e second t h e r e e x i s t s a b l a c k p o i n t i n t h e f i r s t , such t h a t t h e i r d i f f e r e n c e i s P.

A b i n a r y image f o r m u l a t i o n i s a r u l e f o r a s s i g n i n g t h e c o l o r s b l a c k and w h i t e t o e v e r y p o i n t

CH1515-6/79/0000-0712$00.75 @ 1979 IEEE

712

A

0B

= {p:

byB aA!

! . I. !.

c3--

---+--e

p = a

- b}

i

i

A

I

B

AeB

B

ASB

F i g . 2. I l l u s t r a t i n g t h e f i r s t a l t e r n a t i v e d e f i n i t i o n o f t h e geometric o p e r a t i o n s on b i n a r y images. F i g . 1. I l l u s t r a t i n g t h e d e f i n i t i o n s of t h e geometric o p e r a t i o n s on b i n a r y images.

Complement and r e f l e c t i o n , union, i n t e r s e c t i o n , d i l a t i o n and e r o s i o n are t h e p r i m i t i v e b i n a r y image manipulations on which a complete image p r o c e s s i n g system i n c l u d i n g a formal language and a p r o c e s s o r a r c h i t e c t u r e can b e based. The g e n e r a l u t i l i t y o f t h e s e o p e r a t i o n s , p a r t i c u l a r l y t h e geometric operat i o n s , d i l a t i o n and e r o s i o n , cannot b e o v e r s t a t e d . The obviousness of t h e u t i l i t y of d i l a t i o n and e r o s i o n , as g e n e r a l i z e d image p r o c e s s i n g proced u r e s , depends upon t h e i r i n t e r p r e t a t i o n i n somewhat a l t e r e d b u t e q u i v a l e n t d e f i n i t i o n s w i t h t h o s e p r e v i o u s l y p r e s e n t e d . These a l t e r n a t i v e d e f i n i -

A second a l t e r n a t i v e d e f i n i t i o n of d i l a t i o n and e r o s i o n e x p r e s s e s t h e r e s u l t a n t b i n a r v image i n terms of t h o s e t r a n s l a t i o n s of a second b i n a r y image whose b l a c k r e g i o n s e i t h e r o v e r l a p o r are completely c o n t a i n e d i n t h e b l a c k r e g i o n s of a f i r s t b i n a r y image. A p o i n t P i s b l a c k i n t h e d i l a t i o n of two b i n a r y images, i f and o n l y i f t h e r e e x i s t s a t least one b l a c k p o i n t i n t h e t r a n s l a t i o n of t h e r e f l e c t e d second b i n a r y image t o P which i s a l s o b l a c k i n t h e f i r s t b i n a r y image. A p o i n t P i s b l a c k i n t h e eros i o n of two b i n a r y images, i f and only i f every b l a c k p o i n t i n t h e t r a n s l a t i o n of t h e second b i n a r y image t o P i s a l s o b l a c k i n t h e f i r s t b i n a r y image. A @ B =

tions make use of the concept of binary image

(p: B ! b

p

-

brA}

translation. T r a n s l a t i n g a f i r s t b i n a r y image t o a p o i n t P may b e accomplished by e i t h e r d i l a t i n g t h e f i r s t b i n a r y image w i t h a second b i n a r y image whose foreground c o n t a i n s o n l y a s i n g l e b l a c k p o i n t P o r e r o d i n g t h e f i r s t b i n a r y image w i t h a second b i n a r y image whose o n l y b l a c k p o i n t i s a t -P.

I

A f i r s t a l t e r n a t i v e d e f i n i t i o n f o r t h e geomet r i c o p e r a t i o n s d i l a t i o n and e r o s i o n are express i o n s i n v o l v i n g t r a n s l a t i o n s of a f i r s t b i n a r y i n r age by t h e b l a c k p o i n t s o f a second b i n a r y image. The d i l a t i o n of two b i n a r y images i s t h e union of t r a n s l a t i o n s of t h e f i r s t b i n a r y image by b l a c k p o i n t s of t h e second b i n a r y image. D i l a t i o n i s commutative, t h e r e f o r e , t h e d i l a t i o n of a p a i r of b i n a r y images i s a l s o t h e union of t r a n s l a t i o n of t h e second by t h e b l a c k p o i n t s of t h e f i r s t . The e r o s i o n of two b i n a r y images i s t h e i n t e r s e c t i o n of t r a n s l a t i o n s of t h e f i r s t b i n a r y image by t h e b l a c k p o i n t s of t h e r e f l e c t e d second b i n a r y image. Erosion i s n o t commutative.

A @ B = Z B A

A

I

B

A8 .

I

I

A80

F i g . 3. I l l u s t r a t i n g t h e second a l t e r n a t i v e d e f i n i t i o n of t h e geometric o p e r a t i o n s on b i n a r y images. It is t h e second a l t e r n a t i v e d e f i n i t i o n of t h e geometric o p e r a t i o n s d i l a t i o n and e r o s i o n which are most s u g g e s t i v e o f t h e i r u t i l i t y . The f i r s t b i n a r y image of a p a i r e d r e l a t i o n s h i p i s c o n s i d e r e d t o b e t h e image undergoing a n a l y s i s , c a l l e d t h e a c t i v e image. The second b i n a r y image of t h e p a i r e d relat i o n s h i p i s t h e image t o which t h e a c t i v e image

0b

713

t r a n s l a t i o n s of t h e a c t i v e image by t h e b l a c l c p o i n t s of t h e r e f e r e n c e image. The eroded a c t i v e iinage is computed by i t e r a t i v e l y forming t h e i n t e r s e c t i o n of i t s t r a n s l a t i o n s by t h e b l a c k p o i n t s of t h e rer l e c t e d r e f e r e n c e image.

w i l l be compared, c a l l e d t h e r e f e r e n c e image. The b a s i s of comparison i s o v e r l a p p i n g o r containment of t h e r e f e r e n c e image foreground w i t h r e s p e c t t o t h e a c t i v e image foreground. The r e f e r e n c e image s e r v e s a s a probe, l a b e l l i n g t h e r e s u l t a n t o u t p u t image b l a c k a t t h o s e p o i n t s where, i n t h e c a s e of e r o s i o n , t h e foreground o f t h e probe i s completely c o n t a i n e d i n t h e foreground of t h e a c t i v e image o r , i n t h e c a s e of d i l a t i o n , where t h e foreground of t h e r e f l e c t e d probe o v e r l a p s t h e foreground of t h e a c t i v e image.

An optomechanical model of a p a r a l l e l mechanism f o r computing t h e geometric o p e r a t i o n s on p a i r s of b i n a r y images c o n s i s t s of a r i g i d t r a n s p a r e n t a r m , one end of which s c a n s t h e r e f e r e n c e image w'iile s i m u l t a n e o u s l y s c a n n i n g a shadow mask a t t a c h z d a t i t s o p p o s i t e end. A columnated l i g h t s o u r c e i s s e l e c t i v e l y switched on whenever t h e s c a n n i n g arm e n c o u n t e r s a b l a c k p o i n t i n t h e r e f e r e n c e image. For implementing t h e d i l a t i o n o p e r a t i o n s , t h e shadow mask i s opaque i n background r e g i o n s of t h e a c t i v e image. The a c t i v e image shadow mask i n t e r r u p t s t h e l i g h t f a l l i n g on a n e g a t i v e f i l m whose exposure c h a r a c t e r i s t i c s are determined such t h a t t h e f i l m remains w h i t e o n l y a t t h o s e p o i n t s which remain e n t i r e l y w i t h i n shadow. For implementing t h e e r o s i o n o p e r a t i o n , t h e p r o c e d u r e i s m o d i f i e d by r e f l e c t i n g t h e r e f e r e n c e image, c o n s t r u c t i n g t h e shadow mask such t h a t i t s opaque r e g i o n s correspond t o foreground r e g i o n of t h e a c t i v e image and emp l o y i n g a p o s i t i v e f i l m which remains w h i t e a t o n l y t h o s e p o i n t s which remain e n t i r e l y w i t h i n shadow.

Many f r e q u e n t l y used image p r o c e s s i n g t r a n s f o r m a t i o n s may b e c o n v e n i e n t l y e x p r e s s e d i n terms of sequences of l o g i c a l and geometric o p e r a t i o n s combining t h e image undeygoing a n a l y s i s w i t h s t o r e d o r s p e c i a l l y c o n s t r u c t e d r e f e r e n c e images. The medial a x i s t r a n s f o r m a t i o n , convex h u l l , s i z e d i s c r i m i n a t i o n and t e m p l a t e matching a r e b u t a few of t h e commonly employed image a n a l y s i s p r o c e d u r e s which may b e e x p r e s s e d as a l g e b r a i c f o r m u l a t i o n s i n v o l v i n g l o g i c a l and geometric b i n a r y image relat i o n s h i p s . Nor are t h e l o g i c a l and geometric operations r e s t r i c t e d i n t h e i r u t i l i t y t o planar b i n a r y images. The d e f i n i t i o n s q u i t e n a t u r a l l y e x t e n d t o b i n a r y images i n h i g h e r dimensional s p a c e s and s o t o p l a n a r g r e y - s c a l e images which may be i n t e r p r e t e d a s b i n a r y images i n t h r e e s p a c e . Indeed, a v a r i e t y of edge d e t e c t i o n and n o i s e removal p r o c e s s e s on p l a n a r g r e y - s c a l e images may b e f o r m u l a t e d a s sequences of l o g i c a l and geometric o p e r a t i o n s on t h r e e dimensional b i n a r y images.

E

I I I

I

Fig. 4 . An example o f a template matching a l g o r i t h m . The l o g i c a l and g e o m e t r i c o p e r a t i o n s on b i n a r y images a r e e a s i l y comprehended as p a i r e d r e l a t i o n s h i p s between whole images r a t h e r t h a n manipulat i o n s of i n d i v i d u a l p i x e l s . S u c c e s s f u l employment of t h e s e o p e r a t i o n s i n image p r o c e s s i n g systems would s e e m t o r e q u i r e t h a t t h e i r implementation i n hardware p e r m i t s programming by s p e c i f y i n g t h e images and r e l a t i o n s h i p s i n v o l v e d w i t h o u t t h e need t o microprogram a t a p i x e l l e v e l . Machine a r c h i t e c t u r e s s p e c i f i c a l l y d e s i g n e d f o r computing t h e l o g i c a l and g e o m e t r i c o p e r a t i o n s are h i g h l y p a r a l l e l s t r u c t u r e s which e f f i c i e n t l y minimize t h e t i m e and c o n c e p t u a l d i s t r a c t i o n i m p l i c i t i n modelling p a r a l l e l p r o c e s s e s on s e q u e n t i a l machines.

Fig. 5. Optomechanical model of a d e v i c e f o r comp u t i n g t h e g e o m e t r i c o p e r a t i o n s on b i n a r y images.

D i g i t a l e l e c t r o n i c implemectation of g e o m e t r i c and l o g i c a l o p e r a t i o n computations i s s t r o n g l y sugg e s t e d by analogy w i t h t h e optomechanical model b u t r e q u i r e s t h e i n t r o d u c t i o n of t h e concept of a d i g i t a l b i n a r y image. A d i g i t a l b i n a r y image i s t h e i n t e r s e c t i o n of a b i n a r y image w i t h a b i n a r y l a t t i c e . A b i n a r y l a t t i c e i s a b i n a r y image which i s b l a c k o n l y a t p e r i o d i c a l l y spaced p o i n t s i n t h e p l a n e . A b i n a r y l a t t i c e may b e f o r m u l a t e d a s t h e d i l a t i o n o f two n o n c o l i n e a r b i n a r y l a d d e r s , a b i n a r y l a d d e r b e i n g t h e b i n a r y image which i s b l a c k only a t p e r i o d i c a l l y spaced p o i n t s along a s t r a i g h t l i n e , i n c l u d i n g t h e o r i g i n . L o g i c a l and g e o m e t r i c o p e r a t i o n s on p a i r s of d i g i t a l b i n a r y images y i e l d d i g i t a l b i n a r y images.

P a r a l l e l implementation of t h e l o g i c a l operat i o n s on p a i r s of b i n a r y images p r e s e n t s no concept u a l d i f f i c u l t i e s . Computer a r c h i t e c t u r e s f o r p a r a l l e l implementation of t h e g e o m e t r i c o p e r a t i o n s are s u g g e s t e d by t h e f i r s t alternative d e f i n i t i o n of d i l a t i o n and e r o s i o n . The d i l a t i o n o f an a c t i v e b i n a r y image by a r e f e r e n c e b i n a r y image i s corn puted by i t e r a t i v e l y forming t h e union of t h e

A p a r a l l e l e l e c t r o n i c a r c h i t e c t u r e f o r comput i n g g e o m e t r i c o p e r a t i o n s on d i g i t a l b i n a r y images

714

A s i g n i f i c a n t computational s a v i n g s may b e achieved i n c a s e s where t h e d i g i t a l r e f e r e n c e image may be e x p r e s s e d a s t h e i t e r a t e d d i l a t i o n of two o r more d i g i t a l images. In such c a s e s , t h e geometric o p e r a t i o n s can always b e computed i n a t l e a s t a s few s t e p s a s t h e t o t a l number of b l a c k p o i n t s i n t h e d i g i t a l r e f e r e n c e image, and f r e q u e n t l y consid e r a b l y fewer.

c o n s i s t s of two p l a n a r a r r a y s of i d e n t i c a l b i n a r y c e l l s a r r a n g e d on b i n a r y l a t t i c e c e n t e r s . The c e l l s of t h e f i r s t a r r a y s t o r e t h e a c t i v e d i g i t a l b i n a r y image. The c e l l s of t h e second a r r a y rec e i v e s t h e i t e r a t i v e l y computed r e s u l t . For d i l a t i o n , t h e c e l l s of t h e second a r r a y a r e i n i t i a l l y loaded w i t h z e r o s r e p r e s e n t i n g w h i t e p o i n t s ; f o r e r o s i o n , t h e second a r r a y i s i n i t i a l i z e d w i t h ones r e p r e s e n t i n g b l a c k p o i n t s . The b a s i c computational s t e p c o n s i s t s of s h i f t i n g i n p a r a l l e l t h e c o n t e n t s of t h e f i r s t a r r a y by a displacement given a s t h e p o s i t i o n of a p o i n t e r s c a n n i n g an e x t e r n a l l y s t o r e d d i g i t a l r e f e r e n c e image and l o g i c a l l y combining t h e s h i f t e d a c t i v e image w i t h t h e c o n t e n t s of t h e stat i o n a r y second a r r a y , t h e i n t e r m e d i a t e r e s u l t of t h e b a s i c computational s t e p b e i n g s t o r e d i n t h e second a r r a y . D i l a t i o n r e q u i r e s t h a t t h e a c t i v e image b e s h i f t e d t o p o s i t i o n s determined by t h e b l a c k p o i n t s of t h e d i g i t a l r e f e r e n c e image and t h e s h i f t e d a c t i v e image l o g i c a l l y OR'ed w i t h and rep l a c i n g t h e c o n t e n t s of t h e s t a t i o n a r y a r r a y . Erosion s i m i l a r l y r e q u i r e s t h e a c t i v e image t o b e p o s i t i o n e d i n t h e s h i f t i n g a r r a y i n accordance w i t h t h e b l a c k p o i n t s of t h e r e f l e c t e d d i g i t a l r e f e r e n c e image w i t h t h e AND f u n c t i o n d e t e r m i n i n g t h e l o g i c a l r e l a t i o n s h i p between t h e f i r s t and second a r r a y s .

D i l a t i n g a f i r s t b i n a r y image i t e r a t i v e l y by a second and t h e n a t h i r d b i n a r y image i s e q u i v a l e n t t o d i l a t i n g t h e f i r s t b i n a r y image by t h e d i l a t i o n of t h e second w i t h t h e t h i r d b i n a r y image. Eroding a f i r s t b i n a r y image i t e r a t i v e l y by a second and then a t h i r d b i n a r y image i s e q u i v a l e n t t o e r o d i n g t h e f i r s t b i n a r y image by t h e d i l a t i o n of t h e second w i t h t h e t h i r d b i n a r y image.

I

I

I

A

i

C

I

I

ACTIVE IYAOE I N SHlFTlNO ARRAY

i

I

A.0

Bec

I

I

STATIONARY ARRAY CONTAINING RESULT

I

REFERENCE IMAGE

T

Fig. 6 . S h i f t i n g a r r a y a r c h i t e c t u r e f o r computing geometric o p e r a t i o n s on b i n a r y images.

B

A

C

I

I

The t o t a l number o f computational s t e p s req u i r e d t o compute t h e geometric o p e r a t i o n s on p a i r s of d i g i t a l b i n a e images i n s h i f t i n g a r r a y a r c h i t e c t u r e s i s e q u a l t o t h e number of b l a c k p o i n t s i n t h e d i g i t a l r e f e r e n c e image. S i n g l e t i m e s t e p t r a n s l a t i o n of t h e a c t i v e image i n t h e s h i f t i n g a r r a y by a r b i t r a r y displacements r e q u i r e s t h a t e v e r y c e l l of t h e s h i f t i n g a r r a y b e i n t e r c o n n e c t e d t o e v e r y o t h e r c e l l i n t h e a r r a y . The expense of t h i s u n i v e r s a l i n t e r c o n n e c t i o n i s avoided by decomp o s i n g a r b i t r a r y a c t i v e image s h i f t s i n t o a sequence of n e a r e s t neighbor s h i f t s i n v o l v i n g c e l l s which a r e a d j a c e n t l y l o c a t e d i n t h e s h i f t i n g a r r a y . The r e q u i r e d c e l l u l a r i n t e r c o n n e c t i o n s are physic a l l y r e a l i z a b l e i n t h e p l a n e , b u t computation t i m e i s adversely affected, particularly f o r reference images whose b l a c k p o i n t s are w i d e l y d i s j o i n t .

--

-

i

l

A BB

BBC

I

--A-! I

CABB>BC

Fig. 7.

715

-

A0CBBC)

I t e r a t e d d i l a t i o n s and e r o s i o n s of b i n a r y images.

Computational e f f i c i e n c y of e f f e c t i n g t h e dil a t i o n or e r o s i o n of an a c t i v e b i n a r y image by t h e i t e r a t i v e l y a p p l i e d subimages which compose t h e r e f e r e n c e image through mutual d i l a t i o n i s enhanced as t h e decomposition allows f o r more subimages w i t h correspondingly smaller foreground r e g i o n s . Of p r i n c i p a l importance i s t h e q u e s t i o n of whether a given r e f e r e n c e image i s decomposable i n t o subimages whose foregrounds are c o n t a i n a b l e i n b i n a r y images of a r b i t r a r i l y s m a l l foreground e x t e n t , c a l l e d b i n a r y windows. A b i n a r y window is a b i n a r y image whose i n f i n i t e l y i t e r a t e d d i l a t i o n with i t s e l f i s t h e b l a c k unbounded plane. A d i g i t a l b i n a r y window is a b i n a r y image whose i n f i n i t e l y i t e r a t e d d i l a t i o n w i t h i t s e l f is a b i n a r y l a t t i c e . An elemental d i g i t a l b i n a r y window i s a d i g i t a l b i n a r y window c o n s i s t i n g o f b l a c k p o i n t s a t t h e o r i g i n and adjac c a t l a t t i c e p o i n t s . The adjacency r e l a t i o n s h i p may b e formulated i n s e v e r a l ways g i v i n g r i s e t o t h e colemnly implemented Von Neumann f i v e p o i n t elemental window, t h e Golay seven p o i n t elemental window and the Moore n i n e p o i n t window configurations.

-f

i ''

HIwIEuuIII(

I

-9

i.

e-9

GCLAY

Array a r c h i t e c t u r e s f o r image p r o c e s s i n g req u i r e as many c e l l s i n t h e a r r a y as t h e r e ai-e p i x e l s i n t h e d i g i t i z e d image, f r e q u e n t l y r e s u l t i n g i n p r o h i b i t i v e implementation c o s t . The l o g i c a l a r r a y a r c h i t e c t u r e , however, may be modified t o a p i p e l i n e c o n f i g u r a t i o n which i s e f f i c i e n t i n i t s hardware requirements a t t h e c o s t of i n c r e a s e d computation time. The b a s i c r e p l i c a t e d element of t h e p i p e l i n e d p r o c e s s o r i s t h e s t a g e . The f u n c t i o n of t h e s t a g e i s t o perform a d i l a t i o n o r e r o s i o n of t h e e n t i r e a c t i v e image by a subimage of t h e elemental window. Input t o a s t a g e i s a sequence of a c t i v e image b i nary p i x e l s arranged i n r a s t e r scan format. S h i f t r e g i s t e r d e l a y s w i t h i n t h e s t a g e s t o r e contiguous scan l i n e s w h i l e t a p s on t h e s h i f t r e g i s t e r d e l a y s s e q u e n t i a l l y e x t r a c t elemental window configurat i o n s f o r i n p u t t o t h e s t a g e ' s l o g i c module. The l o g i c module implements t h e programmed l o g i c a l f u n c t i o n of i t s s e l e c t e d i n p u t s as a p p r o p r i a t e t o d i l a t i o n o r e r o s i o n by subimages of elemental windows. A t each d i s c r e t e t i m e s t e p , a new a c t i v e image b i n a r y p i x e l i s clocked i n t o t h e s t a g e , w h i l e a t t h e same i n s t a n t , a s i n g l e p i x e l of t h e element a l l y d i l a t e d o r eroded a c t i v e image i s paszed out of t h e s t a g e from t h e l o g i c module. Simultzneously, t h e c o n t e n t s of a l l s h i f t r e g i s t e r delay elements a r e s h i f t e d one element. The elemental wincow conf i g u r a t i o n e x t r a c t e d by t h e s h i f t r e g i s t e r t a p s i s t h u s s e q u e n t i a l l y scanned a c r o s s t h e i n p u t z r r a y i n r a s t e r scan format. D i l a t i o n s and e r o s i o n s of t h e a c t i v e image by subimages on e l e m e n t a l sindow c o n f i g u r a t i o n s a r e computed w i t h i n t h e b a s i c clock s t e p p e r m i t t i n g t h e output of a s t a g e t o occur a t t h e same r a t e as i t s i n p u t , t h u s p e r m i t t i n g t h e s e r i a l c o n c a t e n a t i o n of s t a g e s . Real-time computat i o n of t h e geometric operatons by r e f e r e n c e images decomposed i n t o subimages on elemental windcws i s accomplished by i n i t i a l l y programming s t a g e l o g i c modules i n subsequent s t a g e s and then s e r i a l l y p a s s i n g t h e scanned a c t i v e image through t h e programmed p i p e l i n e .

.

I

i.

Fig. 9 . Logical a r r a y a r c h i t e c t u r e foi: computing geometric o p e r a t i o n s on b i n a r y images.

F.Px

*T

P-. R MOORE

Fig. 8. Elemental d i g i t a l b i n a r y vindow c o n f i g u r a t i o n s . D i l a t i o n and e r o s i o n by d i g i t a l r e f e r e n c e images which have been decomposed i n t o subimages on elemntal window c o n f i g u r a t i o n s a r e r e a d i l y implemented on d i g i t a l e l e c t r o n i c a r c h i t e c t u r e s which are s p e c i f i c a l l y adapted f o r t h a t purpose. The l o g i c a l a r r a y c o n s i s t s of i d e n t i c a l b i n a r y c e l l s arranged i n t h e plane on b i n a r y l a t t i c e c e n t e r s vith p a t t e r n s o f i n t e r c e l l u l a r connections e s t a b l i s h e d about every c e l l as t h e p a t t e r n of p o i n t s i n an e l e m e n t a l window. Each c e l l i n t h e l o g i c a l a r r a y simultaneously e x e c u t e s t h e i d e n t i c a l l o g i c a l f u n c t i o n of i t s s e l e c t e d o u t p u t s , t h e b i nary value of t h e r e s u l t becoming t h e new s t a t e of t h e cell. The p a t t e r n o f s e l e c t e d i n p u t s i s t h e p a t t e r n o f b l a c k p o i n t s i n t h e subimage on t h e elemental vindow, t h e OR f u n c t i o n implementing d i l a t i o n by the subimages of t h e decomposed ref l e c t e d reference image w h i l e t h e AND f u n c t i o n i m p l e m n t s e r o s i o n by t h e subimages of t h e decomposed d i g i t a l r e f e r e n c e .

716

Fig. 10. P i p e l i n e a r c h i t e c t u r e f o r comput i n g geometric o p e r a t i o n s on b i n a r y images.

I n conclusion, a r c h i t e c t u r e s f o r image processi n g cannot be designed independent of t h e image proc e s s i n g o p e r a t i o n s which they a r e intended to implement. Highly p a r a l l e l and conceptually simple arrangements of i d e n t i c a l hardware modules r e p r e s e n t t h e most c o s t e f f i c i e n t approach t o image p r o c e s s i n g a r c h i t e c t u r e s , b u t the p a r t i c u l a r functions those modules implement and t h e methods of t h e i r i n t e r connections a r e e s t a b l i s h e d through a b a s i c unders t a n d i n g of t h e image manipulations which they are intended t o perform. F i n a l l y , computers s p e c i f i c a l l y designed f o r image p r o c e s s i n g may b e c o n s t r u c t e d on t h e b a s i s of t h e s e a r c h i t e c t u r e s through t h e i n c l u s i o n of approp r i a t e i n p u t / o u t p u t and c o n t r o l c i r c u i t r y and t h e a d d i t i o n of image memory f o r s t o r i n g p a r t i a l l y computed r e s u l t s .

717