2015 | OriginalPaper | Chapter
Data Graph Formulation as the Minimum-Weight Maximum-Entropy Problem
Authors : Samuel de Sousa, Walter G. Kropatsch
Published in: Graph-Based Representations in Pattern Recognition
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Consider a point-set coming from an object which was sampled using a digital sensor (depth range, camera, etc). We are interested in finding a graph that would represent that point-set according to some properties. Such a representation would allow us to match two objects (graphs) by exploiting topological properties instead of solely relying on geometrical properties. The Delaunay triangulation is a common out off-the-shelf strategy to triangulate a point-set and it is used by many researchers as the standard way to create the so called data-graph and despite its positive properties, there are also some drawbacks. We are interested in generating a graph with the following properties: the graph is (i) as unique as possible, (ii) and as discriminative as possible regarding the degree distribution. We pose a combinatorial optimization problem (Min-Weight Max-Entropy Problem) to build such a graph by minimizing the total weight cost of the edges and at the same time maximizing the entropy of the degree distribution. Our optimization approach is based on Dynamic Programming (DP) and yields a polynomial time algorithm.