Efficient Selection of Disambiguating Actions for Stereo Vision

Monika Schaeffer, Ronald ParrUAI 2006 · OpenReview

Abstract: In many domains that involve the use of sensors, such as robotics or sensor networks, there are opportunities to use some form of active sensing to disambiguate data from noisy or unreliable sensors. These disambiguating actions typically take time and expend energy. One way to choose the next disambiguating action is to select the action with the greatest expected entropy reduction, or information gain. In this work, we consider active sensing in aid of stereo vision for robotics. Stereo vision is a powerful sensing technique for mobile robots, but it can fail in scenes that lack strong texture. In such cases, a structured light source, such as vertical laser line can be used for disambiguation. By treating the stereo matching problem as a specially structured HMM-like graphical model, we demonstrate that for a scan line with $n$ columns and maximum stereo disparity $d$, the entropy minimizing aim point for the laser can be selected in $O(nd)$ time—cost no greater than the stereo algorithm itself. In contrast, a typical HMM formulation would suggest at least $O(nd^2)$ time for the entropy calculation alone.

The Challenge of Textureless Surfaces

Stereo vision works by finding matching pixels between two cameras to calculate depth via triangulation. This works effectively on surfaces with high visual detail, such as brick walls or gravel paths. However, it fails significantly on "textureless" surfaces like blank white walls or smooth floors. Without distinct visual features, the algorithm cannot determine which pixel in the left image corresponds to which in the right, leading to massive "holes" or errors in the robot's spatial awareness.

The stereo matching process: (a, b) scanlines, (c) the resulting Disparity Space Image (DSI), and (d) the shortest path representing the depth estimate.

While one could sweep a laser across the entire room to add texture, this is slow, power-hungry, and far from efficient. The core challenge addressed in this work is: If you can only project one laser line at a time, where should you aim it to learn the most about the scene? Traditionally, calculating this "Information Gain" is computationally expensive ($O(nd^2)$), making it too slow for real-time robotics.

Methodology: Stereo as a Graphical Model

The researchers bridge the gap between computer vision and information theory using two key steps:

  1. Stereo as a Graphical Model: They reformulate the standard "Disparity Space Image" (DSI)—a common tool for stereo matching—into a highly structured Hidden Markov Model (HMM). In this model, the "hidden states" are the possible depth values (disparities) and occlusion states for each pixel.
  2. The $O(nd)$ Efficiency Trick: Standard HMMs require $O(nd^2)$ time to calculate entropy (where $n$ is the number of columns and $d$ is the max disparity). However, because stereo vision has strict physical constraints (like the "ordering constraint"), the state transitions are very sparse. The authors exploit this sparsity to reduce the complexity to $O(nd)$, meaning the overhead for picking the best laser spot is no worse than the cost of the stereo algorithm itself.
The HMM-like graphical model used for stereo matching, where states M, R, and L represent matching, right-occlusion, and left-occlusion.

The system works in a loop: it estimates depth, identifies where it is most "confused" (highest entropy), aims the laser there to create a temporary artificial feature, and then updates its depth estimate with the new, certain data point.

Experimental Evaluation

The authors evaluated their approach using three distinct sources:

  • Synthetic Rendered Scenes: A custom-made 1256x810 image pair of a hallway designed specifically to have large, ambiguous, low-texture surfaces.
  • Middlebury Stereo Benchmarks: Standard computer vision datasets (Tsukuba, Venus, Sawtooth, and Cones) used to compare their "Information Gain" strategy against random laser placement.
  • Physical Prototype: A real-world rig using two DSLR cameras, a computer-controlled pan-tilt head, and a green laser pointer to test the algorithm in a university hallway.

Key Insights and Results

  • Entropy as a Guide: The distribution of all possible paths is more informative than just the lowest-cost path. If many paths have similar costs, the robot is "confused," and that is exactly where the laser should be aimed.
  • Superiority over Randomness: In the "Sawtooth" benchmark, the Information Gain (IG) strategy reduced pixel errors significantly more than random aims (60 errors vs. 217).
  • Real-World Success: In the physical hallway test, just 9 intelligent laser aims were enough to transform a broken, noisy depth map of a blank wall into a much more accurate representation of the scene's geometry.

Conclusion and Future Work

While the current model is "greedy" (picking only the next best move rather than planning a sequence), it effectively resolves large ambiguous regions by "pinning down" certain points, allowing information to propagate horizontally. Future work may involve integrating this into full 3D mapping systems (SLAM) where the robot chooses laser aims to improve its entire 3D world model, or adapting the framework for more modern stereo algorithms like those using Belief Propagation or deep learning.

Summary updated

Abstract

In many domains that involve the use of sensors, such as robotics or sensor networks, there are opportunities to use some form of active sensing to disambiguate data from noisy or unreliable sensors. These disambiguating actions typically take time and expend energy. One way to choose the next disambiguating action is to select the action with the greatest expected entropy reduction, or information gain. In this work, we consider active sensing in aid of stereo vision for robotics. Stereo vision is a powerful sensing technique for mobile robots, but it can fail in scenes that lack strong texture. In such cases, a structured light source, such as vertical laser line can be used for disambiguation. By treating the stereo matching problem as a specially structured HMM-like graphical model, we demonstrate that for a scan line with n columns and maximum stereo disparity d, the entropy minimizing aim point for the laser can be selected in O(nd) time - cost no greater than the stereo algorithm itself. In contrast, a typical HMM formulation would suggest at least O(nd^2) time for the entropy calculation alone.
BibTeX
@inproceedings{schaeffer2006efficient,
  author = {Monika Schaeffer and Ronald Parr},
  title = {{Efficient Selection of Disambiguating Actions for Stereo Vision}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2006},
  url = {https://openreview.net/forum?id=ivo-poNwHB},
}
Figure