Pushbroom Stereo for High-Speed Navigation in Cluttered Environments

Andrew J. Barry, Russ Tedrake

Abstract

We present a novel stereo vision algorithm that is capable of obstacle detection on a mobile-CPU processor at 120 frames per second. Our system performs a subset of standard block-matching stereo processing, searching only for obstacles at a single depth. By using an onboard IMU and state-estimator, we can recover the position of obstacles at all other depths, building and updating a full depth-map at framerate. Here, we describe both the algorithm and our implementation on a high-speed, small UAV, flying at over 20 MPH (9 m/s) close to obstacles. The system requires no external sensing or computation and is, to the best of our knowledge, the first high-framerate stereo detection system running onboard a small UAV.

Introduction

Small Unmanned Aerial Vehicles (UAVs) face a significant "speed-sensing" paradox. To navigate safely through complex environments like forests at high speeds (exceeding 9 m/s), they require high-framerate depth sensing. However, traditional stereo vision—calculating depth by comparing two camera images—is computationally intensive. Most mobile stereo systems struggle to exceed 30 Hz because they attempt to calculate distance for every pixel across numerous depth planes. For lightweight drones (under 2kg), carrying the GPUs or high-power processors necessary for such computation is impractical. This work bridges the gap between lightweight hardware and the high-speed processing required for aggressive flight.

Methods: The Pushbroom Stereo Algorithm

The core innovation is the Pushbroom Stereo algorithm. Instead of a full search across many disparities, the system searches for matches at only one specific distance (e.g., 4.8 meters).

Single-Disparity Search and Temporal Integration

The algorithm performs block-matching using Sum of Absolute Differences (SAD) for a single disparity. This drastically reduces the search space, enabling 120 FPS performance on a standard ARM CPU. As the aircraft moves forward, this single "detection plane" sweeps through space like a broom, a concept illustrated in Figure 1.

The Pushbroom Stereo concept: forward motion sweeps a single detection plane through space.

By integrating data from an onboard Inertial Measurement Unit (IMU) and a Pitot tube for airspeed, the system tracks the drone's movement. It "remembers" obstacle locations detected at the fixed distance and reprojects them into a 3D point cloud as the drone approaches.

Robustness Filtering

To mitigate false positives, a Laplacian edge filter ensures matching occurs only in regions with sufficient texture. Additionally, a "horizontal invariance filter" prevents the system from being misled by repeating horizontal patterns, such as the horizon or window slats.

Results and Flight Performance

The system was evaluated using a ground dataset of 23,000 frames and real-world flight tests with a modified "Team Black Sheep Caipirinha" delta-wing drone.

Onboard view showing real-time obstacle detection (red dots and blue boxes) on a goalpost during high-speed flight.

Key findings include:

  • Throughput: The system consistently achieved 120 FPS, approximately 4x faster than traditional mobile stereo implementations.
  • Accuracy: 92.6% of detections were within 1.0 meter of results from a full-depth OpenCV baseline.
  • Flight Capability: During flights at speeds up to 9 m/s, the system successfully detected obstacles like goalposts in real-time, providing a robust 3D point cloud for navigation.
  • Low Latency: At 120 FPS, the drone covers only ~7.5 cm between frames, allowing for extremely fine-grained map updates.

Discussion and Future Work

While highly efficient, the algorithm relies on forward motion to build a complete map; it cannot "sweep" the detection plane while hovering or moving laterally. The heavy thresholding used to avoid false positives may also miss thin obstacles (e.g., power lines) or low-texture objects. Future work includes expanding the search to multiple specific depths as mobile CPUs improve and integrating this sensing into a fully autonomous, closed-loop flight controller.

Summary updated

Abstract

We present a novel stereo vision algorithm that is capable of obstacle detection on a mobile-CPU processor at 120 frames per second. Our system performs a subset of standard block-matching stereo processing, searching only for obstacles at a single depth. By using an onboard IMU and state-estimator, we can recover the position of obstacles at all other depths, building and updating a full depth-map at framerate. Here, we describe both the algorithm and our implementation on a high-speed, small UAV, flying at over 20 MPH (9 m/s) close to obstacles. The system requires no external sensing or computation and is, to the best of our knowledge, the first high-framerate stereo detection system running onboard a small UAV.
BibTeX
@inproceedings{barry2015pushbroom,
  author = {Andrew J. Barry and Russ Tedrake},
  title = {{Pushbroom Stereo for High-Speed Navigation in Cluttered Environments}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2015},
  url = {https://openreview.net/forum?id=rCFYxUmwJb},
}

Loading related content...

Figure