Intelligent modeling, transformation and manipulation system

• US 6,879,946 B2
• Filed: 11/30/2000
• Issued: 04/12/2005
• Est. Priority Date: 11/30/1999
• Status: Expired due to Fees

• Current Assignee: Pattern Discovery Software Systems Limited
• Original Assignee: Pattern Discovery Software Systems Limited
• Inventors: Rong, Li, Wong, Andrew K. C.
• Primary Examiner(s): PALADINI, ALBERT WILLIAM
• Application Number:
  US09/725,929
• Publication Number:
  US 20020095276A1
• Time in Patent Office: 1,594 Days
• Field of Search: 703/2, 345/414, 345/427, 345/420, 382/154, 700/98
• US Class Current: 703/2
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2210/61 Scene description

Abstract

The present invention relates to a method of intelligent 2D and 3D object and scene modeling, transformation and manipulation and more particularly this invention relates to the field of computer modeling, virtual reality, animation and 3D Web streaming. The method uses attributed hypergraph representations (AHR) for modeling, transforming and manipulating objects. From one or more 2D views of a 3D object or scene, range information is first computed and then a triangular mesh model is constructed. The data structure is designed to handle the transformations on the representation corresponding to movements and deformations of the object. In an attributed hypergraph, the attributes associated with the hyperedges and the vertices facilitates modeling of various shapes with geometrical, physical or behavior features. As a hierarchical and generic representation, AHR enables pattern matching, recognition, synthesis and manipulation to be carried out at different resolution levels on different subsets depending on the context. Symbolic computation on knowledge represented in the format of attributed hypergraphs becomes straightforward. Given the features of a 3D object or scene, the procedure of constructing the AHR corresponds to the concept of functor in category theory, which maps one category to another one. The transformations of AHR are in the form of a set of operations defined on attributed hypergraphs, which stand for the motions and deformations of the object. This representation is applied to various modeling and manipulation tasks on 3D objects. The process of motion analysis of a 3D object is the task of extracting a sequence of AH operators from the AHR of the object. A 3D scene can be modeled by AHR and then altered/augmented with other 3D models, by which an augmented reality can be built. Given the AHR'"'"'s of two different 3D shapes, 3D morphing may be accomplished by matching the two AHR'"'"'s and then mapping the difference to a sequence of AH operators. Model based animation of an object can be accomplished by applying a set of AH operators to its AHR. The AHR method forms a data compression system for efficient web streaming over the Internet.

Claims

1. A computerized method of modeling a three dimensional object, comprising:

extracting selected topological features from captured imaging data or other surface data of a three dimensional object;

constructing a triangular mesh representation of said three dimensional object from said topological features, the triangular mesh representation including vertices and edges;

mapping each vertex in said triangular mesh to a corresponding vertex in a graph, mapping each edge in said triangular mesh to a corresponding edge in said graph, computing features of said triangular mesh, mapping said features of said triangular mesh to attributes associated with said graph to construct a representative attributed graph; and

constructing an attributed hypergraph representation from said representative attributed graph.

2. A computerized method according to claim 1 wherein the step of constructing a triangular mesh representation includes:

computing a set of faces from said topological features, each face being bounded by a closed circuit;

constructing a face model which models the surface of said three dimensional object from said set of faces; and

converting said face model into said triangular mesh by triangularizing each of said faces.

3. A computerized method according to claim 1 wherein the step of constructing a triangular mesh representation includes:

constructing a spherical coordinate system for said topological features;

transforming coordinates of said topological features from a conventional three dimensional Cartesian coordinate system to said spherical coordinate system;

applying Delaunay triangulation of said transformed topological features to construct said triangular mesh in said spherical coordinate system; and

transforming said computed triangular meshes from said spherical coordinate system to said conventional Cartesian coordinate system.

4. The computerized method according to claim 3 wherein said step of computing the optimal spherical coordinate system for said topological features includes:

computing a geometrical center of all the coordinates of said topological features;

computing a center of gravity of all the coordinates of said topological features;

computing a major axis and a minor axis from said geometrical center and said center of gravity; and

constructing the spherical coordinate system using said geometrical center, said center of gravity, and said major axis and said minor axis.

5. The computerized method according to claim 1 wherein said step of constructing an attributed hypergraph representation from said representative attributed graphs includes:

mapping each attributed vertex of each of said representative attributed graphs to an elementary node of an attributed hypergraph;

mapping each attributed edge of each of said representative attributed graphs to an elementary edge of said attributed hypergraph;

inducing attributed hyperedges of said attributed hypergraph; and

constructing an attributed hypergraph representation from all said attributed hypergraphs, each of which is from a representative attributed graph.

6. The computerized method according to claim 5 wherein the step of inducing the attributed hyperedges of said attributed hypergraph includes:

selecting at least one type of attribute;

selecting value bins for said at least one type of attribute;

grouping all attributed vertices into groups, such that all attributed vertices in a given group are connected, and have attributed values falling into the same value bin;

assigning a hyperedge to each group; and

computing a value for said selected at least one attribute type for each hyperedge.

7. The computerized method according to claim 5 wherein constructing an attributed hypergraph representation from all said attributed hypergraphs includes:

determining the overlapping regions of all said attributed hypergraphs;

re-computing vertices and edges within said overlapping regions;

integrating the non-overlapping regions and said overlapping regions into one attributed hypergraph; and

re-computing the attributed hyperedges of said integrated attributed hypergraph to construct the attributed hypergraph representation.

8. The method according to claim 1 wherein said selected topological features include points, lines and contours.

9. The method according to claim 1 wherein said step of extracting selected topological features from captured imaging data includes providing digitized captured imaging data of said of three dimensional object and extracting therefrom said selected topological features.

10. The computerized method according to claim 1 wherein said captured imaging data is acquired from a machine vision apparatus that includes means for digitizing said imaging data.

11. The computerized method according to claim 10 wherein said machine vision apparatus includes at least one laser range sensor or at least one charge coupled device (CCD) camera.

12. The computerized method according to claim 1 including a step of storing said attributed hypergraph representation in a storage means accessible by a computer.

13. The computerized method according to claim 12 including a step of performing object reconstruction for each attributed hypergraph and displaying said reconstructed object on a computer.

14. The computerized method according to claim 1 wherein said three dimensional object is a scene comprising a plurality of objects.

15. A computerized method of intelligent model transformation, comprising the steps of:

computing an optimal subgraph isomorphism for attributed hypergraph between a source attributed hypergraph and a target attributed hypergraph, wherein said source attributed hypergraph is to be transformed into said target attributed hypergraph;

computing a sequence of transformation operators from said optimal subgraph isomorphism for attributed hypergraph;

computing a transformation path from said sequence of transformation operators; and

generating a sequence of attributed hypergraphs along said transformation path from said sequence of transformation operators.

16. The computerized method according to claim 15 wherein said step of computing the optimal subgraph isomorphism for attributed hypergraph includes:

segmenting said source attributed hypergraph and said target attributed hypergraph into the same number of layers;

for each of said layers, constructing a source attributed graph from said source attributed hypergraph, and a target attributed graph from said target attributed hypergraph;

for each pair of said source attributed graph and said target attributed graph, computing an optimal subgraph isomorphism for attributed graph; and

computing said optimal subgraph isomorphism for attributed hypergraph from all said optimal subgraph isomorphism for attributed graph for each layer.

17. The computerized method according to claim 16 wherein computing said optimal subgraph isomorphism for attributed graph between the source attributed graph and the target attributed graph includes:

building a search tree for the subgraph isomorphism between said source attributed graph and said target attributed graph;

defining a heuristic cost function of said subgraph isomorphism for attributed graph in said search tree; and

applying an A* heuristic search algorithm with said heuristic cost function to find said optimal subgraph isomorphsim for attributed graph.

18. The computerized method according to claim 15 wherein the step of computing said sequence of transformation operators includes:

finding all unmatched attributed vertices, attributed edges or attributed hyperedges from said optimal subgraph isomorphism for attributed hypergraph;

computing the transformation operators from said unmatched attributed vertices, attributed edges or attributed hyperedges;

finding all matched pairs of attributed vertices, attributed edges or attributed hyperedges from said optimal subgraph isomorphism for attributed hypergraphs;

computing the transformation operators from said matched pairs of attributed vertices, attributed edges or attributed hyperedges; and

organizing all said transformation operators into a sequence.

19. The computerized method according to claim 16 including a step of storing said sequence of transformation operators and said sequence of attributed hypergraphs representations in a storage means accessible by a computer.

20. The computerized method according to claim 19 including a step of performing object reconstruction for each attributed hypergraph and displaying said reconstructed object on a computer.

21. The computerized method according to claim 19 including a step of transmitting said sequence of transformation operators and said sequence of attributed hypergraphs representations from a first computer at a server site to a second computer at a client site and performing object reconstruction for each attributed hypergraph sequence and displaying a reconstructed object sequence on said second computer.

22. A computerized method of intelligent model augmentation of a real scene with a virtual scene into an augmented scene, comprising the steps of:

constructing an attributed hypergraph representation of said real scene;

constructing an attributed hypergraph representation of said virtual scene;

computing a sequence of transformation operators between said two attributed hypergraphs;

integrating said two attributed hypergraph representations into a unified attributed hypergraph representation using said sequence of transformation operators;

constructing in augmented scene from said unified attributed hypergraph representation.

23. The computerized method according to claim 22 wherein the step of integrating said two attributed hypergraph representations into a unified attributed hypergraph representation includes:

integrating attributed vertices of said two attributed hypergraph representations;

re-computing attributes for said integrated attributed vertices;

integrating attributed hyperedges of said two attributed hypergraph representations; and

computing attributes for said integrated attributed hyperedges.

24. The computerized method according to claim 23 including a step of storing said augmented scene in a storage means accessible by a computer.

25. The computerized method according to claim 24 including a step of performing object reconstruction for each attributed hypergraph and displaying said reconstructed object on a computer.

26. A computerized method of modeling and transforming and a three dimensional object, comprising:

extracting selected topological features from captured imaging data or other surface data of a three dimensional object;

constructing a triangular mesh representation of said three dimensional object from said topological features, the triangular mesh representation including vertices and edges;

mapping each vertex in said triangular mesh to a corresponding vertex in a graph, mapping each edge in said triangular mesh to a corresponding edge in said graph, computing features of said triangular mesh, mapping said features of said triangular mesh to attributes associated with said graph to construct a representative attributed graph;

constructing a source attributed hypergraph representation from said representative attributed graph;

computing an optimal subgraph isomorphism for attributed hypergraph between said source attributed hypergraph and a target attributed hypergraph, wherein said source attributed hypergraph is to be transformed into said target attributed hypergraph;

computing a sequence of transformation operators from said optimal subgraph isomorphism for attributed hypergraph;

computing a transformation path from said sequence of transformation operators; and

generating a sequence of attributed hypergraphs along said transformation path from said sequence of transformation operators.

27. A computerized method according to claim 26 wherein said three dimensional object is a real scene, including a step of augmentation of said real scene with a virtual scene into an augmented scene, comprising the steps of:

constructing an attributed hypergraph representation of said real scene;

constructing an attributed hypergraph representation of said virtual scene;

computing a sequence of transformation operators between said source attributed hypergraph representation of said real scene and said attributed hypergraph representation of said virtual scene;

integrating said two attributed hypergraph representations into a unified attributed hypergraph representation using said sequence of transformation operators;

constructing an augmented scene from said unified attributed hypergraph representation.

28. The computerized method according to claim 27 including a step of storing said augmented scene in a storage means accessible by a computer.

29. The computerized method according to claim 27 including a step of performing scene reconstruction for said unified attributed hypergraph representation and displaying said reconstructed scene on a computer.

30. A method of modeling, transforming and manipulating objects according to claim 28 wherein said object is a piece of dynamic web content, including

transmitting said attributed hypergraph representation and said associated sequence of transformation operators of said piece of dynamic web content over said internet from a server computer to at least one client computer,

applying said sequence of transformation operators to said attributed hypergraph representation to generate a sequence of attributed hypergraphs representative of said dynamic web content on said client computer;

and

performing object reconstruction for each of said attributed hypergraphs to reproduce the piece of dynamic of web content on said client computer.