Skip to main content
main-content

Über dieses Buch

Recursive Block Coding, a new image data compression technique that has its roots in noncausal models for 1d and 2d signals, is the subject of this book. The underlying theory provides a multitude of compression algorithms that encompass two course coding, quad tree coding, hybrid coding and so on. Since the noncausal models provide a fundamentally different image representation, they lead to new approaches to many existing algorithms, including useful approaches for asymmetric, progressive, and adaptive coding techniques. On the theoretical front, the basic result shows that a random field (an ensemble of images) can be coded block by block such that the interblock redundancy can be completely removed while the individual blocks are transform coded. On the practical side, the artifact of tiling, a block boundary effect, present in conventional block by block transform coding techniques has been greatly suppressed. This book contains not only a theoretical discussion of the algorithms but also exhaustive simulation and suggested methodologies for ensemble design techniques. Each of the resulting algorithms has been applied to twelve images over a wide range of image data rates and the results are reported using subjective descriptions, photographs, mathematical MSE values, and h-plots, a recently proposed graphical representation showing a high level of agreement with image quality as judged subjectively.

Inhaltsverzeichnis

Frontmatter

1. Introduction

Abstract
Digital image data arises for one of three reasons: the image source is inherently digital; we desire to use digital techniques to process images which may actually be analog; or we desire, or have no choice but to use digital transmission networks or digital storage media. Images arise from broadcast TV, videoconference, satellite, medical, and seismic applications, among others, but whatever their origin they invariably contain an enormous amount of data after digitization. This is achieved by sampling the image, or each image in a sequence, in both the horizontal and vertical directions and then each resulting analog sample is digitized using an analog-to-digital converter (ADC) with equally spaced output levels to form a digital picture element, or pixel. This raw digital representation is called pulse code modulation (PCM) and typical image channels are quantized using 8 bits/pixel.
Paul Michael Farrelle

2. RBC—The Theory behind the Algorithms

Abstract
RBC is based on representing digital images by discrete models and then using these models to derive algorithms for image data compression. In this chapter we will introduce the models and their properties and describe the resulting generic RBC algorithms, in one and two dimensions. In later chapters we will provide variations on the basic theme by allowing for adaptation within the algorithm.
Paul Michael Farrelle

3. Bit Allocation and Quantization for Transform Coding

Abstract
The most important part of a transform coding scheme is undoubtedly the bit allocation and quantization. True, there are good and bad transforms, there is straight transform coding and there is RBC, but whichever choice you make for the overall algorithm it will only be as good as the quantization scheme allows. In other words, a good transform and bad quantizer may well perform worse than a bad transform with a very good quantizer—but what do we mean by good and bad?
Paul Michael Farrelle

4. Zonal Coding

Abstract
Zonal coding is the simplest transform coding scheme where each block is coded in the same way without any reference to local image content. That is, we measure statistics for the complete image and then use these to design a bit allocation and set of quantizers to code every block of the image. The bit allocation process, as discussed in chapter three, naturally leads to a zone of active coefficients and this leads to the term zonal coding. However, some researchers choose the zone first and then, using only the coefficient variances within this zone, make the bit allocation. This is a sub-optimal approach and instead we will let the bit allocation determine the zone directly.
Paul Michael Farrelle

5. Adaptive Coding Based on Activity Classes

Abstract
Since images are not stationary a number of techniques have been used to adapt the coding scheme to the local image content. As the image changes, the most complex schemes adapt the transform [68], while simpler schemes modify the bit allocation [69], or leave the allocation unchanged but scale the quantizers [70] from block to block. Some adaptive schemes lead to a variable rate code, where the rate increases for more complex images, while others go to some length to ensure that the rate remains the same for all images. Since most communication systems require that the data be transmitted at a constant rate, the transmission time for a still image coded using a variable rate scheme will vary according to the image content which may be quite acceptable. However this is not possible with broadcast TV and videoconferencing where the data is generated and must be reconstructed by the receiver at a constant rate and an elaborate buffering scheme must be employed to smooth out the non-uniform data generation rate for subsequent fixed rate transmission. In such cases it may be more attractive to use a fixed rate scheme which can be made quite complex before it becomes as involved as a variable rate coder and accompanying buffer and controller which together can meet the fixed rate constraint.
Paul Michael Farrelle

6. Adaptive Coding Based on Quad Tree Segmentation

Abstract
In the last chapter we saw one adaptive coding method which classifies each block and then, depending on which class the block belongs to, uses an appropriate set of quantizers. In this and the following chapter we will discuss a second adaptation technique which varies the block size, rather than the quantizers, according to image activity. In this way it will be possible to ensure that the prediction is only made over regions which are relatively smooth and so avoid the large prediction errors which can occur when a block contains a sharp edge. This will then provide a residual which will be a much better candidate for a stationary source. In section 6.2 we will discuss adaptive segmentation in general, and then in section 6.3 we will describe the specific quad tree approach which leads to unequal block sizes. We will complete the segmentation topic in section 6.4 with ways to minimize the overhead incurred by the adaptivity, and in section 6.5 we will discuss modifications to the reconstruction made possible because of the unequal block sizes. We will then turn, in section 6.6, to the second half of the algorithm—coding the residual, and conclude with some results in section 6.7 and conclusions in section 6.8.
Paul Michael Farrelle

7. QVQ—Vector Quantization of the Quad Tree Residual

Abstract
In the last chapter we developed an adaptive RBC algorithm using unequal block sizes and used the DCT to code the resulting residual image. We will now consider a simple variation of this algorithm which uses the same quad tree prediction but replaces the transform coder with a vector quantizer (VQ). We shall use the notation VQ to refer to both the encoding method: vector quantization and also the encoder: a vector quantizer, where the actual meaning will be evident from the context.
Paul Michael Farrelle

8. Conclusions

Abstract
In this final chapter we will first summarize the new results, both theoretical and practical, described in detail in this book. We will then draw some overall practical coding conclusions illustrated by examples in the figures 8.1.1, 8.1.2, and 8.1.3. Finally we will indicate those areas where future work is still to be done.
Paul Michael Farrelle

Backmatter

Weitere Informationen