NHẬP MÔN XỬ LÝ ẢNH
CHƯƠNG 10: NÉN ẢNH
Biên soạn: TS Ngô Hữu Phúc
1Tham khảo bài giảng ĐH Vanderbilt
Giới thiệu
•
Để có ảnh chất lượng cao (độ nét cao, màu trung thực) thì dung lượng file ảnh
cũng tăng (đáng kể).
–
Ví dụ file ảnh kích thước (640 x 480), sử dụng 24 bit màu sẽ có kích thước: 640 x 480 x 3 =
921600 Byte = 900KB. Kích thước lớn sẽ tốn không gian lưu trữ và thời gian truyền.
•
Để giải quyết vấn đề này người dùng các phương pháp nén đối với file ảnh. Có hai
dạng nén:
–
Nén bảo toàn (không làm mất thông tin) và
–
nén không bảo toàn.
–
Phương pháp thứ hai thường dùng trong truyền hình và một số cấu trúc ảnh.
•
Trong bài này chúng ta chỉ nghiên cứu các phương pháp nén bảo toàn:
–
Mã loạt – Run Length Coding (RLC),
–
mã Huffman,
–
mã LZW.
2Tham khảo bài giảng ĐH Vanderbilt
Phương pháp nén RLC - Mã loạt
Giả sử chúng ta có dãy dữ liệu: aaaaaabbbbbbbbbbccccaaaaacaa

không những không nén được mà thuật toán
còn làm tăng kích thước file lên. Vậy người ta
đã xử lý vấn đề này như thế nào?
Tham khảo bài giảng ĐH Vanderbilt5
Phương pháp nén RLC - Mã loạt
Lưu ý khi cài đặt (Implementation) thuật toán.
•
Thường dùng m=8 bit để biểu diễn li.
•
Dùng bit thấp trong li làm cờ (Flag) - xác định
byte đó là dữ liệu di hay độ dài loạt li (bit cờ
bằng 1→ độ dài loạt, ngược lại → dữ liệu).
Tham khảo bài giảng ĐH Vanderbilt6
Phương pháp nén RLC - Mã loạt
Cách dùng bit cờ:
Người ta có thể dùng 1 bit đầu hoặc 2 bit đầu làm cờ.
•
Dùng 1 bít đầu:
–
Còn lại 7 bít (0-127) thể hiện độ dài loạt → tối đa độ dài loạt có thể là 127.
–
Khi đó các dữ liệu ảnh di riêng lẻ phải có giá trị từ 0000 0000 (0) đến 0111 1111 (127) mới có
thể lưu được trong 1 byte,
–
các di có giá trị từ 1000 0000 (128) đến 1111 1111 (255) vẫn phải lưu trữ trong 2 byte dạng (li,
di) và trường hợp này li =1.
•
Dùng 2 bít đầu:
–
Còn lại 6 bít (0- 63) thể hiện độ dài loạt → tối đa độ dài loạt có thể là 63.

a, 0 - b, khi đó văn bản chỉ cần n bít để lưu trữ
(giảm được 7/8 dung lượng lưu trữ). Như vậy,
tuỳ vào văn bản, nếu chúng ta thay đổi cách
mã có thể nén được dữ liệu.
Tham khảo bài giảng ĐH Vanderbilt9
Phương pháp nén (mã) Huffman
•
Tư tưởng của phương pháp Huffman là:
–
Dùng độ dài thay đổi để mã hóa cho các ký tự,
–
ký tự nào xuất hiện nhiều dùng mã ít bít (ngắn),
–
ký tự nào xuất hiện ít dùng mã nhiều bít (dài).
–
Thông thường độ dài trung bình giảm → nén được thông tin.
•
Phương pháp mã hóa Huffman:
–
xây dựng một cây nhị phân (cây mã Huffman) có các nút lá là các ký tự có trong văn
bản, và
–
tập tin mã hóa sẽ chứa các “đường đi” đến các nút lá (ký tự) của cây nhị phân đó.
•
Việc giải mã được thực hiện như sau:
–
Đọc tuần tự các bit có trong tập tin đã được mã hóa, mỗi bít sẽ cho ta biết hướng đi trên
cây cho đến khi gặp được một nút lá thì sẽ phát sinh ký tự tương ứng,
–
lặp lại quá trình trên cho đến khi hết tập tin.