It would help to have a model of how the rolls were created in the first place, and how they might have changed due to age and/or wear in the mean time. For example, the piano keys themselves are presumably a discrete set, so in one dimension the holes should be spaced more-or-less evenly. Furthermore, any errors in the discrete key axis should be reproducible as the time axis progresses, as the punch mechanism in the discrete axis is fixed. So I would scan the entire roll first just to build a model of the discrete coordinate -- the statistics of the hole locations. Secondly, I'd also be gathering statistics of the _shape_ of all the holes, in order to see how the hole shape varies. Once again, we presume that the exact same punch was used for the same piano key all along the roll, so if there are enough holes of that particular key, we can build a pretty good model. I would imagine that the time axis is _not_ discrete, since I think that the holes are basically punched when the key is pressed, and I don't believe that the mechanical systems utilized any kind of discrete sampling in the time axis. There are some relatively clever algorithms for recognizing straight lines and circles on a noisy grid; these algorithms can obtain 'sub-pixel' accuracy, in the sense that by averaging over a lot of camera pixels, you can find the 'best fitting' line or the 'best fitting' circle that matches what the camera sees. --- I had an analogous, but much simpler, problem coming from the data of my exercise watch. I wanted to compute from my bicycle speed and cadence data precisely which (discrete) gear I was in. Since I had complete access to the bicycle, I could write down all of the rational number gear ratios. The next problem was to calibrate the speedometer data for each ride to guess the exact wheel radius for that day (the effective radius could change based on tire pressure). Finally, I needed to divide the speed by the cadence to come up with a proposed rational number gear ratio & look it up in the gear table. If the ratio is too high (beyond the range of my gear ratio table), then I was coasting. If the ratio was too low, it would indicate that the wheel was slipping, or the GPS had lost its satellite tracking. What amazes me is that the standard bicycle exercise tracking software doesn't do this already. By analyzing enough data, it would be very easy to guess most of the gear ratios without even being told. That way, the software could analyze a complete exercise data set & figure out which bike I was on that day. At 12:32 PM 8/17/2013, Keith F. Lynch wrote:
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.)