Difference between revisions of "PlayChessWithAWebCam/BoardFinder"
| (34 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| + | [https://gitter.im/play-chess-with-a-webcam/community Click here to comment] | ||
| + | see {{Link|target=PlayChessWithAWebCam}} for the project the BoardFinder is used in | ||
| + | |||
= Source Code = | = Source Code = | ||
see [https://github.com/WolfgangFahl/play-chess-with-a-webcam/blob/master/pcwawc/boardfinder.py#L14 class BoardFinder] in module [https://github.com/WolfgangFahl/play-chess-with-a-webcam/blob/master/pcwawc/boardfinder.py boardfinder] | see [https://github.com/WolfgangFahl/play-chess-with-a-webcam/blob/master/pcwawc/boardfinder.py#L14 class BoardFinder] in module [https://github.com/WolfgangFahl/play-chess-with-a-webcam/blob/master/pcwawc/boardfinder.py boardfinder] | ||
| − | tests are in the | + | tests are in the [https://github.com/WolfgangFahl/play-chess-with-a-webcam/blob/master/tests/test_BoardFinder.py test_BoardFinder module] |
| + | |||
= Algorithm = | = Algorithm = | ||
== Finding the chessboard == | == Finding the chessboard == | ||
| Line 12: | Line 16: | ||
finder = BoardFinder(image,video=video) | finder = BoardFinder(image,video=video) | ||
</source> | </source> | ||
| − | === | + | === Finding the chessboard corners === |
| − | The find method starts the board finding. The Boardfinder will try out different patterns from 7x7 down to 3x3. Since a successfull find is much quicker than an unsuccessful one and since searching a small image is much faster than a big one the width of the searchImages can be specified. The default is 640 pixels. For the 13 tests images the search is even successful when the searchWidth is only 360 pixels. The difference in speed is approximately a factor of 1.5. | + | The find method starts the board finding. The Boardfinder will try out different patterns from 7x7 down to 3x3. In fact we only need to check: 7x7, 7x5, 5x5, 5x3, and 3x3 for want of an even number of squares to be detected. We do not try 9x9 which would give us the full 8x8 board since it's very unlikely that our real chessboard will fulfill the requirements of the OpenCV algorithm mentioned in it's footnote: " |
| + | |||
| + | '''Note''' | ||
| + | ''The function requires white space (like a square-thick border, the wider the better) around the board to make the detection more robust in various environments. Otherwise, if there is no border and the background is dark, the outer black squares cannot be segmented properly and so the square grouping and ordering algorithm fails''. " | ||
| + | |||
| + | Since a successfull find is much quicker than an unsuccessful one (a factor of some 6 to 40 times) and since searching a small image is much faster than a big one the width of the searchImages can be specified. The default is 640 pixels. For the 13 tests images the search is even successful when the searchWidth is only 360 pixels. The difference in speed is approximately a factor of 1.5. Searching 13 test images and creating all the debug images takes around 8 seconds. | ||
<source lang='python'> | <source lang='python'> | ||
found=finder.find(limit=1,searchWidth=360) | found=finder.find(limit=1,searchWidth=360) | ||
</source> | </source> | ||
| + | === Expanding the found corners === | ||
| + | Since we have used the OpenCV findChessBoard Corners not for it's intended purpose of camera calibration but for the detection of a real chessboard we have to adapt the result. The result of OpenCV's algorithm already gives us some hints e.g. whether the [https://lichess.org/editor board is empty] or [https://lichess.org/editor/rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR_w_KQkq_-_0_1 is filled with pieces] for the chess game's starting position. | ||
| + | ==== Found chesspoint order issue ==== | ||
| + | see | ||
| + | * https://stackoverflow.com/questions/19190484/what-is-the-opencv-findchessboardcorners-convention | ||
| + | * http://opencv-users.1802565.n2.nabble.com/FindChessboardCorners-ordering-td2122706.html | ||
| + | * https://dsp.stackexchange.com/questions/2805/how-does-opencv-find-chessboard-corners | ||
| + | looks like some sorting is necessary see e.g. | ||
| + | * https://stackoverflow.com/questions/56778645/issue-with-printing-when-using-sorted-function-on-drawchessboardcorners | ||
| + | * https://stackoverflow.com/questions/22232470/how-to-sort-found-chessboard-corners | ||
| + | looks like sorting by multiple columns is awkward in numpy see | ||
| + | * https://stackoverflow.com/questions/2706605/sorting-a-2d-numpy-array-by-multiple-axes | ||
=== Examples === | === Examples === | ||
| Line 23: | Line 44: | ||
[[File:chessBoard001.jpg|400px]][[File:image001-corners-7x7.jpg|400px]] | [[File:chessBoard001.jpg|400px]][[File:image001-corners-7x7.jpg|400px]] | ||
[[File:chessBoard002.jpg|400px]][[File:image002-corners-5x5.jpg|400px]] | [[File:chessBoard002.jpg|400px]][[File:image002-corners-5x5.jpg|400px]] | ||
| − | [[File:chessBoard003.jpg|400px]][[File:image003-corners- | + | [[File:chessBoard003.jpg|400px]][[File:image003-corners-3x7.jpg|400px]] |
[[File:chessBoard004.jpg|400px]][[File:image004-corners-7x7.jpg|400px]] | [[File:chessBoard004.jpg|400px]][[File:image004-corners-7x7.jpg|400px]] | ||
[[File:chessBoard005.jpg|400px]][[File:image005-corners-5x5.jpg|400px]] | [[File:chessBoard005.jpg|400px]][[File:image005-corners-5x5.jpg|400px]] | ||
| Line 30: | Line 51: | ||
[[File:chessBoard008.jpg|400px]][[File:image008-corners-7x7.jpg|400px]] | [[File:chessBoard008.jpg|400px]][[File:image008-corners-7x7.jpg|400px]] | ||
[[File:chessBoard009.jpg|400px]][[File:image009-corners-7x7.jpg|400px]] | [[File:chessBoard009.jpg|400px]][[File:image009-corners-7x7.jpg|400px]] | ||
| − | [[File:chessBoard010.jpg|400px]][[File:image010-corners- | + | [[File:chessBoard010.jpg|400px]][[File:image010-corners-5x5.jpg|400px]] |
[[File:chessBoard011.jpg|400px]][[File:image011-corners-7x7.jpg|400px]] | [[File:chessBoard011.jpg|400px]][[File:image011-corners-7x7.jpg|400px]] | ||
| − | [[File:chessBoard012.jpg|400px]][[File:image012-corners- | + | [[File:chessBoard012.jpg|400px]][[File:image012-corners-3x7.jpg|400px]] |
[[File:chessBoard013.jpg|400px]][[File:image013-corners-5x7.jpg|400px]] | [[File:chessBoard013.jpg|400px]][[File:image013-corners-5x7.jpg|400px]] | ||
==== Chessboard008 in detail ==== | ==== Chessboard008 in detail ==== | ||
| Line 38: | Line 59: | ||
[[File:image008-corners-7x7.jpg|600px]] | [[File:image008-corners-7x7.jpg|600px]] | ||
===== Polygons ===== | ===== Polygons ===== | ||
| − | The corners detected can be used to fill the 4 corner polygons. We don't know the colors yet | + | The corners detected can be used to fill the 4 corner polygons. |
| + | We don't know the colors of the squares yet but we know that a chessboard-pattern was found. | ||
| + | |||
| + | See https://codegolf.stackexchange.com/questions/63772/determine-the-color-of-a-chess-square for some fun code around the issue to determine whether a square is light or dark from its position. | ||
| + | |||
| + | For the time being we guess and might be wrong: | ||
[[File:image008-polygons-7x7.jpg|400px]] | [[File:image008-polygons-7x7.jpg|400px]] | ||
| + | |||
| + | Later we find the correct color: | ||
| + | [[File:image008-polygons-corrected-7x7.jpg|400px]] | ||
| + | |||
===== Masking ===== | ===== Masking ===== | ||
| − | To find out the colors we mask the detected squares. | + | To find out the colors we mask the detected squares. |
| + | |||
[[File:image008-masked-X--7x7.jpg|400px]] | [[File:image008-masked-X--7x7.jpg|400px]] | ||
[[File:image008-masked-O--7x7.jpg|400px]] | [[File:image008-masked-O--7x7.jpg|400px]] | ||
| − | ===== Histogram | + | ===== Histogram ===== |
| − | [[File:image008-histogram-7x7.jpg | + | Now we can create a histogram of the colors found in the two masks |
| + | [[File:image008-histogram-7x7.jpg]] | ||
| + | |||
| + | From now on we know which color is white/light and which one is black/dark. | ||
| + | |||
===== Color filtering ===== | ===== Color filtering ===== | ||
| + | Now we can filter the original image with the color ranges found in the mask / histogram steps. | ||
| + | |||
[[File:image008-colorFiltered-X--7x7.jpg|400px]] | [[File:image008-colorFiltered-X--7x7.jpg|400px]] | ||
[[File:image008-colorFiltered-O--7x7.jpg|400px]] | [[File:image008-colorFiltered-O--7x7.jpg|400px]] | ||
| + | ===== Expanding ===== | ||
| + | By extrapolating the found 7x7 chesspattern's quadrilateral (trapez) to it's 8x8 and 9x9 counterparts we can determine the location of the empty board and mask the image accordingly. | ||
| + | [[File:image008-trapez-7x7.jpg|400px]] | ||
| + | [[File:image008-trapez-masked-7x7.jpg|400px]] | ||
| + | ===== Color filtering the background ===== | ||
| + | When we filter the field colors as per the histograms for an empty board we should get a fully black result. At this point we don't yet: | ||
| + | [[File:image008-colorFiltered-background--7x7.jpg|400px]] | ||
| + | The original histogram was not "wide" enough: | ||
| + | [[File:image008-histogram-7x7-2019-12-03jpg.jpg|400px]] | ||
| + | |||
| + | For a filled board therefore there is still some background noise in the background filtered picture (chessboard013) | ||
| + | [[File:Clipboard20191203060734.png|400px]] | ||
Latest revision as of 07:39, 3 December 2019
Click here to comment see PlayChessWithAWebCam for the project the BoardFinder is used in
Source Code
see class BoardFinder in module boardfinder tests are in the test_BoardFinder module
Algorithm
Finding the chessboard
OpenCV has a function findChessboardCorners which is usually used for camera calibration and not really intended for the use case of "real chessboards".
Still it is very helpful and used as a basis for the BoardFinder.
Initializing the BoardFinder
The board finder is initialized with an image. Optionally you can specify the Video instance to be used.
finder = BoardFinder(image,video=video)
Finding the chessboard corners
The find method starts the board finding. The Boardfinder will try out different patterns from 7x7 down to 3x3. In fact we only need to check: 7x7, 7x5, 5x5, 5x3, and 3x3 for want of an even number of squares to be detected. We do not try 9x9 which would give us the full 8x8 board since it's very unlikely that our real chessboard will fulfill the requirements of the OpenCV algorithm mentioned in it's footnote: "
Note The function requires white space (like a square-thick border, the wider the better) around the board to make the detection more robust in various environments. Otherwise, if there is no border and the background is dark, the outer black squares cannot be segmented properly and so the square grouping and ordering algorithm fails. "
Since a successfull find is much quicker than an unsuccessful one (a factor of some 6 to 40 times) and since searching a small image is much faster than a big one the width of the searchImages can be specified. The default is 640 pixels. For the 13 tests images the search is even successful when the searchWidth is only 360 pixels. The difference in speed is approximately a factor of 1.5. Searching 13 test images and creating all the debug images takes around 8 seconds.
found=finder.find(limit=1,searchWidth=360)
Expanding the found corners
Since we have used the OpenCV findChessBoard Corners not for it's intended purpose of camera calibration but for the detection of a real chessboard we have to adapt the result. The result of OpenCV's algorithm already gives us some hints e.g. whether the board is empty or is filled with pieces for the chess game's starting position.
Found chesspoint order issue
see
- https://stackoverflow.com/questions/19190484/what-is-the-opencv-findchessboardcorners-convention
- http://opencv-users.1802565.n2.nabble.com/FindChessboardCorners-ordering-td2122706.html
- https://dsp.stackexchange.com/questions/2805/how-does-opencv-find-chessboard-corners
looks like some sorting is necessary see e.g.
- https://stackoverflow.com/questions/56778645/issue-with-printing-when-using-sorted-function-on-drawchessboardcorners
- https://stackoverflow.com/questions/22232470/how-to-sort-found-chessboard-corners
looks like sorting by multiple columns is awkward in numpy see
Examples
Chessboard008 in detail
Polygons
The corners detected can be used to fill the 4 corner polygons. We don't know the colors of the squares yet but we know that a chessboard-pattern was found.
See https://codegolf.stackexchange.com/questions/63772/determine-the-color-of-a-chess-square for some fun code around the issue to determine whether a square is light or dark from its position.
For the time being we guess and might be wrong:
Later we find the correct color:
Masking
To find out the colors we mask the detected squares.
Histogram
Now we can create a histogram of the colors found in the two masks
From now on we know which color is white/light and which one is black/dark.
Color filtering
Now we can filter the original image with the color ranges found in the mask / histogram steps.
Expanding
By extrapolating the found 7x7 chesspattern's quadrilateral (trapez) to it's 8x8 and 9x9 counterparts we can determine the location of the empty board and mask the image accordingly.
Color filtering the background
When we filter the field colors as per the histograms for an empty board we should get a fully black result. At this point we don't yet:
The original histogram was not "wide" enough:
For a filled board therefore there is still some background noise in the background filtered picture (chessboard013)
