插值、拟合、积分

Last updated on May 7, 2023 pm

[TOC]

Overview

  • 插值:求过已知有限个数据点的近似函数。

  • 拟合:已知有限个数据点,求近似函数,不要求过已知数据点,只要求在某种意义下它在这些点上的总偏差最小。

插值和拟合都是要根据一组数据构造一个函数作为近似,由于近似的要求不同,二者的数学方法上是完全不同的。而面对一个实际问题,究竟应该用插值还是拟合,有时容易确定,有时则并不明显。

插值

Comparison of 1D and 2D Interpolations

最近邻插值

1D Nearest Interpolation

2D Nearest Interpolation

\[ \mathbf{I}_\mathrm{dst}(i, j) = \mathbf{I}_\mathrm{src}(u^{\prime}, v^{\prime}) = \mathbf{I}_\mathrm{src}(u, v) \]

with

\[ (i, j) \Rightarrow (u^{\prime}, v^{\prime}) \Rightarrow \begin{cases} u = \text{round}(u^{\prime}) \\ v = \text{round}(v^{\prime}) \end{cases} \]

1
2
3
4
5
case INTERPOLATION_NEAREST: {
int lx = static_cast<int>(std::round(x));
int ly = static_cast<int>(std::round(y));
result = (this)(ly, lx);
}

线性插值

Linear Interpolation (Lerp)

Bilinear Interpolation

\[ \mathbf{I}_\mathrm{dst}(i, j) = \mathbf{I}_\mathrm{src}(u^{\prime}, v^{\prime}) = \mathbf{I}_\mathrm{src}(u+\alpha, v+\beta) \]

with

\[ (i, j) \Rightarrow (u^{\prime}, v^{\prime}) \Rightarrow \begin{cases} u = \text{floor}(u^{\prime}) = \lfloor u^{\prime} \rfloor \\ v = \text{floor}(v^{\prime}) = \lfloor v^{\prime} \rfloor \end{cases} \Rightarrow \begin{cases} \alpha = u^{\prime} - u \\ \beta = v^{\prime} - v \end{cases} \]

\[ \begin{aligned} f_{00} &= f(u, v) \\ f_{01} &= f(u, v + 1) \\ f_{10} &= f(u + 1, v) \\ f_{11} &= f(u + 1, v + 1) \end{aligned} \]

(1) V方向线性插值

\[ \begin{cases} f(u, & v+\beta) = (f_{01} - f_{00}) \beta + f_{00} \\ f(u+1, & v+\beta) = (f_{11} - f_{10}) \beta + f_{10} \end{cases} \]

(2) U方向线性插值

\[ f(u+\alpha, v+\beta) = [f(u+1, v+\beta) - f(u, v+\beta)]\alpha + f(u, v+\beta) \]

(3)最终

\[ f(u+\alpha, v+\beta) = [(1-\alpha)(1-\beta)]f_{00} + \beta (1-\alpha) f_{01} + \alpha (1-\beta) f_{10} + \alpha \beta f_{11} \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
case INTERPOLATION_BILINEAR: {
const int lx = std::floor(x);
const int ly = std::floor(y);

T f00 = (this)(ly, lx);
T f01 = (this)(ly + 1, lx);
T f10 = (this)(ly, lx + 1);
T f11 = (this)(ly + 1, lx + 1);

double alpha = x - lx;
double beta = y - ly;

result =
(1 - beta) * ((1 - alpha) * f00 + alpha * f10) +
beta * ((1 - alpha) * f01 + alpha * f11);
}

Spherical Linear Interpolation (Slerp)

  • Ref: ESKF 2.7
  • https://splines.readthedocs.io/en/latest/rotation/slerp.html

\[ \mathbf{q}(t)=\mathbf{q}_{0} \frac{\sin ((1-t) \Delta \theta)}{\sin (\Delta \theta)}+\mathbf{q}_{1} \frac{\sin (t \Delta \theta)}{\sin (\Delta \theta)} \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Quaterniond slerp(double t, Quaterniond &q1, Quaterniond &q2) {
Quaterniond q_slerp;
float cos_q1q2 = q1.w() * q2.w() + q1.x() * q2.x() + q1.y() * q2.y() + q1.z() * q2.z();

if (cos_q1q2 < 0.0f) {
q1.w() = -1 * q1.w();
q1.x() = -1 * q1.x();
q1.y() = -1 * q1.y();
q1.z() = -1 * q1.z();
//cos_q1q2=-1*cos_q1q2;
cos_q1q2 = q1.w() * q2.w() + q1.x() * q2.x() + q1.y() * q2.y() + q1.z() * q2.z();
}

float k1, k2;

if (cos_q1q2 > 0.9995f) {
k1 = 1.0f - t;
k2 = t;
} else {
float sin_q1q2 = sqrt(1.0f - cos_q1q2 * cos_q1q2);
float q1q2 = atan2(sin_q1q2, cos_q1q2);
k1 = sin((1.0f - t) * q1q2) / sin_q1q2;
k2 = sin(t * q1q2) / sin_q1q2;
}

q_slerp.w() = k1 * q1.w() + k2 * q2.w();
q_slerp.x() = k1 * q1.x() + k2 * q2.x();
q_slerp.y() = k1 * q1.y() + k2 * q2.y();
q_slerp.z() = k1 * q1.z() + k2 * q2.z();

return q_slerp;
}

Slerp v.s. Nlerp

  • Nlerp: Normalized Linear Interpolation

样条插值 (Spline)

Bezier Curve

Cubic Spline Interpolation

B-Spline

积分

Runge-Kutta numerical integration methods

The Euler method

\[ \mathbf{x}_{n+1}=\mathbf{x}_{n}+\Delta t \cdot k_1 \]

where

\[ k_1 = f\left(t_{n}, \mathbf{x}_{n}\right) \]

The midpoint method

\[ \mathbf{x}_{n+1} = \mathbf{x}_{n} + \Delta t \cdot k_2 \]

where

\[ k_2 = f\left(t_{n}+\frac{1}{2} \Delta t, \mathbf{x}_{n} + \frac{\Delta t}{2} \cdot k_1\right) \]

The RK4 method

\[ \mathbf{x}_{n+1}=\mathbf{x}_{n}+\frac{\Delta t}{6}\left(k_{1}+2 k_{2}+2 k_{3}+k_{4}\right) \]

where

\[ \begin{aligned} k_{1} &=f\left(t_{n}, \mathbf{x}_{n}\right) \\ k_{2} &=f\left(t_{n}+\frac{1}{2} \Delta t, \mathbf{x}_{n}+\frac{\Delta t}{2} k_{1}\right) \\ k_{3} &=f\left(t_{n}+\frac{1}{2} \Delta t, \mathbf{x}_{n}+\frac{\Delta t}{2} k_{2}\right) \\ k_{4} &=f\left(t_{n}+\Delta t, \mathbf{x}_{n}+\Delta t \cdot k_{3}\right) \end{aligned} \]

General Runge-Kutta method

\[ \mathbf{x}_{n+1}=\mathbf{x}_{n}+\Delta t \sum_{i=1}^{s} b_{i} k_{i} \]

where

\[ k_{i}=f\left(t_{n}+\Delta t \cdot c_{i}, \mathbf{x}_{n}+\Delta t \sum_{j=1}^{s} a_{i j} k_{j}\right) \]


插值、拟合、积分
https://cgabc.xyz/posts/ccb0d7/
Author
Gavin Gao
Posted on
March 9, 2020
Licensed under