Object modeling system and process employing noise elimination and robust surface extraction techniques

• US 6,476,803 B1
• Filed: 01/06/2000
• Issued: 11/05/2002
• Est. Priority Date: 01/06/2000
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Loop, Charles, Zhang, Zhengyou, Shan, Ying
• Primary Examiner(s): Vo, Cliff N.
• Application Number:
  US09/479,408
• Time in Patent Office: 1,034 Days
• Field of Search: 345/418, 345/419, 345/420, 345/423, 345/424, 345/426, 345/427, 345/428, 345/581, 345/582, 345/583
• US Class Current: 345/419
• CPC Class Codes: G06T 15/00 3D [Three Dimensional] image rendering
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• CPC Class Codes: G06T 2200/08 involving all processing steps from image acquisition to 3D model generation

Abstract

A system and process for computer modeling of an object involving first capturing images of the object that collectively depict all the object'"'"'s surfaces which are to be modeled. A series of 3D reconstructions are then derived from the images. Each of the reconstructions represent a portion of the object'"'"'s surfaces. Noise elimination techniques are employed to reduce the number of extraneous reconstruction points. The individual 3D reconstructions are then registered to a common coordinate system to produce an overall 3D reconstruction of the object'"'"'s surfaces. A surface representation of the object is extracted from the overall 3D reconstruction using robust surface extraction techniques, and if desired, a texture map for the surface representation of the object can be computed using the previously captured images to produce a photorealistic model of the object.

Claims

1. A computer-implemented process for modeling an object, comprising the actions of:

capturing images of the object that collectively depict all the object'"'"'s surfaces which are to be modeled;

deriving a 3D reconstruction of a portion of the object'"'"'s surfaces from each of a plurality of sets of one or more of the images, said 3D reconstructions comprising a plurality of point locations corresponding to points on the object'"'"'s surfaces;

registering each 3D reconstruction to a common coordinate system to produce an overall 3D reconstruction of the object'"'"'s surfaces;

extracting a surface representation of the object from the overall 3D reconstruction; and

creating a texture map for the surface representation of the object using the previously captured images of the object.

2. The process of claim 1, further comprising performing a noise reduction procedure prior to performing the action of registering the 3D reconstructions, said noise reduction comprising, for each 3D reconstruction, the actions of:

(a) calculating a mean distance of the points making up a 3D reconstruction, from the origin of a 3D coordinate system associated with a camera used to capture the images employed in computing the reconstruction, in each of the three orthogonal directions;

(b) calculating a variance of the points making up the 3D reconstruction in each of the orthogonal directions based on the mean computed for the respective direction;

(c) eliminating points existing outside a region that extends the same distance both ways from the computed mean in each orthogonal direction to a total distance that is a prescribed multiple of the computed variance for that direction;

(d) repeating process actions (a) through (c);

(e) determining if the newly computed mean and variance in each orthogonal direction has changed more than a prescribed limit for each when compared to the corresponding mean and variance computed during the preceding iteration;

(f) repeating process actions (a) through (c), and (e), whenever the newly computed mean and variance in any orthogonal direction has changed more than the prescribed limits for that direction when compared to the corresponding mean and variance computed during the preceding iteration.

3. The process of claim 1, further comprising performing a noise reduction procedure prior to performing the action of registering the 3D reconstructions, said noise reduction comprising, for each 3D reconstruction, the actions of:

dividing a 3D space containing all the reconstruction points associated with a 3D reconstruction into voxels;

ascertaining which voxels contain at least one reconstruction point; and

for each reconstruction point,

identifying the voxel containing the reconstruction point,

identifying a prescribed number of voxels neighboring the previously identified voxel,

counting the number of reconstruction points contained within all the identified voxels,

determining whether the number of points counted exceeds a prescribed limit, and

eliminating the reconstruction point from the 3D reconstruction whenever the number of points counted does not exceed the prescribed limit.

4. The process of claim 1, wherein the process action of extracting a surface representation of the object from the overall 3D reconstruction, comprises the actions of:

dividing a 3D space containing all the reconstruction points associated with the overall 3D reconstruction into voxels;

ascertaining which voxels contain at least one reconstruction point;

for each voxel containing at least one reconstruction point,

identifying a prescribed number of voxels neighboring the voxel,

computing a plane that best fits the reconstruction points contained within the voxel and the identified neighboring voxels to define a plane representing the surface of the object being modeled in the voxel; and

extracting a triangular-mesh representation of the surface of the object being modeled based on the planes defined for each voxel containing reconstruction points.

5. The process of claim 4, wherein the process action of computing a plane that best fits the reconstruction points contained within a voxel and its neighboring voxels, comprises the actions of:

computing the centroid of the reconstruction points contained within the voxel and its previously identified neighboring voxels;

computing a covariance matrix for the reconstruction points contained within the voxel and its previously identified neighboring voxels based on the centroid;

identifying an eigenvector corresponding to the smallest eigenvalue found in the covariance matrix and designating the identified eigenvector as the vector of a normal of the plane that best fits the reconstruction points contained within the voxel and its previously identified neighboring voxels, wherein the normal vector is initially designated without specifying which of two possible directions the normal is directed; and

computing the distance from the plane to a prescribed one of the vertices of the voxel along said normal vector of the plane to establish the magnitude of the normal vector; and

,

determining which of the two possible directions the normal vector is directed, if feasible, and assigning that direction to the vector.

6. The process of claim 5, wherein the process action of assigning the direction to the normal vector, comprises the action of:

assigning a positive sign to the normal vector if it is directed toward the prescribed vertex of the voxel; and

assigning a negative sign to the normal vector if it is directed away from the prescribed vertex of the voxel.

7. The process of claim 5, wherein the process action of determining which of the two possible directions the normal vector is directed and assigning that direction to the normal vector, comprises the actions of:

identifying a direction vector from each point in the voxel, and each point in each of the previously identified neighboring voxels associated with the voxel, to the optical center associated with the camera used to capture the original image from which the point was derived, said direction vector hereinafter being referred to as a visibility vector;

for the voxel and each of its associated neighboring voxels, respectively determining the angle between the normal vector of each voxel and the visibility vector associated with each point contained in that voxel;

ascertaining whether a majority of the angles are one of (i) less than 90 degrees by a prescribed threshold amount, (ii) more than 90 degrees by the prescribed threshold amount, or (iii) within the prescribed threshold amount of 90 degrees;

assigning a positive sign to the normal vector to indicate that it is directed toward the prescribed vertex of the voxel whenever a majority of the angles are less than 90 degrees by the prescribed threshold amount;

assigning a negative sign to the normal vector to indicate that it is directed away from the prescribed vertex of the voxel whenever a majority of the angles are more than 90 degrees by the prescribed threshold amount;

assigning an undetermined direction status to the normal vector whenever a majority of the angles are within the prescribed threshold amount of 90 degrees.

8. The process of claim 5, wherein the process action of determining which of the two possible directions the normal vector is directed and assigning that direction to the normal vector, further comprises the actions of:

(a) selecting a previously unselected voxel having a normal vector with an undetermined direction status and designating it the currently selected voxel;

(b) identifying which directly adjacent neighboring voxel produces the largest absolute value for the cross product of the normal vector associated with the currently selected voxel and the normal vector associated with the neighboring voxel;

(c) ascertaining whether the neighboring voxel identified as having said largest cross product value has been assigned a direction,

(d) applying the direction assigned to the neighboring voxel identified as having said largest cross product value to the normal vector associated with the currently selected voxel and proceeding to process action (I), whenever said neighboring voxel'"'"'s normal vector has been assigned a direction, and otherwise,

(e) designating the neighboring voxel identified as having said largest cross product value to the normal vector associated with the currently selected voxel, as the currently selected voxel in lieu of the previously selected voxel, whenever said neighboring voxel'"'"'s normal vector has not been assigned a direction;

(f) identifying which directly adjacent neighboring voxel produces the largest absolute value for the cross product of the normal vector associated with the currently selected voxel and the normal vector associated with the neighboring voxel;

(g) ascertaining whether the neighboring voxel identified as having said largest cross product value has been assigned a direction,

(h) applying the direction assigned to the neighboring voxel identified as having said largest cross product value to the normal vector associated with the currently selected voxel and any previously selected voxels still having an undetermined direction status, and then proceeding to process action (I), whenever said neighboring voxel'"'"'s normal vector has been assigned a direction; and

otherwise,

(i) designating the neighboring voxel identified as having said largest cross product value to the normal vector associated with the currently selected voxel, as the currently selected voxel in lieu of the previously selected voxel, whenever said neighboring voxel'"'"'s normal vector has not been assigned a direction, as long as a prescribed propagation limit pertaining to the number voxels that have been designated as a currently selected voxel in a current iteration has not been exceeded;

(j) continuing the current iteration by repeating process actions (f) through (h) or (i), whenever the currently selected voxel'"'"'s normal vector has not been assigned a direction and said propagation limit has not been reached;

(k) retaining the undetermined direction status of the currently selected voxel and any previously selected voxels still having an undetermined direction status, whenever said propagation limit has been reached; and

(l) performing a new iteration by repeating the appropriate ones of process actions (a) through (I) until there are no remaining previously unselected voxels having a normal vector with an undetermined direction status.

9. The process of claim 5, further comprising performing a local consistency check to ensure that the assigned normal vector direction for each voxel having an assigned direction is accurate, said local consistency check comprising, for each voxel containing at least one reconstruction point, the actions of:

identifying a prescribed number of voxels neighboring the voxel under consideration;

ascertaining the direction assigned to the normal vector associated with the voxel under consideration and its identified neighboring voxels for all the normal vectors that have an assigned direction;

determine which direction the majority of the normal vectors associated with the voxel under consideration and its identified neighboring voxels are assigned for all the normal vectors that have an.assigned direction;

assign said majority direction to the voxel under consideration if it has been previously assigned a contrary direction or if it does not have an assigned direction.

10. The process of claim 4, wherein the process action of extracting a triangular-mesh representation of the surface of the object being modeled, comprises the actions of:

(a) selecting a previously unselected voxel containing reconstruction points;

(b) computing the triangle-mesh representation of the portion of the object being modeled having a surface that contains the selected voxel using a marching cubes procedure while keeping track of each voxel processed via the procedure;

(c) determining whether there are any remaining unprocessed voxels containing reconstruction points;

(d) selecting one of any remaining unprocessed voxels containing reconstruction points in lieu of the previously selected voxel; and

(e) repeating process actions (b) through (d) until there are no remaining unprocessed voxels containing reconstruction points,.

11. A system for modeling an object, comprising:

a camera for capturing digital images of the object that collectively depict all the object'"'"'s surfaces which are to be modeled;

a general purpose computing device;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

input said digital images of the object,

select a plurality of sets of one or more of the digital images,

compute a 3D reconstruction of a portion of the object'"'"'s surfaces from each set of digital images, said 3D reconstructions comprising a plurality of reconstruction points,

register each 3D reconstruction to a common coordinate system to produce an overall 3D reconstruction of the object'"'"'s surfaces,

extract a surface representation of the object from the overall 3D reconstruction, and

create a texture map for the surface representation of the object using the previously captured images of the object.

12. The system of claim 11, further comprising a program module for eliminating extraneous points from each individual 3D reconstruction prior to performing the program module for registering the 3D reconstructions, said program module for eliminating extraneous points comprising the following sub-modules:

for each 3D reconstruction,

calculating a mean distance of the reconstruction points in each of the three orthogonal directions from the origin of a 3D coordinate system associated with said camera used to capture the images employed in computing the reconstruction, as well as a variance in each direction based on the associated mean,

eliminating those reconstruction points existing outside a cuboid region defined by extending the same distance both ways from each mean in each orthogonal direction for a total distance equal to a prescribed multiple of the variance associated with the mean in that direction,

repeating the calculating and eliminating sub-modules until the mean and variance in each orthogonal direction has not changed more than a prescribed amount.

13. The system of claim 12, wherein the program module for eliminating extraneous points further comprises sub-modules for:

using an octree approach to divide a 3D space containing all the reconstruction points associated with each of the 3D reconstructions into voxels each of which contains at least one reconstruction point; and

for each reconstruction point in each of the 3D reconstructions,

identifying a voxel neighborhood made up of the voxel containing the reconstruction point and a prescribed number of neighboring voxels,

counting the number of reconstruction points contained within the voxels of the voxel neighborhood, and

eliminating the reconstruction point whenever the number of points counted in the voxel neighborhood associated with the point does not exceed a prescribed threshold number.

14. The system of claim 11, wherein the program module for extracting a surface representation of the object from the overall 3D reconstruction comprises sub-modules for:

using an octree approach to divide a 3D space containing all the reconstruction points associated with the overall 3D reconstruction into voxels each of which contains at least one reconstruction point;

identifying a voxel neighborhood for each voxel made up of the voxel and a prescribed number of neighboring voxels;

respectively computing a plane for each voxel that best fits the reconstruction points contained within its associated voxel neighborhood; and

extracting a triangular-mesh representation of the surface of the object being modeled based on the planes defined for each voxel.

15. The system of claim 14, wherein the sub-module for extracting a triangular-mesh representation of the surface of the object being modeled, comprises sub-modules for:

selecting a voxel;

employing a marching cubes procedure to compute the triangle-mesh representation of the portion of the object being modeled which has a surface contained within the selected voxel while keeping track of each voxel processed via the procedure;

selecting one of any remaining unprocessed voxels; and

repeating the sub-modules for employing the marching cubes procedure and selecting one of any remaining unprocessed voxels until there are no remaining unprocessed voxels.

16. A computer-readable memory for modeling an object, comprising:

a computer-readable storage medium; and

a computer program comprising program modules stored in the storage medium, wherein the storage medium is so configured by the computer program that it causes a computer to,

compute a series of 3D reconstructions from inputted images depicting every surface of the object that is to be modeled, wherein each reconstruction is comprised of a plurality of reconstruction points which correspond to a portion of the object'"'"'s surfaces, and wherein collectively the 3D reconstructions comprise points that represent all of the object'"'"'s surfaces;

register each 3D reconstruction to a common coordinate system to produce an overall 3D reconstruction of the object'"'"'s surfaces; and

extract a surface representation of the object from the overall 3D reconstruction.

17. The computer-readable memory of claim 16, further comprising a program module which creates a texture map for the surface representation of the object using the inputted images depicting the surfaces of the object.

18. The computer-readable memory of claim 16, further comprising a program module for eliminating reconstruction points that are not representative of the object'"'"'s surfaces which is executed prior to executing the program module for registering the 3D reconstructions, said reconstruction point elimination module comprising executing the following sub-modules for each 3D reconstruction:

calculating a separate mean distance for the reconstruction points in each of the three orthogonal directions from the origin of a 3D coordinate system associated with a camera used to capture the images employed in computing the reconstruction points;

calculating a variance of the reconstruction points in each of the orthogonal directions based on the mean computed for the respective direction;

eliminating points existing outside a region that extends the same distance both ways from the computed mean in each orthogonal direction to a total distance equal to a prescribed multiple of the computed variance for that direction;

re-executing both calculating sub-modules and the eliminating sub-module until the mean and variance in each orthogonal direction has not changed more than a prescribed amount from the last time these values were calculated.

19. The computer-readable memory of claim 16, further comprising a program module for eliminating reconstruction points that are not representative of the object'"'"'s surfaces which is executed prior to executing the program module for registering the 3D reconstructions, said reconstruction point elimination module comprising executing the following sub-modules for each 3D reconstruction:

dividing a 3D space containing all the reconstruction points into voxels, each of which contains at least one of the reconstruction points;

selecting one of the voxels;

identifying a voxel neighborhood made up of the selected voxel and a prescribed number of voxels neighboring the selected voxel;

counting the total number of reconstruction points contained within all the voxels of the identified voxel neighborhood;

eliminating the reconstruction points contained in the selected voxel whenever the number of points counted in the associated voxel neighborhood does not exceed a prescribed threshold number; and

selecting each remaining previously unselected voxel, in turn, and re-executing the identifying, counting and eliminating sub-modules for each newly selected voxel.

20. The computer-readable memory of claim 16, wherein the program module for extracting a surface representation of the object from the overall 3D reconstruction, comprises sub-modules for:

dividing a 3D space containing all the reconstruction points of the overall 3D reconstruction into voxels, each of which contains at least one reconstruction point;

selecting one of the voxels;

identifying a voxel neighborhood made up of the selected voxel and a prescribed number of voxels neighboring the selected voxel;

computing a plane for the selected voxel that best fits the reconstruction points contained within the identified voxel neighborhood;

selecting each remaining previously unselected voxel, in turn, and re-executing the identifying and computing sub-modules for each newly selected voxel; and

extracting a triangular-mesh representation of the surface of the object being modeled based on the planes defined for each voxel.

21. The computer-readable memory of claim 20, wherein the sub-module for extracting a triangular-mesh representation of the surface of the object being modeled, comprises sub-modules for:

(a) selecting one of the voxels containing reconstruction points;

(b) computing the triangle-mesh representation of the portion of the object having a surface that is partially contained in the selected voxel using a marching cubes procedure while keeping track of each voxel processed via the procedure;

(c) determining whether there are any remaining unprocessed voxels containing reconstruction points;

(d) selecting one of any remaining unprocessed voxels containing reconstruction points; and

(e) re-executing sub-modules (b) through (d) until there are no remaining unprocessed voxels containing reconstruction points.