Xử lý ảnh - Các phương pháp nén ảnh

Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh XỬ LÝ ẢNH CÁC PHƯƠNG PHÁP NÉN ẢNH Giảng Viên: ThS. Đinh Phú Hùng Bộ môn: Kỹ Thuật Máy Tính & Mạng Email: hungdp@wru.edu.vn Ngày 5 tháng 2 năm 2015 1 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Nội Dung 1 Tổng quan về nén ảnh 2 Phân loại các phương pháp nén ảnh 3 Một số phương pháp nén ảnh 2 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Tổng quan về nén ảnh Một số khái niệm cơ bản: Dư thừa dữ liệu và thông tin. Nén dữ liệu. Tỉ lệ nén. Tính dung lượng ảnh. 3 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Dư thừa dữ liệu và thông tin Dữ liệu và thông tin không tương đương với nhau. Dữ liệu là phương tiện để thể hiện thông tin. Số lượng dữ liệu có thể nhiều hơn số lượng thông tin. Những dữ liệu dư thừa không cung cấp thêm thông tin. Nén ảnh mục đích là để giảm bớt lượng dữ liệu dư thừa trong khi vẫn giữ nguyên được lượng thông tin. 4 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Một số kiểu dư thừa dữ liệu trong ảnh Kiểu 1: Dư thừa mã Một số mức xám trong ảnh phổ biến hơn các mức xám còn lại. Kiểu 2: Dư thừa trong pixel Giá trị của các pixel trong ảnh có thể được dự đoán hợp lý từ các pixel láng giềng. Kiểu 3: Dư thừa trong thị giác mắt Mắt người chỉ có thể phân biệt được một số lượng màu sắc nhất định. 5 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Một số kiểu dư thừa dữ liệu trong ảnh 6 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Nén dữ liệu Nén dữ liệu nhằm làm giảm lượng thông tin “dư thừa” trong dữ liệu gốc. 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. Tạo ra sự hiệu quả trong việc lưu trữ và truyền tải dữ liệu. 7 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh 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. Gọi n1 là dữ liệu ban đầu, n2 là dữ liệu sau khi nén. Tỉ lệ nén Cr được tính như sau: Cr = n1 n2 Dữ liệu dư thừa: Dr = 1− 1 Cr 8 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Dung lượng ảnh Cho một ảnh I có kích thước MxN. Gọi L là số mức xám của ảnh I. Dung lượng của ảnh được tính theo công thức: M ∗ N ∗ Ltb. Trong đó: Ltb = L−1∑ k=0 l(rk)p(rk) l(rk) là độ dài bit biểu diễn cho mức xám rk . p(rk) là xác suất của mức xám rk trong ảnh I. p(rk) = nk M ∗ N 9 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Dung lượng ảnh Ví dụ: Giả sử ảnh 3 bit I có thống kê về các mức xám như bảng sau. Tính dung lượng của ảnh I. rk n(rk) p(rk) mã 0 113 0.051 000 1 139 0.063 001 2 142 0.064 010 3 145 0.066 011 4 181 0.082 100 5 105 0.047 101 6 52 0.023 110 7 1323 0.601 111 Giá trị trung bình mỗi pixel: Ltb = L−1∑ k=0 l(rk)p(rk) = 3 bit Dung lượng của ảnh I: C = Ltb ∗ L−1∑ k=0 n(rk) C = 3 ∗ 2200 = 6600 bit 10 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phân loại các phương pháp nén ảnh Có nhiều cách phân loại các phương pháp nén khác nhau: Phương pháp nén không mất mát thông tin. - Ảnh nén sau khi giải nén có thể thu được dữ liệu ảnh ban đầu. - Tỉ lệ nén thấp từ 2 đến 10 lần. Phương pháp nén có mất mát thông tin. - Ảnh nén sau khi giải nén không thu được dữ liệu như ảnh gốc ban đầu. - Tỉ lệ nén cao từ 10 đến 30 lần. 11 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phân loại các phương pháp nén ảnh Dựa vào quá trình phát triển của các phương pháp nén. Có thể chia các phương pháp nén thành hai nhóm: 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ụ 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 độ bão hòa của tỷ lệ nén. 12 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman. Phương pháp nén ảnh Run-Length Encoding. Phương pháp nén ảnh LZW 13 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Được đề xuất bởi Huffman vào năm 1952. Là phương pháp dựa vào mô hình thống kê. Ý tưởng của phương pháp: gán cho các mức xám có tần suất cao trong ảnh một từ mã ngắn, các mức xám có tần suất thấp từ mã dài. 14 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Ví dụ: Cho ảnh I 3 bit, kích thước 44x50 có các mức xám được biểu diễn bởi các mã trong bảng sau. Tính dung lượng ảnh I ứng với các mã đó. rk n(rk) p(rk) mã 1 mã 2 0 113 0.051 000 1011 1 139 0.063 001 1010 2 142 0.064 010 1001 3 145 0.066 011 1000 4 181 0.082 100 110 5 105 0.047 101 1110 6 52 0.023 110 1111 7 1323 0.601 111 0 15 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Đối với mã 1, dung lượng ảnh I: C1 = Ltb ∗M ∗ N = 3 ∗ 44 ∗ 50 = 6600bit Đối với mã 2: - Độ dài trung bình mỗi pixel: Ltb = L−1∑ k=0 l(rk)p(rk) = 2.1bit - Dung lượng ảnh I: C2 = Ltb ∗M ∗ N = 2.1 ∗ 44 ∗ 50 = 4620bit 16 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Đầu vào: Ảnh I có kích thước MxN và có K mức xám. Đầu ra: Ảnh I* được nén theo phương pháp Huffman. Phương pháp này gồm 2 giai đoạn: Giai đoạn 1: Xây dựng cây nhị phân Huffman Duyệt toàn bộ ảnh để tính xác suất các mức xám có trong ảnh. Khởi tạo rừng có K cây, mỗi cây chỉ có một nút gốc, mỗi nút gốc tương ứng với một mức xám và có trọng số là tần số (hoặc xác suất) của mức xám đó trong ảnh. Thực hiện bước lặp cho đến khi rừng chỉ còn 1 cây: - Chọn hai cây có trọng số ở gốc nhỏ nhất hợp thành một cây bằng cách thêm một gốc mới nối với hai gốc đã chọn. - Trọng số của gốc mới bằng tổng trọng số của hai gốc tạo thành nó. 17 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Giai đoạn 2: Xây dựng mã cho các mức xám Bắt đầu từ 2 nút con ở gốc, gán giá trị 0 cho nút có xác suất cao và giá trị 1 cho nút có xác suất thấp. Đi dần xuống các nút lá cho đến nút cuối cùng của cây để gián giá trị cho tất cả các nút trên cây 18 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Cho ảnh 3 bit I có các thống kê mức xám như sau. Thực hiện nén ảnh I theo phương pháp Huffman. rk n(rk) p(rk) mã 0 113 0.051 000 1 139 0.063 001 2 142 0.064 010 3 145 0.066 011 4 181 0.082 100 5 105 0.047 101 6 52 0.023 110 7 1323 0.601 111 19 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Quá trình thực hiện bước 1 của phương pháp Huffman như sau: 20 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Quá trình thực hiện bước 1 của phương pháp Huffman như sau: 21 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Quá trình thực hiện bước 1 của phương pháp Huffman như sau: 22 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Quá trình thực hiện bước 1 của phương pháp Huffman như sau: 23 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Quá trình thực hiện bước 1 của phương pháp Huffman như sau: 24 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Quá trình thực hiện bước 1 của phương pháp Huffman như sau: 25 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Quá trình thực hiện bước 1 của phương pháp Huffman như sau: 26 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Xây dựng cây Huffman sau bước 1 như sau: 27 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Quá trình thực hiện bước 2 của phương pháp Huffman như sau: 28 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Quá trình thực hiện bước 2 của phương pháp Huffman như sau: 29 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Quá trình thực hiện bước 2 của phương pháp Huffman như sau: 30 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Quá trình thực hiện bước 2 của phương pháp Huffman như sau: 31 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Quá trình thực hiện bước 2 của phương pháp Huffman như sau: 32 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Quá trình thực hiện bước 2 của phương pháp Huffman như sau: 33 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Quá trình thực hiện bước 2 của phương pháp Huffman như sau: 34 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Gán mã cho cây Huffman như sau: 35 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Giá trị trung bình biểu diễn cho mỗi mức xám là: Ltb = L−1∑ k=0 l(rk)p(rk) = 2.1bit Dung lượng của ảnh I: C = Ltb ∗ L−1∑ k=0 n(rk) = 2.1 ∗ 2200 = 4620bit 36 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Bài tập áp dụng: Cho ảnh I 2 bit, kích thước 5 x 5 được biểu diễn bởi ma trận sau. Hãy nén ảnh I theo phương pháp Huffman, tính dung lượng ảnh I trước và sau khi nén. 0 1 0 0 1 2 1 0 1 0 0 3 0 1 0 0 2 3 1 0 0 1 0 0 2  37 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén ảnh Huffman Kết quả sau khi thực hiện: rk n(rk) p(rk) mã 1 mã 2 0 13 0.52 00 0 1 7 0.28 01 10 2 3 0.12 10 110 3 2 0.08 11 111 Dung lượng ảnh I trước khi nén: C1 = Ltb ∗M ∗ N = 2 ∗ 5 ∗ 5 = 50bit Dung lượng ảnh I sau khi nén: C2 = Ltb ∗M ∗ N = 1.68 ∗ 5 ∗ 5 = 42bit 38 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén mã mạch dài Được đề xuất từ những năm 1950, lúc đầu được phát triển cho nén ảnh đen trắng. 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. Sau đó, thay thế chuỗi cũ bởi một chuỗi mới gồm 2 thông tin: chiều dài chuỗi và bít lặp (ký tự lặp). 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 đó. Chuỗi thay thế sẽ có chiều dài ngắn hơn chuỗi cần thay. Phương pháp này được sử dụng trong việc mã hóa lưu trữ các ảnh Bitmap theo dạng PCX, BMP. 39 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén mã mạch dài Đối với ảnh, có thể có các thứ tự duyệt sau: 40 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén mã mạch dài Ví dụ: Cho ảnh nhị phân I có ma trận ảnh (10 x 10) như sau. Dùng phương pháp mã hóa mạch dài để nén ảnh. Cho biết tỷ số nén. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  41 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén mã mạch dài Ảnh trước khi nén có kích thước là 100 bit. Sử dụng mã hóa mạch dài, ta có chuỗi sau khi nén: (23,0), (4,1), (6,0), (1,1), (2,0), (1,1), (6,0), (4,1), (9,0), (1,1), (9,0), (1,1), (6,0), (4,1), (23,0). Có tất cả 15 cặp. Dùng 5 bit để mã hóa số lượng các bit lặp, dùng 1 bit để mã hóa 2 giá trị 0 hoặc 1. Như vậy, độ dài sau khi mã hóa là: 15*(5+1) = 90 bit. Tỷ số nén: Cr = 100 90 = 1.1 Dữ liệu dư thừa: Dr = 1− 1 Cr = 0.1 = 10% 42 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén mã mạch dài Bài tập áp dụng: Cho ánh xám 3 bit I kích thước 8 x 8 có ma trận như sau. Dùng phương pháp mã hóa mạch dài để nén ảnh. Cho cho biết tỷ số nén. 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 4 4 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 0 7 0 7 0 7 0 0 0 0 0 0 0 0 0  43 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén mã mạch dài Ảnh trước khi nén có kích thước là 8*8*3 = 192 bit. Sử dụng mã hóa mạch dài, ta có chuỗi sau khi nén: (2,0), (9,1), (9,2), (4,3), (2,4), (3,5), (12,6), (8,7), (1,0), (1,7), (1,0), (1,7), (1,0), (1,7), (9,0). Có tất cả 15 cặp. Dùng 4 bit để mã hóa số lượng các bit lặp, dùng 3 bit để mã hóa các mức xám từ 0 đến 7. Như vậy, độ dài sau khi mã hóa là: 15*(4+3) = 105 bit. Tỷ số nén: Cr = 192 105 = 1.829 Dữ liệu dư thừa: Dr = 1− 1 Cr = 0.453 = 45.3% 44 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén LZW Khái niệm nén dựa trên từ điển được Jocob Lempe và Abraham Ziv đưa ra vào năm 1977. Năm 1984 Welch đã cải tiến giải thuật LZ thành giải thuật hiệu quả hơn đặt tên là LZW. Là phương pháp nén không mất thông tin. Phương pháp này xây dựng từ điển các chuỗi ký tự có tần suất lặp lại cao và thay thế bằng từ mã mỗi khi lặp lại chúng. LZW được dùng để nén tất cả các file nhị phân và là chuẩn nén cho các dạng ảnh GIF và TIFF. 45 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén LZW Phần quan trọng nhất của phương pháp nén này là phải tạo một mảng rất lớn dùng để lưu giữ các xâu kí tự đã gặp, mảng này được gọi là "Từ điển". Khi các byte dữ liệu cần nén được đem đến, chúng liền được giữ lại trong một bộ đệm chứa và đem so sánh với các chuỗi đã có trong "từ điển". Nếu chuỗi dữ liệu trong bộ đệm chứa không có trong "từ điển" thì nó được bổ sung thêm vào "từ điển" và chỉ số của chuỗi ở trong "từ điển" chính là dấu hiệu của chuỗi. Nếu chuỗi trong bộ đệm chứa đã có trong "từ điển" thì dấu hiệu của chuỗi được đem ra thay cho chuỗi ở dòng dữ liệu ra. 46 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén LZW Cấu trúc từ điển: 47 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén LZW Từ mã từ 0 đến 255 chứa các số nguyên từ 0 đến 255. Từ mã thứ 256 là mã đặc biệt.Để khắc phục trường hợp số mẫu lặp trong ảnh lớn hơn 4096. Mã xóa sẽ cho biết việc kết thúc mã hóa với từ điển cũ và bắt đầu bộ tự điển mới. Từ mã thứ 257 chứa mã kết thúc thông tin. Giúp phân chia file thành nhiều cụm ảnh (file ảnh động GIF có nhiều ảnh gộp lại). Các từ mã còn lại từ (258...4095) là các mẫu lặp lại trong ảnh. 48 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén LZW 512 phần tử đầu tiên được biểu diễn bởi 9 bit. 512 đến 1023 biểu diễn bởi 10 bit. 1024 đến 2047 biểu diễn bởi 11 bit. 2048 đến 4095 biểu diễn bởi 12 bit. 49 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén LZW Ví dụ: Cho ảnh xám I 8 bit kích thước 3 x 5 có ma trận như sau. Dùng phương pháp LZW để nén ảnh I. Cho biết tỷ số nén. I =  72 69 76 76 79 72 69 76 76 79 72 69 76 76 79  50 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén LZW Ảnh trước khi nén có dung lượng 3*5*8 = 120 bit. Chuỗi mức xám của ảnh ban đầu: 72-69-76-76-79-72-69-76-76-79-72-69-76-76-79. Xây dựng từ điển theo LZW như sau: 51 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén LZW 52 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén LZW Chuỗi mức xám của ảnh ban đầu sau khi nén như sau: 72-69-76-76-79-258-260-262-259-261. Dung lượng sau khi nén: 5*8 + 5*9 = 85 bit. Tỷ số nén: Cr = 120 85 = 1.411 Dữ liệu dư thừa: Dr = 1− 1 Cr = 0.291 = 29.1% 53 / 54 Tổng quan về nén ảnh Phân loại các phương pháp nén ảnh Một số phương pháp nén ảnh Phương pháp nén LZW Bài tập áp dụng: Cho ánh xám 8 bit I kích thước 5 x 5 có ma trận như sau. Dùng phương pháp LZW để nén ảnh. Cho cho biết tỷ số nén.  72 79 74 76 72 79 74 76 72 79 74 76 72 79 74 76 72 79 74 76 72 79 74 76 72  54 / 54