Fingerprint identification by ridge angle and minutiae recognition

• US 4,208,651 A
• Filed: 05/30/1978
• Issued: 06/17/1980
• Est. Priority Date: 05/30/1978
• Status: Expired due to Term

• Current Assignee: Sperry Corporation (Unisys Corporation)
• Original Assignee: Sperry Corporation (Unisys Corporation)
• Inventors: McMahon, Donald H.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US05/910,810
• Time in Patent Office: 749 Days
• Field of Search: 340/146.3 AC, 340/146.3 AE, 340/146.3 J, 340/146.3 H, 340/146.3 MA, 340/146.3 E, 340/149 R, 340/149 A
• US Class Current: 382/125
• CPC Class Codes: G06V 40/1347 Preprocessing; Feature extraction

Abstract

A raster scanning laser beam and cooperating light detector generate a stream of binary coded data, which data are processed to yield an organized binary pattern of ridge angle data. Location of secondary data representing only one side of the fingerprint ridges is then accomplished and that data is locally stored. As a further descriptor of the print, non-paired ridge endings are identified. While retaining the advantages inherent in ridge angle processing for identification, the recognition system makes use of non-paired selected line end minutiae data as a fine descriptor, comparing the location of such minutiae with respect to predetermined points of the fingerprint pattern, so affording a final assessment of match validity.

Claims

1. The method of recognizing a pattern of lines lying substantially in a single plane including the steps of:

scanning said pattern of lines in a synchronized manner,

generating a first flow of binary data corresponding to the presence or absence of lines in successive locations of said scanned pattern of lines,

decoding said first flow of binary data, thereby generating a second flow of binary data representing the locations of only a predetermined side of each of said lines,

locating from said second flow of binary data the locations of end points of said one side of each of said lines, and

generating a control signal in response to location of said end points for transferring said data to processor means for selecting only said locations of end points not lying in substantially colineal proximate relation to an associated end point.

2. The method of recognizing a pattern of lines lying in a substantially common plane including the steps of:

scanning said pattern of lines for providing a first flow of binary data representative of the respective angular orientations of said lines,

utilizing said first flow of binary data for providing a second stream of binary data representing the locations of one side only of each of said lines,

locating minutiae in the form of endings of said one side of each of said lines,

storing at least said data representative of the respective angular orientations of said lines, and

additionally storing selected locations of said minutiae.

3. In a pattern identification apparatus:

energy source means for illuminating a predetermined portion of a pattern of lines,

deflector means for raster scanning said illumination over said pattern of lines,

detector means responsive to energy scattered from individual lines of said pattern of lines,

pulse shaper means responsive to said detector means for converting the output thereof into a first flow of binary data,

a plurality of n serially connected shift register means having an input receiving said first flow of binary data,

first and second shift register-counter means,

said first shift register-counter means being responsive to the first of said plurality of shift register means,

said second shift register-counter means being responsive to the second of said plurality of shift register means,

generator means for generating a second flow of binary data representative of one side line binary data,

said generator means being responsive to the nth and (n-1)^th of said plurality of shift register means and to said first and second shift register-counter means.

4. Apparatus as described in claim 3 further including line ridge angle decoder means responsive to the first and second of said shift register means and having plural outputs representing totals of each of a plurality of sampled line angular data.

5. Apparatus as described in claim 4 including:

master clock means,

first OR gate means responsive to first and second of said plural outputs,

first UP-DOWN multi-bit counter means responsive to said first OR gate means, to said first output, and to said master clock means, and

first shift register means responsive to said first UP-DOWN counter means and to said master clock means,

said first UP-DOWN counter means being further responsive to said first shift register means.

6. Apparatus as described in claim 5 wherein:

said master clock means yields first and second clock pulse trains of respective first and second repetition rates,

said first shift register means includes input enable and output enable means responsive to said first clock pulse train of first repetition rate, and

said first UP-DOWN counter means includes preset enable means additionally responsive to said first clock pulse train of first repetition rate.

7. Apparatus as described in claim 6 wherein said first UP-DOWN counter means includes:

data input means responsive to said AND gate means, and

data enable means responsive to said second clock pulse train of second repetition rate.

8. Apparatus as described in claim 7 wherein said first UP-DOWN counter means generates a flow of binary data representing the sign of said first UP-DOWN counter means outputs.

9. Apparatus as described in claim 5 further including:

second OR gate means responsive to third and fourth of said plural outputs,

second UP-DOWN counter means responsive to said second OR gate means, to said third output, and to said clock means, and

second shift register means responsive to said second UP-DOWN counter means and to said master clock means,

said second UP-DOWN counter means being further responsive to said second shift register means.

10. Apparatus as described in claim 9 wherein said second UP-DOWN counter means generates a flow of binary data representing the sign of said second UP-DOWN counter means outputs.

11. In a pattern identification apparatus:

energy source means for illumination of successive portions of a pattern of lines,

deflector means for raster scanning said illumination over said pattern of lines,

detector means responsive to energy scattered from individual lines of said pattern of lines,

pulse shaper means responsive to said detector means for converting the output thereof into a first flow of binary data,

master clock means,

a first plurality of n serially connected shift register means having input means receiving said first flow of binary data and having output means,

a second plurality of n serially connected shift register means having input means responsive to said output means,

first line angle decoder means responsive to said flow of binary data and to the first of said first plurality of n serially connected shift register means,

second line angle decoder means responsive to said (n-1)^th and said n^th shift register means of said second plurality of n serially connected shift register means,

first and second sign generator means both responsive to said first and second line angle decoder means, and

third generator means for generating a second flow of binary data representative to one side line binary data,

said third generator means being responsive to said first and second sign generator means, to the n^th of said first plurality of n serially connected shift register means and to the first of said second plurality of n serially connected shift register means.

12. Apparatus as described in claim 11 wherein said third generator means comprises:

plural AND gate means,

OR gate means responsive to said plural AND gate means for producing said second flow of binary data,

coupling matrix means for selectively activating individual gates of said plural AND gate means,

first coupling means for direct and inverted coupling of versions of said outputs of said first and second sign generator means into said coupling matrix means, and

second coupling means for direct, delayed, and inverted coupling versions of said outputs of said n^th of said first plurality of n serially connected shift register means and of said first of said second plurality of n serially connected shift register means into said coupling matrix means,

said second coupling means including bistable means additionally responsive to said master clock means.

13. In a pattern identification apparatus:

scanning means for regularly scanning a substantially planar pattern of lines in a plurality of locations for producing an output upon traversal of each said line,

synchronizer means,

timing pulse generator means,

said timing pulse generator means and said scanner means being responsive to said synchronizer means,

first decoder means responsive to the presence or absence of lines at successive locations in said scanned planar pattern of lines and to said timing pulse generator means for generating a first flow of binary data, and

first discriminator means responsive to said first decoder means for locating selected end points of each said line,

said timing pulse generator means including;

first, second, third, and fourth counter means in series connection,

flip flop means having set, reset, and output terminals, and

AND gate means,

said flip flop means set terminal being responsive to said synchronizer means,

said AND gate means being responsive to said first counter means and to said flip flop means output terminal output for forming clock pulses of a first repetition frequency,

said second counter means being responsive to said AND gate means for forming clock pulses of a second repetition frequency,

said third counter means being responsive to said second counter means for forming clock pulses of a third repetition frequency,

said fourth counter means being responsive to said third counter means for forming clock pulses of a fourth repetition frequency,

said flip flop means reset terminal being responsive to said fourth counter means, and

said first counter means being responsive to said master clock means.

14. Apparatus as described in claim 13 wherein:

said first and second counter means include reset terminals, and

said first and second counter reset terminals are responsive to the output of said flip flop means.

15. Apparatus as described in claim 14 wherein said third and fourth counter means are cooperatively responsive for generating a flow of binary data instantaneously representative of a second coordinate of said scanning means position.

16. In a pattern identification apparatus:

synchronizer means,

scanning means for regularly scanning a substantially planar pattern of lines in a plurality of locations for producing an output upon traversal of each said line and including;

energy source means for illuminating a predetermined portion of said pattern of lines,

deflector means responsive to said synchronizer means for raster scanning said illumination over said pattern of lines, and

detector means responsive to energy scattered from individual lines of said pattern of lines,

timing pulse generator means,

said timing pulse generator means and said scanning means being responsive to said synchronizer means,

first decoder means responsive to the presence or absence of lines at successive locations in said scanned planar pattern of lines and to said timing pulse generator means for generating a first flow of binary data,

first discriminator means responsive to said first decoder means for locating selected end points of each said line,

pulse forming means responsive to said detector means for converting the output thereof into said first flow of binary data,

storage circuit means responsive to said pulse forming means and to said synchronizer means for storing successive trains of said flow of said first binary data through a predetermined number of successive scans of said deflector means and having plural parallel output means, and

line angle decoder means responsive to said plural parallel output means for supply of a further flow of binary data representing totals of each of a plurality of sampled line angular data.

17. In a pattern identification apparatus:

synchronizer means,

scanning means for regularly scanning a substantially planar pattern of lines in a plurality of locations for producing an output upon traversal of each said line and including

energy source means for illuminating a predetermined portion of said pattern of lines,

deflector means responsive to said synchronizer means for raster scanning said illumination over said pattern of lines, and

detector means responsive to energy scattered from individual lines of said pattern of lines,

timing pulse generator means,

said timing pulse generator means and said scanning means being responsive to said synchronizer means,

first decoder means responsive to the presence or absence of lines at successive locations in said scanned planar pattern of lines and to said timing pulse generator means for generating a first flow of binary data,

first discriminator means responsive to said first decoder means for locating selected end points of each said line,

pulse forming means responsive to said detector means for converting said detector means output into said first flow of binary data,

first and second flip flop means responsive to said synchronizer means and having first and second respective output means,

shift register means responsive to said synchronizer means and having third output means,

said first flip flop means and said shift register means being additionally responsive to said pulse forming means,

said second flip flop means being additionally responsive to said shift register means, and

decoder means responsive to said first, second, and third output means and to said pulse forming network means.