A Dissertation Submitted to Zhejiang University in partial fulfillment of the requirements for the degree of Bachelor of Engineering TITLE Markerless

Size: px

Start display at page:

Download "A Dissertation Submitted to Zhejiang University in partial fulfillment of the requirements for the degree of Bachelor of Engineering TITLE Markerless"

甯娈委贡
7 years ago
Views:

1 ( )

2 A Dissertation Submitted to Zhejiang University in partial fulfillment of the requirements for the degree of Bachelor of Engineering TITLE Markerless Real-Time Camera Tracking Author: Supervisor: Subject: College: Shao Yuanlong Professor Bao Hujun Computer Science and Technology Computer Science and Technology Submitted Date: June, 2007 Zhejiang University Hangzhou, P. R. China May, 2004

Supervisor: Subject: College: Shao Yuanlong Professor Bao Hujun Computer Science and Technology

5 Marker Marker Marker Marker SIFT SSE CPU SSE I

6 Abstract Camera tracking is a fundamental problem in computer vision field, it s applications include special effects in movies, augmented reality, visual scene evaluation or so. According to the usage, camera tracking can be divided into two catalogs, which are special hardware based or computer vision based approaches. Computer vision based methods currently suffers from high computational cost, which makes it only gets good result when calculated off-line, so that it is basically used in accuracy preferred applications. While in the efficiency preferred real-time applications, like augmented reality, people use special hardware to do the tracking, like magnetic equipments, these approaches have a high response rate, while in another aspect, they suffers from flexibility problems due to the complex equipments. Computer vision based approaches, however, are brought in to real-time applications recently, but they use marker to provide clue for camera tracking, which ruined the harmonization of the scene, and also suffers from flexibility problems. There also markerless approaches, mostly suffers from stability and efficiency problems. However, computer vision are preferred in the future. In this article, we proposed a true real-time, computer vision based, markerless approach for camera tracking. First, we described our offline camera tracking technique, it focuses as the quality of camera tracking, which take continuous image sequence as input, and solve the camera parameters from each frame and the world coordinates for feature points. We use this as the preprocess procedure, and match the world coordinates of scene feature points to the image feature points detected from online tracking procedure, so that the camera parameters can be solved in real-time, this profits from the good invariant property of SIFT feature descriptors. Our main contribution in online procedure is to accelerate the SIFT feature extraction and camera parameter solving algorithms. We approximated the algorithm, and reduced computation by changing algorithm parameters, in the precondition of keeping algorithm quality. And we use SSE to accelerate the bottleneck image operations. Also, multi-thread and pipeline approaches are used to take advantage of multiple core computers. Key Words: Camera Tracking, Feature Tracking, Real-time, Augmented Reality, Thread Pool, SSE Instruction set, Pipeline II

Computer vision based methods currently suffers from high computational cost, which makes it only gets good result when calculated off-line, so that it is basically used in accuracy preferred

7 I Abstract II SIFT SIFT SIFT III

1.3................................ 10 3.2 SIFT................................. 11 3.2.1................................ 12 3.2.2 SIFT............................ 14 3.2.3 SIFT...................... 15 16 4.

8 IV

3.5................................ 29 5.4..................................... 30 5.5...................................... 32 33 6.1...................................... 33 6.2...................................... 33 34 37 38 39

9 Marker Scale Space Scale Space Laplacian of Gaussian Scale SIFT Integral Image Best Bin First Package V

............ 14 3.6 SIFT............................. 15 4.1................................... 17 5.1........................... 21 5.2 Integral Image............................... 22 5.

10 VI

11 1.1: [1] 1.2: Marker [2] Marker CAD&CG 1

12 [3] [4, 5] [6, 7] 1.1: Marker Marker Marker [8, 9] Marker Marker Marker

13 3 Marker Marker [10] (ML-Estmiator) orientation (registration) Marker Marker M.L.Yuan KLT [11] Lowe SIFT [12] KLT SIFT SIFT 5 1.3: [12] SIFT LIBRARY

14 [13] [3] SIFT 15 1 SIFT Box filter Gaussian filter 2 SSE SSE cpu

15 2.1 : m ij P i M j (2.1) P i i : P i = K i [R i t i ] = [K i 0] R i 0 t 1 t i (2.2) ( ) ( ) R i 0 t 1 [K i 0] K (f) (u, v) (s) (a)5 2.3 t i K = f s u 0 af v (2.3)

16 : x OX e x e F m i1 jf i1 i 2 m i 2 j = 0 (2.4) 7 RANSAC RANSAC While ITMAX (7 ) F Inlier Inlier F F F 2.3 ( ) ( ) 2.2 P i

17 7 (K i, R i, t i ) ( R i ) [14] 2.2: P i T M j T 1 Let P i = P i T M j = T 1 M j (2.5) m ij P im j m ij K i [R i t i ] M j (2.6) 2.4 P i

1 P i 4 4 15 T M j T 1 Let P i = P i T M j

18 8 2 P i K i [15] P i I 0 0 T 0 P T i = K i [R i t i ] I 0 0 T 0 [R i t i ] T K T i = K i K T i (2.7) K i 2.1 ( [14]) * 2 0 5* * 0 2 4*, 5# # 0 4 2, 3# 2.1: Kruppa * # (f) (s) (u, v) (a) [16] ( ) ( )

1 ( [14]) 5 0 3 0 2 4* 2 0 5* 0 0 1 8* 0 2 4*, 5# 0 0 3

19 SIFT 3.1 (Corner Detector) KLT SIFT KLT SIFT 9

20 KLT Moravec [17, 18] SSD Squared Sum Difference Harris [19] Autocorrelation Function Moravec [20] Moravec SSD Schmid [21] KLT[22, 23, 24] SIFT Scale Invariant Feature Transform 1994 Lindeberg [25] 2003 Lowe [26]

21 11 [27] SIFT 3.1: Moravec Corner ( ) Harris Corner ( ) Scale SIFT Scale SIFT SIFT [26] SIFT SIFT

22 : SIFT ( ) KDTree ( ) RANSAC ( ) SIFT Scale Scale Scale (Image Pyramid) 3.3 Scale Scale Scale Scale SIFT Scale Space ( Scale) Laplacian 3.3 Scale Image Pyramid Scale Space Scale 3.4 Scale Space Scale Blob Scale Blob Scale Space Laplacian ( 3.4 )

23 13 3.3: Scale Space Multi-Scale ( ) SIFT Scale Space ( ) Scale Space Octaves ( ) Octave Octave σ 0 σ : Scale Space ( ) Scale Space Space Scale Scale Space Scale Invariant Scale Scale Laplacian

24 14 3 Laplacian Gaussian Convolution Laplacian of Gaussian 3.5 Laplacian Scale Normalize t 2 2 L 3.5: Laplacian of Gaussian Scale LoG Scale Normalize Gaussian Scale Space 3.1 Scale Normalized Laplacian of Gaussian 3.2 t 2 L = L t (3.1) t 2 2 L = t L t tl ( x, kt) L ( x, t) kt t = const (L ( x, kt) L ( x, t)) (3.2) Scale Space Scale k Scale Normalized Laplacian of Gaussian ( 3.3 ) SIFT 3.6 [28] 3.6

25 15 3.6: SIFT Scale 4 4 ( 2 2 ) = SIFT N k kd-tree [29, 30] 8 3D-Tree SIFT 128D-Tree 128 CPU

26 Track Track 16

27 : / Cube 4.1 Track Track N N RANSAC Track 2.1 x x

28 18 4 X OO X (N-1)/2 4.2 [31] Homography b ij = median k {d (Hu ik, u jk )} (4.1) f ij = 2 (f i f j ) f i + f j (4.2) B ij = nα ijb ij β + f ij (4.3) [31] P 1, P 2 P

29 19 min j d (m ij, K i (R i M j + t i )) 2 (4.4) 4.4 RANSAC P 4.4 (K, R, t) RANSAC

30 5.1 ( ) 5.2 : (1) (2) stateof-the-art : (sec) Step Step 1.1 Gaussian Pyramid 0.4 Step 1.2 Pyramid 0.02 Step 1.3 Gaussian 0.2 Step Step Step Step Step Step 3.1 RANSAC P 0.1 Step 3.2 RANSAC R, t

31 21 5.1: 1.5 Step 1.1 Step 2 5.1: Gaussian Pyramid 3-5 ( ) 25 ( ) : (1) Gaussian Convolution Box Filter Integral Image (2) kdtree Best Bin First (3) (RANSAC) Box Filter Step 1.1 Gaussian Convolution Box Filter Box Filter

32 : Integral Image ( ) Integral Image S ABCD ( ) Gaussian Convolution 3 σ Box Filter Box Filter Integral Image Integral Image 5.2 : Integral Image 5.2 Best Bin First kd-tree Best-Bin-First RANSAC RANSAC (1) (2)

33 23 5.3: Best Bin First RANSAC While Γ (#inlier, #samples) 95% && IT- MAX (7 ) F Inlier Inlier F F F While Γ (p λ inlier m ) Γ = 1 (1 λ p ) m (5.1) SSE 3 4 4

34 24 5 SSE (1) 16 (2) SSE Load Store (3) SSE SSE GPU SSE overhead : Listing 5.1: // Computing Image Gradients for each pixel[x][y] in the pyramid { // Calculate magnitude and direction for that pixel. magnitude = sqrt((pixel[x][y+1] pixel[x][y 1])ˆ2 + (pixel[x+1][y] pixel[ x 1][y])ˆ2); direction = ATan2(pixel[x][y+1] pixel[x][y 1], pixel[x+1][y] pixel[x 1][y]); } ATan2 Listing 5.2: ATan2 // arctan Look Up Table static inline float AtanLookupF32::Value(float y,float x){ float N DOUBLE = ; if ( x > 0.0 ){ if ( y > 0.0 ) return m datan LU[(int)(N DOUBLE y / ( x + y ))]; else return m datan LU[(int)(N DOUBLE ( y) / ( x y ))]; }

35 25 if ( x == 0.0 ){ if ( y > 0 ) return else return } LU PI/2; LU PI/2; } if ( y < 0.0 ) return m datan LU[(int)(N DOUBLE y / ( x + y ))] LU PI; else return m datan LU[(int)(N DOUBLE ( y) / ( x y ))] + LU PI; profiling Magnitude Direction ATan SSE WidthForAllocateMemory = Width (Width - 1) % 4; sqrt SSE Atan sqrt Wild Magic Library FastInvSqrt(x) Listing 5.3: SQRT template <class Real> Real Math<Real>::FastInvSqrt (Real fvalue) { // TO DO. This routine was designed for float. Come up with an // equivalent one for double and specialize the templates for float // and double. float ffvalue = ( float )fvalue; float fhalf = 0.5 f ffvalue; int i = ( int )&ffvalue; i = 0x5f3759df (i >> 1);

36 26 5 } ffvalue = ( float )&i; ffvalue = ffvalue (1.5f fhalf ffvalue ffvalue); return (Real)fFValue; float int 1.0f / FastInvSqrt(x) sqrt(x) SSE 3 SSE sqrt Listing 5.4: SSE SQRT m128 mm sqrt ps( m128 a ); SQRTPS ATan int x,y : Listing 5.5: ATan2 static forceinline float ValueDirect(int y, int x, int idx) { x = x 2 + y + 3; return m datan LU[x][idx]; } x y x,y trick LU PI 4 x,y,idx SSE SSE SSE2 MSDN C++ Language Reference = Compiler Intrinsics max max(x, -x) SSE Intel Compiler

37 27 Listing 5.6: Pow / Sample Usage: double n = 3.0; double s = Pow<2>( n ); // imul instruction used double t = Pow<2>(3.0); // replaced by constant 9.0 / template<int N> class PowAgent { public: template<typename RealT> static forceinline RealT PowN(RealT x) { return PowAgent<N 1>::PowN(x) x; } }; template<> class PowAgent<0> { public: template<typename RealT> static forceinline RealT PowN(RealT x) { return 1; } }; template<int N, typename RealT> forceinline RealT Pow(RealT x) { return PowAgent<N>::PowN(x);

38 28 5 } WorkerItem Listing 5.7: Create k Worker Threads while additional work are to be done { if (Thread i is free) && (WorkerItem j can be started) { Assign WorkItem j to Thread i } else { Wait for some time; } } Listing 5.8: While additional work are to be done { Select all currently startable WorkerItems into Set G

39 29 Create k Worker Threads // Threads can fetch another WorkerItem from Set G when one is done } Wait for Set G to be empty pass 50% Buffer Manager (Frame Buffer) (Result Buffer) Frame Buffer Worker Thread Buffer producer/consumer Listing 5.9: Buffer Manager // Buffer Manager Code. // Product may be Image Frame or Result sembuff = n; semprod = 0; semmutex = 1; // Producer: while(){ produce next product (); Wait(semBuff); Wait(semMutex); put product into buffer queue; Signal(semMutex); Signal(semProd); }

40 30 5 // Consumer: while(){ Wait(semProd); Wait(semMutex); get product from buffer queue; Signal(semMutex); Signal(semBuff); consume product; } n Frame Buffer Consume Image Frame Product Produce Result Buffer SIFT 100 ( ) Pentium D 2.66GHz 2GB 10 8

41 31 (sec) (sec) Step Step 1.1 Gaussian Pyramid Step 1.2 Pyramid Step 1.3 Gaussian Step Step Step Step Step Step 3.1 RANSAC P Step 3.2 RANSAC R, t (sec/frame) : 1.5sec/frame:0.09sec/frame 5.4: ( ) ( ) 5.5: VRML Cube

42 Media Source Input Frame Buffer Camera Tracking Pipeline Manager Tracking Result Buffer Renderer Symbols Control Relationship Logical Flow Data Flow System Design 5.6: Media Source Image Frame Image Frame Image Sequence (for Debug) Camera Capturing (for Release) Media Source Package Feature Extractor Natural Feature Marker Feature Virtual Scene Camera Pos Image Frame Feature Matcher kd-tree Search Marker Match Renderer Camera Pos Solver AugmentedScene (Final Result) Renderer Package Camera Pos Camera Tracking Package 5.7: Package

43 ( ) (25 ) 6.2 Marker Marker SIFT SIFT GPU SIFT 33

44 [1] Xiaobo An Wei Chen Guofeng Zhang, Xueying Qin and Hujun Bao. As-consistentas-possible compositing of virtual objects and video sequences. CASA, [2] Yuanlong Shao Zilong Dong, Guofeng Zhang. Real-time augmented reality using invariant markers [3] 2d3 Ltd. Boujou, [4] Ronald T. Azuma. A survey of augmented reality. Teleoperators and Virtual Environments, pages , [5] Reinhold Behringer Steven Feiner Simon Julier Blair MacIntyre Ronald Azuma, Yohan Baillot. Recent advances in augmented reality [6] Devesh Kumar Bhatnagar. Position trackers for head mounted display systems: A survey [7] Yohan Baillot Jannick P. Rolland and Alexei A. Goon. A survey of tracking technology for virtual environments. In W. Barfield and Lawrence Erlbaum Mahwah N.J. T. Caudell, eds., editors, Fundamentals of Wearable Computers and Augmented Reality, pages , [8] Billinghurst M. Kato, H. Marker tracking and hmd calibration for a video-based augmented reality conferencing system. In International Workshop on Augmented Reality, [9] Kato etc. Artoolkit, [10] Muriel Pressigout Andrew I. Comport, Eric Marchand and Franc?ois Chaumette. Real-time markerless tracking for augmented reality: The virtual visual servoing framework. IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, 12(4): , [11] S.K. Ong M.L. Yuan and A.Y.C. Nee. Registration using natural features for augmented reality systems. IEEE TRANSACTIONS ON VISUALIZATION AND COM- PUTER GRAPHICS, 12(4): ,

45 35 [12] Iryna Gordon and David G. Lowe. Scene modelling, recognition and tracking with invariant image features. In International Symposium on Mixed and Augmented Reality, pages , [13] State Key Lab of CAD&CG of Zhejiang University. Xtrack camera tracking software, [14] R. I. Hartley and A. Zisserman. Multiple View Geometry in Computer Vision. Cambridge University Press, ISBN: , second edition, [15] R. Koch M. Pollefeys and L. Van Gool. Self-calibration and metric reconstruction in spite of varying and unknown internal camera parameters. IJCV, 32(1):7 25, [16] Bill Triggs, Philip McLauchlan, Richard Hartley, and Andrew Fitzgibbon. Bundle adjustment A modern synthesis. In W. Triggs, A. Zisserman, and R. Szeliski, editors, Vision Algorithms: Theory and Practice [17] Hans P. Moravec. Obstacle avoidance and navigation in the real world by a seeing robot rover. Technical report, Robotics Institute, Carnegie Mellon University and doctoral dissertation, Stanford University, September [18] Hans P. Moravec. Rover visual obstacle avoidance. pages International Joint Conference on Artificial Intelligence, August [19] C. Harris and M.J. Stephens. A combined corner and edge detector. page Alvey Vision Conference, [20] Deriche R. Faugeras O. Zhang, Z. and Q.T Luong. A robust technique for matching two uncalibrated images through the recovery of the unknown epipolar geometry. In Artificial Intelligence, pages [21] C. Schmid and R Mohr. Local grayvalue invariants for image retrieval, volume PAMI. [22] Bruce D. Lucas and Takeo Kanade. An iterative image registration technique with an application to stereo vision. pages International Joint Conference on Artificial Intelligence, 1981.

46 36 [23] Carlo Tomasi and Takeo Kanade. Detection and tracking of point features. Technical Report CMU-CS , Carnegie Mellon University, [24] Jianbo Shi and Carlo Tomasi. Good features to track. pages CVPR, [25] T. Lindeberg. Edge detection and ridge detection with automatic scale selection. International Journal of Computer Vision, 30(2):77 116, URL citeseer.ist.psu.edu/lindeberg96edge.html. [26] David G. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 20:91 110, [27] Krystian Mikolajczyk. Detection of local features invariant to affine transformations. [28] Intrator N. Edelman, S. and T Poggio. Complex cells and object recognition [29] Jerome H. Freidman, Jon Louis Bentley, and Raphael Ari Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Softw., 3(3): , ISSN doi: [30] J.S. Beis and D.G. Lowe. Learning indexing functions for 3-d modelbased object recognition. In CVPR94, pages , URL citeseer.ist.psu.edu/beis94learning.html. [31] Marc Pollefeys, Luc Van Gool, Maarten Vergauwen, Frank Verbiest, Kurt Cornelis, Jan Tops, and Reinhard Koch. Visual modeling with a hand-held camera. IJCV, 59 (3): , ISSN

47 CAD&CG SSE GPU SIFT LaTex 37

48 CPU GPU GPU ( ) : ( ) 38

49 ,,,, 15 /.,. ( ) (10%) (20%) (10%) (60%) ( ) 39

(Pattern Recognition) 1 1. CCD

********************************* ********************************* (Pattern Recognition) 1 1. CCD 2. 3. 4. 1 ABSTRACT KeywordsMachine Vision, Real Time Inspection, Image Processing The purpose of this