Solving Minesweeper – Part 9: Color approximation

“So what happened?”, you might ask. Remember Columbo? Remember how he used to ask that final question, just before leaving the suspect alone and walking out the door, later having a big significance in solving the case? This is a classic case of planning to do something and ending up doing a totally different thing.

Before I was closing down this series, for my final trick I was going to solve the issue of size. Our solution till now is great don’t get me wrong, but if you try to solve a 9X9 or a 30X24 grid, it will fail. The issue is that the templates I use now, were extracted from the 30X16 sized grid. I though I will get away very quickly just by doing the following.

1. Detect the Cell Size
2. Scale the templates according to the cell size
3. Use the scaled templates in analysis
4. Open the champagne

Well it didn’t go as planned. The issue was that I already apply a threshold in order to find the perfect match. Scaling the templates meant that the quality of the match will be even worse. I tried adjusting the threshold, but I got more incorrect detection and misbehavior. Shit!

The solution lies in the content of the cells. The game scales the whole grid to have a good visual representation, so size always changes. What doesn’t change is the contents (the numbers). Since i’m too lazy to apply OCR on it, I needed to resort to the other thing that is constant. The color of the characters. Each cell has a different dominant color if we don’t count gray. But how do we do that?

Histograms are a very useful mathematical concept. It is a distribution of numerical data, in our case the elements of an array. The data the Histogram holds is number of elements in each bin. In our case I created a histogram for each color channel, then selected the bin in each channel that held the most pixels from that channel. Practically I was trying to estimate the dominant color this way.

void GameImageAnalyzer::ExtractColor(Mat src, int* cols, Rect roi)
{
	int stx = roi.x + roi.width * 0.1;
	int sty = roi.y + roi.height * 0.1;
	int enx = roi.x + roi.width * 0.9;
	int eny = roi.y + roi.height * 0.9;
	int bins[BIN_SIZE][3]{ 0 };
	for (int i = stx; i < enx; i++)
	{
		for (int j = sty; j < eny; j++)
		{
			auto c = src.at<Vec3b>(j, i);
			auto diff01 = abs(c.val[0] - c.val[1]);
			auto diff02 = abs(c.val[0] - c.val[2]);
			auto diff12 = abs(c.val[1] - c.val[2]);
			// detect grayish color
			if (max(diff01, max(diff02, diff12)) < 20)
				continue;

			bins[c.val[0] / BIN_SIZE][0]++;
			bins[c.val[1] / BIN_SIZE][1]++;
			bins[c.val[2] / BIN_SIZE][2]++;
		}
	}

	int max[3]{ 0 };
	
	for (int i = 0; i < BIN_SIZE; i++)
	{
		for (int c = 0; c < 3; c++)
		{
			if (max[c] < bins[i][c])
			{
				max[c] = bins[i][c];
				cols[c] = i;
			}
		}
	}
}

OpenCV has many cool features to work with histograms, but I’ve chosen to write it myself to count only certain colors. The above code just reduces the region of interest to 80%, in other words I only take into account the inner portion of the cell, excluding border and other factors. Then for each pixel we check in which color bin will it fit (0 = blue, 1 = green, 2 = red), excluding the pixels where the components don’t differ with more than 20 (color is grayish). I use 16 as BIN_SIZE.

Running the above code on the template images we get the following table.

As you can see they are enough to apply a comfortable error and still get the closest value correctly. In the initialization function I convert all my templates to these values (i could hard-code them but I kept it so I can make changes regarding the binning later. Extracting the color of a particular cell looks like this:

int GameImageAnalyzer::GetBestMatch(Mat src, int start, Rect rect)
{
	int components[3];
	ExtractColor(src, components, rect);

	int min_dist = 100, match = -1;
	for (int i = start; i < TEMPLATE_COUNT; i++)
	{
		int dist = 0;
		for (int c = 0; c < 3; c++)
			dist += abs(temp_colors[i][c] - components[c]);
		if (dist < min_dist && dist < 6)
		{
			min_dist = dist;
			match = templates[i];
		}
	}

	return match;
}

In short, I extract the color components for the given cell (we don’t need to use cutouts anymore). Then we try to find the template that is the closest match to our current color value. Remember that the cell can still be in animation resulting in a -1 as a return value. We consider anything a good candidate which has a component difference less than 6. The analyze function now drastically changes to:

bool GameImageAnalyzer::Analyze()
{
	Mat bmp = GetBmp();
	for (int i = 0; i < game.size(); i++)
	{
		// we already processed this cell
		if (game[i] <= BOMB) 
			continue;
		
		int start = (game[i] == NOTBOMB) ? 1 : 0;
		// expect other than the UNDISCOVERED template

		int match = GetBestMatch(bmp, start, rects[i]);
		if (match == -1)
			return false;

		game[i] = match;
	}
	return true;
}

Unfortunately I cannot show a fancy video this time, since it runs more or less as the previous one. It’s faster in detecting individual cells, however it needs to wait until there is virtually no more animation. In my assessment it’s a bit slower like 1-2 seconds for a full solve.

The improvement we will see next time. When we will make our solver size independent (hopefully)