Computational Jigsaw Puzzle Solving – Programmer’s Manual

Computational Jigsaw Puzzle Solving – Programmer’s Manual

Programmer’s Manual

Basic instructions on how to activate the solver

  1. Download the code from the Download section.
  2. The code is a Matlab function that receives several parameters. The first parameter is a path for an image which holds all the puzzle pieces, this is the only mandatory parameter. The second parameter represents the part’s number used by the solver as a seed. If you omit the second parameter, the solver will randomly select a seed for you. The third parameter represents the part’s square size. If omitted, the solver will use 28 x 28 as the default part’s size.
  3. Note that the image will be cropped if its size is not an integral multiple of the part’s size (both height and width).
  4. You may find many useful images in the Download section.
  5. The solver does not use the given image in any way except for cutting it and extracting the bag of pieces from which the solution is generated. You do not need to take our word for it. Rather, you are welcome to feed the solver a scrambled image which can be generated by the GeneratePuzzle function (found in the Download section).
  6. For a full review on the solver’s parameters and return values visit the Manual section.

Several basic examples

  • % A seed will be randomly selected and each part is of size 28 x 28.
    [directCompVal, neighborCompVal] = JigsawSolver(‘C:\Temp\imData\432\1.png’)
  • % The seed will be part number 125 and each part is of size 28 x 28.
    [directCompVal, neighborCompVal] = JigsawSolver(‘C:\Temp\imData\540\2.jpg’, 125)
  • % The seed will be part number 88 and each part is of size 56 x 56
    [directCompVal, neighborCompVal] = JigsawSolver(‘C:\Temp\imData\432\15.png’, 88, 56)

The solver’s Matlab function

Our fully automated solver has several input variables and parameters that control its operation. To use it download the code and run the following routine:

[directCompVal, neighborCompVal, estimatedBestBuddiesCorrectness, estimatedAverageOfProbCorrectness, solutionPartsOrder, segmentsAccuracy, numOfIterations] = JigsawSolver(I, firstPartToPlace, partSize, compatibilityFunc, shiftMode, colorScheme, greedyType, estimationFunc, outputMode, runTests, normalMode,resPath, debug)

Input parameters are:

  1. I – The image full path
  2. firstPartToPlace – The index of a part which will be used as the seed (i.e. the first piece put in place).
  3. partSize – A square part size, this size should divide with the image size or the image is cropped
  4. compatibilityFunc – The type of compatibility function to use
    • 0 – Dissimilarity
    • 1 – Prediction-based Compatibility (Default)
    • [p, q] – Lpq norm. Where p and q are integers
  5. shiftMode – Which shift module to use
    • 0 – None
    • 1 – Move largest segment across all possible locations and take the best placement
    • 2 – Growing largest segment using estimationFunc estimation metric to measure convergence (Default)
    • 3 – Growing largest segment but with fixed number of iterations
  6. colorScheme – which color space to use for processing
    • 0 – RGB
    • 1 – LAB (Default)
    • 2 – HSV
  7. greedyType – The greedy solver criterion for choosing which part to place next on the board (some of these are experimental and not described in the paper)
    • 0 – Multiplication compatibility
    • 1 – Average compatibility
    • 2 – Narrow Best Buddies with multiplication
    • 3 – Narrow Best Buddies with average (Default)
  8. estimationFunc – Which type of estimation metric will be used for conversion
    • 0 – Best Buddies (Default)
    • 1 – Average of compatibilities
  9. outputMode – The desired visualization of the output
    • 0 – None (only return values)
    • 1 – Output image only (Default)
    • 2 – Output image + save figures and data to resPath
    • 3 – Create a visualization movie in resPath named ‘JigsawSolverVisualization.avi’ (will not activate solver!!)
  10. runTests – Should run in test mode (boolean value. Default is false). Test mode runs basic unit tests and compatibility function tests.
  11. normalMode – What method should be used for compatibility normalization
    • 1 – Linear according to the max value
    • 2 – Same as used by Cho et al
    • 3 – Exponent according to median value
    • 4 – Exponent according to first quartile value (Default)
  12. resPath – The path where resources will be created. ‘C:\temp\’ is the default
  13. debug – debug arguments (Enables you to see each of the solver’s placements visually)
    • 0 – Off (Default)
    • 1 – Manual (the user can control the solver’s progress)
    • 2 – Manual + create debug movie in resPath named ‘JigsawSolverInAction.avi’
    • 3 – Automatic (the user can only see the progress)
    • 4 – Automatic + create debug movie in resPath named ‘JigsawSolverInAction.avi’

Return values are:

  1. directCompVal – The solution’s direct comparison value
  2. neighborCompVal – The solution’s neighbor comparison value
  3. estimatedBestBuddiesCorrectness – Best buddies correctness estimation metric value
  4. estimatedAverageOfProbCorrectness – Correctness estimation via average metric value
  5. solutionPartsOrder – The solver’s solution order (left -> right, top -> bottom order)
  6. segmentsAccuracy – What is the percentage of correct parts in the largest segment
  7. numOfIterations – The number of iteration it took the solver to converge

Few examples:

% Creates a visualization movie of the jigsaw problem for this image and part size.
% The movie will be saved as ‘C:\temp\SolverResults\JigsawSolverVisualization.avi’
JigsawSolver(‘C:\temp\imData\432\18.png’, 0, 28, 22, 2, 1, 3, 0, 3, 0, 4,’C:\temp\SolverResults\’,0);
% Activate the solver in debug mode that will also generate a debug movie.
% The movie will be saved as ‘C:\temp\SolverResults\JigsawSolverInAction.avi’
JigsawSolver(‘C:\temp\imData\432\14.png’, 0, 28, 22, 2, 1, 3, 0, 1, 0, 4,’C:\temp\SolverResults\’,2);

The GeneratePuzzle function:

The solver’s code uses the original image only to generate the parts, and to compare its result with the desired output to evaluate performance (i.e., using performance metrics). You can feed the solver with a scrambled image, which will generate similar puzzle solutions. However, notice that if you choose to do so, the reported performance metrics will become meaningless since the generated solution will be compared to a scrambled image.
The function has several input variables:
  1. src – The full path of the image to scramble
  2. dest – The full path of where the scrambled image will be created
  3. partSize – The part’s size which will be used to cut the image into parts. Default value is 28
% An example for creating a scrambled image with part size 28 x 28.
GeneratePuzzle(‘c:\temp\imData\432\8.png’, ‘c:\temp\imData\432\8.mix.png’)
% An example for creating a scrambled image with part size 56 x 56.
GeneratePuzzle(‘c:\temp\imData\432\2.png’, ‘c:\temp\imData\432\2.mix.png’, 56)