W641-Blanchet.qxp_Layout 1 29/12/2014 17:06 Page 1 DIGITAL SIGNAL AND IMAGE PROCESSING SERIES Volume 2 of the second edition of the fully revised and updated M G a é Digital Signal and Image Processing using MATLAB® is u ra essentially a collection of examples and exercises which also ric rd e B presents applications of digital signal- or image processing, and C l a h n techniques which were not touched upon in the previous volume. a c rb h It will be of particular benefit to readers who already possess a i e t t good knowledge of MATLAB®, a command of the fundamental elements of digital signal processing and who are familiar with both the fundamentals of continuous-spectrum spectral analysis and who have a certain mathematical knowledge concerning Hilbert spaces. D More than 200 programs and functions are provided in the i g MATLAB® language, with useful comments and guidance, to i t enable numerical experiments to be carried out, thus allowing a l readers to develop a deeper understanding of both the S theoretical and practical aspects of this subject. i g Digital Signal u n s a i n l and Image Processing g a n M d Gérard Blanchet is Professor at Ecole Nationale Supérieure des A I using MATLAB® Télécommunications, Paris, France. In addition to his research, m T teaching and consulting activities, he is the author of several L a books on automatic control systems, digital signal processing A g and computer architecture. He also develops tools and B e 2nd Edition Revised and Updated methodologies to improve knowledge acquisition in various ® P fields. r o Volume 2 – Advances and Applications c Maurice Charbit is Professor at Ecole Nationale Supérieure des e Télécommunications, Paris, France, where he teaches several The Deterministic Case s courses in signal processing and digital communications. His s i research interests include statistics, speech and image n g processing. Gérard Blanchet and Maurice Charbit Z(7ib8e8-CBGEBJ( www.iste.co.uk Digital Signal and Image Processing using MATLAB® nd Revised and Updated 2 Edition Digital Signal and Image ® Processing using MATLAB Volume 2 Advances and Applications: The Deterministic Case Gérard Blanchet Maurice Charbit First published 2015 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc. Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address: ISTE Ltd John Wiley & Sons, Inc. 27-37 St George’s Road 111 River Street London SW19 4EU Hoboken, NJ 07030 UK USA www.iste.co.uk www.wiley.com © ISTE Ltd 2015 The rights of Gérard Blanchet and Maurice Charbit to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988. Library of Congress Control Number: 2014958256 British Library Cataloguing-in-Publication Data A CIP record for this book is available from the British Library ISBN 978-1-84821-641-9 MATLAB®is a trademark of The MathWorks, Inc. and is used with permission. The MathWorks does not warrant the accuracy of the text or exercises in this book. This book’s use or discussion of MATLAB® software does not constitute endorsement or sponsorship by The MathWorks of a particular pedagogical approach or use of the MATLAB® software. Contents Foreword ix Notations and Abbreviations xi Chapter 1 Recap on Digital Signal Processing 1 1.1 The sampling theorem . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Spectral contents . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.1 Discrete-time Fourier transform (DTFT). . . . . . . . . 7 1.2.2 Discrete Fourier transform (DFT) . . . . . . . . . . . . 8 1.3 Case of random signals . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 Example of the Dual Tone Multi-Frequency (DTMF) . . . . . . 11 Chapter 2 Additional Information About Filtering 15 2.1 Filter implementation . . . . . . . . . . . . . . . . . . . . . . . 15 2.1.1 Examples of filter structures. . . . . . . . . . . . . . . . 16 2.1.2 Distributing the calculation load in an FIR filter . . . . 20 2.1.3 FIR block filtering . . . . . . . . . . . . . . . . . . . . . 21 2.1.4 FFT filtering . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2 Filter banks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.1 Decimation and expansion . . . . . . . . . . . . . . . . . 30 2.2.2 Filter banks . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3 Ripple control . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.3.1 Principle . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.3.2 Programming . . . . . . . . . . . . . . . . . . . . . . . . 44 Chapter 3 Image Processing 51 3.1 A little geometry . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.1.1 3D object . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.1.2 Calibration of cameras . . . . . . . . . . . . . . . . . . . 53 3.2 Pyramidal decompositions . . . . . . . . . . . . . . . . . . . . . 62 3.2.1 Pyramidal decomposition given by Burt and Adelson . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 vi Digital Signal and Image Processing using MATLAB® 3.2.2 Pyramidal decomposition using a Haar tranformation . 65 3.2.3 Stepwise decomposition (lifting scheme) . . . . . . . . . 66 Chapter 4 Numerical Calculus and Simulation 71 4.1 Simulation of continuous-time systems . . . . . . . . . . . . . . 71 4.1.1 Simulation by approximation . . . . . . . . . . . . . . . 71 4.1.2 Exact model simulation . . . . . . . . . . . . . . . . . . 72 4.2 Solving of ordinary differential equations (ODEs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.2.1 Conversion from continuous to discrete time . . . . . . . 76 4.2.2 Linear case, continuous-time solution . . . . . . . . . . . 78 4.2.3 Remarks on the Runge–Kutta methods . . . . . . . . . 81 4.3 Systems of equations and zero-seeking . . . . . . . . . . . . . . 88 4.3.1 Zeros of a function using the Newton method . . . . . . 88 4.3.2 Roots of a polynomial with the Newton–Raphson method 89 4.3.3 Systems of nonlinear equations . . . . . . . . . . . . . . 90 4.4 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 4.4.1 Thiele’s interpolation . . . . . . . . . . . . . . . . . . . 92 4.4.2 Another decomposition in continuous fractions . . . . . 95 4.4.3 Natural cubic splines . . . . . . . . . . . . . . . . . . . . 96 4.5 Solving of linear systems . . . . . . . . . . . . . . . . . . . . . . 100 4.5.1 Jacobi method . . . . . . . . . . . . . . . . . . . . . . . 100 4.5.2 Relaxation method . . . . . . . . . . . . . . . . . . . . . 101 4.5.3 Cholesky factorization . . . . . . . . . . . . . . . . . . . 102 Chapter 5 Speech Processing 105 5.1 A speech signal model . . . . . . . . . . . . . . . . . . . . . . . 105 5.1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 105 5.1.2 A typology of vocal sounds . . . . . . . . . . . . . . . . 106 5.1.3 The AR model of speech production . . . . . . . . . . . 107 5.1.4 Compressing a speech signal. . . . . . . . . . . . . . . . 113 5.2 Dynamic Time Warping . . . . . . . . . . . . . . . . . . . . . . 116 5.2.1 The DTW algorithm . . . . . . . . . . . . . . . . . . . . 117 5.2.2 Examples of pathfinding rules . . . . . . . . . . . . . . . 118 5.2.3 Cepstral coefficients . . . . . . . . . . . . . . . . . . . . 119 5.3 Modifying the duration of an audio signal . . . . . . . . . . . . 120 5.3.1 PSOLA . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.3.2 Phase vocoder . . . . . . . . . . . . . . . . . . . . . . . 123 5.4 Eliminating the impulse noise . . . . . . . . . . . . . . . . . . . 124 5.4.1 The signal model . . . . . . . . . . . . . . . . . . . . . . 125 5.4.2 Click detection . . . . . . . . . . . . . . . . . . . . . . . 126 5.4.3 Restoration . . . . . . . . . . . . . . . . . . . . . . . . . 128 Contents vii Chapter 6 Selected Topics 131 6.1 Tracking the cardiac rhythm of the fetus . . . . . . . . . . . . . 131 6.1.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.1.2 Separating the EKG signals . . . . . . . . . . . . . . . . 132 6.1.3 Estimating cardiac rhythms . . . . . . . . . . . . . . . . 136 6.2 Extracting the contour of a coin . . . . . . . . . . . . . . . . . 142 6.3 Constrained optimization and Lagrange multipliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 6.3.1 Equality-constrained optimization . . . . . . . . . . . . 146 6.3.2 Quadratic problem with linear inequality constraints . . 149 6.3.3 Portfolio optimization . . . . . . . . . . . . . . . . . . . 153 6.4 Principal Component Analysis (PCA) . . . . . . . . . . . . . . 163 6.4.1 Determining the principal components . . . . . . . . . . 164 6.4.2 2-Dimension PCA . . . . . . . . . . . . . . . . . . . . . 168 6.4.3 Linear Discriminant Analysis . . . . . . . . . . . . . . . 170 6.5 GPS positioning . . . . . . . . . . . . . . . . . . . . . . . . . . 175 6.6 The Viterbi algorithm . . . . . . . . . . . . . . . . . . . . . . . 178 6.6.1 Convolutional non-recursive encoder . . . . . . . . . . . 179 6.6.2 Decoding and hard decision . . . . . . . . . . . . . . . . 181 Chapter 7 Hints and Solutions 187 H1 Reminders on digital signal-processing . . . . . . . . . . . . . . 187 H2 Additional information on filtering . . . . . . . . . . . . . . . . 189 H3 Image Processing . . . . . . . . . . . . . . . . . . . . . . . . . . 194 H4 Numerical calculus . . . . . . . . . . . . . . . . . . . . . . . . . 197 H5 Speech processing . . . . . . . . . . . . . . . . . . . . . . . . . . 215 H6 Selected topics . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 Chapter 8 Appendix 243 A1 A few properties of a matrix . . . . . . . . . . . . . . . . . . . . 243 A2 A few relations for matrices . . . . . . . . . . . . . . . . . . . . 246 Bibliography 247 Index 251