点云3DHarris角点检测算法推导

embedded/2024/11/30 10:45:49/

先回顾2D的Harris角点检测算法推导

自相关矩阵是Harris角点检测算法的核心之一,它通过计算图像局部区域的梯度信息来描述该区域的特征。在推导Harris角点检测算法中的自相关矩阵时,我们首先需要了解自相关矩阵的基本思想和数学背景。

参考

1. 能量函数的定义

在图像中,角点通常表现为局部区域内灰度值发生急剧变化的地方,因此,我们需要通过图像的梯度信息来量化图像变化的程度。为了描述图像在局部区域的变化程度,Harris角点检测算法使用了 能量函数,它度量了图像强度在局部区域内的变化。

首先,我们定义图像的梯度:

  • 水平梯度 I x = ∂ I ∂ x I_x = \frac{\partial I}{\partial x} Ix=xI
  • 垂直梯度 I y = ∂ I ∂ y I_y = \frac{\partial I}{\partial y} Iy=yI

然后,我们通过计算图像局部区域的强度变化,来定义 能量函数,该函数通常用梯度的平方来表示变化:
E = ∑ x , y ( ( I x ( x , y ) ) 2 + ( I y ( x , y ) ) 2 ) ⋅ w ( x , y ) E = \sum_{x, y} \left( \left( I_x(x, y) \right)^2 + \left( I_y(x, y) \right)^2 \right) \cdot w(x, y) E=x,y((Ix(x,y))2+(Iy(x,y))2)w(x,y)
其中, w ( x , y ) w(x, y) w(x,y) 是一个权重函数,通常使用 高斯窗口 来加权周围像素,以降低远离中心点的像素对结果的影响。

2. 协方差矩阵的推导

Harris算法的核心是通过 自相关矩阵 来描述局部图像的变化程度。我们从能量函数出发,推导出协方差矩阵的定义。自相关矩阵反映了局部区域的梯度变化,通常由以下几个部分组成:
M = ( ∑ w ( x , y ) I x 2 ( x , y ) ∑ w ( x , y ) I x ( x , y ) I y ( x , y ) ∑ w ( x , y ) I x ( x , y ) I y ( x , y ) ∑ w ( x , y ) I y 2 ( x , y ) ) M = \begin{pmatrix} \sum w(x, y) I_x^2(x, y) & \sum w(x, y) I_x(x, y) I_y(x, y) \\ \sum w(x, y) I_x(x, y) I_y(x, y) & \sum w(x, y) I_y^2(x, y) \end{pmatrix} M=(w(x,y)Ix2(x,y)w(x,y)Ix(x,y)Iy(x,y)w(x,y)Ix(x,y)Iy(x,y)w(x,y)Iy2(x,y))

2.1 矩阵元素的物理意义

这个自相关矩阵是通过局部区域的梯度信息构建的,矩阵的每个元素代表图像局部区域的梯度相关信息。具体来说:

  • M 11 = ∑ w ( x , y ) I x 2 ( x , y ) M_{11} = \sum w(x, y) I_x^2(x, y) M11=w(x,y)Ix2(x,y):表示图像在水平方向的变化强度,经过加权求和得到的值。
  • M 12 = M 21 = ∑ w ( x , y ) I x ( x , y ) I y ( x , y ) M_{12} = M_{21} = \sum w(x, y) I_x(x, y) I_y(x, y) M12=M21=w(x,y)Ix(x,y)Iy(x,y):表示图像在两个方向上的共同变化程度,衡量了水平方向和垂直方向的梯度协方差。
  • M 22 = ∑ w ( x , y ) I y 2 ( x , y ) M_{22} = \sum w(x, y) I_y^2(x, y) M22=w(x,y)Iy2(x,y):表示图像在垂直方向的变化强度。

这些加权求和的值构成了自相关矩阵 M M M,该矩阵包含了图像在局部区域的 梯度信息,用于描述局部特征。

2.2 局部平移不变性

图像中每个像素的梯度是局部信息的反映,而自相关矩阵 M M M 聚合了局部区域内所有像素的梯度信息。通过自相关矩阵计算的响应函数 R R R 对于平移变换具有不变性。即,如果我们平移图像的局部区域,计算出的响应函数值将不受平移影响,这使得Harris角点检测算法在不同位置的图像上都能得到一致的特征。

3. 响应函数

为了从自相关矩阵中提取角点,Harris算法定义了 响应函数 R R R,用于评估点 p i = ( x , y ) p_i = (x, y) pi=(x,y) 是否为角点。响应函数的定义如下:
R = det ( M ) − k ⋅ ( trace ( M ) ) 2 R = \text{det}(M) - k \cdot (\text{trace}(M))^2 R=det(M)k(trace(M))2

  • det ( M ) \text{det}(M) det(M) 是自相关矩阵 M M M 的行列式,表示局部区域的变化程度。
  • trace ( M ) \text{trace}(M) trace(M) 是自相关矩阵 M M M 的迹,表示图像梯度的总变化。
  • k k k 是经验常数,通常取值在 0.04 0.04 0.04 0.06 0.06 0.06 之间。

通过计算 R R R 值,Harris算法可以识别出角点。当 R R R 值较大时,说明该点局部区域的变化较大,且可能是角点。

4. 行列式和迹的几何意义

自相关矩阵的行列式和迹反映了图像局部区域的不同形状特征:

  • 行列式 det ( M ) \text{det}(M) det(M) 衡量的是局部区域在两个主方向上的变化程度。行列式较大表示局部区域在两个方向上都有较强的变化,通常对应于角点。
  • trace ( M ) \text{trace}(M) trace(M) 衡量的是局部区域的整体变化程度。如果局部区域在两个方向上的变化程度相似,则迹值较大,可能表示图像区域较为平坦,或是边缘区域。

5. 总结

自相关矩阵 M M M 是通过计算图像梯度的加权平方和得到的,它包含了图像局部区域的梯度信息。在Harris角点检测算法中,自相关矩阵用于描述局部区域的变化,通过计算行列式和迹来定义响应函数 R R R。响应函数可以帮助我们判断某个点是否为角点。这个过程结合了局部图像区域的梯度信息,能够有效地检测出角点等图像特征。


迹的意义

在 Harris 角点检测中,trace(矩阵的迹)是自相关矩阵 M M M 的一个重要特征,它反映了图像局部区域的总体变化。具体来说,矩阵的迹是其对角线元素的和,数学上表示为:
trace ( M ) = λ 1 + λ 2 \text{trace}(M) = \lambda_1 + \lambda_2 trace(M)=λ1+λ2
其中, λ 1 \lambda_1 λ1 λ 2 \lambda_2 λ2 是自相关矩阵 M M M 的两个特征值。

1. 迹的几何意义

自相关矩阵 M M M 描述了图像局部区域在 x − x- x y − y- y方向上的灰度变化。特征值 λ 1 \lambda_1 λ1 λ 2 \lambda_2 λ2 分别表示图像在这两个方向上的变化强度。

  • trace ( M ) = λ 1 + λ 2 \text{trace}(M) = \lambda_1 + \lambda_2 trace(M)=λ1+λ2 表示图像在这两个方向上的整体变化程度。它是矩阵对角线元素的和,反映了局部区域的总变化量。

2. 迹在 Harris 角点检测中的作用

在 Harris 角点检测中,响应函数 RR 是通过自相关矩阵的行列式和迹计算的,具体公式为:
R = det ( M ) − k ⋅ ( trace ( M ) ) 2 R = \text{det}(M) - k \cdot (\text{trace}(M))^2 R=det(M)k(trace(M))2
其中:

  • 行列式 det ( M ) = λ 1 λ 2 \text{det}(M) = \lambda_1 \lambda_2 det(M)=λ1λ2,表示图像局部区域沿两个主方向的整体变化强度。
  • trace ( M ) = λ 1 + λ 2 \text{trace}(M) = \lambda_1 + \lambda_2 trace(M)=λ1+λ2,表示图像局部区域的总变化程度。

迹的作用是提供对图像局部区域总变化的一个量化。它有以下几种作用:

2.1 描述整体变化程度

trace ( M ) \text{trace}(M) trace(M) 表示局部区域在两个方向上的总变化:

  • 如果迹较大,说明图像在这两个方向上的变化较强,可能是边缘或角点。
  • 如果迹较小,说明图像在这两个方向上的变化较弱,可能是平坦区域。
2.2 区分角点和边缘

在 Harris 角点检测中,行列式 det ( M ) \text{det}(M) det(M) 和迹 trace ( M ) \text{trace}(M) trace(M) 共同决定了一个点是否为角点。具体来说:

  • 角点:当 λ 1 \lambda_1 λ1 λ 2 \lambda_2 λ2 都较大时,表示图像在两个方向上都有显著变化,这时 R R R 的值较大,响应函数 R R R 也较大,通常认为该点为角点。
  • 边缘:当 λ 1 \lambda_1 λ1 很大, λ 2 \lambda_2 λ2 很小(或接近零)时,表示图像在一个方向上有显著变化,而在另一个方向上变化较小。这时,尽管迹值可能不小,但由于 λ 2 \lambda_2 λ2 较小,行列式 det ( M ) \text{det}(M) det(M) 也较小,导致 R R R 较小,响应函数值较小,因此不会被认为是角点。
  • 平坦区域:当 λ 1 \lambda_1 λ1 λ 2 \lambda_2 λ2 都较小,表示图像在两个方向上的变化都很弱,这时 trace ( M ) \text{trace}(M) trace(M) 较小,行列式 det ( M ) \text{det}(M) det(M) 也很小,响应函数值接近零,表示该点是平坦区域。
2.3 惩罚作用

在 Harris 角点检测的响应函数中,迹的平方项( k ⋅ ( trace ( M ) ) 2 k \cdot (\text{trace}(M))^2 k(trace(M))2)作为一个惩罚项,用于抑制那些虽然有较大行列式(即较强的变化),但局部变化是均匀的(即沿一个方向变化而另一个方向变化很小)的区域。这个惩罚项使得响应函数值对于边缘和角点之间的差异更加敏感,从而提高角点检测的准确性。

3. 总结

  • 迹(trace) 是自相关矩阵 M M M 中两个特征值的和,反映了图像局部区域在两个方向上的总体变化。
  • 在 Harris 角点检测中,迹 trace ( M ) \text{trace}(M) trace(M) 反映了图像局部变化的整体程度,结合行列式 det ( M ) \text{det}(M) det(M),通过响应函数 R R R 判断一个点是否为角点。
  • 通过响应函数中的迹项,可以有效区分角点、边缘和平坦区域,从而实现角点的检测。

为什么det(M)等于特征值的积

在矩阵的线性代数理论中,行列式特征值之间有着直接的关系。具体来说,对于一个 2 × 2 2 \times 2 2×2 的矩阵 M M M,其行列式等于该矩阵的特征值的乘积。这一结论可以通过以下推导来理解。

1. 矩阵的特征值与行列式的关系

假设矩阵 M M M 是一个 2 × 2 2 \times 2 2×2 的对称矩阵(因为自相关矩阵 M M M 通常是对称矩阵):
M = [ a b b c ] M = \begin{bmatrix} a & b \\ b & c \end{bmatrix} M=[abbc]
该矩阵的特征值是矩阵的本征值(eigenvalues),我们设其特征值为 λ 1 \lambda_1 λ1 λ 2 \lambda_2 λ2

为了计算特征值,需要解矩阵的特征方程:
det ( M − λ I ) = 0 \text{det}(M - \lambda I) = 0 det(MλI)=0
其中 I I I 是单位矩阵, λ \lambda λ 是特征值。矩阵 M − λ I M - \lambda I MλI 为:
M − λ I = [ a − λ b b c − λ ] M - \lambda I = \begin{bmatrix} a - \lambda & b \\ b & c - \lambda \end{bmatrix} MλI=[aλbbcλ]
它的行列式为:
det ( M − λ I ) = ( a − λ ) ( c − λ ) − b 2 = 0 \text{det}(M - \lambda I) = (a - \lambda)(c - \lambda) - b^2 = 0 det(MλI)=(aλ)(cλ)b2=0
展开得到:
λ 2 − ( a + c ) λ + ( a c − b 2 ) = 0 \lambda^2 - (a + c)\lambda + (ac - b^2) = 0 λ2(a+c)λ+(acb2)=0
这个方程的解就是 λ 1 \lambda_1 λ1 λ 2 \lambda_2 λ2,即矩阵 M M M 的特征值。

2. 行列式与特征值的关系

根据上面的特征方程,我们可以得到两个重要的结论:

  • 特征值的 λ 1 + λ 2 = a + c = trace ( M ) \lambda_1 + \lambda_2 = a + c = \text{trace}(M) λ1+λ2=a+c=trace(M),即矩阵的迹(trace)等于特征值的和。
  • 特征值的 λ 1 λ 2 = a c − b 2 = det ( M ) \lambda_1 \lambda_2 = ac - b^2 = \text{det}(M) λ1λ2=acb2=det(M),即矩阵的行列式(det)等于特征值的积。

3. 为什么行列式等于特征值的积

行列式 det ( M ) \text{det}(M) det(M) 是矩阵的一种不变量,它可以通过矩阵的特征值来表示。对于一个 n × n n \times n n×n 的矩阵 M M M,行列式可以写成所有特征值的积:
det ( M ) = ∏ i = 1 n λ i \text{det}(M) = \prod_{i=1}^{n} \lambda_i det(M)=i=1nλi
其中 λ i \lambda_i λi 是矩阵 M M M 的第 i i i 个特征值。

对于 2 × 2 2 \times 2 2×2 矩阵 M M M,其行列式就是特征值 λ 1 \lambda_1 λ1 λ 2 \lambda_2 λ2 的积,因此:
det ( M ) = λ 1 ⋅ λ 2 \text{det}(M) = \lambda_1 \cdot \lambda_2 det(M)=λ1λ2

4. 在 Harris 角点检测中的应用

在 Harris 角点检测中,矩阵 M M M 是局部图像窗口的自相关矩阵,通常表示为:
M = [ I x 2 I x I y I x I y I y 2 ] M = \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix} M=[Ix2IxIyIxIyIy2]
其中 I x I_x Ix I y I_y Iy 分别是图像在 x − x- x y − y- y方向的梯度。矩阵 M M M 的特征值 λ 1 \lambda_1 λ1 λ 2 \lambda_2 λ2 反映了图像局部区域在两个主方向上的变化程度:

  • 行列式 det ( M ) = λ 1 ⋅ λ 2 \text{det}(M) = \lambda_1 \cdot \lambda_2 det(M)=λ1λ2 反映了图像局部区域在两个方向上的整体变化强度。
  • trace ( M ) = λ 1 + λ 2 \text{trace}(M) = \lambda_1 + \lambda_2 trace(M)=λ1+λ2 反映了图像局部区域的总变化程度。

因此,行列式 det ( M ) \text{det}(M) det(M) 和迹 trace ( M ) \text{trace}(M) trace(M) 是用来区分图像角点、边缘和平坦区域的重要指标。


det(M − λI) = 0怎么来的

det(M − λI) = 0 这个等式是 特征值问题 的核心,它来源于 矩阵的特征方程,用于求解矩阵的特征值。让我们从头开始推导,理解为什么需要这个方程。

1. 特征值与特征向量的定义

假设我们有一个方阵 M M M,我们想要找到这个矩阵的特征值和特征向量。根据定义,一个特征值 λ \lambda λ 和特征向量 v \mathbf{v} v 满足以下关系:
M v = λ v M \mathbf{v} = \lambda \mathbf{v} Mv=λv
这里, v \mathbf{v} v 是非零向量,称为特征向量,而 λ \lambda λ 是与之对应的特征值。

2. 转化为矩阵方程

为了从上面的方程中解出特征值 λ \lambda λ,我们首先将其改写成以下形式:
M v − λ v = 0 M \mathbf{v} - \lambda \mathbf{v} = 0 Mvλv=0
将这个方程右边提取公共因子 v \mathbf{v} v 后,我们得到:
( M − λ I ) v = 0 (M - \lambda I) \mathbf{v} = 0 (MλI)v=0
这里, I I I 是单位矩阵,形状与矩阵 M M M 相同,$\lambda I 表示矩阵 $ λ \lambda λ 乘以单位矩阵。这个方程表示的是一个线性方程组,我们的目标是找到 λ \lambda λ v \mathbf{v} v

3. 求解非平凡解

为了让这个方程有非平凡解(即解不为零的特征向量 v \mathbf{v} v),根据线性代数的理论,矩阵 ( M − λ I ) (M - \lambda I) (MλI) 必须是 奇异矩阵(singular matrix)。即:
det ( M − λ I ) = 0 \text{det}(M - \lambda I) = 0 det(MλI)=0
这里的行列式为零是因为矩阵奇异的条件是它的行列式为零。当行列式为零时,矩阵的秩下降,导致存在非零解 v \mathbf{v} v

4. 得到特征值的特征方程

所以,求解特征值的过程就转化为求解以下方程:
det ( M − λ I ) = 0 \text{det}(M - \lambda I) = 0 det(MλI)=0
这个方程被称为 特征方程。解这个方程得到的 λ \lambda λ 就是矩阵 M M M 的特征值。

5. 如何求解特征值

特征方程是一个关于 λ \lambda λ 的多项式方程,方程的次数等于矩阵的大小(维度)。例如,对于一个 2 × 2 2 \times 2 2×2 矩阵 M M M,特征方程是一个二次方程,解得两个特征值 λ 1 \lambda_1 λ1 λ 2 \lambda_2 λ2

6. 举个例子

假设有一个 2 × 2 2 \times 2 2×2 矩阵 M M M
M = [ a b c d ] M = \begin{bmatrix} a & b \\ c & d \end{bmatrix} M=[acbd]
为了找到它的特征值,我们构造矩阵 ( M − λ I ) (M - \lambda I) (MλI)
M − λ I = [ a − λ b c d − λ ] M - \lambda I = \begin{bmatrix} a-\lambda & b \\ c & d-\lambda \end{bmatrix} MλI=[aλcbdλ]
然后,计算行列式:
det ( M − λ I ) = ( a − λ ) ( d − λ ) − b c \text{det}(M - \lambda I) = (a-\lambda)(d-\lambda) - bc det(MλI)=(aλ)(dλ)bc
展开后得到:
det ( M − λ I ) = λ 2 − ( a + d ) λ + ( a d − b c ) \text{det}(M - \lambda I) = \lambda^2 - (a+d)\lambda + (ad - bc) det(MλI)=λ2(a+d)λ+(adbc)
这就是矩阵 M M M 的特征方程。解这个方程可以得到 λ 1 \lambda_1 λ1 λ 2 \lambda_2 λ2,即矩阵的特征值。

7. 总结

特征值方程 det(M − λI) = 0 是从特征向量的定义出发推导出来的,目的是为了找出使得矩阵 M M M 在作用于特征向量时仅引起缩放而不改变方向的标量 λ \lambda λ,即特征值。通过解这个方程,我们可以得到矩阵的特征值,从而深入了解矩阵的性质。




奇异矩阵(Singular Matrix)

一个矩阵是 奇异矩阵,如果它不具有 逆矩阵。换句话说,一个矩阵 A A A 是奇异的,如果不存在一个矩阵 B B B,使得:
A ⋅ B = I A \cdot B = I AB=I
其中 I I I 是单位矩阵。简单来说,奇异矩阵是“无法反转”的矩阵。

奇异矩阵的几个特征

  1. 行列式为零: 奇异矩阵的一个最基本的特征是它的行列式(determinant)为零:
    det ( A ) = 0 \text{det}(A) = 0 det(A)=0
    行列式为零意味着矩阵在某些方面“退化”了,这也表示它的列向量(或行向量)是线性相关的。也就是说,矩阵的列或行之间存在线性依赖关系,无法形成一个完整的线性空间。

  2. 不可逆: 奇异矩阵无法求逆。对于一个方阵 A A A,如果它是奇异的,那么它就没有逆矩阵。只有行列式非零的矩阵才有逆矩阵。对于奇异矩阵来说,计算其逆矩阵会导致错误或不定义。

  3. 线性依赖: 如果矩阵 A A A 的行或列是线性相关的,即矩阵的某一行或某一列可以表示为其他行或列的线性组合,那么这个矩阵就是奇异矩阵。

  4. 秩小于矩阵的维度: 奇异矩阵的秩小于矩阵的维度。秩是一个矩阵的重要性质,表示矩阵列向量(或行向量)中线性无关的最大数目。如果矩阵的秩小于其维度(比如 n × n n \times n n×n 矩阵的秩小于 n n n),那么该矩阵就是奇异的。

直观解释

可以通过一个简单的二维矩阵来理解奇异矩阵。例如,考虑下面的 2 × 2 2 \times 2 2×2 矩阵:
A = [ 1 2 2 4 ] A = \begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix} A=[1224]
在这个矩阵中,第二行是第一行的两倍,因此它们是线性相关的。我们可以看到,这个矩阵的行列式为零:
det ( A ) = 1 × 4 − 2 × 2 = 0 \text{det}(A) = 1 \times 4 - 2 \times 2 = 0 det(A)=1×42×2=0
因为行列式为零,矩阵是奇异的,表示它无法反转。在几何意义上,这个矩阵表示一个缩放变换,其中两条线(列向量)落在了同一条直线上,导致它们无法提供完整的二维空间的基。

奇异矩阵的数学背景

考虑矩阵的特征值与特征向量问题,如果矩阵 A A A 是奇异的,那么它的行列式为零,意味着矩阵的某些特征值是零。特征值为零的矩阵无法被逆转(因为零不能作为逆的因子)。

在实际应用中,奇异矩阵常常表示数据丢失或线性相关性,可能会导致计算中的不稳定性。比如,在求解线性方程组时,如果矩阵是奇异的,可能没有唯一解。

如何判断一个矩阵是否奇异

  • 计算矩阵的行列式。如果行列式为零,则矩阵是奇异的。
  • 如果矩阵的秩小于它的行或列数,那么它也是奇异的。
  • 对于矩阵的特征值,若存在特征值为零的情况,则矩阵是奇异的。

举例:奇异矩阵与非奇异矩阵

非奇异矩阵

例如,考虑下面的矩阵:
B = [ 2 1 1 2 ] B = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix} B=[2112]
计算它的行列式:
det ( B ) = 2 × 2 − 1 × 1 = 4 − 1 = 3 \text{det}(B) = 2 \times 2 - 1 \times 1 = 4 - 1 = 3 det(B)=2×21×1=41=3
由于行列式不为零,矩阵 B B B 是非奇异的,存在逆矩阵。

奇异矩阵

再看一个例子:
C = [ 1 2 2 4 ] C = \begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix} C=[1224]
计算它的行列式:
det ( C ) = 1 × 4 − 2 × 2 = 4 − 4 = 0 \text{det}(C) = 1 \times 4 - 2 \times 2 = 4 - 4 = 0 det(C)=1×42×2=44=0
由于行列式为零,矩阵 C C C 是奇异矩阵,不能求逆。

总结

奇异矩阵是指没有逆矩阵的矩阵,它的行列式为零,矩阵的行或列是线性相关的,导致秩小于矩阵的维度。奇异矩阵通常用于表示一些在几何或物理模型中无法逆转的情况。




Harris 3D 关键点检测算法的数学推导

Harris 3D 算法是基于 Harris 角点检测 的思想扩展到 三维点云数据 上的。其基本思想是通过分析点云局部表面的变化,来寻找点云中显著的特征点(即关键点),通常用于在点云配准、三维重建等任务中提取关键特征。

Harris 3D 关键点检测的数学推导和过程通常包括以下几个步骤:

1. 局部点云表面估计

对于三维点云中的每个点 p i p_i pi,我们首先计算其 局部邻域,这个邻域是由点 p i p_i pi 周围一定范围内的点组成,通常使用 K-D树 或其他方式来搜索这些邻域点。

然后,我们使用 主成分分析(PCA) 来估计该点的 局部法线曲率,这些信息能够反映局部表面的几何特征。

具体步骤如下:

  • 对于点 p i p_i pi,通过其邻域点 N ( p i ) \mathcal{N}(p_i) N(pi) 来计算局部点云的 协方差矩阵 M M M
  • 协方差矩阵 M M M 是通过对邻域内每个点相对于 p i p_i pi 的位置进行偏差(即差值)求和得到的。

2. 协方差矩阵的计算

协方差矩阵 M M M 用于描述点云局部的几何形态。假设我们已经得到邻域点集 N ( p i ) = { p 1 , p 2 , … , p n } \mathcal{N}(p_i) = \{ p_1, p_2, \dots, p_n \} N(pi)={p1,p2,,pn},则协方差矩阵的计算公式为:
M = 1 ∣ N ( p i ) ∣ ∑ j ∈ N ( p i ) ( p j − p i ˉ ) ( p j − p i ˉ ) T M = \frac{1}{|\mathcal{N}(p_i)|} \sum_{j \in \mathcal{N}(p_i)} (p_j - \bar{p_i}) (p_j - \bar{p_i})^T M=N(pi)1jN(pi)(pjpiˉ)(pjpiˉ)T
其中, p i ˉ \bar{p_i} piˉ 是点 p i p_i pi 的邻域质心:
p i ˉ = 1 ∣ N ( p i ) ∣ ∑ j ∈ N ( p i ) p j \bar{p_i} = \frac{1}{|\mathcal{N}(p_i)|} \sum_{j \in \mathcal{N}(p_i)} p_j piˉ=N(pi)1jN(pi)pj
协方差矩阵 M M M 是一个 3 × 3 3 \times 3 3×3 矩阵,它的特征值反映了该点邻域内的 局部变化 情况。具体来说:

  • 特征值 λ 1 , λ 2 , λ 3 \lambda_1, \lambda_2, \lambda_3 λ1,λ2,λ3 描述了点云在各个主方向上的变化程度(即局部的变异程度)。其中 λ 1 \lambda_1 λ1 是最大的特征值,对应主方向, λ 2 \lambda_2 λ2 λ 3 \lambda_3 λ3 分别是次主方向和最小主方向的特征值。

对于点云中的每一个点 p i p_i pi,我们通过其邻域点 $\mathcal{N}(p_i) $计算出协方差矩阵 M M M。协方差矩阵反映了该点周围局部表面的几何特性,它是通过对该点邻域的点进行 PCA(主成分分析)来估计的。

协方差矩阵 M M M 通常是一个 3 × 3 3 \times 3 3×3 的矩阵,描述了点云局部区域的三维几何形态。协方差矩阵的特征值 λ 1 , λ 2 , λ 3 \lambda_1, \lambda_2, \lambda_3 λ1,λ2,λ3 反映了点云在各个主方向上的变化程度。

3. 响应函数的计算

Harris 3D 关键点检测的核心在于计算 响应函数 R R R,用来评估点 p i p_i pi 是否为一个关键点。这个响应函数通常与 协方差矩阵 的行列式和迹(trace)相关,公式为:
R = det ⁡ ( M ) − k ⋅ ( trace ( M ) ) 2 R = \det(M) - k \cdot (\text{trace}(M))^2 R=det(M)k(trace(M))2
其中:

  • det ⁡ ( M ) \det(M) det(M) 是矩阵 M M M 的行列式,反映了局部表面的 体积 变化,表明点云局部区域的变化程度。

  • trace ( M ) \text{trace}(M) trace(M) 是协方差矩阵的迹,即三个特征值的和,反映了局部表面变化的 总变异

  • k k k 是常数,通常取值在 [0.04,0.06][0.04, 0.06] 之间,用于控制响应函数的敏感度。

  • 行列式 det ⁡ ( M ) \det(M) det(M):反映了协方差矩阵的 体积,即局部点云区域的空间分布。行列式越大,意味着局部区域的几何变化越大,点云在局部区域内的分布更为分散。

  • trace ( M ) \text{trace}(M) trace(M):是协方差矩阵的对角线元素之和,反映了点云在各个方向上的总体变化程度。简单来说,迹是特征值的和:
    trace ( M ) = λ 1 + λ 2 + λ 3 \text{trace}(M) = \lambda_1 + \lambda_2 + \lambda_3 trace(M)=λ1+λ2+λ3
    迹越大,意味着局部点云区域的整体变化越显著。

4. 响应函数的解释

  • 如果 R R R 的值较大,意味着点 p i p_i pi 周围的表面变化非常显著(即有一个 显著的曲率变化)。这种点通常位于 边缘角点 等重要的几何特征处。
  • 如果 R R R 的值接近于零,意味着点 p i p_i pi 周围的表面几乎是平坦的,没有显著的几何变化。

5. 最大值抑制(Non-Maximum Suppression)

为了确保关键点是局部极值点,Harris 3D 会使用 最大值抑制 方法,在点云的邻域中抑制掉非极值点,只保留响应值 R R R 最大的点作为关键点。

6. 关键点的筛选

通过计算响应函数 R R R,我们可以得到每个点的显著性值。根据一个设定的阈值,筛选出关键点:

  • 如果 Threshold \text{Threshold} Threshold,则该点 p i p_i pi 被认为是一个关键点。

此外,通常还会使用 非最大抑制 来进一步去除那些在局部邻域内不具备最大响应的点。

总结:Harris 3D 关键点检测算法的数学推导过程

  1. 局部点云估计:对点 p i p_i pi 的邻域进行 PCA,计算协方差矩阵 M M M
  2. 协方差矩阵的特征值:计算协方差矩阵 M M M 的特征值 λ 1 , λ 2 , λ 3 \lambda_1, \lambda_2, \lambda_3 λ1,λ2,λ3,用于描述局部表面的变化。
  3. 计算响应函数:基于特征值计算响应函数 R R R
  4. 最大值抑制:通过非最大抑制来筛选出局部极值点。
  5. 关键点筛选:通过设定阈值来选择最终的关键点。

算法通过分析点云的 局部表面变化曲率,能够有效地提取出点云中的 角点边缘点,适用于在三维重建、点云配准等任务中的关键点提取。

Harris 3D 关键点检测的核心在于计算 响应函数 RR,用来评估点 pip_i 是否为一个关键点。这个响应函数反映了点云局部表面变化的显著性,通常与 协方差矩阵 MM 的行列式 det⁡(M)\det(M) 和迹(trace) trace(M)\text{trace}(M) 相关。




行列式

行列式是线性代数中两个非常重要的概念,它们在数学和工程中具有广泛的应用。它们不仅描述了矩阵本身的性质,还在解方程、特征值问题、几何学、图像处理等领域中起着重要作用。下面是对这两个概念的详细解释和它们的实际意义:

1. 行列式 (Determinant)

行列式是一个数值,表示矩阵在某些变换下的伸缩因子,反映了矩阵的“规模”或“体积”变化。行列式通常仅定义于方阵,即行数和列数相等的矩阵。

行列式的定义:

对于一个 n × n n \times n n×n 的方阵 A = [ a i j ] A = [a_{ij}] A=[aij],行列式记作 det ⁡ ( A ) \det(A) det(A) ∣ A ∣ |A| A,它是通过递归的方式计算的。对一个 $2 \times 2 $矩阵:
A = [ a b c d ] , det ⁡ ( A ) = a d − b c A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}, \quad \det(A) = ad - bc A=[acbd],det(A)=adbc
对于更高维的矩阵,行列式的计算则涉及到展开式。

行列式的几何意义:

行列式可以用来度量由矩阵表示的线性变换对空间体积的改变。对于一个方阵 A A A

  • 行列式的绝对值 ∣ det ⁡ ( A ) ∣ |\det(A)| det(A) 表示矩阵对应的线性变换对单位体积的 扩展缩放。例如,二维矩阵的行列式 ∣ det ⁡ ( A ) ∣ |\det(A)| det(A) 表示通过该变换后的单位平行四边形的面积,三维矩阵的行列式 $|\det(A)| $表示变换后的单位立方体的体积。
  • 行列式的符号:如果 det ⁡ ( A ) > 0 \det(A) > 0 det(A)>0,表示该线性变换没有改变空间的方向(例如,旋转或缩放);如果 det ⁡ ( A ) < 0 \det(A) < 0 det(A)<0,则表示空间的方向发生了反转(例如,镜像反射)。
行列式的实际意义:
  • 矩阵是否可逆:行列式是判断矩阵是否可逆的重要工具。如果 det ⁡ ( A ) = 0 \det(A) = 0 det(A)=0,矩阵 A A A 不可逆,即矩阵的列(或行)线性相关,表示矩阵在某些变换下将空间压缩到低维度。反之,如果 det ⁡ ( A ) ≠ 0 \det(A) \neq 0 det(A)=0,则矩阵是可逆的。
  • 求解线性方程组:行列式可以用来判断线性方程组是否有唯一解。如果系数矩阵的行列式为零,方程组可能没有解或有无穷多解。
  • 变换后的几何体积:在计算几何中,行列式可以用来计算空间变换(如旋转、缩放、剪切)对几何体积的影响。

2. 秩 (Rank)

秩是矩阵的一个重要概念,它描述了矩阵的线性独立性和有效维度。矩阵的秩反映了矩阵中行或列的最大线性独立数目。

秩的定义:

对于一个 m × n m \times n m×n 的矩阵 A A A,其秩 rank ( A ) \text{rank}(A) rank(A) 是矩阵中线性无关的行(或列)的最大数量。秩有以下几种定义方式:

  • 行秩:矩阵中最大数量的线性无关的行。
  • 列秩:矩阵中最大数量的线性无关的列。

根据 秩-零化定理,对于任意矩阵,其行秩等于列秩。

秩的几何意义:

秩可以看作是矩阵在空间中所能“张成”的最大维度:

  • 秩为 0:矩阵的所有行和列都是线性相关的,表示矩阵将整个空间压缩到一个点(或一条直线)。
  • 秩为 1:矩阵的行或列之间有一定的线性关系,但它们可以张成一条直线。
  • 秩为 2:矩阵的行或列可以张成一个平面。
  • 秩为 3:矩阵的行或列可以张成整个三维空间。
秩的实际意义:
  • 线性独立性:矩阵的秩反映了其列或行向量的线性独立性。如果矩阵的秩等于矩阵的列数(对于列满秩矩阵),那么矩阵的列是线性无关的,反之则存在线性相关的列。
  • 可逆性:如果矩阵是 n × n n \times n n×n 的方阵,且秩为 n n n,则矩阵是可逆的。
  • 矩阵的降维性:秩可以用来衡量矩阵数据的有效维度。在机器学习和信号处理中,秩常常与降维(例如,PCA、SVD等)相关,秩较小的矩阵表示数据的有效维度较低。
  • 解线性方程组:秩也可以用来判断线性方程组的解的个数。如果系数矩阵的秩小于方程组的未知数个数,方程组将有无穷多解;如果秩等于未知数的个数且等于增广矩阵的秩,则方程组有唯一解。

3. 行列式和秩的关系

  • 行列式和秩在判断矩阵是否可逆方面密切相关:
    • 如果矩阵的秩等于矩阵的行数(对于方阵),则行列式非零,矩阵可逆。
    • 如果矩阵的秩小于行数(对于方阵),则行列式为零,矩阵不可逆。

总结

  • 行列式反映了矩阵变换的规模和方向性,特别是对几何体积和变换的影响。如果行列式为零,矩阵是奇异的,表示空间被压缩至低维。
  • 反映了矩阵的线性独立性和它在空间中张成的有效维度。秩为零表示没有有效维度,秩为最大值则表示矩阵完全张成空间。

这两个概念在许多实际问题中都非常重要,尤其在数据分析、信号处理、优化、计算几何等领域有着广泛的应用。




代码

#include <pcl/io/pcd_io.h>
#include <pcl/point_types.h>
// 包含相关头文件
#include <pcl/keypoints/harris_3d.h>
#include "resolution.h" // 用于计算模型分辨率
typedef pcl::PointXYZ PointT;
int main(int argc, char** argv)
{// 读取点云pcl::PointCloud<PointT>::Ptr cloud(new pcl::PointCloud<PointT>);pcl::io::loadPCDFile(argv[1], *cloud);std::cout << "original cloud size : " << cloud->size() << std::endl;double resolution = computeCloudResolution(cloud);pcl::search::KdTree<pcl::PointXYZ>::Ptr tree(new pcl::search::KdTree<pcl::PointXYZ>());pcl::HarrisKeypoint3D<PointT, pcl::PointXYZI> detector;pcl::PointCloud<pcl::PointXYZI>::Ptr keypoints_temp(new pcl::PointCloud<pcl::PointXYZI>);detector.setNonMaxSupression(true);detector.setRadiusSearch(10 * resolution);detector.setThreshold(1E-6);detector.setSearchMethod(tree); // 不写也可以,默认构建kdtreedetector.setInputCloud(cloud);detector.compute(*keypoints_temp);pcl::console::print_highlight("Detected %d points !\n", keypoints_temp->size());pcl::PointCloud<PointT>::Ptr keys(new pcl::PointCloud<pcl::PointXYZ>);pcl::copyPointCloud(*keypoints_temp, *keys);system("pause");return 0;
}

你提供的代码实现了一个 Harris 3D 关键点检测 的功能,它是基于 PCL(Point Cloud Library)库的。这个代码的作用是从点云数据中检测关键点,通常用于点云的特征提取、配准或者其他三维处理任务。让我详细解析一下代码中的每个关键部分及其作用。

代码解析:

1. 读取点云数据:
pcl::PointCloud<PointT>::Ptr cloud(new pcl::PointCloud<PointT>);
pcl::io::loadPCDFile(argv[1], *cloud);
std::cout << "original cloud size : " << cloud->size() << std::endl;
  • 这部分代码使用 PCL 库的 pcl::io::loadPCDFile 函数从 PCD 文件(点云文件格式)加载数据,并将其存储在 cloud 变量中。
  • PointT 是点云数据类型,pcl::PointXYZ 表示三维坐标的点(x, y, z)。
  • 读取点云之后,输出原始点云的大小。
2. 计算模型分辨率:
double resolution = computeCloudResolution(cloud);
  • 这行代码计算了点云的分辨率,computeCloudResolution 是一个外部函数,可能根据点云的稀疏程度或其他特性来计算。
3. 初始化 Kd-Tree:
pcl::search::KdTree<pcl::PointXYZ>::Ptr tree(new pcl::search::KdTree<pcl::PointXYZ>());
  • 使用 Kd-Tree 结构作为邻域搜索的基础。Kd-Tree 是一种高效的数据结构,用于在点云中寻找最近邻点。
4. 初始化 Harris 3D 关键点检测器:
pcl::HarrisKeypoint3D<PointT, pcl::PointXYZI> detector;
  • HarrisKeypoint3D 是 PCL 库中实现的三维 Harris 关键点检测算法。它用于检测点云中显著的几何变化点(如角点或边缘点)。
5. 设置 Harris 3D 关键点检测的参数:
detector.setNonMaxSupression(true);  // 启用非极大值抑制
detector.setRadiusSearch(10 * resolution);  // 搜索半径,取决于点云分辨率
detector.setThreshold(1E-6);  // 阈值,用于控制检测到的关键点的显著性
detector.setSearchMethod(tree);  // 使用之前构建的 KdTree 进行邻域搜索
detector.setInputCloud(cloud);  // 输入点云数据
  • setNonMaxSupression(true):启用非极大值抑制,确保关键点是局部区域中最显著的点。
  • setRadiusSearch(10 * resolution):设置邻域搜索的半径为 10 * resolution,这是与点云分辨率相关的一个参数。
  • setThreshold(1E-6):设置关键点检测的阈值。小的阈值通常表示只有显著的变异区域才会被检测为关键点。
  • setSearchMethod(tree):指定使用 Kd-Tree 进行邻域查询,以加速搜索过程。
  • setInputCloud(cloud):将输入的点云数据传递给检测器。
6. 计算关键点:
pcl::PointCloud<pcl::PointXYZI>::Ptr keypoints_temp(new pcl::PointCloud<pcl::PointXYZI>);
detector.compute(*keypoints_temp);
  • 这行代码执行 Harris 3D 关键点检测,compute 方法会计算关键点并将结果存储到 keypoints_temp 中。
7. 输出检测结果:
pcl::console::print_highlight("Detected %d points !\n", keypoints_temp->size());
  • 输出检测到的关键点的数量。
8. 转换和存储关键点:
pcl::PointCloud<PointT>::Ptr keys(new pcl::PointCloud<pcl::PointXYZ>);
pcl::copyPointCloud(*keypoints_temp, *keys);
  • keypoints_temp 中的 pcl::PointXYZI 类型的关键点云转换为 pcl::PointXYZ 类型,后者只包含位置数据(不含强度信息)。
  • 将结果存储到 keys 中。
9. 程序暂停:
system("pause");
  • 程序会在此处暂停,通常是为了调试时查看输出结果。

主要算法原理:

Harris 3D 关键点检测算法是基于 Harris 角点检测 方法的一种三维扩展。其主要思想是利用点云局部区域的 变化率 来检测关键点:

  1. 对每个点,考虑其周围邻域的几何形状。
  2. 计算该邻域的协方差矩阵,通过矩阵的特征值来描述局部结构的变化情况。
  3. 通过特征值来判断点的显著性,特征值较大时表示该点周围的结构变化明显,通常是角点、边缘点或其他关键点。
  4. 非极大值抑制用于去除周围的冗余点,确保保留最显著的关键点。

适用场景:

  • 特征提取:可以用于点云配准、物体识别、三维重建等任务。
  • 关键点检测:有效地识别点云中的显著几何特征点(如角点、边缘点等)。

总结:

这段代码实现了基于 Harris 3D 方法的点云关键点检测功能,通过计算点云的局部几何特性,识别出在空间中变化显著的点,为后续的点云处理任务提供基础特征。


http://www.ppmy.cn/embedded/141724.html

相关文章

【CVPR24】One-Prompt to Segment All Medical Images

论文介绍 论文: One-Prompt to Segment All Medical Images 代码: https://github.com/KidsWithTokens/one-prompt 会议与年份&#xff1a;CVPR24 全文概述 本文介绍了一种新的医疗图像分割方法—One-Prompt Segmentation。传统的分割方法需要用户在推理阶段为每个样本提供提示…

buuctf-[SUCTF 2019]EasySQL 1解题记录

把你的旗帜给我&#xff0c;我会告诉你这面旗帜是对的。 堆叠注入查询数据库 1; show databases; ​ 查询表名 1; show tables; 获取flag 1;set sql_modepipes_as_concat;select 1

23种设计模式-抽象工厂(Abstract Factory)设计模式

文章目录 一.什么是抽象工厂设计模式&#xff1f;二.抽象工厂模式的特点三.抽象工厂模式的结构四.抽象工厂模式的优缺点五.抽象工厂模式的 C 实现六.抽象工厂模式的 Java 实现七.代码解析八.总结 类图&#xff1a; 抽象工厂设计模式类图 一.什么是抽象工厂设计模式&#xff1f…

【Qt】图片绘制不清晰的问题

背景 实现一个图片浏览器&#xff0c;可以支持放大/缩小查看图片。主要组件如下&#xff1a; // canvaswidget.h #ifndef CANVASWIDGET_H #define CANVASWIDGET_H#include <QWidget>class CanvasWidget : public QWidget {Q_OBJECT public:explicit CanvasWidget(QImag…

STM32 ADC --- 知识点总结

STM32 ADC — 知识点总结 文章目录 STM32 ADC --- 知识点总结cubeMX中配置注解单次转换模式、连续转换模式、扫描模式单通道采样的情况单次转换模式&#xff1a;连续转换模式&#xff1a; 多通道采样的情况禁止扫描模式&#xff08;单次转换模式或连续转换模式&#xff09;单次…

栩熙酷科技,抖音电商优势凸显

在当今数字经济迅猛发展的时代&#xff0c;电子商务已成为推动经济发展的重要力量。抖音电商作为新兴电商平台的代表&#xff0c;凭借其独特的流量优势和便捷的带货工具&#xff0c;吸引了众多企业的关注与入驻。成都栩熙酷网络科技有限公司&#xff08;以下简称“栩熙酷”&…

【Linux】vim

&#x1f33b;个人主页&#xff1a;路飞雪吖~ &#x1f320;专栏&#xff1a;Linux 目录 一、Linux开发工具 &#x1f31f;vim的基本概念 二、Linux编译器-gcc/g使用 &#x1f31f;gcc如何完成&#xff08;ESc - iso&#xff09; 1、预处理&#xff08;进行宏替换&#xff…

【CLIP】3: semantic-text2image-search允许局域网访问

前后端都是局域网的在同一局域网内的其他设备上,打开浏览器,访问 http://192.168.50.197:5173/。前端 前端默认是本地的 (semantic-text2image-search) root@k8s-master-pfsrv:/home/zhangbin/perfwork/01_ai/01_semantic-text2image-search/frontend# npm run dev> web@…