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:

Re: Want to help me with an algorithm?

Post by rob »

So I chose a 128x128 box around the center, and did an autocorrelation on the blurred image. Here's the result:
autocorr.png
autocorr.png (2.12 KiB) Viewed 10822 times
There's a bright white blob at the origin, because the image is by definition correlated perfectly with itself at a shift of dx=0, dy=0. The next major correlation along a rough diagonal is at dx=42, dy=36. Since dx*dx + dy*dy = 2s*s, where s is the side of each square, we have s = 39.1 pixels per side. Since we know a square is 0.2 inches, this translates to 195.5 dpi, which is pretty much what I calculated by eye and by hand.

So, using this information, I can find a dot, move 42,36 from there, and look around +/- a pixel or two to find another intersection.

Now I just need to get the algorithm running quite a bit faster!

--Rob
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 »

Here is an autocorrelation on a sample in the center of the binarized checkerboard (as opposed to the intersection image):
autocorr2.png
autocorr2.png (5.93 KiB) Viewed 10811 times
Here, the image is self-similar at dx=43, dy=36, which compares favorably with the autocorrelation found using the intersection image. It also takes somewhat less time to compute, since we don't have to do a blur.
The Singularity is Near. ~ http://halfbakedmaker.org ~ Follow me as I build the world's first all-mechanical steam-powered computer.
bkrpr
Posts: 9
Joined: 04 Mar 2014, 00:52

Re: Want to help me with an algorithm?

Post by bkrpr »

rob wrote:
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
It might not be quite what you're asking for, but there is an algorithm specifically for correcting barrel distortion:
http://wiki.panotools.org/Lens_correcti ... parameters

With a linux cmd line program for applying it to images: http://wiki.panotools.org/Fulla using a database of various commercial camera lens characteristics (the PTLens database) [since closed]. There is a new database though called the lensfun database: http://lensfun.berlios.de/manual/index.html

Also, I have some university connections in NY, so if there are some papers Daniel can't get for you, I'm happy to give it a try.

All of which is by way of saying that this looks amazing, please keep up the good work.

-Ian
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 think I may abandon this effort also, since it looks like my dewarping work on Scan Tailor is working very well. :)
The Singularity is Near. ~ http://halfbakedmaker.org ~ Follow me as I build the world's first all-mechanical steam-powered computer.
bkrpr
Posts: 9
Joined: 04 Mar 2014, 00:52

Re: Want to help me with an algorithm?

Post by bkrpr »

rob wrote:I think I may abandon this effort also, since it looks like my dewarping work on Scan Tailor is working very well. :)
Well, modular work is always great, especially since the software to do all of these tasks is still really fluid, but getting this algorithm into any workflow is a great gain and it's good to know that scantailor development is still going. Is your scantailor work available anywhere?
bkrpr
Posts: 9
Joined: 04 Mar 2014, 00:52

Re: Want to help me with an algorithm?

Post by bkrpr »

you might also want to check out this piece of work going on at the decapod project: http://decapod.googlegroups.com/web/rec ... gobneSjMyE
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 »

Do you have a sense of why they are using the classic multiple-view lens distortion estimation process instead of the various other methods available? And in particular, why the demo only shows calibration occurring in the center of the lens, where distortion is least problematic?

I know they're trying to integrate everything very tightly, which probably explains it, but it makes me wonder why they aren't using something that doesn't require a special target, like the panoramic lens parameter estimation used by the panotools/hugin group.
o3h1p
Posts: 71
Joined: 08 Nov 2010, 22:47

Re: Want to help me with an algorithm?

Post by o3h1p »

Hey Rob,

If it still matters, and if you give me links to those papers I have access through a lot of paywalls (if we are talking academic).

jack
forza
Posts: 2
Joined: 04 Mar 2014, 00:53

Re: Want to help me with an algorithm?

Post by forza »

Hi!

I think OpenCV could be used for camera calibration and undistortion. Here is an example I found in C code, but there is also bindings for other languges.
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 »

Yes, the OReilly book Learning OpenCV has some great examples of using OpenCV for calibration. I may try this for stereo calibration if the Kinect effort doesn't work out...
The Singularity is Near. ~ http://halfbakedmaker.org ~ Follow me as I build the world's first all-mechanical steam-powered computer.
Post Reply