lOMoARcPSD| 36991220
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC BÁCH KHOA
BÁO CÁO BÀI TẬP LỚN 2 XÁC SUẤT THỐNG KÊ Đề tài XỬ LÝ ẢNH XÁM
ÁP DỤNG MÃ HÓA HUFFMAN ĐỂ NÉN DỮ LIỆU ẢNH XÁM MỤC LỤC I. Mã hóa
Huffman...................................................................................................4
1. Giới thiệu.........................................................................................................5
2. Ý tưởng............................................................................................................5 3. Cây
Huffman....................................................................................................5
4. Mã Huffman.....................................................................................................6
5. Thuật toán nén tĩnh..........................................................................................6
6. Ưu điểm...........................................................................................................7
7. Nhược điểm.....................................................................................................7 lOMoARcPSD| 36991220
8. Ví dụ................................................................................................................7
II. Đọc và xuất ảnh
xám.........................................................................................10
1. Phần mềm sử dụng:........................................................................................10
2. Thư viện sử dụng:..........................................................................................10
3. Các bước làm :...............................................................................................10
III. Mã hóa Huffman cho các mức xám...............................................................18
IV. Hiệu suất...........................................................................................................33
Giới thiệu chung
Ảnh số là hình ảnh được thu nhận bởi các cảm biến điện tử có trong các thiết bị
như camera, máy ảnh số….
Ảnh số là tập hợp của các phần tử ảnh, hay còn gọi là các pixel, điểm ảnh. Kích
thước một ảnh được ký hiệu là N*M pixel, với N là số pixel theo chiều dọc của ảnh
và M là số pixel theo chiều ngang của ảnh.
Ảnh xám (gray image): Các pixel biểu diễn các màu từ màu trắng đến màu đen.
Mỗi màu sẽ được biểu diễn bằng một con số từ 0 (tương ứng với màu đen) đến 255
tương ứng với màu trắng, như vậy có tổng cộng 256 màu. I. Mã hóa Huffman MÃ HÓA lOMoARcPSD| 36991220 HUFFM AN 1. Giới thiệu
Mã hóa Huffman (David A. Huffman) là một thuật toán mã hóa dùng để nén dữ
liệu. Dựa trên bảng tần suất xuất hiện các kí tự cần mã hóa để xây dựng một bộ mã
nhị phân cho các kí tự đó sao cho dung lượng (số bit) sau khi mã hóa là nhỏ nhất. 2. Ý tưởng
Giảm số bit để biểu diễn 1 ký tự.
Dùng chuỗi bit ngắn hơn để biểu diễn ký tự xuất hiện nhiều.
Sử dụng mã tiền tố để phân cách các ký tự. 3. Cây Huffman
+ Là cây nhị phân, mỗi nút chứa ký tự và trọng số (tần suất của ký tự đó).
+ Mỗi ký tự được biểu diễn bằng 1 nút lá (tính tiền tố ). Cây
+ Nút cha có tổng ký tự, tổng trọng số của 2 nút con. Huffman
+ Các nút có trọng số, ký tự tăng dần từ trái sang phải.
+ Các nút có trọng số lớn nằm gần nút gốc.
+ Các nút có trọng số nhỏ nằm xa nút gốc hơn. 4. Mã Huffman
Là chuỗi nhị phân được sinh ra dựa trên cây Huffman.
Mã Huffman của ký tự là đường dẫn từ nút gốc đến nút lá đó. lOMoARcPSD| 36991220
• Sang trái ta được bit 0.
• Sang phải ta được bit 1.
Có độ dài biến đổi (tối ưu bảng mã).
• Các ký tự có tần suất lớn có độ dài ngắn.
• Các ký tự có tần suất nhỏ có độ dài dài hơn.
5. Thuật toán nén tĩnh
B1: Duyệt file, lập bảng thống kê tuần suất xuất hiện của mỗi ký tự
B2: Xây dựng cây Huffman dựa vào bảng thống kê
B3: Sinh mã Huffman cho mỗi ký tự dựa vào cây Huffman
B4: Duyệt file, thay toàn bộ ký tự bằng mã Huffman tương ứng .
B5: Lưu lại cây Huffman (bảng mã) dùng cho việc giải nén. Xuất file đã nén. 6. Ưu điểm
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ớ. 7. Nhược điểm
Mất 2 lần duyệt file khi nén.
Phải lưu trữ thông tin giải mã vào file nén.
Phải xây dựng lại cây Huffman khi giải nén. lOMoARcPSD| 36991220 8. Ví dụ VD1 : A B C D E 0.10 0.15 0.30 0.16 0.29 Tạo cây Huffman: 7 lOMoARcPSD| 36991220 A B C D E 010011 11 00 10 VD2: DE |13 Ký tự Tần suất 234234 A 9 231232 312323 B 15 1312 C 10 D | 6 13113 E | 7 D 6 E 7 lOMoARcPSD| 36991220 lOMoARcPSD| 36991220
II. Đọc và xuất ảnh xám
1. Phần mềm sử dụng:
Visual Studio (Phiên bản Visual studio sử dụng ở đây là phiên bản Visual Studio
2015, các phiên bản khác ta hoàn toàn có thể cấu hình một cách tương tự.)
2. Thư viện sử dụng: OpenCV
3. Các bước làm :
Bước 1: Trước hết ta cần download thư viện OpenCV về máy tính, tốt hơn là luôn
download bản mới nhất tại địa chỉ http://sourceforge.net/projects/opencvlibrary/.
Sau khi dowload về máy, tiến hành cài đặt bình thường, ta để mặc định thư mục cài
đặt là C:\ thư mục cài đặt xong sẽ có dạng C:\opencv.
Bước 2: Trên Microsoft Visual Studio:
+ Tạo một project mới: New -> Project, trong cửa sổ New Project chọn Visual C+
+, Win32 console application. Đặt tên project là docvaxuatanhxam lOMoARcPSD| 36991220
+ Chọn OK, sau đó nhấn Next, hộp thoại tiếp theo xuất hiện, ở hộp thoại này ta
chọn Application type là Console application và Additional option là Empty
project, nhấn Finish để kết thúc quá trình khởi tạo
+ Project mới được tạo ra là project hoàn toàn trống, ta phải thêm vào đó ít nhất
một file nguồn để chương trình có thể chạy được, trong Solution Explorer ta click
chuột phải vào Source Files, chọn Add -> New Item… Hộp thoại Add New Item
hiện ra, ta chọn kiểu cần thêm vào là C++ File(.cpp) đồng thời trong ô Name ta đặt
tên cho file thêm vào, giả sử là Source.cpp lOMoARcPSD| 36991220
+ Để chương trình có thể chạy được với thư viện OpenCV ta cần tùy chỉnh lại một
số thuộc tính của Project như sau:
Vào Project -> Properties (hoặc nhấn tổ hợp phím Alt + F7) để mở hộp thoại
Properties. Hộp thoại opencv Property Pages hiện ra, trong mục Configuration
Properties chọn VC++ Directories, tương ứng bên phải, ta tìm mục Include
Directories và Library Directories. Ta sẽ chỉ đường dẫn hai thư mục này đến các
phần tương ứng của thư viện lOMoARcPSD| 36991220
Mục Include Directories ta tùy chỉnh ở ô bên phải tới C:\opencv\build\include lOMoARcPSD| 36991220
Mục Libraries Directories trỏ đến thư mục C:\opencv\build\x64\vc14\lib lOMoARcPSD| 36991220
Tiếp theo, trong hộp thoại opencv Property Pages -> Configuration Properties ->
Linker chọn Input, tương ứng ở ô bên phải, thêm vào giá trị cho mục Additional
Dependencies là opencv_world450d.lib lOMoARcPSD| 36991220
Cuối cùng, khi dịch xong một chương trình, để nó có thể chạy được ta cần chú ý tới
các file *.dll. Cách đơn giản nhất là ta copy các file *.dll tương ứng (như
opencv_world450d.dll) vào thư mục chứa file chạy của chương trình (file *.exe).
Bước 3: Viết code để đọc và hiển thị một ảnh xám Lena 32*32 pixel
Bước 4: Xuất ảnh xám Lena 32x32 pixel lOMoARcPSD| 36991220
III. Mã hóa Huffman cho các mức xám
• Tải thư viện từ trang web: https://github.com/nothings/stb?
fbclid=IwAR3LfDrYAkBgkQu6Gt4rUxk03W0nGja7zjzQCaCbsBtYEDDCi LzQ0FQArRQ
• Chèn thư viện vào chương trình C
• Thực hiện code đọc ảnh xám Lena gray 32x32 pixel bên dưới
Ảnh Lena gray 32x32 pixel
• Thực hiện code xử lí ảnh thành các mức xám (từ 0 đến 255):
Ảnh code của xử lí ảnh thành các mức xám lOMoARcPSD| 36991220
• Bảng đen console chạy chương trình thể hiện số lần (tần số) xuất hiện của các mức xám
Bảng Consolde của code mã hóa ảnh lOMoARcPSD| 36991220
• Ảnh có chiều cao x chiều rộng 32x32 pixel tương đương 32x32 mức xám
Ảnh thể hiện các mức xám của ảnh (từ 0 đến 255) lOMoARcPSD| 36991220
Ảnh xuất từng tần số các mức xám từ 46 89
Ảnh xuất từng số các mức xám từ 88 131 lOMoARcPSD| 36991220
Ảnh xuất từng số các mức xám từ 130 173
Ảnh xuất từng số các mức xám từ 172 215 lOMoARcPSD| 36991220
Ảnh xuất từng số các mức xám từ 214 255
• Tổng các lần xuất hiện bằng 1024 tương đương với 32x32 với 32x32 mức
xám ở hàng ngang và hàng dọc
• Sử dụng code HuffMan để mã hóa các mức xám của hình Lena gray 32x32
pixel và thực hiện đếm số bit của ảnh sau khi mã hóa và tính hiệu suất của
việc mã hóa: dung lượng ảnh sau khi mã hóa/dung lượng ảnh ban đầu.
Hình ảnh chương trình code lOMoARcPSD| 36991220
Ảnh code mã hóa HuffMan lOMoARcPSD| 36991220 lOMoARcPSD| 36991220 lOMoARcPSD| 36991220 lOMoARcPSD| 36991220
• Màn hình console kết quả
• Bảng phía đầu tiên là bảng thống kê tuần suất tóm gọn, chỉ thể hiện những
mức xám xuất hiện từ 1 lần trở lên và các mức xám không có sẽ không
được xuất hiện(tóm lại tần số các mức xám của bức ảnh )
Bảng thống kế tuần suất tóm gọn các mức xám lOMoARcPSD| 36991220 lOMoARcPSD| 36991220
• Bảng tiếp theo là bảng mã hóa của các mức xám xuất hiện trong bức ảnh bằng mã hóa Huffman
Bảng mã hóa HuffMan của các mức màu lOMoARcPSD| 36991220 lOMoARcPSD| 36991220
• Nhận xét: ta thấy mức xám có tần số càng nhỏ số bit càng dài và ngược lại
mức xám có tần số càng nhiều số bit càng nhỏ
• Phần mã hóa của bằng ảnh bằng cách thay các mức xám bằng các mã hóa sau khi thực hiên HuffMan:
Ảnh mã hóa các mức xám của ảnh Lena gray lOMoARcPSD| 36991220 IV. Hiệu suất
Tính tổng số bit của ảnh sau khi mã hóa và tính hiệu suất của việc mã hóa: dung
lượng ảnh sau khi mã hóa/dung lượng ảnh ban đầu. lOMoARcPSD| 36991220
Ảnh chương trình chạy hiệu suất của bức ảnh