Image stitching

• US 7,894,689 B2
• Filed: 05/31/2007
• Issued: 02/22/2011
• Est. Priority Date: 05/31/2007
• Status: Expired due to Fees

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Liu, Che-Bin, Xiao, Jing
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US11/756,517
• Publication Number:
  US 20080298718A1
• Time in Patent Office: 1,363 Days
• Field of Search: 382/284, 382/282, 382/291, 382/299, 382/173, 382/176, 382/177, 358/453, 358/462, 358/464, 358/465
• US Class Current: 382/284
• CPC Class Codes: G06T 2200/32 involving image mosaicing
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 2207/20164 Salient point detection; Corner detection
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/33 using feature-based methods

Abstract

Disclosed are embodiments of systems and methods to stitch two or more images together into a composite image. By finding matching point pairs for a pair of images, a homography transform may be obtained for the pair of images. The homography transform may be used to generate a composite image of the image pair. In an embodiment, the process of identifying a homography transform may be iterated. In an embodiment, when forming the composite image, the transformed foreground regions may be selected such that there is no intersection of foreground pixel regions. In an embodiment, foreground pixel regions on the border of an image may be removed. The resulting composite image is a larger image generated from the selected regions from the input images. In embodiments, the process may be repeated for sets of images with more than two images.

Claims

1. A method for forming a composite image from a set of images, the method comprising:

using one or more processors to execute at least in part the following operations;

identifying one or more foreground pixel groups in a first image from the set of images and one or more foreground pixel groups in a second image from the set of images;

identifying a set of interest points selected from the foreground pixel groups in the first image;

forming a set of point pairs by finding a set of points selected from the foreground pixel groups of the second image that correlates to the set of interest points;

forming a transform using at least some of the set of point pairs;

responsive to a foreground pixel group residing on a boundary of the first image or the second image, removing the foreground pixel group;

responsive to at least one foreground pixel of a transformed foreground pixel group from the second image, which transformed foreground pixel group is obtained using the transform, corresponding at a same pixel location in the first image to a foreground pixel in the first image, discarding the foreground pixel group of the second image;

for a foreground pixel group of the second image that has not been discarded;

transforming, according to the transform, a bounding box that bounds the foreground pixel group;

performing an inverse transform of at least some of the pixels within the transformed bounding box; and

responsive an inverse-transformed pixel corresponding to a foreground pixel in the second image, making the pixel from the transformed bounding box a foreground pixel.

2. The method of claim 1 wherein the step of identifying one or more foreground pixel groups in a first image from the set of images and one or more foreground pixel groups in a second image from the set of images comprises:

using segmentation to convert each of the first and second images into a binary, segmented image.

3. The method of claim 1 wherein the step of forming a transform using at least some of the set of point pairs comprises:

identifying a set of dominant point pairs; and

using at least some of the set of dominant point pairs to form the transform.

4. The method of claim 3 wherein the step of identifying a set of dominant point pairs comprises:

calculating a distance histogram representing the distance between point pairs from the set of point pairs;

using the distance histogram to identify the set of dominant point pairs.

5. The method of claim 4 wherein the step of using the distance histogram to identify a set of dominant point pairs comprises:

identifying a dominant bin of the distance histogram and the point pairs corresponding the dominant bin; and

including the point pairs corresponding to the dominant bin as part of the set of dominant point pairs.

6. The method of claim 1 wherein a multi-resolution interest point detector is used to identifying the set of interest points.

7. The method of claim 1 wherein the steps of

identifying a set of interest points selected from the foreground pixel groups in the first image;

forming a set of point pairs by finding a set of points selected from the foreground pixel groups of the second image that correlates to the set of interest points; and

forming a transform using at least some of the set of point pairs;

comprise the steps of;

identifying a first-pass set of interest points from the foreground pixel groups in a first portion of the first image;

forming a first-pass set of point pairs by finding a first-pass set of points in the foreground pixel groups of the second image that correlates to the first-pass set of interest points;

forming a first-pass transform using at least some of the first-pass set of point pairs;

using the first-pass transform to identify an overlapping area between the first image and the second image;

identifying a second-pass set of interest points from the foreground pixel groups in a set of regions selected from the overlapping area;

forming a second-pass set of point pairs by finding a second-pass set of points in the foreground pixel groups of the second image that correlates to the second-pass set of interest points; and

forming a transform using at least some of the second-pass set of point pairs.

8. A non-transitory device-readable medium comprising one or more sequences of instructions to direct an instruction-executing device to perform at least the steps of claim 1.

9. A system for forming a composite image from a set of images comprising:

a segmenter, coupled to receive the set of images, that identifies one or more foreground pixel groups in a first image from the set of images and one or more foreground pixel groups in a second image from the set of images;

an interest point detector, coupled to receive information from the segmenter, that identifies a set of interest points selected from the foreground pixel groups in the first image;

a point matcher, coupled to receive information from the interest point detector, that forms a set of point pairs by finding a set of points selected from the foreground pixel groups of the second image that correlates to the set of interest points;

a point pair selector, coupled to receive information from the point matcher, that uses a distance histogram to select a set of dominant point pairs;

a transform calculator, coupled to receive information from the point pair selector, that forms a transform using at least some of the set of dominant point pairs;

a border pixel remover, coupled to receive information from the transform calculator, that, responsive to a foreground pixel group residing on a boundary of the first image or the second image, discards the foreground pixel group;

an intersection checker, coupled to receive information from the border pixel remover, that, responsive to at least one foreground pixel of a transformed foreground pixel group from the second image, which transformed foreground pixel group is obtained using the transform, corresponding at a same pixel location in the first image to a foreground pixel in the first image, discards the foreground pixel group of the second image; and

an image stitcher, coupled to receive information from the intersection checker, that uses the transform and at least some of the non-discarded foreground pixel groups to form a composite image.

10. The system of claim 9 wherein the image stitcher forms the composite image by performing the steps comprising:

for a foreground pixel group of the second image that has not been discarded;

transforming, according to the transform, a bounding box that bounds the foreground pixel group;

performing an inverse transform of at least some of the pixels within the transformed bounding box; and

responsive an inverse-transformed pixel corresponding to a foreground pixel in the second image, making the pixel from the transformed bounding box a foreground pixel.

11. The system of claim 9 wherein the transform calculator forms an overlap transform that is used to identify an overlapping area between the first image and the second image and forms a subsequent transform using point pairs selected from the overlapping area.

12. The system of claim 9 wherein the point pair selector performs the steps comprising:

calculating a distance histogram representing the distance between point pairs from the set of point pairs;

identifying a dominant bin of the distance histogram and the point pairs corresponding the dominant bin; and

including the point pairs corresponding to the dominant bin as part of the set of dominant point pairs.

13. A method for forming a composite image from a set of images, the method comprising:

using one or more processors to execute at least in part the following operations;

forming a transform between a first image and a second image;

responsive to a foreground pixel group residing on a boundary of the first image or the second image, removing the foreground pixel group;

responsive to at least a portion of a foreground pixel group transformed, using the transform, from the second image intersecting at least a portion of a foreground pixel group in the first image, removing the foreground pixel group from one of the first or the second images;

for a foreground pixel group of the second image that has not been discarded;

transforming, according to the transform, a bounding box that bounds the foreground pixel group;

performing an inverse transform of at least some of the pixels within the transformed bounding box; and

responsive an inverse-transformed pixel corresponding to a foreground pixel in the second image, making the pixel from the transformed bounding box in the first image a foreground pixel.

14. The method of claim 13 wherein the step of forming a transform between a first image and a second image comprises:

identifying a set of interest points selected from the foreground pixel groups in the first image;

forming a set of point pairs by finding a set of points selected from the foreground pixel groups of the second image that correlates to the set of interest points; and

forming a transform using at least some of the set of point pairs.

15. The method of claim 14 further comprising:

identifying a set of dominant point pairs; and

using the set of dominant point pairs to form the transform.

16. The method of claim 13 wherein the step of forming a transform between a first image and a second image comprises:

generating an overlap transform using a portion of at least one of the first and the second images;

using the overlap transform to identify an overlapping area between the first image and the second image;

identifying a set of interest points from the foreground pixel groups in a set of regions selected from the overlapping area;

forming a set of point pairs by finding a set of points in a set of regions selected from the overlapping area of the second image that correlates to the set of interest points; and

forming a transform using at least some of the set of point pairs.

17. The method of claim 16 wherein the step of forming a transform using at least some of the set of point pairs comprises the steps of:

[a] forming a transform using at least some of the set of point pairs;

[b] for at least some of the points pairs that were used to form the transform, wherein each point pair contains a first point from the first image and a second point from the second image, using the transform to transform the second point from a point pair to obtain a transformed point;

[c] computing an error value between the transformed point and the first point;

[d] responsive to an error value exceeding an error threshold value, discarding the point pair from the set of point pairs and responsive to the number of point pairs in the set of point pairs exceeding a threshold number, iterating by returning to step [a]; and

[e] responsive to no point pairs being discarded, using the transform to form a composite image of the first and second images.

18. The method of claim 17 further comprising:

responsive to the number of point pairs in the set of point pairs not exceeding a threshold number, reorienting the first and second images and repeating the processes of forming a transform.

19. The method of claim 18 further comprising:

responsive to not forming a transform between the first and second image, selecting a different second image from the set of images and forming a transform.

20. A non-transitory device-readable medium comprising one or more sequences of instructions to direct an instruction-executing device to perform at least the steps of claim 13.