(57)【要約】  点群抽出部（１２）は、点群データから折れ線の作画対象となる点群を抽出する。頂点生成部（１３）は、点群に局所領域を定め、局所領域の点群の分布状態を示す点を代表点として求めると共に、求めた代表点を基準として新たな局所領域を定め、新たな局所領域の点群の分布状態を示す点を新たな代表点として求める。折れ線出力部（１４）は、全ての代表点を順に接続して折れ線を作画する。
2019111323.tif 000002
【特許請求の範囲】
【請求項１】
折れ線を作画する対象となる点群を抽出する点群抽出部と、
前記対象となる点群に局所領域を定め、当該局所領域の点群の分布状態を示す点を代表点として求めると共に、当該求めた代表点を基準として新たな局所領域を定め、当該新たな局所領域の点群の分布状態を示す点を新たな代表点として求める頂点生成部と、
前記頂点生成部で求めた全ての代表点を順に接続して折れ線を作画する折れ線出力部とを備えたことを特徴とする折れ線作画装置。
【請求項２】
前記頂点生成部は、前記局所領域の代表点を求める処理を、前記対象となる点群のうち、いずれの局所領域にも含まれない点が存在しなくなるまで行うことを特徴とする請求項１記載の折れ線作画装置。
【請求項３】
前記点群抽出部は、３次元の点群のうち、１次元の座標を所定範囲として、当該所定範囲内の点群を抽出することを特徴とする請求項１記載の折れ線作画装置。
【請求項４】
前記頂点生成部は、前記代表点を局所領域の重心とし、かつ、前記新たな局所領域を定める際、前記重心を中心とした円領域とすると共に、当該重心を求めた局所領域内の点を取り除いて前記新たな局所領域を定めることを特徴とする請求項１記載の折れ線作画装置。
【請求項５】
３次元の点群に３次元領域の局所領域を定め、当該局所領域の点群の分布状態を示す点を代表点として求めると共に、当該求めた代表点を基準として新たな３次元領域の局所領域を定め、当該新たな３次元領域の局所領域の点群の分布状態を示す点を新たな代表点として求める頂点生成部と、
前記頂点生成部で求めた全ての代表点を順に接続して折れ線を作画する折れ線出力部とを備えたことを特徴とする折れ線作画装置。
【請求項６】
前記頂点生成部は、前記代表点を基準とする局所領域を定める際、当該局所領域の形状及び範囲のうち少なくともいずれか一方の値を、前記代表点を基準とする局所領域を定める処理を行う度に変更することを特徴とする請求項１から請求項５のうちのいずれか１項記載の折れ線作画装置。
【請求項７】
前記頂点生成部は、前記局所領域に含まれる各点に対し、当該局所領域の中心までの距離を算出し、当該距離の統計量を用いて前記変更する値を決定することを特徴とする請求項６記載の折れ線作画装置。
【請求項８】
前記頂点生成部は、前記局所領域の点群の分布状態を示す点を代表点として求める際、外れ点を除外した領域を前記局所領域とすることを特徴とする請求項１から請求項５のうちのいずれか１項記載の折れ線作画装置。
【請求項９】
前記頂点生成部は、前記局所領域内の各点について、当該局所領域内の最近傍点までの距離を算出し、当該最近傍点までの距離が閾値よりも大きい場合に外れ点とすることを特徴とする請求項８記載の折れ線作画装置。
【請求項１０】
点群抽出部が、折れ線を作画する対象となる点群を抽出する点群抽出ステップと、
頂点生成部が、前記対象となる点群に局所領域を定め、当該局所領域の点群の分布状態を示す点を代表点として求めると共に、当該求めた代表点を基準として新たな局所領域を定め、当該新たな局所領域の点群の分布状態を示す点を新たな代表点として求める頂点生成ステップと、
折れ線出力部が、前記頂点生成ステップで検出した全ての代表点を順に接続して折れ線を作画する作画ステップとを備えたことを特徴とする折れ線作画方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、３次元点群データで表現される地形または図形を折れ線（ポリライン）で近似表現する折れ線作画装置及び折れ線作画方法に関する。
【背景技術】
【０００２】
３次元点群データは、物体の形状や空間の構造を把握及び解析するために有用である。３次元点群データは、特定の座標系（一般に三次元計測装置の位置を原点とする）における３次元点座標［Ｘ，Ｙ，Ｚ］の集合である。用いる三次元計測装置によっては、３次元の点に次のような副次的な情報が含まれる場合がある。すなわち、色情報、レーザの反射強度（レーザを照射する計測装置の場合）、法線の向きなどである。【０００３】
３次元点群データを何らかの表示装置で表示する場合、特定の高さに目安となるような等高線を表示することで、確認や解析の作業が容易になる。例えば、地形を計測して得られた３次元点群データを確認する際に、注目する高さに等高線が表示されていれば、地形をより効率良く把握できる。等高線を引く高さは、予め決められている場合もあるが、ユーザがその時々で指定する場合もある。ユーザによる指定には、高さを数値で入力したり、目的の高さの点をクリックなどで選択したりする。等高線を引く高さが予め決められている場合は、決められた高さの等高線を事前に一度算出しておけばよい。一方、ユーザによる指定の場合は、ユーザが指定した高さに合わせてその場で毎回等高線を算出する必要がある。【０００４】
現在では、計算資源の豊富な汎用計算機（いわゆるデスクトップパソコンやワークステーション）だけでなく、比較的計算資源が限られたスマートフォンやタブレットといった端末を用いて３次元点群データを閲覧する場合がある。このような端末は持ち運びが容易であり、三次元計測をする現地でリアルタイムに計測結果を確認するのに便利である。このように比較的計算資源の限られた端末を用いて、かつ円滑に３次元点群データが表す形状を把握する場合に、高速かつ滑らかな等高線の作画が重要である。【０００５】
従来、このような等高線作画する方法として、例えば特許文献１に示されるようなものがあった。これは、次のような処理を行うものである。
１．点群データから等高線を作成する高さの位置を基準位置線とし、基準位置線に対して上方位置線及び下方位置線を定め、上方層及び下方層の二つの層を形成する。
２．上方層に属する点群データと下方層に属する点群データとの間の２点を最短距離で結ぶ直線を算出し、この直線と基準位置線との交点を求める。従って、直線及び交点は複数算出される。
３．上記２．で得た交点を順次接続する。接続では、いずれかの交点を端点（開始点）とし、線の端点から最短距離にあたる点を直線でつなぐことを繰り返す。ただし、既に接続された点は対象としないこととし、かつ、接続した前の二点の延長線上からある範囲の角度と距離内にある場合のみ接続する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００３−３１７１１２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記従来の方法では、次のような問題があった。
（１）計算量が比較的多いため、等高線の作画及び表示に時間がかかる。
（２）点群データの質によっては等高線がぎざぎざになってしまい、視認性が低下する。
上記（１）の計算量が比較的多いという問題点は次の理由からである。すなわち、特許文献１の技術では、点群データを上方層と下方層に分けた後、上方層に属する点と、下方層に属する点を最短距離で結ぶ直線を算出する。この処理では、どちらかの層に属する点１点に対し、もう片方の層で最近傍探索処理を行う必要がある。さらに、算出した直線と基準位置線との交点を求める処理も必要である。これらの処理により、計算量が比較的多くなってしまう。
また、上記（２）の等高線がぎざぎざになるという問題点は次の理由によるものである。すなわち、特許文献１の技術では、入力された点群データ内の点のいくつかを接続して等高線を作画する。点群データ内に、計測誤差の大きい点やノイズが含まれる場合は、これらの点を接続することで、出力である等高線がぎざぎざになってしまう。また、前述の外れ点を含まなかったり、外れ点を何らかの方法で除去できたりしたとしても、複雑な形状をもつ３次元点群データでは、やはり等高線がぎざぎざになってしまう。【０００８】
この発明は、かかる問題を解決するためになされたもので、折れ線で近似表現する際の処理を高速に行い、かつ折れ線を滑らかに作画することのできる折れ線作画装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
この発明に係る折れ線作画装置は、折れ線を作画する対象となる点群を抽出する点群抽出部と、対象となる点群に局所領域を定め、局所領域の点群の分布状態を示す点を代表点として求めると共に、求めた代表点を基準として新たな局所領域を定め、新たな局所領域の点群の分布状態を示す点を新たな代表点として求める頂点生成部と、頂点生成部で求めた全ての代表点を順に接続して折れ線を作画する折れ線出力部とを備えたものである。
【発明の効果】
【００１０】
この発明に係る折れ線作画装置は、局所領域の点群の分布状態を示す点を代表点として求めると共に、求めた代表点を基準として新たな局所領域を定め、新たな局所領域の点群の分布状態を示す点を新たな代表点として求めるようにしたものである。これにより、折れ線で近似表現する際の処理が高速に行え、かつ折れ線を滑らかに作画することができる。
【図面の簡単な説明】
【００１１】
【図１】この発明の実施の形態１の折れ線作画装置の構成図である。
【図２】この発明の実施の形態１の折れ線作画装置のハードウェア構成図である。
【図３】この発明の実施の形態１の折れ線作画装置の動作を示すフローチャートである。
【図４】この発明の実施の形態２の折れ線作画装置における３次元点群データを座標平面と平行でない特定の平面で切断したときの断面の輪郭線を作図する場合の動作を示すフローチャートである。
【図５】この発明の実施の形態２の折れ線作画装置における移動体の位置を一定時間間隔で取得し３次元空間中にプロットしたデータから移動軌跡を作図する場合の動作を示すフローチャートである。
【図６】この発明の実施の形態２の折れ線作画装置における白線領域の点のみを抽出し、抽出された点群をもとに白線を作図する場合の動作を示すフローチャートである。
【図７】この発明の実施の形態３の折れ線作画装置の動作を示すフローチャートである。
【図８】この発明の実施の形態４の折れ線作画装置の動作を示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下、この発明をより詳細に説明するために、この発明を実施するための形態について、添付の図面に従って説明する。
実施の形態１．
図１は、本実施の形態による折れ線作画装置とその周辺機器の構成図である。
折れ線作画装置１０は、３次元点群データ読込部１１、点群抽出部１２、頂点生成部１３、折れ線出力部１４を備える。３次元点群データ読込部１１は、折れ線を作画する元となる３次元点群データを折れ線作画装置１０に読み込む機能を有している。点群抽出部１２は、３次元点群データ読込部１１によって読み込まれた３次元点群データから折れ線を作画する対象となる点群を抽出する機能を有している。頂点生成部１３は、点群に局所領域を定め、局所領域の点群の分布状態を示す点を代表点として求めると共に、求めた代表点を基準として新たな局所領域を定め、新たな局所領域の点群の分布状態を示す点を新たな代表点として求める処理を、対象となる点群のうち、いずれの局所領域にも含まれない点が存在しなくなるまで行う機能を有している。折れ線出力部１４は、頂点生成部で求めた全ての代表点を順に接続して折れ線を作画する機能を有している。
周辺機器のパラメータ入力装置２０は、キーボード及びマウス等の入力機器からなり、折れ線を作画する高さなどのパラメータをユーザが入力するための装置である。また、表示装置３０は、折れ線出力部１４から出力された折れ線等のデータを表示する装置であり、例えば液晶ディスプレイで構成される。
【００１３】
図２は、折れ線作画装置のハードウェア構成図である。
折れ線作画装置はコンピュータを用いて実現されており、プロセッサ１０１、メモリ１０２、入出力インタフェース（入出力Ｉ／Ｆ）１０３、外部記憶装置１０４、バス１０５を備えている。プロセッサ１０１は、３次元点群データ読込部１１〜折れ線出力部１４の機能に対応したそれぞれのプログラムをメモリ１０２に読み込んで実行することにより、３次元点群データ読込部１１〜折れ線出力部１４を構成する。メモリ１０２は、各種データを記憶すると共に、プロセッサ１０１の作業領域を構成する。入出力インタフェース１０３は、パラメータ入力装置２０及び表示装置３０との信号または他の周辺機器との信号をやり取りするためのインタフェースである。外部記憶装置１０４は、３次元点群データ読込部１１〜折れ線出力部１４のそれぞれの機能に対応したプログラムを格納すると共に、各種のデータを記憶するための記憶装置である。バス１０５は、プロセッサ１０１、入出力インタフェース１０３、外部記憶装置１０４を相互に通信接続するための信号路である。
【００１４】
次に、実施の形態１の折れ線作画装置の動作について図３のフローチャートを用いて説明する。なお、実施の形態１では、折れ線近似の一例を等高線として説明する。
等高線を作画する元となる３次元点群データは外部記憶装置１０４に格納され、これを３次元点群データ読込部１１が読み込んでメモリ１０２に格納する。パラメータ入力装置２０より、等高線を作画する高さなどのパラメータが入力された場合、このパラメータは入出力インタフェース１０３を介してメモリ１０２に記憶される。なお、パラメータの入力としては、例えば、キーボードを用いて数値を入力したり、マウスを用いて目的の高さを持つ点を画面上でクリックしたりする。
【００１５】
点群抽出部１２では、３次元点群データ読込部１１で読み込まれた点群データのうち、特定の高さを持つ点だけを抽出する。例えば、ユーザに高さｈ（ｍ）及び許容範囲Δｈ（ｍ）を指定させ、高さ（Ｚ座標値）が（ｈ−Δｈ，ｈ＋Δｈ）の範囲内である点のみを抽出し、２次元点群を得る（ステップＳＴ１）。以降では、このように抽出された２次元点群を抽出点群と記す。なお、ステップＳＴ１では、メモリ１０２から点群データが読み出され、プロセッサ１０１で処理される。
【００１６】
頂点生成部１３では、点群抽出部１２で抽出された抽出点群から、等高線の頂点及びそれらの接続順を算出する。この処理も、メモリ１０２からデータを読み出し、プロセッサ１０１で実行される。まず、開始点を選び、代表点として登録する（ステップＳＴ２）。開始点の選び方には様々な方法が考えられるが、例えばユーザが何らかの方法で座標を指定する方法や、抽出点群の重心から最も離れた点を開始点とする方法などがある。次に、頂点生成部１３は、代表点を中心とする半径ｒの円領域を設定する（ステップＳＴ３）。また、領域内に代表点以外の点があった場合（ステップＳＴ４：ＹＥＳ）、円領域内の点について重心を計算し、新たな代表点として登録する。さらに、円領域内に含まれる新たな代表点以外の全ての点を抽出点群から取り除く（ステップＳＴ５）。その後、ステップＳＴ３に戻り、新たな代表点を中心として円領域を設定する。ステップＳＴ３とステップＳＴ５の処理を、ステップＳＴ４において、領域内に代表点以外の点が無くなる（ステップＳＴ４：ＮＯ）まで繰り返す。
【００１７】
折れ線出力部１４では、頂点生成部１３で算出された代表点を順に接続することで、等高線を生成する（ステップＳＴ６）。等高線の生成では、代表点の間を直線で接続してもよいし、代表点を制御点としたスプライン曲線を描画してもよい。なお、すべての代表点（等高線の頂点）の高さ（Ｚ座標）は、ユーザが指定した高さｈとする。生成した等高線は、表示装置３０を用いてユーザに提示される。
【００１８】
なお、上記例では折れ線近似を等高線であるとして、高さ（Ｚ座標値）が所定範囲内にある点群を抽出したが、等高線に限定されるものではなく、例えばＸ座標値またはＹ座標値といった１次元の座標値の所定範囲を点群の抽出対象とすることも可能である。
また、上記例では、局所領域の点群の分布状態を示す点として、局所領域の重心を代表点として求めたが、これに限定されるものではない。例えば、領域内の点の各軸座標について中央値をとり、それら中央値を座標とする点を代表点としてもよい。それ以外にも、点の分布モデルが既知ならば、そのようなモデルを当てはめ、分布のピーク位置を代表点の座標とすることも可能である。
さらに、上記例では、局所領域を新たな代表点が中心となるよう移動させたが、必ずしも中心となるように移動させなくてもよい。例えば、局所領域内の点群に直線をフィッティングし、局所領域をその直線に沿って一定量だけ移動させる、といった処理であってもよい。
【００１９】
以上説明したように、実施の形態１の折れ線作画装置によれば、折れ線を作画する対象となる点群を抽出する点群抽出部と、対象となる点群に局所領域を定め、局所領域の点群の分布状態を示す点を代表点として求めると共に、求めた代表点を基準として新たな局所領域を定め、新たな局所領域の点群の分布状態を示す点を新たな代表点として求める頂点生成部と、頂点生成部で求めた全ての代表点を順に接続して折れ線を作画する折れ線出力部とを備えたので、折れ線で近似表現する際の処理が高速に行え、かつ折れ線を滑らかに作画することができる。
【００２０】
また、実施の形態１の折れ線作画装置によれば、頂点生成部は、局所領域の代表点を求める処理を、対象となる点群のうち、いずれの局所領域にも含まれない点が存在しなくなるまで行うようにしたので、代表点を正確に求めることができる。
【００２１】
また、実施の形態１の折れ線作画装置によれば、点群抽出部は、３次元の点群のうち、１次元の座標を所定範囲として、所定範囲内の点群を抽出するようにしたので、処理の高速化を図ることができる。
【００２２】
また、実施の形態１の折れ線作画装置によれば、頂点生成部は、代表点を局所領域の重心とし、かつ、新たな局所領域を定める際、重心を中心とした円領域とすると共に、重心を求めた局所領域内の点を取り除いて新たな局所領域を定めるようにしたので、計算量を削減し、かつ、ノイズや計測誤差に対してロバストとすることができる。従って、処理の高速化と滑らかな折れ線の作画が可能となる。
【００２３】
また、実施の形態１の折れ線作画方法によれば、点群抽出部が、折れ線を作画する対象となる点群を抽出する点群抽出ステップと、頂点生成部が、対象となる点群に局所領域を定め、局所領域の点群の分布状態を示す点を代表点として求めると共に、求めた代表点を基準として新たな局所領域を定め、新たな局所領域の点群の分布状態を示す点を新たな代表点として求める頂点生成ステップと、折れ線出力部が、頂点生成ステップで検出した全ての代表点を順に接続して折れ線を作画する作画ステップとを備えたので、折れ線で近似表現する際の処理が高速に行え、かつ折れ線を滑らかに作画することができる。
【００２４】
実施の形態２．
実施の形態１では、特定の高さかつ座標平面（例えばＸＹ平面）に平行な等高線を引くことを目的としている。一方で、アプリケーションによっては、前述の条件に当てはまらない、３次元的な線を作図することが必要な場合がある。例えば、３次元点群データを特定の平面（座標平面と平行でない）で切断したときの断面の輪郭線を作図したり、ドローンなどの移動体の位置を一定時間間隔で取得し３次元空間中にプロットしたデータから移動軌跡を作図したりする場合がある。その他にも、モービルマッピングシステムを用いて取得した道路周辺の３次元点群データから、色情報や反射強度情報を用いて白線領域の点のみを抽出し、抽出された点群をもとに白線を作図する応用も考えられる。このような例を実施の形態２として次に説明する。
【００２５】
実施の形態２の折れ線作画装置において、図面上の構成は図１及び図２と同様であるため、これらの図面を用いて説明する。実施の形態２の３次元点群データ読込部１１及び折れ線出力部１４は実施の形態１と同様である。一方、点群抽出部１２は、３次元の領域内で折れ線を作画する対象となる点群を抽出する機能を有している。頂点生成部１３は、点群に３次元領域の局所領域を定め、局所領域の点群の分布状態を示す点を代表点として求めると共に、求めた代表点を基準として新たな３次元領域の局所領域を定め、新たな３次元領域の局所領域の点群の分布状態を示す点を新たな代表点として求める処理を、対象となる点群のうち、いずれの局所領域にも含まれない点が存在しなくなるまで行うよう構成されている。図１及び図２においてその他の構成は実施の形態１と同様であるため、ここでの説明は省略する。
【００２６】
次に、実施の形態２の折れ線作画装置の動作について説明する。先ず、３次元点群データを座標平面と平行でない特定の平面で切断したときの断面の輪郭線を作図する場合の動作について説明する。
図４は、その処理を示すフローチャートである。
点群抽出部１２では、３次元点群データ読込部１１で読み込まれた点群データのうち、座標平面と平行でない特定の平面で切断したときの断面の一定範囲の点群だけを抽出する（ステップＳＴ１１）。以降では、このように抽出された３次元点群を抽出点群と記す。
【００２７】
頂点生成部１３では、点群抽出部１２で抽出された抽出点群から、開始点を選び、代表点として登録する（ステップＳＴ１２）。次に、頂点生成部１３は、代表点を中心とする半径ｒの球領域を設定する（ステップＳＴ１３）。また、領域内に代表点以外の点があった場合（ステップＳＴ１４：ＹＥＳ）、球領域内の点について重心を計算し、これを新たな代表点として登録すると共に、球領域内に含まれる全ての点を抽出点群から取り除く（ステップＳＴ１５）。その後、ステップＳＴ１３に戻り、新たな代表点を中心として球領域を設定する。ステップＳＴ１３とステップＳＴ１５の処理を、ステップＳＴ１４において、領域内に代表点以外の点が無くなる（ステップＳＴ１４：ＮＯ）まで繰り返す。
【００２８】
折れ線出力部１４では、頂点生成部１３で算出された代表点を順に接続することで、輪郭線を生成する（ステップＳＴ１６）。輪郭線の生成では、代表点の間を直線で接続してもよいし、代表点を制御点としたスプライン曲線を描画してもよい。生成した輪郭線は、表示装置３０を用いてユーザに提示される。
【００２９】
次に、ドローンなどの移動体の位置を一定時間間隔で取得し３次元空間中にプロットしたデータから移動軌跡を作図する場合の処理を図５のフローチャートを用いて説明する。
点群抽出部１２では、３次元点群データ読込部１１で読み込まれた点群データのうち、作画に不要な点群を取り除いた移動軌跡の点群だけを抽出する（ステップＳＴ２１）。例えば、移動軌跡から明らかな外れ点を除去した移動軌跡の点群データを求める。以降では、このように抽出された３次元点群を抽出点群と記す。
【００３０】
頂点生成部１３では、点群抽出部１２で抽出された抽出点群から、開始点を選び、代表点として登録する（ステップＳＴ２２）。次に、頂点生成部１３は、代表点を中心とする半径ｒの球領域を設定する（ステップＳＴ２３）。また、領域内に代表点以外の点があった場合（ステップＳＴ２４：ＹＥＳ）、球領域内の点について重心を計算し、新たな代表点として登録すると共に、球領域内に含まれる全ての点を抽出点群から取り除く（ステップＳＴ２５）。その後、ステップＳＴ２３に戻り、新たな代表点を中心として球領域を設定する。ステップＳＴ２３とステップＳＴ２５の処理を、ステップＳＴ２４において、領域内に代表点以外の点が無くなる（ステップＳＴ２４：ＮＯ）まで繰り返す。
【００３１】
折れ線出力部１４では、頂点生成部１３で算出された代表点を順に接続することで、移動軌跡を生成する（ステップＳＴ２６）。移動軌跡の生成では、代表点の間を直線で接続してもよいし、代表点を制御点としたスプライン曲線を描画してもよい。生成した移動軌跡は、表示装置３０を用いてユーザに提示される。
【００３２】
次に、道路周辺の３次元点群データから、色情報や反射強度情報を用いて白線領域の点のみを抽出し、抽出された点群をもとに白線を作図する場合の処理を図６のフローチャートを用いて説明する。
点群抽出部１２では、３次元点群データ読込部１１で読み込まれた点群データのうち、白に近い特定範囲の色または白に近い反射強度を持つ点群だけを抽出する（ステップＳＴ３１）。これにより、白線領域の点のみを抽出することができる。以降では、このように抽出された３次元点群を抽出点群と記す。
【００３３】
頂点生成部１３では、点群抽出部１２で抽出された抽出点群から、開始点を選び、代表点として登録する（ステップＳＴ３２）。次に、頂点生成部１３は、代表点を中心とする半径ｒの球領域を設定する（ステップＳＴ３３）。また、領域内に代表点以外の点があった場合（ステップＳＴ３４：ＹＥＳ）、球領域内の点について重心を計算し、新たな代表点として登録すると共に、球領域内に含まれる全ての点を抽出点群から取り除く（ステップＳＴ３５）。その後、ステップＳＴ３３に戻り、新たな代表点を中心として球領域を設定する。ステップＳＴ３３とステップＳＴ３５の処理を、ステップＳＴ３４において、領域内に代表点以外の点が無くなる（ステップＳＴ３４：ＮＯ）まで繰り返す。
【００３４】
折れ線出力部１４では、頂点生成部１３で算出された代表点を順に接続することで、白線領域の近似線を生成する（ステップＳＴ３６）。白線領域の近似線の生成では、代表点の間を直線で接続してもよいし、代表点を制御点としたスプライン曲線を描画してもよい。生成した白線領域の近似線は、表示装置３０を用いてユーザに提示される。
【００３５】
以上説明したように、実施の形態２の折れ線作画装置によれば、３次元の点群に３次元領域の局所領域を定め、局所領域の点群の分布状態を示す点を代表点として求めると共に、求めた代表点を基準として新たな３次元領域の局所領域を定め、新たな３次元領域の局所領域の点群の分布状態を示す点を新たな代表点として求める頂点生成部と、頂点生成部で求めた全ての代表点を順に接続して折れ線を作画する折れ線出力部とを備えたので、３次元の領域内で折れ線で近似表現する際の処理が高速に行え、かつ折れ線を滑らかに作画することができる。
【００３６】
実施の形態３．
実施の形態３は、頂点生成部１３が、代表点を基準とした局所領域を定める際、局所領域の形状及び範囲のうち少なくともいずれか一方の値を、繰り返しの度に変更するようにした例である。折れ線作画装置における図面上の構成は図１及び図２と同様であるため、これらの図を用いて説明する。
【００３７】
実施の形態３の折れ線作画装置における頂点生成部１３は、円領域の半径ｒを動的に調整するよう構成されている。その他の構成については実施の形態１と同様であるため、ここでの説明は省略する。
【００３８】
次に、実施の形態３の折れ線作画装置の動作を図７のフローチャートを用いて説明する。図７のフローチャートにおいて、ステップＳＴ１〜ステップＳＴ５の処理は実施の形態１と同様である。ステップＳＴ５の処理を行った際、実施の形態３では、領域内の点について、代表点である領域中心からの距離の標準偏差を算出し、この標準偏差を元に、領域の半径ｒを再設定する（ステップＳＴ７）。例えば、算出された標準偏差をσとすると、ｒ＝２σと設定する。なお、ここでは標準偏差を用いて領域の半径を設定したが、標準偏差に限らず、その他の統計量を用いてもよい。ステップＳＴ７において半径ｒを再設定した後のステップＳＴ３以降の動作は実施の形態１と同様である。これにより、円領域に基づく代表点の算出を繰り返す度に半径ｒが再設定されることになる。
【００３９】
なお、上記例では局所領域の範囲を再設定するようにしたが、局所領域の形状を変更するようにしても良い。また、局所領域の範囲と形状の両方を変更するようにしてもよい。
【００４０】
以上説明したように、実施の形態３の折れ線作画装置によれば、頂点生成部は、代表点を基準とする局所領域を定める際、局所領域の形状及び範囲のうち少なくともいずれか一方の値を、代表点を基準とする局所領域を定める処理を行う度に変更するようにしたので、代表点をより正確に求めることができる。
【００４１】
また、実施の形態３の折れ線作画装置によれば、頂点生成部は、局所領域に含まれる各点に対し、局所領域の中心までの距離を算出し、距離の統計量を用いて変更する値を決定するようにしたので、変更する値を正確に求めることができる。
【００４２】
実施の形態４．
実施の形態４は、頂点生成部１３が、代表点を基準とした局所領域を定める際、局所領域に含まれる外れ点を除外した後に新たな代表点を定めるようにしたものである。折れ線作画装置における図面上の構成は図１及び図２と同様であるため、これらの図を用いて説明する。
【００４３】
実施の形態４の頂点生成部１３は、実施の形態１の頂点生成部１３の機能に加えて、局所領域の点群の分布状態を示す点を代表点として求める際、外れ点を除外した領域を局所領域とするよう構成されている。その他の構成については実施の形態１と同様であるため、ここでの説明は省略する。
【００４４】
次に、実施の形態４の折れ線作画装置の動作を図８のフローチャートを用いて説明する。図８のフローチャートにおいて、ステップＳＴ１〜ステップＳＴ４までの処理は実施の形態１と同様である。実施の形態４では、ステップＳＴ５ａの処理を行った際、頂点生成部１３は、外れ点を除去し、その上で新たな代表点を算出する。外れ点の除外は次のようにする。例えば、円領域内の各点について、同領域内で最近傍点を探索し、その最近傍点までの距離を算出する。その後、最近傍点までの距離の平均を算出し、最近傍点までの距離がその平均と比べて大きく異なる点があれば、その点を外れ点として除外する。この判定では、例えば標準偏差を利用し、最近傍点までの距離の平均がｄ、標準偏差がσのとき、最近傍点までの距離が（ｄ＋２σ）を超える点を外れ点とする。なお、ここで述べたような、統計量を用いた外れ点の除外方法以外にも、クラスタリングに基づいた外れ点の除去方法を用いてもよい。そのような方法として、例えば、文献：Birant Derya、Alp Kut著、「ST-DBSCAN:An algorithm for clustering spatial-temporal data」、Data & Knowledge Engineering、vol.60、no.1、pp.208-221、2007年に示す方法も用いることができる。
【００４５】
また、ステップＳＴ５ａにおいて、外れ点を除去した後に、円領域内の点について重心を計算し、新たな代表点として登録すると共に、円領域内に含まれる新たな代表点以外の全ての点を抽出点群から取り除く処理は実施の形態１と同様である。さらに、ステップＳＴ６は実施の形態１と同様である。
【００４６】
以上説明したように、実施の形態４の折れ線作画装置によれば、頂点生成部は、局所領域の点群の分布状態を示す点を代表点として求める際、外れ点を除外した領域を局所領域とするようにしたので、代表点をより正確に求めることができる。
【００４７】
また、実施の形態４の折れ線作画装置によれば、頂点生成部は、局所領域内の各点について、局所領域内の最近傍点までの距離を算出し、最近傍点までの距離が閾値よりも大きい場合に外れ点とするようにしたので、外れ点を正確に求めることができる。
【００４８】
なお、本願発明はその発明の範囲内において、各実施の形態の自由な組合せ、あるいは各実施の形態の任意の構成要素の変形、もしくは実施の形態の任意の構成要素の省略が可能である。
【産業上の利用可能性】
【００４９】
以上のように、この発明に係る折れ線作画装置及び折れ線作画方法は、３次元点群データから特定の折れ線を求める構成に関するものであり、例えば、地形などの３次元形状を計測して得られた３次元点群データから、等高線を作画するのに適している。
【符号の説明】
【００５０】
１０  折れ線作画装置、１１  ３次元点群データ読込部、１２  点群抽出部、１３  頂点生成部、１４  折れ線出力部、２０  パラメータ入力装置、３０  表示装置。
【図１】
2019111323.tif 000003
【図２】
2019111323.tif 000004
【図３】
2019111323.tif 000005
【図４】
2019111323.tif 000006
【図５】
2019111323.tif 000007
【図６】
2019111323.tif 000008
【図７】
2019111323.tif 000009
【図８】
2019111323.tif 000010
【手続補正書】
【提出日】令和2年2月4日(2020.2.4)
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
この発明は、３次元点群データで表現される地形または図形を折れ線（ポリライン）で近似表現する折れ線作画装置に関する。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
この発明に係る折れ線作画装置は、折れ線を作画する対象となる点群を抽出する点群抽出部と、対象となる点群に局所領域を定め、当該局所領域の点群における点について算出された重心に位置する点を代表点として求めると共に当該重心に位置する点を求めた局所領域内に存在する代表点以外の点を取り除き、当該代表点を中心とした円領域を新たな局所領域と定め、当該新たな局所領域の点群における点について算出された重心に位置する点を新たな代表点として求める頂点生成部と、頂点生成部で求めた全ての代表点を順に接続して折れ線を作画する折れ線出力部とを備えたものである。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
この発明に係る折れ線作画装置は、局所領域の点群における点について算出された重心に位置する点を代表点と求めると共に、当該局所領域内に存在する新たな代表点以外の点を取り除き、求めた代表点を中心とした円領域を新たな局所領域と定め、新たな局所領域の点群における点について算出された重心に位置する点を新たな代表点として求めるようにしたものである。これにより、折れ線で近似表現する際の処理が高速に行え、かつ折れ線を滑らかに作画することができる。しかも、計算量を削減し、かつ、ノイズや計測誤差に対してロバストとすることができる。
【手続補正５】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
折れ線を作画する対象となる点群を抽出する点群抽出部と、
前記対象となる点群に局所領域を定め、当該局所領域の点群における点について算出された重心に位置する点を代表点として求めると共に当該重心に位置する点を求めた局所領域内に存在する前記代表点以外の点を取り除き、当該求めた代表点を中心とした円領域を新たな局所領域と定め、当該新たな局所領域の点群における点について算出された重心に位置する点を新たな代表点として求める頂点生成部と、
前記頂点生成部で求めた全ての代表点を順に接続して折れ線を作画する折れ線出力部とを備えたことを特徴とする折れ線作画装置。
【請求項２】
折れ線を作画する対象となる点群を抽出する点群抽出部と、
前記対象となる点群に局所領域を定め、当該局所領域の点群の分布状態を示す点を代表点として求めると共に、前記局所領域の点群の点に対する当該局所領域の中心までの距離を算出し、当該求めた代表点を基準として前記算出された距離の統計量を用いて前記局所領域の形状及び範囲のうち少なくともいずれか一方の値を変更して新たな局所領域を定め、当該新たな局所領域の点群の分布状態を示す点を新たな代表点として求める頂点生成部と、
前記頂点生成部で求めた全ての代表点を順に接続して折れ線を作画する折れ線出力部とを備えたことを特徴とする折れ線作画装置。
【請求項３】
折れ線を作画する対象となる点群を抽出する点群抽出部と、
前記対象となる点群に局所領域を定め、当該局所領域の点群における点について算出された重心に位置する点を代表点として求めると共に、当該重心に位置する点を求めた局所領域の点群の点に対する当該局所領域の中心までの距離を算出し、当該重心を求めた局所領域内に存在する前記代表点以外の点を取り除き、当該求めた代表点を中心として前記算出された距離の統計量を用いて半径が設定された円領域を新たな局所領域と定め、当該新たな局所領域の点群における点について算出された重心に位置する点を新たな代表点として求める頂点生成部と、
前記頂点生成部で求めた全ての代表点を順に接続して折れ線を作画する折れ線出力部とを備えたことを特徴とする折れ線作画装置。
【請求項４】
折れ線を作画する対象となる点群を抽出する点群抽出部と、
前記対象となる点群に局所領域を定め、当該局所領域内の点群の各点について、当該局所領域内の最近傍点までの距離を算出し、当該最近傍点までの距離が閾値よりも大きい場合に外れ点とし、当該局所領域内の点群から当該外れ点を除外した点群の分布状態を示す点を代表点として求めると共に、当該求めた代表点を基準として新たな局所領域を定め、当該新たな局所領域の点群の各点について、当該新たな局所領域内の最近傍点までの距離を算出し、当該最近傍点までの距離が閾値よりも大きい場合に外れ点とし、当該新たな局所領域の点群から当該外れ点を除外した点群の分布状態を示す点を新たな代表点として求める頂点生成部と、
前記頂点生成部で求めた全ての代表点を順に接続して折れ線を作画する折れ線出力部とを備えたことを特徴とする折れ線作画装置。
【請求項５】
折れ線を作画する対象となる点群を抽出する点群抽出部と、
前記対象となる点群に局所領域を定め、当該局所領域内の点群の各点について、当該局所領域内の最近傍点までの距離を算出し、当該最近傍点までの距離が閾値よりも大きい場合に外れ点とし、当該局所領域内の点群から当該外れ点を除外した点群における点について算出された重心に位置する点を代表点として求めると共に当該重心に位置する点を求めた局所領域内に存在する前記代表点以外の点を取り除き、当該求めた代表点を中心とした円領域を新たな局所領域を定め、当該新たな局所領域の点群の各点について、当該新たな局所領域内の最近傍点までの距離を算出し、当該最近傍点までの距離が閾値よりも大きい場合に外れ点とし、当該新たな局所領域の点群から当該外れ点を除外した点群における点について算出された重心に位置する点を新たな代表点として求める頂点生成部と、
前記頂点生成部で求めた全ての代表点を順に接続して折れ線を作画する折れ線出力部とを備えたことを特徴とする折れ線作画装置。
【請求項６】
前記頂点生成部は、前記新たな局所領域の新たな代表点を求める処理を、前記対象となる点群のうち、いずれの新たな局所領域にも含まれない点が存在しなくなるまで行うことを特徴とする請求項１から請求項５のいずれかに記載の折れ線作画装置。
【請求項７】
前記点群抽出部は、３次元の点群のうち、１次元の座標を所定範囲として、当該所定範囲内の点群を抽出することを特徴とする請求項１から請求項６のいずれかに記載の折れ線作画装置。
【国際調査報告】
2019111323.tif 000011
2019111323.tif 000012