(57)【要約】【課題】  本発明は、経路などの地理的特徴の遮蔽が回避された投影図を、比較的に高速で生成しうるシステムを提供するものである。【解決手段】  処理部１は、以下の処理を行う：（１）３次元地形モデルから、遮蔽に関係している可能性のある部分における地理特徴を表す特徴点を抽出する処理；（２）ある視点から見たときの２次元投影面上において、前記特徴点の最適配置を算出する処理；（３）前記２次元投影面上における前記特徴点の最適配置を満たす３次元地形形状を生成する処理；（４）前記３次元形状を、前記視点又はその近傍から見たときの２次元投影図を生成する処理。【特許請求の範囲】
【請求項１】
処理部を備え、前記処理部は、以下の処理を行うことを特徴とする投影図生成システム：
（１）３次元地形モデルから、遮蔽に関係している可能性のある部分における地理特徴を表す特徴点を抽出する処理；
（２）ある視点から見たときの２次元投影面上において、前記特徴点の最適配置を算出する処理；
（３）前記２次元投影面上における前記特徴点の最適配置を満たす３次元地形形状を生成する処理；
（４）前記３次元形状を、前記視点又はその近傍から見たときの２次元投影図を生成する処理。
【請求項２】
さらに記憶部を備え、前記記憶部は、前記３次元地形モデルを記憶しており、
前記処理部は、前記記憶部から前記３次元地形モデルを取得する構成となっており、
前記処理部は、生成された前記２次元投影図を前記記憶部に格納する構成となっている
ことを特徴とする、請求項１に記載の投影図生成システム。
【請求項３】
請求項１又は２に記載の投影図生成システムと、表示部とを備え、前記表示部は、前記２次元投影図を表示する構成となっていることを特徴とする投影図表示システム。
【請求項４】
前記処理部は、前記視点の移動に対応して、前記（１）〜（４）の処理を行うことにより、異なる時点における２次元投影図を生成する構成となっており、
ある時点における２次元投影図を生成する場合において、次の条件を満たす特徴点が存在する場合には、それを、前記（１）の処理における特徴点として用いることを特徴とする、請求項１〜３のいずれか１項に記載の投影図生成システム：
（条件）
前記ある時点より前に生成した２次元投影図で用いた特徴点であって、それが、前記ある時点の２次元投影図におけるビューボリューム内に存在すること。
【請求項５】
前記特徴点の最適配置とは、前記ある視点から見たときの２次元投影面上において、道路上における特徴点を結ぶ線の遮蔽が回避され、かつ、各特徴点の相対位置関係が保持された状態であることを特徴とする、請求項１〜４のいずれか１項に記載の投影図生成システム。
【請求項６】
前記（１）の処理における、前記特徴点の抽出を、以下の処理により行うことを特徴とする、請求項１〜５のいずれか１項に記載の投影図生成システム：
（ａ）参照点を通る水平面に対して、ある一定の角度で傾斜する方向に視点を置く処理；
（ｂ）前記３次元地形モデルから得られる３次元の地形形状に対する、前記視点の位置を、前記参照点を中心とし、かつ水平な方向に、相対的に回転移動させるときに、前記３次元の地形形状の輪郭線上に乗る頂点をすべて特徴点として抽出する処理。
【請求項７】
以下のステップを備えることを特徴とする、投影図生成方法：
（１）３次元地形モデルから、遮蔽に関係している可能性のある部分における地理特徴を表す特徴点を抽出するステップ；
（２）ある視点から見たときの２次元投影面上において、前記特徴点の最適配置を算出するステップ；
（３）前記２次元投影面上における前記特徴点の最適配置を満たす３次元地形形状を生成するステップ；
（４）前記３次元形状を、前記視点又はその近傍から見たときの２次元投影図を生成するステップ。
【請求項８】
請求項７に記載のステップをコンピュータに実行させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、投影図生成システムに関するものである。
【背景技術】
【０００２】
カーナビゲーションシステムは、近年目覚しい発展を遂げ、鳥瞰図による3次元表示が機能として備わり、ユーザーが、実際の景観との対応付けを容易に行えるようになった。その一方で、透視投影を用いて3次元地形形状を立体的に表示すると、探索された経路が建物や地形の起伏などに遮蔽され、運転に必要な情報を伝えることができない問題が生じる。【０００３】
この問題は、商用のカーナビゲーションシステムでは、遮蔽物を透明に表示するなどして対応しているが、遮蔽が幾重にも重なった状況では、注目している経路や地理特徴も重なってしまい、それらの相対的位置関係が伝わりにくい。そのため、このような遮蔽の問題を抜本的に解決するためには、透視投影の法則を崩すことで、道路や地理特徴を投影図上に適切に配置し、ユーザに提示する必要がある。このような透視投影を崩した投影を、ここでは非透視投影と呼ぶ。【０００４】
非透視投影の研究においては、いくつかの手法が提案されてきている。透視投影の画像を2次元的な変換を用いてゆがめることにより、異なる視点からの投影の効果をあわせた投影を作り出す手法[非特許文献4,8]や曲がった投影線により透視投影を崩す方法[非特許文献2]、指定したカメラパスから見たようなセルアニメーションの背景画に使われるパノラマ画像を作成する手法[非特許文献7]、個々の独立した物体を別々の視点から描画し、奥行きを考慮して2次元画面上で合成する手法[非特許文献1]などが提案されてきた。その中で、3次元モデルを変形することにより非透視投影の表現能力を向上させる手法が近年考案された[非特許文献3,5,6]。3次元モデルの変形を用いることで、多様な非透視投影を表現することが可能となる。【０００５】
しかしながら、非特許文献3,5,6に記載の技術においても、3次元空間におけるモデルの変形から、2次元投影面における振る舞いを直接把握することは難しい。このため、実際に得られた２次元投影面において経路の遮蔽が回避されているかどうかが確認し難い。遮蔽を生じている時に再計算を行うとすれば、計算量や計算時間の増加を招く。特に、２次元投影面をフレームとして連続して表示することによりアニメーションを生成しようとすると、多数の画像を連続的に生成する必要があるので、この問題はさらに顕著になる。
【非特許文献１】M. Agrawala, D. Zorin, and T. Munzner. Artistic multiprojection rendering. In Eurographics Rendering Workshop 2000, pages 125-136, 2000.
【非特許文献２】Y. Kurzion and R. Yagel. Interactive space deformation with hardware-assisted rendering. IEEE Computer Graphics & Applications, 17(5): 66-77, 1997.
【非特許文献３】P. Rademacher. View-dependent geometry. In Computer Graphics (Proceedings of Siggraph '99), pages 439-446, 1999.
【非特許文献４】S. M. Seitzand C. R. Dyer. View morphing. In Computer Graphics (Proceedings of Siggraph '96), pages 21-30, 1996.
【非特許文献５】K. Singh. A fresh perspective. In Proceedings of Graphics Interface 2002, pages 17-24, 2002.
【非特許文献６】S. Takahashi, N. Ohta, H. Nakamura, Y. Takeshima, and I. Fujishiro. Modeling surperspective projection of landscapes for geographical guide-map generation. Computer Graphics Forum, 21(3): 259-268, 2002.
【非特許文献７】D. N. Wood, A. Finkelstein, J. F. Hughes, S. E. Thayer, and D. H. Salesin. Multiperspective panoramas for cel animation. In Computer Graphics (Proceedings of Siggraph '97), pages 243-250, 1997.
【非特許文献８】D. Zorin and A. H. Barr. Correction of geometric perceptual distortions in pictures. In Computer Graphics (Proceedings of Siggraph '95), pages 257-264, 1995.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、前記の状況に鑑みてなされたもので、経路などの地理的特徴の遮蔽が回避された投影図を、比較的に高速で生成しうるシステム、方法、又はコンピュータプログラムを提供しようとするものである。本発明の他の目的は、生成された２次元投影図を表示するシステムを提供することである。
【課題を解決するための手段】
【０００７】
本発明に係る投影図生成システムは、処理部を備えている。前記処理部は、以下の処理を行う構成となっている：
（１）３次元地形モデルから、遮蔽に関係している可能性のある部分における地理特徴を表す特徴点を抽出する処理；
（２）ある視点から見たときの２次元投影面上において、前記特徴点の最適配置を算出する処理；
（３）前記２次元投影面上における前記特徴点の最適配置を満たす３次元地形形状を生成する処理；
（４）前記３次元形状を、前記視点又はその近傍から見たときの２次元投影図を生成する処理。【０００８】
本発明の投影図生成システムは、さらに記憶部を備えていてもよい。前記記憶部は、前記３次元地形モデルを記憶している。この場合、前記処理部は、前記記憶部から前記３次元地形モデルを取得する構成となっている。さらに、前記処理部は、生成された前記２次元投影図を前記記憶部に格納する構成となっている。【０００９】
本発明に係る投影図表示システムは、前記した投影図生成システムと、表示部とを備えている。前記表示部は、前記２次元投影図を表示する構成となっている。【００１０】
前記投影図生成システムにおいて、前記処理部は、前記視点の移動に対応して、前記（１）〜（４）の処理を行うことにより、異なる時点における２次元投影図を生成する構成であってもよい。また、前記処理部は、ある時点における２次元投影図を生成する場合において、次の条件を満たす特徴点が存在する場合には、それを、前記（１）の処理における特徴点として用いる構成であっても良い：
（条件）
前記ある時点より前に生成した２次元投影図で用いた特徴点であって、それが、前記ある時点の２次元投影図におけるビューボリューム内に存在すること。【００１１】
前記投影図生成システムにおける特徴点の最適配置とは、例えば、前記ある視点から見たときの２次元投影面上において、道路上における特徴点を結ぶ線の遮蔽が回避され、かつ、各特徴点の相対位置関係が保持された状態である。【００１２】
前記（１）の処理における、前記特徴点の抽出は、例えば以下の処理により行うことができる：
（ａ）参照点を通る水平面に対して、ある一定の角度で傾斜する方向に視点を置く処理；
（ｂ）前記３次元地形モデルから得られる３次元の地形形状に対する、前記視点の位置を、前記参照点を中心とし、かつ水平な方向に、相対的に回転移動させるときに、前記３次元の地形形状の輪郭線上に乗る頂点をすべて特徴点として抽出する処理。【００１３】
本発明に係る投影図生成方法は、以下のステップを備えている：
（１）３次元地形モデルから、遮蔽に関係している可能性のある部分における地理特徴を表す特徴点を抽出するステップ；
（２）ある視点から見たときの２次元投影面上において、前記特徴点の最適配置を算出するステップ；
（３）前記２次元投影面上における前記特徴点の最適配置を満たす３次元地形形状を生成するステップ；
（４）前記３次元形状を、前記視点又はその近傍から見たときの２次元投影図を生成するステップ。【００１４】
本発明に係るコンピュータプログラムは、前記した投影図生成方法におけるステップをコンピュータに実行させるためのものである。
【発明の効果】
【００１５】
本発明によれば、経路などの地理的特徴の遮蔽が回避された投影図を、比較的に高速で生成しうるシステム、方法、又はコンピュータプログラムを提供することができる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の第１実施形態を、添付図面を参照して説明する。【００１７】
（第１実施形態の構成）
本実施形態に係る投影図生成システムは、図１に示されるように、処理部１と、記憶部２と、表示部３と、通信路４とを備えている。【００１８】
処理部１は、例えばＣＰＵにより構成することができる。【００１９】
処理部１は、以下の処理を行う構成となっている。
（１）３次元地形モデルから、遮蔽に関係している可能性のある部分における地理特徴を表す特徴点を抽出する処理；
（２）ある視点から見たときの２次元投影面上において、前記特徴点の最適配置を算出する処理；
（３）前記２次元投影面上における前記特徴点の最適配置を満たす３次元地形形状を生成する処理；
（４）前記３次元形状を、前記視点又はその近傍から見たときの２次元投影図を生成する処理。【００２０】
これらの処理の詳細は、本実施形態の動作として後述する。また、これらの処理は、計算機（又はＣＰＵ）上で実行されるコンピュータソフトウエアにより実施することができる。【００２１】
記憶部２は、処理部１での処理に用いられる３次元地形モデルや、処理部１を動作させるために必要なコンピュータソフトウエアや、処理部１で生成された３次元地形形状や、２次元投影図など、必要なデータ（情報）を記憶できるようになっている。記憶部２は、内部記憶装置あるいは外部記憶装置により構成することができる。【００２２】
処理部１は、記憶部２から３次元地形モデルを取得する構成となっている。また、処理部１は、生成された３次元地形形状や２次元投影図を記憶部２に格納する構成となっている。【００２３】
表示部３は、処理部１で生成された２次元投影図を表示する構成となっている。表示部３としては、例えばディスプレイである。【００２４】
通信路４は、処理部１と記憶部２と出力部３との間における、情報のやりとりを可能にする媒体である。通信路４は、例えば、コンピュータ内のバスラインであるが、ＬＡＮやインターネットなどのネットワークであってもよい。すなわち、処理部１と記憶部２と出力部３とは、物理的に離間した位置にあり、ネットワークによって接続されたものであっても良い。ネットワークに接続するための手段、例えばインタフェースの構成やプロトコルは良く知られているので、詳細な説明は省略する。【００２５】
（第１実施形態の動作）
次に、前記したシステムを用いて２次元投影図を生成する方法について、図２のフローチャートを参照しながら説明する。このシステムは、カーナビゲーションシステムとして実装されている。このシステムで用いる３次元地形モデルは、一価関数で表現されると仮定する。一価関数とは、この実施形態では、例えば緯度と経度とが決まると標高が一意に定まるような関数をいう。【００２６】
本実施形態のシステムは、進むべき経路が与えられたときに、図３に示されるような鳥瞰図のアニメーションを生成する。本システムでは、視点の俯角として、一般的なカーナビのように20度から70度の値をとることができるが、ここでは遮蔽回避の効果が最もよく確認できるように、俯角を30度に設定した例を示す。【００２７】
本システムにおいて、 生成する各フレームにおいて経路の遮蔽が生じている部分は、 それが回避されるように投影図が変換されるが、それ以外は透視投影図の状態をできる限り保つように非透視投影図を作成する。図３は実装したシステムによって得られたスナップショットであり、球が現在地を、色の濃い線（太線）が経路としての道路を、色の薄い線が経路でない（つまり進むべき道ではない）道路を表している。図(a)は、経路の一部が遮蔽された透視投影図、図(b)は、経路の遮蔽が回避された非透視投影図の表示例である。【００２８】
本実施形態の手法における、運転経路の遮蔽を回避するアイデアは、簡単に述べれば、つぎのようなものである。もし、投影面上において、図４(a)のように、山の輪郭線５が道路６の上にあり遮蔽が生じてしまう場合に、図４(b)のように、山の輪郭線５が道路６と交差しない２次元投影図を生成する。このような変更は、山や道路などの地理特徴から特徴点を取り出し、それらの配置を投影面上で変更し、その変換を地形形状に反映させることにより行うことができる。以下、詳しく説明する。なお、図４において、符号Ｆ１は道路の特徴点、符号Ｆ２は地形の特徴点を示す。【００２９】
（図２のステップＳａ−１）
このステップでは、遮蔽に関係している可能性のある部分における地理特徴を表す特徴点を、３次元地形モデルから、処理部１によって抽出する。具体的にどこを特徴点とするか、どれだけ多くの特徴点を抽出するかは、求める２次元投影図の精度や用いるコンピュータの制約などによって決まる。一般には、カーナビゲーションシステムであれば、山の頂点近傍の点や、道路形状を再現するための点が選ばれる。さらに、建物の輪郭を再現するための点（頂点や屈曲点）を特徴点としてもよい。【００３０】
本実施形態では、地形曲面の輪郭線から、山の頂点Ｆ２１や、谷の底、これらの端点Ｆ２２、 輪郭線同士の交差点Ｆ２３（図５(a)参照）を特徴点として抽出する。この抽出は、視点の情報と、３次元地形モデルの標高の情報とを用いて、容易に算出できる。このような算出の方法は、従来から知られているので、詳細な説明は省略する。【００３１】
さらに、本実施形態では、道路からも、曲率が極大となる点Ｆ１１、端点Ｆ１２、交差点Ｆ１３、変曲点Ｆ１４（図５(b)）を特徴点として取り出す。これらの特徴点を結ぶことで、道路形状を荒く近似することが可能となる。なお、通常のカーナビゲーションシステムでは、道路の情報を、地形曲面の情報とは別に、２次元情報として持っていることも多いが、本実施形態では、この２次元情報も、３次元地形モデルに概念的に含まれるものとして説明する。つまり、３次元地形モデルは、２次元情報を含めた複数の情報の寄せ集めであってもよい。【００３２】
ここで、本実施形態では、３次元地形モデルの全体における地形上および道路上の特徴点を用いる必要はなく、ビューボリューム内にある特徴点のみを選んで使用すればよい。【００３３】
さらに、図５(b)に例示された道路上の特徴点は、運転経路上の特徴点、および、交差点の周囲の道路上の特徴点に限定してもよい。遮蔽回避を行うためには、経路としての道路における特徴点（直線で結ぶことにより道路を近似できる点）のみで十分である。しかし、交差点の周囲の道路において特徴点を抽出することにより、交差点周囲における道路形状がゆがまないようにすることができる。【００３４】
システムにより自動的に抽出された特徴点の例を図６に示す。図中黒い点（四角い点）が特徴点である。なお、本実施形態では、特徴点は、座標の情報により特定される。抽出された特徴点の情報も記憶部２に格納される。【００３５】
（図２のステップＳａ−２）
このステップでは、ある視点から見たときの、２元投影面上における特徴点の最適配置を、ばねモデルを用いて求める。ここでの最適配置とは、道路の遮蔽を回避しつつ、元の透視投影をできる限り保持する配置のことを意味する。道路の遮蔽を回避するとは、本実施形態では、道路上の特徴点を結ぶ線の遮蔽を回避することである。元の透視投影をできる限り保持するとは、本実施形態では、特徴点の相対的位置関係を保持することである。【００３６】
このような最適配置は、遮蔽が完全に回避された特徴点の位置関係を求め、その位置関係から、透視投影における特徴点の配置へ、例えばばねモデルを用いて近づけることで、求めることができる。このステップでの処理は、２次元投影面での表示状態を前提にして行われる。【００３７】
まず、遮蔽が完全に回避された位置関係として、特徴点を水平面に投影した位置{qi}(i=1,...,n)(図７(c)参照)を用いる(nは特徴点の数)。これは、地形形状が一価関数であると仮定しているため、水平面上に射影すれば必ず遮蔽が生じないことが保障されるからである。【００３８】
次に、その配置から、透視投影での特徴点の配置{pi}(i=1,...,n)(図７(a)参照)にできる限り近づけるために、以下のようにばねモデルを構築する。なお、このモデルで用いられるばねの意味はあくまで、計算機で計算するための仮想的なものである。【００３９】
まず、図７（ｃ）の特徴点配置に対し、Delaunay三角形分割を施し（図８(a)参照）、それぞれの辺の端点に、各特徴点の相対位置関係を保持するばねを付ける。さらに、各特徴点qiが、対応する透視投影の位置piに近づくように、piとqiの間にもばねをつける。このばねモデルの平衡状態として、特徴点の最適配置(図７(b))を求める。ここで、最適化の処理中に、特徴点間を結ぶ辺が交差しないようにチェックすることで、道路の特徴点とそれに接続する地形上の特徴点の相対位置関係が変わらないようにすることができ、遮蔽が回避された特徴点配置を得ることができる（図８(b)参照）。【００４０】
本実施形態の実装では、各特徴点に働くばねの力を以下のように定式化した。
2006134962.tif 000002
【００４１】
式（１）中、Fiがインデックスiの特徴点に働く力であり、AはDelaunay三角形分割で隣接している特徴点のインデックスの集合、Rが道路上の、Tが地形上の特徴点のインデックスの集合である。また、式（１）中、ｘは、特徴点の位置であり、ばねモデルが平衡状態に達するとその値は図７（ｂ）のｒに収束する。右辺の第1項が透視投影に近づける力、第2項が相対位置関係を保持するための力である。さらに、第3項は、道路上の特徴点と地形上の特徴点の間の斥力として働く。この斥力は、道路と山などのそれぞれの地理特徴が、投影図上でお互い干渉しあうことなくなるべく離れて配置されるように導入されている。【００４２】
（ステップＳａ−３）
このステップでは、前記ステップＳａ−２で求めた、2次元投影面上での特徴点の最適配置を満たすように、特徴点の位置（３次元空間での位置）を求める。この特徴点の位置を、３次元空間における制約として、３次元地形モデルを変形する。これにより、２次元投影面上において求められた特徴点の配置を満たす３次元地形形状を生成することができる。【００４３】
ただし、２次元投影面上の特徴点配置からだけでは、3次元空間における特徴点位置の、奥行き方向での位置までは決めることができない。本実施形態では、図９に示されるように、変形前と変形後とにおいて、「スクリーンＳ（投影面）から、３次元地形モデル上の特徴点Ｆ２４までの距離が変化しないように」変換している。このようにすることで、変形後の地形上の特徴点の位置Ｆ２４１（３次元空間での位置）が定まるので、その位置を幾何的制約として地形モデルに変形を加える。なお、ここで、スクリーンＳの上に投影される特徴点に、符号Ｆ２４Ｓ及び符号Ｆ２４１Ｓを付している。【００４４】
本実施形態では、より具体的には、変形前後の地形形状の差分を、ガウス関数などを用いた単峰形をなす基底関数の線形和により表現し、地形上の特徴点の位置制約から得られる連立方程式を解くことにより、差分形状を求めることができる。このように差分形状を考えることで、 地形曲面に本来存在する高周波成分の起伏を保持したまま、 変形を施すことができる。このような基底関数を用いた変形操作は、それ自体としてはよく知られているので、詳細な説明を省略する。【００４５】
このステップにおいても、特徴点の抽出の場合と同様に、変形領域を限定して効率化を行うことができる。実際には、急激なカメラのパンに対応するために、投影面を2倍程度のサイズとしたときのビューボリュームの範囲で変形を行うことが好ましい。図１０は、通常の視点より遠くから見たものであり、黒い点で表された範囲が、実際に変形される領域を示している。【００４６】
（ステップＳａ−４）
前記のようにして生成した３次元地形形状を視点から見ることで、個々の静的な非透視投影図（２次元投影図）を生成することができる。すなわち、遮蔽が回避された２次元投影図を得ることができる。得られた２次元投影図においては、基本的に、遮蔽が回避されているので、遮蔽回避のための再計算は原則として不要となる。したがって、本実施形態では、比較的高速に、遮蔽が回避された２次元投影図を得ることができる。得られた静的な非透視投影図（２次元投影図）を表示部３に表示することも可能である。【００４７】
さらに、処理部１は、視点の移動に対応して、前記した各ステップの処理を行うことにより、異なる時点における２次元投影図を生成することができる。これらの図を連続して表示すれば、経路に沿って（つまり視点の変化に対応して）、表示が変化していくアニメーション（動画）を表示することができる。この表示は、本実施形態の例では、表示部３により行うことができる。【００４８】
ただし、前記のステップで生成した図をコマ送りしても、時間に関するコヒーレンスを保持したアニメーションは生成できない。このようなコヒーレンスを保持するために、本実施形態では、2つの処理を施す。【００４９】
まず、フレーム間において、可能な限り同一の特徴点を選択する。これは、前フレームで用いられていた地理特徴点が、現在のフレームでもビューボリューム内に存在していれば、そのまま同じ特徴点を用いるようにすることで、実現される。【００５０】
つまり、ある時点における２次元投影図を生成する場合において、次の条件を満たす特徴点が存在する場合には、それを、ステップＳａ−１の処理における特徴点として用いる。
（条件）
ある時点より前に生成した２次元投影図で用いた特徴点であって、それが、ある時点の２次元投影図におけるビューボリューム内に存在すること。【００５１】
図１１は、連続したフレームで特徴点が取られた様子を示している。図(a)は、特徴点の再利用を行っていないものであり、フレームが１つ進むことでまったく異なる特徴点が選ばれていることが確認できる。なお、この図では、時間軸は、図中の上から下に進むものとする。図(b)から分かるように、特徴点の再利用を行うことにより、特徴点の不均一によって生じる変形の差異もなくなっている。【００５２】
さらに、前後複数のフレームにおいて求められる変形を表す差分形状を平滑化することで、フレーム間コヒーレンスをより保つこともできる。例えば、現在のフレームを中心としたガウス関数から求めた各フレームの重みによって、前後各4フレームについて平滑化を行うこともできる。【００５３】
（実験例１）
実際の地形、道路のデータをもとに、前記した本実施形態の方法により、非透視投影のアニメーションを生成した。1フレームあたりの計算時間は、CPU  3.0GHz  Pentium（登録商標）4、メモリ  2GB  RAMで、およそ3秒である。【００５４】
結果の一部を抜き出したものが図３（ｂ）である。同図（ａ）は、透視投影の図である。本実施形態によれば、経路を投影図上で適切に配置することで、不必要な遮蔽を回避することができる。【００５５】
なお、前記各実施形態の記載は単なる一例に過ぎず、本発明に必須の構成を示したものではない。各部の構成は、本発明の趣旨を達成できるものであれば、上記に限らない。【００５６】
例えば、前記実施形態では、ステップＳａ−２において、特徴点の最適配置を求める手法としてばねモデルを用いた。しかしながら、このような手法としては、他に、特徴点間の間に働く力を原子間の力に近似させるパーティクルなど、種々のものが存在する。パーティクル自体はよく知られた方法である。要するに、特徴点の最適配置を求めることが可能な手法であれば具体的な内容は限定されない。【００５７】
また、前記実施形態では、道路の遮蔽を防ぐ手法を説明したが、道路以外の特徴、例えば建物や地理的目印の遮蔽を防止することもできる。この場合は、遮蔽を防ぎたい対象物の輪郭上に特徴点を配置すればよい。【００５８】
（第２実施形態の構成及び動作）
前記した第１実施形態のステップＳａ−１（図２参照）では、地形曲面の輪郭線から、山の頂点Ｆ２１や、谷の底、これらの端点Ｆ２２、 輪郭線同士の交差点Ｆ２３（図５(a)参照）を特徴点として抽出した。この抽出は、視点の情報と、３次元地形モデルの標高の情報とを用いて行った。【００５９】
第２実施形態における特徴点の抽出は、以下のようにして行われる。本実施形態でも、地形曲面の輪郭線から、山の頂点や、谷の底、これらの端点、輪郭線同士の交差点（図１２参照）を特徴点として抽出することは、前記第１実施形態と基本的に同様である。ただし、第２実施形態における特徴点の抽出は、対象となる地形曲面を取り囲むように視点Ｐを移動して、複数の視点位置において行う。視点Ｐの移動軌跡に符号Ｒを付した。そして、各視点位置で得られる特徴点集合の和をとり、その和集合全体を視点位置に依存しない特徴点の集合として地形曲面の特徴点として用いていく。地形曲面から輪郭線やその上の特徴点を抽出する方法は、従来から知られているので、詳細な説明は省略する。また、このような地形曲面上の特徴点は、あらかじめ抽出しておいて、地形曲面データと一緒に入力として読み込むようにすることができる。【００６０】
すなわち、本実施形態による特徴点の抽出は、以下の処理により行われる：
（ａ）参照点を通る水平面に対して、ある一定の角度で傾斜する方向に視点Ｐを置く処理。ここで、ある一定の角度とは、特に限定されないが、一般的なカーナビゲーションシステムの場合、２０°〜７０°の範囲である。また、参照点とは、視点Ｐから常に参照されている点であり、例えばカーナビゲーションシステムの場合は、自車の位置である。
（ｂ）３次元地形モデルから得られる３次元の地形形状に対する、視点の位置を、参照点を中心とし、かつ水平な方向に相対的に回転移動させるときに、３次元の地形形状の輪郭線上に乗る頂点をすべて特徴点として抽出する処理。ここで、頂点とは、３次元地形モデルを構成する多面体の頂点を意味する。また、参照点を中心とした視点の相対的な回転角度は、一般的には全周（３６０°）である（図１２参照）。また、視点の相対的な移動方法としては、連続的に移動させても良いが、通常は、１５°〜３０°程度の角度毎に、離散的に移動させることが好ましい。要するに、視点の移動方法としては、実質的に必要な頂点を抽出できるものであればよい。【００６１】
また、本実施形態でも、道路から、曲率が極大となる点、端点、交差点（図５(b)）を特徴点として取り出す。【００６２】
第２実施形態のシステムにより自動的に抽出された特徴点の例を図１３に示す。図中黒い点（四角い点）が特徴点である。【００６３】
また、前記した第１実施形態のステップＳａ−２では、特徴点を水平面に投影した位置{qi}(i=1,...,n)(図７(c)参照)から、透視投影での特徴点の配置{pi}(i=1,...,n)(図７(a)参照)にできる限り近づけるために、ばねモデルを用いた。この点は、第２実施形態でも基本的に同様であるが、第２実施形態では、つぎのような方法を用いる。【００６４】
第２実施形態においても、特徴点を水平面に投影した位置{qi}(i=1,...,n)(図７(c)参照)から、道路の遮蔽を回避しつつ透視投影の配置{pi}(i=1,...,n)(図７(a)参照)にできる限り近づけるためのばねモデルを構築する。ただし、第２実施形態では、特徴点の最適配置を求める処理において、各特徴点はそれぞれ投影面上で{qi}(i=1,...,n)と{pi}(i=1,...,n)を結んだ直線上を移動することにし、計算を簡単にしている。【００６５】
特徴点の最適配置の計算は２つの段階を踏んで行われる。まず、図７（ｃ）の特徴点配置に対し、Delaunay三角形分割を施し（図１４（ａ）（ｂ）参照）、それぞれの辺の端点に、各特徴点の相対位置関係を保持するばねを付ける。さらに、各特徴点qiが、対応する透視投影の位置piに近づくように、piとqiの間にもばねをつける。このばねモデルの平衡状態として、特徴点の最適配置(図７(b))を求める。この際、第２実施形態では、道路の遮蔽の原因となる特徴点間を結ぶ辺の交差を許した状態で、道路上の特徴点の最適配置だけを先に決定することにする(図１５（ａ）（ｂ）参照)。【００６６】
このあと、道路の特徴点の位置を固定した状態で、特徴点間を結ぶ辺の交差を避けるように地形曲面上の特徴点の位置を移動して、その交差を避けるようなかたちで再度ばねモデルによる計算をおこない、地形曲面上の特徴点の最適配置を計算する(図１６（ａ）（ｂ）参照)。結果として、遮蔽が回避された特徴点配置を得ることができる。【００６７】
さらに、前記した第１実施形態のステップＳａ−３では、変形前後の地形形状の差分を、ガウス関数などを用いた単峰形をなす基底関数の線形和により表現し、地形上の特徴点の位置制約から得られる連立方程式を解くことにより、差分形状を求めることとしている。【００６８】
第２実施形態においては、変形前後の地形形状の差分を、B-スプライン関数を用いた単峰形をなす基底関数の線形和により階層的に表現し、地形上の特徴点の位置制約を粗いB-スプライン近似から順次細かいB-スプライン近似を施す。これにより、特徴点の位置制約をみたす差分形状を高速に求めることができる。このように差分形状を考えることで、地形曲面に本来存在する高周波成分の起伏を保持したまま、変形を施すことができる。このような基底関数を用いた変形操作は、以下の論文に示されるように、既に知られているので、詳細な説明を省略する。
S. Lee, G. Wolberg, and S. Y. Shin, "Scattered Data Interpolation with Multilevel B-Splines," IEEE Transactions on Visualization and Computer Graphics, Vol. 3, No. 3, pp. 228--244, 1997.【００６９】
さらに、第１実施形態のステップＳａ−４では、時間に関するコヒーレンスを保持するために、フレーム間において、可能な限り同一の特徴点を選択する等の処理を行った。しなしながら、第２実施形態では、このような処理は必要ではない。【００７０】
第２実施形態における、前記した以外の構成及び利点については、第１実施形態と同様なので、説明を省略する。【００７１】
（実験例２）
実際の地形、道路のデータをもとに、前記した第２実施形態の方法により、非透視投影のアニメーションを生成した。実験条件としては、実験例１と同様、CPU  3.0GHz  Pentium（登録商標）4、メモリ  2GB  RAMとした。この場合、1フレームあたりの計算時間は、およそ0.5-1.0秒であった。すなわち、第２実施形態の方法により、処理の高速化を達成できることが判る。第２実施形態では、第１実施形態と異なり、特徴点を、視点に依存しない状態で抽出できる。このため、視点の移動の際に、特徴点抽出のための再計算を行う必要がない。これにより、処理が高速化していると考えられる。【００７２】
なお、各実施形態を実現するための各部（機能ブロックを含む）の具体的手段は、ハードウエア、ソフトウエア、ネットワーク、これらの組み合わせ、その他の任意の手段を用いることができ、このこと自体は当業者において自明である。また、機能ブロックどうしが複合して一つの機能ブロックに集約されても良い。さらに、機能ブロックが複数のハードウエアまたはソフトウエアの協働によって実現されても良い。
【図面の簡単な説明】
【００７３】
【図１】本発明の第１実施形態に係る投影図生成システムの概略的な構成を示すブロック図である。
【図２】本発明の第１実施形態に係る投影図生成方法を説明するためのフローチャートである。
【図３】図（ａ）は、経路の一部が山によって隠された透視投影図の例である。図（ｂ）は、経路の遮蔽が回避された状態における非透視投影図の例である。
【図４】図（ａ）は、経路（道路）の遮蔽が生じる特徴点の配置を模式的に示す図である。図（ｂ）は、特徴点の配置を変換することにより遮蔽が回避された状態を模式的に示す図である。
【図５】図（ａ）は、地形上の特徴点を示す説明図である。図（ｂ）は、道路上の特徴点を示す説明図である。
【図６】システムにより抽出された特徴点の例を示すもので、図（ａ）は地形上の特徴点、図（ｂ）は道路上の特徴点を示している。
【図７】特徴点の配置を説明するための説明図であり、図(a)は透視投影図上の配置、図(b)は最適配置、図(c)は水平面に射影した配置を表している。
【図８】特徴点のDelaunay三角形分割を説明するための説明図であり、図(a)は最適化前、図(b)は最適化後の状態を示している。
【図９】投影面上の最適配置を満たすような、特徴点の3次元空間における移動を説明するための説明図である。
【図１０】変形領域の制限範囲（黒い点で表された範囲）を示す説明図であって、図(a)はワイヤーフレーム表示の例、図(b)はサーフェス表示の例である。
【図１１】特徴点の取られ方を説明するための説明図であって、図(a)は特徴点の再利用なし、図(b)は再利用ありの例である。
【図１２】第２実施形態における、地形上の特徴点を示す説明図である。
【図１３（ａ）】第２実施形態のシステムにより抽出された地形上の特徴点の例を示す図である。
【図１３（ｂ）】第２実施形態のシステムにより抽出された道路上の特徴点の例を示す図である。
【図１４（ａ）】特徴点のDelaunay三角形分割を説明するための説明図であり、図（ａ）は最適化前の状態を示している。
【図１４（ｂ）】特徴点のDelaunay三角形分割を説明するための説明図であり、図（ｂ）は図（ａ）の拡大図である。
【図１５（ａ）】特徴点のDelaunay三角形分割を説明するための説明図であり、図（ａ）は道路上における特徴点の最適配置を計算した例を示している。
【図１５（ｂ）】特徴点のDelaunay三角形分割を説明するための説明図であり、図（ｂ）は図（ａ）の拡大図である。
【図１６（ａ）】特徴点のDelaunay三角形分割を説明するための説明図であり、図（ａ）は最適化後の状態を示している。
【図１６（ｂ）】特徴点のDelaunay三角形分割を説明するための説明図であり、図（ｂ）は図（ａ）の拡大図を示している。
【符号の説明】
【００７４】
１  処理部
２  記憶部
３  表示部
４  通信路
５  山の輪郭線
６  道路
【図１】
2006134962.tif 000003
【図２】
2006134962.tif 000004
【図４】
2006134962.tif 000005
【図５】
2006134962.tif 000006
【図７】
2006134962.tif 000007
【図９】
2006134962.tif 000008
【図３】
2006134962.tif 000009
【図６】
2006134962.tif 000010
【図８】
2006134962.tif 000011
【図１０】
2006134962.tif 000012
【図１１】
2006134962.tif 000013
【図１２】
2006134962.tif 000014
【図１３（ａ）】
2006134962.tif 000015
【図１３（ｂ）】
2006134962.tif 000016
【図１４（ａ）】
2006134962.tif 000017
【図１４（ｂ）】
2006134962.tif 000018
【図１５（ａ）】
2006134962.tif 000019
【図１５（ｂ）】
2006134962.tif 000020
【図１６（ａ）】
2006134962.tif 000021
【図１６（ｂ）】
2006134962.tif 000022
【手続補正書】
【提出日】平成19年11月15日(2007.11.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
処理部を備え、前記処理部は、以下の処理を行うことを特徴とする投影図生成システム：
（１）３次元地形モデルから、遮蔽に関係している可能性のある部分における地理特徴を表す特徴点を抽出する処理；
（２）ある視点から見たときの２次元投影面上において、前記特徴点の最適配置を算出する処理；
（３）前記２次元投影面上における前記特徴点の最適配置を満たす３次元地形形状を生成する処理；
（４）前記３次元形状を、前記視点又はその近傍から見たときの２次元投影図を生成する処理。
【請求項２】
さらに記憶部を備え、前記記憶部は、前記３次元地形モデルを記憶しており、
前記処理部は、前記記憶部から前記３次元地形モデルを取得する構成となっており、
前記処理部は、生成された前記２次元投影図を前記記憶部に格納する構成となっている
ことを特徴とする、請求項１に記載の投影図生成システム。
【請求項３】
請求項１又は２に記載の投影図生成システムと、表示部とを備え、前記表示部は、前記２次元投影図を表示する構成となっていることを特徴とする投影図表示システム。
【請求項４】
前記処理部は、前記視点の移動に対応して、前記（１）〜（４）の処理を行うことにより、異なる時点における２次元投影図を生成する構成となっており、
ある時点における２次元投影図を生成する場合において、次の条件を満たす特徴点が存在する場合には、それを、前記（１）の処理における特徴点として用いることを特徴とする、請求項１〜３のいずれか１項に記載の投影図生成又は表示システム：
（条件）
前記ある時点より前に生成した２次元投影図で用いた特徴点であって、それが、前記ある時点の２次元投影図におけるビューボリューム内に存在すること。
【請求項５】
前記特徴点の最適配置とは、前記ある視点から見たときの２次元投影面上において、道路上における特徴点を結ぶ線の遮蔽が回避され、かつ、各特徴点の相対位置関係が保持された状態であることを特徴とする、請求項１〜４のいずれか１項に記載の投影図生成又は表示システム。
【請求項６】
前記（１）の処理における、前記特徴点の抽出を、以下の処理により行うことを特徴とする、請求項１〜５のいずれか１項に記載の投影図生成又は表示システム：
（ａ）参照点を通る水平面に対して、ある一定の角度で傾斜する方向に視点を置く処理；
（ｂ）前記３次元地形モデルから得られる３次元の地形形状に対する、前記視点の位置を、前記参照点を中心とし、かつ水平な方向に、相対的に回転移動させるときに、前記３次元の地形形状の輪郭線上に乗る頂点をすべて特徴点として抽出する処理。
【請求項７】
以下のステップを備えることを特徴とする、投影図生成方法：
（１）３次元地形モデルから、遮蔽に関係している可能性のある部分における地理特徴を表す特徴点を抽出するステップ；
（２）ある視点から見たときの２次元投影面上において、前記特徴点の最適配置を算出するステップ；
（３）前記２次元投影面上における前記特徴点の最適配置を満たす３次元地形形状を生成するステップ；
（４）前記３次元形状を、前記視点又はその近傍から見たときの２次元投影図を生成するステップ。
【請求項８】
請求項７に記載のステップをコンピュータに実行させるためのコンピュータプログラム。
【国際調査報告】
2006134962.tif 000023
2006134962.tif 000024