00000000080084000000
`
`United States Patent
`US 6,750,873 Bl
`(10) Patent No.:
`(12)
`
`(45) Date of Patent: Jun. 15, 2004
`Bernardini et al.
`
`“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. 1-117.
`“Towards a General Multi-View Registration Technique” by
`Bergevin et al., 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 Chenet al., Institute for Robotics and Intelligent
`Systems, Apr. 1991, pps. 2724-2729.
`(*)
`Notice:—Subject to any disclaimer, the term of this
`“A Method for Registration of 3-D Shapes” by Beslet al.,
`patent is extended or adjusted under 35
`IEEE Transactions on Pattern Analysis and Machine Intel-
`US.C. 154(b) by 259 days.
`ligence, vol. 14, No. 2, Feb. 1992, pps. 239-256.
`
`(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)
`
`(21)
`
`Appl. No.: 09/603,928
`
`(22
`
`Filed:
`
`Jun. 27, 2000
`
`(51)
`(52)
`
`(58)
`
`(56)
`
`MntCIS) excuses
`sie
`.. GO6K 9/00
`U.S. Che ccncse
`“4 ., 345/582; 345/581; 345/586;
`
`"345/606; 345/629; 382/294; 382/295
`Field of Search .
`Wi
`.. 345/582, 586,
`345/581,589, 606,609, 419, 639, 629;
`382/154, 108, 294, 295, 296, 298
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`OTHER PUBLICATIONS
`
`(List continued on next page.)
`
`Primary Examiner—Matthew Luu
`Assistant Examiner—Daniel Chung
`(74) Attorney, Agent, or Firm—Ohlandt, Greeley, Ruggiero
`& Perle, L.L.P.; Louis Percello
`
`(57)
`
`ABSTRACT
`
`Asystem and method is disclosed for constructing a digital
`model of an 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 fromthe plurality of viewpoints. The
`system further includes a data processor for iteratively
`registering the surface scan data for the plurality of 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
`
`A
`T/1995 ELSON wo. 343/530
`*
`5,381,526
`5,579,456 A * 11/1996 Cosman.....
`5,715,166 A
`2/1998 Besl et al.
`.....
`5,986,668
`11/1999 Szeliski et al.
`5,995,650
`* 11/1999 Migdal et al.
`6,009,190
`12/1999 Szeliski et al.
`6,049,636 A *
`4/2000 Yang «eee
`6,256,038 Bl
`*
`7/2001 Krishnamurthy
`6,271,847 Bl
`*
`8/2001 Shumetal. ...
`6,362,821 Bl
`*
`3/2002 Gibsonet al.
`.
`6,469,710 Bl
`* 10/2002 Shumetal. ...
`6,476,803 Bl
`* 11/2002 Zhang et al. oo... 345/419
`
`...
`....
`
`364/474.24
`wee 345/433
`345/419
`
` wee 345/419
`
`AAA
`
`
`
`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 et al. Proc. Siggraph, 2000, pps. 1-14.
`“Multi-Feature Matching Algorithm for Free—Form 3D Sur-
`face Registration” by Schultz et al., Institute for Microtech-
`nology, Neuchatel, 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 from Photo-
`metric Data” by Rushmeieret al., IBM Thomas J. Watson
`Research Center, Oct. 1999,
`“Acquisition and Visualization of Colored 3D Objects” by
`Abi-Rachedet al., University of Washington, undated.
`“Texturing 3D Models of Real World Objects from Multiple
`Unregistered Photographic Views” by Nuegebauer et al.,
`Fraunhofer Institute for Computer Graphics, vol. 18, No. 3,
`1999, pps. 245-256.
`* cited by examiner
`
`0002
`
`0002
`
`

`

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

`

`U.S. Patent
`
`Jun. 15, 2004
`
`Sheet 2 of 19
`
`
`
`US 6,750,873 B1
`
`0004
`
`0004
`
`

`

`U.S. Patent
`
`Jun. 15, 2004
`
`US 6,750,873 B1
`
`Sheet 3 of 19
`
`0005
`
`0005
`
`

`

`U.S. Patent
`
` heet 4 of 19
`
`Jun. 15, 2004
`
`US 6,750,873 B1
`
`
`
`0006
`
`0006
`
`

`

`U.S. Patent
`
`Jun. 15, 2004
`
`Sheet 5 of 19
`
`US 6,750,873 B1
`
`Input:
`
`scans to be registered: S,,..., Sy
`initial registration matrices: M,,..., Mn
`detail maps: D,,...,Dn
`depth maps: Z,...,Zy
`bounding boxes: B,,...,By
`lists of sample points: L,,..., Ly
`where Ly, = {(tm:Pm)ltm € Das Pm € Sm}
`camera parameters: C
`
`Output: accurate registration matrices: M,,..., My
`
`Algorithm Image-Based Registration
`
`read B,,...,By
`1.
`2. while (convergence criterion notsatisfied)
`3.
`(m,,...,™Mn) = random_permutation (2,...,.N)
`4
`for (m = m,...,my)
`5:
`Cm = camera (Mn, C)
`register_scan (m, Cm)
`6
`
`Procedure register_scan (m, Cm)
`
`1.
`2.
`
`OKONAARY
`
`read Dy, Zm, Lm
`for (t =1,...,N) and (i 4 m)
`read S;, D;
`if (B,, intersects B;)
`D. = project_scan (Si, D3; Cm)
`Omi = compute_image_overlap (Dm, D;)
`if (|Ojn;| > min_overlap)
`for ((tm:Pm) € Lm) and (tm € Om)
`ti = tn
`b; =find_best_match (tm, Dm, t:, Di)
`10.
`pi = back_project (b;,S;,Cm) € Si
`11.
`insert_pair (pm, pi, pairstist)
`12.
`13. if (\pairs_tist| > 3)
`14. My = compute_rigidtransform (pairs list)
`
`Fig. 4
`
`0007
`
`0007
`
`

`

`U.S. Patent
`
`Jun. 15, 2004
`
`Sheet 6 of 19
`
`US 6,750,873 B1
`
`
`
`Fig. 5A
`
`Fig. 5B
`
`
`
`Fig. 6
`
`0008
`
`0008
`
`

`

`U.S. Patent
`
`Jun. 15, 2004
`
`Sheet 7 of 19
`
`US 6,750,873 B1
`
`
`
`
`
`
`
`HERECEEooPt
`iV tt
`i|
`ptt|
`
`Smi = LDm(tin)Dy (ty)- +2Daltm) 2D; (ti),
`
`si aren)};
`
`wit? 2Dalim Y= 4 (2Det?
`
`Fig. 7A
`
`0009
`
`0009
`
`

`

`U.S. Patent
`
`Jun. 15, 2004
`
`Sheet 8 of 19
`
`US 6,750,873 B1
`
`ie hs, aj
`
`A PS ak
`
`At
`
`
`
`0010
`
`0010
`
`

`

`U.S. Patent
`
`Jun. 15, 2004
`
`Sheet 9 of 19
`
`US 6,750,873 B1
`
`
`
`0011
`
`0011
`
`

`

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

`

`U.S. Patent
`
`Jun. 15, 2004
`
`Sheet 11 of 19
`
`US 6,750,873 B1
`
`
`
`Fig. 10£
`
`Fig. 10F
`
`0013
`
`0013
`
`

`

`U.S. Patent
`
`Jun. 15, 2004
`
`Sheet 12 of 19
`
`US 6,750,873 B1
`
`0014
`
`0014
`
`

`

`U.S. Patent
`
`Jun. 15,2004
`
`Sheet 13 of 19
`
`US 6,750,873 B1
`
`114
`
`MEMORY 100
`
`Fig. 11A
`
`0015
`
`0015
`
`

`

`BUFFER
`
`106
`
`GRAPHICS
`CONTROL
`PROCESSOR
`
`Z-BUFFER
`
`FRAME
`
`U.S. Patent
`
`Jun. 15,2004
`
`Sheet 14 of 19
`
`US 6,750,873 B1
`
`BUS
`INTERFACE
`
`GEOMETRY
`
`SUBSYSTEM
`
`RASTERIZER
`
`Fig. 11B
`
`0016
`
`0016
`
`

`

`U.S. Patent
`
`Jun. 15, 2004
`
`Sheet 15 of 19
`
`US 6,750,873 B1
`
`
`
`0017
`
`0017
`
`

`

`U.S. Patent
`
`Jun. 15, 2004
`
`Sheet 16 of 19
`
`US 6,750,873 Bl
`
`Fig. 11D
`
`Fig. 11E
`
`SSATAVAIIND0
` ERO
`
`oyGa
`
`Fig. 11F
`
`Fig. 11G
`
`0018
`
`0018
`
`
`
`

`

`U.S. Patent
`
`Jun. 15, 2004
`
`Sheet 17 of 19
`
`US 6,750,873 B1
`
`
`
`
`
`AGE-BASED REGISTRATION
`
`Read B1, ..., Bn
`
`
`
`
`Generate (m2, ..., mn) as a
`random permutation of(2, ..., n)
`
`
`Cmi = camera (Mmi, C)
`Register Scan (mi, Cmi)
`
`
`
`
`convergencecriterion
`is Satisfied
`
`Fig. 12A
`
`0019
`
`0019
`
`

`

`U.S. Patent
`
`Jun. 15, 2004
`
`Sheet 18 of 19
`
`US 6,750,873 B1
`
`REGISTER SCAN(m, Cm)
`
`
`
`
`Read Dm, Zm, Lm
`
`
`
`
`
`
`
`
`Yes
`oe
`Raat
`
`No
`
`;
`Bm intersects B!
`
`Yes
`
`
`here are atleas
`
`pairs of points in
`thelist ofpairs.
`
`
`
`;
`Compute a transformation
`matrix Mm usingthelist of pairs
`
`
`
`
`
`Project scanSi
`textured withits detail
`
`
`
`map Di using camera
`position Cm onto
`
`
`
`image D'i
`
`
`
`overlap of image
`
`Dm with image D' is
`
`significant
`
`
`
`Find bi, the position in D'i that constitutes
`(tm, pm) is a sample pair
`
`inLm nhyet processed
`Yes
`a best match for tm in Dm
`
`
`
`tm is inside the overlap region
`
`Back-project bi using camera position Cm
`onto pi on the surface of scanSi
`
`
`
`Insert the pair (pm,pi) into the list of pairs
`
`Yes
`
`it= 4
`
`Fig. 12B
`
`0020
`
`0020
`
`

`

`U.S. Patent
`
`Jun. 15, 2004
`
`Sheet 19 of 19
`
`US 6,750,873 B1
`
`TEXTURE
`RECONSTRUCTION
`
`Yes
`
`No
`
`Yes
`
`Load Ai, Ni, Wi, Zi into
`memory
`
`Initialize accumulation buffers AcA, AcN, and AcW
`
`Define orthogonal camera for patch Pj
`
`No <<sy>
`Compute dimensionssh, sv of output maps(in pixels)
`Scan converPj and store xyz perpixelin point map XY.
`
`Yes
`
`aa
`
`iew frustum Vi intersects
`bounding boxofpatch Pj
`
`Yes
`
`
`
` Nhe
`
`
`
`
`
`
`
`
`No
`
`AcR /= AcW
`AcN /= AcW
`
`save AcA as albedo map Ajj
`save AcN as normal map Nj
`
`Transform p into q = (qx,qy, qz)
`a pointin the coordinate system
`of scan Si
`
`
`
`
`
`
`qz< 1 AND
`qz < Zi(h, v) + epsilo
`
`
`
`AcA(h, v) += Wi(gx, qy)*Ai(qx, ay)
`AcN(h,v) += Wi(gx, ay)*Ni(qx, ay)
`AcW(h,v) += Wi(qx, gy)
`
`
`
`+= {
`
`
`
`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 displayable 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 INVENTION
`
`The creation of three-dimensional 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 ofattention 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-commerce 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. Hence, 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 CATscans and struc-
`ture from motion applied to video sequences. The following
`description hasbeenrestricted 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 G. 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 meshesinto a single global coordinate system. In
`high-end systemsregistration may be performed by accurate
`tracking. For instance,
`the scanner may be attached to a
`coordinate measurement machine thattracks 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 Besl and McKay.
`After registration, scans do not form a single surface, but
`interpenetrate one another, due to acquisition errors prima-
`
`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 stitching/zippering methods this averaging is performed
`between pairs of overlapping meshes.
`In volumetric/
`occupancy grid methodsline-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 zippering/stitching, isos-
`urface extraction from volumes,or interpolating mesh algo-
`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 tn
`the texture may not correspond to adjacent points on the
`geometry. Another approachis to locate patches of geometry
`which are height fields 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 be recorded with
`electronic or traditional cameras, or by using polychromatic
`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 performed before the sur-
`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 be very effective. A drawbackis
`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
`dient images from approximately aligned scans are trans-
`formed into a common camera view. Locations ofcorre-
`sponding points on overlapping scans are inferred based on
`the difference between intensity values al a given pixel and
`the gradient at that pixel. This method works well onlyif 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-ICP method for using
`intensity imagesto 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 searching
`their
`immediate neighborhoods with image cross-
`correlation. A least-squares optimization follows to deter-
`mine a general 3D 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.
`
`After the intensity images are aligned to the geometry,
`illumination invariant maps are computed to estimate the
`surface reflectance (step E). The numberof 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 ofscans anda large
`number ofintensity images obtained under calibrated light-
`ing conditions, a full Bidirectional Reflectance Distribution
`Function (BRDF) can be estimated.
`If many scansare 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 concernsat 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 usesa single illumination invariant mapat 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 novisible 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 jumpsin color appearance andto 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.
`
`Reference can be had to K. Pulli, “Surface reconstruction
`and display from range and color data”, PhD Thesis, Dept.
`of Computer 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
`
`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-squares 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 madeto K. Pulli et al., “Acquisi-
`tion and Visualization of Colored 3D Objects”, ICPR 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 different
`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 ofthis 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 THE INVENTION
`
`15
`
`30
`
`35
`
`40
`
`45
`
`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.
`
`50
`
`55
`
`60
`
`65
`
`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 well-suited for interactive rendering on the latest-
`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 imagethat 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
`
`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
`3D accelerators.
`
`the issue of acquiring and reconstructing
`In general,
`high-quality 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, reconstruction, and imageregistration 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 mapsare used in a unique way torefine
`a geometry-only registration of the individual range 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 combiningthe 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 andotherfeatures ofthe 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 tocreate a digital model from a series of captured
`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 fine-registration
`and weighted averaging techniques in accordance with the
`teachings herein;
`FIG. 3, shown as FIGS. 3A, 3B and 3C, provides a
`pictorial representation of the presently preferred image-
`based registration algorithm;
`FIG. 4 depicts a pseudocode representation ofthe image-
`based registration algorithm in accordance with the teach-
`ings herein;
`FIGS. 5A and 5B 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;
`
`15
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`FIG. 8Aillustrates a two-dimensional diagram of texture
`remapping, while FIG. 8B shows an example ofan occlu-
`sion;
`FIGS. 9A-9C are representations of photographs, and are
`useful in gaining an understandingthe statue model example
`employed in the description;
`FIGS. LOA-10E are examples of a vase data set example,
`while FIGS. 10F—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. 11B showsthe 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. 11E shows the result of acquiring multiple stripes;
`FIG. 11F shows, in the scan integration phase, the com-
`putation of a triangular mesh;
`FIG, 1G showsa closeup view of the computed trian-
`gular mesh;
`FIG, 12A is a logic flow diagram of the image-based
`registration method in accordance with this invention, while
`FIG. 12B 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-basedfine-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 fine chisel marks become clearly visible after the
`registration.
`A description is now provided of presently preferred
`methodsto realize the steps shown in FIG. 1. 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 for 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-view/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 of 2 mm and submillime-
`ter depth accuracy.
`Intensity images are recorded under five calibrated light-
`ing conditions (see light sources 112a@in FIG. 11C) and have
`a much higher resolution than the projectedlight 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) mapsfor each scan.
`
`0024
`
`0024
`
`

`

`US 6,750,873 B1
`
`7
`This photometric processing involves using the approximate
`knowledge of the underlying geometry to accountfor 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 may 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 ofthe
`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 cach 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 1126 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
`correspondto 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. Thisstep is
`performedat the same time as the removal of outliers in the
`range data.
`Then,
`the initial manual registration ts refined using a
`variation of the multiview ICP 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 mixing of position and
`color data by performing an image-based alignmentafter the
`geometry-based registration has converged.
`In a mannersimilar to a known approach (E. Gagnon,J.-F.
`Rivest, M. Greenspan, and N. Burtnyk, “A computer-
`assisted range image registration system for nuclear waste
`cleanup”,
`IEEE Transactions of Instrumentations and
`Measurement, 48)3):758-762, 1999),
`image matching is
`used to refine the alignment. However, the presently pre-
`ferred embodimentdiffers in a number of critical ways from
`known approaches.