›
›

Bài giảng Xử lý ảnh - Chương 4: Phân vùng ảnh - Hoàng Văn Hiệp

pdf 56 trang ngocly 100
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Xử lý ảnh - Chương 4: Phân vùng ảnh - Hoàng Văn Hiệp", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_xu_ly_anh_chuong_4_phan_vung_anh_hoang_van_hiep.pdf

Nội dung text: Bài giảng Xử lý ảnh - Chương 4: Phân vùng ảnh - Hoàng Văn Hiệp

  1. Xử lý ảnh Hoàng Văn Hiệp Bộ môn Kỹ thuật máy tính Viện Công nghệ thông tin và Truyền thông Email: [email protected] 1
  2. Nội dung Chương 1. Giới thiệu chung Chương 2. Thu nhận & số hóa ảnh Chương 3. Cải thiện & phục hồi ảnh Chương 4. Phát hiện tách biên, phân vùng ảnh Chương 5. Trích chọn các đặc trưng trong ảnh Chương 6. Nén ảnh Chương 7. Lập trình xử lý ảnh bằng Matlab và C 2
  3. Chương 4. Phân vùng ảnh Hai phương pháp chính áp dụng trong phân vùng ảnh . Phương pháp dựa trên biên: phát hiện biên . Phương pháp dựa trên vùng ảnh 3
  4. Phân vùng ảnh dựa trên ngưỡng Segmentation Detect Detect discontinuity similarity Edge detection Gradient Zero crossing Optimal Boundary operator (LoG) thresholding thresholding edge Hough Edge linking Transform Region growing 4
  5. Phân vùng ảnh dựa trên ngưỡng (tiếp) Cơ sở . Khi đối tượng và nền được nhóm lại trong các vùng Lựa chọn một ngưỡng T có thể phân tách các vùng . Điểm ảnh p(x, y) o Nếu f(x, y) > T p(x, y) thuộc đối tượng o Nếu f(x, y) < T p(x, y) thuộc nền . Có thể có nhiễu ngưỡng 5
  6. Phân vùng ảnh dựa trên ngưỡng (tiếp) Lấy ngưỡng có thể coi là bài toán xác định hàm T: T = T[x, y, p(x, y), f(x, y)] . f(x, y): biểu diễn mức xám của điểm ảnh (x,y) . p(x, y): hàm mô tả thuộc tính cục bộ của ảnh Ảnh sau lấy ngưỡng . Hai cấp (bi-level) . Đa cấp (multi-level) o 6
  7. Phân vùng ảnh dựa trên ngưỡng (tiếp) Vấn đề: làm sao để chọn giá trị ngưỡng T thích hợp . Nếu T chỉ phụ thuộc f(x, y): phép lấy ngưỡng toàn cục . Nếu T phụ thuộc vào P(x, y) và f(x, y): phép lấy ngưỡng cục bộ . Nếu T phụ thuộc x, y: Phép lấy ngưỡng thích nghi (adaptive thresholding) 7
  8. Phân vùng ảnh dựa trên ngưỡng (tiếp) 8
  9. Phân vùng ảnh dựa trên ngưỡng (tiếp) Các phương pháp lấy ngưỡng . Lấy ngưỡng cứng . Lấy ngưỡng toàn cục . Lấy ngưỡng cục bộ . Lấy ngưỡng thích nghi . Lấy ngưỡng dựa trên kiểm chứng . Lấy ngưỡng dựa trên phân nhóm (gom nhóm) 9
  10. Lấy ngưỡng cứng 10
  11. Lấy ngưỡng cứng (tiếp) Phụ thuộc chủ quan . phân tích histogram Dễ bị ảnh hưởng bởi nhiễu Ảnh hưởng bởi thay đổi độ sáng 11
  12. Ảnh hưởng của nhiễu 12
  13. Ảnh hưởng của độ sáng 13
  14. Ảnh hưởng của độ sáng Nhận xét . Ảnh có độ sáng đồng đều tại các vùng sẽ dễ tìm ngưỡng hơn 14
  15. Lấy ngưỡng toàn cục Cách tiếp cận heuristic . Bước 1. Xác định giá trị khởi tạo của T (thường là giá trị trung bình mức xám ảnh) . Bước 2. Chia ảnh thành 2 vùng: G1 (gồm các điểm ảnh mức xám >= T) và vùng 2 (gốm những điểm ảnh mức xám < T) . Bước 3. Tính giá trị trung bình mức xám của G1 là m1, G2 là m2 . Bước 4. Cập nhật T = (m1 + m2)/2 . Bước 5. Quay lại bước 2 đến khi nào ∆ ≤ 휀 15
  16. Lấy ngưỡng toàn cục (tiếp) 16
  17. Lấy ngưỡng thích nghi Ý tưởng . Ngưỡng toàn cục bị ảnh hưởng bởi độ sáng, nhiễu . Chia nhỏ ảnh thành các phần, sau đó áp dụng tìm ngưỡng khác nhau cho từng phần nhỏ o Vấn đề:  Chia như thế nào là hợp lý  Tìm ngưỡng cho từng phần nhỏ 17
  18. Lấy ngưỡng thích nghi (tiếp) 18
  19. Lấy ngưỡng thích nghi (tiếp) 19
  20. Lấy ngưỡng tối ưu Giả sử ảnh có 2 vùng chính rõ rệt (vùng đối tượng và nền) Một điểm (x, y) trong ảnh có 2 khả năng . H0: Không thuộc vùng đối tượng . H1: Thuộc vùng đối tượng Gọi z là giá trị mức xám trong ảnh (z coi như biến ngẫu nhiên) Các xác suất . Xác suất tiên nghiệm: P1= p( 휖 1); P2= p( 휖 0); 20
  21. Lấy ngưỡng tối ưu (tiếp) p1(z): hàm mật độ phân bố xác suất của các pixel trên đối tượng p2(z): hàm mật độ phân bố xác suất của cnền (chú ý rằng ta chưa có p1(z) và p2(z)) Hàm mật độ phân bố xác suất p(z) 21
  22. Lấy ngưỡng tối ưu (tiếp) T là ngưỡng được chọn để phân vùng ảnh (pixel > T nền và ngược lại) . Xác suất lỗi khi phân vùng các pixel trên nền là đối tượng . Xác suất lỗi khi phân vùng các pixel trên đối tượng là nền . Xác suất lỗi tổng: 22
  23. Lấy ngưỡng tối ưu (tiếp) Bài toán đặt ra là tìm T để, xác suất lỗi nhỏ nhất Giải, áp dụng luật leibniz cuối cùng thu được 23
  24. Lấy ngưỡng tối ưu (tiếp) Để giải . Chúng ta cần biết p1 và p2, tuy nhiên thực tế thì p1 và p2 là chưa biết . giải quyết có 2 cách o C1) Giả sử phân bố p1 và p2 là các phân bố Gaussian (không có giám sát) o C2) Xấp xỉ phân bố p(z) là các phân bố Gaussian từ histogram của ảnh (có giám sát) sao cho tối thiểu hóa: 24
  25. Lấy ngưỡng tối ưu (tiếp)  Phương trình  Lấy lograrit 2 vế đưa phương trình về 25
  26. Lấy ngưỡng tối ưu (tiếp) Chú ý: có thể lấy ngưỡng tối ưu bằng cách xấp xỉ với các hàm khác Gaussian . Raleigh . Log-normal . 26
  27. Lấy ngưỡng tối ưu Otsu Hàm graythresh trong matlab hiện đang cài đặt theo phương pháp này Bài toán . Cho ảnh đa mức xám MxN . L mức xám {0, 1, 2, L-1} . ni: số pixel trong ảnh có mức xám I o MN = n0 + n1 + + nL-1 . Histogram chuẩn hóa: . Tìm ngưỡng t tối ưu 27
  28. Lấy ngưỡng tối ưu Otsu (tiếp) 28
  29. Lấy ngưỡng tối ưu Otsu (tiếp) Với ngưỡng k, ta có 2 lớp pixel Ý tưởng: Tìm ngưỡng sao cho minimizes the weighted within-class variance tương tự với việc maximizing the between-class variance 29
  30. Lấy ngưỡng tối ưu Otsu (tiếp) Weighed within-class variance 2 2 2 w (t) q1(t)1 (t) q2 (t) 2 (t) Trong đó: t I q1(t)  P(i) q2 (t) P(i) i 1 i t 1 30
  31. Lấy ngưỡng tối ưu Otsu (tiếp) Class mean t iP(i) I iP(i)  (t)  (t) 1  2  i 1 q1(t) i t 1 q2(t ) Class variance t P(i) I 2 2 2 2 P(i) 1 (t) [i 1(t)]  (t) [i  (t)] q (t) 2  2 i 1 1 i t 1 q2 (t) 31
  32. Lấy ngưỡng tối ưu Otsu (tiếp) Total variance 2 2 2   w (t) q1(t)[1 q1 (t)][1(t) 2 (t)] Within-class, 2 from before Between-class, B (t) Vì total variance = const Minimize within-class tương đương với maximize between-class 32
  33. Lấy ngưỡng tối ưu Otsu (tiếp) Thuật toán: . Bước 1. Tính histogram, và xác suất tại mỗi giá trị mức xám . Bước 2. Khởi tạo . Bước 3. Duyệt lần lượt các giá trị của t từ 1 đến L-1 o Tính q1(t); 휇1 푡 2 o Tính B (t) . Bước 4. Cập nhật ngưỡng t ứng với lớn nhất 33
  34. Lấy ngưỡng tối ưu Otsu (tiếp) 2 Chú ý có thể tính  B ( t ) bằng cách đệ qui . Khởi tạo: . Đệ qui: 34
  35. Lấy ngưỡng tối ưu Otsu (tiếp) 35
  36. Ảnh hưởng của nhiễu đến lấy ngưỡng Otsu 36
  37. Ảnh hưởng kích thước vùng đến lấy ngưỡng Otsu 37
  38. Cải thiện lấy ngưỡng bằng cách kết hợp thông tin biên Thuật toán . Tính gradient hoặc laplacian của ảnh ban đầu . Lấy ngưỡng trên ảnh gradient hoặc laplacian để loại bỏ các điểm nhiễu . Nhân ảnh ban đầu với ảnh gradient hoặc ảnh laplacian xây dựng histogram . Lấy ngưỡng Otsu của ảnh ban đầu dựa trên histogram vừa tìm được 38
  39. Cải thiện lấy ngưỡng bằng cách kết hợp thông tin biên 39
  40. Phân vùng ảnh dựa trên các thuật toán gom nhóm Mỗi điểm ảnh được đại diện bởi một vector đặc trưng Các đặc trưng có thể là . Giá trị mức xám . Giá trị thành phần mầu sắc . Các độ đo các lân cận (ví dụ giá trị trung bình trong cửa sổ chạy) . Phân nhóm: tiến hành gom các vector giống nhau vào cùng một nhóm 40
  41. Phân vùng ảnh dựa trên các thuật toán gom nhóm (tiếp) Các phương pháp phân nhóm . K-means . ISODATA Thuật toán K-means . Bước 1. Khởi tạo k tâm của k nhóm . Bước 2. Phân loại n điểm vào k nhóm dựa vào khoảng cách đến các tâm . Bước 3. Tính lại tâm của mỗi nhóm (giá trị trung bình), quay lại bước 2 hoặc sang bước 4 . Bước 4. Thuật toán dừng khi tâm các nhóm ở lần i + 1 so với lần thứ i không có thay đổi 41
  42. Thuật toán K-means 42
  43. Thuật toán gom nhóm ISODATA ISODATA là cải tiến của thuật toán K- means . Số lượng các nhóm có thể được điều chỉnh tự động o Nếu 1 nhóm quá tản mạn tách làm 2 nhóm o Nếu 2 nhóm quá gần nhau gộp vào một nhóm . Tính khoảng cách từ tất cả các phần tử đến tất cả các tâm đưa ra quyết định gom nhóm hay tách nhóm 43
  44. Phân vùng ảnh trực tiếp dựa trên miền ảnh  Giả sử R biểu diễn vùng của toàn ảnh, chúng ta có thể chia R ra thành nhiều vùng con khác nhau R1, R2, , Rn thỏa điều kiện: n (a)  Ri R i 1 (b) Ri là một vùng liên thông, với mọi i = 1, 2, , n. (c) Ri  Rj = , i ≠ j. (d) P(Ri) = TRUE, với mọi i = 1, 2, , n. (e) P(Ri  Rj) = FALSE, với mọi i ≠ j 44
  45. Phân vùng ảnh trực tiếp dựa trên miền ảnh (tiếp)  P(Ri) là một hàm logic được định nghĩa trước trên các điểm ảnh trong tập Ri và  là tập hợp rỗng.  Điều kiện (a) để đảm bảo việc phân vùng là hoàn toàn, mỗi điểm ảnh phải thuộc vào một vùng nào đó.  Điều kiện (b) R là một vùng liên thông.  Điều kiện (c) để đảm bảo các vùng phải rời nhau.  Điều kiện (d) để đảm bảo các điểm ảnh trong vùng phải thỏa một tính chất P nào đó.  Điều kiện (e) để đảm bảo hai vùng khác nhau về tính chất P được định nghĩa trước 45
  46. Phân vùng ảnh trực tiếp dựa trên miền ảnh (tiếp) Áp dụng khi ảnh có nhiều nhiễu việc phát hiện biên phức tạp hoặc không thể phát hiện chính xác Tiêu chuẩn xác định tính đồng nhất của miền đóng vai trò rất quan trọng Một số tiểu chuẩn tính đồng nhất . Theo giá trị mức xám . Theo màu sắc, kết cấu ảnh . Theo hình dạng, theo mô hình . 46
  47. Phân vùng ảnh trực tiếp dựa trên miền ảnh (tiếp) Một số phương pháp . Phương pháp lan tỏa vùng (gia tăng vùng – region growing) . Phương pháp phân chia và kết hợp vùng 47
  48. Phương pháp lan tỏa vùng Bắt đầu tại những điểm “hạt giống” Phát triển vùng bằng cách thêm vào tập các điểm “hạt giống” những điểm lân cận thỏa mãn một tính chất cho trước (như cấp xám, màu sắc, kết cấu) – Thỏa mãn hàm P . 4 lân cận . 8 lân cận 48
  49. Phương pháp lan tỏa vùng Tiêu chuẩn : 1. Giá trị sai khác tuyệt đối giữa các điểm ảnh phải nhỏ hơn 65 2. Các điểm ảnh phải là 8 lân cận với nhau và có ít nhất một điểm ảnh nằm trong vùng 49
  50. Phương pháp lan tỏa vùng (tiếp) Ví dụ: Phân vùng áp dụng lan tỏa vùng cho ảnh sau (sự sai khác < 3, seed point là những điểm có giá trị lớn nhất) 0 0 1 2 5 7 1 0 1 1 1 1 1 0 0 0 1 6 6 7 1 0 0 0 0 0 0 0 0 1 2 1 2 1 1 0 0 7 7 7 1 1 1 2 1 1 1 2 0 0 0 6 6 7 1 1 1 2 7 6 6 6 5 5 1 6 7 7 1 1 2 3 1 1 1 6 6 1 1 6 6 7 1 1 0 0 0 1 1 1 1 1 1 6 6 7 1 1 50 0 0 0 0 0 0 1 1 0 0 0 0 1 1
  51. Phương pháp lan tỏa vùng (tiếp) Các điểm ảnh “hạt giống” 0 0 1 2 5 7 1 0 1 1 1 1 1 0 0 0 1 6 6 7 1 0 0 0 0 0 0 0 0 1 2 1 2 1 1 0 0 7 7 7 1 1 1 2 1 1 1 2 0 0 0 6 6 7 1 1 1 2 7 6 6 6 5 5 1 6 7 7 1 1 2 3 1 1 1 6 6 1 1 6 6 7 1 1 0 0 0 1 1 1 1 1 1 6 6 7 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 51
  52. Phương pháp lan tỏa vùng (tiếp) Phát triển vùng. 0 0 1 2 5 7 1 0 1 1 1 1 1 0 0 0 1 6 6 7 1 0 0 0 0 0 0 0 0 1 2 1 2 1 1 0 0 7 7 7 1 1 1 2 1 1 1 2 0 0 0 6 6 7 1 1 1 2 7 6 6 6 5 5 1 6 7 7 1 1 2 3 1 1 1 6 6 1 1 6 6 7 1 1 0 0 0 1 1 1 1 1 1 6 6 7 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 52
  53. Phương pháp phân chia và kết hợp vùng Ý tưởng: . Xác định một luật P(Ri) mà mỗi vùng phải thỏa mãn . Một vùng Ri sẽ được chia thành các vùng nhỏ hơn nếu P(Ri) = FALSE . Hai vùng Ri và Rj sẽ được gộp vào nhau nếu P(Ri ∪ Rj) = TRUE . Thuật toán dừng khi không chia và gộp được nữa 53
  54. Phương pháp phân chia và kết hợp vùng (tiếp) Có nhiều kỹ thuật tách và hợp vùng . Xem xét kỹ thuật tách và hợp vùng theo cấu trúc cây tứ phân 54
  55. KỸ THUẬT TÁCH VÙNG VÀ HỢP VÙNG TỨ PHÂN  P(Ri) = TRUE nếu có ít nhất 80% các điểm trong Ri có tính chất |zj – m| ≤ 2i.  Trong đó:  zj: là cấp xám của điểm ảnh thứ j trong vùng Ri.  m: là giá trị trung bình của vùng Ri.   : là độ lệch chuẩn của các cấp xám trong R . i i 55
  56. TÍNH ĐỘ LỆCH CHUẨN  Khi các vùng được gộp: tất cả các pixel trong vùng nhận giá trị trung bình của vùng n 2 z z  Phương sai:  j  2 j 1 n 1 n 2 z z  Độ lệch chuẩn:  j  j 1 n 1 56