Đặt vấn đề Trong nhiều thập kỷ, việc triển khai công nghệ thông tin (CNTT) trở nên ngày càng phô biến, tương đương với việc dữ liệu cần được lưu trữ ngày càng lớn, tạo ra thách thức lớn trong việc lưu trữ dữ liệu. Việc sử dụng dung lượng lưu trữ lớn có thé giải quyết van đề kích thước của tệp. Tuy nhiên, phương pháp này tốn kém về mặt chỉ phí cho cả dung lượng và băng thông. Một phương pháp khả thi là nén dữ liệu, phương pháp này giúp làm giảm đáng ké kích thước của tệp.
Với sự phát triển của CNTT, năng lực tính toán ngày càng cao, việc nén đữ liệu ngày càng trở nên rộng rãi trong nhiều lĩnh vực như broadcast television, aircraft, computer transmission, medical imaging. Đối với những lĩnh vực yêu cầu về độ chính xác cao trong việc truyền nhận dữ liệu. Dữ liệu trong quá trình nén không bị mất mát so với dữ liệu ban đầu. Trên thực tế, chúng ta cần biết dữ liệu nào sẽ được nén trước khi tiễn hành việc nén.
Dé giải quyết vấn đề này, nhóm đã tìm hiểu và nghiên cứu đến phương pháp nén ảnh không mat mát thời gian thực, nhăm hướng tới việc phát triển một phương pháp nén được ứng dụng trong việc truyền video trực tuyến, chúng ta không thé biết trước chính xác những gì sẽ được truyền nhưng vẫn đảm độ chính xác cao và giảm tài nguyên lưu trữ dữ liệu. Nén ảnh là một mảng nghiên cứu quan trọng trong lĩnh vực nén dữ liệu. Ngày nay, với sự phát triển của các nền tảng mảng xã hội, kích thước dữ liệu hình ảnh và video cũng ngày càng tăng lên. Do đó, nén ảnh và video đang được nghiên cứu va phat trién rộng rãi vi những ứng dụng thực tế mà nó mang lại [1].
Phân loại nén ảnh Hình 1. So sánh sự khác nhau giữa phương pháp nén lossless va lossy Các phương pháp nén ảnh được chia làm hai loại [2]: nén mat mát - Lossless compression và nén không mat mát - Lossy compression. Cả hai phương pháp nén đêu có ưu nhược điêm khác nhau và được ứng dụng thực tê trong nhiêu lĩnh vực. Phương pháp nén ảnh không mat mát — lossless compression Nén ảnh không mắt mát là một nhóm các thuật toán nén dit liệu cho phép dữ liệu gốc được xây dựng lại chính xác hoàn toàn từ dữ liệu nén.
Phương pháp này không làm giảm chất lượng hình ảnh và được ứng dụng trong một số lĩnh vực yêu cầu độ chính xác cao như hình ảnh y té, anh ban vé kỹ thuật,. Nén không mat mát rất quan trọng trong các ảnh về y tế bởi các công việc liên quan đến khám chữa bệnh không được có bất kỳ thiếu sót nào trong ảnh sau khi được giải nén. Các phương pháp nén ảnh không mat mát chủ yếu dựa trên một số thuật toán: Lempel-Ziv-Welch (LZW) [3], Shanno-Fano coding [4] , Huffman coding [5]. Các giải thuật này dự đoán pixel theo ngữ cảnh xung quanh nó, và mã hóa các độ lỗi dự đoán với kỹ thuật entropy.
Phương pháp nén ảnh mắt mát — lossy compression Nén ảnh mất mát là phương pháp nén loại bỏ phần không hữu ích của dữ liệu. Trong quá trình nén, việc xây dựng lại một hình ảnh chỉ gần đúng với dữ liệu ban dau, có thé thay một lượng dir liệu bị mat đi rất nhỏ như trong Hình 2. Input Restored Image Image Compressed Image Hình 1. Mô tả dữ liệu bi mat trong phương pháp nén lossy compression Nén mắt mát được sử dụng rộng rãi trong việc nén các hình ảnh tự nhiên như ảnh chụp, trong đó tôn thất không đáng kê về độ chính xác dé giảm chi phí lưu trữ.
Một số thuật toán sử dụng phương pháp nén mat mát phố biến là: DCT (Discrete cosine transform) [6], Wavelet transform [7], JPEG 2000 [8]. Các thuật toán này làm giảm kích thước ảnh một cách đáng kể. Tuy nhiên, các hệ thống thiết kế thường lớn và tốn nhiều năng lượng. Hầu hết các thuật toán nén mất mát đữ liệu đều dựa trên mã hóa chuyên đôi.
Một số ứng dụng phô biến của phương pháp nén ảnh mat mát là ảnh JPEG, MPEG videos, MP3 audio. Giới thiệu một số phương pháp nén Các thuật toán nén ảnh được giới thiệu đưới đây đều được phát triển dựa trên phương pháp nén ảnh không mắt mát. Lempel-Ziv-Welch (LZW) LZW là thuật toán nén dựa trên từ điển có thé là tĩnh hoặc động. Đối với mã hóa tĩnh, từ điển được có định trong quá trình mã hóa và giải mã.
Trong mã hóa động, từ điển được cập nhật. LZW được sử dụng rộng rãi trong ngành công nghiệp máy tính và được triển khai như là một lệnh nén trên UNIX [9]. LZW phù hợp với dữ liệu mang nội dung lặp đi lặp lại nhiều lần. Dữ liệu lặp lại được thay thế bằng vị trí và độ dài của chuỗi con hiện có.
Tuy nhiên, phương pháp này sẽ mat nhiều thời gian nếu dit liệu lớn và không liên tục. Shanno-Fano Coding Shanno-Fano Coding là thuật toán nén không mất mát được đặt tên theo nhà toán học Claude Shannon và Robert Fano. Phương pháp nay gan dữ liệu cho một symbol với xác suất được sắp xếp giảm dần. Các mã Shanon được coi là chính xác nếu mã của mỗi symbol là duy nhất.
Nhưng đôi khi, thuật toán này không thể tạo ra dữ liệu một cách hoàn hảo và có tỉ lệ nén thấp. Bởi vì phương pháp này không thé tạo ra một cây nhị phân tối ưu. Thuật toán Huffman Coding giải quyết được những thiếu sót này [5]. Huffman Coding Huffman coding là thuật toán được sử dung phổ biến để loại bỏ dư thừa mã hóa.
Thuật toán nay xử lý nén dir liệu các ký tự ASCII. Nó xây dựng một cây nhị phân day đủ cho các biểu tượng khác nhau sau khi tính toán xác suất của từng biểu tượng và đặt nó theo thứ tự giảm dần. Điều này trái ngược với Shannon-Fano. Huffman coding là thuật toán xác định trước dt liệu đầu vào.
Trong một số ứng dụng thực tê liên quan đên truyên dữ liệu realtime, việc ước tính và sử dụng các bảng mã Huffman riêng biệt cho từng anh và chuỗi hình ảnh không chỉ tốn thời gian mà còn tốn chi phí truyền bang. Các khái niệm cơ bản 1. Phan tử ảnh — pixel Pixel là thành phần cơ bản nhất có thể có của bất kỳ hình ảnh điện tử hoặc kỹ thuật số nào. Một tập hợp các pixel tạo thành một hình anh, video, văn bản hoàn chỉnh hoặc bat kỳ thứ gì có thé thấy trên màn hình máy tính.
Mỗi pixel có một cặp tọa độ x, y và đặc trưng cường độ sáng trong không gian ảnh. Tùy thuộc vào card đồ hoa và màn hình hiển thị, sự kết hợp màu sắc giữa các điểm ảnh sẽ khác nhau và được đo bằng độ phân giải màn hình. Ví dụ máy tính có độ phân giải 1280 x 768 sẽ tạo ra tôi đa 983,040 pIxel. Mức xám — Gray level Mức xám là kết quả của sự mã hóa tương ứng một cường độ sáng của mỗi điểm ảnh với một giá trị sô.
Thường dùng 8 bit để mã hóa 256 mức xám.3 mô tả các mức xám được tham chiếu với từng độ rộng bit khác nhau. Bit Depth and Gray Levels in Digital Images 2Bit 4Bit 6 Bit 7 Bit 8Bit 10 Bit 4 16 64 128 266 1,024 Gray Levels —=——————————x Hình 1. Mô tả số lượng bit biéu diễn các mức xám 1. Histogram Histogram của ảnh là một cách biểu diễn (bằng hình ảnh) về sự phân bố cường độ sáng của ảnh.
Trong histogram của Hình 3, trục ngang biểu thị dãy giá trị của cường độ sáng (thường là số nguyên từ 0 đến 255) và trục dọc biểu thị cho số pixel có giá trị cường độ sáng ứng với trục ngang. Dựa vào histogram, nhóm có thể đánh giá được độ phức tạp của một bức ảnh. Bức ảnh có độ phức tạp cao là bức ảnh có phân bố cường độ sáng trải đều từ 0 đến 255. Biểu đồ histogram biểu thị cường độ sáng của một bức ảnh 1.
Ty lệ nén - Compression ratio (CR) Tỷ lệ nén là phép đo mức giảm tương đối về kích thước biéu diễn dit liệu do thuật toán nén tạo ra. Tỉ lệ nén được định nghĩa là tỷ lệ giữa kích thước trước khi nén và kích thước sau khi nén : 2 TA 7 Kích thước ban đầu Tỷ lệ nến= ——————————— (1 Kích thước sau nén Như vậy, hiệu suất nén được tính theo công thức : Kích thước sau nén Hiệu suất = 1 - lệu suat Kích thước ban đầu (2) 1. Bits per pixel (BPP) Ty lệ bits per pixel cho biết số lượng bit có thé lưu trữ trong một pixel của hình ảnh đầu vào nhất định. Tỷ lệ này được định nghĩa dựa vào kích thước tệp nén và tong số điểm ảnh trong bức ảnh (tổng số pixel).
size of compressed file BPP = Sees (3) Total no. of pixel in the image 1. Cau trúc tương đồng - Structure Similarity Index Measure (SSIM) Chi số SSIM được sử dung dé do mức độ giống nhau giữa hình anh đầu vào và ảnh sinh ra. Công thức SSIM dựa trên ba thông số để so sánh: độ chói (luminance), tương phản (contrast) và cau trúc (structure).
Với một hình anh x, cường độ sáng là ux và độ tương phan là ox được ước tính như là giá trị trung bình và độ lệch chuẩn của ảnh. Thêm vào đó, ci = (kiL) ?và co = (k›L) ? là hằng số dé tăng sự ôn định với ki <= 1, ky <= 1 và L là phạm vi không chắc chắn của giá tri pixel ( mặc định là K; = 0. Trong đó, SSIM giữa hình ảnh x và y được tính bởi công thức (4): (2Hxuy + c1)(2c0xy + ca) SSIM xX; (y) (u? + py + c¡)(0š + oy + C2) re (4) 1. Muc tiéu dé tai Ở dé tài này, nhóm sé tập trung nghiên cứu, tìm hiểu thuật toán Dynamic Huffman Coding và các thuật toán nén ảnh liên quan.
Sau đó, nhóm tiến hành triển khai thuật toán trên phần mềm và cải tiến thuật toán với tỉ lệ nén tối ưu hơn. Tiếp theo, nhóm sẽ phân tích, thiết kế, sử dụng ngôn ngữ verilog để mô tả kiến trúc. Sau cùng sẽ mô phỏng và kiểm tra dé hoàn thiện thiết kế. Với mục tiêu là triển khai một thiết kế hệ thong phan cứng nén dữ liệu thời gian thực không mat mát đi cùng với tỉ lệ nén được cải thiện.
Ngoài ra, mục tiêu thiết kế một hệ thống phần cứng cải thiện được area so với hệ thông phân cứng có liên quan. Với mục tiêu đê tài này, nhóm đánh giá hệ thông dựa trên các tiêu chí sau: e Đầu tiên, mô phỏng hệ thống nén và giải nén trên ngôn ngữ phan mềm C++.