基于随机游走模型的物体识别

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ￣ｔ算机工程与应用　基于随机游走模型的物体识别　林　霄，肖国强，吴松，邱开金　ＬＩＮ　Ｘｉａｏ，ＸＩＡＯ　Ｇｕｏｑｉａｎｇ，ｗｕ　Ｓｏｎｇ，ＱＩＵ　Ｋａｉｊｉｎ　西南大学计算机信息科学学院，重庆４００７　１　５　Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ＆Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ，Ｓｏｕｔｈｗｅｓｔ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｏｎｇｑｉｎｇ　４００７　１　５，Ｃｈｉｎａ　ＬＩＮ　Ｘｉａｏ，ＸＩＡＯ　Ｇｕｏｑｉａｎｇ，ｗＵ　Ｓｏｎｇ，ｅｔ　ａ１．Ｒａｎｄｏｍ　ｗａｌｋ　ｍｏｄｅｌ　ｂａｓｅｄ　ｏｂｊｅｃｔ　ｒｅｃｏｇｎｉｔｉｏｎ．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２０１３，４９（２１）：１４５—１５１．　Ａｂｓｔｒａｃｔ：Ｔｒａｄｉｔｉｏｎａ１　ｏｂｊｅｃｔ　ｒｅｃｏｇｎｉｔｉｏｎ　ｍｅｔｈｏｄｓ　ｉｎ　ｃｏｍｐｕｔｅｒ　ｖｉｓｉｏｎ　ａｒｅ　ａｌｍｏｓｔ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｖｉｓｕａｌ　ｆｅａｔｕｒｅｓ，ｗｈｉｃｈ　ｃａｎｎｏｔ　ｐｅｒｆｏｒｍ　ｗｅｌｌ　ｉｎ　ａ　ｍｏｒｅ　ｃｏｍｐｌｅｘ　ｃｉｒｃｕｍｓｔａｎｃｅ．Ｔｏ　ａｔｔａｃｋ　ｔｈｉｓ　ｃｒｉｔｉｃａｌ　ｐｒｏｂｌｅｍ，ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａ　ｎｏｖｅｌ　ｏｂｊｅｃｔ　ｒｅｃｏｇｎｉｔｉｏｎ　ｍｅｔｈｏｄ　ｗｈｉｃｈ　ｃｏｍｂｉｎｅｓ　ｏｂｊｅｃｔ　ｒｅｃｏｇｎｉｔｉｏｎ　ｗｉｔｈ　ｔｈｅ　ｐｒｉｏｒ　ｒｅｌａｔｉｏｎｓ．Ｄｕｒｉｎｇ　ｔｈｅ　ｔｒａｉｎｉｎｇ　ｓｔａｇｅ，ｓｔｒｕｃｔｕｒｅｄ　ｐｒｅｓｅｎｔａｔｉｏｎ　ｏｆ　ｔｈｅ　ｐｒｉｏｒ　ｒｅｌａｔｉｏｎｓ　ｉｓ　ａｐｐｌｉｅｄ　ｔｈｒｏｕｇｈ　ａ　ｈｙｂｒｉｄ　ｇｒａｐｈ　ｗｈｉｃｈ　ｃｏｎｔａｉｎｓ　ｉｍａｇｅ　ｓｉｍｉｌａｒ　ｓｕｂ—ｇｒａｐｈ，ｓｅｍａｎｔｉｃ　ｓｉｍｉｌａｒ　ｓｕｂ－ｇｒａｐｈ　ａｎｄ　ｔｈｅ　ｒｅｌａｔｉｏｎｓ　ｂｅｔｗｅｅｎ　ｔｈｅ　ｔｗｏ　ｓｕｂ．ｇｒａｐｈｓ．Ａ　ｒａｎｄｏｍ　ｗａｌｋ　ｍｏｄｅｌ　ｉｓ　ｔｈｅｎ　ｃｏｎｓｔｕｒｃｔｅｄ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｈｙｂｒｉｄ　ｇｒａｐｈ．Ｄｕｒｉｎｇ　ｔｈｅ　ｒｅｃｏｇｎｉｔｉｏｎ　ｓｔａｇｅ，ａ　ｎｅｗ　ｔｅｓｔｉｎｇ　ｉｍａｇｅ　ｎｏｄｅ　ｉＳ　ａｄｄｅｄ　ｔｏ　ｔｈｅ　ｒａｎｄｏｍ　ｗａｌｋ　ｍｏｄｅ１．Ｔｈｅ　ｒｅｌａｔｉｏｎｓ　ｂｅｔｗｅｅｎ　ｔｈｉｓ　ｎｏｄｅ　ａｎｄ　ｔｈｅ　ｎｏｄｅｓ　ｉｎ　ｔｈｅ　ｒａｎｄｏｍ　ｗａｌｋ　ｍｏｄｅｌ　ａｒｅ　ｃａｌｃｕｌａｔｅｄ．Ｒａｎｄｏｍ　ｗａｌｋｓ　ｗｈｉｃｈ　ｓｔａｒｔ　ｆｒｏｍ　ｔｈｅ　ｔｅｓｔｉｎｇ　ｉｍａｇｅ　ｎｏｄｅ　ａｒｅ　ｐｅｒｆｏｒｍｅｄ　ａｔ　ｔｈｅ　ｒａｎｄｏｍ　ｗａｌｋ　ｍｏｄｅ１．Ｔｈｅ　ｐｒｏｂａｂｉｌｉｔｙ　ｒａｎｋ　ｐｒｏｖｉｄｅｄ　ｂｙ　ｔｈｅ　ｒｅｓｕｌｔ　ｏｆ　ｒａｎｄｏｍ　ｗａｌｋｓ　ｗｉｌｌ　ｓｅｒｖｅ　ａｓ　ｔｈｅ　ｒｅｃｏｇｎｉｔｉｏｎ　ｒｅｓｕｌｔ　ｏｆ　ｔｈｅ　ｔｅｓｔｉｎｇ　ｉｍａｇｅ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｉｌｌｕｓｔｒａｔｅ　ｔｈｅ　ｖａｌｉｄｉｔｙ　ａｎｄ　ｓｔｒｏｎｇｅｒ　ｒｅｃｏｇｎｉｔｉｏｎ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｅｔｈｏｄ．　Ｋｅｙ　ｗｏｒｄｓ：ｏｂｊｅｃｔ　ｒｅｃｏｇｎｉｔｉｏｎ；ｐｒｉｏｒ　ｒｅｌａｔｉｏｎ；ｈｙｂｒｉｄ　ｇｒａｐｈ　ｍｏｄｅｌ；ｒａｎｄｏｍ　ｗａｌｋ　ｍｏｄｅｌ　摘要：针对传统物体识别算法中只依赖于视觉特征进行识别的单一性缺陷，提出了一种结合先验关系的物体识别算　法。在训练阶段，通过图模型结构化表示先验关系，分别构建了图像一图像、语义一语义两个子图以及两子图之间的联　系，利用该图模型建立随机游走模型；在识别阶段，建立待识别图像与随机游走模型中的图像节点和语义节点的关系，在　该概率模型上进行随机游走，将随机游走的结果作为物体识别的结果。实验结果证明了结合先验关系的物体识别算法的　有效性；提出的物体识别算法具有较强的识别性能。　关键词：物体识别；先验关系；混合图模型；随机游走模型　文献标志码：Ａ　中图分类号：ＴＰ７５１．１　ｄｏｉ：１０．３７７８／ｊ．ｉｓｓｎ．１００２．８３３１．１２０１－０２１３　１　引言　对各类标记的空间位置关系和共现性进行学习，并用遗传　自然界中的物体具有不同的属性，如颜色、形状、纹理　算法完成对图像的最佳标定。文献［２］中提出一种能量模　等，这些不同的属性在大脑的不同部位被加工。人之所以　型来描述各类标记间的关系，并完成对区域的标定。这说　能在各种不同的情境中，通过视觉系统轻松地识别物体，　明了建立一个用以描述标记问内在联系的关系模型对ＲＬ　是因为人在对各类物体的学习过程中不仅记忆了该物体　的重要性。可视物体识别（ｖｉｓｕａｌ　Ｏｂｊｅｃｔ　Ｃｌａｓｓ　Ｒｅｃｏｇｎｉｔｉｏｎ，　的相关特征，还在大脑中建立了各类物体之间的先验关　ＶＯＣＲ）的主要工作是预测图像中某类语义的范例是否出　系。然而在计算机视觉系统中要建立由这种先验关系组　现。而当图像中包含多类物体时，ＶＯＣＲ和ＲＬ所需解决的　成的统一机制却是十分困难的，这也使得物体识别成为了　问题是一致的。基于以上思想，将关系模型应用到ＶＯＣＲ　计算机视觉研究领域中一个非常具有挑战性的课题。　的过程中是可行的。　区域语义标定（Ｒｅｇｉｏｎ　Ｌａｂｅｌｉｎｇ，ＲＬ）是近年来国内外　传统的物体识别算法大致可分为基于局部特征的物　研究的热点问题之一。它的主要工作是对图像中的特定区　体识别和基于全局特征的物体识别两类。基于局部特征　域进行语义标定。文献［１】中用贝叶斯网络构造概率模型　的物体识别算法通过对图像中兴趣点（区域）的检测，得到　基金项目：中央高校基本科研业务费专项资金重点项目（Ｎｏ．ＸＤＪＫ２０１１Ｃ０７３）。　作者简介：林霄（１９８８一），男，硕士，主要研究领域为数字图像处理；肖国强（１９６５一），男，博士，教授；吴松（１９８６一），男，硕士；邱开金　（１９７４一），男，副教授。Ｅ—ｍａｉｌ：ｊａｍｅｓ．１ｉｎｘｉａｏ＠ｇｍａｉｌ．ｃｏｒｎ　收稿日期：２０１２—０１—１２　修回日期：２０１２．０３．０７　文章编号：１００２—８３３１（２０１３）２１—０１４５—０７　ＣＮＫＩ出版日期：２０１２－０６—０１　ｈｔｔｐ：／／ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ｋｃｍｓ／ｄｅｔａｉｌ／１１．２１２７．ＴＰ．２０１２０６０１．１４５７．０２５．ｈｔｍｌ　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　关于图像的局部信息以完成对物体的识别。例如，文献［３］　中采用基于特征点检测以及不同类型物体的特征点所构　成的独特空间几何结构来进行物体识别。基于全局特征　应用十分广泛的图像颜色信息表示方法。它是对图像的　颜色特征进行统计所得到的关于特征的统计直方图，具有　有效地反映图像中颜色组成分布的优点。对于ＲＧＢ三通　道下的彩色图像，首先将其转化到ＨＳＶ颜色空间，然后把　每个颜色通道里面的颜色信息都量化为１０个不同的等级。　的物体识别算法试图找到能代表图像中所有信息的全局　特征，并以该全局特征进行物体识别。这不仅包括简单的　统计方法，例如像素均值、直方图特征等，还包括复杂的降　维算法，例如主成分分析　、独立成分分析　、非负矩阵分解　。　其中降维算法　的主旨在于把原图像投影到一个最能表　达原图像数据的低维子空间中。无论是基于局部特征的　物体识别算法，还是基于全局特征的物体识别算法都未将　先验关系应用到物体识别的过程中，因此很难建立一个有　效且完善的由先验关系组成的统一机制。本文以建立一　个这样的统一机制为出发点，提出了一种结合先验关系的　物体识别算法。在训练阶段，首先，用图像的全局特征相　似度建立图像相似性图（Ｉｍａｇｅ　Ｓｉｍｉｌａｒｉｔｙ　Ｇｒａｐｈ，ＩＳＧ）；同　时，用领域本体中各语义对象的相对距离建立语义相似性　图（Ｓｅｍａｎｔｉｃ　Ｓｉｍｉｌａｒｉｔｙ　Ｇｒａｐｈ，ＳＳＧ）；其次，采用ＪＳＥＧ算　法　对图像进行分割，得到图像的子区域集，选取部分得到　的子区域作为训练样本，利用支持向量机（Ｓｕｐｐｏ￣Ｖｅｃｔｏｒ　Ｍａｃｈｉｎｅ，ＳＶＭ）进行训练得到一个对于多类物体的分类　器。用该分类器建立图像与语义间的关系，并形成统一的　混合图模型。在识别阶段，首先，在统一的图模型中新建　一个待识别图像节点，通过提取其全局特征建立该节点与　其余图像节点的全局特征相似性关联。其次，对待识别图　像进行分割，利用训练得到的分类器建立待识别图像节点　与语义节点问的语义相似性关联。最后，以该节点为起始　节点进行随机游走，并把随机游走的结果作为该图像中的　物体识别的结果。实验结果验证了该算法的有效性和可　靠性，以及其较好的物体识别性能。　基于随机游走模型的物体识别算法流程图如图１所示。　先验知识　构建领域本体　图像集／　图像分割｝—＇Ｈ子区域特征提取　全局特征提取　图像语义相似性　ＳＶＭ　相似性图　蔫曼　＿＿＿—　。１：：：：！！！　：　兰　构建语义　相似性图　磊　厂———Ｌ］　识别阶段广－—＿！—一　随机游　识别　走模型　结果　图１　基于随机游走模型的物体识别算法流程图　２　ＩＳＧ的建立　２．１全局特征的提取　在图像处理中，常用的描述图像全局信息的特征大致　分为三类：颜色、纹理和形状特征。本文选取图像的颜色　和纹理作为全局特征。　２．１．１颜色特征　颜色直方图（Ｃｏｌｏｒ　Ｈｉｓｔｏｇｒａｍ，ＣＨ）是一种在图像处理　通过直方图的统计，对于每幅彩色图像都可以得到一个相　关的颜色特征。　２．１．２纹理特征　局部二元模式（Ｌｏｃａｌ　Ｂｉｎａｒｙ　Ｐａｔｔｅｒｎ，ＬＢＰ）　是近年来　提出的一种有效的纹理描述方法，它通过比较图像中每个　像素与其邻域内像素灰度值的大小，利用二进制模式表示　的比较结果来描述图像的纹理，可以对灰度图像中局部邻　近区域的纹理信息进行有效度量和提取。ＬＢＰ特征突出的　优点是对目标灰度变化不敏感且计算简单迅速。在本文　中，每幅图像都可以得到一个ＬＢＰ纹理特征。　２．２全局特征的相似性度量　在完成全局特征的提取并对其进行归一化处理之后，　定义了衡量各全局特征间相似性的度量。设图像集，中图　像的数量为Ⅳ，对于第ｉ张图片　，ｆ∈［１，Ｎ】，存在全局特征　向量　．。这里用两个向量间夹角的余弦函数作为其相似　性度量，则对于全局特征向量ｌ’。，＇ｌ，。，ｐ，ｑ∈［１，Ⅳ】，其相似性　可表示为：　（Ｖｐ，Ｖｑ　２．３　建立ＩＳＧ　计算图像之间的相似性度量是建立图像相似性图的　基础。此外，建立一个图模型，还需要选取建立图模型的　方法，例如：最邻近图（ｋ－Ｎｅａｒｅｓｔ　Ｎｅｉｇｈｂｏｒ，ｋＮＮ），ｓ阀值邻　近图，指数加权图等。文献［１１］中证明了利用ｋＮＮ图建立　的图模型在大多数情况下具有较好的相关性表达能力。　因此，在本文中基于ｋＮＮ图来建立图像相似性图。在该图　模型中，每幅图像都对应了图中的一个节点。对于任意图　像　，取与其相似度较大的ｉ个图像作为该图像的相邻节　点。相应地，把图像　，在图中所对应的节点与其近邻节点　用以，＿为始点的有向边连接起来，并把它们之间的相似度　作为该有向边的权值。由此，完成了对图像相似性图的建　立。图２举例说明了一个由４个节点组成且　＝１时建立的　图。值得注意的是，由于图像，　与图像　并不一定互为近　邻，所以建立的图像相似性图并非是一个对称的图模型。　图２图像相似性图的结构　３　ＳＳＧ的建立　语义相似性图描述了各类语义之间的关系。不同语　义间的关系是很难通过一般的解析式来获得的。语义问　林霄，肖国强，吴松，等：基于随机游走模型的物体识别　图３语义构建的本体图　的关系是由先验知识决定的，例如：有大象、马、汽车三种　语义，存在先验知识“大象和马都是属于动物”，可以推出　来建立一个统一的混合图模型。由于图像与语义间是多　对多的关系，要直接建立图像与语义之间的关系是复杂　的。但是，子区域与语义间的关系是多对一的关系，建立　大象与马的语义相似性强于大象与汽车的语义相似性。　所以，本文利用先验知识来完成对语义相似图的建立。　它们之间的关系相对简单。同时，一幅特定的图像中又包　含了多个特定的子区域，因此，可以通过建立图像中的子　区域与语义之问的关系来完成对图像相似性图与语义相　似性图之间的关系建立。　３．１领域本体　Ｇｒｕｂｅｒ在文献［１２］中对本体进行了定义：本体是一种　共享概念模型的形式化规范说明。作为知识和概念描述　的重要工具，本体具有领域对象描述手段和描述方法，既　４．１　图像分割　本文选取了经典的ＪＳＥＧ算法　作为图像的分割算法。　ＪＳＥＧ算法主要包括两个步骤：颜色量化和空间分割。颜色　可以用于描述简单的事实，又可以用于描述抽象的概念，　可用于解决图像语义描述中存在的问题。由于本体的建　立是对先验知识库的结构化、形式化的规范，所以本文就　以建立本体的形式来建立先验知识库。为了对实验中所　需要的１２种语义进行描述，在本体中定义了２０种语义，利　用其先验关系手工构建了该本体的层次结构。　量化的目的是为了减少原始彩色图像的颜色数量，以降低　算法复杂度。原图像中像素点的像素值被量化为　个类，　并把量化后的图像作为类图；在分割过程中，通过处理与　类图相关的数据得到分割结果。图４显示了ＪＳＥＧ算法对　一３．２建立ＳＳＧ　类似于图像相似性图，树形本体中叶节点所对应的每　一张图像的分割结果。　种语义都对应了语义相似性图中的一个节点。要建立　语义相似性图，关键在于量化定义出任意两种语义间的相　似性测度。在本文中通过已构建的领域本体来表达语义　间的关系。如图３所示，在本体中两个节点的语义相似性　与这两个节点在树形结构中的最短路径相关㈣。设有两种　不同的语义　与　，则它们的语义相似度可表示为：　１　—墨量　■　■簟　（ａ）原始图像　（ｂ）分割后的图像　图４　ＪＳＥＧ算法分割结果　ｆ（Ｓｐ，Ｓｑ）＝　ｅ　（２）　４．２子区域特征提取　在完成对原图像的分割之后，需要提取所得到子区域　的底层特征。其中颜色特征是最直观、最明显的特征，是　其中，Ｄｉｓｔ（Ｓ　，Ｓ　）表示在本体中构成　与　问最短路径　的边的数量。　图像内容组成的基本要素，是人识别图像的主要感知特征　之一。通过ＪＳＥＧ分割算法而得到的子区域具有色彩相似　性，容易想到选取其平均色彩作为子区域的颜色特征。但　是由于ＪＳＥＧ分割算法的误差导致分割出来的子区域中包　在完成对语义问的相似性度量的定义之后，便可以利　用其建立语义相似性图。同样的，采用ｋＮＮ图的方法完成　语义相似性图的建立。　含了并不属于该区域的部分，可能会使平均色彩的颜色特　４统一图模型的建立　基于上述第２章与第３章所介绍的流程，能分别得到　征不能准确地表示该子区域的颜色特性。因此，选取子区　域的主色彩作为区域的颜色特征。主色彩是通过计算子区　图像相似性图和语义相似性图。但这对于建立一个完整　的关系模型是不够的，还需要找出这两类子图之间的联系　域在ＨＳＶ颜色空间下的颜色直方图，并取其中最大的组所　包含的像素点的像素平均值。最终得到一个由平均色彩和　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　主色彩组成的颜色特征。　与全局纹理特征提取相似，在提取子区域的纹理特征　时，也使用ＬＢＰ纹理特征的提取方法。由此可以得到子区　域的纹理特征，并将颜色特征和纹理特征级联得到子区域　的特征。　４．３基于ＳＶＭ的分类器训练　在完成对图形子区域的特征提取和归一化后，可以得　到一系列由颜色特征和纹理特征组成的特征向量。为了　建立图像中的子区域与语义之间的关系，需要利用ＳＶＭ对　图５统一的混合图模型　各类物体的样本子区域的特征进行训练，得到一个多类物　（不同类型的边表示不同种类的关系）　体的分类器。通过该分类器就可以得到各子区域被判别　为某一语义类别　，　，　【１，１２］的概率，即子区域与语义之间　的关系。设图像集，中第　张图像　，ｆ　［１，Ⅳ］含有子区域　数为　。在多类物体分类器的训练阶段，为１２个语义类　别中的每一类选取了４０个样本子区域进行训练。在完成　训练后，可以对图像中的任意子区域进行识别。由于在图　像分割过程中可能会产生一些零散的过分割区域，这些区　域不仅对图像中的物体识别没有贡献，还会对其他区域的　识别造成影响，因此，只建立了图像中部分子区域与语义　之间的关系。通常情况下，过分割产生的子区域面积总是　相对较小，可以通过取子区域中区域面积较大的部分来减　小过分割子区域对识别产生的影响。取每幅图像中面积　前Ｉｓ×　Ｉ，ｓ　ｅ［ｏ，１］大的子区域，则对任意图像中面积大小　为前Ｉ　ｓ×　Ｊ的子区域Ｒ　，ｆ∈［１，Ⅳ］，ｍ∈Ｊ１，Ｉｓ×　ｌｌ，通过该　分类器都可以得到一个概率集Ｐ　＝｛Ｐ：，　ｌ　，　［１，１２１｝，其中　Ｐ：Ｊ　　表示子区域ＪＲ　被分类器判别为语义　的概率。同　时，把Ｐ　中的最大值　Ｐ　作为子区域Ｒ　与语义　（　。　代表…　所对应的语义类别）的联系。实验中，根据经　验把ｓ设置为０．９。　４．４建立统一图模型　图像库中的任意图像与该图像下的子区域都是一对多　的关系，并可计算得到任意图像下的任意子区域Ｒ　与语义　的量化关系。在建立统一图模型时，如果子区域　与语　义　之间存在这种量化关系，把该子区域所处的图像　在　图像相似性图中的节点与语义　在语义相似性图中的节点　用一条双向边连接起来，并把…Ｐ：一。　一口　　作为该有向边的权值。　基于上述方法，完成了对图像相似性图与语义相似性　图之间的关系的构建，从而得到了一个统一的混合图模型，　如图５所示。　孽随　机游走模型的基本思想是，以一个节点为起始点开　…始遍历一张图。对于任意一４－节点，遍历者以概率１一　游　节点，并称　为随机跳转发生概率。每次游走后，可以得　到一个新的概率分布，该概率分布描述了经过该次游走后　图中每个节点被访问到的概率。把得到的概率分布作为　下一次游走的输入并反复迭代这一过程。本文在建立统　一图模型的基础上，使用随机游走的方法来获取图像与语　义之间联系的紧密程度，即完成对图像中物体的识别。　设Ｇ＝｛　，Ｅ｝，Ｇ表示统一的混合图模型。Ｖ＝ＤＵＳ表　示Ｇ中的所有节点，Ｄ表示图像节点集，　表示语义节点　集。Ｅ＝Ｅ　ＵＥ—Ｕ　表示Ｇ中所有的边，如果边Ｅ　是边　集　中的一个元素，则ｉ∈Ｄ且Ｊ∈Ｄ；同样的，若Ｅ　∈Ｅ一，　则ｉ∈Ｓ且Ｊ∈Ｓ；若Ｅ“∈Ｅ　，则ｉ∈Ｄ且Ｊ∈Ｓ，或者ｉ∈Ｓ　且Ｊ∈Ｄ。　为了建立随机游走模型，需要将　中所有的边的权值　表示为概率。则对于边集　中的所有边，定义其转移概率：　Ｐ　Ｔ”…．，（ｆ，　＝—　—　∑　∑Ｐ　？　Ｊ　１ｎｉ　１　其中，ｉ∈Ｄ且Ｊ∈Ｓ，由于对于一个图像节点可能含有多　个具有同一语义的子区域，所以定义ｍ　，ｋ　［１，ｎｉｌ表示具　有同一语义　的子区域，　为图像　中含有同一语义　，　子区域的数量。同样的，也得到了当ｉ　Ｓ，且　∈Ｄ时的　转移概率：　Ｔ”川（ｆ，寺薹Ｐ　Ｒｊ　　，，　）＝—上　一寺　尸　对于边集Ｅ　，Ｅ一中的边，相应地分别定义它们的转　移概率。对于ｆ　。且ｕ，　ＪＤ，有　”川（　，　ｓ　ｉｍ　（ｖ　ｉ，　ｖｊ）　，ｒ，　舯二　ｆ，ｒ【　，　Ｊ　（ｖｉ，Ｖ■ｊ）　籽　有　林霄，肖国强，吴松。等：基于随机游走模型的物体识别　鼙　兰　Ｐ　　：１ｎ　＝ｌ寺ｊ　圭ｋＰＳ　ｉ　＝ｌ差寺耋　Ｓｉ　（３）　∑ｓｉｍ（ｖ　）’‘，ｆ，　　　ＤＮ　Ｄ　‘　∑　）　～　，ｆ∈　ｎ　∈　，　Ｉ　Ｔ　ｆ＿Ｉ）　＝｛∞×Ｔ　（ｆ卜１）　（５）　ｌ（１一　一ｃｏ）ｘ　Ｔ＇（ｔｆｔ—Ｉ）　）（　：【　（６）　公式（６）计算了在步长为ｔ的情况下，节点ｉ通过所有　路径转移到节点　的概率的累加。连接两节点间的路径越　多，计算得到的转移概率Ｐ（ｒｉｏ）（　越大；转移概率越大，两　节点问的相似度越高。　在图像分割阶段，将图像　分为　，个子区域。由于　只建立了其中面积前１　ｓ×　Ｉ大的子区域与语义之间的关　系。所以在完成ｆ步的随机游走后，对于图像节点ｆ可以根　据其与所有语义节点的相似性对１２类语义进行排序，得到　语义相似性序列Ｒａｎｋ　。最后取序列Ｒａｎｋ。中前ｌｓ×Ｍ　Ｉ大　的数据对应的语义作为图像ｉ中物体识别的结果。　６实验　本文的实验图像集是ＭＩＴ－ＣＳＡＩＬ　Ｄａｔａｂａｓｅ　ｏｆ　Ｏ　ｅｃｔｓ　ａｎｄ　Ｓｃｅｎｅｓ中的２　４００张图像，每幅图像大小为２５６像素×　２５６像素。其中包含八种场景，每种场景３００张图像中都包　含多个组成场景的物体。从中选取了１２类物体作为实验　对象。　６．１全局特征的选取　为了能更好地表达图像间的相似关系，需要选取一些　能较好表达图像全局信息的视觉特征。由此，从实验图像　集中选取了８类图像，每类图像１００张。并分别对边缘方　向直方图（Ｅｄｇｅ　ｏｒｉｅｎｔａｔｉｏｎ　ｈｉｓｔｏｇｒａｍ，Ｅｄｇｅ）　、Ｇａｂｏｒ　ｔ］ｘ波　纹理特征（Ｇａｂｏｒ　ｗａｖｅｌｅｔｓ　ｔｅｘｔｕｒｅ，Ｇａｂｏｒ）　、ＬＢＰ纹理特　征、颜色直方图四种不同的全局特征，以及两种组合特征　进行性能比较。对于每一类图像，都随机选取一张图像作　为该类图像的中心，并用ｋＮＮ算法计算各类图像中心在六　种不同的全局特征下选取ｋ个近邻时的正确率。实验结果　如图６所示。　册　器　选取近邻数　个　图６全局特征精度的比较　可以看到，组合特征明显比单一特征具有更好的性　能。在两种组合特征中，由ＬＢＰ纹理特征和颜色直方图组　成的特征更能表达图像中的全局信息。所以，本文使用３０　维的颜色直方图与５９维的ＬＢＰ纹理特征作为图像的全局　特征。　６．２变量的取值　在设置融合参数　和ＣＯ之前，需要设置另外两个参数　的值：构建图像相似性图和语义相似性图时，使用算法中的　参数　；随机游走模型中随机游走的步长ｔ。　对于参数ｋ，文献［１１】中证明了在基于图模型的机器学　林霄，肖国强，吴松，等：基于随机游走模型的物体识别　２０１３，４９（２１）　１５ｌ　当其关联准确性高于０．５５时，通过随机游走模型能够有效　提高仅基于视觉特征的物体识别算法的识别能力。　［８］Ｐａａｔｅｒｏ　Ｐ，Ｔａｐｐｅｒ　Ｕ．Ｐｏｓｉｔｉｖｅ　ｍａｔｒｉｘ　ｆａｃｔｏｒｉｚａｔｉｏｎ：ａ　ｎｏｎ—ｎｅｇａ—　ｔｉｖｅ　ｆａｃｔｏｒ　ｍｏｄｅｌ　ｗｉｔｈ　ｏｐｔｉｍａｌ　ｕｔｉｌｉｚａｔｉｏｎ　ｏｆ　ｅｒｒｏｒ　ｅｓｔｉｍａｔｅｓ　ｏｆ　ｄａｔａ　ｖａｌｕｅｓ［Ｊ］．Ｅｎｖｉｒｏｎｍｅｔｒｉｃｓ，１９９４，５（２）：１１１—１２６．　７结束语　本文提出了一种基于随机游走模型的物体识别算法。　［９］Ｄｅｎｇ　Ｙｉｎｉｎｇ，Ｍａｎｊｕｎａｔｈ　Ｂ　Ｓ．Ｕｎｓｕｐｅｒｖｉｓｅｄ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｏｆ　ｃｏｌｏｒ－ｔｅｘｔｕｒｅ　ｒｅｇｉｏｎｓ　ｉｎ　ｉｍａｇｅｓ　ａｎｄ　ｖｉｄｅｏ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃ—　ｔｉｏｎｓ　ｏｎ　Ｐａｔｔｅｒｎ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｍａｃｈｉｎｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００　１，２３　该算法用图模型表达各类图像、语义之间潜在的联系，并构　建随机游走模型把这种联系应用到物体识别的过程中。　ｆ８）．　实验证明，本文提出的识别算法具有较强的识别能力。　［１Ｏ】Ｏｊａｌａ　Ｔ，Ｐｉｅｔｉｋａｉｎｅｎ　Ｍ，Ｍａｅｎｐａａ　Ｔ．Ｍｕｌｔｉｒｅｓｏｌｕｔｉｏｎ　ｇｒａｙ—ｓｃａｌｅ　ａｎｄ　ｒｏｔａｔｉｏｎ　ｉｎｖａｒｉａｎｔ　ｔｅｘｔｕｒｅ　ｃｌａｓｓｉｉｃａｔｉｆｏｎ　ｗｉｔｈ　ｌｏｃａｌ　ｂｉｎａｒｙ　ｐａｔｔｅｒｎｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐａｔｔｅｒｎ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｍａ—　参考文献：　［１］Ｐａｐａｄｏｐｏｕｌｏｓ　Ｇ，Ｍｅｚａｒｉｓ　Ｖ，Ｋｏｍｐａｔｓｉａｒｉｓ　Ｉ，ｅｔ　ａ１．Ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｃｏｍｂｉｎａｔｉｏｎ　ｏｆ　ｓｐａｔｉａｌ　ｃｏｎｔｅｘｔ　ｗｉｔｈ　ｖｉｓｕａｌ　ａｎｄ　ｃｏ・ｏｃｃｕ￣ｅｎｃｅ　ｃｈｉｎｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００２，２４（７）：９７１—９８７．　【１１］Ｚｈｕ　Ｘ．Ｓｅｍｉ—ｓｕｐｅｒｖｉｓｅｄ　ｌｅａｒｎｉｎｇ　ｗｉｔｈ　ｇｒａｐｈｓ［Ｄ］．Ｐｉｔｔｓｂｕｒｇｈ，　ＰＡ，２００５．　ｉｎｆｏｒｍａｔｉｏｎ　ｆｏｒ　ｓｅｍａｎｔｉｃ　ｉｍａｇｅ　ａｎａｌｙｓｉｓ［Ｃ］／／ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ（ＩＣＩＰ），２０　１　０．　［１２】Ｇｒｕｂｅｒ　Ｔ　Ｒ．Ａ　ｔｒａｎｓｌａｔｉｏｎ　ａｐｐｒｏａｃｈ　ｔｏ　ｐｏｒｔａｂｌｅ　ｏｎｔｏｌｏｇｙ　ｓｐｅｃ—　ｉｆｉｃａｔｉｏｎｓ［Ｊ］．Ｋｎｏｗｌｅｄｇｅ　Ａｃｑｕｉｓｉｔｉｏｎ，１９９３，５（２）：１９９—２１１．　［１３］Ｒｅｓｎｉｋ　Ｐ．Ｕｓｉｎｇ　ｉｎｆｏｒｍａｔｉｏｎ　ｃｏｎｔｅｎｔ　ｔｏ　ｅｖａｌｕａｔｅ　ｓｅｍａｎｔｉｃ　ｓｉｍｉｌａｒｉｔｙ　ｉｎ　ａ　ｔａｘｏｎｏｍｙ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｉｎｔ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ａｒｔｉｉｆｃｉａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，Ｍｏｎｔｒｅａｌ，Ｃａｎａｄａ，　［２］Ｅｓｃａｌａｎｔｅ　Ｈ　Ｊ，Ｍｏｎｔｅｓ—Ｙ・Ｇｏｍ６ｚ　Ｍ，Ｓｕｃａｒ　Ｌ　Ｅ．Ａｎ　ｅｎｅｒｇｙ—　ｂａｓｅｄ　ｍｏｄｅｌ　ｆｏｒ　ｒｅｇｉｏｎ—ｌａｂｅｌｉｎｇ［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｖｉｓｉｏｎ　ａｎｄ　Ｉｍ—　ａｇｅ　Ｕｎｄｅｒｓｔａｎｄｉｎｇ，２０１１，１１５：７８７・８０３．　【３】Ｆｅｒｇｕｓ　Ｒ，Ｐｅｒｏｎａ　Ｐ，Ｚｉｓｓｅｒｍａｎ　Ａ．Ｏｂｊｅｃｔ　ｃｌａｓｓ　ｒｅｃｏｇｎｉｔｉｏｎ　ｂｙ　ｕｎｓｕｐｅｒｖｉｓｅｄ　ｓｃａｌｅ—ｉｎｖａｒｉａｎｔ　ｌｅａｒｎｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｐｕｔｅｒ　Ｖｉｓｉｏｎ　ａｎｄ　Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉ—　ｔｉｏｎ，２００３．　１９９５：４４８—４５３．　【１４］Ｅｉｒｏｎ　Ｎ，ＭｃＣｕｒｌｅｙ　Ｋ　Ｓ，Ｔｏｍｌｉｎ　Ｊ　Ａ．Ｒａｎｋｉｎｇ　ｔｈｅ　ｗｅｂ　Ｉｒｏｎ—　ｔｉｅｒ［Ｃ］／／Ｐｒｏｃ　ｗｗＷ’０４．Ｎｅｗ　Ｙｏｒｋ，２００４：３０９—３１８．　［１５】Ｐａｇｅ　Ｌ，Ｂｒｉｎ　Ｓ，Ｍｏｔｗａｎｉ　Ｒ，ｅｔ　ａ１．Ｔｈｅ　ｐａｇｅｒａｎｋ　ｃｉｔａｔｉｏｎ　ｒａｎｋ・　ｉｎｇ：ｂｒｉｎｇｉｎｇ　ｏｒｄｅｒ　ｔｏ　ｔｈｅ　Ｗｅｂ，ＳＩＤＬＷＰ一１９９９—０１２０［Ｒ］．１９９９．　【１６］Ｊａｉｎ　Ａ　Ｋ，Ｖａｉｌａｙａ　Ａ．Ｉｍａｇｅ　ｒｅｔｒｉｅｖａｌ　ｕｓｉｎｇ　ｃｏｌｏｒ　ａｎｄ　ｓｈａｐｅ［Ｊ］．　Ｐａｔｔ　Ｒｅｃｏｇｎ，１９９６，２９（８）：１２３３—１２４４．　［４】Ｊｏｌｌｉｆｆｅ　Ｉ　Ｔ．Ｐｒｉｎｃｉｐａｌ　ｃｏｍｐｏｎｅｎｔ　ａｎａｌｙｓｉｓ［Ｍ］＿［ｓ．１．］：Ｓｐｒｉｎｇｅｒ，　２００２．　［５］Ｈｙｖ）￣ａｒｉｎｅｎ　Ａ，Ｋａｒｈｕｎｅｎ　Ｊ，Ｏｊａ　Ｅ．Ｉｎｄｅｐｅｎｄｅｎｔ　ｃｏｍｐｏｎｅｎｔ　ａｎａｌｙｓｉｓ［Ｍ］．［Ｓ．１．】：Ｊｏｈｎ　Ｗｉｌｅｙ＆Ｓｏｎｓ，２００１．　【６］Ｌｅｅ　Ｄ　Ｄ，Ｓｅｕｎｇ　Ｈ　ｓ．Ｌｅａｒｎｉｎｇ　ｔｈｅ　ｐａｒｔｓ　ｏｆ　ｏｂｊｅｃｔｓ　ｂｙ　ｎｏｎ—ｎｅｇ—　ａｔｉｖｅ　ｍａｔｒｉｘ　ｆａｃｔｏｒｉｚａｔｉｏｎ［Ｊ］．Ｎａｔｕｒｅ，１９９９，４０１：７８８—７９１．　［７］Ｍｕｒａｓｅ　Ｈ，Ｎａｙａｒ　Ｓ　Ｋ．Ｖｉｓｕａｌ　ｌｅａｒｎｉｎｇ　ａｎｄ　ｒｅｃｏｇｎｉｔｉｏｎ　ｏｆ　３－ｄ　［１７】Ｌａｄｅｓ　Ｍ，Ｖｏｒｂｒｕｇｇｅｎ　Ｊ　Ｃ，Ｂｕｈｍａｎｎ　Ｊ，ｅｔ　ａ１．Ｄｉｓｔｏｒｔｉｏｎ　ｉｎｖａｒｉ—　ａｎｔ　ｏｂｊｅｃｔ　ｒｅｃｏｇｎｉｔｉｏｎ　ｉｎ　ｔｈｅ　ｄｙｎａｍｉｃ　ｌｉｎｋ　ａｒｃｈｉｔｅｃｔｕｒｅ［Ｊ］．　ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｃｏｍｐｕｔ，１９９３，４２（３）：３００—３１１．　ｏｂｊｅｃｔｓ　ｆｒｏｍ　ａｐｐｅａｒａｎｃｅ［Ｊ］．Ｉｎｔｅｒｎ　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｖｉｓｉｏｎ，　ｌ９９５，１４（Ｉ）：５．２４．　［１８］郑伟，王朝坤，刘璋，等．一种基于随机游走模型的多标签分　类算法［Ｊ］．计算机学报，２０１０，３３（８）：１４１８－１４２６．　（上接１４４页）　Ｓｃｉｅｎｃｅ　５２１１：ＥＣＭＬ／ＰＫＤＤ（１），２００８：３－４．　上的处理效果还不是很好。自适应地确定聚类数目能够　给用户带来极大的方便。　［２］Ｐｏｌｌａｒｄ　Ｄ．Ｓｔｒｏｎｇ　ｃｏｎｓｉｓｔｅｎｃｙ　ｏｆ　Ｋｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ［Ｊ］．Ａｉｌｎａｌｓ　ｏｆ　Ｓｔａｔｉｓｔｉｃｓ，１９８１，９：１３５—１４０．　［３］Ｈｕａｎｇ　Ｚ．Ｅｘｔｅｎｓｉｏｎｓ　ｔｏ　ｔｈｅ　Ｋｍｅａｎｓ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｃｌｕｓｔｅｒｉｎｇ　６结束语　Ｋｒｎｅａｎｓ算法是一种应用非常广泛的聚类算法，但它对　ｌａｒｇｅ　ｄａｔａ　ｓｅｔｓ　ｗｉｔｈ　ｃａｔｅｇｏｒｉｃａｌ　ｖａｌｕｅｓ［Ｊ］．Ｄａｔａ　Ｍｉｎｉｎｇ　ａｎｄ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒ，１９９８，２．　［４］张文明，吴江，袁小蛟．基于密度和最近邻的Ｋ－ｍｅａｎｓ文本聚类　初始聚类中心的依赖性较强，容易陷入局部最优解。本文　提出的ＫＣＧ能够从全局角度均衡地选取初始聚类中心，确　定聚类数目，增加找到全局最优解的可能。　算法【Ｊ］．计算机应用，２０１０，３０（７）：１９３３　１９３４．　［５】Ｇａｎ　Ｗｅｎｙａｎ，Ｌｉ　Ｄｅｙｉ．Ｈｉｅｒａｒｃｈｉｃａｌ　ｃｌｕｓｔｅｒｉｎｇ　ｂａｓｅｄ　ｏｎ　ｋｅｒｎｅｌ　ｄｅｎｓｉｔｙ　ｅｓｔｉｍａｔｉｏｎ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｓｙｓｔｅｍ　Ｓｉｍｕｌａｔｉｏｎ，２００４，１６　（２）：３０２—３０９．　有效性分析和实验表明，ＫＣＧ较大地提高了聚类性　能。但该算法仍然没有解决Ｋｍｅａｎｓ算法处理非球形数　据、流行数据集的聚类效果，如何拓展Ｋｍｅａｎｓ算法的适用　范围是下一步要做的工作。　［６杨善林，６１李永森，胡笑旋，等．Ｋ－ｍｅａｎｓ算法中的｜｝ｉ值优化问题研　究［Ｊ］．系统工程理论与实践，２００６（２）：９７—１０１．　［７］张健沛，杨悦，杨静，等．基于最优划分的Ｋ－Ｍｅａｎｓ初始聚类中　心选取算法［Ｊ］．系统仿真学报，２００９，２１（９）：２５８６—２５９０．　［８曹志宇，张忠林，８］李元韬．快速查找初始聚类中心的／（ｍｅａｎｓ算　法［Ｊ］．兰州交通大学学报，２００９，２８（６）：１５－１８．　［９］Ｍｉｍａｒｏｇｌｕ　Ｓ，Ｅｒｄｉｌ　Ｅ．Ｃｏｍｂｉｎｉｎｇ　ｍｕｌｔｉｐｌｅ　ｃｌｕｓｔｅｒｉｎｇｓ　ｕｓｉｎｇ　ｓｉｍｉｌａｒｉｔｙ　ｇｒａｐｈ［Ｊ］．Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎ，２０１１，４４．　参考文献：　［１］Ｊａｉｎ　Ａ　Ｋ．Ｄａｔａ　ｃｌｕｓｔｅｒｉｎｇ：５０　ｙｅａｒｓ　ｂｅｙｏｎｄ　Ｋｍｅａｎｓ［Ｃ］／／Ｄａｅ—　ｌｅｍａｎｓ　Ｗ，Ｇｏｅｔｈａｌｓ　Ｂ，Ｍｏｒｉｋ　Ｋ．Ｌｅｃｔｕｒｅ　Ｎｏｔｅｓ　ｉｎ　Ｃｏｍｐｕｔｅｒ