Chessboard detection: Difference between revisions

Revision as of 22:24, 3 December 2014

Latest revision as of 02:05, 22 January 2025

(25 intermediate revisions by 19 users not shown)

Line 1:

{{FeatureDetectionCompVisNavbox}}

Chessboards[[Chessboard]]s arise frequently in [[Computer_vision| computer vision]] theory and practice because their highly structured geometry is well-suited for algorithmic [[Detection| detection]] and processing. The appearance of chessboards in computer vision can be divided into two main areas: [[Camera_resectioning|Camera resectioning|camera calibration]] and [[Feature_Feature (computer_visioncomputer vision)| feature extraction]]. This article provides a unified discussion of the role that chessboards play in the canonical methods from these two areas, including references to the seminal literature, examples, and pointers to software implementations.

==Chessboard camera calibration==

A classical problem in computer vision is [[3D_reconstruction_from_multiple_images|3D reconstruction from multiple images|three-dimensional (3D) reconstruction]], where one seeks to infer 3D structure about a scene from two-dimensional (2D) images of it.<ref name=forsyth2002>D. Forsyth and J. Ponce. ''Computer Vision: A Modern Approach''. Prentice Hall. (2002). [http://www.amazon.com/Computer-Vision-Modern-Approach-Edition/dp/013608592X {{ISBN |978-0262061582]}}.</ref> Practical cameras are complex devices, and [[Photogrammetry| photogrammetry]] is needed to model the relationship between image sensor measurements and the 3D world. In the standard [[Pinhole_camera_model| pinhole camera model]], one models the relationship between world coordinates <math>\mathbf{X}</math> and image (pixel) coordinates <math>\mathbf{x}</math> via the [[3D_projection|3D projection|perspective transformation]]

:<math>

Line 11:

</math>

where <math>\mathbb{P}^n</math> is the [[Projective_space| projective space]] of dimension <math>n</math>.

In this setting, [[Camera_resectioning|Camera resectioning|camera calibration]] is the process of estimating the parameters of the <math>3 \times 4</math> matrix <math>M = K \begin{bmatrix} R & t \end{bmatrix}</math> of the perspective model. Camera calibration is an important step in the computer vision pipeline because many subsequent algorithms require knowledge of camera parameters as input.<ref name=szeliski2010>R. Szeliski. ''Computer Vision: Algorithms and Applications''. Springer Science and Business Media. (2010). [http://www.springer.com/computer/image+processing/book/978-1-84882-934-3 {{ISBN |978-1848829350]}}.</ref> Chessboards are often used during camera calibration because they are simple to construct, and their planar grid structure defines many natural [[Interest_point_detection|Interest point detection|interest points]] in an image. The following two methods are classic calibration techniques that often employ chessboards.

===Direct linear transformation===

Direct linear transformation (DLT) calibration uses correspondences between world points and camera image points to estimate camera parameters. In particular, DLT calibration exploits the fact thethat the perspective pinhole camera model defines a set of similarity relations that can be solved via the [[Direct_linear_transformation| direct linear transformation]] algorithm.<ref name=faugeras1993>O. Faugeras. ''Three-dimensional Computer Vision''. MIT Press. (1993). [http://www.amazon.com/Three-Dimensional-Computer-Vision-Artificial-Intelligence/dp/0262061589 {{ISBN |978-0262061582]}}.</ref> To employ this approach, one requires accurate coordinates of a non-degenerate set of points in 3D space. A common way to achieve this is to construct a camera calibration rig (example below) built from three mutually perpendicular chessboards. Since the corners of each square are equidistant, it is straightforward to compute the 3D coordinates of each corner given the width of each square. The advantage of DLT calibration is its simplicity; arbitrary cameras can be calibrated by solving a single [[System_of_linear_equationsSystem of linear equations#Homogeneous_systems|Homogeneous systems|homogeneous linear system]]. However, the practical use of DLT calibration is limited by the necessity of a 3D calibration rig and the fact that extremely accurate 3D coordinates are required to avoid [[Numerical_stability|Numerical stability|numerical instability]].<ref name=forsyth2002/>

{{multiple image

{{Auto images

|title=Example: calibration rig

|align=center

Line 29:

===Multiplane calibration===

Multiplane calibration is a variant of [[Camera_auto-calibration| camera auto-calibration]] that allows one to compute the parameters of a camera from two or more views of a planar surface. The seminal work in multiplane calibration is due to Zhang.<ref name=zhang2000>Z. Zhang. "A flexible new technique for camera calibration." IEEE Transactions on Pattern Analysis and Machine Intelligence. vol. 22(11), pp. 1330-1334 (2000).</ref> [[Camera_resectioningCamera resectioning#Zhang.27s_method|27s method|Zhang's method]] calibrates cameras by solving a particular [[System_of_linear_equationsSystem of linear equations#Homogeneous_systems|Homogeneous systems|homogeneous linear system]] that captures the homographic relationships between multiple perspective views of the same plane. This multiview approach is popular because, in practice, it is more natural to capture multiple views of a single planar surface - like a chessboard - than to construct a precise 3D calibration rig, as required by DLT calibration. The following figures demonstrate a practical application of multiplane camera calibration from multiple views of a chessboard.<ref name=bouguet2013>J. Bouguet, "Camera calibration toolbox for MATLAB". http://www.vision.caltech.edu/bouguetj/calib_doc/. (2013).</ref>

{{multiple image

{{Auto images

|title=Example: multiplane calibration

|align=center

|text_align=center

|total_width=900

|width1=1128|height1=678|image1=Multiple chessboard views.png|caption1=Multiple views of a chessboard for [[Camera_autoCamera auto-calibration| multiplane calibration]]

|width2= 507|height2=384|image2=Reconstructed boards camera.png|caption2=Reconstructed orientations <br /> (camera-centric coordinates)

|width3= 529|height3=471|image3=Reconstructed boards world.png|caption3=Reconstructed orientations <br /> (world-centric coordinates)

Line 43:

==Chessboard feature extraction==

The second context in which chessboards arise in computer vision is to demonstrate several canonical [[Feature_extraction| feature extraction]] algorithms. In [[Feature_extraction| feature extraction]], one seeks to identify image [[Interest_point_detection|Interest point detection|interest points]], which summarize the semantic content of an image and, hence, offer a [[Dimensionality_reductionDimensionality reduction| reduced dimensionality]] representation of one's data.<ref name=szeliski2010/> Chessboards - in particular - are often used to demonstrate feature extraction algorithms because their regular geometry naturally exhibits local image features like edges, lines, and corners. The following sections demonstrate the application of common feature extraction algorithms to a [[:Image:Perspective chessboard.png| chessboard image]].

===Corners===

Corners are a natural local image feature exploited in many computer vision systems. Loosely speaking, one can define a ''corner'' as the intersection of two edges. A variety of [[Corner_detection| corner detection]] algorithms exist that formalize this notion into concrete algorithms. Corners are a useful image feature because they are necessarily distinct from their neighboring pixels. The [[Corner_detectionCorner detection#The_Harris_The Harris .26_Stephens_26 Stephens .2F_Plessey_2F Plessey .2F_Shi2F Shi.E2.80.93Tomasi_corner_detection_algorithm|93Tomasi corner detection algorithm|Harris corner detector]] is a standard algorithm for corner detection in computer vision.<ref name=harris1998>C. Harris and M. Stephens. "A combined corner and edge detector." Proceedings of the 4th Alvey Vision Conference. pp. 147-151 (1988).</ref>. The algorithm works by analyzing the [[Eigenvalues_and_eigenvectors|Eigenvalues and eigenvectors|eigenvalues]] of the 2D discrete [[Structure_tensor| structure tensor]] matrix at each image pixel and flagging a pixel as a corner when the eigenvalues of its structure tensor are sufficiently large. Intuitively, the eigenvalues of the structure tensor matrix associated with a given pixel describe the gradient strength in a neighborhood of that pixel. As such, a structure tensor matrix with large eigenvalues corresponds to an image neighborhood with large gradients in orthogonal directions - ''i.e.,'' a corner.

A chessboard contains natural corners at the boundaries between board squares, so one would expect corner detection algorithms to successfully detect them in practice. Indeed, the following figure demonstrates Harris corner detection applied to a perspective-transformed [[:Image:Perspective chessboard.png| chessboard image]]. Clearly, the Harris detector is able to accurately detect the corners of the board.

{{multiple image

{{Auto images

|title=Example: corner detection

|align=center

Line 57:

|total_width=600

|width1=767|height1=548|image1=Perspective chessboard.png|caption1=Perspective-transformed chessboard image

|width2=767|height2=548|image2=Harris corners detected on chessboard.png|caption2=Output of [[Corner_detectionCorner detection#The_Harris_The Harris .26_Stephens_26 Stephens .2F_Plessey_2F Plessey .2F_Shi2F Shi.E2.80.93Tomasi_corner_detection_algorithm|93Tomasi corner detection algorithm|Harris corner detector]]

}}

The following [[MATLAB| MATLAB]] code generates the above image using the [http://www.mathworks.com/products/image/ Image Processing Toolbox]:

<source lang="matlab">

% Load image

I = imread('Perspective_chessboard.png');

% Detect corners

C = corner(I,'Harris');

%--------------------------------------------------------------------------

% Display results

%--------------------------------------------------------------------------

% Original image

figure; imshow(I);

% Detected corners

figure; imshow(I); hold on;

plot(C(:,1),C(:,2),'ro');

%--------------------------------------------------------------------------

</source>

===Lines===

Lines are another natural local [[Feature_Feature (computer_visioncomputer vision)| image feature]] exploited in many computer vision systems. Geometrically, the set of all lines in a 2D image can be parametrized by [[Polar_coordinate_system|Polar coordinate system|polar coordinates]] <math>(\rho,\theta)</math> describing the distance and angle, respectively, of their [[Normal_Normal (geometry)| normal vectors]] with respect to the origin. The discrete [[Hough_transform| Hough transform]] exploits this idea by transforming a spatial image into a matrix in <math>(\rho,\theta)</math>-space whose <math>(i,j)</math>-th entry counts the number of image edge points that lie on the line parametrized by <math>(\rho_i,\theta_j)</math>.<ref name=shapiro2001>L. Shapiro and G. Stockman. ''Computer Vision''. Prentice-Hall, Inc. (2001). [http://www.amazon.com/Computer-Vision-Linda-G-Shapiro/dp/0130307963 {{ISBN |978-0130307965]}}</ref><ref name=duda1972>R. Duda and P. Hart. "Use of the Hough transformation to detect lines and curves in pictures," Comm. ACM, vol. 15, pp. 11-15 (1972).</ref><ref name=hough1959>P. Hough. "Machine analysis of bubble chamber pictures." Proc. Int. Conf. High Energy Accelerators and Instrumentation. (1959).</ref> As such, one can detect lines in an image by simply searching for [[Maxima_and_minima|Maxima and minima|local maxima]] of its discrete Hough transform.

The grid structure of a chessboard naturally defines two sets of parallel lines in an image of it. Therefore, one expects that line detection algorithms should successfully detect these lines in practice. Indeed, the following figure demonstrates Hough transform-based line detection applied to a perspective-transformed [[:Image:Perspective chessboard.png| chessboard image]]. Clearly, the Hough transform is able to accurately detect the lines induced by the board squares.

{{multiple image

{{Auto images

|title=Example: line detection

|align=center

|text_align=center

|total_width=12001000

|width1=767|height1=548|image1=Perspective chessboard.png|caption1=Perspective-transformed chessboard image

|width2=767|height2=548|image2=Perspective chessboard edges.png|caption2=[[Canny_edge_detector| Canny edge detector]] applied to chessboard image

|width3=767|height3=548|image3=Perspective chessboard hough transform.png|caption3=[[Hough_transform| Hough transform]] of edge image with 19 largest local maxima denoted

|width4=767|height4=548|image4=Perspective chessboard detected lines.png|caption4=Lines parameterized by [[Hough_transform| Hough transform]] local maxima

}}

The following [[MATLAB| MATLAB]] code generates the above images using the [http://www.mathworks.com/products/image/ Image Processing Toolbox]:

<sourcesyntaxhighlight lang="matlab">

% Load image

I = imread('Perspective_chessboard.png');

% Compute edge image

BW = edge(I, 'canny');

% Compute Hough transform

Line 114 ⟶ 92:

numpeaks = 19;

thresh = ceil(0.1 * max(H(:)));

P = houghpeaks(H, numpeaks, 'threshold', thresh);

% Extract image lines

lines = houghlines(BW, theta, rho, P, 'FillGap', 50, 'MinLength', 60);

% --------------------------------------------------------------------------

% Display results

% --------------------------------------------------------------------------

% Original image

figure; imshow(I);

Line 129 ⟶ 107:

% Hough transform

figure; image(theta, rho, imadjust(mat2gray(H)), 'CDataMapping', 'scaled');

hold on; colormap(gray(256));

plot(theta(P(:, 2)), rho(P(:, 1)), 'o', 'color', 'r');

% Detected lines

figure; imshow(I); hold on; n = size(I, 2);

for k = 1:length(lines)

% Overlay kth line

Line 140 ⟶ 118:

y = [lines(k).point1(2) lines(k).point2(2)];

line = @(z) ((y(2) - y(1)) / (x(2) - x(1))) * (z - x(1)) + y(1);

plot([1 n], line([1 n]), 'Color', 'r');

end

</syntaxhighlight>

%--------------------------------------------------------------------------

</source>

==ConclusionLimitations==

The main limitation of using chessboard patterns for geometric camera calibration is that due to their highly repetitive structure, they need to be completely visible in the camera image. This assumption may be violated e.g. when specular reflections due to inhomogenous lighting cause chessboard detection to fail in some of the corners. The measurement of camera distortions close to the image corners is also altered by the need of a completely visible chessboard target.

Chessboards are ubiquitous is computer vision because they provide a convenient way to benchmark/verify many common calibration and feature extraction algorithms.

To solve this issue, chessboard targets can be combined with some position encoding. One popular way is to place ArUco markers<ref name=gerrido2014>S. Garrido-Jurado et al. "Automatic generation and detection of highly reliable fiducial markers under occlusion." Pattern Recognition, vol. 47(6), pp. 2280-2292. https://dl.acm.org/doi/abs/10.1016/J.PATCOG.2014.01.005. (2014).</ref> inside the lightchessboard squares. The main advantage of such ChArUco targets<ref name=opencv>OpenCV. https://docs.opencv.org/3.4/df/d4a/tutorial_charuco_detection.html.</ref> is that all light chessboard squares are uniquely coded and identifiable. This also allows to do single image multiplane calibration by placing multiple targets with different ArUco in one scene.

==See also==

An alternative way for adding position encoding to chessboard patterns is the PuzzleBoard pattern:<ref name=stelldinger2024>P. Stelldinger, et al. "PuzzleBoard: A New Camera Calibration Pattern with Position Encoding." German Conference on Pattern Recognition. (2024). https://users.informatik.haw-hamburg.de/~stelldinger/pub/PuzzleBoard/. (2024).</ref> Each chessboard edge is given one bit of information such that local parts of the pattern show a unique bit pattern. In comparison to ChArUco patterns, the position encoding can be read at much lower resolutions.

*[[Computer_vision| Computer vision]]

*[[Projective_geometry| Projective geometry]]

*[[Pinhole_camera| Pinhole camera]]

*[[Photogrammetry| Photogrammetry]]

*[[Camera_resectioning| Camera calibration]]

*[[Feature_detection_(computer_vision)| Feature detection]]

*[[Feature_extraction| Feature extraction]]

*[[Canny_edge_detector| Canny edge detection]]

*[[Corner_detection| Corner detection]]

*[[Structure_tensor| Structure tensor matrix]]

*[[Hough_transform| Hough transform]]

[[File:PuzzleBoard8x11.jpg|thumb|center|500px|alt=An example of a PuzzleBoard pattern with 8x11 chessboard corners.|An example of a PuzzleBoard pattern with 8x11 chessboard corners. Each 3x3 tile pattern is unique.]]

==External links==

==See also==

The following links are pointers to popular [[MATLAB| MATLAB]] and [[OpenCV| OpenCV]] implementations of chessboard-related computer vision algorithms.

* [http://www.vision.caltech.edu/bouguetj/calib_doc/ Camera Calibration Toolbox for MATLAB] - MATLAB toolbox implementing many common camera calibration methods

*[[Computer_vision| Computer vision]]

* [http://docs.opencv.org/modules/calib3d/doc/camera_calibration_and_3d_reconstruction.html Camera Calibration and 3D Reconstruction] - OpenCV implementation of many common camera calibration methods

*[[Projective_geometry| Projective geometry]]

* [http://www.vision.caltech.edu/bouguetj/calib_doc/htmls/example.html Multiplane Camera Calibration From Multiple Chessboard Views] - MATLAB example of applying multiview auto-calibration to a series of chessboard images

*[[Pinhole_camera| Pinhole camera]]

* [http://www.mathworks.com/help/vision/ref/detectcheckerboardpoints.html MATLAB chessboard detection] - MATLAB function from the [http://www.mathworks.com/products/computer-vision/ Computer Vision System Toolbox] for detecting chessboards in images

*[[Photogrammetry| Photogrammetry]]

* [http://docs.opencv.org/doc/tutorials/calib3d/camera_calibration_square_chess/camera_calibration_square_chess.html OpenCV chessboard detection] - OpenCV function for detecting chessboards in images

*[[Camera_resectioning|Camera resectioning|Camera calibration]]

* [http://www.mathworks.com/help/images/ref/corner.html MATLAB Harris corner detection] - MATLAB function for performing Harris corner detection

*[[Feature_detection_Feature detection (computer_visioncomputer vision)| Feature detection]]

* [http://docs.opencv.org/doc/tutorials/features2d/trackingmotion/harris_detector/harris_detector.html OpenCV Harris corner detection] - OpenCV function for performing Harris corner detection

*[[Feature_extraction| Feature extraction]]

* [http://www.mathworks.com/help/images/hough-transform.html MATLAB Hough transform] - MATLAB function for computing the Hough transform

*[[Canny_edge_detector|Canny edge detector|Canny edge detection]]

* [http://docs.opencv.org/doc/tutorials/imgproc/imgtrans/hough_lines/hough_lines.html OpenCV Hough transform] - OpenCV function for computing the Hough transform

*[[Corner_detection| Corner detection]]

*[[Structure_tensorStructure tensor| Structure tensor matrix]]

*[[Hough_transform| Hough transform]]

==Further reading==

Line 180 ⟶ 150:

# M. Rufli, D. Scaramuzza, and R. Siegwart. "Automatic detection of checkerboards on blurred and distorted images." IEEE/RSJ International Conference on Intelligent Robots and Systems. (2008).

# Z. Weixing, et al. "A fast and accurate algorithm for chessboard corner detection." 2nd International Congress on Image and Signal Processing. (2009).

# A. De la Escalera and J. Armingol. "Automatic chessboard detection for intrinsic and extrinsic camera parameter calibration." Sensors. vol. 10(3), pp. 2027-2044&nbsp;2027–2044 (2010).

# S. Bennett and [[Joan Lasenby|J. Lasenby]]. "ChESS - quick and robust detection of chess-board features." Computer Vision and Image Understanding. vol. 118, pp. 197-210&nbsp;197–210 (2014).

# J. Ha. "Automatic detection of chessboard and its applications." Opt. Eng. vol. 48(6) (2009).

# F. Zhao, et al. "An automated x-corner detection algorithm (axda)." Journal of Software. vol. 6(5), pp. 791-797&nbsp;791–797 (2011).

# S. Arca, E. Casiraghi, and G. Lombardi. "Corner localization in chessboards for camera calibration." IADAT. (2005).

# X. Hu, P. Du, and Y. Zhou. "Automatic corner detection of chess board for medical endoscopy camera calibration." Proceedings of the 10th International Conference on Virtual Reality Continuum and Its Applications in Industry. ACM. (2011).

Line 191 ⟶ 161:

<references/>

==External links==

[[:Category:Feature detection (computer vision)]]

The following links are pointers to popular [[MATLAB| MATLAB]] and [[OpenCV| OpenCV]] implementations of chessboard-related computer vision algorithms.

* [http://www.vision.caltech.edu/bouguetj/calib_doc/ Camera Calibration Toolbox for MATLAB] - MATLAB toolbox implementing many common camera calibration methods

* [http://docs.opencv.org/modules/calib3d/doc/camera_calibration_and_3d_reconstruction.html Camera Calibration and 3D Reconstruction] - OpenCV implementation of many common camera calibration methods

* [http://www.vision.caltech.edu/bouguetj/calib_doc/htmls/example.html Multiplane Camera Calibration From Multiple Chessboard Views] - MATLAB example of applying multiview auto-calibration to a series of chessboard images

* [http://www.mathworks.com/help/vision/ref/detectcheckerboardpoints.html MATLAB chessboard detection] - MATLAB function from the [http://www.mathworks.com/products/computer-vision/ Computer Vision System Toolbox] for detecting chessboards in images

* [http://docs.opencv.org/doc/tutorials/calib3d/camera_calibration_square_chess/camera_calibration_square_chess.html OpenCV chessboard detection] - OpenCV function for detecting chessboards in images

* [http://www.mathworks.com/help/images/ref/corner.html MATLAB Harris corner detection] - MATLAB function for performing Harris corner detection

* [http://docs.opencv.org/doc/tutorials/features2d/trackingmotion/harris_detector/harris_detector.html OpenCV Harris corner detection] - OpenCV function for performing Harris corner detection

* [http://www.mathworks.com/help/images/hough-transform.html MATLAB Hough transform] - MATLAB function for computing the Hough transform

* [http://docs.opencv.org/doc/tutorials/imgproc/imgtrans/hough_lines/hough_lines.html OpenCV Hough transform] - OpenCV function for computing the Hough transform

* [https://github.com/dkogan/mrgingham/ mrgingham] - tool for detection of chessboards

[[:Category:Feature detection (computer vision)]]