SLIC算法

SLIC算法是simplelineariterativecluster的简称，该算法用来生成超像素（superpixel）。SLIC的思想是将彩色图像转化为CIELAB颜色空间和XY坐标下的5维特征向量（Lab模式也是由三个通道组成，第一个通道是明度，即“L”。a通道的颜色是从红色到深绿；b通道则是从蓝色到黄色。），然后对5维特征向量构造度量标准，对图像像素进行局部聚类的过程。该算法速度较快，能生成紧凑、近似均匀的超像素。1、SLIC超像素分割的步骤[java]viewplaincopyfunction[sp_img,disp_img]=DemoSLICSuperpixel(img,K,M)%img:originalrgbimage%K:numberofsuperpixel超像素的个数%M:compactnessofsuperpixel紧凑性tic;[X,Y,L,A,B,Lab_img,STEP]=GetLABXYSeeds(img,K);%初始化种子点并提取种子的XYLab特征EdgeMap=DetectLabEdges(Lab_img);%为了避免边缘位置的干扰，还要考虑边缘剩余[X,Y,L,A,B]=PeturbSeeds(EdgeMap,Lab_img,X,Y,L,A,B);%产生新的XYLab种子labels=PerformSLICSuperpixel(X,Y,L,A,B,Lab_img,STEP,M);%spanstyle=font-family:Arial,Helvetica,sans-serif;根据元素与种子点的相似度关系进行聚类，并添加标签/spansp_img=EnforceLabelConnectivity(labels,K);%合并较小的聚类disp_img=DrawContour(img,sp_img);%超像素边界2、初始化种子点并提取XYLab特征输入m*n的图像，将图像分成k'个超像素。则：每个超像素的大小为：size=m*n/ksize：面积超像素大小一样？两个种子点的距离为：step=sqrt（size）每个超像素在x方向上的像素个数为m/setp每个超像素在x方向上的像素个数为n/setp为了避免边缘位置的干扰，还要考虑边缘剩余3、产生新的XYLab种子为了避免种子点处理图像的边缘位置，对以后的聚类工程造成干扰，需要将种子点以它为中心的3*3的窗口内移动到梯度最小的位置，产生新的种子点计算这K个超像素里所有像素点的平均向量值，重新得到K个聚类中心，4、根据像素之间的相似度进行聚类对每个像素点，分别计算与之距离最近的种子点之间的相似程度，将最相似种子点的标签赋给该像素。通过不断迭代该过程，直到收敛(在程序中迭代了十次)相似度的衡量关系如下？程序中，其其中，第一项为像素点间的颜色差异，第二项为像素点间的空间距离，第三项为两个像素的想速度。S为种子点的距离，m为平衡参数，用来衡量颜色值和空间信息在相似度衡量中的比重1.0/(double(STEP)/M)^2;以下内容是上面的C详细版，大概看划线的就行基本思想算法大致思想是这样的，将图像从RGB颜色空间转换到CIE-Lab颜色空间，对应每个像素的（L，a，b）颜色值和（x，y）坐标组成一个5维向量V[L,a,b,x,y],两个像素的相似性即可由它们的向量距离来度量，距离越大，相似性越小。算法首先生成K个种子点，然后在每个种子点的周围空间里搜索距离该种子点最近的若干像素，将他们归为与该种子点一类，直到所有像素点都归类完毕。然后计算这K个超像素里所有像素点的平均向量值，重新得到K个聚类中心，然后再以这K个中心去搜索其周围与其最为相似的若干像素，所有像素都归类完后重新得到K个超像素，更新聚类中心，再次迭代，如此反复直到收敛。怎么样，是不是感觉很像K-means聚类算法。该算法接受一个参数K，用于指定生成的超像素数目。设原图有N个像素，则分割后每块超像素大致有N/K个像素，每块超像素的边长大致为S=[N/K]^0.5，开始我们每隔S个像素取一个聚类中心，然后以这个聚类中心的周围2S*2S为其搜索空间，与其最为相似的若干点即在此空间中搜寻。算法可能遇到的问题及解决办法：1、为了避免所选的聚类中心是边缘和噪声这样的不合理点，算法做了改进，在3*3的窗口中将聚类中心移动到梯度最小的区域,梯度定义为G(x,y)=[V(x+1,y)-V(x-1,y)]^2+[V(x,y+1)-V(x,y-1)]^2这样就可以避免上面所说的情况。2、L,a,b的大小有限制，而图像尺寸则没有限制，如果图片的尺寸比较大，会造成衡量向量距离时空间距离（x，y）的影响过大，需要调制空间距离（x，y）的影响，所以需要对x，y进行normalize。改进向量距离的度量如下：d_lab=[(Lk-Li)^2+(ak-ai)^2+(bk-bi)^2]^0.5d_xy=[(Xi-Xk)^2+(Yk-Yi)^2]^0.5Ds=d_lab+(m/S)*d_xym用来调整d_xy的权值，一般为1-20，在算法中设置为10。3、最后可能出现一些小的区域d被标记为归属某一块超像素但却与这块超像素没有连接，需要把这块小区域d重新归类为与这块小区域d连接的最大的超像素中去，以保证每块超像素的完整。算法流程1.主程序入口下面的程序就是超像素生成的函数入口：slic.DoSuperpixelSegmentation_ForGivenNumberOfSuperpixels(img,width,height,labels,numlabels,m_spcount,m_compactness);这里有几个特别的参数需要说明：slic：SLICslic;是一个SLIC类labels：int*labels=newint[sz];一张标签图，和图像大小一致，用于标记每个像素的标签值；sz=width*height，即一张图像的像素总数。numlabels：intnumlabels(0);是图像最终分成的类数，即最终生成的超像素个数，在这里被初始化为0。m_spcount:是客户从界面输入的值，即初始化的种子个数，但是SLIC算法中不一定每个种子最终都能得一个超像素，由于某些因素可能被其他超像素合并。若种子数不符合规定，则通过（总像素值SZ）/（每个超像素默认大小200）获得种子数：if(m_spcount20||m_spcountsz/4)m_spcount=sz/200;m_compactness:if(m_compactness1.0||m_compactness80.0)m_compactness=20.0;这个值也是有用户设定的，是颜色特征和XY坐标特征之间的紧密度比例，20这个值效果往往不错。该函数的定义：voidSLIC::DoSuperpixelSegmentation_ForGivenNumberOfSuperpixels(unsignedint*ubuff,//imgconstintwidth,constintheight,int*&klabels,//labelsint&numlabels,//constint&K,//初始化的种子数m_spcountconstdouble&compactnes)//m_compactness空间参数转换的权重值{constintsuperpixelsize=0.5+double(width*height)/double(K);DoSuperpixelSegmentation_ForGivenSuperpixelSize(ubuff,width,height,klabels,numlabels,superpixelsize,compactness);}superpixelsize：超像素的大小，即每个超像素中包含的像素值DoSuperpixelSegmentation_ForGivenSuperpixelSize函数中完成了超像素生成的功能constintSTEP=sqrt(double(superpixelsize))+0.5;这个变量很关键，是种子点的跨度。2.子程序流程在DoSuperpixelSegmentation_ForGivenSuperpixelSize函数中主要包含以下函数：DoRGBtoLABConversion(ubuff,m_lvec,m_avec,m_bvec);将RGB图像转换为LAB图像。GetLABXYSeeds_ForGivenStepSize(kseedsl,kseedsa,kseedsb,kseedsx,kseedsy,STEP,perturbseeds,edgemag);均匀分布种子点，将种子点的5维特征值LABXY作为分类的中心点特征值存入kseeds向量中。PerformSuperpixelSLIC(kseedsl,kseedsa,kseedsb,kseedsx,kseedsy,klabels,STEP,edgemag,compactness);对整张图像进行局部的K-Means聚类，生成超像素。这是超像素生成的关键步骤，也耗时最多。EnforceLabelConnectivity(klabels,m_width,m_height,nlabels,numlabels,double(sz)/double(STEP*STEP));对生成的初步超像素图像，进行合并孤立超像素，某些孤点像素与大小过小的超像素被合并到附近的超像素中。3.关键程序解析：这里只讲PerformSuperpixelSLIC与EnforceLabelConnectivityPerformSuperpixelSLIC：（1）核心就是局部的K-Means聚类局部顾名思义，就是只对种子点附近的像素进行聚类，这里种子是按照STEP=S的跨度分布的，稍微扩大一点聚类范围，选为边长为2S矩形。（2）特征值计算上面即像素到种子点的“距离”计算，距离中包括了LABXY5个特征值。方法就是，在局部区域内对每个像素点求其到中心的距离，若小于以前存放的距离，则将距离更新，且更新该像素点的类别标签。（3）种子点特征值更新上部分程序，将超像素中的特征值加在一起。上部分程序将各特征值的平均值作为中心点的特征值。整个KMeans聚类迭代次数为10，即上面的内容重复10次，每次的像素点所属的类都有可能变化。EnforceLabelConnectivity函数定义与说明voidSLIC::EnforceLabelConnectivity(constint*labels,//inputlabelsthatneedtobecorrectedtoremovestraylabelsconstintwidth,constintheight,int*&nlabels,//newlabelsint&numlabels,//thenumberoflabelschangesintheendifsegmentsareremovedconstint&K)//constintdx8[8]={-1,-1,0,1,1,1,0,-1};//constintdy8[8]={0,-1,-1,-1,0,1,1,1};constintdx4[4]={-1,0,1,0};constintdy4[4]={0,-1,0,1};constintsz=width*height;constintSUPSZ=sz/K;//nlabels.resize(sz,-1);for(inti=0;isz;i++)nlabels[i]=-1;intlabel(0);int*xvec=newint[sz];int*yvec=newint[sz];intoindex(0);intadjlabel(0);//adjacentlabelfor(intj=0;jheight;j++){for(intk=0;kwidth;k++){if(0nlabels[oindex]){nlabels[oindex]=label;//-------