Computing That Serves

Scalable Recognition with a Vocabulary Tree and Using Galois Theory to Prove that Structure from Motion Algorithms are Optimal


Thursday, February 1, 2007 - 11:00am


David Nister, Department of Computer Science, University of Kentucky

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.


 David Nister received the MSc degree in computer science and engineering in 1997 and the Licentiate of Engineering degree in 1998, both from Chalmers University of Technology, Gothenburg, Sweden. In 2001 he received the PhD degree in computer vision, numerical analysis and computing science from the Royal Institute of Technology (KTH), Stockholm, Sweden, with the thesis 'Automatic Dense Reconstruction from Uncalibrated Video Sequences'. He is currently an assistant professor at the Computer Science Department and the Center for Visualization and Virtual Environments at the University of Kentucky. He was previously a researcher in the Vision Technologies Laboratory, Sarnoff Corporation, Princeton. He is the recipient of an NSF CAREER Award 2006, for Structure from Recognition, Building Visual Worlds, and a PI for the DARPA Urbanscape project on 3D Reconstruction from Video. He is a co-chair for a work group of the International Society for Photogrammetry and Remote Sensing (ISPRS), on the editorial board for the Journal of Field Robotics and an area-chair for CVPR 2006, CVPR 2007 and ECCV 2008.