The Minimum Spanning Tree of Maximum Entropy
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.
Code (0)
등록된 구현이 없습니다.
Tasks
graph constructionGraph MatchingSimilar Papers 제목 키워드 기반
Efficient Learning of Optimal Markov Network Topology with k-Tree Modeling
The seminal work of Chow and Liu (1968) shows that approximation of a finite probabilistic system by Markov trees can achieve the minimum information loss with the topology of a maximum spanning tree. Our current paper g…
A gentle tutorial and a structured reformulation of Bock's algorithm for minimum directed spanning trees
This paper presents a gentle tutorial and a structured reformulation of Bock's 1971 Algol procedure for constructing minimum directed spanning trees. Our aim is to make the original algorithm readable and reproducible fo…
Dependency ParsingGraph-Based Parallel Large Scale Structure from Motion
While Structure from Motion (SfM) achieves great success in 3D reconstruction, it still meets challenges on large scale scenes. In this work, large scale SfM is deemed as a graph problem, and we tackle it in a divide-and…
3D ReconstructionClusteringSimulated Annealing is a Polynomial-Time Approximation Scheme for the Minimum Spanning Tree Problem
We prove that Simulated Annealing with an appropriate cooling schedule computes arbitrarily tight constant-factor approximations to the minimum spanning tree problem in polynomial time. This result was conjectured by Weg…
The Central Spanning Tree Problem
Spanning trees are an important primitive in many data analysis tasks, when a data set needs to be summarized in terms of its "skeleton", or when a tree-shaped graph over all observations is required for downstream proce…