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.