一、简介

1 概念
超像素由一系列位置相邻且颜色、亮度、纹理等特征相似的像素点组成的小区域。这些小区域大多保留了进一步进行图像分割的有效信息，且一般不会破坏图像中物体的边界信息。
超像素是吧一幅像素级（pixel-level）的图，划分成区域级（district-level）的图，是对基本信息元素进行的抽象。

（a）是原始图像，（b）是基于人类视角的分割图（groundtruth），（c）是超像素分割的图像，（d）是基于（c）进行分割的图像。
超像素最大的功能之一是作为图像处理其他算法的预处理，在不牺牲太大精确度的情况下降维。
超像素最直观的解释是把一些具有相似特性的像素“聚合”起来，形成一个更具有代表性的大“元素”。而这个新元素，将作为其他图像处理算法的基本单位。这样可以降低维度，剔除一些异常像素点。
理论上，任何图像分割算法的过度分割（over-segmentation）即可生成超像素。
图像分割中的超像素是指具有相似纹理、颜色、亮度等特征的相邻相似构成的具有一定意义的不规则的像素块。它利用像素之间特征的相似性将像素分组，用少量的超像素代替大量的像素来表达图像特征，很大程度上降低了图像处理的复杂度，所以通常作为分割算法的预处理步骤。

2 超像素判别条件
（1）Undersegmentation Error

（2）如上图所示，白色是图像中的一个物体，红线是一个个超像素的轮廓，而粉红色的区域就是undersegmentation区域，这部分区域越大越不好。
Boundary Recall

如上图所示，黑色虚线及实线是图像中物体的轮廓，红线是超像素的边界。一个好的超像素算法，应该覆盖图像中物体的轮廓。在给予一定缓冲（粉红色区域）的情况下，超像素边缘可以覆盖图像物体边缘（黑色实线）越多越好。
（3）Compactness score
衡量超像素是否“紧实”。

3 超像素初始化的方法
种子像素初始化
SLIC利用了简单的聚类（贪婪）算法，初始时，每一个聚类的中心被平均的分布在图像中，而超像素的个数，可以基本由这些中心点来决定。每一步迭代，种子像素合并周围的像素，形成超像素。

矩形区域初始化
SEEDS的初始化是把图像平均分割成很多矩形，初始超像素即为这些矩形。每一步迭代，超像素的边缘不断变化，直到汇合。

4 超像素算法

5 SLIC算法
SLIC（simple linear iterative clustering），即简单的线性迭代聚类。它是2010年提出的一种思想简单、实现方便的算法，将彩色图像转换为CIELAB颜色空间和XY坐标下的5维特征向量，然后对5维特征向量构造距离度量标准，对图像像素进行局部聚类的过程。SLIC算法能生成紧凑近似均匀的超像素，在运算速度，物体轮廓保持、超像素形状方面具有较高的综合评价，比较符合人们期望的分割效果。

5.1 SLIC优点：

生成的超像素如同细胞一般紧凑整齐，邻域特征比较容易表达。这样基于像素方法可以比较容易的改造为基于超像素的方法。
不仅可以分割彩色图像，也可以兼容分割灰度图。
需要设置的参数非常少，默认情况下只需要设置一个预分割的超像素的数量。
相比其他的超像素的分割方法，SLIC在运行速度、生成超像素的紧凑度、轮廓保持方面都比较理想。

5.2 算法步骤：

初始化种子点（聚类中心）：按照设定的超像素的个数，在图像内均匀的分配种子点。假设图像总共有N个像素点，预分割为K个相同尺寸的超像素，那么每个超像素的大小为N/K，则相邻种子点的距离（步长）近似为S=sqrt(N/K)。
在种子点的n*n领域内重新选择种子点（一般取n=3）：计算该领域内所有像素点的梯度值，将种子点移到该领域内梯度最小的地方。避免种子点落在梯度较大的轮廓边界上，以免影响后续聚类效果。
在每个种子点周围的领域内为每个像素点分配类别标签（即属于哪个聚类中心）：SLIC的搜索范围是2S2S，期望的超像素尺寸为SS，这样可以加速算法收敛。
距离度量：包括颜色距离和空间距离。对每个搜索到的像素点，分别计算它和该种子点的距离。

二、源代码

% 能够确定超像素位置的核心程序是  EnforceLabelConnectivity
% 11-123页码 
clc
clear
close all;
tic
img = imread('bee.jpg');
imshow(img)
title('original')
%设定超像素个数
K = 500;
%设定超像素紧凑系数
m_compactness = 100;

%%
img = DeSample(img,2);
img_size = size(img);
%转换到LAB色彩空间
cform = makecform('srgb2lab');       %rgb空间转换成lab空间 matlab自带的用法,Create color transformation structure
img_Lab = applycform(img, cform);    %rgb转换成lab空间
figure;
imshow(img_Lab)
title('img_lab')

%%
%得到超像素的LABXY种子点信息     
img_sz = img_size(1)*img_size(2);
superpixel_sz = img_sz/K;  % 每个超像素的像素点数
STEP = uint32(sqrt(superpixel_sz)); % 开方的边长
xstrips = uint32(img_size(2)/STEP);  % x方向 的超像素个数
ystrips = uint32(img_size(1)/STEP);  % y方向 的超像素个数
xstrips_adderr = double(img_size(2))/double(xstrips);  
ystrips_adderr = double(img_size(1))/double(ystrips);
numseeds = xstrips*ystrips;   % 实际的超像素个数
%种子点xy信息初始值为晶格中心亚像素坐标
%种子点Lab颜色信息为对应点最接近像素点的颜色通道值
kseedsx = zeros(numseeds, 1);
kseedsy = zeros(numseeds, 1);
kseedsl = zeros(numseeds, 1);
kseedsa = zeros(numseeds, 1);
kseedsb = zeros(numseeds, 1);

n = 1;
for y = 1: ystrips   % 第y个超像素
    for x = 1: xstrips   % 第 x 个超像素
        kseedsx(n, 1) = (double(x)-0.5)*xstrips_adderr; % 第x个种子点中心坐标，非准确描述
        kseedsy(n, 1) = (double(y)-0.5)*ystrips_adderr; % 第y个种子点中心坐标，非准确描述
        % 种子点中心对应LAB图上位置的 三通道值
        kseedsl(n, 1) = img_Lab(fix(kseedsy(n, 1)), fix(kseedsx(n, 1)), 1);  % fix 417.1296 变417
        kseedsa(n, 1) = img_Lab(fix(kseedsy(n, 1)), fix(kseedsx(n, 1)), 2); 
        kseedsb(n, 1) = img_Lab(fix(kseedsy(n, 1)), fix(kseedsx(n, 1)), 3);
        n = n+1;
    end
end

n = 1;
%根据种子点计算超像素分区
klabels = PerformSuperpixelSLIC(img_Lab, kseedsl, kseedsa, kseedsb, kseedsx, kseedsy, STEP, m_compactness);
%合并小的分区
[supmtrx,supmtry,nlabels] = EnforceLabelC(img_Lab, klabels, K);
% 这里的supmtrx,supmtry的每列分别是对应标签区域的全部x坐标和y坐标
function klabels = PerformSuperpixelSLIC(img_Lab, kseedsl, kseedsa, kseedsb, kseedsx, kseedsy, STEP, compactness)

[m_height, m_width, m_channel] = size(img_Lab);
[numseeds xxxxx]= size(kseedsl);
img_Lab = double(img_Lab);
%像素标签格式为(x, y) (行, 列)
klabels = zeros(m_height, m_width);
%聚类尺寸
clustersize = zeros(numseeds,1);
inv = zeros(numseeds,1);
sigmal = zeros(numseeds,1);
sigmaa = zeros(numseeds,1);
sigmab = zeros(numseeds,1);
sigmax = zeros(numseeds,1);
sigmay = zeros(numseeds,1);
invwt = 1/( (double(STEP)/double(compactness)) *(double(STEP)/double(compactness)) );
%invwt = double(compactness)/double(STEP);
distvec = 100000*ones(m_height, m_width);
numk = numseeds;
for itr = 1: 10   %迭代次数
    sigmal = zeros(numseeds, 1);
    sigmaa = zeros(numseeds, 1);
    sigmab = zeros(numseeds, 1);
    sigmax = zeros(numseeds, 1);
    sigmay = zeros(numseeds, 1);
    clustersize = zeros(numseeds, 1);
    inv = zeros(numseeds, 1);
    distvec = double(100000*ones(m_height, m_width));
    %根据当前种子点信息计算每一个像素的归属
    for n = 1: numk
        y1 = max(1, kseedsy(n, 1)-STEP);
        y2 = min(m_height, kseedsy(n, 1)+STEP);
        x1 = max(1, kseedsx(n, 1)-STEP);
        x2 = min(m_width, kseedsx(n, 1)+STEP);
        %按像素计算距离
        for y = y1: y2
            for x = x1: x2
                %dist_lab = abs(img_Lab(y, x, 1)-kseedsl(n))+abs(img_Lab(y, x, 2)-kseedsa(n))+abs(img_Lab(y, x, 3)-kseedsb(n));
                % lab图 点到种子点 定义距离差，判断相似度
                dist_lab = (img_Lab(y, x, 1)-kseedsl(n, 1))^2+(img_Lab(y, x, 2)-kseedsa(n, 1))^2+(img_Lab(y, x, 3)-kseedsb(n, 1))^2;
                % 改成平方啊 ！！！  @@@  ！！！  @@@   ！！！
                dist_xy = (double(y)-kseedsy(n, 1))*(double(y)-kseedsy(n, 1)) + (double(x)-kseedsx(n, 1))*(double(x)-kseedsx(n, 1));
                %dist_xy = abs(y-kseedsy(n)) + abs(x-kseedsx(n));
                
                %距离 = lab色彩空间距离 + 空间距离权重×空间距离
                dist = dist_lab + dist_xy*invwt;
                %在周围最多四个种子点中找到最相似的 标记后存入klabels
                %m = (y-1)*m_width+x;
                if (dist<distvec(y, x))
                    distvec(y, x) = dist;  % 不断变小
                    klabels(y, x) = n;  % n是标签，也就是值像素属于哪个种子点
                end
            end
        end
    end
    %完成一遍分类后，重新计算种子点位置 使其向梯度最小地方移动
    ind = 1;
    for r = 1: m_height
        for c = 1: m_width
            sigmal(klabels(r, c),1) = sigmal(klabels(r, c),1)+img_Lab(r, c, 1);  % 像素块内所有的通道值相加
            sigmaa(klabels(r, c),1) = sigmaa(klabels(r, c),1)+img_Lab(r, c, 2);
            sigmab(klabels(r, c),1) = sigmab(klabels(r, c),1)+img_Lab(r, c, 3);
            sigmax(klabels(r, c),1) = sigmax(klabels(r, c),1)+c;    % 像素块内所有的横坐标相加
            sigmay(klabels(r, c),1) = sigmay(klabels(r, c),1)+r;     % 像素块内所有的纵坐标相加
            clustersize(klabels(r, c),1) = clustersize(klabels(r, c),1)+1;   % 像素块内所有个数相加
        end
    end
    for m = 1: numseeds  % 第m个种子点
        if (clustersize(m, 1)<=0)
            clustersize(m, 1) = 1;
        end
        inv(m, 1) = 1/clustersize(m, 1);
    end
    function [supmtrx,supmtry,nlabels] = EnforceLabelC(img_Lab, labels, K)

dx = [-1, 0, 1, 0];  %四邻域
dy = [0, -1, 0, 1];
[m_height, m_width, m_channel] = size(img_Lab);
[M, N] = size(labels);
numlabel = max(max(labels));
SUPSZ = (m_height*m_width)/K;   %标准区域面积
nlabels = (-1)*ones(M, N);

label = 1;
adjlabel = 1;
xvec = zeros(m_height*m_width, 1);
yvec = zeros(m_height*m_width, 1);
supmtrx = zeros(2*floor(SUPSZ), numlabel);
supmtry = zeros(2*floor(SUPSZ), numlabel);
m = 1;
n = 1;

for j = 1: m_height
    for k = 1: m_width
        %逐点寻找未标记的区域 小于0 才执行
        if (0>nlabels(m, n))
            %从第一个未标记的(m,n)起，确定一个新区域，用label标记该区域的起点，用蝶形前进
            nlabels(m, n) = label;
            %开始一个新的分割 记录起点坐标
            xvec(1, 1) = k;
            yvec(1, 1) = j;
            supmtrx(1, label) = k;
            supmtry(1, label) = j;
            %如果起点与某个已知区域相连 用adjlabel记录该区域编号 如果当前区域过小则与相邻区域合并
            for i = 1: 4
                x = xvec(1, 1)+dx(1, i);
                y = yvec(1, 1)+dy(1, i);
                if (x>0 && x<=m_width && y>0 && y<=m_height)
                    if (nlabels(y, x)>0)
                        adjlabel = nlabels(y, x);  % 一般是左临或上邻的标签
                    end
                end
            end

三、运行结果

四、备注

版本：2014a
完整代码或代写加1564658423