点云边界线的提取.pdf

点云曲面边界线的提取引言用三维扫描仪对物体表面采样，可以得到稠 密、均匀、散乱的采样点集，称为点云，其中 每一个点 Pi=(xi,yi,zi)。点云与深度图像(距离图像)-点云p1,p2,.,pn:散乱点的集合，描述一个物 体或其中的一部分-深度图像zi=f(xi,yi)：有规律，描述物体的一个侧 面视图点云的优点曲面的点云表示可以转化为网格表示。近年来基于采样点的数字几何处理研究逐渐深入，用点云表示三维碎片比用网格表示具有很多优势-点云是最原始、最真实的数据，没有加入任何人为因素；-采样点的几何结构简单，处理所需的时空代价较低；-可以直接应用扫描所获取的稠密均匀的采样点集，回避了 复杂的网格生成过程；-对模型表面的离散表示，有助于数据处理中的并行处理和 算法的优化设计，特别是分割、合并处理比较简单等。点云描述的曲面可以分为两类点集开曲面点集闭曲面：由封闭表面围成的具有一定体积的 物体边界线边界线是描述开曲面的一个重要特征。在许多问题中都需要提取点云表示的开曲面的边界线：-访体分割-目标识别-文物复原-碎片拼接-点云补洞点云是散乱点集，属于非结构化数据，不具备连接 性信息，定义和提取其边界线并不简单。定义-曲面的边界线问题：给定一个有边界的曲面片 S的采样点集P,找出代表曲面片边界的采样点 子集B。曲面片S表示一个有边界的流形曲面，它的每 一个点都有一个邻域，或者同胚于开圆盘，或 者同胚于半圆盘。曲面片S的内点存在一个邻域，与开圆盘那=；工正悯曲面片S的边界点存在一个邻域，与半圆盘gcEI：同胚，其中半空间 回：=（.“，）w眩、2 0。全体边界点的集合构成曲而片S的边界。这些定义适用于连续的曲面片S。对于曲面片的有限采样点集P,利用采样点p P的七个最邻近点N(p)构成的邻域得出类似的定义-某个点相邻的k个最邻近点 均匀栅格-KD-树结构-近似最近邻库ANN已有方法 Emelyanov提出了一种利用贪心三角化提取曲 面边界线的方法，把没有被三角形链包围的点 看作是边界点。-在三角化时需要进行复杂的判断，保证与一条边关联的三 角形不能多于两个，而且不能形成四面体，因此计算较复 杂。Orriols利用递归最小二乘法提取曲面边界线。-采用了全局方法，计算速度快；-得到的边界线不够精确，没有找出所有的边界点。Floater在无网格参数化中采用了一种简单的边 界检测方法，把位于局部三角化边界上的点作 为边界点。-在点集采样不均匀的情况下会把很多内部点错误 地判断为边界点 Dey基于采样点的Voronoi图提出了一种边界检 测算法-在满足一定采样条件下这种方法可以从理论上保 证其有效性。但是计算采样点的Voronoi图比较复 杂，而且对采样条件有严格限制。Maes利用Pearson检验和遗传算法检测边界线-在遗传算法计算过程中不能保证最后得到的边界线的封闭 性，而且需要针对不同的数据集调整参数。Gumhold讨论了从曲面点云中苴接提取特征线的方 法，-首先构造点集的邻近关系图，然后计算邻近关系图的最小 生成图，并对较短的特征线进行剪枝处理，提取封闭的特 征线。Bendels为了检测点云数据的空洞边界，计算邻近关 系图的最小生成树，然后添加其他边，寻找长度大 于某个阀值的最小圈。-最小生成图和最小生成树方法都是贪心算法,不能保证提取的封闭边界线的整体最优性。0.150.15O-OOQ）邻近关系图的一部分（b）最小生成树对应的边界（c）最优的边界主要步骤-根据一个点周围的k个最邻近点，计算每个点 的边界概率。-为了找到真正的边界点，根据点的边界概率和 局部邻近关系构造一个赋权无向图。-利用最大圈算法寻找边界线，保证提取的边界 线是封闭的，且是整体最优的。均匀栅格结构 计算整个点集的包围盒 计算网格单元的边长size=(xmax-)(ymax-)(zmax-)/n 把每个数据点放入唯一一个网格单元中一个网格单元对应一个链表，其结点结构如下：structure NODE(flag:标志dataPbintPointer:指向数据点的指针nextNodePointer:指向链表中的下个结点度量标准1最大角度量 利用完全最小二乘平面计算通过某点P目拟合邻近数 据点的平面。把每个点投影到拟合平面上，用极坐标表示。按照夹角从小到大的顺序对所有投影点排序。固定阈值不精确如果其中有一个角度满足一/夕，i=l,2,.用，a1M*=是预先设定的一个角度，例如110,则p为边界点；否则，p不是边界点。边界概率angle Pr(p)=min7T-2/k1.0；度量标准2半圆盘度量用点集N(p)的所有投影点的用心与p的距离(3 而-p|halfdisk Pr(p)=min 11 11.1.0)4广i*、行其中广=而半径为广的半圆盘的重心与圆心的距离是士k占 3穴度量标准3形状度量N(p)的散布矩阵S描述了逼近N(p)的椭球的形状S=+/l3e3e 特征向量对应椭球的主方向，特征值决定了椭球的 大小和形状shape Pr(p)=min(4一石)(右一百)1/9对三个特征值进行归一化处理，构成一个判断 向量特征点判断向量内卢r，八一4名%角点或噪声点直线上的点41,石、石土0边界点%石石综合度量标准1 z Pr(p)=(angle Pr(p)+halfdisk Pr(p)+shape Pr(p)典型数据的边界概率值(a)最大角度吊：(b)半圆盘度T.(c)形状度(d)综合度T：典型数据的边界概率值(a)最大角度T：(b)半圆盘度T：(c)形状度M：(d)综合度最ITI U.7JU工期2她典型数据的边界概率值.5U.LHU(a)最大角度最(b)半圆盘度就(c)形状度最(d)综合度就封闭边界线的提取对邻近点在最小二乘平面上的投影进行Delaunay三角化，如 果两个点属于同一个三角形，则定义为相邻。-点云作为无向图的顶点集合点的相邻关系作为无向图的边集合-边的权值W(Pi，Pj)=Pr(p,)+Pr(p.)2*d(Pj,Pj)-提取封闭边界曲线就转换为在赋权无向图中寻找最大圈问题最大圈算法赋权无向图的构造Q)图G中的简单圈(b)图G中的完全匹配(1)对于G中的每一个顶点/，G，有两个对应的顶点,2 和一条边(%,%)，其权值 W(i J/2)=0 o(2)对G中的每一条边(凡)，G，有曲个对应的顶点,.片和五条边，其权值分别为=w(2，v)=/(、然】)=犷。？匕)=,*31)=0 o定理1如果G包含一个简单圈。，则G存在一个完全匹配M,且 MC)1/(5/)o定理2如果G，存在一个完全匹配”，则G包含一个简单圈集合 S=G，,C,”，且 士 w(C)=。GeS推论 如果G，存在一个最大完全匹配则G包含一个简单圈集合S=G，,g,且C=L,加是包含相同顶点的最大圈。寻找赋权无向图G的最大圈的问题归约到寻找赋权无向 图G，的最大完全匹配问题，这可以利用Edmonds给出 的多项式时间最大完全匹配算法。要提取的边界曲线具有两个重要的性质：-边界曲线是一条封闭曲线；-一个边界点一定与另外一个边界点存在局部邻接关系。散乱点集的边界线包含的边界点数一般都要大于某个 阈值，低于该阈值的边界线不是要寻找的真正的边界 线。因此最大圈中包含的顶点数也必须大于这个阈 值。寻找封闭边界曲线的算法stepl根据图G=（H.E）构造权值非负的赋权无向图U=（忆Ef）；step2在G中寻找最大完全匹配河；step3根据下一节定理2的证明过程，由最大完全匹配M构造G中一个非 负简单圈集合S=G，,g；step4利用双连通算法从S中找出包含顶点最多的圈C：step5如果圈C中的顶点数大于某一个阈值（可以根据边界包含的点数确 定，一般取10至30之间），则C就对应封闭边界曲线，算:法停止；否则继 续执行step6；step6在每个。=1,，中找出权值最小的一条边，并从G中删除，转 stepl：实现过程中利用了 LEDA-最大完全匹配MAK_W曰GHT_MATCHING-双连通算法BI8NNECTED_8MpONENTS。实验结果(a)无向图G(b)的闭边界曲线(c)原始数据中对应的边界曲线实验结果(a)无向图G(b)封闭边界曲线(c)原始数据中对应的边界曲线最小生成树方法vs最大圈方法(a)最小生成树法提取的边界(b)最大圈法提取的边界(c)两种结果的比较(d)局部放大后的结果比较实验结果Orriols方法本文 方法Orriols方法本文 方法两条边界线的情况