Chris Pollett > Students > Venkatesh

    Print View



    [CS 297 Proposal]

    [Deliverable 1 - Android App for Inter-activity Communication]

    [Deliverable 2 - Solver Performance on Custom Images]

    [Deliverable 3 - Paikin Tal Placer]

    [Deliverable 4 - Neural Networks for puzzle reassembly]

    [CS297 Report - PDF]

    [Mixed bag placer review]

Deliverable 2: Solver performance on custom images

The existing solver uses a hierarchical clustering mechanism for assembling a mixed bag of puzzles. This mechanism is used to assemble multiple puzzles without knowing the count of puzzles to solve. The images that were used for mixed bag assembly were fetched from the base papers and most of the images were high contrast pictures with several distinct regions that can be segmented into chunks with relatively higher level of accuracy. However, a typical grayscale document does not have many distinct regions. The contrast level is almost uniformly distributed throughout the image. These two factors pose some challenges to the existing model. The purpose of this exercise is to figure out the specific portions of the algorithm that are the areas of concern.

The algorithm for placement is as follows: Jumble individual pieces from across puzzles: Every puzzle is split into multiple pieces and the pieces from across individual puzzles are jumbled so that a mixed bag of puzzles is created. Calculate piece distance and asymmetric mutual compatibility: Based on the puzzle type which is either type 1 (with no piece rotation) or type 2 (with piece rotation), possible neighbors for each piece are identified and a distance matrix is created for each piece with the value at position (i,j) of the matrix representing the distance value between the said piece and piece j along the side i. Since the pieces are square, there are four different values for i. The asymmetric mutual compatibility is then calculated.

It can be seen that the main reason the solver performance is underwhelming for documents is that there are no strong segments. This is because the piece distances are more or less uniform throughout the image. The potential pitfalls identified from this deliverable are as follows:

  • The use of gradients for piece distance calculation results in several pieces of same distance value, hampering the accuracy of best buddy estimation.
  • Weak segmentation for images of text.

The next step involves implementing the placer algorithm in java to substantiate the hypotheses above.