Image Coding by Adaptive Golomb Codes and the Information of Adjacent Blocks
Date Issued
2010
Date
2010
Author(s)
Wei, Wei-Yi
Abstract
With the advent of the internet and the digital camera, the analog photo has been replaced by the digital image, which plays an important role in our daily life nowadays. However, the uncompressed digital images require a large amount of memory storage for recording, so they waste a large amount of memory and are not suitable for transmission in the internet. Therefore, several image compression standards and algorithms, such as the best-known JPEG still image compression standard and the latest JPEG2000 still image compression standard, have been proposed to solve these problems. Although these image compression standards can provide acceptable image quality and compression ratio, the image quality requirements of the customers become higher and higher, and the conventional image compression standards may not be able to fulfill the customer requirements.
In the latest and most popular video compression standard H.264/AVC, the intra prediction coding algorithm is exploited to increase the coding performance. The intra prediction takes advantage of the correlation between the previously encoded/decoded blocks and the current block to be coded to predict the texture of the current block. Some researchers have proposed the intra-prediction-based JPEG image coding system to improve the coding performance, but the frequency components of the image will be changed after intra prediction and the JPEG quantization table may not be suitable any more. In addition, the intra prediction requires some side information to record the intra prediction modes, so the coding performance may be deteriorated. In this thesis, we proposed new intra prediction approach to solve these problems.
On the other hand, JPEG adopts the zigzag scanning to convert the 2-D DCT matrix into the 1-D vector, then performs zero-run-length coding to reduce the number of data symbols to be coded. If zigzag scanning can place most of the nonzero coefficients in the front end, the performance of zero-run-length coding can be highly improved. However, the conventional zigzag scanning does not take the real distribution of the quantized coefficients into consideration, so we proposed the adaptive coefficient scanning algorithm, which determines the scanning orders based on the neighboring encoded/decoded blocks.
In conventional JPEG image compression standard, we usually adopt the default Huffman table to encode the processed digital image data and to reduce the coding redundancy. Although the default Huffman table can achieve acceptable coding performance for most digital images, it does not assign the optimal codeword table according to the real distribution of every certain image, and this will result into limited coding efficiency. Besides, JPEG can use the dynamic Huffman algorithm to find the optimal codeword table for a certain image, but we must include the codeword table in the bitstream. If the data size of the codeword table is too large, the purpose of compression may be violated. In this thesis, we find that the digital image processed by JPEG can be well modeled by the geometric distribution. When the data is geometrically distributed, we can use the Golomb coding algorithm to achieve optimal coding efficiency. On the other hand, the Golomb coding algorithm can solve the problem with the dynamic Huffman coding algorithm. In Golomb coding, the data can be converted into the binary bitstream by a single tunable parameter, which is the only side information that must be recorded. On the other hand, the look-up-table operation, which is required in the Huffman algorithm, can be ignored, so a large amount of computation can be saved.
Although the Golomb codes outperform the conventional Huffman codes in many aspects, the coding efficiency of the Golomb codes is optimal only when the data is exactly geometrically distributed. Unfortunately, the geometric distribution can approximate the practical distribution of one natural digital image only, not exactly. Therefore, we proposed the adaptive Golomb coding algorithm by joint probability in this thesis. The adaptive Golomb coding can take advantage of the correlation between the neighboring data to adjust the tunable parameter of the Golomb codes, so higher coding efficiency can be achieved. The coding performance of JPEG can be highly improved by the proposed adaptive Golomb coding, which is revealed by our simulation results.
The practical data is usually composed of negative and non-negative integers, so we will map the negative symbols into the non-negative ones before applying Golomb codes. The common geometric distribution model for integers always assumes that the decay probabilities of the negative integers are the same as that of the non-negative integers, but this is not always true. Thus, we proposed the asymmetric two-sided geometric distribution model and the corresponding coding algorithm to improve the coding efficiency.
In statistics, the Pareto distribution is widely used, and the well-known “80-20 rule” is one of its special cases. In this thesis, we find that the probability parameter of the Pareto distribution is highly related to the number of leafs in each layer of the optimal coding tree, and we proposed a corresponding fast coding algorithm and applied it to improve the coding performance of JPEG.
Subjects
Image Coding
Zigzag Scan
Adaptive Coefficient Scanning Algorithm
Huffman Coding
Golomb Coding
Adaptive Golomb Coding
Intra Prediction
Advanced Image Coding
Geometric Distribution
Pareto Distribution
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-99-R97942024-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):a19e4ddd647d29fd9fbbb630aec8ddac