typodupeerror

## A Faster Jigsaw Solving Algorithm104

Posted by Unknown Lamer
from the computers-ruin-everything dept.
mikejuk writes "Andrew Gallagher at Cornell University in Ithaca, New York has improved the standard approach to automated jigsaw solving by copying what humans do in finding groups of pieces that best match and working outwards from there. With a speed of 10,000 pieces per 24 hours, it can solve large puzzles. Not only that, but the type of jigsaw it solves is more difficult than the usual in that the pieces are square and can be placed in any orientation. It is so good it can even solve problems consisting of a number of mixed up pieces without being told how many or their dimensions. Of course, as well as having fun beating humans at another recreational pastime, the technique could be used to unscramble shredded documents, as per the recent DARPA challenge."
This discussion has been archived. No new comments can be posted.

## A Faster Jigsaw Solving Algorithm

• #### Seems slow. (Score:1)

Obviously I don't understand the complexity here but it seems like that is a long time.

By my logic:
- pick 1 of the pieces as a start and pick 1 side of that piece
- now pick another piece and there are 4 possible arrangements to match your selected starting side (assuming square-ish pieces)
- on average, you'll need to check 1/2 of the remaining 9,999 pieces to get the matching one and each of 4 orientations
- so the first side of the first piece will requires, on average, 19998 checks
- next edge you select wi

• #### Re:Seems slow. (Score:5, Informative)

on Tuesday June 19, 2012 @04:11AM (#40367285)

Inexact matches. In the puzzle described in the paper, the pieces are all square (no notches). So the algorithm has to decide which edge matches best based on the similarity of the pixels, but it could be wrong or there may be multiple pieces that look like they match equally well (e.g. sky pieces which look very similar).

In the cases where it's wrong, it may have to throw out some of the fittings -- e.g. if you have a bunch of smaller groups of tiles that seem to fit together, but when you put it all together the puzzle isn't rectangular, then you have to break up the groups and try again. You can't just match one tile and be done with it.

• #### Re: (Score:1)

You sir, should be writing the summaries ... would have saved me reading the paper - which I eventually did do after posting my random musings.

• #### Re: (Score:2)

The edge of the puzzle: you can try what you want at the outside, but you won't (shouldn't) get a match there. On the other hand if the edge is a black line, the algorithm may go haywire as to outside edges form a perfect match against one another.

There may be more than one puzzle included.

One piece may match against several others, but only certain groups of four may match together.

Some pieces may have an imperfect match, the pattern continues (to our eyes) but one edge i

• #### Immediate application (Score:3, Informative)

on Tuesday June 19, 2012 @05:07AM (#40367437) Homepage
Woman Throws Fit and Tears up 50,000 RMB Cash, Takes Bank 6 Hours to Piece Together Just 1 Bill [chinasmack.com]

On the morning of May 3rd, Sichuan Chengdu city resident Lin Zhaoqiang carried 50,000 yuan in torn 100 yuan bills from Chengdu Jintang to the Bank of China Sichuan Branch, looking for help. May 1st, Lin Zhaoqiang's wife all of a sudden had a fit and tore the 50,000 yuan life-saving money into pieces. Facing thousands of pieces of cash, 12 bank employees sorted and spliced for 6 hours only to piece together a single 100 yuan bill. The remaining money, if unable to be pieced back together, face the unfortunate possibility of being declared null and invalid. Because this money is for treating his wife's mental illness, Lin Zhaoqiang said he won't give up.

One of the commenters said they should just weigh the cash, but obviously that would be too simple. Nothing is simple when dealing with Chinese banks and their ridiculous rules. They'll flat-out refuse to take small bills or coins ("What the heck are we going to do with all these jiao notes? [chinasmack.com] What are we, a bank or something?")

• #### Improvements? (Score:1)

A possible improvement to the algorithm would be to check all new edges during a merge of two components rather than just testing for whether the constraint of planarity is violated. This would avoid errors in merges - many of the sample images show components that join well on one or two edges, but badly on others.
• #### Kodak (Score:1)

The original paper was written at Eastman Kodak Research Laboratories. I am guessing we won't be seeing a follow up paper from him.
• #### Paper burner (Score:3)

on Tuesday June 19, 2012 @06:53AM (#40367809)
Your paper shredder is no longer sufficient. I am here to market to you a paper burner!
• #### Very disappointing. (Score:4, Insightful)

on Tuesday June 19, 2012 @08:57AM (#40368597) Journal
The algorithm is matching square tiles and it matches the color distribution along edges. If they are working on shape fitting, (all pieces are of uniform color, but each piece is of different shape, and one has to fit them to all to form a rectangle or square) it could lead to some really useful applications. After it has been extended to 3D, they can try to engineer antibodies to fit into the slots of viruses and bacteria. Well, they went for the simpler problem of square tiles and color map matching at the edges.

Here every edge has a color distribution and another edge of another tile with matching distribution. The fundamental solution was proposed originally in a Perry Mason novel by Erle Stanley Gardener. (As reported by Donald Knuth in his book/manual on TeX ). Perry Mason asks Paul Drake to find the two rentals by the same person just half an hour apart. Paul Drake says, "there are thousands of rental records, I would never find the match in time". Perry Mason says, "Nah. Just sort all the records by name, and look for duplicates".

Sorting by name, is grandiloquently called "Lexicographic Ordering" in comp sci. Create a lexicographic value for the color distribution on each edge, sort it by that order and look for duplicates. Here areas of uniform color would get multiple duplicates and one has to prune the tree. That is where these guys claim to have made some improvement. It is a nice problem I would give to some master's students learning heavy duty scientific computing. But I think shape matching has a lot more potential in developing antibodies and medicines.

• #### Time complexity? (Score:2, Insightful)

by Anonymous Coward

"With a speed of 10,000 pieces per 24 hours" is not useful. What is the time complexity?

• #### Shredded documents (Score:2)

That is an easy problem to solve if you don't care which side of the document you recover.
• #### Kids? (Score:2)

They should program in virtual 3 year old to attempt occasional toddler attacks on the puzzle, attempting to eat, and occasionally succeeding in carting off pieces it then the system has to scour it's house (system files?) to find...

#### Related LinksTop of the: day, week, month.

Today is the first day of the rest of your life.

Working...