How to recognize hexagonal tiling in boardgame?

Question

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";
img = cv2.imread(imgOrig+".jpg");  
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.

Answer 1

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.

Answer 2

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

Relevant game rules

• location tiles, castles and mountains can not be taken by game token (houses)
• in 7 out of 8 cases water can also not be taken
• there are 8 different (unique) kinds of sections, plus 8 through rotation by 180 degrees (see picture of possible sections
• complete game rules can be found here

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.