计算机科学

孙奕,陈性元,杜学绘,徐建

计算机科学. 2015, 42 (11): 1-7. doi:10.11896/j.issn.1002-137X.2015.11.001

摘要 ( 330 )

PDF(698KB) ( 1238 )

参考文献 | 相关文章 | 多维度评价

为了解决外包数据和授权计算的安全性问题,近年来可验证授权计算理论又重新受到人们的关注和青睐。文中重点描述了在不可信环境下可验证授权计算技术是如何解决外包数据和授权计算的可验证性问题,并给出了可验证授权计算方案的形式化定义。首先采用不同分类方法对现有研究方案进行总结与归纳,指出现有研究方案的特点、所采用关键技术及不足之处；然后从功能和性能两个方面对方案进行对比分析；最后结合应用热点,从不同应用方向展望了该领域的研究趋势和发展前景。

社交网络研究综述

李立耀,孙鲁敬,杨家海

计算机科学. 2015, 42 (11): 8-21. doi:10.11896/j.issn.1002-137X.2015.11.002

摘要 ( 470 )

PDF(1448KB) ( 2237 )

参考文献 | 相关文章 | 多维度评价

社交网络已成为Web2.0时代最流行的应用,其服务范围已逐步从社交关系管理扩展到媒体信息、应用集成、电子商务等领域。社交网络中大量的活跃用户为研究网络行为、数据安全、信息传播以及其他跨学科问题提供了宝贵的数据和场景。自Facebook出现以来,研究者先后从不同的角度对社交网络进行了大量的研究,这些研究对人们认识社交网络内部规律、促进ICP服务改进具有重大意义。首先对社交网络的发展进行了简单的回顾；然后从社交网络的数据采集技术、社交网络用户行为分析、社交网络中的信息传播及社交网络中的用户隐私4个方面对已有的研究工作进行总结评价；最后,总结了当前研究中出现的问题并对未来研究发展趋势进行了展望。希望能为该领域的研究者提供一些有益的启示。

医学图像配准分类研究

刘益含,闫德勤,刘彩凤

计算机科学. 2015, 42 (11): 22-27. doi:10.11896/j.issn.1002-137X.2015.11.003

摘要 ( 419 )

PDF(525KB) ( 1401 )

参考文献 | 相关文章 | 多维度评价

医学图像配准是医学图像研究领域的一项重要课题。配准种类包括刚性配准和非刚性配准,配准形式包括不同个体间的配准以及同一个体不同图谱的配准。介绍了基于处理流程和基于图像特征的图像配准方法以及基于变形模型的图像配准三大类。非刚性配准比刚性配准在稳定性和计算效率等方面要求更高,技术难度更大,同时具有更重要的应用意义。随着计算机技术的应用和发展,非刚性配准成为一个非常活跃的研究领域,相关的模型和方法备受关注。

内存列存储数据库中优化的混合自适应索引

薛忠斌,周烜,张延松,周新,王珊

计算机科学. 2015, 42 (11): 28-31. doi:10.11896/j.issn.1002-137X.2015.11.004

摘要 ( 239 )

PDF(432KB) ( 656 )

参考文献 | 相关文章 | 多维度评价

分析型数据库在现代企业中得到广泛应用,在使用过程中对查询处理速度的要求逐渐提高。大数据环境下,分析型数据库面临一系列新的挑战:首先,数据复杂性与日俱增,使得数据库系统的初始配置任务更加繁重,例如索引创建等；其次,在分析过程中,由于查询负载模式无法预知,需要对某些属性反复构建索引,以满足查询的时间要求。显然,传统的索引构建维护技术不能完全满足新的应用环境。数据库分裂技术提出了一种不同的策略去解决这些问题。使用数据库分裂技术,DBA不需要对数据库进行细粒度的系统配置。在查询执行过程中,数据库能自动调整以适应查询负载；随着查询负载的变化,系统自动调整索引。近年来,一系列数据库分裂算法被提出,但已有的算法都各有优缺点。因此给出了一个cache conscious的数据库分裂代价模型,并基于该模型构建了一个新的自适应索引,其可以综合不同数据库分裂算法的优势。通过大量实验验证了这种新自适应索引技术的有效性。

基于OpenCL的直方图生成算法优化方法研究

安小景,张云泉,贾海鹏

计算机科学. 2015, 42 (11): 32-36. doi:10.11896/j.issn.1002-137X.2015.11.005

摘要 ( 212 )

PDF(688KB) ( 640 )

参考文献 | 相关文章 | 多维度评价

随着GPU计算能力及可编程性的不断增强,采用GPU作为通用加速器对应用程序进行性能加速已经成为提升程序性能的主要模式。直方图生成算法是计算机视觉的常用算法,在图像处理、模式识别、图像搜索等领域都有着广泛的应用。随着图像处理规模的扩大和实时性要求的提高,通过GPU提升直方图生成算法性能的需求也越来越强。在GPU计算平台关键优化方法和技术的基础上,完成了直方图生成算法在GPU计算平台上的实现及优化。实验结果表明,通过使用直方图备份、访存优化、数据本地化及规约优化等优化方法,直方图生成算法在AMD HD7850 GPU计算平台上的性能相对于优化前的版本达到了1.8~13.3倍的提升；相对于CPU版本,在不同数据规模下也达到了7.2~210.8倍的性能提升。

Intel Knights Corner的结点级内存访问优化

林新华,李硕,赵嘉明,松岗聪

计算机科学. 2015, 42 (11): 37-42. doi:10.11896/j.issn.1002-137X.2015.11.006

摘要 ( 193 )

PDF(472KB) ( 585 )

参考文献 | 相关文章 | 多维度评价

传统编程优化(Traditional Programming Optimization,TPO)在Intel Knights Corner(KNC)上收效甚微,因此提出内存访问优化(Memory Access Optimization,MAO)。将MAO应用到已经过TPO的程序Diffusion 3D上,发现其性能仍然提高了39.1%。主要有2个贡献:1)提出MAO,认为TPO+MAO有助于在KNC上获取最优化性能；2)发现对于stencil代码,基于intrinsic的MAO比基于编译器的MAO更高效。这些发现对于在KNC上优化大规模应用有启发意义。

基于异构多核平台的同步数据流图帕累托优化与调度

顾玉磊,朱雪阳,晏荣杰,张广泉

计算机科学. 2015, 42 (11): 43-47. doi:10.11896/j.issn.1002-137X.2015.11.007

摘要 ( 194 )

PDF(661KB) ( 557 )

参考文献 | 相关文章 | 多维度评价

同步数据流图被广泛用于多媒体和数字信号处理程序等流应用程序的建模。流应用程序须达到一定吞吐量才能流畅运行,利用异构多核处理器来进一步提高流应用程序的吞吐量已经成为当今嵌入式系统的发展趋势,但是提高吞吐量往往伴随着能耗的增加。为了解决这个问题,基于异构多核平台的同步数据流图系统模型,给出了求解所有能耗和吞吐量的帕累托优化点及其相应静态调度的方法。首先将系统模型转换为时间自动机网络,并将分析目标转换为时序逻辑公式；再使用实时模型检测工具UPPAAL寻找解决方案；最后对UPPAAL返回的结果进行分析,找出满足要求的调度。由于模型检测方法可对问题空间进行穷尽搜索,该方法得到的结果是精确的。该方法可帮助设计者在系统开发早期了解系统能耗和吞吐量的量化关系,有利于缩短系统的开发周期,降低开发成本。

大数据负载的体系结构特征分析

罗建平,谢梦瑶,王华锋

计算机科学. 2015, 42 (11): 48-52. doi:10.11896/j.issn.1002-137X.2015.11.008

摘要 ( 204 )

PDF(447KB) ( 668 )

参考文献 | 相关文章 | 多维度评价

针对大数据离线分析类和交互式查询类负载,首先对这些负载的一些共性进行分析,提取出公共操作集,并对它们进行分组整理；然后在大数据平台上测试这些负载运行过程中的微体系结构特征,采用PCA和SimpleKMeans算法对这些体系结构特征参数进行降维和聚类处理。实验分析结果表明负载之间有公共的操作集,如Join和Cross Production；有些负载有相似的属性,如Difference和Projection共享相同的微体系结构特征。实验结果对于处理器等硬件平台的设计以及应用程序的优化具有指导性的意义,并且为大数据基准测试平台的设计提供了参考。

互相关运算在银河飞腾DSP上的实现及优化

杨琳,吴家铸,扈啸,田希

计算机科学. 2015, 42 (11): 53-55. doi:10.11896/j.issn.1002-137X.2015.11.009

摘要 ( 228 )

PDF(246KB) ( 727 )

参考文献 | 相关文章 | 多维度评价

在信号处理领域中,互相关运算对于寻找未知信号中的特性具有重要的作用。互相关常被用于图像匹配、粒子图像测速等领域。针对互相关运算计算量大而实时系统中要求较快运算速度的问题,利用银河飞腾多核DSP(YHFT-QDSP)的FFT加速器完成二维FFT运算,在YHFT-QDSP上实现了互相关运算,从而提高了互相关运算在实时系统中的性能,并在此基础上针对输入数据大小的不同提出了若干优化的方法,进一步提高了互相关运算的性能。

有限元网格积分算法在MIC众核平台上的并行实现

寇大治,孔大力

计算机科学. 2015, 42 (11): 56-58. doi:10.11896/j.issn.1002-137X.2015.11.010

摘要 ( 168 )

PDF(340KB) ( 519 )

参考文献 | 相关文章 | 多维度评价

基于英特尔集成众核(Many Integrated Core,MIC)架构,将有限元网格积分算法在至强融核(Xeon Phi)协处理器做了移植和性能分析。该应用全面测试了有限元分析的核心计算过程在MIC上的加速效果,实现了卸载模式(offload)[1]下利用OpenMP在MIC上的线程并行化。计算性能测试结果显示集成众核平台可以有效地加速有限元网格积分算法:1)一块被充分利用的MIC设备卡(3115A)的计算能力超过两路16核Intel XeonTM E5-2670 CPU；2)MIC并发的物理线程可能由于公共缓存访问存在竞争而降低程序的扩展性。测试结果还显示了在多CPU多MIC平台上进一步移植完整的MPI并行有限元模拟软件的可行性。这项工作有助于推动与有限元网格相关的科学和工程高性能计算的研究。

OpenFlow网络数据流路径建立开销的量化分析

吴洁,付斌章,陈明宇,张立新

计算机科学. 2015, 42 (11): 59-62. doi:10.11896/j.issn.1002-137X.2015.11.011

摘要 ( 188 )

PDF(351KB) ( 571 )

参考文献 | 相关文章 | 多维度评价

OpenFlow采用数据平面与控制平面分离的架构,以软件实现的OpenFlow控制器作为控制平面对网络进行集中控制。在这种分离架构中,由于交换机需要与控制器进行交互,因此必然会产生一定的时间开销。经实验,数据流建立过程中的信息交互导致数据包传输时延至少增长2倍,严重降低了网络性能。因此,量化分析OpenFlow网络中流建立开销具有重要意义。分析流建立开销产生的原因,对导致数据包传输时延增长的影响因素进行量化分析。评估流建立开销对网络性能的影响是量化分析数据流路径建立开销的重点。

面向定制结构的稀疏矩阵分块方法

邬贵明,王淼,谢向辉,窦勇,郭松

计算机科学. 2015, 42 (11): 63-64. doi:10.11896/j.issn.1002-137X.2015.11.012

摘要 ( 455 )

PDF(494KB) ( 554 )

参考文献 | 相关文章 | 多维度评价

稀疏矩阵向量乘是科学计算的核心问题,采用定制结构来加速稀疏矩阵向量乘的执行对提升科学计算性能具有重要意义。针对目前面向定制结构的稀疏矩阵分块方法和表示方法的缺点,提出了稀疏矩阵二维均匀分块方法和相应的表示方法嵌套分块CSR。实验结果表明,提出的稀疏矩阵分块方法和表示方法能够有效减少填零个数。

基于树型结构的MapReduce并行模型

唐兵,贺海武

计算机科学. 2015, 42 (11): 65-67. doi:10.11896/j.issn.1002-137X.2015.11.013

摘要 ( 260 )

PDF(602KB) ( 556 )

参考文献 | 相关文章 | 多维度评价

MapReduce是Google提出的一种分布式计算模型,已在海量数据处理领域得到了广泛的应用。提出一种基于树型结构的新型MapReduce并行模型。该模型适合于利用Internet或Intranet环境下不可靠的桌面PC资源进行海量科学数据分析。该模型以P2P的形式将计算节点进行组织,模型的底层采用了P2P-MPI框架,采用基于消息传递的模式来实现MapReduce应用层。在MapReduce应用层的实现中,在Map阶段采用广播的形式来分发数据块,在Reduce阶段建立反向二叉树来实现有效的结果合并和化简。将提出的MapReduce模型与现有主流MapReduce模型进行了比较,结果表明,基于树型结构的MapReduce并行模型在容错性能方面具有较优的性能,且系统简单,易于应用开发。

一种基于主动认知决策的高效能模型

杨劲,庞建民,王俊超,于锦涛,刘睿

计算机科学. 2015, 42 (11): 68-72. doi:10.11896/j.issn.1002-137X.2015.11.014

摘要 ( 240 )

PDF(423KB) ( 545 )

参考文献 | 相关文章 | 多维度评价

随着高性能计算机的发展,如何降低功耗、提高计算机的效能,越来越受到人们的关注。针对高性能计算机的效能问题,采用可重构思想,提出一种基于主动认知决策的高效能模型。该模型不断感知应用任务的实时状态,并对应用状态和当前应用结构做出评估决策,通过主动重构应用结构来达到降低系统能耗和提高效能的目的。为了验证模型的有效性,搭建了原型实验系统,实现了视频拷贝检测和口令恢复两个应用,并采用真实的互联网流量统计曲线模拟负荷。结果表明,基于该模型构建的应用能够提高系统的效能,在上述环境下,与传统方法相比,效能提高了58%。

一种基于云端信息保护的汉字计算模型

栗青生,张莉,刘泉,熊晶,杨新新

计算机科学. 2015, 42 (11): 73-79. doi:10.11896/j.issn.1002-137X.2015.11.015

摘要 ( 196 )

PDF(1106KB) ( 1263 )

参考文献 | 相关文章 | 多维度评价

提出了一种基于信息内容保护的信息安全模型。该模型利用将汉字笔画抽象为有向图的方法,设计了汉字笔画图抽象的具体方案,实现了对汉字字形结构的动态描述；建立了动态汉字字形描述库,设计了汉字字形的生成算法,实现了汉字字形的Web存储和特征字形的客户端输出。所提模型为汉字信息的云端存储和云端数据安全性保护提供了一种解决方案,不仅有助于汉字信息的安全保护,而且有助于汉字认知计算、语义计算等深度汉字信息计算。

基于MapReduce的MIC算法并行化

吕瑞,蔡国永,裴广战

计算机科学. 2015, 42 (11): 80-83. doi:10.11896/j.issn.1002-137X.2015.11.016

摘要 ( 215 )

PDF(953KB) ( 568 )

参考文献 | 相关文章 | 多维度评价

MIC是一种分析变量之间可能存在的关系的方法。该方法不仅能够有效识别出变量间各种复杂类型的关系,还能够准确描述噪音数据对存在关系的影响,对探索大数据集中变量之间的关系具有重要意义。针对该方法在处理包含大量变量的数据集时性能方面的不足,首次对它进行了基于MapReduce模型的并行化。提出的并行化方法首先对原算法进行更细颗粒度的划分,然后采用一种基于Map-Reduce-Map任务链的并行模型,该模型不仅有效地增加了并行的计算单元,还大大地降低了不必要的系统开销。最后,通过理论分析和实验验证得出,改进后的算法与原算法相比,在准确率方面具有等效性,运行速度大幅度提升且具有良好的可扩展性;实验同时指出了算法性能的提升与系统资源的关系。

面向Java锁机制的字节码自动重构框架

张杨,张冬雯,仇晶

计算机科学. 2015, 42 (11): 84-89. doi:10.11896/j.issn.1002-137X.2015.11.017

摘要 ( 237 )

PDF(807KB) ( 571 )

参考文献 | 相关文章 | 多维度评价

Java语言提供了同步锁、可重入锁和读写锁等几种锁机制,在并行程序设计中不同的数据结构使用这几种锁机制时获得的性能通常是不同的。为了在不同的锁机制之间进行自动转换,进而帮助程序员了解程序的性能,提出了一种面向Java锁机制的字节码自动重构框架,并基于该框架实现了字节码重构工具Lock2Lock。Lock2Lock在Quad中间表示的基础上对字节码进行静态分析,并对分析的结果进行一致性验证,通过Javassist完成字节码的重构。使用红黑树、消费者生产者程序以及SPECjbb2005 3个测试程序对Lock2Lock重构工具进行了测试,结果表明,Lock2Lock可以成功地实现从同步锁到可重入锁或读写锁的重构。

基于GPU并行加速的多特征融合的超图降维方法

洪朝群,陈旭辉,王晓栋,李士锦,吴克寿

计算机科学. 2015, 42 (11): 90-93. doi:10.11896/j.issn.1002-137X.2015.11.018

摘要 ( 194 )

PDF(399KB) ( 536 )

参考文献 | 相关文章 | 多维度评价

基于图的学习方法目前广泛用于降低特征维度。然而,对于多特征数据而言,不同特征之间的不同关联性很难结合到单个图中。针对多特征数据提出了新的半监督降维方法。首先,以超图中的超边作为片,使超图应用到片对齐框架中。然后,通过统计片中相邻的特征对的距离计算超边的权重,使得不同特征下的片得到结合。其次,由于欧氏距离和矩阵乘法的计算在拉普拉斯矩阵的构造过程中占用了大部分的时间,因此使用GPU对其进行加速。实验结果表明了所提方法在分类性能和学习速度上的提升效果。

基于MIC的GFSR(521,2)并行化设计与实现

顾小璐,周津羽,华诚,刘逍,周晓辉

计算机科学. 2015, 42 (11): 94-95. doi:10.11896/j.issn.1002-137X.2015.11.019

摘要 ( 465 )

PDF(246KB) ( 445 )

参考文献 | 相关文章 | 多维度评价

GFSR是一种反馈移位随机数发生器。在研究GFSR(521,2)串行算法的基础上,利用Strided skip ahead方法对其进行并行化。实验结果显示,GFSR(521,2)并行化后TestU01的测试结果与串行的相同。相对于CPU单线程,MIC平台下的最优加速比为7.58。

基于神经网络的用户视频评分自动获取方法

纪淑娟,王理,梁永全,赵建立

计算机科学. 2015, 42 (11): 96-100. doi:10.11896/j.issn.1002-137X.2015.11.020

摘要 ( 179 )

PDF(517KB) ( 439 )

参考文献 | 相关文章 | 多维度评价

在未来的智能电视系统中,真正的智能视频推荐应该是不需要用户评分动作就能自动、准确地获得用户兴趣、爱好并做出推荐的系统。研究无评分动作约束下的用户评分(揭示了他们的兴趣和爱好)自动获取技术是真正的智能推荐必须解决的一个关键问题。给出了一种基于神经网络的用户视频隐性评分自动获取方法。基于用户视频观看行为与评分样本的实验结果表明,该方法可以有效地获取用户的隐性评分信息。

归约算法统一描述

熊玉庆

计算机科学. 2015, 42 (11): 101-103. doi:10.11896/j.issn.1002-137X.2015.11.021

摘要 ( 170 )

PDF(232KB) ( 1520 )

参考文献 | 相关文章 | 多维度评价

归约算法在并行计算中应用广泛,目前有很多归约算法应用于不同的情形。这些归约算法各不相同, 逻辑拓扑是造成区别的关键。为了统一描述归约算法,揭示它们的共性,给出了一个逻辑拓扑的定义及其性质。在此基础上,给出了归约算法的统一描述,以利于对归约算法的理解,从而设计适应不同应用和环境的归约算法。该描述也可视为可集成不同语义的归约算法框架,从而有助于设计具有新语义的归约算法。本质上,该统一描述是一个归约算法形式定义,有助于验证归约算法的正确性。

基于非负邻域嵌入和非局部正则化的单帧图像超分辨率重建算法

彭羊平,宁贝佳,高新波

计算机科学. 2015, 42 (11): 104-107. doi:10.11896/j.issn.1002-137X.2015.11.022

摘要 ( 166 )

PDF(950KB) ( 541 )

参考文献 | 相关文章 | 多维度评价

单帧图像超分辨率重建是指利用一幅低分辨率图像,通过相应的算法来获取一幅高分辨率图像的技术。提出了一种基于非负邻域嵌入和非局部正则化的单帧图像超分辨率重建算法,以弥补传统邻域嵌入算法的不足。在训练阶段,首先对低分辨率图像预放大2倍,以保证在放大倍数较大时,高、低分辨率图像块之间的邻域关系也能得到较好的保持；在重建阶段,使用非负邻域嵌入来有效地解决近邻数的选取问题；最后利用图像块的非局部相似性构造非局部正则项对重建结果进行修正。实验结果表明,相对于传统算法,本方法的重建结果纹理丰富、边缘清晰。

过渡现象及其理论

洪龙

计算机科学. 2015, 42 (11): 108-111. doi:10.11896/j.issn.1002-137X.2015.11.023

摘要 ( 340 )

PDF(306KB) ( 660 )

参考文献 | 相关文章 | 多维度评价

过渡是自然界和日常生活中普遍存在的现象,它是科学研究、工程技术和社会管理中必须面对的问题。介绍了过渡现象研究的历史及现状,并分别采用传递性、区间和逻辑方法描述了过渡的一般概念。引入了左区间符【和右区间符】,并提出区间邻接概念,并采用这些概念定义了过渡,讨论了过渡的基本特征:过渡变量、过渡区域、始点、增型过渡和减型过渡等内容。另外,还展望了过渡的研究方向,这些方向的研究成果将初步形成有关“过渡”的知识结构。

一种基于Sigmoid函数的抑制Halo效应的有效算法

陈丽,郭玉坤,李金屏

计算机科学. 2015, 42 (11): 112-117. doi:10.11896/j.issn.1002-137X.2015.11.024

摘要 ( 429 )

PDF(1027KB) ( 1075 )

参考文献 | 相关文章 | 多维度评价

人们通常利用暗通道先验理论进行图像去雾,其副作用之一就是光晕现象,即Halo效应。在深入分析光晕效应特点的基础上,提出了一种基于Sigmoid函数的抑制Halo效应的有效算法。首先对带有光晕的图像进行大量观察,总结了光晕产生的位置规律及结构特性,构造了一个具有方向性的Sigmoid模板；然后对由暗通道先验理论得到的粗略透射率图进行边缘检测,获得景深突变处像素点的坐标和方向角；其次,再利用已构造的模板判断该处出现光晕的准确位置,并将非光晕区域的像素值赋给光晕区域,得到优化后的透射率图；最后引入一种容差机制还原出清晰无光晕的图像。本算法的特色在于所构造的模板仅仅处理出现光晕的区域,而不是处理整个图像区域,因此避免了传统方法中非光晕区域的颜色失真问题。实验结果表明,本算法简单易行,运行速度快,复原效果好。

基于视觉运动特性的视频时空显著性区域提取方法

周莺,张基宏,梁永生,柳伟

计算机科学. 2015, 42 (11): 118-122. doi:10.11896/j.issn.1002-137X.2015.11.025

摘要 ( 354 )

PDF(1208KB) ( 498 )

参考文献 | 相关文章 | 多维度评价

为了更准确有效地提取人眼观察视频的显著性区域,提出一种基于视觉运动特性的视频时空显著性区域提取方法。该方法首先通过分析视频每帧的频域对数谱得到空域显著图,利用全局运动估计和块匹配得到时域显著图,再结合人眼观察视频时的视觉特性,根据对不同运动特性视频的主观感知,动态融合时空显著图。实验分析从主客观两个方面衡量。视觉观测和量化指标均表明, 与其他经典方法相比,所提方法提取的显著性区域能够更准确地反映人眼的视觉注视区域。

语言真值格值命题逻辑中的α-语义归结方法

张家锋,徐扬,陈琴

计算机科学. 2015, 42 (11): 123-129. doi:10.11896/j.issn.1002-137X.2015.11.026

摘要 ( 254 )

PDF(531KB) ( 575 )

参考文献 | 相关文章 | 多维度评价

语言值智能信息处理是人工智能的一个重要研究方向,基于归结原理的自动推理因易于在计算机上实现而得到广泛研究。为了提高基于语言真值格值逻辑的α-归结原理的效率,将语义归结策略应用于α-归结原理,研究了基于格值逻辑的归结自动推理方法。首先给出了语言真值格值命题逻辑系统的α-语义归结与L_nP(X)中相应归结水平的语义归结之间的等价性,并通过实例说明其有效性。接着,给出了语言真值格值命题逻辑系统的α-语义归结算法,并证明了该算法的可靠性和完备性。

对称逻辑公式在L*₄逻辑度量空间中的分布

惠小静,赵玛瑙,高姣

计算机科学. 2015, 42 (11): 130-133. doi:10.11896/j.issn.1002-137X.2015.11.027

摘要 ( 197 )

PDF(324KB) ( 462 )

参考文献 | 相关文章 | 多维度评价

在四值逻辑系统L*₄中引入了对称逻辑公式。运用Matla软件研究了对称逻辑公式在L*₄逻辑度量空间中的计数问题,给出了3n元、3n+1元、3n+2元对称逻辑公式的个数。证明了n元对称逻辑公式占全体n元逻辑公式的比例随n的增大而趋于零。

异构复杂信息网络下的异常数据检测算法

穆丽文,彭贤博,黄岚

计算机科学. 2015, 42 (11): 134-137. doi:10.11896/j.issn.1002-137X.2015.11.028

摘要 ( 171 )

PDF(353KB) ( 611 )

参考文献 | 相关文章 | 多维度评价

异构复杂信息网络承载着不同的协议和网络信道,并通过云储存实现资源调度,由此产生的异常数据会给网络信息空间带来安全威胁和存储开销,所以需要进行异常数据准确检测。传统的检测算法采用简化梯度算法进行异常数据检测,不能有效去除多个已知干扰频率成分的异常数据,检测性能不好。提出一种基于自适应陷波级联模型的异常数据检测算法。构建异构复杂信息网络系统模型,采用固有模态分解把异常数据信号解析模型分解为多个窄带信号,设计二阶格型陷波器结构,用多个固定陷波器级联抑制干扰成份,采用匹配投影法寻求优化特征解,找出所有匹配的特征点对,从而实现异常数据检测的改进。仿真实验表明,采用该算法进行异常数据检测时,信号幅值大于干扰噪声数据幅值；该算法提高了检测性能,具有较好的抗干扰性能。

基于梯度博弈的RFID室内定位算法

施竣严,秦小麟,王宁

计算机科学. 2015, 42 (11): 138-143. doi:10.11896/j.issn.1002-137X.2015.11.029

摘要 ( 156 )

PDF(493KB) ( 379 )

参考文献 | 相关文章 | 多维度评价

随着普适计算的不断发展,室内定位技术成为了当今研究的热点问题。室内空间的复杂性使得室内空间的定位精度一直无法满足应用的需求。为了获得更加高效稳定的算法,提出了一种基于梯度和博弈论的室内定位算法,其能够较为有效地提高室内空间的定位精度。在算法中,提出了一种室内的符号划分方法,并利用其对室内空间进行了分割以辅助定位算法。最后以室内为实验环境对算法进行了验证,分析结果表明,该算法拥有良好的定位效果,并且相对于现有算法更稳定。

基于簇首成链的低能耗层次路由协议

王梦莹,王鑫,蒋华

计算机科学. 2015, 42 (11): 144-148. doi:10.11896/j.issn.1002-137X.2015.11.030

摘要 ( 164 )

PDF(453KB) ( 457 )

参考文献 | 相关文章 | 多维度评价

在LEACH协议中,活动节点的数量和簇首间通信距离是影响网络生命周期的两个重要因素。在LEACH协议的基础上设计了一种基于簇首成链的低能耗层次路由协议,该协议将网络分层成簇,簇首节点将簇内距离相近、收集信息相似的节点划分为“相似”群,群内节点按序号每次只有一个节点发送数据到簇首,减少了簇内活动节点的数量,降低了簇首负载；同时簇首间引入了链式通信。理论证明和仿真结果都表明,该算法能够均衡网络能耗,延长网络生命周期。

基于Feeds的社交网络活跃度分析

何旵阳,孙鲁敬,杨家海

计算机科学. 2015, 42 (11): 149-153. doi:10.11896/j.issn.1002-137X.2015.11.031

摘要 ( 439 )

PDF(543KB) ( 805 )

参考文献 | 相关文章 | 多维度评价

从用户产生和消费Feeds的角度分析社交网络变得不活跃的原因,通过分析人人网某大学社区用户长周期的Feeds行为来探讨该社区用户活跃度的变化。通过对用户活跃性周期和Feeds时间间隔的分析,发现越来越多的用户产生Feeds的活跃度在下降,并导致其他用户接收到的信息流的流速和多样性下降。社交网络用户由于各种原因离开或变得不活跃,并通过信息流对其朋友圈形成负向反馈,这可能是社交网络变得不活跃的深层原因。模拟实验表明,30%的初始不活跃用户会使得整个社区的信息流快速下降,并导致整个社区不活跃。

基于信号强度差的RFID室内定位研究

李军怀,贾金朋,王怀军,王志晓,张翔

计算机科学. 2015, 42 (11): 154-157. doi:10.11896/j.issn.1002-137X.2015.11.032

摘要 ( 308 )

PDF(705KB) ( 575 )

参考文献 | 相关文章 | 多维度评价

针对RFID室内定位中使用异种标签以及标签电量差异引起的信号强度差异的问题,提出一种新的基于SSD(Signal Strength Difference)的RFID指纹定位模型。该模型引入虚拟参考点,在离线阶段根据信号传播模型计算虚拟参考点的RSSI,建立SSD指纹地图,利用SSD消除异构定位读写器及电子标签的差异并解决由时间的变化引起的标签RSSI衰减问题；在在线定位阶段,采用位置匹配求交集的方法消除噪声点,然后利用K-NN算法估计目标位置。实验表明该模型具有较好的健壮性和较高的定位精度。

基于数据融合的无线传感器网络林火监控算法

刘永星,赵涓涓,常晓敏

计算机科学. 2015, 42 (11): 158-163. doi:10.11896/j.issn.1002-137X.2015.11.033

摘要 ( 143 )

PDF(548KB) ( 475 )

参考文献 | 相关文章 | 多维度评价

针对无线传感器网络在林火监控应用中存在的问题,提出了一种分层聚簇数据融合算法。簇内传感器节点使用加权平均法对原始数据进行数据级融合处理,以消除原始数据中的冗余成分,减少从簇内传感器节点到簇头节点的通信量；簇头节点采用D-S证据理论建立识别框架,通过对本簇成员的反馈信号进行决策级融合处理,提高了火灾事件的识别精度和网络的鲁棒性。实验结果表明,该算法能有效消除无线传感器网络的冗余数据,并能够在失效节点数不超过总节点数40%的情况下正确工作。

吞吐量最大化的二维无线能量传输算法

姚信威,郑星航,王万良,赵澄,杨双华

计算机科学. 2015, 42 (11): 164-169. doi:10.11896/j.issn.1002-137X.2015.11.034

摘要 ( 193 )

PDF(497KB) ( 396 )

参考文献 | 相关文章 | 多维度评价

针对无线网络中节点能量的局限性,提出了一种网络吞吐量最大化的二维无线能量传输优化算法。根据各节点捕获能量的时域分布,依次从节点维度和时间维度进行节点间的能量分配和传输。根据两节点间的高斯双工信道模型,建立基于能量传输的网络吞吐量模型。引入节点维度和时间维度的能量传输效率,建立了能量传输解析模型,并提出二维无线能量传输算法,实现了网络吞吐量最大化。实验结果表明,该算法能有效地优化网络节点能量分配,提高网络的总吞吐量。

改进的室内移动机器人模糊位置指纹定位研究

毛勤,曾碧,叶林锋

计算机科学. 2015, 42 (11): 170-173. doi:10.11896/j.issn.1002-137X.2015.11.035

摘要 ( 304 )

PDF(334KB) ( 540 )

参考文献 | 相关文章 | 多维度评价

在深入研究现有的室内机器人定位算法的基础上,提出了改进的室内机器人模糊位置指纹定位方法(IRF)。该方法首先利用样本节点之间的空间相关性,采用重心拉格朗日插值算法形成位置指纹库,然后将传统的求解高次坐标问题转换成空间隶属度问题,利用模糊匹配算法计算未知节点与指纹库中已知节点的贴近度,通过贴近度加权定位未知节点。利用卡尔曼滤波算法进行误差修正。实验结果表明,IRF定位方法与传统的定位算法相比,在降低误差、提高稳定性和效率方面具有更高的性能。

车载自组织网络协作MAC协议研究

叶翔,章国安,程黛月

计算机科学. 2015, 42 (11): 174-177. doi:10.11896/j.issn.1002-137X.2015.11.036

摘要 ( 171 )

PDF(316KB) ( 474 )

参考文献 | 相关文章 | 多维度评价

车载自组织网络(Vehicular Ad Hoc Network,VANET)的关键技术之一就是设计一个高效的媒体接入控制(Medium Access Control,MAC)协议。MAC协议因对网络的吞吐量、时延和丢包率等具有重大影响而成为研究热点。针对车载自组织网络对MAC协议的特殊性要求,提出了一种基于协作方案的TDMA MAC协议,即C-TDMA MAC。该协议中,当源节点到目的节点间直接传输失败时,其邻近辅助节点利用未被预留的时隙协作重传其先前侦听到的数据包到目的节点,而不影响其它数据包的正常传输。数值分析和仿真结果表明,所提出的协议提高了数据包成功传输的概率。

基于作业历史运行信息的MapReduce能耗预测模型

廖彬,张陶,于炯,孙华

计算机科学. 2015, 42 (11): 178-183. doi:10.11896/j.issn.1002-137X.2015.11.037

摘要 ( 260 )

PDF(529KB) ( 433 )

参考文献 | 相关文章 | 多维度评价

在数据量规模剧增的背景下,大数据处理过程中产生的高能耗问题亟待解决,而能耗模型是研究提高能耗效率方法的基础。利用传统的能耗模型计算MapReduce作业执行能耗面临诸多挑战,在对大数据计算模型MapReduce的集群结构、作业的任务分解及任务与资源映射模型分析建模的基础上,提出基于作业历史运行信息的MapReduce能耗预测模型。通过对不同作业历史运行信息的分析,得到DataNode运行不同任务时的计算能力及能耗特性,继而实现在MapReduce作业执行前对作业能耗的预测。实验结果验证了能耗预测模型的可行性,并通过对能耗预测准确率调节因子的修正,能够达到提高能耗模型的预测准确度的目的。

未知单协议数据帧的地址分析与研究

郑杰,朱强

计算机科学. 2015, 42 (11): 184-187. doi:10.11896/j.issn.1002-137X.2015.11.038

摘要 ( 224 )

PDF(412KB) ( 400 )

参考文献 | 相关文章 | 多维度评价

网络协议是网络通信中一系列标准的集合,未知协议的识别和分析对网络监管、保障网络安全具有重大意义。协议识别技术多种多样,但在协议的分析识别过程中,为了实现协议的简单高效识别,通常需要将未知混合多协议分离为单协议,然后再进行进一步的识别。在将未知混合数据帧分离为单协议的基础上,提出了一种高效的确定单协议位置信息的方法,即进一步将单协议的数据帧按地址分为点对点数据帧,从而实现未知协议的最终识别。最后通过分析ARP、TCP数据对该方法进行评估,结果表明采用该方法可以找到2/3以上的地址信息。

复杂网络中基于采样的近似三角计数方法研究

黄取治,张军朝

计算机科学. 2015, 42 (11): 188-190. doi:10.11896/j.issn.1002-137X.2015.11.039

摘要 ( 237 )

PDF(306KB) ( 536 )

参考文献 | 相关文章 | 多维度评价

复杂网络中的三角计数可以用于分析网络的同质性和传递性。为了提高复杂网络中三角计数的性能,提出了一种基于采样的近似三角计数方法。首先,以一定的采样概率对网络中的边进行采样从而得到一个子网络,并在该子网络中统计三角的个数。其次,依据采样的概率思想,应用子网络中的三角个数估计原网络中的三角个数。最后,对采样方法的均值和方差进行了理论分析,并给出了由采样方法得到的加速比。理论分析与实验表明,与传统的节点迭代方法相比,提出的方法在保证高准确性的前提下大大提高了算法的运行效率,因而更适用于大规模网络中基于三角计数的相关应用。

基于动态权限集的Android强制访问控制模型

徐潜,谭成翔

计算机科学. 2015, 42 (11): 191-196. doi:10.11896/j.issn.1002-137X.2015.11.040

摘要 ( 219 )

PDF(1114KB) ( 516 )

参考文献 | 相关文章 | 多维度评价

针对Android存在的特权提升攻击问题,提出了基于动态权限集的Android强制访问控制模型DP_ManDroid。该模型首先分析强连通分支的权限分布特性,构建动态的权限集划分；然后在信息流与权限集耦合的基础上,抽象权限提升路径；最后提出线性时间的访问控制算法,并通过动态追踪权限集,实现了细粒度的决策控制。与现有安全模型的对比,以及在原型系统上的仿真结果表明,所提出的安全模型很好地抵御了特权提升攻击,同时降低了时间复杂度。

标准模型下增强的无需安全信道的带关键词搜索的公钥加密

方黎明,黄志球,王建东

计算机科学. 2015, 42 (11): 197-202. doi:10.11896/j.issn.1002-137X.2015.11.041

摘要 ( 187 )

PDF(498KB) ( 454 )

参考文献 | 相关文章 | 多维度评价

Baek,Safavi-Naini和Susilo提出了无需安全信道的带关键词搜索的公钥加密方案。该方案中的安全模型限制了攻击者的能力,并且方案是在随机预言模型下可证安全的。然而在随机预言模型下证明安全的方案在实际执行中会导致不安全。通过改进安全模型使得攻击者能力更强,即允许攻击者获得非挑战密文和陷门之间的关系,同时构造了在增强的安全模型下不使用随机预言机可证安全的带关键词搜索的公钥加密方案。

基于键盘行为进行用户识别的方法与应用

王昱杰,赵培海,王咪咪

计算机科学. 2015, 42 (11): 203-207. doi:10.11896/j.issn.1002-137X.2015.11.042

摘要 ( 327 )

PDF(529KB) ( 636 )

参考文献 | 相关文章 | 多维度评价

基于键盘行为的已有研究大多限制在实验环境下,并限定用户的输入为特定字符串,或只在有限实验参与者中进行识别,从而导致其无法应用在真实的环境中。为了克服已有研究的局限,解决真实环境中正负样本不均衡和负样本缺失的问题,对真实环境下一千万条用户击键行为进行分析,提出了一种基于键盘行为进行用户识别的方法。该方法使用击键持续时间和击键间隔时间描述用户的击键行为,通过实验选择马氏距离进行用户击键行为相似度的对比,并对未知击键行为进行预测。实验结果表明,该方法可获得80%的预测准确率。

CLEFIA-128算法的不可能差分密码分析

邱丰品,卫宏儒

计算机科学. 2015, 42 (11): 208-211. doi:10.11896/j.issn.1002-137X.2015.11.043

摘要 ( 334 )

PDF(270KB) ( 727 )

参考文献 | 相关文章 | 多维度评价

为研究分组密码CLEFIA-128抵抗不可能差分攻击的能力,基于一条9轮不可能差分路径,分析了13轮不带白化密钥的CLEFIA-128算法。利用轮函数中S盒差分分布表恢复部分密钥,利用轮密钥之间的关系减少密钥猜测量,并使用部分密钥分别猜测(Early Abort)技术有效地降低了复杂度。计算结果表明,该方法的数据复杂度和时间复杂度分别为O(2103.2)和O(2124.1)。

基于Snort的Modbus TCP工控协议异常数据检测规则设计

姜伟伟,刘光杰,戴跃伟

计算机科学. 2015, 42 (11): 212-216. doi:10.11896/j.issn.1002-137X.2015.11.044

摘要 ( 358 )

PDF(1033KB) ( 977 )

参考文献 | 相关文章 | 多维度评价

工业控制网络通信协议的脆弱性是导致工控网络遭受攻击的主要因素。Modbus TCP是工控网络的典型通信协议。在对Modbus TCP协议进行脆弱性分析的基础上,结合Snort检测机制对典型的异常行为进行归类,提出了一种用于Snort的Modbus TCP协议异常数据流检测模板。Modbus TCP的分析和规则模板的设计方法也可推广至其他基于工业控制协议的网络,具有一定的普适性。

缩减轮数Crypton算法中间相遇攻击的改进

李永光,曾光,韩文报

计算机科学. 2015, 42 (11): 217-221. doi:10.11896/j.issn.1002-137X.2015.11.045

摘要 ( 179 )

PDF(1201KB) ( 509 )

参考文献 | 相关文章 | 多维度评价

Crypton密码算法是韩国学者提出的一种AES候选算法。通过研究Crypton算法的结构特征和一类截断差分路径的性质,利用差分枚举技术权衡存储复杂度和数据复杂度,提出了4轮和4.5轮中间相遇区分器。新的区分器减少了预计算表中的多重集数量,降低了存储复杂度。基于4轮区分器首次给出对7轮Crypton-128的中间相遇攻击,时间复杂度为2¹¹³,数据复杂度为2¹¹³,存储复杂度为290.72。基于4.5轮区分器首次给出对8轮Crypton-192的中间相遇攻击,时间复杂度为2¹⁷²,数据复杂度为2¹¹³,存储复杂度为2¹³⁸。

口令强度评估的分级先验模型研究

沈瑛,廖刘承,董天阳

计算机科学. 2015, 42 (11): 222-227. doi:10.11896/j.issn.1002-137X.2015.11.046

摘要 ( 200 )

PDF(508KB) ( 696 )

参考文献 | 相关文章 | 多维度评价

拒绝用户设置弱口令是系统信息安全防护的一种重要手段。针对完整口令集设计并实现了一个不同于基于规则的先验口令检验器的口令分级先验组合模型。利用马尔可夫模型,结合影响口令强度的长度、频次、首字母等相关因素,设计了有效的口令强度评估函数,并根据强度值分布设置阈值对全口令集进行合理分级,并将结果导入布鲁姆过滤器中,以在保证分级口令自身安全的同时,减少口令先验检索的时耗。多口令库实验结果表明:口令强度评价结果合理,分级结果在先验口令检测方面具有较好的适用性。

互联网环境中基于环境激发效应的协同式概念建模

蒋逸,张伟,赵海燕,金芝

计算机科学. 2015, 42 (11): 228-234. doi:10.11896/j.issn.1002-137X.2015.11.047

摘要 ( 369 )

PDF(824KB) ( 575 )

参考文献 | 相关文章 | 多维度评价

随着领域的规模性和复杂性不断增加,建立领域的概念模型往往超出了个人的能力。通过对群体智慧的聚集与组织,采用协同方法构建模型具有重要意义。基于社会性昆虫的群体协同机制——环境激发效应,提出了一种互联网环境下面向大规模群体的协同式概念建模方法。该方法具有两个特点:a)提供一种以环境为媒介的间接交互方式,解决了群体协同的规模可扩展性问题；b)提供一种协同的激励机制,初步解决了松散异步的沟通方式下群体协同一致的问题。这使得协同建模者能够相互借鉴知识经验来完善概念模型。在此基础上,通过实例研究对该方法的可行性和有效性进行了验证。

云环境下基于数据流的k-means聚类算法

王飞,秦小麟,刘亮,沈尧

计算机科学. 2015, 42 (11): 235-239. doi:10.11896/j.issn.1002-137X.2015.11.048

摘要 ( 230 )

PDF(512KB) ( 823 )

参考文献 | 相关文章 | 多维度评价

k-means算法是一种最常用的基于划分的聚类算法。传统的集中式k-means算法已不能适应当前呈爆炸式增长的数据规模,设计分布式k-means算法成为了目前亟需解决的问题。现有分布式k-means算法基于MapReduce计算框架且没有考虑初始聚类中心的影响。由于每个MapReduce任务均需要读写分布式文件系统,导致MapReduce不能有效表达多个任务之间的依赖关系,因此提出了一种基于数据流的计算框架,该框架建立在MapReduce之上,将数据处理过程按照数据流图建模。在该框架的基础上,提出了一种高效的k-means算法,它采用基于多次采样的初始聚类中心选取方法来实现负载均衡及减少迭代次数。实验结果表明,该算法的可扩展性较好,且效率比现有算法高。

基于条件分类的控制流向量化

孙回回,赵荣彩,高伟,李雁冰

计算机科学. 2015, 42 (11): 240-247. doi:10.11896/j.issn.1002-137X.2015.11.049

摘要 ( 160 )

PDF(616KB) ( 635 )

参考文献 | 相关文章 | 多维度评价

现代编译器越来越依赖SIMD指令来提高向量化性能,但控制流的复杂性严重阻碍了SIMD向量化的发掘。现有的控制流向量化方法对于单层控制流的向量化很有效,但对嵌套等复杂控制流无法取得令人满意的效果。因此,提出了一种基于条件分类的控制流向量化方法。该方法对条件为循环不变量的控制流,以层次遍历的顺序实施IF外提；对条件为循环变量的控制流,结合语句匹配和条件合并递归地进行IF转换,生成相应的SIMD指令,从而实现嵌套控制流的向量化。实验结果表明,该方法能够有效消除循环中的嵌套控制流,提高向量化发掘的能力, 有效提升测试程序的性能。

一种改进的无偏节点标签预测方法研究

俞刚,张泉方

计算机科学. 2015, 42 (11): 248-250. doi:10.11896/j.issn.1002-137X.2015.11.050

摘要 ( 306 )

PDF(318KB) ( 429 )

参考文献 | 相关文章 | 多维度评价

在社会网络中,用户的位置和属性以及图片的标签预测等都具有广泛的应用前景。为了提高标签预测的性能,提出了一种改进的无偏节点标签预测算法。首先,对社会网络中的标签预测问题进行了形式化描述。其次,基于所有观察数据的训练目标的联合概率最大化与以这些数据为条件的单变量边缘预测值的不匹配现象,提出了一种改进的图模型训练方法。最后,通过对置信度的无偏估计,基于子图方法提出一种不包含额外标签数据的无偏算法用于模型的训练。在Twitter和Pokec数据集上的实验表明,提出的算法与相关的标签预测算法相比,其准确性和运行效率都得到了明显的提升。

基于精简关联度的基因表达数据迭代填补算法

何云,皮德常

计算机科学. 2015, 42 (11): 251-255. doi:10.11896/j.issn.1002-137X.2015.11.051

摘要 ( 178 )

PDF(472KB) ( 524 )

参考文献 | 相关文章 | 多维度评价

基因表达数据时常出现缺失,阻碍了对基因表达的研究。提出了一种新的相似性度量方案——精简关联度,在此基础上,又提出了基于精简关联度的缺失数据迭代填补算法(RKNNimpute)。精简关联度是对灰色关联度的一种改进,能达到与灰色关联度同样的效果,却显著降低了算法的时间复杂度。RKNNimpute算法以精简关联度作为相似度量,将填补后的基因扩充到近邻的候选基因集,通过迭代的方式填补其他缺失数据,提高了算法的填补效果和性能。选用时序、非时序、混合等不同类型的基因表达数据集进行了大量实验来评估RKNNimpute算法的性能。实验结果表明,精简关联度是一种高效的距离度量方法,所提出的RKNNimpute算法优于常规填补算法。

差分进化算法中参数自适应选择策略研究

汪慎文,张文生,丁立新,谢承旺,郭肇禄

计算机科学. 2015, 42 (11): 256-259. doi:10.11896/j.issn.1002-137X.2015.11.052

摘要 ( 192 )

PDF(314KB) ( 718 )

参考文献 | 相关文章 | 多维度评价

参数选择本身是一个组合优化问题,尽管过去提出了很多方法,但是参数选择依然令人困惑,为此提出适用于差分进化算法的参数自适应选择策略。该策略在进化的过程中动态评估参数的性能,并根据其结果指导下一次迭代过程的参数选择。从参数库的建立、参数评分机制和参数配置机制3方面展开研究,对比实验结果表明,该方法效果良好。

创造性驱动优化算法

邹儒,冯翔

计算机科学. 2015, 42 (11): 260-265. doi:10.11896/j.issn.1002-137X.2015.11.053

摘要 ( 205 )

PDF(467KB) ( 493 )

参考文献 | 相关文章 | 多维度评价

模拟人类的创造性思维来求解问题一直是人工智能研究的热点和难点之一。基于当前的创造性思维研究理论,同时借鉴现有自然启发算法的建模过程,提出了一种新的智能优化算法——创造性驱动优化算法(Creativity Driven Optimization Algorithm,CDOA)。首先,构建出创造性驱动优化模型,并且为其5个子模型设计出具体的操作算子。而后,根据各子模型之间的联系,给出创造性驱动优化算法的执行步骤。为验证创造性驱动优化算法的有效性,使用8个CEC-2013实参数优化基准函数对CDOA进行了测试,并与当前最先进的3个同类算法进行对比。实验结果显示,CDOA在复杂函数上具有较好的寻优能力。最后,对CDOA进行的计算复杂度实验及分析表明,在相同实验条件下,与其他3个对比算法相比,CDOA具有更快的执行速度。

七星瓢虫优化算法及其在多学科协同优化中的应用

王鹏,李洋,王昆仑

计算机科学. 2015, 42 (11): 266-269. doi:10.11896/j.issn.1002-137X.2015.11.054

摘要 ( 172 )

PDF(352KB) ( 654 )

参考文献 | 相关文章 | 多维度评价

基于对七星瓢虫觅食行为的研究,提出一种新的生物学启发式算法——七星瓢虫优化算法(Seven-spot Ladybird Optimization,SLO)。通过6个标准测试函数将其与现有的两种启发式算法(GA、PSO)进行比较,探知其寻优能力。在此基础上,针对多学科设计优化协同优化算法求解效率不高、鲁棒性差等缺陷,将SLO引入协同优化算法系统级优化器,通过工程实例验证了七星瓢虫优化算法良好的寻优能力。

基于PCA和SVM的普通话语音情感识别

蒋海华,胡斌

计算机科学. 2015, 42 (11): 270-273. doi:10.11896/j.issn.1002-137X.2015.11.055

摘要 ( 183 )

PDF(355KB) ( 792 )

参考文献 | 相关文章 | 多维度评价

在语音情感识别中,情感特征的选取与抽取是重要环节。目前,还没有非常有效的语音情感特征被提出。因此,在包含6种情感的普通话情感语料库中,根据普通话不同于西方语种的特点,选取了一些有效的情感特征,包含Mel频率倒谱系数、基频、短时能量、短时平均过零率和第一共振峰等,进行提取并计算得到不同的统计量；接着采用主成分分析(PCA)进行抽取；最后利用基于支持向量机(SVM)的语音情感识别系统进行分类。实验结果表明, 与其他一些重要的研究结果相比,该方法得到了较高的平均情感识别率, 且情感特征的选取、抽取及建模是合理、有效的。

基于改进的可能度优势关系的排序方法研究

张其文,王雪勤,庄新磊

计算机科学. 2015, 42 (11): 274-278. doi:10.11896/j.issn.1002-137X.2015.11.056

摘要 ( 146 )

PDF(427KB) ( 413 )

参考文献 | 相关文章 | 多维度评价

优势关系是解决多属性决策问题的一种重要方法,也是研究不完备区间值信息系统的一种重要方法。在不完备区间值信息系统排序方法的研究中,针对属性过多从而可能引起排序失效的问题,提出了一种改进的可能度优势关系排序方法。这种新的排序方法把区间值优势关系和可能度相结合来改进经典优势关系定义的不足,并给出了平均综合优势度的定义。最后,通过与 ∝-β优势关系和容差优势关系等排序方法在具体算例中的比较分析,证明了改进的可能度优势关系排序方法不仅能够解决不完备区间值信息系统中的问题,而且能够使排序结果更合理、有效。

基于最大后验概率估计的压缩感知算法

庄燕滨,王尊志,肖贤建,张学武

计算机科学. 2015, 42 (11): 279-283. doi:10.11896/j.issn.1002-137X.2015.11.057

摘要 ( 276 )

PDF(664KB) ( 452 )

参考文献 | 相关文章 | 多维度评价

针对压缩感知重构算法计算代价较大的问题,提出了一种用来构建压缩感知稀疏数据重构算法的MAP方法。此方法相对于一般的观测矩阵来说,计算代价较低。₁-范数使用一个标准的线性规划算法的最小计算代价是O(N³),该方法通过使用最大后验方法使计算代价减少到O(N²),并通过引入分割比来使算法更好地收敛。实验证明此方法能够获得较为成功的重构区域。

基于视觉特征的网页最优分割算法

李文昊,彭红超,童名文,石俊杰

计算机科学. 2015, 42 (11): 284-287. doi:10.11896/j.issn.1002-137X.2015.11.058

摘要 ( 235 )

PDF(713KB) ( 651 )

参考文献 | 相关文章 | 多维度评价

网页分割技术是实现网页自适应呈现的关键。针对经典的基于视觉的网页分割算法VIPS(Vision-based Page Segmentation Algorithm)分割过碎和半自动的问题,基于图最优划分思想提出了一种新颖的基于视觉的网页最优分割算法VWOS(Vision-based Web Optimal Segmentation)。考虑到视觉特征和网页结构,将网页构造为加权无向连通图,网页分割转化为图的最优划分,基于Kruskal算法并结合网页分割的过程,设计网页分割算法VWOS。实验证明,与VIPS相比,采用VWOS算法分割网页的语义完整性更好,且不需要人工参与。

基于进化深度学习的特征提取算法

陈珍,夏靖波,柏骏,徐敏

计算机科学. 2015, 42 (11): 288-292. doi:10.11896/j.issn.1002-137X.2015.11.059

摘要 ( 340 )

PDF(398KB) ( 1054 )

参考文献 | 相关文章 | 多维度评价

信息全面与维数灾难的矛盾是大数据时代网络态势感知需要解决的首要难题。特征提取一直是主流的降维方法,但现有算法对高维非线性数据效果不佳；深度学习是一类具有多层非线性映射的学习算法,可以完成复杂函数的逼近,但对隐层相关参数十分敏感。针对上述问题,将进化算法的思想引入深度学习,提出了一种基于进化深度学习的特征提取算法。该算法利用遗传算法及进化策略实现全局搜索及优化的特点,并对深度学习结构及相关参数进行了优化。理论分析及实验结果都证明了该算法的有效性。

基于局部和全局特征视觉单词的人物行为识别

谢飞,龚声蓉,刘纯平,季怡

计算机科学. 2015, 42 (11): 293-298. doi:10.11896/j.issn.1002-137X.2015.11.060

摘要 ( 180 )

PDF(1061KB) ( 591 )

参考文献 | 相关文章 | 多维度评价

基于视觉单词的人物行为识别由于在特征中加入了中层语义信息,因此提高了识别的准确性。然而,视觉单词提取时由于前景和背景存在相互干扰,使得视觉单词的表达能力受到影响。提出一种结合局部和全局特征的视觉单词生成方法。该方法首先用显著图检测出前景人物区域,采用提出的动态阈值矩阵对人物区域用不同的阈值来分别检测时空兴趣点,并计算周围的3D-SIFT特征来描述局部信息。在此基础上,采用光流直方图特征描述行为的全局运动信息。通过谱聚类将局部和全局特征融合成视觉单词。实验证明,相对于流行的局部特征视觉单词生成方法,所提出的方法在简单背景的KTH数据集上的识别率比平均识别率提高了6.4%,在复杂背景的UCF数据集上的识别率比平均识别率提高了6.5%。

基于非下采样轮廓波的MRI图像的压缩感知重构

陈秀梅,王敬时,王伟,赵扬,汤敏

计算机科学. 2015, 42 (11): 299-304. doi:10.11896/j.issn.1002-137X.2015.11.061

摘要 ( 250 )

PDF(1056KB) ( 533 )

参考文献 | 相关文章 | 多维度评价

压缩感知是一种全新的信息采集与处理的理论框架,借助信号内在的稀疏性或可压缩性,可从小规模的线性、非自适应的测量值中通过非线性优化的方法精确重构信号。压缩感知以远低于奈奎斯特频率的采样频率,在压缩成像系统、医学图像处理等领域有着广阔的应用前景。提出算法采用非下采样轮廓波变换稀疏表达原始图像,通过傅立叶矩阵进行测量,最后采用迭代软阈值算法实现医学MRI图像的压缩感知重构。以峰值信噪比、互信息、伪影功率为评价指标,比较小波变换、频率局部化轮廓波变换以及非下采样轮廓波变换三者的压缩感知重构效果。实验结果表明,无论采样率设置如何变化,提出算法在峰值信噪比、原始信息保留比例以及重构精度等方面均具有明显优势,在快速医学成像领域具有广阔的应用前景。

一种基于SIFT特征光流的运动目标跟踪算法

李艳萍,林建辉,杨宁学

计算机科学. 2015, 42 (11): 305-309. doi:10.11896/j.issn.1002-137X.2015.11.062

摘要 ( 391 )

PDF(927KB) ( 565 )

参考文献 | 相关文章 | 多维度评价

针对传统光流跟踪算法计算复杂度高、受噪声影响大的问题,提出了一种基于尺度不变特征变换(Scale Invariant Feature Transform,SIFT)和卡尔曼滤波器的特征点光流跟踪算法。首先,利用SIFT算法提取图像中的特征点；然后,根据最小绝对值误差准则对运动目标的特征点进行匹配,建立卡尔曼滤波器方程来计算特征点光流；最后,通过光流特征聚类实现运动目标的识别与跟踪。实验结果表明,算法对自然场景中的运动目标具有良好的跟踪特性,稳定性好,计算量小,易于实现。

基于系统误差和状态联合估计的目标跟踪算法

胡玉梅,胡振涛,郑珊珊,李贤,郭振

计算机科学. 2015, 42 (11): 310-313. doi:10.11896/j.issn.1002-137X.2015.11.063

摘要 ( 169 )

PDF(400KB) ( 521 )

参考文献 | 相关文章 | 多维度评价

针对线性系统中系统误差对状态估计精度造成的不利影响,在卡尔曼滤波算法框架下提出一种基于系统误差和状态联合估计的目标跟踪算法。在算法实现过程中,首先定量分析了系统误差对目标状态估计及其估计误差协方差矩阵的影响,进而结合状态扩维技术构建系统误差配准的实现过程,最终依据标准卡尔曼滤波迭代流程设计了算法实现步骤。仿真实验结果表明: 在系统误差恒定和时变两种情况下,新算法在系统误差配准和状态估计上具有可行性和有效性。

基于全景视觉的移动机器人的运动目标检测

汤一平,胡大卫,蔡盈梅,黄珂,姜荣剑

计算机科学. 2015, 42 (11): 314-319. doi:10.11896/j.issn.1002-137X.2015.11.064

摘要 ( 296 )

PDF(780KB) ( 479 )

参考文献 | 相关文章 | 多维度评价

在动态背景下的运动目标检测中,由于目标和背景两者都是各自独立运动的,在提取前景运动目标时需要考虑由移动机器人自身运动引起的背景变化。仿射变换是一种广泛用于估计图像间背景变换的方法。然而,在移动机器人上使用全方位视觉传感器(ODVS)时,由于全方位图像的扭曲变形会造成图像中背景运动不一致,无法通过单一的仿射变换描述全方位图像上的背景运动。将图像划分为网格窗口,然后对每个窗口分别进行仿射变换,从背景变换补偿帧差中得到运动目标的区域。最后,根据ODVS的成像特性,通过视觉方法解析出运动障碍物的距离和方位信息。实验结果表明,提出的方法能准确检测出移动机器人360°范围内的运动障碍物,并实现运动障碍物的精确定位,有效地提高了移动机器人的实时避障能力。