GraphTracker : a topology projection invariant optical tracker

Abstract In this paper, we describe a new optical tracking algorithm for pose estimation of interaction devices in virtual and augmented reality. Given a 3D model of the interaction device and a number of camera images, the primary difficulty in pose reconstruction is to find the correspondence between 2D image points and 3D model points. Most previous methods solved this problem by the use of stereo correspondence. Once the correspondence problem has been solved, the pose can be estimated by determining the transformation between the 3D point cloud and the model. Our approach is based on the projective invariant topology of graph structures. The topology of a graph structure does not change under projection: in this way we solve the point correspondence problem by a subgraph matching algorithm between the detected 2D image graph and the model graph. In addition to the graph tracking algorithm, we describe a number of related topics. These include a discussion on the counting of topologically different graphs, a theoretical error analysis, and a method for automatically estimating a device model. Finally, we show and discuss experimental results for the position and orientation accuracy of the tracker.