The goal of this project is to investigate tractable approaches to large-scale correspondence problems in computer vision and robotics. Correspondence is a central problem in many vision and robotics applications, and the proposed research centers on three of those: large-scale 3D reconstruction from digital imagery in space and time, simultaneous localization and mapping using mobile robots, and tracking large numbers of visually similar objects, such as ants in an ant-hill or people in a crowd. To eclipse existing state of the art methods, this proposal aims to investigate approximate inference through Markov chain Monte Carlo (MCMC) sampling. MCMC provides an approximate solution for an otherwise intractable problem, and has a number of attractive advantages with respect to other approaches. In addition, practical insights gained in applying MCMC to this problem can cross-pollinate other fields and spawn new theoretical investigations. In terms of broader impact, this project's integrated research and education plan will help produce a next generation of researchers, intimately familiar with these new methods first discovered in statistical mechanics. In addition, the project has a strong outreach component through museum exhibits and interaction with local high schools. Taking a longer view, the proposed research will enable novel and large-scale applications of computer vision and robotics that are expected to have far-reaching implications for society. Robots are on the verge of playing a much larger role in our lives, as evidenced for example by the increasingly popular consumer robots now available. More immediately, the advent of cheap digital photography and video is exponentially increasing the volume of digital imagery that can be used, analyzed, and re-synthesized in new and creative ways. The correspondence problem lies at the heart of many of these novel uses.
