MASTER'S THESIS Hardware Accelerated Particle Filter for Lane Detection and Tracking in OpenCL Nikhil Madduri 2014 Master of Science (120 credits) Space Engineering - Space Master Luleå University of Technology Department of Computer Science, Electrical and Space Engineering Hardware Accelerated Particle Filter for Lane Detection and Tracking in OpenCL Thesis submitted in partial fulfilment of the requirements for the degree of Master of Science in Space Science and Technology on 28th Jan, 2014 Author Nikhil Madduri Advisor Dr. Sergio Montenegro Professor and Chairperson Chair VIII, Department of Informatics Julius-Maximilians-Universit¨at Wu¨rzburg Examiner Supervisor Dr. Jana Mendrok Sebastian Klose Assistant Professor Research Associate Division of Space Technology Department of Informatics Lule˚a University of Technology Technische Universit¨at Mu¨nchen Declaration of Authorship I, Nikhil Madduri, declare that this thesis titled, ’Hardware Accelerated Particle Filter for Lane Detection and Tracking in OpenCL. ’ and the work presented in it are my own. I confirm that: This work was done wholly or mainly while in candidature for a research (cid:4) degree at this University. Where any part of this thesis has previously been submitted for a degree or (cid:4) any other qualification at this University or any other institution, this has been clearly stated. Where I have consulted the published work of others, this is always clearly (cid:4) attributed. Where I have quoted from the work of others, the source is always given. (cid:4) With the exception of such quotations, this thesis is entirely my own work. I have acknowledged all main sources of help. (cid:4) Where the thesis is based on work done by myself jointly with others, I have (cid:4) made clear exactly what was done by others and what I have contributed myself. Signed: Date: i “There are no passengers on Spaceship Earth. We are all crew.” Marshall McLuhan, 1964 ¨ JULIUS-MAXIMILIANS UNIVERSITY OF WURZBURG Abstract Faculty of Robotics and Telematics Department of Computer Science Master of Science in Space Science and Technology Hardware Accelerated Particle Filter for Lane Detection and Tracking in OpenCL. by Nikhil Madduri A road lane detection and tracking algorithm is developed, especially tailored to run on high-performance heterogeneous hardware like GPUs and FPGAs in au- tonomous road vehicles. The algorithm was initially developed in C/C++ and was ported to OpenCL which supports computation on heterogeneous hardware. A novel road lane detection algorithm is proposed using random sampling of par- ticles modeled as straight lines. Weights are assigned to these particles based on their location in the gradient image. To improve the computation efficiency of the lane detection algorithm, lane tracking is introduced in the form of a Particle Filter. Creation of the particles in lane detection step and prediction, measure- ment updates in lane tracking step are computed parellelly on GPU/FPGA using OpenCL code, while the rest of the code runs on a host CPU. The software was tested on two GPUs - NVIDIA GeForce GTX 660 Ti & NVIDIA GeForce GTX 285 and an FPGA - Altera Stratix-V, which gave a computational frame rate of up to 104 Hz, 79 Hz and 27 Hz respectively. The code was tested on video streams from five different datasets with different scenarios of varying lighting conditions on the road, strong shadows and the presence of light to moderate traffic and was found to be robust in all the situations for detecting a single lane. Acknowledgements IwouldliketothankSebastianKlose(DepartmentofInformatics,Technische Universita¨t Mu¨nchen (TUM)) for supervising my thesis, giving invaluable sugges- tions at every phase and for his incredible support. I would like to thank Dr. Sergio Montenegro (Department of Informatics, Julius-Maximilians-Universit¨at Wu¨rzburg) for accepting my thesis proposal and being supportive of my work as the thesis advisor. I would like to sincerely thank Dr. Jana Mendrok (Lule˚a University of Technology, Sweden) for carefully going through the entire thesis and suggesting numerous modifications that only made my thesis more elegant. I would like to thank Dr. Kai Huang and Hardik Shah (Department of Informatics, TUM) for offering me this interesting thesis work in the first place. ImustthanktheEuropeanCommissionforgrantingmetheErasmus-Mundus scholarship without which this dream of pursuing Master’s would never have come true. I would like to thank Dr. Victoria Barabash (Department of Computer Sci- ence, Electrical and Space Engineering, Lule˚a University of Technology, Sweden) and the SpaceMaster consortium for organizing such a very useful program in the field of Space Science and Technology. I thank my mom and dad for their incredible love and support without which I would not have been able to make it all the way from India to pursue Master’s in Europe. iv Contents Declaration of Authorship i Abstract iii Acknowledgements iv Contents v List of Figures vii List of Tables x Abbreviations xii 1 Introduction 14 1.1 Motivation and Purpose . . . . . . . . . . . . . . . . . . . . . . . . 14 1.1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . 14 1.1.2 Recommended Solution . . . . . . . . . . . . . . . . . . . . . 15 1.1.3 List of Contributions . . . . . . . . . . . . . . . . . . . . . . 16 1.2 The Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . 17 2 Background 18 2.1 Lane Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.1 Selection of the Region of Interest . . . . . . . . . . . . . . . 19 2.1.2 Correction for the Perspective Effect . . . . . . . . . . . . . 20 2.1.3 Gray-Scaling, Thresholding and Edge Detection . . . . . . . 20 2.1.4 Line Fitting . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Lane Tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.0.1 Particle Filter . . . . . . . . . . . . . . . . . . . . . 25 2.3 High Performance Computing and OpenCL . . . . . . . . . . . . . 26 2.3.1 Programming Models for High Performance Computing . . . 28 2.3.2 Open Computing Language (OpenCL) . . . . . . . . . . . . 30 v Contents vi 2.3.2.1 Conceptual Foundations of OpenCL . . . . . . . . 30 2.3.2.2 Some Advanced Features in OpenCL . . . . . . . . 37 3 Related Work 40 3.1 Lane Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.2 Lane Tracking Methods . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.2.1 Kalman Filter . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.2.2 Particle Filter . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4 Method and Implementation 47 4.1 Developing lane detection and tracking system for CPU . . . . . . . 47 4.1.1 Preprocessing the Image . . . . . . . . . . . . . . . . . . . . 47 4.1.2 Lane Detection . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.1.3 Lane Tracking . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.1.3.1 Particle Filter for Tracking a Robot in 2D . . . . . 53 4.1.3.2 Particle Filter for Tracking Road-Lane Markings . 56 4.2 Parallelizing the Algorithm for OpenCL . . . . . . . . . . . . . . . . 58 4.2.1 OpenCL Software Implementation . . . . . . . . . . . . . . . 58 4.2.2 Hardware Architecture of OpenCL Devices Used . . . . . . . 61 4.2.2.1 GPU Specifications . . . . . . . . . . . . . . . . . . 61 4.2.2.2 FPGA Specifications . . . . . . . . . . . . . . . . . 63 5 Results 65 5.1 Lane Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.2 Particle Filter for Tracking a Robot in 2D . . . . . . . . . . . . . 69 5.3 Particle Filter for Tracking Road-Lane Markings . . . . . . . . . . 71 5.3.1 TUM Night Dataset . . . . . . . . . . . . . . . . . . . . . . 73 5.3.2 TUM Day Dataset . . . . . . . . . . . . . . . . . . . . . . . 78 5.3.3 Caltech Cordova1 Dataset . . . . . . . . . . . . . . . . . . . 78 5.3.4 Caltech Cordova2 Dataset . . . . . . . . . . . . . . . . . . . 80 5.3.5 Caltech Washington Dataset . . . . . . . . . . . . . . . . . . 80 5.4 Performance of the OpenCL Implementation on Heterogeneous Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6 Conclusion 90 A Lane Markings at Intersections 92 Bibliography 93 List of Figures 2.1 Difference between least squares & total least squares methods. . . . 22 2.2 Mapping from x−y plane to r−θ plane. . . . . . . . . . . . . . . 23 2.3 Lines passing through points in x − y plane represented as curves in r−θ plane. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.4 Heterogeneous hardware. . . . . . . . . . . . . . . . . . . . . . . . . 30 2.5 OpenCL Platform Model. . . . . . . . . . . . . . . . . . . . . . . . 32 2.6 OpenCL host and devices. . . . . . . . . . . . . . . . . . . . . . . . 33 2.7 NDRange Indices of work items. . . . . . . . . . . . . . . . . . . . . 33 2.8 NDRange for 1D, 2D and 3D. . . . . . . . . . . . . . . . . . . . . . 34 2.9 OpenCL memory model. . . . . . . . . . . . . . . . . . . . . . . . . 35 4.1 Lane Detection and Tracking Schematic . . . . . . . . . . . . . . . 48 4.2 ROI selection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.3 Edge detection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.4 Lane Detection Schematic . . . . . . . . . . . . . . . . . . . . . . . 50 4.5 Line Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.6 Before introducing distance criteria. . . . . . . . . . . . . . . . . . . 52 4.7 After introducing distance criteria. . . . . . . . . . . . . . . . . . . 52 4.8 Lane Tracking Schematic . . . . . . . . . . . . . . . . . . . . . . . . 53 4.9 The figures above depict how the particle filter is initialized with sample particles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 a Robot in an empty workspace of size 100x100. . . . . . . . . 54 b Robot in the workspace populated with particles. . . . . . . 54 4.10 Good lines and the best lines. . . . . . . . . . . . . . . . . . . . . . 57 a Original Image . . . . . . . . . . . . . . . . . . . . . . . . . 57 b Particle Filter in action. . . . . . . . . . . . . . . . . . . . . 57 4.11 Lane Detection and Tracking using OpenCL . . . . . . . . . . . . . 59 4.12 Schematic for OpenCL Execution on GPUs . . . . . . . . . . . . . . 60 4.13 Schematic for OpenCL Execution on FPGA . . . . . . . . . . . . . 61 5.1 Test conditions given in Table 5.1. . . . . . . . . . . . . . . . . . . . 66 a Original image. . . . . . . . . . . . . . . . . . . . . . . . . . 66 b After lane detection. . . . . . . . . . . . . . . . . . . . . . . 66 5.2 Test conditions given in Table 5.1. . . . . . . . . . . . . . . . . . . . 67 a Original image. . . . . . . . . . . . . . . . . . . . . . . . . . 67 b After lane detection. . . . . . . . . . . . . . . . . . . . . . . 67 vii List of Figures viii 5.3 Test conditions given in Table 5.1. . . . . . . . . . . . . . . . . . . . 67 a Original image. . . . . . . . . . . . . . . . . . . . . . . . . . 67 b After lane detection. . . . . . . . . . . . . . . . . . . . . . . 67 5.4 Test conditions given in Table 5.1. . . . . . . . . . . . . . . . . . . . 68 a Original image. . . . . . . . . . . . . . . . . . . . . . . . . . 68 b After lane detection. . . . . . . . . . . . . . . . . . . . . . . 68 5.5 Test conditions given in Table 5.1. . . . . . . . . . . . . . . . . . . . 69 a Original image. . . . . . . . . . . . . . . . . . . . . . . . . . 69 b After lane detection. . . . . . . . . . . . . . . . . . . . . . . 69 5.6 Particles after re-sampling phase, for iteration 4. . . . . . . . . . . . 70 5.7 Particle-weight distribution for iteration-4. . . . . . . . . . . . . . . 71 5.8 Robot and particles after measurement update. . . . . . . . . . . . 72 5.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 a Original Image. . . . . . . . . . . . . . . . . . . . . . . . . . 75 b TUM Night - Best and Good Lines . . . . . . . . . . . . . . 75 c After the lane tracking step shown in Figure 5.9b, post- processing is done to introduce a horizontal search windows (orange lines) at a few discrete points along the best lines (red lines). Once a certain gradient is encountered along these search windows, the pixels are colored blue. This step increases the accuracy in locating the actual lane markings. . 75 5.10 A few snapshots from the results for TUM Night Dataset. Fig- ures in the left column are the original images while in the right are the lane-detected images. The blue colored markings are the lanes as detected by our algorithm. . . . . . . . . . . . . . . . . . . . . . 76 5.13 Likelihood Vs Frame Number . . . . . . . . . . . . . . . . . . . . . 78 5.14 A few snapshots from the results for TUM Day Dataset. Figures in the left column are the original images while in the right are the lane-detected images. The blue colored markings are the lanes as detected by our algorithm. . . . . . . . . . . . . . . . . . . . . . . . 79 5.15 A few snapshots from the results for Caltech Cordova1 Dataset. Eachoriginalsnapshotisfollowedbyitscorrespondinglane-detected image. The green lined borders in the lane-detected images indi- cate the ROI while the red colored lines are the lane markings as detected by our algorithm. . . . . . . . . . . . . . . . . . . . . . . . 80 5.16 A few snapshots from the results for Caltech Cordova2 Dataset. Eachoriginalsnapshotisfollowedbyitscorrespondinglane-detected image. The green lined borders in the lane-detected images indi- cate the ROI while the red colored lines are the lane markings as detected by our algorithm. . . . . . . . . . . . . . . . . . . . . . . . 81 5.17 AfewsnapshotsfromtheresultsforCaltechWashingtonDataset. Eachoriginalsnapshotisfollowedbyitscorrespondinglane-detected image. The green lined borders in the lane-detected images indi- cate the ROI while the red colored lines are the lane markings as detected by our algorithm. . . . . . . . . . . . . . . . . . . . . . . . 82