平面点匹配的一点校准算法

点模式匹配是一项重要的视觉课题。对于一个平面点集,由平移和旋转并伴有一定噪声作用产生另一点集,提出一个基于一点校准的点模式快速匹配算法,并推广到带有属性点的匹配问题中。基于一点校准的点模式匹配算法,其计算复杂性为O(mn),其中m,n分别是两个点集所含点的个数,比基于两点距离近似相等的校准匹配算法,其计算复杂性为O(m2nl)(其中l为第二个点集中与第一个点集中任两个点的距离近似相等的平均个数),极大地减少了计算量。     

平面线段集三角剖分的算法

本文提出了计算平面线段集三角剖分的两种算法，第一个算法是利用平面扫描的思想，当扫描线达到事件点时，处理事件点，即将事件点与已被扫描的某些点连接，这样便将已扫描的区域三角剖分，当扫描线达到最左边的事件点时，处理该事件点，就完成了平面线段集的三角剖分，第二个算法基于逐层计算凸壳，并将凸壳改变为多边形，这样便便形成嵌套的多边形层，这些多边形覆盖线段集凸壳内的区域，然后三角剖分每个多边形，即完成平面线段集的三角剖分，两个算法的时间复杂性分别为O（nlogn),O(mnlogn)，其中n为线段集中线估的数目，m为凸壳的层数。     

仿射变换中点匹配的筛选基的对准算法

点模式匹配对准算法的基本思想是在两个点集中各选择不共线的3个点,唯一确定一个仿射变换,该变换作用于第一个点集中的所有点,用变换后的点集与第二个点集进行比较,检验变换的正确性,但尝试所有3点组合的计算代价太大。文章基于仿射变换的最小方差的参数估计以及数值计算的稳定性,对两个点集中参与匹配的基进行筛选,来确定匹配点对,并可极大地减少计算量。     

一个改进的用于流体界面追踪的等值面法

提出了一个改进的O(n)的多点匹配方法用于流体界面追踪。新的方法和快速匹配方法(FMM)一样，都是基于窄带的方法。与FMM不同的是，它不需要对窄带中的点进行排序，也不是逐点更新窄带上的网格点，而是应用一个多点调整的策略来同时更新一组网格点。二维、三维的数值实验表明了本方法的有效性。此方法已应用于动态虚拟环境中的流体界面追踪中。     

一种基于Laplacian矩阵的图像匹配算法

文章提出了一种基于Laplacian矩阵的图像特征匹配算法。首先分别构造两幅图像特征点集的Laplacian矩阵,并对这两个矩阵进行奇异值分解(SVD),然后利用分解的结果构造出一个反应特征点之间匹配程度的关系矩阵,最后根据关系矩阵实现两幅图像的特征点匹配。大量实验结果表明,该文所提出的算法具有较高的匹配精度。     

面向IP地址集过滤的高效包分类技术

针对传统防火墙线性匹配算法匹配效率低、维护困难等问题,提出并实现了一种面向IP地址集过滤的高效、灵活的Netfilter扩展框架Salist。 Salist包含一个基于内核虚拟文件的表管理模块,一个可自动对IP地址集进行去重、归并和排序的表内规则管理模块,一个基于Bsearch算法的高效的包匹配模块。通过理论分析和实际测试证明, Salist使包匹配算法时间复杂度由传统线性匹配的O( n)降低为O( log n),规则合并减少了规则表占用的内核内存空间10%以上,按文件分离的规则管理机制简化了对规则集进行维护的难度。结果表明Salist使用在核心网络设备中可极大提高包转发速率,降低规则的内存占用和管理难度。     

基于积极集策略的最小闭包球问题算法研究

首先,基于每次迭代计算距离当前球心最远的两个点,提出一种求解n维空间中m个点的最小闭包球问题的(1+ε)-近似算法.对于ε∈(0,1),建立了该算法的核心集大小和计算复杂度,分别为O(1/ε)和O(mn/ε).然后,给出一种积极集策略,每次迭代计算距离当前球心最远的N个点.将该策略结合到提出的算法中,得到一个基于积极集策略的算法.最后,实验结果表明基于积极集策略的算法能够快速、有效地求解m》n的大规模数据集的近似最小闭包球.     

一种基于柱面投影的图像拼接算法研究

全息实景图像是近来出现的一种采用基于图像绘制方法再现了真实的三维场景的交互式虚拟现实技术.本文提出了一种基于柱面投影的全景图像拼接算法,采用Scott算法结合颜色特征直方图进行特征点匹配,从两组100个特征点集中匹配出18对匹配点,经过检验匹配无误,证明了该算法具有较高的匹配精度和较强的适应性和鲁棒性.     

基于概率图模型的点集匹配方法研究

在概率图模型框架下提出了一种将回归分析和聚类分析相结合的贝叶斯点集匹配方法,其中,回归分析用来估计两个点集之间的映射函数,而聚类分析用来建立两个点集中点与点之间的对应关系.本文将点集匹配问题表示为一种多层的概率有向图,并提出了一种由粗到精的变分逼近算法来估计点集匹配的不确定性;此外,还利用高斯混合模型估计映射函数回归中的异方差噪声和场景点密度估计中离群点的分布;同时,引入转移变量建立起模型点集与场景点集之间的关系,并与离群点混合模型共同对场景点的分布进行估计.实验结果表明,该方法与其他点集匹配算法相比,在鲁棒性和匹配精度方面均达到了较好的效果.     

一种确定点集最远点对的最优算法

提出了一种确定点集最远点对的最优算法.对平面内n个点的点集,在求出其凸包后,利用求对跖点对的方法确定凸包的最远点对,从而得到点集的最远点对.整个算法的时间复杂性为O(nlogn).     

存储最优的连续MAX查询方法

考虑滑动窗口数据流上的连续MAX查询问题,提出了一种存储最优的方法.该方法只需保存数据集中可能成为极大值点的部分数据(候选点集),而将所有完全不可能成为极值点的数据进行丢弃,从而可以有效降低存储开销;提出了一个动态维护候选点集的方法,当数据独立分布时,处理一个新到数据所需的时间为O(1og N),处理数据失效的时间开销为O(1),其中N为滑动窗口包含的全部数据数目.理论分析和实验结果表明了该方法能够适应流速很快的场景,具有较高的效率.     

汉诺塔非递归算法研究

汉诺塔(Tower of Hanoi)问题是求在三个柱子之间移动圆盘的方法,它是递归程序设计的经典例子,已经证明其时间复杂度下限是O(2n),空间复杂度是O(n),实际使用时很容易溢出.给出汉诺塔问题的两个非递归算法:解集递推法和解集树法.解集递推法的时间复杂度和空间复杂度都是O(2n),该算法空间复杂度很大,无法实际使用,提出该算法的目的是为了引出解集树法.解集树法可以计算出指定的任意一步移动方法,时间复杂度和空间复杂度分别是O(n*2n)和O(1).并证明了汉诺塔问题的空间复杂度下限是O(1).     

一种体视显微图像误匹配消除方法

针对尺度不变特征变换( SIFT)匹配中存在的误匹配问题和立体图像特点,提出一种误匹配消除方法。对体视显微图像进行SIFT特征匹配初步得到匹配对,结合体视显微镜标定参数,计算三维点云坐标。将三维点云分别投影到左、右图像中得到新的匹配对,新投影点的图像坐标分别与原来匹配点的图像坐标相减,生成投影向量集。通过左、右2个投影向量集幅值和方向的异常值剔除,实现误匹配消除。实验结果表明,实验图像的误匹配消除率达到100%,同时不消除正确匹配点,提高了匹配精度。     

平面点集凸壳的实时算法

本文提出平面点集凸壳的实时算法。该算法利用平衡二叉树来代表凸壳的顶点序列,使每次更新凸壳所需计算复杂度为O(log m)。因而n个点的凸壳的计算复杂度为O(n log m),空间复杂度为O(log m),当点服从均匀分布时,算法期望的计算复杂度为O(n)。     

一种新的立体匹配算法

立体匹配是目前计算机视觉领域中最活跃的研究主题之一,在三维重构、对象识别与分类、图像对齐等应用中,立体匹配都是一个关键步骤.为了能够更精确地对特征点进行匹配,给出了一个新的匹配约束条件:匹配点距离相关性约束,据此提出了一种新的立体匹配算法.该算法独立于特征点的检测算法,首先使用灰度相关法进行初始匹配,然后利用最小中值平方法获得部分正确匹配点集,在此基础上加入匹配点距离相关性约束进行引导匹配,得到最后的匹配点集.实验表明,该算法能够很好地实现特征点的正确匹配.具有很高的使用价值.     

二分图最大匹配问题的分布式算法

本文基于异步通讯网络,对二分图最大匹配问题,建议了两个分布式算法。其中第一个简单算法的通讯复杂性为O(n(n~2+m))、时间复杂性为 O(n~3);第二个算法的通讯复杂性为O(n~(1/2)(n~2+m))、时间复杂性为O(n~(5/2)),这里n和m分别为二分图的结点个数及边的数目。关于这一问题的分布式算法目前尚未见诸报导,这里建议的算法很可能是此问题的第一个分布式算法。     

一种基于特征点三维信息的自然路标提取与快速匹配方法

自然路标提取与匹配是vSLAM的基础.文中提出了一种基于特征点三维信息的自然路标提取、局部特征描述与快速匹配方法.采用双目视觉获取环境图像,提取左右目图像的特征点,并进行匹配.建立左摄像机坐标系下的每个匹配点的三维信息,提出视场约束规则对特征点进行过滤.在此基础上基于改进的MeanShift聚类算法进行自然路标提取.提出一种路标描述符,可以快速进行两个聚类的匹配.该方法可以有效提取非结构化环境中的自然路标,对机器人位姿估计精度要求较低.     

可重构造网孔机器上最小生成森林的边更新算法

最小生成森林的边更新在网络路由等方面有着重要的应用价值 .给定 n个结点的无向加权单图 G,该文首先在 n× n的二维可重构造网孔机器上提出了在 O(1)时间内判断 n个结点的无向图的连通性和在 O(logn)时间内求 n个结点的内向树中任一结点到根的路径两个算法 ,并在 n× n× n的三维可重构造网孔机器上提出了 O(1)时间内求 n个结点内向树中任一结点到根的路径的算法 .然后在上述算法的基础上提出了两个 G的最小生成森林的边更新算法 ,一个运行在 n× n的二维可重构造网孔机器上 ,时间复杂度是 O(logn) ,另一个运行在 n× n× n的三维可重构造网孔机器上 ,时间复杂度是 O(1) .     

基于SURF和形状上下文的人脸匹配算法

针对人脸匹配在光照、姿态、表情等背景因素影响下匹配正确率低的问题,本文提出一种基于SURF(Speeded up Robust Features)和形状上下文(Shape Context, SC)的人脸图像匹配算法。在对图像进行人脸区域检测和重构积分图预处理的基础上,本文利用两次SURF算法提取人脸特征点并匹配,第一次用SURF进行粗匹配得到初始匹配集,并据此计算待匹配人脸图像间的尺度差和角度差,以此作为约束条件第二次进行SURF精匹配,以获得更多的匹配点对,最后采用不依赖位置信息的形状上下文算法剔除误匹配点对。在IMM和Georgia人脸数据库上与目前流行的人脸匹配方法进行实验对比,实验结果显示本文算法有效增加了匹配点对数目,并提高了人脸图像匹配正确率,具有更好的稳定性和鲁棒性。     

基于引力模型的三维运动点集的非精确匹配

本文提出了一种基于引力模型(attractive model)的非精确匹配算法,应用于三维空间运动点集的对应点匹配问题.根据引力模型,我们将匹配和运动估计问题转化为一个代价函数的全局优化问题,实现了无对应点的运动估计和总体匹配.这种算法是一个鲁棒(robust)估计和匹配方法,可以处理包含非匹配点对的三维运动点集.大量计算机模拟实验结果充分证明了算法的鲁棒性和有效性.