Dual Photography Part II

It worked. The following playing card was successfully read even though it wasn't in the line ofsight of any light sensor.




Rather than write anything here I'll just refer you to the article on my home page.

I now have a couple of mirrors mounted on steppers so I may see if it's possible to get better results with these than with servos.

Derivatives of Regular Expressions

This paper from 1964 has an interesting algorithm for converting regular expressions into finite state automata. I've just figured out what it's all about.

The idea is that if you have a regular expression over some alphabet of symbols you can differentiate it with respect to a symbol. Basically, if R is a regular expression then dR/da is a regular expression that matches all of the strings that match R when prepended with an a. For example da/da={1} (where 1 = empty string), db/da = 0 (where 0 = the empty set and b!=a), d(a*)/da = a* and d(abc)/da = bc. You can write down a complete set of rules for differentiating regular expressions that are analogous to the Leibniz rules for differentiation.

Now here's the first crucial point: Given a regular epxression, R, you can compute repeated derivatives in an infinite number of ways by repeatedly differentiating with respect to different symbols. Many of these expressions turn out to match the same sets of strings, and when they do they are said to be equivalent. So we may form equivalences classes of derivatives. It turns out that the set of equivalent classes is finite.

Here's the next crucial point: differentiating an element of one of these classes with respect to a symbol gives you a representative of another class. So make a directed graph whose vertices are these classes and whose edges are labelled by symbols. We draw an edge from [S] to [T], with label a, if dS/da = T. This graph is none other than the graph of the finite state automaton to recognise matches with R.

The catch is recognising when [S]=[T], ie. when S and T match the same strings. But if we're building a machine we don't have to get this exactly right. We can use sloppy methods to try to identify [S]=[T]. It turns out that it's easy to produce an algorithm that doesn't guarantee to spot when they recognise the same strings, but that gives us a weaker equivalence which still results in a finite number of classes. This might give us a suboptimal automaton, but it still works.

This approach also leads to an elegant way to extend regular expressions with some other useful operations such as 'interleave' and 'complement'. ('interleave' should be familiar to anyone who's read Hoare's book on Communicating Sequential Processes.)

For further information see JH Conway's book on regular machines. Mark Hopkins posted an implementation in C on comp.compilers in 1994. Mark Hopkins also made this post to comp.theory which fills in the details I left out above. (Search USENET for postings by Mark Hopkins, they are frequently very insightful.)

Fermat's Last Theorem 'Disproved'

This story from the Manila Times is a good illustration, in a mathematical context, of how sarcasm doesn't travel well, especially between cultures.

For those who aren't getting it...Wiles's response isn't 100% serious.

Dual Photography Part I

At the end of this paper is an interesting parlour trick. The authors demonstrate a method of reconstructing what is on the face of a card even though the only light that reaches the camera from the face travels via reflection in a diffuse surface, a page of a book. The first thing that came to my mind was that the page of the book has a highly blurred reflection of the card on it and that what must be required is a form of deconvolution. But a moment's reflection suggests that would be really hard. However, after looking at a few comments on Slashdot claiming that the paper was trivial, I realised that this trick is easy! Even better, it can be done if you replace the camera with a photocell and requires only a few lines of code to process the data. (Note that the rest of the paper isn't quite as trivial!)

The idea in the paper is that a light source (and its characteristics) and a light sensor (and its characteristics) can be swapped and the sensor will record the same amount of light falling onto it. For example, suppose we have a scene illuminated by a laser, which produces a tight beam, and it is viewed by a photocell, which collects light over a wide area. Then the sensor responds as if it collected light from the same narrow beam originating from a lamp spreading light over the same wide area. And this is how we perform the card trick. We point a photocell at the page of the book and rasterize the card using a laser. As the laser scans, the photocell registers exactly as if it were a tightly focussed photocell scanning the card. There's nothing clever here - point a laser at a white object in a dark room and the rest of the room will be illuminated more than if you pointed the laser at a black object.

But I don't want to just claim this is easy. I intend to do it. So far I have hooked up a photocell to an analogue to digital converter on a microcontroller and I've tried 'rasterising' objects by hand. It's pretty clear from the microcontroller data that the sensor is correctly distinguishing light and dark regions on an object completely out of view. So it looks like my dual camera (cocamera?) should work. The only thing left now is to mount the laser on a servo-driven pan-tilt head so I can rasterise automatically. If it all works out I'll have pictures in Part II some time in the next couple of weeks.

Note that the dual in dual photography is the vector space dual.

Diagram Chasing

A few months ago I was looking at a catalogue from a flooring company called FLOR. I spotted that a couple of the pictures of rooms had mathematics on the wall. And not just basic material. One had a commutative diagram with what looked like a piece of a long exact sequence in it. I decided that I had to understand how such a thing could have appeared in a catalogue selling floor tiles.

After a bit of poking around I eventually found the pictures on the company web site, but no clue why they were there. I then posted to sci.math and was eventually led to this article from the Notices of the AMS. It turns out that the artist Bernar Venet specialises in paintings derived from mathematical digrams. He seems to have made a speciality of painting commutative diagrams.

The Neighbourhood of Infinity is now Open

Sorry about the (mathematical) pun!