Pose estimation of colored checkerboard cubes

Question

I want to find the orientation of 2x2 checkerboard cubes, like these:

That is to say, I want to recover their positions and rotations within the image relative to the camera.

In my particular case, I care more about the rotation than the position (and the depth barely matters at all). I know the colors ahead of time, and can change them to be more convenient. I want to pick up the cubes, so a hand may be in the frame. The lighting may not be uniform, but the background should be simple (e.g. carpet, table, pavement).

I do have a partially working solution, which I've included below as an answer (it makes the question too specific to include it here). But I'm looking for suggestions on how to approach the problem and what techniques to apply.

Other things I've been considering:

• Use a line detection algorithm to detect edges, and use those to seed hypotheses (instead of the center saddle point).
• Do a cartesian-to-polar transform at the detected saddle points to turn the angled lines into straight lines (expensive?).
• Score hypotheses by using them to unskew a face then dot product-ing that against a reference image of the face (but what about lightning changes?).
• Random combinations of dilation and erosion throughout (invariably doesn't seem to help).

Answer 1

This is the partial solution alluded to in the question. Should I be using a totally different approach (probably)? Are there standard operations that do what I've cobbled together (definitely)?

1. Sample circularly at a radius of ~6 around each pixel and compute the sum of the absolute differences to the opposite side. This seems to do a pretty good job of picking up edges, and smoothing noise:

   

2. Do the same thing again but, instead of comparing across to the 180 degree counterpart, compute differences to the 90 degree counterparts. This still picks up edges, but especially picks up the saddle points at the centers of each face (less so when tilted, though):

   

3. Subtract the previous two transformations, cancelling the edges and keeping the saddle points. This seems to work quite well:

   

4. Find isolated local maxima in the saddle point image. At each one over some threshold, sample every pixel a distance of ~10 away. Find the alternating colors via a kmeans with k=2 on those pixels' colors. Use the resulting labels and a simple maximization algorithm to estimate the angles where the colors switch. If the kmeans match is terrible or there's lots of mismatches between the angles, discard the point as a false-positive::

   

5. For each remaining saddle point, offset by ~15 along each of its diagonal directions and do a flood fill against a finer version of the half-turn-edges image, made by sampling at a radius of ~2 instead of ~6:

   

6. For each flooded area, compute its contour and fit a rectangle. If the rectangle covers significantly more area than the contour, the flood fill probably escaped the face. For the flood fills that worked, use the furthest points along the diagonals (the support points) to estimate the position of the corners and the side-centers. If the two flood fills adjacent to a side succeed, average the points. When 2/4 or 1/4 of the flood fills for a saddle point failed, use the existing points to infer the missing ones:

   

7. Use the four estimated corners to compute a perspective warp. Try to refine the warp by tweaking the points and preferring lots of brightness near the sides and equators of the half-turn-difference transformed image... and otherwise lots of darkness in the interior.

   

8. (todo) Fuse the found faces into cubes. Recover the entire 3d pose.

From my experimenting, the weaknesses of this method are mainly:

• Bad at finding saddle points on faces titled more than ~45 degrees.
• Bad at refining the faces, unless the flood fill gets it extremely close to correct.
• Bad at excluding close false positives, like if the saddle point on an edge is assumed to be a center.
• Any blurring from motion ruins the saddle point discovery.
• Doesn't infer poses from the faces, yet.

Also its kind of slow, running at about 1fps, but I haven't put much effort into optimizing it.

Any suggestions?

Answer 2

This is not a complete answer to your problem, but the Matlab Calibration Toolbox tackles a number of these problems directly, although with more repetition in the target. http://www.vision.caltech.edu/bouguetj/calib_doc/

A huge issue in these problems is the lighting. It seems you have control over the lighting, so "simple" vs. "hard" solutions should be good, and I would focus on those.

One very robust option is to use a generalized hough transform to identify these shapes in the image.

Additionally, you seem to not have tried matched filtering. Again, a bit slow, but extremely robust.

Both of the above can be massively sped up with image pyramids.