Image Processing: The Fundamentals
Image Processing: The Fundamentals, Second Edition Maria Petrou and Costas Petrou
© 2010JohnWiley&Sons,Ltd. ISBN: 978-0-470-74586-1
Image Processing: The Fundamentals
Maria Petrou
Costas Petrou
A John Wiley and Sons, Ltd., Publication
This edition first published 2010
c 2010 John Wiley & Sons Ltd
Registered office
John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, United Kingdom
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.
The right of the author to be identified as the author of this work has been asserted in accordance with the
Copyright, Designs and Patents Act 1988.
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 or otherwise,
except as permitted by the UK Copyright, Designs and Patents Act 1988, without the prior permission of
the publisher.
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
Petrou, Maria.
Image processing : the fundamentals / Maria Petrou, Costas Petrou. – 2nd ed.
p. cm.
Includes bibliographical references and index.
ISBN 978-0-470-74586-1 (cloth)
1. Image processing – Digital techniques.
TA1637.P48 2010
621.36
7 – dc22
ISBN 978-0-470-74586-1
A catalogue record for this book is available from the British Library.
Set in 10/12 Computer Modern by Laserwords Private Ltd, Chennai, India.
Printed in Singapore by Markono
2009053150
This book is dedicated to our mother and grandmother
Dionisia, for all her love and sacrifices.
Contents
Preface
xxiii
1 Introduction
than one sensor type corresponding to the same patch of the scene?
Why do we process images? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
What is an image? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
What is a digital image? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
What is a spectral band? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Why do most image processing algorithms refer to grey images, while most images
we come across are colour images? . . . . . . . . . . . . . . . . . . . . . . . .
How is a digital image formed? . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
If a sensor corresponds to a patch in the physical world, how come we can have more
. . . . .
What is the physical meaning of the brightness of an image at a pixel position? . .
Why are images often quoted as being 512 × 512, 256 × 256, 128 × 128 etc? . . . .
How many bits do we need to store an image? . . . . . . . . . . . . . . . . . . . . .
What determines the quality of an image? . . . . . . . . . . . . . . . . . . . . . . .
What makes an image blurred? . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
What is meant by image resolution? . . . . . . . . . . . . . . . . . . . . . . . . . .
What does “good contrast” mean? . . . . . . . . . . . . . . . . . . . . . . . . . . .
What is the purpose of image processing? . . . . . . . . . . . . . . . . . . . . . . .
How do we do image processing? . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Do we use nonlinear operators in image processing?
. . . . . . . . . . . . . . . . .
What is a linear operator? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
How are linear operators defined? . . . . . . . . . . . . . . . . . . . . . . . . . . . .
What is the relationship between the point spread function of an imaging device
and that of a linear operator? . . . . . . . . . . . . . . . . . . . . . . . . . . .
How does a linear operator transform an image? . . . . . . . . . . . . . . . . . . .
What is the meaning of the point spread function? . . . . . . . . . . . . . . . . . .
Box 1.1. The formal definition of a point source in the continuous domain . . . . .
How can we express in practice the effect of a linear operator on an image? . . . .
Can we apply more than one linear operators to an image? . . . . . . . . . . . . .
Does the order by which we apply the linear operators make any difference to the
result? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Box 1.2. Since matrix multiplication is not commutative, how come we can change
the order by which we apply shift invariant linear operators? . . . . . . . . .
1
1
1
1
2
2
3
3
3
6
6
7
7
7
10
11
11
12
12
12
12
12
13
14
18
22
22
22
vii
viii
Contents
Box 1.3. What is the stacking operator? . . . . . . . . . . . . . . . . . . . . . . . .
29
What is the implication of the separability assumption on the structure of matrix H? 38
39
How can a separable transform be written in matrix form?
. . . . . . . . . . . . .
40
What is the meaning of the separability assumption? . . . . . . . . . . . . . . . . .
Box 1.4. The formal derivation of the separable matrix equation . . . . . . . . . .
41
43
What is the “take home” message of this chapter? . . . . . . . . . . . . . . . . . .
43
What is the significance of equation (1.108) in linear image processing?
. . . . . .
What is this book about? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
2 Image Transformations
47
47
47
47
47
49
50
50
50
What is this chapter about? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
How can we define an elementary image?
. . . . . . . . . . . . . . . . . . . . . . .
What is the outer product of two vectors? . . . . . . . . . . . . . . . . . . . . . . .
How can we expand an image in terms of vector outer products? . . . . . . . . . .
How do we choose matrices hc and hr? . . . . . . . . . . . . . . . . . . . . . . . . .
What is a unitary matrix? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
What is the inverse of a unitary transform? . . . . . . . . . . . . . . . . . . . . . .
How can we construct a unitary matrix? . . . . . . . . . . . . . . . . . . . . . . . .
How should we choose matrices U and V so that g can be represented by fewer bits
50
than f? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
What is matrix diagonalisation?
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
Can we diagonalise any matrix? . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
2.1 Singular value decomposition . . . . . . . . . . . . . . . . . . . . . . . . .
51
How can we diagonalise an image? . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
Box 2.1. Can we expand in vector outer products any image? . . . . . . . . . . . .
How can we compute matrices U, V and Λ 1
56
2 needed for image diagonalisation? . .
Box 2.2. What happens if the eigenvalues of matrix ggT are negative? . . . . . . .
56
60
What is the singular value decomposition of an image? . . . . . . . . . . . . . . . .
61
Can we analyse an eigenimage into eigenimages? . . . . . . . . . . . . . . . . . . .
62
How can we approximate an image using SVD? . . . . . . . . . . . . . . . . . . . .
62
Box 2.3. What is the intuitive explanation of SVD?
. . . . . . . . . . . . . . . . .
63
What is the error of the approximation of an image by SVD? . . . . . . . . . . . .
How can we minimise the error of the reconstruction? . . . . . . . . . . . . . . . .
65
Are there any sets of elementary images in terms of which any image may be expanded? 72
What is a complete and orthonormal set of functions? . . . . . . . . . . . . . . . .
72
73
Are there any complete sets of orthonormal discrete valued functions? . . . . . . .
74
2.2 Haar, Walsh and Hadamard transforms . . . . . . . . . . . . . . . . . .
74
How are the Haar functions defined? . . . . . . . . . . . . . . . . . . . . . . . . . .
How are the Walsh functions defined? . . . . . . . . . . . . . . . . . . . . . . . . .
74
74
Box 2.4. Definition of Walsh functions in terms of the Rademacher functions
. . .
How can we use the Haar or Walsh functions to create image bases? . . . . . . . .
75
How can we create the image transformation matrices from the Haar and Walsh
functions in practice? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
What do the elementary images of the Haar transform look like? . . . . . . . . . .
Can we define an orthogonal matrix with entries only +1 or −1? . . . . . . . . . .
Box 2.5. Ways of ordering the Walsh functions
. . . . . . . . . . . . . . . . . . . .
What do the basis images of the Hadamard/Walsh transform look like? . . . . . .
76
80
85
86
88
Contents
What are the advantages and disadvantages of the Walsh and the Haar transforms?
What is the Haar wavelet? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Discrete Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . .
What is the discrete version of the Fourier transform (DFT)? . . . . . . . . . . . .
Box 2.6. What is the inverse discrete Fourier transform? . . . . . . . . . . . . . . .
How can we write the discrete Fourier transform in a matrix form? . . . . . . . . .
Is matrix U used for DFT unitary? . . . . . . . . . . . . . . . . . . . . . . . . . . .
Which are the elementary images in terms of which DFT expands an image? . . .
Why is the discrete Fourier transform more commonly used than the other
transforms? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
What does the convolution theorem state? . . . . . . . . . . . . . . . . . . . . . . .
Box 2.7. If a function is the convolution of two other functions, what is the rela-
tionship of its DFT with the DFTs of the two functions? . . . . . . . . . . . .
How can we display the discrete Fourier transform of an image? . . . . . . . . . . .
What happens to the discrete Fourier transform of an image if the image
is rotated? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
What happens to the discrete Fourier transform of an image if the image
is shifted? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
What is the relationship between the average value of the image and its DFT? . .
What happens to the DFT of an image if the image is scaled? . . . . . . . . . . . .
Box 2.8. What is the Fast Fourier Transform? . . . . . . . . . . . . . . . . . . . . .
What are the advantages and disadvantages of DFT? . . . . . . . . . . . . . . . . .
Can we have a real valued DFT? . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Can we have a purely imaginary DFT? . . . . . . . . . . . . . . . . . . . . . . . . .
Can an image have a purely real or a purely imaginary valued DFT? . . . . . . . .
2.4 The even symmetric discrete cosine transform (EDCT) . . . . . . . .
What is the even symmetric discrete cosine transform? . . . . . . . . . . . . . . . .
Box 2.9. Derivation of the inverse 1D even discrete cosine transform . . . . . . . .
What is the inverse 2D even cosine transform? . . . . . . . . . . . . . . . . . . . .
What are the basis images in terms of which the even cosine transform expands an
image? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5 The odd symmetric discrete cosine transform (ODCT) . . . . . . . .
What is the odd symmetric discrete cosine transform? . . . . . . . . . . . . . . . .
Box 2.10. Derivation of the inverse 1D odd discrete cosine transform . . . . . . . .
What is the inverse 2D odd discrete cosine transform? . . . . . . . . . . . . . . . .
What are the basis images in terms of which the odd discrete cosine transform
expands an image? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6 The even antisymmetric discrete sine transform (EDST) . . . . . . .
What is the even antisymmetric discrete sine transform? . . . . . . . . . . . . . . .
Box 2.11. Derivation of the inverse 1D even discrete sine transform . . . . . . . . .
What is the inverse 2D even sine transform? . . . . . . . . . . . . . . . . . . . . . .
What are the basis images in terms of which the even sine transform expands an
image? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
What happens if we do not remove the mean of the image before we compute its
EDST? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . .
2.7 The odd antisymmetric discrete sine transform (ODST)
What is the odd antisymmetric discrete sine transform? . . . . . . . . . . . . . . .
ix
92
93
94
94
95
96
99
101
105
105
105
112
113
114
118
119
124
126
126
130
137
138
138
143
145
146
149
149
152
154
154
157
157
160
162
163
166
167
167