Đồ á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 :
1MỞ ĐẦ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à
phương pháp nén ảnh JPEG2000 dựa trên biến đổi Wavelet với những đặc
tính vượt trội so với các chuẩn nén trước đó đem lại hiệu quả nén cao , cho
ảnh nén chất lượng t
ốt và nhiều những ưu điểm khác mà các chuẩn nén
trước đó không thể có.
- 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.
ảnh
Số
Phân
tích ảnh
Hệ quyết
định
Nhận dạng
Lư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
I.2.Mục đích và sự cần thiết của “ nén ảnh ”: 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
đồ 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,
•
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*%
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 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
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.
II.1.3.Cách 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.
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
Tỷ số nén = 20/ 8 = 2.5
Quá trình nén
Quá trình giải nén
Dữ liệu
ố
Dữ liệ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 :
10
Đố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:
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
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à “+” ta có : 5 8 4 +7 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)
II.2.2.Thuật toán: Thuật toán như sau :
Đồ á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 :
12•
{
pRLEBits[dst_index++] = 1;
pRLEBits[dst_index++] = pSrcBits[src_index];
src_index++;
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 :
13
if(pSrcBits[src_index]==pSrcBits[src_index+1]) goto
tate_compress;
if ( EndOfLine(src_index+1))
{
pRLEBits[dst_index++] = 1;
pRLEBits[dst_index++] = pSrcBits[src_index++];
pRLEBits[dst_index++] = 1;
pRLEBits[dst_index++] = pSrcBits[src_index++];
goto end_of_line;
}
if (pSrcBits[src_index+1] == pSrcBits[src_index+2])
{
pRLEBits[dst_index++] = 1;
pRLEBits[dst_index++] = pSrcBits[src_index++];
goto state_compress;
}
else
goto state_no_compress;
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] )
continue;
if(EndOfLine(src_index+counter+2) ||
SrcBits[src_index+counter+1] != pSrcBits[src_index+counter+2]
)
continue;
else
{
if ( counter > 2) counter--;
pRLEBits[dst_index++] = 0;
pRLEBits[dst_index++] = counter+1;
for (i = counter+1; i > 0; i--)
pRLEBits[dst_index++] = pSrcBits[src_index++];
Đồ á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 :
15
if ( 0 != ((counter+1) % 2) ) pRLEBits[dst_index++];
goto state_compress;
}
}
pRLEBits[dst_index++] = 0;
pRLEBits[dst_index++] = counter;
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)
{
switch (SecondByte)
{
case 0:
x = 0;
y++;
break;
case 1:
return TRUE;
case 2:
if (!fil.read((char*)&data, 2)) return FALSE;
x += LOBYTE(data);
y += HIBYTE(data);
break;
default:
char ch;
for (BYTE i = 0; i < SecondByte; i++)
{
if (!fil.get(ch)) 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
hợp bị thiệt 1 ít bit khi tần suất là rất thấp.
II.3.2. Thuật toán:•
Thuật toán mã hoá Huffman gồm 2 bước chính:
•
Bước một:
Tính tần suất của các ký tự trong dữ liệu gốc bằng cách 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ã và tính toán tần
suất. Tiếp theo sau là sắp xếp lại bảng mã theo thứ tự tần suất giảm dần.
•
Bước hai:
Duyệt bảng tấn suất từ cuối lên đầu để thực hiện ghép hai phần tử
152
323
412
226
385
602
92
112
87
Bảng tần suất sắp xếp giảm dần Kí tự Xác suất (%)
0
9
3
0.3905
0.1535
0.1051
0.0982
0.0824
0.0577
0.0457
0.03880.0286
0.3905
0.1535
0.1051
0.0982
0.0824
0.0674
0.0577 0.0457
0.3906
0.1051
0.1034
0.0982
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.
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
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
001
011
0001
0100
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ã
pDesPtr += sizeof(DWORD);
*pDesPtr = nNodeCount-1;
pDesPtr += sizeof(BYTE);
for(nCount = 0; nCount < nNodeCount; nCount++)
{
memcpy(pDesPtr, &nodes[nCount], nNodeSize);
pDesPtr += nNodeSize;
}
qsort(nodes, 256, sizeof(CHuffmanNode), asciiCompare);
int nDesIndex = 0;
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;
}
Đồ á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 :
25
pDes[nDesIndex++] = pNode->byAscii;
}
Copyright: Tài liệu đại học ©