于永彥　+束玉琴

摘要：從2D圖像中估計出物體對象的幾何模型一直是計算機視覺的重點研究領(lǐng)域，而多模型估計更是其中的關(guān)鍵所在。本文從技術(shù)原理、算法實現(xiàn)、估計效果及實際應(yīng)用等多個角度，對Sequential RANSAC、MultiRANSAC、Residual Histogram Analysis、J-Linkage和Kernel Fitting等幾種典型的多模型估計方案進行了綜合分析與對比研究，指出了它們的優(yōu)缺點和改進方向。

關(guān)鍵詞：多模型估計 技術(shù)原理 算法流程 性能比較

中圖分類號：TP13 文獻標(biāo)識碼：A 文章編號：1007-9416（2015）05-0000-00

從2D圖像中估計對象模型是計算機視覺的基本任務(wù)之一，正確擬合一個最佳模型，消除外點影響，是多模型估計的基本目標(biāo)。目前有多重方法可用于多模型估計，但它們的數(shù)學(xué)原理、算法流程和實現(xiàn)效果各有千秋。

1 Sequential RANSAC

Sequential RANSAC的本質(zhì)是多次調(diào)用RANSAC過程，其算法框架如表1-1所示。

由表1-1可見，Sequential RANSAC的測試原理很直接，若某個模型被拒絕，則算法終止3。文獻所提方案既沒有測試步驟，也沒有明確給定終止條件；而文獻雖然也沒確定可接受條件，但給出了終止條件，即當(dāng)找到個模型后，算法終止。不難看出，Sequential RANSAC具有明顯缺陷，若前期估計結(jié)果不理想必將降低后期估測的有效性。

造成這種現(xiàn)象的原因是由于RANSAC判斷時采用的是最大化一致集。盡管一致集是模型驗證的一種較好方法，但僅僅使用這一種準(zhǔn)則則稍顯不足。

例如有50個模型，不僅需要考察模型一致集大小，而且還要考慮一致集中的點是如何共享同一個模型的，這基于一個基本事實，即梯形數(shù)據(jù)中正確模型的一致集所含數(shù)據(jù)點比錯誤模型一致集所含數(shù)據(jù)點共享了更多的模型。這種不和諧特性在Sequential RANSAC中被進一步惡化。若初始模型選擇是錯誤的，將導(dǎo)致后續(xù)模型估計的失效。

2 MultiRANSAC

文獻指出Sequential RANSAC的缺陷來源于它的順序執(zhí)行，從而提出了一種并行執(zhí)行的方案，即MultiRANSAC。MultiRANSAC搜索最好的個模型的集合，通過使用個極小樣本模型反復(fù)更新這個模型的集合，使用一種融合技術(shù)歸并一致集的集合。MultiRANSAC要求這個模型的一致集不相交，以確保得到個獨立的模型。

每個梯形模型有兩倍的數(shù)據(jù)點。如果有5個模型需要估計，可以通過選擇其中兩個模型來獲得較大的一致集，從剩余的4個真實直線中只得到3個模型。而如果要求一致集不相交，則可完全避免。因為已經(jīng)選擇了估計最大的真實模型的兩個模型中較大的那個，就無法再選擇另一個與同一個真實模型相聯(lián)系的那個模型，因為它與初始模型共享數(shù)據(jù)點，即一致集相交。一致集更新算法如表2-1所示。

UpdateCS的基本功能是用新的個一致集的集合，來更新當(dāng)前個一致集的集合。MultiRANSAC的主體算法如表2-2所示。

MultiRANSAC顯露了一致集導(dǎo)向方法的基本缺陷，即難以消除模型的二義性。因為MultiRANSAC和Sequential RANSAC都需要多個極小樣本模型，每一個都不可避免地含有差異細微的參數(shù)，可能導(dǎo)致冗余模型。

MultiRANSAC和Sequential RANSAC為了避免這種現(xiàn)象，都要求一致集不相交。Sequential RANSAC是在找到每個模型后移除響應(yīng)的內(nèi)點，而MultiRANSAC是在函數(shù)中實現(xiàn)此目的。遺憾的是，真實模型不可能不相交，大量的點可能屬于兩個以上的真實模型。這就需要設(shè)計某種不相交度量方法，以從同一模型的兩個具有不同參數(shù)的實例中辨別不同模型的相交性如果僅使用一致集，這是不可能實現(xiàn)的，因為不同的模型相交的點要比冗余模型相交的點多得多。這種不相交準(zhǔn)則最終導(dǎo)致MultiRANSAC在梯形數(shù)據(jù)集中失效，再次表明了基于一致集的模型估計的不合理。

3 Residual Histogram Analysis

文獻提出殘值直方圖分析法（Residual Histogram Analysis，RHA），避開了一致集方案的問題和數(shù)據(jù)集的先驗知識的需求。它不是去搜索一個擁有大量一致集內(nèi)點的模型，而是在殘值直方圖中根據(jù)峰值點來搜索健壯的模型。因為直方圖中的模就對應(yīng)于真實模型。RHA的基本原理是，計算每個模型與每個數(shù)據(jù)點之間的殘值。對每個點計算關(guān)于所有模型的殘值，經(jīng)過平滑，得到該點的殘值直方圖?；谒悬c找到模，再根據(jù)中位數(shù)，確定模型的數(shù)目。最后，從兩個所選點的模倉中選出實際的模型。表3-1是RHA的算法框架。

可見，RHA不需要任何關(guān)于先驗知識，但需要在含噪直方圖中發(fā)現(xiàn)模。其關(guān)鍵步驟是模檢測和模型估計。在對直方圖進行模分析后，得到正確估計模型的有效點集，從其中選取波峰特異性最大的一個點，再任選一個點，由這兩個點估計出正確的模型。

RHA算法除了構(gòu)建了一種避開考慮一致集的模型估計途徑外，還避免了使用數(shù)據(jù)集的先驗知識。但是，RHA仍需要調(diào)諧參數(shù)。構(gòu)造直方圖的參數(shù)不同，將導(dǎo)致估計出不同數(shù)目的模型。文獻指出，RHA尋找模的步驟是脆弱的。這意味著RHA與其他方法相比沒有競爭力。

4 J-Linkage

文獻提出的J-Linkage算法通過自底向上聚類數(shù)據(jù)點來來尋找模型，使用傾向集，雖然類似于一致集，但是顛倒了模型與數(shù)據(jù)點的角色。一個數(shù)據(jù)點的傾向集定義如下：

J-Linkage不考察模型有哪些點與之匹配，而是考察一個數(shù)據(jù)點與哪些模型匹配。從而確定哪些數(shù)據(jù)點可能聚類在一起。如果有個極小樣本集MSS，數(shù)據(jù)點可以描述為空間的維向量，稱為概念空間。則對于模型，有下面的定義：

這種查看傾向集的方法可幫助理解下面的Kernel Fitting算法。表4-1是J-Linkage算法的基本流程。

上述算法使用了Jaccard距離。二個集合的Jaccard距離定義為：

顯然，，且當(dāng)重合時，為0；當(dāng)不相交時，為1。當(dāng)聚類操作終止后，每個類至少有一個模型估計了所有數(shù)據(jù)，而且，相當(dāng)于真實模型的點位于最大類中，而外點位于較小的類中。這些類類似于一致集。較小的外點類被移除，或者通過一個預(yù)定義閾值，或者直接剔除較小類，直到剔除的點的數(shù)目等于預(yù)期的外點數(shù)。

顯然，不同的采樣策略將通過改變數(shù)據(jù)點的傾向集以及在概念空間的描述，來影響哪些點可能被聚類。J-Linkage不使用一致集，客服了RANSAC類方法的缺陷，但付出了聚類的代價，需要通過一致集閾值來辨別內(nèi)點與外點。如果設(shè)置太小，將導(dǎo)致虛假模型。反之，若太大，又有可能排除真實模型。而且，其運行時間為，搜索空間太復(fù)雜。同時，J-Linkage要求一個聚類中的數(shù)據(jù)點至少有一個初選模型，將導(dǎo)致模型碎裂，即如果沒有一個極小樣本模型能正確估計真實模型，則真實模型可能被分化成多個分離的類。為此，文獻都提出了Merging J-Linkage改良方案，給定數(shù)據(jù)點的兩個類，計算出一個最佳估計的一個解，點到的誤差均值為；歸并誤差最小的兩個類，直到最小歸并誤差大于閾值。這將允許在某次采樣中沒有公共模型的點的聚類，但是，有公共模型的點被歸并。不過，這種方法在處理平面之外的模型時具有很大局限性。

5 Kernel Fitting

文獻提出的Kernel Fitting方案，既具有J-Linkage的執(zhí)行效率，又像RHA一樣不需要任何先驗知識。Kernel Fitting有一個獨特的優(yōu)勢，即僅依靠精密的數(shù)學(xué)技術(shù)。這種數(shù)學(xué)上的完善，使得Kernel Fitting不需要噪聲比例、外點數(shù)量或模型數(shù)目等任何先驗知識。

Kernel Fitting的核心是有序殘值內(nèi)核（Ordered Residual Kernel，ORK）。一個內(nèi)核是一個對稱函數(shù)，稱為Mercer核，其與另一個函數(shù)配對。映射到一個特征空間。如果Mercer條件滿足，則得到下式：

也就是說，不管的實際類型，完全應(yīng)用來工作。設(shè)，則有：

因此，若已知個數(shù)據(jù)和個極小樣本集，即可計算一個核矩陣。移除外點，得到一個簡化的核矩陣。表5-1是ORK的基本框架。

雖然Kernel Fitting不需要任何先驗知識，但仍然需要估計許多模型，需要步長以辨別內(nèi)外點的閾值，且需要模型數(shù)目。

6結(jié)語

Sequential RANSAC是多模型估計的基準(zhǔn)方法，對于大多數(shù)數(shù)據(jù)集，是快速有效的，而且在一致集空間消除模型二義性方面優(yōu)于MultiRANSAC。J-Linkage對所有類型的數(shù)據(jù)集都有效，但設(shè)置聚類閾值很棘手，即如果閾值太小，出現(xiàn)虛假模型，如果太大，又會丟失模型，且時間復(fù)雜度為數(shù)據(jù)點數(shù)目的二次方。而Merging J-Linkage對于平面估計很高效，但在幾何特征估計中易產(chǎn)生幻覺模型。MultiRANSAC需要一致集不相交假定，在平面檢測情況下，劣于Merging J-Linkage。RHA雖然也有能力獨立用于檢測多模型，但在執(zhí)行和性能上與其他算法相比沒有競爭力。Kernel Fitting執(zhí)行力強，且不需要數(shù)據(jù)集的任何先驗知識，但也像J-Linkage一樣，運行時間是數(shù)據(jù)點數(shù)目的二次方，實現(xiàn)起來很困難。

參考文獻

[1] M. A. Fischler and R. C. Bolles. Random sample concensus：A paradigm for model fitting with applications to image analysis and automated cartography. Comm. of the ACM，24：381–395， 1981

[2] R. O. Duda and P. E. Hart. Use of the hough transformation to detect lines and curves in pictures. Comm. of the ACM，15：11–15， 1972.

[3] Y. Kanazawa and H. Kawakami. Detection of planar regions with uncalibrated stereo using distributions of feature points. In Proc. British Machine Vision Conf.， pages 247-256， 2004.