(57)【要約】【課題】  従来の見通し計算では、観測点から見通し限界点まで、仰角の算出及び仰角の比較処理を実行する。この場合の計算オーダは、メッシュ点数ｎに対して観測方位ごとにＯ（ｎ２）となり、メッシュ間隔が小さいと計算時間が膨大になってしまう。即応性が求められるシステムにおいて、見通し計算により覆域を得るためには、仰角計算の回数を減らし計算オーダを低減することが課題となる。【解決手段】  画像の重なり判定を用いて計算対象を絞込んで計算量を削減し、ソートアルゴリズムを利用した見通し計算を行うことで、見通し計算の計算オーダをＯ（ｎ２）からＯ（nlogn）に低減する。以上の効果により、従来手法に比べ、高速に覆域を得ることが可能となる。【選択図】      図１
2016062384.tif 000002
【特許請求の範囲】
【請求項１】
入力された３次元の地形データを、高度の違いに応じて複数段階の階調に色分けして画像化し、かつ観測高度以下の地形データに対応した画像を除去した画像を生成する画像生成処理部と、
画像生成処理部の生成した画像の図形に対して、観測点を中心に回転した扇形が重なりを有するときの扇形の存在領域を、見通し計算の対象領域として出力する計算対象の絞込み処理部と、
計算対象の絞込み処理部から出力される見通し計算の対象領域について、観測点からの最近傍点をソートアルゴリズムで探索して、探索した最近傍点を見通し限界点とする見通し限界点及び覆域算出部と、
を備えた見通し計算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元地形データに基づいて、観測点から見通し可能な地点を計算する見通し計算装置である。
【背景技術】
【０００２】
従来、ある観測点からの見通し計算は次のように行われていた。まず、緯度、経度及び標高等からなる３次元の地形を表現する３次元地形データについて、その構成データをメッシュ状に分割し、離散化した複数の格子点を生成して、各格子点の地点での地形データを保持する。次に、観測点から各地形データを保持した地点までの観測方向及び観測高度に対して、観測点から各地形データを保持した地点を見た仰角の算出（以下、仰角算出処理）及び隣接する地形データを保持した地点間の仰角の比較処理を行うことで、観測点からの見通し限界点を算出する。そして、見通し計算を観測点の全周の地形データを保持した地点で行うことにより、見通し可能な覆域を算出する（例えば非特許文献１参照）。
【０００３】
図５は、従来の見通し計算の原理を説明する図である。
図５において、観測点５１から、観測方向５２に対して、観測点５１と地形データを保持した地点との仰角５３の算出処理を行う。順次仰角５３の算出処理を行い、ある地点での仰角５３が、ひとつ前の地点で算出した仰角５３よりも小さくなるか、仰角５３の算出処理を行う地点が観測高度５４に達した時点で終了し、その地点５５を見通し限界点とする。
【０００４】
図６は、従来の覆域算出の原理を説明する図である。図６で説明した見通し限界点５５の算出を、観測点の全周の地形データを保持した地点で行うことにより、観測点の周囲の見通し限界点５５を求めて、見通し可能な覆域を算出する。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Daniel Cohen-Or ans Amit SHAkedl(1995),”Visibility and Dead-Zones in Degital Terrain Maps”,EuroGraphics Association(1995),Volume14,Number3
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来の見通し計算は、観測点から見通し限界点まで、仰角の算出及び仰角の比較処理からなる仰角計算を繰り返し実行する。この仰角計算の計算オーダは観測方位ごとにＯ（Ｎ２）となり、格子点の間隔（以下、メッシュ間隔）が小さいと計算時間が膨大になる。このため即応性が求められる場合、見通し計算により覆域を得るためには、仰角計算の回数を減らし、その計算オーダを低減することが課題となる。
【０００７】
本発明は係る課題を解決するためになされたものであり、見通し計算における仰角計算の回数を減らし、その計算オーダを低減することを目的とする。
【課題を解決するための手段】
【０００８】
本発明による見通し計算装置は、入力された３次元の地形データを、高度の違いに応じて複数段階の階調に色分けして画像化し、かつ観測高度以下の地形データに対応した画像を除去した画像を生成する画像生成処理部と、画像生成処理部の生成した画像の図形に対して、観測点を中心に回転した扇形が重なりを有するときの扇形の存在領域を、見通し計算の対象領域として出力する計算対象の絞込み処理部と、計算対象の絞込み処理部から出力される見通し計算の対象領域について、観測点からの最近傍点をソートアルゴリズムで探索して、探索した最近傍点を見通し限界点とする見通し限界点及び覆域算出部と、を備えたものである。
【発明の効果】
【０００９】
本発明によれば、画像間演算及びソートアルゴリズムを用いて計算量を削減することにより、従来に比べて計算オーダが低減し、見通し計算及び覆域の算出にかかる計算時間を大幅に短縮することが可能となる。
【図面の簡単な説明】
【００１０】
【図１】実施の形態１による見通し計算装置の構成を示す図である。
【図２】実施の形態１の見通し計算装置における、画像間減算処理により観測高度以上の地点のみの画像を生成する画像生成処理部を説明する図である。
【図３】実施の形態１の見通し計算装置における、画像の重なり判定処理を用いた計算対象の絞込み処理部を説明する図である。
【図４】実施の形態１の見通し計算装置における、ソートアルゴリズムを用いた見通し限界点及び覆域算出部を表した図である。
【図５】従来技術における見通し計算処理の概要を説明する図である。
【図６】従来技術における覆域算出処理の概要を説明する図である。
【発明を実施するための形態】
【００１１】
実施の形態１．
図１は、実施の形態１による見通し計算装置の構成を示す図である。図１において、実施の形態１による見通し計算装置３０は、画像生成処理部２０と、計算対象の絞込み処理部２１と、見通し限界点及び覆域算出部２２を備えている。画像生成処理部２０は、外部から地形データと観測高度が入力され、外部から入力された地形データの画像化処理と画像の減算処理を行う。計算対象の絞込み処理部２１は、画像生成処理部２０の出力画像について画像の重なり判定処理を行い、計算対象とする画像を絞り込む。見通し限界点及び覆域算出部２２は、計算対象の絞込み処理部２１の処理結果について、見通し限界点を得て覆域を算出する。色データベース２３は、予め地形データの高度を複数の範囲に区分けしておき、区分けした高度範囲毎に異なる色を割り当てて登録している。画像生成処理部２０は色データベース２３を参照し、高度に対応した色を出力する。
【００１２】
図２は、画像間減算処理により観測高度以上の地点のみの画像を生成する画像生成処理部１０の処理内容を説明する図であり、（ａ）は高度の違いにより色を分けて画像化した図を示し、（ｂ）は（ａ）の画像から観測高度帯の画像を減算した図を示す。画像生成処理部２０は、緯度、経度及び標高等からなる３次元の地形を表現するデータについて、その構成データがメッシュ状に分割され、離散化された複数の格子点（メッシュ端）の地点毎の地形データが入力される。画像生成処理部２０は、入力された地形データを高度の違いにより複数段階の階調に色分けし、色分けした地形データを画像化する。
例えば画像生成処理部２０は、離散化したそれぞれの格子点の地点での高度に基づいて色データベース２３を参照し、色データベース２３から各格子点の高度に対応した色を取り出し、格子点毎に取り出した色情報を経度、緯度の情報とともに内部メモリに格納する。このとき画像生成処理部２０は、正方形を構成する隣接した４つの格子点の中で、高度に対応した色の異なる格子点が存在する場合、４つの格子点全ての色を、最も低い高度に対応した色に合わせるように、内部メモリに書き込んだ色情報の書換えを行う。かくして、図２（ａ）に示すように、内部メモリに格納した隣接する４つの格子点で囲まれた正方形の単位で、格子点の高度に対応した色情報に基づいて色付けし、入力された地形データを高度の違いにより色を分けて画像化し、画像Ａを生成する。
【００１３】
次に、画像生成処理部２０は、観測高度４よりも低い高度となる観測高度帯について、その観測高度帯の高度のみを有した地形データを、外部から入力された地形データの中から取り出す。画像生成処理部２０は、取り出した観測高度帯までの高度を有した地形データを用いて、図２（ａ）と同様にして、高度の違いにより複数段階の階調に色分けした地形データを画像化する。
例えば画像生成処理部２０は、離散化したそれぞれの格子点の地点での高度に基づいて色データベース２３を参照し、色データベース２３から各格子点の高度に対応した色を取り出し、格子点毎に取り出した色情報を経度、緯度の情報とともに内部メモリに格納する。このとき画像生成処理部２０は、正方形を構成する隣接した４つの格子点の中で、高度に対応した色の異なる格子点が存在する場合、４つの格子点全ての色を、最も低い高度に対応した色に合わせるように、内部メモリに書き込んだ色情報の書換えを行う。かくして、内部メモリに格納した隣接する４つの格子点で囲まれた正方形の単位で、格子点の高度に対応した色情報に基づいて色付けし、入力された観測高度帯に含まれる地形データのみを高度の違いにより色を分けて画像化し、画像Ｂを生成する。
【００１４】
続いて、画像生成処理部２０は、地形データについて高度の違いにより色を分けて画像化した画像Ａから、地形データの中の観測高度帯に含まれるデータについて高度の違いにより色を分けて画像化した画像Ｂを減算する画像間演算を行うことで、図２（ｂ）に示すような観測高度以上の地点のみの画像を生成する。
【００１５】
なお、画像生成処理部２０は、ＧＰＵ(Graphics Processing Unit)を用いて画像間演算を行うことで、より高速な処理が可能となる。
【００１６】
次に、図３は、画像の重なり判定処理を用いた計算対象の絞込み処理部２１の処理内容を説明する図である。図３に示すように、計算対象の絞込み処理部２１は、見通し限界距離を半径とした扇形の図形を、観測点を中心として３６０°回転させる。このとき計算対象の絞込み処理部２１は、図２（ｂ）に示す観測高度以上の地点のみの画像中の図形と、３６０°回転中の扇形の図形との重なり判定処理を行う。
例えば図３において扇形の角度を３０°とし、３０°間隔の回転角度θｉ（ｉ＝１〜１２）で扇形を１２回分回転させる（θ１＝３０°、θ２＝６０°、θ３＝９０°、θ４＝１２０°、θ５＝１５０°、θ６＝１８０°、θ７＝２１０°、θ８＝２４０°、θ９＝２７０°、θ１０＝３００°、θ１１＝３３０°、θ１２＝３６０°）。
このときｉ＝１、２、３、４、５、１１、１２に該当する部分が、重なり判定処理において、扇形の図形と観測高度以上の地点のみの画像中の図形とで重なりのある領域となる。また、ｉ＝６、７、８、９、１０に該当する部分が、重なり判定処理において、扇形の図形と観測高度以上の地点のみの画像中の図形とで重なりのない領域となる。
ここでの重なり判定処理は、例えば扇形の外形を離散化された点で表現し、扇形の外形よりも内側に含まれる格子点の座標（扇形の外形線上の座標は含まない）を、扇形の回転毎に取得する。当該取得した格子点の座標を構成する全ての点について、観測高度以上の地点のみの画像中の図形と比較する。
【００１７】
この比較処理は、観測高度以上の地点のみの画像中の図形について、その外形の内側の４つの格子点で囲まれた各セル（正方形領域部）が色付きの画像である場合、当該セルを構成する４つの格子点全てが、所定角度θｉ（ｉ＝Ｍ）での上記扇形の外形の内側に含まれる格子点の座標の何れかに一致する場合、当該所定角度θｉ（ｉ＝Ｍ）での扇形を、重なり判定処理において重なりのある領域と判定する。一方、当該セルを構成する４つの格子点の何れかが、所定角度θｉ（ｉ＝Ｎ）での上記扇形の外形の内側に含まれる格子点の座標の何れにも一致しない場合、当該所定角度θｉ（ｉ＝Ｎ）での扇形を、重なり判定処理において重なりのない領域と判定する。
【００１８】
計算対象の絞込み処理部２１は、当該重なり判定処理にて重なりのない領域（ｉ＝６、７、８、９、１０に該当する扇形の領域）となる、見通し限界距離を半径とした扇形の図形全域を見通しできる覆域として、当該領域の見通し計算は行わない。これにより見通し計算の計算量を削減することができる。
【００１９】
なお、計算対象の絞込み処理部２１は、ＧＰＵ(Graphics Processing Unit)を用いて重なり判定処理を行うことで、より高速な処理ができる。
【００２０】
見通し限界点及び覆域算出部２２は、まず、計算対象の絞込み処理部２１の重なり判定処理にて重なりのある領域と判定された回転角度θｉの扇形の領域に対して、見通し限界点を得る。
このとき見通し限界点及び覆域算出部２２は、観測点を中心とする観測方位φｊ毎に、図２（ｂ）に示す観測高度以上の地点のみの画像中の図形の外形線と観測点との最近傍点を、ソートアルゴリズムで探索して、探索した最近傍点を見通し限界点として得る。
また、ソートアルゴリズムは、観測点から観測方位φｊの正方向に微小間隔で座標を取り、図２（ｂ）に示す観測高度以上の地点のみの画像中の図形の外形線と交わるか、もしくは外形線を超えたところの近傍格子点を、最近傍点とする。
【００２１】
次に、見通し限界点及び覆域算出部２２は、計算対象の絞込み処理部２１の重なり判定処理にて重なりのない領域と判定された回転角度θｉの扇形の領域に対して、見通し限界距離を求める。
【００２２】
かくして、観測点から観測方位φｊの正方向および負方向に向かって、見通し限界距離またはメッシュ端に達するまで、０より大きい値の探索を続けることで見通し限界点を得ることができる。また、探索にソートアルゴリズムを用いることで、計算オーダは０（nlogn）となる。
【００２３】
以上説明した通り、実施の形態１による見通し計算装置は、入力された３次元の地形データを、高度の違いに応じて複数段階の階調に色分けして画像化し、かつ観測高度以下の地形データに対応した画像を除去した画像を生成する画像生成処理部２０と、画像生成処理部２０の生成した画像の図形に対して、観測点を中心に回転した扇形が重なりを有するときの扇形の存在領域を、見通し計算の対象領域として出力する計算対象の絞込み処理部２１と、計算対象の絞込み処理部２１から出力される見通し計算の対象領域について、観測点からの最近傍点をソートアルゴリズムで探索して、探索した最近傍点を見通し限界点とする見通し限界点及び覆域算出部２２とを備えたものである。
【００２４】
これにより、画像間演算及びソートアルゴリズムを用いて計算量を削減することにより、従来に比べて計算オーダが低減し、見通し計算及び覆域の算出にかかる計算時間を大幅に短縮することが可能となる。
【００２５】
なお、実施の形態１による見通し計算装置は、航空管制や気象観測等でのレーダ覆域の模擬等に利用することができる。
【符号の説明】
【００２６】
２０  画像生成処理部、２１  計算対象の絞込み処理部、２２  見通し限界点及び覆域算出部、２３  色データベース、３０  見通し計算装置。
【図１】
2016062384.tif 000003
【図２】
2016062384.tif 000004
【図３】
2016062384.tif 000005
【図４】
2016062384.tif 000006
【図５】
2016062384.tif 000007
【図６】
2016062384.tif 000008