Introduction

Hi, it's Kevin again. I'm back to continue our exploration of building a software Hollerith card reader using a document scanner and image processing. In this episode, we'll study how to recover the geometry of the punched card in the image scanner In the last couple of episodes - there's a link somewhere nearby - we scanned a card, u sed k-means clustering to separate the paper from the green screen, and then used median filtering, blurring, and gradient estimation to remove noise from the image and detect the edges We now have an image with strong lines drawn at the edges of the paper. Let's get to work on finding the rectangle of the card!

The Hough transform

To do this, we'll use a technique called the Hough transform, named for the American physicist Paul Hough. As an aside, "Hough" rhymes with "rough" and "tough", and not with "bough", "cough", "dough" or "through". Isn't English spelling just wonderful? The Hough transform is a technique for finding straight lines n an image. Variations on the Hough transform have been developed to find circles, ellipses, and other figures in images as well.

Lines in parameter space

All of them work by using a parameter space to represent the lines or other figures. In the parameter space that the Hough line transform uses, every line in the plane can be represented with two parameters, with each pair of parameters representing a unique line. The first of these is the angle that the line makes with one of the axes. I'm using the horizontal axis here. This angle will vary from zero to pi. A given value of theta selects a particular pencil of parallel lines. The second is the signed distance from the origin to the line. Once an angle has been selected, this parameter tells us how far the line is to the left or right of the origin as we look in that direction. The equation of the line is shown at upper right. This representation is better for our immediate purpose than the slope-intercept form because it is free of singularities.

Voting algorithm for Hough transform

Now let's look at how we can find pairs of parameters corresponding to lines in the image. We make a big array whose column number describes the angle theta, divided into whatever step size is convenient, and whose row number describes the distance rho, which is already measured in image pixels. The elements of the array can ordinarily be short integers, because no element will ever be greater than the diagonal of the image, measured in pixels. The distance rho can be no more than plus or minus half the diagonal of the image, and theta is in the range from 0 to pi, so we know in advance what the size of the array has to be. Now we iterate over pixels that we decided were at the edge of the paper. For each edge pixel, we consider all the angle steps from zero to pi. For each angle, we plot the line running through the pixel at that angle, and compute its distance to the origin. In the array, we increment the cell corresponding to that angle and displacement, which amounts to casting one vote for the line. The array elements corresponding to that line's votes lie on half a cycle of a sine wave. If we look at the votes cast by a few more pixels on the top edge of the card, we see that their sine waves all meet at the point that corresponds to the line running along that edge. A selection of points on the left edge of the card again gives us multiple votes at the point corresponding to the formula for that edge. And the right and top edges also give us lots of votes at the points corresponding to their line formulas. Let's add up the votes for every point that we identified as being on an edge.

Interpreting the Hough transform

We see that the resulting plot has four bright spots that have garnered many more votes than anywhere else on the plot. Two of these are for small values of theta, and two are for values of theta close to a right angle. Plotting the lines that those points specify back onto the card shows that they do, indeed, designate the four edges of the card. There are many lesser bright spots, some of which correspond to the left and right edges of the columns, or the top and bottom edges of the rows. If I didn't know the dimensions of the card, I could use this information for reverse engineering. I'm filling in actual numbers from the image I'm using so that I can do a few quick calculations with them. I can plot the lines corresponding to those points, and they overlay on the image almost perfectly. Some trigonometry gives the corners of a rectangle that frames the card.

Evaluating the result

Knowing that I set my scanner to 300 dots per inch, I can read out the dimensions of the rectangle. A standard Hollerith card is 7 3/8 by 3 1/4 inches, and I have hit that to within less than a fiftieth of an inch (or a half of a millimeter). Given the vagaries of paper swelling and shrinking with humidity, that's within an acceptable tolerance. Of course, the proof of a digitization is in the digits. Let's use this alignment to pull the bits off the card. We're all done except for some bookkeeping. We can use the four courners that we found to define a perspective transformation from the coordinates in the image to the coordinates on the card. Using a published standard for the hole locations and sizes, we can draw boxes around where holes might be, and count up the fractions of pixels inside those boxes that are paper and green-screen. The holes align pretty badly, because the old paper is warped. Even so, no zero bit was scored as less than 99% paper and no one bit was scored as greater than 60% paper. Setting a threshold of 75% recovered all the bits. I didn't even need to tweak any of the numbers to run a few hundred more cards. It all just worked. Eventually, I reverse engineered the meaning of the binary data on the cards, but to run the organ, I didn't need to.

I lied! Next time - the transform I actually used.

I needed only to replay it. That would bring this story to a close, except for one minor problem: I lied to you about the Hough transform. It's only a little fib. All the image preparation stays the same, and the perspective transformation at the end is also the same. The angle-and-displacement representation changes only slightly, which we'll see gives us a more convenient way to compute the transformation. The method that I used is quite different from the Hough transformation that I've seen in textbooks and deserves to be better known. I want to devote at least an episode or two to it, so I'll sign off now and get into it next time. Until then, stay safe, stay healthy, and keep calculating!