Luận văn Tìm hiểu một số phương pháp nén ảnh

tìm kiếm nhanh, từ điển chỉ giới hạn 4096 phần tử dùng để lưu trữ giá trị của các từ mã. Như vậy độ dài lớn nhất của từ mã là 12 bit (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). Khi số mẫu lặp lớn hơn 4096 thì người ta sẽ coi ảnh gồm nhiều mảnh ảnh và từ điển sẽ gồm nhiều từ điển con. Khi hết một mảnh ảnh sẽ gửi 1 mã xoá ( CC ) để báo hiệu kết thúc mảnh ảnh cũ và bắt đầu mảnh ảnh mới đồng thời sẽ khởi tạo lại từ điển. Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 28 • Từ mã thứ 257 chứa mã kết thúc thông tin (EOI - End Of Information). Thông thường một file ảnh GIF có thể chứa nhiều mảnh ảnh, mỗi mảnh ảnh này 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ụ : Cho chuỗi đầu vào “HELLOHELLOHELL” Từ điền ban đầu đã gồm 256 kí tự cơ bản. Kích thước đầu vào : 14 x 8 = 112 bit Đầu vào Đầu ra Thực hiện H(72) H đã có trong từ điển Æ đọc tiếp E(69) 72 Thêm vào từ điển mã 258 đại diện cho chuỗi HE L(76) 69 Thêm vào từ điển mã 259 đại diện cho chuỗi EL L 76 Thêm vào từ điển mã 260 đại diện cho chuỗi LL O(79) 76 Thêm vào từ điển mã 261 đại diện cho chuỗi LO H 79 Thêm vào từ điển mã 262 đại diện cho chuỗi OH E HE đã có trong từ điển Æ đọc tiếp L 258 Thêm vào từ điển mã 263 đại diện cho chuỗi HEL L LL đã có trong từ điển Æ đọc tiếp O 260 Thêm vào từ điển mã 264 đại diện cho chuỗi LLO H OH đã có trong từ điển Æ đọc tiếp E 262 Thêm vào từ điển mã 265 đại diện cho chuỗi OHE Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 29 L EL đã có trong từ điển Æ đọc tiếp L 259 Thêm vào từ điển mã 266 đại diện cho chuỗi ELL 76 Input = FALSE EOI Chuỗi đầu ra là : 72 69 76 76 79 258 260 262 259 76 Kích thước đầu ra : 6 x 8 + 4 x 9 = 84 bit Tỷ số nén : 112 / 84 = 1.3 Quá trình giải nén thực hiện như sau: Code OutBuff() AddToDictionary() CodeWord String 72 H 69 E 258 HE 76 L 259 EL 76 L 260 LL 79 O 261 LO 258 HE 262 OHE 260 LL 263 HEL 262 OH 264 LLO 259 EL 265 OHE 76 L 266 ELL EOI Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 30 Chuỗi thu được sau giải nén :”HELLOHELLOHELL” II.4.2. Thuật toán: • Thuật toán nén bằng LZW: InitDictionary() Output(Clear_Code) OldStr = NULL WHILE ( Input ) { NewChar = GetNextChar() NewStr = OldStr + NewChar IF ( InDictionary(NewStr) ) OldsSr = NewStr ELSE { Output(Code(OldStr)) AddToDictionary(NewStr) OldStr = NewChar } } Output(Code(OldStr)) Output(EOI) Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 31 • 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: • Hàm InitDictionary() : Khởi tạo từ điển. Đặt giá trị cho 256 phần tử đầu tiên. Gán mã xoá CC cho phần tử thứ 256 và mã kết thúc thông tin EOI cho phần tử thứ 257. Xoá giá trị tất cả các phần tử còn lại. • Hàm InDictionary (NewStr) : Kiểm tra chuỗi NewStr đã có trong từ điển chưa . • Hàm OutPut() : Gửi chuỗi bit ra file.Tuỳ thuộc vào vị trí của từ mã trong từ điển mà chuỗi bit có độ dài là 9,10,11 hoặc 12. • 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ờ Input xác định xem còn dữ liệu đầu vào nữa hay không. • Hàm AddToDictionary() : Hàm làm chức năng cập nhật mẫu mới 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á CC 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 1 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 rỗ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 trong từ điển. Nếu tồn tại thì 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. Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 32 • Giải nén dữ liệu 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. Thuật toán được mô tả như sau: WHILE (GetNextCode() != EOI) { IF (First_Code) /*Mã đầu tiên của mỗi mảnh ảnh*/ { OutBuff(DeCode(code)) OldStr = DeCode(code) } ELSE { IF (code == CC) /*Mã xoá*/ { InitDictionary() First_Code = TRUE } NewStr = DeCode(code) OutBuff(NewStr) OldStr = OldStr + FirstChar(NewStr) Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 33 AddToDictionary(OldStr) OldStr = NewStr } } • Giá trị cờ First_Code = TRUE chỉ mã vừa đọc là mã đầu tiên của mỗi mảnh ảnh. Chức năng của các hàm: • 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. • 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. • Hàm OutBuff() : Hàm này gửi chuỗi đã giải mã ra vùng nhớ đệm. • Hàm InitDictionary(): Khởi tạo từ điển. Đặt giá trị cho 256 phần tử đầu tiên. Gán mã xoá CC cho phần tử thứ 256 và mã kết thúc thông tin EOI cho phần tử thứ 257. Xoá giá trị tất cả các phần tử còn lại. • Hàm DeCode() : Hàm này tra cứu từ điển và trả về chuỗi ký tự tương ứng với mã. • Hà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 AddToDictionary() : Hàm làm chức năng cập nhật mẫu mới 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á CC và gọi đến hàm InitDictionary() để khởi tạo lại từ điển.. II.4.3.Một số thủ tục chương trình : Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 34 • Chương trình nén phương pháp LZW : BOOL CLZW::Compress(CFile &source, CFile &destination) { long prefix = 0; long result = 0; BYTE readByte = 0; unsigned long filetotal = 0; CString logString; DWORD resAdd = 256; Init(); filetotal = source.GetLength(); if (m_tudien == NULL) { CreateDictionary(); } source.Read(&prefix, 1); while (source.GetPosition() < filetotal) { source.Read(&readByte, 1); result = m_tudien->GetEntry(prefix, readByte); if (result == -1) { resAdd = m_tudien->AddEntry(prefix, readByte); CalculateBitSize(resAdd); logString.Format("Adding combination of %d and %d to dictionary to entry %d.",prefix, readByte, resAdd); Log(logString); CompressData(destination, prefix); prefix = readByte; result = -1; Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 35 } else { prefix = result; readByte = 0; } } CompressData(destination, prefix); CloseCompressedFile(destination); ClearDictionary(); return TRUE; } • Chương trình giải nén phương pháp LZW : BOOL CLZW::Decompress(CFile &source, CFile &destination) { DWORD prefix = 0, data = 0; CString logString; CByteArray decodeString; BYTE writeData = 0, character = 0; int counter = 0; Init(); if (m_tudien == NULL) { CreateDictionary(); } prefix = DecompressData(source); character = (BYTE)prefix; destination.Write(&prefix, 1); Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 36 while ((data = DecompressData(source)) != m_MaxCode[m_MaxBits]) { if (!m_tudien->IsCodeExist(data)) { decodeString.Add((BYTE)character); m_tudien->GetBytesFromCode(&decodeString, prefix); } else { m_tudien->GetBytesFromCode(&decodeString, data); character = decodeString.GetAt(decodeString.GetSize() - 1); } counter = decodeString.GetSize(); while (counter > 0) { writeData = (BYTE)decodeString.GetAt(--counter); destination.Write(&writeData, 1); logString.Format("Adding character code %d with know visualisation of: %s", writeData, convertASCIIToText(writeData)); Log(logString); } decodeString.RemoveAll(); m_tudien->AddEntry(prefix, (BYTE)character); CalculateBitSize(m_tudien->GetMaxCode()+1); prefix = data; Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 37 } return TRUE; } II.5.Phương pháp mã hoá JPEG: II.5.1.Nguyên tắc: JPEG là viết tắt của Joint Photographic Expert Group ( nhóm các chuyên gia đồ hoạ phát triển chuẩn này ). Chuẩn này được phát triển từ giữa thập niên 80 bởi sự hợp tác của tổ chức ISO và ITU và đến 1992 được công nhận là chuẩn ảnh quốc tế ,phục vụ các ứng dụng về ảnh cho các lĩnh vực như mạng, y học, khoa học kỹ thuật, ảnh nghệ thuật … Chuẩn JPEG được sử dụng để mã hoá ảnh đa mức xám, ảnh màu. JPEG không cho kết quả ổn định lắm với ảnh đen trắng, nó cung cấp cả 2 chế độ nén : nén mất mát thông tin và nén không tổn thất. Do độ phức tạp và hiệu suất nén của JPEG không mất mát thông tin mà nó không được sử dụng phổ biến .Dưới đây chỉ trình bày chi tiết về một trong các dạng nén Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 38 P h â n k h ố i ảnh gốc 8x8 8x8 8x8 DCT Lượng tử hoá Mã hoá ảnh nén Bảng lượng tử Bảng mã Khối 8x88 x 8 ảnh nén ảnh giải nén Tương tự hoá Giải mã DCT ngược Bảng lượng tử Bảng mã biến đổi chấp nhận mất mát thông tin dùng biến đổi Cosin tuần tự ( Sequential DTC- Based) của chuẩn JPEG. II.5.2.Thuật toán: Mã hoá JPEG bao gồm nhiều công đoạn, sơ đồ thuật toán nén và giải nén được mô tả như dưới đây Hình 2.5.1 : Quá trình nén ảnh theo chuẩn JPEG Quá trình giải nén sẽ được thực hiện ngược lại, người ta dựa vào các thông tin liên quan ghi trong phần Header của file nén để giải mã từng phần ảnh nén ứng với phương pháp nén. Kết quả thu được là hệ số đã lượng tử. Căn cứ vào bảng lượng tử sẽ khôi phục lại giá trị trước khi lượng tử hoá của các hệ số này. Cuối cùng là biến đổi Cosin ngược để thu lại được ảnh như ban đầu . Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 39 Hình 2.5.2 : Quá trình giải nén ảnh JPEG A. Chia ảnh thành khối Chuẩn nén JPEG phân ảnh ra các khối 8x8. Biến đổi nhanh Cosin 2 chiều cho các khối 8x8 sẽ đạt hiệu quả hơn, việc biến đổi Cosin cho các khối có cùng kích cỡ có thể giảm được một phần các tính toán chung như việc tính hệ số Cij . Khi n = 8 chúng ta chỉ cần tính hệ số Cij cho 3 tầng (8 = 23), số các hệ số là: 4 + 2 + 1 = 7 Nếu với một ảnh 512x512, phếp biến đổi nhanh Cosin một chiều theo hàng ngang hoặc hàng dọc ta phải cần qua 9 tầng (512 = 29). Số các hệ số Cij là: 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 +1 =509. Như vậy thời gian tính các hệ số Cij cho ảnh 512x512 lớn gấp 72 lần so với thời gian tính toán các hệ số này cho từng khối 8x8 , nếu kích thước ảnh lớn hơn thì chi phí thời gian sẽ còn tăng gấp nhiều lần đồng thời còn giúp việc tính toán trong khi biến đổi Cosin chính xác hơn. Ảnh sẽ chia làm B khối với: Các khối được xác định bởi bộ số (m,n) với m=[0..MB-1] và n=[0..NB- 1]. Trong đó : m : thứ tự của khối theo chiều rộng. n : thứ tự của khối theo chiều dài. BB NMl N k MB ×=⎟⎠ ⎞⎜⎝ ⎛×⎟⎠ ⎞⎜⎝ ⎛= '' Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 40 Phân khối thực chất là xác định tương quan giữa toạ độ riêng trong khối với tạo độ thực của điểm ảnh trong ảnh ban đầu. Nếu ảnh ban đầu ký hiệu Image[i,j] thì ma trận biểu diễn khối (m,n) là x[u,v] được tính: x[u,v] = Image[mk + u, nl + v] B. Biến đổi Đây là công đoạn quan trọng của các phương pháp nén sử dụng phép biến đổi, nhiệm vụ của công đoạn này là tập trung năng lượng vào một số ít các hệ số biến đổi. Công thức biến đổi cho mỗi khối là: Trong đó: Thuật toán biến đổi nhanh Cosin hai chiều cho mỗi khối sẽ bao gồm 16 phép biến đổi nhanh Cosin một chiều. Tiến hành biến đổi nhanh Cosin một chiều cho các dãy điểm ảnh trên 8 hàng. Tiếp đó tiến hành biến đổi nhanh Cosin một chiều trên 8 cột của ma trận vừa thu được sau 8 phép biến đổi trên.Kết quả sẽ là ma trận hệ số biến đổi của khối tương ứng. ( ) 16 )12( 16 )12(),( 4 , 22 7 01 7 02 11 21 21 21 Π+Π+= ∑∑ = = knCosknCosnnxkkX n n kk εε ⎪⎩ ⎪⎨ ⎧ = 0 2 1 1kε Khi k1 = 0 Khi (0<k1<8) ⎪⎩ ⎪⎨ ⎧ = 0 2 1 2kε Khi k2 = 0 Khi (0<k2<8) Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 41 Giải thuật biến đổi nhanh được mô tả như hình sau: Hình 2.5.3: Mô tả giải thuật biến đổi nhanh Trong sơ đồ giải nén ta phải dùng phép biến đổi Cosin ngược. Công thức biến đổi ngược cho khối 8x8: -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) X’(0) X’(1) X’(2) X’(3) X’(4) X’(5) X’(6) X’(7) Đ Ả O B Í T 0 2C C Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 42 Trong đó: Công thức tính x’(k1,n2) là phép biến đổi Cosin ngược rời rạc một chiều của X(k1,k2). Như vậy muốn khôi phục lại ảnh ban đầu từ hệ số biến đổi chúng ta sẽ biến đổi nhanh Cosin ngược rời rạc một chiều các hệ số theo hàng, sau đó đem biến đổi nhanh Cosin rời rạc một chiều theo cột các kết quả trung gian vừa tính được. Sơ đồ biến đổi Cosin ngược nhanh được biểu diễn như sau: ⎪⎩ ⎪⎨ ⎧ = 0 2 1 1kε Khi k1 = 0 Khi (0<k1<8) ⎪⎩ ⎪⎨ ⎧ = 0 2 1 2kε Khi k2 = 0 Khi (0<k2<8) ( ) 16 )12( 16 )12(),( 4 , 22 7 01 7 02 11 21 21 21 Π+Π+= ∑∑ = = knCosknCoskkXnnx k k εε Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 43 Hình 2.5.4 : Sơ đồ biến đổi Cosin ngược C. Lượng tử hoá Khối lượng tử hoá trong sơ đồ nén đóng vai trò quan trọng và quyết định tỷ lệ nén của chuẩn nén JPEG. Đầu vào của khối lượng tử hoá là các ma trận hệ số biến đổi Cosin của các khối điểm ảnh. Như ta đã biết ảnh được chia làm nhiều khối, ứng mỗi khối là các hệ số xác định. Trước khi thực hiện bước lượng tử hoá ta có thể loại bỏ vài hệ số. Ngoài hệ số (0,0) (được coi là thành phần DC) biểu diễn mức sáng trung bình của một khối ta có thể loại một số hệ số khác trong khối mang thông tin chi tiết về ảnh. Ta có thể bắt đầu loại bỏ từ hệ số có độ lệch chuẩn thấp nhất. Việc nên giữ lại bao nhiêu hệ số còn tuỳ thuộc vào việc ta muốn tỷ lệ nén cao hay thấp và những yêu cầu về chất lượng của ảnh nén . 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 -1 -1 -1 -1 -1 -1 -1 -1 0.5 -1 -1 -1 -1 X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) X’(0) X’(1) X’(2) X’(3) X’(4) X’(5) X’(6) X’(7) Đ Ả O B Í T 0.5 0.5 0.5 0 42 1 C 0 42 1 C 0 42 1 C 0 42 1 C 0 84 1 C 1 84 1 C 0 84 1 C 1 84 1 C 016 1 C 0 16 1 C 0 16 1 C 0 16 1 C Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 44 Để giảm số bộ lượng tử,người ta tìm cách quy các hệ số ở các khối về cùng một khoảng phân bố. Chuẩn nén JPEG chỉ sử dụng một bộ lượng tử hoá. Giả sử rằng các hệ số đều có hàm tính xác suất xuất hiện như nhau. Ta sẽ căn chỉnh lại hệ số yj bằng phép gán: Với: μj là trung bình cộng của hệ số thứ j σj là độ lệch cơ bản của hệ số thứ j Như vậy chúng ta sẽ đồng nhất được mức quyết định và mức tạo lại cho tất cả các hệ số. Do đó, các hệ số sẽ được biểu diễn bằng cùng một số lượng bit. Có nhiều cách tiếp cận để tính được các mức quyết và mức tạo lại. Lloyd – Max đưa ra giải thuật sau: Bước 1: Chọn giá trị khởi tạo: d0 = yL dn = yH r0 = d0 N là số mức lượng tử Bước 2: Cho i biến thiên từ 1 đến N-1 thực hiện các công việc sau: Tính ri-1 theo công thức: Tính ri theo công thức: j jj j y y σ μ−= ∫ ∫ − −=− i i i i d d d d i dyyp dyypy r 1 1 )( )(. 1 Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 45 ri = 2di – ri-1 Tính di theo công thức: Bước 3: Tính: Bước 4: Nếu rN-1 ≠ r’ điều chỉnh lại r0 và lặp lại từ bước 2 đến bước 4 Trong quá trình cài đặt thủ tục tạo ra bộ lượng tử hoá, Lloyd và Max đã có nhiều cải tiến để tính toán dễ dàng hơn. Sau đây là các bước mô tả toàn bộ công việc của khối lượng tử hoá tác động lên các hệ số biến đổi Cosin: Bước 1: Tính trung bình cộng μ và độ lệch cơ bản σ cho từng hệ số ở mỗi vị trí trong khối: Với : yj là hệ số thứ j, n là số khối Bước 2: Lựa chọn tỷ lệ hệ số giữ lại trong mỗi khối. 2 1−+= iii rrd ∫ ∫ − −=′ N N N N d d d d dyyp dyypy r 1 1 )( )(. n y j j ∑=μ )1( )( 22 − −= ∑∑ nn yyn jj jσ Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 46 Bước 3: Giữ lại các hệ số có độ lệch cơ bản lớn hơn. Bước 4: Lập ma trận khu vực T Tn = 1 nếu hệ số (i,j) được giữ lại Tn = 0 ngược lại Bước 5: Căn chỉnh lại giá trị của các hệ số xoay chiều được giữ lại ở các khối: Bước 6: Tính phân bố của các giá trị xoay chiều đã căn chỉnh. Bước 7: Tính độ lệch cơ bản σs của các phân bố vừa tính. Bước 8: Lượng tử hoá các hệ số xoay chiều bằng cách sử dụng bộ lượng tử Lloyd – Max sau khi đã điều chỉnh mức quyết định và mức tạo lại của nó theo cách sau: di ⇐ di x σs ri ⇐ ri x σs dN = - d0 Thành phần một chiều sẽ không lượng tử hoá (phần tử (0,0) của khối 8x8 được coi là thành phần một chiều, 63 phần tử còn lại được coi là các thành phần xoay chiều). Đến đây ta chuyển sang bước nén. ij ijij ij C C σ μ−= Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 47 D. Nén Đầu vào của khối nén gồm hai thành phần: thành phần các hệ số xoay chiều và thành phần các hệ số một chiều . Thành phần các hệ số một chiều Ci(0,0) với i = 0,1,…, 63 chứa phần lớn năng lượng tín hiệu hình ảnh. Người ta không nén trực tiếp các giá trị Ci(0,0) mà xác định độ lệch của Ci(0,0): di = Ci+1(0,0) - Ci(0,0) di có giá trị nhỏ hơn hiều so với Ci nên trong biểu diễn dấu phẩy động có nhều chuỗi bít 0 cho hiệu suất nén cao hơn. Giá trị C0(0,0) và các độ lệch di được ghi ra một tệp tạm thời. Tệp này được nén bằng phương pháp nén Huffman. Thành phần các hệ số xoay chiều Ci(m,n) với 1=m<=7, 1<= n<=7 chứa các thông tin chi tiết của ảnh. Để nâng cao hiệu quả nén cho mỗi bộ hệ số trong một khối người ta xếp chúng lại theo thứ tự Zig-Zag. Việc sắp xếp này giúp tạo ra nhiều loạt hệ số giống nhau do năng lượng của khối hế số giảm dần từ góc trên bên trái xuống góc dưới bên phải.Dươi đây là một minh hoạ về khối Zig-Zag : 0 2 3 9 10 20 21 35 1 4 8 11 19 22 34 36 5 7 12 18 23 33 37 48 6 13 17 24 32 38 47 49 14 16 25 31 39 46 50 57 15 26 30 40 45 51 56 58 Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 48 27 29 41 44 52 55 59 62 28 42 43 53 54 60 61 63 Hình 2.5.5 : Minh hoạ khối Zig-Zag Mỗi khối Zig-Zag này được mã hoá theo phương pháp RLE. Cuối mỗi khối đầu ra của RLE, ta đặt dấu kết thúc khối EOB (End Of Block). Sau đó các khối được dồn lại và lại mã hoá một lần bằng phương pháp mã Huffman. Nhờ có dấu kết thúc khối nên có thể phân biệt hai khối cạnh nhau khi giải mã Huffman. Hai bảng mã Huffman cho hai thành phần hệ số tất nhiên sẽ khác nhau. Để có thể giải nén được, chúng ta phải ghi lại các thông tin như: kích thước ảnh, kích thước khối, ma trận T, độ lệch tiêu chuẩn, các mức tạo lại, hai bảng mã Huffman, kích thước khối nén một chiều, kích thước khối nén xoay chiều … và ghi nối tiếp vào hai tệp nén của hai thành phần hệ số. Cài đặt giải thuật cho nén JPEG thực sự phức tạp. chúng ta phải lắm được các kiến thức về nén RLE, Huffman, biến đổi Cosin, xây dựng bộ lượng tử hoá Lloyd – Max … Tuy nén và giải nén JPEG hơi chậm nhưng bù lại cho kích thước tệp nén nhỏ. II.5.3.Một số thủ tục chương trình : • Chương trình nén phương pháp JPEG: bool CJPEG::write_JPEG_file(const char * filename, int quality) // JPEG compression { struct jpeg_compress_struct cinfo; Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 49 struct jpeg_error_mgr jerr; FILE * outfile; unsigned char ** buffer; int row_stride; outfile = fopen(filename, "wb"); if (outfile == NULL) return false; cinfo.err = jpeg_std_error(&jerr); jpeg_create_compress(&cinfo); jpeg_stdio_dest(&cinfo, outfile); cinfo.image_width = m_width; cinfo.image_height = m_height; cinfo.input_components = m_mode; switch (m_mode) { case MODE_RGB: cinfo.in_color_space = JCS_RGB; break; case MODE_GRAYSCALE: cinfo.in_color_space = JCS_GRAYSCALE; break; } jpeg_set_defaults(&cinfo); jpeg_set_quality(&cinfo, quality, TRUE); jpeg_start_compress(&cinfo, TRUE); row_stride = m_width * cinfo.input_components; buffer = new unsigned char * [cinfo.image_height]; buffer[0] = new unsigned char[cinfo.image_height * row_stride]; for (int k = 0; k < (int)(cinfo.image_height); k++) { buffer[k] = buffer[0] + row_stride*k; Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 50 } int i, j; switch (m_mode) { case MODE_RGB: for (j = 0; j < m_height; j++) { for (i = 0; i < m_width*3; i += 3) { buffer[j][i] = image[j][i/3].red; buffer[j][i+1] = image[j][i/3].green; buffer[j][i+2] = image[j][i/3].blue; } } break; case MODE_GRAYSCALE: for (j = 0; j < m_height; j++) { for (i = 0; i < m_width; i++) { buffer[j][i] = gImage[j][i]; } } break; } while (cinfo.next_scanline < cinfo.image_height) { (void) jpeg_write_scanlines(&cinfo, &buffer[cinfo.next_scanline], 1); Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 51 } jpeg_finish_compress(&cinfo); fclose(outfile); delete [] buffer[0]; delete [] buffer; jpeg_destroy_compress(&cinfo); return true; } • Chương trình giải nén phương pháp JPEG: int CJPEG::write_BMP_file(const char * outfile) // Writes a bitmap (.bmp) file (JPEG decompression) { FILE * fp; size_t result; int rowEndBytes = (4-(m_width*3)%4)%4; BITMAPFILEHEADER bmFileHdr; bmFileHdr.bfType = 0x4d42; bmFileHdr.bfSize = 58 + (m_width*3 + rowEndBytes) * m_height; bmFileHdr.bfReserved1 = 0; bmFileHdr.bfReserved2 = 0; bmFileHdr.bfOffBits = 58; BITMAPINFOHEADER bmInfo; bmInfo.biSize = 40; bmInfo.biWidth = m_width; bmInfo.biHeight = m_height; bmInfo.biPlanes = 1; bmInfo.biBitCount = 24; bmInfo.biCompression = BI_RGB; Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 52 bmInfo.biSizeImage = (m_width*3 + rowEndBytes) * m_height; bmInfo.biXPelsPerMeter = 0; bmInfo.biYPelsPerMeter = 0; bmInfo.biClrUsed = 0; bmInfo.biClrImportant = 0; fp = fopen(outfile, "wb"); if (fp == NULL) return WRITE_BMP_FILENOTFOUND_ERR; result = fwrite((char *)&bmFileHdr, sizeof(BITMAPFILEHEADER), 1, fp); if (result == 0) { fclose(fp); return WRITE_BMP_WRITE_ERR; } result = fwrite((char *)&bmInfo, sizeof(BITMAPINFO), 1, fp); if (result == 0) { fclose(fp); return WRITE_BMP_WRITE_ERR; } RGBpixel pixel; BYTE pJunk = 0; for (int j = m_height - 1; j >= 0; j--) { for (int i = 0; i < m_width; i++) { this->getPixel(j, i, pixel); result = fwrite((BYTE *)&pixel.blue, sizeof(BYTE), 1, fp); Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 53 if (result == 0) { fclose(fp); return WRITE_BMP_WRITE_ERR; } result = fwrite((BYTE *)&pixel.green, sizeof(BYTE), 1, fp); if (result == 0) { fclose(fp); return WRITE_BMP_WRITE_ERR; } result = fwrite((BYTE *)&pixel.red, sizeof(BYTE), 1, fp); if (result == 0) { fclose(fp); return WRITE_BMP_WRITE_ERR; } } if (rowEndBytes != 0) result = fwrite((BYTE *)&pJunk, sizeof(BYTE), rowEndBytes, fp); if (result == 0) { fclose(fp); return WRITE_BMP_WRITE_ERR; } } fclose(fp); return WRITE_BMP_SUCCESS; Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 54 } II.6.Phương pháp mã hoá JPEG2000: II.6.1. Lịch sử ra đời và phát triển chuẩn JPEG2000: Như chúng ta đã biết, sự ra đời của JPEG mang lại nhiều lợi ích to lớn về nhiều mặt. JPEG có thể giảm nhỏ kích thước ảnh, giảm thời gian truyền và làm giảm chi phí xử lý ảnh trong khi chất lượng ảnh là khá tốt. Tuy nhiên cho đến nay người ta mới chỉ ứng dụng dạng thức nén có tổn thất thông tin của JPEG vì mã hoá không tổn thất của JPEG là khá phức tạp. Để việc nén ảnh có hiệu quả hơn, Ủy ban JPEG đã đưa ra một chuẩn nén ảnh mới là JPEG2000. JPEG2000 sử dụng biến đổi Wavelet và các phương pháp mã hoá đặc biệt để có được ảnh nén ưu việt hơn hẳn JPEG. JPEG2000 hiện vẫn đang tiếp tục được phát triển, nhưng phần I đã được tổ chức ISO chấp nhận là chuẩn nén ảnh quốc tế áp dụng cho ảnh tĩnh. Chuẩn nén ảnh JPEG2000 Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 55 mà xương sống là biến đổi Wavelet với tính năng vượt trội so với JPEG chắc chắn sẽ được sử dụng trong các server nội dung để chuyển đổi định dạng ảnh trong mạng di động. II.6.2.Các tính năng của JPEG2000: JPEG2000 có nhiều chức năng đặc biệt hơn mọi chuẩn nén ảnh tĩnh khác như JPEG hay GIF. Dưới đây là các chức năng ưu việt của JPEG2000 so với các chuẩn nén ảnh tĩnh khác - Cho chất lượng ảnh tốt nhất khi áp dụng nén ảnh tĩnh có tổn thất. - Sử dụng được với truyền dẫn và hiển thị luỹ tiến về chất lượng, độ phân giải, các thành phần màu và có tính định vị không gian. - Sử dụng cùng một cơ chế nén ảnh cho cả hai dạng thức nén. - Truy nhập và giải nén tại mọi thời điểm trong khi nhận dữ liệu. - Giải nén từng vùng trong ảnh mà không cần giải nén toàn bộ ảnh. - Có khả năng mã hoá ảnh với tỷ lệ nén theo từng vùng khác nhau. - Nén một lần nhưng có thể giải nén với nhiều cấp chất lượng tuỳ theo yêu cầu của người sử dụng. Hiện tại, ISO và uỷ ban JPEG đã đưa ra khuyến nghị thay thế JPEG bằng JPEG2000. II.6.3.Các bước thực hiện nén ảnh theo chuẩn JPEG2000: Xử lý trước biến đổi Biến đổi thuận liên thành phần Biến đổi thuận riêng thành phần Lượng tử hoá Mã hoá Giải mã hoá Giải lượng tử hoá Biến đổi ngược riêng thành phần Biến đổi ngược liên thành phần Xử lý sau biến đổi Ảnh gốc Ảnh khôi phục Ảnh sau mã hoá Ảnh mã hoá Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 56 Hình 2.6.1:Các bước nén và giải nén JPEG2000 II.6.3.1.Xử lý trước biến đổi: Do sử dụng biến đổi Wavelet, JPEG2000 cần có dữ liệu ảnh đầu vào ở dạng đối xứng qua 0. Xử lý trước biến đổi chính là giai đoạn đảm bảo dữ liệu đưa vào nén ảnh có dạng trên. Ở phía giải mã, giai đoạn xử lý sau biến đổi sẽ trả lại giá trị gốc ban đầu cho dữ liệu ảnh. II.6.3.2. Biến đổi liên thành phần : Giai đoạn này sẽ loại bỏ tính tương quan giữa các thành phần của ảnh. JPEG2000 sử dụng hai loại biến đổi liên thành phần là biến đổi màu thuận nghịch (Reversible Color Transform - RCT) và biến đổi màu không thuận nghịch (Irreversible Color Transform - ICT) trong đó biến đổi thuận nghịch làm việc với các giá trị nguyên, còn biến đổi không thuận nghịch làm việc với các giá trị thực. ICT và RCT chuyển dữ liệu ảnh từ không gian màu RGB sang YCrCb. RCT được áp dụng trong cả hai dạng thức nén có tổn thất và không tổn thất, còn ICT chỉ áp dụng cho nén có tổn thất. Việc áp dụng các biến đổi này trước khi nén ảnh không nằm ngoài mục đích làm tăng hiệu quả nén. Các thành phần Cr, Cb có ảnh hưởng rất ít tới sự cảm nhận hình ảnh của mắt trong khi thành phần độ chói Y có ảnh hưởng rất lớn tới ảnh. Chúng ta có thể thấy rõ hơn điều này trên hình vẽ sau: Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 57 Hình 2.6.2 II.6.3.3. Biến đổi riêng thành phần (biến đổi Wavelet) : Biến đổi riêng thành phần được áp dụng trong JPEG2000 chính là biến đổi Wavelet. Để đảm bảo tính toàn vẹn thông tin cũng phải áp dụng các phép biến đổi thuận nghịch hoặc không thuận nghịch. Do phép biến đổi Wavelet không phải là một phép biến đổi trực giao như biến đổi DCT mà là một phép biến đổi băng con nên các thành phần sẽ được phân chia thành các băng tần số khác nhau và mỗi băng sẽ được mã hóa riêng rẽ. JPEG2000 áp dụng biến đổi Wavelet nguyên thuận nghịch 5/3 (IWT) và biến đổi thực không thuận nghịch Daubechies 9/7. Việc tính toán biến đổi trong JPEG2000 này sẽ được thực hiện theo phương pháp Lifting. Sơ đồ của phương pháp Lifting 1D áp dụng trong JPEG2000 trên hình 2.6.3.Việc tính toán biến đổi Wavelet 2D suy ra từ biến đổi Wavelet 1D theo các phương pháp phân giải ảnh tuỳ chọn. Trong JPEG2000 có 3 phương pháp phân giải ảnh nhưng phương pháp được sử dụng nhiều nhất chính là phương pháp kim tự tháp. Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 58 Hình 2.6.3 Do biến đổi Wavelet 5/3 là biến đổi thuận nghịch nên có thể áp dụng cho nén ảnh theo cả hai phương pháp, có tổn thất và không tổn thất trong khi biến đổi 9/7 chỉ áp dụng cho nén ảnh theo phương pháp có tổn thất thông tin. II.6.3.4. Lượng tử hoá - Giải lượng tử hoá : Các hệ số của phép biến đổi sẽ được tiến hành lượng tử hoá. Quá trình lượng tử hoá cho phép đạt tỷ lệ nén cao hơn bằng cách thể hiện các giá trị biến đổi với độ chính xác tương ứng cần thiết với mức chi tiết của ảnh cần nén. Các hệ số biến đổi sẽ được lượng tử hoá theo phép lượng tử hoá vô hướng. Các hàm lượng tử hoá khác nhau sẽ được áp dụng cho các băng con khác nhau và được thực theo biểu thức: V(x,y) = ),(sgn|),(| yxUyxU ⎥⎦ ⎤⎢⎣ ⎡ Δ với Δ là bước lượng tử, U(x,y) là giá trị băng con đầu vào; V(x,y) là giá trị sau lượng tử hoá. Trong dạng biến đổi nguyên, đặt bước lượng tử bằng 1.Với dạng biến đổi thực thì bước lượng tử sẽ được chọn tương ứng cho Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 59 từng băng con riêng rẽ. Bước lượng tử của mỗi băng do đó phải có ở trong dòng bít truyền đi để phía thu có thể giải lượng tử cho ảnh. Công thức giải lượng tử hoá là: U(x,y) = [ ]Δ+ ),(sgn),( yxVryxV r là một tham số xác định dấu và làm tròn, các giá trị ( U x,y);V(x,y) tương ứng là các giá trị khôi phục và giá trị lượng tử hoá nhận được. JPEG2000 không cho trước r tuy nhiên thường chọn r =1/ 2 . II.6.3.5. Mã hoá và kết hợp dòng dữ liệu sau mã hoá: JPEG2000 theo khuyến nghị của uỷ ban JPEG quốc tế có thể sử dụng nhiều phương pháp mã hoá khác nhau cũng như nhiều cách biến đổi Wavelet khác nhau để có thể thu được chất lượng ảnh tương ứng với ứng dụng cần xử lý. Điều này giúp cho JPEG2000 mềm dẻo hơn nhiều so với JPEG. Việc áp dụng các phương pháp mã hoá khác nhau cũng được mở rộng sang lĩnh vực nén ảnh động bằng biến đổi Wavelet. Trong thực tế các phương pháp mã hoá ảnh được áp dụng khi nén ảnh bằng biến đổi Wavelet cũng như JPEG2000 thì có hai phương pháp được coi là cơ sở và được áp dụng nhiều nhất: phương pháp SPIHT và phương pháp EZW. Hiện nay JPEG2000 vẫn được áp dụng mã hoá bằng hai phương pháp này và một phương pháp phát triển từ hai phương pháp này là phương pháp mã hoá mặt phẳng bít. Vì thế ở đây chúng ta sẽ xem xét hai phương pháp này. Việc kết hợp dòng dữ liệu sau mã hoá của JPEG2000 thực chất là để thực hiện các tính năng đặc biệt của JPEG2000 như tính năng ROI v.v... II.6.3.6. Phương pháp mã hoá SPIHT: Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 60 Có thể thấy rằng dù áp dụng biến đổi Wavelet nào hay cùng với nó là một phép phân giải ảnh nào thì trong các băng con có số thứ tự thấp cũng là những thành phần tần số cao (mang thông tin chi tiết của ảnh) trong khi những băng con có số thứ tự cao hơn thì sẽ chứa những thành phần tần số thấp (mang thông tin chính về ảnh). Điều đó nghĩa là các hệ số chi tiết sẽ giảm dần từ băng con mức thấp (HH1 chẳng hạn) (ứng với thành phần tần số cao) xuống băng con mức cao (ứng với thành phần tần số thấp) và có tính tương tự về không gian giữa các băng con, ví dụ như một đường biên của hình vẽ trong ảnh sẽ tồn tại ở cùng một vị trí trên các băng con đó (tương ứng với mức độ phân giải của băng con ấy). Điều này đã dẫn tới sự ra đời của phương pháp SPIHT (Set partitioning in hierarchical trees - phương pháp mã hoá phân cấp theo phân vùng). Phương pháp SPIHT được thiết kế tối ưu cho truyền dẫn luỹ tiến. Điều này có nghĩa là tại mọi thời điểm trong quá trình giải nén ảnh theo phương pháp mã hoá này thì chất lượng ảnh hiển thị tại thời điểm ấy là tốt nhất có thể đạt được với một số lượng bít đưa vào giải mã tính cho tới thời điểm ấy. Ngoài ra, phương pháp này sử dụng kỹ thuật embedded coding; điều đó có nghĩa là một ảnh sau nén với kích cỡ (lưu trữ) lớn (tỷ lệ nén thấp) sẽ chứa chính dữ liệu sau nén của ảnh có kích cỡ (lưu trữ) nhỏ (tỷ lệ nén cao). Bộ mã hoá chỉ cần nén một lần nhưng có thể giải nén ra nhiều mức chất lượng khác nhau. Giả sử gọi các pixel trong một ảnh p cần mã hoá là pi, j. Áp dụng một phép biến đổi Wavelet T nào đó cho các pixel trong ảnh để tạo ra các hệ số của phép biến đổi Wavelet là ci, j. Các hệ số này tạo ra một ảnh biến đổi là C. Phép biến đổi này được viết dưới dạng toán tử như sau: C=T(p). Trong phương pháp truyền dẫn luỹ tiến với ảnh thì bộ mã hoá sẽ bắt đầu quá trình khôi phục (giải nén) ảnh bằng cách đặt các giá trị của ảnh khôi phục từ các hệ số biến đổi là cˆ . Sử dụng các giá trị giải mã của các hệ số biến đổi để tạo ra một ảnh khôi phục (vẫn chưa áp dụng biến đổi ngược Wavelet) là cˆ và sau đó áp dụng biến đổi Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 61 ngược Wavelet để tạo ra ảnh cuối cùng là pˆ . Chúng ta có thể viết dưới dạng toán tử như sau: pˆ =T−1 ( cˆ ). Nguyên tắc quan trọng của phương pháp truyền dẫn ảnh theo kiểu luỹ tiến chính là phương pháp này luôn truyền đi các giá trị mang thông tin quan trọng hơn của ảnh đi trước. Sở dĩ làm như vậy là do các thông tin đó chính là các thông tin sẽ làm giảm thiểu nhiều nhất độ méo dạng của ảnh (sự sai khác giữa ảnh gốc và ảnh khôi phục). Đây chính là lý do tại sao phương pháp SPIHT luôn truyền đi các hệ số lớn trước và cũng là một nguyên tắc quan trọng của phương pháp này. Một nguyên tắc nữa là các bít có trọng số lớn bao giờ cũng mang thông tin quan trọng nhất trong dữ liệu nhị phân. Phương pháp SPIHT sử dụng cả hai nguyên tắc này; nó sắp xếp các hệ số biến đổi và truyền đi các bít có trọng số lớn nhất. Quá trình giải mã có thể dừng lại ở bất kỳ một bước nào ứng với giá trị ảnh cần mã hoá yêu cầu. Đây chính là cách mà phương pháp mã hoá SPIHT làm tổn thất thông tin. II.6.3.7. Phương pháp mã hoá EZW: Phương pháp mã hoá EZW (Embedded Zerotree Wavelet Encoder) cũng dựa trên cơ sở phép mã hoá luỹ tiến (progressive coding) giống như phương pháp mã hoá SPIHT. Phương pháp này chủ yếu dựa trên khái niệm về cây zero (zerotree). Về cơ bản, thuật toán này dựa trên hai nguyên tắc như đã trình bày ở phần phương pháp mã hoá SPIHT. Sau đây chúng ta sẽ xem xét các khái niệm cơ bản của thuật toán: Cây tứ phân: Sau khi áp dụng biến đổi Wavelet ứng với các mức phân giải khác nhau chúng ta có thể biểu diễn các hệ số biến đổi dưới dạng một cây. Ta thấy rằng với cây biểu diễn này cứ mỗi nút cha thì có 4 nút con. Sở dĩ có được điều này là do quá trình biến đổi Wavelet ở các tỷ lệ khác nhau. Ta gọi đây là các cây tứ phân (quadtree). Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 62 Hình 2.6.4: Cây tứ phân Cây zero (zerotree): Cây zero là một cây tứ phân, trong đó tất cả các nút của nó đều nhỏ hơn nút gốc. Một cây như vậy khi mã hoá sẽ được mã hoá bằng một đối tượng duy nhất và khi giải mã thì chúng ta cho tất cả các giá trị bằng không. Ngoài ra để có thể mã hoá được các hệ số Wavelet trong trường hợp này, giá trị của nút gốc phải nhỏ hơn giá trị ngưỡng đang được xem xét ứng với hệ số Wavelet đó Sau khi có đủ các khái niệm cần thiết về cây tứ phân và cây zero, chúng ta có thể trình bày nguyên lý hoạt động của thuật toán. Thuật toán sẽ mã hoá các hệ số theo thứ tự giảm dần. Chúng ta sẽ dùng một giá trị gọi là ngưỡng (threshold) và sử dụng ngưỡng này để tiến hành mã hoá các hệ số biến đổi. Các hệ số được mã hoá theo thứ tự từ vùng tần số thấp đến vùng tần số cao. Và chỉ những hệ số có giá trị tuyệt đối lớn hơn hoặc bằng ngưỡng thì mới được mã hoá. Tiếp theo giảm ngưỡng và tiếp tục làm như vậy cho tới khi ngưỡng đạt tới một giá trị nhỏ hơn giá trị của hệ số nhỏ nhất. Cách giảm giá trị ngưỡng ở đây thực hiện tương đối đặc biệt, giá trị của ngưỡng giảm xuống một nửa so với trước đó. Bộ giải mã phải biết các mức ngưỡng này thì mới có thể giải mã ảnh thành công. Nhưng khi ta đi từ nút cha đến nút con trong cây tứ phân thì nó vẫn có 3 nút con. Vậy ta phải đi theo nhánh có nút con nào trước. Hay nói một cách đầy đủ hơn ta di chuyển từ hệ số này đến hệ số khác theo thứ tự như thế nào. Có nhiều cách di chuyển khác nhau, tuy nhiên hai cách di chuyển trên hình trên được sử dụng nhiều nhất. Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 63 Hình 2.6.5 Việc sắp xếp này còn phải được quy ước thống nhất giữa quá trình mã hoá và quá trình giải mã để việc giải mã ảnh được thành công. Trên đây chỉ là nguyên lý cơ bản của phương pháp mã hoá EZW. Hiện nay phương pháp mã hoá này được áp dụng ngày càng nhiều nén ảnh động. Phương pháp này cho tỉ lệ nén và độ tin cậy giải mã cao. Ngoài ra phương pháp EZW rất dễ triển khai trên máy tính bởi phương pháp này không yêu cầu việc lập trình quá phức tạp. II.6.4.So sánh chuẩn JPEG2000 với JPEG và các chuẩn nén ảnh tĩnh khác: Một tính năng quan trọng và là ưu điểm rõ nét nhất của JPEG2000so với JPEG cũng như các chuẩn nén ảnh khác như MPEG 4 VTC hay JPEG - LS v. v.... là JPEG2000 đưa ra cả hai kỹ thuật nén có tổn thất và không tổn thất theo cùng một cơ chế mã hoá nghĩa là JPEG2000 thực hiện tất cả các dạng thức của JPEG chỉ bằng một cơ chế mã hoá duy nhất. Nếu xét về sự tồn tại của hai kỹ thuật này thì JPEG cũng có khả năng nén ảnh có tổn thất và không tổn thất thông tin. Tuy nhiên với JPEG thì cơ chế mã hoá với hai dạng này là khác nhau và rất khó để sử dụng cả hai dạng này cùng lúc cho cùng một ứng dụng. Do đó, có thể thấy rằng JPEG có tính mềm dẻo hơn bất kỳ chuẩn nén ảnh tĩnh nào trước đây. Hơn thế, chúng ta đã thấy rằng tất cả các phương pháp thiết kế cho chuẩn JPEG2000 đều ưu việt và có nhiều tính Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 64 năng hơn so với JPEG; ngoài ra những thống kê về thực tế cho thấy với cùng một tỷ lệ nén và một loại ảnh thì ảnh được nén bởi JPEG2000 hầu như luôn có chất lượng tốt hơn so với JPEG. Chúng ta xem xét hai ảnh trên hình 2.6.6 để thấy rõ điều này, ảnh bên trái được nén theo JPEG còn ảnh bên phải được nén theo JPEG2000. JPEG JPEG 2000 JPEG JPEG 2000 Hình 2.6.6 (a ,b) Tính năng ưu việt thứ hai của JPEG2000 so với JPEG chính là trong dạng thức nén có tổn thất thông tin, JPEG2000 có thể đưa ra tỷ lệ nén cao hơn nhiều so với JPEG. Các phần mềm nén ảnh JPEG hiện tại (kể cả Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 65 Photoshop) cũng chỉ thiết kế để có thể nén được tới tỷ lệ 40:1nhưng với JPEG2000 thì tỷ lệ nén có thể lên tới 200:1. Theo công thức tính PSNR trong đơn vị dB, chúng ta có: (b là số bít dùng biểu diễn một pixel trên ảnh gốc) PSNR(dB) = ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ − − 1210 log20 b RMSE Trong đó MSE( Mean square error ) là sai số bình phương trung bình , PSNR (peak to signal to noise ratio) là tỉ số tín hiệu trên nhiễu đỉnh.MSE thường được gọi là phương sai lượng tử - 2qσ (quantization error variance) .MSE giữa ảnh gốc và ảnh khôi phục được tính như sau : [ ] [ ]( )∑ −== kj q kigkifN MSE , 22 ,,1σ Trong đó tổng lấy theo j, k tính cho tổng tất cả các điểm ảnh trong ảnh và N là số điểm ảnh trong ảnh. RMSE là căn bậc 2 của MSE . Với hai ảnh ở hình 2.6.6, sự so sánh về tham số PSNR cho trên bảng bên dưới. Để có thể so sánh dễ dàng hơn, ta xét ảnh được nén với các tỷ lệ khác nhau (đo lường bởi hệ số bít/pixel hay bpp). Tất cả các số liệu trên bảng đều cho thấy JPEG2000 nén ảnh tốt hơn là JPEG; hơn thế hệ số PSNR mà chúng ta xét trong bảng được đo trong hệ đơn vị logarit. Bit per pixel 0.125 0.50 2.00 Ảnh 1 theo JPEG 24.42 31.17 35.15 Ảnh 1 theo JPEG2000 28.12 32.95 37.35 Ảnh 2 theo JPEG 22.6 28.92 35.99 Ảnh 2 theo JPEG2000 24.85 31.13 38.80 Tính năng ưu việt thứ 3 của JPEG2000 so với JPEG là chuẩn nén ảnh này có thể hiển thị được các ảnh với độ phân giải và kích thước khác nhau từ cùng một ảnh nén. Với JPEG thì điều này là không thể thực hiện được. Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 66 Sở dĩ có điều này là do JPEG2000 sử dụng kỹ thuật phân giải ảnh và mã hoá đính kèm mà chúng ta đã nói tới ở phần mã hoá ảnh theo JPEG2000. Tính năng này là một lợi thế đặc biệt quan trọng của JPEG2000, trong khi JPEG cũng như các chuẩn nén ảnh tĩnh trước đây phải nén nhiều lần để thu được chất lượng với từng lần nén khác nhau thì với JPEG2000 ta chỉ cần nén một lần còn chất lượng ảnh thì sẽ được quyết định tuỳ theo người sử dụng trong quá trình giải nén ảnh theo JPEG2000.Một tính năng ưu việt nữa của JPEG2000 là tính năng mã hoá ảnh quan trọng theo vùng (ROI - Region of Interest) mà chúng ta đã đề cập trong phần mã hoá ảnh theo JPEG2000. Hình 2.6.7 : Minh hoạ tính năng ROI JPEG2000 còn có một khả năng đặc biệt ưu việt hơn so với JPEG, đó chính là khả năng vượt trội trong khôi phục lỗi. Đó là khi một ảnh được truyền trên mạng viễn thông thì thông tin có thể bị nhiễu; với các chuẩn nén ảnh như JPEG thì nhiễu này sẽ được thu vào và hiển thị, tuy nhiên với JPEG2000, do đặc trưng của phép mã hoá có thể chống lỗi, JPEG2000 có thể giảm thiểu các lỗi này tới mức hầu như không có. CHƯƠNG III: CÀI ĐẶT CHƯƠNG TRÌNH VÀ THỬ NGHIỆM Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 67 • Từ những cơ sở lý thuyết trình bày ở trên em đã tiến hành cài đặt chương trình cho một số phương pháp nén ảnh : RLE, HUFFMAN, LZW, JPEG trên ngôn ngữ lập trình Visual C++ 6.0. • Chương trình chạy tương đối ổn định nhưng chỉ hỗ trợ định dạng ảnh Bitmap. Các phương pháp RLE, HUFFMAN, LZW chương trình chỉ chạy tốt trên ảnh Bitmap 256 màu còn đối với JPEG thì hiện thời mới hỗ trợ cho ảnh Bitmap 24 bit màu. • Các file ảnh được nén theo các phương pháp khác nhau sẽ được lưu với các định dạng đuỗi khác nhau HUFFMAN (*.huff) , LZW (*.lzw) , JPEG (*.jpg) riêng RLE vẫn giữ nguyên đuôi *.bmp. • Ngoài các thư viện và các hàm được hỗ trợ sẵn trong Visual C++ 6.0 chương trình còn sử dụng thêm một số thư viện riêng. • Các thuật toán đều có ưu nhược điểm khác nhau và đem lại kết quả chương trình khác nhau. Tốc độ nén và hiệu quả nén của các phương pháp rất khác nhau do độ phức tạp giải thuật và chất lượng ảnh kết quả yêu cầu là khác nhau. Phương pháp RLE, HUFFMAN cho kết quả nhanh chóng và chất lượng ảnh không thay đổi nhưng hiệu suất nén thường không cao đối với ảnh Bitmap 256 màu còn phương pháp LZW do trong thuật toán phải xây dựng từ điển nên tốc độ nén tương đối chậm nhưng kết quả nén rất cao.Cuối cùng phương pháp JPEG thì chất lượng ảnh nén và hiệu quả nén tỷ lệ nghịch với nhau, chất lượng ảnh nén tốt thì kích thước file giảm ít và ngược lại . Giao diện chính chương trình : Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 68 Các bước thực hiện chương trình : Phương pháp nén ảnh RLE Phương pháp nén ảnh HUFFMAN Phương pháp nén ảnh LZW Phương pháp nén ảnh JPEG Đường dẫn file nguồn Đường dẫn file đích Xem ảnh Kích thước file nguồn Kích thước file đích Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 69 1. Chọn mục đích thực hiện nén (Compression) hoặc giải nén (Decompression ) trong phương pháp nén muốn sử dụng. 2. Click vào nút “Duongdan” thứ nhất để mở file muốn thực thi ,nếu muốn xem ảnh chọn (nếu là ảnh Bitmap) thì click nút >> để xem ảnh còn kích thước file hiển thị bên dưới. 3. Click vào nút “Duongdan” thứ hai để chỉ đường dẫn đến file muốn lưu lại kết quả. 4. Click nút “Thuchien” xong chương trình sẽ thông báo bằng hộp hội thoại MessageBox còn riêng với JPEG ta còn phải chọn chất lượng ảnh nén thì mới thực hiện nén. Chất lượng càng cao thì ảnh sẽ ít bị thay đổi nhưng hiệu suất nén thấp và ngược lại. 5. Thông báo hoàn tất nén hoặc giải nén KẾT LUẬN Kết quả đạt được và ứng dụng của đồ án Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 70 Đồ án đã trình bày các khái niệm quan trọng cần thiết của kỹ thuật nén ảnh nói chung và các nguyên tắc , cơ sở lý thuyết ,thuật toán của một số phương pháp nén ảnh phổ biến như : mã loạt dài RLE, HUFFMAN, LZW, JPEG, JPEG2000.Trong đó trình bày phương pháp nén ánh JPEG2000 sử dụng biến đổi Wavelet để nén ảnh, đây là phương pháp nén ảnh đang được quan tâm phát triển vì các tính năng nổi bật so với các phương pháp khác. Phương pháp này không chỉ cho hiệu suất nén cao, chất lượng ảnh bảo đảm so với các phương pháp nén RLE, HUFFMAN, LZW, JPEG mà còn các tính năng riêng biệt do sư dụng biến đổi Wavelet để nén ảnh như : nén ảnh theo vùng (ROI) , trong một ảnh các vùng hoặc các đối tượng có thể có tỷ lệ nén khác nhau ,nén ảnh một lần nhưng có thể giải nén ảnh với chất lượng ảnh và kích thước ảnh khác nhau tuỳ theo yêu cầu người sử dụng ....Các phương pháp nén trình bày ở trong đồ án là những phương pháp đang được sử dụng khá rộng rãi trong nhiều lĩnh vực đặc biệt trong truyền thông cho ảnh trên mạng đảm bảo tốc độ, thời gian và chất lượng dữ liệu truyền. Hướng phát triển nghiên cứu Một số hướng nghiên cứu trong tương lai : • Đồ án mới đề cập đến các phương pháp nén ảnh tĩnh mà chưa ứng dụng chúng cho âm thanh, video, đặc biệt là biến đổi Wavelet của chuẩn JPEG2000 do đó việc đi sâu nghiên cứu tìm hiểu các họ của Wavelet là rất cần thiết. • Nghiên cứu thêm về các giải thuật SPIHT, EZW và các ứng dụng của chúng. • Các phương pháp nén được trình bày trong đồ án đã ra đời từ nhiều năm trước do đó cần nghiên cứu những cải tiến đối với mỗi phuơng pháp để nâng cao hiệu quả nén. Các tài liệu tham khảo: Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh Sinh viên thực hiện : Tạ Minh Thắng CT 702 Trang : 71 1. PGS.Nguyễn Thanh Thuỷ, Ths.Lương Mạnh Bá, Nhập môn xử lý ảnh số 2. Võ Đức Khánh (2003),Giáo trình xử lý ảnh , Nxb Thống kê, Hà Nội 3. D.Huffman , A method for the contruction of minimum – redundancy codes, Proc IRE 40, 1098-1101 (1952) 4. Nguyễn Kim Sách (1997), Xử lý ảnh và video số , Nxb Khoa học và Kỹ thuật , Hà Nội . 5. Michael David Adams - Faouzi Kossentini - Touraji Ebrahimi - “JPEG2000 : The Next Generation Still Image Compression Standard” (2000) 6. Website: 7. Website: