論文標(biāo)題：Performance Evaluation of 3D Correspondence Grouping Algorithms作者：Jiaqi Yang, Ke Xian, Yang Xiao and Zhiguo Cao

譯者：仲夏夜之星

下載地址：https://arxiv.org/pdf/1804.02085.pdf

摘要：本文針對(duì)幾種廣泛使用三維對(duì)應(yīng)關(guān)系聚合算法進(jìn)行了深入的評(píng)價(jià)，其目的在于他們?cè)谝曈X任務(wù)中的意義依賴于正確的對(duì)應(yīng)特征關(guān)系，一個(gè)良好的對(duì)應(yīng)關(guān)系的聚合算法的期望是可以從初始的特征匹配中搜索到盡可能多的關(guān)系，從而提高準(zhǔn)確率和召回率，就這個(gè)規(guī)則，本文從三個(gè)方面分別是處理形狀檢索、三維目標(biāo)識(shí)別及點(diǎn)云配準(zhǔn)來進(jìn)行實(shí)驗(yàn)，該方法受噪音、不同點(diǎn)密度的細(xì)微差別、雜波、遮擋和部分重疊的影響，這將會(huì)導(dǎo)致內(nèi)點(diǎn)和對(duì)應(yīng)分布比率的不同而造成結(jié)果不同，基于定量結(jié)果分析，本文對(duì)其總結(jié)了優(yōu)缺點(diǎn)并從性能和效率兩方面進(jìn)行了評(píng)估。

注1：文末附【立體視覺】交流群

注2：整理不易，請(qǐng)點(diǎn)贊支持！

作者：仲夏夜之星 | 來源：3D視覺工坊微信公眾號(hào)
原文：三維點(diǎn)云對(duì)應(yīng)關(guān)系聚合算法的性能評(píng)價(jià)：https://mp.weixin.qq.com/s/gQD80190SiTzDkVmZW_6Ng

一 、引言

建立三維點(diǎn)云之間的正確匹配關(guān)系，也稱為點(diǎn)云配準(zhǔn)問題，這在三維計(jì)算機(jī)視覺中是一個(gè)基石。一個(gè)至關(guān)重要的原因是基于局部形狀特征的匹配方式的應(yīng)用，如三維對(duì)象識(shí)別，點(diǎn)云注冊(cè)、形狀檢索和三維對(duì)象分類非常流行?；诰植刻卣鞯钠ヅ浞绞饺鐖D1，首先檢測表面上的一組獨(dú)特的關(guān)鍵點(diǎn)并用特征描述符表示局部形狀幾何，然后生成原始初始匹配用于識(shí)別兩種形狀之間的相似性。然而，這個(gè)方式總會(huì)出現(xiàn)大量的虛假匹配，主要有兩個(gè)原因，一個(gè)是加載前一個(gè)模塊的殘差，例如，關(guān)鍵點(diǎn)定位錯(cuò)誤和重復(fù)結(jié)構(gòu)中的特征描述符的不匹配，另一個(gè)是其他因素的干憂，包括噪音，不同點(diǎn)密度、雜波、遮擋和部分重疊。為了確保后續(xù)變換估計(jì)或假設(shè)生成的準(zhǔn)確性，希望有更高的精度從原始特征匹配中過濾，突顯出對(duì)應(yīng)關(guān)系分組的重要性。

一種流行的對(duì)應(yīng)分組算法是從最初的特征中找到盡可能多的內(nèi)部線性匹配，可以增加精度和召回率[5]。類似于二維圖像域的趨勢(shì)，最近研究的熱點(diǎn)話題是特征由三維對(duì)應(yīng)分組相關(guān)算法來驅(qū)使特征匹配的視覺任務(wù)，如三維對(duì)象識(shí)別和三維重建。除了重新探索比較流行的二維對(duì)應(yīng)分組技術(shù)，如三維領(lǐng)域的相似性分?jǐn)?shù)(SS)，最近鄰相似比（NNSR），隨機(jī)抽樣一致性(RANSAC)和光譜技術(shù)(ST)，我們也可以找到許多最近的三維目標(biāo)算法，如幾何一致性(GC)，聚類，博弈論，3D霍夫投票(3DHV)，和線性搜索(SI)等。隨著廣泛的三維對(duì)應(yīng)分組算法的不斷更新，這些算法的有效性通常在特定的數(shù)據(jù)集上進(jìn)行評(píng)估有限數(shù)量的細(xì)微差別和比較，因此研究學(xué)者很難選擇合適的算法并給出了一個(gè)特定的應(yīng)用范圍。為此，對(duì)于七種最先進(jìn)的三維對(duì)應(yīng)分組算法只要有SS、NNSR、RANSAC、ST、GC、3DHV和SI，本文提出了一個(gè)全面的評(píng)價(jià)，這是對(duì)三維對(duì)應(yīng)關(guān)系分組算法的最新的全面的評(píng)估，據(jù)我們所知，它考慮了經(jīng)典和最新的方法對(duì)涉及各種應(yīng)用的基準(zhǔn)和其他干擾進(jìn)行評(píng)估。本文用精確率和召回率兩個(gè)評(píng)價(jià)指標(biāo)來測量定量性能，保證分組的對(duì)應(yīng)關(guān)系和從原始特征匹配的大量線性關(guān)系的準(zhǔn)確性來進(jìn)行平衡的檢查。此外，我們將應(yīng)用的上下文考慮在內(nèi)，具體來說，不同的應(yīng)用將導(dǎo)致不同比例的差異和空間初始特征匹配的位置，主要是由于不同干擾的類別和程度來掩蓋這些問題，我們分別對(duì)實(shí)驗(yàn)博洛尼亞三維檢索(B3R)，UWA三維對(duì)象識(shí)別和UWA三維建模數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)來檢查這些三維對(duì)應(yīng)分組算法。B3R數(shù)據(jù)集測試了關(guān)于噪聲和變化點(diǎn)的算法密度評(píng)估結(jié)果的魯棒性，U3OR數(shù)據(jù)集測試了關(guān)于雜波和遮擋的性能，U3M數(shù)據(jù)集測試了部分重疊的數(shù)據(jù)的影響，這些干擾全部都已經(jīng)被量化，以便進(jìn)行詳細(xì)的比較。

總之，本文的貢獻(xiàn)主要有：

（1）本文對(duì)七種主流的對(duì)應(yīng)關(guān)系分組算法進(jìn)行了定量評(píng)價(jià)，主要是關(guān)于不同干擾包括噪聲、點(diǎn)密度變化、雜波、遮擋和部分重疊下的三個(gè)基準(zhǔn)的比較，還測試了不同數(shù)量的初始匹配的時(shí)間效率。

（2）本為給出了針對(duì)不同算法的局限性以及優(yōu)缺點(diǎn)。本文的結(jié)構(gòu)安排為：第二部分主要介紹七種最新算法中的每個(gè)核心計(jì)算步驟，第三部分主要驗(yàn)證不同數(shù)據(jù)集的評(píng)估方法以及算法的實(shí)施細(xì)則，第四部分為實(shí)現(xiàn)結(jié)果介紹，第五部分為本文的總結(jié)。

二 、三維對(duì)應(yīng)關(guān)系分組算法

最近鄰相似比：本文評(píng)估的算法的另一個(gè)基線為洛必達(dá)規(guī)則，它對(duì)應(yīng)的關(guān)系是特征空間中最近點(diǎn)和第二最近點(diǎn)的距離，可以用獨(dú)特的區(qū)域出口來匹配高分?jǐn)?shù)，其類似于SS的閾值策略，如果滿足：

三維霍夫投票：霍夫變換是一個(gè)比較流行的計(jì)算機(jī)視覺技術(shù)最初被用來檢測圖像的線性關(guān)系，在3DHV中，每個(gè)對(duì)應(yīng)關(guān)系在基于霍夫變換空間的基礎(chǔ)上投票。

線性內(nèi)部搜索：該算法是最近一項(xiàng)旨在解決3D問題的對(duì)應(yīng)關(guān)系配準(zhǔn)的問題，其核心思想是結(jié)合局部和全局特征描述以確定是否應(yīng)該投票，本文將該算法總結(jié)為三個(gè)主要步驟，初始化、局部投票和全局投票。

三 、評(píng)估方法

在第二部分中提到的所有算法已經(jīng)在選定的三個(gè)基準(zhǔn)上進(jìn)行評(píng)價(jià)，其中包括不同水平的噪聲、點(diǎn)密度變化、雜波、遮擋和局部重疊，所有算法的計(jì)算的內(nèi)點(diǎn)線性關(guān)系使用精確率和召回率來進(jìn)行測量，本節(jié)還介紹了每個(gè)算法的實(shí)現(xiàn)細(xì)節(jié)。

3.1 數(shù)據(jù)集

數(shù)據(jù)集主要包括B3R Dataset、U3OR Dataset、U3M Dataset，如圖2所示。

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

3.3 實(shí)施細(xì)節(jié)

本文評(píng)估算法的輸入，即初始對(duì)應(yīng)集C，通過Harris 3D關(guān)鍵點(diǎn)檢測、SHOT特征描述和L2距離特征匹配生成。在默認(rèn)設(shè)置中，我們將Harris三維探測器的Non Maxima-Suppression半徑設(shè)為3pr，為包含十萬個(gè)點(diǎn)的點(diǎn)云生成約1000個(gè)關(guān)鍵點(diǎn)。SHOT的支撐半徑為15pr，而判斷閾值等于4pr。關(guān)于每個(gè)算法的參數(shù)，我們將它們列入表1。值得注意的是，我們對(duì)tss進(jìn)行自適應(yīng)使用，因?yàn)橐粋€(gè)固定值是很難轉(zhuǎn)向不同質(zhì)量的特征匹配。NNSR和SI算法中的閾值與其原始文獻(xiàn)中的閾值保持一致。對(duì)于ST和GC算法，它們的閾值是通過調(diào)整實(shí)驗(yàn)確定的。在RANSAC算法中，考慮到初始對(duì)應(yīng)集的大小，分配10000個(gè)循環(huán)在有效性和效率之間達(dá)到平衡。

四 、實(shí)驗(yàn)結(jié)果

4.1 B3R數(shù)據(jù)集上的性能

對(duì)噪聲的魯棒性：噪聲對(duì)特征描述子的區(qū)分能力產(chǎn)生影響，從而產(chǎn)生一定量的虛假匹配。而在檢索上下文中，由于B3R數(shù)據(jù)集中所使用的模型具有豐富的幾何信息，inliers的比例通常較高。在這種情況下的結(jié)果如圖3(a)所示。從圖中可以看出，從總體查準(zhǔn)率和召回性能來看，RANSAC和SI似乎是所有評(píng)估建議中最好的兩個(gè)。一個(gè)有趣的發(fā)現(xiàn)是，在極端噪聲的情況下，NNSR甚至超過GC和3DHV。這是因?yàn)镹NSR傾向于選擇不同的對(duì)應(yīng)關(guān)系，這在該數(shù)據(jù)集上是特別充分的，因?yàn)槟Ｐ途哂胸S富的獨(dú)特結(jié)構(gòu)。而NNSR的召回率則保持在除SS之外的其他算法的較低。SI算法在高斯噪聲標(biāo)準(zhǔn)差小于0.15pr時(shí)具有良好的性能，當(dāng)噪聲進(jìn)一步嚴(yán)重時(shí)，其性能會(huì)出現(xiàn)明顯惡化，表明其對(duì)高高斯噪聲的敏感性。

對(duì)點(diǎn)密度變化的魯棒性：與噪聲類似，這個(gè)術(shù)語也影響描述符的獨(dú)特性。我們給出了圖3(b)中不同點(diǎn)密度下的結(jié)果。我們可以觀察到，這些算法在點(diǎn)密度變化影響下的性能與在噪聲下的性能類似。例如，RANSAC和ST再次給出最好的整體性能，其次是NNSR，3DHV和GC，但不同的是，在精度方面，當(dāng)降采樣比達(dá)到0.3時(shí)，SS甚至優(yōu)于SI，而在低分辨率情況下，NNSR和SI的召回性能均大幅下降，這是因?yàn)镾HOT對(duì)不同的點(diǎn)密度非常敏感，使得對(duì)于高分辨率的數(shù)據(jù)，特征具有弱的區(qū)分性(如NNSR原理)，雖然SI的原因是SHOT的LRF (例如，SI的全球投票階段的組成部分)在面對(duì)數(shù)據(jù)分辨率變化時(shí)的可重復(fù)性較小。

4.2 U3OR數(shù)據(jù)集的性能比較

對(duì)雜波的魯棒性：雜波是場景中非模型表面斑塊面積的百分比。在特征匹配過程中，雜波區(qū)域的表面貼片與模型中的貼片具有相似的幾何特性，會(huì)引起異常值。雜波量化電平的結(jié)果如圖3 (c)所示。由于三維目標(biāo)識(shí)別場景比檢索更具挑戰(zhàn)性[2]，所有算法都會(huì)出現(xiàn)明顯的性能下降，當(dāng)雜波程度小于75%時(shí)，RANSAC達(dá)到最好的精度性能。隨著雜波程度的進(jìn)一步增大，3DHV給出的性能最好。值得注意的是，ST算法在B3R數(shù)據(jù)集上表現(xiàn)最好，在U3OR數(shù)據(jù)集上表現(xiàn)相當(dāng)差，這是因?yàn)镾T試圖尋找大的等距保持的簇，這些簇很少在雜波百分比較高的場景中退出，在召回性能方面，SS、SI和GC表現(xiàn)優(yōu)于其他，權(quán)衡精度和召回率，3DHV和GC是雜波影響下的兩種最優(yōu)越的算法。

對(duì)遮擋的魯棒性：遮擋會(huì)導(dǎo)致形狀補(bǔ)丁不完整，給精確的特征描述帶來巨大挑戰(zhàn)。遮擋程度給定為被遮擋模型表面貼片與模型總面積的比值，如圖3（d）所示，當(dāng)遮擋程度小于70 %時(shí)，RANSAC精度性能最好，隨著遮擋程度增加到75%，GC優(yōu)于RANSAC為最佳。當(dāng)遮擋程度超過75%時(shí)，GC、SI和3DHV最終超過其他算法。在召回性能方面，對(duì)于所有級(jí)別的遮擋，SI均優(yōu)于其他所有算法，特別是在高度遮擋的場景，SS和ST仍然是本測試中性能較差的兩種算法。我們可以推斷，基于一致性的算法，如RANSAC和GC等，更適合于有遮擋的場景，而基于初始特征匹配分?jǐn)?shù)的算法，如SS和SI，在處理虛假匹配時(shí)具有較高的風(fēng)險(xiǎn)，因?yàn)閺恼趽醯膱鼍皦K測量的特征匹配分?jǐn)?shù)是可疑的。

4.3 U3W數(shù)據(jù)集的性能對(duì)比

對(duì)部分重疊的魯棒性：U3M數(shù)據(jù)集提供了不同程度重疊的匹配對(duì)。重疊度度量為兩個(gè)形狀對(duì)應(yīng)頂點(diǎn)數(shù)與最小頂點(diǎn)數(shù)之比，不同重疊度的結(jié)果如圖3(e)所示。所有算法的共同特點(diǎn)是，它們的性能通常隨著重疊程度的降低而下降。這是由于初始對(duì)應(yīng)集中異常值的比率與重疊區(qū)域的比率密切相關(guān)。在精度性能方面，RANSAC在60%~80%的重疊度范圍內(nèi)，對(duì)于所有級(jí)別的重疊度，一般都會(huì)大幅度超過其他，GC和ST表現(xiàn)相當(dāng)，其次是3DHV、NNSR、SI和SS，在召回率方面，SI優(yōu)于其他，尤其是重疊度小于70%時(shí)。

4.4 可變閾值ε的性能比較

閾值決定了我們?cè)诙啻蟪潭壬蠈⑼ㄐ排袛酁閕nlier。我們特此改變此閾值(默認(rèn)設(shè)置為4pr )，以考察被評(píng)價(jià)算法的性能變化。具體而言，我們?cè)谡麄€(gè)U3OR數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果如圖3(f)所示。正如預(yù)期的那樣，所有算法都能以更寬松的方式獲得更高精度的結(jié)果，特別是當(dāng)閾值在[ 2pr，5pr ]和[ 6pr，10pr ]范圍內(nèi)時(shí)，GC和RANSAC分別達(dá)到了最高的精度，SS的精度有微弱的提高，說明其判斷的多數(shù)inlier偏離了地面真實(shí)inliers，在召回率的inliers方面，隨著閾值的增大，SI和SS呈現(xiàn)增加的趨勢(shì)，而其他算法的性能幾乎不變。

4.5 不同初始條件的性能對(duì)比

針對(duì)不同的應(yīng)用，需要不同數(shù)量的初始對(duì)應(yīng)，例如形狀變形的密集匹配和粗掃描對(duì)齊的稀疏匹配。為此，我們?cè)赨3OR數(shù)據(jù)集上測試了這些算法對(duì)不同數(shù)量的初始對(duì)應(yīng)的性能，如圖3(g)所示。該圖表明，不同的算法在改變初始特征匹配數(shù)量時(shí)給出的響應(yīng)不同，一些算法，如GC，RANSAC和3DHV的性能隨著初始匹配數(shù)目的增加而波動(dòng)，同時(shí)，可以發(fā)現(xiàn)初始對(duì)應(yīng)集的大小對(duì)SI和ST算法的影響相對(duì)較強(qiáng)。具體來說，當(dāng)初始對(duì)應(yīng)數(shù)小于1000時(shí)，這兩種算法產(chǎn)生的精度較低，然而，隨著初始特征匹配變得密集，即1000多個(gè)對(duì)應(yīng)，SI和ST的精度性能迅速攀升，SI算法甚至以大約3000個(gè)初始對(duì)應(yīng)達(dá)到了次優(yōu)精度，這是由于密集的初始對(duì)應(yīng)關(guān)系能夠在SI的局部合并表決集中提供更可靠的成分，盡管如此，SI在初始對(duì)應(yīng)集的所有測試尺寸下都取得了最好的召回性能，以較大的差距超過了其他所有尺寸。

圖3 （a-g）7種對(duì)應(yīng)分組算法在實(shí)驗(yàn)數(shù)據(jù)集上的準(zhǔn)確率和召回率性能。(h) 同大小的初始對(duì)應(yīng)集的時(shí)間效率性能，其中y軸取對(duì)數(shù)為最佳視圖。

五、結(jié)論

本文在多種數(shù)據(jù)集上對(duì)三維對(duì)應(yīng)分組算法進(jìn)行了深入的評(píng)價(jià)，評(píng)價(jià)指標(biāo)包括在不同噪聲水平、點(diǎn)密度變化、雜波、遮擋、部分重疊、內(nèi)點(diǎn)判斷閾值、初始特征匹配大小和計(jì)算效率下的查準(zhǔn)率和召回率。鑒于這些評(píng)價(jià)結(jié)果，總結(jié)如下：（1）SS和NNSR作為依賴特征匹配相似性的兩個(gè)基線，對(duì)雜波、遮擋和部分重疊等干擾非常敏感。給定具有豐富幾何結(jié)構(gòu)的高質(zhì)量形狀，NNSR可以是一個(gè)同時(shí)提供實(shí)時(shí)性能的有效選擇。（2）ST算法對(duì)含有大量內(nèi)點(diǎn)的對(duì)應(yīng)集是有效的，但在三維目標(biāo)識(shí)別和2.5維視圖匹配等挑戰(zhàn)性環(huán)境下，ST算法的性能急劇下降。同樣，ST也被證明非常耗時(shí)，特別是對(duì)于大規(guī)模的對(duì)應(yīng)問題。（3）RANSAC在多種干擾下表現(xiàn)出優(yōu)越的精度性能，以犧牲相對(duì)較長的執(zhí)行時(shí)間為代價(jià)。因此，RANSAC適用于依賴稀疏匹配的離線應(yīng)用，如掃描配準(zhǔn)和三維建模。（4）3DHV是一種超高效的算法，在許多應(yīng)用中同時(shí)返回可接受的inlier搜索性能。這些優(yōu)點(diǎn)表明3DHV可以應(yīng)用于時(shí)間關(guān)鍵的應(yīng)用，如機(jī)器人的同步定位與地圖構(gòu)建( SLAM )、物體抓取和三維物體識(shí)別等。（5）對(duì)于需要密集特征對(duì)應(yīng)的應(yīng)用，SI將是最佳選擇。SI的一個(gè)核心缺點(diǎn)是在雜波和部分重疊的干擾下精度有限。在這種情況下，GC可以成為顯示整體更高精度的替代方案。

參考文獻(xiàn)

1.M. Leordeanu and M. Hebert. A spectral technique for correspondence problems using pairwise constraints. In Proceedings of the International Conference on Computer Vision,volume 2, pages 1482–1489. IEEE, 2005.

2.Y. Guo, M. Bennamoun, F. Sohel, M. Lu, J. Wan, and N. M.Kwok. A comprehensive performance evaluation of 3d local feature descriptors. International Journal of Computer Vision, 116(1):66–89, 2016.

備注：作者也是我們「3D視覺從入門到精通」知識(shí)星球特邀嘉賓

本文僅做學(xué)術(shù)分享，如有侵權(quán)，請(qǐng)聯(lián)系刪文。

3D視覺工坊-點(diǎn)云交流群

已建立3D視覺工坊-點(diǎn)云微信交流群！想要進(jìn)點(diǎn)云學(xué)習(xí)交流群的同學(xué)，可以直接加微信號(hào)：CV_LAB。加的時(shí)候備注一下：點(diǎn)云+學(xué)校+昵稱，即可。然后就可以拉你進(jìn)群了。

強(qiáng)烈推薦大家關(guān)注3D視覺工坊知乎賬號(hào)和3D視覺工坊微信公眾號(hào)，可以快速了解到最新優(yōu)質(zhì)的3D視覺與SLAM論文。