Edge detection based on hum an visual response
M A L A Y K. K U N D U t a n d S A N K A R K . P A L f
An. algorithm based on the characteristics of the hu m a n visual system is presented by which 11 is possible to select automatically (without human intervention) the thresholds for detecting the significant edges as perceived by human beings. The threshold value changes with the background intensity according to the criterion governed by the characteristic of one of the De Vries—Rose, Weber, and saturated regions. The effect of b a c k g ro u n d size and splitting image (dynamic thresholding), and a provision for reducing the computation time are also included in the study.
The algorithm is found to provide a satisfactory improvement in the performance over the conventional edge detection process for a wide range of input image.
1. Introduction
Visual in f o r m a ti o n is c o n c e n t r a t e d a t p o in ts o f la r g e sp a tia l v a r ia tio n o f light intensity in a p ic tu re. T h e d if fe r e n c e o p e r a t o r s su c h a s g r a d ie n t, R o b e rt g ra d ie n t, Sobel a n d P r e w i tt g r a d ie n ts , a n d l a p l a c i a n ( G o n z a l e z a n d W in tz 1977) give rise to high values at th e p laces w h e r e th e c h a n g e in grey-level o c c u r s . T h e g r e a te r th e sp a tia l variation o f intensity, th e e a s ie r is th e d e t e c tio n o f c h a n g e a n d th e str o n g e r is th e edge intensity. T h r e s h o ld i n g o f th e s p a t i a l difference o f greylevels (g ra d ie n t im age) is o n e of the p o p u la r te c h n iq u e s for s h a r p e n i n g th e edges (i.e. se le c tin g valid o r significant edge points a c c o r d in g to h u m a n p e r c e p t i o n — B u c h s b a u m 1980, B r o w n a n d D e ffe n b a c h e r 1979, N e v a tia 1982). T h e p r o b l e m o f ed g e d e te c tio n t h e r e f o r e boils d o w n t o finding out an a p p r o p r i a t e t h r e s h o l d w h i c h m a y b e global, lo c al, o r d y n a m ic such t h a t if the spatial difference a t a p o i n t e x c e e d s t h a t th re sh o ld , t h e n a n d o nly th e n will it be considered as a valid edge p o in t .
The p r e s e n t w o rk is a n a t t e m p t to m a k e this ta s k a u t o m a t i c by p r o v id in g a n adaptive a l g o r i th m b as e d o n h u m a n p s y c h o -v is u a l p h e n o m e n a . T h e visual in c r e m e n t threshold c u r v e ( B u c h s b a u m 1980) is piecew ise linearly a p p r o x i m a t e d here s u c h t h a t the spatial difference in g re y -lev e l a t a p o in t is t h r e s h o l d e d d ep e n d in g o n its background in te n sity b y o n e o f t h e c r it e r ia in th e D e V rie s-R o se , W e b e r a n d s a t u r a t e d regions.
The a l g o r i th m h a s tw o stages. I n th e first stage, grey t o n e edges are exts a c te d u s in g any spatial difference o p e r a to r . T h e e l im i n a ti o n o f th e u n d e s ir a b le edges based o n ihe human visual r e s p o n s e ( B u c h s b a u m 1980) is th e ta sk of th e s e c o n d stage.
Besides th e se, th e in v e s tig a tio n in th is p a p e r also c o m p r i s e s the following.
(a) stu d y in g th e effect o f a d if fe r e n t b a c k g r o u n d size o n th e edge-detected o u tp u t ; (b) sp littin g th e im ag e in o r d e r t o in v e stig a te th e effect o f d y n a m ic th r e s h o ld in g
( W e z k a 1978) o n edge d e t e c tio n ;
(c) p r o p o s in g a new sp e cia l d if fe re n c e o p e r a to r s e m b e d d e d in to the th re s h o ld in g
p r o c e s s ( s e c o n d s ta g e ) t o a v o i d th e a d d i t i o n a l c o m p u ta t io n in stage one.
T h e r o b u s t n e s s o f t h e a l g o r i t h m s is d e m o n s t r a t e d for various images having u n i m o d a l , b im o d a l, m u l t i m o d a l , a n d a fla t-w id e v a lle y e d histogram , and the perfor
m a n c e s a r e c o m p a r e d w i t h t h e s t a n d a r d t h r e s h o l d i n g technique.
2. E d ge operators and thresh old ing
L e t x mn b e th e g re y -le v e l o f th e (m, «)th p ix e l o f a n M x N -dimensional, L-level im a g e X = [ x m„], fo r m = 1 , 2 , M; n = 1, 2 , N . T h e g radient x'm„ denoting the edge i n t e n s it y a t th e p o i n t (m , n ) m a y b e d e fin e d a s ( H a ll 1979)
, ( | G J + |G 2 |)
" ~
2
w h e r e G 1 a n d G 2 a r e g iv e n b y (2), (3) a n d (4) c o r r e s p o n d i n g to the ordinary gradient, th e R o b e r t g r a d ie n t, a n d t h e P r e w i t t a n d S o b e l g r a d ie n ts .
G i = x mn — x mn + j (la)
( j 2 = X mn X m + l , n
(2 ft)
G i = x mn x m+ln+ 1 (3 a)
^ 2 = X m , n + l X m + l ,n
(3i>)
^ 1 2 + W + 1 ,n+ 1 ^ Xm + 1 ,n Xm + l,n - 1 )
G j = 1
2 + W
( X m - l , n + l + W x m - 1 ,n + x m - l , « - l ) ] ^ ^
- 1 ,n + 1 ~r x m,n + 1 “1“ x m + l,n + 1)
( Xm + 1 ,n — 1 + 1 +
wit h W -= 1 a n d 2 for th e P r e w i t t a n d S o b e l g r a d i e n t s respectively. These are called the
;irsr d iffe ren c e o p e r a to r s . T h e s e c o n d difference o p e r a t o r such as the laplacian can be ex p r e s s e d as
= i ( x m - l ,n + x m+l ,r> — 2 x mn) P 4
^2
= j { X m , n - l + x m , n + l ~2xm„)
f iie s im p le g r a d i e n t a n d t h e R o b e r t g r a d i e n t — (2) a n d (3)— not only respond s tr o n g ly to th e edges b u t a l s o t o t h e is o la te d p o in ts . T h e laplacian does respond tc the ed g e s, b u t it r e s p o n d s m o r e s t r o n g l y to th e c o r n e r s , lines, line ends, and isolated p o in ts . It h a s a z e r o r e s p o n s e t o a li n e a r r a m p b u t it r e s p o n d s s t r o n g l y w h e r e there bJ c a n g e in th e r a te o f c h a n g e o f th e grey-level. D u e to som e smoothing effect, the re w itt a n d S o b e l o p e r a t o r s , o n th e o t h e r h a n d , p o sse ss a b etter noise immunity aW- 8°°u c d g e resp o n se : a d d e d t o th is , th e w e ig h te d a v e r a g e in the Sobel operator—(4)
Vlt ti!* " ~ ~ red u c es to a g r e a t e x te n t th e b l u r r i n g effect of smoothing.
T h e r e a r e o t h e r t e c h n i q u e s s u c h as ( P a l a n d M a j u m d e r 1986) x mn = m a x (Xij) - m i n (x,7)
Q Q
w h ere Q is th e set of p e ls i n t h e 3 x 3 n e i g h b o u r h o o d which measures the spati^
difference u sin g th e c o n n e c tiv e p r o p e r t y s u c h t h a t edg e s c a n a ls o be detec ted B ased on the above c o n c e p t , let u s f o r m u l a t e tw o e d g e - d e te c t io n m e t h o d s using c o n t r a s t, instead of in te n sity , as a p a r a m e t e r o f m e a s u r e m e n t.
Let AC; a n d AC 2 d e n o t e th e c o n t r a s t o f a n o b je c t p e l w i t h resp e c t to its a v e r a g e background in ten sity a n d th e a v e r a g e c o n t r a s t w ith in t h e b a c k g r o u n d itself r e s p e c tively, such th a t
A C i = vm„
4 Cl XM + 25/2 1. Xkl
O'.
( i . j ) e C i , A C \ = 1
( k . I) e Qi 1
4 frXiJ 25/2
e; i(5 c)
(5 d) where Q, a n d Q] a r e th e sets o f n e i g h b o u r i n g pels w ith d i s t a n c e 1 a n d 2 1/2 respectively.
Then x' c a n be d e fin e d as
In the second m e t h o d x .
mn = m a x KjACi - A C 2), 0|
is d e f in e d a s
( 5 e )
x mn - m a x (xy]
Q
m i n ( x y )
Q
m a x (Xjj) - m i n ( x 0 )
Q Q
( 5 / )
The definitions (5 e) a n d (5 / ) give r is e to s o m e p o sitiv e r e s u lt s o n ly w h en th e c o n t r a s t of the object w ith resp e ct to t h e b a c k g r o u n d is significant.
After a p p ly in g th e se o p e r a t o r s o n a n i m a g e X , a n e d g e is d e e m e d to be p r e s e n t at the point (m, n) if exceeds a p r e d e f i n e d th r e s h o l d v a lu e T. T h e general fo rm of 7 is
T = f { x mn. n))
( 6 )
where N mn d e n o te s so m e local p r o p e r t y a t th e p o i n t (m, n) h a v i n g a pixel in ten sity x „.
The th re sh o ld is called ‘g l o b a l ’ if T d e p e n d s o n ly o n x mn. W h e n T d e p e n d s o n b o t h xm„ and N mn, it is called ‘lo c a l’. If T d e p e n d s o n th e c o o r d i n a t e (m, n) m a d d i tio n to x mn and N„„, th e t h r e s h o l d so c o m p u t e d is d e fin e d as d y n a m i c . g o o review on different th r e s h o l d in g te c h n iq u e s h a s b e e n given b y W e z k a ( 1 9 /8 ) . e se ec io n o appropriate th r e s h o l d th e re fo re p o s e s a n i m p o r t a n t p r o b l e m m e ec ing
" V S f J n g sections, w e a r e g o i n g , o p r e s e n t a n a u t o m a t i c procedure b as e d o n h u m a n p s y c h o - v i s u a l lacts. The s e le c tio n is m a e o
both local a n d g lo b a l in f o r m a ti o n a v a i l a b l e f r o m X s u c h t a t o r a P f ’’ e ith e r threshold v alu e a d a p t s w ith its a v e r a g e b a c k g r o u n d in t e n s i y m„ in the K l{Bmny > in th e D e V r i e s - R o s e r e g i o n , K t B mn in th e W e b e r reg to n , o r K 3B mn in saturation re g io n K x a n d K 3 b e i n g p o sitiv e c o n s ta n t s ) .
in g re y n e ss b e tw e e n th e o b je c ts . T h e te rm c o n t r a s t is u s e d to em phasize the difference in il lu m in a n c e o f objects. T h e p e r c e iv e d g re y n e ss o f a surface depends on its local b a c k g r o u n d a n d th e p e r c e iv e d c o n t r a s t r e m a in s c o n s t a n t if the ratios of contrasts b e tw e e n th e o b je c t a n d lo c a l b a c k g r o u n d r e m a in c o n s t a n t (H all 1979).
In p s y c h o p h y s io lo g y , t h e p e r c e iv e d c o n t r a s t C refers to the ratio of the difference in l u m in a n c e o f a n o b je c t B 0 a n d its im m e d i a te s u r r o u n d i n g B s , i.e.
r — ~
B s ~ B s (7)
T h e v isu a l in c r e m e n t t h r e s h o l d ( o r th e j u s t n o ti c e a b le difference) is defined as the a m o u n t o f lig h t AJ3r n e c e s s a r y t o a d d to a visu a l field o f intensity B such th at it can be d is c r i m in a te d fro m a r e f e r e n c e field o f th e sa m e i n t e n s it y B. It therefore gives a limit for a p e r c e iv e a b le c h a n g e in l u m i n a n c e o r in ten sity .
T h e m a j o r p r o b le m s a t l o w in te n s ity level w h ic h a n y im age processing system has to face a r e as follow s ( N e v a t i a 1982):
( a ) d e t e c tio n o f c h a n g e s o c c u r r i n g in a low s t e a d y b u t visible illumination (i.e.
m i n i m u m d e t e c ta b l e c h a n g e ) ; a n d
( b) d e t e c tio n o f th e m e r e p r e s e n c e o r a b s e n c e o f light under dark adapted c o n d i t i o n (i.e. a b s o l u t e v isu a l th re sh o ld ).
A t lo w in te n s ity n e a r t h e a b s o l u t e visua l t h r e s h o l d , th e visual increment threshold AB T is c o n s ta n t . W ith in c r e a s e s in in te n s ity B, A B T conve rges asymptotically to the W e b e r b e h a v io u r , i.e. AB T cc B. T h i s ty p e o f b e h a v i o u r is exhibited in the brightness in c r e m e n ta l th r e s h o l d for w h i t e b r o a d b a n d s p e c tr a a n d m on o c h ro m atic narrow band s p e c tr a ( B u c h s b a u m 1980).
F i g u r e 1 p r e se n ts s u c h a c h a r a c te r is t ic r e s p o n s e in the log A B T - log B plane.
W eber b e h a v i o u r is c h a r a c t e r i z e d b y a u n it s lo p e o f th e curve. The preceding region w ith s lo p e 1/2 is k n o w n as t h e De V r i e s - R o s e region. I t h a s been shown (Buchsbaum 1980) t h a t if th e ce n tre v is u a l p r o c e s s o r b e h a v e s a s a n o p ti m u m probabilistic detector, th e in c r e m e n ta l visual t h r e s h o l d follow s th e s q u a r e - r o o t law, i.e. A B r a i/>'
Figure 1. Increment threshold AB T as a function of reference intensity B.
However, in an a c tu a l case this r u le is fo llo w ed in a sm a ll r e s tr ic te d region ( F ig 1) T h e dashed curve sh o w s the d e v . a t . o n f r o m th e W e b e r la w . T h is d e v i a ti o n ’ (w hich represents a s a t u r a n o n r c g u m ) is n o t u s u a lly ex h ib ite d by t h e r e tin a l cone m e c h a n is m even under \ e r \ high in ten sities b u t c o u l d h a p p e n in v e r y r e stric te d cases
From Fig. 1 it is seen t h a t t h e v a r i a t i o n of lo g A B T a g a in s t log B in th e D e Vries Rose region is slo w e r t h a n t h a t in th e W e b e r r e g io n . In o th e r w o rd s , the discrimination ability in the D e V r i e s - R o s e re g io n is g r e a t e r th a n in th e W e b e r region. 1 he p ossible re a so n for th i s d e t e r i o r a t i o n in d is c r i m in a tio n ability c a n be attributed to Visual n o n -lin e a rity .
Assuming the re sp o n se c u r v e ( Fig. 1) to be piecew ise lin e a r , th e W e b er r e g io n a n d the De Vries R ose reg io n c a n b e r e p r e s e n t e d as
log A B , = lo g ( K XB) = lo g B + lo g ( 8)
log M i , = lo g ( K 2( B ) 1/2) = i lo g B + lo g K 2 (9) respectively. H ere A.', a n d K ■ a r e t h e c o n s t a n t s o f p r o p o r t i o n a l i t y
Furtherm ore, the s a t u r a t i o n w h ic h m i g h t o c c u r e v e n ra re ly , only a t v ery h igh intensities can be a p p r o x i m a t e d a s
lo g A B r = 2 lo g B + log K : ( 10)
K } being a c o n s ta n t.
Therefore, w h en the b r ig h tn e s s v a l u e o f a n o b je ct is h ig h e r ( o r lower) t h a n its surrounding, b a c k g r o u n d , o r r e f e r e n c e in te n s ity B b y a n a m o u n t > A B T, it c o r r e sponds to a p o in t o n o r a b o v e t h e c u r v e (Fig. 1), a n d th e o b je c t will a p p e a r e ith er brighter (or d a r k e r) . In case o f a v a r i a b l e o b je c t a n d b a c k g r o u n d intensity, th e visual system a d a p ts to an a v e r a g e in te n s ity .
F urtherm ore, Fig. 2 sh o w s th e v a r i a t i o n of A B T/ B w ith B. it is seen th a t in th e Weber region, the r a tio A B r / B r e m a i n s fa irly c o n s t a n t a t a b o u t ft % oi its m a x im u m value over a very w ide ra n g e o f its B -v a lu e . I n th e l i te r a t u r e th e valu e of/? is said to be around 0 02.
ABt/B
B ( o r b . u n i t ) ---* -
. . .. * h / r with background intensity B for uniform Figure 2. Variation of contrast sensitivity AB T/ h witn g
background.
It is also m e n tio n e d in th e l i t e r a t u r e ( Z u i d e m a the highly dep en d en t o n the size o f th e b a c k g r o u n d . ‘ ' m ax im u m size of threshold value also increases; th i s v a r i a t i o n c o n tin u e s u p , d j e j h j s the background b e y o n d w hich it b e c o m e s i n d e p e n d e n t o f th e b a c k g r o u n d size.
IS
in d ic a te s t h a t a ia rg e r v a lu e o f A B T will be r e q u ir e d f o r th e values of B com puted over a la r g e r b a c k g r o u n d o r w i n d o w size. So it is e x p e c t e d th a t as the size of the b a c k g r o u n d in c re ase s a s m a l l e r n u m b e r o f ed g e p o i n t s will be detected by the visual system .
4, Adaptive threshold selection
T h e pie ce w ise lin e a r a p p r o x i m a t i o n o f th e v is u a l increm ent threshold curve (Fig. 1) is s h o w n in Fig. 3. H e r e , th e t h r e s h o l d v a l u e s in th e D e V ries-R ose region, th e W e b e r reg io n , a n d th e s a t u r a t i o n re g io n a r e d e f in e d by the linear equations ( 8), (9) a n d (10) respectively. A l t h o u g h th e d e m a r c a t i o n b e tw e e n these regions represented by v a r io u s e q u a tio n s is n o t v e r y s h a r p a n d d efin ite, w e assu m e here for the sake of sim plicity a n d ease o f a n a ly s i s t h a t th e D e V r i e s - R o s e re g io n extends between x x and x 2— Fig. 3 — ( x x c o r r e s p o n d s t o th e a b s o lu te v is u a l th resh o ld ), the W eber region b e tw e e n x 2 a n d x 3, a n d t h e s a t u r a t i o n re g io n b e y o n d x 3 . T h e value of B correspond
in g to lo g B = x,- is a s s u m e d h e r e to b e B Xj, for i = 1, 2, 3. In o th e r words
X; = lo g B x ., i = 1 ,2 , 3 (11)
i— Slope = 2
s a t u r a t i o n
REGION S l o p e = 1 W E B E R R E G I O N
Sl ope >: 0 ! A B S . I T H R E j S H O L D
y~ S l o pe = 1 / 2 ;
D E V R I E S , ' - R O S E REGION
Log B (arb unit)
f igure 3. Increment threshold A B T vs reference intensity B curve (Fig. 1) with linear approxim ation for different regions.
L e t x 0 a n d R, be th e m a x i m u m value o f lo g B a n d B, respectively. Let us assume f u r th e r t h a t
x ; = a ;x 0 , i = l , 2 , 3 fl'2)
a n d
B Xi = ^ B „ i = l , 2 , 3 ( 13)
w h e re
0 < « j < a 2 < a 3 < 1 0 < a\ < ct'2 < a '3 < 1
As m e n t i o n e d in § 1, th e v a l u e o f AB T/ B r e m a in s fairly c o n s ta n t over the entire Weber re g io n w ith a value a p p r o x i m a t e l y e q u a l to fi % o f { A B / B ) m^ , the maximum value of
* — » • * - « ' ^ P o n s e 2 m 4 B 8 ,h c ™ , „ , J JTO1I1* n l n g c n c n l Q K fro m m ^ ^
A , = A / i ' ^ 1
/j 100 U L X ( U )
Now. (Si a n d ( l)| are b o t h sa tisfie d n »h„
write P m ^a 2’ -v2) o f F ig. 3 . T herefore, w e c a n
or
.v2 = log Using ( I I ) for i -
2
( 15)
^ l o g B , , - t o g ( ^ l ) or
(16)
K j = F ( 17)
Similarly, c o n s id e r in g |H> a n d ( 10) a t th e p o i n t ( * 3, y 3) w e h a v e K ,
B
The m inim um v alu es o f th e i n c r e m e n t t h r e s h o l d a r e th e r e f o r e
M i , = a: , ( 8 )» * = (- ? L - (i ( A^ j ^ (B XJ 112; s , a ^ f i > BXl (18 a)
* « * * * * ■ ’ ( i 8 5 )
B 2 J A B S 1
corresponding to (he Dc V r i e s - R o s e , W e b e r , a n d s a t u r a t i o n regions. E q u a tio n (12) defines the m i n im u m a m o u n t o f b r i g h t n e s s level, in th r e e d iffe re n t regions, by w h ic h the intensity of an o b je ct m u s t be g r e a t e r o r less t h a n its b a c k g r o u n d in ten sity B in order to m a ke the o b je ct a p p e a r b r i g h t e r o r d a r k e r (i.e. d e te c ta b le ) . In o th e r w o rd s, for a particular p o in t in a p ic tu re h a v i n g in t e n s it y B P if we h a v e e i th e r
, 55 K 2 w h e n •/, B, ^ B > a', B, (1 9 a) ( « ) ; ' 2
or
A S ^ ATj w h e n ce'3 B, ^ cc'2 B, (19 fc)
B or
A B ^ K 3 w h e n 5 ^ a 3 5 t (19 f)
w ith
A B = \BP — B\ (20)
th e n a n d o n ly th e n c a n it b e c o n s i d e r e d as a d e t e c ta b l e edge point having edge in te n s ity A S.
5. C om p utation o f B mn and (AB/B)max
F i g u r e 4 sh o w s th e flow c h a r t f o r e x tra c tin g v a lid e d g e s of an M x ‘If-dimensional, L-level im a g e X = [ x m„], f o r m = 1, 2 , . . . , M; n = 1, 2 , . . . , N using the above-m en"—
d a p t iv e t h r e s h o l d in g s c h e m e .
P R I N T OUTPUT
I' igure 4. Flow c h a rt for the proposed thresholding algorithm.
2531
U t l S f t 'M J » c c o n s f c ...“ * » * U™ r « « W > o m . F o r a 3 x 3 ™
I £ XIJ +
Here Bmn w h ich d e n o t e s th e h-irVo-r^ j •
“ hc ,lK " ? h M — s i r
^ M d * which «re a, a dis„a™
For a 5 x 5 s i / e o f b a c k g r o u n d B,mn where
; 2(xmn + 5 B')
(22 a)
a~h ^ Q „ c , d e Q\, e, f e Q
»:Jl e Q'2 , i. j e Q
2 2
5 o f * - w i t h
Similarly, for a 7 x 7 w in d o w s iz e f o r a b a c k g r o u n d
S - = l [ v m„ + i ( S ' + B " j ] mn ( 23 f l)
B \ 2 ^ . Xk‘ ' 8(1 O r 2 ^ Xpi
1 ,
8( 13)12 “ Vrs 12( 2 ) 1/2 where
1 TIT!
1
Q'\ gj
k J e Q 3 , p , q e Q ' 3 r . s e Q l , u , v e Q ' i '
whete g , , g ', , g ” arKj £)-" are t h e s e ts o f pels in th e 7 x 7 n e i g h b o u r h o o d o f x m„ w ith the corresponding d ista n c e s 3, ( 1 0 ) 1/2, ( 1 3 ) 1/2 a n d 3 (2 )1/2.
Here x mm d e n o t in g the v a lu e o f A B a t th e (m, n )th p o i n t (difference in in te n sity of x«m with respect to its n e i g h b o u r i n g pixels), c a n be o b t a i n e d from ( l ) - ( 5 b ) corresponding to different s p a tia l e d g e d e t e c tio n (g ra d ie n t) o p e r a to r s ; AB c a n a ls o be calculated from th e o p e r a t o r s (5 e) a n d ( 5 / ) u sin g th e s p a t i a l difference o f p a r a m e t e r s which are a fu n c tio n o f th e in t e n s i t y v a l u e o f th e pels.
It is to be n o te d h ere t h a t t h e i n d i v id u a l te rm s o f (21) - (23) re p re s e n tin g th e average b a c k g r o u n d in ten sity f o r d if f e r e n t w in d o w sizes a l s o a p p e a r in (5 c ) - ( 5 / ) . As a result, no a d d i tio n a l c o m p u t a t i o n w o u l d be r e q u ir e d f o r c o m p u tin g x mn w h en (5c)~(5f) are used.
Finally, for c o m p u tin g th e c o n s t a n t s K (, for i = 1 ,2 , 3 w e c o n s id e r
B t = m a x [ x mn] - m in [ x mJ (24)
a n d
, A B X
| = m a x ■^mn
max _ mn _5
m = 1, 2 a n d n = 1 ,2
H e r e , B, h a s b ee n t a k e n t o b e e q u a l to th e d y n a m i c ran g e of the input image.
A s s h o w n in Fig. 4 th e t a s k o f th r e s h o l d in g h a s tw o stages. In the first stage, each pixel in te n s ity x mn is c h o s e n , o n th e b a sis o f its lo c a l in f o rm a tio n (namely, background in te n s ity B mn), to satisfy t h e r e q u i r e m e n t in o n e o f th e th r e e regions. The second stage c o n s ists o f c h e ck in g w h e t h e r x'm„ satisfies its resp e c tiv e c r i t e r i o n ~ ( 19). If that c o n d i t i o n is satisfied, x mn is t h e n tr e a te d as a v a lid e d g e p o in t having edge intensity x'm„. O th e r w is e , the e d g e i n t e n s i t y a t th e (m, n) t h p o i n t is ta k e n to be zero. It is to be n o t e d h e r e t h a t th e t h r e s h o l d i n g c r it e r io n — (18) o r ( 1 9 ) — for a particular x mn is seen to b e a d a p t i v e (i.e. c h a n g i n g w ith its B mn v a lu e a c c o r d i n g to K 2(Bmn) {' 2i or K 3B l,n in th e respective c a se s).
A lt h o u g h it w as m e n t i o n e d in § 4 t h a t th e t h r e s h o l d value of the Weber region is j ‘> % o f th e ( A B / B ) mm c a l c u l a t e d g lo b a lly , it is o f te n f o u n d , in practice, that due to the im p e r fe c tio n o f th e a c q u i s i t i o n p ro c e ss, th e t r u e c o n t r a s t of the original object is not t r u ly reflected in the c a p t u r e d im a g e . A g lo b a l ty p e o f a p p r o a c h for the computation of ( A B / B ) m.tx o v e r the e n t ir e i m a g e m a y n o t be s u ita b le for images having a wide v a r i a t i o n o f c o n t r a s t a t t h e i r different p o r tio n s . In s te a d , a semi-global approach ( R o se n fe ld a n d K a k 1982), i.e. (A B / B ) max c a lc u la t e d o v e r a smaller segmented block will b e d esira b le . T h e t h r e s h o l d se lec tio n b a s e d o n this segmented approach may th e re fo r e be referred to a s ‘d y n a m i c ’ (W e z k a 1978).
6. Im plem entation and resu lts
T he a l g o r i th m d is c u s s e d in th e p r e v io u s s e c tio n was simulated o n EC 1033 c o m p u t e r . T h e o u t p u t i m a g e s w e re g e n e r a te d b y a n o v erp rin tin g technique as there is n o facility for g r a p h ic p r i n t i n g . S o m e o u t p u t im a g e s were generated with numeric r e p r e s e n t a t i o n s o f grey-Ievels d u e to a p r i n t e r p r o b le m . A set of images having d iffe re n t ty p e s o f h i s t o g r a m w a s ta k e n as te st d a t a o f size 64 x 64 and with 32 grey- levels. A l t h o u g h it w as m e n t i o n e d in fhe e a rlie r s e c tio n th a t the W eber region covers th e m a j o r p o r t i o n o f th e t o t a l d y n a m ic r a n g e a n d b o t h the De V ries-Rose and s a t u r a t e d r e g io n s co v e r a v e r y sm a ll p o r t i o n o f it (B u ch sb au m 1980), there is no q u a n t i t a t i v e figure a v a ila b le f o r th e le n g th o f s p a n o f ea c h region discussed.
E x p e r im e n ts w ere c a r r i e d o u t ( K u n d u a n d P a l 1986) for different lengths of span for d iffe re n t regions, n a m e l y ( a 2 = 0-33, o | = 0 6 6 ) , ( a 2 = 0T, a '3 = 0-7), (a'2 = 0-3, a 3 = 0-9), a n d ( a 2 = 0-1, a 3 = 0-9). I t w as f o u n d t h a t the com bination (a'2 = 01, a 3 = 0-9) p r o v id e d th e o p t i m u m re s u lt as far a s co n n e ctiv ity and thinness of edges w ere c o n c e r n e d .
F i g u r e 8 ( 5 )- (9 ) sh o w t h e e d g e - d e te c te d o u t p u t for Biplane, Lincoln, Boy, Jet, and C h r o m o s o m e im ag es w h e n x!mn w a s c o m p u te d w ith a R o b e rt gradient and Bm was o b t a i n e d w ith (21) for t h e t h r e s h o l d i n g p a r a m e t e r s a 2 = 0 1 , a 3 = 0-9 and j? = 4-5. The effect o f th e v a r ia tio n o f [i is d isc u sse d in o u r e a r lie r re p o r t ( K u n d u and Pal 1986).
R e su lts w ith o th e r o p e r a t o r s s u c h as S obel a n d P r e w i tt are also available in that r e p o r t.
F ig u r e s 5(d), 6 ( d ) , ..., 9 ( d ) th e re fo r e d e m o n s t r a t e th e thresholding version of the g r a d i e n t im a g e s F igs 5(c), 6 ( c ) , ..., 9(c)— u s in g th e p r o p o s e d thresholding algorithm (Fig. 4).
(C)
/ 7
i-.:'
id)
Figure 5. [a) Input image of Bi pl ane; / ” ) p r o p o s e d
of Biplane (using Robert g r a d i e n t ) ,j d ) t h r e Shoia thresholding algorithm (a'2 — a 3 ’
(c) id)
* '®ure ' Input image of Lincoln; (b) histogram of the input image; (e) gradient image 01 Lincoln (using R o b e rt gradient); (d) thresholded version of (c) using propose thresholding algorithm (oc| = 0-1, a '3 = 0-9, /? = 4-5).
caioj
stllii
“ II (a)
G rey level •
lb)
m
r,8U,e <rf? ,£ S f o T ^
algorithm («'2 = 0-1, a'3 = 0-9, P — 4'5)-
2536
»
i-W 9 M .
- . K i / r n
( c )
r f j S V M S ? : .
s
W
Figure 8. (a) Input image of Jet; (b) histogram of the input image;(e) gradient i m a g e of Jet (using Robert gradient); (d) thresholded version of (c ) using proposed thresholding algorit ms (a!2 = 0 1 , a'3 = 0-9, (i = 4-5).
OH
%
I I
(a) ( b )
(d)
Figure 9. (<i| Input image of C hrom osom e; ( h) histogram of the input image; (c) gradient image of Chromosome (using R obert gradient); [d J thresholded version of (c) using proposed thresholding algorithms (a', = 0 1 , a '3 = 0-9, /i = 4-5).
Figures 10s«) a n d 10{b) give t h e t h r e s h o l d i n g v e r s io n s o f Fig. 8(c) w h e n th is is individually th r e s h o l d e d ( R o s e n f e ld a n d K a k 1982) a t le v e ls 4 a n d 6. T h e th r e s h o l d at 4 could not iso la te the je t from t h e b a c k g r o u n d r e s u ltin g in u n d e s ira b le edges. O n th e other han d , th e th r e s h o ld a t 6 m a d e th e c o n t o u r s e p a r a t e o u t at the c o s t o f disconnecting the rig h t wing. T h i s is s h o w n as a n i l l u s t r a t i o n o f the im p r o v e m e n t ol the proposed te c h n iq u e o ver th e c o n v e n t i o n a l one.
■ i i l a
. Ti
;;-i i - l - r : ” t f t f i .
'■V-'-.-. ■■
I f - ! ! - !
. . . .
(«)
” ...
; :
•I:
(b)
Figure 10. (a) Thresholded version o f Fig. 8(c) using ™ a l histogram ^ h o l d m ^ - t e c h niques when thresholded at edge intensity level 4; (b) thresholded version of F.g. 8(c) using the same technique with level o f threshold 6.
As discussed in § 5 , th e r e s u lt s s h o w n in Fig. 11 L 'i n g ( 5 *) c*° ^ ( L ^ t additional c o m p u t a t i o n (as in th e c a s e o f R o b e r t , S obel etc.) o r o aining . e
constituting te rm s o f x m„. T h e p a r a m e t e r (a, ft, b a c k g r o u n d size■) ^ n s i d e r e d h e . , a re the same as in F igs (5) (9). A s i m i l a r e x p e r i m e n t w as a ls o c o n d u c t e d for ( / ) , results are n o t in c lu d ed here.
2538
(a)
I . 1"* \ 1 I*1"
V»i. -IKii:*-'
-!»• I::?*?-: w v r . . .
<
- ’ «■;:•: r« . -. ■ 7
•s' . I:' •• ««£-.
H - i l r v ; : . ■ ; * i :
5ic ' {^ ^ ,5 ■.;v
M i , . l . ~
. . v u i m * i: i . i » K -ii-j ■ •
(b)
(c)
Figure 11. Edge detected version using the new edge operator (5 c) and the proposed thresholding technique w ith 3 x 3 background size, a'2 = 0 1 , a ' 3 = 0-9 and ft= 4-5. (a) or t e input image Fig. 7(a); ( b) for the input image Fig. 8(a); (c) for the input image Mg. W -
6.1. E ffe c t o f background size
It w a s d is c u s s e d in § 3 t h a t t h e th r e s h o l d v a l u e is d e p e n d e n t on the size of the b a c k g r o u n d c o n s id e r e d for d e t e c t i n g edges. I n fact, t h e th r e s h o l d value ineteases wit the in c r e a s e in b a c k g r o u n d size r e s u lt in g in a s m a l l e r n u m b e r of detectable e ge points.
T h e a b o v e fact rese m b le s w e ll t h e e x p e r im e n ta l r e s u lt s show n in Figs 12 an c o r r e s p o n d i n g t o th e R o b e r t g r a d i e n t a n d (5 e) w h e n F ig . 7 (a) — Boy is consider as i n p u t w i t h a 5 x 5 a n d 7 x 7 w in d o w size ( b a c k g r o u n d ) . Considering Figs 7 ( ),
11 (a), 12 a n d 13 it is seen t h a t a s t h e b a c k g r o u n d size increases from 3 x 3 to 7 x the c o n t o u r b e c o m e s th in n e r . W i t h a f u rth e r in c r e a s e in b a c k g r o u n d size, the contours were f o u n d t o b e d is c o n n e c te d .
S o m e m o r e results in t h e a b o v e c o n t e x t a re s h o w n in Fig. 14 for some optim um w in d o w sizes.
6.2. Se m i-g lo b a l selection o f ( A B / B ) max
T h e r e s u lt s p re se n te d s o f a r a r e b a s e d o n th e (AJS/B)max value obtained o v e r the entire p i c t u r e (globally). I n t h i s s e c t i o n we will b e d e m o n s t r a t i n g the effect of the sem g lo b a l s e le c tio n of th a t p a r a m e t e r .
... ... %
. c ... :
: . . -
f ! ’I 4' ! ' : : - -
V: . — :=:■ |1
- : : ; r
... '
(a)
...
."I \
;V j T '
■li ;5* .i--. : I
?■ ; . ■ *
r ' '
f i L
V: . . . s £ : s r : s s s : aoB:
r c- „ it n\ ,icim> the R o b e rt gradient and proposed
{h)
* • * ♦ » - * <*» “ d * - * « m
background size = 7 x 7 .
t f t o i U *
..I ..'
( a )
..-s. - ! i ---- s s
. . . . . ■'!
-rV:r - .Ml
■ ! ! ; ■ &
■.-. -v- . v . .. ; III- ” ■
(^) t and proposed
Figure 11 Edge-detected version of Fig. 3 m 8 * 5 * — ' 5 “ *
thresholding technique (a'2 — 0 * 1, <*3 (b) background size = 7 x 7 .
2540
ISI
cF iif
m
in
' i-. ... • :: i r .• - r . - ‘
.7 , . ■■■■.!• . - r !
• * i * ■ ...
..~ I
(c> (<*)
S I
(£) ( /)
Figure 14. bdge-detected version using proposed thresholding technique fa'2 = 0'l. *3" 1 /? = 4-5) for: (a) Fig. 6(a) using the Robert gradient and 5 x 5 window size I ac ground); (b) Fig. 9(a) sam e operator and window size as in Fig. 14(a); (c) Fig- 8(0) uSI^
new edge operator (5 e) a n d same window size as in Fig. 14(a); (d) Fig. 9(a) using *a operator and window size as in Fig. 14(c); (e) Fig. 8(a) using new edge operator (5
e)»
7 x 1 window size; ( / ) Fig. 9(a) using same op era to r and window size as in fig. 1
Figure 15 sh o w s the edges o f t h e J e t a n d C h r o m o s o m e im ag es using th e R o b e r t gradient w hen th e im ages a r e d i v i d e d i n t o f o u r b lo c k s e a c h h a v in g d im en sio n s 32 x 32. The (AB B)max value w as c o m p u t e d s e p a ra te ly fo r e a c h b lo c k in o rd er t o select the thresholds in th e respective b l o c k s . T h e th r e s h o l d se lec tio n s h ave th u s b e c o m e dynamic w hich en a b le s o n e to d e t e c t m o r e in f o r m a t i o n in th e content. H e r e , the background size, a-v a lu es a n d ^ - v a l u e s a r e th e sa m e a s in F ig s (5 )-(9 ).
;-;s . . •I!li||sfe
- - - i ; V f s : = r
■ ■m - ' = | ; : S 5 : S = : I
m m
i t.
„
•■laasns
| |
(a)
m
Figure 15 Edge-detected version using the Robert gradient a n d the semiglobal selection for s the computation of (A B/B)„ax over ’____ „ f / i aia\ window size 32 x 32 for thresholding (with a 2 = 01,
*' = 0-9, I? = 4-5) for: (a) Fig. 8(a); (b) Fig. 9(a).
6.3. Effect o f thresholding on h is t o g r a m
To d e m o n s tr a te the effect o f t h r e s h o l d i n g o n th e h i s t o g r a m let us c o n s .d c r for example Fig 16( a ) w hich s h o w s t h e h is t o g r a m o f th e J e t im ag e after th e R b gradient is used, a n d Pig. 16 <b) w h e n i t is th r e s h o ld e d a d a p t i v e l y using the: p r o p o j r f thresholding a lg o rith m . F ig u re 16 (a) s h o w s th e fre q u e n c y o f ° c c ™ ce^ ° ldi edge points w ith different edge in te n s itie s . I n th e n o r m a l h is to g ra m th r e s h o ld n g
E d g e intensity
(a)
• , - „ thP R o b e r t g r a d ie n t ) tor tne r i g . 16. (a) Histogram of edge intensity * ^ ’ng . 16(a )— using proposed thresholding
(b) histogram of thresholded edge m te n s ity ^ - r ig.
technique
t e c h n i q u e , th e o c c u r r e n c e o f all th e levels u p t o th e point of thresholding is d e l i b e r a t e l y m a p p e d t o z e r o ( g lo b a lly ) w i t h o u t c o n s id e r in g their local importance ( c o n n e c t i v i t y ) . T h is effect is d e m o n s t r a t e d i n Fig. 10.
O n t h e o t h e r h a n d , t h e p r o p o s e d t h r e s h o l d i n g te c h n iq u e used to map a certain n u m b e r o f ed g e p o i n t s a t d if f e r e n t e d g e in t e n s i t y le v e ls — Fig. 16 (b)— to zero instead o f all t h e e d g e p o i n t s c o r r e s p o n d i n g to a few e d g e intensity levels. This is the reason w h y t h e p r o p o s e d t e c h n i q u e b a s e d o n h u m a n v is u a l characteristics gives a better r e s u l t o v e r th e c o n v e n t i o n a l te c h n iq u e .
7. D is c u s s io n
A l g o r i t h m s b a s e d o n h u m a n p s y c h o - v is u a l p h e n o m e n a are presented here for the a u t o m a t i c e x t r a c t i o n o f t h e sig n ific a n t e d g e p o i n t s fro m those obtained by normal e d g e o p e r a t o r s . H u m a n v i s u a l c h a r a c t e r i s t i c s a r e u s e d to m a ke the threshold selection p r o c e d u r e a d a p t i v e in o r d e r t o e l im i n a te th e u n d e s i r a b l e edge points. The results are f o u n d to b e im p r o v e d a s c o m p a r e d to t h o s e o b t a i n e d with standard thresholding t e c h n i q u e s w h e n u n i m o d a l , b i o m o d a l , m u ltip le -v a lle y e d , and flat-wide valleyed i m a g e s a r e c o n s id e r e d a s i n p u t .
T h e t a s k o f g r a d i e n t e d g e d e t e c t o r s w a s a l s o re p la c e d in a part of our study by s o m e o p e r a t o r s i n h e r e n t t o t h e t h r e s h o l d i n g p r o c e d u r e so that the computation time c o u l d b e r e d u c e d w i t h o u t a f f e c tin g th e p e r f o r m a n c e .
T h e b a c k g r o u n d i n t e n s i t y c o m p u t e d o v e r a l a r g e r window size makes the edges t h i n n e r . S p litt in g a n i m a g e i n t o s u b - b l o c k s (i.e. m a k in g the threshold selection p r o c e d u r e d y n a m ic ) o n t h e o t h e r h a n d , e n a b l e s o n e to detect more information.
T h e e d g e d e t e c tio n t e c h n i q u e p r o p o s e d i n th i s p a p e r does not require any human i n t e r v e n t i o n . A l t h o u g h c e r t a i n p o r t i o n s o f t h e e d g e s a r e found to be m ore than one pel w i d t h , t h e s e c o u l d b e t h i n n e d o u t u sin g s t a n d a r d edge-linking techniques. The p r o b a b l 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 will b e in t h e field o f robot vision where the s c o p e o f h u m a n i n t e r a c t i o n is v e r y lim ited.
Ac k n o w l e d g m e n t
T h e a u t h o r s w ish t o t h a n k D r D . D u t t a M a j u m d e r , H ea d of the Electronics and C o m m u n i c a t i o n S c ie n c e s U n i t , I n d i a n S t a t i s t i c a l Institute, for his constant en
c o u r a g e m e n t in th is w o r k , a n d M r M . Y. R a o f o r h is help in the computer program d e v e l o p m e n t . T h e a u t h o r s a l s o w ish to t h a n k M r J. G u p t a for typing the manuscript.
Re f e r e n c e s
Br o w n, E . L „ and De f f e n b a c h e r, K , 1 9 7 9 , Perception and Senses (London: Oxford University Press).
Bu c h s b a u m, G„ 1980, I.F.E.E. Trans. Biomed. Engng, 27, 237.
G o n z a l e z , R. C., and W i n t z , P., 1 9 7 7 , Digital Image Processing (Mass., U.S.A.: Addison- Wesley).
H a l l , E. L„ 1979, C omputer Image Processing and Recognition (New York: Academic Press)- Ku n d u, M . K and P a l , S. K „ 1986, Pattern Recogn. Lett., 4, 433.
fNFVAUA R., 1982, Machine Perception. (Englewood Cliffs, N.J.: Prentice Hal!).
S' *-•; a n d M a j u m d e r , D. D , 1986, Fuzzy Mathematical Approach to Pattern R e c o g n i t a
(N ew York: Wiley).
Ro s e n f e l d A Ka k, A. C „ 1982, Digital Picture Processing (New York: Academic Press)- w i z k a , J S., 1978, Comput. Graphic Image P r o c e s s 7, 259.
Zu id e m a, P., et al„ 1 9 8 3 , I.E.E.E. Trans. Systems Man Cyber., 13, 923
