Solve large jigsaw puzzles using genetic algorithms and OpenCV | Hacker News Reader

Solve large jigsaw puzzles using genetic algorithms and OpenCV

github.com

73 pointsnemanja-m29 comments

To be pedantic, this is not really a jigsaw puzzle, the pieces are squares, I'm guessing the technique may be applicable to real jigsaw puzzles, too.

I'd like to see this applied to puzzles with unique pieces like the ones here (https://libertypuzzles.com/about)

I thought the same thing when I saw it, but I think this just makes it a more challenging problem. You don't get the constraints of edge and corner pieces to start. There is no confirmation of fit with unique interfaces. When every piece is equally interchangeable the problem is more difficult from a human perspective.

Although, from a computer perspective it also makes the edge comparisons nice and clean.

But in case of square puzzles their orientation and border match is limited

I'm rather disappointed to see the Lena image still being used as a demonstration for image processing techniques (regardless of its historical context).

At best, it's crass and tasteless. At worst, it's openly disrespectful and hostile to women. There are millions (billions) of images on the Internet that are available for use under a permissive license - it doesn't take a lot of effort to use something else.

Why is it crass and tasteless? And why is it openly hostile and disrespectful to women?

If I need to explain to you why using a nude image of a model (taken from a pornography magazine, no less) is hostile and disrespectful, then I suspect you are part of the problem.

Genius.... If somebody asks you to explain something, well better just say they are part of the problem and not explain it at all... that will really improve things. Great contribution there.

It is NOT a nude image. It might be a cropped version of a what originally was a nude image, but that doesn't make it a nude image. If i crop you out of a picture, its no longer a picture of you? Now it is just a woman with a hat and a shoulder that is not covered with some fabric. If mentally you instantly see the original picture, perhaps you have 'stared' too long at that playboy issue.

Though the point others make in this thread, i think is very valid, it is not a jigsaw puzzle. I was expecting software for when i visit my mom (who likes making jigsaw puzzles), quickly snap a picture on my phone of the table with all the pieces and it would assist me in solving it while she leaves the table for a bit to make tea/coffee. (leaving mom flabbergasted with: how did you...)

For any curious minds wondering about the provenance of the Lena image, here's a short article written in 1996 by the (at the time) editor-in-chief of IEEE Transactions on Image Processing. The controversy (and both viewpoints) are summed up quite adequately.

http://www.cs.cmu.edu/~chuck/lennapg/editor.html

To respond to your point - while you might be technically correct in that the Lena image commonly used today is not a "nude" image per se... are you genuinely saying that you don't understand why some people don't like it - or why it's unpleasant and/or degrading to women in the field? Its provenance is well known, and the very association with Playboy (nudity notwithstanding) is likely enough to irritate or upset women in image processing/computer vision circles (I say this having had personal experience of various -- female -- lecturers at my alma mater disagreeing with the use of the Lena image).

I think you're either intentionally or unintentionally looking to create/perpetuate controversy where there is none. The post you linked mentions itself that most people weren't even aware of the origin of the image, which I think is probably the only thing which may cause it to be offensive towards prudish people in general.

Personally, I find it strictly more offensive that people are outraged on behalf of these supposed women, who are so delicate that the use of a heavily cropped playboy image outrages, offends, or discourages them from a field of study. I think regardless of which image you choose, you'll always find some group of people who are offended by it, and anyone who is offended by an image as tame as this one probably has some growing up to do.

There are several prominent women in CS that I know personally and respect (some of whom are image processing/CV researchers), who find the image sexist and demeaning. I sympathise with their viewpoint and am inclined to agree with them. I'm clearly not looking to create controversy or be offended on other people's behalf - I'm just trying to not be a dick.

I didn't even realize it was a nude image, nor that it was taken from a pornography magazine. Thank you for the context.

In that case, I apologise! It was not my intention to be blunt or rude if you were asking out of curiosity - sincere apologies.

I thought it was a Playboy. Does Lena have a problem with it or something?

No but individuals, particularly women, working in AI might have a problem with objectification of women.

The new Victorians.

Respect for individuals as beings is completely orthogonal to prudishness, and it is disingenuous of you to conflate the two issues. If you disagree, see any modern sex-positive sex blog, most of which manage both to respect women, and which – by definition – are not prudish.

Would this also work for fitting non-rectangular images together? For example, lets say I have a whole bunch of irregular shaped pieces of flat paper (with pictures on them) and I want to fit them together in a single orientation to cover the smallest 2D area?

That sounds more like a bin-packing problem than a jig-saw problem. If the irregular pieces fit in a specific way the problem is simplified (just check interfaces), if they don't the problem is much harder as you'd have to calculate the minkowski sum of each additional piece to see how they fit together.

Reminds me of the lego sorting project, https://jacquesmattheij.com/sorting-lego-the-software-side

Having seen the Sudoku solver that's also on the front page, I won't be truly impressed until I've seen the ARKit implementation...

I wonder, is a jigsaw always solved when you find a configuration with the least amount of high frequency energy?

I suspect the answer is no in theory and yes in practice.

If any image is legal as the final picture, I can construct a picture which changes suddenly at the intersection of puzzle pieces. That would be a terrible puzzle in practice, though. You would have to carefully consult the box to see if you had put it together or not. So I suspect for any real jigsaw puzzle, the answer is yes.

There are jigsaw puzzles that'd do exactly rigid kind of thing to annoy the puzzle assembler and even ones that have a uniform color do the measured entropy at all edges would be 0.

I wonder how well it would perform against the Eternity II puzzle.

So how do you calculate the fitness score?

>> the sum (over all neighboring pixels) of squared color differences (over all three color bands) should be minimal

I wonder if a technique like this will work for unshredding documents.

We can already do that even if the shreds are 1px wide https://github.com/robinhouston/image-unshredding

The example image contains a large scale object spanning the whole image and has lots of fine-grained detail. While an impressive demo, it probably won't work as well on black-and-white documents, because the edge will have very little information to determine adjacency. Additionally, shredded documents can have two sides and the shredded stripes might be so small that it becomes difficult to tell up from down. That adds another exponential search space on top of the Traveling Salesman Problem.

That said, reconstruction of shreds is probably possible in most cases, although there is still lots of research to be done in this space. For example the Fraunhofer Society has a project to reconstruct torn documents of the East German StaSi surveillance agency [1]. There seem to be very few detailed publications on their methods, but I did find a high-level overview [2]

[1] http://www.bstu.bund.de/EN/Archives/ReconstructionOfShredded...

[2] https://doi.org/10.1007/978-1-4471-4763-3_8 (The Springer page is paywalled, but the DOI can help you find cheaper sources.)

Reply on news.ycombinator.com