最小区域法求平面度及八种算法思路

最小区域法和最小二乘法的区别

最小区域法要求找出两个平行的平面夹逼数据,并且这两个平面之间的距离最小
它有一个等价定义是找出一个平面, 所有点到这个平面的最大距离和最小距离之差最小,这里的距离是带正负的

最小二乘法要求找出一个平面,所有点到这个平面的距离之和最小

它们两个的区别在于一个要求所有点到平面的距离之和最小,一个只看最远两个方向的两个点到平面的距离

最小区域法求解

最小区域法上下两个平面有两种可能:一个是三个点过上(下)平面, 一个是两个点过下平面两个点过上平面,如果上下平面没有这样的,必然能再转一下平面,让两个平面之间的距离再小一些
方法1.大力出奇迹法
知道了两种情况就很简单,遍历点云穷举所有可能性,拟合出需要的平面

方法2.压缩解空间法
当找到一个平面,会有上下两个点离这个平面距离最远, 夹逼数据的上下平面必过这两个点,因此只需要找出有资格成为最远点的点,就可以压缩解空间,减少穷举所需要的情况
凸包就是这些有资格的点

因为最小区域法找的是两个夹逼的平行平面,因此它本质上其实也是在找一个方向,这个方向就是这两个平面的法向
有两个方法可以明确方向:
一个是三个不共线的点确定一个方向
一个是直接三个分量确定一个方向

粒子群
每个粒子有速度$v_i$ 最佳位置$p_i$ 当前位置$x_i$
种群有种群最佳位置$p_{best}$

粒子的速度更新方法是
$v_i^{k+1}=w_1{v}_i^k+w_2(p_i-x_i)+w_3(p_{best}-x_i)$
第一项表示惯性,第二项表示粒子自身前进方向,第三项表示种群的前进方向.新速度就是这三项的加权和

在具体应用中需要我们设计的是
粒子位置的意义
一个评价函数以确定位置优劣
各个权重(不一定是常数,也可以是函数) 以确定更新的步长

需要注意的是粒子群有一些隐式假设
好位置附近也是好位置
位置优劣附近的优劣是单调连续的

已知粒子群的思想我们有下面的几种方法

方法3.粒子群求法向
法线的三个分量就是粒子群的位置(其实两个也行,毕竟法向本质上只有二自由度)
评价函数就是平面度
按照惯用是混沌思路,通过调参大法确定好范围之和,权重可以用随机数生成

方法4. 无速度大小的粒子群
调参是很烦人的操作,粒子群比较愁人的一个就是速度大了震荡,速度小了不动
因此可以搞点隐式约束去掉速度中的大小只保留方向
在求解最终平面度时,法向是要单位化的,因此可以提前单位化,单位化的法线集就是一颗球,粒子群也是在球中搜索答案.单位化的速度只有大小没有方向,这样就不会受速度大小影响,就不需要为了考虑速度大小的影响而调参.但是该调的参数还是有点,只不过少了点

方法5. 梯度粒子群
速度和梯度也算是近亲,因此可以在粒子群求更新速度的时候,自我认知得来的速度更新项可以用梯度表达

遗传算法
不同基因代表不同适应性的生物

在实际应用中需要设计基因,设计适应性计算,设计淘汰规则,设计变异,设计交配

遗传算法也有隐式假设
好基因的后代也是好后代

方法6.遗传算法求拟合平面的三个点
适应性计算不用说自然是平面度
基因可以是点序列
交配就是两组基因每项都随机抽取一个作为后代的基因
变异就是基因中某一项或者某几项变异成其他随机的点序列

方法7.遗传算法求法线
这时的基因就是法向的各个分量
交配可以是父母基因的平均,或者其他线性组合方式,例如根据父母的适应性不同占比权重也不同

随机变异可以跳出局部最优,增强随机性,科学变异用科学的方法知道变异的目标

方法8.三点科学变异法
已知三点拟合平面求解平面度时,上下顶点是拟合上下平面的种子选手,可以用这些点来作为变异的目标,不过它可能会陷入局部最优解,并增大死胎的概率,即出现两个不同基因项共点