基于多視幾何的重疊點(diǎn)云刪除算法

郭 進(jìn)，袁建英，陳小寧

（1.西南財(cái)經(jīng)大學(xué) 天府學(xué)院，四川 綿陽621000；2.西南交通大學(xué) 機(jī)械學(xué)院，四川 成都610000；3.昆明學(xué)院 自動(dòng)控制與機(jī)械工程學(xué)院，云南 昆明650214）

0 引 言

多頻相移的結(jié)構(gòu)光三維測(cè)量系統(tǒng)需要進(jìn)行多次拼接測(cè)量，才能得到大范圍物體的全局點(diǎn)云，當(dāng)把多次視圖下測(cè)量獲得的多片點(diǎn)云拼接成一個(gè)完整點(diǎn)云時(shí)［1］，拼接后兩次點(diǎn)云的重疊區(qū)域會(huì)產(chǎn)生大量的冗余點(diǎn)。冗余點(diǎn)云的數(shù)據(jù)量也會(huì)隨拼接次數(shù)的增多越來越大，進(jìn)而影響后期三維點(diǎn)云數(shù)據(jù)的處理，降低三維建模的速度和精度。

重疊區(qū)域的冗余點(diǎn)刪除一般都是三維點(diǎn)云的后處理，梁新合等人采用法向約束的點(diǎn)云融合方法，但該方法對(duì)種子點(diǎn)依賴大［2］，曹巨明等采用移動(dòng)最小二乘進(jìn)行多視點(diǎn)云數(shù)據(jù)融合，不過他們的算法時(shí)間代價(jià)依舊不?。?］；杜曉暉采用混合模式精簡(jiǎn)點(diǎn)云［4］；楊斌采用多分辨率簡(jiǎn)化算法［5］，算法的計(jì)算量都十分大；Nira Dyn等［6］構(gòu)造了一個(gè)非負(fù)函數(shù)用于度量數(shù)，根據(jù)點(diǎn)的重要性，然后采用基于迭代的方法對(duì)點(diǎn)云進(jìn)行簡(jiǎn)化，但速度不快。根據(jù)點(diǎn)的重要性，采用基于迭代的方法對(duì)點(diǎn)云進(jìn)行簡(jiǎn)化，黃文明等人采用計(jì)算樣點(diǎn)對(duì)最小二乘移動(dòng)曲面的影響大小，簡(jiǎn)化點(diǎn)云，但涉及非線性優(yōu)化計(jì)算過程復(fù)雜［7］。以上方法都是從三維點(diǎn)云的角度出發(fā)，采用八叉樹等數(shù)據(jù)結(jié)構(gòu)［8］，通過計(jì)算點(diǎn)云的曲率，密度等信息來刪除多余的點(diǎn)云，這些方法的計(jì)算量大，效率低，無法保證原始掃描數(shù)據(jù)等信息。

本文避開傳統(tǒng)的點(diǎn)云后處理方法，利用測(cè)量對(duì)象物點(diǎn)的唯一性原理，以及三維點(diǎn)云與多視圖中二維圖像之間的對(duì)應(yīng)關(guān)系，在拼接測(cè)量中自動(dòng)計(jì)算出每一次拼接與前面多次測(cè)量中的重疊區(qū)域，對(duì)于重疊區(qū)域內(nèi)的二維點(diǎn)就不在進(jìn)行匹配重構(gòu)計(jì)算，從根源上避免了重疊區(qū)域內(nèi)冗余點(diǎn)數(shù)據(jù)的產(chǎn)生。

1 冗余點(diǎn)刪除算法

基于雙目視覺的結(jié)構(gòu)光三維測(cè)量系統(tǒng)，測(cè)量前先用張正友平板標(biāo)定對(duì)成交姿狀態(tài)的相機(jī)進(jìn)行標(biāo)定，得到相機(jī)的內(nèi)外參數(shù)，世界坐標(biāo)系建立在左攝像機(jī)上，與左相機(jī)的坐標(biāo)系重合［9］。每次掃描中左右攝像機(jī)內(nèi)部參數(shù)一致，外部參數(shù)所在坐標(biāo)系都不統(tǒng)一?？筛鶕?jù)在物體上粘貼標(biāo)記或者無標(biāo)記拼接的方式計(jì)算兩次測(cè)量之間的變換矩陣，這樣可以把多次掃描的相機(jī)外參數(shù)統(tǒng)一到一個(gè)坐標(biāo)系下，利用光束法平差對(duì)外參數(shù)進(jìn)行優(yōu)化，根據(jù)多極線約束刪除冗余點(diǎn)。

如圖1 所示，有統(tǒng)一的世界坐標(biāo)系OXYZ，P1L 和P1R 為第一次測(cè)量左右相機(jī)對(duì)空間中P 點(diǎn)的像點(diǎn)，P2L 和P2R 為第二次測(cè)量左右相機(jī)對(duì)空間中同一P 點(diǎn)的像點(diǎn)，由空間三角幾何關(guān)系以及相機(jī)標(biāo)定參數(shù)，由第一次的像點(diǎn)P1L（x1L，y1L）和P1L（x1R，y1R）可以求解出P 點(diǎn)的三維坐標(biāo)（xpypzp），同理由第二次的像點(diǎn)P2L（x2L，y2L）和P2L（x2R，y2R）和可以求解出P點(diǎn)的三維坐標(biāo)（x′py′pz′p）。兩次測(cè)量都是同一空間點(diǎn)P，因此計(jì)算出的（xpypzp）和（x′py′pz′p）產(chǎn)生了冗余點(diǎn)，相機(jī)成像光線具有可逆性，把（x′py′pz′p）點(diǎn)向第一次左相機(jī)做反投影，如果反投影點(diǎn)落在成像平面上，并且該點(diǎn)在第一次測(cè)量中已經(jīng)計(jì)算過，則該點(diǎn)為冗余點(diǎn)可以刪除，對(duì)于曲率變化大的區(qū)域采用計(jì)算比較反投影殘差大小進(jìn)去取舍和保留。

1.1 多視相機(jī)外參坐標(biāo)系統(tǒng)一

由SVD 分解求解出兩視之間的變換矩陣M，第一次測(cè)量下坐標(biāo)系為O1X1Y1Z1，左右相機(jī)的投影矩陣分別為PM1L和PM1R，第二次測(cè)量下坐標(biāo)系為O2X2Y2Z2，左右相機(jī)的投影矩陣分別為PM2L和PM2R，由SVD 奇異值分析［10］可以求得兩次測(cè)量之間的變換矩陣M

把第二次的投影矩陣變換到O1X1Y1Z1下

則由PM′2L和PM′2R計(jì)算出來的點(diǎn)云坐標(biāo)系統(tǒng)一到了O1X1Y1Z1下。

1.2 重疊區(qū)域內(nèi)三維點(diǎn)計(jì)算

基于雙目相機(jī)的結(jié)構(gòu)光測(cè)量中，對(duì)空間被測(cè)量對(duì)象采樣越高，獲取的三維點(diǎn)就越稠密，可以更好反應(yīng)物體細(xì)節(jié)，但是當(dāng)拼接測(cè)量過程中，相機(jī)的拍攝角度關(guān)系，會(huì)出現(xiàn)兩次測(cè)量過程對(duì)同一空間的采樣率不同，而出現(xiàn)空間兩點(diǎn)甚至多點(diǎn)在某一次圖像的反投影上映射到一個(gè)點(diǎn)的情況，實(shí)際上空間中缺間隔一段距離。因此，在計(jì)算圖像重疊區(qū)域內(nèi)三維點(diǎn)時(shí)，需要保留空間采樣率大的圖像計(jì)算三維點(diǎn)，保證細(xì)節(jié)不丟失。另外，當(dāng)空間采樣率接近時(shí)，重疊區(qū)域在不同視圖下計(jì)算的三維點(diǎn)精度不同，為了提高冗余點(diǎn)刪除后點(diǎn)云的精度，需要比較反投影殘差從兩次掃描中保留精度較高的點(diǎn)，高曲率和高精度點(diǎn)處理算法設(shè)計(jì)如下。

定義物體表面的單位平面為一個(gè)邊長(zhǎng)為ε的正方形。其中，ε為正向掃描平面時(shí)，像平面中心區(qū)域?qū)?yīng)的三維點(diǎn)點(diǎn)距均值，在本文中ε取0.02mm。定義像平面單位平面為一個(gè)邊長(zhǎng)為e的正方形，其中，e取1，即表示單位像素。令第一次掃描左圖像上的像點(diǎn)P11，相應(yīng)的三維點(diǎn)位P′1，反投影殘差為e1，第二次掃描左圖像上的像點(diǎn)P21，相應(yīng)的三維點(diǎn)為P″1，反投影殘差為e2，將P″1反投影到第一次掃描左右圖像上，反投像點(diǎn)坐標(biāo)為P′11，若‖P11－P′11‖≤e且‖P′1－P″1‖≥ε，則表示計(jì)算出P′1和P″1的像點(diǎn)像素距離不超過e，但是這兩個(gè)點(diǎn)位于物體上不同單位平面，都要保留。若‖P11－P′11‖≤e且‖P′1－P″1‖＜ε，則表示P′1和P″1屬于同一單位平面內(nèi)相距很近的兩點(diǎn)，故只需保留一個(gè)。為保留精度較高者，判斷e1，e2 大小，若e1＜e2，保留P′1，反之保留P″1。

1.3 多次掃描重疊區(qū)冗余點(diǎn)去除算法流程

對(duì)較大物體進(jìn)行全局拼接掃描，隨著掃描次數(shù)增加，公共區(qū)域冗余點(diǎn)云也會(huì)增加，重疊區(qū)域冗余點(diǎn)去查算法流程如下：

步驟1 第1次測(cè)量，不需要進(jìn)行冗余點(diǎn)刪除，計(jì)算投影矩陣PM1L和PM1R，得到三維點(diǎn)云，標(biāo)記第1次參與運(yùn)算的點(diǎn)Mask［i］［u］［v］表示第i次掃描左圖像坐標(biāo)為（u，v）的點(diǎn)是否參與過三維點(diǎn)計(jì)算，第1次測(cè)量i＝1。

步驟2 第2次拼接測(cè)量開始，匹配標(biāo)記三維標(biāo)記點(diǎn)，計(jì)算當(dāng)次變換矩陣M2。

步驟3 由變換矩陣對(duì)第2次測(cè)量的左右相機(jī)投影矩陣進(jìn)行坐標(biāo)系統(tǒng)一，得到PM′2L和PM′2R。

步驟4 由投影矩陣PM′2L和PM′2R計(jì)算當(dāng)次三維點(diǎn)云數(shù)據(jù)Q2（x，y，z），然后把三維點(diǎn)云數(shù)據(jù)向第1次左相機(jī)進(jìn)行反投影，采用1.3所述方法進(jìn)去計(jì)算，標(biāo)記第2 次參與運(yùn)算的點(diǎn)Mask［i］［u′］［v′］。

步驟5 第i次拼接測(cè)量開始重復(fù)步驟2～步驟4，第i次向前1，2，3….i－1次進(jìn)行反投影。

1.4 本文算法具有以下優(yōu)點(diǎn)

（1）可以自動(dòng)識(shí)別拼接測(cè)量中的重疊區(qū)域，僅對(duì)重疊區(qū)域冗余點(diǎn)進(jìn)行處理而不破壞非重疊區(qū)域點(diǎn)的測(cè)量精度和采樣密度。在重疊部分，定義單位空間，對(duì)單位空間內(nèi)的三維點(diǎn)僅保留一個(gè)，即只進(jìn)行了一次計(jì)算。由于在計(jì)算三維點(diǎn)時(shí)，算法并沒有改變相機(jī)參數(shù)，也沒有改變?cè)嫉膱D像匹配關(guān)系，因此所計(jì)算的三維點(diǎn)值和原始點(diǎn)云中某個(gè)點(diǎn)的值一致，即不會(huì)破壞原始點(diǎn)云質(zhì)量。

（2）能提高點(diǎn)云整體精度。在結(jié)構(gòu)光掃描系統(tǒng)中，點(diǎn)云的精度受相機(jī)標(biāo)定精度、圖像點(diǎn)匹配精度等影響。雙目反投影殘差可以定量衡量雙相機(jī)像平面上像點(diǎn)、光心、物點(diǎn)構(gòu)成三角形的誤差，也就從理論上可以衡量各種誤差對(duì)重建的綜合影響。在本文算法中，用這一指標(biāo)來去除重合區(qū)域內(nèi)精度較低的點(diǎn)，保留精度較高的點(diǎn)，因此從理論上提高了點(diǎn)云的整體質(zhì)量。實(shí)現(xiàn)了冗余點(diǎn)刪除效率的最大化。從圖像上將兩次掃描點(diǎn)云劃分開，在單位平面內(nèi)選擇精度較高者保留。

（3）本文算法核心點(diǎn)有兩個(gè)，一是找出重疊區(qū)域，二是對(duì)重疊區(qū)域內(nèi)進(jìn)行單次物點(diǎn)計(jì)算。兩個(gè)核心點(diǎn)計(jì)算過程都需要每次掃描時(shí)雙相機(jī)在全局坐標(biāo)系下的投影矩陣。而不管哪種拼接方法，要實(shí)現(xiàn)坐標(biāo)系的統(tǒng)一，都需要計(jì)算當(dāng)前視圖像在全局坐標(biāo)系下的投影矩陣，所以本文算法對(duì)常見的拼接方式均適用。針對(duì)結(jié)構(gòu)光測(cè)量的特性，該方法還可以應(yīng)用于大型物體如汽車等的測(cè)量，配合攝影測(cè)量系統(tǒng)，把單次點(diǎn)云配準(zhǔn)到全局標(biāo)記點(diǎn)的時(shí)候，避免重疊點(diǎn)云的產(chǎn)生，大大減少冗余數(shù)據(jù)，提高了三維建模效率。

2 實(shí)驗(yàn)驗(yàn)證

本文中搭建的三維光學(xué)測(cè)量系統(tǒng)由一個(gè)光柵投射器（三菱公司DX－320型號(hào)的投影儀，分辨率1024＊768，亮度2500流明）和兩個(gè)大恒的工業(yè)攝像機(jī)及施耐德鏡頭組成（分辨率1280＊1024，焦距12mm），標(biāo)定板和計(jì)算機(jī)以及三腳架組成。

首先對(duì)三維測(cè)量系統(tǒng)進(jìn)行標(biāo)定［11］，得到攝像機(jī)的內(nèi)部參數(shù)和外部參數(shù)，利用粘貼的圓心標(biāo)記點(diǎn)，對(duì)壇子進(jìn)行兩次拼接測(cè)量，測(cè)量方式采用多頻外差原理［12］，點(diǎn)云相位求解采用負(fù)指數(shù)序列展開［13，14］，匹配圓心標(biāo)記點(diǎn)由SVD 法計(jì)算得到M 矩陣，利用本文的算法對(duì)重疊區(qū)域的標(biāo)記點(diǎn)進(jìn)行識(shí)別刪除。如圖2（a）為兩次測(cè)量點(diǎn)云重疊部分放大示意圖，從圖中可以看出在標(biāo)記圓的周圍深色部分為拼接后點(diǎn)云重疊部分，產(chǎn)生了大量冗余點(diǎn)云。從圖2（b）為本文算法處理后刪除了重疊區(qū)域冗余點(diǎn)的示意圖，從圖2（b）中可以看出冗余點(diǎn)的刪除達(dá)到了最大化。上述實(shí)驗(yàn)驗(yàn)證了算法對(duì)重疊區(qū)域冗余點(diǎn)刪除的有效性。對(duì)比圖2點(diǎn)云仍可很好描述物體三維形貌。

圖2 多視圖幾何關(guān)系約束

為了更進(jìn)一步驗(yàn)證本文算法性能，取重疊區(qū)域的一塊點(diǎn)云，對(duì)比傳統(tǒng)冗余點(diǎn)云刪除算法和本文算法處理后效果。將本文的處理結(jié)果與逆向軟件Geomagic Studio中的統(tǒng)一采樣和曲率采樣進(jìn)行了比較分析，取被測(cè)量壇子曲率變化最大的區(qū)域進(jìn)行了三角化比較，由表1可以看出，本文算法相比統(tǒng)一采樣和曲率采樣［15］達(dá)到了冗余點(diǎn)刪除了效率最大化。圖3（a）為原始點(diǎn)云，原始點(diǎn)云中存在很多冗余點(diǎn)，三角化后冗余三角片也較多如圖4（a），圖3（b）和圖3（c）分別為采用統(tǒng)一采樣和曲率采樣后點(diǎn)云效果圖，冗余點(diǎn)雖然已經(jīng)減少，但是不能徹底消除，圖4（b）和圖4（c）分別為三角化結(jié)果，經(jīng)過這兩種算法處理后的點(diǎn)云不再光順，圖3（d）是經(jīng)本文算法處理后的點(diǎn)云，從表1也可知本文冗余點(diǎn)刪除效率較高，圖4（d）為本文算法后三角化效果，不管是從光順度，還是點(diǎn)密度以及細(xì)節(jié)表現(xiàn)能力上都非常接近。圖5為被測(cè)量物體采用本文算法刪除冗余點(diǎn)云后的三角化結(jié)果，點(diǎn)云表面光順。綜上，本文所提出的算法能在冗余點(diǎn)刪除效率與刪除后點(diǎn)云質(zhì)量之間保持平衡，既有較大的刪除效率，又能保持物體原始細(xì)節(jié)信息。

表1 本文算法與其它算法的對(duì)比結(jié)果

圖3 不同算法曲率較大處點(diǎn)云對(duì)比

圖4 不同算法曲率較大處三角化對(duì)比

圖5 刪除重疊點(diǎn)云后三角化

3 結(jié)束語

傳統(tǒng)點(diǎn)云處理算法一般都是在生成點(diǎn)云后期進(jìn)行，包括點(diǎn)云去噪平滑，刪除重疊點(diǎn)云，以及三角化等，需要對(duì)點(diǎn)云建立拓?fù)浣Y(jié)構(gòu)，算法往往消耗的時(shí)間也較長(zhǎng)。本文提出的重疊點(diǎn)云刪除算法是在結(jié)構(gòu)光測(cè)量系統(tǒng)得到三維點(diǎn)云之前，利用多視圖約束以及物點(diǎn)唯一性的原理，從根源上對(duì)重疊點(diǎn)云進(jìn)行了刪除，避免了冗余點(diǎn)的產(chǎn)生，實(shí)驗(yàn)證明了該方法在多次拼接測(cè)量中，在保證單次測(cè)量精度和點(diǎn)云密度的情況下，無論是平面還是曲面都可以有效是去除冗余點(diǎn)，更好保留物體細(xì)節(jié)。

［1］YANG Yingbao，LIU Xianyong，YANG Junping.Pointclouds registration algorithm based on improve projection ［J］.Application Research of Computers，2011，28 （10）：3954－3956 （in Chinese）. ［楊英保，劉先勇，楊俊平.一種基于改進(jìn)投影方法的點(diǎn)云拼接算法 ［J］.計(jì)算機(jī)應(yīng)用研究，2011，28（10）：3954－3956.］

［2］LIANG Xinhe，LIANG Jin，GUO Cheng，et al.Multi range images integration algorithm based on normal constraint ［J］.Journal of Xi’an Jiao Tong University，2009，43 （5）：71－75（in Chinese）.［梁新合，梁晉，郭成，等.法向約束的多幅點(diǎn)云數(shù)據(jù)融合算法 ［J］.西安交通大學(xué)學(xué)報(bào)，2009，43 （5）：71－75.］

［3］CAO Juming，WU SHOUR－Slam，LIANG Jin，et al.Moving least squares based incremental multi－view range images integration algorithm ［J］.Journal of Xi’an Jiao Tong University，2009，43 （9）：46－50 （in Chinese）.［曹巨明，吾守爾·斯拉木，梁晉，等.移動(dòng)最小二乘增量式多視點(diǎn)云數(shù)據(jù)融合算法［J］.西安交通大學(xué)學(xué)報(bào)，2009，43 （9）：46－50.］

［4］DU Xiaohui，YIN Baocai，KONG Dehui.Mixed simplification algorithm of point clouds［J］.Computer Engineering and Applications，2007，43 （34）：43－45 （in Chinese）.［杜曉暉，尹寶才，孔德慧.一種點(diǎn)云混合簡(jiǎn)化算法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43 （34）：43－45.］

［5］YANG Bin，F(xiàn)AN Yuanyuan，WANG Jidong.Multi－resolution simplification algorithm for point cloud ［J］.Journal of Computer Applications，2011，31 （10）：2717－2720 （in Chinese）.［楊斌，范媛媛，王繼東.點(diǎn)云模型的多分辨率簡(jiǎn)化算法 ［J］.計(jì)算機(jī)應(yīng)用，2011，31 （10）：2717－2720.］

［6］Dyn N，Iske A，Wendland H.Meshfree thinning of 3Dpoint clouds ［J］.Foundations of Computational Mathematics，2008，8 （4）：409－425.

［7］HUANG Wenming，PENG Xiwei，WEN Peizhi，et al.Simplification of scattered point cloud with geometric feature reservation ［J］.Computer Engineering and Applications，2009，45（28）：168－170 （in Chinese）.［黃文明，彭希為，溫佩芝，等.保留幾何特征的散亂點(diǎn)云簡(jiǎn)化方法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45 （28）：168－170.］

［8］WANG Hongtao，ZHANG Liyan，DU Ji，et al.Simplification and error analysis based on implicit surface for measuring point－sets［J］.Journal of Image and Graphics，2007，12（11）：2114－2118 （in Chinese）.［王宏濤，張麗艷，杜佶，等.測(cè)量點(diǎn)集的簡(jiǎn)化及其隱式曲面重建誤差分析 ［J］.中國圖象圖形學(xué)報(bào)，2007，12 （11）：2114－2118.］

［9］CHEN Xiabo，XI Juntong，YE Jin.Accurate calibration for a camera－projector measurement system based on structured light projection ［J］.Optics and Lasers in Engineering，2009，47（3－4）：310－319.

［10］GUO Jin，LIU Xianyong，CHEN Xiaoning，et al.An unmarked 3Dpoint cloud automatic registration technology ［J］.Computer Applications and Software，2012，29 （4）：144－147 （in Chinese）.［郭進(jìn)，劉先勇，陳小寧，等.一種無標(biāo)記點(diǎn)三維點(diǎn)云自動(dòng)拼接技術(shù) ［J］.計(jì)算機(jī)應(yīng)用與軟件，2012，29 （4）：144－147.］

［11］ZHANG Z，MA H，ZHANG S，et al.Simple calibration of aphase－based 3Dimaging system based on uneven fringe projection ［J］.Optics Letters，2011，36 （5）：627－629.

［12］LI Lulu，SU Xianyu，DOU Yunfu，et al.Error analysis and algorithm design of temporal phase unwrapping ［J］.Journal of Sichuan University （Natural Science Edition），2012，49（1）：102－108 （in Chinese）. ［李璐璐，蘇顯渝，竇蘊(yùn)甫，等.時(shí)間相位展開的誤差分析與算法設(shè)計(jì) ［J］.四川大學(xué)學(xué)報(bào) （自然科學(xué)版），2012，49 （1）：102－108.］

［13］XU Wei，CHEN Xiaobo，XI Juntong.A method of phase error compensation for structural light measurement［J］.Acta Optica Sinica，2011，31 （3）：1－6 （in Chinese）.［許偉，陳曉波，習(xí)俊通.結(jié)構(gòu)光測(cè)量相位波動(dòng)誤差補(bǔ)償方法研究 ［J］.光學(xué)學(xué)報(bào)，2011，31 （3）：1－6.］

［14］Feipeng Da，Hao Huang.A fast，accurate phase unwrapping method for wavelet－transform profilometry ［J］.Optics Communications，2012，285 （4）：421－432.

［15］LIN Xiufang.Study on data sampling algorithm of reverse engineering ［J］.Electronic Design Engineering，2012，20（11）：23－26 （in Chinese）. ［林秀芳.逆向工程中的點(diǎn)云采樣算法研究 ［J］.電子設(shè)計(jì)工程，2012，20 （11）：23－26.］