Outline Image Compression Image Understanding Multiframe Image Restoration Iterative Image Restoration Motion Detection and Estimation Video Enhancement and Restoration 3-D Shape Reconstruction from Multiple Views Image Sequence Stabilization, Mosaicking, and Superresolution Video Compression Video Understanding

V. Image Compression

5.1 Lossless Coding--Introduction What’s lossless coding? represent an image signal with the smallest possible number of bits without loss of any information speed up transmission and minimizing storage requirements Example: a single uncompressed video frame with a resolution of 500 x 500 pixels would require 100 s over a capacity of 64,000 bit/s(64 Kbps). The resulting delay is intolerably large, considering that a delay as small as 1-2 s is needed to conduct an interactive “slide show,” and a much smaller delay (of the order of 0.1 s) is required for video transmission or playback.

5.1 Lossless Coding--Introduction Why is lossless coding possible? Redundancy—correlation among the image Spatial correlation among neighbor pixels Temporal correlation among video frames Spectral correlation between image samples 视频数据中存在着大量的冗余， 即图像的各像素数 据之间存在极强的相关性。 利用这些相关性， 一部 分像素的数据可以由另一部分像素的数据推导出来， 结果视频数据量能极大地压缩，有利于传输和存储。 视频数据主要存在以下形式的冗余: 视频图像在水平方向相邻像素之间、垂直方向相邻像素之间的变化一般都很小， 存在着极强的空间相关性。 特别是同一景物各点的灰度和颜色之间往往存在着空间连贯性，从而产生了空间冗余， 常称为帧内相关性。 在相邻场或相邻帧的对应像素之间， 亮度和色度信息存在着极强的相关性。 当前帧图像往往具有与前、后两帧图像相同的背景和移动物体， 只不过移动物体所在的空间位置略有不同，对大多数像素来说， 亮度和色度信息是基本相同的，称为帧间相关性或时间相关性。

5.1 Lossless Coding--Introduction Applications of lossless coding Compression of digital media imagery Facsimile transmission of bitonal images Several Standards for lossless compression Lossless JPEG standard Facsimile compression standards JBIG compression standard

5.1 Lossless Coding—Basic ideas

5.1 Lossless Coding—Basic ideas Transformation reversible (one-to-one) reduce data correlation, alter the data distribution,… differential mapping, unitary transforms,…

5.1 Lossless Coding—Basic ideas Data-to-Symbol Mapping convert f’(n) to symbols partitioning Running-length coding

5.1 Lossless Coding—Basic ideas Lossless Symbol Coding assign binary codewords to the input symbols variable-length coding (VLC) i.e., entropy coding, such as Huffman and arithmetic coding fixed-length coding, such as Lempel-Ziv coding

5.1 Lossless Coding—Basic ideas Factors of Lossless Symbol Coding Compression efficiency

5.1 Lossless Coding—Basic ideas Factors of Lossless Symbol Coding Coding delay Implementation complexity Robustness Scalability

5.1 Lossless Coding—Lossless symbol coding Statistical schemes (Huffman, Arithmetic) require the source symbol probability distribution; shorter codewords for the symbols with higher probability of occurrence

5.1 Lossless Coding—Lossless symbol coding Dictionary-based schemes (Lempel-Ziv) do not require a priori knowledge of the source symbol probability distribution; dynamically construct encoding and decoding tables; Fixed length binary codewords

5.1 Lossless Coding—Lossless symbol coding Basic Concepts from Information Theory source alphabet self-information first-order entropy (marginal entropy) average bit rate

5.1 Lossless Coding—Lossless symbol coding Huffman Coding

5.1 Lossless Coding—Lossless symbol coding Huffman Coding

5.1 Lossless Coding—Lossless symbol coding Huffman Coding

5.1 Lossless Coding—Lossless symbol coding Huffman Coding

5.1 Lossless Coding—Lossless symbol coding Arithmetic Coding

5.1 Lossless Coding—Lossless symbol coding Arithmetic Coding

Arithmetic Coding

5.1 Lossless Coding—Lossless symbol coding Lempel-Ziv Coding

5.1 Lossless Coding—Lossless symbol coding Lempel-Ziv Coding

5.1 Lossless Coding –Lossless Coding Standards JBIG Standard Lossless JPEG Standard

5.1 Lossless Coding–Other Developments CALIC Perceptually Lossless Image Coding

5.2 Block Truncation Coding-Introduction Statistical and structural methods have been developed for image compression Statistical method--the algebraic structure of the pixels in an image Structural method--the geometric structure of the image http://zh.wikipedia.org/wiki/%E6%96%B9%E5%9D%97%E7%BC%96%E7%A0%81

5.2 Block Truncation Coding-Basics a lossy fixed length compression method that uses a Q-level quantizer to quantize a local region of the image to preserve the sample mean and sample standard deviation of a gray-scale image in its simplest form additional constraints can be added to preserve higher-order moments. BTC is a block adaptive moment preserving quantizer

5.2 Block Truncation Coding-Algorithm divide the image into nonoverlapping rectangular regions let the sample mean of the block be the threshold; a “1” would then indicate if an original pixel value is above this threshold, and “0” if it is below.

5.2 Block Truncation Coding-Algorithm

5.2 Block Truncation Coding-Decompression

5.2 Block Truncation Coding-Algorithm The data rate is then determined by the block size k and the number of bits f that are allocated to the sample mean and sample standard deviation of a block.

5.2 Block Truncation Coding-Variations and Applications of BTC graphics images predictive coding coding color images the use of absolute moments video compression ……

5.2 Block Truncation Coding-Variations and Applications of BTC HDTV Sun’s CellB video format XMovie ……

5.3 Vector Quantization--Introduction Quantization is a mapping of a large set of values to a smaller set of values.

5.3 Vector Quantization--Introduction

5.3 Vector Quantization--Introduction

5.3 Vector Quantization—Theory of Vector Quantization The bit rate R associated with the VQ depends on N (the number of codevectors in the codebook) and the vector dimension k. For quantifying the "quality of match" between two vectors x and y, the most common of which is the squared error given by

5.3 Vector Quantization—Theory of Vector Quantization

5.3 Vector Quantization—Design of Vector Quantizers LBG Design Algorithm Initialization (random selection) Encoding of the training vectors Computing of the centroids Other Algorithms Finding a good initial set of codevectors Splitting algorithm Nerual nets ......

5.3 Vector Quantization—Structured VQ Sacrifice performance for speed Impose structural constraints on the VQ codebook Linearly or quadratically dependent on the rate and dimension

5.3 Vector Quantization—Structured VQ Tree-Structured VQ A hierarchical arrangement of codevectors Searching efficiently

5.3 Vector Quantization—Structured VQ Mean-Removed VQ a codebook may have many similar vectors differing only in their mean extract the variation among vectors and code that extracted component separately as a scalar

5.3 Vector Quantization—Structured VQ Gain-Shape VQ Multistage VQ ……

5.4 Wavelet Image Compression-Background Capture both the transient high-frequency phenomena and long-spatial-duration low- frequency phenomena Capture most image information in the highly subsampled low-frequency band, and additional localized edge information in spatial clusters of coefficients in the high- frequency bands Have an encoded bitstream that can be chopped off at any desired point to provide a commensurate reconstruction image quality

Multiresolution wavelet image representation naturally facilitates progressive transmission - a desirable feature for the transmission of compressed images over heterogeneous packet networks and wireless channels.

5.4 Wavelet Image Compression-Transform Coding Paradigm

5.4 Wavelet Image Compression-Subband Coding Treat different bands differently as each band can be modeled as a statistically distinct process in quantization and coding; The coding gain of subband coding in general case:

5.4 Wavelet Image Compression-Subband Coding

5.4 Wavelet Image Compression-Subband Coding Bit allocation results for different subbands under a total bit rate budget of 1 bit per pixel for wavelet image coding. Since low-frequency bands in the upper-left corner have far more energy than high-frequency bands in the lower right corner, more bits have to be allocated to low-pass bands than to high-pass bands. Since subband coding treats wavelet coefficients according to their frequency bands, it is effectively a frequency domain transform technique.

5.4 Wavelet Image Compression-Zero-Tree-Based Framework and EZW Coding A wavelet image representation can be thought of as a tree structured spatial set of coefficients. A wavelet coefficient tree is defined as the set of coefficients from different bands that represent the same spatial region in the image.

5.4 Wavelet Image Compression-Zero-Tree-Based Framework and EZW Coding

5.5 JPEG Lossy Image Compression Standard-Introduction Part of the multipart set of ISO standards IS 10918-1,2,3 (ITU-T Recommendations T.81,T.83,T.84) Entails an irreversible mapping of the image to a compressed bit stream with mechanisms for a controlled loss of information produces a bit stream that is usually much smaller in size than that produced with lossless compression

5.5 JPEG Lossy Image Compression Standard-Introduction Key features of the lossy JPEG standard: Both sequential and progressive modes of en coding are permitted. Low complexity implementations in both hardware and software are feasible. All types of images are permitted. A graceful tradeoff in bit rate and quality is offered. …….

5.5 JPEG Lossy Image Compression Standard-Codec Structure

5.5 JPEG Lossy Image Compression Standard-Decoder Structure

5.5 JPEG Lossy Image Compression Standard-Discrete Cosine Transform Lossy JPEG compression is based on transform coding that uses the DCT. In DCT coding, each component of the image is subdivided into blocks of 8 x 8 pixels. A two-dimensional DCT is applied to each block of data to obtain an 8 x 8 array of coefficients.

5.5 JPEG Lossy Image Compression Standard-Discrete Cosine Transform

5.5 JPEG Lossy Image Compression Standard-Quantization

5.5 JPEG Lossy Image Compression Standard-Coefficient-to-Symbol Mapping and Coding JPEG treats the DC coefficient and the set of AC coefficients differently. JPEG uses the Huffman coding or arithmetic coding to represent the symbols.

5.5 JPEG Lossy Image Compression Standard-Coefficient-to-Symbol Mapping and Coding DC Coefficient Symbols Differential encoding The difference is mapped to a symbol described by a pair (category, amplitude)

5.5 JPEG Lossy Image Compression Standard-Coefficient-to-Symbol Mapping and Coding Mapping AC Coefficient to Symbols Run-length coding The symbols are defined as [runs, nonzero terminating value]

5.6 JPEG Lossless Image Compression Standards-Original JPEG Lossless Standards  Code the prediction error Huffman Coding Procedures Arithmetic Coding Procedures

5.6 JPEG Lossless Image Compression JPEG-LS The difference between JPEG-LS and original lossless standards JPEG-LS uses a nonlinear predictor JPEG-LS uses context modeling of the prediction errors prior to encoding JPEG-LS uses Golomb-Rice codes for encoding prediction errors JPEG-LS uses a simple alphabet extension mechanism JPEG-LS provides a near-lossless mode

5.6 JPEG Lossless Image Compression- JPEG-LS

JPEG2000标准 JPEG2000是JPEG工作组制定的最新的静止图像压 缩编码的国际标准， 标准号为ISO／ IECl5444(ITU-TT.800)， 并于2000年底公布。

JPEG2000标准 JPEG2000主要由6个部分组成: 第一部分为编码的核心部分，提供优秀的压缩性能和 压缩灵活性，提供随机访问码流的机制； 第二部分为编码扩展； 第三部分为Motion JPEG2000(MJP2000)； 第四部分为一致性测试； 第五部分为参考软件； 第六部分为复合图像文件格式。

JPEG2000标准 1. JPEG2000采用了小波变换(DWT) JPEG基本算法中的基于子块的DCT被离散小波变 换(DWT, Discrete Wavelet Transform)取代。 DWT自身具有多分辨率图像表示性能， 它可以在 大范围去掉图像的相关性， 将图像能量分布更好 地集中， 使压缩效率得到提高。

JPEG2000标准 一个图像可以被分成若干大小相等的片(tile)， 片 的具体尺寸可以由用户根据应用需要来决定， 片 包括所有的图像分量， 假设图像有3个分量(YUV) 且图像被分成4个片， 实际上指的是对应的4个Y 片， 4个U片和4个V片， 即每个片由3个分量片 组成。 各个分量片独立编、 解码， 可以从码流 中单独提取某个或某些片， 解码后重建图像。 这 种片划分和片独立编码的机制有利于从码流中提 取和解码某个图像区域。

JPEG2000标准 DWT对静止图像进行三级分解 一级分解示意图； (b) 二级分解示意图； (c) 三级分解示意图

JPEG2000标准 对分量片做不同级别的小波变换，小波变换的作用是对图像进行多分辨率分解，即把原始图像分解成不同空间、不同频率的子图像，这些子图像实际上是由小波变换后产生的系数构成，即系数图像。 对一个原始图像或分量片进行3级小波分解,每一级分解都把图像分解成4个不同空间、不同频带的子图像(也称为子带图像或子带分量)。低频分量LL(包含图像的低频信息，即图像的主要特征，低频分量可再次分解)；水平分量LH(包含较多的水平边缘信息)；垂直分量HL(包含较多的垂直边缘信息)；对角分量HH(包含水平和垂直边缘信息)。

JPEG2000标准 分解级数越多，图像分辨率等级越多，每一级分解图像的分辨率降为前一级的一半。在解码端， 如果只想得到低于原始图像分辨率图像，就只需对部分的子带图像(子带分量)进行解码。

JPEG2000标准 小波变换本身并不具有数据压缩能力， 变换前， 原始图像的数据量(像素值的个数)与变换后各系数的数据量（系数个数）相等， 变换的意义在于使图像的能量分布（频域内的系数分布）发生了改变， 图像的主要能量集中在低频区 (LL区)， 而水平、 垂直、 对角线部分的高频能量较少。 通过量化， 把大量幅值较小系数抑制为零， 从而压缩数据量， 要进一步大幅度压缩数据量， 还需进行合适的编码处理(如算术编码)， 用更少的比特表示那些量化后不为零的小波系数。

JPEG2000标准 2. JPEG2000同时支持有损和无损压缩 小波变换可以使用可逆的Le Gall(5，3)滤波器， 也可以使用不可逆的Daubechies(9，7)双正交滤波器。可逆滤波器支持无损编码，不可逆滤波器不支持无损编码但能达到更高的压缩比。

JPEG2000标准 3. JPEG2000支持RoI处理 在处理图像时，往往对部分感兴趣区域(RoI， Region of Interest)有较高的质量要求，希望是无损压缩。为了得到较高的压缩效率，把图像的其他部分看成是背景，进行压缩比较高的有损压缩。 在传输图像码流时，RoI区域可先于图像的其他部分被传输，如果压缩码流被截取，则在一定程度上可保证RoI的质量。

JPEG2000标准 JPEG2000系统为RoI区域产生一个RoI模板，用来标志RoI区域。选择适当的比例因子s，将位于RoI模板区域之外的背景量化系数的幅值除以2s，得到的数值小于RoI模板中最小的量化系数幅值。这样处理后，位于RoI模板内的量化系数所处的位平面高于背景系数所处的位平面，在进行位平面算术编码的时候，先对RoI域中的量化系数编码，然后再对背景系数编码。因为RoI区域的位平面高于背景区域，RoI区域的压缩码流位于整个码流的前端，当码流被截断时RoI区域中的数据在一定程度上受到保护，保证了RoI的重构质量。

JPEG2000标准 在解码器端，将解码后的量化系数与RoI阈值相比较，若小于RoI阈值，则判定是背景系数，对其进行反向比例放大，即乘以2s，进行恢复，得到重构时所需的小波量化系数。

JPEG2000标准 4. 可随机获取部分压缩码流 JPEG2000系统将码流分层组织，每一层含有一定的质量信息，在前面层的基础上改善图像质量。在网络上进行图像浏览时，可先传送第一层，给用户一个较粗的图像，然后再传送第二层，图像质量在第一层的基础上得到改善，这样一层一层地传输下去，可得到不同质量的重构图像。如果传输了所有的层，则可获得完整的图像压缩码流。JPEG2000由于采用了这种思想，使得压缩生成的码流具有质量可分级性和分辨率可分级性。

JPEG2000标准 5. 随机存取图像某个区域 有时只需得到巨幅图像的部分区域，JPEC2000标准利用小波变换的局部特性，可识别部分图像区域在子带上的映射。每个码块是独立进行编码的，通过选取含有此部分图像区域信息的码块压缩码流，进行解码，可以重构出所要的目标区域。RoI技术在很大程度上为实现随机存取码流提供了一种渠道。

JPEG2000标准 6. 抗误码性能 在JPEG2000标准中，采取了一些措施来提高图像压缩码流的抗误码性能。将量化后的子带系数分成若干个小的编码单元——码块，对每个码块进行独立的编解码。这样，当一个码块的位流发生比特错误时，只会把错误引起的影响限制在本码块中。 压缩码流数据采用了称为包(packet)的结构单元， 每个包的数据前面含有再同步信息，允许发生错误后重新恢复同步。

JPEG2000标准 7. 视觉频率加权 在JPEG2000中，可选择使用对不同空间频率有不同敏感度的视觉系统模型。这一模型用对比度敏感函数(CSF）来衡量。由于CSF函数是由变换系数的视觉频率来决定的，因此，给小波变换后的每个子带，分配一个CSF值。CSF值的确定依据观察重构图像的视觉条件而定有两种选取办法：固定的视觉加权编码和视觉累进加权编码。

JPEG2000标准 固定的视觉加权由视觉条件决定。对分层组织码流， 由于码流可以被截断，在不同的截断处，有不同的质量，因此进行观察的视觉条件是不同的。比如，对于低比特率的情况，缺少细节，压缩图像质量差，适合进行远距离观察； 随着比特数的增加， 细节越来越多，压缩图像质量逐渐变好，则适合近距离观测。因此，CSF值在不同的截断处应有不同的值，这便是视觉累进加权编码。 在进行视觉累进加权编码时，不需改变系数值或者量化步长，而是根据视觉权值，改变失真矩阵，计算码块对每个层的贡献，通过改变码块编码通道在分层组织位流中的顺序来实现。

JPEG2000标准 JPEG2000具有的多种特点使得它具有广泛的应用前景，由于采用小波变换和最新的压缩算法， 因此能够获得较好的压缩比，且对压缩码流可进行灵活处理，如随机获取部分压缩码流、累进式传输、实现RoI以及压缩码流具有较强的容错性能等。这些特点可应用于因特网、移动通信、打印、扫描、数字摄像、遥感、传真、医疗、数字图书馆以及电子商务等方面的图像压缩。