Last time we parted ways I explained, that in order to tackle grids of various sized, I needed to adapt my matching logic. At the end of that post, the algorithm did the grid detect just by getting the cell size, than scaling the matching template, and dropping down the matching threshold to 60. Obviously that wasn’t an elegant solution, plus it didn’t work in all cases. It is time to change that!

Let’s consider these input images. For the sake of simplicity i kept the windows the same size (also it looks better this way). In real life we can even get smaller grids and in the 30X24 case, that can really be problematic. But let’s jump into it, shall we?

First thing we need to establish is that color doesn’t help us here. In fact, analysis of colored images compared to gray images, is slower and if you can you should avoid it. In our case it doesn’t matter if those cells are blue or white. Selecting the blue channel and applying a threshold over it quickly reduces our input images to:

Looks a lot better!. We need the get around the noise in the image, and by noise i don’t mean the usual. There is information in the image that isn’t valuable for us, game size information, clock, number of bombs, menu and extra info from the background bleeding through. So let’s look at how our code changed in the Initialize method.

void GameImageAnalyzer::Initialize()
{
	int margin = 50;
	Mat basic;
	Mat tmp = GetBmp();
	vector<Mat> channels;
	split(tmp, channels);
	threshold(channels[0], basic, 127, 255, THRESH_BINARY);

	vector<int> horizontal(basic.cols);
	vector<int> vertical(basic.rows);
	for (int i = margin; i < basic.cols - margin; i++)
	{
		for (int j = margin; j < basic.rows - margin; j++)
		{
			auto z = (uchar)basic.at<uchar>(j, i);
			if (z > 0)
			{
				horizontal[i]++;
				vertical[j]++;
			}
		}
	}
	vector<int> hStartVect, hEndVect;
	vector<int> vStartVect, vEndVect;

	int hMax = *max_element(horizontal.begin(), horizontal.end());
	int vMax = *max_element(vertical.begin(), vertical.end());
	int hTresh = hMax * 0.8;
	int vTresh = vMax * 0.8;
	bool on = false;
	for (int i = 0; i < horizontal.size(); i++)
	{
		if (!on && horizontal[i] >= hTresh)
		{
			on = true;
			hStartVect.push_back(i);
		}
		else if (on && horizontal[i] < hTresh)
		{
			on = false;
			hEndVect.push_back(i);
		}
	}

	for (int i = 0; i < vertical.size(); i++)
	{
		if (!on && vertical[i] >= vTresh)
		{
			on = true;
			vStartVect.push_back(i);
		}
		else if (on && vertical[i] < vTresh)
		{
			on = false;
			vEndVect.push_back(i);
		}
	}

	int hStart = hStartVect.front();
	int hEnd = hEndVect.back();
	int vStart = vStartVect.front();
	int vEnd = vEndVect.back();
	
	BoardWidth = hStartVect.size();
	BoardHeight = vStartVect.size();

	for (int j = 0; j < BoardHeight; j++)
	{
		for (int i = 0; i < BoardWidth; i++)
		{
			int hOffSet = (hEndVect[i] - hStartVect[i]) * 0.2;
			int vOffSet = (vEndVect[j] - vStartVect[j]) * 0.2;
			Point offset(hOffSet, vOffSet);
			Point lt(hStartVect[i], vStartVect[j]);
			Point rb(hEndVect[i], vEndVect[j]);
			lt += offset;
			rb -= offset;
			Point c = (lt + rb) / 2;
			Rect r(lt, rb);
			
			game.push_back(14);
			coords.push_back(c);
			rects.push_back(r);
		}
	}
}

So what is happening here?

1. Convert the image into a black and white image by selecting the blue channel then applying a threshold
2. Count how many white pixels are in each row and each column. This will be very handy later since most of the white pixels belong to the grid. Not that we apply a 50 pixel margin in order to get rid of the noise on the side of the image.
3. Calculate the line and column that holds the maximum number of white pixels.
4. Extract the horizontal changes from black to white and white to black in two different vectors. Not that we don’t analyse the image anymore, we go trough the information we extracted in step 2. Applying an 80% threshold of the horizontal maximum ensures that we don’t count the lines with the clock or other noise.
5. Do the same thing as step 4 only for vertical lines this time.
6. Determine the BoardWidth and BoardHeight based on the number of changes. Previously I’ve created these two public values and adapted the code to use these wherever we previously had the WIDTH, HEIGHT, SIZE constants.
7. Calculate the rectangles, based on the vertical and horizontal shifts. I apply a bit of an offset to reduce the border information of the cells, this concentrates more of the analysis to the cell center, where the color of the pixels are important.

By doing all of this, we managed to get rid of some old functions that are not used anymore. Also we obtained a bit of speed since this is faster than template matching. In order to visualize the outcome for you, i’ll draw in the following: red lines for the extremities of the grid, green rectangles where the image analysis will happen, and blue circles where the clicks happen.

Neat isn’t it. I could assemble a video of how does this play now, but I will do it next time. In order for everything to works smoothly I had to adapt the color detection a bit and some other things regarding game running, but let’s talk about that next time. See ya!