(MIRU2010) 2010 7 Geometric Context Randomized Trees 487-8501 1200 E-mail: {fukuta,ky}@vision.cs.chubu.ac.jp, hf@cs.chubu.ac.jp Geometric Context Randomized Trees 10 3, Geometric Context, Abstract Image Based Localization with Randomized Trees Using Geometric Context Takaaki FUKUTA, Katsuyoshi YAMAUCHI, and Hironobu FUJIYOSHI Dept. of Computer Science, Chubu Univ. 1200, Matsumoto, Kasugai, Aichi, 487-8501 Japan E-mail: {fukuta,ky}@vision.cs.chubu.ac.jp, hf@cs.chubu.ac.jp This paper proposes an algorithm for classifying image camera positions with high speed. Conventional camera position classification algorithms classify camera positions by matching feature points against a reference image or using template matching results. The drawbacks of these conventional algorithms are high processing costs for the processes through classification, and variable classification precision due to the effect of changing seasons or weather on view transformations. The proposed algorithm classifies camera positions by using feature values that employ a geometric context not easily affected by weather changes, and the Randomized Trees statistical learning algorithm. In comparison to a conventional algorithm based on matching results, the proposed algorithm provides the same precision while increasing speed by a factor of 10 3. Key words Image Based Localization, Geometric Context, Randomized Trees 1. GPS GPS GPS [8] GPS SIFT [10] [4] [5] [12] [13] [16] Nearest Neighbor IM2GPS [3] Flickr [9] IS2-47:1085
1 1 Nearest Neighbor Geometric Context [11] Randomized Trees [1] 2. 3. 4. 5. 2. Cipora [13] Bag of Features [8] SIFT [5] ICCV 05 Where am I? Zhang SIFT [16] [6] SURF [17] [4] [12] 2 [13] Hays IM2GPS [3] Flickr (1)Tiny Images, (2), (3)Texton, (4)Line Features, (5) Gist, (6)Geometric Context [11] Nearest Neighbor Nearest Neighbor 3. Geometric Context Randomized Trees 2 Geometric Context [2] Geometric Context Randomized Trees 3. 1 Geometric Context Hoiem Geometric Context(GC) (16 ) (15 ) (8 ) (4 ) (35 ) 73 IS2-47:1086
2 GC 3 Geometric Context AdaBoost (ground) (vertical) (sky) ( 3) 45 90 135 Felzenswalb [18] super pixel (1) AdaBoost n f f m (x 1, x 2 ) = log P(y 1 = y 2, x 1i x 2i ) P(y 1 = y 2, x 1i x 2i ) i (1) x i, x 2 super pixel y 1, y 2 n f 5 7 C n h C(y i = e x) = P(y j = e x, h ji )P(h ji x) (2) j y e x n h h ji AdaBoost j super pixel 4 2 GC (b) RGB 11 R 1 2 GC (c)(d)(e) GC 4 GC 3. 2 GC IS2-47:1087
5 GC [3] GC GC 7 2 5 x y B = {b 45, 90, 135,,,, }, r p x,y,b GC GC S x,y,b,r = x+r y+r j=x r i=y r p i,j,b (3) S [2] f = S x,y,r,b (4) f sum = S x1,y 1,r 1,b 1 + S x2,y 2,r 2,b 2 (5) f diff = S x1,y 1,r 1,b 1 S x2,y 2,r 2,b 2 (6) f abs = S x1,y 1,r 1,b 1 S x2,y 2,r 2,b 2 (7) f b S x,y,b,r f sum,f diff,f abs b 1, b 2 S x1,y 1,b 1,r 1 S x2,y 2,b 2,r 2 Randomized Trees Randomized Trees [2] [7] 3. 3. 1 6 Randomized Trees( P (c l)) Randomized Trees ( 6) Randomized Trees ( ) I I = I I n, I l,i r (8) (9) I l = {i I n f(v i ) < t} (8) I r = I n \ I l (9) 3. 3 Randomized Trees Randomized Trees Randomized Trees Randomized Trees Randomized Trees Randomized Trees 2 f(v i ) t f(v i ) t (10) (Infomation gain) E E = I l I n E(I l) I r I n E(I r) (10) E(I) E(I) = n i=1 P i log 2 P i, P i I n IS2-47:1088
(10) l I n P (c l) 3. 3. 2 Randomized Trees l P (c l) P (c L) = 1 T T P t (c l t ) (11) t=1 T L = (l 1,..., l T ) c C i = arg max c i P (c i L) (12) (12) C i 4. l(l = 1,..., L) d(d = 1,..., D) X l d 2 1 1 1 [4] 2 4. 1 1 GPS L = 8 D = 4 2010 2 25 800 l d 11 32 1 20 2 298 7(a) GPS L = 19 D = 60 2 1 1 60 15 1 4 L = 19 D = 4 7(b) 4. 2 [3] 7 SIFT 2 l d 640 425 r 50 Randomized Trees 1 1 Randomized Trees 25 7 400 5 20% 1 2 r 4 5 7 1 4. 3 4. 3. 1 1 8 8 IM2GPS SIFT SIFT 1 IS2-47:1089
7 8 1 IM2GPS 1 IM2GPS Texton Line Features 3 GC 2 9 2 2 SIFT IM2GPS SIFT 1 SIFT IM2GPS 9 2 GC IM2GPS 4. 3. 2 GC r r 10 50 50 5 10 r r r r 4. 3. 3 5 7 IS2-47:1090
l = 7, d = 1 2 10 r 11 11 f f diff f abs 4 4. 3. 4 2 SIFT SIFT IM2GPS 10 3 Randomized Trees 2 [ms] 0.6 IM2GPS 6.3 10 2 SIFT 7.5 10 3 4. 3. 5 13 l = 6, d = 1 l = 5, d = 2 4. 4 Randomized Trees 12 GC 12 ( 1 ) ( 11 ) 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 1 2 3 4 5 6 7 8 9 10 11 12 5. Geometric Context Randomized Trees 10 3 Geometric Context Randomized Trees Gist [19] Randomized Trees [15] [3] 4. IS2-47:1091
13 [1] L. Breiman, Random forests, Machine learning, Springer, 2001, 45, 5-32 [2] J. Shotton, M. Johnson and R. Cipolla. Semantic Texton Forests for Image Categorization and Segmentation. In Proc. CVPR, pp. 1.8, 2008. [3] James Hays and Alexei A. Efros IM2GPS:estimating geographic information from a single image, In Proc. CVPR, pp.1-8, 2008. [4], 2009,212,pp31-36 [5] SIFT 2009,109(306),pp.127-132 [6], 14 (SSII09) IN1-10,Jun,2008 [7] Lepetit, V., Fua, P. Keypoint Recognition Using Randomized Trees IEEE Trans. Pattern Anal. Mach. Intell., IEEE Computer Society, 2006, 28, 1465-1479 [8] Csurka, G., Dance, C.R., Fan, L., Willamowski, J. and Bray, C., Visual categorization with bags of keypoints, ECCV International Workshop on Statistical Learning in Computer Vision (2004). [9] YAHOO. Flickr. http://www.flickr.com/. [10] D. Lowe, Distinctive image features from scaleinvariant keypoints, Int. Journal of Computer Vision, 60(2), pp. 91-110, 2004. [11] D. Hoiem, A. A. Efros and M. Hebert, Geometric context from a single image, In Proc. ICCV, 1, pp. 654-661 (2005). [12],, Vol.13 No.2 2008. [13] R. Cipolla, D. Robertson and B. Tordoff, Image- Based Localization, In Proc. VSMM, pp. 22-29, 2004. [14] R.Szeliski. Where am I? :ICCV2005 Computer Vision Contest. http://research.microsoft.com/iccv2005/contest/. [15] Osman Hassab Elgawi, Online random forests based on CorrFS and CorrBE, CVPR Workshops, 2008, pp.1-7, 2008 [16] W. Zhang, J. Kosecka, Image Based Localization in Urban Environments, In Proc. 3DPVT,33 40, 2006 [17] H. Bay, T. Tuytelaars, and L. V. Gool, SURF: Speeded up robust features, In Proc.ECCV.,2006 [18] P.Felzenswalb and D. Huttenlockher: Efficient Graphbased Image Segmentation. Int. Journal of Computer Vision. Vol.59 No2, pp. 167-181 (2004). [19] A. Oliva and A. Torralba. Building the gist of a scean: The role of global image features in recognition, In Visual Perception, Progress in Brain Research, Vol.155, 2006. IS2-47:1092