(57)【要約】【課題】レーザスキャナを用いて得られた空間座標点群のデータからポリゴンのデータを生成し、このポリゴンのデータを用いて画像を電子計算機のディスプレイに表示させる際に、視認性の高い画像を生成可能とした画像表示方法、及び画像表示装置、並びに画像表示プログラムを提供する。【解決手段】空間座標点群のデータは、レーザスキャナによる１回のスキャンで得られた点群のデータに全て同一のスキャンの時刻データを付与してグループ化し、ポリゴンのデータを生成する際に、第１のスキャンで得られた第１の点群のデータの１点と、第１のスキャンの直後に行われた第２のスキャンで得られた第２の点群のデータの１点とそれぞれ結ぶ仮想線であって、各仮想線の長さの総和が極小となる仮想線を設定し、この仮想線に基づいてポリゴンのデータを生成する【選択図】図９
2010257261.tif 000002
【特許請求の範囲】
【請求項１】
レーザスキャナで順次スキャニングして得られた空間座標点のデータを用いてポリゴンのデータを生成し、このポリゴンのデータを用いて画像を電子計算機のディスプレイに表示させる画像表示方法であって、
前記空間座標点のデータを、前記レーザスキャナによる１回のスキャンで得られた複数の空間座標点のデータごとにグループ化し、
ポリゴンのデータを生成する際に、第１のスキャンで得られた複数の空間座標点の１点と、前記第１のスキャンの直後に行われた第２のスキャンで得られた複数の空間座標点の１点とそれぞれ結ぶ仮想線であって、各仮想線の長さの総和が極小となる仮想線を設定し、この仮想線に基づいて前記ポリゴンのデータを生成している画像表示方法。
【請求項２】
全ての空間座標点のデータから、前記ディスプレイに表示させる画像の生成に必要となる空間座標点のデータをあらかじめ抽出している請求項１に記載の画像表示方法。
【請求項３】
レーザスキャナで順次スキャニングして得られた空間座標点のデータを記憶する第１の記憶部と、
前記空間座標点のデータから生成されたポリゴンのデータを記憶する第２の記憶部と、
前記ポリゴンのデータを用いてディスプレイに画像を表示させるＣＰＵと
を備えた電子計算機からなる画像表示装置であって、
前記空間座標点のデータを、前記レーザスキャナによる１回のスキャンで得られた複数の空間座標点のデータごとにグループ化しておき、
前記ＣＰＵは、前記ポリゴンのデータを生成する際に、
第１のスキャンで得られた複数の空間座標点の１点と、前記第１のスキャンの直後に行われた第２のスキャンで得られた複数の空間座標点の１点とそれぞれ結ぶ仮想線を仮定して各仮想線の長さの総和を演算するとともに、この仮想線の長さの総和が極小となる仮想線を特定して、この仮想線に基づいて前記ポリゴンのデータを生成する画像表示装置。
【請求項４】
前記ＣＰＵが、全ての空間座標点のデータから、前記ディスプレイに表示させる画像の生成に必要となる空間座標点のデータをあらかじめ抽出している請求項３に記載の画像表示装置。
【請求項５】
ＣＰＵとディスプレイを備えた電子計算機に、レーザスキャナで順次スキャニングして得られた空間座標点のデータからポリゴンのデータを生成させて、このポリゴンのデータを用いて前記ディスプレイに画像を表示させる画像表示プログラムであって、
前記空間座標点のデータは、前記レーザスキャナによる１回のスキャンで得られた複数の空間座標点のデータごとにグループ化しておき、
前記ＣＰＵに、第１のスキャンで得られた複数の空間座標点の１点と、この第１のスキャンの直後に行われた第２のスキャンで得られた複数の空間座標点の１点とそれぞれを結ぶ仮想線の長さの総和を演算させるステップと、
前記ＣＰＵに、前記仮想線の長さの総和が極小となる仮想線を特定させるステップと、
前記ＣＰＵに、特定された前記仮想線に基づいて前記ポリゴンのデータを生成させるステップと
を有する画像表示プログラム。
【請求項６】
前記ＣＰＵに、全ての空間座標点のデータから、前記ディスプレイに表示させる画像の生成に必要となる空間座標点のデータを抽出させるステップを有する請求項５に記載の画像表示プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、レーザスキャナを用いて得られた空間座標点群から、視認しやすい画像を生成して表示させる画像表示方法、及び画像表示装置、並びに画像表示プログラムに関するものである。
【背景技術】
【０００２】
昨今、カーナビゲーションシステムでは、運転者による認識性を高めるために、平面図からなる地図の画像をディスプレイに表示するだけでなく、運転者の視点で捉えた立体的な画像を表示することにより、平面状の地図が苦手な運転者でも直感的に認識可能な地図情報を提供可能としている。
【０００３】
このような３次元の立体的な地図の画像データは、２次元の地図データに、各建物の高さのデータを追加することにより作成可能ではあるが、実際には、建物の高さのデータを収集する作業が困難であって、簡単には作成できなかった。
【０００４】
そこで、２次元の地図データにおいて建物の高さを計測するための目標点となる建物頂部の隅角部をあらかじめ特定しておき、高精度ＧＰＳ(Global Positioning System)を搭載した車両にデジタルカメラなどの撮影手段を搭載して、車両で移動しながら異なる２地点で目標点を撮影して、幾何学手法により目標点の高さを特定する３次元地図データベースの作成方法及び装置が提案されている（例えば、特許文献１参照。）。
【０００５】
あるいは、幾何学手法によって建物の高さデータを測定するのではなく、レーザを利用して対象物までの距離を計測することにより立体地図を作成することも提案されている。
【０００６】
特に、レーザを利用して対象物までの距離を計測する場合には、正確な距離を計測できることから、測定の基準となる地点の３次元データ、すなわち、緯度、経度、高さの空間データがわかっていれば、対象物の３次元データを特定でき、このことを利用して３次元ＣＡＤデータを生成することも提案されている。
【０００７】
たとえば、三菱電機株式会社の三菱モービルマッピングシステムでは、図１４に示すように、車両100の天井部分に支持基台110を装着し、この支持基台110に３台のＧＰＳ装置120と、下方に向けてレーザを照射する第１レーザスキャナ130と、上方に向けてレーザを照射する第２レーザスキャナ140と、下方の路面を撮影する第１カメラ150と、前方を撮影する第２カメラ160と、慣性計測装置(IMU)170をそれぞれ所定位置に装着して、走行しながらＧＰＳ装置120あるいは慣性計測装置170で位置情報を逐次取得するとともに、第１レーザスキャナ130で道路面をスキャンし、また、トンネル内を走行している場合には第２レーザスキャナ140でトンネルの内面をスキャンして空間座標のデータを収集している。
【０００８】
さらに、第１レーザスキャナ130と第２レーザスキャナ140によるスキャンとともに、第１カメラ150で道路面を撮影し、第２カメラ160で前方の景色を撮影している。
【０００９】
このマッピングシステムでは、車両100で通常走行しながら空間座標のデータを収集できるので、データ収集に要する時間を大幅に削減することができる。
【００１０】
収集されたデータは空間座標点の集合となっており、これらのデータを用いて所定の視点からの画像投影を行うことにより、図１５に示す点群画像を生成できる。
【００１１】
しかしながら、点群画像では、点と点との間がすけているために、実際には遮蔽されていて見えないはずの点までが表示されるといった遮蔽関係の表現における不具合が生じやすく、良好な視認性が得られない場合があった。
【００１２】
そこで、第１カメラ150あるいは第２カメラ160で撮影された画像を用い、この画像に点群画像を投影することにより視認性を補っていた。このように生成された画像を用いて対象物の抽出を行い、３次元ＣＡＤデータを生成したり、３次元地図が作成されたりしていた。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開２０００−０７４６６９号公報
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、第１カメラあるいは第２カメラで撮影された画像に点群画像を投影させて使用する場合には、第１カメラあるいは第２カメラで撮影された画像をベースとした画像しか表示できず、点群画像が有している利点を十分に利用できていなかった。
【００１５】
すなわち、第１レーザスキャナ及び第２レーザスキャナを用いて取得された空間座標点のデータは、空間の絶対的な位置のデータであるので、視点を変えたとしても各空間座標点の位置自体は不変であり、任意の位置に視点を設定できるが、視点を変えると第１カメラあるいは第２カメラで撮影された画像と点群画像とがずれるため、視点を変えることができなかった。
【００１６】
したがって、視点を変えたい場合には、点群画像として表示するしかなく、良好な視認性が得られないという問題が再度生じることとなっていた。しかも、点群画像では、全体的な雰囲気は表現できても傾きなどの連続的な状態の表現が不可能であり、例えば道路の傾斜状態や凹みの状態などが見えにくいという問題があった。
【００１７】
そこで、空間座標点のデータからポリゴンを生成して面を描画しようとしたが、レーザスキャナを用いて空間座標点のデータを取得する際に、照射したレーザが対象物によって吸収または散乱されることによって十分な反射光が得られないと、存在すべき空間座標点が欠損することとなり、この空間座標点の欠損によって面を生成するための適正なポリゴンが生成できないという問題があった。
【００１８】
特に、空間座標点の欠損の発生には規則性がなく、どの空間座標点が欠損しているかを特定する手段がないために、適正なポリゴンが生成できないことが多く、不適正なポリゴンを用いた描画を行うことにより、却って画質の低下を招くおそれがあった。
【課題を解決するための手段】
【００１９】
そこで、本発明の画像表示方法では、レーザスキャナで順次スキャニングして得られた空間座標点のデータを用いてポリゴンのデータを生成し、このポリゴンのデータを用いて画像を電子計算機のディスプレイに表示させる画像表示方法であって、空間座標点のデータを、レーザスキャナによる１回のスキャンで得られた複数の空間座標点のデータごとにグループ化し、ポリゴンのデータを生成する際に、第１のスキャンで得られた複数の空間座標点の１点と、第１のスキャンの直後に行われた第２のスキャンで得られた複数の空間座標点の１点とそれぞれ結ぶ仮想線であって、各仮想線の長さの総和が極小となる仮想線を設定し、この仮想線に基づいてポリゴンのデータを生成することとした。
【００２０】
さらに、本発明の画像表示方法では、全ての空間座標点のデータから、ディスプレイに表示させる画像の生成に必要となる空間座標点のデータをあらかじめ抽出していることにも特徴を有するものである。
【００２１】
また、本発明の画像表示装置では、レーザスキャナで順次スキャニングして得られた空間座標点のデータを記憶する第１の記憶部と、空間座標点のデータから生成されたポリゴンのデータを記憶する第２の記憶部と、ポリゴンのデータを用いてディスプレイに画像を表示させるＣＰＵとを備えた電子計算機からなる画像表示装置であって、空間座標点のデータを、レーザスキャナによる１回のスキャンで得られた複数の空間座標点のデータごとにグループ化しておき、ＣＰＵは、ポリゴンのデータを生成する際に、第１のスキャンで得られた複数の空間座標点の１点と、第１のスキャンの直後に行われた第２のスキャンで得られた複数の空間座標点の１点とそれぞれ結ぶ仮想線を仮定して各仮想線の長さの総和を演算するとともに、この仮想線の長さの総和が極小となる仮想線を特定して、この仮想線に基づいてポリゴンのデータを生成することとした。
【００２２】
さらに、本発明の画像表示装置では、ＣＰＵが、全ての空間座標点のデータから、ディスプレイに表示させる画像の生成に必要となる空間座標点のデータをあらかじめ抽出していることにも特徴を有するものである。
【００２３】
また、本発明の画像表示プログラムでは、ＣＰＵとディスプレイを備えた電子計算機に、レーザスキャナで順次スキャニングして得られた空間座標点のデータからポリゴンのデータを生成させて、このポリゴンのデータを用いてディスプレイに画像を表示させる画像表示プログラムであって、空間座標点のデータは、レーザスキャナによる１回のスキャンで得られた複数の空間座標点のデータごとにグループ化しておき、ＣＰＵに、第１のスキャンで得られた複数の空間座標点の１点と、この第１のスキャンの直後に行われた第２のスキャンで得られた複数の空間座標点の１点とそれぞれを結ぶ仮想線の長さの総和を演算させるステップと、ＣＰＵに、仮想線の長さの総和が極小となる仮想線を特定させるステップと、ＣＰＵに、特定された仮想線に基づいてポリゴンのデータを生成させるステップとを有することとした。
【００２４】
さらに、本発明の画像表示プログラムでは、ＣＰＵに、全ての空間座標点のデータから、ディスプレイに表示させる画像の生成に必要となる空間座標点のデータを抽出させるステップを有することにも特徴を有するものである。
【発明の効果】
【００２５】
本発明によれば、空間座標点のデータからポリゴンのデータを生成する際に、第１のスキャンで得られた複数の空間座標点の１点と、第１のスキャンの直後に行われた第２のスキャンで得られた複数の空間座標点の１点とそれぞれ結ぶ仮想線を仮定し、各仮想線の長さの総和を演算して、この仮想線の長さの総和が最小となる仮想線を特定し、この仮想線に基づいてポリゴンのデータを生成することにより、第１のスキャン及び／または第２のスキャンにおいて空間座標点のデータの欠損が生じたとしても、より最適と思われる仮想線に基づいてポリゴンのデータが生成できる。したがって、ディスプレイに表示される画像に異常が生じにくく、実際の目視による画像に近い視認しやすい画像を生成できる。
【００２６】
しかも、第１カメラあるいは第２カメラで撮影された画像を用いることなく視認しやすい画像を生成できるので、画像の生成に必要なデータをレーザスキャナで順次スキャニングして得られた空間座標点のデータだけとして高速に画像を生成することができ、メモリ容量の少ない電子計算機でも利用可能であって、例えば、カーナビゲーションシステムの３次元の地図データとして用いることもできる。
【００２７】
特に、全ての空間座標点のデータから、ディスプレイに表示させる画像の生成に必要となる空間座標点のデータをあらかじめ抽出して、抽出した空間座標点のデータを用いてポリゴンのデータを生成することによって、より高速に所望の画像を生成できる。
【００２８】
また、ポリゴンのデータの生成にともなって面が生成されることから、シェーディングによって陰影を付けることにより表面状態を視認しやすくすることができ、例えば道路表面の摩耗の状態の確認、特に轍の形成状態の確認、あるいはマンホール周辺の沈み込みの確認などに利用でき、さらに、表面状態だけでなく断面状態を表示することも可能であって、道路やトンネルの断面形状のデータを抽出することもできる。
【００２９】
さらには、道路設計において必要とされている視距の確認作業にも使用でき、空間座標点のデータさえあれば電子計算機上で視距の自動判定を行うことができる。
【図面の簡単な説明】
【００３０】
【図１】ポリゴンを生成するための仮想線の説明図である。
【図２】ポリゴンを生成するための仮想線の説明図である。
【図３】仮想線の組み合わせの説明図である。
【図４】２つのスキャンライン間における空間座標点の対応付けの説明図である。
【図５】本発明の実施形態にかかる画像表示装置の概略模式図である。
【図６】本発明の実施形態にかかる画像表示プログラムのフローチャートである。
【図７】視野に含まれる区間の説明図である。
【図８】本発明の実施形態にかかる画像表示プログラムのフローチャートである。
【図９】本発明の実施形態にかかる画像表示プログラムのフローチャートである。
【図１０】本発明の実施形態にかかる画像表示プログラムのフローチャートである。
【図１１】ＤＤＡモードで生成した画像である。
【図１２】ＯＰＴモードで生成した画像である。
【図１３】本発明の実施形態にかかる画像表示プログラムのフローチャートである。
【図１４】三菱モービルマッピングシステムの説明図である。
【図１５】三菱モービルマッピングシステムで生成された点群画像である。
【発明を実施するための形態】
【００３１】
本発明の画像表示方法、及び画像表示装置、並びに画像表示プログラムでは、レーザスキャナを用いてあらかじめ取得された空間座標点のデータを電子計算機のディスプレイに表示させる際に、空間座標点のデータからポリゴンのデータを生成して、このポリゴンのデータを用いてディスプレイに画像を表示させているものである。
【００３２】
ここで、空間座標点のデータからポリゴンのデータを生成する場合に、本当ならば存在すべき空間座標点が欠損していることがあり、この空間座標点の欠損に起因して適正なポリゴンが描けなくなっていたが、本発明では空間座標点の欠損が生じている場合でも可能な限り適正なポリゴンを生成することにより、良質な画像を生成可能としているものである。すなわち、ポリゴンの生成の最適化を行っているものである。
【００３３】
なお、空間座標点のデータは、上述した三菱電機株式会社の三菱モービルマッピングシステムで得られたものであり、この三菱モービルマッピングシステムでは、レーザスキャナによって得られた各点のデータを、経度・緯度・高度からなる３次元の位置のデータと、スキャンが開始された時刻のデータと、色のデータとで構成している。なお、色のデータは、３次元の位置のデータで特定される位置を、第１カメラまたは第２カメラで撮影された画像上に対応付けして特定されたデータであって、三菱モービルマッピングシステムの内部処理によって自動的に特定されている。
【００３４】
空間座標点のデータにおいて、１回のスキャン中に取得された複数の空間座標点は、時刻のデータが全て同一となっている。
【００３５】
そこで、時刻のデータを利用して、同一の時刻のデータを有する空間座標点ごとにグループ化でき、グループ単位で空間座標点を取り扱うことにより、ポリゴンのデータの生成を行いやすくすることができる。
【００３６】
すなわち、ポリゴンのデータを生成する場合には、レーザスキャナによるスキャンを開始してからｎ回目のスキャンで得られた空間座標点と、ｎ＋１回目のスキャンで得られた空間座標点とを識別でき、これらの空間座標点間でポリゴンのデータの生成を行い、ｎを順番にインクリメントしていくことにより、１画面分のポリゴンのデータを生成することとしている。
【００３７】
ここで、１回のスキャンで得られた空間座標点の集まりを、「スキャンライン」と呼ぶこととする。
【００３８】
ｎ回目のスキャンラインとｎ＋１回目のスキャンラインにおいて、それぞれ空間座標点の欠損が生じていない場合には、各スキャンラインにおける空間座標点の数が同一となるので、空間座標点同士を１対１で対応づけることができ、簡単にポリゴンのデータを生成することができる。
【００３９】
すなわち、例えば、図１（ａ）に示すように、ｎ回目のスキャンラインSnにおける空間座標点の数と、ｎ＋１回目のスキャンラインSn+1における空間座標点の数がそれぞれ４個の場合には、図１（ｂ）に示すように、端の空間座標点から順番に各空間座標点を結ぶ仮想線を想定することができ、容易にポリゴンのデータを生成できる。
【００４０】
一方、例えば、図２（ａ）に示すように、ｎ回目のスキャンラインSnではP0、P1、P2、P3の４個の空間座標点を有し、ｎ＋１回目のスキャンラインSn+1ではQ0、Q1、Q2の３個の空間座標点を有する場合には、各点を結ぶ仮想線は、図２（ｂ）、図２（ｃ）、図２（ｄ）に示す３通りが考えられることとなる。
【００４１】
すなわち、図２（ｂ）の場合では、仮想線は、４本の線分であるP0−Q0、P1−Q0、P2−Q1、P3−Q2となり、図２（ｃ）の場合では、仮想線は、４本の線分であるP0−Q0、P1−Q1、P2−Q1、P3−Q2となり、図２（ｄ）の場合では、仮想線は、４本の線分であるP0−Q0、P1−Q1、P2−Q2、P3−Q2となる。
【００４２】
これらの３通りの仮想線の組み合わせは、ｎ＋１回目のスキャンラインSn+1において空間座標点の欠損が生じているために、どのパターンの仮想線の組み合わせとしても空間座標点の欠損を完全には補えないが、本発明では、これらの中で最適な組み合わせに最も近いと思われる組み合わせを選択することにより、ディスプレイに表示される画像に異常が生じにくいポリゴンデータを生成可能としている。
【００４３】
すなわち、本発明では、想定される仮想線の組み合わせの中で、仮想線の長さの総和ができるだけ小さくなる組み合わせを選択することにより、選択された組み合わせの仮想線を最適な仮想線とし、この仮想線に基づいてポリゴンのデータを生成している。
【００４４】
なお、仮想線の長さの総和ができるだけ小さくなる組み合わせを特定する際に、想定される仮想線の組み合わせの全てに対して長さの総和を求めることにより、最適と思われる仮想線を特定することができるが、実際問題として、スキャンライン中の空間座標点の数が多くなると、全ての組み合わせの演算に多大な時間を要し、実用的でなくなるおそれがある。
【００４５】
具体的に説明すると、図３に示すように、ｎ回目のスキャンラインでは６個の空間座標点を有し、ｎ＋１回目のスキャンラインでは４個の空間座標点を有する場合には、各点を対応づける仮想線の組み合わせの数は10通りであるが、実際のデータで比較的頻繁に出現する181個の空間座標点と、176個の空間座標点との間で仮想線の組み合わせを考える場合には、約15億通りの組み合わせを考えなければならないこととなっている。
【００４６】
そこで、本発明では、図４に示すように、各空間座標点を結ぶ仮想線の組み合わせを段階的に想定して、各段階で仮想線の長さの総和が最も小さくなる組み合わせに対して、さらに仮想線の組み合わせ調整を行うこととした。
【００４７】
すなわち、ｎ回目のスキャンラインと、ｎ＋１回目のスキャンラインに対して、第１段階では、一方端（図４では右端）の空間座標点から順番に１対１で空間座標点同士を対応づける仮想線を想定するとともに、空間座標点の欠損にともなって１対１の対応付けができない空間座標点は、他方端（図４では左端）の空間座標点でまとめて対応付けする仮想線を想定することとした。すなわち、図４の場合では、ｎ回目のスキャンラインにおける左端の３つの空間座標点を、ｎ＋１回目のスキャンラインにおける左端の１つの空間座標点に結びつける仮想線を想定している。
【００４８】
ここで、図４中の６桁の数字は対応付けインデックスであって、仮想線の結びつけ状態を表している。すなわち、６桁の数字における各桁は、ｎ回目のスキャンラインにおける６個の空間座標点に対応させており、各桁の数字は、ｎ＋１回目のスキャンラインにおける４個の空間座標点のいずれか１つを示すものとしている。
【００４９】
すなわち、「０００１２３」では、６桁目の「０」が、ｎ回目のスキャンラインにおける左端の０番目（右端の空間座標点から６つ目）の空間座標点に、ｎ＋１回目のスキャンラインにおける左端の０番目の空間座標点を結びつける仮想線を設けることを示している。なお、後述するプログラムにおける表現と合わせるために、ここでは「０番目」という表現を用いている。
【００５０】
「０００１２３」の５桁目の「０」は、ｎ回目のスキャンラインにおける０番目の空間座標点の右隣に位置する１番目（右端の空間座標点から５つ目）の空間座標点に、ｎ＋１回目のスキャンラインにおける左端の０番目の空間座標点を結びつける仮想線を設けることを示している。
【００５１】
「０００１２３」の４桁目の「０」は、ｎ回目のスキャンラインにおける１番目の空間座標点の右隣に位置する２番目（右端の空間座標点から４つ目）の空間座標点に、ｎ＋１回目のスキャンラインにおける左端の０番目の空間座標点を結びつける仮想線を設けることを示している。
【００５２】
「０００１２３」の３桁目の「１」は、ｎ回目のスキャンラインにおける２番目の空間座標点の右隣に位置する３番目（右端の空間座標点から３つ目）の空間座標点に、ｎ＋１回目のスキャンラインにおける０番目の空間座標点の右隣に位置する１番目の空間座標点を結びつける仮想線を設けることを示している。
【００５３】
「０００１２３」の２桁目の「２」は、ｎ回目のスキャンラインにおける３番目の空間座標点の右隣に位置する４番目（右端の空間座標点から２つ目）の空間座標点に、ｎ＋１回目のスキャンラインにおける１番目の空間座標点の右隣に位置する２番目の空間座標点を結びつける仮想線を設けることを示している。
【００５４】
「０００１２３」の１桁目の「３」は、ｎ回目のスキャンラインにおける４番目の空間座標点の右隣に位置する５番目（右端の空間座標点から１つ目）の空間座標点に、ｎ＋１回目のスキャンラインにおける２番目の空間座標点の右隣に位置する３番目の空間座標点を結びつける仮想線を設けることを示している。
【００５５】
第２段階では、まず、スキャンラインにおける左端の１つの空間座標点に結びつけた複数の仮想線のうち、１本の仮想線を減じる。すなわち、図４において、ｎ回目のスキャンラインにおける０番目と１番目の空間座標点を、ｎ＋１回目のスキャンラインにおける０番目の空間座標点に対応づける仮想線を想定する。そして、減じた仮想線の代わりとなる仮想線の位置を右側に順次移動させながら仮想線の長さの総和を求める。ここで、説明の便宜上、順次移動させられる仮想線を「移動仮想線」と称することとする。
【００５６】
第２段階で対応づけられた各仮想線の組み合わせのうち、仮想線の長さの総和が最も小さくなる組み合わせを特定し、その特定された仮想線の組み合わせの中における移動仮想線の位置を特定する。この移動仮想線の位置は、空間座標点の欠損を補うために必ず必要となる仮想線であって、この位置には必ず仮想線が設けられるものとする。すなわち、第２段階における３通りの仮想線の組み合わせのうち、１つの仮想線の組み合わせが選択されることとなり、説明の便宜上、ここでは図４中の真ん中の組み合わせが選択されたものとする。
【００５７】
なお、移動仮想線を順次移動させながら仮想線の長さの総和を計算する際には、移動仮想線の移動前の長さを減算し、移動後の移動仮想線の長さを加算するだけで、容易に仮想線の長さの総和を演算できる。
【００５８】
次いで、第３段階では、まず、スキャンラインにおける左端の１つの空間座標点に結びつけた複数の仮想線のうち、さらに１本の仮想線を減じる。すなわち、ｎ回目のスキャンラインにおける０番目の空間座標点を、ｎ＋１回目のスキャンラインにおける０番目の空間座標点に結びつける仮想線を想定する。そして、減じた仮想線の代わりとなる新たな移動仮想線の位置を右側に順次移動させながら仮想線の長さの総和を求める。
【００５９】
このとき、第２段階で特定された移動仮想線の位置には必ず仮想線が設けられるものとしながら、新たな移動仮想線の位置を順次移動させながら仮想線の長さの総和を求めることにより、第２段階で特定された移動仮想線の位置以外に移動仮想線が設けられる組み合わせを無視することとする。すなわち、図４の場合では、第２段階の上側及び下側の組み合わせに基づく仮想線の組み合わせを無視することとする。したがって、仮想線の長さの総和が求められる仮想線の組み合わせは、図４の場合で７回とすることができ、計算量をほぼ半減させることができる。
【００６０】
このように、各段階で仮想線の総和が最小となる仮想線の組み合わせを選択しながら仮想線の組み合わせを調整することにより、計算量を大きく削減することができる。
【００６１】
ただし、この場合には、例えば、図４中の第３段階の一番上の組み合わせが仮に仮想線の総和が最小となるとしても、第２段階において真ん中の組み合わせが選択された場合には、仮想線の総和が真の最小となる仮想線の組み合わせとはならないが、生成された画像においては十分な視認性を有していた。
【００６２】
そこで、本発明では、仮想線の長さの総和が極小となる仮想線を特定できればよいこととした。なお、多くの場合において、特定された極小の仮想線の長さの総和が、最小の仮想線の長さの総和であった。
【００６３】
上述した段階的な仮想線の調整は、スキャンラインにおける左端の１つの空間座標点に対して１対１の対応付けがなされる組み合わせとなるまで、すなわち、図４の場合では、第３段階までで終了することとなる。ただし、第Ｎ＋１段階を経ても、第Ｎ段階での仮想線の総和の最小値を更新できなかった場合には、第Ｎ段階において選択された組み合わせを採用するものとし、対応付け手順を終了させることとしている。ゆえに、図４の場合において、第１段階または第２段階での組み合わせが選択されることもありうる。
【００６４】
このようにして仮想線の長さの総和が極小となる仮想線が特定されると、その仮想線を指定する対応付けインデックスを記憶して、この対応付けインデックスに基づいてポリゴンのデータを生成し、所定の画像をディスプレイに表示させることとしている。
【００６５】
以下において、上述したように仮想線の長さの総和が極小となる仮想線を特定する方法を「ＯＰＴ」と呼び、全ての仮想線の組み合わせから仮想線の長さの総和が最小となる仮想線を特定する方法を「ＡＬＬ」と呼ぶこととする。また、スキャンラインにおける空間座標点の空間的配置を一切考慮せず、対応付けインデックスができるだけ均等に増加するように仮想線を特定する方法を「ＤＤＡ」と呼ぶこととする。例えば、図３のように、ｎ回目のスキャンラインでは６個の空間座標点を有し、ｎ＋１回目のスキャンラインでは４個の空間座標点を有する場合には、「ＤＤＡ」により得られる対応付けインデックスは「０１１２２３」となる。
【００６６】
上述したように、ＡＬＬの場合では、スキャンライン中の空間座標点の数が多くなると、計算量が膨大となるためにディスプレイへの画像の表示速度が大きく低下することとなって、実用的でなくなり、ＤＤＡの場合では、ディスプレイに画像を高速に表示できる一方で、適正でないポリゴンに基づいて画像が生成されることにより、画質の低下を招くこととなっている。
【００６７】
これに対してＯＰＴの場合では、画質はＤＤＡの場合よりもよく、特に、ＡＬＬの場合に近い画質で、ＡＬＬの場合よりも高速に画像を表示でき、ＡＬＬとＤＤＡのいいとこ取りをすることができる。
【００６８】
なお、画質は問わずに高速性能だけを要求するのであればＤＤＡであってもよく、あるいはより高画質を望むのであればＡＬＬであってもよく、ＯＰＴと、ＡＬＬと、ＤＤＡのいずれか１つのモードを適宜選択可能としてもよい。
【００６９】
あるいは、計算量または計算に要する時間に応じて、ＡＬＬからＯＰＴへ、さらにはＯＰＴからＤＤＡへと自動的に切り替え可能としてもよい。
【００７０】
すなわち、各スキャンライン中の空間座標点の数からＡＬＬの場合の計算量を演算して、この計算量があらかじめ設定した第１の閾値よりも少なければＡＬＬモードで仮想線の特定を行い、そうでない場合には、ＤＤＡモードで仮想線の特定を行い、さらに、ＯＰＴの場合の計算量を演算して、この計算量があらかじめ設定した第２の閾値よりも少なければＯＰＴモードで仮想線の特定を行って対応付けインデックスのデータを生成させるとよい。
【００７１】
なお、多くの場合においてＯＰＴモードでは、ＡＬＬモードとほぼ同等の結果が得られるので、ＡＬＬモードは行わず、まず、ＤＤＡモードで仮想線の特定を行い、次いでＯＰＴの場合の計算量を演算して、この計算量があらかじめ設定した閾値よりも少なければＯＰＴモードで仮想線の特定を行って対応付けインデックスのデータを生成させてもよい。
【００７２】
以下において、本発明の実施形態を、さらに詳説する。本発明の画像表示装置は、図５に示すように、ディスプレイ10を備えた電子計算機20であって、この電子計算機20で本発明の画像表示プログラムを実行することによって所定の画像を表示可能としている。
【００７３】
すなわち、電子計算機20は、演算処理を実行するＣＰＵ21と、所要のプログラムやデータを記憶したハードディスクなどの記憶装置22と、所要のプログラムを展開して実行可能とするとともに、演算にともなって生成されたデータを一時的に記憶するＲＡＭなどで構成されたメモリ装置23を備えている。図５中、24はバスである。
【００７４】
さらに、電子計算機20にはグラフィックボード25を設けており、このグラフィックボード25とディスプレイ10とをディスプレイ用ケーブル26を介して接続し、所定の画像をディスプレイ10に表示可能としている。
【００７５】
本実施形態では、記憶装置22に画像表示プログラムと、この画像表示プログラムが使用する空間座標点のデータを記憶させている。なお、画像表示プログラムは、実際にはサブルーチンとして機能するプログラムであって、メインルーチンを司っているメインプログラムからの命令に基づいて、ＣＰＵ21に所定の処理を実行させている。以下においては、画像表示プログラムの動作について説明する。
【００７６】
なお、本実施形態では、画像表示装置を、ディスプレイ10を備えた電子計算機20で構成しているが、電子計算機20で構成する場合に限定するものではなく、例えばいわゆるカーナビゲーション装置などのようにディスプレイと一体的な装置として構成することもできる。
【００７７】
また、本実施形態の画像表示装置では、上述した三菱電機株式会社の三菱モービルマッピングシステムで得られた空間座標点群のデータを記憶装置22にあらかじめ記憶させている。なお、三菱電機株式会社の三菱モービルマッピングシステムにおいて、レーザスキャナは、最大13575点/秒で計測可能としており、車両が時速27Km時で走行する際に地表面を10cm以下のメッシュで計測可能としている。また、レーザの最大到達距離は、対象物のレーザの反射率で異なるが約80m程度である。
【００７８】
記憶装置22に記憶する空間座標点群のデータは、時刻のデータを利用して、同一の時刻のデータを有する空間座標点ごとにグループ化して、スキャンラインごとにデータを読み出せるようにあらかじめ調整している。
【００７９】
画像表示プログラムが起動されると、図６のフローチャートに示すように、画像表示プログラムは、視野の設定を行わせる（ステップS101)。
【００８０】
この視野の設定では、記憶装置22に記憶された空間座標点群のデータに基づいて、ディスプレイ10に点群画像を表示しながら、所望の視野となるように視点の位置を調整している。
【００８１】
次いで、画像表示プログラムでは、設定された視野に基づいて、図７に示すように、三菱モービルマッピングシステムでの走行軌跡の全体から、視野に含まれる区間の始点と終点のリストを作成する（ステップS102)。
【００８２】
図７に示すように、視野の中には、複数の区間が存在することもあり、各区間の始点の時刻と終点の時刻をリストアップすることにより、所望のリストを作成している。このように、全ての空間座標点のデータから、ディスプレイ10に表示させる画像の生成に必要となる空間座標点のデータをあらかじめ抽出させておくことにより、計算をより高速化することができる。
【００８３】
次いで、画像表示プログラムでは、ステップS102でリストアップされた区間の単位で以下のループを開始する（ステップS103)。
【００８４】
まず、画像表示プログラムでは、区間の始点の時刻を含むスキャンラインを検索し、このスキャンラインの番号をSXとする（ステップS104)。
【００８５】
次いで、画像表示プログラムでは、区間の終点の時刻を含むスキャンラインを検索し、このスキャンラインの番号をSYとする（ステップS105)。
【００８６】
そして、画像表示プログラムでは、スキャンラインSXからスキャンラインSYまで描画を行わせ（ステップS106)、スキャンラインSYまで描画した後に、他にも描画する区間があれば、その区間の描画を同様に開始して、全ての区間の描画を終了させている（ステップS107)。
【００８７】
このステップS106での処理が本発明の要部であり、スキャンラインSXからスキャンラインSYまで描画を行わせる際に、隣り合ったスキャンラインSAとスキャンラインSBの間で空間座標点の対応付けの最適化を行い、この最適化された対応付けに基づく対応付けインデックスを用いてポリゴンのデータを生成し、画像の表示を行っている。
【００８８】
図８は、ＤＤＡモードのフローチャートであって、まず、あらかじめ、スキャンラインSA中の空間座標点の数をＭ、スキャンラインSB中の空間座標点の数をＮとする。ここで、本実施形態では、Ｍは１〜180であり、ＮはＮ＞Ｍであって、２〜181としている。
【００８９】
まず、画像表示プログラムでは、整数変数Ｘ及び整数変数Ｙを「０」に初期化し、整数変数DXを「Ｍ−１」に初期化し、整数変数DYを「Ｎ−１」に初期化し、整数変数Ｅを「−DY」に初期化している（ステップS201）。
【００９０】
次いで、画像表示プログラムでは、整数値の配列Ｉ0,Ｉ1,・・・,ＩN-1からなる対応付けインデックスＩのＩYにＸの値を代入して（ステップS202）、整数変数Ｙのインクリメントを行う（ステップS203）。
【００９１】
次いで、画像表示プログラムでは、終了条件判定を行って、終了条件に達していなければ（ステップS204：NO）、整数変数Ｅに２DXを加えて新たな整数変数Ｅとしている（ステップS205）。
【００９２】
そして、画像表示プログラムでは、整数変数Ｅの値が正でなければ（ステップS206：NO）、ステップS202に戻って対応付けインデックスＩの次の項の値を特定する。
【００９３】
一方、整数変数Ｅの値が正の場合には（ステップS206：YES）、画像表示プログラムでは、整数変数Ｘのインクリメントを行い、整数変数Ｅに２DYを加えて新たな整数変数Ｅとし
て、ステップS202に戻り、対応付けインデックスＩの次の項の値を特定する。
【００９４】
画像表示プログラムでは、ステップS204の終了条件判定で終了条件に達すると、処理を終了する。この終了時点で、対応付けインデックスＩは特定されており、ＤＤＡモードで得られる対応付けインデックスＩとなっている。
【００９５】
ＯＰＴモードでは、画像表示プログラムは、図９に示すフローチャートに基づいて処理を実行することにより、仮想線の長さの総和が極小となる仮想線を設定する対応付けインデックスＩを特定している。
【００９６】
すなわち、画像表示プログラムでは、まず、スキャンラインSB中の空間座標点の数Ｎと、スキャンラインSA中の空間座標点の数Ｍとの差をＤとして設定し（ステップS301）、ＤＤＡモードで特定された対応付けインデックスＩに基づいてスキャンラインSAとスキャンラインSBの間に設けられる仮想線の長さの総和を求める（ステップS302）。
【００９７】
ここで、「Distance(SA,SB,I)」は、「スキャンラインSAとスキャンラインSBの間に、対応付けインデックスＩに基づいて設けられる仮想線の長さの総和」を表すものとし、計算結果をdDDAの値とする。
【００９８】
「Distance(SA,SB,I)」は、具体的には、図１０に示すフローチャートに示すように、SUMを「０」とする初期設定を行うとともに、整数変数ｉを「０」とする初期設定を行い（ステップS401）、スキャンラインSAにおける空間座標点SAIiと、スキャンラインSBにおける空間座標点SBiの２点間の距離、すなわち仮想線の長さを計算して、計算結果をSUMに加算し（ステップS402）、整数変数ｉのインクリメントを行って（ステップS403）、計算の終了判定を行い（ステップS404）、終了条件に達したところで（ステップS404：YES）、SUMの値を返却する処理を行っている（ステップS405）。
【００９９】
ステップS302の後、画像表示プログラムでは、仮想線の長さの総和が極小となる仮想線を設定する対応付けインデックスＩを見つけるために、２つの作業用の対応付けインデックスQ,Rを準備する。
【０１００】
すなわち、画像表示プログラムでは、整数変数ｉを「０」に初期化し（ステップS303）、「０」と「ｉ−Ｄ」とを比較して大きい方の値をQiに代入し（ステップS304）、このQiの値をRiに代入し（ステップS305）、整数変数ｉのインクリメントを行って（ステップS306）、作業用の対応付けインデックスQ,Rが準備できたところで（ステップS307：YES）、Distance(SA,SB,I)の値をｄに代入するとともに（ステップS308）、このｄの値をｄminに代入している（ステップS309）。ここで、作業用の対応付けインデックスQ,Rは、上述の図４における第１段階の状態となっている。
【０１０１】
次いで、画像表示プログラムでは、整数変数ｉにステップS301で設定したスキャンラインSB中の空間座標点の数Ｎと、スキャンラインSA中の空間座標点の数Ｍとの差であるＤを代入している（ステップS310）。
【０１０２】
さらに、画像表示プログラムでは、Flagを「０」とするとともに、整数変数ｊに整数変数ｉの値を代入している（ステップS311）。ここで、「Flag」は、インデックスの変更が行われたことを示すフラグとして用いるものであり、整数変数ｊは、移動仮想線の移動処理に用いるものである。
【０１０３】
そして、画像表示プログラムでは、作業用の対応付けインデックスＱにおけるｊ番目の項の値と、ｊ＋１番目の項の値を比較して、一致している場合には何も行わないが（ステップS312：YES）、不一致の場合には（ステップS312：NO）、Distance(SA,SB,I)の値が代入されたｄから、スキャンラインSAにおける空間座標点SAQjと、スキャンラインSBにおける空間座標点SBjの２点間の距離を減算し（ステップS313）、作業用の対応付けインデックスＱにおけるｊ番目の項の値にｊ＋１番目の項の値を代入して（ステップS314）、スキャンラインSAにおける空間座標点SAQjと、スキャンラインSBにおける空間座標点SBjの２点間の距離を加算することにより（ステップS315）、移動仮想線の移動にともなう仮想線の総和の計算を行っている。
【０１０４】
このようにして計算された仮想線の長さの総和の値であるｄが、先のｄminよりも小さい場合には（ステップS316：YES）、仮想線の長さの総和がより小さいインデックスが見つかったことを示しているので、画像表示プログラムでは、このｄの値の演算に用いた作業用の対応付けインデックスＱが、仮想線の長さの総和をより小さくするインデックスであるとして、インデックスを変更したことを示すFlagに「１」を代入し、ｄminを入れ替え、作業用の対応付けインデックスＲを対応付けインデックスＱとしている（ステップS317）。
【０１０５】
なお、ステップS312において、作業用の対応付けインデックスＱにおけるｊ番目の項の値と、ｊ＋１番目の項の値を比較して、一致している場合、及びステップS316において、移動仮想線の移動にともなって計算された仮想線の総和が先のｄminよりも小さくない場合には、インデックスの変更を行わず、整数変数ｊのインクリメントを行って（ステップS318）、移動仮想線をさらに移動させることができるのであれば（ステップS319：NO）、ステップS312に戻って移動仮想線を移動させている。
【０１０６】
一方、移動仮想線をさらに移動させることができないのであれば（ステップS319：YES）、画像表示プログラムでは、仮想線の長さの総和の値であるｄにｄminの値を代入するとともに、作業用の対応付けインデックスＱを作業用の対応付けインデックスＲとして、現時点で最小となる仮想線の長さの総和と、その仮想線を指定する対応付けインデックスを新たな初期値としている（ステップS320）。
【０１０７】
次いで、Flagの値が「０」である場合には（ステップS321：YES）、移動仮想線を移動させても仮想線の長さの総和がさらに小さくなる対応付けインデックスが存在しないことを示しており、逆に、Flagの値が「０」でない場合には（ステップS321：NO）、移動仮想線の移動にともなって仮想線の長さの総和がさらに小さくなる新たな対応付けインデックスが存在したことを示しており、新たな対応付けインデックスが存在した場合には、画像表示プログラムでは、整数変数ｉのデクリメントを行って（ステップS322）、終了条件を満たしていない場合に（ステップS323：NO）、ステップS311に戻ることとしている。これは、上述した図４での第２段階から第３段階に進んでいることに対応している。
【０１０８】
一方、終了条件を満たしていた場合（ステップS323：YES）、及びステップS321でFlagの値が「０」であった場合には、画像表示プログラムでは、ステップS302のdDDAの値とｄminの値とを比較して、ｄminの値の方が小さい場合に（ステップS324：YES）、仮想線の長さの総和が極小となる仮想線を設定する対応付けインデックスＩを作業用の対応付けインデックスＱとしている（ステップS325）。
【０１０９】
一方、dDDAの値の方が小さい場合には（ステップS324：NO）、画像表示プログラムでは、当初の対応付けインデックスＩのままとしている。
【０１１０】
図１１はＤＤＡモードで生成した画像を、図１２はＯＰＴモードで生成した画像を示しており、ＯＰＴモードで生成した画像の方が、ガードレール、及びガードレール沿いの路側帯に乱れが少なく、画質が向上していることがわかる。
【０１１１】
上述した実施形態では、１つの画像を生成する場合について説明したが、時間経過に合わせて視点を移動させながら画像を順次生成することにより、動画像とすることもできる。その場合には、画像の表示速度が要求されるとともに、多少の画像の乱れが目立ちにくくなることから、ＤＤＡモードで画像を生成してもよい。
【０１１２】
なお、電子計算機の演算速度が十分に高速であるならば、ＡＬＬモードとすることもできる。図１３は、ＡＬＬモードの場合での対応付けインデックスＩを特定するフローチャートであって、画像表示プログラムでは、まず、ｄminの値として取り得る最大値を代入しておく（ステップS501）。
【０１１３】
次いで、画像表示プログラムでは、作業用の対応付けインデックスＱを漏れなく想定するために作業用の対応付けインデックスＱを生成するための補助パターンを生成する（ステップS502）。
【０１１４】
補助パターンの生成は、スキャンラインSA中の空間座標点の数をＭ、スキャンラインSB中の空間座標点の数をＮとして、画像表示プログラムでは、Q1〜QN-1のうち、Ｍ−１個の要素を「１」とし、他を「０」となる補助パターンを生成している。
【０１１５】
具体的に説明すると、例えば、Ｍ＝４，Ｎ＝６の場合、「０００１１１」の補助パターンが生成されることとなる。また、「０００１１１」以外にも、「００１０１１」、「００１１０１」、「００１１１０」、「０１００１１」、「０１０１０１」、「０１０１１０、「０１１００１」、「０１１０１０」、「０１１１００」の10通りがある。
【０１１６】
画像表示プログラムでは、いずれか１つの補助パターンに対して、整数変数ｉを「２」として（ステップS503）、終了条件を満たしていなければ（ステップS504：NO）、作業用の対応付けインデックスＱの項QiにQi-1＋Qiの値を代入して（ステップS505）、整数変数ｉをインクリメントすることにより（ステップS506）、作業用の対応付けインデックスＱを生成している。例えば、補助パターンが「０００１１１」の場合であれば、「０００１２３」という作業用の対応付けインデックスＱを生成できる。
【０１１７】
このようにして生成した作業用の対応付けインデックスＱを用いて、画像表示プログラムでは、スキャンラインSAとスキャンラインSBの間に、作業用の対応付けインデックスＱに基づいて設けられる仮想線の長さの総和Distance(SA,SB,Q)を計算して、仮想線の長さの総和ｄとする（ステップS507）。
【０１１８】
そして、仮想線の長さの総和ｄが、ｄminの値よりも小さい場合には（ステップS508：YES）、画像表示プログラムでは、仮想線の長さの総和ｄを新たなｄminとし、作業用の対応付けインデックスＱを対応付けインデックスＩとする（ステップS509）。
【０１１９】
画像表示プログラムでは、この処理を全ての補助パターンに対して行うことにより（ステップS510）、全ての仮想線の組み合わせの中で仮想線の長さの総和が最小となる対応付けインデックスＩを特定できる。
【０１２０】
上述した実施形態で示した画像表示プログラムのフローチャートは一例であって、本発明は上述したフローチャートに限定されるものではなく、必要に応じて所要のフローチャートに組み替えてもよい。
【符号の説明】
【０１２１】
10  ディスプレイ
20  電子計算機
21  ＣＰＵ
22  記憶装置
23  メモリ装置
24  バス
25  グラフィックボード
26  ディスプレイ用ケーブル
【図１】
2010257261.tif 000003
【図２】
2010257261.tif 000004
【図３】
2010257261.tif 000005
【図４】
2010257261.tif 000006
【図５】
2010257261.tif 000007
【図６】
2010257261.tif 000008
【図７】
2010257261.tif 000009
【図８】
2010257261.tif 000010
【図９】
2010257261.tif 000011
【図１０】
2010257261.tif 000012
【図１３】
2010257261.tif 000013
【図１４】
2010257261.tif 000014
【図１１】
2010257261.tif 000015
【図１２】
2010257261.tif 000016
【図１５】
2010257261.tif 000017