Method of and apparatus for searching corresponding points between images, and computer program

• US 20020136457A1
• Filed: 03/23/2001
• Published: 09/26/2002
• Est. Priority Date: 03/23/2001
• Status: Active Grant

• Current Assignee: Glory Limited
• Original Assignee: Glory Limited
• Inventors: Onishi, Hiroyuki, Kanade, Takeo
• Granted Patent: US 6,941,018 B2
• Time in Patent Office: Days
• US Class Current: 382/209
• CPC Class Codes: G06V 10/507 Summing image-intensity values; Histogram projection analysis
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching
• CPC Class Codes: G06V 40/30 Writer recognition; Reading and verifying signatures

Abstract

In the apparatus for searching corresponding points between an input image and a reference image, a reference image and an input image are received through an image input section. The division process section produces a reference partial image and an input partial image. The similarity degree image production section respectively produces similarity degree images whose similarity degree between the reference partial image and the input partial image. The accumulation-addition processing section recursively performs an accumulation-addition of a plurality of similarity degrees. Based on the result, the corresponding points determination section determines the corresponding points between the input image and the reference image.

Claims

1. An apparatus for searching corresponding points between an input image and a reference image which is an object of comparison with the input image, said apparatus comprising:

a similarity degree image production unit which produces a plurality of similarity degree images each having a similarity degree between the input image and the reference image as a pixel value; and

a corresponding point detection unit which detects corresponding points between the input image and the reference image based on the similarity degree images produced by said similarity degree image production unit.

2. The apparatus according to claim 1, wherein said similarity degree image production unit includes,

a reference partial image production unit which divides the reference image into a plurality of blocks and thereafter produces a reference partial image;

an input partial image production unit which divides the input image into a plurality of blocks and thereafter produces an input partial image; and

a similarity degree calculation unit which calculates the similarity degree between the input partial image and the reference partial image.

3. The apparatus according to claim 2, wherein said reference partial image production unit divides the reference image into a plurality of blocks and generates a plurality of reference partial images;

and

said input partial image production unit produces a plurality of input partial images each of whose size is greater than a size of each of the reference partial images and the each of which is obtained by dividing said input image into a plurality of blocks whose parts are mutually overlapped.

4. The apparatus according to claim 2, wherein said similarity calculation unit defines an Euclid distance or a normalized correlation coefficient between the input partial image and the reference partial image as a similarity degree.

5. The apparatus according to claim 1, wherein said corresponding point detection unit includes,

an accumulation addition unit which sequentially accumulation-adds a pixel value of pixel around each pixel of a plurality of similarity degree images arranged in a predetermined direction to a pixel value of the other pixel;

and

a corresponding point specific unit which specifies corresponding points based on each of similarity degree image accumulatively added by said accumulation addition unit.

6. The apparatus according to claim 5, wherein said accumulation-addition unit recursively repeats accumulation-addition calculation in a horizontal direction, a direction opposite to the horizontal direction, a vertical direction, and a direction opposite to the vertical direction.

7. The apparatus according to claim 5, wherein said accumulation-addition unit recursively repeats accumulation-addition in a horizontal direction, a direction opposite to the horizontal direction, a vertical direction, and a direction opposite to the vertical direction until a width of variance of position of a maximum value in each of the similarity degree images becomes smaller than a predetermined value.

8. The apparatus according to claim 5, wherein said corresponding point specific unit defines a pixel position of pixel whose pixel value of each of the similarity degree images additionally added by said accumulation addition unit which becomes maximum, as the corresponding points.

9. The apparatus according to claim 5, wherein said accumulation-addition unit sequentially accumulation-adds each of maximum pixel values from among each of pixel values of peripheral pixels.

10. A method of searching corresponding points between an input image and a reference image which is an object of comparison with the input image, the method comprising:

a similarity degree image production step of producing a plurality of similarity degree images each having a similarity degree between the input image and the reference image as a pixel value; and

a corresponding point detection step of detecting corresponding points between the input image and the reference image based on the plurality of similarity degree image produced in the similarity degree image production step.

11. The method according to claim 10, wherein the similarity degree image production step includes,

a reference partial image production step of dividing the reference image into a plurality of blocks and thereafter produces a reference partial image;

an input partial image production step of dividing the input image into a plurality of blocks and thereafter produces an input partial image; and

a similarity degree calculation step of calculating the similarity degree between the input partial image and the reference partial image.

12. The method according to claim 11, wherein the reference partial image production step divides the reference image into a plurality of blocks and generates a plurality of reference partial images;

and

said input partial image production step produces a plurality of input partial images each of whose size is greater than a size of each of the reference partial images and the each of which is obtained by dividing said input image into a plurality of blocks whose parts are mutually overlapped.

13. The method according to claim 11, wherein the similarity calculation step defines an Euclid distance or a normalized correlation coefficient between the input partial image and the reference partial image as a similarity degree.

14. The method according to claim 10, wherein the corresponding point detection step includes, p1 an accumulation addition step of sequentially accumulation-adding a pixel value of pixel around each pixel of a plurality of similarity degree images arranged in a predetermined direction to a pixel value of the other pixel, and

a corresponding point specific step of specifying corresponding points based on each of similarity degree image accumulatively added in the accumulation addition step.

15. The method according to claim 14, wherein the accumulation addition step recursively repeats accumulation-addition calculation in a horizontal direction, a direction opposite to the horizontal direction, a vertical direction, and a direction opposite to the vertical direction.

16. The method according to claim 14, wherein the accumulation addition step recursively repeats accumulation-addition calculation in a horizontal direction, a direction opposite to the horizontal direction, a vertical direction, and a direction opposite to the vertical direction until a width of variance of position of a maximum value in each of similarity degree images becomes smaller than a predetermined value.

17. The method according to claim 14, wherein the corresponding point specific step defines a pixel position of pixel whose pixel value of each of the similarity degree images additionally added by the accumulation addition step which becomes maximum, as the corresponding points.

18. The method according to claim 14, wherein the accumulation-addition step sequentially and accumulatively adds each of maximum pixel values from among each of pixel values of peripheral pixels.

20. The computer program according to claim 19, wherein the similarity degree image production step includes,

a reference partial image production step of dividing the reference image into a plurality of blocks and thereafter produces a reference partial image;

an input partial image production step of dividing the input image into a plurality of blocks and thereafter produces an input partial image; and

a similarity degree calculation step of calculating the similarity degree between the input partial image and the reference partial image.

21. The computer program according to claim 20, wherein the reference partial image production step divides the reference image into a plurality of blocks and generates a plurality of reference partial images;

and

said input partial image production step produces a plurality of input partial images each of whose size is greater than a size of each of the reference partial images and the each of which is obtained by dividing said input image into a plurality of blocks whose parts are mutually overlapped.

22. The computer program according to claim 20, wherein the similarity calculation step defines an Euclid distance or a normalized correlation coefficient between the input partial image and the reference partial image as a similarity degree.

23. The computer program according to claim 19, wherein the corresponding point detection step includes,

an accumulation addition step of sequentially accumulation-adding a pixel value of pixel around each pixel of a plurality of similarity degree images arranged in a predetermined direction to a pixel value of the other pixel, and

a corresponding point specific step of specifying corresponding points based on each of similarity degree image accumulatively added in the accumulation addition step.

24. The computer program according to claim 23, wherein the accumulation addition step recursively repeats accumulation-addition calculation in a horizontal direction, a direction opposite to the horizontal direction, a vertical direction, and a direction opposite to the vertical direction.

25. The computer program according to claim 23, wherein the accumulation addition step recursively repeats accumulation-addition calculation in a horizontal direction, a direction opposite to the horizontal direction, a vertical direction, and a direction opposite to the vertical direction until a width of variance of position of a maximum value in each of similarity degree images becomes smaller than a predetermined value.

26. The computer program according to claim 23, wherein the corresponding point specific step defines a pixel position of pixel whose pixel value of each of the similarity degree images additionally added by the accumulation addition step which becomes maximum, as the corresponding points.

27. The computer program according to claim 23, wherein the accumulation-addition step sequentially and accumulatively adds each of maximum pixel values from among each of pixel values of peripheral pixels.

19. A computer program containing instructions which when executed on a computer realizes a method of searching corresponding points between an input image and a reference image which is an object of comparison with the input image, the method comprising:

a similarity degree image production step of producing a plurality of similarity degree images each having a similarity degree between the input image and the reference image as a pixel value; and

a corresponding point detection step of detecting corresponding points between the input image and the reference image based on the plurality of similarity degree image produced in the similarity degree image production step.