Visual information retrieval systems are often constructed upon the notion of image similarity. The concept of image similarity may be defined in many ways: from a pure visual level, where we seek identical images, to a semantic level related with human perception the image. In our research we address the first approach, we explore topics of image matching (image alignment), however in terms of image fragments. The goal of image fragment matching is to find similar parts of two images, without a given model of particular objects present on images. It is also assumed that the number of similar objects (image fragments) is not known. In this paper we present a novel method for image fragment matching. It uses two ellipse pairs as an elementary object for image geometry reconstruction. The method is an extension of the previously proposed approach based on triangles. We have decided to replace triangles with a different geometrical structure to reduce computational complexity from O(n3) to O(n2), where n is the number of coherent key regions. We discuss and compare both matching methods both in terms of quality and processing efficiency.