Chess Segmentation
•Download as PPT, PDF•
0 likes•1,246 views
The document describes a chessboard segmentation algorithm with the following steps: 1. Detect the borders of the chessboard using Hough transform or normalized cross correlation. 2. Split the board into squares by detecting dominant color values and iterating on x and y axes. 3. Classify each square as empty or containing a piece using standard deviation thresholds or a 40-dimensional feature space considering pixel ratios and piece border positions. 4. Produce a FEN notation for the detected board. The algorithm achieved accuracy from 55% to 100% on test images but requires further refinement, expanded training data, and optimized code.
Chess Segmentation
- 1. Chess Segmentation by Statis Grigoropoulos © 2012
- 2. Chess Segmentation • The Problem • Ways of Approach • Implementation • Results • Suggestions for Improvement • Conclusion Page 2 Chess Segmentation 4/13/2012
- 3. The Problem • Detect chessboard segmentation in an image • classify the chess pieces found in the segmented chessboard. • provide a correct FEN notation for the detected chessboard(s) Page 3 Chess Segmentation © 2012
- 4. The Algorithm • Step 1: Find internal borders of the chessboard(s)( i.e detect chessboard) • Step 2: Spit the squares for each chessboard • Step 3: Detect the piece inside the square • Step 4: Produce FEN notation Page 4 Chess Segmentation © 2012
- 5. Step 1: Find the Borders • Ways of Approach: -Hough Transform -Norm. Cross Correlation  Page 5 Template : Chess Segmentation © 2012
- 6. Step 1: Find the Borders • Hough Transform :MATLAB(single case) Page 6 Chess Segmentation © 2012
- 7. Step 1: Find the Borders • Hough Transform :MATLAB(real case) Page 7 Chess Segmentation © 2012
- 8. Step 1: Find the Borders • Norm. Cross Correlation :MATLAB Page 8 Chess Segmentation © 2012
- 9. Step 2: Splitting the Squares • Step 1: Compute the histogram of the • • • • chessboard Step 2: Detect the dominant values of the histogram Step 3: Classify the dominant values with a confidence interval as the white and black square background Step 4: Iterate on the x and y axis and catch the interchange of the values Page 9 Chess Segmentation © 2012
- 10. Step 2: Splitting the Squares Confidence interval = 10%= 25 Page 10 Chess Segmentation © 2012
- 11. Step 3: Classify Square Empty Squares -Standard Deviation • A way to measure the distance of values from the mean Expected low value of standard deviation in empty squares : s.d. < 25(10%)?? -Histogram bins Page 11 Chess Segmentation © 2012
- 12. Step 3: Classify Square s.d. =~ 20 s.d. =~ 11 s.d. =~ 30(!) Page 12 Chess Segmentation © 2012
- 13. Step 3: Classify Square • Square containing a Piece - Rich Feature Space - Simple Mean Classifier  The Method:   Page 13 Shrink-to-fit Compute Characteristics Chess Segmentation © 2012
- 14. Step 3: Classify Square Square Containing a Piece -The Features: 1. Normalized Histogram (dropped) 2. Compute the ratio of dark pixels in square(1) 3. Spit the Square in a 3x3 grid 4. Compute the relative ratio of dark pixels in each region(9) • Page 14 Chess Segmentation © 2012
- 15. Step 3: Classify Square Square Containing a Piece -The Features(cont.): 5. Spit the square in a 5x5 grid 6. Compute the Relative Position of the border of the shape (chess piece) along the lines of the grid, in each direction(20) 7. Compute the relative ratio of dark pixels along each line of the grid(10) Result : 40-dimensional feature space • Page 15 Chess Segmentation © 2012
- 16. Step 3: Classify Square • Square Containing a Piece Shape Context Page 16 Chess Segmentation © 2012
- 17. Some Results Accuracy = 100% Accuracy 55% Accuracy 80% Page 17 Chess Segmentation © 2012
- 18. Towards a complete Program • • • • • • • Minimize assumptions Implement Step 1 Refine Spitting Squares Method Extend Feature Space( go Log Polar?) Add more training sets Optimize Code and Algorithms Test, Test, Test… Page 18 Chess Segmentation © 2012
- 19. Conclusion • Chess Detection and Segmentation a very hard problem in a general case • We managed to solve a small part of it • Each Step poses challenges Page 19 Chess Segmentation 4/13/2012
- 20. Thank you! Page 20 Chess Segmentation © 2012
- 22. Classify that! :p Page 22 Chess Segmentation © 2012