Just after the 0.1 release, I’ve worked to add some few tricks and fix a few bugs (see QtMosaic on Github). The most important change is a better image search.
The Antipole Tree
An antipole tree is a binary search tree that is constructed on antipole pairs. An antipole pair is composed of the furthest points in a set. When constructing the tree, one starts with the full set of images/thumbnails, then recursively, an antipole pair is chosen from the (sub)set (figure 1) and two new clusters are created, images are aggregated to the nearest image of the pair (figure 2). When the subset is small enough, the recursion stops.
The search uses a distance-sorted list. When a leaf node is visited, one looks for the nearest image and stores the result. When an internal node is visited, its children will be added to the sorted list, and the distance will be the distance to the center of the cluster minus the radius (figure 3). This way, if the current best is nearer to the reference than the nearest cluster, no nearest image will be found. It’s a usual distance search in a binary tree.
Result
Of course, building the tree is costly. Although it can be parallelized, it is still slow. The upper side is that using a tree for the search is O(log(n)) instead of the usual O(n). It is actually more efficient for mosaic databases with several thousands of images or more. The result is of course exactly the same as with the linear search.
There are some differences between the original publication (see the reference) and the current code. In the reference, the antipole pair has a special status, as the center of the clusters and they are not tested with the rest of the subset in a leaf node. So in the original code, each tested cluster tests at least one image with the reference, whereas only leaf nodes give the closest images search in my case. The difference is that the center of each cluster will be the real center of the cluster, meaning that the minimum distance will be more close to the reality, and I hope that this will translate into speed-up. The other addition is that the visiting code is also simpler, which is better for maintenance.
Conclusion
This tool has now a logarithmic image search. It should be faster than linear search for huge mosaic databases. Also, the final photomosaic was enhanced by changing the result mosaic mean to the original image mosaic.
Reference : Antipole Tree Indexing to Support Range Search and K-Nearest Neighbor Search in Metric Spaces
Last couple days I have made a photomosaic. I kept is pretty basic. Just comparing the mean colors in linear search. I want to speed up the process and stumbled up on the antipole tree.
But I don’t really understand it.
I see a set of 12 points. What are these points??
I make a 3×3 raster over my pictures and calculate the mean color of all 9 squares, That gives me a vector out of 27 values (9 x RGB). Now I should find the vectors with the biggest distance? So I calculate all distances between the vectors?
How are the new 2 clusters made?
Hi Peter,
I had to refresh my memory a little bit, but here are some hints.
– I split the original image by chunks of 16×12 pixels. These chunks are rescaled to 3×3.
– I search with an antipole tree all thumbnails in my original databse that are close to this 3×3 image (so a 27-dimension vector)
– I recreate a new image (potentially scaled) with these new best images for each chunk.
In my images, the 12 points represent 12 thumbnails in my 27-dimension space of thumbnails where I’m looking for the best thumbnail for a new image. Of course, you will have far more than just 12 points, several thousands if you can.
A new cluster is made by selecting an antipole pair, two points that are far enough one from the other. Then, the two new clusters are created around each point.
The actual heuristics are described in the reference I put at the end of the post. You will find all relevant implementation details that I’ve used. They did a good job in explaining what an antipole tree is!