数字视频处理（英文版）

Contents

Preface

About the Author

About the Notation

REPRESENTATION OF DIGITAL VIDEO

1 BASICS OF VIDEO

1.1 Analog Video

1.1.1 Analog Video Signal

1.1.2 Analog Video Standards

1.1.3 Analog Video Equipment

1.2 Digital Video

1.2.1 Digital Video Signal

1.2.2 Digital Video Standards

1.2.3 Why Digital Video?

1.3 Digital Video Processing

2 TIME-VARYING IMAGE FORMATION MODELS

2.1 Three-Dimensional Motion Models

2.1.1 Rigid Motion in the Cartesian Coordinates

2.1.2 Rigid Motion in the Homogeneous Coordinates

2.1.3 Deformable Motion

2.2 Geometric Image Formation

2.2.1 Perspective Projection

2.2.2 Orthographic Projection

2.3 Photometric Image Formation

2.3.1 Lambertian Reflectance Model

2.3.2 Photometric Effects of 3-D Motion

2.4 Observation Noise

2.5 Exercises

3 SPATIO-TEMPORAL SAMPLING

3.1 Sampling for Analog and Digital Video

3.1.1 Sampling Structures for Analog Video

3.1.2 Sampling Structures for Digital Video

3.2 Two-Dimensional Rectangular Sampling

3.2.1 2-D Fourier Transform Relations

3.2.2 Spectrum of the Sampled Signal

3.3 Two-Dimensional Periodic Sampling

3.3.1 Sampling Geometry

3.3.2 2-D Fourier Transform Relations in Vector Form

3.3.3 Spectrum of the Sampled Signal

3.4 Sampling on 3-D Structures

3.4.1 Sampling on a Lattice

3.4.2 Fourier Transform on a Lattice

3.4.3 Spectrum of Signals Sampled on a Lattice

3.4.4 Other Sampling Structures

3.5 Reconstruction from Samples

3.5.1 Reconstruction from Rectangular Samples

3.5.2 Reconstruction from Samples on a Lattice

3.6 Exercises

4 SAMPLING STRUCTURE CONVERSION

4.1 Sampling Rate Change for l-D Signals

4.1.1 Interpolation of l-D Signals

4.1.2 Decimation of l-D Signals

4.1.3 Sampling Rate Change by a Rational Factor

4.2 Sampling Lattice Conversion

4.3 Exercises

5 TWO-DIMENSIONAL MOTION ESTIMATION

OPTICAL FLOW METHODS

5.1 2-D Motion vs. Apparent Motion

5.1.1 2-D Motion

5.1.2 Correspondence and Optical Flow

5.2 2-D Motion Estimation

5.2.1 The Occlusion Problem

5.2.2 The Aperture Problem

5.2.3 Two-Dimensional Motion Field Models

5.3 Methods Using the Optical Flow Equation

5.3.1 The Optical Flow Equation

5.3.2 Second-Order Differential Methods

5.3.3 Block Motion Model

5.3.4 Horn and Schunck Method

5.3.5 Estimation of the Gradients

5.3.6 Adaptive Methods

5.4 Examples

5.5 Exercises

6 BLOCK-BASED METHODS

6.1 Block-Motion Models

6.1.1 Translational Block Motion

6.1.2 Generalized/Deformable Block Motion

6.2 Phase-Correlation Method

6.2.1 The Phase-Correlation Function

6.2.2 Implementation Issues

6.3 Block-Matching Method

6.3.1 Matching Criteria

6.3.2 Search Procedures

6.4 Hierarchical Motion Estimation

6.5 Generalized Block-Motion Estimation

6.5.1 Postprocessing for Improved Motion Compensation

6.5.2 Deformable Block Matching

6.6 Examples

6.7 Exercises

7 PEL-RECURSIVE METHODS

7.1 Displaced Frame Difference

7.2 Gradient-Based Optimization

7.2.1 Steepest-Descent Method

7.2.2 Newton-Raphson Method

7.2.3 Local vs. Global Minima

7.3 Steepest-Descent-Based Algorithms

7.3.1 Netravali-Robbins Algorithm

7.3.2 Walker-Rao Algorithm

7.3.3 Extension to the Block Motion Model

7.4 Wiener-Estimation-Based Algorithms

7.5 Examples

7.6 Exercises

8 BAYESIAN METHODS

8.1 Optimization Methods

8.1.1 Simulated Annealing

8.1.2 Iterated Conditional Modes

8.1.3 Mean Field Annealing

8.1.4 Highest Confidence First

8.2 Basics of MAP Motion Estimation

8.2.1 The Likelihood Model

8.2.2 The Prior Model

8.3 MAP Motion Estimation Algorithms

8.3.1 Formulation with Discontinuity Model,

8.3.2 Estimation with Local Outlier Rejection

8.3.3 Estimation with Region Labeling

8.4 Examples

8.5 Exercises

III THREE-DIMENSIONAL MOTION ESTIMATION

AND SEGMENTATION

9 METHODS USING POINT CORRESPONDENCES

9.1 Modeling the Projected Displacement Field

9.1.1 Orthographic Displacement Field Model

9.1.2 Perspective Displacement Field Model

9.2 Methods Based on the Orthographic Model

9.2.1 Two-Step Iteration Method from Two Views

9.2.2 An Improved Iterative Method

9.3 Methods Based on the Perspective Model

9.3.1 The Epipolar Constraint and Essential Parameters

9.3.2 Estimation ofthe Essential Pararneters

9.3.3 Decomposition of the E-Matrix

9.3.4 Algorithm

9.4 The Case of 3-D Planar Surfaces

9.4.1 The Pure Parameters

9.4.2 Estimation ofthe Pure Parameters

9.4.3 Estimation ofthe Motion and Structure Parameters

9.5 Examples

9.5.1 Numerical Simulations

9.5.2 Experiments with Two Frames of Miss America

9.6 Exercises

10 OPTICAL FLOW AND DIRECT METHODS

10.1 Modeling the Projected Velocity Field

10.1.1 Orthographic Velocity Field Model

10.1.2 Perspective Velocity Field Model

10.1.3 Perspective Velocity vs. Displacement Models

10.2 Focus of Expansion

10.3 Algebraic Methods Using Optical Flow

10.3.1 Uniqueness of the Solution

10.3.2 Affine Flow

10.3.3 Quadratic Flow

10.3.4 Arbitrary Flow

10.4 Optimization Methods Using Optical Flow

10.5 Direct Methods

10.5.1 Extension ofOptical Flow-Based Methods

10.5.2 Tsai-Huang Method

10.6 Examples

10.6.1 Numerical Simulations

10.6.2 Experiments with Two Frames of Miss America

10.7 Exercises

11 MOTION SEGMENTATION

11.1 Direct Methods

11.1.1 Thresholding for Change Detection

11.1.2 An Algorithm Using Mapping Parameters

11.1.3 Estimation of Model Parameters

11.2 Optical Flow Segmentation

11.2.1 Modified Hough Transform Method

11.2.2 Segmentation for Layered Video Representation .

11.2.3 Bayesian Segmentation

11.3 Simultaneous Estimation and Segmentation

11.3.1 Motion Field Model

11.3.2 Problem Formulation

11.3.3 The Algorithm

11.3.4 Relationship to Other Algorithms

11.4 Examples

11.5 Exercises

12 STEREO AND MOTION TRACKING

12.1 Motion and Structure from Stereo

12.1.1 Still-Frame Stereo Imaging

12.1.2 3-D Feature Matching fbr Motion Estimation

12.1.3 Stereo-Motion Fusion

12.1.4 Extension to Multiple Motion

12.2 Motion Tracking

12.2.1 Basic Principles

12.2.2 2-D Motion Tracking

12.2.3 3-D Rigid Motion Ttacking

12.3 Examples

12.4 Exercises

13 MOTION COMPENSATED FILTERING

13.1 Spatio-Temporal Fourier Spectrum

13.1.1 Global Motion with Constant Velocity

13.1.2 Global Motion with Acceleration

13.2 Sub-Nyquist Spatio-Temporal Sampling

13.2.1 Sampling in the Temporal Direction Only

13.2.2 Sampling on a Spatio-Temporal Lattice

13.2.3 Critical Velocities

13.3 Filtering Along Motion TRajectories

13.3.1 Arbitrary Motion Trajectories

13.3.2 Global Motion with Constant Velocity

13.3.3 Accelerated Motion

13.4 Applications

13.4.1 Motion-Compensated Noise Filtering

13.4.2 Motion-Compensated Reconstruction Filtering

13.5 Exercises

14 NOISE FILTERING

14.1 Intraframe Filtering

14.1.1 LMMSE Filtering

14.1.2 Adaptive (Local) LMMSE Filtering

14.1.3 Directional Filtering

14.1.4 Median and Weighted Median Filtering

14.2 Motion-Adaptive Filtering

14.2.1 Direct Filtering

14.2.2 Motion-Detection Based Filtering

14.3 Motion-Compenaated Filtering

14.3.1 Spatio-Temporal Adaptive LMMSE Filtering

14.3.2 Adaptive Weighted Averaging Filter

14.4 Examples

14.5 Exercises

15 RESTORATION

15.1 Modeling

15.1.1 Shift-Invariant Spatial Blurring

15.1.2 Shift-Varying Spatial Blurring

15.2 Intraframe Shift-Invariant Restoration

15.2.1 Pseudo Inverse Filtering

15.2.2 Constrained Least Squares and Wiener Filtering

15.3 Intraframe Shift-Varying Restoration

15.3.1 Overview ofthe POCS Method

15.3.2 Restoration Using POCS

15.4 Multiframe Restoration

15.4.1 Cross-Correlated Multiframe Filter

15.4.2 Motion-Compensated Multiframe Filter

15.5 Examples

15.6 Exercises

16 STANDARDS CONVERSION

16.1 Down-Conversion

16.1.1 Down-Conversion with Anti-Alias Filtering

16.1.2 Down-Conversion without Anti-Alias Filtering

16.2 Practical Up-Conversion Methods

16.2.1 Intraframe Filtering

16.2.2 Motion-Adaptive Filtering

16.3 Motion-Compensated Up-Conversion

16.3.1 Basic Principles

16.3.2 Global-Motion-Compensated De-interlacing

16.4 Examples

16.5 Exercises

17 SUPERRESOLUTION

17.1 Modeling

17.1.1 Continuous-Discrete Model

17.1.2 Discrete-Discrete Model

17.1.3 Problem Interrelations

17.2 Interpolation-Restoration Methods

17.2.1 Intraframe Methods

17.2.2 Multiframe Methods

17.3 A Frequency Domain Method

17.4 A Unifying POCS Method

17.5 Examples

17.6 Exercises

V STILL IMAGE COMPRESSION

18 LOSSLESS COMPRESSION

18.1 Basics of Image Compression

18.1.1 Elements of an Image Compression System

18.1.2 Information Theoretic Concepts

18.2 Symbol Coding

18.2.1 Fixed-Length Coding

18.2.2 Huffman Coding

18.2.3 Arithmetic Coding

18.3 Lossless Compression Methods

18.3.1 Lossless Predictive Coding

18.3.2 Run-Length Coding of Bit-Planes

18.3.3 Ziv-Lempel Coding

18.4 Exercises

19 DPCM AND TRANSFORM CODING

19.1 Quantization

19.1.1 Nonuniform Quantization

19.1.2 Uniform Quantization

19.2 Differential Pulse Code Modulation

19.2.1 Optimal Prediction

19.2.2 Quantization of the Prediction Error

19.2.3 Adaptive Quantization

19.2.4 Delta Modulation

19.3 Transform Coding

19.3.1 Discrete Cosine Transform

19.3.2 Quantization/Bit Allocation

19.3.3 Coding

19.3.4 Blocking Artifacts in Transform Coding

19.4 Exercises

20 STILL IMAGE COMPRESSION STANDARDS

20.1 Bilevel Image Compression Standards

20.1.1 One-Dimensional RLC

20.1.2 Two-Dimensional RLC

20.1.3 The JBIG Standard

20.2 The JPEG Standard

20.2.1 Baseline Algorithm

20.2.2 JPEG Progressive

20.2.3 JPEG Lossless

20.2.4 JPEG Hierarchical

20.2.5 ImplementationsofJPEG

20.3 Exercises

21 VECTOR QUANTIZATION, SUBBAND CODING

AND OTHER METHODS

21.1 Vector Quantization

21.1.1 Structure of a Vector Quantizer

21.1.2 VQ Codebook Design

21.1.3 Practical VQ Implementations

21.2 Fractal Compression

21.3 Subband Coding

21.3.1 Subband Decomposition

21.3.2 Coding of the Subbands

21.3.3 Relationship to Transform Coding

21.3.4 Relationship to Wavelet Transform Coding

21.4 Second-Generation Coding Methods

21.5 Exercises

VI VIDEO COMPRESSION

22 INTERFRAME COMPRESSION METHODS

22.1 Three-Dimensional Waveform Coding

22.1.1 3-D Transform Coding

22.1.2 3-D Subband Coding

22.2 Motion-Compensated Waveform Coding

22.2.1 MC Transform Coding

22.2.2 MC Vector Quantization

22.2.3 MC Subband Coding

22.3 Model-Based Coding

22.3.1 Object-Based Coding

22.3.2 Knowledge-Based and Semantic Coding

22.4 Exerclses

23 VIDEO COMPRESSION STANDARDS

23.1 The H.261 Standard

23.1.1 Input Image Formats

23.1.2 Video Multiplex

23.1.3 Video Compression Algorithm

23.2 The MPEG-l Standard

23.2.1 Features

23.2.2 Input Video Format

23.2.3 Data Structure and Compression Modes

23.2.4 Intraframe Compression Mode

23.2.5 Interframe Compression Modes

23.2.6 MPEG-l Encoder and Decoder

23.3 The MPEG-2 Standard

23.3.1 MPEG-2 Macroblocks

23.3.2 Coding Interlaced Video

23.3.3 Scalable Extensions

23.3.4 Other Improvements

23.3.5 Overview of Profiles and Levels

23.4 Software and Hardware Implementations

24 MODEL-BASED CODING

24.1 General Object-Based Methods

24.1.1 2-D/3-D Rigid Objects with 3-DMotion

24.1.2 2-D Flexible Objects with 2-D Motion

24.1.3 Affine Transformations with TRiangular Meshes

24.2 Knowledge-Based and Semantic Methods

24.2.1 General Principles

24.2.2 MBASIC Algorithm

24.2.3 Estimation Using a Flexible Wireframe Model

24.3 Examples

25 DIGITAL VIDEO SYSTEMS

25.1 Videoconferencing

25.2 Interactive Video and Multimedia

25.3 Digital Television

25.3.1 Oigital Studio Standards

25.3.2 Hybrid Advanced TV Systems

25.3.3 All-Oigital TV

25.4 Low-Bitrate Video and Videophone

25.4.1 The ITU Recommendation H.263

25.4.2 The ISO MPEG-4 Requirements

APPENDICES

A MARKOV AND GIBBS RANDOM FIELDS

A.l Definitions

A.l.l Markov Random Fields

A.1.2 Gibbs Random Fields

A.2 Equivalence of MRF and GRF

A.3Local Conditional Probabilities

B BASICS OF SEGMENTATION

B.l Thresholding

B.I.l Finding the Optimum Threshold(s)

B.2 Clustering

B.3 Bayesian Methods

B.3.1 The MAP Method

B.3.2 The Adaptive MAP Method

B.3.3 Vector Field Segmentation

C KALMAN FILTEMNG

C.l Linear State-Space Model

C.2 Extended Kalman Filtering