Binary codes play an important role in many computer vision applications. They require less storage space while allowing efficient computations. However, a linear search to find the best matches among binary data creates a bottleneck for large-scale datasets. Among the approximation methods used to solve this problem, the hierarchical clustering tree (HCT) method is a state-of the-art method. However, the HCT performs a hard assignment of each data point to only one cluster, which leads to a quantisation error and degrades the search performance. As a solution to this problem, an algorithm to create hierarchical soft clustering tree (HSCT) by assigning a data point to multiple nearby clusters in the Hamming space is proposed. Through experiments, the HSCT is shown to outperform other existing methods.

References

1. 1)
  - 7. Muja, M., Lowe, D.G.: ‘Scalable nearest neighbor algorithms for high dimensional data’, IEEE Trans. Pattern Anal. Mach. Intell., 2014, 36, (11), pp. 2227–2240 (doi: 10.1109/TPAMI.2014.2321376).
2. 2)
  - 6. Muja, M., Lowe, D.G.: ‘Fast matching of binary features’. Computer and Robot Vision, Toronto, Canada, May 2012, pp. 404–410.
3. 3)
  - 5. Indyk, P., Motwani, R.: ‘Approximate nearest neighbors: towards removing the curse of dimensionality’. ACM Symp. on Theory of Computing, Dallas, TX, USA, May 1998, pp. 604–613.
4. 4)
  - 2. Alahi, A., Ortiz, R., Vandergheynst, P.: ‘FREAK: fast retina keypoint’. IEEE Conf. on Computer Vision and Pattern Recognition, Providence, RI, USA, June 2012, pp. 510–517.
5. 5)
  - 8. Bezdeck, J.C., Ehrlich, R., Full, W.: ‘FCM: The fuzzy c-means clustering algorithm’, Comput. Geosci., 1984, 10, (2), pp. 191–203 (doi: 10.1016/0098-3004(84)90020-7).
6. 6)
  - 11. Muja, M., Lowe, D.G.: ‘Fast approximate nearest neighbors with automatic algorithm configuration’. Int. Conf. on Computer Vision Theory and Application, Lisbon, Portugal, February 2009, pp. 331–340.
7. 7)
  - 4. Yunchao, G., Lazebnik, S., Gordo, A., et al: ‘Iterative quantization: a procrustean approach to learning binary codes for large-scale image retrieval’, IEEE Trans. Pattern Anal. Mach. Intell., 2013, 35, (12), pp. 2916–2929 (doi: 10.1109/TPAMI.2012.193).
8. 8)
  - 1. Leutenegger, S., Chli, M., Siegwart, R.Y.: ‘BRISK: binary robust invariant scalable keypoints’. IEEE Int. Conf. on Computer Vision, Barcelona, Spain, November 2011, pp. 2548–2555.
9. 9)
  - 10. Jegou, H., Douze, M., Schmid, C.: ‘Product quantization for nearest neighbor search’, IEEE Trans. Pattern Anal. Mach. Intell., 2010, 33, (1), pp. 117–128 (doi: 10.1109/TPAMI.2010.57).
10. 10)
  - 3. Heo, J., Lee, Y., He, J., et al: ‘Spherical hashing: binary code embedding with hyperspheres’, IEEE Trans. Pattern Anal. Mach. Intell., 2015, 37, (11), pp. 2304–2316 (doi: 10.1109/TPAMI.2015.2408363).
11. 11)
  - 9. Nister, D., Stewenius, H.: ‘Scalable recognition with a vocabulary tree’. IEEE Conf. on Computer Vision and Pattern Recognition, New York, USA, June 2006, pp. 2161–2168.

Hierarchical soft clustering tree for fast approximate search of binary codes

References

Related content