计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2009年第06期杂志 文档列表

计算机学报杂志综论

三维模型语义检索研究进展1069-1079

摘要：针对近年来三维模型检索研究不只是考虑形状相似性匹配，而更多地关注如何把语义知识应用于检索这一研究新动态，对三维模型语义检索研究现状，包括三维模型知识提取、语义检索中的主动学习机制、三维模型语义检索系统等方面进行总结．在此基础上，对已有研究成果进行比较分析，突出三维模型语义检索取得的进展以及存在的问题．最后，提出三维模型语义检索需要进一步深人研究的方向．

计算机学报杂志研究论文与技术报告

粗粒度可重构平台中循环自流水硬件实现1080-1088

摘要：循环流水技术运用于粗粒度可重构体系结构可带来显著性能提升．循环控制、流水线同步和存储器有效利用是其中的关键问题．文中介绍了在粗粒度可重构体系结构LEAP上循环自主流水化的硬件实现．该方法基于支持循环迭代自动调度的控制部件、数据驱动ALU和可配置静态交换路由．利用动态调度循环中操作的优势，LEAP可发掘更高的程序并行度；分布式存储访问和高效数据重用则提高了带宽利用率．实验结果表明，相对于通用处理器，LEAP有13．08～535．65倍的性能提升．

核心循环到粗粒度可重构体系结构的流水化映射1089-1099

摘要：粗粒度可重构体系结构为数据密集型应用提供了灵活性和高效的解决方法，而应用中的核心循环消耗了程序的大量执行时间，满足核心循环在CGRAs上实现的性能／开销的严格约束仍旧是个重大难题．针对已有工作在研究映射核心循环到CGRAs上的不足，文中提出一种新颖的核心循环自动流水映射到粗粒度可重构体系结构上的方法．文中形式化了核心循环到CGRAs的流水映射问题，阐述了CGRAs的资源共享和流水方法，定义了其循环自流水CGRAs体系结构模板，并给出核心循环流水映射方法．实验结果表明，与已有的先进的方法相比，文中方法的资源占用率降低16．3％、吞吐量提高169．1％．

基于同构多核处理器的H．264多粒度并行编码器1100-1109

摘要：H．264码率低和视频质量高的优越性能以增加编码计算的复杂度为代价，如何开发适用于多核处理器平台的并行编码算法是提高其编码速度的重要研究内容，对于满足高清视频实时传输和大规模共享具有十分重要的意义．利用H．264开源编码器项目X264，在片级和数据级并行编码算法的基础上，通过分析图像帧之间的参考关系，提出并实现了B帧个数可变的帧级并行算法；根据宏块之间的参考关系，设计了一种类似流水线的宏块级并行方法；基于Intel同构多核平台，提出融合帧级、片级、宏块级和数据级4种不同粒度的并行编码方案，开发了H．264多粒度并行编码器．实验结果表明，在码率增加不大的情况下，H．264多粒度并行编码器可以很好地提升编码加速比，视频编码质量符合高质量的要求．

无界模型检验中融合电路信息的SAT算法研究1110-1118

摘要：针对从电路转化而来的SAT问题，通用SAT求解器存在一个缺陷——电路互连信息的缺失，这是造成很多无关推导的根源．文中提出了一个统一的基于CNF数据结构的电路SAT无界模型检验框架．首先作者提出了定值子句的概念，利用这一概念可以在CNF结构中保存电路的互连信息，在搜索过程中更早地识别可满足解，减少不必要的搜索．其次，文中提出了在CNF结构上的状态变量赋值精简方法，摆脱了以往基于SAT的无界模型检验中这一步骤对门级电路结构的依赖．实验数据表明，利用文中方法进行前像计算能够取得明显的加速．同时，文章比较了两种搜索顺序在多时帧搜索中的效果．实验结果表明利用文中方法可以验证传统模型检验方法难以验证的复杂电路属性．

一种基于指针逻辑的代码安全属性分析方法1119-1125

摘要：在分析和总结前人工作的基础上，提出了一种改进的代码安全属性验证方法．该方法在利用传统的源代码安全属性验证工具的基础上，加入了指针逻辑，针对现有代码属性分析技术只能对C语言子集进行分析验证的不足，利用指针逻辑对源代码的分析结果对源代码中的指针进行替换，从而避开了传统静态代码属性验证工具对指针处理功能太弱的瓶颈，可以实现对C语言中的部分指针及运算进行处理．

MANET节点不相交多路径安全源路由协议1126-1133

摘要：多路径路由实现是移动Adhoc网络（MANET）可靠运行的有效保证．现有MANET节点不相交多路径路由协议主要关注节点不相交多路径的可实现性和效率问题．针对节点不相交多路径路由协议MNDP协议在主动攻击者安全模型中的安全缺陷，提出了可证明安全的MANET节点不相交多路径动态源路由协议——SMNDP协议．SMNDP协议路由请求算法中，建立了中间节点路由请求消息传播策略的检错机制，SMNDP协议路由应答算法中建立了消息防篡改机制和身份认证机制．基于攻陷的网络拓扑模型，扩展了可模糊路由概念，提出了多路径可模糊路由集合概念和节点不相交多路径源路由协议的安全定义，并应用于SMNDP协议的安全分析．SMNDP协议的安全性可以归约为消息认证码和签名机制的安全性．

多重周期二元序列的联合k错2-adic复杂度1134-1139

摘要：具有较强密码学性质的序列应该具有较大的2-adic复杂度，以抗击已知的带进位操作反馈移位寄存器综合算法，同时改变较少的几项也不应引起序列的2-adic复杂度的急剧减小，即k错2-adic复杂度也应尽可能地大．近来，向量化流密码的设计逐渐成为国内外密码学界关注的一个重要方向．对这种类型的流密码的安全性分析需要研究多重序列一有限多个序列的并行流的复杂度．目前对多重序列的复杂度研究多集中于线性复杂度．基于此，文中首先给出了多重二元序列的联合k错2-adic复杂度的定义．随后，借助数论中的中国剩余定理等相关理论给出了联合k错2-adic复杂度的下界，并讨论了具有最大联合2-adic复杂度以及较大联合k错2-adic复杂度的N周期序列的存在性及具有此种性质的序列的数目下界．以此种周期序列作为密钥流序列可以有效抵抗穷举攻击．

基于简单反馈的混合静态／动态节能弱硬实时调度算法1140-1146

摘要：随着能耗问题日益显著，节能实时调度成为实时调度领域研究的热点．由于混合静态／动态节能弱硬实时调度算法基于最坏情况执行时间计算任务的执行速度，因此限制了节能效果，文中针对这一问题，提出一种新算法，通过引入简单反馈机制，估计任务的实际执行时间，通过任务划分，降低任务的整体执行速度，延长执行时间，进而达到高效节能的目的．实验表明，当平均情况执行时间低于最坏情况执行时间较多时，新算法优于原始算法，最多可节能60％～70％，最少可节能约10％．算法的不足之处在于当平均情况执行时间接近最坏情况执行时间时，新算法比原算法更耗能．

基于缺陷均匀分布的互连线间耦合电容分析1147-1151

摘要：互连线的寄生效应是制约深亚微米VLSI电路实现高速、高密度的关键因素．文中分析了集成电路制造过程中的工艺缺陷对互连线间寄生电容的影响，给出了考虑缺陷等因素的线间寄生电容模型．模拟结果表明，导电冗余物缺陷明显增加了线间寄生电容，从而对电路的可靠性有较大影响．

一种基于分层率失真优化的容错性视频转码算法1152-1161

摘要：容错性视频转码能够在已压缩视频流中嵌入容错性工具，以增强视频流面向无线信道的抗误码能力．但是容错性工具的嵌入在降低失真的同时也会增加码率，因此需要进行率失真优化．针对这一问题，文中提出了一种基于分层率失真优化的容错性转码算法．该算法通过在帧层和宏块层分别对重同步标记的插入和帧内宏块的刷新进行不同粒度的优化来提高算法的灵活性，通过在帧层考虑帧内宏块刷新、帧内预测和运动矢量预测的影响来提高算法的精确性，通过在宏块层减少候选模式的数量来降低算法的复杂度．实验表明，该算法与基于单层率失真优化的算法相比，信噪比可获得0．6～1．1dB的增益，复杂度最多可降低25％．

一种基于运动信息描述的视频格式自适应方案1162-1171

摘要：多媒体应用领域存在多种视频编码标准，因此实现不同视频格式之间的自适应转换具有重要意义．该文提出了一种新颖的基于运动信息描述的视频格式自适应解决方案．该方案利用作者前期提出的基于H．264／AVC标准的运动信息描述算法提取能够复用的详细完备的运动信息，根据需要快速生成不同视频编码格式、多种码率的码流；也可以利用此运动信息，指导不同视频格式码流之间的快速自适应转换．作为该方案的具体应用，文中提出了一种针对H．264／AVC标准和MPEG-2标准的视频自适应方法．实验结果表明，文中提出的基于运动信息描述的视频格式自适应解决方案不仅可以很好地保证编码性能，同时具有较低的计算复杂度．

基于空盒自适应生成的动态场景光线跟踪计算1172-1182

摘要：提出了一项光线跟踪新技术，能有效提高光线在空白区域的行进速度．该技术首先用一种新方法创建均匀空间网格，然后用较少的空盒自适应聚集空的空间网格，以加快光线跟踪的计算．新加速结构的创建时间复杂度和空间复杂度均是O（n），而相应的光线跟踪计算的时间复杂度为O（logn），与kd树结构相当．当该结构与已有的一些加速结构结合后，能很好地处理大规模动态场景．比如，光线逐根跟踪且计算二次衍生光线时，新技术可在普通PC机上高真实感地交互绘制包含6G三角面片的多Buddha动态场景．

基于面壳封闭的B—rep模型分解方法1183-1195

摘要：三维实体B—rep模型分解是B—rep表示转换为CSG表示的关键问题，并且对深入分析CAD模型的几何形状及其结构关系具有重要意义．文中提出一种基于面壳封闭的方法分解B—rep模型，该方法采用先分割后缝合的策略．首先识别模型中的所有切割环，然后通过切割环将B—rep模型分割成多个面壳，最后利用切割环在面上的收缩将面壳封闭成实体．经过上述3个步骤，可以将具有二次曲面的B—rep模型有效地分解为加体和减体的组合，同时实验表明该方法具有较高的计算效率．

结合图像细节特征的全局优化纹理合成1196-1205

摘要：提出了一种结合图像细节特征的全局优化纹理合成算法．作者利用非线性分解方法获取纹理细节作为特征图，将其作为纹理图像一个新的信息通道来引导纹理合成．联合图像细节信息通道和颜色通道，在图像上建立了一个全局的纹理合成能量方程，采用最大期望值算法迭代优化求解出一个全局的能量最小值．在全局优化算法中，构建样本纹理和待合成纹理之间的各个信息通道直方图匹配算法，进一步提高纹理合成的质量．文中同时给出了结合细节特征的图像和视频纹理合成算法，实验结果表明，文中的方法较好地解决了纹理合成中合成的纹理图像结构不连续或特征结构容易断裂等问题．

一种隐式曲面交互调整的新方法1206-1213

摘要：提出了一种对隐式曲面形状进行交互调整的新方法，为隐式曲面的调整提供了两种交互工具，分别是对曲面上点的位置调整和法向调整．该方法以调整后的位置和法向为新曲面的插值条件建立目标函数，极小化该目标函数求解曲面参数的变化量，从而确定新的隐式曲面．文中采用拟牛顿法和序列二次规划法（SOP）求解该非线性优化问题．在调整过程中用粒子的方法对隐式曲面进行绘制，实现了对隐式曲面形状的实时交互调整．最后用实例说明了新方法的有效性．

用改进的散射搜索法求解带平衡约束的圆形Packing问题1214-1221

摘要：以卫星布局为背景的带平衡约束的圆形Packing问题属NP难问题．该文用给出的改进的散射搜索方法求解．一是给出基于极坐标变换的散射搜索多样性生成策略，二是采取基于极角和极径差异度的参考集更新策略，三是用梯度下降法和Nelder-Mead直接搜索法分别作为散射搜索法中不同阶段所产生新解的改进方法，从而构成改进的散射搜索法，提高了散射搜索法的探索和搜索能力．数值实验结果表明了该改进散射搜索法的可行性和有效性．

基于粒子Mean Shift迁移的红外人体目标跟踪算法1222-1228

摘要：提出了一种基于粒子Mean Shift迁移过程的红外人体跟踪方法．算法通过采样粒子迁移和聚类动态建立目标的状态模型和量测模型．在被跟踪区域随机布撤粒子，以各粒子对应像素的亮度作为特征值进行Mean Shift收敛性分析，使用收敛后的粒子集表达目标的当前状态；以状态粒子的坐标位置为特征值对其进行Mean Shift聚类，作为对目标的量测．连续跟踪时，下一帧的采样粒子基于上一帧的量测结果产生．与传统的基于序贯重要性采样的粒子滤波方法相比，算法不需要目标的相似性测度计算，仅用少数粒子即可实现对目标的可靠跟踪．