Part 1:Scalable Recognition with a Vocabulary Tree
A recognition scheme that scales efficiently to a large number of objects is presented. The efficiency and quality is exhibited in a live demonstration that recognizes CD-covers from a database of 50000 images of popular music CD's. The scheme builds upon popular techniques of indexing descriptors extracted from local regions, and is robust to background clutter and occlusion. The local region descriptors are hierarchically quantized in a vocabulary tree. The vocabulary tree allows a larger and more discriminatory vocabulary to be used efficiently, which we show experimentally leads to a dramatic improvement in retrieval quality. The most significant property of the scheme is that the tree directly defines the quantization. The quantization and the indexing are therefore fully integrated, essentially being one and the same.

Part 2: Using Galois Theory to Prove that Structure from Motion Algorithms are Optimal
This talk presents a general method for establishing that a problem can not be solved by a 'machine' that is capable of the standard arithmetic operations, extraction of radicals (that is, m-th roots for any m), as well as extraction of roots of polynomials of degree smaller than n, but no other numerical operations. This results in a type of complexity theory for geometry problems. The method is based on Galois theory. It is applied to two well known structure from motion procedures: five point calibrated relative orientation, which can be realized by solving a tenth degree polynomial, and L_2-optimal two-view triangulation, which can be realized by solving a sixth degree polynomial. It is shown that both these problems have been optimally solved in the sense that neither problem can be solved by even repeated root extraction of polynomials of any lesser degree. This rules out the possibility of undiscovered symmetries in the problems. It also follows that neither of these problems can be solved in closed form.