December 12, 2011
For the final project in my Computer Vision class, I decided that Waldo needed to be solved. Once and for all. I spent hours as a child hunting for that blasted red-and-white striped man, and this time, I had enough. I whipped up some MATLAB code to create a Where’s Waldo Solver.
Because I was researching Hidden Markov Models (HMMs) at the time, I knew that these could be used to search for patterns in a large image. After some research, I determined that I could construct an HMM based on the 2-dimensional Discrete Cosine Transform (2D DCT) of a small image of Waldo. Using this model, I could scan a large image in chunks looking for a match. If the match was close enough (i.e. over a threshold), I determined that Waldo must be part of that chunk. For this prototype, the MATLAB script highlighted matched chunks in blue (as in the image above). With a set of test images (scanned from an actual Where’s Waldo? book), I saw a 70% positive detection of Waldo with about a 35% false positive rate. Not great, but it shows that Waldo can be found!…by a computer that is.
While finding Waldo may seem frivolous, this type of sub-image identification could be useful: picking out a face in the crowd, looking for a specific type of terrain in a satellite image, and so on. You can find the report and MATLAB code below. The code is based on the HMM Toolbox, which you will need to download before running my scripts.
MATLAB scripts: wheres_waldo_solver.zip