Giáo trình Nhập môn đa phương tiện (Phần 1)
Dữ liệu Multimedia
Thông thường chúng ta thường ghi nhận thông tin ở dạng văn bản, các văn bản này
được mã hoá và lưu giữ trên máy tình, khi đó chúng ta có dữ liệu dạng văn bản. Một câu
hỏi đặt ra nếu thông tin chúng ta thu nhận được ở một dạng khác như âm thanh (voice) ,
hính ảnh (Image) thí dữ liệu của nó ở dạng nào? Chình điều này dẫn đến một khái niệm
mới ta gọi đó là dữ liệu Multimedia.
Dữ liệu Multimedia là dữ liệu ở các dạng thông tin khác nhau.
Vì dụ dữ liệu Multimedia là các dữ liệu ở các dạng thông tin như
- Âm thanh (Sound)
- Hính ảnh (image)
-Văn bản (text).
- Kết hợp của cả ba dạng trên.
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Nhập môn đa phương tiện (Phần 1)", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
Tóm tắt nội dung tài liệu: Giáo trình Nhập môn đa phương tiện (Phần 1)
Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 1 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG BỘ MÔN TRUYỀN THÔNG ĐA PHƢƠNG TIỆN BÀI GIẢNG NHẬP MÔN ĐA PHƢƠNG TIỆN Thông tin môn học Số tín chỉ : 2 Số tiết lý thuyết : 24 Số tiết thực hành : 0 Số tiết thảo luận : 12 Hệ đào tạo : Đại học Ngành đào tạo : Truyền thông đa phương tiện Công nghệ truyền thông Thái Nguyên, 2015 Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 2 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông MỤC LỤC Chƣơng 1: Tổng quan về đa phƣơng tiện ....................................................................... 5 1.1 Giới thiệu chung ......................................................................................................... 5 1.2 Một số khái niệm cơ bản ............................................................................................ 7 1.2.1. Thế nào là phương tiện ....................................................................................... 7 1.2.2. Thế nào là đa phương tiện .................................................................................. 7 1.2.3. Thế nào là truyền thông đa phương tiện ............................................................. 8 1.3 Hoàn cảnh sử dụng Multimedia ................................................................................ 10 1.3.1. Ứng dụng của đa phương tiện ........................................................................... 10 1.3.2. Tính hiển thị ...................................................................................................... 11 1.4 Các chuẩn Multimedia thông dụng ........................................................................... 12 1.4.1. Định nghĩa về chuẩn ........................................................................................ 12 1.4.2. Vai trò của chuẩn ............................................................................................. 13 1.4.3. Giới thiệu một số chuẩn ................................................................................... 14 1.5 Các vấn đề bản quyền đối với các tác phẩm đa phương tiện ................................... 18 1.5.1. Bản quyền ......................................................................................................... 18 1.5.2. Vi phạm bản quyền ........................................................................................... 19 1.5.3. Kết luận ............................................................................................................. 19 1.6.Tổng quan về quá trính phát triển Multimedia ........................................................ 20 1.7 Quá trính phát triển một sản phẩm Multimedia ....................................................... 21 1.8 Các yêu cầu của hệ thống đa phương tiện ................................................................ 30 1.8.1. Các vấn đề về QoS ............................................................................................ 30 1.8.2. Các phần tử quan trọng và nhiệm vụ của quản trị QoS .................................... 31 1.8.3. Thiết bị lưu trữ và quản lý dữ liệu multimedia ................................................. 32 Chƣơng 2: Ứng dụng của đa phƣơng tiện ..................................................................... 34 2.1 Giáo dục và đào tạo .................................................................................................. 34 2.2 Thông tin và bán hàng .............................................................................................. 49 2.3 Y học ........................................................................................................................ 49 Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 3 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông 2.4 Hội thảo trực tuyến ................................................................................................... 50 2.5 Giải trí ...................................................................................................................... 50 2.6 Các ứng dụng khác ................................................................................................... 51 Chƣơng 3: Dữ liệu văn bản ............................................................................................. 54 3.1 Văn bản – các định nghĩa cơ bản ............................................................................. 54 3.2 Kỹ thuật nén văn bản................................................................................................ 54 3.2.1. Nén Huffman .................................................................................................... 55 3.2.2. Nén RLE ........................................................................................................... 59 3.2.3. Nén LZW .......................................................................................................... 61 Chƣơng 4: Dữ liệu ảnh .................................................................................................... 66 4.1. Một số khái niệm cơ bản ......................................................................................... 66 4.2 Lĩnh vực ứng dụng kỹ thuật xử lý ảnh ..................................................................... 67 4.3. Các giai đoạn chình trong xử lý ảnh ....................................................................... 69 4.4. Các phần tử cơ bản của hệ thống xử lý ảnh số ........................................................ 70 4.5 Hệ màu ..................................................................................................................... 74 4.5.1. Màu sắc ............................................................................................................. 74 4.5.2. Mô hình màu RGB ............................................................................................ 74 4.5.3. Mô hình màu CMYK ........................................................................................ 75 4.5.4. Mô hình màu HSV ............................................................................................ 76 4.6 Thu nhận và các thiết bị thu nhận ảnh ..................................................................... 77 4.7 Biểu diễn ảnh ............................................................................................................ 77 4.7.1. Mô hình Raster ................................................................................................. 77 4.7.2. Mô hình Vector ................................................................................................. 78 4.8 Nén ảnh .................................................................................................................... 79 4.8.1. Nén JPEG .......................................................................................................... 79 4.8.2. Nén Fractal ........................................................................................................ 82 Chƣơng 5: Dữ liệu âm thanh .......................................................................................... 84 5.1. Một số khái niệm cơ bản ......................................................................................... 84 5.2. Ứng dụng của âm thanh .......................................................................................... 84 Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 4 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông 5.3. Kỹ thuật Audio số ................................................................................................... 85 5.4 Giới thiệu về âm thanh và hệ thống xử lý âm thanh ................................................ 86 5.4.1. Âm thanh(Sound) .............................................................................................. 86 5.4.2. Đặc tình của âm thanh tương tự ....................................................................... 88 5.4.3. Khái niệm tìn hiệu ............................................................................................ 89 5.4.4. Phân loại tìn hiệu .............................................................................................. 90 5.4.5 Phân loại hệ thống xử lý .................................................................................... 92 5.5. Nén âm thanh .......................................................................................................... 92 5.5.1. Các phương pháp nén âm thanh đơn giản ........................................................ 92 5.5.2. Nén âm thanh dùng mô hình âm – tâm lý ......................................................... 93 5.5.3. Neùn aâm thanh MPEG .................................................................................... 94 Chƣơng 6: Dữ liệu video ................................................................................................. 96 6.1. Một số khái niệm cơ bản ......................................................................................... 96 6.2. Nén video ................................................................................................................ 96 6.3.1. Độ dư thừa trong tìn hiệu video ........................................................................ 97 6.3.2. Nhu cầu cần thiết nén video .............................................................................. 99 6.3.3. Khái niệm về nén video .................................................................................... 99 6.3.4. Một số kỹ thuật nén video .............................................................................. 100 Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 5 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông Chƣơng 1: Tổng quan về đa phƣơng tiện 1.1 Giới thiệu chung Sản phẩm của công nghệ Multimedia đã và đang xâm nhập ngày càng sâu, rộng vào mọi lĩnh vực của đời sống xã hội. Có thể nói các sản phẩm của công nghệ có mặt ở khắp mọi nơi, từ công sở đến gia đính. Nó xuất hiện trong nhiều lĩnh vực từ giáo dục, y tế, đến vui chơi giải trì, nghiên cứu khoa học v..v.. Sức mạnh của các sản phẩm do công nghệ Multimedia mang lại là sự đa dạng phong phú của các dạng thông tin. Người ta có thể thu nhận, xử lý thông tin thông qua thị giác, thính giác nhờ âm thanh, hính ảnh, văn bản mà công nghệ Multimedia mang lại. Điều này làm cho hiệu quả thu nhận, xử lý thông tin cao hơn so với thông tin chỉ ở dạng văn bản. Ý tưởng đặt nền móng cho lĩnh vực công nghệ này đã có từ năm 1945. Ông Vanner Brush ,giám đốc cơ quan nghiên cứu phát triển khoa học của chình phủ Mỹ lúc bấy giờ (Director ofthe office Scientific Research and Development in the US Gouverment) đã đưa ra câu hỏi là, liệu có thể chế tạo được loại thiết bị cho phép lưu trữ các dạng thông tin để thay cho sách, nói một cách khác chẳng nhẽ mọi thông tin chỉ có thể lưu trữ ở dạng sách? Nhận thức được ý nghĩa quan trọng của loại thiết bị có tình chất trên, hàng loạt các nhà khoa học, công nghệ đã tập trung nghiên cứu. Nó là cở sở hay nền tảng của công nghệ Multimedia ngày nay. Năm 1960 Ted Nelson và Andrries Van Dam đã công bố công trính nói về kỹ thuật truy nhập dữ liệu dưới cái tên gọi Hypertext và Hypermedia. Kỹ thuật này cho đến nay vẫn được giữ nguyên tên và được sử dụng rộng rãi trong dịch vụ Web trên Internet. Năm 1968 Engleband đã đưa ra được hệ thống sử dụng Hypertext trên máy tình với cái tên NLS. Bộ quốc phòng Mỹ thành lập tổ chức DARPA (US deference advanced Research Prọject Agency) để nghiên cứu về công nghệ Multimedia. Năm 1978 phòng thì nghiệm khổng lồ MIT Media Laboratory chuyên nghiên cứu về công nghệ Multimedia được thành lập. Chỉ sau một thời gian ngắn hoạt động, nhận thức được tầm quan trọng và ý nghĩa xã hội của công nghệ Multimedia, người ta đã đầu tư gần 40 triệu USD cho phòng thí nghiệm này. Một loạt các công ty, các hãng lớn đã cho ra đời các phòng thì nghiệm về Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 6 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông Multimedia như AT & T, BELL, Olivity...Những nỗ lực không ngừng của các nhà khoa học,công nghệ đã cho phep người ta gặt hái được nhiều kết quả có tình chất nền móng cho lĩnh vực Multimedia. Những kết quả này đa nhanh chóng được triển khai ứng dụng trong các lĩnh vực truyền hính, viễn thông v.v... Dữ liệu Multimedia Thông thường chúng ta thường ghi nhận thông tin ở dạng văn bản, các văn bản này được mã hoá và lưu giữ trên máy tình, khi đó chúng ta có dữ liệu dạng văn bản. Một câu hỏi đặt ra nếu thông tin chúng ta thu nhận được ở một dạng khác như âm thanh (voice) , hính ảnh (Image) thí dữ liệu của nó ở dạng nào? Chình điều này dẫn đến một khái niệm mới ta gọi đó là dữ liệu Multimedia. Dữ liệu Multimedia là dữ liệu ở các dạng thông tin khác nhau. Vì dụ dữ liệu Multimedia là các dữ liệu ở các dạng thông tin như - Âm thanh (Sound) - Hính ảnh (image) -Văn bản (text). - Kết hợp của cả ba dạng trên. Khi nghiên cứu các dữ liệu ở các dạng thông tin trên, người ta nhận ra rằng cần phải phân chia dữ liệu Multimedia nhỏ hơn nữa. Bởi ví dữ liệu ở các dạng âm thanh, hính ảnh trong quá trính "vận động" theo thời gian có những tình chất rất khác so với dạng tĩnh. Điều này đòi hỏi kỹ thuật, công nghệ xử lý rất khác nhau.Ví vậy trong lĩnh vực công nghệ Multimedia người ta chia dữ liệu multimedia ở các dạng: 1. Văn bản (Text) 2. Âm thanh (sound) 3. Audio (âm thanh động, có làn điệu) 4. Image/ Picture (Hính ảnh) 5. Motion picture (ảnh động) 6. Video (ảnh động kết hợp âm thanh động) 7. Animation (hính ảnh sử dụng theo nguyên tắc chiếu phim) Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 7 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông 8. AVI (Audio-Video Interleaved AVI) 9. Kết hợp giữa các dạng trên. Công nghệ Multimedia Một cách đơn giản công nghệ Multimedia là công nghệ xử lý dữ liệu multimedia. Chúng ta cần lưu ý rằng khái niệm xử lý dữ liệu trong công nghệ thông tin bao hàm các công việc sau: mã hóa, lưu trữ, vận chuyển, biến đổi, thể hiện dữ liệu. Với ý nghĩa đó công nghệ Multimedia là công nghệ mã hóa, lưu trữ, vận chuyển, biến đổi, thể hiện dữ liệu multimedia. 1.2 Một số khái niệm cơ bản 1.2.1. Thế nào là phƣơng tiện Trong suốt chiều dài lịch sử, thông tin đã được chuyển tải thông qua một phương tiện duy nhất. Âm thanh, chẳng hạn như giọng nói của con người, chình là một loại phương tiện đó và qua nhiều thế kỉ trước khi chữ viết được sử dụng rộng rãi thí nói chuyện là một cách thức chủ yếu để trao đổi thông tin. Sau này con người bắt đầu kể chuyện và để lại thông tin về cuộc sống của mính thông qua các hính vẽ, các bức tranh. Sự ra đời của chữ viết đã cho con người một phương tiện khác nữa để diễn đạt ý nghĩ của mính. Ngày nay, con người thường sử dụng lời nói, âm thanh, ... LaText và PDF (Portable Document Format). - Thông thường, file header được sử dụng để chỉ ra khuôn mẫu tài liệu. Khi đã biết khuôn mẫu tệp, có thể trìch trọn thông tin cấu trúc để truy tím văn bản. Thì dụ, các từ hay thuật ngữ xuất hiện trong tiêu đề hay tên chương mục sẽ quan trọng hơn từ trong text. Do vậy, nó có trọng lượng lớn hơn trong tiến trính chỉ mục và tím kiếm. 3.2 Kỹ thuật nén văn bản Mặc dù dung lượng lưu trữ văn bản tương đối ìt so với loại dữ liệu khác như dữ liệu âm thanh, video, nhưng vẫn có nhu cầu nén văn bản khi cần lưu trữ nhiều tệp. Đặc trưng chình của văn bản nén là nén không mất mát thông tin, có nghĩa là có thể khôi phục chình xác văn bản như trước khi nén. Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 55 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông Có thể nén văn bản ví có nhiều ký tự xuất hiện thường xuyên hơn một số ký tự khác hay một số ký tự xuất hiện liên tục trong văn bản. Thì dụ các phương pháp nén văn bản: Huffman, RLE và LZW. 3.2.1. Nén Huffman Nguyên tắc Phương pháp mã hóa Huffman là phương pháp dựa trên mô hính thống kê. Dựa vào dữ liệu gốc, người ta tình tần suất xuất hiện của các ký tự. Việc tình tần suất được thực hiện bằng cách duyệt tuần tự tệp gốc từ đầu đến cuối. Việc xử lý ở đây tình theo bit. Trong phương pháp này, người ta gán cho các ký tự có tần suất cao một từ mã ngắn, các ký tự có tần suất thâp một từ mã dài. Nói cách khác, các ký tự có tần suất càng cao được gán mã càng ngắn và ngược lại. Rõ ràng với cách thức này, ta đã làm giảm chiều dài trung bính của từ mã bằng cách dùng chiều dài biến đổi. Tuy nhiên, trong một số tính huống khi tần suất là rất thấp, ta có thể không thu được lợi một chút nào, thậm chí còn bị thiệt một ìt bit. Thuật toán nén Thuật toán gồm 2 bước chình: - Bước 1: tính tần suất của các ký tự trong dữ liệu gốc Duyệt tệp gốc một cách tuần tự từ đầu đến cuối để xây dựng bảng mã. Tiếp sau đó là sắp xếp lại bảng mã theo thứ tự tần suất giảm dần. - Bước 2: mã hóa Duyệt bảng tần suất từ cuối lên đầu để thực hiện ghép 2 phần tử có tần suất thấp nhất thành một phần tử duy nhất. Phần tử này có tần suất bằng tổng 2 tần suất thành phần. Tiến hành cập nhật lại bảng và đương nhiên loại bỏ 2 phần tử đã xét. Quá trính được lặp lại cho đến khi bảng chỉ còn 1 phần tử. Quá trình này gọi là quá trình tạo cây mã Huffman vì việc tập hợp được tiến hành nhơ một cây nhị phân với 2 nhánh. Phần tử có tần suất thấp ở bên phải, phần tử kia ở bên trái. Với cách tạo cây này, tất cả các bit dữ liệu/ ký tự là nút lá, các nút trong là các nút tổng hợp. Sau khi cây đã tạo xong, người ta tiến hành gán mã cho các nút lá. Việc mã hóa rất đơn giản: mỗi lần xuống bên phải ta thêm 1 bit “1” vào từ mã, Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 56 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông mỗi lần xuống bên trái ta thêm 1 bit “0”. Tất nhiên có thể làm ngược lại, chỉ có giá trị mã thay đổi còn tổng chiều dài là không đổi. Cũng chình ví lý do này mà cây có tên gọi là cây mã Huffman. Quá trình giải nén tiến hành theo chiều ngược lại khá đơn giản. Người ta cũng phải dựa vào bảng mã tạo ra trong giai đoạn nén. Ví dụ Một tệp dữ liệu mà tần suất các ký tự cho bởi: Ký tự Tần suất “1” 152 “2” 323 “3” 412 “4” 226 “5” 385 “6” 602 “7” 92 “8” 112 “9” 87 “0” 1532 “.” 536 “+” 220 “-” 315 “ ” 535 Bảng tần suất sắp xếp theo thứ tự giảm dần: Ký tự Tần suất Xác suất “0” 1532 0.2770 “6” 602 0.1088 “.” 536 0.0969 “ ” 535 0.0967 “3” 412 0.0746 Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 57 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông “5” 385 0.0696 “2” 323 0.0585 “-” 315 0.0569 “4” 226 0.0409 “+” 220 0.0396 “1” 152 0.0275 “8” 112 0.0203 “7” 92 0.0167 “9” 87 0.0158 Lưu ý rằng, trong phương pháp Huffman, mã của ký tự là duy nhất và không mã nào là phần bắt đầu của mã khác. Ví vậy, khi đọc tệp nén từng bit từ đầu đến cuối ta có thể duyệt cây mã cho đến một lá, tức là ký tự đã được giải nén. Cây mã Huffman Bảng từ mã gán cho các ký tự bởi mã hóa Huffman: Ký tự Từ mã “0” 10 “6” 010 Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 58 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông “.” 001 “ ” 000 “3” 1110 “5” 1100 “2” 0111 “-” 0110 “4” 11110 “+” 11011 “1” 111111 “8” 111110 “7” 110101 “9” 110100 Thuật toán giải nén - Bước 1: Đọc lần lượt từng bit trong tập tin nén và duyệt cây nhị phân đã được xác định cho đến khi hết một lá. Lấy ký tự ở lá đó ghi ra tệp giải nén. - Bước 2: Trong khi chưa hết tập tin nén thì thực hiện bước một, ngược lại thì thực hiện bước 3. - Kết thúc thuật toán. Ƣu nhƣợc điểm: Ưu điểm: Thuật toán Huffman có ưu điểm là hệ số nén tương đối cao, phương pháp thực hiện tương đối đơn giản, đòi hỏi ít bộ nhớ, có thể xây dựng dựa trên các mảng bé hơn 64KB. Nhược điểm: - Mã Huffman chỉ thực hiện được khi biết tần suất xuất hiện của các ký tự. - Mã Huffman chỉ giải quyết được độ dư thừa phân bố ký tự. Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 59 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông - Huffman tĩnh đòi hỏi phải xây dựng cây nhị phân sẵn chứa các khả năng. Điều này đòi hỏi thời gian không ít do ta không biết trước kiểu dữ liệu sẽ được thực hiện nén. - Quá trình giải nén phức tạp do chiều dài mã không biết trước cho đến khi ký tự đầu tiên được tìm ra. 3.2.2. Nén RLE Mã hóa loạt dài RLE là một phương pháp nén ảnh dựa trên sự cắt bớt các dư thừa về không gian (một vài hính ảnh có vùng màu lớn không đổi đặc biệt là ảnh nhị phân). Loạt được định nghĩa là dãy các phần tử điểm ảnh (pixel) liên tiếp có cùng chung một giá trị. Phương pháp mã hóa loạt dài lúc đầu được phát triển dành cho ảnh nhị phân như các văn bản trên nền trắng, trang in, các bức vẽ kỹ thuật. Nguyên tắc Phát hiện một loạt các bit lặp lại, thì dụ như một loạt các bit 0 nằm giữa 2 bit 1 hay ngược lại, một loạt bit 1 nằm giữa 2 bit 0. Vì dụ: 110000000000000011. Dãy các bit lặp gọi là loạt hay mạch (run). Tiếp theo, thay thế chuỗi đó bởi một chuỗi mới gồm 2 thông tin: chiều dài chuỗi và bit lặp (ký tự lặp). Như vậy, chuỗi thay thế sẽ có chiều dài ngắn hơn chuỗi cần thay. - Ví dụ: Cho một chuỗi nguồn d: d= 5 5 5 5 5 5 5 5 5 5 19 19 19 19 19 0 0 0 0 0 0 0 23 23 23 23 23 23 23 23 Ta sẽ có chuỗi mới là: (10 5) (5 19) (7 0) (8 23) Tỷ số nén = 30/8 = 3.75 Đối với ảnh đen trắng chỉ sử dụng 1 bit để biểu diễn 1 điểm ảnh thí phương pháp này tỏ ra rất hiệu quả. - Ví dụ: Cho một chuỗi nguồn: d= 000000000000000111111111100000000001111111111000000000000000 Ta có chuỗi mới: (15, 10, 10, 10, 15) Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 60 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông Tỷ số nén = 60/(5*4) = 3 (chỉ sử dụng 4 bit để thể hiện độ dài loạt và không thể hiện giá trị loạt ví ảnh đen trắng chỉ có 2 giá trị bit là 0 hoặc 1). Chú ý: - Cần lưu ý rằng, đối với dữ liệu ảnh, chiều dài của chuỗi lặp có thể lớn hơn 255, nếu ta dùng một byte để lưu trữ chiều dài thí không đủ. Giải pháp được dùng là tách chuỗi đó thành 2 chuỗi: một chuỗi có chiều dài 255, chuỗi kia là số bit còn lại. - 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 đó hay nói cách khác trong ảnh cần nén phải có nhiều điểm ảnh kề nhau có cùng giá trị màu. Do đó, phương pháp này không đem lại cho ta kết quả một cách ổn định vì nó phụ thuộc hoàn toàn vào ảnh nén, chỉ thích hợp cho ảnh đen trắng hay ảnh đa cấp xám. - Ví dụ: Ta có một chuỗi nguồn: d = 5 7 9 11 13 18 28 38 48 58 30 35 40 45 Chuỗi kết quả sau khi mã hóa: 1 5 1 7 1 9 1 11 1 3 1 18 1 28 1 38 1 48 1 58 1 30 1 35 1 40 1 45 Tỷ số nén = 14/ 28 = 0.5 Như vậy, chuỗi sau khi mã hóa lớn hơn nhiều chuỗi nguồn ban đầu. Do đó, cần phương pháp cải tiến để xử lý những trường hợp như trên tránh làm mở rộng chuỗi dữ liệu nguồn nghĩa là chỉ mã hóa độ dài loạt dữ liệu lặp lại. Người ta đưa ra cách là thêm ký tự tiền tố vào trước độ dài loạt, việc giải mã được thực hiện nếu gặp ký tự tiền tố với độ dài loạt và giá trị điểm ảnh theo sau. - Ví dụ: Ta có chuỗi nguồn: d= 5 8 4 8 8 8 8 8 8 8 8 10 10 10 10 10 10 10 10 10 Giả sử ký tự tiền tố là “@” ta có chuỗi sau khi mã hóa: 5 8 4 @ 7 8 @ 9 10 Tỷ số nén = 19/9/ 2.1 Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 61 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông Tuy nhiên, trong một số trường hợp các điểm ảnh có độ tương quan với nhau về giá trị mức xám như trong vì dụ dưới đây ta có thể tiến hành xử lý như sau: - Ví dụ: Ta có một chuỗi nguồn: d= 5 7 9 11 13 18 28 38 48 58 55 60 65 70 75 80 85 90 95 100 Ta dựa vào độ tương quan này để có được hiệu quả nén cao, bằng việc áp dụng e(i) = d(i) – d(i-1) sẽ thu được: 5 2 2 2 2 5 10 10 10 10 10 -3 5 5 5 5 5 5 5 5 5 Áp dụng phương pháp nén RLE ta thu được: (1 5)(4 2)(1 5)(5 10)(1 -3)(9 5) 3.2.3. Nén LZW a. Phương pháp mã hóa LZ78 Mô hình từ điển (Dictionary – based compression): Có 2 loại: - Mã hóa từ điển tĩnh ( Static dictionary coding) - Mã hóa từ điển động ( Dynamic dictionary coding) Có rất nhiều thuật toán áp dụng kỹ thuật này như: LZ77, LZK, LZSS, LZHnhưng trong bài này chúng ta chỉ đề cập đến hai thuật toán chình là: - Thuật toán LZ78 - Thuật toán LZW Jacob Ziv và Abraham Lempel đã mô tả kỹ thuật dựa trên từ điển bằng mã hóa LZ77 và LZ78. Ý tưởng dựa trên việc thay thế 1 cụm ký tự bằng một con trỏ, trỏ đến vị trì xuất hiện trước đó của cụm ký tự. LZW là mã hóa trong họ LZ, hoàn thiện hơn LZ77 – LZ78 và đang được sử dụng phổ biến hiện nay. Nguyên tắc: Thay ví thông báo vị trì đoạn văn lặp lại trong quá khứ, mã LZ78 đánh số tất cả các đoạn văn sao cho mỗi đoạn ghi nhận số hiệu đoạn văn lặp lại trong quá khứ cộng với một ký tự mà nó làm cho đoạn đó khác với đoạn trong quá khứ. Như vậy, mỗi đoạn Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 62 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông mới là một đoạn ký tự trong quá khứ cộng với một ký tự trong quá khứ. Chình ví thế đoạn mới khác với đoạn cũ trong quá khứ. Ví dụ: Giả sử ta có đoạn văn bản sau: “aaabbabaabaaabab” Theo thuật toán LZ78 thí chúng được phân thành các đoạn như sau: Input a aa b ba baa baaa bab Đoạn 1 2 3 4 5 6 7 Output 0 + a 1 + a 0 + b 3 + a 4 + a 5 + a 4 + b Như vậy, bản nén của chúng ta là: (0, a); (1, a); (0, b); (3, a); (4, a); (5, a); (4, b) Nói chung thuật toán LZ78 là một thuật toán nén vă bản khá tốt, có thời gian chạy chương trính tương đối nhanh, tuy nhiên khả năng tiết kiệm chưa được khai thác tối đa. b. Phương pháp mã hóa LZW Khái niệm nén từ điển được Jocob Lempe và Abraham Ziv đưa ra lần đầu tiên năm 1977 và lấy tên là LZ77. Năm 1978 cải tiến dựa trên LZ77 và lấy tên là LZ78. Năm 1984, Welch đã cải tiến giải thuật LZ thành giải thuật mới hiệu quả hơn và được đặt tên là LZW (Lempe – Ziv - Welch). Phương pháp này 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à thay thế bằng từ mã tương ứng mỗi khi gặp lại chúng, nó hay hơn các phương pháp trước đó ở kỹ thuật tổ chức từ điển cho phép nâng cao tỷ lệ nén. Giải thuật LZW được dùng cho tất cả các loại file nhị phân, thường được dùng để nén các loại dữ liệu như: văn bản, ảnh đen trắng, ảnh màu, ảnh đa cấp xám và là chuẩn nén cho các dạng ảnh GIF và TIFF. Số bit/pixel không ảnh hưởng đến hiệu quả của LZW. Nguyên tắc 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 là tập hợp những cặp từ vựng và nghĩa của từ vựng. 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 song song với quá trính đọc dữ liệu. Sự xuất hiện của 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 đọc Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 63 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông qua.Thuật toán liên tục tra cứu và sau mỗi lần đọc một ký tự ở dữ liệu đầu vào thí tiến hành cập nhật lại từ điển. Do giới hạn của bộ nhớ và để đảm bảo tốc độ tím kiếm nhanh, từ điển chỉ có 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 = ). Cấu trúc từ điển như sau: - 256 từ mã đầu tiên theo thứ tự từ 0255 chứa các số nguyên từ 0255. Đây là mã của 256 ký tự cơ bản trong bảng mã ASCII. - Từ mã 256 chứa một mã đặc biệt là mã xóa (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ã xóa 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. - 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ã hóa 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 Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 64 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông 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 chuỗi HE L(76) 69 Thêm vào từ điển mã 259 đại diện chuỗi EL L 76 Thêm vào từ điển mã 260 đại diện chuỗi LL O(79) 76 Thêm vào từ điển mã 261 đại diện chuỗi LO H 79 Thêm vào từ điển mã 262 đại diện 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 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 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 chuỗi OHE L EL đã có trong từ điển -> đọc tiếp L 259 Thêm vào từ điển mã 266 đại diện 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() Bài giảng Nhập môn Đa phương tiện – Ngành TTĐPT, CNTRT 65 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông 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 Chuỗi thu được sau giải nén: “HELLOHELLOHELL”
File đính kèm:
- giao_trinh_nhap_mon_da_phuong_tien_phan_1.pdf