|||||||||||||||||||||||||||||l|||||||||||l|||||||||||||||||||||||||||||||||
`
`USI)0675I}873BI
`
`(12)
`
`United States Patent
`US 6,750,873 B1
`(10) Patent N0.:
`Bernardini et al.
`
`(45) Date of Patent: Jun. 15, 2004
`
`(54)
`
`(75)
`
`HIGH QUALITY TEXTURE
`RECONSTRUCTION FROM MULTIPLE
`SCANS
`
`Inventors: Fausto Bernardini, New York. NY
`(US); Ioana M. Martin. Mohegan
`Lake, NY (US); Holly E. Rushmeier,
`Mount Kisco, NY (US)
`
`(73)
`
`Assignee:
`
`International Business Machines
`Corporation. Armonk, NY (US)
`
`t‘)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`use 154w) by 259 days.
`
`(31)
`
`App}. No: 097603328
`
`(22
`
`Filed:
`
`Jun. 27, 2000
`
`(51)
`(52)
`
`(53)
`
`(56)
`
`Int. Cl.7
`U.S. Cl.
`
`..G06K 9700
`3451582, 3457581; 3457586;
`
`3437606 3457629, 3827294; 3823295
`Field of Search
`“3457582, 586.
`3457581,2389 (306,609, 419, 639, 629;
`3827154 108, 294. 295, 296, 298
`
`References Cited
`
`U.S. PA'I‘ENT DOCUMENTS
`
`OTHER PUBLICATIONS
`
`"Surface Reconstruction and Display from Range and Color
`Data" by Pulli. Dissertation submitted in partial fulfillment
`of the requirements for the degree of Doctor of Philosophy,
`University of Washington, 1997, pps.
`l—-ll7.
`"'lbwards a General Multi—View Registration Technique" by
`Bergevin et 31., IEEE Transactions on Pattern Analysis and
`Machine intelligence, vol. 18, No. 5, May 1996, pps.
`540—547.
`”Object Modeling by Registration of Multiple Range
`images" by Chen et al, institute for Robotics and Intelligent
`Systems, Apr. 1991, pps. 2724—2729.
`"A Method for Registration of 3—D Shapes" by Best et al.,
`lEEIE. Transactions on Pattern Analysis and Machine Intel-
`ligence, vol. 14, No. 2, Feb. 1992. pps. 239—256.
`
`{List continued on next page.)
`
`Primary Examiner—Matthew Luu
`Assistant cleanser—Daniel Chung
`(74) Attorney; Agent, or Firrrr—Ohlandl, Greeley, Ruggiero
`& Perle, L.L.1’.; Louis l’ercello
`
`(57)
`
`ABSTRACT
`
`A system and method is disclosed for constructing a digital
`model ofan object. The system includes an imaging system
`for generating object surface scan data from a plurality of
`surface scans, the surface scan data having a first resolution
`and representing the object from a plurality of vieWpoints.
`The imaging system further generates image data having a
`second, higher resolution than the surface scan data for
`representing the object from the plurality of viewpoints. The
`system further includes a data processor for iteratively
`registering the surface scan data [or the plurality 01‘ surface
`scans, using the image data. and for reconstructing substan-
`tially seamless surface texture data for the model using
`weights that reflect a level of confidence in the data at a
`plurality of surface points.
`
`25 Claims, 19 Drawing Sheets
`
`345.3530
`3457419
`364747424
`3457433
`345740)
`
`A
`171995 Ellson
`“
`5,381,526
`5,579,456 A " 1171996 Cosman
`5,715,106 A
`271998 13051 ctal.
`5,986,668 A
`1171999 Sleeliski el al.
`5,995,050
`“ 1171999 Migdaletal.
`611109.190
`1271999 Szcliski ct a1.
`6,049,636
`472000 Yang
`6,256,038 B1
`772.001 Krishnamurttiy
`6,271.84? Bl
`872001 Shumetat.
`6,362.821 Bl
`372002 Gibson c: at.
`6,469,710 Bl
`1072002 Shunt et ai.
`6,476,803 B1
`1172002 Zhang et a].
`
`i-fll-i‘lit‘
`
`AAA
`
`
`
`.
`
`............... 3457419
`
`
`
`Align Ex. 1015
`Align EX. 1015
`U.S. Patent No. 9,962,244
`U.S. Patent No. 9,962,244
`
`0001
`
`0001
`
`

`

`US 6,750,873 B1
`
`Page 2
`
`OTHER PUBLICATIONS
`
`“A Computer—Assisted Range Image Registration System
`for Nuclear Waste Cleanup” by Gagnon et al., IEEE Trans-
`actions on Instrumentation and Measurement, vol. 48, No. 3,
`Jun. 1999, pps. 758—762.
`“The Digital Michelangelo Projects: 3D Scanning of Large
`Statues“ by Levoy el al. Proc. Siggraph, 2000, pps.
`l—l4.
`"Multi—Feature Matching Algorithm for Free—Form 3D Sur-
`face Registration" by Schultz el al., Instilule for Microtech-
`nology. Neuehatel, Switzerland, 1998.
`“Building Models From Sensor Data: An Application
`Shared by the Computer vision and the Computer Graphics
`
`Community" by Gerhard Roth, Visual Information Technol-
`ogy Group, National Research Council of Canada. pps. 1—9,
`undated.
`"Computing Consistent Normals and Colors [rorn Photo-
`metric Data” by Rushmeier el al., IBM Thomas J. Watson
`Research Center, Oct. 1999.
`"Acquisition and Visualization of Colored 3D Objects" by
`Abinached el al., University of Washington, undated.
`"Texturing 3D Models of Real World Objects from Multiple
`Unregistered Photographic Views" by Nuegehauer et al.,
`Fraunhofer Institute for Computer Graphics, vol. 18, N0. 3,
`1999, pps. 245-256.
`* cited by examiner
`
`0002
`
`0002
`
`

`

`US. Patent
`
`Jun. 15, 2004
`
`Sheet 1 0f 19
`
`US 6,750,873 B1
`
`Range
`images
`
`Registration
`
`
`
`Intensity
`images
`
`-------
`
`Texture-to-geometry
`registration
`
`
`
`
`
`
`
`Integration of scans
`into a single mesh
`
`
`
`Computation of
`illumination invariants
`
`r11
`
`Surface
`
`parameterization
`
`
`
`
`
`Surface
`
`parameterization
`
`
`
`Fig. 1
`
`(Prior Art)
`
`0003
`
`0003
`
`

`

`US. Patent
`
`Jun. 15, 2004
`
`Sheet 2 0f 19
`
`US 6,750,873 B1
`
`
`
`0004
`
`0004
`
`

`

`US. Patent
`
`Jun. 15, 2004
`
`Sheet 3 0f 19
`
`US 6,750,873 B1
`
`
`
`0005
`
`0005
`
`

`

`US. Patent
`
`Jun. 15, 2004
`
` heat 4 0f 19
`
`US 6,750,873 B1
`
`
`
`
`
`0006
`
`0006
`
`

`

`US. Patent
`
`Jun. 15, 2004
`
`Sheet 5 0f 19
`
`US 6,750,873 B1
`
`Input:
`
`scans toberegistered: S:,...,SN
`initial regisu'ationmau'ices: M1,...,MN
`dctailmapsle,...,DN
`depthmaps: 21,...,ZN
`boundingboxes: B“...,BN
`, LN
`lists ofsample points: L1,” .
`where Ln = {(tmmmfltm E 13um ‘5 Sm}
`camera parameters: 0
`
`Output: accurate registration matrices: M1, .
`
`.
`
`.
`
`, MN
`
`Algorithm Image-Based Regimarion
`
`read 131,...,BN
`1.
`2. While (convergence criterion not satisfied)
`(m1, .
`. ”111”) = randompermutarion (2, .
`for (m = mh. ..,mN)
`Cm 3 camera (Mm, C)
`ragtlsterjcan (m, Cm)
`
`SI???”
`
`.
`
`.
`
`, N)
`
`Procedure register-Joan (m1 Cm)
`
`read 0",, Zm, Lm
`1.
`for (i = 1,-..,N) and (i 3% m.)
`2.
`read 8,, D,-
`3.
`if (Bm intersects Bi)
`4
`Di =pmjectjcan (3;, Di, Cm)
`5
`0,,“- = computejmageflveriap (Dm, Di)
`6.
`if (10mgl > minflverlap)
`7
`for ((tm,p,,,) e L") and (tn, E On“)
`8
`ti = t‘m
`9-
`b,- =find_best.match (tm, 0,“, a, 13,)
`10.
`p,- : backproject (In, 3;, Cm) E S,-
`11.
`insertjpair (pm, pg, pairsJisr)
`12.
`13. if (lpairslfstl 2 3)
`14.
`Mm = computeJ‘fgfdJransfonn (pairslist)
`
`Fig. 4
`
`0007
`
`0007
`
`

`

`US. Patent
`
`Jun. 15, 2004
`
`Sheet 6 0f 19
`
`US 6,750,873 B1
`
`
`
`Fig. 5A
`
`Fig. 53
`
`
`
`0008
`
`0008
`
`

`

`US. Patent
`
`Jun. 15, 2004
`
`Sheet 7 0f 19
`
`US 6,750,873 B1
`
`t-IlllIIII
`
`
`
`II
`I II
`II I I
`
`.nlnI-Illu "Ila-“II
`IIIUIIIIIIIHIIIIIIIII
`Ill-IIIIHIIHIIIIIIIII
`
`
`
`
`
`IIIIEI=:III%IIIII=III
`
`
`
`
`
`smm = Zomamz- anmtti‘nfl?
`
`sn =X5iufif-Hfoathlf
`
`smi = ZDmuLffJ-I (t?) - ~1—Z Omaha 2 5| (t? ).
`
`Fig. 7A
`
`0009
`
`0009
`
`

`

`US. Patent
`
`Jun. 15, 2004
`
`Sheet 8 0f 19
`
`US 6,750,873 B1
`
`
`
`0010
`
`0010
`
`

`

`US. Patent
`
`Jun. 15, 2004
`
`Sheet 9 0f 19
`
`US 6,750,873 B1
`
`
`
`0011
`
`0011
`
`

`

`U S. Patent
`
`Jun. 15, 2004
`
`Sheet 10 0f 19
`
`US 6,750,873 B1
`
`
`
`0012
`
`0012
`
`

`

`US. Patent
`
`Jun. 15, 2004
`
`Sheet 11 0f 19
`
`US 6,750,873 B1
`
`
`
`Fig. 10E
`
`Fig. 10F
`
`0013
`
`0013
`
`

`

`US. Patent
`
`Jun. 15, 2004
`
`Sheet 12 0f 19
`
`US 6,750,873 B1
`
`
`
`0014
`
`0014
`
`

`

`US. Patent
`
`Jun. 15,2004
`
`Sheet 13 0f19
`
`US 6,750,873 B1
`
`114
`
`
`
`110
`
`
`
`M 1
`
`00
`
`120
`
`MEMORY
`
`
`
`GRAPHICS
`
`
`SUBSYSTEM
`
`
` 118
`
`
`SUBSYSTEM
`
`l/O
`
`
`112
`
`
`
`ACQUISITION
`SUBSYSTEM
`
`Fig. 11A
`
`0015
`
`0015
`
`

`

`US. Patent
`
`Jun. 15, 2004
`
`Sheet 14 0f 19
`
`US 6,750,873 B1
`
`106
`
`1103
`
`BUS
`
`INTERFACE
`
`GRAPFHCS
`
`CONTROL
`
`PROCESSOR
`
`GEOMETRY
`
`SUBSYSTEM
`
`1109
`
`1108
`
`1101
`
`1 10"
`
`Z—BUFFER
`
`RASTERIZER
`
`FRAME
`
`BUFFER
`
`Fig. 118
`
`0016
`
`0016
`
`

`

`US. Patent
`
`Jun. 15, 2004
`
`Sheet 15 0f 19
`
`US 6,750,873 B1
`
`
`
`0017
`
`0017
`
`

`

`US. Patent
`
`M
`
`91f061tcchS
`
`US 6,750,873 B1
`
`....lm.........
`
`
`
`Rm.»................5...,
`
`'4
`
`ig. 11D
`
`n...x.umJ...2“.
`
`\F
`
`
`cur-.........un/FDAvFfldr‘bah9§AVW
`_.«m««flfi¢14m$h>4pfl¢<Auqv‘.
`wwmwflmagéwvaafinw
`xvébhfldhhaq“,
`
`Fig. 11F
`
`Fig. 11G
`
`0018
`
`0018
`
`
`
`
`

`

`US. Patent
`
`Jun. 15, 2094
`
`Sheet 17 0f 19
`
`US 6,750,873 Bl
`
`
`
`AGE-BASED REGISTRATION
`
`
`
`Read B1,
`
`
`
`
`Bn
`
`mn) as a
`Generate (m2,
`random permutation of (2,
`
`n)
`
`
`Cmi = camera (Mmi, C)
`Register Scan (mi, Cmi)
`
`
`
`
`convergence criterion
`IS satisfied
`
`Fig. 12A
`
`0019
`
`0019
`
`

`

`US. Patent
`
`Jun. 15, 2004
`
`Sheet 18 0f 19
`
`US 6,750,873 BI
`
`
`
`REGISTER SCAN (m, Cm)
`
`
`
`
`
`No
`
`
`3 pairs of points in
`the list of pairs
`
`
`
`Compute a transformation
`matrix Mm using the list of pairs
`
`
`
`
`
`Read Dm, Zm, Lm
`
`
`
`fi
`
`Yes
`
`Read Si, Di
`
`No
`
`Bm intersects Br
`
`Yes
`
`
`
`
`Project soanSi
`textured with its detail
`
`map Di using camera
`position Cm onto
`
`image D'i
`
`
`
`overtap of image
`Dm with image D‘I IS
`
`significant
`
`Yes
`
`
`
`
`
`tm, pm) is a sample pair
`Yes
`in Lm not yet processed
`
`
`_
`’
`g
`‘ AND
`
`
`trn rs msrde the overtap region
`
`
`
`Find hi, the position in D'i that constitutes
`a best match for tm in Dm
`
`
`
`
`
`Back-project bi using camera position Cm
`onto pi on the surface of scan Si
`
`insert the pair (pm. pi) into the list of pairs
`
`
`
`0020
`
`0020
`
`

`

`US. Patent
`
`Jun. 15, 2004
`
`Sheet 19 0f 19
`
`US 6,750,873 BI
`
`TEXTURE
`RECONSTRUCTION
`
`-—.=1
`
`No ®
`
`Yes
`
`Initialize accumulation buffers AcA AcN and AM
`
`Define orthogonal camera for patch P]
`
`
`
`’Compute dimensions sh sv of output maps (In pixels. " )
`
`
`
`
`
`
`
`Yes
`
`
`Load Ai, Ni, Wt. Zi into
`memory
`
`No @Yes
`
`
`
`
`
`
`
`
`
`
`
`Scan conver P1 and store xyz per pixet in point map XY
`
`
`
`1ew frustum Vi intersects
`bounding box of patch P‘
`
`Yes
`
`Ma»
`Yes
`
`0.
`
`
`
`No
`i += 1
`
`AcR i: Acw
`AcN I: AcW
`
`save AoA as albedo map A'j.
`save AcN as n rmal map N‘J
`
`
`
`
`Transform p into q = (qx, qy, qz)
`a point in the coordinate system
`of scan Si
`
`
`2 < 1 AND
`
`
`
`qz < Zi(h, v) + epsilo
`
`
`
`AcA(h, v] += Wi{qx, qy)*Ai(qx, qy .
`
`AcN(h, v) += Wi(qx,‘qy)*Ni(qxl qy}
`AcW(h. V) += Wlth. to)
`
`
`
`
`
`0021
`
`0021
`
`

`

`US 6,750,873 B1
`
`1
`HIGH QUALITY TEXTURE
`RECONSTRUCTION FROM MULTIPLE
`SCANS
`
`FIELD OF THE INVENTION
`
`This invention relates generally to methods and apparatus
`for generating displayahle digital models of physical
`objects, and in particular relates to such methods and appa-
`ratus that operate based on object surface scan and image
`data.
`
`BACKGROUND OF THE INVEN'I'ION
`
`The creation of threevdimensional digital content by scan~
`ning real objects has become common practice in graphics
`applications for which visual quality is paramount, such as
`animation, e-commerce, and virtual museums. While a sig-
`nificant amount of attention has been devoted to the problem
`of accurately capturing the geometry of scanned objects, the
`acquisition of high-quality textures is equally important, but
`not as widely studied.
`Three-dimensional scanners are used increasingly to cap
`ture digital models of objects for animation, virtual reality,
`and e-ccmmerce applications for which the central concerns
`are efficient representation for interactivity and high visual
`quality.
`Most high-end 3D scanners sample the surface of the
`target object at a very high resolution.
`I-Ience, models
`created from the scanned data are often over-tesselated, and
`require significant simplification before they can be used for
`visualization or modeling. Texture data is often acquired
`together with the geometry, however a typical system merely
`captures a collection of images containing the particular
`lighting conditions at
`the time of scanning. When these
`images are stitched together. discontinuity artifacts are usu-
`ally visible. Moreover,
`it
`is rather difficult
`to simulate
`various lighting conditions realistically, or to immerse the
`model in a new environment.
`
`A variety of techniques can be used to capture digital
`models of physical objects, including CAT scans and struc-
`ture from motion applied to video sequences. The following
`description has been restricted for convenience to techniques
`involving instruments that capture range images (in which
`each pixel value represents depth) and intensity images (in
`which each pixel is proportional
`to the incident
`light). A
`detailed summary of such methods can be found in (j. Roth,
`"Building models from sensor data:an application shared by
`the computer vision and computer graphics community”, In
`Proc. of the NATO Workshop on the Confluence of Com-
`puter Vision and Computer Graphics, 2000.
`The basic operations necessary to create a digital model
`from a series of captured images are illustrated in FIG. 1.
`After outliers are removed from the range images, they are
`in the form of individual height-field meshes. Step A is to
`align these meshes into a single global coordinate system. In
`high-end systems registration may be performed by accurate
`tracking. For instance,
`the scanner may be attached to a
`coordinate measurement machine that tracks its position and
`orientation with a high degree of accuracy. In less expensive
`systems an initial registration is found by scanning on a
`turntable. manual alignment, or approximate feature match-
`ing. The alignment
`is then refined automatically using
`techniques such as the Iterative Closest Point (ICP) algo-
`rithm of Res] and McKay.
`After registration, scans do not form a single surface, but
`interpenetrate one another. due to acquisition errors prima-
`
`it]
`
`15
`
`“
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`rily along the line-of—sight in each scan. To form a single
`surface, in step B the overlapping scans must be averaged.
`In stitchingtzippering methods this averaging is performed
`between pairs of overlapping meshes.
`ln volumetric;f
`occupancy grid methods line-of-sight errors are averaged by
`letting all scanned points contribute to a function of surface
`probability defined on a single volume grid. An advantage of
`volumetric methods is that all scans representing a surface
`point influence the final result, rather than simply a pair of
`scans.
`
`In step B the scans are integrated into a single mesh. The
`integration may be performed by zipperingfstitching, isos-
`urface extraction from volumes, or interpolating mesh algon
`rithms applied to error-corrected points.
`To use a texture map with the integrated mesh, in step C
`the surface is parameterized with respect to a 2D coordinate
`system and texture coordinates are interpolated between
`mesh vertices. A simple parameterization is to treat each
`triangle separately and to pack all of the individual texture
`maps into a larger texture image. However,
`the use of
`mip‘mapping in this case is limited since adjacent pixels in
`the texture may not correspond to adjacent points on the
`geometry. Another approach is to locate patches of geometry
`which are height lields that can be parameterized by pro-
`jecting the patch onto a plane. Stitching methods use this
`approach by simply considering sections of the scanned
`height fields as patches.
`Other methods could be built on tiling methods developed
`for multiresolution analysis or interactive texture mapping.
`Parallel to acquiring the geometry of the model, intensity
`images are captured to obtain information about the reflec—
`tance of the surface. Such images may he recorded with
`electronic or traditional cameras, or by using polychrumatic
`laser technology. In step D, these images are aligned to the
`corresponding geometry. In some cases the image acquisi-
`tion is decoupled from the geometry acquisition. The camera
`intrinsic and extrinsic parameters for the images are esti—
`mated by manual or automatic feature matching. The advan-
`tage is that acquisition modalities that cannot capture surface
`reflectance can be used for capturing geometry.
`In most cases, however, the alignment is performed by
`calibration. Geometry and intensity are captured simulta—
`neously from scanners with a measured transformation
`between sensing devices. The resolution of the intensity
`image may be the same as that of the range image or even
`higher. When the resolution is the same, texture mapping is
`unnecessary since a color can be assigned to each vertex.
`Nevertheless, such a representation is inefficient, and geo-
`metric simplification is typically performcd before the surn
`face parameterization step.
`The main benefit of obtaining intensity and range images
`simultaneously is that the intensity information can be used
`in the registration process in step A. Various approaches
`have been developed to use intensity images in registration.
`For example,
`it
`is known to use color as an additional
`coordinate in the ICP optimization. This avoids local
`minima in the solution in areas that have no geometric
`features, but have significant variations in the intensity. For
`models with pronounced geometric and intensity features.
`the method has proven to he very effective. A drawback is
`having to combine position and color data with different
`ranges and error characteristics. For subtle feature
`variations, these can cause one type of data to erroneously
`overwhelm the other.
`
`It is also known to use intensity images to avoid the
`spatial search required by ICP. Intensity and intensity gra-
`
`0022
`
`0022
`
`

`

`US 6,750,873 B1
`
`3
`client images from approximately aligned scans are trans-
`formed into a common camera View. Locations 01' corre-
`sponding points on overlapping scans are inferred based on
`the difference between intensity values at a given pixel and
`the gradient at that pixel. This method works well only if the
`spatial variation of the gradient is small relative to errors in
`the alignment of the scans.
`It is also known to present a non-lCP method for using
`intensity images to refine an initial manual alignment. In this
`approach pairs of range images are aligned manually by
`marking three points on overlapping intensity images. The
`locations of the matching points are refined by searchng
`their
`immediate neighborhoods with image cross-
`correlation. A least-squares optimization follows to deter-
`mine a general SD transformation that minimizes the dis—
`tances between the point pairs.
`Image registration
`techniques are also used for image mosaics in which only
`rotations or translations are considered.
`
`ill
`
`15
`
`so
`
`4
`perspective warping of the first image is then computed to
`match the rendered image of the second scan. For each
`corresponding pixel of the two images, under the computed
`transformation, a pair of points from the two scans is
`generated. A least-squ ares optimization is then performed to
`compute a registration matrix. The process is iterated until a
`convergence criterion is satisfied. Pulli also discusses an
`extension for multi-view registration.
`Reference may also be made to K. Pulli et a]., “Acquisi-
`tion and Visualization of Colored 3D Objects", ICI’R 1998,
`for a description of a system for scanning geometry and the
`surface color. The data is registered and a surface that
`approximates the data is constructed,
`It
`is said that
`the
`surface estimate can be fairly coarse, as the appearance of
`fine detail is recreated by view—dependent texturing of the
`surface using color images. This process uses three diflerent
`weights (directional, sampling quality and feathering) when
`averaging together the colors of compatible rays.
`Pulli et al. do not explicitly form texture images associ-
`ated with geometry, but propose a dynamic, view-dependent
`texturing algorithm which determines a subset of the origi-
`nal images taken from a view direction that is close to the
`current view, and the synthesis of new color images from the
`model geometry and input images.
`Based on the foregoing, it can be readily appreciated that
`a need exists for improved methods to construct accurate
`digital models of multi-scanned objects, in particular digital
`models that exhibit high-quality texture.
`
`OBJECTS AND ADVANTAGES OF THE
`INVENTION
`
`is a first object and advantage of this invention to
`It
`provide an improved method and apparatus for constructing
`accurate digital models that exhibit high-quality surface
`texture.
`
`It is a further object and advantage of this invention to
`provide an improved method and apparatus for constructing,
`from object scan data, an accurate digital model of the object
`that exhibits high-quality surface texture.
`
`SUMMARY OF TIIE INVENTION
`
`The foregoing and other problems are overcome and the
`objects of the invention are realized by methods and appa-
`ratus in accordance with embodiments of this invention.
`
`Disclosed herein are methods to construct accurate digital
`models of scanned objects by integrating high-quality tex-
`ture and normal maps with geometric data. These methods
`can be used with inexpensive, electronic camera-based sys-
`tems in which low-resolution range images and high-
`resolution intensity images are acquired. The resulting mod—
`els are wellnsuited for interactive rendering on the latestn
`generation graphics hardware with support
`for bump
`mapping.
`In general, bump mapping refers to encoding
`small scale geometry in an image. The large scale geometry
`contains pointers to the bump map image that are used by the
`computer graphics hardware to display both large and small
`scale geometry.
`The inventive methods provide techniques for processing
`range, albedo, and surface normal data. for image-based
`registration of scans, and for reconstructing high-quality
`textures for the output digital object.
`The scanning system used during the execution of the
`methods described herein was equipped with a high-
`resolution digital color camera that acquires intensity images
`under controlled lighting conditions. Detailed normal and
`
`After the intensity images are aligned to the geometry,
`illumination invariant maps are computed to estimate the
`surface reflectance (step E). The number of scans versus the
`number of intensity images, as well as the resolution of the
`scans compared to the resolution of the images are consid~
`ered at this stage. For a small number of scans and a large
`number of intensity images obtained under calibrated light- -
`ing conditions, a full Bidirectional Reflectance Distribution
`Function (BRDF) can be estimated.
`Ifmany scans are required to represent an object, and only
`a few high—resolution intensity images are captured per scan,
`photometric stereo techniques can be used to estimate Lam-
`bertian reflectance. Alternatively, if the range and intensity
`images have the same resolution, the geometry can be used
`to compute reflectance from a single image.
`In step F the final texture is reconstructed. The illumina—
`tion invariant maps are projected onto the integrated, param-
`etrized surfaces. The main concerns at this step are that the
`final texture is as sharp as the best input images, that seams
`between scans or height-field patches are not visible, and
`that all information available is fully exploited to maximize
`the signal-to-noise ratio.
`To maintain sharpness, a stitching approach has been
`proposed that uses a single illumination invariant map at any
`given surface point. Continuity in sharp features between
`adjoining maps is maintained by a local texture adjustment
`at texture boundaries. However, this approach requires high
`quality input maps that have no visible noise and no scan-
`to-scan chromatic differences. Map adjustment techniques
`such as this, as well as de-ghosting methods for image
`mosaics, decouple texture from geometric variations. This
`may cause noticeable artifacts when these variations are
`correlated (e.g., dents and scratches that reveal underlying
`material with different reflectance properties.)
`To avoid jumps in color appearance and to reduce noise,
`it is known to combine information from multiple overlap-
`ping scans. In this case, however, if texture alignment is
`imperfect then blurring or ghosting artifacts may be gener-
`ated.
`
`35
`
`40
`
`45
`
`50
`
`55
`
`Reference can be had to K. Pulli, "Surface reconstruction
`and display from range and color data”, PhD Thesis, Dept.
`ofComputer Science and Engineering, Univ. of Washington,
`December 1997.
`
`In general, this approach uses intensity images to pair
`points from overlapping scans. With the assumption that two
`scans are already roughly aligned, Pulli’s method starts by
`rendering the second scan, textured with its own intensity
`image, from the viewpoint of the first
`image. A planar
`
`60
`
`65
`
`0023
`
`0023
`
`

`

`US 6,750,873 B1
`
`5
`albedo maps of the surface are computed based on these
`images. By comparison, geometry is captured at
`lower
`resolution.
`typically at a resolution that
`is sufficient
`to
`resolve only the major shape features.
`The benefits of such a system are twofold. First, it allows
`for the use of relatively inexpensive hardware by eliminating
`the nee d for dense geometric sampling, and by taking
`advantage of digital color cameras that are quickly gaining
`In resolution while dropping In price. Second, the generated
`models are more readily usable in a visualization or mod-
`eling environment that exploits the hardware-assisted bump
`mapping feature increasingly available in commercial-grade
`BD accelerators.
`
`the issue of acquiring and reconstructing
`In general,
`high-quaiity texture maps has received less attention than
`the issue of capturing high-quality geometry. The inventors
`have built upon existing techniques developed for texture
`acquisition, reconstmction, and image registration to gener-
`ate maps of high visual quality for the scanned objects.
`Particularly because the noise and inaccuracies of a lower-
`cost scanner are greater than those of high-end. more expen—
`sive systems,
`it
`is desirable to exploit
`in full all of the
`geometric and image information acquired to improve the
`visual quality of the final representation.
`A novel
`texture reconstruction framework is disclosed
`that uses illumination-invariant albedo and normal maps
`derived from calibration-registered range and intensity
`images. The albedo maps are used in a unique way to refine
`a geometry-only registration of the individual rangc images.
`After the range data is integrated into a single mesh, the
`resulting object
`is partitioned into a set of height—field
`patches. New textures are synthesized by projecting the
`maps onto the patches and combining the best data available
`at each point using weights that reflect the level of confi—
`dence in the data. The weighted averaging lowers noise
`present
`in the images, while the fine registration avoids
`blurring, ghosting, and loss of fine texture details.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The above set forth and other features of the invention are
`made more apparent in the ensuing Detailed Description of
`the Invention when read in conjunction with the attached
`Drawings, wherein:
`FIG. 1 is flow diagram depicting the basic operations
`necessary to create a digital model from a series ofcaptured
`images;
`FIG. 2 is an example of the visual quality of textures for
`a model of a statue, obtained from multiple overlapping
`scans, that are enhanced with image-based tine-registration
`and weighted averaging techniques in accordance with the
`teachings herein;
`FIG. 3, shown as FIGS. 3A, SB and 3C, provides a
`pictorial representation of the presently preferred image-
`based registration algorithm;
`FIG. 4 depicts a pseudocode representation of the image-
`based registration algorithm in accordance with the teach-
`ings herein;
`FIGS. 5A and SB depict a sample point selection tech-
`nique based on an edge-detection technique;
`FIG. 6 illustrates two contrasting occlusion situations;
`FIG. 7 illustrates an example of a presently preferred
`sliding-window cross-correlation approach for a point that
`maximizes cross-correlation between image neighborhoods;
`FIG. 7A shows equations used in the computation of a
`correlation coefficient of n data points;
`
`it]
`
`IS
`
`an
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`FIG. 8A illustrates a two-dimensional diagram of texture
`remapping, while FIG. SB shUWs an example of an occlu-
`sion;
`FIGS. 9A—9C are representations of photographs, and are
`useful in gaining an understanding the statue model example
`employed in the description;
`FIGS. lOA—IOE are examples of a vase data set example,
`while FIGS.
`lflF—lOI are examples of the statue data set;
`FIG. 11A is a block diagram of a computer system with
`graphics and 3D data acquisition capabilities that is suitable
`for practicing this invention;
`FIG. 1113 shows the graphics subsystem in greater detail;
`FIG. 11C depicts the 3D data acquisition system in greater
`detail;
`FIG. 11D is an example of the operation of the 3D
`scanner;
`
`FIG. 1113. shows the result of acquiring multiple stripes;
`FIG. 11F shows, in the scan integration phase, the com-
`putation of a triangular mesh;
`FIG. 110 shows a closeup view of the computed lrian~
`gular mesh;
`FIG. 12A is a logic flow diagram of the image~based
`registration method in accordance with this invention, while
`FIG. 123 is a logic flow diagram of the register scan(m)
`procedure of FIG. 12A; and
`FIG. 13 is a logic flow diagram of a presently preferred
`texture reconstruction method.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`FIG. 2 is an example of the visual quality of textures for
`a model of a statue, obtained from multiple overlapping
`scans, that are enhanced with image—based fine—registration
`and weighted averaging techniques in accordance with the
`teachings herein. The top image shows the final
`texture
`reconstructed from 20 overlapping scans. The two smaller
`images illustrate a detail from a highly carved area of the
`hair before (left) and after (right) image-based registration.
`The line chisel marks become clearly visible after the
`registration.
`A description is now provided of presently preferred
`methods to realize the steps shown in FIG. I. The goal is to
`produce a model of high visual quality, rather than to acquire
`a dense geometric representation. In accordance with these
`teachings novel techniques are disclosed [or the registration
`and reconstruction steps, respectively.
`Beginning with scan acquisition and processing, a scan—
`ning system is used in which range and intensity images are
`obtained simultaneously and are registered via a priori
`calibration. The presently preferred scanner is a hybrid
`multi-viewr’photometric system built around the Visual
`Interface Virtuoso. Range images are captured by a multi—
`camera stereo system which projects a striped pattern onto
`the target object. The system produces range images that are
`converted to individual
`triangle meshes (scans) with an
`approximate intersample distance of2 mm and submillime-
`ter depth accuracy.
`Intensity images are recorded under five calibrated light—
`ing conditions (see light sources 112ar in FIG. 11C) and have
`a much higher resolution than the projected light geometric
`scans (between about 0.25 mm and 0.5 mm intersample
`distance, depending on surface orientation.)
`The intensity images are processed to extract RGB
`albedo, normal, and weight (confidence) maps for each scan.
`
`0024
`
`0024
`
`

`

`US 6,750,873 B1
`
`7
`This photometric processing involves toting the approximate
`knowledge of the underlying geometry to account for imper-
`fections in the measuring system, as well as global com-
`pensation of variations in camera response.
`The images that contain the RGB albedo and normals are
`referred to generically as “texture maps". Holes mayr occur
`in these textures where photometric processing fails due to
`fewer than three light sources being visible at a point. In
`Such regions, the textures are filled using the normals of the
`underlying mesh and data from just one or two of the
`associated intensity images.
`A “weight map" encodes a degree of confidence in the
`data at each pixel of a texture map. The weight is propor-
`tional to the ratio of the projected surface area to the true
`area of the surface represented by the pixel. This ratio is
`computed based on the distance from the corresponding
`point on the surface to the camera 112!) center and the scalar
`product between the surface normal and the view direction.
`The weight is higher at pixels computed from the photo-
`metric data rather than based on underlying geometry. In
`addition, the weight of a pixel decreases as the distance to
`the scan boundary becomes smaller.
`The boundaries between photometric values and under—
`lying values are preferably smooth, as are the corresponding
`weights, so that abrupt changes in the final texture are not
`visible.
`
`The acquisition of intensity images aligned with the
`corresponding range images and the photometric processing
`correspond to steps D and E in FIG. 1.
`Next,
`the scan registration step A is initiated with a
`pairwise manual alignment to estimate the position of each
`scan with respect to a global coordinate system. This step is
`performed at the same time as the removal of outliers in the
`range data.
`Then,
`the initial manual registration is refined using a
`variation of the multiview lCP algorithm. The presently
`preferred variation of the multiview ICP algorithm uses
`geometric information only.
`It
`is desired to produce high-quality texture maps by
`combining information from multiple overlapping scans at
`each pixel. To achieve this, a highly accurate alignment is
`required to prevent the appearance of ghosting and blurring
`artifacts. This is accomplished, in accordance with an aspect
`of this invention. by avoiding the mixin