Chương 7: Nén Ảnh

245
Chương 7

NÉN ẢNH
7.1 Tổng quan về nén dữ liệu ảnh
7.1.1 Một số khái niệm
Ảnh sau khi thu nhận thường có kích thước và dữ liệu rất lớn nhất là trong
các ảnh viễn thám, ảnh phong cảnh…nên ta cần nén ảnh ñể giảm bớt các dữ liệu
dư thừa không cần thiết ñể việc xử lý ñược nhanh hơn.
 Khái niện ảnh BMP (Bitmap)
Ảnh BMP sử dụng 3 bytes cho các pixel của ba màu R, G, B. ðược mô tả
2
24
=16.7 triệu màu. Kích thước file = 3*chiềudài*chiều cao, sẽ rất lớn, chúng ta
có thể sử dụng ít hơn 8 bit cho một màu, nhưng chúng ta cần lưu với loại màu
khác. Có thể thực hiện tốt với kiểu ZIP, RAR, …

Hình 7.1 Ảnh BMP

Chương 7: Nén Ảnh

246


ố lần nén và tốc ñộ nén ñược ñịnh nghĩa:
(7.1)
7.1.2 Các loại dư thừa dữ liệu
 Phân bố ký tự:
−
 
= = •
 
1 1 2
2 1
laàn ; 100%[%]
n n n
C R
n n

Chương 7: Nén Ảnh

248
Trong một dãy ký tự, có một số ký tự có tần suất xuất hiện nhiều hơn so với
các dãy khác. Các dãy ký tự có tần suất cao ñược thay bởi một từ mã nhị phân
với số bit nhỏ; ngược lại các dãy có tần suất xuất hiện thấp sẽ ñược mã hóa bởi từ
mã có nhiều bit hơn. ðây chính là bản chất của phương pháp mã hóa từ hóa
Huffman.
 Các ký tự lặp lại:
Một ký hiệu (bit “0” hoặc “1”) lặp lại nhiều lần. Có thể thay dãy ký tự lặp
bằng dãy mới có 2 thành phần (số lần lặp và ký hiệu mã). ðây là ñặc tính của mã

tin chói hơn).
o Bỏ bớt các thành phần tần số không gian quá cao (nằm ngoài vùng nhìn thấy
của mắt).
o Giảm ñộ phân giải không gian của ảnh. Cắt bớt ảnh.
o Bỏ bớt các thông tin ít quan trọng (số lượng màu biểu diễn ảnh (ảnh màu 24
bit có 16,7 triệu màu, ảnh màu 15 bit, ảnh màu 8 bit có 256 màu), ảnh ñen
trắng, ảnh nhị phân): Giảm ñộ phân giải màu và chói.
c. ðộ dư thừa của ảnh ñộng
ðối với ảnh ñộng ñộ dư thừa gồm ñộ dư thừa không gian và thời gian, khi
thực hiện cũng cần ñược quan tâm ñến, việc nén ảnh bằng cách loại bỏ dư thừa
không gian trong ảnh ñộng nhằm:
o Bỏ bớt ñộ dư thừa không gian (spatial redundancy): Các pixels lân cận trong
không gian có ñộ tương phản cao.
o Bỏ bớt ñộ dư thừa thời gian (temporal redundancy): Các ảnh liên tiếp nhau
có ñộ tương quan cao
o ðộ dư thừa phổ (spectral redundancy): Các thành phần màu (biểu diễn từng
pixel) có ñộ tương quan cao.
o ðộ dư thừa thống kê (statistical redundancy) các ký hiệu (symbol) xuất hiện
trong dòng bit với xác suất xuất hiện không ñồng ñều.
o ðộ dư thừa tâm lý thị giác (psychovisual redundancy): Các thông tin không
phù hợp với thị giác, giảm thành phần tần số không gian cao (giảm ñộ nét)
o Giảm ñộ phân giải không gian (giảm số lượng pixels trên ảnh, → giảm kích
thước ảnh).

Chương 7: Nén Ảnh

250

7.2 Các loại nén
ảnh dữ
7.2.1 Các loại nén
Trong
ảnh nén (
số nén cao chất lư
ợng
(Ví dụ nén 40%)
 Nén không t
ổn hao (l
 Nén có t
ổn hao (lossy
hợp v
à không quan tr
7.2.2 Cơ s
ở toán học về né
X: ngu
ồn tín hi
các biến ngẫu
nhiên X
hiệu A chứa 1 lư
ợng h
 Hai mô hình toán h
ọc
o Ngu
ồn không nhớ
o Ngu
ồn Markov

251

A = {a
ợng hữu hạn M ký hiệu

ọc cho nguồn tín hiệu

ng nhớ rời r
ạc (discrete memoryless source)
rkov
- K
Chương 7: Nén Ảnh
g ñến chữ, ñặc biệt khi tỉ

ần thông tin không ph
ù

ẫu nhi
ên rời rạc (chuỗi
= {a
1
, a
2
,…, a
M
}, bộ ký

Chương 7: Nén Ảnh


log ;
i i
i
I a a A
p a

(7.3)
+ I(a
i
) – lượng tin
+ p=1, → I=0
+ p=0, → I → ∞
o Entropy của nguồn không nhớ:
( )
( )
( )
∈ ∈
 
 
= =
 
 
∑ ∑
2 2
1
( )log ( )log
a A a A
H x p a p a p a
p a


253
∈
− − − − − −
=
∑
1 1 1
( ) ( )log ( )
, , , , , ,
i
a A
j j k j j k j j k
a
X X
H p p
x x x x x x

(7.6)

S
k
- mọi thể hiện có thể của x
j-1
,…, x
j-k

7.2.3 Các ñịnh lý cơ bản về nén tín hiệu
a. ðịnh lý mã hoá không tổn hao (Shannon 1948)
o Tốc ñộ min. Khi mã hoá không tổn hao (nén không tổn hao) của 1 nguồn
không nhớ rời rạc X là:
min {R}=H(X) +

ệu
∆. T
ốc ñộ bit thực
R
≥
R(
∆
)

Chú ý:
R(0) = H(X) (m
ñ
ạt R thấp nhất
Hình
7.3 Phương pháp
nén
7.3.1 Giới thiệu các ph
ươ
a. Dựa theo nguy
ên l
o H
ọ nén không tổ
o H
ọ nén có tổn hao
b. Dựa vào cách th
ức
o H
ọ nén không gia
gian.
o H

ợc chín
tổn hao: sau khi giải nén, không thu ñ
ư
ợc chính
ức nén

ng gian: tá
c ñộng trực tiếp lên vi
ệc lấy mẫu ảnh
ng m
ã bi
ến ñổi: (transform coding) tác ñộng l
ý m
ã hoá
hệ 1:
Ví dụ lấy mẫu, gán từ mã
Chương 7: Nén Ảnh
ối với mỗi
∆ cho trước,
ng bì
nh có giá trị tiến về
(7.8)

ết kế 1 hệ thống nén ñể c chính xác dữ liệu gốc.

chính xác dữ liệu gốc.


ối (Blo
o
Mã hóa thích ngh
o S
ử dụng DCT (19
a. Mã hóa RLC
 Nguyên tắc:
o Phát hi
ện một loạ
dãy bit lặp gọi l
à
o Sau ñó thay lo
ạt b
(ký t
ự lặp)), do ñó

255
hệ 2:
Dựa vào mức bảo hoà tỉ lệ nén.
Jain

pháp ñi
ểm
pháp d
ự ñoán
pháp dùng bi
ến ñổi
pháp
kết hợp (hybrid)
Hình 7.7 Các giai ñoạn nén ảnh


Chương 7: Nén Ảnh

256
 Thuật toán:
o Nếu chuỗi lặp > 255, ta tách thành 2 chuỗi: (1 chuỗi có chiều dài 255 + chuỗi
còn lại)
o RLC dùng mã hoá lưu trữ ảnh Bitmap: theo dạng PCX, BMP
o RLC có 2 phương pháp nhỏ:
+ Dùng chiều dài từ mã cố ñịnh
+ Thích nghi kiểu Huffman.
 Dạng thức nén

Hình 7.8 Dạng thức nén loạt dài
+ Sc: Ký tự ñể nhận biết ký tự nén.
+ X: Dữ liệu nén
+ Cc: giá trị lặp lại của dữ liệu nén
 Ví dụ 1:

 Hiệu quả của mã hóa RLC
 Ví dụ 2:

ại: 23 4 6 1 2 1 6 4 9 1 9 1 6 4 23

ạy ñ
ơn giản: 15 ký tự






331
1
533
3
444
4
111
1

iá trị
ảnh gốc:
Chương 7: Nén Ảnh

Chương 7: Nén Ảnh

(β
ββ
β) Giải nén: thực hiện ngược lại khi nén

Chương 7: Nén Ảnh

259
o Bảng mã khi nén ñược giữ lại cùng với dữ liệu nén trong cấu trúc ñầu.
o Mã của ký tự là duy nhất, không có mã nào là bắt ñầu của mã khác (trong
Huffman). Khi ñọc tập nén từng bit từ ñầu ñến cuối, có thể duyệt cây mã cho
ñến 1 lá (tức là ký tự ñã ñược giải nén)
 Ví dụ 1:
Mã nhị phân: Mỗi ký hiệu ñược mô tả bằng chuỗi nhị phân riêng.
o Một tập dữ liệu có thể ñược mô tả theo 2 cách
Kí hiệu
a b c d e f
Tần suất (%)
45 13 12 16 9 5
Mã cố ñịnh
000 001 010 011 100 101
Mã thay ñổi
0 101 100 111 1101 1100
o Mã cố ñịnh có chiều dài là:
L
F
=(45x3)+(13x3)+(12x3)+(16x3)+(9x3)+(5x3)
=3x100=300 bit

ợc biểu di

260
ải m
ã: Sử dụng từ mã trong bảng sau ñể m
ã h
: abc = 0.101.100 = 0101100
. (ch
ỉ khoảng cách
ã: 001011101 = 0.0.101.1101 = aabe

a b c d e

45 13 12 16 9
000 001 010 011
100
0 101 100 111
1101
iểu diễn chiều d
ài từ mã cố ñịnh
Hình 7.10 Cây nh
ị phân (mã cố ñịnh)
iểu diễn chiều d
ài từ mã thay ñổi
Chương 7: Nén Ảnh
ã hóa và gi
ải mã
g cách giữa các từ m
ã)
f

Hình 7.11 Cây Huffman (mã
thay ñổi)
ớc vẽ cây Huffman

gồm 6 ký hiệu: a
1
, a
2
, a
3
, a
4
, a
5
, a
6

ất hiện (
xác su
ất): số lần các ký hiệu xuất hiện t
cây v
à sau m
ỗi lần kết hợp hai giá trị ta lại sắp
tính từ t
rên xuống theo cột) ta ñược bảng
ừ m
ã cho cây Huffman theo như qui ñ
ịnh: t
ng. Các giá trị có tần suất xuất hiện nhiều sẽ c
à ngư

à gán từ mã cho các ký hiệu sau
0,387; B có tần suất 0,194; C có tần suất 0,1
suất 0,129

cây Huffman theo giá trị cho tr
ước
Hình 7.12 Cây Huffman cho ví dụ 4

ằng cách ghi nhận giá trị tr
ên các nhánh t
Chương 7: Nén Ảnh

ất 0,161; D có tần suất hánh t
ừ nút ñến từng ký

Chương 7: Nén Ảnh

263
Ký hiệu Từ mã
A 0
B 111
C 110
D 100
E 101

 Cách chèn mẫu không có trong từ ñiển
o Nếu chỉ có một mẫu không có trong từ ñiển thì chèn vào (0,Ký tự).
o Nếu có nhiều mẫu không có trong từ ñiển thì chèn vào (chỉ số cố ñịnh trong
từ ñiển, mẫu ký tự sau ñó).
o Nếu một ký tự vào hay mẫu ra cuối cùng có trong từ ñiển thì (chỉ số cố ñịnh
trong từ ñiển, ).
 Ví dụ 1
o Mã hóa chuỗi ABBCBCABABCAABCAAB sử dụng thuật toán mã hóa từ
ñiển

o Mã nén ngõ ra: (0,A)(0,B)(2,C) (3,A)(2,A)(4,A) (6,B)

Chương 7: Nén Ảnh

265
o Các bước chèn từ mã
1. A thì không có trong từ ñiển nên chèn vào
2. B thì không có trong từ ñiển nên chèn vào
3. B ñã có trong từ ñiển.
BC thì không có trong từ ñiển nên chèn vào
4. B ñã có trong từ ñiển.
BC ñã có trong từ ñiển.
BCA thì không có trong từ ñiển nên chèn vào
5. B ñã có trong từ ñiển.
BA thì không có trong từ ñiển nên chèn vào
6. B ñã có trong từ ñiển.
BC ñã có trong từ ñiển.

o Mã ñoạn (khối kxl) tự ñộng thích nghi với tác ñộng cục bộ.
o Mã ñoạn khối (kxl) tự ñộng thích nghi một chiều

Chương 7: Nén Ảnh

267
o Mã khối (kxl) tự ñộng thích nghi 2 chiều
o Khi sử dụng phương pháp mã hóa Huffman sẽ không ñược nén tốt nếu ta
không quan tâm ñến ñặc tính của ký hiệu trong các file nén.
+ Vì thế sẽ làm tăng số bit mã hóa
+ Nếu thông tin này không thay ñổi khi nén thì nó yêu cầu thực thi 2 phần
 Phần 1: Tìm tần suất của mỗi ký hiệu và cấu trúc trên cây Huffman
 Phần 2: Nén file
o Ý tưởng chính là xây dựng cây Huffman tối ưu ñể phần tin thấy ñược rõ ràng
và dễ nhận ra nó khi cần thiết và ñồng thời ñể duy trì ñặc tính tối ưu của nó.
o Mã hóa Huffman thích nghi ñược Faller (1973) và Gallager (1978) thực hiện
ñầu tiên
o Knuth (1985) kết hợp và cải tiến thuật toán nên thuật toán có tên là thuật toán
FGK.
o Sau ñó (1987) một phiên bản mới của thuật toán thích nghi Huffman ñược
mô tả bởi Vitter nên ñược gọi là thuật toán V.
o Một ñiểm vượt trội hơn của mã hóa Huffman thích nghi so với mã hóa
Huffman cố ñịnh là ñôi khi một phần thông tin của phương pháp mã hóa
Huffman thích nghi cố ñịnh có dữ liệu nén lớn hơn lúc chưa nén.
o Như vậy chúng ta ñánh giá thế nào về việc giảm dư thừa tối thiểu của dữ liệu
và tính tối ưu của thuật toán Huffman cố ñịnh
 ðặc tính của phương pháp

sao cho các hệ số trong tập giá trị mới này có tương quan giữa các ñiểm ảnh gần
nhau nhỏ hơn.
 DCT 1 chiều:
Thời gian thực hiện chỉ bằng ½ thời gian trong phép biến ñổi Fourier tĩnh
ε
−
=
 
Π +
=
 
 
∑
1
0
2
(2 1)
( ) ( )cos
2
N
k
n
n k
X k x n
N N

(7.9)

=
− −
'( ) (
'( )
x i X
x N i l269
=
= −
; 0
; [1, 1]
k
k N

vào

–
fast cosine Transform)
hân nhỏ d
ãy tín hiệu vào cho ñến khi còn 1 ph
ần
ực hiện tr
ên chuỗi vào x(n), mà th
ực hiện tr
x(n)).

ình 7.14 Khôi ph
ục ảnh dùng biến ñổi DCT