Tammo 80

Home / Weblog / Java / Reizen / Taalverhaspelingen

9 April 2014

SnapSolve

I just released the first version of my first iOS app SnapSolve. It is an app that solves Ruzzle or Boggle: it finds all the words in the 4×4 letter grid. There are already many such apps, but the new thing about SnapSolve is the input: you take a picture of the game, and the letters are automatically detected.

Making this game took me a lot of time, since I had to learn XCode, Objective C, C++, OpenCV and had to come up with an actual algorithm to do the letter detection. In the end I resorted to Python + OpenCV to do prototype the algorithm, so three programming languages were involved. Just as I was submitting the app to Apple for review, a blog appeared about just the thing I was making. I’ll try to illustrate the algorithms I developed in the style of the Megafauna blog. Actually, both our algorithms were inspired by SudokuGrab.

My algorithm consists of

  1. Scale the image to 360×480
  2. Detect if it’s Ruzzle or Boggle
  3. Adaptive threshold
  4. Find all contours
  5. Select contours that have a reasonable size (could be a letter)
  6. From the centers of all these contours, select the 16 that are on a 4×4 rectangular grid
  7. Recognize the score modifiers (only for Ruzzle)
  8. Recognize the letters: for every of the 16 letters:
    1. Draw the letter on a 30×30 image
    2. Overlay it with all (26 x 4 = 104) reference letters, find the letter with the largest overlap
  9. Find all the words using a trie
  10. Sort the words by score

Here are some pictures that show what’s going on:

Step 1: resize image Step 3: adaptive threshold Step 3: adaptive threshold Step 5: select contours Step 6: find grid Step 6: find grid Step 7: recognize modifiers
Step 8: recognize letters

3 Comments »

  1. Any chance of adding support for 5×5 boggle?

    Comment by Carlos — 26 May 2014 @ 06:36

  2. Sure, it’s in the works. Will take a week or so. As a matter of fact: you could help by sending me some pictures that should work (I don’t own a 5×5 boggle).

    Comment by tammojan — 26 May 2014 @ 07:35

  3. Will do. I’ll email them to the address on your home page. Give me a day or two. How many do you want?

    Comment by Carlos — 27 May 2014 @ 23:36

RSS feed for comments on this post. TrackBack URL

Leave a comment