Abstract Problems in machine vision that are posed as variational principles or partial differential equations can often be solved by local, iterative, and parallel algorithms. A disadvantage of these algorithms is that they are inefficient at propagating constraints across large visual representations. Application of multigrid methods has overcome this drawback with regard to the computation of visible-surface representations. We argue that our multiresolution approach has wide applicability in vision. In particular, we describe efficient multiresolution iterative algorithms for computing lightness, shape-from-shading, and optical flow, and evaluate the performance of these algorithms using synthesized images.
Introduction
Many fundamental problems in computer vision—such as determining the true reflectance of a surface (lightness), reconstructing 3D shapes from shading, or tracking motion (optical flow)—are formulated as variational principles or Partial Differential Equations (PDEs). While these formulations are mathematically elegant, they are historically computationally expensive.
Standard iterative algorithms, such as Jacobi or Gauss-Seidel relaxation, update pixel values based solely on their immediate neighbors. This local nature means that information about global properties propagates through the image grid at a very slow pace. For high-resolution images, these algorithms become practically unusable due to this "computational sluggishness." This paper demonstrates that these bottlenecks can be overcome by adopting multigrid (multiresolution) methods.
Multiresolution Methodology
The core innovation is the adaptation of multigrid methods to vision problems. Instead of performing computations on a single high-resolution grid, the algorithm maintains a hierarchy of grids at different spatial scales. This allows global constraints to be resolved on coarser grids where they can "travel" across the image in far fewer iterations, before being refined on higher-resolution grids.
The multiresolution framework relies on four key components:
- Intra-level Relaxation: Standard iterative smoothing performed within a single resolution level to resolve local details.
- Prolongation (Coarse-to-Fine): Using bilinear interpolation to transfer a rough solution from a coarse grid to a finer one, providing a high-quality starting guess for higher-resolution iterations.
- Restriction (Fine-to-Coarse): Averaging or injecting values from a fine grid to a coarser one to improve the accuracy of the coarse representation.
- Recursive Coordination: An adaptive strategy that moves between levels to ensure the entire hierarchy works together efficiently.
Applications and Evaluation
The author applies this framework to three specific mathematical models using synthetically generated images to ensure ground-truth comparison:
- The Lightness Problem: Solving Poisson’s equation to separate illumination gradients from actual surface reflectance using "Synthetic Mondrians."
- Shape-From-Shading: Solving coupled PDEs to recover surface orientation using a smoothness constraint, tested on Lambertian spheres.
- Optical Flow: Minimizing a functional that balances the brightness constancy of moving objects with a global smoothness constraint, tested on expanding spheres.
Experiments were typically conducted at a maximum resolution of 129 x 129 pixels, utilizing a four-level hierarchy (129x129, 65x65, 33x33, and 17x17).
Key Results
To compare algorithms across different resolutions fairly, the paper utilizes "work units"—defined as the amount of computation required for one iteration on the finest grid. The multiresolution algorithms outperformed single-level versions by massive margins:
| Problem | Multigrid (Work Units) | Single-Level (Work Units) | Speedup |
|---|---|---|---|
| Lightness | 33.97 | ~500 | ~15x |
| Shape-From-Shading | 6.125 | 200 | ~32x |
| Optical Flow | 4.938 | 37 | ~7.5x |
Discussion and Conclusion
The results confirm that the slow convergence of single-grid methods is primarily a communication problem. By allowing pixels to represent larger areas on coarse grids, global constraints are satisfied much faster.
However, the paper notes several challenges for future work. The accuracy of these methods is highly sensitive to boundary conditions and the handling of discontinuities (such as occluding edges). While the author suggests marking these discontinuities to prevent the smoothness constraint from blurring sharp edges, integrating this automatically remains a complex task. Despite these implementation complexities, the multigrid approach serves as a powerful meta-algorithm applicable to nearly any vision task posed as a variational optimization.
Summary updated