jsp sql 网站开发/大搜推广
Normalized Cuts and Image Segmentation.
Normalized Cut
在图上，定义什么样的聚类最好，最简单的方法是圈定K个不相交顶点集之后，希望顶点集之间的边，其权值的和最小。
(边上的权值代表的是两头的顶点邻近的程度，或者说相似度)
这就是所谓MinCut(最小割)问题。二类分类的最小割不是NP-hard的，但是这不能让人感到开心，因为MinCut这个准则对于聚类不好。
具体来说，Mincut完全可能将离大部队过远的单个顶点与其它顶点分开, 形成两类。
事实上，我们不仅仅要让割边的权和最小，而且要让这K个顶点集都差不多大，这样才符合聚类给人的直观感觉。
于是在MinCut的基础上，出现了Normalized Cut. 思路很简单，将Cut normalize一下，除以表现顶点集大小的某种量度(如 vol A = 所有A中顶点集的度之和)。
也就是Normalize Cut(A, B) = Cut(A, B) / volA + cut(A, B) / volB
然而这样一改，NP-hard就来了。这几乎是所有组合优化问题的恶梦。
怎么办呢？把组合优化问题连续化，即所谓减少约束，进行适当的relax。那么为什么会和SVD扯上的呢？
很简单，聚类是东西分成不相交集，也就是有正交的含义在里面；只是分东西必须是0-1式的，这种离散化，就是np-hard的原因。
Tested on matlab R2009b.
Installation Notes :
1) After you unzipped the files to mydir,
put the Current Directory in Matlab to mydir
2) In the matlab command prompt,
type compileDir_simple to compile the mex files (ignore the error on the C++ non-mex file; needs to be done once)
3) You can now try any of the functions
type demoNcutImage to see a demo of image segmentation
type demoNcutClustering to see a demo of point cloud clustering
Other top level functions:
NcutImage.m: given image "I", segment it into "nbSegments" segments
[SegLabel,NcutDiscrete,NcutEigenvectors,NcutEigenvalues,W]= NcutImage(I,nbSegments);
ICgraph.m: compute Intervening Contour based pixel similarity matrix W
W = ICgraph(I);
ncutW.m: Given a similarity graph "W", computes Ncut clustering on the graph into "nbSegments" groups;
[NcutDiscrete,NcutEigenvectors,NcutEigenvalues] = ncutW(W,nbSegments);
Release notes:
2010, January 22: release of all c++ source mex files compatible with matlab R2009b
2006, May 04: release version 8: fixed incompatibility issues with new matlab
2004, June 18: release version 7: initial release
Maintained by Timothee Cour, timothee dot cour at gmail dot com
January 22, 2010.