Tài liệu Tìm hiểu mã loạt dài cho ảnh nhị phân và chương trình ứng dụng

Header Page 1 of 128. LỜI CẢM ƠN Lời đầu tiên em xin chân thành cảm ơn cô giáo, Th.S Nguyễn Minh Hiền đã tận tình hướng dẫn và giúp đỡ cho em trong suốt quá trình xây dựng và hoàn thành các yêu cầu của bài khóa luận. Xin chân thành cảm ơn các Thầy, Cô trong khoa công nghệ thông tin đã giảng dạy, cung cấp những kiến thức quý báu và tạo mọi điều kiện thuận lợi cho em trong suốt quá trình học tập vừa qua. Xuân Hòa, tháng 5 năm 2013 Sinh viên Nguyễn Văn Chính luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 1 of 128. Header Page 2 of 128. LỜI CAM ĐOAN Khóa luận này là kết quả của bản thân em trong quá trình học tập và nghiên cứu. Bên cạnh đó em được sự quan tâm của các thầy, cô giáo trong khoa công nghệ thông tin, đặc biệt là sự quan tâm hướng dẫn tận tình của cô giáo, Th.S Nguyễn Minh Hiền. Trong khi nghiên cứu hoàn thành bài khóa luận này em đã tham khảo một số tài liệu trong phần tài liệu tham khảo. Em xin khẳng định kết quả của đề tài “Tìm hiểu mã loạt dài cho ảnh nhị phân và chương trình ứng dụng”. Không trùng lặp với kết quả của đề tài khác. Hà Nội, tháng 5 năm 2013 Sinh viên Nguyễn Văn Chính luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 2 of 128. Header Page 3 of 128. MỤC LỤC DANH MỤC HÌNH ẢNH MỞ ĐẦU ....................................................................................................... 1 Chương 1: GIỚI THIỆU CHUNG .............................................................. 4 1.1. Giới thiệu về nén dữ liệu ...................................................................... 4 1.2. Ứng dụng của nén dữ liệu ..................................................................... 5 1.3. Nguyên tắc của nén dữ liệu .................................................................. 5 1.4. Tầm quan trọng của nén dữ liệu trong truyền tin nối tiếp...................... 6 Chương 2: MỘT SỐ KỸ THUẬT NÉN TRONG MÃ HÓA DỮ LIỆU .... 8 2.1. Các khái niệm cơ bản ........................................................................... 8 2.1.1. Tỷ lệ nén (Compression Rate) ....................................................... 8 2.1.2. Các loại dư thừa dữ liệu.................................................................. 8 2.2. Phân loại phương pháp nén .................................................................. 9 2.3. Tiêu chuẩn đánh giá chất lượng mã hóa ảnh ....................................... 10 2.4. Mô hình thống kê ............................................................................... 11 2.4.1. Mô hình thống kê tĩnh .................................................................. 11 2.4.2. Mô hình thống kê động................................................................. 12 2.5. Mô hình từ điển .................................................................................. 14 2.5.1. Tổng quát ..................................................................................... 14 2.5.2. Từ điển tĩnh .................................................................................. 14 2.5.3. Từ điển động ................................................................................ 15 2.5.4. LZ77 ............................................................................................ 15 2.5.5. LZ78 ............................................................................................ 20 2.6. Một số mã nén cơ bản......................................................................... 23 2.6.1. Mã nén RLE ( Run Length Encoding) .......................................... 23 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 3 of 128. Header Page 4 of 128. 2.6.2. Mã nén Huffman .......................................................................... 24 2.6.3. Phương pháp LZW ....................................................................... 27 2.6.4. Phương pháp mã hóa khối ............................................................ 34 2.6.5. Phương pháp thích nghi ................................................................ 36 2.7. Phương pháp mã hóa loạt dài RLE cho ảnh nhị phân.......................... 37 2.7.1. Ảnh nhị phân ................................................................................ 37 2.7.2. Mã RLE (Run- Length- Encoding) ............................................... 38 Chương 3: CHƯƠNG TRÌNH DEMO...................................................... 40 3.1. Giới thiệu bài toán .............................................................................. 40 3.2. Chương trình thử nghiệm ................................................................... 41 3.2.1. Thử nghiệm với hình ảnh.............................................................. 42 3.2.2. Thử nghiêm với ảnh có sử dụng nhiều loạt dài ............................. 43 3.2.3. Thử nghiệm với ảnh sử dụng ít loạt dài ........................................ 44 3.2.4. Thử nghiệm với ảnh chứa nhiều điểm đen trắng ........................... 46 3.2.5. Thử nghiệm với ảnh chứa các điểm đen trắng đan xen ................. 48 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ................................................. 50 TÀI LIỆU THAM KHẢO.......................................................................... 52 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 4 of 128. Header Page 5 of 128. DANH MỤC HÌNH ẢNH Hình 2.1. Mã hóa theo mô hình thống kê động ............................................. 12 Hình 2.2. Giải mã theo mô hình thống kê động ............................................ 13 Hình 2.3. Sơ đồ thuật toán nén LZW ............................................................ 31 Hình 3.1. Ảnh gốc (kích thước157 KB) ........................................................ 42 Hình 3.2. Ảnh sau nén (kích thước14.3 KB)................................................. 42 Hình 3.3. Ảnh gốc (kích thước 145 KB) ....................................................... 43 Hình 3.4. Ảnh sau nén (kích thước 24.1 KB)................................................ 43 Hình 3.5. Ảnh gốc (kích thước 145 KB) ....................................................... 44 Hình 3.6. Ảnh sau nén (kích thước 47.0 KB)................................................ 44 Hình 3.7. Ảnh gốc (kích thước 145KB) ........................................................ 46 Hình 3.8. Ảnh sau nén (kích thước 8.49KB)................................................. 47 Hình 3.9. Ảnh gốc (kích thước 145KB) ........................................................ 48 Hình 3.10. Ảnh sau nén (kích thước 14.8KB) ............................................... 49 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 5 of 128. Header Page 6 of 128. MỞ ĐẦU 1. Lý do chọn đề tài Nén dữ liệu là một môn kiến thức chuyên ngành rất cần thiết cho mỗi người học và làm về công nghệ thông tin. Trong môn học này chúng ta được tìm hiểu, nghiên cứu các phương pháp nén ảnh, video, âm thanh,… cùng với những ứng dụng không nhỏ của chúng trong thực tế. Ứng dụng của nén dữ liệu là vô cùng to lớn do nhu cầu trao đổi dữ liệu giữa mọi người ngày một tăng, dữ liệu mà chúng ta muốn chia sẻ, trao đổi ngày một lớn hơn, phức tạp hơn và đa dạng hơn. Để giải quyết vấn đề này bài toán nén dữ liệu đã ra đời, mục đích của nó là làm giảm kích thước của dữ liệu gốc nhằm giúp cho việc xử lý dữ liệu nhanh hơn (sao chép, di chuyển, tải lên, tải xuống,…). Đề tài “Tìm hiểu mã loạt dài cho ảnh nhị phân và chương trình ứng dụng” đưa ra một phương pháp nén dữ liệu đơn giản nhưng rất hiệu quả, ứng dụng trong việc nén biểu tượng, ảnh đen trắng, mã vạch, fax… vì ở đó chứa nhiều loạt dài. Dưới góc độ góc độ một sinh viên chuyên nghành công nghệ thông tin và trong khuôn khổ bài khóa luận tốt nghiệp đồng thời dưới sự hướng dẫn tận tình của cô giáo, Th.S Nguyễn Minh Hiền em đã chọn đề tài “Tìm hiểu mã loạt dài cho ảnh nhị phân và chương trình ứng dụng” 2. Mục đích nghiên cứu Tìm hiểu mã loạt dài đưa ra một phương pháp nén dữ liệu đơn giản nhưng rất hiệu quả, ứng dụng trong việc nén biểu tượng, ảnh đen trắng, mã vạch, fax… vì ở đó chứa nhiều loạt dài. 3. Nhiệm vụ nghiên cứu Nhiệm vụ cơ bản của khóa luận là tìm hiểu các phương pháp, các thuật toán nén ảnh và nắm vững thuật toán nén ảnh về mã loạt dài. Đọc và tìm hiểu 1 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 6 of 128. Header Page 7 of 128. về ngôn ngữ lập trình C. Từ đó, xây dựng một chương trình thử nghiệm để nén ảnh sử dụng phương pháp mã loạt dài. 4. Phương pháp, phạm vi nghiên cứu + Phương pháp nghiên cứu lý luận Nghiên cứu qua việc đọc sách báo và các tài liệu liên quan nhằm xây dựng cơ sở lý thuyết của đề tài và các biện pháp cần thiết để giải quyết các vấn đề của đề tài. + Phương pháp chuyên gia Tham khảo ý kiến của các chuyên gia để có thể thiết kế chương trình phù hợp với yêu cầu thực tiễn. Nội dung xử lý nhanh đáp ứng nhu cầu của người sử dụng. + Phương pháp thực nghiệm Thông qua quan sát thực tế, yêu cầu của cơ sở, những lý luận được nghiên cứu và kết quả đạt được qua những phương pháp trên. Bài khóa luận tập chung nghiên cứu về các thuật toán nén dữ liệu đặc biệt là thuật toán Run length encoding, cùng với đó em cũng tìm hiểu về ngôn ngữ lập trình C để xây dựng chương trình ứng dụng. 5. Ý nghĩa khoa học và thực tiễn của đề tài Đề tài “Tìm hiểu mã loạt dài cho ảnh nhị phân và chương trình ứng dụng” được nghiên cứu để tạo ra chương trình nén hiệu quả với các dữ liệu chứa nhiều loạt dài và tạo cơ sở để phát triển các chương trình nén dữ liệu khác. 6. Cấu trúc khóa luận Ngoài mục lục, danh mục hình ảnh, phần mở đầu, kết luận và tài liệu tham khảo, khóa luận gồm 3 chương: Chương 1: GIỚI THIỆU CHUNG Giới thiệu về nén dữ liệu, các ứng dụng và nguyên tắc của nén dữ liệu, tầm quan trọng của nén dữ liệu trong truyền tin nối tiếp 2 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 7 of 128. Header Page 8 of 128. Chương 2: MỘT SỐ KỸ THUẬT NÉN TRONG MÃ HÓA DỮ LIỆU Đưa ra các khái niệm cơ bản như tỷ lệ nén, các loại dư thừa dữ liệu… Tiêu chuẩn đánh giá chất lượng mã hóa ảnh và các thuật toán cho một số phương pháp nén cơ bản như Run length encoding, Hufman, LZW… Và từ đó đi sâu vào nghiên cứu mã loạt dài Run length en coding để hiểu rõ tính hiệu quả của phương pháp nén mã loạt dài này. Chương 3: CHƯƠNG TRÌNH DEMO Giới thiệu về bài toán và đưa ra chương trình ứng dụng. 3 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 8 of 128. Header Page 9 of 128. Chương 1: GIỚI THIỆU CHUNG Nén dữ liệu là một đề tài nghiên cứu rất phổ biến trong lĩnh vực xử lý dữ liệu đa phương tiện. Mục đích là làm thế nào để lưu trữ dữ liệu dưới dạng có kích thước nhỏ hơn hay dưới dạng biểu diễn mà chỉ yêu cầu số bít mã hoá ít hơn so với dữ liệu gốc. Nén dữ liệu thực hiện được là do một thực tế, thông tin trong dữ liệu không phải là ngẫu nhiên mà có trật tự, có tổ chức. Vì thế nếu bóc tách được tính trật tự, cấu trúc đó thì sẽ biết được phần thông tin nào quan trọng nhất trong dữ liệu để biểu diễn và truyền đi với số lượng bít ít hơn so với ảnh gốc mà vẫn đảm bảo tính đầy đủ thông tin. Ở phía thu, quá trình giải mã sẽ tổ chức, sắp xếp lại được dữ liệu xấp xỉ gần chính xác so với dữ liệu gốc nhưng vẫn thoả mãn chất lượng yêu cầu, đảm bảo đủ thông tin cần thiết. Tóm lại, các dữ liệu như tín hiệu ảnh, video hay audio… đều có thể nén lại bởi chúng có những tính chất như sau: + Có sự tương quan (dư thừa) thông tin về không gian: Trong phạm vi một bức ảnh hay một khung video tồn tại sự tương quan đáng kể (dư thừa) giữa các điểm ảnh lân cận. + Có sự tương quan (dư thừa) thông tin về phổ: Các dữ liệu thu được từ các bộ cảm biến của thiết bị thu nhận ảnh tồn tại sự tương quan đáng kể giữa các mẫu thu, đây chính là sự tương quan về phổ. + Có sự tương quan (dư thừa) thông tin về thời gian: Trong một chuỗi ảnh video, tồn tại sự tương quan giữa các điểm ảnh của các khung video (frame). 1.1. Giới thiệu về nén dữ liệu Nén dữ liệu (Data Compression) 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à do vậy, lượng thông tin thu được sau khi nén thường nhỏ hơn dữ liệu gốc rất nhiều, với dữ liệu ảnh, kết quả thường là 10:1. Một số phương pháp 4 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 9 of 128. Header Page 10 of 128. còn cho kết quả cao hơn. Theo kết quả nghiên cứu được công bố gần đây tại Viện Kỹ thuật Georfie, kỹ thuật nén fractal cho tỉ số nén là 30 trên 1 [6]. Ngoài thuật ngữ “nén dữ liệu”, do bản chất của kỹ thuật này nó còn có một số tên gọi khác như: Giảm độ dư thừa, mã hóa ảnh gốc. Từ hơn hai thập kỷ nay, có rất nhiều kỹ thuật nén đã được công bố trên các tài liệu về nén và các phần mềm nén dữ liệu đã xuất hiện ngày càng nhiều trên thương trường. Tuy nhiên, chưa có phương pháp nén nào được coi là phương pháp vạn năng (Universal) vì nó phụ thuộc vào nhiều yếu tố và bản chất của dữ liệu gốc. Trong chương này, chúng ta không thể hy vọng xem xét tất cả các phương pháp nén. Hơn thế nữa, các kỹ thuật nén dữ liệu chung đã được trình bày trong nhiều tài liệu chuyên ngành. Ở đây, chúng ta chỉ đề cập các phương pháp nén có đặc thù riêng cho dữ liệu ảnh. 1.2. Ứng dụng của nén dữ liệu Ứng dụng của nén dữ liệu là vô cùng to lớn do nhu cầu trao đổi dữ liệu giữa mọi người ngày một tăng, dữ liệu mà chúng ta muốn chia sẻ, trao đổi ngày một lớn hơn, phức tạp hơn và đa dạng hơn. Để giải quyết vấn đề này bài toán nén dữ liệu đã ra đời, mục đích của nó là làm giảm kích thước của dữ liệu gốc nhằm giúp cho việc xử lý dữ liệu nhanh hơn (sao chép, di chuyển, tải lên, tải xuống,…). Ưu điểm nổi bật của nén dữ liệu đã được ứng dụng và phát triển trong nhiều lĩnh vực truyền thông đa phương tiện và nhiều lĩnh vực nghiên cứu khác. Thời gian gần đây, một số lĩnh vực đang phát triển rất nhanh và thu hút sự quan tâm của nhiều người đó là truyền thong nối tiếp, đồ họa, ý tế từ xa… Mà ở đó nén đóng vai trò rất quan trọng. 1.3. Nguyên tắc của nén dữ liệu Thông thường, hầu hết các tập tin trong máy tính có rất nhiều thông tin dư thừa, việc thực hiện nén tập tin thực chất là mã hoá lại các tập tin để loại bỏ các thông tin dư thừa. 5 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 10 of 128. Header Page 11 of 128. Nhìn chung không thể có phương phát nén tổng quát nào cho kết quả tốt đối với tất cả các loại tập tin vì nếu không ta sẽ áp dụng n lần phương pháp nén này để đạt được một tập tin nhỏ tuỳ ý, Kỹ thuật nén tập tin thường được áp dụng cho các tập tin văn bản (trong đó có một số kí tự nào đó có xác suất xuất hiện nhiều hơn các kí tự khác), các tập tin ảnh bitmap (mà có thể có những mảng lớn đồng nhất), các tập tin dùng để biểu diễn âm thanh dưới dạng số hoá và các tín hiệu tương tự (analog signal) khác (các tín hiệu này có thể có các mẫu được lặp lại nhiều lần). Đối với các tập tin nhị phân như tập tin chương trình thì sau khi nén cũng không tiết kiệm được nhiều. Ngoài ra, trong một số trường hợp để nâng cao hệ số nén người ta có thể bỏ bớt một số thông tin của tập tin (Ví dụ như kỹ thật nén ảnh JPEG). 1.4. Tầm quan trọng của nén dữ liệu trong truyền tin nối tiếp Trong kỹ thuật truyền tin nối tiếp, do các bit dữ liệu được truyền đi nối tiếp, lại bị giới hạn về dãi thông của kênh truyền và giới hạn về các chuẩn ghép nối... Nên tốc độ truyền tin tương đối chậm. Để tăng tốc độ truyền ta có thể dùng nhiều phương pháp như sử dụng kỹ thuật điều chế pha nhiều mức, điều chế QAM, TCM... Nén dữ liệu trước khi truyền đi cũng là một trong các phương pháp nhằm tăng tốc độ truyền dữ liệu. Trong các modem hiện đại, việc thực hiện nén dữ liệu trước khi truyền đi có thể được thực hiện ngay trong modem theo các giao thức V42bis, MNP5. Phương pháp này đòi hỏi hai modem phải có cùng một giao thức nén dữ liệu, điều này nhiều khi khó thoã mãn. Có một phương pháp khác là thực hiện nén các tập tin ngay tại các máy vi tính trước khi truyền đi, tại các máy tính nhận, các tập tin lại được giải nén để phục hồi lại dạng ban đầu. Phương pháp này có ưu điểm là bên phát và bên thu chỉ cần có chung phần mềm nén và giải nén, ngoài ra còn có thể áp dụng được để truyền dữ liệu qua các modem không hỗ trợ nén dữ liệu hoặc truyền dữ liệu trực tiếp qua cổng COM của máy tính. Nhược điểm của phương pháp 6 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 11 of 128. Header Page 12 of 128. này là các máy vi tính phải tốn thêm thời gian nén và giải nén, nhưng do sự phát triển nhanh chóng của các bộ vi xử lý mà thời gian thực hiện nén và giải nén được giảm nhỏ hơn rất nhiều thời gian để truyền dữ liệu. Ví dụ, khi truyền một tập tin có kích thước là 100Kbyte với dạng thức của một SDU là: 8 bits dữ liệu, 2 bit STOP và 1 bit START, không dùng bit chẵn lẻ, tốc độ truyền là 9600bits/giây thì mất khoảng 120 giây, trong khi một máy vi tính với bộ vi xử lí 80386 có thể thực hiện nén tập tin trên xuống còn 50Kbyte chỉ mất chưa đến 10 giây. 7 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 12 of 128. Header Page 13 of 128. Chương 2: MỘT SỐ KỸ THUẬT NÉN TRONG MÃ HÓA DỮ LIỆU 2.1. Các khái niệm cơ bản 2.1.1. Tỷ lệ nén (Compression Rate) 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. Tuy nhiên, về cách đánh giá và các kết quả công bố trong các tài liệu cũng cần quan tâm xem xét. Nhìn chung, người ta định nghĩa tỷ lệ cơ bản của phương pháp nén. Nhiều khi tỷ lệ nén cao cũng chưa thể nói phương pháp đó hiệu quả hơn các phương pháp khác, vì còn các chi phí như thời gian, không gian và thậm chí cả độ phức tạp tính toán nữa. Thí dụ như nén phục vụ trong truyền dữ liệu. Vấn đề đặt ra là hiệu quả nén có tương hợp với đường truyền không. Cũng cần phân biệt dữ liệu với nén băng truyền. Mục đích chính của nén là giảm lượng thông tin dư thừa và dẫn tới giảm kích thước dữ liệu. Tuy vậy, đôi khi quá trình nén cũng làm giảm băng truyền tín hiệu số hóa thấp hơn so với truyền tín hiệu tương tự. 2.1.2. Các loại dư thừa dữ liệu Như trên đã nói, nén nhằm mục đích giảm kích thước dữ liệu bằng cách loại bỏ dư thừa dữ liệu. Việc xác định bản chất các kiểu dư thừa dữ liệu rất có ích cho việc xây dựng các phương pháp nén dữ liệu khác nhau. Nói một cách khác, các phương pháp nén dữ liệu khác nhau là do sử dụng các kiểu dư thừa khác nhau. Có 4 kiểu dư thừa chính : + Sự phân bố ký tự Trong một dãy ký tự, có một số ký tự có tần suất xuất hiện nhiều hơn so với các dãy khác. Do vậy, ta có thể mã hóa dữ liệu một cách cô đọng hơn. Các dãy ký tự có tần suất cao được thay bởi một từ mã nhị phân với số bít nhỏ, ngược lại các dãy có tần suất xuất hiện thấp sẽ được mã hóa bởi từ mã có nhiều bít hơn. Đây chính là bản chất của phương pháp mã hóa từ hóa 8 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 13 of 128. Header Page 14 of 128. Huffman. + Sự lặp lại của các ký tự Kỹ thuật nén dùng trong trường hợp này là thay dãy lặp đó bởi dãy mới gồm hai thành phần: Số lần lặp và kí hiệu dùng để mã. Phương pháp mã hóa kiểu này có tên là mã hóa loạt dài RLE (Run Length Encoding). + Những mẫu sử dụng tần suất Có thể có dãy ký hiệu nào đó xuất hiện với tần suất tương đối cao. Do vây, có thể mã hóa bởi ít bít hơn. Đây là cơ sở của phương pháp mã hóa kiểu từ điển do Lempel-Ziv đưa ra và có cải tiến vào năm 1977, 1978 và do đó có tên gọi là phương pháp nén LZ77, LZ78. Năm 1984, Tery Welch đã cải tiến hiệu quả hơn và đặt tên là LZW (Lempel-Ziv-Welch). + Độ dư thừa vị trí Do sự phụ thuộc lẫn nhau của dữ liệu, đôi khi biết được ký hiệu (giá trị) xuất hiện tại một vị trí, đồng thời có thể đoán trước sự xuất hiện của các giá trị ở các vị trí khác nhau một cách phù hợp. Chằng hạn, ảnh biểu diễn trong một lưới hai chiều, một số điểm ở hàng dọc trong một khối dữ liệu lại xuất hiện trong cùng vị trí ở các hàng khác nhau. Do vậy, thay vì lưu trữ dữ liệu, ta chỉ cần lưu trữ vị trí hàng và cột. Phương pháp nén dựa trên sự dư thừa này gọi là phương pháp mã hóa dự đoán. 2.2. Phân loại phương pháp nén Có nhiều cách phân loại các phương pháp nén khác nhau. + Cách thứ nhất dựa vào nguyên lý nén. Cách này phân các phương pháp nén thành hai họ lớn: - Nén chính xác hay nén không mất thông tin: Họ này bao gồm các phương pháp nén mà sau khi giải nén ta thu được chính xác dữ liệu gốc. - Nén có mất thông tin: Họ này bao gồm các phương pháp mà sau khi giải nén ta không thu được dữ liệu như bản gốc. Phương pháp này lợi dụng tính chất của mắt người, chấp nhận một số vặn xoắn trong ảnh khi khôi phục 9 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 14 of 128. Header Page 15 of 128. lại. Tất nhiên, các phương pháp này chỉ có hiệu quả khi mà độ vặn xoắn chấp nhận được bằng mắt thường hay với dung sai nào đấy. + Cách phân loại thứ hai dựa vào cách thức thực hiện nén. Theo cách này, người ta cũng phân thành hai họ: - Phương pháp không gian (Spatial Data Compression): Các phương pháp thuộc họ này thực hiện nén bằng các tác động trực tiếp lên việc lấy mẫu của ảnh trong miền không gian. - Phương pháp sử dụng biến đổi (Transform Coding): Gồm các phương pháp tác động lên sự biến đổi của ảnh gốc mà không tác động trực tiếp như họ trên. + Cách phân loại thứ ba dựa vào triết lý của sự mã hóa. Cách này cũng phân các phương pháp nén thành hai họ: - 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ã,... - 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. Trong bài viết này sẽ theo cách phân loại thứ ba. Các phương pháp nén thế hệ thứ nhất gồm: - Mã hóa loạt dài RLE (Run Length Encoding) - Mã hóa Huffman - Mã hóa LZW (Lempel Ziv-Wench) - Mã hóa khối (Block Encoding) 2.3. Tiêu chuẩn đánh giá chất lượng mã hóa ảnh Để đánh giá chất lượng của bức ảnh (hay khung ảnh video) ở đầu ra của bộ mã hoá, người ta thường sử dụng hai tham số: Sai số bình phương trung bình MSE (mean square error) và tỉ số tín hiệu trên nhiễu đỉnh PSNR (peak to signal to noise ratio). MSE thường được gọi là phương sai lượng tử  q2 (quantization error variance). MSE giữa ảnh gốc và ảnh khôi phục được tính như sau [1]: 10 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 15 of 128. Header Page 16 of 128. MSE   q2  1 N  ( f [ j, k ]  g[ j, k ]) 2 ik 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. Còn PSNR giữa hai ảnh (b bít cho mỗi điểm ảnh, RMSE là căn bậc 2 của MSE) đước tính theo công thức dB như sau: PSNR  20 log10 RMSE 2b  1 Thông thường, nếu PSNR ≥ 40dB thì hệ thống mắt người gần như không phân biệt được giữa ảnh gốc và ảnh khôi phục. Một tham số khác hay sử dụng trong các hệ thông viễn thông đó là tỉ số tín hiệu trên nhiễu - SNR , tuy vậy SNR sử dụng cho một hệ thống nén ảnh cũng có công thức dB như sau: SNR  10 log10 Encoder input energy Noise energy 2.4. Mô hình thống kê 2.4.1. Mô hình thống kê tĩnh Dạng đơn giản nhất của mô hình thống kê tĩnh là một bảng tĩnh liệt kê các giá trị xác suất theo cách tính thông thường. Trước đây, do việc phân tích và xây dựng mã Huffman rất tốn thời gian, nên người ta chỉ phân tích một lần đối với các dữ liệu điển hình để có được một bảng đếm số lần xuất hiện của từng ký hiệu. Dựa vào kết quả đó, một cây mã Huffman tĩnh được xây dựng và lưu trữ để có thể sử dụng nhiều lần. Mô hình như vậy được gọi là mô hình thống kê tĩnh (Static Statiscal Model). Việc sử dụng một mô hình tĩnh vạn năng cho nhiều kiểu dữ liệu rõ ràng có nhiều hạn chế. Nếu dữ liệu vào không thích hợp với mô hình thì hiệu quả nén sẽ giảm, thậm chí sẽ có kích thước lớn hơn dữ liệu vào ( gọi là nở đầu vào). Do đó một cải tiến tiếp theo là xây dựng mô hình tĩnh cho nhiều kiểu dữ liệu. 11 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 16 of 128. Header Page 17 of 128. Việc xây dựng mô hình tĩnh riêng sẽ có thuận lợi là mang lại hiệu suất nén cao. Nhưng nhược điểm là lại cần lưu trữ thêm một lượng dữ liệu nhất định (cấu trúc của cây mã) trước khi lưu trữ bản mã. Nếu cấu trúc của cây mã vào không lớn lắm vào khoảng 256B so với lượng số lượng dữ liệu cần nén vài trăm KB thì mô hình tĩnh riêng là hiệu quả. Nhưng nếu cấu trúc của cây mã tăng lên mức không thể chấp nhận được so với mục tiêu nén dữ liệu (cỡ khoảng 64KB) thì mô hình tĩnh riêng không phù hợp. 2.4.2. Mô hình thống kê động Để khắc phục những nhược điểm của mô hình thống kê tĩnh, mô hình thống kê động ra đời với số liệu thống kê đối với dữ liệu cần mã hoá không phải lưu trữ trước mà liên tục được tích luỹ và sửa đổi trong suốt quá trình mã hoá và giải mã. Các Các ký hiệu Đọc ký hiệu Mã hóa ký Xuất từ mã kiệu Cập nhật Mô hình mô hình Hình 2.1. Mã hóa theo mô hình thống kê động 12 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 17 of 128. từ mã Header Page 18 of 128. Các Các ký từ mã Đọc từ Giải từ mã mã Xuất ký hiệu hiệu Cập nhật mô Mô hình hình Hình 2.2. Giải mã theo mô hình thống kê động Điểm đáng chú ý trong hai sơ đồ trên là khối cập nhật mô hình. Khối này phải hoạt động chính xác như nhau cả khi mã hoá và khi giải mã. Sau khi một ký hiệu hoặc một nhóm ký hiệu nhập vào, nó sẽ được mã hoá dựa trên mô hình hiện thời, sau đó mô hình mới được cập nhật dựa trên ký hiệu hoặc nhóm ký hiệu đó. Tương tự như vậy, sau khi một từ mã được đọc vào nó sẽ được giải mã theo mô hình hiện thời rồi sau đó mô hình mới được cập nhật theo ký hiệu đã được giải mã. Với mô hình thống kê động, ban đầu nó chưa biết gì về dữ liệu cần được mã hoá cho nên hiệu ứng nén chưa thể xuất hiện ngay. Hiệu ứng nén chỉ xuất hiện rõ rệt khi làm việc với cỡ vài nghìn ký hiệu. ưu điểm của mô hình động ở chỗ nó có khả năng thích ứng với nhiều kiểu dữ liệu khác nhau. 13 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 18 of 128. Header Page 19 of 128. 2.5. Mô hình từ điển 2.5.1. Tổng quát Kỹ thuật từ điển là kỹ thuật sử dụng phương pháp phân đoạn văn bản thành các đoạn nhỏ hơn sao cho nó đạt được độ dài nhất có thể được mà nó đã xuất hiện ở trong quá khứ. Định nghĩa (phân đoạn văn bản). Phân đoạn văn bản A là chia nó ra thành các đoạn nhỏ hơn. Mỗi đoạn được gọi là một phân đoạn. Giả sử chúng ta có từ điển D thì tồn tại một ánh xạ f: D -> W trong đó W là tập các đoạn bit 0/1. Việc nén sẽ tối ưu khi chúng ta phân được đoạn văn bản có độ dài lớn nhất mà sao cho khi đi tìm trong quá khứ thì chúng ta được đoạn 0/1 trong W là nhỏ nhất. Trong kỹ thuật từ điển, tương tự như kỹ thuật thống kê, ta cũng có hai phương án sau: + Mã tĩnh (từ điển tĩnh) + Mã động (từ điển động) 2.5.2. Từ điển tĩnh Mã có từ điển cố định được gọi là mã tĩnh hay nói cách khác là từ điển tĩnh. Nhược điểm của từ điển tĩnh: + Kích thước của từ điển tĩnh không thể mở rộng ra, để cập nhật các thông tin mới so với các loại dữ liệu khác. + Quá trình nghiên cứu thiết kế từ điển đòi hỏi nhiều công sức. + Các thuật toán sử dụng từ điển tĩnh chạy tương đối chậm. + Tốn không gian lưu trữ dữ liệu. Tuy nhiên bên cạnh những nhược điểm này thì từ điển tĩnh cũng có ưu điểm là: Thiết kế các thuật toán áp dụng cho việc tìm kiếm trên từ điển tĩnh đơn giản tốn ít thời gian. 14 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 19 of 128. Header Page 20 of 128. Do những đặc tính hạn chế của từ điển tĩnh, kết hợp với những đặc điểm nổi bật của thuật toán nén là "sự cứng nhắc" đã làm cho người dùng chương trình để tiết kiệm bộ nhớ nhàm chán không thích sử dụng các chương trình nén nữa. Vậy phải có cách để khắc phục những hạn chế đó và làm cho chương trình nén dữ liệu trở nên mềm dẻo hơn. Chính vì vậy những thuật toán nén chỉ đạt hiệu quả cao nếu chúng ta xử lý tốt "từ điển" được sử dụng trong các thuật toán nói chung. 2.5.3. Từ điển động Để khắc phục những hạn chế của từ điển tĩnh, biện pháp được xét đến là: Chúng ta không thiết kế một từ điển sẵn mà " từ điển" đó được xây dựng trong quá trình chạy chương trình. Một từ điển như vậy người ta gọi là từ điển động. Đặc điểm chính của từ điển động: + Kích thước của từ điển có thể thay đổi tuỳ theo kích thước của tập tin. + Không tốn thời gian lưu trữ từ điển. + Thời gian thực hiên quá trình nén nhanh. + Từ điển không phụ thuộc vào kiểu dữ liệu. + Thời gian thực hiện quá trình giải nén chậm. 2.5.4. LZ77 Ý tưởng là: Sử dụng phần đã xét trước đó như là một từ điển. Mã hóa duy trì một cửa số gắn với luồng vào và dịch đầu vào trong cửa sổ từ phải sang trái theo đúng cách các chuỗi ký tự được mã hóa. Phương thức này dựa trên một cửa sổ trượt. Cửa sổ dưới được chia làm hai phần: - Phần bên trái gọi là bộ đệm tìm kiếm - search buffer. Đây là từ điển hiện hành và nó bao gồm các ký hiệu mới được duyệt ở đầu vào và được mã hóa. 15 luan van thac si - luan van kinh te - khoa luan - tai lieu -Footer Page 20 of 128.