The Graph Labeling Model and Its Application to the Problem of Edge Linking in Computer Vision.
Marc David. Diamond · Deep Blue (University of Michigan) · 1986
This thesis addresses the problem in computer vision of deriving continuous contours from a primitive feature map, or primal sketch, a process often referred to as edge linking. The objective of this work has been to develop new edge linking algorithms, with a focus on how those algorithms might be implemented on a multiprocessor (SIMD or MIMD) architecture. The need for dramatic improvements in execution speeds for real time applications motivates the research into the use of parallelism to solve this problem. Past approaches to edge linking have fallen into two categories, those based on dynamic programming or graph searching, and those based on the so-called "relaxation labeling processes." Approaches based on dynamic programming have performed well in linking edges to form continuous contours, but cannot readily be implemented on existing parallel architectures. Approaches based on the relaxation labeling processes are ideally suited for massively parallel architectures but their ability to link edges has shown to be very poor. The approach developed here, based on a graph labeling model, achieves the edge linking performance of the graph searching approaches and yet has an efficient realization on a multiprocessor architecture. In the graph labeling approach, primitive features, or scene events are assigned to each pixel in the image, subject to pair wise constraints which guarantee that line segments are not broken at pixel boundaries. The problem is represented as a linear program in 0-1 integer variables. Powerful results from the theory of the vertex and set packing problems are adapted to the graph labeling model. The result is a scheme for dynamically decomposing the edge linking process into independent subproblems that, therefore, can be addressed on separate processors. Results of the application of the graph labeling model to several real world images are given. Although the focus here has been on a problem in computer vision, the algorithms that have been developed, along with the treatment of the theoretical properties of the graph labeling problem have ramifications for a wide range of topics in artificial intelligence to which graph labeling models apply.