Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

demonstration

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.

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.