74462

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

Answer1:

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.

Answer2:

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.

Answer3:

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.

Answer4:

.1 Find <strong>2x2-grams</strong> 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 <strong>orientations</strong> (manually or heuristically), but only use them as heuristics scores (for ranking), not as definitive search criteria.

.3 <strong>Shape Context</strong>

Recommend

  • javascript and dragging in firefox
  • jQuery knob tron skin issue
  • find multiple edges given 2 vertices in BOOST graph
  • Fixing the size of JEditorPane Content
  • Convert a list with non-fixed length elements to tensor
  • iPhone: Stop UIScrollView from auto scrolling when UITextView text is changed
  • How to target a single image map area when multiple image maps are on the same page with jQuery
  • What is the equivalent of Matlab's imadjust in python?
  • bty = “n” in ggplot2
  • Use WPF object to 'punch' hole in another?
  • R script - least squares solution to the following [duplicate]
  • How to change shape of square to dot in XYSplineRenderer Graph
  • OpenCV with Python error - Assertion failed ((mask.type() == CV_8UC1 || mask.type() == CV_8SC1)) in
  • How to render two pd.DataFrames in jupyter notebook side by side?
  • Using meshgrid to convert X,Y,Z triplet to three 2D arrays for surface plot in matplotlib
  • QVideoWidget: Video is cut off
  • Calculating gradient norm wrt weights with keras
  • how to create aggregation on a graph from CONSTRUCT
  • Case insensitive search in CQ5 using querybuilder
  • friend declaration in protected section
  • Assignment of Allocatables of Different Shapes in Fortran [duplicate]
  • Broadcast advanced indexing numpy
  • How to identify incomplete rectangles in openCV
  • Thrust filter by key value
  • Python equivalent of Scala's exists() function?
  • How to add new index numbers to the upsampled data while preserving the orginal indices one
  • Plotting A Hyperboloid
  • Why should be the function backward be called only on 1 element tensor or with gradients w.r.t to Va
  • Base64 as method of sanitizing user input for Mysql
  • Cythonized function unexpectedly slow
  • How to reshape a 3D numpy array?
  • How to change placeholder text in an autocomplete activity of android google place?
  • Calculating ratio of reciprocated ties for each node in igraph
  • How to use remove-erase idiom for removing empty vectors in a vector?
  • How to convert from System.Drawing.Color to Excel.ColorFormat in C#? Change comment color
  • retrieve vertices with no linked edge in arangodb
  • sending mail using smtp is too slow
  • Busy indicator not showing up in wpf window [duplicate]
  • Why is Django giving me: 'first_name' is an invalid keyword argument for this function?
  • How can I use `wmic` in a Windows PE script?