Nhập môn xử lý ảnh số - Chương 8
Nén Dữ liệu (Data Compression)
Nén dữ liệu là quá trình làm giảm lượng thông tin "dư thừa" trong
dữ liệu gốc và do vậy, lượng thông tin thu được sau nén thường nhỏ hơn
dữ liệu gốc rất nhiều. Với dữ liệu ảnh, kết quả thường là 10 : 1. Một số
phương pháp còn cho kết quả cao hơn. Theo kết quả nghiên cứu được
công bố gần đây tại viện kỹ thuật Georgie, kỹ thuật nén fractal cho tỉ số
nén là 30 trên 1[6]....
Chương Tám: NÉN DỮ LIỆU ẢNH
8
NÉN DỮ LIỆU ẢNH
IMAGE COMPRESSION
8.1 TỔNG QUAN VỀ NÉN DỮ LIỆU ẢNH
Chương này nhằm cung cấp một số khái niệm (thuật ngữ) như:
nén, tỉ lệ nén, các ý tưởng dẫn tới các phương pháp nén khác nhau và cách
phân loại, đánh giá các phương pháp nén.
8.1.1 Một số khái niệm
Nén Dữ liệu (Data Compression)
Nén dữ liệu là quá trình làm giảm lượng thông tin "dư thừa" trong
dữ liệu gốc và do vậy, lượng thông tin thu được sau nén thường nhỏ hơn
dữ liệu gốc rất nhiều. Với dữ liệu ảnh, kết quả thường là 10 : 1. Một số
phương pháp còn cho kết quả cao hơn. Theo kết quả nghiên cứu được
công bố gần đây tại viện kỹ thuật Georgie, kỹ thuật nén fractal cho tỉ số
nén là 30 trên 1[6].
Ngoài thuật ngữ "nén dữ liệu”, do bản chất của kỹ thuật này nó
còn có một số tên gọi khác như: giảm độ dư thừa, mã hoá ảnh gốc.
Từ hơn hai thập kỷ nay, có rất nhiều kỹ thuật nén đã được công
bố trên các tài liệu về nén và các phần mềm nén dữ liệu đã xuất hiện
ngày càng nhiều trên thương trường. Tuy nhiên, chưa có phương pháp nén
nào được coi là phương pháp vạn năng (Universel) vì nó phụ thuộc vào
Nhập môn xử lý ảnh số - ĐHBK Hà nội 227
Chương Tám: NÉN DỮ LIỆU ẢNH
nhiều yếu tố và bản chất của dữ liệu gốc. Trong chương này, chúng ta
không thể hy vọng xem xét tất cả các phương pháp nén. Hơn nữa, các kỹ
thuật nén dữ liệu chung đã được trình bày trong nhiều tài liệu chuyên
ngành. Ở đây, chúng ta chỉ đề cập các phương pháp nén có đặc thù riêng
cho dữ liệu ảnh.
Tỷ lệ nén (Compression rate)
Tỷ lệ nén là một trong các đặc trưng quan trọng nhất của mọi
phương pháp nén. Tuy nhiên, về cách đánh giá và các kết quả công bố
trong các tài liệu cũng cần được quan tâm xem xét . Nhìn chung, người ta
định nghĩa tỷ lệ nén như sau:
1
Tỷ lệ nén = x%
r
với r là tỷ số nén được định nghĩa: r = kích thước dữ liệu gốc/ kích
thước dữ liệu thu được sau nén. Như vậy hiệu suất của nén là : (1 -
tỷ lệ nén) x %.
Trong các trình bày sau, khi nói đến kết quả nén, chúng ta dùng tỷ
số nén, thí dụ như 10 trên 1 có nghĩa là dữ liệu gốc là 10 phần sau khi nén
chỉ có 1 phần.
Tuy nhiên, cũng phải thấy rằng những số đo của một phương
pháp nén chỉ có giá trị với chính sự nén đó, vì rằng hiệu quả của nén còn
phụ thuộc vào kiểu dữ liệu định nén. Tỷ lệ nén cũng chỉ là một trong các
đặc trưng cơ bản của phương pháp nén. Nhiều khi tỷ lệ nén cao cũng
chưa thể nói rằng phương pháp đó là hiệu quả hơn các phương pháp
khác, vì còn các chi phí khác như thời gian, không gian và thậm chí cả độ
Nhập môn xử lý ảnh số - ĐHBK Hà nội 228
Chương Tám: NÉN DỮ LIỆU ẢNH
phức tạp tính toán nữa. Thí dụ như nén phục vụ trong truyền dữ liệu: vấn
đề đặt ra là hiệu quả nén có tương hợp với đường truyền không.
Cũng cần phân biệt nén dữ liệu với nén băng truyền. Mục đích
chính của nén là giảm lượng thông tin dư thừa và dẫn tới giảm kích
thước dữ liệu. Tuy vậy, đôi khi quá trình nén cũng làm giảm băng truyền
tín hiệu số hoá thấp hơn so với truyền tín hiệu tương tự.
8.1.2 Các loại dư thừa dữ liệu
Như trên đã nói, nén nhằm mục đích giảm kích thước dữ liệu
bằng cách loại bỏ dư thừa dữ liệu. Việc xác định bản chất các kiểu dư
thừa dữ liệu rất có ích cho việc xây dựng các phương pháp nén dữ liệu
khác nhau. Nói một cách khác, các phương pháp nén dữ liệu khác nhau là
do sử dụng các kiểu dư thừa dữ liệu khác nhau. Người ta coi có 4 kiểu
dư thừa chính:
ừ Sự phân bố ký tự
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 một số dãy khác. Do vậy, ta có thể mã hoá dữ liệu một cách cô đọng
hơn. Các dãy ký tự có tần xuất cao được thay bởi một từ mã nhị phân với
số bít nhỏ; ngược lại các dãy có tần xuất thấp sẽ được mã hoá bởi từ mã
có nhiều bít hơn. Đây chính là bản chất của phương pháp mã hoá
Huffman (xem mục 8.2.2).
ụ Sự lặp lại của các ký tự
Trong một số tình huống như trong ảnh, 1 ký hiệu (bít "0" hay bít
"1") được lặp đi lặp lại một số lần. Kỹ thuật nén dùng trong trường hợp
này là thay dãy lặp đó bởi dãy mới gồm 2 thành phần: số lần lặp và kí
Nhập môn xử lý ảnh số - ĐHBK Hà nội 229
Chương Tám: NÉN DỮ LIỆU ẢNH
hiệu dùng để mã. Phương pháp mã hoá kiểu này có tên là mã hoá loạt dài
RLC (Run Length Coding). Phương pháp mã hoá RLC sẽ được trình bày
trong mục 8.2.1.
ụ Những mẫu sử dụng tần suất
Có thể có dãy ký hiệu nào đó xuất hiện với tần suất tương đối
cao. Do vậy, có thể mã hoá bởi ít bít hơn. Đây là cơ sở của phương pháp
mã hoá kiểu từ điển do Lempel-Ziv đưa ra và có cải tiến vào năm 1977,
1978 và do đó có tên gọi là phương pháp nén LZ77, LZ78. Năm 1984,
Terry Welch đã cải tiến hiệu quả hơn và đặt tên là LZW (Lempel-Ziv-
Welch). Phương pháp nén này sẽ được trình bày trong 8.2.3.
ợ Độ dư thừa vị trí
Do sự phụ thuộc lẫn nhau của dữ liệu, đôi khi biết được ký hiệu
(giá trị) xuất hiện tại một vị trí, đồng thời có thể đoán trước sự xuất
hiện của các giá trị ở các vị trí khác nhau một cách phù hợp. Chẳng hạn,
ảnh biểu diễn trong một lưới hai chiều, một số điểm ở hàng dọc trong
một khối dữ lệu lại xuất hiện trong cùng vị trí ở các hàng khác nhau. Do
vậy, thay vì lưu trữ dữ liệu, ta chỉ cần lưu trữ vị trí hàng và cột. Phương
pháp nén dựa trên sự dư thừa này gọi là phương pháp mã hoá dự đoán.
Cách đánh giá độ dư thừa như trên hoàn toàn mang tính trực quan
nhằm biểu thị một cái gì đó xuất hiện nhiều lần. Đối với dữ liệu ảnh,
ngoài đặc thù chung đó, nó còn có những đặc thù riêng. Thí dụ như có ứng
dụng không cần toàn bộ dữ liệu thô của ảnh mà chỉ cần các thông tin đặc
trưng biểu diễn ảnh như biên ảnh hay vùng đồng nhất. Do vậy, có những
phương pháp nén riêng cho ảnh dựa vào biến đổi ảnh hay dựa vào biểu
Nhập môn xử lý ảnh số - ĐHBK Hà nội 230
Chương Tám: NÉN DỮ LIỆU ẢNH
diễn ảnh. Các phương pháp này sẽ lần lượt trình bày trong mục 8.3 và
8.4.
8.1.3 Phân loại các phương pháp nén
Có nhiều cách phân loại các phương pháp nén khác nhau. Cách thứ
nhất dựa vào nguyên lý nén. Cách này phân các phương pháp nén thành 2
họ lớn:
ớ Nén chính xác hay nén không mất thông tin: họ này bao
gồm các phương pháp nén mà sau khi giải nén ta thu được chính xác
dữ liệu gốc.
ố Nén có mất mát thông tin: họ này bao gồm các phương
pháp mà sau khi giải nén ta không thu được dữ liệu như bản gốc.
Trong nén ảnh, người ta gọi là các phương pháp "tâm lý thị giác". Các
phương pháp này lợi dụng tính chất của mắt người, chấp nhận một
số vặn xoắn trong ảnh khi khôi phục lại. Tất nhiên, các phương
pháp này chỉ có hiệu quả khi mà độ vặn xoắn là chấp nhận được
bằng mắt thường hay với dung sai nào đó.
Cách phân loại thứ hai dựa vào cách thức thực hiện nén. Theo cách này,
người ta cũng phân thành hai họ:
ọ Phương pháp không gian (Spatial Data Compression): các
phương pháp thuộc họ này thực hiện nén bằng cách tác động trực tiếp
lên việc lấy mẫu của ảnh trong miền không gian.
ề Phương pháp sử dụng biến đổi (Transform Coding):
Gồm các phương pháp tác động lên sự biến đổi của ảnh gốc mà
không tác động trực tiếp như họ trên [6].
Nhập môn xử lý ảnh số - ĐHBK Hà nội 231
Chương Tám: NÉN DỮ LIỆU ẢNH
Có một cách phân loại khác nữa, cách phân loại thứ ba, dựa vào triết lý
của sự mã hoá. Cách này cũng phân các phương pháp nén thành 2 họ:
ọ Các phương pháp nén thế hệ thứ nhất: Gồm các
phương pháp mà mức độ tính toán là đơn giản, thí dụ như việc lấy mẫu,
gán từ mã, v,..., v.
ừ Các phương pháp nén thế hệ thứ hai: Dựa vào mức độ
bão hoà của tỷ lệ nén.
Trong các phần trình bày dưới đây, ta sẽ theo cách phân loại này.
Cũng còn phải kể thêm một cách phân loại thứ tự do Anil.K.Jain nêu ra.
Theo cách của Jain, các phương pháp nén gồm 4 họ chính:
ọ Phương pháp điểm.
ể Phương pháp dự đoán.
ự Phương pháp dựa vào biến đổi.
ổ Các phương pháp tổ hợp (Hybrid).
Thực ra cách phân loại này là chia nhỏ của cách phân loại thứ ba và dựa
vào cơ chế thực hiện nén. Xét một cách kỹ lưỡng nó cũng tương đương
cách phân loại thứ ba.
Nhìn chung, quá trình nén và giải nén dữ liệu có thể mô tả một
cách tóm tắt theo sơ đồ hình 8.1 dưới đây.
Quá trình nén
Dữ liệu gốc Dữ liệu
nén
Nhập môn xử lý ảnh số - ĐHBK Hà nội 232
Chương Tám: NÉN DỮ LIỆU ẢNH
Quá trình giải nén
Hình 8.1 Sơ đồ chức năng quá trình nén dữ
liệu
8.2 CÁC PHƯƠNG PHÁP NÉN THẾ HỆ THỨ NHẤT
Trong lớp các phương pháp này, ta lần lượt xem xét các phương pháp:
- Mã hoá loạt dài RLC (Run Length Coding)
- Mã hoá Huffman
- Mã hoá LZW(Lempel Ziv-Wench)
- Mã hoá khối (Block Coding).
8.2.1 Phương pháp mã hoá loạt dài
Phương pháp mã hoá loạt dài lúc đầu được phát triển dành cho
ảnh số 2 mức: mức đen (1) và mức trắng (0) như các văn bản trên nền
trắng, trang in, các bức vẽ kỹ thuật.
Nguyên tắc của phương pháp là phát hiện một loạt các bít lặp lại,
thí dụ như một loạt các bit 0 nằm giữa hai bit 1, hay ngược lại, một loạt
bit 1 nằm giữa hai bit 0. Phương pháp này chỉ có hiệu quả khi chiều dài
dãy lặp lớn hơn một ngưỡng nào đó. Dãy các bit lặp gọi là loạt hay mạch
(run). Tiếp theo, thay thế chuỗi đó bởi một chuỗi mới gồm 2 thông tin:
chiều dài chuỗi và bit lặp (ký tự lặp). Như vậy, chuỗi thay thế sẽ có
chiều dài ngắn hơn chuỗi cần thay.
Nhập môn xử lý ảnh số - ĐHBK Hà nội 233
Chương Tám: NÉN DỮ LIỆU ẢNH
Cần lưu ý rằng, đối với ảnh, chiều dài của chuỗi lặp có thể lớn
hơn 255. Nếu ta dùng 1 byte để mã hoá thì sẽ không đủ. Giải pháp được
dùng là tách chuỗi đó thành 2 chuỗi: một chuỗi có chiều dài 255, chuỗi kia
là số bit còn lại.
Phương pháp RLC được sử dụng trong việc mã hoá lưu trữ các
ảnh Bitmap theo dạng PCX, BMP (đã nêu trong chương 2).
Phương pháp RLC có thể chia thành 2 phương pháp nhỏ: phương
pháp dùng chiều dài từ mã cố định và phương pháp thích nghi như kiểu
mã Huffman. Giả sử các mạch gồm M bits. Để tiện trình bày, đặt M =2m-
1. Như vậy mạch cũ được thay bỏi mạch mới gồm m bits. Với cách thức
này, mọi mạch đều được mã hoá bởi từ mã có cùng độ dài. Người ta cũng
tính được, với M=15, p=0.9, ta sẽ có m=4 và tỷ số nén là 1,95.
Với chiều dài cố định, việc cài đặt thuật toán là đơn giản. Tuy
nhiên, tỷ lệ nén sẽ không tốt bằng dùng chiều dài biến đổi hay gọi là mã
RLC thích nghi.
8.2.2 Phương pháp mã hoá Huffman
Nguyên tắc
Phương pháp mã hoá Huffman là phương pháp dựa vào 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ủa các
ký tự. Việc tính tần xuất được thực hiện bằng cách duyệt tuần tự tệp
gốc từ đầu đến cuối. Việc xử lý ở đây tính theo bit. Trong phương pháp
này, ngưới ta gán cho các ký tự có tần suất cao một từ mã ngắn, các ký tự
có tần xuất thấp từ mã dài. Nói một cách khác, các ký tự có tần xuất càng
cao được gán mã càng ngắn và ngược lại. Rõ ràng với cách thức này, ta đã
Nhập môn xử lý ảnh số - ĐHBK Hà nội 234
Chương Tám: NÉN DỮ LIỆU ẢNH
làm giảm chiều dài trung bình của từ mã hoá bằng cách dùng chiều dài
biến đổi. Tuy nhiên, trong một số tình huống khi tần suất là rất thấp, ta
có thể không được lợi một chút nào, thậm chí còn bị thiệt một ít bit.
Thuật toán
Thuật toán bao gồm 2 bước chính:
ớ Giai đoạn tính tần suất của các ký tự trong dữ liệu gốc: Duyệt tệp
gốc một cách tuần tự từ đầu đến cuối để xây dựng bảng mã. Tiếp
sau đó là sắp xếp lại bảng mã theo thứ tự tần suất giảm dần.
ầ Giai đoạn thứ hai: mã hoá. Duyệt bảng tần suất từ cuối lên đầu
để thực hiện ghép 2 phần tử có tần suất thấp nhất thành một phần tử duy
nhất. Phần tử này có tần xuất bằng tổng 2 tần suất thành phần. Tiến
hành cập nhật lại bảng và đương nhiên loại bỏ 2 phần tử đã xét. Quá
trình được lặp lại cho đến khi bảng chỉ có một phần tử. Quá trình này gọi
là quá trình tạo cây mã Huffman vì việc tập hợp được tiến hành nhờ một
cây nhị phân với 2 nhánh. Phần tử có tần suất thấp ở bên phải, phần tử
kia ở bên trái. Với cách tạo cây này, tất cả các bit dữ liệu/ ký tự là nút lá;
các nút trong là các nút tổng hợp. Sau khi cây đã tạo xong, người ta tiến
hành gán mã cho các nút lá. Việc mã hoá rất đơn giản: mỗi lần xuống bên
phải ta thêm 1 bit "1" vào từ mã; mỗi lần xuống bên trái ta thêm 1 bit "0".
Tất nhiên có thể làm ngược lại, chỉ có giá trị mã thay đổi còn tổng chiều
dài là không đổi. Cũng chính do lý do này mà cây có tên gọi là cây mã
Huffman như trên đã gọi.
Quá trình giải nén tiến hành theo chiều ngược lại khá đơn giản.
Người ta cũng phải dựa vào bảng mã tạo ra trong giai đoạn nén (bảng này
Nhập môn xử lý ảnh số - ĐHBK Hà nội 235
Chương Tám: NÉN DỮ LIỆU ẢNH
được giữ lại trong cấu trúca đầu của tệp nén cùng với dữ liệu nén).
Thí dụ, với một tệp dữ liệu mà tần suất các ký tư cho bởi:
Ký tự Tần suất Ký tự tần suất xác suất
"1" 152 "0" 1532 0.2770
"2" 323 "6" 602 0.1088
"3" 412 "." 536 0.0969
"4" 226 "" 535 0.0967
"5" 385 "3" 112 0.0746
"6" 602 "5 " 385 0.0696
"7" 92 "2" 323 0.0585
"8" 112 "_" 315 0.0569
"9" 87 "4" 226 0.0409
"0" 1532 "+" 220 0.0396
"." 536 "1" 152 0.0275
"+" 220 "8" 112 0.0203
"_" 315 "7" 92 0.0167
"" 535 "9" 87 0.0158
Bảng tần xuất Bảng tần suất sắp theo thứ
tự giảm dần
Lưu ý rằng, trong phương pháp Huffman, mã của ký tự là duy nhất và
không mã nào là phần bắt đầu của mã khác. Vì vậy, khi đọc tệp nén từng
bit từ đầu đến cuối ta có thể duyệt cây mã cho cho đến một lá, tức là ký
tự đã được giải nén.
Nhập môn xử lý ảnh số - ĐHBK Hà nội 236
Chương Tám: NÉN DỮ LIỆU ẢNH
Cây mã Hufman tương ứng
Gốc
1 0
N12 N11
1 0 1 0
N10 "0" N9 N8
1 0 1 0 1 0
N7 N6 N5 "6" "." ""
1 0 1 0 1 0
N4 "3" N3 "5" "2" "_"
1 0 1 0
N2 "4" "+" N1
1 0 1 0
"1" "8" "7" "9"
Hình 8.2. Cây mã Huffman .
Bảng từ mã gán cho các ký tự bởi mã hoá Huffman
"0" 10 "_" 0110
"6" 010 "4" 11110
"." 001 "+" 11011
"" 000 "1" 111111
Nhập môn xử lý ảnh số - ĐHBK Hà nội 237
Chương Tám: NÉN DỮ LIỆU ẢNH
"3" 1110 "8" 111110
"5" 1100 "7" 110101
"2" 0111 "9" 110100
8.2.3 Phương pháp LZW
Mở đầu
Khái niệm nén từ điển được Jacob Lempel và Abraham Ziv đưa ra lần
đầu tiên vào năm 1977, sau đó phát triển thành một họ giải thuật nén từ
điển LZ. Năm 1984, Terry Welch đã cải tiến giải thuật LZ thành một giải
thuật mới hiệu quả hơn và đặt tên là LZW. Phương pháp nén từ điển dựa
trên việc xây dựng từ điển lưu các chuỗi kí tự có tần suất lặp lại cao và
thay thế bằng từ mã tương ứng mỗi khi gặp lại chúng. Giải thuật LZW
hay hơn các giải thuật trước nó ở kĩ thuật tổ chức từ điển cho phép nâng
cao tỉ lệ nén.
Giải thuật nén LZW được sử dụng cho tất cả các loại file nhị phân.
Nó thường được dùng để nén các loại văn bản, ảnh đen trắng, ảnh màu,
ảnh đa mức xám... và là chuẩn nén cho các dạng ảnh GIF và TIFF. Mức
độ hiệu quả của LZW không phụ thuộc vào số bit màu của ảnh.
Phương pháp
Giải thuật nén LZW xây dựng một từ điển lưu các mẫu có tần
suất xuất hiện cao trong ảnh. Từ điển là tập hợp những cặp từ vựng và
nghĩa của nó. Trong đó, từ vựng sẽ là các từ mã được sắp xếp theo thứ tự
nhất định. Nghĩa là một chuỗi con trong dữ liệu ảnh. Từ điển được xây
dựng đồng thời với quá trình đọc dữ liệu. Sự có mặt của một chuỗi con
trong từ điển khẳng định rằng chuỗi đó đã từng xuất hiện trong phần dữ
Nhập môn xử lý ảnh số - ĐHBK Hà nội 238
Chương Tám: NÉN DỮ LIỆU ẢNH
liệu đã đọc. Thuật toán liên tục "tra cứu" và cập nhật từ điển sau mỗi lần
đọc một kí tự ở dữ liệu đầu vào.
Do kích thước bộ nhớ không phải vô hạn và để đảm bảo tốc độ
tìm kiếm , từ điển chỉ giới hạn 4096 ở phần tử dùng để lưu lớn nhất là
4096 giá trị của các từ mã. Như vậy độ dài lớn nhất của từ mã là 12 bits
( 4096 = 212). Cấu trúc từ điển như sau:
0 0
1 1
... ...
... ...
255 255
256 256 (Clear Code)
257 257 (End Of
Information)
258 Chuỗi
259 Chuỗi
... ...
... ...
4095 Chuỗi
+ 256 từ mã đầu tiên theo thứ tự từ 0...255 chứa các số nguyên từ
0...255. Đây là mã của 256 kí tự cơ bản trong bảng mã ASCII.
+ Từ mã thứ 256 chứa một mã đặc biệt là "mã xoá" (CC - Clear
Code). Mục đích việc dùng mã xoá nhằm khắc phục tình trạng số mẫu
lặp trong ảnh lớn hơn 4096. Khi đó một ảnh được quan niệm là nhiều
mảnh ảnh, và từ điển là một bộ từ điển gồm nhiều từ điển con. Cứ hết
một mảnh ảnh người ta lại gửi một mã xoá để báo hiệu kết thúc mảnh
Nhập môn xử lý ảnh số - ĐHBK Hà nội 239
Chương Tám: NÉN DỮ LIỆU ẢNH
ảnh cũ, bắt đầu mảnh ảnh mới đồng thời khởi tạo lại từ điển cho mảnh
ảnh mới. Mã xoá có giá trị là 256.
+ Từ mã thứ 257 chứa mã kết thúc thông tin (EOI - End Of
Information). Mã này có giá trị là 257. Như chúng ta đã biết, một file ảnh
GIF có thể chứa nhiều ảnh. Mỗi một ảnh sẽ được mã hoá riêng. Chương
trình giải mã sẽ lặp đi lặp lại thao tác giải mã từng ảnh cho đến khi gặp
mã kết thúc thông tin thì dừng lại.
+ Các từ mã còn lại (từ 258 đến 4095) chứa các mẫu thường lặp
lại trong ảnh. 512 phần tử đầu tiên của từ điển biểu diễn bằng 9 bit. Các
từ mã từ 512 đến 1023 biểu diễn bởi 10 bit, từ 1024 đến 2047 biểu diễn
bởi 11 bit và từ 2048 đến 4095 biểu diễn bởi 12 bit.
Ví dụ minh hoạ cơ chế nén của LZW
Cho chuỗi đầu vào là "ABCBCABCABCD" (Mã ASCII của A là 65, B là
66, C là 67).
Từ điển ban đầu đã gồm 256 kí tự cơ bản.
Đầu Đ ầu Thực hiện
vào Ra
A (65) A đã có trong từ điển ⇒ Đọc tiếp
B (66) 65 Thêm vào từ điển mã 258 đại diện cho chuỗi
AB
C (67) 66 Thêm vào từ điển mã 259 đại diện cho chuỗi
BC
B 67 Thêm vào từ điển mã 260 đại diện cho chuỗi
CB
Nhập môn xử lý ảnh số - ĐHBK Hà nội 240
Chương Tám: NÉN DỮ LIỆU ẢNH
C BC đã có trong từ điển ⇒ Đọc tiếp
A 259 Thêm vào từ điển mã 261 đại diện cho chuỗi
BCA
B AB đã có trong từ điển ⇒ Đọc tiếp
C 258 Thêm vào từ điển mã 262 đại diện cho chuỗi
ABC
A 67 Thêm vào từ điển mã 263 đại diện cho chuỗi
CA
B AB đã có trong từ điển ⇒ Đọc tiếp
C ABC đã có trong từ điển ⇒ Đọc tiếp
D 262 Thêm vào từ điển mã 263 đại diện cho chuỗi
ABCD
Chuỗi đầu ra sẽ là:
65 - 66 - 67 - 259 - 258 - 67 - 262
Đầu vào có kích thước: 12 x 8 = 96 bits. Đầu ra có kích thước là: 4x8
+3x9 = 59 bits
Tỉ lệ nén là: 96:59 ≅ 1,63.
Thuật toán
- Giá trị cờ INPUT = TRUE khi vẫn còn dữ liệu đầu vào và ngược lại.
- Chức năng của các hàm:
• InitDictionary() : Hàm này có chức năng khởi tạo từ điển. Đặt giá trị cho
256 phần tử đầu tiên. Gán mã xoá (Clear Code) cho phần tử thứ 256 và
mã kết thúc thông tin (End Of Information) cho phần tử thứ 257. Xoá giá
trị tất cả các phần tử còn lại.
Nhập môn xử lý ảnh số - ĐHBK Hà nội 241
Chương Tám: NÉN DỮ LIỆU ẢNH
• Hàm Output() : gửi chuỗi bit ra file. Chuỗi bit này có độ dài là 9,10,11
hoặc 12 tuỳ thuộc vào vị trí trong từ điển của từ mã gửi ra.Các chuỗi bit
này được nối tiếp vào với nhau.
• Hàm GetNextChar(): Trả về một kí tự từ chuỗi kí tự đầu vào. Hàm này
cập nhật giá trị của cờ INPUT xác định xem còn dữ liệu đầu vào nữa hay
không.
• Hàm AddtoDictionary() sẽ được gọi khi có một mẫu mới xuất hiện.
Hàm này sẽ cập nhật mẫu này vào phần tử tiếp theo trong từ điển. Nếu
từ điển đã đầy nó sẽ gửi ra mã xoá(Clear Code) và gọi đến hàm
InitDictionary() để khởi tạo lại từ điển.
• Hàm Code(): Trả về từ mã ứng với một chuỗi.
Tư tưởng của đoạn mã trên có thể hiểu như sau: Nếu còn dữ liệu
đầu vào thì tiếp tục đọc. Một chuỗi mới sẽ được tạo ra từ chuỗi
cũ(chuỗi này ban đầu trBắt đầu ỗi này phải là chuỗi đã tồn tại trong từ
ống, chu
điển) và kí tự vừa đọc vào. Sau đó kiểm tra xem chuỗi mới đã có trong từ
điển hay chưa. Mục đích của công việc này là hi vọng tìm được chuỗi có
InitDictionary()
số kí tự lớn Output(Clear_Code)
nhất đã tồn tại trong từ điển. Nếu tồn tại ta lại tiếp tục đọc
OldStr = NULL
một kí tự tiếp theo và lặp lại công việc. Nếu chưa có trong từ điển, thì
gửi chuỗi cũ ra ngoài và thêm chuỗi mới vào từ điển. Có thể xem lại phần
- Ouput(Code(OldSt
ví dụ để hiểu rõ hơn.
INPUT r))
OutPut(EOI)
+
NewChar = GetNextChar()
NewStr = OldStr + NewChar KẾT THÚC
Nhập môn xử lý ảnh số - ĐHBK Hà nội
InDictionary(New - 242
Str)
+
Ouput(Code(OldStr))
AddtoDictionary(NewStr)
OldStr = NewChar
OldStr = NewStr
Chương Tám: NÉN DỮ LIỆU ẢNH
Hình 8.3. Sơ đồ thuật toán nén LZW
Nhập môn xử lý ảnh số - ĐHBK Hà nội 243
Chương Tám: NÉN DỮ LIỆU ẢNH
Giải nén dữ liệu nén bằng LZW
Giải thuật giải nén gần như ngược với giải thuật nén . Với giải
thuật nén, một từ mã ứng với một chuỗi sẽ được ghi ra tệp khi chuỗi
ghép bởi chuỗi trên với kí tự vừa đọc chưa có mặt trong từ điển. Người ta
cũng cập nhật ngay vào từ điển từ mã ứng với chuỗi tạo bởi chuỗi cũ với
kí tự vừa đọc. Kí tự này đồng thời là kí tự đầu tiên trong chuỗi ứng với từ
mã sẽ
được ghi ra tiếp theo. Đây là điểm mấu chốt cho phép xây dựng thuật
toán giải nén.
Thuật toán được mô tả như sau:
while(GetNextCode() != EOI) do
Begin
if FIRST_CODE /* Mã đầu tiên của mỗi mảnh ảnh*/
Then Begin
OutBuff(code);
OldStr := code;
End;
If code = CC /* Mã xoá*/
Then Begin
InitDictionary();
FIRST_CODE = TRUE;
End;
NewStr := DeCode(code);
OutBuff(NewStr);
Nhập môn xử lý ảnh số - ĐHBK Hà nội 244
Chương Tám: NÉN DỮ LIỆU ẢNH
OldString = OldStr + FirstChar(NewStr);
AddtoDictionary(OldStr);
OldString := NewStr;
End;
+ Giá trị cờ FIRST_CODE = TRUE chỉ mã vừa đọc là mã đầu tiên
của mỗi mảnh ảnh. Mã đầu tiên có cách xử lí hơi khác so với các mã tiếp
theo.
+ Mã CC báo hiệu hết một mảnh ảnh. Mã EOI báo hiệu hết toàn
bộ thông tin ảnh.
+Chức năng của các hàm:
• GetNextCode() : Hàm này đọc thông tin đầu vào(dữ liệu nén) trả về mã
tương ứng. Chúng ta nhớ lại rằng, dữ liệu nén gồm chuỗi các từ mã nối
tiếp nhau. Ban đầu là 9 bit, sau đó tăng lên 10 bit rồi 11, 12 bit. Nhiệm vụ
của hàm này không phải đơn giản. Để biết được tại thời điểm hiện thời,
từ mã dài bao nhiêu bit ta phải luôn theo dõi từ điển và cập nhật độ dài từ
mã tại các phần tử thứ 512, 1024, 2048.
• OutBuff() Hàm này gửi chuỗi giá trị đã giải mã ra vùng nhớ đệm.
• DeCode() Hàm này tra cứu từ điển và trả về chuỗi kí tự tương ứng với
từ mã.
• FirstChar() Lấy kí tự đầu tiên của một chuỗi. Kí tự vừa xác định nối
tiếp vào chuỗi kí tự cũ (đã giải mã ở bước trước) ta được chuỗi kí tự có
mặt trong từ điển khi nén. Chuỗi này sẽ được thêm vào từ điển giải nén.
Nhập môn xử lý ảnh số - ĐHBK Hà nội 245
Chương Tám: NÉN DỮ LIỆU ẢNH
• Hàm Output() : gửi chuỗi bit ra file. Chuỗi bit này có độ dài là 9,10,11
hoặc 12 tuỳ thuộc vào vị trí trong từ điển của từ mã gửi ra.Các chuỗi bit
này được nối tiếp vào với nhau.
Trường hợp ngoại lệ và cách xử lý
Đối với giải thuật LZW tồn tại một trường hợp được sinh ra
nhưng chương trình giải nén có thể không giải mã được. Giả sử c là một
kí tự, S là một chuỗi có đọ dài lớn hơn 0. Nếu mã k của từ điển chứa giá
trị là cS. Chuỗi đầu vào là cScS. Khi đọc đến cSc chương trình sẽ tạo mã
k' chứa cSc. Ngay sau đó k' được dùng thay thế cho cSc. Trong chương
trình giải nén, k' sẽ xuất hiện trước khi nó được định nghĩa. Rất may là từ
mã vừa đọc trong trường hợp này bao giờ cũng có nội dung trùng với tổ
hợp của từ mã cũ với kí tự đầu tiên của nó. Điều này giúp cho quá trình
cài đặt chương trình khắc phục được trường hợp ngoại lệ một cách dễ
dàng.
8.2.4 Phương pháp mã hoá khối (Block Coding)
Nguyên tắc
Phương pháp này lúc đầu được phát triển cho ảnh số 2 mức xám,
sau đó hoàn thiện thêm bởi các phương pháp thích nghi và mở rộng cho
ảnh số đa cấp xám.
Cho một ảnh số I(x,y) kích thước M x N. Người ta chia nhỏ ảnh
số thành các khối hình chữ nhật kích thước k x l, (k,l) là rất nhỏ so với M,
N. Như vậy ảnh gốc coi như gồm các khối con xếp cạnh nhau và có N x
M / (k x l) khối con.
Nhập môn xử lý ảnh số - ĐHBK Hà nội 246