Image Normalization For Computed Image Construction

• US 20070154072A1
• Filed: 11/17/2006
• Published: 07/05/2007
• Est. Priority Date: 11/17/2005
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Upek, Inc. (Apple Inc.)
• Inventors: Taraba, Peter, Subert, Martin, Corradini, Giovanni
• Granted Patent: US 7,809,211 B2
• Time in Patent Office: Days
• US Class Current: 382/124
• CPC Class Codes: G06V 40/1335 Combining adjacent partial images (e.g. slices) to create a composite input or reference pattern; Tracking a sweeping finger movement

Abstract

Image normalization examines the pixels of two frames, most commonly sequentially obtained sub-images, and mathematically determines the displacement of those pixels from the first frame to the second based on pixel data. The pixel data is obtained from a scanning device, and may be for example grayscale value. The image may be for example that of a user'"'"'s fingerprint, and the image normalization used to form a computed image of the fingerprint from a plurality of sub-images obtained from a fingerprint scanner. The computed image may be stored, compared to a reference frame or otherwise processed, for example for identifying the user.

Claims

1. A method for generating a computed image comprised of pixels arranged in a rectangular grid using a first image frame and second image frame following a displacement of said first image frame, said second image frame not aligned with said rectangular grid, each image frame comprising at least two rows of pixels, each pixel having measured pixel data associated therewith, comprising:

calculating the displacement between said first and second image frames using said pixel data from said first and second image frames;

calculating by interpolation, using at least said calculated displacement and said pixel data from said second image frame, pixel data for a third image frame aligned with said rectangular grid; and

generating said computed image using said third image frame.

2. The method of claim 1, wherein said third image frame is calculated from said calculated displacement and said pixel data from said first and second image frames.

3. The method of claim 1, wherein said computed image represents a reconstruction of a physical image, further comprising:

establishing a first row of data for said computed image from data obtained from said physical image; and

using said first row to establish the orientation of said rectangular grid and thereafter generating said computed image within said rectangular grid from said computed third frame.

4. The method of claim 1, wherein said first and second frames comprise first and second rows of pixels, said first row of each frame having a greater number of pixels than said second row of each frame.

5. The method of claim 1, wherein said first and second frames comprise first and second rows of pixels, and further wherein less than all of said pixels comprising said second row of pixels are used to calculate the displacement between said first and second image frames.

6. The method of claim 1, wherein said first and second frames comprise first and second rows of pixels, and wherein said step of calculating the displacement between said first and second image frames comprises using at least a pixel from said first and second rows of said first frame and a pixel from said second row of said second frame.

7. The method of claim 6, wherein said step of calculating the displacement between said first and second image frames further comprises using at least two pixels from said second row of said second frame.

8. A method for generating a computed image from a scanned image, comprising:

electronically sensing a first image portion proximate to a scanning device, to thereby obtain a first scanned sub-image, the first scanned sub-image including pixel data for at least two pixels thereof;

storing said first scanned sub-image as a first frame;

electronically sensing a second image portion proximate to said scanning device, to thereby obtain a second scanned sub-image, the second scanned sub-image including pixel data for at least two pixels thereof;

storing said second sub-image as a second frame;

determining the amount of movement in a first direction of said scanned image relative to said scanning device between sensing said first scanned image portion and sensing said second scanned image portion by directly calculating the amount from the pixel data for at least one pixel of said second frame with the pixel data for at least two pixels of said first frame;

associating the amount of movement with pixel data for the entire second frame when said amount of movement is at least equal to a threshold distance;

using said amount of movement and pixel data from said second frame to construct a third frame; and

locating said third frame in the computed image of said scanned image.

9. The method of claim 8, wherein said at least two pixels from the first frame are contiguous.

10. The method of claim 8, wherein the image moves by an amount α

in a first direction which is significantly greater than the amount the image moves in a second direction, the first and second directions being orthogonal, the first frame including a pixel having an attribute value of A and a second pixel having an attribute value of B, the second frame having an attribute value of C, and further wherein;

C=α

B+(1−

α

)A.

11. The method of claim 10, wherein the scanned image is captured by a scanning device having a width direction, and wherein said first direction is perpendicular to said width direction.

12. The method of claim 10 wherein the step of constructing a third frame comprises:

determining the pixel data value for pixels comprising said third frame.

13. The method of claim 12, wherein said step of determining the pixel data value comprises determining said pixel data value by interpolation using pixel data values from said first and second frames.

14. The method of claim 8, wherein the pixel data for each pixel comprises the grayscale value of the pixel.

15. A method for generating a computed image from a scanned image of a fingerprint, comprising:

electronically sensing a first fingerprint portion proximate to a scanning device, to thereby obtain a first sub-image, the first sub-image including pixel data for at least two pixels thereof;

storing said first sub-image as a first frame;

electronically sensing a second fingerprint portion proximate to said scanning device, to thereby obtain a second sub-image, the second sub-image including pixel data for at least two pixels thereof;

storing said second sub-image as a second frame;

determining the amount of movement in a first direction of said fingerprint relative to said scanning device between sensing said first fingerprint portion and sensing said second fingerprint portion by directly calculating the amount from the pixel data for at least one pixel of said second frame with the pixel data for at least two pixels of said first frame;

associating the amount of movement with pixel data for the entire second frame when said amount of movement is at least equal to a threshold distance;

using said amount of movement and pixel data from said second frame to construct a third frame; and

;

locating said third frame in the computed image of said fingerprint.

16. The method of claim 15, wherein said at least two pixels from the first frame are contiguous.

17. The method of claim 15, wherein the image moves by an amount α

in a first direction which is significantly greater than the amount the image moves in a second direction, the first and second directions being orthogonal, the first frame including a pixel having an attribute value of A and a second pixel having an attribute value of B, the second frame having an attribute value of C, and further wherein;

C=α

B+(1−

α

)A.

18. The method of claim 17, wherein the scanned image is captured by a scanning device having a width direction, and wherein said first direction is perpendicular to said width direction.

19. The method of claim 17 wherein the step of constructing a third frame comprises:

determining the pixel data value for pixels comprising said third frame.

20. The method of claim 19, wherein said step of determining the pixel data value comprises determining said pixel data value by interpolation using pixel data values from said first and second frames.

21. The method of claim 17, wherein the threshold distance is less than one pixel, further comprising the steps of:

prior to using said amount of movement to construct said third frame, if the amount of movement is at least equal to the threshold, adding that amount of movement to an accumulator, Σ

α

;

determining if Σ

α

≧

1, and if not;

electronically sensing a new second fingerprint portion proximate to said array, to thereby obtain a new second sub-image, the new second sub-image including pixel data for at least one pixel thereof;

storing said new second sub-image as the second frame;

determining the amount of movement in a first direction of said fingerprint relative to said scanning device by direct calculation using the pixel data for at least one pixel of said new second sub-image and the pixel data for at least two pixels of said first sub-image; and

returning to the step of adding the amount of movement to the accumulator and repeating that step and the steps thereafter; and

if so;

associating the value of Σ

α

with pixel data for the entire second frame; and

using the value of Σ

α

to locate said third frame in the computed image of said fingerprint.

22. The method of claim 21 wherein the step of using said amount of movement to locate said third frame in the computed image further comprises:

determining the pixel data value of at least one pixel in said third frame.

23. The method of claim 22, wherein said step of determining the pixel data value comprises determining said pixel data value by interpolation using pixel data values from said first and second frames.

24. The method of claim 15, wherein the relative motion of the fingerprint and the scanning device is in two orthogonal dimensions relative to one another, the movement in the first dimension being represented by α

and movement in the second dimension being represented by β

, and further comprising;

the first sub-image including pixel data for at least four pixels thereof, represented respectively by A, B, C, and D;

the pixel data for the at least one pixel of said second sub-image represented by E; and

said comparison comprising determining α and

β

from;

E=α

β

A+α

(1−

β

)B+β

(1−

α

)C+(1−

α

)(1−

β

)D.

25. The method of claim 24 wherein the step of constructing a third frame comprises:

determining the pixel data value for pixels comprising said third frame.

26. The method of claim 25, wherein said step of determining the pixel data value comprises determining said pixel data value by interpolation using pixel data values from said first and second frames.

27. The method of claim 24, wherein the threshold distance is less than one pixel, further comprising the steps of:

prior to using said amount of movement to construct said third frame, if the amount of movement is at least equal to the threshold, adding that amount of movement to an accumulator, Σ

α

;

determining if Σ

α

≧

1, and if not;

electronically sensing a new second fingerprint portion proximate to said array, to thereby obtain a new second sub-image, the new second sub-image including pixel data for at least one pixel thereof;

storing said new second sub-image as the second frame;

determining the amount of movement in a first direction of said fingerprint relative to said scanning device by direct calculation using the pixel data for at least one pixel of said new second sub-image and the pixel data for at least two pixels of said first sub-image; and

returning to the step of adding the amount of movement to the accumulator and repeating that step and the steps thereafter;

and if so;

associating the value of Σ

α

with pixel data for the entire second frame; and

using the value of Σ

α

to at least partially locate said third frame in the computed image of said fingerprint.

28. The method of claim 15, wherein the pixel data for each pixel comprises the grayscale value of the pixel.

29. A method of constructing a computed image of a fingerprint from pairs of a plurality of scanned sub-images of the fingerprint, a first sub-image including pixels forming a first frame arranged in at least two rows and a plurality of columns, a second sub-image including pixels forming a second frame arranged in at least two rows and a plurality of columns, each pixel having pixel data associated therewith, each sub-image displaced vertically from an adjacent sub-image by a distance M_v which less than the height of one pixel and horizontally by a distance M_h, comprising:

obtaining a first pair of sub-images;

calculating M_v and M_h from the pixel data of the first pair of sub-images;

adding M_v to an accumulator A_v, and adding M_h to an accumulator A_h if M_v is greater than a threshold value;

determining the pixel data that corresponds to A_v equal to one and A_h when A_v is equal to one, if A_v is greater than one;

setting A_v equal to A_v−

1 and A_h equal to zero; and

obtaining a new pair of sub-images.

30. The method of claim 29, wherein the step of determining the pixel data that corresponds to A_v, equal to one comprises interpolation.

31. The method of claim 29, wherein a first sub-image of the pair of sub-images includes a pixel having a pixel data value of A and a second pixel having a pixel data value of B, a second sub-image of the pair of sub-images includes a pixel having a pixel data value of C, and further wherein the step of calculating M_v and M_h from the pixel data comprises determining M_v from:

C=M_vB+(1−

M_v)A.

32. The method of claim 31, wherein a first sub-image of the pair of sub-images includes a pixel having a pixel data value of D and a second pixel having a pixel data value of E, a second sub-image of the pair of sub-images includes a pixel having a pixel data value of F, and further wherein the step of calculating M_v and M_h from the pixel data comprises determining M_h from:

F=M_hE+(1−

M_h)D.

33. The method of claim 29, wherein a first sub-image of the pair of sub-images includes four pixels having pixel data values of A, B, C, and D, respectively, a second sub-image of the pair of sub-images includes a pixel having a pixel data value of E, and further wherein the step of calculating M_v and M_h from the pixel data comprises the step of determining Mv and Mh from:

E=M_vM_hA+M_v(1−

M_h)B+M_h(1−

M_v)C+(1−

M_v) (1−

M_h)D.

34. The method of claim 29, wherein the computed image is comprised of a plurality of contiguous computed rows of data, each row spaced apart from it'"'"'s adjacent row by the height of one pixel, and further wherein A_v represents the vertical displacement of a frame of interest from the position of an immediately prior computed row.

35. The method of claim 34, wherein the vertical position of a row in the computed image is determined by adding 1 to the vertical position of the prior row, and the pixel data for each pixel of the row is the pixel data that corresponds to A_v equal to one and A_h.

36. The method of claim 29, wherein the pixel data for each pixel is the grayscale value of the pixel.

37. The method of claim 29, further comprising the step of constructing a computed image from the pixel data that corresponds to A_v equal to one.

38. The method of claim 37, wherein the step of constructing a computed image is performed after the step of determining the pixel data that corresponds to A_v equal to one for every pair of sub-images.

39. The method of claim 37, further comprising the step of comparing portions of the computed image to a reference image.

40. An apparatus for generating an image of a fingerprint from a plurality of image frames that are each a small fraction of an overall geometry of the fingerprint, comprising:

(a) an array of successively scanning electronic sensors for electronically sensing fingerprint portions proximate to the array that are a fraction in size in at least one dimension compared to an entire fingerprint;

(b) electronic memory, coupled to said sensors, for acquiring first and second image frames of raw image data when first and second fingerprint portions are respectively proximate to the array, and in which is stored a first set of sub-image pixels corresponding to said first fingerprint portion and for storing a second set of sub-image pixels corresponding to said second fingerprint portion;

(c) a discriminator coupled to said memory for permitting acquisition of said second image frame when not less than a threshold amount of movement is detected between successive scans of said sensor array and at least one pixel of movement is detected in at least one direction since acquiring said first image frame; and

(d) a processor for computing by interpolation the second sub-image pixels, including stitching together portions of pixels offset within said acquired second image frame with respect to said first sub-image pixels, such that said first and second sub-image pixels correspond to adjacent portions of said entire fingerprint, for generating one or more further sub-image pixels, and for assembling the first, second and further sub-image pixels to form a computed image of the entire fingerprint.

41. The apparatus of claim 40, wherein said discriminator determines to discard an image frame when less than said threshold amount of computed movement is detected between successive frames following use of that image frame to determine a displacement of said image frame from a previous image frame.

42. The apparatus of claim 40, wherein said discriminator determines to discard an interim image frame corresponding to an interim fingerprint portion between said first and second fingerprint portions following use of that interim image frame to determine a displacement of said interim image frame from a previous image frame when, prior to said electronic memory acquiring said second image frame, said discriminator detects less than one pixel of movement in said at least one direction since acquiring said first image frame.

43. The apparatus of claim 40, wherein said processor computes said movement perpendicular to a row of sensors in said sensor array as

44. The apparatus of claim 40, wherein said processor computes said movement in a direction comprising first and second component directions parallel to rows and columns of sensors in said sensor array, respectively, as E=α

β

_iA+α

(1−

β

)B+β

(1−

α

)C+(1−

β

)(1−

α

)D, where α and

β

are distances in said first and second directions, respectively, and N is a number of columns of pixels contained in one image frame.

45. One or more processor readable storage devices having processor readable code embodied thereon, said processor readable code for programming one or more processors to perform a fingerprint image normalization method for generating a computed image of a fingerprint from a plurality of sub-images that are each a small fraction of an overall geometry of the fingerprint, the method comprising:

electronically sensing a first fingerprint portion proximate to a scanning device, to thereby obtain a first sub-image, the first sub-image including pixel data for at least two pixels thereof;

storing said first sub-image as a first frame;

electronically sensing a second fingerprint portion proximate to said scanning device, to thereby obtain a second sub-image, the second sub-image including pixel data for at least two pixels thereof;

storing said second sub-image as a second frame;

determining the amount of movement in a first direction of said fingerprint relative to said scanning device between sensing said first fingerprint portion and sensing said second fingerprint portion by directly calculating the amount from the pixel data for at least one pixel of said second sub-image with the pixel data for at least two pixels of said first sub-image;

associating the amount of movement with pixel data for the entire second frame when said amount of movement is at least equal to a threshold distance; and

using said amount of movement to locate said second frame in the computed image of said fingerprint.