ICP算法的鲁棒性改进
- 格式：pdf
- 大小：543.23 KB
- 文档页数：4
2
605
E( a) = 2(
2
e) e+ 2(
th
e)
T
e
比 ICP 迭代多消耗一个因素 p 。 但是在部分 5 中, 这种 消耗将 消失, 所以在这 部分迭代 计算实际 上就是 计算 正确的横坐标。 在图 1 中显示这个结果的概述是 LM ICP 有一个 略大的收敛区间, 以略微减小的误差能找到最优。L M 算法平均需要 少出 50% 的迭代, 但是除非像部 分 5 中 那样应 用加速, 否则这 个优点在 有限差分 求导中 将会 丢失。 甚至在用于一般用途的情况下, 也会吃惊的发现 LM 算法甚至可以与 ICP 的闭式内部最优相匹敌。
Robust Improvement of ICP Algorithm
L iu Fanming Qu Hao
( College of A utomation, H ar bin Engineer ing U niv er sity , H ar bin 150001 , China)
Abstract It int roduces a new meth od of regist ering poin t sets . T h e regist rat ion error is directly min imized us in g gen eralpurpos e nonlinear opt imizat ion ( t he Levenberg -M arquardt algorithm ) . T h is techn ique is comparable in speed to th e special-purpose ICP algorith m wh ich is mos t commonly us ed for t his task . Becau se th e routine direct ly minimizes an energy fu nct ion , it is easy t o ext end it t o incorporate robus t est imat ion via a Huber k ernel, yielding a basin of convergence th at is many t imes wider t han exist in g techniques. Fin ally it introdu ces a dat a st ruct ure f or the min imizat ion b ased on th e ch amf er distance transf orm w hich yields an algorit hm th at is both fast er and more robus t than previou sly described met hods. Key words ICP algorith m Nonlinear opt imization Poin t set regis tration Robus t
2
在 L M 的 来历中一个重 要的概念是余 数向量 Ei ( a) , 这样 E( a ) = 。 LM 算法合并了梯 度下降和高斯—牛顿法对 函数 最小化。 使用上面的符号表示法, 每次迭代的目的是对 现有 的 a k 选择 一次 更新, 设为 x, 这样 使 a k+ 1 = ak + x 以减小误差 E ( a) 。围绕 a 扩展 E ( a + x ) , 我们得到: m j - T ( ak ; di ) i= 1…N d E( a+ x) = E( a) + ( 1 (( 2!
E( a) ・x) + E( a) ・x ) ・x) + h. o. t .
因此 m
( i)
是对 应于由 现有 的估 计值 ak 变化 而来
根据 e 表示, 有: E( a) = eT e E ( a ) = 2(
T e) e
的数据点 di 的最近模型点。
第 4 期增刊 I CP 算法的鲁棒性改进
表2
符号一览表 N m 模型点 m i N d 数据点 di 数据点 最近模型点 : i
( i) -
( i)
变换 T ( a ; x ) , 参数 a ∈ R p 误差 i ( a) = m T ( a; di )
i(
余量 e ∈ RN d , 元素 E i = ∈ 2 (
a) )
ei a j
2 2
ICP 算法最简单的形式是两步 迭代。从对准参数 a 0 的 初始 估计开 始, 算法 形成 估计值 ak 的序列, 它不 断 的减 小误差 E( a) 。算 法的每次 迭代由 下面两 步组 成, 记为 C 和 T : C . 计算对应性 , 设: ( i) = argmin
j ∈{ 1…N m}
Nd
E ( a, ) =
∑w ∈
i= 1 i
2
m
(i)
- T ( a; di )
( 1)
通常, 函数
考虑在最小化过程中: 像 ICP 算法中
( i) 是基于使模 型和数据之间的距离最小 这点来选择 的, 结果误差函数变为:
Nd
E( a) =
∑w
i= 1
i
min
j
2
m j - T ( a; di )
( 2)
第 25 卷第 4 期增刊
仪 器 仪 表 学 报
2004 年 8 月
ICP 算法的鲁棒性改进
刘繁明 屈 昊
( 哈尔滨工程大学自动化学院 哈 尔滨 150001) 摘要 提出了对准点 集合的一种新方法。 该方法采用对准误差 通过非线性最优化 算法 ( L evenberg M arquardt) 直接最小化 , 在速度上可与 ICP 算法相匹敌 , ICP 算法是 专门用于对准工作的特殊用途的算法。因 为程序直接最小化 一个能量函数 , 所以 很容易通过 Hunber 核 , 把它扩充 到合并的鲁棒性估计中 , 产生的收敛区间比现存方法 的收敛区间宽很多倍。 最后介绍一种基 于切面距离变换最小化的数据结构 , 这种变换产生的算法比以前描述的方法速度快而且鲁棒 性强。 关键词 ICP 算法 非线性最优化 点集对准 鲁棒性
雅可比行列式 J, 大小 N d × p, ijt h 元素 =
算法。 把 L M 应用到 ICP 问 题将马上产生 这样的 疑问: E 的导数要怎样计算。确实对第一次求导从 LM 最优 化角 度来看 直接 就不适 合 E , 如 果在 总和之 内对 j 离 散最小化。 但是, 在第 5 部分可以看到实际上 E 的导数 可以简 单有效的获得, 它们是平 滑的或者 可以使 之平 滑。目前, 我们就假设它们是平滑的, 通过有限次差分 [ 3] 计算它们, 以每次内循环有 p 次额外的函数估值为 贷价, 这意味着对最简单形式的 LM ICP 来说, 每次迭 代的消耗由于 1+ p 这个因素而增加了。但是, 在典型 情况 下, LM 要求 很少次 的迭代 就能 得到确 定的精 确 度, 这个因素是个上限。在许多情况下, 减少迭代的次 数比增加每次迭代的消耗要好。 接下来引出 L M 算法。 误差函数 E( a) 可以写成 N d 个余数的和, 如下:
。由于它的简单和功能, ICP 算法
很具有吸引力的。 这里放弃了 ICP 的一个基本特性—— 它 的闭式内回路—— 取而代之的用了标准迭代非线性最优 化, L even berg M arquardt 算法 。它在没有出现大量速 度损失的情况下把 ICP 扩展到真实的鲁棒估计中。 文章所 提出的技 术有更多 的好处, 使得算法 比传 统的 ICP 更快更精确, 有更宽的收敛区间。
x
E( a+ x) = J e+ J Jx= 0
T
T
解方程求 x, 得到高斯—牛 顿更新, 给算法 高斯—牛顿 ICP 的一次更新 ( 1) 计算 余数 向量 e( a k ) , 和根 据 a 的 分 量导 出 J 的 N d ×p 矩阵。( 对于二维刚体变换, a 有三个分量, 则 J 是 N d ×3 矩阵) 。 ( 2) 计算更新 x = ( J J ) ( 3) 使 a k+ 1 = ak + x 。 当 然, 上述 方 法 并不 保 证 采 用的 步 长 会 引起 误 差 E ( a ( k+ 1) 减小。它是否减小依 赖于对 a k 的泰 勒级数展开 的第二项的精确性, 和高斯—牛顿近似值的有效性。 但 是, 可以看出接近最小值时它们的近似值通常是好的, 收敛是快速可靠的。 进行比 较, 用一些 以前对准 算法中 用到的加 速梯 度下降法代替第二步, 有: ( 2) 计算更新 x = - 1 T T - 1 T
最后, 围绕 a 的最小化给出对准的最优估计:
Nd
E( a) = Ei ( a) = e( a ) =
∑E ( a)
i= 1 2 i
∑ a = argmin w i min a i= 1 j
2. 1 ICP 算法
2
m j - T ( a; di )
w i min
j Nd i= 1
m j - T ( a; di ) e( a)
Nm i= 1
和 di
Nd i= 1
表示。 对准工作是确定变换 T , 当应用
于数据点时得到最好的对准模型和数据。T 的参数由 一般的变换和相对应的 p 值列在表 1 p 维向量 a 表示。 中。 表 1, 出现在对准问题中的一般性变换, 表 2, 文章 的符号一览表。 对于二维对准 p= 3, T 的参数是旋转角 和平移向 量 t x , t y 。则得到参数向量 a = T 2D ( a ; x ) = T , t x , ty ; x = cos - sin , t x , t y , 我们定义: s in cos ty 2 for x ∈R x+ tx
605
E( a) = 2(
2
e) e+ 2(
th
e)
T
e
比 ICP 迭代多消耗一个因素 p 。 但是在部分 5 中, 这种 消耗将 消失, 所以在这 部分迭代 计算实际 上就是 计算 正确的横坐标。 在图 1 中显示这个结果的概述是 LM ICP 有一个 略大的收敛区间, 以略微减小的误差能找到最优。L M 算法平均需要 少出 50% 的迭代, 但是除非像部 分 5 中 那样应 用加速, 否则这 个优点在 有限差分 求导中 将会 丢失。 甚至在用于一般用途的情况下, 也会吃惊的发现 LM 算法甚至可以与 ICP 的闭式内部最优相匹敌。
Robust Improvement of ICP Algorithm
L iu Fanming Qu Hao
( College of A utomation, H ar bin Engineer ing U niv er sity , H ar bin 150001 , China)
Abstract It int roduces a new meth od of regist ering poin t sets . T h e regist rat ion error is directly min imized us in g gen eralpurpos e nonlinear opt imizat ion ( t he Levenberg -M arquardt algorithm ) . T h is techn ique is comparable in speed to th e special-purpose ICP algorith m wh ich is mos t commonly us ed for t his task . Becau se th e routine direct ly minimizes an energy fu nct ion , it is easy t o ext end it t o incorporate robus t est imat ion via a Huber k ernel, yielding a basin of convergence th at is many t imes wider t han exist in g techniques. Fin ally it introdu ces a dat a st ruct ure f or the min imizat ion b ased on th e ch amf er distance transf orm w hich yields an algorit hm th at is both fast er and more robus t than previou sly described met hods. Key words ICP algorith m Nonlinear opt imization Poin t set regis tration Robus t
2
在 L M 的 来历中一个重 要的概念是余 数向量 Ei ( a) , 这样 E( a ) = 。 LM 算法合并了梯 度下降和高斯—牛顿法对 函数 最小化。 使用上面的符号表示法, 每次迭代的目的是对 现有 的 a k 选择 一次 更新, 设为 x, 这样 使 a k+ 1 = ak + x 以减小误差 E ( a) 。围绕 a 扩展 E ( a + x ) , 我们得到: m j - T ( ak ; di ) i= 1…N d E( a+ x) = E( a) + ( 1 (( 2!
E( a) ・x) + E( a) ・x ) ・x) + h. o. t .
因此 m
( i)
是对 应于由 现有 的估 计值 ak 变化 而来
根据 e 表示, 有: E( a) = eT e E ( a ) = 2(
T e) e
的数据点 di 的最近模型点。
第 4 期增刊 I CP 算法的鲁棒性改进
表2
符号一览表 N m 模型点 m i N d 数据点 di 数据点 最近模型点 : i
( i) -
( i)
变换 T ( a ; x ) , 参数 a ∈ R p 误差 i ( a) = m T ( a; di )
i(
余量 e ∈ RN d , 元素 E i = ∈ 2 (
a) )
ei a j
2 2
ICP 算法最简单的形式是两步 迭代。从对准参数 a 0 的 初始 估计开 始, 算法 形成 估计值 ak 的序列, 它不 断 的减 小误差 E( a) 。算 法的每次 迭代由 下面两 步组 成, 记为 C 和 T : C . 计算对应性 , 设: ( i) = argmin
j ∈{ 1…N m}
Nd
E ( a, ) =
∑w ∈
i= 1 i
2
m
(i)
- T ( a; di )
( 1)
通常, 函数
考虑在最小化过程中: 像 ICP 算法中
( i) 是基于使模 型和数据之间的距离最小 这点来选择 的, 结果误差函数变为:
Nd
E( a) =
∑w
i= 1
i
min
j
2
m j - T ( a; di )
( 2)
第 25 卷第 4 期增刊
仪 器 仪 表 学 报
2004 年 8 月
ICP 算法的鲁棒性改进
刘繁明 屈 昊
( 哈尔滨工程大学自动化学院 哈 尔滨 150001) 摘要 提出了对准点 集合的一种新方法。 该方法采用对准误差 通过非线性最优化 算法 ( L evenberg M arquardt) 直接最小化 , 在速度上可与 ICP 算法相匹敌 , ICP 算法是 专门用于对准工作的特殊用途的算法。因 为程序直接最小化 一个能量函数 , 所以 很容易通过 Hunber 核 , 把它扩充 到合并的鲁棒性估计中 , 产生的收敛区间比现存方法 的收敛区间宽很多倍。 最后介绍一种基 于切面距离变换最小化的数据结构 , 这种变换产生的算法比以前描述的方法速度快而且鲁棒 性强。 关键词 ICP 算法 非线性最优化 点集对准 鲁棒性
雅可比行列式 J, 大小 N d × p, ijt h 元素 =
算法。 把 L M 应用到 ICP 问 题将马上产生 这样的 疑问: E 的导数要怎样计算。确实对第一次求导从 LM 最优 化角 度来看 直接 就不适 合 E , 如 果在 总和之 内对 j 离 散最小化。 但是, 在第 5 部分可以看到实际上 E 的导数 可以简 单有效的获得, 它们是平 滑的或者 可以使 之平 滑。目前, 我们就假设它们是平滑的, 通过有限次差分 [ 3] 计算它们, 以每次内循环有 p 次额外的函数估值为 贷价, 这意味着对最简单形式的 LM ICP 来说, 每次迭 代的消耗由于 1+ p 这个因素而增加了。但是, 在典型 情况 下, LM 要求 很少次 的迭代 就能 得到确 定的精 确 度, 这个因素是个上限。在许多情况下, 减少迭代的次 数比增加每次迭代的消耗要好。 接下来引出 L M 算法。 误差函数 E( a) 可以写成 N d 个余数的和, 如下:
。由于它的简单和功能, ICP 算法
很具有吸引力的。 这里放弃了 ICP 的一个基本特性—— 它 的闭式内回路—— 取而代之的用了标准迭代非线性最优 化, L even berg M arquardt 算法 。它在没有出现大量速 度损失的情况下把 ICP 扩展到真实的鲁棒估计中。 文章所 提出的技 术有更多 的好处, 使得算法 比传 统的 ICP 更快更精确, 有更宽的收敛区间。
x
E( a+ x) = J e+ J Jx= 0
T
T
解方程求 x, 得到高斯—牛 顿更新, 给算法 高斯—牛顿 ICP 的一次更新 ( 1) 计算 余数 向量 e( a k ) , 和根 据 a 的 分 量导 出 J 的 N d ×p 矩阵。( 对于二维刚体变换, a 有三个分量, 则 J 是 N d ×3 矩阵) 。 ( 2) 计算更新 x = ( J J ) ( 3) 使 a k+ 1 = ak + x 。 当 然, 上述 方 法 并不 保 证 采 用的 步 长 会 引起 误 差 E ( a ( k+ 1) 减小。它是否减小依 赖于对 a k 的泰 勒级数展开 的第二项的精确性, 和高斯—牛顿近似值的有效性。 但 是, 可以看出接近最小值时它们的近似值通常是好的, 收敛是快速可靠的。 进行比 较, 用一些 以前对准 算法中 用到的加 速梯 度下降法代替第二步, 有: ( 2) 计算更新 x = - 1 T T - 1 T
最后, 围绕 a 的最小化给出对准的最优估计:
Nd
E( a) = Ei ( a) = e( a ) =
∑E ( a)
i= 1 2 i
∑ a = argmin w i min a i= 1 j
2. 1 ICP 算法
2
m j - T ( a; di )
w i min
j Nd i= 1
m j - T ( a; di ) e( a)
Nm i= 1
和 di
Nd i= 1
表示。 对准工作是确定变换 T , 当应用
于数据点时得到最好的对准模型和数据。T 的参数由 一般的变换和相对应的 p 值列在表 1 p 维向量 a 表示。 中。 表 1, 出现在对准问题中的一般性变换, 表 2, 文章 的符号一览表。 对于二维对准 p= 3, T 的参数是旋转角 和平移向 量 t x , t y 。则得到参数向量 a = T 2D ( a ; x ) = T , t x , ty ; x = cos - sin , t x , t y , 我们定义: s in cos ty 2 for x ∈R x+ tx
