Using Computer Vision To Solve Jigsaw Puzzles

Figure 1. Input Image for the Wookie PuzzleFigure 2. Polar Plot of Boundary for One Puzzle PieceSince segmentation can be done in a multitude of ways,the approach I use is to put the pieces on a solid green screenbackground and segment based on color. This has beendone for ease and efficiency since segmentation is not theentire focus of the project. However, as with the additionaladaptation of the code to varying image capture angles, itwould be entirely possible to segment the image using othermeans, such as the mean shift or normalized-cut methodsused in class. These other methods have the potential tomake the code more robust to varying backgrounds, suchas wood table tops or off-axis image capture. These methods were considered, but were not completed since the puzzle assembly was considered more important to the overallprogram completion.The primary result of the segmentation is a binary maskthat we use to obtain the location and extent of the individual pieces using the bwconncomp and bwregionpropsMatlab functions. There are provisions in the code forcleaning up somewhat imperfect masks that may have resulted from additional specks of dirt blocking the greenbackground or when the green background does not fill theentire image and there is a segment along an edge where thetrue background (i.e. the floor or table) peeks through.XY-coordinates to polar coordinates and then using this information to find the predominant direction of the points,taking the average of the intersection, and then taking theclosest point on the boundary. While these methods mayhave eventually been adapted for my purposes, I had issues getting them to work consistently and instead landedon a method based on the one presented in [6] where I convert the border points to polar coordinates and use the Matlab function imregionalmax to find peaks in the data(other matlab functions were tried, but did not return as favorable of results). See Figure 2 for a visualization of whatis returned for an individual piece. Unfortunately, since theborder is somewhat noisy, there are many more peaks thanactual corners or heads. Thus I wrote a script that stepsthrough the peaks, consolidates the multiples to the truepeak in the θ region, and tries to discriminate whether thepeak is a corner or a head and, if a head, eliminates the peak.The script then goes in and uses the remaining peaks to determine the corners, which are two sets of peaks separatedby 180 degrees that alternate.Once the four corners of the piece are found, the sides ofthe piece are simply taken to be the points along the boundary between each set of two corners. The next most significant task is to assign each side of each piece as a head ( 1),a hole (-1), or flat (0), see Figure 3 for a visual. This canbe done in many ways. The original method I used wouldtake the points along the edge in XY-coordinates, re-alignthem such that the two corners each lie on the x-axis, andthen take the integral. If there was significant area eitherabove or below the axis created by the two corner points,then the side could be declared either a head or hole, otherwise it was considered flat. However, there were issues withthis method that were brought to light when experimentingwith one of the puzzles. Specifically, there was difficultysetting a specific pixel integral threshold for all of the sideswhen the piece was more rectangular than square. One so-3.2. Puzzle Piece CharacterizationOnce the pieces have been segmented from the background and a binary mask created, the individual pieces arebroken down further and many traits are extracted that willbe used in later matching.The first step is to define the corners. As per the assumptions about the puzzle pieces used, each piece has four,well-defined corners with an angle approximating 90 degrees. Several approaches for extracting either the cornersor the sides were attempted before ultimately landing onthe method used in the puzzle solver. One of the methods involved using the Hough transform to find the predominant direction of the points along the border while another found in [5] involved the conversion of the borders3

method similar to [5], I identify small patches of pixels (Ifound three, 2x2 patches to work well) distributed evenlyalong the edge, grab the average L*a*b* color informationin each of the patches, and store it for the matching process(see figure 3 for an example). Of course, I only do thisalong the edges with holes and heads – this is unnecessaryalong the flat edges. As with the piece information before,I also gather the HSV values for each of the patches, butno longer use them in the matching process after receivingmixed results.3.3. Puzzle AssemblyWhen discussing the puzzle assembly, I have decided tobreak the process down first and foremost into “global” versus “local” assembly, and then break the “global” assembly down further into two distinct areas of the puzzle: theborder pieces and the inner pieces. This is a method thatis discussed and accomplished in most of the papers I reviewed, but specifically discussed in [4] and [3] and seemslike a reasonable approach to the problem. It also seemslike a logical approach given how one might go about solving a jigsaw puzzle in the physical world. As such, I will bebreaking this section into subsections along those lines, beginning with the discussion on how two pieces are matched.Figure 3. Example Piece with Labeled Sides and Example ColorPatcheslution to this problem was to divide the resulting integral bythe length of the side, but even that did not completely solvethe issue. So instead I developed a new method that uses the“height” of the midpoint of the side relative to the x-axis asdefined by the rotated side. If the height is beyond a certainthreshold, it could be considered a head or hole. Otherwiseit is considered a flat side.Once the sides of the piece are determined and the information stored, the next step is to gather color informationabout the piece that will be used in the matching process.By using the mask created by the individual piece, I canuse Matlab functions to back out intensity levels for individual color channels for the entire piece. At first I grabbeda lot of information, and much of it is still in the code. Thisincludes average, minimum, and maximum intensity levelsfor each of the RGB color channels as well as each of theHSV color channels. After rather exhaustive experimentation with the matching algorithm, however, most of thisinformation proved to be hit or miss when it came to truecolor coordination across pieces. Since this is informationabout the entire piece, it is primarily used to find regionallikeness in the final puzzle image. After doing some research, one method for finding how similar two colors arein the spectrum is by calculating the E, which requiresthe color values to be in CIE’s L*a*b* color space. So, ultimately, the color values for each piece are translated tothis color space and the average “intensity” in each of thosechannels is found and stored.Not only do I store color information about the entirepiece, but also color information along each edge. Using a3.3.1Local Assembly – Piece-to-Piece MatchingI am beginning the discussion on how the puzzle is assembled by describing the method by which the pieces arematched to one another. While the algorithm works slightlydifferently whether we’re assembling the border or we’reassembling the inner pieces, the specific match parametersremain the same. I will describe the general case of twopieces being matched together and then discuss the specificnuances for each of the two global situations.What this algorithm is ultimately trying to find is a“match” between the edge of one piece and the edge of another piece. A “match” is defined as two pieces that “fit”together. Ideally, the two pieces that “fit” the best wouldalso be the “correct match,” so one would think that if thehead of one piece is similar to the hole of another piece,they would fit and we could move on. However, when trying to do this process with little to no human input, findingthe correct match is not as easy as finding two shapes thatare simply the inverse of one another. Especially when onethrows in measurement noise due to imperfect segmentationand image distortion. So instead, I try to use additional information about each piece in order to try and compute a“score” for a potential match.After extensive experimentation, the factors that twoneighboring pieces appear to have most in common are sidelength, color along the edge, and overall piece color. Additionally, I looked at the difference between the overlaid4

curves along each edge to determine an average overlap (orgap) – obviously the smaller the overlap or gap, the better the match. With these factors in mind, here is how thematching algorithm works.Once the algorithm determines the two pieces and theside of each piece to be matched, it first checks to makesure one is a head and one is a hole. If not, the match isdiscarded. It then compares the side lengths and the integrals along each edge. If the difference in side lengthsis significant (beyond approximately 10 pixels for the standard resolution image), the match is discarded. The integralof the curve along each edge is compared. If they are notapproximately equal and opposite, the match is discarded(the threshold for this varies based on image resolution –turns out it is not the best method for weeding out candidatematches so it is not the most strict). Next, the overlap is calculated by overlaying the two edges in XY-coordinate spaceand taking the difference (using pdist). The result is theoverlap, or gap, between the two pieces. If the average,minimum, or maximum overlap is beyond specific thresholds based on image resolution, then the match is thrownout. Once we’ve looked at the basic shape discriminants fordetermining whether a match is likely correct, we then lookat the color discriminants and determine the E. We do thisboth from a regional perspective (piece to piece) and froman edge perspective (using the patches along the edge). Eis essentially the “distance” between two colors in the colorspectrum and is determined using the following formula: L L 1Avg L 2Avg(1) a a 1Avg a 2Avg(2) b 1Avgb 2Avg p E L 2 a 2 b 2 b least two of the categories, so a score threshold of about280 (again, experimentally determined) can be set in orderto weed out incorrect matches.Once the local matching algorithm has pared down to afinal set of scored matches, it then returns these matches tothe global algorithm in score-priority order. The primarynuances that differ between local matching for the borderversus the inner pieces is the orientation of the piece. As Iwill soon discuss, the border pieces are aligned accordingto the flat edge, so the local matching only considers onepotential edge for each piece. And, because the border isbeing matched in the absence of the rest of the puzzle, thelocal matching algorithm does not have to consider any additional sides from other pieces that may come into play.Not so for the inner pieces. For the inner portion of the puzzle, a piece is being matched to a slot in a grid, and thatslot has neighboring sides. As will soon be discussed, thelocal matching algorithm will always have at least two sidesfor each internal piece, but could have upwards of three orfour to consider depending on the location of the slot andwhat pieces have been matched so far. In the inner case, thelocal matching algorithm has to ensure that the heads andholes all line up first, as before, but then determines all ofthe matching metrics per side and takes the average over thenumber of sides. The major difference here is that a singlepiece could fit into a slot in multiple ways, so piece orientation must be accounted for and the piece must be rotated inall valid configurations before the algorithm returns a set ofmatches. A single piece could potentially have four possible “matches” to a single slot, depending on hole/head orientation. The match thresholding and scoring are the sameacross pieces and edges in the inner piece matching as in theborder matching, the only true difference being that theyare averaged across each piece/edge to which the piece ismatched in the inner matching (which is unnecessary in theborder case).(3)(4)The E is found for each pair of patches along the edgeand the average of those patch values is used. Obviously,the lower the E, the closer the colors are in the spectrum.Once we’ve computed and captured these shape andcolor comparisons and have weeded out obviously badmatches, we then compute a match “score.” This scoreis found using experimentally determined weights that aremultiplied by the four key matching criteria: side lengthdifference, overlap difference, E along the edge, and Ebetween the pieces. Since these values tend to vary widelybetween matches and puzzles, the standard range of valuesfound for “correct” matches on one of the test puzzles wasused to develop a set of weights that somewhat normalizeseach parameter so that one specific criteria is not favored toomuch more than another. For most correct matches, whenmultiplied by the weights, the values should be no greaterthan 100. This means that, theoretically, a correct matchcould have a total score of up to approximately 400. However, in reality, most correct matches have low scores in at3.3.2Global Assembly – the Border PiecesIt is logical to begin the global assembly with the borderbecause the border pieces are distinct – they each have atleast one flat side. Since the piece matching algorithm is notperfect and does not always return the “correct” match asthe “best” match, a so-called “greedy” algorithm that simply places the “best” match between two pieces in the nextavailable slot will not necessarily result in a coherent solution (i.e. one might get something that is non-rectangularor even nonsensical). In order to provide for this possibility while not resorting to a “brute-force” approach thatruns through every possible combination of pieces, I decided to use a so-called “branch-and-bound” algorithm, normally used in the solution of the Traveling Salesman Problem (TSP). In the general description of the TSP, a salesman5

needs to do business in a number of cities spread out over aregion with defined distances between each. The salesmanwants to find the shortest overall route that goes to everycity only once and returns to his starting point – thus its adistance minimization problem.Much like the TSP, each match made between two piecesalong the puzzle border is given a score. Once a solutionis found, the total of all of the match scores that make upthat border solution should reflect how good the solutionis. Ideally, the smallest overall score will be the best andcorrect solution. However, that turns out not always beingthe case, as will be discussed.Since there are many ways of reaching a solution, weneed a way of capturing a large number of possible solutions and then finding the best one of those potential solutions. One way of doing this is the branch-and-boundmethod. This algorithm will be discussed shortly, but first Iwill describe the greater methodology for how the border isconstructed.The general construction of the border begins with acorner piece. We orient the piece such that the counterclockwise-most flat side is “down,” with the other flat sideto the “left” and a head or hole to the “right.” Matching isthen done to the “right” in a sequential manner. The localmatching algorithm, then, receives a left piece and a list ofpossible right pieces, all with the flat side down. It returns alist of potential right pieces. We then choose one of the rightpieces to be the new left piece and continue the process untilwe run out of possible right pieces. As we progress aroundthe border, when we hit another corner, we rotate the entire puzzle and continue as if the flat side of each piece is“down.”Now, since the potential number of solutions is (n 1)!where n is the number of border pieces, we want to constrain the number of solutions found through whatevermeans necessary. The local matching algorithm does a goodjob of weeding out very poor matches, but will still returnmultiple potential matches that could lead to a nonsensicalfull solution. In order to combat this we also place a set ofside length constraints on the puzzle such that the bordersolution must have side lengths corresponding to a rectangular puzzle. If we’ve gone too long without a corner pieceor if we get sides defined by corner pieces that do not equalone another, the solution is thrown out and we search for anew one.After all of this preamble, I am now going to describethe basic branch-and-bound algorithm that is used for theborder matching problem. The algorithm can be describedin the following manner:can be considered “children” or “branches.”3. Since the local matching algorithm returns a rankordered list of potential matches, start with the firstpotential match as piece B.4. Next, remove piece B from the list of pieces remainingto be matched and make piece B the new piece A.5. Use the new piece A to find more potential matches.6. This process continues until one of the following occurs:(a) We run out of pieces remaining – in this case wehave found a solution or “leaf.” We store this setof matches and their scores as a solution, backup, and see if we can find more solutions.(b) We run into a border constraint that isn’t satisfied– in this case we back up and see if another matchdoes satisfy the border constraint before movingon.(c) We do not get any potential matches for the current piece A – in this case we need to back up andsee if we can find another path using a differentpiece from an older set of potential matches.The algorithm either runs until it has exhausted the searchspace and found all possible solutions based on both the sideconstraints and the local matching thresholds, or until it hasobtained the number of solutions requested of it. As canprobably be surmised from the basic description above, onecan visualize this approach as a tree with the first piece atthe root and branches extending upward for each potentialmatch. If we are able to make it all the way up a branch toa leaf, then we have found a solution to the problem. If weget stuck on a branch and can’t expand, we come back downthe tree until we find another path that looks fruitful. In thisway we can reduce the total number of solutions tried towell below that which would be found through simple bruteforce.As one can see, because the problem is being solved ina nonlinear fashion, the number of solutions that might befound before the “correct” solution is highly dependent onseveral factors, not least of which are the first piece chosen and how well the first few pieces match. If incorrectmatches are made early in the process, it can take a longtime (and a lot of matches) before the correct solution isfound. And even when the correct solution is found, it maynot be the “best” solution as per the scoring system. Ideallythe “best” and “correct” would be the same, but that is notalways the case.1. Choose a starting piece (usually a corner) and call itpiece A.2. Use piece A to find a set of potential matches – these6

3.3.3PuzzleNameWookieStorm TroopsDroidsSpeederRey FinnKylo RenGlobal Assembly – the Inner PiecesOnce a border solution is found, it is passed to the global assembly for the inner pieces. The global assembly algorithmassembles the border pieces into a grid and then grabs the“upper left” open slot as the new “piece A.” This algorithmalso creates a grid with relative orientations for each piece.When the pieces were first characterized, they were eachoriented with “side 1” being “up.” Once they are placedin the final puzzle grid, we create a second grid with thesame dimensions that provides the relative 90 degree rotation from “up” for each piece (0-3). Because we know wehave the border completed, we can be assured that that firstslot will have at least two pieces along its edges. The morepieces along an edge, the more accurate and discriminatingthe score should be. The inner piece matching algorithmthen uses a similar branch-and-bound algorithm as in theborder case to find potential matches for this first slot. Itthen removes the piece from those remaining and movesacross the puzzle filling in all available pieces from left toright and then top down (like rea

Using Computer Vision to Solve Jigsaw Puzzles Travis V. Allen Stanford University CS231A, Spring 2016 tallen1@stanford.edu Abstract Many in the computer vision community have written papers on solving the “problem” of jigsaw puzzles for decades. Many of the former papers written cit