计算机科学

一种大数据放置方法

张桂刚

计算机科学. 2014, 41 (6): 1-4. doi:10.11896/j.issn.1002-137X.2014.06.001

摘要 ( 225 )

PDF(427KB) ( 428 )

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

数据密集型应用越来越多,如何将大数据在数据中心实现有效放置变得日益重要。研究了大数据的放置模型。影响大数据放置的因素主要有:能耗、异构节点的服务能力及具有关联计算的数据集。基于这3个因素设计了一种节能、充分考虑异构节点服务能力及提升MapReduce处理Join连接的效率的大数据放置模型。该模型将有效实现大数据的有效放置管理,同时也为未来软件定制数据中心奠定了基础。

TVBRT:一种基于Radial Tree的具有度量属性的多变元时态数据可视化方法

孙宁伟,赵瑜,刘勇,刘海峰,肖卫东,张翀

计算机科学. 2014, 41 (6): 5-11. doi:10.11896/j.issn.1002-137X.2014.06.002

摘要 ( 234 )

PDF(1174KB) ( 656 )

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

多变元时态数据大量存在于社会科学、环境监测、金融经济、医疗卫生及地理信息等领域。对多变元时态数据集进行深入分析,创新性地将经典的层次数据可视化方法Radial Tree加以改进,提出集成度量属性的Radial Tree布局算法(LAMPRT)、基于Radial Tree的具有度量属性的多变元时态数据可视化布局算法(LOVEBRT),结合相应的人机交互策略,形成可视化方法TVBRT。案例研究证明了该方法的有效性,并表明它能展示数据集中的细节内容。TVBRT方法侧重于对数据进行层次分析,适合于展示对具体度量值更为关心的数据集。

面向异构众核从核的数学函数库访存优化方法

许瑾晨,郭绍忠,黄永忠,王磊

计算机科学. 2014, 41 (6): 12-17. doi:10.11896/j.issn.1002-137X.2014.06.003

摘要 ( 272 )

PDF(1221KB) ( 524 )

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

数学库函数算法的特性致使函数存在大量的访存,而当前异构众核的从核结构采用共享主存的方式实现数据访问,从而严重影响了从核的访存速度,因此异构众核结构中数学库函数的性能无法满足高性能计算的要求。为了有效解决此问题,提出了一种基于访存指令的调度策略,亦即将访存延迟有效地隐藏于计算延迟中,以提高基于汇编实现的数学函数库的函数性能；结合动态调用方式,利用从核本地局部数据存储空间LDM(local data memory),提出了一种提高访存速度的ldm_call算法。两种优化技术在共享存储结构下具有普遍适用性,并能够有效减少函数访存开销,提高访存速度。实验表明,两种技术分别能够平均提高函数性能16.08%和37.32%。

同构多核/众核处理器任务分配自适应模拟退火算法

闫乔,覃志东,王绍宇,闫红曼

计算机科学. 2014, 41 (6): 18-21. doi:10.11896/j.issn.1002-137X.2014.06.004

摘要 ( 192 )

PDF(434KB) ( 451 )

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

随着多核/众核处理器核心数快速增加,任务分配解空间急剧增大,降低近似解的相对偏差越来越难。提出一种自适应模拟退火算法,建立了模拟退火算法中参数与优化环境任务数和核心数的关系。核心数的增加不但可以有效降低近似解的相对偏差,而且使任务分配算法具有较高的环境自适应能力。与较近研究成果相比较,在16核心时,自适应模拟退火算法迭代次数增加41%,相对偏差降低86%。

基于闭合最小图划分模型的多作业分配优化方法

张拥军,林宇斐

计算机科学. 2014, 41 (6): 22-26. doi:10.11896/j.issn.1002-137X.2014.06.005

摘要 ( 151 )

PDF(414KB) ( 401 )

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

随着并行计算系统规模的增大和复杂度的提高,已有的多作业分配方式可能导致较长的通信延迟和严重的通信竞争。针对这一问题,提出了一种基于闭合最小图划分模型的多作业分配优化方法。该方法以最小化通信延迟和消除通信竞争为出发点,通过建立闭合最小图划分模型,将多作业分配优化问题转化成闭合最小图划分问题,并设计闭合最小图划分算法来获得优化的多作业分配方案。

认知无线电分簇子网频谱决策

赵俊,廖名学,何晓新,郑昌文

计算机科学. 2014, 41 (6): 27-30. doi:10.11896/j.issn.1002-137X.2014.06.006

摘要 ( 289 )

PDF(414KB) ( 396 )

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

树形认知无线电分簇子网采用多簇并行工作模式,其频谱决策涉及子网容量、吞吐量与子网稳定性3方面因素,计算复杂度高。针对多簇子网的频谱决策问题,建立了三层优先级决策模型,并提出一种启发式决策算法。该算法基于簇结构和簇生长度构造无重复的搜索空间,并以当前最优解更新的搜索步长为启发式条件,贪心搜索增长率更高的子网结构,引入子网容量下限、可用频谱及子网速率双门限,对解空间进行严格剪枝。仿真结果表明,在相应频谱空间和子网规模等约束条件下,该算法能够获得最优解且满足实时性需求。

权重感知的三维室内无线传感器网络部署算法

庞博,秦小麟,江国华,刘亮

计算机科学. 2014, 41 (6): 31-36. doi:10.11896/j.issn.1002-137X.2014.06.007

摘要 ( 177 )

PDF(543KB) ( 472 )

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

已有室内受限空间无线传感器网络部署问题的研究均未综合考虑各种部署应用需求以及障碍物对无线传感器信号的干扰,导致传感器感知与通信能力的浪费。为解决上述问题,提出了一种基于启发式算法的无线传感器网络部署算法,该算法利用贪心策略在有障碍的三维室内环境中进行部署,并在此基础上设计了权重感知的遗传算法优化策略用以求解全局最优部署方案。部署算法利用分权的方式描述不同空间区域的重要性,利用带方差的对数正态阴影模型建模信号衰减过程,在获得最大覆盖效果的同时最小化部署开销,并保证空间k覆盖和网络连通性。实验结果表明,障碍物对无线传感器节点造成一定影响时,提出的WCRH算法与OWCRG算法的性能均优于使用传统Line-of-Sight(LoS)模型的基于面积开销比的启发式算法。

异构无线网络终端服务感知的动态负载均衡机制

罗俊辉,白光伟,沈航,曹磊

计算机科学. 2014, 41 (6): 37-42. doi:10.11896/j.issn.1002-137X.2014.06.008

摘要 ( 153 )

PDF(549KB) ( 442 )

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

异构无线网络负载均衡是提高网络服务质量的关键技术之一。现有负载均衡机制大多没有考虑用户的个性化业务在请求网络资源时存在的差异,同时缺乏一种用户满意度保障机制。针对这一问题,提出一种终端服务感知的动态负载预先均衡机制。首先,采用模糊数学的推理方法,计算出终端对各个候选网络的接入期望值。在此基础上,充分考虑各候选网络的资源拥塞状况,有选择性地将该终端用户业务链接切换到低资源拥塞率、高接入期望值网络中,从而缓解网络中的局部热点,提高网络资源有效利用率与用户满意度。仿真结果表明,该机制能够显著均衡网络中各个无线接入点的工作负荷,有效减少拥塞发生的概率,改善用户的网络体验。

基于网络拓扑和地理特征融合的朋友关系预测模型

罗惠,郭斌,於志文,王柱,封云

计算机科学. 2014, 41 (6): 43-47. doi:10.11896/j.issn.1002-137X.2014.06.009

摘要 ( 194 )

PDF(434KB) ( 405 )

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

朋友关系预测已成为基于位置的社交网络(LBSN)的主要研究方向之一。提出一种基于网络拓扑特征和地理融合的面向LBSN的朋友关系预测方法。首先,利用信息增益评估不同特征对朋友关系的影响,最终选取3种重要特征:用户社交拓扑、用户签到地点类型和用户签到地点。然后,提出基于这3种特征融合的朋友关系预测方法,分别采用随机森林、支持向量机和朴素贝叶斯3种分类算法建模实现朋友关系推理。最后通过Foursquare和街旁的实际签到数据验证了特征选取的有效性和朋友关系预测的准确性。

基于多目标演化算法的云计算虚拟机分配策略研究

艾浩军,龚素文,袁远明

计算机科学. 2014, 41 (6): 48-53. doi:10.11896/j.issn.1002-137X.2014.06.010

摘要 ( 152 )

PDF(732KB) ( 398 )

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

分析云计算虚拟机资源模型,针对模型中虚拟机与物理机的映射关系以及虚拟机多资源因子、多优化目标的特点,将虚拟机分配问题转化成多维装箱问题,引入多目标演化算法进行求解。算法设计了基于组的虚拟机分配链式编码和染色体评估函数,并根据编码设计了两种交叉算子和智能变异算子,通过引入基于超体积的种群更新机制,设计了基于SMS-EMOA的云计算虚拟机分配算法。为验证SMS-EMOA的性能,分别使用优先匹配启发式算法、基于物理节点数量的单目标简单遗传算法、SMS-EMOA进行了模拟。实验结果表明,基于SMS-EMOA的虚拟机分配算法在性能上更优。

基于节点感应度的自主决策目标跟踪算法

郑瑾,吕朋朋,呙邵明

计算机科学. 2014, 41 (6): 54-58. doi:10.11896/j.issn.1002-137X.2014.06.011

摘要 ( 145 )

PDF(907KB) ( 457 )

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

目标跟踪是无线传感器网络的一项基本应用。由于传感器节点能量有限,如何在保证跟踪精度的前提下降低节点能耗以延长网络生命周期一直是研究的重点之一。文中采用RNG平面化技术将无线传感器网络平面化为多边形跟踪结构,基于定位边,采用加权质心算法对目标位置进行估计,结合节点对目标感应质量与距离负相关的特性,给出了节点感应度的计算方法,同时提出了一种节点自主决策是否参与跟踪的目标跟踪算法(NS-ADTT)。该算法中,节点可根据自身感应度值及局部网络情况自主决策是否参与当前跟踪。仿真结果表明,在目标跟踪过程中,该算法在保证一定跟踪精度的基础上减少了参与跟踪的节点数,降低了网络能耗,有效地延长了网络生命周期。

一种基于机制理论的云市场多类型资源分配定价机制

沈张果,楼俊钢,马小龙,麻旺勇

计算机科学. 2014, 41 (6): 59-62. doi:10.11896/j.issn.1002-137X.2014.06.012

摘要 ( 151 )

PDF(400KB) ( 436 )

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

为避免在云服务资源分配中因参与人的自私性而造成的个人效用与社会收益的冲突,在所有参与人都是理性的这一共同知识假定下,针对云市场多类型资源分配问题,首先给出其形式化描述,设计了基于机制理论的分配定价机制,该机制能在复杂用户任务请求下进行资源有效分配,保证个人效用与社会收益最大化。最后证明该机制满足个体理性、预算均衡和激励兼容性质,并给出该机制下寻求任务请求成本最小和效用最大的算法。

基于GPU的并行奇异值分解最小平方估计算法

李繁,金明录,刘继

计算机科学. 2014, 41 (6): 63-68. doi:10.11896/j.issn.1002-137X.2014.06.013

摘要 ( 145 )

PDF(444KB) ( 613 )

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

对奇异值分解(SVD)求解最小平方估计的问题进行了研究。提出迭代式分割与合并的算法(IDMSVD),目的是解决奇异值分解在估计参数时非常耗费内存空间的问题。基于IDMSVD提出了并行IDMSVD算法,并使用GPU实现之。实验结果显示,IDMSVD可以有效地解决SVD求最小平方解耗费运行时间与内存空间的问题,并行IDMSVD算法可进一步改善IDMSVD的运行时间。

基于负载均衡的虚拟网映射随机算法

余建军,吴春明

计算机科学. 2014, 41 (6): 69-74. doi:10.11896/j.issn.1002-137X.2014.06.014

摘要 ( 338 )

PDF(556KB) ( 423 )

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

分析了基于“尽力服务”模式的虚拟网映射算法所存在的问题,并指出了其在资源均衡利用方面的不足,设计了物理网负载均衡代价指标,提出了负载均衡的虚拟网映射随机算法。实验表明,所提出的算法能提高物理网资源的负载均衡度和利用率,从而提高虚拟网构建请求的接受率和物理网提供商的收益。

BitTorrent网络节点间流量的数据采集和分析

鄢羽,唐红

计算机科学. 2014, 41 (6): 75-78. doi:10.11896/j.issn.1002-137X.2014.06.015

摘要 ( 144 )

PDF(314KB) ( 533 )

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

BitTorrent网络流量占据了互联网总流量的很大比例,吸引了大量专家学者的专注,然而现有实测工具无法实时记录BT网络中节点间的流量交互情况,有关真实BT网络中节点间流量的研究很少。建立了一个BT网络节点间流量的数据采集系统,将其部署在全球性实验平台Planetlab之后得到了真实数据,并验证了数据的正确性。通过对实测数据的分析和研究发现:(1)Tracker服务器在为各下载节点随机返回邻居节点列表时会受到各节点入网时间的影响；(2)50%以上的下载节点从种子处下载的数据为零,大部分下载节点的数据下载对种子的依赖性不大,从而深刻地体现出P2P应用模式的优越性。

基于多种性能约束的光突发交换网络动态组装算法

牛大伟,李歧,于卫波,米志超

计算机科学. 2014, 41 (6): 79-83. doi:10.11896/j.issn.1002-137X.2014.06.016

摘要 ( 222 )

PDF(539KB) ( 417 )

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

在综合分析光突发交换网络中组装算法对控制平面处理时延、数据平面资源利用效率和数据平面突发丢失率等多种性能指标的影响的基础上,提出了一种能够同时满足多种网络性能指标约束的边缘节点动态组装算法。该算法根据全网目标性能指标的约束,动态调整组装输出的突发长度和突发时间门限,从而实现同时满足全网链路资源利用率和控制平面突发丢失概率的双重性能约束。

一种支持密文转码的JPEG2000图像加密算法

傅勇,易小伟,马恒太

计算机科学. 2014, 41 (6): 84-88. doi:10.11896/j.issn.1002-137X.2014.06.017

摘要 ( 154 )

PDF(1004KB) ( 426 )

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

针对异构化程度不断加剧的通信网络环境对码率转换能力的需求,提出了一种支持密文域转码的层次化加密算法CT-HEA。与以往基于JPEG2000图像的加密算法相比,CT-HEA针对率失真优化截断模型的特点,按照图像质量层和分辨率对压缩流重新进行截断与合并,对重组后的码流采用密码学算法进行分层加密。该算法支持对加密压缩流的透明码率转换。仿真实验结果表明,CT-HEA算法复杂度低、保密性好,具有灵活的安全转码特性和低的转码代价。

一种车载自组织网络路况信息的数据信任模型

王光浩,吴越

计算机科学. 2014, 41 (6): 89-93. doi:10.11896/j.issn.1002-137X.2014.06.018

摘要 ( 196 )

PDF(490KB) ( 449 )

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

动态寻路是解决城市交通拥堵的重要手段。在动态寻路中,一些车辆产生和转发路况信息,使其他车辆能够避开拥堵路段。但一般车载自组织网络寻路算法缺乏验证路况信息的真实性的措施,导致恶意车辆能轻易篡改路况信息,误导其他车辆选择错误路线。提出了一种路况信息鉴别模型,该模型将基于数据的信任模型应用到路况信息真伪的鉴别中,并在一般投票算法的基础上利用D-S理论增加不确定情况下的鲁棒性。仿真实验表明,该算法在不增加额外信息交互的前提下,有效规避了恶意伪造信息,改进了车辆的行程时间。

一种基于多域特征的JPEG图像隐写分析算法

汪磊,曾宪庭,苏金阳

计算机科学. 2014, 41 (6): 94-98. doi:10.11896/j.issn.1002-137X.2014.06.019

摘要 ( 209 )

PDF(425KB) ( 514 )

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

为实现对以JPEG图像为载体的隐秘图像的高效检测,提出了一种基于多域特征的通用隐写分析算法。该算法结合两种不同校准方法在图像不同域中对原始载体图像的估计能力,分别从图像DCT域、空域和DWT域中提取特征向量,提高了特征向量对隐秘信息的敏感性,达到了隐秘图像的高效检测。实验结果表明,与现有几种典型的通用隐写分析算法相比,所提算法具有很好的检测效果且稳定性好、运算速度快。

一种改进的基于信号强度的WLAN定位方法

孙善武,王楠,陈坚

计算机科学. 2014, 41 (6): 99-103. doi:10.11896/j.issn.1002-137X.2014.06.020

摘要 ( 175 )

PDF(655KB) ( 415 )

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

与室外定位技术相比(如GPS),基于无线局域网(Wireless Area Network)的定位更适用于室内环境。两种基于接收信号强度(RSSI,Received Signal Strength Indication)的定位方法即位置指纹法和信号传播模型法广泛用于室内定位的研究。使用边界盒算法和改进的二分范围搜索算法将两种室内定位方法相结合,提出了一种改进的基于RSSI的定位方法。提出的方法根据指纹数据库中样本的横纵坐标对其进行预处理,同时使用改进的线性二分范围搜索算法降低指纹数据库中的样本数,进而提高实时定位过程的效率。最大化位置指纹维度,并添加时间维,同时通过实验数据阐明所提出的方法可提高用户位置估算的精确度。

基于多值属性分量的XACML策略匹配算法

李冬辉,张斌,费晓飞,刘洋

计算机科学. 2014, 41 (6): 104-107. doi:10.11896/j.issn.1002-137X.2014.06.021

摘要 ( 240 )

PDF(289KB) ( 443 )

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

针对多值属性分量的XACML策略和策略请求之间的匹配需求,分析多值属性策略匹配中策略规则与请求匹配时两者的对应属性关系,依据属性之间的包含关系和权限蕴含关系,给出3个关于策略匹配的定理并加以证明。根据策略匹配的定理,提出多值属性匹配算法。最后进行实验验证,结果表明该算法能够提高多值属性分量策略的匹配效率。

基于信任值的云存储数据确定性删除方案

冯贵兰,谭良

计算机科学. 2014, 41 (6): 108-112. doi:10.11896/j.issn.1002-137X.2014.06.022

摘要 ( 197 )

PDF(514KB) ( 390 )

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

数据确定性删除是云存储安全的研究热点。目前云存储中分散式的数据确定性删除方案在密钥分量存储时没有考虑DHT((Distributed Hash Table)节点可信性,使得用户在授权时间内也存在无法访问自己敏感数据的问题。为此提出了一种基于信任值的云存储数据确定性删除方案,该方案的核心是对DHT节点进行可信度评价,密钥分量的存储选择可信度较高的节点。与已有的确定性删除方案相比,该方案仍然是利用DHT网络的动态特性实现密钥的定期删除,使得用户敏感数据能够在特定的一段时间之后自动销毁。不同的是,该方案在将密钥分量分发到DHT网络中时倾向于选择可信度高的节点进行交互,使得在密钥的过期时间戳之前从DHT网络中得到足够多的密钥分量来恢复出密钥的可能性大大提高,降低了用户在授权时间内无法访问自己敏感数据的概率。实验结果表明,该方案不仅可以有效地抑制恶意节点,还可以提高密钥分量提取成功率,从而增加用户在授权时间内访问自己敏感数据的成功率。

面向NUMA集群的代数多重网格算法优化

顾坚,刘伟

计算机科学. 2014, 41 (6): 113-118. doi:10.11896/j.issn.1002-137X.2014.06.023

摘要 ( 331 )

PDF(573KB) ( 834 )

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

代数多重网格(AMG)是众多数值模拟应用的核心算法,在基于多核的NUMA架构的机群系统上,AMG的并行扩展性暴露了新的问题。通过设计感知NUMA架构的内存分配器,将划分给多个线程的数据分割并绑定到运行对应线程的CPU所属的NUMA存储节点上,从而改善了OpenMP多线程并行的数据局部性,使BoomerAMG程序在大规模多核计算平台上具有更好的并行扩展性。在单节点和小规模机群的测试中,使用NAAlloc分配器分别获得了最高16%和60%的性能提升。

基于推荐质量的信任感知推荐系统

王海艳,周洋

计算机科学. 2014, 41 (6): 119-124. doi:10.11896/j.issn.1002-137X.2014.06.024

摘要 ( 297 )

PDF(673KB) ( 431 )

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

推荐系统在解决信息过载方面已经取得了很大的成功,同时也存在数据稀疏、冷启动等问题。如何在评分数据稀疏的情况下获得满意的推荐成为推荐系统亟待解决的问题。将信任引入推荐系统成为解决上述问题的有效方法之一。已有的信任感知推荐系统大多基于布尔型信任关系,且没有考虑信任的领域相关性。在服务选择领域,服务请求者依据QoS(quality of service)选择服务。联想到在服务推荐领域推荐请求者可以依据推荐质量(quality of recommendation,QoR)选择推荐用户,提出了推荐质量(QoR)的概念和基于推荐质量的信任感知推荐系统。QoR的属性包含评价相似度、领域信任值、领域相关度和亲密程度,利用信息熵方法可确定各属性的权重。仿真表明该方法提高了推荐系统在数据稀疏情况下的精确度和评分覆盖率,有效提高了冷启动用户的召回率,在一定程度上解决了冷启动问题。

基于分解的多值模型的逼近关系

陈娟娟,魏欧

计算机科学. 2014, 41 (6): 125-130. doi:10.11896/j.issn.1002-137X.2014.06.025

摘要 ( 132 )

PDF(465KB) ( 402 )

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

多值模型可用于对包含不确定与不一致信息的软件系统进行建模与验证。提出了采用基于分解的方式来刻画多值模型之间的逼近关系,这为采用抽象方法解决模型检测时所产生的状态爆炸问题奠定了理论基础。为此,首先给出了多值模型分解为多个三值模型的方法,并且证明了任意μ演算公式在多值模型上的检测结果等于在分解后所有三值模型上的检测结果的合并。进一步,由三值模型上的混合模拟关系给出了多值模型间逼近关系的结构定义,并证明对于任意给定的两个满足逼近关系的多值模型,μ演算公式在其上的检测结果在信息序关系上得以保持。

一种利用UML的软件需求阶段风险评估方法

刘锦行,夏红霞

计算机科学. 2014, 41 (6): 131-135. doi:10.11896/j.issn.1002-137X.2014.06.026

摘要 ( 217 )

PDF(445KB) ( 446 )

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

在软件开发活动早期阶段评估软件的风险及其影响程度将有效减少软件开发成本和降低软件开发风险。针对目前软件风险评估的研究主要集中在软件过程的中后期阶段的现状及遵循“尽早识别和控制风险”的实践准则,提出了一种在软件需求分析阶段,利用UML建模图形度量软件风险的方法。该方法主要关注在软件需求分析阶段预防软件风险,为降低风险在软件开发后期产生严重影响提供优化参考。

动态受限区域内的单纯型连续近邻链查询方法

李松,张丽平,朱德龙,郝晓红

计算机科学. 2014, 41 (6): 136-141. doi:10.11896/j.issn.1002-137X.2014.06.027

摘要 ( 173 )

PDF(526KB) ( 404 )

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

受限区域内的单纯型连续近邻链查询在空间数据挖掘、数据的相似分析和推理、空间数据库等方面具有重要的作用。为了弥补已有方法的不足,详细研究了动态受限区域内的单纯型连续近邻链查询方法。基于计算几何中的Voronoi图给出了VOR_IN_CRSCNNC算法、VOR_EX_CRSCNNC算法和VOR_DE_CRSCNNC算法。进一步进行了实验比较和分析。理论研究和实验分析表明,所提出的算法在查询过程中减少了数据逐一筛选和判断的冗余计算,在处理空间数据量较大、初始受限区域数据量较多、受限区域形状较为复杂的单纯型连续近邻链查询方面具有较大的优势。

PBPP:列存储系统中基于传递块缓冲区的流水线并行处理

丁祥武,张光辉

计算机科学. 2014, 41 (6): 142-147. doi:10.11896/j.issn.1002-137X.2014.06.028

摘要 ( 177 )

PDF(485KB) ( 355 )

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

片上多核处理器(CMP)凭借其低功耗和低成本等优势迅速成为处理器市场的主角,它为多线程的实现提供了硬件支持。列存储技术在分析型应用中具有显著的优势。在列存储系统中,查询优化依然是最重要的问题之一。在列存储系统中,利用多核资源提高查询处理性能具有较大潜力。文中通过对查询执行器生成的物理查询树进行流水多线程设计,结合列存储的特点,建立传递块缓冲区,使主线程和辅助线程分别对传递块缓冲区读写,以提高查询性能。同时还提出使用操作系统中经典的“生产者和消费者”模式来解决线程之间的同步问题。提出的这些方法应用在实验室研发的列存储系统DWMS中,使用数据仓库基准测试集SSB验证了这些方法的有效性。实验结果表明,传递块缓冲区的设计使SQL的查询效率有了近50%的提升。

基于LaTex的Web数学公式提取方法研究

陈立辉,苏伟,蔡川,陈晓云

计算机科学. 2014, 41 (6): 148-154. doi:10.11896/j.issn.1002-137X.2014.06.029

摘要 ( 403 )

PDF(609KB) ( 1253 )

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

数学论坛、Wiki等社会性网站对数学教育的影响日益增长,数学公式广泛存在这些网站中,如何对这些网站中的数学公式进行搜索,对学习和科研非常重要。数学公式提取是索引系统的前提和基础,文中主要研究LaTex格式的数学公式的提取方法,结合BNF表述方式,提出自动分析提取包含LaTex公式特征的方法。依据公式包含的特征,提出提取和过滤LaTex数学公式的方法规则。通过实验发现,该方法的查全率达到75%,查准率达到99%。

自适应云端的大规模导出子图提取算法

郭鑫,董坚峰,周清平

计算机科学. 2014, 41 (6): 155-160. doi:10.11896/j.issn.1002-137X.2014.06.030

摘要 ( 177 )

PDF(619KB) ( 604 )

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

针对现有云计算平台资源随机调配与传统导出子图挖掘效率较低等问题,进一步提升云计算平台中资源整合利用效率与大规模导出子图挖掘效率,提出了一种自适应云端的大规模导出子图提取算法,以解决资源优化利用与海量图挖掘等问题。首先介绍了云计算概念与导出子图挖掘相关概念以及问题描述；接着根据MapReduce并行处理模型设计了一种自适应任务动态分配算法SAC_TA(Self Adaptive Cloud Dynamic Allocation),它根据计算任务自适用分配系统资源以达到成本消耗的最优；并设计出自适应云端框架,然后基于自适应云端提出了大规模导出子图挖掘算法SFGFF(SAC_TA、Find_VE、G_F1、FindPartFG、FindAllFG),它共分为4个阶段的挖掘,将所有算法应用到自适应云端中可构成整个导出子图挖掘体系；最后在人工模拟数据与真实环境数据下进行了试验, 结果表明,自适应云端运行良好,算法有效可行,具有较高的加速比与运行效率,能有效满足大规模频繁导出子图挖掘的需求。

基于拉普拉斯方向的差值线性判别分析

李照奎,丁立新,王岩,何进荣,周凌云

计算机科学. 2014, 41 (6): 161-165. doi:10.11896/j.issn.1002-137X.2014.06.031

摘要 ( 159 )

PDF(965KB) ( 361 )

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

标准的LDA方法通常有3个问题:1)为了确保类内散度矩阵的非奇异性,必须首先通过PCA进行维数约简,这限制了对更多维数空间的使用；2)当每人只有单个训练样本时,类内散度矩阵必然奇异,此时LDA无法工作；3)缺乏对像素间的局部相关性的考虑。为了解决这些问题,提出一种基于拉普拉斯方向的差值线性判别分析方法。该方法通过拉普拉斯方向实现更鲁棒的图像相异性测度,通过引入差值散度矩阵来避免类内散度矩阵的奇异性。实验结果显示,该算法对表情变化、光照改变及不同遮挡情况获得了更高的识别率,尤其针对光照变化,效果更加显著。

支持向量回归增量学习

张一凡,冯爱民,张正林

计算机科学. 2014, 41 (6): 166-170. doi:10.11896/j.issn.1002-137X.2014.06.032

摘要 ( 214 )

PDF(418KB) ( 751 )

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

针对支持向量回归因时空复杂度较高而无法处理大规模数据的问题,提出了一个新颖的增量学习模型——L增量υ支持向量回归(L Incremental υ Support Vector Regression,LISVR)。该模型针对支持向量丢失所产生的不利影响,通过不断对支持向量样本加权并及时淘汰非支持向量,降低了时空复杂度。从理论上证明了算法可收敛到全局最优解。结合人工数据集、UCI数据集和机场噪声的实际问题对该算法做了相应测试,结果验证了算法的有效性。

基于语义互补推理的文献隐含知识的发现方法研究

温浩,温有奎

计算机科学. 2014, 41 (6): 171-175. doi:10.11896/j.issn.1002-137X.2014.06.033

摘要 ( 163 )

PDF(663KB) ( 752 )

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

文献知识发现已经成为解决海量信息检索难题的突破技术。但是目前的文献知识发现方法是基于词袋法的矢量空间模型方法。这类方法具有词汇元素之间语义无关性的先天不足,不能有效地发现文本之间存在的大量潜在知识。提出一种基于主谓宾(S,P,O)结构的最小知识单元表示及其语义推理的中文文献知识发现方法,避免了传统的文献知识发现方法的不足,并在此模型的基础上提出了一种推理算法,其能有效地发现文本中的潜在知识。经过实验证明,该方法与传统的文献知识发现方法相比有效地提高了潜在知识发现的正确率。

多agent规划领域中的观察信息约简

伍选,文中华,汪泉,常青

计算机科学. 2014, 41 (6): 176-179. doi:10.11896/j.issn.1002-137X.2014.06.034

摘要 ( 147 )

PDF(464KB) ( 502 )

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

观察信息约减是近年来不确定规划中的研究热点,但研究集中于单个agent的环境,在多agent规划环境下的研究不足。面对多agent环境下的规划问题,设计了一种用于不确定规划领域中多agent求解协同规划解的ORMAP算法。该算法首先根据基于模型检测的不定规划中的状态分层思想,将问题领域的所有状态进行分层,以此来减少不同的agent的冲突,再利用以最小代价优先的回溯法搜索协同规划解,同时在解的搜索过程中选择最小的观察信息集,使求出的协同规划解在众多符合条件的协同规划解中所需要的观察信息最少或接近最少,这样就达到了信息约简的目的。最后通过实验证明,在考虑了观察信息约简的限制条件后,这种算法的效率较高。

SPFA算法的分析及改进

夏正冬,卜天明,张居阳

计算机科学. 2014, 41 (6): 180-184. doi:10.11896/j.issn.1002-137X.2014.06.035

摘要 ( 545 )

PDF(428KB) ( 762 )

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

SPFA(Shortest Path Faster Algorithm)算法是一种对任意有向图求单源最短路径的算法。该算法实现简单,实际运行效果较好,在国内有着比较大的影响力。但遗憾的是,该算法一直缺少正确的理论分析。对该算法进行了分析,指出该算法在不存在源点可达负圈的有向图中,最坏情况运行时间为Θ(|V||E|)；在存在源点可达负圈的有向图中,算法将无限运行下去。对此,给出了改进的SPFA算法,对于任意的有向图,该算法能够在O(|V||E|)内运行完毕。最后,从实际运行角度将SPFA算法与其它思想上同源的最短路径算法进行了一系列比较。

时序最短路径算法

邓冬梅,王冠楠,朱建,高辉,陈端兵

计算机科学. 2014, 41 (6): 185-187. doi:10.11896/j.issn.1002-137X.2014.06.036

摘要 ( 356 )

PDF(319KB) ( 860 )

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

最短路径是指网络中两结点间阻碍强度最小的一条路径。传统的最短路径是在静态网络上进行研究的,然而现实生活中很多网络是动态的、有时序性的,因此传统的最短路径算法并不能用于解决所有最短路径问题。为了寻找时序网络上的最短路径,在Dijkstra算法思想基础上,提出一种时序最短路径的精确算法。文中利用严格的数学推导证明了本算法的可行性,并通过对构建的网络做实证分析验证了算法的正确性。

企业云应用演进策略多时段分析

殷星,周剑雄,王明哲

计算机科学. 2014, 41 (6): 188-192. doi:10.11896/j.issn.1002-137X.2014.06.037

摘要 ( 179 )

PDF(467KB) ( 395 )

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

随着云计算技术的发展,企业急需一种有效方法将原本孤立的应用系统向云平台迁移。将网络层次分析法(ANP)及其超级矩阵收敛过程应用于企业云应用演进计划制定,提出一个演进策略的多时段分析方法。通过对企业云应用体系结构的建模与仿真分析,构建ANP多属性决策模型,解析超级矩阵从初始状态到极限状态的收敛过程,挖掘各云应用系统的分时段关键性影响因素,为企业的整体演进策略提供支持。最后,通过一个案例展示多时段分析方法的具体过程,提取出相关关键因素,为企业策略的动态规划提供理论依据。

空间生命支持系统中VCCR子系统的安全性验证

李倩,郁文生

计算机科学. 2014, 41 (6): 193-198. doi:10.11896/j.issn.1002-137X.2014.06.038

摘要 ( 317 )

PDF(959KB) ( 404 )

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

基于动态微分逻辑的混成系统形式化验证理论,分析空间生命支持系统的一个子系统VCCR(Variable Configuration Carbon Dioxide Removal)的安全性。将VCCR系统基于混成程序建模,并给定需验证的安全性性质,使用KeYmaera混成系统形式化验证工具进行验证,证明了空间生命支持系统中VCCR子系统的安全性。

基于自适应粒子群优化的代价评估Marginalized粒子滤波

胡振涛,魏丹,金勇,胡玉梅

计算机科学. 2014, 41 (6): 199-203. doi:10.11896/j.issn.1002-137X.2014.06.039

摘要 ( 141 )

PDF(450KB) ( 385 )

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

针对量测受扰动情况下粒子重要性权重的精确度量和粒子的有效采样问题,提出了一种基于自适应粒子群优化的代价评估Marginalized粒子滤波。首先,在Marginalized粒子滤波框架下,通过引入代价函数和风险函数,实现了粒子重要性权重评价过程中对最新量测信息的合理利用,以降低传统的依据重要性权重度量方式中对于噪声先验信息的依赖。其次,通过对粒子分布特征信息的提取和利用,构建了粒子极限速度设定的自适应选取策略,给出了一种自适应粒子群优化方法。在此基础上,结合粒子群优化中群体优化机理来提升采样粒子对被估计状态的逼近程度,进而改善重采样后粒子的多样性。理论分析和仿真实验验证了算法的有效性。

关键词自动提取方法的研究与改进

黄磊,伍雁鹏,朱群峰

计算机科学. 2014, 41 (6): 204-207. doi:10.11896/j.issn.1002-137X.2014.06.040

摘要 ( 228 )

PDF(368KB) ( 665 )

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

关键词提取技术是信息检索和文本分类领域的基础与关键技术之一。首先分析了TFIDF算法中存在的不足,即IDF(Inverse Document Frequency)权值中没有考虑特征词在类内以及类别间的分布情况。因此,原有的TFIDF方法会出现有些不能代表文档主题的低频词的IDF值很高,而有些能够代表文档主题的高频词的IDF值却很低的情况,这会导致关键词提取不准确。通过增加一个新的权值,即类内离散度DI(Distribution Information)来增加关键的特征词条的权重,提出了一种新的算法DI-TFIDF。实验中使用的是搜狗语料库,选择其中的体育、教育和军事3类文档各1000篇作为实验的语料库,分别用基于传统TFIDF方法和基于DI-TFIDF方法提取关键词。实验结果表明,所提出的DI-TFIDF方法提取关键词的准确度要高于传统的TFIDF算法。

基于残余抗原学说的动态记忆风险识别模型

陶媛,胡珉,王萍

计算机科学. 2014, 41 (6): 208-213. doi:10.11896/j.issn.1002-137X.2014.06.041

摘要 ( 149 )

PDF(489KB) ( 390 )

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

以小概率事件风险识别为研究对象,提出一个基于残余抗原学说的动态记忆风险识别模型DMRIM。DMRIM针对小概率事件风险的无规则等特点,将风险的强度和频度直观地、动态地映射为残余抗原的浓度,以残余抗原刺激免疫记忆、指导抗体进化、控制识别器的生命周期,突破了传统的记忆细胞生命周期,实现了识别器分布自制,提高了小概率事件的辨识能力。仿真实验表明,DMRIM充分体现免疫记忆的动态性,有效地识别小概率事件,其可行性在实际应用中得到了验证。

垃圾邮件过滤中信息增益的改进研究

翟军昌,秦玉平,车伟伟

计算机科学. 2014, 41 (6): 214-216. doi:10.11896/j.issn.1002-137X.2014.06.042

摘要 ( 372 )

PDF(361KB) ( 395 )

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

针对垃圾邮件过滤中的特征项选择问题,提出了一种改进的信息增益方法。首先利用特征词的先验概率定义增益比,然后利用增益比对特征词为整个分类所提供的信息量进行放大或弱化,从而对特征词的类别条件熵计算作了改进,采用极大后验假设朴素贝叶斯决策方法在英文语料库上进行实验,通过召回率、正确率、精确率和错误率对算法进行评价分析。实验结果表明,改进后的算法提高了过滤器的分类精度,降低了过滤器对合法邮件的误判给用户带来的损失。

Dijkstra算法中的多邻接点与多条最短路径问题

王树西,李安渝

计算机科学. 2014, 41 (6): 217-224. doi:10.11896/j.issn.1002-137X.2014.06.043

摘要 ( 596 )

PDF(654KB) ( 2442 )

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

Dijkstra算法是图论中求取最短路径的经典算法。列举并分析了Dijkstra算法及其伪码,为了深刻理解Dijkstra算法,列举了几种错误观点并加以纠正。分析发现,根据Dijkstra算法,最短路径上的某个顶点的前面,可能有多个邻接点；从开始点到某个顶点之间,可能存在多条权重相同的最短路径。对于上述多邻接点问题与多条最短路径问题,Dijkstra算法并没有涉及。分析了多邻接点问题与多条最短路径问题的成因,提出解决方案,对Dijkstra算法进行了改进,给出了改进之后的算法与伪码,分析了算法的时间复杂度,并用c语言编码实现。实验结果表明,改进之后的Dijkstra算法可以有效解决多邻接点问题与多条最短路径问题。

基于贝叶斯与多故障推理的Web服务诊断

贾志淳,邢星

计算机科学. 2014, 41 (6): 225-230. doi:10.11896/j.issn.1002-137X.2014.06.044

摘要 ( 180 )

PDF(486KB) ( 388 )

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

Web服务组合进程规模的不断增加和复杂性的不断提高都有可能导致服务的运行失败,因此很难确保服务的可靠性。针对传统的基于模型的方法无法处理服务应用系统中状态和行为故障的不确定性问题,提出了一种基于贝叶斯与多故障逻辑推理的诊断方法。该方法使用历史数据构建服务执行矩阵,通过多故障逻辑推理技术获取候选诊断解并利用贝叶斯公式计算候选解的后验概率并排序,最终获得一个最优的诊断结果。相比于传统基于模型的Web服务诊断方法,该方法不仅可以同时定位多个故障,而且能够随着历史数据的增加不断优化诊断结果。实验证明该方法具有很好的诊断效果。

一种改进的基于加权网络的蛋白质复合物识别算法

赵碧海,熊慧军,倪问尹,刘志兵,胡赛

计算机科学. 2014, 41 (6): 231-234. doi:10.11896/j.issn.1002-137X.2014.06.045

摘要 ( 194 )

PDF(334KB) ( 414 )

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

不断增长的蛋白质相互作用数据使我们能够采用计算方法预测蛋白质复合物。然而,由于实验条件和技术的限制,现有的PPI网络中包含噪声。为了降低噪声对复合物识别所产生的负面影响,提出了一种改进的名为WPC的算法,用于从加权网络中识别蛋白质复合物。给定一个选定节点,所有邻居节点组成候选集,候选集中节点的邻居节点组成邻居集。对于候选集中的节点,若该节点在候选集与邻居集间的加权比低于设定阈值,则将该点剔除。处理后的候选集被标记为复合物。对于没有包含在任何复合物中的节点,如果节点在某一复合物内的平均加权度超过一个自适应的阈值,则将其补充到该复合物中。对WPC算法和现有的几种经典蛋白质复合物识别算法的性能进行了综合比较。实验结果表明,WPC算法的性能优于几种对比的复合物识别算法。

蝉鸣优化:一种新的仿生进化算法

贺毅朝,李宁,李文斌

计算机科学. 2014, 41 (6): 235-238. doi:10.11896/j.issn.1002-137X.2014.06.046

摘要 ( 229 )

PDF(379KB) ( 568 )

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

借鉴秋蝉鸣叫中表现出的某种同步化以及蝉的生活习性提出了一种新的仿生优化算法:蝉鸣优化(CSO),分析并指出了CSO除具有一般进化算法的特性外还具有两点独特的特性,并基于有限Markov链理论证明了CSO的渐近收敛性。利用CSO、PSO和DE对9个高维Benchmark函数的仿真计算比较表明:CSO是一种非常适于求解数值最优化问题的进化算法。

基于Tile Coding编码和模型学习的Actor-Critic算法

金玉净,朱文文,伏玉琛,刘全

计算机科学. 2014, 41 (6): 239-242. doi:10.11896/j.issn.1002-137X.2014.06.047

摘要 ( 423 )

PDF(455KB) ( 703 )

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

Actor-Critic是一类具有较好性能及收敛保证的强化学习方法,然而,Agent在学习和改进策略的过程中并没有对环境的动态性进行学习,导致Actor-Critic方法的性能受到一定限制。此外,Actor-Critic方法中需要近似地表示策略以及值函数,其中状态和动作的编码方法以及参数对Actor-Critic方法有重要的影响。Tile Coding编码具有简单易用、计算时间复杂度较低等优点,因此,将Tile Coding编码与基于模型的Actor-Critic方法结合,并将所得算法应用于强化学习仿真实验。实验结果表明,所得算法具有较好的性能。

一种基于尾匹配q-gram的近似串匹配算法

孙德才,王晓霞

计算机科学. 2014, 41 (6): 243-249. doi:10.11896/j.issn.1002-137X.2014.06.048

摘要 ( 248 )

PDF(603KB) ( 793 )

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

近似串匹配是生物信息学、文本检索、信号处理等领域的一个基础问题,如何提高近似串匹配的速度一直都是研究的关键问题。提出一种新的在大文本库中快速查找近似匹配的无损过滤算法。为保证在大文本库中的匹配速度,本算法使用了查询速度较快的q-gram索引。为通过提高过滤算法的过滤效率达到提升算法整体性能的目的,详细分析了含有匹配串的文本区域,提取了一些基于尾匹配q-gram特征的新过滤条件,然后用这些特征优化了过滤算法的过滤标准。实验数据表明,新过滤条件有效地提高了算法的过滤效率,提升了算法的整体性能。结果显示新算法适合各种匹配错误率下的近似匹配,算法的通用性较强。

基于Petri网的数据库日志分析方法研究

景波,刘莹,陈耿

计算机科学. 2014, 41 (6): 250-253. doi:10.11896/j.issn.1002-137X.2014.06.049

摘要 ( 155 )

PDF(323KB) ( 367 )

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

为提高对复杂ERP系统的审计效率,提出了通过数据库日志快速发现系统中存在的不合规业务流程的方法。该方法利用数据库中已有的结构关系来确定日志操作中工作流程的次序,并通过Petri网中的a-算法对数据库日志进行转换,将转换后的真实业务流与合规业务流进行差异比较,使审计人员能较直观和准确地判断出系统中存在的异常业务流程。

改进人工蜂群算法求解多目标连续优化问题

葛宇,梁静,王学平,谢小川

计算机科学. 2014, 41 (6): 254-259. doi:10.11896/j.issn.1002-137X.2014.06.050

摘要 ( 331 )

PDF(548KB) ( 385 )

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

针对多目标连续优化问题,依据人工蜂群算法原理给出其求解流程,并指出算法中更新策略存在盲目搜索和丢失优秀个体的不足,随后提出改进方案。改进方案包含两部分:首先,设计一种自适应搜索算子,使算法在运行过程中能根据个体质量自动调节搜索范围,让算法搜索行为准确高效；其次,利用外部集合记录下新产生的个体,一次迭代完成后结合外部集合重新构造种群,让算法能有效地保存进化过程中产生的优秀个体。实验中将改进人工蜂群算法与NSGA2算法、改进前算法以及文献报道的同类优秀算法进行了比较,结果说明:改进人工蜂群算法在求解多目标连续优化问题中具有良好的收敛性和均匀性。

基于改进自适应聚类算法的RBF神经网络分类器设计与实现

郝晓丽,张靖

计算机科学. 2014, 41 (6): 260-263. doi:10.11896/j.issn.1002-137X.2014.06.051

摘要 ( 175 )

PDF(341KB) ( 544 )

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

针对传统径向基函数神经网络构造的网络分类器通常存在分类精度不高、训练时间长等缺陷,首先提出了一种改进的自适应聚类算法,用于确定分类器的隐含层节点。该算法通过筛选基于轮廓系数的优秀样本群,来寻找最佳初始聚类中心,避免了传统K-means算法易受初始聚类中心点影响,导致最终的分类效果严重偏离全局等情况的发生。其次,将该改进算法用于构造径向基函数神经网络分类器和快速有效地确定隐含层节点径向基函数中心及函数的宽度。最后,通过大量UCI数据集的实验和仿真,验证了改进算法在聚类时间、聚类轮廓系数及聚类正确率等方面具有优越性。同时,大量的仿真实验也证明了基于改进算法构造的RBF分类器具有更高的分类精度。

稀疏数据集协同过滤算法的进一步研究

罗琦,缪昕杰,魏倩

计算机科学. 2014, 41 (6): 264-268. doi:10.11896/j.issn.1002-137X.2014.06.052

摘要 ( 181 )

PDF(415KB) ( 398 )

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

协同过滤算法是电子商务和信息系统中非常重要的一门技术。其中用户相似度度量方法的科学性至关重要。为了获得更好的精度,采用用户间共同评分数目来动态调节原相似度,以更准确地反映用户间相似度的真实性。在此基础上,根据社会网络中FTL模型(follow the leader)的思想,对新用户或找不到最近邻的用户采用基于专家信任度的预测算法代替传统相似度来预测用户的评分,弥补了传统算法的不足。实验表明,算法提高了预测评分的准确性和推荐质量,并缓解了新用户的冷启动问题。

基于四元数视觉注意模型的肇事车辆匹配方法

徐航,臧笛,程成,张亚英

计算机科学. 2014, 41 (6): 269-274. doi:10.11896/j.issn.1002-137X.2014.06.053

摘要 ( 167 )

PDF(1286KB) ( 377 )

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

在交通监控录像中快速准确地检索匹配肇事车辆是智能交通系统的重要任务。与传统的匹配方法相比,视觉注意模型融合了多种底层特征,为肇事车辆匹配提供了新的思路。针对车辆匹配的特点,提出了一种新的颜色信息提取方法,并在四元数数学框架下与亮度、方向特征相结合,将标量显著性转换成四元数显著性,提出了一种四元数视觉注意模型。将四元数显著性作为新的特征用于肇事车辆匹配。实验表明,该匹配方法可以根据肇事车辆信息有效地缩小搜索范围,具有较好的准确性和鲁棒性。

基于二维局部鉴别高斯的特征提取方法

张智斌,朱俊勇,郑伟诗,王倩,赖剑煌

计算机科学. 2014, 41 (6): 275-277. doi:10.11896/j.issn.1002-137X.2014.06.054

摘要 ( 182 )

PDF(265KB) ( 427 )

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

特征提取是人脸识别的关键。特征提取方法一般需要预先把二维图像转化成一维图像向量。然而高维的图像向量会导致不能快速、精确地计算所需的协方差矩阵及其特征向量。针对该问题,提出了一种基于二维局部鉴别高斯的特征提取方法(2D-LDG)。该方法继承一维局部鉴别高斯降维方法的优点,其目标函数是留一交叉验证误差的光滑逼近,并且只考虑训练样本的局部分布,对训练样本的全局分布不做任何假设。同时,2D-LDG直接对二维图像做特征提取,不需要事先把图像转化为维数巨大的图像向量,能快速、精确地计算协方差矩阵及其特征向量。在ORL、YaleB人脸数据库上的实验结果表明,2D-LDG特征提取方法有良好的识别效果。

全景鸟瞰拼接图像的质量评价方法

常嘉义,秦瑞,李庆,陈大鹏

计算机科学. 2014, 41 (6): 278-281. doi:10.11896/j.issn.1002-137X.2014.06.055

摘要 ( 458 )

PDF(1247KB) ( 441 )

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

针对全景拼接图像尚无有效的全参考质量评价方法,无法有效地选择最佳拼接方案以及优化系统参数的问题,创新性地提出一种基于图像信息采样的质量评价方法 ,即通过统计俯视图像素在原始图像中的对应分布,对原始图像素的重采样率和均值方差等统计信息进行分析评估。首先介绍一种车载环视摄像头下4个不同角度的视频图像拼接的方法,然后提出像素采样率性能指标,最后通过仿真实验与实际测试,对比图像方差、熵值和平均梯度等指标,证明了提出的评价方法能够有效地评价拼接图像质量和优化摄像头安装参数。

一种二次阈值调整SIFT算法

卫保国,张海曦

计算机科学. 2014, 41 (6): 282-286. doi:10.11896/j.issn.1002-137X.2014.06.056

摘要 ( 211 )

PDF(878KB) ( 368 )

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

SIFT算法因其良好的特征提取和匹配效果得到了广泛的应用,但在光照不足和模糊条件下其效果不能令人满意,为此提出了一种基于全局信息和局部信息的自适应SIFT算法。利用图像的对比度信息得到初始阈值,使该阈值适应光照不足和模糊图像,根据周围特征点分布情况来对阈值进行二次调整以控制特征点数目及分布,并改进了误匹配剔除方法。实验结果表明,改进后的SIFT算法不仅能很好地适应低光照和模糊图像,而且可以调节特征点数目,降低簇效应。

基于膨胀的梯度结构相似度图像质量评价方法

桑庆兵,梁狄林,吴小俊,李朝锋

计算机科学. 2014, 41 (6): 287-290. doi:10.11896/j.issn.1002-137X.2014.06.057

摘要 ( 191 )

PDF(869KB) ( 384 )

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

传统的梯度结构相似度算法(GSSIM)简单地将各子块GSSIM的平均值作为整幅图像的质量评估值,忽略了人眼对图像不同失真区域的视觉灵敏度不同的特点。针对此问题,提出了一种基于膨胀和图像块分类的加权梯度结构相似度图像质量评价方法(WGSSIM)。该方法首先将失真图像划分为两个区域:边缘膨胀区域和平滑区域；然后将失真图像划分成8×8的图像块,根据失真区域将图像块区分为边缘膨胀块与平滑块两类；最后对不同类型图像块之间的GSSIM值赋予不同的权值,计算得到整幅图像的WGSSIM。实验表明,该方法在3个数据库上的评价结果稳定、合理,更加符合人眼视觉系统特性,评价结果与主观评价有很好的一致性。

基于SIFT特征匹配的CamShift运动目标跟踪算法

马正华,顾苏杭,戎海龙

计算机科学. 2014, 41 (6): 291-294. doi:10.11896/j.issn.1002-137X.2014.06.058

摘要 ( 341 )

PDF(652KB) ( 502 )

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

针对复杂背景下采用一般CamShift算法跟踪目标容易失败,提出将SIFT(Scale Invariant Feature Transform)特征点匹配融入到CamShift算法。该算法利用SIFT特征对尺度和方向无关特性实现连续图像序列的精准匹配,具有对尺度缩放、目标旋转以及亮度变化保持不变性的优点,不仅弥补了一般CamShift算法只以颜色为关键信息的不足,而且可将目标跟踪窗口形心和质心间的位移稳定在设定阈值内。最后通过对比性实验来验证该算法的有效性和稳定性。实验结果表明,该算法能够对复杂背景下的光照突变、缩放和旋转运动目标实现实时稳定跟踪。

约束优化进化的夜间图像时频复合加权提取

刘淑琴,彭进业

计算机科学. 2014, 41 (6): 295-298. doi:10.11896/j.issn.1002-137X.2014.06.059

摘要 ( 211 )

PDF(776KB) ( 392 )

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

研究了一种约束优化进化的夜间图像时频复合加权提取技术。对多帧夜间图像的时域与频域同时加权处理是一种深度检索夜间图像信息的先进技术。夜间图像质量低,传统的夜间图像信息检索技术采用单独的时域检索方法,无法对多帧夜间图像的频谱特性进行分析和信息检索。为此,提出一种约束优化进化的夜间图像时频复合加权提取技术。首先在频域和时域同时对多帧原始图像进行处理,提取多帧图像之间的相关信息；然后做加权处理,形成新的图像特征；在此基础上,通过约束优化进化算法对图像信息检索的结果不断进行循环优化,最终达到较好的效果。采用一组夜间图像进行了实验测试,结果显示,采用约束优化进化的夜间图像时频复合加权提取,多帧图像之间的时域和频域特征得到了很好的加权利用,最终实现了图像信息的深度提取。该方法在图像检索领域具有很好的应用价值。

方向场和频率场约束的结构光条纹图像增强算法

郑红波,徐玲玲,杜轶诚,秦绪佳,陈嵩辉

计算机科学. 2014, 41 (6): 299-303. doi:10.11896/j.issn.1002-137X.2014.06.060

摘要 ( 391 )

PDF(878KB) ( 506 )

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

条纹图像增强在指纹图像处理与识别、结构光三维重建中有重要应用。针对结构光三维重建的条纹图像处理,提出了一种基于图像方向场与频率场约束的条纹图像增强算法,设计了图像方向场与频率场的计算方法,构造了方向场与频率场的约束的Gabor滤波器。算法首先对条纹图像进行高斯滤波,去除图像亮度不均匀的影响；然后计算条纹图像的方向场与频率场；最后在图像方向场与频率场的约束下对图像进行Gabor滤波。实验结果表明,算法可有效消除图像光照不均匀的影响,较好地增强结构光图像的条纹信息。

Clifford 代数几何不变量3D医学图像配准的方法

华亮,丁立军,黄宇,冯浩,顾菊平

计算机科学. 2014, 41 (6): 304-308. doi:10.11896/j.issn.1002-137X.2014.06.061

摘要 ( 160 )

PDF(842KB) ( 458 )

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

就3D医学图像配准数据量大、计算复杂度高、配准精度低的问题,提出一种基于Clifford代数几何不变量的配准方法,以实现人头颅部3D医学图像配准。提出配准所需的Clifford代数几何不变量及其Clifford代数方程算式,并构造适合于该几何参考轴旋转的Clifford几何旋转算子,利用所求的最大、最小值对应的Clifford几何不变量建立Clifford旋转算子,对浮动影像数据实现几何变换,以达到配准的结果。配准实验中对两个世界著名的3D医学数据集进行了测试,结果表明:该方法计算简单,几何意义直观,配准精度高,执行效率高,并且通过轴线变换不易陷入配准过程的局部极值点。

基于类对可分和灰色决策的高光谱波段选择方法

张海涛,王鹤桥,孟祥羽,武文波

计算机科学. 2014, 41 (6): 309-313. doi:10.11896/j.issn.1002-137X.2014.06.062

摘要 ( 149 )

PDF(878KB) ( 420 )

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

随着研究者对高光谱图像光谱信息的质量要求逐渐提高,其自身特点给图像信息的进一步提取带来了阻碍。现有单一波段选择方法不能完全顾及“信息量、相关性、类别可分性” 3点准则,所得结果不可避免地受其他指标度量所约束。而利用灰色系统理论以小样本、贫信息、不确定性系统作为研究对象的属性,可以在将高光谱数据划分为子空间的基础上,进行灰色关联决策运算,从而克服了单指标度量的独立性与不相容性。因此,针对“确保类对可分”这日益高涨的需求,提出一种通过引入灰色关联决策对单一波段选择结果进行综合考量的波段选择方法。最后,通过实验与常见融合方法进行了对比。

基于小样本高维特征的人脸自动识别算法研究

李凌,李桂娟

计算机科学. 2014, 41 (6): 314-316. doi:10.11896/j.issn.1002-137X.2014.06.063

摘要 ( 191 )

PDF(275KB) ( 356 )

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

特征提取对人脸识别十分重要,传统典型相关分析算法(CCA)存在无法描述人脸图像的小样本、高维特征的缺陷。为了提高人脸识别精度,提出一种专门针对小样本、高维特征的人脸自动识别算法(SpCCA)。首先分别提取人脸全局特征和局部特征,并采用CCA对特征进行融合,消除特征间冗余信息,降低特征维数；然后通过划分子模型,避免人脸识别存在小样本、非线性问题,并以简单投票进行结果矫正,提高模型稳定性；最后在AR与Yale两个人脸数据集上对SpCCA算法性能进行测试。仿真结果表明,SpCCA解决了典型相关分析算法存在的不足,提高了人脸识别的精度。

一种基于图像匹配的地面交通标志实时识别方法

王棚飞,刘宏哲,袁家政,陈丽

计算机科学. 2014, 41 (6): 317-325. doi:10.11896/j.issn.1002-137X.2014.06.064

摘要 ( 256 )

PDF(1722KB) ( 540 )

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

地面交通标志检测识别是智能驾驶领域的一个研究方向,实时性、准确率是该研究的重点。图像匹配的方法是常用的模式识别方法。文中介绍了一种结合先验知识和图像匹配的地面交通标志检测识别方法。算法包括两部分:预处理和检测识别。预处理阶段包括图像压缩、感兴趣区域提取、形态学处理、中值滤波和逆透视等步骤,实现图像降噪和正畸,为检测识别做准备。检测识别阶段包括轮廓提取、面积过滤、图像匹配等步骤,目的是判断待测图像是否含有地面交通标志及其种类。实验证明,该算法实时性好、鲁棒性强、准确率高。