摘要:特征匹配是计算机视觉和图形图像处理领域中很多研究方向的基础，也是当前的研究热点.SIFT（scaleinvariant feature transformation）特征因其具有尺度、旋转不变性，对一定范围的仿射及视角变换具有鲁棒性等优点，自Lowe提出后，10多年来一直受到众多研究人员的关注.匹配的快速性和准确性是很多应用对特征匹配的要求，如三维重建中立体图像对（stereo pairwise image，简称SPI）的匹配.针对这一问题，以SIFT特征为基础，提出用于SPI匹配的方向大约一致（approximately consistent in orientation，简称ACIO）约束关系，其描述了SPI的匹配特征向量间的空间位置关系，有效地避免了误匹配的发生，提高了匹配的精度；通过对标准K-d树（standard K-d tree，简称SKD-tree）结构的分析，提出了层次结构K-d树（hierarchical K-d tree，简称HKD-tree），将SPI特征集根据ACIO约束关系划分成层次结构并建立映射，该方法缩小了搜索空间，从而达到加速匹配的目的.在ACIO和HKD-tree的基础上，提出了高效、快速的匹配算法.实验结果表明，所提方法比SKD-tree方法和最新的级联哈希方法（cascade hash，简称CasHash）在精度上略占优势，但在匹配速度上比SKD-tree快一个数量级以上，同时也数倍于CasHash.

摘要:投影四面体法是四面体体数据可视化的一种重要方法.为了保证绘制结果准确,每一帧都需要对所有四面体按照遮挡关系进行排序,然而四面体之间强烈的依赖性不仅导致排序效率很低,而且很难并行实现.提出了一种基于K-D树空间划分的快速精确的四面体排序策略,在每个叶节点内逐层并行提取互不遮挡的四面体,层与层之间自然有序,且各叶节点的操作彼此独立进行.最后将结果按照叶节点之间的空间遮挡顺序组织在一起.通过两个级别的并行,在保证精确排序的同时极大地提高了效率,且数据结构易于图形处理单元GPU实现.实验结果表明,基于K-D树快速精确排序策略的GPU 实现极大地缩短了排序时间.

摘要:提出了一种适用于交互式动态场景光线跟踪的高质量k-D树构建算法.结合基本的k-D树遍历代价函数和场景一般具有较均匀分布的特征,推导出合理表示节点中连续分割面遍历代价的计算公式.在计算过程中将待划分节点包围盒划分成均匀子空间,采用直接求解函数解析解的方式进行节点分割面计算.为了保证各种光线跟踪应用中较高的渲染效率,提出了不同情况下合理的空间划分数量计算函数.实验结果表明,该算法适用于各种不同图元分布的场景k-D 树构建,并可以应用于整个构建过程,效率有了很大的提升,同时构建结果保持了与最优划分相近的质量.

摘要:提出了一种快速而鲁棒的点模型布尔运算算法.在进行布尔运算之前,首先将点模型中的每个点表示成具有一定半径的面元,并确定它相对于另一个模型表面的内、外及相交关系;然后对相交面元进行全局误差控制下的自适应加密重采样,以求取交线;为了加速面元的内、外及相交关系的检测,对每个模型建立层次结构k-d树.实验结果表明,该方法对于具有不同分辨率以及采样不均匀的点模型也能进行稳定可靠的布尔运算.

摘要:多维时间序列是信息系统中一类重要的数据对象,相似搜索是其应用的一个核心.两个序列(子序列)相似度加以比较的常用方法是:将序列(子序列)转换成空间中的曲线,然后计算曲线间的欧几里德距离.这种方法的主要缺陷是它仅考虑了序列(子序列)间的整体距离关系,而不能体现它们自身的局部变化.针对此问题,提出了一种新的可应用于多维时间序列的快速相似搜索方法.该方法将序列(子序列)的局部变化特性与检索结构(k-d树)结合起来,使得在搜索k-d树的同时实现了序列(子序列)的局部变化匹配,从而极大地提高了查询效率和正确率.实验结果表明了算法的有效性.