The automatic detection of planes in depth images plays an important role in computer vision. Plane detection from unorganized point clouds usually requires complex data structures to pre-organize the points. On the other hand, existing detection approaches tailored to depth images use the structure of the image and the 2.5-D projection of the scene to simplify the task. However, they are sensitive to noise and to discontinuities caused by occlusion. We present a real-time deterministic technique for plane detection in depth images that uses an implicit quadtree to identify clusters of approximately coplanar points in the 2.5-D space. The detection is performed by an efficient Hough-transform voting scheme that models the uncertainty associated with the best-fitting plane with respect to each cluster as a Gaussian distribution. Experiments shows that our approach is fast, scalable, and robust even in the presence of noise, partial occlusion, and discontinuities.