3
$\begingroup$

I want to solve a puzzle such as this one:

scrambled image

by using a genetic algorithm. When the number of pieces grow, and maybe some are rotated, the number of combinations become overwhelming. I am hoping that a genetic algorithm will be a lot faster than an exhaustive search. As a fitness function I can detect pieces that don't fit with each other using a gradient filter.

What crossover operator would you say is suitable for this type of problem? I have previously tried simulated annealing and have observed that pieces often correctly become each other's neighbors, but are in the wrong place in the image as a whole. Is there a crossover operator that can move such correct groups?

Are there any other considerations regarding the configuration of a genetic algorithm for this problem that comes to mind?

$\endgroup$
  • 1
    $\begingroup$ First you have to segment this into its original pieces. I don't know that a GA is going to work for that. Next you must re-order candidates. Any optimization requires a measure of goodness so how do you measure that the edges of two pieces go together? If you have a "DNA" string showing edge adjacencies then a GA might help you keep the good fits and update the bad ones. Do you have a target image? Could you take a image a few seconds before and use it to train an randomforest for pixel location by local metrics (mean, stdev, entropy, ...)? You could then get decent starting guess. $\endgroup$ – EngrStudent Oct 23 '14 at 13:09
  • 1
    $\begingroup$ @EngrStudent The pieces are of constant width so it is easy to partition the image. The "goodness"/"fitness" of a combination can be evaluated by using a gradient filter because the derivative in seams is disruptive if the pieces do not fit together. So this is what I did, I partitioned the image and flattened the matrix of pieces to a list ("chromosome"), but the problem is that the usual crossover operators don't work well because local arrangements that work in two dimensions aren't preserved. The reason is that the arrangement is two dimensional whereas the chromosome is one dimensional. $\endgroup$ – user55561 Oct 23 '14 at 15:49
  • $\begingroup$ I'm not sure what I mean by "usual crossover operators" since I haven't used GAs for combinatorial problems before. Using a target image would defeat the purpose of solving this problem, but since they are photographs/paintings we can probably assume that properties are different for different regions in the image, if that helps. $\endgroup$ – user55561 Oct 23 '14 at 15:49
  • 1
    $\begingroup$ In fact, this graph-theoretic approach shows how you can solve the puzzle deterministically in $O(n^2)$ time for $n$ rectangular puzzle pieces: just compare all $4(n-1)$ sides of $n-1$ pieces to a given side of one piece until you find the right one, freeze it, and iterate with the remaining $4n-1$ sides. That's scarcely an "overwhelming" number of combinations! $\endgroup$ – whuber Oct 23 '14 at 17:32
  • 1
    $\begingroup$ After giving this some thought overnight, I realize the problem can be quite challenging under certain circumstances. Imagine, for instance, an image with a uniform white border (as in many maps). The graph will indicate there are perfect matches among all border edges with each other. A greedy algorithm will fail dismally. You can get a lot of mileage out of noting that top/bottom and left/right sides create one-dimensional "subpuzzles" to solve and exploiting that to generate tentative coordinates for the pieces during the search, but even then some backtracking would still be needed. $\endgroup$ – whuber Oct 24 '14 at 14:16
2
$\begingroup$

Problem statement:

Given:

You have many subimages of an image. They are all squares of the same size (pixels by pixels). No connectivity is provided in the metadata or file ordering.

Assuming:

We are going to assume that when two edges match the error between them is zero, or has an absolute value of error that is sufficiently smaller than all other "matching errors" such that it can be clamped to zero.

We are also going to assume that no two non-contacting edges are identical.

We are going to assume that the images are not a trivial case. They are all uniformly the same color, for example.

We are going to assume that they are all facing the proper way, that they have not been "flipped".

Find:

The proper placement of edges such that the original (whole) image is re-assembled. Failing that, assemble as much of the whole image as possible.

My (first) Approach:

Make a hash of edges:

  • For each edge make a unique subimage and edge identifier
  • convert edge pixel intensity values into a vector
  • assemble these into a table (hash?)

Pre-processing the intensity-value-strings might improve performance:

  • treat each edge as a single vector in a higher-dimensional space
  • use PCA to center and scale intensity values
  • consider using PCA to reduce dimension if rank of eigenvalue matrix is less than its size
  • consider data whitening to move the data toward the "front" of the vectors so error compute can be truncated early if it gets too large.

Search for edges:

  • Pick a random image
  • Pick a random edge on the image
  • Get its vector from the table
  • while match error is not zero, and number of already-tried-matches-this-picking-of-this-edge is less than half the available set:
    • pick a random, unmatched edge of a unfitted sub-image
    • measure value of pixel-by-pixel intensity difference, store
  • sort hash by value of stored error measure from smallest magnitude to largest
  • pick top edge, not this edge off of hash
  • while match error is not zero, and number of already-tried-matches-this-picking-of-this-edge is less than half the available set:
    • pick a random, unmatched edge of a unfitted sub-image
    • measure value of pixel-by-pixel intensity difference ...
  • we might want to uniformly sub-sample the remaining un-matched hash elements at this point.

Thoughts:

  • This quit early will keep outer perimeter edges for trying to match when they don't have a match. It will also reduce the search space by half. I don't know if it is proper to call this "adding a poor mans greedy to the algorithm".
  • The pair smaller errors every other trip through is likely to put similar-looking edges next to each other and try to match them up. This should improve the likelihood of matching quickly using already computed data.
  • Data whitening and premature exit of comparison when error is above a certain value can also accelerate the process by 10x or better. PCA and dimension reduction can also do that. Mileage is going to depend on the perimeter-cells to total cells ratio of your subimages and the entropy in edge intensity values.
  • If the data is non-pristine, so that no matching edges have nonzero error, then an approach like this might assemble more of the image in less time than an exhaustive-search method.

As someone who has played many delightful games of boxes and dots with my younger siblings, cousins, nephews and nieces my intuition tells me that there are at least two parts of the game. The first is where you partition the general space into sub-blocks that are discontiguous in a way that gives enough choice that you can force your opponent into low-capture-size partitions while taking high capture-size partitions. The second is in actually taking those partitions and capturing as many individual boxes. This problem is that game in reverse. After some portion of the edge-matching process is complete, say 60% of the total number of edges, has been set then the transition to "endgame" can occur. In relation to "puzzle" metaphor - it is where you have big enough chunks and you look to tie them together. Majoring on connecting edge pieces will allow you to combine networks, and in one or two edge-matches can lock down many remaining image locations with regards to that first one. After the nodes are "connected enough" in terms of random subnets it becomes prudent to look only at net-edges and try to relate them to other net-edges.

$\endgroup$
  • $\begingroup$ Nice, I will consider this in detail later. $\endgroup$ – user55561 Oct 23 '14 at 22:44
  • $\begingroup$ It seems you overlook the advantages of using a suitable data structure. The algorithm is, at heart, dead simple. There will be pieces each having sides which are vectors. Put the sides as reversed vectors into a spatial data array (an MDS solution in 2D or 3D ought to be fine). They begin in an umatched state. For each unmatched side match it via lookup in the array to a side belonging to a different piece. If there is a match, declare this and the matched side to be matched. Otherwise, declare this side to be an edge. Repeat. (The delicate part is backtracking to handle incorrect matches.) $\endgroup$ – whuber Oct 24 '14 at 0:02
  • $\begingroup$ @whuber - Are you making it into a sort? Donald Knuth likes sorts. $\endgroup$ – EngrStudent Oct 24 '14 at 11:45
  • $\begingroup$ each edge could be an MD5 checksum, or similar. Perhaps the binary bits of each edge could be turned into characters to allow text based comparison (aka block compare vs. bit-by-bit). You could then make each edge and its mirror into checksums, and instead of looking at it as pixels you could look at it like matching strings. Proving lack of a match using the characters should be quite fast. Setting it up so that already matched edges are not re-considered might make it faster. $\endgroup$ – EngrStudent Sep 3 '16 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy