Correlatability analysis for sparse alignment

• US 8,351,740 B2
• Filed: 12/10/2008
• Issued: 01/08/2013
• Est. Priority Date: 12/11/2007
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Hardy, Stephen James, Pham, Tuan Quang
• Primary Examiner(s): DRENNAN, BARRY T
• Application Number:
  US12/332,251
• Publication Number:
  US 20090148051A1
• Time in Patent Office: 1,490 Days
• Field of Search: None
• US Class Current: 382/294
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image

Abstract

Disclosed herein is a method of estimating a geometrical relationship between a first image (101) and a second image (102), wherein the second image (102) includes a noise component. The method determines a location and size of each one of a plurality of image patches (201), based on the noise component included in the second image (102) and correlation information derived from the first image (101). The method then identifies a plurality of first image areas in the first image and a corresponding plurality of second image areas in the second image, based on the location and size of each one of the plurality of image patches. Each first image area of the first image (101) corresponds to a related second image area of the second image (102). The method then determines a geometrical relationship between the first and second images (101, 102) by comparing, for each one of the first image areas, information located within the first image area with information located within the corresponding related second image area.

Claims

1. A computer-implementable method of estimating a geometrical relationship between a first image and a second image, said second image including a noise component, said method comprising the steps of:

(a) determining a location and size of each one of a plurality of image patches for each of said images, based on the noise component included in said second image and correlation information derived from said first image, wherein the size of each of the plurality of image patches is determined using a Cramer-Rao lower bound of two-dimensional shift estimation;

(b) identifying a plurality of first image areas in said first image and a corresponding plurality of second image areas in said second image, based on the location and size of each one of said plurality of image patches, wherein each first image area of said first image corresponds to a related second image area of said second image; and

(c) determining a geometrical relationship between said first and second images by comparing, for each one of said first image areas, information located within said first image area with information located within said corresponding related second image area.

2. The method according to claim 1, wherein the first image is a reference image and the second image is a corrupted image.

3. The method according to claim 1, further including a step of coarsely aligning the first image and the second image by applying one or more of a rotation transformation, a scaling transformation, or a translation transformation to at least one of said first image and second image.

4. The method according to claim 1, wherein, for each one of said plurality of image patches, the correlation information relates at least in part to at least one colour in an area of said first image defined by the location and size of said image patch.

5. The method according to claim 4, wherein the location and size of each image patch is further determined based on correlation information located within an area of said first image defined by the location and size of each image patch, when colours in said area are projected onto either one of:

(i) a one dimensional subspace of the colour space of at least one of the images; and

(ii) a two dimensional subspace of the colour space of at least one of the images.

6. The method according to claim 1, wherein at least one of the first and second images is a downsized image.

7. The method according to claim 1, wherein the size and location of each image patch is determined based on an accuracy target, said accuracy target defining an amount of correlation information required within an area of said first image defined by the location and size of each image patch.

8. The method according to claim 1, wherein said step of comparing, for each one of said first image areas, information located within said first image area with information located within said corresponding related second image area, produces a translation estimate which is used to determine the relationship between the first image and the second image.

9. The method according to claim 8, wherein the translation estimate is defined as one or more of a rotation transformation, scaling transformation, or a translation transformation for at least one of the first image and the second image.

10. The method according to claim 1, wherein said correlation information derived from said first image is computed from a linear combination of channels from said first image.

11. The method according to claim 1, wherein said first and second images are obtained from the group of images consisting of:

(a) digital images of a document;

(b) a video sequence that contains independently moving objects;

(c) digital images of a scene with overlapping content; and

(d) a digital image of a test chart.

12. The method according to claim 1, wherein said determining step is further based on a second noise component included in said first image.

13. The method according to claim 1, wherein a first image patch having a location corresponding to a first region of said first image has a smaller size than a second image patch having a location corresponding to a second region of said first image, when said first region contains more correlation information than said second region.

14. The method according to claim 1, wherein said second image is a digital image derived by scanning an image on a printed medium.

15. The method according to claim 1, wherein said geometric relationship is a warp map.

16. A non-transitory computer readable storage medium having recorded thereon a computer program executable by a processor to estimate a geometrical relationship between a first image and a second image, said second image including a noise component, said program comprising:

(a) code for determining a location and size of each one of a plurality of image patches for each of said images, based on the noise component included in said second image and correlation information derived from said first image, wherein the size of each of the plurality of image patches is determined using a Cramer-Rao lower bound of two-dimensional shift estimation;

(b) code for identifying a plurality of first image areas in said first image and a corresponding plurality of second image areas in said second image, based on the location and size of each one of said plurality of image patches, wherein each first image area of said first image corresponds to a related second image area of said second image; and

(c) code for determining a geometrical relationship between said first and second images by comparing, for each one of said first image areas, information located within said first image area with information located within said corresponding related second image area.

17. A computer-implementable method of estimating a geometrical relationship between a first image and a second image, said second image including a noise component, said method comprising the steps of:

(a) determining a location and size of each one of a plurality of image patches for each of said images, based on the noise component included in said second image and correlation information derived from said first image, wherein a first image patch, having a location corresponding to a first region of said first image, has a smaller size than a second image patch having a location corresponding to a second region of said first image, when said first region contains more correlation information than said second region;

(b) identifying a plurality of first image areas in said first image and a corresponding plurality of second image areas in said second image, based on the location and size of each one of said plurality of image patches, wherein each first image area of said first image corresponds to a related second image area of said second image; and

(c) determining a geometrical relationship between said first and second images by comparing, for each one of said first image areas, information located within said first image area with information located within said corresponding related second image area.