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
- Scale the image to 360×480
- Detect if it’s Ruzzle or Boggle
- Adaptive threshold
- Find all contours
- Select contours that have a reasonable size (could be a letter)
- From the centers of all these contours, select the 16 that are on a 4×4 rectangular grid
- Recognize the score modifiers (only for Ruzzle)
- Recognize the letters: for every of the 16 letters:
- Draw the letter on a 30×30 image
- Overlay it with all (26 x 4 = 104) reference letters, find the letter with the largest overlap
- Find all the words using a trie
- Sort the words by score
Here are some pictures that show what’s going on:
Any chance of adding support for 5×5 boggle?
Comment by Carlos — 26 May 2014 @ 06:36
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
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