图像拼接
1542012,48(34)ComputerEngineeringandApplications计算机工程与应用
用分支限界策略可以提高搜索效率。论文采用基于
k-d树(k-dtree)的最近邻搜索算法,可以将特征检索的时间复杂度降低到O(mlbn)。当特征点数目较多时,搜索效率的改进还是比较显著的。
的初始位置指针和特征点数目。
(6)以划分后的左边特征点集和左孩子结点为输入,递归调用算法1;以划分后的右边特征点集和右孩子结点为输入,递归调用算法1。
3.1k-d树的生成算法3.2基于k-d树的最近邻搜索
如前所述,在k-d树中进行数据的k最近邻搜索
k-d树[9]是由二叉搜索树(BinarySearchTree,BST)扩展而来的一种特殊的检索树,其中k表示有k个维度(dimension),在数据挖掘和光线跟踪[10]中有着广泛的应用。它是一种空间划分数据结构,所有非叶子节点可以视作用一个超平面把空间分割成两部分。在超平面左边的点代表结点的左子树,在超平面右边的点代表结点的右子树。假设对一幅图像检测得到的特征点存储在一个顺序数组里面,对数组中的元素的顺序不作要求,那么k-d树的每个节点的结构可以表示如表1。
表1k-d树结点结构
字段名featurekikvleftright
类型指针整数整数kd-treekd-tree
描述
指向特征点集的指针
划分序号划分中值左子树右子树
是特征匹配的重要环节,其目的是检索在k-d树中与待查询点距离最近的k个数据点。而最近邻搜索是k最近邻搜索的特例,也就是1近邻。下面阐述基于
k-d树的最近邻搜索算法。
算法2基于k-d树的k最近邻搜索输入:带查询特征点和算法1的输出k-d树输出:与待查询特征点欧式距离最近的k个特征点(1)建立一个k维数组,用于存储待查询特征点欧式距离最近的k个特征点。
(2)从根节点出发,比较待查询特征点和划分结点的划分维ki的值,如果小于等于就进入该结点的左子树分支,如果大于就进入右子树分支。
(3)递归遍历,一直到叶子结点,也就是与待查询点处于同一个子空间的叶子结点;计算该结点与待查询特征点的欧氏距离,并将该叶子结点指向的特征点放入到维数组中,作为候选结点。
(4)回溯搜索路径,并判断搜索路径上的结点的其他子结点空间中是否可能有距离查询点更近的数据点。如果有可能,则需要跳到其他子结点空间中去搜索,并将其他子结点加入到搜索路径中。
(5)计算遍历到的叶子结点和待查询结点之间的欧式距离,并和维数组中已经保存的结点进行比较,如果小于,则放到相应的位置;如果大于,则放弃。
(6)重复这个过程直到搜索路径为空。
算法1通过递归构建一棵k-d树
输入:检测到的特征点集输出:k-d树(1)如果特征点集不为空,则创建一个k-d树的结点,作为根结点,并包含指向特征点集起始位置的指针和特征点数目。
(2)如果该k-d树结点指向的特征数量为0或者1,则表示这个结点是叶子结点,直接返回。否则计算特征点在每一维的方差,将方差最大的维数赋值给ki,作为划分的序号。
(3)对每个特征点在第ki维的分量进行选取中值计算,以在第ki维的分量是中值的特征点作为划分基准点。
(4)以基准点对特征点集进行划分,将第ki维分量小于等于基准点对应分量的特征点移动到基准点的左边,将第ki维分量大于基准点对应分量的特征点移动到基准点的右边。
(5)如果所有特征点都位于基准点的同一侧,则令这个k-d树的结点为叶子结点,然后返回。否则创建两个新的k-d树结点,一个为已经创建结点的左孩子结点,并包含有指向划分后左边特征点集的初始位置指针和特征点数目;另外一个为已经创建结点3.3RANSAC鲁棒参数估计
基于k-d树最近邻搜索得到的匹配点集中还会
有错误的匹配点对,本文使用RANSAC(Random
[11-12]
SampleConsensus)算法对匹配结果进行进一步
求精,并对图像之间的变换参数进行鲁棒估计。在使用RANSAC算法进行图像变换参数估计的时候,需要从候选匹配点集中随机选择最小的匹配点对,并使用直接线性变换(DirectLinearTransformation,DLT)算法计算图像之间的变换矩阵。最小匹配点对的数目取决于待匹配图像之间的几何变换模型,本文使用的最小匹配点对为4。
4图像融合
CmueniergnApitn 计算机工程 与应用 optEgnei dplaisrnaco @ 图形 、 图像 、式识别@ 模 多幅图像 的 自动拼接 算法研究 赵毅力 ZHAO i Y1i 西南林业大学 计算机...
而且该算法能够实现多 幅图像自动排序和配准,稳定性好,无需人工干预.最后,对此次 研究工作的内容进行了总结,并对下一步的研究工作和图像拼接领 域的未来发展进行...
一种图像拼接算法研究_计算机软件及应用_IT/计算机...全局配准是消除多幅 图像拼接到一起的误差累积以...一种自动全景拼图的快速算法,计算机研究与发展,38(5...
基于特征点匹配的图像拼接算法研究_IT/计算机_专业...图 ,广泛应用于虚拟现实和计算机视觉 等多个领域 ...1 特征点的自动提取 设待拼接的左 、 右两幅图像...
一种序列图像的自动拼接算法 张汗灵 张敏贵 刘庆云...视觉、计算机图形学、图像 处理等领域的重要研究课题...本文基于多分辨率样条方法[5] 提出了一 种新的...
基于全景图像的拼接算法研究_信息与通信_工程科技_...试验证明,此 方法在全景图像的生成中具有自动拼接、...利 用两 幅图 像间 的边 界重 叠 部分进 行...
基于比值法图像拼接算法研究_IT/计算机_专业资料。...现实等多个领域中 .而要实现图像 的拼接 , 就要...一种图像自动拼接的快速算法 [J ] . [ 2 ] 张...
3. 1 多幅图像的匹配关系 对于输入的无序图像, 本文采用 Bro wn M 提 出... 全景图自动拼接算法研究... 60页 免费 改进的全景图拼接融合算... 暂无评价...
遥感图像拼接算法的研究_IT/计算机_专业资料。全景...因此 ,多幅遥感图像的拼接处理技术成为地理科学中...基于轮廓相位相关的图像自动拼接 [ J ]. 大连理工...
图像拼接系统算法研究及实现_IT/计算机_专业资料。...讨论了全自动图像拼接系统所需要的技术细节和实现方法... 这样的情况可以认为符合照相机平移拍摄多幅图像的...
热门文档