基于KD树的海量图像匹配技术

针对海量图像匹配的速度瓶颈问题,提出一种结合图像SIFT特征和KD树搜索的图像匹配算法,并建立了适应有限内存环境的大型KD树混合存储模式。实验结果表明,该方法能显著提高图像搜索速度和图像库的可扩展性,查准率和查全率也明显高于其他搜索方法。     

结合K均值聚类和KD-Tree搜索的快速分形编码方法

利用部分失真搜索求解传统K均值聚类算法中的最近邻搜索问题,显著地减少了传统算法的乘法次数,从而提高了聚类速度;然后用改进后的聚类算法来加速分形编码：首先将定义域块聚类并为每个类建立一棵KD-Tree,编码时对每个值域块先后用部分失真搜索与近似最近邻搜索得到与其距离最近的若干KD-Tree及其上的若干最近邻,而其最优匹配块即由后者产生.实验结果表明,相对于全局搜索,该方法能大幅度地提高编码速度和较大地提高压缩比,而解码质量只有很小的下降;相对于同类方法,在相同压缩比下有更好的加速效果和解码质量.     

基于OpenCL的实时KD-Tree与动态场景光线跟踪

目前,基于GPU或多核CPU加速的光线跟踪算法是与硬件相关的.研究具有跨平台性能的实时光线跟踪算法既具有挑战性,又具有很强的应用价值.为此,提出一种基于OpenCL并且跨平台的动态场景实时光线跟踪绘制算法.首先通过对通用GPU并行处理性能进行发掘,将光线跟踪中KD-Tree建立、场景遍历和绘制3个过程均设计在GPU上,而CPU只负责其中各过程的调度,从而充分利用了GPU的计算性能,并有效地降低了数据传输开销;通过设计并行分区、并行SAH、紧密的数据管理以及区间性叶结点存储等算法,在GPU中高效、高质量地建立动态场景的KD-Tree,同时高质量的KD-Tree也有效地加速了场景的遍历速度.该算法以广度优先和大规模并行模式建立K D-Tree,更具通用性,既可以运行于NVIDIA GPU(CUDA GPU),也可以运行于AMD GPU.实验结果表明,文中算法可以在NVIDIA GPU和AMD GPU上对中等规模的动态场景实现实时光线跟踪绘制.     

改进SURF特征的维吾尔文复杂文档图像匹配检索

针对图像局部特征的词袋模型（Bag-of-Word,BOW）检索研究中聚类中心的不确定性和计算复杂性问题,提出一种由不同种类的距离进行相似程度测量的检索和由匹配点数来检索的方法。这种方法首先需要改进文档图像的SURF特征,有效降低特征提取复杂度;其次,对FAST+SURF特征实现FLANN双向匹配与KD-Tree+BBF匹配,在不同变换条件下验证特征鲁棒性;最后,基于这两种检索方法对已收集整理好的各类维吾尔文文档图像数据库进行检索。实验结果表明:基于距离的相似性度量复杂度次于基于匹配数目的检索,而且两种检索策略都能满足快速、精确查找需求。     

Rao-Blackwellized滤波器实现机器人同时定位和地图创建

为了实现移动机器人仅依靠单目视觉和里程计创建可靠地图,本文提出了基于Rao-Blackwellized粒子滤波器的同时定位和地图创建方法.文中建立了鲁棒的运动模型和感知模型;通过有效的尺度不变特征变换方法提取环境特征,并采用基于KD-Tree的高维特征点最近邻快速搜索算法实现特征匹配;通过对匹配对的三维重建创建了密集的空间三维自然路标.实际实验表明本文方法能创建较高精度的地图.     

基于空间分割的局部KD树动态构建算法

由于点云数据是大量的散乱的没有任何拓扑关系的数据,文中引入KD树,并对其做了相应改进,使得能动态的构建局部KD树。实验结果表明,所提出的基于空间分割的局部KD树动态构建算法既保证了准确性与搜索效率,又具有比较满意的空间复杂度。     

基于KD-Tree搜索和SURF特征的图像匹配算法研究

针对图像匹配时进行特征检测和匹配的搜索时间长的问题,文章研究了基于KD-Tree搜索和SURF特征的图像匹配算法。该算法首先提取得到图像的SURF特征并生成特征描述向量,然后为这些特征描述向量建立KD-Tree索引,最后通过计算每个特征点的与其距离最近的若干个KD-Tree上的最近邻点,完成特征匹配工作。实验结果表明,与SIFT算法相比,SURF算法进行特征检测的速度要快2～3倍;与全局最近邻搜索相比,基于KD-Tree索引的近似最近邻搜索大大减少了计算量,较大地提高了SURF算法的匹配速度。     

有序的KD-tree在图像特征匹配上的应用

针对用KD-tree实现高维空间点匹配中存在的错误匹配问题进行讨论,分析其存在的原因;接着,使用PCA,根据各维数之间的协方差,求出它们的主成分奉献率,再按主成分奉献率进行维数优先级排序,并在该基础上增加了KD-tree各节点的权重;最后,将改进前后的KD-tree应用于Sift特征点匹配。实验证明,改进后的KD-tree能在保持实时性的前提下,大大提高匹配的准确率。     

高效KD树并行算法优化

KD树作为一种用于查询高维键值的流行算法, 由于其准确性高、可扩展性强与较快的查询速度而应用于多媒体检索领域, 但缓慢的建树效率已不能很好的满足当前的应用场景. 针对KD树的低效建树过程, 作者探寻并分析了KD树建树现存的并行潜能并提出了一种面向KD树建树过程的多核并行算法—ParK(Parallel KD-Tree). ParK探求了不同的并行模式来充分利用现代硬件中的计算资源, 并在此基础上提出了一种新的内存分配策略来解决并行处理中的数据争用状况. 实验结果表明Park相比于原始串行版本最高能够在16核的服务器上达到21.75倍的加速.