  We propose a new framework for object detection based on a generalization of
the keypoint correspondence framework. This framework is based on replacing
keypoints by keygraphs, i.e. isomorph directed graphs whose vertices are
keypoints, in order to explore relative and structural information. Unlike
similar works in the literature, we deal directly with graphs in the entire
pipeline: we search for graph correspondences instead of searching for
individual point correspondences and then building graph correspondences from
them afterwards. We also estimate the pose from graph correspondences instead
of falling back to point correspondences through a voting table. The
contributions of this paper are the proposed framework and an implementation
that properly handles its inherent issues of loss of locality and combinatorial
explosion, showing its viability for real-time applications. In particular, we
introduce the novel concept of keytuples to solve a running time issue. The
accuracy of the implementation is shown by results of over 800 experiments with
a well-known database of images. The speed is illustrated by real-time tracking
with two different cameras in ordinary hardware.
