Bài giảng Xử lý tín hiệu và mã hóa - Chương 5: Nén dữ liệu ảnh - Phạm Việt Hà

Xử lý tín hiệu và mã hóa
(Master program)
Giảng viên: TS. Phạm Việt Hà
Email: phamvietha@gmail.com
ĐT CQ: (04).37544486
Địa chỉ CQ: 122 Hoàng Quốc Việt, Cầu Giấy, Hà Nội
1
Chương 5. Nén dữ liệu ảnh
Viện Khoa học Kỹ thuật Bưu điện 2
5.1 Giới thiệu chung
5.2 Phân loại các thuật toán nén ảnh
5.3 Các bước trong nén ảnh
5.3 Thuật toán mã hóa Huffman
5.1. Giới thiệu chung
Viện Khoa học Kỹ thuật Bưu điện 3
So sánh kích thước ảnh gốc và ảnh nén:
 Bức ảnh màu bên: 352 x 288 điểm ảnh
 Hiển thị dưới dạng RGB: 24 bit
(8 bit cho mỗi màu Đỏ-Lục-Lam)
 Kích thước ảnh > 300Kbyte
 Với tiêu chuẩn JPEG thì kích thước của ảnh
dưới < 20Kbyte với chất lượng tương đương
5.1. Giới thiệu chung
Viện Khoa học Kỹ thuật Bưu điện 4
So sánh kích thước file Video và tốc độ môi trường truyền
5.1. Giới thiệu chung
Viện Khoa học Kỹ thuật Bưu điện 5
Tính chất dư thừa thông tin của ảnh số:
Tương quan giữa các điểm ảnh ở cạnh nhau trong ảnh số là lớn, điều này dẫn đến 
dư thừa thông tin để biểu diễn ảnh. Dư thừa thông tin sẽ làm cho việc mã hoá 
không tối ưu. Do đó công việc cần làm để nén ảnh là phải tìm được các biểu diễn 
ảnh với tương quan nhỏ nhất để giảm thiểu độ dư thừa thông tin của ảnh. Thực 
tế, có hai kiểu dư thừa thông tin được phân loại như sau:
- Dư thừa trong miền không gian: tương quan giữa các giá trị pixel của ảnh, điều 
này có nghĩa rằng các pixel lân cận của ảnh có giá trị gần giống nhau (trừ những 
pixel ở giáp đường biên ảnh).
- Dư thừa trong miền tần số: Tương quan giữa các mặt phẳng màu hoặc dải phổ 
khác nhau.
Trọng tâm của các nghiên cứu về nén ảnh là tìm cách giảm số bit cần để biểu 
diễn ảnh bằng việc loại bỏ dư thừa trong miền không gian và miền tần số càng 
nhiều càng tốt.
5.2. Phân loại các thuật toán nén ảnh 
Viện Khoa học Kỹ thuật Bưu điện 6
 Nén ảnh không mất thông tin: với phương pháp này sau khi giải nén ta khôi 
phục được chính xác ảnh gốc. Các phương pháp nén này bao gồm mã hoá 
Huffman, mã hoá thuật toán
 Nén ảnh có mất thông tin: ảnh giải nén có một sự sai khác nhỏ so với ảnh 
gốc. Các phương pháp này bao gồm:
 Lượng tử hoá vô hướng: PCM và DPCM
 Lượng tử hoá vector
 Mã hoá biến đổi: biến đổi cosin rời rạc (DCT), biến đổi Fourier nhanh (FFT)
 Mã hoá băng con
5.3. Các bước trong nén ảnh 
Viện Khoa học Kỹ thuật Bưu điện 7
Các bước nén ảnh:
1. Biến đổi: biến đổi hệ màu RGB sang hệ màu YCrCb
2. Chia nhỏ: phân chia bức ảnh thành các thành phần nhỏ 8x8 pixel
3. Biến đổi DCT thuận: biến đổi cosin rời rạc DCT nhằm biến các giá trị pixel 
của ảnh trong miền không gian sang các giá trị khác trong miền tần số sao cho 
các giá trị mới này có tương quan giữa các điểm ảnh gần nhau nhỏ hơn.
4. Lượng tử hóa
5. Mã hóa
5.3. Các bước trong nén ảnh 
Viện Khoa học Kỹ thuật Bưu điện 8
Biến đổi: Trong không gian màu YCrCb hoặc YUV nhãn thị của con người rất 
nhạy cảm với thành phần Y (độ sáng) và kém nhạy cảm với hai loại Cr, Cb hoặc
U, V (hai thành phần màu). Cr và Cb là phiên bản biến thể của U và V. Phương 
pháp nén ảnh nắm bắt phát hiện này để tách những thông tin thừa của ảnh. Hệ 
thống nén thành phần Y của ảnh với mức độ suy giảm ít hơn so với Cr, Cb hoặc
U,V bởi người ta ít nhận thấy sự thay đổi của Cr, Cb hoặc U,V so với Y.
Y = 0.299R + 0.587G + 0.114B
U= 0.492(B − Y) = − 0.147R − 0.289G + 0.436B
V= 0.877(R − Y) = 0.615R − 0.515G − 0.100B
5.3. Các bước trong nén ảnh 
Viện Khoa học Kỹ thuật Bưu điện 9
Biến đổi:
Ảnh gốcẢnh gốc
R
G
B
Y
Cr
Cb
5.3. Các bước trong nén ảnh 
Viện Khoa học Kỹ thuật Bưu điện 10
Biến đổi:
Lấy mẫu thành phần màu có thể sử dụng mô hình: 4:4:4, 4:2:2, 4:2:0
Khi chuyển đổi từ RGB sang YCrCb ở mô hình 4:4:4 thì hai thành phần màu bị
loại bỏ nên băng thông giảm 50% 
5.3. Các bước trong nén ảnh 
Viện Khoa học Kỹ thuật Bưu điện 11
Chia nhỏ:
Ảnh được phân chia thành các khối vuông, mỗi khối này thường có kích thước 8 
x 8 pixel và biểu diễn các mức xám của 64 điểm ảnh, các mức xám này là các số 
nguyên dương có giá trị từ 0 đến 255. Việc phân khối này sẽ làm giảm được một 
phần thời gian tính toán các hệ số chung, mặt khác biến đổi cosin đối với các 
khối nhỏ sẽ làm tăng độ chính xác khi tính toán với dấu phẩy tĩnh, giảm thiểu sai 
số do làm tròn sinh ra.
5.3. Các bước trong nén ảnh 
Viện Khoa học Kỹ thuật Bưu điện 12
Biến đổi DCT thuận:
Mỗi khối 64 điểm ảnh sau biến đổi DCT thuận sẽ nhận được 64 hệ số thực DCT. 
Mỗi hệ số này có chứa một trong 64 thành phần tần số không gian hai chiều. Hệ 
số với tần số bằng không theo cả hai hướng (tương ứng với k1 và k2 bằng 0) 
được gọi là hệ số một chiều DC, hệ số này chính là giá trị trung bình của 64 điểm 
ảnh trong khối. 63 hệ số còn lại gọi là các hệ số xoay chiều AC. Hệ số một chiều 
DC tập trung phần lớn năng lượng của ảnh.
5.3. Các bước trong nén ảnh 
Viện Khoa học Kỹ thuật Bưu điện 13
Biến đổi DCT thuận: Chú ý rằng bản thân biến đổi DCT không làm mất 
thông tin vì DCT là một biến đổi tuyến tính chuyển các giá trị của điểm ảnh từ 
miền không gian thành các hệ số trong miền tần số
Miền thời gian
Miền tần số
5.3. Các bước trong nén ảnh 
Viện Khoa học Kỹ thuật Bưu điện 14
Lượng tử:
Sau khi thực hiện biến đối DCT, 64 hệ số sẽ được lượng tử hoá dựa trên một 
bảng lượng tử gồm 64 phần tử Q(u,v) với 0≤u, v≤7. Bảng này được định nghĩa 
bởi từng ứng dụng cụ thể. Các phần tử trong bảng lượng tử có giá trị từ 1 đến 
255 được gọi là các bước nhảy cho các hệ số DCT. Quá trình lượng tử được coi 
như là việc chia các hệ số DCT cho bước nhảy lượng tử tương ứng, kết quả này 
sau đó sẽ được làm tròn xuống số nguyên gần nhất.
Mục đích của việc lượng tử hoá là giảm số lượng bit cần để lưu trữ các hệ số 
biến đổi bằng việc giảm độ chính xác của các hệ số này cho nên lượng tử là quá 
trình xử lý có mất thông tin (mã hóa Entropy)
Bảng lượng tử được đặt trong phần header của ảnh
5.3. Các bước trong nén ảnh 
Viện Khoa học Kỹ thuật Bưu điện 15
Lượng tử:
Các hệ số thu được sau khi lượng tử hoá sẽ được sắp xếp thành một chuỗi các ký 
hiệu theo kiểu “zig-zag” để đặt các hệ số có tần số thấp lên trước các hệ số tần số 
cao. Các hệ số này sẽ được mã hoá dựa trên bảng mã Huffman sao cho chiều dài 
trung bình của từ mã là nhỏ nhất. Bảng mã này cũng sẽ được đặt trong phần mào 
đầu của ảnh để thực hiện giải nén ảnh
5.3. Các bước trong nén ảnh 
Viện Khoa học Kỹ thuật Bưu điện 16
Lượng tử:
5.3. Các bước trong nén ảnh 
Viện Khoa học Kỹ thuật Bưu điện 17
Mã hóa:
Mã hoá là bước cuối cùng trong hệ thống nén ảnh dựa trên biến đổi DCT. Chuẩn 
nén ảnh JPEG hiện nay dùng phương pháp mã hoá Huffman, đây là phép mã hoá 
không làm mất thông tin. Phương pháp này dựa trên mô hình thống kê. Dựa vào 
dữ liệu gốc, người ta tính tần suất xuất hiện các hệ số. Việc tính tần suất được 
thực hiện bằng cách duyệt tuần tự từ đầu khối đến cuối khối, sau đó, những hệ số 
có tần suất cao được gắn cho một từ mã ngắn, các hệ số có tần suất thấp được 
gán một từ mã dài. Với cách thức này chiều dài trung bình của từ mã đã giảm 
xuống.
5.4. Mã hóa Huffman
Viện Khoa học Kỹ thuật Bưu điện 18
 Bài toán: Có một bản tin là dãy các ký hiệu lấy trong một tập hữu hạn A. Mỗi 
ký hiệu xuất hiện trong bản tin theo một tần suất đã biết. Hãy xây dựng bộ mã 
tiền tố cho tập A sao cho độ dài chuỗi mã của bản tin là ngắn nhất. 
 Kết quả: Bộ mã tìm được mang tính tối ưu và được gọi là bộ mã Huffman
Gọi d là số ký hiệu của bản tin, (x) là tần suất xuất hiện của ký hiệu x
trong bản tin. 
Mỗi cây nhị phân T với nhãn 0,1 trên các cạnh và có số lá bằng số ký hiệu 
của tập A sẽ cho ta một bộ mã tiền tố cho tập ký hiệu A. 
Mức (x) của lá x chính là chiều dài mã của ký hiệu x. Khi đó, độ dài 
chuỗi mã của toàn bộ bản tin sẽ là: M = d. (x) (x).
Cây mã tiền tố T là tối ưu khi độ dài M của mã bản tin đạt giá trị nhỏ nhất. 
5.4. Mã hóa Huffman
Viện Khoa học Kỹ thuật Bưu điện 19
 Ví dụ:
Xét bản tin gồm 1000 ký hiệu trong tập ký hiệu A = {a, b, c, d, e} với tần suất 
xuất hiện của các ký hiệu trong bản tin như sau:
4
d
12174423Tần suất%
ecbaKý hiệu
5.4. Mã hóa Huffman
Viện Khoa học Kỹ thuật Bưu điện 20
da b c e
c d
a b
e
0
0 0
000
0
0
0
0
1
1
1
1
1 1
1
1
 Xây dựng cây mã tiền tố:
Mã hóa tập các ký hiệu này bằng dãy các chữ số 0, 1 thoả mãn tính chất tiền tố, 
nghĩa là không có mã của ký hiệu nào lại là tiền tố của mã của ký hiệu khác
Xây dựng một cây nhị phân sao cho:
- Mỗi ký hiệu tương ứng với một lá, 
- Cạnh xuống con trái của một đỉnh được gán nhãn 0
- Cạnh đi xuống con phải được gán nhãn 1. 
Khi đó, dãy các nhãn trên đường đi từ gốc đến lá sẽ cho mã tiền tố của ký hiệu
tương ứng.
5.4. Mã hóa Huffman
Viện Khoa học Kỹ thuật Bưu điện 21
e
a
b
c
d
0
0
0
0
1
1
1
1
44
23
17
4
56
33
16
12
 Bộ mã tối ưu:
Cây mã tiền tố ở hình vẽ trên được xây dựng dựa trên nguyên lý: đỉnh lá nào có 
tần suất càng lớn thì đường đi từ gốc cây tới đỉnh lá đó càng ngắn.
5.4. Mã hóa Huffman
Viện Khoa học Kỹ thuật Bưu điện 22
205022703000Độ dài mã bản tin
111110100e
1110001011d
11001010c
011001b
10000000a
Bộ mã 3Bộ mã 2Bộ mã 1Ký hiệu
 Kết quả: Độ dài của mã bản tin với Bộ mã 1 và 2 trong ví dụ cây mã tiền tố
và Bộ mã 3 (tối ưu) 
5.3. Mã hóa Huffman
Viện Khoa học Kỹ thuật Bưu điện 23
 Thuật toán Huffman:
1. Xây dựng rừng T có l cây, mỗi cây chỉ gồm một đỉnh tương ứng với một 
ký hiệu x trong A và được gán nhãn (x).
2. Chọn hai cây trong T có gốc với nhãn nhỏ nhất. Thêm một đỉnh mới với 
nhãn là tổng các nhãn của hai gốc cây vừa chọn. Nối đỉnh mới với hai gốc 
này bằng hai cạnh có nhãn 0, 1 để tạo thành một cây nhị phân.
3. Nếu T vẫn chưa phải là một cây thì lặp lại bước 2), ngược lại thì dừng.