Hardware-Accelerated Algorithms in Visual Computing Dissertation zur Erlangung des Grades des Doktors der Ingenieurwissenschaften der Naturwissenschaftlich-Technischen Fakult¨aten der Universit¨at des Saarlandes vorgelegt von Pascal Gwosdek Saarbru¨cken 2011 ii Tag des Kolloquiums: 11.07.2012 Dekan: Prof. Dr. Mark Groves Pru¨fungsausschuss: Prof. Dr. Thorsten Herfet Universit¨at des Saarlandes (Vorsitz) Prof. Dr. Joachim Weickert Universit¨at des Saarlandes (1. Gutachter) Prof. Dr. Horst Bischof Technische Universit¨at Graz (2. Gutachter) Dr. Christian Schmaltz Universit¨at des Saarlandes iii Eidesstattliche Versicherung Hiermit versichere ich an Eides statt, dass ich die vorliegende Arbeit selbsta¨ndig und ohne Benutzung anderer als der angegebenen Hilfsmittel angefertigt habe. Die aus anderen Quellen oder indirekt u¨bernommenen Daten und Konzepte sind unter Angabe der Quelle gekennzeichnet. Die Arbeit wurde bisher weder im In- noch im Ausland in gleicher oder ¨ahn- licher Form in einem Verfahren zur Erlangung eines akademischen Grades vorgelegt. Saarbru¨cken, 11.07.2012 ¨ Ver¨offentlichungs- und Ubereinstimmungserkl¨arung Ich u¨bertrage der Saarla¨ndischen Universita¨ts- und Landesbibliothek (SULB) das Recht, diese Arbeit in elektronischer und gedruckter Form zuga¨nglich zu machen. Ich best¨atige, dass die hierzu u¨bermittelte elek- tronische Version der Arbeit mit der genehmigten Originalfassung in Form und Inhalt u¨bereinstimmt. Saarbru¨cken, 11.07.2012 Contents Contents v 1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 CUDA 7 2.1 Graphics Processing Units . . . . . . . . . . . . . . . . . . . 7 2.1.1 Performance . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.2 The GPU as a Coprocessor . . . . . . . . . . . . . . 8 2.1.3 Memory Model . . . . . . . . . . . . . . . . . . . . . 10 2.2 CUDA Programming Model . . . . . . . . . . . . . . . . . . 12 2.2.1 General Concepts . . . . . . . . . . . . . . . . . . . . 12 2.2.2 Textures . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2.3 Atomic Operations . . . . . . . . . . . . . . . . . . . 16 2.2.4 Algorithmic Optimisation Techniques . . . . . . . . . 17 2.3 Runtime Measurement . . . . . . . . . . . . . . . . . . . . . 18 3 Homogeneous Diffusion 21 3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Introduction to Homogeneous Diffusion . . . . . . . . . . . . 22 3.3 Classical Numerics . . . . . . . . . . . . . . . . . . . . . . . 23 3.3.1 Explicit Linear Diffusion . . . . . . . . . . . . . . . . 23 3.3.2 Implicit Linear Diffusion . . . . . . . . . . . . . . . . 25 3.3.3 Spatial Convolution . . . . . . . . . . . . . . . . . . . 26 3.3.4 Multiplication in the Frequency Domain . . . . . . . 29 3.3.5 Recursive Filtering . . . . . . . . . . . . . . . . . . . 30 3.3.6 Iterated Box Filtering . . . . . . . . . . . . . . . . . 35 3.4 Numerical Improvements . . . . . . . . . . . . . . . . . . . . 40 3.4.1 Box Filtering with Correction . . . . . . . . . . . . . 40 v vi CONTENTS 3.4.2 Extended Box Filtering . . . . . . . . . . . . . . . . . 42 3.5 Efficient GPU-Based Algorithms . . . . . . . . . . . . . . . . 46 3.5.1 Explicit Linear Diffusion . . . . . . . . . . . . . . . . 46 3.5.2 Implicit Linear Diffusion . . . . . . . . . . . . . . . . 47 3.5.3 Spatial Convolution . . . . . . . . . . . . . . . . . . . 48 3.5.4 Multiplication in the Frequency Domain . . . . . . . 50 3.5.5 Recursive Filtering . . . . . . . . . . . . . . . . . . . 52 3.5.6 Iterated (Extended) Box Filtering . . . . . . . . . . . 53 3.6 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.6.1 Ground Truth . . . . . . . . . . . . . . . . . . . . . . 57 3.6.2 Parameter Configuration . . . . . . . . . . . . . . . . 60 3.6.3 Quality Comparison . . . . . . . . . . . . . . . . . . 76 3.6.4 Runtime . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 4 Anisotropic diffusion 91 4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 4.2 Edge and Coherence Enhancing Diffusion . . . . . . . . . . . 93 4.3 Fast Explicit Diffusion . . . . . . . . . . . . . . . . . . . . . 95 4.4 Implementation on a GPU . . . . . . . . . . . . . . . . . . . 98 4.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 4.5.1 Visual Comparison . . . . . . . . . . . . . . . . . . . 99 4.5.2 Runtime Scaling on Image Size . . . . . . . . . . . . 101 4.5.3 Runtime Scaling on Stopping Time . . . . . . . . . . 103 4.5.4 Runtime Comparison to CPU . . . . . . . . . . . . . 105 4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5 PDE-Based Image Inpainting 109 5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 5.2 Image Inpainting . . . . . . . . . . . . . . . . . . . . . . . . 111 5.3 Cascadic FED . . . . . . . . . . . . . . . . . . . . . . . . . . 112 5.4 GPU-Based Algorithm . . . . . . . . . . . . . . . . . . . . . 114 5.4.1 FED . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.4.2 Resampling . . . . . . . . . . . . . . . . . . . . . . . 115 5.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5.5.1 Quality and Parameters . . . . . . . . . . . . . . . . 117 5.5.2 Runtime . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.6 Application: Realtime Video Inpainting . . . . . . . . . . . . 124 5.6.1 Scenario . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.6.2 Semantic and Analytic Image Compression . . . . . . 124 5.6.3 Implementation . . . . . . . . . . . . . . . . . . . . . 125 CONTENTS vii 5.6.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . 127 5.6.5 Efficiency . . . . . . . . . . . . . . . . . . . . . . . . 128 5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6 Optic Flow 133 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 6.2 Variational Optic Flow . . . . . . . . . . . . . . . . . . . . . 136 6.2.1 Complementary Optic Flow . . . . . . . . . . . . . . 137 6.2.2 Energy Minimisation via the Euler-Lagrange Framework . . . . . . . . . . . . . . . 140 6.2.3 Warping . . . . . . . . . . . . . . . . . . . . . . . . . 141 6.3 Numerical Solution . . . . . . . . . . . . . . . . . . . . . . . 143 6.3.1 Fast Explicit Diffusion . . . . . . . . . . . . . . . . . 143 6.3.2 Fast Jacobi . . . . . . . . . . . . . . . . . . . . . . . 146 6.3.3 Cascadic Application . . . . . . . . . . . . . . . . . . 148 6.4 Implementation on the GPU . . . . . . . . . . . . . . . . . . 149 6.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 6.5.1 Quality . . . . . . . . . . . . . . . . . . . . . . . . . 151 6.5.2 Runtime . . . . . . . . . . . . . . . . . . . . . . . . . 161 6.6 Interactive Real-Time Application . . . . . . . . . . . . . . . 166 6.7 Summary and Conclusion . . . . . . . . . . . . . . . . . . . 167 7 Halftoning 171 7.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 7.2 Point-Based Halftoning . . . . . . . . . . . . . . . . . . . . . 175 7.2.1 Rendering . . . . . . . . . . . . . . . . . . . . . . . . 178 7.2.2 Sampling . . . . . . . . . . . . . . . . . . . . . . . . 180 7.2.3 Sampling + Rendering = Halftoning? . . . . . . . . . 182 7.3 Electrostatic Halftoning . . . . . . . . . . . . . . . . . . . . 184 7.3.1 Repulsion . . . . . . . . . . . . . . . . . . . . . . . . 185 7.3.2 Attraction . . . . . . . . . . . . . . . . . . . . . . . . 187 7.3.3 Towards an Iterative Scheme . . . . . . . . . . . . . . 188 7.4 Modifications and Extensions . . . . . . . . . . . . . . . . . 191 7.4.1 Dithering . . . . . . . . . . . . . . . . . . . . . . . . 192 7.4.2 Point Size Adjustment . . . . . . . . . . . . . . . . . 194 7.4.3 Grey Value Correction . . . . . . . . . . . . . . . . . 195 7.4.4 Jittering for Stippling . . . . . . . . . . . . . . . . . . 198 7.4.5 Edge Enhancement . . . . . . . . . . . . . . . . . . . 200 7.4.6 Colour Halftoning . . . . . . . . . . . . . . . . . . . . 201 7.4.7 Second Order Screening . . . . . . . . . . . . . . . . 206 7.4.8 Multi-Class Sampling . . . . . . . . . . . . . . . . . . 210 viii CONTENTS 7.5 Direct Summation Algorithm . . . . . . . . . . . . . . . . . 214 7.5.1 Attraction . . . . . . . . . . . . . . . . . . . . . . . . 215 7.5.2 Repulsion . . . . . . . . . . . . . . . . . . . . . . . . 218 7.5.3 Transporting Particles . . . . . . . . . . . . . . . . . 220 7.5.4 Additional Features . . . . . . . . . . . . . . . . . . . 221 7.6 Fast Summation Algorithm . . . . . . . . . . . . . . . . . . 222 7.6.1 Repulsion by Fast Summation . . . . . . . . . . . . . 224 7.6.2 Non-Equispaced Fast Fourier Transform . . . . . . . 228 7.6.3 Near-Field Evaluation . . . . . . . . . . . . . . . . . 232 7.6.4 Attraction . . . . . . . . . . . . . . . . . . . . . . . . 235 7.7 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 7.7.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . 236 7.7.2 Evaluation of Quality . . . . . . . . . . . . . . . . . . 237 7.7.3 Modifications and Extensions . . . . . . . . . . . . . 251 7.7.4 Runtime . . . . . . . . . . . . . . . . . . . . . . . . . 292 7.7.5 Quality-Based Runtime for Fast Summation . . . . . 299 7.7.6 CUDA Performance Profiling . . . . . . . . . . . . . 299 7.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 8 Summary and Outlook 305 8.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 8.2 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . 308 8.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 A Proofs 313 A.1 Linear Diffusion . . . . . . . . . . . . . . . . . . . . . . . . . 313 A.2 Halftoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 Bibliography 329 Short Abstract This thesis presents new parallel algorithms which accelerate computer vi- sion methods by the use of graphics processors (GPUs) and evaluates them with respect to their speed, scalability, and the quality of their results. It covers the fields of homogeneous and anisotropic diffusion processes, diffu- sion image inpainting, optic flow, and halftoning. In this turn, it compares different solvers for homogeneous diffusion and presents a novel ‘extended’ box filter. Moreover, it suggests to use the fast explicit diffusion scheme (FED) as an efficient and flexible solver for nonlinear and in particular for anisotropic parabolic diffusion problems on graphics hardware. For elliptic diffusion-like processes, it recommends to use cascadic FED or Fast Jacobi schemes. The presented optic flow algorithmrepresentsoneofthefastestyetveryaccuratetechniques. Finally, it presents a novel halftoning scheme which yields state-of-the-art results for many applications in image processing and computer graphics. ix