Bối cảnh và vấn đề nghiên cứu

Trong bối cảnh khoa học công nghệ và mạng Internet phát triển, nhu cầu trao đổi và lưu trữ thông tin số—đặc biệt là dữ liệu hình ảnh đa phương tiện—ngày càng gia tăng trong các lĩnh vực như viễn thông, y tế, truyền hình và thiên văn học. Tuy nhiên, dữ liệu ảnh số hóa ở dạng nguyên bản chiếm dung lượng lưu trữ rất lớn và đòi hỏi băng thông truyền tải cao.

Văn bản minh chứng sự cần thiết của kỹ thuật nén ảnh thông qua bài toán thực tế trên đường truyền tốc độ 9600 baud (9600 bps):

  • Ảnh đa cấp xám hoặc ảnh 256 màu có kích thước 800 $\times$ 600 (8 bit/điểm ảnh) tiêu tốn 3.000 bit lưu trữ và đòi hỏi thời gian truyền đáng kể.
  • Ảnh màu RGB (24 bit/điểm ảnh) cùng độ phân giải 800 $\times$ 600 đòi hỏi hơn 10 triệu bit lưu trữ và mất khoảng 20 phút để truyền tải.
  • Một phim âm bản kích thước 24 $\times$ 36 mm (35 mm) quét ở bước 12 $\mu$m tạo ra ma trận xấp xỉ 3000 $\times$ 2000 điểm ảnh (8 bit/pixel), yêu cầu 48 triệu bit dung lượng và mất tới 83 phút để truyền đi.

Do đó, đồ án tốt nghiệp tập trung giải quyết bài toán giảm dung lượng dữ liệu biểu diễn ảnh nhằm tiết kiệm không gian lưu trữ và hạ thấp chi phí thời gian truyền dữ liệu trên mạng truyền thông nhưng vẫn duy trì chất lượng ảnh theo yêu cầu.

Nhiệm vụ nghiên cứu của đề tài gồm 3 nội dung chính:

  1. Nghiên cứu tổng quan về ảnh số, quy trình xử lý ảnh và bản chất các dạng dư thừa dữ liệu trong ảnh (dư thừa không gian, dư thừa mức xám, dư thừa thời gian).
  2. Phân tích nguyên lý toán học và cấu trúc giải thuật của các phương pháp nén dữ liệu phổ biến: Mã hóa độ dài loạt (RLE), Mã hóa Huffman, Mã hóa từ điển LZW, chuẩn nén JPEG và chuẩn nén nâng cao JPEG2000 dựa trên biến đổi Wavelet.
  3. Thiết kế, cài đặt các thủ tục chương trình và tiến hành thử nghiệm các thuật toán để đánh giá hiệu quả nén.

Đề tài do sinh viên Tạ Minh Thắng (lớp CT 702) thực hiện tại Khoa Công nghệ Thông tin - Trường Đại học Dân Lập Hải Phòng vào năm 2007, dưới sự hướng dẫn khoa học của PGS. Ngô Quốc Tạo.

Cơ sở lý thuyết và phương pháp

Khung lý thuyết và mô hình tính toán

Ảnh số được mô hình hóa dưới dạng một ma trận hai chiều các phần tử ảnh (Pixel hay PEL):

  • Ảnh đa mức xám: Sử dụng 8 bit (1 byte) để biểu diễn mức xám cho mỗi điểm ảnh, tương ứng $2^8 = 256$ mức (từ mức 0 biểu diễn cường độ đen nhất đến mức 255 biểu diễn cường độ sáng nhất).
  • Ảnh màu: Biểu diễn bằng 24 bit cho mỗi điểm ảnh, chia thành 3 khoảng 8 bit độc lập đại diện cho 3 kênh màu cơ bản: Đỏ (Red), Lục (Green) và Lam (Blue).

Cơ sở của việc nén dữ liệu bắt nguồn từ tính trật tự và phi ngẫu nhiên của dữ liệu ảnh. Kỹ thuật nén thực hiện bóc tách cấu trúc để triệt tiêu các thành phần dư thừa:

  • Dư thừa không gian: Tương quan tương hỗ cao giữa các điểm ảnh kề nhau trong cùng một bức ảnh.
  • Dư thừa mức xám (màu sắc): Sự tương quan giữa các dải màu lân cận.
  • Dư thừa thời gian: Tương quan giữa các điểm ảnh qua các khung hình liên tiếp (video frame).

Các chỉ số định lượng đánh giá hiệu quả nén được xác định theo công thức:

  • Tỷ số nén ($r$): $$r = \frac{\text{Kích thước dữ liệu gốc}}{\text{Kích thước dữ liệu nén}}$$
  • Tỷ lệ nén: $$\text{Tỷ lệ nén} = \frac{1}{r} \times 100%$$
  • Hiệu suất nén: $$\text{Hiệu suất nén} = (1 - \text{Tỷ lệ nén}) \times 100%$$

Phương pháp nghiên cứu

  • Phương pháp phân tích - tổng hợp lý thuyết: Hệ thống hóa lý thuyết mã hóa thông tin, lý thuyết xác suất thống kê, phép biến đổi không gian và biến đổi miền tần số (Discrete Cosine Transform - DCT, Wavelet).
  • Phương pháp thiết kế và lập trình thực nghiệm: Cài đặt thuật toán bằng ngôn ngữ C++ trên môi trường Windows/MFC, trực tiếp xử lý các cấu trúc dữ liệu ảnh Bitmap (DIB), mảng bit và các luồng tệp tin nhị phân.

Nội dung chính theo từng chương

Chương I: Giới thiệu tổng quan về nén ảnh

Chương này trình bày các khái niệm nền tảng về xử lý ảnh số và lý do kỹ thuật dẫn đến sự ra đời của các chuẩn nén.

  • Biểu diễn ảnh số: Định nghĩa phần tử ảnh (Pixel/PEL), mức xám (Graylevel), các chuẩn độ phân giải màn hình phổ biến (320 $\times$ 200, 640 $\times$ 350, 800 $\times$ 600, 1024 $\times$ 768).
  • Quy trình xử lý ảnh số: Mô tả chu trình khép kín gồm: Thu nhận ảnh (Camera/Sensor) $\rightarrow$ Số hóa $\rightarrow$ Phân tích $\rightarrow$ Nhận dạng $\rightarrow$ Hệ quyết định $\rightarrow$ Lưu trữ.
  • Bản chất của nén ảnh: Quá trình biến đổi luồng dữ liệu gốc thành luồng dữ liệu nén nhằm loại bỏ tính dư thừa thông tin nhưng vẫn cho phép phục hồi ảnh xấp xỉ hoặc chính xác so với ban đầu.
Thành phần dư thừa Đặc điểm kỹ thuật
Dư thừa không gian Điểm ảnh lân cận có mức xám hoặc giá trị màu tương tự nhau.
Dư thừa mức xám Giới hạn phân biệt màu sắc của mắt người cho phép giảm bớt số mức biểu diễn.
Dư thừa thời gian Sự lặp lại bối cảnh giữa các khung hình (frames) liên tiếp trong chuỗi video.

Chương II: Các phương pháp nén ảnh

Chương II phân loại toàn diện các trường phái nén và đi sâu vào chi tiết giải thuật của 5 phương pháp nén ảnh điển hình.

                   CÁC PHƯƠNG PHÁP NÉN ẢNH
Theo nguyên lý         Theo cách thức          Theo lý thuyết mã hóa
- Bảo toàn (Lossless)   - Miền không gian       - Thế hệ thứ nhất
- Mất mát (Lossy)       - Miền biến đổi         - Thế hệ thứ hai

1. Phương pháp mã hóa độ dài loạt (Run Length Encoding - RLE)

  • Nguyên tắc: Gom cụm các dãy điểm ảnh liên tiếp có cùng giá trị thành cặp (độ dài loạt, giá trị). Thích hợp cho ảnh nhị phân hoặc ảnh có các vùng đồng màu lớn.
  • Xử lý giới hạn: Với loạt có độ dài $> 255$, thuật toán phân tách thành chuỗi độ dài 255 và chuỗi phần dư.
  • Kỹ thuật chống giãn nở dữ liệu: Khi ảnh chứa các giá trị biến đổi liên tục, RLE thông thường làm tăng gấp đôi kích thước. Tác giả trình bày hai giải pháp:
    • Bổ sung ký tự tiền tố (ví dụ dấu +) trước loạt lặp; các điểm ảnh đơn lẻ được giữ nguyên.
    • Sử dụng sai phân vi sai giữa các điểm lân cận: $e(i) = d(i) - d(i-1)$ để tạo ra chuỗi giá trị có độ tương quan lặp lại cao trước khi đưa qua bộ mã hóa RLE.

2. Phương pháp mã hóa Huffman

  • Nguyên tắc: Dựa trên mô hình thống kê xác suất xuất hiện của các ký tự/mức xám. Ký tự có tần suất xuất hiện cao được gán từ mã ngắn, ký tự có tần suất thấp được gán từ mã dài, tối ưu hóa chiều dài trung bình của từ mã.
  • Thuật toán tạo cây nhị phân:
    1. Thống kê tần suất xuất hiện của các ký tự trong toàn bộ tệp dữ liệu nguồn và sắp xếp giảm dần.
    2. Hợp nhất hai phần tử có tần suất thấp nhất ở cuối bảng thành một nút cha có trọng số bằng tổng hai nút con. Cập nhật nút cha vào bảng và loại bỏ hai nút con.
    3. Lặp lại quá trình cho đến khi cây chỉ còn lại một nút gốc duy nhất.
    4. Gán mã nhị phân: Rẽ nhánh sang phải gán bit 1, rẽ nhánh sang trái gán bit 0. Mã thu được có tính tiền tố (Prefix code), đảm bảo quá trình giải mã không bị nhập nhằng.

3. Phương pháp mã hóa từ điển LZW (Lempel - Ziv - Welch)

  • Lịch sử & Nguyên lý: Phát triển từ giải thuật nén LZ (Jacob Ziv và Abraham Lempel, 1977), được Terry Welch cải tiến năm 1984. LZW xây dựng từ điển chứa các chuỗi mẫu lặp lại trong quá trình đọc dữ liệu và thay thế chuỗi bằng chỉ số từ mã tương ứng.
  • Cấu trúc từ điển (tối đa 4096 phần tử - biểu diễn bằng 12 bit):
    • Mục 0 đến 255: 256 ký tự cơ bản trong bảng mã ASCII.
    • Mục 256 (Clear Code - CC): Mã xóa dùng để báo hiệu khởi tạo lại từ điển khi số mẫu vượt quá 4096 hoặc khi chuyển sang mảnh ảnh mới.
    • Mục 257 (End Of Information - EOI): Mã báo hiệu kết thúc dữ liệu ảnh.
    • Mục 258 đến 4095: Các chuỗi mẫu ký tự ghép mới được tạo ra trong quá trình nén. Kích thước từ mã tăng động từ 9 bit (512 mục đầu), 10 bit (512–1023), 11 bit (1024–2047) đến 12 bit (2048–4095).
  • LZW là chuẩn nén cốt lõi cho các định dạng ảnh GIF và TIFF.

4. Phương pháp mã hóa JPEG (Joint Photographic Experts Group)

Chuẩn quốc tế ISO/ITU (1992) chuyên dụng cho ảnh đa mức xám và ảnh màu. Đề tài tập trung phân tích kỹ thuật nén mất mát thông tin dựa trên biến đổi Cosin rời rạc tuần tự (Sequential DCT-Based):

  • Phân khối 8 $\times$ 8: Ảnh được chia thành các khối $8 \times 8$ điểm ảnh. Việc phân khối giúp giảm khối lượng tính toán hệ số $C_{ij}$. Với khối $8 \times 8$ ($8 = 2^3$), chỉ cần tính 7 hệ số qua 3 tầng; trong khi ảnh $512 \times 512$ cần tới 509 hệ số qua 9 tầng. Thời gian tính toán cho cả bức ảnh lớn gấp 72 lần so với tính toán trên từng khối $8 \times 8$.
  • Biến đổi Cosin rời rạc 2 chiều (2D-DCT): Thực hiện thông qua 16 phép biến đổi DCT 1 chiều (8 hàng và 8 cột), tập trung năng lượng ảnh vào một số ít hệ số góc trên bên trái: $$X(k_1, k_2) = \frac{1}{4} c(k_1) c(k_2) \sum_{n_1=0}^{7} \sum_{n_2=0}^{7} x(n_1, n_2) \cos\left[\frac{(2n_1+1)k_1\pi}{16}\right] \cos\left[\frac{(2n_2+1)k_2\pi}{16}\right]$$
  • Lượng tử hóa (Quantization): Áp dụng bộ lượng tử hóa Lloyd - Max để chia các hệ số biến đổi cho các bước lượng tử tương ứng, loại bỏ các chi tiết mắt người khó cảm nhận.
  • Mã hóa thành phần:
    • Hệ số một chiều (DC - $X(0,0)$): Mang phần lớn năng lượng ảnh, được mã hóa vi sai theo hiệu số $d_i = C_{i+1}(0,0) - C_i(0,0)$ rồi nén bằng bảng mã Huffman riêng.
    • 63 hệ số xoay chiều (AC): Sắp xếp theo đường quét Zig-zag để gom các hệ số 0 thành chuỗi dài, sau đó nén bằng RLE kết hợp ký hiệu kết thúc khối (EOB - End Of Block) và mã hóa tiếp bằng bảng mã Huffman thứ hai.

5. Chuẩn nén JPEG2000

Mục lục và phần mở đầu của đề tài giới thiệu chuẩn JPEG2000 với các nội dung:

  • Lịch sử ra đời và tính năng nâng cao.
  • Quy trình nén: Xử lý trước biến đổi $\rightarrow$ Biến đổi liên thành phần $\rightarrow$ Biến đổi riêng thành phần bằng phép biến đổi sóng nhỏ (Wavelet Transform) $\rightarrow$ Lượng tử hóa $\rightarrow$ Mã hóa phân cấp dòng dữ liệu bằng thuật toán SPIHT (Set Partitioning in Hierarchical Trees) và EZW (Embedded Zerotree Wavelet).
  • Ưu thế: Loại bỏ hiện tượng phân khối (blocking artifact) của DCT ở tỷ số nén cao, hỗ trợ nén bảo toàn lẫn không bảo toàn thông tin.

Chương III: Cài đặt chương trình và thử nghiệm

Chương III trình bày việc xây dựng phần mềm thử nghiệm để hiện thực hóa các giải thuật nén đã nghiên cứu trên các tệp dữ liệu ảnh cụ thể, kiểm nghiệm tính đúng đắn của giải thuật nén/giải nén và đánh giá các kết quả thu được.

Thiết kế và triển khai thuật toán

Đồ án xây dựng chương trình thử nghiệm bằng C++ với cấu trúc lớp đối tượng module hóa:

Lớp đối tượng Hàm / Thủ tục chính Chức năng kỹ thuật trong mã nguồn
CRLE CompressInRLE8() Quét từng dòng quét ảnh DIB, kiểm tra trạng thái lặp; loạt $\ge 3$ chuyển sang chế độ nén; loạt $> 255$ tách chuỗi; chèn padding căn chỉnh 4-byte (BMPWIDTHBYTES).
CRLE DecRLE8() Giải mã dòng byte nhị phân nén RLE8, phục hồi ma trận ảnh gốc dựa trên các cờ điều khiển dòng/khối.
CHuffmanNode CompressHuffman() Đếm tần suất xuất hiện 256 ký tự ASCII trên mảng 511 nút, tạo cây nhị phân, gán từ mã bit động và xuất luồng bit nén.
CHuffmanNode DecompressHuffman() Đọc cấu trúc cây nhị phân từ Header tệp, duyệt luồng bit dịch trái/phải trên cây nhị phân để giải mã byte gốc.
CLZW Compress() Khởi tạo từ điển 256 ký tự ASCII + 2 mã điều khiển CC (256) và EOI (257); đọc chuỗi ký tự, tra cứu và bổ sung mục mới vào từ điển, xuất mã có độ dài 9–12 bit.
CLZW Decompress() Tái tạo từ điển động đồng thời với quá trình đọc chuỗi mã nén, xử lý mã xóa CC để khởi tạo lại bảng tra cứu.
CJPEG write_JPEG_file() Thiết lập cấu trúc jpeg_compress_struct, xử lý không gian màu JCS_RGB hoặc JCS_GRAYSCALE, cấu hình chất lượng nén jpeg_set_quality(), thực hiện nén dữ liệu khối theo chuẩn JPEG.

Kết quả và đóng góp

  1. Hệ thống hóa lý thuyết: Tổng hợp các nhóm giải thuật nén ảnh kinh điển (từ nén không gian RLE, nén thống kê Huffman, nén từ điển LZW đến nén biến đổi DCT trong JPEG và Wavelet trong JPEG2000).
  2. Chứng minh định lượng hiệu quả phân khối: Phân tích toán học chứng minh việc phân khối $8 \times 8$ trong biến đổi DCT giúp giảm số phép tính hệ số biến đổi $C_{ij}$ đi 72 lần so với việc tính toán trên toàn bộ ma trận ảnh $512 \times 512$, tối ưu hóa tốc độ xử lý.
  3. Hiện thực hóa mã nguồn: Cài đặt hoàn chỉnh các hàm nén/giải nén mức bit và byte bằng C++ cho các thuật toán RLE 8-bit, Huffman và LZW, cùng module tích hợp nén JPEG.

Hạn chế và hướng nghiên cứu tiếp

  • Hạn chế:
    • Thuật toán RLE phụ thuộc vào cấu trúc ảnh, hiệu quả không ổn định nếu ảnh có độ biến thiên mức xám cao (cần tiền xử lý vi sai).
    • Thuật toán JPEG tuần tự có độ phức tạp cài đặt lớn ở khâu thiết kế bộ lượng tử Lloyd - Max và xảy ra hiện tượng mờ/khối khi áp dụng hệ số nén cao.
  • Hướng phát triển:
    • Tiếp tục hoàn thiện việc cài đặt chi tiết và tối ưu hóa giải thuật nén JPEG2000 trên cơ sở phép biến đổi Wavelet kết hợp các bộ mã hóa SPIHT và EZW.
    • Mở rộng nghiên cứu áp dụng các kỹ thuật khử dư thừa thời gian cho nén chuỗi hình ảnh video.

Giá trị tham khảo

Tài liệu là nguồn tham khảo trực tiếp cho sinh viên, học viên ngành Công nghệ Thông tin, Kỹ thuật Phần mềm và Điện tử - Viễn thông khi làm đồ án hoặc nghiên cứu về:

  • Các thuật toán xử lý và nén dữ liệu cơ bản (RLE, Huffman, LZW).
  • Kỹ thuật tính toán biến đổi Cosin rời rạc (DCT) và lượng tử hóa ma trận trong xử lý tín hiệu số.
  • Cách tổ chức cấu trúc dữ liệu cây nhị phân, bảng từ điển động và thao tác xử lý tệp tin nhị phân mức bit/byte trong ngôn ngữ C++.

Câu hỏi thường gặp

1. Tại sao chuẩn JPEG lại chia ảnh thành các khối 8 $\times$ 8 điểm ảnh trước khi biến đổi DCT?

Việc chia ảnh thành các khối $8 \times 8$ giúp giảm độ phức tạp tính toán hệ số biến đổi $C_{ij}$. Với khối kích thước 8, chỉ cần tính 7 hệ số qua 3 tầng phân chia ($8 = 2^3$), trong khi ảnh kích thước $512 \times 512$ đòi hỏi tính 509 hệ số qua 9 tầng ($512 = 2^9$). Thời gian tính toán hệ số cho cả bức ảnh $512 \times 512$ lớn gấp 72 lần so với việc thực hiện trên từng khối $8 \times 8$.

2. Từ điển của thuật toán LZW trong đề tài có cấu trúc và giới hạn kích thước như thế nào?

Từ điển LZW được giới hạn ở kích thước 4096 phần tử (tương ứng từ mã tối đa 12 bit) nhằm đảm bảo tốc độ tra cứu và tiết kiệm bộ nhớ. Trong đó:

  • 256 phần tử đầu tiên (0–255) chứa mã ASCII cơ bản.
  • Phần tử 256 là mã xóa (Clear Code - CC) dùng để khởi tạo lại từ điển.
  • Phần tử 257 là mã kết thúc thông tin (End Of Information - EOI).
  • Các phần tử từ 258 đến 4095 lưu trữ các chuỗi ký tự lặp mới xuất hiện.

3. Giải pháp nào được đề xuất để tránh hiện tượng RLE làm tăng kích thước tệp khi ảnh không có các điểm lặp lại?

Đề tài nêu hai giải pháp cải tiến:

  • Bổ sung một ký tự tiền tố đặc biệt (ví dụ +) trước loạt lặp; các điểm ảnh đơn lẻ không lặp được giữ nguyên.
  • Áp dụng phép biến đổi sai phân mức xám $e(i) = d(i) - d(i-1)$ giữa các điểm ảnh kề nhau để tạo ra chuỗi giá trị tương quan lặp lại trước khi nén.

4. Trong chuẩn JPEG, hệ số DC và các hệ số AC được mã hóa khác nhau như thế nào?

  • Hệ số một chiều (DC - mang phần lớn năng lượng khối) không nén trực tiếp mà được tính sai phân $d_i = C_{i+1}(0,0) - C_i(0,0)$ so với khối trước đó rồi mã hóa bằng bảng mã Huffman riêng.
  • 63 hệ số xoay chiều (AC - biểu diễn chi tiết) được quét theo đường Zig-zag để gom các hệ số 0 liên tiếp, sau đó mã hóa độ dài loạt RLE, thêm ký hiệu kết thúc khối (EOB) và nén tiếp bằng bảng mã Huffman thứ hai.

Kết luận

Đồ án tốt nghiệp "Tìm hiểu một số phương pháp nén ảnh" của tác giả Tạ Minh Thắng đã hệ thống hóa cơ sở lý thuyết về biểu diễn ảnh số và các kỹ thuật khử dư thừa dữ liệu. Công trình phân tích chi tiết cơ chế hoạt động của các phương pháp nén phổ biến gồm RLE, Huffman, LZW, JPEG và chuẩn JPEG2000 sử dụng biến đổi Wavelet. Đề tài cũng hiện thực hóa thành công mã nguồn C++ thử nghiệm cho các thuật toán nén cơ sở, cung cấp tài liệu tham khảo có giá trị kỹ thuật cho lĩnh vực xử lý ảnh số.