Đề tài Phân đoạn ảnh màu bằng Normalized CUT-NCUT

PHÂN TÍCH XỬ LÝ ẢNH Giảng viên: Ths Phạm Thế Bảo NHÓM 4: Phân đoạn ảnh màu Phạm Quang Tiến 0511038 Phạm Minh Điền 0511333 Trần Thị Mỹ Huệ 0511309 Lê Thị Khuê Văn 0511330 Phân đoạn ảnh Bài toán phân đoạn ảnh Phân hoạch một ảnh thành những phần liên thông chứa những pixel tương đồng Trường hợp lý tưởng : mỗi phần biểu diễn một đối tượng trong thế giới thực Có nhiều ứng dụng như ảnh y khoa, nhận diện khuôn mặt,… Gom nhóm(clustering) Gom nhóm Cho một tập n đối tượng x1, x2,…., xn Gom x1, x2,…., xn thành k nhóm đối tượng tương đồng Hai nhóm đối tượng xi, xj tương đồng được đo bởi độ đo tương đồng s Đồ thị ảnh Mỗi pixel là một node Mỗi cặp pixel tạo nên một cạnh Trọng lượng của cạnh đo độ tương đồng Tỉ lệ nghịch đối với màu ,vị trí ,.. Sinh ra một đồ thị chỉ độ tương đồng Thuộc tính của đồ thị tương đồng Cho Một tập đối tượng x1,…,xn độ đo tương đồng sij giữa tất cả các cặp đối tượng xi and xj là một số dương Đồ thị tương đồng G=(V,E) Vô hướng,có trọng lượng Thuộc tính của đồ thị tương đồng Cho : Một tập đối tượng x1,…,xn độ đo tương đồng sij giữa tất cả các cặp đối tượng xi and xj là một số dương Đồ thị tương đồng G=(V,E) Vô hướng,có trọng lượng Mỗi đỉnh v biểu diễn một điểm dữ liệu x Thuộc tính của đồ thị tương đồng Cho: Một tập đối tượng x1,…,xn độ đo tương đồng sij giữa tất cả các cặp đối tượng xi and xj là một số dương Đồ thị tương đồng G=(V,E) Vô hướng,có trọng lượng Mỗi đỉnh v biểu diễn một điểm dữ liệu x Mỗi cạnh có trọng lượng wij ứng với độ tương đồng sij Những node là đỉnh cô lập có trọng lượng là 0 Xây dựng đồ thị tương đồng Mô hình quan hệ láng giềng cục bộ giữa tập điểm dữ liệu Những cách tiếp cận khác nhau cho việc lựa chọn các cạnh ε-láng giềng k- láng giềng gần nhất Hoàn toàn liên thông Xây dựng đồ thị tương đồng Mô hình quan hệ láng giềng cục bộ giữa tập điểm dữ liệu Những cách tiếp cận khác nhau cho việc lựa chọn các cạnh ε-láng giềng k- láng giềng gần nhất Hoàn toàn liên thông Xây dựng đồ thị tương đồng Mô hình quan hệ láng giềng cục bộ giữa tập điểm dữ liệu Những cách tiếp cận khác nhau cho việc lựa chọn các cạnh ε-láng giềng k- láng giềng gần nhất Hoàn toàn liên thông Xây dựng đồ thị tương đồng Mô hình quan hệ láng giềng cục bộ giữa tập điểm dữ liệu Những cách tiếp cận khác nhau cho việc lựa chọn các cạnh ε-láng giềng k- láng giềng gần nhất Liên thông đủ Xây dựng đồ thị tương đồng Mô hình quan hệ láng giềng cục bộ giữa tập điểm dữ liệu Những cách tiếp cận khác nhau cho việc lựa chọn các cạnh ε-láng giềng k- láng giềng gần nhất Liên thông đủ Không biết kết quả gom nhóm như thế nào là hiệu quả Đồ thị tương đồng » Minimum Cut (1) Mục đích: phân hoạch đồ thị thành 2 tập rời nhau A và B. Ý tưởng cơ bản: tháo bỏ những cạnh liên kết với A và B. Mức độ không tương đồng giữa A và B là tổng trọng lượng của những cạnh đã tháo bỏ. Tối ưu viêc phân hoạch bằng cách giảm đến mức tối thiểu giá trị cut. Đồ thị tương đồng » Minimum Cut (1) Mục đích: phân hoạch đồ thị thành 2 tập rời nhau A và B. Ý tưởng cơ bản: tháo bỏ những cạnh liên kết với A và B. Mức độ không tương đồng giữa A và B là tổng trọng lượng của những cạnh đã tháo bỏ. Tối ưu viêc phân hoạch bằng cách giảm đến mức tối thiểu giá trị cut. Đồ thị tương đồng» Minimum Cut (1) Mục đích: phân hoạch đồ thị thành 2 tập rời nhau A và B. Ý tưởng cơ bản: tháo bỏ những cạnh liên kết với A và B. Mức độ không tương đồng giữa A và B là tổng trọng lượng của những cạnh đã tháo bỏ. Tối ưu viêc phân hoạch bằng cách giảm đến mức tối thiểu giá trị cut. Đồ thị tương đồng» Minimum Cut (2) Tồn tại những giải thuật hiệu quả cho việc tìm giá trị cut cực tiểu Đồ thị tương đồng» Minimum Cut (2) Tồn tại những giải thuật hiệu quả cho việc tìm giá trị cut cực tiểu Bài toán:tiêu chuẩn cut cực tiểu nghiêng về việc phân chia những tập nhỏ các node riêng biệt. Giá trị cut sẽ gia tăng với số cạnh liên kết A và B Đồ thị tương đồng» Minimum Cut (2) Tồn tại những giải thuật hiệu quả cho việc tìm giá trị cut cực tiểu Bài toán:tiêu chuẩn cut cực tiểu nghiêng về việc phân chia những tập nhỏ các node riêng biệt. Giá trị cut sẽ gia tăng với số cạnh liên kết A và B Đồ thị tương đồng » Minimum Cut (2) Tồn tại những giải thuật hiệu quả cho việc tìm giá trị cut cực tiểu Bài toán:tiêu chuẩn cut cực tiểu nghiêng về việc phân chia những tập nhỏ các node riêng biệt. Giá trị cut sẽ gia tăng với số cạnh liên kết A và B Đồ thị tương đồng Tồn tại những giải thuật hiệu quả cho việc tìm giá trị cut cực tiểu Bài toán:tiêu chuẩn cut cực tiểu nghiêng về việc phân chia những tập nhỏ các node riêng biệt. Giá trị cut sẽ gia tăng với số cạnh liên kết A và B  Normalization Đồ thị tương đồng» Normalized Cut (1) Ý tưởng : tính giá trị cut như tỉ số của tổng trọng lượng các cạnh của mỗi phân hoạch. Tổng trọng lượng của những node trong A đến tất cả các node trong đồ thị V đuợc định nghĩa như sau: Điều này dẫn tới normalzed cut Ncut: Đồ thị tương đồng» Normalized Cut (2) Biện pháp khắc phục tính lệch không tự nhiên của giá trị cut cực tiểu đối với những tập nhỏ. Những tập điểm riêng biệt không còn giá trị cut nhỏ nữa Giá trị Cut là tỉ số lớn của tổng kết nối từ tập nhỏ đó đến những node khác. Đồ thị tương đồng» Normalized Cut (2) Biện pháp khắc phục tính lệch không tự nhiên của giá trị cut cực tiểu đối với những tập nhỏ. Những tập điểm riêng biệt không còn giá trị cut nhỏ nữa Giá trị Cut là tỉ số lớn của tổng kết nối từ tập nhỏ đó đến những node khác. Đồ thị tương đồng» Normalized Cut (2) Biện pháp khắc phục tính lệch không tự nhiên của giá trị cut cực tiểu đối với những tập nhỏ. Những tập điểm riêng biệt không còn giá trị cut nhỏ nữa Giá trị Cut là tỉ số lớn của tổng kết nối từ tập nhỏ đó đến những node khác. Đồ thị tương đồng» Normalized Cut (2) Biện pháp khắc phục tính lệch không tự nhiên của giá trị cut cực tiểu đối với những tập nhỏ. Những tập điểm riêng biệt không còn giá trị cut nhỏ nữa Giá trị Cut là tỉ số lớn của tổng kết nối từ tập nhỏ đó đến những node khác. Ncut đo sự không liên kết (dissasociation) giữa những phân hoạch. normalized association trong phân hoach A và B có thể được định nghĩa như sau: Mục đích Mục đích:phân chia đồ thị thành những tập rời nhau A và B Sự không liên kết disassociation giữa những nhóm được cực tiểu và Sự liên kết (association)trong nội bộ các nhóm được cực đại Ncut and Nassoc liên quan với nhau theo: Do đó,việc cực tiểu sự không liên kết và cực đại sự liên kết thực sự là đồng nhất và có thể được thỏa mãn đồng thời. Không may:việc cực tiểu normalized cut chính xác là bài toán NP-đủ Giải thuật hiệu quả được yêu cầu! Tổng quan về thuật toán gom nhóm Ý tưởng cơ bản: xấp xỉ 1 lời giải rời rạc đối với bài toán phân hoạch bởi việc đưa bài toán normalized cut vào trường giá trị thực Giải thuật gom nhóm do Shi & Malik đề xuất gồm những bước cơ bản sau: Cho 1 ảnh,thiết lập đồ thị tương đồng sử dụng những pixel như những node của đồ thị. Tính toán một lời giải thực cho bài toán phân hoạch Chuyển lời giải thực sang lời giải rời rạc Thuật toán gom nhóm Ý tưởng: viết lại tiêu chuẩn Ncut sử dụng đồ thị Laplace và cực tiểu sử dụng các vector riêng Cho đồ thị tương đồng W = (wij)i,j є V Bậc di của đỉnh vi được định nghĩa như sau : D-là ma trận bậc với d1,…,dn trên đường chéo của nó Đồ thị Laplace unnormalized LU được định nghĩa như sau : Thuật toán gom nhóm Cho x là vector rời rạc |V| chiều với xi = 1 nếu vi є A, bằng -1 ngược lại Chuẩn Ncut có thể được viết lại Rayleigh quotient x có thể lấy giá trị thực, và biểu thức này có thể được tối tiểu bằng giải quyết hệ vector riêng tổng quát X dựa trên giá trị tương đồng của đỉnh vi , vi nếu wij lớn