Solving a Digital Jigsaw Puzzle

Early in the morning on September 26, 1997, a mild temblor shook northern Italy, rattling the fragile 13th-century Basilica of St. Francis in Assisi. Only minor damage occurred, and the friars counted their blessings. Nine hours later, though, a second, far more powerful quake hit. Within seconds, the vaulted ceiling of the upper Basilica collapsedkilling a friar, a novice and two technicians below. And several renowned medieval frescoes crashed to the floor, fracturing into hundreds of thousands of shards and clouds of dust.

The loss of life was a tragedy, and of art, a disaster. Among the frescoes destroyed were St. Jerome by Giotto and St. Matthew by Cenni di Pipi, also known as Cimabue. Both artists are considered fathers of Italian painting. Also lost were sections of molding painted by Giotto and the church's altar. Photographer Ghigo Roli, who was in the basilica at the time of its collapse, later published his diary of that day, writing, "I want to cry." Roli had spent the past four months photographing the frescos in detail.

Many experts feared the frescos could never be repaired. But an international team of scientists now says they have a way to use Roli's photographs, other images and computer algorithms to guide the restoration process to near completion. Their methodpresented last week at the 2nd International Symposium on Image and Signal Processing and Analysis in Pula, Croatiarelies on a computer program to sort out which fragments belong next to others, much like solving a digital jigsaw puzzle.

To prove the approach could work, three Italian electrical engineers interested in the frescoesGiovanni Jacovitti of the University La Sapieneza, and Alessandro Neri and Marco Carli of the University of Rome 3first conducted a feasibility study. They hired an artist to create a replica of the Cimabue fresco and then photographed it in such a way as to reproduce the effects on the original created by lighting, and the curve and height of the vaulted ceiling. They smashed the phony, photographed the pieces and scanned them into a computer, creating a database of fragments.

Next the trio developed a computer algorithm to search the fragment database, looking for pieces to match up with parts of the complete photograph according to color and detail. "Our method works by having the computer reposition the pieces with the highest confidence level," Neri says. "Then successive searches work down the levels of confidence"a strategy similar to finding the corner pieces of a puzzle first. In the end, the algorithm correctly placed between 90 and 98 percent of the pieces.

When the Italian team began to consider the real fragments and Roli's photographs, though, they knew they had a problem. They could no longer use plain color to guess where different pieces had come from in the original. The 750-year-old frescoes were painted on cement, some of which pulverized when it hit the basilica's floor. When workers washed this dust from the remaining fragments, they also washed away soot that had accumulated on the frescoes over time. Thus, the colors in the fragments didn't match those in the photographs.

So Neri, Carli and Jacovitti solicited the help of Sanjit Mitra at the University of California at Santa Barbara. Both Neri and Carli had worked as visiting scientists in Mitra's research lab, which specializes in color filtering, or correcting, and color matching. "When Marco explained last summer that they were doing a pixel-based analysis, I suggested they also use texture," Mitra recalls. "In other words, not just one pixel but blocks of pixels. Blocks afford a much more robust approach, so that the process of searching and sorting is faster."

Mitra's group has explored this sort of texture-based sorting in the hopes of developing novel Internet search engines for the future. "Give me a barking dog or a rotating yellow bowl," offers Serkan Hatipoglu, a graduate student in Mitra's lab, by example, "but search not by using words but image features." Hatipoglu has spent four years on the problem, "trying to find features to distinguish images, so that I don't have to look at all the image information. I just extract features from texture patterns and compare those features to find similar images in a database."

In the case of the ruined frescoes, Hatipoglu applied this texture-based sorting to pick out plain cement. The team was thus able to quickly subtract from the fragments' images all those broken edges and three-dimensional faces that were not part of the original frescoa simplification that should make the task to matching up colors and details much easier.

If they ever get to that point. So far the scientists have had little contact with the actual restoration project in Assisi. Neri and Carli say that perhaps some of the restoration professionals found the idea of using computers distasteful. At any rate, based on their work with the Assisi frescoes, the researchers suggest that all earthquake-prone countries place on file extensive photographic surveys of their priceless works of art; should disaster strike, computers and image-processing techniques might then come to the rescue.