区域生长的基本概念
数字图像分割算法一般是基于灰度值的两个基本特性之一：不连续性和相似性。前一种性质的应用途径是基于图像灰度的不连续变化分割图像，比如图像的边缘。第二种性质的主要应用途径是依据实现指定的准则将图像分割为相似的区域。区域生长算法就是基于图像的第二种性质，即图像灰度值的相似性。
如下图所示，如下图所示的一个极端情况，只需确认一个种子节点，然后按8临域法搜索与其相同的点，第一轮搜索结束后，更改种子节点并重复 该过程，直到找不到点为止。
具体细节如下，当随机到中间的点时，按顺序搜索周围的八个点，找到满足条件的最接近的一个点，将其选为新的种子节点，第一轮判断完毕后，生成新的区域与种子点，然后继续上述过程，直到到达停止条件为止。
区域生长的过程
区域生长是一个或多个将成组的像素或区域发展成更大区域的过程。从种子点的集合开始，通过将与每个种子点有相似属性强度、灰度级、纹理颜色等的相邻像素合并到此区域，从而完成对图像的分割。
因此区域生长算法一般分为三个步骤实现：
(1)确定生长种子点；
(2)规定生长准则；
(3)确定生长停止条件。
下面将详细讲解这三个步骤
1确认种子点
种子点的确认根据具体算法不同，存在差异
但本质上遵循有序随机的规律
假设要确认提取4个种子节点，图像的长和宽为w,h。那么可以先找出四个均匀分布的点[w/4,h/4]，[3w/4,h/4]，[w/4,3h/4]，[3w/4,3h/4]，再通过设好的随机规则随机移动四个点。
有序性是为了保证分割的平滑，随机性是为了优化分割效果。
当然也可以根据需求自行决定种子点。
2确认生长准则
一般来说，生长点的选取规则有两种，邻域法和区域法
领域法如上面所讲的八领域，关注的是像素级的相似度，即尽量纳入与种子像素相似的像素，这种方法对非固定图像的识别更加有效，能很好的找出像素级的相似区域，但对模糊边界的识别较差。
区域法则是在纳入新像素时并不只考虑种子像素，而是将已确认区域与其进行整体比较。
如下图所示如果单考虑种子节点与其领域，20与10的差距不大，但是如果考虑已有区域的整体灰度值，与10的差距就会变的很大。
总体来说，两种方法各有优缺点，这两种方法的选取一般是根据需要切割的目标决定的。领域法对差异及其敏感，很容易避开差异较大的位置，但是对模糊边界或梯度变化图像的识别就很差，而区域法能很好的保证切割的整体性和一致性，但是对边界缺乏敏感，很容易陷入欠拟合的问题中。
3确认生长停止条件
当根据生长准则，一般到达指定大小或所有的点都无法将新的点纳入其中时，停止生长。
根据以上三个法则，对出需要分割的图像：1、选取图像中的一点为种子点（种子点的选取需要具体情况具体分析）。2、在种子点处进行扩展，判定准则是：如果考虑的像素与种子像素或区域灰度值差的绝对值小于某个门限T，则将该像素包括进种子像素所在的区域。3、当不再有像素满足加入这个区域的准则时，区域生长停止。
区域生长的步骤
- 对图像顺序扫描，找到第1个还没有归属的像素, 设该像素为(x0, y0);
- 以(x0, y0)为中心, 考虑(x0, y0)的8邻域像素(x, y)，如果(x, y)满足生长准则, 将(x, y)与(x0, y0)合并(在同一区域内), 同时将(x, y)压入堆栈;
- 从堆栈中取出一个像素, 把它当作(x0, y0)返回到步骤2;
- 当堆栈为空时，返回到步骤1;
- 重复步骤1 - 4直到图像中的每个点都有归属时。生长结束。
如实现对下图中娃娃的分割
手动选取种子点并按回车健完成分割
% Segment based on area, Region Growing基于区域生长算法的图像分割;
clear ;
[fileName,pathName] = uigetfile('*.*','Please select an image');%文件筐，选择文件
if(fileName)
fileName = strcat(pathName,fileName);
fileName = lower(fileName);%一致的小写字母形式
else
J = 0;%记录区域生长所分割得到的区域
msgbox('Please select an image');
return; %退出程序
end
I = imread(fileName);
figure; imshow(I);
if( ~( size(I,3)-3 ))
I = rgb2gray(I);%转化为单通道灰度图
end
I = im2double(I); %图像灰度值归一化到[0,1]之间
% Ireshape = imresize(I,[600,800]);
% I = Ireshape(51:475,200:699);
% gausFilter = fspecial('gaussian',[5 5],0.5);
% I = imfilter(I,gausFilter,'replicate');
%种子点的交互式选择
[y,x] = getpts;%鼠标取点 ， 回车确定
x = round(x);
y = round(y);
% if( exist('x','var') == 0 && exist('y','var') == 0)
% subplot(2,2,1),imshow(I,[]);
% hold on;
% [y,x] = getpts;%鼠标取点 回车确定
% x = round(x(1));%选择种子点
% y = round(y(1));
% end
% if( nargin == 0)
% reg_maxdist = 0.1;
% %nargin是matlab代码编写中常用的一个技巧，主要用于计算当前主函数的输入参数个
% %数，一般可以根据nargin的返回值来确定主函数输入参数的缺省值。在实现中，如果
% %用户输入的参数个数为零，那么默认为0.2
% end
J = zeros(size(I)); % 主函数的返回值，记录区域生长所得到的区域
Isizes = size(I);
reg_mean = I(x,y);%表示分割好的区域内的平均值，初始化为种子点的灰度值
reg_size = 1;%分割的到的区域，初始化只有种子点一个
neg_free = 10000; %动态分配内存的时候每次申请的连续空间大小
neg_list = zeros(neg_free,3);%第一列行坐标，第二列列坐标，第三列存储灰度值
%定义邻域列表，并且预先分配用于储存待分析的像素点的坐标值和灰度值的空间，加速
%如果图像比较大，需要结合neg_free来实现matlab内存的动态分配
neg_pos = 0;%用于记录neg_list中的待分析的像素点的个数
pixdist = 0;
%记录最新像素点增加到分割区域后的距离测度
%下一次待分析的四个邻域像素点和当前种子点的距离
%如果当前坐标为（x,y）那么通过neigb我们可以得到其四个邻域像素的位置
neigb = [ -1 0;
1 0;
0 -1;
0 1];
%开始进行区域生长，当所有待分析的邻域像素点和已经分割好的区域像素点的灰度值距离
%大于reg_maxdis,区域生长结束
while (pixdist < 0.06 && reg_size < numel(I))
%增加新的邻域像素到neg_list中
for j=1:4
xn = x + neigb(j,1);
yn = y + neigb(j,2);
%检查邻域像素是否超过了图像的边界
ins = (xn>=1)&&(yn>=1)&&(xn<=Isizes(1))&&(yn<=Isizes(2));
%如果邻域像素在图像内部，并且尚未分割好；那么将它添加到邻域列表中
if( ins && J(xn,yn)==0) %J(xn,yn)==0表示图像中该点还没有被分割
neg_pos = neg_pos+1;
neg_list(neg_pos,:) =[ xn, yn, I(xn,yn)];%存储对应点的灰度值
J(xn,yn) = 1;%标注该邻域像素点已经被访问过 并不意味着，他在分割区域内
end
end
%如果分配的内存空问不够，申请新的内存空间
if (neg_pos+10>neg_free)
neg_free = neg_free + 100000;
neg_list((neg_pos +1):neg_free,:) = 0;
end
%从所有待分析的像素点中选择一个像素点，该点的灰度值和已经分割好区域灰度均值的
%差的绝对值时所待分析像素中最小的
dist = abs(neg_list(1:neg_pos,3)-reg_mean);
[pixdist,index] = min(dist);
%计算区域的新的均值
reg_mean = (reg_mean * reg_size +neg_list(index,3))/(reg_size + 1);
reg_size = reg_size + 1;
%将旧的种子点标记为已经分割好的区域像素点
J(x,y)=2;%标志该像素点已经是分割好的像素点
x = neg_list(index,1);
y = neg_list(index,2);
%将新的种子点从待分析的邻域像素列表中移除
neg_list(index,:) = neg_list(neg_pos,:);
neg_pos = neg_pos -1;
end
J = (J==2);%我们之前将分割好的像素点标记为2
hold off;
figure;
subplot(2,2,2),imshow(J);
J = bwmorph(J,'dilate');%补充空洞
subplot(2,2,3),imshow(J);
subplot(2,2,4),imshow(I+J);
超像素的基本概念
超像素就是把一幅原本是像素级(pixel-level)的图，划分成区域级(district-level)的图。可以将其看做是对基本信息进行的抽象。
超像素分割属于图像分割(image segmentation)，再细化应该属于过分割(over segmentation)。比如我们对一幅图像进行超像素分割，分割之后，会得到许多大小不一的区域，我们可以从这些区域中提取出有效的信息，比如颜色直方图、纹理信息。
比如有一个人，我们可以对这个人的图像进行超像素分割，进而通过对每个小区域的特征提取，辨识出这些区域是处于人体的哪个部分（头部、肩部，腿部），进而建立人体的关节图像。
如果你要用图论的方法来分离前景背景。如果这幅图的大小为480 * 640，那么你建立的图(graph)有480640个节点。如果你预先对这幅图像使用超像素分割，将其分割为1000个超像素，那么你建立的图只有1000个节点。大大提升了计算速度。
以上是超像素的基本概念，超像素分为很多类
如常用用来处理大型图片的有：
分水岭算法：它是一种梯度上升方法，在O（N log N）时间内运行。该算法生成以分水岭线为界的区段，通过从局部最小区域扩展区域自下而上。Achanta等人发现分水岭算法的边界依从性差，产生的大小和形状不规则的超像素。
Turbopixel方法：基于几何流的算法，其运行时间接近O（N）。Achanta等人发现Turbopixels表现出较差的边界粘附性并且在实践中表现缓慢。
SLIC（简单线性迭代聚类）是一种在O（N）时间内运行的超像素分割算法。SLIC 通过仅在恒定大小的区域上搜索聚类中心来调整k -means聚类。SLIC速度非常快，并且具有良好的边界依从性。Achanta等人发现SLIC是实践中最快的超像素算法。
Felzenszwalb和Huttenlocher 提出了一种基于图的图像分割算法（FH），它在O（NlogN）时间内运行。该算法使用类似于Kruskal算法的方法自下而上构建超像素。FH需要调整单个参数，该参数设置对更大或更小的超像素的偏好，尽管阈值函数τ可用于调整期望的超像素形状。Achanta等。人现这个算法具有很好的边界依从性，运行速度几乎和SLIC一样快。
相比较而言，SLIC超像素分割的性能优异且处理速度较快，接下来将以论文《SLIC Superpixels Compared to State-of-the-art
Superpixel Methods》为基础分析SLIC分割。
SLIC Superpixels Compared to State-of-the-artSuperpixel Methods
该论文对五种最先进的超像素算法进行了实证比较，以了解它们对图像边界、速度、内存效率以及对分割性能的影响。然后介绍了一种新的超像素算法——简单线性迭代聚类(SLIC)，并将运行效果进行比较，得到了较好的速度和结果。
超像素算法将像素组织成具有感知意义的原子区域，可以用来替代像素网格的刚性结构。它们捕获图像冗余，提供了计算图像特征的实用原子，大大降低了后续图像处理任务的复杂度。如下图所示：
生成超级像素的方法有很多，每个方法都有自己的优点和缺点，这些优点和缺点可能更适合于特定的应用程序。例如，如果坚持图像边界是最重要的，那么基于图形的方法（例如IJCV）可能是一个较好的选择。然而，如果用超像素构建一个图形，一个产生更规则格子的方法(如PAMI)可能是更好的选择。
虽然很难定义什么是适用于所有应用程序的理想方法，但本文作者认为一个好的分割效果往往需要以下三个特性:
1.像素应该很好地遵守图像边界。
2.当作为预处理步骤来降低计算复杂度时，超像素应该计算速度快，内存效率高，并且易于使用。
3.当用于分割目的时，超像素既增加速度又提高结果的质量。
基于上面的三条原则，作者对最新各种方法进行了比较，但是这些方法在某些方面都存在问题。于是他提出了SLIC超像素分割方法来对图像进行分割。SLIC在PASCAL和MSRC数据集中用于分割时优于现有的方法，而且其处理数据的速度比现有的方法更快，内存效率更高。以下是方法效能的比较：
硬件:2GB RAM的英特尔双核2.26 GHz处理器
关于以上几种参数简单讲解下
欠分割率(Under Segmentation )US=Nfp/Nn
边界召回（Boundary recall）BR=TP/(TP+FN)
SLIC超像素规则
本文提出了一种生成超像素的新方法，它比现有的方法更快，更高效的内存，具有最先进的边界粘附性，并提高了分割算法的性能。简单线性迭代聚类（SLIC）是对超像素生成的一种适应，与传统的kmean算法有两个重要的区别:
1.通过将搜索空间限制在与超像素大小成比例的区域，优化过程中的距离计算次数大大减少。这降低了复杂度，使其在像素数量N上是线性的，并且与超像素数量k无关。
2.加权距离测量结合了颜色和空间接近度，同时控制了超像素的大小和紧凑性。
SLIC简单易用，易于理解。默认情况下，该算法的唯一参数是k，即大小近似相等的所需超像素数。对于CIELAB颜色空间中的彩色图像，聚类过程从初始化步骤开始，首先在间隔为S像素的规则网格上采样k个初始聚类中心Ci。生产大约同样大小的超像素，网格间隔S = √N / k。中心移动到种子位置对应于最低的梯度的位置在一个3×3的小区。这样做是为了避免将一个超像素集中在边缘上，并减少用一个有噪声的像素播种一个超像素的机会。
接下来，在赋值步骤中，每个像素i与最近的集群中心相关联，其搜索区域与其位置重叠，如下图所示。这是加快算法速度的关键，因为限制搜索区域的大小可以显著减少距离计算的次数，并且比传统的k-means聚类具有显著的速度优势，因为每个像素都必须与所有聚类中心进行比较。这通过引入距离度量D来实现，它确定每个像素最近的集群中心，由于预期的空间范围超像素近似大小为S×S,因此在超像素中心2 S×2 S 的区域寻找相似的像素。
一旦每个像素都关联到最近的集群中心，更新步骤就会调整集群中心，使其成为属于集群的所有像素的均值向量。使用L2范数用于计算新的集群中心位置和以前的集群中心位置之间的剩余误差E。赋值和更新步骤可以重复进行，直到错误收敛为止，但是我们发现，对于大多数图像，10次迭代就足够了，并且使用这个标准报告本文中的所有结果。最后，通过处理步骤通过将不相交的像素重新分配给附近的超像素来增强连通性。
下述为该算法的伪代码：
SLIC超像素在彩色图像平面空间中生成时。会在定义距离度量D时会存在问题，这个问题可能不会表现明显。计算算法中像素i与聚类中心Ck之间的距离D时，像素的颜色在CIELAB颜色空间中表示，其可能值的范围已知。
简单地将D定义为labxy空间中的5D欧氏距离，会导致不同超像素大小的聚类行为不一致。对于较大的超像素，空间距离大于颜色接近度，因此空间接近度比颜色更重要。这产生了紧凑的超像素，不能很好地坚持图像边界。对于较小的超像素，反之亦然。
为了将这两种距离合并成一个单独的度量，有必要通过它们在集群、Ns和Nc中各自的最大距离来规范化颜色接近度和空间接近度。
D’可以如下推导
在给定的集群中预期的最大空间距离，应该对应于采样间隔，NS = S 。确定最大颜色距离Nc就不是那么简单的了，因为从一簇到另一簇颜色的距离可能会有显著的变化，从一幅图像到另一幅图像也完全不一样。这个问题可以通过将Nc固定到一个常数m以使D‘为
通过这样定义D, m也允许我们衡量颜色相似度和空间接近度之间的相对重要性。当m较大时，空间接近性更重要，产生的超像素更紧凑(即，它们的面积与周长比较低)。当m很小时，产生的超像素更紧密地附着在图像边界上，但其大小和形状不那么规则。当使用CIELAB颜色空间时，m可以在范围[1,40]内变化。
例如如下分割，分别为m为1和m为50时的不同效果
该方法同样可以推广到三维图片
接下来贴出各种方法性能的比较
该文后续讲解的就是关于其应用场景和数据讲解，有需要可以直接观看原文。