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     

Image coding using lapped biorthogonal transform

The wireless sensor network utilizes image compression algorithms like JPEG, JPEG2000, and SPIHT for image transmission with high coding efficiency. During compression, discrete cosine transform (DCT)–based JPEG has blocking artifacts at low bit-rates. But this effect is reduced by discrete wavelet transform (DWT)–based JPEG2000 and SPIHT algorithm but it possess high computational complexity. This paper proposes an efficient lapped biorthogonal transform (LBT)–based low-complexity zerotree codec (LZC), an entropy coder for image coding algorithm to achieve high compression. The LBT-LZC algorithm yields high compression, better visual quality with low computational complexity. The performance of the proposed method is compared with other popular coding schemes based on LBT, DCT and wavelet transforms. The simulation results reveal that the proposed algorithm reduces the blocking artifacts and achieves high compression. Besides, it is analyzed for noise resilience.     

Complexity-constrained best-basis wavelet packet algorithm forimage compression

The concept of adapted waveform analysis using a best-basis selection out of a predefined library of wavelet packet (WP) bases allows an efficient image representation for the purpose of compression. Image coding methods based on the best-basis WP representation have shown significant coding gains for some image classes compared with methods using a fixed dyadic structured wavelet basis, at the expense however, of considerably higher computational complexity. A modification of the best-basis method, the so-called complexity constrained best-basis algorithm (CCBB), is proposed which parameterises the complexity gap between the fast (standard) wavelet transform and the best wavelet packet basis of a maximal WP library. This new approach allows a `suboptimal' best basis to be found with respect to a given budget of computational complexity or, in other words, it offers an instrument to control the trade-off between compression speed and, coding efficiency. Experimental results are presented for image coding applications showing a highly nonlinear relationship between the rate-distortion performance and the computational complexity in such a way that a relatively small increase in complexity with respect to the standard wavelet basis results in a relatively high rate distortion gain     

A 128 Kb/s Hi-Fi audio codec based on adaptive transform codingwith adaptive block size MDCT

A Hi-Fi audio codec with an improved adaptive transform coding (ATC) algorithm is presented using digital signal processors (DSPs). An audio signal with a 20 kHz bandwidth sampled at 48 kHz is coded at a rate of 128 kb/s. The algorithm utilizes adaptive block size selection, which is effective for preecho suppression. A modified discrete cosine transform (MDCT) with a simple window set is employed to reduce block boundary noise without decreasing the performance of transform coding. In addition, a fast MDCT calculation algorithm, based on a fast Fourier transform, is adopted. Weighted bit allocation is employed to quantize the transformed coefficients. The codec was realized by a multiprocessor system composed of newly developed DSP boards. Subjective tests with the codec show that the coding quality is comparable to that of compact disc signals     

A locally adaptive algorithm for measuring blocking artifacts in images and videos

Block transform coding is the most popular approach for image and video compression. The objective measurement of blocking artifacts plays an important role in the design, optimization, and assessment of image and video coding systems. This paper presents a new algorithm for measuring image quality of a BDCT coded images or videos. It exhibits unique and useful features: (1) it examines the blocks individually so that it can measure the severity of blocking artifacts locally; (2) it is a one-pass algorithm in the sense that the image needs to be accessed only once; (3) it takes into account the blocking artifacts for high bit rate images and the flatness for the very low bit rate images; (4) the quality measure is well defined in the range of 0–10. Experiments on various still images and videos show that the new quality measure is very efficient in terms of computational complexity and memory usage, and can produce consistent blocking artifacts measurement.     

Low complexity shape-adaptive DCT for coding of arbitrarily shaped image segments

A low complexity shape-adaptive DCT transform algorithm for coding pels in arbitrarily shaped image segments is presented. The proposed algorithm is compared to the well established generalized shape-adaptive transform method introduced by Gilge et al. in terms of transform efficiency and computational complexity. Results obtained under both theoretical and experimental conditions show that the new algorithm achieves a transform efficiency close to that of the Gilge method with considerably reduced computational complexity. The proposed shape-adaptive DCT algorithm was implemented into a standard MPEG-1 coder to provide object or segment based coding of images and video with additional content-based functionality. The extended MPEG-1 object based coding scheme can handle generic input sequences and can readily provide MPEG-1 backward compatibility if no contour data is transmitted for a given video sequence. Results for INTRA coding of images indicate that the algorithm allows efficient coding over a wide range of coding parameters — thus providing means for generic coding of segmented video between very high and very low bit rates. It is further shown that some of the content-based based functionalities currently discussed in MPEG-4 can be provided efficiently using the proposed object based coding scheme.     

变换编码中直流偏移的快速处理

根据变换编辑码的持点,对变换编码中直流偏移处理提出一种快速算法。该算法通过交流常规的直流偏移和变换的顺序,可大大减少直流偏移的运算次数,余弦变换编码器的每个编码块的直流偏移运算次数降低至一次,小波变换变换块后的真流运算降低至分析增益为1的子带大小。例如对8×的DCT块直流偏移次数只需1次,对采用MALLAT方式的L层分解的二维图像,直流偏移次数只有原来的1/4L.     

Best wavelet packet bases in a rate-distortion sense

A fast rate-distortion (R-D) optimal scheme for coding adaptive trees whose individual nodes spawn descendents forming a disjoint and complete basis cover for the space spanned by their parent nodes is presented. The scheme guarantees operation on the convex hull of the operational R-D curve and uses a fast dynamic programing pruning algorithm to markedly reduce computational complexity. Applications for this coding technique include R. Coefman et al.'s (Yale Univ., 1990) generalized multiresolution wavelet packet decomposition, iterative subband coders, and quadtree structures. Applications to image processing involving wavelet packets as well as discrete cosine transform (DCT) quadtrees are presented.     

Using edge direction information for measuring blocking artifacts of images

Block-based transform coding is the most popular approach for image and video compression. The objective measurement of blocking artifacts plays an important role in the design, optimization, and assessment of image and video coding systems. This paper presents a new algorithm for measuring blocking artifacts in images and videos. Instead of using the traditional pixel discontinuity along the block boundary, we use the edge directional information of the images. The new algorithm does not need the exact location of the block boundary thus is invariant to the displacement, rotation and scaling of the images. Experiments on various still images and videos show that the new blockiness measure is very efficient in terms of computational complexity and memory usage, and can produce blocking artifacts measurement consistent with subjective rating.     

二维滑动矩形窗傅氏变换的快速递推算法

该文利用相邻滑动窗数据之间的关系以及傅氏变换的平移性质,提出一种二维滑动矩形窗傅氏变换的快速递推算法。文中分析了该快速递推算法的复杂度和传统直接计算法的复杂度,证明了新的快速递推法可以大大降低计算复杂性,尤其是在图像尺寸和窗口尺寸较大的场合中。该算法可以改善滑窗傅氏变换或Gabor变换的计算效率。     

自适应分区DCT/DWT低码率视频编码算法

为了降低低码率视频编码算法的块效应与环效应，提出了一种基于自适应分区余弦变换／子波变换和重叠运动补偿的视频编码算法，首先给了一种空－是相关自适应运动估计算法，有效降低运算复杂性，然后通过过层游动窗块区域形成算法检测现帧间预测误差场的高能量区域，对大区域进行了子波变换和量化，对零散区域进行余弦变换和量化，根据人类视觉系统（ＨＶＳ）的空－频和时－频特性，给出基于ＨＶＳ的量化模型，以期在信噪比约束下获得     

Extended lapped transform in image coding

A modulated lapped transform with extended overlap (ELT) is investigated in image coding with the objective of verifying its potential to replace the discrete cosine transform (DCT) in specific applications. Some of the criteria utilized for the performance comparison are reconstructed image quality (both objective and subjective), reduction of blocking artifacts, robustness against transmission errors, and filtering (for scalability). Also, a fast implementation algorithm for finite-length-signals using symmetric extensions is developed specially for the ELT with overlap factor 2 (ELT-2). This comparison shows that ELT-2 is superior to both DCT and the lapped orthogonal transform (LOT).     

数字音频压缩中的变换编码算法

变换编码是音频压缩中的一个重要部分,文中叙述ＭＰＥＧ音频编码标准中的变换编码技术,包括改进余弦变换和反变换（ＭＤＣＴ和ＩＭＤＣＴ）时域混叠抵消与自适应窗选择,详细推导了ＭＤＣＴ和ＩＭＤＣＴ的快速算法。     

一种新的小波分形变换图像编码算法

提出了一种基于平滑双正交小波和自适应分割算法的小波域分形图像编码算法，在基于离散有限方差(DFV)最优准则下得到了适合图像编码的一种新的平滑双正交小波，从而改善了分块效应。在小波域的分形编码中，提出了一种基于图像信息分布特征的自适应分割算法，实验表明，该文算法在相同压缩比的情况下，解码图像的主观视觉质量和峰值信噪比都明显优于SQS方法、基本分形图像编码方法和SPIHT方法。     

基于三维变换域频谱差的视频显著性检测算法

显著性区域检测是计算机视觉的重要课题,对视频质量评价和感知视频编码算法优化也至关重要.大多显著性检测算法不能权衡准确率和复杂度,限制了它们在视频预处理和实时处理中的应用.提出了一种基于三维变换域频谱差(3DTDSD)的快速视频显著性检测算法,分别以关键帧及其前一帧为中心建立一定数量图像帧的滑动窗,得到两组3D视频体,用傅里叶变换将两组视频变换到三维频域,两组三维数据之间的差值经过反变换得到显著性图,最后通过连通分析、阈值判断等得到显著区域.频域算法具有运算速度快的特点,实验对比和算法复杂度分析证明了该算法的有效性和快速性.     

A Truncation method for computing slant transforms withapplications to image processing

A truncation method for computing the slant transform is presented. The slant transform truncation (STT) algorithm uses the divide and conquer principle of hierarchical data structures to factorize coherent image data into sparse subregions. In one dimension with a data array of size N=2ⁿ, the truncation method takes a time between O(N) and O(Nlog₂N), degenerating to the performance of the fast slant transform (FST) method in its worst case. In two dimensions, for a data array of size N×N, the one-dimensional truncation method is applied to each row, then to each column of the array, to compute the transform in a time between O(N²) and O(N²log₂N). Coherence is a fundamental characteristic of digital images and so the truncation method is superior to the FST method when computing slant transforms of digital images. Experimental results are presented to justify this assertion     

A 110-K transistor 25-MPixels/s configurable image transformprocessor unit

A configurable architecture for performing image transform algorithms is presented that provides a better tradeoff between low complexity and algorithm flexibility than either software-programmable processors or dedicated ASIC's. The configurable processor unit requires only 110 K transistors and can execute several image transform algorithms. By emulating the signal flow of the algorithms in hardware, rather than software, complexity is reduced by an order of magnitude compared with current software programmable video signal processors, while providing more flexibility than single function ASIC's. The processor has been fabricated in 1.2-μm CMOS and has been successfully used to execute the discrete cosine transform/inverse discrete cosine transform (DCT/IDCT), subband coding, vector quantization, and two-dimensional filtering algorithms at pixel rates up to 25 MPixels/s     

Hadamard transform image coding

The introduction of the fast Fourier transform algorithm has led to the development of the Fourier transform image coding technique whereby the two-dimensional Fourier transform of an image is transmitted over a channel rather than the image itself. This devlopement has further led to a related image coding technique in which an image is transformed by a Hadamard matrix operator. The Hadamard matrix is a square array of plus and minus ones whose rows and columns are orthogonal to one another. A high-speed computational algorithm, similar to the fast Fourier transform algorithm, which performs the Hadamard transformation has been developed. Since only real number additions and subtractions are required with the Hadamard transform, an order of magnitude speed advantage is possible compared to the complex number Fourier transform. Transmitting the Hadamard transform of an image rather than the spatial representation of the image provides a potential toleration to channel errors and the possibility of reduced bandwidth transmission.     

A fast and low memory image coding algorithm based on lifting wavelet transform and modified SPIHT

Due to its excellent rate–distortion performance, set partitioning in hierarchical trees (SPIHT) has become the state-of-the-art algorithm for image compression. However, the algorithm does not fully provide the desired features of progressive transmission, spatial scalability and optimal visual quality, at very low bit rate coding. Furthermore, the use of three linked lists for recording the coordinates of wavelet coefficients and tree sets during the coding process becomes the bottleneck of a fast implementation of the SPIHT. In this paper, we propose a listless modified SPIHT (LMSPIHT) approach, which is a fast and low memory image coding algorithm based on the lifting wavelet transform. The LMSPIHT jointly considers the advantages of progressive transmission, spatial scalability, and incorporates human visual system (HVS) characteristics in the coding scheme; thus it outperforms the traditional SPIHT algorithm at low bit rate coding. Compared with the SPIHT algorithm, LMSPIHT provides a better compression performance and a superior perceptual performance with low coding complexity. The compression efficiency of LMSPIHT comes from three aspects. The lifting scheme lowers the number of arithmetic operations of the wavelet transform. Moreover, a significance reordering of the modified SPIHT ensures that it codes more significant information belonging to the lower frequency bands earlier in the bit stream than that of the SPIHT to better exploit the energy compaction of the wavelet coefficients. HVS characteristics are employed to improve the perceptual quality of the compressed image by placing more coding artifacts in the less visually significant regions of the image. Finally, a listless implementation structure further reduces the amount of memory and improves the speed of compression by more than 51% for a 512×512 image, as compared with that of the SPIHT algorithm.     

Incremental Fourier interpolation of 2-D fractional Brownian motion

This paper presents a new method to interpolate two-dimensional fractional Brownian motion (fBm), fBm interpolation can be used in multimedia applications such as landscape synthesis or zooming into a synthetic scene, where the objective is to generate an fBm field that passes through a sparse set of known points. The fBm interpolation problem differs from standard image interpolation because noise must be added to the interpolated points to obtain an interpolated image with the proper second-order statistics. Our interpolation method is based on the first-order increments of both the original fBm and interpolated fBm. These increments are stationary and yield interpolation equations with a Toeplitz-block-Toeplitz structure which can be approximated by a circulant-block-circulant matrix. By taking advantage of fast Fourier transform, the computational complexity is O(N²log₂N) for N×N image interpolation. Simulation shows this method achieves good second-order statistics, even for small-size images