当前位置:首页 >> >>

Multiscale principal components analysis for image local orientation estimation

Multiscale Principal Components Analysis for Image Local Orientation Estimation ?
XiaoGuang Feng Computer Engineering University of California, Santa Cruz Santa Cruz, CA 95064 xgfeng@soe.ucsc.edu
This paper presents an image local orientation estimation method, which is based on a combination of two already well-known techniques: the principal component analysis (PCA) and the multiscale pyramid decomposition. The PCA analysis is applied to ?nd the Maximum Likelihood (ML) estimate of the local orientation. The proposed technique is shown to enjoy excellent robustness against noise. We present both simulated and real image examples to demonstrate the proposed technique.

Peyman Milanfar Electrical Engineering University of California, Santa Cruz Santa Cruz, CA 95064 milanfar@ee.ucsc.edu
very sensitive to noise, making the estimate of local orientation directly from these rather unreliable. So there is often a need for some local or even global process to ’smooth’ the estimate. However, by smoothing one gives up localization. A mechanism with both noise robustness and feature localization is needed. The estimation method presented here is based on the Principal Components Analysis (PCA) [4], which at its core uses the Singular Value Decomposition (SVD) of the ensemble of gradient vectors in a local neighborhood to ?nd the dominant orientation. We develop this PCA-based method in a multiscale framework, which e?ectively enforces smoothness. Another bene?t of the proposed method is the adaptive compromise between the resolution of the orientation ?eld and its relative accuracy. In Section 2, the PCA analysis of local orientation will be introduced. We will also show that this method results in the ML estimate of the local orientation. In Section 3, we will develop the multiscale implementation of the PCA-based method. Section 4 contains the experimental results, in both simulated images and real images. In Section 5 we present our conclusions.



Image local orientation estimation plays an important role in many computer vision and image processing tasks such as edge detection, image segmentation, and texture analysis. The 2-D local orientation estimation is also directly related to optical ?ow estimation, which is the generalization of orientation in a 3-D space/time volume. Several techniques for local orientation estimation have been proposed in the past. Perona [2] extended the idea of anisotropic di?usion to orientation maps. Bigun et al. [3] posed the problem as the least-squares ?tting of a plane in the Fourier transform domain. Another set of techniques is based on steerable ?lters [6], but they are often limited in precision and generalization. Wilson et al. [8] developed a multiscale orientation estimation approach, which is closely related to the one we propose here. But our method of combining the PCA and multiscale is novel, more e?cient, and will give more robust results. Almost all the established local orientation estimation techniques are based on the analysis of the local gradient ?eld of the image. But the local gradients are
? Supported in part by U.S. National Science Foundation grants CCR-9984246


PCA Analysis of local orientation

Principal Components Analysis is used for computing the dominant vectors representing a given data set and also provides an optimal basis for minimum mean-squared reconstruction of the given data. It is also sometimes referred to as the Karhunen-Loeve Transform [4]. The computational basis of PCA is the calculation of the Singular Value Decomposition (SVD) of the data matrix, or equivalently the eigendecomposition of the data covariance matrix. Here we describe the method in terms of the SVD. Let us assume that in the image of interest f (x, y ), the orientation ?eld is piecewise constant. Under this

0-7803-7576-9/02$17.00 ? 2002 IEEE


assumption, the gradient vectors in a block should on average be orthogonal to the dominant orientation of the image pattern. So orientation estimation can be formulated as the task of ?nding a unit vector a, to maximize the average of angles θi between a and gradient vectors gi = ?f (xi , yi ), i = 1, ..., n, (within a local window) [1], equivalently to minimize:
n n

This can be accomplished by a variety of di?erencing operators, which ultimately can and should be optimized. Denote the local estimate of the gradient of image f (x, y ) at point (xk , yk ) by: ?f (k ) = ?f (xk , yk ) = [?f (xk , yk )/?x, ?f (xk , yk )/?y ]T In order to estimate the local orientation, we divide the gradient ?eld into local blocks (overlapped or nonoverlapped). For each block, group the gradients into an N × 2 matrix G as follows: ? ? ?f (1)T ? ?f (2)T ? ? ? (3) G=? ?. . . ? ? . ?f (N )T The last step is to compute the SVD of matrix G: G = U SV T (4)

(aT gi )2 = aT
i=1 i=1

T (gi gi )a = aT Ca


where C=
(i) (i) n i=1 gx gx (i) (i) n i=1 gx gy (i) (i) (i) n i=1 gx gy (i) (i) n i=1 gy gy (i)

subject to a = 1, where gx and gy are derivatives in x and y direction, respectively. This problem can be solved using Lagrange multipliers and it can be shown that the unit vector a minimizing aT Ca is the eigenvector of C corresponding to the smallest eigenvalue, or equivalently, the singular vector corresponding to the smallest singular value of G, de?ned in (3). Note that the SVD method is numerically more stable and e?cient. From the theory of Directional Statistics [5], for a bivariate Gaussian distributed random vector ?eld, the direction of the vectors will have von Mises distribution, with the probability density function (PDF): f (θ; ?, k ) = where 1 ek cos(θ??) 2πI0 (k )
2π k cos(θ )


where U is orthogonal and N × N , representing each vector’s ’contribution’ to the corresponding singular vector; S is N × 2, representing the energy in the dominant directions; and V is orthogonal and 2 × 2, in which the ?rst column v1 represents the dominant orientation of the gradient ?eld. By rotating v1 by 90 degrees, we have the dominant orientation in the image block. The di?erence between the singular value s1 and s2 can be used as a measure of accuracy or dominance of the estimate. However, because s1 ? s2 is an energy dependent measure, the quantity R= s1 ? s2 s1 + s2 (5)

1 I0 (k ) = 2π


In the task of local orientation estimation, we are concerned with the ’axes’ of orientation, which means the vectors a and ?a de?ne the same orientation. For Gaussian distributed random vectors (in our case, the gradient vectors), the axes of the vectors will have Bingham distribution. In the 2-D case, this is just the 2-wrapped von Mises distribution, which means, given the PDF of von Mises distribution f (θ), the PDF of Bingham distribution f ? (θ) = f (2θ) [5]. From [1], for Bingham distributed unit vectors, the ML estimate of the dominant direction equals to the ?rst singular vector v1 from the SVD of the data vector matrix(de?ned in equation 3). This shows that by assuming the gradient vectors to have Gaussian distribution, the PCA method will give the ML estimate. The ?rst step of the PCA-based method is the computation of the gradient map for the whole image.

will be more suitable for this task [3]. Note that the above quantity is bounded between 0 and 1, and is related to the condition number k of matrix G by: k?1 R= (6) k+1 The PDF of the condition number of an N × 2 independent and identically distributed (i.i.d) white Gaussian matrix is derived in [7]. From this we can get the PDF of R for an N × 2 i.i.d white Gaussian matrix (shown in Figure 1): p(R) = 4(N ? 1)R (1 ? R2 )N ?2 (1 + R2 )N (7)

We can use this PDF in a signi?cance test [11] to distinguish between a pure noise image and an image



x[n] = s[n] + v [n]



The MMSE estimate can be written in the form of recursive linear combination: s ?[n] = s ?[γn] + K [n](x[n] ? s ?[γn]) (12)

pdf of R




where K [n] is the Kalman gain matrix: K [n] = M [n|γn](C [n] + M [n|γn])?1
0.2 0.4 R 0.6 0.8 1

0 0


Figure 1: PDF of R (N=16) with orientation pattern. First we can set a signi?cance level threshold R? . For any given image block, we can perform the PCA-based estimation, if the R is less than R? , it is very likely that the corresponding image block is only pure white noise and contains no dominant orientation.

M [n|γn] is the covariance matrix of the estimation error. There are three major steps in our multiscale PCAbased method: 1. From the computed gradient ?eld of the given image, build up a gradient pyramid (Gaussian pyramid). 2. On each layer of the gradient pyramid, divide the gradient ?eld into local blocks (overlapped or nonoverlapped), and on each block, use the PCAbased method to estimate the local orientation. 3. Propagate the estimates from coarser layer to ?ner layer (as described in Equation 12), all the way to the ?nest resolution. In step 3, the optimal propagation weight is given by (13) in terms of the covariance of estimation error and the covariance of noise. But these quantities are unknown or hard to determine. Wilson et al. [8] used the ’average energy’ as propagation weights, which is not directly related to the variance of orientation. In our approach, we assume the innovation vector w[n] and the measurement noise v [n] are both zero-mean white Gaussian. Then both M [n|γn] and C [n] will be diagonal matrices and the Kalman gain matrix K [n] can be simpli?ed as a scalar quantity k [n] times the identity matrix, where k [n] can be approximated as: k [ n] ?
2 σγn 2 + σ2 σγn n


Multiscale Implementation

Multiscale signal and image analysis have been investigated for some time with applications in data compression, edge detection, and segmentation, etc. Wilson et al. [8] used a multiscale approach in orientation estimation. The method we propose here is similar to Wilson’s method, but our method combines PCA and multiscale, using the dominance measure R as the propagation weight. The combination of these techniques makes our method very e?cient and is shown to be more robust. As introduced in [9], multiscale estimation can be described within the framework of Kalman ?ltering across scales: s[n] = A[n]s[γn] + B [n]w[n] x[n] = H [n]s[n] + v [n] (8) (9)

where s[n] is the signal in the current layer; s[γn] is the signal in the parent layer (coarser resolution); x[n] is the measurement in the current layer; w[n] and v [n] are the innovation signal and measurement noise in current layer, respectively. The covariance matrix of v [n] is denoted as C [n]. In the task of local orientation estimation, the signal s[n] is the local dominant orientation (or equivalently, the local dominant gradients). The signal in the current layer can be modeled as the corresponding signal from parent layer (up-sampled to ?t the size) plus an innovation vector. And the measurement is simply the signal vector plus a noise vector. So we can simplify the Kalman ?lter equations as : s[n] = s[γn] + w[n] (10)


2 2 where σγn and σn are variances of orientation on parent layer and current layer, respectively. Note that in the PCA-based method, the dominance measure R can be viewed to be inverse proportional to the variance σ 2 . Thus we elect to de?ne the propagation weight in terms of R, which is easy to compute as a byproduct of the SVD. Our experiments show that this weight will give more robust estimates than Wilson’s approach. We have:

s ?[n] = s ?[γn] +

R [ n] (x[n] ? s ?[γn]) R[n] + R[γn]




Experimental Results

In order to test our method’s stability in the presence of noise, we generate a test image with single known sinusoidal orientation pattern and apply zero mean Gaussian white noise to it (Figure 2). Observe the change of the average estimation error with increasing noise variance. We compare the multiscale method with the single-scale method, both using PCA-based method to estimate the local orientation. For both methods, we compare the results of overlapped-neighbor-block and nonoverlapped-neighbor-block. We also compare the result with Wilson’s multiscale method. The results are shown in Figure 3.

than methods with non-overlapped blocks; and Wilson’s multiscale method is not as robust as the method proposed here. The multiscale method’s robustness to noise can be shown in another experiment. The test image in Figure 4 has diverse orientations with di?erent contrast. Gaussian white noise is applied in the right half. From the estimated orientation map we can see (Figure 5 and Figure 6), the single scale method is quite messy in the noisy half, while the multiscale method works well on both sides.

Figure 2: Left:clean test image(value range: 1).Right:noisy test image(noise variance: 0.6)


Figure 4: Test image

0.8 1 0.7 2
Average Error Angle (radians)

0.6 3 0.5 0.4 0.3 0.2 5 0.1 0 ?0.1


Figure 5: Orientation map of Figure 4, Single scale method



0.2 0.3 Noise variance




Figure 3: Multiscale VS. Single scale (1: PCA/Single scale, non-overlap; 2:PCA/Single scale, overlap; 3:Wilson’s multiscale method; 4:PCA/Multiscale, non-overlap; 5:PCA/Multiscale, overlap;) From Figure 3 we can see that the multiscale methods work much better than single scale methods; the methods with overlapped local blocks are more robust

Figure 6: Orientation map of Figure 4, Multiscale method


Finally, as an example of the performance of the proposed method on a real image, the orientation estimation result for a real ?ngerprint image is shown in Figure 8.

[2] Pietro Perona. Orientation di?usions, IEEE Transactions on Image Processing, 7(3):457-467, March 1998. [3] J. Bigun, G. H. Granlund, and Johan Wiklund. Multidimensional orientation estimation with applications to texture analysis and optical ?ow, IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(8):775-790, August 1991. [4] Ed. F. Deprettere. SVD and Signal Processing: Algorithms, Applications and Architectures. Elsevier Science Pub. Co., 1988. [5] K. V. Mardia and P. E. Jupp. ”Directional Statistics”, John Wiley Sons Ltd, 2000. [6] Leif Haglund and David J. Fleet. Stable estimation of image orientation, In Processings of the First IEEE International Conference on Image Processing, volumn III, pages 68-72, November 1994. [7] A. Edelman. Eigenvalues and condition numbers of random matrices, SIAM Journal on Matrix Analysis and Applications 9 (1988), 543–560. [8] R. Wilson, S. Clippingdale, A. H. Bhalerao. Robust Estimation of Local Orientations in Images Using a Multiresolution Approach, SPIE Visual Communications and Image Processing, Vol 1360, 1990. [9] Kenneth C. Chou, Alan S. Willsky, and Ramine Nikoukhah. Multiscale Systems, Kalman Filters and Riccati Equations, IEEE Transactions on Automatic Control, Vol 39, No.3, March 1994.

Figure 7: Fingerprint image

Figure 8: Orientation map of Figure 7



[10] C. G. Harris and M. Stephens. A combined corner and edge detector. In 4th Alvey Vision Conference, pages 147–151, 1988. [11] Alvin W. Drake. Fundamentals of Applied Probability Theory. McGraw-Hill Classic Textbook Reissue Series, McGraw-Hill Book Company. 1976.

The proposed orientation estimation method works well in terms of both robustness and accuracy. The PCA-based estimation gives the optimal (Maximum Likelihood) estimation of the local dominant orientation. The multiscale framework helps in noise rejection and balancing localization and accuracy. We point out that this multiscale PCA-based method can also be developed for other applications, e.g. corner detector. The PCA method is used in the Harris corner detector [10]. The multiscale PCA scheme presented here can be used to detect corners at di?erent scales.

[1] K. V. Mardia, J. T. Kent and J. M. Bibby. ”Multivariate Analysis”, Academic Press, 1979.




All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。