說明

L1算法中的核心公式簡明易懂，但是從核心的優(yōu)化式向復(fù)雜的迭代式的推導(dǎo)卻不是那么簡單磕仅。本文將針對相關(guān)公式進(jìn)行一次推導(dǎo)荐吉，最后根據(jù)驗證的迭代式進(jìn)行代碼實現(xiàn)。

公式推導(dǎo)

L1核心公式如下：
$\underset{X}{\operatorname{argmin}} \sum_{i \in I} \sum_{j \in J}\left\|x_{i}-q_{j}\right\| \theta\left(\left\|x_{i}-q_{j}\right\|\right)+R(X) \tag{1} \\ \theta(r)=e^{-r^{2} /(h / 2)^{2}} , R(X)=\sum_{i \in I} \gamma_{i} \sum_{i^{\prime} \in I \backslash\{i\}} \frac{\theta\left(\left\|x_{i}-x_{i^{\prime} }\right\|\right)}{\sigma_{i}\left\|x_{i} -x_{i^{\prime}}\right\|}$

(1)中 $X, x_i$ 代表sample point集合和單個點炬藤， $Q,q_j$ 代表原本的點云點集和單個點御铃， $\gamma_i$ 代表 $x_i$ 對應(yīng)的平衡常數(shù)(balancing constants)， $\sigma_i$ 代表 $x_i$ 的有向度(directionality degree)沈矿。
將 $x_i$ 看做函數(shù)中的變量上真，則有以下式子

$\underset{X}{arg\,min}\:f(x_i)= \underset {j \in J}{\sum} f_1(||x_i-q_j||) + \gamma _i \underset {i^, \in I/ \{ i \}}{\sum} f_2(||x_i-x_{i^,}||) \tag {1.1}$

$f_1$ 偏微分：
$\begin{align} \frac {\partial f_1}{\partial x_i}&= \frac {\partial f_1}{\partial ||x_i-q_i||} \times \, \frac {\partial ||x_i-q_i||}{\partial x_i}\\ &= (1-\frac {2{(x_i-q_j)}^2}{{(h/2)}^2}) \theta (||x_i-q_j||) \times \frac {x_i-q_i}{||x_i-q_i||}\\ &=(1-\frac {2{(x_i-q_j)}^2}{{(h/2)}^2}) (x_i-q_j) \alpha _{ij} \tag{1.2} \end{align}$

$f_2$ 偏微分：
$\begin{align} \frac {\partial f_2}{\partial x_i}&= \frac {\partial f_2}{\partial ||x_i-x_{i^,}||} \times \, \frac {\partial ||x_i-x_{i^,}||}{\partial x_i}\\ &=-(1+\frac {2{(x_i-x_{i^,})}^2}{(h/2)^2})\frac {\theta (||x_i-x_{i^,}||)}{\sigma _i(x_i-x_{i^,})^2}\times \frac {x_i-x_{i^,}}{||x_i-x_{i^,}||}\\&= -(1+\frac {2{(x_i-x_{i^,})}^2}{(h/2)^2}) \frac {x_i-x_{i^,}}{\sigma _i} \beta _{ii^,} \tag {1.3} \end{align}$

由于式(1.2)和(1.3)中的系數(shù) $(1-\frac {2{(x_i-q_j)}^2}{{(h/2)}^2})$ 和 $-(1+\frac {2{(x_i-x_{i^,})}^2}{(h/2)^2})$ 在實際運算中近似為1和-1，所以系數(shù)可以直接去掉细睡，直接保留符號即可谷羞。

最終去掉系數(shù)的化簡式如下：
$\sum_{j \in J}\left(x_{i}-q_{j}\right) \alpha_{i j}-\gamma_{i} \sum_{i^{\prime} \in I \backslash\{i\}} \frac{x_{i}-x_{i^{\prime}}}{\sigma_{i}} \beta_{i i^{\prime}}=0, i \in I \tag{2} \\ \alpha_{i j}=\frac{\theta\left(\left\|x_{i}-q_{j}\right\|\right)} {\left\|x_{i}-q_{j}\right\|},\: \beta _{ii^,}=\frac {\theta (||x_i-x_{i^,}||)} {||x_i-x_{i^,}||^3}$
P.S. 原論文 $\beta _{ii^,}=\frac {\theta (||x_i-x_{i^,}||)} {||x_i-x_{i^,}||^2}$ ，但是按照(1.3)計算 $\beta _{ii^,}=\frac {\theta (||x_i-x_{i^,}||)} {||x_i-x_{i^,}||^3}$ 溜徙，此處采用的是3次方的這個定義。

化簡式又可以提取為：
$(\underset {j \in J}{\sum} \alpha _{ij}-\frac {\gamma _i \sum _{i^, \in I/\{ i\}} \beta _{ii^,}} {\sigma _i})x_i=\underset {j \in J}{\sum} \alpha _{ij}q_{j}-\frac {\gamma _i \sum _{i^, \in I/\{ i\}} \beta _{ii^,}x_{i^,}} {\sigma _i} \: \tag {2.1}$

根據(jù)新的斥力系數(shù)定義 $\mu=\frac{\gamma_{i} \sum_{i^{\prime} \in I \backslash\{i\}} \beta_{i i^{\prime}}}{\sigma_{i}^2 \sum_{j \in J} \alpha_{i j}}, \forall i \in I$ (刊誤：原論文里使用公式為 $\mu=\frac{\gamma_{i} \sum_{i^{\prime} \in I \backslash\{i\}} \beta_{i i^{\prime}}}{\sigma_{i} \sum_{j \in J} \alpha_{i j}}, \forall i \in I$ 犀填，經(jīng)分析 $\sigma_i$ 應(yīng)為筆誤)蠢壹，可將(2.2)化簡為：

$\left(1-\mu \sigma_{i}\right) x_{i}=\frac{\sum_{j \in J} q_{j} \alpha_{i j}}{\sum_{j \in J} \alpha_{i j}} - \mu \sigma_{i} \frac{\sum_{i^{\prime} \in I \backslash\{i\}} x_{i^{\prime}} \beta_{i i^{\prime}}}{\sum_{i^{\prime} \in I \backslash\{i\} } \beta_{i i^{\prime}}} \tag {3}$

簡單移項后可得:
$x_{i} = \frac{\sum_{j \in J} q_{j} \alpha_{i j}}{\sum_{j \in J} \alpha_{i j}} + \mu \sigma_{i} \frac{\sum_{i^{\prime} \in I \backslash\{i\}} (x_i - x_{i^{\prime} }) \beta_{i i^{\prime}}}{\sum_{i^{\prime} \in I \backslash\{i\}} \beta_{i i^{\prime}}} \tag {3.1}$

使用不動點迭代^[1]推導(dǎo)出迭代公式：
$x_{i}^{k+1}=\frac{\sum_{j \in J} q_{j} \alpha_{i j}^{k}}{\sum_{j \in J} \alpha_{i j}^{k}}+\mu \sigma_{i}^{k} \frac{\sum_{i^{\prime} \in I \backslash\{i\}}\left(x_{i}^{k}-x_{i^{\prime}}^{k}\right) \beta_{i i^{\prime}}^{k}} {\sum_{i^{\prime} \in I \backslash\{i\}} \beta_{i i^{\prime}}^{k}} \\ \alpha_{i j}=\frac{\theta\left(\left\|x_{i}-q_{j}\right\|\right)} {\left\|x_{i}-q_{j}\right\|},\: \beta _{ii^,}=\frac {\theta (||x_i-x_{i^,}||)} {||x_i-x_{i^,}||^3} \tag {4}$
可以看到，(3.1)和迭代公式(4)已經(jīng)基本一毛一樣了九巡。

代碼實現(xiàn)

整個迭代的流程包括:

計算鄰居(self neighbor 和origin neighbor)
計算 $f_1$ 項(computeAlphasTerms)和 $f_2$ 項(computeBetasTerms)
根據(jù) $f_1$ 和 $f_2$ 計算新的迭代坐標(biāo)（公式4）
重復(fù)上述步驟直到滿足停止條件

迭代函數(shù)

double L1median::iterateReturnError()
{
    /*位置迭代更新*/
    paraPtr->add("neighborhood_size", h);
    for (int i = 0; i < sampleInfo.size(); ++i) {
        sampleInfo[i].kind = (sampleInfo[i].kind == pi::Candidate) ? pi::Sample : sampleInfo[i].kind;
    }

    computeAlphasTerms();
    computeBetasTerms();
    double error = updateSamplePos();
    emit infoSignal("RMS:" + QString::number(error, 'f', 6)+'\n');

    /*位置同步*/
    if (synSampleWithInfo()) {
        emit iterateSignal();
    } else {
        emit errorSignal(QString("fail to synchronize sample info"));
        return 0.0;
    }
    /*位置更新后的預(yù)備信息計算*/
    computeNeighbors();
    computeSigmas();
    return error;
}

其它具體實現(xiàn)部分過于復(fù)雜图贸，此處按下不表，有時間可能另開一章進(jìn)行說明冕广。

https://blog.csdn.net/jbb0523/article/details/52459797 ?

L1算法分析和實現(xiàn)(2) 從優(yōu)化公式到迭代公式

L1算法分析和實現(xiàn)(2) 從優(yōu)化公式到迭代公式

說明

公式推導(dǎo)

代碼實現(xiàn)