Khalid Sayood Ph.D. - Introduction to Data Compression (The Morgan Kaufmann Series in Multimedia Information and Systems)

Fifth edition

Khalid Sayood

1. Tables in Chapter 1
2. Tables in Chapter 2
3. Tables in Chapter 3
4. Tables in Chapter 4
5. Tables in Chapter 5
6. Tables in Chapter 6
7. Tables in Chapter 7
8. Tables in Chapter 9
9. Tables in Chapter 10
10. Tables in Chapter 11
11. Tables in Chapter 12
12. Tables in Chapter 13
13. Tables in Chapter 14
14. Tables in Chapter 15
15. Tables in Chapter 16
16. Tables in Chapter 17
17. Tables in Chapter 18
18. Tables in Chapter 19

1. Figures in Chapter 1
2. Figures in Chapter 2
3. Figures in Chapter 3
4. Figures in Chapter 4
5. Figures in Chapter 5
6. Figures in Chapter 6
7. Figures in Chapter 7
8. Figures in Chapter 8
9. Figures in Chapter 9
10. Figures in Chapter 10
11. Figures in Chapter 11
12. Figures in Chapter 12
13. Figures in Chapter 13
14. Figures in Chapter 14
15. Figures in Chapter 15
16. Figures in Chapter 16
17. Figures in Chapter 17
18. Figures in Chapter 18
19. Figures in Chapter 19
20. Figures in Appendix C

Morgan Kaufmann is an imprint of Elsevier

50 Hampshire Street, 5th Floor, Cambridge, MA 02139, United States

Copyright 2018 Elsevier Inc. All rights reserved.

No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or any information storage and retrieval system, without permission in writing from the publisher. Details on how to seek permission, further information about the Publisher's permissions policies and our arrangements with organizations such as the Copyright Clearance Center and the Copyright Licensing Agency, can be found at our website: www.elsevier.com/permissions.

This book and the individual contributions contained in it are protected under copyright by the Publisher (other than as may be noted herein).

Notices

Knowledge and best practice in this field are constantly changing. As new research and experience broaden our understanding, changes in research methods, professional practices, or medical treatment may become necessary.

Practitioners and researchers must always rely on their own experience and knowledge in evaluating and using any information, methods, compounds, or experiments described herein. In using such information or methods they should be mindful of their own safety and the safety of others, including parties for whom they have a professional responsibility.

To the fullest extent of the law, neither the Publisher nor the authors, contributors, or editors, assume any liability for any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods, products, instructions, or ideas contained in the material herein.

Library of Congress Cataloging-in-Publication Data

A catalog record for this book is available from the Library of Congress

British Library Cataloguing-in-Publication Data

A catalogue record for this book is available from the British Library

ISBN: 978-0-12-809474-7

For information on all Morgan Kaufmann publications visit our website at https://www.elsevier.com/books-and-journals

Publisher: Katey Birtcher

Acquisition Editor: Steve Merken

Editorial Project Manager: Peter Jardim

Production Project Manager: Punithavathy Govindaradjane

Designer: Matthew Limbert

Typeset by VTeX

To Fsun

Data compression has been an enabling technology for the information revolution. As this revolution has changed our lives, data compression has become a more and more ubiquitous, if often invisible, presence. From smartphones, to digital television and movies, data compression is an integral part of information technology and of our lives. This incorporation of compression into more and more of our lives also points to a certain degree of maturation and stability of the technology. This maturity is reflected in the fact that there are fewer differences between each edition of this book. In the second edition we had added new techniques that had been developed since the first edition of this book came out. In the third edition we added a chapter on audio compression, a topic that had not been adequately covered in the second edition. The fourth edition expanded the coverage of wavelets. In this edition we have added details of standards that have come out since the last edition such as High Efficiency Video Coding and new standards from the JPEG committee. We have added a description of Grammar based codes which might become more important in the coming years and as always we have filled in details left out from the previous editions. I have also indulged my latest interests by including a few applications of data compression algorithms to bioinformatics.

Though the percentage growth of this edition is less than that of previous editions it is still growth and it has yet again enlarged the book. Despite its expanded coverage, the intent remains the same: to provide an introduction to the art or science of data compression. There is a tutorial description of most of the popular compression techniques followed by a description of how these techniques are used for image, speech, text, audio, and video compression. We have attempted to make the chapters on techniques as self contained as possible. This is of course not completely possible for the application chapters which rely on multiple techniques presented in previous chapters, but here too we have tried to make sure that the dependence does not interrupt the explanation. One hopes the size of the book will not be intimidating and once you open the book and begin reading a particular section we hope you will find the content easily accessible. If some material is not clear please write to me at with specific questions and I will try and help (homework problems and projects are of course your responsibility).

If you are designing hardware or software implementations of compression algorithms, or need to interact with individuals engaged in such design, or are involved in development of multimedia applications and have some background in either electrical or computer engineering, or computer science, this book should be useful to you. We have included a large number of examples to aid in self-study. We have also included discussion of various multimedia standards. The intent here is not to provide all the details that may be required to implement a standard but to provide information that will help you follow and understand the standards documents. The final authority is always the standards document.

The impetus for writing this book came from the need for a self-contained book that could be used at the senior/graduate level for a course in data compression in either electrical engineering, computer engineering, or computer science departments. There are problems and project ideas after most of the chapters. A solutions manual is available from the publisher. Also at http://datacompression.unl.edu we provide links to various course homepages, which can be a valuable source of project ideas and support material.