|
||||||||||||||||
|
Ph.D. ThesesResolution Scalable and Random Access Decodable Image Coding with Low Time Complexity
By Yushin Cho
Modern image compression methods such as JPEG 2000 are based on the wavelet transform. They provide not only higher compression performance, but also the capability to support various features, such as quality (SNR) scalability, resolution scalability, and region-of-interest encoding and decoding. Quality scalability is commonly achieved via bit-plane coding, which also helps to improve compression, since neighboring bits provide convenient and powerful contexts for entropy coding. However, on many important applications (e.g. digital camera), the images always need to have a pre-defined high quality, and any extra effort required for quality scalability is wasted.Furthermore, for compressing a very large size image source, a low time complexity is often the most desirable characteristic of an image coding algorithm. In this thesis, we consider fast coding methods that support resolution scalability and efficient decoding of a region of interest by random access to the codestream. A resolution scalable and random accessible image coding algorithm, PROGRES (Progressive Resolution Decompression), is designed based on predictive dynamic range coding of wavelet coefficients and without bit-plane coding. Avoiding bit-plane coding leads to considerable speed improvement without compromising coding efficiency. The dynamic range of a set of wavelet coefficients is represented as "dynamic range number", which gives the number of bits required to represent every magnitude of the coefficient in the set. Based on the assumption of decaying power spectral density, the dynamic ranges of children sets are smaller than that of parent set. We code the amount of this decrease in dynamic range number. In addition, since local neighborhood wavelet coefficients have similar statistics, the partitioned subsets can share the information of decrease in dynamic range. This procedure is hierarchically applied to each coefficient resolution by resolution. Because a decrease in dynamic range between some parent-child coefficients affects not just those children (direct descendants) but all their descendants also, the presented dynamic range coding method efficiently represents the hierarchy of dynamic ranges over a spatial orientation tree. The PROGRES algorithm is designed and implemented for both 2D and 3D image sources. Experiments show that our suggested coding model lessens the computational burden of bit-plane based image coding, both in encoding and decoding time. For faster random access of a target image block in a very large compressed bitstream, an intuitive idea is applied to generate efficient block indices. The idea is based on a popular problem solving strategy, a "search space reduction". Given a target block index, a conventional random access decoding method simply configures sequential links, so that an average of n/2 links should be followed to seek the target block out of n blocks in the image bitstream. The presented method applies the bi-section idea to narrow down the search space exponentially. This method has the worst case seek time complexity of $O(\log_2n)$, which is a great improvement over $O(n)$ of the standard linear seek method. The PROGRES algorithm combined with the fast random access decoding method is suitable for browsing a very large image bitstream. It can seek the requested part in the bitstream very quickly, and then decode them upto desired resolution at high speed. In related work, we introduce the concept of higher order zerotrees in modern wavelet-based coders and quantify their relative coding power. By analyzing two famous zerotree-based image coders, EZW and SPIHT, we are able to explain the superior coding efficiency of SPIHT through its ability to code higher order zerotrees than EZW. We are also able to calculate the bit savings of SPIHT compared to EZW within this framework.
|
||||||||||||||||
Research
