Xem mẫu
- 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
- 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-
- 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)
- 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)
- 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 .
- 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.
- 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)
- 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,
- 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
- 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.
- 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.
- 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
- 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
- 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
- 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.
- 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
- 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)
- 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.
- 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.
nguon tai.lieu . vn
