计算机科学

蔡莉,梁宇,朱扬勇,何婧

计算机科学. 2018, 45 (4): 1-10. doi:10.11896/j.issn.1002-137X.2018.04.001

摘要 ( 509 )

PDF(1627KB) ( 2351 )

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

在互联网时代,数据成为了新的生产要素,也成为了基础性资源和战略性资源,同时还是重要的生产力。大数据服务业在全国广泛开展,数据交易所纷纷成立。这时,数据质量就逐渐变成制约数据产业发展的关键问题。首先,按照时间顺序将数据质量的研究内容划分为3个阶段,全面梳理和总结每个阶段的代表性成果,包括理论、方法、技术、工具和框架；然后,分析了在物联网、云计算和大数据环境下,数据质量研究所面临的各种挑战和机遇；最后,从数据质量模型、大数据质量管理、大数据质量相关技术、众包、物联网以及数据开放6个方面对数据质量的研究热点和发展方向进行了展望。

图编辑距离概述

徐周波,张鵾,宁黎华,古天龙

计算机科学. 2018, 45 (4): 11-18. doi:10.11896/j.issn.1002-137X.2018.04.002

摘要 ( 531 )

PDF(1424KB) ( 2777 )

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

图编辑距离是图模式匹配技术中常用的方法之一。基于图编辑距离的匹配方法能够处理多种类型的图数据,因而受到了学术界的广泛关注。首先介绍了图编辑距离的相关概念；然后简述了基于启发式搜索技术的精确图编辑距离算法,重点分析了基于二分图匹配的近似图编辑距离算法；最后对现存的一些图编辑问题进行了总结,并对未来的发展趋势进行了展望。

移动低占空比无线传感网中数据收集的研究进展

梁俊斌,周翔,王田,李陶深

计算机科学. 2018, 45 (4): 19-24. doi:10.11896/j.issn.1002-137X.2018.04.003

摘要 ( 332 )

PDF(2120KB) ( 721 )

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

移动低占空比无线传感网(Mobile Low-duty-cycle Wireless Sensor Networks,MLDC-WSN)是一种新型的传感器网络,它能克服传统无线传感网络(WSN)中仅考虑静态网络、网络能耗大等问题。但是,MLDC-WSN的新特性给数据收集应用带来了新的挑战,例如:移动性会导致网络拓扑结构不断改变,造成网络连通性不稳定；节点的苏醒时间短,造成通信延迟大。针对MLDC-WSN中数据收集的研究现状进行了分析和对比,分别从节点移动性管理、节点睡眠调度、数据收集协议等3个方面进行了综述。此外,还总结了该领域中待解决的重要科学问题,并对未来的研究方向进行了展望。

工业控制系统的安全技术与应用研究综述

锁延锋,王少杰,秦宇,李秋香,丰大军,李京春

计算机科学. 2018, 45 (4): 25-33. doi:10.11896/j.issn.1002-137X.2018.04.004

摘要 ( 563 )

PDF(1727KB) ( 2749 )

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

为应对控制系统与互联网技术深度融合引发的安全新挑战,抵御震网病毒、火焰病毒、BlackEnergy等靶向攻击,针对工业控制系统漏洞挖掘、修复与控制等技术滞后,以及工业控制安全面临的“难发现、难监测、难防护”等问题,通过对工业控制系统的理论模型、关键技术、装备研制及测试评估进行研究,以漏洞挖掘与利用研究为主线,以理论与体系架构研究和安全技术测试验证平台的建设为基础,以动态监测防护和主动防御为目标,以测试样例集的攻防验证与典型示范为应用,提出了包含工业控制系统漏洞挖掘、深度检测、动态防护、主动防御等的整体安全技术解决方案,设计并构建了集漏洞挖掘、验证评估、动态防护、主动防御于一体的工业控制系统安全技术体系。

基于四叉树分割的地形LOD技术综述

王振武,吕小华,韩晓辉

计算机科学. 2018, 45 (4): 34-45. doi:10.11896/j.issn.1002-137X.2018.04.005

摘要 ( 657 )

PDF(1881KB) ( 2326 )

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

层次细节(Levels of Detail,LOD)技术是在大规模地形模型简化方面使用得最多的技术,它极大地提高了地形场景的漫游速度。在众多LOD模型中,应用最为广泛的是基于四叉树(Quadtree)分割的LOD算法。国内外学者对LOD模型做了大量的研究工作,文中对基于四叉树分割的LOD算法进行了系统的梳理与总结,对涉及到的核心算法进行了归类并详细分析了各自的优缺点,深入且全面地介绍了其研究现状。

同态加密在加密机器学习中的应用研究综述

崔建京,龙军,闵尔学,于洋,殷建平

计算机科学. 2018, 45 (4): 46-52. doi:10.11896/j.issn.1002-137X.2018.04.006

摘要 ( 996 )

PDF(1324KB) ( 4038 )

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

现有的机器学习算法不能对加密后的数据进行分析计算,而很多领域如医疗、金融等又要求数据保持机密性和安全性,这促进了加密机器学习的产生和发展。同态加密技术是解决这一问题的主要思路,它可以保证在不解密的情况下对密文进行计算,使得解密后的结果与对明文执行相同计算得到的结果相同。文中对同态加密在加密机器学习中的相关应用研究进行了综述,主要介绍了目前用同态加密实现加密机器学习的3种算法(加密神经网络、加密k-NN、加密决策树和完全随机森林),并从正确性、安全性、执行效率方面分析了方案设计,总结并对比了不同加密机器学习算法的构造思路,指出了同态加密用于加密机器学习的关键问题和进一步研究需要关注的内容,为同态加密和加密机器学习提供参考。

考虑时间因素的0-1背包调度问题

王正理,谢添,何琨,金燕

计算机科学. 2018, 45 (4): 53-59. doi:10.11896/j.issn.1002-137X.2018.04.007

摘要 ( 458 )

PDF(1378KB) ( 800 )

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

文中提出考虑时间因素的0-1背包调度问题这一具有NP难度的组合优化问题。给定n个物体(每个物体i的重量为w_i,连续加工时间为t_i),以及一个容量为S的背包,要求给出一个调度方案(物品的放入顺序和放入时间),使得任意时刻放入背包的物品总重量不超过背包容量,每个物体需放入背包连续加工时长t_i后才能取出,该问题是求使所有物体均加工完毕的时间尽可能短的调度方案。提出了3种求解算法:迭代动态规划算法、基于分枝限界的完备算法和遗传进化算法。迭代动态规划算法使用动态规划策略放置尽可能多的未加工物体到背包中,然后每次迭代取出加工完成的物品后再使用动态规划放入尽可能多的剩余未加工物品,直至所有物品被加工完成。基于分枝限界的完备算法通过定义上下界及剪枝操作,有效地降低了算法的计算复杂度。遗传进化算法将一个物品装填序列定义为个体,并定义了相应的适应度、选择、交叉与变异操作。在所设计的3组共计36个算例上的实验结果表明,迭代动态规划算法可以很快求出高质量的解,基于分枝限界的完备算法对小规模算例有很好的效果,遗传算法在处理几百个物体的算例时能在1500s内得到比动态规划算法更好的结果。

基于极大团的边缘云节点聚合算法

朱金彬,武继刚,隋秀峰

计算机科学. 2018, 45 (4): 60-65. doi:10.11896/j.issn.1002-137X.2018.04.008

摘要 ( 482 )

PDF(1501KB) ( 708 )

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

组合多个边缘云可以向用户提供更强大的云计算服务,在大量边缘云节点集合中选择适当的节点进行组合是一项具有挑战性的任务。该问题被建模成由云节点作为顶点、节点之间的链路作为边的资源拓扑图。云组合的构建过程等同于在该图中选择子图的过程,这是一个NP完全问题。子图的选择策略是决定云组合性能的重要因素,现有的minStar算法贪心地选择节点之间通信延迟最小的子图,将最优资源分配给当前用户,导致了局部最优和全局性能不良的问题。鉴于此,提出基于极大团的边缘云资源分配算法,提取图中的极大团并将其划分为若干互不重叠的规模较小的完全子图,以子图为单位构建资源块,以资源块为单位进行资源的分配。实验结果表明,与minStar算法相比,新算法将全局最大通信延迟降至原来的50%。

基于注意力长短时记忆网络的中文词性标注模型

司念文,王衡军,李伟,单义栋,谢鹏程

计算机科学. 2018, 45 (4): 66-70. doi:10.11896/j.issn.1002-137X.2018.04.009

摘要 ( 575 )

PDF(2453KB) ( 1422 )

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

针对传统的基于统计模型的词性标注存在人工特征依赖的问题,提出一种有效的基于注意力长短时记忆网络的中文词性标注模型。该模型以基本的分布式词向量作为单元输入,利用双向长短时记忆网络提取丰富的词语上下文特征表示。同时在网络中加入注意力隐层,利用注意力机制为不同时刻的隐状态分配概率权重,使隐层更加关注重要特征,从而优化和提升隐层向量的质量。在解码过程中引入状态转移概率矩阵,以进一步提升标注准确率。在《人民日报》和中文宾州树库CTB5语料上的实验结果表明,该模型能够有效地进行中文词性标注,其准确率高于条件随机场等传统词性标注方法,与当前较好的词性标注模型也十分接近。

可能性测度下的LTL模型检测并行化研究

雷丽晖,王静

计算机科学. 2018, 45 (4): 71-75. doi:10.11896/j.issn.1002-137X.2018.04.010

摘要 ( 661 )

PDF(2528KB) ( 911 )

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

分布式模型检测是一种缓解状态空间爆炸的有效途径,已有文献提出了定性的分布式模型验证算法,然而定量LTL验证算法并行化问题还未得到有效解决。对此,展开两个方面的工作:提出一种新的动态系统状态空间划分方法;在定性LTL分布式验证算法的基础上给出了定量模型检测并行化验证算法。首先,将系统模型转化为可能的Kripke结构并选取一个并发分量,依据状态之间的关系完成系统状态的分割,使得关系紧密的状态尽可能分布在同一个计算节点上；其次,调整划分结果以使得计算负载平衡；然后,将划分结果与其他并发分量的状态进行叉乘,以完成系统状态空间的划分；最后,将待检测性质用自动机表示,在两者的乘积上,利用扩展的基于嵌套DFS的分布式验证算法完成系统的定量验证。

用于求解混合车辆路径问题的混合进化算法

孙启,金燕,何琨,徐凌轩

计算机科学. 2018, 45 (4): 76-82. doi:10.11896/j.issn.1002-137X.2018.04.011

摘要 ( 540 )

PDF(2094KB) ( 1124 )

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

文中研究了具有NP难度的混合车辆路径问题(Mixed Capacitated General Routing Problem,MCGRP),其是在基本车辆路径问题(Vehicle Routing Problem,VRP)的基础上通过添加限载容量约束及弧上的用户需求而衍生的。给定一列车辆数不限的车队,使车辆从站点出发向用户提供服务,服务完用户需求后仍返回站点；规定每辆车的总载重不能超过其载重量,且每个需求只能被一辆车服务且仅服务一次。MCGRP旨在求解每辆车的服务路线,使得在满足以上约束条件的情况下所有车辆的旅行消耗之和最小。混合车辆路径问题具有较高的理论价值和实际应用价值,针对该问题提出了一种高效的混合进化算法。该算法采用基于5种邻域算符的变邻域禁忌搜索来提高解的质量,并通过一种基于路径的交叉算符来继承解的优异性,从而有效地加速算法的收敛。在一组共计23个经典算例上的实验结果表明,该混合进化算法在求解混合车辆路径问题时是非常高效的。

带权混合支配问题的近似算法研究

张佳男,肖鸣宇

计算机科学. 2018, 45 (4): 83-88. doi:10.11896/j.issn.1002-137X.2018.04.012

摘要 ( 667 )

PDF(1313KB) ( 1002 )

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

图G=(V,E)上的混合支配集D是由图G中的顶点和边组成的集合,因此对于图G中的任意一条边或一个顶点,若其不在D中,则其必须与D中某条边或某个顶点相邻。混合支配问题是在一个图中找到一个基数最小的混合支配集。混合支配问题是图顶点支配问题和边支配问题的混合,在实际生活中有着许多应用,最近在算法中也备受关注。混合支配问题在一般图上是NP完全的。带权混合支配问题则是混合支配问题的一个自然推广,其将图中的点和边以不同权重进行区分。令图中所有点的权重均为w_v,所有边的权重均为w_e,带权混合支配问题则要求寻找一个混合支配集使得其点和边的权重之和达到最小。尽管针对混合支配问题已存在一个简单2倍近似算法,但是对带权混合支配问题的近似算法的研究进展却非常缓慢。在点的权重不大于边的权重的情况下,文中给出了带权混合支配问题的一个3倍近似算法。

城市道路建设时序决策的鲁棒优化

伍建辉,黄中祥,李武,吴健辉,彭鑫,张生

计算机科学. 2018, 45 (4): 89-93. doi:10.11896/j.issn.1002-137X.2018.04.013

摘要 ( 541 )

PDF(2423KB) ( 897 )

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

为提高城市道路建设时序决策的鲁棒性,提出了城市道路建设时序决策优化的双层规划模型。模型假定出行需求在一定范围内扰动,上层规划是在有限资金的约束下寻求各建设阶段的系统总出行时间与系统总出行时间对出行需求的灵敏度之间的综合最小值,下层规划为各建设阶段的随机用户均衡配流。文中推导出了系统总出行时间对出行需求灵敏度的计算式,并给出了模型的求解算法。最后以一个测试路网为例,对基于系统总出行时间、基于灵敏度、基于系统总出行时间与灵敏度综合出行时间的决策优化模型进行了计算分析,结果显示3种决策优化模型均可寻求到各自目标最优的城市道路建设时序,但在需求不确定的情景下基于灵敏度、基于系统总出行时间与灵敏度综合出行时间的决策优化结果更具鲁棒性。

针对移动云计算任务迁移的快速高效调度算法

史雯隽,武继刚,罗裕春

计算机科学. 2018, 45 (4): 94-99. doi:10.11896/j.issn.1002-137X.2018.04.014

摘要 ( 671 )

PDF(3604KB) ( 790 )

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

计算量较大的应用程序由于需要大量的能耗,因此在电池容量有限的移动设备上运行时十分受限。云计算迁移技术是保证此类应用程序在资源有限的设备上运行的主流方法。针对无线网络中应用程序任务图的调度和迁移问题,提出了一种快速高效的启发式算法。该算法将能够迁移到云端的任务都安排在云端完成这种策略作为初始解,通过逐次计算可迁移任务在移动端运行的能耗节省量,依次将节省量最大的任务迁移到移动端,并依据任务间的通讯时间及时更新各个任务的能耗节省量。为了寻找全局最优解,构造了适用于此问题的禁忌搜索算法,给出了相应的编码方法、禁忌表、邻域解以及算法终止准则。构造的禁忌搜索算法以提出的启发式解为初始解进行全局搜索,并实现对启发解的进一步优化。通过实验将所提方法与无迁移、随机迁移、饱和迁移3类算法进行对比,结果表明提出的启发式算法能够快速有效地给出能耗更小的解。例如,在宽度为10的任务图上,当深度为8时,无迁移、随机迁移与饱和迁移的能耗分别为5461、3357和2271能量单位,而给出的启发解对应的能耗仅为2111。在此基础上禁忌搜索算法又将其能耗降低到1942, 这进一步说明了提出的启发式算法能够产生高质量的近似解。

基于L1-范数距离的最小二乘对支持向量机

周燕萍,业巧林

计算机科学. 2018, 45 (4): 100-105. doi:10.11896/j.issn.1002-137X.2018.04.015

摘要 ( 672 )

PDF(3032KB) ( 802 )

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

最小二乘对支持向量机(LSTSVM)是一种有效的分类技术。然而,该方法需计算点到平面的平方L2-范数距离,从而易受野值或噪声的影响。为了缓解此问题,提出了一种有效的鲁棒 LSTSVM方法,即基于L1-范数距离的LSTSVM(LSTSVML1D)。该方法由于使用L1范数作为距离度量,因此不易受到野值或噪声数据的影响。此外,设计了一种有效的迭代算法,旨在求解目标问题,并从理论上证明了其收敛性。在人工数据集和UCI数据集上验证了LSTSVML1D 的有效性。

基于多生长时期模板匹配的玉米螟识别方法

刘博艺,唐湘滟,程杰仁

计算机科学. 2018, 45 (4): 106-111. doi:10.11896/j.issn.1002-137X.2018.04.016

摘要 ( 477 )

PDF(10579KB) ( 925 )

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

玉米螟是玉米种植中的主要虫害之一。为了解决人工识别的劳动强度大,且识别不够准确、及时的问题,文中提出了一种在自然场景下基于多生长时期模板匹配的不同生长时期亚洲玉米螟的识别方法。该方法首先对获取到的图像进行数学形态学预处理；其次利用直方图反向映射法和多模板图像得到总的概率图像；然后利用约束空间的大津法对二值图像进行轮廓提取,并根据周长和面积特征进行初步筛选；最后结合基准轮廓,利用Hu矩等特征选出符合亚洲玉米螟特征的轮廓,进而得出识别结果并以三角形标记。实验和理论分析证明,在复杂自然场景图像中,该方法不仅时效性强,而且具有很好的识别准确度,能够有效降低不同生长时期的玉米螟颜色变化带来的影响。

基于有向无环图的互联网域内节能路由算法

耿海军,施新刚,王之梁,尹霞,尹少平

计算机科学. 2018, 45 (4): 112-116. doi:10.11896/j.issn.1002-137X.2018.04.017

摘要 ( 529 )

PDF(2152KB) ( 646 )

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

互联网在快速发展的过程中面临新的挑战,其中网络能耗问题尤为突出。学术界提出了大量用于解决网络能耗问题的方案,然而这些方案都考虑了网络中的实时流量数据,计算复杂度较高,不利于实际部署。对此,提出一种基于有向无环图的互联网域内节能路由算法(Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph,EEBDAG),该方法利用有向无环图来解决因链路关闭造成的路由环路和网络性能下降等问题, 仅须考虑网络拓扑结构,不需要考虑网络中的实时流量数据。实验结果表明,EEBDAG不仅具有较低的节能比率,而且具有较低的链路利用率,为ISP解决互联网节能问题提供了一种全新的方案。

基于节点修复的网络化指挥信息系统弹性分析模型

崔琼,李建华,王宏,南明莉

计算机科学. 2018, 45 (4): 117-121. doi:10.11896/j.issn.1002-137X.2018.04.018

摘要 ( 408 )

PDF(12885KB) ( 962 )

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

提出一种基于节点修复的网络化指挥信息系统弹性分析模型。首先,确立了网络化指挥信息系统弹性的概念,构建了指挥信息系统网络模型,对网络级联失效和恢复过程进行了描述；然后,在建立负载分配模型和节点修复模型的基础上,根据网络化指挥信息系统弹性过程构建了弹性度量模型；最后,进行仿真分析,计算不同模型参数下的网络弹性。结果表明,恢复概率和平均修复时间等参数对网络弹性的影响显著,为提高网络化指挥信息系统的弹性提供了参考。

抑制CMT中乱序程度的路径优化方案

王振朝,侯欢欢,连蕊

计算机科学. 2018, 45 (4): 122-125. doi:10.11896/j.issn.1002-137X.2018.04.019

摘要 ( 423 )

PDF(1869KB) ( 635 )

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

为减轻并行多路径传输(CMT)中接收端的乱序程度,文中提出了一种新的路径优化方案。该方案以MPTCP协议为基础,在三维笛卡尔坐标系下建立基于路径往返时延、丢包率和带宽的路径评价模型,将二分法与改进的基于密度的聚类分析方法相融合,根据所需路径数在坐标系下选择出一组带宽大、丢包率小且时延差也小的路径作为活跃路径。仿真结果显示,本方案与基于权重的路径选择方案相比降低了接收端的乱序长度与重传数据包个数,从而可以提高吞吐量与数据包传输速率。

车载自组织网络中基于车辆密度的双簇头路由协议

杨羽琦,章国安,金喜龙

计算机科学. 2018, 45 (4): 126-130. doi:10.11896/j.issn.1002-137X.2018.04.020

摘要 ( 359 )

PDF(2912KB) ( 724 )

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

为了降低城市环境下对转发范围内的单个车辆节点运动的感知敏感度,减少源节点到目的节点的平均跳数和传输时延,提出一种车载自组织网络中基于车辆密度的双簇头路由协议(Dual-Cluster-Head Routing Protocol Based on Vehicle Density,DCHPBD)。该路由协议根据车辆密度设置簇的大小,在同一路段簇内左右车道分别选出一个簇头,根据最大化生存期原则选择用于转发数据分组的主簇头,另外一个作为备选簇头。仿真结果表明,与CBDRP和EG-RAODV协议相比,所提出的协议簇头生存期较长,平均跳数和平均时延较小,通信性能更好。

基于稳定匹配的容器部署策略的优化

施超,谢在鹏,柳晗,吕鑫

计算机科学. 2018, 45 (4): 131-136. doi:10.11896/j.issn.1002-137X.2018.04.021

摘要 ( 384 )

PDF(1426KB) ( 1055 )

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

Docker的发展使得操作系统级虚拟化的容器渐渐兴起,容器即服务(CaaS)也越来越普及。随着容器技术的发展,容器将成为云环境中的主要部署模型,但针对容器的整合部署技术还未得到广泛的研究。容器化云环境中的容器数量众多,如何将众多的容器部署到合适的虚拟机以降低数据中心能耗,成为了一个亟待解决的问题。因此,文中创新性地将机器学习中的几种相似度计算方法作为稳定匹配算法的偏好规则,同时将已经拟分配过容器的虚拟机继续加入偏好列表,从而将一对一的稳定婚姻匹配算法改进为多对一的稳定匹配,解决了将容器整合到虚拟机上的初始化部署问题。仿真实验结果表明 , 采用优化的稳定匹配算法来初始化将部署容器时,不仅SLA违规较低,而且比FirstFit,MostFull以及Random算法分别约节能12.8%,34.6%和30.87%,其中使用欧氏距离作为稳定匹配算法偏好规则的节能效果最好。

一种基于改进遗传算法的雾计算任务调度策略

韩奎奎,谢在鹏,吕鑫

计算机科学. 2018, 45 (4): 137-142. doi:10.11896/j.issn.1002-137X.2018.04.022

摘要 ( 790 )

PDF(1616KB) ( 927 )

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

任务的调度与分配一直以来都是云计算技术发展中的关键问题。然而,随着物联网连接设备的爆炸式增长,云计算已不能满足一些任务的调度需求,如健康检测、应急响应等都需要较低的延迟,雾计算应运而生。雾计算将云的服务扩展到网络边缘。雾计算架构下的任务调度与分配目前还是一个较新的研究热点。文中介绍了一种改进的遗传算法(IGA),该算法将适应度判断引入到亲代变异操作中,克服了基本遗传算法(SGA)在变异操作中的盲目性。在雾计算架构下采用该算法调度任务时考虑了服务等级目标(SLO)中响应时间的约束(FOG-SLO-IGA)。实验结果表明,FOG-SLO-IGA调度用户任务时在时延、SLO违规率以及服务提供商的花费上均低于云计算架构下采用IGA的调度(CLOUD-IGA)；同时,在雾端调度任务时,IGA算法在执行速度上要快于传统SGA算法和轮询调度算法(RRSA)。

软件定义网络中基于网络切片和ILP模型的路由方案

庞博,金乾坤,合尼古力·吾买尔,齐兴斌

计算机科学. 2018, 45 (4): 143-147. doi:10.11896/j.issn.1002-137X.2018.04.023

摘要 ( 432 )

PDF(2241KB) ( 721 )

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

针对软件定义网络(SDN)中数据层的路由优化问题,提出一种基于网络切片和整数线性规划(ILP) 多约束优化的路由方案。首先,根据多租户业务的链路需求,基于Kruskal算法对数据层中的链路资源进行网络切片,尽可能形成相互隔离的租户子网络。然后,在考虑链路约束和租户业务的服务质量(QoS)约束下, 以最小化传输延迟为目标, 构建一个ILP整数线性规划(ILP)路由优化模型,并获得最佳的路由方案。仿真结果表明,所获得的路由方案具有较少的共享链路,有效降低了链路拥塞和传输延迟。

一种基于局部性原理的远程验证机制

夏庆勋,庄毅

计算机科学. 2018, 45 (4): 148-151. doi:10.11896/j.issn.1002-137X.2018.04.024

摘要 ( 543 )

PDF(2374KB) ( 842 )

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

为了提高嵌入式平台配置远程证明方案的效率,在基于Merkle哈希树存储结构的基础上,结合程序的局部性原理,考虑平台下程序验证的时间特性,对存储程序模块完整性度量值的数据结构进行了改进,提出了一种基于局部性原理的远程验证机制。实验分析表明,新的机制可以减少构造存储度量日志的时间消耗,缩短应用程序实时认证路径的长度,提高平台配置远程证明的验证效率。

MORUS-1280-128算法的区分分析

郑秀林,宋海燕,付伊鹏

计算机科学. 2018, 45 (4): 152-156. doi:10.11896/j.issn.1002-137X.2018.04.025

摘要 ( 614 )

PDF(1275KB) ( 707 )

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

MORUS算法是被提交到CAESAR竞赛中的一种认证加密算法,已经进入第三轮安全评估。对算法进行区分分析对于其安全性评估具有很重要的意义。以MORUS-1280-128为例,在nonce重用的情况下,对算法进行区分分析能够区分出密文的绝大部分比特,并通过寻找内部状态碰撞对算法进行标签伪造攻击。该研究结果对MORUS算法的安全性分析有很重要的意义。

基于伪梯度提升决策树的内网防御算法

厉柏伸,李领治,孙涌,朱艳琴

计算机科学. 2018, 45 (4): 157-162. doi:10.11896/j.issn.1002-137X.2018.04.026

摘要 ( 704 )

PDF(1423KB) ( 675 )

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

结合TF-IDF算法思想,提出了特征频率、森林频率以及伪梯度提升决策树,解决了梯度提升决策树随着迭代次数的增加,错误数据被边缘化的问题。在伪梯度提升决策树中,所有决策树分别在原始数据集的Bootstrapping后的数据集上产生,无须针对每次迭代来对数据集采样。在分布式集群上进行内网防御的实验,结果表明在一定规模的训练集上,伪梯度提升决策树具有更好的预测准确度。

PDiOS:iOS应用程序中私有API的调用检测

吴姝,周安民,左政

计算机科学. 2018, 45 (4): 163-168. doi:10.11896/j.issn.1002-137X.2018.04.027

摘要 ( 423 )

PDF(1515KB) ( 1179 )

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

苹果公司对App Store上的每一款应用程序都进行了审核,包括是否存在访问用户敏感信息的私有API调用,但是仍有恶意应用通过了该项审查。针对iOS应用程序中私有API的调用问题,提出了一种动、静态相结合的检测技术PDiOS。通过反向分片和常量传播的静态分析方式来处理大部分API调用,基于强制执行的动态迭代分析来处理剩余API。静态分析包含了对二进制文件的全面分析以及对资源文件中隐式调用的处理,动态分析主要依赖于二进制动态分析框架进行迭代分析。最后通过对比公开头文件中的API来确定私有API的调用。在对官方商店的1012款应用程序的检测中,确认有82款应用程序存在共128个不同的私有API调用。在对企业证书签名的32款应用程序的检测中,确认有26款使用了私有API调用。

计算机取证过程中基于约束的数据质量问题研究

刘琴

计算机科学. 2018, 45 (4): 169-172. doi:10.11896/j.issn.1002-137X.2018.04.028

摘要 ( 376 )

PDF(1251KB) ( 763 )

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

为了发现线索,提高数据质量,提出了一种应用于计算机取证领域的基于约束的数据修复算法。首先,利用等价类,针对不同的约束对数据进行初始化；然后,对初始化阶段发现的有问题的数据进行修正,修正值依据约束类型的不同而取不同的值；最后, 根据函数依赖集合和其他约束集,对经过修复的单元格集合重新生成问题单元格集合,如果依然存在问题单元格集合,则继续修复,直到不存在问题单元格为止。实验数据证明了所提方法的有效性和高效性。

基于多残差马尔科夫模型的图像拼接检测

罗霄阳,霍宏涛,王梦思,陈亚飞

计算机科学. 2018, 45 (4): 173-177. doi:10.11896/j.issn.1002-137X.2018.04.029

摘要 ( 362 )

PDF(2791KB) ( 737 )

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

针对传统马尔科夫特征计算差值矩阵的方式单一、拼接检测鲁棒性不强的问题,提出彩色多残差马尔科夫特征拼接检测模型。该模型引入隐写检测模型(Rich Models for Steganalysis,SRM)中的多种残差类型来改进传统马尔科夫特征,从R,G,B 3个通道分别提取10种不同类型的马尔科夫特征,训练30个独立的SVM分类器,最后通过决策判断进行分类预测。该方法在哥伦比亚大学彩色拼接检测库上达到了95.40%的准确率。

针对基于感知器模型的混沌图像加密算法的选择明文攻击

朱淑芹,王文宏,李俊青

计算机科学. 2018, 45 (4): 178-181. doi:10.11896/j.issn.1002-137X.2018.04.030

摘要 ( 397 )

PDF(3939KB) ( 660 )

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

对一种基于感知器模型的混沌图像加密算法进行了安全性分析,发现该算法的本质就是根据等效密钥流来改变明文图像像素值的比特位,从而得到密文图像。而等效密钥流与明文图像和对应的密文图像没有任何关系,因此运用选择明文攻击的方法破解出了算法中的等效密钥流,解密出了目标明文图像；同时指出了原算法存在的另外两个安全缺陷；最后对原算法进行了改进,弥补了其缺陷。理论分析和实验结果均证实了所提出的选择明文攻击策略的可行性以及改进算法的有效性。

用户偏好约束的空间关键词范围查询处理方法

郭帅,刘亮,秦小麟

计算机科学. 2018, 45 (4): 182-189. doi:10.11896/j.issn.1002-137X.2018.04.031

摘要 ( 386 )

PDF(2955KB) ( 642 )

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

随着基于地理位置的个性化服务的广泛应用,用户偏好约束的空间关键词范围查询成为了研究热点。现有面向空间关键词范围查询的索引没有考虑用户偏好属性,导致剪枝性能和查询效率较低。为了解决该问题,提出了一种支持用户偏好属性、空间位置、关键词协同剪枝的混合索引BRPQ；并在此基础上,提出了高效的用户偏好约束的空间关键词范围查询处理算法。实验结果表明,相比现有索引,BRPQ索引的构建时间平均减少了13%,查询效率平均提升了20%。

AUTOSAR可运行实体-任务自动映射方法研究

冉正,罗蕾,晏华,李允

计算机科学. 2018, 45 (4): 190-195. doi:10.11896/j.issn.1002-137X.2018.04.032

摘要 ( 737 )

PDF(2287KB) ( 857 )

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

下一代汽车电子标准AUTOSAR定义汽车应用程序设计过程包括系统级设计和ECU级设计。系统级设计以软件构件为单位来设计应用,其中软件构件包含一组可运行实体。ECU级设计主要将可运行实体代码组织为嵌入式实时操作系统任务。因此,在将分配到ECU的软件构件集转换为实时系统任务集的过程中,需要有经验的嵌入式开发工程师进行可运行实体-任务的映射配置,以保证系统的实时性。鉴于可运行实体-任务的映射配置工作具有配置需求量大、复杂度高等特点,文中设计了一种可运行实体-任务自动映射方法。该方法综合考虑了可运行实体的触发关系、周期需求、数据共享等因素,对提高汽车软件开发效率具有非常重要的实用价值。最后,将该方法应用于AUTOSAR标准的汽车电子巡航控制系统实例中。实验结果显示,所提方法在抖动时间、阻塞时间、调度频繁度和数据通信量4个方面都具有良好的表现。

面向DO-178C的襟缝翼控制系统需求的形式化描述

战芸娇,魏欧,胡军

计算机科学. 2018, 45 (4): 196-202. doi:10.11896/j.issn.1002-137X.2018.04.033

摘要 ( 479 )

PDF(1366KB) ( 656 )

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

DO-178C是对机载软件适航认证标准DO-178B的改进和补充,用于对民用飞机机载系统和设备软件质量控制提供指导。SCR(Software Cost Reduction)方法作为一种形式化方法,基于四变量模型,可以对复杂和大型的嵌入式系统进行需求描述。文中基于DO-178C,使用SCR方法对原飞机系统中的襟缝翼控制系统的需求文档进行形式化的需求描述,针对襟缝翼控制系统中的襟翼电机转速控制模块进行详细的案例分析,判断其是否满足DO-178C的相关验证指标。通过分析和验证,提出了SCR方法中的一些应用技巧。该工作可为SCR方法在机载软件系统中的应用提供依据。

基于Session的Web应用软件EFSM模型构建方法研究

郭俊霞,郭仁飞,许南山,赵瑞莲

计算机科学. 2018, 45 (4): 203-207. doi:10.11896/j.issn.1002-137X.2018.04.034

摘要 ( 443 )

PDF(2242KB) ( 815 )

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

在Web应用软件模型表示研究领域中,研究对象主要为不含Ajax技术的应用程序。少数针对Ajax(Asynchronous JavaScript and XML)的模型构建采用传统的FSM模型表示方法,并不能描述客户端消息触发后的参数传递问题；在FSM模型的基础上引入UML分层模型的表示方法因需要人工干预,不利于测试用例的自动生成。针对上述问题,借鉴EFSM模型这一重要的软件描述模型,从用户的Session数据出发,通过日志数据分析用户的行为,并记录客户端的操作事件。通过对用户行为和客户端操作事件进行匹配,生成完整的用户会话,从而建立EFSM模型。实验结果表明,该EFSM模型能够有效地表示Web应用程序的状态以及状态的变化情况,并可以有效地为测试用例自动生成服务。

基于CBOW-LDA主题模型的Stack Overflow编程网站热点主题发现研究

张景,朱国宾

计算机科学. 2018, 45 (4): 208-214. doi:10.11896/j.issn.1002-137X.2018.04.035

摘要 ( 421 )

PDF(2059KB) ( 776 )

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

Stack Overflow是一个热门的国外编程问答网站,通过对该网站编程提问帖的问题文本进行文本语义挖掘,能获析用户关注的编程热点。由于研究对象所代表的短文本信息具有高维性及分布不均的特点,易导致主题获取不明晰。文中提出一种基于LDA(Latent Dirichlet Allocation)主题模型的CBOW-LDA建模方法,该方法对目标语料进行相似词聚类后再完成主题建模,能有效降低文本输入维度,使主题分布更明确。采集Stack Overflow网站上2010－2015年的问题帖数据集POST,并对其进行实验,同等主题数下采用文本建模中衡量模型性能的评价指标困惑度(Perplexity)来度量算法在不同数据集容量维度下的性能。结果表明,与现有的基于词频权重的词量化主题建模TF-LDA方法相比,CBOW-LDA方法的困惑度更低,在实验语料下的困惑度降低约4.87%,证明了所提算法的性能更好。采用CBOW-LDA方法对Stack Overflow进行热点挖掘,同时使用TF-LDA方法进行对比实验,建立手工标注的标准评测集对两种方法获取的热门主题和热搜词汇进行查全率、查准率及F1值的判定,结果证实CBOW-LDA表现更佳,其热点挖掘效果较好。由实验结果可知,Java为该编程网站提问帖中最热门的主题,而C和Javascript则为该网站用户提问中被提及得最频繁的词汇。

基于用户聚类和移动上下文的矩阵分解推荐算法研究

文俊浩,孙光辉,李顺

计算机科学. 2018, 45 (4): 215-219. doi:10.11896/j.issn.1002-137X.2018.04.036

摘要 ( 398 )

PDF(3996KB) ( 784 )

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

随着移动互联网技术的快速发展,越来越多的用户通过移动设备获取移动信息和服务,导致信息过载问题日益凸出。针对目前上下文感知推荐算法中存在的数据稀疏性差、上下文信息融入不够、用户相似性度量被忽略等问题,提出一种基于用户聚类和移动上下文的矩阵分解推荐算法。该算法通过利用k-means对用户聚类找到偏好相似的用户簇,求出每簇中并对用户所处上下文之间的相似度并对其进行排序,由此找出与目标用户偏好和上下文均相似的用户集合,借助该集合改进传统矩阵分解模型损失函数,并以此为基准进行评分预测和推荐。仿真实验结果表明,所提算法可有效提高预测评分的准确度。

基于改进粒子群优化的移动界面模式聚类算法

贾伟,华庆一,张敏军,陈锐,姬翔,王博

计算机科学. 2018, 45 (4): 220-226. doi:10.11896/j.issn.1002-137X.2018.04.037

摘要 ( 506 )

PDF(1437KB) ( 516 )

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

聚类是一种非常有效的信息分析方法。针对现有基于粒子群优化的模糊C均值(Fuzzy C-means,FCM)聚类算法的聚类效果不佳的问题,提出一种基于改进粒子群优化的模糊C均值聚类算法,并将该聚类算法应用到移动界面模式的聚类中。首先,利用直觉模糊熵的几何解释和约束构造合理的直觉模糊熵；然后,在粒子群优化中使用直觉模糊熵判断种群的多样性程度,并引入混沌反向学习策略来提高全局搜索能力；最后,为了增强聚类算法的非线性处理能力,在聚类算法中加入高斯核函数,并将该聚类算法应用到移动界面模式的聚类中。移动界面模式聚类的实验表明,与现有聚类算法相比,文中所提聚类算法具有更好的聚类效果。

基于深度极限学习机的卫星云图云量计算

翁理国,孔维斌,夏旻,仇学飞

计算机科学. 2018, 45 (4): 227-232. doi:10.11896/j.issn.1002-137X.2018.04.038

摘要 ( 329 )

PDF(6142KB) ( 1261 )

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

卫星云图云量计算是卫星气象应用的基础,现阶段对其的研究未能充分利用卫星云图的特征,导致云检测及云量计算的效果不好。针对该问题,利用多层神经网络进行卫星云图的特征提取,并通过大量实验寻找到最优的深度学习的网络结构。基于度极限学习机对卫星云图的云进行检测和分类,再利用“空间相关法”计算云图中的总云量。实验结果表明,基于传统极限学习机的深度极限学习机能够充分提取云图的特征,在进行云分类时能够较清晰地区分厚云和薄云间的界限。相比于传统阈值法、极限学习机模型以及卷积神经网络,深度极限学习机的云识别率以及云量计算准确率更高,且所提方法比卷积神经网络的效率更高。

基于改进的离散PSO算法的FJSP的研究

丁舒阳,黎冰,侍洪波

计算机科学. 2018, 45 (4): 233-239. doi:10.11896/j.issn.1002-137X.2018.04.039

摘要 ( 503 )

PDF(2392KB) ( 887 )

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

柔性作业车间调度问题(Flexible Job-shop Scheduling Problem,FJSP)是经典作业车间调度问题的一个扩展,前者更接近于实际生产。以最小化最大完工时间为目标,提出了一种改进的离散粒子群优化算法。传统粒子群优化算法一般适用于优化连续模型问题,FJSP作为复杂度比较高的组合优化问题,是一种典型的离散模型。提出的算法采用机器负荷平衡机制初始化粒子种群,在粒子的更新过程中引入了3个操作算子来更新粒子的工序排序部分和机器分配部分,这3个算子分别为基于工序排序或机器分配的变异、与个体最优位置之间进行工序先后顺序保留的交叉(POX)操作、与全局最优位置进行随机点保存的交叉(RPX)操作。先后执行以上3个算子以完成粒子的一次更新。这种操作能够使种群较快地收敛于最优解。对标准测试案例进行实验的结果表明,所提算法对解决FJSP具有有效性,并且能够快速地搜索到近似最优解；与其他同类算法相比,所提算法在求解效果和收敛速度上均具有优越性。

求解多车型校车路径问题的混合集合划分的GRASP算法

侯彦娥,孔云峰,党兰学

计算机科学. 2018, 45 (4): 240-246. doi:10.11896/j.issn.1002-137X.2018.04.040

摘要 ( 340 )

PDF(1323KB) ( 808 )

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

针对不同规划场景下具有不同优化目标的多车型校车路径问题(HSBRP),提出一种混合集合划分(SP)的贪婪随机自适应(Greedy Randomized Adaptive Search Procedure,GRASP)算法。根据GRASP算法寻优过程中产生的路径信息构建SP模型,然后使用CPLEX精确优化器对SP模型进行求解。为了适应不同类型的HSBRP问题,改进GRASP的初始解构造函数得到一个可行解,并将其对应的路径放入路径池；在局部搜索过程中应用多种邻域结构和可变邻域下降(VND)来提升解的质量,同时在路径池中记录在搜索过程中得到提升的路径和在每次迭代中得到局部最好解的路径信息。使用基准测试案例进行测试,实验结果表明在GRASP算法中,混合SP能够有效地提高算法的求解性能和稳定性,并且该算法能适应不同优化目标下车型混合和车辆数限制两类HSBRP的求解；与现有算法的比较结果再次验证了所提算法的有效性。

基于标签聚类与项目主题的协同过滤推荐算法

李昊阳,符云清

计算机科学. 2018, 45 (4): 247-251. doi:10.11896/j.issn.1002-137X.2018.04.041

摘要 ( 221 )

PDF(1434KB) ( 782 )

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

传统基于项目的协同过滤算法在计算项目相似度时仅依靠评分数据,未考虑项目的自身特征。社会化标注的出现使得标签能在一定程度上反映项目特征,但标签具有语义模糊的特点,因此直接将标签纳入协同过滤算法存在一定问题。为解决上述问题,提出一种改进的基于项目的协同过滤推荐算法。该算法对标签进行聚类并生成主题标签簇,根据项目标注情况计算项目与主题间的相关度并生成项目-主题相关度矩阵,同时将其与项目-评分矩阵相结合来计算项目间的相似度,采用协同过滤完成对目标项目的评分预测,以实现个性化推荐。在Movielens数据集上的实验结果表明,该算法能够解决标签的语义模糊问题并提升推荐质量。

基于密度约束和间隙约束的对比模式挖掘

魏芹双,武优西,刘靖宇,朱怀忠

计算机科学. 2018, 45 (4): 252-256. doi:10.11896/j.issn.1002-137X.2018.04.042

摘要 ( 245 )

PDF(1483KB) ( 582 )

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

对比模式挖掘是序列模式挖掘的一个重要分支,带有密度约束的对比模式有助于生物学家发现生物序列中的特殊因子的分布情况。为此,文中提出了MPDG (Mining distinguishing sequence Patterns based on Density and Gap constraint) 算法,该算法应用网树结构挖掘满足密度约束和间隙约束的对比模式,在仅需扫描一遍序列库的情况下,该算法可计算当前模式的所有超模式的支持度,从而提高挖掘效率。最后,在真实蛋白质数据集上进行实验,实验结果验证了MPDG算法的有效性。

决策形式背景属性约简的关系

秦克云,林洪

计算机科学. 2018, 45 (4): 257-259. doi:10.11896/j.issn.1002-137X.2018.04.043

摘要 ( 383 )

PDF(1993KB) ( 609 )

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

形式背景的属性约简是形式概念分析的重要研究方向。针对决策形式背景,已有多种属性约简标准及属性约简方法。文中研究了相关属性约简方法之间的关系,从形式概念的角度给出了规则协调集的等价描述方法；证明了强协调决策形式背景中的规则协调集为协调集,粒协调决策形式背景中的规则协调集为粒协调集。

基于随机需求与产能限制的供应链协同优化研究

童泽平,李涛,李立杰,任亮

计算机科学. 2018, 45 (4): 260-265. doi:10.11896/j.issn.1002-137X.2018.04.044

摘要 ( 351 )

PDF(2384KB) ( 726 )

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

供应链所面临的需求随机性以及供应方的产能限制对供应链协同路径优化有着显著影响。已有研究并未考虑二者综合作用下供应链各参与主体的行为选择机理及协同优化的实现路径。对此,建立了一个包含多制造商与单一销售商的二级供应链模型,运用非合作博弈的方法求得稳定均衡解,并探讨了实现供应链协同优化的有效路径,从而有助于为供应链参与主体提供决策支持。

基于双层规划的网络化防空作战编队结构优化

李慧,周林,辛文波

计算机科学. 2018, 45 (4): 266-272. doi:10.11896/j.issn.1002-137X.2018.04.045

摘要 ( 313 )

PDF(5117KB) ( 960 )

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

科学、合理的网络化防空作战编队结构是确保编队自身安全,提高作战任务可靠性和有效性的重要保证。针对网络化防空作战编队结构优化问题,首先,定义了编队防空结构的相关概念,分析了编队防空作战的一般过程；其次,基于双层规划理论,分别以掩护节点与核心节点距离最大、编队抗饱和攻击能力最强为上下层目标,综合考虑探测角度覆盖、火力拦截时间、导弹二次捕捉等因素,建立了作战编队防空结构双层优化模型；然后,引入层次粒子群算法,对模型进行求解,并给出了具体运算步骤；最后,以水面舰艇编队防空结构优化为例,求解最佳编队防空结构,计算最大抗饱和攻击能力。通过与典型的纵队、弧形编队的对比,验证了模型与方法的合理性与可行性。

基于单个卷积神经网络的面部多特征点定位

朱虹,李千目,李德强

计算机科学. 2018, 45 (4): 273-277. doi:10.11896/j.issn.1002-137X.2018.04.046

摘要 ( 516 )

PDF(5495KB) ( 721 )

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

深度学习在面部特征点定位领域取得了比较显著的效果。然而,由于姿态、光照、表情和遮挡等因素引起的面部图像的复杂多样性,数目较多的面部特征点定位仍然是一个具有挑战性的问题。现有的用于面部特征点定位的深度学习方法是基于级联网络或基于任务约束的深度卷积网络,其不仅复杂,且训练非常困难。为了解决这些问题,提出了一种新的基于单个卷积神经网络的面部多特征点定位方法。与级联网络不同,该网络包含了3组堆叠层,每组由两个卷积层和最大池化层组成。这种网络结构可以提取更多的全局高级特征,能更精确地表达面部特征点。大量的实验表明,所提方法在姿态、光照、表情和遮挡等变化复杂的条件下优于现有的方法。

基于小波变换和倒谱分析的腭裂高鼻音等级自动识别

赵利博,刘奇,付方玲,何凌

计算机科学. 2018, 45 (4): 278-284. doi:10.11896/j.issn.1002-137X.2018.04.047

摘要 ( 394 )

PDF(1900KB) ( 725 )

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

为实现对腭裂高鼻音等级的自动识别,通过对语音信号小波处理和特征提取方法的综合研究,提出基于小波分解系数倒谱特征的腭裂高鼻音等级自动识别算法。目前,研究人员对腭裂语音的研究多基于MFCC、Teager能量、香农能量等特征,识别正确率偏低,且计算量过大。文中对4种等级腭裂高鼻音的1789个元音\a\语音数据提取小波分解系数倒谱特征参数,使用KNN分类器对4种不同等级的高鼻音进行自动识别,将识别结果与MFCC、LPCC、基音周期、共振峰和短时能量共5种经典声学特征的识别结果作比较,同时使用SVM分类器对不同等级的腭裂高鼻音进行自动识别,并与KNN分类器进行对比。实验结果表明,基于小波分解系数倒谱特征的识别结果优于经典声学特征,且KNN分类器的识别结果优于SVM分类器。小波分解系数倒谱特征在KNN中的识别率最高达到91.67%,在SVM中达到87.60%,经典声学特征在KNN分类器中的识别率为21.69%~84.54%,在SVM中的识别率为30.61%~78.24%。

基于噪声空间结构嵌入和高维梯度方向嵌入的鲁棒人脸识别方法

李小薪,李晶晶,贺霖,刘志勇

计算机科学. 2018, 45 (4): 285-290. doi:10.11896/j.issn.1002-137X.2018.04.048

摘要 ( 401 )

PDF(7384KB) ( 625 )

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

基于核范数的矩阵回归方法(Nuclear norm based Matrix Regression,NMR)对人脸图像中因遮挡和光照变化等噪声引发的误差具有很强的鲁棒性。分析了NMR的鲁棒性的基本原理:首先,误差的核范数度量的是误差在其主方向上的能量,而主方向上的能量通常都去除了常规噪声的干扰；其次,误差的核范数度量嵌入了噪声的空间结构信息,而噪声的空间结构对于表示并排除噪声的影响至关重要。然而,仅仅考虑噪声的空间结构并不能有效消除噪声的影响。将具有噪声抑制能力的高维梯度方向(High-dimensional Gradient Orientation,HGO)特征嵌入NMR,提出了一种基于高维梯度方向特征的NMR方法(High-dimensional Gradient Orientations-based NMR,HGO-NMR)极大地提升了NMR的识别性能。其重要意义在于指出噪声空间结构信息和噪声抑制机制对于面向现实的鲁棒人脸识别系统同等重要,单方面强调其中任何一种机制都将导致不稳定的识别性能。

基于视频的矿井中人体运动区域检测

李珊,饶文碧

计算机科学. 2018, 45 (4): 291-295. doi:10.11896/j.issn.1002-137X.2018.04.049

摘要 ( 299 )

PDF(10131KB) ( 607 )

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

将人体运动区域检测技术应用到矿井视频中可以检测矿井下矿工的运动情况,进一步可以智能检测矿工的异常行为,根据反馈的检测结果实现实时报警和联动控制,减少矿井事故的发生。针对矿井场景下的人体运动区域检测,提出了一种实现人体运动区域提取的融合方法TD-HF(Time Difference and Haar Feature),该方法融合了时间差分法和基于Haar特征的人体检测算法。实验表明,所提方法在检测率和误识率方面均比单纯的基于AdaBoost算法的分类器更胜一筹,并且在检测时间上满足实时性要求,适用于矿井视频这种特殊场景下的人体运动区域检测。

一种抗遮挡的自适应尺度目标跟踪算法

瞿中,赵从梅

计算机科学. 2018, 45 (4): 296-300. doi:10.11896/j.issn.1002-137X.2018.04.050

摘要 ( 375 )

PDF(6229KB) ( 998 )

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

在处理尺度变化和目标遮挡方面,利用相关滤波器的不同特征进行目标跟踪仍然存在问题。提出了一种基于随机蕨丛检测器的多尺度核相关滤波器算法。该算法将跟踪任务分解为目标尺度估计和位移估计,同时将CN颜色特征和HOG特征进行响应融合,进一步提高了整体跟踪性能。此外,文中训练了一个在线随机蕨分类器,在目标丢失后其能重新获取目标。与KCF,DSST,TLD,MIL,CT共5种算法相比,所提算法不仅能够准确地估计目标状态,而且可以有效处理目标的遮挡问题。

基于高斯分布的大气光估计算法

张文博,侯晓荣

计算机科学. 2018, 45 (4): 301-305. doi:10.11896/j.issn.1002-137X.2018.04.051

摘要 ( 443 )

PDF(7969KB) ( 873 )

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

针对现有去雾算法在估计大气光向量时,所采用的方法包含的大气光候选点数量较少,导致估计结果在统计意义上误差较大这一问题,提出了基于高斯分布的大气光估计算法。该算法首先使用阈值划分的方式选取候选点以增加初始样本点数量；然后引入聚类算法对原算法所得光源点簇进行合并以提高单个点簇所含样本点个数；同时,使用比例阈值过滤掉不合理的点簇,并将各点簇视为单独光源,单独计算其对周围像素的影响,其影响通过二维高斯分布函数进行建模；最后使用大气光图取代全局大气光复原图像。实验结果表明, 相对于原算法, 使用高斯分布大气光图复原的结果在主观视觉上看起来更加自然,且其客观图像质量评价指标也得到了提高。

用于图像重构的基于行间支撑集相似度的CoSaMP算法

杜秀丽,顾斌斌,胡兴,邱少明,陈波

计算机科学. 2018, 45 (4): 306-311. doi:10.11896/j.issn.1002-137X.2018.04.052

摘要 ( 358 )

PDF(9482KB) ( 684 )

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

压缩采样匹配追踪(CoSaMP)算法的性能受初始支撑集选择的制约,初始支撑集选择不准确不仅影响重构精度,还会降低重构速度。针对该问题,将图像在稀疏域的结构特性引入到CoSaMP算法中,提出了支撑集相似度的概念；利用数字图像相邻行之间原子支撑集的相似性,提出了基于行间支撑集相似度的CoSaMP算法。实验结果表明,在同等采样率的条件下, 与传统的CoSaMP算法相比,所提算法在不增加算法时间复杂度的同时提高了重构质量 ,峰值信噪比提高了0.6~2.5dB。

基于组稀疏表示的在线单帧图像超分辨率算法

李键红,吴亚榕,吕巨建

计算机科学. 2018, 45 (4): 312-318. doi:10.11896/j.issn.1002-137X.2018.04.053

摘要 ( 413 )

PDF(6092KB) ( 740 )

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

基于稀疏表示的图像超分辨率重建算法以近似随机抽取的方式选取字典中的原子来拟合图像片,而实际中的字典原子的选择体现出了很强的结构稀疏性,从而导致算法计算复杂且引入了大量的误差,影响重建图像的质量。针对该问题,提出了一种基于组稀疏表示的在线图像超分辨率重建算法。该方法引入组稀疏理论,仅利用输入的低分辨率图像作为样本来构建组稀疏字典,通过结合组稀疏性和几何对偶性来构建超分辨率图像算法的成本函数,并使用提出的一种迭代的方法进行求解。实验表明,该算法在视觉观察和参数比较上都优于当前主流的超分辨率算法。