An image localization system receives an image of a scene and generates a depth map for the image by inputting the image to a model trained for generating depth maps for images. The system determines surface normal vectors for the pixels in the depth map. The system clusters the surface normal vectors to identify regions in the image corresponding to planar surfaces. The system partitions the image into patches, each of which is a region of connected pixels in the image and corresponds to a cluster of surface normal vectors. The system rectifies the perspective distortion of patches and extracts perspective corrected features from the rectified patches. The system matches the perspective corrected features of the image with perspective corrected features of other images for three-dimensional re-localization.