二維地形圖是記錄都市地區地表地物現況的主要圖資，隨著科技技術之進步，二維地理資訊系統逐漸往三維數碼城市發展，兩者內涵豐富且多元，然都會區比例最高的人為構造物非建物莫屬，因此建物可說是二維與三維圖資中最基本的主要元素之一。一般來說，兩者多透過航測方式產製，但其過程通常較繁複且需人為介入，為提高半自動或自動化重建之可能性，越來越多研究引進光達點雲資料。光達系統直接記錄地表地物的三維坐標與雷射訊號反射強度，離散的點雲分佈所具有的特徵資訊是隱性的，因此如何從點雲中萃取出隱含之幾何特徵（如點、線、面）是一門重要的課題。一般而言，點雲高密度之特性有利於面特徵的萃取，而線特徵可透過面交會之方式獲取，然此法通常適用於屋頂內部結構線之萃取，因空載點雲中所含有的垂直牆面通常較為稀疏甚至沒有，房屋外部輪廓線之萃取變得較為困難，基於此，本研究發展一套演算法，企圖從空載光達點雲中自動化萃取房屋邊界線。
由於建物存在高低差之區域（即建物輪廓線附近）的點雲資料多存在多重回訊點，經觀察發現其第一與中間回訊通常傳達建物邊界之訊息，因此本研究結合反射回訊與建物邊界點進行邊界線之自動化萃取，流程包含點雲預處理、建物邊界點偵測、以及建物邊界線萃取。點雲預處理係以點雲處理套裝軟體進行分類，將點雲初步分成地面、植被、建物、與其他四類，而後人工編修提取建物點雲，再針對多層結構之平頂建物萃取三維平面特徵。建物邊界點偵測包含估計多層平頂建物之屋頂面高度，針對屋頂面以上之建物點雲，改善凸殼演算法（稱為凹殼演算法）進行邊界點追蹤，產生粗略之建物輪廓線。建物邊界線萃取則以第一與中間回訊點為輔，應用霍夫轉換分離屬於不同邊界之點群，以點到直線之距離需小於門檻值為約制條件，迭代求解共線點之最佳擬合直線，以點位的高程資訊賦予直線高度，最後偵測線段並將點群之兩端點反投影至擬合直線得到邊界線段。
實驗中挑選十棟不同結構之建物，以萃取成果之正確度與完整度，驗整演算法之可行性，並探討各階段中點雲分布與參數之關係，歸納出能因應多元複雜建物之最適參數。實驗結果顯示第一與中間回訊點能有效提升邊界線萃取的完整度，正確度與完整度之量化統計，在含有屋脊之建物部分，第I類邊界線之平均正確率約為71%。在多層結構之平頂建物部分，第I類邊界線之正確率約為60%，部分可達80%以上，第II類邊界線部分，萃取率都在85%以上，甚至可達90%左右，顯示出本研究提出之演算法，對於從空載光達點雲資料萃取建物邊界線是有成效的。就自動化程度而言，過程中不須經過太多的人為介入，自動化程度高，且萃取之成果能經過後續加以整合，的確對未來的建物模型重建是有潛力的。

2D topographic maps are the main map data of recording objects information on ground in urban area. Along with the progress of technology, 2D geographic information system trends to 3D cyber city. Both contain rich components, however, building boundary is one of the important components for the mapping of 2D digital topographic maps and the modeling of 3D city buildings. Photogrammetry is currently the common technique applied for building boundary generation. However, photogrammetric approaches to building reconstruction are still labor intensive and time consuming. Many researches have proposed the use of airborne LiDAR data to increase the automation of the reconstruction process. Airborne LiDAR data directly provide the three dimensional coordinates and the reflectivity information of the scanned objects, resulting in a lot of discrete points with very high density also known as LiDAR point clouds. However, the characteristics of objects such as building corners (point feature); building boundary (line feature); and roofs (plane feature); are implicitly contained in the data set. Those characteristics of objects need other process or algorithms to be extracted for further applications. Airborne LiDAR points are not evenly distributed on building surfaces. Usually top surfaces, such as roofs, may have densely distributed points, but vertical surfaces, such as walls, usually have sparsely distributed points or even on points. It means that while plane features of roofs can be extracted appropriately, plane features of walls could be very vague for extraction. Building boundaries, referring to the intersections of roof and wall planes are, therefore, not clearly defined in point clouds.To overcome this problem, this paper develops an algorithm to acquire building boundary from airborne LiDAR data.
Three major process steps are included in the algorithm. Firstly the point clouds are classified as building points and non-building points using the commercial software, TerraScan. Then, octree-based split-and-merge segmentation approach is applied for building points to extract 3D plane features. Second, those building points and coplanar points are then used to trace the boundary points by the modified convex-hull algorithm, so called concave-hull algorithm. Boundary points of coplanar point group and building points and the first and intermediate echo points of multi-return scan are selected as candidates of building boundary points. Third, methods of the Hough transform, line fitting and line segmentation are applied to find line segments belonging to building boundaries. After the Hough transform process, the collinear points can be detected. A line fitting process is applied to obtain the best-fitting line of these collinear points. The height information of straight line from average z coordinate can be obtained after height fitting process. Then, several line segments represented by the two endpoints of the fitting lines are finally obtained.
The test data in our experiments include ten buildings. The degree of correctness and completeness of results will be checked by comparing the extracted boundaries with that in 2D digital topographic map data, which can inspect and verify the feasibility of the algorithm. Also, the relationship between point cloud distribution and parameters in each step are probed in order to induce the most appropriate parameters. The experiment results show the effectiveness of the proposed method for automatic building boundary extraction from airborne LiDAR data, and that combining the information of the first and intermediate echo points of multi-return and the boundary points increases the completeness of boundaries. And, it is promising to use the extracted boundaries for 3D building modelling in the future.

內政部(2010)，建置都會區一千分之一數值航測地形圖作業工作手冊，臺北：內政部。
陳衍豪(2001)，「立體航照影像直線與圓弧輪廓建物半自動之三維模型重建」，國立中央大學土木工程研究所碩士論文。
茂榮編輯部(2011)，「最新建築技術規則」，臺北：茂榮書局。
郭志奕(2005)，「結合光達資料與大比例尺向量圖重建三維建物模型」，國立中央大學土木工程研究所碩士論文。
劉嘉銘(2005)，「光達點雲資料特徵萃取之研究」，國立成功大學測量及空間資訊學系碩士論文。
蔡函芳(2009)，「多重影像匹配於房屋邊緣線三維定位」，國立中央大學土木工程學系碩士論文。
賴彥中(2004)，「結合光達資料與數位空照影像重建三維建物模型」，國立中央大學土木工程研究所碩士論文。
Ackermann, F.(1999), “Airborne laser scanning—present status and future expectations,” ISPRS Journal of Photogrammetry and Remote Sensing, 2-3 (54) pp. 64~67.
Al-Durgham, M., Kwak, E., Habib, A.(2012), “Automatic Extraction of Building Outlines from LiDAR Using the Minimum Bounding Rectangle Algorithm,” Proceedings of Global Geospatial Conference, May.
Andraw, A.M.(1979), “Another efficient algorithm for convex hulls in two dimensions,” Information Processing Letters, 5 (9) pp.216~219.
Axelsson, P.(1999), “Processing of laser scanner data—algorithms and applications,” ISPRS Journal of Photogrammetry and Remote Sensing, 2-3 (54) pp. 138~147.
Brenner, C.(2005), “Building reconstruction from images and laser scanning,” International Journal of Applied Earth Observation and Geoinformation, 2-3 (6) pp. 187~198.
Dorninger, P. and Pfeifer, N.(2008), “A comprehensive automated 3D approach for building extraction, reconstruction, and regularization from airborne laser scanning point clouds,” Sensors, 8 (11) pp. 7323~7343.
Duda, R.O. and Hart, P.E.(1972), “Use of the hough transformation to detect lines and curves in pictures,” Communications of the ACM, 1 (15) pp.11~15.
Gröger, G., Kolbe, T. H., Czerwinski, A.(2006), Candidate OpenGIS® CityGML Implementation Specification: City Geography Markup Language(3rd ed.), Germany: the Special Interest Group 3D.
Gruen, A. and Wang, X.(1998), “CC-MODELER-a topology generator for 3-D city models,” ISPRS Journal of Photogrammetry and Remote Sensing, 5 (53) pp.286~295.
Hough, P.V.C.(1962), Method and means for recognizing complex patterns, United States: U.S. Atomic Energy Commission.
Hu, J., You, S. and Neumann, U.(2003), “Approaches to large-scale urban modeling,” Survey, 6 (23) pp. 62~69.
Huang, H., Brenner, C., Sester, M.(2013), “A generative statistical approach to automatic 3D building roof reconstruction from laser scanning data,” ISPRS Journal of Photogrammetry and Remote Sensing, (79) pp. 29~43.
Jarzabek-Rychard, M.(2012), “Reconstruction of building outlines in dense urban areas based on LiDAR data and address points,” International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, August, pp. 121~126.
Kada, M. and Wichmann, A.(2012), “Sub-surface growing and boundary generalization for 3d building reconstruction,” ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, August, pp. 233~238.
Kim, C. and Habib, A.(2009), “Object-Based Integration of Photogrammetric and LiDAR Data for Automated Generation of Complex Polyhedral Building Models,” Sensors, 9 (7) pp. 5679~5701.
Lafarge, F., Descombes, X., Zerubia, J., Pierrot-Deseilligny, M.(2008), “Automatic building extraction from DEMs using an object approach and application to the 3D-city modeling,” ISPRS Journal of Photogrammetry and Remote Sensing, (63) pp. 365~381.
Lee, Jeongho, Han, S., Byun,Y., and Kim,Y.(2011), “Extraction and regularization of various building boundaries with complex shapes utilizing distribution characteristics of airborne LiDAR points,” ETRI Journal, 4 (33) pp. 547~557.
Ma, R.(2005), “DEM generation and building detection from LiDAR data,” Photogrammetric Engineering & Remote Sensing, 7 (71) pp. 847~854.
Mannan, M. A. and Juergen, B.(2004), “Virtual environments in planning affairs,” International Archives of Photogrammetry and Remote Sensing, July, pp. 22~26.
Rau, J.Y. and Chen, L.C.(2003), “Robust Reconstruction of Building Models from Three-Dimensional Line Segments,” Photogrammetric Engineering & Remote Sensing Journal, 2 (69) pp. 181~188.
Rottensteiner, F. and Briese, C.(2003), “Automatic generation of building models from lidar data and the integration of aerial images,” International Archives of Photogrammetry and Remote Sensing, October.
Sampath, A., Shan, J.(2007), “Building boundary tracing and regularization from airborne LiDAR point clouds,” Photogrammetric Engineering & Remote Sensing Journal, 7 (73) pp. 805~812.
Shiode, N.(2001), “3D urban models: Recent developments in the digital modelling of urban environments in three-dimensions,” GeoJournal, 52 (3) pp. 263~269.
Suveg, I. and Vosselman, G.(2004), “Reconstruction of 3D building models from aerial images and maps,” ISPRS Journal of Photogrammetry and Remote Sensing, 3-4 (58) pp. 202~224.
Terrasolid(2010), TerraScan User’s guide, Taipei: Terrasolid, pp. 241-250.
Tseng, Y.H. and Wang, S.(2003), “Semiautomated Building Extraction Based on CSG Model-Image Fitting,” Photogrammetric Engineering & Remote Sensing, 2 (69) pp. 171~180.
Tu,C., Wyk,B.J.V., Djouani,K., Hamam,Y., and Du, S.(2011), “A super resolution algorithm to improve the Hough transform,” Image Analysis and Recognition Lecture Notes in Computer Science, (6753) pp. 80~89.
Vosselman, G. and Dijkman, S.(2001), “3D building model reconstruction from point clouds and ground plans,” International Archives of Photogrammetry and Remote Sensing, October, pp. 37~43.
Wang, M. and Tseng, Y.H.(2010), “Automatic segmentation of LiDAR data into coplanar point clusters using an octree-based split-and-merge algorithm,” Photogrammetric Engineering & Remote Sensing, 4 (76) pp. 407~420.
Wei, S.(2008), “Building Boundary Extraction Based on LIDAR Point Clouds Data,” International Archives of Photogrammetry and Remote Sensing, July, pp. 157~162.
Xiaa, Z. and Qing, Z.(2004), “Applications of 3d city models based spatial analysis to urban design,” International Archives of Photogrammetry and Remote Sensing, July, pp. 325~329.
Zhang, K., Yan, J. and Chen, S.C.(2006), “Automatic Construction of Building Footprints from Airborne LIDAR Data,” Geoscience and Remote Sensing, IEEE Transactions on, 9 (44) pp. 2523~2533.