Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2010年 第47卷 第8期    出版日期:2010-08-15
论文
基于关键姿态分析的运动图自动构建
宗 丹, 李淳芃, 夏时洪, 王兆其,
2010, 47(8):  1321-1328. 
摘要 ( 362 )   HTML ( 0)   PDF (1544KB) ( 421 )  
相关文章 | 计量指标
高结点聚合运动图(snap together motion graph, STM graph)是刻画虚拟角色运动序列关系的一种结构化运动图.其特点是图中每个结点都包含多条与之相连的边,能够实现对虚拟角色的灵活控制.然而现有的高结点聚合运动图构建方法存在手工标注任务繁重、关键姿态提取结果不准确等问题.针对上述问题,提出了一种基于关键姿态分析的运动图自动构建新方法:通过维度约简和非参数密度估计分析样本数据的概率密度,获得一组关键姿态;然后通过分割获得运动片段,最后构建高结点聚合运动图.该方法不仅提高了关键姿态的提取精度,减少了构图过程的主观因素,同时提高了对虚拟角色控制的灵活性.实验结果表明了该方法的有效性.
基于相关向量机的图像阈值技术
乔立山, 陈松灿, 王 敏,
2010, 47(8):  1329-1337. 
摘要 ( 523 )   HTML ( 0)   PDF (2757KB) ( 393 )  
相关文章 | 计量指标
图像阈值化是一种直观有效的图像分割技术,在图像分析、模式识别及计算机视觉中具有重要应用.传统的阈值化方法通常基于某个特定的优化问题,需要在整个灰度范围内搜索最佳阈值(或阈值组合).最近,基于支持向量回归(SVR)的多阈值分割算法,直接从支持向量(SV)中获得阈值信息,无需对图像施加任何先验假设,并避免了繁琐的优化过程.然而:1.如何从众多SV中获得可靠的阈值尚待解决(SVR阈值方法的公开问题);2.虽然SVR阈值技术避免了传统多阈值算法可能出现的组合优化问题,但是其中超参数的选择往往需要耗时的交叉验证;3.算法在单峰直方图情形下失效.针对这些问题,并受相关向量机(RVM)方法的启发,提出了一种新的基于RVM的多阈值自动选择技术.由于RVM可以极大地约减“SV”数目,并且无需交叉验证进行参数调整,使得最终阈值的确定更加高效、可靠且异常容易;另外所提算法能有效地处理单峰直方图情形,使阈值分割具有更强的适应性.实验表明基于RVM的阈值技术不仅保留了SVR阈值技术的优点,而且解决了其中的公开问题,并显著地提高了算法的效率和适应能力.
基于升阶矩阵的有理曲面之间L\-2距离计算
黄伟贤 王国瑾
2010, 47(8):  1338-1345. 
摘要 ( 331 )   HTML ( 2)   PDF (698KB) ( 429 )  
相关文章 | 计量指标
计算曲线曲面之间的距离是几何设计与几何逼近的一个重要课题,如估计有理曲线曲面的降阶逼近和多项式逼近的误差时,需要一种简洁有效的方法来计算原曲线曲面和逼近曲线曲面间的距离.首先给出了基于升阶矩阵的两张有理Bézier曲面的L\-2距离表示,然后利用这个L\-2距离表示和最小二乘法,对有理Bézier曲面多项式逼近的误差作了明确而统一的度量.最后,基于Bernstein基与B样条基的相互转换,把有理Bézier曲线曲面的L\-2距离表示简洁地推广到有理B样条曲线曲面.所得到的几个计算曲线曲面之间的L\-2距离的公式均可通过矩阵运算表示,十分利于程序的实现,有应用价值.最后还给了几个实例.
一种基于实体替换与小波均值的二维工程图盲水印算法
彭 飞, 黄小峰, 邓 韬, 龙 敏,
2010, 47(8):  1346-1353. 
摘要 ( 437 )   HTML ( 1)   PDF (1158KB) ( 387 )  
相关文章 | 计量指标
提出了一种基于实体替换与小波均值的二维工程图盲水印算法.首先在保证工程图外观不变的情况下,将二维工程图中的直线替换成多段线,并提取多段线顶点坐标进行变换以获取旋转、平移和缩放不变性,然后对变换后的顶点坐标数据构造变换单元,对每个单元进行二维小波变换,最后在小波系数中嵌入水印.同时对水印信息采用混沌加密以提高水印的安全性.实验结果与分析表明:这种算法能够实现水印的盲提取,具有良好的不可见性和较高的运行效率,并对平移、旋转、均匀缩放、图形增加等攻击具有良好的鲁棒性,为二维CAD工程图的版权保护提供了一种新的方法.
人体运动仿真综述
夏时洪 魏 毅 王兆其
2010, 47(8):  1354-1361. 
摘要 ( 690 )   HTML ( 3)   PDF (767KB) ( 1117 )  
相关文章 | 计量指标
人体运动仿真是生物力学、机器人学和计算机科学交叉产生的研究领域,其目的是建立计算模型模拟人体在给定约束下自然真实的物理运动.与一般的人体动画相比,人体运动仿真要求合成的人体运动满足牛顿定律.因此,人体运动仿真除了可用于特效制作,还可用于物理任务的操作培训和学习等方面.首先介绍人体运动仿真的起源与典型应用,然后阐述人体运动仿真研究的关键技术.在关键技术介绍中,引入人体运动仿真研究中使用的人体简化几何模型和物理模型,然后将人体运动仿真方法分成两类:基于前向动力学方法与基于逆向动力学方法,并详细介绍它们的发展历程和最新研究进展.最后从交互动作的仿真、仿真结果验证等几方面讨论人体运动仿真未来可能的发展方向.
区间值信息系统的知识约简
张 楠 苗夺谦 岳晓冬
2010, 47(8):  1362-1371. 
摘要 ( 411 )   HTML ( 0)   PDF (817KB) ( 594 )  
相关文章 | 计量指标
知识约简是粗糙集理论的重要研究内容之一.传统的知识约简主要针对单值信息系统,但在许多实际问题中,信息系统中的数据往往以区间值的形式存在,因此,区间值信息系统的知识约简研究具有重要意义.现有工作中,论域的分类结果存在冗余度大、误分率高等问题.针对上述问题,在区间值信息系统中引入了α-极大相容类的概念,并提出了新的粗糙上下近似算子,α-极大相容类的采用有效地提高了分类和粗糙近似精度.最后,给出了区间值信息系统知识约简的定义和相应区分函数的计算方法,为区间值信息系统的知识获取提供了一条新的途径.
简约支持向量聚类
凌 萍, 王 喆, 周春光, 黄 岚,
2010, 47(8):  1372-1381. 
摘要 ( 675 )   HTML ( 0)   PDF (1416KB) ( 455 )  
相关文章 | 计量指标
针对传统支持向量聚类(support vector clustering, SVC)的高耗费和低性能弊端,提出了简约支持向量聚类算法(reduced support vector clustering, RSVC).RSVC的核心是简约策略和新的簇划分方法.前者是基于薛定谔方程而设计,提取对模型生成有重要意义的数据构成简约子集,并在此子集之上完成优化过程.后者提出并证明了高斯核函数特征空间的几何性质,并以此设计方法完成对数据簇的辨识任务.理论分析和实验结果表明,和同类算法相比,RSVC可更有效地解决两个弊端,在实际应用中取得良好的聚类效果.
基于自组织演化的多Agent可信联盟研究
程柏良, 曾国荪, 揭安全,
2010, 47(8):  1382-1391. 
摘要 ( 455 )   HTML ( 0)   PDF (1681KB) ( 418 )  
相关文章 | 计量指标
不同于现有采用博弈论的方法研究多Agent联盟技术,从联盟信任这一角度开展可信联盟研究,首先在历史合作信息的基础上构建个体信任度,在此基础上建立联盟信任度,进而形成可信联盟.通过联盟间的竞价协商来使得多个小规模的联盟合并成规模更大的联盟从而完成复杂的任务,刻画出联盟演化的自组织性并将信任贯穿于联盟的演化过程.为获得稳定的联盟,在联盟内部收益分配的机制上采用自由竞价与信任评估方式,最后在联盟收益分配结束后,通过信任修正来解决自由竞价中的欺诈行为,并同时获得数据隐私保护,使得联盟内部成员获得公平合理而又高效的分配机制.通过联盟信任,建立起分布式合作模型,可以大规模地降低计算复杂度和可控的风险收益,为动态联盟的稳定性提供有效保障.
一种针对弱标记的直推式多标记分类方法
孔祥南 黎 铭 姜 远 周志华
2010, 47(8):  1392-1399. 
摘要 ( 619 )   HTML ( 0)   PDF (1248KB) ( 598 )  
相关文章 | 计量指标
多标记学习主要解决一个样本可以同时属于多个类别的问题,它广泛适用于图像场景分类、文本分类等任务.在传统的多标记学习中,分类器往往需要利用大量具有完整标记的训练样本才能获得较好的分类性能,然而,在很多现实应用中又往往只能获得少量标记不完整的训练样本.为了更好地利用这些弱标记训练样本,提出一种针对弱标记的直推式多标记分类方法,它可以通过标记误差加权来补全样本标记,同时也能更好地利用弱标记样本提高分类性能.实验结果表明,该方法在弱标记情况下的图像场景分类任务上具有较好的性能提高.
基于多核学习的双稀疏关系学习算法
韩彦军 王 珏
2010, 47(8):  1400-1406. 
摘要 ( 460 )   HTML ( 0)   PDF (776KB) ( 437 )  
相关文章 | 计量指标
在关系学习中样本无法在R\+n空间中表示.与其他机器学习问题有很大不同,因为无法利用R\+n空间的几何结构使得其解决异常困难.将多核学习方法用于关系学习中. 首先,可以证明当用逻辑规则生成的核矩阵进行多核学习时,其他核都可以等价转化为线性核.在此基础上,通过用修正FOIL算法迭代生成规则,构造相应的线性核然后进行多核优化,由此实现了由规则诱导出的特征空间上的线性分类器.算法具有“双稀疏”特性,即:可以同时得到支持向量和支持规则.此外,可以证明在规则诱导出的特征空间上的多核学习可以转化为平方\-1 SVM,这是首次提出的新型SVM算法.在6个生物化学和化学信息数据集上与其他算法进行了对比实验.结果表明不仅预测准确率有明显提高,而且得到的规则集数目更小,解释更为直接.
类别不平衡的分类方法及在生物信息学中的应用
邹 权 郭茂祖 刘 扬 王 峻
2010, 47(8):  1407-1414. 
摘要 ( 679 )   HTML ( 0)   PDF (811KB) ( 733 )  
相关文章 | 计量指标
提出一种处理正反例不平衡的分类方法,以解决生物信息学中的snoRNA识别、microRNA前体判别、SNP位点的真伪识别等问题. 利用集成学习的思想,将反例集均匀分割并依次与正例集组合,得到一组类别平衡的训练集.然后对每个训练集采用不同原理的分类器进行训练,最后投票表决待测样本.为了避免弱分类器影响投票效果,结合AdaBoost思想,将每个分类器训练中产生的错误样本加入到下2个分类器的训练集中,既避免了AdaBoost的反复训练,又有效地利用投票机制遏制了弱分类器的影响.5组UCI测试数据和3组生物信息学实验证明了它在处理类别不平衡分类问题时的优越性.
不确定数据库中基于x-tuple的高效Top-k查询处理算法
刘德喜 万常选 刘喜平
2010, 47(8):  1415-1423. 
摘要 ( 359 )   HTML ( 0)   PDF (1048KB) ( 425 )  
相关文章 | 计量指标
Top-k查询由于其广泛的应用而倍受欢迎.不确定数据库中通常考虑的两条生成规则是:独立和互斥,一个x-tuple是由一些互斥的元组组成的,构成一个x-tuple的各个元组称为该x-tuple的可选元组.U-kRanks查询考虑x-tuple中每个可选元组排在前k的概率,并返回最可能排在前k的k个元组.已有的Top-k语义都没有将x-tuple作为一个整体,因此,定义了一种新的Top-k查询语义,不确定x-kRanks查询 (U-x-kRanks),该Top-k语义返回最可能排在前k的k个x-tuple而非元组.新语义考虑x-tuple中的每个可选元组位于前k的概率,并将之汇集,得到整个x-tuple位于前k的概率.提出了一种基于动态规划的有效算法处理U-x-kRanks 查询,在最小的搜索空间内完成查询处理过程.不同数据集合上的综合实验显示,所提出的算法是高效的.
命题μ-演算全局模型检测的高效算法设计
江 华
2010, 47(8):  1424-1433. 
摘要 ( 528 )   HTML ( 1)   PDF (815KB) ( 415 )  
相关文章 | 计量指标
在Long, Browne, Jha 和 Marrero等人工作的基础上,详细分析了用Tarski不动点定理计算不动点交替嵌套深度为4的命题μ-演算公式的计算过程,找到了计算中间结果间具有的两组偏序关系,利用这两组偏序关系设计了一个高效的命题μ-演算全局模型检测算法,该算法与Long等人提出的算法有相似的时间复杂度(O((2n+1)\+{[d/2]+1})相对于O(n\+[d/2]+1})),但空间复杂度有很大的改进(O(dn)相对于O(n\+{[d/2]+1})),其中n是变迁系统的状态规模,d是命题μ-演算公式中不动点算子的嵌套深度.算法性能的改进对于命题μ-演算模型检测技术的理论研究与实际推广应用都意义重大.
基于IBM Cell多核平台的OpenMP数组私有化技术研究
李建江 刘珍珍 王 珏
2010, 47(8):  1434-1441. 
摘要 ( 531 )   HTML ( 0)   PDF (1002KB) ( 468 )  
相关文章 | 计量指标
数组私有化是并行化编译中的重要技术之一,IBM Cell是异构多核处理器,SPMD代表实现OpenMP数组私有化的重要手段,但是SPMD形式的OpenMP程序却不能直接通过IBM XLC(适用于IBM Cell多核平台的编译器)的编译.为了解决该问题,并充分利用IBM Cell本地存储器中的静态缓冲区以减少DMA通信,提出一种IBM Cell多核平台的OpenMP数组私有化技术.旨在充分利用本地存储器、减少DMA通信,集中处理可重用数据的私有化.主要包括:数组私有化分析、数组私有化转换、同步消除与非阻塞DMA操作,从而扩大数据的可重用作用域.转换后的Jacobi迭代代码进行实际测试表明,这种基于IBM Cell多核平台的数组私有化技术能够平均提高3%左右的执行性能,尤其对于小规模计算来说性能提高还会更多.
基于行为效果的服务可替换性分析
刘 莹, 张一川, 张 斌, 张明卫, 朱志良,
2010, 47(8):  1442-1449. 
摘要 ( 388 )   HTML ( 0)   PDF (769KB) ( 468 )  
相关文章 | 计量指标
服务可替换性分析是服务无缝集成与协作领域的一个重要问题,通过形式化的分析方法验证替换前后服务组合效果是否一致,有助于实现服务的动态组合.现有研究针对服务内部的操作和操作序列是否一致对服务的可替换性进行分析,会缩小可替换服务的空间.基于服务执行时的触发条件和结果提出了服务可替换性的定量判定方法.该方法采用有色Petri网对服务行为进行建模,将服务执行时的触发条件和结果定义为服务的行为效果,给出了行为效果一致的概念,并结合Petri网变换理论实现对服务可替换度的计算.最后通过定理证明了方法的有效性,这种定量分析的判定方法对于服务替换的正确建立和替换后组合服务的可靠执行具有重要作用.
VSR: 多sink机会移动传感器网络的数据收集
熊永平, 孙利民, 马 建, 牛建伟,
2010, 47(8):  1450-1458. 
摘要 ( 379 )   HTML ( 2)   PDF (2000KB) ( 470 )  
相关文章 | 计量指标
机会移动传感器网络可应用在野生动物监控,或利用手持设备嵌入的传感器收集城市信息等场景,往往需要将数据从源节点传输到多个基站中的任一个.提出了一个基于虚拟空间的路由机制VSR(virtual space-based routing),采用“存储-携带-转发”的传输模式实现数据收集.每个传感器节点根据与多个sink节点的期望传输延迟映射成高维空间中的一个坐标点,消息传输对应于从源节点移动到空间原点的过程.细粒度的转发决策特性,使VSR自适应于网络的动态变化,具有很好的鲁棒性.此外,VSR机制具有很低的计算和存储开销,非常适合资源受限的传感器节点.两种不同随机特性场景下的模拟实验验证了VSR机制比ZebraNet的基于历史的转发机制和随机转发机制的性能更好.
一种基于预测的WSN非均衡分簇路由算法
李 捷 韩志杰
2010, 47(8):  1459-1465. 
摘要 ( 410 )   HTML ( 0)   PDF (1359KB) ( 374 )  
相关文章 | 计量指标
无线传感器网络由部署在一定区域内大量传感器节点组成.针对无线传感器网络中分簇路由算法中存在的“热区”问题,提出了一种基于虚拟区域划分的非均衡簇路由算法.算法将簇划分的任务交由能量无限制的汇聚节点完成,使得靠近汇聚节点的内层簇的规模小于外层簇的规模.在簇的结构中引入了主、从簇头节点,从而实现了分布式簇头选举工作,同时在分簇过程中避免了每个阶段的能量消耗.将Markov预测模型引入到主簇头节点的更换过程中,从而避免了主簇头因为能量完全消耗而死亡,也避免了因为主簇头死亡而造成网络分割,降低网络的生存时间,利用NS2.26仿真平台对基于虚拟区域划分的非均衡簇路由算法进行了仿真验证,结果表明与传统路由算法相比,该算法延长了WSN的生存时间,有效提高了WSN网络健壮度.
MEANS:基于微线程结构的网络服务器
龚奕利, 雷迎春, 张 文, 吴产乐, 张国安,
2010, 47(8):  1466-1480. 
摘要 ( 483 )   HTML ( 4)   PDF (2023KB) ( 512 )  
相关文章 | 计量指标
Internet应用需要高性能的网络服务器体系结构.提出MEANS结构,这是一种针对Internet应用的网络服务器软件体系结构.通过引入一种新的线程抽象——微线程,MEANS向上层的程序员提供微线程环境,并通过传统线程并发访问下层操作系统的服务,而微线程的管理和调度则使用事件驱动机制,从而综合多线程和事件驱动结构的各自优点.此外,MEANS还具备通用性、扩展性、健壮性和适应性.经初步验证,在并发策略方面,MEANS具有相似于事件驱动结构的特性;在I/O策略方面,MEANS具有比多线程结构更好的I/O访问特性.
汇编级软硬结合的控制流检测方法
吴艳霞, 顾国昌, 戴 葵, 刘海波, 沈 晶 ,
2010, 47(8):  1481-1489. 
摘要 ( 424 )   HTML ( 1)   PDF (890KB) ( 366 )  
相关文章 | 计量指标
控制流检测技术是防止由于瞬时故障造成程序错误运行的有效手段之一,在ARGOS卫星上测试过的基于汇编语言的软件控制流检测算法CFCSS具有较高的错误检测能力和较低的冗余指令开销,实用性较强,但此算法存在检测混淆和检测出错现象.为此,首先阐述了CFCSS算法中存在的检测混淆和检测出错现象;接下来根据汇编语言特点,修改了基础基本块的选择方法和多调整签名值赋值语句的插入位置,提出了改进的ICFCSS控制流检测算法;为了在ICFCSS算法基础上进一步提高错误检测能力、降低故障延迟时间和冗余指令开销,提出了软硬结合的ICFCSSHS控制流检测方法,此方法在编译程序时只增加了和签名有关的信息,在程序运行时通过译码阶段判指令类型来触发相应的硬件完成控制流检测.实验表明,此方法的冗余代码空间开销比CFCSS算法减少了21.5%,平均未检测出错误率仅为1.5%,具有一定的使用价值.
基于日志的系统任务模型推理工具及其应用
高崇南 余宏亮 郑纬民
2010, 47(8):  1490-1496. 
摘要 ( 362 )   HTML ( 1)   PDF (1166KB) ( 419 )  
相关文章 | 计量指标
分布式系统成为Internet应用的关键组成部分,理解其运行时行为成为验证系统设计、解决系统逻辑与性能错误的关键.已有工作需要程序员手工标注代码或网络数据包,提供描述请求处理和任务执行的相关信息,以抽取系统运行时路径.工作创新性地从系统日志中提取系统任务信息,推断出系统的层次结构任务模型,利用任务模型将系统运行时行为分解为有层次结构的任务实例.实际应用经验表明,利用日志提取的任务模型能够帮助理解系统运行时行为,并解决系统的性能问题.