ICP配准算法

配准算法

  • 问题定义
  • ICP(point to point)算法思想步骤分解
  • point to point和point to plane的区别
  • ICP配准算法的标准流程
  • NDT

本篇将介绍配准算法,将介绍ICP(point to point)、ICP(point to plane)和NDT算法。其中ICP有两种,point to point表示通过构建点与点的对应关系完成代价损失的最优化,point to plane表示通过构建点到面的对应关系完成代价损失的最优化。

问题定义

配准算法就是通过迭代完成两个点集的旋转矩阵 R R R和平移矩阵 T T T的迭代求解。数学定义如下:
给定源点集 P , P = { p 1 , p 2 , . . . , p n } , p i ∈ R m P,P=\{p_1,p_2,...,p_n\},p_i\in R_m P,P={p1,p2,...,pn},piRm,和目标点击 Q = { q 1 , q 2 , . . . , q n } , q i ∈ R m Q=\{q_1,q_2,...,q_n\},q_i\in R_m Q={q1,q2,...,qn},qiRm。两个点集之间存在着旋转 R R R和平移 t t t的转化关系,构建如下损失函数(点与点在某个尺度上的距离), E ( R , t ) = 1 n ∑ i = 1 n ∥ q i − R p i − t ∥ 2 E(R, t)=\frac{1}{n} \sum_{i=1}^{n}\left\|q_{i}-R p_{i}-t\right\|^{2} E(R,t)=n1i=1nqiRpit2最优化损失函数 R , t = arg ⁡ R , t min ⁡ E ( R , t ) = arg ⁡ R , t min ⁡ 1 n ∑ i = 1 n ∥ q i − R p i − t ∥ 2 = ∥ Q − ( R P + t 1 T ) ∥ F 2 ,  s.t.  R R T = I m \begin{align} R, t&=\arg _{R, t} \min E(R, t) \\&=\arg _{R, t} \min \frac{1}{n} \sum_{i=1}^{n}\left\|q_{i}-R p_{i}-t\right\|^{2}{\tiny } \\ &= \left\|Q-\left(R P+t \mathbf{1}^{T}\right)\right\|_{F}^{2}, \text { s.t. } R R^{T}=I_{m} \end{align} R,t=argR,tminE(R,t)=argR,tminn1i=1nqiRpit2= Q(RP+t1T) F2, s.t. RRT=Im其中, P = [ p 1 , . . . , p n ] ∈ R m × n , p i ∈ R m Q = [ q 1 , . . . , q n ] ∈ R m × n , q i ∈ R m   1 = [ 1 , 1 , . . . , 1 ] T ∈ R n P = [p_1,...,p_n] \in R_{m \times n}, p_i \in R_m \\\\\\\\\\\\\\\\\\\\\\ Q = [q_1,...,q_n] \in R_{m \times n}, q_i \in R_m \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ \mathbf{1} = [1,1,...,1]^T \in R_n P=[p1,...,pn]Rm×n,piRmQ=[q1,...,qn]Rm×n,qiRm 1=[1,1,...,1]TRn得,也是Procrustes Transformation的求解过程 μ p = 1 n ∑ i = 1 n p i , μ 1 = 1 n ∑ i = 1 n q i P ′ = { p i − μ p } , Q ′ = { q i − μ q } O ′ P ′ T = U Σ V T R = U V T , t = μ q − R μ q \mu_p = {1 \over n} \sum_{i=1}^np_i, \mu_1 = {1 \over n} \sum_{i=1}^nq_i \\ P^{'} =\{ p_i - \mu_p \}, Q^{'}=\{q_i- \mu_q \} \\ O^{'}P^{'T} = U \Sigma V^T \\ R = U V^T, t = \mu_q-R\mu_q μp=n1i=1npi,μ1=n1i=1nqiP={piμp},Q={qiμq}OPT=UΣVTR=UVT,t=μqRμq其中 R , t R,t R,t即为集合P与Q之间的旋转平移,不过需要注意的是,这是迭代解,求出的只是当前集合状态的最优解。并不是最终解。

ICP(point to point)算法思想步骤分解

以ICP算法为例子,配准算法分为以下步骤:

  1. 给定集合P和Q,从中提取部分点(记为集合 s u b P , s u b Q subP,subQ subPsubQ)进行求解,可以使用随机采样,体素降采样,NSS采样和特征提取(比如ISS提取特征点)
  2. 选定匹配的若干点对,对于选出集合 s u b P subP subP中的每个点 p i p_i pi,在集合 s u b Q subQ subQ中找到邻居点。邻居点的尺度可以使用欧式空间最邻近思想,也可以是特征描述子空间的距离(对应ISS算法提取的特征点的特征描述子),也可以选用Normal shooting思想和Projection思想。要求双方互为最近邻居,并且为了算法的精度,可以仅仅使用点对距离超过某值的点对,或者选用相对距离前百分之k的点对。
    前两个都容易理解,后两个的直观表达如下:
    在这里插入图片描述
    在这里插入图片描述
  3. 构建point to point类型的优化函数进行迭代,完成当前迭代的旋转平移矩阵求解。
    R , t = arg ⁡ R , t min ⁡ E ( R , t ) = arg ⁡ R , t min ⁡ 1 n ∑ i = 1 n ∥ q i − R p i − t ∥ 2 = ∥ Q − ( R P + t 1 T ) ∥ F 2 ,  s.t.  R R T = I m \begin{align} R, t&=\arg _{R, t} \min E(R, t) \\&=\arg _{R, t} \min \frac{1}{n} \sum_{i=1}^{n}\left\|q_{i}-R p_{i}-t\right\|^{2}{\tiny } \\ &= \left\|Q-\left(R P+t \mathbf{1}^{T}\right)\right\|_{F}^{2}, \text { s.t. } R R^{T}=I_{m} \end{align} R,t=argR,tminE(R,t)=argR,tminn1i=1nqiRpit2= Q(RP+t1T) F2, s.t. RRT=Im4. 判断旋转平移矩阵的更新量是否已经满足阈值,如果是满足就终止,输出最后的结果。如果没有,就迭代到最大次数。

point to point和point to plane的区别

  • 算法思想的不同
    point to point和point to plane类型的ICP算法之间的优化函数构建思想不同。

    • 在点对点配准中,算法通过最小化两个点云之间的点与点之间的距离来实现配准。这意味着算法试图将一个点云中的每个点与另一个点云中的最近邻点对齐,然后通过优化来最小化它们之间的距离。
    • 点对点配准适用于两个点云表面之间存在较小的形变,并且点云中的噪声较少的情况。
    • 点对点匹配只是寻找了匹配点,点邻域内的信息没有使用,没有考虑上下文,并且最近邻查找的时候时间消耗大。
    • 在点对面配准中,不仅考虑了点的位置,还考虑了点的法线(即表面的朝向),从而更好地描述了表面的几何特征。
    • 点对面配准试图最小化一个点到另一个点云表面的法线方向上的投影之间的距离,而不仅仅是点之间的距离。这意味着算法不仅考虑了点的位置,还考虑了点云表面的曲率和法线方向,因此能够更好地处理曲面之间的配准。
    • 点对面配准通常比点对点配准更稳健,因为它们对点云中的噪声和表面曲率变化更具有鲁棒性
  • 优化函数求解不同
    point to point的优化函数形式为:
    R , t = arg ⁡ R , t min ⁡ E ( R , t ) = arg ⁡ R , t min ⁡ 1 n ∑ i = 1 n ∥ q i − R p i − t ∥ 2 \begin{align} R, t&=\arg _{R, t} \min E(R, t) \\&=\arg _{R, t} \min \frac{1}{n} \sum_{i=1}^{n}\left\|q_{i}-R p_{i}-t\right\|^{2}{\tiny } \\ \end{align} R,t=argR,tminE(R,t)=argR,tminn1i=1nqiRpit2point to plane的优化函数形式为: R , t = arg ⁡ R , t min ⁡ E ( R , t ) = arg ⁡ R , t min ⁡ 1 n ∑ i = 1 n ∥ ( R p i + t − q i ) T n i ∥ 2 \begin{align} R, t&=\arg _{R, t} \min E(R, t) \\&=\arg _{R, t} \min \frac{1}{n} \sum_{i=1}^{n}\left\|(R p_{i}+t-q_i)^Tn_i\right\|^{2}{\tiny } \\ \end{align} R,t=argR,tminE(R,t)=argR,tminn1i=1n (Rpi+tqi)Tni 2其中, n i n_i ni为点 q i q_i qi的法向量。
    对于point to plane的优化函数,采用最小二乘法的方式进行求解,计算过程如下,
    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

ICP配准算法的标准流程

  • 粗配置
    粗配准使用RANSAC+ISS+FPFH完成

    • 使用ISS算法完成点集P和Q的特征点提取,并计算FPFH特征描述子ru
    • 在特征描述空间寻找两个点集中关键点在对方集合中的配对点,构成配对点集集合。
    • 采用RANSAC算法,从配对点集中,选择3个点对。采用Procrustes Transformation的求解思路完成3个点对的 R , t R,t Rt求解
    • 根据得到的 R , t R,t R,t,完成源点云P的几何位置变换。然后计算配对点之间的几何距离,设置距离阈值,得到内点个数。
    • 如果内点个数满足阈值要求,就终止。如果不满足,就一直迭代到最大次数,选择所有迭代中内点比例最高的一次迭代的 R , t R,t R,t结果,作为ICP配准的初始解
  • 精配置
    精配准的时候,可以不用完成点云的降采样,选用全部点进行计算。尺度为欧式几何空间,在欧式空间中,寻找双方互为最近邻的配对点,保留TOP k进行P进行计算。

NDT

NDT算法有点复杂,NDT相对ICP而言,可以更好的利用周围邻域信息,有更好的鲁棒性,而且效率而比较高。具体思路等之后整理

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

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

相关文章

达梦备份与恢复

达梦备份与恢复 基础环境 操作系统:Red Hat Enterprise Linux Server release 7.9 (Maipo) 数据库版本:DM Database Server 64 V8 架构:单实例1 设置bak_path路径 --创建备份文件存放目录 su - dmdba mkdir -p /dm8/backup--修改dm.ini 文件…

NzN的数据结构--二叉树part1

你叉叉,让你学数据结构你不学;你叉叉,让你看二叉树你不看。 今天我们来一起学习二叉树部分,先赞后看是好习惯。 一、树的概念及结构 1. 树的概念 树是一种非线性的数据结构,它是由n(n>0)个有…

阿里云服务器可以干什么?阿里云服务器主要用途是干嘛的?

阿里云服务器可以干嘛?能干啥你还不知道么!简单来讲可用来搭建网站、个人博客、企业官网、论坛、电子商务、AI、LLM大语言模型、测试环境等,阿里云百科aliyunbaike.com整理阿里云服务器的用途: 阿里云服务器活动 aliyunbaike.com…

SpringCloud Alibaba Sentinel 规则持久化

一、前言 接下来是开展一系列的 SpringCloud 的学习之旅,从传统的模块之间调用,一步步的升级为 SpringCloud 模块之间的调用,此篇文章为第十七篇,即使用 Sentinel 实现规则持久化。 二、概述 从前面我们做的实验可知,…

4/7 QT_day1

#include "mainwindow.h"MainWindow::MainWindow(QWidget *parent): QMainWindow(parent) {//窗口设置this->setWindowTitle("小黑子(little black son)");this->setWindowIcon(QIcon("D:\\qq文件\\Pitrue\\pictrue\\black.jpg"));this-&g…

【数据结构与算法】:快速排序和冒泡排序

一,快速排序 快速排序是一种比较复杂的排序算法,它总共有4种实现方式,分别是挖坑法,左右"指针"法,前后"指针"法,以及非递归的快速排序,并且这些算法中也会涉及多种优化措施…

Tokenize Anything via Prompting

SAM的延续,把SAM输出的token序列用来进行分类,分割和一个自然语言的decoder处理,但其实现在多模态的图像的tokenizer也几乎都是用VIT来实现的。一开始认为这篇文章可能是关于tokenize的,tokenize还是很重要的,后来看完…

若依框架学习——分页查询列表

条件查询【多条件】列表展示【分页】SaCheckPermissionTableName TableId NotBlank Page分页 响应数据封装类

JMeter+Ant+Jenkins构建接口报告(无人驾驶版)

展示结果: uc浏览器打开测试报告,绿色显示脚本结果 搭建操作步骤如下 1.jemter写好脚本 2.下载并配置ant环境变量:加上activation.jar、commons-lang3-3.8.1.jar、mail.jar 这3个包 mail.jar需要引用到jmeter 3.下载安装Jenkins 并进行构建…

CKA 基础操作教程(六)

Kubernetes Deployments 理论学习 在 Kubernetes 中,Deployments 是一种资源对象,用于定义和管理容器化应用程序的部署过程, 容器化应用的声明式定义:使用 Deployments ,可以声明性地定义应用程序的部署配置&#x…

Vue使用高德地图

1.在高德平台注册账号 2.我的 > 管理管理中添加Key 3.安装依赖 npm i amap/amap-jsapi-loader --save 或 yarn add amap/amap-jsapi-loader --save 4.导入 AMapLoade import AMapLoader from amap/amap-jsapi-loader; 5.直接上代码,做好了注释(初始化…

初识ES(ES的基本概念、倒排索引、索引和文档的CRUD)

1、ES是什么? 一个开源的分布式搜索引擎,可以用来实现搜索、日志统计、分析、系统监控等功能。ES的底层是基于Lucene实现的。 Lucene是一个Java语言的搜索引擎类库。 什么是elastic stack(ELK)? elasticsearch。存储、…

实验室用进口高纯聚四氟乙烯材质PFA方盘抗酸碱耐高温PFA托盘

PFA方盘又称托盘:耐高温、耐腐蚀。 进口透明可溶性聚四氟乙烯方盘。可应用于成膜实验,样品液体脱漏等。能放在电热板上直接加热使用,也可以用于烘箱烘干,实验室腐蚀性样品的转移和搬运,防止腐蚀性液体洒落。 产品特性…

Python常用算法--解决数据结构问题【附源码】

一、约瑟夫环问题 解释:约瑟夫环(Josephus Problem)是一个著名的数学问题,它描述了一个关于围坐一圈的人进行游戏的场景。游戏规则是从一个人开始,顺序报数,每报到特定数目的人将会被排除出圈子,然后从被排除的下一人开始继续报数,游戏继续进行直到最后剩下一个人。 …

ETL工具-nifi干货系列 第九讲 处理器EvaluateJsonPath,根据JsonPath提取字段

1、其实这一节课本来按照计划一起学习RouteOnAttribute处理器(相当于java中的ifelse,switch case 控制语句),但是在学习的过程中遇到了一些问题。RouteOnAttribute 需要依赖处理器EvaluateJsonPath,所以本节课我们一起…

如何确定螺栓的载荷和扭矩——SunTorque智能扭矩系统

智能扭矩系统-智能拧紧系统-扭矩自动控制系统-SunTorque 螺栓作为一种常见的紧固件,广泛应用于各种机械和设备中。正确确定螺栓的载荷及其扭矩对于确保设备的安全运行和延长其使用寿命至关重要。本文将探讨如何确定螺栓的载荷及其扭矩,帮助读者更好地理…

将excel,csv中合并块中某条记录的值应用到整个块(使用多行的值,来填充新列数据)。

背景描述 在excel中使用其它列的值,根据某种计算规则来填充另一列(或新列)很容易实现。但是如果需要根据合并块中的多行来填充列时,就不容易实现,由于对excel不是太常用,因此这里使用的命令行工具实现的。…

K8s学习三(Pod与探针)

深入学习Pod Pod配置文件 写一个自己的配置文件,nginx-po.yaml apiVersion: v1 #api文档版本 kind: Pod #资源类型对象,也可以配置为像Development,StatefulSet这一类的对象 metadata: # Pod相关的元数据,用于描述Pod的数据name: nginx-po…

4月7号总结

java学习 一.正则表达式 定义:正则表达式是一种用于描述字符串模式的表达式,通常被用于文本搜索、匹配和替换。它是一种强大的工具,可以在文本处理和文本分析中进行复杂的匹配和操作。 通过字符串引用里面的方法matches,然后执行…

【Web】纯萌新的CISCN刷题记录(1)

目录 [CISCN 2019华东南]Web11 [CISCN 2019华北Day2]Web1 [CISCN 2019初赛]Love Math [CISCN 2022 初赛]ezpop [CISCN 2019华东南]Double Secret [CISCN 2023 华北]ez_date [CISCN 2019华北Day1]Web1 [CISCN 2019华东南]Web4 [CISCN 2019华北Day1]Web2 [CISCN 2023 …