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?
