Image processing apparatus and image capturing apparatus, which approximate object shapes using a plurality of polygon patches

• US 6,847,359 B1
• Filed: 10/11/2000
• Issued: 01/25/2005
• Est. Priority Date: 10/14/1999
• Status: Expired due to Fees

• Current Assignee: Fujifilm Corporation (Fujifilm Holdings Corporation)
• Original Assignee: Fuji Photo Film Co Limited (Fujifilm Holdings Corporation)
• Inventors: Ono, Shuji
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): WALLACE, SCOTT A
• Application Number:
  US09/685,688
• Time in Patent Office: 1,567 Days
• Field of Search: 345/441, 345/646, 345/647, 345418-420
• US Class Current: 345/419
• CPC Class Codes: G06T 17/10 Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes
• 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

According to the present invention, an image processing apparatus, that can effectively generate a polygon model approximating a shape of an object by a plurality of polygon patches, includes: an input portion for inputting three-dimensional data of the object of the input points; a storage portion for storing coordinate values of the input points input by the input portion; an update portion for updating three-dimensional coordinate values of a plurality of lattice points of the polygon model so as to reflect a distribution density of the input points, the lattice points being arranged to form lattices on a two-dimensional plane; and an output portion for outputting, as the polygon patches of the polygon model, the three-dimensional coordinate values of the lattice points updated by the update portion and a relationship of connections between the lattice points in the lattices.

Claims

1. An image processing apparatus for generating a polygon model that approximates a shape of an object using a plurality of polygon patches, comprising:

an input portion for inputting three-dimensional coordinate data of the object as input points;

a storage portion for storing coordinate values of the input points input by the input portion;

an update portion for updating three-dimensional coordinate values of a plurality of lattice points of a polygon model to reflect a distribution density of the input points, the lattice points being initially arranged to form a plurality of lattices on a two-dimensional plane connected to each other to form a two-dimensional map such that, upon updating a range in which a vicinity of the lattice points exist becomes smaller, said input points being mapped into said two-dimensional map by which said lattice points adjacent to each of said input points converge in a determined manner toward said input points thereby providing a representation of said distribution density of said input points on said two-dimensional map; and

an output portion for outputting, as the polygon patches of the polygon model, the updated three-dimensional coordinate values of the lattice points and a relationship of connections between the lattice points in the lattices.

2. An image processing apparatus according to claim 1, wherein the lattice points of the polygon model are arranged to form quadrangular lattices on the two-dimensional plane.

3. An image processing apparatus according to claim 2, wherein each of the quadrangular polygon patches is divided into two triangular polygon patches by setting a diagonal connecting two of four connected lattice points obtained by the update by the update portion, the two lattice points being not adjacent to each other.

4. An image processing apparatus according to claim 1, wherein the lattice points of the polygon model are arranged to form triangular lattices on the two-dimensional plane.

5. An image processing apparatus according to claim 1, wherein the output portion displays the polygon model based on the polygon patches, and

wherein a manipulator is further provided for modifying and/or transforming the polygon model displayed by the output portion.

6. An image processing apparatus for generating a polygon model that approximates a shape of an object using a plurality of polygon patches, comprising:

an input portion for inputting three-dimensional coordinate data of the object as input points;

a storage portion for storing coordinate values of the input points input by the input portion;

an update portion for updating three-dimensional coordinate values of a plurality of lattice points of a polygon model to reflect a distribution density of the input points, the lattice points being initially arranged to form a plurality of lattices on a two-dimensional plane connected to each other to form a two-dimensional map such that, upon updating, said input points are mapped into said two-dimensional map thereby providing a representation of said distribution density of said input points on said two-dimensional map; and

an output portion for outputting, as the polygon patches of the polygon model, the updated three-dimensional coordinate values of the lattice points and a relationship of connections between the lattice points in the lattices;

wherein the update portion updates the three-dimensional coordinate values of the plurality of lattice points of the polygon model one by one, for each of the input points stored in the storage portion; and

wherein the update portion updates the three-dimensional coordinate values of the lattice points, by making a three-dimensional coordinate value of a closest lattice point and three-dimensional coordinate values of a plurality of vicinity lattice points closer to a three-dimensional coordinate value of each input point by a predetermined amount such that a range in which the vicinity lattice points exist becomes smaller, the closest lattice point being closer to said input point than any other lattice point in the three-dimensional coordinate system, the plurality of vicinity lattice points existing in the vicinity of the closest lattice point in the lattices on the two-dimensional plane.

7. An image processing apparatus according to claim 6, wherein said range in which the vicinity lattice points exist becomes smaller as a number of times the update is performed by the update portion increases.

8. An image processing apparatus according to claim 6, wherein the amount by which the three-dimensional coordinate value of each of the vicinity lattice points is updated becomes smaller as a distance from said vicinity lattice point to the closest lattice point increases.

9. An image capture apparatus for obtaining information regarding depths of an object and outputting a polygon model of the object, comprising:

a capture portion for capturing an image of the object;

a depth calculator for calculating the information regarding the depths of the object from the image captured by the capture portion, to output three-dimensional coordinate data of the object;

a storage portion for storing as coordinate values of input points the three-dimensional coordinate data output by the depth calculator;

an update portion for updating three-dimensional coordinate values of a plurality of lattice points of the polygon model to reflect a distribution density of the input points, the lattice points being initially arranged to form a plurality of lattices on a two-dimensional plane that are connected to each other to form a two-dimensional map such that, upon updating a range in which a vicinity of the lattice points exists becomes smaller, said input points being mapped into said two-dimensional map by which said lattice points adjacent to each of said input points converge in a determined manner toward said input points thereby providing a representation of said distribution density of said input points on said two-dimensional map; and

an output portion for outputting as polygon patches of the polygon model the three-dimensional coordinate values of the lattice points updated by the update portion and a relationship of connections between the lattice points in the lattices.

10. An image capture apparatus according to claim 9, wherein a direction from which the object is seen is perpendicular to the two-dimensional plane on which the lattices are arranged.

11. An image capture apparatus according to claim 10, wherein values that are proximate to coordinate values of the input points in the direction from which the object is seen, respectively, are used as initial coordinate values in the direction perpendicular to the two-dimensional plane on which the lattices are arranged.

12. An image processing method for generating a polygon model that approximates a shape of an object by a plurality of polygon patches, comprising:

inputting three-dimensional data of the object as input points;

storing coordinate values of the input points;

updating three-dimensional coordinate values of a plurality of lattice points of the polygon model to reflect a distribution density of the input points, the lattice points being initially arranged to form a plurality of lattices on a two-dimensional plane that are connected to each other to form a two-dimensional map such that, upon updating a range in which a vicinity of the lattice points exist become smaller, said input points being mapped into said two-dimensional map by which said lattice points adjacent to each of said input points converge in a determined manner toward said input points thereby providing a representation of said distribution density of said input points on said two-dimensional map; and

outputting as the polygon patches of the polygon model the updated three-dimensional coordinate values of the lattice points and a relationship of connections between the lattice points in the lattices.

13. An image processing method for generating a polygon model that approximates a shape of an object by a plurality of polygon patches, comprising:

inputting three-dimensional data of the object as input points;

storing coordinate values of the input points;

updating three-dimensional coordinate values of a plurality of lattice points of the polygon model to reflect a distribution density of the input points, the lattice points being initially arranged to form a plurality of lattices on a two-dimensional plane that are connected to each other to form a two-dimensional map such that, upon updating, said input points are mapped into said two-dimensional map thereby providing a representation of said distribution density of said input points on said two-dimensional map; and

outputting as the polygon patches of the polygon model the updated three-dimensional coordinate values of the lattice points and a relationship of connections between the lattice points in the lattices;

wherein the three-dimensional coordinate values of the lattice points are updated one by one by making a three-dimensional coordinate value of a closest lattice point and three-dimensional coordinate values of a plurality of vicinity lattice points closer to a three-dimensional coordinate value of each of the input points by a predetermined amount such that a range in which the vicinity lattice points exist becomes smaller, the closest lattice point being the closest one of the lattice points to said input point in a three-dimensional system, the vicinity lattice points being the lattice points that exist in the vicinity of the closest lattice point in the lattices on the two-dimensional plane.

14. A computer-readable recording medium storing a program for generating a polygon model that approximates a shape of an object using a plurality of polygon patches, the program comprising:

an input model for making three-dimensional coordinate data of an object be input as input points;

a storage module for making values of the input points input by the input module being stored;

an update module for updating three-dimensional coordinate values of a plurality of lattice points of the polygon model to reflect a distribution density of the input points, the lattice points being initially arranged to form a plurality of lattices on a two-dimensional plane to form a two-dimensional map such that, upon updating a range in which a vicinity of the lattice points exist becomes smaller, said input points being mapped into said two-dimensional map by which said lattice points adjacent to each of said input points converge in a determined manner toward said input points thereby providing a representation of said distribution density of said input points on said two-dimensional map; and

an output module for outputting the three-dimensional coordinate values of the lattice points updated by the update module and a relationship of connections between the lattice points in the lattices as the polygon patches of the polygon model.