A different course today: algorithmically solving puzzles. The reading is here: http://chenlab.ece.cornell.edu/people/Andy/publications/Andy_files/Gallagher_cvpr2012_puzzleAssembly.pdf
Some of the proposed applications include piecing together shredded evidence or archeological artifacts. I'm not sure those applications are of particular interest to me, but the fundamental problem is still interesting.
The proposed solutions here are to determine a gradient across the edges of pieces, rather than the absolute color as former solutions had. It presents a greedy solution, which means that it optimizes the local areas rather than optimizing the whole puzzle, in the interest of processing power.
The conclusion I have reached from this paper is that: I need to learn a heck of a lot more about this. Check back in a few days; I'll be going through some of the references and trying to determine what the models actually are. It's an interesting read anyway even if you don't know all the nitty-gritty details of how they solve these things, and I do recommend it.
My first thought (with admittedly very little knowledge of how these things actually get solved) is: is there a way to organize the puzzle first so that you don't have to locally optimize as much, and would that be worth the extra processing power? I expect that with a large enough puzzle it could eventually be. What I'm thinking is assign a gradient value based on the pixels, inserted into a binary tree, or something of that nature. Not sure. I'll follow up here when I've got a clearer mental idea.
No comments:
Post a Comment