Method and apparatus for highly efficient representation and compression of images

• US 6,571,014 B1
• Filed: 04/21/1999
• Issued: 05/27/2003
• Est. Priority Date: 05/07/1998
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Larkin, Kieran Gerard
• Primary Examiner(s): Do, Anh Hong
• Application Number:
  US09/295,094
• Time in Patent Office: 1,497 Days
• Field of Search: 382/232, 382/113, 382/115, 382/116, 382/125, 382/124
• US Class Current: 382/232
• CPC Class Codes: A61B 5/117 Identification of persons methods or arrangements for recognising patterns, e.g. fingerprints, G06F18/00, G06V40/00; identification of persons by analysing their voice or speech G10L17/00
• CPC Class Codes: A61B 5/1171 based on the shapes or appearances of their bodies or parts thereof
• CPC Class Codes: A61B 5/7232 involving compression of the physiological signal, e.g. to extend the signal recording period
• CPC Class Codes: A61B 5/726 using Wavelet transforms
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: G06V 40/1347 Preprocessing; Feature extraction

Abstract

A method of encoding images such as fingerprint type images (FIG. 2) is disclosed. A phase map structure for the image is formed (FIG. 3) and any singularities (+1, 2, 0.5) in the phase map structure are removed to create a continuous phase map structure (FIG. 5). The structure of the singularities and the continuous phase map structure are then separately encoded to form an encoded representation (88) of the image (50). Preferably, the singularity encoding includes encoding a position of each singularity in addition to its order and orientation. The phase map structure can be of the form:

ƒ(x,y)=a(x,y)+b(x,y)cos(φ(x,y))+c(x,y)+n(x,y)

The significance map can further include a separate encoding of phase map magnitude components.

Claims

1. A method of encoding a fringe pattern image, said method comprising the steps of:

demodulating said image to provide a phase map structure of said image;

identifying and removing any singularities in said phase map structure to create a continuous phase map structure, wherein each of said singularities is removed by adding to said phase map structure a phase spiral of equal charge magnitude and opposite charge sign to said singularity being removed;

removing 2π

phase discontinuities from said continuous phase map; and

separately encoding said singularities and said continuous phase map structure as an encoded representation of said image.

2. A method according to claim 1, wherein encoding of said singularities includes encoding at least a position and order of each said singularity.

3. A method according to claim 1, further comprising encoding a significance map of a magnitude of said phase map structure.

4. A method according to claim 3, wherein said continuous phase map structure is separately encoded from significance map.

5. A method according to claim 3, wherein encoding of said continuous phase map structure is performed using said magnitude.

6. A method according to claim 1, wherein said image is of the form:

7. A method according to claim 1, wherein said image is selected from the group consisting of a fingerprint image, a synthetic aperture radar image, an ultrasonic image, a sonar image, an interferometry image, an astronomical image, a seismic image, and an image obtained from a non-destructive evaluation procedure.

8. A method of encoding an image, said method comprising the steps of:

(a) providing input data of an image;

(b) demodulating said input data to determine at least a phase mapping structure;

(c) identifying singularities within said phase mapping structure and retaining a separate record of said singularities;

(d) removing said singularities from said phase mapping structure to provide a continuous phase mapping structure;

(e) removing 2π

phase discontinuities from said phase mapping structure;

(f) encoding said continuous phase mapping structure; and

(g) associating said separate record of said singularities with said encoded continuous phase mapping structure to provide an encoded representation of said image.

9. A method according to claim 8, wherein said demodulating further comprises determining an amplitude mapping of said image, and said method comprises the further steps of:

(h) determining a significance mapping based on said amplitude mapping;

(i) encoding said significance mapping; and

(j) associating said encoded amplitude mapping with said separate record and said encoded continuous phase mapping to form part of said encoded representation.

10. A method according to claim 9, wherein step (f) is performed using said significance mapping.

11. A method according to claim 8, wherein each said singularity is represented by a corresponding position, order and orientation.

12. A method according to claim 11, wherein step (d) comprises adding to said phase map structure a phase spiral of equal charge magnitude and opposite charge sign to said singularity being removed.

13. A method according to claim 8, wherein step (f) comprises performing a discrete wavelet transform upon said continuous phase mapping.

14. A method according to claim 9, wherein step (i) comprises performing a discrete wavelet transform upon said significance mapping.

15. A method according to claim 10, wherein step (f) comprises parametrically compressing said continuous phase mapping.

16. A method according to claim 15, wherein said parametrically compressing utilizes one of an n-th order 2-dimensional polynomial (n=1,2,3 . . . ) on a spline fitting arrangement.

17. A method according to claim 8, wherein step (e) precedes steps (c) and (d).

18. A method of handling singularities forming parts of fringe maps, said method comprising the steps of:

demodulating said fringe map to provide a phase mapping structure of said fringe map;

identifying each singularity within said phase mapping structure and forming a corresponding record thereof; and

subtracting each said singularity from said phase mapping structure to form a continuous phase mapping structure, wherein each of said singularities is subtracted by adding to said phase map structure a phase spiral of equal charge magnitude and opposite charge sign to said singularity being subtracted.

19. A method according to claim 18, further comprising associating each said singularity record with a phase value from said continuous phase mapping structure at a location of said singularity record.

20. A method of processing a fringe map, said fringe map including at least one singularity, said method comprising:

performing the method of claim 19; and

processing at least one of;

(a) said corresponding records;

(b) said continuous phase mapping structure; and

(c) said associated records and said phase values.

21. A method of determining a match between an input fringe pattern image and one of a plurality of stored fringe pattern images, each of said images being represented in an encoded form comprising a residual phase mapping and a record of singularities in which each said singularity is associated with a residual phase value of said mapping at a location corresponding to said singularity, said method comprising the steps of:

comparing the record of singularities of said input fringe pattern image with the records of singularities of each said stored fringe pattern image to determine an output group of matching images;

decoding said input fringe pattern image and each image of said output group; and

comparing said input fringe pattern image with each image of said output group to determine a match between said input fringe pattern image and one image of said output group.

22. A method of decoding an encoded representation of an image, wherein said encoded representation comprises at least one phase singularity and encoded amplitude components, said method comprising the steps of:

(a) decoding said encoded representation to provide a phase map structure of said image;

(b) adding said singularities to said phase map structure;

(c) decoding said encoded amplitude components;

(d) combining said amplitude component with said phase map structure; and

(e) inverse transforming said phase map structure to form said image.

23. A method according to claim 22, wherein said phase map structure prior to step (e) is of the form:

24. Apparatus for encoding a fringe pattern image, said apparatus comprising:

first means for demodulating said image to provide a phase map structure of said image;

second means for identifying and removing any singularities in said phase map structure to create a continuous phase map structure, wherein each of said singularities is removed by adding to said phase map structure a phase spiral of equal charge magnitude and opposite charge sign to said singularity being removed;

third means for removing 2π

phase discontinuities from said continuous phase map; and

fourth means for separately encoding said singularities and said continuous phase map structure as an encoded representation of said image.

25. Apparatus according to claim 24, wherein said third means comprises fourth means for encoding said singularities including encoding at least a position and order of each said singularity.

26. Apparatus according to claim 24, further comprising fifth means for encoding a significance map of a magnitude of said phase map structure.

27. Apparatus according to claim 26, wherein said third means comprises sixth means for separately encoding said significance map from said continuous phase map structure.

28. Apparatus according to claim 26, wherein encoding of said continuous phase map structure is performed using said magnitude.

29. Apparatus according to claim 24, wherein said image is of the form:

30. Apparatus according to claim 24, wherein said image is selected from the group consisting of a fingerprint image, a synthetic aperture radar image, an ultrasonic image, a sonar image, an interferometry image, an astronomical image, a seismic image, and an image obtained from a non-destructive evaluation procedure.

31. Apparatus for encoding an image, said apparatus comprising:

a demodulator for demodulating said input data to determine at least a phase mapping structure;

means for identifying singularities within said phase mapping structure and retaining a separate record of said singularities;

means for removing said singularities from said phase mapping structure to provide a continuous phase mapping structure;

means for removing 2π

phase discontinuities from said phase mapping structure;

means for encoding said continuous phase mapping structure; and

means for associating said separate record of said singularities with said encoded continuous phase mapping structure to provide an encoded representation of said image.

32. Apparatus according to claim 31, wherein said demodulator is configured to determine an amplitude mapping of said image, said apparatus further comprising:

means for determining a significance mapping based on said amplitude mapping;

means for encoding said significance mapping; and

means for associating said encoded amplitude mapping with said separate record and said encoded continuous phase mapping to form part of said encoded representation.

33. Apparatus according to claim 32, wherein said means for encoding said continuous phase mapping structure utilizes said significance mapping.

34. Apparatus according to claim 31, wherein each said singularity is represented by a corresponding position, order and orientation.

35. Apparatus according to claim 34, wherein said means for removing adds to said phase map structure a phase spiral of equal charge magnitude and opposite charge sign to said singularity being removed.

36. Apparatus according to claim 31, wherein said means for encoding said continuous phase mapping structure performs a discrete wavelet.

37. Apparatus according to claim 32, wherein said means for encoding said significance mapping performs a discrete wavelet transform upon said significance mapping.

38. Apparatus according to claim 33, wherein the encoding of said continuous phase mapping structure comprises parametrically compressing said continuous phase mapping.

39. Apparatus according to claim 38, wherein said parametrically compressing utilizes one of an n-th order 2-dimensional polynomial (n=1,2,3 . . . ) on a spline fitting arrangement.

40. Apparatus for handling singularities forming parts of fringe maps, said apparatus comprising:

means for demodulating said fringe map to provide a phase mapping structure of said fringe map;

means for identifying each singularity within said phase mapping structure and forming a corresponding record thereof; and

means for subtracting each said singularity from said phase mapping structure to form a continuous phase mapping structure, wherein each of said singularities is removed by adding to said phase map structure a phase spiral of equal charge magnitude and opposite charge sign to said singularity being subtracting.

41. Apparatus according to claim 40, further comprising means for associating each said singularity record with a phase value from said continuous phase mapping structure at a location of said singularity record.

42. Apparatus for processing a fringe map, said fringe map including at least one singularity, said apparatus comprising:

apparatus according to claim 40; and

means for processing at least one of;

(a) said corresponding records;

(b) said continuous phase mapping structure; and

(c) said associated records and said phase values.

43. Apparatus for determining a match between an input fringe pattern image and one of a plurality of stored fringe pattern images, each of said images being represented in an encoded form comprising a residual phase mapping and a record of singularities in which each said singularity is associated with a residual phase value of said mapping at a location corresponding to said singularity, said apparatus comprising:

means for comparing the record of singularities of said input fringe pattern image with the records of singularities of each said stored image to determine an output group of matching images;

means for decoding said input fringe pattern image and each image of said output group; and

means for comparing said input fringe pattern image with each image of said output group to determine a match between said input fringe pattern image and one image of said output group.

44. Apparatus for decoding an encoded representation of an image, wherein said encoded representation comprises at least one phase singularity and encoded amplitude components, said apparatus comprising:

means for decoding said encoded representation to provide a phase map structure of said image;

means for adding said singularities to said phase map structure;

means for decoding said encoded amplitude components;

means for combining said amplitude component with said phase map structure; and

means for inverse transforming said phase map structure to form said image.

45. A computer readable medium incorporating a computer program product for encoding a fringe pattern image, said computer program product including:

code for demodulating said image to provide a phase map structure of said image;

code for identifying and removing any singularities in said phase map structure to create a continuous phase map structure, wherein each of said singularities is removed by adding to said phase map structure a phase spiral of equal charge magnitude and opposite charge sign to said singularity being removed;

code for removing 2π

phase discontinuities from said continuous phase map; and

code for separately encoding said singularities and said continuous phase map structure as an encoded representation of said image.

46. A computer readable medium incorporating a computer program product for handling singularities forming parts of a fringe map, said computer program product including:

code for demodulating said fringe map to provide a phase mapping structure of said fringe map;

code for identifying each singularity within said phase mapping structure and forming a corresponding record thereof; and

code for subtracting each said singularity from said phase mapping structure to form a continuous phase mapping structure, wherein each of said singularities is subtracted by adding to said phase map structure a phase spiral of equal charge magnitude and opposite charge sign to said singularity being subtracted.

47. A computer readable medium incorporating a computer program product for decoding an encoded representation of an image, wherein said encoded representation comprises at least one phase singularity and encoded amplitude components, said computer program product including:

code for decoding said encoded representation to provide a phase map structure of said image;

code for adding said singularities to said phase map structure;

code for decoding said encoded amplitude components;

code for combining said amplitude component with said phase map structure; and

code for inverse transforming said phase map structure to form said image.

48. An image representation system comprising an encoding arrangement for encoding an image by providing input data of said image;

demodulating said input data to determine at least a phase mapping structure;

identifying singularities within said phase mapping structure and retaining a separate record of said singularities;

removing said singularities from said phase mapping structure to provide a continuous phase mapping structure;

removing 2π

phase discontinuities from said phase mapping structure;

encoding said continuous phase mapping structure; and

associating said separate record of said singularities with said encoded continuous phase mapping structure to provide an encoded representation of said image; and

a decoding arrangement substantially complementing said encoding arrangement.

49. An image matching system, said system comprising:

(a) a database of compressed image data representing a plurality of images, the compressed image data for each said image including;

(i) a compressed residual phase map obtained by compressing a phase map from which singularities have been removed; and

(ii) a record of each said singularity removed from said phase map, said record including a position, order and orientation of each said singularity;

(b) means for extracting from said database for any one said image said record and associating with said position, order and orientation, a value of the local residual phase associated with said singularity;

(c) means for comparing the extracted position, order, orientation and local residual phase of said one image with corresponding values of an input image to determine a match therebetween.