Robert M. Gray

In the current age of information technology, the issues of distributing and utilizing images efficiently and effectively are of substantial concern. Solutions to many of the problems arising from these issues are provided by techniques of image processing, among which segmentation and compression are topics of this book. Image segmentation is a process for dividing an image into its constituent parts. For block-based segmentation using statistical classification, an image is divided into blocks and a feature vector is formed for each block by grouping statistics of its pixel intensities. Conventional block-based segmentation algorithms classify each block separately, assuming independence of feature vectors. Image Segmentation and Compression Using Hidden Markov Models presents a new algorithm that models the statistical dependence among image blocks by two dimensional hidden Markov models (HMMs). Formulas for estimating the model according to the maximum likelihood criterion are derived from the EM algorithm. To segment an image, optimal classes are searched jointly for all the blocks by the maximum a posteriori (MAP) rule. The 2-D HMM is extended to multiresolution so that more context information is exploited in classification and fast progressive segmentation schemes can be formed naturally. The second issue addressed in the book is the design of joint compression and classification systems using the 2-D HMM and vector quantization. A classifier designed with the side goal of good compression often outperforms one aimed solely at classification because overfitting to training data is suppressed by vector quantization. Image Segmentation and Compression Using Hidden Markov Models is an essential reference source for researchers and engineers working in statistical signal processing or image processing, especially those who are interested in hidden Markov models. It is also of value to those working on statistical modeling.

In the current age of information technology, the issues of distributing and utilizing images efficiently and effectively are of substantial concern. Solutions to many of the problems arising from these issues are provided by techniques of image processing, among which segmentation and compression are topics of this book. Image segmentation is a process for dividing an image into its constituent parts. For block-based segmentation using statistical classification, an image is divided into blocks and a feature vector is formed for each block by grouping statistics of its pixel intensities. Conventional block-based segmentation algorithms classify each block separately, assuming independence of feature vectors. Image Segmentation and Compression Using Hidden Markov Models presents a new algorithm that models the statistical dependence among image blocks by two dimensional hidden Markov models (HMMs). Formulas for estimating the model according to the maximum likelihood criterion are derived from the EM algorithm. To segment an image, optimal classes are searched jointly for all the blocks by the maximum a posteriori (MAP) rule. The 2-D HMM is extended to multiresolution so that more context information is exploited in classification and fast progressive segmentation schemes can be formed naturally. The second issue addressed in the book is the design of joint compression and classification systems using the 2-D HMM and vector quantization. A classifier designed with the side goal of good compression often outperforms one aimed solely at classification because overfitting to training data is suppressed by vector quantization. Image Segmentation and Compression Using Hidden Markov Models is an essential reference source for researchers and engineers working in statistical signal processing or image processing, especially those who are interested in hidden Markov models. It is also of value to those working on statistical modeling.

Probability, Random Processes, and Ergodic Properties is for mathematically inclined information/communication theorists and people working in signal processing. It will also interest those working with random or stochastic processes, including mathematicians, statisticians, and economists. Highlights: Complete tour of book and guidelines for use given in Introduction, so readers can see at a glance the topics of interest. Structures mathematics for an engineering audience, with emphasis on engineering applications. New in the Second Edition: Much of the material has been rearranged and revised for pedagogical reasons. The original first chapter has been split in order to allow a more thorough treatment of basic probability before tackling random processes and dynamical systems. The final chapter has been broken into two pieces to provide separate emphasis on process metrics and the ergodic decomposition of affine functionals. Many classic inequalities are now incorporated into the text, along with proofs; and many citations have been added.

This book is an updated version of the information theory classic, first published in 1990. About one-third of the book is devoted to Shannon source and channel coding theorems; the remainder addresses sources, channels, and codes and on information and distortion measures and their properties. New in this edition:Expanded treatment of stationary or sliding-block codes and their relations to traditional block codesExpanded discussion of results from ergodic theory relevant to information theoryExpanded treatment of B-processes -- processes formed by stationary coding memoryless sourcesNew material on trading off information and distortion, including the Marton inequalityNew material on the properties of optimal and asymptotically optimal source codesNew material on the relationships of source coding and rate-constrained simulation or modeling of random processesSignificant material not covered in other information theory texts includes stationary/sliding-block codes, a geometric view of information theory provided by process distance measures, and general Shannon coding theorems for asymptotic mean stationary sources, which may be neither ergodic nor stationary, and d-bar continuous channels.

Stochastic Image Processing provides the first thorough treatment of Markov and hidden Markov random fields and their application to image processing. Although promoted as a promising approach for over thirty years, it has only been in the past few years that the theory and algorithms have developed to the point of providing useful solutions to old and new problems in image processing. Markov random fields are a multidimensional extension of Markov chains, but the generalization is complicated by the lack of a natural ordering of pixels in multidimensional spaces. Hidden Markov fields are a natural generalization of the hidden Markov models that have proved essential to the development of modern speech recognition, but again the multidimensional nature of the signals makes them inherently more complicated to handle. This added complexity contributed to the long time required for the development of successful methods and applications. This book collects together a variety of successful approaches to a complete and useful characterization of multidimensional Markov and hidden Markov models along with applications to image analysis. The book provides a survey and comparative development of an exciting and rapidly evolving field of multidimensional Markov and hidden Markov random fields with extensive references to the literature.

The Fourier transform is one of the most important mathematical tools in a wide variety of fields in science and engineering. In the abstract it can be viewed as the transformation of a signal in one domain (typically time or space) into another domain, the frequency domain. Applications of Fourier transforms, often called Fourier analysis or harmonic analysis, provide useful decompositions of signals into fundamental or "primitive" components, provide shortcuts to the computation of complicated sums and integrals, and often reveal hidden structure in data. Fourier analysis lies at the base of many theories of science and plays a fundamental role in practical engineering design. The origins of Fourier analysis in science can be found in Ptolemy's decomposing celestial orbits into cycles and epicycles and Pythagorus' de­ composing music into consonances. Its modern history began with the eighteenth century work of Bernoulli, Euler, and Gauss on what later came to be known as Fourier series. J. Fourier in his 1822 Theorie analytique de la Chaleur [16] (still available as a Dover reprint) was the first to claim that arbitrary periodic functions could be expanded in a trigonometric (later called a Fourier) series, a claim that was eventually shown to be incorrect, although not too far from the truth. It is an amusing historical sidelight that this work won a prize from the French Academy, in spite of serious concerns expressed by the judges (Laplace, Lagrange, and Legendre) re­ garding Fourier's lack of rigor.

Herb Caen, a popular columnist for the San Francisco Chronicle, recently quoted a Voice of America press release as saying that it was reorganizing in order to "eliminate duplication and redundancy. " This quote both states a goal of data compression and illustrates its common need: the removal of duplication (or redundancy) can provide a more efficient representation of data and the quoted phrase is itself a candidate for such surgery. Not only can the number of words in the quote be reduced without losing informa­ tion, but the statement would actually be enhanced by such compression since it will no longer exemplify the wrong that the policy is supposed to correct. Here compression can streamline the phrase and minimize the em­ barassment while improving the English style. Compression in general is intended to provide efficient representations of data while preserving the essential information contained in the data. This book is devoted to the theory and practice of signal compression, i. e. , data compression applied to signals such as speech, audio, images, and video signals (excluding other data types such as financial data or general­ purpose computer data). The emphasis is on the conversion of analog waveforms into efficient digital representations and on the compression of digital information into the fewest possible bits. Both operations should yield the highest possible reconstruction fidelity subject to constraints on the bit rate and implementation complexity.

Source coding theory has as its goal the characterization of the optimal performance achievable in idealized communication systems which must code an information source for transmission over a digital communication or storage channel for transmission to a user. The user must decode the information into a form that is a good approximation to the original. A code is optimal within some class if it achieves the best possible fidelity given whatever constraints are imposed on the code by the available channel. In theory, the primary constraint imposed on a code by the channel is its rate or resolution, the number of bits per second or per input symbol that it can transmit from sender to receiver. In the real world, complexity may be as important as rate. The origins and the basic form of much of the theory date from Shan­ non's classical development of noiseless source coding and source coding subject to a fidelity criterion (also called rate-distortion theory) [73] [74]. Shannon combined a probabilistic notion of information with limit theo­ rems from ergodic theory and a random coding technique to describe the optimal performance of systems with a constrained rate but with uncon­ strained complexity and delay. An alternative approach called asymptotic or high rate quantization theory based on different techniques and approx­ imations was introduced by Bennett at approximately the same time [4]. This approach constrained the delay but allowed the rate to grow large.

This book is an updated version of the information theory classic, first published in 1990. About one-third of the book is devoted to Shannon source and channel coding theorems; the remainder addresses sources, channels, and codes and on information and distortion measures and their properties. New in this edition:Expanded treatment of stationary or sliding-block codes and their relations to traditional block codesExpanded discussion of results from ergodic theory relevant to information theoryExpanded treatment of B-processes -- processes formed by stationary coding memoryless sourcesNew material on trading off information and distortion, including the Marton inequalityNew material on the properties of optimal and asymptotically optimal source codesNew material on the relationships of source coding and rate-constrained simulation or modeling of random processesSignificant material not covered in other information theory texts includes stationary/sliding-block codes, a geometric view of information theory provided by process distance measures, and general Shannon coding theorems for asymptotic mean stationary sources, which may be neither ergodic nor stationary, and d-bar continuous channels.

Linear prediction has long played an important role in speech processing, especially in the development during the late 1960s of the first low bit rate speech compression/coding systems. The approach, which eventually became known as linear predictive coding (LPC), coincidentally came to fruition at the right time to be adopted as the speech compression technique in the first successful realtime packet speech communication through the nascent ARPAnet in December 1974 — the ancestor of voice over the Internet Protocol (IP) and, more generally, of realtime signal processing through the Internet. This first part of a two part monograph on LPC and the IP provides a tutorial overview of linear prediction and its application to speech coding. A variety of viewpoints provides background and context for the second part, which comprises a technical and personal history of LPC, its use in the first packet speech demonstrations, and many related stories of the early applications of LPC and the prehistory of the Internet.

This book describes the essential tools and techniques of statistical signal processing. At every stage theoretical ideas are linked to specific applications in communications and signal processing using a range of carefully chosen examples. The book begins with a development of basic probability, random objects, expectation, and second order moment theory followed by a wide variety of examples of the most popular random process models and their basic uses and properties. Specific applications to the analysis of random signals and systems for communicating, estimating, detecting, modulating, and other processing of signals are interspersed throughout the book. Hundreds of homework problems are included and the book is ideal for graduate students of electrical engineering and applied mathematics. It is also a useful reference for researchers in signal processing and communications.

Probability, Random Processes, and Ergodic Properties is for mathematically inclined information/communication theorists and people working in signal processing. It will also interest those working with random or stochastic processes, including mathematicians, statisticians, and economists. Highlights: Complete tour of book and guidelines for use given in Introduction, so readers can see at a glance the topics of interest. Structures mathematics for an engineering audience, with emphasis on engineering applications. New in the Second Edition: Much of the material has been rearranged and revised for pedagogical reasons. The original first chapter has been split in order to allow a more thorough treatment of basic probability before tackling random processes and dynamical systems. The final chapter has been broken into two pieces to provide separate emphasis on process metrics and the ergodic decomposition of affine functionals. Many classic inequalities are now incorporated into the text, along with proofs; and many citations have been added.

Toeplitz and Circulant Matrices derives in a tutorial manner the fundamental theorems on the asymptotic behavior of eigenvalues, inverses, and products of banded Toeplitz matrices and Toeplitz matrices with absolutely summable elements. Mathematical elegance and generality are sacrificed for conceptual simplicity and insight in the hope of making these results available to engineers lacking either the background or endurance to attack the mathematical literature on the subject. By limiting the generality of the matrices considered, the essential ideas and results can be conveyed in a more intuitive manner without the mathematical machinery required for the most general cases. As an application the results are applied to the study of the covariance matrices and their factors of linear models of discrete time random processes. The book has been written for students and practicing engineers in an accessible manner bringing this important topic to a wider audience.

This book describes the essential tools and techniques of statistical signal processing. At every stage theoretical ideas are linked to specific applications in communications and signal processing using a range of carefully chosen examples. The book begins with a development of basic probability, random objects, expectation, and second order moment theory followed by a wide variety of examples of the most popular random process models and their basic uses and properties. Specific applications to the analysis of random signals and systems for communicating, estimating, detecting, modulating, and other processing of signals are interspersed throughout the book. Hundreds of homework problems are included and the book is ideal for graduate students of electrical engineering and applied mathematics. It is also a useful reference for researchers in signal processing and communications.

Stochastic Image Processing provides the first thorough treatment of Markov and hidden Markov random fields and their application to image processing. Although promoted as a promising approach for over thirty years, it has only been in the past few years that the theory and algorithms have developed to the point of providing useful solutions to old and new problems in image processing. Markov random fields are a multidimensional extension of Markov chains, but the generalization is complicated by the lack of a natural ordering of pixels in multidimensional spaces. Hidden Markov fields are a natural generalization of the hidden Markov models that have proved essential to the development of modern speech recognition, but again the multidimensional nature of the signals makes them inherently more complicated to handle. This added complexity contributed to the long time required for the development of successful methods and applications. This book collects together a variety of successful approaches to a complete and useful characterization of multidimensional Markov and hidden Markov models along with applications to image analysis. The book provides a survey and comparative development of an exciting and rapidly evolving field of multidimensional Markov and hidden Markov random fields with extensive references to the literature.

The Fourier transform is one of the most important mathematical tools in a wide variety of fields in science and engineering. In the abstract it can be viewed as the transformation of a signal in one domain (typically time or space) into another domain, the frequency domain. Applications of Fourier transforms, often called Fourier analysis or harmonic analysis, provide useful decompositions of signals into fundamental or "primitive" components, provide shortcuts to the computation of complicated sums and integrals, and often reveal hidden structure in data. Fourier analysis lies at the base of many theories of science and plays a fundamental role in practical engineering design. The origins of Fourier analysis in science can be found in Ptolemy's decomposing celestial orbits into cycles and epicycles and Pythagorus' de­ composing music into consonances. Its modern history began with the eighteenth century work of Bernoulli, Euler, and Gauss on what later came to be known as Fourier series. J. Fourier in his 1822 Theorie analytique de la Chaleur [16] (still available as a Dover reprint) was the first to claim that arbitrary periodic functions could be expanded in a trigonometric (later called a Fourier) series, a claim that was eventually shown to be incorrect, although not too far from the truth. It is an amusing historical sidelight that this work won a prize from the French Academy, in spite of serious concerns expressed by the judges (Laplace, Lagrange, and Legendre) re­ garding Fourier's lack of rigor.

Herb Caen, a popular columnist for the San Francisco Chronicle, recently quoted a Voice of America press release as saying that it was reorganizing in order to "eliminate duplication and redundancy. " This quote both states a goal of data compression and illustrates its common need: the removal of duplication (or redundancy) can provide a more efficient representation of data and the quoted phrase is itself a candidate for such surgery. Not only can the number of words in the quote be reduced without losing informa­ tion, but the statement would actually be enhanced by such compression since it will no longer exemplify the wrong that the policy is supposed to correct. Here compression can streamline the phrase and minimize the em­ barassment while improving the English style. Compression in general is intended to provide efficient representations of data while preserving the essential information contained in the data. This book is devoted to the theory and practice of signal compression, i. e. , data compression applied to signals such as speech, audio, images, and video signals (excluding other data types such as financial data or general­ purpose computer data). The emphasis is on the conversion of analog waveforms into efficient digital representations and on the compression of digital information into the fewest possible bits. Both operations should yield the highest possible reconstruction fidelity subject to constraints on the bit rate and implementation complexity.

Source coding theory has as its goal the characterization of the optimal performance achievable in idealized communication systems which must code an information source for transmission over a digital communication or storage channel for transmission to a user. The user must decode the information into a form that is a good approximation to the original. A code is optimal within some class if it achieves the best possible fidelity given whatever constraints are imposed on the code by the available channel. In theory, the primary constraint imposed on a code by the channel is its rate or resolution, the number of bits per second or per input symbol that it can transmit from sender to receiver. In the real world, complexity may be as important as rate. The origins and the basic form of much of the theory date from Shan­ non's classical development of noiseless source coding and source coding subject to a fidelity criterion (also called rate-distortion theory) [73] [74]. Shannon combined a probabilistic notion of information with limit theo­ rems from ergodic theory and a random coding technique to describe the optimal performance of systems with a constrained rate but with uncon­ strained complexity and delay. An alternative approach called asymptotic or high rate quantization theory based on different techniques and approx­ imations was introduced by Bennett at approximately the same time [4]. This approach constrained the delay but allowed the rate to grow large.