A method for face detection includes capturing a depth map and an image of a scene and selecting one or more locations in the image to test for presence of human faces. At each selected location, a respective face detection window is defined, having a size that is scaled according to a depth coordinate of the location that is indicated by the depth map. Apart of the image that is contained within each face detection window is processed to determine whether the face detection window contains a human face. Similar methods may also be applied in identifying other object types.