Báo cáo Xử lý ảnh-Dò biên

BỘ CƠNG THƯƠNG TRƯỜNG ĐẠI HỌC CƠNG NGHIỆP HÀ NỘI KHOA CƠNG NGHỆ THƠNG TIN BÁO CÁO XỬ LÝ ẢNH Đề Tài: Dị biên Giáo viên hướng dẫn: Trần Hùng Cường Nhĩm sinh viên thực hiên: Nguyễn Văn Điệp Nguyễn Huy Đơng Nguyễn Hồng Hiếu TỔNG QUAN VỀ BIÊN VÀ CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN Vị trí của biên trong phân tích ảnh Phân tích ảnh là một qua trình gồm nhiều giai đoạn. Đầu tiên là giai đoạn tiền xử lý ảnh. Sau giai đoạn này, ảnh được tăng cường hay được khơi phục đề làm nồi các đặc tính ( feature extraction ), tiếp theo là phân đoạn ảnh (segmentation) thành các phần tử. Thí dụ, như phân đoạn dựa theo biên, dựa theo vùng,… Và tuỳ theo các ứng dựng, giai đoạn tiếp theo cĩ thể là nhận dạng ảnh ( phân thành các lớp cĩ miêu tả) hay là giải thích và miêu tả ảnh. Hình 1.1 mơ tả tĩm lược các bước của quá trình phân tích ảnh: Trích chọn đặc tính Phân đoạn Phân loại Giải thích Ảnh đầu ra của quá trình tiền XL Hình 1.1. Các bước trong phân tích ảnh Các đặc trưng của ảnh thường gồm: mật độ xám, phân bổ xác xuất, phân bồ khơng gian, biên ảnh. Các kỹ thuật phân đoạn ảnh chủ yếu dựa vào biên. Do đĩ, biên cĩ tầm quan trọng đặc biệt trong qua trình phân tích ảnh. Biên và các kỹ thuật dị biên Trong phần này chúng ta sẽ đề cập đến một số nội dung: khái niệm về biên, phân loại các phương pháp phát hiện biên và qui trình phát hiện biên. Khái niệm về biên Biên là một vấn đề chủ yếu trong phân tích ảnh vì các kỹ thuật phân đoạn ảnh chủ yếu dựa vào biên. Một điểm ảnh cĩ thể coi là điểm biên nếu ở đĩ cĩ sự thay đổi đột ngột về mức xám. Tập hợp các điểm biên tạo thành biên hay đường bao ảnh của ảnh (boundary). Thí dụ, trong một ảnh nhị phân, một điểm cĩ thể gọi là biên nếu đĩ là điểm đen và cĩ ít nhất một điểm trắng là lân cận. Để hình dung tầm quan trọng của biên ta xét ví dụ sau: Khi người hoạ sĩ vẽ một cái bàn gỗ, chỉ cần vài nét phác thảo về hình dáng như cái mặt bàn, chân bàn mà khơng cần thêm các chi tiết khác, người xem đã cĩ thể nhận ra nĩ là một cái bàn. nếu ứng dụng của ta là phân lớp nhận diện đối tượng, thì coi như nhiệm vụ đã hồn thành. Tuy nhiên nếu địi hỏi thêm về các chi tiết khác như vân gỗ hay màu sắc,…thì với chừng ấy thơng tin là chưa đủ. Nhìn chung về mặt tố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ư 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 tố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 mức xám giữa các ảnh trong một vùng thường là nhỏ, trong khi đĩ biến thiên mức xám của điểm vùng giáp ranh (khi qua biên) lại khá lớn. Phân loại các kỹ thuật phát hiện biên Xuất phát từ định nghĩa tốn học của biên người ta thường sử dụng 2 phương pháp phát hiện biên sau: 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 biên dựa vào sự biến thiên về giá trị độ sáng của điểm ảnh. kỹ thuật chủ yếu dùng phát hiện biên ở đây là 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. Hai phương pháp trên được gọi là phương pháp dị biên cục bộ. ngồi ra người ta cịn sử dụng phương pháp “đii theo đường bao”: dựa vào nguyên lý qui hoạch hoạt động và được gọi là phương pháp dị biên tổng thể. Phương pháp gián tiếp: Nếu bằng cách nào đấy , ta phân được ảnh thành các vùng thì đường phân ranh giữa các vùng đĩ chính là biên. việc phân vùng ảnh thường dựa vào kết cấu (texture) bề mặt của ảnh. Cũng cần lưu ý rằng, kỹ thuật dị biên và phân vùng ảnh là hai bài tốn đối ngẫu của nhau. Thực vậy, dị biên để thực hiện phân lớp đối tượng và một khi đã phân lớp xong cĩ nghĩa là đã phân vùng được ảnh. Và ngược lại, khi phân vùng, ảnh đã phân lập được thành các đối tượng, ta cĩ thể phát hiện được biên. Phương pháp dị biên trực tiếp tỏ ra khá hiệu quả vì ít chịu ảnh hưởng của nhiễu. song nếu sự biến thiên độ sáng khơng đột ngột, phương pháp này lại kém hiệu quả. Phương pháp dị biên gián tiếp tuy cĩ khĩ cài đặt song lại áp dụng khá tốt khi sự biến thiên độ sáng nhỏ. Qui trình phát hiện biên trực tiếp 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 tố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 tố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. Một số phương pháp phát hiện biên cục bộ 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 đạii của đạo hàm. Theo định nghĩa, gradient là một véctơ 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: df(x,y) = fx » f(x+dx,y) – f(x,y) dx dx df(x,y) = fy » f(x,y+dy) – f(x,y) dy dy với dx là khoảng cách giữa các điểm theo hướng x ( khoảng các 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 với dx = dy = 1 Trong kỹ thuật gradient, người ta chia thành 2 kỹ thuật (do dùng 2 tốn tử khác nhau): kỹ thuật gradient và kỹ thuật la bàn. kỹ thuật gradient dùng tốn tử gradient lấy đạo hàm theo hai hướng; cịn kỹ thuật la bàn lấy đạo hàm theo 8 hướng chính: Bắc, Nam, Đơng ,Tây và Đơng Bắc, Tây Bắc, Đơng Nam, Tây Nam. Kỹ thuật gradient Kỹ thuật này sử dụng một cặp mặt nạ H1 và H2 trực giao ( theo 2 hướng vuơng gĩc). Nếu định nghĩa g1,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: A0 = g(m,n) = Ư g² 1(m,n) + g22(m,n) (1.2) qr(m,n) = tan-1g2(m,n)/ g1(m,n) (1.3) Chú ý: để giảm tính tốn, cơng thức 1-2 được tính gần đúng bởi: A0 = | g1(m,n) | + | g2(m,n) | Các tốn tử đạo hàm được áp dụng là khá nhiều. ở đây ta chỉ xét một số tốn tử tiêu biểu: tốn tử Robert, Sobel, Prewitt… Trước tiên chúng ta xét tốn tử Robert. Tốn tử này do Robert đề xuất vào năm 1965. Nĩ áp dụng trực tiếp của các cơng thức đạo hàm tại điểm (x,y). 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 được tính: gx = I(x +1,y) – I(x,y) gy =I(x,y+1) – I(x,y) điều này tương đương với việc chập ảnh với 2 mặt nạ H1 và H2: H1 = 0 1 H2 = -1 0 -1 0 0 -1 Ta gọi H1,H2 là mặt nạ Robert. Trong trường hợp tổng quát, giá trị gradient biên độ g và gradient hướng qr được tính bởi cơng thức 1.2 và 1.3. Thường để giảm thời gian tính tốn, người ta cịn tính gradient theo các chuẩn sau: A1 = | g1(m,n) + g2(m,n) | hoặc A2 = max( | g1(m,n) | , | g2(m,n) |) Cần lưu ý rằng, do lạm dụng về ngơn từ, tuy ta lấy đạo hàm của ảnh nhưng thực ra chỉ là mơ phỏng và xấp xỉ đạo hàm bằng kỹ thuật nhân chập do ảnh số là tín hiệu rời rạc, do vậy đạo hàm khơng tồn tại. Trong kỹ thuật Sobel và prewtt người ta sử dụng 2 mặt nạ: H1 = -1 0 1 H2 = -1 -1 -1 -1 0 1 0 0 0 -1 0 1 1 0 1 Ngang (hướng x) Dọc(hướng y) a) mặt nạ Sobel H1 = -1 0 1 H2 = -1 -2 -1 -2 0 2 0 0 0 -1 0 1 1 2 1 Ngang (hướng x) Dọc(hướng y) b) mặt nạ Prewitt H1 = -1 0 1 H2 = -1 - -1 - 0 0 0 0 -1 0 1 1 1 Ngang (hướng x) Dọc(hướng y) c) mặt nạ đẳng hướng (Isometric) Gradient được tính xấp xỉ cơng thức Gx=Hx I và Gy=Hy I (Hx nhân chập với I, Hy nhân chập với I) Thực tế cho thấy rằng các tốn tử Sobel và Prewitt tốt hơn tốn tử Sobel bởi chúng ít nhậy cảm với nhiễu. Kỹ thuật La bàn Về phương pháp kỹ thuật này tương tự kỹ thuật Gradient. Tuy nhiên,điểm khác, kỹ thuật Gradient chỉ lấy đạo hàm theo 2 hướng. cịn kỹ thuật la bàn lấy đạo hàm theo 8 hướng chính: Bắc, Nam, Đơng ,Tây và Đơng Bắc, Tây Bắc, Đơng Nam, Tây Nam. Bằng cách sử dụng 8 mặt nạ cho 8 hướng khác nhau. Phương pháp Laplace Các phương pháp đánh giá Gradient ở trên làm việc khá tốt khi mà độ sáng thay đổi rõ nét. Khi mức sáng thay đổi chậm, miền chuyển tiếp trải rộng, phương pháp cho hiệu quả hơn đĩ là sử dụng phương pháp đạo hàm bậc hai gọi là phương pháp Laplace. Kết quả nghiên cứu cho thấy phương pháp Gradient rất nhậy cảm với nhiễu và thường tạo nên biên kép. Tốn tử Laplace dùng nhiều kiểu mặt nạ khác nhau để xấp xỉ đạo hàm bậc hai. Dưới đây là 3 kiểu mặt nạ hay dùng. 0 -1 0 -1 -1 -1 1 -2 1 H1= -1 4 -1 H2= -1 8 -1 H2= -2 8 -2 0 -1 0 -1 -1 -1 1 -2 1 Kỹ thuật laplace cho đường biên mảnh, tức là đường biên cĩ độ rộng bằng một pixel. Tuy nhiên, kỹ thuật này rất nhạy cảm với nhiễu vì đạo hàm bậc hai thường khơng ổn định. Các phương pháp do biên gián tiếp (phân vùng ảnh) Giới thiệu Như phần trên đã trình bày, Nếu bằng cách nào đấy, ta phân được ảnh thành các vùng thì đường phân ranh giữa các vùng đĩ chính là biên. việc phân vùng ảnh thường dựa vào kết cấu (texture) bề mặt của ảnh. Kỹ thuật dị biên và phân vùng ảnh là hai bài tốn đối ngẫu của nhau. Thực vậy, dị biên để thực hiện phân lớp đối tượng và một khi đã phân lớp xong cĩ nghĩa là đã phân vùng được ảnh. Và ngược lại, khi phân vùng, ảnh đã phân lập được thành các đối tượng, ta cĩ thể phát hiện được biên. Do vậy, Phân vùng ảnh là bước then chốt trong xử lý ảnh. Giai đoạn này nhằm phân tích ảnh thành các thành phần cĩ cùng tính chất nào đấy dựa vào biên hay những vung liên thơng. Tiêu chuẩn để xác định các vùng liên thơng cĩ thể là cùng mức xám, cùng màu, v..v… Vùng ảnh là một thuộc tính quan trọng của ảnh. Nĩi đến vùng ảnh là nĩi đến kết cấu bề mặt. Đường bao quanh một vùng ảnh gọi là biên ảnh. CHƯƠNG TRÌNH ỨNG DỤNG Giới thiệu Phần 1 đã trình bày khái quát về vai trị và tầm quan trọng của biên trong quá trình xử lý ảnh. Đồng thời, phần 1 cũng đã trình bày khái niệm về biên ảnh cũng như các phương pháp dị biên của ảnh nhị phân trong máy tính. Để áp dụng lý thuyết đã trình bày ở phần 1, Phần này sẽ giới thiệu một chương trình ứng dụng tìm biên của ảnh. Chương trình này áp dụng các kỹ thuật do biên trực tiếp là kỹ thuật Gradient và Laplace. Trong kỹ thuật Gradient, các tốn tử Sobel và Prewitt được sử dụng. Tiếp đĩ chương trình cũng giới thiệu một phương pháp dị biên gián tiếp thơng qua việc phân vùng ảnh. Chương trình được viết trên ngơn ngữ Visual C++ 6.0. Các chức năng trong chương trình Chương trình bao gồm các chức năng chính sau: Đọc một ảnh nhị phân: ảnh cĩ thể là đen trắng, ảnh màu (16 màu hoặc 256 màu) dạng bitmap (*.bmp). Lưu ảnh: lưu ảnh đã biến đổi ra file Dị biên ảnh bao gồm các chức năng sau Theo kỹ thuật Gradient: bằng cách sử dụng tốn tử Sobel và Prewitt. Theo kỹ thuật Laplace: sử dụng tốn tử Laplace-H2. Dị biên gián tiếp theo phân vùng ảnh: dị biên theo màu của ảnh. Chi tiết các chức năng dị biên và thuật tốn Dị biên theo kỹ thuật Gradient Theo như phần lý thuyết đã trình bày, kỹ thuật Gradient dị biên theo 2 hướng x và y bằng cách sử dụng hai mặt nạ nhân chập theo hai hướng Chương trình sử dụng hai tốn tử là Sobel và Prewitt như sau. H1 = -1 0 1 H2 = -1 -1 -1 -1 0 1 0 0 0 -1 0 1 1 0 1 Ngang (hướng x) Dọc(hướng y) a) mặt nạ Sobel H1 = -1 0 1 H2 = -1 -2 -1 -2 0 2 0 0 0 -1 0 1 1 2 1 Ngang (hướng x) Dọc(hướng y) b) mặt nạ Prewitt Giả sử Gx và Gy là 2 ma trận điểm ảnh thu được sau khi nhân chập với 2 mặt nạ theo hai hướng tương ứng. Ma trận điểm ảnh G được tính xấp xỉ theo cơng thức sau: G=|Gx| + |Gy| Thuật tốn dị biên theo phương pháp Gradient như sau: Đầu vào: ma trận ảnh cần tìm biên: mặt nạ I1 và I2 Đầu ra: Một ma trận ảnh (chứa các đường biên được tìm thấy). Giải thuật // Gradient Algorithm For (mỗi điểm ảnh của ảnh) if(Nếu điểm ảnh nẳm trên đường viền ảnh) Gán giá trị các điểm ảnh trên đường viền ảnh =0 (hoặc bằng màu nền ảnh). else { - Tính xấp xỉ Gradient theo chiều x (Gx): nhân chập với mặt nạ I1 -Tính xấp xỉ Gradient theo chiều y (Gy): nhân chập với mặt nạ I2 -Tính giá trị điểm ảnh theo cơng thức xấp xỉ G: G=|Gx|+ |Gy| - Nếu giá trị điểm ảnh lớn hơn chỉ số màu của ảnh thì gán giá trị ảnh là giá trị màu lớn nhất. } Để dễ hiểu, phần dưới đây sẽ minh hoạ thêm về giải thuật này: Ma trận ảnh vào Mặt nạ a11 a12 a13 .... a1n a21 a22 a23 .... a2n a31 a32 a33 .... a3n .. .. .. .. m11 m12 m13 m21 m22 m23 m31 m32 m33 Ma trận ảnh ra sau khi nhân chập b11 b12 b13 .... b1n b21 b22 b23 .... b2n b31 b32 b33 .... b3n .. .. .. .. Trong đĩ: b22=(a11*m11)+ (a12*m12)+ (a12*m13)+ (a21*m21) + (a22*m22) + (a23*m23) + (a31*m31)+ (a32*m32)+ (a33*m33). Các giá trị nằm trên đường viền được gán =0 (hay giá trị màu nền). (b11,b12,...b1n,b11....bn1,b1n...bnn, bn1...bnn) Đây là cơng thức tính Gx và Gy Để tính giá trị điểm ảnh đầu ra, sử dụng cơng thức: G=|Gx|+ |Gy| Phương pháp dị biên theo kỹ thuật Laplace Kỹ thuật Laplace dị biên theo cách tính xấp xỉ đạo hàm bậc hai dựa trên một mặt nạ. Chương trình sử dụng mặt nạ H2 trong cách dị biên theo kỹ thuật Laplace. -1 -1 -1 H2= -1 8 -1 -1 -1 -1 Gọi G là ma trận điểm thu được sau khi nhân chập ma trận điểm ảnh (của ảnh cần tìm biên)với mặt nạ H2. G chính là ma trận điểm ảnh chứa các đường biên cần tìm. Thuật tốn dị biên theo phương pháp Gradient như sau: Đầu vào: ma trận ảnh cần tìm biên: mặt nạ H2 Đầu ra: Một ma trận ảnh (chứa các đường biên được tìm thấy). Giải thuật // Laplace Algorithm For (mỗi điểm ảnh của ảnh) if(Nếu điểm ảnh nẳm trên đường viền ảnh) Gán giá trị các điểm ảnh trên đường viền ảnh =0 (hoặc bằng màu nền ảnh). else { - Tính xấp xỉ Laplace G: nhân chập với mặt nạ I1 - Nếu giá trị điểm ảnh lớn hơn chỉ số màu của ảnh thì gán giá trị ảnh là giá trị màu lớn nhất. } Phương pháp dị biên gián tiếp Dựa trên kỹ thuật phân vùng ảnh, Phương pháp này dị biên theo sự thay đổi mức xám màu của ảnh. Nếu những điểm ảnh nào cĩ cùng màu hoặc cĩ màu khác nhưng khoảng cách màu nằm trong phạm vi cho phép, đồng thời nằm kề nhau sẽ tạo thành một vùng. Định nghĩa khoảng cách màu: Khoảng cách màu là một khái niệm để chỉ sự khác nhau về giá trị màu của các điểm ảnh. Giả sử a và b là 2 giá trị màu của 2 điểm ảnh. Khoảng cách màu d của a và b được tính như sau: d(a,b)=|Ra-Rb| + |Ga-Gb| + |Ba-Bb| Trong đĩ Ra: là giá trị màu đỏ tại điểm ảnh Ga: là giá trị màu xanh (green)tại điểm ảnh Ba: là giá trị màu xanh da trời (blue) tại điểm ảnh. Nếu khoảng cách màu d=0 thì 2 điểm ảnh đĩ cĩ cùng màu. Đường biên giữ các vùng chính là các đường biên cần tìm. Thuật tốn tìm đường biên dựa trên sự biến thiên giá trị màu của các điểm ảnh. Đầu vào: Ma trận điểm ảnh, khoảng cách màu tối thiểu Đầu ra: Ma trận điểm ảnh mới (chứa các đường biên tìm thấy). Giải thuật: For (mỗi điểm ảnh của ảnh) { - Tính khoảng cách màu của điểm ảnh với các điểm ảnh lân cận: Tính theo 8 hướng của điểm ảnh if(Nếu cĩ một khoảng cách màu lớn hơn khoảng cách màu cho phép) { - Ghi nhận điểm ảnh này là một điểm biên mới. } } Tài Liệu Tham Khảo Luận Văn Tốt nghiệp NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP PHÁT HIỆN BIÊN VÀ ỨNG DỤNG Giáo Trình Xử Lý Ảnh…………………………………ĐH Back Khoa Giáo Trình Xử Lý Ảnh…………………………………ĐH Thái Nguyên Và 1 số tài liệu trên mạng khác Chương trình tham khảo