Kd tree 3d

[phpeter]

I made a photo mosaic script (PHP). This script takes one main picture and changes it to a photo buildup of little pictures (thumbnails). From a distance it looks like the real picture, when you move closer you see it are all little pictures. I take a square of a fixed number of pixels and determine the average color of that square. Then I compare this with my database which contains the average color of a couple thousand of pictures. I determine the color distance with all available images. But to run this script fully it takes a couple of minutes.

The bottleneck is matching the best picture with a part of the main picture. I have been searching online how to reduce this and came a cross “KD Tree.”

So I’m trying to make a K-D Tree, to compare the mean color of pictures. For example: I have to search which thumbnail is closed to the color 255.255.2555. (RGB). But I have some questions.

• Is the KD Tree the best way to store my data? Or are there better solutions which are quicker or easier to code?
• First off all I’m only familiar with PHP in combination with MySQL. Is it possible to store this tree somehow in to my MySQL DB? If not what do you guys recommend
• I presume it is possible to find the 3 closed points by using Nearest Neighbor (NN), but do I really get the points closed to it or do I get some points that are pretty close?
• I've have searched the web but couldn’t find something on how to search in the tree. Does anyone know an article or some other guide on how the search works? Any other useful information about the K-D tree is welcome as well.

Peter