Intelligent stitcher for panoramic image-based virtual worlds

• US 6,011,558 A
• Filed: 09/23/1997
• Issued: 01/04/2000
• Est. Priority Date: 09/23/1997
• Status: Expired due to Term

• Current Assignee: Transpacific IP Group Limited
• Original Assignee: Industrial Technology Research Institute
• Inventors: Hsieh, Chun-Wei, Huang, Shu-Cheng, Cheng, Tse, Chiang, Cheng-Chin
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): HARRISON, CHANTE E
• Application Number:
  US08/933,758
• Time in Patent Office: 833 Days
• Field of Search: 345/425, 345/426, 345/430, 345/421, 345/435, 382/199, 382/284, 382/294
• US Class Current: 345/629
• CPC Class Codes: G06T 11/00 2D [Two Dimensional] image generation

Abstract

A pair of images are stitched together by warping the pair of images into an environment map representative of a panoramic image. A first edge and a corresponding second edge for each of the first and second images, respectively, are detected. A set of edge position coordinates along the edge of the first warped image is determined. A set of possible matched solutions from the edge position coordinates of the first and second edge are generated. An optimum matched offset from the set of possible matched solutions is determined. Because the set of possible matched solutions is small and compact, the optimum matched offset can be determined efficiently from the set of solutions.

Claims

1. A method of stitching together a first and second image, the method comprising:

warping the first and second images into an environment map representative of a panoramic image;

detecting a first edge for the first warped image and a corresponding second edge of the second warped image;

determining a set of edge position coordinates from each of the detected first and second edges;

generating a set of possible matched solutions from the edge position coordinates of the detected first and second edges; and

determining an optimum matched offset of the first image relative to the second image from the set of possible matched solutions.

3. The method of claim 1 wherein detecting the first and second edges for each of the first and second warped images comprises:

detecting a vertical edge of one of the first and second images including;

determining gradient intensity values along columns of pixels forming one of the first and second warped images;

summing, for each column of pixels, gradient intensity values for all pixels along each column; and

comparing the summed value with a preselected threshold value.

4. The method of claim 1 wherein detecting the first and second edges for each of the first and second images comprises:

detecting a horizontal edge of one of the first and second images including;

determining gradient intensity values along rows of pixels forming one of the first and second images;

summing, for each row of pixels, gradient intensity values for all pixels along each row; and

comparing the summed value with a preselected threshold value.

6. The method of claim 1 wherein determining the optimum matched offset includes applying a mean absolute error correlation technique.

7. The method of claim 1 wherein the determining the optimum matched offset includes applying a normalized cross-correlation technique.

2. A method of stitching together a first and second image, the method comprising:

warping the first and second images into an environment map representative of a panoramic image, the environment map being formed of a plurality of pixels representative of the panoramic image;

detecting a first edge for the first warped image and a corresponding second edge of the second warped image;

determining a set of edge position coordinates from each of the detected first and second edges;

generating a set of possible matched solutions from the edge position coordinates of the detected first and second edges;

determining an optimum matched offset of the first image relative to the second image from the set of possible matched solutions; and

blending intensity values of pixels of the first warped image with corresponding pixels of the second warped image.

5. A method of stitching together a first and second image, the method comprising:

warping the first and second images into an environment map representative of a panoramic image;

detecting a first edge for the first warped image and a corresponding second edge of the second warped image;

determining a set of edge position coordinates from each of the detected first and second edges;

generating a set of possible matched solutions from the edge position coordinates of the detected first and second edges, wherein generating a set of possible matched solutions includes;

calculating an offset function according to the following equation;

d(i,k)=min |P_a (i)-k-P_b (j)|.

space="preserve" listing-type="equation">1≦

j≦

N.sub.b

where;

P_a represents edge position values associated with edge position coordinates of the first warped image;

P_b represents edge position values associated with edge position coordinates of the second warped image;

N_b is the number edge position values of Pb;

k is a user selected variable;

calculating a number N_p representative of the number of edge position values whose value of d(i,k) is less than a threshold value T₀ ;

determining an average value of d(i,k) for values of P_a less than threshold value T₀ ;

determining an average value of d(i,k) for elements of P_a whose d(i,k) is less than a first threshold value T₀ ; and

determining that a position k is a possible matched solution when the average value of d(i,k) is less than a second threshold value T₁ and the number N_p is larger than a third threshold value T₂ ; and

determining an optimum matched offset from the set of possible matched solutions.

8. A system for stitching together a first and a second image of an environment map formed of a plurality of pixels representative of a panoramic image, the system comprising:

an edge detector which detects a first edge of the first image and a corresponding second edge of the second image, the edge detector determining sets of edge position coordinates from each of the detected first and second edges;

a memory which stores the sets of edge position coordinates from each of the detected first and second edges;

a hypothesis generator which generates a set of possible matched solutions from the edge position coordinates of the detected first and second edges; and

an optimal hypothesis selector which determines an optimum matched offset of the first image relative to the second image from the set of possible matched solutions.

9. The system of claim 8 wherein the memory stores pixels representative of edges of the first and second warped images and the system further comprises a blending engine for blending intensity values of pixels of the first warped image with corresponding pixels of the second warped image.

10. The system of claim 8 wherein a microprocessor includes the edge detector, the hypothesis generator, and the optimal hypothesis selector.

11. The system of claim 8 further comprising an external storage which stores the warped images of the environment map.