Rate-distortion estimation for fast JPEG2000 compression at low bit-rates

In JPEG2000 block coding, all coding passes are generated before rate allocation is performed among code blocks. Unwanted passes are then discarded. For low bit-rate coding, this results in a large number of coding passes being discarded. A rate-distortion estimation method that enables precompression rate-distortion optimisation to be carried out, wherein only the required passes need to be coded is presented. Experiments using the proposed technique demonstrate speed-up factors ranging from 1.17 to 1.78 at 0.0625 bpp, for JPEG2000 compression.     

Image sequence coding using quadtree-based block-matching motioncompensation and classified vector quantisation

The authors propose a new image sequence coding algorithm based on two crucial methods: quadtree segmentation and classified vector quantisation (CVQ). Overall coding rates are efficiently lowered by quadtree segmentation while visual quality is well preserved by a CVQ method. A moving-block extraction technique is employed to greatly improve the coding efficiency in the interframe coding mode. A quadtree efficiently segments the stationary background regions of interframe differential signals with various large-sized blocks, and the moving regions are extracted from the smallest blocks of 4×4 size during the growth of the quadtree. These moving regions are motion-compensated using a block-matching method based on 4×4 blocks and the residual signals of the motion-compensated moving regions are coded by CVQ. The stationary regions are simply replenished from the previous frame. The proposed coding scheme is effective for coding the sequential signals of video telephony or video conferencing at low bit rates     

Highly scalable video compression with scalable motion coding

A scalable video coder cannot be equally efficient over a wide range of bit rates unless both the video data and the motion information are scalable. We propose a wavelet-based, highly scalable video compression scheme with rate-scalable motion coding. The proposed method involves the construction of quality layers for the coded sample data and a separate set of quality layers for the coded motion parameters. When the motion layers are truncated, the decoder receives a quantized version of the motion parameters used to code the sample data. The effect of motion parameter quantization on the reconstructed video distortion is described by a linear model. The optimal tradeoff between the motion and subband bit rates is determined after compression. We propose two methods to determine the optimal tradeoff, one of which explicitly utilizes the linear model. This method performs comparably to a brute force search method, reinforcing the validity of the linear model itself. Experimental results indicate that the cost of scalability is small. In addition, considerable performance improvements are observed at low bit rates, relative to lossless coding of the motion information.     

Novel image compression method using edge-oriented classifier andnovel predictive noiseless coding method

A new image compression approach is proposed in which variable block size technique is adopted, using quadtree decomposition, for coding images at low bit rates. In the proposed approach, low-activity regions, which usually occupy large areas in an image, were coded with a larger block size and the block mean is used to represent each pixel in the block. To preserve edge integrity, the classified vector quantisation (CVQ) technique is used to code high-activity regions. A new edge-oriented classifier without employing any thresholds is proposed for edge classification. A novel predictive noiseless coding (NPNC) method which exploits the redundancy between neighbouring blocks is also presented to efficiently code the mean values of low-activity blocks and the addresses of edge blocks. The bit rates required for coding the mean values and addresses can be significantly reduced by the proposed NPNC method. Experimental results show that excellent reconstructed images and higher PSNR were obtained     

Index-compressed vector quantisation based on index mapping

The authors introduce a novel coding technique which significantly improves the performance of the traditional vector quantisation (VQ) schemes at low bit rates. High interblock correlation in natural images results in a high probability that neighbouring image blocks are mapped to small subsets of the VQ codebook, which contains highly correlated codevectors. If, instead of the whole VQ codebook, a small subset is considered for the purpose of encoding neighbouring blocks, it is possible to improve the performance of traditional VQ schemes significantly. The performance improvement obtained with the new method is about 3 dB on average when compared with traditional VQ schemes at low bit rates. The method provides better performance than the JPEG coding standard at low bit rates, and gives comparable results with much less complexity than address VQ     

Optimal buffered compression and coding mode selection for MPEG-4shape coding

We propose an optimal buffered compression algorithm for shape coding as defined in the forthcoming MPEG-4 international standard. The MPEG-4 shape coding scheme consists of two steps: first, distortion is introduced by down and up scaling; then, context-based arithmetic encoding is applied. Since arithmetic coding is "lossless," the down up scaling step is considered as a virtual quantizer. We first formulate the buffer-constrained adaptive quantization problem for shape coding, and then propose an algorithm for the optimal solution under buffer constraints. Previously, the fact that a conversion ratio (CR) of 1/4 makes a coded image irritating to human observers for QCIF size was reported for MPEG-4 shape coding. Therefore, careful consideration for small size images such as QCIF should be given to prevent coded images from being unacceptable. To this end, a low bit rate tuned algorithm is proposed in this paper as well. Experimental results are given using an MPEG-4 shape codec.     

View-dependent 3-D mesh coding by rate allocation with the image rendering-based distortion measures

Low-bandwidth transmission of synthetic digital content to the end user device in the form of a scene of 3-D meshes requires efficient compression of the mesh geometry. For applications in which the meshes are observed from a single viewpoint, this work explores the use of the image rendering-based distortion measures in rate allocation to their surface regions for view-dependent mesh geometry compression. It is experimentally demonstrated that the image rendering-based distortion measures yield far superior performance (the quality of the rendered image of the reconstructed scene from a viewpoint at a given rate) in optimal rate allocation than other previously proposed distortion measures. A fast rate allocation method is also proposed for use with the image rendering-based measures for real-time or interactive applications. Not only does this method have significantly lower complexity than the optimal rate allocation method due to the rendering of the images of the reconstructed meshes at only judiciously selected rate–distortion operating points, but also its coding performance is just as competitive. Further complexity reduction in rate allocation, through rendering of only the coded regions of the meshes, is also investigated.     

Source fidelity over fading channels: performance of erasure and scalable codes

We consider the transmission of a Gaussian source through a block fading channel. Assuming each block is decoded independently, the received distortion depends on the tradeoff between quantization accuracy and probability of outage. Namely, higher quantization accuracy requires a higher channel code rate, which increases the probability of outage. We first treat an outage as an erasure, and evaluate the received mean distortion with erasure coding across blocks as a function of the code length. We then evaluate the performance of scalable, or multi-resolution coding in which coded layers are superimposed within a coherence block, and the layers are sequentially decoded. Both the rate and power allocated to each layer are optimized. In addition to analyzing the performance with a finite number of layers, we evaluate the mean distortion at high signal-to-noise ratios as the number of layers becomes infinite. As the block length of the erasure code increases to infinity, the received distortion converges to a deterministic limit, which is less than the mean distortion with an infinite-layer scalable coding scheme. However, for the same standard deviation in received distortion, infinite layer scalable coding performs slightly better than erasure coding, and with much less decoding delay.     

Adaptive lossless coding scheme of lattice vector quantisation

In the process of quantisation, a lattice vector quantiser (LVQ) generates radius and index sequences. In lossless coding, the radius sequence is run-length coded and then Huffman or arithmetic coded, and the index sequence is represented by fixed binary bits. The author has improved the LVQ lossless coding by removing the redundant information between radius sequence and index sequence. An algorithm is developed that redistributes radius and index sequences. The algorithm adaptively shifts down large indices to smaller values and reduces the index bits. Hence, the proposed LVQ lossless coding method reduces the gap between actual coding bit rates and the optimal bit rate boundary. For a Laplacian source the proposed lossless coding scheme achieves more than 10% of bit reduction at bit rates higher than 0.7 bits/sample over the traditional lossless coding method     

Rate distortion optimization for H.264 interframe coding: a general framework and algorithms.

Rate distortion (RD) optimization for H.264 interframe coding with complete baseline decoding compatibility is investigated on a frame basis. Using soft decision quantization (SDQ) rather than the standard hard decision quantization, we first establish a general framework in which motion estimation, quantization, and entropy coding (in H.264) for the current frame can be jointly designed to minimize a true RD cost given previously coded reference frames. We then propose three RD optimization algorithms--a graph-based algorithm for near optimal SDQ in H.264 baseline encoding given motion estimation and quantization step sizes, an algorithm for near optimal residual coding in H.264 baseline encoding given motion estimation, and an iterative overall algorithm to optimize H.264 baseline encoding for each individual frame given previously coded reference frames-with them embedded in the indicated order. The graph-based algorithm for near optimal SDQ is the core; given motion estimation and quantization step sizes, it is guaranteed to perform optimal SDQ if the weak adjacent block dependency utilized in the context adaptive variable length coding of H.264 is ignored for optimization. The proposed algorithms have been implemented based on the reference encoder JM82 of H.264 with complete compatibility to the baseline profile. Experiments show that for a set of typical video testing sequences, the graph-based algorithm for near optimal SDQ, the algorithm for near optimal residual coding, and the overall algorithm achieve on average, 6%, 8%, and 12%, respectively, rate reduction at the same PSNR (ranging from 30 to 38 dB) when compared with the RD optimization method implemented in the H.264 reference software.     

3D-HEVC合并模式快速判决方法研究

基于高效视频编码的3D视频编码（3D-HEVC）是目前正在研究的新一代3D视频编码标准。为降低3D-HEVC中模式选择的计算复杂度,根据非独立视点纹理图中合并模式采用率高的特点,该文提出了一种3D-HEVC合并模式快速判决方法。在B帧中,分析了当前编码单元（CU）与视点方向参考帧中参考块间编码模式的相关性;在P帧中,分析了位于相邻划分深度的CU间编码模式的相关性。根据分析的视点间和划分深度间的相关性设计快速判决条件,预判采用合并/合并-跳过模式编码的CU,判别出的CU在模式选择过程中只检查相关的候选预测模式,从而降低计算复杂度。实验结果表明,与3D-HEVC原始算法相比,该文算法能够在率失真性能损失很小的前提下,平均节省11.2%的总编码时间和25.4%的非独立视点纹理图的编码时间。      

Strong converses in source coding relative to a fidelity criterion

Two strong converses are obtained for an abstract alphabet stationary ergodic source coded relative to an appropriate fidelity criterion. It is shown that given a distortion rate point (D, R) that lies below the rate distortion curve, (1) block codes that operate at rate level R must encode sample source blocks at a rate exceeding D with probability tending to one as the block length tends to infinity, and (2) variable-rate codes that operate at distortion level D must encode sample source blocks at a rate exceeding R with probability tending to one as the block length tends to infinity. The previously known weak converses guarantee only that the indicated probabilities remain bounded away from zero as block length tends to infinity. The proofs of the strong converses involve sample converses in source coding theory     

Novel embedded image coding algorithms based on wavelet difference reduction

Wavelet difference reduction (WDR) has recently been proposed as a method for efficient embedded image coding. In this paper, the WDR algorithm is analysed and four new techniques are proposed to either reduce its complexity or improve its rate distortion (RD) performance. The first technique, dubbed modified WDR-A (MWDR-A), focuses on improving the efficiency of the arithmetic coding (AC) stage of the WDR. Based on experiments with the statistics of the output symbol sequence, it is shown that the symbols can either be arithmetic coded under different contexts or output without AC. In the second technique, MWDR-B, the AC stage is dropped from the coder. By employing MWDR-B, up to 20% of coding time can be saved without sacrificing the RD performance, when compared to WDR. The third technique focuses on the improvement of RD performance using context modelling. A low-complexity context model is proposed to exploit the statistical dependency among the wavelet coefficients. This technique is termed context-modelled WDR (CM-WDR), and acts without the AC stage to improve the RD performance by up to 1.5 dB over WDR on a set of test images, at various bit rates. The fourth technique combines CM-WDR with AC and achieves a 0.2 dB improvement over CM-WDR in terms of PSNR. The proposed techniques retain all the features of WDR, including low complexity, region-of-interest capability, and embeddedness.     

一种H.264视频流自适应率失真优化编码算法

为了提高编码视频流在丢包网络环境中的抗误码性能,目前比较常用的是采用帧内刷新算法.在率失真框架之内的帧内优化编码刷新算法,则被认为是更为直接和有效的解决办法.在视频编码标准H.264/JVT中采用的就是这种算法.然而由于没有考虑到信道丢包率对编码器端进行仿真解码次数的影响,从而导致在进行率失真优化编码时的计算量较大,编码耗时较长,严重影响了编码器的编码效率.基于以上分析,提出了一种改进的自适应率失真优化编码算法.将H.264标准率失真优化编码算法中计算解码器端视频帧期望失真度的代数平均值算法,改进为加权平均值算法.仿真实验表明,提出的算法可根据信道丢包率和模拟信道状态个数信息来自适应地决定编码器端进行仿真解码计算的次数,从而有效降低H.264标准率失真优化编码算法中的计算冗余和计算复杂度,节省编码耗时.在模拟信道状态个数默认为30个时,本算法最多可节省近55%的编码耗时.     

Rate distortion optimal bit allocation methods for volumetric data using JPEG 2000.

Computer modeling programs that generate three-dimensional (3-D) data on fine grids are capable of generating very large amounts of information. These data sets, as well as 3-D sensor/measured data sets, are prime candidates for the application of data compression algorithms. A very flexible and powerful compression algorithm for imagery data is the newly released JPEG 2000 standard. JPEG 2000 also has the capability to compress volumetric data, as described in Part 2 of the standard, by treating the 3-D data as separate slices. As a decoder standard, JPEG 2000 does not describe any specific method to allocate bits among the separate slices. This paper proposes two new bit allocation algorithms for accomplishing this task. The first procedure is rate distortion optimal (for mean squared error), and is conceptually similar to postcompression rate distortion optimization used for coding codeblocks within JPEG 2000. The disadvantage of this approach is its high computational complexity. The second bit allocation algorithm, here called the mixed model (MM) approach, mathematically models each slice's rate distortion curve using two distinct regions to get more accurate modeling at low bit rates. These two bit allocation algorithms are applied to a 3-D Meteorological data set. Test results show that the MM approach gives distortion results that are nearly identical to the optimal approach, while significantly reducing computational complexity.     

Entropy-constrained tree-structured vector quantizer design

Current methods for the design of pruned or unbalanced tree-structured vector quantizers such as the generalized Breiman-Friedman-Olshen-Stone (GBFOS) algorithm proposed in 1980 are effective, but suffer from several shortcomings. We identify and clarify issues of suboptimality including greedy growing, the suboptimal encoding rule, and the need for time sharing between quantizers to achieve arbitrary rates. We then present the leaf-optimal tree design (LOTD) method which, with a modest increase in design complexity, alters and reoptimizes tree structures obtained from conventional procedures. There are two main advantages over existing methods. First, the optimal entropy-constrained nearest-neighbor rule is used for encoding at the leaves; second, explicit quantizer solutions are obtained at all rates without recourse to time sharing. We show that performance improvement is theoretically guaranteed. Simulation results for image coding demonstrate that close to 1 dB reduction of distortion for a given rate can be achieved by this technique relative to the GBFOS method.     

A transform tree code for stationary Gaussian sources

A new tree code is introduced for discrete-time stationary Gaussian sources with hounded, integrable power spectra and the squared-error distortion measure. The codewords in the tree are reconstructions of Karhunen-Loève transforms of the source words. The branching factor and the number of code letters per branch may vary with level in the tree. A theorem that guarantees the existence of an optimal code for any code rate using such a tree is proved. The proof uses the random coding argument in conjunction with a theorem on survival of a branching process with random environment. A suboptimal but computationally affordable realization of the theorem's coding technique was used for encoding simulations for six autoregressive sources at rates of1.0, 0.50, 0.25, and0.10bits per source symbol. The average distortion results were generally within1dB of the distortion-rate bound but varied widely depending on the source and rate. The results were compared with those for transform quantization simulations for the same sources and rates. The tree code always performed better but only by an average of0.44dB all sources and rates. Longer source blocks and more intensive search would certainly improve the performance of the tree codes, but at the expense of extra computation and storage.     

A successive approximation vector quantizer for wavelet transformimage coding

A coding method for wavelet coefficients of images using vector quantization, called successive approximation vector quantization (SA-W-VQ) is proposed. In this method, each vector is coded by a series of vectors of decreasing magnitudes until a certain distortion level is reached. The successive approximation using vectors is analyzed, and conditions for convergence are derived. It is shown that lattice codebooks are an efficient tool for meeting these conditions without the need for very large codebooks. Regular lattices offer the extra advantage of fast encoding algorithms. In SA-W-VQ, distortion equalization of the wavelet coefficients can be achieved together with high compression ratio and precise bit-rate control. The performance of SA-W-VQ for still image coding is compared against some of the most successful image coding systems reported in the literature. The comparison shows that SA-W-VQ performs remarkably well at several bit rates and in various test images.     

On multirate optimality of JPEG2000 code stream.

Arguably, the most important and defining feature of the JPEG2000 image compression standard is its R-D optimized code stream of multiple progressive layers. This code stream is an interleaving of many scalable code streams of different sample blocks. In this paper, we reexamine the R-D optimality of JPEG2000 scalable code streams under an expected multirate distortion measure (EMRD), which is defined to be the average distortion weighted by a probability distribution of operational rates in a given range, rather than for one or few fixed rates. We prove that the JPEG2000 code stream constructed by embedded block coding of optimal truncation is almost optimal in the EMRD sense for uniform rate distribution function, even if the individual scalable code streams have nonconvex operational R-D curves. We also develop algorithms to optimize the JPEG2000 code stream for exponential and Laplacian rate distribution functions while maintaining compatibility with the JPEG2000 standard. Both of our analytical and experimental results lend strong support to JPEG2000 as a near-optimal scalable image codec in a fairly general setting.     

Fractal image compression with region-based functionality

Region-based functionality offered by the MPEG-4 video compression standard is also appealing for still images, for example to permit object-based queries of a still-image database. A popular method for still-image compression is fractal coding. However, traditional fractal image coding uses rectangular range and domain blocks. Although new schemes have been proposed that merge small blocks into irregular shapes, the merging process does not, in general, produce semantically-meaningful regions. We propose a new approach to fractal image coding that permits region-based functionalities; images are coded region by region according to a previously-computed segmentation map. We use rectangular range and domain blocks, but divide boundary blocks into segments belonging to different regions. Since this prevents the use of standard dissimilarity measure, we propose a new measure adapted to segment shape. We propose two approaches: one in the spatial and one in the transform domain. While providing additional functionality, the proposed methods perform similarly to other tested methods in terms of PSNR but often result in images that are subjectively better. Due to the limited domain-block codebook size, the new methods are faster than other fractal coding methods tested. The results are very encouraging and show the potential of this approach for various internet and still-image database applications.