The minimum spanning tree of maximum entropy

In computer vision, we have the problem of creating graphsout of unstructured point-sets, i.e. the data graph. A common approachfor this problem consists of building a triangulation which might not al-ways lead to the best solution. Small changes in the location of the pointsmight generate graphs with unstable configurations and the topology ofthe graph could change significantly. After building the data-graph, onecould apply Graph Matching techniques to register the original point-sets.In this paper, we propose a data graph technique based on the MinimumSpanning Tree of Maximum Entropty (MSTME). We aim at a data graphconstruction which could be more stable than the Delaunay triangula-tion with respect to small variations in the neighborhood of points. Ourtechnique aims at creating data graphs which could help the point-set reg-istration process. We propose an algorithm with a single free parameterthat weighs the importance between the total weight cost and the entropyof the current spanning tree. We compare our algorithm on a number ofdifferent databases with the Delaunay triangulation.