We address the problem of matching two pictures of a scene taken from two separate viewpoints and with potentially non-overlapping parts. While the image deformation is non-rigid, it underlies the geometric constraint that at least one part of the scene is rigid. We formulate the problem as a search problem in the Cartesian product of all possible correspondences. In this space, candidate matches vote for geometry hypotheses with a vote weight depending on local image similarity. The voting process can be written as a Radon transform and we present a new scheme for computing it efficiently based on Fourier analysis on the sphere and the rotation group. We show that the maximum of the Radon transform is a very good global similarity metric for images and apply it in the organization of unordered sets of pictures. At the end of the talk we relax the geometry constraint and instead we ask for matching of regions which match and are salient in both images. We maximize a score function that segments jointly two images and matches their spectral embeddings. This results in a global matching score influenced only from salient matched regions.