Solving a picture jumble!

Question

What algorithm would you make a computer use, if you want to solve a picture jumble?

You can always argue in terms of efficiency of the algorithm, but here I am really looking at what approaches to follow.

Thanks

Answer 1

Solving a jigsaw puzzle can basically be reduced to matching like edges to like edges. In a true jigsaw puzzle only one pair of pieces can properly be interlocked along a particular edge, and each piece will have corners so that you know where a particular side starts and ends.

Thus, just find the endpoints of each edge and select a few control points. Then iterate through all pieces with unbound edges until you find the right one. When there are no more unbound edges, you have solved the puzzle.

Answer 2

What you need to do is to define an indexing vocabulary for each face of a jigsaw puzzle, such that the index of a right-facing edge can can tell you what the index of a corresponding left-facing edge is (e.g, a simple vocabulary: "convex" and "concave", with "convex" on a face implying "concave" on a matching opposite face), and then classify each piece according to the indexing vocabulary. The finer the vocabulary, the more discrimantory the face-matching and the faster your algorthm will go, however you implement it. (For instance, you may have "flat edge, straight-edge-leans-left, straight-edge-leans-right, concave, convex, knob, knob-hole, ...). We assume that the indexing scheme abstracts the actual shape of the edge, and that there is a predicate "exactly-fits(piece1,edge1,piece2,edge2)" that is true only if the edges exactly match. We further assume that there is at most one exact match of a piece with a particular edge.

The goal is grow a set of regions, e.g., a set of connected pieces, until it is no longer possible to grow the regions. We first mark all pieces with unique region names, 1 per piece, and all edges as unmatched. Then we enumerate the piece edges in any order. For each enumerated piece P with edge E, use the indexing scheme to select potentially matching piece/edge pairs. Check the exactly-fits predicate; at most one piece Q, with edge F, exactly-matches. Combine the regions for P and Q together to make a large region. Repeat. I think this solves the puzzle.

Answer 3

To elaborate on Ira Baxter's answer, another way of conceptualizing the problem is to think about the jigsaw puzzle as a graph, where each piece is a node and each iterface with another piece is an edge.

For example if you were designing a puzzle game, storing the "answer" this way would make "check if this fits" code a lot faster, since it could be reduced to some sort of hash-lookup.

Answer 4

.1 Find 2x2-grams such that all four edges will fit. Then, evaluate how well the image content matches with each other.

  P1 <--> P2
  ^       ^
  |       |
  v       v
  P3 <--> P4

.2 Tag orientations (manually or heuristically), but only use them as heuristics scores (for ranking), not as definitive search criteria.

.3 Shape Context