Aligning rectilinear images in 3D through projective registration and calibration

• US 20020114536A1
• Filed: 02/14/2002
• Published: 08/22/2002
• Est. Priority Date: 09/25/1998
• Status: Active Grant

• Current Assignee: Ken Turkowski, Yalin Xiong
• Original Assignee: Ken Turkowski, Yalin Xiong
• Inventors: Xiong, Yalin, Turkowski, Ken
• Granted Patent: US 6,549,651 B2
• Time in Patent Office: Days
• US Class Current: 382/284
• CPC Class Codes: G06T 15/503 Blending, e.g. for anti-aliasing
• CPC Class Codes: G06T 15/506 Illumination models
• CPC Class Codes: G06T 3/4038 Image mosaicing, e.g. composing plane images from plane sub-images
• CPC Class Codes: G06T 7/32 using correlation-based methods
• CPC Class Codes: G06V 10/16 using multiple overlapping images; Image stitching
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image

Abstract

An improved apparatus and method for creating high quality virtual reality panoramas is disclosed that yields dramatic improvements during the authoring and projecting cycles, with speeds up to several orders of magnitude faster than prior systems. In a preferred embodiment, a series of rectilinear images taken from a plurality of rows are pairwise registered with one another, and locally optimized using a pairwise objective function (local error function) that minimizes certain parameters in a projective transformation, using an improved iterative procedure. The local error function values for the pairwise registrations are then saved and used to construct a quadratic surface to approximate a global optimization function (global error function). The chain rule is used to avoid the direct evaluation of the global objective function, saving computation. In one embodiment concerning the blending aspect of the present invention, an improved procedure is described that relies on Laplacian and Gaussian pyramids, using a blend mask whose boundaries are determined by the grassfire transform. An improved iterative procedure is disclosed for the blending that also determines at what level of the pyramid to perform blending, and results in low frequency image components being blended over a wider region and high frequency components being blended over a narrower region. Human interaction and input is also provided to allow manual projective registration, initial calibration and feedback in the selection of photos and convergence of the system.

Claims

1. A computer system for authoring panoramas, comprising:

memory storing data representations of a plurality of images;

I/O for inputting and outputting data;

function modules in said memory;

a processor cooperating with said memory and I/O for processing instructions and data from said memory, said I/O and said function modules;

a pairwise registration function module in said memory and operating said processor for pairwise registration of said images, said pairwise registration function module generating output data related to said pairwise registration of said images;

a calibration and global optimization function module in said memory and operating said processor for calibration and global optimization of said output data of said pairwise registration module, said calibration and global optimization module generating output data related to said calibration and global optimization of said images;

a blending function module in said memory and operating said processor for generating at least one panorama from said output data from said pairwise registration module and said calibration and global optimization module; and

a projection function module in said memory and operating said processor for forming a panorama from said images.

2. The invention according to claim 1, wherein:

said pairwise registration function module operates said processor to register a plurality of each of said images that overlap with one another, by perturbing said images.

3. The invention according to claim 2, wherein:

said pairwise registration function module performs a projective transformation between a pair of said images, said projective transformation is estimated by said pairwise registration function module by performing a gradient-based optimization that minimizes a local error function.

4. The invention according to claim 3, further comprising:

a user interface module in said memory, and cooperating with said I/O, operating said processor for initializing said projective matrix of said pairwise registration function module, said user interface module operating to process input from a user of the computer system, wherein said projective matrix is initialized with said camera internal and external parameters from manual input by a user; and

,

said pairwise registration function projective transformation error function is comprised of the differences in exposures between pixels comprising the pairs of images, and contains a projective matrix initialized by camera internal and external parameters relating to said plurality of images.

5. The invention according to claim 4, wherein:

said internal and external parameters are selected from the group comprising;

image center position of each of said pairs of images, aspect ratio of said pixels comprising said images, the focal length of the camera which took said images;

the camera orientation with respect to a common reference frame, camera pan, tilt, roll and skew and brightness and contrast of said pairs of images.

6. The invention according to claim 3, wherein:

said local error function, eij, is given by the equation

7. The invention according to claim 2, wherein:

said pairwise registration function module operates said processor to form a Gaussian pyramid in said memory from said plurality of overlapping images, said Gaussian pyramid having a plurality of levels, each subsequent level being finer than each preceding level, said optimization of said local error function is performed on progressively finer levels of said Gaussian pyramid.

8. The invention according to claim 7, wherein:

the number of pyramid levels of said Gaussian pyramid is computed by said pairwise registration function module according to the formula;

${\log }_2<br><br>\left(\frac{l}{l_{\min }}\right)$

where l is the square root of the smaller eigenvalue of the 2×

2 inertial tensor of the overlap polygon region of said plurality of images, and l_min is the minimal size of the finest level resolution pyramid level.

9. The invention according to claim 6, wherein:

said pairwise registration function module operates said processor to form a Gaussian pyramid in said memory from said plurality of overlapping images, said Gaussian pyramid having a plurality of levels, each subsequent level being finer than each preceding level, said optimization of said local error function is performed on progressively finer levels of said Gaussian pyramid;

said pairwise registration function module operates said processor to estimate said exposure parameters, s_ij and b_ij, of said local error function by a correlation-based linear search, and attenuates said exposure parameters with progressive damping, said progressive damping set to maximum at the coarsest level of said pyramid and decreasing to zero at the finest level.

10. The invention according to claim 2, wherein:

a calibration and global optimization function module in said memory and operating said processor for calibration and global optimization of said output data of said pairwise registration module, said calibration and global optimization module generating output data related to said calibration and global optimization of all of said overlapping images.

11. The invention according to claim 10, wherein:

said calibration and global optimization function module calibrates and optimizes said output data of said pairwise registration module by approximating said local error function.

12. The invention according to claim 11, wherein said approximation of said local error function, eij, is a Taylor Series expansion given by the formula:

e_ij(M_ij)≈

e_ij⁰+(M_ij−

M_ij⁰)^TC_ij(M_ij−

M_ij⁰)

where e_ij⁰ is a constant representing the minimal value achieved by said pairwise registration function module;

M_ij is the projective matrix of overlapping pairs of images, M_ij⁰ is the vector representing the optimal projective matrix, and C_ij is the Hessian matrix obtained by the pairwise registration function module when optimizing objective function e_ij.

13. The invention according to claim 12, wherein said calibration and global optimization function module calculates a global error function for all overlapping images by application of the chain rule to said output data of said pairwise registration module, according to the formula:

14. The invention according to claim 10, further comprising:

said pairwise registration function module operates said processor to estimate a projective transformation for pairwise registration of images.

15. The invention according to claim 14, wherein:

said projective transformation is initialized by camera internal and external parameters relating to said plurality of images in said pairwise registration function; and

said projective transformation is initialized by said output data generated by said calibration and global optimization module generating output data, in an iterative manner, and,

said calibration and global optimization function module attenuates camera internal parameters during said calibration and global optimization.

16. The invention according to claim 1, wherein:

said blending function module generating at least one panorama by employing in the image overlap areas of said output data a multi-resolution weighted average blending.

17. The invention according to claim 1, further comprising:

a user interface function module in said memory and operating said processor for accepting input from a human user, and for adjusting the areas said images overlap;

said blending function module generating at least one panorama by blending said images where the images overlap, in response to said user interface module.

18. The invention according to claim 1:

said blending function module generates said panorama from said output data comprising images having image overlap regions, said image overlap regions blended by said panorama generating function module by performing a grassfire transform on data relating to said images to generate a blend mask of said image overlap regions.

19. The invention according to claim 1:

said blending function module generates said panorama from said output data comprising images having image overlap regions, said blending function module blending by instructing said processor to construct Laplacian pyramids stored in said memory for each plurality of images that overlap in said image overlap regions, said Laplacian pyramids having a plurality of levels, said blending function module determining the coarsest level resolution level of the Laplacian pyramids for each of said images, said blending function module generating a blend mask from the image overlap region of said plurality of images, said blending function module constructing a Gaussian pyramid from said blend mask for each said plurality of images, and blending said images by multiplying said Laplacian and Gaussian pyramid values for every level of said Laplacian pyramids for every said plurality of images.

20. The invention according to claim 1, wherein said blending function module blends the high frequency components of said images that overlap over a smaller region in the area of overlap than the low frequency components of said images.

21. The invention according to claim 20, wherein said smaller region is on the order of 3-5 pixels.

22. The invention according to claim 1, wherein said projection function module forms said panorama on a geometry that is selected from geometries consisting of:

cubic, polyhedral, cylindrical and spherical geometries, frusto-conical cones joined at their base with the apexes pointing away from one another;

all geometries employing conical sections, and geometries using the following projections;

equidistant, equiangular, ellipsoid, Mercator, transverse Mercator, Oblique Mercator, cylindrical equal-area, Miller cylindrical, equidistant cylindrical, Cassini, Albers equal-area, Lambert conformal conic, equidistant conic, bipolar oblique conic conformal, polyconic, Bonne, azimuthal, orthographic, sterographic, gnomonic, general perspective, Lambert azimuthal equal-area, azimuthal equidistant, modified-stereographic conformal, space map projections, space oblique Mercator, satellite-tracking projections, pseudocylindrical projections, Van der Grinten, sinusoidal, Mollweide and Eckert IV and VI projections.

24. The method according to claim 23, wherein:

said step of blending said rectilinear images to create a panorama comprises the step of identifying a region of overlap between said rectilinear images from said generated data;

generating a blend mask from said rectilinear images from said generated data;

locating the boundary of said mask by performing a grassfire transform on said at least two rectilinear images individually.

25. The method according to claim 23, wherein:

said step of generating data by performing pairwise registration of said rectilinear images by estimating said projective transformation of said rectilinear images comprises the steps of;

initializing said projective transformation with camera internal and external parameters of two rectilinear images that overlap;

forming a Gaussian pyramid from said plurality of overlapping rectilinear images;

perturbing said overlapping rectilinear images until a local registration error function is minimized at a first level of said Gaussian pyramid for said images.

26. The method according to claim 25, wherein:

wherein said camera internal and external parameters are selected from the group comprising the image center position of each of said pairs of images, aspect ratio of said pixels comprising said images, the focal length of the camera which took said images;

the camera orientation with respect to a common reference frame, camera pan, tilt, roll and skew and brightness and contrast of said images.

27. The method according to claim 25, wherein:

said local registration error function, eij, is given by the equation;

$e_{\mathrm{ij}}=\frac{1}{A_{\mathrm{ij}}}<br><br>\underset{\mathrm{overlap}}{\sum <br><br>}<br><br>{\left(s_{\mathrm{ij}}<br><br>I_j<br><br>\left(X_j\right)+b_{\mathrm{ij}}-I_i<br><br>\left(M_{\mathrm{ij}}<br><br>X_j\right)\right)}^2$

 

where s_ij and b_ij, the exposure parameters, represent the exposure difference, I_i( ) and I_j( ) are pixel intensity values from two images, and A_ij is the overlap area of said images, the vector X_i represents the homogeneous coordinates of the pixel locations making up said images, and the matrix M_ij represents the matrix that transforms coordinates from image j to image i;

further comprising the step of pairwise registration of said overlapping images on successive iterations of said Gaussian pyramid.

28. The method according to claim 27, further comprising the step of:

attenuating said estimated exposure parameters, sij and bij, in said equation, at each successive iteration of said Gaussian pyramid by progressive damping, said damping set to maximum at the coarsest level of said Gaussian pyramid and decreasing to zero at the finest level of said Gaussian pyramid.

29. The method according to claim 28, further comprising the step of:

estimating said exposure parameters, sij and bij, according to a correlation based linear search.

30. The method according to claim 27, further comprising the step of:

finding said first level of said Gaussian pyramid by successively moving down said Gaussian pyramid until a predetermined number of pixels from each of said images overlap.

31. The method according to claim 30, further comprising the step of:

determining the number of levels of said Gaussian pyramid of said pairwise registration of overlapping images according to the formula;

${\log }_2<br><br>\left(\frac{l}{l_{\min }}\right)$

 

where l is the square root of the smaller eigenvalue of the 2×

2 inertial tensor of the overlap polygon region of said plurality of images, and l_min is the minimal size of the finest level resolution pyramid level.

32. The method according to claim 23, further comprising the step of:

projecting said panorama formed from said steps of pairwise registration and calibration and global optimization, wherein said projection function module forms said panorama on a geometry that is selected from geometries consisting of;

cubic, polyhedral, cylindrical and spherical geometries, frusto-conical cones joined at their base with the apexes pointing away from one another;

all geometries employing conical sections, and geometries using the following projections;

equidistant, equiangular, ellipsoid, Mercator, transverse Mercator, Oblique Mercator, cylindrical equal-area, Miller cylindrical, equidistant cylindrical, Cassini, Albers equal-area, Lambert conformal conic, equidistant conic, bipolar oblique conic conformal, polyconic, Bonne, azimuthal, orthographic, sterographic, gnomonic, general perspective, Lambert azimuthal equal-area, azimuthal equidistant, modified-stereographic conformal, space map projections, space oblique Mercator, satellite-tracking projections, pseudocylindrical projections, Van der Grinten, sinusoidal, Mollweide and Eckert IV and VI projections.

33. The invention according to claim 25, wherein:

wherein said calibration and global optimization function module calibrates and optimizes said output data of said pairwise registration module by approximating said local error function, eij;

wherein said step of estimating said local error function is an approximation of said local error function given by the formula;

e_ij(M_ij)≈

e_ij⁰+(M_ij−

M_ij⁰)^TC_ij(M_ij−

M_ij⁰)

 

where e_ij⁰ is a constant representing the minimal value achieved by said pairwise registration function module;

M_ij is the projective matrix of overlapping pairs of images, M_ij⁰ is the vector representing the optimal projective matrix, and C_ij is the Hessian matrix obtained by the pairwise registration function module when optimizing objective function e_ij.

34. The invention according to claim 33, further comprising the steps of:

saving said approximated local error function generated during pairwise registration of said images according to the steps above;

computing, for each and every overlapping images, said calibration and global optimization of said images, according to the global error formula;

$\frac{\partial <br><br>E}{\partial <br><br>\left(p_i,q_i\right)}=\underset{j}{\sum <br><br>}<br><br>\frac{\partial <br><br>e_{\mathrm{ij}}}{\partial <br><br>M_{\mathrm{ij}}}<br><br>\frac{\partial <br><br>M_{\mathrm{ij}}}{\partial <br><br>\left(p_i,q_i\right)}$

 

minimizing said global error function, where p_j=the vector for camera internal parameters for each image j_i and q_j=the camera orientation with respect to a common reference frame for each image j.

35. The invention according to claim 34, further comprising the steps of:

re-initializing said projective transformation, in an iterative manner, with said output data generated by said calibration and global optimization module.

36. The method according to claim 23, wherein:

said step of blending comprises blending high frequency components of said images that overlap over a smaller region in the area of overlap than low frequency components of said images.

37. The invention according to claim 36, wherein said blending for high frequency components of said images is performed over said smaller region on the order of 3-5 pixels.

38. The invention according to claim 23, wherein said steps further comprising:

wherein said blending of said rectilinear images to create a panorama comprises the steps of;

constructing a Laplacian pyramid for the overlapping images in an image overlap region where said images overlap, said Laplacian pyramids having a plurality of levels;

determining the coarsest level resolution level of the Laplacian pyramids for each of said images;

constructing a blend mask from the image overlap region for said plurality of overlapping images, said blend mask being a Gaussian pyramid

combining said Laplacian pyramid and said Gaussian pyramids to blend said images in said image overlap region.

39. The method according to claim 38, wherein said step of constructing said blend mask is performed by locating the boundary of said blend mask by performing a grassfire transform on at least two overlapping images.

40. The invention according to claim 38, further comprising the steps of:

labeling, during the steps of blending, the pixels comprising each said overlapping images with values to associate each pixel with a particular image;

generating a blend mask from the image overlap region of said images, and computing a boundary to said blend mask from said values of said pixel labels and from said overlapping images.

41. The invention according to claim 38, wherein said blending function module generating at least one panorama from said output of said pairwise registration module and said calibration and global optimization module by employing in the image overlap areas of said output a multi-resolution weighted average blending.

42. The invention according to claim 23, further comprising the steps of:

projecting said panorama from said images, after said images have been pairwise registered, calibrated and globally optimized;

projecting said panorama onto a view surface geometry that is selected from geometries consisting of;

cubic, polyhedral, cylindrical and spherical geometries, frusto-conical cones joined at their base with the apexes pointing away from one another;

all geometries employing conical sections, and geometries using the following projections;

equidistant, equiangular, ellipsoid, Mercator, transverse Mercator, Oblique Mercator, cylindrical equal-area, Miller cylindrical, equidistant cylindrical, Cassini, Albers equal-area, Lambert conformal conic, equidistant conic, bipolar oblique conic conformal, polyconic, Bonne azimuthal, orthographic, sterographic, gnomonic, general perspective, Lambert azimuthal equal-area, azimuthal equidistant, modified-stereographic conformal, space map projections, space oblique Mercator, satellite-tracking projections, pseudocylindrical projections, Van der Grinten, sinusoidal, Mollweide and Eckert IV and VI projections.

23. In a computer having a processor which executes instructions stored in memory, a method for generating panoramas comprising the steps of:

storing at least two rectilinear images in a computer memory;

generating image output data by performing pairwise registration of said rectilinear images as an estimate to a projective transformation relating to said rectilinear images;

generating image output data by calibration and global optimization of said rectilinear images from image output data from said pairwise registration;

blending said rectilinear images to create a panorama from said generated image output data from said pairwise registration and said calibration and global optimization.

43. In a computer having a processor which executes instructions stored in memory, a method for generating panoramas from two dimensional images, comprising the steps of:

storing at least two rectilinear images in a computer memory;

blending said rectilinear images to create a panorama.

44. The method according to claim 43, further comprising the steps of:

wherein said blending of said rectilinear images to create a panorama comprises the steps of;

constructing a Laplacian pyramid for the overlapping images in an image overlap region where said images overlap, said Laplacian pyramids having a plurality of levels;

determining the coarsest level resolution level of the Laplacian pyramids for each of said images;

constructing a blend mask from the image overlap region for said plurality of overlapping images, said blend mask being a Gaussian pyramid

combining said Laplacian pyramid and said Gaussian pyramids to blend said images in said image overlap region.

45. The method according to claim 44, wherein said step of constructing said blend mask is performed by locating the boundary of said blend mask by performing a grassfire transform on at least two overlapping images.

46. The invention according to claim 44, further comprising the steps of:

labeling, during the steps of blending, the pixels comprising each said overlapping images with values to associate each pixel with a particular image;

generating a blend mask from the image overlap region of said images, and computing a boundary to said blend mask from said values of said pixel labels and from said overlapping images.

47. The invention according to claim 44, wherein said blending function module generating at least one panorama from said output of said pairwise registration module and said calibration and global optimization module by employing in the image overlap areas of said output a multi-resolution weighted average blending.

48. The invention according to claim 43, further comprising the steps of:

projecting said panorama from said images, after said images have been pairwise registered, calibrated and globally optimized;

projecting said panorama onto a view surface geometry that is selected from geometries consisting of;

cubic, polyhedral, cylindrical and spherical geometries, frusto-conical cones joined at their base with the apexes pointing away from one another;

all geometries employing conical sections, and geometries using the following projections;

equidistant, equiangular, ellipsoid, Mercator, transverse Mercator, Oblique Mercator, cylindrical equal-area, Miller cylindrical, equidistant cylindrical, Cassini, Albers equal-area, Lambert conformal conic, equidistant conic, bipolar oblique conic conformal, polyconic, Bonne, azimuthal, orthographic, sterographic, gnomonic, general perspective, Lambert azimuthal equal-area, azimuthal equidistant, modified-stereographic conformal, space map projections, space oblique Mercator, satellite-tracking projections, pseudocylindrical projections, Van der Grinten, sinusoidal, Mollweide and Eckert IV and VI projections.

50. The method according to claim 49, wherein:

said step of performing pairwise registration of said rectilinear images by calculating said projective transformation between said rectilinear images comprises the steps of;

initializing said projective transformation with camera internal and external parameters of a pair of said rectilinear images that overlap;

forming a Gaussian pyramid from said pair of overlapping rectilinear images;

perturbing said overlapping rectilinear images until a local registration error function is minimized at a first level of said Gaussian pyramid for said images.

51. The method according to claim 50, wherein:

wherein said camera internal and external parameters are selected from the group comprising the image center position of each of said pairs of images, aspect ratio of said pixels comprising said images, the focal length of the camera which took said images;

the camera orientation with respect to a common reference frame, camera pan, tilt, roll and skew and brightness and contrast of said pairs of images.

52. The method according to claim 50, wherein:

said local registration error function, eij, is given by the equation;

$e_{\mathrm{ij}}=\frac{1}{A_{\mathrm{ij}}}<br><br>\underset{\mathrm{overlap}}{\sum <br><br>}<br><br>{\left(s_{\mathrm{ij}}<br><br>I_j<br><br>\left(X_j\right)+b_{\mathrm{ij}}-I_i<br><br>\left(M_{\mathrm{ij}}<br><br>X_j\right)\right)}^2$

 

where s_ij and b_ij, the exposure parameters, represent the exposure difference, I_i( ) and I_j( ) are pixel intensity values from two images, and A_ij is the overlap area of said images, the vector X_i represents the homogeneous coordinates of the pixel locations making up said images, and the matrix M_ij represents the matrix that transforms coordinates from image j to image i;

further comprising the step of pairwise registration of said overlapping images on successive iterations of said Gaussian pyramid.

53. The method according to claim 52, further comprising the step of:

attenuating said estimated exposure parameters, sij and bij, in said equation, at each successive iteration of said Gaussian pyramid by progressive damping, said damping set to maximum at the coarsest level of said Gaussian pyramid and decreasing to zero at the finest level of said Gaussian pyramid.

54. The method according to claim 53, further comprising the step of:

estimating said exposure parameters, sij and bij, according to a correlation based linear search.

55. The method according to claim 52, further comprising the step of:

finding said first level of said Gaussian pyramid by iteratively moving down said Gaussian pyramid until a predetermined number of pixels from each of said images overlap.

56. The method according to claim 55, further comprising the step of:

determining the number of levels of said Gaussian pyramid of said pairwise registration of overlapping images according to the formula;

${\log <br><br>\text{\hspace{1em}<br><br>}}_2<br><br>\left(\frac{l}{l_{\min }}\right)$

 

where l is the square root of the smaller eigenvalue of the 2×

2 inertial tensor of the overlap polygon region of said plurality of images, and l_min is the minimal size of the finest level resolution pyramid level.

58. The invention according to claim 57, wherein:

said pairwise registration function module operates said processor to register a plurality of each of said images that overlap with one another, by perturbing said images.

59. The invention according to claim 58, wherein:

said pairwise registration function module performs said pairwise registration by estimating a projective transformation relating a pair of images that overlap.

60. The invention according to claim 59, wherein:

said projective transformation between said pair of images is estimated by said pairwise registration function module by performing a gradient-based optimization that minimizes a local error function that is comprised of the differences in exposures between pixels comprising pairs of overlapping images, and contains a projective matrix initialized by camera internal and external parameters relating to said plurality of images.

61. The invention according to claim 60 wherein:

said local error function, eij, is given by the equation

$e_{\mathrm{ij}}=\frac{1}{A_{\mathrm{ij}}}<br><br>\underset{\mathrm{overlap}}{\sum <br><br>}<br><br>{\left(s_{\mathrm{ij}}<br><br>I_j<br><br>\left(X_j\right)+b_{\mathrm{ij}}-I_i<br><br>\left(M_{\mathrm{ij}}<br><br>X_j\right)\right)}^2$

 

where s_ij and b_ij, the exposure parameters, represent the exposure difference, I_i( ) and I_j( ) are pixel intensity values from two images, and A_ij is the overlap area of said images, the vector X_i represents the homogeneous coordinates of the pixel locations making up said images, and the matrix M_ij represents the matrix that transforms coordinates from image j to image i, and;

said pairwise registration function module operates said processor to form a Gaussian pyramid in said memory from said plurality of overlapping images, said Gaussian pyramid having a plurality of levels, each subsequent level being finer than each preceding level, said optimization of said local error function is performed on progressively finer levels of said Gaussian pyramid.

62. The invention according to claim 61, wherein:

the number of pyramid levels of said Gaussian pyramid is computed by said pairwise registration function module according to the formula;

${\log <br><br>\text{\hspace{1em}<br><br>}}_2<br><br>\left(\frac{l}{l_{\min }}\right)$

 

where l is the square root of the smaller eigenvalue of the 2×

2 inertial tensor of the overlap polygon region of said plurality of images, and l_min is the minimal size of the finest level resolution pyramid level.

63. The invention according to claim 61, wherein:

said pairwise registration function module operates said processor to estimate said exposure parameters, s_ij and b_ij of said local error function by a correlation-based linear search, and attenuates said exposure parameters with progressive damping, said progressive damping set to maximum at the coarsest level of said pyramid and decreasing to zero at the finest level.

64. The invention according to claim 59, further comprising:

a user interface module in said memory and operating said processor for initializing said projective transformation of said pairwise registration function module, said user interface module operating to process input from a user of the computer system, wherein said projective transformation is initialized with said camera internal and external parameters from manual input by a user.

65. The invention according to claim 64, wherein:

said internal and external parameters are selected from the group comprising;

image center position of each of said pairs of images, aspect ratio of said pixels comprising said images, the focal length of the camera which took said images;

the camera orientation with respect to a common reference frame, camera pan, tilt, roll and skew and brightness and contrast of said pairs of images.

66. The invention according to claim 64, wherein:

said user interface module allows the user the ability to select the arrangement of said images.

67. The invention according to claim 66, wherein:

said user interface module comprises a virtual reality environment comprising a spherical coffee table.

68. The invention according to claim 67, wherein:

said user interface module allows the user to select the arrangement of said images from a plurality of rows of photos on said spherical coffee table.

69. The invention according to claim 59, wherein:

a calibration and global optimization function module in said memory and operating said processor for calibration and global optimization of said output data of said pairwise registration module, said calibration and global optimization module generating output data related to said calibration and global optimization of all of said overlapping images.

70. The invention according to claim 69, wherein:

wherein said calibration and global optimization function module calibrates and optimizes said output data of said pairwise registration module by approximating a local error function.

71. The invention according to claim 70, wherein said approximation of said local error function is a Taylor Series expansion given by the formula:

e_ij(M_ij)≈

e_ij⁰+(M_ij−

M_ij⁰)^TC_ij(M_ij−

M_ij⁰)

where e_ij⁰ is a constant representing the minimal value achieved by said pairwise registration function module;

M_ij is the projective matrix of overlapping pairs of images, M_ij⁰ is the vector representing the optimal projective matrix, and C_ij is the Hessian matrix obtained by the pairwise registration function module when optimizing objective function e_ij.

72. The invention according to claim 70, wherein said calibration and global optimization function module calculates a global error function for all overlapping images by application of the chain rule to said output data of said pairwise registration module, according to the formula:

73. The invention according to claim 69, wherein:

said projective transformation initialized by camera internal and external parameters relating to said plurality of images in said pairwise registration function is initialized by said output data generated by said calibration and global optimization module generating output data, in an iterative manner.

74. The invention according to claim 73, wherein:

said calibration and global optimization function module attenuates camera internal parameters during said calibration and global optimization.

75. The invention according to claim 69, further comprising:

a blending function module in said memory and operating said processor for generating at least one panorama from said output data from said pairwise registration module and said calibration and global optimization module.

76. The invention according to claim 75, wherein:

said blending function module generating at least one panorama from said output of said pairwise registration module and said calibration and global optimization module by employing in the image overlap areas of said output a multi-resolution weighted average blending.

77. The invention according to claim 76, further comprising:

a user interface module in said memory and operating said processor for accepting input from a human user, and for selecting said images and adjusting the areas said images overlap;

said blending function module generating at least one panorama from said output of said pairwise registration module and said calibration and global optimization module by employing in the image overlap areas of said output a weighted average blending, in response to said user interface module.

78. The invention according to claim 76, further comprising:

a user interface module in said memory and operating said processor for accepting input from a human user, and for selecting said images and adjusting the areas. said images overlap, wherein said user interface module allows the user the ability to select the arrangement of said images.

79. The invention according to claim 78, wherein:

said user interface module comprises a virtual reality environment comprising a spherical coffee table.

80. The invention according to claim 79, wherein:

said user interface module allows the user to select the arrangement of said images from a plurality of rows of photos.

81. The invention according to claim 76, wherein:

said blending function module generates said panorama from said output data comprising images having image overlap regions, said image overlap regions blended by said panorama generating function module by performing a grassfire transform on data relating to said images to generate a blend mask of said images.

82. The invention according to claim 76, wherein said blending function module blends high frequency components of said images that overlap over a smaller region in the area of overlap than low frequency components of said images.

83. The invention according to claim 82, wherein said smaller region is on the order of 3-5 pixels.

84. The invention according to claim 76, wherein:

said blending function module generates said panorama from said output data comprising images having image overlap regions, said blending function module blending by instructing said processor to construct Laplacian pyramids stored in said memory for each plurality of images that overlap in said image overlap regions, said Laplacian pyramids having a plurality of levels, said blending function module determining the coarsest level resolution level of the Laplacian pyramids for each of said images, said blending function module generating a blend mask from the image overlap region of said plurality of images, said blending function module constructing a Gaussian pyramid from said blend mask for each said plurality of images, and blending said images by multiplying said Laplacian and Gaussian pyramid values for every level of said Laplacian pyramids for every said plurality of images.

85. The invention according to claim 76, wherein:

said blending function labels the pixels comprising each said overlapping images with values to associate each pixel with a particular image. said blending function module generating a blend mask from the image overlap region of said images, and computing a boundary to said blend mask from said values of said pixel labels and from said overlapping images.

86. The invention according to claim 76, further comprising:

a projection function module in said memory and operating said processor for forming a panorama from said images, said projection function forms said panorama on a geometry that is selected from geometries consisting of;

cubic, polyhedral, cylindrical and spherical geometries, frusto-conical cones joined at their base with the apexes pointing away from one another;

all geometries employing conical sections, and geometries using the following projections;

equidistant, equiangular, ellipsoid, Mercator, transverse Mercator, Oblique Mercator, cylindrical equal-area, Miller cylindrical, equidistant cylindrical, Cassini, Albers equal-area, Lambert conformal conic, equidistant conic, bipolar oblique conic conformal, polyconic, Bonne, azimuthal, orthographic, sterographic, gnomonic, general perspective, Lambert azimuthal equal-area, azimuthal equidistant, modified-stereographic conformal, space map projections, space oblique Mercator, satellite-tracking projections, pseudocylindrical projections, Van der Grinten, sinusoidal, Mollweide and Eckert IV and VI projections.

49. A computer readable memory storing a program which executes the steps of:

storing at least a pair of rectilinear images in a computer memory;

performing pairwise registration of said rectilinear images by calculating a projective transformation between said rectilinear images.

57. A computer system comprising:

a memory storing data representations relating to at least two images;

function modules in said memory;

a processor for processing instructions and data from said memory and said function modules;

a pairwise registration function module in said memory, and operating said processor for pairwise registration of said images, said pairwise registration function module generating output data related to said pairwise registration of said images.

87. A computer system comprising:

a memory storing data representations relating to at least a pair of overlapping images;

a blending function module in said memory;

a processor for processing instructions and data from said memory and said blending function module;

said blending function module in said memory operating said processor for blending said images to form a panorama from said images.

88. The invention according to claim 87, further comprising:

said blending function module generating at least one panorama by employing in the image overlap areas of said images a multi-resolution weighted average blending.

89. The invention according to claim 87, further comprising:

a user interface module in said memory and operating said processor for accepting input from a human -user, and for selecting said images and adjusting the areas said images overlap;

said blending function module generating at least one panorama by blending said image overlap areas, in response to said user interface module.

90. The invention according to claim 87, wherein:

said blending function module generates said panorama by performing a grassfire transform on data relating to said images to generate a blend mask of said images.

91. The invention according to claim 87, wherein:

said blending function module generates said panorama by instructing said processor to construct Laplacian pyramids stored in said memory for each plurality of images that overlap in image overlap regions, said Laplacian pyramids having a plurality of levels, said blending function module determining the coarsest level resolution level of the Laplacian pyramids for each of said images, said blending function module generating a blend mask from the image overlap region of said plurality of images, said blending function module constructing a Gaussian pyramid from said blend mask for each said plurality of images, and blending said images by multiplying said Laplacian and Gaussian pyramid values for every level of said Laplacian pyramids for every said plurality of images.

92. The invention according to claim 87, further comprising:

a projection function module in said memory and operating said processor for forming a panorama from said images, said projection function forms said panorama on a geometry that is selected from geometries consisting of;

cubic, polyhedral, cylindrical and spherical geometries, frusto-conical cones joined at their base with the apexes pointing away from one another;

all geometries employing conical sections, and geometries using the following projections;

equidistant, equiangular, ellipsoid, Mercator, transverse Mercator, Oblique Mercator, cylindrical equal-area, Miller cylindrical, equidistant cylindrical, Cassini, Albers equal-area, Lambert conformal conic, equidistant conic, bipolar oblique conic conformal, polyconic, Bonne, azimuthal, orthographic, sterographic, gnomonic, general perspective, Lambert azimuthal equal-area, azimuthal equidistant, modified-stereographic conformal, space map projections, space oblique Mercator, satellite-tracking projections, pseudocylindrical projections, Van der Grinten, sinusoidal, Mollweide and Eckert IV and VI projections.

93. The invention according to claim 87, further comprising:

a user interface module in said memory and operating said processor, said user interface module operating to process input from a user of the computer system, said user interface module allowing the user the ability to manually select the arrangement of said images to be blended.

94. The invention according to claim 93, wherein:

said user interface module comprises a virtual reality environment comprising a spherical coffee table.

95. The invention according to claim 94, wherein:

said user interface module allows the user to select the arrangement of said images from a plurality of rows or columns of photos.

96. The invention according to claim 87, wherein:

said blending function labels the pixels comprising each said overlapping images with values to associate each pixel with a particular image, said blending function module generating a blend mask from the image overlap region of said. images, and computing a boundary to said blend mask from said values of said pixel labels and from said overlapping images.

97. The invention according to 96, wherein said blend mask is constructed by said blending module function performing a grassfire transform on said overlapping images.

98. The invention according to claim 87, further comprising:

a pairwise registration function module in said memory, and operating said processor for pairwise registration of said images, said pairwise registration function module generating output data related to said pairwise registration of said images, said pairwise registration function module operates said processor to register a plurality of each of said images that overlap with one another, by perturbing said images.

99. The invention according to claim 98, wherein:

said pairwise registration function module performs a pairwise registration by performing a projective transformation between said images, said projective transformation is estimated by said pairwise registration function module by performing a gradient-based optimization that minimizes a local error function.

100. The invention according to claim 99, further comprising:

a user interface module in said memory and operating said processor for initializing said projective matrix of said pairwise registration function module, said user interface module operating to process input from a user of the computer system, wherein said projective matrix is initialized with said camera internal and external parameters from manual input by a user; and

,

said error function of said projective transformation is comprised of the differences in exposures between pixels comprising said pairs of overlapping images, and contains a projective matrix initialized by camera internal and external parameters relating to said plurality of images.

101. The invention according to claim 100, wherein:

said internal and external parameters are selected from the group comprising;

image center position of each of said pairs of images, aspect ratio of said pixels comprising said images, the focal length of the camera which took said images;

the camera orientation with respect to a common reference frame, camera pan, tilt, roll and skew and brightness and contrast of said pairs of images.

102. The invention according to claim 100, wherein:

said local error function, eij, is given by the equation

$e_{\mathrm{ij}}=\frac{1}{A_{\mathrm{ij}}}<br><br>\underset{\mathrm{overlap}}{\sum <br><br>}<br><br>{\left(s_{\mathrm{ij}}<br><br>I_j<br><br>\left(X_j\right)+b_{\mathrm{ij}}-I_i<br><br>\left(M_{\mathrm{ij}}<br><br>X_j\right)\right)}^2$

 

where s_ij and b_ij, the exposure parameters, represent the exposure difference, I_i( ) and I_j( ) are pixel intensity values from two images, and A_ij is the overlap area of said images, the vector X_i represents the homogeneous coordinates of the pixel locations making up said images, and the matrix M_ij represents the matrix that transforms coordinates from image j to image i.

103. The invention according to claim 102, wherein:

said pairwise registration function module operates said processor to form a Gaussian pyramid in said memory from said plurality of overlapping images, said Gaussian pyramid having a plurality of levels, each subsequent level being finer than each preceding level, said optimization of said local error function is performed on progressively finer levels of said Gaussian pyramid; and

said pairwise registration function module operates said processor to estimate said exposure parameters, s_ij and b_ij, of said local error function by a correlation-based linear search, and attenuates said exposure parameters with progressive damping, said progressive damping set to maximum at the coarsest level of said pyramid and decreasing to zero at the finest level.

104. The invention according to claim 98, wherein:

said pairwise registration-function module operates said processor to form a Gaussian pyramid in said memory from said plurality of overlapping images, said Gaussian pyramid having a plurality of levels, each subsequent level being finer than each preceding level, said optimization of said local error function is performed on progressively finer levels of said Gaussian pyramid.

105. The invention according to claim 104, wherein:

the number of pyramid levels of said Gaussian pyramid is computed by said pairwise registration function module according to the formula;

${\log <br><br>\text{\hspace{1em}<br><br>}}_2<br><br>\left(\frac{l}{l_{\min }}\right)$

10 where l is the square root of the smaller eigenvalue of the 2×

2 inertial tensor of the overlap polygon region of said plurality of images, and l_min is the minimal size of the finest level resolution pyramid level.

106. The invention according to claim 98, wherein:

a calibration and global optimization function module in said memory and operating said processor for calibration and global optimization of said output data of said pairwise registration module, said calibration and global optimization module generating output data related to said calibration and global optimization of all of said overlapping images.

107. The invention according to claim 106, wherein:

wherein said calibration and global optimization function module calibrates and optimizes said output data of said pairwise registration module by approximating a local error function.

108. The invention according to claim 107, wherein said approximation of said local error function is a Taylor Series expansion given by the formula:

e_ij(M_ij)≈

e_ij⁰+(M_ij−

M_ij⁰)^TC_ij(M_ij−

M_ij⁰)

where e_ij⁰ is a constant representing the minimal value achieved by said pairwise registration function module;

M_ij is the projective matrix of overlapping pairs of images, M_ij⁰ is the vector representing the optimal projective matrix, and C_ij is the Hessian matrix obtained by the pairwise registration function module when optimizing objective function e_ij.

109. The invention according to claim 108, wherein said calibration and global optimization function module calculates a global error function for all overlapping images by application of the chain rule to said output data of said pairwise registration module, according to the formula:

110. The invention according to claim 106, wherein:

said pairwise registration function module performs a pairwise registration by performing a projective transformation between said images, said projective transformation- is estimated by said pairwise registration function module by performing a gradient-based optimization that minimizes a local error function; and

the projective transformation between said pair of said images is initialized by camera internal and external parameters relating to said images in said pairwise registration function module by said calibration and global optimization module, in an iterative manner.

111. The invention according to claim 110, wherein:

said calibration and global optimization function module attenuates camera internal parameters during said calibration and global optimization.

112. The invention according to claim 106, further comprising:

a blending function module in said memory and operating said processor for generating at least one panorama from said output data from said pairwise registration module and said calibration and global optimization module.

114. The invention according to claim 113, wherein:

said pairwise registration means operates said processor to register a plurality of each of said images that overlap with one another, through perturbation of said images.

115. The invention according to claim 114, wherein:

said pairwise registration means estimates a projective transformation between a pair of images by performing a gradient-based optimization that minimizes a local error function.

116. The invention according to claim 115, further comprising:

a user interface module in said memory and operating said processor for initializing said projective matrix of said pairwise registration means, said user interface module operating to process input from a user of the computer system, wherein said projective matrix is initialized with said camera internal and external parameters from manual input by a user; and

the local error function of said pairwise registration means is comprised of the differences in exposures between pixels comprising the pairs of images.

117. The invention according to claim 116, wherein:

said projective transformation contains a projective matrix parametrized by said internal and external parameters, selected from the group comprising;

image center position of each of said pairs of images, aspect ratio of said pixels comprising said images, the focal length of the camera which took said images;

the camera orientation with respect to a common reference frame, camera pan, tilt, roll and skew and brightness and contrast of said pairs of images, and, said projective transformation is initialized by camera internal and external parameters relating to the plurality of images.

118. The invention according to claim 115, wherein:

said local error function, eij, is given by the equation

$e_{\mathrm{ij}}=\frac{1}{A_{\mathrm{ij}}}<br><br>\underset{\mathrm{overlap}}{\sum <br><br>}<br><br>{\left(s_{\mathrm{ij}}<br><br>I_j<br><br>\left(X_j\right)+b_{\mathrm{ij}}-I_i<br><br>\left(M_{\mathrm{ij}}<br><br>X_j\right)\right)}^2$

 

where s_ij and b_ij, the exposure parameters, represent the exposure difference, I_i( ) and I_j( ) are pixel intensity values from two images, and A_ij is the overlap area of said images, the vector X_i represents the homogeneous coordinates of the pixel locations making up said images, and the matrix M_ij represents the matrix that transforms coordinates from image j to image i.

119. The invention according to claim 118, wherein:

said pairwise registration means operates said processor to form a Gaussian pyramid in said memory from said plurality of overlapping images, said Gaussian pyramid having a plurality of levels, each subsequent level being finer than each preceding level, said optimization of said local error function is performed on progressively finer levels of said Gaussian pyramid.

120. The invention according to claim 119, wherein:

the number of pyramid levels of said Gaussian pyramid is computed by said pairwise registration means according to the formula;

${\log }_2<br><br>\left(\frac{l}{l_{\min }}\right)$

 

where l is the square root of the smaller eigenvalue of the 2×

2 inertial tensor of the overlap polygon region of said plurality of images, and l_min is the minimal size of the finest level resolution pyramid level.

121. The invention according to claim 119, wherein:

said pairwise registration means operates said processor to estimate said exposure parameters, s_ij and b_ij, of said local error function by a correlation-based linear search, and attenuates said exposure parameters with progressive damping, said progressive damping set to maximum at the coarsest level of said pyramid and decreasing to zero at the finest level.

122. The invention according to claim 115, wherein:

a calibration and global optimization means in said memory and operating said processor for calibration and global optimization of said output data of said pairwise registration module, said calibration and global optimization module generating output data related to said calibration and global optimization of all of said overlapping images.

123. The invention according to claim 122, wherein:

wherein said calibration and global optimization means calibrates and optimizes said output data of said pairwise registration module by approximating said local error function, eij.

124. The invention according to claim 123, wherein said approximation of said local error function is a Taylor Series expansion given by the formula:

e_ij(M_ij)≈

e_ij⁰+(M_ij−

M_ij⁰)^TC_ij(M_ij−

M_ij⁰)

where e_ij⁰ is a constant representing the minimal value achieved by said pairwise registration means;

M_ij is the projective matrix of overlapping pairs of images, M_ij⁰ is the vector representing the optimal projective matrix, and C_ij is the Hessian matrix obtained by the pairwise registration means when optimizing objective function e_ij.

125. The invention according to claim 123, wherein said calibration and global optimization means calculates a global error function for all overlapping images by application of the chain rule to said output data of said pairwise registration module, according to the formula:

126. The invention according to claim 122, wherein:

said projective transformation is initialized by camera internal and external parameters relating to said plurality of images in said pairwise registration function, said initialization is by said output data generated by said calibration and global optimization module, and said initialization is performed by said calibration and global optimization module in an iterative manner.

127. The invention according to claim 126, wherein:

said calibration and global optimization means attenuates camera internal parameters during said calibration and global optimization.

128. The invention according to claim 122, further comprising:

a blending means in said memory and operating said processor for generating at least one panorama from said output data from said pairwise registration module and said calibration and global optimization module.

129. The invention according to claim 128, wherein:

said blending means generating at least one panorama from said output of said pairwise registration module and said calibration and global optimization module by employing in the image overlap areas of said output a multi-resolution weighted average blending.

130. The invention according to claim 129, further comprising:

a user interface module in said memory and operating said processor for accepting input from a human user, and for selecting said images and adjusting the areas said images overlap.

131. The invention according to claim 129, further comprising:

a projecting means in said memory and operating said processor for forming a panorama from said images, said projection function forms said panorama on a geometry that is selected from-geometries consisting of;

cubic, polyhedral, cylindrical and spherical geometries, frusto-conical cones joined at their base with the apexes pointing away from one another;

all geometries employing conical sections, and geometries using the following projections;

equidistant, equiangular, ellipsoid, Mercator, transverse Mercator, Oblique Mercator, cylindrical equal-area, Miller cylindrical, equidistant cylindrical, Cassini, Albers equal-area, Lambert conformal conic, equidistant conic, bipolar oblique conic conformal, polyconic, Bonne, azimuthal, orthographic, sterographic, gnomonic, general perspective, Lambert azimuthal equal-area, azimuthal equidistant, modified-stereographic conformal, space map projections, space oblique Mercator, satellite-tracking projections, pseudocylindrical projections, Van der Grinten, sinusoidal, Mollweide and Eckert IV and VI projections.

132. The invention according to claim 129, wherein:

said blending means generates said panorama from said output data comprising images having image overlap regions, said image overlap regions blended by said panorama generating means by performing a grassfire transform on data relating to said images to generate a mask of said images.

133. The invention according to claim 129, wherein:

said blending means generates said panorama from said output data comprising images having image overlap regions, said blending means blending by instructing said- processor to construct Laplacian pyramids stored in said memory for each plurality of images that overlap in said image overlap regions, said Laplacian pyramids having a plurality of levels, said blending means determining the coarsest level resolution level of the Laplacian pyramids for each of said images, said blending means generating a blend mask from the image overlap region of said plurality of images, said blending means constructing a Gaussian pyramid from said blend mask for each said plurality of images, and blending said images by multiplying said Laplacian and Gaussian pyramid values for every level of said Laplacian pyramids for every said plurality of images.

134. The invention according to claim 129, wherein:

said blending function labels the pixels comprising each said overlapping images with values to associate each pixel with a particular image, said blending means generating a blend mask from the image overlap region of said images, and computing a boundary to said blend mask from said values of said pixel labels and from said overlapping images.

136. The invention according to claim 135, wherein:

said first data structure comprises parameters in a projective registration matrix;

said second data structure comprises a constant, e_ij representing the minimal value achieved in said projective registration of overlapping images, a vector representing the optimal projective matrix obtained for said constant e_ij, and a Hessian matrix.

113. An apparatus for generating a panorama comprising:

means for pairwise registration of images having overlapping regions;

means for calibration and global optimization of said images;

means for blending said images after pairwise registration, calibration and global optimization of said images;

means for projecting said blended images into a panorama.

135. A computer readable memory comprising:

a memory storing a first data structure for pairwise projective registration of overlapping images;

a memory storing a second data structure for calibration and global optimization of data from said first data structure;

a memory storing a third data structure for blending data from said first and second data structures;

whereby a panorama of three-dimensional images may be constructed from two-dimensional images from said data in said first, second and third data structures.