Design for Embedded Image Processing on FPGAs

Donald Graeme Bailey, PhD, is Professor of Imaging Systems in the Department of Mechanical and Electrical Engineering, Massey University, New Zealand. He is an internationally recognized expert on FPGA technology in image processing, and has published widely on FPGAs and related subjects.

Preface xiii Acknowledgments xix About the Companion Website xxi 1 Image Processing 1 1.1 Basic Definitions 1 1.2 Image Formation 3 1.2.1 Optics 3 1.2.2 Colour 5 1.3 Image Processing Operations 6 1.4 Real-time Image Processing 8 1.5 Embedded Image Processing 9 1.6 Computer Architecture 10 1.7 Parallelism 11 1.7.1 Temporal or Task Parallelism 12 1.7.2 Spatial or Data Parallelism 13 1.7.3 Logical Parallelism 14 1.7.4 Stream Processing 14 1.8 Summary 15 References 16 2 Field-programmable Gate Arrays 19 2.1 Hardware Architecture of FPGAs 19 2.1.1 Logic 21 2.1.2 DSP Blocks 22 2.1.3 Memory 23 2.1.4 Embedded CPU 23 2.1.5 Interconnect 24 2.1.6 Input and Output 24 2.1.7 Clocking 26 2.1.8 Configuration 26 2.1.9 FPGAs vs. ASICs 27 2.2 Programming FPGAs 28 2.2.1 Register Transfer Level 30 2.2.2 Hardware Description Languages 32 2.2.3 High-level Synthesis 33 2.3 FPGAs and Image Processing 38 2.3.1 Choosing an FPGA or Development Board 39 2.4 Summary 40 References 41 3 Design Process 45 3.1 Problem Specification 45 3.2 Algorithm Development 47 3.2.1 Algorithm Development Process 47 3.2.2 Algorithm Structure 48 3.2.3 FPGA Development Issues 51 3.3 Architecture Selection 51 3.3.1 System Architecture 52 3.3.2 Partitioning Between Hardware and Software 53 3.3.3 Computational Architecture 55 3.4 System Implementation 60 3.4.1 Mapping to FPGA Resources 60 3.4.2 Algorithm Mapping Issues 62 3.5 Testing and Debugging 63 3.5.1 Design 63 3.5.2 Implementation 64 3.5.3 Common Implementation Bugs 64 3.5.4 Timing 66 3.5.5 System Debugging 68 3.5.6 Algorithm Tuning 70 3.5.7 In-field Diagnosis 71 3.6 Summary 72 References 73 4 Design Constraints 77 4.1 Timing Constraints 77 4.1.1 Low-level Pipelining 78 4.1.2 Process Synchronisation 80 4.1.3 Synchronising Between Clock Domains 82 4.1.4 I/O Constraints 83 4.2 Memory Bandwidth Constraints 84 4.2.1 Memory Architectures 84 4.2.2 Caching 86 4.2.3 Row Buffering 87 4.3 Resource Constraints 88 4.3.1 Bit-serial Computation 89 4.3.2 Resource Multiplexing 89 4.3.3 Arbitration 92 4.3.4 Resource Controllers 94 4.3.5 Reconfigurability 95 4.4 Power Constraints 97 4.5 Performance Metrics 98 4.5.1 Speed 99 4.5.2 Resources 99 4.5.3 Power 99 4.5.4 Cost 100 4.5.5 Application Metrics 100 4.6 Summary 101 References 102 5 Computational Techniques 105 5.1 Number Systems 105 5.1.1 Binary Integers 105 5.1.2 Residue Systems 106 5.1.3 Redundant Representations 107 5.1.4 Fixed-point Numbers 107 5.1.5 Floating-point Numbers 108 5.1.6 Logarithmic Number System 110 5.1.7 Posit Numbers 110 5.2 Elementary Functions 111 5.2.1 Square Root 111 5.2.2 Trigonometric Functions 112 5.2.3 Linear CORDIC 116 5.2.4 Hyperbolic Functions 117 5.2.5 Logarithms and Exponentials 118 5.2.6 Lookup Tables 118 5.2.7 Polynomial Approximations 122 5.2.8 Iterative Techniques 123 5.3 Other Computation Techniques 124 5.3.1 Incremental Update 124 5.3.2 Separability 124 5.4 Memory Structures 124 5.4.1 FIFO Buffer 124 5.4.2 Zigzag Buffers 126 5.4.3 Stacks 126 5.4.4 Linked Lists 127 5.4.5 Trees 128 5.4.6 Graphs 129 5.4.7 Hash Tables 129 5.5 Summary 130 References 131 6 Interfacing 135 6.1 Camera Input 135 6.1.1 Analogue Video 136 6.1.2 Direct Digital Interface 137 6.1.3 MIPI Camera Serial Interface 138 6.1.4 Camera Link 139 6.1.5 USB Cameras 139 6.1.6 GigE Vision 139 6.1.7 Camera Processing Pipeline 140 6.2 Display Output 143 6.2.1 Display Driver 143 6.2.2 Display Content 146 6.3 Serial Communication 147 6.3.1 Rs- 232 147 6.3.2 I 2 c 148 6.3.3 Serial Peripheral Interface (SPI) 149 6.3.4 Universal Serial Bus (USB) 150 6.3.5 Ethernet 150 6.3.6 PCI Express 151 6.4 Off-chip Memory 151 6.4.1 Static RAM 152 6.4.2 Dynamic RAM 152 6.4.3 Flash Memory 155 6.5 Processors 155 6.5.1 AXI Interface 155 6.5.2 Avalon Bus 156 6.5.3 Operating Systems 157 6.5.4 Implications for System Design 157 6.6 Summary 157 References 158 7 Point Operations 161 7.1 Point Operations on a Single Image 161 7.1.1 Contrast and Brightness Adjustment 161 7.1.2 Global Thresholding and Contouring 164 7.1.3 Lookup Table Implementation 166 7.2 Point Operations on Multiple Images 167 7.2.1 Image Averaging 168 7.2.2 Image Subtraction 170 7.2.3 Background Modelling 172 7.2.4 Intensity Scaling 175 7.2.5 Masking 175 7.2.6 High Dynamic Range (HDR) Imaging 177 7.3 Colour 179 7.3.1 False Colour 179 7.3.2 Colour Space Conversion 180 7.3.3 Colour Thresholding 192 7.3.4 Colour Enhancement 193 7.3.5 White Balance 194 7.4 Multi-spectral and Hyperspectral Imaging 197 7.4.1 Hyperspectral Image Acquisition 197 7.4.2 Processing Steps 198 7.5 Summary 199 References 199 8 Histogram Operations 203 8.1 Greyscale Histogram 203 8.1.1 Building the Histogram 203 8.1.2 Data Gathering 205 8.1.3 Histogram Equalisation 209 8.1.4 Automatic Exposure 214 8.1.5 Threshold Selection 215 8.1.6 Histogram Similarity 220 8.2 Multidimensional Histograms 220 8.2.1 Triangular Arrays 221 8.2.2 Multidimensional Statistics 222 8.2.3 Colour Segmentation 225 8.2.4 Colour Indexing 228 8.2.5 Texture Analysis 229 8.3 Summary 231 References 231 9 Local Filters 235 9.1 Window Caching 235 9.1.1 Border Handling 237 9.1.2 Filter Latency 239 9.2 Linear Filters 239 9.2.1 Filter Techniques 240 9.2.2 Noise Smoothing 243 9.2.3 Edge Detection 246 9.2.4 Edge Enhancement 248 9.3 Nonlinear Filters 249 9.3.1 Gradient Magnitude 249 9.3.2 Edge Orientation 250 9.3.3 Peak Detection and Non-maximal Suppression 251 9.3.4 Zero-crossing Detection 252 9.3.5 Bilateral Filter 252 9.3.6 Adaptive Thresholding 253 9.3.7 High Dynamic Range Tone Mapping 255 9.4 Rank Filters 256 9.4.1 Sorting Networks 258 9.5 Adaptive Histogram Equalisation 262 9.6 Morphological Filters 262 9.6.1 Binary Morphology 262 9.6.2 Greyscale Morphology 266 9.7 Colour Filtering 268 9.7.1 Colour Morphology and Vector Median 269 9.7.2 Edge Enhancement 269 9.7.3 Bayer Pattern Demosaicing 271 9.7.4 White Balancing 272 9.8 Summary 273 References 274 10 Geometric Transformations 281 10.1 Reverse Mapping 282 10.1.1 Anti-alias Filtering 283 10.1.2 Interpolation 284 10.2 Forward Mapping 291 10.2.1 Separable Mapping 292 10.2.2 Hybrid Approach 296 10.3 Common Mappings 297 10.3.1 Affine Transformation 297 10.3.2 Perspective Mapping 297 10.3.3 Polynomial Mapping 298 10.3.4 Lens Distortion 299 10.3.5 Non-parametric Mappings 302 10.4 Image Registration 302 10.4.1 Feature-based Methods 303 10.4.2 Area-based Methods 307 10.4.3 Applications 314 10.5 Summary 315 References 315 11 Linear Transforms 321 11.1 Discrete Fourier Transform 322 11.1.1 Fast Fourier Transform (FFT) 323 11.1.2 Goertzel's Algorithm 331 11.1.3 Applications 332 11.2 Discrete Cosine Transform (DCT) 336 11.3 Wavelet Transform 338 11.3.1 Filter Implementations 340 11.3.2 Applications 344 11.4 Summary 345 References 345 12 Image and Video Coding 349 12.1 Compression Techniques 350 12.1.1 Colour Conversion 350 12.1.2 Prediction and Transformation 350 12.1.3 Motion Estimation and Compensation 351 12.1.4 Quantisation 352 12.1.5 Run-length Coding 353 12.1.6 Entropy Coding 354 12.2 DCT-based Codecs 357 12.2.1 DCT Block Processing 357 12.2.2 Jpeg 357 12.2.3 Video Codecs 358 12.3 Wavelet-based Codecs 359 12.4 Lossless Compression 360 12.5 Perceptual Coding 361 12.6 Coding Hyperspectral Images 362 12.7 Summary 362 References 363 13 Blob Detection and Labelling 367 13.1 Bounding Box 367 13.2 Run-length Coding 369 13.3 Chain Coding 369 13.3.1 Sequential Implementation 370 13.3.2 Single-pass Stream Processing Algorithms 370 13.3.3 Feature Extraction 372 13.4 Connected Component Labelling (CCL) 374 13.4.1 Random Access Algorithms 374 13.4.2 Multiple Pass Algorithms 374 13.4.3 Two-pass Algorithms 375 13.4.4 Parallel Algorithms 377 13.4.5 Hysteresis Thresholding 377 13.5 Connected Component Analysis (CCA) 377 13.5.1 Basic Single-pass Algorithm 378 13.5.2 Reducing Memory Requirements 379 13.5.3 Eliminating End-of-row Overheads 379 13.5.4 Parallel Algorithms 380 13.5.5 Further Considerations and Optimisations 381 13.6 Distance Transform 381 13.6.1 Morphological Approaches 381 13.6.2 Chamfer Distance 382 13.6.3 Euclidean Distance 384 13.6.4 Applications 386 13.6.5 Geodesic Distance Transform 386 13.7 Watershed Transform 387 13.7.1 Flow Algorithms 388 13.7.2 Immersion Algorithms 389 13.8 Hough Transform 391 13.8.1 Line Hough Transform 391 13.8.2 Circle Hough Transform 394 13.8.3 Generalised Hough Transform 395 13.9 Summary 396 References 396 14 Machine Learning 403 14.1 Training 403 14.1.1 Loss and Cost Functions 404 14.1.2 Model Optimisation 405 14.1.3 Considerations 406 14.2 Regression 409 14.2.1 Linear Regression 409 14.2.2 Nonlinear Regression 409 14.2.3 Neural Networks 409 14.3 Classification 411 14.3.1 Decision Trees 411 14.3.2 Random Forests 412 14.3.3 Bayesian Classification 412 14.3.4 Quadratic Discriminant Analysis 414 14.3.5 Linear Discriminant Analysis 414 14.3.6 Support Vector Machines 415 14.3.7 Neural Networks 416 14.3.8 Clustering 417 14.4 Deep Learning 418 14.4.1 Building Blocks 419 14.4.2 Architectures and Applications 421 14.4.3 Training 427 14.4.4 Implementation Issues 428 14.5 Summary 433 References 433 15 Example Applications 441 15.1 Coloured Region Tracking 441 15.2 Foveal Sensor 443 15.2.1 Foveal Mapping 444 15.2.2 Using the Sensor 447 15.3 Real-time Produce Grading 448 15.3.1 Software Algorithm 448 15.3.2 Hardware Implementation 450 15.4 Stereo Imaging 453 15.4.1 Rectification 454 15.4.2 Calculating the Depth 456 15.4.3 Stereo Matching Design 457 15.5 Face Detection 459 15.5.1 Design 460 15.6 Summary 461 References 461 Index 465