Introduction to the special section on graph algorithms in computer vision
Sven Dickinson, Marcello Pelillo, Ramin Zabih · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2001
N a letter to C. Huygens of 1679, G.W. Leibniz expressed his dissatisfaction with the standard coordinate treatment of geometric figures and maintained that we need yet another kind of analysis, geometric or linear, which deals directly with position, as algebra deals with magnitude (1). In fact, Leibniz initiated the study of the so-called geometry of positions (geometria situs) which, as L. Euler clearly put it in his famous 1736 Konigsberg bridges paper which had to mark the beginning of graph theory, concerned only with the determination of position, and its properties; it does not involve measurements nor calculations made with them (2). After about two centuries, this study developed into two of the richest branches of modern mathematics: graph theory and combinatorial topology. Mutatis mutandis, an analogous discontent is nowadays being felt among many researchers working in computer vision, a field that is currently dominated by purely geometric methods, who are increasingly making use of sophisticated graph-theoretic concepts, results, and algorithms. Indeed, graphs have long been an important tool in computer vision, especially because of their representational power and flexibility. However, there is now a renewed and growing interest toward explicitly formulating computer vision problems as graph problems. This is particularly advanta- geous because it allows vision problems to be cast in a pure, abstract setting with solid theoretical underpinnings and also permits access to the full arsenal of graph algorithms developed in computer science and operations research. Graph-theoretic problems which have proven to be relevant to computer vision include maximum flow, minimum spanning tree, maximum clique, shortest path, maximal common subtree/subgraph, etc. In addition, a number of fundamental techniques that were designed in the graph algorithms community have recently been applied to computer vision problems. Examples include spectral