XỬ LÝ ẢNH Phát hiện biên Thi-Lan Le (lan.vn) SET, HUST 1. Giới thiệu về biên trong ảnh Đ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ụ, trong ảnh nhị phân, điểm đen được gọi là điểm biên nếu lân cận của nó có ít nhất một điểm trắng. Đường biên còn gọi là đường bao (boundary): Là tập hợp các điểm biên liên tiếp.
Giới thiệu về biên trong ảnh Ý nghĩa của đường biên ● Đườ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. ● Người ta sử dụng biên làm phân cách các vùng xám (hoặc màu) cách biệt. Ngược lại, người ta cũng sử dụng các vùng ảnh để tìm phân cách. Giới thiệu về biên trong ảnh Sự không liên tục về pháp tuyến bề mặt Hướng các vector nó khác nhau => không liên tục về bề mặt Source: D.
Giới thiệu về biên trong ảnh Sự không liên tục về độ sâu Source: D. Giới thiệu về biên trong ảnh Sự không liên tục về màu sắc của bề mặt Source: D. Giới thiệu về biên trong ảnh Mô hình biểu diễn đường biên ● Theo toán học, điểm ảnh có sự biến đổi mức xám u(x) một cách đột ngột theo hình dưới: Biến đổi đột ngột Biến đổi bậc thang Biến đổi từ từ 1. Giới thiệu về biên trong ảnh Phát hiện biên - Tìm biên ● Làm nổi lên những điểm ảnh mà tại đó có sự biến đổi lớn về giá trị độ sáng.
● Làm nổi được các vùng khác nhau của ảnh (các vùng có sự biến thiên độ sáng của các vùng là đều) thì có nghĩa là làm nổi được biên của ảnh. Các phương pháp tìm biên (chú trọng 2 pp in đậm) ● Các phương pháp phát hiện biên trực tiếp ● Phát hiện biên gián tiếp 2 Phát hiện biên trực tiếp Phương pháp này chủ yếu dựa vào sự biến thiên độ sáng của điểm ảnh để làm nổi biên bằng kĩ thuật đạo hàm. ● Nếu lấy đạo hàm bậc nhất của f(x,y) ta có phương pháp Gradient ● Nếu lấy đạo hàm bậc hai của f(x,y) ta có phương pháp Laplace Nội dung: ● Kỹ thuật phát hiện biên Gradient ● Kỹ thuật phát hiện biên Laplace ● Kỹ thuật Canny 2 Kỹ thuật phát hiện biên gradient Gradient là một vectơ có các thành phần biểu thị tốc độ thay đổi mức xám của điểm ảnh (theo hai hướng x,y đối với ảnh 2 chiều) tức là: Ta có: ● Trong đó dx, dy là khoảng cách giữa 2 điểm kế cận theo hướng x,y tương ứng (thực tế chọn dx=dy=1) 2 Kỹ thuật phát hiện biên gradient 11 2 Kỹ thuật phát hiện biên gradient Nếu áp dụng Gradient vào xử lý ảnh, việc tính toán sẽ rất phức tạp. Để đơn giản mà không mất tính chất của phương pháp Gradient, người ta sử dụng kĩ thuật Gradient dùng cặp mặt nạ H1,H2 trực giao.
Nếu định nghĩa Gx, Gy tương ứng là Gradient theo hai hướng x,y khi đó ta có vector Gradient của một ảnh f(x,y) là: = Ta có Hướng Biên độ 2 Kỹ thuật phát hiện biên gradient Ví dụ biên độ G(m,n) tại điểm (m,n) được tính: Để giảm độ phức tạp tính toán, G(m,n) được tính gần đúng như sau: Một số toán tử Gradien tiêu biểu như toán tử Prewitt, Sobel, Robert đẳng hướng (Isometric), 4-lân cận. 2 Kỹ thuật phát hiện biên gradient Các công đoạn phát hiện biên theo kỹ thuật Gradient I(x,y) I’(x,y) I’’(x,y) Làm nổi biên So sánh ngưỡng Thực tế, việc làm nổi biên là nhân chập ảnh I với một mặt nạ (ma trận) Kỹ thuật Prewitt Kỹ thuật sử dụng 2 mặt nạ nhập chập xấp xỉ đạo hàm theo 2 hướng x và y là: Bước 1: Tính I Hx và I Hy Bước 2: Tính I Hx + I Hy Kỹ thuật Sobel Tương tự như kỹ thuật Prewitt kỹ thuật Sobel sử dụng 2 mặt nạ nhân chập theo 2 hướng x, y là: Bước 1: Tính I Hx và I Hy Bước 2: Tính I Hx + I Hy Kỹ thuật Sobel Ngoài ra để phát hiện biên theo đường chéo ta sử dụng 2 mặt nạ: Kỹ thuật la bàn Kỹ thuật la bàn Kỹ thuật phát hiện biên Laplace Kỹ thuật phát hiện biên Laplace Kỹ thuật phát hiện biên Laplace Dưới đây là ba kiểu mặt nạ thường dùng: Quan tâm đến 4 hướng xung quanh Quan tâm đến 8 hướng xung quanh Kỹ thuật Canny Kỹ thuật Canny Bước 3: Tính Gradient theo 8 hướng tương ứng với 8 lân cận của 1 điểm ảnh Bước 4: Loại bỏ những điểm không phải cực nhằm xóa bỏ những điểm không thuộc biên Bước 5: Phân ngưỡng. Thực hiện lấy Gradient lần cuối. Biên và độ biến đổi về mức xám Trong thực tế người ta thường dùng hai phương pháp phát hiện biên trục tiếp và phát hiện biên gián tiếp.
Một kỹ thuật khác dựa vào trung bình cục bộ dựa trên cơ sở đánh giá sự chênh lệch mức xám các điểm ảnh so với các điểm lân cận. Đối với một ảnh bất kỳ ta có thể chuyển sang ảnh xám theo công thức: Gray=(R+G+B)/3 Khó khăn đối với phát hiện Biên Một cách lý tưởng (ảnh đen trắng) thì đồ thị sự biến thiên mức xám của các điểm ảnh khi qua biên như sau: Đối với các ảnh đa mức xám thì đồ thị có dạng 2. Phát hiện biên gián tiếp Phân vùng ảnh dựa vào phép xử lý kết cấu đối tượng, cụ thể là dựa vào sự biến thiên nhỏ và đồng đều của các điểm ảnh thuộc một đối tượng. Dựa trên các vùng, đòi hỏi áp dụng lý thuyết về xử lý kết cấu đối tượng phức tạp và khó cài đặt.
Các điểm 4 và 8-láng giềng ● Các điểm P0, P2, P4, P6 là các 4-láng giềng của điểm P ● Các điểm P0, P1, P2, P3, P4, P5, P6, P7 là các 8-láng giềng của P. Chu tuyến của một đối tượng ảnh Chu tuyến của một đối tượng ảnh là dãy các điểm của đối tượng ảnh P1,…,Pn sao cho ● Pi và Pi+1 là các 8-láng giềng của nhau (i=1,.,n-1) ● P1 là 8-láng giềng của Pn, ● i Q không thuộc đối tượng ảnh và Q là 4-láng giềng của Pi (hay nói cách khác i thì Pi là biên 4).Pn> Hình bên biểu diễn chu tuyến của ảnh, trong đó, P là điểm khởi đầu chu tuyến. Tổng các khoảng cách giữa hai điểm kế tiếp của chu tuyến là độ dài của chu tuyến và kí hiệu Len(C) và hướng PiPi+1 là hướng chẵn nếu Pi và Pi+1 là các 4 – láng giềng (trường hợp còn lại thì PiPi+1 là hướng lẻ). Chu tuyến ngoài Chu tuyến trong Thuật toán dò biên tổng quát Có hai kỹ thuật dò biên cơ bản.
● Xét ảnh biên thu được từ ảnh vùng sau một lần duyệt như một đồ thị, sau đó áp dụng các thuật toán duyệt cạnh đồ thị. ● Dựa vào ảnh vùng, kết hợp đồng thời quá trình dò biên và tách biên. Ở đây ta quan tâm cách tiếp cận thứ hai. Về cơ bản, các thuật toán dò biên trên một vùng đều bao gồm các bước sau: ● (1) Xác định điểm biên xuất phát ● (2) Dự báo và xác định điểm biên tiếp theo ● (3) Lặp bước 2 cho đến khi gặp điểm xuất phát Thuật toán dò biên tổng quát ● Bước 1: Xác định cặp nền-vùng (đen-trắng) xuất phát: Duyệt ảnh lần lượt từ trên xuống dưới và từ trái sang phải điểm đem đầu tiên gặp được cùng với điểm trắng trước đó (theo hướng 4) để tạo nên cặp nền vùng xuất phát ● Bước 2: Xác định cặp nền-vùng tiếp theo ● Bước 3: Lựa chọn điểm biên vùng ● Bước 4: Nếu gặp lại cặp xuất phát thì dừng, nếu không quay lại bước 2.
Phát hiện một số hình dạng cơ bản Giả sử đã có kết quả phát hiện biên Biết được phương trình hình học của đối tượng cần tìm (đường thẳng, đường tròn, đường ellipise) Thực hiện 1 trong 2 thuật toán ● Hough transform ● RANSAC Minh họa một số cách làm với đường thẳng ● Đúng cho các đối tượng khác như đường tròn, ellipse Lý thuyết về giả định và kiểm chứng Thuật toán Hough transform Thuật toán Hough transform Thuật toán Hough transform Thuật toán Hough transform Ví dụ minh họa Nhận xét về Hough Transform Nhận xét về thuật toán RANSAC