Chơng Tám: nén dữ liệu ảnh
Quá trình nén
Dữ liệu gốc Dữ liệu nén
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.
Cần lu ý 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á lu 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.
Nhập môn xử lý ảnh số - ĐHBK Hà nội 231
Chơng Tám: nén dữ liệu ảnh
Để tiện trình bày, đặt M =2
m
-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 đã 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
Nhập môn xử lý ảnh số - ĐHBK Hà nội 232
Chơng Tám: nén dữ liệu ảnh
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 đợ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
Lu ý 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.
Cây mã Hufman tơng ứng
Gốc
1 0
N12 N11
Nhập môn xử lý ảnh số - ĐHBK Hà nội 233
Chơng Tám: nén dữ liệu ảnh
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
"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 lu 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.
Nhập môn xử lý ảnh số - ĐHBK Hà nội 234
Chơng Tám: nén dữ liệu ảnh
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 lu 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ữ 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 để lu 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 = 2
12
). 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 cũ, bắt
Nhập môn xử lý ảnh số - ĐHBK Hà nội 235
Chơng Tám: nén dữ liệu ảnh
đầ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 vào Đầu Ra Thực hiện
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
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.
Nhập môn xử lý ảnh số - ĐHBK Hà nội 236
Chơng Tám: nén dữ liệu ảnh
- 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.
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 trống, chuỗi này phải là
chuỗi đã tồn tại trong từ đ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 cha. Mục đích của công việc này là hi vọng tìm đợc chuỗi có số kí tự lớn
nhất đã tồn tại trong từ điển. Nếu tồn tại ta lại tiếp tục đọc một kí tự tiếp theo và lặp lại công
việc. Nếu cha 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 ví dụ để hiểu rõ hơn.
Nhập môn xử lý ảnh số - ĐHBK Hà nội 237
Bắt đầu
InitDictionary()
Output(Clear_Code)
OldStr = NULL
NewChar = GetNextChar()
NewStr = OldStr + NewChar
InDictionary(NewStr)
INPUT
Ouput(Code(OldStr))
AddtoDictionary(NewStr)
OldStr = NewChar
OldStr = NewStr
Kết thúc
+
-
-
+
Ouput(Code(OldStr))
OutPut(EOI)
Chơng Tám: nén dữ liệu ảnh
Hình 8.3. Sơ đồ thuật toán nén LZW
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 cha 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á*/
Nhập môn xử lý ảnh số - ĐHBK Hà nội 238
Chơng Tám: nén dữ liệu ảnh
Then Begin
InitDictionary();
FIRST_CODE = TRUE;
End;
NewStr := DeCode(code);
OutBuff(NewStr);
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.
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 nhng 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
Nhập môn xử lý ảnh số - ĐHBK Hà nội 239
Chơng Tám: nén dữ liệu ảnh
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.
Ta có thể dùng phơng pháp mã hoá Huffman cho từng khối của ảnh gốc, nghĩa là
gán cho mỗi từ khối một từ mã nhị phân nh ở phần trên. Một khó khăn gặp phải khi dùng
mã hoá tối u Huffman đó là số lợng khối quá lớn. Giải pháp ở đây là dùng mã hoá gần tối u,
đơn giản hơn để thực hiện mã hoá.
Ta giả thiết các khối là độc lập với nhau và số cấu hình là 2
kl
. Gọi p(i,k,l) là sác
xuất xuất hiện cấu hình i, entropy tơng ứng là:
H(k,l) = -
i
kl
=
1
2
p(i,k,l)log
2
P(i,k,l)
Giá trị H(k,l) có thể diễn giải là số bit/ khối.
Các từ mã gán cho các khối k x l đợc tạo bởi các điểm trắng (cấu hình trội) là "0".
Các từ mã gán cho các khối k x l khác gồm kxl bit màu ("1" cho đen, "0" cho trắng) đi tiếp
sau 1 bit tiền tố "1".
Việc mã hoá theo khối cũng đợc sử dụng nhiều trong các phơng pháp khác nh ph-
ơng pháp dùng biến đổi sẽ trình bày trong phần 8.3 để giảm bớt không gian lu trữ.
Thuật toán
Giả sử p(0,k,l) xác suất của khối chỉ tạo bởi các điểm trắng là đã biết, t ỷ số nén
có thể tính đợc dễ dàng. Xác suất này có thể đợc thiết lập bởi mô hình lý thuyết cho một
kiểu khối đặc biệt. Do vậy, ta chia khối
Nhập môn xử lý ảnh số - ĐHBK Hà nội 240
Không có nhận xét nào:
Đăng nhận xét