US6434265B1 — Aligning rectilinear images in 3D through project…

Claim 1

Independent Claim 209 words

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, the pairwise registration function module including a projective matrix, wherein the projective matrix is a function of image center position, said output data including a Hessian matrix; 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.

Claim 2

Dependent Claim 209 words

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, the pairwise registration function module including a projective matrix, wherein the projective matrix is a function of image center position, said output data including a Hessian matrix; 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.

Claim 3

Dependent Claim 34 words

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.

Claim 4

Dependent Claim 45 words

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.

Claim 5

Dependent Claim 110 words

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.

Claim 6

Dependent Claim 72 words

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.

Claim 7

Dependent Claim 23 words

The invention in accordance with claim 4 , wherein said user interface module comprises a virtual reality environment comprising a spherical coffee table.

Claim 8

Dependent Claim 31 words

The invention according to claim 6 , wherein: said user interface module allows the user to select the arrangement of said images from a plurality of rows or columns of photos.

Claim 9

Dependent Claim 128 words

The invention according to claim 3 , wherein: said local error function, eij, is given by the equation e ij = 1 A ij  ∑ overlap  ( s ij  I j  ( X j ) + b ij - I i  ( M ij  X j ) ) 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.

Claim 10

Dependent Claim 122 words

The invention according to claim 8 , 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.

Claim 11

Dependent Claim 64 words

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.

Claim 12

Dependent Claim 76 words

The invention according to claim 10 , wherein: the number of pyramid levels of said Gaussian pyramid is computed by said pairwise registration function module according to the formula: log 2  ( l l min ) where I 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 I min is the minimal size of the finest level resolution pyramid level.

Claim 13

Dependent Claim 58 words

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.

Claim 14

Dependent Claim 32 words

The invention according to claim 12 , 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.

Claim 15

Dependent Claim 112 words

The invention according to claim 13 , wherein said approximation of said local error function, eij, is a Taylor Series expansion given by the formula: e ij ( M ij )≈ e ij 0 +( M ij −M ij 0 ) T C ij ( M ij −M ij 0 ) where e ij 0 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 0 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 .

Claim 16

Dependent Claim 111 words

The invention according to claim 14 , 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: ∂ E ∂ ( p i , q i ) = ∑ j  ∂ e ij ∂ M ij  ∂ M ij ∂ ( p i , q i ) and minimizes said global error function, where p j =the vector for camera internal parameters for each image j, and q j =the camera orientation with respect to a common reference frame for each image j.

Claim 17

Dependent Claim 27 words

The invention according to claim 12 , further comprising: said pairwise registration function module operates said processor to estimate a projective transformation for pairwise registration of images.

Claim 18

Dependent Claim 73 words

The invention according to claim 16 , 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.

Claim 19

Dependent Claim 33 words

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.

Claim 20

Dependent Claim 60 words

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.

Claim 21

Dependent Claim 141 words

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.

Claim 22

Dependent Claim 39 words

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.

Claim 23

Dependent Claim 18 words

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

Claim 24

Dependent Claim 116 words

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; any quadric surface 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.

Claim 25

Dependent Claim 33 words

The invention in accordance with claim 1 , 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.

Claim 26

Dependent Claim 111 words

The invention according to claim 24 , wherein said approximation of said local error function is a Taylor Series expansion given by the formula: e ij ( M ij )≈ e ij 0 +( M ij −M ij 0 ) T C ij ( M ij −M ij 0 ) where e ij 0 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 0 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 .

Claim 27

Dependent Claim 111 words

The invention according to claim 25 , 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: ∂ E ∂ ( p i , q i ) = ∑ j  ∂ e ij ∂ M ij  ∂ M ij ∂ ( p i , q i ) and minimizes said global error function, where p j =the vector for camera internal parameters for each image j, and q j =the camera orientation with respect to a common reference frame for each image j.

Claim 28

Dependent Claim 125 words

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, wherein the projective transformation includes a projective matrix, the matrix being a function of image center position; generating image output data by calibration and global optimization of said rectilinear images from image output data from said pairwise registration, said image output data including a Hessian matrix; blending said rectilinear images to create a panorama from said generated image output data from said pairwise registration and said calibration and global optimization.

Claim 29

Dependent Claim 125 words

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, wherein the projective transformation includes a projective matrix, the matrix being a function of image center position; generating image output data by calibration and global optimization of said rectilinear images from image output data from said pairwise registration, said image output data including a Hessian matrix; blending said rectilinear images to create a panorama from said generated image output data from said pairwise registration and said calibration and global optimization.

Claim 30

Dependent Claim 67 words

The method according to claim 27 , 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.

Claim 31

Dependent Claim 85 words

The method according to claim 27 , 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.

Claim 32

Dependent Claim 73 words

The method according to claim 29 , 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.

Claim 33

Dependent Claim 147 words

The method according to claim 29 , wherein: said local registration error function, eij, is given by the equation: e ij = 1 A ij  ∑ overlap  ( s ij  I j  ( X j ) + b ij - I i  ( M ij  X j ) ) 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.

Claim 34

Dependent Claim 59 words

The method according to claim 31 , 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.

Claim 35

Dependent Claim 26 words

The method according to claim 32 , further comprising the step of: estimating said exposure parameters, sij and bij, according to a correlation based linear search.

Claim 36

Dependent Claim 39 words

The method according to claim 31 , 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.

Claim 37

Dependent Claim 79 words

The method according to claim 34 , 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  ( l l min ) where I 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 I min is the minimal size of the finest level resolution pyramid level.

Claim 38

Dependent Claim 142 words

The invention according to claim 29 , 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 0 +( M ij −M ij 0 ) T C ij ( M ij −M ij 0 ) where e ij 0 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 0 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 .

Claim 39

Dependent Claim 118 words

The invention according to claim 36 , 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: ∂ E ∂ ( p i , q i ) = ∑ j  ∂ e ij ∂ M ij  ∂ M ij ∂ ( p i , q i ) minimizing said global error function, where p j =the vector for camera internal parameters for each image j, and q j =the camera orientation with respect to a common reference frame for each image j.

Claim 40

Dependent Claim 32 words

The invention according to claim 37 , 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.

Claim 41

Dependent Claim 38 words

The method according to claim 27 , 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.

Claim 42

Dependent Claim 29 words

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

Claim 43

Dependent Claim 106 words

The invention according to claim 27 , 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.

Claim 44

Dependent Claim 36 words

The method according to claim 41 , 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.

Claim 45

Dependent Claim 67 words

The invention according to claim 41 , 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.

Claim 46

Dependent Claim 47 words

The invention according to claim 41 , 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.

Claim 47

Dependent Claim 135 words

The invention according to claim 27 , 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; any quadric surface, 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.

Claim 48

Dependent Claim 66 words

A computer readable memory storing a program which executes the steps of: storing at least a pair of rectilinear images in a computer memory; and performing pairwise registration of said rectilinear images by calculating a projective transformation between said rectilinear images, the projective transformation includes a projective matrix, the matrix being a function of image center position, said pairwise registration function module generating a Hessian matrix.

Claim 49

Dependent Claim 66 words

A computer readable memory storing a program which executes the steps of: storing at least a pair of rectilinear images in a computer memory; and performing pairwise registration of said rectilinear images by calculating a projective transformation between said rectilinear images, the projective transformation includes a projective matrix, the matrix being a function of image center position, said pairwise registration function module generating a Hessian matrix.

Claim 50

Dependent Claim 85 words

The method according to claim 46 , 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.

Claim 51

Dependent Claim 75 words

The method according to claim 47 , 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.

Claim 52

Dependent Claim 147 words

The method according to claim 47 , wherein: said local registration error function, eij, is given by the equation: e ij = 1 A ij  ∑ overlap  ( s ij  I j  ( X j ) + b ij - I i  ( M ij  X j ) ) 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.

Claim 53

Dependent Claim 59 words

The method according to claim 49 , 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.

Claim 54

Dependent Claim 26 words

The method according to claim 50 , further comprising the step of: estimating said exposure parameters, sij and bij, according to a correlation based linear search.

Claim 55

Dependent Claim 39 words

The method according to claim 49 , 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.

Claim 56

Dependent Claim 79 words

The method according to claim 52 , 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  ( l l min ) where I 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 I min is the minimal size of the finest level resolution pyramid level.

Claim 57

Dependent Claim 96 words

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; and 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, the pairwise registration function module including a projective matrix, wherein the projective matrix is a function of image center position, said output data including a Hessian matrix.

Claim 58

Dependent Claim 96 words

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; and 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, the pairwise registration function module including a projective matrix, wherein the projective matrix is a function of image center position, said output data including a Hessian matrix.

Claim 59

Dependent Claim 34 words

The invention according to claim 54 , 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.

Claim 60

Dependent Claim 29 words

The invention according to claim 55 , wherein: said pairwise registration function module performs said pairwise registration by estimating a projective transformation relating a pair of images that overlap.

Claim 61

Dependent Claim 68 words

The invention according to claim 56 , 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.

Claim 62

Dependent Claim 184 words

The invention according to claim 57 wherein: said local error function, eij, is given by the equation e ij = 1 A ij  ∑ overlap  ( s ij  I j  ( X j ) + b ij - I i  ( M ij  X j ) ) 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.

Claim 63

Dependent Claim 76 words

The invention according to claim 58 , wherein: the number of pyramid levels of said Gaussian pyramid is computed by said pairwise registration function module according to the formula: log 2  ( l l min ) where I 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 I min is the minimal size of the finest level resolution pyramid level.

Claim 64

Dependent Claim 66 words

The invention according to claim 58 , 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.

Claim 65

Dependent Claim 65 words

The invention according to claim 56 , 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.

Claim 66

Dependent Claim 72 words

The invention according to claim 61 , 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.

Claim 67

Dependent Claim 24 words

The invention according to claim 61 , wherein: said user interface module allows the user the ability to select the arrangement of said images.

Claim 68

Dependent Claim 22 words

The invention according to claim 63 , wherein: said user interface module comprises a virtual reality environment comprising a spherical coffee table.

Claim 69

Dependent Claim 34 words

The invention according to claim 64 , 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.

Claim 70

Dependent Claim 58 words

The invention according to claim 56 , 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.

Claim 71

Dependent Claim 33 words

The invention according to claim 66 , 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.

Claim 72

Dependent Claim 111 words

The invention according to claim 67 , wherein said approximation of said local error function is a Taylor Series expansion given by the formula: e ij ( M ij )≈ e ij 0 +( M ij −M ij 0 ) T C ij ( M ij −M ij 0 ) where e ij 0 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 0 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 .

Claim 73

Dependent Claim 111 words

The invention according to claim 67 , 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: ∂ E ∂ ( p i , q i ) = ∑ j  ∂ e ij ∂ M ij  ∂ M ij ∂ ( p i , q i ) and minimizes said global error function, where p j =the vector for camera internal parameters for each image j, and q j =the camera orientation with respect to a common reference frame for each image j.

Claim 74

Dependent Claim 50 words

The invention according to claim 66 , 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.

Claim 75

Dependent Claim 25 words

The invention according to claim 70 , wherein: said calibration and global optimization function module attenuates camera internal parameters during said calibration and global optimization.

Claim 76

Dependent Claim 42 words

The invention according to claim 66 , 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.

Claim 77

Dependent Claim 47 words

The invention according to claim 72 , 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.

Claim 78

Dependent Claim 84 words

The invention according to claim 73 , 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.

Claim 79

Dependent Claim 56 words

The invention according to claim 73 , 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.

Claim 80

Dependent Claim 22 words

The invention according to claim 75 , wherein: said user interface module comprises a virtual reality environment comprising a spherical coffee table.

Claim 81

Dependent Claim 29 words

The invention according to claim 76 , wherein: said user interface module allows the user to select the arrangement of said images from a plurality of rows of photos.

Claim 82

Dependent Claim 55 words

The invention according to claim 73 , 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.

Claim 83

Dependent Claim 37 words

The invention according to claim 73 , 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.

Claim 84

Dependent Claim 18 words

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

Claim 85

Dependent Claim 142 words

The invention according to claim 73 , 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.

Claim 86

Dependent Claim 65 words

The invention according to claim 73 , 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.

Claim 87

Dependent Claim 134 words

The invention according to claim 73 , 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; any quadric surface, 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.

Claim 88

Independent Claim 70 words

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; said pairwise registration function module including a projective matrix, wherein the projective matrix is a function of image center position; and means for projecting said blended images into a panorama.

Claim 89

Independent Claim 70 words

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; said pairwise registration function module including a projective matrix, wherein the projective matrix is a function of image center position; and means for projecting said blended images into a panorama.

Claim 90

Dependent Claim 34 words

The invention according to claim 84 , 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.

Claim 91

Dependent Claim 32 words

The invention according to claim 85 , 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.

Claim 92

Dependent Claim 88 words

The invention according to claim 86 , 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.

Claim 93

Dependent Claim 98 words

The invention according to claim 87 , 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.

Claim 94

Dependent Claim 128 words

The invention according to claim 86 , wherein: said local error function, eij, is given by the equation e ij = 1 A ij  ∑ overlap  ( s ij  I j  ( X j ) + b ij - I i  ( M ij  X j ) ) 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.

Claim 95

Dependent Claim 63 words

The invention according to claim 89 , 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.

Claim 96

Dependent Claim 75 words

The invention according to claim 90 , wherein: the number of pyramid levels of said Gaussian pyramid is computed by said pairwise registration means according to the formula: log 2  ( l l min ) where I 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 I min is the minimal size of the finest level resolution pyramid level.

Claim 97

Dependent Claim 65 words

The invention according to claim 90 , 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.

Claim 98

Dependent Claim 57 words

The invention according to claim 86 , 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.

Claim 99

Dependent Claim 33 words

The invention according to claim 93 , 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.

Claim 100

Dependent Claim 109 words

The invention according to claim 94 , wherein said approximation of said local error function is a Taylor Series expansion given by the formula: e ij ( M ij )≈ e ij 0 +( M ij −M ij 0 ) T C ij ( M ij −M ij 0 ) where e ij 0 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 0 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 .

Claim 101

Dependent Claim 110 words

The invention according to claim 94 , 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: ∂ E ∂ ( p i , q i ) = ∑ j  ∂ e ij ∂ M ij  ∂ M ij ∂ ( p i , q i ) and minimizes said global error function, where p j =the vector for camera internal parameters for each image j, and q j =the camera orientation with respect to a common reference frame for each image j.

Claim 102

Dependent Claim 61 words

The invention according to claim 93 , 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.

Claim 103

Dependent Claim 24 words

The invention according to claim 97 , wherein: said calibration and global optimization means attenuates camera internal parameters during said calibration and global optimization.

Claim 104

Dependent Claim 41 words

The invention according to claim 93 , 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.

Claim 105

Dependent Claim 46 words

The invention according to claim 99 , 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.

Claim 106

Dependent Claim 39 words

The invention according to claim 100 , 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.

Claim 107

Dependent Claim 133 words

The invention according to claim 100 , 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; any quadric surface, 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.

Claim 108

Dependent Claim 52 words

The invention according to claim 100 , 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.

Claim 109

Dependent Claim 137 words

The invention according to claim 100 , 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.

Claim 110

Dependent Claim 64 words

The invention according to claim 100 , 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.

Claim 111

Dependent Claim 232 words

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; 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 image overlap regions; and a projection function module in said memory and operating said processor for forming a panorama from said images.

Claim 112

Dependent Claim 232 words

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; 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 image overlap regions; and a projection function module in said memory and operating said processor for forming a panorama from said images.

Claim 113

Dependent Claim 227 words

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; and 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.

Claim 114

Dependent Claim 227 words

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; and 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.

Claim 115

Dependent Claim 84 words

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; and 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, for use in a global optimization function module, said output data including a Hessian matrix.

Claim 116

Dependent Claim 84 words

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; and 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, for use in a global optimization function module, said output data including a Hessian matrix.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2005-08-12	2006-02-11	2006-08-13	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2009-08-12	2010-02-11	2010-08-13	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2013-08-12	2014-02-11	2014-08-13	$7700.00	Window Closed / Lapsed

Aligning rectilinear images in 3D through projective registration and calibration

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag