A parallel algorithm for decomposition of binary objects through

(1)

Pattern Recognition L ette rs 12 (1991) 2 3 5 -2 4 0

North-Holland A pril 1991

A parallel algorithm for decomposition of binary objects through skeletonization

S.K. Parui

Electronics a n d C o m m u n ic a tio n S cien ces U nit, In d ia n S ta tistica l In stitu te , Calcutta-700035, In d ia

A. Datta

Computer a n d S ta tistica l Service C e n tre, In d ia n S ta tistica l In stitu te , Calcutta-700035, India

Received 25 S eptem ber 1990 Revised 9 Ja n u ary 1991

Abstract

Parui, S.K. an d A . D a tta , A p arallel alg o rith m fo r deco m po sition o f b inary objects th ro ugh skeletonization, P a tte rn Recogni

tion Letters 12 (1 9 9 1 ) 2 3 5 -2 4 0 .

A simple d ecom position tech n iq u e is p ro p o se d for b in ary objects. F irst a certain skeleton o f a b inary object is fo u n d and then the skeleton is d eco m p o sed in to co n n ected co m p o n en ts. Finally a sim ple o b ject p a rt is reconstructed from each such skeletal component. T he alg o rith m s p ro p o se d fo r sk eletonization an d recon struction are parallelizable.

Keywords. B inary ob jects, d e c o m p o sitio n , skeleton ization , connected com p onents, parallel algorithm s.

1. Introduction

Decomposition o f a p a tte rn o r o bjec ' ^ simpler

and

sm aller su b p attern s o r p a rts is useful in image processing a n d p a tte rn recog (Pavlidis, 1977). I n th is p a p e r, w e p resen t a si ^ technique for decom posing a b in a ry ° f ? * we object parts which are easier to deal w ith , ere ^ consider objects w hich m ainly consist o f elonga P^ts. Character p a tte rn s are o n e su c h exa^

decomposition here is b ased o n a c e rta in s e onization o f the o bject (P a ru i, 1 9 8 4 ). T h e s e e is first decomposed in to several co n n ected c P oints from w hich th e o b je c t p a rts a re t e ^

^constructed. T h e skeleton fin d in g a n d rec° I\

section algorithms are im plem entable o n o a ra

m achines. The skeleton in the analog case is defin

ed in the following way. For every point P in the object, all possible chords passing through it are considered and the chord with the m inim um length is chosen. I f P is the m id-point o f the m inim al chord, then P is a skeletal point. The skeleton of the object consists o f all such skeletal points and is n o t necessarily connected for a connected object (Figure 1).

2. Skeletonization o f a binary object

The input image here is represented as a 2-D b inary m atrix where the 0- and 1-pixels indicate the background and the object, respectively. F or

(2)

F ig u re 1. D ash ed lines indicate th e skeleton o f a re c ta n g u la r

object in the analog case. (a)

1 H V H 1 H

1 H (b>

1 1 1

V V V

1 1 1

1 1 V V V 1

sk eletonization we consider only the vertical an d h o rizo n tal runs o f 1-pixels. The length o f such a ru n is (n - 1) where n is the num ber o f pixels in the ru n (F ig u re 2). F or a run o f n 1-pixels, the m id  p ix e l o f the run is defined as the [(« + l)/ 2 ]- t h pixel

fro m th e start o f the run (th a t is, th e to p pixel for a vertical ru n an d the leftm ost pixel fo r a h o rizo n ta l ru n ) (Figure 2).

N ow the skeleton o f the object is fo un d in the follow ing way. F or every object pixel P we find the ru n s o f l ’s containing P only in vertical and h o riz o n tal directions (in the analog case all p o s

sible directions are considered). F rom am ong these tw o ru n s, we choose the one with the shorter ru n length. It is called the m inim al run containing P . If P is th e mid-pixel o f this m inim al ru n , then P is called a skeletal pixel. All such skeletal pixels co n stitu te th e skeleton. If fo r a skeletal pixel P , the length o f the corresponding m inim al ru n is m , th en we say th a t the object has thickness m at P.

T hus the m inim al runs are either vertical or h o rizo n tal. If the vertical and horizontal run lengths are equal, then the vertical run is co n

sidered first. If the corresponding pixel is not its m id-pixel, th en the horizontal ru n is considered.

E ach skeletal pixel is given a label depending on the m inim al ru n containing the pixel. A skeletal pixel em erging from a vertical m inim al run has label V. In the other case, the label is H . Thus, the pixels w ith labels V and H constitute the entire skeleton (Figure 3b).

3 3 3 * * * 3 3 3 3 3 3

1 1 1 1 1 1

(a)

1 1 1 1 1

<b)

11 11

(c)

• 3

• 3 4 • 4 ■

4 4 •

• 4 •

(c)

F ig u re 3. T h e orig inal p a tte rn is in (a ). Its skeleton is show n in (b ) w h ere the pixels w ith labels V a n d H form th e sk e leto n . The th ick n ess m ap fo r th e skeleton in (b ) is show n in (c ) w here the

n o n -sk eletal pixels are sh ow n as d o ts.

It can be seen th a t skeletal parts fo rm ed by the V-pixels indicate the h o rizontal parts (th a t is, parts m aking an angle betw een - 4 5 and 45 degrees with th e x-axis) o f the object an d those fo rm ed by the H -pixels indicate its vertical parts (th a t is, parts m aking an angle betw een 45 and 135 degrees with the x-axis). A p art from giving a label to every skeletal pixel, the thickness also is assigned to every skeletal pixel and is stored in w hat is called the th ickn ess m a p o f the skeleton (F igure 3c).

It is clear th a t a skeletal pixel can be fo u n d in

dependently o f o ther skeletal pixels and hence the skeleton finding can be parallelized. O n th e other h an d , the skeleton thus fo u n d is n o t necessarily con

nected for a connected object. All the 8-connected com ponents o f the V-pixels an d H -pixels present in th e skeleton are found. These com ponents will be used in the next section fo r decom posing the object into sm aller parts.

A digital curve S is defined as an 8-connected set o f pixels such th at every pixel except tw o o f S has exactly two 8-neighbours. The tw o pixels each having ju st one 8-neighbour are the end pixels of S-

F ig u re 2. T h e lengths of the ru n s in (a ), (b ) a n d (c ) are 5, 4 an d 3 respectively. T he m id-pixels are underlined.

Proposition 1. E very 8-co n n ected co m p o n en t in the skeleton as d e fin ed above is a digital curve

(3)

provided th e th ickn ess at skeleta l p ix e ls at a cross

ing or b ranching is m ore than 1.

(F or a 1-pixel thick ‘Y ’-like p a tte rn , all the o b ject pixels fo rm one single skeletal com ponent which is n o t a digital curve. This type o f patterns is not considered in this p ap e r.)

3. D ecom position

Note th a t the skeleton does not rem ain co n nected a t a crossing o r a sharp tu rn or a jo in t. A t these ju n c tu re s am ong o thers, the o bject is dis

connected fo r decom position. First the skeleton is decomposed in to connected com ponents an d then the o bject p a rts are reconstructed fro m these skeletal co m p o n en ts. Details o f the decom position technique are given below.

After c o n stru c tin g the skeleton, we locate the 8-connected co m p on en ts o f V ’s and H ’s. E ach such skeletal co m po nent (w hich is a digital curve) corresponds to a single simple p art o f the original object, an d these sim ple p arts can be reconstructed from the skeletal com ponents and th e thickness map. This is possible by recovering the m inim al run containin g every skeletal pixel and tak in g the union o f all such m inim al runs. N ote th a t this can be done in p arallel since th e reco n stru ctio n from one skeletal pixel does not affect the reco n stru c

tion from an y o th e r skeletal pixel.

It can be seen th a t the skeletal pixels do n o t span the whole o b je c t. In other w ords, there m ay be some object pixels o r parts which do n o t fall on the m inim al ru n o f any skeletal pixel. In Figure 3, the skeleton is d ecom posed into fo u r com ponents from which th e o b ject p arts can be reconstructed.

But here th e m iddle p a rt o f the to p o f the ob-

1 H 1 1 H 1 1 H 1 1 H 1 1 1 H 1 1

1 H 1 1 1 1 1 1 1 1 1 1 1 1 1 1 V

1 H 1 1 V V V V V V V V V V V V 1

1 H 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 H 1 1

(a) (b)

% u re 4. A b o v e a r e th e tw o p a rts a fte r deco m p o sin g the o b ject ln Figure 3a u sin g th e m u lti-p ass alg o rith m (A lg o rith m 1).

ject is not spanned by th e skeleton. (T h o u g h the skeleton contains in fo rm a tio n ab o u t the overall shape o f the o b je c t.) A n o th er problem is th a t there m ay be som e object pixels which are span ned by m o re th a n one skeletal co m ponent. F o r exam ple, in Figure 3b, the object pixels spanned by tw o V- pixels in the b o ttom left p art are also spanned by the H -pixels. Both these problem s during rec o n struction can be overcom e if a m ulti-pass (ra th e r th a n one-pass as discussed ab ove) reconstruction algorithm is used which runs as follow s.

A lgorithm 1

Step 1. Set A = th e w hole object.

Step 2. Find the skeleton o f A in the w ay described in Section 2. A lso, find the thickness m ap o f the skeleton.

Step 3. Find the connected com ponents o f V- an d H -pixels in the skeleton. C hoose the com p o n en t C th a t has th e m axim um length. If th is length is not large enough, stop . O therw ise, go to Step 4.

Step 4. F rom C an d the thickness m ap, reco nstruct only th a t p a rt o f the object th a t corresponds to C. Call the reconstructed object p a rt R.

Step 5. Rem ove the pixels o f R from A . Set A = A - R . G o to Step 2.

N ote th a t only Step 3 in the above algorithm is sequential while the other steps are parallel since they involve only local op erations. As is clear from above, the num ber o f passes in the m ulti-pass algorithm is the sam e as the num ber o f the object p arts th at the algorithm produces. F or exam ple, fo r the object in Figure 3a, tw o passes are needed.

In the first pass, the skeletal com ponent o f H - pixels is the com ponent w ith the m axim um length (F igure 3 b ). The reconstructed p a rt R is shown in Figure 4a. In the second p ass, there is only one skeletal com ponent (F igure 4 b ) which indicates the u p p er horizo ntal p a rt o f th e o bject. T he one-pass alg o rith m on the o th er han d w ould have u n fo r

tu n ately produced m ore th a n tw o p arts a fte r decom posing the object in Figure 3a.

Now it should be no ted th a t decom posing th e skeleton into connected co m pon en ts using only th e d irectional labels (V or H ) m ay n o t be enough fo r

(4)

P A TT E R N R E C O G N IT IO N l.liT T L R S A p r i l 1991

1 1 1 1 1 1 1 1 1 1 1 1 1

V V V V V V V V V V V V V V V V V V V V 1 1 1 1 1 1 1 1 1 1 1 11 11 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1

(a)

1 1 1 1 1 i i

v v v v v v v

1 1 1 1 1 i i

1 1 1

1 1 1 1 1 1

V V V V ' ' V V V V V V V V V V V 1 1 1 1 11 1 1 1 1 1 1 1

1 1 11 1 1 1 1 1

1

(•>)

6 6 6 6 6 6 6 6 6 2 2 2 2 2 2 2 6 6 6 6 6 6 6 6 6 5 6 6 6 6 6 6 6 6 6

(b) (b)

1 1 1 1 1 1 111 1 1 1 1 1 1 1 1 1 1 1111

1 1 1 1 1 1 111 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 111 1111111 1 1 1 1 1 1 1 111 111 1 1 1 1 1 1 1 1 1 1111

1 1 1 1 1 1 111 1111111 1 1 1 111 111 1 1 1 1 1 1 1 1 1111

1 1 1 1 1 1 111 1 1 1 111 111 1 1 1 1 *

1 1 1 1 1 1 111 1 1 1 1 1 1 1 1

(c)

F igure 5. (a ) A n object where its skeleton (V -pi.\els) has only one co nnected com p on ent, (b ) T he thickness m ap o f the skeleto n in (a ) w here th ere are tw o pairs of ad jacen t pixels w ith thickness d ifference 4. T he skeletal com pon ent is decom posed in to su b c o m p o n en ts a t these two pairs o f pixels, (c ) T h e object

is co rrespondingly split into three object parts.

( = >

F ig u re 6 . ( a ) A n o b je c t w here its skeleton (V -pixels) has only o n e c o n n e c te d c o m p o n e n t, (b ) T h e th ick ness m a p o f the sk e le to n in ( a ) w ilh a lo cal m in im u m a t (h ickn ess = 2 where the sk e letal c o m p o n e n t is d e c o m p o s e d in to tw o subcom pon ents, (c)

T h e ob ject is c o rre sp o n d in g ly split in to tw o parts.

m eaningful decom position o f the object (Figure 5).

T he thickness m ap can be useful in such cases.

Since a skeletal com ponent is a digital curve (from P ro p o sitio n 1), its pixels can be scanned in a linear fashion . T hrough such a scan o f the pixels their thickness values can be exam ined sequentially. If w ithin a single skeletal co m ponent, tw o adjacent pixels have significantly different thickness, then th e co m p o n en t is split into tw o betw een these tw o pixels (Figure 5b). But som etim es the difference in thickness is n o t significant aro u nd a skeletal pixel w here the object should be split (F igure 6 ). In such cases the local m inim a in thickness values can be fo u n d . A t these local m inim a the skeletal com po

n en t can be split (Figure 6b ).

N ow A lgorithm 1 can be m odified to incor

p o ra te the thickness-based skeleton splitting criteria discussed above. The m odified algorithm is given below.

A lgorithm 2

Step I. Set / l= th e whole object.

Step 2. Find the skeleton o f A in the way de

scribed in Section 2. A lso, find the thickness map o f th e skeleton.

Step 3. F ind th e connected com ponents of V- a n d H -pixels in th e skeleton. Split each such com

p o n en t into su bcom po nents using the thickness m a p as discussed ab ove. F in d the subcom ponent C th a t h as th e m axim um length. If this length is not large en ough, sto p . O therw ise, go to Step 4.

Step 4. F rom C an d the thickness m ap, re

c o n stru ct only th a t p a rt o f th e o bject th a t corres

pon ds to C. Call the reco nstru cted o b ject part R-

1 H 1 H

i " i i ” i

! „ t i i v v v

\

²

]

1 1 V 1 1

; 1 i v i i

H 1 1 V 1 1

1 H 1 1 1V 1 1

i n i 1 1 V 1 1

5 ! V V V 11

I I I

(a) <b>

F igu re 7 . T w o digital rectang les (vertically o rien ted in (a ) an(^

o rien ted a t 4 5 degrees in (b )) h ave d iffe re n t skeletons.

(5)

1 1 1 1

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1

(C)

1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1

1 1

(b) (d)

Figure 8. (a ) A dig ital im age o f the ch aracter ‘H ’ a n d (c ) a digital im age o f a ch ro m o so m e (ta k e n from R osenfeld an d K ak (1 9 8 2 )).

T h e d eco m p o sed p a rts o f (a ) an d (c ) using th e m ulti-pass alg o rith m a re show n in (b ) an d (d ), respectively.

Step 5. R em ove th e pixels o f R from A . Set A - A - R. G o to Step 2.

4. Conclusions

It can be seen th a t the skeletonization and re

construction p a rts o f the decom position algorithm proposed in th e present paper can be im plem ented on a parallel m ach ine while finding the skeletal components a n d th eir lengths involves sequential computations.

The skeleton p ro p o sed above has the d isadvan

tage of being depen d en t on the o rien tatio n o f the input p attern (F ig u re 7). In the d efin itio n o f a skeletal pixel in Section 2, only tw o directions (vertical and h o riz o n ta l) are considered. I f four directions (in clu d in g the diagonal directions) are considered in stead , the skeleton in m any cases becomes 2-pixel th ick and P ro p o sitio n 1 no m ore holds.

T he above skeletonization and decom position algorithm s can easily be extended to 3 dim ensions.

Instead o f tw o directions (vertical and ho rizon tal), three ortho go nal directions are to be considered in 3 dim ensions. T here are two possible definitions o f a skeletal pixel in this case. F o r every object pixel P, consider the three runs o f 1-pixels (containing P ) in these three directions. If P is in the m iddle o f the m inim al ru n, P is a skeletal pixel. T he other possible d efinition is as follow s. F or every object pixel P, consider the three cross-sections consisting o f 1-pixels (con tain in g P ) in th e three directions.

C hoose th e cross-section w ith the m inim um area (th a t is, th e m inim um num ber o f 1-pixels). If P is in the m iddle o f the m inim al cross-section, P is a skeletal pixel. In the case o f the first definition , the skeleton will be a 1-pixel th ick digital surface and in the case o f the second, it will be a 1-pixel thick digital line in 3 dim ensions.

T he skeletal decom positio n technique proposed above can have applications in character recogni-

(6)

tio n , ch ro m o so m e analysis, curve segm entation, etc. (F ig u re 8 ).

R eferences

P a v lid is, T . (1 9 7 7 ). S tru c tu r a l P a tte rn R e c o g n itio n . S prin ger, B erlin .

P a r u i , S .K . (1 9 8 4 ). S o m e stud ies in an aly sis a n d reco g n itio n o f 2 -d im e n s io n a l sh a p es. P h .D . T hesis, In d ia n S tatistical In stitu te .

R o s e n fe ld , A . a n d A .C . K ak (1 9 8 2 ). D ig ita l P ic tu re P ro cessin g , V ol. 2. A ca d e m ic P re ss, N ew Y o rk .