Fundamentals of Multimedia, Chapter

Fundamentals of Multimedia, Chapter 7
Chapter 7
Lossless Compression Algorithms
7.1 Introduction
7.2 Basics of Information Theory
7.3 Run-Length Coding
7.4 Variable-Length Coding (VLC)
7.5 Dictionary-based Coding
7.6 Arithmetic Coding
7.7 Lossless Image Compression
7.8 Further Exploration
1 Li & Drew ! c Prentice Hall 2003Fundamentals of Multimedia, Chapter 7
7.1 Introduction
• Compression: the process of coding that will effectively
reduce the total number of bits needed to represent certain
information.
Encoder
(compression)
Decoder
(decompression)
Storage or
networks
Input Output
data data
Fig. 7.1: A General Data Compression Scheme.
2 Li & Drew ! c Prentice Hall 2003Fundamentals of Multimedia, Chapter 7
Introduction (cont’d)
• If the compression and decompression processes induce no
information loss, then the compression scheme is lossless;
otherwise, it is lossy.
• Compression ratio:
compression ratio =
B0
B1
(7.1)
B0 – number of bits before compression
B1 – number of bits after compression
3 Li & Drew ! c Prentice Hall 2003Fundamentals of Multimedia, Chapter 7
7.2 Basics of Information Theory
• The entropy η of an information source with alphabet S =
{s1, s2, . . . , sn} is:
η = H(S) =
n!
i=1
pi log2
1 pi
(7.2)
= −
n!
i=1
pi log2 pi (7.3)
pi – probability that symbol si will occur in S.
log2 1
pi
– indicates the amount of information ( self-information
as defined by Shannon) contained in si, which corresponds
to the number of bits needed to encode si.
4 Li & Drew ! c Prentice Hall 2003Fundamentals of Multimedia, Chapter 7
Distribution of Gray-Level Intensities
0 0
255 255
1
2/3
1/3
1/256
(a) (b)
i i
pi pi
Fig. 7.2 Histograms for Two Gray-level Images.
• Fig. 7.2(a) shows the histogram of an image with uniform distribution of gray-level intensities, i.e., ∀i pi = 1/256.
Hence, the entropy of this image is:
log2 256 = 8 (7.4)
5 Li & Drew ! c Prentice Hall 2003Fundamentals of Multimedia, Chapter 7
Entropy and Code Length
• As can be seen in Eq. (7.3): the entropy η is a weighted-sum
of terms log2 1
pi
; hence it represents the average amount of
information contained per symbol in the source S.
• The entropy η specifies the lower bound for the average number of bits to code each symbol in S, i.e.,
η ≤ ¯ l (7.5)
¯ l - the average length (measured in bits) of the codewords
produced by the encoder.
6 Li & Drew ! c Prentice Hall 2003Fundamentals of Multimedia, Chapter 7
7.3 Run-Length Coding
• Memoryless Source: an information source that is independently distributed. Namely, the value of the current symbol
does not depend on the values of the previously appeared
symbols.
• Instead of assuming memoryless source, Run-Length Coding
(RLC) exploits memory present in the information source.
• Rationale for RLC: if the information source has the property that symbols tend to form continuous groups, then such
symbol and the length of the group can be coded.
7 Li & Drew ! c Prentice Hall 2003Fundamentals of Multimedia, Chapter 7
7.4 Variable-Length Coding (VLC)
Shannon-Fano Algorithm — a top-down approach
1. Sort the symbols according to the frequency count of their
occurrences.
2. Recursively divide the symbols into two parts, each with approximately the same number of counts, until all parts contain only one symbol.
An Example: coding of “HELLO”
Symbol H E L O
Count 1 1 2 1
Frequency count of the symbols in ”HELLO”.
8 Li & Drew ! c Prentice Hall 2003Fundamentals of Multimedia, Chapter 7
L:(2)
(5)
H,E,O:(3)
(a)
0 1
(b)
L:(2)
(5)
H:(1) E,O:(2)
(3)
0 1
0 1
L:(2)
O:(1)
(5)
E:(1)
H:(1)
(c)
(2)
(3)
0 1
0 1
0 1
Fig. 7.3: Coding Tree for HELLO by Shannon-Fano.
9 Li & Drew ! c Prentice Hall 2003Fundamentals of Multimedia, Chapter 7
Table 7.1: Result of Performing Shannon-Fano on HELLO
Symbol Count log2 1
pi
Code # of bits used
L 2 1.32 0 2
H 1 2.32 10 2
E 1 2.32 110 3
O 1 2.32 111 3
TOTAL number of bits: 10
10 Li & Drew ! c Prentice Hall 2003Fundamentals of Multimedia, Chapter 7
(5)
(a)
L,H:(3) E,O:(2)
0 1
(5)
(3)
H:(1) E:(1) O:(1)
(2)
L:(2)
0 1
(b)
0 1
0 1
Fig. 7.4 Another coding tree for HELLO by Shannon-Fano.
11 Li & Drew ! c Prentice Hall 2003Fundamentals of Multimedia, Chapter 7
Table 7.2: Another Result of Performing Shannon-Fano
on HELLO (see Fig. 7.4)
Symbol Count log2 1
pi
Code # of bits used
L 2 1.32 00 4
H 1 2.32 01 2
E 1 2.32 10 2
O 1 2.32 11 2
TOTAL number of bits: 10
12 Li & Drew ! c Prentice Hall 2003Fundamentals of Multimedia, Chapter 7
Huffman Coding
ALGORITHM 7.1 Huffman Coding Algorithm — a bottomup approach
1. Initialization: Put all symbols on a list sorted according to
their frequency counts.
2. Repeat until the list has only one symbol left:
(1) From the list pick two symbols with the lowest frequency counts.
Form a Huffman subtree that has these two symbols as child nodes
and create a parent node.
(2) Assign the sum of the children

Kết quả (Việt) 1:

Nguyên tắc cơ bản của đa phương tiện, chương 7Chương 7Thuật toán nén lossless7.1 giới thiệu7.2 khái niệm cơ bản của lý thuyết thông tin7.3 quản-độ dài mã hóa7.4 biến-độ dài mã hóa (VLC)7,5 dictionary dựa trên mã hóa7,6 mã hóa số học7.7 hình ảnh lossless nén7.8 tiếp tục thăm dò1 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, chương 77.1 giới thiệu• Nén: quá trình mã hóa mà sẽ có hiệu quảgiảm số lượng bit cần thiết để đại diện cho một sốthông tin.Mã hóa(nén)Bộ giải mã(giải nén)Lưu trữ hoặcmạng lướiĐầu vào đầu radữ liệu dữ liệuHình 7.1: Một chương trình nén dữ liệu nói chung.2 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, chương 7Giới thiệu (cont 'd)• Nếu các quá trình nén và giải nén gây nothông tin giảm cân, sau đó các chương trình nén là lossless;Nếu không, nó là lossy.• Tỷ lệ nén:tỉ lệ nén =B0B1(7.1)B0-số bit trước khi nénB1-số bit sau khi nén3 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, chương 77.2 khái niệm cơ bản của lý thuyết thông tin• Entropy η của một nguồn thông tin với chữ cái S ={s1, s2,..., sn} là:Η = H (S) =n!i = 1Pi log21 pi(7.2)= −n!i = 1Pi log2 pi (7.3)Pi-xác suất biểu tượng si sẽ xảy ra trong S.log2 1Pi-cho biết số lượng thông tin (thông tin tựtheo định nghĩa của Shannon) chứa trong si, tương ứngsố lượng bit cần thiết để mã hóa si.4 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, chương 7Phân phối của cường độ cấp độ xám0 0255 25512/31/31/256(a) (b).tôi tôipi piHình 7.2 Histograms cho hai cấp độ màu xám hình ảnh.• Hình 7.2(a) cho thấy biểu đồ của một hình ảnh với các phân phối đồng đều của cường độ xám cấp, ví dụ, ∀i pi = 1/256.Do đó, dữ liệu ngẫu nhiên của hình ảnh này là:log2 256 = 8 (7.4)5 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, chương 7Entropy và mã dài• Có thể nhìn thấy ở Eq. (7.3): entropy η là một weighted-tổng hợptrong điều khoản log2 1Pi; do đó, nó đại diện cho số lượng trung bìnhthông tin cho mỗi biểu tượng trong mã nguồn S.• Η dữ liệu ngẫu nhiên chỉ định ràng buộc thấp nhất số bit để mã mỗi biểu tượng thuộc S, tức là, Trung bìnhΗ ≤ ¯ l (7,5)¯ l - độ dài trung bình (đo bằng các bit) của các codewordssản xuất bởi các bộ mã hóa.6 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, chương 77.3 quản-độ dài mã hóa• Nguồn memoryless: một nguồn thông tin được phân phối một cách độc lập. Cụ thể, giá trị của các biểu tượng hiện tạikhông phụ thuộc vào giá trị của xuất hiện trước đóCác biểu tượng.• Thay vì giả định nguồn memoryless, chiều dài chạy mã hóa(RLC) khai thác bộ nhớ hiện diện trong các nguồn thông tin.• Các lý do cho RLC: nếu các nguồn thông tin có tính chất biểu tượng có xu hướng để tạo thành các nhóm liên tục, sau đó như vậybiểu tượng và chiều dài của các nhóm có thể được mã hoá.7 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, chương 77.4 biến-độ dài mã hóa (VLC)Thuật toán Shannon-Fano-một cách tiếp cận từ trên xuống1. sắp xếp biểu tượng theo tần số đếm của họCác sự kiện.2. đệ quy các biểu tượng phân chia thành hai phần, mỗi khoảng cùng một số đếm, cho đến khi tất cả các bộ phận chứa chỉ có một biểu tượng.Ví dụ: mã hóa của "Xin CHÀO"Biểu tượng H E L OĐếm 1 1 2 1Tần số của các biểu tượng trong "Xin CHÀO".8 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, chương 7L:(2)(5)H,E,O:(3)(a)0 1(b)L:(2)(5)H:(1) E,O:(2)(3)0 10 1L:(2)O:(1)(5)E:(1)H:(1)(c)(2)(3)0 10 10 1Hình 7.3: Mã hóa cây cho HELLO của Shannon-Fano.9 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, chương 7Bảng 7.1: Kết quả thực hiện Shannon-Fano trên HELLOBiểu tượng tính log2 1PiMã số bit được sử dụngL 2 1.32 0 2H 1 2,32 10 2E 1 2,32 110 3O 1 2,32 111 3TỔNG số bit: 1010 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, chương 7(5)(a)L,H:(3) E,O:(2)0 1(5)(3)H:(1) E:(1) O:(1)(2)L:(2)0 1(b)0 10 1Hình 7.4 mã hóa một cây cho HELLO của Shannon-Fano.11 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, chương 7Bảng 7.2: Một kết quả thực hiện Shannon-Fanotrên HELLO (xem hình 7.4)Biểu tượng tính log2 1PiMã số bit được sử dụngL 2 1.32 00 4H 1 2,32 01 2E 1 2,32 10 2O 1 2,32 11 2TỔNG số bit: 1012 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, chương 7Mã hóa HuffmanThuật TOÁN 7.1 các thuật toán mã hóa Huffman-một cách tiếp cận bottomup1. khởi tạo: Đặt tất cả các biểu tượng trên một danh sách được sắp xếp theotần số của họ đếm.2. lặp lại cho đến khi danh sách chỉ có một biểu tượng còn lại:(1) từ danh sách lựa chọn các biểu tượng hai với số lượng tần số thấp nhất.Tạo thành một subtree Huffman có các biểu tượng hai như nút convà tạo ra các nút cha mẹ.(2) Ấn định tổng số trẻ em

Kết quả (Việt) 2:

Nguyên tắc cơ bản của đa phương tiện, Chương 7
Chương 7
Lossless nén thuật toán
7.1 Giới thiệu
7.2 Khái niệm cơ bản của thông tin Lý thuyết
7.3 Run-Length Mã hóa
7.4 Variable-Length Mã hóa (VLC)
7,5 từ điển dựa trên Mã hóa
7,6 Arithmetic Mã hóa
7,7 Lossless Nén ảnh
7.8 Hơn nữa thăm dò
1 Li & Drew ! c Prentice Hall 2003Fundamentals đa phương tiện, Chương 7
7.1 Giới thiệu
• Nén: quá trình mã hóa sẽ có hiệu quả
làm giảm tổng số bit cần thiết để đại diện cho một số
thông tin.
Bộ mã hóa
(nén)
Decoder
(giải nén)
lưu trữ hoặc
mạng
đầu vào đầu ra
dữ liệu dữ liệu
hình. 7.1. Một nén dữ liệu chung Đề án
2 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, Chương 7
Giới thiệu (tt)
• Nếu các quá trình nén và giải nén gây ra không
mất mát thông tin, sau đó các chương trình nén là lossless;
nếu không, nó là lossy.
• Tỉ số nén:
tỷ số nén =
B0
B1
( 7.1)
B0 - số bit trước khi nén
B1 - số bit sau khi nén
3 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, Chương 7
7.2 Khái niệm cơ bản của lý thuyết thông tin
• Entropy η của một nguồn thông tin với bảng chữ cái S =
{s1, s2,. . . , Sn} là:
η = H (S) =
n!
I = 1
pi log2
1 pi
(7,2)
= -
n!
I = 1
pi pi log2 (7.3)
pi - xác suất mà biểu tượng si sẽ xảy ra trong S.
log2 1
pi
- chỉ ra số lượng thông tin (tự thông tin
theo quy định của Shannon hóa) trong si, tương ứng
với số bit cần thiết để mã hóa si.
4 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, Chương 7
Phân phối của Gray-Level cường độ
0 0
255 255
1
2/3
1/3
tới 1/256
(a) (b)
ii
pi pi
hình. 7.2 Biểu đồ cho hai Xám cấp hình ảnh.
• Hình. . 7.2 (a) cho thấy biểu đồ của hình ảnh với phân bố đồng đều của các cường độ màu xám cấp, tức là, ∀i pi = 1/256
Do đó, entropy của hình ảnh này là:
log2 256 = 8 (7.4)
5 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, Chương 7
Entropy và Mã Chiều dài
• Như có thể thấy trong phương trình. (7.3): các η entropy là một trọng-sum
ngữ log2 1
pi
; do đó nó đại diện cho số lượng trung bình của
thông tin chứa mỗi biểu tượng trong nguồn S.
• Các η entropy xác định thấp hơn giới hạn cho số lượng trung bình của các bit để mã mỗi ký hiệu S, tức là,
η ≤ ¯ l (7.5)
¯ l - các chiều dài trung bình (đo bằng bit) của từ mã
được sản xuất bởi các bộ mã hóa.
6 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, Chương 7
7.3 Run-Length Mã hóa
• không nhớ nguồn: một nguồn thông tin được phân phối độc lập. Cụ thể, giá trị của các biểu tượng hiện tại
không phụ thuộc vào các giá trị của xuất hiện trước đó
. Ký
• Thay vì giả định nguồn không nhớ, Run-Length Mã hóa
(RLC) khai thác bộ nhớ có mặt trong nguồn thông tin.
• Cơ sở cho RLC: nếu thông tin nguồn có tính rằng các biểu tượng có xu hướng hình thành các nhóm liên tục, sau đó như
biểu tượng và độ dài của nhóm có thể được mã hóa.
7 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, Chương 7
7.4 Variable-Length Mã hóa (VLC)
Shannon-Fano Algorithm - một cách tiếp cận từ trên xuống
1. Sắp xếp các biểu tượng theo số lượng tần số của họ
xuất hiện.
2. Đệ quy chia những biểu tượng thành hai phần, mỗi phần với khoảng cùng một số đếm, cho đến khi tất cả các phần chỉ chứa một biểu tượng.
Một ví dụ: mã hóa của "HELLO"
Symbol HELO
Đếm 1 1 2 1
đếm tần số của các biểu tượng trong "HELLO".
8 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, Chương 7
L: (2)
(5)
H, E, O: (3)
(a)
0 1
(b)
L: (2)
(5)
H: (1) E, O : (2)
(3)
0 1
0 1
L: (2)
O: (1)
(5)
E: (1)
H: (1)
(c)
(2)
(3)
0 1
0 1
0 1
Hình . 7.3. Mã hóa Tree cho Hello bởi Shannon-Fano
9 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, Chương 7
Bảng 7.1: Kết quả của biểu Shannon-Fano trên Hello
Symbol Đếm log2 1
pi
Mã # bit được sử dụng
L 2 1,32 0 2
H 1 2.32 10 2
E 1 2.32 110 3
O 1 2.32 111 3
TỔNG số bit: 10
10 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, Chương 7
(5)
(a)
L, H: (3) E, O: (2)
0 1
(5)
(3)
H: (1) E: (1) O :( 1)
(2)
L: (2)
0 1
(b)
0 1
0 1
hình. 7.4 Một cây mã hóa cho Hello bởi Shannon-Fano.
11 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, Chương 7
Bảng 7.2: Một quả biểu diễn Shannon-Fano
trên Hello (xem hình 7.4).
Symbol Đếm log2 1
pi
Mã # bit được sử dụng
L 2 1,32 00 4
H 1 2.32 01 2
E 1 2.32 10 2
O 1 2.32 11 2
TỔNG số bit: 10
12 Li & Drew! c Prentice Hall 2003Fundamentals đa phương tiện, Chương 7
Huffman Mã hóa
THUẬT TOÁN 7.1 Huffman Mã hóa Algorithm - một cách tiếp cận bottomup
1. Khởi tạo: Đặt tất cả các ký hiệu trên một danh sách được sắp xếp theo
số lượng tần số của chúng.
2. Lặp lại cho đến khi danh sách chỉ có một biểu tượng trái:
. (1) Từ danh sách chọn hai biểu tượng với số lượng tần số thấp nhất
Hình thành một cây con Huffman rằng có hai biểu tượng này như là nút con
và tạo ra một nút cha.
(2) Gán tổng của trẽ con