2015/05/23 by Samuel de Sousa, de Sousa, Samuel, Walter G. Kropatsch +1
Computer Science · Engineering · #Computer Vision and Pattern Recognition (cs.CV) #Data Management and Algorithms #FOS: Computer and information sciences #Graph Theory and Algorithms #Robotics and Sensor-Based Localization #cs.CV
paper · pdf · doi:10.48550/arxiv.1505.06319
Presented at OAGM Workshop, 2015 (arXiv:1505.01065)
arxiv created 2015/05/23 · openalex publication_date 2015/05/23 · arxiv updated 2015/05/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In computer vision, we have the problem of creating graphs out of unstructured point-sets, i.e. the data graph. A common approach for this problem consists of building a triangulation which might not always lead to the best solution. Small changes in the location of the points might generate graphs with unstable configurations and the topology of the graph could change significantly. After building the data-graph, one could apply Graph Matching techniques to register the original point-sets. In this paper, we propose a data graph technique based on the Minimum Spanning Tree of Maximum Entropty (MSTME). We aim at a data graph construction which could be more stable than the Delaunay triangulation with respect to small variations in the neighborhood of points. Our technique aims at creating data graphs which could help the point-set registration process. We propose an algorithm with a single free parameter that weighs the importance between the total weight cost and the entropy of the current spanning tree. We compare our algorithm on a number of different databases with the Delaunay triangulation.