Implicit Data Association from Spectrally Clustered Local Matches

Inside Data Association Workshop: Robotics Science and Systems, 2008

PDF thumbnail
(PDF, 856.8 KB )


Place recognition is a fundamental but challenging perceptual problem. One common application is robot mapping: recognizing places allows the trajectory of a robot to be over-constrained, allowing better maps to be produced. Similar looking (but physically distinct) environments can result in false positives, a problem exacerbated by the large positional uncertainties that can accumulate from dead-reckoning. A classic approach is based on associating observations with specific landmarks, i.e., explicit global data association. Good results, however, typically require jointly assigning several observations, leading to computationally expensive algorithms.

In this paper, we describe an alternative approach that is based on local matching. These local matches are derived from a set of easily computed pose-to-pose matches. Outliers and ambiguous cases are rejected using SCGP, a spectral clustering algorithm. We argue that when the spatial extent of a locally unambiguous match is large in comparison to the robot's positional uncertainty, the match becomes a reliable place recognition. We illustrate our method on a real dataset with significant perceptual ambiguity, evaluating the robustness of the method using ground-truth data.

This paper has been revised and expanded. Click here to go to the updated paper.


DLR Circles Dataset
Movie 21.0 MB

Inlier Cluster
Movie 90.1 MB


    AUTHOR     = {Edwin Olson},
    TITLE      = {Implicit Data Association from Spectrally Clustered Local Matches},
    BOOKTITLE  = {Inside Data Association Workshop: Robotics Science and Systems},
    YEAR       = {2008},
    MONTH      = {June},