文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > paper1220_final
侵权投诉

paper1220_final

快速Mean-shift聚类

nalindividualpoints,wecomputeonthesamples(whichisofamuchsmallernumber)toobtainthemodesofthesamplespace.Finallywe ndtheclosestmodeforeachpointbasedonGaussianweightedfeaturesimilarity,andconstructthe nalclusteringresults.

Asmeanshiftisperformedonagreatlyreducedspace(typicallythousandsoftimessmallerthanoriginaldataset),andallstagesofouralgorithmaredata-parallelacrossqueriesandcanbeimplementedthealgorithminCUDA[Buc07],wecanclusterthelargedatasetinrealtimeoratin-teractiverate(foravideowith1.44×107pixelsinFigure5).Furthermore,asthesamplespaceisanapproximatefeaturespaceoftheoriginaldatasetgeneratedusingtheproposedGaussianweightedsimilaritysampling,ourmethodreceivesaccurateresultscomparablewiththestandardmeanshiftthatperformedontheoriginaldataset.Inaddition,ourmethodusesonlyanextremelysmallfractionofresources,forbothtimeandmemoryconsuming.

Thispaperisorganizedasfollows.Insection2,wegivetherelatedwork,section3isthemainpartofourpaper,wedescribetheproposedfastmeanshiftclusteringmethod.Insection4,wegivetheapplicationsofourmethodandcom-parisonswiththerelatedmeanshiftaccelerationmethods,andweconcludeinsection5.2.Relatedwork

Meanshiftwas rstpresentedbyFukunagaandHostetler[FH75],anditwasfurtherinvestigatedbyChengetal.[Che95]andComaniciuetal.[CM02].Meanshiftisnowapopularapproachfordatasetclustering,andhasbeenwidelyusedinimageandvideosegmentation[CM02][WTXC],ob-jecttracking[CRM03],imagedenoising[BC04]andimageandvideostylization[DS02][WXSC04],italsohasbeenextendedtogeometrysegmentation[YLL 05]and3Dre-construction[WQ04],andmanyimageandvideoeditingmethodsarebasedonthemeanshiftclusteringpreprocess-ing[WBC 05].

Oneofthemaindif cultiesinapplyingMeanShiftbasedclusteringtolargedatasetsisitscomputationalcomplexity.ForeachGaussianweightedaverageiteration,thecomplex-ityofbruteforcecomputationisquadraticinthenumberofdatapoints.ThereareseveralexistingtechniqueswhichhavebeendevelopedtoincreasethespeedofMeanShift.ComaniciuandMeer[CM02]usedaxis-alignedboxwin-dows,however,thisproducesmanylimitpointsandadjacentpointsaremergedasapost-process.Dementhon[DeM02]usedmultiscalestructuretoacceleratevideosegmentation.Yangatal.[YDDD03]appliedtheFastGaussTransformtospeedupthesumsofGaussiansinhigherdimensionsthatwereusedintheMeanShiftiteration.ThismethodiseffectiveforGaussianweightedaveragewithlarge lter-ingradius,however,performingweightedaverageinarel-ativesmallradiusdoesnotbene tmuchfromthismethod.

Georgescuetal.[GSM03]acceleratedmeanshiftbyper-formingfastnearestneighborsearchwithspatiallycoherenthashtables.Carreira-Perpinán[CP06]studiedfouracceler-ationstrategiesandfoundthatspatialdiscretizationmethod(usinguniformdownsamplingschemes)performedbest.ParisandDurand[PD07]appliedthesparserepresenta-tionofthedensityfunctiontoacceleratemeanshift,similartothebilateral ltering[PD06],they rstbinnedthefea-turepointsinacoarseregulargrid,andthenblurredthebinvaluesusingaseparableGaussian.Thecomputationalcomplexityandmemoryscaleexponentiallywiththedimen-siond.Wangetal.[WLGR07]usedadualtreetospeedupMeanShiftbycomputingtwoseparatetrees,oneforthequerypoints,andoneforthereferencepoints.Comparedtothemethodsof[YDDD03][PD07],thismethodmaintainsarelativeerrorboundoftheMeanShiftiterationateachstage,leadingtoamoreaccuratealgorithm,however,theperformanceofthismethodismuchlowerthan[YDDD03][PD07].Morerecently,FreedmanandKisilev[FK09]pro-posedasamplingtechniqueforKernelDensityEstimate(KDE),theyconstructedacompactlyrepresentedKDEwithmuchsmallerdescriptioncomplexity,thismethodgreatlyacceleratesthemeanshiftprocedure,however,theaccuracyofthemeanshiftclusteringdependsonthenumberoftherandomsamples.

ManymethodshaveappliedGaussianKD-Treesforacceleratingimageandvideoprocessing.Adamsetal.[AGDL09]appliedGaussianKD-Treesforacceleratinghigh-dimensional lteringincludesthebilateralimage l-ter[TM98],bilateralgeometry ltering[JDD03,FDCO03]andimagedenoisingwithnonlocalmeans[BCM05].Weborrowsomeideasfrom[AGDL09]foradaptiveclusteringinthispaper.Xuetal.[XLJ 09]usedK-DTreetobuildadaptiveclusteringforacceleratingaf nity-basedimageandvideoeditpropagation.Asanalterative,Xiaoetal.[XNT10]usedquadtreebasedhierarchicaldatastructuretoaccelerateeditpropagation.KD-Treeshavebeenwidelyusedinac-celeratinggraphicsrendering[HSA91],thereal-rimeKD-treeconstructionongraphicshardwarealsohavebeenpro-posed[HSHH07][ZHWG08].OurmethodappliesGaus-sianKD-Trees[AGDL09]tobuildahierarchyandclusteringforthelargedatasettoacceleratethemeanshiftcomput-ing.ComparedwithParisandDurand[PD07],whosecom-plexityisexponentialinthedimensiondofthepoint,ourtree-basedmeanshiftprovideswithexcellentperformance,asitsruntimeandmemoryconsumingbothscalelinearlywithdimensionofthepoints.Withthesamplesgeneratedusingsimilarity-basedKD-treeclustering,ourmethodob-tainsmoreaccurateresultsthan[FK09]whenusingsimilarnumberofsamples.

3.Fastmeanshiftclustering

We rstgivebriefreviewofmeanshift,thenwedescribetheproposedfastmeanshiftclusteringmethod,including

c2010TheAuthor(s)Journalcompilation

c2010TheEurographicsAssociationandBlackwellPublishingLtd.

上一页第2页

你可能喜欢

热门文档

相关文档

  • 3080_Final_2012_answers

    Answers Final Exam CHEM 3080 April 9, 2012, 2 pm-5 pm CB 121 Name ... no additional paper, but you are allowed to use the back of the pages...

  • final paper

    Academic paper Final Paper Literature review ? including the backgrand, previous research limitation, purpose, method, findings and results, futhur research, ...

  • final_draft

    final_draft_其它语言学习_外语学习_教育专区。The Final Draft Reflecting on ...8 ? by 11 inch white paper ? double spaced, size 12 font ? one inch...

  • 120703_UNIQLO PR Plan CN final-14时 (NXPowerLite)

    120703_UNIQLO PR Plan CN final-14时 (NXPowerLite)_销售/营销_经管营销_...paper (release) ● 媒体/政府关系 ● 准备并进行面对媒体的准备 ● 紧急时...

  • final-exam paper

    Appendix Final exame paper of systemic anatomy for foreign studnts in WZMC Part One: 5.5 Years MBBS Major, 1 Semester of 2006-2007, Systemic Anatomy...

  • ...Multiprocessor_Architecture_white_paper_Final_v1...

    Tegra_Multiprocessor_Architecture_white_paper_Final_v1.1 tegra2 nvidiategra2 nvidia隐藏>> Whitepaper NVIDIA Tegra Multi-processor Architecture V1.0 P age...

  • 邱媛媛_小微_final

    1000-1220(2010)07- An approach for Building Complex Network of Web Service...In this paper, the approach of building complex network of web service is...

  • English_Final_Examination_Paper_A

    English_Final_Examination_Paper_A_英语考试_外语学习_教育专区。山东建筑大学往年期末及答案College English Achievement Test (Band I ) 试卷类型 A Paper One ...

  • take-home paper final

    take-home paper final_英语学习_外语学习_教育专区 暂无评价0人阅读0次下载举报文档 take-home paper final_英语学习_外语学习_教育专区。Yintong Liu ...

  • 西门子面试题 A6_Answers_to_paper_testing_Final

    西门子面试题 A6_Answers_to_paper_testing_Final_IT/计算机_专业资料。A6答案Answer to paper testing of SCM Excellence Graduate Program 2011 I. 翻译 1. ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email