Bài giảng Xử lý ảnh số - Phân tích ảnh - Phần 2: Xử lý đường biên (edge)

Nội dung text: Bài giảng Xử lý ảnh số - Phân tích ảnh - Phần 2: Xử lý đường biên (edge)

1. 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
2. Xử lý đường biên •Biểudiễnbiên •Gradient rờirạc •Cácphương pháp tách biên •Dòvànối đường biên • Mã hóa đường biên
3. Biểudiễnbiên •Kháiniệmbiên – Biên ( edge ): là tậphợpcácđiểmtại đóhàmđộ sáng của ảnh thay đổicụcbộđộtngột; – Đốivới hàm liên tục, sự biếnthiêncủahàmđượcxác định thông qua đạohàmcáccấp. – Ảnh: hàm liên tụchaibiếnlàcáctọa độ trong mặt phẳng ảnh: •Sự biến thiên hàm sẽđượcbiểudiễnbằng các đạo hàm riêng. •Sự biếnthiêncủahàmảnh biểudiễnbằng vector gradient; –Gradient chỉ hướng biếnthiêntăng cực đạicủahàm ảnh; – Đốivới ảnh số, phảixácđịnh các gradient rờirạc
4. Biểudiễnbiên –Biênlàthộctínhcụcbộ củamỗi điểmvàđược tính từ hàm ảnh tạinhững điểmlâncậncủa điểm đang xét; –Biênđượcxácđịnh bằng mộtvector cóhaithành phần: • Độ lớn: xác định bằng độ lớncủagradient; •Hướng: hợpvớihướng của gradient một góc -90o.
5. Biểudiễnbiên –Biênđượcsử dụng trong phân tích ảnh để xác định các đường biên củavùngảnh; – Đường biên là tậphợpcácđiểmtại đóhàmảnh biếnthiênvà bao gồmnhững điểmvớibiênđộ biên cao; – Đường biên và các phầncủa nó ( các điểm biên ) luôn trựcgiao vớihướng củagradient; –Mộtsố dạng biên ảnh:
6. Gradient rờirạc • Độ lớàh nvướng t t củ n e i d a rạim agột điểmcủa hàm: – Tính heot gradient theo hai hướng x, y: Gx = ∂s(x, y)/ ∂x ; Gy = ∂s(x, y)/ ∂y 2 2 s∇ x(,) y =x G + y G ψ = arctanGG( y x)
7. Gradient rờirạc •Mộtsố hệ thhgứ n í ctần đúng độ lớncủa gradient: (,)(,)s∂ x y s∂ x y grads x ( y= , ) + ∂x ∂y ⎧s∂(,) x ys∂(,) x y⎫ grad s ( x , y= )⎨ max , ⎬ ⎩ ∂x ∂y ⎭
8. Gradient rờirạ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ụctọa độ củahàm: s m(,)(,) n− s− m k n s m(,)(,) n− s m− n k G(,) m= n G(,) m= n x k y k Hoặc s m(,)(,) k+ n− s m n s m(,)(,) n+ k− s m n G(,) m= n G(,) m= n x k y k –Cácyêucầu đốivới k : • k là số nguyên nhỏ, thường chọnbằng 1; • Đủ nhỏđểướclượ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ủahàmảnh.
9. Gradient rờirạc –Mộtsố trường hợh ót pcể dùng sai phân đốixứng để tính gradient: s m(,)(,) k+ n− s− m k n 1 G(,) m= n =s(,) m n ∗ []k0 − k x 2k 2k ⎡ k ⎤ s m(,)(,) n+ k − s m − n k 1 G(,) m= n =s(,) m n ∗ ⎢ 0 ⎥ y 2k 2k ⎢ ⎥ ⎣⎢−k⎦⎥ h –Nược điểm: không tính đến ảnh hưởng của điểm pm,n lên gradient.
10. Gradient rờirạc • Tính gradient theo hai hướng trựcgiaobấtkỳ: –Xácđịnh các mặtnạ gradient theo các hướng trực giao H1, H2; – Tính gradient theo các hướng tạitừng điểmcủatoàn ảnh bằng các mặtnạ H1, H2; –Toántử xác định gradient thựcchất là phép toán lấy tổng chập ảnh s(m, n) vớicáchàmmặtnạ h1(-m, -n ) và h2( -m, -n ). –Nếucácmặtnạ H1 và H2 là đốixứng thì h1(-m, -n ) = h1(m, n ); h2(-m, -n ) = h2(m, n )
11. Gradient rờirạc – Các gradient rờirạctheohướng: g1(m, n) = s( m, n ) * h1( m, n ) g2(m, n) = s( m, n ) * h2( m, n ) –Biênđộ củagradient 2 2 1/2 g(m, n ) = (((g1(m, n)) + (g2(m, n)) ) Hoặc g(m, n ) = |g1(m, n)| + |g2(m, n)|
12. Gradient rờirạc – Điểmpm,n được coi là điểmtrênbiênnếug(m, n) ≥θ và Ig = { (m, n)| g(m, n) ≥θ} - Là tậphợpcá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ấpdữ liệu để dò biên đốitượng trong ảnh 1 , ⎧ (m,∈ g n) I (,)εm n= ⎨ 0, ⎩ otherwise
13. Gradient rờirạc •Xácđịnh biên theo đạohàmcấp2 –toántử Laplace – Trong mộtsố trường hợp, chỉ cần tính đếnbiênđộ củagradient mà không cầnquantâmtớisự thay đổivề hướng; –Toántử vi phân tuyếntínhbậc hai Laplace cũng đượcsử dụng để tính biên độ gradient; –Toántử Laplace có cùng tính chấttheomọihướng và bấtbiến đốivới phép quay ảnh (,)(,)∂s2 x y ∂s2 x y Δs(,) x y = + ∂x2 ∂y2 –Rờirạchóa: Δs(m,n) = 4s(m,n) – [s(m-1,n) + s(m+1,n) + s(m,n-1) + s(m,n+1)]
14. Các phương pháp xác định biên ảnh •Cácbộ lọc tìm biên • Các toán tửđạohàmcấp1; • Các toán tửđạohàmcấp2; • Các toán tửđiểm giao không; • Các toán tửđốisánhvớimôhìnhthamsố
15. Các phương pháp xác định biên ảnh •Cácbộ lọc tìm biên – xác định biên qua việc đo độ dốccủabiênđượcchialàmbadạng: –Cácbộ lọc ( toán tử ) tính xấpxỉđạohàmcủahàm ảnh bằng các sai phân hữuhạn: •Cáctoántử tính xấpxỉđạohàmbậcnhấtsử dụng các cửa sổ mặtnạ. Hướng củagradient đượcxácđịnh bằng mặtnạ cho đáp ứng cao nhất. Giá trị tuyệt đốicủa đáp ứng của mặtnạ là môdun của gradient •Cáctoántử bấtbiếnvới phép quay ( toán tử Laplace ) và không phụ thuộchướng, khi đóchỉ cầnmộtmặtnạ tổng chập.
16. Các phương pháp xác định biên ảnh – Các toán tử dựatrêncácđiểm giao không của đạo hàm bậchaicủahàmảnh ( phương pháp Marr- Hildreth hoặclọc tìm biên Canny ). – Các toán tửđối sánh hàm ảnh vớimôhìnhthamsố của điểmbiên. • Các mô hình tham số mô tả biên chính xác hơnlàchỉ sử dụng độ lớnvàhướng của biên. •Những phương pháp này yêu cầukhốilượng tính toán lớn. •Rất khó có thể lựachọnchiếnlượcxácđịnh biên tối ưu. •Lĩnh vựcnàyđượctập trung nghiên cứu;
17. 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êncạnh việcxá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ọctìmbiên: • Đánh giá theo xác suấttìmbiênđúng; • Đánh giá theo tỷ lệ tín hiệu trên nhiễu; • Đánh giá theo hướng củabiên; • Đánh giá theo khả năng tách biên
18. Các toán tửđạohàmcấp1 • Các toán tửđạohàmcấp1: – Các toán tử tính gradient theo hai hướng; –Tínhđộ lớncủagradient tổng hợp; –Xácđịnh góc của gradient theo các thành phần; –Lậpbản đồ biên theo ngưỡng
19. Các toán tửđạohàmcấp1 •Toántử Roberts –Cácmặtnạ lọctương ứng vớihaihướng hợpvớilưới ảnh 45o. –Cácmặtnạđượcápdụng riêng rẽ với ảnh đầu vào và cho giá trịđộđo gradient theo mỗihướng ( G1 và G2). –Cácmặtnạ lọc cho phép tính các thành phầnvàhướng của gradient tạitừ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ểđượctínhbằng độ đo Euclide hoặc độ đoL1: |G( m, n )| = | G1( m, n ) | + | G2( m, n )| –Hướng của gradient: ψ = arctan( G2/G1) - 3π/4
20. Các toán tửđạohàmcấp1 –Mặtnạ lọccủatoántử Roberts 1 0 0 1 H = , H = 1 0− 1 2 −1 0 –Vídụ toán tử Roberts
21. Các toán tửđạohàmcấp1 – Ưu điểm: • Đơngiản khi tính toán vì chỉ sử dụng lân cận 2x2 của điểm; •Cácmặtnạ lọc đáp ứng cực đạivới các biên tạo góc 45o vớilưới ảnh. –Nhược điểm: •Nhạycảmvớinhững biếnthiênnhỏ củabiênvìsử dụng ít điểmlâncận để xấpxỉ gradient; • Đáp ứng yếuvớinhững đường biên đích thực, trừ khi các đường biên này rấtnét; •Nhạycảmvới nhiễu
22. Các toán tửđạohàmcấp1 •Toántử Prewitt –Toántử Prewitt xấpxỉ hóa đạohàmbậcnhất; –Toántử Prewitt xác định gradient theo hai hướng trựcgiao theo phương nằm ngang và thẳng đứng; – Gradient xác định theo các sai phân đốixứng: 1 Gmn((= 1, +−−−−++−−+++−−+ 1) sjk),( ([ 1, sjk 1) ( sjksjksjk1,) ( 1,) ( 1,] 1) sjk ( 1, 1) x 3 1 Gmn((= 1, −+−−−+ 1) sjk),( ([ 1, sjk 1) (, sjk +− 1) (, sjk −+++−+− 1) ( sjk 1,] 1) sjk ( 1, 1) y 3 – Môdun củagradient được tính theo độ đo Euclide: 2 2 1/2 G(m, n ) = [((Gx(m, n)) + (Gy(m, n)) ]
23. Các toán tửđạohàmcấp1 – Các ma trậngradient: −1 − 1 − 1 1− 0 1 1 1 H = 0 0 0, H = 1− 0 1 1 3 2 3 1 1 1 1− 0 1 –Vídụ toán tử Prewitt:
24. Các toán tửđạohàmcấp1 – Đặc điểmcủatoántử Prewitt: •Thựchiệnchậmhơntoántử Roberts; •Tốthơntoántử Roberts theo nghĩa tín hiệu trên nhiễuvà xác suấtpháthiệnbiênđúng; •Cóưu điểm trong việcxá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
25. Các toán tửđạohàmcấp1 •Toántử Sobel –Toántử Sobel xấpxỉ hóa đạohàmbậcnhất; –Cácmặtnạđượcthiếtkếđểđáp ứng tối đavớicác biên chạythẳng đứng hoặcnằmngangso vớilưới ảnh; –Toántử 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 đốixứng: 1 Gmn((= 1, +−−−−+ 1) sjk(,) ([ 1, sjk 1)2(( sjksjksjk +−−+++−−+ 1,) ( 1,)) ( 1,] 1) sjk ( 1, 1) x 4 1 Gmn((= 1, −+−−−+ 1) sjk(,) ([ 1, sjk 1)2((, sjk +− 1) (, sjk −+++−+− 1)) sjk ( 1,] 1) sjk ( 1, 1) y 4 – Môdun củagradient đượctínhtheođộ đoL1 hoặc Euclide: 2 2 1/2 G(m, n ) = [((Gx(m, n)) + (Gy(m, n)) ]
26. Các toán tửđạohàmcấp1 –Ma trậnlọccủatoántử Sobel −1 2 − − 1 1− 0 1 1 1 H = 0 0 0 , H = 2− 0 2 1 4 2 4 1 2 1 1− 0 1 –Vídụ toán tử Sobel
27. Các toán tửđạohàmcấp1 – Đặc điểmcủatoántử Sobel: •Toántử Sobel tính biên chậmhơntoántử Roberts; •Mặtnạ tổng chậplớnhơn so vớitoántử Roberts và có tác dụng làm trơnnênítnhạycảmvới nhiễuhơn; •Bêncạ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ớitoántử Roberts do hiệu ứng làm trơn; •Toántử có đầuravới giá trị lớnhơn so vớitoántử Roberts do đódễ làm tràn biểudiễn ảnh; • Làm khuếch đại các thành phầntầnsố cao; •Cóưu điểm trong việcxácđịnh các biên nghiêng 45o so với các biên thẳng đứng hoặcnằm ngang; • Không thể xác định biên về thành đường độ dày 1
28. Các toán tửđạohàmcấp1 • Các toán tử la bàn –Gradient được ướclượng theo 8 hướng theo mặtnạ tổng chập; –Kếtquả củatổng chậpcóđộ lớncực đạichogiátrịđộ lớncủa gradient tại điểm đang xét; –Mặtnạ cho tổng chậpcực đạichỉ hướng củagradient; – Thông thường mặtnạ là ma trận 3x3, tuy vậycóthể có mặtnạ vớikíchthướclớnhơnnhư 5x5, ; – Các toán tử xác định đạohàmbậcnhấtcủahàmảnh thường đượcgọi là các toán tử la bàn hay toán tử quay vìchophépxácđịnh hướng củagradient;
29. Các toán tạ ửđmc à ohấp1 – |G( m, n )| = max { |Gk( m, n )|, k = 0, , 7 } – θk = π/2 + kπ/4 1 1 1 1 1 0 1 0− 1 0− 1 − 1 0 0 0 ,1 0− 1 ,1 0− 1 ,1 0− 1 −1 − 1 − 1 0− 1 − 1 1 0− 1 1 1 0 −1 − 1 − 1 1 − 1 − 0 1− 0 1 0 1 1 0 0 0 , 1 − 0 1 ,1 − 0 1 ,1 − 0 1 1 1 1 0 1 1 1− 0 1 −1 −1 0
30. Các toán tạ ửđmc à ohấp1 5 5 5 t n á o –Tử la bàn Kirsch: −3 0 − 3 −3 − 3 − 3 t n á o –Tử la bàn rewitt:P 1 1 1 0 0 0 −1 − 1 − 1 1 2 1 t n á o –Tử la bàn obel:S 0 0 0 −1 − 2 − 1
31. Các toán tửđạohàmcấp2 •Toántử Laplace: –Biênđượcxácđịnh theo điểm giao không của đạohàmcấphai; –Xácđịnh đạohàmbậchai: 2 2 2 (,)(,)∂s x y ∂s x y Δs(,)(,) x y = ∇ s x y = 2 + 2 –Trường hợpsố hóa: ∂x ∂y Δs(m,n) = 4s(m,n) – [s(m-1,n) + s(m+1,n) + s(m,n-1) + s(m,n+1)] –Ma trậntoántử Laplace: 0− 1 0 1 H = −1 4 − 1 L 4 0− 1 0
32. Các toán tửđạohàmcấp2 – Đặc điểmcủatoántửđạo hàm Laplace: •Làtoántửđạohàmbậc2; •Cáchệ số dương nằmgầntâm •Cáchệ số âm nằm ở vùng ngoài biên; •Tổng các hệ số củabộ lọcbằng 0: không có thành phầnDC; •Toántử Laplace đượctínhtheophương pháp tính tổng chập thông thường. •Nhạycảmvới nhiễu –Mộtsố mặtnạ Laplace thông dụng: 1 1 1 −1 2 − 1 H=1 − 8 1 H = 2− 4 2 1 1 1 −1 2 − 1
33. Các toán tửđạohàmcấp2 Tác động của toán tửđạohàmbậc hai Laplace 0− 1 0 1 H = −1 4 − 1 4 0− 1 0