SLIC算法.

图像分割算法•图像分割是指把图像分解成各具特性的区域并提取出感兴趣目标的技术和过程，它是计算机视觉领域的一个重要而且基本的问题，分割结果的好坏将直接影响到视觉系统的性能。•图像分割的要求：•a．高分辨率、速度高：图像处理技术发展的最终目标是要实现图像的实时处理，•这在移动目标的生成、识别和跟踪上有着重要意义；•b．立体化：立体化包括的信息量最为丰富和完整，未来采用数字全息技术将有助•于达到这个目的；•c．智能化:其目的是实现图像的智能生成、处理、识别和理解。超像素及其优势：•所谓的“超像素”，就是指许多相似的像素点组合在一起，作为一个整体来处理，这个整体就称之为超像素。像素并不是人类视觉的着重点，因为人类获得图像是从许多的像素点的组合的一个区域而来的，单一的某个像素点并不具有什么意义，只有在组合在一起对人类而言才有意义。•SLIC（简单线性、迭代聚类）算法在由CIELAB色彩空间中的L，a,b值和x,y坐标像素所构成的五维空间中执行一个局部的像素点聚合。一种新的距离度量能够实现超像素形状的紧凑、有规则，并能够无缝隙的包含灰度及彩色图像。SLIC实现起来比较简单,容易在实践中应用——唯一的参数指定所需超像素点的数量。•Lab色彩模型是由亮度（L）和有关色彩的a,b三个要素组成。L表示亮度（Luminosity），L的值域由0（黑色）到100（白色）•SLIC(简单线性迭代聚类)是一种通过利用像素的颜色相似度和图像片面空间对像素进行聚类，从而有效的生成紧凑的几乎统一化的超像素的分割方法。SLIC分割方法使用简单，只需给定需要得到的超像素的数量即可，且运行速度快，只需要线性的运行时间和存储空间。SLIC分割方法生成的超像素具有较好的紧凑性和边界贴合度，超像素大小一致且形状均匀。•我们的方法(SLIC)是在五维空间labxy中来实现的，其中lab为CIELAB色彩空间中的像素颜色矢量，被认为是小颜色距离感知统一，xy是像素点的位置。在CIELAB空间中两种颜色的最大可能距离受到限制，在xy平面上空间距离取决于图像大小。K-means算法：K-Means的算法如下：1.随机在图中取K（这里K=2）个种子点。2.然后对图中的所有点求到这K个种子点的距离，假如点Pi离种子点Si最近，那么Pi属于Si点群。（图中，我们可以看到A，B属于上面的种子点，C，D，E属于下面中部的种子点）3.接下来，我们要移动种子点到属于他的“点群”的中心。（见图上的第三步）4.然后重复第2）和第3）步，直到种子点没有移动，一般迭代十次即可。•clc•clear•%读取图像，预处理•he=imread('1.jpg');%读取图像•cform=makecform('srgb2lab');%图像由RGB转为lab•lab_he=applycform(he,cform);%•lab_he=double(lab_he);%设置初值•color=[255,255,255];•thre=0.02;%最终生成分割图像梯度阈值•m=40;%权值•k=1;%划分为300个簇•die=20;%kmeans迭代die次•x=size(he);s=(x(1)*x(2)/k)^0.5;s=ceil(s);%初始分割网格间距s•r=ceil(x(1)/s);%网格行数r•w=ceil(x(2)/s);%网格列数w•ct=r*w;•belong=ones(x(1),x(2));•center=zeros(ct,5);•%初始每个像素点的距离•dist=9999*ones(x(1),x(2));SLIC算法：•1.初始化种子点（聚类中心）：按照设定的超像素个数，在图像内均匀的分配种子点。•图片总共有N个像素点•预分割为K个相同尺寸的超像素•每个超像素的大小为N/K•相邻种子点的距离（步长）近似为S=sqrt(N/K)•%初始中心节点center•fori=1:r•forj=1:w•if(ir)•x1=(i-1)*s+fix(s/2);•else•x1=(i-1)*s+fix(rem(x(1),s)/2);•end•if(jw)•y1=(j-1)*s+fix(s/2);•else•y1=(j-1)*s+fix(rem(x(2),s)/2);•end•z=lab_he(x1,y1,:);•center((i-1)*w+j,:)=[z(:,:,1)z(:,:,2)z(:,:,3)x1y1];%初始中心节点center•end•end•2.在种子点的3*3邻域内重新选择种子点：•计算该邻域内所有像素点的梯度值•将种子点移到该邻域内梯度最小的地方•避免种子点落在噪声点上•3.在每个种子点周围的邻域内为每个像素点分配类标签：•SLIC的搜索范围限制为2S*2S•加速算法收敛SLIC算法：SLIC算法：•4.距离度量：•颜色距离和空间距离•dc代表颜色距离•ds代表空间距离•%迭代聚类处理•t1=clock;•move=99999;•forc=1:die%进行迭代die次•ifmove10•break;•end•move=0;•c1=zeros(ct);•ct_x=zeros(ct);•ct_y=zeros(ct);•ct_l=zeros(ct);•ct_a=zeros(ct);•ct_b=zeros(ct);•fori=1:ct•foru=center(i,4)-s:center(i,4)+s•if(u=1)&&(u=x(1))•forv=center(i,5)-s:center(i,5)+s•if(v=1)&&(v=x(2))•dc=((lab_he(u,v,1)-center(i,1))^2+(lab_he(u,v,2)-center(i,2))^2+(lab_he(u,v,3)-center(i,3))^2)^0.5;•ds=((u-center(i,4))^2+(v-center(i,5))^2)^0.5;•d=((dc)^2+(ds*m/s)^2)^0.5;%计算距离•ifddist(u,v)•dist(u,v)=d;•belong(u,v)=i;•move=move+1;•end•end•end•end•end•endSLIC算法：•5、移动聚类中心：•即迭代优化•理论上上述步骤不断迭代直到误差收敛（可以理解为每个像素点聚类中心不再发生变化为止），实践发现10次迭代对绝大部分图片都可以得到较理想效果，所以一般迭代次数取10。•6.增强连通性：•不连续的超像素、尺寸过小超像素重新分配给邻近的超像素•求点群中心的算法•1）MinkowskiDistance公式——λ可以随意取值，可以是负数，也可以是正数，或是无穷大。•2）EuclideanDistance公式——也就是第一个公式λ=2的情况•3）CityBlockDistance公式——也就是第一个公式λ=1的情况•这三个公式的求中心点有一些不一样的地方，我们看下图（对于第一个λ在0-1之间）。•K-Means++算法：•K-Means主要有两个最重大的缺陷——都和初始值有关：•K是事先给定的，这个K值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。（ISODATA算法通过类的自动合并和分裂，得到较为合理的类型数目K）•K-Means算法需要用初始随机种子点来搞，不同的随机种子点会有得到完全不同的结果。（K-Means++算法可以用来解决这个问题，其可以有效地选择初始点）•我在这里重点说一下K-Means++算法步骤：•先从我们的数据库随机挑个随机点当“种子点”。•对于每个点，我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))。•然后，再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random-=D(x)，直到其=0，此时的点就是下一个“种子点”。•重复第（2）和第（3）步直到所有的K个种子点都被选出来。•进行K-Means算法。•%去坏点•fori=1:ct•bw=zeros(x(1),x(2));•fork=1:x(1)•forg=1:x(2)•ifbelong(k,g)==i•bw(k,g)=1;•end•end•end•[L,num]=bwlabel(bw,4);%查找连通的点•fork=1:num•[rr,cc]=find(L==k);•c1=size(rr);•ifc1(1)0&&c1(1)100•forg=1:c1(1)•ifrr(1)-1=1•belong(rr(g),cc(g))=belong(rr(1)-1,cc(1));•elseifcc(1)-1=1•belong(rr(g),cc(g))=belong(rr(1),cc(1)-1);•elseifcc(1)+1=x(2)•belong(rr(g),cc(g))=belong(rr(1),cc(1)+1);•elseifrr(1)+1=x(1)•belong(rr(g),cc(g))=belong(rr(1)+1,cc(1));•endif((i-1)=1)&&((j-1)=1)ifbelong(i-1,j-1)~=belong(i,j)hehe(i,j,1)=color(1);hehe(i,j,2)=color(2);hehe(i,j,3)=color(3);b=1;endifbelong(i-1,j)~=belong(i,j)hehe(i,j,1)=color(1);hehe(i,j,2)=color(2);hehe(i,j,3)=color(3);b=1;endifbelong(i,j-1)~=belong(i,j)hehe(i,j,1)=color(1);hehe(i,j,2)=color(2);hehe(i,j,3)=color(3);b=1;endifbelong(i,j+1)~=belong(i,j)hehe(i,j,1)=color(1);hehe(i,j,2)=color(2);hehe(i,j,3)=color(3);b=1;endelseif((i+1)=x(1))&&((j-1)=1)ifbelong(i+1,j-1)~=belong(i,j)hehe(i,j,1)=color(1);hehe(i,j,2)=color(2);hehe(i,j,3)=color(3);b=1;endifbelong(i+1,j)~=belong(i,j)hehe(i,j,1)=color(1);hehe(i,j,2)=color(2);hehe(i,j,3)=color(3);b=1;endelseif((i+1)=x(1))&&((j+1)=x(2))ifbelong(i+1,j+1)~=belong(i,j)hehe(i,j,1)=color(1);hehe(i,j,2)=color(2);hehe(i,j,3)=color(3);b=1;end•%聚类后图像网格显示•hehe=uint8(hehe);•figure(1)•imshow(he),title('原始图像');%显示图像•figure(20)•imshow(hehe),title('SLIC分割k=400,m=40')•etime(t2,t1)K=256K=512SLIC算法的比较与改进：•对于一个480×320的图像来说，SLIC要比TP09快10倍，比NC05快500倍。由b图可知，对于百万像素以上的图片，SLIC的速度要快于GS04。这是因为我们的算法运行复杂度为O(N)而GS04的复杂度为O(NlogN)。这是有趣的因为即使低端数码相机也能产生300万以上的像素。同时，GS04需要5×N的空间来存储边权重和阀值，这与SLIC相反，SLIC需要1×N的空间（存储离族群中心最近的像素点的距离）。•图4(a)：在一幅481×321的图形中，横坐标输入量为超像素