Some Research On Digital Image Processing About Compression And Denoising Based On Local Directionality

The investigation on adaptive and multiresolution(multiscale) method is an important research direction on digital signal processing. Up to now, this kind of idea has been widely accepted and adopted, such as the famous basis pursuit of Mallat, the local cosine basis of Coifman , the wedgelet of Donoho and the best wavelet package of Ramchandran and Vetterli, etc. In the last recent rears , wavelet analysis has always been a hot topic, no matter what for theory research and practical application. As is well known, wavelet is very successful in image compression, and has been the dominant tool in 2D image compression[JPEG2000, Taubman, 2002], which is profit from its best nonlinear approach capacity for 1D bounded variance signal[DeVore, 1998]. Unfortunately, despite the success of wavelet, the 2D separable wavelet, customarilycreated by the direct product of two independent 1-D wavelet, is not provided with the capacity of best representing 2D image [curvelet, Donoho, 1999], where there exists a plenty of edges, because the traditional standard wavelet only have two transform directions, namely horizontal and vertical. So the problem of finding efficient representations of images is a fundamental problem in many image processing tasks. Along with the study in nonlinear approach, many new tool have been proposed, such as curvelets, contourlet, directionlet,etc. These new tools not only inherit many advantages of traditionalwavelet, but also breach the limitation of the traditional standard 2D wavelet transform. The discrete directional wavelet transform(S-WT) utilizedin our work is an excellent delegate of these new tools. At present, the study on these new methods is going along, which will certainly impact the area of image processing greatly.The main work of this thesis is on the research of compression and denoising algorithms about still images. For the compression, we mainly utilize discrete directional wavelet transform(S-WT) [Velisavljevic, 2006][22] and linear polynomial to represent the 2D image. Compared with the traditional2D wavelet transform, the directional vanish moment(DVM) of S-WT is crucial to compression, and the capacity of linear and piecewise linear polynomial on representing smooth area and linear edge of image is obvious,all the above are the motivation of our work on compression. Because of the complexity of natural images , regular change of image intensity is a local phenomena, and curve edge of images can be regarded as straight lines in local area, so directionality of image should better be considered as local property. So in our algorithms, the whole images are divided into many smaller blocks adaptively, and three tilling manners are utilized to accomplishthe above manipulation, namely quadtree, binary tree and multitree. Quadtree is frequently utilized in many image processing methods, but binarytree and multitree are seldom encountered in the existing papers. We utilize the above three manners in our three algorithms in wavelet compressionpart of this thesis, and in the polynomial approach part, only the binary tree is used.In Chapter 2 of this thesis, we utilize the Skewed-Wavelet Transform(S-WT) proposed in [Directionlets, Velisavljevic,2006][22],which is isotropic, and a kind of simple method for computation of dominant directions is proposed.In the theory of the optimal wavelet packet decomposition to achieve the best rate-distortion (R-D) tradeoff, it is proved that the constant R-D slope criterion for optimum bit allocation is equivalent to the constant distortioncriterion, which can be easily implemented via thresholding by Li[59], which can greatly reduce the computation complexity of the method [44] proposedby Ramchandran and Vetterli. We introduce this kind of idea into our work, and develop a sort of criterion for spatial tilling based on R-D sense, which will be depicted as follows.Because S-WT is similar to the standard WT, the distribution of transformcoefficients can be modeled by a random variable with the generalized Gaussian PDF (GGPDF). Utilizing the exponentially R-D decay property of Gaussian source , the following two assumptions are used in our work: andwhere D_max is the maximum coding distortion at coding rate R = 0, which is equal to the variance of the source. The discussion about the above assumptionsand the high resolution hypothesis of R-D function D = D_max2^-2R [60] is in Chapter 2, section 3.If a subimage X is decomposed into N subbands B_i,1≤i≤N with S-WT, the number of wavelet coefficients, the average distortion, the average bit rate and the maximum coding distortion are denoted by n_i, D_i R_i, D_max,i respectively. For a total bit budget R, one should optimally allocate the average bit rate R_i, 1≤i≤N so thatBy means of Lagrangian method , (1)(2) and nonnegative bit rate constraint, the total bit budget for the entire image(3)is written as:where K_i² = max(D_th,σ_i²), D_th is called threshold distortion , andσ² representsthe variance of subband B_i. If X is furthermore divided into four subimages X₁, X₂, X₃, X₄, their subbands are denoted by B_ji, 1≤j≤4,1≤i≤N.By means of the above description, the bit saving due to further decomposition isWhen theR_s is greater than the decomposition overheadR_c, the spatial dividingis accepted. And this kind of criterion is utilized in all the three algorithms of Chapter 2. The methods of binary tree and multitree are proposedin order to better take advantage of the local directionality, where the same transform and coding methods as the quadtree are used, but the spatial dividing manner is different. In the binary tree part, the best spatial tilling is obtained by update from bottom to top by dynamic programming, and the experiments indicate that although the computation is more complex than the quadtree method, the binary tree method has better performance in codinggain and visual quality. The multitree part is an new attempt, because the computation complexity, we utilize the greedy algorithm to obtain suboptimalmultitree of image from top to bottom, which will be further studied because of its advanced idea. The total computation complexity of quadtree is O(N²), so does the binary tree method. But in the part of creating best spatial tilling, the computation implemented in the binary is n + 1 times of quadtree, where n is the layers of spatial dividing. Because the computation of multitree is related to the given image, we do not analysis its complexity detailed, but the total computation complexity is also O(N²).In Chapter 3, the part of polynomial approach, we borrow the idea of [Ramchandran, Vetterli, 1993] [44] and [Shukla, 2005] [48], but we utilize the binary tree tilling, not the quadtree. We also use the linear polynomial and nonlinear polynomial to approximate the small blocks of images. In the part of creating best spatial tilling, the computation implemented of mine is (n+1) times of [48](assuming that we also utilize the same edge dictionary), where n is the layers of spatial dividing. Although the binary tree consumes more computation than quadtree, the former is more flexible than the latter, and the number of edge dictionaries used in our method is more less than the [48], meanwhile we got rid of the operation of combining the joint similar neighbor, which can reduce the computational complexity greatly, meanwhile with the better performance. So the total computation complexity of our method is also O(N log N), where N is the number of image pixels.In Chpater 4, the wavelet denoising part, we firstly use the number experiments to demonstrate the denoising capability of directional transform.Further more utilizing the new idea on wavelet denoising of directional wavelet transform [35], by introducing the directional WT without subsampling,and averaging all the denoised images created by all the directional transforms and denoising processing eventually, we have improved the spatiallyadaptive wavelet threshold denoising with context modeling[98] base on the previous idea, which made the new method to be provided with the power of better keeping side information and translation-invariant (TI)denoising property, which is proposed by Coifman and Donoho in [94], because averagingall the directional transform outputs is corresponding to the rotation processing of image. But the computation in our method is five times of the [98] without considering the resampling operation.Our work is motivated by the idea of those new nonlinear approach tools after wavelet, and one of which, S-WT, has been directly utilized in our algorithms. We knows that our work is only an attempting, and because of our ability limitation, our work looks like a little superficial. This work is only the starting of our intending work, and we hope that we will obtain better results in this area in the future.