Digital Video Processing - Pearsoncmg
Digital Video ProcessingSecond Edition
This page intentionally left blank
Digital Video ProcessingSecond EditionA. Murat TekalpNew York Boston Indianapolis San FranciscoToronto Montreal London Munich Paris MadridCapetown Sydney Tokyo Singapore Mexico City
Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks.Where those designations appear in this book, and the publisher was aware of a trademark claim, the designationshave been printed with initial capital letters or in all capitals.The author and publisher have taken care in the preparation of this book, but make no expressed or impliedwarranty of any kind and assume no responsibility for errors or omissions. No liability is assumed for incidental orconsequential damages in connection with or arising out of the use of the information or programs contained herein.For information about buying this title in bulk quantities, or for special sales opportunities (which may includeelectronic versions; custom cover designs; and content particular to your business, training goals, marketing focus, orbranding interests), please contact our corporate sales department at corpsales@pearsoned.com or (800) 382-3419.For government sales inquiries, please contact governmentsales@pearsoned.com.For questions about sales outside the United States, please contact international@pearsoned.com.Visit us on the Web: informit.com/phLibrary of Congress Cataloging-in-Publication DataTekalp, A. Murat.Digital video processing / A. Murat Tekalp.—Second edition.pages cmIncludes bibliographical references and index.ISBN 978-0-13-399100-0 (hardcover : alk. paper)—ISBN 0-13-399100-8 (hardcover : alk. paper)1. Digital video—Textbooks. I. Title.TK6680.5.T45 2015621.388’33—dc232015007504Copyright 2015 Pearson Education, Inc.All rights reserved. Printed in the United States of America. This publication is protected by copyright, andpermission must be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system,or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. Toobtain permission to use material from this work, please submit a written request to Pearson Education, Inc.,Permissions Department, 200 Old Tappan Road, Old Tappan, New Jersey 07675, or you may fax your request to(201) 236-3290.ISBN-13: 978-0-13-399100-0ISBN-10: 0-13-399100-8Text printed in the United States on recycled paper at Courier in Westford, Massachusetts.First printing, June 2015
To Sevim and Kaya Tekalp, my mom and dad,To Özge, my beloved wife, andTo Engin Deniz, my son, and Derya Cansu, my daughter
This page intentionally left blank
ContentsPreface xviiAbout the Author xxv1 Multi-Dimensional Signals and Systems11.1Multi-Dimensional Signals 21.1.1 Finite-Extent Signals and Periodic Signals 21.1.2 Symmetric Signals 51.1.3 Special Multi-Dimensional Signals 51.2 Multi-Dimensional Transforms 81.2.1 Fourier Transform of Continuous Signals 81.2.2 Fourier Transform of Discrete Signals 121.2.3 Discrete Fourier Transform (DFT) 141.2.4 Discrete Cosine Transform (DCT) 181.3 Multi-Dimensional Systems 201.3.1 Impulse Response and 2D Convolution 201.3.2 Frequency Response 231.3.3 FIR Filters and Symmetry 251.3.4 IIR Filters and Partial Difference Equations 271.4 Multi-Dimensional Sampling Theory 301.4.1 Sampling on a Lattice 301.4.2 Spectrum of Signals Sampled on a Lattice 341.4.3 Nyquist Criterion for Sampling on a Lattice 36vii
Contentsviii 1.4.4 Reconstruction from Samples on a Lattice 411.5 Sampling Structure Conversion 42References 47Exercises 48Problem Set 1 48MATLAB Exercises 502 Digital Images and Video2.153Human Visual System and Color 542.1.1 Color Vision and Models 542.1.2 Contrast Sensitivity 572.1.3 Spatio-Temporal Frequency Response 592.1.4 Stereo/Depth Perception 622.2 Analog Video 632.2.1 Progressive vs. Interlaced Scanning 642.2.2 Analog-Video Signal Formats 652.2.3 Analog-to-Digital Conversion 662.3 Digital Video 672.3.1 Spatial Resolution and Frame Rate 672.3.2 Color, Dynamic Range, and Bit-Depth 692.3.3 Color Image Processing 712.3.4 Digital-Video Standards 742.4 3D Video 792.4.1 3D-Display Technologies 792.4.2 Stereoscopic Video 822.4.3 Multi-View Video 832.5 Digital-Video Applications 852.5.1 Digital TV 852.5.2 Digital Cinema 892.5.3 Video Streaming over the Internet 922.5.4 Computer Vision and Scene/Activity Understanding 952.6 Image and Video Quality 962.6.1 Visual Artifacts 962.6.2 Subjective Quality Assessment 972.6.3 Objective Quality Assessment 98References 100
Contents 3Image Filtering3.1ix105Image Smoothing 1063.1.1 Linear Shift-Invariant Low-Pass Filtering 1063.1.2 Bi-Lateral Filtering 1093.2 Image Re-Sampling and Multi-Resolution Representations 1103.2.1 Image Decimation 1113.2.2 Interpolation 1133.2.3 Multi-Resolution Pyramid Representations 1203.2.4 Wavelet Representations 1213.3 Image-Gradient Estimation, Edge and Feature Detection 1273.3.1 Estimation of the Image Gradient 1283.3.2 Estimation of the Laplacian 1323.3.3 Canny Edge Detection 1343.3.4 Harris Corner Detection 1353.4 Image Enhancement 1373.4.1 Pixel-Based Contrast Enhancement 1373.4.2 Spatial Filtering for Tone Mapping and Image Sharpening 1423.5 Image Denoising 1473.5.1 Image and Noise Models 1483.5.2 Linear Space-Invariant Filters in the DFT Domain 1503.5.3 Local Adaptive Filtering 1533.5.4 Nonlinear Filtering: Order-Statistics, Wavelet Shrinkage,and Bi-Lateral Filtering 1583.5.5 Non-Local Filtering: NL-Means and BM3D 1623.6 Image Restoration 1643.6.1 Blur Models 1653.6.2 Restoration of Images Degraded by Linear Space-InvariantBlurs 1693.6.3 Blind Restoration – Blur Identification 1753.6.4 Restoration of Images Degraded by Space-Varying Blurs 1773.6.5 Image In-Painting 180References 181Exercises 186Problem Set 3 186MATLAB Exercises 189MATLAB Resources 193
Contentsx 4Motion Estimation4.14.24.34.44.54.64.74.8195Image Formation 1964.1.1 Camera Models 1964.1.2 Photometric Effects of 3D Motion 201Motion Models 2024.2.1 Projected Motion vs. Apparent Motion 2034.2.2 Projected 3D Rigid-Motion Models 2074.2.3 2D Apparent-Motion Models 2102D Apparent-Motion Estimation 2144.3.1 Sparse Correspondence, Optical-Flow Estimation, andImage-Registration Problems 2144.3.2 Optical-Flow Equation and Normal Flow 2174.3.3 Displaced-Frame Difference 2194.3.4 Motion Estimation is Ill-Posed: Occlusion and ApertureProblems 2204.3.5 Hierarchical Motion Estimation 2234.3.6 Performance Measures for Motion Estimation 224Differential Methods 2254.4.1 Lukas–Kanade Method 2254.4.2 Horn–Schunk Motion Estimation 230Matching Methods 2334.5.1 Basic Block-Matching 2344.5.2 Variable-Size Block-Matching 2384.5.3 Hierarchical Block-Matching 2404.5.4 Generalized Block-Matching – Local Deformable Motion 2414.5.5 Homography Estimation from Feature Correspondences 243Nonlinear Optimization Methods 2454.6.1 Pel-Recursive Motion Estimation 2454.6.2 Bayesian Motion Estimation 247Transform-Domain Methods 2494.7.1 Phase-Correlation Method 2494.7.2 Space-Frequency Spectral Methods 2513D Motion and Structure Estimation 2514.8.1 Camera Calibration 2524.8.2 Affine Reconstruction 2534.8.3 Projective Reconstruction 2554.8.4 Euclidean Reconstruction 260
Contents xi4.8.5 Planar-Parallax and Relative Affine StructureReconstruction 2614.8.6 Dense Structure from Stereo 263References 263Exercises 268Problem Set 4 268MATLAB Exercises 270MATLAB Resources 2725 Video Segmentation and Tracking5.1273Image Segmentation 2755.1.1 Thresholding 2755.1.2 Clustering 2775.1.3 Bayesian Methods 2815.1.4 Graph-Based Methods 2855.1.5 Active-Contour Models 2875.2 Change Detection 2895.2.1 Shot-Boundary Detection 2895.2.2 Background Subtraction 2915.3 Motion Segmentation 2985.3.1 Dominant-Motion Segmentation 2995.3.2 Multiple-Motion Segmentation 3025.3.3 Region-Based Motion Segmentation: Fusion of Color andMotion 3115.3.4 Simultaneous Motion Estimation and Segmentation 3135.4 Motion Tracking 3175.4.1 Graph-Based Spatio-Temporal Segmentation and Tracking 3195.4.2 Kanade–Lucas–Tomasi Tracking 3195.4.3 Mean-Shift Tracking 3215.4.4 Particle-Filter Tracking 3235.4.5 Active-Contour Tracking 3255.4.6 2D-Mesh Tracking 3275.5 Image and Video Matting 3285.6 Performance Evaluation 330References 331MATLAB Exercises 338Internet Resources 339
Contentsxii 6 Video Filtering3416.1Theory of Spatio-Temporal Filtering 3426.1.1 Frequency Spectrum of Video 3426.1.2 Motion-Adaptive Filtering 3456.1.3 Motion-Compensated Filtering 3456.2 Video-Format Conversion 3496.2.1 Down-Conversion 3516.2.2 De-Interlacing 3556.2.3 Frame-Rate Conversion 3616.3 Multi-Frame Noise Filtering 3676.3.1 Motion-Adaptive Noise Filtering 3676.3.2 Motion-Compensated Noise Filtering 3696.4 Multi-Frame Restoration 3746.4.1 Multi-Frame Modeling 3756.4.2 Multi-Frame Wiener Restoration 3756.5 Multi-Frame Super-Resolution 3776.5.1 What Is Super-Resolution? 3786.5.2 Modeling Low-Resolution Sampling 3816.5.3 Super-Resolution in the Frequency Domain 3866.5.4 Multi-Frame Spatial-Domain Methods 389References 394Exercises 399Problem Set 6 399MATLAB Exercises 4007Image Compression4017.1Basics of Image Compression 4027.1.1 Information Theoretic Concepts 4027.1.2 Elements of Image-Compression Systems 4057.1.3 Quantization 4067.1.4 Symbol Coding 4097.1.5 Huffman Coding 4107.1.6 Arithmetic Coding 4147.2 Lossless Image Compression 4177.2.1 Bit-Plane Coding 4187.2.2 Run-Length Coding and ITU G3/G4 Standards7.2.3 Adaptive Arithmetic Coding and JBIG 423419
Contents xiii7.2.4 Early Lossless Predictive Coding 4247.2.5 JPEG-LS Standard 4267.2.6 Lempel–Ziv Coding 4307.3 Discrete-Cosine Transform Coding and JPEG 4317.3.1 Discrete-Cosine Transform 4327.3.2 ISO JPEG Standard 4347.3.3 Encoder Control and Compression Artifacts 4427.4 Wavelet-Transform Coding and JPEG2000 4437.4.1 Wavelet Transform and Choice of Filters 4437.4.2 ISO JPEG2000 Standard 448References 454Exercises 456Internet Resources 4598 Video Compression4618.1 Video-Compression Approaches 4628.1.1 Intra-Frame Compression, Motion JPEG 2000, andDigital Cinema 4628.1.2 3D-Transform Coding 4638.1.3 Motion-Compensated Transform Coding 4668.2 Early Video-Compression Standards 4678.2.1 ISO and ITU Standards 4678.2.2 MPEG-1 Standard 4688.2.3 MPEG-2 Standard 4768.3 MPEG-4 AVC/ITU-T H.264 Standard 4838.3.1 Input-Video Formats and Data Structure 4848.3.2 Intra-Prediction 4858.3.3 Motion Compensation 4868.3.4 Transform 4888.3.5 Other Tools and Improvements 4898.4 High-Efficiency Video-Coding (HEVC) Standard 4918.4.1 Video-Input Format and Data Structure 4918.4.2 Coding-Tree Units 4928.4.3 Tools for Parallel Encoding/Decoding 4938.4.4 Other Tools and Improvements 4958.5 Scalable-Video Compression 4978.5.1 Temporal Scalability 498
Contentsxiv 8.5.2 Spatial Scalability 4998.5.3 Quality (SNR) Scalability 5008.5.4 Hybrid Scalability 5028.6 Stereo and Multi-View Video Compression 5028.6.1 Frame-Compatible Stereo-Video Compression 5038.6.2 Stereo and Multi-View Video-Coding Extensions ofthe H.264/AVC Standard 5048.6.3 Multi-View Video Plus Depth Compression 507References 512Exercises 514Internet Resources 515A Vector-Matrix Operations in Image and Video Processing517A.1A.2Two-Dimensional Convolution 517Two-Dimensional Discrete-Fourier Transform 520A.2.1 Diagonalization of Block-Circulant Matrices 521A.3 Three-Dimensional Rotation – Rotation Matrix 521A.3.1 Euler Angles 522A.3.2 Rotation About an Arbitrary Axis 523A.3.3 Quaternion Representation 524References 525Exercises 525B Ill-Posed Problems in Image and Video Processing527B.1Image Representations 527B.1.1 Deterministic Framework – Function/Vector SpacesB.1.2 Bayesian Framework – Random Fields 528B.2 Overview of Image Models 528B.3 Basics of Sparse-Image Modeling 530B.4 Well-Posed Formulations of Ill-Posed Problems 531B.4.1 Constrained-Optimization Problem 531B.4.2 Bayesian-Estimation Problem 532References 532C Markov and Gibbs Random Fields527533C.1 Equivalence of Markov Random Fields and Gibbs Random Fields 533C.1.1 Markov Random Fields 534C.1.2 Gibbs Random Fields 535C.1.3 Equivalence of MRF and GRF 536
Contents xvC.2 Gibbs Distribution as an a priori PDF Model 537C.3 Computation of Local Conditional Probabilities from a GibbsDistribution 538References 539D Optimization Methods541D.1 Gradient-Based Optimization 542D.1.1 Steepest-Descent Method 542D.1.2 Newton–Raphson Method 543D.2 Simulated Annealing 544D.2.1 Metropolis Algorithm 545D.2.2 Gibbs Sampler 546D.3 Greedy Methods 547D.3.1 Iterated Conditional Modes 547D.3.2 Mean-Field Annealing 548D.3.3 Highest Confidence First 548References 549E Model Fitting 551E.1E.2Least-Squares Fitting 551Least-Squares Solution of Homogeneous Linear Equations 552E.2.1 Alternate Derivation 553E.3 Total Least-Squares Fitting 554E.4 Random-Sample Consensus (RANSAC) 556References 556Index 557
This page intentionally left blank
PrefaceThe first edition of this book (1995) was the first comprehensive textbook on digitalvideo processing. However, digital video technologies and video processing algorithms were not mature enough then. Digital TV standards were just being written,digital cinema was not even in consideration, and digital video cameras and DVDwere just entering the market. Hence, the first edition contained some now-outdatedmethods/algorithms and technologies compared with the state of the art today, andobviously missed important developments in the last 20 years. The first edition wasorganized into 25 smaller chapters on what were then conceived to be importanttopics in video processing, each intended to be covered in one or two lectures duringa one-semester course. Some methods covered in the first edition—e.g., pel-recursivemotion estimation, vector quantization, fractal compression, and model-basedcoding—no longer reflect the state of the art. Some technologies covered in the firstedition, such as analog video/TV and 128K videophone, are now obsolete.In the 20 years since the first edition, digital video has become ubiquitous in ourdaily lives in the digital age. Video processing algorithms have become more maturewith significant new advances made by signal processing and computer vision communities, and the most popular and successful techniques and algorithms for different tasks have become clearer. Hence, it is now the right time for an updated editionof the book. This book aims to fill the need for a comprehensive, rigorous, andtutorial-style textbook for digital image and video processing that covers the mostrecent state of the art in a well-balanced manner.This second edition significantly improves the organization of the materialand presentation style and updates the technical content with the most up-to-datetechniques, successful algorithms, and most recent knowledge in the field. It isxvii
xviii Prefaceorganized into eight comprehensive chapters, where each covers a major subject,including multi-dimensional signal processing, image/video basics, image filtering,motion estimation, video segmentation, video filtering, image compression, andvideo compression, with an emphasis on the most successful techniques in eachsubject area. Therefore, this is not an incremental revision—it is almost a completerewrite.The book is intended as a quantitative textbook for advanced undergraduateand graduate-level classes on digital image and video processing. It assumes familiarity with calculus, linear algebra, probability, and some basic digital signal processingconcepts. Readers with a computer science background who may not be familiarwith the fundamental signal processing concepts can skip Chapter 1 and still followthe remaining chapters reasonably well. Although the presentation is rigorous, it is ina tutorial style starting from fundamentals. Hence, it can also be used as a referencebook or for self-study by researchers and engineers in the industry or in academia.This book enables the reader to understand theoretical foundations of image and video processing methods,learn the most popular and successful algorithms to solve common image andvideo processing problems,reinforce their understanding by solving problems at the end of each chapter, andpractice methods by doing the MATLAB projects at the end of each chapter.Digital video processing refers to manipulation of the digital video bitstream.All digital video applications require compression. In addition, they may benefitfrom filtering for format conversion, enhancement, restoration, and super-resolution in order to obtain better-quality images or to extract specific information, andsome may require additional processing for motion estimation, video segmentation, and 3D scene analysis. What makes digital video processing different from stillimage processing is that video contains a significant amount of temporal correlation(redundancy) between the frames. One may attempt to process video as a sequenceof still images, where each frame is processed independently. However, multi-frameprocessing techniques using inter-frame correlations enable us to develop more effective algorithms, such as motion-compensated filtering and prediction. In addition,some tasks, such as motion estimation or the analysis of a time-varying scene, obviously cannot be performed on the basis of a single image.It is the goal of this book to provide the reader with the mathematical basis ofimage (single-frame) and video (multi-frame) processing methods. In particular, thisbook answers the following fundamental questions:
Preface xixHow do we separate images (signal) from noise?Is there a relationship between interpolation, restoration, and super-resolution?How do we estimate 2D and 3D motion for different applications?How do we segment images and video into regions of interest?How do we track objects in video?Is video filtering a better-posed problem than image filtering?What makes super-resolution possible?Can we obtain a high-quality still image from a video clip?What makes image and video compression possible?How do we compress images and video?What are the most recent international standards for image/video compression?What are the most recent standards for 3D video representation and compression?Most image and video processing problems are ill-posed (underdetermined and/or sensitive to noise) and their solutions rely on some sort of image and video models. Approaches to image modeling for solution of ill-posed problems are discussed inAppendix B. In particular, image models can be classified as those based on local smoothness,sparseness in a transform domain, andnon-local self-similarity.Most image processing algorithms employ one or more of these models. Videomodels use, in addition to the above, global or block translation motion,parametric motion,motion (spatial) smoothness,motion uniformity in time (temporal continuity or smoothness), andplanar support in 3D spatio-temporal frequency domain.An overview of the chapters follows.Chapter 1 reviews the basics of multi-dimensional signals, transforms, and systems, which form the theoretical basis of many image and video processing methods.We also address spatio-temporal sampling on MD lattices, which includes severalpractical sampling structures such as progressive and interlaced sampling, as wellas theory of sampling structure conversion. Readers with a computer science background who may not be familiar with signal processing concepts can skip this chapter and start with Chapter 2.
xx PrefaceChapter 2 aims to provide a basic understanding of digital image and videofundamentals. We cover the basic concepts of human vision, spatial frequency, colormodels, analog and digital video representations, digital video standards, 3D stereoand multi-view video representations, and evaluation of digital video quality. Weintroduce popular digital video applications, including dig
MATLAB Exercises 50 2 Digital Images and Video 53 . 2.2 Analog Video 63 2.2.1 Progressive vs. Interlaced Scanning 64 2.2.2 Analog-Video Signal Formats 65 2.2.3 Analog-to-Digital Conversion 66 2.3 Digital Video 67 2.3.1 Spatial Resolution and Frame Rate 67 2.3.2 Color, Dynamic Range, and Bit-Depth 69 2
Using Cross Products Video 1, Video 2 Determining Whether Two Quantities are Proportional Video 1, Video 2 Modeling Real Life Video 1, Video 2 5.4 Writing and Solving Proportions Solving Proportions Using Mental Math Video 1, Video 2 Solving Proportions Using Cross Products Video 1, Video 2 Writing and Solving a Proportion Video 1, Video 2
most of the digital signal processing concepts have benn well developed for a long time, digital signal processing is still a relatively new methodology. Many digital signal processing concepts were derived from the analog signal processing field, so you will find a lot o f similarities between the digital and analog signal processing.
How to edit the imported video on Mac Leawo Video onverter for Mac can also serve as a video editor to help users make a unique video. This page will tell the detailed steps of how to edit a video on mac. Five main video editing function will meet all your basic needs to edit a video. 1. Edit video on Mac . Import the file
viii Resources VIDEO Video 0.1 Alphabetic Principle xvi Video 0.2 Concept of Word in Print xviii Video 0.3 Importance of Organizing Phonics Information xix Video 0.4 Active Phonics Instruction xix Video 0.5 Phonics Strategies xix Video 0.6 Explanation of Temporary Spelling xx Video 0.7 Temporary Spelling xx Video 0.8 Why a One-Size-Fits-All Approach Is Less Effective in Kindergarten xxii
Creating a Video quiz is very simple. First you'll need a video that you want to create the quiz in. Don't worry; creating the Video Quiz will not change the video itself! Making a video Quiz will actually make a copy of the video in your My Media area. (A "Chapter 1 Overview" video, for example, would have a duplicate video titled .
Digital image processing is the use of computer algorithms to perform image processing on digital images. As a subfield of digital signal processing, digital image processing has many advantages over analog image processing; it allows a much wider range of algorithms to be applied to the in
Digital video camera, with as many manual setting options as possible (e.g. manual focus, exposure/aperture, shutter speed control) Winkler, Introduction to the Digital Video Camera, p. 2 Introduction to the Digital Video Camera The following is a collection of some features of a digital video camera. Since accessing
Korean also has a formality system built into the language. That is, the way one speaks to an older person who deserves high respect would be different than the way one speaks to a friend. There are many ways words in a sentence can change depending on the formality of the situation, but the two most common, basic and important things to be aware of are: 1) There are two ways to say “I” or .
