Covering the space of tilts. Application to affine invariant image comparison

We propose a mathematical method to analyze the numerous algorithms performing image matching by affine simulation (IMAS). To become affine invariant they apply a discrete set of affine transforms to the images, prior to the comparison of all images by a scale invariant image matching (SIIM), like SIFT (scale invariant feature transform). Obviously this multiplication of images to be compared increases the image matching complexity. Three questions arise: (a) what is the best set of affine transforms to apply to each image to gain full practical affine invariance? (b) what is the lowest attainable complexity for the resulting method? (c) how is the underlying SIIM method chosen? We provide an explicit answer and a mathematical proof of quasi-optimality of the solution to the _rst question. As an answer to (b) we find that the near-optimal complexity ratio between full affine matching and scale invariant matching is more than halved, compared to the current IMAS methods. This means that the number of key points necessary for affine matching can be halved, and that the matching complexity is divided by four for exactly the same performance. This also means that an affine invariant set of descriptors can be associated with any image. The price to pay for full affine invariance is that the cardinality of this set is around 6.4 times larger than for a SIIM.