Aerial vehicles that are equipped with one or more imaging devices may detect obstacles that are small in size, or obstacles that feature colors or textures that are consistent with colors or textures of a landing area, using pairs of images captured by the imaging devices. Disparities between pixels corresponding to points of the landing area that appear within each of a pair of the images may be determined and used to generate a reconstruction of the landing area and a difference image. If either the reconstruction or the difference image indicates the presence of one or more obstacles, a landing operation at the landing area may be aborted or an alternate landing area for the aerial vehicle may be identified accordingly.