Preface xi
Acknowledgements xvii
1 Image Processing 1
1.1 Basic Definitions 2
1.2 Image Formation 3
1.3 Image Processing Operations 7
1.4 Example Application 9
1.5 Real-Time Image Processing 11
1.6 Embedded Image Processing 12
1.7 Serial Processing 12
1.8 Parallelism 14
1.9 Hardware Image Processing Systems 18
2 Field Programmable Gate Arrays 21
2.1 Programmable Logic 21
2.1.1 FPGAs vs. ASICs 24
2.2 FPGAs and Image Processing 25
2.3 Inside an FPGA 26
2.3.1 Logic 27
2.3.2 Interconnect 28
2.3.3 Input and Output 29
2.3.4 Clocking 30
2.3.5 Configuration 31
2.3.6 Power Consumption 32
2.4 FPGA Families and Features 33
2.4.1 Xilinx 33
2.4.2 Altera 38
2.4.3 Lattice Semiconductor 44
2.4.4 Achronix 46
2.4.5 SiliconBlue 47
2.4.6 Tabula 47
2.4.7 Actel 48
2.4.8 Atmel 49
2.4.9 QuickLogic 50
2.4.10 MathStar 50
2.4.11 Cypress 51
2.5 Choosing an FPGA or Development Board 51
3 Languages 53
3.1 Hardware Description Languages 56
3.2 Software-Based Languages 61
3.2.1 Structural Approaches 63
3.2.2 Augmented Languages 64
3.2.3 Native Compilation Techniques 69
3.3 Visual Languages 72
3.3.1 Behavioural 73
3.3.2 Dataflow 73
3.3.3 Hybrid 74
3.4 Summary 77
4 Design Process 79
4.1 Problem Specification 79
4.2 Algorithm Development 81
4.2.1 Algorithm Development Process 82
4.2.2 Algorithm Structure 83
4.2.3 FPGA Development Issues 86
4.3 Architecture Selection 86
4.3.1 System Level Architecture 87
4.3.2 Computational Architecture 89
4.3.3 Partitioning between Hardware and Software 93
4.4 System Implementation 96
4.4.1 Mapping to FPGA Resources 97
4.4.2 Algorithm Mapping Issues 100
4.4.3 Design Flow 101
4.5 Designing for Tuning and Debugging 102
4.5.1 Algorithm Tuning 102
4.5.2 System Debugging 104
5 Mapping Techniques 107
5.1 Timing Constraints 107
5.1.1 Low Level Pipelining 107
5.1.2 Process Synchronisation 110
5.1.3 Multiple Clock Domains 111
5.2 Memory Bandwidth Constraints 113
5.2.1 Memory Architectures 113
5.2.2 Caching 116
5.2.3 Row Buffering 117
5.2.4 Other Memory Structures 118
vi Contents
5.3 Resource Constraints 122
5.3.1 Resource Multiplexing 122
5.3.2 Resource Controllers 125
5.3.3 Reconfigurability 130
5.4 Computational Techniques 132
5.4.1 Number Systems 132
5.4.2 Lookup Tables 138
5.4.3 CORDIC 142
5.4.4 Approximations 150
5.4.5 Other Techniques 152
5.5 Summary 154
6 Point Operations 155
6.1 Point Operations on a Single Image 155
6.1.1 Contrast and Brightness Adjustment 155
6.1.2 Global Thresholding and Contouring 159
6.1.3 Lookup Table Implementation 162
6.2 Point Operations on Multiple Images 163
6.2.1 Image Averaging 164
6.2.2 Image Subtraction 166
6.2.3 Image Comparison 170
6.2.4 Intensity Scaling 171
6.2.5 Masking 173
6.3 Colour Image Processing 175
6.3.1 False Colouring 175
6.3.2 Colour Space Conversion 176
6.3.3 Colour Thresholding 192
6.3.4 Colour Correction 193
6.3.5 Colour Enhancement 197
6.4 Summary 197
7 Histogram Operations 199
7.1 Greyscale Histogram 199
7.1.1 Data Gathering 201
7.1.2 Histogram Equalisation 206
7.1.3 Automatic Exposure 210
7.1.4 Threshold Selection 211
7.1.5 Histogram Similarity 219
7.2 Multidimensional Histograms 219
7.2.1 Triangular Arrays 220
7.2.2 Multidimensional Statistics 222
7.2.3 Colour Segmentation 226
7.2.4 Colour Indexing 229
7.2.5 Texture Analysis 231
Contents vii
8 Local Filters 233
8.1 Caching 233
8.2 Linear Filters 239
8.2.1 Noise Smoothing 239
8.2.2 Edge Detection 241
8.2.3 Edge Enhancement 243
8.2.4 Linear Filter Techniques 243
8.3 Nonlinear Filters 248
8.3.1 Edge Orientation 250
8.3.2 Non-maximal Suppression 251
8.3.3 Zero-Crossing Detection 252
8.4 Rank Filters 252
8.4.1 Rank Filter Sorting Networks 255
8.4.2 Adaptive Histogram Equalisation 260
8.5 Colour Filters 261
8.6 Morphological Filters 264
8.6.1 Binary Morphology 264
8.6.2 Greyscale Morphology 269
8.6.3 Colour Morphology 270
8.7 Adaptive Thresholding 271
8.7.1 Error Diffusion 271
8.8 Summary 273
9 Geometric Transformations 275
9.1 Forward Mapping 276
9.1.1 Separable Mapping 277
9.2 Reverse Mapping 282
9.3 Interpolation 285
9.3.1 Bilinear Interpolation 286
9.3.2 Bicubic Interpolation 288
9.3.3 Splines 290
9.3.4 Interpolating Compressed Data 292
9.4 Mapping Optimisations 292
9.5 Image Registration 294
9.5.1 Feature-Based Methods 295
9.5.2 Area-Based Methods 299
9.5.3 Applications 305
10 Linear Transforms 309
10.1 Fourier Transform 310
10.1.1 Fast Fourier Transform 311
10.1.2 Filtering 318
10.1.3 Inverse Filtering 320
10.1.4 Interpolation 321
10.1.5 Registration 322
viii Contents
10.1.6 Feature Extraction 323
10.1.7 Goertzel’s Algorithm 324
10.2 Discrete Cosine Transform 325
10.3 Wavelet Transform 328
10.3.1 Filter Implementations 330
10.3.2 Applications of the Wavelet Transform 335
10.4 Image and Video Coding 336
11 Blob Detection and Labelling 343
11.1 Bounding Box 343
11.2 Run-Length Coding 346
11.3 Chain Coding 347
11.3.1 Sequential Implementation 347
11.3.2 Single Pass Algorithms 348
11.3.3 Feature Extraction 350
11.4 Connected Component Labelling 352
11.4.1 Random Access Algorithms 353
11.4.2 Multiple-Pass Algorithms 353
11.4.3 Two-Pass Algorithms 354
11.4.4 Single-Pass Algorithms 356
11.4.5 Multiple Input Labels 358
11.4.6 Further Optimisations 358
11.5 Distance Transform 359
11.5.1 Morphological Approaches 360
11.5.2 Chamfer Distance 360
11.5.3 Separable Transform 362
11.5.4 Applications 365
11.5.5 Geodesic Distance Transform 365
11.6 Watershed Transform 366
11.6.1 Flow Algorithms 366
11.6.2 Immersion Algorithms 367
11.6.3 Applications 369
11.7 Hough Transform 370
11.7.1 Line Hough Transform 371
11.7.2 Circle Hough Transform 373
11.7.3 Generalised Hough Transform 374
11.8 Summary 375
12 Interfacing 377
12.1 Camera Input 378
12.1.1 Camera Interface Standards 378
12.1.2 Deinterlacing 383
12.1.3 Global and Rolling Shutter Correction 384
12.1.4 Bayer Pattern Processing 384
Contents ix
12.2 Display Output 387
12.2.1 Display Driver 387
12.2.2 Display Content 390
12.3 Serial Communication 393
12.3.1 PS2 Interface 393
12.3.2 I2C 395
12.3.3 SPI 397
12.3.4 RS-232 397
12.3.5 USB 398
12.3.6 Ethernet 398
12.3.7 PCI Express 399
12.4 Memory 400
12.4.1 Static RAM 400
12.4.2 Dynamic RAM 401
12.4.3 Flash Memory 402
12.5 Summary 402
13 Testing, Tuning and Debugging 405
13.1 Design 405
13.1.1 Random Noise Sources 406
13.2 Implementation 409
13.2.1 Common Implementation Bugs 410
13.3 Tuning 412
13.4 Timing Closure 412
14 Example Applications 415
14.1 Coloured Region Tracking 415
14.2 Lens Distortion Correction 418
14.2.1 Characterising the Distortion 419
14.2.2 Correcting the Distortion 421
14.3 Foveal Sensor 424
14.3.1 Foveal Mapping 425
14.3.2 Using the Sensor 429
14.4 Range Imaging 429
14.4.1 Extending the Unambiguous Range 431
14.5 Real-Time Produce Grading 433
14.5.1 Software Algorithm 434
14.5.2 Hardware Implementation 436
14.6 Summary 439
References 441
Index 475
x Content
1