# Xử lý hình ảnh kỹ thuật số P5

Chia sẻ: Do Xon Xon | Ngày: | Loại File: PDF | Số trang:19

0
54
lượt xem
3

## Xử lý hình ảnh kỹ thuật số P5

Mô tả tài liệu

DISCRETE IMAGE MATHEMATICAL CHARACTERIZATION Chapter 1 presented a mathematical characterization of continuous image fields. This chapter develops a vector-space algebra formalism for representing discrete image fields from a deterministic and statistical viewpoint. Appendix 1 presents a summary of vector-space algebra concepts.

Chủ đề:

Bình luận(0)

Lưu

## Nội dung Text: Xử lý hình ảnh kỹ thuật số P5

1. Digital Image Processing: PIKS Inside, Third Edition. William K. Pratt Copyright © 2001 John Wiley & Sons, Inc. ISBNs: 0-471-37407-5 (Hardback); 0-471-22132-5 (Electronic) 5 DISCRETE IMAGE MATHEMATICAL CHARACTERIZATION Chapter 1 presented a mathematical characterization of continuous image fields. This chapter develops a vector-space algebra formalism for representing discrete image fields from a deterministic and statistical viewpoint. Appendix 1 presents a summary of vector-space algebra concepts. 5.1. VECTOR-SPACE IMAGE REPRESENTATION In Chapter 1 a generalized continuous image function F(x, y, t) was selected to represent the luminance, tristimulus value, or some other appropriate measure of a physical imaging system. Image sampling techniques, discussed in Chapter 4, indicated means by which a discrete array F(j, k) could be extracted from the contin- uous image field at some time instant over some rectangular area – J ≤ j ≤ J , – K ≤ k ≤ K . It is often helpful to regard this sampled image array as a N 1 × N 2 element matrix F = [ F ( n 1, n 2 ) ] (5.1-1) for 1 ≤ n i ≤ Ni where the indices of the sampled array are reindexed for consistency with standard vector-space notation. Figure 5.1-1 illustrates the geometric relation- ship between the Cartesian coordinate system of a continuous image and its array of samples. Each image sample is called a pixel. 121
2. 122 DISCRETE IMAGE MATHEMATICAL CHARACTERIZATION FIGURE 5.1-1. Geometric relationship between a continuous image and its array of samples. For purposes of analysis, it is often convenient to convert the image matrix to vector form by column (or row) scanning F, and then stringing the elements together in a long vector (1). An equivalent scanning operation can be expressed in quantita- tive form by the use of a N2 × 1 operational vector v n and a N 1 ⋅ N 2 × N 2 matrix N n defined as 0 1 0 1 … … … … 0 n–1 0 n–1 vn = 1 n Nn = 1 n (5.1-2) 0 n+1 0 n+1 … … … … 0 N2 0 N2 Then the vector representation of the image matrix F is given by the stacking opera- tion N2 f = ∑ N n Fv n (5.1-3) n=1 In essence, the vector v n extracts the nth column from F and the matrix N n places this column into the nth segment of the vector f. Thus, f contains the column-
3. GENERALIZED TWO-DIMENSIONAL LINEAR OPERATOR 123 scanned elements of F. The inverse relation of casting the vector f into matrix form is obtained from N2 T T F = ∑ N n fv n (5.1-4) n=1 With the matrix-to-vector operator of Eq. 5.1-3 and the vector-to-matrix operator of Eq. 5.1-4, it is now possible easily to convert between vector and matrix representa- tions of a two-dimensional array. The advantages of dealing with images in vector form are a more compact notation and the ability to apply results derived previously for one-dimensional signal processing applications. It should be recognized that Eqs 5.1-3 and 5.1-4 represent more than a lexicographic ordering between an array and a vector; these equations define mathematical operators that may be manipulated ana- lytically. Numerous examples of the applications of the stacking operators are given in subsequent sections. 5.2. GENERALIZED TWO-DIMENSIONAL LINEAR OPERATOR A large class of image processing operations are linear in nature; an output image field is formed from linear combinations of pixels of an input image field. Such operations include superposition, convolution, unitary transformation, and discrete linear filtering. Consider the N 1 × N 2 element input image array F ( n1, n 2 ). A generalized linear operation on this image field results in a M 1 × M 2 output image array P ( m 1, m 2 ) as defined by N1 N2 P ( m 1, m 2 ) = ∑ ∑ F ( n 1, n 2 )O ( n 1, n 2 ; m 1, m2 ) (5.2-1) n1 = 1 n 2= 1 where the operator kernel O ( n 1, n 2 ; m 1, m 2 ) represents a weighting constant, which, in general, is a function of both input and output image coordinates (1). For the analysis of linear image processing operations, it is convenient to adopt the vector-space formulation developed in Section 5.1. Thus, let the input image array F ( n1, n 2 ) be represented as matrix F or alternatively, as a vector f obtained by column scanning F. Similarly, let the output image array P ( m1, m2 ) be represented by the matrix P or the column-scanned vector p. For notational simplicity, in the subsequent discussions, the input and output image arrays are assumed to be square and of dimensions N 1 = N 2 = N and M 1 = M 2 = M , respectively. Now, let T 2 2 2 denote the M × N matrix performing a linear transformation on the N × 1 input 2 image vector f yielding the M × 1 output image vector p = Tf (5.2-2)
4. 124 DISCRETE IMAGE MATHEMATICAL CHARACTERIZATION The matrix T may be partitioned into M × N submatrices T mn and written as T11 T 12 … T 1N T21 T 22 … T 2N T = (5.2-3) … … … TM1 TM2 … T MN From Eq. 5.1-3, it is possible to relate the output image vector p to the input image matrix F by the equation N p = ∑ TN n Fv n (5.2-4) n =1 Furthermore, from Eq. 5.1-4, the output image matrix P is related to the input image vector p by M T T P = ∑ Mm pu m (5.2-5) m=1 Combining the above yields the relation between the input and output image matri- ces, M N T T P = ∑ ∑ ( M m TNn )F ( v n u m ) (5.2-6) m=1 n=1 where it is observed that the operators Mm and N n simply extract the partition T mn from T. Hence M N T P = ∑ ∑ Tmn F ( vn um ) (5.2-7) m =1 n =1 If the linear transformation is separable such that T may be expressed in the direct product form T = TC ⊗ TR (5.2-8)
5. GENERALIZED TWO-DIMENSIONAL LINEAR OPERATOR 125 FIGURE 5.2-1. Structure of linear operator matrices. where T R and T C are row and column operators on F, then T mn = T R ( m, n )T C (5.2-9) As a consequence, M N T T P = TC F ∑ ∑ T R ( m, n )v n u m = T C FT R (5.2-10) m =1 n = 1 Hence the output image matrix P can be produced by sequential row and column operations. In many image processing applications, the linear transformations operator T is highly structured, and computational simplifications are possible. Special cases of interest are listed below and illustrated in Figure 5.2-1 for the case in which the input and output images are of the same dimension, M = N .
6. 126 DISCRETE IMAGE MATHEMATICAL CHARACTERIZATION 1. Column processing of F: T = diag [ T C1, T C2, …, T CN ] (5.2-11) where T Cj is the transformation matrix for the jth column. 2. Identical column processing of F: T = diag [ T C, T C, …, T C ] = T C ⊗ I N (5.2-12) 3. Row processing of F: T mn = diag [ T R1 ( m, n ), T R2 ( m, n ), …, T RN ( m, n ) ] (5.2-13) where T Rj is the transformation matrix for the jth row. 4. Identical row processing of F: T mn = diag [ T R ( m, n ), T R ( m, n ), …, T R ( m, n ) ] (5.2-14a) and T = IN ⊗ TR (5.2-14b) 5. Identical row and identical column processing of F: T = TC ⊗ I N + I N ⊗ T R (5.2-15) The number of computational operations for each of these cases is tabulated in Table 5.2-1. Equation 5.2-10 indicates that separable two-dimensional linear transforms can be computed by sequential one-dimensional row and column operations on a data array. As indicated by Table 5.2-1, a considerable savings in computation is possible 2 2 for such transforms: computation by Eq 5.2-2 in the general case requires M N 2 2 operations; computation by Eq. 5.2-10, when it applies, requires only MN + M N operations. Furthermore, F may be stored in a serial memory and fetched line by line. With this technique, however, it is necessary to transpose the result of the col- umn transforms in order to perform the row transforms. References 2 and 3 describe algorithms for line storage matrix transposition.
7. IMAGE STATISTICAL CHARACTERIZATION 127 TABLE 5.2-1. Computational Requirements for Linear Transform Operator Operations Case (Multiply and Add) General N4 Column processing N3 Row processing N3 Row and column processing 2N3– N2 Separable row and column processing matrix form 2N3 5.3. IMAGE STATISTICAL CHARACTERIZATION The statistical descriptors of continuous images presented in Chapter 1 can be applied directly to characterize discrete images. In this section, expressions are developed for the statistical moments of discrete image arrays. Joint probability density models for discrete image fields are described in the following section. Ref- erence 4 provides background information for this subject. The moments of a discrete image process may be expressed conveniently in vector-space form. The mean value of the discrete image function is a matrix of the form E { F } = [ E { F ( n 1, n 2 ) } ] (5.3-1) If the image array is written as a column-scanned vector, the mean of the image vec- tor is N2 ηf = E { f } = ∑ N n E { F }v n (5.3-2) n= 1 The correlation function of the image array is given by R ( n 1, n 2 ; n 3 , n 4 ) = E { F ( n 1, n 2 )F∗ ( n 3, n 4 ) } (5.3-3) where the n i represent points of the image array. Similarly, the covariance function of the image array is K ( n 1, n 2 ; n 3 , n 4) = E { [ F ( n 1, n 2 ) – E { F ( n 1, n 2 ) } ] [ F∗ ( n 3, n 4 ) – E { F∗ ( n 3, n 4 ) } ] } (5.3-4)
8. 128 DISCRETE IMAGE MATHEMATICAL CHARACTERIZATION Finally, the variance function of the image array is obtained directly from the cova- riance function as 2 σ ( n 1, n 2 ) = K ( n 1, n 2 ; n 1, n 2 ) (5.3-5) If the image array is represented in vector form, the correlation matrix of f can be written in terms of the correlation of elements of F as N2 N T    2 T T T  R f = E { ff∗ } = E    ∑ Nm Fvm   ∑ vn F∗ Nn   n = 1  (5.3-6a) m=1 or N2 N2  T T T Rf = ∑ ∑ N m E  Fv m v n F∗ N n   (5.3-6b) m=1 n=1 The term  T T E  Fv m v n F∗  = R mn (5.3-7)   is the N 1 × N1 correlation matrix of the mth and nth columns of F. Hence it is possi- ble to express R f in partitioned form as R11 R 12 … R 1N 2 R21 R 22 … R 2N Rf = 2 … … … RN RN … RN 21 22 2 N2 (5.3-8) The covariance matrix of f can be found from its correlation matrix and mean vector by the relation T K f = R f – η f η f∗ (5.3-9) A variance matrix V F of the array F ( n1, n 2 ) is defined as a matrix whose elements represent the variances of the corresponding elements of the array. The elements of this matrix may be extracted directly from the covariance matrix partitions of K f . That is,
9. IMAGE STATISTICAL CHARACTERIZATION 129 V F ( n 1, n 2 ) = K n n 2 ( n 1, n1 ) (5.3-10) 2, If the image matrix F is wide-sense stationary, the correlation function can be expressed as R ( n 1, n 2 ; n3, n 4 ) = R ( n 1 – n3 , n 2 – n 4 ) = R ( j, k ) (5.3-11) where j = n 1 – n 3 and k = n 2 – n 4. Correspondingly, the covariance matrix parti- tions of Eq. 5.3-9 are related by K mn = K k m≥n (5.3-12a) mn = K∗ K∗ k m
10. 130 DISCRETE IMAGE MATHEMATICAL CHARACTERIZATION As a special case, consider the situation in which adjacent pixels along an image row have a correlation of ( 0.0 ≤ ρ R ≤ 1.0 ) and a self-correlation of unity. Then the covariance matrix reduces to N –1 1 ρR … ρR 2 N –2 KR = σR 2 ρR 1 … ρR 2 (5.3-15) … … … N –1 N –2 ρR 2 ρR 2 … 1 FIGURE 5.3-1. Covariance measurements of the smpte_girl_luminance mono- chrome image.
11. IMAGE STATISTICAL CHARACTERIZATION 131 FIGURE 5.3-2. Photograph of smpte_girl_luminance image. 2 where σ R denotes the variance of pixels along a row. This is an example of the covariance matrix of a Markov process, analogous to the continuous autocovariance function exp ( – α x ) . Figure 5.3-1 contains a plot by Davisson (6) of the measured covariance of pixels along an image line of the monochrome image of Figure 5.3-2. The data points can be fit quite well with a Markov covariance function with ρ = 0.953 . Similarly, the covariance between lines can be modeled well with a Markov covariance function with ρ = 0.965 . If the horizontal and vertical covari- ances were exactly separable, the covariance function for pixels along the image diagonal would be equal to the product of the horizontal and vertical axis covariance functions. In this example, the approximation was found to be reasonably accurate for up to five pixel separations. The discrete power-spectral density of a discrete image random process may be defined, in analogy with the continuous power spectrum of Eq. 1.4-13, as the two- dimensional discrete Fourier transform of its stationary autocorrelation function. Thus, from Eq. 5.3-11 N1 – 1 N2– 1  ju kv  W ( u, v ) = ∑ ∑ R ( j, k ) exp  – 2πi  ----- + -----   - - (5.3-16) N  j= 0 k=0  1 N2  Figure 5.3-3 shows perspective plots of the power-spectral densities for separable and circularly symmetric Markov processes.
12. 132 DISCRETE IMAGE MATHEMATICAL CHARACTERIZATION u v (a) Separable u v (b) Circularly symmetric FIGURE 5.3-3. Power spectral densities of Markov process sources; N = 256, log magnitude displays. 5.4. IMAGE PROBABILITY DENSITY MODELS A discrete image array F ( n1, n 2 ) can be completely characterized statistically by its joint probability density, written in matrix form as
13. IMAGE PROBABILITY DENSITY MODELS 133 p ( F ) ≡ p { F ( 1, 1 ), F ( 2, 1 ), …, F ( N 1, N 2 ) } (5.4-1a) or in corresponding vector form as p ( f ) ≡ p { f ( 1 ), f ( 2 ), …, f ( Q ) } (5.4-1b) where Q = N 1 ⋅ N 2 is the order of the joint density. If all pixel values are statistically independent, the joint density factors into the product p ( f ) ≡ p { f ( 1 ) }p { f ( 2 ) }…p { f ( Q ) } (5.4-2) of its first-order marginal densities. The most common joint probability density is the joint Gaussian, which may be expressed as –Q ⁄ 2 –1 ⁄ 2  1 T –1  p ( f ) = ( 2π ) Kf exp  – -- ( f – η f ) K f ( f – η f )  - (5.4-3)  2  where K f is the covariance matrix of f, η f is the mean of f and K f denotes the determinant of K f . The joint Gaussian density is useful as a model for the density of unitary transform coefficients of an image. However, the Gaussian density is not an adequate model for the luminance values of an image because luminance is a posi- tive quantity and the Gaussian variables are bipolar. Expressions for joint densities, other than the Gaussian density, are rarely found in the literature. Huhns (7) has developed a technique of generating high-order den- sities in terms of specified first-order marginal densities and a specified covariance matrix between the ensemble elements. In Chapter 6, techniques are developed for quantizing variables to some discrete set of values called reconstruction levels. Let r jq ( q ) denote the reconstruction level of the pixel at vector coordinate (q). Then the probability of occurrence of the possi- ble states of the image vector can be written in terms of the joint probability distri- bution as P ( f ) = p { f ( 1 ) = r j ( 1 ) }p { f ( 2 ) = r j ( 2 ) }…p { f ( Q ) = r j ( Q ) } (5.4-4) 1 2 Q where 0 ≤ j q ≤ j Q = J – 1. Normally, the reconstruction levels are set identically for each vector component and the joint probability distribution reduces to P ( f ) = p { f ( 1 ) = r j }p { f ( 2 ) = r j }…p { f ( Q ) = r j } (5.4-5) 1 2 Q
14. 134 DISCRETE IMAGE MATHEMATICAL CHARACTERIZATION Probability distributions of image values can be estimated by histogram measure- ments. For example, the first-order probability distribution P [ f ( q ) ] = PR [ f ( q ) = r j ] (5.4-6) of the amplitude value at vector coordinate q can be estimated by examining a large collection of images representative of a given image class (e.g., chest x-rays, aerial scenes of crops). The first-order histogram estimate of the probability distribution is the frequency ratio Np ( j ) H E ( j ; q ) = ------------- - (5.4-7) Np where N p represents the total number of images examined and N p ( j ) denotes the number for which f ( q ) = r j for j = 0, 1,..., J – 1. If the image source is statistically stationary, the first-order probability distribution of Eq. 5.4-6 will be the same for all vector components q. Furthermore, if the image source is ergodic, ensemble aver- ages (measurements over a collection of pictures) can be replaced by spatial aver- ages. Under the ergodic assumption, the first-order probability distribution can be estimated by measurement of the spatial histogram NS ( j ) HS ( j ) = ------------ - (5.4-8) Q where N S ( j ) denotes the number of pixels in an image for which f ( q ) = r j for 1 ≤ q ≤ Q and 0 ≤ j ≤ J – 1 . For example, for an image with 256 gray levels, H S ( j ) denotes the number of pixels possessing gray level j for 0 ≤ j ≤ 255. Figure 5.4-1 shows first-order histograms of the red, green, and blue components of a color image. Most natural images possess many more dark pixels than bright pixels, and their histograms tend to fall off exponentially at higher luminance levels. Estimates of the second-order probability distribution for ergodic image sources can be obtained by measurement of the second-order spatial histogram, which is a measure of the joint occurrence of pairs of pixels separated by a specified distance. With reference to Figure 5.4-2, let F ( n1, n 2 ) and F ( n3, n 4 ) denote a pair of pixels separated by r radial units at an angle θ with respect to the horizontal axis. As a consequence of the rectilinear grid, the separation parameters may only assume cer- tain discrete values. The second-order spatial histogram is then the frequency ratio NS ( j1, j2 ) H S ( j 1, j 2 ; r, θ ) = ----------------------- - (5.4-9) QT
15. IMAGE PROBABILITY DENSITY MODELS 135 FIGURE 5.4-1. Histograms of the red, green and blue components of the smpte_girl _linear color image. where N S ( j 1, j2 ) denotes the number of pixel pairs for which F ( n1, n 2 ) = r j1 and F ( n 3, n 4 ) = r j . The factor QT in the denominator of Eq. 5.4-9 represents the total 2 number of pixels lying in an image region for which the separation is ( r, θ ). Because of boundary effects, QT < Q. Second-order spatial histograms of a monochrome image are presented in Figure 5.4-3 as a function of pixel separation distance and angle. As the separation increases, the pairs of pixels become less correlated and the histogram energy tends to spread more uniformly about the plane.
16. 136 DISCRETE IMAGE MATHEMATICAL CHARACTERIZATION FIGURE 5.4-2. Geometric relationships of pixel pairs. j2 j1 FIGURE 5.4-3. Second-order histogram of the smpte_girl_luminance monochrome image; r = 1 and θ = 0 . 5.5. LINEAR OPERATOR STATISTICAL REPRESENTATION If an input image array is considered to be a sample of a random process with known first and second-order moments, the first- and second-order moments of the output image array can be determined for a given linear transformation. First, the mean of the output image array is  N1 N2    E { P ( m 1, m2 ) } = E  ∑ ∑ F ( n1, n2 )O ( n1, n2 ; m1, m2 ) (5.5-1a)  n =1 n2 = 1   1 
17. LINEAR OPERATOR STATISTICAL REPRESENTATION 137 Because the expectation operator is linear, N1 N2 E { P ( m 1, m 2 ) } = ∑ ∑ E { F ( n 1, n 2 ) }O ( n 1, n 2 ; m 1, m 2 ) (5.5-1b) n1 = 1 n2 = 1 The correlation function of the output image array is RP ( m 1, m 2 ; m 3 , m4 ) = E { P ( m 1, m 2 )P∗ ( m 3, m 4 ) } (5.5-2a) or in expanded form  N1 N2  R P ( m 1, m2 ; m 3 , m 4 ) = E   ∑ ∑ F ( n 1, n 2 )O ( n 1, n 2 ; m 1, m 2 ) × n 1 = 1 n 2= 1  N1 N2   ∑ ∑ F∗ ( n 3, n 4 )O∗ ( n 3, n 3 ; m 3, m4 )   n3 = 1 n4 = 1  (5.5-2b) After multiplication of the series and performance of the expectation operation, one obtains N1 N2 N1 N2 R P ( m 1, m 2 ; m 3, m 4 ) = ∑ ∑ ∑ ∑ RF ( n 1, n 2, n 3, n 4 )O ( n 1, n 2 ; m1, m 2 ) n1 = 1 n2 = 1 n 3 = 1 n4 = 1 × O∗ ( n 3, n 3 ; m3, m 4 ) (5.5-3) where R F ( n 1, n 2 ; n 3 , n 4 ) represents the correlation function of the input image array. In a similar manner, the covariance function of the output image is found to be N1 N2 N1 N2 KP ( m 1, m 2 ; m 3, m 4 ) = ∑ ∑ ∑ ∑ KF ( n 1, n 2, n 3, n 4 )O ( n 1, n 2 ; m 1, m 2 ) n1 = 1 n2 = 1 n 3 = 1 n4 = 1 × O∗ ( n 3, n 3 ; m3, m 4 ) (5.5-4)
18. 138 DISCRETE IMAGE MATHEMATICAL CHARACTERIZATION If the input and output image arrays are expressed in vector form, the formulation of the moments of the transformed image becomes much more compact. The mean of the output vector p is η p = E { p } = E { Tf } = TE { f } = Tηf η (5.5-5) and the correlation matrix of p is T T T T R p = E { pp∗ } = E { Tff∗ T∗ } = TRf T∗ (5.5-6) Finally, the covariance matrix of p is T K p = TK f T∗ (5.5-7) Applications of this theory to superposition and unitary transform operators are given in following chapters. A special case of the general linear transformation p = Tf , of fundamental importance, occurs when the covariance matrix of Eq. 5.5-7 assumes the form T K p = TK f T∗ = Λ (5.5-8) where Λ is a diagonal matrix. In this case, the elements of p are uncorrelated. From Appendix A1.2, it is found that the transformation T, which produces the diagonal matrix Λ , has rows that are eigenvectors of K f . The diagonal elements of Λ are the corresponding eigenvalues of K f . This operation is called both a matrix diagonal- ization and a principal components transformation. REFERENCES 1. W. K. Pratt, “Vector Formulation of Two Dimensional Signal Processing Operations,” Computer Graphics and Image Processing, 4, 1, March 1975, 1–24. 2. J. O. Eklundh, “A Fast Computer Method for Matrix Transposing,” IEEE Trans. Com- puters, C-21, 7, July 1972, 801–803. 3. R. E. Twogood and M. P. Ekstrom, “An Extension of Eklundh's Matrix Transposition Algorithm and Its Applications in Digital Image Processing,” IEEE Trans. Computers, C-25, 9, September 1976, 950–952. 4. A. Papoulis, Probability, Random Variables, and Stochastic Processes, 3rd ed., McGraw-Hill, New York, 1991.
19. REFERENCES 139 5. U. Grenander and G. Szego, Toeplitz Forms and Their Applications, University of Cali- fornia Press, Berkeley, CA, 1958. 6. L. D. Davisson, private communication. 7. M. N. Huhns, “Optimum Restoration of Quantized Correlated Signals,” USCIPI Report 600, University of Southern California, Image Processing Institute, Los Angeles August 1975.