Bài giảng Xử lý tín hiệu và mã hóa - Chương 4: Phát hiện biên và phân vùng ảnh - Phạm Việt Hà

Nội dung text: Bài giảng Xử lý tín hiệu và mã hóa - Chương 4: Phát hiện biên và phân vùng ảnh - Phạm Việt Hà

1. Xử lý tín hiệu và mã hóa (Master program) Giảng viên: TS. Phạm Việt Hà Email: phamvietha@gmail.com ĐT CQ: (04).37544486 Địa chỉ CQ: 122 Hoàng Quốc Việt, Cầu Giấy, Hà Nội 1
2. Chương 4. Phát hiện biên và phân vùng ảnh 4.1 Biên và kỹ thuật phát hiện biên 4.1.1 Phương pháp phát hiện biên trực tiếp 4.1.2 Phương pháp phát hiện biên gián tiếp 4.2 Phân vùng ảnh và phương pháp phân vùng ảnh 4.2.1 Phân vùng ảnh dựa theo ngưỡng biên độ 4.2.2 Phương pháp phân vùng ảnh Viện Khoa học Kỹ thuật Bưu điện 2
3. 4.1. Biên và kỹ thuật phát hiện biên Biên là vấn đề quan trọng trong trích chọn đặc điểm nhằm tiến tới hiểu ảnh. Cho đến nay chưa có định nghĩa chính xác về biên. Trong mỗi ứng dụng người ta đưa ra các độ đo khác nhau về biên. Một trong có độ đo đó là độ đo về sự thay đổi đột ngột cấp xám. Một số khái niệm cơ bản:  Điểm biên: Một điểm ảnh được coi là điểm biên nếu có sự thay đổi nhanh hoặc đột ngột về mức xám (hoặc màu). Ví dụ đối với ảnh đen trắng, một điểm được gọi là điểm biên nếu nó là điểm đen và có ít nhất một điểm trắng nằm bên cạnh.  Đường biên (đường bao): Tập hợp các điểm biên liên tiếp tạo thành một đường biên hay đường bao. Viện Khoa học Kỹ thuật Bưu điện 3
4. 4.1. Biên và kỹ thuật phát hiện biên  Ý nghĩa của đường biên trong xử lý ảnh: . Đường biên là một loại đặc trưng cục bộ tiêu biểu trong phân tích, nhận dạng ảnh. . Thứ hai, người ta sử dụng biên làm phân cách các vùng xám (màu) cách biệt. Viện Khoa học Kỹ thuật Bưu điện 4
5. 4.1. Biên và kỹ thuật phát hiện biên  Phân loại các kỹ thuật phát hiện biên: . Phương pháp phát hiện biên trực tiếp: Phương pháp này nhằm làm nổi đường biên dựa vào biến thiên về giá trị độ sáng (mức xám) của điểm ảnh. Kỹ thuật chủ yếu là dùng kỹ thuật đạo hàm. Nếu lấy đạo hàm bậc nhất của ảnh ta có phương pháp Gradient, nếu lấy đạo hàm bậc hai ta có kỹ thuật Laplace. . Phương pháp gián tiếp: Nếu bằng cách nào đấy ta phân ảnh thành các vùng ảnh thì đường phân ranh giữa các vùng đó chính là biên. Viện Khoa học Kỹ thuật Bưu điện 5
6. 4.1. Biên và kỹ thuật phát hiện biên  Quy trình phát hiện biên: . B1. Khử nhiễu ảnh Vì ảnh thu nhận thường có nhiễu, nên bước đầu tiên là phải khử nhiễu. việc khử nhiễu được thực hiện bằng các kỹ thuật khử nhiễu khác nhau. .B2. Làm nổi biên Tiếp theo là làm nổi biên bởi các toán tử đạo hàm. .B3. Định vị điểm biên Vì các kỹ thuật làm nổi biên có hiệu ứng phụ là tăng nhiễu, do vậy sẽ có một số điểm biên giả cần loại bỏ. .B4. Liên kết và trích chọn biên. Như đã nói, phát hiện biên và phân vùng ảnh là một bài toán đối ngẫu. Vì thế cũng có thể phát hiện biên thông qua việc phân vùng ảnh hoặc ngược lại . Viện Khoa học Kỹ thuật Bưu điện 6
7. 4.1. Biên và kỹ thuật phát hiện biên  So sánh phương pháp xác định biên ảnh trực tiếp và gián tiếp: . Phương pháp phát hiện biên trực tiếp: Hiệu quả và ít chịu ảnh hưởng của nhiễu Ảnh có sự biến thiên độ sáng không đột ngột thì phương pháp tỏ ra kém hiệu quả Kết quả của phương pháp là đường biên . Phương pháp phát hiện biên gián tiếp: Khó cài đặt và sử dụng Ảnh có sự biến thiên độ sáng không đột ngột thì phương pháp áp dụng khá tốt Kết quả của phương pháp là ảnh biên Viện Khoa học Kỹ thuật Bưu điện 7
8. 4.1.1. Phương pháp phát hiện biên trực tiếp 4.1.1.1. Phương pháp Gradient Phương pháp gradient là phương pháp dò biên cục bộ dựa vào giá trị cực đại của đạo hàm. Gradient là vector cho thấy tốc độ thay đổi giá trị độ chói của các điểm ảnh theo hướng nhất định. dx và dy là khoảng cách giữa các điểm theo hướng x và y. Trên thực tế thường dùng dx=1, dy=1. Viện Khoa học Kỹ thuật Bưu điện 8
9. 4.1.1.1. Phương pháp Gradient Nhận xét: Tuy nói là lấy đạo hàm nhưng thực chất chỉ là mô phỏng và xấp xỉ đạo hàm bằng các kỹ thuật nhân chập vì ảnh số là tín hiệu rời rạc nên đạo hàm không tồn tại Khi ảnh số được biểu diễn như ma trận các điểm ảnh phân bố theo dòng và cột, gradient rời rạc theo hướng x sẽ là: Mặt nạ nhân chập theo hướng x là Hx = Gradient theo hướng y sẽ là: Mặt nạ nhân chập theo hướng y là Hy = Viện Khoa học Kỹ thuật Bưu điện 9
10. 4.1.1.1. Phương pháp Gradient  Ví dụ: Viện Khoa học Kỹ thuật Bưu điện 10
11. 4.1.1.1. Phương pháp Gradient  Ví dụ: Làm nổi đường biên sử dụng phương pháp gradient: a- ảnh gốc; b- lấy đạo hàm riêng theo hướng y; c- lấy đạo hàm riêng theo hướng x; Viện Khoa học Kỹ thuật Bưu điện 11
12. 4.1.1.1. Phương pháp Gradient  Kỹ thuật Prewitt Kỹ thuật sử dụng 2 mặt nạ chập xấp xỉ đạo hàm theo 2 hướng x và y: Các bước tính toán: Viện Khoa học Kỹ thuật Bưu điện 12
13. 4.1.1.1. Phương pháp Gradient  Kỹ thuật Prewitt Ví dụ: Viện Khoa học Kỹ thuật Bưu điện 13
14. 4.1.1.1. Phương pháp Gradient  Kỹ thuật Sobel Kỹ thuật sử dụng 2 mặt nạ chập xấp xỉ đạo hàm theo 2 hướng x và y: Các bước tính toán tương tự như Prewitt + Bước 1: + Bước 2: + Bước 3: Tách ngưỡng theo θ 1 nếu ≥ θ I(x, y) = 0 nếu ngược lại Viện Khoa học Kỹ thuật Bưu điện 14
15. 4.1.1.1. Phương pháp Gradient  Kỹ thuật Sobel 7 6 5 4 3 2 1 0 7 6 5 4 3 2 17 0 8 8 8 17 0 8 8 8 0 0 7 6 5 4 3 20 17 0 8 8 20 17 0 8 8 0 0 0 7 6 5 4 7 20 17 0 8 7 20 17 0 8 0 0 0 0 7 6 5 0 7 20 17 0 0 7 20 17 0 0 0 0 0 0 7 6 0 0 0 0 0 0 7 | | + | |= θ =34 34 0 16 16 16 1 0 0 0 0 40 34 0 16 16 0 1 0 0 0 14 40 34 0 16 0 0 1 0 0 0 14 40 34 0 0 0 0 1 0 Viện Khoa học Kỹ thuật Bưu điện 15
16. 4.1.1.1. Phương pháp Gradient  Kỹ thuật la bàn . Toán tử la bàn đo gradient theo một số hướng đã chọn. Ta kí hiệu gk là gradient la bàn theo hướng θk=π/2 +2kπ với k=0,1, 2, 7. . Như vậy ta có gradient E theo 8 hướng ngược chiều kim đồng hồ. . Bộ lọc H1, H2, H3, , H8 tương ứng với 8 hướng: 0o, 45o, 90o, 135o, 180o,225o,315o. . Nếu ta kí hiệu , i=1, 2, 8 là gradient thu được theo 8 hướng bởi 8 mặt nạ, biên độ gradient tại (x, y) được tính như sau: Viện Khoa học Kỹ thuật Bưu điện 16
17. 4.1.1.1. Phương pháp Gradient  Kỹ thuật la bàn . Toán tử Kirsh: Viện Khoa học Kỹ thuật Bưu điện 17
18. 4.1.1.1. Phương pháp Gradient  Kỹ thuật la bàn Đáp ứng của mặt nạ tại vùng ảnh có độ màu không đổi sẽ bằng 0. Viện Khoa học Kỹ thuật Bưu điện 18
19. 4.1.1.1. Phương pháp Gradient Nhận xét: . Phương pháp gradient tốt cho các ảnh có độ xám biến đổi nhiều. Khi ảnh có độ xám biến đổi chậm thì dùng phương pháp Laplace. . Phương pháp Sobel lấy xấp xỉ đạo hàm theo các trục, căn cứ vào điều kiện để xác định một điểm có phải là biên không. Viện Khoa học Kỹ thuật Bưu điện 19
20. 4.1.1.2. Phương pháp Laplace .Khi mức xám thay đổi chậm, các đường biên không rõ nét, miền chuyển tiếp tương đối rộng, phương pháp hiệu quả hơn là dùng đạo hàm bậc hai mà ta gọi là phương pháp Laplace. .Việc xấp xỉ đạo hàm bậc hai cho tín hiệu rời rạc (tạm thời xét từng chiều) được thực hiện như sau: .Tương tự: Viện Khoa học Kỹ thuật Bưu điện 20
21. 4.1.1.2. Phương pháp Laplace . Toán tử Laplace hai chiều rời rạc có dạng: . Dẫn tới: . Thông thường người ta dùng nhiều kiểu mặt nạ khác nhau để xấp xỉ rời rạc đạo hàm bậc hai Laplace. Dưới đây là ba kiểu mặt nạ thường dùng Viện Khoa học Kỹ thuật Bưu điện 21
22. 4.1.1.2. Phương pháp Laplace .Làm nổi đường biên sử dụng phương pháp Laplace với mặt nạ H1 và H2 Viện Khoa học Kỹ thuật Bưu điện 22
23. 4.1.1. Phương pháp phát hiện biên trực tiếp . Cần xác định mức ngưỡng (phân ngưỡng) để loại bỏ các điểm ảnh không phải là điểm cực đại (điểm biên cục bộ) Viện Khoa học Kỹ thuật Bưu điện 23
24. 4.1.1. Phương pháp phát hiện biên trực tiếp Kỹ thuật phát hiện biên trực tiếp: . Ảnh gốc f(x,y) được đưa vào khối làm nổi đường biên. . Ảnh G(x,y) là ảnh gốc đã được tăng cường biên độ đường biên giữa các vùng ảnh. . Tại khối so sánh, người ta so sánh giá trị các điểm ảnh G(x,y) với mức ngưỡng T để xác định vị trí các điểm có mức thay đổi độ chói lớn. . G(x,y) TH: có sự thay đổi mức chói từ thấp lên cao TL và TH: là giá trị mức ngưỡng thấp và cao Viện Khoa học Kỹ thuật Bưu điện 24
25. 4.1.1. Phương pháp phát hiện biên trực tiếp Kỹ thuật phát hiện biên trực tiếp: Việc lựa chọn giá trị ngưỡng rất quan trọng trong quá trình xác định đường biên: . Khi giá trị T quá cao, các đường biên có độ tương phản thấp sẽ bị mất đi. . Khi T quá thấp, dễ xảy ra hiện tượng xác định biên sai dưới tác động của nhiễu. Viện Khoa học Kỹ thuật Bưu điện 25
26. 4.1.2. Phương pháp phát hiện biên gián tiếp Quy trình dò biên gián tiếp: . Xác định điểm biên xuất phát . Dự báo và xác định điểm biên tiếp theo . Lặp lại bước 2 cho đến khi gặp điểm xuất phát Nhận xét: khó khăn trong việc khảo sát tính chất của đường biên và phải kiểm tra tất cả 8 điểm-láng giềng của của mỗi điểm Thuật toán dò biên tổng quát: B1. Xác định cặp nền-vùng xuất phát: bằng cách duyệt ảnh từ trên xuống dưới, trái sang phải để lựa chọn điều kiển l B2. Xác định cặp nền-vùng tiếp theo B3. Lựa chọn điểm biên vùng B4. Nếu gặp cặp xuất phát thì dừng, nếu không thì quay lại bước 2 Viện Khoa học Kỹ thuật Bưu điện 26
27. 4.1.2. Phương pháp phát hiện biên gián tiếp Phương pháp khớp nối lỏng : Khái niệm láng giềng 4 và láng giềng 8 Với điểm P được bao phủ xung quanh bởi 8 điểm: P0, P1, P8 Láng giềng 8 của P gồm các điểm: P0, P1, P2, P3, P4, P5, P6, P7 Láng giềng 4 của P gồm các điểm: P0, P2, P4, P6. Viện Khoa học Kỹ thuật Bưu điện 27
28. 4.1.2. Phương pháp phát hiện biên gián tiếp Phương pháp khớp nối lỏng : . Xét các điểm p và q là 2 điểm 4 láng giềng. . I(p), I(q): Giá trị mức xám của điểm p và q . Nếu thì coi như có cặp biên (p, q). Ví dụ: Cho ma trận ảnh chọn θ =2 ta có Viện Khoa học Kỹ thuật Bưu điện 28
29. 4.2. Phân vùng ảnh và phương pháp phân vùng ảnh Có thể hiểu phân vùng là tiến trình chia ảnh thành nhiều vùng, mỗi vùng chứa một đối tượng hay nhóm đối tượng cùng tính chất như cùng mức xám, cùng màu hay cùng độ nhám Dựa vào đặc tính vật lý của ảnh, người ta có nhiều kiểu phân vùng như phân vùng đựa vào vùng đồng nhất hay vùng liền kề, phân vùng ảnh dựa vào biên độ . Không có kỹ thuật phân đoạn nào là vạn năng, theo nghĩa có thể áp dụng cho mọi loại ảnh. . Không có kỹ thuật phân đoạn nào là hoàn hảo. Viện Khoa học Kỹ thuật Bưu điện 29
30. 4.2. 1. Phân vùng ảnh dựa theo ngưỡng biên độ Kỹ thuật lấy ngưỡng Kỹ thuật này dựa trên một ý tưởng hết sức đơn giản. Một tham số θ, gọi là ngưỡng độ sáng, sẽ được chọn để áp dụng cho một ảnh a[m,n] theo cách sau: Viện Khoa học Kỹ thuật Bưu điện 30
31. 4.2. 1. Phân vùng ảnh dựa theo ngưỡng biên độ 4.2.1.1 Ngưỡng cố định: Sử dụng lược đồ xám để xác định. Nếu lược đồ xám có dạng rắn lượn, có nhiều đỉnh và khe thì sử dụng các khe làm ngưỡng phân vùng 4.2.1.2 Ngưỡng dựa trên lược đồ: Tính toán để xác định ngưỡng Viện Khoa học Kỹ thuật Bưu điện 31
32. 4.2. 1. Phân vùng ảnh dựa theo ngưỡng biên độ 4.2.1.2 Ngưỡng dựa trên lược đồ Thuật toán đẳng liệu B 1  Chia lược đồ thành 2 đoạn bằng một giá trị ngưỡng khởi động  0 2 ,tức là bằng phần nửa thang độ xám động của ảnh.  Sau đó tính toán độ sáng trung bình của 2 vùng: . m f,0 của những điểm ảnh thuộc đối tượng . mb,0 của những điểm ảnh nền.  Tính giá trị ngưỡng mới  Quá trình này cứ thế sẽ được tiếp tục với các ngưỡng mới cho đến khi nào giá trị ngưỡng không thay đổi nữa thì dừng lại. Viện Khoa học Kỹ thuật Bưu điện 32
33. 4.2.2 Phân vùng bằng tách cây tứ phân .Thuật toán này tạo nên một cây mà mỗi nút cha có 4 nút con ở mọi mức trừ mức ngoài cùng. Cây này cho ta hình ảnh rõ nét về cấu trúc phân cấp của các vùng tương ứng với tiêu chuẩn. . Một vùng thỏa chuẩn sẽ tạo nên một nút lá, nếu không nó sẽ tạo nên một nút trong và có 4 nút con tương ứng với việc chia làm 4 vùng. . Ta cứ tiếp tục như vậy cho đến khi phân xong. Các nút của cây biểu diễn số vùng đã phân .Với ngưỡng θ cho trước, vùng thuần nhất phải thỏa điều kiện: Độ lệch chuẩn σ < θ . Hoặc Max, Min lần lượt là giá trị lớn nhất và nhỏ nhất của mức xám trong vùng cần chia. . Giá trị điểm ảnh trong vùng bằng cách lấy trung bình giá trị của vùng đó. Viện Khoa học Kỹ thuật Bưu điện 33
34. 4.2.2 Phân vùng bằng tách cây tứ phân Ví dụ: Cho ảnh S(m, n) , hãy phân vùng theo tiêu chí: ngưỡng θ= 2 và Viện Khoa học Kỹ thuật Bưu điện 34
35. 4.2.2 Phân vùng bằng tách cây tứ phân Ví dụ: Cho ảnh S(m, n) , hãy phân vùng theo tiêu chí: ngưỡng θ= 2 và Viện Khoa học Kỹ thuật Bưu điện 35
36. 4.2.3 Phân vùng nối hợp (tổng hợp) .Ý tưởng của phương pháp này là xem xét ảnh từ các miền nhỏ nhất rồi hợp chúng lại nếu thỏa tiêu chuẩn để được một miền đồng nhất lớn hơn. . Ta lại tiếp tục với miền thu được cho tới khi không thể hợp được nữa. Số miền còn lại cho ta kết quả phân đoạn. Viện Khoa học Kỹ thuật Bưu điện 36
37. 4.2.3 Phân vùng tổng hợp Phương pháp hợp vùng được thực hiện như sau: . Giả sử có 2 vùng ω và ω’ . Ta xác định cặp các điểm 4 láng giềng (p, q) sao cho p ω và q ω’ . Xác định . Trong đó I(p), I(q) là giá trị mức xám của điểm p và q, θ1 là giá trị ngưỡng cho trước. Viện Khoa học Kỹ thuật Bưu điện 37
38. 4.2.3 Phân vùng tổng hợp Phương pháp hợp vùng được thực hiện như sau: . Gọi b(ω) và b(ω’) là số điểm biên của 2 vùng ω và ω’ . Xét hàm khả năng hợp 2 vùng: .Nếu thì có thể hợp 2 vùng ω và ω’ thành 1 vùng Viện Khoa học Kỹ thuật Bưu điện 38
39. 4.2.3 Phân vùng tổng hợp Ví dụ  Xét khả năng hợp các vùng của ảnh sau, θ1 =3, θ 2 =0.6 Viện Khoa học Kỹ thuật Bưu điện 39
40. 4.2.3 Phân vùng tổng hợp Ví dụ . Gọi A, B, C, D, E lần lượt là các vùng chứa mức xám 1, 2, 4, 6, 8 . Ta có bảng 1, đếm số điểm biên các vùng và tính toán các giá trị Viện Khoa học Kỹ thuật Bưu điện 40
41. 4.2.3 Phân vùng tổng hợp Ví dụ . Xác định hợp vùng Bảng 2 Kết luận: • Có thể hợp được 2 vùng D và E vì 11/10 >θ2 • Có thể hợp được 2 vùng B và C vì 4/6 >θ2 Viện Khoa học Kỹ thuật Bưu điện 41