Glass patterns in image alignment and analysis

• US 5,613,013 A
• Filed: 05/13/1994
• Issued: 03/18/1997
• Est. Priority Date: 05/13/1994
• Status: Expired due to Term

• Current Assignee: Reticula Corporation
• Original Assignee: Reticula Corporation
• Inventors: Schuette, Wade
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Do, Anh Hong
• Application Number:
  US08/242,565
• Time in Patent Office: 1,040 Days
• Field of Search: 382/41, 382/44, 382/46, 382/4, 382/45, 382/276, 382/293, 382/296, 382/295, 382/124, 356/363, 356/374
• US Class Current: 382/124
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 10/42 Global feature extraction by analysis of the whole pattern, e.g. using frequency domain transformations or autocorrelation

Abstract

A system and method is provided for aligning and analyzing multiple images using Glass patterns. A Glass pattern is a Moire-like pattern obtained by superimposing an image on a transformed version of itself. The method includes superimposing the images to produce a first Glass pattern which has a determinable reference point, repositioning at least one of the images to produce a subsequent Glass pattern having a different reference point, and simultaneously aligning the reference points of each of the Glass patterns so as to align the images. The reference points are determined by any of a number of methods including the use of Fourier Transforms. In various embodiments of the invention, information obtained from the nature and quality of the Glass patterns produced is utilized for image analysis without aligning the images.

Claims

1. A method of aligning first and second images containing randomly distributed features wherein the first image is a transformed version of the second image, and neither image is required to contain a periodic pattern, the method comprising:

superimposing the images to form a composite image in which a first Glass pattern having a determinable reference point is produced, said reference point, in turn, defining a pair of matching points, said matching point in each of the two superimposed images being defined to be point in said image collocated at that time with said reference point in said composite image;

repositioning at least once at least one of the images so that superimposition of the randomly distributed features from the superimposed images produces a subsequent composite image having a subsequent Glass pattern having, in turn, a determinable reference point, defining, in turn, a pair of matching points, said pair of matching points being different from the pairs of matching points determined in preceding repositionings; and

applying a smooth warping transformation to at least one of the images so as to simultaneously align each pair of matching points in the images so as to align the images.

2. The method of claim 1 wherein simultaneously aligning the reference points comprises determining a relationship between the reference points of the first Glass pattern which relationship also exists between the reference points of the subsequent Glass patterns.

3. The method of claim 2 wherein determining a relationship comprises determining a transformation which includes parameters for at least one of translating, rotating, scaling, and skewing at least one of the images.

4. The method of claim 1 wherein superimposing the images comprises:

creating a numerical representation of each image; and

combining the numerical representations of the images to generate a superimposition of the images.

5. The method of claim 4 wherein combining the numerical representations comprises summing corresponding numbers of the numerical representations.

6. The method of claim 1 wherein the step of superimposing the images includes utilizing a computer to determine a reference point.

7. The method of claim 6 wherein a reference point is determined by:

defining a plurality of test regions each having a corresponding center point, the plurality of test regions being disposed within the two superimposed images;

computing a Fourier transform for each of the plurality of test regions to generate a parallel line pattern having substantially equal line spacing within each of the plurality of test regions; and

utilizing the line spacing and the corresponding center point of each of the plurality of test regions to determine the reference point.

8. The method of claim 7 wherein defining a plurality of test regions includes positioning each test region adjacent to at least one other test region such that each point disposed within the images is located in one of the plurality of test regions.

9. The method of claim 7 wherein the steps of defining, computing, and utilizing, are repeated a predetermined number of times to monitor movement of the reference point.

10. The method of claim 1 further comprising processing at least one of the images so as to eliminate points which are not of interest as determined by a user of the method, processing being performed prior to superimposing the images.

11. The method of claim 10 wherein the images include pixels characterized by a contrast level and wherein processing at least one of the images prior to superimposing the images comprises adjusting the contrast level of the pixels so that each pixel is no more than half-saturated so as to prevent image saturation during the step of superimposing the images.

12. The method of claim 1 further comprising sparsification of at least one of the images so as to reduce the number of points considered during the alignment process, sparsification being performed prior to superimposing the images.

13. The method of claim 1 wherein the images are N-dimensional where N is an integer greater than unity.

14. The method of claim 1 further comprising:

selecting a subsequent image to be aligned with the most recently aligned image; and

repeating the steps of superimposing, repositioning, simultaneously aligning, and selecting, a predetermined number of times so as to align each image in a multiple image sequence.

15. The method of claim 1 further comprising transforming at least one of the images prior to superimposing the images so as to facilitate the formation of a particular Glass pattern.

16. The method of claim 1 further comprising processing the images after simultaneously aligning the reference points so as to enhance an image feature of interest.

17. The method of claim 1 wherein the selected number of subsequent reference points is determined as a function of the group of the Glass pattern produced.

18. The method of claim 1 wherein the selected number of subsequent reference points is specified by a user.

19. The method of claim 1 wherein the selected number of subsequent reference points is determined as a function of recently aligned images, the recently aligned images having similar characteristics to the plurality of images currently being aligned.

20. The method of claim 1 wherein one of the plurality of images has been rotated and translated relative to another image of the plurality of images and wherein the rotation and translation are in the same plane.

21. The method of claim 20 wherein the translation is coplanar with the two images and the rotation is about an axis orthogonal to the two images.

22. The method of claim 20 wherein the two images are coplanar and wherein the translation is along an axis orthogonal to the plane of the two images.

23. The method of claim 22 wherein the rotation is about an axis orthogonal to the plane of the two images.

24. The method of claim 1 wherein the plurality of images comprises two three-dimensional images each having first, second, and third axes each axis corresponding to a single dimension and wherein the second image is translated along its first and second axes relative to the first image.

25. The method of claim 24 wherein the first image is rotated about its third axis, its third axis being mutually orthogonal to the first and second axes of the first image.

26. The method of claim 1 wherein the plurality of images comprises two three-dimensional images and wherein the second image has been perspectively transformed relative to the first image.

27. The method of claim 1 wherein one of the plurality of images includes local distortions having an average value of zero.

28. The method of claim 1 wherein the plurality of images includes first and second images and wherein the first image has been transformed relative to the second image such that a sequential ordering of points in the first image

is maintained in the second image.

29. The method of claim 1 wherein repositioning at least one of the images includes utilizing knowledge of a particular image characteristic to facilitate the repositioning.

30. The method of claim 1 wherein each of the plurality of images represents at least one fingerprint.

31. The method of claim 30 wherein aligning the images is operative to locate a predefined fingerprint within a fingerprint database.

32. The method of claim 1 wherein each of the plurality of images represents at least one voice-print.

33. The method of claim 1 wherein each of the plurality of images represents range information acquired from at least one of a radar system and a sonar system.

34. A method of aligning a first image containing randomly distributed features and having a first coordinate system and a second image which is a transformed version of the first image and having a second coordinate system wherein neither image is required to contain a periodic pattern, comprising:

superimposing the images so that superimposition of the randomly distributed features in the superimposed images produce a first Glass pattern having a determinable reference point in each of the first and second coordinate systems;

for each of a selected number of subsequent reference points, which selected number is determined as a function of the group of the Glass pattern produced, repositioning at least one of the images so that superimposition of the randomly distributed features in the superimposed images produces a subsequent Glass pattern having a determinable reference point in each of the two images, the reference points of the subsequent Glass pattern being different from the reference points of the preceding Glass patterns; and

determining a transformation relating the first image to the second image utilizing the coordinates of the reference points, for aligning the reference points of the first Glass pattern and the reference points of the subsequent Glass patterns so as to align the images.

35. A method for determining the transformation parameters for aligning a first image containing randomly distributed features and having a first coordinate system and a second image which is a transformed version of the first image and having a second coordinate system where the second image is translated and rotated relative to the first image, wherein neither image is required to contain a periodic pattern, the method comprising:

superimposing the images so that superimposition of the randomly distributed features in the superimposed images produce a first bull'"'"'s-eye pattern having a determinable reference point in each of the two images;

determining the location of the reference point of the first bull'"'"'s-eye pattern in the first and second coordinate systems;

translating at least one of the images so that superimposition of the randomly distributed features in the superimposed images produce a second bull'"'"'s-eye pattern having a determinable reference point in each of the two images, the reference points of the second bull'"'"'s-eye pattern being different from the reference points of the first bull'"'"'s-eye pattern;

determining the location of the reference point of the second bull'"'"'s-eye pattern in the first and second coordinate systems; and

solving a set of simultaneous equations characterizing the relationship between the reference points in the first image and the corresponding reference points in the second image to yield the transformation parameters which relate each point in the first image to a corresponding point in the second image.

36. A method for determining the transformation parameters for aligning a first image containing randomly distributed features having a first coordinate system and a second image which is a transformed version of the first image and having a second coordinate system where the second image is translated and scaled by a uniform factor relative to the first image, wherein neither image is required to contain a periodic pattern, the method comprising:

superimposing the images so that superimposition of the randomly distributed features in the superimposed images produce a first starburst pattern having a determinable reference point in each of the two images;

determining the location of the reference point of the first starburst pattern in the first and second coordinate systems;

translating at least one of the images so that superimposition of the randomly distributed features in the images produce a second starburst pattern having a determinable reference point in each of the two images, the reference points of the second starburst pattern being different from the reference points of the first starburst pattern;

determining the location of the reference point of the second starburst pattern in the first and second coordinate systems; and

solving a set of simultaneous equations characterizing the relationship between the reference points in the first image and the corresponding reference points in the second image to yield the transformation parameters which relate each point in the first image to a corresponding point in the second image.

37. A method for aligning two cognitive maps each being represented as an image containing randomly distributed features, each image being a transformed version of the other image and having a corresponding coordinate system, wherein neither image is required to contain a periodic pattern, the method comprising:

superimposing the images so that superimposition of the randomly distributed features in the superimposed images produce a first Glass pattern having a determinable reference point in each of the two images;

for each of a selected number of subsequent reference points, which selected number is determined as a function of the group of the Glass pattern produced, repositioning at least one of the images so that superimposition of the randomly distributed features in the superimposed images produce a subsequent Glass pattern having a determinable reference point in each of the two images, the reference points of the subsequent Glass pattern being different from the reference points of the preceding Glass patterns; and

simultaneously aligning the reference points of each of the Glass patterns so as to align the images thereby aligning the cognitive maps.

38. The method of claim 37 wherein the cognitive maps are aligned to locate areas of common belief between the cognitive maps.

39. A method of aligning two images containing randomly distributed features wherein one of the images is a transformed version of the other image, each of the images having a plurality of points, superimposition of randomly distributed features of superimposed images producing a detectable Glass pattern having a determinable reference point upon transformation of the second image relative to the first image and superimposition thereupon, wherein neither image is required to contain a periodic pattern, the method comprising:

(a) mathematically associating a first coordinate system having a first origin with the first image so as to define coordinates within the first coordinate system for each of the plurality of points in the first image;

(b) mathematically associating a second coordinate system having a second origin with the second image so as to define coordinates within the second coordinate system for each of the plurality of points in the second image;

(c) further transforming at least one of the two images;

(d) superimposing the images produced by said step (c) so that the superimposition of randomly distributed features in the superimposed images produce a Glass pattern having a corresponding determinable reference point;

(e) determining coordinates for the reference point in the first and second coordinate systems;

(f) repeating said steps (c)-(e) a predetermined number of times so as to generate a set of reference points;

(g) generating an alignment transformation for the images based on the set of reference points; and

(h) applying the alignment transformation to one of the images so as to align the images.

40. The method of claim 39 further comprising preprocessing at least one of the two images to produce a corresponding reference image so as to enhance predetermined features of the at least one preprocessed image prior to said Step (a) for use in said Steps (a)-(h).

41. The method of claim 39 further comprising performing the following steps between said Steps (g) and (h):

applying the alignment transformation determined in said Step (g) to one of the two images to evaluate a global quality and a local quality of the alignment transformation; and

repeating said Steps (a)-(g) until the global quality and the local quality of the alignment transformation exceed corresponding predetermined quality parameters.

42. A method for aligning two photographic images containing randomly distributed features wherein one of the images is a transformed version of the other image, the images being captured one moveable translucent media, the images containing at least one identical portion having a substantially similar scale and a substantially similar viewpoint, superimposition of the randomly distributed features of superimposed images producing a detectable Glass pattern having a determinable reference point upon translation and rotation of the second image relative to the first image and superimposition thereupon, wherein neither image is required to contain a periodic pattern, the method comprising:

(a) placing the first image over the second image so as to superimpose the images;

(b) repeatedly moving the first image relative to the second image until a reference point of a Glass pattern is detected;

(c) capturing the reference point by inserting a threaded needle through each image at the location of the reference point, the thread allowing relative movement between the two images;

(d) repeating said steps (b) and (c) a predetermined number of times so as to generate a set of captured reference points; and

(e) substantially simultaneously pulling all threads taut so as to align all corresponding pairs of reference points in the set of captured reference points to align the two images.

43. The method of claim 42 further comprising (f) evaluating a global alignment quality by quantifying a deformation of the translucent media produced by said Step (e).

44. A system for aligning first and second images containing randomly distributed features wherein the first image is a transformed version of the second image, the system comprising:

a memory for storing data representative of each of the plurality of images, and for storing instructions which operate on the data; and

a processor in communication with the memory for executing the instructions, the instructions being operative to superimpose the images such that a first Glass pattern is produced by superimposition of the randomly distributed features in the superimposed images, the first Glass pattern having a determinable reference point in each of the two images, the instructions also being operative to repetitively reposition at least one of the images so that superimposition of the randomly distributed features in the superimposed images produce a subsequent Glass pattern for each repetition, each subsequent Glass pattern having a determinable reference point in each of the images, the reference points of the subsequent Glass pattern being different from the reference points of the preceding Glass patterns, the instructions also being operative to simultaneously align the reference points of each of the Glass patterns in the two images so as to align the images wherein neither image is required to contain a periodic pattern.

45. A system for aligning first and second images containing randomly distributed features wherein the first image is a transformed version of the second image, wherein neither image is required to contain a periodic pattern, the system comprising:

means for superimposing the images so that superimposition of the randomly distributed features in the superimposed images produce a first Glass pattern having a determinable reference point in each of the images;

means for repetitively repositioning at least one of the images so that superimposition of the randomly distributed features in the superimposed images produce subsequent Glass patterns having a determinable reference point in each of the plurality of images, the reference points of the subsequent Glass patterns being different from the reference points of the preceding Glass patterns; and

means for simultaneously aligning the reference points of each of the Glass patterns in the plurality of images so as to align the images.

46. A method for analyzing first and second images containing randomly distributed features wherein the first image is a transformed version of the second image, wherein neither image is required to contain a periodic pattern, the method comprising:

superimposing the images; and

detecting a first Glass pattern produced by superimposition of the randomly distributed features in the superimposed images, the glass pattern having a determinable reference point within each of the images so as to indicate a determinable relationship between the images.

47. The method of claim 46 further comprising identifying the Glass pattern as one of the members of the group consisting of a starburst pattern, an elliptical pattern, a circular pattern, a vortical pattern, and a hyperbolic pattern, so as to classify the determinable relationship.

48. The method of claim 46 wherein the at least two images includes a reference image, the method further comprising:

measuring a distance between the determinable reference point and a predetermined point in the reference image so as to indicate an absolute rotation of one of the plurality of images.