智能视觉系统是机器人技术的关键之一,而图像与视频处理技术是视觉系统研究的基础工作。随着机器人在中国境内的大规模应用,人工智能已经成为“工业3.0”和“智能制造2015”的关键核心技术之一。在图像和视频处理的研究问题中,前景提取是最重要的核心问题之一[1]。
前景是相对于背景的概念,指的是图像或者单帧视频中信息的主要部分。有效提取前景是目标分割[2]、识别[3]和行为理解[4]等应用任务的基础。前景提取的有效性直接影响到各种仿生视觉系统的性能。
到目前为止,前景提取方法大致可以分为两类:一种是交互式的前景提取[5-6],另一种是全自动的前景提取[7-9]。这两种方法侧重点并不相同,交互式前景提取方法侧重于目标边沿细节,并精准地分离目标与背景,在提取过程中需要人工对图像进行标注;而全自动的前景提取方法并不考虑边沿细节,侧重于对图像目标区域的快速定位,全程无需人工交互。因此,在这个图像数量爆炸式增长的时代,人工标注的交互式前景提取方法显然无法有效处理海量的数据,探索全自动的前景提取方法进行快速有效地处理海量数据已是当前图像领域研究的趋势。全自动的前景提取方法的应用前景非常广,比如运动捕捉、目标识别[10]、图像剪辑[11]、基于内容的检索[12]等方面。
自动前景提取技术由于难度较高,尽管有不少专家学者在努力探索和研究,但是所取得的效果往往不佳,主要原因是没有目标的先验知识,提取到的前景目标常常残缺与期望的结果大相径庭。2013年, Zou等[13]使用基于图分割和条件随机场尝试建立自动分割模型,并在PASCAL VOC 2010图像数据集合上完成前景分割工作,验证了他们提出的算法的有效性。2014年,Yuan等[14]尝试使用基于图像分割算子(Nomalized cut, Ncut)分割,使用高斯变差提取关键点,构建自动前景目标提取模型,是一个基于视觉机制的全新的前景提取技术,称为基于高斯变差的自动前景提取(automatic foreground extraction based on difference of Gaussian, FMDOG)技术。对于图像目标相对显著的图像来说,该算法还是相当有效的,但是算法对于部分图像仍然出现“过提取”和“前景目标残缺”现象。
为了解决“过提取”和“前景目标残缺”的问题,本文提出了一种新的方法。该方法的技术基础是模拟视觉机制,第一眼看到是候选前景区域,然后扩大重要候选,过滤掉次要候选,根据连通性和凸球原则生成有效前景目标轮廓;然后利用遗传的机制,构造适应性函数,利用选择、交叉及变异的遗传机制,得到精确且有效的最终前景。从实验结果可以看出,本文方法非常有效。
1 基于遗传机制和高斯变差的前景提取模型本文技术框架见图 1,提出一种基于遗传机制和高斯变差的前景目标提取(Foreground Extraction with Genetic Mechanism and Difference of Guassian, GFO)方法,其关键思想在于用遗传的机制,在已有种子前景的基础上,扩展性地得到较为完整的图像前景。
首先对输入的原始图像进行三个重要运算,分别是图像分割算子(Ncut)、图像边沿检测算子Canny、图像关键点检测算子(Difference of Guassian, DoG);在此基础上,结合Ncut分割的区域和DoG得到的关键点数量,得出初始种群,然后结合边沿信息利用星凸的概念得到目标轮廓,在构造的适应性选择函数的保证下,在轮廓范围内执行遗传机制,提取出更加完整的前景目标。
1.1 初始种群确定在基于GFO算法的图像目标区域生长的过程中,假定图像中像素点的集合当成是生物的种群,那么图像中的每一个像素点就是种群中的个体GA(x, y)。在初始种群的选择中,以高斯变差前景提取技术得到的图像前景区域为初始种群,并将落在这些区域中的像素点定义为初始种子点。
1.2 目标轮廓构造通过对各种边沿检测算法的分析,本文选用边沿检测结果较为完整的Canny算子进行边沿检测,并利用得到的边沿信息逐步地构造出图像中前景目标的轮廓。
首先,分析利用Canny算子提取原始图像中的边沿曲线,结果如图 2所示,图 2(a)是原始图像,图 2(b)是使用Canny算子提取出的原始图像的边沿信息。
从图 2(b)中可以明显看到,通过Canny算子虽然得到比较完整的图像前景的边沿信息,但还存在两个问题:
1) Canny算子的主要优点在于可以比较完整地获得图像的边沿信息,但同时也会产生一些伪边沿点。以图 2为例,图(b)中定位的边沿包含了地面与天空交界的边沿信息,这一信息对图中前景的定位会产生一定的干扰。
2) 图 2(b)中获得的边沿并不是一个封闭的轮廓,无法作为一个限制条件限制遗传算法对区域的再生。
为了解决上述的两个问题,本文提出在通过高斯变差获得的初步前景区域中再次用Canny算子提取边沿信息,结果如图 3所示,图 3(a)为高斯变差分离出的图像前景目标,图 3(b)为前景目标中的边沿信息。
然后,结合原始图像边沿信息eI和图像初步前景的边沿信息eF,利用图像边沿的连通性和像素点之间的颜色相似性获得较为完整的图像前景目标的边沿信息b(x, y),具体过程如下公式所示:
$ {e_s} = {e_I} \cap {e_F} $ | (1) |
$ R' = R\left( {x, y} \right)-R\left( {{x_0}, {y_0}} \right) $ | (2) |
$ G' = G\left( {x, y} \right)-G\left( {{x_0}, {y_0}} \right) $ | (3) |
$ B' = B\left( {x, y} \right)-B\left( {{x_0}, {y_0}} \right) $ | (4) |
$ \rho \left( {\left( {x, y} \right), \left( {{x_0}, {y_0}} \right)} \right) = \sqrt {{R^{'2}} + {G^{'2}} + {B^{'2}}} $ | (5) |
$ b\left( {x, y} \right) = \left\{ \begin{array}{l} 1, \;\;\;\;{e_I}\left( {x, y} \right) = 1\& \rho \left( {\left( {x, y} \right), \left( {{x_0}, {y_0}} \right)} \right) \le \delta \\ 0, \;\;\;\;其他 \end{array} \right. $ | (6) |
式(6)中:b(x, y)的初始值为es(x, y),可以表示为式(1);ρ((x, y), (x0, y0))代表图像中相邻像素点的相似性;R(x, y)、G(x, y)、B(x, y)分别代表像素点在红层、绿层和蓝层的像素值;如式(6)所示,δ为阈值,经过大量的实验,选取为5最适合。
经过以上步骤获得了较为精确和完整的边沿信息b(x, y),结果如图 4所示,其中,图 4(a)为原始图像,图 4(b)为原始图像边沿信息eI和图像初步前景的边沿信息eF的交集,图 4(c)为提取出的图像中的边沿信息。下一步的工作就是将获得的边沿信息b(x, y)连接成为一个闭合的轮廓。
定义1 给定一个目标前景F,O是其几何中心,星凸轮廓指的是以O为中心做星型射线与边沿的最远交点或者球形封闭边界点的并集。
轮廓封闭操作具体步骤如下:
1) 计算抽取得到前景的中心点O;
2) 以中心点为起点在图像范围内做射线,相邻射线间的夹角均为α;
3) 记录与目标边沿有交点的射线,并保留交点,如果存在多个交点,则只保留离中心点最远的那个;
4) 依次计算出离各个交点最近的交点;
5) 在计算出的距离最近的两交点间构造椭圆凸包将两点进行连接;
6) 直到所有相邻交点连接完成,得到封闭的轮廓。
图 6显示的是经过以上过程获得的图像的前景轮廓信息,其中图 6(a)为原始图像,图 6(b)为图像中的轮廓信息。
依据原图Ncut分割得到的区域分布,统计闭合轮廓内各个区域的区域连续种子数量,然后将统计得到的各个区域连续种子数量进行排序,区域连续种子数量最多的区域就作为适应度强的种群,由于新增区域是由图像的前景区域向外生成的,因此定义前景区域的边界部分为适应度强的种群。优先选择这些点去产生新的像素点可以有效提高遗传的效率和质量。
图 7展示了GFO算法选种的过程,其中,图 7(a)为适应性强的种群区域,图 7(b)中种群区域边沿上的点为适应性强的种子点,本文优先选择这些点去产生新的像素点。
在GFO算法的使用过程中,首先把种群中每一个个体的基因序列定义成一个4维的向量(H, S, V, S_RGB),其中H、S和V分别代表HSV空间中的色度、饱和度和明度,S_RGB代表RGB空间中红绿蓝三层值得总和。由此可知,所定义的像素点的基因序列涵盖了HSV和RGB两个颜色空间的色彩信息,这使得图像区域的遗传增长不仅具有合理性,而且更具有可靠性。
对于初始种群中的每一个个体GA(x, y),值为1表示该像素点在种群中,0表示不在种群中。其次定义适应度强的种子点为父节点Fa,在父节点的八邻域内随机定义一个在种群中的种子点为母节点Ma,如果没有找到母节点Ma,则该像素点不能产生新的个体,如果找到母节点Ma,则通过后续的遗传机制产生一个新的个体。
首先执行选择过程得到父节点Fa和母节点Ma,然后将得到的父节点Fa基因序列与母节点Ma基因序列进行交叉,也就是将父节点Fa基因序列中的前两项和母节点基因中的后两项来组成子节点Child,交叉过程如式(7)所示:
$ \mathit{\boldsymbol{Child}} = \mathit{\boldsymbol{Fa}}\left( {\begin{array}{*{20}{c}} 1&0&0&0\\ 0&1&0&0\\ 0&0&0&0\\ 0&0&0&0 \end{array}} \right) + \mathit{\boldsymbol{Ma}}\left( {\begin{array}{*{20}{c}} 0&0&0&0\\ 0&0&0&0\\ 0&0&1&0\\ 0&0&0&1 \end{array}} \right) $ | (7) |
图 9形象地展示了交叉的过程,子节点Child的前两个基因序列来自父节点Fa,后两个基因序列来自母节点Ma,最后把经过交叉生成的子节点Child与父节点Fa八邻域内的非种群内的且在前景目标闭合轮廓内的点进行比较,如果它们的基因序列的相似度在范围内,就把该点加入到种群中。
定义2 如果一个种群内的像素点的八邻域内的所有点都是非种群内的,则将此像素点变异为种群外的像素点; 相反,如果一个种群外的像素点的八邻域内的所有像素点都是邻域内的,则将此像素点也变为种群内的点。此即为遗传变异过程,如式(8)所示:
$ GA\left( {x, y} \right) = \left\{ \begin{array}{l} 0, \;\;\;\;\;\;\;\;\sum\limits_{x-1 \le i \le x + 1, y-1 \le j \le y + 1} {G{A_{\left( {i, j} \right)}} \le 1} \\ 1, \;\;\;\;\;\;\;\;\;\sum\limits_{x-1 \le i \le x + 1, y - 1 \le j \le y + 1} {G{A_{\left( {i, j} \right)}} \le 1} \\ 不变, \;\;\;\;\;其他 \end{array} \right. $ | (8) |
图 10形象地描述了变异的过程,图 10(a)表示非种群内的点变异成为种群内的点的过程,图 10(b)表示种群内的点变异成为非种群内的点的过程。
当图像中的像素点变化小于阈值时,停止区域增长。经过大量的实验,最佳阈值为0.0002,它定义为遗传增长得到的点数占图像总点数的比例。
2 算法复杂性分析 2.1 算法结构算法1 基于遗传和高斯变差的自动前景提取算法。
1) 输入:原始图像I。
2) 输出:前景目标IGFO。
3) 获取初步前景区域IFMDOG=FMDOG(I)。
4) 利用Canny算子获得原始图像边沿信息eI和图像初步前景的边沿信息eF,并通过式(1)和式(6)得到前景边沿轮廓集合,最终根据星凸定义计算得到闭合轮廓集合。
5) 在前景区域IFMDOG内选择父节点和母节点。
6) 根据式(7)得到子节点。
7) 在父节点的八邻域内按如下规则选择子节点:a)非种群内; b)在前景目标闭合轮廓集合内;c)按照相似性阈值确定是否前景遗传。
8) 根据式(8)完成像素点变异。
9) 判断遗传条件是否成立,如果成立执行第2)步;否则执行第5)步。
2.2 时间复杂度分析本算法复杂性主要由两个部分组成:第一部分是种子前景区域获取, 第二部分是遗传生成前景目标。
第一部分需要完成两个重要的步骤,它们分别是对图像进行高斯差分处理和关键点过滤, 则第一部分的复杂度为:
$ {T_1}\left( {{N_0}, m, n} \right) = O\left( {{N_0} \times {{\left( {m \times n} \right)}^2}} \right) $ | (9) |
其中:参数N0为输入图像的总数,m×n为每幅图像的大小。
第二部分中时间复杂度主要来源于适应性种子点交叉再生, 则第二部分的复杂度为:
$ {T_2}\left( {{N_0}, p, k} \right) = O\left( {{N_0} \times {p^k}} \right) $ | (10) |
其中:参数p为适应性种子点个数,k为适应性种子点交叉再生像素点的迭代次数。
最终,算法总的时间复杂度为:
$ T = {T_1} + {T_2} $ | (11) |
本章将在现有公开的Achanta图像集[15]上进行FMDOG算法和提出的GFO算法的性能对比。在显著性检测邻域,Achanta的图像集已经被广泛使用。通过主观视觉及三个客观指标对比这两种算法的性能,从而证明本文提出的GFO算法性能上的优越性。
3.1 实验结果对比分析图 11展示了GFO算法的实验结果,其中,图 11(a)为原始图像,图 11(b)为使用FMDOG算法的结果,图 11(c)为GFO方法的实验结果。可以看出,本文方法基本上比FMDOG方法效果好。
本文采用准确率(Precision)、召回率(Recall)和Fβ三个评价指标将提出的算法与FMDOG算法进行对比。准确率(Precision)、召回率(Recall)定义公式如下:
$ \mathit{Precision} = \frac{{GT \cap SO}}{{SO}} $ | (12) |
$ \mathit{Recall} = \frac{{GT \cap BS}}{{GT}} $ | (13) |
其中:GT表示人工标注图中的目标点, SO表示前景提取算法检测出的目标点。
还有一个评价指标是Fβ,Fβ能够很好地评估分割结果的整体性能,它是由准确率和召回率综合计算而得到的,定义公式如下:
$ {F_\beta } = \frac{{\left( {1 + {\beta ^2}} \right)\mathit{Precision} \times \mathit{Recall}}}{{{\beta ^2} \times \mathit{Precision} + \mathit{Recall}}} $ | (14) |
因为前景目标提取中正确率重要程度要高于召回率,因此这里定义值β2为1,确保准确率的权值要高于召回率。
实验结果如图 12所示,从实验结果可以看出,GFO算法在这三种评价指标上的表现都要优于FMDOG算法。。
从表 1的展示可以更直观地从总体上对GFO方法与FMDOG方法在3类指标上的表现进行对比。从召回率、准确率及Fβ指标的结果数据上看,在Achanta图像集目标提取上,GFO方法提取效果优于FMDOG方法。
本次实验选取的视频序列来自公开的Fukuchi视频数据库[16],此数据库包含有10个非压缩AVI剪辑的自然场景,及每个视频对应的Groung-truth图像。本文从中选取4个具有代表性的视频序列应用于实验,有视频1(狐狸(Fox))、视频2(猫(Cat))、视频3(犀牛(Rhino))和视频4(单人滑雪(Ski))。选取的视频分辨率都为352×288。
从图 14视频数据库部分实验结果可以看出: FMDOG提取的目标存在目标缺损或者冗余等问题; 本文提出的GFO方法是对FMDOG方法的改进,它可以很好地解决FMDOG方法存在的问题。相比FMDOG方法,GFO提取到的目标更加完整和精确。
将视频数据库运用召回率、准确率及Fβ这三类指标进行评价,其结果如图 15所示。对于本实验选取的视频,虽然GFO方法和FMDOG方法在召回率上的表现相差甚小,但是在准确率和Fβ指标上GFO方法明显更优于FMDOG方法,体现了较好的抽取效果。
表 3数据说明从总体上对GFO方法与FMDOG方法在3类指标上的表现进行对比。从召回率、准确率及Fβ指标的结果数据上看,对于本文选取的4种视频,GFO方法抽取目标的效果要优于FMDOG方法。
本文借助遗传思想提出一种基于像素遗传的前景目标提取方法。由于像素的遗传需要限定其遗传范围,可通过构造目标轮廓对遗传进行限定,使其在轮廓内最大化目标的完整性。相比FMDOG方法,本文方法虽然具有较高的复杂性,但其召回率和准确率都有明显的提高。
[1] | ZHANG J, FENG S W, LI D, et al. Image retrieval using the extended salient region[J]. Information Sciences, 2017, 399(C): 154-182. |
[2] | 王丹丹, 徐越, 宋怀波, 等. 融合K-means与Ncut算法的无遮挡双重叠苹果目标分割与重建[J]. 农业工程学报, 2015, 31(10): 227-234. (WANG D D, XU Y, SONG H B, et al. Fusion of K-means and Ncut algorithm to realize segmentation and reconstruction of two overlapped apples without blocking by branches and leaves[J]. Transactions of the Chinese Society of Agricultural Engineering, 2015, 31(10): 227-234. DOI:10.11975/j.issn.1002-6819.2015.10.030) |
[3] | 王海英, 郭志芬. 一种复杂图像目标的分割与识别[J]. 北京理工大学学报, 2000, 20(2): 224-228. (WANG H Y, GUO Z F. An approach to complex target segmentation and recognition[J]. Journal of Beijing Institute of Technology, 2000, 20(2): 224-228.) |
[4] | 张惊雷, 张云飞. 基于改进分水岭算法的运动目标行为理解[J]. 计算机工程与设计, 2015, 36(7): 1880-1844. (ZHANG J L, ZHANG Y F. Behavior understanding of moving objects based on improved watershed algorithm[J]. Computer Engineering and Design, 2015, 36(7): 1880-1844.) |
[5] | PRICE B L, MORSE B S, COHEN S. Simultaneous foreground, background, and alpha estimation for image matting[C]//Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition. Washington, DC:IEEE Computer Society, 2010:2157-2164. https://www.computer.org/csdl/proceedings/cvpr/2010/6984/00/index.html |
[6] | CHEN Y T, SHENG J W. Learning-based hierarchical graph for unsupervised matting and foreground estimation[J]. IEEE Transactions on Image Processing, 2014, 23(12): 4941-4953. DOI:10.1109/TIP.2014.2323132 |
[7] | HASSAN M A, MALIK A S, NICOLAS W, et al. Foreground extraction for real-time crowd analytics in surveillance system[C]//Proceedings of the 18th International Symposium on Consumer Electronics. Piscataway, NJ:IEEE, 2014:1-2. |
[8] | WANG M, SHEN L, YUAN Y. Automatic foreground extraction of clothing images based on GrabCut in massive images[C]//Proceedings of the 2012 Information Science and Technology. Piscataway, NJ:IEEE, 2012:238-242. http://dro.dur.ac.uk/view/year/2016.html |
[9] | LEI B, XU L Q. Real-time outdoor video surveillance with robust foreground extraction and object tracking via multi-state transition management[J]. Pattern Recognition Letters, 2006, 27(15): 1816-1825. DOI:10.1016/j.patrec.2006.02.017 |
[10] | ROSENFELD A, WEINSHALL D. Extracting foreground masks towards object recognition[C]//Proceedings of the 2011 International Conference on Computer Vision. Piscataway, NJ:IEEE, 2011:1371-1378. https://www.computer.org/csdl/proceedings/iccv/2011/1101/00/index.html |
[11] | LEVIN A, LISCHINSKI D, WEISS Y A. Closed-form solution to natural image matting[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(2): 228-242. DOI:10.1109/TPAMI.2007.1177 |
[12] | SHEKHAR R, CHAUDHURI S. Content-based image retrieval in presence of foreground disturbances[J]. IEE Proceedings-Vision, Image and Signal Processing, 2006, 153(5): 625-638. DOI:10.1049/ip-vis:20045232 |
[13] | ZOU W, KPALMA K, RONSIN J. Automatic foreground extraction via joint CRF and online learning[J]. Electronics Letters, 2013, 49(18): 1140-1142. DOI:10.1049/el.2013.2100 |
[14] | YUAN Y B, LIU Y, DAI G H, et al. Automatic foreground extraction based on difference of Gaussian[J]. The Scientific World Journal, 2014, 2014: 29074. |
[15] | ACHANTA R, HEMAMI S, ESTRADA F, et al. Frequency-tuned salient region detection[C]//Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway, NJ:IEEE, 2009:1597-1604. https://link.springer.com/content/pdf/10.1007%2Fs11042-015-2965-y.pdf |
[16] | FUKUCHI K, MIYAZATO K, KIMURA A, et al. Saliency-based video segmentation with graph cuts and sequentially updated priors[C]//Proceedings of the 2009 International Conference on Multimedia and Expo. Piscataway, NJ:IEEE, 2009:638-641. https://link.springer.com/article/10.1007/s12559-016-9387-7 |