Log in

No account? Create an account
Who, me? [userpic]

The Chudnovsky Mathematician

January 19th, 2006 (09:23 am)

Last night I went to a lecture at the MoS by David & Gregor Chudnovsky, on how they reconciled the digital images of the Unicorn Tapestries. Really interesting. (Oh, and I think I saw siderea there. Not sure, though; I'd only seen her once before, and that in passing.)

I'm going to assume you've read the New Yorker article.The Chudnovskys, with Amir D. Aczel, who moderated the talk They started out by comparing the two alternate techniques for large-scale photography: taking lots of pictures and tiling them together versus taking one gigantic picture. The latter has actually been done; they showed a picture of a camera built for George Roberts (?) in 1900. Roberts was retained by a Chicago train company to take pictures of their trains for a World's Fair in Paris; they wanted huge pictures that could show the details, so Roberts had a special camera built. This was a big camera. It was the only camera I've ever heard of that required a crew of operators—Roberts to work the lens, and an assistant to handle the film (plates?). The camera proper weighed 900 pounds; the film box weighed a further 500 pounds. It was mounted on a wooden framework; the crew stood on the framework. The resulting prints were so huge that the French government refused to believe they were real, and were going to kick them out of the fair. The train company's lawyers sent an affidavit; the French government still didn't believe it. Finally, the French consul in New York went to Chicago to see the camera, and reported that, oui, it was real. Recent estimates are that the Roberts camera produced an image with 400 gigapixels.

The Chudnovskys call the approach of tiling many pictures parallel photography; by analogy with parallel and serial computing, they call Roberts's massive camera an instance of serial photography.

Now, they started getting into what the Met had done, and why they were called in. Turns out there were some complications that the New Yorker article hadn't covered. In addition to the fact that the threads had unstretched when laid out horizontal, the photographers had moved the tapestries from time to time—they weren't allowed to touch the tapestries themselves, but they did move the white cardboard (?) they were resting on (it wasn't clear to me why; something about making things straight). The Cs showed an animation whose frames were different versions of a snippet of the edge; it should have been a still image, but instead the snippet wobbled back and forth slightly. Then they showed an analogous animation of one section of the vines, which waved around wildly, as if blowing in the wind. In essence, they said, the surface they were trying to reconstruct was less like a solid and more like a very slowly moving liquid.

So, the standard image tiling algorithms (which actually date to the mid-19th century) were useful only as a conceptual starting point. Instead, they wound up using algorithms more akin to those used for speech recognition, or DNA sequence analysis, in which you have two streams of data and need to find similar substreams. Those algorithms are O(N2), which is to say, the amount of time they take is more or less proportional to the square of the amount of data you feed them. Not wonderfully efficient, but not too bad...but, when you try to apply them to two-dimensional data, you're doomed; the result is O(2N), meaning the amount of time needed grows exponentially with the size of the data. The Cs had to devise new algorithms which could run in O(N5) time. In most domains, that'd sound pretty bad; but, compared to exponential, it's a huge improvement.

Now, this paragraph is going to be pretty geeky (yeah, yeah), but I want to get the details down while I remember them. Skip ahead if you're not interested. The stream-based algorithms are based on measuring edit distance from one stream to another. The Cs' 2D algorithm applies a similar metric; IIRC, it just takes an N-pixel image as being a point in 3N space (RGB), and then uses the standard Euclidean distance. What I don't think they covered was how theyexplored that space; as I understand it, the vast number of ways to explore it is why the naïve approach is exponential.

Part of how they sped things up was by being willing to live with an inexact answer; this cut down the size of the search space. As they pointed out, all they were really looking for was something that looked like the tapestry to the human eye. Further, since the pictures had been taken at different times, under slightly different lighting and atmospheric conditions, there was no single correct answer anyway. (Even when it's hanging on the wall, they pointed out, everybody sees it slightly differently.) This was driven home most dramatically when they gave the combined picture to the Met (never having looked at the whole thing); the Met printed it out, and found that one segment was overexposed. Apparently, when that tile was photographed, someone opened the door at just the wrong time, or something. So the Cs had to go back to that section and do gamma correction (basically, tweaking the exposure) to make it match the rest of the picture.

After their talk about the tapestry, the Cs sat down with a local mathematician, and talked about their larger work. For a long time, the Cs were working on using their supercomputer to generate more and more digits of π. The world record for most digits kept going back and forth between them and some guy in Japan, using a Hitachi supercomputer. They were using more sophisticated techniques, so they were able to keep up, even though their computer wasn't as fast. They were hoping to discover regularities in the digits of π. But, once they passed the billion-digit mark (they reached 1.1011 billion), and still didn't find any, they decided they were wasting their time. Besides, the Man From Hitachi was improving his techniques, and the Cs just couldn't keep up in raw computrons— the Hitachi machine has 2TB of cache.

The host mathematician mentioned some Japanese guy who had memorized the first 40,000 digits of π. Gregory: "That's sick.". That got a big laugh.

Gregory said that π's positional representation seemed to be a very good pseudorandom number generator, but that wasn't intrinsic; it was an accident of positional notation. He mentioned some other representation that the Chinese used to use (continued fractions?), and said that might have been interesting if they had developed it further instead of adopting European notation.

The Cs explained that calculating digits of π is a good way to stress-test a computer design; there are ways to, in essence, compute a checksum over the first N digits, to verify that the value found for π is correct. (Apparently, The Man From Hitachi didn't used to do that; he just ran the calculation twice, which can detect intermittent failures, but not consistent hardware bugs.)

The Cs would love to find some other use for massively parallel computing, especially if it involves image processing. (They're only interested in peaceful applications, though.) An idea I had on the way home: for tricky problems, such as predicting network outages, use genetic-algorithm techniques on the parallel machine (it's an embarassingly parallel problem, since each CPU can simulate a separate candidate algorithm), then run the resulting algorithm on lesser machines. Same sort of economic nature as writing software.


Posted by: C. Virtue (cvirtue)
Posted at: January 19th, 2006 04:11 pm (UTC)
circuit seablatt

May I put a link to this on the SCA LJ community and other similar places?

Posted by: Who, me? (metageek)
Posted at: January 19th, 2006 04:11 pm (UTC)


(Deleted comment)
Posted by: Who, me? (metageek)
Posted at: January 19th, 2006 04:58 pm (UTC)
Doesn't look like it

Doesn't look like it. The Met doesn't sell it online; and I'd be surprised if it were available for free, since it could be used for high-quality competition to the Met's prints of the tapestries.

Posted by: C. Virtue (cvirtue)
Posted at: January 19th, 2006 05:22 pm (UTC)
about tapestry backs

I have one of the coffee table books the Met has published about the tapestries, and they do have one or two examples of what the back looks like, to show aging/light damage. Likewise the book about the Devonshire Hunting Tapestries (the recent color one) has such photos.

I was able to get my own prints of some views of the Devonshire tapestries by going to their image library, finding what I wanted, and ordering a copy. In that process, I saw a lot of back-of-tapestry pictures, and could have ordered lots of them if I'd wanted to/had the money.

I had to sign several things saying I would not copy or publish the photos I bought, and the photos were expensive.

(Deleted comment)
Posted by: C. Virtue (cvirtue)
Posted at: January 19th, 2006 05:35 pm (UTC)
Re: about tapestry backs

And that gets into the whole issue of copyright and intellectual property, which is thorny for museums with ancient works. I think that "Corel vs. Bridgeman" probably applies to tapestries, myself, but I'm not a lawyer, etc.

Posted by: Who, me? (metageek)
Posted at: January 19th, 2006 05:45 pm (UTC)
Re: about tapestry backs

In this case, the problem is that the Chudnovskys had to make some judgment calls in reconciling the images; that's probably enough to count as the spark of originality required to qualify for copyright.

(Deleted comment)
(Deleted comment)
Posted by: Who, me? (metageek)
Posted at: January 19th, 2006 06:04 pm (UTC)

Sure, go ahead

9 Read Comments