locations—even while they’re inadequate for 3D reconstructions on their own. Google Earth offers an additional way to add handcrafted 3D models to its terrains through the Google SketchUp program—a feature appropriate for both existing and historical buildings. One unusually extensive SketchUp initiative placed recreations of more than 6,000 ancient Roman buildings in their original positions in Rome.

Another consumer-level phenomenon that contributes to high-end 3D modeling is crowdsourced photos, available through such sources as the photo-sharing Web site Flickr. That was the basis for a reconstruction of present-day Rome, led by Sameer Agarwal, an acting assistant professor of computer science and engineering at the University of Washington, and described in the paper “Building Rome in a Day.” Agarwal and colleagues selected 150,000 photos from more than two-and-a-half million returned from a Flickr.com search for “Rome” and “Roma,” and applied existing Structure from Motion techniques to meld multiple views of the same structure into a unified 3D model. Central to this project—and to most others that agglomerate photos—is a feature detector that recognizes image elements. This project uses the popular Scale-Invariant Feature Transform algorithm; others include Speeded Up Robust Features and Maximally Stable Extremal Regions.

The Bayan temple
project measured
the entire site to
a resolution of at
least one centimeter.

The Rome project was unusual in its scale, and the University of Washington team used a variety of existing and novel approaches to match photos, place them in relation to each other, and ultimately meld them back together into a consistent geometry. The latter steps led to two innovations. First, the team computationally reduced the number of photographs to a “skeletal set” to simplify and confirm site geometry; second, newly developed software optimized the results over a distributed parallel network of about 500 cores. The result was a completion time, from photo matching to reconstruction, of less than 22 hours. Previous techniques would have taken more than 11 days to complete just the photo-matching process.

Much of the work on this project, and the Photo Tourism project by three of the same researchers, led to production of the consumer-level program Microsoft Photosynth and an open-source

version, Bundler. According to Microsoft Partner Architect Blaise Aguera y Arcas, approximately 16% of recent, user-contributed Photosynth mosaics are of artwork or heritage-related sites.

The photographed environment for the Rome project was fairly static. Many of the sites were of long-standing structures, and nearly all photos were taken in the five years since the launch of Flickr. But 3D modeling techniques can also enhance historic photographs, as the paper “Inferring Temporal Order of Images from 3D Structure,” by Grant Schindler, a Ph.D. candidate at the Georgia Institute of Technology, and colleagues, demonstrated with the use of a collection of 212 photos of downtown Atlanta taken over a period of 144 years. 3D analysis of the photos determined structure locations and then, based on the pattern of buildings appearing and disappearing, a constraint-satisfaction algorithm put them in the correct order. (An interactive applet at http://4d-cities.cc.gatech. edu/atlanta/ enables people to “time travel” through the images.)

 

laser scanning and Photometry Photo-based modeling’s big advantage is that many people can create its source material. But it has its failings, most notably when trying to coordinate photo collections that depict large blank spaces. Depth information is mostly interpolated from multiple views of the

Milestones
Feng Kang Prize and Other CS Awards

tai Xue-Cheng, Manindra Agrawal, Raj Jain, and Anurag Kumar were recently honored for their contributions to computer science.

fenG kAnG PRize tai Xue-Cheng, an associate professor at nanyang technological University’s school of physical and Mathematical sciences, was awarded the eighth Feng Kang prize in scientific Computing. Xue-Cheng’s research involves numerical analysis and computational mathematics, in particular image processing.

His mathematical modeling has
been used to restore degraded
images to their original look.
Xue-Cheng has also developed
new models for MRi medical
image processing and
other medical and industrial
applications.

G.D. BiRlA AWARD Manindra Agrawal, a professor at the indian institute of technology at Kanpur’s department of computer science and engineering, was awarded the 2009 G.D. Birla Award for scientific Research for his pioneering research in

the theories of computation and algorithms. the award honors high-caliber scientific accomplishments of indian scientists, preferably below the age of 50. A co-winner of the 2006 Gödel prize, Agrawal’s accomplishments include the first deterministic algorithm to test an n-digit number for primality in a time that has been proven to be polynomial in n.

cDAc-Accs
founDATion AWARD
the Center for Development of
Advanced Computing (CDAC)
and the Advanced Computing

and Communications society (ACCs) jointly presented the 2009 CDAC-ACCs Foundation Award to Raj Jain, professor of computer and engineering at washington University in st. Louis’s school of engineering and Applied science, for his role in influencing the growth and impact of networking technology and to Anurag Kumar, professor and chairman of the department of electrical communication at the indian institute of science at Bangalore, for his contributions to the analysis, optimization, and control techniques in communication networks.