Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Image unshredding using a TSP solver

github.com

Post reply on HN
Print view View original

41–50 of 56 posts

Re: Image unshredding using a TSP solver

#41

Post by preygel »

robinhouston wrote: post #26
preygel wrote: post #22

A bit tangentially, this is also a great display of just how good readily available approximate solvers have gotten for a wide range of combinatorial optimization problems (like TSP). The LKH solver used here has rather impressive performance. From http://webhotel4.ruc.dk/~keld/research/LKH/ : "LKH has produced optimal solutions for all solved problems we have been able to obtain," and the studies linked there show t…

Not so long ago, we’d say “That’s an NP-complete problem” with the implication that it was hopeless to expect an efficient solution. Now (to exaggerate a little) it’s more like a sign that there probably is an efficient solution using some powerful solver. LKH is a lovely piece of work. I used it a couple of years ago to find a counterexample to an unimportant but fairly long-standing conjecture in combinatorics[0],…

Absolutely!

Not to mention the often impressive performance of "general" MIP solvers. It is only a shame that the best ones there are commercial (Gurobi followed by Cplex). That said, Cbc is lovely in a wide range of cases, and is open-source.

Re: Image unshredding using a TSP solver

#42

Post by Flabenmaben »

preygel wrote: post #22

A bit tangentially, this is also a great display of just how good readily available approximate solvers have gotten for a wide range of combinatorial optimization problems (like TSP). The LKH solver used here has rather impressive performance. From http://webhotel4.ruc.dk/~keld/research/LKH/ : "LKH has produced optimal solutions for all solved problems we have been able to obtain," and the studies linked there show t…

How is it determined that optimal solutions have been produced? Does an exact solver have to find the same solution, or is there a more analytic / less computationally-intensive method?

Re: Image unshredding using a TSP solver

#43

Post by Xcelerate »

inimino wrote: post #34
Xcelerate wrote: post #31

Earlier quoted context omitted.

I wouldn't be surprised if a complete shuffling could be solved — i.e., every pixel is given a new random location. (Source: I do research involving stuff like this.)

How could that be possible? Wouldn't that literally throw away everything but the distribution of colors in the image?

An error function against neighboring pixels alone probably would not be enough to reconstruct the image (there are information theoretic limitations on how much noise can exist for a certain model before ground truth recovery becomes impossible); however, depending on the type of image, additional information could be gleaned from images that fall into the same category.

For instance, if I assign each pixel a random color and call that my "image", and then scramble all of the pixels, it is easy to see that recovery of the original image is mathematically impossible. However, if I use a photograph of a person standing in front of a car, information gleaned from similar types of photos could be sufficient to allow complete recovery given only the exact distribution of pixel colors. I don't know whether this is true, but I wouldn't be surprised if it is. (Actually, this seems like a fun hobby project. I may give it a shot.)

Re: Image unshredding using a TSP solver

#44

Post by inimino »

Xcelerate wrote: post #43
inimino wrote: post #34

Earlier quoted context omitted.

How could that be possible? Wouldn't that literally throw away everything but the distribution of colors in the image?

An error function against neighboring pixels alone probably would not be enough to reconstruct the image (there are information theoretic limitations on how much noise can exist for a certain model before ground truth recovery becomes impossible); however, depending on the type of image, additional information could be gleaned from images that fall into the same category. For instance, if I assign each pixel a random…

I can see making a heuristic assessment that says "based on the blues and greens there is probably a large expanse of sky and some trees in the original image" but getting from there to where the trees are and putting the leaves back on the trees in the right places, I can't see that being even mathematically possible. It's a million-piece jigsaw puzzle where each piece is square and monochromatic.

If enhancing a low-resolution image to regain lost information is basically impossible, getting back a picture from a color histogram would surely be much more impossible.

Re: Image unshredding using a TSP solver

#46

Post by botw »

I guess the difference with the simulated annealing approach would be that this approach(and the simple picking-the-most-similar-column approach) assumes you know the particular shredding method in advance, whereas the simulated annealing does not have this requirement. For example, does this still work out for shredding diagonally in some unknown degree?

Re: Image unshredding using a TSP solver

#47

Post by botw »

robinhouston wrote: post #26
preygel wrote: post #22

A bit tangentially, this is also a great display of just how good readily available approximate solvers have gotten for a wide range of combinatorial optimization problems (like TSP). The LKH solver used here has rather impressive performance. From http://webhotel4.ruc.dk/~keld/research/LKH/ : "LKH has produced optimal solutions for all solved problems we have been able to obtain," and the studies linked there show t…

Not so long ago, we’d say “That’s an NP-complete problem” with the implication that it was hopeless to expect an efficient solution. Now (to exaggerate a little) it’s more like a sign that there probably is an efficient solution using some powerful solver. LKH is a lovely piece of work. I used it a couple of years ago to find a counterexample to an unimportant but fairly long-standing conjecture in combinatorics[0],…

I always thought "NP-complete/NP-hard" metaphor only meaningful in theoretical work. In practice, it does not make much sense in guiding what/how the real world problem is to be solved.

Re: Image unshredding using a TSP solver

#48

Post by robinhouston »

botw wrote: post #47
robinhouston wrote: post #26

Earlier quoted context omitted.

Not so long ago, we’d say “That’s an NP-complete problem” with the implication that it was hopeless to expect an efficient solution. Now (to exaggerate a little) it’s more like a sign that there probably is an efficient solution using some powerful solver. LKH is a lovely piece of work. I used it a couple of years ago to find a counterexample to an unimportant but fairly long-standing conjecture in combinatorics[0],…

I always thought "NP-complete/NP-hard" metaphor only meaningful in theoretical work. In practice, it does not make much sense in guiding what/how the real world problem is to be solved.

I don't know. I find it useful in practice. Apart from anything else it means there's (probably) no point looking for an exact polynomial-time algorithm, which can save a lot of wasted effort. But it also gives useful clues about what sort of algorithmic approaches might be useful, and allows you to relate your problem to a huge amount of existing research.

It's really basic taxonomy: what sort of problem are we dealing with? If you don't know that, how could you even begin to design a reasonable algorithm for it?

Re: Image unshredding using a TSP solver

#49

Post by szemet »

syphilis2 wrote: post #5

Could be used to compress images? Perhaps instead of shuffling the columns and rows randomly they could be ordered in ways that are better suited for compression.

To me the whole experiment suggests otherwise:

it shows that naturally occurring images are organized by having similar rows and columns close to each other, which is - by default - good for most compression algorithms that prefer regularities/similarities to be as local as possible.

edit: but it can be good for other cases, where there are no good-enough default orders. For example "customer - product bought" matrix (binary matrix, customer rows, product columns: X customer bought Y product = 1, otherwise =0 ).

Here the order of rows/columns are not predefined, and ordering by similar customers and products the compression of the matrix could be improved. Finding these similarities also can be a good starting point for some recommendation/collaborative filtering engine.

Re: Image unshredding using a TSP solver

#50

Post by Retr0spectrum »

robinhouston wrote: post #26
preygel wrote: post #22

A bit tangentially, this is also a great display of just how good readily available approximate solvers have gotten for a wide range of combinatorial optimization problems (like TSP). The LKH solver used here has rather impressive performance. From http://webhotel4.ruc.dk/~keld/research/LKH/ : "LKH has produced optimal solutions for all solved problems we have been able to obtain," and the studies linked there show t…

Not so long ago, we’d say “That’s an NP-complete problem” with the implication that it was hopeless to expect an efficient solution. Now (to exaggerate a little) it’s more like a sign that there probably is an efficient solution using some powerful solver. LKH is a lovely piece of work. I used it a couple of years ago to find a counterexample to an unimportant but fairly long-standing conjecture in combinatorics[0],…

Z3 (and other constraint solvers) are very impressive. The most interesting application I've seen is in binary exploitation and reverse-engineering through symbolic execution.

Angr is a very popular framework which allows for symbolic execution of binaries using Z3 as a backend. It's made a whole class of common CTF challenges almost trivial:

https://docs.angr.io/docs/examples.html

Post reply on HN