Fitting a Step Function to a Point Set

We consider the problem of fitting a step function to a set of points. More precisely, given an integer k and a set P of n points in the plane, our goal is to find a step function f with k steps that minimizes the maximum vertical distance between f and all the points in P. We first give an optimal Θ(nlog n) algorithm for the general case. In the special case where the points in P are given in sorted order according to their x-coordinates, we give an optimal Θ(n) time algorithm. Then, we show how to solve the weighted version of this problem in time O(nlog ⁴ n). Finally, we give an O(nh ²log n) algorithm for the case where h outliers are allowed. The running time of all our algorithms is independent of k.     

基于局部特征匹配的对称面提取算法

在反求工程中,对称面提取对于点云的几何模型重建具有重要意义,根据对称性原理,给出了点云模型中双侧对称性的数学定义,在此基础上,构造了一种基于迭代最近点(ICP)数据匹配的对称面提取算法,该算法已经在反求工程CAD系统RE-SOFT中实现,并应用于汽车引擎罩、卫生洁具零件的模型重构。     

三维模型对称平面重建的特征匹配方法

提出一种利用实物对称特征重建对称基准平面的方法：首先选择一组对称特征;然后将测量数据点投影在一过测量坐标原点的平面——定义为初始平面上,并用折线连接,旋转初始平面使两条折线重合,可以得到一个与对称平面平行的平面;接下来再移动这个平行平面,使对称特征到它的距离相等,这时的位置平面即为所求的对称平面。该方法已在逆向工程数据前处理系统中实现,并应用于摩托车外形塑件的逆向工程．     

基于变分贝叶斯层次概率模型的非刚性点集配准

非刚性点集配准是计算机视觉和模式识别领域的基础研究问题,现今的非刚性点集配准算法在存在大量离群点、噪声、点集对应关系缺失、旋转和形变情况下,不能非常准确地评估出两个点集间的对应关系.本文通过交替执行点集对应关系评估和空间转换更新两个步骤来逐步恢复点集间一一对应关系.在对应关系评估步骤,首先本文基于有限重尾学生t分布隐变...     

A Theory of Minimal 3D Point to 3D Plane Registration and Its Generalization

Registration of 3D data is a key problem in many applications in computer vision, computer graphics and robotics. This paper provides a family of minimal solutions for the 3D-to-3D registration problem in which the 3D data are represented as points and planes. Such scenarios occur frequently when a 3D sensor provides 3D points and our goal is to register them to a 3D object represented by a set of planes. In order to compute the 6 degrees-of-freedom transformation between the sensor and the object, we need at least six points on three or more planes. We systematically investigate and develop pose estimation algorithms for several configurations, including all minimal configurations, that arise from the distribution of points on planes. We also identify the degenerate configurations in such registrations. The underlying algebraic equations used in many registration problems are the same and we show that many 2D-to-3D and 3D-to-3D pose estimation/registration algorithms involving points, lines, and planes can be mapped to the proposed framework. We validate our theory in simulations as well as in three real-world applications: registration of a robotic arm with an object using a contact sensor, registration of planar city models with 3D point clouds obtained using multi-view reconstruction, and registration between depth maps generated by a Kinect sensor.     

基于支持向量机的散乱数据拟合

文章提出了一种有效的大规模散乱点拟合方法,它是采用最小均方支持向量机局部拟合对Shepard插值方法进行改进。支持向量机基于结构风险最小化准则,在数据拟合方面具有较好的泛化能力,而改进的Shepard法能有效拟合大规模样本点。实验结果表明该算法对大规模散乱数据点具有较好的拟合性能。     

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

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

Fuzzy Free Path Detection from Disparity Maps by Using Least-Squares Fitting to a Plane

A method to detect obstacle-free paths in real-time which works as part of a cognitive navigation aid system for visually impaired people is proposed. It is based on the analysis of disparity maps obtained from a stereo vision system which is carried by the blind user. The presented detection method consists of a fuzzy logic system that assigns a certainty to be part of a free path to each group of pixels, depending on the parameters of a planar-model fitting. We also present experimental results on different real outdoor scenarios showing that our method is the most reliable in the sense that it minimizes the false positives rate.     

利用点和平面间的对偶性设计可展面

基于点和平面间的对偶性原理 ,提出了一种设计四次样条上可展面的方法 ,讨论了所设计可展面的特点和几何构造 ,并以中心点表示控制平面的方式对曲面的设计进行了较详细的实例分析 文中的设计方法直接、简单、有效 ,实例表明设计结果良好     

基于最大熵和互信息最大化的特征点配准算法

点配准问题在机器视觉、医学图像等领域,有着非常重要的应用基础．通过在最大化熵原理的基础上,将互信息相似性测度引入到点配准算法中,提出了一种新的快速、准确的健壮性的点配准算法．首先建立起表示两个特征点集之间匹配对应关系的联合概率分布匹配矩阵,通过最大化熵和互信息最大化,建立起一个包含匹配矩阵和空间变换参数的新的能量函数,通过确定性退火算法,可以获得最优的匹配矩阵和空间变换参数,从而解决点的对应性问题和出界点(outliers)确定．实验结果表明,算法具有较强的鲁棒性,具有较高的配准精度和较快的计算速度．     

启发式探查最佳分割平面的快速KD-Tree构建方法

在基于光线跟踪方法的真实感绘制中,kd-tree是一种重要的加速结构.文章对kd-tree的构建方法进行了研究,提出了一种基于分区(binning)算法的快速构建方法.首先,通过分析kd-tree的成本函数,启发式地定位了当前节点的分割平面所在的子区间;其次,对探查到的子区间进行进一步的细化采样(sub-sampling),使得到的分割平面更好地逼近最优分割位置;同时,文章分析了现有方法在处理分割终止时存在的问题,提出了更加合理的分割终止条件.与以往方法相比,新方法用更小的计算成本生成了质量更好的kd-tree,构建过程更加鲁棒.实验数据验证了文中方法的有效性.     

用最小不动点理论求解最小函数依赖集

最小函数依赖是数据库模式分解的基础。本文首先介绍最小函数依赖集的概念和最小不动点理论．然后分析函数依赖集的闭包与完全格的关系，提出了用最小不动点理论求解最小函数依赖集的具体求解方法。     

气动肌肉仿生关节建模与机构优化设计仿真

关于机器人关节动态设计优化问题,机器人关节机构应随仿生特性要求而变化.建立了拮抗安装气动肌肉驱动的关节模型,通过齐次坐标变换建立了气动肌肉伸缩量与关节转角之间的精确模型.提出了4个约束条件,定义了关节有效摆动角度.为分析不对称和不等高机构对转动角度、速度及加速和控制精度的影响,利用MATLAB编程进行了3组参数下的摆动仿真,对比了关节轨迹曲线,并分析了各约束条件的强弱.针对人手臂关节,优化设计了仿生肩和肘关节.与传统方案对比表明,优化设计的仿生肘关节转角范围更广;肩关节加速性能更好;仿生关节性能特性更接近人类上肢体运动特点.