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

Nội dung text: So sánh một số phương pháp phát hiện biên

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