Method of and system for determining a data model designed for being superposed with an image of a real object in an object tracking process

• US 7,889,193 B2
• Filed: 01/30/2007
• Issued: 02/15/2011
• Est. Priority Date: 02/03/2006
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Metaio GmbH (Apple Inc.)
• Inventors: Platonov, Juri, Langer, Marion
• Primary Examiner(s): Yang; Ryan R
• Application Number:
  US11/668,495
• Publication Number:
  US 20070182739A1
• Time in Patent Office: 1,477 Days
• Field of Search: 345/419, 345/420, 345/633, 345/427, 382/154
• US Class Current: 345/419
• CPC Class Codes: G06T 15/20 Perspective computation
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 19/006 Mixed reality object pose determination, tracking or camera calibration for mixed reality G06T7/00
• CPC Class Codes: G06T 7/564 from contours

Abstract

A data model which is designed for being superposed with an image of a real object in an optical object tracking process is determined by the following steps: providing a three-dimensional CAD model (10) for representing the real object, and thereafter there are different synthetic two-dimensional views (31 to 34) of said CAD model (10) generated. Each generated view (31 to 34) is subjected to edge extraction for determining at least one extracted edge (38, 39) in the respective view, with the edges (38, 39) extracted from said respective views (31 to 34) being transformed to a three-dimensional contour model (85, 91) corresponding to said data model to be determined. Permits rapid and efficient generation of a contour model as a data model intended for being superposed with an image of a real object.

Claims

1. A method of determining a data model of virtual information to be superposed with an image of a real object in an object tracking process, said method being performed on at least one digital computer configured to implement method steps comprising:

providing a three-dimensional CAD model (10) on said at least one digital computer wherein said three-dimensional CAD model (10) represents a real object to be tracked in a subsequent object tracking process;

generating different synthetic two-dimensional views (31 to 34) from said CAD model (10) on said at least one digital computer;

subjecting each generated view (31 to 34) to edge extraction on said at least one digital computer to determine at least one extracted edge (38, 39) in a respective view and determining which edges of the real object to be tracked are of relevance for said subsequent object tracking process; and

,

transforming on said at least one digital computer said at least one extracted edge (38, 39) extracted from said respective view selected from said respective views (31 to 34) to a three-dimensional contour model (85, 91) corresponding to a data model.

2. The method of claim 1, further comprising:

determining subsequent to said edge extraction, respective two-dimensional edge points (37) of an extracted edge (38, 39); and

,

determining in said transforming said at least one extracted edge (38, 39), a three-dimensional position of said respective edge points (37) using said CAD model (10), obtaining a set of three-dimensional points (70) from which said three-dimensional contour model (85, 91) is determined.

3. The method of claim 2, further comprising:

detecting each edge point (37) as a two-dimensional point in an image plane and said three-dimensional position (70) is determined in a coordinate system (11) of said CAD model (10).

4. The method of claim 2, further comprising:

storing obtained said three-dimensional positions (70) of said respective edge points are stored in a data structure permitting inquiries with respect to a spatial proximity of three-dimensional points, said data structure being in particular in a form of a k-d tree.

5. The method of claim 2, further comprising:

incrementing a count value for said three-dimensional point if after determining said three-dimensional position (70) of an edge point it is ascertained that there is already a three-dimensional point (70) present at said three-dimensional position.

6. The method of claim 2, further comprising:

incrementing a corresponding count value when edge points (37) belonging semantically to a same three-dimensional position in space are stored as one three-dimensional point (70), with each edge point mapped on this three-dimensional position.

7. The method of claim 6, further comprising:

recognizing that an edge point semantically belongs to said same three-dimensional position wherein there is started for each edge point (37), after determination of said three-dimensional position (70), an inquiry as to whether there is at least one stored three-dimensional point (70) in an immediate vicinity and if so, there is no new three-dimensional point stored, but said corresponding count value of an already stored three-dimensional point (70) is incremented and with said immediate vicinity in this regard being determined by means of a threshold value.

8. The method of claim 2, further comprising:

associating with each three-dimensional point (70) a value which indicates how many times said three-dimensional point has been rated as belonging to one visual edge (38, 39).

9. The method of claim 8, further comprising:

discarding with aid of a threshold value, a three-dimensional point (70) having an associated value below said threshold value with remaining three-dimensional points (70) representing visually relevant contours of said real object.

10. The method of claim 2, further comprising:

reducing said set of three-dimensional points (70) to portions representing with high probability relevant contours of said real object for a subsequent tracking method in an augmented reality system; and

,

discarding said three-dimensional points (70) employing a threshold value method wherein said three-dimensional points (70) have an associated probability or in particular an associated count value below a specific threshold value.

11. The method of claim 2, further comprising:

dividing said set of three-dimensional points (70) into joined contour segments (71 to 75).

12. The method of claim 11, further comprising:

using an algorithm for said dividing said set of three-dimensional points (70) into joined contour segments (71 to 75), wherein said algorithm utilizes an Euclidean minimum spanning tree of said three-dimensional points.

13. The method of claim 12, further comprising:

forming a first graph for determining said Euclidean minimum spanning tree (201) of a point cloud (200), at first a graph G interconnecting all such points of said point cloud that have a mutual distance from each other that is smaller than or equal to a maximum acceptable noise r_max of an edge.

14. The method of claim 13, further comprising:

determining a tree (201) as said Euclidean minimum spanning tree of said graph G, wherein said tree (201) interconnects all points of said graph G such that a sum of their edge lengths is at minimum.

15. The method of claim 11, further comprising:

replacing at least part of said three-dimensional points (70) in said contour segments by a suitable contour representation (81 to 85;

91) which is approximated in particular with aid of an optimization method using curves, B splines, Bezier splines or NURBS.

16. The method of claim 1, wherein

generating the different synthetic two-dimensional views (31 to 34) from said CAD model (10) comprises simulating different light situations.

17. The method of claim 1, further comprising:

generating a pseudo color view (50) for each two-dimensional view (31 to 34) of said CAD model (10), having individual faces, with each face having an unequivocal color assigned thereto;

retrieving a color value from said pseudo color image for each edge point at the same two-dimensional position;

accessing the corresponding face of said CAD model (10) using a determined color value that is used as an index with each face of said CAD model spanning a plane in three-dimensional space; and

,

determining a three-dimensional position (70) of a two-dimensional edge point being a point of intersection of said plane of said corresponding face of said CAD model (10) and of a beam (61, 62) connecting a camera center of a virtual camera (40) to said respective two-dimensional edge point.

18. The method of claim 1, wherein the edges that are of relevance are ascertained as relevant those which can be extracted from the respective view in a large number of different views.

19. The method of claim 1, wherein said subjecting each said generated view to edge extraction comprises using a same edge extractor as is used in the subsequent object tracking process.

20. The method of claim 1, wherein said generating said different synthetic two-dimensional views includes using a virtual camera in generating the synthetic two-dimensional views from different positions, wherein positioning of the virtual camera takes place in accordance with a probability distribution which considers which views of the real object are most probable from a user'"'"'s view.

21. An object tracking method making use of a data model of virtual information being superposed with an image of a real object on an image plane, said method comprising the following steps:

providing a three-dimensional CAD model (10) for representing a real object to be tracked in a subsequent object tracking process;

generating different synthetic two-dimensional views (31 to 34) from said CAD model (10);

subjecting each generated view (31 to 34) to edge extraction, determining at least one extracted edge (38, 39) in a respective view and determining which edges of the real object to be tracked are of relevance for said subsequent object tracking process;

transforming said at least one extracted edge (38, 39) extracted from said respective view selected from said respective views (31 to 34) to a three-dimensional contour model (85, 91) corresponding to a data model;

taking a two-dimensional image using a camera, said image at least including said real object; and

,

performing an optimization method projecting said data model to said image plane in order to superpose a projection of said data model with the image of said real object on said image plane.

22. The method of claim 21, comprising the following steps:

comparing said projection of said data model to said image of said real object; and

,

determining parameters of a pose of said camera based on a comparison result.

23. A system for determining a data model of virtual information which is designed for being superposed with an image of a real object by means of an augmented reality system, comprising:

a means for providing a three-dimensional CAD model (10) for representing the real object to be tracked in a subsequent object tracking process;

a means for generating different synthetic two-dimensional views (31 to 34) from said CAD model (10), said means being designed furthermore to subject each generated view (31 to 34) to an edge extraction for determining at least one extracted edge (38, 39) in the respective view and means for determining which edges of the real object to be tracked are of relevance for said subsequent object tracking process; and

,

a means for transforming said edges (38, 39) extracted from the respective views (31 to 34) to a three-dimensional contour model (85, 91) corresponding to said data model.

24. A computer program product in a memory medium adapted to be loaded into the internal memory of a digital computer and comprising software code sections configured to:

provide a three-dimensional CAD model (10) for representing a real object to be tracked in a subsequent object tracking process;

generate different synthetic two-dimensional views (31 to 34) from said CAD model (10);

subject each generated view (31 to 34) to edge extraction for determining at least one extracted edge (38, 39) in a respective view and determine which edges of the real object to be tracked are of relevance for said subsequent object tracking process; and

,

transform said at least one extracted edge (38, 39) extracted from said respective view selected from said respective views (31 to 34) to a three-dimensional contour model (85, 91) corresponding to a data model.