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) 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