Random Processes for Image and Signal Processing

Excerpt

Science and engineering deal with temporal, spatial, and higher-dimensional processes that vary randomly from observation to observation. While one might study a specific observation for its algebraic or topological content, deterministic analysis does not provide a framework for understanding the ensemble of observations, nor does it provide a mechanism for prediction of future events. A system that functions over time needs to be designed in accordance with the manner in which input processes vary over time. System performance needs to be measured in terms of expected behavior and other statistical characteristics concerning operation on random inputs. There is an input random process, a transformation, and an output random process. System analysis begins with the input process and, based on the transformation, derives characteristics of the output process; system synthesis begins with an input process and a desired output process, and derives a transformation that estimates the desired output from the input.

Image and (one-dimensional) signal processing concern the analysis and synthesis of linear and nonlinear systems that operate on spatial and temporal random functions. As areas of applied science, image and signal processing mark off a region within the overall domain of random processes that suits the set of applications they encompass. Because our major concern is algorithm development, our major interest is operator synthesis. We focus on three basic problems: representation, filter design, and modeling. These are not independent; they form a unity that is the key to algorithm development in a stochastic framework. The end goal is design of a filter (operator). If the input process is given in terms of a representation that is compatible with the form of the desired filter, then design is enhanced. Ultimately, the filter is to be used on some class of real-world images or signals. Therefore we need models that fit real processes and whose mathematical structure facilitates design of filters to extract desired structural information.

My goal is not just to present the theory along with applications, but also to help students intuitively appreciate random functions. Were this a mathematics book, I would have taken the mathematical approach of stating general theorems and then giving corollaries for special situations. Instead, I have often begun with special cases in which probabilistic insight is more readily achievable. Moreover, I have not taken a theorem-proof approach. When provided, proofs are in the main body of the text and clearly delineated; sometimes they are either not provided or outlines of conceptual arguments are given. The intent is to state theorems carefully and to draw clear distinctions between rigorous mathematical arguments and heuristic explanations. When a proof can be given at a mathematical level commensurate with the text and when it enhances conceptual understanding, it is usually provided; in other cases, the effort is to explain subtleties of the definitions and properties concerning random functions, and to state conditions under which a proposition applies. Attention is drawn to the differences between deterministic concepts and their random counterparts, for instance, in the mean-square calculus, orthonormal representation, and linear filtering. Such differences are sometimes glossed over in method books; however, lack of differentiation between random and deterministic analysis can lead to misinterpretation of experimental results and misuse of techniques.

My motivation for the book comes from my experience in teaching graduate-level image processing and having to end up teaching random processes. Even students who have taken a course on random processes have often done so in the context of linear operators on signals. This approach is inadequate for image processing. Nonlinear operators play a widening role in image processing, and the spatial nature of imaging makes it significantly different from one-dimensional signal processing. Moreover, students who have some background in stochastic processes often lack a unified view in terms of canonical representation and orthogonal projections in inner product spaces.

The book can be used for courses in a number of ways. For students with a strong background in probability and statistics, it can form a one-semester course on random processes, with the obvious necessity of omitting a number of sections. Since the first chapter provides the essential probability and estimation theory that would normally be taught in a one-semester undergraduate course, the book can be used for a full-year course for students who lack a good undergraduate probability course. The book is structured with this use in mind. My experience shows me that very few engineering students come to graduate school having an adequate background in probability theory. Finally, owing to the large number of imaging applications, with the addition of some supplementary papers, the book can be used for a graduate course on image processing; indeed, I have taken such an approach here at Texas A&M. I suspect that a similar approach can be used for signal processing. For research-oriented departments, cookbook-style texts are totally inadequate and future researchers receive significant benefit from learning their specialty in the proper mathematical framework.

The first chapter covers basic probability theory, with attention paid to multivariate distributions and functions of several random variables. The probability theory concludes with a section on laws of large numbers. There follows a general section on parametric estimation. Maximum-likelihood estimators are covered and applied to a constant signal corrupted by various noise models. Estimation plays an important role throughout the book because it is not enough to know the probabilistic theory behind algorithm design; one also needs to be aware of the problems associated with estimating an optimal filter from sample signals. The chapter concludes with sections on entropy and coding.

The second chapter covers the basic properties of random functions typically found in general texts on engineering random processes. Differences are mainly in orientation, but this is important. The stochastic problems of image processing differ substantially from those of one-dimensional signal processing. Because the latter is more mature as a discipline, books on random processes tend to orient their image-signal processing applications toward signals. Historically, such an approach is natural; nevertheless, it is often not sufficient to give a definition, property, or application for signal processing and then say that, as presented, it is suitable for image processing. Many stochastic problems that are straightforward in one dimension become either very difficult or intractable in two dimensions. I try to take a balanced approach with the basic theory and continue to pay attention to both one-and two-dimensional processes throughout the text.

The third chapter treats canonical representation in the natural context of Fourier expansions in inner product spaces. The Karhunen-Loeve expansion is covered in detail: the meaning of the expansion, its relation to deterministic Fourier representation, and the role played by the eigenfunctions resulting from the covariance function. There follow sections on noncanonical representation, trigonometric representation of wide-sense stationary processes, and the role of canonical expansions as transforms. There is a substantial section on transform coding. It is placed in the context of the Karhunen-Loeve expansion, so that transform efficiency for other transforms, such as the discrete cosine and Walsh-Hadamard transforms, can be better understood. The text then goes into the general theory of discrete canonical expansions whose coefficients are generated by linear functionals. Properties of the coefficients and related coordinate functions are discussed. Because a canonical expansion of a random function can be derived from a canonical expansion of its covariance function, covariance expansions are discussed. Integral canonical expansions are theoretically more difficult and rely on the theory of generalized functions. Therefore the subject is treated formally with the understanding that we often consider random functions whose covariance functions are distributions. Integral canonical expansions provide an appropriate framework for discussion of the power spectral density and the Wiener-Khinchin theory. We are not merely concerned with the power spectral density as the Fourier transform of a covariance function; we are also concerned with white-noise representation of random functions. Representation is discussed in the context of necessary and sufficient conditions for an integral canonical expansion. The next section introduces vector random functions and their canonical representation. The chapter closes with an algorithm that produces a canonical representation over a discrete set that can be applied in very general circumstances.

The fourth chapter treats filter design. The basic theory of optimal mean-square-error filters is covered first. The next eight sections are committed to optimal linear filters. Coverage begins with application of the orthogonality principle to find the optimal linear filter for a finite number of observations. A number of examples are provided to explain both the algebraic and statistical aspects of the theory. The steepest-descent and LMS iterative algorithms are covered next, including convergence. Vector estimation begins with least-squares-estimation of a nonrandom vector, with the best estimator given in terms of the pseudoinverse of the design matrix. Because we assume that the columns of the design matrix are linearly independent, the pseudoinverse takes a simple form. The next section treats random vectors and requires the pseudoinverse of an autocorrelation matrix that may be singular. The main theorem follows directly from a basic theorem on finding projections into subspaces spanned by linearly dependent vectors in a Hilbert space. It is the main result for optimal finite-observation linear filters. The last section on finite-observation filters discusses recursive linear filters, concluding with the Kalman filter. Recursive linear filters are based on the fact that projections into direct sums of subspaces can be decomposed into sums of projections. This principle is introduced and both static and dynamic recursive filtering follow from it. The last three sections on optimal linear filtering involve infinite observations. The Kolmogorov theory places optimal linear filtering into the context of projections into subspaces generated by operators (in our case, integral operators). The Wiener-Hopf equation is derived and the Wiener filter for wide-sense stationary processes is covered. The next section considers optimal linear filtering in the context of a linear model. This approach can lead to an optimal filter being derived from a system of linear equations; in other cases, it leads to the solution of Wiener-Hopf-like equations that are simpler than the original equation. Optimal linear filtering culminates with the derivation of optimal filters in the framework of canonical expansions. Because it provides a general method for design, it may be considered the main section on optimal linear filtering. Having concluded coverage of linear filters, the chapter turns to nonlinear filters. There is extensive coverage of optimal binary filters, which are a key concern of digital image processing. For discrete binary images, optimization stays close to the probabilistic nature of the processes and optimal versus suboptimal design is appreciable at a very low level. Next, pattern classification is treated in the context of filter design and the Gaussian maximum-likelihood classifier is obtained under the appropriate model conditions. The chapter concludes with neural networks. Error back-propagation is discussed in the context of sum-of-squares error and adaptive network design. Overall, the chapter emphasizes the fundamental role of filter representation. This begins with the integral representation of linear filters and canonical decomposition of random functions, continues with the morphological representation of binary filters, and concludes with the representational power of neural-network filters.

The final chapter treats random models. A major portion is devoted to discrete- and continuous-time Markov chains. The range of application for these models is extensive, including engineering, computer science, and operations research. The key role of the Chapman-Kolmogorov equations is emphasized. Steady-state and stationary distributions are covered for both finite and infinite state spaces. Conditions for existence are given and methods for finding stationary distributions are explored. Special treatment is given to the birth-death model, random walks, and queues. Passing to two dimensions, Markov random fields and Gibbs distributions are discussed. Next comes the random Boolean model, which is fundamental to coverage processes, filtering, and texture analysis. Vacancy and hitting are discussed, and the simple linear Boolean model is discussed in some detail. Granulometries are treated in the following section, which describes granulometric classification and adaptive design of openings to filter clutter in the signal-union-noise model. The final section of the book provides elements of the theory of random closed sets and is at a higher mathematical level than the rest of the text. Its goal is twofold: to explain how the hit-or-miss topology arises naturally from the probabilistic requirements of a random closed set and to present the capacity theorem.

For those who wish to use the text without following the given order, I will outline the essential logical order of the book. Except for Sections 1.10 and 1.11, which are independent from the remainder of the book, one should be familiar with the first chapter before proceeding to random processes. Chapter 2 should be read in its entirety. The remaining three chapters are close to being independent. Except for Section 4.9, Chapter 4 does not depend on Chapter 3. In Chapter 4, one can go directly from Section 4.3 to Section 4.7; indeed, if desired, one can go from Section 4.1 to Section 4.10; however, I do not recommend reading Section 4.12 prior to Sections 4.2 and 4.3. Chapter 5 can be studied after completing Chapter 2. The last three sections of Chapter 5 can be read before the first four sections (exceptions being reference to Gaussian-maximum-likelihood classification in Section 5.6.2 and random walks in Section 5.6.3).

I hope readers find this book both instructive and enjoyable, and that it provides them with insight and knowledge useful to the pursuit of groundbreaking research. For me, a person trained in analysis, it represents a growing appreciation of the profound differences between deterministic and stochastic scientific epistemology.

Edward R. Dougherty

College Station, Texas

July 1998