So sánh một số phương pháp phát hiện biên

Tạp chí Khoa học ĐHQGHN: Khoa học Tự nhiên và Công nghệ, Tập 31, Số 2 (2015) 1-7<br /> <br /> <br /> <br /> <br /> So sánh một số phương pháp phát hiện biên<br /> <br /> Nguyễn Vĩnh An*<br /> Bộ Thông tin và Truyền thông, 18 Nguyễn Du, Hà Nội, Việt Nam<br /> Nhận ngày 18 tháng 7 năm 2014<br /> Chỉnh sửa ngày 20 tháng 8 năm 2014; Chấp nhận đăng ngày 28 tháng 5 năm 2015<br /> <br /> <br /> Tóm tắt: Phát hiện biên của ảnh là một trong những nhiệm vụ quan trọng trong xử lý ảnh. Nhận<br /> dạng ảnh dùng máy tính liên quan tới việc nhận dạng và phân loại các đối tượng trong bức ảnh do<br /> đó phát hiện biên là một công cụ quan trọng. Phát hiện biên sẽ làm giảm một cách đáng kể khối<br /> lượng dữ liệu cần xử lý và loại bỏ các thông tin không cần thiết trong khi vẫn đảm bảo các thuộc<br /> tính quan trọng về cấu trúc của ảnh. Có rất nhiều kỹ thuật phát hiện biên hiện đang được sử dụng,<br /> mỗi kỹ thuật này thường làm việc một cách có hiệu quả cao đối với một loại đường biên cụ thể.<br /> Trong bài báo này, tác giả tiến hành so sánh một số kỹ thuật phát hiện biên thông dụng thông qua<br /> các thuật toán được lập trình trên MATLAB.<br /> Từ khóa: Canny, Laplacian of Gaussian (LOG), Sobel, Prewitt, Robert.<br /> <br /> <br /> <br /> 1. Giới thiệu chung* trình bày trong [4]. Trong bài này tác giả sẽ so<br /> sánh một số phương pháp phát hiện biên đang<br /> Phát hiện biên là một công cụ quan trọng được sử dụng phổ biến hiện nay thông qua<br /> trong xử lý ảnh số. Nó làm giảm một cách đáng matlab toolbox và viết chương trình trên<br /> kể khối lượng dữ liệu cần tính toán, chỉ giữ lại MATLAB 7.0 để tiến hành so sánh cả về định<br /> một số ít những thông tin cần thiết đồng thời tính và định lượng. Bố cục của bài báo gồm các<br /> vẫn bảo toàn được những cấu trúc quan trọng phần sau: Trong phần 2 sẽ liệt kê một số dạng<br /> trong bức ảnh. Trong [1] phát hiện biên dùng đường biên cơ bản. Phần 3 trình bày cơ sở lý<br /> mathematical morphology được so sánh với luận của một số phương pháp phát hiện biên<br /> một số phương pháp phát hiện biên. Các tác giả thông dụng. Phần 4 sẽ so sánh hiệu quả của các<br /> trong [2] đã tiến hành so sánh một số phương phương pháp phát hiện biên này và cuối cùng là<br /> pháp phát hiện biên áp dụng cho một số bức phần kết luận.<br /> ảnh có nội dung khác nhau. Độ nhạy của các<br /> phương pháp phát hiện biên đối với tác động<br /> của nhiễu được so sánh trong [3]. Phát hiện 2. Một số kiểu đường biên<br /> biên bằng thông qua việc xử lý các pixels dùng<br /> các ma trận, đạo hàm riêng, convolution được Đường biên là nơi mà các điểm ảnh lân cận<br /> nhau có cường độ thay đổi mạnh một cách đột<br /> _______<br /> * ngột. Một số kiểu đường biên hay gặp trên thực<br /> ĐT.: 84- 913508067<br /> Email: annv@pvu.edu.vn tế được minh họa trên hình 1.<br /> 1<br /> 2 N.V. An / Tạp chí Khoa học ĐHQGHN: Khoa học Tự nhiên và Công nghệ, Tập 31, Số 2 (2015) 1-7<br /> <br /> <br /> <br /> <br /> (a)) (b)<br /> <br /> <br /> <br /> <br /> (c) (d)<br /> <br /> <br /> Hình 1. Một số kiểu đường biên thông dụng<br /> (a) Biên dạng nhảy bậc; (b) Biên dốc; (c) Biên dạng xung vuông; (d) Biên dạng hình nón.<br /> <br /> 3. Các phương pháp phát hiện biên chập (convolution) giữa bức ảnh cần nghiên<br /> cứu f ( x, y ) và một bộ lọc 2D (filter)<br /> Các phương pháp phát hiện biên truyền h( x, y ) thường được gọi là mặt nạ (mask).<br /> thống thường dựa trên kết quả của phép tích<br /> +∞ +∞<br /> h ( x, y ) * f ( x, y ) = ∫ ∫ h(k , k ) f ( x − k , y − k )dk dk<br /> −∞ −∞<br /> 1 2 1 2 1 2     (1)<br /> <br /> <br /> Nếu h(x,y) và f(x,y) có dạng rời rạc thì công thức (1) sẽ được viết lại thành<br /> ∞ ∞<br /> h(n1 , n2 ) * f (n1 , n2 ) = ∑ ∑ h( k , k ) f ( n − k , n<br /> k1 =−∞ k2 =−∞<br /> 1 2 1 1 2 − k2 )     (2)<br /> <br /> <br /> Trên thực tế người ta hay dùng h(n1 , n2 ) là ma trận [ 3 × 3 ] như sau:<br /> ⎛ h(−1,1) h(0,1) h(1,1) ⎞<br /> ⎜ ⎟ (3)<br /> h = ⎜ h(−1, 0) h(0, 0) h(1, 0) ⎟  <br /> ⎜ ⎟<br /> ⎝ h(−1, −1) h(0, −1) h(1, −1) ⎠<br /> <br /> Cấu trúc và giá trị của các toán tử phát hiện nhạy cảm với biên. Có một số toán tử thích hợp<br /> biên sẽ xác định hướng đặc trưng mà toán tử cho các đường biên có hướng nằm ngang, một<br />  N.V. An / Tạp chí Khoa học ĐHQGHN: Khoa học Tự nhiên và Công nghệ, Tập 31, Số 2 (2015) 1-7 3<br /> <br /> <br /> số toán tử lại thích hợp cho việc tìm kiếm biên convolution giữa ảnh và các mặt nạ này ta nhận<br /> dạng thẳng đứng hay theo hướng đường chéo. được các gradient theo chiều đứng và chiều<br /> Có nhiều phương pháp phát hiện biên đang ngang Gx, Gy. Toán tử Sobel có dạng như hình 2.<br /> được áp dụng, tuy nhiên ta có thể phân thành<br /> hai nhóm cơ bản là phát hiện biên dùng<br /> Gradient và phương pháp Laplacian. Phương<br /> pháp phát hiện biên dùng Gradient (sử dụng các<br /> toán tử Roberts, Prewitt, Sobel, Canny) dựa vào<br /> tính giá trị cực đại và cực tiểu của đạo hàm bậc<br /> nhất của ảnh. Phương pháp Laplacian sẽ tìm<br /> kiếm những điểm có giá trị 0 khi lấy đạo hàm Hình 2. Toán tử Sobel.<br /> bậc hai của ảnh (Mars-Hildreth).<br /> 3.1.2. Toán tử Prewitt<br /> 3.1. Phương pháp Gradient<br /> Phương pháp Prewitt gần giống với Sobel.<br /> Đạo hàm bậc nhất theo hướng ngang và dọc Đây là phương pháp lâu đời nhất, cổ điển nhất.<br /> được tính theo (4) Toán tử Prewitt được mô tả trên hình 3<br /> ⎡ ∂f ⎤<br /> ⎡ Gx ⎤ ⎢ ∂x ⎥<br /> Δf = ⎢ ⎥ = ⎢ ⎥ (4)<br /> ⎣G y ⎦ ⎢ ∂f ⎥<br /> ⎢⎣ ∂y ⎥⎦<br /> <br /> Biên độ của gradient vector hay độ lớn tổng<br /> cộng của giá trị đạo hàm nằm tại biên là kết hợp<br /> Hình 3.Toán tử Prewitt.<br /> của cả hai giá trị này theo công thức (5)<br /> Δf = Δf = Gx2 + G y2 (5) 3.1.3. Toán tử Robert<br /> <br /> Hướng của gradient vector được xác định Tương tự như Sobel, ta tính đường biên<br /> theo ngang và dọc một cách riêng rẽ dùng 2 mặt nạ<br /> ⎛ Gy ⎞ như hình 4, sau đó tổng hợp lại để cho đường<br /> angle of ∇f = tan −1 ⎜ ⎟ (6) biên thực của ảnh. Tuy nhiên do mặt nạ của<br /> ⎝ Gx ⎠<br /> Robert khá nhỏ nên kết quả là bị ảnh hưởng khá<br /> Hướng của biên sẽ vuông góc với hướng nhiều của nhiễu.<br /> của gradient vector này.<br /> 3.1.1. Toán tử Sobel<br /> Trên thực tế Sobel sử dụng hai mặt nạ có<br /> kích thước [3 x 3] trong đó một mặt nạ chỉ đơn<br /> giản là sự quay của mặt nạ kia đi một góc 900<br /> như ở hình 2. Các mặt nạ này được thiết kế để<br /> tím ra các đường biên theo chiều đứng và chiều<br /> ngang một cách tốt nhất. Khi thực hiện phép Hình 4. Toán tử Roberts.<br /> 4 N.V. An / Tạp chí Khoa học ĐHQGHN: Khoa học Tự nhiên và Công nghệ, Tập 31, Số 2 (2015) 1-7<br /> <br /> <br /> <br /> 3.1.4. Phương pháp Canny phát hiện càng nhiều (nhưng kèm theo là nhiễu<br /> và số các đường biên giả cũng xuất hiện càng<br /> Phương pháp này sử dụng hai mức ngưỡng<br /> nhiều). Ngược lại nếu ta đặt mức ngưỡng càng<br /> cao và thấp. Ban đầu ta dùng mức ngưỡng cao<br /> cao, ta có thể bị mất những đường biên mờ<br /> để tìm điểm bắt đầu của biên, sau đó chúng ta<br /> hoặc các đường biên sẽ bị đứt đoạn.<br /> xác định hướng phát triển của biên dựa vào các<br /> điểm ảnh liên tiếp có giá trị lớn hơn mức Phương pháp Canny có các ưu điểm sau:<br /> ngưỡng thấp. Ta chỉ loại bỏ các điểm có giá trị • Cực đại hóa tỷ số tín hiệu trên nhiễu làm<br /> nhỏ hơn mức ngưỡng thấp. Các đường biên yếu cho việc phát hiện các biên thực càng chính<br /> sẽ được chọn nếu chúng được liên kết với các xác.<br /> đường biên khỏe. • Đạt được độ chính xác cao của đường<br /> biên thực.<br /> Phương pháp Canny bao gồm các bước sau:<br /> • Làm giảm đến mức tối thiểu số các điểm<br /> Bước 1. Trước hết dùng bộ lọc Gaussian nằm trên đường biên nhằm tạo ra các đường<br /> (3.4) để làm mịn ảnh.<br /> biên mỏng, rõ.<br /> ⎛ x2 ⎞<br /> −⎜<br /> ⎛ x ⎞ ⎜ 2σ 2 ⎟⎟<br /> G ' ( x) = ⎜ − 2 ⎟ e ⎝ ⎠<br /> (7)<br /> ⎝ σ ⎠ 3.2. Laplacian of Gaussian (LOG)<br /> <br /> Bước 2. Sau đó tính toán gradient (8) và (9) Dùng phương pháp gradient sẽ cho kết quả<br /> của đường biên của ảnh đã được làm mịn. là ảnh nhận được có cấu trúc không rõ nét do<br /> ⎛ x2 + y2 ⎞ tạo nên những đường biên dày, không sắc nét.<br /> ⎛ j ⎞ −⎜⎜ 2σ 2 ⎟⎠<br /> ⎟<br /> C x [ x, y ] = − ⎜ 2 ⎟ e ⎝ (8) Để nhận được các đường biên mỏng và rõ nét,<br /> ⎝σ ⎠ ta phải tiến hành các bước xử lý tiếp theo như<br /> loại bỏ những điểm không phải là cực trị (non-<br /> ⎛ x2 + y2 ⎞ maximum suppression) đồng thời áp dụng kỹ<br /> ⎛ i ⎞ −⎜⎜⎝ 2σ 2 ⎟⎠<br /> ⎟<br /> C y [ x, y ] = − ⎜ 2 ⎟e (9) thuật liên kết biên (edge linking). Ngoài ra ta<br /> ⎝σ ⎠ còn gặp phải vấn đề là làm thế nào để xác định<br /> Bước 3. Tiếp theo là loại bỏ những điểm được mức ngướng một cách chính xác. Việc<br /> không phải là cực đại. chọn đúng giá trị ngưỡng phụ thuộc rất nhiều<br /> Bước 4. Bước cuối cùng là loại bỏ những vào nội dung của từng bức ảnh. Nếu ta tăng gấp<br /> giá trị nhỏ hơn mức ngưỡng. đôi kích thước của một bức ảnh mà không thay<br /> đổi giá trị cường độ của các điểm ảnh, ta sẽ<br /> Phương pháp này hơn hẳn các phương pháp<br /> nhận được gradients bị suy giảm đi một nửa.<br /> khác do ít bị tác động của nhiễu và cho khả Mặt khác kích thước của mặt nạ (masks) cũng<br /> năng phát hiện các biên yếu. Nhược điểm của ảnh hưởng nhiều đến giá trị của gradients trong<br /> phương pháp này là nếu chọn ngưỡng quá thấp ảnh.<br /> sẽ tạo ra biên không đúng, ngược lại nếu chọn<br /> Phương pháp gradient chỉ thích hợp cho các<br /> ngưỡng quá cao thì nhiều thông tin quan trọng<br /> vùng ảnh độ tương phản thay đổi có tính nhảy<br /> của biên sẽ bị loại bỏ. Căn cứ vào mức ngưỡng<br /> bậc, điều này gây khó khăn cho phát hiện các<br /> đã xác định trước, ta sẽ quyết định những điểm<br /> đường thẳng. Để khắc phục nhược điểm này ta<br /> thuộc biên thực hoặc không thuộc biên. Nếu<br /> thường dùng đạo hàm bậc hai. Phương pháp<br /> mức ngưỡng càng thấp, số đường biên được<br /> Laplacian cho phép xác định đường biên dựa<br />  N.V. An / Tạp chí Khoa học ĐHQGHN: Khoa học Tự nhiên và Công nghệ, Tập 31, Số 2 (2015) 1-7 5<br /> <br /> <br /> vào giá trị 0 của đạo hàm bậc hai của ảnh. 4. Kết quả thực nghiệm<br /> Laplacian của một ảnh tại điểm I(x,y) được tính<br /> theo (10): Ta tiến hành so sánh hiệu quả phát hiện<br /> biên khi áp dụng các toán tử nêu trên dùng<br /> ∂2I ∂2 I<br /> L ( x, y ) = + (10) MATLAB. Chất lượng phát hiện biên được<br /> ∂x 2 ∂y 2<br /> đánh giá thông qua các tiêu chí như sai số trung<br /> Laplacian được kết hợp với bộ lọc làm mịn bình bình phương (MSE) và tỷ số tín hiệu/nhiễu<br /> ảnh để tìm biên [5]. Xét công thức sau: (PSNR).<br /> r2<br /> −<br /> h( r ) = −e 2σ 2<br /> (11) a) Sai số trung bình bình phương MSE đánh<br /> giá mức độ sai khác giữa biên nhận được do<br /> Ở đây r 2 = x 2 + y 2 và ơ là độ lệch chuẩn tính toán và biên thực thông qua công thức:<br /> (standard deviation). Nếu thực hiện phép tích 1 M N<br /> <br /> ∑∑ ( f (i, j ) − f (i , j ) )<br /> 2<br /> chập của hàm này với ảnh cần tìm biên, kết quả MSE = 1 2 và<br /> MN i =1 j =1<br /> là ảnh sẽ bị mờ đi, mức độ mờ phụ thuộc vào<br /> giá trị của ơ. Laplacian của h tức đạo hàm bậc RMSE = MSE (13)<br /> hai của h theo r là: Với f1 (i, j ) và f 2 (i, j ) là các điểm ảnh trên<br /> ⎡ r 2 − σ 2 ⎤ − 2rσ22 biên theo tính toán và trên biên thực.<br /> ∇2h( r ) = − ⎢ ⎥e (12)<br /> ⎣ σ<br /> 4<br /> ⎦ b) Tỷ số tín hiệu/nhiễu được tính theo công<br /> thức<br /> Hàm này thường được gọi là Laplacian of a<br /> Gaussian (LoG) do (11) có dạng Gaussian. PSNR = 10log ( 2552 / MSE ) (14)<br /> Trong phương pháp này, bộ lọc Gaussian<br /> được kết hợp với Laplacian cho phép hiển thị a. Kết quả tính toán đối với 2 bức ảnh<br /> “moon.jpg” và “Lena.jpg” được cho trong bảng<br /> những vùng ảnh có cường độ thay đổi nhanh do<br /> 1 và bảng 2.<br /> đó làm tăng hiệu quả phát hiện biên. Nó cho<br /> phép làm việc với một diện tích rộng hơn xung Bảng 1. So sánh MSE và PSNR của ảnh mặt trăng<br /> quanh điểm ảnh đang được nghiên cứu nhằm (moon.jpg)<br /> phát hiện chính xác hơn vị trí của đường biên.<br /> STT Phương pháp MSE PSNR<br /> Nhược điểm của phương pháp này là không xác 1 Sobel 9.9033e+003 8.1730<br /> định được hướng của biên do sử dụng hai bộ 2 Prewitt 9.9035e+003 8.1729<br /> lọc Laplacian quá khác nhau có dạng như trên 3 Canny 9.8804e+003 8.1830<br /> 4 LoG 9.8881e+003 8.1797<br /> hình 5.<br /> Bảng 2. So sánh MSE và PSNR của ảnh cô gái Lena<br /> (Lena.jpg)<br /> <br /> STT Phương pháp MSE PSNR<br /> 1 Sobel 1.1028e+004 7.7058<br /> 2 Prewitt 1.1028e+004 7.7058<br /> 3 Canny 1.1017e+004 7.7103<br /> 4 LoG 1.1022e+004 7.7081<br /> Hình 5. Toán tử Laplacian.<br /> 6 N.V. An / Tạp chí Khoa học ĐHQGHN: Khoa học Tự nhiên và Công nghệ, Tập 31, Số 2 (2015) 1-7<br /> <br /> <br /> <br /> Qua số liệu ở bảng 1 và bảng 2 thấy phương phương pháp Canny cho phép hiện đầy đủ hơn<br /> pháp Canny cho kết quả MSE có giá trị nhỏ các biên có thể có trên các bức ảnh. Phương<br /> nhất và PSNR cho giá trị lớn nhất so với các pháp LoG cho ta thấy rõ hơn các đường thảng<br /> phương pháp khác. Hình 5 và hình 6 cho ta kết thuộc biên, đồng thời chỉ số MSE và PSNR<br /> quả khi áp dụng các toán tử nêu trên cho hai cũng đạt được tương đối tốt.<br /> bức ảnh có nội dung khác nhau. Ta thấy rằng<br /> <br /> <br /> <br /> <br /> Original Prewitt Sobel<br /> <br /> <br /> <br /> <br /> Canny LoG<br /> <br /> Hình 5. Kết quả phát hiện biên sử dụng các toán tử Prewitt, Sobel, Canny và LoG cho ảnh “moon.jpg”<br /> <br /> <br /> <br /> <br /> Original Prewitt Sobel<br /> <br /> <br /> <br /> <br /> Canny LoG<br /> Hình 6. Kết quả phát hiện biên sử dụng các toán tử Prewitt, Sobel, Canny và LoG cho ảnh “Lena.jpg”.<br />  N.V. An / Tạp chí Khoa học ĐHQGHN: Khoa học Tự nhiên và Công nghệ, Tập 31, Số 2 (2015) 1-7 7<br /> <br /> <br /> 5. Kết luận Tài liệu tham khảo<br /> <br /> Bài báo đã phân tích và so sánh một số [1] Beant Kaur, Anil Garg, Comparative study of<br /> different edge detection techniques, International<br /> phương pháp phát hiện biên dùng Gradients và journal of Engineering Science and Technology<br /> phương pháp Laplacian. Mỗi phương pháp đều (IJEST), vol. 3, No. 3 March 2011.<br /> có những ưu điểm nhất định. Tuy nhiên, tùy [2] Raman Maini and Dr. Himanshu Aggarwai, Study<br /> thuộc vào tính chất phức tạp của nội dung trong and Comparison of various Image Edge Detection<br /> Techniques, International journal of Image<br /> từng bức ảnh, các phương pháp đều có những<br /> Processing, Volume 3, Issue 1.<br /> nhược điểm khó khắc phục. Phương pháp [3] Bindu Bansal, Jasbir Singh Saini, Vipan Bansal<br /> Canny cho độ méo MSE nhỏ nhất do sử dụng and Gurjit Kaur, “Comparison of various edge<br /> bộ lọc Gaussian và tỷ số PSNR tốt nhất do sử detection techniques”, Journal of Information and<br /> dụng nhiều mức ngưỡng. Dùng Laplacian cho Operations Management, Vol 3, Issue 1, 2012, pp.<br /> 103-106.<br /> kết quả khá tốt trong trường hợp các đường [4] John Schmeelk, AC2011-279: “Edge Detectors in<br /> biên thẳng. Tuy nhiên chưa có phương pháp Image Processing”, American Society for<br /> nào thỏa mãn tốt được các tiêu chí về độ chống Engineering Education Annual Conference and<br /> nhiễu, phát hiện chính xác vị trí các đường biên Exposition, 26-29 June 2011, Vancouver, BC,<br /> Canada,<br /> thực, không tạo ra những ảnh quá phức tạp mà<br /> [5] Rafael C. Gonzalez and Richard E. Woods,<br /> vẫn thể hiện đầy đủ các đặc điểm quan trọng “Digital Image Processing”, 2nd edition, Prentice-<br /> của ảnh. Do đó việc tìm kiếm một phương pháp Hall,Inc, 2002.<br /> mới phải được tiếp tục nghiên cứu.<br /> <br /> <br /> Comparison of Edge Detection Techniques<br /> <br /> Nguyễn Vĩnh An<br /> Ministry of Information and Communications, 18 Nguyễn Du, Hanoi, Vietnam<br /> <br /> <br /> Abstract: Image Edge detection is very important in image processing since computer vision<br /> involves the identification and classification of objects in an image. Image Edge detection reduces<br /> significantly the amount of data and filters out the useless information while preserving all important<br /> structural properties of an image. There are many edge detection techniques available, each of them is<br /> designed to be sensitive to a certain type of edges. This paper compares several popular techniques for<br /> edge detection in image processing using MATLAB.<br /> Keywords: Canny, Laplacian of Gaussian (LOG), Sobel, Prewitt, Robert.<br />