Bài giảng Xử lý ảnh số - Phân tích ảnh. Xử lý đường biên - Nguyễn Linh Giang

Xử lý ảnh số
Phân tích ảnh
Xử lý đường biên ( edge )
Chương trình dành cho kỹ sư CNTT
Nguyễn Linh Giang
Xử lý đường biên
• Biểu diễn biên
• Gradient rời rạc
• Các phương pháp tách biên
• Dò và nối đường biên
• Mã hóa đường biên
Biểu diễn biên
• Khái niệm biên
– Biên ( edge ): là tập hợp các điểm tại đó hàm độ sáng
của ảnh thay đổi cục bộ đột ngột;
– Đối với hàm liên tục, sự biến thiên của hàm được xác
định thông qua đạo hàm các cấp. 
– Ảnh: hàm liên tục hai biến là các tọa độ trong mặt
phẳng ảnh:
• Sự biến thiên hàm sẽ được biểu diễn bằng các đạo hàm riêng.
• Sự biến thiên của hàm ảnh biểu diễn bằng vector gradient;
– Gradient chỉ hướng biến thiên tăng cực đại của hàm
ảnh;
– Đối với ảnh số, phải xác định các gradient rời rạc
Biểu diễn biên
– Biên là thộc tính cục bộ
của mỗi điểm và được
tính từ hàm ảnh tại những
điểm lân cận của điểm
đang xét; 
– Biên được xác định bằng
một vector có hai thành
phần:
• Độ lớn: xác định bằng độ
lớn của gradient; 
• Hướng: hợp với hướng của
gradient một góc -90o.
Biểu diễn biên
– Biên được sử dụng trong phân tích ảnh để xác định các đường
biên của vùng ảnh;
– Đường biên là tập hợp các điểm tại đó hàm ảnh biến thiên và
bao gồm những điểm với biên độ biên cao; 
– Đường biên và các phần của nó ( các điểm biên ) luôn trực giao
với hướng của gradient;
– Một số dạng biên ảnh:
Gradient rời rạc
• Độ lớn và hướng của gradient tại một điểm của
hàm:
– Tính theo gradient theo hai hướng x, y: 
Gx = ∂s(x, y)/ ∂x ; Gy = ∂s(x, y)/ ∂y 
22),( yx GGyxs +=∇
( )xy GGarctan=ψ
Gradient rời rạc
• Một số hệ thức tính gần đúng độ lớn của
gradient:
y
yxs
x
yxsyxs ∂
∂+∂
∂= ),(),(),( grad
⎭⎬
⎫
⎩⎨
⎧
∂
∂
∂
∂=
y
yxs
x
yxsyxs ),(,),(max),( grad
Gradient rời rạc
• Tính gradient của ảnh số
– Các gradient theo các hướng được tính theo các sai
phân theo từng hướng trục tọa độ của hàm:
Hoặc
k
nkmsnmsnmGx
),(),(),( −−=
k
knmsnmsnmGy
),(),(),( −−=
k
nmsnkmsnmGx
),(),(),( −+=
k
nmsknmsnmGy
),(),(),( −+=
– Các yêu cầu đối với k :
• k là số nguyên nhỏ, thường chọn bằng 1;
• Đủ nhỏ để ước lượng gần chính xác đạo hàm theo hướng;
• Đủ lớn để có thể bỏ qua những biến thiên nhỏ của hàm ảnh.
– Một số trường hợp có thể dùng sai phân đối xứng
để tính gradient:
– Nhược điểm: không tính đến ảnh hưởng của điểm
pm,n lên gradient. 
Gradient rời rạc
[ ]kk
k
nms
k
nkmsnkmsnmGx −∗=−−+= 02
1),(
2
),(),(),(
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
∗=−−+=
k
k
k
nms
k
knmsknmsnmGy 02
1),(
2
),(),(),(
• Tính gradient theo hai hướng trực giao bất kỳ:
– Xác định các mặt nạ gradient theo các hướng trực
giao H1, H2;
– Tính gradient theo các hướng tại từng điểm của toàn
ảnh bằng các mặt nạ H1, H2;
– Toán tử xác định gradient thực chất là phép toán lấy
tổng chập ảnh s(m, n) với các hàm mặt nạ h1(-m, -n ) 
và h2( -m, -n ). 
– Nếu các mặt nạ H1 và H2 là đối xứng thì
h1(-m, -n ) = h1(m, n ); h2(-m, -n ) = h2(m, n ) 
Gradient rời rạc
Gradient rời rạc
– Các gradient rời rạc theo hướng:
g1(m, n) = s( m, n ) * h1( m, n )
g2(m, n) = s( m, n ) * h2( m, n )
– Biên độ của gradient
g(m, n ) = (((g1(m, n))2 + (g2(m, n))2)1/2
Hoặc
g(m, n ) = |g1(m, n)| + |g2(m, n)|
– Điểm pm,n được coi là điểm trên biên nếu g(m, n) ≥ θ
và
Ig = { (m, n)| g(m, n) ≥ θ } - Là tập hợp các điểm
biên ảnh
θ - là ngưỡng xác định biên
– Hàm ε(m, n) là bản đồ biên ảnh và cung cấp dữ liệu
để dò biên đối tượng trong ảnh
⎩⎨
⎧ ∈=
otherwise 0,
I n) (m, ,1
),( gnmε
Gradient rời rạc
Gradient rời rạc
• Xác định biên theo đạo hàm cấp 2 – toán tử Laplace
– Trong một số trường hợp, chỉ cần tính đến biên độ của gradient 
mà không cần quan tâm tới sự thay đổi về hướng;
– Toán tử vi phân tuyến tính bậc hai Laplace cũng được sử dụng để
tính biên độ gradient;
– Toán tử Laplace có cùng tính chất theo mọi hướng và bất biến
đối với phép quay ảnh
– Rời rạc hóa:
Δs(m,n) = 4s(m,n) – [s(m-1,n) + s(m+1,n) + s(m,n-1) + s(m,n+1)]
2
2
2
2 ),(),(),(
y
yxs
x
yxsyxs ∂
∂+∂
∂=Δ
Các phương pháp xác định biên ảnh
• Các bộ lọc tìm biên
• Các toán tử đạo hàm cấp 1;
• Các toán tử đạo hàm cấp 2;
• Các toán tử điểm giao không;
• Các toán tử đối sánh với mô hình tham số
Các phương pháp xác định biên ảnh
• Các bộ lọc tìm biên – xác định biên qua việc đo
độ dốc của biên được chia làm ba dạng:
– Các bộ lọc ( toán tử ) tính xấp xỉ đạo hàm của hàm
ảnh bằng các sai phân hữu hạn:
• Các toán tử tính xấp xỉ đạo hàm bậc nhất sử dụng các cửa
sổ mặt nạ. Hướng của gradient được xác định bằng mặt nạ
cho đáp ứng cao nhất. Giá trị tuyệt đối của đáp ứng của
mặt nạ là môdun của gradient
• Các toán tử bất biến với phép quay ( toán tử Laplace ) và
không phụ thuộc hướng, khi đó chỉ cần một mặt nạ tổng
chập. 
Các phương pháp xác định biên ảnh
– Các toán tử dựa trên các điểm giao không của đạo
hàm bậc hai của hàm ảnh ( phương pháp Marr-
Hildreth hoặc lọc tìm biên Canny ). 
– Các toán tử đối sánh hàm ảnh với mô hình tham số
của điểm biên. 
• Các mô hình tham số mô tả biên chính xác hơn là chỉ sử
dụng độ lớn và hướng của biên. 
• Những phương pháp này yêu cầu khối lượng tính toán lớn.
• Rất khó có thể lựa chọn chiến lược xác định biên
tối ưu.
• Lĩnh vực này được tập trung nghiên cứu;
Các phương pháp xác định biên ảnh
• Đặc điểm chung của các bộ lọc tìm biên:
– Là các bộ lọc thông cao;
– Bên cạnh việc xác định biên, các bộ lọc này còn làm
tăng cường nhiễu;
– Đánh giá các bộ lọc tìm biên:
• Đánh giá theo xác suất tìm biên đúng;
• Đánh giá theo tỷ lệ tín hiệu trên nhiễu;
• Đánh giá theo hướng của biên;
• Đánh giá theo khả năng tách biên
Các toán tử đạo hàm cấp 1
• Các toán tử đạo hàm cấp 1:
– Các toán tử tính gradient theo hai
hướng;
– Tính độ lớn của gradient tổng hợp;
– Xác định góc của gradient theo các
thành phần;
– Lập bản đồ biên theo ngưỡng
Các toán tử đạo hàm cấp 1
• Toán tử Roberts
– Các mặt nạ lọc tương ứng với hai hướng hợp với lưới ảnh 45o. 
– Các mặt nạ được áp dụng riêng rẽ với ảnh đầu vào và cho giá
trị độ đo gradient theo mỗi hướng ( G1 và G2). 
– Các mặt nạ lọc cho phép tính các thành phần và hướng của
gradient tại từng điểm ảnh. Độ lớn các thành phần được tính
bằng:
G1( m, n ) = | s( m, n ) – s( m+1, n+1 ) |
G2( m, n ) = | s( m, n+1 ) – s( m+1, n ) |
– Biên độ của gradient có thể được tính bằng độ đo Euclide hoặc
độ đo L1:
|G( m, n )| = | G1( m, n ) | + | G2( m, n )|
– Hướng của gradient: 
ψ = arctan( G2/G1) - 3π/4
Các toán tử đạo hàm cấp 1
– Mặt nạ lọc của toán tử Roberts
– Ví dụ toán tử Roberts
01
10
 ,
10
01
21 −=−= HH
– Ưu điểm:
• Đơn giản khi tính toán vì chỉ sử dụng lân cận 2x2 của
điểm;
• Các mặt nạ lọc đáp ứng cực đại với các biên tạo góc 45o
với lưới ảnh.
– Nhược điểm: 
• Nhạy cảm với những biến thiên nhỏ của biên vì sử dụng ít
điểm lân cận để xấp xỉ gradient;
• Đáp ứng yếu với những đường biên đích thực, trừ khi các
đường biên này rất nét;
• Nhạy cảm với nhiễu
Các toán tử đạo hàm cấp 1
Các toán tử đạo hàm cấp 1
• Toán tử Prewitt
– Toán tử Prewitt xấp xỉ hóa đạo hàm bậc nhất; 
– Toán tử Prewitt xác định gradient theo hai hướng trực giao
theo phương nằm ngang và thẳng đứng;
– Gradient xác định theo các sai phân đối xứng:
– Môdun của gradient được tính theo độ đo Euclide:
G(m, n ) = [((Gx(m, n))2 + (Gy(m, n))2]1/2
[ ])1,1()1,1(),1(),1()1,1()1,1((
3
1),( +−−+++−−++−−−−+= kjskjskjskjskjskjsnmGx
[ ])1,1()1,1()1,()1,()1,1()1,1((
3
1),( −+−+++−−++−−−+−= kjskjskjskjskjskjsnmGy
– Các ma trận gradient:
– Ví dụ toán tử Prewitt:
Các toán tử đạo hàm cấp 1
101
101
101
3
1 ,
111
000
111
3
1
21
−
−
−
=
−−−
= HH
Các toán tử đạo hàm cấp 1
– Đặc điểm của toán tử Prewitt:
• Thực hiện chậm hơn toán tử Roberts;
• Tốt hơn toán tử Roberts theo nghĩa tín hiệu trên nhiễu và
xác suất phát hiện biên đúng;
• Có ưu điểm trong việc xác định các biên thẳng đứng hoặc
nằm ngang so với các biên nghiêng 45o;
• Không thể xác định biên về thành đường độ dày 1
• Toán tử Sobel
– Toán tử Sobel xấp xỉ hóa đạo hàm bậc nhất; 
– Các mặt nạ được thiết kế để đáp ứng tối đa với các
biên chạy thẳng đứng hoặc nằm ngang so với lưới ảnh;
– Toán tử Sobel xác định gradient theo hai hướng trực
giao theo phương nằm ngang và thẳng đứng;
– Gradient xác định theo các sai phân đối xứng:
– Môdun của gradient được tính theo độ đo L1 hoặc
Euclide:
G(m, n ) = [((Gx(m, n))2 + (Gy(m, n))2]1/2
Các toán tử đạo hàm cấp 1
[ ])1,1()1,1()),1(),1((2)1,1()1,1((
4
1),( +−−+++−−++−−−−+= kjskjskjskjskjskjsnmGx
[ ])1,1()1,1())1,()1,((2)1,1()1,1((
4
1),( −+−+++−−++−−−+−= kjskjskjskjskjskjsnmGy
– Ma trận lọc của toán tử Sobel
– Ví dụ toán tử Sobel
Các toán tử đạo hàm cấp 1
101
202
101
4
1 ,
12
00
12
2
−
−
−
=
−
H
1
0
1
4
1
1
−−
=H
– Đặc điểm của toán tử Sobel:
• Toán tử Sobel tính biên chậm hơn toán tử Roberts;
• Mặt nạ tổng chập lớn hơn so với toán tử Roberts và có tác
dụng làm trơn nên ít nhạy cảm với nhiễu hơn;
• Bên cạnh tách biên, toán tử Sobel còn có tác dụng làm trơn
nhiễu; 
• Các đường biên dày hơn so với toán tử Roberts do hiệu ứng
làm trơn;
• Toán tử có đầu ra với giá trị lớn hơn so với toán tử Roberts 
do đó dễ làm tràn biểu diễn ảnh;
• Làm khuếch đại các thành phần tần số cao;
• Có ưu điểm trong việc xác định các biên nghiêng 45o so với
các biên thẳng đứng hoặc nằm ngang;
• Không thể xác định biên về thành đường độ dày 1
Các toán tử đạo hàm cấp 1
• Các toán tử la bàn
– Gradient được ước lượng theo 8 hướng theo mặt nạ
tổng chập;
– Kết quả của tổng chập có độ lớn cực đại cho giá trị độ
lớn của gradient tại điểm đang xét; 
– Mặt nạ cho tổng chập cực đại chỉ hướng của gradient;
– Thông thường mặt nạ là ma trận 3x3, tuy vậy có thể
có mặt nạ với kích thước lớn hơn như 5x5, ...;
– Các toán tử xác định đạo hàm bậc nhất của hàm ảnh
thường được gọi là các toán tử la bàn hay toán tử quay 
vì cho phép xác định hướng của gradient; 
Các toán tử đạo hàm cấp 1
Các toán tử đạo hàm cấp 1
– |G( m, n )| = max { |Gk( m, n )|, k = 0, ..., 7 }
– θk = π/2 + kπ/4
011
101
110
 , 
101
101
101
 , 
110
101
011
 , 
111
000
111
−
−−
−
−
−
−−
−
−−−
011
101
110
 , 
101
101
101
 , 
110
101
011
 , 
111
000
111
−−
−
−
−
−
−
−−−−−
Các toán tử đạo hàm cấp 1
– Toán tử la bàn Kirsch:
– Toán tử la bàn Prewitt:
– Toán tử la bàn Sobel:
111
000
111
−−−
121
000
121
−−−
333
303
555
−−−
−−
Các toán tử đạo hàm cấp 2
• Toán tử Laplace:
– Biên được xác định theo điểm giao không của đạo hàm cấp hai;
– Xác định đạo hàm bậc hai:
– Trường hợp số hóa:
Δs(m,n) = 4s(m,n) – [s(m-1,n) + s(m+1,n) + s(m,n-1) + s(m,n+1)]
– Ma trận toán tử Laplace:
2
2
2
2
2 ),(),(),(),(
y
yxs
x
yxsyxsyxs ∂
∂+∂
∂=∇=Δ
010
141
010
4
1
−
−−
−
=LH
– Đặc điểm của toán tử đạo hàm Laplace: 
• Là toán tử đạo hàm bậc 2;
• Các hệ số dương nằm gần tâm
• Các hệ số âm nằm ở vùng ngoài biên; 
• Tổng các hệ số của bộ lọc bằng 0: không có thành phần DC;
• Toán tử Laplace được tính theo phương pháp tính tổng chập
thông thường.
• Nhạy cảm với nhiễu
– Một số mặt nạ Laplace thông dụng:
Các toán tử đạo hàm cấp 2
111
181
111
−=H
121
242
121
−−
−
−−
=H
010
141
010
4
1
−
−−
−
=H
Tác động của toán tử đạo hàm bậc hai Laplace
Các toán tử đạo hàm cấp 2