Computer Scientists Tackle 1600-Year-Old Jigsaw PuzzleJune 3, 2002
Four fragments of the Forma Urbis Romae, fit together in the early 1980s. As evident in this photograph, the matches between fragments are not obvious from an examination of their top surfaces. That the particular pieces do fit can be verified by inspection of the surfaces, largely hidden in this photograph, where they mate. Photograph courtesy of Emilio Rodriguez-Almeida.
As an undergraduate, Marc Levoy, now a professor of computer science at Stanford University, majored in architecture and once devoted a semester to a fifty-page research paper on Michelangelo for a history class. So it's not completely surprising that he's applying his expertise in computer graphics to one of the great unsolved problems of classical archeology: assembly of an immense, 1600-year-old jigsaw puzzle, most of whose pieces are missing.
The components of the puzzle are the remaining fragments of the Forma Urbis Romae, or the Severan Marble Plan of Rome. Carved on marble slabs that were once attached to the wall of the Temple of Peace in Rome, this enormous city map---60 feet wide and 42 feet high---depicted every street, building, ground floor room, and staircase of the ancient city of Rome. Some small parts of the map have been pieced together, but this puzzle has defied the skills of archeologists, primarily because of the un-wieldiness of the puzzle pieces (some of which weigh hundreds of pounds) and the exceedingly large number of them. The fragments, moreover, are kept in sealed crates in the Museum of Roman Civilization, and few people have had access to them.
By creating three-dimensional models of the puzzle pieces and devising algorithms that can find matches between them, Levoy, working with other researchers in both the computer science and classics departments at Stanford, hopes to piece together some large sections of the map. If successful, they will have attained an important milestone in archeological research, as the Severan Plan is one of the most important sources of information about ancient Rome. The map shows the layout of the neighborhoods of the ancient city, depicting homes, public baths, brothels, and their proximity to each other, as well as the location of important monuments. In some cases archeologists have chosen excavation sites on the basis of fragments of the Forma Urbis Romae.
"It's a weird project because the first place where we publish the results might not be a scholarly journal, but the front page of The New York Times," Levoy says. "Scholars argue for years about the placement of a single fragment, since by moving a fragment you might move a temple that's been lost since antiquity."
The fragments of the map offer many clues, as well as abundant challenges, to a puzzle enthusiast. Information can be gleaned, Levoy points out, not only from the pattern of surface incisions, but also from the shapes of the border surfaces, the thickness and physical characteristics of the fragments, the direction of the marble veining, and matches to excavations in the modern city. The challenges include eroded surfaces and faded incisions.
The Story of the Map
The map was constructed in about 200 A.D., during the reign of the emperor Septimus Severus. It was prominently displayed in one of the most important buildings in the city, which also housed a library and treasures from cities the Romans had conquered.
Three centuries later, as the Roman empire slowly collapsed, people began to strip away chunks of the valuable marble for construction purposes. Fortunately for historians, the remains of the map eventually broke away from the wall and parts of the building collapsed around it.
A few fragments were unearthed in 1562, and more have been gathered over the centuries, for a total of about 1180 pieces---roughly 15% of the original. About four hundred of the pieces have no surface incisions; these pieces, according to scholars, might represent parts of the Tiber River, plaza centers, or, perhaps, the borders of the map.
About two hundred pieces have been identified as depicting some of the most important and famous parts of the city, such as the Coliseum, the Palatine Hill, and parts of the imperial forums. Because of the way the map fell from the wall, scholars believe that many of the remaining shards will turn out to be clustered in these same areas of the city. The fragments are all from about half of the map, and Levoy does not believe that the pieces are randomly distributed across that half. "We expect a lot of the pieces will fit together," he says.
Levoy became interested in the map in 1997, during a trip to Italy for the planning stage of another bold endeavor: creation of highly detailed three-dimensional images of sculptural and architectural works of Michelangelo, including David (which produced the largest data set). For that project, Levoy, Brian Curless of the University of Washington, and 30 other researchers from the two universities traveled to Italy with four tons of equipment and spent an academic year scanning works of art under less-than-ideal laboratory conditions.
The following summer, Levoy and five other Stanford researchers scanned all the available Forma Urbis Romae fragments, working around the clock for 25 days in the damp, dusty basement of the Museum of Roman Civilization. The group used laser-stripe scanners that sweep the pieces with a plane of laser light and analyze the shape of the stripe 30 times per second. The scans were overlapped substantially, so that the swaths traced by the lasers could later be algorithmically aligned.
A year later, workers restoring a nearby building discovered 30 new pieces of the map---the first new fragments to be unearthed since 1956. The pieces were shipped to Levoy, by then back at Stanford, so that he could scan them in as well. In the end, a total of 40 gigabytes of raw data was created.
Making the Models
The group is now in the process of completing three-dimensional models of the scans. To create a model, they first align the scanned images, in the form of "polygon meshes," millions of tiny triangles measuring 0.25 millimeter on a side, using a modified, iterated closest-point algorithm. They then use a volumetric algorithm to combine the scans, after which they map color data onto the resulting three-dimensional models. The models of the fragments, which look quite real, can easily be rotated and viewed from various angles on a computer screen.
The group is also constructing a relational database that provides descriptions and bibliographic information for each fragment, with links to the 3D models and high-resolution photographs. This database will be freely available to the archeological and computer graphics research communities, educators, museum curators, and the general public---a boon to researchers in particular, as the originals are not on display. A sample database of 28 fragments is now online at http://graphics.stanford.edu/projects/forma-urbis/.
The next step will be the development of shape-matching algorithms for finding fits between the pieces---a tough task because the search space is so large. Without divulging his detailed plan of attack, Levoy explains that the basic idea is to sort the pieces by thickness and start with close neighbors in the sorted list. From there, the researchers will move to an algorithm that matches only the surface lines and the direction of marble veining. This algorithm will give lots of false positives, Levoy points out, but it's an inexpensive way to reduce the search space.
For sifting through the resulting sets of matches, the group will use string-matching algorithms---similar to those used in sequencing the human genome---to compare two-dimensional contours of the pieces. For the final step, the researchers will work with the three-dimensional models themselves, trying all possible rotations and shifts on just the small set of close matches obtained with the previous two methods.
One potential problem concerns limitations of the algorithm for aligning the scans. The iterated closest-point algorithm works by finding for every vertex point on one mesh of triangles a closest vertex point on the mesh from the overlapping region; it then finds the translation and rotation that minimize the distance between the points. "This method gives the best alignment between two meshes," Levoy says, "but if it takes you twenty or thirty meshes for one object, by the time you're at the back of the fragment they don't line up well." To overcome this obstacle, the researchers are using optimization techniques to spread the errors around all the meshes. Still, there are mistakes and global biases, and details are blurred out below one millimeter. This level of error is only borderline satisfactory for the task, as the lines of the map are only a millimeter and a half across. "We're working on algorithms to resolve the optimization problems," Levoy says.
People have scanned broken artifacts before and tried to piece them together via computer algorithms, Levoy explains, but typically the method has been applied to shards of pottery and other objects that break cleanly. "No one has ever tried to do something this eroded or with this many pieces," he says. Still, Levoy is optimistic about his prospects: "I think we will get somewhere."
Sara Robinson is a freelance writer based in Berkeley, California.