Browse Prior Art Database

Means for Pattern Matching Amplitude-Coded Data

IP.com Disclosure Number: IPCOM000114075D
Original Publication Date: 1994-Nov-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 2 page(s) / 92K

Publishing Venue

IBM

Related People

Li, C-S: AUTHOR [+2]

Abstract

Matched filter operations of signals are typically used for phase, frequency, and amplitude-coded information streams. When used for amplitude-coded streams, the information is normally in the form of binary valued data. That is, the signal is present or not present, or the phase is shifted 180 degrees, or the frequency is shifted. We wish to do match filtering on data that is amplitude coded into many different quantized levels. Typical of such data is the encoding of pixels of digital images. Multilevel amplitude encoding presents an obstacle for pattern matching, because high amplitude responses can swamp out recognition of lower amplitude information.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Means for Pattern Matching Amplitude-Coded Data

      Matched filter operations of signals are typically used for
phase, frequency, and amplitude-coded information streams.  When used
for amplitude-coded streams, the information is normally in the form
of binary valued data.  That is, the signal is present or not
present, or the phase is shifted 180 degrees, or the frequency is
shifted.  We wish to do match filtering on data that is amplitude
coded into many different quantized levels.  Typical of such data is
the encoding of pixels of digital images.  Multilevel amplitude
encoding presents an obstacle for pattern matching, because high
amplitude responses can swamp out recognition of lower amplitude
information.

      (*)  describes a correlation mechanism that minimizes the
mean-square error of a pattern matching, and thus deals effectively
with color-encoding problem.  The means used by [*]  is based on a
correlator implemented by optical means.  We discuss an efficient
all-digital implementation of a similar correlator.

      The problem is match a pattern p(n), n%=%0,1,2,...,k-1 to an
image y(n), n%=%0,1,2,...,N-1 to find the point n sub 0 at which the
match is closest in the mean square sense.  The point n sub 0 is the
point at which the following sum is minimized:
  sum from <0> to <k-1> (p(n) - y(n+n sub 0)) sup 2 ,%%%%%%%
  <k le N>,  <0 le n sub 0 le N - k>.
  eqno (1)

By expanding Eq.  (1), (*) shows that it reduces to correlation
operations.  He obtains
  sum from <0> to <k-1> (p(n) - y(n + n sub 0)) sup 2
  =
  sum from <0> to <k-1>
  p(n) sup 2
  +
  sum from <0> to <k-1>
  y(n + n sub 0) sup 2
  -
  sum from <0> to <k-1>
  p(n) y(n+ n sub 0)
  eqno (2)

      Each of the three terms is a correlation function.  The first
is an autocorrelation of the pattern with itself, and is a fixed
constant for each pattern.  The second is a an autocorrelation of the
image with itself over a window of k points starting at position n
sub 0.  This depends on the number of points k in a pattern, which is
pattern dependent.  The third term is the cross-correlation of the
pattern with the image.

      For efficient computation of the three terms, consider
processing in the frequency domain.  It is well-known that the
cross-correlation in Eq.  (2) can be computed by taking the inverse
Fourier transform of the following product function Z(j) = P(j)Y(j)
where P(j) and Y(j) are respectively the N-point Fourier transforms
of p(n) and y(n).  The cost of computing the cross correlation is on
the order of kN whereas the cost of computing the same function by
means of transforms is on the order of N + 3 N log N .  The dominant
cost is 3 N log N, which is the cost of taking two forward and one
inverse transforms.  Note that as k grows toward N, the cost of the
cross correlation...