Tài liệu Nén video phục vụ cho lưu trữ và truyền tải trong môi trường băng hẹp

Đ Ạ I H Ọ C Q U Ố C G IA H À NỘI TRƯ Ờ N G ĐẠI H Ọ C CÔNG N GH Ệ Nguvễn T h ị T hanh Hưưng NÉN VIDEO PHỤC vụ CHO Lưu TRỮ VÀ TRUYỀN TẢI TRONG MỐI TRƯỜNG BÂNG HẸP N gành : C ông nghệ thông tin M ã s ố : 1.01.10 LUẬN VĂN THẠC s ĩ NGƯỜI HƯỚNG DẪN KHOA HỌC: PSG.TS NGÔ QUỐC TẠO _ j _____ _______ _____ ——~ ■■■-■ , " \! — I 丨卜. 丨 h C :.. j xr^-NG w L —-------------------- ĩ HOM G TIN n • 一 V z i o / ^ G H à N ôi - 2006 " i V iiN j Đ Ạ I H Ọ C Q U Ố C G IA H À NỘI TRƯ Ờ N G ĐẠI H Ọ C CÔNG N GH Ệ Nguvễn T h ị T hanh Hưưng NÉN VIDEO PHỤC vụ CHO Lưu TRỮ VÀ TRUYỀN TẢI TRONG MỐI TRƯỜNG BÂNG HẸP N gành : C ông nghệ thông tin M ã s ố : 1.01.10 LUẬN VĂN THẠC s ĩ NGƯỜI HƯỚNG DẪN KHOA HỌC: PSG.TS NGÔ QUỐC TẠO _ j _____ _______ _____ ——~ ■■■-■ , " \! — I 丨卜. 丨 h C :.. j xr^-NG w L —-------------------- ĩ HOM G TIN n • 一 V z i o / ^ G H à N ôi - 2006 " i V iiN j MỤC LỤC MỤC LỤ C ....................................... ...................... ............................................................................. 1 DÀNH ỈVIỤC CÁC HÌNH VẼ VÀ BẢNC ĐƯỢC sù' DỤNG...............................................................3 MỞ OÀII Mia hóa dữ liê u ....................................................................................... Tâm quan trọng cua nén video.............................................................. Phân loại nén dữ liệu............................................................................. Vài nét về nén video............................................................................... Mục đích nghiên cún của luận văn........................................................ Cấu trúc luận văn.................................................................................. ............................................ ........................... — ............................................................................................................* .......................................................................................................................................................... ___ 、 CHUƠNC;丨 - k N C ; QUAN VÈ NÉN VID EO .......................................................... 1.1. Giới thiệu về nén ảnh.................................................................. 1.2. Một sô phương pháp nén ảnh theo kiêu lossless......................... 1.2.1. Entropy................................................................................. ■*> r 1.2.2. 1.2.3. 1.2.4. H uffm an .............................................................................................. M ã hóa số học (A rithm e tic coding)............................................. M ã hoá lo ạ t dài (Run Length E ncoding)................................... 1.2.5. Move to Front Coding......................................................... 1.3. Ciói thiệu về nén video............................................................... 1.3.1. Phân biệt giữ a nén video và nén ả nh .......................................... 1.3.2. 1.3.3. Mô hình nén video tống quát............................................... . Mô hình thời gian (Temporal model)................................... . 1.3.4. 1.3.5. D ự đoản từ các ảnh phía trư ớc....................................................... Những thay đỗi theo chuyển động ................................................. CHƯƠNG 2 - 2.1. 2.2. 2.3. 2.4. 2.5. CÁC： KỸ THUẬT CHÍNH ĐUỢC s ử DỤNG TRONG NÉN VIDEO Nén không gian dữ liệ u .............................................................. Giảm không gian mầu................................................................ Nén theo thòi gian....................................................................... Nén dựa vào đối tượng cơ bản..................................................... Kỹ thiiật nén MPEG:.. . . ........................................................ 2.5.1. 2.5.2. 2.5.3. 2.5.4. 2.5.5. Quá trìn h g iả i nén M peg ................................................................. Phăn cấp dữ liê u ( Data H ie ra rch y)............................................. In te r-P ictu re Coding .......................................................................... Cấu tạo dòng Video ........................................................................... Nén theo ch "yen động ...................................................................... 2.6. Nén dựa vào các block................................................................. 2.7. Uớc Iưọng và bù chuyển động..................................................... 2.7. /. Macrobiock........................................................................... 2.7 .2. ƯVClượng ch uyển động theo macroblock....................................... 2.7.3. Bù chuyển động theo từng macroblock................................. 2.8. Chuyên đôi mien biêu diên và van đe vẽ 丨 irọng tử....................... «% ■ 2.8.1. 2.8.2. A A ■ • Ạ 1 « A «BÃ V _ A _ -* A 1_ _ M _*> Thuật toán D C T áp dụng cho nén ảnh ........................................ Biến đổi D C T .............:....................................................................... 6 8 9 5 Kết luận ................................................................................. M ỘT SÓ C H LÀ N NÉN VIDEO THÔNG DỤNG..................... Chuẩn nén video và ứng dụng............................................ G iói thiệu về M P E G ......... .................................................... Chuẩn MPEG-1................................................................... Chuẩn MPEG-2................................................................... Chuẩn nén video MPEG-4.................................................. 5 í5 5 7 ô t x K T ô- .ớ * 9 G iớ i th iệ u M PEG -4 ................................................................ P ro file ，objects ，tools，và levels ............................................. 3.5.3. Một sô công cụ nén video được sử dụng trong MPEG4 3.5.4. Điểu khiển tốc độ dòng mã hỏa .................................... 3.5.5. ủng dụng của MPEG-4 : ............................................... 3.6. So sánh các định chuẩn MPEG........................................... 5 6 THỤC N G H IỆ M ......................................................................... 7 Chương trình thực nghiệm................................................. Hiệu quả hoạt động.............................................................. Những mặt hạn chê.............................................................. ;0 8 4.1. 4.2. 4.3. r - T FS C HƯƠNG 4 - vi J 3 5 3.5. /. 3.5.2. í9 5 ;io 5; 5. 3 3.1. 3.2. 3.3. 3.4. 3.5. i7 4! 4 (i8 5 c HUONG 3 - 22 2.9. ^. J 4 L ư ợ nỊỊ tử h o á ....................................................................... 4 2. H. 3. , KÉT LU Ậ N .................:.……:..................................................................................... TÀ丨 UỆ； Ù TH A M K H Ả O ....................................................................................... 2 DANH MỤC CÁC HÌNH VẼ VÀ BẢNG Đ ư ợ c s ử DỤNG I linh 1: Kẻi qua nén anh theo hai phương pháp:lossy và lossless....................................................10 1lình 2: Sơ đồ tổng quát bộ mã hóa video..........................................................................................19 1linh 3: Hệ tọa độ IJ， V............................................. :....................................................................... 23 íiinh 4: Mô tà quá trinh biến đồi keyframe....................................................................................... 26 Hinh 5: Mô tả tách đối tượng..............................................................................................................27 Hình 6: I ỉệ thống giải mâ M PEG ....................................................................................................... 28 Hình 7: Phân cấp dữ liệu..................................................................................................................... 29 Hình 8: Forward Prediction (dự báo một chiều)............................................................................... 31 1linh 9: Bidirectional Prediction (dự báo hai chiêu).........................................................................31 Hình 10: Thứ tự các khuôn h ìn h .......................................................................................................32 Hình 11 : Thử tự hiển thị và thứ tự khuôn hinh trong dòngdữ liệu Video................................... 33 Hình 12: Macroblock (4:2:0)............................................................................................................ 35 Hình 13: Ước lượng chuyền động theo macroblock...................................................................... 36 ỉ ỉình 14: Ánh thứ nhất........................................................................................................................38 ỉỉình 15: Ảnh thứ 2 ............................................................................................................................ 38 Hình 16: Phân sai sô giữa ành 1 và ảnh 2 khi không sử dụng bù chuyên động......................... 39 Hình 17: Phần sai số giữa ảnh 1 và ảnh 2 khi áp dụng bù chuyển dộng cho khối 16 X 16••…39 Minh 18: Phần sai số giữa ảnh 1 và anh 2 khi áp dụng bù chuyền động cho khối 8 X 8 ........40 Hình ] 9: Phần sai số giữa ảnh 1 và ánh 2 khi áp dụng bù chuyển động cho khối 4 X 4 ........40 Hình 20: Quá trình mã hoá biến đồi trong M PEG...................................................................... 41 Mình 21 : Sơ đồ chung quá trình nén ảnh.......................................................................................42 Hình 22: Sơ đồ chung quá trình giải nén ảnh............................................................................... 42 Hình 23: Sơ đồ chuyển đối dừ liệu video dùng cho các ứng dụng.......................................... 48 Hình 24: Bang so sánh kết quả thử nghiệm nén dữ liệu videocho các ứng dụng...................49 Hình 25: Sơ dồ nguyên mẫu giải nén chuẩn MPEG1 (ISO/IEC 11172)..................................51 l iình 26: Sơ đồ nén âm thanh.........................................................................................................51 Hình 27: Mô hinh hệ thống giải mã MPEG2.................................................................................. 54 l ỉình 28: Mô hinh nén và giái ncn theo từng lớp của MPEG-4.................................................... 56 s r -» 3 Ilinh 29 ： Ví dụ về một cảnh trong Mí)t:c 4 ..................................................................................57 卜 Hình 30: VOP và v o dạng hinh chừ n h ật...................................................................................... 58 I lình 31: VOP và v o dạng hình tùy ý ............................................................................................ 58 I lình 32: Danh sách profile cua chuẩn MPHG4............................................................................. 59 Hinh 33: Sư đồ kết hợp các đối tượng và công cụ nén hiệu quả...................................................61 I ỉ ình 34: Bang giá trị cùa dc-scaler phụ thuộc vào tham số Q P ................................................62 Hinh 35: Ọuá trình nén và giải nén các P-VOP............................................................................. 62 Hình 36: Mô hinh dự đoán chuyển động cho B-VOP................................................................. 63 Hình 37: Bicu diễn vecto bù chuyến đône cho mỗi macroblock...............................................65 Mình 38: Sơ đồ cấu trủc gói video................................................................................................ 66 Hình 39: Điều khiển lồi bàng Newpred....................................................................................... 68 Hình 40: Biến đổi bitrate......................................................................................... .......................70 Hình 41 : Bộ mã hoá và giải mă sử dụng bộ đệm ........................................................................ 71 Hình 42: Bảng so sánh các định chuẩn M PEG............................................................................74 Hinh 43: Mô hình nén phim mô phòng......................................................................................... 75 4 M Ở ĐẦU Mã hóa dữ liệu Thuậl ngữ mã hóa dừ liệu có ihể hiểu theo nhiều nghĩa khác nhau, tuỳ thuộc t ’ vào mục đích mã hóa: M ã hóa đê bảo vệ an toàn dừ liệu, giảm thiêu việc dữ liệu bị xâm hại từ các tác nhân bên ngoài có ý nghĩa bảo mật. Mã hóa để làm giâm bớt kích thước dữ liệu phục vụ trong lưu trữ và truyền thông, còn gọi là nén dừ liệu. 、 1 Khái niệm mã hóa được đê cập tới trong luận văn này được hiêu theo nghĩa thứ hai: nén thu nhỏ dữ liệu. * Tâm quan trọng của nén video % f r f Từ lâu vân đê nén dữ liệu đã được coi là thiêt yêu trong các lĩnh vực lưu trừ và truyền tải dữ liệu. Với từng loại dữ liệu khác nhau như số liệu, chương trình, âin thanh, hình ảnh thì sử dụng các phương pháp nén khác nhau. Chất lượng s r \ nén cũng phụ thuộc vào yêu câu của các thiêt bị truyên và ứng dụng. \ ' Ngày nay, nhu câu khai thác mạng internet phục vụ truyên thông, học tập, giải Irí ngày một tăng. Đặc biệt là các nhu câu xem phim trực tuyên, truyèn » r / ' hình trực tuyên đòi hỏi chát lượng phục vụ ngày một tôt hơn. Tuy nhiên, tôc độ thông lượng Internet không đù đế giải nén video, audio tronu thời gian thực (khó khăn thường gặp là tôc độ truyên dân các frame thâp, hoặc kích thước các frame nhỏ). Một đĩa DVD (Digital Versatile Disk) chí cỏ thể lưu trữ được vài giây raw video có độ phân giải và tôc độ truyên frame đảm bảo chât lượng truyền hình. Vì vậy, việc lưu trữ video trên DVD là không thực tế nếu không tính đén các giải pháp nén audio và tín hiệu video. Mặt khác, với kênh truyền có tần sổ nén cao, có thể truyền phát một hoặc nhiều kênh video đã được nén với độ phân giải cao, thay vi việc gửi đi các đoạn * t video dơn lẻ, độ phân giải thâp…Đặc biệt với chât lượng và dung lượng đường \ f 、 * • truyên hạn chê, việc nén video ià vô cùng cân thiêt dôi với các ứng đụng multimedia trong nhiều năm tới. T ó m lại. nén video có hai lợi ích quan trọníỊ. T h ứ nhảt, nén v id e o tạo cơ hội để khai thác video kỹ thuật số truvền phát trực lưvến và là môi trường lưu trữ mà khôns cẩn hỗ trợ giải nén ('ra w ') video. Thứ hai, nén video đem lại hiộu quả cao trong truyền dẫn và lưu trữ. Phân loại nén dữ liệu Nén dừ liệu được chia thành hai dạng cơ bản: Nén không mất thông tin t / r (Lossless) và nén có mât thỏĩìR tin (Lossy). Đôi với dạng nén không mât thông tin. ảnh được khôi phục hoàn toàn giống ảnh gốc, thường được sử dụngtrong các lĩnh vực đòi hỏi độ chính xác cao như y hoc, quân sự. Tuy nhiên các phưưns pháp nén không mât thônạ tin cho ti sô nén thâp. điêu nảy đòi hỏi phải có thiết bị lưu trữ và đường truyền lớn. Các thuật toán nén không mất thông tin thường dựa vào việc thay thế một nhóm các ký tự trùng lặp bởi một nhóm các / ký tự đặc biệt khác ngăn hơn mà không quan tâm tới ý nghĩa của dòng bit dữ liệu và chỉ tạo ra một bản sao của đoạn dữ liệu lặp lại này. M ột số thuật toán khác dùng những mã có độ dài khác nhau mã hóa cho các kí tự khác nhau giúp cho các ký tự này chiếm chỗ ít hơn. Các phương pháp nén không mất thông tin như Run-Length Encoding (RLK), Huffman Coding, Arithmetic coding, Shannon-Fano Coding, LZ78. LZH, LZW.... Đối với dạng nén có mất thông tin ( lossy compresstion), dữ liệu được khôi phục không giông hoàn toàn với dữ liệu gôc, nhưng vân dàm bảo sai sô châp nhận dược. Ưu điểm của phương pháp này là cho tỉ số nén cao, phù hợp với các ứng dụng lưu trữ và truyền âm thanh, ảnh tĩnh, video qua một mạng có băng / t ' thông hạn chê. Các phương pháp nén mât thông tin thường dựa trên nên tảng là loại bò bớt các màu mà mắt thường không hoặc khỏ cảm nhận được, chỉ giữ lại một số màu chủ yếu có ảnh hưởng tích cực đến khả năng cảm nhận màu cùa mắt. Ngoài ra. ta cũng cỏ thể áp dụng phương pháp giảm độ phân giải của ảnh, tức là giám bớt số điểm ảnh trên một inch (dots per inch - dpi). Các dạng nén mất dừ liệu thườn a cho hệ số nén cao hơn, nó liên quan lói việc dùng các phép biến đổi tín hiệu từ miền này sane miền khác. Các kỹ thuật biên đôi có mât dừ liệu có thê kc dên: Differential Encoding. Discrete Cosine 'i'ransfonn(DCT), Vector Quantization... Vài nét về nén video Công nghệ video hiện dã trừ nên quen thuộc và dược sử dụng rộng rãi trong \ •» nhiêu lĩnh vực. Công nghệ này dựa trên sức mạnh của máy tính đê xử lý và truyền tải video. Hạn chế của video là khối lượng dữ liệu rất lớn và khả năng tương tác khó khăn. Hiện nay để giải quvết những yếu điểm này có nhiều hướng nghiên cứu: Tìm hiểu thuật toán nén video hiệu quả dể giảm thiểu khối lượng dữ liệu video, nghiên cứu các định chuẩn video để có thể tối ưu hoá video. Xây dựng tương tác trong video. Xây dựng cơ sờ dừ liệu video. Thuậl ngữ nén video Video compression (còn gọi là video coding) là quá trình thu gọn. cô đặc các chuồi video dạng số vào một không gian nhớ có số bit nhỏ hơn kích thước ban đầu. “ RAW” hoặc quá trinh giải nén thông thường đòi r r t hỏi bitrate khá lớn (xâp xỉ 216 Mbits trong một giây đôi với Video chât lượng truyền hinh (TV-qualit>). Nén video bao gồm hệ thống nén (encoder) và giải nén (decoder). Bộ encoder chuyển dữ liệu nguồn vào trong một mô hình nén trước khi truyền dẫn y r » hoặc lưu trữ, còn bộ decoder chuyên dữ liệu đã nén thành video sô ban đâu. Cặp encoder/decodcr thường được biết đến với cái lên CODEC. Mỗi tín hiệu thu nhận được có thể được nén bằng cách loại bỏ các thông tin • • thừa. Đôi với nén không mât thông tin (lossless compression) dựa trên mô hình r ' t thông kê. dữ liệu sau khi được khôi phục hoàn toàn giông với dữ liệu gôc ban đầu, phương pháp nén không mất thông tin cho hệ số nén thấp. Do vậy chỉ có ể t một sô ứng dụng đòi hỏi độ chính xác tiệm cận tuyệt đôi như nén video phục vụ trône y tế, quân sự... thường sir dụng phưcyng pháp này. Phần lớn các kỹ thuật nén video dựa trên phương pháp nén mất thông tin. Phương pháp này cho hệ số nén cao. tuv nhiên các tín hiệu thu lại sau quá trình giái mã không hoàn toàn giống như dừ liệu ban đầu. Tuy nhiên mục dích cùa thuật toán nén video là lìm một phươníỉ pháp nén hiệu quã ngay cá khi phái chấp nhận các biến dạnti trong quá trình nén. Mắt và não người không nhạy cảm với các tín hiệu tần số thấp, do vậy y \ \ f không phát hiện dược sự thav đôi của ảnh khi các tín hiệu thuộc miên tân sô thấp bị loại bỏ. Thuật toán nén video loại bỏ nhừns thông tin thừa trong miền thời gian, không gian, và miền tần số. Ảnh sau khi đã được xử lý bằng cách loại bo thông tin thừa như trên, được đưa vào nén hằng các kỹ thuật mã hóa entropy như mã hỏa Huffman, mã hóa số học... Nén video, ảnh đã có một bề dày nghiên cứu hơn 20 năm nay. Có rất nhiều k ỹ th u ậ t n é n và g iã i nén đ ư ợ c g iớ i th iệ u và phát triể n . T ro n g đ iề u k iệ n h iệ n nay, r s ■» khi mà có rât nhiêu các chuân nén đan xen, cạnh tranh, và cùng được lựa chọn, ■» / ^ r » Sự ra đời của một chuân nén và giải nén thông nhât cho phép nhiêu sản phâin t / •» của các nhà sản xuâl khác nhau cùng tim đưực tiêng nói chung đê hoạt động hiệu quá là vô cùng cần thiết. Chính điều này đã dẫn đến sự ra đòi cùa các chuẩn nén ảnh quốc tế bao gồm JPEG để nén ảnh tĩnh, các chuẩn MPEG và H.26x phục vụ nén video. Mục đích nghiên cứu của luận văn r \ t \ Xuât phát từ những nhu câu thực tê trên，tôi lựa chọn dê tài “ N á i video phục vụ cho lưu trữ và truyền tài trong môi trường băng hẹp” . Luận văn tập trung vào nghiên cứu một sổ vấn đề như sau: - Trình bày một cách hệ thống một số phương pháp nén ảnh cơ bản - Tập trung nghiên cứu các kỹ thuật nén video. - Nghiên cứu định chuẩn MPEG, đặc biệt là chuẩn nén video MPEG4. Bao gồm việc giới thiệu một cách hệ thống quá trình mã hóa và giải mã, khai thác các công cụ nén video của chuẩn MPEG4 đảm bảo truyền dẫn hiệu quả trên môi trường băng hẹp, tổng hợp so sánh các định chuẩn MPHG. - Vi ếl chương trình mô phong nén video (lược thu nhận trực tiếp từ các * y thiỏt bị thu phô thông như Web Cam. dựa trên chuân MPEG4 8 cấu trúc luân văn \ • Luận vãn bao gôm hôn chương như sau. Chương 1: Giới thiệu tồng quan về nén video. Chương 2: Trinh bày một cách hệ thống các kỹ thuật chính được sử dụng trong nén video. Chương 3: Mô tả. phân tích các ưu. nhược điểm và so sánh một số chuẩn nén phim thông dụng. Chương 4: Viết chương trình thực nahiệm mô phỏng bộ nén phim theo chuẩn MPHG4, va dánh g i á . : 9 CHƯƠNG 1 - T Ó N G QUAN VÈ NÉN V ID E O 1.1. Giói thiệu về nén ảnh r \ r Nén ánh là khoa học mã hóa một cách có hiệu quả các ảnh sô nhăm giảm sô lượng các bít cần thiết để biểu diễn ánh. Mục đích nén ảnh là giảm chi phí trong việc lưu trữ và truyền thông nhưng vẫn giữ dược chất lượng ảnh. Chúng ta xét ví dụ lưu trừ và truyền dữ liệu trên đườne truyền với tốc độ 9600 bps để thấy rõ sự cần Ihiết cùa việc nén ảnh: và mât 3.64 phút đê truyên. - Ảnh màu RGB cùng độ phân giải như thế cần 6.000.000 bit để lưu trữ và 11 phút để truyền. - Anh âm bản 24 X 36 mm được quét ở 12 micromet, khoảng 3000 X 2000 điểm ảnh, nếu sử dụng 8bit/điổm ảnh thì cần 48.000.000 bit lưu •> % trữ và 83 phút đê truỵên tải, ảnh âm bản màu đòi hỏi lượng lưu trữ và thời gian truyền tái lớn gấp 3 lần. \ t r Nén dừ liệu ảnh bao gôm nén mât thông tin và nén không mât thông tin, lựa * t chọn phương pháp nén nào là tuỳ thuộc vào việc cân đôi giữa chât lượng ảnh nén và tỳw> số nén. ãnh đưưc nén bâng thdâi loàn khỏng nìãt thong tin. sau khi phục h6i Hình 1: .inh được ncn bẳng (h u ii lo.in mấ( íhồng lin, sau khi phục hói Kết quả nén ảnh theo hai phuoìig pháp: lossy và lossless 10 Các phương pháp nén ảnh không mât thông tin bao gôm một sô phương p h á p c ơ bản như : h u ffm a n , ru n le n g c o d in g , a rith m e tic , ... ĩ ^ -7 % Các phương pháp nén ảnh có mât dừ liệu sử (lụng kỹ thuật chuycn đôi miên biêu diên và lượng tử hóa. 1.2. Một sổ phương pháp nén ảnh theo kiếu lossless 1.2.1. Entropy 1. Độ đo Entropy p(a) log2—L p(a) H(A) = E Trong dó : - A là tập thông báo - H(A) là độ đo Entropv của A - p(a) là xác suất cùa thông báo a Lượng thông tin trong mồi thông báo a được định nghĩa như sau: i(a) = log2 — — p(a) Định nghĩa đó cho thấy xác suất của thông báo a càng lớn thì lượng thông tin trong a càng nhỏ 2. Mã tiền tố Tập mã c được gọi là thoà mãn tính tiền tố nếu không tồn tại trong c một cặp mã sao cho mã này là đoạn đầu của mã kia. » t r r l ập mã c được gọi là m ã tiên tô tô i tru nêu: - c thoả mãn tính tiền tố - Không tim được một tập mã C' sao cho độ dài trung bình cùa các từ mã trong C' nhỏ hơn độ dài trung bình của các từ mã trong c. 3. Liên hệ giữa Entropy và độ dài từ mã Giả sử ta có một tập thông báo A = { ai a2, ...,an } Phân phối xác suất tương ứng của A là P{pi P2 , ...,pn } c = {C|.C2, ...,cn } là tập các từ mã của A. Độ dài từ mã của các thông báo trong tập A tương ứng là 1C| 1C2, ...,lcn, Khi đó, độ dài trung bình từ mã là: 1= + r ：i, : + -• + r,J,n /=1 Xét tập Ihông báo A có Entropy là 11(A) và tập các từ mã c thoả mãn tính liền tố. / (C) là độ dài trung bình của tập các từ mã c, khi đó : IỈ(A)< / (C) Pj thì suy ra ltj < lCj. Điêu này có nghĩa là nêu xác xuât của một thông báo càng lớn thì độ dài từ mã cùa thông báo đó càng nhỏ ỉ. 2.2. H uffm an • t Phương pháp mã hóa Huffman dựa vào mô hình thông kè xác định xác suât f t t xuât hiện các kí tự trong dữ liệu gôc. Trong một dày kí tự, kí tự nào có xác suât ' 、 r * xuât hiện nhiêu hơn SC được thay b ãn e m ột m ã nhị phân với sô bít nhở (từ m ã ngắn), và ngược lại. Như vậy với phương pháp này độ dài trung bình của từ mã r \ r > sẽ giảm. Xác suât được tính băng cách duyệt tuân tự từng kí tự trong tệp gôc. Ưu điềm của phương pháp mã hoá Huffman là sinh ra tập các từ mã có độ r / s dài trung bình nhò nhât và thỏa mãn tính liên tô. Hay nói một cách khác, N t r phương pháp Huffman sinh ra tập mã tiên tô tôi ưu. Thuật toán xây dựng tập mã Huffman: • 1. r »w Xuât phát từ rừng cây con, môi kí tự i là một cây có gôc wi / , r được đánh trọng sô pi (pi là phân phôi xác suât của kí tự ị trong chuỗi kí tự). 2. Lặp lại các bước sau cho đến khi chỉ còn lại mộl cây duy nhất 3. Chọn hai cây có gốc trọng số nhỏ nhất (pi và pj min) 4. Cìhép hai cây con đó thành câỵ mới và đánh trọng số gốc bằng pi + pị Không quan trọng thứ tự trái phải của cây con 12 khi ghép vảo, nhưng để thuận tiện, nếu pi ■* pj thì đặt cây con cỏ trọng số thấp hơn vào nhánh trái cua cây mới. 5. Đảnh trọng số cho mỗi cung của cây kết quả. cung có hướng sang trái trọng sô băng 0, cung có hướng sang phải đánh trọng số bằng 1, ta có kết quả là một cây nhị phân Huffman 6. Duyệt câv Huffman sẽ sinh ra bảng mã tiền tố tối ưu Số lượne hit được sử dụng để lưu trừ mã của mồi kí tự trong phương pháp 1 r r Huffman là log?— trong đó p là xác xuât xuât hiện của kí tự đó trong thône p ' báo. Vidụ, một kí tự A có phân phối xác suất trong thông báo là 1/256 , thì cần số bit dể lưu Irữ ỉà log2256, tức là cần 8 bit. Nếu phân phối xác suất của kí tự là / r \ 0,5 thì sô bit m ã hoá cho kí tự đạt tôi ưu băng 1. Tuy nhiên, rất dễ nhận thấy một nhược điểm của phương pháp này, dó là số bit thực tế cần sử dụng cho mồi kí tự thường lớn hơn so với lý thuyết. Chẳng r • r hạn, một ki tự có phân phôi xác suât là 1/3，theo lý thuyêt thì 1,6 bit. nhưng trên thực tế phài cần 2 bit để mã hoá. Nếu phân * sô bit mã hoálà phối xác xuấtlà 0,999 cần 0,001443 bit, trên thực tế cần 1 bit tức là gấp gần 693 lần số lượng r ’ r » bit trên lý thuyêt. Và như vậy, nêu phân phôi xác xuât của kí tự càng lớn thì tỉ lệ nén càng giảm. Điều này có nghĩa là nếu trong dừ liệu nguồn số đoạn lặp lại càng nhiều thì phương pháp Huffman càng tỏ ra kém hiệu quả 18,1,4,3]. 1.2.3. Mã hóa sô học (Arithmetic coding) Khác với mã hoá Huffman, mã hoá số học bỏ qua việc sinh mã cho từng kí tự, thay vào đó là thay thế một chuồi kí tự đầu vào (message) bàng một khoảng •) X (low, high) năm trong [0,1], các khoảng con này hoàn toàn độc lập đê đảm bảo ' * f s f s tính tiên tô của mã dược sinh ra. Sô bit cân thiêt cho mã hoá nhỏ hơn chiêu dài của thông báo. Việc mã hoá và giải mã băng phương pháp mã hoá sô học đêu / r ^ y dựa vào phân phôi xác suât cùa môi kí tự trong thông báo cân mã hoá. Phươne pháp mã hoá số học hoàn toàn khả thi khi thực hiện trên máy tính vói những thanh íihi cố định. 13 Quả trình mâ hoá được mô lá như sau: Set low to 0.0 Set hìẹh to 1.0 While there are still input symbols do Get an input symbol code—range = high - low high - low + ra n ^e *high range (sym bol) low = low + range */(m’一rcw ge (sym bol) End o f while Output low Trong đó, cặp (low ， high) đươc khởi tạo giá trị ban đầu là (0，1) [5]. Ví dụ mã hoá thông báo “ BILL GATES” : Kí tự Phân phôi xác suất Khoảog con Space A B E G 1 L s T 1/10 1/10 1/10 1/10 1/10 1/10 2/10 1/10 1/10 0.00-0.10 0.10-0.20 0.20-0.30 0.30-0.40 0.40 - 0.50 0.50 - 0.60 0.60-0.80 0.80 - 0.90 0.90-1.00 1'rcn thực tế, mỗi kí tự trong thông báo được nhận một khoảng trong đoạn f ệ \ [0,1 ] tuỳ thuộc vào phân phôi xác suât của kí tự đó, nhưng không bao gôm cận trên. Chẳng hạn kí tự “ T” trong thực tế nhận được khoảng 0.90 - 0.999... Kết quả sau khi mã hóa thông báo “ BILL GATES” theo phương pháp mã hóa số học: Kí tự 2 1 '6 . 0.2 l. o . o . 3 0.0 0.2 High ? 0 B I Low 14 0.256 0.258 0.2572 0.2576 Ü.25724 SPACE 0.25720 Ci 0.257216 0.257220 0.2572164 A 0.2572168 r 0.25721676 0.2572168 0.257216776 1-; 0.257216772 0.2572167752 0.2572167756 s Kct quả mã hóa thông báo "B IL L GATES” thu được giá trị low _ final bằng 0.2572167752 Quá trinh giải mã thông báo '"BILL GATES'' sẽ tien hành ngược lại, bắt đầu từ giá trị low final = 0.2572167752 nhận được và đối chiếu với các khoảng con của mỗi kí tự. Giá trị low_final rơi vào khoảng con [0.2;0.3], do vậy kí tự đầu tiên là “ B” ，và low B = 0.2 . Biển đồi ngược lại ta được lo w jk i tự tiếp theo =0.572167752, nằm trong khoảng [0.5;0.6], vậy kí tự tiếp theo là “ I” . lặp lại cho đến khi gặp dấu hiệu EOF hoặc khi độ dài thông báo đích bang với thông báo nguồn. Thuật toán giải mã dược mô tả như sau Get encoded num ber Do find sym bol whose range straddles the encoded num ber output the s y m b o l range = symbol low value - symbol high value subtract symbol low value from cncoded n u m b e r divide encoded number by ranee Until no more symbols f > f Trong thực tê, việc tính toán các cận của các khoảng mã yêu câu các sô có độ chính xác cao, nhưng máy lính chỉ cho phép tính toán trên các thanh ghi có kích thước hữu hạn (16 bit, 32 bit, 64 bit, 128 bit), do đó thuật toán mã hóa số học không thể thực hiện được khi các khoảng cần cho việc mã hóa quá bé, vượt qua khả năng của các thanh ghi. Để khắc phục vấn đề này, người ta sử dụng các r f • SÔ nguycn với độ dài cô định. Khi đó, mặc dù các mã sô học thu được không 〜 , chính xác, vì lôi làm tròn, nhưng nêu cả bộ mã hóa và giải mã cùng sử dụng chung một cách làm tròn thì bộ giải mã sẽ sinh ra các thông báo chính xác. 15 • r r Dôi với kỹ thuật mã hóa sô học thực hiện trcn các sô nguyên, quá trinh mã * r ^ hóa \ à giai mã được áp dụnẹ trong thực tc vàn đảm bảo dộ chính xác như kêt quả ihực hiện trên số thực. 1.2.4. M ã hoá loạt dài (Run Length Encoding) Mã hóa loạt dài sử dụng đặc điếm dư thừa về không gian, “ loạt” được dịnh 7 / _ < nghĩa ià dãy điêm liên tiêp có cùng giá trị. Ọuá trình mã hóa loạt dài bao gôm hai bước: Tiền xử lv dừ liêu và mà hóa Huffman. Trước tiên, dừ liệu nguồn được chuyển sang dạng trung gian, các kí tự liên t t \ r tiêp nhau được thay thê băng một cặp (giá trị đêm, ký tự đại điện). Phân tích r \ thông kê dừ liệu trung gian và mã hóa băng phương pháp Huffman. Dữ liệu mã hóa ít bị lặp, và lúc này phương pháp Huffman tỏ ra hiệu quả hơn. Áp dụng trong mã hóa ảnh: Với ảnh đen trắng: kí hiệu điểm ảnh trắng là 1，điểm ảnh đen là 0, giả định điêin ánh đâu tiên của ảnh là trăng. Ví dụ với chuôi điêm ảnh 111110001111 ....kết quả tiền xử lý là 534. Bộ mã hóa sẽ phân tích thống kê kết quả này và mã hóa chúng. Với ảnh đa cấp xám: giả sử có chuồi điểm ảnh là 3,3,33,3,9,9,9,9,12,12,8, 56， __ Kết quà thu được sau bước tiền xử lý là 5,3,4,9,2,12.8,56....Khi đó bát đầu ' y ' xuât hiện sự nhập nhăng: Bộ giải mã không phân biệt được có 8 điêm ảnh 56， t ^ ■» hay 8 và 56 là hai điêm ảnh. Có nhiêu phương pháp đê phân biệt sự nhập nhàng này, chẳng hạn: • f \ n - Nêu ảnh chỉ có 128 câp xám, bit đâu tiên sẽ được sử đụng đê đánh dâu hyte hiện thời là giá trị đếm hav giá trị cùa điểm ảnh. • r r - Nêu ảnh có 256 câp xám, giảm đi I câp xám, và dùng chính byte chứa giá trị 255 đổ đánh dấu byte tiếp sau là byte đếm. Xét với ví dụ trên, ta cỏ kết quả: 255,5,3,255.4,9,255,2,12,8,56.... Quá trình 2.iải mã: Quá trình giài mã RLE sẽ theo trình tự ngược lại [5.8]. r /.2.5. Move to Front Coding Phương pháp Move to Front Coding sử dụng một danh sách các thông báo. Danh sách này có dặc điểm là các thông báo có xác suất cao được xuất hiện ở phần đầu danli sách, các thông báo có xác suất thấp được xuất hiện ở cuổi danh sách. Dâv là dặc điêm quan trọng quyểt cỉịnh hiệu quả mã hóa của phương pháp này. Quá trinh mã hóa: Giả sử ta có chuôi ký tự cân mâ hóa s, Lập ra một danh sách A bao gôm các ký tự trong s và sãp xêp Iheo thứ tự Alphabet. Các kí tự trong danh sách s được mã há dựa vào thứ tự cùa chúng trong danh sách A. Ta có thể mô tả thuật toán mã hóa Move to front như sau: Lặp lại quá trình sau, với i tâng từ 0 đến n-1 : 1. Kiểm tra thứ tự của từng kí tự S j e s trong danh sách A, sinh ra từ mã ĩị là thứ tự cùa Sj trong A. 2. Chuyển kí tự Sj trong A lên đầu danh sách. Kct quá sau bước tiền xử ]ý trên là một dãy số nguycn N. Tiếp tục mã hóa N theo phương pháp Huffman, hoặc phương pháp mã hóa số học. Ví dụ: mã hóa chuỗi kí tự '*ssat tt hiies • ， ， Danh sách ban đâu: “ Quá trinh tiên xử lý diên ra như sau: ỈChuỗi kí tự mã hóa Danh sách ----------------------------------r-rì ， _ Từ mã Issat tt hiies. ’ v.'/a'/e'/h'/i'/s'/t' ịSat tt hiics . ,s’， _’’..Va’ ’ ’ 。 '#'’ '。 ’ ’ 。6 丨 at tt 6:0 ,s_， ' ,’,.,:aVeVhVi,,_t, 「 hiies . |t tt hiies . •a'/s'；V.Ve’,'hVi'， _t’ 6,0,3 !tt hiies . ’tVaVsV ,,|.'’,eVh\ĩ ịó.0,3,7 tt hiies . • VtYaVsV.VeVhVi16,0 ,3 ,7,4 ịt lìiies. _tv ,， ,a,'’s,， _.,:e’， ’h,， ,i. 6,0,3,7,4,1 't\' YaW.VeVhVi’ 16,0.3 ,7 .4, 1.0 hi ies . ịhiies . iies . 6,0,3,7,4,1,0,1 ■hv V d V /.V e V i, 6,0,3.7Ạ1.0.1,6 ics . Ị'i?hV YtVa’,’s'， V/e’ ị6.0.3,7,4,1.0,1.6,7 ； es • ~ i'i VhVVtVaVs； v/ẽ 7|6,0,3,7ÃŨ0, U 6,7^ 'sVeViVhV ' . w , ? |6A3,7,4,1,0,1.6,7,0,7,6 f V s Y e '/i'W .X V Ị6,0,3,7,4,1,0,1,6,7,0,7,6,4 i6 . 0 J , 7 . 4 , L ( U . 6 , 7 , 0 , 7 \ 6 A 7 % Ta cũng lưu ý răng，trong phương pháp MTF, khi gặp một loạt các ký tự iặp liên tiếp thì từ kí tự thử 2 trong loạt sẽ được thay thế bàng số 0 trong mã. Chẳng hạn trong ví dụ trên, “ ss” được mã hóa là 6,0; “ tt” được mã hóa là 1,0; hav “ ii” được mã hóa là 7,0. Đây cũng chính là một đặc điểm khá thú vị cùa phương pháp MTF. Quá trình giải mã: Sau khi dữ liệu được giải mã theo phương pháp Huffman * r r • hoặc giải mã sô học, kêt quả được một dãy sô nguyên N, các bước tiêp theo của giải mã Move To Front như sau: 1. Duvệt từng số nguyên íij trong dãy số nguyên N , 2. Lây ra ký tự thứ rij trong danh sách A 3. Trong danh sách A, đưa kí tự thứ rii lên đâu Ví dụ: giải mã chuồi số nguyên 6,0,3,7,4,1,0,1,6,7,0,7,6,4,7 Chuỗi cần giải mã Danh sách Kết quả 16,0,3,7.4,1,0,1,6,7.0,7,6,4,7 10.3,7,4,1.0,1,6,7,0,7,6,4,7 ,s’， , ,,V,,a, ’eVhVi,;t, s |3,7,4,1,0,K6,7,0,7,6.4,7 ’sV .’V’.a’/eVhVr’V ss 7,4,1,0,1,6,7,0,7,6,4,7 'aVsV V.VeVhVi’’ĩ ssa 4,1,0,1,6,7,0,7,6,4,7 't'/a'/s '：'：：：Q\'h'：i' ssat ịl.(U ， 6， 7.0.7.6， 4， 7 ， ssat_ 10.1,6,7,0,7,6,4,7 't'；YaVsV.'/eVhYi' ssat t 1.6,7,0.7,6.4.7 r ：Va’/sV.VeVhVi' ssat tt |6,7.0.7,6.4,7 • VtVaVs',’.’，'e W ， Y ssat tt_ p， 0,7,6’4,7 'h',' '’’t V C V e ', ? ssat tt h 18