Method and a device for matching images

• US 6,563,951 B2
• Filed: 02/17/1998
• Issued: 05/13/2003
• Est. Priority Date: 12/30/1997
• Status: Expired due to Fees

• Current Assignee: Anoto Group AB
• Original Assignee: C Technologies AB (Anoto Group AB)
• Inventors: Ericson, Petter, Fåhraeus, Christer, Hugosson, Ola
• Primary Examiner(s): Lee, Thomas D.
• Application Number:
  US09/024,641
• Publication Number:
  US 20010028741A1
• Time in Patent Office: 1,911 Days
• Field of Search: 382/318, 382/218, 382/219, 382/216, 382/294, 382/154, 382/217
• US Class Current: 382/216
• CPC Class Codes: G06V 10/12 Details of acquisition arrangements; Constructional details thereof
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 30/142 using hand-held instruments; Constructional details of the instruments

Abstract

In a method for matching two images, each consisting of a plurality of pixels and having partially overlapping contents, the degree of correspondence between the contents of the images is determined for different displacement positions representing different overlappings of the images. More specifically, a plurality of numbers are determined for each one of a plurality of said displacement positions. Each number is formed with the aid of pixel values from both images and is used to simultaneously retrieve predefined overlap assessment values for at least two of said displacement positions. The overlap assessment values retrieved are subsequently used to determine the degree of correspondence between the images for the different displacement positions. The method is carried out with the aid of a computer and can be implemented as a computer program.

Claims

1. A method for matching a first and a second image, each consisting of a plurality of binary pixels and having partially overlapping contents, the degree of correspondence between the contents of the images being determined for different displacement positions which represent different overlappings of the images, comprising the following steps:

determining a correlation score retrieval number for each of a plurality of coarse displacement positions of said first image relative to said second image, each correlation score retrieval number being determined from at least two pixel values from each image corresponding to each coarse displacement position,

using said correlation score retrieval number to retrieve corresponding predefined correlation scores for at least two fine displacement positions simultaneously, and

using the correlation scores in determining the degree of correspondence between the contents of the images.

2. A method according to claim 1, further comprising the steps of:

determining, at said coarse displacement position, a second correlation score retrieval number from at least two pixel values from each image different from said first correlation score retrieval number and retrieving a corresponding correlation score;

adding up the correlation scores for said coarse displacement position; and

using the totals obtained in this manner to determine which of coarse and fine displacement positions provide the best correspondence between the contents of the images.

3. A method according to claim 2, wherein the correlation scores are added up in parallel for a plurality of fine displacement positions.

4. A method according to claim 1, wherein at least one of the correlation scores relate to more than one overlapping pixel.

5. A method according to claim 1, further comprising the step of putting together the images in the displacement posit on which provides the best correspondence between the images.

6. A method according to claim 1, wherein the coarse displacement positions represent different overlappings of the images in a first direction, and further comprising the step of repeating the method for different overlappings of the images in a second direction.

7. A method according to claim 1, wherein the coarse displacement positions are determined by the images being divided into a plurality of coarse segments consisting of N×

M pixels, where N and M are greater than one, the displacement between two adjoining coarse displacement positions consisting of a coarse segment.

8. A method according to claim 1, wherein the correlation score retrieval numbers constitute addresses of memory locations, which store said correlation scores consisting of predefined values.

9. A method according to claim 8, wherein the addresses are employed to address at least one lookup table which, for each address, contains the predefined correlation scores for at least two fine displacement positions.

10. A method according to claim 9, which method is performed with the aid of a processor working with a pre-determined word length and wherein said at least one lookup table comprise a plurality of addressable rows, each having the predetermined word length and storing said predefined correlation scores.

11. A method according to claim 10, wherein the storing of the correlation scores is performed in such a manner that all correlation scores as well as the images which are to be matched can be contained in a cache memory in the processor.

12. A method according to claim 1, further comprising the step of forming each correlation score retrieval number of first fine segment, which comprises at least two adjoining pixel values from the first image, and of a second fine segment, which overlaps the first fine segment and which comprises as many adjoining pixel values as the first fine segment from the second image, and of a third fine segment, which comprises as many adjoining pixel values as the first fine segment from the second image and which overlaps the first fine segment in an adjacent displacement position, for which the determination of a plurality of correlation score retrieval numbers is carried out.

13. A method according to claim 12, wherein the correlation score retrieval numbers constitute addresses of memory locations which store said correlation scores consisting of predefined values and wherein each address is divided into a first and a second subaddress, the first subaddress, which consists of the pixel values from the first and the second fine segment, being used to simultaneously retrieve correlation scores in a first table for overlapping pixels belonging to the first and the second fine segment, and the second subaddress, which consists of the pixel values from the first and the third fine segment, being used to simultaneously retrieve correlation scores in a second table or overlapping pixels belonging to the first and the third segment.

14. A method according to claim 13, wherein, for each address, the first and the second table store a correlation score for each one of said at least two displacement positions, and wherein the sum of the correlation scores for a first displacement position, which is retrieved using the first and second sub-addresses of an address, constitutes a correlation score for all overlapping pixels between the first, the second, and the third fine segment for said first displacement position.

15. A method according to claim 1, wherein the degree of correspondence between the images is first determined with a first resolution of the images for selection of a plurality of displacement positions, and is subsequently determined with a second, higher resolution of the images for the displacement positions selected and adjoining displacement positions.

16. A device for matching a first and a second image, each consisting of a plurality of binary pixels and having partially overlapping contents, characterized by a processing unit which is adapted to implement a method according to claim 1.

17. A device for matching a first and a second image, each consisting of a plurality of binary pixels and having partially overlapping contents, which device comprises a storage medium, which is readable with the aid of a computer and in which is stored a compute program for implementing the method according to claim 1.

18. A method for determining the degree of correspondence between a first image and a second image, each image consisting of a plurality of binary pixels and having partially overlapping contents, comprising the following steps:

forming a score retrieval number using one or more pixel values from the first image and one or more pixel values from the second image;

using the score retrieval number to simultaneously retrieve at least two scores;

each score being a fixed correlation value for a relative displacement of the pixel values from the first image with respect to the pixel values from the second image; and

using the scores in determining the degree of correspondence between the contents of the first image and the second image.

19. A method of determining a correlation score for a first and a second image having partially overlapping contents, each image being stored in a memory in the form of a pixelmap each pixel being binary and having two conditions, one and zero, comprising the steps of:

selecting at least two pixels from the first image, forming at least two first bits,

selecting at east two pixels from the second image, forming at least two second bits;

forming a binary address by defining said at least two first bits as the least significant bits of said address and said at least two second bits as the most significant bits of said address; and

accessing a table by said binary address to retrieve at least one correlation score.

20. A method as claimed in claim 19, further comprising the steps of:

repeating the selection of pixels from said first and second images;

retrieving correlation scores from each combined selection; and

determining best match as the selection having the highest correlation score.

21. A method as claimed in claim 19, wherein the said correlation score of said table is precalculated by bitwise comparing said first bits and said second bits whereas if the bits in the bitpair are unequal, the score is zero, if the bits in the bitpair both are zero, the score is one, and if the bits in the bitpair both are one the score is two, and the scores for the bitpairs are summed to give the correlation score.

22. A method as claimed in claim 19, wherein said at least two pixels from said first and second images are adjacent pixels arranged in any one of a row and a column.

23. A method as claimed in claim 19, further comprising the steps of:

determining a coarse relative position between the images;

selecting said at least two pixels from said first image; and

selecting said at least two pixels from a corresponding position of said second image for retrieval of said at least one correlation score.

24. A method as claimed in claim 23, further comprising the steps of:

selecting, in said coarse relative position between the images, another at least two pixels from said first image and selecting another at least two pixels from said second image for retrieval of another at least one correlation score; and

adding said at least one correlation retrieval score and said another at least one correlation retrieval score.

25. A method as claimed in claim 23, wherein

said at least one correlation score comprises at least two correlation scores corresponding to fine displacements of the images relative to each other from said coarse relative position.

26. A method as claimed in claim 19, wherein said at least two pixels comprises five pixels.

27. A method as claimed in claim 19, further comprising the steps of:

assembling the images in the displacement position which provides the best correspondence between the images.

28. A device for determining a match between a first and a second image having partially overlapping contents, each image being stored in a memory in the form of a pixelmap each pixel being binary and having two conditions, one and zero, comprising:

a selection means for selecting at least two pixels from the first image, forming at least two first bits;

a selection means for selecting at least two pixels from the second image, forming at least two second bits;

an address means for forming a binary address by defining said at least two first bits as the least significant bits of said address and said at least two second bits as the most significant bits of said address; and

an access means for accessing a table by said binary address to retrieve at east one correlation score.