Tài liệu Thuật toán phân vùng ảnh slic bằng các superpixels

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Nguyễn Xuân Kỳ THUẬT TOÁN PHÂN VÙNG ẢNH SLIC BẰNG CÁC SUPERPIXELS LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Thái Nguyên - 2013 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 1 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Nguyễn Xuân Kỳ THUẬT TOÁN PHÂN VÙNG ẢNH SLIC BẰNG CÁC SUPERPIXELS LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Chuyên ngành: Khoa học máy tính Mã số: 60480101 NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. ĐÀO NAM ANH Thái Nguyên - 2013 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ LỜI CẢM ƠN Để hoàn thành chương trình cao học và viết luận văn này, tôi đã nhận được sự hướng dẫn, giúp đỡ và góp ý nhiệt tình của quí thầy cô trường Đại học Công nghệ thông tin và truyền thông – Đại học Thái Nguyên. Trước hết, tôi xin chân thành cảm ơn đến quí thầy cô trường Đại học Công nghệ thông tin và truyền thông – Đại học Thái Nguyên, đặc biệt là những thầy cô đã tận tình dạy bảo cho tôi suốt thời gian học tập tại trường. Tôi xin gửi lời biết ơn sâu sắc đến Tiến sĩ Đào Nam Anh đã dành rất nhiều thời gian và nhiệt tình hướng dẫn nghiên cứu giúp tôi hoàn thành luận văn tốt nghiệp. Nhân đây, tôi xin chân thành cảm ơn Ban Giám hiệu trường Đại học Công nghệ thông tin và truyền thông – Đại học Thái Nguyên cùng quí thầy cô đã tạo rất nhiều điều kiện để tôi học tập và hoàn thành tốt khóa học. Mặc dù tôi đã có nhiều cố gắng hoàn thiện luận văn bằng tất cả sự nhiệt tình và năng lực của mình, tuy nhiên không thể tránh khỏi những thiếu sót, rất mong nhận được những đóng góp quí báu của quí thầy cô và các bạn. Thái Nguyên, tháng 9 năm 2013 Học viên Nguyễn Xuân Kỳ Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ LỜI CAM ĐOAN Tôi xin cam đoan luận văn là kết quả nghiên cứu của tôi, không sao chép của ai. Nội dung luận văn có tham khảo và sử dụng các tài liệu liên quan, các thông tin trong tài liệu được đăng tải trên các tạp chí và các trang website theo danh mục tài liệu của luận văn. Tác giả luận văn Nguyễn Xuân Kỳ Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ MỤC LỤC Danh mục các thuật ngữ, các từ viết tắt iii Danh mục các hình vẽ, đồ thị iv Mở đầu 1 Chương 1. Tổng quan về phân vùng ảnh 3 1.1 Phương pháp phân vùng dựa vào ngưỡng 4 1.2 Phân vùng dựa vào phát triển vùng 7 1.2.1 1.3 7 Phương pháp phân vùng dựa vào cạnh 1.3.1 1.4 Điểm ảnh lớn Thuật toán phân vùng đập nước Phân lớp dữ liệu 9 11 14 1.4.1 Phân lớp phân cấp 14 1.4.2 Thuật toán phân chia thứ bậc 16 1.4.3 Phân cụm 17 Kết luận chương 1 23 1.5 Chương 2. Thuật toán điểm ảnh lớn dựa trên lặp tuyến tính 2.1 Các phương pháp điểm ảnh lớn 25 26 2.1.1 Các thuật toán điểm ảnh lớn dựa vào đồ thị 26 2.1.2 Các thuật toán điểm ảnh lớn tăng dần độ dốc 27 2.2 Thuật toán điểm ảnh lớn dựa trên lặp tuyến tính 28 2.2.1 Thuật toán 30 2.2.2 Phép đo khoảng cách 32 2.2.3 Hậu xử lý 34 i Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 2.3 Độ phức tạp giải thuật 2.4 Ứng dụng của thuật toán phân vùng ảnh với điểm ảnh lớn SLIC 36 35 2.4.1 Xác định cơ chấn thương 36 2.4.2 Nén ảnh JPEG 39 2.5 Kết luận chương 2 40 Chương 3. Cài đặt thử nghiệm 41 3.1 Môi trường cài đặt 41 3.2 Kết quả thực nghiệm 41 3.3 Kết luận chương 3 51 Kết luận 52 Tài liệu tham khảo 53 Error! Bookmark not defined. ii Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ DANH MỤC CÁC THUẬT NGỮ, CÁC TỪ VIẾT TẮT CÁC THUẬT NGỮ Dendrogram Sơ đồ phân lớp Edge-Based Segmentation Method Phân vùng dựa vào cạnh Gradient Độ dốc Over-segmentation Phân vùng quá Screen Resolution Độ phân giải màn hình Sensor Cảm ứng Similarity Giống nhau Superpixel Điểm ảnh lớn True Color Màu tự nhiên Under-segmentation Phân vùng chưa hết Normalized cuts algorithm Thuật toán cắt trung bình Gradient-ascent-based algorithms Thuật toán tăng dần độ dốc Simple linear iterative clustering Thuật toán điểm ảnh lớn dựa trên lặp tuyến tính CÁC TỪ VIẾT TẮT XLA Xử lý ảnh SLIC Simple linear iterative clustering iii Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1: Phân vùng ảnh theo một ngưỡng 5 Hình 2: Phân vùng ảnh theo hai ngưỡng trong biểu đồ 6 Hình 3: Phân vùng ảnh theo vùng - phát triển vùng 7 Hình 4: Điểm ảnh lớn 8 Hình 5: Điểm ảnh lớn với kích thước nhỏ hơn 9 Hình 6: Phân vùng ảnh theo cạnh 10 Hình 7: Khái niệm về đập nước và dòng chảy 12 Hình 8: (a) ảnh đầu vào và (b) - kết quả áp dụng thuật toán đập nước. 12 Hình 9: (a) Ảnh hiển thị đánh dấu nội bộ (vùng sáng) và các đanh dấu bên ngoài (dòng nước chảy).(b) Kết quả phân vùng của (a). 13 Hình 10: Mô hình 8 nhóm thành ba cụm. 15 Hình 11: Dendrogram này tương ứng với tám mẫu trong hình 12 bằng cách sử dụng các thuật toán liên kết đơn. 16 Hình 12: Thí dụ về thuật toán k-means, để phân vùng ban đầu. 19 Hình 13: Kết quả phân vùng của ảnh Lena bằng cách sử dụng các thuật toán thay đổi trung bình. 22 Hình 14: Phân vùng “quá” - oversegmentation 244 Hình 15: Phân vùng ảnh kiến trúc với SLIC 245 Hình 16: Phân vùng ảnh thiên nhiên với SLIC 29 Hình 17: a. tìm kiếm k-mean trong toàn ảnh, b. SLIC tìm kiếm trong một vùng 30 Hình 18: Kết quả phân điểm ảnh lớn của SLIC cho các loại ảnh khác nhau với cùng số điểm ảnh lớn 31 Hình 19: SLIC với dãy ảnh liên tục trong video 364 Hình 20: Kết quả của SLIC với các ảnh kiến trúc 365 Hình 21: Ảnh siêu âm của (a) sợi cơ khỏe mạnh và (b) sợi cơ yếu. 366 Hình 22: Ảnh ban đầu của cơ khỏe mạnh và ảnh nâng cao cấp độ màu xám. 36 Hình 23: Kết quả phân vùng của hình 22. 37 Hình 24: Các vùng sợi cơ từ hình 22 38 Hình 25: Tìm các sợi lành mạnh hoặc bị hỏng từ hình 22. 38 Hình 26: (a) Một ví dụ về một người đàn ông và (b) là kết quả phân chia hình thang của chiếc mũ của ông ta. 39 iv Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ Hình 27: Kết quả tốt với i>=200 42 Hình 28: Kết quả tốt nhất với i=500, do ảnh có quá nhiều chi tiết 43 Hình 29: Kết quả với i=200 có thể chấp nhận được, tuy nhiên với i=500 thì tốt hơn 444 Hình 30: Kết quả i=100 đã khá tốt 455 Hình 31: với ảnh kiến trúc, các mức độ chi tiết tương ứng với số điểm ảnh 46 Hình 32: Với ảnh kiến trúc, số điểm ảnh lớn cao phân vùng tốt hơn 47 Hình 33: Với ảnh kiến trúc có khung cảnh thiên nhiên, cần số điểm ảnh lớn 48 Hình 34: Với ảnh có kiến trúc nét, chỉ cần ít số điểm ảnh lớn 49 Hình 35: Để phân biệt các chi tiết kiến trúc cần chọn số điểm ảnh phù hợp 50 v Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ MỞ ĐẦU Thông tin ảnh đóng vai trò quan trọng trong hầu hết mọi lĩnh vực của cuộc sống. Ngày nay, thông tin ảnh được xử lý bằng kỹ thuật số. Xử lý ảnh (XLA) là một trong những chuyên ngành quan trọng và lâu đời của Công nghệ thông tin được áp dụng trong các ứng dụng khác nhau, từ truyền hình đến chụp cắt lớp, từ nhiếp ảnh đển in ấn, từ robot đến cảm biến từ xa [1,2]. Để xử lý được ảnh thì phải trải qua nhiều bước, nhưng bước quan trọng và khó khăn nhất đó là phân vùng ảnh. Nếu bước phân vùng ả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[3,4]. Điểm ảnh lớn đang trở nên ngày càng phổ biến để sử dụng trong các ứng dụng thị giác máy tính. Superpixel là điểm ảnh lớn, hay một nhóm điểm ảnh ở cạnh nhau và có đặc tính tương đồng. Điểm ảnh lớn được dùng để đánh giá độ sâu của ảnh, phân vùng ảnh, phát hiện đối tượng trong ảnh, và thường được áp dụng cho ảnh màu. Tuy nhiên, không phải thuật toán superpixel nào cũng tốt. Để hiểu những thuật toán hiện có, cần thiết phân tích, đánh giá các ưu điểm và mặt yếu của các thuật toán. Các yếu tố cần xem xét là khả năng phát hiện phân vùng ảnh, tốc độ tính toán, hiệu quả sử dụng bộ nhớ. Trong các thuật toán trên có thuật toán đệ qui tuyến tính có tên là SLIC. Thuật toán này có cách tiếp cận phân nhóm k-means để tạo ra các điểm ảnh lớn một các hiệu quả. Mặc dù thuật toán đơn giản, nhưng SLIC có khả năng bám đường biên tốt. Đồng thời, thuật toán có tốc độ nhanh và sử dụng bộ nhớ hiệu quả, cải thiện hiệu suất phân vùng ảnh. Mục đích chính của luận văn là nắm được các hướng tiếp cận chính trong phân vùng ảnh trong đó có phân vùng ảnh màu dựa trên Điểm ảnh lớn. Luận văn sẽ tập trung tìm hiểu và trình bày thuật toán phân vùng ảnh đệ qui tuyến tính SLIC. 1 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ Ngoài phần mở đầu và kết luận, luận văn được chia làm 3 chương, cụ thể nội dung các chương như sau: Chương 1: Tổng quan về phân vùng ảnh, các thuật toán tạo superpixel. Các mô hình phân vùng ảnh cơ bản: theo đường biên, theo vùng. Trong phân ảnh theo vùng, superpixel – điểm ảnh lớn là một hướng phát triển. Chương 2: Thuật toán phân vùng ảnh SLIC. Trong chương này một số thuật toán tạo superpixel – điểm ảnh lớn sẽ được tập trung phân tích. Sau đó trình bày chi tiết thuật toán xây dựng các điểm ảnh lớn SLIC theo phương pháp đệ qui tuyến tính, áp dụng cho ảnh màu. Chương 3: Cài đặt thử nghiệm. Cài đặt thuật toán phân vùng ảnh màu, xây dựng điểm ảnh lớn SLIC bằng ngôn ngữ C++. 2 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ CHƯƠNG 1. TỔNG QUAN VỀ PHÂN VÙNG ẢNH Với một số ứng dụng, như nhận diện ảnh hay nén ảnh, ta không thể xử lý toàn bộ bức ảnh một cách trực tiếp bởi lý do việc đó không hiệu quả và phi thực tế. Vì vậy, một vài thuật toán về phân vùng ảnh đã được đưa ra nhằm phân vùng ảnh trước khi nhận diện hoặc nén. Phân vùng ảnh là phân loại hoặc nhóm ảnh thành nhiều phần (vùng) tuỳ theo đặc tính của ảnh, ví dụ, giá trị điểm ảnh hay miền tần số. Cho tới nay, có rất nhiều thuật toán về phân vùng ảnh vẫn tồn tại và được ứng dụng rộng rãi trong khoa học và trong cuộc sống thường ngày. Tuỳ theo phương pháp phân vùng ảnh, có thể phân loại chúng thành phân vùng ảnh dựa vào vùng, nhóm dữ liệu, và phân vùng ảnh dựa vào biên (cạnh) [13,14,15]. Phân vùng ảnh rất hữu ích trong nhiều ứng dụng. Phân vùng ảnh có thể phát hiện những vùng cần quan tâm trong một cảnh hoặc chú giải dữ liệu. Ta phân loại thuật toán phân vùng hiện nay thành phân vùng ảnh dựa vào vùng, hợp nhóm dữ liệu, và phân vùng ảnh dựa vào biên [6,7]. Phân vùng ảnh dựa vào vùng bao gồm các thuật toán phát triền vùng gieo hạt và vùng không gieo hạt, và thuật quét nhanh. Tất cả chúng đều mở rộng từng vùng điểm ảnh dựa vào giá trị điểm ảnh của chúng hay giá trị lượng tử hoá để làm sao cho mỗi nhóm đều có mối quan hệ. Đối với hợp nhóm dữ liệu, khái niệm nhóm dựa trên toàn ảnh và khoảng cách giữa từng dữ liệu. Đặc điểm của nhóm dữ liệu là mỗi điểm ảnh của một nhóm không liên kết hoàn toàn với nhau. Phương pháp cơ bản của nhóm dữ liệu có thể được chia thành nhóm theo thứ bậc và nhóm bộ phận. Ngoài ra, có phiên bản mở rộng của nhóm dữ liệu là thuật toán dịch chuyển trung bình, mặc dầu thuật toán này thuộc về ước lượng mật độ nhiều hơn. Phần còn lại của phân vùng ảnh là phân vùng ảnh dựa vào biên. Loại phân vùng ảnh này nhìn chung áp dụng việc tìm biên hoặc khái niệm biên. Loại điển hình này là một thuật toán đập nước, nhưng thuật toán này có vấn đề phân vùng quá (over-segment), vì thế nên dùng kỹ thuật đánh dấu (marker) để cải thiện thuật toán đập nước. Cuối cùng, ta chỉ ra một số ứng dụng áp dụng kỹ thuật phân vùng trong quá trình tiền xử lý. 3 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ Phần này giới thiệu một số thuật toán phân vùng ảnh phổ biến, tìm hiểu về những đặc tính của chúng, và chỉ ra các kết quả phân vùng. 1.1 Phương pháp phân vùng dựa vào ngưỡng Phân vùng ảnh dựa trên ngưỡng nhằm mục đích phân vùng một ảnh đầu vào thành các điểm ảnh của hai hoặc nhiều hơn hai giá trị thông qua việc so sánh các giá trị pixel với giá trị T ngưỡng được xác định một cách độc lập. Không tìm thấy các thuật toán phù hợp nhất để xác định giá trị T ngưỡng. Kết quả có thể là một hoặc tất cả những điều sau đây. • Các vùng được phân vùng có thể là nhỏ hơn hoặc lớn hơn so với thực tế. • Các cạnh của vùng đượcphân vùng có thể không được kết nối. • Vùng trên hoặc dưới của ảnh (phát sinh của các cạnh giả hoặc thiếu cạnh). Kỹ thuật cắt biểu đồ, dựa vào một ngưỡng được sử dụng để phân vùng ảnh. Việc này có thể được áp dụng trực tiếp cho một ảnh, nhưng cũng có thể được kết hợp, thực hiện trước hoặc sau một kỹ thuật xử lý ảnh khác. Ký hiệu f(x,y) là màu xám của ảnh gốc. với ngưỡng T, hàm g(x,y) sẽ lọc những điểm ảnh mà f(x,y) cho giá trị lớn hơn hoặc bằng ngưỡng T. 1 g ( x, y ) =  0 if f ( x, y ) ≥ T if f ( x, y ) < T ( 1) Trong hình 1, bên trái là ảnh gốc với ba chiếc bút chì, bên phải là phân vùng, xác định đối tượng trong vùng màu trắng, còn lại là nền màu đen. 4 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ Hình 1: Phân vùng ảnh theo một ngưỡng Việc phần vùng theo ngưỡng không chỉ dừng lại một ngưỡng: có thể có nhiều hơn một ngưỡng.  0 if f ( x, y ) < T1 1 if T ≤ f ( x, y ) < T 1 2  2 if T2 ≤ f ( x, y ) < T3 g ( x, y ) =      n if Tn ≤ f ( x, y) < Tn +1 ( 2) Việc phần vùng theo ngưỡng không chỉ dừng lại một ngưỡng: có thể có nhiều hơn một ngưỡng. Trong hình 2 là một ví dụ sử dụng 2 ngưỡng để phân vùng ảnh. 5 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ a. ảnh gốc b. ảnh được phân vùng với ngưỡng thấp c. ảnh được phân vùng với ngưỡng cao d. ảnh được phân vùng với cả hai ngưỡng Hình 2: Phân vùng ảnh theo hai ngưỡng trong biểu đồ 6 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ 1.2 Phân vùng dựa vào phát triển vùng Kỹ thuật phân vùng dựa trên cạnh có thể tìm được đường biên đối tượng và sau đó xác định vị trí các đối tượng đó bằng cách làm đầy bên trong đường biên. Kỹ thuật phân vùng dựa trên vùng có cách tiếp cận ngược lại, bắt đầu ở giữa một đối tượng và sau đó "phát triển" ra ngoài cho đến khi gặp đường biên đối tượng [11,12]. a. ảnh gốc b. kết quả của việc phát triển từ điểm hạt giống nằm chính giữa ảnh (a) Hình 3: Phân vùng ảnh theo vùng - phát triển vùng 1.2.1 Điểm ảnh lớn Các thuật toán điểm ảnh lớn nhóm các điểm ảnh thành các vùng ảnh có ý nghĩa. Cách tiếp cận này có thể thay thế các cấu trúc lưới điểm ảnh (Hình 4), loại bớt thông tin thừa, tạo nên cơ sở thuận tiện tính toán các đặc điểm của ảnh, và giảm độ phức tạp của các thủ tục xử lý ảnh sau đó. Điểm ảnh lớn đã trở thành cơ sở quan trọng cho các thuật toán quan sát máy tính, được sử dụng trong các ứng dụng đánh giá chiều sâu không gian, phân vùng ảnh, đánh giá chuyển động cơ thể, và xác định đối tượng trong ảnh. 7 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ Hình 4: Điểm ảnh lớn Có nhiều phương pháp tạo ra điểm ảnh lớn, mỗi phương pháp đều có ưu nhược điểm và phù hợp với từng ứng dụng cụ thể. Ví dụ, phương pháp dựa trên đồ thị có thể là lựa chọn tốt khi xem biên ảnh là quan trọng nhất. Tuy nhiên nếu sử dụng điểm ảnh lớn để xây dựng đồ thị, phương pháp tạo lưới đều, có thể là lựa chọn tốt hơn. Thường là khó xác định một giải pháp lý tưởng cho tất cả các ứng dụng, tuy nhiêu, với điểm ảnh lớn, thường có các yêu cầu sau: • Điểm ảnh lớn cần phải tạo nên biên ảnh tốt. • Điểm ảnh lớn cần phải được tính toán nhanh, tiết kiệm bộ nhớ, và dễ sử dụng, giảm độ phức tạp tính toán. • Khi được dùng cho mục đích phân vùng ảnh, điểm ảnh lớn cần làm tăng tốc độ và cải thiện chất lượng của kết quả. 8 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ Hình 5: Điểm ảnh lớn với kích thước nhỏ hơn Điểm ảnh lớn đã trở thành một công cụ cần thiết cho xử lý ảnh, và chương sau sẽ phân tích các kỹ thuật điểm ảnh lớn hiện đại. Các thuật toán được phân tích về sự tuân thủ đường biên, tốc độ phân vùng, và hiệu suất khi sử dụng như là một bước tiền xử lý trong phạm vi phân vùng ảnh. 1.3 Phương pháp phân vùng dựa vào cạnh Trong kỹ thuật này, các cạnh được phát hiện trong ảnh được cho là đại diện cho đường biên đối tượng, và được sử dụng để xác định các đối tượng này. Thuật toán Phân vùng theo cạnh: Bước 1: Tính ảnh tăng cường cạnh ∇f từ f, bằng một toán tử dạng gradient 9 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ Bước 2: Áp dụng ngưỡng với ảnh∇f: (∇f)t, từ đó ta có ảnh nhị phân chỉ ra các cạnh. Bước 3: Tính Laplacian Δf từ f, sử dụng bộ lọc Laplacian liên tục hoặc rời rạc. Bước 4: Tính ảnh g = (∇f)t · sgn(Δf). Trong đó hàm sgn trả lại dấu của giá trị. Ảnh g sẽ chỉ có 3 giá trị: 0 tại điểm không phait cạnh, 1. Tại điểm cạnh, ở bên vùng sáng, -1 tại điểm cạnh ở bên vùng tối. Hình dưới đây minh họa thuật toán trên. a. ảnh gốc b. ảnh được làm nét các cạnh c. ảnh được lấy ngưỡng từ (b) d. ảnh được áp dụng bộ lọc Laplacian (fii) với σ = 1 điểm ảnh. e. Làm nét cạnh cho (d) f. Lấy ngưỡng cho (e) Hình 6: Phân vùng ảnh theo cạnh 10 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/ Những phương pháp này có vấn đề với ảnh đó là: • Cạnh yếu • Rất nhiễu • Ranh giới rất mịn • Ranh giới kết cấu Các vấn đề khác của những kỹ thuật này bắt nguồn từ sự khó khăn điều chỉnh hiệu chỉnh chức năng Gradient cho phù hợp như vậy, tạo ra kết quả không mong muốn như: • Các vùng phân vùng có thể là nhỏ hơn hoặc lớn hơn so với thực tế • Các cạnh của vùng phân vùng có thể không được kết nối • Phân vùng trên hoặc dưới của ảnh (phát sinh của các cạnh giả hoặc thiếu cạnh) Về sau, các phương pháp khác chỉ dựa trên cơ sở các khái niệm về cạnh thay vì sử dụng phương pháp phát hiện cạnh, ví dụ, thuật toán phân vùng đập nước. 1.3.1 Thuật toán phân vùng đập nước Mục đích chính của thuật toán phân vùng đập nước là để tìm thấy những "dòng chảy" trong một ảnh để tách các vùng riêng biệt. Trong thuật toán này, xem ảnh như một biểu đồ địa hình 3D, trong đó x và y biểu thị tọa độ, và z biểu thị các giá trị pixel. Thuật toán bắt đầu đổ nước trong biểu đồ địa hình từ lưu vực thấp nhất tới đỉnh cao nhất. Trong quá trình này, ta có thể phát hiện một số đỉnh núi được tách rời các lưu vực, được gọi là "đập". Biểu đồ cho thấy trong hình dưới đây. 11 Soá hoùa bôûi trung taâm hoïc lieäu http://www.lrc.tnu.edu.vn/