This paper proposes a hybridization of two well-known stereo-based obstacle detection techniques for all-terrain environments. While one of the techniques is employed for the detection of large obstacles, the other is used for the detection of small ones. This combination of techniques opportunistically exploits their complementary properties to reduce computation and improve detection accuracy. Being particularly computation intensive and prone to generate a high false-positive rate in the face of noisy three-dimensional point clouds, the technique for small obstacle detection is further extended in two directions. The goal of the first extension is to reduce both problems by focusing the detection on those regions of the visual field that detach more from the background and, consequently, are more likely to contain an obstacle. This is attained by means of spatially varying the data density of the input images according to their visual saliency. The second extension refers to the use of a novel voting mechanism, which further improves robustness. Extensive experimental results confirm the ability of the proposed method to robustly detect obstacles up to a range of 20 m on uneven terrain. Moreover, the model runs at 5 Hz on 640 � 480 stereo images.