Developing and Evaluating a Word Search Puzzle Solver

 1.    Objective

You are asked to build and evaluate a system that can solve Word Search puzzles. The input to the system will be, i) a set of images of Word Search puzzles photographed

from a puzzle book and stored in  image format, ii) the list of words that are to be

found in each puzzle. The output will be a sequence of word positions indicating the grid coordinates of the first and last letter of each of the words that are to be found. Solving the problem will require two stages: building a letter classifier; implementing a word finding algorithm.  Your classifier must operate with feature vectors that have no more than 20 dimensions. You are given labelled data sets for training and evaluation, and some template code to help you get started.

 2.    Background

A Word Search is a puzzle game that first appeared in the 1960’ and which is now commonly found in newspapers and puzzle books. The puzzle consists of a grid of letters and a list of words that are hidden in the grid. Words appear in the grid as straight, connected sequences of letters which can run in any direction, i.e., including diagonally and backwards. The aim is for the solver to locate each of the words.

In the lab classes, you have been experimenting with techniques for classification and dimensionality reduction. In this assignment, you will use the experience you have gained to build a system for solving Word Search puzzles, i.e., taking images of word search puzzles and outputting the positions of the hidden words. This involves taking the image of the full puzzle, cutting it into separate squares (i.e., one square for each letter) and then classifying the letter images, i.e., as one of the 26 possible letters,             Z’. Finally, you will need an algorithm to search through the grid of labels to find where the words are hidden. In Word Search puzzles, the words can run left, right, up, down, or in any diagonal direction. Words can also overlap.

The images you will be processing have come from a normal puzzle book, the ‘Tesco Handy Mixed Puzzle’ book and have been photograph using an iPhone. To make the task more interesting, photographs of varying quality have been captured: high- quality in which the letter are clearly readable (see Figure 1); and low-quality where the blurring of the image makes many letters quite ambiguous (see Figure 2).

You are provided with a correctly-labeled set of training data and if you use appro- priate techniques you should be able to produce a solution that will work perfectly on the high-quality data, and surprisingly well on the low-quality data. You will be assessed partly on the performance of your solution.

1.    What you are given

You have been given,

1. data for training and testing your systems, and
2. some template code to get you

The template code will run but it will produce poor results. The dimensionality reduc- tion, classification and word searching stages have been given stub implementations: 

they return the correct type of value but do nothing useful. You will need to replace these implementations using ideas that you have learnt during the course.

3.1.    The data

There are two types of data.

1. Image files. These are images of complete puzzles. The images have all be pre-processed so that are all upright and scaled such that each letter in the image occupies a 30 by 30 pixel square.

Label files. There are two label files: puzzles.train.json which provides labels for the training data, and puzzles.dev.json which provides labels for the development test data. They are stored in JSON format and contain a list of dictionaries. Each dictionary represents one puzzles and has the structure 

In the dictionary, the fields have the following meaning:

• name : a string containing the name of the puzzle - used to identify the image file
• rows : an integer specifying the number of rows 

• columns: an integer specifying the number of columns 
• Strings: a list of strings containing the words to be found

• positions : a list of 4 digit lists indicating the correct position of each The first two digits are the row and column of the first letter, and the last two digits are the row and column of the last letter.

3.1.    The code

The code is organised into four Python files: train.py , evaluate.py , utils.py and system.py . train.py and evaluate.py will train and test the system, respectively. They will do this by calling functions in system.py . Your task is to rewrite the code in system.py to produce a working system. No other Python file should be changed.

In brief, the code files have the following function. 

• py - this runs the training stage. It will train two models: one using the high quality images and one using the low quality images. For each model, train.py will read the corresponding training data, process it, and store results. Results are saved in a pair of files called model.high.json.gz and model.low.json.gz stored in the directory, data/ , for the high and low quality data respectively. The training code uses functions in system.py that you will need to modify and extend. Do not change the code in the train.py file itself.
• py - this runs the evaluation stage. It will run two evaluations: one using the high quality data and one using the low quality data. For each dataset, evaluate.py first reads the corresponding model file, i.e., model.high.json.gz or model.low.json.gz . It will then perform the letter classification on the test images. It will then attempt to find the puzzles list of

words in the grid of classified letters. Finally, it will use the test image letter la- bels and known word locations to evaluate the solution, reporting scores for the percentage of letters correctly classified, and the percentage of words correctly located. Similarly to train.py ,it uses functions in system.py that you will need to modify and extend. Do not change the code in the evaluate.py file itself.

• py - these are some utility functions that perform operations such as loading and segmenting the image files. Do not change the code in this file.
• py - the code in this file is used by both train.py and evaluate.py

.   It implements the key system functionality, including the dimensionality

reduction, the classification, and the word searching steps that you will develop. The provided version contains dummy code that will run but which won’t produce good results.  The dummy dimensionality reduction just returns the first elements of the feature vector; The dummy classifier outputs the label ‘E’ for every square; the dummy word finder always says the word lies between square (0, 0) and (1, 1).

Your task is to write a new version of system.py . Your solution must not change train.py , evaluate.py or utils.py . Once finished, you will run   train.py to generate your own versions of  model.high.json.gz and  model.low.json.gz

. You will then submit the system.py along with the model.high.json.gz and model.low.json.gz files. The assignment assessors will then run the program evaluate.py using your copy of system.py and your model files. We will evaluate using a new test puzzle images that you have not seen during development. The performance on the unseen test puzzle will form part of the assessment of your work.

 2.    How to proceed

The plan below has been written to help you get started. Steps 1 and 2 should be completed first. Steps 3 to 6 are not necessarily sequential, and you are free to use any process you wish. However, it is recommended that you read through this section carefully before considering how best to proceed.