Checkerboard detection – part 1

I've began my foray into lens distortion correction. I've been looking forward to tackling this one, because it's the last of the three engines I need to get working, before I can try and use The Dark Room for something. It's also one of the most critical engines to get right, because this is what helps the camera pose engine to do its thing.

Upon doing my initial research, I found that there are already a number of external libraries out there that accomplish detecting checkerboard patterns in images. What I also found, was that they each differ slightly in their capability and detection methods. For my part, although this engine is really important, I wasn't too concerned with which algorithm I used. I was more concerned with just getting something to work so I can start trying to use the program.

I went through some papers and website posts others had written, found from various places online. I must admit, at this point I find things quite difficult. I've never been shown how to read and interpret a paper into code form. So even though I understand the concepts the papers talk about, I don't know how to turn that into code. With this in mind, I had to do a fair bit of searching around to find examples of code and how to implement it. It's taken a fair bit of effort, but I've managed to put together an engine that can detect corners. It's a start.

Here's what we're trying to do.

We want to find a checkerboard pattern in an image. I'll explain why in the follow up to this post (part 2), which is hopefully not too far away. For now, let's look at the photo below, taken from my phone:

This is a photo of a checkerboard pattern I printed out on A4 paper. You can tell that the printout is not entirely flat, I'll have to deal with that later. For now, what we want to do is find the corners of the checker pattern tiles. We do this by iterating over all the pixels, and see if we can find various gradients in the image that are formed a certain way. Visually, it looks something like this:

Before I go any further here, I'm not sure if my understanding of this is correct, so all of this comes with the caveat that I may not have interpreted what I read very well!

By finding gradient matches, and then calculating things a little deeper using something like the Harris corner detection method, we can find the corners of each square to sub-pixel accuracy. This is important, because we'll be using these corners to establish our distortion correction parameters.

I spent quite some time trying to make this work. I then got an early version working, only to find that I had to go back and redo a bunch of code in my matrix class as well. It really highlights the importance of making sure your code is correct at each stage along the way. For instance, my inverse matrix function was not returning the correct result. Nor was the determinant function. So I had to redo them. And a few other bits and bobs as well. I went over my code line by line in key places to find these bugs... It was painful.

But after much toying about, I managed to come up with this:

Great, we've found some corners! But, this is only part of the way there. From here, I still need to detect and build a checkerboard object. We do this so that we know how the points relate to each other. If we know how the points relate to each other, in the sense of a board, we know how we can tell the computer that the red dots on the top row, are in fact corners of the pattern that form a single straight line. So, we need to put together and figure out how to interpret the corners into a board object. And we need to do this using the found corner points in the image.

We're trying to get to something like this:

And in case anyone is thinking "Oh that's easy, you can just start 'scanning' from top to bottom", this is not the case. You may have a checkerboard image that's rotated, warped, or an image with more than one checkerboard. Take a look at these examples:

So, it's not a straight forward case of simply doing a top to bottom search. It's much more sophisticated than that.

By the way, the image above with the red and green lines, is actually a work in progress of part 2. You can see I've almost detected the board itself. But those with a savvy eye may notice that there is an error in the found board - the points from the bottom row (yellow markers, hard to see) are not being picked up as being part of the board for some reason. I don't know what's causing this yet.

And this is where we end part 1. I'm still working on the code for part 2. I'm hoping this can be resolved fairly soon as well. Then I can move onto the final part, which is establishing the correction parameters from our found corner points and board object.

Exiting times!