Bananagrams Verifier

Bananagrams is a game played with lettered tiles. Players race to assemble a crossword-puzzle configuration that uses all of their tiles, like this one:

For fun, I built a system to detect the letters and the puzzle connectivity, check the words found against a dictionary of valid words (using the official Scrabble dictionary), and verify whether or not a puzzle uses only valid words.

We start with an image like this:

Binarize it (using k-means in intensity space to find ideal separation of light vs dark pixels)

Clean it with some morphological operations. (note improvements in the 'A' and 'T' in the upper right, where they were shiny.

We then apply contour detection, and find the level of the contour hierarchy that has many objects of approximately the size that we think letters should be (hard-coded).

Wth the letters (and maybe some noise) identified, we now want to correct the orientation of the puzzle so we can recognize characters.

We use the minimum-area oriented-bounding-box function on each of these contours:

There is some noise (like between the 'S' and 'T' in STARE), there are some letters for which the box was not a good fit (like the 'O's), and there are some misleading tiles which do not fit with the puzzle.

But despite these factors, most of the boxes are aligned in the direction of the puzzle, and we can extract the correct direction by letting each contour 'vote' for the X direction, and then use RANdom SAmple Consensus (RANSAC) to find the 'vote' with the most other 'votes' that are very close to it.

The votes:

And the image after rotation correction:

Now that the image has been straightened, we can read these letters.

We extract the image region around each contour and compare it to an alphabet which we formed by manually sorting a large number of extracted letters and averaging the appearance of all occurences of a letter together.

The averaged alphabet:

We compare our candidate letter against each letter in our alphabet using the absolute value of intensity difference at each pixel (this is a simple metric for fast comparison).

For the match with the least error, if the error was below a threshold (hard-coded), we accept that this is actually an instance of that letter. If above that threshold, we reject it as noise, or as a tile not oriented with the puzzle (like the stray tiles here).

The set of all accepted letters from this image is:

Which is all of the letters which were upright in the rotation-corrected image, so this is a great result.

Now, among the contours which were accepted as letters, we need to determine the puzzle connectivity. To do this, we average the size of all letters so we know the approximate size, and thus spacing, that they should have in this image.

Then, we explore from each letter going straight up, down, left, and right, and searching for other accepted letters which are within a small tolerance of the predicted neighbor location. A search in one direction looks like this:

Now we know every word that is used in the puzzle, and the location of every letter making up each word.

We use a list of over 17,000 official Scrabble words. We load them into an unordered map. This allows constant-time lookup of words.

If a word is valid, we color it green. If not, we color it red. Then we draw the recognized letter on top:

This puzzle had all valid words, so it is a valid puzzle!

You can download this project for android phones HERE

This video shows the algorithm working in real time, with some invalid words along the way: