PHÂN ĐOẠN ẢNH BẰNG THUẬT TOÁN NORMALIZED CUTS

Mở đầu

Phân đoạn ảnh từ lâu đã có những

ứng dụng mạnh mẽ và rộng rãi trong các bài toán phân tích và hiểu ảnh tự động, nhưng nó cũng là một bài toán khó mà đến bây giờ các nhà khoa học vẫn chưa giải quyết được một cách hoàn toàn thấu đáo. Trong bài báo này chúng tôi xin trình
bày một thuật toán khá đặc sắc trong lĩnh vực phân đoạn ảnh mà chúng tôi đã tìm hiểu, thuật toán “Normalized Cut” của đồng tác giả Jianbo Shi và Jitendra Malik. Ngoài ra chúng tôi cũng xin trình bày một số cải tiến của thuật

toán mà chúng tôi tìm hiểu được, đồng thời cũng đưa ra một số kết quả mà chúng tôi đã đạt được trong việc ứng dụng thuật toán “Normalized Cut” cơ bản, và cải tiến mà chúng tôi xây dựng được.

Giới thiệu

Tầm quan trọng và những khó khăn của việc gom nhóm các đối tượng mang tính tri giác của con người từ lâu đã được nghiên cứu nhiều trong các lĩnh vực của thị giác máy tinh đặc biệt trong lĩnh vực của xử lí ảnh. Làm thế nào để phân chia một ảnh thành các tập con. Những cách khả thi để có thể làm được điều đó. Đó là những câu hỏi mà người ta đã đặc ra từ lâu và mong muốn tìm được câu trả lời.

Trong vài chục năm gần đây, cộng đồng các nhà khoa học đã đưa ra các phương pháp khác nhau trong lĩnh vực phân đoạn ảnh như : Phân đoạn ảnh dựa vào cấu trúc gom cụm dựa vào cây, hay các thuật toán tách và trộn ảnh dựa vào vùng và các phương pháp thống kê … nhằm giải quyết tốt bài toán. Trước khi thực hiện bất kì một thuật toán nào chúng ta phải xác định được tiêu chuẩn gì mà chúng ta muốn tối ưu và liệu có hay không một thật toán hiệu quả cho việc thi hành phương pháp đó.

Thuật toán mà chúng tôi sử dung ở đây “Normalized Cut” là một thuật toán sử dụng phương pháp gom nhóm theo lí thuyết Graph. Mỗi ảnh gốc sẽ được thể hiện một mối quan hệ tương ứng bằng việc chuyển tập ảnh gốc ban đầu thành một đồ thị trọng số vô hướng G = (E,V) . Mà mỗi node trong G sẽ thể hiện một không gian đặc trưng và một cạnh được hình thành giữa hai node bằng một trong các phương pháp sẽ được đề cập ở phần sau.

Thực ra thuật toán này không phải là một cái gì quá xa lạ mà thực tế đã có các bài toán tương tự được đề cập trước đó, nhưng cái quan trọng nhất tạo nên sự khác biệt giữa nó với thuật toán mà chúng ta sẽ đề cập đến là sự khác biệt ở việc xây dựng một tiêu chuẩn độ đo hợp lí. Hầu hết các thuật toán tương tự trước đây đưa ra một tiêu chuẩn đánh giá dựa trên tính chất cục bộ của Graph. Trong thuật toán này các tác giả đã đưa ra một tiêu chuẩn đánh giá khác, một độ đo khá tốt cho việc phân chia ảnh – normalized cut.

Trong bài báo này chúng tôi xin giới thiệu tiêu chuẩn đánh giá này trong phần 2, sử dụng các vấn đề giá trị đặc trưng, vector đặc trưng nhằm đưa ra một phương pháp, một tiêu chuẩn để cực tiểu hóa tốt cho việc phân chia ảnh. Trong phần 3 chúng tôi trình bày các giải thích chi tiết cho thuật toán, đưa ra một số công thức nhằm áp dụng cho việc xây dựng một đồ thị từ một ảnh tổng quát. Trong phần 4, chúng tôi đưa ra một số kết quả đạt được trên thuật toán cơ bản, mà chúng tôi bàn đến ở trên. Trong phần 5, chúng tôi trình bày một số cải tiến của thuật toán đồng thời đưa ra một số kết quả tốt hơn so với chuẩn thuật toán ban đầu.

Tải về

Download DAXLA.rar From FileFront!