Bridge the gap between software and hardware with this foundational design reference
Field-programmable gate arrays (FPGAs) are integrated circuits designed so that configuration can take place. Circuits of this kind play an integral role in processing images, with FPGAs increasingly embedded in digital cameras and other devices that produce visual data outputs for subsequent realization and compression. These uses of FPGAs require specific design processes designed to mediate smoothly between hardware and processing algorithm.
Design for Embedded Image Processing on FPGAs provides a comprehensive overview of these processes and their applications in embedded image processing. Beginning with an overview of image processing and its core principles, this book discusses specific design and computation techniques, with a smooth progression from the foundations of the field to its advanced principles.
Readers of the second edition of Design for Embedded Image Processing on FPGAs will also find:
- Detailed discussion of image processing techniques including point operations, histogram operations, linear transformations, and more
- New chapters covering Deep Learning algorithms and Image and Video Coding
- Example applications throughout to ground principles and demonstrate techniques
Design for Embedded Image Processing on FPGAs is ideal for engineers and academics working in the field of Image Processing, as well as graduate students studying Embedded Systems Engineering, Image Processing, Digital Design, and related fields.
Table of Contents
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