荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: oopilix ([0;1;32;40m), 信区: Visual
标  题: [zz]视频压缩(English)
发信站: 荔园晨风BBS站 (Mon Oct 13 23:25:35 2003), 站内信件

如果您对视频压缩感兴趣,那么
一必须学会看English
二必须有一定的数学功底
三就是到网上google上input key words : mpeg jpeg jpeg2000 etc

Video Compression

JPEG
H.261
MPEG

Reference: Chapter 6 of Steinmetz and Nahrstedt


Motivations:
Uncompressed video and audio data are huge. In HDTV, the bit rate easily
 exceeds 1 Gbps. --> big problems for storage and network
communications.

The compression ratio of lossless methods (e.g., Huffman, Arithmetic,
LZW) is not high enough for image and video compression, especially when
 distribution of pixel values is relatively flat.

The following will be discussed:
Spatial Redundancy Removal -- Intraframe coding (JPEG)

Spatial and temporal Redundancy Removal -- Intraframe and Interframe
coding (H.261, MPEG)


4.2.1. JPEG

------------------------------------------------------------------------
--------

1. What is JPEG?
"Joint Photographic Expert Group". Voted as international standard in
1992.

Works with color and grayscale images, e.g., satellite, medical, ...
2. JPEG overview
Encoding



Decoding -- Reverse the order
3. Major Steps
DCT (Discrete Cosine Transformation)

Quantization

Zigzag Scan

DPCM on DC component

RLE on AC Components

Entropy Coding
3a. Discrete Cosine Transform (DCT)
Overview:



Definition (8 point DCT):


Question: What is F[0,0]? -- define DC and AC components.


The 64 (8 x 8) DCT basis functions



Why DCT not FFT?
DCT is like FFT, but can approximate lines well with few coeff.




Computing the DCT

Factoring reduces problem to a series of 1D DCTs:





Most software implementations use fixed point arithmetic. Some fast
implementations approximate coefficients so all multiplies are shifts
and adds.

World record is 11 multiplies and 29 adds. (C. Loeffler, A. Ligtenberg
and G. Moschytz, "Practical Fast 1-D DCT Algorithms with 11
Multiplications", Proc. Intl. Conf. on Acoustics, Speech, and Signal
Processing 1989 (ICASSP `89), pp. 988-991)
3b. Quantization
Why? -- To throw out bits

Example: 101101 = 45 (6 bits).
Truncate to 4 bits: 1011 = 11.
Truncate to 3 bits: 101 = 5.

Quantization error is the main source of the Lossy Compression.
Uniform quantization
Divide by constant N and round result (N = 4 or 8 in examples above).

Non powers-of-two gives fine control (e.g., N = 6 loses 2.5 bits)
Quantization Tables
In JPEG, each F[u,v] is divided by a constant q(u,v).

Table of q(u,v) is called quantization table.
----------------------------------
16 11 10 16 24 40 51 61
12 12 14 19 26 58 60 55
14 13 16 24 40 57 69 56
14 17 22 29 51 87 80 62
18 22 37 56 68 109 103 77
24 35 55 64 81 104 113 92
49 64 78 87 103 121 120 101
72 92 95 98 112 100 103 99
----------------------------------


Eye is most sensitive to low frequencies (upper left corner), less
sensitive to high frequencies (lower right corner)

Standard defines 2 default quantization tables, one for luminance
(above), one for chrominance.

Q: How would changing the numbers affect the picture (e.g., if I doubled
 them all)?
Quality factor in most implementations is the scaling factor for default
 quantization tables.


Custom quantization tables can be put in image/scan header.
3c. Zig-zag Scan
Why? -- to group low frequency coefficients in top of vector.

Maps 8 x 8 to a 1 x 64 vector


3d. Differential Pulse Code Modulation (DPCM) on DC component
DC component is large and varied, but often close to previous value
(like lossless JPEG).

Encode the difference from previous 8x8 blocks -- DPCM
3e. Run Length Encode (RLE) on AC components
1x64 vector has lots of zeros in it

Encode as (skip, value) pairs, where skip is the number of zeros and
value is the next non-zero component.

Send (0,0) as end-of-block sentinel value.
3f. Entropy Coding
Categorize DC values into SSS (number of bits needed to represent) and
actual bits.
--------------------
Value SSS
0 0
-1,1 1
-3,-2,2,3 2
-7..-4,4..7 3
--------------------


Example: if DC value is 4, 3 bits are needed.
Send off SSS as Huffman symbol, followed by actual 3 bits.


For AC components (skip, value), encode the composite symbol (skip,
SSS) using the Huffman coding.

Huffman Tables can be custom (sent in header) or default.
4. Overview of the JPEG bitstream

A "Frame" is a picture, a "scan" is a pass through the pixels (e.g., the
 red component), a "segment" is a group of blocks, a "block" is an 8x8
group of pixels.

Frame header:
sample precision
(width, height) of image
number of components
unique ID (for each component)
horizontal/vertical sampling factors (for each component)
quantization table to use (for each component)

Scan header
Number of components in scan
component ID (for each component)
Huffman table for each component (for each component)

Misc. (can occur between headers)
Quantization tables
Huffman Tables
Arithmetic Coding Tables
Comments
Application Data
5. Various JPEG Modes
Baseline/Sequential -- the one that we described in detail

Lossless

Progressive

Hierarchical

"Motion JPEG" -- Baseline JPEG applied to each image in a video.
Lossless Mode

A special case of the JPEG where indeed there is no loss



Take difference from previous pixels (not blocks as in the Baseline
mode) as a "predictor".
Predictor uses linear combination of previously encoded neighbors.
It can be one of seven different predictor based on pixels neighbors




Since it uses only previously encoded neighbors, first row always uses
P2, first column always uses P1.

Effect of Predictor (test with 20 images)


Note: "2D" predictors (4-7) always do better than "1D" predictors.

Comparison with Other Lossless Compression Programs (compression ratio):


-----------------------------------------------------------------
Compression Program Compression Ratio
Lena football F-18 flowers
-----------------------------------------------------------------
lossless JPEG 1.45 1.54 2.29 1.26
optimal lossless JPEG 1.49 1.67 2.71 1.33
compress (LZW) 0.86 1.24 2.21 0.87
gzip (Lempel-Ziv) 1.08 1.36 3.10 1.05
gzip -9 (optimal Lempel-Ziv) 1.08 1.36 3.13 1.05
pack (Huffman coding) 1.02 1.12 1.19 1.00
-----------------------------------------------------------------



Progressive Mode

Goal: display low quality image and successively improve.

Two ways to successively improve image:

Spectral selection: Send DC component, then first few AC, some more AC,
 etc.

Successive approximation: send DCT coefficients MSB (most significant
bit) to LSB (least significant bit).

Hierarchical Mode
A Three-level Hierarchical JPEG Encoder

(From V. Bhaskaran and K. Konstantinides, "Image and Video Compression
Standards: Algorithms and Architectures", Kluwer Academic Publishers,
1995.)




Down-sample by factors of 2 in each direction.
Example: map 640x480 to 320x240


Code smaller image using another method (Progressive, Baseline, or
Lossless).

Decode and up-sample encoded image

Encode difference between the up-sampled and the original using
Progressive, Baseline, or Lossless.

Can be repeated multiple times.

Good for viewing high resolution image on low resolution display.

JPEG-2

Big change was to use adaptive quantization
Further Exploration
Try the Interactive JPEG examples and the JPEG examples.


4.2.2. H. 261

------------------------------------------------------------------------
--------

Developed by CCITT in 1988-1990

Meant for videoconferencing, videotelephone applications over ISDN
telephone lines.

Baseline ISDN is 64 kbits/sec, and integral multiples (px64)
1. Overview of H.261
Decoded Sequence



Frame types are CCIR 601 CIF (352x288) and QCIF (176x144) images with
4:2:0 subsampling.

Two frame types: Intraframes (I-frames) and Interframes (P-frames)

I-frames use basically JPEG

P-frames use "pseudo-differences" from previous frame ("predicted"),
so frames depend on each other.

I-frame provide us with an accessing point.
2. Intra Frame Coding

Macroblocks are 16x16 pixel areas on Y plane of original image.
A macroblock usually consists of 4 Y blocks, 1 Cr block, and 1 Cb block.



Quantization is by constant value for all DCT coefficients (i.e., no
quantization table as in JPEG).
3. Inter-frame (P-frame) Coding
An Coding Example (P-frame)



Previous image is called reference image.

Image to code is called target image.

Actually, the difference is encoded.

Subtle points:

Need to used decoded image as reference image, not original. Why?

Were using "Mean Absolute Difference" (MAD) to decide best block. Can
also use "Mean Squared Error" (MSE) = sum(E*E)
4. Details -- How the Macroblock is Coded

Many macroblocks will be exact matches (or close enough). So send
address of each block in image --> Addr

Sometimes no good match can be found, so send INTRA block --> Type

Will want to vary the quantization to fine tune compression, so send
quantization value --> Quant

Motion vector --> vector

Some blocks in macroblock will match well, others match poorly. So
send bitmask indicating which blocks are present (Coded Block Pattern,
or CBP).

Send the blocks (4 Y, 1 Cr, 1 Cb) as in JPEG.
5. H.261 Bitstream Structure

Need to delineate boundaries between pictures, so send Picture Start
Code --> PSC

Need timestamp for picture (used later for audio synchronization), so
send Temporal Reference --> TR

Is this a P-frame or an I-frame? Send Picture Type --> PType

Picture is divided into regions of 11x3 macroblocks called Groups of
Blocks --> GOB

Might want to skip whole groups, so send Group Number (Grp #)

Might want to use one quantization value for whole group, so send
Group Quantization Value --> GQuant

Overall, bitstream is designed so we can skip data whenever possible
while still unambiguous.
6. H.261 Codec

7. Hard Problems in H.261
Motion vector search

Propagation of Errors

Bit-rate Control
7a. Motion Vector Search


-- pixels in the macro block with upper left corner (x,y) in the Target.

-- pixels in the macro block with upper left corner (x+i,y+j) in the
Reference.

Cost function is:



Where MAE stands for Mean Absolute Error.

Goal is to find a vector (u, v) such that MAE (u, v) is minimum

Full Search Method:

Search the whole [-p,p] searching region.

Cost is: operations,
assuming that each pixel comparison needs 3 operations (Subtraction,
Absolute value, Addition).

Two-Dimensional Logarithmic Search:
Similar to binary search. MAE function is initially computed within a
window of [-p/2, p/2] at nine locations as shown in the figure.

Repeat until the size of the search region is one pixel wide:


Find one of the nine locations that yields the minimum MAE

Form a new searching region with half of the previous size and
centered at the location found in step 1.




Hierarchical Motion Estimation:



Form several low resolution version of the target and reference pictures


Find the best match motion vector in the lowerest resolution version.

Modify the motion vector level by level when going up

Performance comparison:

-----------------------------------------------------------------
Search Method Operation for 720x480 at 30 fps
p = 15 p=7
-----------------------------------------------------------------
Full Search 29.89 GOPS 6.99 GOPS
Logarithmic 1.02 GOPS 777.60 MOPS
Hierarchical 507.38 MOPS 398.52 MOPS
-----------------------------------------------------------------

7b. Propagation of Errors
Send an I-frame every once in a while

Make sure you use decoded frame for comparison
7c. Bit-rate Control
Simple feedback loop based on "buffer fullness"
If buffer is too full, increase the quantization scale factor to
reduce the data.



4.2.3. MPEG

------------------------------------------------------------------------
--------

1. What is MPEG ?
"Motion Picture Expert Group", established circa 1990 to create standard
 for delivery of audio and video

MPEG-1 Target: VHS quality on a CD-ROM (320 x 240 + CD audio @ 1.5
Mbits/sec)

Standard had three parts:

Video: based on H.261 and JPEG

Audio: based on MUSICAM technology

System: control interleaving of streams
2. MPEG Video
Recall H.261 dependencies:



Problem: many macroblocks need information not in the reference frame.


Example:



MPEG solution: add third frame type: bidirectional frame, or B-frame

B-frames search for macroblock in past and future frames.

Typical pattern is IBBPBBPBB IBBPBBPBB IBBPBBPBB
Actual pattern is up to encoder, and need not be regular.



3. Differences from H.261
Larger gaps between I and P frames, so expand motion vector search
range.

To get better encoding, allow motion vectors to be specified to fraction
 of a pixel (1/2 pixels).

Bitstream syntax must allow random access, forward/backward play, etc.


Added notion of slice for synchronization after loss/corrupt data.
Example: picture with 7 slices:



B frame macroblocks can specify two motion vectors (one to past and
one to future), indicating result is to be averaged.



Compression performance of MPEG 1
------------------------------
Type Size Compression
------------------------------
I 18 KB 7:1
P 6 KB 20:1
B 2.5 KB 50:1
Avg 4.8 KB 27:1
------------------------------

4. MPEG Video Bitstream
Public domain tool mpeg_stat and mpeg_bits will analyze a bitstream.


Sequence Information

Video Params include width, height, aspect ratio of pixels, picture
rate.

Bitstream Params are bit rate, buffer size, and constrained parameters
flag (means bitstream can be decoded by most hardware)

Two types of QTs: one for intra-coded blocks (I-frames) and one for
inter-coded blocks (P-frames).

Group of Pictures (GOP) information

Time code: bit field with SMPTE time code (hours, minutes, seconds,
frame).

GOP Params are bits describing structure of GOP. Is GOP closed? Does
it have a dangling pointer broken?

Picture Information

Type: I, P, or B-frame?

Buffer Params indicate how full decoders buffer should be before
starting decode.

Encode Params indicate whether half pixel motion vectors are used.

Slice information

Vert Pos: what line does this slice start on?

QScale: How is the quantization table scaled in this slice?

Macroblock information

Addr Incr: number of MBs to skip.

Type: Does this MB use a motion vector? What type?

QScale: How is the quantization table scaled in this MB?

Coded Block Pattern (CBP): bitmap indicating which blocks are coded.
5. Decoding MPEG Video in Software
Software Decoder goals: portable, multiple display types

Breakdown of time
-------------------------
Function % Time
Parsing Bitstream 17.4%
IDCT 14.2%
Reconstruction 31.5%
Dithering 24.5%
Misc. Arith. 9.9%
Other 2.7%
-------------------------

6. MPEG-2, MPEG-3, and MPEG-4
MPEG-2 target applications
--------------------------------------------------------------------
Level size Pixels/sec bit-rate Application
(Mbits)
--------------------------------------------------------------------
Low 352 x 240 3 M 4 consumer tape equiv.
Main 720 x 480 10 M 15 studio TV
High 1440 1440 x 1152 47 M 60 consumer HDTV
High 1920 x 1080 63 M 80 film production
--------------------------------------------------------------------


Differences from MPEG-1

Search on fields, not just frames.

4:2:2 and 4:4:4 macroblocks

Frame sizes as large as 16383 x 16383

Scalable modes: Temporal, Progressive,...

Non-linear macroblock quantization factor

A bunch of minor fixes (see MPEG FAQ for more details)

MPEG-3: Originally for HDTV (1920 x 1080), got folded into MPEG-2

MPEG-4: Very little published information. Originally targeted at very
low bit-rate communication (4.8 to 64 kb/sec). Now addressing video
processing...
Further Exploration
MPEG Resources on the Web.
------------------------------------------------------------------------
--------

Last Updated: 6/26/96

--


 ※ IP来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM oo.pi.li.x]
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh

※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 61.144.235.39]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店