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

当期目录

2010年 第47卷 第11期    出版日期:2010-11-15
论文
基于Level-Set的火焰动画生成方法研究
洪 义, 王兆其, 朱登明, 邱显杰,
2010, 47(11):  1849-1856. 
摘要 ( 597 )   HTML ( 2)   PDF (1636KB) ( 591 )  
相关文章 | 计量指标
火焰动画在影视、动漫、游戏等领域有着广泛的应用,而逼真模拟细节丰富的多形态火焰动画一直是图形学研究领域的难点.以Level-Set曲面变形为基础,提出了将目标形态、路径约束和燃烧传播相结合的火焰蓝芯曲面演化模型,以此模拟沿路径的火焰蔓延、移动燃烧物等现象.并针对目前模拟中火焰细节不足的问题,引入修正的MacCormack高阶对流求解器;同时,采用烟密度演化曲线模拟燃烧过程中的烟雾生成,进一步提高火焰真实感.实验结果表明该方法能逼真模拟沿路径的火焰蔓延、移动燃烧物以及其他多形态且细节丰富的火焰动画.
一种基于GPU的标量场驱动物理变形算法
伍潇潇 梁晓辉 徐启迪 赵沁平
2010, 47(11):  1857-1864. 
摘要 ( 482 )   HTML ( 0)   PDF (1533KB) ( 535 )  
相关文章 | 计量指标
基于标量场的变形技术是计算机图形学中的研究热点之一,其时效性问题一直未得到很好的解决.从自适应采样距离场的表示方法和基于物理的建模技术的优点出发,提出了一种基于GPU的标量场驱动的物理变形算法.在GPU上构造基于八叉树的自适应采样距离场(adaptively sampled distance fields,ADFs)对模型进行表示,将质点弹簧物理模型与ADFs相结合,依据物理动力学原理直接对ADFs进行控制产生模型的变形,在变形过程中对ADFs进行动态的自适应调整.为了避免由非规则结构引起物理上的非同质性,根据ADFs局部的空间分辨率大小来调整非均匀弹簧的刚度大小.实验结果表明,该算法具有较高的时间和空间效率,比CPU上的算法在时间上快一个数量级,可有效用于基于物理的交互式雕刻等动态应用中.
不互溶液体交互的快速模拟
孙洪全 韩纪庆
2010, 47(11):  1865-1870. 
摘要 ( 423 )   HTML ( 0)   PDF (1485KB) ( 617 )  
相关文章 | 计量指标
为模拟不互溶液体之间的交互现象,提出了一种基于粒子的模拟方法.通过建立一个简单有效的液体间界面张力计算模型,并利用光滑粒子流体动力学的基本方法进行求解,实现了对多种不互溶液体间交互的快速模拟.通过2组实验分别模拟2种液体间和3种液体间的交互,并与传统SPH方法和Müller等人的方法进行了对比,验证了算法的优越性.计算界面张力所需的计算量非常小,能够快速真实地模拟多种液体交互的不互溶现象,可适用于多种图形、动画的具体应用.
基于时空轨迹行为特征的视频拷贝检测方法
吴 潇, 李锦涛, 唐 胜, 郭俊波,
2010, 47(11):  1871-1877. 
摘要 ( 433 )   HTML ( 0)   PDF (1700KB) ( 527 )  
相关文章 | 计量指标
互联网环境中大规模的视频拷贝检测面临拷贝变化多样性问题和数据量大的问题,需要使用鲁棒、精简的视觉特征.提出以视频连续帧中关键点的轨迹行为作为内容匹配的特征.关键点轨迹的运动行为不受拷贝变化的影响,利用其特征可以实现鲁棒性匹配.采用马尔可夫链模型建模轨迹的行为过程,将每条轨迹表示为一个25维的精简向量特征.使用时序一致性匹配方法定位视频拷贝的段落.在标准数据集上的对比实验证明:提出的算法在各种常见的拷贝变化下可以得到较高的检测精度,特征匹配的时空消耗低,对大规模的视频拷贝检测行之有效.
一种各向异性Wells算法脑核磁共振图像分割模型
陈允杰, 张建伟, 王顺凤, 詹天明,
2010, 47(11):  1878-1885. 
摘要 ( 633 )   HTML ( 3)   PDF (1882KB) ( 569 )  
相关文章 | 计量指标
核磁共振图像分析已经成为主要的医疗辅助手段之一.然而,由于偏移场的影响导致该类图像的分析较为困难,去偏移场已成为图像分析的必要步骤.Wells算法将图像分割和去偏移场放入同一个框架内并取得较好的结果.然而该算法没有考虑像素间的位置信息,因而导致该算法对图像噪声比较敏感.为了克服其局限性,利用Gibbs理论和图像结构信息构造各向异性Gibbs随机场,并将其引入到Wells算法的框架中,完善其分类效果,使其克服噪声影响的同时还能够保持细长拓扑结构区域信息以及角点区域信息.实验证明提出的算法可以得到较好的分类结果.
一种基于离散微粒群优化的数字曲线的多边形近似算法
王 斌
2010, 47(11):  1886-1892. 
摘要 ( 426 )   HTML ( 0)   PDF (812KB) ( 439 )  
相关文章 | 计量指标
数字曲线的多边形近似是图像分析研究领域的一个热点问题.获取数字曲线的优化多边形近似是一个复杂的问题,其计算复杂度非常高.微粒群算法是近些年来提出的一种新的优化方法,已经被广泛应用于各种优化问题的求解.提出了一种求解数字曲线的多边形近似问题的基于整数编码的离散微粒群算法(IPSO).IPSO通过重新定义标准微粒群算法的速度和位置更新公式中的加法、乘法和减法运算,使得算法能运行在离散的解空间.IPSO的位置向量修复机制保证了解的可行性,而局部优化器提高了算法的搜索精度.实验结果表明,IPSO求解的质量和求解的效率均优于遗传算法和0-1编码的微粒群算法.
适用于周期休眠MAC协议的分簇时间同步算法
苏金钊 刘丽艳 吴 威
2010, 47(11):  1893-1902. 
摘要 ( 470 )   HTML ( 0)   PDF (2416KB) ( 420 )  
相关文章 | 计量指标
无线传感器网络中节点能量有限,常采用周期休眠的方式工作,而周期性休眠机制的实现依赖于节点间的时间同步方法.基于竞争的周期性休眠MAC协议的典型代表是S-MAC,在S-MAC协议的时间同步算法基础上,通过引入簇控制和边界节点控制方法提出一种分簇时间同步算法,该算法适用于周期性休眠的MAC协议.仿真和物理实验表明,分簇时间同步相比S-MAC时间同步方法能够有效控制网络中的簇数和边界节点数,减少时间同步开销和端到端传输时延,从而节省能耗,延长网络生存周期.
一种支持实时增量更新的并行包分类算法
张树壮, 罗 浩, 方滨兴,
2010, 47(11):  1903-1910. 
摘要 ( 525 )   HTML ( 0)   PDF (1758KB) ( 465 )  
相关文章 | 计量指标
UTM(unified threat management)技术的提出和应用要求多维包分类算法能够支持实时的增量更新.但由于以往的研究都侧重于加快算法的查找速度,这一需求已经成了目前包分类算法在实际应用中的一个瓶颈.提出一种二维trie树结构来组织分类规则,并给出了相应的查找及更新算法.利用trie结构的特性将各种长度的前缀组合进行分组,并依此将整个规则集分成多个子集.查找时将每一次查找过程分解成若干个可以独立运行的子任务,每个子任务处理一个子集.两级混合trie结构保持了规则之间的独立性,因此可以快速地对单条规则进行增量删除或添加.实验结果表明,本算法在保持高速查找的基础上,将单条规则的增量更新操作速度提高到了和单次查找操作同样的量级,同时并行查找使得算法对规则类型和规模的敏感度大大降低,具有较好的可扩展性.
大规模无线传感器网络中基于振荡轨迹的数据存储与发现机制
李志刚 肖 侬 褚福勇
2010, 47(11):  1911-1918. 
摘要 ( 456 )   HTML ( 0)   PDF (1746KB) ( 513 )  
相关文章 | 计量指标
在大规模无线传感器网络中,在不存在基站节点的情况下,节点组成对等网络,任何一个节点都有可能成为数据消费者节点或者数据生产者节点.传感器网络是一种资源受限的自组织网络,节点的能量和计算能力不足以支持复杂协议的设计.如何让随机产生的消费者节点和生产者节点能够有效迅速地发现对方并进行数据查询工作是传感器网络研究中的一个难点.利用数据为中心的存储策略,提出了一种振荡轨迹的数据存储发现机制.该方案要求消费者节点和生产者节点将查询或者数据存储到相应的振荡路径上.该方案不需要节点存储全局的网络信息,每个节点根据局部信息和预设的反射角度进行路由选择和数据转发.理论上,所有的振荡轨迹满足两两相交的特性,保证了数据查询成功率,而且消费者节点在查询数据时所需要的跳步距离是有界的,同时该方案能够保证数据负载的平衡.
无线传感器网络中基于线性聚合的启发式穿越算法
罗 卿, 林亚平,
2010, 47(11):  1919-1927. 
摘要 ( 369 )   HTML ( 0)   PDF (1987KB) ( 469 )  
相关文章 | 计量指标
当智能目标穿越敌方无线传感器网络的穿行时间受限时,现有基于广度优先搜索的穿越算法不能保证路径满足约束条件.为此,建立了一种穿越模型,并提出一种启发式的近似数值优化算法:k-shortest path-线性聚合启发式穿越路径算法(kSP-LAHTP).算法利用Voronoi图将连续路径问题域离散化,以曝露度和穿行时间为衡量指标,结合线性聚合的启发式路由机制,使目标实现满足时间约束值的最佳穿越.分析和实验结果表明:算法很好地解决了目标穿越时间受限情况下的穿越问题;且随系数k的增加,算法搜索路径更接近实际最佳.
动态分片在线聚集
安明远, 孙秀明, 孙凝晖,
2010, 47(11):  1928-1935. 
摘要 ( 519 )   HTML ( 1)   PDF (1678KB) ( 429 )  
相关文章 | 计量指标
传统的在线聚集方法为了避免执行中随机I/O导致的性能下降,假设数据本身近似随机分布于数据文件中,用顺序I/O来代替随机I/O. 数据随机分布于数据文件的假设在很多实际的应用场景中是难以成立的,从而导致查询结果产生很大误差.提出了动态数据分片在线聚集算法DDPOA(dynamic data-partitioned online aggregation),将整个数据集分片,对各个子数据集独立计算,线性组合子集结果进而得到全集最终结果,一方面降低了在线聚集对整体数据集随机分布的要求,提高了准确性,另一方面动态调整分片数量以改善I/O性能,缩短完成时间.真实系统负载上的实验表明:DDPOA与传统在线聚集相比,在完成时间相差不大的情况下准确性有了大幅提高.
基于文档属性单元松弛的XML近似查询方法
孟祥福, 严 丽, 张文博, 马宗民,
2010, 47(11):  1936-1946. 
摘要 ( 474 )   HTML ( 1)   PDF (1119KB) ( 455 )  
相关文章 | 计量指标
为解决普通用户对XML文档的近似查询问题,提出了一种基于文档属性单元松弛的XML近似查询方法.该方法将XML文档中的叶子结点和属性结点作为属性单元处理,基于一致集的概念导出最大集,生成最小非平凡函数依赖集,从而找出属性单元之间的近似函数依赖关系,进而求出近似候选码和近似关键字.在此基础上,根据属性单元支持度将属性单元按重要程度排列并据此对初始查询条件进行松弛,最不重要的属性单元最先松弛并且松弛程度最大.利用松弛后的查询条件对XML文档进行查询,可得到与初始查询条件近似的查询结果.实验结果和分析表明:提出的XML近似查询方法能够很好地满足用户的查询意图,具有较高的执行效率.
一种处理Skyline查询的有效方法
黄震华, 向 阳, 薛永生, 刘啸岭,
2010, 47(11):  1947-1953. 
摘要 ( 886 )   HTML ( 4)   PDF (787KB) ( 573 )  
相关文章 | 计量指标
skyline查询是近年来数据库领域的一个研究重点和热点.当系统中存在多个不同维空间上的skyline查询时,现有的工作均直接从底层关系表中获取这些skyline查询的结果集.显然,当底层关系表的基数较大且skyline查询的个数较多时,现有方法的处理效率极其低下.基于此,提出一种使用预存储的n个skyline集合{PR\-1,…,PR\-n}来回答用户提交的m个不同维空间上的skyline查询{SQ\-1,…,SQ\-m}的有效方法EAPSQ(efficient algorithm for processing skyline queries).算法充分考虑预存储的skyline集合的编码机制,采用经济学中边际贡献(contribution margin)的概念,使得m个用户提交的skyline查询在n个预存储的skyline集合间的分配达到最佳状态,从而显著提高了处理用户m个skyline查询的效率.实验评估表明,EAPSQ算法具有有效性和实用性.
结合增量与启发式搜索的多目标问题处理方法
魏 唯, 欧阳丹彤, 吕 帅, 殷明浩,
2010, 47(11):  1954-1961. 
摘要 ( 506 )   HTML ( 1)   PDF (921KB) ( 571 )  
相关文章 | 计量指标
提出了一种结合增量与启发式搜索的多目标问题处理方法,设计并实现了一个基于路径扩展方法的多目标增量启发式搜索系统.当问题搜索图中边的权重发生改变或添加删除节点时,该系统通过对搜索现场进行实时的更新,部分利用先前搜索保留的信息,从更新后的状态开始求解新的问题,从而提高了重搜索的效率.对gridworld标准测试样例进行了大量的系统测试,实验结果表明:结合增量与启发式搜索的处理方法能够有效地解决状态格局不断变化的一系列相似的多目标最短路径问题.
SMO算法的简化及其在非正定核条件下的应用
周晓剑, 马义中, 朱嘉钢,
2010, 47(11):  1962-1969. 
摘要 ( 777 )   HTML ( 2)   PDF (899KB) ( 658 )  
相关文章 | 计量指标
SMO算法是求解大型支持向量机(SVM)的有效算法.已有的算法都必须判定4个Lagrange乘子位于哪个象限,从而使算法的实现更为复杂.此外,现有算法都假定核矩阵是正定的或半正定的,因此使其应用受到了限制.考虑到传统算法的不足,提出了一种用于ε-SVR的简化SMO算法,进而将其用于求解非正定核的ε-SVR.与已有的算法不同,通过将ε-SVR的原始规划问题进行展开并求解其KKT条件,提出的算法只需考虑2个Lagrange乘子,从而有效地简化了算法的实现,并能方便地应用于非正定核SVR的求解.采用一个常用于衡量预测误差的函数对算法进行了测试,实验表明,与ε-SVR现有的SMO算法相比,在不增加空间复杂度和时间复杂度的前提下避免了大量繁琐的判别条件,简化了算法的实现,这就为不同的损失函数所对应的SVR提供了一个通用的SMO算法,从而有利于SVR的推广应用.另外,提出的求解非正定核的ε-SVR的方法也为求解其他的非正定核SVR提供了一个思路.
含故障模式的值传递诊断及其完备性讨论
张学农, 姜云飞, 张立成,
2010, 47(11):  1970-1977. 
摘要 ( 469 )   HTML ( 0)   PDF (779KB) ( 530 )  
相关文章 | 计量指标
基于模型的诊断是人工智能领域一个活跃的研究方向.基于值传递的诊断是一种高效的故障诊断方法,但在一般情况下不完备,且系统模型仅描述元件的正常行为.扩充了基于值传递的系统模型,可以描述系统元件的多种故障模式;重新定义了诊断,明确了该模型下得到的诊断与一致性诊断和溯因诊断之间的关系;同时,指出了值传递与真实诊断的关系,为诊断测试提出了新的思路;最后,给出了值传递诊断方法的完备的充分条件,对推进值传递诊断方法的实际应用有积极意义.
基于序贯重点采样粒子滤波和Cholesky分解的分布估计算法
张建华, 曾建潮,
2010, 47(11):  1978-1985. 
摘要 ( 632 )   HTML ( 1)   PDF (859KB) ( 497 )  
相关文章 | 计量指标
连续域分布估计算法一般假设数据服从Gauss分布,而且大多采用了单峰的概率模型,但是对于一些复杂的优化问题,单峰的Gauss分布模型不能有效地描述解在空间的分布.提出一种基于序贯重点采样粒子滤波的分布估计算法,采用带权粒子描述优选集样本服从的概率分布,Cholesky分解法分解收缩的协方差矩阵并利用其产生下一代样本,不需要假设样本服从Gauss分布.算法采用的概率模型是多峰的.变量之间的相关性通过采样时利用群体的协方差矩阵显式地予以考虑,并对协方差矩阵为零矩阵的情况进行了处理.仿真实验结果验证了方法的正确性和有效性.
基于密度聚类的神经模糊系统建模算法
潘维民 何 骏
2010, 47(11):  1986-1992. 
摘要 ( 452 )   HTML ( 1)   PDF (1037KB) ( 456 )  
相关文章 | 计量指标
神经模糊系统经常被用来对非线性系统建模,并能取得很好的效果.以往的模糊系统建模方法存在着输入空间划分个数难以确定和规则冗余的问题,这些问题阻碍了模糊系统的应用.基于动态阈值DENCLUE和相似规则合并的神经模糊系统建模算法DDTSRM(DENCLUE using a dynamic threshold and similar rules merging),首先在DENCLUE算法中使用动态阈值来合并密度吸引子,得到DDT算法.DDTSRM利用DDT算法不依赖初始参数的特点,解决了输入空间划分个数难以确定的问题.因为DDT算法可以得到任意形状和任意密度的聚类结果的特性,所以提高了模糊系统模型的准确性.辨识出模型的初始结构后,DDTSRM通过计算模糊集合之间的相似度来减少规则冗余,使模糊系统模型结构得到优化.最后利用BP算法对系统模型进行训练,进而提高系统的建模精度.以S-Y模糊系统模型为原型,在两输入一输出的非线性函数和Box-Jenkins数据上的仿真实验证明了DDTSRM算法在神经模糊系统建模应用的有效性,能够取得精确的建模效果.
数据密集型计算编程模型研究进展
王 鹏, 孟 丹, 詹剑锋, 涂碧波,
2010, 47(11):  1993-2002. 
摘要 ( 634 )   HTML ( 1)   PDF (1185KB) ( 806 )  
相关文章 | 计量指标
作为一种新兴的计算模式,云计算受到了学术界和产业界的广泛关注.云计算以互联网服务和应用为中心,服务提供者需要存储和分析海量数据.为了能够低成本高效率地处理Web量级数据,主要的互联网公司都在由商品化服务器组成的大规模集群系统上研发了分布式编程系统.编程模型可以降低开发人员在大规模集群上编程的难度,并让程序充分利用集群资源,但设计这样的编程模型面临巨大挑战.首先说明了数据密集型计算的特点,并指出了编程模型要解决的基本问题;接着深入介绍了国际上代表性的编程模型,并对这些编程模型的特点进行了比较和分析;最后对当前所面临的问题和今后的发展趋势进行了总结和展望.
基于被动副版本优先级提高策略的分布式实时容错调度
朱 萍 阳富民 涂 刚
2010, 47(11):  2003-2010. 
摘要 ( 436 )   HTML ( 0)   PDF (873KB) ( 587 )  
相关文章 | 计量指标
FTRMFF(fault-tolerant rate-monotonic first-fit)分布式容错算法具有实现简单、调度开销小的优点,但是副版本的优先级继承策略不利于处理器空闲资源的充分利用.针对这个问题并结合各类型任务的最坏响应时间的分析,提出IPPBS(improving priority for passive backup based scheduling)算法.IPPBS算法能在不破坏处理机上已分配任务的可调度性的前提下,适当提高待分配的被动副版本的优先级来缩短响应时间,增加其在现有处理机上的可调度性,从而提高处理器的利用率.在此基础上,给出了具体的优先级提高因子搜索算法.仿真实验验证了IPPBS算法的可行性和有效性,较FTRMFF算法可节约的处理器个数百分比最高可达13%.
通过交互式移位-插入-删除进行基因组排序的较快算法
郝凡昌 栾峻峰 朱大铭 张 鹏 李 明
2010, 47(11):  2011-2023. 
摘要 ( 511 )   HTML ( 2)   PDF (1387KB) ( 447 )  
相关文章 | 计量指标
多染色体基因组进化问题中常见的重组事件就是移位(translocation),对此已有很多研究成果.但事实上更为普遍的情况是2个基因组包含不同基因,这需要考虑插入和删除事件.对于“通过移位-插入-删除进行基因组排序(简称SG-TID)”这个问题,此前已有一个求解移位-删除(或者移位-插入)序列的近似算法,以及求解SG-TID问题的启发式算法.在给出了移位-插入-删除距离的表达公式后,给出了在增加O(n)存储空间的条件下,O(n\+2)时间内求解该问题的精确算法.该算法比此前给出的算法要快.