search

brianfromoregon / photomosaic

Automatically exported from code.google.com/p/photomosaic
1 stars 1 forks source link

Implement optimal source image selection algorithm #24

Open GoogleCodeExporter opened 9 years ago

GoogleCodeExporter commented 9 years ago 
I think that the optimal selection algorithm would minimize the sum of the 
errors of each slice.  If that were true, one implementation would be this:

1. If there are no slices left to fill, exit.
2. Fill all slices with their best images, allowing duplicates.
3. Of all the cells that used duplicate images, only keep the one with the 
lowest error, throw the rest out.
4. Go to step 1.

Original issue reported on code.google.com by brianfromoregon on 1 Jun 2010 at 11:30

GoogleCodeExporter commented 9 years ago 
Looks like the Hungarian algorithm is a way to solve this 
(http://en.wikipedia.org/wiki/Hungarian_algorithm)

Original comment by brianfromoregon on 4 Jun 2010 at 2:45

GoogleCodeExporter commented 9 years ago 
I tested out a couple of implementations found here: 
http://timefinder.svn.sourceforge.net/viewvc/timefinder/trunk/timefinder-
algo/src/main/java/de/timefinder/algo/roomassignment/

They don't practically scale well to n=thousands, too slow.  Googling shows a 
few 
papers on monte carlo based approximation algorithms which may be the best bet.

Original comment by brianfromoregon on 5 Jun 2010 at 4:21

GoogleCodeExporter commented 9 years ago 
Another way of stating the problem: given a MxN weighted-edge biclique, find a 
minimal assignment (as in the assignment problem).

I hope there's an approximation solution, maybe using monte-carlo simulations.

Original comment by brianfromoregon on 25 Jun 2010 at 2:07