算法学习记录1102

• [[#RANSAC|RANSAC]]
• [[#稀疏矩阵存储|稀疏矩阵存储]]
  • [[#稀疏矩阵存储#CSC|CSC]]
  • [[#稀疏矩阵存储#CSR|CSR]]
• [[#B样条曲线|B样条曲线]]
• [[#增广加软约束初次尝试|增广加软约束初次尝试]]
• [[#增广添加软约束|增广添加软约束]]

RANSAC

RANSAC算法的基本假设是样本中包含正确数据(inliers，可以被模型描述的数据)，也包含异常数据(outliers，偏离正常范围很远、无法适应数学模型的数据)，即数据集中含有噪声。这些异常数据可能是由于错误的测量、错误的假设、错误的计算等产生的。同时RANSAC也假设，给定一组正确的数据，存在可以计算出符合这些数据的模型参数的方法。

RANSAC算法不依赖于特定的模型或数据集,只要能够定义出模型和内外点的判断标准,就可以使用RANSAC算法。

RANSAC算法的实现步骤如下：

1. 随机选择一定数量的样本点。
2. 使用这些样本点拟合一个模型。
3. 计算所有数据点到该模型的误差，将误差小于阈值的数据点视为内点。
4. 如果内点数量足够多，则认为找到了一个好的模型，否则继续随机选择样本点进行下一次迭代。
5. 重复上述步骤，直到达到最大的迭代次数或找到一个满意的模型 ![[ransac.pdf]]

稀疏矩阵存储

CSC

CSC（Compressed Sparse Column）格式是一种稀疏矩阵存储格式，主要用于存储稀疏矩阵的列压缩形式

1
2
3

1 0 2 
0 3 0 
4 0 5

• 值（values）：存储非零元素的值，按照列的顺序排列，即 [1, 4, 3, 2, 5]。
• 列指针（column pointers）：表示每一列第一个非零元素在值数组中的索引位置，对于这个  的矩阵，有三列，列指针数组为 [0, 2, 3, 4]。解释如下：
  • 第 0 列第一个非零元素（1）在值数组中的索引为 0，所以第一个数是 0。
  • 第 1 列第一个非零元素（3）在值数组中的索引为 2，所以第二个数是 2。
  • 第 2 列第一个非零元素（2）在值数组中的索引为 3，所以第三个数是 3。
  • 最后一个数是值数组的长度，表示最后一列之后的位置，这里值数组长度为 5，所以最后一个数是 4。
• 行索引（row indices）：存储非零元素所在的行索引，按照列的顺序排列，即 [0, 2, 1, 0, 2]。对应值数组中的元素，分别表示它们所在的行。

CSR

CSR（Compressed Sparse Row）格式是另一种稀疏矩阵存储格式，主要用于存储稀疏矩阵的行压缩形式。对于给定的  的核矩阵 ： - 值（values）：存储非零元素的值，按照行的顺序排列，即 [1, 2, 3, 4, 5]。 - 行指针（row pointers）：表示每一行第一个非零元素在值数组中的索引位置，对于这个  的矩阵，有三行，行指针数组为 [0, 2, 3, 5]。解释如下： - 第 0 行第一个非零元素（1）在值数组中的索引为 0，所以第一个数是 0。 - 第 1 行第一个非零元素（3）在值数组中的索引为 2，所以第二个数是 2。 - 第 2 行第一个非零元素（4）在值数组中的索引为 3，所以第三个数是 3。 - 最后一个数是值数组的长度，表示最后一行之后的位置，这里值数组长度为 5，所以最后一个数是 5。 - 列索引（column indices）：存储非零元素所在的列索引，按照行的顺序排列，即 [0, 2, 1, 0, 2]。对应值数组中的元素，分别表示它们所在的列。

B样条曲线

https://zhuanlan.zhihu.com/p/144042470 贝塞尔

$$\vec{P(t)} = \Sigma_{i=0}^{n-1}\vec{p_i}B_{i,n}(t), t\in [0,1]$$ B样条

$$\vec{P(t)} = \Sigma_{i=0}^{n-1}\vec{p_i}B_{i,d}(t), t\in [t_{min},t_{max}],2\le d \le n$$

• P(t) 表示曲线上的点坐标向量。
• n 为控制点 pi 数量。
• pi→为控制点坐标( i 从 0 开始)。
• Bi,n(t) 为控制点坐标影响权重的多项式系数（式中 i 代表坐标的索引， n 代表多项式最高的幂数）。
• d 影响 B 样条曲线的次数： d−1 就是曲线的次数。
• t 是绘制曲线时的取值。

一般来讲，$t_{min} = 0，t_{max} = n+p-1$，这里很像是我们代码中的num_of_control_points。n是num_of_knots_，p是spline_order_。t不一定是整数，可以是区间$t_{min},t_{max}$内的任何数值。

Cox-de Boor https://zhuanlan.zhihu.com/p/680031028

均匀B样条的矩阵表达，对于5阶B样条，k=0,1,2,3,4，矩阵列数1,2,3,4,5 均匀B样条曲线的表达式

$$c(t) = \begin{bmatrix}1&t&…&t^k\end{bmatrix}M_k\begin{bmatrix}P_{i-k}\\P_{i-k+1}\\.\\.\\.\\P_i\end{bmatrix},\ t\in [0,1], t = \frac{u-u_i}{u_{i+1}-u_i}\in [0,1]$$ 这是从$u_i~u_{i+1}$段曲线上关于参数t的曲线表达式，即第i段

$$M_k = \begin{bmatrix}m_{0,0}&m_{0,1}&…&m_{0,k}\\.\\.\\m_{k,0}& m_{k,1}&…&m_{k,k}\end{bmatrix}$$ Mk的size为k+1 * k+1

$$m_{i,j} = \frac{1}{(k-1)!}c_{k}^{k-i}\Sigma_{s=j}^k (-1)^{s-j}C_{k+1}^{s-j}(k-s)^{k-i}$$ b样条在第i-1~i个knots上时，在order = 5 的b样条上

$$c_i(t) = \begin{bmatrix}1&t&…&t^5\end{bmatrix}M_5\begin{bmatrix}P_{i}\\P_{i+1}\\…\\P_{i+5}\end{bmatrix}$$ 当 B 样条曲线的一个节点重复度为k次，且该节点的两侧各有 k个不同的节点时，对应的 B 样条曲线段可以被看作是一个 k次贝塞尔曲线。

贝塞尔曲线在该段内

$$b(t) = \begin{bmatrix}1&t&…&t^5\end{bmatrix}A\begin{bmatrix}Q_{0}\\Q_{1}\\…\\Q_{5}\end{bmatrix}$$

此时我想要求的贝塞尔曲线的6个控制点，应有

$$\begin{bmatrix}Q_{0}\\Q_{1}\\…\\Q_{5}\end{bmatrix} = A^{-1}M_5\begin{bmatrix}P_{i}\\P_{i+1}\\…\\P_{i+5}\end{bmatrix}$$

增广加软约束初次尝试

$$min \ \begin{bmatrix}X\\ Y\end{bmatrix}^T\begin{bmatrix}H&0\\0&D\end{bmatrix}\begin{bmatrix}X\\ Y\end{bmatrix}$$

$$Y = \begin{bmatrix}x_0\\x_1\\…\\x_n\\y_0\\y_1\\…\\y_n\end{bmatrix}$$ 再来一遍xy，然后 $$P = \begin{bmatrix}A&0&0&…&0&1&0&0&…&0\\ 0&A&0&…&0&0&1&0&…&0\\ 0&0&A&…&0&0&0&1&…&0 \end{bmatrix}$$ 有n行，2n列 $$(PY)^T(PY) = Y^TP^TPY= Y^TDY$$ 调整primal_warm_start为原来的两倍长度，将x和y复制一遍

调整osqp的kernel dim 为 4 * num_of_control_points_

如何使X与Y保持一致？ 调整约束限制Y的x0和X的x0相等 $$A\begin{bmatrix}X\\Y\end{bmatrix}\le b$$

$$\begin{bmatrix} A_{0,0}&…&…&A_{0,n}& 0&…&…&0\\ …&…\\ A_{n,0} &…& …&A_{n,n} & 0&…&…&0\\ 1 & 0& …&0&-1&0&…&0\\ -1 & 0&…&0&1&0&…&0\\ 0 & 1&…&0&0&-1&…&0\\ \end{bmatrix} \begin{bmatrix}x_{x0}\\ …\\ x_{xn}\\ y_{x0}\\…\\ y_{xn}\\ x_{y0}\\…\\x_{yn}\\y_{y0}\\…\\y_{yn} \end{bmatrix}\le b$$

约束矩阵的增广——列数增加num_of_variables，行数增加num_of_variables，同时使用upper bound和lower bound的话下面两个矩阵可以缩小 $$\begin{bmatrix}A & 0 \\ M&N\end{bmatrix}$$ $$M = \begin{bmatrix}1 & 0 & 0 & … &0\\ 0&1&0&…&0\\ … \\ …&0&0&0&1\end{bmatrix}$$ 对角阵 $$N = -M$$ 填充新矩阵时，稀疏矩阵，0就不必填了，主要填写后面的两个对角阵。

![[Pasted image 20241029105829.png]]

如果添加散点约束该如何实现？ 对每一个point计算一下在某两个散点之间，如果投影在某两个散点间，就用该两个散点的直线约束✅

增广添加软约束

重新来考虑一个问题，假设我们在规划路径时，要让每个路径点都在一个直线的左侧 设给出直线上的两个点为 $$A:x_0,y_0,B:x_1,y_1$$ 曲线上的某个散点为 $$P:px_{i},py_{i}$$

可以使用叉乘来判断 $$\vec{AB}\times\vec{AP} < 0$$ $$(x_1-x_0)(py_i-y_0)-(px_i-x_0)(y_1-y_0)<0$$ 等价于约束 $$(x_1-x_0)py_i - (y_1-y_0) px_i<y_0(x_1-x_0) - x_0(y_1-y_0)$$ 写为向量形式则为 $$\begin{bmatrix} y_0-y_1 &x_1-x_0 \end{bmatrix}\begin{bmatrix} px_i \\ py_i\end{bmatrix} < \begin{bmatrix} y_0(x_1-x_0) - x_0(y_1-y_0)\end{bmatrix}$$ 对于原数据 $$\begin{bmatrix} px_0 \\px_1\\px_2\\px_3\\…\\px_n \\ py_0\\py_1\\py_2\\…\\py_n\end{bmatrix}$$ 而言，约束所有点的表达式应该为 $$\begin{bmatrix} y_0-y_1 & 0&0&…&0 &x_1-x_0 & 0&0&…&0 \\ 0&y_0-y_1 & 0&…&0 &0 &x_1-x_0 & 0&…&0 \\ 0&0&y_0-y_1 & …&0 &0 &0&x_1-x_0 & …&0 \\ … & …&…& …&…&…&…&…&…&…\\ 0 & 0&…& …&y_0-y_1&0&0&…&…&x_1-x_0 \end{bmatrix}\begin{bmatrix} px_0 \\px_1\\px_2\\…\\px_n \\ py_0\\py_1\\py_2\\…\\py_n\end{bmatrix} < \begin{bmatrix} y_0(x_1-x_0) - x_0(y_1-y_0)\\ y_0(x_1-x_0) - x_0(y_1-y_0)\\ y_0(x_1-x_0) - x_0(y_1-y_0) \\…\\ y_0(x_1-x_0) - x_0(y_1-y_0)\end{bmatrix}$$ 即为 $$A_{new}X<b_{new}$$ 其中$A_{new}$的行数等于点数，列数等于点数的二倍（因为有x和y两个坐标）

接下来调整一下原问题 原问题为

$$min\ \ \ \ \ \ X^THX,\ \ \ \ \ \ st \ \ \ \ \ \ A_0X<b_0$$ 现在将目标函数增广为

$$\begin{bmatrix}X\\Y \end{bmatrix}^T \begin{bmatrix}H&0\\0 &I\end{bmatrix} \begin{bmatrix}X\\Y \end{bmatrix} = X^THX+Y^TY$$

约束条件增广为

$$\begin{bmatrix}A_0&0\\A_{new} &I\end{bmatrix} \begin{bmatrix}X\\Y \end{bmatrix} < \begin{bmatrix}b_0\\b_{new} \end{bmatrix}$$ 即

$$A_0X<b_0,A_{new}X+Y<b_{new}$$ 一般情况下，目标函数最小时，Y=0 此时约束条件等效于新约束为硬约束。 当新约束无法满足时，目标函数被惩罚，Y值不为零，使得新约束被满足。