Luận văn
Tìm hiểu một số phương
pháp nén ảnh
Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh
Sinh viên thực hiện : Tạ Minh Thắng CT 702
Trang :
1

MỞ ĐẦU

Ngày nay, cùng với sự phát triển không ngừng của khoa học và công
nghệ thì máy tính đóng vai trò ngày càng quan trọng và không thể thiếu
trong cuộc sống xã hội loài người. Việc trao đổi thông tin của con người
trong tất cả các ngành, các lĩnh vực của đời sống ngày càng trở nên cần thiết
cùng với sự ra đời và phát triển của mạng Internet.
Xử lý ảnh là một ngành khoa học còn tương đối mới mẻ so với nhiều
ngành khoa học khác như
ng nó đang được tập trung nghiên cứu và phát
triển vì những ứng dụng thực tiễn của nó trong nhiều ngành , lĩnh vực khác
nhau. 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. Trong đồ án tốt nghiệp
“TÌM HIỂU MỘT SỐ PHƯƠNG PHÁP NÉN ẢNH” được sự hướng dẫn
của PGS .TS . Ngô Quốc Tạo em đã đi sâu nghiên cứu một số phương pháp
nén ảnh phổ biến như : mã loạt dài RLE, HUFFMAN, LZW, JPEG và

đượ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à 2
8
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
Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh
Sinh viên thực hiện : Tạ Minh Thắng CT 702
Trang :
3
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.
Số
Phân
t
í
ch
ả
nh
Hệ quyết
định
Nhận
d
ạn
gLưu
t
r
ữ

Lưu
Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh
Sinh viên thực hiện : Tạ Minh Thắng CT 702
Trang :
4
5
đồ hoạ qua đường điện thoại (Fax), nén ảnh trong y tế và truyền hình
cáp….Chính sự ứng dụng trong nhiều lĩnh vực của nén ảnh cùng với sự tiến
bộ trong lĩnh vực vi điện tử dẫn đến sự ra đời các chuẩn né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 hay dư thừa về thời gian:

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

• Dư thừa thông tin về thời gian : Trong một chuỗi ảnh video, tồn tại sự
tương quan giữa các điểm ảnh của các frame khác nhau .

I.3.Các khái niệm cơ bản:
• 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: 320 x 200, 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

Đố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 tốt nghiệp Tìm hiểu một số phương pháp nén ảnh
Sinh viên thực hiện : Tạ Minh Thắng CT 702
Trang :
7 CHƯƠNG II:
CÁC PHƯƠNG PHÁP NÉN ẢNH

II.1.Cách phân loại các phương pháp nén ảnh: II.1.1.Cách 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.


II.1.4.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.
Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh
Sinh viên thực hiện : Tạ Minh Thắng CT 702
Trang :
9
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:

Hình 2.1 : Quá trình nén và giải nén
II.2.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ị.
II.2.1.Nguyên tắc :

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

Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh
Sinh viên thực hiện : Tạ Minh Thắng CT 702
Trang :
11
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

12
• 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 – o f- bitmap)
II.2.3.Một số thủ tục chương trình :• Chương trình nén theo phương pháp RLE :
void CRLE::CompressInRLE8(BYTE*pSrcBits,CByteArray& pRLEBits, int&
RLE_size)
{
int line;
int src_index = 0, dst_index = 0, counter, i;
for ( line = 0; line < m_dib.dsBmih.biHeight; line++)
{
state_start:
if ( EndOfLine(src_index))
{
pRLEBits[dst_index++] = 1;

break;
if ( EndOfLine(src_index+counter) )
{
pRLEBits[dst_index++] = counter+1;
pRLEBits[dst_index++] = pSrcBits[src_index];
src_index += counter +1;
goto end_of_line;
}
Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh
Sinh viên thực hiện : Tạ Minh Thắng CT 702
Trang :
14
}
pRLEBits[dst_index++] = counter;
pRLEBits[dst_index++] = pSrcBits[src_index];
src_index += counter;
goto state_start;
state_no_compress:
for (counter = 2; counter <= 254; counter++)
{
if ( EndOfLine(src_index+counter) ) {
pRLEBits[dst_index++] = 0;
pRLEBits[dst_index++] = counter + 1;
for (i = counter + 1; i > 0; i )
pRLEBits[dst_index++]=pSrcBits[src_index++];
if ( 0 != ((counter+1) % 2) ) pRLEBits[dst_index++];
goto end_of_line;
}
if(EndOfLine(src_index+counter+1) ||
pSrcBits[src_index+counter] != pSrcBits[src_index+counter+1] )

int pad = 4 - (src_index%4);
src_index += pad;
}
pRLEBits[dst_index++] = 0;
pRLEBits[dst_index++] = 0;
}

pRLEBits[dst_index++] = 0;
pRLEBits[dst_index++] = 1;
RLE_size = dst_index;
}

• Chương trình giải nén phương pháp RLE :
BOOL CRLE::DecRLE8(ifstream &fil, BYTE *pDest)
{
DWORD x, y, paddedwidth;
Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh
Sinh viên thực hiện : Tạ Minh Thắng CT 702
Trang :
16
paddedwidth =BMPWIDTHBYTES(pInfo->biWidth*pInfo-> biBitCount);
BYTE FirstByte, SecondByte;
WORD data;
x = y = 0;
while (!fil.eof())
{
if (!fil.read((char*)&data, 2)) return FALSE;
FirstByte = LOBYTE(data);
SecondByte = HIBYTE(data);
if (FirstByte == 0)

{
for (BYTE i = 0; i < FirstByte; i++)
pDest[paddedwidth * y + x++] = SecondByte;
}
}
return FALSE;
}

II.3.Phương pháp mã hoá Huffman:

II.3.1. Nguyên tắc:
Phương pháp mã hoá 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 tốt nghiệp Tìm hiểu một số phương pháp nén ảnh
Sinh viên thực hiện : Tạ Minh Thắng CT 702
Trang :
18
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

19
1
2
3
4
5
6
7
8
9
152
323
412
226
385
602
92
112
87

Bảng tần suất sắp xếp giảm dần

0.6100
0.3905
0
6
5
2
4
1
8
7
9
3
0.3905
0.1535
0.1051
0.0982
0.0824
0.0577
0.0457
0.0388

0.0286
0.3905
0.1535
0.1051
0.0982
0.0824
0.0674
0.0577


0.0235

0.0222
0.0577
0.0824
0.0982
0.1051
0.1535
Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh
Sinh viên thực hiện : Tạ Minh Thắng CT 702
Trang :
20 Mô tả : Ta tiến hành hợp nhất hay cộng 2 tần suất nhỏ nhất ở cuối
bảng để thu được giá trị tần suất mới sau đó đưa giá trị này trở lại bảng tần
suất ban đầu đã bỏ đi 2 tần suất thành phần tạo thành nó. Sau khi đưa giá trị
mới vào bảng ta phải tiến hành sắp xếp lại toàn bộ bảng , lúc này số
lượng
tần suất chỉ còn là n-1 nếu ban đầu số lượng tần suất là n. Tiếp tục thực hiện
lần lượt theo thứ tự như trên cho đến khi nào số lượng tần suất chỉ còn lại
duy nhất 1 giá trị.

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.

Hình 2.3 : Quá trình tạo cây nhị phân
Ta có cây mã Huffman tương ứng như sau : 0 1
0
Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh
Sinh viên thực hiện : Tạ Minh Thắng CT 702
Trang :

00000
01010
01011
000010
000011 Như vậy với ví dụ sau đây ta có thể tiến hành mã hoá như sau:
Chuỗi nguồn : 00000000006666693333 Æ kích thước = 20*8=160 bit
Đồ án tốt nghiệp Tìm hiểu một số phương pháp nén ảnh
Sinh viên thực hiện : Tạ Minh Thắng CT 702
Trang :
23
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ị 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.
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 .

II.3.3.Một số thủ tục chương trình :
• Chương trình nén phương pháp HUFFMAN :


for(nCount = 0; nCount < nSrcLen; nCount++)
{
*(DWORD*)(pDesPtr+(nDesIndex>>3))|=nodes[pSrc[nCount]].dwCode<<
(nDesIndex&7);
nDesIndex += nodes[pSrc[nCount]].nCodeLength;
}
nDesLen = (pDesPtr-pDes)+(nDesIndex+7)/8;
pDes = (BYTE*)realloc(pDes, nDesLen);

return true;
}