Share Pdf : Design And Application Of Quincunx Filter Banks

Download and Preview : Design And Application Of Quincunx Filter Banks

Report CopyRight/DMCA Form For : Design And Application Of Quincunx Filter Banks

## Transcription

Design and Application of Quincunx Filter Banks, B Eng Tsinghua University China 2002. Supervisory Committee, Dr Michael D Adams Department of Electrical and Computer Engineering. Co Supervisor, Dr Wu Sheng Lu Department of Electrical and Computer Engineering. Co Supervisor, Dr Reinhard Illner Department of Mathematics and Statistics. Outside Member, Supervisory Committee, Dr Michael D Adams Department of Electrical and Computer Engineering.

Co Supervisor, Dr Wu Sheng Lu Department of Electrical and Computer Engineering. Co Supervisor, Dr Reinhard Illner Department of Mathematics and Statistics. Outside Member, Quincunx filter banks are two dimensional two channel nonseparable filter banks They are widely used. in many signal processing applications In this thesis we study the design and applications of quincunx filter. banks in the processing of two dimensional digital signals. Symmetric extension algorithms for quincunx filter banks are proposed In the one dimensional case. symmetric extension is a commonly used technique to build nonexpansive transforms of finite length se. quences We show how this technique can be extended to the nonseparable quincunx case We consider three. types of quadrantally symmetric linear phase quincunx filter banks and for each of these types we show. how nonexpansive transforms of two dimensional sequences defined on arbitrary rectangular regions can be. constructed, New optimization based techniques are proposed for the design of high performance quincunx filter. banks for the application of image coding The new methods yield linear phase perfect reconstruction sys. tems with high coding gain good analysis synthesis filter frequency responses and certain prescribed vanish. ing moment properties We present examples of filter banks designed with these techniques and demonstrate. their efficiency for image coding relative to existing filter banks The best filter banks in our design examples. outperform other previously proposed quincunx filter banks in approximately 80 cases and sometimes even. outperform the well known 9 7 filter bank from the JPEG 2000 standard. Abstract iii, Table of Contents iv, List of Tables vii.

List of Figures viii, List of Acronyms xi, 1 Introduction 1. 1 1 Quincunx Filter Banks 1, 1 2 Historical Perspective 2. 1 3 Overview and Contribution of This Thesis 3, 2 Preliminaries 5. 2 1 Overview 5, 2 2 Notation and Terminology 5, 2 3 Multidimensional Multirate Systems 6. 2 3 1 Multidimensional Signals 7, 2 3 2 Multirate Fundamentals 9.

2 3 3 Uniformly Maximally Decimated Filter Banks 12. 2 3 4 Quincunx Filter Banks 15, 2 3 5 Relation Between Filter Banks and Wavelet Systems 18. 2 3 6 Lifting Realization of Quincunx Filter Banks 20. 2 4 Image Coding 21, 2 4 1 Subband Image Compression Systems 23. 2 4 2 Coding Gain 23, 3 Symmetric Extension for Quincunx Filter Banks 25. 3 1 Overview 25, 3 2 Introduction 25, 3 3 Types of Symmetries 28. 3 4 Mapping Scheme 32, 3 5 Preservation of Symmetry and Periodicity 33.

3 6 Symmetric Extension Algorithm 40, 3 6 1 Type 1 Symmetric Extension Algorithm 41. 3 6 2 Type 2 Symmetric Extension Algorithm 43, 3 6 3 Type 3 Symmetric Extension Algorithm 50. 3 6 4 Type 4 PR Quincunx Filter Banks 50, 3 6 5 Octave Band Decomposition 52. 3 7 Summary 54, 4 Optimal Design of Quincunx Filter Banks 56. 4 1 Overview 56, 4 2 Introduction 56, 4 3 Lifting Parametrization of Linear Phase PR Quincunx Filter Banks 57.

4 3 1 Type 1 Filter Banks 58, 4 3 2 Type 2 and Type 3 Filter Banks 62. 4 4 Design of Type 1 Filter Banks with Two Lifting Steps 64. 4 4 1 Coding Gain 65, 4 4 2 Vanishing Moments 65, 4 4 3 Frequency Response 70. 4 4 4 Design Problem Formulation 73, 4 4 5 Design Algorithm with Hessian 77. 4 5 Design of Type 1 Filter Banks with More Than Two Lifting Steps 78. 4 5 1 Vanishing Moments 79, 4 5 2 Frequency Responses 81. 4 5 3 Design Problem Formulation 82, 4 6 Suboptimal Design Algorithm 86.

4 7 Design Examples 87, 4 8 Image Coding Results and Analysis 92. 4 9 Summary 106, 5 Conclusions and Future Research 108. 5 1 Conclusions 108, 5 2 Future Research 109, Bibliography 110. List of Tables, 3 1 Four types of quadrantal centrosymmetry 29. 3 2 Symmetry type for x where x nn 1 nn x nn and X zz X zz 31. 3 3 Properties of the extended sequences 33, 3 4 Symmetry type of y where y x h 36.

4 1 Comparison of algorithms with linear and quadratic approximations 79. 4 2 Filter bank comparison 88, 4 3 Test images 100. 4 4 Lossy compression results for the finger image 103. 4 5 Lossy compression results for the sar2 image 103. 4 6 Lossy compression results for the gold image 104. List of Figures, 1 1 Frequency responses of a quincunx lowpass filter 2. 2 1 An MD digital filter 8, 2 2 A lattice on Z2 10. 2 3 An MD downsampler 10, 2 4 An MD upsampler 11, 2 5 Cascade connection 11. 2 6 Noble identities 12, 2 7 A UMD filter bank 13, 2 8 Polyphase representation of a UMD filter bank before simplification with the noble identities 14.

2 9 Polyphase representation of a UMD filter bank 14. 2 10 Quincunx lattice 15, 2 11 Quincunx filter bank 16. 2 12 Ideal frequency responses of quincunx filter banks 16. 2 13 An N level octave band filter bank 17, 2 14 Frequency decomposition associated with octave band quincunx scheme 17. 2 15 The equivalent filter bank to octave band 18, 2 16 Lifting realization 21. 2 17 Lifting realization of ITI transforms 22, 2 18 Block diagram of an image coder 24. 3 1 Filter bank with symmetric extension 27, 3 2 1D symmetric extension 27.

3 3 Quadrantal centrosymmetry 29, 3 4 Rotated quadrantal centrosymmetry 31. 3 5 Symmetric extension example 34, 3 6 Frequency responses of a type 1 filter bank 44. 3 7 Scaling and wavelet functions for a type 1 filter bank 44. 3 8 Sequences in the type 1 filter bank 45, 3 9 Frequency responses of the Haar like filter bank 48. 3 10 Scaling and wavelet functions for the Haar like filter bank 48. 3 11 Sequences in the Haar like filter bank 49, 3 12 2 level symmetric extension 53. 4 1 Analysis side of a quincunx filter bank 58, 4 2 Lifting realization 58.

4 3 A quincunx filter bank with two lifting steps 65. 4 4 Ideal frequency responses of quincunx filter banks 71. 4 5 Weighting function 72, 4 6 Lifting filter coefficients for a OPT1 b OPT2 and c OPT3 89. 4 7 Lifting filter coefficients for d OPT4 e OPT5 and f OPT6 90. 4 8 Lifting filter coefficients for OPT7 91, 4 9 Frequency responses of OPT1 92. 4 10 Scaling and wavelet functions for OPT1 93, 4 11 Frequency responses of OPT2 93. 4 12 Scaling and wavelet functions for the OPT2 94. 4 13 Frequency responses of OPT3 94, 4 14 Scaling and wavelet functions for the OPT3 95. 4 15 Frequency responses of OPT4 95, 4 16 Scaling and wavelet functions for the OPT4 96.

4 17 Frequency responses of OPT5 96, 4 18 Scaling and wavelet functions for the OPT5 97. 4 19 Frequency responses of OPT6 97, 4 20 Scaling and wavelet functions for the OPT6 98. 4 21 Frequency responses of OPT7 98, 4 22 Scaling and wavelet functions for the OPT7 99. 4 23 Frequency responses of type2 filter bank 99, 4 24 Scaling and wavelet functions for the type2 filter bank 100. 4 25 The finger image 101, 4 26 The sar2 image 101.

4 27 The gold image 102, 4 28 Reconstructed images for the fingerprint image 105. 4 29 Reconstructed images for the fingerprint image 107. List of Acronyms, 1D One dimensional, 2D Two dimensional. CR Compression ratio, HVS Human visual system, ITI Integer to integer. LTI Linear time invariant, MD Multidimensional, MRA Multiresolution approximation. MSE Mean squared error, PR Shift free perfect reconstruction.

PSNR Peak signal to noise ratio, SOCP Second order cone programming. SVD Singular value decomposition, UMD Uniformly maximally decimated. Introduction, 1 1 Quincunx Filter Banks, One dimensional 1D and multidimensional MD filter banks have proven to be a highly effective tool for. the processing of digital signals including speech image and video Usually the MD case is handled via. tensor product i e the MD signal is decomposed into 1D signals and processed by 1D filter banks along. each dimension Some of the more recent efforts concentrate on the nonseparable case where nonseparable. sampling and filtering are employed 1 2 3 4 5 6 7 8 The quincunx sampling scheme is the simplest. two dimensional 2D nonseparable sampling scheme It is used in many signal processing applications. such as the handling of images returned from remote sensors of satellites 5 and intraframe coding of HDTV. 1 9 In contrast to the separable case the quincunx sampling scheme leads to a two channel filter bank and. reduces the scale by a factor of 2, Although the implementation of quincunx filter banks has higher computational complexity than the. dyadic separable case these filter banks offer several important advantages Firstly the quincunx filter bank. is a good match to the human visual system HVS 10 The HVS has a higher sensitivity to changes in. the horizontal and vertical directions 11 This is equivalent to saying that the HVS is more accurate in per. ceiving high frequencies in the horizontal and vertical directions than along diagonals Figure 1 1 shows the. frequency response of a typical quincunx lowpass filter where the shaded and unshaded regions correspond. to the passband and stopband respectively With the diamond shaped passband this filter conserves hori. zontal and vertical high frequencies and cuts diagonal frequencies by half In this way the quincunx filter. bank well matches the HVS Another advantage of quincunx filter banks is that there are more degrees of. Figure 1 1 Frequency responses of a quincunx lowpass filter The shaded and unshaded regions represent. the passband and stopband respectively, freedom in the design of such filter banks This may lead to filter banks with better performance for targeted.

applications, 1 2 Historical Perspective, Although 1D filter banks have been well studied in the MD case many problems remain unsolved Filter. banks are often defined to operate on signals of infinite extent In practice however we frequently deal with. signals of finite extent This leads to the well known boundary problem that can arise whenever a finite extent. signal is filtered In the 1D case several solutions have been proposed to solve this problem by extending. the finite extent signal into a signal with infinite extent Zero padding and periodic extension 12 13 14. introduce sharp discontinuities in the extended signals which cause distortion at edges of the reconstructed. signals Symmetric extension 14 15 16 is the most commonly used solution to the boundary problem. in the 1D case This extension scheme provides smooth extended signals and leads to desirable nonexpan. sive transforms In the MD case symmetric extension is often applied to the signals separably along each. For 1D filter banks various design techniques have been successfully developed In the nonseparable. MD case however far fewer effective methods have been proposed Variable transformation methods are. commonly used for the design of MD filter banks With such methods a 1D prototype filter bank is designed. first Then it is mapped into an MD filter bank by a change of variables For example the McClellan trans. formation 17 has been used in several design approaches 18 19 20 21 In these designs the frequency. responses of the 1D filters are mapped into MD frequency responses Other design techniques have also been. proposed where a transformation is applied to the polyphase components of the filters instead of the original. filter transfer functions 22 5 7 23 These transformation based designs have the restriction that one cannot. explicitly control the shape of the MD frequency responses while in some cases the transformed MD filter. banks can only achieve approximate perfect reconstruction Direct optimization of the filter coefficients has. also been proposed 24 2 25 but because of the involvement of large numbers of variables and nonlinear. nonconvex constraints such optimization typically leads to a very complicated system which is often diffi. cult to solve Designs through the lifting framework 26 27 have been proposed in 28 6 for two channel. MD filter banks with an arbitrary number of vanishing moments With these methods however only interpo. lating filter banks i e filter banks with two lifting steps are considered Thus good filter banks with more. lifting steps cannot be designed with these approaches. 1 3 Overview and Contribution of This Thesis, This thesis is primarily concerned with the design and application of quincunx filter banks A symmetric ex. tension algorithm is presented to build nonexpansive transforms associated with quincunx filter banks Then. an optimization based design algorithm with some variations is proposed for constructing quincunx filter. banks with a number of desirable characteristics Finally the optimally designed filter banks are compared to. some previously proposed ones in terms of their performance in image coding. The remainder of this thesis is structured as follows Chapter 2 introduces the background necessary to. understand this work We begin by discussing the notational conventions used herein Then we introduce. multidimensional multirate systems and filter banks and examine in detail the quincunx fi. Design and Application of Quincunx Filter Banks by Yi Chen B Eng Tsinghua University China 2002 Supervisory Committee Dr Michael D Adams Department of Electrical and Computer Engineering Co Supervisor Dr Wu Sheng Lu Department of Electrical and Computer Engineering Co Supervisor Dr Reinhard Illner Department of Mathematics and