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

Nội dung text: Bài giảng Xử lý ảnh - Chương 4: Phân vùng ảnh (Tiếp) - 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: hiephv@soict.hut.edu.vn 1
2. 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
3. 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
4. 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
5. 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
6. 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
7. Ảnh hưởng của độ sáng 13
8. 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
9. 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
10. Lấy ngưỡng thích nghi (tiếp) 19
11. 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
12. 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
13. 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
14. 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
15. 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
16. 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
17. 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
18. Lấy ngưỡng tối ưu Otsu (tiếp) 35
19. Ảnh hưởng kích thước vùng đến lấy ngưỡng Otsu 37
20. Cải thiện lấy ngưỡng bằng cách kết hợp thông tin biên 39
21. 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
22. 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
23. 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
24. 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
25. 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
26. 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
27. 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
28. 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