离散点云最小包围圆求解.doc

离散点最小包围圆求解
近年来激光雷达技术去得了快速的发展，由于它在数据上又精确度高，速度快，能够快速展现出地物原貌等特点，对于海量的数据我们可以通过简化为数学模型，进而确定地物的中心点。点云数据在树木，电杆等地物的提取中，树木电杆的点云并不是无关的，而是具有高度的相关性，他们的投影可以看成平面的不规则图形，通过求取最小包围圆的中心和半径，进而判断出电杆和树木的中心位置，而这个过程就可以转化为离散点求最小包围圆的问题了。
在平面离散点数据中，树木和电杆的离散点急可以近似的看成一个类似圆的图形，通过求取圆形的中心就可以近似确定树木和电杆的中心达到获得地物中心点的目的。
目前，通用的做法就是根据最小二乘原理求出近似中心，再以此为近似值进行精确求取圆心坐标。目前典型算法主要有
Mark de berg的随机增量算法：
1. 随机打乱点集中的所有点的顺序
2. 以序列中前两个点构造最小包围圆d
3. 一次搜索其余的点，若某个点v在d外，则重新构造最小包围圆d’，是d’包含d中的所有点且以v为边界点。重复执行第三步，直到求出最小包围圆。
随机增量算法，一般点是有序的，故打乱点顺序也需要耗费时间，然后构造圆并进行判断，满足在圆内是排除这些点，再根据剩下的点生成最小包围圆再一次判断，这个方法构造的包围圆相当于点集中距离最远的点形成的最小包围圆。

汪卫最远点优先渐进算法：
1. 在点集中任取三个点：A,B,C；
2. 以这三个点构造最小包围圆D；
3. 在点集p中查询距离D的圆心最远的点v；若v在D内则算法终止；否则
4. 在{A,B,C,D}中选取3个点，构造包含这四个点的最小包围圆D’，转至第二步，其中选取的这3个点尽可能是边界上的点。
这个算法第一步任取三个边界点可以用凸包求出边界点，然后进行构造最小包围圆，任取三个点可以改为任取两个点，因为根据凸包的性质，做小包围圆的边界肯定包含凸包的定点，然后只要判断剩下的点时候在圆内，如果在则终止算法，不在则根据新点和圆心重新构造最小包围圆
Frank Nielsen对偶决策算法：
1. 计算所有点在x轴上的投影区间[min x , max x];
2. 计算所有点到第一个点的距离最大值d1；
3. 以r=3d1/4为初始半径，以ε=d1ε0/8为误差控制，搜索区间为[max x-r ,min x+r]构造对偶决策误差，并进行迭代求解。其中ε0为用户指定的误差控制阀值。
不仅能算出平面点集的最小包围圆，也能算出圆盘集的最小包围议案，但是算法设计比较复杂
另外还有计算几何求解最小包围圆的算法：
1. 对点集构造凸包，删除凸壳内的点
2. 以凸壳上的采样点的最小二乘为圆心，求取最远一点到它的距离，令其为比较半径Rc
3. 删除无关数据点：以Rc为标尺，删除所有不可能参与构成最小外接圆的无关数据点，即，对于点Pi，若Pi-1Pi的中垂线与PiPi+1的中垂线的交点到Pi之间的距离Ri>Rc,则删去Pi
4. 调整数据结构，循环到步骤2，知道没有无关数据点，循环终止
5. 对剩余的点构造最远Voronoi图，判断Voronoi定点距其相关点的距离，其中距离最小者为所求的最小外接圆半径，该Voronoi定点为最小外接圆圆心
在实际点云数据处理中，电杆为人工建筑物，可以按上述几种方法求取中心线位置，并有较好的精度，但是树木，由于其生长的特殊性，以及后期人工干预其生长等特性，并不能单一的认为树木中心即在点云所处的中心，必须有一定的约束条件，一般树木都是以中心位置向外伸张，所以点云采集密度也由两边向中间密集，类似于正态分布，但考虑到植物的向阳性以等原因，采样点的分布不可能非常均匀，肯能向某一方偏移较大，但是中心点附近一定范围内的点数目还是占很大比重的
故个人认为在计算时可以距离为权，相当于确定点云的质心所在位置，这个位置也并不是非常精确，可以结合最高点和最低点进行约束拟合，求取精确位置
也可以以最小二乘求取点云的中心，在根据约束条件求取
另外，根据树木分析的特性，一般在距离地面两米高的树干上基本不生长枝叶，并且也很少有枝叶会遮挡下面的树干，故以此为约束条件，可以较好的求出树木中心所在的位置，但是，也得考虑车辆，行人，建筑物等对树干的遮挡，在这种情况下这种方法基本失效
所以在实际过程中可以采取两种方法相结合求取树木中心位置