Bài giảng Xử lý ảnh số - Bài toán dò cạnh
Thuật giải dò cạnh được phát triển dựa trên đạo
hàm bậc một hoặc hai.
Các toán tử Prewitt, Sobel (đạo hàm bậc nhất), hoặc
các toán tử dựa trên Laplacian (đạo hàm bâc hai)
như LoG hoặc DoG đều bị nhạy với ảnh nhiễu
Thuật giải Canny được phát triển dựa trên đạo hàm
bậc nhất (dùng toán tử Sobel hoặc Prewitt), nhưng
thêm một số bước để dò cạnh được tối ưu
48 trang |
Chia sẻ: nguyenlam99 | Lượt xem: 1222 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Bài giảng Xử lý ảnh số - Bài toán dò cạnh, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
BÀI TOÁN DÒ CẠNH
TS. NGÔ QUỐC VIỆT
TPHCM-2014
1. Các toán tử dò cạnh dựa trên gradient bậc nhất,
bậc hai
1. Robert, Sobel, Prewitt
2. Laplacian operator
2. Dò cạnh tối ưu dựa trên phương pháp Canny
3. Dò cạnh sử dụng OpenCV
2 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
Trang bị cho sinh viên nền tảng lý thuyết để thực
hiện bài toán dò cạnh
Trang bị các toán tử phổ biến (mặt nạ) dùng để dò
cạnh
Trình bày các trở ngại (nhiễu, cạnh dầy) và hướng
giải quyết cho bài toán dò cạnh
Cung cấp các kỹ năng cần thiết sử dụng OpenCV để
thực hiện dò cạnh
3 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
Nhằm biến đổi ảnh thành tập các curve.
Thể hiện được đặc trưng nổi bật trong ảnh
Cạnh mang lại nhiều thông tin hơn pixel. Cạnh và vùng là
hai thông tin hữu ích cho các bài toán dựa trên ảnh.
Đối sánh các cạnh dễ hơn đối sánh tập các pixel giữa hai
ảnh (cạnh hình dáng, kích cỡ, vị trí đối tượng)
4 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt
Cạnh có thể được biểu hiện bởi một số thay đổi có
trong ảnh
Cạnh là nơi xảy ra sự thay đổi đột ngột hay không
liên tục (discontinuity) về độ sáng, bề mặt, màu sắc
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 5
depth discontinuity
surface color discontinuity
illumination discontinuity
surface normal discontinuity
Sự thay đổi có thể đo bằng đạo hàm bậc nhất
hoặc
Thay đổi cực đại, đạo hàm có có biên độ cực đại
hay đạo hàm bậc hai bằng zero
Thông tin biên được phát hiện bởi pixel trung tâm
và các pixel lân cận.
Nếu cường độ sáng các điểm ảnh lân cận xấp xỉ
cường độ sáng điểm ảnh trung tâm, thì điểm ảnh đó
không là điểm thuộc cạnh
Nếu các lân cận của điểm ảnh trung tâm đang xét
thay đổi mạnh, điểm ảnh đó có thể là thuộc cạnh.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 6
Phương pháp đạo hàm bậc nhất hay Gradient
Roberts Operator
Sobel Operator
Prewitt Operator
Đạo hàm bậc hai
Laplacian
Laplacian of Gaussian
Difference of Gaussian
Dò cạnh tối ưu
Dò cạnh Canny
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 7
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 8
Kỹ thuật chủ yếu dùng để phát hiện cạnh dựa vào sự
biến đổi cường độ xám theo hướng
Cách tiếp cận theo đạo hàm bậc nhất của ảnh dựa
trên kỹ thuật Gradient
Tiếp cận dựa trên gradient hiệu quả khi cường độ
sáng thay đổi rõ nét trên biên. Nghĩa là biến thiên
độ sáng là đột ngột.
Tại điểm có thay đổi nhiều nhất (độ dốc lớn nhất),
đạo hàm bậc nhất có giá trị cực đại.
Điểm trên cạnh có cực trị biên độ gradient
Phương pháp gradient dựa trên so sánh biên độ
với một ngưỡng
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 9
Gradient của ảnh:
Điểm gradient theo hướng thay đổi cường độ sáng nhiều nhất
Hướng gradient xác định bởi:
Độ đo cạnh xác định bởi biên độ gradient
y
f
x
f
f
Gradient rời rạc được xấp xỉ bởi đạo hàm bậc nhất
Đạo hàm bậc hai
Làm cách nào chuyển từ gradient sang dạng mặt nạ
để thực hiện toán tử chập H?
Thực hiện tổng hợp đạo hàm theo hai hướng X và Y
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 10
Chỉ kiểm tra điểm ảnh thuộc cạnh hay không
Làm việc tốt với ảnh nhị phân. Mục tiêu là để dò
cạnh nhanh.
Làm việc không tốt với cạnh nhiễu.
Dạng của toán tử Roberts chéo
Mục tiêu là xác định gradient theo các hướng chéo
so với pixel hiện hành
Differences được tính tại điểm [r+1/2, c+1/2],
không phải tại [r, c]
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 11
|),1()1,(||)1,1(),(|)],([ crfcrfcrfcrfcrfG
10
01
1h
01
10
2h
Xét khác biệt theo hai hướng ngang và dọc, sau đó
kết hợp cả hai nhằm xác định biên độ hay hướng
Biên độ cạnh =
Hướng cạnh =
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 12
111
1
0
1
111
000
111
yH 101
1
1
1
101
101
101
xH
yy HIG xx HIG
22
yx GG
x
y
G
G
1tan
Xấp xỉ đạo hàm tồn tại tốt hơn
Tương tự toán tử Prewit, nhưng sử dụng các hệ số
mặt nạ khác:
Biên độ cạnh =
Hướng cạnh =
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 13
121
1
0
1
8
1
121
000
121
8
1
yH 101
1
2
1
8
1
101
202
101
8
1
xH
22
yx GG
x
y
G
G
1tan
• Dạng chuẩn của Sobel
không có phân số 1/8
• Giá trị 1/8 nhằm lấy được
gradient đúng
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 14
Mặt nạ Prewitt dò cạnh xéo
Mặt nạ Sobel dò cạnh xéo
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 15
Thêm cột và hàng zero
vào các biên ảnh khi
chập - zero padding
121
000
121
yH
101
202
101
xH
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 16
Duplicate mở rộng
cột và hàng ở các biên
ảnh khi chập
121
000
121
yH
101
202
101
xH
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 17
Duplicate mở rộng
cột và hàng ở các biên
ảnh khi chập
121
000
121
yH
101
202
101
xH
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 18
Duplicate mở rộng cột
và hàng ở các biên ảnh
khi chập
121
000
121
yH
101
202
101
xH
Cho một mặt nạ và quay nó theo 8 hướng chính: N,
NW, W, SW, S, SE, E, và NE.
Biên độ cạnh = Giá trị lớn nhất được tìm thấy khi
chập (convolution) 8 mặt nạ với ảnh.
Hướng được xác định theo mặt nạ cho biên độ cạnh
lớn nhất.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 19
Các mặt nạ Kirsch được xác định như sau:
Ví dụ: Nếu NE tạo biên độ cạnh lớn nhất, thì hướng
cạnh là NE (Northeast)
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 20
533
503
533
E
333
503
553
NE
333
303
555
N
333
305
355
NW
335
305
335
W
355
305
333
SW
555
303
333
S
553
503
533
SE
Tương tự như mặt nạ Kirsch, nhưng các hệ số là 0, -
1, 1, -2, và 2
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 21
101
202
101
E
012
101
210
NE
121
000
121
N
210
101
012
NW
101
202
101
W
012
101
210
SW
121
000
121
S
210
101
012
SE
Nhiễu – các toán tử dò cạnh dựa trên đạo
hàm bậc nhất bị ảnh hưởng bởi nhiễu– có thể
dùng các bộ lọc làm trơn ảnh trước.
Cạnh dày – cạnh sẽ có nhiều pixel với toán tử
Sobel – tuy nhiên cạnh có thể bị nhòe và
không định vị chính xác
Toán tử Roberts không làm việc tốt cho ảnh
nhiễu
Toán tử Sobel có xu hướng tính trung bình và
tập trung vào pixel gần tâm của nhân chập.
Toán tử này ít bị ảnh hưởng bởi nhiễu hơn, và
được dùng phổ biến để dò cạnh.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 22
Xét hình sau. Cạnh ở đâu trong hình, làm cách nào
để dò cạnh
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 23
Cạnh ở đâu?
Nguồn: S.Sietz
Zero crossing của đạo hàm bậc hai xác định sự tồn
tại của cực trị
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 24
Xấp xỉ đạo hàm bậc hai
Mặt nạ được định nghĩa
Toán tử nhạy với nhiễu ảnh hưởng dò cạnh.
Sử dụng Laplacian Gaussian
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 25
0 1 0
1 -4 1
0 1 0
Còn gọi bộ dò cạnh Marr-Hildreth
Các bước thực hiện
Làm trơn ảnh với Gaussian filter
Nâng cấp cạnh với Laplacian operator
Kiểm tra Zero crossings để xác định điểm trên
cạnh.
Sử dụng nội suy tuyến tính để xác định vị trí sub-
pixel của cạnh.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 26
Được định nghĩa bởi
Giá trị càng lớn, lọc Gaussian càng rộng,
hiệu ứng làm trơn càng nhiều.
Làm trơn quá nhiều sẽ ảnh hưởng đến dò
cạnh
Bài tập: viết code (C++/C#/JAVA/MATLAB)
phát sinh nhân chập LoG.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 27
2
22
2
2
22
4 2
1
1
),(
yx
e
yx
yxLoG
Hình dạng hàm lọc có dạng Mexican Hat (nên
còn gọi là toán tử Mexican Hat)
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 28
Nhân chập Mexican Hat với giá trị = 1.4
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 29
LoG cần nhiều tính toán khi kích thước nhân chập
dò cạnh lớn
Để giảm bớt tính toán, xấp xỉ LoG bởi hiệu của hai
LoG DoG
Độ rộng của cạnh có thể điều chỉnh bằng cách thay
đổi 1 and 2.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 30
2
2
)
2
22
(
2
1
)
2
22
(
22
),(
2
2
2
1
yxyx
ee
yxDoG
function h = d2dgauss(n1,sigma1,n2,sigma2,theta)
r=[cos(theta) -sin(theta);
sin(theta) cos(theta)];
for i = 1 : n2
for j = 1 : n1
u = r * [j-(n1+1)/2 i-(n2+1)/2]';
h(i,j) = gauss(u(1),sigma1)*dgauss(u(2),sigma2);
end
end
h = h / sqrt(sum(sum(abs(h).*abs(h))));
function y = gauss(x,std)
y = exp(-x^2/(2*std^2)) / (std*sqrt(2*pi));
function y = dgauss(x,std)
y = -x * gauss(x,std) / std^2;
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 31
Một số mặt nạ dò cạnh theo DoG
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 32
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 33
Laplacian
Laplacian*I
Duplicate boundary row & cols
trước khi chập
Đạo hàm bậc hai, cụ thể là phương pháp dựa
trên Laplacian, vẫn còn ảnh hưởng nhiều bởi
nhiễu.
Khả năng dò cạnh sai và mất cạnh vẫn còn
Tuy nhiên, định vị cạnh chính xác hơn so với
các phương pháp dựa trên gradient
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 34
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 35
Cạnh
thật
Bị tác động bởi nhiễu
Poor robustness
To noise
Vị trí sai
Poor
Localization
Dư
quá nhiều
Multiple
Responses
Dò cạnh tối ưu phụ thuộc vào các yếu tố
Tỉ lệ lỗi thấp – cạnh không bị thiếu và không
được có điểm sai.
Vị trí đúng – khoảng cách giữa điểm cạnh dò
được và tâm thật sự của cạnh phải nhỏ nhất
Single response – không dư pixel khi dò cạnh
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 36
Các tiêu chuẩn có thể định lượng bằng công thức
Tỉ lệ lỗi nhiễu
Localization:
Mục tiêu là cần tìm min biểu thức
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 37
RMS of Filter to edge
RMS of Filter to noise
)()(*)( fPfonLocalizatifSNR ii
Phát triển bởi John F. Canny (1986)
Bước 1
Khử nhiễu– dùng lọc Gaussian
Chú ý chọn độ rộng thích hợp cho bộ lọc Gaussian
Bước 2
Cường độ cạnh được xác định thông qua gradient
của image
Sử dụng mặt nạ Sobel hoặc Prewitt
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 38
GyGxGyGxG 22
Bước 3: xác định hướng cạnh
Bước 4: tìm hướng cạnh đúng trong các
hướng đã xác định
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 39
Gx
Gy1tan
Bước 5: khử những non-maxima– theo vết
dọc theo hướng cạnh và loại bỏ pixel không
được xem nằm trên cạnh. Nhằm tạo ra cạnh
mịn
Bước 6: dùng ngưỡng double / hysteresis
(ngưỡng kép hoặc ngưỡng trễ) để loại bỏ
streaking (sọc trên cạnh)
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 40
Ước lượng hướng chính theo nguyên tắc
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 41
41420tan41422-:3
41422|tan|:2
41422tan41420:1
41420tan41420:0
.θ.
.θ
.θ.
.θ.-
x
y
G
G
θ tan
0
1
2
3
Xấp xỉ hướng
Loại bỏ các pixel có |G| không là cực trị cục bộ
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 42
yx ,
yx,
yx ,
otherwise0
),(),(&
),(),( if),(
, yxGyxG
yxGyxGyxG
yxM
(x’, y’) và (x’’, y’’) là lân cận của (x, y) dọc
theo hướng của gradient tại (x, y).
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 43
Hướng chính 90 độ.
Các pixel khoanh
trắng được giữ lại
sau bước Non-Max
Suppession.
Cho trước cặp giá trị (High, Low), nếu biên độ của
gradient tại pixel:
Lớn hơn “High”, pixel được gán nhãn ‘edge
pixel’
Nhỏ hơn “Low”, pixel được gán nhãn“non-
edge-pixel”
Giữa “Low” và “High”
Kiểm tra các lân cận của pixel, nếu tồn tại một điểm
ảnh có biên độ gradient lớn hơn “High” thì gán pixel
đó nhãn “edge pixel” ngược lại gán “non-edge-
pixel”.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 44
cvSobel( const CvArr* src, CvArr* dst, int xorder, int
yorder, int aperture_size=3 )
cvLaplace( const CvArr* src, CvArr* dst, int
aperture_size=3 )
cvCanny( const CvArr* image, CvArr* edges, double
threshold1, double threshold2, int aperture_size=3 );
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 45
Tham khảo: openCV_Canny(x)
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 46
Thuật giải dò cạnh được phát triển dựa trên đạo
hàm bậc một hoặc hai.
Các toán tử Prewitt, Sobel (đạo hàm bậc nhất), hoặc
các toán tử dựa trên Laplacian (đạo hàm bâc hai)
như LoG hoặc DoG đều bị nhạy với ảnh nhiễu
Thuật giải Canny được phát triển dựa trên đạo hàm
bậc nhất (dùng toán tử Sobel hoặc Prewitt), nhưng
thêm một số bước để dò cạnh được tối ưu
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 47
1. Cài đặt chương trình minh họa dò cạnh với các
toán tử Prewitt, Sobel, Log, DoG
2. Cài đặt lại dò cạnh Canny trên ảnh tĩnh với các
tham số High, Low và kiểu và kích thước mặt nạ
thay đổi.
Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 48
Các file đính kèm theo tài liệu này:
- xla_baigiang_06_617.pdf