Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh . Đồ án t t nghiệp Tìm hi u m t s ph M ng pháp nén nh Đ U Ngày nay, cùng với sự phát tri n không ngừng c a khoa học và công nghệ thì máy tính đóng vai trò ngày càng quan trọng và không th thiếu trong cu c s ng xã h i loài ng i. Việc trao đổi thông tin c a con ng i trong tất c các ngành, các lĩnh vực c a đ i s ng ngày càng tr nên cần thiết cùng với sự ra đ i và phát tri n c a m ng Internet. Xử lý nh là m t ngành khoa học còn t ng đ i mới mẻ so với nhi u ngành khoa học khác nh ng nó đang đ ợc tập trung nghiên cứu và phát tri n vì những ứng d ng thực tiễn c a nó trong nhi u ngành , lĩnh vực khác nhau. Trong đó “Nén nh” là m t phần c a xử lý nh có ứng d ng to lớn trong truy n thông và trong l u trữ, đã có rất nhi u ph ng pháp nén nh đ ợc ra đ i và không ngừng đ ợc c i tiến đ ngày càng hoàn thiện đem l i hiệu qu nén cao và cho chất l ợng nh t t nhất. Trong đồ án t t nghiệp “TÌM HI U M T S PH NH” đ ợc sự h ớng dẫn NG PHÁP NÉN c a PGS .TS . Ngô Qu c T o em đã đi sâu nghiên cứu m t s ph nén nh phổ biến nh ph ng pháp : mã lo t dài RLE, HUFFMAN, LZW, JPEG và ng pháp nén nh JPEG2000 dựa trên biến đổi Wavelet với những đặc tính v ợt tr i so với các chuẩn nén tr ớc đó đem l i hiệu qu nén cao , cho nh nén chất l ợng t t và nhi u những u đi m khác mà các chuẩn nén tr ớc đó không th có. N i dung đồ án t t nghiệp bao gồm các phần chính nh : ch giới thiệu tổng quan v xử lý nh, m c đích ch khái niệm cần biết v s ph Ch ng hai sẽ giới thiệu m t ng pháp nén nh và cách phân lo i các ph ng pháp nén nh. ng trình thử nghiệm và kết qu đ t đự c Sinh viên thực hiện : T Minh Thắng CT 702 1 ng này là giới thiệu m t s nh s và xử lý nh s . Ch ng ba sẽ giới thiệu v ch ng m t Trang : Đồ án t t nghiệp c a ch Tìm hi u m t s ph ng pháp nén nh ng trình. Cu i cùng sẽ là phần kết luận đánh giá kết qu nghiên cứu thu đ ợc và h ớng phát tri n c a đ tài. CH NG I: GI I THI U T NG QUAN V NÉN NH I.1.Gi i thi u v nh số và x lý nh số: I.1.1. nh số: nh có th bi u diễn d ới d ng tín hiệu t ng tự hoặc tín hiệu s . Trong bi u diễn s c a các nh đa mức xám, m t nh đ ợc bi u diễn d ới d ng m t ma trận hai chi u. M i phần tử c a ma trận bi u diễn cho mức xám hay c ng đ c a nh t i vị trí đó. M i phần tử trong ma trận đ ợc gọi là m t phần tử ảnh, thông th ng kí hiệu là PEL (Picture Element) hoặc là đi m nh (Pixel). - Với ảnh đa cấp xám: Nếu dùng 8 bit (1 byte) đ bi u diễn mức xám, thì s các mức xám có th bi u diễn đ ợc là 28 hay 256. M i mức xám đ ợc bi u diễn d ới d ng là m t s nguyên nằm trong kho ng từ 0 đến 255, với mức 0 bi u diễn cho mức c c ng đ đen nhất và 255 bi u diễn cho mức ng đ sáng nhất. - Với ảnh màu: Cách bi u diễn cũng t ng tự nh với nh đen trắng, chỉ khác là các s t i m i phần tử c a ma trận bi u diễn cho ba màu riêng rẽ gồm: đ (red), l c (green) và lam (blue). Đ bi u diễn cho m t đi m nh Sinh viên thực hiện : T Minh Thắng CT 702 2 Trang : Đồ án t t nghiệp Tìm hi u m t s ph ng pháp nén nh màu cần 24 bit, 24 bit này đ ợc chia thành ba kho ng 8 bit. M i kho ng này bi u diễn cho c ng đ sáng c a m t trong các màu chính. Pixel or PEL Đ sáng trung bình trong m i hình chữ nhật = giá trị m t đi m nh. Hình 1.1 Bi u diễn c a m t mức xám c a nh s . I.1.2.X lý nh số: Xử lý nh là m t khoa học mặc dù còn t ng đ i mới so với nhi u ngành khoa học khác ,nhất là trên quy mô công nghiệp. Xử lý nh s có rất nhi u ứng d ng nh làm nổi các nh trong y học, khôi ph c l i nh do tác đ ng c a khí quy n trong thiên văn học, tăng c ng đ phân gi i c a nh truy n hình mà không cần thay đổi cấu trúc bên trong c a hệ th ng chuy n t i, nén nh trong khi truy n đi xa hoặc l u trữ. Các giai đo n chính trong xử lý nh có th đ ợc mô t trong hình sau: L u CAMERA Thu nhận nh S Phân tích nh Nhận d ng SENSOR Sinh viên thực hiện : T Minh Thắng CT 702 3 L u trữ Hệ quyết định Trang : Đồ án t t nghiệp Tìm hi u m t s ph ng pháp nén nh I.2.Mục đích và sự c n thi t của “ nén nh ”: Nén nh là m t kỹ thuật mã hoá các nh s hoá nhằm gi m s l ợng các bit dữ liệu cần thiết đ bi u diễn nh. M c đích là gi m đi những chi phí trong việc l u trữ nh và chi phí th i gian đ truy n nh đi xa trong truy n thông nh ng vẫn đ m b o đ ợc chất l ợng c a nh. Nén nh thực hiện đ ợc là do m t thực tế: thông tin trong bức nh không ph i là ngẫu nhiên mà có trật tự , 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 phần thông tin nào quan trọng nhất trong bức nh đ bi u diễn và truy n đi với s l ợng ít bit h n so với nh g c mà vẫn đ m b o tính đầy đ c a thông tin. bên nhận quá trình gi i mã sẽ tổ chức, sắp xếp l i đ ợc bức nh xấp xỉ gần chính xác so với nh g c nh ng vẫn th a mãn chất l ợng yêu cầu. D ới đây là ví d v l u trữ nh s và truy n đi xa với đ ng truy n 9600 baud (9600 bps) đ thấy rõ sự cần thiết c a việc nén nh: • nh đa cấp xám hay nh 256 màu có kích th ớc 800 x 600, 8 bit/đi m nh, cần 3.840.000 bit l u trữ và mất 6.67 phút đ truy n. • nh màu RGB (24 bit/đi m nh ) cùng đ phân gi i nh vậy cần h n 10 triệu bit đ l u trữ và 20 phút đ truy n. • M t phim âm b n có kích th ớc 24 × 36 mm (35 mm) chia bằng các kho ng cách nhau 12 àm, vào kho ng 3000 × 2000 đi m, 8 bit / pixel, yêu cầu 48 triệu bit cho l u giữ nh và 83 phút đ truy n. Qua ví d trên ta thấy nhi u vấn đ trong việc l u trữ và truy n t i nh s hoá. Nén nh có nhi u ứng d ng trong thực tế nh : truy n các văn b n Sinh viên thực hiện : T Minh Thắng CT 702 4 Trang : Đồ án t t nghiệp đồ ho qua đ Tìm hi u m t s ph ng pháp nén nh ng điện tho i (Fax), nén nh trong y tế và truy n hình cáp….Chính sự ứng d ng trong nhi u lĩnh vực c a nén nh cùng với sự tiến b trong lĩnh vực vi điện tử dẫn đến sự ra đ i các chuẩn nén nh. Nén nh đ t đ ợc bằng cách lo i b các phần d thừa trong nh đã đ ợc s hoá. D thừa có th là d thừa thông tin v không gian, d thừa v cấp xám hay d thừa v th i gian: • D thừa thông tin v không gian : trong m t bức nh luôn tồn t i sự t ng quan giữa các đi m nh c nh nhau. • D thừa thông tin v cấp xám :là d thừa dựa vào sự t ng quan giữa các màu sắc c nh nhau. • 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 frame khác nhau . I.3.Các khái ni m c b n: • Pixel (picture element) : phần tử nh nh trong thực tế là m t nh liên t c v không gian và v giá trị đ sáng. Đ có th xử lý nh bằng máy tính cần thiết ph i tiến hành s hoá nh. Nh vậy m t nh là m t tập hợp các pixel. M i pixel là gồm m t cặp to đ x, y và màu. Cặp to đ x,y t o nên đ phân gi i (resolution). Màn hình máy tính có nhi u lo i với đ phân gi i khác nhau: 320 x 200, 640x350, 800x600, 1024x768,… • Mức xám (Graylevel) Mức xám là kết qu sự mã hoá t ng ứng c a m i c ng đ sáng c a m i đi m nh với m t giá trị s – kết qu c a quá trình l ợng hoá . • Dữ liệu Sinh viên thực hiện : T Minh Thắng CT 702 5 Trang : Đồ án t t nghiệp Tìm hi u m t s ph ng pháp nén nh Trong m t bài toán, dữ liệu bao gồm m t tập các phần tử c s mà ta gọi là dữ liệu nguyên tử. Nó có th là m t chữ s , m t ký tự, ... nh ng cũng có th là m t con s , m t từ, ... đi u đó ph thu c vào từng bài toán. • Nén dữ liệu Nén dữ liệu là qu trình gi m dung l ợng thông tin “d thừa” trong dữ liệu g c và làm cho l ợng thông tin thu đ ợc sau nén th ng nh h n dữ liệu g c rất nhi u. Do vậy, tiết kiệm đ ợc b nhớ và gi m th i gian trao đổi dữ liệu trên m ng thông tin mà l i cho phép chúng ta khôi ph c l i dữ liệu ban đầu. • Tỷ lệ nén Tỷ lệ nén là m t trong các đặc tr ng quan trọng c a mọi ph ng pháp nén. Tỷ lệ nén đ ợc định nghĩa nh sau: Tỷ lệ nén = 1/r*% với r là tỷ s nén đ ợc định nghĩa: r = kích th c dữ li u gốc / kích th c dữ li u nén. Nh vậy hiệu suất nén = (1- tỷ lệ nén)*100%. Đ i v i nh tĩnh, kích th Đ i với nh video, kích th c chính là s bit bi u diễn toàn b bức nh. c chính là s bit đ bi u diễn m t khung hình video (video frame). Sinh viên thực hiện : T Minh Thắng CT 702 6 Trang : Đồ án t t nghiệp Tìm hi u m t s ph CH CÁC PH ng pháp nén nh NG II: NG PHÁP NÉN NH II.1.Cách phân lo i các ph ng pháp nén nh: II.1.1.Cách phân lo i dựa vào nguyên lý nén: Nén b o toàn thông tin (losses compression): bao gồm các ph ng pháp nén mà sau khi gi i nén sẽ thu đự c chính xác dữ liệu g c.Tuy nhiên nén b o toàn thông tin chỉ đ t hiệu qu nh so với ph ng pháp nén không b o toàn thông tin. Nén không b o toàn thông tin (lossy compression): bao gồm các ph ng pháp nén sau khi gi i nén sẽ không thu đ ợc dữ liệu nh b n g c. Các ph ng pháp này đ ợc gọi là “tâm lý thị giác” đó là 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 l i.Ph ng pháp này luôn đem l i hiệu qu cao do lo i b đi những thông tin d thừa không cần thiết. II.1.2.Cách phân lo i dựa vào cách thức thực hi n nén: Sinh viên thực hiện : T Minh Thắng CT 702 7 Trang : Đồ án t t nghiệp Ph Tìm hi u m t s ph ng pháp nén nh ng pháp không gian (Spatial Data Compression ): các ph ng pháp này thực hiện nén bằng cách 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 chứ không tác đ ng trực tiếp. II.1.3.Cách phân lo i dựa vào lý thuy t mã hoá: Các phương pháp nén thế hệ thứ nhất: gồm các ph ng pháp có mức đ tính toán đ n gi n nh lấy mẫu , gán từ mã,…. Các phương pháp nén thế hệ thứ hai: gồm các ph ng pháp dựa vào mức đ bão hoà c a tỷ lệ nén bằng cách sử d ng các phép toán tổ hợp đầu ra m t cách hợp lý hoặc sử d ng bi u diễn nh nh : ph tháp Laplace, ph ng pháp dựa vào vùng gia tăng, ph ng pháp kim tự ng pháp tách hợp. II.1.4.Quá trình nén và gi i nén : Gồm 2 công đo n : Nén : dữ liệu g c qua b mã hoá dữ liệu , b mã hoá này thực hiện nén dữ liệu đến m t mức thích hợp cho việc l u trữ và truy n dẫn thông tin. Quá trình này sẽ thực hiện việc lo i b hay cắt bớt những d thừa c a nh đ thu đ ợc thông tin cần thiết nh ng vẫn đ m b o đ ợc chất l ợng nh. Gi i nén : dữ liệu nén đi qua b gi i mã dữ liệu, b gi i mã sẽ thực hiện gi i nén đ thu đ ợc dữ liệu g c ban đầu.Việc gi i nén này th ng ph i dựa vào các thông tin đi kém theo dữ liệu nén ,tuỳ thu c vào ki u nén hay ph ng pháp nén mà dữ liệu gi i nén đ ợc có hoàn toàn gi ng với dữ liệu g c ban đầu hay không. Sinh viên thực hiện : T Minh Thắng CT 702 8 Trang : Đồ án t t nghiệp Tìm hi u m t s ph ng pháp nén nh Tóm l i quá trình nén và gi i nén dữ liệu có th mô t m t cách tóm tắt theo s đồ d ới đây: Quá trình nén Dữ liệu Dữ liệu Quá trình gi i nén Hình 2.1 : Quá trình nén và gi i nén II.2.Ph ng pháp mã hoá đ dài lo t RLE: Mã hoá theo đ dài lo t RLE (Run Length Encoding) 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 đ i với 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ị. II.2.1.Nguyên tắc : Nguyên tắc c a ph ng pháp này là phát hiện m t lo t các đi m nh lặp l i liên tiếp, ví d :110000000000000011 .Ta thấy đi m nh có giá trị 0 xuất hiện nhi u lần liên tiếp thay vì ph i l u trữ toàn b các đi m nh có giá trị 0 ta chỉ cần l u trữ chúng bằng cách sử d ng các cặp (đ dài lo t, giá trị). 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 : (10 5) (5 19) (7 0) (8 23) Tỷ s nén = 20/ 8 = 2.5 Sinh viên thực hiện : T Minh Thắng CT 702 9 Trang : Đồ án t t nghiệp Tìm hi u m t s ph ng pháp nén nh Đ i với nh đen trắng chỉ sử d ng 1 bit đ bi u diễn 1 đi m nh thì ng pháp này t ra rất hiệu qu , ta thấy đi u đó qua ví d sau : ph Cho m t chu i nguồn d: 000000000000000111111111100000000001111111111000000000000000 Ta có chu i mới : (15, 10, 10, 10, 15) Tỷ s nén = 60 bit / (5*4 bit) = 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 là 1) Chú ý: • Đ i với nh chi u dài c a m t dãy lặp có th lớn h n 255, nếu ta dùng 1 byte đ l u trữ chi u dài thì sẽ 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 là 255, chu i kia có chi u dài còn l i. • Ph ng pháp nén RLE chỉ đ t hiệu qu khi chu i lặp lớn h n 1 ng ỡng nhất định nào đó hay nói các 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ững 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ã hoá : 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.2 Sinh viên thực hiện : T Minh Thắng CT 702 10 Trang : Đồ án t t nghiệp Tìm hi u m t s ph ng pháp nén nh Nh vậy chu i sau khi mã hoá đã 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ã hoá đ dài lo t dữ liệu lặp i ta đã đ a ra cách đó là thêm kí tự ti n t vào tr ớc đ dài lo t, l i. Ng 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ó : 5 8 4 +7 8 + 9 10 Tỷ s nén = 19 / 9 = 2.1 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 có 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 -3 5 5 5 5 5 5 5 5 5 Áp d ng ph ng pháp nén lo t dài ta dễ dàng thu đ ợc : (5 1)( 2 4)(5 1)(10 5)(-3 1)(5 9) II.2.2.Thu t toán: Thuật toán nh sau : Sinh viên thực hiện : T Minh Thắng CT 702 11 Trang : Đồ án t t nghiệp Tìm hi u m t s ph ng pháp nén nh • Tiến hành duyệt trên từng hàng cho đến khi kết thúc vùng dữ liệu nh, trong quá trình duyệt tiến hành ki m tra đ tìm ra những lo t có cùng giá trị đồng th i chú ý những kí hiệu xu ng dòng (hay kết thúc dòng) ,kết thúc nh Bitmap, … • Khi gặp lo t có đ dài > 3 thì nh y đến chế đ nén ng ợc l i nh y đến chế đ không nén tuy nhiên nếu lo t > 255 thì sẽ tách ra chỉ mã < 255 sau đó mã tiếp phần còn l i. Ngoài ra còn các chế đ khác nh : bắt đầu , kết thúc 1 dòng. • Kết thúc khi gặp kí hiệu kết thúc bitmap ( end – o f- bitmap) II.2.3.M t số thủ tục ch • Ch ng trình : ng trình nén theo ph ng pháp RLE : void CRLE::CompressInRLE8(BYTE*pSrcBits,CByteArray& pRLEBits, int& RLE_size) { int line; int src_index = 0, dst_index = 0, counter, i; for ( line = 0; line < m_dib.dsBmih.biHeight; line++) { state_start: if ( EndOfLine(src_index)) { pRLEBits[dst_index++] = 1; pRLEBits[dst_index++] = pSrcBits[src_index]; src_index++; goto end_of_line; } Sinh viên thực hiện : T Minh Thắng CT 702 12 Trang : Đồ án t t nghiệp Tìm hi u m t s ph ng pháp nén nh if(pSrcBits[src_index]==pSrcBits[src_index+1]) goto tate_compress; if ( EndOfLine(src_index+1)) { pRLEBits[dst_index++] = 1; pRLEBits[dst_index++] = pSrcBits[src_index++]; pRLEBits[dst_index++] = 1; pRLEBits[dst_index++] = pSrcBits[src_index++]; goto end_of_line; } if (pSrcBits[src_index+1] == pSrcBits[src_index+2]) { pRLEBits[dst_index++] = 1; pRLEBits[dst_index++] = pSrcBits[src_index++]; goto state_compress; } else goto state_no_compress; state_compress: for ( counter = 1; counter <= 254; counter++) { if ( pSrcBits[src_index+counter] != pSrcBits[src_index] ) break; if ( EndOfLine(src_index+counter) ) { pRLEBits[dst_index++] = counter+1; pRLEBits[dst_index++] = pSrcBits[src_index]; src_index += counter +1; goto end_of_line; } Sinh viên thực hiện : T Minh Thắng CT 702 13 Trang : Đồ án t t nghiệp Tìm hi u m t s ph ng pháp nén nh } pRLEBits[dst_index++] = counter; pRLEBits[dst_index++] = pSrcBits[src_index]; src_index += counter; goto state_start; state_no_compress: for (counter = 2; counter <= 254; counter++) { if ( EndOfLine(src_index+counter) ) { pRLEBits[dst_index++] = 0; pRLEBits[dst_index++] = counter + 1; for (i = counter + 1; i > 0; i--) pRLEBits[dst_index++]=pSrcBits[src_index++]; if ( 0 != ((counter+1) % 2) ) pRLEBits[dst_index++]; goto end_of_line; } if(EndOfLine(src_index+counter+1) || pSrcBits[src_index+counter] != pSrcBits[src_index+counter+1] ) continue; if(EndOfLine(src_index+counter+2) || SrcBits[src_index+counter+1] != pSrcBits[src_index+counter+2] ) continue; else { if ( counter > 2) counter--; pRLEBits[dst_index++] = 0; pRLEBits[dst_index++] = counter+1; for (i = counter+1; i > 0; i--) pRLEBits[dst_index++] = pSrcBits[src_index++]; Sinh viên thực hiện : T Minh Thắng CT 702 14 Trang : Đồ án t t nghiệp Tìm hi u m t s ph ng pháp nén nh if ( 0 != ((counter+1) % 2) ) pRLEBits[dst_index++]; goto state_compress; } } pRLEBits[dst_index++] = 0; pRLEBits[dst_index++] = counter; for (i = counter; i > 0; i--) pRLEBits[dst_index++] = pSrcBits[src_index++]; if ( 0 != ((counter) % 2) ) pRLEBits[dst_index++]; goto state_start; end_of_line: if ( 0 != (src_index % 4 )) { int pad = 4 - (src_index%4); src_index += pad; } pRLEBits[dst_index++] = 0; pRLEBits[dst_index++] = 0; } pRLEBits[dst_index++] = 0; pRLEBits[dst_index++] = 1; RLE_size = dst_index; } • Ch ng trình gi i nén ph ng pháp RLE : BOOL CRLE::DecRLE8(ifstream &fil, BYTE *pDest) { DWORD x, y, paddedwidth; Sinh viên thực hiện : T Minh Thắng CT 702 15 Trang : Đồ án t t nghiệp Tìm hi u m t s ph ng pháp nén nh paddedwidth =BMPWIDTHBYTES(pInfo->biWidth*pInfo-> biBitCount); BYTE FirstByte, SecondByte; WORD data; x = y = 0; while (!fil.eof()) { if (!fil.read((char*)&data, 2)) return FALSE; FirstByte = LOBYTE(data); SecondByte = HIBYTE(data); if (FirstByte == 0) { switch (SecondByte) { case 0: x = 0; y++; break; case 1: return TRUE; case 2: if (!fil.read((char*)&data, 2)) return FALSE; x += LOBYTE(data); y += HIBYTE(data); break; default: char ch; for (BYTE i = 0; i < SecondByte; i++) { if (!fil.get(ch)) return FALSE; pDest[paddedwidth * y + x++] = (BYTE)ch; Sinh viên thực hiện : T Minh Thắng CT 702 16 Trang : Đồ án t t nghiệp Tìm hi u m t s ph ng pháp nén nh } if ((SecondByte % 2) == 1) if (!fil.get(ch)) return FALSE; } } else { for (BYTE i = 0; i < FirstByte; i++) pDest[paddedwidth * y + x++] = SecondByte; } } return FALSE; } II.3.Ph ng pháp mã hoá Huffman: II.3.1. Nguyên tắc: Ph kê. Ng ng pháp mã hoá Huffman là ph ng pháp dựa vào mô hình th ng i ta tính tần suất xuất hiện c a các ký tự bằng cách duyệt tuần tự từ đầu tệp g c đến cu i tệp. Việc xử lý đây tính theo bit. Trong ph Sinh viên thực hiện : T Minh Thắng CT 702 17 ng pháp Trang : Đồ án t t nghiệp Tìm hi u m t s ph ng pháp nén nh này 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. Nh vậy với cách thức này ta đã làm gi m chi u dài trung bình c a từ mã hoá bằng cách dùng chi u dài biến đổi tuy nhiên cũng có tr ng hợp bị thiệt 1 ít bit khi tần suất là rất thấp. II.3.2. Thu t toán: • Thu t toán mã hoá Huffman g m 2 b c chính: • Bước một: Tính tần suất c a các ký tự trong dữ liệu g c bằng cách 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ã và tính toán tần suất. Tiếp theo sau là sắp xếp l i b ng mã theo thứ tự tần suất gi m dần. • Bước hai: Duyệt b ng tấn suất từ cu i lên đầu đ thực hiện ghép hai phần tử có tần suất thấp thành m t phần tử duy nhất có tần suất bằng tổng hai tần suất thành phần. Cập nhật phần tử này vào vị trí phù hợp trong b ng và lo i b hai phần tử đã xét. Thực hiện cho đến khi b ng chỉ có m t phần tử. Đây là quá trình t o cây nhị phân Huffman ,phần tử có tần suất thấp phần tử kia bên trái. Sau khi cây đã t o xong ng bên ph i, i ta tiến hành gán mã cho các nút lá. Việc mã hoá thực hiện theo quy định : m i lần xu ng bên ph i ta thêm m t bit ‘1’ vào từ mã, m i lần xu ng bên trái ta thêm m t bit ‘0’ vào từ mã. Quá trình gi i nén cũng khá đ n gi n đ ợc tiến hành theo chi u ng ợc l i. Ng i ta cũng ph i dựa vào b ng mã t o ra trong giai đo n nén (b ng này đ ợc l u trữ trong cấu trúc đầu c a tệp nén cùng với dữ liệu nén). Ví dụ: M t tệp bất kỳ có tần suất xuất hiện c a các kí tự s nh Ký tự Tần suất 0 1532 Sinh viên thực hiện : T Minh Thắng CT 702 18 b ng sau. Trang : Đồ án t t nghiệp Tìm hi u m t s ph 1 152 2 323 3 412 4 226 5 385 6 602 7 92 8 112 9 87 ng pháp nén nh Bảng tần suất sắp xếp giảm dần 0 6 3 5 2 4 1 8 7 9 0.3905 0.1535 0.1051 0.0982 0.0824 0.0577 0.0388 Kí tự Xác suất (%) 0 0.3906 6 0.1535 3 0.1051 5 0.0982 2 0.0824 4 0.0577 1 0.0388 8 0.0286 7 0.0235 9 0.0222 0.3905 0.3905 0.1535 0.1051 0.0982 0.0824 0.1535 0.1051 0.0982 0.0824 0.0577 0.0457 0.0388 0.0674 0.0577 0.3906 0.1535 0.1051 0.1034 0.3905 0.3905 0.3905 0.3905 0.6100 0.1535 0.1498 0.2016 0.1535 0.1498 0.1051 0.2549 0.2016 0.1535 0.3551 0.2549 0.3905 0.0982 0.1051 0.1034 0.0824 0.0982 0.0674 0.0286 0.0457 Sinh viên thực hiện : T Minh Thắng CT 702 0.0235 19 0.0222 0.0286 Trang :