Tăng tốc độ giải thuật mã hóa Huffman cho nén ảnh số bằng GPU

Trong bài viết này, tác giả đưa ra phương pháp cải tiến giải thuật Huffman áp dụng trong nén ảnh có độ phân giải cao bằng cách chia ảnh thành các khối con để có thể thực hiện mã hóa song song trên các lõi của GPU.
Nội dung trích xuất từ tài liệu:
Tăng tốc độ giải thuật mã hóa Huffman cho nén ảnh số bằng GPU Điều khiển – Cơ điện tử - Truyền thông<br /> <br /> TĂNG TỐC ĐỘ GIẢI THUẬT MÃ HÓA HUFFMAN<br /> CHO NÉN ẢNH SỐ BẰNG GPU<br /> Đào Huy Du*<br /> Tóm tắt: Trong các phương pháp nén đặc biệt là các phương pháp nén không<br /> tổn hao nếu muốn kết quả nén đạt tỷ lệ nén cao đồng nghĩa với việc thời gian nén sẽ<br /> cao. Giải thuật mã hóa Huffman là một giải thuật mã hóa không mất mát thông tin<br /> được áp dụng vào việc nén các đối tượng (văn bản, hình ảnh,…) cần độ chính xác<br /> cao, tuy nhiên giải thuật này cần một khoảng thời gian khá lớn để thực thi các thao<br /> tác mã hóa. Trong bài báo này, tác giả đưa ra phương pháp cải tiến giải thuật<br /> Huffman áp dụng trong nén ảnh có độ phân giải cao bằng cách chia ảnh thành các<br /> khối con để có thể thực hiện mã hóa song song trên các lõi của GPU. Việc thực thi<br /> giải thuật đề xuất này được thực thi trên GPU của NVIDIA kết hợp với các thư viện<br /> hỗ trợ xử lý song song của MatLab, đồng thời, đưa ra kết quả để so sánh hiệu suất<br /> giữa việc mã hóa có sử dụng và không sử dụng GPU.<br /> Từ khóa: Paralell Computing, GPU, Huffman, Paralell Coding.<br /> <br /> 1. ĐẶT VẤN ĐỀ<br /> Với mục đích cắt giảm chi phí trong việc lưu trữ ảnh và thời gian để truyền ảnh đi xa<br /> nhưng vẫn đảm bảo chất lượng của ảnh, nén ảnh là một trong những bước quan trọng nhất<br /> trong quá trình truyền thông và lưu trữ.<br /> Nén ảnh được áp dụng rất rộng rãi trong thực tế như: truyền các văn bản dưới dạng đồ<br /> họa, nén ảnh trong y tế, các ảnh dữ liệu chụp từ vệ tinh v.v... Nén ảnh là kỹ thuật được sử<br /> dụng để làm giảm kích thước của ảnh bằng cách loại bỏ một số thành phần dư thừa trong<br /> ảnh hay thay thế các thành phần trong ảnh bằng một thành phần khác nhằm làm giảm kích<br /> thước ảnh. Phương pháp cắt giảm các thông tin dư thừa trong dữ liệu gốc và làm cho dữ<br /> liệu sau nén nhỏ hơn rất nhiều so với dữ liệu gốc được gọi là phương pháp nén mất mát<br /> thông tin. Ngược lại, phương pháp nén mà sau khi giải nén thu được chính xác dữ liệu gốc<br /> gọi là phương pháp nén không mất mát thông tin [1].<br /> Một số ảnh cần độ chính xác cao thường phải áp dụng kỹ thuật mã hóa không mất mát<br /> thông tin để truyền thông hoặc lưu trữ. Ví dụ trong lĩnh vực y tế, đối với kỹ thuật chụp<br /> CT-Scanner thì mỗi lát cắt của hình ảnh có thế lên đến 150MB hoặc cao hơn, vì vậy, một<br /> tập dữ liệu đầy đủ cho một chẩn đoán trung bình có thể từ 200MB đến 400MB [2]. Với<br /> những dữ liệu ảnh như vậy, độ phân giải sẽ rất lớn và cần nhiều dung lượng lưu trữ và đặc<br /> biệt chi phí cho thời gian nén và giải nén sẽ cao.<br /> Giải thuật mã hóa Huffman được sử dụng rộng rãi trong các ứng dụng liên quan đến<br /> truyền thông, các ứng dụng nén dữ liệu ảnh và video [3] [4], giải thuật này đặc biệt phù<br /> hợp với những tập dữ liệu lớn nhưng có số lượng các đối tượng xuất hiện trong đó là ít.<br /> Giải thuật mã hóa Huffman gồm có 2 bước chính: Bước thứ nhất, dữ liệu ảnh đầu vào<br /> được xử lý để tạo ra cây nhị phân và bảng từ mã; Bước thứ 2, mỗi mức xám trong dữ liệu<br /> đầu vào được so sánh với bảng từ mã để tạo ra luồng bit nhị phân. Trong bước thứ 2, đây<br /> là giai đoạn chiếm nhiều thời gian nhất trong các giai đoạn nén Huffman do việc phải đi so<br /> sánh từng phần tử trong tập dữ liệu với bảng từ mã để tạo ra chuỗi dữ liệu mã hóa.<br /> Cho dù việc mã hóa Huffman song song là một vấn đề khá phức tạp, song đã có nhiều<br /> công trình tập trung nghiên cứu như: tác giả P. Berman, M. Karpinski và Y. Nekrich [5] đã<br /> nghiên cứu việc sử dụng n bộ xử lý để tạo ra bảng từ mã song song, nhưng chưa đề cập<br /> đến vấn đề mã hóa song song. Trong [6], tác giả trình bày phương pháp giải mã song song<br /> mà có một bị lỗi trong quá trình truyền từ tập dữ liệu mã hóa. Trong [7], tác giả đề cập đến<br /> <br /> <br /> 80 Đào Huy Du, “Tăng tốc độ giải thuật mã hóa Huffman cho nén ảnh số bằng GPU.”<br /> Nghiên cứu khoa học công nghệ<br /> ảnh hưởng của các kiến trúc phần cứng khác nhau đến việc mã hóa Huffman theo phương<br /> pháp động. Các kỹ thuật nén JPEG và MPEG cũng áp dụng phương pháp mã hóa Huffman<br /> để làm tăng tốc độ nén [8] [9] [10] [11].<br /> Với sự ra đời và phát triển nhanh chóng của bộ xử lý đồ họa GPU (Graphics Processing<br /> Unit) cùng với Kiến trúc thiết bị tính toán hợp nhất CUDA (Compute Unified Device<br /> Architecture ) của NVIDIA với mô hình xử lý SIMD (Single Instruction Multi Data),<br /> nhiều nhà nghiên cứu cũng đã tập trung giải quyết các bài toán xử lý dữ liệu trên GPU.<br /> Trong [12], tác giả đã sử dụng GPU để song song hóa giải thuật mã hóa theo độ dài và đã<br /> đạt được tốc độ xử lý cao bằng cách giới hạn cho độ dài từ mã; Trong [13], tác giả đã thay<br /> đổi giải thuật Huffman để tạo ra khối dữ liệu nén và giải nén hoàn toàn độc lập với nhau<br /> và làm tăng tốc độ lên gấp 3 lần so với mã hóa Huffman tuần tự.<br /> Trong nghiên cứu này, chúng tôi thực hiện việc mã hóa ảnh mầu có độ phân giải cao<br /> sử dụng giải thuật Huffman bằng cách tạo ra các ma trận mầu sau đó chia các ma trận<br /> này thành các khối con để đưa vào thực hiện trên từng lõi của GPU. Kết quả kiểm<br /> nghiệm cho thấy tốc độ mã hóa và giải mã tăng khoảng 5 lần so với thực hiện giải thuật<br /> Huffman tuần tự.<br ...