A Systematic Approach to Continuous Graph Labeling With Application to Computer Vision

M. D. Diamond, N. Narasimhamurthi, S. GanapathyAAAI 1982

Introduction

In computer vision, labeling image components—such as edges, surfaces, or junctions—is a fundamental task often complicated by sensor noise and data ambiguity. Historically, two divergent approaches dominated the field: discrete graph labeling and continuous relaxation labeling. Discrete methods utilized rigorous "all-or-nothing" constraints (e.g., geometric rules for junctions), which were mathematically sound but fragile in the presence of noise. Conversely, continuous relaxation methods employed "strength measures" (probabilities) and heuristic "compatibility coefficients" to handle noise, yet often lacked a formal definition of consistency.

This paper bridges this gap by proposing a formal "maximum-sum" decision rule. By treating continuous labeling as a global optimization problem—specifically, finding a strictly consistent labeling that maximizes the sum of initial strength measures—the authors move away from heuristic "shades of compatibility" toward a mathematically grounded approach using linear programming.

Methodology

The core of the proposed approach is the reformulation of labeling as a search for a configuration that is both consistent with an underlying discrete constraint network and optimal according to a specific objective function.

The Maximum-Sum Decision Rule

Instead of relying on local iterative updates with arbitrary weights, the goal is to select a labeling where the sum of initial strength measures (representing the confidence of feature detectors) is maximized across the entire graph. This ensures that the final result respects the hard geometric or physical rules of the domain while remaining sensitive to the underlying data.

Global Enhancement and Optimization

The process involves a Global Enhancement Process ($g$), which accumulates evidence across the network to update local labeling values. The authors compare two primary algorithmic strategies for solving this optimization:

  1. Linear Programming (LP): A rigorous approach that treats labeling as a constrained optimization problem, providing high accuracy.
  2. Dynamic Programming (DP): A faster, heuristic approach that propagates data along eight major directions (horizontal, vertical, diagonal), though it does not guarantee perfect consistency.
Block diagram of the global enhancement process ($g$) and local maxima selection ($s$).

Experimental Setup

To evaluate the framework, the researchers utilized a synthetic benchmark consisting of a 16x16 raster grid. In this grid, each vertex represents a pixel adjacent to its eight neighbors. Simple closed curves (polygons) were drawn on the grid to serve as the ground truth.

Synthetic polygons on a 16x16 raster grid used for testing.

To simulate real-world sensor error, "uniformly independently distributed noise" was injected into the initial labeling values. The label set consisted of custom line-segment orientations representing various junctions and edges.

Results and Discussion

The experiments yielded several key insights into the performance of global optimization in vision tasks:

  • LP Superiority: The Linear Programming algorithm successfully reconstructed the original noise-free labeling after six iterations, demonstrating the power of formal optimization.
  • DP Efficiency vs. Accuracy: The Dynamic Programming approach was significantly faster, reaching a fixed point in only two iterations. However, it failed to achieve perfect consistency, leaving residual errors in the final drawing.
  • Binary Consistency: The results support the argument that while evidence (confidence) is continuous, the underlying rules of the world are often discrete. Using these rules as hard constraints in an optimization framework proves more effective than using heuristic "shades of compatibility."

Conclusion

The mapping of graph labeling to Linear Programming represents a significant step toward robust optimization in low-level vision. While LP provides superior results, its computational complexity and the challenges of local implementation (such as resolving "cycling under degeneracy") remain areas for future research. Subsequent work will focus on applying these principles to real-world scenes, moving beyond synthetic noisy grids to derive line drawings from complex visual data.

Summary updated

BibTeX
@inproceedings{diamond1982systematic,
  author = {M. D. Diamond and N. Narasimhamurthi and S. Ganapathy},
  title = {{A Systematic Approach to Continuous Graph Labeling With Application to Computer Vision}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1982},
}

Loading related content...

Figure