Introduction
Illumination variation remains a fundamental challenge in computer vision. A single object, such as a human face, can exhibit drastically different appearances depending on the direction and intensity of light. While classical models for convex Lambertian objects—like the 9D spherical harmonic subspace—capture the majority of energy on average, they often fail for real-world, non-convex objects. These objects possess complex geometries that create sharp shadows and self-occlusions, breaking simple linear assumptions. This paper introduces the first rigorous theoretical framework to provide guarantees for modeling light interaction with non-convex objects, even in worst-case lighting scenarios.
Sampling with Theoretical Guarantees
The authors represent the set of all possible images of an object under varying light as a "convex cone." To approximate this cone effectively, they derive a novel perturbation bound that quantifies how much an image changes as the light source moves. This bound is intrinsically linked to the object's geometry, specifically its "ambient visibility" (how much of the sky a surface point can see) and "gnomon length" (the length of shadow-casting edges).
By establishing these geometric metrics, the researchers can calculate the exact sampling density required to ensure that any valid image of the object is within a specified distance of a sampled image. This shift from average-case performance to worst-case guarantees is critical for high-stakes applications like security and biometric verification.
Cone-Preserving Complexity Reduction
While the theoretical sampling density can lead to an astronomical number of images, the authors propose a method to compress these models without sacrificing their accuracy guarantees. They introduce a Cone-Preserving Complexity Reduction framework that decomposes the image set into a low-rank component for smooth variations and a sparse component for sharp shadows.
Unlike standard Robust PCA, this formulation includes a constraint to minimize the Hausdorff distance between the original high-dimensional cone and the compressed polyhedral model. This optimization is solved using the Linearized Alternating Direction Method of Multipliers (L-ADMM), resulting in models that are over 90% smaller while maintaining rigorous performance bounds.
Key Results and Insights
Numerical experiments on synthetic models (Vase, Face, and Bunny) and the Yale Face Database B validated the tightness of the derived perturbation bounds. Key findings include:
- Superior Verification: The proposed guaranteed models (C1 and C2) achieved near-perfect ROC curves in object verification tasks, significantly outperforming 9D subspaces and feature-based methods like HOG and LBP under extreme lighting.
- Geometric Complexity: The difficulty of modeling an object is shown to be a direct function of its non-convexity. Objects with lower minimum visibility and longer shadow-casting edges require denser sampling.
- Shadow Sparsity: The success of the compression stage relies on the insight that while shadows are complex, the pixel-wise difference they introduce is often sparse relative to the overall image.
Conclusion
This work provides a robust mathematical foundation for illumination modeling that extends beyond the limitations of convex assumptions. By quantifying the relationship between geometry and light, the authors enable the creation of compressed models with provable accuracy. Future work aims to address the "curse of small epsilon"—the high sample count required for extremely low error rates—and to integrate pose variation into these guaranteed frameworks.
Summary updated