fallinlove_bmt2007
New Member
Download miễn phí Bài giảng Nén dữ liệu ảnh
Thuật ngữ "thích nghi" thường dùng để chỉ sự thích hợp của các từ mã theo một nghĩa nào đấy. Như trong phương pháp RLC ở trên, thay vì dùng chiều dài từ mã cố định m bits, người ta dùng chiều dài biến đổi và trên cơ sở đó có phương pháp RLC thích nghi.
Trong phương pháp mã hoá khối, người ta dùng chiều dài khối cố định gồm k x l điểm ảnh. Tuy nhiên, với ảnh không thuần nhất, phương pháp mã hoá này bộc lộ nhiều nhược điểm. Vì rằng, với ảnh không thuần nhất, chính sự không thuần nhất của ảnh quyết định sự thích nghi với điều kiện cục bộ.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
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 đầ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 thay mặt cho chuỗi AB
C (67)
66
Thêm vào từ điển mã 259 thay mặt cho chuỗi BC
B
67
Thêm vào từ điển mã 260 thay mặt 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 thay mặt 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 thay mặt cho chuỗi ABC
A
67
Thêm vào từ điển mã 263 thay mặt 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 thay mặt 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.
ã Hàm Output() : gửi chuỗi bit ra file. Chuỗi bit này có độ dài là 9,10,11 hay 12 tuỳ từng trường hợp 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 chưa. 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 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 ví dụ để hiểu rõ hơn.
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)
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 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);
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 hay 12 tuỳ từng trường hợp 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 ...