iccv iccv2013 iccv2013-409 iccv2013-409-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Lixin Fan
Abstract: This paper proposes to learn binary hash codes within a statistical learning framework, in which an upper bound of the probability of Bayes decision errors is derived for different forms of hash functions and a rigorous proof of the convergence of the upper bound is presented. Consequently, minimizing such an upper bound leads to consistent performance improvements of existing hash code learning algorithms, regardless of whether original algorithms are unsupervised or supervised. This paper also illustrates a fast hash coding method that exploits simple binary tests to achieve orders of magnitude improvement in coding speed as compared to projection based methods.
[1] A. Bosch, A. Zisserman, and X. Munoz. Image classification using random forests and ferns. In ICCV, 2007. 2
[2] M. Calonder, V. Lepetit, C. Strecha, and P. Fua. Brief: binary robust independent elementary features. ECCV’ 10, 2010. 1, 2 2622 Table 4. Comparison of mean average precision i.e. mAP (%), for which only Hamming radiuses no great than 3 are considered. The highest rates along each row are in bold font, while the second best underlined. ‡ indicates those exceptional cases in which JSD does not outperform tsh ael original m roewthao rde. iSne eb odlidsc founssti,o wn hiinl eSe thceti sonecso 4n.3d abnesdt 4un.4d. Dataset CIFAR10 (Euclidean) Labelme22K LCenodgteh LSH/JSDSH/JSDBRE/JSDAIpTpQro/aJcShDesKSH/JSDrHALF/JSD 186 2 43. 3869/ 3403. 0 95 1 63. 4789/ 2419. 7591 3 90. 3736/ 4598. 1867 4387. 14 3/ 4567. 456 8740..8566//8700.4.536‡ 1 84. 1029/ 2310. 5 25 3642 186 9703..0736//7968..3632 3299..2051//3412..4758 9979..1282//9969..5360‡ 5478..9079//4688..8047 4370..6522//5798..7691 191.6.548//1241..8311 32 64 7351..7036//6804..2858 180.5.727//2314..0380 22.27 /56.78 41.84/77.21 32.08 /53.89 95.49/95.57 9603..4246//7947..3482 3232..5641//3443..1955 56.23 /64.90 89.94/91.49 69.82/67.92‡ 92.16/95.45 84.96/89.63 98.49/98.42‡ 27.05 /40.67 62.41 /74.39 32 64 10.35/14.85 90.73 /91.06 6.80/15.76 24.24/57.74 5 . 5481/ 86. 124 86.8.5 7/ 161. 8379 96.3.567/ 170. 0741 21.69/23.29 74.19/71.87‡ 25.75/28.16 59.70/78.92 2130..8959//1190.6.949‡ 79.91/74.52‡ 91.69/94.45 8.48/18.57 56.04/91.52 CIFAR100 186 1 . 7494/ 21. 1526 1 . 212 / 21. 2459 12. 97 2/ 31. 4815 13. 1720/ 31. 381 52.6.576//42..7556‡ 1 . 5138/ 21. 1560 (fine) 3642 854..0238//88.71.765 102..1082//64.84.070 5140..2257//1611..3754 3141..7922//1533..0857 4743..8869//4811..0882‡ 382..5409//88.20.260 CIFAR100 (coarse) (CseImFAanRt1i0c) SIFT10K 186 6 . 7021/ 76. 0 86 6231..9009//6894..9272 1197..7623//2313..7969 5 . 8436/ 86. 73 9 31862 12 3 5. 362958/ 132 06. 038694 1 172. 674869/ 12 605. 7549 2 231480. 457321/ 132846. 7 6972 241603. 831983/ 142 57. 2 6316 1 675. 12403 / 12 507. 453054 1 183. 706 79/ 132405. 2 5702 186 105. 7369/ 61.16.315 1 90. 3412/ 16 . 8026‡ 172.0.503/ 1234. 5 94 176.0.46 / 1236. 509 160.2.71 / 120 . 1739 186.8.541/ 1361. 0382 3642 2841. 1568/ 2831. 172 ‡ 9389..6767//9480.1.235‡ 5279..6130//5531.6.753‡ 7355..2519//7436.3.862‡ 4299..1919//3313.8.502‡ 8474. 8518/ 6976. 2905 64 92.94/92.34‡ 30.12/57.83 68.63 /73.81 59.66/69.60 18.04/27.78 30.27 /66.01
[3] Y. Gong and S. Lazebnik. Iterative quantization: A procrustean approach to learning binary codes. CVPR ’ 11, 2011. 1, 5
[4] Y. Gong, S. Lazebnik, A. Gordo, and F. Perronnin. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence, 99: 1, 2012. 1
[5] P. Indyk and R. Motwani. Approximate nearest neighbors: towards
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20] removing the curse of dimensionality. STOC ’98, 1998. 2, 3 H. J ´egou, M. Douze, C. Schmid, and P. P ´erez. Aggregating local descriptors into a compact image representation. In IEEE Transactions on Pattern Analysis and Machine Intelligence. 1 B. Kulis and T. Darrell. Learning to hash with binary reconstructive embeddings. In NIPS, pages 1042–1050. 2009. 1, 2, 5 V. Lepetit, P. Lagger, and P. Fua. Randomized Trees for Real-Time Keypoint Recognition. In CVPR, 2005. 2 S. Leutenegger, M. Chli, and R. Siegwart. Brisk: Binary robust invariant scalable keypoints. In ICCV’11, pages 2548–2555, 2011. 1 X. Li, G. Lin, C. Shen, A. van den Hengel, and A. Dick. Learning hash functions using column generation. In International Conference on Machine Learning (ICML’13), Atlanta, USA, 2013. 2 J. Lin. Divergence measures based on the shannon entropy. IEEE Transactions on Information theory, 37: 145–151, 1991 . 3 W. Liu, J. Wang, R. Ji, Y.-G. Jiang, and S.-F. Chang. Supervised hashing with kernels. In CVPR, 2012. 1, 2, 3, 5 M. Norouzi and D. J. Fleet. Minimal loss hashing for compact binary codes. In ICML, pages 353–360, 2011. 1, 2 M. Norouzi, D. J. Fleet, and R. Salakhutdinov. Hamming distance metric learning. In NIPS, 2012. 1, 2 A. Oliva and A. Torralba. Modeling the shape of the scene: A holistic representation of the spatial envelope. Int. J. Comput. Vision, 42(3):145–175, May 2001. 4 M. O¨zuysal, M. Calonder, V. Lepetit, and P. Fua. Fast keypoint recognition using random ferns. IEEE Trans. Pattern Anal. Mach. Intell., 32(3):448–461, 2010. 1, 2, 7 E. Rublee, V. Rabaud, K. Konolige, and G. Bradski. Orb: An efficient alternative to sift or surf. In ICCV, 2011. 1, 2 T. Sattler, B. Leibe, and L. Kobbelt. Fast image-based localization using direct 2d-to-3d matching. In ICCV, pages 667–674, 2011. 1, 7 C. Strecha, A. M. Bronstein, M. M. Bronstein, and P. Fua. LDAHash: Improved Matching with Smaller Descriptors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(1), 2012. 1 A. Torralba, R. Fergus, and Y. Weiss. Small codes and large image
[21]
[22]
[23]
[24]
[25]
[26] databases for recognition. In CVPR, 2008. 1 T. Trzcinski and V. Lepetit. Efficient Discriminative Projections for Compact Binary Descriptors. In ECCV, 2012. 1, 2 P. A. Viola and M. J. Jones. Rapid object detection using a boosted cascade of simple features. In CVPR (1), pages 511–518, 2001. 2, 6 J. Wang, S. Kumar, and S.-F. Chang. Semi-supervised hashing for scalable image retrieval. In CVPR, 2010. 1, 2, 3 J. Wang, S. Kumar, and S.-F. Chang. Sequential projection learning for hashing with compact codes. In ICML, 2010. 1, 2, 3 J. Wang, J. Wang, N. Yu, and S. Li. Order preserving hashing for approximate nearest neighbor search. In ACM, 2013. 2 Y. Weiss, A. Torralba, and R. Fergus. Spectral hashing. In NIPS, pages 1753–1760, 2008. 1, 2, 5 2623