于永彥　+束玉琴

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

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

中圖分類(lèi)號(hào)：TP13 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2015）05-0000-00

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

1 Sequential RANSAC

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

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

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

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

2 MultiRANSAC

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

每個(gè)梯形模型有兩倍的數(shù)據(jù)點(diǎn)。如果有5個(gè)模型需要估計(jì)，可以通過(guò)選擇其中兩個(gè)模型來(lái)獲得較大的一致集，從剩余的4個(gè)真實(shí)直線(xiàn)中只得到3個(gè)模型。而如果要求一致集不相交，則可完全避免。因?yàn)橐呀?jīng)選擇了估計(jì)最大的真實(shí)模型的兩個(gè)模型中較大的那個(gè)，就無(wú)法再選擇另一個(gè)與同一個(gè)真實(shí)模型相聯(lián)系的那個(gè)模型，因?yàn)樗c初始模型共享數(shù)據(jù)點(diǎn)，即一致集相交。一致集更新算法如表2-1所示。

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

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

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

3 Residual Histogram Analysis

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

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

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

4 J-Linkage

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

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

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

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

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

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

5 Kernel Fitting

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

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

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

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

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

6結(jié)語(yǔ)

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

參考文獻(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.