Image adaptive multistage vector Quantization scheme for different Multiscale and multidirectional Image representations

Abstract

Digital image and image sequences in uncompressed formats require excessive storage capacity and huge transmission bandwidth. Therefore, compression of digital image and image sequence is necessary for efficient storage and transmission. Image compression is possible due to redundancy and irrelevancy. Redundancy is a characteristic which is related to predictability, smoothness, etc., in the image data. All natural images exhibit some form of internal structures, which can be explained in terms of statistical dependencies between pixels. This dependency is utilized by signal decomposition. The irrelevancy relies on the fact that the human eye cannot perceive certain image degradations due to the visual perception mechanisms. This is utilized by the quantization scheme. Thus, the role of the signal decomposition is to decorrelate the signal and make the subsequent quantization process easier. Once the decomposed signal samples are quantized, an appropriate symbol coding strategy is used to represent the quantized symbols by bits. Image compression can be achieved either by means of spatial domain techniques or by means of frequency domain techniques. Vector quantization (VQ) is a quantization technique applied to an ordered set of symbols. The superiority of VQ lies in block coding gain, flexibility in partitioning the vector space, and the ability to exploit intra~ vector correlations. When used for image compression, codebooks are designed from training data using some variant of the Generalized Lloyd Algorithm (GLA). Unfortunately, one distinguishing aspect of image data is that there is generally no constraint on what a given image can represent. This characteristic leads to substantial image diversity that often manifests itself as unique, and repeated edge and texture information. Due to this absence of governing model, attempts to represent an arbitrary image using codebooks designed on even large sets of training data can be extremely unproductive unless image membership is restricted to some very confining class. Motivated by this fact, an attempt is made in this thesis to develop a codebook design which is adaptive to input source statistics. Vector quantization theory asserts that increased vector dimension allows improved performance. Three practical problems arise whenever large-dimension vectors are used to achieve improved performance. The first is the codebook search process, which finds the codevector that best approximates the input vector, becomes much slower. Second, the memory required to store the predefined codebook vectors becomes much larger. Third, the inherent delay associated with block processing becomes large as the vector size increases. A structured VQ scheme which can achieve very low encoding and storage complexity is Mulitstage Vector Quantization (MSVQ). MSVQ divides the encoding task into several stages. The first stage performs a relatively crude encoding of the input vector. Then, a second-stage operates on the error vector between the original vector and the quantized first stage output. The quantized error vector provides a refinement to the first approximation. At the decoder, the reconstruction vectors are obtained using Look-Up Table (LUT). The objective of this dissertation is to investigate the rate-distortion performance of the proposed image-adaptive multistage vector quantization scheme for different multiresolution and multi-directional image representations. In recent years, researchers have been using the Discrete Wavelet Transform (DWT) in image compression. Wavelet based coding does not require partitioning of the image. Hence, the typical blocking artifacts, like the ones occurring in JPEG, are avoided and the computation time is hardly increased. However, wavelets are inefficient in representing texture-rich images. The work of Xiong shows that using wavelet packet decomposition to an image can improve PSNR by 0.8-1.3 dB for some texture-rich images, when compared with the standard wavelet transform. Rajpoot and Khalil applied zerotree technique to wavelet packet transforms to generate an embedded bitstream. Unfortunately, these techniques cannot avoid the difficulty of defining zerotree set for wavelet packet transform data of images. Motivated by this, this thesis applies multistage vector quantization scheme to wavelet packet coefficients, where it is not required to define the zerotree set. In particular, an attempt has been made to select the best basis of Wavelet Packet Transform through Singular Value Decomposition. The approach is simple, so that the bands which posses sufficient information alone will be quantized so as to get better reconstructed image quality. The obtained experimental results validate the approach. A scalar wavelet system is based on a single scaling function and mother wavelet. On the otherhand, a multiwavelet uses several scaling functions and mother wavelets. This adds several degrees of freedom in multiwavelet design and generates useful properties such as symmetry, orthogonality, short support, and higher number of vanishing moments, simultaneously. In this work, image-adaptive multistage vector quantization scheme is applied to multiwavelet coefficients and their performance is compared against wavelets. Researchers have proposed multiscale and directional representations that can capture the intrinsic geometrical structures such as smooth contours in natural images. Contourlet transform has basis function oriented at many directions, as opposed to only three directions of wavelets. The contourlet transform satisfies anisotropy property, which means that the basis functions appear at different aspect ratios (depending on the scale), whereas wavelets are separable functions and thus, their aspect ratio equals to one. As a result, image-adaptive multistage vector quantization scheme has been applied in this thesis to contourlet and the performance against wavelets is compared. The proposed image-adaptive multistage vector quantization scheme is applied to wavelets, wavelet packets, multiwavelets, and contourlets. The performance of the proposed algorithm vis-a-vis wavelet packet, multiwavelet and contourlet is compared with wavelet based image-adaptive vector quantization scheme. The performance of the proposed algorithm is evaluated in terms of Peak Signal to Noise Ratio. The proposed image-adaptive vector quantization scheme is extended to sequence of images. The main objective of a video compression algorithm is to exploit both the spatial and temporal redundancy of a video sequence such that fewer bits can be used to represent a video sequence at an acceptable visual distortion. In this thesis, multiwavelet transform and Kite Cross Diamond Search (KCDS) algorithm have been employed so as to minimize spatial redundancy and temporal redundancy, respectively. An attempt is made to use Contourlet transform along with KCDS to improve the visual quality of the reconstructed frames. The performance of the proposed scheme is compared against wavelet based video coding scheme. The proposed scheme achieves higher average PSNR than the wavelet based scheme at low bit rate.