 |
Claims  |
|
|
We claim:
1. A pre-edit signalling system responsive to an electrical signal analog
of a scanned image for indicating the probable absence or presence of a
non-fingerprint region of such image, said system comprising
a two-dimensional sequency function transform analyzer responsive to a
binary-coded image signal for identifying discrete frequency terms
occurring within a preselected bandwidth corresponding to a spatial
frequency region associated with descriptions of a fingerprint image; and
logic means responsive to said bandwith limited transform analyzer for
further identifying the relative energy level of the bandwidth-limited
spectral content of the binary-coded image signal as an indication of the
inclusion of a non-fingerprint region within the scanned image represented
by said binary-coded signal analog.
2. The device of claim 1 in which said logic means includes multiple level
thresholding means responsive to the total energy represented by the
output of the bandwidth limited transform analyzer for indicating a degree
of probability that the scanned image represents a non-fingerprint region.
3. The device of claim 1 in which said logic means comprises:
means for determining the total energy E represented by the discrete
frequency term output of the bandwidth limited transform analyzer, as the
signal sum of selected signals in the output of said analyzer and
corresponding to at least the largest energy component occurring at a
discrete first frequency, and a second largest energy component occurring
at a second discrete frequency, said signal corresponding to said second
largest energy component being attenuated as a function of the frequency
spacing between the spatial frequencies of said largest and second largest
energy components.
4. The device of claim 1 in which said logic means comprises:
means for determining the total energy E represented by the discrete
frequency term output of the bandwidth limited transform analyzer, as the
signal sum of selected signals in the output of said analyzer and
corresponding to the largest energy component occurring at a discrete
first frequency, a second largest energy component occurring at a second
discrete frequency, and a third energy component occurring at a third
discrete frequency, each of said signals corresponding to said second and
third largest energy components being attenuated as a function of the
frequency spacing between the spatial frequencies of said largest and
respective second and third largest energy components.
5. The device of claim 3 or 4 in which said logic means further included
means for identifying that discrete frequency term having the largest
energy component associated therewith and comprising:
register means responsive to a current output sample and associated
two-dimensional frequency address for temporary storage of said sample and
associated address;
storage means for storing a previous data sample and the associated address
thereof; and
comparator means responsive to said register means and storage means for
comparing said current and previous data samples, said comparator
cooperating with said storage means to dump said stored previous data
sample and associated address and substitute said current sample and
associated address in said storage means, in response to said current
sample exceeding said stored sample.
6. The device of claims 2, 3 or 4 in which said means for determining the
total energy E comprises:
amplitude means responsive to data sets (e.sub.i, .omega..sub.x.sbsb.i and
.omega..sub.y.sbsb.i) representing the two-dimensional discrete frequency
transform output of the transform analyzer for determining that data set
corresponding to a predominant data set (e.sub.i, .omega..sub.x.sbsb.i,
.omega..sub.y.sbsb.1) and at least a second next most predominant data set
(e.sub.2, .omega..sub.x.sbsb.2 and .omega..sub.y.sbsb.2), where
.vertline.e.sub.1 .vertline.<.vertline.e.sub.2 .vertline.;
frequency spacing means responsive to the two-dimensional frequency
coordinates associated with said first predominant and at least a second
next most predominant data set for determining an attenuation factor;
attenuation means responsive to said frequency spacing means for
attenuation of an energy term of said second predominant data set; and
signal combining means responsive to said amplitude means and said
attenuation means for providing a signal output E indicative of the sum of
said predominant energy term and said attenuated energy term.
7. The device of claim 1 in which said logic means includes:
first signalling means responsive to the discrete frequency term output of
the bandwidth limited transform analyzer for generating a signal
indicative of the largest energy component occurring at a discrete first
frequency,
second signalling means responsive to said first signalling means for
generating a signal indicative of a second largest energy component
occurring at a second discrete frequency, said second signalling means
including signal attenuating means for attenuating said signal indicative
of said second largest energy component as a function of the frequency
spacing between said first and second discrete frequencies.
8. The device of claim 1 in which said logic means includes:
first signalling means responsive to the discrete frequency term output of
the bandwidth limited transform analyzer for generating a signal
indicative of the largest energy component occurring at a discrete first
frequency,
second signalling means responsive to said first signalling means for
generating a signal indicative of a second largest energy component
occurring at a second discrete frequency, said second signalling means
including signal attenuating means for attenuating said signal indicative
of said second largest energy component as a function of the frequency
spacing between said first and second discrete frequencies; and
summing means responsive to said first and second signal means for
providing an output indicative of the sum of the inputs thereto.
9. The device of claim 1 in which said logic means comprises
means for determining the total energy E represented by the discrete
Fourier term output of the bandwidth limited fast Fourier transform
analyzer, as the sum of selected signals in the output of said analyzer
and corresponding to at least the largest energy component occurring at a
discrete first frequency, a second largest energy component occurring at a
second discrete frequency, said signal corresponding to said second
largest energy component being attenuated as a function of the frequency
spacing between the spatial frequencies of said largest and second largest
energy components, and
multiple thresholding means responsive to said means for determining for
indicating ones of preselected threshold levels exceeded by the bandwidth
limited response of said analyzer.
10. The device of claim 1 in which said logic means includes means for
identifying those respective discrete Fourier terms having the largest and
second largest energy components, respectively, and the associated
two-dimensional frequency addresses thereof.
11. The device of claim 10 in which said means for identifying includes:
first peak detection means adapted to be responsive to an applied input for
storing a first detected peak value (e.sub.1) of a data train and
discarding all other data of the data train, and
second peak detecting means responsive to said all other data of the data
train for storing a second peak detected value (e.sub.2 <e.sub.1) of said
data train and discarding the remainder of the data.
12. A pre-edit signalling subsystem for use in a fingerprint identification
system and responsive to an electrical signal analog of a scanned image
for indicating the presence/absence of a non-fingerprint region of such
image, said subsystem comprising:
a two-dimensional sequency transform analyzer responsive to a binary-coded
image signal for identifying the two largest discrete frequency terms
occurring within a selected bandwidth corresponding to a spatial frequency
region describing the description of a fingerprint image; and
logic means responsive to said bandwidth limited transform analyzer for
further identifying the relative energy levels of the spectral content of
the binary-coded image signal, for indicating the probability that the
scanned image represented by said binary coded signal analog represents a
non-fingerprint region.
13. A pre-edit signalling system responsive to an electrical signal analog
of a scanned image for indicating the probable absence or presence of a
non-fingerprint region of such image, said system comprising
signalling means response to a grey level electrical signal corresponding
to a scanned image, for providing a compacted, thresholded binary-coded
electrical signal;
a two-dimensional sequency transform analyzer responsive to said
binary-coded signal for identifying discrete frequency terms occuring
within a preselected bandwidth corresponding to a spatial frequency region
associated with descriptions of a fingerprint image; and
logic means responsive to said bandwidth limited transform analyzer for
further identifying the relative total energy level of the bandwidth
limited spectral content of the binary-coded image signal as in terms of
the probability of the scanned image corresponding to said binary-coded
signal representing a non-fingerprint region.
14. The device of claim 13 in which said signalling means comprises
data comparator means responsive to a matrix (n.times.n) of discrete grey
level first pixels corresponding to an image field of interest for
combining clusters of contiguous grey level pixels to provide a compacted
matrix (N/2.times.n/2) of second pixels, each said second pixel having a
grey level corresponding to the average grey level of the associated pixel
cluster represented by such second pixel.
15. The device of claim 14 in which said signalling means further comprises
means for thresholding signals representing said second pixels of said
compacted matrix to provide binary-coded signals corresponding to a
binary-coded data matrix representing said scanned image.
16. A pre-edit signalling system responsive to an electrical signal analog
of a scanned image for indicating the probable absence or presence of a
non-fingerprint region of such image, said system comprising
a two-dimensional periodic function transform analyzer responsive to a
binary-coded image signal for identifying discrete periodic function
frequency terms occurring within a preselected bandwidth corresponding to
a spatial frequency region associated with descriptions of a fingerprint
image; and
logic means responsive to said bandwidth limited transform analyzer for
further identifying the relative energy level of the bandwidth-limited
spectral content of the binary-coded image signal as an indication of the
inclusion of a non-fingerprint region within the second image represented
by said binary-coded signal analog.
17. The device of claim 16 in which said logic means comprises: means for
determining the total energy E represented by the frequency term output of
the bandwidth limited transform analyzer, as the sum,
e.sub.1 +(e.sub.2 /d.sub.12.sup.2)+(e.sub.3 /d.sub.13.sup.2),
where
e.sub.1 =the largest energy component occurring at a first discrete
frequency
e.sub.2 =a second largest energy component occurring at a second discrete
frequency
e.sub.3 =a third energy component occurring at a third discrete frequency
d.sub.12 =the frequency interval or spacing between e.sub.1 and e.sub.2
d.sub.13 =the frequency interval or spacing between e.sub.1 and e.sub.3.
18. The device of claim 17 in which said logic means further includes means
for identifying that discrete Fourier term having the largest energy
component associated therewith and comprising:
a first register responsive to a current serial output sample of said fast
Fourier transform analyzer for temporary storage of said current sample;
first storage means for storing a previous data sample input thereto;
a comparator responsive to said first register and said first storage means
for comparing the amplitudes represented by said current sample and
previous sample;
a second register responsive to a two-dimensional frequency address of said
fast Fourier serial output sample; and
a second register for storing a two-dimensional frequency address
associated with said previous data sample,
said comparator, in response to said current sample exceeding said stored
sample, cooperating to dump said stored previous sample and associated
stored address from said first and second storage means, respectively, and
substitute said exceeding current sample and the associated address
therefor in a respective one of said storage means.
19. The device of claim 17 in which said logic means further includes means
for identifying that discrete Fourier term having the largest energy
component associated therewith and comprising:
register means responsive to a current said output sample and associated
two-dimensional frequency address for temporary storage of said sample and
associated address;
storage means for storing a previous data sample and the associated address
thereof; and
comparator means responsive to said register means and storage means for
comparing said current and previous data samples, said comparator
cooperating with said storage means to dump said stored previous data
sample and associated address and substitute said current sample and
associated address in said storage means, in response to said current
sample exceeding said stored sample.
20. The device of claim 17 in which said logic means includes means for
identifying those respective discrete Fourier terms having the largest,
and second and third largest energy components, respectively, and the
associated two-dimensional frequency addresses thereof.
21. The device of claim 20 in which said means for identifying includes:
a first peak detection means adapted to be responsive to an applied input
for storing a first detected peak value (e.sub.1) of a data train and
discarding all other data of the data train,
second peak detecting means responsive to said all other data of the data
train for storing a second peak detected value (e.sub.2 <e.sub.1) of said
data train and discarding the remainder of the data, and
third peak detecting means responsive to the remainder of said data train
for storing a third peak value (e.sub.3 <e.sub.2 <e.sub.1) of said data
train.
22. The device of claim 16 in which said logic means includes multiple
level thresholding means responsive to the total energy represented by the
output of the bandwidth limited Fourier transform analyzer for indicating
a degree of probability that the scanned image represents a
non-fingerprint region.
23. The device of claim 16 in which said logic means comprises means for
determining the total energy E represented by the discrete Fourier term
output of the bandwidth limited fast Fourier transform analyzer, as the
sum,
e.sub.1 +(e.sub.2 /d.sub.12.sup.2)+(e.sub.3 /d.sub.13.sup.2),
where
e.sub.1 =the largest energy component occurring at a discrete first
frequency
e.sub.2 =a second largest energy component occurring at a second discrete
frequency
e.sub.3 =a third energy component occurring at a third discrete frequency
d.sub.12 =the frequency interval or spacing between e.sub.1 and e.sub.2
d.sub.13 =the frequency interval or spacing between e.sub.1 and e.sub.3 ;
and
multiple thresholding means responsive to said means for determining for
indicating ones of preselected threshold levels exceeded by the bandwidth
limited response of said analyzer.
24. A pre-edit signalling subsystem for use in a fingerprint identification
system and responsive to an electrical signal analog of a scanned image
for indicating the presence/absence of a non-fingerprint region of such
image, said subsystem comprising:
a two dimensional fast Fourier transform analyzer responsive to a
binary-coded image signal for identifying the two largest discrete Fourier
terms occurring within a selected bandwidth corresponding to a spatial
frequency region describing the description of a fingerprint image; and
logic means responsive to said bandwidth limited fast Fourier transform
analyzer for furtheer identifying the relative energy levels of the
spectral content of the binary-coded image signal, for indicating the
probability that the scanned image represented by said binary coded signal
analog represents a non-fingerprint region.
25. A pre-edit signalling system responsive to an electrical signal analog
of a scanned image for indicating the probable absence or presence of a
non-fingerprint region of such image, said system comprising
signalling means response to a grey level electrical signal corresponding
to a scanned image, for providing a compacted, thresholded binary-coded
electrical signal;
a two dimensional fast Fourier transform analyzer responsive to said
binary-coded signal for identifying discrete Fourier terms occurring
within a preselected bandwidth corresponding to a spatial frequency region
associated with descriptions of a fingerprint image; and
logic means responsive to said bandwidth limited fast Fourier transform
analyzer for further identifying the relative total energy level of the
bandwidth limited spectral content of the binary-coded image signal as in
terms of the probability of the scanned image corresponding to said
binary-coded signal representing a non-fingerprint region.
26. The device of claim 25 which said sampling means comprises
data comparator means responsive to a matrix (n.times.n) of discrete grey
level first pixels corresponding to an image field of interest for
combining clusters of contiguous grey level pixels to provide a compacted
matrix (n/2.times.n/2) of second pixels, each said second pixel having a
grey level corresponding to the average grey level of the associated pixel
cluster represented by such second pixel.
27. The device of claim 25 in which said signalling means further comprises
means for thresholding signals representing said second pixels of said
compacted matrix to provide binary-coded signals corresponding to a
binary-coded data matrix representing said scanned image.
28. The device of claims 17, 23 or 27 in which said logic means E
comprises:
amplitude means responsive to data sets (.omega..sub.x.sbsb.i,
.omega..sub.y.sbsb.i and e.sub.i) representing the two-dimensional
discrete Fourier transform output of the fast Fourier transform analyzer
for determining that data set corresponding to a predominant data set
(e.sub.1, .omega..sub.x.sbsb.1, .omega..sub.y.sbsb.1) and a second and
third next most predominant data set (e.sub.2, .omega..sub.x.sbsb.2 and
.omega..sub.y.sbsb.2) and (e.sub.3, .omega..sub.x.sbsb.3 and
.omega..sub.y.sbsb.3), where .vertline.e.sub.1
.vertline.>.vertline.e.sub.2 .vertline.>.vertline.e.sub.3 .vertline.,
frequency spacing means responsive to the two dimensional frequency
coordinates associated with said first predominant second and third next
most predominant data sets for determining the frequency spacing factors
d.sub.12.sup.1/2 and d.sub.13.sup.1/2,
signal combining means responsive to said amplitude means and frequency
spacing means for providing a signal output E indicative of the
relationship, e.sub.1 +(e.sub.2 /d.sub.12.sup.2)+(e.sub.3
/d.sub.13.sup.2).
29. The device of claim 28 in which said signal combining means comprises:
first multiplier means responsive to data element e.sub.2 and factor
d.sub.12.sup.1/2 for providing an output e.sub.2 /d.sub.12.sup.2
corresponding to the product of the applied inputs thereto;
second multiplier means responsive to data element e.sub.3 and factor
d.sub.13.sup.1/2 for providing an output e.sub.3 /d.sub.13.sup.2
corresponding to the product of the applied inputs thereto; and
output data summing means responsive to data element e.sub.1 and to the
outputs of said first and second multiplier means for providing an output
E corresponding to the sums of the applied inputs thereto. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
CO-PENDING APPLICATIONS
1. Application Ser. No. 722,308 filed Sept. 10, 1976 for MINUTIAE PATTERN
MATCHER by John P. Riganati et al, now U.S. Pat. No. 4,135,147.
2. Application Ser. No. 722,244 filed Sept. 10, 1976 for AUTOMATIC PATTERN
PROCESSING SYSTEM by John P. Riganati et al, now U.S. Pat. No. 4,151,512.
3. Application Ser. No. 847,987 filed Nov. 2, 1977 for METHOD AND APPARATUS
FOR AUTOMATIC EXTRACTION OF FINGERPRINT CORES AND TRI-RADII by John P.
Riganati et al, now U.S. Pat. No. 4,156,230.
4. Application Ser. No. 934,657 filed Aug. 17, 1978 for SYSTEM FOR
EXPANDING THE VIDEO CONTRAST OF AN IMAGE by Stanley A. White et al.
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to pattern identification systems and more
particularly to a non-fingerprint-like region indicator for indicating
whether or not a region or portion of a pattern of interest is free of
fingerprint-like pattern data, as to be of no interest in the processing
of such pattern.
2. Description of the Prior Art
The advent of high speed digital data processors has enabled the mass
handling of fingerprint pattern data by automatic data retrieval and
pattern identification systems. Such systems involve the treatment of an
image as a large matrix of many discrete elements which provide a mosaic
pattern resembling the image of interest. For a grey-coded image, for
example, each discrete element or pixel thus has an intensity score of
weighting and also an assigned set of coordinates corresponding to the
position of such pixel in the image plane or field.
The range of average pixel intensity (for the pixels in a given region) may
be quite wide over the large number of regions comprising the total image
pattern. Due to dynamic range limitations of the data processing
equipment, such range of average pixel intensity over such regions may
need be compressed or "normalized" relative to equipment performance
limitations. Such gain normalization may be achieved in a manner
corresponding to automatic gain control techniques. In this way, image
definition is retained in each region or sub-pattern of the overall
pattern, without either saturating the equipment (by regions with strong
average intensities) or losing image definition (in regions of weak
average intensities).
Other equipment limitations occur with regard to logic limitations of the
pattern matcher to correlate an imperfect, broken, smudged or dirty image
with a clean reference image. Such image-data processing limitations have
led to the development of pre-processors for masking or editing such image
data, whereby the image content thereof could be made more useful to the
pattern identification system, rather than rejected as a mismatch or
pattern not of interest.
Still further devices have been devised for reducing the volume of the data
retrieval and processing involved in the pattern matching process by the
use of automatic image classification techniques. By means of such
techniques, recognized fingerprints are classified in accordance with
image classifications occurring in the automatic pattern recognition
process. An automatic recognition process of interest is the encoding of
minutiae data of a fingerprint into a relative information vector (RIV)
format. Other techniques include the identification of cores and deltas.
An exposition of exemplary forms of such pattern processing techniques is
included in the following copending patent applications, all of which are
assigned to Rockwell International Corporation, assignee of the subject
patent application:
1. Application Ser. No. 722,308 for MINUTIAE PATTERN MATCHER, filed Sept.
10, 1976 by John P. Riganati et al
2. Application Ser. No. 722,244 for AUTOMATIC PATTERN PROCESSING SYSTEM,
filed Sept. 10, 1976 by John P. Riganati et al
3. Application Ser. No. 847,987 for METHOD AND APPARATUS FOR AUTOMATIC
EXTRACTION OF FINGERPRINT CORES AND TRI-RADII, filed Nov. 2, 1977 by John
P. Riganati et al
4. Application Ser. No. 934,657 for SYSTEM FOR EXPANDING THE VIDEO CONTRAST
OF AN IMAGE, filed Aug. 17, 1978 by Stanley A. White et al.
However, all of such fingerprint pattern recognition systems require
pre-processing or pre-editing of regions of the image data, not only to
format the data in a form and style compatible with the pattern
recognition system mechanization, but to also either fix-up or edit-out
useless regions of an otherwise useful image of interest, so as to avoid
"false alarms" and unnecessary rejects or useless attempts to perform
pattern recognition of unrecognizable data.
What is desired is further means for indicating or pre-editing pattern data
signals relative to non-fingerprint-like regions within an image field or
pattern of interest, with a view to reducing unnecessary processing of
less relevant image data and improving the consequent quality and speed of
image matching.
SUMMARY OF THE INVENTION
By means of the concept of the invention there is provided signalling means
for enhancing the performance of automatic fingerprint identification
systems by reducing the system response to local non-fingerprint regions
of an image field pattern of interest. Such non-fingerprint region
indicator or signalling means may be employed to "vote" with or to
supplement the editing provided by other pre-editing systems or used in
lieu of other types of pre-editing of electrical image-pattern signals.
In a preferred embodiment of the invention there is provided a
two-dimensional generalized sequency analyzer, such as a fast Fourier
transform (2D-FFT) machine or the like, responsive to a binary-coded image
signal for identifying discrete frequency terms occurring within a
selected bandwidth corresponding to a spatial frequency region associated
with descriptions of a fingerprint image. There is also provided logic
means responsive to the bandwidth limited generalized transform analyzer
for further identifying the relative energy levels of the
bandwidth-limited spectral content of the binary-coded image signal to
provide the identity of a non-fingerprint region within the scanned image,
represented by the binary-coded signal.
In normal operation of the above-described arrangement, the failure to
detect discrete frequency terms indicative of a fingerprint in a
particular region of a scanned image results in a "non-fingerprint-like
region" indication for such region. Such indication may be used to avoid,
screen, block or edit-out such region from the image pattern being
subjected to the pattern recognition process. In this way, the processing
time required to effect the overall pattern recognition process may be
reduced, and the certainty of recognition is improved by the exclusion of
image data not of interest.
Accordingly, it is an object of the invention to enhance the performance of
automatic fingerprint pattern recognition systems.
It is another object of the invention to provide alternative signalling
means for supplementary pre-editing of grey-coded electrical signals
corresponding to a scanned fingerprint image for providing an indication
of a non-fingerprint-like region within such image.
It is a further object to distinguish a non-fingerprint-like region amid a
fingerprint image of interest by the relative absence (from said region)
of discrete fast Fourier transform elements within a preselected bandwidth
of spatial frequencies.
A still further object is to identify a non-fingerprint-like region of an
image as being an image region not of interest in the pattern recognition
of fingerprint patterns.
These and other objects of the invention will become readily apparent from
the following description, taken together with the accompanying drawings
in which:
BRIEF DESCRIPTION OF THE DRAWINGS
FIGS. 1a and 1b are a representative spatial bar pattern and its associated
Fourier transform.
FIGS. 2a and 2b are a stylized minutia pattern and the location of its
Fourier components in a half plane.
FIGS. 3a and 3b are a stylized delta pattern and the location of its
Fourier components in a half plane.
FIGS. 4a, 4b and 4c are a stylized core-like pattern and its Fourier
components in a half plane.
FIGS. 5a and 5b are a representative noisy pattern and the location of its
Fourier components in the half plane, which FIG. 5c illustrates the
magnitudes of the associated Fourier coefficients.
FIG. 6 is a representation of the bandpass limited Fourier transform
response region of interest.
FIG. 7 is a block diagram of a system in which the concept of the invention
may be advantageously employed.
FIG. 8 is a block diagram of a system embodying the concept of the
invention.
FIG. 9 is a schematic arrangement, partially in block form, of an exemplary
mechanization for the data compaction block element included in FIG. 8.
FIG. 10 is an illustration of an exemplary compaction of a representative
pixel pattern, as performed by the device of FIG. 9.
FIG. 11 is a timing diagram for the device of FIG. 9.
FIG. 12 is a schematic arrangement, partially in block form, of the
binary-coding thresholded signalling block of FIG. 8.
FIG. 13 is a responsive diagram, illustrating the four-state, three-level
thresholded response of the logic device 33 of FIG. 8.
FIGS. 14a and 14b are a schematic arrangement, partially in block form, of
the "scoring" or confidence logic block of FIG. 8.
DESCRIPTION OF THE PREFERRED EMBODIMENT OF THE INVENTION
The purpose and function of the invention described herein is to supplement
or augment the pre-edit or preliminary image signal conditioning and
masking in an automatic fingerprint identification system, by indicating
the probable absence of fingerprint-like structure in an identified region
of a fingerprint pattern of interest. The performance of such function
involves a consideration of the gross structure of a fingerprint pattern,
and treats a local region of a fingerprint pattern as a system of thick
parallel lines. The gross structure of a fingerprint pattern resembles
parallel thick curves. However, within a local region, these curves appear
as almost straight lines.
Several exceptions to such appearance of a local fingerprint region
appearance as parallel thick line structure are:
1. the existence of minutia
2. the existence of cores and deltas
3. the existence of gaps, pores and scars and other noise effects, such as
poor contrast and smudging.
The last item (image noise) may be internal to the specific fingerprint
itself (gaps, pores, scars) or due to the quality of the detection and
reproduction of the print (poor contrast and smudging).
It has been discovered that an examination of the spatial frequency
spectral content or Fourier transform term provides a means of
automatically detecting and indicating a non-fingerprint region within a
fingerprint pattern field of interest. Referring to FIG. 1a there is
illustrated a representative spatial bar pattern corresponding to a
fingerprint-like region within a fingerprint pattern field of interest. As
illustrated, a vertical array of three horizontally parallel lines or
ridges is interleaved by three valleys for a region or frame 64 mils
square (0.064 inches by 0.064 inches), corresponding to a spatial
periodicity of three cycles per frame. However, it has been determined
that within the reference region or frame size (0.064".times.0.064") the
contemplated spatial periodicity includes the range from 2 to 5 cycles per
frame. The corresponding predominant frequency term is shown in FIG. 1b,
the ordinate, .omega..sub.y, of which represents spatial frequency in a
reference or vertical direction, and abscissa, .omega..sub.x, of which
represents spatial frequency occurring in a directional orthogonal to the
first direction.
The existence of a minutia region, as illustrated in idealized form in FIG.
2a, produces two predominant Fourier terms, spaced somewhat closely
together in the frequency domain, as shown in FIG. 2b. Such idealized form
of FIG. 2 may be viewed as if produced by rotation of the lower lines of
FIG. 1, with the two frequency terms of FIG. 2b resulting from a
decomposition of the predominant term of FIG. 1b.
For a delta-like region (of a fingerprint), as illustrated in the idealized
form in FIG. 3a, three predominant Fourier terms occur, as shown in FIG.
3b. For a core-like region (of a fingerprint), as illustrated by the
idealized form of FIG. 4a, two (somewhat like) predominant discrete
Fourier frequency terms occur, displaced 90.degree. apart as shown in FIG.
4b, the amplitude of such high power or predominant terms being shown (in
the .omega. axis) in FIG. 4c.
A Fourier transform estimate of a noisy pattern (FIG. 5a) usually results
in many low-energy, higher-frequency terms, a typical representation for
which is shown in FIG. 5b. The low energy content of such Fourier terms of
FIG. 5b are shown in the .omega. axis of the discrete spectral energy
distribution depicted in FIG. 5c, and is to be compared with the energy
levels depicted in FIG. 4c for the spectral distribution of FIG. 4b. For a
light or datk patch, (i.e., little or no pattern), the discrete Fourier
terms would be clustered about the origin in FIG. 5b.
In view of the foregoing, it is to be appreciated that a means of testing a
spatial spectrum of interest for fingerprint content or identification as
a non-fingerprint indicating region has been conceived as a combination of
bandpass limiting of the spatial spectrum response to within a preselected
spatial frequency region of interest. Such bandpass limited discrete
Fourier transform response region is depicted graphically in FIG. 6, as
excluding frequencies above and below those corresponding to 2-5 cycles
per 64 mil frame. Thus, both high frequency noise and low spatial
frequency modulation terms are discarded. Referring again to FIG. 5c,
showing the spectral energy distribution associated with a noisy or
noise-type pattern, it is to be seen that many of the discrete frequency
Fourier terms associated therewith would lie outside the preselected
bandpass region, while those terms within the bandpass, being low-level
relative to the terms of interest in FIGS. 4a, 4b and 4c, are susceptible
to thresholding.
Because the discrete Fourier transform terms for spatial frequencies for a
given fingerprint region are relatively few, the effects of
non-fingerprint or non-regular source contributions to such terms can be
attenuated by a "scoring" technique, contrived to discriminate in terms of
that predominant discrete frequency (f.sub.1) having the highest energy
level (e.sub.1). Such scoring system will attenuate the energy term
(e.sub.i) for other than the largest discrete Fourier term by a factor
(d.sub.1i.sup.1/2) corresponding to the reciprocal of the square or other
function of the spectral interval between the predominant frequency energy
term e.sub.1 and the energy terms (e.sub.i) for such other discrete
Fourier terms. For at least two such other terms (i.e., three predominant
terms):
E=e.sub.1 +e.sub.2 /d.sub.12.sup.2 +e.sub.3 /d.sub.13.sup.2. (1)
In this way, the energy contributed by randomly present discrete
frequencies within the spatial spectrum of interest is attenuated and the
score, E, tends to approach the value of e.sub.1. The score E may then be
further tested by thresholding as an indication of the confidence level
with which such term indicates the presence of a fingerprint-like region
(high-level thresholding) or, conversely, the presence of a
non-fingerprint-like region (null or low-level thresholding).
A system in which the concept of the invention may be advantageously
employed is shown in FIG. 7.
Referring now to FIG. 7, there is illustrated in block diagram form an
automatic fingerprint reader system comprising an input section 20,
decision logic section 21, and display indicator 22. Input section 20
includes electro-optic means for converting an image or optical impression
into a series of grey-coded electrical signals which are applied to the
decision logic 21 for a determination as to whether the image may include
fingerprint data of interest, while utilization means 22 displays the
machine decision in that regard. Alternatively, block element 22 may
comprise fingerprint classifier and comparator means.
There is further provided in the arrangement of FIG. 7 non-fingerprint-like
region indicator means 23, responsive to the output 24 of signalling
device 20, for "weighting", gating or otherwise modulating the output of
display indicator 22 in accordance with the concept of the invention. In
other words, element 23 provides a control signal output indicative of the
occurrance of a non-fingerprint-like region in the review of the regions
of a fingerprint image of interest, for the purpose of preventing spurious
image non-match decisions based on processing of irrelevant image data.
The device of block 23, embodying the concept of the invention, is shown in
further detail in FIG. 8.
Referring now to FIG. 8, there is illustrated a block diagram of a system
embodying the concept of the invention. There is provided data compaction
means 30 responsive to a "grey-coded" pixel image signal output of the
sensor or input stage of an automatic fingerprint reader system. Such
"grey-coded" signal represents a scanned image as a matrix of grey-coded
pixels or discrete elements of a mosaic or pattern corresponding to the
pattern of interest. The data density of the signal of interest is greater
than that required for the non-fingerprint indicator function of the
invention. Accordingly, to unnecessarily cope with such data density would
merely slow-down the data processing function or require unnecessary data
processing capacity, neither of which is desirable. Therefore, 4:1 data
compaction of the grey-coded data is provided by means of element 30,
whereby an image of 32.times.32 pixels is reduced in definition or
resolution to an image of 16.times.16 pixels. In other words, a 4-pixel
cluster of 2.times.2 pixels is supplanted by a single grey-coded pixel,
the code or intensity of which is the average of those pixels being
supplanted. Such compaction technique is also useful in interfacing the
data input source with the fast Fourier transform device 32 to be employed
for spatial frequency analysis of the input data. Such interfacing or
scaling may be selected to overlap the sub-areas or regions utilized by
other testing or data pre-editing schemes, so that the editing function
provided thereby may be supplemental to that provided by such other
testing schemes for such regions.
If deemed desirable, an AGC function may be interposed at the input to data
compaction means 30, in accordance, for example, with the teachings of
U.S. Application Ser. No. 934,657 for SYSTEM FOR EXPANDING THE VIDEO
CONTRAST OF AN IMAGE, filed Aug. 17, 1978, by Stanley A. White, assignor
to Rockwell International Corporation, assignee of the subject
application. However, signal normalization within the fingerprint reader
input system (i.e., element 20 in FIG. 1) may obviate any necessity for
such additional function.
Because the fast Fourier analyzer 32 in the arrangement of FIG. 8 employs
binary-coded (i.e., black-white coded) data, there is interposed between
the output of data compaction means 30 and fas | | |
