Bài giảng Xử lý ảnh số - Bài: Phân tích ảnh Phân vùng ảnh ( Segmentation) - Nguyễn Linh Giang

Nội dung text: Bài giảng Xử lý ảnh số - Bài: Phân tích ảnh Phân vùng ảnh ( Segmentation) - Nguyễn Linh Giang

1. Xử lý ảnh số Phân tích ảnh Phân vùng ảnh ( Segmentation ) Chương trình dành cho kỹ sư CNTT Nguyễn Linh Giang
2. Vùng ảnh và phân vùng ảnh • Bài toán phân vùng ảnh: – Phân tách ảnh thành những tập hợp điểm không giao nhau ( phân hoạch ) –Mục đích: phục vụ bài toán nhận dạng ảnh, hiểu ảnh và những bài toán liên quan tới xử lý vùng; – Phân vùng ảnh là bài toán xác định yếu ( ill- defined ): •Việc xác định các vùng ảnh phụ thuộc vào ngữ cảnh.
3. Vùng ảnh và phân vùng ảnh • Các phương pháp phân vùng ảnh – Phân vùng dựa trên đường biên: • Xác định đường ranh giới giữa những vùng lân cận; – Phân vùng dựa trên ngưỡng: • Tìm các vùng ảnh bằng cách nhóm các điểm có giá trị mức xám tương tự nhau; – Phân vùng ảnh dựa trên các miền: • Xác định trực tiếp các vùng ảnh dựa trên việc gia tăng hoặc phân chia vùng; – Phân vùng dựa trên chuyển động: • Xác định vùng dựa trên việc so sánh các khung video liên tiếp trong một chuỗi video để xác định các vùng tương ứng với đối tượng chuyển động;
4. Vùng ảnh phân vùng ảnh •Biểu diễn vùng ảnh: –Biểu diễn bằng mã loạt dài ( run-length code ) • Vùng trên ảnh nhị phân là chuỗi các giá trị 0 và 1; –Biểu diễn bằng các miền và cây tứ phân
5. Phân vùng ảnh dựa trên ngưỡng –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ámcủa điểm (x, y); • p(x, y): là hàm mô tả thuộc tính cục bộ của điểm ảnh; –Ví dụ: p(x, y) là mức xám trung bình trong lân cận điểm (x, y); – Ảnh sau khi lấy ngưỡng là: ⎧1, if f (x, y) > T g(x, y) = ⎨ ⎩0, if f (x, y) < T –Nếu: •Ngưỡng T chỉ phụ thuộc f(x,y): ngưỡng toàn cục; •Ngưỡng T phụ thuộc vào cả f(x, y) và p(x, y): ngưỡng cục bộ; •Ngưỡng T phụ thuộc vào các tọa độ x, y: ngưỡng động
6. Phân vùng ảnh dựa trên ngưỡng • Các tiêu chuẩn lựa chọn ngưỡng: – Xác suất lỗi cực tiểu –Giá cực tiểu –Phương sai trong nhóm cực tiểu –Kiểm tra bằng mắt
7. Phân vùng ảnh dựa trên ngưỡng •Lấy ngưỡng theo kiểm chứng – Đặt vấn đề: điểm (x,y) với cường độ sáng u nằm trong vùng hay không ? –Hai khả năng: •H0: không nằm trong vùng; •H1: nằm trong vùng; –Các xác suất: • Xác suất tiên nghiệm: P1 = p(z∈H0) , P2 = p(z∈H1) • Hàm khả năng: p(z|z∈H0) = p1(z), p(z| z∈ H1) = p2(z)
8. Phân vùng ảnh dựa trên ngưỡng •Ví dụ trường hợp phân bố Gauss: 1 ⎛ − ()z − µ 2 ⎞ – Cho p (z) = exp⎜ i ⎟ i ⎜ 2 ⎟ 2πσ ⎝ 2σ i ⎠ – Xác định ngưỡng T, giải phương trình: P1 p1(T) = P2 p2(T) –Lấy logarithm cả hai vế ta đưa về phương trình: AT2 + BT + C = 0 2 2 2 2 A = σ1 −σ 2 B = 2(µ1σ 2 − µ2σ1 ) ⎛σ P ⎞ 2 2 2 2 2 2 ⎜ 2 1 ⎟ C = σ1 µ2 −σ 2 µ1 + 2σ1 σ 2 ln⎜ ⎟ ⎝σ1P2 ⎠ µ + µ σ 2 ⎛ P ⎞ 1 2 ⎜ 2 ⎟ If σ1 = σ 2 = σ , then T = + ⋅ln⎜ ⎟ 2 µ1 − µ2 ⎝ P1 ⎠
9. Phân vùng ảnh dựa trên ngưỡng – Bài toán phân nhóm: • Cho tập các vector: {sk; 1 ≤ k ≤ K}, • Xác định M phân nhóm với các tâm {w(i); 1 ≤ i ≤ c}, sao cho các vector sk được đưa vào một phân nhóm thỏa mãn điều kiện tối thiểu hóa sai số khoảng cách: 1 c K D = ∑∑I(xk ,i)d(xk ,W (i)) K i==11k – Trong đó • I(sk,i) = 1 nếu sk được gán vào phân nhóm i với trọng tâm w(i); • I(sk,i) = 0 trong những trường hợp khác.
10. Phân vùng ảnh dựa trên ngưỡng –Thuật toán ISODATA: •Cải tiến so với K-means: – Thay đổi số phân nhóm một cách tự động: –Nếu một phân nhóm quá tản mạn thì được tách làm 2; –Nếu hai phân nhóm khá gần nhau thì nhập làm một. –Bổ sung thêm: »Tính khoảng cách trung bình giữa những phần tử trong một phân nhóm Ci với tâm zi; »Tính khoảng cách trung bình của tất cả các phần tử trong các phân nhóm đến các tâm; »Tính độ lệch tiêu chuẩn trung bình giữa các phần tử trong phân nhóm với tâm theo từng chiều – Các giá trị này phục vụ quá trình phân tách và kết hợp các phân nhóm.
11. Phân vùng ảnh dựa trên miền ảnh •Vị từ xác định vùng ảnh: – Xác định các vùng trực tiếp – Quá trình phân vùng chia ảnh thành các miền {Ri} thỏa mãn: n R = U Ri , Ri ∩ R j = ∅ , i ≠ j i=1 – Các vùng ảnh được xác định theo vị từ P sao cho: • P(Ri) = TRUE nếu tất cả các điểm trong vùng thỏa mãn những thuộc tính xác định; • P(Ri ∩Rj) = FALSE đối với i ≠j.
12. Phân vùng ảnh dựa trên miền ảnh •Phương pháp kết hợp vùng –Thuật toán cơ sở: • Xác định phương pháp phân chia ảnh thành những vùng nhỏ thỏa mãn điều kiện P(Ri) = TRUE ; • Xác định tiêu chuẩn hợp hai miền liền kề; •Kết hợp các miền liền kề thỏa mãn điều kiện hợp. Nếu không có hai miền nào có thể hợp mà không phá vỡ điều kiện vùng, dùng thuật toán. –Các phương pháp hợp vùng ảnh khác nhau ở quá trình xác định vùng ban đầu và tiêu chuẩn hợp; –Kết quả hợp vùng phụ thuộc vào trình tự hợp của các vùng.
13. Phân vùng ảnh dựa trên miền ảnh –Cấu trúc lưới chứa thông tin phục vụ quá trình hợp vùng 4-liên thông sử dụng các giá trị biên. –Một số heuristic: • Hai vùng liền kề có thể kết hợp lại nếu phần lớn biên chung chứa các điểm biên yếu; • Hai vùng liền kề có thể kết hợp lại nếu phần lớn biên chung chứa các điểm biên yếu nhưng trong trường hợp này không tính đến độ dài tổng cộng của đường biên của vùng.
14. Phân vùng ảnh dựa trên miền ảnh –Thuật toán kết hợp vùng qua đường biên: • Xác định các vùng với mức xám không đổi. Xây dựng cấu trúc lưới chứa thông tin giá trị biên; •Loại bỏ các điểm biên có giá trị biên nhỏ hơn ngưỡng; •Loại bỏ các biên chung giữa hai miền liền kề Ri, Rj bằng đệ quy nếu W ≥ T2 min(li ,l j ) Trong đó W là số lượng các điểm biên yếu trên đường biên chung, li và lj là độ dài chu vi ngoài của các vùng Ri, Rj, T2 là ngưỡng; •Loại bỏ các biên chung giữa hai miền liền kề Ri, Rj bằng đệ quy nếu W ≥ T l 3 hoặc W >= T3 trong đó l là độ dài đường biên chung và T3 là ngưỡng
15. Phân vùng ảnh dựa trên miền ảnh •Phương pháp kết hợp: phân chia và hợp vùng: – Xác định các vùng khởi tạo, các điều kiện đồng nhất, cấu trúc tứ diện; –Nếu vùng R trong cấu trúc tứ diện không đồng nhất ( H(R)=FALSE ), chia vùng thành 4 vùng con; Nếu 4 vunngf có cùng một cha có thể kêt hợp thì kết hợp thành một; –Nếu hai vùng liền kề không cùng cha và thỏa mãn điều kiện đồng nhất, hợp hai vùng này lại.