Luận án tiến sĩ: Texture- and structure-based image representation with applications to image retrieval and compression

BOSTON UNIVERSITY COLLEGE OF ENGINEERING Dissertation TEXTURE- AND STRUCTURE-BASED IMAGE REPRESENTATION WITH APPLICATIONS TO IMAGE RETRIEVAL AND COMPRESSION ZHIHUA HE B., University of Electronic Science and Technology of China, 1999 M., Drexel University, 2002 Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy 2007 UMI Number: 3246606 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted. Also, if unauthorized copyright material had to be removed, a note will indicate the deletion.

® UMI UMI Microform 3246606 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P.

Box 1346 Ann Arbor, MI 48106-1346 Approved by First Reader Associate Professor of Electrical and Computer Engineering Second Reader W. Clem Karl, Ph. Professor of Electrical and Computer Engineering and Professor of Biomedical Engineering Third Reader Janusz Konréd, Ph. Associate Professor of Electrical and Computer Engineering 2 Fourth Reader Ủ—.- Stan Sclaroff, Ph.

Associate Professor of Computer Science Acknowledgments I am usually not good at writing acknowledgment, one reason is that I am never good at writing, and another reason is that I believe action speaks more for words. However, when I look back over all these years I spent in schools, I do realize that I owe lots of thanks to people along the way. First, I would like to thank my parents, ShuiBao He and Yong Xu. They have provided me with a stable home, without which I can never dream of getting advanced education; especially thanks for my father, who gave me a dream of being a scientist from my early childhood.

I definitely want to thank my brother, Zhipeng He, who takes the responsibility to take care of the family while I am away from home. Then, a special thank goes to my PhD adviser, Dr. Without her continuous support, I will not be able to come here for my PhD research. Without her guidance and patience, I can hardly imagine how I could get through the PhD research alone.

I will not forget the warmth brought by her in those cold winters. I also want to thank Dr. Arkady Kopansky, my first office-mate here, who has been always willing to help and answer the questions. Here, I want to thank my committee members: Dr.

Stan Sclaroff, Dr. Janusz Konrad and Dr. Thank you for your careful reviews and valuable comments. In the mean time I would also like to express my gratitude to all my teachers from primary school to college.

You have led me step by step into the science world, and have shown me how to approach problems from different aspects. Finally, I want to express my gratitude to all my friends, life will be so lonely and so boring without you guys! It is really hard for me to name all of you here, but I want to let you all know that I really appreciate your love and care, and I will always be willing to share mine with you. Below I want share my special thanks to Fang, Doreen, Violet, Shuang and Ling. Thank you for being there with me always.

iii TEXTURE- AND STRUCTURE-BASED IMAGE REPRESENTATION WITH APPLICATIONS TO IMAGE RETRIEVAL AND COMPRESSION (Order No. ) ZHIHUA HE Boston University, College of Engineering, 2007 Major Professor: Maja Bystrom, Ph., Department of Electrical and Computer Engineering ABSTRACT The design of an efficient image representation methods using small numbers of features can facilitate image processing tasks such as compression of images and content-based retrieval of images from databases. In this dissertation, three methods for capturing and concisely representing two distinguishing characteristics of images, namely texture and structure, are developed. Applications of these compact representations of image characteristics to image compression as well as retrieval of images and hand-sketches of images from databases are given and performance is compared with other compression and retrieval methods.

The first method to be introduced is a directional, hidden- Markov-model-based method for succinctly describing image texture using a small number of features. This method employs the well known, multi-scale contourlet and steerable-pyramid transforms to isolate in different subbands the edges that comprise the image texture. Statistical inter- and intra- subband dependencies are captured via hidden Markov models, and model parameters are used to represent texture in small feature sets. Application of this method to content- based retrieval of images with homogeneous textures from database is shown.

At the similar computation cost, about 10% higher retrieval rates over comparable methods are 1V demonstrated; when approximately one third fewer features are used, similar retrieval rates can be obtained using the proposed method. A method for concisely describing large image structures, that is, significant image edges, is then proposed. This method decomposes an image using the contourlet transform into directional subbands which contain edges of different orientations. Each subband is then projected onto its associated primary and orthogonal directions and the resulting projections are filtered and then modeled using piece-wise linear approximations or Gaus- sian mixture models.

The model parameters then form the concise feature sets used to represent the image’s structure. An application of this image-representation method to retrieval of images from databases based on users’ sketches of the images is shown. An retrieval rate increase of 138% using the proposed method is demonstrated over a current spatial-histogram-based method. Finally, a new multi-scale curve representation framework, the chordlet, is constructed for succinct curve-based image structure representation.

This framework can be viewed as an extension to curves of the well known beamlet transform, a multi-scale line repre- sentation system. In this dissertation, the representation efficiency, in terms of bits versus distortion, of the chordlet transform is compared with that of the beamlet transform. An algorithm for performing a fast chordlet transform has been developed. A chordlet-based coding system is constructed for application of the chordlet transform to compression of image shapes.

By using the proposed method increased compression is obtained at lower distortion when compared with two well known methods. Contents 1 Introduction 2 An Overview of Multi-scale Representation 2. Q Q Q Q Q H H n H Hán nàn kg K N ko Na 2. QC Q Q HH HQ Q ng gu kh k k gia 10 2.3 Gaussian Pyramid and Laplacian Pyramid.4 Wavelet Transform and Wavelet Packets.5 Directional Multi-Scale Transform .1 Steerable Pyramid Transform.

Q Q Q Q Q HQ Q HH k k vn ngà k kh kg va 24 2. QC HQ HQ HQ HH HQ n nk v v v kk k k k kia 27 2. QC Q Q Q Q HH HQ Q n v v v g V k kia 29 2.6 Multi-scale Line and Curve Representation .1 Background on Hidden Markov Models.2 Texture Representation using Directional HMMs in the Contourlet Domain 40 3.1 HMM Exploiting Luminance In-band Directional Dependencies in Contourlet Domain.2 HMM Exploiting Luminance Cross-scale and Directional In-band De- pendencies in the Contourlet Domain. HMM Exploiting Color In-Band Directional Dependencies in the Contourlet Domain.

c c c Q Q Q Q kg HQ Q V2 La vi 3.4 HMM Exploiting Color Cross-Scale Dependencies in the Contourlet Domamn. Q Q Q Q Q Q Q Q HH ng kg VN kia 50 3.3 Rotation-Invariant Texture Representation Using an HMM and Exploiting In-band and Cross-band Dependencies in Steerable Pyramid.4 Applications to Texture-Based Retrieval .41 Non-Rotation-Invariant Texture-Based Retrieval .2 Rotation-Invariant Texture-Based Retrieval.1 Structure Representation Using Directional Projection .1 DP-SR Framework.4 Low-Pass Filtering of 1D Profiles.2 Application to Sketch-Based Image Retreval.1 DP-SR-I: Piece-wise Linear Profile Modeling and Similarity Measure- ment. DP-SR-II: Non-linear Gaussian Mixture Profile Modeling and Simi- larity Measurement. Q Q Q Q HQ ee ee 80 4.

83 Curve Representation Via the Chordlet 86 5. uc Q Q Q n HH HQ na ng vc k k k KV Vk k kà 86 5. HQ HQ va 87 5.QQ ee ee 91 5.3 Comparison Between Beamlet and Chordlet for the Representation Efficiency 93 5.00 bee ee ee 94 vii 5.2 Curve Representation Via Chordlet and Beamlet Elements .3 Comparison and Discussion .4 Implementation of the Chordiet Transform.1 Construction of FEFI-based Chordlet .42 Direct Chordlet Versus FFT-Based Chordlet .4 Savings Due to Combination of the Direct Chordlet and the FFT- based Chordlet Transform.5 Is the Estimated Computational Cost for the Direct Chordlet and FFT-based Chordlet Transforms Consistent with the True Value? .5 Chordlet Coefficient Significance Model .1 Coefficient Significance Model. HQ HQ cv ng VN v kg kia 5.

Q Q Q LH HQ na HH ng ng kg kg k N k kia 5.6 A Thresholding-based Chordlet Representation System.1 An Image Structure Representation System .2 Simulation and Discussion. ee ee ee 5.7 Rate-Distortion Based Multi-Scale Chordlet Representation Systems .2_ Eundamentals and Defnitions. Mono-Scale Chordlet Representation.4 Multi-Scale Chordlet Representation. Q HH ng ng.

ng và kg và và 5.81 Chordlet-Based Representation Coder. ce kg cv cv g A k k V lv k V va 5.2 Chordlet Dictionary Slz€.3 The Definition of Curvature.4 The Proof of Lemma l. c Q QQ HH HH He.5 The Optimal Line Approximation fora SmoothCurve .7 A Lower-Bound for the Average Number of Beamlets Required for a SmoothCurveSegment C,; in an N x N Lattice Grid .8 The Proof of Lemma3. ee ee ee 171 5.9 The Proof of Lemma 4.10 The Proof of Lemma5.11 The Proof of LemmaÖ.

KH Q HQ Ho 177 6 Contributions and Future Work 180 6. cu HH nà gà Q v cv KV k KV k va 180 62 EPuture WOrk. Q c Q Q Q Q k H n nu vn v k k k v v kk kia 182 References 184 Curriculum Vitae 190 1X List of Figures 11 Example of texture images. 2 1-2 An example of sketches and corresponding images.

(b)-(c) Two sketches of Flower 1. (e)-(£) Two sketches of Flower 2. 6 21 A block diagram of a three-level Gaussian pyramid. 13 2-2 An example of a three-level Gaussian pyramid decomposition of image Lena.3 A block diagram of a two-level Laplacian pyramid.4 An example of a two-level Laplacian pyramid decomposition of image Lena.

15 2:5 An illustration of the analysis and synthesis filter bank. (a) Analysis filter bank. (b) 5ynthesis filter bank. ee ee 17 2-6 A block diagram of a two-level wavelet pyramid.

18 2:7 An example of a two-level wavelet decomposition of image Lena. 19 2-8 A block diagram of a two-level wavelet packet pyramid. 21 2:9 An example of a two-level wavelet packet decomposition of image Lena. 22 2:10 A block diagram of a two-level steerable decomposition.

24 2-11 An example of a two-level steerable pyramid decomposition of image Lena. 25 2-12 A block diagram of a two-level contourlet decomposition. 30 2-13 An example of a two-level contourlet decomposition of image Lena with subbands labeled according to the block diagram in Fig. 31 2:14 An illustration of the representation of a curve using wavelet, curvelet /contourlet, beamlet and chordlet.

(a) Representation using wavelet. (b) Representation using curvelet/contourlet. (c) Representation using beamlet. (d) Represen- tation using chordlet.

c Q Q LH Q LH gu Q Q.2 32 3-1 An illustration of a two-level contourlet decomposition of image Peppers. 36 3-2 Three classes of Markov dependencies in a wavelet pyramid. (c) Cross-band dependencies within scales L and £ +1 among horizontal, vertical and diagonal subbands. 3:3 An illustration of cross-scale dependencies, indicated by ellipsoids, in con- tourlet pyramid of Fig.

(a) The vertical subband at scale 2, labeled 21 in Fig. (b) The child subband of (a), which is the near-vertical subband at scale 1 labeled 12 in Fig.