Bài giảng Đồ họa và xử lí ảnh - Chương 5: Phát hiện biên và phân vùng ảnh - Nguyễn Đình Cường

CHƯƠNG V  PHÁT HIỆN BIÊN VÀ PHÂN VÙNG ẢNHA. CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN5.1 Biên và kỹ thuật phát hiện biên	Nhìn chung về mặt toán học người ta coi điểm biên của ảnh là điểm có sự biến đổi đột ngột về độ xám như chỉ ra trong hình dưới đây Mức xámđường bao lý tưởngMức xámđường bậc thanghMức xámđường bao thựcNhư vậy, phát hiện biên một cách lý tưởng là xác định được tất cả các đường bao trong các đối tượng. Định nghĩa toán học của biên ở trên là cơ sở cho các kỹ thuật phát hiện biên. Điều quan trọng là sự biến thiên giữa các điểm ảnh là nhỏ, trong khi đó biến thiên độ sáng của điểm biên (khi qua biên) lại khá lớn.Xuất phát từ cơ sở này người ta thường sử dụng 2 phương pháp phát hiện biên A. CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN(tt ) Phương pháp phát hiện biên trực tiếp: phương pháp này nhằm làm nổi đường biên dựa vào biến thiên về giá trị độ sáng của điểm ảnh. Kỹ thuật chủ yếu là dùng kỹ thuật đạo hàm. Nếu lấy đạo hàm bậc nhất của ảnh ta có phương pháp gradient, nếu lấy đạo hàm bậc 2 ta có kỹ thuật Laplace.  Phương pháp gián tiếp: nếu bằng cách nào đấy ta phân ảnh thành các vùng thì đường phân ranh giữa các vùng đó chính là biên Tách biênA. CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN(tt)5.1.1 Phương pháp gradient	 Phương pháp gradient là phương pháp dò biên cục bộ dựa vào cực đại của đạo hàm. Theo định nghĩa gradient là một vectơ có các thành phần biểu thị tốc độ thay đổi giá trị của điểm ảnh theo hai hướng x và y. Các thành phần của gradient được tính bởi: Với dx là khoảng cách các điểm theo hướng x(khoảng cách tính bằng số điểm) và tương tự với dy. Trên thực tế người ta hay dùng dx=dy=1 Xét trong hệ toạ độ cực ta có Tính đạo hàm theo hướng bất kì đối với  đạt cực đại khi =0Tinh góc r: r=tan-1 và max= rfyfxryxf(x, y)Ta gọi r là hướng của biên A. CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN(tt)5.1.1.1 Kỹ thuật gradient Sử dụng một cặp mặt nạ H1 và H2 trực giao(theo 2 hướng vuông góc). Gọi g1 và g2 là gradient tương ứng theo 2 hướng x và y, thì biên độ của gradient, kí hiệu là g tại điểm(m,n) được tính theo công thức: Với mỗi điểm ảnh I(x, y) của I, đạo hàm theo x, theo y được kí hiệu tương ứng bởi gx, gyĐiều này tương đương với nhân chập ảnh với 2 mặt nạ H1 và H2 Ta gọi H1 và H2 là mặt nạ Robert Ngoài ra trong kỹ thuật Sobel và Prewitt người ta sử dụng 2 mặt nạ sau:Mặt nạ Sobel Mặt nạ Prewitt Gradient được xấp xỉ bởi công thức Thường để giảm thời gian tính toán, người ta còn tính gradient theo các chuẩn sau:hoặc Hình 5.1 Tìm biên dùng mặt nạ sobel A. CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN(tt)5.1.1.2 Toán tử la bànToán tử la bàn đo gradient theo một số hướng đã chọn. Nếu kí hiệu gk là gradient la bàn theo hướng k=/2 +2k với k=0,1, 2,7. Như vậy ta có gradient E theo 8 hướng ngược chiều kim đồng hồ.Có nhiều toán tử la bàn khác nhau. Nhưng ở đây, trình bày một cách chi tiết toán tử Kish. Toán tử này sử dụng mặt nạ 3x3 WSNWEWNSNESEMô hình 8 hướngTrong đó H1, H2, H3, H8 tương ứng với 8 hướng: 00, 450, 900, 1350, 1800, 2250, 3150. Nếu ta kí hiệu Ai, i=1, 2, 8 là gradient thu được theo 8 hướng bởi 8 mặt nạ, biên độ gradient tại (x, y) được tính như sau:A. CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN(tt)5.1.2 Kỹ thuật LaplaceCác phương pháp đánh giá gradient ở trên làm việc khá tốt khi độ sáng thay đổi rõ nét. Khi mức xám thay đổi chậm, miền chuyển tiếp trải rộng, phương pháp hiệu quả hơn đó là phương pháp sử dụng đạo hàm bậc2, gọi là phương pháp Laplace. Toán tử Laplace được định nghĩa như sau:Toán tử Laplace dùng nhiều kiểu mặt nạ khác nhau để xấp xỉ rời rạc đạo hàm bậc hai. Dưới đây là 3 kiểu mặt nạ hay dùng: Trong không gian rời rạc đạo hàm bậc 2 có thể tính:Vậy A. CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN(tt)5.1.3 Phương pháp khớp nối lỏng Khái niệm liên thông 4 và liên thông 8 	Với điểm P được bao phủ xung quanh bởi 8 điểm: P0, P1, P8 . 	Ta có láng giềng 8 của P gồm các điểm: P0, P1, P2, P3, P4, P5, P6, P7 	Láng giềng 4 của P gồm các điểm: P0, P2, P4, P6.b. Phương pháp khớp nối lỏng P3P2P1P4PP0P5P6P7 Xét các điểm p và q là 2 điểm 4 láng giềng.  I(p), I(q): giá trị mức xám của điểm p và q  Nếu thì coi như có cặp biên (p, q). Hình vị trí các láng giềngVí dụ: Cho ma trận ảnh 6236236236236232362314285742857128571436chọn  =3 ta có 142857428571285714Nhận xét:Nếu  giảm thì số khớp sẽ tăng và ngược lại A. CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN(tt)5.1.4 Làm mảnh đường biênÝ tưởng chính của quá trình làm mảnh biên là xoá nhiều lần các điểm biên để giảm bề rộng dòng còn một Pixel. Điều này phải được thực hiện không tách rời đối tượng (tách đối tượng thành 2 phần) cũng như không cần xoá các điểmcuối dòng. Nói cách khác chúng ta có thể nhận thấy làm mảnh là xoá các điểm biên có điều kiện. Ta có giải thuật như sau:Sử dụng quy ước lân cận như hình vẽ, đặt NT(P1) là số các biến đổi 0(trắng) thành 1(đen) trong chuỗi có thứ tự và NZ(P1) là số các lân cận khác 0 của P1. Điểm ảnh P1 bị xoá(đặt bằng 0) nếu :P3P2P9P4P1P8P5P6P7Quy ước các lân cận làm mảnh biên B. CÁC KỸ THUẬT DÒ VÀ MÃ HÓA ĐƯỜNG BIÊN5.2 Kỹ thuật dò biên5.2.1 Kỹ thuật Freeman(dò biên theo ảnh đen trắng)Thuật toánBước1: Quét ảnh đến khi gặp điểm đen. Gọi nó là pixel 1.Bước 2: Lặp	 Nếu “điểm ảnh hiện thời là đen” rẽ phai Ngược lại thì rẽ trai. Dừng khi gặp điểm 1 ban đầu. B. CÁC KỸ THUẬT DÒ VÀ MÃ HÓA ĐƯỜNG BIÊN(tt)Cải tiến thuật toán trên Thuật toánBước1: Quét ảnh đến khi gặp điểm đen. Gọi nó là pixel 1.Bước 2: Lặp	 Nếu “điểm ảnh hiện thời là đen” Thì “dò ngược”. Ngược lại “sang phải”. Đến khi gặp pixel 1 121231146510987B. CÁC KỸ THUẬT DÒ VÀ MÃ HÓA ĐƯỜNG BIÊN(tt)5.2.2 Dò biên theo cặp nền vùngPhương phápTìm cặp điểm (n,v), trong đó n và v là điểm 8 láng giềng, n là điểm nền và v là điểm vùng.Ban đầu có (n0, v0) dựa vào đó ta tìm được (n1, v1), qua trình này cứ tiếp tục. Tổng quát nếu có (ni, vi) ta sẽ tìm (ni+1, vi+1), sao cho ni và ni+1 là 8 láng giềng , vi và vi+1 là 8 láng giềng. Quá trình dò biên theo nền vùng là: tìm 1 dãy các điểm (n0, v0), (n1, v1)(nk, vk) sao cho n0, n1, .nk : chu tuyến nềnv0, v1, .vk : chu tuyến vùng 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 1 1 1 1 1 1 1 0 0 00 0 0 1 1 1 1 1 1 1 1 1 0 00 0 0 1 1 1 1 1 1 1 1 1 0 00 0 0 1 1 1 1 1 1 1 1 0 0 00 0 0 1 1 1 1 1 1 1 0 0 0 00 0 0 0 1 1 1 1 1 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0Cặp (ni+1, vi+1) 8 láng giềng B. CÁC KỸ THUẬT DÒ VÀ MÃ HÓA ĐƯỜNG BIÊN(tt)5.2.3 Mã hoá biên (mã hoá Freeman) Phương pháp mã hoá này cũng là một cách biểu diễn chính xác các điểm đường bao bằng việc sử dụng vị trí tương đối của điểm trên đường bao với điểm trước.2534002070644Xuất phát23214 0567Xích mã hoá đường biên freeman như sau:Cung=(6 0 7 0 2 0 0 2 4 3 5 4 4) Hình 8 liên thông và mã hướng tương ứngB. CÁC KỸ THUẬT DÒ VÀ MÃ HÓA ĐƯỜNG BIÊN(tt)5.2.4 Xấp xỉ bởi đoạn thẳngNối điểm xuất phát R với điểm đang xét Pc bởi một đoạn thẳng. Sau đó tính toạ độ của Pi, một điểm nằm giữa R và Pc sao cho khoảng cách từ Pi đến đoạn thẳng là cực đại. Gọi khoảng cách này là d1. Nếu d1 lớn hơn một ngưỡng cho trước (độ chính xác của xấp xỉ) người ta phân đoạn RPc thành 2 đoạn RPi và PiPc và tiếp tục thực hiện lấy mẫu với từng đoạn cho tới khi đoạn thẳng tìm được là “rất gần” với đường bao.PiRPcdiPidiRPcP1P2RPcHình xấp xỉ đường biên bằng đường gấp khúc C. CÁC PHƯƠNG PHÁP PHÂN VÙNG ẢNHPhân vùng là tiến trình chia ảnh thành nhiều vùng, mỗi vùng chứa một đối tượng hay nhóm đối tượng cùng kiểu. Chẳng hạn, một đối tượng có thể là một kí tự trên một trang văn bản hoặc một đoạn thẳng trong một bản vẽ kỹ thuật hoặc một nhóm các đối tượng có thể biểu diễn một từ hay hay đoạn thẳng tiếp xúc nhau. Ta có một số phương pháp phân vùng ảnh như sau:5.3.1 Thuật toán gán nhãn thành phần liên thôngGiải thuật quét ảnh từ trái sang phải và từ trên xuống dưới. Trong dòng thứ nhất của các pixel đen, một nhãn duy nhất được gán cho mỗi đường chạy liên tục của pixel đen. Với mỗi pixel đen của các dòng tiếp theo, các pixel lân cận trên dòng trước và pixel bên trái được xem xét. Nếu bất kì pixel lân cận nào được gán nhãn, nhãn tương tự được gán cho pixel đen hiện thời; ngược lại nhãn tiếp theo chưa được sử dụng được chọn. Thủ tục này được tiếp tục cho tới dòng cuối của ảnh. Lúc kết thúc tiến trình này, một thành phần liên thông có thể chứa các pixel có các nhãn khác nhau vì khi chúng ta xem xét lân cận của pixel đen, chẳng hạn pixel “?” trong hình vẽ. Pixel đối với lân cận trái và những lân cận trong dòng trước có thể được gán nhãn một cách riêng biệt. Một tình huống như vậy phải được xác định và ghi lại. Sau tiến trình quét ảnh, việc gán nhãn được hoàn tất bằng cách thống nhất các mâu thuẫn các nhãn và gán lại các nhãn chưa sử dụng.. . . . . . . . . ... . . . P P P P . . . .. . . . L ? . . . . . . .. . . . . . . .. . . . . ..P: lân cận trước, L lân cân tráiHình minh hoạ các lân cậnC. CÁC PHƯƠNG PHÁP PHÂN VÙNG ẢNH(tt). . . . . . . . . . . . . . . . . . . . . . . . . . . . . * * * * . . * * * . . . . . 1 1 1 1 . . 2 2 2 . . . . . . * * * . . * * * * . . . . . 1 1 1 . . 2 2 2 2 . . . . * * * * . * * * * * . . . . 1 1 1 1 . 2 2 2 2 2 . . . . . . * * * * * . . . . . . . . . 1 1 ? * * . . . . . . . . . * * * * * * . * . . .  . . . * * * * * * . * . . . * * . . . . . . . . * * . . * * . . . . . . . . * * . . . * * . . . . . . . * * . . . * * . . . . . . . * * . . . * * . . . . . . . . . . . . * * . . . . . . . . . . . Hình b . Ảnh ban đầu Hình c . Tiến trình gán nhãn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 1 1 . . 2 2 2 . . . . . 1 1 1 1 . . 1 1 1 . . . . . . 1 1 1 . . 2 2 2 2 . . . . . 1 1 1 . . 1 1 1 1 . . . . 1 1 1 1 . 2 2 2 2 2 . . . . 1 1 1 1 . 1 1 1 1 1 . . . . . . 1 1 1 1 1 . . . . . . . . . 1 1 1 1 1 . . . . . . . . . 1 1 1 1 1 1 . 3 . . .  . . . 1 1 1 1 1 1 . 2 . . . 4 4 . . . . . . . . 3 3 . . 3 3 . . . . . . . . 2 2 . . . 4 4 . . . . . . . 3 3 . . . 3 3 . . . . . . . 2 2 . . . 4 4 . . . . . . . . . . . . 3 3 . . . . . . . . . . . Hình d . Sau khi quét đầy đủ Hình e .Kết quả sau cùngC. CÁC PHƯƠNG PHÁP PHÂN VÙNG ẢNH(tt)5.3.2 Phân vùng bằng cây tứ phânVới ngưỡng  cho trước, vùng thuần nhất phải thỏa điều kiện Độ lệch chuẩn  2