Đồ án Phân đoạn ảnh dựa trên phương pháp phát hiện biên - Đinh Văn Vạn

Nội dung text: Đồ án Phân đoạn ảnh dựa trên phương pháp phát hiện biên - Đinh Văn Vạn

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG o0o ĐỒ ÁN TỐT NGHIỆP Ngành công nghệ thông tin HẢI PHÒNG - 2012
2. 1 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG o0o PHÂN ĐOẠN ẢNH DỰA TRÊN PHƢƠNG PHÁP PHÁT HIỆN BIÊN ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ Thông tin HẢI PHÒNG - 2012
3. 2 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG o0o PHÂN ĐOẠN ẢNH DỰA TRÊN PHƢƠNG PHÁP PHÁT HIỆN BIÊN ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ Thông tin Sinh viên thực hiện: Đinh Văn Vạn Giáo viên hƣớng dẫn: PGS. TS. Ngô Quốc Tạo Mã số sinh viên: 111136 HẢI PHÒNG - 2012
4. 3 BỘ GIÁO DỤC VÀ ĐÀO TẠO CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG Độc lập – Tự do – Hạnh phúc o0o NHIỆM VỤ THIẾT KẾ TỐT NGHIỆP Lớp: CT1201 Sinh viên:Đinh Văn Vạn Ngành: Công nghệ Thông tin Mã số: 111136 Tên đề tài: Phân đoạn ảnh dựa trên phƣơng pháp phát hiện biên
5. 4 NHIỆM VỤ ĐỀ TÀI 1. Nội dung và các yêu cầu cần giải quyết trong nhiệm vụ đề tài tốt nghiệp a. Nội dung: Tìm hiểu về phân đoạn ảnh và các phƣơng pháp phát hiện biên. b. Các yêu cầu cần giải quyết: - Tìm hiểu một số các khai niệm cơ bản về xử lý ảnh - Tìm hiểu về phân đoạn ảnh - Tìm hiểu các phƣơng pháp phát hiện biên, các toán tử tách cạnh Sobel,prewitt, Kiresh, Laplace, Canny, Roberts 2. Các số liệu cần thiết để thiết kế, tính toán 3. Địa điểm thực tập
6. 5 CÁN BỘ HƢỚNG DẪN ĐỀ TÀI TỐT NGHIỆP Ngƣời hƣớng dẫn thứ nhất: Họ và tên: Ngô Quốc Tạo Học hàm, học vị: Phó giáo sƣ, Tiến sĩ Cơ quan công tác: Viện Công nghệ thông tin, Viện Khoa học và Công nghệ Việt Nam. Nội dung hƣớng dẫn: Phân đoạn ảnh dựa trên phƣơng pháp phát hiện biên Ngƣời hƣớng dẫn thứ hai: Họ và tên: Học hàm, học vị: Cơ quan công tác: Nội dung hƣớng dẫn: Đề tài tốt nghiệp đƣợc giao ngày 27 tháng 08 năm 2012 Yêu cầu phải hoàn thành trƣớc ngày 2 tháng 12 năm 2012 Đã nhận nhiệm vụ: Đ.T.T.N Đã nhận nhiệm vụ: Đ.T.T.N Sinh viên Cán bộ hƣớng dẫn Đ.T.T.N Hải phòng, ngày .tháng .năm 2012 HIỆU TRƢỞNG GS.TS.NGƢT Trần Hữu Nghị
7. 6 PHẦN NHẬN XÉT TÓM TẮT CỦA CÁN BỘ HƢỚNG DẪN 1. Tinh thần thái độ của sinh viên trong quá trình làm đề tài tốt nghiệp: . . . . 2. Đánh giá chất lƣợng của đề tài tốt nghiệp (so với nội dung yêu cầu đã đề ra trong nhiệm vụ đề tài tốt nghiệp) . . . . 3. Cho điểm của cán bộ hƣớng dẫn: (Điểm ghi bằng số và chữ) . Ngày tháng năm 2012 Cán bộ hƣớng dẫn chính (Ký, ghi rõ họ tên)
8. 7 PHẦN NHẬN XÉT ĐÁNH GIÁ CỦA CÁN BỘ CHẤM PHẢN BIỆN ĐỀ TÀI TỐT NGHIỆP 1. Đánh giá chất lƣợng đề tài tốt nghiệp (về các mặt nhƣ cơ sở lý luận, thuyết minh chƣơng trình, giá trị thực tế, ) . . . . . . 2. Cho điểm của cán bộ phản biện (Điểm ghi bằng số và chữ) . Ngày .tháng .năm 2012 Cán bộ chấm phản biện (Ký, ghi rõ họ tên)
9. Mục lục Mục lục 0 DANH MỤC HÌNH ẢNH 0 LỜI CÁM ƠN 1 MỞ ĐẦU 2 Chƣơng 1. GIỚI THIỆU 3 1.1 Tổng quan về xử lý ảnh 3 1.1.1 Giới thiệu về xử lý ảnh 3 1.1.2 Các bƣớc cơ bản của xử lý ảnh 4 1.1.2.1 Thu nhận ảnh 4 1.1.2.2 Tiền xử lý 4 1.1.2.3 Phân đoạn ảnh 5 1.1.2.4 Biểu diễn và mô tả 5 1.1.2.5 Nhận dạng và nội suy ảnh 6 1.2 Các khái niệm cơ bản về xử lý ảnh 6 1.2.1 Điểm ảnh 6 1.2.2 Mức xám 6 1.2.3 Biên 7 1.2.4 Láng giềng 7 1.2.5 Vùng liên thông 7 Chƣơng 2 PHÂN ĐOẠN ẢNH VÀ BIÊN 8 2.1 Tổng quan về phân đoạn ảnh 8 2.2 Tổng quan về biên 9 2.2.1 Biên và các kiểu biên cơ bản 9 2.2.1.1 Biên lý tƣởng 9
10. 2.2.1.2 Biên dốc 10 2.2.1.3 Biên không trơn 11 2.2.2 Vai trò của biên trong nhận dạng 12 Chƣơng 3. MỘT SỐ KĨ THUẬT PHÂN ĐOẠN ẢNH 14 3.1 Phân đoạn ảnh dựa vào ngƣỡng 14 3.1.1 Giới thiệu 14 3.1.2 chọn ngƣỡng cố định 15 3.1.3 Chọn ngƣỡng trên lƣợc đồ(Histogram) 15 3.1.3.1 Thuật toán đẳng liệu 15 3.1.3.2 Thuật toán đối xứng nền 16 3.1.3.3 Thuật toán tam giác 17 3.1.3.4 Chọn ngƣỡng đối với Bimodal Histogram 18 3.2 Phân đoạn theo miền đồng nhất 19 3.3.1 Giới thiệu 19 3.3.2 Phƣơng pháp tách cây tứ phân 19 3.3.3 Phƣơng pháp phân vùng bởi hợp 23 3.3.4 phƣơng pháp tổng hợp. 24 Chƣơng 4 MỘT SỐ PHƢƠNG PHÁP PHÁT HIỆN BIÊN 26 4.1 Phân loại các kĩ thuật phát hiện biên 26 4.1.1 Phƣơng pháp phát hiện biên trực tiếp 26 4.1.2 Phƣơng pháp phát hiện biên gián tiếp 26 4.1.3 Quy trình phát hiện biên 27 4.2. Kỹ thuật phát hiện biên Gradient 27 4.2.1 Toán tử Sobel 28 4.2.2 Toán tử Prewitt 30
11. 4.3 Các toán tử la bàn 31 4.3.1 Toán tử Kirsh 31 4.3.2 Toán tử la bàn Prewitt 33 4.4 Kĩ thuật phát hiện biên Laplace 34 4.5 Phƣơng pháp phát hiện biên Canny 36 4.5.1 Cơ sở lý thuyết thuật toán 36 4.5.2 Hoạt động của thuật toán 38 4.6 Toán tử Robert(1965) 43 Kết luận Error! Bookmark not defined. TÀI LIỆU THAM KHẢO 46
12. DANH MỤC HÌNH ẢNH Hình 1.1. Quá trình xử lý ảnh 3 Hình 1.2 Các bƣớc cơ bản trong qua trình xử lý ảnh 4 Hình 2.1.Đƣờng biên lý tƣởng 10 Hình 2.2.Đƣờng biên dốc 11 Hình 2.3. đƣờng biên không trơn 12 Hình 3.1. Minh họa thuật toán đối xứng nền 16 Hình 3.2. Minh họa thuật toán tam giác 17 Hình 3.3. Thuật toán đối xứng nền 18 Hình 3.4. phƣơng pháp cây tứ phân 23 Hình 4.1. Biên ảnh với sobel 30 Hình 4.2 Biên ảnh với toán tử Prewitt 31 Hình 4.3. Kết quả với toán tử Kirsh 33 Hình 4.4. Biên ảnh với toán tử la bàn Prewitt 34 Hình 4.5. Biên ảnh với kỹ thuật Laplace 36 Hình 4.6. Đạo hàm hàm Gauss theo hai hƣớng (x,y) 40 Hình 4.7. Hình mô tả các điểm biên lân cận 41 Hình 4.8. Biên ảnh theo phƣơng pháp Canny 43 Hình 4.9. Biên ảnh với toán tử Robert 44
13. 1 LỜI CÁM ƠN Trƣớc hết em xin chân thành cảm ơn các thầy cô giáo trong khoa công nghệ thông tin trƣờng đại học dân lập Hải Phòng đã trang bị những cơ bản cần thiết và quý để em thực hiện đề tài của mình. Đặc biệt tôi xin gửi lời cảm ơn sâu sắc đến thầy giáo hƣớng dẫn PGS.TS Ngô Quốc Tạo về những chỉ dẫn khoa học và tận tình hƣớng dẫn, tạo mọi điều kiện thuận lợi giúp đỡ cho em trong suốt quá trình làm đồ án. Tôi cũng xin cảm ơn những ngƣời bạn của mình, các bạn đã luôn ở bên tôi, giúp đỡ và cho tôi những ý kiến đóng góp quý báu trong học tập cũng nhƣ trong cuộc sống. Sinh viên Đinh Văn Vạn
14. 2 MỞ ĐẦU Trong thời đại hiện nay, công nghệ thông tin có sự phát triển mạnh mẽ về mọi mặt. Cũng chính nhờ sự phát triển này đã góp phần rất lớn trong việc thúc đẩy sự phát triển của các ngành khác nhƣ: giáo dục, y tế, quốc phòng an ninh, giải trí, Những năm gần đây, phần cứng máy tính đã dần trở nên mạnh mẽ cả về năng lực xử lý lẫn dung lƣợng lƣu trữ vì thế mà các lĩnh vực phần mềm cũng đƣợc phát triển theo đặc biệt là lĩnh vực xử lý ảnh. Phân đoạn ảnh để nhận biết đƣợc các thành phần trong ảnh nhằm hiểu đƣợc kết cấu của bức ảnh ở mức độ cao hơn. Để xử lý đƣợc một bức ảnh thì phải trải qua rất nhiều bƣớc nhƣng quan trọng và khó khăn nhất là phân đoạn ảnh. Nếu bƣớc phân đoạn ảnh không tốt thì dẫn đến việc nhận diện sai lầm về các đối tƣợng có trong ảnh. Phân đoạn ảnh có nhiều các tiếp cận, một trong những cách tiếp cận đó là phát hiện biên ảnh trƣớc.
15. 3 Chƣơng 1. GIỚI THIỆU 1.1 Tổng quan về xử lý ảnh 1.1.1 Giới thiệu về xử lý ảnh Con ngƣời thu nhận thông tin qua các giác quan trong đó thị giác đóng vai trò quan trọng nhất. Sự phát triển nhanh của phần cứng máy tính, xử lý ảnh và đồ hoạ đã phát triển mạnh mẽ và ngày càng có nhiều ứng dụng trong cuộc sống. Xử lý ảnh đóng một vai trò quan trọng trong tƣơng tác ngƣời máy. Quá trình xử lý nhận dạng ảnh là một quá trình thao tác nhằm biến đổi một ảnh đầu vào để cho ra một kết quả mong muốn. Kết quả đầu ra của một quá trình xử lý ảnh có thể là một ảnh "tốt hơn" hoặc một kết luận. Ảnh kết quả Ảnh ban đầu Xử lý ảnh Kết luận Hình 1.1. Quá trình xử lý ảnh Nhƣ vậy mục đích của việc xử lý ảnh đƣợc chia ra làm hai phần: Biến đổi, xử lý ảnh ban đầu để cho ra một ảnh mới tốt hơn một mong muốn của ngƣời dùng. Phân tích ảnh để thu đƣợc thông tin nào đó giúp cho việc phân loại và nhận biết ảnh, từ ảnh đầu vào mà có những nhận xét, kết luận ở mức cao hơn, sâu hơn .
16. 4 1.1.2 Các bƣớc cơ bản của xử lý ảnh Quá trình xử lý một ảnh đầu vào nhằm thu đƣợc một ảnh mong muốn ở đầu ra phải trải qua nhiều bƣớc khác nhau. Thông thƣờng các bƣớc cơ bản xử lý ảnh đƣợc thể hiện thông qua “Hình 1.2” Phân đoạn ảnh Biểu diễn và mô tả Tiền xử lý CƠ SỞ Nhận dạng và TRI nội suy Thu nhận ảnh THỨ C Hình 1.2 Các bƣớc cơ bản trong qua trình xử lý ảnh 1.1.2.1 Thu nhận ảnh Đây là bƣớc đầu tiên trông quá trình xử lý ảnh, ảnh đƣợc thu từ các thiết bị nhƣ máy ảnh, máy quét. 1.1.2.2 Tiền xử lý Ở đây ảnh đƣợc cải thiện về độ tƣơng phản, khử nhiễu, khôi phục ảnh, nắn chỉnh hình học Với mục đích làm cho chất lƣợng ảnh trở lên tốt hơn, chuẩn bị cho các bƣớc xử lý phức tạp tiếp sau đó.
17. 5 1.1.2.3 Phân đoạn ảnh Phân đoạn ảnh có nghĩa là chia một ảnh đầu vào thành nhiều phần khác nhau hay còn gọi là các đối tƣợng để biểu diễn phân tích nhận dạng ảnh. Ví dụ để nhận dạng chữ (hay mã vạch) trên phong bì thƣ để phân loại bƣu phẩm, cần chia các câu, chữ về địa chỉ hoặc teen ngƣời thành các từ, các chữ, các số (hoặc các vạch) riêng biệt để nhận dạng. đây là phần phức tạp, khó khăn nhất trong xử lý ảnh và cũng dễ dây lỗi, làm mất độ chính xác của ảnh. Kết quả nhận dạng phụ thuộc rất nhiều vào công đoạn này. Kết quả của bƣớc phân đoạn ảnh thƣờng đƣợc cho dƣới dạng dữ liệu điểm ảnh thô, trong đó hàm chứa biên của một vùng ảnh hoặc tập hợp tất cả các điểm ảnh thuộc về chính vùng ảnh đó. Trong cả hai trƣờng hợp, sự chuyển đổi dữ liệu thô này thành một dạng thích hợp hơn cho việc xử lý trong máy tính là hết sức cần thiết, nghĩa là nên biểu diễn một vùng ảnh dƣới dạng biên hay dƣới dạng một vùng hoàn chỉnh gồm tất cả những điểm ảnh thuộc về nó. Biểu diễn dạng biên cho một vùng phù hợp với những ứng dụng chỉ quan tâm đến các đặc trƣng hình dạng bên ngoài của đối tƣợng, ví dụ nhƣ các góc cạnh và điểm uốn trên biên. Biểu diễn dạng vùng lại thích hợp cho những ứng dụng khai thác các tính chất bên trong của đối tƣợng. Ví dụ nhƣ vân ảnh hoặc cấu trúc xƣơng của nó. Và trong một số ứng dụng thì cả hai cách biểu diễn trên đều cần thiết. 1.1.2.4 Biểu diễn và mô tả a) Biểu diễn Đầu ra ảnh sau phân đoạn chứa các điểm ảnh của vùng ảnh (ảnh đã phân đoạn) cộng với mã liên kết với các vùng lận cận. Việc biến đổi các số liệu này thành dạng thích hợp là cần thiết cho xử lý tiếp theo bằng máy tính. Việc chọn các tính chất để thể hiện ảnh gọi là trích chọn đặc trƣng (Feature Selection) gắn với việc tách các đặc tính của ảnh dƣới dạng các thông tin định lƣợng hoặc làm cơ sở để phân biệt lớp đối tƣợng này với đối tƣợng khác trong phạm vi ảnh nhận đƣợc. Ví dụ: trong nhận dạng ký tự trên phong bì thƣ, chúng ta miêu tả các đặc trƣng của từng ký tự giúp phân biệt ký tự này với ký tự khác.
18. 6 b) Mô tả Ảnh sau khi số hoá sẽ đƣợc lƣu vào bộ nhớ, hoặc chuyển sang các khâu tiếp theo để phân tích. Nếu lƣu trữ ảnh trực tiếp từ các ảnh thô, đòi hỏi dung lƣợng bộ nhớ cực lớn và không hiệu quả theo quan điểm ứng dụng và công nghệ. Thông thƣờng, các ảnh thô đó đƣợc đặc tả (biểu diễn) lại (hay đơn giản là mã hoá) theo các đặc điểm của ảnh đƣợc gọi là các đặc trƣng ảnh nhƣ: biên ảnh, vùng ảnh. 1.1.2.5 Nhận dạng và nội suy ảnh Nhận dạng ảnh là quá trình xác định ảnh. Quá trình này thƣờng thu đƣợc bằng cách so sánh với mẫu chuẩn đã đƣợc lọc (hoặc lƣu) từ trƣớc. Nội suy là phán đoán theo ý nghĩa trên cơ sở nhận dạng. Ví dụ: một loạt chữ số và nét gạch ngang trên phong bì thƣ có thể đƣợc nội suy thành mã điện thoại. Có nhiều cách phân loại khác nhau về ảnh. Theo lý thuyết về nhận dạng, các mô hình toán học về ảnh đƣợc phân theo hai loại nhận dạng ảnh cơ bản: - Nhận dạng theo tham số. - Nhận dạng theo cấu trúc. 1.2 Các khái niệm cơ bản về xử lý ảnh 1.2.1 Điểm ảnh Ảnh trong thực tế là một ảnh liên tục về không gian và về giá trị độ sáng. Đểcó thể XLA bằng máy tính cần phải tiến hành số hoá ảnh. Trong quá trình số hoá,ngƣời ta biến đổi tín hiệu liên tục sang tín hiệu rời rạc thông qua quá trình lấy mẫu (rời rạc hoá về không gian) và lƣợng hoá thành phần giá trị mà về nguyên tắc bằng mắt thƣờng không phân biệt đƣợc hai điểm kề nhau. Trong quá trình này ngƣời ta sử dụng khái niệm Picture element mà ta quen gọi là Pixel - phần tử ảnh. Nhƣ vậy,một ảnh là một tập hợp các Pixel 1.2.2 Mức xám Mức xám là kết quả sự mã hoá tƣơng ứng một cƣờng độ sáng của mỗi điểm ảnh với một giá trị số - kết quả của quá trình lƣợng hoá. Cách mã hoá kinh
19. 7 điển thƣờng dùng 16, 32 hay 64 mức. Phổ dụng nhất là mã hoá ở mức 256, ở mức nàymỗi Pixel sẽ đƣợc mã hoá bởi 8 bit. 1.2.3 Biên Biên là một đặc tính rất quan trọng của đối tƣợng trong ảnh, nhờ vào biên mà chúng ta phân biệt đƣợc đối tƣợng này với đối tƣợng kia. Một điểm ảnh có thể gọi 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 còn gọi là đƣờng bao ảnh. 1.2.4 Láng giềng Trong XLA có một khái niệm rất quan trọng, đó là khái niệm láng giềng. Cóhai loại láng giềng: 4-láng giềng và 8-láng giềng 4-láng giềng của một điểm (x,y) là một tập hợp bao gồm láng giềng dọc và láng giềng ngang của nó: N4((x,y)) = {(x+1,y), (x-1,y), (x,y+1), (x,y-1)} (1.1) 8-láng giềng của (x,y) là một tập cha của 4-láng giềng và bao gồm láng giềng ngang, dọc và chéo: N8((x,y)) = N4((x,y))∪{(x+1,y+1),(x-1,y-1), (x+1,y-1),(x-1,y+1)} (1.2) 1.2.5 Vùng liên thông Một vùng R đƣợc gọi là liên thông nếu bất kỳ hai điểm (xA,yA) và (xB,yB) thuộc vào R có thể đƣợc nối bởi một đƣờng (xA,yA) (xi-1,yi-1), (xi,yi), (xi+1,yi+1) (xB,yB), mà các điểm (xi,yi) thuộc vào R và bất kỳ điểm (xi,yi) nào đều kề sát với điểm trƣớc (xi-1,yi-1) và điểm tiếp theo (xi+1,yi+1) trên đƣờng đó. Một điểm (xk,yk) đƣợc gọi là kề với điểm (xl,yl) nếu (xl,yl) thuộc vào láng giềng trực tiếp của (xk,yk).
20. 8 Chƣơng 2 PHÂN ĐOẠN ẢNH VÀ BIÊN 2.1 Tổng quan về phân đoạn ảnh Để phân tích các đối tƣợng trong ảnh, chúng ta cần phải phân biệt đƣợc các đối tƣợng cần quan tâm với phần còn lại của ảnh, hay còn gọi là nền ảnh. Những đối tƣợng này có thể tìm ra đƣợc nhờ các kỹ thuật phân đoạn ảnh, theo nghĩa tách phần tiền cảnh ra khỏi hậu cảnh trong ảnh. Mỗi một đối tƣợng trong ảnh đƣợc gọi là một vùng hay miền, đƣờng bao quanh đối tƣợng ta gọi là đƣờng biên. Mỗi một vùng ảnh phải có các đặc tính đồng nhất (ví dụ: màu sắc, kết cấu, mức xám vv ). Các đặc tính này tạo nên một véc tơ đặc trƣng riêng của vùng (feature vectors) giúp chúng ta phân biệt đƣợc các vùng khác nhau. Nhƣ vậy, hình dáng của một đối tƣợng có thể đƣợc miêu tả hoặc bởi các tham số của đƣờng biên hoặc các tham số của vùng mà nó chiếm giữ. Sự miêu tả hình dáng dựa trên thông tin đƣờng biên yêu cầu việc phát hiện biên. Sự mô tả hình dáng dựa vào vùng đòi hỏi việc phân đoạn ảnh thành một số vùng đồng nhất. Có thể thấy kỹ thuật phát hiện biên và phân vùng ảnh là hai bài toá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ũng có nghĩa là đã phân vùng đƣợc ảnh. Ngƣợc lại, khi đã phân vùng, ảnh đƣợc phân lập thành các đối tƣợng, ta có thể phát hiện biên. Có rất nhiều kỹ thuật phân đoạn ảnh, nhƣng nhìn chung chúng ta có thể chia thành ba lớp khác nhau: Các kỹ thuật cục bộ (Local techniques) dựa vào các thuộc tính cục bộ của các điểm và láng giềng của nó. Các kỹ thuật toàn thể (global techniques) phân ảnh dựa trên thông tin chung của toàn bộ ảnh (ví dụ bằng cách sử dụng lƣợc đồ xám của ảnh –image histogram). Các kỹ thuật tách (split), hợp (merge) và growing sử dụng các khái niệm đồng nhất và gần về hình học.
21. 9 2.2 Tổng quan về biên 2.2.1 Biên và các kiểu biên cơ bản Các đặc trƣng của ảnh thƣờng bao gồm các thành phần nhƣ: mật độ xám, phân bố xác suất, phân bố không gian, biên ảnh. Biên là một vấn đề chủ yếu và đặc biệt quan trọng 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. Hiện nay có nhiều định nghĩa về biên ảnh và mỗi định nghĩa đƣợc sử dụng trong một số trƣờng hợp nhất định. Song nhìn chung, ta có thể hiểu là: Một điểm ảnh có thể coi là biên nếu ở đó có sự thay đổi đột ngột về mức xám. 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 có ít nhất một điểm trắng bên cạnh. Tập hợp các điểm biên tạo thành biên, hay còn gọi là đƣờng bao của ảnh (boundary). Chẳng hạn, trong một ảnh nhị phân, một điểm có thể đƣợc gọi là biên nếu đây là một điểm đen và có ít nhất một điểm trắng nằm trong lân cận điểm đó. Mỗi một biên là một thuộc tính gắn liền với một điểm riêng biệt và đƣợc tính toán từ những điểm lân cận nó. Đó là một biến Vector bao gồm hai thành phần: - Độ lớn của Gadient. - Hƣớng φ đƣợc quay đối với hƣớng Gradient . 2.2.1.1 Biên lý tƣởng Việc phát hiện biên một cách lý tƣởng là việc xác định đƣợc tất cả các đƣờng bao trong đối tƣợng. Biên là sự thay đổi đột ngột về mức xám nên sự thay đổi cấp xám giữa các vùng trong ảnh càng lớn thì càng dễ dàng nhận ra biên. Hình minh hoạ điểm ảnh có sự biến đổi mức xám u(x) một cách đột ngột:
22. 10 Hình 2.1.Đƣờng biên lý tƣởng Một biên đƣợc coi đó là biên lý tƣởng khi mà có sự thay đổi cấp xám lớn giữa các vùng trong ảnh. Biên này thƣờng chỉ xuất hiện khi có sự thay đổi cấp xám qua một điểm ảnh. 2.2.1.2 Biên dốc Biên dốc xuất hiện khi sự thay đổi cấp xám trải rộng qua nhiều điểm ảnh. Vị trí của cạnh đƣợc xem nhƣ vị trí chính giữa của đƣờng dốc nối giữa cấp xám thấp và cấp xám cao. Tuy nhiên đây chỉ là đƣờng dốc trong toán học, từ khi ảnh đƣợc kỹ thuật số hoá thì đƣờng dốc không còn là đƣờng thẳng mà thành những đƣờng lởm chởm, không trơn.
23. 11 Hình 2.2.Đƣờng biên dốc 2.2.1.3 Biên không trơn Trên thực tế, ảnh thƣờng có biên không lý tƣởng, các điểm ảnh trên ảnh thƣờng có sự thay đổi mức xám đột ngột và không đồng nhất, đặc biệt là ảnh nhiễu. Trong trƣờng hợp không nhiễu (biên lý tƣởng), bất cứ một sự thay đổi cấp xám nào cũng thông báo sự tồn tại của một biên. Trƣờng hợp đó khó có khả năng xảy ra, ảnh thƣờng là không lý tƣởng, có thể là do các nguyên nhân sau: - Hình dạng không sắc nét. - Nhiễu: do một loạt các yếu tố nhƣ: kiểu thiết bị nhập ảnh, cƣờng độ ánh sáng, nhiệt độ, hiệu ứng áp suất, chuyển động, bụi , chƣa chắc rằng hai điểm ảnh có cùng giá trị cấp xám khi đƣợc nhập lại có cùng cấp xám đó trong ảnh. Kết quả của nhiễu trên ảnh gây ra một sự biến thiên ngẫu nhiên giữa các điểm ảnh. Sự xuất hiện ngẫu nhiên của các điểm ảnh có mức xám chênh lệch cao làm cho các đƣờng biên dốc trở lên không trơn chu mà trở thành các đƣờng biên gồ ghề, mấp mô, không nhẵn, đây chính là đƣờng biên trên thực tế. Ngày nay, những phƣơng pháp phát hiện biên hiện đại thƣờng kết hợp nhiễu vào trong mô hình của bài toán và trong quá trình phát hiện biên cũng đƣợc
24. 12 tính đến. Còn khái niệm về biên nêu ở trên đƣợc sử dụng để xây dựng các phƣơng pháp phát hiên biên trong quá khứ, những mô hình về cách này đƣợc coi là đơn giản và sơ sài. Hình 2.3. đƣờng biên không trơn 2.2.2 Vai trò của biên trong nhận dạng Đƣờ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. Ngƣời ta sử dụng đƣờng biên làm phân cách các vùng xám (màu) cách biệt. Ngƣợc lại, ngƣời ta cũng dùng các vùng ảnh để tìm đƣờng phân cách. Nhƣ đã đề cập tới ở phần tổng quan về một hệ thống nhận dạng và xử lý ảnh, quá trình nhận dạng có hai giai đoạn cần thực hiện: - Giai đoạn học: Các đặc điểm của đối tƣợng mẫu đƣợc lƣu trữ (gọi là học mẫu) và tập các phần tử mẫu đƣợc chia thành các lớp.
25. 13 - Giai đoạn nhận dạng: Khi có đối tƣợng cần nhận dạng, các đặc điểm của đối tƣợng sẽ đƣợc trích chọn và sử dụng hàm quyết định để xác định đối tƣợng cần nhận dạng thuộc lớp nào. Nhƣ vậy, việc nhận dạng sẽ chính xác nếu các đặc điểm đƣợc trích chọn chính xác. Trong thực tế, các đặc điểm trích chọn phục vụ cho việc nhận dạng thƣờng là các bất biến [7,8,18,26,30,38,45], bởi vì vấn đề cơ bản trong bài toán nhận dạng ảnh là xác định các đối tƣợng không phụ thuộc vào vị trí, kích thƣớc và hƣớng quay. Có nhiều loại bất biến đƣợc trích chọn nhƣ: - Bất biến thống kê: Các mô men, độ lệch chuẩn của tập ảnh hay các độ đo thống kê khác không phụ thuộc các phép biến đổi tuyến tính. - Bất biến hình học: Số đo kích thƣớc của các đối tƣợng ảnh. - Bất biến tô-pô: Biểu diễn các cấu trúc tô-pô của các ảnh nhƣ số điểm đỉnh, số lỗ hổng v.v - Bất biến đại số: Chu tuyến, phân bố của các điểm ảnh, v.v dựa vào các việc tổ hợp các hệ số của đa thức mô tả đối tƣợng ảnh. Các bất biến dùng trong nhận dạng thƣờng đƣợc trích chọn từ biên, xƣơng của đối tƣợng [3,5,8,18,33,38,39,45,46,48]. Do vậy, việc nhận dạng có hiệu quả hay không phụ thuộc nhiều vào cách biểu diễn hình dạng và mô tả của vật thể.
26. 14 Chƣơng 3. MỘT SỐ KĨ THUẬT PHÂN ĐOẠN ẢNH 3.1 Phân đoạn ảnh dựa vào ngƣỡng 3.1.1 Giới thiệu Biên độ của các tính chất vật lý của ảnh (nhƣ là độ phản xạ, độ truyền sáng, màu sắc ) là một đặc tính đơn giản và rất hữu ích. Nếu biên độ đủ lớn đặc trƣng cho ảnh thì chúng ta có thể dùng ngƣỡng biên độ để phân đoạn ảnh. Thí dụ, biên độ trong bộ cảm biến hồng ngoại có thể phản ánh vùng có nhiệt độ thấp hay vùng có nhiệt độ cao. Đặc biệt, kỹ thuật phân ngƣỡng theo biên độ rất có ích đối với ảnh nhị phân nhƣ văn bản in, đồ họa, ảnh màu hay ảnh X-quang. Việc chọn ngƣỡng trong kỹ thuật này là một bƣớc vô cùng quan trọng, thông thƣờng ngƣời ta tiến hành theo các bƣớc chung nhƣ sau: Xem xét lƣợc đồ xám của ảnh để xác đỉnh và khe. Nếu ảnh có nhiều đỉnh và khe thì các khe có thể sử dụng để chọn ngƣỡng. Chọn ngƣỡng T sao cho một phần xác định trƣớc η của toàn bộ số mẫu là thấp hơn T. Điều chỉnh ngƣỡng dựa trên xét lƣợc đồ xám của các điểm lân cận. Chọn ngƣỡng bằng cách xem xét lƣợc đồ xám của những điểm thoả tiêu chuẩn đã chọn. Một thuật toán đơn giản trong kỹ thuật này là: giả sử rằng chúng ta đang quan tâm đến các đối tƣợng sáng (object) trên nền tối (background), một tham số T - gọi là ngƣỡng độ sáng, sẽ đƣợc chọn cho một ảnh f[x,y] theo cách: Ngƣợc lại, đối với đối tƣợng tối trên nền sáng chúng ta có thuật toán sau:
27. 15 Vấn đề chính là chúng ta nên chọn ngƣỡng T nhƣ thế nào để việc phân vùng đạt đƣợc kết quả cao nhất?. Có rất nhiều thuật toán chọn ngƣỡng: ngƣỡng cố định, dựa trên lƣợc đồ, sử dụng Entropy, sử dụng tập mờ, chọn ngƣỡng thông qua sự không ổn định của lớp và tính thuần nhất của vùng vv Ở đây chúng tôi đề cập đến hai thuật toán chọn ngƣỡng đó là chọn ngƣỡng cố định và chọn ngƣỡng dựa trên lƣợc đồ. 3.1.2 chọn ngƣỡng cố định Đây là phƣơng pháp chọn ngƣỡng độc lập với dữ liệu ảnh. Nếu chúng ta biết trƣớc là chƣơng trình ứng dụng sẽ làm việc với các ảnh có độ tƣơng phản rất cao, trong đó các đối tƣợng quan tâm rất tối còn nền gần nhƣ là đồng nhất và rất sáng thì việc chọn ngƣỡng T= 128 (xét trên thang độ sáng từ 0 đến 255) là một giá trị chọn khá chính xác. Chính xác ở đây hiểu theo nghĩa là số các điểm ảnh bị phân lớp sai là cực tiểu. 3.1.3 Chọn ngƣỡng trên lƣợc đồ(Histogram) Trong hầu hết các trƣờng hợp, ngƣỡng đƣợc chọn từ lƣợc đồ độ sáng của vùng hay ảnh cần phân đoạn. Có rất nhiều kỹ thuật chọn ngƣỡng tự động xuất phát từ lƣợc đồ xám {h[b] | b = 0, 1, , 2B-1} đã đƣợc đƣa ra. Những kỹ thuật phổ biến sẽ đƣợc trình bày dƣới đây. Những kỹ thuật này có thể tận dụng những lợi thế do sự làm trơn dữ liệu lƣợc đồ ban đầu mang lại nhằm loại bỏ những dao động nhỏ về độ sáng. Tuy nhiên các thuật toán làm trơn cần phải cẩn thận, không đƣợc làm dịch chuyển các vị trí đỉnh của lƣợc đồ. Nhận xét này dẫn đến thuật toán làm trơn dƣới đây: (3.1) Trong đó W thƣờng đƣợc chọn là 3 hoặc 5 3.1.3.1 Thuật toán đẳng liệu Đây là kỹ thuật chọn ngƣỡng theo kiểu lặp do Ridler và Calvard đƣa ra.Thuật toán đƣợc mô tả nhƣ sau: Bƣớc 1: Chọn giá trị ngƣỡng khởi động
28. 16 Bƣớc 2: Tính các trung bình mẫu (mf,0) của những điểm ảnh thuộc đối tƣợng và (mb,0) của những điểm ảnh nền. Bƣớc 3: Tính các ngƣỡng trung gian theo công thức: vớik=1,2, (3.2) Bƣớc 4: Nếu : kết thúc; dừng thuật toán. Ngƣợc lại, lặp lại bƣớc 2. 3.1.3.2 Thuật toán đối xứng nền Kỹ thuật này dựa trên sự giả định là tồn tại hai đỉnh phân biệt trong lƣợc đồ nằm đối xứng nhau qua đỉnh có giá trị lớn nhất trong phần lƣợc đồ thuộc về các điểm ảnh nền. Kỹ thuật này có thể tận dụng ƣu điểm của việc làm trơn đƣợc mô tả trong phƣơng trình (2.1). Đỉnh cực đại maxp tìm đƣợc nhờ tiến hành tìm giá trị cực đại trong lƣợc đồ. Sau đó thuật toán sẽ đƣợc áp dụng ở phía không phải là điểm ảnh thuộc đối tƣợng ứng với giá trị cực đại đó nhằm tìm ra giá trị độ sáng a ứng với giá trị phần trăm p% mà: P(a) = p%, trong đó P(a) là hàm phân phối xác suất về độ sáng đƣợc định nghĩa nhƣ sau: Định nghĩa: Hàm phân phối xác suất P(a) thể hiện xác suất chọn đƣợc một giá trị độ sáng từ một vùng ảnh cho trƣớc, sao cho giá trị này không vƣợt quá một giá trị sáng cho trƣớc a. Khi a biến thiên từ -∝ đến +∝, P(a) sẽ nhận các giá trị từ 0 đến 1. P(a) là hàm đơn điệu không giảm theo a, do vậy dP/da ≥ 0. Hình 3.1. Minh họa thuật toán đối xứng nền Ở đây ta đang giả thiết là ảnh có các đối tƣợng tối trên nền sáng. Giả sử mức là 5%, thì có nghĩa là ta phải ở bên phải đỉnh maxp một giá trị a sao cho
29. 17 P(a)=95%. Do tính đối xứng đã giả định ở trên, chúng ta sử dụng độ dịch chuyển về phía trái của điểm cực đại tìm giá trị ngƣỡng T: T = maxp – (a – maxp) (3.3) Kỹ thuật này dễ dàng điều chỉnh đƣợc cho phù hợp với tình huống ảnh có các đối tƣợng sáng trên một nền tối. 3.1.3.3 Thuật toán tam giác Khi một ảnh có các điểm ảnh thuộc đối tƣợng tạo nên một đỉnh yếu trong lƣợc đồ ảnh thì thuật toán tam giác hoạt động rất hiệu quả. Thuật toán này do Zack đề xuất và đƣợc mô tả nhƣ sau: Bƣớc 1: Xây dựng đƣờng thẳng ∆ là đƣờng nối hai điểm (Hmax, bmax) và (Hmin, bmin), trong đó Hmax là điểm có Histogram lớn nhất ứng với mức xám bmax và Hmin là điểm có Histogram ứng với độ sáng nhỏ nhất bmin. Bƣớc 2: Tính khoảng cách d từ Hb của lƣợc đồ (ứng với điểm sáng b) đến ∆. Trong đó, b ∈ [bmax, bmin] Bƣớc 3: Chọn ngƣỡng T = Max{Hb }. Thuật toán tam giác đƣợc minh họa bởi hình 3.2 Hình 3.2. Minh họa thuật toán tam giác
30. 18 3.1.3.4 Chọn ngƣỡng đối với Bimodal Histogram Ngƣỡng T đƣợc chọn ở tại vị trí cực tiểu địa phƣơng của histogram nằm giữa hai đỉnh của histogram. Điểm cực đại địa phƣơng của histogram có thể dễ dàng đƣợc phát hiện bằng cách sử dụng biến đổi chóp mũ (top hat) do Meyer đƣa ra: Phụ thuộc vào tình huống chúng ta đang phải làm việc là với nhƣng đối tƣợng sáng trên nền tối hay đối tƣợng tối trên nền sáng mà phép biến đổi top hat sẽ có một trong hai dạng sau: a) Các đối tƣợng sáng: TopHat ( A, B) = A − ( A * B ) = A − max (min ( A)) (3.4) b) Các đối tƣợng tối: TopHat ( A, B) = A − ( A * B ) = A − min (max( A)) (3.5) Việc tính toán giá trị cực tiểu địa phƣơng của histogram thì khó nếu histogram nhiễu. Do đó, trong trƣờng hợp này nên làm trơn histogram, ví dụ sử dụng thuật toán (3.1). Hình 3.3. Thuật toán đối xứng nền Trong một số ứng dụng nhất định, cƣờng độ của đối tƣợng hay nền thay đổi khá chậm. Trong trƣờng hợp này, histogram ảnh có thể không chứa hai thuỳ phân biệt rõ ràng, vì vậy có thể phải dùng ngƣỡng thay đổi theo không gian. Hình ảnh đƣợc chia thành những khối hình vuông, histogram và ngƣỡng đƣợc tính cho mỗi khối tƣơng ứng. Nếu histogram cục bộ không phải là bimodal histogram thì
31. 19 ngƣỡng đƣợc tính bằng cách nội suy ngƣỡng của các khối láng giềng. Khi ngƣỡng cục bộ đã có thì áp dụng thuật toán (2.1) phân ngƣỡng cho khối này. 3.2 Phân đoạn theo miền đồng nhất 3.3.1 Giới thiệu Giả sử rằng một miền ảnh X phải đƣợc phân thành N vùng khác nhau: R1, , RN và nguyên tắc phân đoạn là một vị từ của công thức P(R). Việc phân đoạn ảnh chia tập X thành các tập con Ri, i = 1 N phải thoả mãn: Các vùng Ri, i=1 N phải lấp kín hoàn toàn ảnh: N X = * Ri (3.6) i =1 Hai vùng khác nhau phải là những tập hợp rời nhau: Ri ∩ R j = 0 với i ≠ j (3.7) Mỗi vùng Ri phải có tính đồng nhất: P(Ri) = TRUE với i = 1 N (3.8) Kết quả của việc phân vùng ảnh phụ thuộc vào dạng của vị từ P và các đặc trƣng đƣợc biểu diễn bởi vectơ đặc trƣng. Thƣờng thì vị từ P có dạng P(R,X,t), trong đó X là vectơ đặc trƣng gắn với một điểm ảnh và t là một tập hợp các tham số (thƣờng là các ngƣỡng). Trong trƣờng hợp đơn giản nhất, vectơ đặc trƣng X chỉ chứa giá trị mức xám của ảnh I(k,l) và vectơ ngƣỡng chỉ gồm một ngƣỡng T. Một nguyên tắc phân đoạn đơn giản có công thức: P(R): f(k,l) < T (3.10) Trong trƣờng hợp các ảnh màu, vectơ đặc trƣng X có thể là ba thành phần T. ảnh RGB [fR(k,l), fG(k,l), fB(k,l)] Lúc đó luật phân ngƣỡng có dạng: P(R,x,t): ((fR(k,l)<TR)&& (fG(k,l)<TR)&&(fB(k,l)<TR)) (3.11) 3.3.2 Phƣơng pháp tách cây tứ phân Phƣơng pháp tách cây tứ phân dựa trên nguyên tắc kiểm tra tính hợp thức của tiêu chuẩn đồng nhất một cách tổng thể trên miền lớn. Nếu tiêu chuẩn đƣợc
32. 20 thoả việc phân đoạn coi nhƣ kết thúc. Trong trƣờng hợp ngƣợc lại, chia miền đang xét thành 4 miền nhỏ hơn, áp dụng đệ quy bằng phƣơng pháp trên cho mỗi miền nhỏ hơn cho đến khi tất cả các miền đều thoả mãn tiêu chuẩn đồng nhất. Thuật toán đƣợc mô tả nhƣ sau: Procedure PhanDoan(Mien) Begin If miền đang xét không thoả Then Begin Chia miền đang xét thành 4 miền: Z1, Z2, Z3, Z4 For i=1 to 4 Do PhanDoan(Zi) End Else Exit End; 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. Vì thế cây này có tên là cây tứ phân. Gốc của cây là ảnh ban đầu, một vùng thoả tiêu chuẩn tạo nên một nút lá, nếu không sẽ tạo nên một nút nhánh . Giả sử chọn tiêu chuẩn phân vùng là màu sắc và quy ƣớc mọi điểm của vùng là màu trắng sẽ tạo nên một nút lá trắng và tƣơng tự nhƣ vậy với nút lá đen. Nút màu ghi có nghĩa là vùng không thuần nhất và phải tiếp tục chia. Hình x.x a-e minh họa thuật toán tách cây tứ phân: ảnh gốc (a) đƣợc chia thành 4 phần đƣợc kết quả phân mức 1 (b), tiếp tục thực hiện đối với các phần nhỏ, ta đƣợc phân mức 2, 3.
33. 21 a) ảnh gốc b) phân mức 1
34. 22 c) phân mức 2 d) phân mức 3
35. 23 e) cây tƣơng phản Hình 3.4. phƣơng pháp cây tứ phân 3.3.3 Phƣơng pháp phân vùng bởi hợp Phƣơng pháp phân vùng bởi hợp thao tác ngƣợc lại với phƣơng pháp tách cây tứ phân, nghĩa là xuất phát từ các miền nhỏ nhất – các điểm ảnh rồi hợp chúng lại nếu thoả mãn tiêu chuẩn đề ra để đƣợc miền đồng nhất lớn hơn. Tiếp tục với các miền thu đƣợc cho đến khi ta không thể hợp nhất chúng với nhau nữa, lúc này số miền còn lại chính là các phân vùng của ảnh. Việc hợp nhất hai miền phải thoả mãn hai nguyên tắc sau: - Hai vùng kế cận - Hai vùng phải đáp ứng tiêu chuẩn, nhƣ cùng màu, cùng mức xám hay cùng kết cấu vv Giả sử vùng Ri có n điểm, lúc đó giá trị trung bình mi và độ lệch tiêu chuẩn σi đƣợc tính theo công thức: (3.12)
36. 24 Hai vùng R1 và R2 có thể hợp thành một vùng nếu | m1 − m2 |< T và điểm I(k, l) sẽ đƣợc hợp với vùng Ri nếu |I (k , l ) − mi |< T, với T là một ngƣỡng. Đầu tiên chúng ta cố gắng hợp điểm (k, l) với một trong các vùng lân cận Ri. Nếu việc hợp không thành công thì ta hợp với các vùng khác đã có. Nếu vẫn không thành công hoặc không có vùng lân cận tồn tại thì điểm này đƣợc coi là một vùng mới. Sau khi hợp nhất (k,l) vào vùng R thì ta phải cập nhật lại giá trị trung bình và độ lệch tiêu chuẩn: (3.14) (3.15) Nếu có nhiều hơn một vùng lân cận thoả mãn thì hợp điểm (k, l) với vùng Ri sao cho sự khác biệt |I ( k , l ) – mi| nhỏ nhất 3.3.4 phƣơng pháp tổng hợp. Hai phƣơng pháp: tách cây tứ phân và phƣơng pháp phân vùng bởi hợp có một số nhƣợc điểm. phƣơng pháp tách cây tứ phân tạo nên một cấu trúc phân cấp và thiết lập mối quan hệ giữa các vùng. Tuy nhiên nó thực hiện việc chia quá chi tiết. Phƣơng pháp phân vùng bởi hợp cho phép làm giảm số miền liên thông xuống tối thiểu nhƣng cấu trúc hàng ngang dàn trải, không cho ta thấy mối liên hệ giữa các vùng. Để khắc phục nhƣợc điểm này mà ta sử dụng phƣơng pháp phối hợp cả 2 phƣơng pháp. Trƣớc tiên dùng phƣơng pháp tách để tạo nên cây tứ phân, phân đoạn theo hƣớng từ gốc đến lá. Tiếp theo tiến hành duyệt cây theo chiều ngƣợc lại và hợp các vùng có cùng tiêu chuẩn. Với phƣơng pháp này ta thu đƣợc miêu tả cấu trúc của ảnh với các miền liên thông có kích thƣớc tối đa. Giải thuật trên gồm một số bƣớc sau: 1. Kiểm tra tiêu chuẩn đồng nhất
37. 25 Nếu không thoả và số điểm trong vùng lớn hơn một điểm, tách làm 4 vùng (trên, dƣới, trái, phải) bằng cách gọi đệ quy. Nếu kết quả tách xong và không tách đƣợc nữa chuyển sang bƣớc ii. Nếu tiêu chuẩn đồng nhất là thoả thì tiến hành hợp vùng và cập nhật giá trị trung bình cho vùng. 2. Hợp vùng: Cần kiểm tra 4 lân cận đã nêu trên. Có thể có nhiều vùng thoả mãn khi đó ta chọn vùng tối ƣu rồi tiến hành hợp. Phƣơng pháp này thu đƣợc kết quả số vùng là nhỏ hơn phƣơng pháp tách và ảnh đƣợc làm trơn hơn.
38. 26 Chƣơng 4 MỘT SỐ PHƢƠNG PHÁP PHÁT HIỆN BIÊN Biên là một phần đặc biệt quan trọng trong xử lý ảnh, hầu nhƣ trƣớc khi sử dụng các thuật toán phát hiện biên phải trải qua một bƣớc tiền xử lý, đó là quá trình loại bỏ nhiễu. Cơ sở của các phép toán phát hiện biên đó là quá trình biến đổi về giá trị độ sáng của các điểm ảnh. Tại điểm biên sẽ có sự biến đổi đột ngột về mức xám. Đây chính là cơ sở của kỹ thuật phát hiện biên. Xuất phát từ cơ sở này, có hai phƣơng pháp phát hiện biên tổng quát, đó là phƣơng pháp phát hiện biên trực tiếp và phƣơng pháp phát hiện biên gián tiếp. 4.1 Phân loại các 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 Phƣơng pháp phát hiện biên 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. Phƣơng pháp này bao gồm kỹ thuật Gradient và kỹ thuật la bàn. - Nếu lấy đạo hàm bậc hai của ảnh ta có phƣơng pháp Laplace. 4.1.2 Phƣơng pháp phát hiện biên gián tiếp Là quá trình phân vùng dựa vào phép xử lý kết cấu đối tƣợng, cụ thể là dựa vào sự biến thiên nhỏ và đồng đều độ sáng của các điểm ảnh thuộc một đối tƣợng. Nếu các vùng của ảnh đƣợc xác định thì đƣờng phân ranh giữa các vùng đó chính là biên ảnh cần tìm. Việc phát hiện biên và phân vùng đối tƣợng là hai bài toán đối ngẫu. Từ phát hiện biên ta có thể tiến hành phân lớp đối tƣợng, nhƣ vậy là đã phân vùng đƣợc ảnh. Và ngƣợc lại, khi đã phân vùng đƣợc ảnh nghĩa là đã phân lập đƣợc thành các đối tƣợng, từ đó có thể phát hiện đƣợc biên cần tìm. Tuy nhiên, phƣơng pháp tìm biên trực tiếp thƣờng sử dụng có hiệu quả vì ít chịu ảnh hƣởng của nhiễu. Song nếu sự biến thiên độ sáng của ảnh là không cao thì khó có thể phát hiện đƣợc biên, trong trƣờng hợp này việc tìm biên theo phƣơng pháp trực tiếp tỏ ra không đạt đƣợc hiệu quả tốt. Phƣơng pháp tìm biên
39. 27 gián tiếp dựa trên các vùng, đòi hỏi áp dụng lý thuyết về xử lý kết cấu đối tƣợng phức tạp, vì thế khó cài đặt, song đạt hiệu quả cao khi sự biến thiên về cƣờng độ sáng là nhỏ. 4.1.3 Quy trình phát hiện biên Bƣớc 1: Do ảnh ghi đƣợc thƣờng có nhiễu, bƣớc một là phải lọc nhiễu Bƣớc 2: Làm nổi biên sử dụng các toán tử phát hiện biên. Bƣớc 3: Định vị biên. Bƣớc 4: Liên kết và trích chọn biên. Chú ý: kĩ thuật làm nổi biên có thể gay nhiễu và làm xuất hiện một số biên giả, do vậy ta cần lạo bỏ biên giả. 4.2. Kỹ thuật phát hiện biên Gradient Kỹ thuật Gradient là kỹ thuật dò biên cục bộ dựa vào cực đại của đạo hàm. Đây là phép toán lấy đạo hàm bậc nhất trong không gian hai chiều. 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, ta có: (4.1) (4.2) Trong đó dx, dy là khoảng cách giữa 2 điểm kế cận theo hƣớng x, y tƣơng ứng (thực tế chọn dx= dy=1). Đây là phƣơng pháp dựa theo đạo hàm riêng bậc nhất theo hƣớng x, y. Theo định nghĩa về Gradient, nếu áp dụng nó vào xử lý ảnh, việc tính toán sẽ rất phức tạp. Để đơn giản mà không mất tính chất của phƣơng pháp Gradient, ngƣời ta sử dụng kỹ thuật Gradient dùng cặp mặt nạ H1, H2 trực giao (theo 2 hƣớng vuông góc). Việc xấp xỉ đạo hàm bậc nhất theo các hƣớng x và y đƣợc thực hiện thông qua 2 mặt nạ nhân chập tƣơng ứng sẽ cho ta các kỹ thuật phát hiện biên khác nhau.
40. 28 4.2.1 Toán tử Sobel Kỹ thuật Sobel sử dụng 2 mặt nạ nhân chập theo 2 hƣớng x, y là: Các bƣớc tínhcủa kĩ thuật sobel: Bƣớc 1: Tính I ⊗ Hx và I ⊗ Hy Bƣớc 2: Tính I ⊗ Hx + I ⊗ Hy Ví dụ:
41. 30 Hình 4.1. Biên ảnh với sobel 4.2.2 Toán tử Prewitt Toán tử đƣợc Prewitt đƣa ra vào năm 1970, kĩ thuật này sử dụng hai mặt nạ nhân chập có dạng: Các bƣớc tínhcủa kĩ thuật Prewitt: Bƣớc 1: Tính I ⊗ Hx và I ⊗ Hy Bƣớc 2: Tính I ⊗ Hx + I ⊗ Hy Kết quả của kĩ thuật Prewitt xem hình 4.2
42. 31 Hình 4.2 Biên ảnh với toán tử Prewitt 4.3 Các toán tử la bàn Kỹ thuật sử dụng toán tử la bàn lấy đạo hàm theo tám hƣớng: Bắc, nam, đông , tây, đông bắc, tây bắc, đông nam, tây nam. Toán tử la bàn do Gradient dựa trên sự đánh giá tất cả các hƣớng có thể của một đƣờng biên ảnh trong một ảnh rời rạc. Bởi vậy thay vì chỉ áp dụng hai mặt nạ nhƣ các toán tử trong kỹ thuật Gradient ở trên, tám mặt nạ đã đƣợc dùng, mỗi cái cung cấp một cạnh đƣờng biên dọc theo một trong tám hƣớng có thể của vòng. Nhƣ vậy, mỗi điểm ảnh đầu ra là giá trị lớn nhất trong tám kết quả nhân xoắn của mặt nạ với ma trận ảnh. Sau mỗi lần nhân xoắn, ta quay mặt nạ này đi một góc 450 ngƣợc chiều kim đồng hồ 00, 450, 900, 1350, 1800, 2250, 2700,3150. 4.3.1 Toán tử Kirsh Phép toán này đƣợc xem nhƣ là các toán tử thuần nhất. Nó tạo ra một sự thay đổi nhỏ trong Gradient và tạo ra các sự so sánh lần lƣợt nhƣ các phƣơng
43. 32 pháp trên. Các mặt nạ đƣợc sử dụng nhƣ sau: Để tìm ra biên ảnh, mỗi điểm ảnh đƣợc nhân xoắn với tất cả các mặt nạ (tâm của mặt nạ trùng với điểm ảnh đang xét). Kết quả của toán tử tại mỗi điểm là giá trị lớn nhất trong tám kết quả của việc nhân xoắn. Ký hiệu Ai; i = 1,2, ,8 là Gradient theo 8 hƣớng nhƣ 8 mặt nạ kể trên, khi đó biên độ Gradient tại điểm ảnh (x,y) đƣợc tính theo: A(x,y) = Max(|gi(x,y)|) i = 1,2, ,8
44. 33 Hình 4.3. Kết quả với toán tử Kirsh 4.3.2 Toán tử la bàn Prewitt Toán tử la bàn Prewitt đƣa ra các mặt nạ nhân cuộn theo 8 hƣớng khác nhau. Giá trị độ lớn của điểm ảnh mới đƣợc thực hiện nhƣ toán tử la bàn Kirsh. Các mặt nạ có dạng nhƣ sau:
45. 34 Hình 4.4. Biên ảnh với toán tử la bàn Prewitt 4.4 Kĩ thuật phát hiện biên Laplace Để khắc phục hạn chế và nhƣợc điểm của phƣơng pháp Gradient, trong đó sử dụng đạo hàm riêng bậc nhất ngƣời ta nghĩ đến việc sử dụng đạo hàm riêng bậc hai hay toán tử Laplace. Phƣơng pháp dò biên theo toán tử Laplace hiệu quả hơn phƣơng pháp toán tử Gradient trong trƣờng hợp mức xám biến đổi chậm, miền chuyển đổi mức xám có độ trải rộng. Toán tử Laplace đƣợc xác định bởi công thức (4.3): (4.3) Toán tử Laplace dùng một số kiểu mặt nạ khác nhau nhằm tính gần đúng đạo hàm riêng bậc hai. Các dạng mặt nạ theo toán tử Laplace bậc 3x3 có thể: (4.4)
46. 35 (4.5) (4.6) Từ đó ta đƣa ra đƣợc mặt nạ nhân chập của phƣơng pháp đạo hàm bậc hai. Kết quả này cho ra mặt nạ thứ ba gọi là phƣơng pháp Four - neighbor Laplace (sử dụng bốn láng giềng). 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. Ba kiểu mặt nạ hay dùng với toán tử Laplace: Giả sử có ảnh I, khi đó tìm biên ảnh bằng cách lấy đạo hàm bậc 2 của ảnh I (phƣơng pháp Laplace) nghĩa là nhân cuộn ảnh I với một trong 3 mặt nạ trên: Ikq = I ⊗ H Kết quả mô phỏng đƣợc thể hiện nhƣ hình 4.5
47. 36 Hình 4.5. Biên ảnh với kỹ thuật Laplace 4.5 Phƣơng pháp phát hiện biên Canny Phƣơng pháp này do John Canny ở phòng thí nghiệm MIT khởi xƣớng vào năm 1986. Canny đã đƣa một tập hợp các ràng buộc mà một phƣơng pháp phát biện biên phải đạt đƣợc. Ông đã trình bày một phƣơng pháp tối ƣu nhất để thực hiện đƣợc các ràng buộc đó. Và phƣơng pháp này đƣợc gọi là phƣơng pháp Canny. 4.5.1 Cơ sở lý thuyết thuật toán Ý tƣởng thuật toán: Ý tƣởng của phƣơng pháp này là định vị đúng vị trí bằng cách cực tiểu hoá phƣơng sai δ2 của vị trí các điểm cắt "Zero" hoặc hạn chế số điểm cực trị cục bộ để chỉ tạo ra một đƣờng bao. Các ràng buộc mà phƣơng pháp phát hiện biên Canny đã thực hiện đƣợc đó là: mức lỗi, định vị và hiệu suất. Trong đó: - Mức lỗi: có ý nghĩa là một phƣơng pháp phát hiện biên chỉ và phải tìm tất cả các biên, không biên nào đƣợc tìm bị lỗi. - Định vị: Điều này nói đến độ chênh lệch cấp xám giữa các điểm trên cùng một biên phải càng nhỏ càng tốt. - Hiệu suất: là làm sao cho khi tách biên không đƣợc nhận ra nhiều biên trong khi chỉ có một biên tồn tại.
48. 37 Ràng buộc mức lỗi và định vị đƣợc dùng để đánh giá các phƣơng pháp phát hiện biên. Còn ràng buộc về hiệu suất thì tƣơng đƣơng với mức lỗi dƣơng. Canny đã giả thiết rằng nhiễu trong ảnh tuân theo phân bố Gauss và đồng thời ông cũng cho rằng một phƣơng pháp phát hiện biên thực chất là một bộ lọc nhân xoắn có khả năng làm mịn nhiễu và định vị đƣợc cạnh. Vấn đề là tìm một bộ lọc sao cho thoả mãn tối ƣu nhất các ràng buộc ở trên. Dƣới đây là việc xây dựng một bộ lọc tối ƣu f đƣợc xấp xỉ bằng đạo hàm. Bộ lọc f đƣợc giả thiết f=0 ngoài đoạn (-w,+ w). Ba ràng buộc trên tƣơng ứng với ba điều kiện nhƣ sau: (4.7) (4.8) (4.9) Trong đó: SNR: (mức lỗi) nhằm tìm một hàm f(x) phản đối xứng sao cho tỷ số giữa tín hiệu và nhiễu là cực đại. Các giá trị Localization đại diện cho nghịch đảo chênh lệch mức xám giữa các điểm trong cùng một biên và càng lớn càng tốt. XZC: ràng buộc này nhằm hạn chế điểm cực trị cục bộ với mục đích cung cấp chỉ một đƣờng bao. Canny cố gắng tìm ra bộ lọc f làm cực đại tích: SNR * Localization. Nhƣng cuối cùng thì một sự sấp xỉ có hiệu quả của f lại chính là đạo hàm bậc nhất của hàm Gauss.
49. 38 Khi đó G có đạo hàm theo cả hai hƣớng x và y. Sự xấp xỉ với bộ lọc tối ƣu của thuật toán phát hiện biên Canny chính là G’ và do vậy, bằng phép nhân xoắn ảnh vào với G’ ta thu đƣợc ảnh E đã đƣợc tách biên ngay cả trong trƣờng hợp ảnh có nhiều nhiễu. Phép nhân xoắn thực hiện một cách dễ dàng trong khi việc tính toán khá phức tạp, đặc biệt là nhân xoắn với mảng hai chiều. Tuy nhiên một phép nhân xoắn với mảng hai chiều Gauss có thể đƣợc chia thành hai phép nhân xoắn với mặt nạ Gauss một chiều. Việc vi phân cũng có thể đƣợc thực hiện bằng phép nhân xoắn ở mảng một chiều tạo nên hai ảnh: ảnh một là việc nhân xoắn thành phần của x với mảng một chiều, ảnh hai là việc nhân xoắn thành phần của y. 4.5.2 Hoạt động của thuật toán a) Thuật toán: Thuật toán đƣợc tiến hành qua bốn bƣớc cơ bản sau: - Đọc ảnh I cần xử lý: tiến hành làm trơn ảnh bằng cách nhân xoắn ảnh với bộ lọc Gauss. - Đạo hàm bậc nhất kết quả trên theo hai hƣớng x và y: Điều này tƣơng ứng với việc nhân xoắn ảnh kết quả ở bƣớc 1 theo hai hƣớng (x và y) với một bộ lọc dựa trên đạo hàm bậc nhất (các bộ lọc của kỹ thuật Gradient). Từ đó đƣa ra kết quả đạo hàm ảnh sau khi tiến hành nhân xoắn với Gauss. - Cho ảnh kết quả ở bƣớc trên tiến hành “Non-maximum Suppression” Nghĩa là loại bỏ bớt các điểm cạnh (loại bỏ bớt nhiễu), chỉ giữ lại điểm có mức xám cao. - Tiến hành thực hiện áp dụng ngƣỡng (ngƣỡng cao và ngƣỡng thấp) để loại bỏ một số cạnh xấu. b) Giải thích thuật toán Bƣớc 1 : Tiến hành làm trơn ảnh Ở bƣớc này chúng ta tiến hành nhân ảnh với bộ lọc Gauss
50. 39 Bƣớc 2: Tiến hành đạo hàm kết quả ở bƣớc 1 Sau khi làm trơn ảnh ảnh ở bƣớc 1 (nhân ảnh với bộ lọc Gauss) ta tiến hành đạo hàm bậc nhất kết quả đó. Kết quả đạo hàm S là đạo hàm của tích ảnh I và hàm Gauss (x,y). Điều này tƣơng ứng với đạo hàm của hàm Gauss sau đó nhân với ảnh I. (4.10) Với: (4.11) Nhƣ vậy, kết quả ảnh bƣớc hai chính là sự tổng hợp của đạo hàm của Gauss theo hƣớng x nhân với ảnh I và đạo hàm của Gauss theo hƣớng y nhân với ảnh I. Nghĩa là ta có thể đạo hàm hàm Gauss theo hai hƣớng rồi mới tiến hành nhân xoắn với ảnh thay vì nhân xoắn ảnh với hàm Gauss rồi mới đạo hàm. Có thể minh hoạ nhƣ sau đạo hàm hàm Gauss theo hai hƣớng x và y, xem hình 4.6
51. 40 Hình 4.6. Đạo hàm hàm Gauss theo hai hƣớng (x,y) Sau khi tiến hành nhân xoắn ảnh I với bộ lọc Gauss ở bƣớc 1 ta có một ảnh mới S đƣợc làm trơn. Tiến hành thực hiện bƣớc hai bằng cách lấy đạo hàm ảnh mới đó theo hai hƣớng x và y rồi tổng hợp kết quả lại. Ở đây ta tiến hành nhân xoắn ảnh S với hai mặt nạ của phƣơng pháp Sobel theo hai hƣớng x và y nhƣ sau: Sau khi tiến hành nhân xoắn ảnh theo hai hƣớng x và y ta đƣợc hai ảnh theo hai hƣớng là Sx và Sy, ta tiến hành tổng hợp hai kết quả đó để cho ra kết quả cuối cùng S': (4.12) Hƣớng của biên θ nhƣ sau: (4.13)
52. 41 Ảnh S’ tìm đƣợc là kết quả của bƣớc 2. Bƣớc 3: Tiến hành loại bỏ một số cạnh dƣ thừa: Đối với mỗi điểm ảnh trên ảnh S’ ta tiến hành so sánh giá trị của điểm đó với giá trị của hai điểm lân cận điểm đó. Hai điểm lân cận này là hai điểm nằm trên đƣờng thẳng chứa hƣớng của đƣờng biên θ. Giả sử ta có điểm biên đang xét là tại vị trí (x,y), ta có 8 điểm biên lân cận điểm biên này thể hiện ở hình x.x Hình 4.7. Hình mô tả các điểm biên lân cận Tại điểm biên đó ta tiến hành tính giá trị góc của hƣớng đƣờng biên θ. Nếu hƣớng của đƣờng biên θ ≤ 22.50 hoặc θ > 157.50 thì đặt giá trị của θ= 00 và khi đó hai điểm biên lân cận điểm biên này tại vị trí (x-1, y) và (x+1, y) Tƣơng tự ta có kết quả hai điểm biên lân cận theo các hƣớng biên khác nhau, kết quả đƣợc nêu trong bảng 4.1
53. 42 Giá trị θ Phƣơng hƣớng Điểm ảnh θ ≤ 22,50 hoặc θ > 157,50 θ = 00 (x-1,y) (x+1,y) 22,50 < θ ≤ 67,50 θ = 450 (x-1,y-1) (x+1,y+1) 67,50 < θ ≤ 112,50 θ = 900 (x-1,y-1) (x+1,y-1) 112,50 < θ ≤ 157,50 θ = 1350 (x,y+1) (x,y-1) Bảng 4.1 bảng kết quả Ta tiến hành thực hiện: - Tại mỗi điểm ảnh ta tiến hành tính toán hƣớng của đƣờng biên, sau đó so sánh kết quả đó tìm ra hai điểm biên lân cận. - So sánh giá trị điểm ảnh đang xét với hai điểm biên trên: Nếu điểm ảnh này là lớn nhất thì giữ lại điểm biên này (đánh dấu điểm biên này), ngƣợc lại nếu nó nhỏ hơn một trong hai điểm biên lân cận thì điểm biên này bị loại đi (cho giá trị điểm biên này bằng 0) Ta đƣợc kết quả ảnh sau khi đã loại đi một số điểm biên không phù hợp, Lúc này số lƣợng biên trên ảnh nhìn thấy sẽ ít đi. Điều này đặc biệt có giá trị tốt để loại bỏ một số biên dƣ thừa đặc biệt với ảnh có nhiều nhiễu. Bƣớc 4: Tiến hành áp dụng ngƣỡng: Sau khi tiến hành bƣớc 3 ta tiến hành áp dụng ngƣỡng: sử dụng hai ngƣỡng, ngƣỡng cao Th và ngƣỡng thấp Tl . Những điểm biên đƣợc đánh dấu (không bị loại) ta tiếp tục tiến hành áp dụng ngƣỡng cao và ngƣỡng thấp: - Xét điểm ảnh I tại vị trí (x,y) - So sánh I(x,y) với hai ngƣỡng Th và Tl + Nếu I(x,y) ≥ Th: đánh dấu và giữ lại điểm biên này (đặt giá trị bằng 1) + Nếu I(x,y) < Tl: Loại bỏ điểm biên này (đặt giá trị bằng 0) + Nếu Tl ≤ I(x,y) < Th: ta tiến hành so sánh giá trị I(x,y) với giá trị của các của 8 điểm lân cận :
54. 43 Nếu một trong 8 điểm lân cận có giá trị > Th: Tiến hành đánh dấu và giữ lại điểm biên này. Ngƣợc lại: Loại bỏ điểm biên này (đặt giá trị bằng 0) Kết quả sau khi thực hiện phƣơng pháp phát hiện biên Canny: Hình 4.8. Biên ảnh theo phƣơng pháp Canny 4.6 Toán tử Robert(1965) Trong phƣơng pháp này sử dụng hai mặt lạ để nhân xoắn Hx và Hy và đƣợc thực hiện theo hai hƣớng -450 và 450 Chiều dài đƣờng biên ảnh có thể rút ra bằng cách dùng bất kỳ phép xử lý tuyến tính nào sau đây: (4.14) (4.15) (4.16) Trong đó: y1(i,j) và y2(i,j) là đáp ứng rút ra từ mẫu Hx và Hy
55. 44 Các phần tử trong mặt nạ gọi là trọng số. Di chuyển lần lƣợt các mặt nạ trên ảnh đang xét sao cho phần tử đầu tiên của mặt nạ trùng với phần tử (i,j) đang xét trên ảnh. Từ đó cho ra kết quả của ảnh mới theo phƣơng pháp này. Nhƣ vậy, ta có kết quả Gradient tại một điểm ảnh (i,j): y(i,j)= |y(i,j+1)- y(i+1,j)| + |y(i,j)+y(i+1,j+1)| (4.17) Kết quả của toán tử Robert sau khi tiến hành tách biên: Hình 4.9. Biên ảnh với toán tử Robert
56. 45 KẾT LUẬN Các kết quả đạt đƣợc: Trong quá trình nghiên cứu tài liệu và thực hiện đồ án dƣới sự định hƣớng của thầy hƣớng dẫn em thấy bản thân đã đạt đƣợc một số kết quả nhƣ sau:Tìm hiểu đƣợc một cách tổng quan các vấn đề về XLA và phân đoạn ảnh. Em đã có một cách nhìn có hệ thống về các phƣơng pháp phân đoạn ảnh và các thuật toán trong mỗi phƣơng pháp. Đồng thời biết đƣợc điểm mạnh/yếu của từng phƣơng pháp và có thể đƣa ra cách lựa chọn phƣơng pháp phù hợp với từng loại ảnh. Trong quá trình làm đồ án giúp em tích lũy thêm một số kiến thức về toán học, kĩ năng lập trình và đặc biệt là rèn luyện một kĩ năng để nghiên cứu khoa học Một số hạn chế cần khắc phục: Bên cạnh những kết quả đạt đƣợc em tự thấy còn một số hạn chế: chƣa đƣa ra đƣợc một phƣơng pháp phân đoạn mới hoàn toàn, trong đồ án tốt nghiệp em chỉ trình bày lại các kiến thức tìm hiểu đƣợc.
57. 46 TÀI LIỆU THAM KHẢO Tiếng Việt 1. Lƣơng Mạnh Bá,Nguyễn Thanh Thủy ,Nhập môn xử lý ảnh số,NXB Khoa học và kỹ thuật, Hà Nội. 2. Võ Đức Khánh(2003), Giáo trình xử lý ảnh ,NXB Thống kê, HàNội Tiếng Anh 3. Advanced Edge Detection Techniques in Computational Vision: [4]A.A.Alshennawy, A.A.Aly,"Edge Detection in Digital Images Using Fuzzy Logic Technique", World Academy of Science, Engineering and Technology 51 2009. 4. Canny, J., “A Computational Approach to Edge Detection”, IEEE Trans. Pattern Analysis and Machine Intelligence, 8:679-714, November 1986. 5. M.Abdulghafour,”Image segmentation using Fuzzy logic and genetic algorithms”, Journal of WSCG, vol. 11, no.1, 2003. 6. M.Paulinas, A.Usinskas, “A Survey of Genetic Algorithms Applications for Image Enhancement and Segmentation”, Information Technology and Control, Vol.36, No.3, pp.278-284,2007. 7. N. Senthilkumaran, R. Rajesh, "Edge Detection Techniques for Image Segmentation and A Survey of Soft Computing Approaches", International Journal of Recent Trends in Engineering, Vol. 1, No. 2, PP.250-254, May 2009. 8. N. Senthilkumaran, R. Rajesh, “Edge Detection Techniques for Image Segmentation - A Survey”, Proceedings of the International Conference on Managing Next Generation Software Applications (MNGSA-08), 2008, pp.749- 760. 9. Salem Saleh Al-amri et. Al., Image Segmentation by Using Edge Detection, IJCSE, Vol. 02, No. 03, 2010, 804-807.