Image analysis – Image transformation or preprocessing – Combining image portions
Reexamination Certificate
1997-05-30
2001-06-19
Boudreau, Leo (Department: 2621)
Image analysis
Image transformation or preprocessing
Combining image portions
C382S154000, C382S294000, C345S427000, C348S039000
Reexamination Certificate
active
06249616
ABSTRACT:
BACKGROUND
The present invention relates to combining digital images.
Digital images typically comprise two-dimensional arrays of picture elements (pixels) and may be, for example, digitized photographs or computer-generated images. Many applications exist for combining digital images, including applications for determining camera motion between video frames to stabilize video images, for relating or recognizing the content of different images, for aligning images for mosaicing, for high-resolution enhancement, and for building detailed models for virtual reality applications. Further discussion of various applications are found in articles such as S. Mann & R. W. Picard, Video Orbits of the Projective Group: A New Perspective on Image Mosaicing, M.I.T. Media Laboratory Perceptual Computing Section Technical Report No. 338 (1995) and Richard Szeliski, Image Mosaicing for Tele-Reality Applications, Cambridge Research Laboratory Technical Report Series (CRL 94/2) (1994), both of which are incorporated by reference.
Combining images typically requires “registering” pairs of images, which matches two or more images containing overlapping scenes and describes the correspondence of one to another. The correspondence enables the images to be combined by mapping the image data into a common image space using any of a variety of transforms, such as affine and projective transforms. As described in the Mann & Picard article, affine methods are simpler and are acceptable approximations when the correspondence between pictures is high or the images have a small field of view, or the content of the image is planar. Projective transform methods are more complex but can produce results that are mathematically more accurate for images acquired from a fixed camera location. Existing projective transform methods typically register a first image with a second by determining transform parameters corresponding to a two-dimensional projective transformation:
[
&AutoRightMatch;
w
′
u
′
w
′
v
′
w
′
]
=
[
u
v
1
]
[
m
0
m
1
m
2
m
3
m
4
m
5
m
6
m
7
1
]
Equation 1
where (u,v) are the coordinates in an image space of a pixel of the first image and (u′, v′) are the coordinates of the pixel mapped into an image space of the second image. This transform has eight parameters, or degrees of freedom (m
0
, . . . ,m
7
). Solving for the eight degrees of freedom typically requires a non-linear approach, which can be computationally expensive and is not guaranteed to produce a correct result.
SUMMARY
In general, in one aspect, the invention features a computer-implemented method for combining related source images, each represented by a set of digital data, by determining three-dimensional relationships between data sets representing related source images and creating a data set representing an output image by combining the data sets representing the source images in accordance with the determined three-dimensional relationships.
Certain implementations of the invention include one or more of the following features. Each of the source images and the output image may have a corresponding image space. Determining three-dimensional relationships between source images further may include determining three-dimensional transformations between the source image spaces. The output image space may be the image space of a source image. Determining a three-dimensional transformation between one source image space and another image space further may include determining parameters describing the three-dimensional transformation. The parameters may describe a camera orientation, a distance between the camera and the source image, and a distance between the camera and the target image.
In general, in another aspect, the invention features a memory device storing computer readable instructions for aiding a computer to perform the above method.
In general, in another aspect, the invention features an apparatus to combine related source images, each represented by a set of digital data, comprising a storage medium to store related source images, each represented by a set of digital data, and a processor operatively coupled to the storage medium and configured to perform the above method.
Among the advantages of the invention are the following. The invention may be used to create composite images with wide fields of view, to create fully surrounding environments, and to enhance resolution. Further, source images may be merged without identification of specific corresponding features.
The invention determines projective transform parameters for a three-dimensional projective mapping, requiring solving for only five variables (degrees of freedom) rather than the eight required for two-dimensional projective mappings. The invention produces a solution that is always physically realizable, and because the dimensionality of the problem is reduced, a solution may be obtained more quickly. Further, because the parameters may be chosen to be directly related to how the images are acquired, solving for the parameters is readily simplified by further reducing the number of degrees of freedom if there are known constraints on the image acquisition, such as using a single focal length lens for multiple images or restricting motion (such as if the images are all acquired using a camera mounted on a tripod and allowing only panning).
Other advantages and features of the invention will become apparent from the following description and from the claims.
REFERENCES:
patent: 4598369 (1986-07-01), Wang et al.
patent: 4673988 (1987-06-01), Jansson et al.
patent: 4797942 (1989-01-01), Burt et al.
patent: 5187754 (1993-02-01), Currin et al.
patent: 5444478 (1995-08-01), LeLong et al.
patent: 5531520 (1996-07-01), Grimson et al.
patent: 5586231 (1996-12-01), Florent et al.
patent: 5611000 (1997-03-01), Szeliski et al.
patent: 5613013 (1997-03-01), Schuette
patent: 5629988 (1997-05-01), Burt et al.
patent: 5649032 (1997-07-01), Burt et al.
patent: 5650814 (1997-07-01), Florent et al.
patent: 5684890 (1997-11-01), Miyashita et al.
patent: 5699444 (1997-12-01), Palm
patent: 5706416 (1998-01-01), Mann et al.
patent: 5757321 (1998-05-01), Billyard
patent: 5825369 (1998-10-01), Rossignac et al.
patent: 5881163 (1999-03-01), Slump et al.
patent: 0 563 737 A1 (1993-03-01), None
patent: WO 98 12504 (1998-03-01), None
Lipari et al., Geometric Modeling and Recognition of elongated Regions in Arial Images, IEEE vol. 19 No. 6, pp. 1600-1612, Dec. 1989.*
R. I. Hartley, “Projective Reconstruction and Invarants from Multiple Images”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 16, No. 10, Oct. 1, 1994, pp. 1036-1041.
P.J. Burt and E.H. Adelson, A Multiresolution Spline with Application to Image Mosaics, ACM Transactions on Graphics, pp. 217-36 (Oct. 1983).
Mann and Picard, Video Orbits of the Projective Group: A New Perspective on Image Mosaicing, MIT Media Lab Tech Report No. 338 (1995).
Mann, Compositing Multiple Pictures of the Same Scene: Generalized Large-Displacement 8-Parameter Motion, Proceedings of the 46th Annual IS&T Conference, Cambridge, Massachusetts (May 9-14, 1993).
Brown, A Survey of Image Registration Techniques, ACM Computing Surveys (1992).
D.J. Burr, A Dynamic Model for Image Registration, Computer Graphics and Image Processing (1981).
F. Bartolini et al., A Noise Resistant Optical Flow Algorithm, Proceedings of 7th Intl. Conference on Image Analysis & Processing (Sep. 20-22, 1993).
P. Haeberli and E. Ofek, Automatic Panoramic Image Merging, http://www.sgi.com/grafica/mergeindex.html (1997).
P. Haeberli and E. Ofek, “align.c” source code (1993).
Bergen et al., Hierarchical Model-Based Motion Estimation, ECCV '92, 2nd European Conference on Computer Vision (May 1992).
R.M. Hord, Digital Image Processing of Remotely Sensed Data, Academic Press (May 1982).
Irani and Peleg, Improving Resolution by Image Registration, CVGIP: Graphical Models and Image Processing (1991).
R. Szeliski, Image Mosaicing for Tele-Reality Applications, Digital Equipment Corporat
Boudreau Leo
Enroute, INC
Fish & Richardson P.C.
Sherali Ishrat
LandOfFree
Combining digital images based on three-dimensional... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Combining digital images based on three-dimensional..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combining digital images based on three-dimensional... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2528928