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

Luận án tiến sĩ nghiên cứu texture and structure based image representation with applications to image retrieval and, phát triển phương pháp mới, đánh giá hiệu quả ứng dụng trong

• Đề tài: Phương Pháp Đại Diện Hình Ảnh Dựa Trên Kết Cấu và Kết Cấu với Ứng Dụng trong Tìm Kiếm và Nén Hình Ảnh

Tóm tắt

I. Tổng Quan Về Đại Diện Hình Ảnh Dựa Trên Kết Cấu

Trong lĩnh vực xử lý ảnh, đại diện hình ảnh đóng vai trò then chốt trong việc thiết kế các thuật toán hiệu quả. Đặc biệt, việc lựa chọn phương pháp đại diện hình ảnh phù hợp ảnh hưởng trực tiếp đến hiệu suất của các ứng dụng như nén hình ảnh và tìm kiếm hình ảnh dựa trên nội dung. Luận án này tập trung vào việc phát triển các phương pháp nắm bắt và biểu diễn một cách ngắn gọn hai đặc điểm nổi bật của hình ảnh: kết cấu hình ảnh và cấu trúc. Các phương pháp này được ứng dụng để tạo ra các biểu diễn nhỏ gọn, phục vụ cho việc nén hình ảnh và tìm kiếm hình ảnh từ cơ sở dữ liệu dựa trên phác thảo. Hiệu suất của các phương pháp này được so sánh với các phương pháp nén hình ảnh và tìm kiếm hình ảnh khác. Các phương pháp đại diện hình ảnh dựa trên kết cấu hình ảnh và cấu trúc có tiềm năng lớn trong việc cải thiện hiệu quả và độ chính xác của các ứng dụng xử lý ảnh.

1.1. Tầm quan trọng của mô tả kết cấu trong xử lý ảnh

Việc mô tả kết cấu một cách chính xác và hiệu quả là yếu tố then chốt trong nhiều ứng dụng xử lý ảnh. Một mô tả kết cấu tốt cho phép phân biệt các vùng khác nhau trong ảnh, nhận diện đối tượng và thực hiện các tác vụ phân tích ảnh khác. Các phương pháp mô tả kết cấu khác nhau có thể phù hợp với các loại ảnh và ứng dụng khác nhau. Việc lựa chọn phương pháp mô tả kết cấu phù hợp là rất quan trọng để đạt được hiệu suất tối ưu.

1.2. Ứng dụng của đại diện hình ảnh trong tìm kiếm hình ảnh

Đại diện hình ảnh đóng vai trò trung tâm trong các hệ thống tìm kiếm hình ảnh dựa trên nội dung (CBIR). Một đại diện hình ảnh tốt cho phép hệ thống so sánh các hình ảnh một cách hiệu quả và trả về các kết quả phù hợp với truy vấn của người dùng. Các phương pháp đại diện hình ảnh khác nhau có thể được sử dụng để tìm kiếm hình ảnh dựa trên các đặc trưng khác nhau, chẳng hạn như màu sắc, kết cấu hình ảnh và hình dạng.

II. Thách Thức Trong Nén Hình Ảnh và Tìm Kiếm Hình Ảnh

Việc thiết kế các phương pháp đại diện hình ảnh sử dụng số lượng đặc trưng nhỏ đặt ra nhiều thách thức. Một trong những thách thức lớn nhất là làm thế nào để nắm bắt và biểu diễn thông tin quan trọng của hình ảnh một cách hiệu quả với số lượng đặc trưng hạn chế. Điều này đặc biệt quan trọng trong các ứng dụng như nén hình ảnh, nơi mục tiêu là giảm kích thước tệp tin hình ảnh mà không làm giảm đáng kể chất lượng hình ảnh. Tương tự, trong tìm kiếm hình ảnh dựa trên nội dung, việc sử dụng số lượng đặc trưng nhỏ có thể giúp tăng tốc độ tìm kiếm hình ảnh và giảm yêu cầu về bộ nhớ. Tuy nhiên, việc lựa chọn các đặc trưng phù hợp và biểu diễn chúng một cách hiệu quả là một vấn đề phức tạp.

2.1. Giới hạn của các phương pháp nén ảnh truyền thống

Các phương pháp nén ảnh truyền thống, như JPEG, có thể đạt được tỷ lệ nén ảnh cao, nhưng thường dẫn đến mất mát thông tin và giảm chất lượng hình ảnh. Các phương pháp nén ảnh mới hơn, như JPEG 2000, sử dụng các kỹ thuật phức tạp hơn để giảm thiểu mất mát thông tin, nhưng vẫn có những hạn chế nhất định. Việc phát triển các phương pháp nén ảnh mới, có thể đạt được tỷ lệ nén ảnh cao mà không làm giảm đáng kể chất lượng hình ảnh, vẫn là một thách thức quan trọng.

2.2. Độ phức tạp của tìm kiếm ảnh trong cơ sở dữ liệu lớn

Tìm kiếm ảnh trong các cơ sở dữ liệu lớn có thể là một tác vụ tốn kém về mặt tính toán. Việc so sánh từng hình ảnh trong cơ sở dữ liệu với truy vấn của người dùng có thể mất nhiều thời gian và tài nguyên. Các phương pháp đại diện hình ảnh hiệu quả có thể giúp giảm độ phức tạp của tìm kiếm ảnh bằng cách cho phép hệ thống so sánh các hình ảnh một cách nhanh chóng và hiệu quả.

III. Phương Pháp Đại Diện Kết Cấu Dựa Trên Mô Hình Markov Ẩn

Luận án giới thiệu một phương pháp dựa trên mô hình Markov ẩn (HMM) để mô tả một cách ngắn gọn kết cấu hình ảnh sử dụng một số lượng nhỏ các đặc trưng. Phương pháp này sử dụng các phép biến đổi đa tỷ lệ contourlet và steerable-pyramid để phân tách hình ảnh thành các dải con chứa các cạnh. Các phụ thuộc giữa các dải con được nắm bắt bằng các mô hình Markov ẩn, và các tham số mô hình được sử dụng để biểu diễn kết cấu hình ảnh bằng một tập hợp các đặc trưng nhỏ. Ứng dụng của phương pháp này trong tìm kiếm hình ảnh dựa trên nội dung với các kết cấu hình ảnh đồng nhất từ cơ sở dữ liệu được trình bày. Tính toán cao hơn khoảng 10% so với các phương pháp so sánh được chứng minh; khi số lượng đặc trưng ít hơn có thể thu được bằng phương pháp được đề xuất.

3.1. Sử dụng biến đổi Contourlet để trích xuất đặc trưng kết cấu

Biến đổi Contourlet là một công cụ mạnh mẽ để phân tích kết cấu hình ảnh ở nhiều tỷ lệ và hướng khác nhau. Bằng cách sử dụng biến đổi Contourlet, có thể trích xuất các đặc trưng kết cấu quan trọng từ hình ảnh, chẳng hạn như các cạnh, đường và góc. Các đặc trưng này có thể được sử dụng để phân biệt các kết cấu hình ảnh khác nhau và để tìm kiếm hình ảnh dựa trên kết cấu.

3.2. Mô hình hóa phụ thuộc giữa các dải con bằng HMM

Các mô hình Markov ẩn (HMM) là một công cụ hiệu quả để mô hình hóa các phụ thuộc giữa các dải con trong biến đổi Contourlet. Bằng cách sử dụng HMM, có thể nắm bắt các mối quan hệ phức tạp giữa các đặc trưng kết cấu khác nhau và tạo ra một đại diện kết cấu chính xác và hiệu quả.

IV. Đại Diện Cấu Trúc Hình Ảnh Sử Dụng Phép Chiếu Định Hướng

Luận án đề xuất một phương pháp mô tả ngắn gọn cấu trúc hình ảnh. Phương pháp này phân tách hình ảnh bằng cách sử dụng biến đổi contourlet thành các dải con định hướng chứa các hướng cạnh. Mỗi dải con sau đó được chiếu lên các hướng chính và trực giao liên quan, và các phép chiếu kết quả sau đó được mô hình hóa bằng cách sử dụng các phép xấp xỉ từng phần các mô hình hỗn hợp Gaus. Các tham số mô hình sau đó tạo thành một đặc trưng ngắn gọn được sử dụng để biểu diễn cấu trúc của hình ảnh. Một ứng dụng của phương pháp đại diện hình ảnh này cho hình ảnh từ cơ sở dữ liệu dựa trên phác thảo hình ảnh được trình bày. Một sự gia tăng sử dụng phương pháp được đề xuất được chứng minh so với phương pháp dựa trên biểu đồ không gian hiện tại.

4.1. Phân tích hướng cạnh bằng biến đổi Contourlet

Biến đổi Contourlet cho phép phân tích hướng cạnh một cách hiệu quả, cung cấp thông tin quan trọng về cấu trúc hình ảnh. Việc xác định và phân tích các hướng cạnh giúp phân biệt các đối tượng và vùng khác nhau trong ảnh.

4.2. Mô hình hóa phép chiếu bằng hỗn hợp Gaussian

Sử dụng hỗn hợp Gaussian để mô hình hóa các phép chiếu giúp tạo ra một đại diện cấu trúc linh hoạt và chính xác. Các tham số của hỗn hợp Gaussian có thể được sử dụng để nắm bắt các đặc điểm quan trọng của cấu trúc hình ảnh.

V. Khung Đại Diện Đường Cong Đa Tỷ Lệ Mới Chordlet

Luận án xây dựng một khung đại diện đường cong đa tỷ lệ mới, chordlet, để biểu diễn cấu trúc hình ảnh dựa trên đường cong một cách ngắn gọn. Khung này có thể được xem như là một phần mở rộng của các đường cong được gọi là biến đổi beamlet, một hệ thống biểu diễn đa tỷ lệ. Trong luận án này, biểu diễn về mặt độ méo so với biến dạng, biến đổi chordlet được so sánh với biến đổi beamlet. Một thuật toán thực hiện biến đổi chordlet đã được phát triển. Một hệ thống mã hóa dựa trên chordlet được xây dựng để ứng dụng biến đổi chordlet vào nén hình ảnh hình dạng. Bằng cách sử dụng phương pháp được đề xuất, khả năng nén ảnh tăng lên thu được độ méo thấp hơn khi so sánh với hai phương pháp đã biết.

5.1. So sánh hiệu quả biểu diễn giữa Beamlet và Chordlet

Việc so sánh hiệu quả biểu diễn giữa Beamlet và Chordlet cho thấy Chordlet có khả năng biểu diễn đường cong một cách hiệu quả hơn trong một số trường hợp nhất định. Điều này có thể dẫn đến cải thiện hiệu suất trong các ứng dụng như nén hình ảnh và tìm kiếm hình ảnh.

5.2. Ứng dụng Chordlet trong nén ảnh hình dạng

Việc ứng dụng Chordlet trong nén ảnh hình dạng cho thấy tiềm năng của phương pháp này trong việc giảm kích thước tệp tin hình ảnh mà không làm giảm đáng kể chất lượng hình ảnh. Điều này có thể đặc biệt hữu ích trong các ứng dụng như lưu trữ và truyền tải hình ảnh.

VI. Kết Luận và Hướng Phát Triển Cho Đại Diện Hình Ảnh

Luận án này đã trình bày các phương pháp mới để đại diện hình ảnh dựa trên kết cấu hình ảnh và cấu trúc, với các ứng dụng trong tìm kiếm hình ảnh và nén hình ảnh. Các phương pháp này sử dụng các kỹ thuật tiên tiến như mô hình Markov ẩn, biến đổi contourlet và khung chordlet để nắm bắt và biểu diễn thông tin quan trọng của hình ảnh một cách hiệu quả. Kết quả nghiên cứu cho thấy các phương pháp này có tiềm năng cải thiện hiệu suất của các ứng dụng xử lý ảnh. Trong tương lai, có thể tiếp tục nghiên cứu và phát triển các phương pháp đại diện hình ảnh mới, kết hợp các kỹ thuật khác nhau và tập trung vào các ứng dụng cụ thể.

6.1. Tóm tắt đóng góp của luận án

Luận án đã đóng góp vào lĩnh vực đại diện hình ảnh bằng cách đề xuất các phương pháp mới dựa trên kết cấu hình ảnh và cấu trúc, đồng thời chứng minh hiệu quả của chúng trong các ứng dụng thực tế. Các phương pháp này có thể được sử dụng để cải thiện hiệu suất của các hệ thống tìm kiếm hình ảnh và nén hình ảnh.

6.2. Hướng nghiên cứu tiềm năng trong tương lai

Trong tương lai, có thể tiếp tục nghiên cứu và phát triển các phương pháp đại diện hình ảnh mới, kết hợp các kỹ thuật khác nhau và tập trung vào các ứng dụng cụ thể. Ví dụ, có thể nghiên cứu các phương pháp đại diện hình ảnh dựa trên học sâu, hoặc các phương pháp đại diện hình ảnh phù hợp với các loại hình ảnh cụ thể, chẳng hạn như ảnh y tế hoặc ảnh vệ tinh.

Trích đoạn nội dung tài liệu

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.