​PuzzleBot
Overview
Our software is capable of remotely taking a photo. It then uses computer vision to find puzzle pieces and extract their edges. Next it compares edges for matches and finds a viable solution to the puzzle using an edge matching based solver developed jointly by UC San Diego and the University of Minnesota. From this solution we extract a list of matching edges as well as the necessary rotation and translation required to assemble the puzzle. We then write out a gCode file, which is a list of commands that the gantry needs to execute in order to physically assemble the puzzle. Finally, we read this text file over serial to the Arduino, which interprets the commands and actuates all the motors. Below is a system overview, which demonstrates how our different software elements communicate with each other.
Solving Algorithm
The solver takes in a set of vectors representing the edges of a puzzle. It then does bivertex arc-decomposition on the puzzle piece which reduces the puzzle pieces into arcs. The puzzle is then calculated for its Euclidean signature and the Euclidean signatures of all the arcs are then compared. After finding a promising fit the possible arcs are entered into a locking function to reduce drift as many pieces are added. It starts with the most unique piece to reduce the likelihood of error, and works its way out to the edges. The original algorithm and source code was found online (links below). It was modified to extract rotation, translation, and a list of matching edges for solving jigsaw puzzles in a real coordinate system. The original code was well commented, but there was a considerable learning curve with how to interface with it.
Design Process
Our team chose to use MatLab as our main computational language. Our main reason for this is that the existing software we found was already in MatLab, and we didn't view it as valuable to translate it. MatLab also has great built in functionality for processing matrices, which is how a computer views images.
We also choose to save the output of the solver to a text file instead of directly sending it to the Arduino. It added another layer of complexity, since we needed a script for formatting a file, as well as another one for reading and interpreting a text file. We decided it was worth it because the solver can take a very long time to run, and if there is a problem that causes the program to crash while manipulating the puzzle pieces we don't want to have to re-run the solver. By saving a txt file, the required moves are saved.
We discussed multiple methods of acquiring the image. Possibilities included an overhead camera as well as a small webcam mounted on the gantry head. We ended up deciding on an overhead camera for computational simplicity. Stitching together moving images taken from the head would have been very difficult. Because of this, we decided to use a DLSR instead of a webcam. This made interfacing more complicated, since webcams are designed to interface with computers, but we needed the increased resolution in order to accurately extract each piece from a single photo.
We researched different methods of solving a puzzle computationally. The two main schools of thoughts are using edge matching, which can handle puzzles with unexpected color changes and incoherent pictures, but struggles with regular, repetitive shapes, and color gradient matching, which can handle puzzles of any shape (including all square pieces), but requires consistent color gradients. We chose to use edge matching, primarily because we found an algorithm that works well, and because we can't guarantee consistent lighting, which would affect a gradient matcher worse. We also want to be able to handle puzzles with any photo on them.
Challenges
We had some difficulty getting open CV to run in MatLab. Some functions are slightly different than in other languages, and others require a paid version. Eventually, we were able to develop algorithms using only the free CV toolbox that could extract outlines and export edge vectors from puzzle pieces.
Because of the number of different platforms and languages being used, communication required caused unexpected problems. We needed the camera to talk to the computer in MatLab, which had to talk to a python script that allowed the computer to talk to the Arduino, which controlled the motors. Whenever there wasn't a standard already in place, clear standards were created so that different team members could know what to expect while developing code.
Software and hardware were inherently developed in parallel. This meant that it was many weeks before there was a fully operational system to test software on. This made debugging errors more challenging, and delayed the development cycle for code.
Unit conversion proved to be unusually tricky. Because our system starts with a photo and is ultimately driven by steppers, we had to deal with conversion between pixels, inches, and steps. We also had to keep track of our coordinate system. For instance, the solver treated 0,0 as the upper right hand corner with positive Y values coming down, while the gantry code treated the lower left corner as 0,0.
Extracting puzzle outlines was more complicated than originally expected. Variances in lighting condition and cleanliness of the background significantly altered edge detection ability. To solve this, we photographed all the pieces upside-down and placed them all on a white background. We use the camera's flash to reduce lighting variance.
One issue that took us a considerable length of time to hunt down was a bad cable. We were receiving spotty communication between python and the Arduino, and ended up discovering that the USB cable was defective, causing the serial port to occasionally drop connection. The cable was replaced.
Source Code
Dependencies: OpenCV for MATLAB
Git repo containing source code for solver and firmware for controls: https://github.com/emocallaghan/PoEPuzzle
Link to original source of solver algorithm: http://math.umn.edu/~olver/matlab.html
