Want to help me with an algorithm?
Moderator: peterZ
- 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?
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):
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
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):
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.
- 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?
I'll email this to Aaron, he knows lots of vision tricks and graphics people...
Re: Want to help me with an algorithm?
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
Cheers,
Aaron
- 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?
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.
- 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?
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.
- 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?
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):
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
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):
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
- 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?
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.rob wrote:Oh, you are teh awesomes. Can I send you a list of links to articles that I'm interested in?
- 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?
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?
- 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?
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.
- 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?
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
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.