United States Patent [19]
`Szeliski et al.
`
`[54] 3-DIMENSIONAL IMAGE ROTATION
`METHOD AND APPARATUS FOR
`PRODUCING IMAGE MOSAICS
`
`[75] Inventors: Richard Szeliski; Heung-Yeung Shum,
`both of Bellevue, Wash.
`[73] Assignee: Microsoft Corporation, Redmond,
`Wash.
`
`[*] Notice:
`
`This patent is subject to a terminal dis
`claimer.
`
`[21] Appl. No.: 08/904,922
`[22] Filed:
`Aug. 1, 1997
`
`US006157747A
`[11] Patent Number:
`[45] Date of Patent:
`
`6,157,747
`*Dec. 5, 2000
`
`J. R. Bergen, P. Anandan, K. J. Hanna, and R. Hingorani.
`Hierarchical model—based motion estimation. In Second
`European Conference on Computer Vision (ECCV'92), pp.
`237–252, Santa Margherita Liguere, Italy, May 1992.
`Springer-Verlag.
`S. J. Gortler, R. Grzeszczuk, R. Szeliski, and M.F. Cohyen.
`The lumigrap. In Computer Graphics Proceedings, Annual
`Conference Series, pp. 43–54, Proc. SIGGRAPH '96 (New
`Orleans), Aug. 1996. ACM SIGGRAPH.
`S. E. Chen. QuickTime VR—an image—based approach to
`virtual environment navigation. Computer Graphics (SIG
`GRAPH '95), pp. 29–38, Aug. 1995.
`
`(List continued on next page.)
`
`[52] U.S. Cl. .......................... 382/284; 345/435; 345/437;
`348/36; 38.2/296
`
`41 Claims, 25 Drawing Sheets
`
`(4 of 25 Drawing Sheet(s) Filed in Color)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`- 1110
`
`INPUT IMAGESI: (X) AND I (x) AND THE
`ORIENTATIONS, R, ANDR, OF, AND I,
`RELATIVE TO APOINT P
`|N 3D WORLD COORDINATES
`1130
`2 f
`t
`FORLATEST VERSION OFi, FIND AN INCREMENTAL
`ROTATIONR (Q) OFXTHROUGHA3D ANGLE
`Q = (Wx, Wy, W2 WHICH PROVIDES BETTER
`REGISTRATION OFI, WITHI,
`
`UPDATEMAS M. V. R.R.'vº tº 1140
`
`UPDATE?, BY RESAMPLING II
`USING THE LATEST VERSION OF M
`
`1160
`
`ARE THE
`LATEST RESIDUA:
`REGISTRATIONERRORS
`NEGugble
`
`
`
`YES
`OUTPUTATESIVERSION OF
`1 ANDR;
`
`| 11so
`
`[51] Int. Cl." … G06K 9/36
`Primary Examiner—Bhavesh Mehta
`Attorney, Agent, or Firm—Michaelson & Wallace; Peter L.
`Michaelson
`ABSTRACT
`[57]
`The invention aligns a set of plural images to construct a
`mosaic image. At least different pairs of the images overlap
`partially (or fully), and typically are images captured by a
`camera looking at the same scene but oriented at different
`angles from approximately the same location or similar
`locations. In order to align one of the images with another
`one of the images, the following steps are carried out: (a)
`determining a difference error between the one image and
`the other image; (b) computing an incremental rotation of
`the one image relative to a 3-dimensional coordinate system
`through an incremental angle which tends to reduce the
`difference error; and (c) rotating the one image in accor
`dance with the incremental rotation to produce an incremen
`tally warped version of the one image. As long as the
`difference error remains significant, the method continues by
`re-performing the foregoing determining, computing and
`rotating steps but this time with the incrementally warped
`version of the one image.
`
`[58] Field of Search ..................................... 382/154, 284,
`382/294, 296, 282; 345/419, 425–438;
`348/42, 263, 580, 36, 37
`References Cited
`U.S. PATENT DOCUMENTS
`
`[56]
`
`5,187,754 2/1993 Currin et al. ........................... 382/284
`5,488,674
`1/1996 Burt et al. .........
`... 382/284
`5,581,638 12/1996 Givens et al.
`... 382/294
`5,649,032 7/1997 Burt et al. ............................... 382/294
`5,907,626 5/1999 Toklu et al. ............................ 382/284
`OTHER PUBLICATIONS
`Richard Szeliski and James Coughlan, “Spline—Based Image
`Registration,” Tech Report CRL 94/1, Digital Equipment
`Corporation, Cambridge Research Lab, Cambridge, MA,
`Apr. 1994.
`P. Anandan et al., editors. IEEE Workshop on Representa
`tions of Visual Scenes, Cambridge, Massachusetts, Jun.
`1995, IEEE Computer Society Press. pp. 10–17.
`Anonymous. Creating full view panoramic image mosaics
`and texture—mapped models. In Computer Graphics Pro
`ceedings Annual Conference Series, Proc. SIGGRAPH '97
`(Los Angeles) Aug. 1997, ACM SIGGRAPH. pp. 251–258.
`
`Prime Focus Ex 1037-1
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`6,157,747
`Page 2
`
`OTHER PUBLICATIONS
`R. I. Hartley. Self-calibration from multiple views of a
`rotating camera. In Third European Conference on Com
`puter Vision (ECCV’94), vol. 1, pp. 471–478, Stockholm,
`Sweden, May 1994. Springer-Verlag.
`M. Irani, S. Hsu, and P. Anandan. Video compression using
`mosaic representations. Signal Processing: Image Commu
`nication, 7:529–552, 1995.
`S. B. Kang and R. Weiss. Characterization of errors in
`compositing panoramic images, Technical Report 96/2,
`Digital Equipment Corporation, Cambridge Research Lab,
`Jun. 1996.
`M,-C. Lee et al. A layered video object occling system using
`sprite and affine motion model. IEEE Transactions on Cir
`cuits and Systems For Video technology, 7(1):130–145, Feb.
`1997.
`M. Levoy and P. Hanrahan. Light field rendering. In Com
`puter Graphics Proceedings, Annual Conference Series, pp.
`31–42, Proc. SIGGRAPH '96 (New Orleans), Aug. 1996.
`ACM SIGGRAPH.
`B.D. Lucas and T. Kanade. An iterative image registration
`technique with an application in stereo vision. In Seventh
`International Joint Conference on Aritificial Intelligence
`(IJCAI-81), pp. 674–679, Vancouver, 1981.
`H. E. Malde. Panoramic photographs. American Scientist,
`71(2):132–140, Mar.-Apr. 1983.
`L. McMillan and G. Bishop. Plenoptic modeling: An
`image—based rendering system. Computer Graphics (SIG
`GRAPH '95), pp. 39–46, Aug. 1995.
`S. Mann and R. W. Picard. Virtual bellows: Constructing
`high-quality images from video. In First IEEE International
`Conference on Image Processing (ICIP–94), vol. I, pp.
`363–367, Austin, Texas, Nov. 1994.
`
`W. H. Press, B.P. Flannery, S. A. Teukolsky, and W.T.
`VCetterling. Numerical Recipes in C: The Art of Scientific
`Computing. Cambridge University Press, Cambridge,
`England, second edition, 1992.
`G. S. Stein. Accurate internal camera calibration using
`rotation, with analysis of sources of error. In Fifth Interna
`tional Conference on Computer Vision (ICCV'95), pp.
`230–236, Cambridge, Massachusetts, Jun. 1995.
`R. Szeliski. Image mosaicing for tele—reality applications. In
`IEEE Workshop on Applications of Computer Vision
`(WACV'94), pp. 44–53, Sarasota, Florida, Dec. 1994. IEEE
`Computer Society.
`R. Szeliski. Video mosaics for virtual environments. IEEE
`Computer Graphics and Applications, pp. 22–30, Mar. 1996.
`G. Wolberg “Digital Image Warping” IEEE Computer Soci
`ety Press, Los Alamitos, Ca. 1990.
`Ned Greene, New York Institute of Technology “Environ
`ment Mapping and Other AQpplications Of World Projec
`tions” IEEE, Nov. 1986, pp. 21–29.
`Roger Y. Tsai. “A Verstile,e Camera Calibration Technique
`for High—Accuracy 3D Machine Vision Metrology Using
`Off—The-Shelf TV Camerads and Lenses” IEEE Journal of
`Robotics and Automation vol. RA-3, Aug 1987, pp.
`323–344.
`Hank Weghorst, Gary Hooper, and Donald P. Greenberg,
`Cornell University ACM Transactions on Graphics, vol. 3,
`No. 1, Jan. 1984, pp. 52–69.
`Lance Williams. Computer Graphics Laboratory New York
`Institute of Technology Old Westbury, New York, ACM
`0–089791–10–9–1/83, Computer Graphics vol. 17, Nov. 3,
`Jul. 1983, pp. 1–11.
`
`Prime Focus Ex 1037-2
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 1 of 25
`
`6,157,747
`
`ESTIMATE FOCAL LENGTH
`
`110
`
`|MAGE ALIGNMENT
`USING PATCH-BASED
`ALGORITHM, PREFERABLY)
`
`120
`
`GLOBAL IMAGE ALIGNMENT
`
`130
`
`DEGHOSTING LOCALALIGNMENT tº 149
`ENVIRONMENTTEXTURE MAPPING OF COLORST-199
`BLENDED FROM OVERLAPPING IMAGES
`
`STANDARD3-D GRAPHICS SOFTWARE T-160
`
`OUTPUT
`
`|MAGE
`
`FIG. 1
`
`Prime Focus Ex 1037-3
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`
`
`Sheet 2 of 25
`
`
`
`
`
`WELSÅS
`
`0N|| WHEdO
`
`Prime Focus Ex 1037-4
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 3 of 25
`
`6,157,747
`
`220
`
`12
`
`--
`
`— I
`
`\ -T 210
`
`.* º ==
`
`230
`
`240
`
`260
`
`|MAGE
`MEMORY
`
`PROGRAM
`MEMORY
`|MAGE
`ALIGNMENT
`ALGORITHM
`
`
`
`
`
`
`
`|MAGE WARP
`MEMORY
`MO, M1, M2,
`M3, - - - Mk
`
`250
`
`MICROPROCESSOR
`
`270
`
`ENVIRONMENT/
`TEXTURE MAP
`MEMORY
`3–D MODEL
`
`
`
`
`
`
`
`TEXTURED MAP
`3.
`
`
`
`IMAGE OUTPUT?
`DISPLAY|MONITOR
`
`FIG. 2B
`
`Prime Focus Ex 1037-5
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 4 of 25
`
`6,157,747
`
`
`
`PANARAMIC
`
`FIG. 3
`
`Prime Focus Ex 1037-6
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 5 of 25
`
`6,157,747
`
`
`
`P,
`WORLD 3D
`COORD, SYS
`
`(0,0,0)
`
`P,
`
`FIG. 4
`
`520
`
`510
`
`FIG. 5
`
`Prime Focus Ex 1037-7
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 6 of 25
`
`6,157,747
`
`FIG. 6
`
`J.D.
`
`
`
`FIG. 7
`
`Prime Focus Ex 1037-8
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 7 of 25
`
`6,157,747
`
`|NPUT PARTIALLY OVERLAPPING IMAGES
`Io (x) AND I1 (x)
`
`810
`
`820
`
`INITALIZETRANSFORM MATRIXM (E.G., M-I)
`
`FORLATEST VERSION OF I., (x), FINDADEFORMATION
`D OF x WHICHPROVIDES BETTERREGISTRATION OF
`In WITH Io, WHERE I4 (x) = It (x)
`
`830
`
`M -— (I +D) M
`
`840
`
`860
`
`UPDATE I: BY RESAMPLING (925) THE LATEST
`VERSION OF I. USING THE LATEST VERSION OFM
`
`
`
`
`
`
`
`
`
`870
`
`ARE
`THE LASTEST
`RESIDUAL REGISTRATION
`ERRORS NEGLIGELE
`
`
`
`
`
`880
`
`YES
`OUTPUTLATEST VERSION OF
`IT AND M
`
`FIG. 8
`
`Prime Focus Ex 1037-9
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 8 of 25
`
`6,157,747
`
`GRADENT
`9
`
`917
`
`M -— (I + D) M
`980
`
`D = F (d)
`
`
`
`NORMAL ECUATION
`SOLVER
`
`Prime Focus Ex 1037-10
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 9 of 25
`
`6,157,747
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`START AT COARSEST IMAGE RESOLUTION
`
`PERFORM ALIGNMENT ALGORITHM
`USING PRIOR RESULTS
`
`1020
`
`HIGHEST
`|MAGE RESOLUTION
`IEEl
`
`OUTPUT
`RESULTS
`
`1050
`
`GO TO THE NEXT HIGHEST RESOLUTION LEVEL
`AND PERFORM THE REQUIRED MODIFICATION
`OF THE ALIGNMENT PARAMETERS
`e.g. MODIFY ESTIMATE OFM
`FIG. 10
`
`
`
`
`
`
`
`PERFORMAT LEAST A ROUGH ALIGNMENT OF
`Io, I, USING INCREMENTALALIGNMENT
`ALGORITHM WITH PERSPECTIVE TRANSFORM M
`
`
`
`EXTRACT INDIVIDUALELEMENT OFM (moTHROUGH my)
`
`
`
`
`
`ESTIMATE FOCAL LENGTHS fo, f,
`FROMAFUNCTION OF moTHROUGHM,
`FIG. 13
`
`1330
`
`Prime Focus Ex 1037-11
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 10 of 25
`
`6,157,747
`
`INPUT IMAGES I, (x) AND I (X) AND THE
`ORIENTATIONS, RK AND R1, OFlk AND II
`RELATIVE TO A POINT P
`|N 3D WORLD COORDINATES
`
`1110
`
`1130
`
`FORLATEST VERSION OFI, FINDAN INCREMENTAL
`ROTATION R (Q) OFX THROUGH A3D ANGLE
`Q = (Wx, Wy, WZ) WHICH PROVIDES BETTER
`REGISTRATION OF I, WITH I,
`
`UPDATE MASM - V. R. R. V.'
`
`1140
`
`UPDATE?, BY RESAMPLING II
`USING THE LATEST VERSION OF M
`
`1160
`
`1170
`
`NO
`
`ARE THE
`LATEST RESIDUA:
`REGISTRATION ERRORS
`NEGugble
`
`YES
`
`OUTPUTLATEST VERSION OF
`I AND RI
`FIG. 11
`
`1 180
`
`Prime Focus Ex 1037-12
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 11 of 25
`
`6,157,747
`
`1225
`
`1205
`1230 |{-
`
`aw
`
`I º
`
`- - - - -
`
`WARP - * º: M-V. R. R. 'V'
`Il
`
`
`
`RODRIGUEZ
`FORMULA
`R (Q) = G (Q)
`
`NORMAL ECUATION
`SOLVER
`
`1275
`
`FIG. 12
`
`Prime Focus Ex 1037-13
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 12 of 25
`
`6,157,747
`
`|NNER LOOP
`
`e;
`
`*
`
`
`
`
`
`
`
`1245 GRADENT
`9i
`|
`1265
`
`
`
`COMPUTE
`JACOBANJ;
`AT CENTER
`OF PATCH j
`
`ri.T
`919
`
`ALLPXELS
`IN PATCH
`|
`*
`
`Ji
`
`1425
`
`1460
`
`SUMOVER
`ALL PIXELS
`INPATCH
`1470
`
`
`
`NVERSE|| ALLPXELs
`IN PATCH j
`
`
`
`COMPUTE
`WEIGHTS
`W
`
`TRANSPOSER
`
`1485
`
`1487
`
`- - - - - - - Willibi
`
`|| Williº'
`
`|
`
`“[SUNOMERAI] *[sºoyºAll tº
`OUTER |
`PATCHES
`PATCHES
`1470
`|
`1 < j < m
`1 < j < m —- |
`| _ _ –H —H l
`b
`A
`
`Prime Focus Ex 1037-14
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`Prime Focus Ex 1037-15
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 14 of 25
`
`6,157,747
`
`1
`1810
`
`PERFORM PATCH-BASED ALIGNMENT TO
`PRODUCER FOREACH IMAGE Ik
`
`1820
`
`DETERMINE FROM RK's WHICH IMAGES ARE
`SIGNIFICANTLY OVERLAPPING PAIRS
`
`1830 —? DEFINE PATCHESj|NONE IMAGE Ik
`
`1840
`
`1850
`
`FOREACH PATCH j|N IMAGE I, FIND WHICH
`|MAGES OVERLAP THAT PATCH AND COMPUTE
`OPTIMAL REGISTRATION AND ERROR
`
`DISCARD º DEWEIGHT) PATCHES HAVING
`HIGH RES UALERROR (OR LOWVARIANCE)
`
`1860
`
`
`
`PERFORM SIMULTANEOUS INCREMENTAL 3D ROTATIONS
`R § (ORWARPINGSM) OF EACH IMAGE OF THE
`SET OF PARS, SOAS TO CONVERGE EACH PAIR
`OF CENTER-RAY-DIRECTIONS
`FOREACHIMAGE I. UPDATER, ORMBYEON 17; r1870
`RECOMPUTE fl. AND FORMV,
`
`|S
`YES 213ESIDUALRAY
`DIVERGENCE
`sGNECANI
`rºo
`
`1880
`
`1890
`
`|
`
`OUTPUT RK FOR EACH IMAGE
`
`FIG. 18
`
`Prime Focus Ex 1037-16
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 15 of 25
`
`6,157,747
`
`FOR k. 1–N AND l = 1–N
`DETERMINE OVERLAPPING IMAGE PAIRS
`Ik, I FROM RK, R OR Mk, M.
`
`FOREACH OVERLAPPING MAGE PAIR
`Ik, I WARP IMAGE I BY RI-1RK
`OR MF1MK AND OVERLAYONI,
`
`FOREACH PATCH(I) IN Ik OVERLAID BY I,
`§§§ Ujkl
`
`FOREACH PATCH j, COMPUTE ANORMALIZED
`AVERGAEu?k OFuk! FOR ALLIMAGES
`OVERLAYING THE jth PATCH
`
`2010
`
`2020
`
`2030
`
`2040
`
`REVERSEEACHuk-uk -— uk
`
`2050 FOREACH
`PATCHj
`
`REVERSE MAP TO PIXEL LOCATIONS IN
`UNWARPED VERSIONS OF Ik USING-Uk
`AND INTERPOLATE THE SPARSE SET OF MOTION
`ESTIMATES-up, TO OBTAINPER=PIXELMOTION
`ESTIMATES u(x)
`
`
`
`2060
`
`RESAMPLE PIXEL VALUES AT REVERSE—MAPPED
`PIXEL LOCATIONS ACCORDING TO
`Ik(X) = Ik(x + u(x))
`
`OUTPUT RESAMPLED VERSION OF I.(X)
`
`FIG. 20
`
`
`
`2070
`
`2080
`
`Prime Focus Ex 1037-17
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 16 of 25
`
`6,157,747
`
`FIG. 21
`
`FIG. 22
`
`
`
`Prime Focus Ex 1037-18
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 17 of 25
`
`6,157,747
`
`(SOURCE
`DESTINATION PIXEL)
`PIXEL
`FIG. 25A
`
`DESTINATION
`PIXEL
`FIG. 24
`
`
`
`Prime Focus Ex 1037-19
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 18 of 25
`
`6,157,747
`
`
`
`MOTION
`ESTIMATE
`
`
`
`-
`
`SPARSE
`DATA
`|NTERPOLATION
`
`
`
`2640
`
`2650
`
`Prime Focus Ex 1037-20
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 19 of 25
`
`6,157,747
`
`Po14
`~ P111
`Poio e-Evž
`P
`
`FIG. 27
`
`P,
`
`Pooo
`
`P.
`
`
`
`P101
`
`Prime Focus Ex 1037-21
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 20 of 25
`
`6,157,747
`
`2%NS
`
`
`
`
`
`F.
`
`
`
`NNNNNNNN
`NNNNN)
`R. º SNM//
`s s s s s s N
`s
`e N s N N s e
`le
`
`<SSN/2
`
`FIG. 30
`
`N N
`
`FIG. 31
`
`Prime Focus Ex 1037-22
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 21 of 25
`
`6,157,747
`
`PAINT PSEUDOCOLORS INTO
`TEXTURE MAP TRIANGLES
`USINGAU)(ILIARY BUFFER
`
`3200
`
`FOR EVERY TRIANGLE IN 3-D MODEL
`COMPUTE Mr MAPPING ALLVEHICLES
`p|N 3-D MODELTO POINTS u
`IN 2-D TEXTURE MAP
`
`
`
`
`
`3210
`
`FOREACH IMAGE () (X)K RECALLCAMERA
`k
`MATRIX Mk MAPPING X, TO 3-D
`POINT P N 3-D MODEL
`
`3220
`
`COMPUTE IMAGE PIXELS; Xk FROM TEXTURE
`3230
`MAP PIXELSu:X - M.MF'u
`FOREACHTRIANGLEN3D MODELFIND T-3240
`EVERY POINT U INSIDE CORRESPONDING
`TRIANGLE IN TEXTURE MAP
`3250
`
`
`
`
`
`FOREVERY POINT u INSIDE OR BESIDE THE TRIANGLE,
`FIND THE CORRESPONDING PIXELX, IN
`IMAGE Ik FOR EVERY IMAGE k, 1–N AND
`COMPUTEABLENDED COLOR (SHADE) OF
`UAS AWEIGHTED SUM OF THE COLORS
`OF THE CORRESPONDING PIXELSX.
`IN THE NIMAGES I,
`colon ()–:W. Colonº-iw, color M.M.')
`PLACE COLORONTEXTUREMAP USING | *
`PSEUDOCOLOR STENCIL
`
`FIG. 32
`
`Prime Focus Ex 1037-23
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 22 of 25
`
`6,157,747
`
`
`
`Gö
`****
`
`33A
`
`FIG
`
`33B
`
`FIG.
`
`33C
`
`FIG.
`
`33D
`
`Prime Focus Ex 1037-24
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 23 of 25
`
`6,157,747
`
`
`
`
`
`FIG. 35B
`
`Prime Focus Ex 1037-25
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 24 of 25
`
`6,157,747
`
`36A
`
`
`
`Prime Focus Ex 1037-26
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`U.S. Patent
`
`Dec. 5, 2000
`
`Sheet 25 of 25
`
`6,157,747
`
`FIG 37A FIG, 37B FIG. 37C FIG, 37D
`
`
`
`FIG 38
`
`Prime Focus Ex 1037-27
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`6,157,747
`
`1
`3-DIMENSIONAL IMAGE ROTATION
`METHOD AND APPARATUS FOR
`PRODUCING IMAGE MOSAICS
`
`10
`
`15
`
`20
`
`25
`
`BACKGROUND OF THE INVENTION
`1. Technical Field
`The invention is related to computer systems for con
`structing and rendering panoramic mosaic images from a
`sequence of still images, video images or scanned photo
`graphic images or the like.
`2. Background Art
`Image-based rendering is a popular way to simulate a
`visually rich tele-presence or virtual reality experience.
`Instead of building and rendering a complete 3D model of
`the environment, a collection of images is used to render the
`scene while supporting virtual camera motion. For example,
`a single cylindrical image surrounding the viewer enables
`the user to pan and zoom inside an environment created from
`real images. More powerful image-based rendering systems
`can be built by adding a depth map to the image or by using
`a larger collection of images.
`The present invention is particularly directed to image
`based rendering systems without any depth information, i.e.,
`those which only support user panning, rotation, and zoom.
`Most of the commercial products based on this idea (such as
`QuickTime VR) use cylindrical images with a limited ver
`tical field of view, although newer systems support full
`spherical maps (e.g., Interactive Pictures, and Real VR). A
`number of techniques have been developed for capturing
`30
`panoramic images of real-world scenes. One way is to
`record an image onto a long film strip using a panoramic
`camera to directly capture a cylindrical panoramic image.
`Another way is to use a lens with a very large field of view
`such as a fisheye lens. Mirrored pyramids and parabolic
`mirrors can also be used to directly capture panoramic
`images. A less hardware-intensive method for constructing
`fill view panoramas is to take many regular photographic or
`video images in order to cover the whole viewing space.
`These images must then be aligned and composited into
`complete panoramic images using an image mosaic or
`“stitching” method. Most stitching systems require a care
`fully controlled camera motion (pure pan), and only produce
`cylindrical images.
`Cylindrical panoramas are commonly used because of
`their ease of construction. To build a cylindrical panorama,
`a sequence of images is taken by a camera mounted on a
`leveled tripod. If the camera focal length or field of view is
`known, each perspective image can be warped into cylin
`drical coordinates. To build a cylindrical panorama, 3D
`world coordinates are mapped to 2D cylindrical screen
`coordinates using
`
`35
`
`40
`
`45
`
`50
`
`where 6 is the panning angle and v is the scanline. Similarly,
`3D world coordinates can be mapped into 2D spherical
`coordinates 6,4) using
`
`6 = tan' (X/Z) and 0 = an "(Y/N X2 + Z2 )
`
`55
`
`60
`
`Once each input image has been warped, constructing the
`panoramic mosaics for a leveled camera undergoing a pure
`panning motion becomes a pure translation problem. Ideally,
`
`65
`
`2
`to build a cylindrical or spherical panorama from a horizon
`tal panning sequence, only the unknown panning angles
`need to be recovered. In practice, small vertical translations
`are needed to compensate for vertical jitter and optical twist.
`Therefore, both a horizontal translation tº and a vertical
`translation tº are estimated for each input image. To recover
`the translational motion, the incremental translation Öt=(öte,
`öt.) is estimated by minimizing the intensity error between
`two images, Io, In,
`
`i
`
`where
`
`are corresponding points in the two images, and t={t, t) is
`the global translational motion field which is the same for all
`pixels. After a first order Taylor series expansion, the above
`equation becomes
`
`i
`
`where e-I (x'1)—Io(x,) is the current intensity or color error,
`and gº=VI,(x') is the image gradient of I, at x', This
`minimization problem has a simple least-squares solution,
`
`|X. w). — -2. (eigi);
`
`To handle larger initial displacements, a hierarchical coarse
`to-fine optimization scheme is used. To reduce discontinui
`ties in intensity and color between the images being
`composited, a simple feathering process is applied in which
`the pixels in each image are weighted proportionally to their
`distance to the edge (or more precisely, their distance to the
`nearest invisible pixel). Once registration is finished, the
`ends are clipped (and optionally the top and bottom), and a
`single panoramic image is produced.
`Creating panoramas in cylindrical or spherical coordi
`nates has several limitations. First, it can only handle the
`simple case of pure panning motion. Second, even though it
`is possible to convert an image to 2D spherical or cylindrical
`coordinates for a known tilting angle, ill-sampling at north
`pole and south pole causes big registration errors. (Note that
`cylindrical coordinates become undefined as you tilt your
`camera toward north or south pole.) Third, it requires
`knowing the focal length (or equivalently, field of view).
`While focal length can be carefully calibrated in the lab,
`estimating the focal length of the lens by registering two or
`more images using conventional techniques is not very
`accurate.
`The automatic construction of large, high-resolution
`image mosaics is an active area of research in the fields of
`photogrammetry, computer vision, image processing, and
`computer graphics. Image mosaics can be used for many
`different applications. The most traditional application is the
`construction of large aerial and satellite photographs from
`collections of images. More recent applications include
`scene stabilization and change detection, video compression
`and video indexing, increasing the field of view and reso
`lution of a camera, and even simple photo editing. A
`
`Prime Focus Ex 1037-28
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`3
`particularly popular application is the emulation of tradi
`tional film-based panoramic photography with digital pan
`oramic mosaics, for applications such as the construction of
`virtual environments and virtual travel. In computer vision,
`image mosaics are part of a larger recent trend, namely the
`study of visual scene representations. The complete descrip
`tion of visual scenes and scene models often entails the
`recovery of depth or parallax information as well.
`In computer graphics, image mosaics play an important
`role in the field of image-based rendering, which aims to
`rapidly render photorealistic novel views from collections of
`real (or pre-rendered) images. For applications such as
`virtual travel and architectural walkthroughs, it is desirable
`to have complete (full view) panoramas, i.e., mosaics which
`cover the whole viewing sphere and hence allow the user to
`look in any direction. Unfortunately, most of the results to
`date have been limited to cylindrical panoramas obtained
`with cameras rotating on leveled tripods with carefully
`designed stages adjusted to minimize motion parallax. This
`has limited the users of mosaic building (“stitching”) to
`researchers and professional photographers who can afford
`such specialized equipment. Present techniques are difficult
`because generally they require special camera equipment
`which provides pure panning motion with no motion paral
`lax.
`Problems to be Solved by the Invention:
`It would be desirable for any user to be able to “paint” a
`full view panoramic mosaic with a simple hand-held camera
`or camcorder. However, this requires several problems to be
`OVer COIT le.
`First, cylindrical or spherical coordinates should be
`avoided for constructing the mosaic, since these represen
`tations introduce singularities near the poles of the viewing
`sphere.
`Second, accumulated misregistration errors need to be
`corrected, which are always present in any large image
`mosaic. For example, if one registers a sequence of images
`using pairwise alignments, there is usually a gap between the
`last image and the first one even if these two images are the
`same. A simple “gap closing” technique is introduced in the
`specification below which forces the first and last image to
`be the same and distributes the resulting corrections across
`the image sequence. Unfortunately, this approach works
`only for pure panning motions with uniform motion steps, a
`significant limitation.
`Third, any deviations from the pure parallax-free motion
`model or ideal pinhole (perspective) camera model may
`result in local misregistrations, which are visible as a loss of
`detail or multiple images (ghosting).
`SUMMARY OF THE INVENTION
`The invention claimed herein solves the problem of how
`to avoid using cylindrical or spherical coordinates for con
`structing the mosaic by associating a rotation matrix (and
`optionally a focal length) with each input image, and per
`forming registration in the input image’s coordinate system.
`Such mosaics are referred to herein as rotational mosaics.
`The system can use a postprocessing stage to project such
`mosaics onto a convenient viewing surface, i.e., to create an
`environment map represented as a texture-mapped polyhe
`dron surrounding the origin.
`The problem of accumulated misregistration errors is
`solved by a global optimization process, derived from simul
`taneous bundle block adjustment in photogrammetry, to find
`the optimal overall registration.
`The problem of loss of detail or image ghosting is solved
`by computing local motion estimates (block-based optical
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6,157,747
`
`4
`flow) between pairs of overlapping images, and using these
`estimates to warp each input image so as to reduce the
`misregistration. This is less ambitious than actually recov
`ering a perspective depth value for each pixel, but has the
`advantage of being able to simultaneously model other
`effects such as radial lens distortions and small movements
`in the image.
`The invention aligns a set of plural images to construct a
`mosaic image. Each image overlaps partially with some
`other image of the set. Typically the images are captured by
`a camera looking at the same scene but oriented at different
`angles from approximately the same location or similar
`locations. In order to align one of the images with another
`one of the images, the following steps are carried out: (a)
`determining a difference error between the one image and
`the other image; (b) computing an incremental 3
`-dimensional rotation of the one image relative to a
`3-dimensional coordinate system through an incremental
`angle which tends to reduce the difference error; and (c)
`rotating the one image in accordance with the incremental
`rotation to produce an incrementally rotated version of the
`one image. As long as the difference error remains
`significant, the method continues by re-performing the fore
`going determining, computing and rotating steps but this
`time with the incrementally rotated version of the one image.
`Preferably, the re-performing step is repeated until the
`difference error has been reduced to a desired minimum. At
`this point, a final rotation is produced representing a com
`bination of the successive incremental rotations computed in
`the foregoing repetitions of the process.
`Preferably, each image in the set of images is associated
`with a respective rotation matrix defining its respective
`orientation relative to the 3-dimensional coordinate system.
`This rotation matrix is updated by multiplying it by the
`incremental rotation with each repetition of the rotation
`computing step. Such a process is carried out for all the
`images in the set to produce a set of finally rotated (aligned)
`images from which a mosaic image may be constructed.
`Preferably, the step of determining an error produces an
`error vector between the one image and the other image at
`each pixel coordinate of the one image. The one image
`typically is defined as individual pixels relative to a pixel
`coordinate system of that image and the incremental rotation
`defines a rotated or warped version of the pixel coordinate
`system. The computing of the incremental rotation is carried
`out preferably by determining for each pixel coordinate of
`the one image a gradient, a Jacobian of the rotated version
`of the pixel coordinate system of the one image relative to
`the incremental rotation and then computing the product of
`the gradient and Jacobian.
`Preferably, the computing of the incremental rotation
`further includes multiplying the error vector by the product
`of the gradient and Jacobian to produce a residual error, and
`this is summed over all pixel coordinates to produce a
`“residual”. Also, a “Hessian” is produced by computing a
`transpose of the product of the gradient and Jacobian and
`combining the transpose with the gradient and Jacobian to
`produce a matrix, and then summing the result over all pixel
`coordinates in the one image. (“Hessian” is a term of art and
`typically refers to the outer product of two Jacobian opera
`tors and more generally to the second derivative of a
`function with respect to a vector-valued parameter.) A set of
`normal equations is then formed involving the residuals and
`Hessians. Solving normal equations with the residuals and
`Hessians produces the next optimum incremental rotation.
`The invention creates full view panoramic mosaics from
`image sequences. Unlike current panoramic stitching
`
`Prime Focus Ex 1037-29
`Prime Focus v Legend3D
`IPR2016-01243
`
`

`

`5
`methods, which usually require pure horizontal camera
`panning, our system does not require any controlled motions
`or constraints on how the images are taken (as long as there
`is no strong motion parallax). For example, images taken
`from a hand-held digital camera can be stitched seamlessly
`into panoramic mosaics.
`By taking as many images as needed, image mosaics can
`be constructed which cover as large a field of view as
`desired, e.g., a complete environment map. Because the
`image mosaics is represented in the invention using a set of
`transforms, there are no singularity problems such as those
`existing at the top and bottom of cylindrical or spherical
`maps. This method is fast and robust because it directly
`recovers 3D rotations instead of general 8 parameter planar
`perspective transforms. By mapping the mosaic onto an
`arbitrary texture-mapped polyhedron surrounding the origin,
`the virtual environment can be viewed or explored using
`standard 3D graphics viewers and hardware without requir
`ing special-purpose players. Once a mosaic has been
`constructed, it can, of course, be mapped into cylindrical or
`spherical coordinates, and displayed using a special purpose
`viewer. Such specialized representations are not necessary,
`and represent just a particular choice of geometry and
`texture coordinate embedding. Instead, using a mapping
`process described herein, the mosaic can be converted to an
`environment map, i.e., by mapping the mosaic onto any
`texture-mapped polyhedron surrounding the origin. This
`allows the use of standard 3D graphics APIs and 3D model
`formats, and allows the use of 3D graphics accelerators for
`texture mapping. The mapping process can be employed in
`a rendering process that can be just as fast as special-purpose
`viewers. Furthermore, the mapping process can take advan
`tage of 3D graphics (rendering) hardware, support multi
`resolution textures, and allow for easy integration with
`regular 3D graphics.
`BRIEF DESCRIPTION OF THE DRAWINGS
`The file of this patent contains at least one drawing
`executed in color. Copies of this patent with color
`drawing(s) will be provided by the Patent and Trademark
`Office upon request and payment of the necessary fee.
`FIG. 1 is a block diagram illustrating the operation of a
`system embodying the invention.
`FIGS. 2A and 2B is a block diagram illustrating apparatus
`embodying a system of the invention.
`FIG. 3 illustrates apparatus including a camera employed
`for the acquisition of images to form a panoramic image.
`FIG. 4 is a detailed view of a portion of the apparatus of
`FIG. 3.
`FIG. 5 illustrates a perspective warping and image.
`FIG. 6 illustrates a sequence of images obtained in an
`incremental image alignment method.
`FIG. 7 illustrates a pixel resampling problem encountered
`in the incremental image alignment method.
`FIG. 8 is a flow diagram of the incremental alignment
`method employed in the invention.
`FIG. 9 is a block diagram illustrating the sign