A graph centrality approach to computer vision

Abstract

Computer vision has changed the way we deal with computers, since the first automatic facial detection to the latest augmented reality application. The study of social networks models relations using graph theory and has been emerging in recent years. This field designs the concept of centrality by defining how important a certain node is within a network. In this dissertation, we study the centrality concept applied to computer vision. We start by analyzing the point-set registration problem which arises whenever one needs to match information in images. The kind of information to be matched consists of feature locations, landmarks, or points representing a surface of an object. We propose our own centrality-oriented matching algorithm focusing on the generation of a distinguishable data-graph. In this second problem, we pose our data-graph generation using an optimization formulation whose goal is to maximize the entropy of the degree centrality while minimizing the cost of the edges. Later, we constrain this problem into generating a tree for robustness. We evaluate the robustness of the generated data-graph in the presence of differing amounts of noise in the local neighborhood of points. The last aspect studied in this dissertation is the impact of centrality in a machine learning scenario. We train learning algorithms using centrality-based features focusing on the classification of shapes. We evaluate our approach by perturbing the topology of the graph. In this dissertation, we study the behavior of centrality in the vision problems and estimate when a certain centrality measure can perform better than another according to their properties.