下载文档原格式
点云对齐杨成林∗2009年5月31日进行数据采集时，由于受到测量设备和坏境的限制，物体表面完整测量数据的获得往往需要通过多次测量完成。
由于每次测量得到的点云数据往往只覆盖物体部分表面，并且可能出现平移错位和旋转错位，因此为了得到物体完整表面的点云数据，需要对这些局部点云数据进行对齐。
点云的对齐所用的方法可分为两种，一种是依靠测量设备进行对齐，另一种则是根据测量后的数据处理对齐。
第一种方法通过特定的设备测量待测工件或测量传感器在多次测量中的位姿。
通过测得的位姿来对齐多次测量数据。
这一方法快速方便，不需后续处理，不过需要额外的设备，而且不能完全满足测量视角的要求。
第二种方法利用测量得到的数据进行对齐，不受设备的约束，测量视角的选择可以更加自由，不过有时计算量很大，而且会因为局部最优等问题得不到正确的对齐。
本文主要讨论后一种对齐方式。
1ICP方法对于两个点集:作为对齐基准的点集P={p1,p2,...,p n}和待对齐的点集X={x1,x2,...,x m}，两个点云的对齐是使以下目标函数的值最小f(R,t)=mi=1||Rx i+t−y i||22(1)其中R和t分别是旋转矩阵和平移向量，而y i是点x i经过变换后的对应点。
此公式中，对应点可以有多种定义方法，比如规定y i为点x i在P中的最近点。
点云对齐问题的难点在于：y i是R和t的函数，事先无法确定，而∗*****************1且对应点的求取通常是计算量很大的工作。
在对应点是最近点的情况，原始的方法计算复杂度为O(mn)，常用的改进方法kd-tree方法计算复杂度在最好的情况下为O(m log n)。
在点集中点数很多的情况下，计算上的消耗是很大的，所以目标函数求值是计算量很大的工作。
虽然对于一般的最优化问题，减少目标函数的计算次数也是一个重要的目标，但在点云对齐问题中，减少目标函数的计算显得尤为重要。
为了解决这一问题，对齐问题的处理通常分为初始对齐和精确对齐两步。
第四章
第四章
无约束优化问题标准形式：
无约束优化问题标准形式：
§
§
§
§
§
§
图最速下降法的收敛过程
αα
2
2
例4－1 求目标函数
取初始点
[2,2]
=
x
例4－2 求目标函数解取初始点[2,2]
=x
算出一维搜索最佳步长
§
例4－3 用梯度法求下面无约束优化问题：
例4－3 用梯度法求下面无约束优化问题：
例4－3 用梯度法求下面无约束优化问题：
例4－3 用梯度法求下面无约束优化问题：
例4－3 用梯度法求下面无约束优化问题：
梯度法的特点
x
给定0,ε
一般迭代式：
§4.3
§4.3
§4.3
§4.3
α0
d 0
x
x 1
x*
1
α1d 1
1()
f −∇x d 1
4-4 共轭方向法
假设目标函数f (x ) 在极值点附近的二次近似函数为
沿某个下降方向
如果能够选定这样的搜索方向，那么对于二
α
0d0
x0x1x*
1
α
1
d1
1
()
f
−∇x d
1。
目录1．最优化的概念与分类 (2)2. 最优化问题的求解方法 (3)2.1线性规划求解 (3)2.1.1线性规划模型 (3)2.1.2线性规划求解方法 (3)2.1.3 线性规划算法未来研究方向 (3)2.2非线性规划求解 (4)2.2.1一维搜索 (4)2.2.2无约束法 (4)2.2.3约束法 (4)2.2.4凸规划 (5)2.2.5二次规划 (5)2.2.6非线性规划算法未来研究方向 (5)2.3组合规划求解方法 (5)2.3.1 整数规划 (5)2.3.2 网络流规划 (7)2.4多目标规划求解方法 (7)2.4.1 基于一个单目标问题的方法 (7)2.4.2 基于多个单目标问题的方法 (8)2.4.3多目标规划未来的研究方向 (8)2.5动态规划算法 (8)2.5.1 逆推解法 (8)2.5.2 顺推解法 (9)2.5.3 动态规划算法的优点及研究方向 (9)2.6 全局优化算法 (9)2.6.1 外逼近与割平面算法 (9)2.6.2 凹性割方法 (9)2.6.3 分支定界法 (9)2.6.4 全局优化的研究方向 (9)2.7随机规划 (9)2.7.1 期望值算法 (10)2.7.2 机会约束算法 (10)2.7.3 相关机会规划算法 (10)2.7.4 智能优化 (10)2.8 最优化软件介绍 (11)3 最优化算法在电力系统中的应用及发展趋势 (12)3.1 电力系统的安全经济调度问题 (12)3.1.1电力系统的安全经济调度问题的介绍 (12)3.1.2电力系统的安全经济调度问题优化算法的发展趋势 (12)2. 最优化问题的求解方法 最优化方法是近几十年形成的，它主要运用数学方法研究各种优化问题的优化途径及方案，为决策者提供科学决策的依据。
最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。
最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。
【MATLAB与机械设计】多维优化之DFP变尺度法1.程序框图其中E矩阵的求解公式为：2.MATLAB可执⾏程序function [k,x_min,f_min]= variable_metric_algorithm(f,x,exp)%% 程序说明%{该程序应⽤于多维⽆条件优化问题中的变尺度法变量说明：输⼊值部分f为⽬标函数，对于⽬标函数中⾃由变量的个数没有要求x为初值矩阵，要求在调⽤函数是必须为⼀⾏n列的形式，否则会导致后期维度出现错误exp为精度返回值部分k为迭代次数x_min为函数的局部极⼩值数列f_min为函数的局部极⼩值调⽤⽅法：clcclearsyms x1 x2%所有的⾃由变量且必须由x1,x2,x3……表⽰x=[0,0];f=x1^2+x2^2-x1*x2-10*x1-4*x2+60;exp=0.01;[k,x_min,f_min]=variable_metric_algorithm(f,x,exp)%}%% 确定维度x_size=size(x,2);x_i= sym(zeros(1,x_size));%class(x_i)for i=1:x_sizesyms(['x' num2str(i)]);x_i(1,i)=['x' num2str(i)];end%% 迭代主题grad_f=gradient(f,x_i);H=eye(x_size);fz_d=-subs(grad_f,x_i,x);fz_d=double(fz_d);g0=fz_d;k=0;while 1s=-H*g0;syms as=s';f_b=subs(f,x_i,x+a.*s);f_bd=diff(f_b,a);a=solve(f_bd==0,a);a=double(a);x_1=x+a*s;fz_d1=-subs(grad_f,x_i,x_1);fz_d1=double(fz_d1);fz_dm1=norm(fz_d1);g1=fz_d1;if fz_dm1<=expx_min=x_1;f_min=subs(f,x_i,x_min);k=k;break;elseif k==x_sizefz_d=-subs(grad_f,x_i,x_1);fz_d=double(fz_d);k=0;H=eye(x_size);elsedeta_x=x_1-x;deta_f_d=fz_d1-fz_d;A=(deta_x')*(deta_x);sub_A=(deta_x)*deta_f_d;B=H*deta_f_d*(deta_f_d')*H; sub_B=(deta_f_d')*H*deta_f_d; E=A./sub_A-B./sub_B;H=H+E;k=k+1;endx=x_1;g0=g1;endendend。
