Automatic pattern processing system

An automatic system for processing patterns characterized by respectively unique minutiae patterns and further characterized by contour lines forming patterns which are respectively classifiable into corresponding ones of a predetermined number of classification types, wherein said system comprises:

• means for providing pattern minutiae data and line contour data corresponding to a unique minutiae pattern and a contour line pattern characterizing a pattern for processing;
• means responsive to said line contour data for automatically classifying said pattern into one of said classification types;
• and
• means for automatically storing said presented pattern minutiae data according to the classification type of said pattern;
• said providing means including means for identifying contour lines in said pattern, means for determining average contour angle values of said identified contour lines for predetermined areas of said pattern, and means for storing said average contour values thereby defining said line contour data;
• said classifying means including means for scanning said lines of contour data, means for identifying the occurrence of tri-radii points from said scanned lines contour data and means for representing three contour lines uniquely associated with each identified tri-radii point.

An automatic system for verifying the identity of a pattern, with respect to a previously identified pattern comprising:

• means for representing a pattern to be verified;
• means for extracting pattern minutiae from said represented pattern;
• means for storing previously identified pattern data in addressable positions corresponding to the identity of said previously identified pattern;
• means for addressing said storing means to read out said stored pattern data;
• means for comparing said extracted minutiae with said read out data and producing an identity verification output when the patterns match, within predetermined limits;
• means for extracting contour data from said represented pattern including means for identifying contour lines in said represented pattern, means for determining average contour angle values of said identified contour lines for predetermined areas of said represented pattern and means for storing said average contour angle values thereby defining said line contour data;
• and
• means for classifying said represented pattern in accordance with said contour lines into corresponding ones of a predermined number of classification types, said classifying means including means of scanning line contour data, means for identifying the occurrence of tri-radii points from said scanned line contour data, means for representing three contour lines uniquely associated with each identified tri-radii point, means for comparing said represented contour lines with reference contour lines representing a plurality of classification types and means responsive to said comparing means for classifying said represented pattern.

An automatic system for identifying an individual according to dermatoglyphic patterns of that individual, comprising:

• means for representing a dermatoglyphic pattern of an individual to be identified;
• means for extracting pattern minutiae data from said represented pattern;
• means for storing dermatoglyphic pattern minutiae data corresponding to at least one previously identified individual;
• means for selectively addressing and retrieving said minutiae data stored in said storing means;
• means for comparing said extracted pattern minutiae data with said retrieved minutiae data from said storing means for said at least one previously identified individual;
• means for determining whether said compared data matches within predetermined limits and producing an identification output when said compared data matches;
• means for extracting contour data from said represented pattern including means for identifying contour lines in said represented pattern, means for determining average contour angle values of said identified contour lines for predetermined areas of said represented pattern and means for storing said average contour angle values thereby defining said line contour data;
• and
• means for classifying said represented pattern in accordance with said contour lines into corresponding ones of a predetermined number of classification types, said classifying means including means of scanning line contour data, means for identifying the occurrence of tri-radii points from said scanned line contour data, means for representing three contour lines uniquely associated with each identified tri-radii point, means for comparing said represented contour lines with reference contour lines representing a plurality of classification types and means responsive to said comparing means for classifying said represented pattern.

An automatic system for processing patterns characterized by respectively unique minutiae patterns and further characterized by contour lines forming patterns which are respectively classifiable into corresponding ones of a predetermined number of classification types, wherein said system comprises:

• means for scanning a pattern characterized by a unique minutiae pattern and a contour line pattern;
• means for automatically extracting pattern minutiae data corresponding to said minutiae pattern from said scanned pattern;
• means for automatically extracting contour data from said scanned pattern corresponding to said contour lines;
• means responsive to said line contour data for automatically classifying said scanned pattern into one of said classification types;
• and
• means for automatically storing said extracted pattern minutiae data according to the classification type of said scanned pattern;
• said contour data extracting means including means for determining average contour angle values of said contour lines for predetermined areas of said pattern;
• said classifying means including means for scanning said line contour data, means for identifying the occurrence of tri-radii points from said scanned line contour data, means for representing three contour lines uniquely associated with each identified tri-radii point, means for comparing said represented contour lines with reference contour lines representing said classification types and means responsive to said comparing means for classifying said scanned pattern.

An automatic system for processing fingerprint patterns which are each characterized by epidermal ridge lines forming a contour pattern classifiable into one of a predetermined number of classification types, wherein said system comprises:

• means for scanning a fingerprint;
• means for inputting identifying information corresponding to said scanned fingerprint;
• means for automatically extracting ridge contour data from said scanned fingerprint corresponding to said contour pattern;
• means responsive to said ridge contour data for automatically classifying said scanned pattern into one of said predetermined classification types;
• and
• means for automatically storing said identifying information according to said corresponding classification type;
• said ridge contour data extracting means including means for identifying contour lines in said scanned fingerprint, means for determining average contour angle values of said identified contour lines for predetermined areas of said scanned fingerprint and means for storing said average contour angle values thereby defining said line contour data;
• said classifying means includes means for scanning said line contour data, means for identifying the occurrence of tri-radii points from said scanned line contour data, means for representing three contour lines uniquely associated with each identified tri-radii point, means for comparing said represented contour lines with reference contour lines representing said predetermined number of classification types.

An automatic system for identifying a pattern characterized by a unique minutiae pattern, comprising:

• means for electrically representing a pattern to be identified;
• means for automatically extracting pattern minutiae data corresponding to said minutiae pattern from said electrically represented pattern;
• means for storing pattern minutiae data corresponding to at least one previously identified pattern;
• means for automatically comparing said extracted pattern minutiae data with said pattern minutiae data in said storing means corresponding to said at least one previously identified pattern;
• means for automatically determining the degree of match between said compared data and for automatically producing an output identifying said compared data with at least one previously identified pattern when said degree of match is determined to exceed a predetermined value;
• said patterns also being characterized by contour lines forming patterns which are classifiable into corresponding ones of a predetermined number of classification types;
• means for automatically extracting the line contour data corresponding to said contour line pattern from said electrically represented pattern;
• said storing means storing pattern minutiae data associated with a plurality of identified patterns according to their corresponding classification types;
• means responsive to said line contour data for classifying said represented pattern into one of said classification types;
• means responsive to said classifying means for addressing said storing means according to said one of said classification types;
• wherein said line contour data extracting means includes means for scanning said electrically represented pattern, means for identifying contour lines in said scanned pattern, means for determining average contour angle values of said identified contour lines for predetermined areas of said represented pattern and means for storing said average contour angle values, thereby defining said line contour data;
• and
• wherein said classifying means includes means for scanning said line contour data, means for identifying the occurrence of tri-radii points from said scanned line contour data, means for representing three contour lines uniquely associated with each identified tri-radii point, means for comparing said represented contour lines with reference contour lines representing a plurality of classification types, and means responsive to said comparing means for classifying said represented pattern.

An automatic system for identifying an unknown pattern by comparison with stored patterns, each such pattern being characterized uniquely by a minutiae pattern and a configuration of contour lines, wherein said system comprises:

• means for scanning an unknown pattern including means for imaging said unknown pattern and means for coverting said image into a binary bit stream of electrical signals in a line scan format representing said unknown pattern;
• means for automatically extracting minutiae data, describing said minutiae pattern from said scanned pattern;
• means for storing the minutiae data of each of a plurality of previously identified patterns in addressable locations;
• means for selectively addressing and retrieving said stored minutiae data;
• means for window scanning said binary bit stream to produce a window scan address;
• means for automatically comparing said extracted minutiae data with retrieved minutiae data corresponding to selected ones of said plurality of patterns in succession and indicating the identity of said corresponding pattern when said compared data matches within predetermined limits;
• said minutiae data extracting means, including preprogrammed means responsive to said window scan address for detecting the occurrence of minutiae in said scanned pattern, means responsive to said preprogrammed means for determining the location of said detected minutiae with respect to a defined corrdinate system and means for storing the location coordinate values for each of the detected minutiae;
• said minutia data extracting means defining a reference coordinate system and presenting said extracted minutiae data in an X, Y, .theta. format, wherein X and Y indicate coordinate locations of each detected minutia with respect to said defined coordinate system and .theta. indicates the angular orientation of each detected minutia with respect to said defined coordinate system;
• said storing means storing said retrievable minutiae data in an X, Y, .theta. format;
• said comparing means including means for automatically converting extracted minutiae data and said retrieved minutiae data into an RIV format, whereby each minutia is represented in terms of its surrounding minutiae in a surrounding neighborhood of a predetermined size;
• and
• said comparing means also including means for matching each minutia of said unknown pattern represented in an RIV format with each minutia of a selected previously identified pattern represented in an RIV format and producing a plurality of neighborhood comparison signals indicating the relative closeness of match and relative coordinate displacement between minutia neighborhoods of the compared patterns, and means responsive to the neighborhood comparison signals for developing output signals indicative of the relative closeness of match and the relative coordinate displacement of the compared patterns.

An automatic system for identifying an unknown pattern by comparison with stored patterns, each such pattern being characterized uniquely by a minutiae pattern and a configuration of contour lines, wherein said system comprises:

• means for scanning an unknown pattern;
• means for automatically extracting minutiae data, describing said minutiae patterns from said scanned pattern;
• means for storing the minutiae data from each of a plurality of previously identified patterns in addressable locations;
• means for selectively addressing and retrieving said minutiae data;
• means for automatically comparing said extracted minutiae data with retrieved minutiae data corresponding to selected ones of said plurality of patterns in succession and indicating the identity of said corresponding patterns when said compared data matches within predetermined limits;
• said extracting means defining a reference coordinate system and presenting said extracted minutiae data in an X, Y, .theta. format, wherein X and Y indicate coordinate locations of each detected minutia with respect to said defined coordinate system and .theta. indicates the angular orientation of each detected minutia with respect to said defined coordinate system;
• said storing means storing said retrievable minutiae data in an X, Y, .theta. format;
• said comparing means including means for automatically converting said extracted minutiae data and said retrieved minutiae data into an RIV format, whereby each minutiae is represented in terms of its surrounding minutiae in a surrounding neighborhood of a predetermined size;
• said comparing means also including means for matching each minutia of said unknown pattern represented in an RIV format with each minutia of a selected previously identified pattern represented in an RIV format and producing a plurality of neighborhood comparison signals indicating the relative closeness of match and relative coordinate displacement between minutia neighborhoods of the compared patterns, and means responsive to the neighborhood comparison signals for developing output signals indicative of the relative closeness of match and the relative coordinate displacement of the compared patterns;
• means for extracting contour data from said scanned pattern corresponding to said configuration of contour lines;
• means receiving said extracted contour data for classifying said unknown pattern into one of a predetermined number of classification types defined by reference pattern contour configurations, and producing a classification type output signal;
• said storing means defining classification bins corresponding to said predetermined number of classification types, said previously identified minutiae data being stored in corresponding classification bins according to the classification type of each previously identified pattern;
• said addressing and retrieving means receiving said classification type output signal from said classifying means for addressing said storing means at a corresponding classification bin and retrieving stored minutiae data from said addressed classification bin;
• wherein said scanning means includes means for imaging said unknown pattern and means for converting said image into a binary bit stream of electrical signals in a line scan format representing said unknown pattern;
• means for window scanning said binary bit stream for producing a window scan address;
• and
• said minutiae data extractor means including preprogrammed means responsive to said window scan address for detecting the occurrence of minutiae in said represented pattern, means responsive to said preprogrammed means for determining the location of said detected minutiae with respect to said defined coordinate system and means for storing the location coordinate values for each of the detected minutiae.

An automatic system for identifying a pattern characterized by a unique minutiae pattern, comprising:

• means for electrically representing a pattern to be identified including means for imaging said characterized pattern and means for converting said image into a binary bit stream of electrical signals and a line scan format representing said characterized pattern;
• means for automatically extracting pattern minutiae data corresponding to said minutiae pattern from said electrically represented pattern;
• means for storing pattern minutiae data corresponding to at least one previously identified pattern;
• means for automatically comparing said extracted pattern minutiae data with said pattern minutiae data in said storing means corresponding to said at least one previously identified pattern;
• means for window scanning said binary bit stream for producing a window scan address;
• said minutiae data extracting means including preprogrammed means responsive to said window scan address for detecting the occurrence of minutiae in said represented pattern, means responsive to said preprogrammed means for determining the location of said detected minutiae with respect to a defined coordinate system, means for storing the location coordinate values for each of the detected minutiae;
• means for automatically determing the degree of match between said compared data for automatically producting an output identifying said compared data with at least one previously identified pattern when said degree of match is determined to exceed a predetermined value;
• wherein said patterns are further characterized by contour lines forming patterns which are classifiable into corresponding ones of a predetermined number of classification types;
• said storing means includes a plurality of classification bins corresponding to said classification types and each said previously identified pattern has pattern minutiae data stored in a corresponding classification bin;
• and wherein
• said extracting means includes:
• means for automatically scanning said electrically represented pattern,
• means for automatically identifying contour lines in said scanned pattern,
• means for automatically determining the average contour angle values from said identified contour lines for predetermined areas of said represented pattern, and
• means for automatically storing said average contour angle values in a matrix format corresponding to said predetermined areas;
• said system further comprising:
• means for automatically classifying said represented pattern into one of said classification types according to said stored average contour angle values;
• and
• means for supplying a classification bin address to said storing means in accordance with said classification type of said represented pattern for designating the pattern minutiae data to be compared by said comparing means.

A method of identifying an unknown pattern, wherein each such pattern is characterized uniquely by a minutiae pattern and a configuration of contour lines, comprising the steps of:

• extracting minutiae data describing said minutiae pattern from said unknown pattern;
• storing minutiae data of each of a plurality of previously identified patterns in association with corresponding addresses enabling retrieval of the stored data;
• selectively addressing and retrieving said stored minutiae data;
• comparing said extracted minutiae data with retrieved minutiae data corresponding to selected ones of said plurality of patterns in succession and indicating a match when said compared data matches within predetermined limits;
• and
• indicating the identity of said corresponding pattern for each match indicated;
• wherein said step of extracting minutiae data includes the step of defining a reference coordinate system and said minutiae data is extracted in an X, Y, .theta. format, wherein X and Y indicate coordinate locations of each extracted minutia with respect to said defined coordinate system and .theta. indicates the angular orientation of each extracted minutia with respect to said defined coordinate system;
• said retrievable minutiae data being stored in an X, Y, .theta. format;
• said step of comparing including the step of converting said extracted minutiae data and said retrieved minutiae data into an RIV format, whereby each minutia is represented in terms of its surrounding minutiae in a surrounding neighborhood of a predetermined size, the step of matching each minutia of said unknown pattern represented in an RIV format with each minutia of a selected previously identified pattern represented in an RIV format to produce a plurality of neighborhood comparison signals indicating the relative closeness of match and relative coordinate displacement between minutiae neighborhoods of the corresponding patterns and the step of developing output signals indicative of the relative closeness of match and the relative coordinate displacement of the compared patterns in response to the neighborhood comparison signals;
• and further including the following steps:
• extracting contour data from said unknown pattern corresponding to said configuration of contour lines;
• storing said extracted contour data;
• identifying singularity points from said stored contour data;
• classifying said unknown pattern into one of a pre-determined number of classification types according to said identified singularity points;
• and
• said retrievable minutiae data being stored in classification bins defined as corresponding to said pre-determined number of classification types according to the classification type of each previously identified pattern;
• said step of addressing and retrieving said stored minutiae data being performed by addressing said stored minutiae data according to said classification type of said unknown pattern at a corresponding classification bin and retrieving stored minutiae data from said addressed classification bin.