January 17th 2012
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.
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.
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.
2 Comments »