K-means, EM and Mixture models

Please note that this is a draft version, and it has not been completed yet (though it is being improved continuously 🙂 ). I disabled the download option, so if you feel this presentation is useful, please contact me at phvu225 (at) gmail (dot) com for an updated pdf version.

Advertisements

31 comments

  1. Hi Vu, chi chua hoc xu ly anh o dai hoc, nen co mot so khai niem co ban chi nho em giup xem chi hieu dung khong nhe?

    In computer vision, segmentation refers to the process of partitioning a digital image into multiple segments (sets of pixels, also known as superpixels). The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze.[1] Image segmentation is typically used to locate objects and boundaries (lines, curves, etc.) in images. More precisely, image segmentation is the process of assigning a label to every pixel in an image such that pixels with the same label share certain visual characteristics.

    The result of image segmentation is a set of segments that collectively cover the entire image, or a set of contours extracted from the image (see edge detection). Each of the pixels in a region are similar with respect to some characteristic or computed property, such as color, intensity, or texture. Adjacent regions are significantly different with respect to the same characteristic(s)

    Mot trong nhung giai thuat cho segmentation chinh la mean shift va k-means
    Dung khong em?

  2. Hi chị, đoạn này e sửa lại như sau:
    In computer vision, image segmentation refers to the process of partitioning a digital image into multiple segments (sets of pixels, also known as superpixels). The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze.[1] Image segmentation is typically used to locate objects and boundaries (lines, curves, etc.) in images. More precisely, image segmentation is the process of assigning a label to every pixel in an image such that pixels with the same label share certain visual characteristics.

    The result of image segmentation is a set of segments that collectively cover the entire image, or a set of contours extracted from the image (see edge detection). Each of the pixels in a region are similar with respect to some characteristic or computed property, such as color, intensity, or texture. Adjacent regions are significantly different with respect to the same characteristic(s)

    Về cơ bản thì là như vậy, nhưng còn 1 ý nữa là image segmentation phụ thuộc vào cách quan niệm/yêu cầu về độ chi tiết của người dùng (cái này gọi là semantic gap). Ví dụ ảnh chụp 1 ô tô, thì có thể có các cách segmentation sau:
    – Segment ô tô ra khỏi phần nền
    – Segment từng phần của ôtô: bánh, capo, kiếng v.v…
    – Segment từng bộ phận chi tiết hơn: lốp, đĩa …

    Image Segmentation là bài toán lớn và có rất nhiều cách tiếp cận. Đúng là Mean-Shift cũng dc dùng trong Image segmentation nhưng không phải là phương pháp hiệu quả nhất. Các phương pháp segment tốt hơn sử dụng cách tiếp cận energy function, chẳng hạn như Level Set, Graph Cut, hay sử dụng ANN, model-based… Image Segmentation tùy thuộc nhiều vào quan niệm của người dùng nên cũng khó đánh giá thuật toán nào tốt nhất, nhưng theo e biết thì Mean-Shift không phải là tốt nhất, nói nó là 1 trong những phương pháp kinh điển có lẽ hợp lí hơn.
    K-means thì rất ít khi được dùng “đơn thương độc mã” cho bài toán segmentation. Có thể nó được dùng kèm trong 1 bước phụ của các pp khác.

  3. hi em, chi thay mean-shift khac k-means o cho nay: details in the image are preserved due to the nonparametric charater of the analysis which does not assume a priori any particular structure of data.

    Ques: nonparametric character la gi? does not assume a priori any particular structure of data la gi?
    Thank em.

  4. Như em đã nói, Kmeans rất ít khi dùng cho image segmentation nên so sánh Mean-Shift và Kmeans không nên lấy ngữ cảnh của image segmentation, mà phải là cho trường hợp chung chung, dùng để clustering/density estimation của một tập dữ liệu nào đó. Do đó câu trả lời của chị không ổn. Em thấy có bài này (http://saravananthirumuruganathan.wordpress.com/2010/04/01/introduction-to-mean-shift-algorithm/) viết về Mean-Shift khá ổn. Chị đọc thử xem.

  5. theo chi hieu la user khong can tunning parameter, tuc la khong can dieu chinh thong so gi trong giai thuat, doi voi optical flow thi co alpha can phai dieu chinh, con mean shift thi ko co nhieu tham so. Va no khong phu thuoc vao hinh dang, cau truc cua data.

  6. Hi chị,
    Trong thống kê, các phương pháp non-parametric là các phương pháp không dựa trên bất kì giả sử nào về dữ liệu, ngược lại với phương pháp parametric (thường giả sử dữ liệu phân bố theo một “dạng” biết trước nào đó, “dạng” biết trước đó chính là “priori” trong câu hỏi thứ 2 của chị).
    Về thực hành, parametric method thường đặc trưng dữ liệu bằng 1 số tham số nào đó (chẳng hạn giả sử dữ liệu có phân bố Gaussian, thì các tham số là variance và mean. Các tham số này là do giả sử về phân bố Gaussian mà có, chứ không phải xuất hiện từ trong bản thân dữ liệu), còn non-parametric thường không có những tham số “trên trời rơi xuống” như thế, mà nó đặc trưng dữ liệu bằng cách phân tích đặc trưng bên trong của dữ liệu, không dựa trên bất kì giả sử nào. Chính vì không có giả sử nào nên ngta nói rằng các phương pháp non-parametric thường thích nghi tốt hơn với sự phát triển/thay đổi của dữ liệu, do đi sâu phân tích vào “bản chất” của dữ liệu, mà không cần giả sử “tiền định” nào về nó cả (do những giả sử này có thể đúng với dữ liệu hiện tai nhưng nếu dữ liệu thay đổi thì có thể không còn đúng nữa).

  7. hi em, data point ma dung discussion trong nhung tai lieu ve mean shift, neu nhin o goc do segmentation, chi co the hieu data point la pixel khong?

  8. Va move to khu vuc cang dense o day, tuc la move toi khu vuc co intensity cua image cao nhat, cang ngay cang hoi tu, tuc la no se vao khu vuc density nhat, ma density nhat tren mot image anh chinh la trong greyscale, do sang toi, tuc la no move den khu vuc toi nhat cua buc anh ha?

  9. Hi chị,
    Thuật toán Mean-shift về cơ bản là như vậy, nhưng áp dụng thế nào vào segmentation là một chuyện khác. Chị thử tìm paper cụ thể về bài toán đó để đọc xem. Em không nghĩ là có thể áp dụng Mean-Shift một cách đơn giản như vậy được.

  10. oh, chi tim duoc roi, dang doc, no co lien quan den color pixel, spatial domain, no ap dung de dat duoc homogeneous regions trong mot image sau khi segmentation bang mean shift, phan tich thong tin chua trong diem convergence.

  11. Hi em, em co tim hieu tai sao mean-shift filtering lai preserve edge chua? Chi thay no explain trong cai thhi nghiem ve mean-shift filtering la do cac diem hoi tu, hoi tu ve huong nguoc voi edge, nhung van chua hieu vi sao no hoi tu nguoc ve huong edge, tai edge thi chi van thay cai diem hoi tu. Theo chi nghi thi vi doc theo edge, intensity no bi change rat sharply. Nen no converge ve edge rat nhanh, nen chac la edge co intensity rat cao, do do no van bao ton duoc edge sao khi da smooth anh bang mean shift, em thay nhan ddinh cua chi co dunmg khong?

  12. Hi chị,
    Về Mean-Shift thì có slide này soạn khá chi tiết: http://www.wisdom.weizmann.ac.il/~vision/courses/2004_2/files/mean_shift/mean_shift.ppt
    Trong slide đó, vấn đề edge preserving được giải thích là do cách làm việc của Mean-Shift filter. Theo đó nó coi không gian mẫu là kết hợp từ spatial coordinates (2 chiều x, y) và grayscale level (1 chiều) thành không gian 3 chiều. Khi đó tại các cạnh thì như chị nói, grayscale level thay đổi nhanh (giữa 2 bên của cạnh), do đó trong không gian mẫu 3D thì xung quanh những điểm trên cạnh sẽ có mật độ lớn (intensity cao) và các điểm trên cạnh sẽ dễ trở thành mean trong thuật toán Mean-Shift.

  13. 1) Hi em trai, em biet tai sao Mean shift no bao la non-parametric, nhung van co mot tham so can phan tunning do la bandwidth h(hay ban kinh cua so, hoac sigma). Chi doc Mean shift filter voi mean shift segmentation, cai nao cung phai tunning cai bandwidth ay. Theo chi hieu thi non-parametric o day la do su dung kernel Epannechnikov no ko co hai tham so nhu kernel Gaussian. Nhung that su cai cua so window cua thang mean-shift co tham so radius h. Cai tham so nay dau phai cua kernal dau dung ko em, vi neu cua kernel thi no phai la parametric roi. Chi hoi bi khong hieu cho nay.
    2) Trong giai thuat mean shift filter hoac segment, no co mot doan giong nhu la normalize cua so window. Em co tung tim hieu y nay chua, no normalize de lam gi? Chi thay no ghi normalize cua so xuong radius = 1. Co y nghia gi dac biiet ko? Normalize khac voi khong normalize cho nao? Em co tung nghe qua hoac tim hieu qua van de nay trong mean shift chua?

  14. Hi chị,
    bandwidth trong Mean-Shift là argument chứ không phải là parameter 🙂 Trong ngữ cảnh của một số thuật toán machine learning thì parameter là những thứ cần phải phải estimate, ban đầu thì giá trị của parameter là không biết trước, sau khi thuật toán chạy xong thì giá trị của parameter mới được xác định. Còn argument là những thứ ảnh hưởng đến quá trình hoạt động của thuật toán, được xác định một lần duy nhất lúc bắt đầu chạy thuật toán, và không đổi trong quá trình hoạt động của thuật toán.

    Em chưa đọc kĩ Mean-Shift filter nên chưa rõ normalize là gì. Chị đọc trong tài liệu nào thế?

  15. Hi em, vay chi hoi them cai, kernel Gaussian thi co 2 parameters: mean va variance. Ban dau gia tri nay la khong biet truoc ha? Sau khi thuat toan chay xong moi biet duoc ah? Theo nhu chi hieu thi neu su dung kernel la Gaussian thi bandwidth chinh la std deviation (la can cua variance) cua cai Gaussian ay. Em cho chi mot vi du ve parameter di, gio chi hieu argument em noi la gi, nhung chua tuong tuong duoc parameter la gi. Em co vi du cu the nao trong xu ly anh khong?

  16. Ví dụ trong xử lí ảnh thì nhiều, chẳng hạn như bài toán backgound subtraction sử dụng Gaussian distribution: phân bố của mỗi pixel sẽ được đặc trưng bởi 1 Gaussian distribution (đây là trường hợp đơn giản nhất, phức tạp hơn người ta có thể dùng mixture of Gaussians). Khi đó trong bước học mô hình background, vấn đề là làm sao xác định được mean và variance của Gaussian distribution tại mỗi pixel. Cách đơn giản nhất là người ta dựa vào frame đầu tiên để tính mean và variance. Như vậy mean và variance được thuật toán xác định, chứ không phải là do người dùng cung cấp.
    Trong trường hợp adaptive background subtraction thì mean và variance còn được cập nhật liên tục sau mỗi frame. Do đó trong trường hợp này mean và variance tại mỗi pixel là các parameter. Parameter là parameter của cái mô hình Gaussian, và thuật toán có nhiệm vụ xác định mô hình đó, cũng chính là đi tìm giá trị phù hợp của các parameter.

  17. Dạ 😀 Trong nhiều trường hợp thì parameter và argument được dùng như nhau, nhưng trong nhiều thuật toán máy học, khi phải học một cái model nào đó, thì các tham số của model đó gọi là parameter, và tương ứng để học mô hình đó thì có một thuật toán, người ta gọi luôn là parameter của thuật toán đó. Ngoài ra bản thân cái thuật toán cũng có một số argument nên dễ gây ra nhầm lẫn.
    Optical flow không phải là thuật toán máy học nên alpha gọi là argument hay parameter đều được.

  18. Hi em, em co biet binh thuong thi giai thuat mean-shift xuat phat o dau khong? Hay no muon bat dau tu dau cung duoc. Diem start cua no tren anh do. Hay cai do do user tunning luon em?

  19. Không thấy nó nói gì, chắc là bắt đầu ở đâu cũng được 😀 Em thấy bắt đầu ở đâu thì nó cũng cho cùng kết quả thì phải?

  20. Hehe,(cho la cung radius di) neu start khac cho chi chac shift den nhung cho khac nhau, nhung chac la van hoi tu tai density cao nhat nhi? Chi co neu khac radius thi moi ket qua khac nhau thoi. Ma no noi la hoi tu den density cuc bo thoi. Co khi nao phai start nhieu cho ko ta? Hoc may ly thuyet nay toan phai suy luan, ko co tool de thu 🙂

  21. Chi thay trong nhung thi nghiem cua mean shift segmentation, ket qua cho ra rat nhieu convergent points. Neu nhu chay giai thuat, start tai mot diem chi cho ra mot convergent point. Vay thi chi nghi chac phai start giai thuat tai nhieu diem khacc nhau, moi cho ra mot dong convergent points duoc. Phai khong em?

  22. Theo em biết thì trong MeanShift cổ điển, ban đầu người ta chọn một số initial position, từ đó chạy meanshift cho mỗi điểm. Mỗi position là một window. Ngta có thể merge window khi nó có cùng distribution hay peak. Như vậy thì phụ thuộc vào số điểm initial có thể có nhiều converge point.
    Ngoài ra hình như em biết 1 cải tiến của MeanShift để làm việc trên nhiều scale. Khi đó người ta chọn intial position ở tất cả các pixel, với kích thước window nhỏ, sau đó tăng dần kích thước window. Như vậy thì số điểm converge point có thể khá nhiều.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s