记录读论文时遇到的一些算法|【记录读论文时遇到的一些算法8】—

Surface normal：法向量

问题定义
优化方法
总结
带有噪声的法向量计算

问题定义记x i ∈ R n , i = 1 , 2 , ? ? , m x_{i} \in R^{n}, i=1,2, \cdots, m xi?∈Rn,i=1,2,?,m 为数据点，找到一个平面（超平面），该平面穿过法向量为 n \mathbf{n} n的点 c \mathbf{c} c：
min ? c , n , ∥ n ∥ = 1 ∑ i = 1 m ( ( x i ? c ) T n ) 2 \min _{\mathbf{c}, \mathbf{n},\|\mathbf{n}\|=1} \sum_{i=1}^{m}\left(\left(\mathbf{x}_{i}-\mathbf{c}\right)^{T} \mathbf{n}\right)^{2} c,n,∥n∥=1min?i=1∑m?((xi??c)Tn)2

文章图片
说白了，就是给定了一组点，找到一个平面，保证这组点到这个平面的距离最小，距离最小时，平面确定，这组点处的法向量也随之确定。在确定这个平面之前，还需要确定一个点，该点在这个平面上，用于计算给定点到这个平面上的距离。目前已经确定好了优化函数，接下来就是要寻找优化方法。
优化方法由于点 c \mathbf{c} c和法向量 n \mathbf{n} n 是独立变量。可以先找到最优的 c \mathbf{c} c：
c ? = arg ? min ? c ∑ i = 1 m ( ( x i ? c ) T n ) 2 = arg ? min ? { c j } ∑ i = 1 m ∑ j = 1 n ( x i j ? c j ) 2 n j 2 = arg ? min ? { c j } ∑ i = 1 m ∑ j = 1 n ( x i j ? c j ) 2 = arg ? min ? c ∑ i = 1 m ∥ x i ? c ∥ 2 \begin{aligned} \mathbf{c}^{*} &=\underset{\mathbf{c}}{\arg \min } \sum_{i=1}^{m}\left(\left(\mathbf{x}_{i}-\mathbf{c}\right)^{T} \mathbf{n}\right)^{2} \\ &=\underset{\left\{c_{j}\right\}}{\arg \min } \sum_{i=1}^{m} \sum_{j=1}^{n}\left(x_{i j}-c_{j}\right)^{2} n_{j}^{2} \\ &=\underset{\left\{c_{j}\right\}}{\arg \min } \sum_{i=1}^{m} \sum_{j=1}^{n}\left(x_{i j}-c_{j}\right)^{2} \\ &=\underset{\mathbf{c}}{\arg \min } \sum_{i=1}^{m}\left\|\mathbf{x}_{{i}}-\mathbf{c}\right\|^{2} \end{aligned} c??=cargmin?i=1∑m?((xi??c)Tn)2={cj?}argmin?i=1∑m?j=1∑n?(xij??cj?)2nj2?={cj?}argmin?i=1∑m?j=1∑n?(xij??cj?)2=cargmin?i=1∑m?∥xi??c∥2?
对上式展开求导，得到 c ? \mathbf{c}^* c? 是这些点的质心：
x ˉ = 1 m ∑ i = 1 m x i \bar{x}=\frac{1}{m} \sum_{i=1}^{m} x_{i} xˉ=m1?i=1∑m?xi?
那么可以先将给定的数据点归一化：
X ~ = [ x ~ 1 , ? ? , x ~ m ] , x ~ i = x i ? x ˉ , i = 1 , ? ? , m \tilde{X}=\left[\tilde{x}_{1}, \cdots, \tilde{x}_{m}\right], \tilde{x}_{i}=x_{i}-\bar{x}, i=1, \cdots, m X~=[x~1?,?,x~m?],x~i?=xi??xˉ,i=1,?,m
现在问题转化为求PCA：
min ? n ∈ R n ∑ i = 1 m ( x ~ i T n ) 2 ,s.t.:∥ n ∥ 2 = 1 min ? n ∈ R n ∑ i = 1 m n T x ~ i x ~ i T n ,s.t.:∥ n ∥ 2 = 1 min ? n ∈ R n n T ( ∑ i = 1 m x ~ i x ~ i T ) n ,s.t.:∥ n ∥ 2 = 1 min ? n ∈ R n n T X ~ X ~ T n ,s.t.:∥ n ∥ 2 = 1 \begin{aligned} &\min _{n \in R^{n}} \sum_{i=1}^{m}\left(\tilde{x}_{i}^{T} n\right)^{2}, \text { s.t.: }\|n\|_{2}=1 \\ &\min _{n \in R^{n}} \sum_{i=1}^{m} n^{T} \tilde{x}_{i} \tilde{x}_{i}^{T} n, \text { s.t.: }\|n\|_{2}=1 \\ &\min _{n \in R^{n}} n^{T}\left(\sum_{i=1}^{m} \tilde{x}_{i} \tilde{x}_{i}^{T}\right) n, \text { s.t.: }\|n\|_{2}=1 \\ &\min _{n \in R^{n}} n^{T} \tilde{X} \tilde{X}^{T} n, \text { s.t.: }\|n\|_{2}=1 \end{aligned} ?n∈Rnmin?i=1∑m?(x~iT?n)2, s.t.: ∥n∥2?=1n∈Rnmin?i=1∑m?nTx~i?x~iT?n, s.t.: ∥n∥2?=1n∈Rnmin?nT(i=1∑m?x~i?x~iT?)n, s.t.: ∥n∥2?=1n∈Rnmin?nTX~X~Tn, s.t.: ∥n∥2?=1?
n \mathbf{n} n对应于最小特征值的特征向量。
总结

选一个点 P
找到该点附近的领域，将该邻域定义为surface
P C A \mathrm{PCA} PCA
Normal→ \rightarrow → 最小的特征向量
Curvature→ \rightarrow → ratio between eigen valuesλ 3 / ( λ 1 + λ 2 + λ 3 ) \lambda_{3} /\left(\lambda_{1}+\lambda_{2}+\lambda_{3}\right) λ3?/(λ1?+λ2?+λ3?)

带有噪声的法向量计算加权法向量计算
【记录读论文时遇到的一些算法|【记录读论文时遇到的一些算法8】—— 法向量】 min ? n ∈ R n ∑ i = 1 m w i ( x ~ i T n ) 2 ,s.t.:∥ n ∥ 2 = 1 min ? n ∈ R n ∑ i = 1 m w i n T x ~ i x ~ i T n ,s.t.:∥ n ∥ 2 = 1 min ? n ∈ R n n T ( ∑ i = 1 m w i x ~ i x ~ i T ) n ,s.t.:∥ n ∥ 2 = 1 min ? n ∈ R n n T X ~ W X ~ T n ,s.t.:∥ n ∥ 2 = 1 \begin{aligned} &\min _{n \in R^{n}} \sum_{i=1}^{m} w_{i}\left(\tilde{x}_{i}^{T} n\right)^{2}, \text { s.t.: }\|n\|_{2}=1 \\ &\min _{n \in R^{n}} \sum_{i=1}^{m} w_{i} n^{T} \tilde{x}_{i} \tilde{x}_{i}^{T} n, \text { s.t.: }\|n\|_{2}=1 \\ &\min _{n \in R^{n}} n^{T}\left(\sum_{i=1}^{m} w_{i} \tilde{x}_{i} \tilde{x}_{i}^{T}\right) n, \text { s.t.: }\|n\|_{2}=1 \\ &\min _{n \in R^{n}} n^{T} \tilde{X} W \tilde{X}^{T} n, \text { s.t.: }\|n\|_{2}=1 \end{aligned} ?n∈Rnmin?i=1∑m?wi?(x~iT?n)2, s.t.: ∥n∥2?=1n∈Rnmin?i=1∑m?wi?nTx~i?x~iT?n, s.t.: ∥n∥2?=1n∈Rnmin?nT(i=1∑m?wi?x~i?x~iT?)n, s.t.: ∥n∥2?=1n∈Rnmin?nTX~WX~Tn, s.t.: ∥n∥2?=1?
其中
W = [ w 1 0 ? 0 0 w 2 ? 0 ? ? ? ? 0 0 ? w m ] W=\left[\begin{array}{cccc} w_{1} & 0 & \cdots & 0 \\ 0 & w_{2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & w_{m} \end{array}\right] W=??????w1?0?0?0w2??0??????00?wm????????
根据点之间的关系确定。
深度学习计算法向量