Method and apparatus for verifying identity using image correlation

Claim 2

An image correlation method for verifying the identity of an object, said method comprising the steps of: forming a reference image of a reference object; identifying a plurality of reference sections from said reference image, wherein the image data contained in each of said reference sections is distinct relative to the image data adjacent to and surrounding said reference section and is redetectable by virtue of its similarity with the image data of one or more subsequent images of said reference object; and then forming a verify image of an object whose identity is to be verified, wherein said verify image includes a plurality of verify regions each corresponding in position to one of said reference sections and each larger in extent than its corresponding reference section; determining a best-match location within each verify region at which the image data is most similar to the image data of its corresponding reference section; and verifying the identity of said object according to the degree of similarity between the image data of said best-match locations and said corresponding reference sections, and according to the degree of similarity between the relative positioning of said best-match locations and said corresponding reference sections.

Claim 3

A method as recited in claim 1 wherein said step of forming a reference image of a reference object includes the steps of first forming an image consisting of grey pixels having a plurality of brightness values on a grey scale ranging between black and white, and then converting said grey pixels into binary pixels having brightness values of black or white.

Claim 4

A method as recited in claim 2 wherein said step of converting said grey pixels into binary pixels includes the steps of first determining a local median grey value of a subfield of said reference image, and then converting each grey pixel within said subfield into a binary pixel according to its grey scale brightness value relative to said median grey value.

Claim 5

A method as recited in claim 1 wherein said step of identifying a plurality of reference sections includes the steps of: partitioning said reference image into a plurality of candidate reference sections from which said reference sections will be selected, performing an autocorrelation calculation for each candidate reference section to determine the degree of distinctiveness of said candidate reference section relative to a local region surrounding said candidate reference section, and selecting said reference sections from the most distinctive of said candidate reference sections based on the results of the autocorrelation calculations.

Claim 6

A method as recited in claim 4 wherein said step of performing an autocorrelation calculation for each candidate reference section includes the steps of computing a plurality of correlation values, wherein each correlation value is based on a comparison of the image data of said candidate reference section with the image data of an equal-sized area of said local region, and computing an autocorrelation score based on the highest correlation value computed within said local region but outside of a region near the location of said candidate reference section, wherein a high autocorrelation score indicates a locally non-distinct candidate reference section.

Claim 7

A method as recited in claim 5 wherein said step of computing a correlation value includes the step of a pixel-by-pixel comparison between the image data of said candidate reference section and the image data of said equal-sized area of said local region.

Claim 8

A method as recited in claim 5 wherein said step of forming a reference image of a reference object includes the step of forming an image consisting of grey pixels having a plurality of brightness values on a grey scale ranging between black and white, and wherein said step of a performing an autocorrelation calculation includes the step of converting the grey pixels of said candidate reference section and of said local region into binary pixels having brightness values of black or white prior to performing said step of computing correlation values.

Claim 9

A method as recited in claim 7 wherein said step of converting the grey pixels of said local region into binary pixels includes the steps of first determining a median grey value within said local region, and then converting each grey pixel of said local region into a binary pixel according to its grey scale brightness value relative to said median grey value.

Claim 10

A method as recited in claim 7 wherein said step of converting the grey pixels of said candidate reference section into binary pixels includes the step of trinarizing the image data of said candidate reference section by first determining a black-grey threshold value and a grey-white threshold value based on the distribution of grey scale brightness values within said candidate reference section, and then converting the grey scale pixels of said candidate reference section into black, grey, and white pixels according to their grey scale brightness values relative to said black-grey and grey-white threshold values.

Claim 11

A method as recited in claim 9 wherein said step of computing a correlation value includes the step of comparing the black pixels and white pixels of said candidate reference section to the black pixels and white pixels of said local region, adding the number of matches between black or white pixels of said candidate reference section and black or white pixels of said local region, and dividing by the number of black and white pixels of said candidate reference section, wherein the resulting value equals said correlation value.

Claim 12

A method as recited in claim 9 wherein said black-grey and grey-white threshold values are selected such that about one third of the grey scale pixels of said candidate reference section are converted into black pixels and about one third of the grey scale pixels of said candidate reference section are converted into white pixels.

Claim 13

A method as recited in claim 4 wherein said step of partitioning said reference image defines a plurality of candidate reference sections that overlap adjacent candidate reference sections, and wherein said step of selecting said reference sections from the most distinctive of said candidate reference sections includes the step of rejecting candidate reference sections that overlap by more than a minimal amount other candidate reference sections having higher degrees of local distinctiveness.

Claim 14

A method as recited in claim 4 wherein said step of forming a reference image of a reference object includes the step of forming an image consisting of grey pixels having a plurality of brightness values on a grey scale ranging between black and white, and wherein said method further comprises the step of rejecting certain candidate reference sections based on the grey scale values of the pixels within said candidate reference sections.

Claim 15

A method as recited in claim 13 wherein said step of rejecting candidate reference sections includes the step of rejecting a candidate reference section if the median grey value within said candidate reference section is either too light or too dark.

Claim 16

A method as recited in claim 14 wherein said step of rejecting a candidate reference section if said median grey value is too light eliminates candidate reference sections at the edge of said reference image, and wherein said step of rejecting candidate reference sections includes the step of rejecting a candidate reference section if said candidate reference section is too close to a candidate reference section that has been rejected as too light.

Claim 17

A method as recited in claim 13 wherein said step of rejecting candidate reference sections includes the steps of first determining a black-grey threshold value and a grey-white threshold value based on the distribution of grey scale brightness values within a candidate reference section, wherein substantially one-third of the pixels of said candidate reference sections are darker than said black-grey threshold and substantially one-third of the pixels are lighter than said grey-white threshold, and then rejecting said candidate reference section if said black-grey and grey-white thresholds are too close in value.

Claim 18

A method as recited in claim 1 wherein said step of identifying a plurality of reference sections includes the steps of: partitioning said reference image into a plurality of candidate reference sections from which said reference sections will be selected, performing an autocorrelation calculation for each remaining candidate reference section to determine the degree of distinctiveness of said candidate reference section relative to a local region surrounding said candidate reference section, selecting a number of the most distinctive of said candidate reference sections based on the results of the autocorrelation calculations, measuring the redetectability of each of the remaining candidate reference sections with respect to one or more subsequent images of said reference object, and selecting said reference sections according to said degree of similarity between the image data of said remaining candidate reference sections and the image data of said one or more subsequent images.

Claim 19

A method as recited in claim 17 wherein said step of measuring the redetectability of each of the remaining candidate reference sections includes the steps of forming one or more subsequent images of said reference object and determining the degree of similarity between the image data of each of the remaining candidate reference sections and the image data of said one or more subsequent images.

Claim 20

A method as recited in claim 18 wherein said step of determining the degree of similarity between the image data of each of the remaining candidate reference sections and the image data of said one or more subsequent images includes for each of said subsequent images the step of determining best-match locations for said remaining candidate reference sections within corresponding search areas of said subsequent image, wherein each search area is a region of said subsequent image that surrounds the expected location of a corresponding candidate reference section, wherein each best-match location is the location within a search area at which the correlation is highest between the image data of a corresponding candidate reference section and the image data of the subsequent image, and wherein the correlation value computed at each best-match location is a measure of said degree of similarity.

Claim 21

A method as recited in claim 19 wherein said step of determining best-match locations for said remaining candidate reference sections within corresponding search areas of said subsequent image includes the steps of first determining the best-match location of one of said remaining candidate reference sections within a first search region of said subsequent image, wherein the deviation of the best-match location of said one candidate reference section from the expected location thereof defines a positional error of said subsequent image with respect to said reference image, and then determining the best-match locations of the rest of said remaining candidate reference sections with respect to said subsequent image by searching within second search regions for best-match locations, wherein said second search regions are located with reference to said positional error, and wherein said second search regions are smaller is size than said first search region.

Claim 22

A method as recited in claim 20 wherein said step of selecting said reference sections from the remaining candidate reference sections according to said degree of similarity between the image data of said reference sections and the image data of said one or more subsequent images includes the steps of sorting said remaining candidate reference sections according to the average of the correlation values computed at the best-match locations for each of said subsequent images, and then selecting a number of the highest ranked candidate reference sections as said reference sections.

Claim 23

A method as recited in claim 1 further comprising the step of storing the image and relative positioning data of each of said reference sections after said step of identifying a plurality of reference sections for later use in verifying the identity of objects.

Claim 24

A method as recited in claim 1 wherein said step of forming a verify image includes the steps of first forming an image consisting of grey pixels having a plurality of brightness values on a grey scale ranging between black and white, and then converting said grey pixels into binary pixels having brightness values of black or white.

Claim 25

A method as recited in claim 1 wherein said step of determining a best-match location within each verify region includes the steps of first determining the best-match location of one of said reference sections within a first verify region of said verify image, wherein the deviation of the best-match location of said one reference section from the expected location thereof defines a positional error of said verify image with respect to said reference image, and then determining the best-match locations of the rest of said reference sections with respect to said verify image by searching within second verify regions for best-match locations, wherein said second verify regions are located with reference to said positional error.

Claim 26

A method as recited in claim 24 wherein said second verify regions are smaller in size than said first verify region.

Claim 27

A method as recited in claim 24 wherein said step of first determining the best-match location of said one of said reference sections within said first verify region includes the steps of finding the highest correlation value within a subfield of said first verify region and specifying the best-match location as the location within said subfield at which said correlation value is highest if said highest correlation value exceeds a predetermined value, and if not, finding the highest correlation value with the entire first verify region and specifying the best-match location as that location within the entire first verify region at which the correlation value is highest, wherein each correlation value is a measure of the similarity between the image data of said one reference section and the image data of an equal-sized area of said first verify region.

Claim 28

A method as recited in claim 26 wherein said subfield is located within said first verify region at a location surrounding the expected location of said one reference section.

Claim 29

A method as recited in claim 1 wherein said step of determining a best-match location includes the steps of computing correlation values throughout said verify region, wherein each correlation value is a measure of the similarity between the image data of a reference section and the image data of an equal-sized area of the corresponding verify region, and specifying the best-match location as that location within said verify region at which the correlation value is highest.

Claim 30

A method as recited in claim 28 wherein said step of computing a correlation value includes the step of comparing pixel-by-pixel the image data of said reference section and the image data of an equal-sized area of said verify region.

Claim 31

A method as recited in claim 28 wherein said step of determining a best-match location includes the steps of first computing correlation values at selected locations distributed throughout said verify region and then computing correlation values at all possible locations near those locations where relatively high correlation values were found.

Claim 32

A method as recited in claim 1 wherein said step of forming a reference image of a reference object includes the step of forming an image consisting of grey pixels having a plurality of brightness values on a grey scale ranging between black and white, wherein said step of identifying a plurality of reference sections includes the step of converting the grey pixels of each reference section into binary pixels having brightness values of black or white, wherein said step of forming a verify image includes the steps of first forming an image consisting of grey pixels having a plurality of brightness values on a grey scale ranging between black and white, and then converting said grey pixels into binary pixels having brightness values of black or white, and wherein said step of determining a best-match location within each verify region includes the steps of computing correlation values throughout said verify region, wherein each correlation value is computed by a pixel-by-pixel comparison between the binary image data of said reference section and the binary image data of an equal-sized area of said verify region, and specifying the best-match location as that location within said verify region where the correlation value is highest.

Claim 33

A method as recited in claim 31 wherein said step of converting the grey pixels of each reference section into binary pixels includes the step of trinarizing the image data of a reference section by first determining a black-grey threshold value and a grey-white threshold value based on the distribution of grey scale brightness values within said reference section, and then converting the grey scale pixels of said reference section into black, grey, and white pixels according to their grey scale brightness values relative to said black-grey and grey-white threshold values.

Claim 34

A method as recited in claim 32 wherein said step of computing a correlation value includes the step of comparing the black pixels and white pixels of said reference section to the black pixels and white pixels of said verify region, adding the number of matches between black or white pixels of said reference section and black or white pixels of said verify region, and dividing by the number of black and white pixels of said reference section, wherein the resulting value equals said correlation value.

Claim 35

A method as recited in claim 1 wherein said step of determining a best-match location includes the steps of computing correlation values throughout said verify region, wherein each correlation value is a measure of the similarity between the image data of a reference section and the image data of an equal-sized area of the corresponding verify region, and specifying the best-match location as that location within said verify region where the correlation value is highest, and wherein said step of verifying the identity of said object includes the steps of first determining a displacement value for each of said reference sections, wherein each displacement value relates to the distance between the location of a reference segment within said reference image and the location of the corresponding best-match location within said verify image, and verifying that said object has the same identity as said reference object when said correlation values are relatively high and said displacement values are relatively low.

Claim 36

A method as recited in claim 34 wherein said step of verifying the identity of said object includes the step of adjusting said displacement values to correct for translational and rotational misalignment of said verify image with respect to said reference image.

Claim 37

A method as recited in claim 34 wherein said step of verifying the identity of said object includes the step of establishing a functional expression utilizing correlation values and displacement values so that each reference section can be classified as tending to verify or not depending on its corresponding correlation and displacement values relative to said functional expression, and wherein the identity of said object will be verified only when a predetermined number of said reference sections tend to verify object identity.

Claim 38

A method as recited in claim 36 wherein the identity of said object will be verified if a majority of said reference sections tend to verify.

Claim 39

A fingerprint verification method for verifying the identity of a person as recited in claim 1 wherein said step of forming a reference image of a reference object includes the step of forming an image of a fingerprint of a person seeking enrollment, and wherein said step of forming a verify image of an object whose identity is to be verified includes the step of forming an image of a fingerprint of a person seeking verification.

Claim 40

A fingerprint verification method for verifying the identity of a person by comparing presently obtained fingerprint data with previously obtained fingerprint data, said method comprising the steps of: first enrolling one or more persons by the steps of forming a reference image of a fingerprint of each enrolling person, identifying a plurality of reference sections from each reference image, wherein the image data contained in each reference section is distinct relative to the image data within a region surrounding said reference section and is redetectable by virtue of its similarity with the image data of one or more subsequent images of the fingerprint of said enrolling person, and saving the image and relative positioning data of each of said reference sections as fingerprint data for the enrolling person; and then verifying the identity of someone claiming to be an enrolled person by the steps of retrieving the image and relative positioning data of the reference sections of the enrolled person, forming a verify image of the fingerprint of the person claiming to be enrolled, wherein said verify image includes a plurality of verify regions each corresponding in position to one of said reference sections and each larger in extent than its corresponding reference section, determining a best-match location within each verify region at which the image data is most similar to the image data of its corresponding reference section, and verifying the identity of the person claiming to be enrolled according to the degree of similarity between the image data of said best-match locations and said corresponding reference sections and according to the degree of similarity between the relative positioning of said best-match locations and said corresponding reference sections.

Claim 41

A fingerprint verification method for verifying the identity of a person by comparing presently obtained fingerprint data with previously obtained fingerprint data, said method comprising the steps of: first enrolling one or more persons according to the steps of: forming a reference image of a fingerprint of a person seeking enrollment, partitioning said reference image into a plurality of candidate reference sections, determining the degree of distinctiveness of each candidate reference section within a local region surrounding said candidate reference section, determining the redetectability of each candidate reference section with respect to one or more subsequent images of the fingerprint of the person seeking enrollment by determining the degree of similarity between the image data of said candidate reference section and the image data of said one or more subsequent images, selecting a group of reference sections from said candidate reference sections according to the degree of distinctiveness and the degree of redetectability of said candidate reference sections, and saving the image and relative positioning data of each of the selected reference sections as fingerprint data for later use in verifying the identity of a person seeking verification; and later verifying the identity of a person seeking verification according to the steps of: obtaining an indication of which previously enrolled person that the person seeking verification claims to be, retrieving the image and relative positioning data of the reference sections of the previously enrolled person, forming a verify image of the fingerprint of the person seeking verification, wherein said verify image includes a plurality of verify regions each corresponding in relative position to and each larger in extent that a corresponding one of said reference sections, determining the best-match locations of said reference sections within their corresponding verify regions, wherein each best-match location is that location within a verify region at which the image data is most similar to the image data of the corresponding reference section, determining a displacement value for each of said reference sections, wherein each displacement value is a measure of the distance between the position of the best-match location and the expected position thereof, adjusting one or more of said displacement values to correct for misalignment of said verify image with respect to said reference image, classifying each reference section as tending to verify or not based on its corresponding correlation and displacement values, wherein relatively high correlation values and relatively low displacements tend to verify, and verifying the identity of the person seeking verification if at least a predetermined number of said reference sections are classified as tending to verify.

Claim 42

A fingerprint verification method for verifying the identity of a person by comparing presently obtained fingerprint data with previously obtained fingerprint data, said method comprising the steps of: first enrolling one or more persons according to the steps of: forming a reference image of a fingerprint of a person seeking enrollment, wherein said reference image consists of grey pixels having a plurality of brightness values on a grey scale ranging between black and white, partitioning said reference image into a plurality of candidate reference sections from which a set of reference sections will be selected, rejecting certain candidate reference sections based on the grey scale values of the pixels within said candidate reference sections, performing an autocorrelation calculation for each remaining candidate reference section to determine the degree of distinctiveness of said candidate reference section within a local region surrounding said candidate reference section, wherein said autocorrelation calculation includes the steps of computing a plurality of correlation values throughout said local region, wherein each correlation value is a measure of the similarity between the image data of said candidate reference section with the image data of an equal-sized area of said local region, and computing an autocorrelation score based on the highest correlation value computed within said local region but outside of a region near the location of said candidate reference section, wherein a high autocorrelation score indicates a locally non-distinct candidate reference section, selecting a number of the most distinctive of said candidate reference sections based on the results of the autocorrelation calculations, measuring the redetectability of each of the remaining candidate reference sections with respect to one or more subsequent images of the fingerprint of the person seeking enrollment by determining the degree of similarity between the image data of said remaining candidate reference sections and the image data of said one or more subsequent images, selecting a template of reference sections from the set of remaining candidate reference sections according to said redetectability of said remaining candidate reference sections with respect to said one or more subsequent images, and saving the image and relative positioning data of each of the selected reference sections as fingerprint data for later use in verifying the identity of a person seeking verification; and later verifying the identity of a person seeking verification according to the steps of: obtaining from the person seeking verification an indication of which previously enrolled person that the person seeking verification claims to be, retrieving the image and relative positioning data of the reference sections of the previously enrolled person, forming a verify image of the fingerprint of the person seeking verification, wherein said verify image includes a plurality of verify regions each corresponding in relative position to and each larger in extent than a corresponding one of said reference sections, determining the best-match locations of said reference sections within corresponding verify regions of said verify image, wherein each best-match location is that location within a verify region at which the image data is most similar to the image data of the corresponding reference section, wherein said best-match location is determined by the steps of computing correlation values throughout said verify region, wherein each correlation value is a measure of the similarity between the image data of said corresponding reference section and the image data of an equal-sized area of said verify region, and specifying the best-match location as that location within said verify region where the correlation value is highest, determining a displacement value for each of said reference sections, wherein each displacement value is a measure of the distance between the position of the best-match location and the expected position thereof, adjusting one or more of said displacement values to correct for misalignment of said verify image with respect to said reference image, classifying each reference section as tending to verify or not based on its corresponding correlation and displacement values, wherein relatively high correlation values and relatively low displacements tend to verify, and verifying the identity of the person seeking verification if at least a predetermined number of said reference sections are classified as tending to verify.

Claim 43

A method as recited in claim 41 wherein said step of a performing an autocorrelation calculation includes the steps of converting the grey pixels of said local region into binary pixels having brightness values of black or white and converting the grey scale pixels of said candidate reference section into trinary pixels having brightness values of black, grey, or white, and wherein said step of computing correlation values throughout said local region disregards the grey trinary pixels of said candidate reference sections.

Claim 44

A method as recited in claim 42 wherein each computation of a correlation value within said local region includes the step of comparing the black pixels and white pixels of said candidate reference section to the black pixels and white pixels of said local region, adding the number of matches between black or white pixels of said candidate reference section and respective black or white pixels of said local region, and dividing by the number of black pixels and white pixels of said candidate reference section, wherein the resulting value equals said correlation value.

Claim 45

A method as recited in claim 41 wherein said method further includes the step of converting the grey scale pixels of said reference sections into trinary pixels having brightness values of black, grey, or white, wherein said step of forming a verify image includes the step of forming an image with binary pixels having brightness values of black or white, and wherein said step of computing correlation values throughout each verify region disregards the grey trinary pixels of said reference sections.

Claim 46

A method as recited in claim 44 wherein each computation of a correlation value within said verify region includes the step of comparing the black pixels and white pixels of said reference section to the black pixels and white pixels of said verify region, adding the number of matches between black or white pixels of said reference section and respective black or white pixels of said verify region, and dividing by the number of black pixels and white pixels of said reference section, wherein the resulting value equals said correlation value.

Claim 47

A method as recited in claim 41 wherein said step of determining the best-match locations of said reference sections within respective verify regions of said verify image includes the steps of determining a first best-match location of one of said reference sections within a corresponding first verify region of said verify image, and then locating the rest of said verify regions relative to said first best-match location, and then determining the best-match locations of the rest of said reference sections.

Claim 48

A method as recited in claim 46 wherein said step of adjusting said displacement values to correct for misalignment of said verify image includes the step of adjusting for rotational misalignment of said verify image by finding a rotated position of said template of reference sections with respect to said verify image at which sum of the squares of the displacement values is minimized.

Claim 49

A fingerprint verification method for verifying the identity of a person by comparing presently obtained fingerprint data with previously obtained fingerprint data, said method comprising the steps of: first enrolling one or more persons according to the steps of: forming a reference image of the ridges and valleys of a fingerprint of a person seeking enrollment, wherein said reference image consists of grey pixels having a plurality of brightness values on a grey scale ranging between black and white, and wherein said fingerprint ridges and valleys are represented by brightness values tending toward black or white, partitioning said reference image into a plurality of candidate reference sections from which a set of reference sections will be selected, rejecting certain candidate reference sections based on the grey scale values of the pixels within said candidate reference sections, performing an autocorrelation calculation for each remaining candidate reference section to determine the degree of distinctiveness of said candidate reference section within a local region surrounding said candidate reference section, wherein said autocorrelation calculation includes the steps of converting the grey pixels of said local region into binary pixels having brightness values of black or white, converting the grey scale pixels of said candidate reference section into trinary pixels having brightness values of black, grey, or white, computing a plurality of correlation values throughout said local region, wherein each correlation value is a measure of the similarity between the black and white trinary pixels of said candidate reference section with the black and white binary pixels of an equal-sized area of said local region, and computing an autocorrelation score based on the highest correlation value computed within said local region but outside of a region near the location of said candidate reference section, wherein a high autocorrelation score indicates a locally non-distinct candidate reference section; selecting a number of the most distinctive of said candidate reference sections based on the results of the autocorrelation calculations, measuring the redetectability of each of the remaining candidate reference sections with respect to one or more subsequent images of the fingerprint of the person seeking enrollment by determining the degree of similarity between the image data of said remaining candidate reference sections and the image data of said one or more subsequent images, selecting a template of reference sections from the set of remaining candidate reference sections according to said redetectability of said remaining candidate reference sections with respect to said one or more subsequent images, wherein the image data contained in each of said reference sections is locally unique, and saving the image and relative positioning data of each of the selected reference sections as fingerprint data for later use in verifying the identity of a person seeking verification; and later verifying the identity of a person seeking verification according to the steps of: obtaining from the person seeking verification an indication of which previously enrolled person that the person seeking verification claims to be, retrieving the image and relative positioning data of the reference sections of the previously enrolled person, forming a verify image of the ridges and valleys of the fingerprint of the person seeking verification, wherein said verify image includes binary pixels having brightness values of black or white to indicate said ridges and valleys, and wherein said verify image includes a plurality of verify regions each corresponding in relative position to and each larger in extent than a corresponding one of said reference sections, determining a first best-match location of one of said reference sections within a first verify region of said verify image, wherein each best-match location is that location within a verify region at which the image data is most similar to the image data of the corresponding reference section, wherein each best-match location is determined by the steps of computing correlation values throughout the verify region and specifying the first best-match location as that location within the verify region where the correlation value is highest, wherein each correlation value is a measure of the similarity between the black and white pixels of the reference section and the black and white pixels of an equal-sized area of the corresponding verify region, and then locating the rest of said verify regions relative to said first best-match location, and then determining the best-match locations of the rest of said reference sections with respect to said verify image by searching within the rest of said verify regions for best-match locations, determining a displacement value for each of said reference sections, wherein each displacement value is a measure of the distance between the position of the best-match location and the expected position thereof, adjusting one or more of said displacement values to correct for rotational misalignment of said verify image with respect to said reference image, classifying each reference section as tending to verify or not depending on its corresponding correlation and displacement values, wherein relatively high correlation values and relatively low displacement tend to verify, and verifying the identify of the person seeking verification if at least a predetermined number of said reference sections are classified as tending to verify.