【機器學習】最小中值平方法

最小中值平方法

最小中值平方法是通過求解下面的非線性最小問題來估計參數的

LMedS記錄的是所有樣本中，偏差值居中的那個樣本的偏差，這種方法對錯誤匹配和外點有很好的魯棒性。

不像M-estimator，LMedS問題不能直接化簡為帶權重的最小二乘問題，對于LMedS估計沒有一個具體的公式。

LMedS是從樣本中隨機抽選出一個樣本子集，使用LS對子集計算模型參數，然后計算所有樣本與該模型的偏差。

具體方法是根據下面方法進行曲線估計：

假設給定n個點：
1.采用Monte Carlo技術進行抽取包含p個點的m個樣本集。對于目前的問題，選擇p=5，因為5 個點就可以確定一個二次曲線。

2.用每一個樣本集求出二次曲線Pj。

3.對于每一個二次曲線Pj，可求出整個數據集殘差平方的中值Mj。

對于第i個點到二次曲線 的殘差有多種選擇，根據需要的精度和計算效率，可以選擇algebraic distance、Euclidean distance 、gradient weighted distance。

4.求取使得最小的。

現在的問題是：怎樣確定m的值？？如果一個樣本的p個點均是內點，則為一個好的樣本。假設一個數據集包含 的外點，則m個樣本中至少有一個是好的樣本的概率是

一般包含好點的概率P接近于1，給定p和

若包含外點的百分比=40%，P=0.99，則m=57；可以通過并行算法加快算法的速度，使得對于每個子集的處理均相互獨立。

如果數據集存在高斯噪音，LMedS的效率將會非常低。為了彌補這種缺陷，提出了帶權重的最小二乘法，標準差的估計由下式給出

為最小的中值。常數1.4826使得在出現高斯噪音的時候，和最小二乘方法的效率一樣。5/(n-p)用來補償數量太少?；?img src="/uploadfile/image/20170724/20170724130901_58276.png" alt="" />，我們可以給每一項分配一個權重系數

 是第i個點相對于二次曲線P的殘差，如果某個點所對應的權重系數為0，則為外點，應剔除掉。二次曲線P則可以由下面帶權重的最小二乘問題求解

如前所述，可以通過采用Monte-Carlo技術來提高LMedS方法計算效率。然而，通過這種方法生成的樣本中的5個點很有可能非?？拷?，這種情況在曲線擬合過程中是應該盡量避免的，因為用這些點進行曲線擬合非常不穩定，而且通常會得到錯誤的結果。對每一個樣本進行有效性檢驗，將會非常耗時，降低整個算法的計算效率。為了保證算法的魯棒性和有效性，我們采用一種基于分組的規則的隨機抽樣法（regularly random selection method based on bucketing techniques），具體實現過程如下：

首先，計算第一幅圖像中點坐標的極大極小值，然后將坐標點所在的區域均勻劃分成組（在實驗中，b=8）。每一個組將包含一系列的點，同時也包括一些匹配點。最后，剔除沒有匹配點的分組。為了生成包含5個點的一個樣本，首先隨機選擇5個相互不同的組，然后在每一個組里隨機選取一個匹配點。

現在任然存在的問題是：到底需要多少個樣本？如果壞點在空間中均勻分布，且每一組有相同的點數，隨機選擇是一種均勻分布則33式仍然可用。但是，一般情況下各組所包含的點數可能相差會非常大。由此造成的結果就是，包含點數少的組中的點比包含點數多的組中的點被選擇地可能性更大?？梢杂萌缦碌姆椒▉碚f明：

假設共有I個組，我們將0到1分成I個區間，則第i個區間的寬度是是第i組點的個數。在選擇組的過程中，由均勻隨機數發生器（uniform random generator）產生一個0到1的隨機數，這個隨機數落入哪個區間，則選擇哪個組。
 

Figure 6: Interval and bucket mapping

可以用這種方法對兩幅非標定的圖像進行匹配。對于給定的兩幅未標定圖像，唯一能用的幾何約束是極線約束。先采用傳統的方法（correlation and relaxation methods）找到初始的匹配點，然后利用最小中值平方法（LMedS）剔除初始匹配中的錯誤匹配。圖像間的極線幾何關系可以由圖像中有實際意義的準則精確估計出來。