Solving a Digital Jigsaw Puzzle

Computer programs that can sort images by color, detail and texture could help restore medieval frescoes ruined in an earthquake

Image: courtesy of UCS
B
FRESCOES from the Basilica of St. Francis in Assisi, Italy, were copied (above) for scientists hoping to learn if computers might help restore the originals, ruined nearly four years ago in an earthquake.

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 collapsed¿killing 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.


On supporting science journalism

If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.


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 method¿presented last week at the 2nd International Symposium on Image and Signal Processing and Analysis in Pula, Croatia¿relies 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 frescoes¿Giovanni Jacovitti of the University La Sapieneza, and Alessandro Neri and Marco Carli of the University of Rome 3¿first 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.

Image: courtesy of UCSB
FRAGMENT from a replica, like one from an Assisi fresco, is harder to place than a jigsaw puzzle piece. The colors don't match the originals, and the jagged edges don't line up
.

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 fresco¿a 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.

It’s Time to Stand Up for Science

If you enjoyed this article, I’d like to ask for your support. Scientific American has served as an advocate for science and industry for 180 years, and right now may be the most critical moment in that two-century history.

I’ve been a Scientific American subscriber since I was 12 years old, and it helped shape the way I look at the world. SciAm always educates and delights me, and inspires a sense of awe for our vast, beautiful universe. I hope it does that for you, too.

If you subscribe to Scientific American, you help ensure that our coverage is centered on meaningful research and discovery; that we have the resources to report on the decisions that threaten labs across the U.S.; and that we support both budding and working scientists at a time when the value of science itself too often goes unrecognized.

In return, you get essential news, captivating podcasts, brilliant infographics, can't-miss newsletters, must-watch videos, challenging games, and the science world's best writing and reporting. You can even gift someone a subscription.

There has never been a more important time for us to stand up and show why science matters. I hope you’ll support us in that mission.

Thank you,

David M. Ewalt, Editor in Chief, Scientific American

Subscribe