, :., (Scale-invariant feature transform, SIFT) [2] (Speeded up robust features, SURF) [3],.,, (Principal component analysis-sift, PCA- SIFT) [

Size: px

Start display at page:

Download ", :., (Scale-invariant feature transform, SIFT) [2] (Speeded up robust features, SURF) [3],.,, (Principal component analysis-sift, PCA- SIFT) ["

弱诞敖
7 years ago
Views:

1 40 2 Vol. 40, No ACTA AUTOMATICA SINICA February, ,, ;,,.,.,,.,... DOI,,,,,,,.., 2014, 40(2): /SP.J 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): , 3D.,.. ( ) ( ),,, , Manuscript received May 28, 2013; accepted September 18, 2013 ( ) Supported by National Natural Science Foundation of China ( ) Recommended by Associate Editor ZHOU Jie School of Mechanical Engineering, Nanjing University of Science and Technology, Nanjing ,,, [1].,,,.,,.,.,.,

2 , :., (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].,, ).,.,,,,. D-Brief [16] LDA-Hash [17]. BINBOOST [18],.,.,,.,.,., BRISK FREAK.,, ( ).,, BRIEF,,.,.,. 1, SIFT [2]. SIFT.,, SIFT. PCA-SIFT [4] SIFT,, GLOH [1], SIFT 4 4,, SIFT. DAISY [5],,. SIFT,. SURF [3] Hessian, Haar. MROGH [6]

3 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., ;,,.,

4 258 40,. 1,,, 1 L 1 L 2 = 1 L 2 L 3 (1),,, 2.,. : = Fig % (2) The diagram of sampling-point density,,.,,,., : ;.. 80 % 80 %, 80 %, 78 %. 2.2.,,,.,,.,.,., ;,,,.,... 3 P,,.,,. S 1 = α 1 r α 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 d 2 r 2 2 )/(2r 1 d)), α 2 = arccos((r 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]

5 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 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,,

6 ,.,, 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, , 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,

7 2 : 261 CF RBD 2 b CF RBD 1 a,., ,. 6 : JPEG. 3.2,, ;,,. [1],,. (Recall), (1-precision). 4.2, DAISY [5] FREAK [15] BRISK [13].,. 5 20, 100,.,., Hessian [2] Harris [3],,,. 4, ,,,., Hessian, Harris,..,.,, (CFRBD FREAK BRISK DAISY).,,. AGAST [24]. Ubuntu (32 ) (, 512 MB, Intel Core Duo-2.2 GHz). Graffiti 4, , 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 ( ) (ms) (ms) (ms) (ns) ,... Graffiti ,.,,. 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 ( ) Graffiti-5 ( ) (ms) (ns)

8 262 自动化学报 40 卷

9 2期惠国保等: 基于优化采样模式的紧凑而快速的二进制描述子 (c) 结构图像在视角变化下的匹配结果 (c) Viewpoint change of structured image (d) 纹理图像在视角变化下的匹配结果 (d) Viewpoint change of textured image 263

10 (e) (e) Performance of illumination changes (f) JPEG (f) Performance of JPEG compression Fig. 8 8 Matching effect under various image transformations

11 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): Lowe D G. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 2004, 60(2): Bay H, Ess A, Tuytelaars T, van Gool L. SURF: speeded up robust features. Computer Vision and Image Understanding, 2008, 110(3): 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, II-506 II 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): 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, 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, Jégou H, Douze M, Schmid C. Improving bag-of-features for large scale image search. International Journal of Computer Vision, 2010, 87(3): 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, 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): Lepetit V, Fua P. Keypoint recognition using randomized trees. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(9): 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): 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, 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, 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, Trzcinski T, Lepetit V. Efficient discriminative projections for compact binary descriptors. In: Proceedings of the 12th European Conference on Computer Vision. Firenze, Italy: IEEE, 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): 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, 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, 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

12 (,,,.., 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): (,,. Laplacian., 2011, 19(12): ) 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): (,,,,,.., 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): (,,,.., 2013, 39(6): ) 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, 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): 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.).. 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): (,,,. AdaBoost., 2013, 39(6): ) 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,.. 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.)

2 3. 1,,,.,., CAD,,,. : 1) :, 1,,. ; 2) :,, ; 3) :,; 4) : Fig. 1 Flowchart of generation and application of 3D2digital2building 2 :.. 3 : 1) :,

2 3. 1,,,.,., CAD,,,. : 1) :, 1,,. ; 2) :,, ; 3) :,; 4) : Fig. 1 Flowchart of generation and application of 3D2digital2building 2 :.. 3 : 1) :, 3 1 Vol. 3. 1 2008 2 CAA I Transactions on Intelligent Systems Feb. 2008, (,210093) :.,; 3., 3. :; ; ; ; : TP391 :A :167324785 (2008) 0120001208 A system f or automatic generation of 3D building models