使用三维网格与霍夫转换於

1、使用三維網格與霍夫轉換於雷射掃點雲資料結構化暨分面之研究指導教授：趙鍵哲學生：黃國彥一前言雷射技術(Light Amplification by Stimulated Emission of Radiation, Laser)發明於 1960 年，顧名思義，雷射運作的原理即是以輻射激發光線的能量，因此也稱為激光賴，2003。雷射掃瞄到目標點反射後可由其時間差得知之間的距離，若是配合定位儀器，如：GPS，便能更進一步自掃瞄時的位置推出目標點的坐標，故對於量測或重建物空間資訊之應用越趨重要。以點的方式表現一件物體的外形需要數量繁多且密集的點群方能忠實呈現，因此處理龐大的雷射點雲資料即是一門重要的課

2、題，除了大量的點數外，另一個要面對的即是點雲形態為不規則散佈的問題，此時最常見的方式即是以內插處理光達點雲資料。然而內插後的規則網格會喪失空間資訊，對三維分佈的掃瞄點資料而言，以2.5D維度的表示法將掃瞄資料結構化，難以完整展現出掃瞄點精確描述地物的特性 賴，2003。但是要如何保存資料結構的完整性呢？如圖1.1所示，若將資料以Pseudo-Grid的方式結構化，除避免離散的光達點因經過內插而使得精度降低的情況發生，在處理時以網格為單位更可提升處理速度Cho et al., 2004。除Cho et al., 2004外，Tang, 2003亦在將資料三維網格化後，令有點之網格組成一3D之影像

3、，以進行後續匹配的動作。圖1.1Pseudo-Grid示意圖Cho et al., 2004雷射點雲分面的研究中，賴，2003曾提出以八分樹法為切割依據，並以每一點雲資料至擬合面之距離為設定的分割條件，若大於門檻值則繼續切割，直到任一子節點中僅有一個平面存在為止。而Lin, Jaw, 2003則是搜尋每一掃瞄點指定範圍內之相鄰點，並計算這些點所構成的平面法向量參數、平面精度以及目標點至平面之距離，將其統整後再以此相關性建構平面。先前曾試過以類似Cho et al., 2004與Tang, 2003的三維網格去結構化雷射點雲資料並分面，但由於耗時過久，在效率及發展性的情況考量下，引入霍夫轉換(H

4、ough Transform)，以期達到下列四個目的：1. 效率高2. 有效分離離散點3. 多尺度空間的面偵測4. 有效萃取各平面資訊二原理如前言所述，自龐大的光達點雲資料中直接進行分面的工作，是件極費工夫的事，因此，找出一套有效的邏輯使資料結構化再予以分面是首要問題；於此使用三維網格的方式，依資料在三維物空間中之分佈進行切割以達分類之目的，其後再以網格結構的面擬合與霍夫轉換找出共面之點群，以下將詳細說明。以三維網格使點雲資料結構化將點雲資料視為一個巨大的網格，並找出其在三維物空間中各坐標軸的極值，、，以此界定此網格的範圍並做為切割時的依據。之後視光達點數目多寡決定總分割次數，過少的分割次數會

5、造成一個網格內存有很多的光達點，而這些點群很有可能各自屬於不同平面，如此在其後分面時，將會嚴重影響完成後的成果；過多的分割次數則會使資料量增加，同時減低整體的效率，是故決定一個合理的分割次數是很重要的。由於每切割一次所增加的子網格數目是以倍在成長，因此，雖然切割次數只差一次，但其中的子網格數目的差距卻是很大的。此外，由於光達點雲並不一定均勻的分佈在網格中，是故不是每一個子網格都會有資料。考量到效率的因素，這些沒有光達點的子網格將視為空網格，且處理的過程中將視為不存在；之後所提及的子網格皆非此類之網格。待決定好切割的次數，、軸會被分為個區間，亦即這一個巨大的網格會被分為個子網格，每一個子網格皆含

6、有各自的編號，圖2.1.1即為切割一次時的網格示意圖。()()()()()()()()圖 2.1.1子網格編號示意圖以網格結構搜尋近似之法向量霍夫轉換在使用上有一定的限制條件，若是未給定近似之法向量，則運算時間會因此增加，是故在網格結構化後，需要先找出資料中各個面的近似法向量，霍夫轉換的過程與細節將會在說明之。在搜尋近似法向量的部份是利用網格的位相關係去進行，首先先任選一子網格做為起始的目標網格(Target Grid)，並自目標網格臨近的網格找尋適當的搜尋網格(Search Grid)，針對其中的所有光達點進行面擬合的工作。由於所需的僅只是近似的平面法向量，因此無需以一個子網格為單位去進行搜

7、尋的動作，多重網格搜尋即足矣，以下將說明如何利用多重網格搜尋近似的法向量。進行第次搜尋之前，需決定起始的目標網格Target Gridi為何者，此時搜尋網格Search Gridi範圍為目標網格同時自、三軸六個方向增減一層，同時計算所有目標網格與搜尋網格範圍中光達點群的擬合面法向量，若這些光達點群中的任一點與擬合面的距離小於門檻值時，繼續搜尋，且次的目標網格Target Gridi+1為第次的搜尋網格Search Gridi範圍；反之，若搜尋網格中的任一點與擬合面的距離大於門檻值時，代表搜尋範圍已含有非共面點之網格，為了不影響擬合精度，此時停止搜尋，且目標網格保持不變。同時為確保目標網格與搜尋

8、網格之間可組成平面，目標網格與搜尋網格所含之總點數最少需大於或等於三點。舉例說明，進行第一次多重網格搜尋時，假設目標網格編號為，則搜尋網格範圍為目標網格同時自三軸方向增加與減少一層，即自到，總計27格，之後這27格中的光達點一起進行面擬合。若每一點與擬合面之距離皆小於門檻值時，下一次的目標網格即為從到的這27格再往外擴展一層，總計125格，如圖2.2.2所示。圖 2.2.2多重網格搜尋示意圖(a) 第次目標網格(b) 第次搜尋網格(c) 第次目標網格(d) 第次搜尋網格(a)(b)(c)(d)利用霍夫轉換找出平面法向量以霍夫轉換搜尋共面點由於三維物空間中應用霍夫轉換以分面不易由圖形表示，故先以

9、其在二維空間應用之情況說明之，一線性方程式如式2.3.1所示：式 2.3.1將式2.3.1改寫為式2.3.2之形式：式 2.3.2：此直線之法向量：此直線上每一點之坐標：此直線之平移向量：線方程式上之點數若將與的角色互換，即針對每一座標組皆有一組對應之，原線性方程式在參數空間可繪出條直線，如式2.3.3所示：霍夫轉換後對應座標之直線法向量組式 2.3.3由於、本為一直線，故若包含於的範圍時，這些在參數空間的條直線會相交於一點，亦即每一組中皆擁有相同之法向量。今以如式2.3.4與圖2.3.1所示，一點數為點之直線方程式為例：圖 2.3.1直線(物空間)式 2.3.4將式2.3.4化為式2.3.2

10、之形式後再進行霍夫轉換會得到以下的結果：式 2.3.5Hough Transform式 2.3.6圖 2.3.2直線(霍夫轉換後)令中之或其中之一為一組接近或的近似值，在代入式2.3.6後即可得到另一組係數，將其繪製成圖則如圖2.3.2。由圖可知，經過霍夫轉換後，式2.3.6中的每一組皆會產一條直線，且、這十五組係數會交於圈起部份中的一點，此點即為式2.3.5中之。現以公式說明以上概念擴展至三維物空間的形式，一平面方程式如式2.3.7所示：式 2.3.7：此平面之法向量：此平面上每一點之坐標：此平面之平移向量：面方程式上之點數今假設其點數為三點，則式2.3.7在經過霍夫轉換後可寫為：式 2.3

11、.8：霍夫轉換後對應座標之平面法向量組使、其中兩者為一接近、的近似值，並代回式2.3.8後即可得到另外一組法向量。此時，若在、與的範圍內，則其對應的、與所繪出的三個面會交於一點，此點即為法向量。定義霍夫轉換時所代入之近似法向量雖然使用霍夫轉換可以很快速的得到，但要精確掌控使其必定包含是一件很困難的事，故需要使用網格結構搜尋進而得知近似法向量，再以此為基準，定義出之範圍以找出正確的。以現有之模擬資料與實際資料實驗後，將、定義如下：之近似法向量：之近似法向量式 2.3.9除此之外，近似法向量之值過大或過小皆會影響最後之結果，若是過大，則在代入式2.3.9後所得到、之範圍會隨之增加，霍夫轉換時的處理

12、時間亦會增加；若是過小，則所得到的、之範圍未必會包含正確的法向量。是故，此次研究是以式2.3.10調整近似法向量之值。式 2.3.10：修正後之近似法向量：放大倍率此次研究中模擬資料；實際資料判斷霍夫轉換後之法向量承上，由於計算時位數之故，且是以近似法向量進行計算，因此、與不可能完全與相同，此時由所組成的個面會群聚於一個範圍，而非交於一點。基於以上的原因，霍夫轉換後如何在一群聚的區塊中找出正確的平面法向量即為一個重要的問題，於此次研究中，是採類似影像處理的方式判斷，先以二維平面的霍夫轉換說明之。今一有個點之線性方程式，令中之為個接近的近似值，在代入式2.3.6後即可得到個對應的，此時建立一零矩

13、陣，行方向記錄值、列方向記錄值，若任意一組、所對應之行數與列數分於為、時，則，如此依序將每一個點之組、皆處理完，此時中最大值所對應之值即為法向量。同理，三維空間的霍夫轉換亦可以此法找出其法向量為何。以式2.3.11與圖2.3.3之面方程式為例，屬於其面之點數為點，經霍夫轉換後其最大值所坐落層數之影像則如圖2.3.4所示：圖 2.3.4以影像的方式表示轉換後最大值所在該層之分佈情況式 2.3.11圖 2.3.3面(物空間)由圖2.3.4可知，最大值之位置約略在左上，同時亦可看出，這些面逐漸往左上的部份群聚，最後可知、。理論上，點群轉換後所產生之面應只會交於一格，但由於先前所說之原因，此時最大值有

14、兩者，而這種情況可藉由調高的倍率解決。若將調至10，則可得、，且轉換後其最大值所坐落層數之影像如圖2.3.5所示：圖 2.3.5以影像的方式表示轉換後最大值所在該層之分佈情況三流程光達點至面的距離是否皆在門檻值內？定義起始網格定義多重搜尋網格範圍Yes面擬合判斷為共面點No是否所有光達點皆已處理？YesNo調整近似法向量之大小與霍夫轉換分面完成讀取光達點雲資料三維網格切割使其結構化圖 3.1流程圖四實例於此部份將以模擬資料驗證其邏輯之可行性；之後再引入實際資料，並藉由成果說明應用上所可能碰到的問題。共計採用兩種模擬資料，一為存有兩交會平面之點雲資料，試圖驗証是否可以準確將兩平面之交線訂出；一為

15、具高突物之點雲資料，試圖驗証是否可以偵測出高突物，其資訊如表4.1所示：模擬資料一模擬資料二總點數140070011平面一之點數700669-0.191-0.191-0.268-0.2680.0780.07811平面二之點數700310.415-0.311-0.271-0.4440.0750.13011表 4.1模擬資料資訊表4.2、圖4.1(a)、圖4.1(b)分別為模擬資料一經霍夫轉換前後之成果：所搜尋到之點數平面一(藍色)760-31-4412.874163.8平面二(紅色)64069.850-43.90012.391163.8表 4.2模擬資料一分面成果圖 4.1(a)模擬資料一原始點

16、雲圖圖 4.1(b)模擬資料一分面後點雲圖表4.2與表4.1比對後，其平面法向量相差無幾，但圖4.1(b)卻可以看到在交界處時分面成果仍顯不足，這將在之後結果討論部份說明之。表4.3、圖4.2(a)、圖4.2(b)分別為模擬資料二經霍夫轉換前後之成果：圖 4.2(a)模擬資料二原始點雲圖圖 4.2(b)模擬資料二分面後點雲圖所搜尋到之點數平面一(藍色)669-21-298.425108.35平面二0表 4.3模擬資料二分面成果模擬資料二的成果如預期所料，高突物並不會影響分面的成果，同時亦由於高突物部份的點數過少，故在多重網格搜尋時所得的近似法向量精度並不佳，因此即使將該近似法向量代回霍夫轉換亦

17、無法將其展示出來。在處理的速度上，模擬資料一與資料二的運算時間則如表4.4所示：點數多重網格以取得霍夫轉換近似值近似值其近似法向量(Sec)(Sec)之計算範圍之計算範圍模擬資料一140024.82113.447270模擬資料二70010.28520.999940表 4.4分面效率一覽表實際資料為成功大學圖書館側面的近景影像及地面光達資料，所使用之地面雷射掃描儀為加拿大Optech公司所生產之ILRIS-3D(劉，2004)，點數總計3306點、光達點先驗中誤差皆為。表4.5、圖4.3(a)、圖4.3(b)分別為實際資料經霍夫轉換前後之成果。平面一(藍色)-55-7824.6432884.2平

18、面二(紅色)119-7823.7142884.2平面三(紫色)8-91.5-290.652884.2平面四(黃色)-10-94-338.172884.2表 4.5實際資料分面成果圖4.3(a)實際資料原始點雲圖圖4.3(b)實際資料分面後點雲圖圖4.3(b)下方的平面三(紫色)與平面四(黑色)之分面成果較差，其原因將會於結果討論中一併加以說明。五結果討論使用三維網格結合霍夫轉換與僅使用三維網格化以分面之速度相比，前者大約只需後者的，但三維網格結合霍夫轉換仍受限於起始值的優劣，亦即近似法向量的給定。若在多重網格搜尋時無法得到較佳的近似法向量，或由於某些原因使得部份的面未被偵測到，如此將會嚴重影響

19、到成果。圖4.3(b)的平面三與平面四部份即是由於此三個面的法向量過於接近，且皆包含於給定的近似法向量之範圍內，因此使得應屬於兩平面之點群被誤判或合併的情形產生。針對此問題，有以下五種改進方式：1. 在切割時以較多的子網格，即更切割的更細密，如此在多重網格搜尋時，可以得到更為精準的近似法向量，同時亦可避免如圖4.1(b)，在兩平面交界處容易發生混淆的情形。2. 在多重網格搜尋以求得近似法向量時，若其並非同時自、三軸六個方向增減一層，而是先成長其中一軸，待搜尋到多個面存在的網格時再延另外一軸成長，如此循序至每一方向皆達停止搜尋條件，如此可得到更為精準且群聚的初始平面。3. 在多重網格搜尋以求得近

20、似法向量時，可再額外記錄對應該平面法向量之點群改正數，由改正數之大小判定其結果的優劣，若有兩個或以上的面被誤判為同一個面，則可考慮提高式2.3.9之範圍，使得近似法向量之範圍含括這些平面之法向量。4. 除第3點外，或可將改正數較大之點所位於的網格找出，並針對這些網格及其鄰近範圍之網格一併進行再度切割的動作，使子網格可以以更細小的單元去描述此地形，並期達到分離非共面點群的目的。5. 在霍夫轉換時使用三維極座標系統，由於以三維極座標的方式表達空間內任一點時，皆可由兩個角度與半徑構成，因此可取代現今需先得到近似法向量方可繼續霍夫轉換的工作，但運算量勢必會增加許多。且若是光達點雲資料龐大、存有複雜且多

21、的平面，或許使用三維極座標會比較有效率；而對於地貌單純的情形，三維極座標則因為運算次數過多，造成運算時間暴增。此外，由於兩平面交線的周遭點群會同時滿足此兩平面之法向量，因此在霍夫轉換時會發生點群重複或被判定到另一平面的情況，如圖4.1(b)。這可藉由將重覆點取出，並由兩平面所交出來之線方程式去判定這些點群落在線的何方，以次做為分離交會處點群的判斷邏輯。若分離結果仍然差強人意，則可於分離之後，再次求得更為精準的法向量與線方程式，重覆進行判斷的動作，直到改正數或情況符合停止條件為止。雖然仍有以上問題尚需處理，但三維網格結合霍夫轉換以分面除了快速外，亦有多尺度(Multi-Resolution)的功用，在進行多重網格搜尋時，除了近似法向量會被記錄外，對應於該近似法向量之光達點數亦會一同被保存，因此可藉由此點濾除較為破碎或細小