PHÂN ĐOẠN ẢNH MÀU BẰNG NORMALIZED CUT_NCUT

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 tính, đặ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. Đó là những câu hỏi mà người ta đã đặt 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 nhó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 thuật toán hiệu quả cho việc thi hành phương pháp đó.

Trong bài thực hành phân đoạn ảnh chúng em sử dụng ở đây”Normalized Cut” là một thuật toán sử dụng phương pháp gom nhóm theo lí thuyết đồ thị. 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ị vô hướng có trọng số G=(E,V) mà mỗi node trong G là một điểm trong không gian đặc trưng và mỗi cạnh được hình thành giữa 2 node, trọng lượng trên mỗi cạnh w(i,j) là hàm đo sự tương đồng giữa 2 node i, j.

Trong việc gom nhóm, ta cố gắng phân chia tập đỉnh thành những tập rời nhau V1,V2, ,Vm với độ đo sự tương tự của những đỉnh trong Vi thì cao còn khi băng qua những tập Vj khác thì thấp.

Để phân hoạch 1 đồ thị, ta cần đặt ra những câu hỏi sau:

· Tiêu chuẩn chính xác nào cho 1 sự phân hoạch tốt?

· Bằng cách nào 1 phân hoạch như thế có thể được tính toán 1 cách hiệu quả