Segmentation using eigenvectors - University of Nevada, Reno分割使用特征向量-內(nèi)華達(dá)大學(xué)里諾校區(qū)

1、normalized cuts and image segmentationjianbo shi and jitendra malik,presented by: alireza tavakkoliimage segmentationimage segmentationlhow do you pick the right segmentation? bottom up segmentation: - tokens belong together because they are locally coherent. top down segmentation: - tokens grouped

2、because they lie on the same object.“correct” segmentationlthere may not be a single correct answer.lpartitioning is inherently hierarchical.lone approach we will use in this presentation:l“use the low-level coherence of brightness, color, texture or motion attributes to come up with partitions”outl

3、ine1.introduction2.graph terminology and representation.3.“min cuts” and “normalized cuts”.4.other segmentation methods using eigenvectors.5.conclusions.outline2.graph terminology and representation.3.“min cuts” and “normalized cuts”.4.other segmentation methods using eigenvectors.5.conclusions.grap

4、h-based image segmentationimage (i)graph affinities(w)intensitycoloredgestextureslide from timothee cour (/timothee)graph-based image segmentationimage (i)(1)(1),(),(bvolavolbacutbancutslide from timothee cour (/timothee)graph affinities(w)intensitycol

5、oredgestexturegraph-based image segmentationimage (i)(1)(1),(),(bvolavolbacutbancuteigenvector x(w)aiifaiifixdxxwda01)()(slide from timothee cour (/timothee)graph affinities(w)intensitycoloredgestexturegraph-based image segmentationimage (i)(1)(1),(),(bvolavolbacutbancuteigen

6、vector x(w)discretizationslide from timothee cour (/timothee)aiifaiifixdxxwda01)()(graph affinities(w)intensitycoloredgestextureoutline1.introduction3.“min cuts” and “normalized cuts”.4.other segmentation methods using eigenvectors.5.conclusions.graph-based image segmentation

7、v: graph nodese: edges connection nodesg = v,epixelspixel similarityslides from jianbo shigraph terminologylsimilarity matrix:slides from jianbo shi222)()(,xjixxjiewjiww,affinity matrixsimilarity of image pixels to selected pixelbrighter means more similarreshapen*m pixelsn*m pixelsm pixelsn pixelst

8、he size of w is quadratic with the numberof parameters!graph terminologyldegree of node:slides from jianbo shijjiiwd,graph terminologylvolume of set:slides from jianbo shiaiivadavol,)(graph terminologyajaijiwaacut,),(slides from jianbo shilcuts in a graph:representationkxxx,.,1jjiwiid,),(wdlsegments

9、pixels),(),(jiaffjiwpixel similarity functionsintensitytexturedistance222)()(),(ijiiiejiw222)()(),(xjixxejiw222)()(),(cjiccejiwpixel similarity functionsintensitytexturedistance222)()(),(ijiiiejiw222)()(),(xjixxejiw222)()(),(cjiccejiwhere c(x) is a vector of filter outputs. a natural thing to do is

10、to square the outputs of a range of different filters at different scales and orientations, smooth the result, and rack these into a vector.definitionslmethods that use the spectrum of the affinity matrix to cluster are known as .lnormalized cuts, average cuts, average association make use of the ei

11、genvectors of the affinity matrix.lwhy these methods work?spectral clusteringdatasimilarities* slides from dan klein, sep kamvar, chris manning, natural language group stanford universityeigenvectors and blockslblock matrices have block eigenvectors:lnear-block matrices have near-block eigenvectors:

12、1100110000110011eigensolver.71.710000.71.711= 22= 23= 04= 011.2 0110-.2.20110-.211eigensolver.71.69.1400-.14.69.711= 2.022= 2.023= -0.024= -0.02* slides from dan klein, sep kamvar, chris manning, natural language group stanford universityspectral spacelcan put items into blocks by eigenvectors:lclus

13、ters clear regardless of row ordering:11.2 0110-.2.20110-.400-.14.69.71e1e2e1e21.2 10.2101101-.201-.900.69-.14.71e1e2e1e2* slides from dan klein, sep kamvar, chris manning, natural language group stanford universityoutline1.introduction2.graph terminology and representation.4.ot

14、her segmentation methods using eigenvectors.5.conclusions.how do we extract a good cluster?: we want a vector giving the association between each element and a clusterlwe want elements within this cluster to, on the whole, have lwe could lbut need the lthis is an - choose the eigenvector of w with l

15、argest eigenvalue.wxxt1xxtlcriterion for partition:minimum cutbvaubavuwbacut,),(min),(minfirst proposed by wu and leahyabideal cutcuts with lesser weightthan the ideal cutweight of cut is directly proportional to the number of edges in the cut.normalized cut)(1)(1),(),(bvolavolbacutbancutnormalized

16、cut or balanced cut:finds better cutnormalized cutlvolume of set (or association):vtautuwvaassocavol,),(),()(abnormalized cutlvolume of set (or association):ldefine normalized cut: “a fraction of the total edge connections to all the nodes in the graph”:),(),(),(),(),(vbassocbacutvaassocbacutbancutv

17、tautuwvaassocavol,),(),()(),(),(),(),(),(vbassocbbassocvaassocaaassocbanassocababldefine normalized association: “how tightly on average nodes within the cluster are connected to each other”ab01dytsubject to:observations(i)lmaximizing nassoc is the same as minimizing ncut, since they are related:lho

18、w to minimize ncut?ltransform ncut equation to a matricial form.lafter simplifying:),(2),(banassocbancutdyyywdyxncutttyx)(min)(minrayleigh quotientlinstead, relax into the continuous domain by solving generalized eigenvalue system:lwhich gives:lnote that so, the first eigenvector is y0=1 with eigenv

19、alue 0.lthe second smallest eigenvector is the real valued solution to this problem!observations(ii)dyywd)(01 )(wdmaxyytdwy subject to ytdy 1minalgorithm1.define a similarity function between 2 nodes. i.e.:2.compute affinity matrix (w) and degree matrix (d).3.solve4.use the eigenvector with the seco

20、nd smallest eigenvalue to bipartition the graph.5.decide if re-partition current partitions.note: since precision requirements are low, w is very sparse and only few eigenvectors are required, the eigenvectors can be extracted very fast using lanczos algorithm.dyywd)(222)()(222)()(,xjiijixxffjiewdis

21、cretizationlsometimes there is not a clear threshold to binarize since eigenvectors take on continuous values.lhow to choose the splitting point? a)pick a constant value (0, or 0.5).b)pick the median value as splitting point.c)look for the splitting point that has the minimum ncut value:1.choose n p

22、ossible splitting points.2.compute ncut value.3.pick minimum.use k-eigenvectorslrecursive 2-way is slow.lwe can use more eigenvectors to re-partition the graph, however:lnot all eigenvectors are useful for partition ().lprocedure: compute with a high . then follow one of these procedures:a)merge seg

23、ments that minimize -way criterion.b)use the k segments and find the partitions there using exhaustive search.lcompute q (next slides).11.2 0110-.2.20110-.400-.14.69.71e1e2e1e2exampleexperimentsldefine similarity:l for point sets.l for brightness images.l for hsv images.l in case of textu

24、re.222)()(222)()(,xjiijixxffjiew 1if iiif )cos(.),sin(.,hsvhsvvif |*| ,|,*|1nfifiifexperiments (i)lpoint set segmentation:(a) pointset generated by poisson process. (b) segmentation results.experiments (ii)lsynthetic images:experiments (iii)lweather radar:experiments (iv)lmotion segmentationoutline1

25、.introduction2.graph terminology and representation.5.conclusions.other methodslaverage associationluse the eigenvector of w associated to the biggest eigenvalue for partitioning.ltries to maximize:lhas a bias to find tight clusters. useful for gaussian distributions.bbbassocaaaassoc),(),(abother me

26、thodslaverage cutltries to minimize:lvery similar to normalized cuts.lwe cannot ensure that partitions will have a a tight within-group similarity since this equation does not have the nice properties of the equation of normalized cuts.bbacutabacut),(),(other methodsother methods20 points are randomly distributed from 0.0 to 0.512 points are randomly distributed from 0.65 to 1.0other methods20 points are randomly distributed from 0.0 to 0.512 points are randomly distributed