CS Bits & Bytes is a bi-weekly newsletter highlighting innovative computer science research. It is our hope that you will use CS Bits & Bytes to engage in the multi-faceted world of computer science to become not just a user, but also a creator of technology. Please visit our website at: www.nsf.gov/cise/csbytes/.

December 17, 2012
Volume 2, Issue 8

Building Rome in a Day

Have you ever looked at a site like Flickr, Facebook or Google images, with their billions of photos, and wondered if every corner of the world has been photographed by now?

MUST SEE!

Cryptography Video

Watch Rome be Built in a Day at: http://grail.cs.washington.edu/rome/.

With the explosion of the use of Internet image sites such as Flickr, Facebook, Instagram and others, the number of photos that are publicly available has exploded to over 100 billion. Many of these are of the same location, building or site, and more often than not these are from various perspectives and angles. A single building can have photos taken of it from every angle and from both outside and inside the building. Researchers at the University of Washington, led by Dr. Sameer Agarwal, have combined many of these existing photos to create a 3D model of the building, and even have been able to reconstruct the city of Rome! As Dr. Agarwal states about all of the images from Rome:

"This collection represents an increasingly complete photographic record of the city, capturing every popular site, facade, interior, fountain, sculpture, painting, cafe, and so forth. It also offers us an unprecedented opportunity to richly capture, explore and study the three dimensional shape of the city."

There are several complex challenges in creating a 3D model from thousands of 2D images. The first challenge is matching the hundreds of thousands of photos taken of the same location. Identifying which images are of the same site is a daunting computational task. The second challenge is mapping points between images -image correspondence - in order to create the 3D image. Creating an algorithm that can determine which points of an image correlate to the same specific points on another image is not trivial. These tasks must be repeated many, many times for thousands of photos and points within photos. The computer algorithm then needs to place the points correctly, in the right position and perspective, to create the 3D model.

Rome

Image of the Colosseum in Rome.

The University of Washington team, with the help of NSF funding, has been able to create a computer program that includes a “parallel matching” system that can match massive collections of images very quickly to create 3D reconstructions. The team ran 150,000 images from Flicker.com associated with the tags “Rome” or “Roma” through their matching algorithm, and the images organized themselves into a number of groups that corresponded to major landmarks. In one example, the computer analysis was able to take 2,106 photos of the Colosseum in Rome, map nearly one million points on those images, and reconstruct a 3D image of the Colosseum. Other 3D images reconstructed included Trevi Fountain, the Pantheon, and St. Peter’s Basilica. This computer matching and reconstruction from Rome took a total of 21 computer hours and near 500 computer cores, or central processing units. In addition to Rome, the project reconstructed 3D models of landmarks in Venice, Italy and Dubrovnik, Croatia.

Professor Shafrira Goldwasser

Image of Sameer Agarwal.

Who Thinks of this Stuff?! Dr. Sameer Agarwal studied mathematics in college and computer science in graduate school. He says that this combination of education informs his work every day. The mathematics education taught him the power of abstract thinking, and the joy of finding elegant solutions to problems. The computer science education taught him to be practical, efficient, and to enjoy building systems that work. The two together motivate both his choice of problems, as well as his approach to solving them. "I like working on large-scale problems, which have an interesting mathematical problem at their core," he states.

Dr. Agarwal is currently a software engineer at Google and an affiliate professor in the Computer Science Department at the University of Washington.

Links:

Learn more about Rome in a Day at: http://www.nsf.gov/news/special_reports/science_nation/virtualrealitymaps.jsp.

Read more about building Rome in a Day in the Communications of the ACM (Association for Computing Machinery) at: http://cacm.acm.org/magazines/2011/10/131417-building-rome-in-a-day/fulltext or from National Geographic at: http://news.nationalgeographic.com/news/2009/09/090924-flickr-rome-build-day.html.

 

Activity:

Create a physical 3D model of a building using printed photos.

  1. Print out 2 copies of a set of the photos of any building.
  2. Using one set of photos, construct a 3D model - matching the backgrounds, points that are similar in one image to another, and tape together.
  3. Write down the instructions (the “algorithm”) for constructing the model.
  4. Once you’ve completed your 3D model and written down your instructions, have another group of students take the second set of photo copies, and follow your instructions to build another 3D model.
  5. Can you think of ways to generalize the instructions (create an "abstraction") so that they might work with any other building or object?

An additional activity for home use: Use the Photosynth site to create a panorama or ‘synth’ of a set of photos. While not true 3D, photosynth will give you and your students a glimpse of the complexity and power of mapping points in many different photos to one another to create a seamless panoramic or near-3D zoomable image (synth).

  1. Go to http://www.photosynth.net and download the needed software (Windows only).
  2. Select a set of photos from a social networking site or take several dozen of a new place or object.
  3. Use these photos to create a panorama or synth.