Some of the most interesting math problems are ones that relate to the real world. I was recently loaned an antique piano roll to scan in with my flatbed scanner and turn into a MIDI file. (You can hear it at <http://KeithLynch.net/2202.mid>. 2202 is its serial number. I have no idea what the tune is called.) The piano roll consists of a regular square lattice of holes, much like a punched card or punched paper tape. My first problem was to figure out the alignment, since it's all but impossible to feed it into the scanner perfectly straight. When I scanned my old punched paper tapes last year, I used the edges of the tape as reference, but that wasn't practical for the piano roll as the edge was too ragged due to wear. So I used the holes themselves. The holes are all circular and the same size. I identified the holes, as N coterminous black pixels with N in a certain range. (The contrast was of course cranked all the way up, so every pixel was either pure white or solid black.) I located the center of each hole, by averaging the locations of its pixels. Then I constructed lines between the centers of the holes, and looked for the modes of the slopes of these lines. As I expected, those modes were the horizontal and vertical axes. (Is this a known algorithm? Is there a better one?) A complication is that the mode of a set of floating point numbers isn't well defined. I used binning. Details on request. Another complication was dealing with near-vertical slopes. I swapped X for Y when slopes became too great. Unsurprisingly, the two axes aren't quite at right angles to each other. I'm not sure how much of this skew is intrinsic to the piano roll and how much iss an artifact of rotation combined with non-square pixels. Another complication is that many of the holes were not recognized as such, as they were too large due to two holes merging. But this wasn't a problem, since this algorithm is quite robust for moderate numbers of missing or spurious holes. (Of course I had to do something else to rediscover those missing holes later, so they would turn into sounds.) The one problem with this algorithm is it's O(N^2) in the number of holes. But that's not much of a problem since there are usually only about a hundred holes per scan page. Another problem with this piano roll was that someone had made purple marks on it, which can be mistaken for holes. Fortunately, I was using a color scanner. It was a simple matter to subtract the values of the green pixels from the sum or the red and blue before cranking up the contrast. (I'm doing all of this processing in my own C program, after reverse-engineering the TIFF format. I also had to reverse-engineer the MIDI format.) (I was using a large black book as backing, so that the holes would look black. Appropriately enough it was also an antique book. But it was not an antique scanner.) Puzzle: Suppose there had also been green marks on it? How would I also get rid of them in software? Then, since the reward for a job well done is more work, I was given several more piano rolls. Even though these were intended for the same piano, they are quite different. Instead of circular holes, there are long thin holes, like many overlapping circular holes. In other words they're hot-dog shaped. So I need to rewrite the axis- finding code. The obvious approach is to to find the long axis of each hole, as those should all be parallel and should be the horizontal axis. What's the best way to do that? One approach would be to start with any point in the hole, find the most distant point in the hole from that point, find the most distant point in the hole from *that* point, find the most distant point in the hole from *that* point, etc., until I'm finding the same two points each time. Is this guaranteed to always converge to the correct two points in any finite set of points? How many steps might it take? But wait, in some of the piano rolls the long thin holes don't have round ends, but square ones. The holes are rectangles. The long axis of such a hole is of course a diagonal, which is not what I want. Nor am I guaranteed to find as many "/" diagonals as "\" diagonals, so I don't want to rely on binning averaging them out. Any ideas on how to efficiently find the long central axis of a rectangle with arbitrary orientation? Well, not quite arbitrary. The slope should never be as much as 1/10. Also, some of these piano rolls have black marks on them. How can I distinguish holes from them? (Yes, I know the answer to this one.)