第３９卷　Ｖ＿０ｌ＿３９　第５期　

Ｎｏ．５　计算机工程　

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　２０１３年５月　

Ｍａｙ　２０１３　

・图形图像处理・　文章编号：１０ｏｏ—３４２８（２ｏ１３）０５—０２４３—０５　文献标识码：Ａ　中圈分类号ｔ　ＴＮ９１１．７３　基于复杂网络的图像建模与特征提取方法　汤进Ｌ　，陈影　，江波　，罗斌　（１．安徽省工业图像处理与分析重点实验室，合肥２３００３９；　２．安徽大学计算机科学与技术学院，合肥２３０６０　１）　

摘要：针对传统图像结构图表示特征不稳定的问题，提出一种基于复杂网络模型的图像表示与识别方法。以图像的关键　点作为网络节点，构建复杂网络初始模型。利用最小生成树分解方法对初始网络模型进行动态演化，提取不同演化阶段下　的网络特征，实现对图像结构特征的描述。该方法直接利用图像关键点之间的空间分布信息，结构简单。分类与聚类实验　结果表明，与传统基于边权值阈值的演化方法相比，该方法能更准确地描述图像的结构。　关健诃：图像识别；最小生成树；动态演化；特征提取；小世界网络；复杂网络　

Ｉｍａｇｅ　Ｍｏｄｅｌｉｎｇ　ａｎｄ　Ｆｅａｔｕｒｅ　Ｅｘｔｒａｃｔｉｏｎ　Ｍｅｔｈｏｄ　Ｂａｓｅｄ　０ｎ　Ｃｏｍｐｌｅｘ　Ｎｅｔｗｏｒｋ　ＴＡＮＧ　Ｊｉｎ　，ＣＨＥＮ　Ｙｉｎｇ　，ＪＩＡＮＧ　Ｂｏ　，ＬＵＯ　Ｂｉｎ　，　ｆ１．Ｋｅｙ　Ｌａｂ　ｏｆ　Ｉｎｄｕｓｔｒｉａｌ　Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ＆Ａｎａｌｙｓｉｓ　ｏｆＡｎｈｕｉ　Ｐｒｏｖｉｎｃｅ，Ｈｅｆｅｉ　２３００３９，Ｃｈｉｎａ；　２．Ｓｃｈｏｏｌ　ｏｆＣｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ａｎｈｕｉ　Ｕｎｉｖｅｒｓｉｔｙ，Ｈｅｆｅｉ　２３０６０１，Ｃｈｉｎａ）　

［Ａｂｓｔｒａｃｔ］Ｆｏｒ　ｔｈｅ　ｓｔｒｕｃｔｕｒｅ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｕｓｕａｌｌｙ　ｂｅｃｏｍｅ　ｉｎｓｔａｂｌｅ　ｉｎ　ｔｒａｄｉｔｉｏｎａｌ　ｇｒａｐｈ　ｂａｓｅｄ　ｉｍａｇｅ　ｒｅｐｒｅｓｅｎｔａｔｉｏｎ　ｍｅｔｈｏｄｓ，ａ　ｎｏｖｅｌ　ｉｍａｇｅ　ｒｅｐｒｅｓｅｎｔａｔｉｏｎ　ａｎｄ　ｒｅｃｏｇｎｉｔｉｏｎ　ｍｅｔｈｏｄ　ｂａｓｅｄ　ｏｎ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋ　ｉｓ　ｐｒｏｐｏｓｅｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ．Ｋｅｙ　ｐｏｉｎｔｓ　ａｒｅ　ｅｘｔｒａｃｔｅｄ　ｆｏｒ　ａｎ　ｉｍａｇｅ　ａｎｄ　ａｎ　ｉｎｉｔｉａｌ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋ　ｉｓ　ｃｏｎｓｔｒｕｃｔｅｄ　ｉｎ　ｗｈｉｃｈ　ｎｏｄｅｓ　ｃｏｒｒｅｓｐｏｎｄ　ｔｏ　ｔｈｅ　ｋｅｙ　ｐｏｉｎｔｓ．Ａ　ｎｏｖｅｌ　ｄｙｎａｍｉｃ　ｅｖｏｌｕｔｉｏｎ　ｐｒｏｃｅｓｓ　ｉｓ　ｄｅｖｉｓｅｄ　ｆｏｒ　ｔｈｅ　ｉｎｉｔｉａｌ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋ　ｕｓｉｎｇ　ｔｈｅ　ｍｉｎｉｍｕｍ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ　ｄｅｃｏｍｐｏｓｉｔｉｏｎ．Ｔｈｅ　ｆｅａｔｕｒｅｓ　ｏｆ　ｔｈｅ　ｎｅｔｗｏｒｋｓ　ｉｎ　ｄｉｆｆｅｒｅｎｔ　ｅｖｏｌｕｔｉｏｎ　ｓｔａｇｅｓ　ａｒｅ　ｅｘｔｒａｃｔｅｄ　ｔｏ　ｆｉｎａｌｌｙ　ａｃｈｉｅｖｅ　ｉｍａｇｅ　ｓｔｒｕｃｔｕｒａｌ　ｉｎｆｏｒｍａｔｉｏｎ　ｅｘｔｒａｃｔｉｏｎ．Ｔｈｉｓ　ｍｅｔｈｏｄ　ｃａｎ　ｓｉｍｐｌｙ　ｄｅｓｃｒｉｂｅ　ａｎ　ｉｍａｇｅ　ｂｙ　ｕｓｉｎｇ　ｇｅｏｍｅｔｒｉｃａｌ　ｆｅａｔｕｒｅ　ｏｆ　ｔｈｅ　ｉｍａｇｅ　ｋｅｙ　ｐｏｉｎｔｓ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｏｎ　ｂｏｔｈ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ａｎｄ　ｃｌｕｓｔｅｒｉｎｇ　ｄｅｍｏｎｓｔｒａｔｅ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｅｔｈｏｄ　ｏｕｔｐｅｒｆｏｒｍｓ　ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ｅｄｇｅ　ｗｅｉｇｈｔ　ｔｈｒｅｓｈｏｌｄ　ｅｖｏｌｕｔｉｏｎ　ｍｅｔｈｏｄ　ａｎｄ　ｉｔ　ｃａｎ　ｄｅｓｃｒｉｂｅ　ｔｈｅ　ｓｔｒｕｃｔｕｒｅ　ｏｆ　ｉｍａｇｅｓ　ｍｏｒｅ　ｅｆｆｅｃｔｉｖｅｌｙ．　［Ｋｅｙ　ｗｏｒｄｓ］ｉｍａｇｅ　ｒｅｃｏｇｎｉｔｉｏｎ；ｍｉｎｉｍｕｍ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ；ｄｙｎａｍｉｃ　ｅｖｏｌｕｔｉｏｎ；ｆｅａｔｕｒｅ　ｅｘｔｒａｃｔｉｏｎ；ｓｍａｌｌ—ｗｏｒｌｄ　ｎｅｔｗｏｒｋ；ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋ　Ｄ０ｈ　１０．３９６９￣．ｉｓｓｎ．１　０００．３４２８．２０１３．０５．０５３　

１概述　图像识别是利用计算机对图像进行处理、分析和理　解，以识别不同目标和对象的技术。目前图像识别方法有　很多，如基于边缘轮廓的图像识别方法　Ｊ、基于纹理的图　像识别方法［３－４］以及基于关键点的图像识别方法　Ｊ。基于　关键点的图像识别方法一般是先对图像提取一些关键点，　如Ｈａｒｒｉｓ角点、ＳＩＦＴ关键点等，然后通过构建具有一定拓　扑结构的结构图来描述这些关键点的空间位置分布信息，　最后通过提取结构图的拓扑结构信息，如谱信息、直方图　信息等来实现结构图之间的特征提取，从而对图像之间的　相似性进行度量，完成图像的识别　Ｊ。然而由于图像本身　存在一定的噪声，使图像的关键点提取存在误差，这就使　传统结构化的描述方法具有一定的挑战性　Ｊ。　近年来，复杂网络理论得到越来越多学者的关注【ｌ　“Ｊ。　文献［１】通过对形状轮廓边缘点建立复杂网络模型，实现对形　状特征的描述；文献［３］通过对图像的纹理特征进行分析，建　立复杂网络模型，实现对纹理图像的识别。由于复杂网络模　型的图像形状特征描述是基于统计特征得以实现的，因此这　种特征具有稳定性好、抗噪声能力强等优点。针对上述特点，　本文在图像关键点的基础上，提出一种新的基于图像关键点　的复杂网络表示模型，并利用最小生成树分解方法给出一种　

基金项目：国家自然科学基金资助项Ｈ（６１０７３１１６，６１００３０３８）；安徽省教育厅自然科学基金资助重点项Ｉ￣Ｉ（ＫＪ２０１０Ａ００６）；安徽　大学“２１１工程”创新团队基金资助项目　作者简介：汤进（１９７６一），男，副教授、博士，主研方向：图像处理，模式识别；陈影、江波，硕士研究生；罗斌，　教授　收稿日期：２０１２—０３—０５　修回日期：２０１２。０５　０１　Ｅ－ｍａｉｌ：ａｈｈｆｔａｎｇ＠ｇｍａｉｌ．ｃｏｍ　第３９卷第５期　汤进，陈影，江波，等：基于复杂网络的图像建模及特征提取方法　２４７　表２混淆矩阵（３类图像）　

此外，本文针对该图像库，进一步做了主成分分析以　及多维尺度分析。在此与传统的基于Ｄｅｌａｕｎａｙ图像特征提　取方法（以下简称为Ｄｅｌａｕｎａｙ直方图）进行比较　Ｊ，实验结果　如图９、图１０所示。由实验结果可以看出，相比于Ｄｅｌａｕｎａｙ　图的图像结构特征提取方法，基于本文所提的特征，同类　图像分布显得更为紧密，不同类的图像分布较开，这表明　在图像的复杂网络表示下，图像分类和聚类更加容易。进　

一步分析，相比于边权值阈值演化的复杂网络模型，本文　的最小生成树演化模型能够较好地实现对网络特性的描　述，从而保证了在这种演化下的图像网络特征能够更加充　分地描述图像的结构信息。　

（ａ）最小生成树演化　（ｂ）边权值阈值演化　（ｃ）Ｄｅｌａｕｎａｙ直方图　图９不同方法的主成分分析的嵌入结果　

（ａ）最小生成树演化　（ｂ）边权值阈值演化　（ｃ）Ｄｅｌａｕｎａｙ直方图　图１０不同方法的多维尺度分析的嵌入结果　

５结束语　本文给出了一种基于复杂网络模型的图像表示及其特　征提取方法。提取图像的关键点，并在此基础上构建复杂　网络初始模型，利用最小生成树分解的方法对网络进行演　化，提取不同演化阶段下的网络特征。综合不同演化时刻　下的网络特征，对图像的特征进行描述，并在此基础上，　实现图像的识别。实验结果表明，与传统的结构图表示方　法相比，本文方法对图像结构信息描述更加充分，能够较　好地实现图像的分类与聚类。相比于传统边权值阈值演化　模型，本文的最小生成树演化模型能够更好地刻画复杂网　络的结构特征。在后期工作中，笔者将研究基于图像关键　点的有向复杂网络表示模型，实现图像的特征提取。　（下转第２５２页）　２５２　计算机工程　２０１３年５月１５日　格点上的频谱值可通过分数阶Ｆｏｕｒｉｅｒ变换精确计算。实验　结果表明，该算法较为准确，能扩大可配准图像的尺度变　化范围。如何减少算法复杂度及寻找快速算法将是今后的　研究方向。　

参考文献　［１］Ｚｉｔｏｖａ　Ｂ，Ｆｌｕｓｓｅｒ　Ｊ．Ｉｍａｇｅ　Ｒｅｇｉｓｔｒａｔｉｏｎ　Ｍｅｔｈｏｄｓ：Ａ　Ｓｕｒｖｅｙ［Ｊ］．Ｉｍａｇｅ　Ｖｉｓｉｏｎ　Ｃｏｍｐｕｔｉｎｇ，２００３，２１（１　１）：９７７—　１０００．　［２］Ｆｏｒｏｏｓｈ　Ｈ，Ｚｅｒｕｂｉａ　Ｊ　Ｂ，Ｂｅ￣ｈｏｄ　Ｍ．Ｅｘｔｅｎｓｉｏｎ　ｏｆ　Ｐｈａｓｅ　Ｃｏｒｒｅｌａｔｉｏｎ　ｔｏ　Ｓｕｂｐｉｘｅｌ　Ｒｅｇｉｓｔｒａｔｉｏｎ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ，２００２，１１（３）：１８８—２００．　［３】Ｃｈａｎｇ　Ｓ　Ｈ，Ｃｈｅｎ　Ｆ　Ｈ，Ｈｓｕ　Ｗ　Ｈ，ｅｔ　ａ１．Ｆａｓｔ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｐｏｉｎｔｅｒ　Ｐａｔｔｅｍ　Ｍａｔｃｈｉｎｇ；Ｉｎｖａｒｉａｎｔ　ｔｏ　Ｔｒａｎｓｌａｔｉｏｎｓ，　Ｒｏｔａｔｉｏｎｓ，ａｎｄ　Ｓｃａｌｅ　Ｃｈａｎｇｅｓ［Ｊ］．Ｐａ￣ｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎ，　１９９７，３０（２）：３１１－３２０．　［４】Ｍａｔｓｏｐｏｕｌｏｓ　Ｇ　Ｋ，Ａｔｌｉｎｓ　Ｓ．Ｍｕｌｔｉｒｅｓｏｌｕｔｉｏｎ　Ｍｏｒｐｈｏｌｏｇｉｃａｌ　Ｆｕｓｉｏｎ　ｏｆ　ＭＲ　ａｎｄ　ＣＴ　Ｉｍａｇｅｓ　ｏｆ　ｔｈｅ　Ｈｕｍａｎ　Ｂｒａｉｎ［Ｊ］．ＩＥＥ　Ｐｒｏｃｅｅｄｉｎｇｓ————ｖｉｓｉＯｎ，Ｉｍａｇｅ　ａｎｄ　Ｓｉｇｎａｌ　Ｐｒｏｃｅｓｓｉｎｇ，　１９９４，１４１（３）：１３７－１４２．　［５］Ｒｅｄｄｙ　Ｓ，Ｃｈａ￣ｅｑｉ　Ｂ　Ｎ．Ａｎ　ＦＦＴ－ｂａｓｅｄ　Ｔｅｃｈｎｉｑｕｅ　ｆｏｒ　Ｔｒａｎｓｌａｔｉｏｎ，Ｒｏｔａｔｉｏｎ，ａｎｄ　Ｓｃａｌｅ－ｉｎｖａｒｉａｎｔ　Ｉｍａｇｅ　Ｒｅｇｉｓｔｒａ—　ｔｉｏｎ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ，１９９６，　３（８）：１２６６．１２７０．　［６］Ｋｅｌｌｅｒ　Ａｖｅｒｂｕｃｈ　Ａ，Ｉｓｒａｅｌｉ　Ｍ．Ｐｓｅｕｄｏｐｏｌａｒ—ｂａｓｅｄ　Ｅｓｔｉ—　ｍａｒｉｏｎ　ｏｆ　Ｌａｒｇｅ　Ｔｒａｎｓｌａｔｉｏｎｓ，Ｒｏｔａｔｉｏｎｓ，ａｎｄ　Ｓｃａｌｉｎｇｓ　ｉｎ　Ｉｍａｇｅｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ，２００５，　１４（１）：１２—２２．　【７］Ｐａｎ　Ｗｅｉ，Ｑｉｎ　Ｋａｉｈｕａｉ，Ｃｈｅｎ　Ｙａｏ．Ａｎ　Ａｄａｐｔａｂｌｅ－ｍｕｌｔｉｌａｙｅｒ　Ｆｒａｃｔｉｏｎａｌ　Ｆｏｕｒｉｅｒ　Ｔｒａｎｓｆｏｒｍ　Ａｐｐｒｏａｃｈ　ｆｏｒ　Ｉｍａｇｅ　Ｒｅｇｉｓｔｒａｔｉｏｎ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐａｔｔｅｒｎ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｍａｃｈｉｎｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００９，３　１（３）：４００－４　１　３．　［８］杨虎，李万松．分数傅里叶变换的无透镜光学实现［Ｊ］　激光杂志，１９９９，２０（１）：１５－１８．　［９］９　孙晓兵，保铮．分数阶Ｆｏｕｒｉｅｒ变换及其应用［Ｊ］＿电子　学报，１９９６，２４（１２）：６０—６５．　［１Ｏ］邓兵，陶然，齐林，等．分数阶Ｆｏｕｒｉｅｒ变换与时　频滤波［Ｊ］．系统工程与电子技术，２００４，２６（１０）：１３５７—　１３５９．　［１　１】Ｋｅｌｌｅｒ　Ａｖｅｎｂｕｃｈ　Ａ，Ｍｉｌｌｅｒ　Ｏ．Ｒｏｂｕｓｔ　Ｐｈａｓｅ　Ｃｏｒｒｅ．　１ａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ｔｈｅ　１４ｔｈ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　ＰａＲｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎ．【Ｓ．１．］：ＩＥＥＥ　Ｐｒｅｓｓ，２００４．　［１　２］Ｓｔｏｎｅ　Ｈ　Ｓ，Ｔａｏ　Ｂｏ，ＭｃＧｕｉｒｅ　Ｍ．Ａｎａｌｙｓｉｓ　ｏｆ　Ｉｍａｇｅ　Ｒｅ．　ｇｉｓｔｒａｔｉｏｎ　Ｎｏｉｓｅ　Ｄｕｅ　ｔｏ　Ｒｏｔａｔｉｏｎａｌｌｙ　Ｄｅｐｅｎｄｅｎｔ　Ａｌｉａｓｉｎｇ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｖｉｓｕａｌ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ　ａｎｄ　Ｉｍａｇｅ　Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ，２００３，１４（１）：１　１４－１３５．　编辑刘冰