Design for Embedded Image Processing on FPGAs
, by Bailey, Donald G.- ISBN: 9781119819790 | 1119819792
- Cover: Hardcover
- Copyright: 8/14/2023
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.
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
Audience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv
Changes Since the First Edition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv
Outline of the Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv
Conventions Used . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviii
Acknowledgements xix
1 Image Processing 1
1.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Image Formation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Optics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 Colour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Image Processing Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Real-Time Image Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Embedded Image Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6 Computer Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7 Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.9 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.7 Clocking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1.8 Configuration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1.9 FPGAs vs. ASICs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2 Programming FPGAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2.1 Register Transfer Level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2.2 Hardware Description Languages . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.2.3 High-Level Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3 FPGAs and Image Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.3.1 Choosing an FPGA or Development Board . . . . . . . . . . . . . . . . . . . . 40
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.5 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3 Design Process 47
3.1 Problem Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2 Algorithm Development . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2.1 Algorithm Development Process . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2.2 Algorithm Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.2.3 FPGA Development Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3 Architecture Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3.1 System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3.2 Partitioning Between Hardware and Software . . . . . . . . . . . . . . . . . . . 56
3.3.3 Computational Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.4 System Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.4.1 Mapping to FPGA Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.4.2 Algorithm Mapping Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.5 Testing and Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.5.1 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.5.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.5.3 Common Implementation Bugs . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.5.4 Timing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.5.5 System Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.5.6 Algorithm Tuning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.5.7 In-Field Diagnosis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.7 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4 Design Constraints 83
4.1 Timing Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.1.1 Low-Level Pipelining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.1.2 Process Synchronisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.1.3 Synchronising Between Clock Domains . . . . . . . . . . . . . . . . . . . . . . 88
4.1.4 I/O Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.2 Memory Bandwidth Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.2.1 Memory Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.2.2 Caching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.2.3 Row Buffering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.3 Resource Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.3.1 Bit-Serial Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.3.2 Resource Multiplexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.3.3 Arbitration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.3.4 Resource Controllers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.3.5 Reconfigurability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.4 Power Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4.5 Performance Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.5.1 Speed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.5.2 Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.5.3 Power . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.5.4 Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.5.5 Application Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.7 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5 Computational Techniques 113
5.1 Number Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.1.1 Binary Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.1.2 Residue Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5.1.3 Redundant Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.1.4 Fixed-Point Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.1.5 Floating-Point Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.1.6 Logarithmic Number System . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.1.7 Posit Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.2 Elementary Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.2.1 Square Root . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.2.2 Trigonometric Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.2.3 Linear CORDIC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.2.4 Hyperbolic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.2.5 Logarithms and Exponentials . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.2.6 Lookup Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
5.2.7 Polynomial Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.2.8 Iterative Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.3 Other Computation Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.3.1 Incremental Update . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.3.2 Separability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.4 Memory Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
5.4.1 FIFO Buffer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
5.4.2 Zigzag Buffers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
5.4.3 Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.4.4 Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.4.5 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.4.6 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
5.4.7 Hash Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.6 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
6 Interfacing 145
6.1 Camera Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
6.1.1 Analogue Video . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.1.2 Direct Digital Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
6.1.3 MIPI Camera Serial Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
6.1.4 Camera Link . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.1.5 USB Cameras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.1.6 GigE Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.1.7 Camera Processing Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
6.2 Display Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
6.2.1 Display Driver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
6.2.2 Display Content . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
6.3 Serial Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
6.3.1 RS-232 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
6.3.2 I2C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
6.3.3 Serial Peripheral Interface (SPI) . . . . . . . . . . . . . . . . . . . . . . . . . . 159
6.3.4 Universal Serial Bus (USB) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
6.3.5 Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
6.3.6 PCI Express . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
6.4 Off-Chip Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
6.4.1 Static RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
6.4.2 Dynamic RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
6.4.3 Flash Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.5 Processors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.5.1 AXI Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.5.2 Avalon Bus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
6.5.3 Operating Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
6.5.4 Implications for System Design . . . . . . . . . . . . . . . . . . . . . . . . . . 167
6.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
6.7 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
7 Point Operations 171
7.1 Point Operations on a Single Image . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
7.1.1 Contrast and Brightness Adjustment . . . . . . . . . . . . . . . . . . . . . . . . 172
7.1.2 Global Thresholding and Contouring . . . . . . . . . . . . . . . . . . . . . . . 174
7.1.3 Lookup Table Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
7.2 Point Operations on Multiple Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
7.2.1 Image Averaging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
7.2.2 Image Subtraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
7.2.3 Background Modelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
7.2.4 Intensity Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
7.2.5 Masking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
7.2.6 High Dynamic Range (HDR) Imaging . . . . . . . . . . . . . . . . . . . . . . . 187
7.3 Colour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
7.3.1 False Colour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
7.3.2 Colour Space Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
7.3.3 Colour Thresholding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
7.3.4 Colour Enhancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
7.3.5 White Balance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
7.4 Multi-Spectral and Hyperspectral Imaging . . . . . . . . . . . . . . . . . . . . . . . . . 208
7.4.1 Hyperspectral Image Acquisition . . . . . . . . . . . . . . . . . . . . . . . . . 208
7.4.2 Processing Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
7.6 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
8 Histogram Operations 217
8.1 Grey-Scale Histogram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
8.1.1 Building the Histogram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
8.1.2 Data Gathering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
8.1.3 Histogram Equalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
8.1.4 Automatic Exposure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
8.1.5 Threshold Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
8.1.6 Histogram Similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
8.2 Multi-Dimensional Histograms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
8.2.1 Triangular Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
8.2.2 Multi-Dimensional Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
8.2.3 Colour Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
8.2.4 Colour Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
8.2.5 Texture Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
8.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
8.4 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
9 Local Filters 249
9.1 Window Caching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
9.1.1 Border Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
9.1.2 Filter Latency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
9.2 Linear Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
9.2.1 Filter Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
9.2.2 Noise Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
9.2.3 Edge Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
9.2.4 Edge Enhancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
9.3 Nonlinear Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
9.3.1 Gradient Magnitude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
9.3.2 Edge Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
9.3.3 Peak Detection and non-Maximal Suppression . . . . . . . . . . . . . . . . . . 265
9.3.4 Zero-Crossing Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
9.3.5 Bilateral Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
9.3.6 Adaptive Thresholding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
9.3.7 High Dynamic Range Tone Mapping . . . . . . . . . . . . . . . . . . . . . . . 269
9.4 Rank Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
9.4.1 Sorting Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
9.5 Adaptive Histogram Equalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
9.6 Morphological Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
9.6.1 Binary Morphology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
9.6.2 Grey-Scale Morphology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
9.7 Colour Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
9.7.1 Colour Morphology and Vector Median . . . . . . . . . . . . . . . . . . . . . . 283
9.7.2 Edge Enhancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
9.7.3 Bayer Pattern Demosaicing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
9.7.4 White Balancing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
9.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
9.9 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
10 Geometric Transformations 297
10.1 Reverse Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
10.1.1 Anti-Alias Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
10.1.2 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
10.2 Forward Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
10.2.1 Separable Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
10.2.2 Hybrid Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
10.3 Common Mappings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
10.3.1 Affine Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
10.3.2 Perspective Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
10.3.3 Polynomial Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
10.3.4 Lens Distortion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
10.3.5 Non-Parametric Mappings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
10.4 Image Registration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
10.4.1 Feature-Based Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
10.4.2 Area-Based Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
10.4.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
10.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
10.6 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
11 Linear Transforms 339
11.1 Discrete Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
11.1.1 Fast Fourier Transform (FFT) . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
11.1.2 Goertzel’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
11.1.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
11.2 Discrete Cosine Transform (DCT) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
11.3 Wavelet Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
11.3.1 Filter Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
11.3.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
11.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
11.5 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
12 Image and Video Coding 367
12.1 Compression Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
12.1.1 Colour Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
12.1.2 Prediction and Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
12.1.3 Motion Estimation and Compensation . . . . . . . . . . . . . . . . . . . . . . . 370
12.1.4 Quantisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
12.1.5 Run-Length Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
12.1.6 Entropy Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
12.2 DCT-Based Codecs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
12.2.1 DCT Block Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
12.2.2 JPEG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
12.2.3 Video Codecs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
12.3 Wavelet-Based Codecs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
12.4 Lossless Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
12.5 Perceptual Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
12.6 Coding Hyperspectral Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
12.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
12.8 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
13 Blob Detection and Labelling 387
13.1 Bounding Box . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
13.2 Run-Length Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
13.3 Chain Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
13.3.1 Sequential Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
13.3.2 Single-Pass Stream Processing Algorithms . . . . . . . . . . . . . . . . . . . . 391
13.3.3 Feature Extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392
13.4 Connected Component Labelling (CCL) . . . . . . . . . . . . . . . . . . . . . . . . . . 394
13.4.1 Random Access Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
13.4.2 Multiple Pass Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
13.4.3 Two-Pass Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
13.4.4 Parallel Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
13.4.5 Hysteresis Thresholding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
13.5 Connected Component Analysis (CCA) . . . . . . . . . . . . . . . . . . . . . . . . . . 398
13.5.1 Basic Single-Pass Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
13.5.2 Reducing Memory Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 399
13.5.3 Eliminating End-of-Row Overheads . . . . . . . . . . . . . . . . . . . . . . . . 399
13.5.4 Parallel Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401
13.5.5 Further Considerations and Optimisations . . . . . . . . . . . . . . . . . . . . . 401
13.6 Distance Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401
13.6.1 Morphological Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
13.6.2 Chamfer Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
13.6.3 Euclidean Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
13.6.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
13.6.5 Geodesic Distance Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
13.7 Watershed Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
13.7.1 Flow Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
13.7.2 Immersion Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
13.8 Hough Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
13.8.1 Line Hough Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
13.8.2 Circle Hough Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
13.8.3 Generalised Hough Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
13.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
13.10References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
14 Machine Learning 427
14.1 Training . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
14.1.1 Loss and Cost Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
14.1.2 Model Optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
14.1.3 Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
14.2 Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
14.2.1 Linear Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
14.2.2 Nonlinear Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
14.2.3 Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
14.3 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
14.3.1 Decision Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436
14.3.2 Random Forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436
14.3.3 Bayesian Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
14.3.4 Quadratic Discriminant Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 438
14.3.5 Linear Discriminant Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
14.3.6 Support Vector Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
14.3.7 Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441
14.3.8 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441
14.4 Deep Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
14.4.1 Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444
14.4.2 Architectures and Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
14.4.3 Training . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452
14.4.4 Implementation Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
14.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458
14.6 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
15 Example Applications 467
15.1 Coloured Region Tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
15.2 Foveal Sensor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
15.2.1 Foveal Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
15.2.2 Using the Sensor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
15.3 Real-Time Produce Grading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
15.3.1 Software Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
15.3.2 Hardware Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
15.4 Stereo Imaging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
15.4.1 Rectification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481
15.4.2 Calculating the Depth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
15.4.3 Stereo Matching Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
15.5 Face Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486
15.5.1 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487
15.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
15.7 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
Index 493
The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.
The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.