Các phương pháp nén ảnh

TRƯỜNG SĨ QUAN THÔNG TINKHOA CÔNG NGHỆ THÔNG TIN CÁC PHƯƠNG PHÁP NÉN ẢNH * GIỚI THIỆU Giới thiệu chung Graphics Interchange format(GIF) Tagged image file format(TIFF) Digitized documents Digitized pictures JPEG * GIỚI THIỆU Hình ảnh có 2 loại : Do máy tính tạo ra (Graphical) Hình ảnh đã được số hóa Hình ảnh được biểu diễn bởi ma trận 2 chiều bao gồm các thành phần được gọi là các Pixel Hình ảnh do chương trình (phần mềm) tạo ra tốn ít bộ nhớ hơn so với hình ảnh tương ứng được biểu diễn bởi ma trận điểm * GIỚI THIỆU Khi truyền các hình ảnh do chương trình tạo ra thì sẽ được biểu diễn theo định dạng của chương trình đó và sử dụng thuật toán nén tương ứng ví dụ : .jpeg  thuật toán nén ảnh jpeg Có nhiều thuật toán nén khác nhau nhưng chủ yếu sử dụng 2 phương án Dựa trên sự kết hợp của mã hóa vi sai và mã hóa thống kê Dựa trên sự biến đổi, phép tính vi phân và mã hóa vi sai và được phát triển để nén các hình ảnh bitonal và ảnh màu * GRAPHICS INTERCHANGE FORMAT(GIF) Định dạng ảnh GIF thì được sử dụng rộng rãi trên Internet cho việc biểu diễn và nén các ảnh Graphical Màu sắc của ảnh bao gồm 24 bit 8 bit Red, 8 bit Green, 8 bit Blue Biểu diễn được 256 màu từ 224 màu * GRAPHICS INTERCHANGE FORMAT(GIF) Dữ liệu nén được chia làm 4 nhóm (Figure 3.10), đầu tiên là 1/8 tổng số dữ liệu được nén, 1/4 và cuối cùng là 1/2 * GRAPHICS INTERCHANGE FORMAT(GIF) Bảng màu liên quan tới toàn bộ ảnh gọi là  Golbal color table Bảng màu được gửi qua mạng cùng với dữ liệu nén và một số thông tin khác  Local color table Nén ảnh thực chất là nén text bằng cách mở rộng bảng màu 1 cách tự động Tuy nhiên trong GIF thay vì mỗi mục trong bảng màu là 24bit để tiết kiệm bộ nhớ chỉ sử dụng 8 bit chỉ số của bảng màu cơ bản 256 màu. * GRAPHICS INTERCHANGE FORMAT(GIF) Nếu chúng ta giới hạn mỗi mục trong bảng là 24bit  biểu diễn 1 chuỗi 3 giá trị điểm ảnh trong bảng mở rộng Thông thường bảng màu chứa 256 mục ban đầu là 512 mục GIF cho phép 1 hình ảnh được lưu trữ và truyền trên mạng trong chế độ xen kẽ Điều này có lợi khi truyền hình ảnh qua 2 kênh có tốc độ thấp GIF sử dụng mã hóa : LZW coding GIF nén không mất mát thông tin * GRAPHICS INTERCHANGE FORMAT(GIF) Giải thuật nén LZW (Jacob Lempel, Abraham Ziv and Terry Welch) Phương pháp nén từ điển dựa trên việc xây dựng từ điển lưu các chuỗi ký tự có tần suất lặp lại cao và thây 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 khác ở cách tổ chức từ điển cho phép nâng cao tỉ lệ nén. Giải thuật LZW được sử dụng cho tất cả các file nhị phân, nó được dùng để nén cho tất cả 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, TIFF. Mức độ hiệu quả của LZW không phụ thuộc vào số bít màu của ảnh * GRAPHICS INTERCHANGE FORMAT(GIF) Giải thuật nén LZW (Jacob Lempel, Abraham Ziv and Terry Welch) Giải thuật nén LZW xây dựng một từ điển lưu các mẫu có tần suất xuất hiện cao trong ảnh. Từ điển tập hợp những từ vựng có 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 ảnh. Sự xuất hiện của một chuỗi con trong từ điển chứng tỏ rằng nó đã từng xuất hiện trong từ điển. 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 từ mã là 12 bits (4096 = 212 ). Cấu trúc từ điển như sau: * GRAPHICS INTERCHANGE FORMAT(GIF) Giải thuật nén LZW (Jacob Lempel, Abraham Ziv and Terry Welch) * GRAPHICS INTERCHANGE FORMAT(GIF) Ví dụ minh họa 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. * GRAPHICS INTERCHANGE FORMAT(GIF) Chuỗi đầu ra sẽ là :65 – 66 – 67 – 259 – 258 – 67 – 262 Đầu vào có kích thướ c :12x8 = 96 bits Đầu ra có kích thướ c là :4x8 + 3x9 = 59 bits Tỉ lệ nén là 96 : 59≅1,63 * GRAPHICS INTERCHANGE FORMAT(GIF) LZW coding * TAGGED IMAGE FILE FORMAT(TIFF) * Sử dụng rộng rãi, sử dụng 48 bít để biểu diễn 16 bits Red, 16 bits Green, 16 bits Blue Dự định để truyền cả hình ảnh và tài liệu đã được số hóa Do đó dữ liệu được lưu trữ và truyền theo 1 số định dạng khác nhau Mỗi định dạng sử dụng code number khác nhau LZW-compression có code number là 5 (nén ảnh) Số hóa tài liệu code number là: 2,3,4 DIGITIZED DOCUMENTS Máy quét anh sau khi thực hiện việc quét hình ảnh thường tiến hành số hóa. Nguyên tắc quét của máy quét là:từ trái qua phải ,từ trên xuống dưới Chỉ sử dụng 1 bít để biểu diễn 1 điểm ảnh + 0  trắng + 1  đen Với độ phân giải xấp xỉ 8 điểm ảnh /mm luồng bits không bị nén Trong hầu hết các trường hợp dữ liệu được truyền qua moden và PSTN tốc độ thấp tốn thời gian * DIGITIZED DOCUMENTS Tổ chức ITU-T đưa ra 4 chuẩn T2(Group 1) hiện nay ít được sử dụng T3(Group 2) T4(Group 3) PSTN T6(Group 4) ISDN Tỷ lệ nén 10:1 Sau khi phân tích tần số xuất hiện của các bits trắng và đen liền kề nhau  đưa ra được 2 bản code word termination-codes table: biểu diễn mã vi sai của màu trắng hoặc màu đen từ 063 điểm ảnh trong các bước của 1 điểm ảnh make-up codes table: biểu diễn mã vi sai của màu trắng hoặc màu đen là bội số của 64 * * DIGITIZED DOCUMENTS Kỹ thuật overscaning được sử dụng nghĩa là tất cả các dòng bắt đầu với ít nhất 1 bit trắng Bên nhận biết rằng codeword đầu tiên luôn luôn liên quan tới màu trắng rồi thì nó sẽ thay thế giữa màu trắng or màu đen sử dụng 2 bảng termination-codes table và make-up codes table gọi là: modified Huffman codes Nếu không có giao thức check lỗi trong PSTN, khi sảy ra lỗi trên đường truyền bên nhận sẽ bắt đầu dịch các codeword trong ranh giới các bit bị lỗi bên nhận sẽ bất đồng bộ không thể giải mã Để cho phép đồng bộ lại kết thúc mỗi dòng chèn thêm mã EOL(end of line) 6 EOL liên tiếp chỉ ra EOP(end of page) * DIGITIZED DOCUMENTS Mỗi dòng quét được mã hóa 1 độc lập  One-dimensinal coding One-dimensinal coding làm việc tốt nếu tài liệu chỉ chứa ký tự và bản vẽ Negative compression ratio: số bít được gửi đi khi nén lớn hơn số bits khi không nén Vì nhưng lý do trên mã hóa T6(Group 4) được định nghĩa. Nó là tùy chọn trong Group 3(máy fax) nhưng lại là bắt buộc trong Group4 Khi hỗ trợ các máy trong Group 3, EOL code thêm vào cuối của mỗi dòng Nếu là bít 1 dòng tiếp theo Group 3 Nếu là bít 0 dòng tiếp theo Group 4 * DIGITIZED DOCUMENTS Ký tự 0 và 1 đó được gọi là modified – modified READ (MMR) coding hoặc two-dimensional coding (2D) Mã hóa MMR liên quan tới mã hóa vi sai với 1 dòng đã được xác định bằng việc so sánh nội dung của 1 dòng gọi là : coding Line(CL) Liên quan tới ngay dòng trước nó thì gọi là: Reference line (RL) * DIGITIZED DOCUMENTS Có 3 chế độ của mã hóa vi sai: Pass mode Vertical mode Horizontal mode * * DIGITIZED PICTURES Hình ảnh bao gồm 2 dạng: Đơn sắc Ảnh màu Dung lượng vào khoảng 37kb đến 2.4Mb  Ảnh hưởng đến ứng dụng tương tác Dùng nén two-deminsional để giảm thời gian truyền Hầu hết các phương pháp nén ảnh đều dựa trên tiêu chuẩn quốc tế * ẢNH JPEG Phương pháp nén ảnh JPEG (Joint Photographic Experts Group ISO/ITU/IEC) là một trong những phương pháp nén ảnh hiệu quả, có tỷ lệ nén ảnh tới vài chục lần. Tuy nhiên ảnh sau khi giải nén sẽ khác với ảnh ban đầu và nó được định nghĩa trong tiêu chuẩn IS 10918 Baseline mode (chế độ cơ bản ): dùng trong việc nén các hình ảnh đơn sắc và số hóa các ảnh màu, sử dụng trong các ứng dụng truyền thông đa phương tiện Các giai đoạn nén ảnh: 5 giai đoạn 1. Image/Block Preparation (chuẩn bị hình ảnh, khối) 2. Forward DCT (Chuyển tiếp DTC) 3. Quantization (Lượng tử hoá) 4. Entropy Encoding ( mã hóa Entropy) 5. Frame Building (xây dựng khung hình) * ẢNH JPEG * ẢNH JPEG Dùng ma trận 2 chiều để biểu diễn hình ảnh Trong trường hợp ảnh đơn sắc chỉ sử dụng 1 ma trận 2 chiều để thiết lập 8 bit giá trị mức xám * ẢNH JPEG Ảnh màu : nếu CLUT(color look-up table là bảng tìm kiếm màu) được sử dụng chỉ là duy nhất và được đại diện bởi R,G,B ta có thể thay bằng: Y ,Cb,Cr * ẢNH JPEG Một khi file hình ảnh gốc được lựa chọn và chuẩn bị tập hợp các giá trị được nén riêng biệt bằng cách sử dụng DCT.Nó thì tốn thời gian vì vậy mỗi ma trận đầu tiên được chia 1 tập các ma trận nhỏ hơn (8x8) gọi là ma trận phụ * ẢNH JPEG 2.Forward DCT DCT: Chuyển đổi ma trận hai chiều của giá trị pixel vào một ma trận tương đương của các thành phần tần số. Thay vì biểu diễn ảnh thành ma trận điểm ảnh, biểu diễn thành ma trận tần số thay đổi của các điểm ảnh sẽ giảm việc biểu diễn, lưu trữ ảnh Mỗi giá trị pixel sử dụng 8 bít . Từ 0 đến 255 cho các giá trị mức xám R,G,B ,Y và -128 đến 127 cho các giá trị mầu Cb , Cr.Đầu vào được biểu diễn bằng ma trận 2 chiều P[x,y] và đầu ra F[i,j] .Nén DCT , mỗi khối 8x8 các giá trị được tính bằng biểu thức * ẢNH JPEG * ẢNH JPEG Trong DCT Tất cả 64 mục giá trị trong ma trận input P [x, y] đóng góp cho mỗi mục trong ma trận chuyển đổi F [i, j]. Đối với i = j = 0, vì cos (0) = 1. giá trị ở vị trí F [0,0] là giá trị trung bình của tất cả 64 giá trị trong ma trận và được biết đến như hệ số DC  Tất cả giá trị khác của ma trận chuyển đổi có tần số hệ số liên quan với chúng-hoặc ngang (x=17, y = 0), theo chiều dọc (x=0, y = 7) hoặc cả hai (x = 17 cho y = l7) gọi là hệ số AC . Đối với j = 0 chỉ có hệ số tần số quét ngang có mặt gia tăng tần số cho i = 17. Đối với i = 0, chỉ có hệ số tần số quét dọc có mặt tăng tần số cho  j= 17. * ẢNH JPEG * ẢNH JPEG 3. Quantization: lượng tử hóa Mắt phản ứng chủ yếu để các DC và các thành phần tần số thấp hơn và thay đổi theo tần số không gian. Do ngưỡng giá trị sử dụng khác nhau cho mỗi tổng số 64 hệ số DCT. Lượng tử hoá là quá trình làm giảm tầm quan trọng của quá trình DC. Lượng tử hoá làm giảm tầm quan trọng của DC và các hệ số AC để giảm băng thông . Các tính toán của các hệ số lượng liên quan đến việc phân chia các hệ số của một yếu tố bình thường và làm tròn hệ số giá trị số nguyên gần nhất.JPEG đạt tiêu chuẩn bao gồm hai bảng lượng tử mặc định hoặc tùy chỉnh .Nói chung, tăng cường độ với tần số không gian ngày càng tăng hệ số DC trong ma trận là lớn nhất của các hệ số tần số cao hơn không(khai thác trong giai đoạn mã hóa dữ liệu Entropy sau đây.) * ẢNH JPEG Chúng ta có thể suy từ những con số quantization error tối đa là cộng hoặc trừ 50% của giá trị ngưỡng được * ẢNH JPEG Tính toán của một tập hợp các lượng tử hóa DCT * ẢNH JPEG 4. Entropy Coding : Giai đoạn mã hóa dữ liệu ngẫu nhiên bao gồm 4 bước sau: Vectoring Differential encoding Run-length encoding Huffman encoding * ẢNH JPEG Các thuật toán mã hóa dữ liệu Entropy hoạt động trên ma trận 1 chiều giá một véc tơ. Tuy nhiên, sản lượng của lượng tử là 2-D.Vì vậy, các giá trị được đại diện trong các hình thức của một đơn kích thước véc tơ. Ngoài ra, tất các hệ số tần số cao trong một trình tự để làm cho hình thức đại diện thích hợp cho nén.Đầu tiên là sự khác biệt giữa mã hóa, mà được áp dụng cho các hệ số DC. * Thứ hai là chạy dài mã hóa, được áp dụng cho các giá trị còn lại trong các vector có các hệ số AC. ẢNH JPEG * ẢNH JPEG Differential encoding : Các giá trị khác biệt đầu tiên luôn luôn được mã hóa tương đối bằng không. Các giá trị khác biệt này sau đó được mã hóa trong các hình thức (SSS, giá trị) . SSS trường cho biết số bit cần thiết để mã hóa các giá trị. Lĩnh vực giá trị các bit thực tế đại diện cho các giá trị. Các quy tắc được sử dụng để mã hóa mỗi giá trị được tóm tắt: * ẢNH JPEG * ẢNH JPEG Như chúng ta có thể thấy: Một giá trị tích cực sau đó được mã hóa bằng cách sử dụng các unsigned nhị phân Số lượng bit cần thiết để mã hóa mỗi giá trị là xác định bởi cường độ của nó. Cũng lưu ý rằng giá trị của số không được mã hóa sử dụng một đơn bit 0 trong các lĩnh vực SSS. * ẢNH JPEG * 3.4.5 JPEG(cont.) Huffman encoding : Nén có thể được thu được bằng cách thay thế chuỗi dàichữ số nhị phân của một chuỗi của codewords ngắn hơn nhiều, (tương đối tần số xuất hiện). Huffman là thuật toán mã hóa. Đối với sự khác biệt giữa hệ số DC mã hóa trong khối,bit trong lĩnh vực SSS không được gửi dưới dạng nhị phân unsigned * ẢNH JPEG * ẢNH JPEG Điều này được thực hiện để các bit trong lĩnh vực SSS * ẢNH JPEG * ẢNH JPEG Giải thích ví dụ 3.8 sau. Các lĩnh vực SSS sau đó được sử dụng để xác định số bit trong giá trị lĩnh vực thời gian dài và sau khi đọc và giải mã đó, lặp đi lặp lại quá trình cho đến khi từ mã EOB nhận được các hệ số còn lại là tất cả các số không. Bởi vì việc sử dụng các codewords chiều dài thay đổi khác nhau các bộ phận của giai đoạn mã hóa dữ liệu ngẫu nhiên. * ẢNH JPEG * ẢNH JPEG 5. Frame Building : Frame Header : Chiều rộng và chiều cao của hình ảnh bằng pixel. Số lượng và loại của các thành phần được sử dụng để đại diện cho hình ảnh (CLUB, RGB, YCbCr). Số hóa dữ liệu định dạng được sử dụng: (4:2:2,4; 2, 0, vv) Scan Header: Danh tính của các thành phần (RGB vv) Số lượng bit được sử dụng để số hóa mỗi thành phần. Bảng lượng tử hóa các giá trị được sử dụng để mã hóa mỗithành phần * ẢNH JPEG * ẢNH JPEG