精华内容
参与话题
问答
  • mean shift

    千次阅读 2018-01-31 19:48:35
    参考: http://blog.csdn.net/google19890102/article/details/51030884 http://www.cvvision.cn/5778.html https://wenku.baidu.com/view/5862334827d3240c8447ef40.html ...

    参考:
    http://blog.csdn.net/google19890102/article/details/51030884
    http://www.cvvision.cn/5778.html
    https://wenku.baidu.com/view/5862334827d3240c8447ef40.html
    http://blog.csdn.net/qq_23968185/article/details/51804574
    https://www.cnblogs.com/liqizhou/archive/2012/05/12/2497220.html
    https://www.zhihu.com/question/27301358
    https://www.zybang.com/question/3797fbcae06ac70f5071ff1ee42f23e2.html

    1 mean shift 原始形式

    mean shift介绍

    mean shift是一种聚类算法,又称为均值漂移算法,在聚类,图像平滑、分割以及视频跟踪等方面有广泛的应用。Mean Shift的概念最早是由Fukunage在1975年提出的。

    mean shift原始形式

    原始形式为这里写图片描述(1),其中x表示高维球形的球心,xi表示各个向量点,K表示落在高维球形中的向量点的个数。这个向量就是漂移向量,其中Sk指的是一个半径为h的高维球区域。也就是:这里写图片描述。从公式(1)中也可以看出,原始的mean shift不过就是对球心内所有向量进行了合成,因为我们知道这里写图片描述,最终的mean shift向量就是这些下图用黑线表示向量的和。就像力的合成一样,合力的方向由所有力的方向共同决定。
    当我们求得Mh(x)以后,我们即对x进行更新这里写图片描述(2),从而得到一个新的球心。在这个过程中,球心会一直向数据点集中的地方移动,换句话说球心会朝着数据集密度最大的方向移动。如此反复,最终球心x会收敛到一个固定值。

    原始形式伪代码

    该过程的伪代码可以表达成下面几句话,给大家一个整体认识该算法的角度。总得来说,该算法以每一个样本点作为窗口的中心点,再寻得最终中心点,最终中心点相同的样本点就是同一类。
    重复移动直至收敛{
    对每一个数据点,固定一个窗口(数据范围):
    计算窗口内数据的中心;
    移动窗口至新的中心

    用图像解释mean shift过程

    我们用二维图像上的点来解释上面的过程。
    这里写图片描述
    首先我们选定初始点为蓝色点(圆心),然后定义h的长度,我们发现一旦h定义完毕之后,那么蓝色的圆也就确定了,我们利用公式(1)计算Mh(x)并利用此来更新圆心x,得到新的圆心即黑色点,然后以黑色点为圆心,h为半径确定一个新的圆,再利用公式(1)求Mh,……如此往复,最终圆心x会收敛在一个固定的值,也就是概率密度最大的地方。更多的图像来形象地表达上述文字,如下。
    黄色箭头即为平均的偏移向量Mh(x),指向样本分布最多的区域,也就是概率密度函数的梯度方向。
    (1)初始化一个圆心蓝色点和h,计算出Mh(x)
    这里写图片描述
    (2)利用这里写图片描述进行更新,形象地看就是蓝色点在黄色箭头方向上移动到了黄色点。
    这里写图片描述
    (3)将黄色点作为新的圆心,计算出新的Mh(x),并更新圆心。
    这里写图片描述
    (4)如(3)同样的处理。
    这里写图片描述
    (5)最终圆心收敛到黄色点。
    这里写图片描述
    mean shift的基本思想就讲解完毕了。

    时间复杂度

    n 是样本点数, T 是迭代次数. 一般mean shift 在计算时间上开销很大,时间复杂度为,O(Tn^2)。

    原始形式的不足

    这样的一种原始形式的Mean Shift形式存在一个问题:在上面Mean Shift向量的计算过程中我们并没有考虑距离因素,即只要两个采样点在均值向量方向上的投影相等,则它们对Mean Shift向量计算的贡献就一样。从公式(1)我们也会发现,由于K是一个常数,所以每个向量的权重是一样的,即每一个点对圆心x的贡献是一样的。而实际上,这种贡献与x到每一个点xi之间的距离是相关的。

    2 预备知识

    核函数

    核函数也叫窗口函数,在核估计中起到平滑的作用。常用的核函数有:Uniform,Epannechnikov,Gaussian等。下面是wiki上核函数的定义(截图别人的blog,感谢作者)
    这里写图片描述
    这里写图片描述

    核密度估计

    核密度估计是一种通过非参数估计来估计变量的概率密度函数的方法,通常也被称为是Parzen窗技术。对于一维的密度函数的核密度估计公式为这里写图片描述这里写图片描述,扩展到d维下的密度函数的估计用核密度估计时就为这里写图片描述,d为x的维数,h是窗口大小。

    3 mean shift改进

    再后来由Yizong Cheng对其进行扩充,主要提出了两点的改进:
    1)定义了核函数;
    2)增加了权重系数。
    具体地说,核函数的定义使得偏移值对偏移向量的贡献随之样本与被偏移点的距离的不同而不同。权重系数使得不同样本的权重不同。所以Mean Shift中引入kernel的初衷是:随着样本与被偏移点的距离不同,其偏移量对Mean Shift向量的贡献也不同。我们先来看看核函数的定义。

    带有核函数的公式

    在原始的mean shift加入核函数,meanshift算法变为这里写图片描述(3.1),其中参数的意思为K()表示核函数,h为半径,这里写图片描述为单位密度,如果想(3.1)中的f得到最大值,我们可想到的方法就是对公式(3.1)求导。得到这里写图片描述(3.2)
    令g(x) = - k’(x);k(x)叫做g(x)的影子核,名字听上去听深奥的,也就是求导的负方向,那么上式可以表为
    这里写图片描述(3.3)
    公式(3.3)中的第二项为meanshift向量,即这里写图片描述;要使得公式(3.3)为0,当且仅当这里写图片描述,此时求出新的中心点坐标为这里写图片描述(3.4)

    meanshift算法流程

    1. 选择空间中x为圆心,以h为半径为半径,做一个高维球,落在所有球内的所有点xi
    2. 计算这里写图片描述,如果这里写图片描述<ε(人工设定),推出程序。如果这里写图片描述>ε, 则利用(3.4)计算x,返回1.
    展开全文
  • Mean Shift

    千次阅读 2012-04-03 17:37:25
    Mean Shift 2010-10-11 17:34 转载自 aspireal 最终编辑 zzf378139208 ... MeanShift并不算一种很新的特征空间分析算法,但是它原理简单,计算速度较快,通常能在一次分割后形
    Mean Shift
    
    2010-10-11 17:34
    转载自 aspireal
    最终编辑 zzf378139208

    Edge Detection and Image SegmentatiON (EDISON) System

    一、概述

           MeanShift并不算一种很新的特征空间分析算法,但是它原理简单,计算速度较快,通常能在一次分割后形成大量小的模态区域。这样便直接将问题分析层次从像素域提升到特征域,对后续处理有很大的好处。CVPR07不少新颖的分析算法(比如多目标分割)都是以mean shift为基础的。因此,它仍然有很大的研究价值。

           Rutgers的RIUL实验室将mean shift和synergistic分割算法以C++实现,并将派生的边缘检测方法集成到EDISON分析平台中,以自由软件的形式发放。本日志不讨论meanshift原理和性能,而是分析EDISON控制台程序中mean shift分割算法的实现过程和技巧。

           EDISON控制台程序模块:
           1. 脚本解释器(parser.h/parser.cpp/globalfnc.cpp)
           由于程序参数是以脚本文件提供的,所以需要进行词法、语法分析。这不是算法的重点,这里不讨论其实现方法。调用函数为
           CheckSyntax()   脚本文件语法分析,查找是否有错误语法
           Run()        脚本执行

           2. 算法控制平台(edison.h/edison.cpp)
           控制输入输出、所有参数设置及算法执行,一般由globalfnc.cpp中EXECUTE()函数调用

           3. mean shift算法(ms.h/ms.cpp/msImageProcessor.cpp)
           算法核心,ms.h/ms.cpp定义了MeanShift基类,使用lattice迭代计算实现。msImageProcessor派生至MeanShift,实现了区域合并、剔除、边界查找等应用。

           分割过程:
           1.LoadImage 获取height, width, 数据指针pImg, 数据通道数(彩色为3,灰度为1)。
           EDISON原系统仅支持PPM,PGM,PBM三种图像格式,需注意,edison不支持photoshop输出的PPM图像(ps将height width作为两行参数写入文件头;而edison默认为一行,并以空格隔开,所以需要略为修改)。我们可以很容易添加对DIB和JPG等格式的支持。

           2.指定meanshift参数:
           (1)spatial Bandwidth (float)   空间窗
           (2)range Bandwidth (float)   特征空间窗
           (3)min Region Area (int)   允许的最小区域
           关于空间窗和特征空间窗的物理含义请查看Comaniciu的《Mean Shift:A Rubost Approach Toward Feature Space Analysis》。允许的最小区域对分割算法本身是无意义的,主要用于后续区域合并。

           3.流程:
           (1) 实例化类msImageProcessor
           (2) msIP::DefineImage(pImage, channel, height, width) 定义图像数据
           内部流程为
           a. MS::DefineLInput() 设置lattice格形数据
           b. 若用户未定义核函数,定义核函数 MS::DefineKernel()。算法默认使用单位均匀核函数(flat kernel function)
           (3) msIP::Filter(spatialBW, rangeBW, speedUpLevel) 处理
           其中speedUpLevel为速度等级,值为 NONE, MEDIUM, HIGH。
           内部流程为:
           a.根据speedUpLevel分别调用NewNonOptimizedFilter(), NewOptimizedFilter1(),   NewOptimizedFilter2()进行meanshift迭代计算,NONE速度最慢,但精度最高;HIGH反之。具体区别将在以后说明。
           b.Connect() 对每个像素进行模式标注
           (4) msIP::GetResults(filtImage) 获取粗分割后的图像, filtImage必须预先分配内存
           (5) msIP::FuseRegions(spatialBW, miniRegion) 根据设定的分割最小区域合并
           它包括区域邻接矩阵RAM建立、传递闭包搜索和小区域剔除。此过程较为复杂,且不属于mean shift本身,将在后续作详细分析。
           (6) msIP::GetResults(segmImage) 获取合并区域后的最终结果, segmImage必须预先分配内存
           (7)      RegionList *regionList = msIP::GetBoundaries() //获取以区域边界点为存储对象的区域数组
                     int *regionIndeces = regionList->GetRegionIndeces(0);
                      int numRegions = regionList->GetNumRegions();    //获取区域总数
                      numBoundaries_ = 0;
                       for(int i = 0; i < numRegions; i++)
                      numBoundaries_ += regionList->GetRegionCount(i); //获取边界点总数
                      boundaries_ = new int [numBoundaries_];
                      for(i = 0; i < numBoundaries_; i++)
                       boundaries_[i] = regionIndeces[i]; //赋予边界点在原始图像数据的索引值
           (8) 存储分割后数据,数据指针为segmImage
           (9) 存储粗分割数据,数据指针为filtImage
           (10) 存储带边界的分割数据,须在segmImage上将所有boundaries_[i]设置为边界颜色。

    二、迭代核

           设图像数据长度为L,通道数为3(LUV格式存储),数据指针为data,空间窗为sigmaS,特征空间窗为sigmaR。以无加速(NO_SPEEDUP)设置下的NewNonOptimizedFilter()说明edsion迭代原理。

           非参数核方法的关键为窗的选取以及窗内点选取的代码实现。如果采用常规方法,那么需要首先提取当前点迭代P所在窗以及其邻接四个窗内的所有点,然后比较每个点和P的特征分量距离是否在特征空间窗内。这个过程中的比较次数为O(L*I*sigmaS*sigmaS),I为每个数据点的平均迭代次数,和图像特征有关。同时,迭代过程需要频繁进行数据指针移动和边界检查,很容易造成计算错误。

           edison采用了一种3维桶缓存(3d buckets[x,y,L])来替换搜索,其过程如下:
           (1)分别对每个数据点在空间域(x,y)和特征空间域(L,u,v)加窗,装入数据缓存sdata
           for(i=0; i<L; i++)
           {
               sdata[idxs++] = (i%width)/sigmaS;
                 sdata[idxs++] = (i/width)/sigmaS;
                sdata[idxs++] = data[idxd++]/sigmaR;
                sdata[idxs++] = data[idxd++]/sigmaR;
                sdata[idxs++] = data[idxd++]/sigmaR;
           }
           (2)计算sdata在(x,y,L)3个分量下的尺度,构造3维数组作为桶缓存,并初始化
           int nBuck1, nBuck2, nBuck3;
           int cBuck1, cBuck2, cBuck3, cBuck;
           nBuck1 = (int) (sMaxs[0] + 3);   // sMaxs[0]为x分量最大值,最小值为0
           nBuck2 = (int) (sMaxs[1] + 3);   // sMaxs[1]为y分量最大值,最小值为0
           nBuck3 = (int) (sMaxs[2] - sMins + 3);   // sMaxs[2],sMins为L分量极值
           buckets = new int[nBuck1*nBuck2*nBuck3];
           for(i=0; i<(nBuck1*nBuck2*nBuck3); i++)
           buckets[i] = -1;
           (3)根据每个点(x,y,L)值,计算其在buckets中的对应位置,然后将点坐标装入slist中
           int* slist = new int[L];
           int idxs = 0;
           for(i=0; i<L; i++)
           {
                 cBuck1 = (int) sdata[idxs] + 1;
                 cBuck2 = (int) sdata[idxs+1] + 1;
                 cBuck3 = (int) (sdata[idxs+2] - sMins) + 1;
                 cBuck = cBuck1 + nBuck1*(cBuck2 + nBuck2*cBuck3);// 3维数组坐标

                 slist[i] = buckets[cBuck];
                 buckets[cBuck] = i;

                 idxs += lN;
           }
           可以看到,此操作完成后,buckets[x,y,L]存储了所有值为(x,y,L)的点空间坐标最大值loc,若loc_next=slist[loc]不为-1,则表示了下一个值为(x,y,L)的点。因此,通过不断访问loc_next,就能找到(x,y,L)在窗sigmaS*sigmaS*sigmaR下的所有邻接点。buckets和slist构造完成后,就可以进行迭代运算了。
           buckets有点在于完全避免了O(L*I*sigmaS*sigmaS)的比较运算以及其带来的大量指针移动和边界检查运算。它的代价在于nBuck1*nBuck2*nBuck3+L的内存开销。其缺陷是由于buckets是根据各分量尺度构造的,要求sigmaS和sigmaR不变,故无法推广到自适应变带宽mean shift算法中。
           (4)迭代过程按照标准mean shift算法完成,可以根据文献直接分析,这里不做阐述。值得注意的是:
           double hiLTr = 80.0/sigmaR;
           是高L值像素的阈值,即当值大于hiLTr时,误差倍数按乘4计算

           NONE,MEDIUM,HIGH的区别
           (1) MEDIUM_SPEEDUP模式
           设P为当前点,每次迭代后获得meanshift向量Mh,将窗口移动到点P1=P+Mh后,并不立即进行迭代。而是计算P1[x,y]与sdata[x,y]在特征空间的差值。当差值小于阈值TC_DIST_FACTOR,按下列规则快速分配模式:
           a.若sdata[x,y]已分配某一模式,则将P1标记为此模式;
           b.否则,记录存在从P到sdata的移动路径至pointList,继续迭代至收敛。然后将pointList上的所有点赋予同一模式。
           代码如下,modeTable为模式标志数组,0表示未分配模式,且无meanshift路径经过,1表示已分配模式,2表示有meanshift路径经过。
           if (diff < TC_DIST_FACTOR)
           {
           if (modeTable[modeCandidate_i] == 0)
           {
               pointList[pointCount++]   = modeCandidate_i; //加入至路径链表
               modeTable[modeCandidate_i] = 2; //标记有路径经过
           }
           else
           {
               for (j = 0; j < N; j++)
                   yk[j+2] = msRawData[modeCandidate_i*N+j];
               modeTable[i] = 1; //标记已分配模式
               mvAbs = -1;
               break;
           }
       }
           MEDIUM_SPEEDUP模式速度性能与TC_DIST_FACTOR设置有关。TC_DIST_FACTOR过小,性能提升不太,过大则可能造成大量计算错误。

           (2) HIGH_SPEEDUP模式
           HIGH_SPEEDUP在MEDIUM_SPEEDUP模式下对运算进行了进一步精简:
           在迭代过程中,若P和它邻域内某点Pn的5维差值小于阈值speedThreshold,则直接将Pn加入移动路径pointList。显然,HIGH模式能够更快速的实现收敛,但也会获得大量的错数据。
           if (diff < speedThreshold)
           {
                 if(modeTable[idxd] == 0)
                 {
                      pointList[pointCount++]   = idxd;
                       modeTable[idxd]   = 2;
                }
           }

           迭代结束后,数据存储于LUV_data数组中。edison调用Connect()函数对各个像素进行模式标注,同时完成对各个模式的计数。Connect()将调用Fill()通过简单的非递归泛洪完成标注。

    三、区域合并

           区域合并包括相似的邻接区域合并和小区域剔除两个过程。它们的算法核心内容均是对区域邻接矩阵进行传递闭包迭代运算。因此,这里仅分析邻接区域合并。

           1. 区域邻接矩阵(Region Adjacency Matrix, RAM)建立,函数为BuildRAM()
           RAM实际上为一区域链表数组:
           RAList *raList = new RAList [regionCount];   //regionCount为区域总数
           它的每个元素raList[i]均为区域链表,RAList数据成员如下:
           int   label;   //本区域标识
           float   edgeStrength;   //边界强度,须由用户定义,一般不用
           int   edgePixelCount;   //边界点计数
           RAList   *next;   //指向下一个邻接区域的指针
           RAM建立好后,raList[i]的所有邻接区域均按label的大小顺序链接起来。所以RAM可以被看成一个稀疏矩阵的数据结构。RAM中的所有元素均分配于raPool中:
           RAList *raPool = new RAList [NODE_MULTIPLE*regionCount];
           NODE_MULTIPLE=10,表示单个区域的最大邻域数。
           查找规则为:
           a.设当前点P区域标识为i,检查P的右边节点Pr,设其标识为j,若Pr和P的标识不同。则从raPool取出两个节点raNode1,raNode2,分别赋予标识i,j。将raNode2,raNode1分别插入raList[i]和raList[j]中。插入操作将调用RAList::Insert(),与一般的链表插入机制相同。
           b.检查P的下方节点Pb,与Pr类似。

           2.传递闭包迭代
           由函数TransitiveClosure()完成,实际上BuildRAM()也是在TransitiveClosure内调用的。
    TransitiveClosure实现过程如下:
           a.检查raList[i]的每个邻近区域,若它们差异小于某阈值,则将较大的标识用较小的代替。
           for(i = 0; i < regionCount; i++)
           {
                 neighbor = raList[i].next;
                 while(neighbor)   
                 {
                   if((InWindow(i, neighbor->label)))
                         {
                             iCanEl = i;
                             while(raList[iCanEl].label != iCanEl)
                                  iCanEl = raList[iCanEl].label;

                            neighCanEl   = neighbor->label;
                            while(raList[neighCanEl].label != neighCanEl)
                                     neighCanEl   = raList[neighCanEl].label;

                          if(iCanEl < neighCanEl)
                                  raList[neighCanEl].label   = iCanEl;
                            else
                                   raList[iCanEl].label = neighCanEl;
                     }
                      neighbor = neighbor->next;
                 }
           }
           InWindow(i, neighbor->label)比较两个区域是否可以合并,阈值为0.25。
           iCanEl的含义是canonical element(正则节点?),即raList[i]的i值与其label相等的节点。BuildRAM()后,raList[i]与raList[i].label是相等的。但一些raList[i]可能会在此步骤中被赋予邻域的标识labeln(labeln一定比raList[i].label小),以后的邻接区域标识必须要保证用最小的同类标识labeln,而不是raList[i].label来代替。
           这步也就是所谓传递闭包运算的意义:如果把所有区域看作总集S,InWindow(i, neighbor->label)看成定义在S->S上的关系运算,传递闭包运算即是通过raList[iCanEl].label != iCanEl找出S中所有满足同类区域。

           b.标识最小化
           for(i = 0; i < regionCount; i++)
            {
                iCanEl   = i;
               while(raList[iCanEl].label != iCanEl)
               iCanEl   = raList[iCanEl].label;
               raList[i].label   = iCanEl;
           }
           a步骤已经完全可以保证表示最小,此步没有必要

           c.区域重新计数,并重新计算模式
           这步属于比较简单的计数和均值运算,不做分析。

           至此便基本完成了对图像的分割运算,我们可以通过后续处理进行模式间的边界标注。

    四、边界标注

           GetBoundaries()函数可以获取图像边界,它将调用DefineBoundaries()定义边界。边界点将存储在boundaryMap数组中:
           boundaryMap = new int [L];
           若boudaryMap[i]!=-1,则i为边界,且boudaryMap[i]为i所在区域的标识。
           boundaryCount = new int [regionCount];
           boundaryCount[i]为第i个区域的边界点数;totalBoundaryCount为总边界点计数。

           设labels为记录每个点所在区域标识的数组,则边界点按如下方式定义:
           a.图像第一行和第一列所有点被标为边界,
           b.若i点与它某个四邻域点区域标识不同,则记为边界,
           dataPoint = i*width+j;
           label = labels[dataPoint];
           if(   (label != labels[dataPoint-1]) || (label != labels[dataPoint+1])||
                  (label != labels[dataPoint-width]) || (label != labels[dataPoint+width]))
           {
                  boundaryMap[dataPoint] = label = labels[dataPoint];
                    boundaryCount[label]++;
                  totalBoundaryCount++;
           }
           c.将图像最后一行和最后一列记为边界。

           boundaryMap含有大量无用数据,下一步将用更紧凑的数据结构存储边界:
           int *boundaryBuffer = new int [totalBoundaryCount];
           int *boundaryIndex = new int [regionCount];
           int counter = 0;
           for(i = 0; i < regionCount; i++)
           {
                  boundaryIndex[i] = counter;
                  counter   += boundaryCount[i];
           }
           for(i = 0; i < L; i++)
           {
                  if((label = boundaryMap[i]) >= 0)
                  {
                         boundaryBuffer[boundaryIndex[label]] = i;
                         boundaryIndex[label]++;
                  }
           }
           与boundaryMap相比,boundaryBuffer能够连续存储边界点,各区域边界在数组中的地址偏移量由boundaryIndex[label]指定。

           DefineBoundaries()返回的区域链表regionList在最后生成,它将调用RegionList::AddRegion()函数。AddRegion的3个形参的含义分别为:
           int label   //区域标识
           int pointCount   //区域边界点总数
           int *indeces   //边界点在boundaryBuffer中的地址偏移量
           添加方法如下:
           counter   = 0;
           for(i = 0; i < regionCount; i++)
           {
                  regionList->AddRegion(i, boundaryCount[i], &boundaryBuffer[counter]);
                  counter += boundaryCount[i];
           }
           AddRegion将按如下方式修改regionList:
           regionList[i].label = label;
           regionList[i].pointCount = pointCount;
           regionList[i].region = freeBlockLoc;
           for(int k = 0; k < pointCount; k++)
           indexTable[freeBlockLoc+i] = indeces[i];
           freeBlockLoc += pointCount;
           indexTable为边界点位置索引表,freeBlockLoc指示了表中第一个未使用索引。

           有了boundaryBuffer和boundaryCount之后,边界的标注就简单了:
           int *regionIndeces = regionList->GetRegionIndeces(0);
           //获取indexTable中第一个点地址
           int numRegions = regionList->GetNumRegions();   //获取区域数
           numBoundaries_ = 0;
           for(int i = 0; i < numRegions; i++)
           {
                //获取边界点总数
               numBoundaries_ += regionList->GetRegionCount(i);
       }
          boundaries_ = new int [numBoundaries_];
       for(i = 0; i < numBoundaries_; i++)
       {
              //获取所有边界点索引
               boundaries_[i] = regionIndeces[i];
       }


    展开全文
  • meanshift

    2018-07-22 21:18:40
     meanshift聚类方法又称为均值漂移聚类。均值漂移聚类是基于滑动窗口的算法,来找到数据点的密集区域。通过将中心点的候选点更新为滑动窗口内点的均值来完成,来定位每个簇的中心点。然后对这些候选窗口进行相似...

    先贴出我借鉴的博客

    1. https://blog.csdn.net/Katherine_hsr/article/details/79382249

           meanshift聚类方法又称为均值漂移聚类。均值漂移聚类是基于滑动窗口的算法,来找到数据点的密集区域。通过将中心点的候选点更新为滑动窗口内点的均值来完成,来定位每个簇的中心点。然后对这些候选窗口进行相似窗口进行去除,最终形成中心点集及相应的分组。

    以选取一个簇为例,具体步骤如下:

    1. 确定滑动窗口半径r,以随机选取的样本为中心点半径为r的圆形滑动窗口开始滑动。在每一次迭代中向密度更高的区域移动,直到收敛。 
    2. 每一次滑动到新的区域,计算滑动窗口内的均值来作为中心点,滑动窗口内的点的数量为窗口内的密度。在每一次移动中,窗口会向密度更高的区域移动。 
    3. 移动窗口,计算窗口内的中心点以及窗口内的密度,知道没有方向在窗口内可以容纳更多的点,即一直移动到圆内密度不再增加为止。 
    4. 步骤一到三会产生很多个滑动窗口,当多个滑动窗口重叠时,保留包含最多点的窗口,然后根据数据点所在的滑动窗口进行聚类。 

    优点:

    1. 不同于K-Means算法,均值漂移聚类算法不需要我们知道有多少簇。 
    2. 基于密度的算法相比于K-Means受均值影响较小。 

    缺点:

    1. 窗口半径r的选择可能是不重要的。
    展开全文
  • Meanshift

    2016-04-30 23:26:37
    编译环境VC6.0 #include "cv.h" #include "highgui.h" #include #include IplImage *image = 0, *hsv = 0, *hue = 0, *mask = 0, *backproject = 0, *histimg = 0;//用HSV中的Hue分量进行跟踪 ...

    编译环境VC6.0

    #include "cv.h"
    #include "highgui.h"
    #include <stdio.h>
    #include <ctype.h>
    IplImage *image = 0, *hsv = 0, *hue = 0, *mask = 0, *backproject = 0, *histimg = 0;//用HSV中的Hue分量进行跟踪
    CvHistogram *hist = 0;//直方图类
    int backproject_mode = 0;
    int select_object = 0;
    int track_object = 0;
    int show_hist = 1;
    CvPoint origin;
    CvRect selection;
    CvRect track_window;
    CvBox2D track_box; // Meanshift跟踪算法返回的Box类
    CvConnectedComp track_comp;
    int hdims = 50; // 划分直方图bins的个数,越多越精确
    float hranges_arr[] = {0,180};//像素值的范围
    float* hranges = hranges_arr;//用于初始化CvHistogram类
    int vmin = 10, vmax = 256, smin = 30;
    void on_mouse( int event, int x, int y, int flags,void *NotUsed)//该函数用于选择跟踪目标
    {
          if( !image )
             return;
         if( image->origin )
             y = image->height - y;
         if( select_object )//如果处于选择跟踪物体阶段,则对selection用当前的鼠标位置进行设置
         {
             selection.x = MIN(x,origin.x);
             selection.y = MIN(y,origin.y);
             selection.width = selection.x + CV_IABS(x - origin.x);
             selection.height = selection.y + CV_IABS(y - origin.y);
             selection.x = MAX( selection.x, 0 );
             selection.y = MAX( selection.y, 0 );
             selection.width = MIN( selection.width, image->width );
             selection.height = MIN( selection.height, image->height );
             selection.width -= selection.x;
             selection.height -= selection.y;
          }
          switch( event )
          {
                case CV_EVENT_LBUTTONDOWN://开始点击选择跟踪物体
                       origin = cvPoint(x,y);
                       selection = cvRect(x,y,0,0);//坐标
                       select_object = 1;//表明开始进行选取
                break;
               case CV_EVENT_LBUTTONUP:
                       select_object = 0;//选取完成
                       if( selection.width > 0 && selection.height > 0 )
                           track_object = -1;//如果选择物体有效,则打开跟踪功能
               break;
          }
    }
    
    CvScalar hsv2rgb( float hue )//用于将Hue量转换成RGB量
    {
        int rgb[3], p, sector;
        static const int sector_data[][3]={{0,2,1}, {1,2,0}, {1,0,2}, {2,0,1}, {2,1,0}, {0,1,2}};
        hue *= 0.033333333333333333333333333333333f;
        sector = cvFloor(hue);
        p = cvRound(255*(hue - sector));
        p ^= sector & 1 ? 255 : 0;
        rgb[sector_data[sector][0]] = 255;
        rgb[sector_data[sector][1]] = 0;
        rgb[sector_data[sector][2]] = p;
        return cvScalar(rgb[2], rgb[1], rgb[0],0);//返回对应的颜色值
    }
    int main( int argc, char** argv )
    {
        CvCapture* capture = 0;
        IplImage* frame = 0;
        if( argc == 1 || (argc == 2 && strlen(argv[1]) == 1 && isdigit(argv[1][0])))
             capture = cvCaptureFromCAM( argc == 2 ? argv[1][0] - '0' : 0 );//打开摄像头
        else if( argc == 2 )
             capture = cvCaptureFromAVI( argv[1] );//打开AVI文件
        if( !capture )
        {
            fprintf(stderr,"Could not initialize capturing.../n");//打开视频流失败处理
            return -1;
         }
        printf( "Hot keys: /n/tESC - quit the program/n/tc - stop the tracking/n/tb - switch to/from backprojection view/n/th - show/hide object histogram/nTo initialize tracking, select the object with mouse/n" );//打印出程序功能列表
        cvNamedWindow( "CamShiftDemo", 1 );//建立视频窗口
        cvSetMouseCallback( "CamShiftDemo", on_mouse ); // 设置鼠标回调函数
        cvCreateTrackbar( "Vmin", "CamShiftDemo", &vmin, 256, 0 );//建立滑动条
        cvCreateTrackbar( "Vmax", "CamShiftDemo", &vmax, 256, 0 );
        cvCreateTrackbar( "Smin", "CamShiftDemo", &smin, 256, 0 );
        for(;;)//进入视频帧处理主循环
       {
           int i, bin_w, c;
           frame = cvQueryFrame( capture );
           if( !frame )
                   break;
          if( !image )//刚开始先建立一些缓冲区
          {
              image = cvCreateImage( cvGetSize(frame), 8, 3 );//
              image->origin = frame->origin;
              hsv = cvCreateImage( cvGetSize(frame), 8, 3 );
              hue = cvCreateImage( cvGetSize(frame), 8, 1 );
              mask = cvCreateImage( cvGetSize(frame), 8, 1 );//分配掩膜图像空间
              backproject = cvCreateImage( cvGetSize(frame), 8, 1 );//分配反向投影图空间,大小一样,单通道
              hist = cvCreateHist( 1, &hdims, CV_HIST_ARRAY, &hranges, 1 ); //分配建立直方图空间
              histimg = cvCreateImage( cvSize(320,200), 8, 3 );//分配用于画直方图的空间
             cvZero( histimg );//背景为黑色
           }
           cvCopy( frame, image, 0 );
           cvCvtColor( image, hsv, CV_BGR2HSV ); // 把图像从RGB表色系转为HSV表色系
           if( track_object )//   如果当前有需要跟踪的物体   
          {
                 int _vmin = vmin, _vmax = vmax;
                 cvInRangeS( hsv, cvScalar(0,smin,MIN(_vmin,_vmax),0),cvScalar(180,256,MAX(_vmin,_vmax),0), mask ); //制作掩膜板,只处理像素值为H:0~180,S:smin~256,V:vmin~vmax之间的部分
                 cvSplit( hsv, hue, 0, 0, 0 ); // 取得H分量
                 if( track_object < 0 )//如果需要跟踪的物体还没有进行属性提取,则进行选取框类的图像属性提取
                 {
                        float max_val = 0.f;
                       cvSetImageROI( hue, selection ); // 设置原选择框
                       cvSetImageROI( mask, selection ); // 设置Mask的选择框
                       cvCalcHist( &hue, hist, 0, mask ); // 得到选择框内且满足掩膜板内的直方图
                       cvGetMinMaxHistValue( hist, 0, &max_val, 0, 0 ); 
                       cvConvertScale( hist->bins, hist->bins, max_val ? 255. / max_val : 0., 0 ); // 对直方图转为0~255
                       cvResetImageROI( hue ); // remove ROI
                       cvResetImageROI( mask );
                       track_window = selection;
                       track_object = 1;
                      cvZero( histimg );
                      bin_w = histimg->width / hdims;
                      for( i = 0; i < hdims; i++ )
                      {
                          int val = cvRound( 
                          cvGetReal1D(hist->bins,i)*histimg->height/255 );
                          CvScalar color = hsv2rgb(i*180.f/hdims);
                          cvRectangle( histimg, cvPoint(i*bin_w,histimg->height),
                          cvPoint((i+1)*bin_w,histimg->height - val),color, -1, 8, 0 );//画直方图到图像空间
                      }
            }
             cvCalcBackProject( &hue, backproject, hist ); // 得到hue的反向投影图
             cvAnd( backproject, mask, backproject, 0 );//得到反向投影图mask内的内容
             cvCamShift( backproject, track_window,cvTermCriteria( CV_TERMCRIT_EPS | CV_TERMCRIT_ITER, 10, 1 ),&track_comp, &track_box );//使用MeanShift算法对backproject中的内容进行搜索,返回跟踪结果
             track_window = track_comp.rect;//得到跟踪结果的矩形框
             if( backproject_mode )
                    cvCvtColor( backproject, image, CV_GRAY2BGR ); // 显示模式
             if( image->origin )
             track_box.angle = -track_box.angle;
            cvEllipseBox( image, track_box, CV_RGB(255,0,0), 3, CV_AA, 0 );//画出跟踪结果的位置
       }
      if( select_object && selection.width > 0 && selection.height > 0 )//如果正处于物体选择,画出选择框
      {
           cvSetImageROI( image, selection );
           cvXorS( image, cvScalarAll(255), image, 0 );
          cvResetImageROI( image );
      }
      cvShowImage( "CamShiftDemo", image );//显示视频和直方图
      cvShowImage( "Histogram", histimg );
      c = cvWaitKey(10);
      if( c == 27 )
          break;
      switch( c )
      {
         case 'b':
               backproject_mode ^= 1;
               break;
         case 'c':
               track_object = 0;
               cvZero( histimg );
               break;
        case 'h':
              show_hist ^= 1;
              if( !show_hist )
                    cvDestroyWindow( "Histogram" );
             else
                   cvNamedWindow( "Histogram", 1 );
             break;
        default:
               ;
          }
       }
       cvReleaseCapture( &capture );
       cvDestroyWindow("CamShiftDemo");
        return 0;
    }


    展开全文
  • meanShift

    千次阅读 2013-12-22 13:54:05
    Finds an object on a back projection image. ...C++: int meanShift(InputArray probImage, Rect& window, TermCriteria criteria) Python: cv2.meanShift(probImage, window, criteria) → retval, window
  • Mean shift

    2017-10-29 15:19:00
    转载:... 然后引入opencv中的pyrMeanShiftFiltering函数: pyrMeanShiftFiltering函数 对图像进行:均值偏移滤波 调用格式: void cvPyrMeanShiftFiltering( const CvArr* src, CvA...
  • 针对Mean Shift算法固定搜索核窗口存在局限性的问题,提出了一种基于边缘特性的Mean Shift搜索核半径自动调节的运动目标跟踪方法。在视频序列图像中,当目标远离、靠近摄像机时,会发生尺寸变小、变大的变化,导致...
  • meanshift算法学习笔记

    2013-01-06 12:01:58
    meanshift算法思想其实很简单:利用概率密度的梯度爬升来寻找局部最优。它要做的就是输入一个在图像的范围,然后一直迭代(朝着重心迭代)直到满足你的要求为止。但是他是怎么用于做图像跟踪的呢?这是我自从学习...
  • meanshift图像分割代码

    热门讨论 2013-05-30 15:16:33
    本代码利用meanshift的方法进行图像分割和边缘检测。代码1在m.main里可以直接运行(图片已经存放在相应目录下),代码2注意一下图片文件路径即可。代码1是利用rgb三个维度进行meanshift分割,代码2利用luv三个维度...
  • Meanshift,聚类算法入门讲解 Mean Shift算法,一般是指一个迭代的步骤,即先算出当前点的偏移均值,移动该点到其偏移均值,然后以此为新的起始点,继续移动,直到满足一定的条件结束. 1. Meanshift推导 给定d维空间Rd的n...
  • 传统MeanShift目标跟踪算法通过bin-bin颜色直方图表示目标特征,直方图中往往会混入背景颜色信息,造成跟踪不准确;同时由于MeanShift算法具有局部最优性,当目标受到严重遮挡丢失后,不能对目标重新定位跟踪。为了...
  • Meanshift 应用

    2009-04-27 01:10:41
    这是Meanshift 的一个简单应用,可以脱离复杂理论的限制,很容易理解。
  • meanshift kalman

    2009-12-27 17:36:01
    meanshift kalman 相结合实现跟踪的代码,很好用
  • MeanShift源码

    2015-05-10 12:26:15
    一个经典的采用java实现的Meanshift图像分割算法。
  • Meanshift C++

    2016-06-01 19:13:37
    Meanshift目标跟踪算法,VS2013环境下直接运行
  • Meanshift简介

    2010-03-11 15:45:21
    Meanshift 算法简介 主要介绍了meanshift算法的原理
  • 均值漂移(Meanshift)算法

    万次阅读 多人点赞 2017-01-16 21:12:29
    均值漂移(Meanshift) 1.均值漂移的基本概念:沿着密度上升方向寻找聚簇点 设想在一个有N个样本点的特征空间 初始确定一个中心点center,计算在设置的半径为D的圆形空间内所有的点(xi)与中心点center的向量 计算...

空空如也

1 2 3 4 5 ... 20
收藏数 1,889
精华内容 755
热门标签
关键字:

meanshift