40 2 Vol. 40, No. 2 2014 2 ACTA AUTOMATICA SINICA February, 2014 1 1 1..,, ;,,.,.,,.,... DOI,,,,,,,.., 2014, 40(2): 255 266 10.3724/SP.J.1004.2014.00255 A Binary Descriptor Based on Both Optimized Sampling Pattern and Image Sub-patches HUI Guo-Bao 1 LI Dong-Bo 1 TONG Yi-Fei 1 Abstract This paper proposes a more robust binary descriptor through further excavating feature information of image patch. Conventional binary descriptors such as binary robust independent elementary features (BRIEF) are not robust to rotation and viewpoint invariance, which is improved from two aspects in this paper. Firstly, an optimized sampling pattern is presented by tuning the density of sampling points and the overlapping size of receptive fields. Secondly, all pixels in the patch are classified according to their intensity order, so that the patch is decomposed into several subpatches. Then, random tests on each sub-patch mapped with the optimized sampling pattern are repeatedly taken, and each test result is concatenated to form a distinct binary string of the sub-patch. The proposed descriptor encodes not only intensity-comparison information but also information about relative relationship of intensities. As a result, results based on experiments of performance evaluation have shown that the proposed binary descriptor outperforms the-state-of-the-art binary descriptors. Key words Keypoint, image patch, binary descriptor, sampling pattern, intensity order, sub-patch Citation Hui Guo-Bao, Li Dong-Bo, Tong Yi-Fei. A binary descriptor based on both optimized sampling pattern and image sub-patches. Acta Automatica Sinica, 2014, 40(2): 255 266, 3D.,.. ( ) ( ),,, 2013-05-28, 2013-09-18 Manuscript received May 28, 2013; accepted September 18, 2013 (61104171) Supported by National Natural Science Foundation of China (61104171) Recommended by Associate Editor ZHOU Jie 1. 210094 1. School of Mechanical Engineering, Nanjing University of Science and Technology, Nanjing 210094...,,, [1].,,,.,,.,.,.,
256 40., :., (Scale-invariant feature transform, SIFT) [2] (Speeded up robust features, SURF) [3],.,, (Principal component analysis-sift, PCA- SIFT) [4] (Gradient location and orientation histogram, GLOH) [1] DAISY [5] (Multi support region of gradient histogram, MROGH) [6].,,.,...,.,, : 1). : a),,, Torralba [7] GIST 1 ; b),, Jégou [8] SIFT ; c),,, Salakhutdinov [9] GIST. 2). [10 11],,,,. (Binary robust independent elementary features, BRIEF) [12].,,,, (Binary robust invariant scalable keypoints, BRISK) [13] ORB [14] (Fast retina keypoint, FREAK) [15].,,. 1 http://gistdescriptor.codeplex.com/ 3).,.,,,,. D-Brief [16] LDA-Hash [17]. BINBOOST [18],.,.,,.,.,., BRISK FREAK.,, ( ).,, BRIEF,,.,.,. 1, SIFT [2]. SIFT.,, SIFT. PCA-SIFT [4] SIFT,, 128 36. GLOH [1], SIFT 4 4,, SIFT. DAISY [5],,. SIFT,. SURF [3] Hessian, Haar. MROGH [6]
2 : 257. (Local intensity order pattern, LIOP) [19] 24. [20],. [21]. [22].,,. [23].,,. BRIEF [12]. BRIEF ( U-BRIEF),. BRIEF,, BRIEF, (O, S)-BRIEF. D-BRIEF [16]. ORB [14],. BRISK [13] AGAST [24],,.,,. FREAK [15],. Boosting [25], BINBOOST [18] Boosting,,. Brown [26]. Cai [27],. Strecha [17]., MROGH [6] LIOP [19]., BRISK FREAK.,,. BRISK FREAK, MROGH LIOP. CFRBD,. 2,.,, [14 15]., BRISK FREAK DAISY. BRISK.,., 60.,. FREAK,. 43,,,,.,. FREAK, ;,. DAISY [5], 25.,,,.,. DAISY SIFT, SIFT,.,.,. 2.1., ;,,.,
258 40,. 1,,, 1 L 1 L 2 = 1 L 2 L 3 (1),,, 2.,. : = Fig. 1 1 100 % (2) The diagram of sampling-point density,,.,,,., : ;.. 80 % 80 %, 80 %, 78 %. 2.2.,,,.,,.,.,., ;,,,.,... 3 P,,.,,. S 1 = α 1 r 1 2 + α 2 r 2 2 r 1 d sin(α 1 ) (3) Fig. 2 2 The relationship between sampling-point density and discriminative power of descriptor 2, 0 %, 100 %. 2.,, r 1 r 2, d, α 1 = arccos((r 2 1 + d 2 r 2 2 )/(2r 1 d)), α 2 = arccos((r 2 2 + d 2 r 2 1 )/(2r 2 d))., S 2 S 3 S 4. P S 1 + S 2 + S 3 + S 4 πr 1 2,., 4.,,, FREAK [15]
2 : 259.,,,, 4, 22 %., ;,. 4 : BRISK [13], FREAK [15] DAISY [5].,,,.,,., FREAK, DAISY SIFT [2],,.. Fig. 5 5 The proposed sampling pattern Fig. 4 Fig. 3 4 3 The diagram of overlapping degree The relationship between overlapping degree and discriminative power of descriptor,, 5, 5., 8,,, 2. FREAK DAISY., FREAK 6, DAISY 8, 8, DAISY.., FREAK DAISY, 3,.,.,,.,,.,., MROGH [6] LIOP [19].,,,.,,,, 6. 6 ;,, 6., 256,,
260 40 0,.,, BRISK [13] FREAK [15].,, BRIEF [12],.,, 7. 7, 5, 5, 5,. 6 Fig. 6 Fig. 7 Sorting pixels by their intensity order 7 The process of building binary descriptor 3.1 P,. 0 255, M I i (0 i < M), : (256/M)i I i < (256/M)(i+1).,,,,,...,,.,,., P i (0 i < M)., [12] : { 1, I(P i, x) < I(P i, y) T (P i ; x, y) := (4) 0,, x, y P i, I(P i, x) P i x., N., N Desc i : Desc i := 2 j 1 T (P i ; x j, y j ) (5) 1 j N, N M P Desc : P Desc := (Desc 1,, Desc M ) (6) ( ). 3.2 CF RBD a 1, 2,,. CF RBD a 1 2,, 2, {CF RBD a 2, CF RBD b 2, CF RBD c 2, }. DIS(CF RBD a 1, CF RBD a 2 ) DIS(CF RBD a 1, CF RBD b 2 ), CF RBD a 2 2 CF RBD a 1. DIS(CF RBD 1 a, CF RBD 2 a ) < T DIS(CF RBD 1 a, CF RBD 2 b ), T CF RBD a 1 CF RBD a 2 a,. CF RBD 1 2, CF RBD a 1 CF RBD a 1, CF RBD a 1 2., CF RBD a a 2 CF RBD 1 2,
2 : 261 CF RBD 2 b CF RBD 1 a,.,. 4 4.1 2.,. 6 : JPEG. 3.2,, ;,,. [1],,. (Recall), (1-precision). 4.2, DAISY [5] FREAK [15] BRISK [13].,. 5 20, 100,.,., Hessian [2] Harris [3],,,. 4, 8. 8. 8,,,., Hessian, Harris,..,.,,. 4.3. 4 (CFRBD FREAK BRISK DAISY).,,. AGAST [24]. Ubuntu-10.04 (32 ) (, 512 MB, Intel Core Duo-2.2 GHz). Graffiti 4, 800 640, PPM. 1. 1, FREAK BRISK, DAISY, DAISY. Table 1 1 (Graffiti-4) The results of time comparisons of detecting and describing all key-points of Graffiti-4 DAISY BRISK FREAK CFRBD ( ) 1 373 1 050 1 036 1 053 (ms) 1 548.3 17.1 18.97 18.22 (ms) 1 486.1 22.06 28.12 18.43 (ms) 3 034.4 39.16 47.09 36.65 (ns) 2 210.1 37.3 45.45 34.81,... Graffiti 2 4. 2. 2,.,,. Table 2 2 (Graffiti-2 Vs. Graffiti-5) The results of real-time performance comparisons of matching key-points in Graffiti-2 to that in Graffiti-5 DAISY BRISK FREAK CFRBD Graffiti-2 ( ) 1 468 1 064 1 017 1 063 Graffiti-5 ( ) 1 984 1 259 1 160 1 302 (ms) 246.16 32.53 34.68 30.41 (ns) 68.44 22.23 24.52 20.12 2 http://www.robots.ox.ac.uk/vgg/research/affine/
262 自 动 化 学 报 40 卷
2期 惠国保等: 基于优化采样模式的紧凑而快速的二进制描述子 (c) 结构图像在视角变化下的匹配结果 (c) Viewpoint change of structured image (d) 纹理图像在视角变化下的匹配结果 (d) Viewpoint change of textured image 263
264 40 (e) (e) Performance of illumination changes (f) JPEG (f) Performance of JPEG compression Fig. 8 8 Matching effect under various image transformations
2 : 265 5,..,,.,,.,.,,.. RGB, RGB. References 1 Mikolajczyk K, Schmid C. A performance evaluation of local descriptors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(10): 1615 1630 2 Lowe D G. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 2004, 60(2): 91 110 3 Bay H, Ess A, Tuytelaars T, van Gool L. SURF: speeded up robust features. Computer Vision and Image Understanding, 2008, 110(3): 346 359 4 Ke Y, Sukthankar R. PCA-SIFT: a more distinctive representation for local image descriptors. In: Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington, D. C., USA: IEEE, 2004. II-506 II-513 5 Tola E, Lepetit V, Fua P. Daisy: an efficient dense descriptor applied to wide-baseline stereo. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(5): 815 830 6 Fan B, Wu F C, Hu Z Y. Aggregating gradient distributions into intensity orders: a novel local image descriptor. In: Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition. Rhode Island, Providence, USA: IEEE, 2011. 2377 2384 7 Torralba A, Fergus R, Weiss Y. Small codes and large image databases for recognition. In: Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition. Anchorage, Alaska, USA: IEEE, 2008. 1 8 8 Jégou H, Douze M, Schmid C. Improving bag-of-features for large scale image search. International Journal of Computer Vision, 2010, 87(3): 316 336 9 Salakhutdinov R, Hinton G. Learning a nonlinear embedding by preserving class neighbourhood structure. In: Proceedings of the 2007 International Conference on Artificial Intelligence and Statistics. Monte Carlo Resort, Las Vegas, Nevada, USA: IEEE, 2007. 412 419 10 Ozuysal M, Calonder M, Lepetit V, Fua P. Fast keypoint recognition using random ferns. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(3): 448 461 11 Lepetit V, Fua P. Keypoint recognition using randomized trees. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(9): 1465 1479 12 Calonder M, Lepetit V, Ozuysal M, Trzcinski T, Strecha C, Fua P. BRIEF: computing a local binary descriptor very fast. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7): 1281 1298 13 Leutenegger S, Chli M, Siegwart R. BRISK: binary robust invariant scalable keypoints. In: Proceedings of the 2011 International Conference on Computer Vision. Barcelona, Spain: IEEE, 2011. 2548 2555 14 Rublee E, Rabaud V, Konolidge K, Bradski G. ORB: an efficient alternative to SIFT or SURF. In: Proceedings of the 2011 IEEE International Conference on Computer Vision. Barcelona, Spain: IEEE, 2011. 2564 2571 15 Alahi A, Ortiz R, Vandergheynst P. FREAK: fast retina keypoint. In: Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition. Rhode Island, Providence, USA: IEEE, 2012. 2069 2076 16 Trzcinski T, Lepetit V. Efficient discriminative projections for compact binary descriptors. In: Proceedings of the 12th European Conference on Computer Vision. Firenze, Italy: IEEE, 2012. 228 242 17 Strecha C, Bronstein A, Bronstein M, Fua P. LDAHash: improved matching with smaller descriptors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(1): 66 78 18 Trzcinski T, Christoudias M, Fua P, Lepetit V. Boosting binary keypoint descriptors. In: Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition. Washington, D. C., USA: IEEE, 2013. 2874 2881 19 Wang Z H, Fan B, Wu F C. Local intensity order pattern for feature description. In: Proceedings of the 2011 IEEE International Conference on Computer Vision. Barcelona, Spain: IEEE, 2011. 603 610 20 Liu Ping-Ping, Zhao Hong-Wei, Zang Xue-Bai, Dai Jin-Bo. A fast local feature description algorithm. Acta Automatica Sinica, 2010, 36(1): 40 45
266 40 (,,,.., 2010, 36(1): 40 45) 21 Tang Yong-He, Lu Huan-Zhang, Hu Mou-Fa. Local feature description algorithm based on Laplacian. Optics and Precision Engineering, 2011, 19(12): 2999 3006 (,,. Laplacian., 2011, 19(12): 2999 3006) 22 Ge Juan, Cao Wei-Guo, Zhou Wei, Gong Ming, Liu Liu, Li Hua. A local feature descriptor under color affine transformation. Journal of Computer-Aided Design & Computer Graphics, 2013, 25(1): 26 33 (,,,,,.., 2013, 25(1): 26 33) 23 Song Ke-Chen, Yan Yun-Hui, Chen Wen-Hui, Zhang Xu. Research and perspective on local binary pattern. Acta Automatica Sinica, 2013, 39(6): 730 744 (,,,.., 2013, 39(6): 730 744) 24 Mair E, Hager G D, Burschka D, Suppa M, Hirzinger G. Adaptive and generic corner detection based on the accelerated segment test. In: Proceedings of the 11th European Conference on Computer Vision. Berlin, Heidelberg: Springer-Verlag, 2010. 183 196 27 Cai H P, Mikolajczyk K, Matas J. Learning linear discriminant projections for dimensionality reduction of image descriptors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(2): 338 352... E-mail: huiguobao@163.com (HUI Guo-Bao Ph. D. candidate at the School of Mechanical Engineering, Nanjing University of Science and Technology. His research interest covers image registration and pattern recognition. Corresponding author of this paper.).. E-mail: db calla@yahoo.com.cn (LI Dong-Bo Professor at the School of Mechanical Engineering, Nanjing University of Science and Technology. His main research interest is advanced manufacture technology.) 25 Cao Ying, Miao Qi-Guang, Liu Jia-Chen, Gao Lin. Advance and prospects of AdaBoost algorithm. Acta Automatica Sinica, 2013, 39(6): 745 758 (,,,. AdaBoost., 2013, 39(6): 745 758) 26 Brown M, Hua G, Winder S. Discriminative learning of local image descriptors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(1): 43 57,.. E-mail: tyf51129@yahoo.com.cn (TONG Yi-Fei Ph.D., associate professor at the School of Mechanical Engineering, Nanjing University of Science and Technology. His main research interest is grid manufacture technology.)