lanxicy.com

第一范文网 文档专家

第一范文网 文档专家

Image Coding by Morphological Skeleton Transformation

Ryszard S. Chora~ Institute of Telecommunications, Technological Academy 85-763 Bydgoszcz,Poland

Abstract. Mathematical m

orphology operations are becoming increasingly important for analysing images. Binary morphological operations of dilation and erosion have been successfully extended to gray-scale image processing. This paper presents the results of a study on the use of morphological set operations to represent and encode a discrete binary and gay-scale image by parts of its skeleton and reports the results of image coding.

1 Introduction

Mathematical morphology, which is based on set-theoretic concepts, extracts objects features by choosing a suitable structuring shape as a probe. More images are transmitted over a network in order to process and to examine the data. The time taken for archiving, the cost of communication, and the limited bandwidth of transmission lines are reasons which lead us to examine the data compression of images. Usually, we use classical techniques such as predictive coding and transform coding. The morphological skeleton provides a complete and compact description of an object and the algorithm to find this skeleton is simple.

2 Theory

A binary image B is a mapping defined on a certain domain D c Z 2 and taking its values in { 0,1 }. The domain D of B is generally rectangular. We fix an origin O in a subset A of Z 2 , and then every point p of A defines a translation, the one mapping O to p ; we call it the translation by p. A p denotes the translated set A p c Z ~4th respect to the vector p ~ Z : Ap = { a + p : The complement of set A is denoted a e A }

(1)

Ac = { a E Z 2 : a e ~ A }

(2)

217

The symmetric set ( transposed set) with respect to the origin O =(0,0) X = { -a 9 a c A } (3)

Let A and B be two subset of Z'- . The set B is called the structuring element is often considered as a " moving " set, which is used as a probe. We call the origin O the centre of structuring element B. The definitions of the basic morphological operations are defined as follows. The Minkowski set addition of the set A, B G Z 2 is the set

A 9 B = {a+ b aeA,bEB}=~/B~=U

aEA b~B

(4)

The Minkowski set subtraction of B from A is the set A OB=(A~ @B)~ 2'VbEB,x-b~A}=(~Ab

beB

={xeZ The transformation

(5)

dB ' A ~ A @ g is called the dilation by B, and the transformation eB 9 A - ~ A | is called the erosion by B.

= { a'Ba ~ A r

} =~,.J Ab

b~g

(6)

B--= { a 9 Ba G A } = ('~ A b b~g

(7)

The opening and the closing of A by B, respectively denoted o B(A) and ca(A), are defined as follows: o B(A)= dg(e B(A))=(A |

~ U

Bx Bx )

(8)

(9)

cB(A)= eg(dB(A))=(A @ B ) |

B~GA~

Figure 1 illustrates an example of a dilation, erosion, opening and of a closing by a square. Let nB designate the ( isotropic ) structuring element of radius n Mth respect to the digital grid nB= B@B@B| ........ @ B The dilation and erosion of a set A e Z 2 by nB can be expressed by A| = { p ~ Z 2 d (p,A)<n } (10)

218

A |

c) > n }

(11)

where the distance between two pixels is the minimal length of the paths joining them and included in digital grid The digital grid, provides the neighborhood relationships between pixels e.g.: Pl is a neighbor of p2 if Pl e { p2 } | B. d ( Pl, P: ) = inf { 1 (P), P path joining Pl and P2 in digital grid } V (pl,p2)eZ2xZ 2

A

B

e

B

d

B

o

B

c

B

Fig. 1. An example of a erosion, dilation, opening and closing of a set A by a structuring element B.

For gray - images the basic operations have to be redefined. Let f (i,j) be a finite graytone image function on Z2 , and let g (i,j) be a fixed graytone pattern called a function structuring element. The umbra of two-dimensional image f ( i , j ) , is a three dimensional function U ( i, j , k ) with U(i,j,k)=l if k < f ( i j ) (12)

We can apply binary morphological transforms to the umbra with a structuring element which is also a binary set B ( i, j , k ). The dilation and erosion are defined as follows DB f ( i , j ) = U @ B s EB f(i,j) = U | s (13) (14)

If the structuring element B is a non-zero function on a limited field, the following propositions given an alternative method of computing dilation and erosion DBf(i,j)=max{ f(il, jl)+B(il-i, jl-j):il ,jl EBi,j } eBi.j } (15) (16)

EBf(i,j)=min{ f(il, jl)-B(ii-i, jl-j):il,jl

The basic morphological transformation of an image f(ij ) by a function structuring element g(i,j ) are ;

219

Dgffi.j)=max { f(i-x,j-y)+g(i,j):(i,j) Egfi(i,j)=min { f ( i + x , j +y)-g(i,j): (i,j) e D} ~ D ~,

(17) (18)

The openpTg 0 and closing C o f f ( i.j ) by B are given by Os f ( i 3 ) = { ( f | (i,j)@B } (i,j) (19)

EB f(i,j) = { ( f @ B ) ( i , j ) | B } ( i , j ) All these operators are translation-invariant

(20)

3 Binary and gray-scale morphological skeleton

Using morphological erosions and openings, a finite image can be uniquely decomposed into a finite number of skeleton subsets and then the image can be exactly reconstructed by dilating the skeleton subsets. For images containing blobs and large areas, the subsets are much thinner than the original image. The set S = w Si is called the binary morphological skeleton and is defined as :

1) A o = A

2 ) Ai = E Ai-1 3) Si=Ai_l -OAi-1

(21)

(22) (23)

We iterate the process until Ai. ] = 0. ff B is symmetric ( i.e. B = B ) like the square or rhombus, then S is the well-known ( discrete ) medial axis of X. We immediately see that knowledge of S allows us to completely restore the original set, and the general formula is A = w(Si| i) (24)

where B i is the result ofi - 1 dilations on the structural element B. In Fig.2 we plot the skeleton obtained for a given set. For the image f ( i, j ) we have the series of erosion fn = EIn-~ ( i , j ) with fo ( i , j ) = f ( i , j ) . The skeleton at the step n is the set difference between fn-~ u.ith the result of an opening operation on it Sn ( i , j ) =f,_~ ( i , j ) - O f , _ ~ ( i , j ) The complete skeleton is the series: (25)

(26)

220

S~ , S2, S~,. ......... Sn

(27)

where n = max { n > 0 : f ( i ,j ) | B n ~ 0 } and B" is the result of n - 1 dilations on the structural element B. An exact restoration can be obtained by f(i,j) = D ..... ( D ( D S n ( i , j ) + S n . l ( i , j ) ) ) ) ..... + S ( i , j ) (28)

1 11

11111 111111 111111 1111 11 A 111 111 111

'1

222 22 11 B

11 1 1

S=US

Fig. 2. The binary morphological skeleton of A by B

4

Image coding by morphological skeleton transformation

We have chosen for the experiment image LENA as shown in Fig.3. The binary. image ( Fig. 3a ) showing a face shape can be reduced by its binary morphological skeleton transformation. The structuring element B used in this example is the square 5 x 5 elements. In Fig. 3b we see the composition of the skeleton S as the union of the skeleton subsets Si. We can also represent image with Fig. 3d by its morphological gray-scale skeleton ( Fig. 3e ). The skeleton image includes two kinds of information : the skeleton positions and the skeleton values. The skeleton positions are coded by using the quadcode and their values are coded sequentially by Huffman's code. The quadcode is an information-compact coding system. It combines the coordinates of two dimensions into one code. The quadcode is a quaternary digital system used in describing images. When the quadcode is used in describing image, each character represents one operation of subdividing the image or its subimage into quadrants and after each subdivision the length of the quadcode increases by one. Huffman's code is based on the data distribution. We consider image as a sample function of a 2-D stochastic process characterized by joint probability distributions of all orders. The mean number of bits for a pixel is close to the entropy H. We code the image by encoding the runlengths, use the Huffman's code.

221

Fig. 3. Binary (a) and grayscale (d) image LENA 9binary (b) mad grayscale (e) morphological skeleton S a n d binary. (c) and grayscale (f) reconstructed image.

222

The compression rate cannot exceed 16. The compression efficiency is dependent upon how "thin" the skeleton image is. Coding of the image in Figure 3a and 3d gave respectively compression ratio 6.5 and 14.3.

5 Concluding

remarks

In this paper we have endeavoured to develop morphological transformations to image processing / analysis. Morphological transformations are based on the principles of mathematical formalism. This makes them well suited for shape analysis or extraction of geometrical and topological features from image objects. It also helps to obtain the solution of a class of problems directly from their statement as a morphological operation. We have mentioned only a few among the numerous applications of morphological transformation to image processing / analysis. Erosions, dilations and the rest of the morphological transformations ( which are combinations of erosions or dilations ) are defined by logical operations on sets / functions representing images. More and more often, images are transmitted over a network in order to process and examine the data. The time taken for archiving, the cost of communication, and the limited bandwidth of transmission lines are reasons which lead us to examine the data compression of images. Morphological compression method is very. powerful and also helpful to the research of any shape. Because there exist relations between the compressed data and the geometrical parameters of an object ( the maximum eroding step gives us the approximate size of an object, etc. ), so the compressed data can be used directly for transmission, detection, classification and recognition.

6 References

1. G, Matheron: Random sets and integral geometry. New York: Wiley 1975 2. J. Serra: Image analysis and mathematical morphology. New York: Academic 1982 3. S.R. Sternberg: Grayscale morphology. Comput. Vision, Graph, Image Processing 35, 333 - 355 ( 1986 ) 4. R.M. Haralick, S.R. Sternberg, X. Zhuang: Image analysis using mathematical morphology. IEEE Trans. Pattern Anak Machine Intell. PAMI-9, 523 -550 ( 1987 ) 5. P. Maragos, R.W. Schafer: Morphological filters - Part I: Their set theoretic analysis and relations to linear shift - invariant filters. IEEE Trans. Acoust. Speech, Signal Processing ASSP - 35, 1153 - 1169 ( 1987 ) 6. P. Maragos, R.W. Schafer: Morphological filters - Part II : Their relations to median, order - statistic, and stack filters. IEEE Trans. Acoust. Speech, Signal Processing ASSP- 35, 1170 - 1184 ( 1987 ) 7. P. Maragos, R.W. Schafer: Morphological skeleton representation and coding of binary images. IEEE Trans. Acoust. Speech, Signal Processing ASSP - 34, 1228 - 1244 ( 1986 )

相关文章:

- Mathematica图像处理命令集
*ImageTransformation*?*Image*Perspective*Transformation*? ... 颜色处理 ? Colorize...*SkeletonTransform*? Thinning ? Pruning ?*Morphological*BranchPoints*Morphological*...

更多相关标签:

- Morphological Representation of Wavelet Data For Image Coding
- Cellular neural network for image compression by adaptive morphological subband coding
- Partitioning Morphological Wavelet Image Coding
- Morphological Pyramid Image Registration
- Color image segmentation based on automatic morphological clustering
- High Performance Embedded Morphological Wavelet Coding
- Encrypting the compressed image by chaotic map and arithmetic coding
- reference [3] Image Compression by B-Tree Triangular Coding
- Analog VLSI Arrays for Morphological Image Processing
- Morphological grayscale reconstruction in image analysis Applications and efficient algorit
- Reduction of block-transform image coding artifacts by using local statistics of transform
- Image Compression by Parameterizod-Model Coding of Wavelet Packet Near-Best Bases
- Variable Block-size Image Coding by Resource Planning
- Improvement on Image Transform Coding by Reducing Interblock Correlation
- Morphological Motion Field Representation for Region-Based Image Sequence Coding y