Method of multivariant intraclass pattern recognition

A method of recognizing different perspective views or images (i.e., multivariant views) of the same object (i.e., intraclass patterns). Each intraclass pattern, or different representation of the same object, is described as an orthonormal basis function expansion, and a single averaged matched spatial filter is produced from a weighted linear combination of these functions. The method eliminates the multiple matched spatial filters, and the extensive postprocessing of the matrix output from a multichannel correlator, which are used in the prior art.

BACKGROUND OF THE INVENTION 
This invention relates to a method of recognizing a pattern and more 
particularly, of recognizing different perspective views or images (i.e., 
differences in tilt and/or rotation and/or magnification, hereinafter 
referred to as "multivariant views") of the same object (hereinafter 
referred to as "intraclass patterns"). 
On most pattern recognition problems, multivariant views or images of the 
intraclass pattern type must be recognized, and discrimination between 
multiobjects (i.e., different, but similar, objects) must also be 
maintained. Such pattern recognition problems arise in missile guidance, 
product line inspection, and elsewhere. 
Prior approaches to the multivariant intraclass pattern recognition 
problem, and to the multiobject pattern recognition problem, have utilized 
multiple matched spatial filters (hereinafter a single said filter will be 
referred to as a "MSF"), extensive postprocessing of the matrix output 
from a multichannel correlator, and other non-MSF techniques. 
What is needed in the art is a method of recognizing multivariant views of 
intraclass patterns, while maintaining discrimination between 
multiobjects, without requiring multiple MSFs or extensive postprocessing. 
SUMMARY OF THE INVENTION 
The instant invention fulfills the aforementioned need; and, thereby, 
constitutes a significant advance in the state-of-the-art. 
In essence, we avoid the prior art necessity of using multiple MSFs and of 
extensive postprocessing by incorporating postprocessing into the MSF 
itself and by basing the average MSF on the correlation matrix. 
Accordingly, the principal object of this invention is to provide a method 
of recognizing multivariant views of intraclass patterns, without loss of 
discrimination between multiobjects. 
Another object of this invention is to attain the hereinbefore described 
pattern recognition by retaining the simplicity and real-time and parallel 
processing features of the well-understood optical plane correlator 
system, which said system will be reviewed, shown, and described later 
herein. 
Still another object of this invention is to attain the hereinbefore 
described pattern recognition by utilizing the control, dynamic range, and 
flexibility of digital processors, together with the aforesaid optical 
plane correlator system. 
A further object of this invention is to allow use of preprocessing, such 
as edge enhancement, by weighted MSF synthesis. 
These objects of this invention, as well as other objects related thereto, 
will become readily apparent after a consideration of the description of 
the invention, together with reference to the contents of the Figures of 
the drawing.

DETAILED DESCRIPTION OF THE INVENTIVE METHOD 
As to the use of the optical frequency plane correlator 
With reference to FIG. 1, therein is shown a well known (optical) frequency 
plane correlator system 10. It is here to be noted that, although the 
correlator 10 is prior art, our manner of use of it is new. In this 
system, the input object f(x) is placed at P.sub.1 and a MSF H*(u) at 
P.sub.2. (Capital letters denote the Fourier transform of the 
corresponding space functions.) One-dimensional functions are used only to 
simplify notation. The Fourier transform, F(u) of f(x), is incident on 
P.sub.1, and the light distribution leaving P.sub.2 is FH*. At P.sub.3, 
the Fourier transform of this product of two Fourier transforms is 
produced, and hence the desired correlation f * h results. 
Holographic techniques are used to produce the MSF by recording the 
interference of the Fourier transform of the function h and an off-axis 
plane wave reference beam at P.sub.2. By adjusting the spatial frequency u 
at which the beam balance ratio K (equal to the ratio of the intensities 
of the reference and signal beams) is unity, a weighted MSF results in 
which different object spatial frequencies can be emphasized. This 
technique has been shown to be of use in reducing the correlation 
degradations due to expected within-class object differences. 
In our multivariant intraclass pattern recognition method to be described, 
an intraclass reference h is formed off line by digital computer means. 
The MSF H* is then recorded on film and is placed at P.sub.2. 
As to hyperspace and basis functions 
Our multivariant intraclass pattern recognition method utilizes a 
hyperspace (i.e., a multidimensional vector space) description of the 
intraclass and multiobject functions. Accordingly, the following is a 
brief review of this area and the use of orthonormal basis function 
expansion for the intraclass pattern recognition problem. 
We denote the input image by f, the intraclass object functions to be 
recognized by g, and the average filter by h. We assume that K different 
inputs {f.sub.k } and N different orientations {g.sub.n } of the object 
function g can occur. The pattern recognition task is to recognize f if it 
belongs to the set {g.sub.n } and to reject it otherwise. For simplicity, 
we assume that the {g.sub.n } are different orientations of g and that the 
{f.sub.k } belong to the set {g.sub.n }. Neither of these assumptions is 
essential to the general theory. 
We begin by expanding f and g in a set of orthonormal basis functions 
{.phi..sub.j }: 
##EQU1## 
where 
EQU .intg..phi..sub.j (x).phi..sub.i (x)dx=.delta..sub.ji (3) 
The set of basis functions {.phi..sub.j } establishes the set of expansion 
coefficients a.sub.j and b.sub.j that specifies f and g. We can thus 
represent f or g as a vector 
EQU f=(a.sub.1,a.sub.2, . . . ,a.sub.k), (4) 
in a multidimensional vector space (hyperspace) whose axes are the basis 
function .phi..sub.j. In terms of these expansions, the correlation of f 
and g can be described by 
##EQU2## 
The value of the correlation at the registration point .tau.=0 reduces to 
the simple summation of the products of the coefficients as in Eqs. (5). 
In this formulation, we see that the correlation of f and g has the 
special significance of the dot product. 
When the various vectors corresponding to the {f.sub.k } or {g.sub.n } set 
of input objects are plotted as pointed in this hyperspace, discriminant 
surfaces can be drawn that enable intraclass objects to be grouped 
together and separated from multiobject false input. The shape of these 
discriminant hypersurfaces defines the average MSF to be used. The simple 
discriminant surfaces such as lines (hyperplanes) or circles 
(hyperspheres) are preferable. They correspond to f.multidot.h=constant or 
f.multidot.f=constant, respectively. In the first case, a single averaged 
filter h suffices. In the second case, requiring the autocorrelation of 
the input to lie within the specific range is an adequate discriminant. In 
the more general case, several averaged filters may be necessary to 
realize more complex discriminant hypersurfaces. 
For a simple intraclass case in which either of the two vectors f.sub.1 
=(a.sub.11,a.sub.12) and f.sub.2 =(a.sub.21,a.sub.22) are to be recognized 
and all other inputs rejected, the hyperplane connecting f.sub.1 and 
f.sub.2 is described by f.multidot.h=constant. In this case, h is a vector 
perpendicular to the plane, and the constant is (g.multidot.g). The 
average filter is thus a specific linear combination of f.sub.1 and 
f.sub.2, each of which is another linear combination of the basis 
functions {.phi.}: 
##EQU3## 
As to the basis function and average filter computation 
We now consider the procedure by which the basis functions {.phi..sub.j } 
and the linear weights c.sub.j can be found and thus the average filter h. 
For this case, we consider the recognition of N reference functions 
{g.sub.n } described by Eq. (2). We describe the filter as a linear 
combination of the reference functions 
##EQU4## 
The intraclass pattern recognition correlation outputs can then be 
described by 
##EQU5## 
The objective is to find {.phi..sub.j }, b.sub.nj, then c.sub.j and 
finally h so that R.sub.n yields acceptable correlation performance. 
We require shift invariance and assume that the N correlations R.sub.n peak 
at .tau.=0 for all registered inputs. This co-location feature requires us 
to shift each g.sub.n or .phi..sub.j to the correct input location when we 
form h. Such techniques are acceptable since this an off-line filter 
synthesis procedure. It also allows us the added flexibility of weighting 
the different portions of each g.sub.n differently when forming h. 
We first form the unnormalized cross-correlation matrix 
EQU R.sub.ij =g.sub.i *g.sub.j (9) 
of all pairs of possible input functions {g.sub.n }. This R.sub.ij has 
also been referred to as the autocorrelation matrix. If a Gram-Schmidt 
expansion for the .phi..sub.j is used, the .phi..sub.j can be found from 
the R.sub.ij in Eq. (9) using 
##EQU6## 
where the k.sub.n are normalization constants that are functions of the 
R.sub.ij and where the C.sub.nj are linear combinations of the R.sub.ij 
with known weighting coefficients. With .phi..sub.j determined as above, 
the coefficients b.sub.nj in Eq. (8), or equivalently the individual 
b.sub.j values in Eq. (2), are directly obtainable. If we then require all 
N correlations R.sub.n in Eq. (8) to be equal, we can solve Eq. (8) for 
the weights c.sub.j and thus obtain the desired average filter function h 
in Eq. (7). 
As to experimental confirmation 
The specific multivariant intraclass pattern recognition problem chosen to 
demonstrate the use of our method was the recognition of a M-60 tank 
independent of its orientation. In this case, the functions {g.sub.n } are 
different orientational views of the tank. Because of the excellent target 
signature information that they provide, IR imagery of the tank target was 
used. Although considerable advances in IR sensors have occurred, little 
attention has been given to the pattern recognition techniques required 
for IR imagery. The IR tank imagery used was taken in the 8-12-.mu.m IR 
window because of the higher and more reliable radiance image variances 
possible in this region. 
The R.sub.ij correlation matrix was produced using both the frequency plane 
correlator system of FIG. 1 and by digital techniques. All correlations 
were also obtained using weighted MSFs with different u' spatial 
frequencies. From these tests, the optimum u' spatial frequency band was 
found to be centered at u'=2.25 cycles/mm. In the digital computations of 
R.sub.ij, this weighted MSF synthesis was simulated by bandpass filter 
preprocessing of each image with a digital filter centered at u'. This is 
similar to the edge enchancement preprocessing operation used in 
multisensor image pattern recognition. For the experiments performed, IR 
images of the tank at seven different orientations were used. The R.sub.ij 
unnormalized correlation matrix is shown in Table I. 
TABLE I 
______________________________________ 
EXPERIMENTALLY OBTAINED UNNORMALIZED 
CORRELATION MATRIX R.sub.ij 
Aspect 
1 2 3 4 5 6 7 
______________________________________ 
1 2.42 0.29 0.15 -0.24 -0.09 -0.12 0.10 
2 0.29 2.19 0.10 -0.14 -0.10 -0.07 0.06 
3 0.15 0.10 4.95 0.02 -0.35 -0.30 0.03 
4 -0.24 -0.14 0.02 1.51 0.04 -0.02 0.04 
5 -0.09 -0.10 -0.35 0.04 3.87 0.03 0.02 
6 -0.12 -0.07 -0.30 -0.02 0.03 3.93 0.02 
7 0.10 0.06 0.03 0.04 0.02 0.02 0.22 
______________________________________ 
A Gram-Schmidt expansion was used for the basis functions. The procedure 
outlined in Eq. (10) then yielded the desired .sub.j and b.sub.nj values 
as shown in Table II. As seen in Table II, the resultant matrix has large 
diagonal and small off-axis values. 
TABLE II 
______________________________________ 
DIGITALLY COMPUTED COEFFICIENTS 
IN THE GRAM-SCHMIDT 
EXPANSION OF THE BASIS FUNCTIONS 
g.sub.1 g.sub.2 g.sub.3 g.sub.4 
g.sub.5 
g.sub.6 
g.sub.7 
______________________________________ 
.phi.1 
0.64 -- -- -- -- -- -- 
.phi.2 
-0.08 0.68 -- -- -- -- -- 
.phi.3 
-0.02 -0.01 0.44 -- -- -- -- 
.phi.4 
0.07 0.04 -0.00 0.82 -- -- -- 
.phi.5 
0.01 0.02 0.03 -0.01 0.51 -- -- 
.phi.6 
0.02 0.01 0.02 0.01 -0.00 0.50 -- 
.phi.7 
-0.08 -0.06 -0.01 -0.07 -0.01 -0.01 2.1 
______________________________________ 
The coefficients c.sub.j were then computed, and the expression for the 
average filter h in terms of the basis functions .phi..sub.j and the 
reference objects {g.sub.n } was then obtained as described hereinbefore. 
The resultant average filter, 
EQU h=0.64.phi..sub.1 +0.60.phi..sub.2 +0.42.phi..sub.3 +0.93.phi..sub.4 
+0.57.phi..sub.5 +0.59.phi..sub.6 +1.85.phi..sub.7, (11) 
was then digitally calculated and constructed. It was then correlated with 
all seven input image aspects {g.sub.n }. Cross-sectional scans through 
one of the output correlation peaks are shown in FIG. 3. In all cases, 
high quality correlation peak intensities resulted with sharp correlation 
peaks and good correlation surfaces. This verified the use of this method 
in multivariant intraclass pattern recognition. 
PERFORMANCE OF THE METHOD AND USE OF THE APATUS 
The performance of the fundamental steps of our method FIG. 2, and the use 
of the apparatus 10, FIG. 1, can be easily ascertained by any person of 
ordinary skill in the art from the foregoing description, coupled with 
reference to the Figures of the drawing and Table I and II herein. 
For others, the following simplified explanation is given. With reference 
to FIG. 2, P.sub.1, P.sub.2 and P.sub.3 are image planes, i.e., sheets of 
photographic film. The image of an object to be recognized (e.g., the 
hereinbefore mentioned tank) appears on P.sub.1. P.sub.2 includes a 
matched filter, i.e., a conjugate Fourier transform of a reference 
function, with this function representing the object to be recognized. 
P.sub.3 indicates if such an object has been recognized. 
Accordingly, the procedure for the use of the correlator 10, FIG. 1, is as 
follows: an image of the object appears at P.sub.1 ; L.sub.1 performs a 
Fourier transform of the image at P.sub.1 ; the Fourier transform from 
L.sub.1 is multiplied by the MSF at P.sub.2 ; L.sub.2 integrates over the 
multiplication; and, if any correlation between the images of P.sub.1 and 
of P.sub.2 exists, a spot of light or some other indication appears at 
P.sub.3 to signify that an object, whose reference function appears at 
P.sub.2, has been recognized. 
In essence, therefore, the invention concerns the use of a particular 
matched filter at P.sub.2 for recognizing different perspective views of 
the same object, and for maintaining discrimination between different but 
similar objects. 
More specifically and succinctly, our inventive method comprises the 
fundamental steps of: 
Firstly, obtaining a synthetic discriminant function for use in a pattern 
recognition hyperspace (i.e., a multidimensional vector space) formulation 
by using a Gram-Schmidt or Karhunen Loeve or other orthonormal basis 
function expansion technique; and 
Then, relating that discriminant function to a MSF in the optical 
correlator 10, FIG. 1. 
Discriminant surfaces may be drawn from the function, and the shape of 
these surfaces defines the MSF. The discriminant surfaces may be formed 
off-line by digital computer means; recorded on film; and, placed at 
P.sub.2, FIG. 1. 
With reference to FIG. 2, therein are shown, with greater specificity and 
in a flow-type diagram, the above-mentioned fundamental steps of our 
inventive method, wherein: 
f.sub.1 . . . f.sub.n comprise the training set, i.e., an adequate number 
of multivariant views of the interclass pattern; 
SDFG is the synthetic discriminate function generator; 
g is the synthetic discriminate function; 
FT are Fourier transforms boxes; 
G is the matched filter; 
* is the conjugate; 
f is the space function; 
F is the Fourier transform of f; and 
FT.sub.-1 is the inverse Fourier transform box. 
Accordingly, the steps of our inventive method also may be stated as 
comprising the steps of: 
Firstly, obtaining a training set, i.e., f.sub.1 . . . f.sub.n. 
Next, obtaining a synthetic discriminant function, i.e., g. 
Lastly, relating that discriminant function g to MSF in the optical 
correlator 10, FIG. 1. 
CONCLUSION 
It is abundantly clear from all of the foregoing, and from the contents of 
the Figures of the drawing, that the stated objects of the invention, as 
well as objects related thereto, have been achieved. 
It is to be noted that, because of our teachings herein, it may occur to 
others of ordinary skill in the art that, in appropriate particular 
circumstances, the number of the basic and fundamental steps of our 
inventive method can be increased, decreased, or otherwise varied, and/or 
that their sequence can be changed. In this regard, it is also to be noted 
that, in spite of any variations in the number or sequence of the steps of 
our method, the same disclosed and desired end results will be obtained 
nevertheless.