Bài giảng Xử lý ảnh - Trần Quang Đức

B = {z | ( ⌢B)z∩A ≠∅} = {z | (B)z ⊆ A}A!B 
A⊕ B A!B 
Phép mở 
A !B =             ⊕B
A !BA!B 
(A!B) 
Phép mở xóa bỏ những đoạn mảnh, loại bỏ nhiễu nhưng làm tăng số đoạn đứt gãy 
Phép đóng 
A•B = (A⊕ B)!B 
A !BA!B 
Phép đóng có thể làm trơn biên ảnh và kết nỗi các vùng của cùng một đối tượng. 
Tách biên ảnh 
β(A)=A - (A!B) 
Lấp đầy vùng ảnh 
Xk = (Xk−1⊕ B)∩Ac,    k =1,2,3...
Lặp quá trình trên đến khi Xk-1=Xk 
B Ac X0 A 
X1 X2 X7 X7∪A
Lấp đầy vùng ảnh 
Ảnh gốc Lấp đầy một vùng ảnh Lấp đầy vùng ảnh 
MÃ HÓA VÀ NÉN ẢNH 
Trần Quang Đức 
Dung lượng thông tin 
•  Một trang văn bản: 2 KB. 
•  Một ảnh màu (800x600x24): 1,4 MB 
•  30 phút âm thanh thoại số (8 kHz, 8 bits): 14 MB 
•  30 phút audio CD (44,1 kHz, 16 bits, stereo): 316 MB 
•  30 phút video (800x600x24, 25 khung hình/s): 64,8 GB 
Khái niệm 
•  Nén dữ liệu ảnh: Biển đổi dòng thông tin ảnh thành từ mã 
nhằm giảm độ dư thừa thông tin. Các phương pháp nén khác 
nhau do định nghĩa các kiểu dư thừa thông tin khác nhau. 
•  Các kiểu dư thừa thông tin gồm: sự phân bố mức xám (Mã 
Huffman), sự lặp lại của các mức xám (RLC), những mẫu sử 
dụng tần xuất cao (LZW) hoặc độ dư thừa vị trí (mã hóa dự 
đoán) 
•  Tỷ lệ nén=1/r (%) trong đó r là kích thước dữ liệu gốc chia 
cho kích thước dữ liệu sau nén 
Phân loại phương pháp nén 
•  Cách 1 (Dựa trên nguyên lý nén) 
▫  Nén không mất mát thông tin 
▫  Nén mất mát thông tin 
•  Cách 2 (Dựa trên cách thức thực hiện nén) 
▫  Phương pháp không gian 
▫  Phương pháp dựa trên biến đổi 
•  Cách 3 (Dựa trên triết lý mã hóa) 
▫  Phương pháp nén thế hệ thứ nhất 
▫  Phương pháp nén thế hệ thứ hai 
Mã loạt dài 
•  Thay bằng việc truyền đi một chuỗi “0” hoặc “1”, có thể truyền 
độ dài của chuỗi. 
•  Trong dữ liệu fax, 70%-80% không gian là các điểm ảnh có giá 
trị 0 (điểm ảnh trắng). Vì thế mã loạt dài hoạt động rất hiệu 
quả. Có thể thay thế độ dài chuỗi bằng một số nguyên có kích 
thước cố định. 
•  Mã loạt dài tỏ ra kém hiệu quả nếu tần suất xuất hiện của giá 
trị 1 (điểm ảnh màu đen) tăng. 
•  11111111111000000000000011111 à 11,1,13,0,5,1 
Mã Huffman 
•  Mã Huffman: Phương pháp nén dự trên mô hình thống kê 
xem xét sắc xuất phân bố của ký tự. Mô hình xác định sắc xuất 
có thể là mô hình tĩnh, thích nghi hoặc bán thích nghi (semi-
adaptive). 
•  Mô hình tĩnh được tích hợp sẵn trong thiết bị nén và thiết 
bị giải nén. 
•  Mô hình bán thích nghi là mô hình cố định được xây dựng 
từ dữ liệu được nén. 
•  Mô hình thích nghi thay đổi trong quá trình nén. 
Thuật toán cơ bản 
•  Các ký tự có tần suất xuất hiện khác nhau. 
•  Các ký tự chiếm không gian biểu diễn khác nhau. 
•  Ký tự với độ dài từ mã nhị phân cố định trong bảng mã ASCII 
được thay bằng từ mã có độ dài thay đổi. 
•  Từ mã ngắn được gán cho các ký tự với tần suất xuất hiện cao 
trong văn bản hoặc tập văn bản. 
•  Bộ mã tạo ra có tính chất tiền tố. 
Thuật toán cơ bản 
1)  Quét văn bản để thống kê tần suất xuất hiện của các ký tự. 
2)  Xây dựng cây mã Huffman dựa trên thống kê tần suất. Mỗi 
ký tự được biểu diễn bằng một nút lá. Nút lá xa gốc được 
gán cho ký tự ít xuất hiện. 
3)  Từ mã biểu diễn ký tự được lấy thông qua đường dẫn từ gốc 
đến nút lá tương ứng. Nhánh rẽ trái và nhánh rẽ phải được 
ký hiệu bởi bit 0 và 1. 
Minh họa 
 BCAACADBDCADAEEEABACDBACADCBADABEABEAAA 
A(15) 
(11) (13) 
C(6) 
(24) 
B(7) E(5) 
(39) 
D(6) 
0 1 
0 1 
0 1 0 1 
Mã số học 
•  Chuỗi ký tự được gán bởi một từ mã số học duy nhất. Độ dài 
của từ mã tỷ lệ thuận với độ dài của chuỗi ký tự. Mã số học 
cần phải có bản tin đặc biệt để phân biệt giữa các từ mã. 
a1 
a2 
a3 
a4 
a1 
a2 
a3 
a4 
a1 
a2 
a3 
a4 
a1 
a2 
a3 
a4 
a1 
a2 
a3 
a4 
0 
1 
0 
0.2 
0.04 
0.08 0.072 0.0688 
0.056 0.0624 
0.06752 
Mã từ điển Lempel-Ziv 
•  Mã từ điển xây dựng từ mã mới cho một chuỗi các từ mã. 
•  Ví dụ: Bảng mã ASCII – mỗi từ mã có độ dài 8 bit, cho phép 
mã hóa 256 ký tự. 
•  Mã từ điển mở rộng thư viện với từ mã có độ dài từ 9 đến 12 
bit. Từ mã mới là chuỗi các từ mã đã xuất hiện. 
•  Mã từ điển hoạt động không hiệu quả với văn bản gồm những 
chuỗi ký tự ngắn và khác nhau. 
•  Xét chuổi ký tự sau: ABCBCABCABCD 
Minh họa 
Previous 
Input 
Input Output Symbol Index 
NIL A 
A B A AB 256 
B C B BC 257 
C B C CB 258 
B C 
BC A BC BCA 259 
A B 
AB C AB ABC 260 
C A C CA 261 
A B 
AB C 
ABC D ABC ABCD 262 
D EOL D 
Previous 
Input 
Input Output Symbol Index 
NIL A A 
A B B AB 256 
B C C BC 257 
C 257 BC CB 258 
BC 256 AB BCA 259 
AB C C ABC 260 
C 260 ABC CA 261 
ABC D D ABCD 262 
Minh họa 
•  Mã từ điển được sử dụng trong nén ảnh graphic interchange 
format (GIF), tagged image file format (TIFF) và portable 
document format (PDF). Ảnh đa mức xám sử dụng 8 bit/
pixel. 
39 39 126 126 
39 39 126 126 
39 39 126 126 
39 39 126 126 
39-39-126-126-256-258-260-259-257-126 
NÉN ẢNH FAX 
Trần Quang Đức 
Chuẩn nén 
•  ITU-T Nhóm 1,2 
▫  Kỹ thuật điều chế: FM, AM, PM 
▫  Màu trắng: 1300 Hz, 1500 Hz 
▫  Màu đen: 2100 Hz, 2400 Hz 
•  ITU-T Nhóm 3: mày fax được thiết kế hoạt động trong 
mạng PSTN (9600 baud). 
•  ITU-T Nhóm 4: Mày fax được thiết kế hoạt động trong 
mạng ISDN (64K baud). 
ITU-T Nhóm 3 
•  Hướng quét: Trái sang phải, Trên xuống dưới 
•  Độ rộng đường quét: 215 (255, 303) 
•  Số lượng pixel trên một đường: 1728 (2048, 2432) 
•  Mã hóa: RLC+MH (MMR - Nhóm 4, Tùy chọn nhóm 3) 
•  Tỷ lệ nén: 5%-20% của kích thước ban đầu (đến 95%) 
Mã Huffman hiệu chỉnh 
•  Loạt điểm ảnh trắng có độ dài 1664 được thay thế bằng 
từ mã ngắn 011000. 
•  Mã Huffman được hiệu chỉnh để mã hóa những loạt 
điểm ảnh có độ dài là bội số của 64. 
•  Độ dài của loạt điểm ảnh có thể biểu diễn bằng một từ 
mã hoặc một vài từ mã (trong trường hợp loạt quá dài). 
Mã Huffman hiệu chỉnh 
Run Length White Code Word Black Code Word 
0 00110101 0000110111 
1 000111 010 
2 0111 11 
3 1000 10 
4 1011 011 
5 1100 0011 
61 00110010 000001011010 
62 00110011 000001100110 
63 00110100 000001100111 
Mã Huffman hiệu chỉnh 
Run Length White Code Word Black Code Word 
64 11011 0000001111 
128 10010 000011001000 
192 010111 000011001001 
256 0110111 000001011011 
320 00110110 000000110011 
384 0110111 000000110100 
2432 000000011101 Same as white 
2496 000000011110 Same as white 
2560 000000011111 Same as white 
Mã Huffman hiệu chỉnh 
•  Loạt gồm 5 điểm ảnh trắng được mã hóa 1100 
•  Loạt gồm 69 điểm ảnh trắng được mã hóa: 64+5 
•  Loạt gồm 64 điểm ảnh trắng được mã hóa: 64+0 
•  Loạt gồm 2561 điểm ảnh trắng được mã hóa: 2560+1 
•  Từ mã EOL: 000000000001 
Mã Huffman hiệu chỉnh 
•  Không có loạt có độ dài 0. Tại sao vẫn có từ mã cho loạt gồm 0 
điểm ảnh trắng và 0 điểm ảnh đen? 
•  Thường một dòng quét có kích thước 8.5 inch tương đương 
1728 điểm ảnh, tại sao vẫn có mã cho những loạt có độ dài 
2561? 
•  Loạt gồm 5 điểm ảnh đen có mã 0011, cũng là tiền tố của loạt 
gồm 61, 62 hoặc 63 điểm ảnh trắng. Giải thích lý do! 
•  Tìm tỷ số nén của ảnh gồm các điểm ảnh đen và trắng nằm 
xen kẽ nhau. 
NÉN ẢNH JPEG 
Trần Quang Đức 
Giảm mẫu kênh màu 
Giảm mẫu kênh màu 
•  4:4:4 (1:1) 
▫  Thiết bị quét phim cao cấp 
▫  Điện ảnh 
•  4:2:2 (3:2) 
▫  Đinh dạng video cao cấp 
•  4:1:1 (2:1) 
▫  DVCPRO (ví dụ NTSC, PAL ) 
•  4:2:0 (2:1) 
▫  MPEG, mã hóa video H.26X 
▫  DVD, Blue-ray 
▫  JPEG, MJPEG 
Chuẩn JPEG 
•  JPEG là chuẩn nén ảnh, được phát triển bởi “Joint 
Photographic Experts Group”. 
•  JPEG là định dạng thường được sử dụng trong lưu và 
truyền ảnh. 
•  JPEG nén được trên cả ảnh màu và đen trắng 
•  Tỷ lệ nén 1:10 nhưng không ảnh hưởng nhiều đến cảm 
nhận của mắt người. 
Chuẩn JPEG 
•  JPEG là kỹ thuật nén mất mát thông tin dựa trên biến 
đổi 2D-DCT (Discrete Cosine Transform). 
▫  Nhận định 1: Nội dung ảnh thay đổi tương đối chậm trên 
bề mặt của ảnh. 
▫  Nhận định 2: Mắt người nhạy cảm hơi với những mất 
mát thuộc về thành phần tần số thấp. 
▫  Nhận định 3: Mắt người cảm nhận tốt hơn sự thay đổi về 
độ chói so với màu sắc. 
Chuẩn JPEG 
Source Image 
Quantization 
Entropy 
Encoding 
Compressed Image 
Huffman Table Quant. Table 
8×8 blocks 
FDCT 
Source Image 
Dequantization 
Entropy 
Decoding 
Huffman Table Quant. Table 
8×8 blocks 
IDCT 
Biến đổi DCT 
•  DCT biến đổi tín hiệu ảnh từ miền không gian sang miền tần 
số. Năng lượng ảnh tập chung chủ yếu ở các thành phần tần 
số thấp, nằm góc trên cùng bên trái của DCT. Các thành phần 
tần số cao thường có giá trị thấp trong biến đổi DCT nên có 
thể loại bỏ để tăng hiệu quả của quá trình nén. 
F(u,v) = 4CkClMN f (x, y)cos
π (2k +1)u
2M
!
"
#
$
%
&cos π (2l +1)v2N
!
"
#
$
%
&
l=0
N−1
∑
k=0
M−1
∑
Ck = 1/ 2 If  k = 01 Otherwise
!
"
#
$#
Cl = 1/ 2 If  k = 01 Otherwise
!
"
#
$#
Biến đổi DCT 
•  Thành phần DC (i.e., F(0,0)) và AC (i.e., F(u,v) (u,v≠0)) đều 
là số nguyên, có giá trị nằm trong khoảng từ -1024 đến 1023. 
52 55 61 66 70 61 64 73 
63 59 55 90 109 85 69 72 
62 59 68 113 144 104 66 73 
63 58 71 122 154 106 70 69 
67 61 68 104 126 88 68 70 
79 65 60 70 77 68 58 75 
85 71 64 59 55 61 65 83 
87 79 69 68 65 76 78 94 
-145 -30 -61 27 56 -20 -2 0 
4 -22 -61 10 13 -7 -9 5 
--47 7 77 -25 -29 10 5 -6 
-49 12 34 -15 -10 6 2 2 
12 -7 -13 -4 -2 2 -3 3 
-8 3 2 -6 -2 1 4 2 
-1 0 0 -2 -1 -3 4 -1 
0 0 -1 -4 -1 0 1 2 
DCT 
Lượng tử hóa 
•  Lượng tử hóa loại bỏ những thông tin thừa trong ảnh. Lượng tử hóa 
là nguyên nhân chủ yếu dẫn đến mất mát thông tin trong các kỹ 
thuật dựa trên biến đổi DCT. 
•  Bước lượng tử hóa được chọn dựa trên cảm nhận của mắt người. 
Nó là hàm với các biến gồm đặc trưng ảnh, đặc trưng hiển thị và 
khoảng cách hiển thị. 
•  Trong ứng dụng, bước lượng tử hóa thường được xác định dựa trên 
thực nghiệm. 
FQ(u,v)=Integer Round (F (u,v)/Q(u,v)) 
Quantization step size 
Lượng tử hóa 
•  Những thành phần tần số cao thường có giá trị bằng 0 hoặc 
rất nhỏ (kể cả giá trị âm và giá trị dương) nên có thể được 
biểu diễn bằng một vài bit. 
16 11 10 16 24 40 51 61 
12 12 14 19 26 58 60 55 
14 13 16 24 40 57 69 56 
14 17 22 29 51 87 80 62 
18 22 37 56 68 109 103 77 
24 35 55 64 81 104 113 92 
49 64 78 87 103 121 120 101 
72 92 95 98 112 100 103 99 
-26 -3 -6 2 2 -1 0 0 
0 -2 -4 1 1 0 0 0 
-3 1 5 -1 -1 0 0 0 
-4 1 2 -1 0 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
Tần số tăng dần 
Mã hóa Entropy 
•  Mã hóa Entropy là dạng đặc biệt của nén không mất mát 
thông tin. 
•  Mã hóa Entropy gồm các bước sau: (1) sắp xếp các thành 
phần ảnh theo đường díc dắc; (2) mã hóa các thành phần ảnh 
bằng mã loạt dài (RLC) và Huffman. 
DPCM 
RLC 
Huffman 
coding FQ(u,v) 
AC 
DC 
01101 
Đường díc dắc 
•  Tất cả các hệ số đều nằm trên đường díc dắc. Các thành phần 
tần số thấp (thường khác 0) được xếp trước các thành phần 
tần số cao. 
-26 -3 -6 2 2 -1 0 0 
0 -2 -4 1 1 0 0 0 
-3 1 5 -1 -1 0 0 0 
-4 1 2 -1 0 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
-26 -3 -6 2 2 -1 0 0 
0 -2 -4 1 1 0 0 0 
-3 1 5 -1 -1 0 0 0 
-4 1 2 -1 0 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
DPCM và Mã loạt dài 
•  Các thành phần DC của các khối ảnh lân cận có tính 
tương quan cao. Vì vậy, mã hóa sự sai khác giữa các 
thành phần trên làm tăng tính hiệu quả của quá trình 
nén. 
•  Mã loạt dài được sử dụng để mã hóa các thành phần AC 
DCi-1 DCi 
DIFF = DCi - DCi-1 
DPCM và Mã loạt dài 
•  Thành phần DC: +3 à (2),(3) 
•  Thành phần AC: 
▫  (0,2) (-3) 
▫  (1,2) (-3) 
▫  (0,2) (-2) 
▫  (0,3) (-6) 
▫  (0,2) (2) 
▫   
▫  (0,0) à EOB 
•  Các thành phần AC được mô tả bởi một cặp ký hiệu (loạt dài, kích 
thước) (biên độ). Loạt dài được tính bằng số lượng 0 giữa hai thành 
phần khác 0. Kích thước biểu diễn số lượng bit dùng để mã hóa giá 
trị biên độ. 
-26 -3 -6 2 2 -1 0 0 
0 -2 -4 1 1 0 0 0 
-3 1 5 -1 -1 0 0 0 
-4 1 2 -1 0 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
Mã Huffman 
•  Thực hiện tăng hiệu quả nén bằng việc thay thế những 
chuỗi ký tự dài bằng những từ mã ngắn. 
•  Độ dài của mỗi từ mã được xác định dựa trên tần suất 
xuất hiện của các ký tự. 
•  JPEG cung cấp bảng mã Huffman chuẩn, nhưng bảng 
mã Huffman cũng có thể được định nghĩa riêng tùy 
thuộc vào ứng dụng và đặc trưng của các ảnh sử dụng 
trong ứng dụng. 
Mã Huffman 
Category Values Bits for the value 
1 -1,1 0,1 
2 -3,-2,2,3 00,01,10,11 
3 -7,-6,-5,-4,4,5,6,7 000,001,010,011,100,101,110,111 
4 -15,...,-8,8,...,15 0000,...,0111,1000,...,1111 
5 -31,...,-16,16,...31 00000,...,01111,10000,...,11111 
6 -63,...,-32,32,...63 000000,...,011111,100000,...,111111 
7 -127,...,-64,64,...,127 0000000,...,0111111,1000000,...,1111111 
8 -255,..,-128,128,..,255 ... 
9 -511,..,-256,256,..,511 ... 
10 -1023,..,-512,512,..,1023 ... 
11 -2047,..,-1024,1024,..,2047 ... 
Giá trị và số lượng bit cho mỗi giá trị 
Mã Huffman 
Run, category Code Length Codeword 
0,0 4 1010 
0,1 2 00 
0,2 2 01 
...   
0,10 16 1111111110000011 
1,1 4 1100 
1,2 5 11011 
15,10 16 1111111111111110 
Bảng mã Huffman chuẩn cho các thành phần AC của kênh độ chói 
Mã Huffman 
Category Code Length Codeword 
0 2 00 
1 3 010 
2 3 011 
3 3 100 
4 3 101 
5 3 110 
6 4 1110 
7 5 11110 
8 6 111110 
9 7 1111110 
10 8 11111110 
11 9 111111110 
Bảng mã chuẩn cho các thành phần DC của kênh độ chói 
Mã Huffman 
•  Thành phần DC: +3 à (2),(3) 
•  Từ mã của thành phần DC: 011 11 
•  Thành phần AC: (0,2) (-3), (1,2) (-3) EOB 
•  Từ mã của thành phần AC: 01 00 11011 00  00 
Minh họa 
1.  Q = 100 - 83,2 bytes 
2.  Q = 50 - 15,1 bytes 
3.  Q = 25 - 9,5 bytes 
4.  Q = 10 - 4,7 bytes 
5.  Q = 5 - 1,5 bytes 
1 2 3 
4 5 
NÉN ẢNH JPEG2000 
Trần Quang Đức 
Chuẩn nén khác? 
•  Với tỷ lệ nén cao (ví dụ 0.25 bpp), méo của chuẩn JPEG là 
không thể chấp nhận. 
•  JPEG có 44 cách thức, rất nhiều trong số đó không được sử 
dụng trong bộ mã hóa JPEG. 
•  Chất lượng của ảnh giảm đi rõ rệt nếu xuất hiện lỗi trong quá 
trình truyền ảnh. 
•  JPEG được tối ưu hóa cho ảnh tự nhiên những không phù 
hợp với ảnh đồ họa. 
•  JPEG không áp dụng được cho ảnh nhị phân. 
Chuẩn JPEG2000 
•  Đặc trưng 
▫  Biến đổi sóng con Wavelet 
▫  Chất lượng tốt với tỷ lệ nén cao 
▫  Nén ảnh nhị phân 
▫  Nén mất mát và không mất mát thông tin 
▫  Linh hoạt với lỗi trong quá trình truyền 
▫  Có khả năng mở rộng 
▫  Chọn vùng quan tâm ROI 
•  Một vài ứng dụng 
▫  Website 
▫  Camera kỹ thuật số 
▫  Ảnh y học 
▫  Ảnh viễn thám 
Chuẩn JPEG2000 
Original image 
5.2 bpp 
b
it 
s
t
r
e
a
m
Lossy 
Lossless 
1.89 bpp 
Chuẩn JPEG2000 
0.125 bpp 
0.25 bpp 
JPEG vs. JPEG2000 
Chuẩn JPEG2000 
•  Nhược điểm 
▫  Thiết bị mã hóa và giải mã phức tạp, thời gian tính toán lâu. 
▫  Khi tỷ lệ nén khoảng 1:25, JPEG2000 so với JPEG có thể 
tạo ra ảnh nén ít bị chia ô nhưng giảm đang kể các chi tiết 
ảnh.