Digital images are an increasingly ubiquitous source of information, but they capture only a 2D view of the world. For many applications a 3D model is needed, be it a model of a city, a water catchment, or as a basis for integrating other data sets. Advances in computer vision have made it possible to reconstruct 3D models from sets of 2D images, but as our ability to capture large numbers of high resolution images increases we are faced with a computational challenge: How can we process very large numbers of images to create accurate 3D models? In addition, we want to utilise non-conventional processing units, such as graphics processing units (GPUs). This raises a more general research question: How can we map large, semi-structured problems to heterogeneous distributed computing resources?
We have identified three phases in the computation of 3D models from sets of images: individual image processing; local processing (typically pairwise feature matching); and global bundle adjustment, a large numeric optimisation task with a sparse structure that emerges from the local connectivity.
We have started to study these phases and to create algorithms to distribute this problem over a cluster of computation nodes such as the New Zealand eScience Infrastructure infrastructure. We are also investigating the application of heterogeneous computing, including mixes of CPUs and GPUs to these tasks. This raises a number of issues, including trade-offs between computation and communication; scheduling tasks between processors; and adapting algorithms for very different computing architectures.
Our initial results indicate that, at least for the first two stages of processing, this task can be effectively distributed across clusters of heterogeneous computers. Communication costs can be reduced by graph-based optimisations; dynamic task scheduling can ensure effective use of resources; and GPU-based algorithms have been developed that are of similar speed to multi-core CPU approaches.