Tài liệu Bài báo cáo thực tập-acknowledgements

  • Số trang: 77 |
  • Loại file: PDF |
  • Lượt xem: 1290 |
  • Lượt tải: 0
quangtran

Đã đăng 3721 tài liệu

Mô tả:

CODEBOOK ORDERING FOR VECTOR QUANTIZATION by LINKING YE, B.E. A THESIS IN ELECTRICAL ENGINEERING Submitted to the Graduate Faculty of Texas Tech University in Partial Fulfillment of the Requirements for the Degree of MASTER OF SCIENCE IN ELECTRICAL ENGINEERING Approved Accepted December, 2003 ACKNOWLEDGEMENTS I would like to express my sincere appreciation to my advisor and committee chairperson, Dr. Sunanda Mitra. Her guidance, knowledge, illumination, and encouragement have been invaluable. I would like to thank Dr. Brian Nutter and Dr. Tanja Karp for being on my committee and for their generous assistance. I would also like to thank my parents, my sister, and all my friends for their unflagging support. 11 TABLE OF CONTENTS ACKNOWLEDGEMENTS ii ABSTRACT v LIST OF TABLES vi LIST OF FIGURES vu CHAPTER 1. INTRODUCTION 1 2. WAVELET TRANSFORM 4 2.1 Basic Concept of Wavelet Transform 4 2.2 Continuous and Discrete Wavelet Transform 5 2.3 2D Wavelet Transform 13 3. VECTOR QUANTIZATION 17 3.1 Vector Quantization 17 3.2 The LBG Algorithm 22 3.3 Introduction of Adaptive Arithmetic Coding 26 4. ADDRESS PREDICTIVE VECTOR QUANTIZATION 29 4.1 Address Vector Quantization 29 4.2 Address Predictive Vector Quantization 30 4.3 Codebook Ordering Technique 36 5. GEOMETRIC VECTOR QUANTIZATION 5.1 Basic Idea of GVQ 43 43 111 5.2 Realization of GVQ 44 6. RESULTS 48 6.1 Results for Codebook Ordering 48 6.2 Codebook Ordering for VQ Based on the LBG Algorithm 51 6.3 Codebook Ordering for Geometric Vector Quantization 61 7. CONCLUSIONS 65 REFERENCES 67 IV ABSTRACT Address predictive vector quantization (APVQ) utilizes an ordered codebook to exploit the dependency among close input vectors. The Kohonen algorithm is often chosen in APVQ. However, the Kohonen algorithm is not applicable while a codebook already exists. In this thesis three methods of ordering an existing codebook have been developed. Theoretically these codebook ordering methods can be utilized in any vector quantization in order to reduce the output bit rate. Here we apply it to two types of vector quantization approaches, geometric vector quantization (GVQ) and vector quantization based on the LBG algorithm. The results of codebook ordering on vector quantization based on the LBG algorithm are quite good. However, codebook ordering does not have good performance on GVQ. Therefore, while applying codebook ordering to one specific VQ, we should consider the property of this VQ in order to achieve a satisfactory result. LIST OF TABLES 2.1: Daubechies 4 coefficients 9 2.2: Daubechies 10 coefficients 9 3.1: The training vectors for designing VQ codebook 23 3.2: An initial codebook 24 3.3: The codebook after one iteration 25 3.4: The final codebook 25 6.1: Computational time for each method 50 6.2: The size of lossless encoding output files after VQ Based on the LBG Algorithm (unit: Kbytes) 59 6.3: The size of lossless encoding output files after GVQ (unit: Kbytes) 63 VI LIST OF FIGURES 2.1: Multi-resolution time-frequency tiling 5 2.2: The Haar wavelet 8 2.3: A sample Daubechies wavelet 8 2.4: ID wavelet transform decomposition 11 2.5: Approximation information after the n level ID wavelet transform. (a) Original signal, (b) Approximation after the 1 level wavelet transform, (c) Approximation after the 2 level wavelet transform, (d) Approximation after the 3 level wavelet transform, (e) Approximation after the 4 level wavelet transform 12 2.6: ID wavelet ttansform reconstmction 13 2.7: 2D wavelet ttansform. (a) One level wavelet ttansform. (b) Two level wavelet transform, (c) Three level wavelet transform 14 2.8: 2D wavelet transform on image "Camera." (a). The original image "Camera." (b). 2D one level wavelet transform, (c). 2D two level wavelet transform, (d). 2D three level wavelet transform 15 3.1: The procedure of vector quantization 18 3.2: The height and weight scalar quantizer [7] 21 3.3: The height and weight vector quantizer [7] 21 3.4: The procedure for generating the tag 27 4.1: APVQ on image "Peppers." (a) Original image "Peppers." (b) Address image got from using an ordered codebook. (c) Address image got from using an un-ordered codebook. (d) Reconstmcted image 32 4.2: APVQ on image "Mandrill." (a) Original image "Mandrill." (b) Address image got from using an ordered codebook. (c) Address image got from using an un-ordered codebook. (d) Reconstmcted image 34 Vll 4.3: Encoding procedure of APVQ 35 4.4: Adaptation rule in the Kohonen algorithm 38 5.1: A nine vector GVQ codebook (codevector size: 3x3) 44 5.2: An example of matching a two-level GVQ 45 6.1: Codebook ordering results.(a) The original codebook. (b) The codebook after ordering by method 1. (c) The codebook after ordering by method 2. (d) The codebook after ordering by method 3 49 6.2: VQ based on the LBG algorithm using an ordered codebook 51 6.3: Some training images used in the LBG algorithm 52 6.4: Input images for VQ based on the LBG algorithm. (a) "Einstein." (b) "Tmck." (c) "Boats." (d) "Circuit." (e) "GoldhiU." (f) "Kids." (g) "Paolina." (h)"Lamp." 54 6.5: The first 90 codevectors in the codebook generated by LBG algorithm 55 6.6: The first 90 codevectors in the codebook ordered by method 1 56 6.7: The first 90 codevectors in the codebook ordered by method 2 57 6.8: The first 90 codevectors in the codebook ordered by method 3 58 6.9: Applying codebook ordering to GVQ 61 6.10: The original and reconstmcted "Einstein." (a) The input image "Einstein." (b) The reconstmcted image 6.11: The original and reconstmcted "Tmck." (a) The input image "Tmck." (b) The reconstmcted image 62 Vlll 62 CHAPTER 1 INTRODUCTION The purpose of image compression is to reduce the amount of data required to represent a digital image. This reduction process can be understood as removing redundant data. Over the years, the need for image compression has grown steadily. An ever-expanding number of applications depend on the efficient manipulation, storage, and ttansmission of binary, gray-scale, or color images [1]. Image compression is utilized for image ttansmission and storage. Image transmission applications include broadcast television, remote sensing via satellite, aircraft, radar and sonar, teleconferencing, computer communication, and facsimile transmission. Image storage applications include educational and business documents, medical images, etc. Because of its wide applications, image compression is of great importance in digital image processing [2]. Based on the different requirements of reconstmction, image compression can be divided into two categories, lossless compression and lossy compression. The purpose of lossless image compression is to represent an image signal with the smallest possible number of bits without any information loss. The number of bits representing the signal is typically expressed as an average bit rate per pixel for still images and as an average number of bits per second for video. The purpose of lossy compression is to minimize the number of bits representing the image signal with some allowable information loss. In this way, a much greater reduction in bit rate can be obtained as compared to lossless compression [4]. Lossy compression techniques resuh in some loss of information. Therefore data compressed by lossy compression techniques cannot be reconstmcted exactly. However, in many applications, this lack of exact reconstmction is not a problem. Therefore, lossy compression is widely used because of the high compression ratio it can achieve. Both scalar and vector quantization are lossy compression techniques. Scalar quantization processes the samples of an input signal one by one and independently. Vector quantization processes the samples of an input signal in group. Shannon's information theory [20] has proven that encoding sequences of input samples can get a better result than encoding input samples one by one. Therefore by utilizing vector quantization, we are able to achieve a better quantization result than scalar quantization. In vector quantization, the most important problem is designing an efficient codebook. There are already many algorithms published on how to generate a codebook. The LBG algorithm is a well-known algorithm on designing the codebook. It is the starting point for most of the work on vector quantization. Although many clustering algorithms have been designed for generating the codebook, there is no general approach available to generate a universal codebook [3]. In traditional vector quantization, we utilize a set of ttaining images to generate the codebook. This generated codebook is used directly to perform the vector quantization. If we perform some pre-processing on this generated codebook, it can make the vector quantization more efficient. That is the basic motivation of address predictive vector quantization (APVQ). In APVQ, we use an ordered codebook to exploit the interblock dependency. Kohonen algorithm is often chosen because of its good performance and robustness. However, Kohonen algorithm is only applicable when we need to generate a new codebook. If we want to order an existing codebook and apply the idea of APVQ to some other types of vector quantization, we have to find some other solution. Codebook ordering is a complicated problem because it will lead to the ttaveling salesman problem. What we can do is finding a comparatively good solution. Geometric vector quantization is a type of vector quantization that is suitable for exttacting the edge related feature of a subband. In a GVQ codebook, each codevector is composed by a single strip or single dot of different widths and sizes. After VQ process we need to ttansmit the index of each codevector and the foreground and background intensity values [18]. GVQ has a good effect on encoding the high frequency subband. This thesis is outlined as follows. Chapter 2 describes the wavelet transform. Both continuous and discrete wavelet transform will be discussed. The idea of wavelet ttansform is extended from ID to 2D. Chapter 3 presents how vector quantization works and describes in detail about how to generate a codebook by using the LBG algorithm. Chapter 4 presents APVQ. After the introduction of APVQ, three codebook ordering methods that were designed in this thesis will be presented. In Chapter 5, the theory of GVQ is described. Chapter 6 presents the results of applying codebook ordering to VQ based on the LBG algorithm and GVQ. Finally, The conclusion is given in Chapter 7. CHAPTER 2 WAVELET TRANSFORM 2.1 Basic Concept of Wavelet Transform For a one-dimensional signal, the two most common representations are time domain and frequency domain representations. However, time domain representation and frequency domain representation are orthogonal to each other. Therefore it is difficuU for us to exfract frequency information from the time domain representation. It is also difficult to get the time information from the frequency domain representation [5]. Normally, we utilize the Fourier transform to analyze the frequency components of a signal. Like the Fourier transform, the wavelet transform can provide the frequency domain information of a signal. At the same time, the wavelet transform can also provide the time domain information of a signal. To achieve this, the wavelet transform sacrifices some of its spectral resolution. From the uncertainty principle, we know that we cannot localize perfectly well in both the time domain and the frequency domain [6]. We can understand this from Figure 2.1. In Figure 2.1, the x-axis represents the time domain resolution of a signal and the y-axis represents the frequency domain resolution. It can be seen that the frequency domain resolution becomes worse as the time domain resolution gets better. The frequency domain resolution becomes better as the time domain resolution gets worse. Therefore when we analyze lower-frequency components, we should use a wide wavelet signal. If we want to analyze higher-frequency components, we should use a narrow wavelet signal. Figure 2.1: Multi-resolution time-frequency tiling. 2.2 Continuous and Discrete Wavelet Transform The following equations describe the continuous wavelet ttansform (CWT). Wavelet ttansform: = f Wa.bit)f{t)dt (2.1) Inverse wavelet transform: /(O^TT-f [ ^a,^a,bii)dadb ( J-00 J-oo (2.2) In equation 2.2, \\f(t) represents a "mother" wavelet function. A scaled and 1 f L ttanslated mother wavelet t^„ ^ (t) = -i=\\i ( Va ), where a = scaling factor, b = translation « to right. In CWT, the basis functions are shifted and scaled versions of each other. Therefore they cannot form a very orthonormal base. The result of CWT holds an infinite number of wavelets. It is very difficult to find the desired results from the fransformed data. These drawbacks of CWT make it difficult for us to utilize CWT to solve any real problem [12]. Next we will introduce the discrete wavelet transform (DWT), which has wider applications than CWT. In discrete wavelet transform, '^(t) is the scaling function. w{t) is the wavelet function. It is also called the mother wavelet. They are related by the following equations: <^j_k{t)=2-^''^{rt-k), (2.3) O(0=X /i^^-u(0=V2X h^{2t-k). * (2.4) k If we define Ck= 42 hk, we can get: 0 ( 0 = X Ck^{2t-k), (2.5) k yifj,k(t)=2-'''w{2-'t-k), (2.6) 1^(0=1 g^^-u(0=V2i; gk^i2t-k). k If we define dk=-sl2gk, we can get: k (2.7) V ( 0 = S dk^{2t-k). (2.8) k In the wavelet transform, a function f{t) can be represented by a linear combination of scaling and wavelet functions. Although scaling functions or wavelet functions can represent f[t) alone, it is common to use both scaling functions and wavelet functions to express f{t). M=T %.k{t) (2.9) it k k The simplest wavelet basis function is the Haar basis function. The Haar scaling function ^1' (t) is defined as: 0{t)=l fl 0 0 be the given initial data. Usually, it is a sequence of samples from/02. In this step we calculate the set of wavelet coefficients and scaling coefficients on scale 1: dl= = Y. Sn-2kcl ^ U > = Z ^n-2kcl (2.11) (2.12) 3. Calculate the wavelet coefficients and scaling coefficients on level j : ^/ = Z Sn.2kCi-\ (2.13) hn-ikcl'. (2.14) n ci^Y. n We can express the wavelet transform in matrix notation. The operation in equation 2.14 can be looked at as a matrix L, where Lij=Ay.2,. The operation in equation 2.13 can be looked at as a matrix H, where Hij=gy-2/. From above implement steps, we can get a set of coefficients {dj, dz, ..., dj. c,}. The set of coefficients is the wavelet transform of/f^y*- {dj, dj, .... dj) is the detailed information on the j level wavelet transform, cyis the approximation of the original data on the j level wavelet transform. From the view of ftiter bank, we can look at the L matrix as a lowpass fiher. The H matrix can be looked at as a highpass filter [10]. The low frequency components of the original signal are expressed by Cj. The high frequency components of the original signal are expressed by dj. Therefore, we can express the wavelet transform as shown in figure 2.4. In Figure 2.4, the original data c*' is passed through a lowpass filter and a highpass filter. After downsampling, we can get the first level wavelet transform output c' and d'. c' is the approximation information, d' is the detailed information. We continue decomposing c' by passing it through a lowpass filter and a highpass filter, c' is decomposed into c^ and d^. c^ is the approximation and d^ is the detailed information on 10 L i2 H \2 •• \2 —•, L — \2 • Onginal data c" H — • • H ki \2 \2 d3 d2 d' Figure 2.4: ID wavelet transform decomposition. the level 2 wavelet fransform. We can get the level n wavelet transform data by repetition of the described steps. Figure 2.5 shows the approximation information at the n level wavelet transform. Figure 2.5(a) is the original data. Figure 2.5(b) is the approximation after the 1 level wavelet transform. Figure 2.5(c) is the approximation after the 2 level wavelet ttansform. Figure 2.5(d) is the approximation after the 3 level wavelet transform. Figure 2.5(e) is the approximation after the 4 level wavelet transform. We can find that the waveform in Figure 2.5 (b) is the most similar to the original waveform. The waveform in Figure 2.5 (e) is the least like to the original waveform. This is because after the 4 level wavelet transform, there is less approximation information but more detailed information than after a 1 level wavelet transform. Now let us have a look at how to implement the inverse wavelet transform. The steps are similar to the implementation of the wavelet transform but the procedure is 11 A ^^..j I I . V. (b) (c) r1 ' I V \ i V , (e) (d) Figure 2.5: Approximation information after the n level ID wavelet ttansform. (a) Original signal, (b) Approximation after the 1 level wavelet transform. (c) Approximation after the 2 level wavelet transform, (d) Approximation after the 3 level wavelet transform, (e) Approximation after the 4 level wavelet transform. 12
- Xem thêm -