微信服务号

微信订阅号

2025年4月7日 6:03 星期一
首页 > 过刊浏览>2007年第18卷第2期 >205-212
PDF HTML阅读 XML下载 导出引用 引用提醒
Mean Shift算法的收敛性分析
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant Nos.60234030, 60404021 (国家自然科学基金); the Basic Research Project of the 11th Five-Year-Plan of China under Grant No.A1420060159 (国家"十一五"基础研究项目); the Academician Foundation Project of H


Convergence Analysis of Mean Shift Algorithm
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [24]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    作为迭代算法,Mean Shift的收敛性研究是应用的基础,而Comaniciu和李乡儒分别证明了Mean Shift的收敛性,但证明过程存在错误.首先指出了Comaniciu和李乡儒的证明过程存在错误;然后,从数学上重新证明了Mean Shift算法的局部收敛性,并指出其收敛到局部极大值的条件;最后,从几何上举反例分析了Mean Shift的收敛性,并进行了深入比较和讨论.这为Mean Shift算法的深入研究及应用奠定了基础.

    Abstract:

    The research of its convergence of Mean Shift algorithm is the foundation of its application. Comaniciu and Li Xiang-ru have respectively provided the proof for the convergence of Mean Shift but they both made a mistake in their proofs. In this paper, the imprecise proofs existing in some literatures are firstly pointed out. Then, the local convergence is proved in a new way and the condition of convergence to the local maximum point is offered. Finally, the geometrical counterexamples are provided for explanation about convergence of Mean Shift and the conclusion is further discussed. The results of this paper contribute to further theoretical study and extensive application for Mean Shift algorithm.

    参考文献
    [1]Cheng YZ.Mean shift,mode seeking,and clustering.IEEE Trans.on Pattern Analysis and Machine Intelligence,1995,17(8):790-799.
    [2]Comaniciu D,Ramesh V.Mean shift and optimal prediction for efficient object tracking.In:Mojsilovic A,Hu J,eds.Proc.of the IEEE Int'l Conf.on Image Processing (ICIP).2000.70-73.http://www.caip.rutgers.edu/～comanici/
    [3]Comaniciu D,Ramesh V,Meer P.Real-Time tracking of non-rigid objects using mean shift.In:Proc.of the IEEE Conf.on Computer Vision and Pattern Recognition (CVPR).2000.142-149.http://www.caip.rutgers.edu/～comanici/
    [4]Collins RT.Mean shift blob tracking through scale space.In:Proc.of the Conf.on Computer Vision and Pattern Recognition (CVPR).2003.18-20.http://csdl.computer.org/comp/proceedings/cvpr/2003/1900/02/190020234abs.htm
    [5]Comaniciu D.Image segmentation using clustering with saddle point detection.In:Proc.of the IEEE Int'l Conf.on Image Processing (ICIP).2002.297-300.http://www.caip.rutgers.edu/～comanici/
    [6]Wang J,Thiesson B,Xu YQ,Cohen M.Image and video segmentation by anisotropic kernel mean shift.In:Proc.of the European Conf.on Computer Vision (ECCV).2004.http://research.microsoft.com/～cohen/MeanShiftECCV.pdf
    [7]Comaniciu D,Ramesh V,Bue AD.Multivariate saddle point detection for statistical clustering.In:Proc.of the European Conf.on Computer Vision (ECCV).2002.561-576.http://www.caip.rutgers.edu/～comanici/
    [8]Georgescu B,Shimshoni I,Meer P.Mean shift based clustering in high dimensions:A texture classification example.In:Proc.of the ICCV.2003.456-463.http://www.caip.rutgers.edu/riul/research/papers/pdf/hims.pdf
    [9]Comaniciu D,Meer P.Mean shift analysis and applications.In:Proc.of the IEEE Int'l Conf.on Computer Vision (ICCV).1999.1197-1203.http://www.caip.rutgers.edu/～comanici/
    [10]Comaniciu D.Nonparametric information fusion for motion estimation.In:Proc.of the IEEE Conf.on Computer Vision and Pattern Recognition (CVPR).2003.59-66.http://www.caip.rutgers.edu/～comanici/
    [11]Comaniciu D,Meer P.Mean shift:A robust approach toward feature space analysis.IEEE Trans.on Pattern Analysis and Machine Intelligence,2002,24(5):603-619.
    [12]Li XR,Wu FC,Hu ZY.Convergence of a mean shift algorithm.Journal of Software,2005,16(3):365-374 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/16/365.htm
    [13]Peng NS,Yang J,Liu Z,Zhang FC.Automatic selection of kernel-bandwidth for mean shift object tracking.Journal of Software,2005,16(9):1542-1550 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/16/1542.htm
    [14]Comaniciu D,Ramesh V,Meer P.The variable bandwidth mean shift and data-driven scale selection.In:Proc.of the IEEE Int'l Conf.on Computer Vision (ICCV).2001.438-445.http://www.caip.rutgers.edu/～comanici/
    [15]Comaniciu D.An algorithm for data-driven bandwidth selection.IEEE Trans.on Pattern Analysis and Machine Intelligence,2003,25(2):281-288.http://www.caip.rutgers.edu/～comanici/
    [16]Xie Z,Li JP,Tang ZY.Non-Linear Optimization.Changsha:Publishing House of National University of Defense Technology,2003.167-174 (in Chinese).
    [17]Yu J,Shi HB,Huang HK,Sun XC,Cheng QS.Counterexamples to convergence theorem of maximum-entropy clustering algorithm.Science in China Series F,2003,46(5):321-326.
    [18]Mu YM,Yu J.On convergence of the maximum entropy clustering algorithm.Journal of Northern Jiaotong University,2003,27(5):26-29 (in Chinese with English abstract).
    [19]Laszlo M,Mukherjee S.A genetic algorithm using hyper-quadtrees for low-dimensional k-means clustering.IEEE Trans.on Pattern Analysis and Machine Intelligence,2006,28(4):533-543.
    [20]Fashing M,Tomasi C.Mean shift is a bound optimization.IEEE Trans.on Pattern Analysis and Machine Intelligence,2005,27(3):471-474.
    [12]李乡儒,吴福朝,吴战义.均值漂移算法的收敛性.软件学报,2005,16(3):365-374.http://www.jos.org.cn/1000-9825/16/365.htm
    [13]彭宁嵩,杨杰,刘志,张凤超.Mean Shift跟踪算法中核函数窗宽的自动选取.软件学报,2005,16(9):1542-1550.http://www.jos.org.cn/1000-9825/16/1542.htm
    [16]谢政,李建平,汤泽滢.非线性最优化.长沙:国防科学技术大学出版社,2003.30-54.
    [18]牟永敏,于剑.极大熵聚类算法的收敛性定理.北方交通大学学报,2003,27(5):26-29.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

文志强,蔡自兴. Mean Shift算法的收敛性分析.软件学报,2007,18(2):205-212

复制
分享
文章指标
  • 点击次数:6495
  • 下载次数: 7860
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2005-11-28
  • 最后修改日期:2006-04-27
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19796428位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号