# How to recognize hexagonal tiling in boardgame?

I would like to recognize the boundaries of a hexagonal tiling in a photograph, like in image below:

It seems to me, that a standard approach at a square grid is to first detect corners (e.g. canny) and then extract the longest lines via a Hough transform or something similar.

This does not look as optimal solution with hex tiling, because the length of outer lines is shorter and it's hard to separate them from other lines.

Is there any algorithm to adress this problem? It would be particulary nice to have a solution in opencv, but I am also interested in general ideas.

update:

With python and opencv I was able to receive this result:

Here is my code:

import cv2
import numpy as np

imgOrig = "test1";
lap = cv2.Laplacian(img, cv2.IPL_DEPTH_32F, ksize = 3)
imgray = cv2.cvtColor(lap,cv2.COLOR_BGR2GRAY)
ret,thresh = cv2.threshold(imgray,127,255,0)
contours, hierarchy = cv2.findContours(thresh,cv2.RETR_TREE,cv2.CHAIN_APPROX_NONE)
size = img.shape
m = np.zeros(size, dtype=np.uint8)
for i, cnt in enumerate(contours):
if cv2.contourArea(cnt) >= 1:
color = (255,255,255)
cv2.drawContours(m, cnt, -1, color, -1)
cv2.imwrite(str(imgOrig)+"contours.jpg", m);


Laplacian of image looks like:

I will try to optimate the parameters of this approach and then try to interpolate the boundaries of the four sections.

• Signal processing meets euro-gaming; my geek senses are tingling! – nispio Aug 19 '13 at 3:54
• If you are always using the same size board, and will always have roughly the same view of the board in the image, then you might be able to solve the problem as simply as recognizing the outline of the board to determine sizing and registration. The placing and sizing of the tiles is constant with respect to the edges of the board, so once you know where all of your edges are, you should be able to accurately infer the positions of the inner tiles. – nispio Aug 21 '13 at 17:04
• Thank you for your suggestion, @nispio. The board size is the same all the time, whereas the view of the board might change quite a bit. The color of the background is also different in other pictures, which leads to a much lower contrast. If the background is beige for example the position of the outline is hard to determine. – snalx Aug 23 '13 at 11:32
• If you're not getting any other answers, I think it's a good idea to post your edits as an answer your own question. I'm not sure how that interacts with the bounty though ! – lmjohns3 Aug 24 '13 at 16:29
• @snalx: If you post your findings as an answer I will award the bounty to you. Needs to be done in the next 12 hours, though. – jan Aug 28 '13 at 19:59

# 1st Approach:

Use the haartraining methods of opencv according to this tutorial http://note.sonots.com/SciSoftware/haartraining.html -- this should give the best results, but I haven't worked with haartraining myself so far...

# 2nd Approach:

I would suggest to use methods of "markerless tracking" of the individual tiles of the board. You can implement this using OpenCV, too..

## Preparation

1. For this purpose you'll need some photos of each type of tile. Take a picture of all tile types (each one as one picture), with a homogeneous background from top-down-view tile in the middle of the picture.

2. Then use some feature detector (OpenCV has multiple algorithms for this, but SIFT/SURF are non-free algorithms; I would suggest to use "FAST") to find distinctive points in the images.

3. Use a feature descriptor to describe the feature found in the image (use e.g. "BRIEF").

## Detection

Now you can detect the tiles in an image by applying the same feature detector/descriptor algorithms to this image. When you've acquired the features/descriptors you can apply the FlannBasedMatcher to find the tiles.

Here's a code example / tutorial from OpenCV: http://docs.opencv.org/doc/tutorials/features2d/feature_homography/feature_homography.html#feature-homography

## Notes

The Matcher Method will give you only one match and will possibly have problems if there is more than one tile of that type found on the board. You could work around that problem by masking out only some parts of the input image. I suggest to do this using the pixel coordinates of the detected features. If you - somehow - detect the outline and size of the tiles first, you can roughly estimate the tile positions and size on the picture. Filter your detected feature-list (e.g. only features within x-pixel radius from expected midpoint of the tile) before matching and then use the strongest match. As a result you'll be given the exact position of the tile on the image (including it's orientation). If it's too complicated to detect the map outline, you can let the user "point" at the corner tiles to mark the outline manually...

# Alternative Approach

You can also use this method to find just any of the tiles by its outline. Draw a sample "schematic" grayscale picture of a tile (hexagon) without any image on it. Note that the "dark" and "light" regions in this image need to be correct in the schematic, not just some "lines". You'll probably need to experiment with this. You could try to average multiple photographs of different tiles to generate an "average" image of a tile. Make sure the corners are at the same position (move/scale pictures accordingly) and sharpen the picture when finished (clear corners/edges should be visible) and adjust the contrast a bit, if needed.

• Thanks for your suggestion @StefanK. I am a little worried if the first and second approach still work if gaming pieces (houses) lie on the tiles. Your alternative approach looks promissing, I'll try that (maybe after a bit of preprocessing). – snalx Aug 26 '13 at 14:58
• The detection of the outer lines seems to be possible in most cases. I recently tried that with Hough transfom on images similar to the final result in my question. I will update my question when I found a stable solution. – snalx Aug 26 '13 at 15:01
• Houses and other game pieces on the tiles should not be a problem. This causes some "features" to be covered, but some of them will still be detected. At least 4 need to be detectable. You can try the feature detection demos of opencv and look at how many features are detected on each tile... – SDwarfs Aug 30 '13 at 15:22

I will describe my current approach, which is an combination of exploiting game rules, image processing and feature detection.

# Realisation

At first I use Hough transform to extract position of game board. Source image looks similar to final image in question, but with thicker lines and I filtered the smaller boundaries. I use only detect very long lines (order of magnitude: about 60 percent of image width/height) and very small threshold for line matching. I also just look at lines at the outer 40 percent of image and take the median of detected lines at top, bottom, left and right. Result is shown in image below:

I only need a rough approximation, so this is just fine. From now on I only examine image inside the Houghlines, plus some extra space due to uncertainty of Hough transform.

Then I use feature detection, as proposed by Stefan K. in his answer, to detect the features in image, that can not be taken by the players, i.e. castles, location tiles and mountains. I use the ORB algorithm in opencv-python to do that and BruteForce-Hamming-Matcher (I was not yet able to get FlannBased matcher running). ORB is scale and rotation invariant. In order to detect multiple occurrences of same features (e.g. castles) I split image in parts, that overlap. This works fine as long image resolution is big enough and picture is taken directly from top (still needs some tests). It is also kind of slow. Detection of location tile (tavern) is shown as an example in image below

At the moment I try to find the homographyTransform to extract exact position and orientation of detected features.

I hope to be able to reconstruct the grid out of this information (position of mountains, castle, location tiles and in most cases water). Currents experiments look promising, though a lot of fine tuning and proper preparation of feature images has to be done.

• I have done something similar with Catan but instead of hoomography I am using mean color value for any given tile. Identify the tile as a 6-faced poly contour with pre-processing to help isolate the edges, then convert that ROI to a mask, then apply the mask with bitwise_and over the source image. You can then get mean color, which may be enough to identify most tiles, and then you can do additional pattern matching. I just started this: youtube.com/watch?v=0ezfyWkio6c – Rex Hardin Jul 11 '17 at 18:40