Sequential NN + Heuristic Approach to image puzzle solving.

Go solution console output

What it does

Our system can unscramble 2x2 image puzzles by analyzing patterns in the edges of each image segment. Our heuristic algorithm in Go can rapidly compare entire edges using standard deviation in tandem with a grayscale difference function. Utilizing these metrics, we were able to match the edges of the given image to determine its proper orientation.

Additionally, we have a machine learning model trained on these edge weights that can take the edges and predict the most likely orientation for the unscrambled image with a high degree of accuracy.

How we built it

Our group started by developing a heuristic algorithm that matched pixel edges by utilizing standard deviation, matrix multiplication, pixel manipulation, and other data clustering techniques. Under normal circumstances, this task would have taken hours, however, our group used Golang to perform these operations concurrently across the entire dataset (~50,000 images) in less than 40 seconds. Following this, we optimized our heuristic using a neural network developed in python. The neural network helped us to optimize the heuristic and make corrections, thus improving the prediction accuracy across the entire dataset.

Challenges we ran into

Our greatest challenge proved to be deploying our hybrid codebase, in the end, we ended up compiling the Go code on the submission server and running it directly from python while passing in the file path as a command line argument.

One difficulty we encountered was optimizing the runtime in Go. We overcame this challenge by employing concurrency. This allowed us to leverage all cores (up to 24 because there were 24 folders) on the server running our solution making ours stand out in real-world application, however, concurrency has its quirks and can sometimes be hard to align timing however by use of WaitGroups we were able to ensure all threads were handled by the Go Scheduler correctly.

Accomplishments that we're proud of

We're proud of the high degree of accuracy we were able to attain using our custom algorithm and our accuracy to runtime ratio on our Go Algorithmic Solution.

At peak performance, our Neural Network performs with just over 90% accuracy on the training data while our go function performs at around 85% accuracy. This is incredible especially given our Runtime is about 30 seconds per 50,000 images in Go.

What we learned

Our group collectively gained experience in Go and Python as well as many Python libraries including TensorFlow, NumPy, pandas, etc. In addition, we also learned valuable team-building and collaboration skills.

What’s next? What improvements could be made?

With about a day's more time, we would’ve had time to create a feedback loop into our Golang implementation which we think would’ve increased the accuracy by ~10%. We started implementing this before we ran out of time and already have seen a double-digit performance increase.

One huge component we could fix is to reduce the amount of reslicing that takes place on the Go side. Though our implementation was already blazing fast we definitely could have saved another ~25% of the time by using fixed-size arrays rather than reslicing.