The MAP labeling with a prior potential of the form introduced in Section 1.3.3 is equivalent to the regularization of an ill-posed problem. A problem is mathematically an ill-posed problem [Tikhonov and Arsenin 1977] in the Hadamard sense if its solution (1) does not exist, (2) is not unique or (3) does not depend continuously on the initial data. An example is surface reconstruction or interpolation. A problem therein is that there are infinitely many ways to determine the interpolated surface values if only the constraint from the data is used. Additional constraints are needed to guarantee the uniqueness of the solution to make the problem well-posed. An important such constraint is smoothness. By imposing the smoothness constraint, the analytic regularization method converts an ill-posed problem into a well-posed one. This has been used in solving low level problems such as surface reconstruction from stereo [Grimson 1981], optical flow [Horn and Schunck 1981], shape-from-shading [Ikeuchi and Horn 1981], and motion analysis [Hildreth 1984]. A review of earlier work of regularization in vision is given by [Poggio et al. 1985]. Relationships between regularization and smoothing splines for vision processing are investigated by [Terzopoulos 1986b ; Lee and Pavlidis 1987].
A regularization solution is obtained by minimizing an energy of the following form
where is a set of indices to the sample data points, 's are the locations of the data points, is a weighting factor and is an integer number. The first term on the RHS, called the closeness term, imposes the constraint from the data d. The second term, called the smoothness term or the regularizer, imposes the a priori smoothness constraint on the solution. It is desired to minimize both but they may not be each minimized simultaneously. The two constraints are balanced by . Any f minimizing (1.86) is a smooth solution in the so-called Sobolev space (In the Sobolev space, every point f is a function whose n-1 derivative is absolutely continuous and whose n-th derivative is square integrable) . Different types of regularizers impose different types of smoothness constraints. Section 1.3.3 has described smoothness priors for some classes of surfaces. A study of the quadratic smoothness constraints is given in [Snyder 1991].
Under certain conditions, the MAP labeling of MRFs is equivalent to a regularization solution [Marroquin et al. 1987]. These conditions are (1) that the likelihood energy is due to additive white Gaussian noise and (2) that the prior assumption is the smoothness. Letting n=1 and discretizing x, (1.86) becomes the posterior energy (1.84) for the restoration of flat surfaces (in 1D). When the regularizer takes the form of the rod (1.61), it encodes the smoothness of planar surfaces (in 1D). The 2D counterparts are the membrane (1.60), (1.65) and the plate (1.66).
MRFs is more general than regularization in that it can encode not only the smoothness prior but also priors of other constraints. MRF-based models have to be chosen among the two when the priors are due to those other than the smoothness, e.g. in texture modeling and analysis. However, regularization can deal with spatially continuous fields whereas MRFs, which in this book are spatially discrete, cannot. When the problem under consideration involves concepts such as discontinuities, the analytical regularization is more suitable for the analysis. This is why we will study the issue of discontinuities, in Chapter 3, from regularization viewpoint.