Xử lý tín hiệu và mã hóa - Chương 4: Phát hiện biên và phân vùng ảnh

Xử lý tín hiệu và mã hóa (Master program) Giảng viên: TS. Phạm Việt Hà Email: phamvietha@gmail.com ĐT CQ: (04).37544486 Địa chỉ CQ: 122 Hoàng Quốc Việt, Cầu Giấy, Hà Nội 1 Chương 4. Phát hiện biên và phân vùng ảnh Viện Khoa học Kỹ thuật Bưu điện 2 4.1 Biên và kỹ thuật phát hiện biên 4.1.1 Phương pháp phát hiện biên trực tiếp 4.1.2 Phương pháp phát hiện biên gián tiếp 4.2 Phân vùng ảnh và phương pháp phân vùng ảnh 4.2.1 Phân vùng ảnh dựa theo ngưỡng biên độ 4.2.2 Phương pháp phân vùng ảnh 4.1. Biên và kỹ thuật phát hiện biên Viện Khoa học Kỹ thuật Bưu điện 3 Biên là vấn đề quan trọng trong trích chọn đặc điểm nhằm tiến tới hiểu ảnh. Cho đến nay chưa có định nghĩa chính xác về biên. Trong mỗi ứng dụng người ta đưa ra các độ đo khác nhau về biên. Một trong có độ đo đó là độ đo về sự thay đổi đột ngột cấp xám. Một số khái niệm cơ bản:  Đ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ụ đối với ảnh đen trắng, một điểm được gọi là điểm biên nếu nó là điểm đen và có ít nhất một điểm trắng nằm bên cạnh.  Đường biên (đường bao): Tập hợp các điểm biên liên tiếp tạo thành một đường biên hay đường bao. 4.1. Biên và kỹ thuật phát hiện biên Viện Khoa học Kỹ thuật Bưu điện 4  Ý nghĩa của đường biên trong xử lý ảnh:  Đườ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.  Thứ hai, người ta sử dụng biên làm phân cách các vùng xám (màu) cách biệt. 4.1. Biên và kỹ thuật phát hiện biên Viện Khoa học Kỹ thuật Bưu điện 5  Phân loại các kỹ thuật phát hiện biên:  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 (mức xám) 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 hai 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 ảnh thì đường phân ranh giữa các vùng đó chính là biên. 4.1. Biên và kỹ thuật phát hiện biên Viện Khoa học Kỹ thuật Bưu điện 6  Quy trình phát hiện biên:  B1. Khử nhiễu ảnh Vì ảnh thu nhận thường có nhiễu, nên bước đầu tiên là phải khử nhiễu. việc khử nhiễu được thực hiện bằng các kỹ thuật khử nhiễu khác nhau. B2. Làm nổi biên Tiếp theo là làm nổi biên bởi các toán tử đạo hàm. B3. Định vị điểm biên Vì các kỹ thuật làm nổi biên có hiệu ứng phụ là tăng nhiễu, do vậy sẽ có một số điểm biên giả cần loại bỏ. B4. Liên kết và trích chọn biên. Như đã nói, phát hiện biên và phân vùng ảnh là một bài toán đối ngẫu. Vì thế cũng có thể phát hiện biên thông qua việc phân vùng ảnh hoặc ngược lại . 4.1. Biên và kỹ thuật phát hiện biên Viện Khoa học Kỹ thuật Bưu điện 7  So sánh phương pháp xác định biên ảnh trực tiếp và gián tiếp:  Phương pháp phát hiện biên trực tiếp: Hiệu quả và ít chịu ảnh hưởng của nhiễu Ảnh có sự biến thiên độ sáng không đột ngột thì phương pháp tỏ ra kém hiệu quả Kết quả của phương pháp là đường biên  Phương pháp phát hiện biên gián tiếp: Khó cài đặt và sử dụng Ảnh có sự biến thiên độ sáng không đột ngột thì phương pháp áp dụng khá tốt Kết quả của phương pháp là ảnh biên 4.1.1. Phương pháp phát hiện biên trực tiếp Viện Khoa học Kỹ thuật Bưu điện 8 4.1.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 giá trị cực đại của đạo hàm. Gradient là vector cho thấy tốc độ thay đổi giá trị độ chói của các điểm ảnh theo hướng nhất định. dx và dy là khoảng cách giữa các điểm theo hướng x và y. Trên thực tế thường dùng dx=1, dy=1. 4.1.1.1. Phương pháp Gradient Viện Khoa học Kỹ thuật Bưu điện 9 Nhận xét: Tuy nói là lấy đạo hàm nhưng thực chất chỉ là mô phỏng và xấp xỉ đạo hàm bằng các kỹ thuật nhân chập vì ảnh số là tín hiệu rời rạc nên đạo hàm không tồn tại Khi ảnh số được biểu diễn như ma trận các điểm ảnh phân bố theo dòng và cột, gradient rời rạc theo hướng x sẽ là: Mặt nạ nhân chập theo hướng x là Hx = Gradient theo hướng y sẽ là: Mặt nạ nhân chập theo hướng y là Hy = 4.1.1.1. Phương pháp Gradient Viện Khoa học Kỹ thuật Bưu điện 10  Ví dụ: 4.1.1.1. Phương pháp Gradient Viện Khoa học Kỹ thuật Bưu điện 11  Ví dụ: Làm nổi đường biên sử dụng phương pháp gradient: a- ảnh gốc; b- lấy đạo hàm riêng theo hướng y; c- lấy đạo hàm riêng theo hướng x; 4.1.1.1. Phương pháp Gradient Viện Khoa học Kỹ thuật Bưu điện 12  Kỹ thuật Prewitt Kỹ thuật sử dụng 2 mặt nạ chập xấp xỉ đạo hàm theo 2 hướng x và y: Các bước tính toán: 4.1.1.1. Phương pháp Gradient Viện Khoa học Kỹ thuật Bưu điện 13  Kỹ thuật Prewitt Ví dụ: 4.1.1.1. Phương pháp Gradient Viện Khoa học Kỹ thuật Bưu điện 14  Kỹ thuật Sobel Kỹ thuật sử dụng 2 mặt nạ chập xấp xỉ đạo hàm theo 2 hướng x và y: Các bước tính toán tương tự như Prewitt + Bước 1: + Bước 2: + Bước 3: Tách ngưỡng theo θ 1 nếu ≥ θ I(x, y) = 0 nếu ngược lại 4.1.1.1. Phương pháp Gradient Viện Khoa học Kỹ thuật Bưu điện 15  Kỹ thuật Sobel | | + | |= θ =34                                                         0172070 8017207 8801720 888017 0172070 8017207 8801720 888017 7000000 6700000 5670000 4567000 3456700 2345670 1234567                             01000 00100 00010 00001 03440140 160344014 161603440 161616034 4.1.1.1. Phương pháp Gradient Viện Khoa học Kỹ thuật Bưu điện 16  Kỹ thuật la bàn  Toán tử la bàn đo gradient theo một số hướng đã chọn. Ta 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ồ.  Bộ lọc H1, H2, H3,, H8 tương ứng với 8 hướng: 0o, 45o, 90o, 135o, 180o,225o,315o.  Nếu ta kí hiệu , 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: 4.1.1.1. Phương pháp Gradient Viện Khoa học Kỹ thuật Bưu điện 17  Kỹ thuật la bàn  Toán tử Kirsh: 4.1.1.1. Phương pháp Gradient Viện Khoa học Kỹ thuật Bưu điện 18  Kỹ thuật la bàn Đáp ứng của mặt nạ tại vùng ảnh có độ màu không đổi sẽ bằng 0. 4.1.1.1. Phương pháp Gradient Viện Khoa học Kỹ thuật Bưu điện 19 Nhận xét:  Phương pháp gradient tốt cho các ảnh có độ xám biến đổi nhiều. Khi ảnh có độ xám biến đổi chậm thì dùng phương pháp Laplace.  Phương pháp Sobel lấy xấp xỉ đạo hàm theo các trục, căn cứ vào điều kiện để xác định một điểm có phải là biên không. 4.1.1.2. Phương pháp Laplace Viện Khoa học Kỹ thuật Bưu điện 20 Khi mức xám thay đổi chậm, các đường biên không rõ nét, miền chuyển tiếp tương đối rộng, phương pháp hiệu quả hơn là dùng đạo hàm bậc hai mà ta gọi là phương pháp Laplace. Việc xấp xỉ đạo hàm bậc hai cho tín hiệu rời rạc (tạm thời xét từng chiều) được thực hiện như sau: Tương tự: 4.1.1.2. Phương pháp Laplace Viện Khoa học Kỹ thuật Bưu điện 21  Toán tử Laplace hai chiều rời rạc có dạng:  Dẫn tới:  Thông thường người ta 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 Laplace. Dưới đây là ba kiểu mặt nạ thường dùng 4.1.1.2. Phương pháp Laplace Viện Khoa học Kỹ thuật Bưu điện 22 Làm nổi đường biên sử dụng phương pháp Laplace với mặt nạ H1 và H2 4.1.1. Phương pháp phát hiện biên trực tiếp Viện Khoa học Kỹ thuật Bưu điện 23  Cần xác định mức ngưỡng (phân ngưỡng) để loại bỏ các điểm ảnh không phải là điểm cực đại (điểm biên cục bộ) 4.1.1. Phương pháp phát hiện biên trực tiếp Viện Khoa học Kỹ thuật Bưu điện 24 Kỹ thuật phát hiện biên trực tiếp:  Ảnh gốc f(x,y) được đưa vào khối làm nổi đường biên.  Ảnh G(x,y) là ảnh gốc đã được tăng cường biên độ đường biên giữa các vùng ảnh.  Tại khối so sánh, người ta so sánh giá trị các điểm ảnh G(x,y) với mức ngưỡng T để xác định vị trí các điểm có mức thay đổi độ chói lớn.  G(x,y) <TL: có sự thay đổi mức chói từ cao xuống thấp G(x,y) >TH: có sự thay đổi mức chói từ thấp lên cao TL và TH: là giá trị mức ngưỡng thấp và cao 4.1.1. Phương pháp phát hiện biên trực tiếp Viện Khoa học Kỹ thuật Bưu điện 25 Kỹ thuật phát hiện biên trực tiếp: Việc lựa chọn giá trị ngưỡng rất quan trọng trong quá trình xác định đường biên:  Khi giá trị T quá cao, các đường biên có độ tương phản thấp sẽ bị mất đi.  Khi T quá thấp, dễ xảy ra hiện tượng xác định biên sai dưới tác động của nhiễu. 4.1.2. Phương pháp phát hiện biên gián tiếp Viện Khoa học Kỹ thuật Bưu điện 26 Quy trình dò biên gián tiếp:  Xác định điểm biên xuất phát  Dự báo và xác định điểm biên tiếp theo  Lặp lại bước 2 cho đến khi gặp điểm xuất phát Nhận xét: khó khăn trong việc khảo sát tính chất của đường biên và phải kiểm tra tất cả 8 điểm-láng giềng của của mỗi điểm Thuật toán dò biên tổng quát: B1. Xác định cặp nền-vùng xuất phát: bằng cách duyệt ảnh từ trên xuống dưới, trái sang phải để lựa chọn điều kiển l B2. Xác định cặp nền-vùng tiếp theo B3. Lựa chọn điểm biên vùng B4. Nếu gặp cặp xuất phát thì dừng, nếu không thì quay lại bước 2 4.1.2. Phương pháp phát hiện biên gián tiếp Viện Khoa học Kỹ thuật Bưu điện 27 Phương pháp khớp nối lỏng : Khái niệm láng giềng 4 và láng giềng 8 Với điểm P được bao phủ xung quanh bởi 8 điểm: P0, P1, P8 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. 4.1.2. Phương pháp phát hiện biên gián tiếp Viện Khoa học Kỹ thuật Bưu điện 28 Phương pháp khớp nối lỏng :  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). Ví dụ: Cho ma trận ảnh chọn θ =2 ta có 4.2. Phân vùng ảnh và phương pháp phân vùng ảnh Viện Khoa học Kỹ thuật Bưu điện 29 Có thể hiểu phâ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 tính chất như cùng mức xám, cùng màu hay cùng độ nhám Dựa vào đặc tính vật lý của ảnh, người ta có nhiều kiểu phân vùng như phân vùng đựa vào vùng đồng nhất hay vùng liền kề, phân vùng ảnh dựa vào biên độ  Không có kỹ thuật phân đoạn nào là vạn năng, theo nghĩa có thể áp dụng cho mọi loại ảnh.  Không có kỹ thuật phân đoạn nào là hoàn hảo. 4.2. 1. Phân vùng ảnh dựa theo ngưỡng biên độ Viện Khoa học Kỹ thuật Bưu điện 30 Kỹ thuật lấy ngưỡng Kỹ thuật này dựa trên một ý tưởng hết sức đơn giản. Một tham số θ, gọi là ngưỡng độ sáng, sẽ được chọn để áp dụng cho một ảnh a[m,n] theo cách sau: 4.2. 1. Phân vùng ảnh dựa theo ngưỡng biên độ Viện Khoa học Kỹ thuật Bưu điện 31 4.2.1.1 Ngưỡng cố định: Sử dụng lược đồ xám để xác định. Nếu lược đồ xám có dạng rắn lượn, có nhiều đỉnh và khe thì sử dụng các khe làm ngưỡng phân vùng 4.2.1.2 Ngưỡng dựa trên lược đồ: Tính toán để xác định ngưỡng 4.2. 1. Phân vùng ảnh dựa theo ngưỡng biên độ Viện Khoa học Kỹ thuật Bưu điện 32 4.2.1.2 Ngưỡng dựa trên lược đồ Thuật toán đẳng liệu  Chia lược đồ thành 2 đoạn bằng một giá trị ngưỡng khởi động ,tức là bằng phần nửa thang độ xám động của ảnh.  Sau đó tính toán độ sáng trung bình của 2 vùng:  m f,0 của những điểm ảnh thuộc đối tượng  mb,0 của những điểm ảnh nền.  Tính giá trị ngưỡng mới  Quá trình này cứ thế sẽ được tiếp tục với các ngưỡng mới cho đến khi nào giá trị ngưỡng không thay đổi nữa thì dừng lại. 1 0 2  B 4.2.2 Phân vùng bằng tách cây tứ phân Viện Khoa học Kỹ thuật Bưu điện 33 Thuật toán này tạo nên một cây mà mỗi nút cha có 4 nút con ở mọi mức trừ mức ngoài cùng. Cây này cho ta hình ảnh rõ nét về cấu trúc phân cấp của các vùng tương ứng với tiêu chuẩn.  Một vùng thỏa chuẩn sẽ tạo nên một nút lá, nếu không nó sẽ tạo nên một nút trong và có 4 nút con tương ứng với việc chia làm 4 vùng.  Ta cứ tiếp tục như vậy cho đến khi phân xong. Các nút của cây biểu diễn số vùng đã phân Với ngưỡng θ cho trước, vùng thuần nhất phải thỏa điều kiện: Độ lệch chuẩn σ < θ  Hoặc Max, Min lần lượt là giá trị lớn nhất và nhỏ nhất của mức xám trong vùng cần chia.  Giá trị điểm ảnh trong vùng bằng cách lấy trung bình giá trị của vùng đó. 4.2.2 Phân vùng bằng tách cây tứ phân Viện Khoa học Kỹ thuật Bưu điện 34 Ví dụ: Cho ảnh S(m, n) , hãy phân vùng theo tiêu chí: ngưỡng θ= 2 và 4.2.2 Phân vùng bằng tách cây tứ phân Viện Khoa học Kỹ thuật Bưu điện 35 Ví dụ: Cho ảnh S(m, n) , hãy phân vùng theo tiêu chí: ngưỡng θ= 2 và 4.2.3 Phân vùng nối hợp (tổng hợp) Viện Khoa học Kỹ thuật Bưu điện 36 Ý tưởng của phương pháp này là xem xét ảnh từ các miền nhỏ nhất rồi hợp chúng lại nếu thỏa tiêu chuẩn để được một miền đồng nhất lớn hơn.  Ta lại tiếp tục với miền thu được cho tới khi không thể hợp được nữa. Số miền còn lại cho ta kết quả phân đoạn. 4.2.3 Phân vùng tổng hợp Viện Khoa học Kỹ thuật Bưu điện 37 Phương pháp hợp vùng được thực hiện như sau:  Giả sử có 2 vùng ω và ω’  Ta xác định cặp các điểm 4 láng giềng (p, q) sao cho p ω và q  ω’  Xác định  Trong đó I(p), I(q) là giá trị mức xám của điểm p và q, θ1 là giá trị ngưỡng cho trước. 4.2.3 Phân vùng tổng hợp Viện Khoa học Kỹ thuật Bưu điện 38 Phương pháp hợp vùng được thực hiện như sau:  Gọi b(ω) và b(ω’) là số điểm biên của 2 vùng ω và ω’  Xét hàm khả năng hợp 2 vùng: Nếu thì có thể hợp 2 vùng ω và ω’ thành 1 vùng 4.2.3 Phân vùng tổng hợp Viện Khoa học Kỹ thuật Bưu điện 39 Ví dụ  Xét khả năng hợp các vùng của ảnh sau, θ1 =3, θ 2 =0.6 4.2.3 Phân vùng tổng hợp Viện Khoa học Kỹ thuật Bưu điện 40 Ví dụ  Gọi A, B, C, D, E lần lượt là các vùng chứa mức xám 1, 2, 4, 6, 8  Ta có bảng 1, đếm số điểm biên các vùng và tính toán các giá trị 4.2.3 Phân vùng tổng hợp Viện Khoa học Kỹ thuật Bưu điện 41 Ví dụ  Xác định hợp vùng Bảng 2 Kết luận: • Có thể hợp được 2 vùng D và E vì 11/10 >θ2 • Có thể hợp được 2 vùng B và C vì 4/6 >θ2