本发明提出了一种基于K近邻和随机游走算法的图像自动标注方法，属于图像检索领域。其特点在于采用K近邻算法构造概率图模型的顶点集，基于训练图像标签集中标签间的相互关系构造随机游走图的边集，通过随机游走算法自动标注待标注图像的标签。本发明具有良好的适应性、准确性和通用性。
1.一种基于K近邻和随机游走的图像自动标注方法，其特征在于，基于汉明损失和高斯核函数计算图像间相似度，基于K近邻构造概率模型图，基于随机游走构造图像属于各个标签的预测概率，基于标签预测概率构造图像预测标签集，依次含有以下步骤：步骤(A1)：提取图像的特征构成训练集 和测试集其中i为图像的编号， 为
第i幅图像xi的特征向量， 为连续特征，D1为连续特征的个数，为离散特征，D为特征的总个数， 为xi的标签集yi标签向量， L＝{l1,l2,…,lQ}为总标签集，lq为L中的第q标签，q为标签的编号，Q为总标签个数；
步骤(A2)：基于汉明损失和高斯函数计算xi与xj间的相似度similarity(xi,xj)(i,j＝
步骤(A3)：基于K近邻构造概率模型图其中 为 的顶点集， 为 的边集；
步骤(A4)：基于随机游走算法构造图像属于各个标签的预测概率向量其中 为xi属于lq的预测概率(i＝m+1,m+2,…,m+n，q＝1,2,…,Q)；
步骤(A5)：基于预测概率构造图像的预测标签集y′i(i＝m+1,m+2,…,m+n)；
所述基于汉明损失和高斯核函数计算图像间相似度，步骤如下：步骤(B1)基于汉明损失构造xi与xj间关于各个离散特征的相似度且i和j不可同时
步骤(B2)基于高斯核函数构造xi与xj间关于各个连续特征的相似度其中 表
步骤(B3)通过对NomSimilarity(xi,xj)和NumSimilarity(xi,xj)加权求和，构造xi与xj间的相似度所述基于K近邻构造概率模型图，步骤如下：步 骤 (C 1) ：构 造 x i 在 训练 集 中 K 近 邻其中K为 中元素的个数，其中x属于xi在χtrain中的K近邻表示在χtrain中所有特征向量对应的图像与xi间的相似度由大到小的排序中，x位于前K个中；
步骤(C2)：构造 的顶点集 其中 r为 中第一顶点的编号；
步骤(C3)：构造 的边集其中 其中s为 中第二顶点的编号， 分别为vr、vs对应的图像的标签集；
步骤(C4)：构造概率模型图所述基于随机游走构造图像属于各个标签的预测概率，步骤如下：步骤(D1)：构造基于 的转态转移矩阵其中 为 的第r+1行第s+1列上的元素，
步骤(D2)：构造基于 的跳转概率向量 其中1K+1为分量为1的K+1维度列向量；
步骤(D3)：构造基于 随机游走公式 其中k为迭代次数α为随机游走时发生跳转的概率， 为第k次随机游走时的概率分布向量，为k＝0对应的概率分布向量；
步骤(D4)：不断迭代直至得到稳定的概率分布向量 其中 满足ε为迭代误差；
步骤(D5)：计算最终的概率分布向量 其中 为lq在中的先验概率；
步骤(D6) :计算图 像属于各 个标签的预 测概率向量其中 为xi属于lq的预测概率，所述基于标签预测概率构造图像预测标签集，步骤如下：步骤(E1):计算 中属于lq的图像的标签集的平均长度步骤(E2):计算 中图像xi的标签集的预测长度步骤(E3):对 按由大到小进行排序；
步骤(E4):在 按由大到小进行排序中选取前length(yi′)个概率对应的标签，将这些标签的集合构成图像预测标签集。
一种基于K近邻和随机游走算法的图像自动标注方法
技术领域
[0001] 本发明属于图像检索领域，针对手工标注图像无法胜任互联网上海量图像标注任务的问题，利用K近邻和随机游走算法实现了对图像的自动标注。
背景技术
[0002] 本发明对互联网的海量图像实现自动标注，为图像检索提供基础支撑。传统的手工图像标注方法不但工作量大，而且不可避免地带来主观性和不精确性，让计算机实现图像自动标注势在必行。图像自动标注是让计算机自动地给图像加上能够反映其内容的语义关键词，自动标注的使用可以有效地改善目前图像检索的困境。
[0003] K近邻算法是懒惰学习方法的典型代表，它没有明显的训练过程，具有分类精度高、对异常值不敏感以及无数据输入假定的优点。随机游走算法首先由爱因斯坦在1926年以数学方式加以描述。由于自然界中的许多实体会以不可预知的方式移动，因此随机游走算法用来描述这种不稳定的移动过程，在移动过程中移动节点随机选择一个方向和速度来从当前位置移动到新的位置。随机游走算法是一种全局最优化方法，具有不易陷入局部极小值的优点。
发明内容
[0004] 本发明的目的是通过综合考虑图像的离散特征和连续特征的区别并基于汉明损失和高斯核函数来提高图像间相似度计算的准确性，基于K近邻算法构造概率图模型来降低算法的时间复杂度和空间复杂度，通过在概率图模型上进行随机游走实现图像的自动标注。本方法具有良好的适应性、准确性和通用性。
[0005] 本发明所采用的基于K近邻和随机游走算法的图像自动标注方法步骤如下：
[0006] 步骤(A1)：提取图像的特征构成训练集 和测试集其中i为图像的编号， 为
第i幅图像xi的特征向量， 为连续特征，D1为连续特征的个数，
为离散特征，D为特征的总个数， 为xi的标签集yi的标签
向量， 为总标签集，lq为L中的第q个标
签，q为标签的编号，Q为总标签个数；
[0007] 步骤(A2)：基于汉明损失和高斯函数计算xi与xj间的相似度similarity(xi,xj)(i,j＝1,2,…m+n)；步骤(A3)：基于K近邻构造概率图模型其中 为 的顶点集， 为 的边集；
[0008] 步骤(A4)：基于随机游走算法构造图像属于各个标签的预测概率向量其中 为xi属于lq的预测概率(i＝m+1,m+2,…,m+n，q＝1,2,…,Q)；
[0009] 步骤(A5)：基于预测概率构造图像的预测标签集y′i(i＝m+1,m+2,…,m+n)。
[0010] 本发明采用的基于汉明损失和高斯核函数计算图像间相似度的步骤如下：
[0011] 步骤(B1) 基于汉明损失构造xi与xj间各个离散特征的相似度(i,j＝1,2,…m+n，且i和j不可同时
大于m)；
[0012] 步骤(B2)基于高斯核函数构造xi与xj间各个连续特征的相似度其中 表
示向量 与 间的距离，
为调节因子；
[0013] 步骤(B3)通过对NomSimilarity(xi,xj)和NumSimilarity(xi,xj)加权求和，构造xi与xj间的相似度
[0014]
[0015] 本发明所采用的基于K近邻构造概率图模型的步骤如下：
[0016] 步骤(C1)：构造xi在训练集 中K近邻其中K为 中元素的个数，x表示将χtrain中的所有图像与xi间的相似度由大到小排序后，x为前K个最相似的图像之一；
[0017] 步骤(C2)：构造 的顶点集其中 r为 中顶点的编号；
[0018] 步骤(C3)：构造 的边集其中 其中s为 中顶点的编号，
分别为vr和vs对应图像的标
签集；
[0019] 步骤(C4)：构造概率图模型 本发明采用的基于随机游走算法构造图像属于各个标签的预测概率的步骤如下：
[0020] 步骤(D1)：构造基于 的转态转移矩阵其中 为 的第r+1行、第s+1列上的元
素，
[0021] 步骤(D2)：构造基于 的跳转概率向量 其中1K+1为各个分量均为1的K+1维度列向量；
[0022] 步骤(D3)：构造基于 随机游走公式 其中k为迭代次数，α为随机游走时发生跳转的概率， 为第k次随机游走时的概率分布向量， 为k＝0对应的概率分布向量；
[0023] 步骤(D4)：不断迭代直至得到稳定的概率分布向量 其中 满足ε为迭代误差；
[0024] 步骤(D5)：计算最终的概率分布向量 其中为lq在 中的先验概率；
[0025] 步骤(D6):计算图像属于各个标签的预测概率向量其中 为xi属于lq的预测概率， 本发
明采用的基于标签预测概率构造图像预测标签集的步骤如下：
[0026] 步骤(E1):计算 中属于lq的图像的标签集的平均长度(q＝1,2,…,Q)；
[0027] 步骤(E2):计算 中图像xi的标签集的预测长度(i＝m+1,m+2,…,m+n)
[0028] 步骤(E3):对 由大到小进行排序；
[0029] 步骤(E4):在 由大到小的排序序列中选取前length(y′i)个概率对应的标签，将这些标签的集合作为图像预测标签集，完成对图像的自动标注。
[0030] 本发明具有以下优点：
[0031] 1、本发明能够标注所有类型的图像，通用性强。
[0032] 2、本发明能够处理包含连续特征和离散特征的图像，适应性强。
[0033] 3、本发明基于K近邻和随机游走算法自动标图像，鲁棒性和准确性强。
附图说明
[0034] 图1本发明基于汉明损失和高斯核函数计算图像间相似度的流程图[0035] 图2本发明基于K近邻构造概率图模型的流程图
[0036] 图3本发明基于随机游走算法构造图像属于各个标签的预测概率的流程图[0037] 图4本发明基于标签预测概率构造图像预测标签集的流程图
[0038] 图5本发明的简明流程图
具体实施方式
[0039] 本发明基于汉明损失和高斯核函数构造图像相似度度量方法，基于K近邻算法构造概率图模型，通过在概率图模型上进行随机游走实现图像的自动标注。
[0040] 基于汉明损失和高斯核函数计算图像间相似度的流程如下：
[0041] (1)如图1所示，通过汉明损失计算图像间关于离散特征间相似度，通过高斯核函数计算图像间关于连续特征的相似度；
[0042] (2)将离散特征间的相似度和连续特征间的相似度进行加权平均得到图像间的相似度。
[0043] 基于K近邻构造概率图模型的流程如下：
[0044] (1)如图2所示，基于图像的K近邻构造概率图模型的顶点集，基于图像对应标签集间的相互关系构造概率图模型的边集；
[0045] (2)将顶点集和边集组成概率图模型。
[0046] 基于随机游走算法构造图像属于各个标签的预测概率的流程如下：
[0047] (1)如图3所示基于概率图模型图构造随机游走过程中的状态转移矩阵和跳转概率向量；
[0048] (2)通过随机游走得到图像在概率图模型中各个顶点上的概率分别向量；
[0049] (3)基于概率分布向量计算图像属于各个标签的概率。
[0050] 基于标签预测概率构造图像预测标签集的流程如下：
[0051] (1)如图4所示，计算属于各个标签的图像的标签集的平均长度和图像的预测标签集的长度；
[0052] (2)构造图像的预测标签集。
