快速理解支持向量机实现图像分割（Matlab实现基于SVM的图像分割）
@Matlab实现基于SVM的图像分割
如何通过一篇文章就理解支持向量机实现图像分割
最近是Matlab实验周，我选择的课题是支持向量机实现图像分割，说实话比较让人头大，因为向量机训练的效果不佳，切割出来的图片奇奇怪怪五花八门（甚至还有些搞笑），开始的时候是从CSDN上copy的代码直接运行，我觉得选像素点和向量机训练过程有一些问题，查阅资料之后，我对向量机有了新的理解。（文章结尾有能够成功运行的Matlab代码）
查阅资料
先贴一段我从图书馆借来的书上关于SVM的原话：支持向量机的基本思想是：定义最优线性超平面，并把寻找最优线性超平面的算法归结为求解一个凸规划问题，进而基于Mercer核展开定理，通过构造一个非线性映射φ，把样本空间映射到一个高位乃至无穷维的特征空间，使之在特征空间中可以应用线性学习机的方法解决样本空间中的高度非线性分类和回归等问题。
emmm…说实话，看了这句话我感觉更疑惑了，但是知乎上的一篇回答真的让人拍手叫绝，我总结一下那篇文章对向量机的描述：SVM就像是一个如何用一根棍子把球分开的游戏（但是这个游戏涉及到多维情况——对于二维点而言是直线，三维空间中则是平面，更高维则是超平面），如何才能确定那个最佳分类的直线呢?其实这正是支持向量机(SVM,SupportVectorMachine)要解决的问题。
SVM就是试图把棍放在最佳位置，好让在棍的两边有尽可能大的间隙。
即使放了更多的球，棍仍然是一个好的分界线
像这样的情况，如果在二维空间没有办法用一根棍子将他们分开呢？
这个时候可以像所有武侠片中一样桌子一拍，球飞到空中。然后，定格时间，抓起一张纸，插到了两种球的中间（二维转三维），就像下图一样；
这个时候，从“上帝视角”来看，这些球看起来像是被一条曲线分开了。
如果把这个游戏运用到向量机中，这些球就叫做 「data」，棍子就叫做 「classifier」, 最大间隙trick叫做「optimization」， 拍桌子叫做「kernelling」, 那张纸叫做「hyperplane」
其实，我们可以在这个游戏中思考一个问题，就是——我们可以有很多种方式用一根棍子将这些球分开，那有没有一种最优方法呢？哪一条直线分类效果最好呢？评判的标准又是什么？
比如下面这张图，是line1还是line2的分割效果更好？
line1的分类效果要比line2更好的，因为line1几乎位于这两类点的中间，不偏向于任何一类点；而line2则偏向右上部分的点更多一些。如果这时又增加了一些点让你将它们归为这两类，显然line1要更“公正”一些，而line2则有可能将本来属于右上类的点错误地归为左下类。当然，也有确定最佳分类的直线的办法，这就是支持向量机要解决的问题了。
显然，存在无穷多条直线可以将这两类点分开，但最佳直线应该满足“公正性”：即不偏向任何一类点，或者说处于中间位置。假设：有一条分割直线l方程为：wx+b=0；共有n个点，坐标分别为(x1,y1)，(x2,y2)，⋯，(xn,yn)，n个点到直线l的距离分别为d1，d2，⋯，dn，现在我们需要找d1,d2,⋯,dn中的最小值：dmin=min{d1,d2,⋯,dn}，显然我们希望dmin越大越好，dmin越大，说明它距离两类的距离都较远。于是问题转化为在所有可行的直线划分中，找到使得dmin最大的那条即是最佳划分直线。对于线性可分的情况而言，我们可以证明，这样的最佳直线总是存在的。我们称找到的最佳划分两类的直线为:最大几何间隔分离超平面(对于二维点而言是直线，三维空间中则是平面，更高维则是超平面了，这里统称为超平面)
什么是支持向量？
支持向量机(SVM)之所以称之为支持向量机，是因为有一个叫作支持向量(SupportVector)的东西。假设我们现在已经找到了最大几何间隔分离超平面，我们可以找到许多条与这条直线平行的直线，在所有平行的直线中，存在两条直线，它们恰好可以划分两类点，所谓恰好是指，如果再平移哪怕一点点，就会不能正确划分两类点，这两条临界直线(超平面)被称之为间隔边界。手绘一下这种情况，看下图：
对于线性可分的情况而言，我们可以证明，在样本点中总会有一些样本点落在间隔边界上(但是对于线性不可分的情况，则未必如此)，落在间隔边界上的这些样本点就被我们称为支持向量。之所以被称之为支持向量呢，是因为我们确定的最大几何间隔分离超平面只与这些支持向量有关，与其他的样本点无关，也就是说哪怕你去掉再多非支持向量的点，最大几何间隔分离超平面也一样不变。这也就是支持向量机名字的来源。
支持向量机如何处理线性不可分的情况？
这个问题其实涉及到SVM的核心了。首先，我们需要明确一下输入空间与特征空间这两个概念。输入空间就是我们定义样本点的空间，由于问题线性不可分，所以我们无法用一个超平面将两类点分开，但是我们总可以找到一个合适的超曲面将两类点正确划分，问题的关键就是找到这个超曲面。直接寻找显然是很困难的，所以我们聪明的数学家就定义了一个映射（从低维到高维），研究发现，如果映射定义地恰当，则原来在低维线性不可分的问题，到了高维居然就线性可分了！（就像开始说的那个拍桌子分球的游戏，将桌面二维空间不可分的球转换到三维空间去），这真的是一个让人惊喜的发现！所以我们只要在高维按照之前线性可分的情况去找最大几何间隔分离超平面，找到之后，再还原到低维就可以了。理论上已经证明，在低维线性不可分的情况下，我们总可以找到合适的从低维到高维的映射，使得在高维线性可分。于是问题的关键就是找这个从低维到高维的映射了，这个其实就是核函数(核技巧)要干的事情。简单地说，在给定核函数的情况下，我们可以利用求解线性分类问题的方法来求解非线性分类问题的支持向量机，学习是隐式地在特征空间(也就是映射之后的高维空间)进行的，这被称之为核技巧。在实际应用中，往往直接依赖经验选择核函数，然后再验证其是有效的即可。常用的核函数有:多项式核函数、高斯核函数、sigmoid核函数等。
代码思路
以我儿子哈利的照片为例：
我们知道，彩色图片本质上是由一个一个的像素点组成的，每一个像素点由RGB三色组成，或者说本质上彩色图像就是三维数组（灰度图像是二维数组），如果我们将哈利和背景看做两类物体，那么现在的任务则是从整个图像中将这两类分割出来。显然哈利和背景的界限并不是一条单纯的直线，所以
这是一个非线性可分的问题。从图中可以看出，哈利偏黑色和灰色，掺杂有少量红色以及黄色(格兰芬多围巾)，而背景则是淡棕色和乳白色的。所以我们可以以颜色为标准对二者进行分类，即以RGB为分类标准。为了使用SVM，首先我们需要选取训练样本，这里就是找出典型的属于哈利的像素点RGB值(为一个长度为3的向量),和属于背景的RGB值。对于如何选取像素点，不建议用PS或者安装小软件测每一张图片的RGB值，我们使用下面代码中给出的方法，在运行程序的时候实时选取坐标点，这样就可以根据每张图片有针对性的选取像素点，并且不用每次运行之前都用选色工具，省去了很多不必要的麻烦。这里我对于哈利和背景分别选取了20个像素点，就分别得到了一个20行3列的样本数据(每一行是一个样本,共有20个样本)。将背景的像素点标记为0，哈利的像素点标记为1，得到长度为20的的向量。由于图像原始数据为三维矩阵，设其维度为(m,n,k)，先将其转化为二维(mn,k)的矩阵，然后使用线性不可分的SVM训练样本数据，接着使用训练好的SVM对(mn,k)矩阵进行归类，得到一个长为mn的数据全0或者全1的一维数组TestLabal，为0的部分就是代表对应的像素点判定为背景了。接着将一维数组TestLabal在行的方向上扩展为3列，即变为(TestLabal,TestLabal,TestLabal)，扩展之后的矩阵维度为(mn,k),再将其变回(m,n,k)三维矩阵。该矩阵与原始图像三维矩阵对应，该矩阵数据点为(0,0,0)的部分即判定为背景，我们将图像上该像素点的RGB值变为(255,255,255)(白色)，于是我们就可以得到去掉背景(变为白色)的哈利了。
总结步骤如下：
1.选取彩色图像的像素点
2.原始数据为(m,n,k)三维矩阵
3.转化为(mn,k)二维矩阵
4.用线性不可分SVM训练数据
5.SVM对(mn,k)归类
6.得到全0或全1一维数组
7.一维数组在行方向上扩展为三列，扩展之后矩阵维度(m*n,k)
8.变回三维矩阵，并与原来的三维矩阵作对应，矩阵数据点为(0,0,0)的部分判定为背景，将图像上该像素点的RGB值变为(255,255,255)白色
具体实现
Matlab实现基于SVM的图像分割代码如下：
%%
tic; %tic函数自动记录起始时刻，toc函数记录时间差
close all; %关闭所有figure窗口
clear; %清除工作空间所有变量
clc; %清除命令窗口的内容
format compact; %控制输出显示格式
%%
[filename,pathname,flag] = uigetfile('.jpg','请导入图像文件');
pic = imread([pathname,filename]);
figure;
imshow(pic);
%% 确定训练集
TrainData_background = zeros(20,3,'double');
TrainData_foreground = ones(20,3,'double');
% 背景采样
msgbox('请选择20个背景样本点','Background Samples','help');
pause;
for run = 1:20
[x,y] = ginput(1); %ginput函数直接提取像素点,返回这个点的坐标
hold on;
plot(x,y,'r*');
x = uint8(x);
y = uint8(y);
TrainData_background(run,1) = pic(x,y,1);
TrainData_background(run,2) = pic(x,y,2);
TrainData_background(run,3) = pic(x,y,3);
end
% 待分割出来的前景采样
msgbox('请选择20个前景样本点','Foreground Samples','help');
pause;
for run = 1:20
[x,y] = ginput(1);
hold on;
plot(x,y,'ro');
x = uint8(x);
y = uint8(y);
TrainData_foreground(run,1) = pic(x,y,1);
TrainData_foreground(run,2) = pic(x,y,2);
TrainData_foreground(run,3) = pic(x,y,3);
end
% let background be 0 & foreground 1
TrainLabel = [zeros(length(TrainData_background),1); ...
ones(length(TrainData_foreground),1)];
%% 建立支持向量机 基于libsvm
TrainData = [TrainData_background;TrainData_foreground];
model = svmtrain(TrainLabel, TrainData, '-t 1 -d 3');
%% 进行预测 i.e.进行图像分割 基于libsvm
preTrainLabel = svmpredict(TrainLabel, TrainData, model);
[m,n,k] = size(pic);
TestData = double(reshape(pic,m*n,k));
TestLabal = svmpredict(zeros(length(TestData),1), TestData, model);
%%
ind = reshape([TestLabal,TestLabal,TestLabal],m,n,k);
ind = logical(ind);
pic_seg = pic;
pic_seg(~ind) = 255;
figure;
imshow(pic_seg);
figure;
subplot(1,2,1);
imshow(pic);
subplot(1,2,2);
imshow(pic_seg);
%%
toc;
运行结果
可以看出来运行结果并没有那么理想，可以通过改变一些选取的像素点，或者增加一些样本来优化分割的效果。
需要注意的几个点儿
首先就是svmtrain函数的报错问题，可能运行会出现如下报错：
因为matlab2018以上版本不支持这个函数，你得下载libsvm工具箱才可以，下载网址如下：https://www.csie.ntu.edu.tw/~cjlin/libsvm/，下载完成之后解压，在matlab中选择主页-添加并包含子文件夹-选择libsvm解压到的路径，就可以成功运行啦！
还有一个问题，就是选取20个像素点的时候，如果不小心背景点和前景点选混了怎么办？没有办法，那你可能只有退出程序重新选了
不过这个程序如果操作中途退出的话，就会非常非常非常的卡，不太清楚原因，我猜测可能是向量机训练像素点的时候*终止有什么不好的影响？建议大家非意外情况不要尝试。
咳咳，最后总结一下我心中的向量机问题：向量机处理图像问题的时候，图像由一个个点组成，向量机就像一根棍子（或者面，或者超平面），把两类点分开，向量机运用相应的核函数把两类点分开，你再根据具体需要对这两类点做操作（分割，分类什么的），就这样，nice！