Want to help me with an algorithm?

DIY Book Scanner Skunk Works. Share your crazy ideas and novel approaches. Home of the "3D structure of a book" thread.

Moderator: peterZ

User avatar
rob
Posts: 773
Joined: 03 Jun 2009, 13:50
E-book readers owned: iRex iLiad, Kindle 2
Number of books owned: 4000
Country: United States
Location: Maryland, United States
Contact:

Want to help me with an algorithm?

Post by rob »

So I was playing around with a method of automatically rotating, deskewing, dekeystoning, and de-lens-distorting images. Daniel brought up an idea a while back, that we could have a calibration page, then scan many pages, then recalibrate, and so on. So I printed up two calibration images, one with a checkerboard (0.2 inches per square), and one with dots (0.2 inches between dots). By knowing the size of the features, the average dpi is easy to calculate.

As an experiment, I scanned them, manually determined the coordinates of the outer edges of the checkerboard image, and applied a bilinear interpolation to correct. Here is the result (I cut the images down by 50% to save on space):
calibration-dots.jpg
Calibration image, dots, 0.2 inches apart
(516.74 KiB) Downloaded 1626 times
calibration-checkerboard.jpg
Calibration image, checkerboard, 0.2 inches per square
(637.98 KiB) Downloaded 1626 times
corrected-checkerboard.jpg
Corrected checkerboard image
(614.8 KiB) Downloaded 1626 times
As you can see, the correction worked perfectly, except that the corrected image shows barrel distortion. That could be due to the lens, but an easy fix is to correct based on more tiles (I chose a single tile, the entire checkerboard).

Here's what I need: an algorithm that will pick out the coordinates of the corners of each square in the checkerboard image, or an algorithm that will pick out the coordinates of the centers of the dots in the dot image. Yes, I did Google for checkerboard corner detection, and there are lots of papers... hidden behind paywalls. So I'm throwing this out to the group: can anyone find a suitable algorithm? I'm not looking for ideas on constructing such an algorithm, but an algorithm that already works.

Thanks!

--Rob
The Singularity is Near. ~ http://halfbakedmaker.org ~ Follow me as I build the world's first all-mechanical steam-powered computer.
User avatar
daniel_reetz
Posts: 2812
Joined: 03 Jun 2009, 13:56
E-book readers owned: Used to have a PRS-500
Number of books owned: 600
Country: United States
Contact:

Re: Want to help me with an algorithm?

Post by daniel_reetz »

I'll email this to Aaron, he knows lots of vision tricks and graphics people...
Aaron
Posts: 4
Joined: 04 Mar 2014, 00:52

Re: Want to help me with an algorithm?

Post by Aaron »

The SIFT algorithm is basically a fancy corner detector. It should also be able to pick out the dots on your dot page. This link describes the algorithm and has links to implementations on various platforms at the bottom: http://en.wikipedia.org/wiki/Scale-inva ... _transform .

Cheers,

Aaron
User avatar
daniel_reetz
Posts: 2812
Joined: 03 Jun 2009, 13:56
E-book readers owned: Used to have a PRS-500
Number of books owned: 600
Country: United States
Contact:

Re: Want to help me with an algorithm?

Post by daniel_reetz »

Also, just letting you know, if you need any papers that could be behind a paywall that a university might have access to, I can get them for you through NDSU or one of my librarian friends.
User avatar
rob
Posts: 773
Joined: 03 Jun 2009, 13:50
E-book readers owned: iRex iLiad, Kindle 2
Number of books owned: 4000
Country: United States
Location: Maryland, United States
Contact:

Re: Want to help me with an algorithm?

Post by rob »

Oh, you are teh awesomes. Can I send you a list of links to articles that I'm interested in?
The Singularity is Near. ~ http://halfbakedmaker.org ~ Follow me as I build the world's first all-mechanical steam-powered computer.
User avatar
rob
Posts: 773
Joined: 03 Jun 2009, 13:50
E-book readers owned: iRex iLiad, Kindle 2
Number of books owned: 4000
Country: United States
Location: Maryland, United States
Contact:

Re: Want to help me with an algorithm?

Post by rob »

I used an idea based on the FAST algorithm: Take a 2n x 2n square. Determine the number of black pixels in the top half, bottom half, left half, and right half. The counts should each be approximately equal to half of 2n x 2n to be a checkerboard intersection.

I colored the result using intensities to show how close a pixel was to the ideal definition. A bright white pixel (255) perfectly fits the definition, while a black pixel (0) indicates that the counts are way off. I also postprocess by accepting only the highest resulting intensity within a 2n x 2n square (maximum emphasis). Here are some zoomed results (each dot is a pixel):
Intersections identified somewhere in the middle of the checkerboard
Intersections identified somewhere in the middle of the checkerboard
corners-zoomed1.png (2.82 KiB) Viewed 15115 times
Intersections identified at the lower right of the checkerboard
Intersections identified at the lower right of the checkerboard
corners-zoomed2.png (1.86 KiB) Viewed 15115 times
As can be seen, identification in the middle is nearly perfect. There is some uncertainty at the edges (which is OK), and false positives outside the checkerboard. Further refinement of the algorithm could eliminate the false positives. At that point, we could simply read off the coordinates of the white pixels, and use a subset of those to compute the distortion correction matrix.

Note that the ultimate goal here is to act as a preprocessor for Scan Tailor. I am mightily impressed with Scan Tailor's GUI and speed!

--Rob
User avatar
daniel_reetz
Posts: 2812
Joined: 03 Jun 2009, 13:56
E-book readers owned: Used to have a PRS-500
Number of books owned: 600
Country: United States
Contact:

Re: Want to help me with an algorithm?

Post by daniel_reetz »

rob wrote:Oh, you are teh awesomes. Can I send you a list of links to articles that I'm interested in?
Absolutely, anytime and as many as you like (though I can't promise I can get all of them, obviously). This goes for other forum members as well. I hate paywalls and all walled gardens. Subverting them is a true pleasure.
User avatar
daniel_reetz
Posts: 2812
Joined: 03 Jun 2009, 13:56
E-book readers owned: Used to have a PRS-500
Number of books owned: 600
Country: United States
Contact:

Re: Want to help me with an algorithm?

Post by daniel_reetz »

HOly crap!! Those are some great looking results!!! I love the idea of doing this kind of calibration. Do you think it would be worthwhile to try to get a luminance calibration in there as well?
User avatar
rob
Posts: 773
Joined: 03 Jun 2009, 13:50
E-book readers owned: iRex iLiad, Kindle 2
Number of books owned: 4000
Country: United States
Location: Maryland, United States
Contact:

Re: Want to help me with an algorithm?

Post by rob »

Perhaps given that the checkerboard should be pure black and pure white, that might do just as well to adjust the contrast in a tiled manner!
The Singularity is Near. ~ http://halfbakedmaker.org ~ Follow me as I build the world's first all-mechanical steam-powered computer.
User avatar
rob
Posts: 773
Joined: 03 Jun 2009, 13:50
E-book readers owned: iRex iLiad, Kindle 2
Number of books owned: 4000
Country: United States
Location: Maryland, United States
Contact:

Re: Want to help me with an algorithm?

Post by rob »

Some more experimentation shows that with differing values of n, the locations of the intersections change a little bit. That makes sense, since we're dealing with raster images, not vector images.

So the next step is to identify the intersections due to the checkerboard, and get rid of the false intersections. Well, the checkerboard has an obvious regular pattern to it. I figure an autocorrelation should do it, but there are two problems with that approach. First, the intersections will not match exactly when they are offset by a square, because the intersection locations aren't exact due to rasterization. Second, an autocorrelation on a huge image, even using an FFT algorithm, may take too long.

So here's my current idea. Around the center of the image (where it is virtually guaranteed we're inside the checkerboard), take an MxM square -- say, 512x512 or even 256x256. Gaussian blur it by a few pixels to smear out the intersections a bit. Now run an autocorrelation on this smaller image, but only at the points highlighted by the original (nonblurred) image. Search the resulting image for the brightest pixels that are not at the origin, and that are on a rough diagonal from the origin. This should give an offset equal to one square by one square, and will tell you how big the squares are, and where to expect the intersections.

Hopefully I'll have an example image I can share some time today.

--Rob
The Singularity is Near. ~ http://halfbakedmaker.org ~ Follow me as I build the world's first all-mechanical steam-powered computer.
Post Reply