In this paper, we address the problem of fast and accurate extraction of points that correspond to the same location (named tie-points) from pairs of large-sized images. First, we conduct a theoretical analysis of the performance of the full-image matching approach, demonstrating its limitations when applied to large images. Subsequently, we introduce a novel technique to impose spatial constraints on the matching process without employing subsampled versions of the reference and the target image, which we name coupled image decomposition. This technique splits images into corresponding subimages through a process that is theoretically invariant to geometric transformations, additive noise, and global radiometric differences, as well as being robust to local changes. After presenting it, we demonstrate how coupled image decomposition can be used both for image registration and for automatic estimation of epipolar geometry. Finally, coupled image decomposition is tested on a data set consisting of several planetary images of different size, varying from less than one megapixel to several hundreds of megapixels. The reported experimental results, which includes comparison with full-image matching and state-of-the-art techniques, demonstrate the substantial computational cost reduction that can be achieved when matching large images through coupled decomposition, without at the same time compromising the overall matching accuracy.