3
Why Data Compression ?
786488 bytes
23116 bytes, Cr=34.0
2020/3/3
compression chap01.ppt
4
Why Data Compression ?
2020/3/3 786488 bytes compression 33079 chap01.ppt bytes, Cr=23.785
PSNR
2552

[ f ( x, y) f ( x, y)]2
xy
2020/3/3
compression chap01.ppt
29
Fidelity Criteria
• Subjective fidelity criteria
Value
Rating
Description
1
Excellent
2020/3/3
compression chap01.ppt
15
rK
r0 = 0 r1 = 1 r2 = 2 r3 = 3 r4 = 4 r5 = 5 r6 = 6 r7 = 7
Example: VLC
pr(rK) Code1 l1(rK) Code2 l2(rK)
0.19
000
3
11
2
0.25
001
Why Data Compression ?
2020/3/3 786488 bytes
compression 49746 chap01.ppt bytes, Cr=15.80 6
Why Data Compression ?
2020/3/3 786488 bytes
compression 26614 chap01.ppt bytes, Cr=29.55 7
18
Inter-sample Redundancy
1300.00
1200.00
1100.00
1000.00
900.00 0.00
2020/3/3
400.00
800.00
compression chap01.ppt
1200.00
1600.00
19
Inter-pixel Redundancy
200.00 160.00 120.00
– 信息的定量測試與分析
2020/3/3
compression chap01.ppt
2
資料壓縮
• 資料壓縮的定義
– 用來減少表示一個信息(資訊)所需之訊號空間 量的程序。
– 例: 長話短說、縮寫
• 資料壓縮的目的
– 降低儲存資料的空間 – 減少資料傳輸速度
2020/3/3
compression chap01.ppt
= 2(0.19)+2(0.25)+2(0.21)+3(0.16)+4(0.08) +5(0.06)+6(0.03)+6(0.02) = 2.7 bits
• Cr = 3/2.7 = 1.11
2020/3/3
compression chap01.ppt
17
符號間之累贅(inter-symbol redundancy)
2020/3/3
compression chap01.ppt
14
編碼累贅(coding redundancy)
• 沒有充分的使用代表資訊的位元資料。
s1, s2, …, sq：所有可能出現的符號 p(si)：符號出現的si機率 平均一個符號需用Lavg個位元： Lavg = ∑(l(si)×p(si)), for i = 1 to q 固定長度編碼(fixed length coding)：Lavg = 3 變動長度編碼(variable length coding)：Lavg=2.7 (表1.1, p1-10)
3
01
2
0.21
010
3
10
2
0.16
011
3
001
3
0.08
100
3
0001
4
0.06
101
3
00001 5
0.03
110
3
000001 6
0.02
111
3
000000 6
2020/3/3
compression chap01.ppt
16
Coding Redundancy
Lavg (Code2) = l2(rK) Pr(rK)
80.00 40.00
0.00
2020/3/3 0.00
Row 256 of lenna
20c0o.m0p0ression chap01.ppt 400.00
600.0200
畫面間累贅(inter-frame redundancy)
• video資料之前後frames間的資料大多很相 似
2020/3/3
2020/3/3
compression chap01.ppt
26
Classes of Data Compression
資料壓縮
無失真資料壓縮法 Huffman 編碼 5 Shannon-Fano 編碼 5 算術編碼 5 LZ 系列 6 其他 7,8,15
失真資料壓縮法 預測編碼 7 非累贅取樣編碼 8 方塊截短編碼 9 轉換編碼 10 向量量化編碼 11 分頻編碼法 12 小波編碼 13 影像碎形壓縮 14 階級式編碼法 15 視訊編碼 18
extreme high quality,
Oriபைடு நூலகம்inal
2020/3/3
4-bits image by IGS
compression chap01.ppt
24
Temporal Redundancy
2020/3/3
compression chap01.ppt
25
Classes of Data Compression
Lossless
Lossy
Why Data Compression ?
2020/3/3 786488 bytes
compression 25485 chap01.ppt bytes, Cr=30.86 8
壓縮資料
• 文書 • 語音(speech)、音訊(audio)與心電圖
(electrocardiogram, ECG) • 影像資料 • 視訊會議及高品質電視
2020/3/3
compression chap01.ppt
27
Fidelity Criteria
• objective fidelity criteria
– Root mean square error Rms
Rms [ 1
M 1 N 1
[f
(x, y)
f
(
x,
y)]2
1
2020/3/3
compression chap01.ppt
9
[ 傳輸影像資料 1024*1024--->4Mbits ]
傳輸媒體
傳輸速率
傳輸時間
電信局電話線
2400 bps
1740秒(29分)
對絞線[或專線]
9600 bps
437秒(7.3分)
T1專線
1.544 Mbps
2.7 秒
同軸電覽
3-10 Mbps
Introduction to Data Compression
2020/3/3
compression chap01.ppt
1
序
• 人類社會生存三大要素
– 物質、能量與信息
• 訊息
– 非獨立存在, 以相互聯繫為前提 – 要依附於載體才能處理、傳輸、操作
• 控制理論的創立: N. Wiener • 訊息理論的定義: C. Shannon
1000 1111
If MSBi(1~4) of Gray Leveli =1111 then Sumi = Gray Leveli
else
Sumi = Gray Leveli + LSBi-1(5~8) of Sumi-1
2020/3/3
compression chap01.ppt
23
Psycho-visual Redundancy
– NTSC : 512 480 – PAL : 512 512 – CCIR 601 (Studio) : 720 480/576 – HDTV : 1440 960 – Super HDTV : 4000 2000 (Japan) – CIF (low bitrate) : 360 240/288(Video
Reversal
Irreversal
Noiseless coding
Fidelity-reduction coding
Redundancy reduction Entropy reduction
Cr

Number of bits needed for the original signal Number of bits needed for the compressed signal
]2
MN x0 y0
– signal-to-noise ratio SNR

f (x, y)2
SNR
xy
[ f ( x, y) f ( x, y)]2
xy
2020/3/3
compression chap01.ppt
28
Fidelity Criteria
– Peak signal-to-noise ratio PSNR