Pattern Matching Based on a Generalized Transform[Final Report]Ram RajagopalNational Instruments11500 N. Mopac Expwy., Building B,Austin, TX [email protected] a two-dimensional pattern matching problem, a known template image has to be located in anotherimage, irrespective of the template’s position, orientation and size in the image. One way to accomplishinvariance to the changes in the template is by forming a set of feature vectors that encompass all thevariations in the template. Matching is then performed by finding the best similarity between thefeature vector extracted from the image to the feature vectors in the template set. In this report weintroduce a new concept of a Generalized Transform. The Generalized Transform offers a relativelyrobust and extremely fast solution to the described matching problem. An algorithm for scale invariantpattern matching based on the Generalized Transform is introduced.1. IntroductionPattern matching is an important technique in digital image processing. The evolution ofcomputer technology has enabled many practical applications based on pattern matching, especially inindustrial automation. An example of a process to be automated is the visual inspection of circuitboards. Typically, we are interested in finding a missing component in circuit boards on a productionline. The procedure is based on a digital picture of the circuit board. In such image, one could searchfor a predefined template corresponding to the desired component. So given a test image I,weareinterested in finding the location of the template Itwithin this image. Typical test and template imagesare given in Figure 1.To properly define a pattern matching problem, all the valid transformations of the templateshould be clearly specified. In a majority of the applications, the template will appear shifted, rotatedand scaled in the test image.Approaches for solving the proposed problem can be divided into two categories: correlationbased solutions and image understanding solutions [BB82, GMO99]. Correlation based solutionspredominantly use a cross correlation to find the potential locations of the template, whereas imageunderstanding solutions attempt to model the objects observed in the template.TemplateImage ItTest Image IFigure 1: Pattern matching applicationFigure 2: Classic CorrelationIn this paper we present a statistical sampling approach to pattern matching. We also introducea new generalized transform and some of its properties. This transform provides the basis for a robustreal-time scaling invariant pattern matching algorithm.2. Classic Correlation Based Pattern MatchingTraditional pattern matching techniques include normalized cross correlation [BB82] and pyramidalmatching [CC98]. Normalized cross correlation is the most common way to find a template in animage. The following is the basic concept of correlation: Consider a sub-image w(x,y) of size K × Lwithin an image f(x,y) of size M × N, where K × M and L × N. The normalized correlation betweenw(x,y) and f(x,y) at a point (i,j) is given by21101022110102_00__)),(),(()),(()),(),()(),((),(ÿ−++ÿ−−++−=−=−=−=−===LxKyLxKyxyjifjyixfwyxwjifjyixfwyxwjiCwhere i = 0,1, … M –1,j=0,1…N–1, w (calculated only once) is the average intensity value of thepixels in the template w. The variable),(jifis the average value of f in the region coincident with thecurrent location of w. The value of C lies in the range –1 to 1 and is independent of scale changes in theintensity values of f and w.Figure 2 illustrates the correlation procedure. Assume that the origin of the image f is at the top leftcorner. Correlation is the process of moving the template or sub-image w around the image area andcomputing the value C in that area. The maximum value of C indicates the position where w bestmatches f. Since the underlying mechanism for correlation is based on a series of multiplicationoperations, the correlation process is time consuming. With new technologies such as MMX,multiplications can be done in parallel, and the overall computation time can be reduced considerably.The basic normalized cross correlation operation does not meet speed requirements for manyapplications [BB82].Normalized cross correlation is a good technique for finding patterns in an image as long as thepatterns in the image are not scaled or rotated. Typically, cross correlation can detect patterns of thesame size up to a rotation of 5° to 10° [NW99]. Extending correlation to detect patterns that areinvariant to scale changes and rotation is difficult. Approaches based on multidimensional DiscreteFourier Transforms and Principal Component Analysis have been proposed [UK97]. But they are notvery adequate, due to the slowness of the learning phase and requirements for non-integer operations[UK97].3. Statistical Sampling Based Pattern MatchingLow discrepancy sequences have been successfully used in a variety of applications that requirespatial or multidimensional sampling [C86, NW99]. A low discrepancy sequence can be described as asequence that samples a given space as uniformly as possible. Thus, the density of points in relation tothe space volume is almost constant.Images typically contain a lot of redundant information. In a correlation based pattern matching atemplate image could be subsampled according to a two-dimensional low discrepancy sequence[NW99]. A set S of N coordinates of the template could be formed and the correlation computed onlyin relation to these coordinates. Such an algorithm has been proposed in [NW99b].The algorithm has two stages. In the first, possible matches are computed based on a subsampledcorrelation. A threshold in the correlation value determines the exclusion or inclusion of a match. In thesecond, the edge information of the template is used to accurately locate the potential match indicatedby the first stage. Typically, for a 100 X 100 template, a set of 61 points in enough to provide a robustcorrelation basis (160 times faster) for the first stage candidate list generation procedure [NW99].In a pattern matching application where only shift invariance is desired, a Halton low discrepancysequence can be used [C86, NW99b]. Typically, 61-70 points from the template should be selected.5. Generalized TransformAssume that N vectors (signals) of length N are given. Denote these vectors byif . A matrix Acan be defined, such that10fAf = ,21fAf