【機器學(xué)習(xí)】最小中值平方法

最小中值平方法

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

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

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

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

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

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

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

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

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

4.求取使得最小的。

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

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

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

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

為最小的中值。常數(shù)1.4826使得在出現(xiàn)高斯噪音的時候，和最小二乘方法的效率一樣。5/(n-p)用來補償數(shù)量太少。基于，我們可以給每一項分配一個權(quán)重系數(shù)

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

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

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

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

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

Figure 6: Interval and bucket mapping

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