一种基于统一关联超图规约的跨媒体检索方法

摘要

本发明涉及一种基于统一关联超图规约的跨媒体检索方法，包括以下步骤：1.建立包含多种媒体类型的跨媒体数据集，提取每种媒体类型数据的特征向量；2.通过跨媒体数据集，同时为所有媒体学习得到统一特征表示映射矩阵，通过在一个关联超图中建模所有媒体数据，综合考虑了所有媒体的关联关系；3.根据映射矩阵，将不同媒体类型映射到统一空间，在统一空间中计算媒体数据的相似性；4.以任意一种媒体类型作为查询，计算其与作为查询目标的媒体类型数据的相似性，并根据相似性从大到小排序，最终输出检索结果。本发明将所有媒体数据建模在一个超图中，提高了建模的统一性和信息的多样性，提高了跨媒体检索的准确率。

说明书

技术领域

本发明涉及多媒体检索领域，具体涉及一种基于统一关联超图规约的跨媒体检索 方法。

背景技术

近年来，互联网上的多媒体数据(如图像、视频、文本、音频等)总量飞速增长，已经 成为大数据的主要内容。面对快速增长的媒体数量和丰富多样的媒体种类，用户对多媒体 数据的检索需求越来越强烈。然而，现有的搜索引擎系统(如百度等)仍然主要基于文本关 键词，通过对用户输入文本进行匹配来实现检索。另一方面，基于内容的多媒体检索能够根 据内容的相似性进行检索，但局限在单媒体检索上，即返回的检索结果媒体类型与用户输 入的媒体类型必须一致，从而限制了检索的灵活性和全面性。跨媒体检索是指用户以任意 一种媒体类型作为输入，系统经过检索后返回所有媒体类型的结果。如用户输入一幅图片， 不仅能够返回内容相关的图片，还能够得到相关文本、音频、视频等数据。

相比较单媒体检索，跨媒体检索具有两方面的优势：一方面能够返回所有媒体的 相关数据，增加了检索的灵活性；另一方面多种媒体相互促进，起到了降低噪声的修正作 用。

现有的最常见的跨媒体检索方法是基于统计分析的映射学习方法。其代表为典型 相关分析(CanonicalCorrelationAnalysis，简称CCA)。CCA通过统计分析，学习得到能够 最大化两组异构数据关联性的子空间，从而将两种媒体的特征向量映射到统一空间中。CCA 被广泛应用于如视频音源定位、视频说话人检测等研究中。另一种相关方法是跨模态因子 分析(Cross-modalFactorAnalysis，简称CFA)，由Li等人在文献“Multimediacontent processingthroughcross-modalassociation”中提出。该方法直接在映射后的空间中 最小化两组数据间的弗罗贝尼乌斯范数(FrobeniusNorm)，也取得了较好的效果。

为了利用已知的数据标注信息，Rasiwasia等人在其文献“ANewApproachto Cross-ModalMultimediaRetrieval”中提出了高层语义映射方法：先对不同媒体数据进 行CCA学习关联，再在统一空间中使用逻辑回归得到高层语义表示(相同维度的语义概念向 量)。该方法在CCA的基础上取得了一定的效果提升，但只利用了有标注的信息，且无法同时 建模两种以上媒体。另外，关联学习和高层语义表示是两个独立的步骤，无法同时考虑。针 对这些问题，Zhai等人在文献“LearningCross-MediaJointRepresentationwith SparseandSemi-SupervisedRegularization”中提出了一种基于稀疏和半监督规约的 跨媒体检索方法，同时进行关联学习和语义抽象。该方法在一个统一的框架中对不同媒体 的数据使用半监督图规约方法，且加入稀疏规约项，从而能够利用无监督的数据取得更好 的效果。另外，该方法也能够同时建模两种以上媒体。但是，它对于不同媒体分别建图，不能 同时有效考虑所有媒体的关联信息，从而在信息的全面性上有所欠缺。

发明内容

针对现有技术的不足，本发明提出了一种基于统一关联超图规约的跨媒体检索方 法，能够在映射后的统一空间中，同时将所有媒体建模在同一个超图中，从而使得模型具有 全面分析跨媒体关联的能力。该方法同时学习不同媒体的统一特征表示映射矩阵，且利用 超图表达复杂关联的能力，使得模型的信息更加完整，提高了跨媒体检索的准确率。

为达到以上目的，本发明采用的技术方案如下：

一种基于统一关联超图规约的跨媒体检索方法，用于同时学习不同媒体的统一空 间映射，进而得到不同媒体的统一特征表示，实现跨媒体检索，包括以下步骤：

(1)建立包含多种媒体类型的跨媒体数据集，提取每种媒体类型数据的特征向量；

(2)通过跨媒体数据集，同时为所有媒体类型学习得到统一特征表示映射矩阵；

(3)根据映射矩阵，将不同媒体类型映射到统一空间，在统一空间中计算媒体数据 间的相似性；

(4)进行跨媒体检索时，以任意一种媒体类型作为查询，按照步骤(3)计算其与作 为查询目标的媒体类型数据的相似性，并根据相似性从大到小排序，最终输出检索结果。

进一步，上述一种基于统一关联超图规约的跨媒体检索方法，所述步骤(1)中的多 媒体类型为五种媒体类型，包括：文本、图像、视频、音频和3D模型。

进一步，上述一种基于统一关联超图规约的跨媒体检索方法，所述步骤(1)中的特 征向量具体为：文本数据是提取隐狄雷克雷分布特征向量；图像数据是提取词袋特征向量； 视频数据是提取关键帧后，对关键帧提取词袋特征向量；音频数据是提取其梅尔频率倒谱 系数特征向量；3D数据是提取其光场特征向量。

进一步，上述一种基于统一关联超图规约的跨媒体检索方法，所述步骤(2)中的映 射矩阵学习过程，通过在一个关联超图中建模所有媒体的数据(包括标注数据和未标注数 据)，能够同时考虑所有媒体之间的关联关系，使得学习得到的映射矩阵能够全面地利用媒 体类型之间、媒体类型内部的数据关联关系。另外，该方法考虑到了映射矩阵的稀疏性，对 数据噪声有抑制作用。

进一步，上述一种基于统一关联超图规约的跨媒体检索方法，所述步骤(3)的相似 性定义为两个媒体数据属于同一语义类别的概率。

进一步，上述一种基于统一关联超图规约的跨媒体检索方法，所述步骤(4)的跨媒 体检索是指，使用一种媒体类型的数据作为查询，返回另一种媒体类型的相关结果。步骤 (2)中的学习过程同时学习对于所有媒体的映射矩阵，但一次检索只在两种媒体间进行。该 步骤计算得到所述相似性后，根据相似性从大到小排序，最终输出检索结果。

本发明的效果在于：与现有方法相比，本方法能够通过构建跨媒体统一关联超图， 充分考虑了媒体类型之间、媒体类型内部的关联关系，同时学习所有媒体的统一特征表示 映射矩阵，进而得到多种媒体类型的更加精确的统一特征表示。通过综合考虑不同媒体的 信息及其关联，兼顾统一特征表示的稀疏性，进一步提高了统一特征表示的有效性，提高了 跨媒体检索的准确率。

本方法之所以具有上述发明效果，其原因在于：在建模过程中以跨媒体统一关联 超图为中心。一方面，将所有媒体类型数据统一建模在一张超图中(而不是对不同媒体类型 分别建图)，大大提高了建模的统一性与模型信息的全面性。另一方面，相比起普通图，超图 表达复杂关联结构的能力更强，能够起到更好地描述跨媒体关联的作用，进一步提高了该 方法关联学习及语义抽象的能力。通过上述一种基于统一关联超图规约的跨媒体检索方法 学习得到的统一特征表示，具有更高的有效性，从而提高了跨媒体检索的准确率。

附图说明

图1是本发明的基于统一关联超图规约的跨媒体检索方法的流程示意图。

图2是本发明的超图构建过程、统一特征表示学习过程的示意图。

具体实施方式

下面结合附图和具体实施例对本发明作进一步详细的描述。

本发明的一种基于统一关联超图规约的跨媒体检索方法，其流程如图1所示，包含 以下步骤：

(1)建立包含多种媒体类型的跨媒体数据集，并将所述数据集分为训练集和测试 集，提取每种媒体类型数据的特征向量。

本实施例中，所述的多种媒体类型为文本、图像、视频、音频和3D模型。对于不同媒 体类型的特征向量提取方法如下：文本数据是提取隐狄雷克雷分布特征向量；图像数据是 提取词袋特征向量；视频数据是提取关键帧后，对关键帧提取词袋特征向量；音频数据是提 取其梅尔频率倒谱系数特征向量；3D数据是提取其光场特征向量。

本方法同样支持其它种类的特征，例如图像纹理特征、颜色特征、深度学习特征， 视频运动特征、音频均方根、3D形状特征等。

用s表示媒体跨媒体训练集中的媒体类型数量，对于第r种媒体类型，我们定义n^(r)为其数据个数。训练集中的每个数据有且只有一个语义类别。

定义为第r种媒体类型中的第p个数据的特征向量，其表示结构为一个d^(r)×1 的向量，其中d^(r)表示第r种媒体的特征向量维度。

定义的语义标签为其表示结构为一个c×1的向量，其中c表示语义类别 的总量。中有且只有一维为1，其余为0，表示该数据的语义类别值为1的列所对应的标 签。

(2)通过训练集的数据，同时为所有媒体类型学习得到统一特征表示映射矩阵。

建立目标函数如下：

$\underset{P^{\left(i\right)},\mathrm{...},P^{\left(s\right)}}{min}\underset{r=1}{\overset{s}{\Sigma }}\left(\underset{p=1}{\overset{n^{\left(r\right)}}{\Sigma }}\right||P^{{\left(i\right)}^T}{X}_p^{\left(r\right)}+b{1}_c-y_p^{\left(r\right)}|{|}_F^2+\lambda \left|\right|P^{\left(r\right)}\left|{|}_{2,1}\right)+\Omega \left(O\right)$

其中P⁽¹⁾,...,P^(s)为跨媒体数据集中所有s种媒体类型的映射矩阵，其中上标(s) 表示第s种媒体类型的映射矩阵，矩阵的维度为d^(s)×c，可以将原始的特征向量从d^(s)维的 空间映射到一个统一的c维的统一空间中。P^T表示矩阵P的转置。即为数据通过 映射矩阵变换到统一空间中后的向量(维度为c×1)。1_c表示一个c×1的全1列向量，b 为偏移项，用于构造线性规约模型。||Z||_F表示矩阵Z的Frobenius范数，其定义为： 上式中λ表示权重参数，||Z||_2,1表示矩阵Z的l_2,1范数，其定义为： 最小化||Z||_2,1能够使得矩阵Z具有稀疏性。上述公式的第一项使得 原始数据通过映射矩阵，映射到统一空间后的统一特征表示能够尽可能与其类别标签一 致。另外，通过l_2,1范数，使得学习到的统一特征表示具有稀疏性，起到抑制噪声的作用。

Ω(O)为跨媒体统一关联超图规约项，O代表所有映射到统一空间后的媒体数据。 图2以4种媒体为例，示意了本发明的超图构建过程和统一特征表示学习过程。下面先介绍 统一关联超图的构建方法：

定义统一关联超图G＝{V，E，H，w}，其中V为点集，E为超边集，H为关联矩阵，w为超 边权重集。V，E，H，w的构造方法如下：

V：所有映射到统一空间后的媒体数据。

E：对于V中的任意一点v_i，将其k近邻使用一条超边连接，如此构成超边集。

H：对于V中的任意一点v_i及E中任意一条超边e_j，若v_i∈e_j，则令H_ij＝1，否则H_ij＝0。

w：本方法中，令所有超边的权重w_j均为1。

我们根据文献“Learningwithhypergraphs:Clustering,classification,and embedding”中的推导，定义该统一关联超图G的拉普拉斯：

$L=I-D_v^{-\frac{1}{2}}{\mathrm{HwD}}_e^{-1}{H}^T{D}_v^{-\frac{1}{2}}$

其中，I为单位矩阵，D_v为所有顶点的度数构成的对角矩阵，设共有p个顶点，则该 矩阵大小为p×p，对角线上的值为对应点的度数。D_e为所有超边度数构成的对角矩阵，设共 有q条超边，则该矩阵大小为q×q，对角线上的值为对应超边的度数。其它符号上述已经介 绍过。

推导得到：

$\Omega \left(O\right)=tr\left(O^{T}LO\right)={\Sigma }_{r=1}^s{\Sigma }_{k=1}^{s}tr\left(P^{{\left(r\right)}^T}{X}_a^{\left(r\right)}{L}_{rk}{X}_a^{{\left(k\right)}^T}{P}^{\left(k\right)}\right)$

其中，分别代表第r种、第k种媒体的所有数据构成的矩阵。以第r种媒 体为例，该矩阵的大小应为d^(r)×n^(r)。L_rk代表在统一关联超图的拉普拉斯L中，按照对应媒 体类型r的行以及对应媒体类型k的列所取出的子矩阵。

该目标函数通过迭代求解，经过推导，迭代求解公式为：

其中，P^(r)代表第r中媒体类型在该轮迭代的结果，代表第j种媒体类型在上一 轮迭代的结果。Y^(r)为第r种媒体所有数据对应的标签构成的矩阵。D^(r)为对角矩阵，第i行对 角线上的值定义为$D_i^{\left(r\right)}=\frac{1}{2\left|\right|P_i^{\left(r\right)}\left|\right|}.$为中心矩阵，定义为$H_n^{\left(r\right)}=I-\frac{1}{n^{\left(r\right)}}{1}_{n^{\left(r\right)}}{1}_{n^{\left(r\right)}}^T.$我 们初始化所有P^(r)为随机值，之后每次迭代更新所有的P^(r)，即可得到对应每种媒体类型的 映射矩阵。

(3)根据映射矩阵，将不同媒体类型映射到统一空间，在统一空间中计算媒体数据 间的相似性。

该步骤首先将测试集中的每种媒体类型数据，通过上述学习的映射矩阵映射到一 个统一空间中，以获得多种媒体类型的统一特征表示：

设我们要求第r种媒体的第p个数据的统一特征表示，则

由于在统一空间中已经不存在媒体类型的区别，在后面的公式中我们省略媒体类 型，仅仅用x_p代表一个媒体数据，用y_p代表其语义类别，o_p代表其统一特征表示。

定义一个数据属于概念t的概率为：

其中，N_k(o_p)表示数据o_p在统一空间中的k近邻，σ(z)＝(1+exp(-z))^-1为sigmoid函 数。

定义两个数据的相似性为：

$Sim(o_p,o_q)=\underset{t}{\Sigma }p(y_p=t|o_p)p(y_q=t|o_q)$

(4)任取测试集中的两种媒体类型A与B，将A中的每个数据作为查询样例，B为查询 目标进行检索，计算查询样例和B中数据的相似性，将相似性按照从大到小排序，得到媒体 类型B的相关结果列表。

该步骤中使用的测试方式是一种媒体到另一种媒体的检索，跨媒体统一检索是指 提交任意一种媒体类型作为查询，返回的结果是另一种媒体的数据，并对返回的数据进行 相似性的排序，用户所看到的是返回数据及其相似性构成的列表，按相似度从大到小排序。 用户提交任意媒体数据作为查询样例，系统自动从跨媒体数据集中检索出另一种媒体的相 关结果。例如提交一段北京大学的介绍音频作为查询，除了能搜索出相关的音频结果以外， 还能自动检索出所有相关的文本、图像、视频和3D。

下面的实验结果表明，与现有方法相比，本发明基于统一关联超图规约的跨媒体 检索方法，可以取得更高的检索准确率。

本实施例中的数据集为XMedia异构媒体数据集进行实验，该数据集由文献 “Learningcross-mediajointrepresentationwithsparseandsemi-supervised regularization”(作者X.Zhai,Y.Peng,andJ.Xiao，发表在2014年的IEEETransactions onCircuitsandSystemsforVideoTechnology)提出，包括5种媒体类型：图像、文本、 视频、音频、3D。数据量分别为：5000段文本，5000张图像，1000段音频，500段视频和500个3D 模型。该数据集包含20个不同的类别，每个类别具有同样的媒体类型数量，即250段文本， 250张图像，50段音频，25段视频和25个3D模型。通过随机选取，将数据集的80％作为训练 集，剩余20％作为测试集。我们测试了以下3种方法作为实验对比：

现有方法一：文献“Relationsbetweentwosetsofvariates”(作者 H.Hotelling.)中的典型相关分析(CCA)方法，可以同时分析两组变量之间的相关性，学习 出映射子空间使得在子空间中两组变量的相关性最大，这是跨媒体检索领域的典型方法， 也是很多涉及两种数据建模工作的基本方法；

现有方法二：文献“ANewApproachtoCross-ModalMultimediaRetrieval” (作者N.Rasiwasia,J.Pereira,E.Coviello,G.Doyle,G.Lanckriet,R.Levy和 N.Vasconcelos，发表在2010年的ACMinternationalconferenceonMultimedia)中的方 法，该方法先对不同媒体数据使用CCA学习其关联，再在CCA学习到的子空间中使用逻辑回 归，对数据进行语义表示；

本发明：本实施例的方法。

实验采用信息检索领域常用的MAP(meanaverageprecision)指标来评测跨媒体 检索的准确性，MAP是指每个查询样例检索准确性的平均值，MAP值越大，说明跨媒体检索的 结果就越好。

表1.与现有方法的对比实验结果

从表1可以看出，本发明的方法取得了最好的跨媒体检索结果。对比方法中，方法 一只建模了跨媒体数据的一一对应关系，不能对数据的语义信息进行有效建模。另外，该方 法一次只能建模两种媒体，对多种媒体之间的校正作用的利用不足。方法二在方法一的基 础上引入了高层语义信息，取得了更好的效果，但一方面只使用了标注样本的信息，没有使 用未标注样本，从而训练数据的多样性受到限制；另一方面，其并没有对所有媒体统一建 模，不能同时对所有媒体学习映射，利用的关联信息有限，因此取得的提升不够明显。本发 明的方法不仅考虑了未标注样本，也能同时将所有媒体数据统一建模到一张关联超图中， 提高了建模的统一性和信息的多样性。本发明同时采用了稀疏规约项，起到了抑制噪声的 作用。因为上述优势，本方法在上述所有检索任务上都取得了显著的提高。

显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精 神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围 之内，则本发明也意图包含这些改动和变型在内。