Least-Squares Rigid Motion Using SVD——文献精读(使用 SVD 方法求解 ICP 问题)

一、文章信息与摘要

文章标题:Least-Squares Rigid Motion Using SVD使用奇异值分解的最小二乘刚性运动

说明本文的核心目标:计算对齐两组对应点的最佳拟合刚性变换的步骤

二、问题描述

假设P={p1,p2,...,pn}Q={q1,q2,...,qn}是两组Rd空间中的对应点集,现在想要根据这个两个点集的数据来计算出它们之间的刚性转置信息,可以知道这其实是一个最小二乘求优问题

目标:我们希望找到一个使两个集合在最小二乘意义下最优对齐的刚性变换,即寻找一个旋转矩阵 R 和平移向量 t,满足如下关系:

其中, 𝑤𝑖 表示每个点的权重。 𝑆𝑂(𝑑表示 d 维空间的一组旋转群。

三、计算平移向量t和旋转矩阵

计算平移向量t的推导过程:

计算旋转矩阵的推导过程:

四、反射修正

为什么要进行反射修正?

答:通过之前的推导,我们用 SVD 求解的 R 一定是一个正交矩阵,但并非所有正交矩阵都是旋转矩阵,还可能是反射,因此要进行判断。

旋转矩阵的定义:旋转矩阵是一个用来表示在欧几里得空间中的点或向量围绕一个固定轴的旋转的正交矩阵。

旋转矩阵—>正交矩阵,但正交矩阵不能推导出旋转矩阵。举个反例:

  • 因此我们还需要对所求得的 R 进行行列式判断,判断方法:
  • 如果 det⁡(𝑉𝑈⊤)=−1,则所求的 R 包含了镜像;
  • 如果 det⁡(𝑉𝑈⊤)=1,则所求的 R 是我们所求的旋转矩阵。
  • 反射的最优化问题

    如果确定了𝑅包含反射(det(𝑉𝑈𝑇〖VU〗^T)=−1),我们接下来的目标是找到一个反射矩阵𝑀,它能最大化迹的函数𝑡𝑟(Σ𝑀) 。这里的迹函数只依赖于 𝑀的对角线元素𝑚𝑖𝑖。我们将这些对角线元素视作变量,它们构成了所有反射矩阵对角线的集合。由于反射矩阵可以通过反转旋转矩阵的一行来构建,所以优化集合是点 (±1,...,±1) 的凸包,其中坐标−1的个数是奇数。

    凸多面体和极值

    由于我们处理的领域是一个凸多面体,线性函数𝑓在其顶点达到极值。因此,我们寻找的最优解是在这些顶点之一。其中对角线全为1(即没有 −1)不在考虑的范围内,所以次优的选择是在最后一个元素为 −1的情况,即 𝑡𝑟(Σ𝑀)=𝜎1"σ" _1+ 𝜎2 "σ" _2  +…+ 𝜎d−1 "σ" _(d-1)   𝜎d "σ" _d  。这个值是在我们的域的一个顶点上取得的,除了全1情况外,是所有可能组合中最大的,因为 𝜎d"σ" _d是最小的奇异值(因为SVD 分解特征值是从大到小排序)

    总结

    如果 det(𝑉𝑈𝑇〖VU〗^T)=−1,我们需要的 𝑀=𝑉𝑇𝑅𝑈V^T RU的形式,其中最后一个元素为 −1即:

  • 我们还可以总结出一个更一般的公式,无论 det(𝑉𝑈𝑇〖VU〗^T)等于−1还是−1R 都可以表示为:

五、总结

经过上面的推导和镜像修正,我们可以总结出一套完整的使用 SVD 求解 ICP 问题的流程:

我们的问题是求解 R, t 使得下面的误差函数最小:

步骤如下:

  1. 1.计算两个点的加权质心;

2.对所有点做归一化;

3.计算d x d 的协方差矩阵d代表数据维度);

4.SSVD分解S= 𝑈Σ𝑉𝑇〖UΣV〗^T,则得到想要求的旋转矩阵R如下:

5.计算平移向量t

六、本文的扩展——点云配准中的ICP算法

ICP Iterative Closest Point,迭代最近点)算法是一种广泛应用于计算机视觉和机器人领域的技术,主要用于在两组数据点之间找到最佳的对齐方式。通过不断地迭代,每次在前一次的计算结果之上再计算出新的变换矩阵,最终当迭代次数满足条件或者变换矩阵收敛时停止ICP广泛应用于3D重建、机器人定位、医疗影像处理等领域。

原理

ICP算法的基本步骤如下:

1. 选择对应点:在两组点云中,为每个点找到对应的最近点。这些对应点构成了点云之间的初步匹配。
2. 最小化误差:计算一个变换(包括旋转 矩阵 R 和平移向量 t ),使得这些对应点之间的距离(即误差)最小化。常用的求解 R t 的方法有: SVD 非线性优化,但非线性优化的描述比较繁琐,通常采用 SVD 方法。
3. 应用变换:将变换应用到其中一组点云上,使其更好地与另一组点云对齐。
4. 迭代优化:重复上述步骤,每次都在更新后的点云基础上进行对应点选择和误差最小化,直到变换达到稳定或误差小于某个阈值。

优点:简单,不必对点云进行分割和特征提取;初值较好情况下,精度和收敛性都不错

缺点对初始变换敏感,容易陷入局部最优解;只考虑了点与点距离,缺少对点云结构信息的利用

实际使用中的一些注意事项

ICP 比较依赖于变换初值,平移比较简单,直接用点云质心来估计;旋转初值的话可以手动调一个粗略值,或者沿每个轴的旋转进行采样、组合来尝试(不适合实时性应用);
点太多的话可以先降采样;
找到一些 anchor 点对(比如先用特征点匹配),可以帮助加速收敛;
对应用场景引入一些合理假设,比如限制旋转、平移的范围,变换自由度数量等
ICP改进算法名称简介

Point-to-Plane ICP

原始 ICP 算法的代价函数中使用的 point-to-point 距离,point-to-plane 则是考虑源顶点到目标顶点所在面的距离,比起直接计算点到点距离,考虑了点云的局部结构,精度更高,不容易陷入局部最优;但要注意 point-to-plane 的优化是一个非线性问题,速度比较慢,一般使用其线性化近似;

Plane-to-Plane ICP

point-to-plane 只考虑目标点云局部结构, plane-to-plane 顾名思义就是也考虑源点云的局部结构,计算面到面的距离

Generalized ICP (GICP)

综合考虑 point-to-pointpoint-to-plane plane-to-plane 策略,精度、鲁棒性都有所提高;

Normal Iterative Closest Point (NICP)

考虑法向量和局部曲率,更进一步利用了点云的局部结构信息,其论文中实验结果比 GICP 的性能更好。

七、本文的扩展——常见点集配准技术:RPM

Robust point matchingRPM

RPM算法的核心是通过软对应和确定性退火过程来逐步达到精确匹配:

1.软对应:RPM算法中每个点可以部分地与多个点对应,这种软对应由一个“对应矩阵”来表示,该矩阵中的每个元素表示两点之间的匹配程度。

2.确定性退火:算法引入了退火技术,通过逐渐减小“温度”参数来从宽松的匹配逐步过渡到严格的匹配。高温度允许点对之间有更大的自由度,随着温度的降低,算法逐步锁定更精确的对应关系。

3.变换优化:在每个退火步骤中,算法通过优化变换参数(旋转、缩放、平移)来最小化配准误差,通常使用迭代最小化方法。

优点:由于引入了退火过程,RPM算法不如ICP算法那样依赖于初始位置,能够从较差的初始状态恢复;软对应机制使得RPM能够处理局部遮挡问题,不要求两个点集具有完全相同的点数或结构。

缺点RPM算法的计算复杂度高于传统ICP算法,尤其是在点集较大时,计算量和时间消耗显著增加。算法效果很大程度上依赖于退火过程中温度下降策略和其他参数的选择,这些参数的设定需要根据具体问题仔细调整,可能需要较多的实验和专业知识。

八、本文的扩展——常见点集配准技术:KC

Kernel correlationKC

KC算法的核心是利用核函数来转换和比较数据集,其基本步骤如下:

1.数据转换:使用核函数将原始数据映射到一个高维特征空间。常用的核函数包括高斯核、多项式核等

2.核相关计算:在特征空间中,通过计算两个映射后的数据集的内积(或相似度)来评估它们的相关性。核相关的值越高,表示两个数据集越相似。

3.归一化:通常需要对核相关值进行归一化处理,确保结果的稳定性和可比性。

优点:通过使用核函数,KC算法能有效处理非线性的数据,显著提高模型的灵活性和适用范围提供了一种在复杂数据集间进行深入相似度评估的有效工具。

缺点:映射数据到高维空间可能导致计算成本高算法性能在很大程度上依赖于核函数的选择,不恰当的核函数可能导致性能不佳参数敏感:核参数(如在高斯核中的带宽)的选择对结果有显著影响,需要仔细调整以获得最佳性能。

九、本文的扩展——常见点集配准技术:CPD

Coherent point driftCPD

CPD算法的核心思想基于概率方法,将点集配准问题视为一个概率密度估计问题。算法的基本步骤包括:

1.概率模型:将一个点集视为高斯混合模型(GMM)中心的“静态”点集,而另一个点集则被视为来自这个模型的“动态”样本。

2.期望最大化(EM)算法CPD使用EM算法来估计配准的参数。在期望步骤(E-step),算法计算每个点对模型中每个高斯成分的责任度(即该点来自某个高斯成分的概率)。在最大化步骤(M-step),根据这些责任度更新变换参数和GMM参数。

3.变换估计CPD支持刚体、仿射和非刚体变换,可以根据实际应用需求选择相应的模型进行点集配准。

优点:CPD算法对噪声和异常值具有很好的鲁棒性,可以有效处理不完整或部分遮挡的数据。支持多种类型的变换,包括刚体、仿射和非刚体变换无需手动标定或预处理,算法能够自动对点集进行有效配准。

缺点:由于涉及复杂的迭代计算和概率模型,CPD算法在处理大规模数据时可能会有较高的计算成本;算法性能在一定程度上依赖于参数的选择,如高斯混合模型的宽度参数等,这些参数需要根据具体的数据情况仔细调整在某些情况下,CPD算法可能需要较多的迭代次数才能收敛,特别是在点集规模较大或数据复杂度较高的情况下。

十、本文的扩展——常见点集配准技术的对比

参考文章:

点集配准技术(ICP、RPM、KC、CPD) - 算法小丑 - 博客园 (cnblogs.com)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/672365.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

以sqlilabs靶场为例,讲解SQL注入攻击原理【25-31关】

【Less-25】 首先分析源码 发现把 SQL语句中的 or、and 替换成了空格,这就导致无法使用之前的sql注入方式。 解决方案:用 && 代替 and , 用 || 代替 or , 而且&在url中有特殊含义,如果直接使用会有问题&a…

电磁兼容(EMC):BUCK变换器基本原理及传导辐射分析设计

目录 1. BUCK电路拓扑及原理 2. Buck拓扑电路电磁场分析 3.总结 开关电源替代线性电源,解决了效率和体积问题,但也带来了新的EMI问题。开关电源也是产品内部的强辐射源之一,基于透过现象看本质,将复杂问题简单化,本…

2024年06月在线IDE流行度最新排名

点击查看最新在线IDE流行度最新排名(每月更新) 2024年06月在线IDE流行度最新排名 TOP 在线IDE排名是通过分析在线ide名称在谷歌上被搜索的频率而创建的 在线IDE被搜索的次数越多,人们就会认为它越受欢迎。原始数据来自谷歌Trends 如果您相…

JAVA流程控制--For循环

1.虽然所有循环都可以用while或do...while表示,但Java提供了另外一种语句——for循环,使一些循环结构变得简单 2.for循环语句是支持迭代的一种通用结构,是最有效,最灵活的循环,结构 3.for循环执行的次数是在…

快速排序(排序中篇)

1.快速排序的概念及实现 2.快速排序的时间复杂度 3.优化快速排序 4.关于快速排序的细节 5.总代码 1.快速排序的概念及实现 1.1快速排序的概念 快速排序的单趟是选一个基准值,然后遍历数组的内容把比基准值大的放右边,比基准值小的放在左边&#xf…

编译原理【第四+七章】

考试题 1、简述语法制导翻译的基本思想 将语法分析和语义分析结合起来,通过语法规则驱动语义动作执行,用于将源程序翻译成目标代码或中间代码。 通过使用属性和语义动作,编译器可以在语法分析的同时生成目标代码或中间代码,实现…

网络原理——TCP/IP--数据链路层,DNS

T04BF 👋专栏: 算法|JAVA|MySQL|C语言 🫵 今天你敲代码了吗 目录 数量链路层目的地址和原地址类型校验和 DNS 数量链路层 主要的协议是以太网协议.一个横跨数据链路层和 物理层的协议,既包含了数据链路层的内容, 也包含了⼀些物理层的内容 我们来了解一…

STM32作业实现(五)温湿度传感器dht11

目录 STM32作业设计 STM32作业实现(一)串口通信 STM32作业实现(二)串口控制led STM32作业实现(三)串口控制有源蜂鸣器 STM32作业实现(四)光敏传感器 STM32作业实现(五)温湿度传感器dht11 STM32作业实现(六)闪存保存数据 STM32作业实现(七)OLED显示数据 STM32作业实现(八)触摸按…

官网上线,一款令人惊艳的文本转语音模型:ChatTTS

近日,一个名为 ChatTTS 文本转语音模型的项目在github上横空出世,一经推出便引发极大关注,短短四天时间,已经狂揽了14.2k的Start量。 ChatTTS是一款专为对话场景设计的支持中英文的文本转语音(TTS)模型&…

AGM DAP-LINK 离线烧录报错信息分析

DAP-LINK 支持离线烧录。 即:先把要烧录的bin 烧录到DAP-LINK 中;然后DAP-LINK 可以脱离PC,上电后通过按键对目标板进行烧录。 CMSIS-DAP模式 跳线JGND断开,状态LED D4快闪,D3常亮(串口状态)。…

服务失败后如何重试?

服务失败后如何重试? 在分布式系统和网络应用程序中,重试策略对于有效处理瞬时错误和网络不稳定性至关重要。 重试策略能让系统在发生故障时多次尝试操作,从而提高最终成功的可能性。 下图显示了 4 种常见的重试策略。 01 线性回退 线性回…

LabVIEW开发中对RS-232、RS-485、RS-422通讯的比较及注意事项

本文介绍了LabVIEW开发中常用的RS-232、RS-485和RS-422通讯方式的区别及各自特点,详细说明了它们的适用场景和开发过程中需要注意的问题,帮助开发人员在选择和实现通讯方式时做出最佳决策。 详细说明 RS-232、RS-485、RS-422通讯简介 RS-232、RS-485和…

虚幻引擎5 Gameplay框架(四)

Gameplay重要类及重要功能使用方法(三) 虚幻的委托机制 虚幻委托之间的区别序列化就是是否可以在蓝图中执行 多播与单播的创建 制作功能:使用多播与单播将血条与血量进行实时更新首先新建一个单播与一个多播委托 实例化这两个委托的标签…

西门子电梯控制保姆级教程

一、电梯运行控制 1.电梯控制系统结构 可以理解是通过ip进行访问的 2.基于PLCSIM Adv与电梯仿真软件的控制环境搭建 虽然都是用一台电脑来控制,但是还是用以太网来连接 在FC块里面也要用两个DB块来放输入和输出 二、电梯对象的分析 在eet里面,用手动控制…

关于高版本 Plant Simulation 每次保存是 提示提交comm对话框的处理方法

关于高版本 Plant Simulation 每次保存是 提示提交comm对话框的处理方法 如下图 将model saving history 修改为None即可 关于AutoCAD 2022 丢失模板库的问题 从新从以下地址打开即可: D:\Program Files\Autodesk\AutoCAD 2022\UserDataCache\zh-cn\Template

LabVIEW步进电机的串口控制方法与实现

本文介绍了在LabVIEW环境中通过串口控制步进电机的方法,涵盖了基本的串口通信原理、硬件连接步骤、LabVIEW编程实现以及注意事项。通过这些方法,用户可以实现对步进电机的精确控制,适用于各种自动化和运动控制应用场景。 步进电机与串口通信…

python--面向对象-文件读写-异常

一、继承 定义一个类时,需要使用另外一个类的方法或属性,就可以通过继承实现 object是Python的顶级类,创建类是会自动继承,就拥有object中的方法 定义格式 # 类的定义 # 旧式类定义 一般在定义单个类时使用 class 类名:name N…

Nginx01-HTTP简介与Nginx简介(安装、命令介绍、目录介绍、配置文件介绍)

目录 HTTP简介HTTP原理查看访问网站的详细流程curl -vwget --debug 查看网站访问量HTTP协议版本HTTP协议交互HTTP 请求请求报文起始行请求头 HTTP响应响应报文起始行响应头 Nginx常见的Web服务常见网站服务 安装NginxNginx目录结构Nginx启动管理Nginx常用命令 Nginx配置文件主配…

牛客周赛 Round 45VP

这场应该是十分仁慈的一场了 1.签到&#xff1a;https://ac.nowcoder.com/acm/contest/84244/A AC代码&#xff1a; #include<bits/stdc.h> using namespace std; int a,b,c,d,e; int main() {cin>>a>>b>>c>>d>>e;int sabcde;if(s>1…

关于nodejs单线程

Node是使用C++语言写的一款JavaScrip解析器。 高并发 一般来说,高并发的解决方案就是多线程模型,服务器为每隔客户端请求分配一个线程,使用同步I/o,比如Apache就是这种策略,由于I/O一般都是耗时操作,因为这种策略很难实现高性能,但非常简单,可以实现复杂的交互逻辑。…