0 引言

图像语义标注的任务是给图像添加反映图像内容语义的文本标签。对图像自动标注的结果进行标注改善,可以更加全面、准确地描述图像内容。一种直观的改善方法是利用电子词典得到标签的语义距离,进而将相关度较低的标签去除^[1-2]。但是这类方法与数据集统计特性无关,标注改善的效果受字典的规模制约。利用随机游走获得数据集标签之间的统计相关性,性能优于基于词典的改善方法^[3]。通过图像的视觉特征定义标签相似度,可进一步提升标注改善性能^[4]。通过样本近邻标签投票,可以提升标签的完整性^[5]。核密度估计也可得到标签与视觉特征的初始相关度,进而通过标签图上的随机游走获得相关分数,可以达到改善标签排序^[6]。利用分类方法可以改善标注,但是其针对每一个概念训练one-versus-all 分类器的方法,不是用于大规模概念集合^[7]。比较而言,将特定标签的图像聚类,以簇为单位进行相关性估计,可以适用于较大规模的数据集^[8]。从数据集中发现数据之间潜在的语境相关信息很重要,如空间上下文关系和共现关系建模,可以提高物体识别精度^[9-12]。从数据集所蕴含的语境相关信息出发,结合标签相关约束,可通过基于图的标签传播过程获得标签相关性^[13-14]。依据视觉特征构建样本子图,依据标签相关信息构建标签子图,然后通过二步图上的随机游走也可得到图像相关性和语义组间相关性^[15]。上述语境信息传播方法,虽然能够利用标签相关信息,但是计算复杂^[16-18]。

1 标签相关图上的标注改善

图 1给出标签相关图上的标注改善过程。

令Y₀表示原始的图像-标签矩阵,Y表示改善后的图像-标签矩阵,Y_ij表示第j个标签赋予第i幅图像的概率。令S表示图像相关矩阵,S_ij表示两幅图像的视觉相关度,R表示标签相关矩阵。采用皮尔逊相关系数度量标签c_i与c_j的相关度

$\rho ({{c}_{i}},{{c}_{j}})=\frac{1}{n-1}\sum\limits_{k=1}^{n}{\left( \frac{Y_{ik}^{T}-\frac{1}{n}{{\left\| Y_{ik}^{T} \right\|}_{1}}}{{{\left( \frac{1}{n-1}\sum\limits_{k=1}^{n}{{}}{{\left( Y_{ik}^{T}-\frac{1}{n}{{\left\| Y_{ik}^{T} \right\|}_{1}} \right)}^{2}} \right)}^{1/2}}} \right)}$

(1)

以概念集为顶点,相关度为边,构造标签相关图R。 令Y_i^T 表示Y转置后的第i列,其为标签c_i的标注结果向量,令Y_j^T 表示Y的转置后的第j列,其为标签c_j的标注结果向量。 R上损失函数

$E\left( R \right)=\frac{1}{2}\sum\limits_{i=1}^{m}{\sum\limits_{j=1}^{m}{{{R}_{ij}}}}{{\left\| \frac{{{Y}_{i}}^{T}}{\sqrt{d({{c}_{i}})}}-\frac{{{Y}_{j}}^{T}}{\sqrt{d({{c}_{j}})}} \right\|}^{2}}=tr(YL{{Y}^{T}})$

(2)

其中:归一化项$d\left( {{c}_{i}} \right)=\sum\limits_{j=1}^{N}{{{R}_{ij}}},D=diag({{d}_{1}},{{d}_{2}},\ldots ,{{d}_{m}})$,标签相关图R上的拉普拉斯矩阵定义为L=I-D^-1／2RD^-1／2。 令$\nabla $_Y^TE(R)=LY^T=0,可以得到

$Y_{t}^{T}=Y_{t-1}^{T}-\alpha {{\nabla }_{Y_{t-1}^{T}}}-E={{(I-\alpha L)}^{t}}Y_{0}^{T},$

(3)

式中:α∈[0,1]为步长。对式(3)做指数展开,并略去高次项,可得到近似解:

$\begin{align} & {{Y}_{t}}^{T}=\left( I-t(\alpha L)+\frac{{{t}^{2}}}{2!}{{(\alpha L)}^{2}}-\frac{{{t}^{3}}}{3!}{{\left( \alpha L \right)}^{3}}+\ldots \right){{Y}^{T}}_{0}\approx \\ & I-t\left( \alpha L \right)+\frac{1}{2}{{\left( \alpha tL \right)}^{2}}-\frac{1}{6}{{\left( \alpha tL \right)}^{3}}Y_{0}^{T} \\ \end{align}$

(4)

考虑如下场景,如果存在若干标注有“horse”和“polo”的样本,那么“horse”和“polo”的相关性应该对标注结果起到作用。 因此,将R上的拉普拉斯矩阵表示为L=I-D^-1／2RD^-1／2=I-R′,进而,将式(2)改写为

$E({{Y}^{T}},{{R}^{'}})=\frac{1}{2}tr(Y\left( I-{{R}^{'}} \right){{Y}^{T}})=\frac{1}{2}tr\left( Y{{Y}^{T}} \right)-\frac{1}{2}tr(Y{{R}^{'}}{{Y}^{T}})$

(5)

令$\nabla $_R′E=-Y^TY=0,则R′_t=R_t-1+βY_t-1^TY_t-1,其中β∈[0,1]为步长,Y^TY为语境相关矩阵^[19]。 将式(5)按照下式展开,即可得到改善结果:

$\left\{ \begin{matrix} {{L}_{t}}=I-R{{\prime }_{t}}=I-{{R}_{t-1}}-\beta {{Y}_{t-1}}^{T}{{Y}_{t-1}}={{L}_{t-1}}-\beta {{Y}_{t-1}}^{T}{{Y}_{t-1}}, \\ {{Y}_{t}}^{T}={{Y}_{t-1}}^{T}-\alpha {{L}_{t-1}}~{{Y}_{t-1}}^{T} \\ \end{matrix} \right.$

(6)

算法归纳如下:

算法 1 标签相关图上的标注改善(Label Revelant Graph,LRG)

输入 图像标签矩阵Y₀;标签相关图R;参数α,β。

输出 改善后的图像标签矩阵Y。

第1步: 初始化R的拉普拉斯矩阵L₀=I-D^-1／2RD^-1／2,并令t=1;

第2步: 重复执行如下步骤,直至满足收敛准则:

L_t=L_t-1-βY_t-1^T Y_t-1; Y_t^T=Y_t-1^T-αL_t-1Y_t-1^T; t=t+1;

第3步: 生成标注改善结果Y。

2 融合视觉相关性的标注改善

算法1只考虑标签之间的相关性。 图 2给出了融合视觉相关性的语境传播实例。

图 2中待改善图像分别具有标签“smoke” “explosion”和“terrible”。 前两个标签“smoke”和“explosion”标签相关度较大,因此,其所描述图像的视觉相关性应适当增强。虽然“explosion”和“terrible”反映出的标签相关性较弱,但是后两幅图像视觉相关性较强,因此,它们对应的标签的相关性应适当增强,即在标注结果中应反映出这种相关性。 实际上,前两幅图像确实语境相关性较大,但只依据视觉相关性判断,语境相关性较弱,融合视觉相关性后,图像的标注结果向量将具备更高的相关性。 为了达到上述目的,定义损失函数

$E\left( S \right)=\frac{1}{2}\sum\limits_{i=1}^{m}{\sum\limits_{j=1}^{m}{{{S}_{ij}}}}{{\left\| \frac{{{Y}_{i}}}{\sqrt{d({{x}_{i}})}}-\frac{{{Y}_{j}}}{\sqrt{d({{x}_{j}})}} \right\|}^{2}}=tr({{Y}^{T}}{{L}^{v}}Y)=tr\left( {{L}^{v}}\left( Y{{Y}^{T}} \right) \right),$

(7)

其中: $d\left( {{x}_{i}} \right)=\sum\limits_{j=1}^{m}{{{S}_{ij}}},$,D=diag(d₁,d₂,…,d_n);L^v=I-D^-1／2SD^-1／2,表示视觉相关图S上的拉普拉斯矩阵。将上节的损失函数重新表示为E(R)=tr(YL^wY^T),其中标签相关图R上的拉普拉斯矩阵定义为L^w=I-D^-1／2RD^-1／2。 合并两个损失项,得损失函数

$E=\mu tr({{L}^{v}}(Y{{Y}^{T}}))+\delta tr({{L}^{w}}(Y{{Y}^{T}})),$

(8)

其中: μ、δ用于平衡视觉相关性和标签相关性。 考虑到标注改善的结果Y和基本标注结果矩阵Y₀的近似一致性假设,得到优化目标:

$\left\{ \begin{matrix} min\left\{ \mu tr({{L}^{v}}(Y{{Y}^{T}}))+\delta tr\left( {{L}^{w}}\left( Y{{Y}^{T}} \right) \right)+\left\| Y-{{Y}_{0}} \right\|{{2}_{F}} \right\}, \\ s.t. {{Y}_{ij}}\ge 0 \\ \end{matrix} \right.$

(9)

为了使得该方法适用于大规模数据集,在迭代求解过程中,每次只优化Y的一个行向量:

$\underset{{{Y}_{i}}}{\mathop{min}}\,~\left\{ {{Y}_{i}}\left( \delta {{L}^{w}}+\left( \mu {{L}_{ii}}^{v}+1 \right)I \right)Y_{i}^{T}+2\mu \sum\limits_{j=1,j\ne i}^{m}{\left( {{L}_{ij}}^{v}{{Y}_{j}}{{Y}_{i}}^{T}-2{{Y}_{0}}^{i}{{Y}^{T}}_{i} \right)~} \right\}s.t.~{{Y}_{ij}}>0,$

(10)

式中：Y₀ⁱ 表示初始标注矩阵的第i行。该问题是一个带约束条件的二次规划问题,如果直接求解这个问题,类似于内插法的时间复杂度为O(m³),m为概念集的规模。 式(10)的简化求解步骤如下:首先放松非负约束,由于目标函数对Y_i的梯度为

${{\nabla }_{{{Y}_{i}}}}E={{Y}_{i}}(\delta {{L}^{w}}+(\mu L_{ii}^{v}+1)I)+\mu \sum\limits_{j=1,j\ne i}^{m}{(L_{ij}^{v}~{{Y}_{j}}^{T}-Y_{0}^{i})},$

(11)

令$\nabla $_YiE=0,得

${{Y}_{i}}=Y_{0}^{i}-\mu \sum\limits_{j=1,j\ne i}^{m}{(L_{ij}^{v}{{Y}_{j}}^{T})}{{(\delta {{L}^{w}}+(\mu {{L}_{ii}}^{v}+1)I)}^{-1}}$

(12)

式(12)的求逆运算不适用于大规模数据,整理得

${{Y}_{i}}=Y_{0}^{i}-\mu \sum\limits_{j=1,j\ne i}^{m}{(L_{ij}^{v}{{Y}_{j}}^{T})}{{(I+(\delta {{L}^{w}}+\mu L_{ii}^{v}))}^{-1}}$

(13)

式(13)含有形如(I+M)^-1的求逆运算,对其做泰勒展开:

${{\left( I+M \right)}^{-1}}=I+\sum\limits_{i=1}^{\infty }{{{\left( -1 \right)}^{i}}}{{M}^{i}}$

(14)

得

${{(\delta {{L}^{w}}+(\mu {{L}_{ii}}^{v}+1)I)}^{-1}}\approx \frac{1}{\mu {{L}_{ii}}^{v}+1}\left( I+\sum\limits_{j=1}^{p}{{{\left( -1 \right)}^{j}}}{{\left( \frac{\delta {{L}^{w}}}{\mu {{L}_{ii}}^{v}+1} \right)}^{j}} \right)$

(15)

这样,目标函数在放松非负约束下的近似解为

${{Y}_{i}}\approx \frac{\left( {{Y}_{0}}^{i}-\mu \sum\limits_{j=1,j\ne i}^{m}{({{L}_{ij}}^{v}{{Y}_{j}}^{T})} \right)\left( I+\sum\limits_{j=1}^{p}{{{\left( -1 \right)}^{j}}}{{\left( \frac{\delta ~{{L}^{w}}}{\mu {{L}_{ii}}^{v}+1} \right)}^{j}} \right)}{\mu {{L}_{ii}}^{v}+1}$

(16)

式中:p为常量,实际求解过程中将高阶项略去; L^w可依据训练集预估计并缓存。 式(16)的解可能违反非负约束,因此,对于负值,直接令Y_ij=0。 由于初始标注结果Y的稀疏性较高,所以改方法求解速度很快。

算法归纳如下:

算法 2 融合视觉相关性的标注改善(Label-Visual Relevant Graph,LVRG)

输入 矩阵Y₀; 相关图R; μ,δ,p,k。

输出 改善后的图像标签矩阵Y。

第1步: 将具有初始标签的图像集合聚为k个簇;

第2步: 每个簇内均执行如下步骤:

初始化R的拉普拉斯矩阵L^w;

构造视觉相关图S,初始化拉普拉斯矩阵L^v;

重复执行如下步骤,直至满足收敛准则

${{Y}_{i}}\approx \frac{\left( {{Y}_{0}}^{i}-\mu \sum\limits_{j=1,j\ne i}^{m}{({{L}_{ij}}^{v}{{Y}_{j}}^{T})} \right)\left( I+\sum\limits_{j=1}^{p}{{{\left( -1 \right)}^{j}}}{{\left( \frac{\delta ~{{L}^{w}}}{\mu {{L}_{ii}}^{v}+1} \right)}^{j}} \right)}{\mu {{L}_{ii}}^{v}+1}$

第3步: 生成标注改善结果Y。

实际求解过程中,将图像按照其附带标签集合的相似度进行簇划分,不同簇之间认为语境不相关,可降低拉普拉斯矩阵L^v和L^w的维度。

3 试验结果与分析

采用NUS-WIDE^[20]与Flickr 25K^[21]数据集。NUS-WIDE数据集来自Flickr网站约5 000名用户提供的269 648幅图像和425 059个不同的标签,以5 018个基准标签进行测试。Flickr 25K数据集包含1 386个频率大于20的标签和25 000幅图像和组成。NUS-WIDE中取200 000幅图像为训练集,其余为测试集。Flickr 25K中取20 000幅图像为训练集,其余为测试集。对于测试集中的每一幅图像,通过不同的标注方法产生标签,6名志愿者独立的对标签的相关性进行判断,最后通过投票确定标签是否与图像内容相关。对图像提取征64维COLOR64特征,包含 44维颜色相关图,14维颜色纹理矩和6维颜色矩构成,384维GIST特征和PCA降维后的30维Dense-Surf特征。对比不同方法的平均标签准确率和平均标签召回率,并评测F₁。

LRG的梯度下降求解过程需要确定步长,试验中设置α=β=0.04。图 3记录了LRG的F₁随着迭代次数变化情况。从图中可以看到,随着迭代次数增加,F₁增长态势明显,说明标签相关图上的语境相关信息对于标注改善是有效的,而且当迭代次数大于60的时候,F₁较为稳定。

算法2(LVRG)中正则参数μ和δ用于平衡视觉模态和文本模态。固定μ为0.5,记录δ在集合｛0.1,0.2,0.4,0.6,0.8,1.0,1.2,1.4,1.6,1.8｝中取值变化的情况下算法的F₁,如图 4所示,在大致中部位置,系统性能较高,改善效果较为显著,而在δ小于0.6和大于1.2时,F₁下降较为明显。这说明两者的比例固定为0.5较为合适,否则融合效果就会退化。因此相关参数设置如下:μ设定为0.5,δ设定为1.0,簇数量设定为120,p设定为5。

以近邻相关学习^[5]产生的标注结果为候选标签,然后对基本标注进行改善。

对比如下方法,包括基于马尔可夫随机游走模型的图像标注改善RWR^[3],基于标签相关图的改善方法LRG(算法1),基于内容的图像标注改善方法CIAR^[4],基于标签相似图随机游走的改善方法RWTR^[6],融合视觉相关图的标注改善方法LVRG(算法2)。图 5给出了不同方法在NUS-WIDE数据集上的性能对比。

LRG方法利用标签相关图进行标签相关关系传播,较RWR性能提升16.5％。但是,上述方法均忽略了图像的视觉信息。CIAR利用图像的内容信息,通过待改善图像的视觉特征定义标签相似度,以马尔可夫随机游走的稳定状态概率较大的标签作为最终改善结果,其性能较LRG提升15.1％。RWTR与CIAR均采用生成模型的改善框架,不同于CIAR、RWTR利用图

像的视觉内容信息和标签共现信息构造标签相关图,通过图上的随机游走得到最终的标注结果,其性能较CIAR提升4.2％。本研究所提出的LVRG算法取得最好的改善效果,其性能较RWTR提升9.8％。

LRG的复杂度为O(m²n),其中,m为概念集规模,n为图像集规模,RWTR的复杂度为O(mn²),因此,如果概念集合固定,LRG方法随改善图像的数量线性增长,对于大规模图像集合,更为适用。随机从图像集中选取18 000幅图像,相似度矩阵和相关性矩阵均预计算并缓存,图 6记录了LVRG和RWTR两种方法的运行时间随数据集规模变化的情况,可知,RWTR对数据集规模近似呈现多项式复杂度O(n^0.61),而LVRG为近似线性复杂度O(n^0.43),因此,LVRG方法在运行效率上优于RWTR。图 7记录了簇数量对LVRG性能的影响。随着簇数量的变化,LVRG算法性能变化幅度在0.5％以内,因此LVRG对簇数量较为稳定。但是,对数据集进行聚类分割的策略忽略了簇间样本的相似性,当簇数量过多,性能下降趋势明显增大。

随着k的增长,相关图的邻接信息逐渐丰富,LVRG性能随之升高。但是当k超过6的时候,F₁增速放缓,因为邻接信息已经较为充分,而当邻域范围过大,相应的噪声干扰会降低方法性能。因此,试验中设置k=10。

图 8记录了LVRG性能随参数k的变化情况。

4 结论

由于“语义鸿沟”的存在,自动标注生成的图像标签并不能全面、准确地反映图像的内容。因此,对标签进行改善具有重要的意义。但是现有标注改善方法计算复杂,算法的规模化处理能力和改善性能不适用于真实环境下的大规模数据集。本研究提出一种利用语境相关图进行标注改善的方法,通过集成标签相关图和视觉相关图,得到数据集的语境相关图进行语境相关信息传播。虽然所提出的方法在评测集上取得了很好的性能,但是如何深层次的融合文本相关性和视觉相关性,实现语义关联性的深度挖掘,依然是个难点。下一步的研究工作,将通过哈希学习等方法实现更好的融合机制。