Pattern R eco g n itio n L ette rs 8 (1988) 237 -2 4 9 North-Holland
Binary contour coding using Bezier approximation
S .N . B IS W A S , S .K . P A L a n d D . D U T T A M A J U M D E R
Electronic a n d C om m unication Sciences Unit, Indian S ta tistica l In stitu te, C alcutta 700 035, India
Received 16 J a n u a ry 1988 R evised 28 July 1988
A bstract: A m e th o d fo r co d in g o f b in a ry im age c o n to u r using Bezier a p p ro x im a tio n is pro p o sed . A set o f key pixel (guiding pixels) o n th e c o n to u r is defined w hich en ab les th e c o n to u r to be d eco m p o sed in to arcs an d straig h t line segm ents. A set o f clean in g o p e ra tio n s h as been co n sid ered as a n in term e d ia te ste p b efo re p ro d u c in g the final o u tp u t.
T h e q u ality o f faith fu l re p ro d u c tio n o f th e d eco d ed version h as been exam ined th ro u g h the objective m easures o f shape co m p actn ess an d th e p ercen tag e e rro r in a rea. F inally, the bit re q u ire m e n t a n d the com p ressio n ratio s for different in p u t im ages a re c o m p a re d w ith th e existing ones.
K ey words: C o n to u r c o d in g , Bezier a p p ro x im a tio n , B resenham alg o rith m .
1. In tro d u c tio n
Im ag e c o d in g is a te c h n iq u e w hich re p re se n ts an image, o r th e in fo rm a tio n c o n ta in e d in it w ith few er bits. I ts o b je ctiv e is to c o m p re ss th e d a t a fo r re d u c ing its tra n s m is s io n a n d sto ra g e c o sts w hile p re se rv ing its in fo rm a tio n . V a rio u s te c h n iq u e s su c h as sp a tial d o m a in m e th o d s , tra n s fo rm c o d in g , h y b rid coding, in te rfra m e c o d in g etc. w h ere b o th ex a c t (er- ror-free) a n d a p p r o x im a te (faithful rep lica) c o d in g algorithm s for b in a ry a n d g ra y to n e im a g e hav e been fo rm u la te d a re a v a ila b le in [1-8]. A p p ro x i
mate c o d in g o f g r a y to n e c o n to u r fo r its p rim itiv e (lines a n d arc s o f d iffe re n t d eg re e o f c u rv a tu re ) ex tractio n u sin g fuzzy sets is d e s c rib e d b y P a l e t al.
[4-5].
B ezier a p p ro x im a tio n te c h n iq u e [6,7] w hich uses B ernstein p o ly n o m ia ls as th e b le n d in g fu n c tio n provides a successful w ay to a p p ro x im a te a n arc (not h a v in g a n y in flexion p o in t) fro m a set o f m inim um th re e c o n tro l p o in ts. T h e a p p ro x im a tio n scheme is sim p le a n d useful for its axis in d e p e n d e n ce p r o p e rty . I t is a lso fo u n d to be c o m p u ta tio n a lly efficient.
T h e p re s e n t w o rk a tte m p ts to fo rm u la te a n a lg o
r ith m fo r a p p ro x im a te c o d in g o f b in a ry im ages b a s e d o n B ezier a p p ro x im a tio n te ch n iq u e . A c o n to u r is first o f all d e c o m p o se d here in to a set o f arcs a n d lin e segm ents. F o r this, a set o f key pixels are d efin ed o n th e c o n to u r a n d th e vertices o f B ezier c h a ra c te ristic tria n g le s c o rre sp o n d in g to a n arc are co d e d . R e g e n e ra tio n te c h n iq u e involves B er- s e n h a m ’s a lg o rith m [8] in a d d itio n to th e B ezier m e th o d . D u rin g th e re g e n e ra tio n p ro cess, key pixels o n e c o n sid e re d to be th e g u id in g pixels a n d th e ir lo c a tio n s a re th e re fo re in n o w ay d istu rb e d . In o r d e r to p rese rv e th e m , a n d to m a in ta in th e c o n n e c tiv ity p r o p e r ty som e in te rm e d ia te o p e ra tio n s e.g., d e le tio n a n d shiftin g o f u n d e sira b le pixels g e n e ra te d by B ezier a p p ro x im a tio n , a n d in se rtio n o f new pixels a re in tro d u c e d in o rd e r to h av e b e tte r faithful re p ro d u c tio n .
E ffectiveness o f th e a lg o rith m s is c o m p a re d w ith tw o e x istin g a lg o rith m s b ased o n c o n to u r ru n le n g th c o d in g (C R L C ) [9] a n d d isc re te line seg m en t c o d in g (D L S C ) [10]. T h e c o m p re ssio n r a tio s o f th e p ro p o s e d m e th o d s are fo u n d to be sig n ifican tly im p ro v e d w ith o u t affecting th e q u a lity m u c h w h e n a set o f im ag es is c o n s id e re d as in p u t. T h e c o m p a c t
ness a n d th e difference in a re a b etw e en th e in p u t
a n d o u tp u t v ersio n s k e e p in g th e lo c a tio n s o f th e key pixels th e sa m e a re also c o m p u te d to p ro v id e a m e asu re o f th e e rro r.
2. B ezier a p p ro x im a tio n technique Bernstein polynomials
T he B e rn stein p o ly n o m ia l a p p r o x im a tio n o f d e gree m to a n a r b itra ry fu n c tio n F: [0,1] -> R is d e fined as
m
B im[f(t)\ = X /O '/m ) <t>im(t) i = 0
w here th e w eig h tin g fu n c tio n s <pim are , fo r fixed t, th e discrete b in o m ia l p ro b a b ility d e n sity fu n c tio n s for a fixed p ro b a b ility ,
w here
m ml
i } (m — i) \ i \
T h e re m a rk a b le c h a ra c te ristic s o f th e B e rn stein p o ly n o m ia ls a re th e e x te n t to w hich th e y m im ic th e p rin c ip a l fea tu re s o f th e p rim itiv e fu n c tio n / a n d th e fact th a t th e B e rn ste in a p p r o x im a tio n is alw ays a t least as sm o o th as th e p rim itiv e fu n ctio n / w here
‘s m o o th ’ refers to th e n u m b e rs o f u n d u la tio n s , th e to ta l v a ria tio n etc.
Bezier curves
T h is class o f cu rv es w as first p ro p o s e d by B ezier [6,7]. T h e p a ra m e tric form o f th e curves is
X = P x( 0, Y = P y(t).
(2a) (2b) L et (x 0,j;0), ( x l , y l ) , . . . , ( x m, y m) be (m + 1) o r d ered p o in ts in a plane. T h e B ezier cu rv e asso cia te d w ith th e p o ly g o n th ro u g h th e ab o v e p o in ts is the
v e c to r v a lu e d B e rn s te in p o ly n o m ia l a n d is given by m
P*(t) = X (3a)
i = 0 m
Py(t) = Z & m (0 y< (3b)
i = 0
w h ere 4>im{t) a re th e b in o m ia l p ro b a b ility density fu n c tio n s o f (1).
In th e v e c to r fo rm , th e e q u a tio n s (3) a re
n , ) = ( w ) and
so th a t
m
P(t ) = £ Vi- i = 0
(4)
T h e p o in ts v0, vx, . . . , vm a re k n o w n a s th e guiding p o in ts o r th e c o n tro l p o in ts.
F ro m e q u a tio n (4) it is seen th a t P (0 ) = vo a n d P( 1) = vm.
T h u s th e ra n g e o f t significantly e x te n d s fro m 0 to 1. T h e d e riv a tiv e o f P(t ) is
P'(t) = - m { 1 - 0 m _ 1 vo
m ~ \ (
+ l l . j i i f - K i - t r - '
+ m t m~ l vm.
N o w P ’(0) = m ( v l — v0) a n d P ’( l ) = m( v m — vm_
T h u s th e T a y lo r series e x p a n sio n n e a r z e r o is P(t) = P (0 ) + t P \0) + h ig h e r o r d e r te rm s o f t
~ v0(l +
a n d a n ex p a n sio n n e a r o n e is
P(t) = P ( l ) — (1 — t) P '( l) + h ig h e r o r d e r te rm s o f (1 — t)
as vm{l - m ( 1 - 0 } + m ( 1
I t is n ow clear th a t as t - » 0 th e B ezier p o ly n o m ial lies o n th e line jo in in g v0 a n d Vj a n d fo r t -> 1 on th e line jo in in g vm _ x a n d vm. T h is m e a n s t h a t these lines a re ta n g e n ts to th e cu rv e a t v0 a n d vm.
Also since = o 0 ™ (0 = 1 th e B ezier cu rv e lies inside th e con v ex h u ll o f th e c o n tro l p o in ts.
F or c u b ic B ezier cu rv es, m = 3. T h e c o n tro l p o ly gon th e n c o n sists o f fo u r c o n tro l v ertices v0, v1; v2, v3. T he B e rn ste in p o ly n o m ia ls for th is case are
00.3(f) = (1 - 0 3 = - t 3 + 3 t 2 - 3t + 1, 4>u3(t) = 3 t(l - t) 2 = 3 t3 - 61 2 + 31, 0 2 ,3 (0 = 3 t 2( l — t) = — 3 t3 + 3 t 2, 0 3 ,3 (0 =
and th e c o rre s p o n d in g B ezier cu rv e is
^ ( 0 = (1 - O3v0 + 3 t(l - t ) 2v 1
+ 3 f2( l - f)v2 + f3v3. (5)
T h o u g h th e c u b ic B ezier cu rv e is w idely u sed in com puter g ra p h ic s [1 1] we h av e u sed h ere its q u a dratic v e rsio n to m a k e th e p ro c e d u re fa ste r en o u g h . F o r th e q u a d r a tic B ezier cu rv e, m = 2 a n d th e control p o ly g o n alw a y s c o n sists o f th re e p o in ts . T h e Bernstein p o ly n o m ia ls in th is c a se a re
002(0
= (1 - 0 2 = 1 - 2r + t 2, 0 i2 (O = 2(1 — t)t = 2r — 2 r 2, 0 2 2 ( 0 = t 2.Thus
0 — [0O2<012'022]
’'O Vl l v2
= [f2 t 1] [c]
Vo Vl where th e coefficient m a trix
1 - 2 f
[c] = - 2 2 0
. 1 0 0^
In the p o ly n o m ia l fo rm th e B ezier cu rv e is
n o = t 2 ( v o + V2 - 2 v j)
+ J(2 vi - 2v0) + v0. (
6
)This is a se c o n d d eg re e p o ly n o m ia l a n d c a n be c o m puted in a m u c h fa ste r w ay th a n in th e H o r n e r ’s process [1 1].
Bresenham algorithm
T h e u n d e rly in g co n c e p t o f th e B re s e n h a m a lg o rith m for g e n e ra tin g th e p o in ts fo r a s tr a ig h t lin e se g m en t re stric te d to a n o c ta n t, given its tw o e n d p o in ts , lies in ch eck in g th e p ro x im ity o f th e a c tu a l line to th e g rid lo c a tio n . L et ( x 1, y 1) a n d ( x 2, y 2) b e th e tw o p o in ts th r o u g h w hich a d isc re te s tr a ig h t lin e se g m en t is re q u ire d . F o r this, th e in te rc e p t o f th e lin e se g m en t w ith th e lin e a t x = Xj + 1, x , -t- 2 ,. . . , x 2 a re c o n sid ered . If th e in te rc e p t w ith th e lin e a t x = x x + 1 is closer to th e line a t y = + 1, th e n th e p o in t (x j + 1, ^ + 1) b e tte r a p p ro x im a te s th e line se g m en t in q u e s tio n th a n th e p o in t (x j + 1 , y) . T h is m e a n s if th e in te rc e p t is g re a te r th a n o r e q u a l to h a lf th e d ista n c e b etw een ( x , + 1 , y ) a n d ( x t + 1,3?! -I- 1) th e n th e p o in t ( x t + 1,)^ + 1) is se-
F ig u re 1. F lo w c h a rt for B resenham ’s a lg o rith m for g e n e ra tin g stra ig h t line in first o c ta n t.
le c te d for a p p ro x im a tio n o th e rw ise th e p o in t (x j + l ,y ) is selected. N e x t, th e in te rc e p t o f th e line seg m en t w ith th e line a t x = x 1 + 2 is co n sid ered a n d th e sam e logic is a p p lie d fo r th e selectio n of p o in ts.
N o w , in ste a d o f fin d in g th e in te rc e p t a n e r ro r te rm , e, is used for th e se lec tio n p u rp o se . In itia lly e = — \ a n d th e in itia l p o in t is selected. T h e slope o f th e line, A y/A x is a d d e d to e a n d th e sign o f th e c u rre n t v alu e o f e = e + A y / A x is te ste d . If it is n eg a tiv e , th e n th e p o in t is selected alo n g th e h o r i
z o n ta l line, i.e. x is in c re m e n te d by o n e a n d y re
m a in s th e sam e. T h e e r ro r te rm is th e n u p d a te d by a d d in g th e slope to it. B u t if th e e rro r te rm is p o si
tive (o r tw o ), th e n th e p o in t is selected a lo n g th e v ertical line, i.e. b o th x a n d y a re in c re m e n te d by one. T h e e rr o r te rm is u p d a te d by d ec reasin g o n e fro m it.
F o r in teg er c a lc u la tio n , e is in itialize d to e = 2 Ay — Ax b ec au se 2Ay — A x = 2eAx = e (say).
T h e d etails o f th e a lg o rith m for th e first o c ta n t is given in th e flo w -c h art as sh o w n in F ig u re 1.
3. Key pixels and contour ap p ro x im a tio n A. K e y pixels
I n th e a n a ly tic p la n e th e c o n to u r o f a n o b je ct ex
h ib its sh a rp m a x im a a n d m in im a a n d th ese p o in ts ca n be d etec ted a lm o st a c c u ra te ly w ith o u t m u c h difficulty. H o w ev er w h en th e c o n to u r is dig itized in a tw o -d im e n sio n a l a rra y sp ace o f M x N p o in ts o r pels o r pixels, th e sh a rp n e ss in th e c u rv a tu re o f th e c o n to u r is d e stro y e d d u e to th e in fo rm a tio n loss in h e re n t in th e p ro cess o f d ig itiz a tio n . T h e e r ro r is k n o w n as th e d ig itiz a tio n e rro r. C o n s e q u e n tly it b e
co m es ra th e r difficult a n d co m p lic a te d to estim a te th e p o in ts o f m a x im a a n d m in im a. A n a p p ro x im a te s o lu tio n to th is p ro b le m is to define a set o f pixels, we call key pixels w hich a re close to th e p o in ts o f m a x im a a n d m inim a.
F o r exam ple, co n sid er a fu n ctio n f ( x ) in th e d is
cre te p lan e. W h e n / ( x ) is c o n s ta n t in a n in te rv al [ku k 2], th e c o rre sp o n d in g a n a ly tic fu n c tio n / a(x) m a y exhibit local m a x im a a n d m in im a (o r glo b al m a x im u m o r m in im u m ) an y w h e re w ith in th e in te r
val as show n in the F ig u re s 2(a) a n d 2(b).
F ig u re 2. P ossible b e h a v io u r o f / a(x) w hen f ( x ) is c o n s ta n t, (a) C on sid erin g local m a x im a /m in im a o ff a(x). (b) C o n s id e rin g glo
bal m ax im u m /m in im u m o f / a(x). ■ d en o tes the p o s itio n o f the key pixel.
If we get a pixel e ith e r d ire c t-c o n n e c te d o r out
w a rd c o rn e r-c o n n e c te d to th e e n d pixels o f th e in
te rv a l [ k1, k 2] su ch th a t b o th th e v alu es o f f ( x ) at th ese pixels are e ith e r g re a te r o r sm a lle r t h a n its val
ue in th e in te rv a l, th e n w e assu m e a p o in t o f m axi
m u m o r m in im u m to exist a t th e m id - p o in t o f the in te rv al, i.e. a t x = ( k v + k 2)/2 if (&i + k2) is even a n d a t x = {k^ + k 2 + l)/2 if (A^ + k 2) is o d d . Let us co n sid e r th is p o in t o r pixel in th e d is c re te plane to be a key pixel. A n o th e r e x a m p le fo r th e existence o f a key pixel sh o w n by ■ is d e p ic te d in F ig u re 3 for w h ic h /( x ) is n o t c o n s ta n t o v er a n in te r v a l.
B. Definition
A fu n ctio n / ( x ) , c o n s ta n t in [ku k 2\, in th e dis
crete p la n e is sa id to h av e a key pixel P a t x = c (w here c = ( k 1 + k 2)f2 o r (k l + k 2 + l ) / 2 cor
re sp o n d in g to even a n d o d d values o f ( k 1 + k 2)) p ro v id e d th e re exist <51? S2 e {0,1} su c h t h a t in both
;he intervals [(/ct — <5i),AJ a n d [k2, ( k 2 + d 2)}
either f ( c ) > f{x) o r f { c ) < f ( x ) .
When k l = k 2 = c, th e d e fin itio n is a p p lic a b le for Figure 3 w here = S2 = 1.
It is to be n o te d h ere th a t th e a b o v e d efin itio n corresponds to th e F ig u re s 2 a n d 3 w h ere k ey pixels lie on a h o riz o n ta l se q u e n c e o f pixels fo r th e in te rv a l [A’j, k 2] o f x. S im ila rly , k ey pixels c a n also b e d efined for a vertical se q u e n c e o f pixels fo r th e in te rv a l [i-!,A2] o f y.
C. Contour approxi mat i on
L e t k 1, k 2, . . . , k p b e p k ey pixels o n a c o n to u r. T h e segment (the G e o m e tric a l E n tity , G E ) b e tw e e n tw o key pixels c a n th e n b e classified as e ith e r a n a rc o r a s tra ig h t line. If th e d ista n c e o f e a ch pixel fro m the line jo in in g th e tw o key pixels is less th a n a p r e specified value, d, say, th e n th e se g m en t is c o n s id ered to be a s tra ig h t line (F ig u re 4(c)); o th e rw ise it is a n arc . T h e a rc m a y a g a in be o f tw o ty p e s, w ith all t h e pixels e ith e r lying o n b o th sides (F ig u re 4(a)) or ly in g o n th e sa m e side (F ig u re 4(b )) o f th e line joining th e key pixels. L et us d e n o te th e G E in F ig ure 4 (c) by L (line) a n d th a t in F ig u re 4 (b ) b y C C (curve). I t is th e re fo re seen th a t th e G E in F ig u re 4(a) is n o th in g b u t a c o m b in a tio n o f tw o C C ’s Meeting a t a p o in t Q (p o in t o f inflexion).
T h e re fo re , th e key pixels o n th e c o n to u r o f a tw o - tone p ic tu r e c a n be used to d e c o m p o se th e c o n to u r 'nto tw o ty p e s o f G E ’s, n a m e ly a rc a n d line.
L e t us n o w c o n s id e r F ig u re 5 w h ere th e cu rv e C C
>n F ig u r e 4 (b ) is first o f all en c lo se d w ith in a rig h t
y
Figure 4. T ypes o f G E . (a) A rc w ith inflexion p o in t, (b) A rc. (c) S tra ig h t line.
tria n g le A B C w h ere A C (th e line jo in in g k j a n d k j + 1 ) is th e h y p o te n u se a n d A B a n d B C a re th e h o riz o n ta l a n d v ertical lines resp ectiv ely . I t is p ro v e d in A p p e n d ix A th a t th e a rc C C will alw a y s be c o n fin e d w ith in a rig h t tria n g le A B C . A lin e D F is th e n d ra w n w hich is p a ra lle l to th e h y p o te n u s e A C a n d p asses th r o u g h th e pixel E o f m a x im u m d is p la c e m e n t w ith resp ect to AC . T h u s , th e s u b tr ia n gles A D E a n d CFE, so c o n s tru c te d , m a y be ta k e n as th e c h a ra c te ris tic tria n g les to a p p ro x im a te th e cu rv e C C by q u a d ra tic B ezier a p p r o x im a tio n te c h niq u e.
T h e p re s e rv a tio n o f th e in fo rm a tio n o f B ezier c h a ra c te ristic tria n g le s w ith th e h elp o f key pixels fo rm s th e b asis o f th e u n d erly in g c o n c e p t o f th e p r o p o se d c o d in g schem es.
4. C oding schem es
In th e p ro p o s e d m e th o d , tw o p o in ts (n am e ly , E a n d C) a re o n ly s to re d to p rese rv e th e c h a ra c te ristic tria n g le s c o rre s p o n d in g to a n a rc w h e n its s ta rtin g
F ig u re 3. P o sitio n of th e key pixel w hen k 1 = k 2 = c. F ig u re 5. Bezier ch aracteristic tria n g le s for th e a rc A E C .
p o in t A is k n o w n b e fo re h a n d . T h e p o in t D o r F n e e d n o t be s to re d b ec au se th e y c a n a u to m a tic a lly b e o b ta in e d fro m th e afo re sa id p o in ts . F o r exam ple, D is th e p o in t o f in te rse c tio n o f th e h o riz o n ta l line th r o u g h A a n d th e line th r o u g h E a n d p ara llel to AC . It is to be n o te d h ere th a t th e e n d p o in t o f G E is th e s ta rtin g p o in t o f its follo w in g G E .
R e g a rd in g stra ig h t lines, it is o b v io u s th a t, only on e p o in t needs to be sto re d w h en th e sta rtin g p o in t is k n o w n .
T h e a lg o rith m for key pixel e x tra c tio n is sh o w n in A p p en d ix B.
Bit requirement
L et th e re be p different c o n to u rs in a b in a ry im age o f size M x N w h ere M = 2 m a n d N = 2".
T h e c o n to u rs m a y be o f tw o types; e ith e r closed o r op en . If n k a n d n; are respectively th e n u m b e r o f key pixels (including th e e n d pixels for o p e n c o n to u r) a n d p o in ts o f inflexion o n a c o n to u r, th e n the n u m b e r o f arcs a n d stra ig h t lines (segm ents) is («k H- — 1). O f them , let ns b e th e n u m b e r o f stra ig h t line segm ents. F o r clo sed c o n to u rs th e in i
tial key pixel is th e sam e as th e final key pixel.
T he co d e w o rd , s, o f a G E is v a ria b le in length.
s consists o f tw o su b w o rd s s x a n d s 2. s x alw ays re p resen ts id e n tity (arc o r line) o f th e G E w hile s2 d e n o te s its d escrip tio n . W h e n th e G E is a n arc , s2 gives th e vertices o f th e c h a ra c te ris tic tria n g le (for ex a m p le , A , E , C in F ig u re 5). F o r a stra ig h t line seg m en t, s2 in d ic ates th e e n d p o in ts o f th e line seg
m e n t. It is o b v io u s th a t th e c u rr e n t e n d p o in t is a l
w ays th e s ta rtin g p o in t o f th e su c ce ed in g G E . T he b it p a tte r n rep rese n tin g a c o n to u r is th e re fo re as d isp la y e d in F ig u re 6.
< r1 ---> <--- r2 --- ► <--- r} --- ► [T ype o f contour] [N u m ber o f G E] [Starting point]
< S1 > < s2 > ...
[Id en tity o f G E] [D escrip tion o f G E]
<--- s i --- > <--- s2 --- ► [Id en tity o f G E] [D escrip tion o f G E ]
F ig u re 6. Bit p a tte rn .
T y p es o f c o n to u rs (o p en o r closed) c a n be repre
se n ted b y a single bit.
In th e w o rst case, all th e G E ’s m a y be straight line segm ents a n d th e n u m b e r o f key pixels m a y be M N . T h u s it needs (m + n) b its to re p re se n t th e to
ta l n u m b e r o f G E ’s in a c o n to u r.
Id e n tity o f G E (arc o r line) ca n be re p re se n te d by a single b it.
G iv e n a s ta rtin g p o in t o f th e c o n to u r, w e need tw o p o in ts for d escrib in g a n a rc a n d o n e p o in t for a s tra ig h t line. E a c h p o in t c a n be re p re s e n te d by (m + n) bits.
T h erefo re, for d escrib in g a n o p e n c o n to u r con
sistin g o f ((nk + Mj — 1) — ns) arc s a n d ns lin e s we need
Ta = (m + n) + 2 (m + n)((nk + nt — 1) — ns) + (m + n)ns
b its w here th e first te rm c o rre s p o n d s to th e starting p o in t. F o r a clo sed c o n to u r, th e a m o u n t o f b its re
q u ire d is Tc = T0 — (m + n) since th e la st k e y pixel (en d p o in t) c o rre sp o n d s to th e s ta rtin g p o in t.
F ro m F ig u re 6, it is th e re fo re seen th a t T0 (o r Tc) gives th e b it re q u ire m e n t for s2’s only . T h e to ta l re
q u ire m e n t co n sid e rin g th e re m a in in g e n titie s o f Fig
u re 6, will th e re fo re be
^totai = x + (3 + y + 5 w here
a = re q u ire m e n t c o rre s p o n d in g to = 1, P = re q u ire m e n t c o rre s p o n d in g to r 2
= (m + n),
y = re q u ire m e n t c o rre s p o n d in g to s ^ s
= K + «i - i), 8 = T0o tTc.
5. D ecoding
T h e c o d e d b in a ry strin g o u tp u t c o rr e s p o n d in g10 th e m e th o d is sh o w n in F ig u re 7. (m + n) indicate th e w o rd le n g th for th e n u m b e r o f G E ’s w h e r e ^ (m) + (n) d e n o te th e c o -o rd in a te s o f a p o in t.
D e c o d in g o f th e s trin g o f F ig u re 7 is b a se d o n the follo w in g n o ta tio n s .
T h e first b it ( / J in d ic a te s th e ty p e o f c o n to u r ( ie- /; = 0 fo r o p e n a n d 1 fo r closed). T h e n ex t se q u e n t
/1 l2 I3 U h (*) (*** • • ■ *) (*** • • ■ *) (*** • • ■ *) (*)
(m + n) (m) + (n) (m) + (n)
^6 U h h
(*** • ■ • (*** • • ■ *) (*) v--v--'
( m) + (n) (m) + (n)
U h U
(*** • ■ • *) (*) >— v— 1 (m) + (n)
F ig u re 7. C o d e d b in a ry strin g o u tp u t.
U o f (m + n) b its re p re se n ts th e n u m b e r o f G E ’s p r e s e n t in th e c o n to u r. T h e first m b its o f th e se
q u e n c e /3 d e n o te th e v alu e o f th e o r d in a te w h ereas th e r e m a in in g n b its give th e v a lu e o f th e ab scissa of th e s ta r tin g p o in t. S im ilarly , th e c o -o rd in a te s o f th e firs t k ey pixel is given by th e se q u e n c e /4. B it l5 says w h e th e r th e G E b etw e en th e p o in ts re p re s e n te d b y /3 a n d l4 is a n a rc o r a s tra ig h t line. l5 = 0 for lin e a n d 1 for arc . If th e re is a n a rc , th e n th e fol
lo w in g se q u en c e l6 is c o n s id e re d to in d ic a te th e p o in t E (as in F ig u re 5); o th e rw ise , th e se q u en c e l6 will b e a b s e n t.
A s s o o n as a n a rc o r line is re c o n s tru c te d , th e p re c e d in g k ey pixel p o in t b ec o m e s th e n ew sta rtin g p o in t.
T h e p o in t d e s ig n a te d by th e fo llo w in g seq u en ce /4 th e n re p re se n ts th e new key pixel fo r fu rth e r re c o n s tr u c tio n .
T h e p r o c e d u re fo r d e c o d in g c o n tin u e s u n til th e n u m b e r o f G E ’s, as re p re se n te d b y th e se q u e n c e /2, is e x h a u s te d . A fter th a t, a new c o n to u r is s ta rte d w ith th e first b it as / t .
6. R e g e n e ra tio n te chnique
D u r in g th e d e c o d in g p ro c e d u re , if th e G E b e tw e e n tw o key pixels is fo u n d to b e a s tra ig h t line, th e n it is g e n e ra te d b y th e B re s e n h a m a lg o rith m as m e n tio n e d in S ectio n 2. If th e G E is a n a rc , th e B ezier c h a ra c te ris tic tria n g le s a re first o f all c o n s tr u c te d in o rd e r to g e n e ra te its q u a d r a tic a p p r o x i
m a te d v ersio n .
Recursive computation algorithm
T h e a lg o rith m fo r c o m p u tin g th e v alu es o f 2n d o r d e r B ezier a p p ro x im a tio n cu rv e u sin g a fo rw a rd d ifference sc h em e is d esc rib e d belo w . L et
y = a t 2 + bt + c
b e a p o ly n o m ia l re p re s e n ta tio n o f th e e q u a tio n (6) w h ere th e c o n s ta n t p a ra m e te rs a, b a n d c a re d e te r
m in e d by th e vertices o f th e B ezier c h a ra c te ris tic tr i
angle.
S u p p o se , a n u m b e r o f p o in ts (values o f y) o n th e a rc a re to be e v a lu a te d for e q u isp a c e d v alu e o f th e in d e p e n d e n t v a ria b le t.
T h e u su a l N e w to n ’s m e th o d o f e v a lu a tin g th e p o ly n o m ia l resu lts in m u ltip lic a tio n s a n d d o es n o t m a k e use o f th e p rev io u sly c o m p u te d valu es to c o m p u te new values.
A ssum e th a t th e p a ra m e te r t ran g e s fro m 0 to 1.
L e t th e in c re m e n ta l v alu e b e q. T h e n th e c o r
re sp o n d in g y valu es will be c, a q 2 + bq + c, 4 a q 2 + 2 bq + c, 9 a q 2 + 3bq + c , . . . . L e t us n o w fo rm th e d ifference ta b le (see T a b le 1). O b se rv e th a t
A 2yj = 2 a q 2 a n d
y J + 2 - 2yj + 1 + y,- = 2a <l2 fo r a l l ; > 0.
T h is le a d s to th e re c u rre n c e fo rm u la y 2 = 2 y x — y 0 + 2a q 2 th a t involves ju s t th re e a d d itio n s to get th e n ex t v alu e fro m th e tw o p re c e d in g valu es a t h a n d . T h u s o n e d o es n o t n ee d to s to re all th e p o in ts o n th e curve.
T ab le 1
D ifference tab le for recursive c o m p u ta tio n o f p o in ts o f Bezier curve
t V Ay A 2y
0 c a q 2 + bq 2 a q 2
q a q 2 + bq + c h a q 2 + bq l a q 1
2 q Aaq1 + 2 bq + c 5a q 2 + bq l a q 2 3 q 9 a q z + 3bq + c l a q 2 + bq
4 q 16 a q 2 + 4 bq + c
7. Im p le m e n ta tio n stra te g ie s
A fter c o d in g a single pixel w id th c o n to u r in p u t, the re g e n e ra tio n a lg o rith m as d escrib ed before is used to d e c o d e a n d result in its a p p ro x im a te d v e r
sion (o u tp u t) . D u rin g re g e n e ra tio n , the o u te r c o n to u r is o n ly trac ed using F re e m a n 's c h a in c o d e (clo ck w ise sense) a ssu rin g th e p o sitio n s o f key pixels o n it. In o th e r w o rd s, key pixels are c o n s id ered to be th e guid in g pixels (b ein g im p o r ta n t fo r p re se rv in g th e in p u t sh a p e) d u rin g re p ro d u c tio n .
It is to be n o te d th a t d u e to th e a p p ro x im a tio n schem e, so m e tim es th e follow ing u n d e sira b le s itu a tio n s m ay arise:
(1) T h e reg e n erate d c o n to u r m a y n o t have single pixel w id th .
(2) T h e key pixel m ay b ec o m e a n in te rio r pixel o f th e c o n to u r.
T o o v erc o m e these s itu a tio n s w e tra c e th e c o n to u r s from th e o rd e re d re g e n e ra te d d a ta set, c o n sid e rin g th e follow ing o p e ra tio n s.
A. Deletion o f pixels
D u rin g th e c o n to u r tra c in g if a pixel o n the c o n to u r finds m o re th a n o n e n e ig h b o u r in its 8 -n eig h b o u r h o o d d o m a in , then th e e x te rio r pixel o n th e c o n to u r is k ep t w hile d e le tin g th e rest (pixels o n th e in te rio r c o n to u r). But if th e re is a key pixel fallin g in su c h n e ig h b o u rh o o d , th e n th e key pixel is r e ta in e d as th e c o n to u r pixel a n d th e rest a re deleted . T h is e n a b le s us to keep th e key pixel alw ays o n th e c o n to u r, th u s m a k in g th e a p p r o x im a tio n o f th e in p u t b e tte r. F ig u re s 8(a) a n d (b) d e p ic t th e s itu a tio n s.
C o n s id e rin g ‘c ’ to be th e c u r re n t pixel a n d ‘p ’ th e p re v io u s pixel, th e c o n to u r (clockw ise) is ‘a ’ fo r a s itu a tio n as show n in F ig u re 8(a) b u t if th e s itu a tio n is as in F ig u re 8(b) th e n ex t pixel o n th e c o n to u r is th e n k (th e key pixel).
d
c k ->
d c
b b
a a
(a ) (b)
F igure 9. Shifting o f pixels: (a) c o n to u r before shifting, (b) con
to u r a fte r shifting.
B. Shifting o f pixels
S u p p o se a G E is g e n e ra te d a n d a k ey pixel is re a c h e d . N o w d u r in g th e g e n e ra tio n o f a following G E , its first d a t a p o in t m a y m a k e th e p rec ed in g key pixel lie o n th e in te r io r c o n to u r. F o r e x a m p le , con
sid er F ig u re 9 (a). H e re a b k is p a r t o f th e GE w hich is a lre a d y g e n e ra te d . N o w g e n e ra tin g the n ex t G E : k c d , . . . , th e first m o v e fro m k to c m a k es th e key pixel (k ) lie o n a n in te r io r contour.
In su c h cases, th e d a t a p o in t c is sh ifte d as shown in F ig u re 9(b). T h is p re se rv e s c o n n e c te d n e ss o f the pixel c w ith b o th th e G E ’s a n d also e n su re s single pixel w id th o f th e c o n to u r.
C. Undesirable loop
S o m etim es in th e v ic in ity o f k ey p ix e ls an unde
sira b le lo o p ( c o n to u r w ith a single p ix e l hole) may a p p e a r d u e to th e a p p r o x im a te d g e n e ra tio n proce
d u re . F o r e x a m p le c o n s id e r F ig u re 10. H e re GEs a k , k 2 k 3 a r e a lre a d y g e n e ra te d . T h e n ex t move fro m k 3 to b c re a te s a n u n d e s ira b le lo o p h av in g sin
gle pixel hole.
T o o v e rc o m e th is s itu a tio n , th e pix el b is shifted a lo n g w ith a n in s e rtio n o f a n ew pix el e (as shown
a a k j k 3
p c b p c b a k 2
e d e k
(a) (b) (a)
c e k i
(b) f ig u re S. D eletion of pixels: (a) in absence o f key pixel, (b) in
presence o f key pixel.
F ig u re 10. U n d e sira b le lo o p : (a) before clean in g , (b) after clea11' ing.
in F ig u re 10(b)). S in ce th e shiftin g o f b a lo n e loses the co n n e c tiv ity p r o p e r ty b etw een k 3 a n d th e su b se quent pixels, it n e c e s sita te s a n in se rtio n o f a new pixel w h o se lo c a tio n is g o v e rn e d by th e c o n c e p t o f m inim um c o n n e c te d p a th .
8. R esults an d discussion
F ig u re s 1 1(a), 12(a) a n d 13 sh o w th e d ig ita l c o n to u rs o f th re e d iffe ren t figures, n a m e ly , b u tte rfly , c h ro m o so m e a n d n u m e ra l-e ig h t, w h ich w ere co n -
0 0 0 0 0 0 0 3 0 0
0 0 0 0 3
0 0 0
0 o
3 0 0
3 0
3 0
3 3 3
0 3 3 0 0
3 0 0 0 0 0
3 0 0 0 0 3
3 0 0 3 z 0
0 0 0 0 0 0
0 0 0 0 0 0
0 G 0 3 0 0 0
0 0 3 3 0 0 0 3 0 0
3 3 3
3 i 9 9
• • •
• 9 9 • 9
I 3 •
9 9 9 3
• I 3
9 9 9 I «
• 3
• 3
• 3
3 9
3 I
3 •
• 9
• •
I I I3
• • 9
• 9 3
9 9 9
9 9 9
9 3
3 9
3 9
9 3 3 9
9 9 3 3 3 9
9 3 9 9 99 9
3 9 9
9 9 3 9 9 9
3 0 0 0
00 00 00
0 o e
0 0 X
e 3o
3 0 9
0
00 00
0 0
0 e
0 0 3
0e o e
X 9
0 0 0 0 0
0 0 0
3 0
0 0 0 0 e o d
0 0
3 0
0 0 X 3 X
3 0 0 0
0
0 0
3 I
0 0
0
0 0 0 3 0
3 0
00
0 0 3 0 0 0
0 0 00
0 3
00 00 0 03
0
F ig u re 11. (a) Butterfly in p u t, (b) R e g en era te d version, (c) R eg en erated v ersion before cleaning.
0 3 0 0
00 0
• • • 3 • t «
• •
• •
• •
3 •
: • •
• •
■ •
■
# X •
*
» •
• • 3 • •
• •t
• • 3 «
• •
« •
t « 3 •
F ig u re 12. (a) C h ro m o so m e in p u t, (b) R eg en erated version.
sid e re d as in p u t to the p ro p o s e d c o d in g schem es.
T h e k ey pixels a n d th e p o in ts o f inflexion as d e te cte d o n th e in p u t p a tte rn s are m a rk e d b y ‘3’ a n d
‘X ’ respectively.
In F ig u re 13, th e in p u t im age c o n to u r is r e p re se n ted by th e pixels m a rk e d ‘5’ a n d ‘0 ’ alo n g w ith
‘3’ d e n o tin g its key pixels. T h e o u tp u t c o rr e s p o n d ing to th e b u tte rfly a n d c h ro m o so m e im ages a re sh o w n in F ig u re s 11(b) a n d 12(b) respectively. T h e o u tp u t v e rsio n c o rre sp o n d in g to th e n u m e ra l-8 c o n to u r is m a rk e d by ‘5’ a n d *•’ in F ig u re 13 s u p e r
im p o s in g o n its in p u t. T h is su p e rim p o se d d ia g ra m facilitates o n e to ex am in e th e v isu a l p ro x im ity b e tw een th e in p u t a n d o u tp u t v ersions. I t is to be n o t
ed in th is c o n n e c tio n th a t th e p o sitio n s o f key pixels in b o th in p u t a n d o u tp u t re m a in u n a lte re d .
F o r c o d in g th e in p u t p a tte r n s , th e n u m b e rs of G E ’s in th e b u tte rfly , c h ro m o s o m e a n d n u m e ra l^
w ere fo u n d to b e 27, 19 a n d 16 resp ectiv ely . O u t of these figures th e n u m b e rs o f a rc s w ere 9, 16 a n d 16- T h e c o n to u r o f th e n u m e ra l-8, as ex p e c te d , h a s the m in im u m n u m b e r o f G E ’s a n d h a s n o s tra ig h t line- As a ty p ic al illu s tr a tio n , th e effectiveness o f the c lea n in g o p e ra tio n s (S e c tio n 7) p e rfo rm e d o n the g e n e ra te d p o in ts is d e m o n s tr a te d o n ly fo r th e but' terfly im age. F ig u re 11(c) sh o w s su c h a n interm e' d ia te s ta te b e fo rin g p r o d u c in g its final d e c o d e d on1' p u t. H e re , 0 d e n o te s a pix el d e le te d a n d ^ c o rre s p o n d s to th e p o s itio n w h ere a pix el is inserted to k ee p co n n e c tiv ity .
In o r d e r to s tu d y th e efficiency o f th e coding schem es, th e b it re q u ire m e n ts fo r d iffe ren t in p u t in1'
I I I I I S 3 S S I • • • I I S S 0 0 0 0 0 0 0 0 0 5 5 I I I
• • 5 0 0 0 0 0 5 5 M
• 5 0
• 0 • 0
• •00
• •00
• 0 0
• • • • 5 3 S S • • I I
• • • 0 0 0 0 O O O O I I I
• 5 0 0 0 0 0 0 5 *
• 0 0 •
5 0 •
5 0 C
• 0 0 0 5 1
• • 5 0 0 5 *
• 5 3 5 5 • 0 •
001
• • • 5 3 S U M
• • 0 0 0 0 0 0 0 5 5 *
• 00 05*
5 0 0 5 1
• 0
• 0 • 0
• 0
• 0
• 0
• 0 0 0
•••000
• • • 5
0 0 5 00 • 0 0 • • •
5 5 • •
5 •0 5 5 0
• 55 0 0
• •00
• • 5 0 0 0 0
• • • • 5 0 0 0 0
• • • • 0 0 5 5 5
5 5 5 3 5 5 5 * #
F ig u re 13. N u m eral-8 in p u t a n d its reg en erated o u tp u t together.
ages a n d th e ir rela tiv e c o m p re ssio n ra tio s a re c o m pared w ith th o se in th e C R L C a n d D L S C m e th o d s.
It is sh o w n in T a b le 2 th a t in th e p ro p o s e d te c h nique, th e b it re q u ire m e n ts are sig n ific an tly less. It is o b v io u s th a t th e n u m e ra l-8 im a g e c o n s istin g o f few la rg e a rc s o n ly p ro v id e d h ig h e r c o m p re ssio n ratio. T h e b u tte rfly im ag e o n th e o th e r h a n d , h as the la rg e st n u m b e r o f G E ’s a n d th u s p ro v id es lowest c o m p re s s io n ra tio .
As th e c o d in g sch em es a re a p p r o x im a te th e re g enerated im a g e d e v ia te s fro m its o rig in a l version.
To o b se rv e th e d e v ia tio n o f re g e n e ra te d im ag e q u a l
ity th ro u g h a n o b je ctiv e m e a su re w e h a v e ca lc u lat-
T ab le 2 Bit req u irem en t
Figure C R L C
Bit req u irem en t
D L S C P ro p o se d m e th o d
<5«i % (rel.
C R L C )
^rel % (rel.
D L S C )
Butterfly 799 531 435 183.67 122.06
C h ro m o so m e 1175 603 452 259.95 133.40
N u m eral-8 2085 1169 474 439.87 246.62
T a b le 3
E rro r in re g en eratio n
F ig u re % E rro r in a re a C o m p ac tn e ss
P ro p o se d O rig in al G en e ra te d
m eth o d figure figure
B utterfly 8.63 0.024635 0.025393
C h ro m o so m e 6.8 0.016061 0.016672
N u m e ra l-8 2.92 0.014728 0.014589
ed th e e r r o r in a re a a n d th e s h a p e c o m p a c tn e ss. F o r th e c a lc u la tio n o f th e a re a a n d th e p e rim e te r o f th e c o n to u r w e h av e used th e te c h n iq u e p r o p o s e d by K u lp a [12]. Since th e key pixels are alw ays o n th e c o n to u r a n d th e g e n e ra te d arc s a re b etw e en th e m a n d re s tric te d b y th e resp e ctiv e B ezier c h a ra c te ristic tria n g le s, th e m a x im u m e r ro r fo r a n a rc is th e a re a o f its p a ir o f B ezier c h a ra c te ris tic tria n g les. A lso, for th e a b o v e c o n s tra in t th e sh a p e c o m p a c tn e ss c a n p ro v id e a g o o d m e a su re o f th e d is to rtio n in tr o d u c e d in to th e d e c o d e d im ages. T a b le 3 show s b o th th e p e rc e n ta g e e r r o r a n d th e c o m p a c tn e ss o f figures.
I t is th u s seen th a t th e d e c o d e d im ag e in e a ch case is a faith fu l r e p ro d u c tio n o f its in p u t versio n . H e re to o , th e b u tte rfly /n u m e ra l-8 c o n to u r h a v in g th e la rg e s t/s m a lle s t n u m b e r o f G E ’s in c u rre d h ig h e st/
lo w est % e r r o r in th e ir re g e n e ra tio n .
F in a lly , it is to b e m e n tio n e d h e re th a t since th e re g e n e ra tio n p ro c e d u re uses th e q u a d ra tic B ezier a p p ro x im a tio n te ch n iq u e , th e d e c o d e d im age d is
p la y is very fast.
A cknow ledgm ent
T h e a u th o r s w o u ld like to th a n k M r. J. G u p ta a n d S. C h a k ra b o rty for re n d e rin g th e se creta rial help.
R eferences
[1] Proc. IE E E (1980). Special issue on C o m p u te r G rap h ics, Vol. 68.
[2] E k stro m . M .P ., Ed. (1984). D igital Im age Processing Tech
niques. A cadem ic Press, N ew Y ork.
[3] H u a n g , T.S. (1977). C o d in g o f tw o -to n e im ages. IE E E Trans. Com . 25. 1406—1424.
[4] P al, S .K ., R.A . K in g a n d A.A . H ash im (1983). Im age de
sc rip tio n a n d p rim itiv e ex tra c tio n using fuzzy sets. IEE E Trans. S yst. M a n C ybernet. 13 (1), 94 -100.
[5] P al, S .K . an d D . D u tta M a ju m d e r (1986). F uzzy M a th em a t
ical A pproach to P a ttern R ecognition. W iley, N ew Y ork.
[6] Bezier, P .E . (1974). M a th e m a tic a l a n d p ractical possibilities o f U N IS U R F . In: B arnhill, R .E . a n d R .F . Riesenfeld, Eds., C om puter A ided G eom etric Design. A cadem ic Press, New Y ork.
[7] B arskey, B.A. (1983). A d escrip tio n an d e v a lu a tio n o f va
rio u s 3-D m odels. In: K u n ii, T .L ., E d., C om puter Graphics (theory and applications). S p ringer, Berlin.
[8] B resenham , J.E . (1965). A lg o rith m for c o m p u te r co n tro l of a digital p lo tter. IB M S y ste m s J. 4 (1), 25 30.
[9] M o rrin , T .H . (1976). C h a in link co m p ressio n o f arb itrary black w hite im ages. C om puter Graphics and Im age Process
ing 5, 172-189.
[10] C h a u d h u ri, B.B. a n d M .K . K u n d u (1984). D ig ital line seg
m en t coding: A new efficient c o n to u r co d in g schem e. IEE Proc. 131 (4), P t.E , 143-147.
[11] P avlidis, T . (1982). A lgorithm s f o r Graphics and Im age Pro
cessing. Springer, Berlin.
[12] K u lp a, Z . (1977). A rea a n d p erim eter m easu rem en t o f blobs in discrete b in a ry p ictu res. C om puter G raphics and Image Processing 6, 434-451.
A ppendix A
P ro p o sitio n 1. In the discrete plane all the pixels on an arc between two k e y pixels remain al ways on or inside a right triangle with the line joining the key pixels as the hypotenuse. The other two sides o f the right triangle are the horizontal and the vertical lines through the k e y pixels.
P ro o f. W h e n th e key pixel is o n the h o riz o n ta l line a t x = c it follow s fro m th e d e fin itio n o f key pixel, th a t
e ith e r f ( c ) > f ( x ) o r f ( c ) < f { x )
in b o th th e in te rv a ls [kl - d^k^] a n d [k2, k 2 + <y w h e r e /(x ) is c o n s ta n t in [&i,/c2] a n d <51, 52 e {0,1}.
T h u s
(1) P ixels a t k 1 a n d k 2 a re e ith e r c o rn e r co n n ected o r d irec t c o n n e c te d o r its c o m b in a tio n to th e neigh
b o u rin g pixels o u tsid e th e in te rv a l [kx, k 2].
(2) W h e n k l = k 2 = c, th e key pixel will h av e at least o n e c o rn e r c o n n e c tio n to its n e ig h b o u rin g pixels.
A
F igure A l. An arc w ith its asso ciated right triangle.
S im ilar a rg u m e n ts h o ld w hen th e k ey pixel lies on a vertical line.
Let A N B be th e a rc w ith A a n d B b ein g tw o su c
c e ssiv e key pixels as sh o w n in F ig u re A l. N o w a p ix e l o n th e a rc c a n g o o u tsid e th e line A C o r B C i f a n d only if (1) th e re ex ists a se q u en c e o f co llin e a r p ix e ls such th a t its e n d pixels a re e ith e r c o rn e r c o n n e c te d o r d ire c t c o n n e c te d o r its c o m b in a tio n , o r (2) th e re exists a pixel w h ich h as a t le ast o n e c o rn e r c o n n e c t io n w ith its n e ig h b o u rin g pixel.
B o th th e se c o n d itio n s le ad to th e ex iste n ce of a n o t h e r key pixel o u ts id e th e lin e A C o r BC. T h is i s a c o n tra d ic tio n .
A p p e n d ix B
-4 Igorithm f o r ext ract ion o f k e y pixels
{?,■},"= i a re th e c o n to u r p o in ts in th e b in a ry
4 3 2
5 • 1
6 7 6
F ig u re B l. D irectio n al codes w ith respect to 9 .
im age a n d { ( x i, y i)}"=1 a re th e ir p o s itio n c o -o rd i
n ates. Since, fo r a closed c o n to u r, th e re is a p o ssi
b ility o f m issin g th e first k ey pix el we n ee d to e x a m ine a few m o re p o in ts a fte r th e s ta rtin g p o in t is re a c h e d so as to e n a b le o n e to g et th e sa m e b ac k .
St ep 1. S et / <- 1, c o u n t <- 1.
F in d th e in itia l d ire c tio n c o d e b etw e en a n d Pi + 1 a c c o rd in g to F ig u re B l . L et it be d 1.
S t e p 2. In c re m e n t i <- i + 1; if i = n go to S tep 7;
o th e rw ise find th e d ire c tio n a l c o d e b e tw e e n P t a n d F i+ L e t it be d 2.
S t e p 3. If dx = d 2 go to S tep 2; o th e rw ise if d t div 2 = 0 a n d d 2 div 2 = 0 o r if | d t — d2 1 = 3 o r 5 th e n re tu rn
St e p 4. In c re m e n t i < - i + 1; if i = n g o to S te p 7;
o th e rw ise find th e d ire c tio n co d e b etw e en P, a n d P i + 1 . L e t it be d 3.
S t e p 5. If d 3 = d 2 th e n c o u n t «- c o u n t + 1 a n d go to S tep 4; o th e rw ise if | d r — d 3 \ = 0 o r 1 th e n set c o u n t <- 1, d t < - d 3 a n d go to S tep 2 else d o S tep 6.
St e p 6. I f c o u n t div 2 = 0 th e n r e tu rn (x ; colim/2, yi - cou„t/2)o th e r w is e re tu rn (x j _ count 2 ^ 1 — count div 2) ’
St ep 7. S to p .
