Linear phase paraunitary filter bank with filters of differentlengths and its application in image compression

In this paper, the theory, structure, design, and implementation of a new class of linear-phase paraunitary filter banks (LPPUFBs) are investigated. The novel filter banks with filters of different lengths can be viewed as the generalized lapped orthogonal transforms (GenLOTs) with variable-length basis functions. Our main motivation is the application in block-transform-based image coding. Besides having all of the attractive properties of other lapped orthogonal transforms, the new transform takes advantage of its long, overlapping basis functions to represent smooth signals in order to reduce blocking artifacts, whereas it reserves short basis functions for high-frequency signal components like edges and texture, thereby limiting ringing artifacts. Two design methods are presented, each with its own set of advantages: the first is based on a direct lattice factorization, and the second enforces certain relationships between the lattice coefficients to obtain variable length filters. Various necessary conditions for the existence of meaningful solutions are derived and discussed in both cases. Finally, several design and image coding examples are presented to confirm the validity of the theory     

Design of orthogonal and biorthogonal lapped transforms satisfyingperception related constraints

We propose a new efficient method for the design of orthogonal and biorthogonal lapped transforms for image coding applications. It is shown how perception related constraints such as decay and smoothness of the filters' impulse responses can be incorporated in the optimization procedure. A decomposition of lapped transforms (orthogonal and biorthogonal) with 50% overlap leads to an efficient recursive optimization procedure, which is robust with respect to initial solutions. The importance of this decomposition lies in the fact that it allows to decouple the design of the even-symmetric and the odd-symmetric filters and hence drastically reduces the number of variables to be optimized. It furthermore reveals all the variables predetermined by perception related and coding-efficiency related constraints imposed on the filters. We present design and coding examples demonstrating the perceptual performance and the rate distortion performance of the resulting transforms.     

Directional Lapped Transforms for Image Coding

In this paper, we present the design of directional lapped transforms for image coding. A lapped transform, which can be implemented by a prefilter followed by a discrete cosine transform (DCT), can be factorized into elementary operators. The corresponding directional lapped transform is generated by applying each elementary operator along a given direction. The proposed directional lapped transforms are not only nonredundant and perfectly reconstructed, but they can also provide a basis along an arbitrary direction. These properties, along with the advantages of lapped transforms, make the proposed transforms appealing for image coding. A block-based directional transform scheme is also presented and integrated into HD Phtoto, one of the state-of-the-art image coding systems, to verify the effectiveness of the proposed transforms.     

A biorthogonal transform with overlapping and non-overlapping basis functions for image coding

The paper presents a novel design method of a biorthogonal lapped transform that consists of long (overlapping) and short (nonoverlapping) basis functions (VLLBT, variable-length function lapped biorthogonal transform), which can reduce annoying blocking artifacts and ringing. We formulate the VLLBT by extending conventional lapped transforms. Then, we provide the theory of the Karhunen-Loeve transform in a subspace (SKLT). Using the theory of the SKLT, we show that given the biorthogonal long basis functions of the VLLBT, the optimal short basis functions in the energy compaction sense are derived by solving an eigenvalue problem without iterative searching techniques. This leads to a desirable feature from a parameter optimization point of view since the degree of freedom for the VLLBT can be theoretically reduced by means of the SKLT. Moreover, the SKLT easily enables us to construct a two-dimensional (2D) VLLBT with nonseparable short basis functions. Experimental results show that, compared to the case where all parameters are optimized, the reduction of free parameters by using the SKLT causes no decline in coding gain for the AR(1) process, and the proposed transform provides promising performance in the efficiency of image coding.     

Integer lapped transforms and their applications to image coding

This paper proposes new integer approximations of the lapped transforms, called the integer lapped transforms (ILT), and studies their applications to image coding. The ILT are derived from a set of orthogonal sinusoidal transforms having short integer coefficients, which can be implemented with simple integer arithmetic. By employing the same scaling constants in these integer sinusoidal transforms, integer versions of the lapped orthogonal transform (LOT), the lapped biorthogonal transform (LBT), and the hierarchical lapped biorthogonal transform (HLBT) are developed. The ILTs with 5-b integer coefficients are found to have similar coding gain (within 0.06 dB) and image coding performances as their real-valued counterparts. Furthermore, by representing these integer coefficients as sum of powers-of-two coefficients (SOPOT), multiplier-less lapped transforms with very low implementation complexity are obtained. In particular, the implementation of the eight-channel multiplier-less integer LOT (ILOT), LBT (ILBT), and HLBT (IHLBT) require 90 additions and 44 shifts, 98 additions and 59 shifts, and 70 additions and 38 shifts, respectively.     

The generalized lapped pseudo-biorthogonal transform: oversampled linear-phase perfect reconstruction filterbanks with lattice structures

We investigate a lattice structure for a special class of N-channel oversampled linear-phase perfect reconstruction filterbanks with a decimation factor M smaller than N. We deal with systems in which all analysis and synthesis filters have the same finite impulse response (FIR) length and share the same center of symmetry. We provide the minimal lattice factorization of a polyphase matrix of a particular class of these oversampled filterbanks (FBs). All filter coefficients are parameterized by rotation angles and positive values. The resulting lattice structure is able to provide fast implementation and allows us to determine the filter coefficients by solving an unconstrained optimization problem. We consider next the case where we are given the generalized lapped pseudo-biorthogonal transform (GLPBT) lattice structure with specific parameters, and we a priori know the correlation matrix of noise that is added in the transform domain. In this case, we provide an alternative lattice structure that suppress the noise. We show that the proposed systems with the lattice structure cover a wide range of linear-phase perfect reconstruction FBs. We also introduce a new cost function for oversampled FB design that can be obtained by generalizing the conventional coding gain. Finally, we exhibit several design examples and their properties.     

Linear-phase perfect reconstruction filter bank: lattice structure,design, and application in image coding

A lattice structure for an M-channel linear-phase perfect reconstruction filter bank (LPPRFB) based on the singular value decomposition (SVD) is introduced. The lattice can be proven to use a minimal number of delay elements and to completely span a large class of LPPRFBs: all analysis and synthesis filters have the same FIR length, sharing the same center of symmetry. The lattice also structurally enforces both linear-phase and perfect reconstruction properties, is capable of providing fast and efficient implementation, and avoids the costly matrix inversion problem in the optimization process. From a block transform perspective, the new lattice can be viewed as representing a family of generalized lapped biorthogonal transform (GLBT) with an arbitrary number of channels M and arbitrarily large overlap. The relaxation of the orthogonal constraint allows the GLBT to have significantly different analysis and synthesis basis functions, which can then be tailored appropriately to fit a particular application. Several design examples are presented along with a high-performance GLBT-based progressive image coder to demonstrate the potential of the new transforms     

LINC: a common theory of transform and subband coding

A common theory of lapped orthogonal transforms (LOTs) and critically sampled filter banks, called L into N coding (LINC), is presented. The theory includes a unified analysis of both coding methods and identity relations between the transform, inverse transform, analysis filter bank, and synthesis filter bank. A design procedure for LINC analysis/synthesis systems, which satisfy the conditions for perfect reconstruction, is developed. The common LINC theory is used to define an ideal LINC system which is used, together with the power spectral density of the input signal, to calculate theoretical bounds for the coding gain. A generalized overlapping block transform (OBT) with time domain aliasing cancellation (TDAC) is used to approximate the ideal LINC. A generalization of the OBT includes multiple block overlap and additional windowing. A recursive design procedure for windows of arbitrary lengths is presented. The coding gain of the generalized OBT is higher than that of the Karhunen-Loeve transform (KLT) and close to the theoretical bounds for LINC. In the case of image coding, the generalized OBT reduces the blocking effects when compared with the DCT     

The GenLOT: generalized linear-phase lapped orthogonal transform

The general factorization of a linear-phase paraunitary filter bank (LPPUFB) is revisited. From this new perspective, a class of lapped orthogonal transforms with extended overlap (generalized linear-phase lapped orthogonal transforms (GenLOTs)) is developed as a subclass of the general class of LPPUFB. In this formulation, the discrete cosine transform (DCT) is the order-1 GenLOT, the lapped orthogonal transform is the order-2 GenLOT, and so on, for any filter length that is an integer multiple of the block size. The GenLOTs are based on the DCT and have fast implementation algorithms. The implementation of GenLOTs is explained, including the method to process finite-length signals. The degrees of freedom in the design of GenLOTs are described, and design examples are presented along with image compression tests     

Fast downscaled inverses for images compressed with M-channellapped transforms

Compressed images may be decompressed and displayed or printed using different devices at different resolutions. Full decompression and rescaling in space domain is a very expensive method. We studied downscaled inverses where the image is decompressed partially, and a reduced inverse transform is used to recover the image. In this fashion, fewer transform coefficients are used and the synthesis process is simplified. We studied the design of fast inverses, for a given forward transform. General solutions are presented for M-channel finite impulse response (FIR) filterbanks, of which block and lapped transforms are a subset. Designs of faster inverses are presented for popular block and lapped transforms.     

A family of lapped regular transforms with integer coefficients

Invertible transforms with integer coefficients are highly desirable because of their fast, efficient, VLSI-suitable implementations and their lossless coding capability. In this paper, a large class of lapped regular transforms with integer coefficients (ILT) is presented. Regularity constraints are also taken into account to provide smoother reconstructed signals. In other words, this ILT family can be considered to be an M-band biorthogonal wavelet with integer coefficients. The ILT also possesses a fast and efficient lattice that structurally enforces both linear-phase and exact reconstruction properties. Preliminary image coding experiments show that the ILT yields comparable objective and subjective performance to those of popular state-of-the-art transforms with floating-point coefficients     

Generalized unequal length lapped orthogonal transform for subband image coding

Generalized linear phase lapped orthogonal transforms with unequal length basis functions (GULLOTs) are considered. The length of each basis of the proposed GULLOT can be different from each other, whereas all the bases of the conventional GenLOT are of equal length. In general, for image coding application, the long basis for a low-frequency band and the short basis for a high-frequency one are desirable to reduce the blocking and the ringing artifact simultaneously. Therefore, the GULLOT is suitable especially for a subband image coding. In order to apply the GULLOT to a subband image coding, we also investigate the size-limited structure to process the finite length signal, which is important in practice. Finally, some design and image coding examples are shown to confirm the validity of the proposed GULLOT.     

Biorthogonal and nonuniform lapped transforms for transform codingwith reduced blocking and ringing artifacts

New lapped transforms are introduced. The lapped biorthononal transform (LBT) and hierarchical lapped biorthogonal transform (HLBT) are appropriate for image coding, and the modulated HLBT biorthogonal transform (MMLBT) and nonuniform modulated lapped biorthogonal transform (NMLBT) are appropriate for audio coding. The HLBT has a significantly lower computational complexity than the lapped orthogonal transform (LOT), essentially no blocking artifacts, and fewer ringing artifacts than the commonly used discrete cosine transform (DCT). The LBT and HLBT have transform coding gains that are typically between 0.5 and 1.2 dB higher than that of the DCT. Image coding examples using JPEG and embedded zerotree coders demonstrate the better performance of the LET and HLBT. The NMLBT has fewer ringing artifacts and better reproduction of transient sounds than the MLT, as shown in audio coding examples. Fast algorithms for both the HLBT and the NMLBT are presented     

A Direct Design of Oversampled Perfect Reconstruction FIR Filter Banks

We address a problem to find optimal synthesis filters of oversampled uniform finite-impulse-response (FIR) filter banks (FBs) yielding perfect reconstruction (PR), when we are given an analysis FB, in the case where all the filters have the same length that is twice a factor of downsampling. We show that in this class of FBs, a synthesis FB that achieves PR can be found in closed form with elementary matrix operations, unlike conventional design methods with numerical optimization. This framework allows filter coefficients to be complex as well as real. Due to the extra degrees of freedom in a synthesis FB provided by oversampling, we can determine optimal coefficients of synthesis filters that meet certain criteria. We introduce in this paper two criteria: variance of additive noise and stopband attenuation. We show theoretical results of optimal synthesis filters that minimize these criteria and design examples of oversampled linear-phase FIR FBs and DFT-modulated FBs. Moreover, we discuss applications to signal reconstruction from incomplete channel data in transmission and inverse transform of windowed discrete Fourier transform with 50% overlapping.     

Group testing for image compression using alternative transforms

This paper extends the group testing for wavelets (IEEE Trans. Image Process. 11 (2002) 901) algorithm to code coefficients from the wavelet packet transform, the discrete cosine transform, and various lapped transforms. Group testing offers a noticeable improvement over zerotree coding techniques on these transforms; is inherently flexible; and can be adapted to different transforms with relative ease. The new algorithms are competitive with many recent state-of-the-art image coders that use the same transforms.     

Encoding of images based on a lapped orthogonal transform

Traditional block transform image coding systems generate artifacts near block boundaries which degrade low bit rate coded images. To reduce these artifacts, a class of unitary transformations, called lapped orthogonal transforms (LOT), is investigated. The basis function on which the signal is projected are overlapped for adjacent blocks. An example of an LOT optimized in terms of energy compaction is numerically derived, using an augmented Lagrangian optimization algorithm. Using this LOT, intraframe coding experiments for 256×240 pixel images were performed at bit rates between 0.1 and 0.35 bits/pixel. The LOT improved the coded image subjective quality over other transforms. The LOT was also used in interframe full-motion video coding experiments for head and shoulder sequences at 28 and 56 kb/s. Significant improvement resulted at low data rates and if no motion compensation were used. However, the improvement was no longer significant at 56 kb/s with full motion compensation     

An orientation-selective orthogonal lapped transform

A novel critically sampled orientation-selective orthogonal lapped transform called the lapped Hartley transform (LHT) is derived. In a first step, overlapping basis functions are generated by modulating basis functions of a 2-D block Hartley transform by a cosine wave. To achieve invertibility and orthogonality, an iterative filter is applied as prefilter in the analysis and as postfilter in the synthesis operation, respectively. Alternatively, filtering can be restricted to analysis or synthesis, ending up with a biorthogonal transform (LHT-PR, LHT-PO). A statistical analysis based on a 4000-image data base shows that the LHT and LHT-PO have better redundancy removal properties than other block or lapped transforms. Finally, image compression and noise removal examples are given, showing the advantages of the LHT especially in images containing oriented textures.     

Extended lapped transforms: properties, applications, and fastalgorithms

The family of lapped orthogonal transforms is extended to include basis functions of arbitrary length. Within this new family, the extended lapped transform (ELT) is introduced, as a generalization of the previously reported modulated lapped transform (MLT). Design techniques and fast algorithms for the ELT are presented, as well as examples that demonstrate the good performance of the ELT in signal coding applications. Therefore, the ELT is a promising substitute for traditional block transforms in transform coding systems, and also a good substitute for less efficient filter banks in subband coding systems     

Undersampled boundary pre-/postfilters for low bit-rate DCT-based block coders.

It has been well established that critically sampled boundary pre-/postfiltering operators can improve the coding efficiency and mitigate blocking artifacts in traditional discrete cosine transform-based block coders at low bit rates. In these systems, both the prefilter and the postfilter are square matrices. This paper proposes to use undersampled boundary pre- and postfiltering modules, where the pre-/postfilters are rectangular matrices. Specifically, the prefilter is a "fat" matrix, while the postfilter is a "tall" one. In this way, the size of the prefiltered image is smaller than that of the original input image, which leads to improved compression performance and reduced computational complexities at low bit rates. The design and VLSI-friendly implementation of the undersampled pre-/postfilters are derived. Their relations to lapped transforms and filter banks are also presented. Two design examples are also included to demonstrate the validity of the theory. Furthermore, image coding results indicate that the proposed undersampled pre-/postfiltering systems yield excellent and stable performance in low bit-rate image coding.     

On the performance of linear phase wavelet transforms in lowbit-rate image coding

The behavior of linear phase wavelet transforms in low bit-rate image coding is investigated. The influence of certain characteristics of these transforms such as regularity, number of vanishing moments, filter length, coding gain, frequency selectivity, and the shape of the wavelets on the coding performance is analyzed. The wavelet transforms performance is assessed based on a first-order Markov source and on the image quality, using subjective tests. More than 20 wavelet transforms of a test image were coded with a product code lattice quantizer with the image quality rated by different viewers. The results show that, as long as the wavelet transforms perform reasonably well, features like regularity and number of vanishing moments do not have any important impact on final image quality. The influence of the coding gain by itself is also small. On the other hand, the shape of the synthesis wavelet, which determines the visibility of coding errors on reconstructed images, is very important. Analysis of the data obtained strongly suggests that the design of good wavelet transforms for low bit-rate image coding should take into account chiefly the shape of the synthesis wavelet and, to a lesser extent, the coding.