Method of composing three-dimensional multi-viewpoints data

• US 6,405,151 B1
• Filed: 09/28/1999
• Issued: 06/11/2002
• Est. Priority Date: 10/08/1998
• Status: Expired due to Term

• Current Assignee: Minolta Co., Ltd. (Konica Minolta Inc.)
• Original Assignee: Minolta Co., Ltd. (Konica Minolta Inc.)
• Inventors: Shiono, Koichi, Fujii, Eiro
• Primary Examiner(s): Grimley, Arthur T.
• Assistant Examiner(s): Le, John
• Application Number:
  US09/407,771
• Time in Patent Office: 987 Days
• Field of Search: 702/150, 702/152, 702/153, 702/155, 345/118, 345/119, 345/427
• US Class Current: 702/155
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 17/205 Re-meshing

Abstract

Based on maximum value of distances between vertexes of polygons in plurality of polygon meshes, size of voxel is determined. Respective potential values for plurality of polygon meshes are obtained on basis of signed respective distances of voxels. Sum of potential values is obtained as added potential value. Polygon mesh made of equivalent face of added potential value is defined as surface mesh. Comparison between surface mesh and plurality of original polygon meshes is performed, to determine respective vertexes of plurality of original meshes corresponding to each vertex of surface mesh. Polygons of surface mesh are divided/synthesized to obtain intermediate surface data. Referring to original polygon meshes, respective vertexes of intermediate surface data are moved. Composed polygon mesh data are obtained with stability even if original three-dimensional data have errors, within practical time, without unnecessarily high redundancy, while maintaining accuracy and resolution of three-dimensional multi-viewpoints data.

Claims

1. A method of composing a plurality of three-dimensional data obtained by measuring an object from a number of viewpoints, said plurality of three-dimensional data defining a plurality of original meshes representing a plurality of surface images of said object observed from different directions and/or distances, said method comprising the steps of:

(a) converting said plurality of original meshes into a first surface mesh through a volumetric method; and

(b) correcting a mesh structure of said first surface mesh by comparing said first surface mesh with said plurality of original meshes, to thereby obtain a second surface mesh; and

(c) correcting a local position of said second surface mesh by comparing said second surface mesh with said plurality of original meshes, to thereby obtain a third surface mesh,

wherein each mesh is defined by a set of polygons, and

a composed result of said plurality of three-dimensional data is given by data representing said third surface mesh.

2. The method according to claim 1, wherein said step (b) includes the steps of

(b-1) sequentially selecting one of vertexes of said first surface mesh as an objective vertex;

(b-2) selecting a reference mesh from said plurality of original meshes with respect to said objective vertex; and

(b-3) correcting a structure of said first surface mesh surrounding said objective vertex according to a resolution of said reference mesh, to obtain said second surface mesh.

3. The method according to claim 2, wherein

said step (b-2) includes the steps of

(b-2-1) selecting reference meshes existing within a threshold distance from said objective vertex, out of said plurality of original meshes;

(b-2-2) determining the highest one of resolutions of said reference meshes as a reference resolution; and

(b-2-3) correcting said mesh structure of said first surface mesh surrounding said objective vertex according to said reference resolution.

4. The method according to claim 3, wherein

said step (b-2-3) includes the step of

adding a polygon to a portion of said first surface mesh surrounding said objective vertex when said reference resolution is higher than a resolution of said first surface mesh.

5. The method according to claim 3, wherein

said step (b-2-3) includes the step of

deleting a polygon from a portion of said first surface mesh surrounding said objective vertex when said reference resolution is lower than a resolution of said first surface mesh.

6. The method according to claim 1, wherein

said step (c) includes the steps of

(c-1) sequentially selecting one of vertexes of said second surface mesh as an objective vertex;

(c-2) selecting a reference portion from said plurality of original meshes with respect to said objective vertex; and

(c-3) correcting a relative position of said objective vertex with respect to said reference portion, to obtain said third surface mesh.

7. The method according to claim 6, wherein

said step (c-2) includes the steps of

(c-2-1) selecting mesh elements existing within a threshold distance from said objective vertex, out of said plurality of original meshes;

and

(c-2-2) moving said objective vertex to reduce a sum of distances from said objective vertex to said mesh elements.

8. The method according to claim 7, wherein

said step (c-2-2) includes the step of

moving said objective vertex to minimize said sum of distances from said objective vertex to said mesh elements.

9. The method according to claim 7, wherein

said step (c-2-2) includes the step of

moving said objective vertex so that said sum of distances from said objective vertex to said mesh elements is smaller than a predetermined threshold value.

10. The method according to claim 7, wherein

said step (c-2-1) includes the steps of

determining whether or not said plurality of original meshes have a facing polygon which faces to said objective vertex;

adding said facing polygon to said mesh elements when said plurality of original meshes have said facing polygon; and

adding a vertex corresponding to said objective vertex among vertexes of said plurality of original meshes to said mesh elements when said plurality of original meshes have no facing polygon.

11. The method according to claim 1, wherein

said step (a) includes the steps of

(a-1) defining a voxel grid;

(a-2) calculating potentials of voxels for each one of said plurality of original meshes, to obtain a plurality of potential values for each voxel;

(a-3) composing said plurality of potentials for each voxel, to obtain a composed potential; and

(a-4) obtaining said first surface mesh on the basis of said composed potential.

12. An apparatus for composing a plurality of three-dimension data obtained by measuring an object from a number of viewpoints, said plurality of three-dimensional data defining a plurality of original meshes representing a plurality of surface images of said object observed from different directions and/or distances, said apparatus comprising:

(a) a first processing unit for converting said plurality of original meshes into a first surface mesh through a volumetric method;

(b) a second processing unit for correcting a mesh structure of said first surface mesh by comparing said first surface mesh with said plurality of original meshes, to thereby obtain a second surface mesh; and

(c) a third processing unit for correcting a local position of said second surface mesh by comparing said second surface mesh with said plurality of original meshes, to thereby obtain a third surface mesh,

wherein each mesh is defined by a set of polygons, and

a composed result of said plurality of three-dimensional data is given by data representing said third surface mesh.

13. The apparatus according to claim 12, wherein

said second processing unit includes

(b-1) a first sub-processing unit for sequentially selecting one of vertexes of said first surface mesh as an objective vertex;

(b-2) a second sub-processing unit for selecting a reference mesh from said plurality of original meshes with respect to said objective vertex; and

(b-3) a third sub-processing unit for correcting a structure of said first surface mesh surrounding said objective vertex according to a resolution of said reference mesh, to obtain said second surface mesh.

14. The apparatus according to claim 12, wherein

said third processing unit includes

(c-1) a first sub-processing unit for sequentially selecting one of vertexes of said second surface mesh as an objective vertex;

(c-2) a second sub-processing unit for selecting a reference portion from said plurality of original meshes with respect to said objective vertex; and

(c-3) a third sub-processing unit for correcting a relative position of said objective vertex with respect to said reference portion, to obtain said third surface mesh.