Xử lý ảnh - Chương 4: Phân vùng ảnh

10/26/2011 1 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 Xử lý ảnh 1 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 10/26/2011 2 Chương 4. Phân vùng ảnh 3 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 Phương pháp phân vùng dựa trên biên 4 Phát hiện sự không liên tục (biến đổi bất thường)  Phát hiện điểm ảnh  Phát hiện đường thẳng  Phát hiện biên Các phương pháp nối biên Các phương pháp làm mảnh đường biên đến 1 pixel 10/26/2011 3 Phát hiện điểm ảnh 5 Phát hiện điểm ảnh 6 T = 90% giá trị max của mức xám 10/26/2011 4 Phát hiện đường thẳng 7 Chọn mặt nạ thích hợp để phát hiện Lấy ngưỡng (thresholding) Phát hiện đường thẳng 8 10/26/2011 5 Phát hiện đường thẳng 9 Giả sử muốn tìm các đường thẳng theo hướng -45 độ Phát hiện biên 10 Xấp xỉ đạo hàm cấp 1, và cấp 2 10/26/2011 6 Phát hiện biên (tiếp) 11 Phát hiện biên (tiếp) 12 Đạo hàm cấp 1:  Bằng 0 tại những điểm không đổi  Khác 0 tại những điểm bắt đầu, kết thúc thay đổi (bắt đầu, kết thúc dốc)  Khác 0 tại những điểm nằm trên dốc Đạo hàm cấp 2:  Bằng 0 tại những điểm không đổi  Khác 0 tại những điểm bắt đầu, kết thúc thay đổi (2 giá trị) o Một giá trị phía bên thấp (tối) o Một giá trị phía bên cao (sáng)  Bằng 0 tại những điểm trên dốc 10/26/2011 7 Phát hiện biên (tiếp) 13 Phát hiện biên (tiếp) 14 10/26/2011 8 Phát hiện biên (tiếp) 15 Nhận xét  Độ lớn của đạo hàm cấp 1: có thể xác định một điểm có nằm trên biên hay không  Dấu trong đạo hàm cấp 2 cho biết điểm ảnh nằm ở vùng sáng hay vùng tối của biên o Đạo hàm cấp 2 luôn có 2 giá trị khác dấu ứng với các điểm trên biên o Điểm cắt 0 có ý nghĩa trong việc tìm biên mỏng Phát hiện biên (tiếp) 16 Ảnh hưởng của nhiễu đến đạo hàm Ảnh gốc + nhiễu Gaussian (mean = 0, delta = 0, 0.1 1, 10) 10/26/2011 9 Phát hiện biên (tiếp) 17 Ảnh hưởng nhiễu  Nhận xét: o Nhiễu trên ảnh gốc nhỏ o Ảnh hưởng trên các đạo hàm rất lớn o Các phép lọc làm trơn ảnh (lọc nhiễu, làm mờ ảnh) thường được áp dụng trước khi lấy đạo hàm  Phát hiện biên o Đạo hàm cấp 1: toán tử gradient o Đạo hàm cấp 2: toán tử laplacian Toán tử gradient 18 Gradient của ảnh f(x, y) tại vị trí (x, y) được định nghĩa 10/26/2011 10 Toán tử gradient (tiếp) 19 Toán tử gradient (tiếp) 20 Cài đặt thực tế 10/26/2011 11 Toán tử gradient (tiếp) 21 Toán tử gradient đường chéo Toán tử gradient (tiếp) 22 10/26/2011 12 Toán tử gradient (tiếp) 23 Toán tử gradient (tiếp) 24 10/26/2011 13 Toán tử gradient (tiếp) 25 Để xác định một điểm ảnh có nằm trên biên hay không  Tính gradient  So sánh với ngưỡng Toán tử Laplacian 26 10/26/2011 14 Toán tử Laplacian (tiếp) 27 Toán tử laplacian thường không được áp dụng trực tiếp để tìm biên  Đạo hàm cấp 2 nhận 2 giá trị tại các điểm trên biên  Rất nhạy với nhiễu  Laplacian không tìm được hướng của biên Áp dụng Laplacian  Smoothing ảnh  Sử dụng thuộc tính cắt 0 (zero-crossing)  Laplacian of Gaussian Laplacian of Gaussian 28 10/26/2011 15 Laplacian of Gaussian (tiếp) 29 Laplacian of Gaussian (tiếp) 30 Áp dụng LoG để phát hiện biên  Tính LoG cuar ảnh  Tìm các điểm cắt 0 (zero crossing) o Áp mặt nạ 3 x 3 cho mỗi pixel o Điểm cắt 0 là những điểm có 2 lân cận đối diện nhau trái dấu 10/26/2011 16 Laplacian of Gaussian (tiếp) 31 Laplacian of Gaussian (tiếp) 32 Tính xấp xỉ LoG  Có thể xấp xỉ LoG bằng DoG (different of gaussian)  Với tỉ lệ: 1.6:1 thì DoG có thể xấp xỉ với LoG 10/26/2011 17 Laplacian of Gaussian 33 Bộ dò biên Canny 34 Là bộ dò biên cho kết quả rất tốt (so với Prewitt, sobel, LoG)  Tỷ lệ lỗi thấp  Phân vùng các điểm trên biên  Trả về biên mỏng (đơn điểm) 10/26/2011 18 Bộ dò biên Canny (tiếp) 35 Các bước thực hiện  Bước 1. Smoothing  Bước 2. Tính Gradients  Bước 3. Loại những điểm không cực đại  Bước 4. Dò các điểm trên biên bằng 2 ngưỡng Bộ dò biên Canny (tiếp) 36 Bước 1. Smoothing  Sử dụng bộ lọc Gaussian  Cài đặt 10/26/2011 19 Bộ dò biên Canny (tiếp) 37 Bước 2. Tính Gradient  Sử dụng bất kỳ mặt nạ Gradient nào  Cài đặt Bộ dò biên Canny (tiếp) 38 Bước 3. Loại những điểm không cực đại  Tính độ lớn và góc của vector gradient  Quantize góc của vector gradient về góc 45 độ gần nhất 10/26/2011 20 Bộ dò biên Canny (tiếp) 39 Bước 3 (tiếp) Bộ dò biên Canny (tiếp) 40 Bước 3 (tiếp)  So sánh M(x, y) với M(x’, y’) theo hướng dương và âm của hướng gradient o Nếu M(x, y) > M(x’, y’) theo cả hai hướng  giữ nguyên: gN(x, y) = M(x, y) o Ngược lại:  loại bỏ: gN(x, y) = 0  Nếu: thì xét điểm (x+1,y) và (x-1, y)  Nếu: thì xét điểm (x,y+1) và (x,y-1)  Nếu: thì xét điểm (x+1,y+1) và (x-1,y-1)  Nếu: thì xét điểm (x+1,y-1) và (x-1,y+1) 10/26/2011 21 Bộ dò biên Canny (tiếp) 41 Bước 4. Dò biên  Lựa chọn 2 giá trị ngưỡng (TH và TL): TH=kTL  Tính 2 ảnh dựa trên 2 ngưỡng này  Loại bỏ những điểm nằm trên biên “mạnh” Bộ dò biên Canny (tiếp) 42 Bước 4 (tiếp)  Những điểm nằm trên biên “mạnh”, gNH được đánh dấu  Những điểm trên biên “yếu”, gNL o Step1. Duyệt qua từng điểm p trong gNH o Step2. Đánh dấu những điểm biên “hợp lệ” trong gNL nếu điểm đó liên thông với p (8 liên thông) o Step 3. Nếu tất cả các điểm khác 0, p trong gNH đều đã được thăm  step 4, ngược lại  step 1 o Step 4. Gán 0 tất cả những điểm trong gNL không được đánh dấu biên “hợp lệ” o Step 5. Thêm những điểm khác 0 trong gNL vào kết quả biên 10/26/2011 22 Bộ dò Canny (tiếp) 43 Bộ dò Canny (tiếp) 44 10/26/2011 23 Bộ dò Canny (tiếp) 45 Bộ dò Canny (tiếp) 46 10/26/2011 24 Phương pháp phân vùng dựa trên biên 47 Phát hiện sự không liên tục (biến đổi bất thường)  Phát hiện điểm ảnh  Phát hiện đường thẳng  Phát hiện biên Các phương pháp nối biên Các phương pháp làm mảnh đường biên đến 1 pixel Các phương pháp nối biên 48 Phương pháp xử lý nối biên cục bộ Phương pháp xử lý toàn cục 10/26/2011 25 Phương pháp xử lý nối biên cục bộ 49 Tổng quát  Tính độ lớn và góc của vector gradient o M(x, y) và 𝛼(𝑥, 𝑦) o Áp mặt nạ (3x 3, hoặc 5 x 5) cho mỗi điểm ảnh (x, y) và kiểm tra  Nếu cả 2 điều kiện cùng thỏa mãn  nối 2 điểm với nhau  Chi phí tính toán lớn Phương pháp xử lý nối biên cục bộ (tiếp) 50 Thuật toán đơn giản hơn  Tính độ lớn và góc của vector gradient o M(x, y) và 𝛼(𝑥, 𝑦)  Tạo ảnh nhị phân g(x, y)  Duyệt các dòng của g và điền (nối liền) các khoảng trắng có độ dài < K  Duyệt tất cả các hướng 𝜃, bằng cách o Quay g một góc 𝜃 áp dụng quét dòng như trên o Quay g một góc -𝜃 10/26/2011 26 Phương pháp xử lý nối biên cục bộ (tiếp) 51 Phương pháp xử lý nối biên toàn cục 52 Tổng quát  Tìm tất cả các đường thẳng tạo bởi 2 điểm bất kỳ  Tìm tất cả các tập điểm nằm trên (gần nằm trên) đường thẳng đó  Độ phức tạp o n(n-1)/2 đường thẳng o Số pháp so sánh n(n(n-1)/2) ~ n3 10/26/2011 27 Phương pháp xử lý nối biên toàn cục 53 Biến đổi Hough (Hough transform)  Xét điểm (xi, yi), đường thẳng đi quay (xi, yi) có dạng: y = ax + b  yi = axi + b  Có thể viết dưới dạng: Biến đổi Hough 54 Cách tính toán  Với mỗi giá trị (x, y) trên miền không gian, quét và điền giá trị trên miền tham số 10/26/2011 28 Biến đổi Hough (tiếp) 55 Giá trị amin, amax, bmin, bmax tùy thuộc vào giá trị các điểm (x, y) Thuật toán:  Bước 1. Xây dựng mảng chỉ số tích lũy H[a, b] và gán giá trị 0 ban đầu  Bước 2. Với mỗi giá trị (xi, yi), với mỗi a, tính b theo b = -xi * a + yi. H[a, b] += 1  Bước 3. Tìm giá trị lớn nhất max của H[a, b], nếu max/N > ngưỡng  kết luận N điểm đã cho cùng nằm trên 1 đường thẳng Biến đổi Hough (tiếp) 56 Ví dụ: cho 5 điểm (0, 1); (1, 3); (2, 5); (3, 5); (4, 9), ngưỡng = 80%. Kiểm tra xem 5 điểm trên có nằm trên 1 đường thẳng hay không? Pt đường thẳng nếu có 10/26/2011 29 Biến đổi Hough trong hệ tọa độ cực 57 Biến đổi Hough (tiếp) 58 Chú ý:  Biến đổi Hough còn có thể áp dụng cho hình tròn, elipse hay bất cứ hàm nào có dạng o F(v, c) = 0  Trong đó: v là vector tọa độ  c là vector tham số 10/26/2011 30 Biến đổi Hough (tiếp) 59 Áp dụng cho bài toán nối biên  Giả sử biên được tìm bằng cách tính toán gradient và lấy ngưỡng  Xây dựng mảng chỉ số tích lũy trên miền tham số [𝜌, 𝜃], thiết lập các phần tử bằng 0 ban đầu  Với mỗi điểm trên miền không gian, cập nhật mảng chỉ tích lũy số trên miền tham số  Xác định mối quan hệ giữa các pixel trong ảnh biên (có thể liên kết với nhau không?) o Liên kết nếu: các pixel cùng có giá trị mảng chỉ số tích lũy lớn o Giới hạn về khoảng cách giữa các pixel Biến đổi Hough (tiếp) 60 10/26/2011 31 Bài tập 61 Sobel Canny 16 4