Pergamon Pattern Recognition, Vol. 30, No. 5, pp. 751-768, 1997 © 1997 Pattern Recognition Society. Published by Elsevier Science Ltd Printed in Great Britain. All rights reserved 0031-3203/97 $17.00+.00 PII: S0031-3203(96)00104-5 TEMPLATE MATCHING: MATCHED SPATIAL FILTERS AND BEYOND R. BRUNELLI~'* and T. POGGIO$ tlstituto per la Ricerca Scientifica e Tecnologica, 1-38050 Povo, Trento, Italy eArtificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, U.S.A. (Received 27 November 1995; in revised form 1 July 1996; received for publication 15 July 1996) Abstract--Template matching by means of cross-correlation is common practice in pattern recognition in spite of its drawbacks. This paper reviews some results on how these shortcomings can be removed. Several techniques (Matched Spatial Filters, Synthetic Discriminant Functions, Principal Components Projections and Reconstruction Residuals) are reviewed and compared on a common task: locating eyes in a database of faces. New variants are also proposed and compared: least squares Discriminant Functions and the combined use of projections on eigenfunctions and the corresponding reconstruction residuals. Finally, approximation networks are introduced in an attempt to improve filter design by the introduction of nonlinearity. © 1997 Pattern Recognition Society. Published by Elsevier Science Ltd. Template matching Correlation Neural networks Learning HyperBF networks Principal components 1. INTRODUCTION The detection and recognition of objects from their images, irrespective of their orientation, scale, and view, is a very important research subject in computer vision, if not computer vision itself. Several techniques have been proposed in the past to solve this challenging problem. In this paper we will focus on a subset of these techniques, those employing the idea of projection to match image patterns. The notion of Matched Spatial Filter (MSF) is a venerable one with a long history. °) While by itself it cannot account for invariant recognition, it can be coupled to invariant mappings or signal expansions, and is therefore able to provide invariance to rotation and scaling in the image plane. In order to cope with more general variations of the object's views more sophisti- cated approaches have to be employed. Among them, the use of Synthetic Discriminant Functions ~2-~4) is one of the more promising so far developed. In these paper we will follow a path from MSF, to expansion matching through different variant of SDFs. Section 2 describes the basic properties of MSF, their optimality and their relation to the probability of misclassification. The gen- eralization of MSF to a linear combination of example images is introduced next. Several shortcomings of the basic approach are outlined and a set of possible solutions is presented in the subsequent section. We discuss a relation of the resulting class of filters to nonorthogonal image expansion. A generalization to projections on multiple directions and the use of the projection residual for pattern matching is then investigated. °5-2°) Finally, a more powerful, nonlinear framework is introduced in which template matching can be looked at as a problem * Author to whom correspondence should be addressed. of function approximation. Network architectures and training strategies are proposed within this new general framework. 2. MATCHED SPATIAL FILTER Template matching is extensively used in low-level vision tasks to localize and identify patterns in images. Two methods are commonly used: 1. Image subtraction: images are considered as vectors and the norm of their difference is considered as a measure of dissimilarity; 2. Correlation: the dot product of two images is con- sidered as a measure of their similarity (it represents the angle between the images when they are suitably normalized and considered as vectors). When the images are normalized to have zero average and unit norm, the two approaches give the same result. The usual implementation of the above methods relies on the Euclidean distance. Other distances can be used and some of them have better properties such as increased robustness to noise and minor deformationsJ 2~) The next sections are mainly concerned with the correlation ap- proach. The idea of image subtraction is introduced again in the more general nonlinear framework. 2.1. Optimality One of the reasons for which template matching by correlation is commonly used is that correlation can be shown to be the optimal (according to a particular criterion) linear operation by which a deterministic signal corrupted by additive white Gaussian noise can be 751
`
`Magna 2046
`TRW v. Magna
`IPR2015-00436
`
`

`
`752 R. BRUNELLI and T. POGGIO detected31) Let the signal be g(x) = (~(x) + A(x), (1) where 0(x) is the original, uncorrupted, signal and A(x) is noise with power spectrum S(co). The noise is assumed to be wide-sense stationary with zero average so that e{;~(x)} = 0, e{;~(x + ,,);~(x)} = R(a). We assume that 0(x) is known and we want to establish its presence and location. To do so we apply to the process g(x) a linear filter with impulse response h(x) and system function H(co). The resulting output is z(x) = g(x) * h(x) = f g(x - a)h(a) do (2) oc = z~(x) + z~(x). (3) Using the convolution theorem for the Fourier transform we have that zo(x) : 70(x - a)h(a) do -- ,oc =2~f • (co)H (~o)expiwx dco. --oc We want to find H(~o) so as to maximize the following signal to noise ratio (SNR): r 2- IZ¢(X°)2 (4) E{z~(x0)}' where Xo is the location of the signal. The SNR represents the ratio of the filter responses at the uncorrupted signal and at the noise. It is defined at the true location of the signal (usually the correlation peak) therefore not taking into account the off-peak response of the filter. Two cases of particular interest are those of white and colored noise: White Noise: This type of noise is defined by the following condition: S(~o) = S0, which corresponds to a flat energy spectrum. The Schwartz inequality states that f f(x)g(x) <_ f(x)l 2 Ig(x)l 2 a a a and the equality holds iff f(x)= k~,(x) (we use - to represent complex conjugation). This implies the follow- ing bound for the signal to noise ratio r: r2 _< f ~(co) expi~oxol 2 dw f IH(w)l 2 dw 27rSo f H(w)I 2 dco and then rZ < E2_ ~ -- So' where 1 f g~ = ~ J I~b(w)l 2 d~ represents the energy of the signal. From the Schwartz inequality the equality holds only if H(co) = k/~(co) exp-i~ox0. The spatial domain version of the filter is simply the mirror image of the signal: h(x) = kO(xo - x) which implies that the convolution of the signal with the filter can be expressed as the cross-correlation with the signal (hence the name Matched Spatial Filter). Colored Noise: If the noise has a nonflat spectrum S(co) it is said to be colored. In this case the following holds: 2rrz0(x0) = f ~(aJ)H(w) expicox dw, <-.s IO(W)S(u;)expi~x 12 dw × s(.~)lu(~)l 2 d~, J hence 1 f I~(co)expicoxl 2 r2 <-- ~ S(~) d~ with equality holding only when ~H(~) = k ~ exp-i~ox0 The main consequence of the color of noise is that the optimal filter corresponds to a modified version of the signal k ~ exp-iwx0 n(~) -- s(~) ' which emphasizes the frequencies where the energy of the noise is smaller. The optimal filter can also be considered as a cascade of a whitening filter S-1/2(co) and the usual filter based on the transformed signal. In the spatial domain, correlation amounts to project- ing the signal g(x) onto the available template O(x). If the norm of the projected signal is not equal to that of the template, the value of the projection can be meaningless as the projection value can be large without implying that the two vectors are close in any reasonable sense. The solution is to compute the projection using normalized vectors. In particular, if versors are used, computing the projection amounts to computing the cosine of the angle formed by the two vectors, which is an effective measure of similarity. In vision tasks, vector normalization corre- sponds to adjusting the intensity scale so that the corre- sponding distribution has a given variance. Another
`
`

`
`Template matching: method spatial filters and beyond 753 useful normalization is to set the average value of the vector coordinates to zero. This operation corresponds to setting the average of the intensity distribution for images. These normalizations are particularly useful when modern cameras are used, as they usually operate with automatic gain level (acting on the scale of the intensity) and black level adjustment (acting as an offset on the intensity distribution). 2.2. Distorted templates The previous analysis was focused on the detection of a deterministic signal corrupted by noise. An interesting extension is the detection of a signal belonging to a given distribution of signals. (2) As an example, consider the problem of locating the eyes in a face image. We do not know who's face it is so that we cannot select the corresponding signal (the eyes of that person). A whole set of different eyes could be available, possibly includ- ing the correct ones. Let {~b(x)} denote the class of signals to be detected. We want to find the filter h which maximizes the SNR r 2 over the class of signals { O(x) }. The input signal ~b(x) can be modeled as a sample realization of the stochastic process { q~(x)}. The ensemble-average correlation func- tion of the stochastic process is defined by roc~(x,y ) = Ee,{~(x)~(y)} (5) and represents the average over the ensemble of signals (and not over the coordinates of a signal). What we want to maximize is the ensemble average of the signal to noise ratio: E~{r 2} E{lzo(x°)12} -- ~. (6) Assume, without loss of generality, that x0=0. The average SNR can then be rewritten as E6{r2} = ffh(-x)h(-y)K~o(x,y)dxdy (7) f f h(-x)h(-y)Ka~ (x, y) dx dy' where the ensemble autocorrelation function of the signal and noise have been used. The autocorrelation function of the white noise is proportional to a Dirac delta func- tion: Kaa(x,y) = N6(x - y) (8) so that the average signal to noise ratio can be rewritten as E~{r2} = f f h(-x)h(-y)K~¢(x,y) dxdy N f h(_x)2 dx (9) Pre-whitening operators can be applied as preprocessing functions when the assumption of white noise does not hold. The denominator of the RHS in equation (9) re- presents the energy of the filter and we can require it to be 1: f h(-x)2dx = (10) 1. To optimize equation (9) we must maximize the numera- tor subject to the energy constraint of the filter. The ensemble autocorrelation function can be expressed in terms of the orthonormal eigenfunctions of the integral kernel Ke)~(x, y) K~o(x,y) = Z .~iOi(x)@i(Y), (1 l) i where the Ai are the corresponding eigenvalues. The filter function h can also be expanded in the same basis h(-x) = Z Cdi~Ji(X)" (12) i Using the inner product notation and the orthonormality of the ~i(x) we can state the optimization problem as finding arg max ~-~)~i(h.~i) 2. (13) ~,4:1 "-7" If we order the eigenvalues so that/~1 >_A2>.. ">_Ak2" ", we have N . E~{r 2} = ~ Ai(h " ~i) 2 i = ~.~iw~ < )q Z a;~= A, (14) i i and the maximum value is achieved when the filter function is taken to be the dominant eigenvector. 2.3. Signal to noise ratio and classification error Several performance metrics are available for correla- tion filters that describe attributes of the correlation plane. The signal to noise ratio (SNR) is just one of them. Other useful quantities are the peak-to-correlation energy, the location of the correlation peak and the invariance to distortion. As correlation is typically used to locate and discriminate objects, another important measure of a filter's performance is how well it discri- minates between different classes of objects. The sim- plest case is given by the discrimination between the signal and the noise. In this section we will show (14'22) that for the classical matched filter maximizing the SNR is equivalent to minimizing the probability of classifica- tion error Pe when the underlying probability distribution functions (PDFs) are Gaussians. The classifier which minimizes the probability of error is the Bayes classifier. If we consider two normal dis- tributions A and B, according to the Bayes decision rule, the observed vector x E A if (X - mA)'r~Al (X -- mA) -- (X -- ms)'r~l (x -- mB) 1-EAI PA (15) + n~-~ < 21n p~ and x E B otherwise, where mA, me are the distribution means, Za, EB the covariance matrices and PA, PB the occurrence probabilities. Let us consider two classes: a deterministic signal corrupted with white Gaussian noise as class A and the noise itself as class B. In this case mA = q~, me = 0 and ~A = ~B = I. This means that the compo-
`
`

`
`754 R. BRUNELLI and T. POGGIO Fig. 1. The probability of error, represented by the shaded area, when the distributions are Gaussian with the same covafiance. nents of the signal are uncorrelated and have unit var- iance. If we further assume that the a priori probabilities of occurrence of these classes are equal, the probability of error (see also Fig. 1) is given by ? exp(-u2/2)du, (16) 1 Pe--v~ r/ where ~? = ½ (1/2, with ( being the Mahalanobis distance between the PDFs of the two classes: : (raA -- mB)Tl(raA -- m/~) = ~bTq5 (17) and the Bayes decision rule simplifies to x E A if ~bTx > ~, (18) 1 x C B if ~Tx < ~. (19) The input vector x is then classified as signal or noise depending on the value of the correlation with the un- corrupted signal. We have already shown that correlation with the signal maximizes the signal to noise ratio, so when the noise distribution is Gaussian maximizing the SNR is equivalent to minimizing the classification error probability. When the noise is not white, the signal can be transformed by applying a whitening transformation A: ATEA = I (20) and the previous reasoning can be applied. 3. SYNTHETIC DISCRIMINANT FUNCTIONS While correlators are optimal for the recognition of patterns in the presence of white noise they have three major limitations: the output of the correlation peak degrades rapidly with geometric image distortions, the peak is often broad (see Fig. 2), making its detection difficult, and they cannot be used for multiclass pattern recognition. It has been noted that one can obtain better performance from a multiple correlator (i.e. one comput- ing the correlation with several templates) by forming a linear combination of the resulting outputs instead of, for example, taking the maximum value. (23"24) The filter synthesis technique known as Synthetic Discriminant Functions (SDF) starts from this observation and builds a filter as a linear combination of MSFs for different patterns. (3'4) The coefficients of the linear combination are chosen to satisfy a set of constraints on the filter output, requiring a given value for each of the patterns used in the filter synthesis. By forcing the filter output to different values for different patterns, multiclass pattern recognition can be achieved. Let { 0i (x) }i 1 ...... be a set of (linearly independent) images and u = {u j,..., un} T be a vector representing the required output of the filter for each of the images: ~i @ h = ui (21) where ® represents correlation (not convolution). The filter h can be expressed as a linear combination of the images ~hi: h(x) = E biOi(x) (22) i=l,...,n 10 0 N.I . X 0.0 Fig. 2. The cross-correlation of the template reported on the right. Note the diffuse shape of the peak that makes its localization difficult.
`
`

`
`Template matching: method spatial filters and beyond 755 as any additional contribution from the space ortho- gonal to the images would yield a zero contribution when correlating with the image set. If we denote by X the matrix whose columns represent the images (re- presented as vectors by concatenating their rows), by enforcing the constraints we obtain the following set of equations: b = (xTx) lu, (23) which can be solved as the images are linearly indepen- dent. The resulting filter is appropriate for pattern re- cognition applications in which the input object can be a member of several classes and different distorted ver- sions of the same object (or different objects) can be expected within each class. If M is the number of classes, ng the number of different pattern within each class i, N the overall number of patterns, M filters can be built by solving bi = (xTx)-Igi, i = I,...,M, (24) where {~ i-I ~ik : ~-~j::l /'/J < k < ~j:l I/j, (25) otherwise, k = 1,..., N and image Ck belongs to class i if ~Sik = 1. Discrimination of different classes can be obtained also using a single filter and imposing different output values. However the performance of such a filter is expected to be inferior to that of a set of class specific filters due to the high number of constraints imposed on the filter outputs. (3) While this approach makes it easy to obtain predefined values on a given set of patterns it does not allow to control the off-peak filter response. This can prevent reliable classification when the number of con- straints becomes large. The effect of filter clutter can also appear in the construction of a filter giving a fixed response over a set of images belonging to the same class (the Equal Correlation Filter introduced in reference (3)). In order to minimize this problem we propose a new variant of SDFs: least squares SDFs. These filters are computed using only a subset of the training images 1 and the coefficient of the linear combination is chosen to minimize the square error of the filter output on all of the available images. In this case the matrix R = xTx is rectangular and the estimate of the b relies on the computation of the pseudoinverse of R: R t = (RTR) IRT. (26) The dimension of the matrix to be inverted is n × n, where n represents the number of images used to build the filter and not the (greater) number of training images. By using a reduced number of building templates the problem of ~The subset of training images can be chosen in a variety of ways. In the reported experiments they were chosen at random. Another possibility is that of clustering the available images, the number of clusters being equal to the number of images used in filter synthesis. filter cluttering is reduced. A different use of least square estimation for filter synthesis can be found in reference (4) where it is coupled to Karhunen-Loeve expansion for the construction of correlation SDFs. The results for a sample application are reported in Fig. 3. Note that by using a least square estimate a good performance can be achieved using a small number of templates. This has a major influence on the appearance of the resulting MSF as can he seen in Fig. 4. Another variant is to use symbolic encoded filters. (3~ In this case a set of k filters is built whose outputs are 0 or 1 and can be used to encode the different patterns using a binary code. In order to use the filter for classification, the outputs are thresholded and the resulting binary number is used to index the pattern class. Synthesis of the MSF from a projection SDF algo- rithm can achieve distortion invariance and retain shift invariance. However, the resulting filter cannot prevent large sidelobe levels from occurring in the correlation plane for the case of false (or true) targets. The next section will detail the construction of filters which guarantee controlled sharp peaks and good noise immunity. 4. ADVANCED SDFs The signal to noise ratio maximized by the MSF is limited to the correlation peak: it does not take into account the off-peak response and the resulting filters often exhibit a sustained response welt apart from the location of the central peak. This effect is usually am- plified in the case of SDF when many constraints are imposed on the filter output. In order to locate the correlation peak reliably, it should be very localized. (5) However, it can be expected that the greater the localiza- tion of the filter response (approaching a ~ function) the more sensitive the filter to slight deviations from the patterns used in its synthesis. This suggests that the best response of the filter should not really be a function, but some shape, like a Gaussian, whose dispersion can be tuned to the characteristics of the pattern space. In this section we will review the synthesis of such filters in the frequency domain. (12) Let us assume for the moment that there is no noise. The correlation of the ith pattern with the filter h is represented by zi(n)-~i(n)®h(n), n=0 ..... d-l, (27) where d is the dimension of the patterns. In the following, capital letters are used to denote the Fourier transformed quantities. The filter is also required to produce an output ui for each training image: zi(O) = ui, (28) which can be rewritten in the Fourier domain as H+X = du, (29) where + denotes complex conjugate transpose. Using Parseval's theorem, the energy of the ith circulant cor-
`
`

`
`756 R. BRUNELLI and T. POGGIO Generalized Matched Filters 1.0 ....... , ............. u SDF O. 9 z~ Average c 0 Maximum .o 0.8 "5 i i o 0.7 ............................................................................................. t 0.6 ..... ~~~ .......... -j .......... &---- ............ , , , , , , i , 4 6 8 10 12 14 16 Troining imoges Fig. 3. An increasing portion of a set of 30 eyes images was used to build an SDF, an average MSF or a set of prototype MSFs from which the highest response was extracted. Our new least square SDF uses four building templates. The plot reports the average responses over a disjoint 30 image test set. Note that the lower values of MSFs are due to the fact that their response is not scaled to obtain a predefined value as opposed to SDFs whose output is constrained to be 1, and to approximate 1 for ls SDFs. i Fig. 4. The MSFs resulting from using 20 building images in the SDF (left) and 2 in the least square SDF (right) when using the same set of training images. The difference in contrast of the two images reflects the magnitude of the MSFs. The performance of the two filters was similar. relation plane is given by d-I ldl Ei = ~ Iz,(n) 2 = ~ ~ lZi(k)l 2 n=0 k=0 1 a-1 = - ~_, In(k)12l~i(k) 2. (30) d k=0 When the signal is perturbed with noise the output of the filter will also be corrupted: zi(O) = ~bi(0) ® h(0) + ,~(0) ® h(0). (31) Under the assumption of zero-mean noise, the variance of the filter output due to noise is 1 d-I EN = ~l ~-" IH(k)IES(k)' (32) k=0 where S(k) is the noise spectral energy. What we would like is a filter whose average correlation energy over the different training images and noise is as low as possible while meeting the constraints on the filter outputs. A first choice is to minimize E = ~_, (El + EN) (33) i 1 = ~l ~ ~ In(k)12(~'(k) 12 + S(k)) (34) i k subject to the constraints of equation (29). However, minimizing the average energy (or filter variance due to noise) does not minimize each term, corresponding to a particular correlation energy (or noise variance). A more stringent bound can be obtained by considering the spectral envelope of the different terms in equation (34): E = ~ IH(k)12max(l~l (k)12,..., I~N(k)I 2, S(k)). k (35)
`
`

`
`Template matching: method spatial filters and beyond 757 If we introduce the diagonal matrix Tkk = N max(lqh (k)12,..., ~s(k)2, S(k)) the filter synthesis can be summarized as minimizing E = H+TH (36) subject to H+ X = du. (37) This problem can be solved (7) using the technique of Lagrange multipliers to minimize the function: N = H+TH - 2 ~ ,~i(n+xi - dui), (38) i=1 where A1, • • •, As are the parameters introduced to satisfy the constrained minimization. By zeroing the gradient of with respect to H we can express H as a function of T and of A= {A1,...,AN}. By substitution into equa- tion (37), the following solution is found: H = T-1X(X+T Ix)-lu. (39) The use of the spectral envelope has the effect of redu- cing the emphasis given by the filter to the high fre- quency content of the signal, thereby improving intraclass performance. It is important to note that the resulting filter can be seen as a cascade of a whitening filter T -1/2 and a conventional SDF based on the trans- formed data. Note that in this case the whitened spectrum is the envelope of the spectra of the real noise and of the training images. A least square approach may again be preferred to cope with a large number of examples. In this case all available images are used to estimate T but only a subset of them is used to build the corresponding SDE Experiments have been reported using a white noise of tunable energy to model the intraclass variability (12) E = ~ In(k)lZmax(l,~,(k)2,..., I~,s(~)12,,~). (40) k Adding white noise limits the emphasis given to high frequencies, reducing the sharpness of the correlation peak and increasing the tolerance to small variations of the templates (see Figs 5 and 6). A comparison of different filters is reported in Fig. 7. The effect of non- linear processing emphasizing the high frequencies to obtain a sharp correlation peak is reported in Fig. 8. Another way of controlling the intraclass performance is that of modeling the correlation peak shape. (1°'13) As already mentioned, the shape of the correlation peak is expected to be important both for its detection and for the requirements imposed on the filter which can impair its ~~ 100 .~ 100 25 ~.t ~5.OJ°O - ~~0 .~ r Fig. 5. Using an increasing amount of added white noise the emphasis given to the high frequency is reduced and the resulting filter response approaches that of the standard MSE
`
`

`
`758 R. BRUNELLI and T. POGGIO Fig. 6. The output of the correlation with an SDF computed using the spectral envelope of 10 training images and different amounts of white noise (left: ~- 1, middle ~=5) compared to the output of normalized cross-correlation using one of the images used to build the SDF but without any spectral enhancement. The darker the image the higher the corresponding value. Fig. 7. The output of the correlation with an SDF computed using the spectral envelope of 20 training images as whitening preprocessing. Left: the normal SDF (20 examples). Right: a least square SDF with 6 templates (20 examples). The darker the image the higher the corresponding value. The least square SDF exhibits a sharper response using the same whitening filter. ability to correlate well with patterns even slightly dif- ferent from the ones used in the training. Let us denote with F(k) the required shape of the correlation peak. The shape of the peak can be constrained by minimizing the squared deviations of its output from the required shape F: N d Es = ~_, ~ Ig(k)*~g(k) - F(k) 2, i=1 k=l (41) where, for instance, f(x) = exp(-xZ/2~r 2) is a Gaussian amplitude function. By switching to matrix notation, the resulting energy can be expressed as Es -- H+DH + F+F - H+AF - F+A+H, (42) where A is a diagonal matrix whose elements are the sum of the components of ~i and D is a diagonal matrix whose elements are the sum of the squares the components of ~i. The first term in the RHS of equation (42) corre-
`
`

`
`Template matching: method spatial filters and beyond 759 I00 7 ! r ~ 28 .c #°~°° ~0.~" X 0.0 Fig. 8. Nonlinear processing can be employed. The figure represents the result of preprocessing the image to extract the local image contrast (intensity value over the average value in a small neighborhood). This kind of preprocessing emphasizes high frequencies and results in a sharp correlation peak. sponds to the average correlation energy of the different patterns see equation (30). We suggest the use of the spectral envelope T instead of D, employed in the original approach, thereby minimizing the following energy: E' s = H+TH + F+F - H+AF - F+A+H > Es. (43) The minimization of Es subject to the constraints of equation (29) can be done again using the Lagrange multiplier and is found to be H = T-Ix(X+T-1X)-Idu (44) + T 1AF - T-tX(X+T-1X)-IX+T-IAF. These filters provide a controlled, sharp correlation peak subject to the constraints on the filter output, the required correlation peak shape and the reduced variance to the noise. In our experiments the Fourier domain was used to compute the whitening filters. They were then trans- formed to the spatial domain where a standard correlation was computed after their application. An approach using only computations in the space domain can be found in reference (8). 5. NONORTHOGONAL IMAGE EXPANSION AND SDF In this section we review an alternative way of looking at the problem of obtaining sharp correlation peaks, namely the use of nonorthogonal image expansion. (25'26) Matching by expansion is based on expanding the signal with respect to basis functions (BFs) that are all trans- lated versions of the template. Such an expansion is feasible if the BFs are linearly independent and complete. It can be proven that self-similar BFs of compact support are independent and complete under very weak condi- tions. Suppose one wants to estimate the discrete d- dimensional signal g(x) by a linear combination of basis functions @(x): d g'(x) = Z ciOi(x)' (45) i=1 where @ (x) now represents the ith circulated translation of ~b. The coefficients are estimated by minimizing the square error of the approximation I g - g'l 2. The approx- imation error is orthogonal to the basis functions so that the following system of equations must be solved: d Z ((~)1, Oj)Cj = (~, 01) j--I • " (46) d j=l If the set of basis functions is linearly independent the equations give a unique solution for the expansion coef- ficients. If we consider the advanced SDF for the case of no noise, single training image and working in the spatial domain, (s) we have that the corresponding filter can be expressed as h = (q~iTq~)-l~, (47) where the columns of matrix . are the circulated basis functions @. The output of the correlation is then given by ~h =C = ~T lq~. (48) The solution of the system (46) can be expressed as: c = q~T-1 ~, (49) which is clearly the same. In the case of no noise the resulting expansion is c=(0 ..... 0,1,0 ..... 0) with a single 1 at the location of the signal. The idea of expansion matching is also closely related to correlation SDFs ¢4) where multiple shifted templates were explicitly used to shape the correlation peak. Let us consider a set of templates obtained by shifting the original pattern (pos- sibly with circulation) on the regular grid defined by the image coordinates. We can require that the correlation value of the original pattern with its shifted versions be 1 when there is no shift and 0 for every nonnull shift. This corresponds to a filter whose response is given by c=(0 ..... 0,1,0 ..... 0) as previously described.
`
`

`
`760 R. BRUNELLI and T. POGGIO 6. OTHER PROJECTION APPROACHES The whole idea of projection Synthetic Discriminant Functions is to find a direction onto which the projections of the different signals have predefined values. A typical image with 256×256 pixels is projected, for recognition purposes, onto a single direction in this high dimensional space. Another approach is to project the signal to be recognized onto a linear subspace. (16-2°'27) Let us first assume that the patterns of each of the classes to be discriminated belongs to different linear subspaces. For each class it is then possible to determine an orthogonal transformation which diagonalizes the covariance ma- trix. The elements of the transformed basis are the eigenvectors of the covariance matrix and are called principal components. They can be sorted by decreasing contribution to the covariance matrix, as represented by the corresponding entry in the diagonal covariance ma- trix. (22) The number of vectors in the basis is equal to the minimum between the number of available class pattern and the dimensionality of the embedding space. Each pattern in the class can usually be described by using only the most important components. The resulting restricted basis spans a linear subspace in which the patterns of the represented class can be found. Each possible pattern ~h can be projected onto the set of principal components and can be described as the sum of its projection qSc, plus an orthogonal residual ~bR,: = ,PL, + ~R~ + (~i), (50) where i identifies the class and (4~i) is the corresponding centroid. A comparison with the usual technique of computing the distance from a single pattern (e.g. the centroid) is reported in Fig. 9. ~" t~ L ~i ~> An important class of objects spanning a linear space is given by the orthographic projections of rigid sets of points when looked at from different positions. (28'z9) Different objects span different six-dimensional linear spaces. This can be used to recogn