Image analysis – Pattern recognition – Template matching
Reexamination Certificate
2001-04-10
2004-10-19
Mariam, Daniel (Department: 2623)
Image analysis
Pattern recognition
Template matching
Reexamination Certificate
active
06807305
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of signal processing, and more particularly to pattern matching and signal characterization.
DESCRIPTION OF THE RELATED ART
A great variety of systems may be characterized by the property that they receive a signal and attempt to match the received signal to one of a series of candidate or template signals. Such signal or pattern matching is common in diverse fields such as telecommunications, wireless telecommunications, radar, machine vision and control, system automation, manufacturing, quality control, acoustics, optics, measurement, filtering, data analysis, and others. Signal types may include 1-dimensional (1-D) signals, 2-D signals, such as images, as well as 3-D and higher dimensional data sets or signals. Signals may also be either analog or digital signals.
The presence of noise or other distortions in the received signal complicates the task of matching or characterizing the received signal. In many systems, the signal matching task may be greatly aided by the use of transforms, such as the well known Fourier Transform. The Fourier Transform may be used to recast the signal data into the frequency domain, which can make certain characteristics or underlying structure more apparent, and thus easier to characterize.
For example, in the field of telecommunications the signal is usually a time-varying voltage or current. Fourier theory teaches that such signals may be represented as a superposition of sinusoidal signals of various frequencies and phase values. The Fourier Transform, in essence, decomposes or separates a signal waveform or function into sinusoids of different frequency, amplitude, and/or phase, which sum to the original waveform, i.e., the Fourier transform identifies or determines the different frequency sinusoids and their respective amplitudes that can be combined to represent the original signal. Understanding this aspect of a signal is important in determining how the signal will behave, e.g., when it passes through filters, amplifiers and communication channels. Fourier analysis provides a means to determine the frequency spectrum of a given signal, i.e., to determine the frequency content of a signal. Even discrete digital communications which use 0's or 1's to send information still have frequency content. The Fourier Transform may be used to move the signal data from the time domain to the frequency domain where the spectral content of the signal may be easily analyzed or compared to other transformed signals.
In one signal matching approach, the candidate signals are shifted and noise-perturbed versions of each other. A signal generally comprises a series of values, and thus may be thought of as a vector. For example, the candidate signals may comprise an initial signal or vector, and a sequence of signals or vectors which are each phase shifted some amount from its predecessor. In many applications it is necessary to analyze a received input signal to determine which of the candidate signals or vectors most closely matches the input signal. One example of this process is shown in
FIGS. 1A and 1B
and described as follows.
FIGS.
1
A and B—Signal Matching (Prior Art)
FIGS. 1A and 1B
illustrate a prior art method of determining a “best fit” or “closest match” between an input signal of interest and a set of N candidate signals f, wherein the candidate signals are shifted versions of each other. When the set of candidate signals are shifted versions of each other, then the signals will exhibit properties whereby Fourier techniques may be used in making the determination.
FIG. 1A
illustrates a preprocessing technique that may be used to preprocess the set f of candidate signals prior to receipt of the signal of interest. This preprocessing performed in
FIG. 1A
enables a faster and hence more “real time” determination of the closest candidate signal in the set of candidate signals f when the input signal is received as shown in FIG.
1
B.
As shown in
FIG. 1A
, in step
102
the set of candidate signals f may be stored in a memory. As mentioned above, the set of candidate signals f comprises an initial signal f
0
and shifted versions of the signal f
0
, referred to as f
1
, f
2
, . . . f
N-1
. In step
104
the method may include selecting a frequency, e.g., the k
th
frequency, that is present in each of these candidate signals. Step
104
may also be stated as selecting the k
th
row of a matrix W
N
wherein the matrix W
N
comprises the standard Fourier matrix. In step
106
the preprocessing method calculates the value of the Fourier transform at the k
th
frequency for a first candidate signal in the set of candidate signals. This may be performed by applying the Fourier transform, e.g. an FFT, on the first candidate signal f
0
and using the value produced at the respective k
th
frequency for the Fourier transform calculation. Alternatively, this computation may be performed by computing the vector product between the k
th
row of the matrix W
N
and the first candidate signal according to the equation
F
k
=W
N
(
k
)*
f
0
,
In step
108
the method computes and stores the values of the Fourier transform at the k
th
frequency for each of the shifted versions of the first signal f
0
. The values of the Fourier transform at the k
th
frequency may be referred to as &agr;(n), or alpha(n). The values of the transformation at the k
th
generalized frequency for the shifted versions of the first signal may be computed according to the expression:
&agr;(
n
)=exp(2
&pgr;n/N k
)·
F
k
, where
F
k
is calculated above in
106
.
This expression uses the shift invariant property of the Fourier transform to substantially reduce the number of calculations required, i.e., the fact that in the frequency domain the candidate signals are shifted versions of the first signal f
0
allows the Fourier transforms of the remainder of the candidate signals to be computed easily from the Fourier transform of the first candidate signal. Alternately, the values of the transformation at the k
th
generalized frequency for the remaining set of N candidate signals may be computed by applying the Fourier transform at the k
th
generalized frequency to each of remaining candidate signals, as was applied to the first candidate signal in
106
.
The preprocessing performed in
FIG. 1A
allows a faster determination when an input signal of interest is received.
FIG. 1B
illustrates the method performed when an input signal of interest g is received to determine the closest match of the set of candidate signals with the input signal g. As shown, in step
122
the input signal of interest g is received. In step
124
the method calculates the Fourier transform, e.g., using an FFT of g at the k
th
frequency. The value of the Fourier transform of g at the k
th
frequency may be referred to as alpha bar. The alpha bar value may also be computed according to the equation
{overscore (&agr;)}=
W
N
(
k
)*
g,
where W
N
(k) refers to the k
th
row vector of the matrix W
N
.
In step
126
the method determines the best match between {overscore (&agr;)} and the &agr;(n) values corresponding to each of the candidate signals. This operates to determine the closest candidate signal to the input signal of interest g. In step
128
this closest candidate signal may then be output as a final result.
As noted, the method described in
FIGS. 1A and 1B
may be used when the set of candidate signals are shifted versions of each other, wherein this characteristic allows the use of Fourier transform techniques to greatly simplify and speed up the analysis. However, when one or more of the signals in the set of candidate signals are not shifted versions of each other, e.g., are uncorrelated, then the method described in
FIGS. 1A
and
1
B cannot be used. The problem of attempting to match a received input signal of interest with one of a set of candidate or template signals, wherein two or more of the signals comprised in the set of candidate or template signals are uncorrelated with each other,
Nair Dinesh
Rajagopal Ram
Schmidt Darren
Wenzel Lothar
Hood Jeffrey C.
Mariam Daniel
Meyertons Hood Kivlin Kowert & Goetzel P.C.
National Instruments Corporation
Williams Mark S.
LandOfFree
System and method for image pattern matching using a unified... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for image pattern matching using a unified..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for image pattern matching using a unified... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3263407