Minutiae recognition system

• US 3,893,080 A
• Filed: 06/29/1973
• Issued: 07/01/1975
• Est. Priority Date: 06/29/1973
• Status: Expired due to Term

• Current Assignee: Allen P. Ho, Hua-Tung Lee
• Original Assignee: Allen P. Ho, Hua-Tung Lee
• Inventors: Ho, Allen P., Lee, Hua-Tung
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US05/375,211
• Time in Patent Office: 732 Days
• Field of Search: 340/146.3E,146.3MA,146.3AC,146.3R,146.3,172.5 356/71
• US Class Current: 382/125
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices
• CPC Class Codes: G06V 40/1347 Preprocessing; Feature extraction

Abstract

A system for detecting bifurcations and ridge endings (minutiae) in a fingerprint or on similar patterns in which two lines merge into one. The print is optically scanned, converted into electrical signals and entered into a novel continuity logic network. The presence of a bifurcation in the network results in three distinct outputs on the periphery of the network from at least two sides. The split in the bifurcation may also be detected by reversing the polarity of the electrical signals and detecting a single output. Means are also provided for ensuring that a single bifurcation is detected only once. Ridge endings are treated as reverse-polarity bifurcations and can be detected by the same system elements.

Claims

1. A system for recognizing the merger of two lines in a pattern consisting of lines and spaces between lines comprising:

scanniNg means for scanning said pattern and having a scanning output;

means for converting the output of said scanning means into binary signals representative of the contrast between said lines and said spaces; and

continuity logic means for forming conductive paths corresponding to the contrast between said lines and spaces including;

a matrix of logic elements;

a source of a continuity signal;

each said logic element in said matrix generating an output signal to the inputs of the logic elements located adjacent and orthogonal thereto in response to the combination of a binary signal from said scanning means and said continuity signal;

said continuity signal source being directly connected only to the inputs of a first set of logic elements in said matrix;

whereby said continuity signal source is electrically connected to the inputs of the logic elements outside of said first set only when at least one of said first set of logic elements generates an output signal; and

means connected to the outputs of a second selected set of logic elements in said matrix and responsive to conductive paths between said continuity signal source and the logic elements in said second set for providing an indication of a merger of two lines.

2. A system as in claim 1 wherein said second selected set of logic elements are the logic elements which comprise the periphery of said matrix.

3. A system as in claim 2 wherein each said logic element comprises:

OR circuit means responsive to a signal from logic elements located adjacent and orthogonal to said each logic element in said matrix; and

AND circuit means, responsive to a signal from said OR circuit means and to a binary signal from said converting means to cause said each logic element to be in an operated condition, for generating an output signal which activates the OR circuit means of each of said adjacent, orthogonally located logic elements;

whereby said conductive paths are formed between said continuity signal source and the periphery of said matrix by said operated logic elements.

4. A system as in claim 3 wherein said first selected set of logic elements comprise four logic elements which are located at the center of said matrix.

5. A system as in claim 3 wherein each said logic element comprises:

a set of field effect transistors;

the gates of said transistors being connected in common to said binary signal received from said conversion means; and

the sources of said transistors being both the inputs of said OR gate and the outputs of said AND gate.

6. A system as in claim 2 wherein said merger indication means comprises:

means for detecting the existence of three groups of binary signals from said periphery.

7. A system as in claim 6 wherein said indication means further comprises:

means for rejecting an indication of a merger if one of said groups contains more than a predetermined number of signals.

8. A system as in claim 1 further comprising:

means for inverting the polarity of said binary signals and having an output;

second continuity logic means including a matrix of logic elements operative in response to said inverted binary signals for forming conductive paths corresponding to the contrast between said lines and spaces; and

means connected to the outputs of selected logic elements of said second continuity logic means and responsive to said conductive paths for providing an indication of a split between two merged lines.

9. A system as in claim 8 wherein said split indication means comprises:

means for detecting the existence of a single group of binary signals from the logic elements which comprise the periphery of said matrix of said second continuity logic means.

10. A system as in claim 9 wherein said indication means further comprises:

means for rejecting an indication of a split if said group contains more than a predetermined number of signals.

11. A system for recognizing tHe merger of two lines in a pattern consisting of lines and spaces between lines comprising:

scanning means for scanning said pattern and having a scanning output;

means for converting the output of said scanning means into binary signals representative of the contrast between said lines and said spaces;

means for inverting the polarity of said binary signals;

first continuity logic means responsive to said inverted binary signals for detecting the three-line pattern indicative of the merger of two lines;

second continuity logic means responsive to said binary signals for detecting the space between said merged lines;

said first and second continuity logic means each comprising;

a matrix of logic elements; and

a source of potential;

each of said logic elements having an output which is energizable by the combination of a binary signal received from said converting means and said source of potential;

first decision means connected to the outputs of the logic elements located on the periphery of the matrix of said first continuity logic means for signalling the existence of said three-line pattern; and

second decision means connected to the outputs of the logic elements located on the periphery of the matrix of said second continuity logic means for signalling the existence of said space between said merged lines.

12. A system as in claim 11 wherein:

said first decision means further comprise means for suppressing said three-line pattern signal if any one of said lines exceeds a predetermined width; and

said second decision means further comprise means for suppressing said space signal if said space exceeds a predetermined width.

13. A system for recognizing the merger of two lines in a pattern consisting of lines and spaces between lines comprising:

scanning means for scanning said pattern and having a scanning output;

means for converting the output of said scanning means into binary signals representative of the contrast between said lines and said spaces;

means for inverting the polarity of said binary signals;

first continuity logic means responsive to said inverted binary signals for detecting the three-line pattern indicative of the merger of two lines;

second continuity logic means responsive to said binary signals for detecting the space between said merged lines;

said first and second continuity logic means each comprising;

a matrix of logic elements; and

a source of potential;

each of said logic elements being energizable by the combination of a binary signal received from said converting means and said source of potential;

each said source of potential being directly connected to four logic elements which are located at the center of its associated matrix.

14. A system for recognizing minutiae in a fingerprint comprising:

means for sensing selected areas of said fingerprint and having an output for generating binary signals representative of the contrast between ridges and valleys in said fingerprint;

continuity logic means responsive to said sensing output for forming conductive paths corresponding to the contrast between ridges and valleys including;

a matrix of logic elements;

a source of a continuity signal;

each said logic element in said matrix generating an output signal to the inputs of the logic elements located adjacent and orthogonal thereto in response to the combination of a binary signal from said sensing means and said continuity signal;

said continuity signal source being directly connected only to the inputs of a first set of logic elements in said matrix;

whereby said continuity signal source is electrically connected to the inputs of the logic elements outside said first set when at least one of said first set of logic elements generates an output signal; and

means connected to the outputs of a second selected set of logic elements in said matrix and responsive to conductive patHs between said continuity signal source and the logic elements in said second set for providing an indication of a minutia.

15. A system as in claim 14 wherein said second selected set of logic elements are the logic elements which comprise the periphery of said matrix.

16. A system as in claim 15 wherein each said logic element comprises:

OR circuit means responsive to a signal from logic elements located adjacent and orthogonal to said each element in said matrix; and

AND circuit means, responsive to a signal from said OR circuit means and to a binary signal from said sensing means to cause said each logic element to be in an operated condition, for generating an output signal which actuates the OR circuit means of each of said adjacent, orthogonally located logic elements;

whereby said conductive paths are formed between said continuity signal source and the periphery of said matrix by said operated logic elements.

17. A system as in claim 16 wherein said first selected set of logic elements comprise four logic elements which are located at the center of said matrix.

18. A system as in claim 16 wherein each said logic element comprises:

a set of field effect transistors;

the gates of said transistors being connected in common to said binary signal received from said sensing means; and

the sources of said transistors being both the inputs of said OR gate and the outputs of said AND gate.

19. A system as in claim 15 wherein said minutia indication means comprises:

means for detecting the existence of a single group of binary signals from said periphery.

20. A system as in claim 19 wherein said indication means further comprises:

means for rejecting an indication of a minutia if said group contains more than a predetermined number of signals.

21. A system as in claim 14 further comprising:

means for inverting the polarity of said binary signals and having an output;

second continuity logic means including a matrix of logic elements operative in response to said inverted binary signals for forming conductive paths corresponding to the contrast between ridges and valleys; and

means connected to the outputs of selected logic elements of said second continuity logic means and responsive to said conductive paths for providing an indication of a bifurcation in a minutia.

22. A system as in claim 21 wherein said bifurcation indication means comprises:

means for detecting the existence of three groups of binary signals from the logic elements which comprise the periphery of said matrix of said second continuity logic means.

23. A system as in claim 22 wherein said indication means further comprises:

means for rejecting an indication of a bifurcation if one of said groups contains more than a predetermined number of signals.

24. A continuity logic network adapted to generate indications of patterns of binary signals impressed thereon comprising:

a matrix of logic circuits, each said circuit including an AND gate and an OR gate said AND gate having a first input from the output of said OR gate;

the inputs of each said OR gate connected to the outputs of the AND gates of circuits located adjacent and orthogonally with respect to said each circuit;

the output of said AND gate in each circuit being connected to the input of the OR gate of each of the circuits located adjacent and orthogonally with respect to said circuit;

each said AND gate having a second input responsive to an external binary signal;

each said circuit comprising a set of field effect transistors;

the gates of said transistors being connected to said external signal; and

the sources of said transistors being the inputs of said OR gate and the outputs of said AND gate;

whereby each said logic circuit in said matrix generates an output signal whenever said external signal is in one binary state an at least one of said adjacent and orthogonal logic circuitS is in the same binary state.

25. A continuity logic network adapted to generate indications of patterns of binary signals impressed thereon comprising:

a matrix of logic circuits, each said circuit including an AND gate and an OR gate said AND gate having a first input from said OR gate;

the inputs of each said OR gate connected to the outputs of the AND gates of circuits located adjacent and orthogonally with respect to said each circuit;

the output of said ANd gate in each circuit being connected to the input of the OR gate of each of the circuits located adjacent and orthogonally with respect to said circuit;

each said AND gate having a second input responsive to an external binary signal;

continuity signal means comprising a source of potential directly connected to the input of the OR gates of four adjacent logic circuits which are located at the center of the said matrix;

whereby each said logic circuit in said matrix generates an output signal whenever the external signal to which it is responsive is in one binary state, at least one of said adjacent and orthogonal logic circuits is in said one binary state and one of said four centrally located circuits receives an external signal in said one binary state.

26. A network as in claim 25 wherein each said circuit comprises a set of field effect transistors;

the gates of said transistors being connected to said external signal; and

the sources of said transistors being the inputs of said OR gate and the outputs of said AND gate.

27. A network as in claim 26 wherein the drains of said sets of field effect transistors which comprise the peripheral circuits of said matrix function as outputs indicative of the state of continuous conductive paths from said continuity signal means to said peripheral circuits.

28. A system for recognizing the merger of two lines in a pattern consisting of lines and spaces between lines comprising:

scanning means for scanning said pattern and having a scanning output;

means for converting the output of said scanning means into binary signals representative of the contrast between said lines and said spaces;

continuity logic means for forming conductive paths corresponding to the contrast between said lines and spaces including;

a matrix of logic elements;

a source of a continuity signal;

each said logic element in said matrix generating an output signal to the inputs of predetermined other logic elements in said matrix in response to the combination of a binary signal from said scanning means and said continuity signal;

said continuity signal source being directly connected only to the inputs of a first set of logic elements in said matrix;

whereby said continuity signal source is electrically connected to the inputs of the logic elements outside of said first set only when at least one of said first set of logic elements generates an output signal; and

means connected to the outputs of the logic elements located at the periphery of said matrix and responsive to conductive paths between said continuity signal source and the peripheral logic elements for providing an indication of a merger of two lines;

said merger indication means comprising means for detecting the existence of three groups of binary signals from said periphery.

29. A system as in claim 28 wherein said merger indicator means further comprises means for rejecting an indication of a merger if at least one of said groups contains more than a predetermined number of signals.

30. A system for recognizing the merger of two lines in a pattern consisting of lines and spaces between lines comprising:

scanning means for scanning said pattern and having a scanning output;

means for converting the output of said scanning means into binary signals representative of the contrast between said lines and said spaces;

means for inverting the polarity of said binary signals;

first and secOnd continuity logic means for forming conductive paths corresponding to the contrast between said lines and spaces, each said continuity logic means including;

a matrix of logic elements;

a source of a continuity signal;

each said logic element in said first and second matrices generating an output signal to the inputs of predetermined other logic elements in said respective matrices in response to the combination of said continuity signal and a binary signal from said converting means and said inverting means, respectively;

each said continuity signal source being directly connected only to the inputs of a first set of logic elements in its associated matrix;

whereby said continuity signal source is electrically connected to the inputs of the logic elements outside of said first set only when at least one of said first set of logic elements generates an output signal;

means connected to the outputs of logic elements located at the periphery of said second continuity logic means and responsive to conductive paths between said continuity signal source of said second continuity logic means and the peripheral logic elements for providing an indication of a merger of two lines;

means connected to the outputs of logic elements located at the periphery of said first continuity logic means and responsive to conductive paths between said continuity source of said first continuity logic means and the peripheral logic elements for providing an indication of a split between two merged lines;

said split indication means comprising means for detecting the existence of a single group of binary signals from said peripheral logic elements of said second continuity logic means.

31. A system as in claim 30 wherein said split indication means further comprises:

means for rejecting an indication of a split if said group contains more than a predetermined number of signals.

32. A system for recognizing minutiae in a fingerprint comprising:

means for sensing selected areas of said fingerprint and having an output for generating binary signals representative of the contrast between ridges and valleys in said fingerprint;

continuity logic means responsive to said sensing output for forming conductive paths corresponding to the contrast between ridges and valleys including;

a matrix of logic elements;

a source of a continuity signal;

each said logic element in said matrix generating an output signal to the inputs of predetermined other logic elements in said matrix in response to the combination of a binary signal from said sensing means and said continuity signal;

said continuity signal source being directly connected only to the inputs of a first set of logic elements in said matrix;

whereby said continuity signal source is electrically connected to the inputs of the logic elements outside of said first set only when at least one of said first set of logic elements generates an output signal; and

means connected to the outputs of logic elements located at the periphery of said matrix and responsive to conductive paths between said continuity signal source and the peripheral logic elements for providing an indication of a minutia;

said minutia indication means comprising means for detecting the existence of three groups of binary signals from said periphery.

33. A system as in claim 32 wherein said minutia indication means further comprises means for rejecting an indication of a minutia if at least one of said groups contains more than a predetermined number of signals.

34. A system for recognizing minutiae in a fingerprint comprising:

means for sensing selected areas of said fingerprint and having an output for generating binary signals representative of the contrast between ridges and valleys in said fingerprint;

means for inverting the polarity of said signals and having an output;

first and second continuity logic means for forming conductive paths corresponding to the contrast Between said ridges and valleys, each said continuity logic means including;

a matrix of logic elements;

a source of a continuity signal;

each said logic element in said first and second matrices generating an output signal to the inputs of predetermined other logic elements in said respective matrices in response to the combination of said continuity signal and a binary signal from said sensing means and said inverting means, respectively;

each said continuity signal source being directly connected only to the inputs of a first set of logic elements in its associated matrix, whereby each said continuity signal source is electrically connected to the inputs of the logic elements outside of said first set in its respective matri only when at least one of said first set of logic elements generates an output signal; and

means connected to the outputs of logic elements located at the periphery of said first continuity logic means and responsive to conductive paths between said continuity signal source of said first continuity logic means and the peripheral logic elements in said first minutia;

means connected to the outputs of logic elements located at the periphery of said second continuity logic means and responsive to conductive paths between said continuity signal source of said second continuity logic means and the peripheral logic elements in said second matrix for providing an indication of a bifurcation in a minutia;

said bifurcation indication means comprising means for detecting the existence of a three groups of binary signals from said peripheral logic elements of said second matrix.

35. A system as in claim 34 wherein said bifurcation indication means further comprises:

means for rejecting an indication of a bifurcation if at least one of said groups contains more than a predetermined number of signals.