点击上方“”，选择加""或“”
重磅干货，第一时间送达 本文转自|新机器视觉
鉴于图割方法的明显优势，采用Graph Cuts算法和Grab Cut该算法分别对木材表面的单目标和多目标缺陷图像进行分割试验，以总结传统图形切割方法的不足和改进算法的优点。
针对传统Graph Cuts算法只能分割灰度图像，运行时参数的选择比较复杂，存在算法效率和精度低的缺陷。这两种方法分别对三种木材表面缺陷的活节、虫眼和死节图像进行了分割实验。为了验证Grab Cuts该方法的适用性用含有多个缺陷目标的木板图像进行图像分割验证。
结果表明，缺陷图像的目标和背景的种子点选择直接影响Graph Cuts算法的分割结果，Graph Cuts算法计算效率低，分割时间长，相邻像素差，分割结果不理想。改进后的Grab Cut算法是迭代的Graph Cuts，虽然该方法还需要在图像分割前人工绘制初始矩形框，但操作相对简单，分割结果可以完全关闭缺陷区域边界，不受木材表面缺陷类型、数量、尺寸和缺陷形状的影响，分割效果好，分割速度快，抗噪声强，可使用灰色图像和彩色图像。
图割(Graph Cuts)交互式图像分割算法是一种基于图论组合的优化方法，其基础是最大流算法，将图像分割问题转化为能量函数的最小化，通过最小化能量函数实现图像的最佳分割。首先，建立能量函数：
E(L) ＝R(L) ＋λB(L) (1)
式中:R(L)是区域项，表示区域属性；B(L)是边界项，表示边界属性；λ 当λ 当边界项较小时可以忽略时λ 当图像较大时，所有点都被赋予相同的标记。
设P＝｛p1，p22，…，pN2 ｝ 是像素集合，L={0，1}是像素标记集，0表示背景，1表示目标；像素标记可以表示为从P到L的映射， 记作fp＝｛fp｜fp∈Ｌ｝。
因此，公式(1)中的区域项表示为R(f)＝Rp(fp)，p∈P，用Rp(fp)判断像素p分配给某个标记的可能性。能量函数中的区域项通常取概率的负对数，预定义的种子点作为目标和背景的采样，以估计目标和背景的灰度直方图分布。对于目标/背景的二值分割，区域项可以表示为:
类型(2)代表像素p类型(3)代表像素分配给目标区域的可能性p随着可能性的增加，分配给背景区的可能性，Rp(?) 的值会减小，从而可通过最小化能量函数来实现对图像的准确分割。式(1)的边界项可表示为：
式中:p和q边界项邻像素，边界项反映了图像边界像素值的不连续性；N为4邻域或8邻域系统。公式(4)可以通过变分模型写成:
其中， T(fp,fq） 满足指标函数 ：
B<p,q> 为对像素p、q不连续的惩罚值：
式中:Ip、Iq为像素p、q的灰度值；dist(p,q)是p和q的距离；δ图像噪声。p和q越相近，则B<p,q>越大；若p和q差别较大，则B<p,q>趋近于0 。当B<p,q>当图像分割获得最小能量值时，两个像素更容易分配到不同的区域。
Graph Cuts算法源于图论，通过最小化能量函数实现图像分割 。首先，我们应该构建一个具有非负边权的能量函数公式的网络图G＝ (V,E)其中，作为图像V为顶点集，相应图像的边集为像素点集P，E。V它包含两个特殊的顶点，叫源节点S(代表目标)T(代表背景)，所以构建的网络图也叫S-T图。
1956年Ford提出了网络流理论，论证了网络图中最大流和最小流的等价性。通过最大流/最小切割定理，可以解决类型（1）的能量函数，包括扩展路径(augmenting paths)推进法和重标记(push-relabel)法律。本试验采用后者。
由于Graph Cuts该算法只能分割灰度图像，参数选择复杂，效率和分割精度低。Blake从以下三个方面进行改进，形成Grab Cut算法 ：
1)废弃灰度直方图，选择高斯混合模型(GMM 模型)描述颜色信息的概率分布，实现彩色图像分割；
2)在GMM在模型参数估计过程中，可进化迭代算法取代最小能量估计，提高分割精度；
3)为了减少用户交互的工作量，通过非完全标记(incomplete labeling)像素标记方法（交互中没有明确的目标）。该方法只需在目标周围画一个矩形框。
Grab Cut算法将图像表示为矢量Z＝ ｛z1,z2,…,zn,…,zN｝ ，这样，图像的分割就会转化为每个像素对应的不透明度数组α＝ ｛α1,α2,…,αn,…,αN｝αN｜(αn∈［0,1］)，αn值为0(背景)或1(目标)，图像目标和背景模型分别使用k维的全协方差矩阵GMM表达，通常k＝5。向量k＝｛k1,k2,…,kn,…,kN｝为每个像素的独立GMM(参数来自目标或背景，取决于目标或背景αn的值 ，从而将目标提取问题转化为能量函数的优化问题，然后采用图切法进行解决。
对于RGB吉布斯(Gibbs)能量函数为：
式中:E为能量；U代表数据项；V代表光滑项；α代表不透明度；θ灰度直方图代表图像目标和背景；z代表图像灰度值。U定义为：
其中， D(αn,knθ,zn) ＝ -log p(zn｜αn,kn,θ) －
式中： π(•) 代表该高斯模型的样本数在总样本中的混合权重系数； p(•)代表高斯概率分布。所以数据项又可表示为：
则高斯混合模型的参数模型为：
其中： π(α,k)代表每个高斯概率分布的样本数在总样本数中的权值； μ(α,k） 代表高斯模型的均值；代表协方差； α代表不透明度Alpha值；k代表高斯混合模型参数。
平滑项Ｖ可以采用RGB彩色空间的欧几里德距离求得：
式中：C代表相邻像素对； γ为自适应λ参数； β为常数项。
若把一个更接近真实情况的标记赋予某个像素，则将会惩罚更小的数据项，这样会使总能量函数减少，不断地迭代，最终收敛至最优分割，这样便将Grab Cut算法的图像分割问题转化成求解最小割的问题。
Grab Cut算法的图像分割步骤如图1所示。
本试验采用的计算机为Intel(R) Core(TM)i5-4200U CPU，1.60G硬盘，4G RAM，操作系统为Windows 7 with SP1，编程软件为Visual Studio 2010 C＋＋，OpenCV库。
采用Graph Cuts算法对单缺陷目标图像进行图像分割，木材样本如图2，灰度图像如图3。
采用Graph Cuts算法对图3a活节缺陷图像进行分割，参数λ＝1。试验中对活节灰度图像进行3次人工种子点标记(其中红色为目标标记，蓝色为背景标记，且标记画笔的半径是5个像素)，如图4所示，对应的分割结果如图5所示。
Graph Cuts 算法是基于像素级的分割，不能准确评估像素属于前景或者背景的概率，由于活节缺陷边缘与背景的灰度值差距较小，即使标定的目标种子点像素数量很多(如图4c)，但仍存在较严重的欠分割情况。对应图4a、b、c的分割初始化时间分别为41140.06，41022.37和40904.52ms，图像分割所用时间分别为146268.57，278338.17和388243.09ms。可见，种子点素数越多，初始化所用的时间越短，图像分割所用的时间越长。
采用同样的方法对图3b的虫眼缺陷图像进行分割：设置λ＝1，3次人工标记种子点的结果如图6，对应的分割结果如图7。由试验结果可知，虫眼缺陷图像的分割结果与活节缺陷分割相似，分割结果受标定的前景/背景种子点像素数量影响，且都存在一定的欠分割问题。对应图7a、b、c的分割初始化时间分别为41152.20，41038.55和40894.37ms，图像分割时间分别为177052.53，368657.00和417434.91ms。种子点素数越多，初始化所用的时间越短，图像分割所用的时间越长。
对图3c死节缺陷图像进行分割：设λ＝1，3次人工标记种子点的结果如图8，对应的分割结果如图9。可见，采用Graph Cuts算法对标注像素点多的死节缺陷图像能够实现完整分割，但死节缺陷的分割轮廓曲线不平滑，且存在部分过分割情况。对应图8a、b、c的初始化时间分别为40933.91，40921.05和40916.92ms，图像分割所用时间分别为34677.35，371604.00和413967.44ms。
综上所述，采用Graph Cuts算法对木材表面缺陷图像进行分割时，由于Graph Cuts算法对能量函数采用一次性最小化，对目标和背景的人工标记的种子点选取十分重要，选取结果直接影响分割结果；且该算法对相邻像素间的区分度较差，对活节和虫眼缺陷进行分割时存在欠分割问题，对死节缺陷进行分割时出现过分割情况。该算法的初始化时间随种子点标记的像素数的增加而缩短，运行时间相反。
采用Grab Cut算法对含有单缺陷目标、多缺陷目标的木材表面缺陷图像进行分割试验。试验的参数设定为距离参数β＝0.1和GMM更新迭代次数k＝5。木材缺陷图像为512×512的彩色图像。在试验过程中，首先输入相同的初始化矩形框。
1）单活节图像分割：图10a为单个活节样本的原图像，图10b为初始化矩形框，图10d为分割结果，图10c为分割结果的局部放大图，图10e为分割结果与原图像的掩模。虽然活节缺陷的像素灰度值与背景的灰度值的差距较小，但Grab Cut算法仍然可以得到完整的分割轮廓， 分割时间为108144.784ms。由图10e可见，分割结果与原图的吻合度较高，分割效果较好；从图10c分割结果局部放大图可见，Grab Cut算法进行图像分割时，会使活节缺陷内部出现零星的欠分割区域。
2）单虫眼图像分割：图11a为单虫眼样本的原图像，图11b为初始化矩形框，图11d为分割结果，图11c为分割结果的局部放大图，图11e为分割结果与原图像的掩模。虽然活节缺陷的像素灰度值与背景的灰度值的差距较小，但Grab Cut算法仍然可以得到完整的分割轮廓， 分割时间为87329.92ms。由图11e可见，分割结果与原图的吻合度较高，分割效果较好；从图11c分割结果局部放大图可见，Grab Cut算法进行图像分割时，会使虫眼缺陷内部出现零星的欠分割区域。
3）单死节图像分割：图12a为单虫眼样本的原图像，图12b为初始化矩形框，图12d为分割结果，图12c为分割结果的局部放大图，图12e为分割结果与原图像的掩模。虽然活节缺陷的像素灰度值与背景的灰度值的差距较小，但Grab Cut算法仍然可以得到完整的分割轮廓， 分割时间为77545.63ms。由图12e可见，分割结果与原图的吻合度较高，分割效果较好；从图12c分割结果局部放大图可见，Grab Cut算法进行图像分割时，会使虫眼缺陷内部出现零星的欠分割区域。
综上所述，Grab Cut算法进行木材表面缺陷分割，能够得到完整的分割轮廓，且不受背景噪声影响，分割速度快，且对目标与背景像素差别较大的死节和虫眼缺陷分割速度更快，但分割结果均会出现少量的欠分割问题。
多活节缺陷分割试验(图13)：图13a为多活节样本的原图像，图13b为初始化矩形框，图13c为分割结果，图13d为分割结果与原图像的掩模。可见，Grab Cut算法能将木材表面的每一个活节缺陷都分割出来，且分割轮廓曲线完整，分割结果与原图的吻合度较高，但在背景中识别出两个过分割噪点，分割时间为13.337s。
2）多虫眼缺陷分割试验(图14)：由图14可见，Grab Cut算法能将木材表面的每一个虫眼缺陷都分割出来，且分割轮廓曲线完整，分割效果好，分割结果与原图吻合度较高，分割时间为10.913s。
3） 多死节缺陷分割试验(图15)：由图15可见，
Grab Cut算法能将木材表面的每一个死节缺陷都分割出来，且分割轮廓曲线完整，但是右下角死节缺陷的轮廓上存在少量过分割噪点，分割时间为11.634s。
由图13、14、15的分割结果可知，Grab Cut算法能够快速锁定多个木材表面缺陷的边界轮廓，且不受木材表面缺陷的多少、大小和缺陷轮廓形状的影响，分割效果好，分割速度快，抗噪性强，运行时间短。但是Grab Cut算法对木材表面缺陷分割时会出现零星的欠分割或者过分割情况，且分割前需要用户人工画定初始化矩形框。
在「」公众号后台回复：即可下载全网第一份OpenCV扩展模块教程中文版，涵盖等二十多章内容。
在「」公众号后台回复：即可下载包括等31个视觉实战项目，助力快速学校计算机视觉。
在「」公众号后台回复：即可下载含有个基于实现20个，实现OpenCV学习进阶。
交流群
欢迎加入公众号读者群一起和同行交流，目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群（以后会逐渐细分），请扫描下面微信号加群，备注：”昵称+学校/公司+研究方向“，例如：”张三 + 上海交大 + 视觉SLAM“。请按照格式备注，否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。在群内发送广告，否则会请出群，谢谢理解~