FastLCD: Fast Label Coordinate Descent for the Efficient Optimization of 2D Label MRFs

Kangwei Liu, Junge Zhang, Peipei Yang, Kaiqi HuangIJCAI 2016

Introduction

Markov Random Fields (MRFs) are fundamental to computer vision, underpinning tasks such as image matching, stereo reconstruction, and optical flow estimation. These problems often involve assigning a two-dimensional label $(x, y)$ to each pixel—for instance, representing horizontal and vertical displacement. However, as the resolution and search range increase, the label space grows quadratically. Traditional optimization methods like $\alpha$-expansion, which perform an exhaustive search over the label set, become computationally prohibitive, often requiring significant processing time for even moderate label sizes.

To address this "label explosion," researchers from CASIA have developed FastLCD (Fast Label Coordinate Descent). This optimization strategy treats the label space as a coordinate system, allowing for efficient descent along specific axes rather than exhaustive searching.

Methodology: Label Coordinate Descent

The primary innovation of FastLCD is the decomposition of the 2D label search into a series of 1D moves. Instead of evaluating all $m \times n$ possible labels simultaneously, the algorithm performs Label Coordinate Descent (LCD) across three primary directions:

  1. Horizontal and Vertical Moves: The algorithm fixes one coordinate (e.g., the vertical component $y$) and optimizes the other ($x$). This allows pixels to transition to any new label along the chosen axis.
  2. Diagonal Moves: To prevent the optimization from becoming trapped in axis-aligned local minima, FastLCD incorporates diagonal moves where both $x$ and $y$ coordinates are incremented or decremented by the same value.
Visualization of the 2D label space and the coordinate descent moves (horizontal, vertical, and diagonal) employed by FastLCD.

Each move is formulated as a binary sub-problem solved via standard st-mincut graph techniques. For non-submodular energy functions common in real-world vision tasks, FastLCD utilizes an approximate graph construction that reweights edges to satisfy submodularity while maintaining a theoretical upper bound on the energy. This approach reduces the computational complexity per cycle from $O(m \cdot n)$ to $O(m + n)$.

Experimental Results

The performance of FastLCD was evaluated against several state-of-the-art methods, including $\alpha$-expansion, TRWS, and Curve Expansion, using both synthetic data and standard benchmarks like the Middlebury optical flow dataset.

Speed and Scaling

The most significant advantage of FastLCD is its efficiency. On a synthetic dataset with an $81 \times 81$ label space, FastLCD demonstrated a 40x speedup over $\alpha$-expansion and was 22x faster than curve expansion. As shown in the figure below, the runtime of FastLCD scales much more gracefully with increasing label size compared to traditional move-making algorithms.

Runtime comparison between FastLCD and standard move-making algorithms as label size increases.

Quality and Accuracy

Despite the massive reduction in computation, FastLCD does not compromise on accuracy. In optical flow tasks, it consistently achieved energy levels nearly identical to $\alpha$-expansion while running 5 to 8 times faster. Qualitative results on the Middlebury dataset confirm that the resulting flow fields are visually indistinguishable from those produced by more computationally intensive "optimal" methods. Unlike "Curve Expansion," which is limited to convex energy functions, FastLCD’s approximate move strategy allows it to handle arbitrary semimetric functions, making it significantly more versatile.

Conclusion

FastLCD offers a powerful alternative for optimizing MRFs with large 2D label spaces. By exploiting the coordinate structure of the label space, it achieves significant speedups and superior scaling properties. While the method currently finds local minima and uses approximations for non-submodular energies, its performance in practical computer vision tasks makes it a highly effective tool for high-resolution applications. Future work may explore extending this coordinate descent framework to higher-dimensional label spaces.

Summary updated

BibTeX
@inproceedings{liu2016fastlcd,
  author = {Kangwei Liu and Junge Zhang and Peipei Yang and Kaiqi Huang},
  title = {{FastLCD: Fast Label Coordinate Descent for the Efficient Optimization of 2D Label MRFs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure