About

The PuzzleBoard is an alternative calibration pattern for geometric camera calibration. The often used checkerboard calibration pattern (based on Zhang et al.'s seminal work) lacks any positional encoding. Thus, the calibration pattern must be completely visible without any occlusions. In some applications alternative solutions are preferred. E.g. ArUco or ChArUco boards allow partial occlusions, but require a higher camera resolution to read the code.

The PuzzleBoard is a new alternative that combines the advantages of checkerboard calibration patterns with a lightweight position coding that can be decoded at very low resolutions. Even very small image sections are unique in terms of translation and rotation. The decoding algorithm includes error correction and is computationally effi�cient.

PuzzleBoards can be used not only for camera calibration but also for camera pose estimation and marker-based object localization tasks (the markers will then be small subpatterns of the PuzzleBoard pattern).

This reposiory gives a first implementation of the decoding algorithm for pictures taken from a PuzzleBoard target.

If you want to print a PuzzleBoard target you can use the PuzzleBoard generator from the following website:

https://users.informatik.haw-hamburg.de/~stelldinger/pub/PuzzleBoard/welcome.html

there you will also find demo videos and further information about the PuzzleBoard.

Usage

Needed pip packages

1. opencv2
2. numpy
3. sklearn

Structure

example.py is a simple example program calling puzzleboard_detector.py for a given image and plotting the detections.

puzzleboard_detector.py is the main entrance point of this project. Running this with an rgb uint8 image as parameter will run the entire pipeline from initial corner detection to MST and Grid Decoding. It returns the discrete grid coordinates as well as the subpixel image positions of the found grid points.

PuzzleBoard pattern structure

Basicly the puzzle consists of a standard checkerboard pattern with alternating white and black squares. On the edges of each square are bits encoded with filled circles with diameter edge-length/3. A white circle represents a 1-Bit and a black circle represents a 0-Bit.

There are two binary base codes, each of size 3x167 bits. Each base code is a binary 3x3 sub-perfect map. This means that every possible 3x3 sub-pattern (with periodic extension of the pattern) occurs at most once in the given base pattern.

Let the base codes for the horizontal and vertical edges start with the following

code1 = 
[[0 0 0 0 1 ...]
 [0 1 1 0 0 ...]
 [0 1 0 0 0 ...]]

code2 = 
[[1 1 1 1 1 ...]
 [1 0 1 1 0 ...]
 [0 0 1 1 0 ...]]

Vertical edges are encoded with code1.

Vertical edges look like this:

* |         | ******* |         | ******* | ...
--+---------+---------+---------+---------+ ...
  | ******* |         | ******* |         | ...
  0 ******* 0         0 ******* 0         1 ...
  | ******* |         | ******* |         | ...
--+---------+---------+---------+---------+ ...
* |         | ******* |         | ******* | ...
* 0         1 ******* 1         0 ******* 0 ...
* |         | ******* |         | ******* | ...
--+---------+---------+---------+---------+ ...
  | ******* |         | ******* |         | ...
  0 ******* 1         0 ******* 0         0 ...
  | ******* |         | ******* |         | ...
--+---------+---------+---------+---------+ ...
* |         | ******* |         | ******* | ...
* 0         0 ******* 0         0 ******* 1 ... // repeat from here down
* |         | ******* |         | ******* | ...
--+---------+---------+---------+---------+ ...
       .
       .
       .

Horizontal edges are encoded with the transposed code2.

code2 (transposed) = 
[[1 1 0]
 [1 0 0]
 [1 1 1]
 [1 1 1]
 [1 0 0]
 ...]

Horizontal adges look like this:

                                | repeating from here ->
* |         | ******* |         | ******* | ...
--+----1----+----1----+----0----+----1----+ ...
  | ******* |         | ******* |         | ...
  | ******* |         | ******* |         | ...
  | ******* |         | ******* |         | ...
--+----1----+----0----+----0----+----1----+ ...
* |         | ******* |         | ******* | ...
* |         | ******* |         | ******* | ...
* |         | ******* |         | ******* | ...
--+----1----+----1----+----1----+----1----+ ...
  | ******* |         | ******* |         | ...
  | ******* |         | ******* |         | ...
  | ******* |         | ******* |         | ...
--+----1----+----1----+----1----+----1----+ ...
* |         | ******* |         | ******* | ...
* |         | ******* |         | ******* | ...
* |         | ******* |         | ******* | ...
--+----1----+----0----+----0----+----1----+ ...
       .
       .
       .

The resulting pattern looks like this:

                                | repeating from here ->
* |         | ******* |         | ******* | ...
--+----1----+----1----+----0----+----1----+ ...
  | ******* |         | ******* |         | ...
  0 ******* 0         0 ******* 0         1 ...
  | ******* |         | ******* |         | ...
--+----1----+----0----+----0----+----1----+ ...
* |         | ******* |         | ******* | ...
* 0         1 ******* 1         0 ******* 0 ...
* |         | ******* |         | ******* | ...
--+----1----+----1----+----1----+----1----+ ...
  | ******* |         | ******* |         | ...
  0 ******* 1         0 ******* 0         0 ...
  | ******* |         | ******* |         | ...
--+----1----+----1----+----1----+----1----+ ...
* |         | ******* |         | ******* | ...
* 0         0 ******* 0         0 ******* 1 ... // repeat from here down
* |         | ******* |         | ******* | ...
--+----1----+----0----+----0----+----1----+ ...
       .
       .
       .

Replacing the bits with black and white circles, the PuzzleBoard pattern emerges:

* |         | ******* |         | ******* | ...
--+---\ /---+---/ \---+---/*\---+---/ \---+ ...
  | ******* |         | ******* |         | ...
 (* ******* *)       (* ******* *)         )...
  | ******* |         | ******* |         | ...
--+---/ \---+---/*\---+---\*/---+---\ /---+ ...
* |         | ******* |         | ******* | ...
* *)         )*******(         (* ******* *)...
* |         | ******* |         | ******* | ...
--+---\ /---+---/ \---+---\ /---+---/ \---+ ...
  | ******* |         | ******* |         | ...
 (* *******(         (* ******* *)       (* ...
  | ******* |         | ******* |         | ...
--+---/ \---+---\ /---+---/ \---+---\ /---+ ...
* |         | ******* |         | ******* | ...
* *)       (* ******* *)       (* *******(  ...
* |         | ******* |         | ******* | ...
--+---\ /---+---\*/---+---/*\---+---/ \---+ ...
       .
       .
       .

Corner coordinates (x,y) in the puzzle are shown below:

    x -->
  * |0,0      |1,0 **** |2,0      |3,0 **** | ...
y --+---------+---------+---------+---------+--
|   | ******* |         | ******* |         | ...
|   | ******* |         | ******* |         | ...
V   |0,1 **** |1,1      |2,1 **** |3,1      | ...
  --+---------+---------+---------+---------+--
  * |         | ******* |         | ******* | ...
  * |         | ******* |         | ******* | ...
  * |0,2      |1,2 **** |2,2      |3,2 **** | ...
  --+---------+---------+---------+---------+--
    | ******* |         | ******* |         | ...
    | ******* |         | ******* |         | ...
    |0,3 **** |1,3      |2,3 **** |3,3      | ...
  --+---------+---------+---------+---------+--
  * |         | ******* |         | ******* | ...
  * |         | ******* |         | ******* | ...
  * |         | ******* |         | ******* | ...
  --+---------+---------+---------+---------+--
         .
         .
         .

code1, which is of size 3x167, is repeated 167 times vertically and 3 times horizontally, resulting in a pattern of 501x501 bits total size. The transposed code2, which is of size 167x3, is repeated 3 times vertically and 167 times horizontally, resulting in a pattern of 501x501 bits total size as well. Thus the whole pattern is of size 501x501. Since 3 and 167 are corime (both are primes), every local 3x3 pattern of puzzle pieces is unique up to translation. The base codes are chosen in a way, which ensures that more than 99 percent of all 3x3 patterns are also unique up to rotation (100 percent for 4x4 pieces).

Due to the periodicity of each isolated base pattern, every third row, respectively column can be combined by majority voting, which allows efficient error correction when a larger part of the pattern is visible. Moreover, the two base patterns have a high Hamming distance to each other and to translated and/or rotated versions of each other, such that the decoding can be done by using cross correlation, adding additional error correction capabilities.