Methods and Apparatus for Dot Marker Matching

• US 20100080447A1
• Filed: 09/29/2008
• Published: 04/01/2010
• Est. Priority Date: 09/29/2008
• Status: Active Grant

• Current Assignee: Two PIC MC LLC
• Original Assignee: ImageMovers Digital LLC
• Inventors: Epps, Douglas, Kanazawa, Nori
• Granted Patent: US 8,204,340 B2
• Time in Patent Office: Days
• US Class Current: 382/154
• CPC Class Codes: G06T 2200/08 involving all processing steps from image acquisition to 3D model generation
• CPC Class Codes: G06T 2207/10012 Stereo images
• CPC Class Codes: G06T 2207/30201 Face
• CPC Class Codes: G06T 2207/30204 Marker
• CPC Class Codes: G06T 7/593 from stereo images
• CPC Class Codes: G06V 10/426 Graphical representations
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

A method for a computer system includes receiving a first camera image of a 3D object having sensor markers, captured from a first location, at a first instance, receiving a second camera image of the 3D object from a second location, at a different instance, determining points from the first camera image representing sensor markers of the 3D object, determining points from the second camera image representing sensor markers of the 3D object, determining approximate correspondence between points from the first camera image and points from the second camera image, determining approximate 3D locations some sensor markers of the 3D object, and rendering an image including the 3D object in response to the approximate 3D locations.

Claims

1. A method for a computer system comprising:

receiving a first view of a three-dimensional object from a first sensor from a first location with respect to the three-dimensional object, at a first instance in time, wherein the object includes a plurality of sensor markers;

receiving a second view of the three-dimensional object from a second sensor from a second location with respect to the three-dimensional object, at substantially the first instance of time;

determining a first plurality of points from the first view of the three-dimensional object in response to a first plurality of sensor markers from the plurality of sensor markers;

determining a second plurality of points from the second view of the three-dimensional object in response to a second plurality of sensor markers from the plurality of sensor markers;

determining at least an approximate correspondence between points in a subset of points from the first plurality of points and points in a subset of points from the second plurality of points;

determining approximate three-dimensional locations of a third plurality of sensor markers from the plurality of sensor markers in response to the approximate correspondence; and

rendering an image of the three-dimensional object in response to the approximate three-dimensional locations of the third plurality of sensor markers.

2. The method of claim 1 wherein determining the approximate correspondence comprises performing a graph matching algorithm in response to the points in the subset of points from the first plurality of points and in response to the points in the subset of points from the second plurality of points.

3. The method of claim 1 wherein determining the approximate correspondence comprises performing an A* algorithm in response to the points in the subset of points from the first plurality of points and in response to the points in the subset of points from the second plurality of points.

4. The method of claim 1 wherein the determining the approximate correspondence comprises:

determining a plurality of matches between the points in the subset of points from the first plurality of points and the points in the subset of points from the second plurality of points;

computing a cost function associated with each match from the plurality of matches; and

removing a first plurality of matches from the plurality of matches in response to the associated cost function, wherein the associated cost function with matches from the first plurality of matches is higher than an associated cost function of matches from a second plurality of matches from the plurality of matches.

5. The method of claim 4 wherein the subset of points from the second plurality of points is determined in response to an epipolar computation.

6. The method of claim 1 further comprising:

storing a representation of the image on a tangible media;

retrieving the representation of the image; and

displaying the image to a user.

7. The method of claim 1 wherein a majority of sensor markers of the first plurality of sensor markers are also sensor markers in the second plurality of sensor markers.

8. A computer system comprising:

a memory configured to store a first view of a three-dimensional object from a first sensor from a first location with respect to the three-dimensional object, at a first instance in time, wherein the object includes a plurality of sensor markers, and configured to store a second view of the three-dimensional object from a second sensor from a second location with respect to the three-dimensional object, at substantially the first instance of time;

a processor coupled to the memory, wherein the processor is configured to determine a first plurality of points from the first view of the three-dimensional object in response to a first plurality of sensor markers from the plurality of sensor markers, wherein the processor is configured to determine a second plurality of points from the first view of the three-dimensional object in response to a second plurality of sensor markers from the plurality of sensor markers, wherein the processor is configured to determine at least an approximate correspondence between points in a subset of points from the first plurality of points and points in a subset of points from the second plurality of points, and wherein the processor is configured to determine approximate three-dimensional locations of a third plurality of sensor markers from the plurality of sensor markers in response to the approximate correspondence; and

a display coupled to the memory and to the processor, wherein the display is configured to display a representation of the approximate three-dimensional locations of the third plurality of sensor markers.

9. The computer system of claim 8 wherein the processor is configured to implement a graph matching algorithm in response to the points in the subset of points from the first plurality of points and in response to the points in the subset of points from the second plurality of points, to determine the approximate correspondence between points in the subset of points from the first plurality of points and points in the subset of points from the second plurality of points.

10. The computer system of claim 8 wherein the processor is configured to implement an A* algorithm in response to the points in the subset of points from the first plurality of points and in response to the points in the subset of points from the second plurality of points, to determine the approximate correspondence between points in the subset of points from the first plurality of points and points in the subset of points from the second plurality of points.

11. The computer system of claim 8:

wherein the processor is configured to determine a plurality of matches between the points in the subset of points from the first plurality of points and the points in the subset of points from the second plurality of points;

wherein the processor is configured to computing a cost function associated with each match from the plurality of matches; and

wherein the processor is configured to remove a first plurality of matches from the plurality of matches in response to the associated cost function, wherein the associated cost function with matches from the first plurality of matches is higher than an associated cost function of matches from a second plurality of matches from the plurality of matches.

12. The computer system of claim 8 wherein the processor is configured to computing the cost function associated with each match from the plurality of matches in response to angular distances and distance distances.

13. The computer system of claim 8:

wherein the processor is configured to determine an epipolar relationship; and

wherein the processor is configured to determine the subset of points from the second plurality of points in response to an epipolar computation.

14. The computer system of claim 8:

wherein the processor is configured to render an image of the three-dimensional object; and

wherein the display is configured to display the image to a user.

16. The computer program product of claim 15 wherein code that determine the approximate correspondence comprises code configured to direct the processor to perform a graph matching algorithm in response to the points in the subset of points from the first plurality of points and in response to the points in the subset of points from the second plurality of points.

17. The computer program product of claim 15 wherein code that determine the approximate correspondence comprises code configured to perform an A* algorithm in response to the points in the subset of points from the first plurality of points and in response to the points in the subset of points from the second plurality of points.

18. The computer program product of claim 15 wherein code that determine the approximate correspondence comprises:

code configured to direct the processor to determine a plurality of matches between the points in the subset of points from the first plurality of points and the points in the subset of points from the second plurality of points;

code configured to direct the processor to compute a cost function associated with each match from the plurality of matches; and

code configured to direct the processor to remove a first plurality of matches from the plurality of matches in response to the associated cost function, wherein the associated cost function with matches from the first plurality of matches is higher than an associated cost function of matches from a second plurality of matches from the plurality of matches.

19. The computer program product of claim 18 further comprising:

code configured to direct the processor to determine an epipolar relationship between the first image and the second image; and

code configured to direct the processor to determine the subset of points from the second plurality of points in response to the epipolar relationship.

20. The computer program product of claim 18 further comprising:

code configured to direct the processor to render an image of the three-dimensional object in response to the approximate three-dimensional displacements; and

code configured to direct the processor to display the image to a display.

25. A computer program product comprising a computer-readable tangible media including computer-executable code for a computer system including a processor and a memory, wherein computer-readable tangible media comprises:

code configured to direct the processor to receive a first image of a three-dimensional object from a camera from a first location with respect to the three-dimensional object, at a first instance in time, wherein the object includes a plurality of sensor markers;

code configured to direct the processor to receive a second image of the three-dimensional object from the camera from the first location with respect to the three-dimensional object, at a second instance of time;

code configured to direct the processor to determine a first plurality of points from the first image of the three-dimensional object in response to a first plurality of sensor markers from the plurality of sensor markers;

code configured to direct the processor to determine a second plurality of points from the second image of the three-dimensional object in response to a second plurality of sensor markers from the plurality of sensor markers;

code configured to direct the processor to determine at least an approximate correspondence between points in a subset of points from the first plurality of points and points in a subset of points from the second plurality of points;

code configured to direct the processor to determine approximate three-dimensional displacements of a third plurality of sensor markers from the plurality of sensor markers in response to the approximate correspondence; and

code configured to direct the processor to display a representation of the approximate three-dimensional displacements of the third plurality of sensor markers on top of the first image.