DESIGN FOR EMBEDDED
IMAGE PROCESSING
ON FPGAS
DESIGN FOR EMBEDDED
IMAGE PROCESSING
ON FPGAS
Donald G. Bailey
Massey University, New Zealand
This edition first published 2011
Ó 2011 John Wiley & Sons (Asia) Pte Ltd
Registered office
John Wiley & Sons (Asia) Pte Ltd, 1 Fusionopolis Walk, #07-01 Solaris South Tower, Singapore 138628
For details of our global editorial offices, for customer services and for information about how to apply for permission
to reuse the copyright material in this book please see our website at www.wiley.com.
All Rights Reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted, in any
form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as expressly
permitted by law, without either the prior written permission of the Publisher, or authorization through payment of the
appropriate photocopy fee to the Copyright Clearance Center. Requests for permission should be addressed to the
Publisher, John Wiley & Sons (Asia) Pte Ltd, 1 Fusionopolis Walk, #07-01 Solaris South Tower, Singapore 138628,
tel: 65-66438000, fax: 65-66438008, email: enquiry@wiley.com.
Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be
available in electronic books.
Designations used by companies to distinguish their products are often claimed as trademarks. All brand names and
product names used in this book are trade names, service marks, trademarks or registered trademarks of their respective
owners. The Publisher is not associated with any product or vendor mentioned in this book. This publication is
designed to provide accurate and authoritative information in regard to the subject matter covered. It is sold on the
understanding that the Publisher is not engaged in rendering professional services. If professional advice or other expert
assistance is required, the services of a competent professional should be sought.
Library of Congress Cataloging-in-Publication Data
Bailey, Donald G. (Donald Graeme), 1962-
Design for embedded image processing on FPGAs / Donald G. Bailey.
p. cm.
Includes bibliographical references and index.
ISBN 978-0-470-82849-6 (hardback)
1. Embedded computer systems. 2. Field programmable gate arrays. I. Title.
TK7895.E42B3264 2011
621.39’9 dc22
2011002991
Print ISBN: 978-0-470-82849-6
ePDF ISBN: 978-0-470-82850-2
oBook ISBN: 978-0-470-82851-9
ePub ISBN: 978-0-470-82852-6
Mobi ISBN: 978-1-118-07331-5
Set in 9/11 pt Times New Roman by Thomson Digital, Noida, India
Contents
Preface
Acknowledgements
1
Image Processing
1.1 Basic Definitions
Image Formation
1.2
1.3
Image Processing Operations
1.4 Example Application
1.5 Real-Time Image Processing
1.6 Embedded Image Processing
1.7 Serial Processing
1.8 Parallelism
1.9 Hardware Image Processing Systems
2 Field Programmable Gate Arrays
2.1 Programmable Logic
2.1.1 FPGAs vs. ASICs
2.2 FPGAs and Image Processing
2.3
Interconnect
Input and Output
Inside an FPGA
2.3.1 Logic
2.3.2
2.3.3
2.3.4 Clocking
2.3.5 Configuration
2.3.6 Power Consumption
2.4 FPGA Families and Features
2.4.1 Xilinx
2.4.2 Altera
2.4.3 Lattice Semiconductor
2.4.4 Achronix
2.4.5 SiliconBlue
2.4.6 Tabula
2.4.7 Actel
2.4.8 Atmel
xi
xvii
1
2
3
7
9
11
12
12
14
18
21
21
24
25
26
27
28
29
30
31
32
33
33
38
44
46
47
47
48
49
vi
Contents
QuickLogic
2.4.9
2.4.10 MathStar
2.4.11 Cypress
2.5 Choosing an FPGA or Development Board
3 Languages
3.1 Hardware Description Languages
3.2 Software-Based Languages
3.2.1 Structural Approaches
3.2.2 Augmented Languages
3.2.3 Native Compilation Techniques
3.3 Visual Languages
3.3.1 Behavioural
3.3.2 Dataflow
3.3.3 Hybrid
3.4 Summary
4 Design Process
4.1 Problem Specification
4.2 Algorithm Development
4.2.1 Algorithm Development Process
4.2.2 Algorithm Structure
4.2.3 FPGA Development Issues
4.3 Architecture Selection
4.3.1 System Level Architecture
4.3.2 Computational Architecture
4.3.3 Partitioning between Hardware and Software
4.4 System Implementation
4.4.1 Mapping to FPGA Resources
4.4.2 Algorithm Mapping Issues
4.4.3 Design Flow
4.5 Designing for Tuning and Debugging
4.5.1 Algorithm Tuning
4.5.2 System Debugging
5 Mapping Techniques
5.1 Timing Constraints
5.1.1 Low Level Pipelining
5.1.2 Process Synchronisation
5.1.3 Multiple Clock Domains
5.2 Memory Bandwidth Constraints
5.2.1 Memory Architectures
5.2.2 Caching
5.2.3 Row Buffering
5.2.4 Other Memory Structures
50
50
51
51
53
56
61
63
64
69
72
73
73
74
77
79
79
81
82
83
86
86
87
89
93
96
97
100
101
102
102
104
107
107
107
110
111
113
113
116
117
118
Contents
5.3 Resource Constraints
5.3.1 Resource Multiplexing
5.3.2 Resource Controllers
5.3.3 Reconfigurability
5.4 Computational Techniques
5.4.1 Number Systems
5.4.2 Lookup Tables
5.4.3 CORDIC
5.4.4 Approximations
5.4.5 Other Techniques
5.5 Summary
6 Point Operations
6.1 Point Operations on a Single Image
6.1.1 Contrast and Brightness Adjustment
6.1.2 Global Thresholding and Contouring
6.1.3 Lookup Table Implementation
6.2 Point Operations on Multiple Images
Image Averaging
Image Subtraction
Image Comparison
Intensity Scaling
6.2.1
6.2.2
6.2.3
6.2.4
6.2.5 Masking
6.3 Colour Image Processing
6.3.1 False Colouring
6.3.2 Colour Space Conversion
6.3.3 Colour Thresholding
6.3.4 Colour Correction
6.3.5 Colour Enhancement
6.4 Summary
7 Histogram Operations
7.1 Greyscale Histogram
7.1.1 Data Gathering
7.1.2 Histogram Equalisation
7.1.3 Automatic Exposure
7.1.4 Threshold Selection
7.1.5 Histogram Similarity
7.2 Multidimensional Histograms
7.2.1 Triangular Arrays
7.2.2 Multidimensional Statistics
7.2.3 Colour Segmentation
7.2.4 Colour Indexing
7.2.5 Texture Analysis
vii
122
122
125
130
132
132
138
142
150
152
154
155
155
155
159
162
163
164
166
170
171
173
175
175
176
192
193
197
197
199
199
201
206
210
211
219
219
220
222
226
229
231
viii
Contents
8 Local Filters
8.1 Caching
8.2 Linear Filters
8.2.1 Noise Smoothing
8.2.2 Edge Detection
8.2.3 Edge Enhancement
8.2.4 Linear Filter Techniques
8.3 Nonlinear Filters
8.3.1 Edge Orientation
8.3.2 Non-maximal Suppression
8.3.3 Zero-Crossing Detection
8.4 Rank Filters
8.4.1 Rank Filter Sorting Networks
8.4.2 Adaptive Histogram Equalisation
8.5 Colour Filters
8.6 Morphological Filters
8.6.1 Binary Morphology
8.6.2 Greyscale Morphology
8.6.3 Colour Morphology
8.7 Adaptive Thresholding
8.7.1 Error Diffusion
8.8 Summary
9 Geometric Transformations
9.1 Forward Mapping
9.1.1 Separable Mapping
9.2 Reverse Mapping
9.3
Interpolation
9.3.1 Bilinear Interpolation
9.3.2 Bicubic Interpolation
9.3.3 Splines
9.3.4
Interpolating Compressed Data
9.4 Mapping Optimisations
9.5
Image Registration
9.5.1 Feature-Based Methods
9.5.2 Area-Based Methods
9.5.3 Applications
10 Linear Transforms
10.1 Fourier Transform
10.1.1 Fast Fourier Transform
10.1.2 Filtering
10.1.3
Inverse Filtering
10.1.4
Interpolation
10.1.5 Registration
233
233
239
239
241
243
243
248
250
251
252
252
255
260
261
264
264
269
270
271
271
273
275
276
277
282
285
286
288
290
292
292
294
295
299
305
309
310
311
318
320
321
322