This article presents four modifications to the JPEG arithmetic coding (JAC) algorithm, a topic not studied well before. It then compares the compression performance of the modified JPEG with JPEG XR, the latest block-based image coding standard. We first show that the bulk of inter/intra-block redundancy, caused due to the use of the block-based approach by JPEG, can be captured by applying efficient prediction coding. We propose the following modifications to JAC to take advantages of our prediction approach. 1) We code a totally different DC difference. 2) JAC tests a DCT coefficient by considering its bits in the increasing order of significance for coding the most significant bit position. It causes plenty of redundancy because JAC always begins with the zeroth bit. We modify this coding order and propose alternations to the JPEG coding procedures. 3) We predict the sign of significant DCT coefficients, a problem is not addressed from the perspective of the JPEG decoder before. 4) We reduce the number of binary tests that JAC codes to mark end-of-block. We provide experimental results for two sets of eight-bit gray images. The first set consists of nine classical test images mostly of size 512 × 512 pixels. The second set consists of 13 images of size 2000 × 3000 pixels or more. Our modifications to JAC obtain extra-ordinary amount of code reduction without adding any kind of losses. More specifically, when we quantize the images using the default quantizers, our modifications reduce the total JAC code size of the images of these two sets by about 8.9 and 10.6%, and the JPEG Huffman code size by about 16.3 and 23.4%, respectively, on the average. Gains are even higher for coarsely quantized images. Finally, we compare the modified JAC with two settings of JPEG XR, one with no block overlapping and the other with the default transform (we denote them by JXR0 and JXR1, respectively). Our results show that for the finest quality rate image coding, the modified JAC compresses the large set images by about 5.8% more than JXR1 and by 6.7% more than JXR0, on the average. We provide some rate-distortion plots on lossy coding, which show that the modified JAC distinctly outperforms JXR0, but JXR1 beats us by about a similar margin.

This article presents a novel method for exploiting inter/intra-block redundancies for JPEG image coding. It first expands the given image by duplicating certain rows and columns so that if f is a 8 by 8 pixel block and g and h are blocks to its immediate left and above, resp., adjacent pixels at the common boundary of f and g and at the boundary of f with h in the expanded image match. We show that the first column (row) DCT coefficients of f can be predicted without incurring any loss from the remaining DCT coefficients of f and from the DCT coefficients of g (h), assuming that the DCT is reversible. Our experiment shows that on average, we can save about 14.6% of JPEG Huffman code bits just by not coding the first row/column DCT coefficients.

We explore predictive coding for the JPEG baseline sequential algorithm in this article. Our objective is to reduce inter-block redundancy of discrete cosine transform (DCT) blocks. We first present an implementation of image interpolation approach and develop a method for predicting ac coefficients of a block in terms of sum of pixels (or dc coefficients) of some surrounding patches. If we use 2-D quadratic polynomials for interpolation over 24$\times$24 pixel area, our method derives the same equations, which JPEG developed for reducing blocking artifacts. Next, we show that nonpolynomial functions such as$\arctan$perform better for ac prediction. We develop additional prediction equations considering different configurations of the interpolation area. Finally, we present performance results, which show that for images compressed at the default quality factor of 75, our equations reduce the ac energy of DCT blocks by about 22% and the final code bit size by about 5.5% over the JPEG sequential algorithm. At the quality factor of 90, the code size reduction is 10.8%. We also present an adaptive dc coding method by considering the prediction algorithm of JPEG-LS. It reduces the average JPEG dc residual by over 20% and the dc code bits by 7.75%.

Yamatani and Saito recently published an interesting method for predicting discrete cosine transform (DCT) coefficients of an image block, which uses partial derivatives of the image at the block boundary points. It estimates partial derivatives the same way for all four side boundary points. In this correspondence, we improve their estimation method for the left and top side boundary points by observing that the decoder can use 1-D DCT of the rightmost column of pixels of the block on the left side and bottom row pixels of the block on the top side instead of using just the DC of these two blocks. It led us to revise their prediction equations. Experimental results show that the cumulative reduction in the size of the first five AC coefficients obtained using their equations is 15.1%, and the same using our equations is 24.6%.

The JPEG baseline algorithm follows a block-based coding approach and therefore, it does not explore source redundancy at the sub-block level. This note explores correlation between adjacent rows (or columns) at the block boundaries for predicting DCT coefficients of the first row/column of DCT blocks. Experimental results show that our prediction method reduces the average JPEG DC residual by about 75% for images compressed at the default quality level. The same for AC01/10 coefficients is about 30%. It reduces the final code bits by about 4.55% of the total image code for grey images. Our method can be implemented as a part of the JPEG codec without requiring any changes to its control structure or to its code stream syntax.

In the basic 3-layer MRC model for compound document image coding, image pixels are separated into foreground and background layers. Pixels placed in the FG (BG) layer are called holes in the complementary layer and they can be assigned (filled) any values. This article proposes an optimal algorithm for hole filling. Our algorithm first divides the input into blocks to reduce complexity of the mask layer and then minimizes the sum of squares of Haar transform AC coefficients, which we show to be also equal to the square of DCT AC coefficients of the block. Experiments show that our method reduces the average energy by 30% more for the FG layer and by 20% more for BG layer blocks.

We present a lossless compression algorithm for coding image edges. First, we determine an optimal order of all edges by solving a traveling salesperson problem and then code efficiently the starting point of each edge with respect to one of the two end points of the previous edge in the order. Next, we code the remaining edge points using a modified chain difference coding algorithm. This algorithm reduces entropy of the source. Finally, we use LZW for entropy coding of the output. We provide experimental results to compare the coding rate of our algorithm for some natural images with arithmetic coding of chain difference code and JBIG.

This paper presents a Sequitur, which is a powerful realization of the grammar-based text compression approach. First, it derives a context-free grammar, which generates the given input as its only language. Then it represents the grammar as a single sequence of symbols, where a symbol represents either a rule head or an alphabet, and finally it uses arithmetic coder to code the sequence. Sequitur encodes each symbol individually. A modified approach is to code a rule symbol in the context of the last alphabet of the preceding rule symbol. Thereby, the partial matching (PM) approach is followed to realize code reduction. The crux of this approach is to maintain multiple dictionaries, each containing rules that begin with the same alphabet.

While conducting experiments with JPEG binary arithmetic coding, we noticed that if a natural photographic image is rotated by 90/spl deg/ and then coded, the DC code size is reduced in general. This led us to investigate the discrete cosine transform and statistical models of JPEG arithmetic coder, and formulate two modifications to DC coefficient coding. We propose that the DC of a block should be predicted from the block just above. This modification reduces the DC code size further by about 9% on average. This change is more important for arithmetic coding than Huffman DC coding. We also propose a change in the binary decision coding order specified by the DC statistical model; it produces only a minor reduction in the code size.

It is a well-observed characteristic that, when a discrete cosine transform block is traversed in the zigzag order, ac coefficients generally decrease in size and the runs of zero coefficients increase in length. This paper presents a minor modification to the Huffman coding of the JPEG baseline compression algorithm to exploit this characteristic. During the run-length coding, instead of pairing a nonzero ac coefficient with the run-length of the preceding zero coefficients, our encoder pairs it with the run-length of subsequent zeros. This small change makes it possible for our codec to code a pair using a separate Huffman code table optimized for the position of the nonzero coefficient denoted by the pair. These position-dependent code tables can be encoded efficiently without incurring a sizable overhead. Experimental results show that our encoder produces a further reduction in the ac coefficient Huffman code size by about 10%-15%.

It is a well observed characteristic that when a DCT block is traversed in the zigzag order, the AC coefficients generally decrease in size and the run-length of zero coefficients increase in number. This article presents a minor modification to the Huffman coding of the JPEG baseline compression algorithm to exploit this redundancy. For this purpose, DCT blocks are divided into bands so that each band can be coded using a separate code table. Three implementations are presented, which all move the end-of-block marker up in the middle of DCT block and use it to indicate the band boundaries. Experimental results are presented to compare reduction in the code size obtained by our methods with the JPEG sequential-mode Huffman coding and arithmetic coding methods. The average code reduction to the total image code size of one of our methods is 4%. Our methods can also be used for progressive image transmission and hence, experimental results are also given to compare them with two-, three-, and four-band implementations of the JPEG spectral selection method.

Summary form only given. It is a well-known observation that when a DCT block is traversed in a zig-zag order, the AC coefficients generally decrease in size and the run-length of zero coefficients increase in number. Therefore, use of a single AC Huffman code table in the JPEG baseline algorithm leads to sub-optimal coding, and it is desirable to use multiple code tables, one for each DCT coefficient position, if necessary. It creates a problem, because a nonzero coefficient, X, and the run-length, Z, of zero coefficients that precede X, are coded as one element (Z,X), and therefore, the decoder may not know which table to use to decode the next X. To solve this problem, we made a minor modification to the JPEG Huffman coding algorithm. To evaluate reduction in the code size using our method, we compressed the luminancec component of ten well-known test images at default quality level and computed AC Huffman code size.

Summary form only given. In a DCT block of a compressed image, the density of non-zero AC coefficients and their size decrease as the block is scanned in the zigzag order. This paper presents a minor modification to the Huffman coding phase of the JPEG baseline algorithm to exploit this redundancy for further compression. Our encoder divides each block into two roughly equal halves (bands) and codes each band using a separate code table. It moves the EOB (end-of-block) marker to the middle of the sequence of non-zero AC coefficients and then replaces it by one of two split markers, whose selection depends on whether the number of non-zero AC coefficients is even or odd. No marker is needed at the end of a block. The major difference between this approach and the spectral selection method of the JPEG progressive mode is that the band boundary is flexible in our approach (i.e., it can vary from block to block).

Although it is established that the distribution of the discrete cosine transform coefficients can be modeled, it is not known how this knowledge can best be applied to improve the JPEG compression algorithms. We studied this problem by making modifications to both the JPEG baseline encoder and decoder separately. Experimental results show that modifications to the decoder alone do not reduce any compression losses. However, if the encoder is also modified, the losses can be reduced, but only marginally.

A heuristic is proposed by Minami and Zakhor (see IEEE Trans. Circuits Syst. Video Technol., vol.5, p.74-82, 1995) to solve an optimization problem on reduction of blocking effects seen in low bit-rate coded images. This paper presents a novel solution to the same problem. Not only does it compute the global minimum, but its computational complexity is significantly smaller as well. The solution is stated in the form of prediction equations for computation of certain discrete cosine transform coefficients-an approach adapted by JPEG for its block-smoothing method. Experimental results show that our solution outperforms the JPEG's method.

The problem of blocking distortion reduction for images compressed using the JPEG baseline algorithms is well-known. It is because of this that the JPEG algorithm is not very effective for low-bit rate image coding applications. Over the last decade, researchers have proposed several approaches to reduce the effects of blocking artifacts, but there has been no study on the performance of the different approaches. The main problem is that no suitable metric has been established to measure the visibility of image distortions such as blockiness of block boundaries, blurriness in originally sharp edges and shifts in textured regions. Note that the mean-square-error (MSE) metric is not suitable for this purpose. In this article, first we outline the discrete cosine transform (DCT) prediction approach for the blocking artifacts reduction problem, and we summarize four different implementations of this approach. Next, we define a number of new metrics by considering various types of distortions resulting from the use of a block-based coding technique, and finally we present results of experiments that we have conducted to compare the performance of the four implementations. The reasons for choosing the prediction approach are that it is used by the JPEG's block smoothing algorithm, that it can be implemented easily in hardware, and that it can be used for real-time applications such as the browsing of images over a network.

Summary form only given. In JPEG baseline compression algorithm, the quantization loss to DCT coefficients can be reduced, if we make use of the observation that the distributions of the DCT coefficients peak at zero and decrease exponentially. It means that the mid-point of a quantization interval, say m, used by the JPEG decoder to restore all coefficients falling within the interval, may be replaced by another point, say y, closer to zero but within the interval. If we model the distributions by /spl lambda/e/sup -/spl lambda/|x|/, where /spl lambda/>0 is a constant, derivable from some statistical parameters such as mean or variance, and we assume that the adjustment q=|m-y| should be chosen so that the sum of the loss to all coefficients falling within a quantization interval is zero for each interval, we can derive q=Q(e/sup /spl lambda/(Q-1)/+(Q-2)/2)/2e/sup /spl lambda/(Q-1)/-1)-1//spl lambda/ where Q is the quantizer step size. To test usefulness of the above idea, we implemented both approaches: (1) JPEG encoder computes /spl lambda/ for each DCT distribution and passes it as part of coded data to the decoder, and (2) JPEG decoder computes /spl lambda/ from the quantized DCT coefficient incrementally as it decodes its input. Through experiments, we found that none of these approaches resulted in much improvements, but found a better approach (OUR) which does not require any modeling of DCT. It uses /spl Sigma/(|m-y|*C)//spl Sigma/C to compute adjustments, where C is the number of coefficients falling within an interval, and the /spl Sigma/ is taken over all intervals not-containing the zero DCT. We also implemented the formulation developed by Ahumada et. al (see SID Digest, 1994) to compare it with the results of OUR approach. The comparison is shown in terms of the % reduction in the RMSE of the images.

In this paper, we derive a new set of prediction equations for the block smoothing method of JPEG for reduction of blocking artifacts. We also devise some simple metrics to measure the effects of edging and ringing artifacts. Experiments show that at the bit rate of 0.3 b/p or less, images reconstructed using the proposed equations have significantly fewer number of artifacts compared to the images reproduced using the original set of equations.

Deals with the Huffman encoding phase of two well-known compression encoders, one that of the baseline algorithm proposed by JPEG for the compression of still images, and the other that of the H.261 based video encoder. We identify two types of minor redundancies in the input to the encoding phase, and present alternative Huffman code tables. Simulation results on still picture compressions indicate that the proposed redundancy reduction leads to an improvement of the order of 3.35% in the size of the image compressed at 75% quality level, and 5.3% when compressed at the 50% quality level, on the average.>

The article presents new tables for Huffman encoding of still images. Experimental results indicate that tables lead to an improvement of the order of 3.35% in the size of images compressed at 75% quality level and 5.3% compressed at the 50% quality level on the average.

Elegant implementation of modulo adders are presented. A design suitable for small moduli is given first, and then, by using the divide and conquer approach, a design for large moduli is derived. The designs are such that modulo subtraction can also be performed on the same hardware. The designs are suitable for high-speed digital parallel processing. The propagation delay of a modulo-64 adder realized using this design is 12 ns.>

The time complexity of a distributed algorithm [5] for all-pair shortest path problem is improved by a factor 0(n) by pipelining instructions. Its implementation using VLSI technology is proposed and area complexity is computed.