Đề tài Nén ảnh số

Click to edit Master title style Click to edit Master text styles Second level Third level Fourth level Fifth level 1/11/2009 ‹#› Nén Ảnh Số (Image Compression) GVHD:ThS.Phạm Thế Bảo 1.Nguyễn Trọng Hóa 0511011 2.Võ Quốc Đạt 0511051 3.Nguyễn Văn Tung 0511257 4.Hồ Sỹ Mạnh Trường 0611235 1/11/2009 1 Nội dung trình bày Giới thiệu Các loại dư thừa dữ liệu Mô hình nén ảnh Phân loại nén ảnh Nén không mất dữ liệu Nén mất dữ liệu 1 số chuẩn ảnh 1/11/2009 2 Đặt vấn đề 1/11/2009 3 Ảnh 32bit (3200*2400) Lưu trữ 245,760,000 bits ~ 30mb Chụp 100 tấm hình ~ 3 GB Đặt vấn đề 1/11/2009 4 Tom & Jerry (~20 phút) (VGA,24bit/pixel,24 hình/s) 44.236.800byte ~ 43200MB Nén ảnh là cần thiết Vấn đề Đặt ra 1/11/2009 5 Lượng thông tin Dữ liệu dư thừa Nguyên lý nén 1/11/2009 6 Dữ liệu dư thừa Tỉ lệ nén 1/11/2009 7 Loại bỏ dữ liệu dư thừa Tỉ lệ nén = (n2/n1)*100 (%) Hiệu xuất nén = 100 – tỉ lệ nén (%) Các loại dữ liệu dư thừa 1/11/2009 8 Những pixel láng giềng có giá trị tương tự nhau Xuất hiện các dãy pixel có giá trị bằng nhau Các giá trị khác nhau mà mắt người không thể nhận thấy Dư thừa mã Nhắc lại về tính toán Histogram: với p(rk) là xác suất của 1 pixel với giá trị rk Nếu số bit dùng để biểu diễn rk là l(rk), thì 1/11/2009 9 Dư thừa mã Ví dụ 1/11/2009 10 .7 Dư Thừa Mã 1/11/2009 11 Variable-Length Coding Nhận xét: 1/11/2009 12 Nguồn có các giá trị độc lập Nén bằng không hiệu quả Các kí tự xuất hiện thường xuyên Gán vào chuỗi bit ngắn Các kí tự xuất hiện ít Gán vào chuỗi bit dài hơn 2 phương pháp thường dùng là Huffman và LZW Dư thừa trong pixel 2 bức ảnh có Histogram gần giống nhau Ta lợi dụng sự phụ thuộc Của các pixel Mỗi pixel có thể ước lượng bởi các pixel láng giềng 1/11/2009 13 Dư Thừa trong pixel Còn gọi là dư thừa không gian, dư thừa hình học,dư thừa trong ảnh Để giảm dư thừa  biến đổi sang 1 dạng khác hiệu quả hơn 1/11/2009 14 Dư thừa trong pixel 1/11/2009 15 Ví dụ về giảm dư thừa trong pixel,dùng RLC Các phương pháp nén 1/11/2009 16 Dư thừa trong Pixel Mã loạt dài (Run length coding) Cây tứ phân Mã hóa vùng (Region Encoding) Hình nhiễu ít Mã dự đoán Nén fractal Mã chuyển đổi Hình nhiễu chấp nhận được Dư thừa tâm lý thị giác Mắt không đáp ứng với cùng độ nhậy của tất cả các thông tin nhìn thấy Thông tin ít quan trọng  không được nhìn thấy dư thừa Để giảm dư thừa lượng tử hóa  mất dữ liệu 1/11/2009 17 Dư thừa tâm lý thị giác Hình đầu là ảnh đơn sắc với 256 mức xám Ảnh giữa: Sau khi lượng tử hóa từ 256 xuống 16 mức xám CR= 2 Right picture: Dùng pp lượng tử hóa cải tiến mức xám (IGS) CR= 2 1/11/2009 18 Tiêu chuẩn chính xác Sự sai khác giữa 2 hàm được định nghĩa : Từ đó ,ta có sự sai khác giữa 2 ảnh : Căn bậc 2 bình phương trung bình lỗi trên toàn ảnh 1/11/2009 19 Tiêu chuẩn chính xác 1 tiêu chuẩn đánh giá khác: bình phương tỉ lệ tín hiệu nhiễu trung bình của ảnh nén và giải nén 1/11/2009 20 Mô hình nén Quá trình mã hóa nguồn làm nhiệm vụ giảm độ dư thừa ( dư thừa mã ,dư thừa trong pixel ,dư thừa tâm lý thị giác) Kênh mã hóa đảm bảo độ bền nhằm chống lệnh sự nhiễu trên kênh truyền 1/11/2009 21 encoder decoder f(x,y) f^(x,y) Mô hình nén 1/11/2009 22 f(x,y) channel Channel f^(x,y) Phân loại nén ảnh 1/11/2009 23 Nén ảnh Nén không mất dữ liệu Nén mất dữ liệu Thông tin được giữ nguyên, chất lượng hình tốt, tỉ lệ nén thấp Thông tin mất mát có thể chấp nhận được, chất lượng ảnh đủ theo yêu cầu, tỉ lệ nén cao Nén không mất dữ liệu Một số lĩnh vực ,ứng dụng yêu cầu không mất dữ liệu trong khi nén: Y khoa , kinh tế : các văn bản lưu trữ . Xử lý hình ảnh vệ tinh .Việc mất mát thông tin là điều không muốn Chụp ảnh số bằng tia X , thông tin bị mất có thể bao gồm các chẩn đoán chính xác Đó là động lực để thúc đẩy việc nén không mất dữ liệu Tỉ lệ nén CR=2 đến 10 ,áp dụng cho ảnh nhị phân và ảnh xám Dùng cho trường hợp dư thừa mã và dư thừa trong pixel 1/11/2009 24 Nén không mất dữ liệu Variable – length Coding LZW Run-length coding 1/11/2009 25 Variable-length coding Dùng để giảm dư thừa mã 1 số phương pháp: Huffman Mã hóa số học 1/11/2009 26 Mã Huffman Dùng để giảm dư thừa mã Dựa trên bảng tần suất xuất hiện các kí tự để xây dựng một bộ mã nhị phân cho các kí tự đó sao cho dung lượng (số bít) sau khi mã hóa là nhỏ nhất Kết quả sau cùng là tối ưu 1/11/2009 27 Mô hình 1/11/2009 28 Tạo bảng mã (tính toán và thống kê) Tính toán xác suất của mỗi kí tự bằng histogram ảnh nguồn Thêm xác suất đã tính vào bảng mã Mã hóa kí tự nguồn theo kí tự (symbol by symbol) Mã Huffman 1/11/2009 29 Mã Huffman 1/11/2009 30 Mã Huffman Ví dụ về cây Huffman 1/11/2009 31 Cho 1 file có bộ kí tự nguồn là S = {A,H,C,E,I} và có số lần xuất hiện tương ứng tỉ lệ {3, 2, 5, 8, 7}. ta có cấu trúc cây Huffman như sau: Ví dụ Huffman Tree 1/11/2009 32 3 5 8 2 7 A C E H I Ví dụ Huffman Tree 1/11/2009 33 3 5 8 2 7 5 A C E H I Ví dụ Huffman Tree 1/11/2009 34 3 5 8 2 7 5 10 15 A C E H I Ví dụ Huffman Tree 1/11/2009 35 3 5 8 2 7 5 10 15 25 1 1 1 1 0 0 0 0 A C E H I E = 01 I = 00 C = 10 A = 111 H = 110 Bảng mã Huffman Huffman code Input ACE Output (111)(10)(01) = 1111001 1/11/2009 36 E = 01 I = 00 C = 10 A = 111 H = 110 Giải mã Huffman 1 1/11/2009 37 3 5 8 2 7 5 10 15 25 1 1 1 1 0 0 0 0 A C E H I 1111001 Giải mã Huffman 2 1/11/2009 38 3 5 8 2 7 5 10 15 25 1 1 1 1 0 0 0 0 A C E H I 1111001 Giải mã Huffman 3 1/11/2009 39 3 5 8 2 7 5 10 15 25 1 1 1 1 0 0 0 0 A C E H I 1111001 A Giải mã Huffman 4 1/11/2009 40 3 5 8 2 7 5 10 15 25 1 1 1 1 0 0 0 0 A C E H I 1111001 A Giải mã Huffman 5 1/11/2009 41 3 5 8 2 7 5 10 15 25 1 1 1 1 0 0 0 0 A C E H I 1111001 AC Giải mã Huffman 6 1/11/2009 42 3 5 8 2 7 5 10 15 25 1 1 1 1 0 0 0 0 A C E H I 1111001 AC Giải mã Huffman 7 1/11/2009 43 3 5 8 2 7 5 10 15 25 1 1 1 1 0 0 0 0 A C E H I 1111001 ACE Giới hạn của mã Huffman chỉ hữu hiệu và thuật toán nén thực hiện được khi bộ kí tự nguồn và tần số của chúng đã được biết 1 file có dung lượng lớn việc tìm bộ kí tự nguồn có thể tốn nhiều chi phí. Một bản mã Huffman cho trước không thể được áp dụng cho tất cả các văn bản dù chúng có cùng bộ kí tự nguồn. 1/11/2009 44 Giới hạn của mã Huffman đối với những văn bản mà tần số xuất hiện của các kí tự không quá chênh lệch và có bộ kí tự nguồn lớn thì tác dụng nén dữ liệu của mã Huffman là không đáng kể - đưa ra mã Huffman có điều chỉnh ? 1/11/2009 45 Mã hóa số học 1/11/2009 46 Ý tưởng chính: Chuỗi Dãy pixel Bằng 1 số thực hoặc nguyên Giá trị số thực trong khoảng (0,1) Từ 1 số thực đó ta giải mã 1 cách duy nhất để ra chuỗi đã mã hóa Ví dụ: 1/11/2009 47 Mã hóa chuỗi “Probability line” ta có bảng mã sau: Ví dụ (tt) 1/11/2009 48 Từ bảng mã trên ta có: Giải mã 1/11/2009 49 (0.2572167752, 0.25721677526) Chọn số thực Văn bản cần giải mã Duy nhất Hạn chế trong quá trình mã hóa số học bằng số thực có thể rút ra nhược điểm của phương pháp này đó là số ký tự mã hóa sẽ phụ thuộc vào số chữ số sau phần thập phân, máy tính có thể hỗ trợ 80 bits để thể hiện phần này do đó chỉ có thể mã hóa một chuỗi có 10 ký tự hoặc 15 ký tự. 1/11/2009 50 - Mã hóa số học sẽ thực hiện dựa trên số nguyên 2 bytes - Khi sử dụng với số nguyên thay vì sử dụng xác suất của kí tự trong chuỗi ta tính toán dựa trên số ký tự đó xuất hiện trong dãy. Khắc phục Mã hóa số học Ta xét bộ bốn ký tự A = {a, b, c, d} với xác suất ký tự cố định p(a) = 0.3, p(b) = 0.2, p(c) = 0.4, và p(d) = 0.1. Xác suất ký tự được biểu thị bởi phần chia của khoảng [0.0, 1.0) trong bảng 2.4 1/11/2009 51 Mã LZW Được Jacob Braham Ziv đưa ra lần đầu tiên năm 1977, sau đó phát triển thành một họ giải thuật nén từ điển là LZ. Năm 1984, Terry Welch cải tiến giải thuật LZ thành một giải thuật tốt hơn :LZW Dùng để giảm dư thừa trong pixel Không cần biết trước xác suất phân bố của các pixel 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. 1/11/2009 52 Mã LZW Phương pháp : Xây dựng 1 từ điển 1/11/2009 53 Cấu trúc từ điển Mã LZW 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 để 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 mã là 12 bít(4096= 212). 1/11/2009 54 Mã LZW Ví dụ cơ chế nén LZW 1/11/2009 55 Cho chuỗi ban đầu 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. 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. Ý tưởng chính 1/11/2009 56 N N N N N 5 N N N N N 2 bytes 5 bytes Length Run Mã đường chạy (RLE) Vấn đề và ý tưởng: 1/11/2009 57 5 5 5 21 21 2 87 Giá trị các pixel giống nhau Thay thế 3 5 2 21 2 87 Làm sao phân biệt được giá trị đường chạy với giá trị pixel Phải có 1 ngưỡng nào đó để thay thế Vấn đề và cách giải quyết 1 1/11/2009 58 5 7 7 ……….. 7 6 270 số 7 Giải quyết 5,(256,7),(14,7),6 Vấn đề và cách giải quyết 2 1/11/2009 59 7 7 7 ……….. 55 Tất cả các số nhỏ hơn 128 Giải quyết 131,7,………..,55 +128 Giải quyết 2: 1/11/2009 60 Ta có chuỗi: 3,4,5,5,5,5,5,5,5,5,5,5,5,6,6,6,6,3,100,21,21,21….. Giải quyết 0010100,3,4,11,5,4,6,3,100,1xxxxxxx,3,21  Tổng giá trị byte thêm vào sẽ bằng 1/8 kích cỡ của luồng xuất (output stream). Nghĩa là kích cỡ luồng xuất sẽ tăng 12.5% Mã Đường chạy (RLE) 1/11/2009 61 Ảnh màu Red Green Blue Áp dụng mã đường chạy Mã Đường chạy (RLE) 1/11/2009 62 4 5 6 7 8 8 8 8 8 8 8 8 9 10 11 12 13 14 3 5 Giải quyết 4,5,6,7,(5,8),eof,(3,8),9,10,11,12,13,14 Ưu điểm cho phép trích một phần của ảnh nén Bị lỗi dòng trên thì những phần dưới giải nén bình thường Áp Dụng??? 1/11/2009 63 Nén mất dữ liệu Giảm lượng dữ liệu cần thiết để biểu diễn thông tin Có tỉ lệ nén cao (hơn 100:1) 1 số phương pháp Transform Coding Wavelet Coding 1/11/2009 64 Mã hóa bằng cách biến đổi 1 ánh biến đổi tuyến tính khả nghịch để biến đổi ảnh thành các hệ số biến đổi Các hệ số sau đó được lượng tử hóa và mã hóa Mục đích của mã hóa bằng biến đổi là tạo ra mối quan hệ giữa các pixel và gom nhiều nhất thông tin có thể bằng ít hệ số biến đổi nhất Quá trình nén xảy ra trong khi lượng tử hóa ( không phải trong quá trình biến đổi) 1/11/2009 65 Mã hóa bằng cách biến đổi 1/11/2009 66 Mã hóa bằng cách biến đổi Giả sử có 1 ảnh f(x,y) kích thước N x N Biến đổi thuận g(x,y,u,v) là nhân biến đổi thuận hay còn gọi là hàm cơ bản 1/11/2009 67 Mã hóa bằng cách biến đổi Biến đổi ngược h(x,y,u,v) là nhân biến đổi ngược (hay còn gọi là các hàm cơ bản) 1/11/2009 68 Mã hóa bằng cách biến đổi 1 số tính chất: hàm g(x,y,u,v) trong pt trên gọi là : tách được nếu g(x,y,u,v) =g1(x,y) g2(u,v) đối xứng nếu :g1 =g2 hay ta có g(x,y,u,v) =g1(x,y) g1(u,v) 1 số biến đổi hay gặp : Biến đổi Fourier rời rạc (DFT) ,biến đổi Walsh-Hadamard (WHT) , biến đổi Cosine rời rạc (DCT) 1/11/2009 69 Mã hóa bằng cách biến đổi 1/Biến đổi Fourier rời rạc : g(x,y,u,v) = h(x,y,u,v)= 2/Biến đổi Walsh-Hadamard: h(x,y,u,v) =g(x,y,u,v)= 1/11/2009 70 Mã hóa bằng cách biến đổi 1/11/2009 71 Mã hóa bằng cách biến đổi 3/Biến đổi Cosin rời rạc: (DCT) h(x,y,u,v) =g(x,y,u,v)= Với 1/11/2009 72 Mã hóa bằng cách biến đổi 1/11/2009 73 Mã hóa bằng cách biến đổi 1/11/2009 74 Mã hóa bằng cách biến đổi Bình phương trung bình lỗi Ta chia ảnh thành các ảnh con ,khi đó ta có hàm f(x,y) của ảnh con qua phép biến đổi ngược f(x,y) = với x,y =0,1,2,3….n-1 F = Với H = 1/11/2009 75 Mã hóa bằng cách biến đổi Ta định nghĩa 1 xấp xỉ = Với g( u,v) = ems =E{||F- ||2} = E{|| ||2} = E{|| ||2} = 1/11/2009 76 Mã hóa bằng cách biến đổi Lựa chọn kích thước ảnh con: Thường sử dụng các ma trận có kích thước 8 x 8 , 16 x16 1/11/2009 77 Các chuẩn ảnh cơ bản Ở đây chúng ta chỉ xét 2 chuẩn phổ biến nhất: JPEG (Joint Photographic Expert Group- Nhóm các chuyên gia phát triển chuẩn này). JPEG 2000 1/11/2009 78 JPEG_Mô hình nén(mất dữ liệu) 1/11/2009 79 Ảnh Gốc Ảnh con 8x8 Ảnh con 8x8 Ảnh con 8x8 Ảnh con 8x8 DCT Lượng tử hóa Mã hóa Ảnh nén Bảng lượng tử hóa Dùng mã huffman, RLC JPEG_Ví dụ 1/11/2009 80 Ảnh gốc -128 x y DCT u v Lượng tử hóa JPEG_Ví dụ 1/11/2009 81 Bảng lượng tử Công thức biến đổi Cosin rời rạc: JPEG_Mô hình giải nén 1/11/2009 82 Ảnh Giải nén Ảnh con 8x8 Ảnh con 8x8 Ảnh con 8x8 Ảnh con 8x8 DCT Ngược Lượng tử hóa ngược (inverse Quantizer) Giải mã Ảnh nén JPEG_Ví dụ 1/11/2009 83 Inverse Quantizer DCT ngược +128 JPEG_Ví dụ 1/11/2009 84 Ảnh gốc Ảnh đã nén + giải nén Biến đổi ngược cosin rời rạc: Đuôi mở Rộng .jpg và .jpeg 1/11/2009 85 Ảnh màu ????? 1/11/2009 86 RGB YUV Biến đổi Giới thiệu các chuẩn ảnh 1/11/2009 87 JPEG 2000 Giới thiệu chung: 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 Để việc nén ảnh có hiệu quả hơn, tháng 12/1999 một bản phác thảo tiêu chuẩn nén hình ảnh theo công nghệ mới JPEG2000 Tháng 8/2000, bản phác thảo về tiêu chuẩn JPEG2000 đã được lưu hành trong giới chuyên gia hình ảnh 12/2000 và được ISO hợp thức hóa năm nay để cho phép ứng dụng vào các hệ xử lý‎, phân phối. Chuẩn nén ảnh JPEG2000 88 JPEG-2000 sử dụng kỹ thuật mã hóa dạng sóng rời rạc (DWT – Descrete Wavelet Transform) dùng mã số học JPEG2000 có thể nén nhỏ tới100-200 lần mà hình ảnh không sai sót bao nhiêu so với hình ảnh gốc. Chuẩn nén ảnh JPEG2000 89 Các tính năng của jpeg2000 Cho chất lượng ảnh tốt nhất khi nén ảnh tĩnh có tổn thất 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 90 Chuẩn nén ảnh JPEG2000 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 Chuẩn nén ảnh JPEG2000 91 GIF (Graphics Interchange Format) Được giới thiệu bởi Compuserve năm 1987 (GIF87a), Hộ trợ hình động (nhiều hình ở trong 1 file). hộ trợ metadata vào 1989 (GIF89a) Mã hóa LZW (Lempel-Ziv-Welch) thay thế RLE (Run Length Encoding) trong ảnh B&W Hộ trợ tối đa 256 màu Ứng dụng Nén các dạng hình minh hoạ, bảng biểu hay các hình chụp đen trắng Đối với ảnh chụp Ảnh gốc: 1600x1200 (24 bits) ~5,49MB Gif JPG: ~900KB JPG ~1,4MB (8bits) JPG: 201x71 (8 bits) ~ 7kB Gif: 223x78 (8 bits) ~ 1kB 50% 2KB Ảnh Gốc: 201x71 (8 bits) ~15,20k 90% Jpg: 4,48KB JPG: 2,48 KB GIF: 1,84KB 50% Ảnh Gốc 391x165 (24 bits) ~ 198KB Gif: 26kB JPG:45kB PNG (Portable Network Graphics) Sử dụng thuật toán LZ77 với mã hóa Huffman Kết hợp với dự đoán trước (tính toán pixel dựa vào pixel trước đó). Hộ trợ 48bit (16 tỉ màu). PNG là khắc phục được những giới hạn của GIF nhưng không thực sự thay thế được vì không tạo được ảnh động 2,7MB 1,64kB (PNG) ~ 1,84KB (GIF) 16kB Gif ~ 2,61kB PNG ~1,77kB HD photo (chuẩn JPEG XR) Microsoft hy vọng chuẩn mới HD Photo cuối cùng sẽ thay thế cho chuẩn JPEG hiện tại. Trong số những điểm mới mà HD Photo mang lại có: nén hiệu quả hơn, màu sắc phong phú hơn, có thể lưu ảnh mà không mất dữ liệu khi nén, chạy trên các phần mềm máy ảnh, và hoàn toàn miễn phí. Khả năng hỗ trợ cho định dạng file này (được Microsoft gọi là Windows Media Photo) đã được tích hợp sẵn cho Windows Vista. HD Photo cũng có thể được sử dụng để trình diễn hình ảnh trực tuyến ở nhiều cấp độ phân giải khác nhau, chỉ truyền duy nhất phần ảnh nhìn thấy trên màn hình. Khả năng này rất hữu ích cho việc thu nhỏ những ảnh có độ phân giải cao mà không phải giảm kích cỡ toàn bộ ảnh. Công nghệ này từng được Microsoft sử dụng cho phần mềm HD View của hãng.Tuy nhiên, Microsoft cũng phải đối mặt với những thử thách lớn, đó là việc thuyết phục thông qua công nghệ này. Việc tích hợp HD Photo vào Vista là một bước đi lớn, và sự đồng ý của Adobe (tích hợp vào Photoshop) là dấu ấn quan trọng, nhưng định dạng JPEG hiện vẫn rất còn phổ biến, và Microsoft không dễ gì có thể thay đổi thực tế này một sớm một chiều.