Unstructured Point Cloud Matching Within Graph-Theoretic and Thermodynamic Frameworks

Abstract

In the context of object recognition from point cloud data, we present a thermodynamically-inspired graph theoretic algorithm to address the problem of matching the scene and the model point clouds, when the cardinalities of the two sets are orders of magnitude different. Such an approach determines a subset of points from the model that is structurally and spatially as similar as possible to the set of points in the scene. A new formulation for graph enthalpy characterizes the structural differences between point sets, which together with the existing notions of graph entropy quantifies the Gibbs' free energy. A two-scale approach is proposed, wherein, at the coarse scale, a set of points that comprise the model neighborhood around the scene is identified by minimization of entropy. At the fine scale, the desired correspondence is achieved by a refinement process, aimed at maximizing the Gibbs' free energy. The results demonstrate the robustness and efficiency of the approach.