基于角点检测及几何约束的仿射变换参数估计

本文针对机器视觉现有方法对目标的姿态判定及不同视角间仿射变换参数估计存在的对应特征点提取困难、计算复杂度高等不足,提出一种新的算法.算法引入角点和凸壳等概念,检测目标图像和模板图像的角点,分别组成特征点集并构造点集凸壳,由计算几何原理可知凸壳上的点在仿射变换前后具有对应性.当凸壳内部有内点时,分别对凸壳上的点、凸壳内部的点、凸壳的形心的横坐标和纵坐标构建方程,利用此方程组求解得到仿射变换6个未知参数;当凸壳内部无内点时,采用多项式理论再构建一组二次方程,以达到求解仿射变换参数的目的.实验结果表明,本方法不需要搜索特征点集间一一对应关系,只需点群子集间整体对应,估计得到的仿射变换参数精确,计算复杂度远低于基于区域的同类算法.     

求解k(<10)-中心问题的快速算法

提出求解3-中心问题、4-中心问题、5-中心问题及k(<10)-中心问题的算法.设计该算法的依据是覆盖点集的凸壳必覆盖点集.算法首先判定点集凸壳的形状,然后确定k个圆的排列方式,最后以确定方式计算圆心位置.证明了算法的正确性并且分析了算法的复杂性.     

基于凸壳的支持向量机训练集选取算法研究

基于对支持向量机训练算法的研究与理解,针对支持向量的几何特点,结合凸壳的几何性质,对支持向量机训练算法的工作集选取进行了改进.在LIBSVM的环境下进行了对比分析.数值实验表明,改进的基于凸壳的训练数据选取算法缩短了训练时间并保持了良好的泛化能力,具有一定的参考价值.     

基于非凸上界的ranking模型构造算法

现有的ranking算法均通过最小化原目标函数的凸上界构造ranking模型,得到的模型不够精确.为此,文中提出一种基于非凸上界的ranking算法.该算法首先给出一个基于多类支持向量机(SVM)的框架,然后定义面向NDCG的目标函数,在此基础上设计一个比现有的凸上界更为紧凑的非凸上界逼近原目标函数;针对上界函数的非凸非光滑,提出使用凹-凸过程进行凸逼近,并采用割平面算法进行求解;最后,通过在基准数据集上的实验对该算法进行验证,并与现有算法进行对比.结果表明,相比现有的基于凸上界的ranking算法,文中算法得到的模型不但更为精确,而且更加稳定.     

Delaunay三角剖分的递进构造算法

提出一个计算有限点集Ｓ的Ｄｅｌａｕｎａｙ三角剖分的递进算法，本算法通过对点集Ｓ进行预处理，使得每次插入的点落在已处理点集的凸壳外，从而减少了查找第一个删除顶点的时间，并且能够在最优时间内维持凸壳，克服了Ｂｏｗｙｅｒ算法的缺陷。     

形式验证中近似流管道的算法研究

混合系统形式验证技术是分析在给定的初始条件下,系统的可达集是否都在目标状态集合内。计算可达集是混合系统形式验证中的重要一步,选用何种几何体表示可达集对于整个验证精度有决定性的影响。文章对有向矩形壳和凸多面体2种状态可达集近似表示方法进行了分析比较,结合2种方法的优点提出了流管道过近似混合算法以降低保守性和提高运算速度;最后在Matlab环境下实现了混合算法并且验证了1个分段非线性系统实例,验证结果显示了所提混合算法的有效性。     

求凸壳顶点的一种算法

提出了一种求平面有限点集凸壳顶点的算法,并分析出该算法的时间复杂性是线性次乘法和O(nlogn)次两个数的比较。     

基于金字塔凸壳算法的初始凸包快速优化算法

首先改进四边形法快速凸壳算法使其适应金字塔凸壳算法,进而提出初始近似凸壳算法.其次对初始近似凸壳算法的工作原理进行阐述,并其具体的实现步骤描述.最后通过大量实验数据分析近似凸壳的加速效率以及粗凸壳边数的最佳选择方案.     

金字塔凸壳算法的并行化处理

提出了在金字塔凸壳算法基础上的并行算法.在由多个PC机相互连接所构成的机群并行计算系统之上,采用消息传递方式执行该算法,经过与原串行金字塔算法进行对比,验证本并行处理算法的正确性、可行性和高效性.     

基于凸壳技术的Delaunay三角网生成算法研究

TIN作为DEM的一种重要表达模型,其生成算法一直备受关注。首先对传统的生成算法原理进行总结,并针对其特点进行了分析,对利用凸壳建立TIN的原理和方法进行简单描述。由于许多计算几何学对点集进行限制以简化凸壳的建立过程,对凸壳的生成过程进行了改进。在点集的排序过程中剔除重复点,将点联入原凸壳过程中,排除共线这一特殊情况,建立新的凸壳,直至所有点都被包含在凸壳中。至此,三角网建立完毕。通过对三角形公共边进行LOP优化,使其满足Delau-nay三角网的特性。当所有三角形满足特性时,Delaunay三角网构建完毕。该算法的优势在于构网速度较快,并能够对重复点进行处理,同时在生成网的过程中对共线这种特殊情况进行处理。     

基于夹角的二维凸包改进算法

二维凸包问题是计算几何领域的经典问题之一,在地理信息系统中有广泛的应用.在凸包中,位于两凸点之间直线上点也在凸包上,但不是凸点,如何寻找凸点是凸包算法的关键.提出了基于夹角的平面点集凸包改进算法,以最大夹角,按顺时针的方向可得到所有的凸点,当满足最大夹角的点不唯一时,以离当前凸点最远的点为凸点.     

一般图形与平行线相交之概率

从蒲丰投针问题出发，利用线段与平行线相交之概率，导出一般的凸多边形与平行线相交之概率，进而利用两边夹原理得出一般的凸图形与平行线相交之概率，最后指出一般的图形与平行线相交之概率和其凸包与平行线相交之概率相同．     

一种凸多边形的爆破网络等时线算法研究

本文从爆破网络等时线定义及等时线在爆破工程中的应用出发,提出了一种新的基于凸多边形的爆破等时线凸多边形三角插入算法,算法首先分层算法找出所有的由炮孔组成凸多边形,然后将内层的凸多边形运用三角形插入算法逐次插入到外层凸多边形,从而找出炮孔的等时线,最后采用贪心算法修正少数等时线交叉点。结果表明,此算法生成速度快,解决了爆破网络等时线出现交叉点的情况,具有实际的工程应用价值。     

基于凸包算法的指尖识别方法

针对现有指尖检测方法容易受背景的干扰,并且指尖误判点较多的情况,提出了一种基于凸包分析的指尖检测算法。首先,为减少类肤色背景和光照对手部轮廓提取的影响,采用YCbCr肤色模型和背景差分法相结合的方法提取手部轮廓;然后采用快速凸包算法获得手部轮廓的凸包,并利用凸包顶点和缺陷点计算出掌心的坐标,根据凸包缺陷深度和手指几何特征及曲率特征检测手指指尖;最后采用有灯光和类肤色背景干扰的环境,而不是背景单一的环境进行实验,验证了所提算法的鲁棒性。实验结果表明,该算法可以有效识别出指尖数目和手掌的位置,实现简单的数字手势（0~5）的识别,具有较强的鲁棒性。     

旅行推销员问题凸包方法的性能比分析

在欧几里德平面上证明了旅行推销员问题的凸包方法的性能比上界为n／2,同时给出了凸包随意插入算法的性能比可以接近n／2的例子。另外,对凸包增量最小插入法、凸包最近插入法及凸包最近加入法给出了性能比不超过3的证明。     

一种简单多边形凸包的快速算法及程序设计

给出了一种求简单多边形凸包的快速算法，此算法采取将各个点按与X轴的夹角顺次排列，然后逐渐地删除凹顶点，求得简单多边形的凸包，并给出了算法的数据结构．算法达到了O(nlogn)的理论时间复杂度下限．     

环状分布平面点集的凸包快速生成算法

针对栅格辅助法在处理环状分布平面点集时计算效率较低的问题,提出了一种格网2次处理算法.通过比较离散点所在网格的空间位置关系,经2次剔除点集中绝大部分不可能成为凸包顶点的内点,减少了参与Graham扫描的点数,提高了计算效率.实验结果表明,与栅格辅助法相比,格网2次处理算法能够明显提高处理环状分布平面点集的效率,而且对于其他空间分布较为均匀的平面点集的处理效率也有一定程度的提高.     

轨迹和干扰功率联合优化的无人机主动窃听算法

研究一种无人机(UAV)作为合法窃听器的无线通信窃听算法.首先,将一个合法窃听器(UAV(E))用于窃听可疑发射器(UAV(B))发送到地面可疑接收器的可疑信息.然后,利用可疑系统的特点,提出一种有效的主动干扰方案,从而最大限度地提高有效窃听速率;针对构造的原问题是一个优化变量耦合的混合非凸优化问题,应用更新速率辅助的块坐标下降和连续凸优化技术,在每次迭代中交替优化无人机轨迹和干扰功率.最后,针对非凸的无人机轨迹优化和干扰功率优化问题,分别利用连续凸优化算法将原非凸问题转化为近似的次优化问题,再使用凸优化方法进行求解.仿真结果表明:相较于其他基准算法,文中算法具有更高的有效窃听速率.     

多边形内点集的三角剖分算法

提出了一种多边形内点集的三角剖分算法，该算法采用逐层求凸壳，对不在凸壳边界上的多边形顶点给予特殊处理，然后逐层分割环域成三角形序列，最后优化各三角形的边长，改变分割方式，使之能得到最短长度或接近最短长度的三角剖分．