# Unscramble images without trying all permutations

I try to write an algorithm that unscrambles images that were before scrambled by mixing up small blocks:

My idea is that in the bottom image there are more "sharp" corners compared to the image above. Therefore I try to minimize the functional:

energy(image)
{
score = 0;
for(pixels inside the image)
score = score + abs(pixel sum of sourrounding 4 pixels - 4 value of internal pixel)
}


The energy should therefore be high if there are many hard edges and low for the original image. In a test I found that the original image has the score $845.812$ whereas the scrambled one has the score $1.085.521$ so the approach might be worth a try.

My question is whether there is an efficient method to minimize the energy function now without trying all $n!$ permutations (too many). Or a different approach I didn't come up with.

-
Why are there 3 and not 4 surrounding pixels? And don't you have to take an absolute value or a square somewhere? Otherwise the interior contributions will cancel out and your function will only describe the boundary. – joriki Sep 3 '11 at 9:49
You are right: its 4 pixels and absolute value. I did it correct in the original formula but got it wrong in the pseudocode. – Listing Sep 3 '11 at 10:23

I don't think there's an analytic solution to this. Here's how I would approach it. Instead of calculating the entire energy for the entire image, for each pair of blocks and each of the four directions in which the blocks might form an interface, calculate the energy contribution resulting from that interface. That gives you an energy defined directly on the permutations of the blocks, and you don't have to deal with the image anymore. You can apply any combinatorial optimization algorithm to this, for instance simulated annealing. The time required to find the optimum may strongly depend on the types of moves you allow, since you'll often get parts of the image assembled correctly in the wrong place and you can significantly lower the energy barriers between local optima by using moves that shift entire groups of blocks together, rather than just individual blocks.

-
Thank you this is helpful, I will try to implement it. – Listing Sep 3 '11 at 10:59