目录

使用超像素分割与图割的网状遮挡物检测算法

标题 使用超像素分割与图割的网状遮挡物检测算法
年份: 2017 年 7 月
GB/T 7714: [1]刘宇, 金伟正, 范赐恩, et al. 使用超像素分割与图割的网状遮挡物检测算法[J]. 计算机应用, 2018, 38(001):238-245.

摘要

针对由于摄影角度受限,一些自然图像被铁丝网、栅栏、外墙玻璃接缝等网状遮挡物所遮挡的问题,提出了一种用于修复此类图像的网状遮挡物检测算法。对于现有算法使用单像素颜色特征和固定形状特征造成对颜色和形状不均的网状遮挡物检测效果不佳的弊端,首先将图像进行超像素分割,引入颜色与纹理直方图的联合特征来描述超像素块,将基于像素分类问题转换成基于超像素的分类问题,抑制了局部颜色变化造成的误分类;然后,使用图割算法将超像素块进行分类,使网状结构能够沿着光滑的边缘进行延伸,不受固定的形状限制,提高了对异形网状结构的检测准确率,并且不依赖Farid等提出的算法(FARID M S,MAHMOOD A,GRANGETTO M.Image de-fencing framework with hybrid inpainting algorithm.Signal,Image and Video Processing,2016,10(7):1193-1201)所需的人工输入;其次使用新的联合特征训练支持向量机(SVM)分类器并对所有未被分类的超像素块进行分类,得到准确网状遮挡物掩膜;最后,使用SAIST算法对图像进行修复。实验中,获得的网状遮挡物掩膜比Farid等提出的算法所得到的保留了更多的细节,在修复算法不变的同时显著提升了图像修复效果。在使用相同网状遮挡物掩膜的情况下,使用SAIST算法修复得到的图片在峰值信噪比(PSNR)和结构相似性(SSIM)上分别比Farid等提出算法提高了3.06和0.02。新的掩膜检测算法联合SAIST修复算法的总体修复效果对比Farid等提出算法及Liu等提出的算法(LIU Y Y,BELKINA T,HAYS J H,et al.Image de-fencing.Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition.Washington,DC:IEEE Computer Society,2008:1-8)有了明显提升。实验结果表明,所提算法提升了网状遮挡物的检测准确性,得到了效果更好的去除网状遮挡物的图像。

https://gitee.com/xiaomoon/image/raw/master/Img/image-20210509182225599.png
Examples of image de-fencing

算法流程

超像素分割

为了突破单个像素的特征限制,同时保留图像的局部细节特征,本文算法使用简 单 线 性 迭 代 聚 类 ( Simple Linear Iterative Clustering,SLIC)算法对图像进行超像素分割预处理。SLIC算法将图像上的每个像素点n由一个五维特征向量$[I_n,a_n,b_n,x_n,y_n]^T$表示,$l_n,a_n,b_n$截是点n在CIELAB (CIEL* a* b* 1976 color space)色彩空间的L,a,b三个通道上的像素值,$x_n,y_n$为点n的坐标。图像中的每一个像素点通过K-means聚类的方法分配其最邻近的聚类中心的标号值,像素点n距离一个聚类中心$C_i=[l_i,a_i,b_i,x_i,y_i]^T $的距离D表示为:

$$ \begin{array}{l} D_{s}=d_{l a b}+\frac{m}{S} d_{x y} \\ d_{\text {lab }}=\sqrt{\left(l_{n}-l_{i}\right)^{2}+\left(a_{n}-a_{i}\right)^{2}+\left(b_{n}-b_{i}\right)^{2}} \\ d_{x y}=\sqrt{\left(x_{n}-x_{i}\right)^{2}+\left(y_{n}-y_{i}\right)^{2}} \end{array} $$

其中$d_{lab}$和 $d_{xy}$分别表示点 n 和聚类中心 $C_i$的颜色相似性和空间距离; m/S 调整两者之间的权重,其值越大,每超像素块中的像素在空间上的分布越紧凑,$S = \sqrt{ N / P}$,N 为图像像素点的个数,P 为希望产生超像素块的近似数量,S 实际上表示每个超像素块的大致宽度

https://gitee.com/xiaomoon/image/raw/master/Img/image-20210509183629935.png
Flow chart of the proposed algorithm

整个 SLIC 算法的流程如下:

  1. 在图像中以 S 为步长均匀地划分网格,以网格的中心作为初始化聚类中心点$C_i=[l_i,a_i,b_i,x_i,y_i]^T$
  2. 将聚类中心移至 $n* n $邻域的最小梯度位置
  3. 对于图像中的每个像素点,将其分配给 $2S* 2S$ 矩形范围内$D_s$最小的聚类中心
  4. 计算新的聚类中心点
  5. 计算残留率,如果残留率小于一定阈值或者像素点的标号不再改变,算法收敛。重复3~5直至收敛

https://gitee.com/xiaomoon/image/raw/master/Img/image-20210509183954824.png
SLIC 聚类分割过程

使用图割算法的超像素块融合

从图 2( c) 中可以看到,经过超像素处理后,所有的网状遮挡物和背景都被超像素块的边界所分离开了,但新的问题是网状遮挡物自身也被分割成了小块。本文使用图割算法来解决这个问题,通过合理地构建能量函数,使网状遮挡物的小超像素块与背景的超像素块分别与其毗邻的相似超像素块进行融合,使局部的超像素块相互组合生成一个大的结构,如图2( d) 所示。利用图割算法,本文算法可以在不知道网状遮挡物的颜色特征和结构特征的情况下,自动从彩色图像中提取出类似物体供后续算法进行筛选和分类.

将超像素块映射成一个带权图,为每个超像素块赋予不同的标号,构建一个能量函数来使用图割算法,能量函数的一般形式为:

$$ E(f)=E_{data}(f)+\gamma E_{smooth}(f) $$

其中: 数据项 $E_{data}$表示同一标号顶点的不相似性,光滑项$E_{smooth}$表示不同标号顶点的相似性,γ 为平衡因子,f 表示图中各顶点被赋予的标号。利用图割算法使两者之和 E 尽可能地小,就能够得到边界光滑分类准确的图像分割结果。在许多图割算法的应用中,都是将每个像素点作为带权图的顶点,用像素点的灰度值作为特征来计算相似性。这种做法直观且易于实现但由于其将每一个像素点都作为带权图的顶点,使得这个图的尺寸十分庞大,对其使用图割算法在时间复杂度和空间复杂度上都非常高,并且最后得到的分割结果也会由于过于追求边界的光滑性而抹去许多细节元素,不利于本文对细小的网状结构的检测需求。

同 SLIC 算法一样,本文在 CIELAB 色彩空间中对超像素图像使用图割算法。对于每个超像素块,取其平均颜色来表示其颜色特征计算相似性。为了减弱环境光照对分割结果的影响,每个超像素块只取 a、b 两个颜色空间,计其平均像素值为Ia、Ib。初始标号通过 K-means 算法获得,将图像分为 K 类,每类中心点的 a、b 通道像素值计为$I_{ca},I_{cb}$。

令$E_{data}(f) = \sum _{p \in P} D_p(f_p)$, 其中$D_{p}\left(f_{p}\right)=\left(I_{p a}-I_{c a}\right)^{2}+\left(I_{p b}-I_{c b}\right)^{2}$

对于光滑项$E_{smooth}$:$E_{\text {smooth }}(f)=\sum_{p, q \in P} V_{p, q}\left(f_{p}, f_{q}\right)$

其中:

$$V_{p, q}\left(f_{p}, f_{q}\right)=\left\{\begin{array}{c}0, \quad p, q \text { 不毗邻或 } f_{p}=f_{q} \\ \mathrm{e}^{-\left[\left(I_{p a}-I_{q a}\right)^{2}+\left(I_{p b}-I_{q b}\right) 2\right]}, \text { 其他 }\end{array}\right. $$

$p,q $表示不同的超像素块,$f_p,f_q$表示超像素块被分配的标号。能量函数构建完成后,利用 GraphCuts 算法,重新分配标号最小化能量函数( 如图 4) 。在能量函数优化过程中,可能会有一些标号被完全合并,最终得到 K’种标号,K' ≤ K。

https://gitee.com/xiaomoon/image/raw/master/Img/image-20210509190332069.png
Graph Cuts 分割优化过程中能量函数的数值变化

图割结果如图 2( d) 所示,图中将相同标号的超像素块用相同的纯色替换。仅通过聚类算法得到的超像素块分类分布十分零散,很难从中分类定位出不同的物体; 经过图割算法处理后的新的超像素块分类勾勒出了图像中各个物体的轮廓,其中就包括本研究所需的网状遮挡物。

遮挡物样本超像素块的获得与 CCTP 特征提取

本文算法从上述处理中在自然图像中得到了 K' 类物体,接下来利用笔画宽度特征从 K 类物体中筛选出最可能的网状遮挡物

利用 Li 等用在字符检测中的笔画宽度检测算法,取出第 k 类物体中连通域面积最大的区域,求出其平均笔画宽度 $SW_{mean}(k)$ 与笔画宽度的方差 $SW_{var}( k) $。通过对网状遮挡物的形状特征分析可知,其通常比较细小并且在图像中宽度变化不大,因此网状遮挡物的两种比划宽度特征应该都较小,因此对所有的 k ∈ K,将 $SW_{mean}(k)$与 这两 $SW_{var}( k) $种特征进行升序排序,得到每类的两个排名 $R_m( k) ,R_v( k)$ ,那么最可能的网状遮挡物的标号 $f $就可依式( 9) 得到: $fg = arg min(R_m(k)+R_v(k))$

对于图像内所有的超像素块 p,求出其颜色平均值 $MC_p$,根据下式对它们进行标记:

$$ L(p)=\left\{\begin{array}{ll} 1, \quad f_{p}=f g \\ -1, & \left\|M \boldsymbol{C}_{p}-\boldsymbol{M} \boldsymbol{C}_{f g}\right\|_{2}>2 \star\left\|\boldsymbol{S} \boldsymbol{C}_{f g}\right\|_{2} \\ 0, & \text { 其他 } \end{array}\right. $$

当超像素块的标号为 fg 时,它是已经确定的网状遮挡物对象,标记为 1; 当超像素块的平均颜色远离已知的网状遮挡物的颜色时,将其标记为 - 1。这样就将图像中的部分超像素块分为了两类: 一类是网状遮挡物超像素块,如图 2( e) 所示;另一类是背景超像素块,如图 2( f) 所示。

SVM分类

求出所有超像素块的 CCTP 特征,将标记过的正负样本的 CCTP 特征构造一个训练样本集用于训练一个 SVM 二分类器。 $$ T = {(x_i,y_i)\mid y_i{1.-1},i = 1,2,…,n} $$ 其中: $x_i$是标记过的超像素块的 66 维 CCTP 特征,$y_i= 1 $时表示该超像素块为已标记的网状遮挡物,$y_i= - 1 $时表示该超像素块是已标记过的背景超像素块

在线性可分的情况下,使训练样本分开的超平面描述为: $w\sdot x +b = 0$

最优超平面就是能将训练样本集完全正确分开,同时满足距离超平面最近的两类点间隔最大。求解这样的超平面问题,可表示为下述的约束优化问题:

$$ \begin{array}{l} \min \frac{1}{2}\|\boldsymbol{w}\|_{2}^{2} \\ \text { s.t. } y_{i}\left(\boldsymbol{w} \cdot \boldsymbol{x}_{i}+\boldsymbol{b}\right) \geqslant 1, i=1,2, \cdots, n \end{array} $$

上式的拉格朗日目标函数为: $L(w,b,\alpha) = \frac {1}{2}||w||^2_2 - \sum^n_{i=1} \alpha_i[y_i(w\cdot x_i+b)-1]$

其中: $\alpha _i \geq 0$为各样本对应的拉格朗日系数。

对 w 和 b 分别求其偏导函数,令其等于 0,则该约束优化问题可转化为较简单的二次函数寻优问题:

$$ \begin{aligned} & \max _{\boldsymbol{\alpha}} Q(\boldsymbol{\alpha})=\sum_{k=1}^{n} \alpha_{k}-\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}\right) \\ \text { s.t. } & \sum_{i=1}^{n} \alpha_{i} y_{i}=0, \alpha_{i} \geqslant 0, i=1,2, \cdots, n \\ \boldsymbol{w}^{*}=\sum_{i=1}^{n} \alpha_{i}^{*} \boldsymbol{x}_{i} y_{i} \\ \boldsymbol{b}^{*}=y_{i}-\boldsymbol{w}^{*} \boldsymbol{x}_{i}^{*} \end{aligned} $$

α*是求出的最优解,w*和 b*为对应的最优平面参数。本文使用 CCTP 特征对目标超像素块进行分类的问题常常是线性不可分的,可利用核函数将该线性分类问题推广到非线性的情况,使用下述的高斯核函数:

$$ \kappa\left(\boldsymbol{x}_{1}, \boldsymbol{x}_{2}\right)=\exp \left(-\left\|\boldsymbol{x}_{1}-\boldsymbol{x}_{2}\right\|_{2}^{2} / 2\right) $$

上试可变为求解:

$$ \begin{aligned} & \max _{\boldsymbol{\alpha}} Q(\boldsymbol{\alpha})=\sum_{k=1}^{n} \alpha_{k}-\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} \boldsymbol{\kappa}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \\ \text { s.t. } & \sum_{i=1}^{n} \alpha_{i} y_{i}=0, \alpha_{i} \geqslant 0, i=1,2, \cdots, n \end{aligned} $$

则分类函数为: $f(\boldsymbol{x})=\operatorname{sgn}\left(\sum_{i}^{n} \alpha_{i}^{*} y_{i}\boldsymbol{\kappa}\left(\boldsymbol{x}_{i},\boldsymbol{x}\right)+\boldsymbol{b}^{*}\right)$

使用$f(\boldsymbol{x})$对所有标记为 0 的超像素块的 CCTP 特征进行分类,这样所有的超像素块就被分成了两类: 网状遮挡物超像素块与背景超像素块。

最后,将所有属于网状遮挡物超像素块的像素赋值为255,剩下的赋值为 0,就得到了一张标记出了网状遮挡物位置的掩膜。由于图像修补算法的基本原理就是在未被破坏的图像区域寻找与待修补区域相近的图像块来修补被破坏的位置,如果算法得到的掩膜将所有的网状遮挡物全部标记为待修补区域,那么图像修补算法将会利用背景的图像块修补原来为网状遮挡物的区域,最终得到没有网状遮挡物的图像,也就成功实现了网状遮挡物去除。

https://gitee.com/xiaomoon/image/raw/master/Img/image-20210509210840553.png
Examples of CCTP feature vector

实验分析与对比

  • 数据集:PSU-NRT
  • 超参数:$S = 10,\lambda = 100, m = \lambda * S = 1000$,聚类数量$K=10$,光滑项与数据项的平衡因子 $\gamma = 0.35$
  • 实验平台:64 位 Windows 10,Matlab R2016b

网状遮挡物检测结果对比

https://gitee.com/xiaomoon/image/raw/master/Img/image-20210509213431647.png
本文网状遮挡物检测算法替换 Farid 算法中网状检测部分后的恢复效果比较

不同算法特征分类效果对比

https://gitee.com/xiaomoon/image/raw/master/Img/image-20210509213656061.png
使用不同的特征对超像素块进行分类的结果比较

不同算法对网状遮挡物的修复效果与质量评价参数对比

https://gitee.com/xiaomoon/image/raw/master/Img/image-20210509213844511.png
PSNR and SSIM comparison results of

https://gitee.com/xiaomoon/image/raw/master/Img/image-20210509213906827.png
3 种修复算法得到的恢复结果比较

总体恢复效果对比

https://gitee.com/xiaomoon/image/raw/master/Img/image-20210509214039480.png
3 种恢复算法结果对比