サマリー
屋根特徴線は建物表面の重要な構造的特徴です。既存の屋根特徴線抽出法は、アルゴリズムの複雑さ、頑健性の低さ、屋根面分割精度への過度な依存などの問題があり、本稿では境界三角形検出と双方向重ね合わせ平行移動を組み合わせた建物屋根特徴線抽出方法を提案します。まず、デローニ三角分割を用いて屋根点群の三角格子モデルを構築し、各三角形の隣接情報を高速に格納・照会するために等深フォレスト（E-forest）データ構造を作成します。次に、E-forestが提供する三角形の隣接関係に基づき、三角格子モデル内の独立した辺から境界点を特定し、各三角形の中心点を法線方向に上下に平行移動させ、移動後の各点の球域内にある点断面の数を統計的に集計して棟線上の点を決定します。最後に、D-Pアルゴリズムと最小二乗法を用いて屋根境界線と棟線を生成し、多重特徴線交点の平面座標および局所的な原始点の標高を組み合わせて各特徴線端点を精密化し、屋根面特徴線の抽出を完了します。本研究はBuilding3DおよびVaihingenデータセットに含まれる12組の典型的な屋根点群でテストし、既存の特徴線抽出法と比較しました。実験結果より、本手法で抽出した特徴線の平均値は平均点間距離の約1倍であり、LSMは85%以上であることが示されました。全体的に安定性と信頼性が高く、頑健性に優れ、大多数の建物屋根特徴線抽出ニーズを満たすことが可能です。
キーワード
特徴線抽出;双方向重ね合わせ平行移動;三角格子モデル;D-Pアルゴリズム;DBSCANアルゴリズム
1はじめに
建物は都市建設の重要な構成部分である。近年、都市化の急速な発展に伴い、建築物の種類と数量は頻繁に革新され、これらの変化情報を収集し更新するには大量の人力、物力、財力が必要である（王竞雪 等，2012；Yang等，2017；Du等，2017；Salehi和Mohammadzadeh，2017）。この現状を改善するために、建築物情報を効率的に取得し、処理することは現在の研究の焦点となっており、建築物屋根特徴線抽出はこの研究の重要なステップの1つである（Dos等，2019; Fengなど、2019 ;王竞雪 等，2014）。機上レーザレーダLiDAR（Light Detection And Ranging）技術は高精度の地物3次元情報を直接取得することができるが、観測距離、物体反射率、気候環境などのデータ収集条件の違いにより、機上LiDARから取得される建物点雲には通常、点密度が均一でない場合がある（Yang等，2021）；また、点群データ自体は離散性があり、各点間には必要なトポロジー関係が不足している（文学东 等，2019）。そのため、機上LiDAR点群データに基づく建築物屋根特徴線の抽出作業は依然として大きな課題を抱えている。
屋根の特徴線の位置と属性の違いに基づいて、輪郭線、屋根線、ステップ線に分けることができます。ここで、輪郭線は建物の屋根面の境界線であり、通常は屋根面の外周に位置している。屋根稜線は2つの隣接する屋根面の交差線であり、通常は屋根面の内部に位置している。ステップ線は水平方向に隣接する屋根パッチであり、立面構造と交差して標高にジャンプが存在する一対の線分を形成する。
建築物の屋根輪郭線の抽出方法は主に3種類に分けられる：不規則三角格子TIN（Triangulated Irregular Network）に基づく方法、輪郭特徴に基づく方法、深さに基づく学習方法。ここで、TINベースの方法としては、Alpha shapes、凸包（convex−hull）など（惠振阳 等，2022）。Alpha shapesは現在最も一般的な輪郭線抽出方法であり、沈蔚等（2008）初めてAlpha shapesアルゴリズムを用いて無秩序な建築物点雲から屋根輪郭線抽出を行い、Alpha shapesアルゴリズムによる屋根輪郭線抽出の有効性を確認したが、単一のキー閾値ボール半径は密度不均一な点雲に適用することが困難であった。Alpha shapesアルゴリズムの適用性を高めるために、伍阳等（2021）2次元グリッドを分割し、境界グリッドの平滑性を計算することにより、密度が不均一な点群への適応性が明らかに向上する可変半径のAlpha shapesアルゴリズムを設計するが、境界グリッドの誤った分割は局所境界点の欠損を招く可能性がある。バンプアルゴリズムは、点群の境界（Lv等，2022）があるため、境界に凹み領域が存在する点群に対して、このアルゴリズムの輪郭線抽出能力は限られている。輪郭特徴に基づく抽出アルゴリズムは、近傍方向分布（Kong等，2023）、最小境界矩形（Minimum Boundary Rectangle，MBR）（Coiffier等，2021; Vanianなど、20と仮想メッシュ（Sun和Salvaggio，2013)などのアルゴリズムがあります。Kong等（2023）近傍方向分布を用いて建物の屋根の輪郭を抽出するアルゴリズムは、点雲の局所密度が異なり、形状が複雑な建物に適しており、パラメータを設定しやすいが、凹部領域の輪郭線を抽出することはできず、抽出効率は相対的に低い。Coiffier等（2021）MBRメソッドを使用して抽出された輪郭線は直角多角形であり、不規則な境界形状を表現することはできません。Sunなどが提案した仮想メッシュ方法は、点群上に仮想メッシュを構築することで建物の輪郭を抽出するが、この方法はメッシュの辺長の影響を受け、抽出された輪郭点が建物内部にシフトし、抽出された輪郭線が実際の建物の境界よりも小さくなる。ディープラーニングの進展に伴い、建物の輪郭情報を抽出するために使用できるネットワークフレームワークが相次いで提案されている。Bazazian和Parés（2021）提案されたEDC-NetフレームワークとZhang等（2020）提案した3-D-GMRGANフレームワークはいずれも大規模な点群から建築輪郭情報を効率的に抽出することができるが、抽出結果はトポロジー関係のない輪郭点群であり、これらの点群を後処理し、応用に便利な点鎖式輪郭抽出結果を得る必要がある。
稜線抽出には主に平面交差に基づく稜線抽出とグローバル特徴解析に基づく稜線抽出に分けられる。蒋星（2019）最小二乗フィッティングによる平面交差により稜線の位置を決定し、稜線の端点として架線と建物境界の交点を計算し、両端点間隔は稜線の長さであるが、この方法は多面片点の共通面性を考慮していないので、簡単な建物稜線の抽出にしか適用されない、吴华意等（2007）改良された3 D Hough変換及びクラスター解析を用いて屋根パッチが位置する平面のパラメータを取得し、クラスターを通じて異なるパッチに属する共平面点が複数の独立パッチに分割されることを確保し、比較的複雑な屋根の屋根線を抽出することができる、朱琴等（2018）ランダムサンプリング整合性RANSAC（Random Sample Consensus）アルゴリズムを用いて屋根面点雲を分割したが、稜線点面片が競合する現象があり、抽出された稜線に一定のずれや偏向があった。屋根面分割精度への屋根線抽出の依存性を回避するために、Cai等（2023）屋根面点の曲率特徴を分析することにより、山登り法に基づく屋根線抽出方法を提案し、この方法は屋根線上の点が比較的密であり、点雲内部に穴が存在できないことを要求する。陈华伟等（2019）曲率突然変異点の識別を通じて、さらに初期屋根線上の点集を得て、腐食アルゴリズムを用いて初期点集を細分化して、この過程は密度が不均一な点雲に対して、腐食後に特徴線点群が破断し、局所特徴線が欠損する可能性がある。Yu等（2024）3次元空間近傍点分布に基づく稜線抽出アルゴリズムを提案し、このアルゴリズムは各点近傍域内に一方向上の線形配列特徴が存在するかどうかを分析することにより、稜線上の点を選別する。このアルゴリズムは異なる屋根タイプの屋根点群に強い適応性を持っているが、稜線点の抽出効果は角度閾値に依存しすぎ、パラメータの変化に敏感である。
ステップ線の抽出には、既存の方法では、同じ立面に標高変化が存在する異なる平面を利用してステップ線を抽出することが多い。信頼性の高いステップラインを抽出するために、赵传（2020）高差の大きい隣接点鎖をフィッティングして3次元平面を生成することにより、点鎖の長さ、3次元平面法ベクトルとZ軸の角度が一定の閾値より大きい隣接点鎖を真のステップ線と見なす。高广（2014）距離分析に基づいて各屋根パッチの輪郭線から候補ステップ線を識別し、次にバッファを構築してグリッド化処理を行い、標高突然変異の隣接グリッドユニットを統合し、最小二乗法を用いてステップ線をフィッティングすることによりステップ線を生成するが、ステップ線における元の点に欠落した屋根面点雲が存在する場合、生成されたステップ線はしばしば破断することがある。
以上より、既存の建築物屋根特徴線抽出アルゴリズムに対して、一般的に抽出精度が限られ、ロバスト性が不足し、屋根面分割効果に高度に依存するなどの問題が存在し、本文は等深林の境界三角形検出と双方向重畳並進に基づく稜線点抽出アルゴリズムを提案し、屋根面分割を免れる屋根特徴線抽出を実現した。
2研究方法
本文が提案した連合境界三角形検出と双方向重畳並進の建築物屋根特徴線抽出方法は、データ前処理、特徴点抽出と特徴線生成の3段階に分けられる：（1）データ前処理段階：建築物屋根点雲の平均点間隔を計算し、Delaunay三角形切断を用いてTINを構築し、三角形隣接関係を検索しやすい等深森林（Equi-deep forest、E-forest）を構築する、（2）特徴点抽出段階：E-forestを通じてTIN中の各三角形の独立辺を検索し、トポロジ関係を含む境界点を抽出する、TIN中の各三角形の中心をその法ベクトル方向に沿って双方向に並進すると、交線における密度倍増の並進後点雲が得られ、交線における点を両面片並進方向ベクトル和の反対方向に並進すると、建物の屋根線上の点が得られる、（3）特徴線生成段階：境界線生成過程において、境界点間のトポロジ関係に基づいて、それを秩序正しく配列して閉じた多段線を生成し、D-Pアルゴリズムを用いて閉じた多段線を簡略化し、キー変曲点を抽出し、そしてこれら変曲点生成簡略化後の屋根境界線を接続する、稜線生成過程において：双方向重畳並進により各稜線の点クラスタを得た後、最小二乗法を用いて各グループの稜線点クラスタをフィッティングし、稜線が位置する3次元直線のパラメータを得て、各グループの稜線点をそれぞれの3次元フィッティング直線に投影し、各フィッティング直線上で最も離れた2つの投影点を稜線端点とし、最後に抽出された境界線と屋根線上の点を精密化し、建物の屋根特徴線の抽出を完了した。本文は機械搭載LiDAR建築物の屋根点雲の特徴線抽出プロセスに基づいてFig. 1を参照してください。
本文が提案した連合境界三角形検出と双方向重畳並進の建築物屋根特徴線抽出方法は、データ前処理、特徴点抽出と特徴線生成の3段階に分けられる：（1）データ前処理段階：建築物屋根点雲の平均点間隔を計算し、Delaunay三角形切断を用いてTINを構築し、三角形隣接関係を検索しやすい等深森E-forest（Equi-deep forest）を構築する、（2）特徴点抽出段階：E-forestを通じてTIN中の各三角形の独立辺を検索し、トポロジ関係を含む境界点を抽出する、TIN中の各三角形の中心をその法ベクトル方向に沿って双方向に並進すると、交線における密度倍増の並進後点雲が得られ、交線における点を両面片並進方向ベクトル和の反対方向に並進すると、建物の屋根線上の点が得られる、（3）特徴線生成段階：境界線生成過程において、境界点間のトポロジ関係に基づいて、それを秩序正しく配列して閉じた多段線を生成し、D-Pアルゴリズムを用いて閉じた多段線を簡略化し、キー変曲点を抽出し、そしてこれら変曲点生成簡略化後の屋根境界線を接続する、稜線生成過程において：双方向重畳並進により各稜線の点クラスタを得た後、最小二乗法を用いて各グループの稜線点クラスタをフィッティングし、稜線が位置する3次元直線のパラメータを得て、各グループの稜線点をそれぞれの3次元フィッティング直線に投影し、各フィッティング直線上で最も離れた2つの投影点を稜線端点とし、最後に抽出された境界線と屋根線上の点を精密化し、建物の屋根特徴線の抽出を完了した。本文は機械搭載LiDAR建築物の屋根点雲の特徴線抽出プロセスに基づいてFig. 1を参照してください。
2.1データ前処理
飛行高度、設備型番、気候条件などの客観的な要素の影響を受けて、異なる機上LiDAR点雲は通常大きな密度差を持っている。アルゴリズムが異なる密度点群に適応性を持つことを確保するために、本文は屋根面点雲中の各点から最近接点までの距離の平均値を点雲平均点間隔dとして、後続のTIN構築、特徴点抽出、特徴線精度分析などの仕事に使用する。
機上LiDAR点群データがトポロジー関係に欠けている問題に対して、本文はDelaunay三角断面アルゴリズムを用いて建築物屋根面点雲の三角格子モデルを構築し、その中の各三角形はいずれも最小角、空円などの性質を最大化し、比較的に高い安定性を持っている。窪み、ステップ構造などの領域三角形の生成を制限するために、本文ではTINを構築する際に、最大辺長Lがn倍の平均点間隔の大きさ、すなわちL=n×dを設定する。
点群データに基づいて構築された建物屋根三角格子モデルは、複雑な屋根表面を正確に表現することができますが、そのデータ構造とトポロジの関係が複雑で、クエリ効率が低下しています（张雨禾 等，2015）。クエリ効率を向上させるために、KD-tree（杨丽娟 等，2023）、R-tree（龚俊 等，2011）、Octree（张蕊等，2018）などを使用して、局所領域内の三角形探索と位置決めの効率を高めることができます。これらのデータ構造は検索効率を向上させますが、構築とメンテナンスのコストが高くなります。この問題に対して、本文は三角形の隣接関係を検索するのに便利な等深森林E-forest（Equi-deep forest）を創立して、各三角形を1つの独立したルートノードとして、いくつかの深さが3の秩序樹を創立して、E-forestの中で各樹のノードが表す意味はFig. 2を参照してください。
隣接する三角形間の異なる隣接関係を区別しやすくするために、本文は2つの共通頂点を持つ隣接三角形を共辺三角形、1つの共通頂点のみを含む隣接三角形性を共点三角形と記す。E−forestにおける第2層分岐ノード度の和は隣接三角形の個数に等しく、ここで左サブノードの度は現在の三角形近傍域内の共辺三角形の数を表し、右サブノードの度は、現在の三角形近傍領域内の共点三角形の数を表します。如Fig. 2中の三角形T 6に示すように、合計12個の三角形が隣接しており、その中には3個の共辺三角形と9個の共点三角形が含まれている、一方、境界上に位置する三角形T 8は、その近傍に2つの共通辺の三角形しかないため、その隣接関係木の左子接点度は2である。
2.2特徴点抽出
本節では、建物の屋根点群に基づく特徴点抽出方法を提案し、まずE-forestの左の子結点度＜3の境界三角形を見つけ、それから境界三角形のすべての頂点がその共辺の三角形に現れる回数を統計し、繰り返し出現回数＜2の頂点を境界点と記す、屋根線上の特徴点抽出に対して、TIN中の各三角形中心をその法ベクトル方向に沿ってそれぞれ上方向と下方向に直線移動すると、交線における密度倍増の直線移動後点雲が得られ、交線における点を両面片直線移動方向ベクトル和の反対方向に直線移動すると、建物の屋根線上の点が得られる。最終的に建物の屋根面特徴点の抽出を完了します。
2.2.1独立エッジ検出に基づく境界点抽出
ステップ構造が存在する建物の屋根の場合、三角格子モデルを構築する際に使用される最長エッジ制約により、建物の屋根の三角格子モデルが複数のグループの独立したTINに分割され、TINの境界に輪郭線とステップ線の点が同時に含まれるようになる可能性があります。
建物屋上三角格子モデル詳細はFig. 3。ここで、各グループのTINの境界には部分輪郭点とステップ点が含まれており、本文では三角メッシュモデル中の輪郭点とステップ点を総称して各グループのTINの境界点と呼び、2つの隣接境界点が連なって構成された辺を独立辺と記す。境界点が位置する三角形には1-2本の独立した辺が存在し、境界点が位置する三角形の共辺三角形の数＜3、すなわちE-forestにおける境界三角形が対応する木の左子結点度＜3をもたらすため、本文は左子結点度＜3の木が対応する三角形を境界三角形と見なし、境界三角形と各共辺三角形頂点の共通回数に基づいて境界点を決定し、具体的な実現方法は以下の通りである：
（1）E-forest中の各木を遍歴し、左子結点度＜3の木を境界木とし、各境界木内に境界三角形を含む、
（2）ランダムに境界木を選択する、統計対応する三角形の頂点がその共辺三角形に繰り返し現れる回数、繰り返し出現回数＜2の頂点を境界点と記す、
（3）手順（2）を繰り返し、すべての境界ツリーを巡回し、重複した境界点を削除して、三角メッシュモデルの境界点セットを得る。
（4）共通点境界三角形間の独立辺の連通性、及び独立辺上の2つの独立点の連結性に基づいて境界点間の順序を決定し、いくつかの境界点からなる首尾が閉じた多段線を得る。
2.2.2双方向重畳並進に基づく稜線点抽出
建物の屋根線は2つの隣接する面の交差線であり、屋根線が2つの隣接する面の位置と比較する高低によって、それを凸屋根線と凹屋根線に分けることができ、詳しくはFig. 4を選択して設定できます。Fig. 4凸稜線にある2つの隣接する屋根パッチをその法ベクトル方向に沿って下に移動することができ、凸稜線の近くに交差する直線を得ることができる。由Fig. 4凹凸稜線にある2つの隣接する屋根パッチをその法ベクトル方向に沿って上に移動することにより、凹凸稜線付近に交差する直線を得ることができる。屋根点雲をパッチ並進方向等距離に沿って並進すると、稜線付近の点も交線に落下し、このとき交線上並進点の密度は元の屋根点雲の密度に比べて倍増し、交線上の点を両面パッチ並進方向ベクトル和の反対方向に並進すると、建物の稜線上の点が得られる。
本論文では、屋根三角メッシュモデルにおける三角形ごとの法ベクトルを移動方向として用い、移動距離として、ここで、kは平均点間隔dの倍数であり、各三角形の中心点をそれぞれそれぞれの法ベクトル方向に沿って上、下に移動し、双方向移動後の点群、例えばFig. 5を参照してください。理想的には、各直線移動点間の距離は等しく、屋根平面には1平方メートルあたり個の点、並進点を球心とし、半径を確立するダイアログが表示されます。各球形領域内には無数の円形の断面が存在するが、個別の断面には連続的に均一に分布する並進点が存在するのみであり、本文ではこの断面を有点断面と呼び、交線上に位置する並進点を交線点と呼ぶ。屋根パッチ上に位置する移動点。球面内にはわずかな断面が1つしか存在しません。たとえば、Fig. 5中赤色断面で示す、交点の球領域内には2つの点断面があります。たとえば、Fig. 5に青色の断面を表示します。そこで本文では、球面内の点数＞1.5nの並進点を交線上の点と見なし、ここでnの計算方式は式（1）を参照してください。
式中、nは球域内の単一の有点断面上の点の数であり、rは球域半径であり、dは建築物の屋根点雲の平均点間隔である。
点群中の各点間距離が異なることを考慮すると、平均点間隔は各点と最も近い点との距離の平均値であるため、=d半径のために構築された近傍領域には、球状中心点以外の点は通常存在しない、一方、密度が不均一な点雲については、＝2d統計有点パッチ数の安定性が劣るため、本文はさらに検出半径を拡大し、＝3d。また、交点付近の交線点は同じ複数の交線に属し、例えばFig. 5黒いボックス内の領域に示されているため、交点付近の交線点の帰属関係が確定しにくい。異なる交線上の点の逆方向の直線移動方向を決定するために、本文はまず交点近傍内の交線点を除去してから、残りの交線点を複数のグループの独立して異なる交線を代表する点のセットにクラスター化して、各グループの交線点クラスタの逆方向の直線移動方向を決定する。
交点は少なくとも3つの並進後の屋根パッチで構成されているため、交点を球心として構築された球域内には少なくとも3つの有点断面が存在するため、本文は球域内の点数＞3＜i＞nの並進点を初期交点と見なし、DBSCANアルゴリズムを用いて初期交点集合をクラスタ化し、初期交点クラスタを取得し、各初期点クラスタ群中の各点座標の平均値を交点とし、交線からの距離がの交線点を使用して、再びDBSCANアルゴリズムを使用して残りの交線点をクラスタリングし、いくつかのグループがそれぞれ異なる交線上に位置する交線点クラスタを得て、その時各グループの交線点クラスタの中の点はすべて2つの隣接パッチの並進点である。建物の屋根に存在する可能性のある表面歪み、機上LiDARデータ収集誤差などの要素の影響により、同じ屋根のパッチ上の異なる三角形法ベクトル間に一定の偏差が存在するが、この偏差は異なるパッチ上の三角形法ベクトル間の偏差よりはるかに小さい。本文は2つの並進点法ベクトル間の偏向角を計算することによって、交線点クラスタ中の偏向角がTβ未満の並進点を同じ集合に加え、個別ノイズの影響を防止するために、並進点数が最も大きい2つの集合を2つの異なるパッチ上の点とし、2つの集合中の並進点法ベクトルの平均値を現在の交線点クラスタの2つの並進方向とする。一般的な屋根隣接パッチ法ベクトル間の角度を解析することにより、隣接屋根パッチ法ベクトル間の角度は通常＞10°（王竞雪 等 ，2023）に設定されているので、本明細書では移動点パケットの角度閾値としてTβ＝10°をとる。
Fig. 6背面屋根面点群を直線移動するための側面図。その中で、交差点クラスタ内の1つの直線移動点のために、現在の交差点クラスタの2つの直線移動方向はそれぞれ和，θは3次元空間内であると角の半分。点を両面シート並進方向に沿うベクトルの和の反対方向Lを直線移動すると、稜線上の点が得られるを選択し、、。各グループの交線点クラスタをそれぞれの逆並進方向に並進すると、独立した稜線点クラスタが複数セット得られる。
2.3ブレークライン生成
本文はそれぞれダグラス・プランクD-P（Douglas-Peuker）と最小二乗フィッティングアルゴリズムを用いて建物の屋根面の境界線と屋根線を生成した。抽出された境界線に対して、TIN上でランダムに境界点を開始境界点として選択し、三角形間の共通点隣接関係を結合して残りの境界点を順次接続し、閉じた多段線を生成する、D-Pアルゴリズムにより簡略化され、境界線のキーカーブが得られ、多段線上の各点の順に閉じた屋根境界線が生成される。稜線抽出は最小二乗法を用いて各グループの稜線点クラスタをフィッティングし、稜線が位置する3次元直線のパラメータを得て、そして各グループの稜線点をそれぞれの3次元フィッティング直線に投影して、その中で最も遠い2点を稜線端点として選択した、交差する特徴線のスクリーニングを二重閾値で拘束し、交差する特徴線の交点をその新しい特徴線の端点とし、屋根線の抽出を完了する。
2.3.1 D-Pアルゴリズムに基づく境界線生成
独立したエッジ検出により抽出された閉じた多段線上には大量の離散的な境界点が存在し、屋根境界のパラメータ化表現に不利であるため、本文は並進と回転不変性を有するD-Pアルゴリズムを用いてそれを簡略化し、その中のキー変曲点を取得し、順次接続して屋根境界線を生成する。
従来のD-Pアルゴリズムでは、閉じたポリラインのキー変曲点をフィルタリングする際に使用されていたため、始点終点の選択にはランダム性があり、デフォルトの始点終点はキー変曲点であり、フィルタされたキー変曲点には冗長性があることが多い。このため、本文では隣接する独立エッジの角度拘束を新たに追加し、非コーナーの独立エッジの端点を始点の端点として選択し、キーのコーナーの必要性を確保します。以Fig. 7のグレーの初期境界線を例に挙げます。具体的な実装手順は次のとおりです。
（1）初期境界線でランダムに独立したエッジを選択し、3次元空間内の2つの独立したエッジと接続された2つの独立したエッジの角度をそれぞれ計算すると、、いずれも150°を超えると、現在の独立エッジの2つの境界点を始点とし、逆に、独立したエッジが条件を満たすまで、別の独立したエッジを選択します。この条件を最初に満たす独立辺が位置する直線を先頭基準線と記す。如Fig. 7に示すように、点1と点12を始点とする青色実線分を先頭とする基準線。
（2）3次元空間で基準線の両端点間の境界点ごとに基準線までの垂直距離を計算し、その中の最大の垂直距離≦を選択すると、現在の基準線が直接削除されます。それ以外の場合は、対応する点をキー変曲点として記録します。参考（さんこう）洪绍轩等（2020）のしきい値選択、本文令。データムライン上の2つの境界点をキーカーブにそれぞれ接続して2つの新しいデータムラインを作成し、元のデータムラインを削除します。以Fig. 7中頭段の基準線を例に、点7は基準線から最も遠い境界点であり、垂直距離がとなりますので、点1点7、点7点12が位置する直線をそれぞれ基準線とし、先頭基準線を削除します。
（3）他の基準線を選択して、現在の初期境界線に基準線がなくなるまで手順2を繰り返します。
（4）最初と最後の両端点を削除し、初期境界線上の各点間の順序に基づいて残りのキーの変曲点を順次接続し、簡略化された境界線を生成する。
2.3.2最小二乗フィッティングに基づく屋根線生成
双方向重畳並進により各稜線の特徴点クラスタを得た後、最小二乗アルゴリズムを用いて各グループの稜線点クラスタをフィッティングし、稜線が位置する3次元直線のパラメータを生成し、各グループの稜線点からそれぞれの3次元フィッティング直線上の最も遠い並進点を稜線の端点とした。以Fig. 8で示した稜線点クラスタを例に、この稜線点クラスタを最小二乗法でフィットさせた3次元直線のために、稜線点クラスタの各点を垂直方向に投影するポイントのセットを得るただし、jは稜線点クラスタの中点の数である。計算の2点間の3 D空間内の距離のうち、最も遠い2点を、稜線の端点と見なす。
2.3.3特徴線終点の精密化
本文は異なる戦略を用いて段階的に建物の屋根境界線と屋根線を抽出し、両者の間の接続関係を考慮せず、さらに抽出された境界線と屋根線は互いに独立し、実際の建物の屋根特徴線と一致しないため、各特徴線の終点をさらに精密化する必要がある。
屋根の各交差特徴線の間に共通の端点が存在するため、交差する特徴線の間には比較的に近い同名の端点を持つべきで、近似平行の異なる特徴線の交点が遠すぎることを防止するために、本文の連合距離閾値Fmと角度閾値Fnは交差特徴線の選別を共同で拘束し、交差特徴線の交点をその新しい端点とし、具体的なステップは以下の通りである：
（1）在屋顶特征线中随机选取两条特征线L1、L2，计算L1与L2端点之间的最小距离Dmin，和L1与L2在二维水平面方向上的夹角Ang，Dmin小于Fm且Ang小于Fn（本文将夹角＞170°的两条相交特征线视为同一方向上的特征线，因此，令Fn＝170°），则将L1、L2视为两条存在交点的相邻特征线；
（2）L1とL2を水平面に投影し、水平面内の交点Hを計算し、HのX軸とY軸座標と元の端点のZ軸座標をL1とL2>近交点端の端点座標、
（3）ステップ1-2を繰り返し、すべての特徴線の組み合わせを遍歴し、特徴線の端点の予備補正を完了する。
実際の屋根には3つ以上の特徴線が交差する場合があるため、初期補正では2つの2つの補正プロセスが交差点に同じ名前の複数の端点を生成する可能性があります。Fig. 9を参照してください。したがって、同じ名前の複数の端点を正規化するためにマージする必要があります。本文は相互距離がFm未満の端点を同名端点と見なし、同名端点X軸とY軸座標の平均値を複数の特徴線が交差する唯一の端点として採用する。同名の端点座標を正規化した後、同名の端点のX軸とY軸座標及びZ軸座標の平均値を円心とし、半径がFmの球域を確立し、元の同名の端点の高距離を球域内の元の建築物屋根点の高距離平均値で置換し、すべての特徴線端点の精密化を完成する。
適切な特徴線端点微細化閾値を選択するために、本文ではそれぞれ異なる大きさのFm対を用いてFig. 9でブレークラインの端点の初期最適化結果を処理します。Fig. 10を参照してください。異なるFmの値を分析することにより、Fm3dの場合、交差する特徴線間の同名の端点の最小距離が閾値Fm未満であるため、一部の特徴線の端点で破断が発生し、例えばFig. 10ブラックボックス内の領域を示します。Fm＝4dの場合、特徴線の端点はすべて交差して最適化が完了するので、本文は特徴線の端点の微細化閾値としてFm＝4dを選択した。
3実験結果と精度分析
3.1実験データ
本文で提案した方法の有効性を検証するために、本文は12組の異なる屋根構造を持つ建築物点雲を試験データセットとして選択し、各組の建築物点雲を順次B 1-B 12と記す。ここで、B 1−B 8はBuilding 3 Dデータセット（Wang等，2023）、その属するBuilding 3 Dデータセット（ISPRS、2022）はより高い点密度を持ち、境界点は比較的完全であり、選択されたB 1-B 8はBuilding 3 Dデータセットの様々な一般的な建築物タイプをカバーし、B 9-B 12は、国際写真測量・リモートセンシング学会ISPRS（International Society for Photogrammetry and Remote Sensing）が提供するVaihingenデータセットから来ており、Building 3 Dデータセットに比べてVaihingenデータセットの点密度が均一ではなく、各セットのデータの具体的な状況とデータセットに付属するワイヤフレームモデルは、Fig. 11を参照してください。
3.2異なるパラメータ<i>k</i>が稜線点抽出結果に与える影響
建築物の屋根線点の抽出は建築物の屋根の構造特徴を初歩的に確定することができ、後続の特徴線生成の基礎である。双方向重畳並進法に基づいて稜線点を抽出する場合、三角形の中心点の並進距離としてk倍の平均点間隔を採用する。異なるパラメータkが稜線点抽出結果に与える影響を比較するために、本文は3組の代表的な屋根面点雲B 7、B 8、B 9を実験データとして選択し、異なるk値の下の稜線点抽出結果は以下の通りであるFig. 12を参照してください。
Fig. 12異なるk値における稜線点の抽出結果。分かるように：当時、並進距離が短いため、異なるパッチ上の並進点の交差現象は明らかではなく、抽出された稜線点はまばらで、各稜線を完全にカバーすることができず、黒い矩形領域内の稜線点クラスタには明らかな欠損が存在した（Fig. 12および（b））、当の場合、黒色矩形領域内の稜線点の密度が顕著に増加し、このとき得られた稜線点は屋根内部特徴線の構造情報を完全に記録することができる（Fig. 12と（d）、kの値がさらに大きくなるにつれて、稜線点クラスタは徐々に広くなってきたが、特徴線発現能力は明らかに改善されておらず、抽出された特徴線点クラスタは短くなっている（Fig. 12）。以上より、屋根線点の正確な抽出と後続特徴線生成の効率を考慮して、本文はk＝4.0を確定として選択するサイズのパラメータ。
3.3建築物屋根特徴線抽出結果と分析
本文のアルゴリズムによる特徴線抽出の利点を証明するために、本文はそれぞれ鲍娣（2017）、Yu等（2024）の特徴線抽出方法を比較し、古典的な精度評価指標を通じて、それぞれ3種類のアルゴリズムの性能に対して定性と定量分析を行い、それによって本文のアルゴリズムが既存の特徴線抽出方法と比較する優位性を正確に評価し、潜在的な改善空間を探す。
3.3.1特徴線抽出結果の定性分析
異なるアルゴリズムペアを使用Fig. 11に示す12組の建築物屋根点群データを特徴線抽出し、抽出結果はFig. 13を参照してください。参照特徴線の正確性を確保するために、本文ではデータセットに提供される屋根フレームを参照特徴線として採用する。
B 4、B 12中の黒い矢印が指す屋根面のように屋根構造が比較的に複雑な建物に対して、凸稜線と凹稜線を同時に含み、本文のアルゴリズムは双方向並進の方式を採用してそれぞれ凸稜線と凹稜線を抽出し、各稜線線上に比較的稠密な稜線点を抽出することができ、異なる稜線の交点での相互干渉を減少させ、アルゴリズムが複雑な屋根に対してより高い包容性を持つことを確保する。ために鲍娣（2017）採用された屋根線抽出方法は屋根面分割結果に依存しすぎ、そして各パッチ間のトポロジ関係を判断して隣接パッチ交線を確定する必要があり、屋根面分割結果またはトポロジ関係マッチングに誤りが発生した場合、屋根線に偏向、欠損、誤りなどの奇妙な抽出結果を直接引き起こす。B 2のパッチ分割精度が低いと、黒枠内領域の特徴線の端点に偏向が生じ、およびB 5を構成する2つの屋根パッチ間の偏向角度が小さすぎて、屋根面が分割されたときに同じパッチとみなされ、黒枠内の屋根線が欠落してしまうことがあります。
さらに、鲍娣（2017）異なる種類の特徴線の端点を結合する場合、B 6、B 8の青色枠内領域に示すように、点群の各点の標高に一定の誤差があるため、内部特徴線と外部特徴線の共通端点を直接3次元空間内で決定する。ステップライン構造が存在する屋根については、Yu等（2024）2次元水平方向にグリッドを分割し、3次元空間内のステップ線上点の線形分布特徴を解析できず、B 3、B 11の紫色矢印で示す領域のような抽出結果にステップ線上点が欠落している。しかし、建物B 10のような水平方向に離れたステップ構造については、Yu等（2024）これを2つの独立した建物の屋根として扱うことで、建物の屋根にあるすべての特徴線を効率的に抽出することができます。
本文は2 D平面内で終点を結合し、3 D空間内で終点標高を回復する方法を採用し、局所点雲標高の変動が特徴線抽出結果に与える影響を抑制し、抽出した特徴線が真実の屋根面に近いことを確保する。樹木や付属建物などの物体に遮られ、建物の屋根点雲には通常、局所的な欠落やまばらなものが存在する。境界点に対して明らかに欠落している領域、例えばFig. 13に紫色のボックス内の領域を示す、鲍娣（2017）採用されたAlpha shapesアルゴリズム、Yu等（2024）採用した近傍点線形方向解析アルゴリズム、及び本文で採用した独立辺検出アルゴリズムはいずれも既存の境界点に対してしか解析できず、点集境界が建築物の真の境界であるかどうかを考慮できなかったため、3種類のアルゴリズムは現在の領域で抽出された特徴線に対して一定の偏差を残している。境界点が疎な領域については、B 7の赤色のボックス領域に示すように、Yu等（2024）グリッドを分割する際に、点数の少ないグリッドをノイズ除去とみなし、抽出した境界が偏向し、さらに特徴線抽出結果が実際と一致しないことになる。本文のアルゴリズムによる境界点の抽出は境界三角形中の独立辺に依存し、密度疎領域の独立辺の性質は稠密領域と同じであるため、境界点疎領域に対しては、比較的完全な境界線を抽出することができる。
全体的に見ると、本文の方法は様々な屋根構造建築物を含む特徴線を抽出することができ、抽出された特徴線は高い完全性を持ち、元の点雲と高い適合度を持つ。
3.3.2特徴線抽出結果の定量分析
建物屋上特徴線の抽出結果を定量的に評価するために、抽出した特徴線と参照特徴線を比較する。Building 3 DデータセットとVaihingenデータセットの参照特性線は、屋根のワイヤフレームによって提供されます。たとえば、Fig. 11に表示されます。本文はそれぞれ端点座標偏差平均値Meanと線分総合類似度LSM（Line Similarity Measure）（崔巍 等，2003）2つの評価指標により抽出結果を定量的に分析した。前者は抽出されたすべての特徴線終点座標と対応する参照特徴線終点座標の偏差平均値Meanであり、計算式は以下の通りである：
式中、とそれぞれ第個の参照特徴線端点と抽出特徴線端点、aとbはそれぞれP抽出特徴線端点と参照特徴線端点を表し、3次元空間内の2点のユークリッド距離のために、建物の屋根の特徴点の数です。
後者は線分の中点、長さと角度の3方面を兼ねて類似度LSMを総合して抽出特徴線と参照特徴線の間の類似度を反応させ、計算式は以下の通りである：
式中、PSM、LnSM、OSMはそれぞれ中点位置類似度PSM（Point Similarity）、長さ類似度LnSM（Length Similarity）、角度類似度ASM（Angle Similarity）を表し、その計算式はそれぞれ式（4）—（6)を参照してください。 それぞれPSM、LnSM、OSMの重み値であり、本文ではそれぞれ2、1、2の値をとる。
式中、dは屋根面点雲の平均点ピッチであり、li、lj中点の水平ピッチが（）（うちは適応値）である場合、2つの線分は無関係であるとみなされる。
式では、2つの線分の長さの差が小さいほど、2つの線分は長さ的に近く、2つの線分が同じ内部特徴線を表す可能性が高くなります。
式中、偏向角度のしきい値であり、2つの線分方向ベクトル間の角度がを選択すると、2つの線分セグメントは関係ないとみなされます。
Fig. 13における各グループのデータ特徴線抽出結果のMean、LSM値はそれぞれTable 1と2に示す。分析により、一般的に本文の方法で抽出された特徴線の端点の精度はより高く、全体と参照特徴線はより類似していることが分かった。結合Table 1中の各グループのデータの平均点間隔を見ると、本文のアルゴリズムで抽出された特徴線の端点は基準特徴線の端点と比べて、最大偏差は平均点間隔の2倍、平均偏差は平均点間隔の1倍である。B 4やB 7などの複雑な建物では、すべてのアルゴリズムで抽出された特徴線と参照特徴線との類似度は低いものの、本アルゴリズムはLSMを85%以上維持することができる。
Table 1 The mean values of the feature line extraction results of different algorithms
| 数据编号 | 各组数据的平均点间距/m | 平均值/m |
|---|
| 鲍娣（2017） | Yu等（2024） | 本文算法 |
|---|
| B1 | 0.1480 | 0.1612 | 0.1143 | 0.0798 |
| B2 | 0.1614 | 0.4571 | 0.3417 | 0.3205 |
| B3 | 0.1343 | 0.1181 | 0.4274 | 0.0296 |
| B4 | 0.1360 | 0.3223 | 0.2132 | 0.1862 |
| B5 | 0.1287 | 0.2798 | 0.1916 | 0.1642 |
| B6 | 0.1380 | 0.4260 | 0.2844 | 0.2732 |
| B7 | 0.1169 | 0.3454 | 0.3002 | 0.2618 |
| B8 | 0.1060 | 0.0833 | 0.0507 | 0.0364 |
| B9 | 0.2364 | 0.1117 | 0.0606 | 0.0454 |
| B10 | 0.2279 | 0.1630 | 0.2329 | 0.1071 |
| B11 | 0.4397 | 0.2784 | 0.2576 | 0.1384 |
| B12 | 0.2178 | 0.3415 | 0.2300 | 0.1232 |
Table 2 The LSM values of the feature line extraction results of different algorithms
| 数据编号 | 相似度/% |
|---|
| 鲍娣（2017） | Yu等（2024） | 本文算法 |
|---|
| B1 | 86.22 | 87.50 | 92.52 |
| B2 | 71.82 | 81.75 | 87.45 |
| B3 | 90.94 | 68.83 | 97.12 |
| B4 | 74.88 | 82.62 | 86.27 |
| B5 | 76.13 | 79.63 | 92.65 |
| B6 | 77.45 | 85.11 | 92.51 |
| B7 | 75.30 | 81.40 | 85.08 |
| B8 | 92.99 | 96.06 | 98.30 |
| B9 | 94.41 | 96.82 | 98.45 |
| B10 | 88.16 | 91.90 | 95.07 |
| B11 | 84.70 | 74.46 | 93.35 |
| B12 | 86.97 | 90.69 | 94.63 |
ために鲍娣（2017）屋根の輪郭線（B 7、B 11）を正確に識別できなかったり、パッチ分割中にパッチ間のトポロジー関係を正確に構築できなかったり（B 5）、特徴線の抽出結果が実際の建物の屋根の特徴線と大きく異なり、特徴線の類似度が本文のアルゴリズムより明らかに低かった。に比べて鲍娣（2017），Yu等（2024）特徴線抽出の精度と類似度は一般的に高い鲍娣（2017）が、本文で提案する方法よりも低い。本文で提案したアルゴリズムが抽出した特徴線は実際の建物の屋根特徴線とほぼ同じ位置で、類似度が明らかに高く、特に点雲データの品質が高い場合、B 6、B 8、B 9のように、本文のアルゴリズムが生成した特徴線は品質と類似度の上で比較アルゴリズムより優れている。上記の建築物屋根特徴線生成結果の定量と定性の分析により、本文で提案した方法は建築物屋根特徴線を抽出するのに高い精度があることが分かった。また、本文の方法は特徴線を抽出する際に屋根パッチを分割しないようにし、非稜線にノイズを含む屋根点雲に対して強い耐干渉能力を持ち、ほとんどの建物の屋根特徴線抽出需要を満たすことができる。
3.4 E-forest構築とストレージ性能分析
E-forestデータ構造の効率性を検証するために、本文はそれぞれ異なる頂点数を含む三角網を実験データとして採用し、半辺データ構造HEDS（Half-Edge Data Structure）と構築時間と記憶占有空間の両面で比較し、実験結果はTable 3を参照してください。異なる頂点数では、E-forestデータ構造の構築に必要な時間はHEDSの43.17%、記憶に必要なメモリ空間はHEDSの31.52%であることがわかります。
Table 3 The construction time and space occupancy of data structures under different numbers of vertices in triangular meshes
| 顶点数量/个 | 构建时间/s | 占用空间/Mb |
|---|
| HEDS | E-forest | HEDS | E-forest |
|---|
| 5000 | 0.048 | 0.031 | 4.72 | 1.35 |
| 10000 | 0.127 | 0.080 | 9.77 | 3.00 |
| 15000 | 0.210 | 0.096 | 14.76 | 4.63 |
| 20000 | 0.337 | 0.159 | 19.89 | 6.30 |
| 25000 | 0.479 | 0.196 | 25.12 | 8.00 |
| 30000 | 0.689 | 0.254 | 30.24 | 9.66 |
HEDSと比較して、本文で提案したE-forestデータ構造は三角形頂点座標、共辺及び共点三角形インデックスを直接記憶し、それにより点、半辺、三角形間の指向関係を維持するための大量の指針情報を節約した。また、三角形間の隣接関係のクエリについては、E-forestデータ構造は、多段ポインタジャンプを介する必要がなく、隣接三角形のインデックスを直接呼び出すことができる。そのため、E-forestデータ構造を用いて三角形網における各三角形間の隣接関係を管理することで、アルゴリズムの運行効率を著しく向上させることができる。
4結節論
既存の屋根特徴線抽出方法にはアルゴリズムが複雑で、ロバスト性が悪い、屋根面分割精度に依存しすぎるなどの問題があり、本文は境界三角形検出と双方向重畳並進を結合する建築物屋根特徴線抽出方法を提案した。Building 3 DデータセットとVaihingenデータセットを使用して、異なる複雑さを持つ建物の屋根点群検証を選択します。主な結論は以下の通りである：（1）本文はE-forestストレージ三角格子モデルにおける各三角間の隣接関係を構築することにより、三角近傍関係の検索と呼び出しを便利にする、（2）双方向重畳並進により屋根面点雲から屋根面分割精度が特徴線抽出結果に干渉しないように、屋根面点を直接取得する、（3）独立辺検出を用いて屋根面の初期境界線を確定し、さらに角度判定条件を追加し、改善後のD-Pアルゴリズムが安定的にキー変曲点を獲得できることを確保することができる、（4）MeanとLSM定量分析を用いて抽出した特徴線精度から分かるように、本文のアルゴリズムで抽出した特徴線の端点の最大偏差は2倍の平均点間隔、平均偏差は2倍の平均点間隔であり、抽出した特徴線と参照特徴線の間の全体的な類似度は85%以上である。
本文で提案した方法は、ほとんどの機械搭載LiDAR建築物の屋根点雲の特徴線抽出ニーズを満たすことができるが、まだ一部の限界がある。一方、稜線のフィッティング精度は点群形状の影響を受け、稜線の点群が短い場合、フィッティングによって生成される稜線の角度は偏向しやすく、稜線で密度が薄すぎる屋根点雲に対して、抽出された稜線に破断が存在する可能性がある、一方、元の建物点雲境界には一定の欠落があるため、本アルゴリズムで抽出された輪郭線と真の境界との間にはずれがある。後続の作業では、マルチソースデータ補完境界に欠落した点群を導入したり、輪郭線を修正したりして、より精度の高い建物屋根の特徴線を取得することが考えられます。
