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.
Our cost function is built upon a Minimum Spanning Tree formulation and entropy maximization. In this sense, our work is closely related to @cite_9 as the authors also formulate an optimization problem focusing on the entropy of a Minimum Spanning Tree. However, they are dealing with a different problem by proposing an entropy estimator for clustering. In our work, we are interested on the data graph construction problem and our cost function differs from theirs since our entropy is calculated on the degree distribution of the generated MST while they estimate the data entropy based on the length of the spanning tree. Our problem can also be seen as a bi-criteria optimization problem. proposed a Lagrangian relaxation to solve the constrained minimum spanning tree problem, which is also a bi-criteria optimization proven to be NP-Hard by . Neighborhood search and adjacency search heuristics for the bicriterion minimum spanning tree problem were proposed by .
@cite_9
1576317141
Given an undirected graph with two different nonnegative costs associated with every edge e (say, w e for the weight and l e for the length of edge e) and a budget L, consider the problem of finding a spanning tree of total edge length at most L and minimum total weight under this restriction. This constrained minimum spanning tree problem is weakly NP-hard. We present a polynomial-time approximation scheme for this problem. This algorithm always produces a spanning tree of total length at most (1 + e)L and of total weight at most that of any spanning tree of total length at most L, for any fixed e >0. The algorithm uses Lagrangean relaxation, and exploits adjacency relations for matroids.