Photo mosaic, datastructure, process speed up?

Hello,

Last couple days I have made a photomosaic web application. I kept is pretty basic. I have a DB with pictures and their mean colors. I divide my main picture in to a set number of squares. I’ll calculate the mean of these squares and compare them to my DB, the closest match will be placed on this square.

II want to improve this process.

I’m not comparing with only the mean of the square but I’m going to dive it in to 3 x 3 so my vector changes from 3 to 27 dimensions.
Also I trying to figure out how to speed up the process. Now I’m comparing all of the vectors with a linear search. What kind of data structure would be suited for my problem?

Let’s say the number of pictures in my DB is always between 1000 & 2000. And I want to find the 15 closest matches.

data machine-learning

asked Dec 12 '12 at 05:31

phpeter
1●1●2●2

edited Dec 12 '12 at 06:42

One Answer:

oldest newest most voted

You should look at (approximate) nearest neghbour search algorithms. There are 2 main types of appraches: locality sensitive hashing and various kinds of metric trees (M-tree, KD-ree, spill tree, ball tree, ...). Apart from the links from the wikipedia page, there are implementations for python in scikit & for R on CRAN. However, if you only have <2000 vectors to search through in 27 dimesions, then linear search may be competitive as long as you precompute the 27dim vectors for the images.

answered Dec 12 '12 at 11:07

Daniel Mahler
1226●3●13●22

Subscription:

Once you sign in you will be able to subscribe for any updates here

Tags:

machine-learning ×391
data ×53

Asked: Dec 12 '12 at 05:31

Seen: 901 times

Last updated: Dec 12 '12 at 11:07

Photo mosaic, datastructure, process speed up?

Subscription:

Related questions