Please wait a minute...
  • 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

当期目录

    目录
    2018年第5期目录
    2018, 40(05): 0-0. doi:
    摘要 ( 7 )   PDF (289KB) ( 18 )     
    高性能计算
    一种云环境下基于混合型BBO的任务调度算法
    童钊1,2,陈洪剑1,2,陈明1,2,梅晶1,2,刘宏1,2
    2018, 40(05): 765-772. doi:
    摘要 ( 148 )   PDF (887KB) ( 339 )     

    任务调度在云计算中占有重要地位,是影响云计算性能的关键因素,被证明是NP问题。启发式算法是解决该问题的最有效方法之一,针对近年来出现的一种新型启发式算法——BBO算法展开研究,由于BBO算法在求解过程中收敛速度较慢,因此结合粒子群算法提出了一种新型算法的任务调度算法——HMBBO,并结合Cloudsim云仿真平台,进行了以Makespan为目标函数的比对实验。实验结果表明,与几种经典的启发式算法相比,HMBBO算法具有寻优能力强、收敛速度快、求解质量高的特点,为解决云计算环境中任务调度问题提供了一种新思路。

    基于无锁原子操作的多线程并行Delaunay三角化算法
    王俊吉1,2,朱朝艳1,2,4,陈建军1,2,郑澎3,5,徐权3
    2018, 40(05): 773-779. doi:
    摘要 ( 144 )   PDF (575KB) ( 228 )     

    基于OpenMP实现了一种基于空腔交叠互斥准则与无锁原子操作的Delaunay三角化增量插点细粒度并行算法。在串行算法的基础上,对点集引入Hilbert排序,使相邻点在几何上亦相邻。引入互斥机制——仅当各空腔无公共单元及公共相邻边时,才可同时插入,根据Delaunay局部性准则可保证整个网格都具备Delaunay属性。每个单元用一个原子变量标记该单元是否已被占有,在计算Delaunay空腔时,各线程将试图写入该原子变量,但本竞争机制保证有且仅有一个线程能成功获得该单元的所有权,以保证算法的互斥性。经数值实验表明,对于107的点集,该算法在16核下加速比可达7.06倍。

    基于TI 6678多核DSP的OpenCV并行优化
    李津1,罗昕颉2,扈啸1,陈跃跃1
    2018, 40(05): 780-786. doi:
    摘要 ( 523 )   PDF (728KB) ( 391 )     
    数字信号处理器(DSP)广泛应用于各类工业领域和军事装备领域,OpenCV是业界通用的开源图像处理算法库,但目前鲜有针对DSP平台的OpenCV移植和优化实现。在TI 6678平台上实现了OpenCV的移植,生成了支持绝大多数OpenCV功能的TI 6678底层支持库。在此基础上,深入分析了一类OpenCV库函数在TI 6678硬件平台运行的计算特征和数据流,提出了一种针对这类OpenCV库函数的优化方法,将TI 6678体系结构支持的DMA和Cache操作与OpenMP并行框架高效结合,实现这类OpenCV库函数在TI 6678芯片上的优化和多核并行。依据本文的方法,优化改造的OpenCV库函数在TI 6678上单核运行性能最多可提升3.6倍,在单核优化基础上并行改造的这类库函数8核加速比达到2.55~7.06。
     
    基于选择性集成的并行多分类器融合方法
    陶晓玲1,2,亢蕊楠3,刘丽燕3
    2018, 40(05): 787-792. doi:
    摘要 ( 145 )   PDF (529KB) ( 233 )     

    为解决多分类器融合过程中时间开销大和准确率不高的问题,采用改进的Bagging方法并结合MapReduce技术,提出了一种基于选择性集成的并行多分类器融合方法PMCF-SE。该方法基于MapReduce并行计算架构。在Map阶段,选择分类效果较好的基分类器;在Reduce阶段,从所选的基分类器中选择差异性较大的基分类器,然后采用D-S证据理论融合被选的基分类器。实验结果表明,在执行效率方面,与单机环境相比,集群环境下该方法的执行效率有所提高;在分类准确率方面,与Bagging算法相比,PMCF-SE在不同的基分类器数目下的分类准确率都高于Bagging算法。

    一种基于FPGA的素域椭圆曲线标量乘结构
    邬贵明,王淼,谢向辉
    2018, 40(05): 793-797. doi:
    摘要 ( 144 )   PDF (453KB) ( 242 )     

    基于一种简化求商的高基Montgomery模乘流水化阵列结构,提出并实现了素域上椭圆曲线标量乘硬件结构。该结构采用修正的Jacobian坐标的点加和倍点算法以及Kaliski提出的Montgomery模逆的算法。实验结果表明,该结构与相关工作相比具有更好的性能。

    一种基于遗传算法的BLAS库优化方法
    孙成国1,兰静2,姜浩1
    2018, 40(05): 798-804. doi:
    摘要 ( 202 )   PDF (642KB) ( 288 )     
    基于OpenBLAS和BLIS开源线性代数基础算法库,对稠密矩阵乘法GEMM运算的性能优化展开研究。针对如何选取稠密矩阵分块并行算法的关键分块参数这一问题,建立性能优化模型。采用改进的遗传算法求解上述优化模型,将某一分块参数组合(种群个体)所对应的稠密矩阵乘法的性能值作为该个体的适应度,通过不断迭代地进行选择、交叉、变异操作,找到最优的分块参数组合,使得稠密矩阵运算的性能值最优。数值实验表明,基于遗传算法求解得出最优分块参数下的GEMM性能值优于默认分块参数下的性能值,达到了优化的目的。
     
    计算机网络与信息安全
    可实现隐私保护的多接收者异构聚合签密方案
    牛淑芬,牛灵,王彩芬,杨喜艳,贾向东
    2018, 40(05): 805-812. doi:
    摘要 ( 119 )   PDF (617KB) ( 246 )     
    考虑到异构密码系统中的安全通信与隐私保护,提出了一个无证书密码系统到基于身份密码系统的异构签密方案,允许多个发送者与多个接收者进行安全通信并为系统中的发送者实现了匿名,只有信任机构可追踪发送者的真实信息。对于接收者,通过应用拉格朗日插值公式防止了向未授权用户泄露合法接收者的用户信息。在随机预言模型下证明了本方案满足适应性选择密文攻击以及适应性选择消息攻击下的不可区分性和存在性不可伪造。实验结果表明,本方案有效地提高了系统的计算效率。
     
    Piazza问答平台与Open edX平台的集成
    张燕妮1,陆慧梅1,向勇2
    2018, 40(05): 813-820. doi:
    摘要 ( 96 )   PDF (890KB) ( 188 )     

    Piazza问答平台与Open edX学习平台两者相互独立,影响用户使用,并且Piazza问答数据无法被高效利用。针对上述问题 ,对Piazza问答数据进行持久保存,
    利用多标签过滤方法提高了Piazza问答数据的查找能力;基于Piazza-Xblock插件,实现了在Open edX平台查找和展现Piazza问答数据,以及通过URL参数直接访问Piazza特定页面的功能,达到Piazza问答平台与Open edX平台有机结合的效果。

    基于RSS阈值模型的Amorphous算法定位误差抑制
    宋海声,朱长驹,吴佳欣,杨鸿武
    2018, 40(05): 821-828. doi:
    摘要 ( 110 )   PDF (949KB) ( 189 )     
    针对无线传感器网络定位算法在不同的通信模型下误差较大的问题,在Amorphous算法离线计算网络平均连通度的基础上,建立了四种RSS阈值模型来抑制Amorphous算法在不同通信模型下的定位误差。由不同阈值模型得到的阈值在不同程度上修正了算法的梯度值,使定位误差得到抑制。仿真结果表明,Amorphous算法在Regular模型下的最优阈值模型从Regular阈值模型和Log-normal阈值模型中选择;算法在Log-normal模型下的最优阈值模型从Regular阈值模型、Log-normal阈值模型、DOI阈值模型和RIM阈值中选择;算法在DOI模型和RIM模型下的最优阈值模型从Log-normal阈值模型、DOI阈值模型和RIM阈值模型中选择,最后得到Amorphous算法在不同的通信模型、通信半径和不规则度下对应的最优阈值模型。

     
    图形与图像
    基于D-S证据理论的人体跌倒检测方法
    孙子文1,2,李松1,孙晓雯1
    2018, 40(05): 829-835. doi:
    摘要 ( 107 )   PDF (585KB) ( 181 )     
    针对人体跌倒检测算法存在错误否定率高的问题,研究了一种基于D-S证据理论的人体跌倒检测算法。采用智能手机内置的加速度传感器和陀螺仪传感器获得人体手臂运动的三维方向的运动数据,采用三阶滑动平均滤波器对获得的两个传感器的三维原始数据进行预处理;从三维预处理后的数据中提取运动幅度、倾斜程度以及旋转程度三种特征;采用动态时间规整方法分别依据三种特征进行局部检测,局部检测结果作为证据被D-S证据理论组合规则所采用以得到最终融合的全局检测结果,其中各证据被证据权修正以避免证据冲突问题。实验结果显示,本文算法准确度高于对比方法,能有效提高检测性能。
     
     
    基于Kinect传感器和ORB特征的视觉SLAM算法设计与实现
    许芬,王振
    2018, 40(05): 836-841. doi:
    摘要 ( 163 )   PDF (935KB) ( 243 )     

    介绍了一个基于嵌入式平台和Kinect传感器的同时定位与地图创建算法的设计与实现。Kinect传感器包括一个可见光彩色摄像头和一个利用结构光测量深度的红外CMOS摄像头。 算法利用ORB算子作为环境特征点的描述信息,并利用基于边沿的最近邻修复方法对深度图像进行修正以获得完整的深度信息。在此基础上,利用LSH方法进行特征点的匹配。实验结果表明,基于ORB特征的视觉SLAM算法具有较好的实用性和良好的定位精度,可以广泛应用于室内机器人的自主导航任务。

    基于稀疏表示与字典学习的彩色图像去噪算法
    杨培1,高雷阜1,王江1,訾玲玲2
    2018, 40(05): 842-848. doi:
    摘要 ( 133 )   PDF (1127KB) ( 297 )     
    针对彩色图像在去噪时易产生模糊现象和伪色彩的问题,提出多信息结合字典算法。首先提出了基于RGB颜色空间各通道模值的加权梯度定义,并在此基础上建立了由彩色图像的亮度、加权梯度、颜色信息结合的一种过完备结构字典。其次利用噪声图像的稀疏性,通过不断更新迭代的字典训练过程,找到最优稀疏系数和最优学习字典,从而将噪声信息和图像有用信息分离开,精确重构图像并单求其颜色,进而得到去噪后的彩色图像。实验结果显示,与已有算法相比,本文提出的算法在不同的噪声强度下都取得了更好的视觉效果和更高的客观评价指标值,表明该算法具有良好的去噪性能。
     
     
    图像矩阵上的广义最大噪声分离算法
    张大明,张学勇,李璐,刘华勇
    2018, 40(05): 849-855. doi:
    摘要 ( 114 )   PDF (1135KB) ( 246 )     

    主成分分析(PCA)是模式识别中一种重要的变换工具,在图像处理的特征提取和降维方面有广泛的应用。然而,由于二维图像数据需要进行向量化处理,导致高维向量的产生和像素空间位置丢失。广义主成分分析(GPCA)则是基于图像矩阵的主成分分析推广算法,它不改变像素间的空间位置关系,而且计算量也显著降低。但主成分分析和广义主成分分析都没有考虑到实际图像中存在的噪声干扰。最大噪声分离(MNF)则是一种面向噪声干扰的变换方法,与主成分分析基于方差的最大化不同,最大噪声分离是基于信噪比的最大化。与GPCA的推广类似,在图像二维矩阵上推广最大噪声分离方法,提出一种广义最大噪声分离(GMNF)算法。该变换方法在保证重构时信噪比最大的同时,也具有不改变像素空间位置、计算量小的优点。在人脸和红外图像上的仿真实验结果验证了所提算法的有效性。

    基于时空混沌和小波变换的图像加密算法
    王磊,薛伟
    2018, 40(05): 856-862. doi:
    摘要 ( 201 )   PDF (825KB) ( 275 )     
    本文提出一种基于时空混沌系统的图像加密算法。首先对明文图像进行Zigzag方式扫描置乱,再对置乱后的图像分块;然后用Logistic混沌系统生成的伪随机序列对其进行置乱,置乱结束后对其进行整数小波变换,利用基于耦合映像格子CML的混沌系统生成三个伪随机序列对低频小波系数进行置乱操作,同时对低频小波系数进行扩散,然后进行整数小波逆变换;最后再由基于CML的混沌系统生成两个伪随机序列对图像像素值进行扩散操作,得到最终的加密图像。经测试,该算法具有良好的加密性能,可以有效抵挡差分、明文等攻击。
     
     
    基于多尺度自适应扩散方程的边缘检测方法
    郭伟,董宏亮,石尚
    2018, 40(05): 863-871. doi:
    摘要 ( 141 )   PDF (1294KB) ( 255 )     

    针对Canny算法对较高密度椒盐噪声和双阈值选取方面存在的不足,提出一种改进方法,采用多尺度自适应各向异性扩散方程对图像进行平滑,有效去除较高密度脉冲信号的同时又可以更好地保留边缘轮廓信息。在双阈值门限的选取上采用最大类间方差法根据图像的灰度信息自适应地选取,可以更好地满足实时性要求。为验证其性能,在不同噪声浓度情况下进行实验,结果表明,改进的边缘检测算法可以更完整地保留边缘信息,提高边缘检测的准确性,得到较理想的边缘轮廓信息。

    人工智能与数据挖掘
    基于计算机视觉及深度学习的无人机手势控制系统
    马乐乐,李照洋,董嘉蓉,侯永宏
    2018, 40(05): 872-879. doi:
    摘要 ( 203 )   PDF (857KB) ( 585 )     
    传统的无人机人机交互需要专门的设备和专业的训练,便捷新颖的交互方式往往更令人青睐。利用普通相机,对基于计算机视觉以及深度学习的无人机手势控制系统进行了研究。该系统首先利用快速跟踪算法在视频序列中提取出操作者所在区域,大大减少后续视频处理压力的同时去除了复杂背景以及相机漂移的影响。其次,根据动作的时间信息,用不同颜色编码光流特征,叠加在一张图片上,将视频转换为同时包含时间特征以及空间特征的彩色纹理图。最后,利用卷积神经网络对彩色纹理图进行学习及分类,根据分类结果生成控制无人机的指令。该系统每0.4 s对1.6 s内的动作进行一次判定,利用卷积神经网络对图片的分类实现实时性的人机交互,系统在60 m范围内的识别准确率在93%以上,在室内和室外环境下,操作者可以通过模仿指令动作方便地控制无人机。
     
     
    一种融合社会化标注系统中主题域相似的个性化排序方法
    黄进,周栋
    2018, 40(05): 880-887. doi:
    摘要 ( 117 )   PDF (718KB) ( 194 )     
    随着网络技术的发展,互联网中越来越多的资源被应用于信息检索中,大量的研究表明,社会化标注可以用于改善信息检索。现有个性化排序的方法中,用户之间的相似度大多通过其共同使用过的标签集来计算。然而,现实中用户标注数据存在稀疏性和标签同义词等问题,导致相似度计算并不准确。在前人研究的基础上,提出了一种融合主题域相似的个性化排序方法。该方法首先通过主题域的划分,将不同主题含义的网页及标签分开,通过构建的标签相似网络找出标签同义词。然后结合用户标签和主题偏好找出兴趣相近的用户,并对用户的标注信息进行扩展,从而能够有效地改善个性化信息检索的效果。在真实数据上的实验结果表明,该方法能有效缓解标注稀疏性和标签同义词问题,有助于改善用户检索体验。
     
     
    基于非线性距离和夹角组合的最近特征空间嵌入方法
    杜弘彦,王士同,李滔
    2018, 40(05): 888-897. doi:
    摘要 ( 151 )   PDF (857KB) ( 240 )     

    最近特征空间嵌入NFSE方法在训练过程中选取最近特征空间时采用传统的欧氏距离度量会导致类内离散度和类间离散度变化同步;测试时,最近邻规则也使用欧氏距离度量,而高维空间样本间直线距离具有趋同性。这些都会降低识别率,为解决此问题,提出了基于非线性距离和夹角组合的最近特征空间嵌入方法。在训练阶段,该方法使用非线性距离度量选取最近特征空间,使类内离散度的变化速度远小于类间离散度的变化速度,从而使转换空间中同类样本距离更小,不同类样本距离更大。在匹配阶段,使用结合夹角度量的最近邻分类器,充分利用样本相似性与样本夹角的关系,更适合高维空间中样本分类。仿真实验表明,基于非线性距离和夹角组合的最近特征空间嵌入方法的性能总体上优于对比算法。

    一种模糊认知的协同过滤算法
    刘井平,李平
    2018, 40(05): 898-905. doi:
    摘要 ( 124 )   PDF (967KB) ( 350 )     

    协同过滤是目前电子商务推荐系统中应用最成功的个性化推荐技术之一,但传统的协同过滤算法认为各个时期的评分数据信息是静态的。针对该问题,提出两种模糊认知:评分的模糊递增和评分权重的模糊递增。首先,对项目的评分信息划分时间窗口,且利用链式结构计算项目的相似性,选择目标项目的最近邻居;其次,对评分数据赋予时间权重,提出一种权重函数,并对传统的预测方法进行改进。同时,在预测阶段提出一种分层式的优化策略对评分的时间权重进行求解,完成推荐。最后,在Netflix的数据集实验结果表明,该算法较传统的协同过滤算法有显著的提高,推荐准确率提升了9.8%~14.1%。

    基于SQP局部搜索的多子群果蝇优化算法
    王英博1,王艺星2
    2018, 40(05): 906-915. doi:
    摘要 ( 100 )   PDF (756KB) ( 199 )     
    针对基本果蝇优化算法在寻优过程中种群多样性降低导致算法易陷入早熟收敛的问题,提出了基于序列二次规划(SQP)局部搜索的多子群果蝇优化算法(MFOA-SQP)。新算法将果蝇种群均匀划分为多个子群,并引入粒子群算法中的惯性权重和学习因子,协同调节果蝇移动方向和步长;每隔一定迭代次数重新划分子群,避免种群单一化,使算法更易跳出局部最优;对子群最优个体进行SQP搜索,提高局部寻优性能。通过6个测试函数和优化广义回归神经网络对银行客户进行分类的实验结果表明,算法在寻优精度和速度方面性能优越,能够有效提高广义回归神经网络的分类准确率。
     
    基于加权网络结构的冷门资源推荐算法
    刘国梁,钱晓东
    2018, 40(05): 916-923. doi:
    摘要 ( 86 )   PDF (615KB) ( 212 )     
    基于网络结构的推荐方法存在过度推荐“热门资源”,忽略推荐“冷门资源”的问题。然而实际中“冷门资源”更契合用户个性化的偏好需求,因此通过挖掘“冷门资源”来提高推荐结果的新颖性成为推荐算法研究方向之一。通过改进网络结构的推荐算法来提高对“冷门资源”的推荐:首先,构建用户-项目-特征词关联网络结构;其次,将用户对项目的评分差作为用户-项目能量传递的权值提高推荐准确性,将项目所具有的特征词的信息熵作为项目-特征词能量传递的权值增加“冷门资源”的推荐;最后,利用线性加权生成推荐列表。在MovieLens数据集上的实验结果表明,本文算法兼顾了推荐结果的准确性,提高了推荐结果中“冷门资源”的推荐。
     
    基于随机森林的老年人居住偏好预测研究
    吴帅,赵方
    2018, 40(05): 924-930. doi:
    摘要 ( 90 )   PDF (869KB) ( 250 )     
    随着我国老龄化和高龄化趋势的加速,以及家庭养老功能弱化、社会养老服务体系不健全等问题,养老事业面临诸多挑战。为了更好地为老年人提供居住安排建议,同时为养老事业管理部门提供精准的决策支持,对CHARLS问卷中将近2万名老年人的数据进行了分析,力图发现影响老年人居住偏好的主要因素。同时,也尝试利用大数据和数据挖掘方法,从个人层面对老年人居住偏好进行预测,并针对类不平衡的情况下随机森林特征选择算法进行了改进。研究结果表明:基于老年人的特征数据可以很好地预测其居住偏好,为养老事业的精准化决策提供一种依据。
     
    多路径高斯核模糊C均值聚类算法
    文传军1,汪庆淼2
    2018, 40(05): 931-937. doi:
    摘要 ( 138 )   PDF (698KB) ( 184 )     

    聚类算法单一迭代路径限制了参数优值的搜索。提出一种多路径高斯核模糊C均值聚类算法(MGKFCMs),MGKFCMs算法首先取核目标函数及模糊隶属度函数中的核函数为高斯核函数;然后利用梯度法得到聚类中心迭代公式,并基于该迭代公式和粒子群算法作聚类中心的并行参数迭代,在每一次聚类迭代时,选择聚类目标函数值小的路径作为参数迭代最终路径。对比分析了MGKFCMs算法的相关性质,通过仿真实验验证了所提算法的有效性。

    采用磁传感器的餐厅服务机器人导引控制方法
    朱琳1,2,郭健1,吴益飞1,李胜1,章伟1
    2018, 40(05): 938-942. doi:
    摘要 ( 99 )   PDF (717KB) ( 199 )     
    针对餐厅环境复杂、定位精度低等问题,提出了一种以磁传感器为核心的餐厅服务机器人导引控制方法。该方法通过安装在机器人底盘的磁传感器感知铺设在地面下的磁条,使得机器人能够平滑、准确地沿着磁条运动,在运动的过程中,结合地标模块感知到的地标信息,获取精准的位置信息和工作状态。最后将该方法应用于一种实际餐厅服务机器人,实现了机器人在餐厅内的精准定位与导航。实验结果表明,本文所提方法性能可靠、成本较低、实用性较强,具有较广阔的应用前景。

     
    融合上下文字符信息的泰语神经网络分词方法
    陶广奉,线岩团,王红斌,汪淑娟
    2018, 40(05): 943-949. doi:
    摘要 ( 116 )   PDF (522KB) ( 227 )     
    自动分词是自然语言处理的关键基础技术。针对传统泰语统计分词方法特征模板复杂、搜索空间大的问题,提出融合上下文字符信息的泰语神经网络分词模型。该模型借助词分布表示方法,训练泰语字符表示向量,利用多层神经网络分类器实现泰语分词。基于InterBEST 2009泰语分词评测语料的实验结果表明,所提方法相较于条件随机场分词模型、Character-Cluster Hybrid 分词模型以及 GLR and N-gram 分词模型取得了更好的分词效果,分词准确率、召回率和F值分别达到了97.27%、99.26 %及98.26 %,相比条件随机场分词速度提高了112.78%。
     
    基于分类融合和关联规则挖掘的图像语义标注
    秦铭,蔡明
    2018, 40(05): 950-956. doi:
    摘要 ( 75 )   PDF (519KB) ( 269 )     
    图像语义自动标注问题是现阶段一个具有挑战性的难题。在跨媒体相关模型基础上,提出了融合图像类别信息的图像语义标注新方法,并利用关联规则挖掘算法改善标注结果。首先对图像进行低层特征提取,用“视觉词袋”描述图像;然后对图像特征分别进行K-means聚类和基于支持向量机的多类别分类,得到图像相似性关系和类别信息;计算语义标签和图像之间的概率关系,并将图像类别信息作为权重融合到标签的统计概率中,得到候选标注词集;最后以候选标注词概率为依据,利用改善的关联规则挖掘算法挖掘文本关联度,并对候选标注词集进行等频离散化处理,从而得到最终标注结果。在图像集Corel上进行的标注实验取得了较为理想的标注结果。