Spie Press BookProgressive Image Transmission: The Role of Rationality, Cooperation, and Justice
|Format||Member Price||Non-Member Price|
The authors present a sound, practical approach to information prioritization in progressive image transmission. The method, suitable for a variety of imaging applications from consumer products to the defense, publishing, science, and law enforcement industries, first states some general principles that the solution must obey and then derives the solution that satisfies exactly those principles. The text is intended for graduate students as well as engineers and research scientists in the field of image coding.
- Chapter 1: Rationality in Progressive Transmission
- 1.1 Introduction
- 1.2 Basic elements of the selection problem
- 1.3 Basic axioms for avoiding forms of behavioral inconsistency
- 1.4 Progressive transmission utility functions
- 1.4.1 Rate control procedure
- Chapter 2: Coder Evaluation Procedure
- 2.1 Introduction
- 2.2 Compound gain: A computational tool for predicting visual distinctness
- 2.3 Comparison between PSNR and CG
- 2.3.1 Images
- 2.3.2 Psychophysical target distinctness
- 2.3.3 Evaluation function
- 2.3.4 Experiment 1
- 2.3.5 Experiment 2
- 2.3.6 Statistical accuracy
- 2.4 Objective coder selection procedure
- 2.4.1 An example
- 2.5 Assessment of risk attitudes in rational transmission
- 2.5.1 Objective evaluation
- 2.5.2 Subjective evaluation
- Chapter 3: Visual Distinctness of Prioritized Data
- 3.1 Introduction
- 3.2 Prioritization by distortion measures and by human observers
- 3.2.1 Distortion measures for prioritization protocols
- 3.2.2 Psychophysical experiments
- 3.3 Results and discussion
- 3.3.1 Experiment 1
- 3.3.2 Experiment 2
- 3.3.3 Experiment 3
- 3.3.4 Experiment 4
- Chapter 4: Integration of Rationality and Cooperation
- 4.1 Introduction
- 4.2 Cooperative decision for bit allocation
- 4.3 Self-control of risk aversion attitude in progressive transmission
- 4.4 Integration of rationality/cooperation in unsteady-state transmission
- 4.4.1 Self-rewarding risk attitude
- 4.4.2 Self-rewarding attitude integrates cooperative action with rationality
- 4.5 Experimental results
- 4.5.1 Subjective coder evaluation
- 126.96.36.199 Experiment 1
- 188.8.131.52 Experiment 2
- 184.108.40.206 Experiment 3
- 4.5.2 Objective coder evaluation
- 220.127.116.11 Experiment 1
- 18.104.22.168 Experiment 2
- 22.214.171.124 Experiment 3
- 126.96.36.199 Experiment 4
- Chapter 5: Conflict and Cooperation at Very Low Bit Rates
- 5.1 Introduction
- 5.2 Acceleration of benefit gain by increasing risk attitude tolerance
- 5.3 A coalitional game for controlling a quantizer's risk tolerance
- 5.4 A family of solutions for the coalitional game
- 5.5 Assessment of weight functions
- 5.6 Experimental results
- 5.6.1 Subjective coder evaluation
- 188.8.131.52 Experiment 1
- 184.108.40.206 Experiment 2
- 220.127.116.11 Experiment 3
- 5.6.2 Objective coder evaluation
- 5.7 The self-rewarding solution and the dissatisfaction solution
- 5.7.1 Basic properties of the dissatisfaction solution
- 5.7.2 Relationship between the self-rewarding solution and the dissatisfaction solution
- Chapter 6: Justice in Rational Transmission
- 6.1 Introduction
- 6.2 Just quantizer formation
- 6.3 A priori importance of an SOT
- 6.3.1 SOT-restricted games: Cooperation and communication among wavelet coefficients
- 6.3.2 Zerotree solution for SOT-restricted games
- 6.4 Experimental results
- 6.4.1 Subjective coder evaluation
- 18.104.22.168 Experiment 1
- 22.214.171.124 Experiment 2
- 6.4.2 Objective coder evaluation
- 6.5 Just transmission
- Epilogue: Rationality, Cooperation, and Justice
- Appendix A: Fundamentals in Embedded Zerotree Wavelet Coding
- A.1 Introduction
- A.2 Progressive transmission
- A.3 Wavelet transform; decomposition into subbands
- A.4 Compression algorithm based on "zerotrees"
- A.4.1 SPIHT
- A.4.1.1 Examples
- Appendix B: REWIC Algorithm
- B.1 Algorithms for encoding/decoding an image in REWIC format
- B.2 Algorithms for encoding/decoding an image in RECON format
- Appendix C: Information Theoretic Measure
- C.1 Introduction
- C.2 Information conservation constraint
- C.2.1 Selective information gain
- C.2.2 Properties of the selective information gain
- C.3 Significance conservation constraint
- C.3.1 Compound information gain
- C.3.2 Properties of the CG
- Appendix D: Best Achievable Compression Ratio
- D.1 Introduction
- D.2 The best achievable compression ratio
- D.3 Effects of lossy compression at the best achievable compression ratio
- D.3.1 Results
Way back when we began to write this book, our objectives were clear. We aspired to develop a sound, practical theory for organizing the quantizer-dependent quality of encoding in progressive image transmission. The basic elements of this theory would be a novel scheme for information prioritization, the mechanism of bit rate allocation among competing quantizers, and the strategy for coder performance evaluation.
In the coding community the standard approach is often to use the peak signal to noise ratio (PSNR) for coder evaluation, the largest reduction in some square error for information priorization, and a theory of (minimal) distortion as a function of rate for bit allocation. Thus, any coding scheme that does not attempt to minimize some square-error cannot be expected to prove its worth with a curve of PSNR versus bit rate, which may be a constraint on the formulation of new coding schemes capable of making an intelligent use of visual information. This may be justified assuming the correctness of the PSNR, but what are the actual properties of the PSNR? For example, does it take into account the effectiveness of the information, so discriminating relevant structures from unwanted detail and noise? Does it examine whether the properties of the original image at significant points are equal to the properties of the decoded output at corresponding locations? The point is that whereas we have no evident affirmative answer to these and other questions, the PSNR does not appear capable of predicting visual distinctness from digital imagery as perceived by human observers.
Regarding the issue of information prioritization, standard schemes prioritize the code bits often according to their reduction in distortion, and a major objective in this context is to select the most important information--which yields the largest distortion reduction--to be transmitted first, where the distortion is usually a squared-error metric. Since the quality of the reconstructions at different bit rates strongly depends on the visual distinctness of the perceived data, the information selected to be transmitted first by any prioritization scheme at each truncation time should achieve the largest visual distinctness over still-to-be-transmitted data. The natural question is whether a squared-error metric is capable to rank order visual information with respect to the visual distinctness as measured by humans, and thus, the largest squared-error reduction can be used to prioritize, with reliability, the most important information according to their distinctness.
With respect to the issue of distribution of bits, in the standard approach of Rate-Distortion Theory (the idea of rate distortion was introduced in 1948 by Shannon) a bit rate allocation problem among competing quantizers (e.g., spatial regions) is optimally solved for a given bit budget if the marginal change in distortion is the same for all regions. Again, the squared-error metric is the most popular distortion measure used for continuous alphabets. Its advantages are its simplicity and its relationship to least squares prediction. To our understanding, the problem with the standard approach of rate (square-error) distortion is that there exist some questions yet to be answered concerning the properties that obey its solution for bit allocation among competing regions. For example, if we view the regions as citizens of a society, does this solution respect the views of the regions (citizens)? Is this solution blind to the kind of objects that the regions contain? Could it be interpreted as a fair aggregation of individual interests? Does the solution of the distribution problem change by virtue of a change in the scale of the benefits regions receive from their respective allocations?
In this book we propose that a different approach to solve the problems of evaluation, prioritization, and distribution can be to first state some general principles that the solution of the problem in each case must obey, and then derive the solution that satisfies exactly the principles (see the Epilogue of this book). The axioms may, of course, be incompatible. It is not rare that one would like to impose more axioms that are jointly compatible. It may also happen that the axiomatic solution resulting from a list of axioms that all seem appealing is found to behave unsatisfactorily in some significant example. To overcome this problem, one must formalize the example and state an additional axiom that specifies how the solution should behave in this situation, and finally determine the greatest subset of axioms from the original list that are compatible with the new axiom. Of course, compatibility may hold for several distinct such subsets. In any case, the critical difference with respect to the approaches discussed above is that we will be able to predict exactly the behavior of the axiomatic solution according to its principles. For example, the principles of rationality avoid certain forms of behavioral inconsistency in situations in which choices are to be made among available quantizers for their prioritization; the principles of cooperation among quantizers may be needed to increase their risk tolerance in variable-resolution compression, and the principle of justice provides conditions for fair quantizer formation.
In a rational system for transmission, a discrete wavelet transform provides a representation of the original image. A tree structure, called a spatial orientation tree, naturally defines the spatial relationship in the pyramid that results from the transformation. Each node of the tree corresponds to a pixel, and its direct descendants (offspring) correspond to the pixels of the same spatial orientation in the next finer level of the pyramid. Transform coefficients in a spatial orientation tree correspond to a particular region of the original image, and thus, each spatial orientation tree is associated with one spatial region. Individual trees may be grouped together to form a reduced number of quantizers that convey structural information about the picture to the rational transmission. A "just" quantizer formation will give no tree a cause for "reasonable regret" in rational progressive transmission (Chapter 6). That is, they are all able to achieve the same overall success. The basic assumption is that justice requires compensating individual spatial orientation trees for aspects of their prioritization for which they are not responsible and which hamper their achievement of whatever is valuable in their own transmission. Differences for which they are responsible may be ruled by rationality (Chapter 1). A simple condition to perform a just quantizer formation can be the equality of the a priori importance of the spatial orientation trees that are grouped together in one quantizer, from which we understand the key role of the a priori importance of a tree in the development of a theory for just quantizer formation.
A prioritization protocol whereby the ordering of importance is determined within a rational approach, chooses at each truncation time among alternative quantizers for further transmission in such a way as to avoid certain forms of behavioral inconsistency (Chapter 1). The system may exhibit either a risk-seeking posture with respect to "gambles" on quantizer-dependent quality of encoding or risk-averse behavior.
By changing its risk attitude within a rational approach that avoids certain forms of behavioral inconsistency, a quantifier may modify the gain in benefit that results from a particular bit stream candidate to be transmitted at a truncation time. At medium and high bit rates, quantizers exhibit only low risk tolerance since they are aware that the next truncation time might be the last one (Chapter 4). Anyway, since at extremely low bit rates the target bit rate may be far away, quantizers are able to exhibit higher risk tolerance, and as a consequence, they will have a greater possibility of accelerating their benefit gain. The cooperation among subsets of the quantizers may be needed to increase the risk tolerance at very low bit rates within a rational approach and still prioritize first the more relevant pieces of information at each truncation time (Chapter 5): The members of any coalition of quantizers can then negotiate a feasible change in the risk attitudes of the quantizers of the coalition that would benefit them all. The final risk tolerance of different quantizers comes from the balance of power among the coalitions of quantizers; and the prioritization protocol chooses to transmit, at each truncation time, a bit stream for the quantizer that receives the highest payment (per coding bit) in a coalitional game that minimizes the dissatisfaction of coalitions.
Experimental results should illustrate the comparative performance of the rational system against the state of the art in progressive transmission. Chapter 2 shows the principles of a visual distinctness measure that can be used to evaluate image compression methods. The book ends with an epilogue that summarizes the key results and conclusions plus four appendixes containing basic background material.
All software (with documentation) developed in the book may be accessed on the Internet site http://decsai.ugr.es/cvg/REWIC or by anonymous ftp to decsai.ugr.es with the path pub/cvg/software. All material is made available to other researchers for academic use only. The programs were not optimized to a commercial application level.
This is intended to be a simple and accessible book on the role of rationality, cooperation, and justice in progressive image transmission. From the above discussion, it is clear that we were drawn to the problem of progressive transmission from backgrounds in theories of distributive justice and game theory, because of the difficulty of capturing the concept of relative information for predicting visual distinctness from 2D digital images. We hope that you find a few key ideas and techniques that provide intuition toward new questions, and also that our answers to problems of evaluation, prioritization, and distribution allow extensive interpretation. For example, the information theoretic measure for predicting visual distinctness and the expected increase in utility for information prioritization are related (Chapter 3). We all know the feeling that follows when one investigates a problem, goes through a certain amount of analysis and finally investigates the answer, only to find that the entire problem is illuminated not by the analysis, but by the inspection of the answer.
Thanks are due to Dr. Alexander Toet (TNO Human Factors Research Institute in Soesterberg) for his contribution to Chapters 2 and 3.
SPIE Press (in the person of Margaret Thayer) provided the much needed focus and guidance that are required in the completion of a text. We are deeply indebted to the referees for suggesting several good ways to improve the quality of the initial manuscript.
We are grateful for the permission to reproduce figures and text of some of our papers, to Elsevier Science Ltd., IEEE Computer Society, and SPIE--The International Society for Optical Engineering.
Thanks are due to the TNO Human Factors Research Institute for providing us with the image data, search time, and cumulative detection probabilities from search experiments made during the DISSTAF field test.
Some of the results in the different chapters were previously published in Refs. - and .
This research was sponsored by the Spanish Board for Science and Technology (CICYT) under grant TIC2003-00473.
Finally, the first author would like to honestly say that his admiration for the other two authors has never stopped growing. The third author would like to offer his deepest and most heartfelt thanks to his wife for her love, understanding, support and patience.Jose A. Garcia