SLIC图像分割算法.pptx
图像分割算法 图像分割是指把图像分解成各具特性的区域图像分割是指把图像分解成各具特性的区域并提取出感兴趣目标的技术和过程，并提取出感兴趣目标的技术和过程， 它是计算机它是计算机视觉领域的一个重要而且基本的问题，视觉领域的一个重要而且基本的问题， 分割结果分割结果的好坏将直接影响到视觉系统的性能。的好坏将直接影响到视觉系统的性能。 图像分割的要求：图像分割的要求： 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）步，直到种子点没步，直到种子点没有移动，一般迭代十有移动，一般迭代十次即可。次即可。clcclear%读取图像，预处理读取图像，预处理he=imread(1.jpg);%读取图像读取图像cform=makecform(srgb2lab);%图像由图像由RGB转为转为lablab_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);%初始分割网格间距初始分割网格间距sr=ceil(x(1)/s);%网格行数网格行数rw=ceil(x(2)/s);%网格列数网格列数wct=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)%初始中心节点初始中心节点centerfor i=1:r for j=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) x1 y1;%初始中心节初始中心节点点center endend 2. 在种子点的在种子点的3*3邻域内重新选择种子邻域内重新选择种子点：点： 计算该邻域内所有像素点的梯度值计算该邻域内所有像素点的梯度值 将种子点移到该邻域内梯度最小的地方将种子点移到该邻域内梯度最小的地方 避免种子点落在噪声点避免种子点落在噪声点上上 3. 在每个种子点周围的邻域内为每个像素在每个种子点周围的邻域内为每个像素点分配类点分配类标签：标签： SLIC的搜索范围限制为的搜索范围限制为2S*2S 加速算法收敛加速算法收敛SLIC算法：算法：SLIC算法：算法： 4. 距离距离度量：度量： 颜色距离和空间距离颜色距离和空间距离 dc代表颜色距离代表颜色距离 ds代表空间距离代表空间距离%迭代聚类处理迭代聚类处理t1=clock;move=99999;for c=1:die %进行迭代进行迭代die次次 if move=1)&(u=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;%计算距离计算距离 if ddist(u,v) dist(u,v)=d; belong(u,v)=i; move=move+1; end end end end end end SLIC算法：算法： 5、移动聚类、移动聚类中心：中心： 即迭代优化即迭代优化 理论上上述步骤不断迭代直到误差收敛理论上上述步骤不断迭代直到误差收敛（可以理解为每个像素点聚类中心不再发（可以理解为每个像素点聚类中心不再发生变化为止），实践发现生变化为止），实践发现10次迭代对绝大次迭代对绝大部分图片都可以得到较理想效果，所以一部分图片都可以得到较理想效果，所以一般迭代次数取般迭代次数取10。 6. 增强连通增强连通性：性： 不连续的超像素、尺寸过小超像素重新分不连续的超像素、尺寸过小超像素重新分配给邻近的超像素配给邻近的超像素求点群中心的算法求点群中心的算法1）Minkowski Distance公式公式可以随意取值，可以是负数，也可以是正数，或是无穷大。2）Euclidean Distance公式公式也就是第一个公式=2的情况3）CityBlock Distance公式公式也就是第一个公式=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&c1(1)=1 belong(rr(g),cc(g)=belong(rr(1)-1,cc(1); elseif cc(1)-1=1 belong(rr(g),cc(g)=belong(rr(1),cc(1)-1); elseif cc(1)+1=x(2) belong(rr(g),cc(g)=belong(rr(1),cc(1)+1); elseif rr(1)+1=1)&(j-1)=1) if belong(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 if belong(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; end if belong(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; end if belong(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; end elseif (i+1)=1) if belong(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 if belong(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; end elseif (i+1)=x(1)&(j+1)=x(2) if belong(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算法的比较与改进：算法的比较与改进：对于一个480320的图像来说，SLIC要比TP09快10倍，比NC05快500倍。由b图可知，对于百万像素以上的图片，SLIC的速度要快于GS04。这是因为我们的算法运行复杂度为O(N)而GS04的复杂度为O(NlogN)。这是有趣的因为即使低端数码相机也能产生300万以上的像素。同时，GS04需要5N的空间来存储边权重和阀值，这与SLIC相反，SLIC需要1N的空间（存储离族群中心最近的像素点的距离）。图4(a)：在一幅481321的图形中，横坐标输入量为超像素点数，纵坐标为GKM与我们的算法所耗费时间值的对比。我们的算法对任何大小的超像素所需时间都不到0.5s。(b)图为不同的图片大小分割所需时间对比。
