Bài giảng Xử lý ảnh số - Chương 6: Bài toán dò cạnh - Ngô Quốc Việt

Nội dung text: Bài giảng Xử lý ảnh số - Chương 6: Bài toán dò cạnh - Ngô Quốc Việt

1. 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 G [ f (r,c)] | f (r,c) f (r 1,c 1) | | f (r,c 1) f (r 1,c) | 1 0 0 1 h1 h2 0 1 1 0 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
2. 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 1 1 1 1 1 0 1 1 H 0 0 0 0 1 1 1 H 1 0 1 1 1 0 1 y   x   1 1 1 1 1 0 1 1 Gy I  H y Gx I  H x 2 2 Biên độ cạnh = Gx Gy 1 Gy Hướng cạnh = tan Gx Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 12
3. 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: 1 2 1 1 1 0 1 1 1 1 1 1 H 0 0 0 0 1 2 1 H 2 0 2 2  1 0 1 y 8 8 x 8 8 1 2 1 1 1 0 1 1 • Dạng chuẩn của Sobel không có phân số 1/8 2 2 • Giá trị 1/8 nhằm lấy được Biên độ cạnh = Gx Gy gradient đúng 1 Gy Hướng cạnh = tan G x Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 13
4. 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 14
5. 1 0 1 1 2 1 H 2 0 2 H 0 0 0 x y 1 0 1 1 2 1 Thêm cột và hàng zero vào các biên ảnh khi chập - zero padding Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 15
6. 1 0 1 1 2 1 H 2 0 2 H 0 0 0 x y 1 0 1 1 2 1 Duplicate mở rộng cột và hàng ở các biên ảnh khi chập Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 16
7. 1 0 1 1 2 1 H 2 0 2 H 0 0 0 x y 1 0 1 1 2 1 Duplicate mở rộng cột và hàng ở các biên ảnh khi chập Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 17
8. 1 0 1 1 2 1 H 2 0 2 H 0 0 0 x y 1 0 1 1 2 1 Duplicate mở rộng cột và hàng ở các biên ảnh khi chập Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 18
9. 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
10. Các mặt nạ Kirsch được xác định như sau: 3 3 5 3 5 5 5 5 5 5 5 3 E 3 0 5 NE 3 0 5 N 3 0 3 NW 5 0 3 3 3 5 3 3 3 3 3 3 3 3 3 5 3 3 3 3 3 3 3 3 3 3 5 W 5 0 3 SW 5 0 3 S 3 0 3 SE 3 0 5 5 3 3 5 5 3 5 5 5 3 5 5 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
11. Tương tự như mặt nạ Kirsch, nhưng các hệ số là 0, - 1, 1, -2, và 2 1 0 1 0 1 2 1 2 1 2 1 0 E 2 0 2 NE 1 0 1 N 0 0 0 NW 1 0 1 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 0 1 2 1 2 1 2 1 0 W 2 0 2 SW 1 0 1 S 0 0 0 SE 1 0 1 1 0 1 2 1 0 1 2 1 0 1 2 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 21
12. 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
13. Xét hình sau. Cạnh ở đâu trong hình, làm cách nào để dò cạnh Cạnh ở đâu? Nguồn: S.Sietz Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 23
14. 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
15. Xấp xỉ đạo hàm bậc hai Mặt nạ được định nghĩa 0 1 0 1 -4 1 0 1 0 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
16. 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
17. Được định nghĩa bởi x2 y2 2 2 1 x y 2 LoG(x, y) 1 e 2 4 2  2 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
18. 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
19. 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
20. 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 x2 y2 x2 y2 ( ) ( ) 2 2 e 2 1 e 2  2 DoG(x, y) 2 2 2  1 2  2 Độ 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
21. 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
22. 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
23. Laplacian*I Laplacian Duplicate boundary row & cols trước khi chập Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 33
24. Đạ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
25. Cạnh Bị tác động bởi nhiễu Vị trí sai Dư thật Poor robustness Poor quá nhiều To noise Localization Multiple Responses Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 35
26. 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
27. Các tiêu chuẩn có thể định lượng bằng công thức RMS of Filter to edge Tỉ lệ lỗi nhiễu RMS of Filter to noise Localization: Mục tiêu là cần tìm min biểu thức SNR( f )*Localization( f ) i Pi ( f ) Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 37
28. 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 G Gx 2 Gy 2 Gx Gy Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 38
29. Bước 3: xác định hướng cạnh Gy  tan 1 Gx 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
30. 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
31. Ước lượng hướng chính theo nguyên tắc G y 2 tan θ 3 1 Gx Xấp xỉ hướng 0 : -0.4142 tan θ 0.4142 0 1: 0.4142 tan θ 2.4142 2 : | tan θ | 2.4142 3: - 2.4142 tan θ 0.4142 Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 41
32. Loại bỏ các pixel có |G| không là cực trị cục bộ G(x, y) if G(x, y) G(x , y ) x , y M x, y & G(x, y) G(x , y ) x, y 0 otherwise x , y (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 42
33. Hướng chính 90 độ. Các pixel khoanh trắng được giữ lại sau bước Non-Max Suppession. Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 43
34. 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
35. 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
36. Tham khảo: openCV_Canny(x) Bài giảng Xử lý ảnh - TS. Ngô Quốc Việt 46
37. 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
38. 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