Recognizing Matching Colors in a Game Grid from a Camera Image

Question

I am relatively new to Mathematica, having taken my first serious dive into it this week. As a fun project to teach myself some of the basics, I've come up with a goal of optimally solving a game called "Chromazone".

The idea is that you start with a 13x13 board made of 6 colors, and the middle spot is "captured." You select colors and any consecutive blocks of that color touching the middle (black) captured area becomes captured as well. The game is complete when you've captured the entire board, and the goal is to complete in as few moves as possible.

To make it additionally challenging, I took a picture of the game board with my cellphone, and am using that as a starting point. Here is the picture:

After researching different approaches for a couple of hours, I've settled on the following algorithm to interpret the board into a Table I can manipulate for solving later:

1. Resize the image to dimensions that are exact multiples of 13x13 (I chose 520x520, making each square 40x40)
2. Split the image into 40x40-sized square units.
3. Interpolate the color of that square by taking the average.
4. Match the color to one of the standard 6.

I'm somewhat stuck on #4. I've experimented with multiple approaches but there is enough error in the color matching that I can't quite get it correct. My first approach was to use the Nearest function to match the result of DominantColor against the standard 6. Then I converted the result into indices:

Grid[Table[
  Table[Nearest[{#[[1]], #[[2]], #[[3]]} & /@ {Yellow, Orange, Green, 
       Red, Blue, Purple} -> Automatic, 
    List @@ DominantColors[
       ImageTake[
        Import["I:\projects\Chromazone\WP_20141015_004.jpg"], {y, 
         y + 40}, {x, x + 40}], 1][[1]]], {x, 0, 480, 40}], {y, 0, 
   480, 40}]]

The result is very close to correct, but as you can see below the first incorrect match is the upper-right square, which is detected as orange even though it's yellow:

{1} {2} {3} {4} {5} {1} {5} {5} {6} {2} {4} {2} {2}
{5} {3} {6} {6} {4} {2} {3} {6} {2} {3} {5} {2} {2}
{3} {3} {6} {6} {4} {1} {2} {3} {2} {3} {3} {6} {5}
{6} {6} {4} {6} {2} {5} {2} {2} {1} {4} {5} {5} {3}
{1} {4} {6} {5} {2} {1} {3} {2} {1} {3} {5} {1} {2}
{6} {4} {5} {3} {6} {5} {6} {1} {6} {1} {2} {2} {5}
{5} {5} {6} {6} {5} {4} {6} {5} {1} {1} {4} {2} {3}
{5} {1} {2} {5} {5} {2} {4} {4} {2} {5} {1} {3} {2}
{3} {3} {6} {3} {5} {2} {1} {6} {4} {5} {6} {3} {6}
{5} {5} {5} {5} {1} {1} {2} {4} {1} {1} {2} {3} {5}
{6} {2} {1} {2} {1} {3} {3} {6} {3} {3} {5} {3} {3}
{6} {1} {6} {2} {3} {6} {2} {2} {4} {2} {2} {6} {6}
{5} {5} {5} {1} {1} {4} {2} {1} {1} {2} {3} {3} {4}

Then I stumbled on the FindClusters function and thought it might make more sense to separate the squares into 6 clusters, and if there's enough difference between the color sets it should neatly separate into the 6 color categories:

FindClusters[
 Flatten[Table[
   Table[ColorQuantize[
     ImageTake[
      Import["I:\projects\Chromazone\WP_20141015_004.jpg"], {y, 
       y + 40}, {x, x + 40}], 1], {x, 0, 480, 40}], {y, 0, 480, 40}]],
  6]

However, there are a few dark yellows again that are grouped with orange (when I used 7 clusters instead, to try to separate black, the black still stayed with the green, and the yellows split into two groups, but interestingly there were no false matches):

I'm running out of ideas to get a more accurate result short of hard-coding the correct color match for the exception squares (which I'd really like to avoid). One more thought I had was to try some sort of image enhancement to counteract the obvious lighting artifact, where the cellphone camera made the center brighter than the edges. Maybe if I used some circular filter to brighten the outer edge, the FindClusters result would not have false matches any more - but I'm not quite sure how to accomplish that.

Does anybody have any ideas on how to get a more accurate detection of each grid square's color within these constraints?

Answer 1

Here is a first pass at this problem.

img = Import["http://i.stack.imgur.com/wwHZe.jpg"];

getHue = First[DominantColors[#, 1][[1]] ~ToColor~ Hue] &;

hues = Map[getHue, ImagePartition[img, 40], {2}];

plot = Map[Hue, hues, {2}] // ArrayPlot

I tried to use ClusteringComponents to further quantize these hues but I got a bad result. Edit: After a rethink I have it working OK now:

labels =
 ClusteringComponents[hues, 6,
   DistanceFunction -> (Min @ Abs[{#, # - 1} - #2] &), 
   Method -> "Agglomerate"];

labels // Grid

$\begin{array}{ccccccccccccc} 1 & 2 & 3 & 4 & 5 & 1 & 5 & 5 & 6 & 2 & 4 & 2 & 1 \\ 5 & 3 & 6 & 6 & 4 & 4 & 3 & 6 & 2 & 3 & 5 & 1 & 1 \\ 3 & 3 & 6 & 6 & 4 & 1 & 4 & 3 & 2 & 3 & 3 & 6 & 5 \\ 6 & 6 & 4 & 6 & 2 & 5 & 2 & 4 & 1 & 4 & 5 & 5 & 3 \\ 1 & 4 & 6 & 5 & 4 & 1 & 3 & 2 & 1 & 3 & 5 & 1 & 1 \\ 6 & 4 & 5 & 3 & 6 & 5 & 6 & 1 & 6 & 1 & 2 & 2 & 5 \\ 5 & 5 & 6 & 6 & 5 & 4 & 4 & 5 & 1 & 1 & 4 & 2 & 3 \\ 5 & 1 & 2 & 5 & 5 & 2 & 4 & 4 & 4 & 5 & 1 & 3 & 1 \\ 3 & 3 & 6 & 3 & 5 & 2 & 1 & 6 & 4 & 5 & 6 & 3 & 6 \\ 5 & 5 & 5 & 5 & 1 & 1 & 2 & 4 & 1 & 1 & 2 & 3 & 5 \\ 6 & 2 & 1 & 4 & 1 & 3 & 3 & 6 & 3 & 3 & 5 & 3 & 3 \\ 6 & 1 & 6 & 2 & 3 & 6 & 2 & 2 & 4 & 2 & 2 & 6 & 6 \\ 5 & 5 & 5 & 1 & 1 & 4 & 2 & 1 & 1 & 2 & 3 & 3 & 4 \\ \end{array}$