I. Giới thiệu

Hiện nay có nhiều vấn đề trong việc lưu trữ và truyền tải ảnh số hoá. Nén ảnh thực sự có nhiều ứng dụng trong thực tế như: truyền các văn bản đồ hoạ qua đường điện thoại (Fax), nén ảnh trong y tế và truyền hình cáp….

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.

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.

II. Nội dung

1. Phương pháp nén được phân loại như thế nào?

- Dựa vào nguyên lý nén: Nén không mất thông tin: Sau khi giải nén ta thu được chính xác dữ liệu gốc.Nén có mất thông tin: Sau khi giải nén ta không thu được dữ liệu như bản gốc.

- Dựa vào cách thức thực hiện nén: Phương pháp không gian: 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: Tác động lên sự biến đổi của ảnh gốc.

- Dựa vào triết lý của sự mã hóa: Các phương pháp nén thế hệ thứ nhất: Gồm các phương pháp mà mức độ tính toán là đơn giản.Các phương pháp nén thế hệ thứ hai: dựa vào độ bão hòa của tỷ lệ nén.

2. Một số phương pháp nén ảnh số cơ bản

Một số phương pháp nén ảnh số như:Phương pháp mã hóa loạt dài RLE (Run Length Encoding), phương pháp LZW, phương pháp mã hoá Huffman....

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

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ị. 

* 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 = 30/8 = 2.5

Đối với ảnh đen trắng chỉ sử dụng 1 bit để biểu diễn 1 điểm ảnh thì phương pháp này tỏ ra rất hiệu quả, ta thấy điều đó qua ví dụ sau :

Ví dụ: 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 13 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

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 lại. Người ta đã đưa ra cách đó là thêm kí tự tiền tố vào trước độ dài loạt, 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à dấu “+” ta có : 5 8 4 +8 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) 

* Thuật toán: Thuật toán như sau :

- 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 – of bitmap)

b. Phương pháp mã hoá Huffman

Phương pháp mã hóa Huffman là phương pháp dựa vào mô hình thống kê. 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ương pháp 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.

* Thuật toán

Thuật toán bao gồm 2 bước chính:

- Giai đoạn thứ nhất: tính tần suất của các ký tự trong dữ liệu gốc: 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ã. Tiếp sau đó là sắp xếp lại bảng mã theo thứ tự tần suất giảm dần.

- Giai đoạn thứ hai: mã hóa: duyệt bảng tần suất từ cuối lên đầu để thực hiện ghép 2 phần tử có tần suất xuất hiện thấp nhất thành một phần tử duy nhất. Phần tử này có tần suất bằng tổng 2 tần suất thành phần. Tiến hành cập nhật lại bảng và đương nhiên loại bỏ 2 phần tử đã xét. Quá trình được lặp lại cho đến khi bảng chỉ có một phần tử. Quá trình này gọi là quá trình tạo cây mã Huffman vì việc tập hợp được tiến hành nhờ một cây nhị phân 2 nhánh. Phần tử có tần suất thấp ở bên phải, phần tử kia ở bên trái. Với cách tạo cây này, tất cả các bit dữ liệu/ký tự là nút lá; các nút trong là các nút tổng hợp. Sau khi cây đã tạo xong, người ta tiến hành gán mã cho các nút lá. Việc mã hóa rất đơn giản: mỗi lần xuống bên phải ta thêm 1 bit “1” vào từ mã; mỗi lần xuống bên trái ta thêm một bit “0”. Tất nhiên có thể làm ngược lại, chỉ có giá trên mã thay đổi còn tổng chiều dài là không đổi. Cũng chính do lý do này mà cây có tên gọi là cây mã Huffman như trên đã gọi.

Quá trình giải nén tiến hành theo chiều ngược lại khá đơn giản. 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 giữ lại trong cấu trúc của tệp nén cùng với dữ liệu nén). Thí dụ, với một tệp dữ liệu mà tần suất các ký tự cho bởi.

Việc tạo cây nhị phân có thể được thực hiện theo một thuật toán sau:

1. Tất cả những ký tự ban đầu được xem như là những ký tự giao điểm tự do.

2. Hai nút tự do với tần số xuất hiện thấp nhất được phân công tới một nút gốc với giá trị bằng với tổng của hai nút con tự do.

3. Hai nút con được chuyển khỏi danh sách nút tự do. Chuyển nút gốc mới tạo thành công vào danh sách.

4. Bước hai sang bước ba được lặp cho đến khi chỉ có 1 nút tự do về phía trái. Nút tự do này là gốc của cây.

Quá trình xây dựng cây nhị phân Huffman được thể hiện chi tiết như trong hình sau:

Ví dụ:

Chuỗi nguồn : 00000000006666693333 è kích thước = 20*8=160 bit

Sử dụng mã Huffman theo bảng trên è kích thước =10*1+5*3+1*6+4*3= 43 bit (Vì gía trị 0 xuất hiện 10 lần nhưng chỉ dùng 1 bit để thể hiện, giá trị 6 xuất hiện 5 lần dùng 3 bit để thể hiện  ,giá trị 9 dùng 6 bit và giá trị 3 xuất hiện 4 lần dùng 3 bit để thể hiện)

Vậy tỷ số nén = 160 / 43 = 3.7

Trong phương pháp mã Huffman mã của ký tự là duy nhất và không mã nào là phần bắt đầu của mã trước.Vì vậy khi đọc theo từng bit từ đầu đến cuối tệp nén ta có thể duyệt cây mã cho đến một lá, tức là ký tự đã được giải mã. Việc giải mã chắc chắn phải sử dụng cây nhị phân giống như trong mã hoá. Để đọc, giải mã được yêu cầu phải sử dụng theo đúng tiêu chuẩn nhất định.

c. Phương pháp LZW

Giải thuật LZW hay hơn các giải thuật trước nó ở kỹ thuật tổ chức từ điển cho phép nâng cao tỉ lệ nén. Phương pháp nén từ điển dựa trên việc xây dựng từ điển lưu các chuỗi ký tự có tần suất lặp lại cao và thay thế bằng từ mã tương ứng mỗi khi gặp lại chúng.

Giải thuật nén LZW được sử dụng cho tất cả các loại file nhị phân. Nó thường được dùng để nén các loại văn bản, ảnh đen trắng, ảnh màu, ảnh đa mức xám… và là chuẩn nén cho các dạng ảnh GIF và TIFF. Mức độ hiệu quả của LZW không phụ thuộc vào số bít màu của ảnh.

* Nguyên tắc:

Giải thuật nén LZW xây dựng một từ điển lưu các mẫu có tần suất xuất hiện cao trong ảnh. Từ điển là tập hợp những cặp (từ vựng và nghĩa của từ vựng). Trong đó từ vựng sẽ là các từ mã được sắp xếp theo thứ tự nhất định. Nghĩa là một chuỗi con trong dữ liệu ảnh. Từ điển được xây dựng song song với quá trình đọc dữ liệu. Sự  xuất hiện của chuỗi con trong từ điển khẳng định rằng chuỗi đó đã từng xuất hiện trong phần dữ liệu đã được đọc qua. Thuật toán liên tục tra cứu và sau mỗi lần đọc một ký tự ở dữ liệu đầu vào thì tiến hành cập nhật lại từ điển.

Do giới hạn của bộ nhớ và để đảm bảo tốc độ tìm kiếm nhanh, từ điển chỉ giới hạn 4096 phần tử dùng để lưu trữ giá trị của các từ mã. Như vậy độ dài lớn nhất của từ mã là 12 bit (4096=2¹²). Cấu trúc từ điển như sau:

- 256 từ mã đầu tiên theo thứ tự từ 0 … 255 chứa các số nguyên từ 0 …  255. Đây là mã của 256 kí tự cơ bản trong bảng mã ASCII.

- Từ mã thứ 256 chứa một mã đặc biệt là mã xoá (CC - Clear Code). Khi số mẫu lặp lớn hơn 4096 thì người ta sẽ coi ảnh gồm nhiều mảnh ảnh và từ điển sẽ gồm nhiều từ điển con. Khi hết một mảnh ảnh sẽ gửi 1 mã xoá (CC ) để báo hiệu kết thúc mảnh ảnh cũ và bắt đầu mảnh ảnh mới đồng thời sẽ khởi tạo lại từ điển.

- Từ mã thứ 257 chứa mã kết thúc thông tin (EOI  -  End Of Information). Thông thường một file ảnh GIF có thể chứa nhiều mảnh ảnh, mỗi mảnh ảnh này sẽ được mã hoá riêng. Chương trình giải mã sẽ lặp đi lặp lại thao tác giải mã từng ảnh cho đến khi gặp mã kết thúc thông tin thì dừng lại.

- Các từ mã còn lại (từ 258 đến 4095) chứa các mẫu thường lặp lại trong ảnh. 512 phần tử đầu tiên của từ điển biểu diễn bằng 9 bit. Các từ mã từ 512 đến 1023 biểu diễn bởi 10 bit, từ 1024 đến 2047 biểu diễn bởi 11 bit, và từ 2048 đến 4095 biểu diễn bởi 12 bit.

Chuỗi thu được sau giải nén: “HELLOHELLOHELL”

III. Kết luận

Để so sánh 3 phương pháp nén ảnh số ở trên, chúng ta thấy rằng: Phương pháp nén RLE không thể áp dụng nén nhiều loại tập tin. Phương pháp LZW có hệ số nén tương đối cao, tốn nhiều bộ nhớ, khó thực hiện trên các mảng bé hơn 64KB. Phương pháp Huffman cũng có hệ số nén tương đối cao, phương pháp thực hiện lại tương đối đơn giản, đòi hỏi ít bộ nhớ, có thể xây dựng dựa trên các mảng bé hơn 64KB.

Tài liệu tham khảo

[1] PGS.TS Nguyễn Quang Hoan, Bài giảng Xử lý Ảnh, Học viện công nghệ Bưu chính Viễn thông.

[2] Tạ Minh Thắng, Tìm hiểu một số phương pháp nén ảnh, Đại học dân lập Hải Phòng.