计算机科学

模糊测试技术研究综述

张雄,李舟军

计算机科学. 2016, 43 (5): 1-8. doi:10.11896/j.issn.1002-137X.2016.05.001

摘要 ( 1286 )

PDF(833KB) ( 7253 )

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

软件中的安全漏洞可能导致非常严重的后果,因此漏洞挖掘已成为网络与信息安全领域的重大课题和研究热点。目前常用的漏洞挖掘技术包括静态分析、动态分析、二进制比对、模糊测试等。随着软件的规模和复杂度不断增大,模糊测试具有其它漏洞挖掘技术无法比拟的优势。首先介绍和分析了各种漏洞挖掘技术的优点和缺点；然后分别详细描述了模糊测试的研究进展、模糊测试的过程、测试用例的生成技术；最后介绍了模糊测试在各个领域的应用,并对其发展方向进行了展望。

软差错影响下的电路可靠性分析

王真,江建慧

计算机科学. 2016, 43 (5): 9-12. doi:10.11896/j.issn.1002-137X.2016.05.002

摘要 ( 240 )

PDF(456KB) ( 787 )

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

随着大数据时代的到来,人们对微处理器可靠性的要求也越来越高,同时处理器芯片内电路密度的增大使其更易受到软差错的侵害,因此软差错影响下的电路可靠性问题显得尤为重要。针对这一问题,从系统结构级、RTL、门级及电路级4个抽象层次进行了全面的分析,并在每个抽象层次上依据方法属性做了分类介绍和比较。

广义Kautz有向图GK(3,n)的反馈数的界

徐喜荣,黄亚真,张思佳,董学智

计算机科学. 2016, 43 (5): 13-21. doi:10.11896/j.issn.1002-137X.2016.05.003

摘要 ( 222 )

PDF(399KB) ( 584 )

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

对于给定的图G的顶点集的子集F,如果删除F使得剩余子图是无圈子图,则称子集F为图G的反馈点集。研究了广义Kautz有向图GK(d,n)的反馈点集。令f(d,n)表示广义Kautz有向图GK(d,n)的所有反馈集合中顶点个数最少的集合的个数(即广义Kautz有向图GK(d,n)的反馈数),给出了GK(3,n)的反馈数的上界,即 f(3,n)≤n+5n8 － 3n4－ 4n7+3。

GPU平台上面向性能和功耗的分支优化

于齐,王博千,沈立,王志英,陈微

计算机科学. 2016, 43 (5): 22-26. doi:10.11896/j.issn.1002-137X.2016.05.004

摘要 ( 373 )

PDF(394KB) ( 1054 )

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

强大的计算能力使得GPGPU在通用计算领域得到了广泛的应用。然而,GPGPU的SIMT(Single Instruction Multiple Threads)工作方式,使其执行效率受到应用中不一致分支行为(Branch Divergence)的严重影响。虽然人们提出了线程交换方法来减小分支带来的性能损失,但这种方法往往会引入额外的访存操作,不仅在一定程度上减少了线程交换优化的性能收益,还增加了功耗。首先举例说明线程交换范围对程序性能和功耗的影响；然后提出了一种减少线程交换所引入的额外访存操作的方法。实验表明,对于Reduction程序,当交换范围为256时,在性能平均损失为4%的情况下功耗降低幅度最大为7%；而对于Bitonic程序,当交换范围为256和512时,在没有功耗开销的情况下,性能分别最大提升了6.4%和5.3%。

基于热例程的动态二进制翻译优化

董卫宇,刘金鑫,戚旭衍,何红旗,蒋烈辉

计算机科学. 2016, 43 (5): 27-33. doi:10.11896/j.issn.1002-137X.2016.05.005

摘要 ( 281 )

PDF(916KB) ( 645 )

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

依据对系统级程序行为特性的观察,提出了一种基于热例程的动态二进制翻译优化方法。该方法以频繁执行的例程作为优化单位,通过块内和块间优化算法消除动态二进制翻译引入的冗余。相比基于踪迹的优化方法,该方法具有优化单位发现开销更小、代码区域更大、无重复翻译等优点,更适用于系统虚拟机中操作系统代码的优化。在跨平台系统虚拟机监控器ARCH-BRIDGE上的测试表明,通过对内核代码实施该优化方法,SPEC CPUINT 2006程序的效率提升了3.5%~14.4%,相比基于踪迹的优化,性能最大提升了5.1%。

Intel64体系结构的数据预取机制及效果

董钰山,李春江

计算机科学. 2016, 43 (5): 34-41. doi:10.11896/j.issn.1002-137X.2016.05.006

摘要 ( 533 )

PDF(622KB) ( 2703 )

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

数据预取是为缓解微处理器与DRAM之间速度差异而出现的隐藏访存延迟的方法。当前Intel各系列处理器都采用多种预取机制来加速数据和代码向Cache的移动,从而提升程序的性能。通过对Intel64体系结构存储层次的分析,剖析了X86/X64体系的数据预取机制,包括硬件预取和软件预取,并且分析了编译器对软件预取机制的支持。最后测试了Intel64体系结构数据预取对科学计算程序中紧嵌套循环性能的影响,总结出了影响数据预取有效性的几个因素。此项工作对在Intel平台上进行循环数组预取优化有指导意义。

基于范畴论的本体描述方法

余珊珊,苏锦钿,易法令

计算机科学. 2016, 43 (5): 42-46. doi:10.11896/j.issn.1002-137X.2016.05.007

摘要 ( 244 )

PDF(455KB) ( 598 )

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

针对各种本体语言在描述本体过程中容易产生理解不一致的问题,利用范畴论的抽象性及图形化表示的优势,提出一种基于范畴论的本体描述方法,并给出了本体、本体映射和本体实例化的范畴论定义,其中本体被描述成范畴中的对象,本体间的映射被描述成范畴中对象间的同态射,本体实例化被描述成范畴间的函子。在此基础上,结合共极限和推出给出本体合并的描述及解释,并证明了本体合并的一些典型性质。

基于Owen值算法的社会网络关键节点问题研究

王学光

计算机科学. 2016, 43 (5): 47-50. doi:10.11896/j.issn.1002-137X.2016.05.008

摘要 ( 264 )

PDF(367KB) ( 585 )

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

社会网络关键节点发现问题有着许多重要的应用,如何找到网络中具有最大影响力的K个节点是一个NP问题。考虑到社会网络中普遍存在着社区结构,提出一种新的社会网络的关键节点发现算法,其在两个信息融合模型的基础上利用Owen值和Monte-Carlo方法得到每个节点的边际贡献,其中边际贡献最大的K个节点即为该问题的解。实验结果表明,该算法更适用于网络中存在社区结构的情形,在时间效率上相对于Greedy算法有几十倍的提高。

基于改进PSO_GA联合算法的电力线多用户通信资源分配

张培玲,张洪欣

计算机科学. 2016, 43 (5): 51-55. doi:10.11896/j.issn.1002-137X.2016.05.009

摘要 ( 189 )

PDF(410KB) ( 553 )

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

针对电力线信道在传输速率受限、子载波单用户独享和兼顾用户公平性的约束条件下,以余量自适应(MA)为准则,提出一种基于粒子群优化遗传(PSO_GA)联合算法的多用户自适应OFDM系统子载波和比特分配。在此联合算法中利用改进PSO算法中更新粒子速度和位置的思路来重构GA算法中的交叉、变异操作,可克服PSO算法早熟收敛、GA收敛速度慢等问题,能够提高联合算法对全局最优解的搜索能力及收敛速度。在典型电力线衰落信道下的实验结果表明,相比于已有的资源分配算法,基于所提联合算法的系统资源分配方案随着用户数增多,其收敛速度明显加快,且系统所需发射总功率最小,有效地提高了系统通信性能,从而充分证实了所提联合算法的有效性。

一种新的航空自组网混合路由算法

庞松超,罗长远,韩东东,庞涵滢

计算机科学. 2016, 43 (5): 56-61. doi:10.11896/j.issn.1002-137X.2016.05.010

摘要 ( 191 )

PDF(472KB) ( 633 )

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

路由算法是航空自组网研究的重点和难点。针对目前对航空自组网高动态路由研究较少的现状,考虑到飞机节点高动态但局部结构相对稳定的特点,通过将ADS-B系统整合到路由表建立过程中,设计了一种基于分簇和地理位置信息的混合路由算法CGCR。应用ADS-B消息中的节点位速和飞行意向数据预测节点运动趋势,从而选择最优下一跳节点。通过扩大下一跳选择区域策略来避免路由空洞的产生。仿真结果表明,CGCR具有良好的性能。

车载自组织网络中基于定向传播的自适应路由协议

蔡蓉,章国安,季彦呈

计算机科学. 2016, 43 (5): 62-66. doi:10.11896/j.issn.1002-137X.2016.05.011

摘要 ( 152 )

PDF(384KB) ( 527 )

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

数据分组在转发过程中需要在其转发范围内寻找一个中继节点进行转发。为了降低转发过程中寻找中继节点的复杂程度,减少从源节点到达目的节点的平均跳数,提出了一种车载自组织网络中基于定向传播的自适应路由协议(Adaptive Routing Protocol Based on Directional Transmission,ARPBDT)。该路由协议有两个关键参数:转发角度和平均每跳前进距离。首先为了缩小转发范围,设置一个始终朝着目的节点方向的转发角度,以减少转发范围内的节点数以及寻找中继节点的计算量；其次为了减少平均跳数,在转发范围内根据前进距离自适应地选择较优或次优的邻居节点作为中继节点进行转发。仿真结果表明,与OBDR相比,所提路由协议的平均跳数较少,平均每跳前进距离较大,能够使数据分组快速地到达目的节点。

基于分布式邻居发现机制的ZigBee网络能耗研究

黄恒杰,周涛,王高才

计算机科学. 2016, 43 (5): 67-72. doi:10.11896/j.issn.1002-137X.2016.05.012

摘要 ( 170 )

PDF(562KB) ( 606 )

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

ZigBee是一种基于IEEE 802.15.4标准的适用于短距离、低功耗和低数据传输率的无线网络技术。ZigBee网络的节点电池能量的有效利用能延长其网络生命周期。采用分布式邻居发现机制研究了ZigBee网络能耗。该机制使得ZigBee网络中的节点在其可访问的区域内及时发现邻居节点,通过分析和定义3种分布式邻居发现算法下ZigBee节点在整个发现过程中所需要的平均帧数,提出了ZigBee网络能耗模型,对ZigBee网络设备在3种分布式邻居发现算法下的能耗进行了详细分析并得出能耗表达式。在仿真实验中比较了ZigBee网络节点和邻居节点在不同算法下的工作循环模式和连续模式下设备的能耗,结果表明对于基于分布式邻居发现机制算法的ZigBee网络能耗,当帧时隙数较小时,选择争用树算法能获得较好的节能效果；当帧时隙数较大时,选择无反馈帧时隙算法或有反馈帧时隙算法则可减少节点能耗以延长ZigBee网络的生命周期。

基于WiFi的指纹匹配算法在室内定位中的应用研究

唐洋,白勇,马跃,蓝章礼

计算机科学. 2016, 43 (5): 73-75. doi:10.11896/j.issn.1002-137X.2016.05.013

摘要 ( 208 )

PDF(240KB) ( 910 )

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

快速、准确地建立目标测定的接收信息强度(RSS)与指纹数据库的匹配,是提高指纹定位算法性能的关键。提出一种基于指纹簇匹配算法,以缩小搜索范围,优化搜索路径,通过减少搜索数目及计算量,达到快速、准确完成匹配的目的。考虑不同簇形对定位性能的影响,采用4组实验对算法的快速性、准确性进行评估。实验结果展示在保证定位精度的同时,指纹簇算法较传统算法至少减少了60%的搜索数目,并验证得出蜂窝簇形的性能是最优的。

一种基于三维树模型的源代码安全缺陷分类方法

张 ,李舟军,董国伟,马殿富

计算机科学. 2016, 43 (5): 76-79. doi:10.11896/j.issn.1002-137X.2016.05.014

摘要 ( 179 )

PDF(394KB) ( 504 )

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

提出了一种基于三维树模型的源代码缺陷分类方法,该方法综合考虑了缺陷产生的原因、造成的结果及其表现形式3方面的信息。实例分析结果表明:使用基于三维树模型的缺陷分类法得到的缺陷类别比CWE和Fortify中的缺陷分类更为精确和详细。该工作不仅有助于建立一种比较完善的源代码缺陷分类体系,而且对于缺陷检测规则的细化也具有实际的指导意义。

软件漏洞静态检测模型及检测框架

王涛,韩兰胜,付才,邹德清,刘铭

计算机科学. 2016, 43 (5): 80-86. doi:10.11896/j.issn.1002-137X.2016.05.015

摘要 ( 345 )

PDF(663KB) ( 1070 )

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

软件漏洞静态分析是信息安全领域的重点研究方向,如何描述漏洞及判别漏洞是漏洞静态分析的核心问题。提出了一种用于描述和判别漏洞的漏洞静态检测模型。首先对软件漏洞的属性特征进行形式化定义,并对多种软件漏洞和其判定规则进行形式化描述；其次,针对传统的路径分析存在的状态空间爆炸问题,提出了一个新的程序中间表示——漏洞可执行路径集,以压缩程序状态空间。在该模型的基础上,设计了一个基于漏洞可执行路径集的软件漏洞静态检测框架,利用定义的漏洞语法规则求解漏洞可执行路径集上的漏洞相关节点集,利用漏洞判定规则对漏洞相关节点集进行判别得出漏洞报告。实验分析验证了该漏洞检测模型的正确性和可行性。

一种新的半监督入侵检测方法

梁辰,李成海

计算机科学. 2016, 43 (5): 87-90. doi:10.11896/j.issn.1002-137X.2016.05.016

摘要 ( 464 )

PDF(408KB) ( 553 )

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

针对基于监督的入侵检测算法在现实网络环境中通常面临的训练样本不足的问题,提出了一种基于纠错输出编码的半监督多类分类入侵检测方法。该方法综合cop-kmeans算法的半监督思想,挖掘未标记数据中的隐含关系,扩大有标记正常网络数据的数量。该算法首先采用SVDD计算入侵检测各类别的可分程度,从而得到由不同子类构成的二叉树；然后分别对二叉树的各层节点进行编码并形成层次输出编码,得到最终的分类器。实验表明,该算法对各种类型的攻击具有更高的检测率,在现实网络环境中具有较好的实用性。

基于数据挖掘的多轨迹特征检测技术

薛飞,单征,闫丽景,范超

计算机科学. 2016, 43 (5): 91-95. doi:10.11896/j.issn.1002-137X.2016.05.017

摘要 ( 237 )

PDF(406KB) ( 564 )

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

针对现有恶意程序行为特征检测存在的不足,采用多轨迹检测方法,用文件操作、网络访问、内存资源访问的行为特征构建出三维恶意行为特征库。在构造投影数据库的过程中,结合AC自动机优化频繁序列查询,舍去不满足最小长度的频繁序列,得到改进的数据挖掘算法——Prefixspan-x,并将其应用于动态提取恶意软件行为特征库和阈值匹配,以克服静态反汇编方式获取软件行为轨迹时软件加壳、混淆带来的检测困难。实验结果表明,基于数据挖掘的多轨迹特征检测技术具有较高的准确率和较低的漏报率。

一种基于组合事件行为触发的Android恶意行为检测方法

张国印,曲家兴,付小晶,何志昌

计算机科学. 2016, 43 (5): 96-99. doi:10.11896/j.issn.1002-137X.2016.05.018

摘要 ( 193 )

PDF(444KB) ( 683 )

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

当前Android恶意应用程序在传播环节缺乏有效的识别手段,对此提出了一种基于自动化测试技术和动态分析技术的Android恶意行为检测方法。通过自动化测试技术触发Android应用程序的行为,同时构建虚拟的沙箱监控这些行为。设计了一种组合事件行为触发模型——DroidRunner,提高了Android应用程序的代码覆盖率、恶意行为的触发率以及Android恶意应用的检测率。经过实际部署测试,该方法对未知恶意应用具有较高的检测率,能帮助用户发现和分析未知恶意应用。

基于SecLA的云服务商选择方法研究

朱华旻,吴礼发,康红凯

计算机科学. 2016, 43 (5): 100-107. doi:10.11896/j.issn.1002-137X.2016.05.019

摘要 ( 446 )

PDF(693KB) ( 575 )

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

云计算应用领域不断拓展,用户越来越关注云服务的安全性,现有云服务商选择方法主要考量性能和费用,缺乏有效的安全属性考评方法,为此提出了基于安全等级协议的云安全量化评比方法。基于云安全联盟的云控制矩阵及配套共识评估问卷,设计了云服务商安全指标体系及量化评分模型；对Web服务协议框架进行扩展,设计了云安全等级协议的模板框架；引入负提供参数来增强比较优势度法,实现了云安全等级的量化评比。实验检验了系列方法的可行性及有效性,与参数评估方法、简单线性加权方法等的对比表明,优先度排序更加合理,负提供参数对决策起到了良好的辅助效果。

基于SI-UNIWARD失真函数的改进隐写方案

司一帆,魏立线,张英男,刘佳

计算机科学. 2016, 43 (5): 108-112. doi:10.11896/j.issn.1002-137X.2016.05.020

摘要 ( 625 )

PDF(1125KB) ( 883 )

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

针对通用小波失真函数(UNIWARD)的失真代价的四舍五入误差为1/2时嵌入失真为零的问题,基于边信息的通用小波失真函数(SI-UNIWARD),提出了一种改进隐写方案。该方案首先对前载体的原始像素值进行四舍五入,然后重新定义了一组间距合理的四舍五入误差,产生了新的嵌入代价,重新使用了在SI-UNIWARD中禁用的00、40、04、44模式中的1/2离散余弦变换(DCT)系数,避免了检测性能的病态饱和,从而解决了零嵌入失真代价问题。实验表明,该方案与SI-UNIWARD相比,DCT系数的更改概率降低了3%,同时降低了空域中像素值间的数量差别和DCT系数的嵌入更改率,提升了检测误差性能,能够较好地利用边信息。

云数据在数据挖掘中的隐私保护

陶林波,沈建京,游庆祥,郭佳

计算机科学. 2016, 43 (5): 113-116. doi:10.11896/j.issn.1002-137X.2016.05.021

摘要 ( 195 )

PDF(344KB) ( 518 )

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

云计算环境下用户数据的集中存储为数据挖掘提供了便利条件,同时也为用户的隐私保护带来了挑战。为了解决云数据在数据挖掘条件下的隐私保护问题,提出了云计算环境下的隐私保护模型。该模型以公有云为基础,增加了一个分类预处理模块,设定了分类标准,详细讨论了分类后数据的处理方法,并讨论了该模型下数据的检索、还原方法以及运行环境保护、数据的云端销毁等环节。最后对模型的复杂性及安全性进行理论的对比分析,证明了该模型在数据挖掘条件下对云数据隐私保护的有效性。

一种基于二层节点和客观风险的电子商务交易信任模型

李道全,吴兴成,郭瑞敏

计算机科学. 2016, 43 (5): 117-121. doi:10.11896/j.issn.1002-137X.2016.05.022

摘要 ( 258 )

PDF(414KB) ( 529 )

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

为解决P2P环境下电子商务的安全交易问题,在深入研究电子商务相关信任模型的基础上,基于交易中可能存在的客观风险,提出了一种基于二层节点的综合信任度的计算模型。综合考虑了影响交易的交易金额、交易时间等多种因素,引入了可交易度的概念,并将其作为节点是否进行交易的决策依据。实验表明,该模型能够更准确地计算节点的信任值,可有效地提高交易的安全性。

虚拟分组撤销策略的云存储访问控制模型

谢丽霞,薄夫宽,赵彬彬

计算机科学. 2016, 43 (5): 122-126. doi:10.11896/j.issn.1002-137X.2016.05.023

摘要 ( 194 )

PDF(403KB) ( 527 )

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

为解决现有云存储访问控制模型用户权限撤销效率低、无法适应大规模用户的问题,在分析基于属性加密的密文策略的基础上提出了一个新的模型,给出了虚拟分组撤销策略,将用户映射到多个虚拟分组中,并重新构建了访问结构。用户权限撤销的范围被限制在一个虚拟分组内,对该虚拟组内的用户重新分发密钥即可实现用户权限撤销,而其它虚拟分组不需要任何变化,从而提高了用户权限撤销的效率。在Hadoop平台下进行了仿真实验,结果表明该模型具有较高的撤销效率。

有向天线的无线传感器网络病毒传播模型

胡金涛,宋玉蓉,苏晓萍

计算机科学. 2016, 43 (5): 127-131. doi:10.11896/j.issn.1002-137X.2016.05.024

摘要 ( 156 )

PDF(488KB) ( 551 )

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

采用定向感知天线模型建立基于有向天线的无线传感器网络中的病毒传播模型,通过智能监视节点广播的切换天线消息触发无线传感器网络节点使用有向天线,以研究无线传感器网络中的病毒传播。研究结果表明:使用有向天线不仅能够节约传感器节点能量,延长网络生命周期,还能够有效抑制病毒传播,减小无线传感器网络中病毒大规模爆发的风险,而且该模型适用于不同的病毒传播模型和不同结构的无线传感器网络。

基于压缩感知的视频双水印算法研究

周燕,曾凡智,赵慧民

计算机科学. 2016, 43 (5): 132-139. doi:10.11896/j.issn.1002-137X.2016.05.025

摘要 ( 205 )

PDF(1148KB) ( 496 )

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

针对数字视频的内容保护与帧内、帧间篡改检测的难题,采用压缩感知理论提取视频的内容特征作为水印,提出一种双水印的视频保护和篡改检测算法。首先,利用压缩感知过程提取I帧宏块的内容特征,生成半脆弱的内容认证水印；然后,对帧序号进行二值运算,生成完整性水印；最后,利用压缩感知信号重构OMP(Orthogonal Matching Pursuit)算法把生成的双水印嵌入到I帧和P帧相应宏块的DCT高频系数的压缩测量值中,以此提高视频水印的抗攻击能力,并实现对视频篡改的检测。仿真实验表明,所提算法对视频帧内篡改具有精确定位到子块的检测能力；同时对帧插入、帧删除、帧交换等类型的视频帧间篡改具有很强的检测能力。

云环境下基于协同推荐的信任评估与服务选择

游静,冯辉,孙玉强

计算机科学. 2016, 43 (5): 140-145. doi:10.11896/j.issn.1002-137X.2016.05.026

摘要 ( 215 )

PDF(473KB) ( 463 )

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

“模糊、自治”的云计算环境中,服务品类繁多、质量参差不齐,用户主体难以进行可信赖的服务选择。在用户交互经验的基础上,结合现实人际交易模式,提出了一种基于协同推荐的综合信任量化评估模型。模型引入了时间衰减、权重两类动态因子,设计了多元化混合协同推荐算法来实现用户之间的有效协作,帮助用户正确选择可信云服务。为了验证模型的可行性,设计出一个分布式的原型系统,对模型的用户满意度和服务选择质量进行仿真实验。仿真结果表明,该模型能够更快地提高平均服务满意度,更有效地抑制恶意服务,而且随着交互次数的增长,服务选择质量也会不断提高。

分布式容错计算描述语言及其应用研究

蔡媛媛,赵致琢

计算机科学. 2016, 43 (5): 146-149. doi:10.11896/j.issn.1002-137X.2016.05.027

摘要 ( 270 )

PDF(407KB) ( 540 )

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

在设计分布式容错系统的架构时,不仅要控制所有组件正常运行时的标准系统活动,还要控制某个组件失效时的情形。在传统的分布式容错系统设计中,这两者的模块实现往往具有紧密的耦合性,这为大型分布式容错系统的理解、设计、开发与维护增加了难度。为了解决这个问题,提出了一种新的方法,参考Hoare的通信顺序进程理论,使用维也纳定义语言元语言来定义这样一种描述语言:它不仅能够描述分布式计算的并发现象,还能够独立刻画系统的容错行为。这种解决方案体现了现代编程语言走向抽象化的必然趋势,也为分布式容错计算研究领域的发展提供了一种新的思路。

面向DO-333的襟缝翼控制单元安全性分析

陈光颖,黄志球,陈哲,阚双龙

计算机科学. 2016, 43 (5): 150-156. doi:10.11896/j.issn.1002-137X.2016.05.028

摘要 ( 406 )

PDF(649KB) ( 558 )

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

DO-333是对机载软件安全性标准DO-178C关于形式化方法的补充,为机载软件开发过程中形式化方法的使用提供指导。模型检验作为一种形式化方法,可以应用于对软件需求和设计阶段制品的严格验证。基于DO-333,使用模型检验对飞控系统中襟缝翼控制单元不同阶段的软件制品进行验证与分析,判断其是否满足DO-178C的相关验证目标并提供证据支持。首先,对控制单元中襟翼与缝翼必须互斥更新的高级需求进行规约和验证；其次,对单个机翼控制逻辑的低级需求进行规约和验证。通过以上验证与分析,分别为标准中关于高级和低级需求的验证目标提供证据。文中展示了模型检验在一个机载软件认证中的应用实例,该工作将为机载软件的安全性保障和适航认证提供技术支持。

基于分布函数的WCET快速估计

周国昌,郭宝龙,高翔,王健,闫允一

计算机科学. 2016, 43 (5): 157-161. doi:10.11896/j.issn.1002-137X.2016.05.029

摘要 ( 203 )

PDF(403KB) ( 568 )

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

在实时软件系统中,软件时间性能的分析与评估技术是一个重要的课题,然而随着CPU的结构越来越复杂,采用传统的模拟底层硬件执行的方法越来越困难。而基于分布函数的最坏执行时间(Worst Case Execution Time,WCET)估计方法从概率角度出发,可以绕过复杂的底层硬件建模,估计程序的最坏执行时间。首先对TI TMS320C6713 DSP汇编代码进行基本块的划分,以基本块为结点构建程序流图；然后用贝塔分布模拟每条指令的运行时间并采用改进的计划评审技术(Program Evaluation and Review Technique,PERT)确定贝塔分布相关参数,指令叠加后用正态分布模拟每个基本块的执行时间；最后利用基于路径的方法得到整个程序的最坏执行时间。实验结果表明此方法是可行的和合理的。

运行时验证中的减少监控开销方法研究

徐胜,叶俊民,陈曙,金聪,陈盼

计算机科学. 2016, 43 (5): 162-168. doi:10.11896/j.issn.1002-137X.2016.05.030

摘要 ( 170 )

PDF(580KB) ( 522 )

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

运行时验证中的一个重要研究内容就是减少监控开销,以达到运行时开销对系统影响最小化的目标。总结了近年来运行时验证中减少监控开销技术的研究发展,首先介绍了运行时开销控制的研究现状；然后详细介绍了运行时开销减少的具体方法；最后分析了运行时开销控制技术面临的主要挑战,并对该领域未来的研究方向进行了展望。

基于条件冲突分析的主动规则集汇流性判定方法

熊中敏,朱吉光,李长绩,袁红春

计算机科学. 2016, 43 (5): 169-173. doi:10.11896/j.issn.1002-137X.2016.05.031

摘要 ( 177 )

PDF(418KB) ( 491 )

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

主动规则使数据库具备自反应能力,在数据库、知识库和无线传感器网络等领域得到了广泛应用。汇流性分析是保持数据一致性的重要手段,但有效判定汇流性仍是一个难题。现有的方法基于规则可交换性进行判定,没有考虑规则之间是否存在条件冲突而导致它们不可能同时出现在同一个执行序列中；同时基于触发关系的集合分析没有考虑在规则触发序列中的先后时序性。为此,提出了规则的触发序列概念,分析了单个触发序列上的条件冲突和一对无序规则所在的两条触发序列之间的条件冲突,从而提出了更有效的汇流性先决条件及其判定定理,同时给出了新的判定算法的完整描述及其可终止性、正确性证明和复杂度分析。

障碍空间中基于Voronoi图的k最近邻查询

张丽平,经海东,李松,崔环宇

计算机科学. 2016, 43 (5): 174-178. doi:10.11896/j.issn.1002-137X.2016.05.032

摘要 ( 449 )

PDF(448KB) ( 686 )

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

为了提升障碍空间中k最近邻查询的效率,研究了障碍空间中基于Voronoi图的k最近邻查询方法,提出了在障碍空间基于Voronoi图的kNN-Obs算法。该算法采用了两个过程:过滤过程和精炼过程。过滤过程主要是利用Voronoi图的过滤功能,较大程度地减少了被查询点的个数。精炼过程主要根据障碍距离和邻接生成点对候选集内对象进行第二次筛选。进一步给出了处理新增加点的ADDkNN-Obs算法和处理删除点的DENkNN-Obs算法。实验表明该算法在处理障碍空间中的k最近邻问题时具有优势。

物联网中具有时间持续性特征的乱序事件查询处理技术研究

周春姐,戴鹏飞,李洪波,张振兴

计算机科学. 2016, 43 (5): 179-187. doi:10.11896/j.issn.1002-137X.2016.05.033

摘要 ( 167 )

PDF(732KB) ( 739 )

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

现实世界中的很多事件都是基于时间段的,具有明显的时间持续性特征。具有这种特征的事件之间的时态关系复杂多变,在发生乱序事件时,查询处理极具挑战性。物联网环境中对于时序事件的有序到达具有非常严苛的要求,但网络延迟和机器故障却导致事件乱序问题频发。基于建立的时态事件语义表示模型,提出了一种用于处理具有时间持续性特征的乱序事件的查询处理模式,并构建了一种混合解决方案,使物联网环境中乱序事件在到达后的一定时间阈值内达到正确有序。最后,通过实验验证了所提方法的有效性。

一种领域语料驱动的句子相关性计算方法研究

李峰,黄金柱,李舟军,杨伟铭

计算机科学. 2016, 43 (5): 188-192. doi:10.11896/j.issn.1002-137X.2016.05.034

摘要 ( 320 )

PDF(774KB) ( 543 )

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

句子相关性计算在自然语言处理的多个实践应用中均具有十分重要的作用,如舆情监测、信息检索、统计机器翻译等。在明确相似性与相关性之间的关系之后,设计了一种基于领域语料驱动的句子相关性计算方法,该方法基于同一领域的语料构建一个“句-段-篇”3层的领域语义空间,通过度量词语在各个层级间的共现概率、共现平均距离和句长等因子来测量词间的主题相关性。与基于字面特征、HowNet和同义词词林的方法进行了实验对比,结果表明该方法具有较好的实践应用价值。

基于聚类分析的业务流程模型抽象

孙善武,王楠,欧阳丹彤

计算机科学. 2016, 43 (5): 193-197. doi:10.11896/j.issn.1002-137X.2016.05.035

摘要 ( 330 )

PDF(470KB) ( 482 )

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

业务流程模型抽象的一个最突出的用例是对包含大量元素的业务流程细节模型进行“简要视图”的构造,以便对流程进行快速理解。很多学者对流程抽象方法进行了研究,提出根据行为的语义相似性对行为进行聚合,其中多数研究基于k-means聚类分析,即根据事先指定的抽象行为个数对行为进行聚类,在将行为聚合到某一个行为簇时,选择距离该行为簇的图心最近的行为。但实际上,抽象行为(子流程)个数是一个未知的量,哪些行为属于同一个子流程往往取决于建模者的经验和抽象习惯,而且在聚合时,若行为从业务意义角度或建模者的抽象习惯角度并不属于该子流程,则合并往往会产生抽象错误。因此,引入虚拟文档表示行为和流程模型,以消除固定属性作为表示行为的向量空间维度带来的约束。并且设计算法从大量包含人工设计子流程的真实的业务流程模型库中获取行为与所在子流程的距离阈值,利用该阈值指导生成可能获得的抽象行为个数k。以k为参数对流程模型进行行为聚类,在聚类过程中,进一步利用距离阈值对聚合行为进行限制。对真实的流程模型库进行实验分析,结果表明提出的行为聚类方法更加接近人工设计的抽象结果。

一种基于社区分类的社交网络用户推荐方法

赵勤,王成,王鹏伟

计算机科学. 2016, 43 (5): 198-203. doi:10.11896/j.issn.1002-137X.2016.05.036

摘要 ( 186 )

PDF(526KB) ( 627 )

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

社交网络上的用户推荐是目前计算机领域研究的热门问题。已有的社交网络推荐算法对于多主题的社交网络下的相关用户的推荐效果不佳。针对此问题,对社交网络的主题分类方法进行了研究与讨论,在此基础上提出了基于主题的用户社区分类方法,并根据分类信息给出一种新的社交网络用户推荐方法。经实验验证,该方法能有效地提高推荐的准确性并降低时间复杂度。

基于正交非负矩阵分解的K-means聚类算法研究

李孟杰,谢强,丁秋林

计算机科学. 2016, 43 (5): 204-208. doi:10.11896/j.issn.1002-137X.2016.05.037

摘要 ( 488 )

PDF(378KB) ( 1427 )

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

为提高K-means聚类算法在高维数据下的聚类效果,提出了一种基于正交非负矩阵分解的K-means聚类算法。该算法对原始数据进行非负矩阵分解,并分别通过改进的Gram-Schmidt正交化和Householder正交化加入了正交约束,以保证低维特征的非负性,增加数据原型矩阵的正交性,然后进行K-means聚类。实验结果表明,基于IGS-ONMF和H-ONMF的K-means聚类算法在处理高维数据上具有更好的聚类效果。

基于社交网络群智感知信息的非常规突发事件描述方法研究

陈海燕,徐峥

计算机科学. 2016, 43 (5): 209-213. doi:10.11896/j.issn.1002-137X.2016.05.038

摘要 ( 237 )

PDF(1232KB) ( 618 )

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

群智感知是以近年来兴起的物联网、大数据、云计算等多种技术为基础发展起来的。群智感知就是用城市环境中感知的大数据来解决城市本身所面临的挑战,通过对多源异构数据的整合、分析和挖掘来提取知识和价值,从而提高城市服务的现代化水平。非常规突发事件是一类前兆特征不充分、具有明显的复杂性和潜在次生衍生危害、破坏性严重、采用传统管理方式难以应对处置的罕见重大突发事件。由于构成群智感知网络的基本单元是无所不在的移动智能终端用户,这种新型的体系架构无论是在感知及认知的广度、深度还是在构建的成本与速度上,都是传统技术手段所无法比拟的。对社交网络信息进行语义感知、时空关联等以对非常规突发事件进行描述,并通过实例对该方法进行验证。非常规突发事件的语义信息包括关键词、模式、语句等。时空信息用来描述非常规突发事件的客观时间属性与空间属性。时间属性包括非常规突发事件的发生时间、结束时间,以及重要时间点。空间属性包括非常规突发事件的发生位置、影响位置,位置信息可以是路名建筑物名称,也可以具体到GIS信息。多媒体信息包括图像、视频、音频等。

改进的粗糙描述逻辑框架

闫之焕,雷银彬

计算机科学. 2016, 43 (5): 214-218. doi:10.11896/j.issn.1002-137X.2016.05.039

摘要 ( 178 )

PDF(384KB) ( 550 )

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

已有的粗糙描述逻辑(RDLs)都是基于经典的粗糙集理论,也就是在讨论可以处理不确定信息的粗糙描述逻辑前首先要定义出论域中元素间的某种等价关系。事实上,人们经常会遇到用形式概念表示的对象域,这种情况下一个自然的问题就是:如何处理可能出现的不确定性概念?把形式概念分析与粗糙集理论联系起来作为基础,建立了两种新的粗糙描述逻辑。把文献[14]中Y.Y.Yao等提出的方法应用于新的RDLs,其中的上(下)近似算子分别用格论算子和集合论算子来定义。这里的近似的定义虽然不同于传统的粗糙近似算子形式,但是有很好的实用性。基于这个新颖的上(下)近似的定义,把这两组近似算子引入到描述逻辑的结构中形成两种粗糙描述逻辑FlALC和FsALC。给出了相应的语法和语义,最后还给出了扩展的Tableaux算法,其可以用来解决相应的推理问题。

基于矩阵完整化的分块整合推荐算法

王毅,金忠

计算机科学. 2016, 43 (5): 219-222. doi:10.11896/j.issn.1002-137X.2016.05.040

摘要 ( 270 )

PDF(374KB) ( 504 )

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

传统的推荐系统往往是通过使用协同过滤或基于内容的方式来实现的,而文中将矩阵完整化的方法应用到推荐系统中。由于数据的稀疏性,直接使用矩阵完整化的方法会给推荐结果带来不小的误差。考虑到使用用户中存在一些活跃用户,挖掘出这些特殊用户,由他们组成的数据会降低稀疏性,而且对活跃用户提高推荐质量,会产生更大的商业价值。提出了一种分块整合推荐的方法,实验结果表明该方法能够提升推荐精度。

基于近邻传播的文本数据流聚类算法研究

李一鸣,倪丽萍,方清华,刘慧婷

计算机科学. 2016, 43 (5): 223-229. doi:10.11896/j.issn.1002-137X.2016.05.041

摘要 ( 200 )

PDF(512KB) ( 680 )

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

随着大数据时代的到来,网络上产生了大量非结构化文本数据流,这些文本数据流具有动态、高维、稀疏等特征。针对这些特点,首先将传统的AP算法及流式文本数据特征相结合,然后提出文本数据流聚类算法——OAP-s算法。该算法通过在AP算法上引入衰减因子,对聚类中心结果进行衰减,同时将当前时间窗口的聚类中心带入到下一时间窗口中进行聚类。针对OAP-s算法的不足,又提出了OWAP-s算法。该算法在OAP-s算法模型的基础上定义了加权相似度,并通过引入吸引度因子,使得历史聚类中心更具吸引性,得到更精确的聚类结果。同时,两种算法均采用滑动时间窗口模式,使算法既能体现数据流的时态特征,又能反映数据流的分布特征。实验结果表明,两种算法在聚类精确度、稳定性方面均高于OSKM算法,而且具有较好的伸缩性和可扩展性。

基于类心距离的模糊支持向量数据描述

王敏光,王喆

计算机科学. 2016, 43 (5): 230-233. doi:10.11896/j.issn.1002-137X.2016.05.042

摘要 ( 198 )

PDF(358KB) ( 587 )

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

针对传统的支持向量数据描述模型忽略了样本分布的重要性,提出了基于类心距离的模糊支持向量数据描述算法,并将其应用在UCI机器学习数据库的二分类和多分类数据集中。该算法利用样本到两类中心距离的比值赋予样本权重,增大贡献度大的样本的权重,降低贡献度小的样本的权重,突出样本之间的差异性,从而提高了算法的分类效果。实验表明,该算法具有比传统支持向量数据描述更好的学习能力和分类效果。

一种基于关键点的时间序列线性表示方法

陈帅飞,吕鑫,戚荣志,王龙宝,余霖

计算机科学. 2016, 43 (5): 234-237. doi:10.11896/j.issn.1002-137X.2016.05.043

摘要 ( 194 )

PDF(321KB) ( 708 )

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

时间序列数据具有规模大、维度高等特点,直接在原始序列上进行数据挖掘,其计算复杂度高且易受噪声影响,因此对原始时间序列进行预处理是必不可少的,而常用的线性表示方法大多存在对分段点的筛选准确度不高的问题。基于时间序列的变化特征,提出了一种基于时间序列关键点的线性表示方法。该方法综合考虑了时间跨度和振幅变化,能高效提取时间序列中的关键点,并防止过度除噪,实现简单。实验表明,该方法对不同领域的数据具有良好的普适性。

基于Spark的并行SVM算法研究

刘泽燊,潘志松

计算机科学. 2016, 43 (5): 238-242. doi:10.11896/j.issn.1002-137X.2016.05.044

摘要 ( 287 )

PDF(411KB) ( 800 )

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

随着数据规模的不断增加,支持向量机(SVM)的并行化设计成为数据挖掘领域的一个研究热点。针对SVM算法训练大规模数据时存在寻优速度慢、内存占用大等问题,提出了一种基于Spark平台的并行支持向量机算法(SP-SVM)。该方法通过调整层叠支持向量机(Cascade SVM)的合并策略和训练结构,并利用Spark分布式计算框架实现；其次,进一步分析并行操作算子的性能,优化算法并行化实现方案,有效克服了层叠模型训练效率低的缺点。实验结果表明,新的并行训练方法在损失较小精度的前提下,在一定程度上减少了训练时间,能够很好地提高模型的学习效率。

基于Kolmogorov复杂性的文本聚类算法改进

王有华,陈笑蓉

计算机科学. 2016, 43 (5): 243-246. doi:10.11896/j.issn.1002-137X.2016.05.045

摘要 ( 226 )

PDF(324KB) ( 593 )

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

基于Kolmogorov复杂性的聚类算法虽然具有普适性、参数无关性的优点,但是应用到文本内容语义信息聚类时往往准确率较低。针对这一问题,提出了一种基于特征扩展的文本聚类改进算法——DEF-KC算法。该算法通过引用百度百科中特定词条的信息,对预处理过的文本中的关键词进行特征扩展,从而提高特征词的主题贡献度,增强文本的结构辨识度,并通过选取特定压缩算法近似计算Kolmogorov复杂性得到文本相似度,最后使用谱聚类算法进行聚类。实验结果表明,与传统的基于Kolmogorov复杂性的文本聚类算法相比,使用该算法时聚类准确率和召回率均得到了较大提升。

与数据挖掘相关的整数矩阵的左右可逆性研究

陆成刚

计算机科学. 2016, 43 (5): 247-251. doi:10.11896/j.issn.1002-137X.2016.05.046

摘要 ( 165 )

PDF(428KB) ( 544 )

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

考虑了数据挖掘中基于整数矩阵的离散数据观测模型,并提出了观测矩阵的整数分解问题。该问题实质上是求解经典的线性丢番图系统,只是要求基矩阵是被分解矩阵的一个部分。提出了一个新的求解方法——左右逆法,并研究了与此相关的一类满秩非方整数矩阵的整数左右可逆性问题,提出了一些左右可逆的充分条件以及求整数左右逆的方法。该方法可以求出某些最小二乘法无法求出的整数逆,并与最小二乘法结合构成了一个整数分解的完整解决方案。

基于相关熵和距离方差的支持向量数据描述选择性集成

邢红杰,魏勇乐

计算机科学. 2016, 43 (5): 252-256. doi:10.11896/j.issn.1002-137X.2016.05.047

摘要 ( 211 )

PDF(446KB) ( 507 )

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

提出基于信息理论学习中相关熵和距离方差的支持向量数据描述选择性集成。利用相关熵代替均方误差来度量集成的紧致性,构造出更为紧致的分类边界；利用距离方差集成度量集成中基分类器间的差异性,以提高集成模型的差异性；在目标函数中增加基于₁范数的正则化项,实现选择性集成。此外,利用半二次优化技术对所提选择性集成模型进行求解。与单个支持向量数据描述、基于Bagging的支持向量数据描述集成以及基于AdaBoost的支持向量数据描述集成相比,所提方法取得了更优的分类性能。

一种使用shapelets的增量式时间序列分类

丁剑,王树英

计算机科学. 2016, 43 (5): 257-260. doi:10.11896/j.issn.1002-137X.2016.05.048

摘要 ( 303 )

PDF(403KB) ( 681 )

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

根据时间序列数据维度高、实值有序、数据间存在自相关性等特点,对时间序列分类过程进行研究。研究了当前比较流行的时间序列分类方法；从图像处理的角度出发,提出了一种将图片信息转化为时间序列数据的ITTS方法。shapelets作为最能够表示一条时间序列的子序列,随着时间的推移,这个特征序列可能会动态地发生变化。基于这样的思想,提出了一种基于动态发现shapelets的增量式时间序列分类算法IPST。该算法能够较好地动态发现当前最优的k个shapelets,从而提高时间序列分类的准确度。得到的shapelets集合还可以与多个传统的分类器结合,从而获得更佳的分类效果。

一种寻找最近子串的快速种子集求精算法

张懿璞,茹锋,王飚

计算机科学. 2016, 43 (5): 261-264. doi:10.11896/j.issn.1002-137X.2016.05.049

摘要 ( 222 )

PDF(295KB) ( 603 )

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

寻找序列中的最近子串对挖掘基因中特殊的功能位点和了解基因调控关系有着重要意义。提出了一种新的基于种子集求精的改进的期望最大化算法SCEM来对基因序列中的最近子串进行寻找。通过对输入序列聚类,将数据集分解为若干种子集,再使用改进的期望最大化算法对各种子集进行求精,SCEM最终可寻找到序列中的最近子串。真实数据和模拟数据实验表明,SCEM算法可以寻找到真实的最近子串,与随机投影等流行算法相比也能保证较高的性能和效率,并且可以有效解决较长的最近子串寻找问题。

一种高效的大规模网络k团挖掘算法

柴旭清,董永亮

计算机科学. 2016, 43 (5): 265-268. doi:10.11896/j.issn.1002-137X.2016.05.050

摘要 ( 187 )

PDF(324KB) ( 748 )

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

网络结构中的k团挖掘是各种基于网络的应用的基础问题之一。针对大规模网络k团挖掘效率低的问题,提出了一种高效的大规模网络k团挖掘算法。首先,将寻找最大密度的k团问题进一步转化为寻找超过给定密度值k团的问题。然后,以网络中的顶点和k－1团顶点为两类顶点构建二部图,并证明应用二部图可以在多项式时间内求解k团问题。在稀疏网络中,提出的算法的时间和空间复杂度分别为O(c²_k)和O(c_k)。实验表明,提出的算法与目前最优的算法相比能更准确地挖掘大规模网络中的k团,并且具有更高的运行效率。此外,提出的算法可应用于不完全网络中的k团挖掘。

基于梯度核特征及N-gram模型的商品图像句子标注

张红斌,姬东鸿,尹兰,任亚峰

计算机科学. 2016, 43 (5): 269-273. doi:10.11896/j.issn.1002-137X.2016.05.051

摘要 ( 233 )

PDF(503KB) ( 493 )

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

提出为商品图像标注句子,以便更准确地刻画图像内容。首先,执行图像特征学习,选出标注性能最优的梯度核特征完成图像分类和图像检索,该特征能客观描绘商品图像中形状和纹理这两类关键视觉特性。然后,基于语义相关度计算结果从训练图像的文本描述中摘取关键单词,并采用N-gram模型把单词组装为蕴涵丰富语义信息且满足句法模式兼容性的修饰性短语,基于句子模板和修饰性短语生成句子。最后,构建Boosting模型,从若干标注结果中选取BLEU-3评分最优的句子标注商品图像。结果表明,Boosting模型的标注性能优于各基线。

基于分数阶全变分正则化的超分辨率图像重建

刘亚男,杨晓梅,陈超楠

计算机科学. 2016, 43 (5): 274-278. doi:10.11896/j.issn.1002-137X.2016.05.052

摘要 ( 345 )

PDF(936KB) ( 849 )

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

从退化的低分辨率图像重建得到高分辨率图像的本质是一病态逆问题,针对该问题,通过添加正则项进行处理。在使用传统的全变分(TV)的基础上,添加了分数阶全变分(FOTV)作为另一正则项来约束解空间。分数阶全变分正则项的使用可以更好地重建图像的细节纹理信息,弥补了全变分算子在平滑区域易出现阶梯效应的缺陷。利用交替方向乘子(ADMM)算法将问题划分为子问题,将全变分和分数阶全变分算子作为循环矩阵,通过傅里叶变换将其对角化,降低了计算的复杂程度。实验结果表明,与已有的方法相比,所提方法有效地避免了阶梯效应的产生,较好地保持了细节信息,并且具有更好的峰值信噪比(PSNR)和结构相似度(SSIM)。

一种改进的降低扭曲误差的快速图像拼接算法

瞿中,林嗣鹏,鞠芳蓉

计算机科学. 2016, 43 (5): 279-282. doi:10.11896/j.issn.1002-137X.2016.05.053

摘要 ( 258 )

PDF(573KB) ( 718 )

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

通过提取SIFT特征进行图像拼接得到的全景图存在一定程度的扭曲误差,尤其当序列图像集合很大时,全景图扭曲现象更为严重。为提高全景图拼接质量,对Song Fuhua等人提出的图像拼接算法进行改进,首先改变参考图像的选取方式,提出图像序列中任意图像映射到与参考图像相同坐标系下的变换模型计算方法,并且在拼接过程中根据匹配特征点数目动态选取下次待拼接图像。与Song Fuhua等人提出的拼接算法相比,改进的图像拼接算法增加了图像重叠区域中SIFT特征点匹配对数,减小了参考图像SIFT特征检测区域。实验表明,提出的改进拼接算法提高了全景图拼接的时间效率,同时全景图扭曲现象也得到极大改善。

基于光流模值变化频率的群体骚乱行为检测方法

林杰,林拉

计算机科学. 2016, 43 (5): 283-287. doi:10.11896/j.issn.1002-137X.2016.05.054

摘要 ( 182 )

PDF(640KB) ( 560 )

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

群体骚乱行为突发性强、破坏性大,是视频监控关注的重点。研究群体骚乱行为的智能检测方法有助于提高视频监控的智能化水平。现有行为检测方法在检测群体骚乱行为时虚警率较高,实用性较差。因此,依据群体骚乱行为发生时光流模值变化大的特性,提出了一种基于光流模值变化频率的群体骚乱行为检测方法。该方法首先计算视频中每一帧图像上各像素点的光流；然后自适应求取反映像素点光流变化大小的二值映射图；接着分区块计算视频片段上的光流变化频率直方图,构建行为描述子；最后采用线性支持向量机进行特征训练与分类。实验表明,所提方法在检测群体骚乱行为时虚警率和漏警率低、识别率高,可广泛用于智能视频监控领域。

基于二次谱聚类和HMM-RF混合模型的车辆行为识别方法研究

范菁,阮体洪,吴佳敏,董天阳

计算机科学. 2016, 43 (5): 288-293. doi:10.11896/j.issn.1002-137X.2016.05.055

摘要 ( 317 )

PDF(484KB) ( 618 )

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

从高速交通监控视频中提取的车辆轨迹数据可以用于分析和识别车辆行为。由于从高速监控视频中提取的车辆轨迹中只有少量的变道、超车等类型轨迹,采用经典的最长公共子串(LCSS)相似度和谱聚类等算法无法有效地区分轨迹数据中所有类型的轨迹；此外,在车辆行为识别方面,常用的隐马尔科夫(HMM)轨迹模型忽略了负样本的影响,且仅用最大似然值进行分类,存在较高的误识别率。为了解决这些问题,分析和研究了高速监控视频中车辆轨迹数据的特点,提出了一种基于二次谱聚类和HMM-RF混合模型的车辆行为识别方法。该方法利用轨迹曲率来识别具有曲线轨迹特征的超车轨迹,利用倾角相似度和谱聚类算法来识别非曲线轨迹中的变道轨迹,并将得到的所有聚类簇用LCSS和谱聚类算法进行再聚类,从而有效地区分超车、变道以及直行轨迹等。在进行车辆行为识别时,该方法通过将不同HMM模型的多维概率输出作为随机森林RF模型的输入来识别多类型轨迹以替代最大似然值分类,提高了行为识别的正确率。为了验证方法的有效性,在不同数据集下进行实验,结果表明轨迹聚类的平均准确率为96%,而行为识别的平均准确率是89.3%,算法具有较高的准确率和鲁棒性。

基于曲波变换和余弦测度的人脸识别方法

李艳萍,姜颖,胡金明,李卫平

计算机科学. 2016, 43 (5): 294-297. doi:10.11896/j.issn.1002-137X.2016.05.056

摘要 ( 195 )

PDF(610KB) ( 592 )

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

人脸识别是一种常用的生物特征识别技术,广泛应用于门禁考勤、公安司法等领域。光照、人脸表情与姿态、遮挡等采集条件的变化对现有人脸识别方法影响较大,限制了其应用。提出了一种基于曲波变换和余弦测度的人脸识别方法,以提高人脸识别对采集条件的鲁棒性。首先,对待识别人脸图像进行曲波变换,依据曲波系数检测人脸区域的关键点；然后,提取各关键点在不同尺度和方向上的曲波特征,构建人脸特征描述子；最后,依据余弦测度、累加和运算和极值运算求取人脸的最优匹配结果。仿真实验表明,所提方法对光照、姿态、表情和遮挡等变化的鲁棒性强,且识别性能好。

相差显微图像下的癌细胞状态检测

张剑华,邹祎杰,高强,陈胜勇

计算机科学. 2016, 43 (5): 298-303. doi:10.11896/j.issn.1002-137X.2016.05.057

摘要 ( 479 )

PDF(1244KB) ( 622 )

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

针对相差显微镜下癌细胞的生命状态分析问题,提出了一种基于形态学的癌细胞状态检测与判别方法。首先使用改进的水平集算法分割出目标癌细胞的轮廓,然后使用OTSU方法在细胞内部进行二值化处理,得到亮、暗两种区域。基于细胞轮廓和细胞内部亮、暗区域,充分利用细胞灰度、形状及内部结构信息,提出了5种有效的特征来进行细胞分裂间期、分裂前期、分裂中期和分裂后期的检测与判别。大量实验表明,所提方法对膀胱癌T24相差显微(Phase-Microscopy)细胞视频中的癌细胞检测可以得到较好的结果,证明该方法可以检测并判别出各个独立细胞的位置及所处阶段,且对序列图像中的细胞状态检测有较强的鲁棒性。

基于EEMD的高速列车横向减振器故障的排列熵特征分析

吴志丹,秦娜,金炜东

计算机科学. 2016, 43 (5): 304-307. doi:10.11896/j.issn.1002-137X.2016.05.058

摘要 ( 199 )

PDF(317KB) ( 611 )

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

针对高速列车转向架横向减振器状态监测数据的特点,提出了一种聚合经验模式分解和排列熵相结合的故障特征分析方法,用于在不同时间尺度下对信号进行复杂性分析。首先利用EEMD对横向减振器不同个数失效的7种工况信号进行分解,再用排列熵量化IMF的复杂度,得到多维特征向量集,最后采用支持向量机对故障状态进行分类识别。实验结果表明本方法对多个横向减振器失效的工况识别率最高可达100%,验证了排列熵特征对于高速列车横向减振器故障信号分析的有效性。

基于局部抑制线性编码的图像快速识别方法

陈光喜,龚震霆,温佩芝,任夏荔

计算机科学. 2016, 43 (5): 308-312. doi:10.11896/j.issn.1002-137X.2016.05.059

摘要 ( 188 )

PDF(1000KB) ( 564 )

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

传统的图像识别方法如ScSPM、LLC都是在SIFT的基础上提取特征,忽略了人工特征的局限性,且单张图像识别耗时略长。考虑到这些不足,提出了一种基于局部抑制线性编码的图像快速识别方法。该方法首先直接利用局部抑制线性编码提取图像局部特征描述子；然后用线性空间金字塔匹配(LSPM)对特征描述子进行计算；最后将计算结果输入到线性支持向量机(LSVM)中进行训练和测试。在3个常用的图像数据集上的实验结果表明,该方法在类别不多的情况下具有很好的识别准确率,同时大大减少了单张图像识别耗时,从而验证了该方法在图像识别上的有效性。

基于哈希编码的无线多媒体传感网络森林火灾图像识别算法

常晓敏,赵涓涓,葛磊,强彦,史曜华

计算机科学. 2016, 43 (5): 313-317. doi:10.11896/j.issn.1002-137X.2016.05.060

摘要 ( 203 )

PDF(913KB) ( 501 )

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

针对无线多媒体传感网络在森林火灾监测应用中存在的问题,提出了基于图像哈希编码技术的森林火灾识别算法。首先,建立森林火灾图像的图像库,提取火焰图像的一系列静态和动态特征, 通过哈希函数对其特征向量进行计算得到对应的哈希码,从而得到图像库对应的哈希码库。其次,计算被识别图像的哈希码,并通过计算汉明距离与哈希码库进行匹配,得出与其最相近的图像,从而得出是否有火灾发生。实验结果表明,该算法的火焰识别准确率达到94.12%,高于SVM、BP神经网络和稀疏表示的火焰识别算法,且减少了网络中因图像传输而产生的能量消耗,提高了网络带宽的使用率。

基于区域协方差的图像超像素生成

张旭东,吕言言,缪永伟,杨东勇

计算机科学. 2016, 43 (5): 318-323. doi:10.11896/j.issn.1002-137X.2016.05.061

摘要 ( 320 )

PDF(1492KB) ( 721 )

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

图像分割是指将图像分割成一些互不重叠的区域,各区域内部具有相同或相近的某些特定属性,而不同区域之间的属性则相差明显。在图像处理的许多应用中,由于像素级处理的方法因图像数据量庞大、运算规模较大而需要耗费大量的运行时间,因此对图像进行超像素分割预处理是很有必要的一个步骤。基于区域协方差分析,提出了一种新的像素块相似度度量方法；基于像素块相似度度量提出了一种图像超像素生成的鲁棒方法。该方法首先利用K-means算法对输入图像进行初始聚类分割成若干小区域,对每个小区域利用区域协方差矩阵描述其特征信息；然后利用小区域块之间的区域协方差距离来构造相似度矩阵,结合Graph-based与K-means方法对区域块聚类生成图像超像素。与其它方法相比,该方法在生成较紧凑超像素的同时能更好地保持图像边缘特征信息,改善了图像欠分割错误,减少了不必要的过分割现象。将图像超像素生成方法应用于图像风格化中可以快速生成油画风格的风格化图像。