Checkerboard Corner Detection

hardPROCamera CalibrationCalibrationCV: Structure from Motion and SLAM

Implement simplified checkerboard corner detection for camera calibration, a crucial step in Structure from Motion and SLAM. This task involves identifying the corners of a checkerboard pattern in an image, which is essential for estimating camera parameters.

Checkerboard corners are used in camera calibration because they provide high precision, known 3D geometry, and are easy to detect. The corners of a checkerboard can be represented by a grid of points in 3D space, with each point having a known position $x_i, y_i, z_i$ . When projected onto a 2D image, these points form a grid of corners, which can be detected using corner detection algorithms.

To detect these corners, the following steps are involved:

Apply a corner detector to the image, which calculates the Harris response $R = \det(\mathbf{M}) - k \cdot \operatorname{tr}^2(\mathbf{M})$ , where $\mathbf{M}$ is the structure tensor.
Filter the detected corners by their pattern, ensuring they form a grid.
Refine the corner locations to sub-pixel accuracy.

Return the corners as $(x, y)$ pixel coordinates (exactly rows $\times$ cols of them), or None if fewer corners than that are found.

R = \det\begin{bmatrix} I_{xx} & I_{xy} \\ I_{xy} & I_{yy} \end{bmatrix} - k \cdot (I_{xx} + I_{yy})^2

This technique is widely used in robotics and computer vision applications, such as autonomous vehicles and augmented reality systems.

Example

Input

image = checkerboard image
board_size = (6, 9)  # 6×9 internal corners

Output

List of 54 corner coordinates

Reasoning

Input: image is a $140 \times 200$ grayscale array of $20 \times 20$ px squares (7 $\times$ 10 squares). board_size = (6, 9) counts internal corners, where four squares meet: $x \in \{20, 40, \dots, 180\}$ , $y \in \{20, 40, \dots, 120\}$ .
Structure tensor at a true corner such as $(20, 20)$ both directions change, so $I_{xx} \approx I_{yy} \approx 2.81 \times 10^5$ and $I_{xy} \approx 143$ . Then $\det \approx 7.88 \times 10^{10}$ , $(I_{xx}+I_{yy})^2 \approx 3.15 \times 10^{11}$ and, with $k = 0.04$ , $R \approx 6.6 \times 10^{10}$ , the maximum of $R$ , shared by every internal corner.
On an edge such as $(20, 10)$ : only one direction changes ( $I_{yy} = I_{xy} = 0$ , $I_{xx} \approx 3.9 \times 10^5$ ), so $\det = 0$ and $R \approx -6.1 \times 10^9$ . Flat interiors give $R = 0$ .
Output: a list of $6 \times 9 = 54$ $(x, y)$ points at the strong positive peaks of $R$ , row by row.
A blank image has no gradients, so $R = 0$ everywhere and the result is None.

Constraints

image: Grayscale image with checkerboard
board_size: (rows, cols) of internal corners
Return: List of corner coordinates

Learn this in

Camera Models & Calibration3D Computer Vision

More from CV: Structure from Motion and SLAM

Map Point Visibility Testhard Triangulation of 3D Pointsmedium PnP Pose from Correspondencesmedium Range-Bearing Observationmedium Odometry Pose Updateeasy

Concept primerPREVIEW

Camera calibration with checkerboards relies on detecting a regular grid of high-contrast corners and matching them to known 3D points on the calibration plate. Each black–white intersection is a strong corner: image intensity changes sharply in two orthogonal directions, and the 3D layout of these corners (typically a flat grid in the $z=0$ plane) is known precisely. Once these 2D–3D correspondences are available, standard calibration methods (e.g., Zhang’s method) estimate intrinsic parameters (focal length, principal point, distortion) and extrinsic pose for each image.

Corner detectors like Harris or FAST respond wherever there is a local 2D intensity structure that is not well explained by a single edge or flat region. Checkerboard “X-corners” are ideal: they are stable under small viewpoint changes and support sub-pixel localization by fitting a local intensity model or optimizing a local cost function. The extra difficulty in checkerboard detection is not finding some corners, but selecting only those that form a consistent grid pattern in the right order, and refining their positions to sub-pixel accuracy for high-precision calibration.

1. Background Knowledge (key concepts)

Corner detection (Harris / FAST)
A corner is a point where image intensity changes significantly in both $x$ and $y$ directions.
Harris uses the second-moment matrix of gradients in a local window and looks at its eigenvalues; both large ⇒ corner.
FAST uses a circle test around the pixel for rapid detection: if a contiguous arc of pixels is all brighter or darker than the center by a threshold, it flags a corner.
Checkerboard structure
Corners lie on roughly straight rows and columns with constant spacing (up to perspective distortion).
Each valid corner belongs to exactly four squares with alternating black/white pattern (an “X-corner”).
Geometrically, the set of corners lies on a planar grid that becomes a projective transform (homography) of a regular grid in the image.
Sub-pixel refinement
Initial corner detection gives integer-pixel coordinates.
For calibration, we refine to sub-pixel by:
Fitting a quadratic to the corner response map, or
Fitting an intensity model to the local patch, or
Using built-in routines like cv::cornerSubPix.
This reduces reprojection error and improves calibration stability.

2. Algorithm / Approach Pattern

The overall pattern is:

Detect many raw corners using a generic detector (Harris or FAST).
Filter and group these corners into a structure that matches a checkerboard:

Enforce geometric constraints (grid-like rows/columns, roughly uniform spacing, planarity).
Optionally, validate the local intensity pattern (black–white–black–white around the corner).

Order the corners into a consistent $(i, j)$ grid (e.g., top-left to bottom-right).
Refine positions of the selected corners to sub-pixel precision.
(Outside this problem) Feed these 2D points with known 3D grid coordinates to a calibration routine.

This is an example of: generic detection → pattern-specific filtering → geometric reasoning → local refinement.

3. Step-by-Step Strategy

Step 1: Preprocessing (optional but helpful)

Convert to grayscale.
Optionally apply:
Slight Gaussian blur to reduce noise.
Contrast normalization (e.g., histogram equalization) if illumination is poor.

Step 2: Corner detection

Use Harris or FAST (often available in libraries):

# Example with OpenCV-like API (conceptual)
gray = to_grayscale(img)
corners = harris_detect(gray) # or fast_detect(gray)

Keep:
A response map (Harris score) or list of keypoints.
Apply non-maximum suppression and a threshold to remove weak / duplicate corners.

Step 3: Initial filtering and clustering

Goal: remove corners that obviously cannot belong to the checkerboard.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results