LỜI CẢM ƠN
Sau một thời gian thực hiện khóa luận tốt nghiệp, đến nay công việc
liên quan đến khóa luận đã được hoàn tất. Trong suốt thời gian thực hiện khóa
luận em đã nhận được rất nhiều sự giúp đỡ. Ở phần đầu của khóa luận này
cho phép em gửi lời cảm ơn chân thành và sâu sắc đến những người đã giúp
đỡ em.
Em xin cảm ơn các thầy cô giáo trong khoa Công nghệ Thông tin,
trường Đại học sư phạm Hà Nội 2, những người đã giúp đỡ cho em trong suốt
quá trình học tập và nghiên cứu.
Em xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới thầy giáo TS.Trịnh
Đình Vinh, khoa Công nghệ Thông tin, trường Đại học sư phạm Hà Nội 2 đã
hướng dẫn hết sức chu đáo, nhiệt tình trong quá trình em làm khóa luận.
Cuối cùng, em xin bày tỏ lòng biết ơn tới gia đình và các bạn bè đã
giúp đỡ, động viên em rất nhiều trong suốt quá trình học tập để em có thể
thực hiện tốt khóa luận này.
Tuy đã có những cố gắng nhất định nhưng do thời gian và trình độ có
hạn nên chắc chắn khóa luận này còn nhiều thiếu sót và hạn chế nhất định.
Kính mong nhận được sự góp ý của thầy cô và các bạn.
Hà Nội, tháng 05 năm 2013
Sinh viên

Nguyễn Thị Thanh Nhã


LỜI CAM ĐOAN
Tên em là: NGUYỄN THỊ THANH NHÃ
Sinh viên lớp: K35 – Tin học, khoa Công nghệ Thông tin, trường Đại
học sư phạm Hà Nội 2.
Em xin cam đoan:
1. Đề tài: “MỘT SỐ PHƯƠNG PHÁP NÉN ẢNH VÀ XÂY DỰNG
CHƯƠNG TRÌNH THỬ NGHỆM” là sự nghiên cứu của riêng em, dưới sự

hướng dẫn của thầy giáo TS. Trịnh Đình Vinh.
2. Khóa luận hoàn toàn không sao chép của tác giả nào khác.
Nếu sai em xin hoàn toàn chịu trách nhiệm.
Hà Nội, tháng 05 năm 2013
Người cam đoan

Nguyễn Thị Thanh Nhã


MỤC LỤC
Trang
LỜI CẢM ƠN
LỜI CAM ĐOAN
MỤC LỤC
CÁC TỪ VIẾT TẮT
DANH MỤC HÌNH
MỞ ĐẦU ....................................................................................................... 1
CHƯƠNG 1: TỔNG QUAN VỀ XỬ LÝ ẢNH .............................................. 4
1.1. TỔNG QUAN VỀ XỬ LÝ ẢNH ...................................................... 4
1.1.1. Xử lý ảnh .................................................................................... 4
1.1.2. Giới thiệu về ảnh số và xử lý ảnh số ........................................... 7
1.2. NÉN ẢNH ........................................................................................ 9
CHƯƠNG 2: CÁC PHƯƠNG PHÁP NÉN ẢNH......................................... 11
2.1. Phân loại các phương pháp nén ảnh ................................................. 11
2.1.1. Phân loại dựa vào nguyên lý nén .............................................. 11
2.1.2. Phân loại dựa vào cách thức thực hiện nén ............................... 11
2.1.3. Phân loại dựa vào lý thuyết mã hoá .......................................... 11
2.2. Quá trình nén và giải nén ................................................................ 12
2.3. Phương pháp mã hoá độ dài loạt RLE .............................................. 12
2.3.1. Nguyên tắc ............................................................................... 12

2.3.2. Thuật toán ................................................................................ 14
2.4. Phương pháp mã hoá Huffman tĩnh ................................................. 15
2.4.1. Nguyên tắc ............................................................................... 15
2.4.2. Thuật toán ................................................................................ 16
2.5. Phương pháp mã hoá LZW .............................................................. 19
2.5.1. Nguyên tắc ............................................................................... 19
2.5.2. Thuật toán ................................................................................ 22


2.6. Phương pháp mã hoá JPEG.............................................................. 24
2.6.1. Nguyên tắc ............................................................................... 24
2.6.2. Thuật toán ................................................................................ 24
2.7. Phương pháp mã hoá JPEG2000 ...................................................... 34
2.7.1. Lịch sử ra đời và phát triển chuẩn JPEG2000 .......................... 34
2.7.2. Các tính năng của JPEG2000 ................................................... 34
2.7.3. Các bước thực hiện nén ảnh theo chuẩn JPEG2000 ................. 35
2.7.4. So sánh chuẩn JPEG2000 với JPEG và các chuẩn nén ảnh
tĩnh khác............................................................................................. 42
CHƯƠNG 3: XÂY DỰNG CHƯƠNG TRÌNH THỬ NGHIỆM ................. 46
3.1. Phát biểu bài toán ............................................................................ 46
3.2. Phương pháp tiến hành .................................................................... 46
3.2.1. Phương pháp Huffman tĩnh ....................................................... 46
3.2.2. Phương pháp JPEG ................................................................... 50
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .................................................... 54
1. Kết luận .............................................................................................. 54
2. Hướng phát triển nghiên cứu .............................................................. 55
TÀI LIỆU THAM KHẢO ............................................................................ 57


CÁC TỪ VIẾT TẮT


Viết
ắt

CC

Tên đầy đủ - Mô tả
Clear Code - mã xóa

EOB

End Of Block - kết thúc khối

EOI

End Of Information- kết thúc thông tin

EZW

Embedded Zerotree Wavelet Encoder - phương pháp mã
hóa dựa trên cơ sở phép mã hóa lũy tiến

ICT

Irreversible Color Transform - biến đổi màu không thuận
nghịch

JPEG

Joint Photographic Expert Group - nhóm các chuyên gia đồ

hoạ phát triển chuẩn này

LZW

Lempe Ziv Welch - nén từ điển

MSE

Mean Square Error - Sai số bình phương trung bình

PSNR

Peak Signal To Noise Ratio - tỉ số tín hiệu trên nhiễu đỉnh

RCT

Reversible Color Transform - biến đổi màu thuận nghịch

RGB

Red Greeb Blue - không gian màu

RLE

Run Length Encoding - mã hoá theo độ dài loạt

SPIHT

Set Partitioning In Hierarchical Trees - phương pháp mã
hoá phân cấp theo phân vùng



DANH MỤC HÌNH
Trang
Hình 1.1: Quá trình xử lý ảnh ..... ................................................................. 4
Hình 1.2: Các bước cơ bản trong một hệ thống xử lý ảnh ............................ 5
Hình 1.3: Biểu diễn một mức xám của ảnh số ............................................. 8
Hình 1.4: Các giai đoạn chính trong xử lý ảnh ............................................. 9
Hình 2.1: Quá trình nén và giải nén ............................................................ 12
Hình 2.2: Quá trình nén ảnh theo chuẩn JPEG ............................................ 24
Hình 2.3: Quá trình giải nén JPEG ............................................................. 25
Hình 2.4: Mô tả giải thuật biến đổi nhanh .................................................. 27
Hình 2.5: Sơ đồ biến đổi Cosin ngược ......................................................... 29
Hình 2.6: Minh họa khối Zig-Zag ............................................................... 33
Hình 2.7: Các bước nén và giải nén JPEG2000 .......................................... 35
Hình 2.8: Ảnh hưởng của độ chói Y tới ảnh ............................................... 36
Hình 2.9: Sơ đồ của phương pháp Lifting 1D áp dụng trong JPEG200
.................................................................................................................... 37
Hình 2.10: Cây tứ phân .............................................................................. 41
Hình 2.11: Mã hoá theo thứ tự từ vùng tần số thấp đến vùng tần số cao ...... 42
Hình 2.12: So sánh chất lượng ảnh được nén bởi JPEG(a) và JPEG2000(b)
.................................................................................................................... 43
Hình 2.13: Tính năng ROI .......................................................................... 45
Hình 3.1: Giao diện chính của phương pháp nén Huffman tĩnh ................. 47
Hình 3.2: Chọn ảnh nén (Huffman tĩnh) ...................................................... 47
Hình 3.3: Ảnh được chọn ........................................................................... 48
Hình 3.4: Chọn vị trí lưu ảnh sau khi nén (Huffman tĩnh) .......................... 48
Hình 3.5: Chọn ảnh để giải nén phương pháp Huffman tĩnh ........................ 49
Hình 3.6: Các thông số của ảnh giải nén (Huffman tĩnh) ............................. 49



Hình 3.7: Chọn vị trí lưu ảnh sau giải nén (Huffman tĩnh)........................... 50
Hình 3.8: Giao diện chính của phương pháp nén JPEG .............................. 51
Hình 3.9: Chọn ảnh nén (JPEG) ................................................................. 51
Hình 3.10 Ảnh nén được chọn (JPEG) ....................................................... 52
Hình 3.11: Chọn vị trí lưu ảnh (JPEG) ....................................................... 52
Hình 3.12: Giao diện sau khi chọn vị trí lưu ảnh (JPEG) ............................ 53


MỞ ĐẦU
1. Lý do chọn đề tài
Khoảng hơn mười năm trở lại đây, phần cứng máy tính và các thiết bị
liên quan đã có sự tiến bộ vượt bậc về tốc độ tính toán, dung lượng chứa,
khả năng xử lý... và giá cả đã giảm đến mức máy tính và các thiết bị liên
quan đến xử lý ảnh đã không còn là thiết bị chuyên dụng nữa. Khái niệm
ảnh số đã trở nên thông dụng với hầu hết mọi người trong xã hội và việc
thu nhận ảnh số bằng các thiết bị cá nhân hay chuyên dụng cùng với việc
đưa vào máy tính xử lý đã trở nên đơn giản.
Trong hoàn cảnh đó, xử lý ảnh là một lĩnh vực đang được quan tâm và
đã trở thành môn học chuyên ngành của sinh viên ngành Công nghệ Thông
tin trong nhiều trường đại học trên cả nước. Xử lý ảnh là một ngành khoa
học mới mẻ so với nhiều ngành khoa học khác nhưng tốc độ phát triển của nó
rất nhanh. Sự ra đời của nó đã tạo ra các kỹ thuật quan trọng ảnh hưởng trực
tiếp đến các lĩnh vực như: Tivi, truyền thông, kỹ xảo đồ họa…
Cùng với sự phát triển đó có những nhu cầu thực tế đặt ra thách thức
đối với các nhà khoa học máy tính càng nhiều. Những công việc, những bài
toán được xử lý theo lối cổ truyền không theo kịp tốc độ phát triển của công
nghệ ngày nay. Trong đó “Nén ảnh” là một phần của xử lý ảnh có ứng
dụng to lớn trong truyền thông và trong lưu trữ, đã có rất nhiều phương pháp
nén ảnh được ra đời và không ngừng được cải tiến để ngày càng hoàn thiện

đem lại hiệu quả nén cao và cho chất lượng ảnh tốt nhất. Do đó em đã lựa
chọn đề tài “MỘT SỐ PHƯƠNG PHÁP NÉN ẢNH VÀ XÂY DỰNG
CHƯƠNG TRÌNH THỬ NGHIỆM”.
2. Mục đích và nhiệm vụ nghiên cứu
Mục đích nghiên cứu: tìm hiểu các phương pháp nén ảnh tĩnh nhằm
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,
1


đối với bức ảnh được nén phần thông tin quan trọng nhất trong bức ảnh sẽ
được 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.
Nhiệm vụ nghiên cứu: tìm hiểu một số phương pháp nén ảnh và xây
dựng chương trình thử nghiệm.
3. Phương pháp và đối tượng nghiên cứu
Phương pháp nghiên cứu:
- Phương pháp khảo cứu lý thuyết: nghiên cứu lý thuyết về các
phương pháp nén ảnh.
- Phương pháp điều tra khảo sát: Thực hiện qua hai bước chính là
nghiên cứu sơ bộ và nghiên cứu chính thức.
+ Nghiên cứu sơ bộ: Thực hiện thông qua phương pháp định tính, sử
dụng kỹ thuật thảo luận nhóm để bổ sung chức năng của bản demo.
+ Nghiên cứu chính thức: Thực hiện thông qua phương pháp nghiên
cứu định lượng, sử dụng kỹ thuật thu thập thông tin qua sách, internet…
Đối tượng nghiên cứu:
- Nghiên cứu các lý thuyết về xử lý ảnh và tìm hiểu các phương pháp
nén ảnh: RLE, Huffman tĩnh, LZW, JPEG, JPEG2000.
- Nghiên cứu các yếu tố thành phần liên quan đến chất lượng ảnh nén
như tỉ lệ nén, mức xám, các điểm ảnh…

- Tìm hiểu phần mềm CSharp.
4. Phạm vi nghiên cứu
Đề tài giới hạn trong việc nghiên cứu tìm hiểu một số phương pháp nén ảnh
tĩnh: RLE, Huffman tĩnh, LZW, JPEG, JPEG2000 và xây dựng chương trình
thử nghiệm với các định dạng ảnh: .png, .bmp, .jpg, .tif, .tiff.
5. Ý nghĩa khoa học và thực tiễn của đề tài
Ý nghĩa khoa học: lý thuyết nén ảnh ra đời, phát triển và có cơ sở khoa
học vững chắc, nghiên cứu sẽ góp phần chứng minh thêm tính đúng đắn của
2


lý thuyết nén ảnh. Hiện nay nén ảnh là một lĩnh vực được các chuyên gia
nghiên cứu trên thế giới quan tâm và phát triển.
Ý nghĩa thực tiễn: chương trình thử nghiệm nếu thành công sẽ đóng
góp một phần nhỏ trong việc giảm dung lượng của những bức ảnh trước khi
được truyền đi trên mạng internet mà vẫn giữ được chất lượng hình ảnh.
6. Cấu trúc khóa luận
Ngoài phần mở đầu và kết luận khóa luận còn có những nội dung sau:
Chương 1: Tổng quan về xử lý ảnh – Chương này trình bày một số
kiến thức chung về xử lý ảnh, các bước cơ bản trong một hệ thống xử lý ảnh,
một số khái niệm về nén ảnh, giải nén ảnh, mức xám, pixel…
Chương 2: Các phương pháp nén ảnh – Trong chương này khóa luận
trình bày cách phân loại các phương pháp nén ảnh, quá trình nén và giải nén.
Nêu nguyên tắc và thuật toán một số phương pháp nén ảnh RLE, Huffman
tĩnh, LZW, JPEG, JPEG2000 là nội dung chính được trình bày trong khóa
luận.
Chương 3: Xây dựng chương trình thử nghiệm – Từ những kiến thức
lý thuyết đã nghiên cứu, khóa luận đã vận dụng và cài đặt thử nghiệm chương
trình nén ảnh. Chương trình được xây dựng trên ngôn ngữ CSharp đã hoàn
thành và đạt được những thành công nhất định dựa trên thuật toán nén bằng

phương pháp Huffman tĩnh, phương pháp nén JPEG với các định dạng ảnh:
.png, .bmp, .tif, .tiff, .jpg.
7. Kết quả đạt được
Xây dựng thành công chương trình thử nghiệm với phương pháp nén,
giải nén bằng thuật toán Huffman tĩnh và phương pháp nén JPEG. Áp dụng
nén với các định dạng ảnh tĩnh: .png, .bmp, .tiff, .tif, .jpg. Hướng phát triển
nghiên cứu trong tương lai là: thực hiện giải nén đối với phương pháp JPEG,
ứng dụng nén cho các dạng dữ liệu khác: video, âm thanh, văn bản… đi sâu
nghiên cứu tìm hiểu các họ của Wavelet.
3


CHƯƠNG 1: TỔNG QUAN VỀ XỬ LÝ ẢNH
1.1. TỔNG QUAN VỀ XỬ LÝ ẢNH
1.1.1. Xử lý ảnh
Con người thu nhận thông tin qua các giác quan, trong đó thị giác
đóng vai trò quan trọng nhất. Những năm trở lại đây với sự phát triển của
phần cứng máy tính, xử lý ảnh và đồ hoạ đó phát triển một cách mạnh mẽ
và có nhiều ứng dụng trong cuộc sống. Xử lý ảnh và đồ hoạ đóng một vai
trò quan trọng trong tương tác người máy.
Quá trình xử lý ảnh được xem như là quá trình thao tác ảnh đầu vào
nhằm cho ra kết quả mong muốn. Kết quả đầu ra của một quá trình xử lý
ảnh có thể là một ảnh “tốt hơn” hoặc một kết luận.
Ảnh “tốt hơn”
Ảnh

XỬ LÝ ẢNH
Kết luận
Hình 1.1: Quá trình xử lý ảnh


Ảnh có thể xem là tập hợp các điểm ảnh và mỗi điểm ảnh được xem
như là đặc trưng cường độ sáng hay một dấu hiệu nào đó tại một vị trí nào
đó của đối tượng trong không gian và nó có thể xem như một hàm n biến
P(c1, c2,..., cn). Do đó, ảnh trong xử lý ảnh có thể xem như ảnh n chiều.

4


Sơ đồ tổng quát của một hệ thống xử lý ảnh:
Hệ quyết
định
Thu nhận ảnh
(Scanner,
Camera,
Sensor)

Tiền xử
lý

Trích
chọn đặc
điểm

Đối sánh rút
ra kết luận

Hậu xử
lý

Lưu trữ


Hình 1.2: Các bước cơ bản trong một hệ thống xử lý ảnh
Các thiết bị thu nhận ảnh:
Các thiết bị thu nhận ảnh bao gồm camera, scanner các thiết bị thu
nhận này có thể cho ảnh đen trắng.
Các thiết bị thu nhận ảnh có 2 loại chính ứng với 2 loại ảnh thông
dụng Raster, Vector.
Các thiết bị thu nhận ảnh thông thường Raster là camera các thiết bị
thu nhận ảnh thông thường Vector là sensor hoặc bàn số hoá Digitalizer
hoặc được chuyển đổi từ ảnh Raster.
Nhìn chung các hệ thống thu nhận ảnh thực hiện 1 quá trình:
- Cảm biến: biến đổi năng lượng quang học thành năng lượng điện.
- Tổng hợp năng lượng điện thành ảnh.
Tiền xử lý: Sau bộ thu nhận ảnh có thể nhiễu độ tương phản thấp nên cần đưa
vào bộ tiền xử lý để nâng cao chất lượng. Có hai phương pháp cơ bản được sử
dụng trong tiền xử lý ảnh. Phương pháp thứ nhất dựa vào các kĩ thuật tiền xử
lý trong miền không gian và phương pháp thứ hai sử dụng các khái niệm
trong miền tần số thông qua biến đổi Fourier.
- Phương pháp tiền xử lý trong miền không gian: thuật ngữ miền không
gian ở đây muốn nói đến số lượng pixel tạo nên một hình ảnh. Các phương
pháp tiền xử lý trong miền không gian là các thủ tục tác động trực tiếp lên các
5


pixel tạo lên hình ảnh đó. Một trong những kĩ thuật được sử dụng rộng rãi
nhất là sử dụng mặt nạ nhân chập.
- Phương pháp tiền xử lý trong miền tần số: thuật ngữ miền tần số ở
đây có nghĩa là tổng số pixel phức được tạo ra từ việc lấy biến đổi Fourier
hình ảnh. Khái niệm “tần số” thường được sử dụng trong giải thích biến đổi
Fourier và suy ra từ bản chất của biến đổi Fourier là tổ hợp của các hàm sin

phức. Phương pháp này đóng vai trò rất quan trọng trong các lĩnh vực như
phân tích chuyển động của một vật và miêu tả vật.
Chức năng chính của bộ tiền xử lý là lọc nhiễu.
Trích chọn đặc điểm:
Các đặc điểm của đối tượng được trích chọn tuỳ theo mục đích nhận
dạng trong quá trình xử lý ảnh. Có thể nêu ra một số đặc điểm của ảnh
sau đây:
+ Đặc điểm không gian: Phân bố mức xám, phân bố xác suất, biên
độ, điểm uốn...
+ Đặc điểm biến đổi: Các đặc điểm loại này được trích chọn bằng việc
thực hiện lọc vùng (zonal filtering). Các bộ vùng được gọi là “mặt nạ đặc
điểm” (feature mask) thường là các khe hẹp với hình dạng khác nhau (chữ
nhật, tam giác, cung tròn...)
+ Đặc điểm biên và đường biên: Đặc trưng cho đường biên của đối
tượng và do vậy rất hữu ích trong việc trích trọn các thuộc tính bất biến
được dùng khi nhận dạng đối tượng. Các đặc điểm này có thể được trích
chọn nhờ toán tử gradient, toán tử la bàn, toán tử Laplace, toán tử “chéo
không” (zero crossing)…
Việc trích chọn hiệu quả các đặc điểm giúp cho việc nhận dạng các
đối tượng ảnh chính xác, với tốc độ tính toán cao và dung lượng nhớ lưu
trữ giảm xuống.

6


Hậu xử lý:
Các kĩ thuật hậu xử lý bao gồm: rút gọn số lượng điểm biểu diễn, xấp
xỉ đa giác bởi các hình cơ sở, biến đổi Hough.
- Rút gọn số lượng điểm biểu diễn là kết quả của phần dò biên hay trích
xương thu được một dãy các điểm liên tiếp và bỏ bớt các điểm thu được để

giảm thiểu không gian lưu trữ và thuận tiện cho việc đối sánh.
- Xấp xỉ đa giác bởi các hình ảnh cơ sở là các đối tượng hình học được
phát hiện thường thông qua các kĩ thuật dò biên, kết quả tìm được này là các
đường biên xác định đối tượng. Đó là một dãy các điểm liên tiếp đóng kín, sử
dụng các thuật toán đơn giản hóa như Douglas Peucker, Band Width,
Angle… ta sẽ thu được một đa giác xác định đối tượng dấu. Vấn đề là ta cần
xác định xem đối tượng có phải là đối tượng cần tách hay không? Như ta đã
biết một đa giác có thể có hình dạng tựa như một hình cơ sở, có thể có nhiều
cách tiếp cận xấp xỉ khác nhau. Cách xấp xỉ dựa trên các đặc trưng cơ bản
sau: đặc trưng toàn cục, đặc trưng địa phương. Việc xấp xỉ tỏ ra rất có hiệu
quả đối với một số hình phẳng đặc biệt như tam giác, đường tròn, hình chữ
nhật, hình vuông, hình elllipse, hình tròn và một đa giác mẫu.
- Biến đổi Hough bao gồm biến đổi Hough cho đường thẳng và biến
đổi Hough cho đường thẳng trong tọa độ cực.
Một số khái niệm cơ bản
* Ảnh và điểm ảnh: Điểm ảnh được xem như là dấu hiệu hay cường độ
sáng tại 1 toạ độ trong không gian của đối tượng và ảnh được xem như là
1 tập hợp các điểm ảnh.
* Mức xám, màu: Là số các giá trị có thể có của các điểm ảnh của ảnh.
1.1.2. Giới thiệu về ảnh số và xử lý ảnh số
a. Ảnh số
Ảnh có thể biểu diễn dưới dạng tín hiệu tương tự hoặc tín hiệu số.
Trong biểu diễn số của các ảnh đa mức xám, một ảnh được biểu diễn dưới
7


dạng một ma trận hai chiều. Mỗi phần tử của ma trận biểu diễn cho mức xám
hay cường độ của ảnh tại vị trí đó. Mỗi phần tử trong ma trận được gọi là một
phần tử ảnh, thông thường kí hiệu là PEL (Picture Element) hoặc là điểm
ảnh (Pixel).

- Với ảnh đa cấp xám: Nếu dùng 8 bit (1 byte) để biểu diễn mức
xám, thì số các mức xám có thể biểu diễn được là 28 hay 256. Mỗi mức
xám được biểu diễn dưới dạng là một số nguyên nằm trong khoảng từ 0 đến
255, với mức 0 biểu diễn cho mức cường độ đen nhất và 255 biểu diễn
cho mức cường độ sáng nhất.
- Với ảnh màu: Cách biểu diễn cũng tương tự như với ảnh đen trắng,
chỉ khác là các số tại mỗi phần tử của ma trận biểu diễn cho ba màu riêng
rẽ gồm: đỏ (red), lục (green) và lam (blue). Để biểu diễn cho một điểm
ảnh màu cần 24 bit, 24 bit này được chia thành ba khoảng 8 bit. Mỗi khoảng này
biểu diễn cho cường độ sáng của một trong các màu chính.

Pixel or
PEL

Độ sáng trung bình trong mỗi
hình chữ nhật = giá trị một điểm ảnh

Hình 1.3: Biểu diễn của một mức xám của ảnh số
b. Xử lý ảnh số
Xử lý ảnh số có rất nhiều ứng dụng như làm nổi các ảnh trong y học,
khôi phục lại ảnh do tác động của khí quyển trong thiên văn học, tăng cường
độ phân giải của ảnh truyền hình mà không cần thay đổi cấu trúc bên trong
8


của hệ thống chuyển tải, nén ảnh trong khi truyền đi hoặc lưu trữ.
Các giai đoạn chính trong xử lý ảnh có thể được mô tả trong hình
sau:

Lưu trữ

CAMERA
Thu nhận
ảnh

Phân
tích ảnh

Số hóa

Nhận dạng
ảnh

SENSOR
Hệ quyết
định

Lưu trữ

Hình 1.4: Các giai đoạn chính trong xử lý ảnh.
1.2. NÉN ẢNH
• Pixel (picture element): phần tử ảnh
Ảnh trong thực tế là một ảnh liên tục về không gian và về giá trị
độ sáng. Để có thể xử lý ảnh bằng máy tính cần thiết phải tiến hành số hoá
ảnh. Như vậy một ảnh là một tập hợp các pixel. Mỗi pixel là gồm một cặp
toạ độ x, y và màu. Cặp toạ độ x, y tạo nên độ phân giải (resolution). Màn
hình máy tính có nhiều loại với độ phân giải khác nhau: 320x200, 640x350,
800x600, 1024x768,...
• Mức xám (Graylevel)
Mức xám là kết quả sự mã hoá tương ứng của mỗi cường độ sáng
của mỗi điểm ảnh với một giá trị số – kết quả của quá trình lượng hoá.

• Dữ liệu
Trong một bài toán, dữ liệu bao gồm một tập các phần tử cơ sở mà ta
gọi là dữ liệu nguyên tử. Nó có thể là một chữ số, một ký tự,... nhưng cũng
9


có thể là một con số, một từ,... điều đó phụ thuộc vào từng bài toán.
• Nén dữ liệu
Nén dữ liệu là quả trình giảm dung lượng thông tin “dư thừa” trong dữ
liệu gốc và làm cho lượng thông tin thu được sau nén thường nhỏ hơn dữ
liệu gốc rất nhiều. Do vậy, tiết kiệm được bộ nhớ và giảm thời gian trao đổi
dữ liệu trên mạng thông tin mà lại cho phép chúng ta khôi phục lại dữ liệu
ban đầu.
• Tỷ lệ nén
Tỷ lệ nén là một trong các đặc trưng quan trọng của mọi phương
pháp nén. Tỷ lệ nén được định nghĩa như sau:
Tỷ lệ nén = (1/r)*100%
với r là tỷ số nén được định nghĩa:
r = kích thước dữ liệu gốc / kích thước dữ liệu nén.
Như vậy:
hiệu suất nén = (1- tỷ lệ nén)*100%.
Đối với ảnh tĩnh, kích thước chính là số bit biểu diễn toàn bộ bức ảnh.
Đối với ảnh video, kích thước chính là số bit để biểu diễn một
khung hình video (video frame).
• 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. 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:
+ Dư thừa thông tin về không gian: trong một bức ảnh luôn tồn tại
sự tương quan giữa các điểm ảnh cạnh nhau.

+ Dư thừa thông tin về cấp xám: là dư thừa dựa vào sự tương quan
giữa các màu sắc cạnh nhau.
• Giải nén là quá trình xử lý dữ liệu nén trở về dữ liệu gốc

10


CHƯƠNG 2: CÁC PHƯƠNG PHÁP NÉN ẢNH
2.1. Phân loại các phương pháp nén ảnh
2.1.1. Phân loại dựa vào nguyên lý nén
Nén bảo toàn thông tin (losses compression): bao gồm các phương
pháp nén mà sau khi giải nén sẽ thu đựơc chính xác dữ liệu gốc. Tuy
nhiên nén bảo toàn thông tin chỉ đạt hiệu quả nhỏ so với phương pháp nén
không bảo toàn thông tin.
Nén không bảo toàn thông tin (lossy compression): bao gồm các
phương pháp nén sau khi giải nén sẽ không thu được dữ liệu như bản
gốc. Các phương pháp này được gọi là “tâm lý thị giác” đó là lợi dụng tính
chất của mắt người chấp nhận một số vặn xoắn trong ảnh khi khôi phục lại.
Phương pháp này luôn đem lại hiệu quả cao do loại bỏ đi những thông tin dư
thừa không cần thiết.
2.1.2. Phân loại dựa vào cách thức thực hiện nén
Phương pháp không gian (Spatial Data Compression): các phương
pháp này thực hiện nén bằng cách 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 (Transform Coding): gồm các phương
pháp tác động lên sự biến đổi của ảnh gốc chứ không tác động trực tiếp.
2.1.3. Phân loại dựa vào lý thuyết mã hoá
Các phương pháp nén thế hệ thứ nhất: gồm các phương pháp có mức
độ tính toán đơn giản như lấy mẫu, gán từ mã,…
Các phương pháp nén thế hệ thứ hai: gồm các phương pháp dựa

vào mức độ bão hoà của tỷ lệ nén bằng cách sử dụng các phép toán tổ hợp
đầu ra một cách hợp lý hoặc sử dụng biểu diễn ảnh như: phương pháp kim
tự tháp Laplace, phương pháp dựa vào vùng gia tăng, phương pháp tách hợp.

11


2.2. Quá trình nén và giải nén
Quá trình nén và giải nén gồm 2 công đoạn:
Nén: dữ liệu gốc qua bộ mã hoá dữ liệu, bộ mã hoá này thực hiện nén
dữ liệu đến một mức thích hợp cho việc lưu trữ và truyền dẫn thông tin. Quá
trình này sẽ thực hiện việc loại bỏ hay cắt bớt những dư thừa của ảnh để thu
được thông tin cần thiết nhưng vẫn đảm bảo được chất lượng ảnh.
Giải nén: dữ liệu nén đi qua bộ giải mã dữ liệu, bộ giải mã sẽ thực
hiện giải nén để thu được dữ liệu gốc ban đầu. Việc giải nén này thường phải
dựa vào các thông tin đi kèm theo dữ liệu nén, tuỳ thuộc vào kiểu nén hay
phương pháp nén mà dữ liệu giải nén được có hoàn toàn giống với dữ liệu
gốc ban đầu hay không.
Tóm lại quá trình nén và giải nén dữ liệu có thể mô tả một cách tóm
tắt theo sơ đồ dưới đây:
Quá trình nén
Dữ liệu gốc

Dữ liệu nén
Quá trình giải nén

Hình 2.1: Quá trình nén và giải nén
2.3. Phương pháp mã hoá độ dài loạt RLE
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ị.
2.3.1. 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á
12


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ị)
(L, C). Trong đó: L là số các từ kế cận giống nhau, C là kí tự được lặp lại.
Ví dụ 1: 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 = 20/ 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:
Cho một chuỗi nguồn d:
d=000000000000000111111111100000000001111111111000000000000000

Ta sẽ 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).
Đố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ụ 2: 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 3 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
13


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ụ 3: 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à “+” 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ụ 4:
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)
2.3.2. Thuật toán
a. Thuật toán nén RLE
Input: Tệp tin nguồn f
Output: Tệp tin nén fn
Bước 1:

+ Mở tệp tin nguồn f (để đọc)
+ Mở tệp tin nén fn (để ghi)

Bước 2:

+ Đặt L=1; // L là một số nguyên
14


+ Đọc kí tự trong bản mã gán vào C1;
Bước 3: Khi nào C1 không phải là ký tự cuối cùng trong tệp f thì thực
hiện:
b1. Đọc kí tự tiếp theo trong bản mã gán vào C2.
b2. Kiểm tra, nếu C1 = C2 thì:
+ Tăng L=L+1;
+ Quay lên thực hiện tiếp b1;
Ngược lại thì:
+ Ghi cặp (L, C1) ra tệp nén fn.
+ Quay lên thực hiện tiếp Bước 3:
Ngược lại, nếu (C1 là ký tự cuối cùng trong tệp f mã) thì thực hiện Bước 4
Bước 4: Kết thúc.

b. Thuật toán giải nén RLE
Input: Tệp tin nguồn nén fn
Output: Tệp tin giải nén fg
+ Mở tệp tin nén fn (để đọc)

Bước 1:

+ Mở tệp tin giải nén fg (để ghi)
Bước 2: Khi nào cặp (L,C) không phải là ký tự cuối cùng trong tệp fn
thì thực hiện:
b1. Đọc cặp (L,C) trong tệp nén fn
b2. + For i=1 to L do ghi ký tự C ra tệp giải nén fg
+ Quay lên thực hiện tiếp Bước 2:
Ngược lại (L, C là cặp ký tự cuối cùng trong tệp nén fc) thì
thực hiện Bước 3
Bước 3: Kết thúc.
2.4. Phương pháp mã hoá Huffman tĩnh
2.4.1. Nguyên tắc
Phương pháp mã hoá Huffman tĩnh là phương pháp dựa vào mô hình
15


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 và thỏa mãn tính chất frefix (Không có từ mã nào là tiền tố của
từ mã khác). Như vậy với cách thức này ta đã làm giảm chiều dài của từ mã
bằng cách biến đổi chiều dài các bit tuy nhiên cũng có trường hợp bị thiệt một
ít bit khi tần suất xuất hiện của kí tự đó thấp.
2.4.2. Thuật toán

a) Thuật toán tạo mã Huffman tĩnh
Input: Tệp tin nguồn chưa nén fn
Output: Tệp tin nén fg
Bắt đầu: + Mở tệp tin nguồn để đọc
+ Mở tệp tin nén để ghi
Bước 1: Thống kê tạo ra bảng tần suất xuất hiện của các ký hiệu có
trong nguồn.
Bước 2: Sắp xếp các ký hiệu trong bảng theo chiều không giảm hoặc
không tăng.
Bước 3: Bắt đầu với một rừng các cây (coi mỗi ký tự trong bảng là 1
cây): Tìm hai cây có trọng số nhỏ nhất ghép lại làm một, trọng số của cây mới
bằng tổng trọng số của hai cây con đem ghép.
Bước 4: Nếu số lượng cây trong danh sách còn lớn hơn một thì
Thực hiện bước 3, ngược lại thì thực hiện bước 5.
Bước 5: Xuất phát từ gốc đi tới các nút lá trên cây và tạo cây nhị phân
với qui ước đi sang trái ghi mã 0, đi bên phải ghi mã 1.
Bước 6: Thực hiện nén xâu đã cho
Bước 7: Kết thúc

16


Ví dụ 5: Nén chuỗi “go go gophers”
Bước 1:
Kí tự
g
o
..
e
h

p
r
s

Tần xuất
3/13
3/13
2/13
1/13
1/13
1/13
1/13
1/13

Từ mã

Bước 2:
‘g’

‘o’

‘. .’

‘e’

‘h’

‘p’

‘r’


‘s’

3

3

2

1

1

1

1

1

Bước 3,4:

13
0

1

7
0

1


4
1
6

0

2

3

2

1

0

1

0

1

0

‘g’

‘o’

‘. .’


‘e’

‘h’

‘p’

‘r’

‘s’

3

3

2

1

1

1

1

1

17

0


1


Bước 5: Xuất phát từ gốc đi tới các nút lá trên cây và tạo cây nhị phân với qui
ước đi sang trái ghi mã 0, đi bên phải ghi mã 1 ta được.
Kí tự
g
o
Dấu cách
e
h
p
r
s

Tần xuất
3/13
3/13
2/13
1/13
1/13
1/13
1/13
1/13

Từ mã
11
10
011

010
0011
0010
0001
0000

Bước 6: Xâu “ go go gophers” sẽ được mã hoá như sau (dấu - cho dễ đọc)
11-10-011-11-00-011-11-00-0010-0011-010-0001-0000
Bước 7: Kết thúc.
Quá trình giải nén cũng khá đơn giản được tiến hành theo chiều ngược
lại. 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 lưu trữ trong cấu trúc đầu của tệp nén cùng với dữ liệu nén).
b. Thuật toán giải nén Huffman tĩnh
Bước 1: Đặt u = “”, xb = “”;
Bước 2: Đọc lần lượt từng bit trong tập tin nén ->u; xb= xb + u
Bước 3: Duyệt trong bảng tần xuất đã được xác định
Nếu thấy có mã = xb thì
Ghi ký tự tương ứng trong bảng tần xuất ra tệp giải nén
Gán xb = “”, u = “”;
Ngược lại sang Bước 4
Bước 4: Nếu chưa hết tập tin nén thì thực hiện Bước 2
Ngược lại thực hiện Bước 5.
Bước 5: Kết thúc thuật toán.
Ví dụ 6: Giải nén đoạn mã: 1110011110001111000010001101000010000
Bước 1: Đặt u = “”, xb = “”;
18