JPH11174952A - 地図データの先読み方法及び地図スクロール方法 - Google Patents

Abstract

(57)【要約】 【課題】 ＣＰＵのアイドルタイムを有効に利用し、該
アイドルタイムにおいて現図葉及び周辺の８つの図葉を
先読みする。 【解決手段】 車両が属する領域に応じた中心図葉と該
領域の周辺領域に応じた隣接図葉を主記憶装置３３に先
読みするナビゲーション装置の地図データの先読み方法
である。地図データの先読みを行う先読みスレッドをプ
ログラムメモリ３２内に用意すると共に該先読みスレッ
ドの優先度を低くし、ＣＰＵ２０の空き時間を監視し、
該ＣＰＵ空き時間に先読みスレッドを起動し、先読みス
レッドにより現図葉及び周辺の隣接図葉を地図記録媒体
１１より読出して主記憶装置３３に格納する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は地図データの先読み
方法及び地図スクロール方法に係わり、特に、車両の移
動に伴って車両位置周辺の地図をスクリーンに表示する
ナビゲーション装置における地図データの先読み方法及
び地図スクロール方法に関する。

【０００２】

【従来の技術】車両の走行案内を行い、運転者が所望の
目的地に容易に到達できるようにしたナビゲーション装
置は、車両の位置を検出して地図記録媒体（例えばＣＤ
−ＲＯＭ）から車両位置周辺の地図データを読み出し、
地図画像をディスプレイ画面に描画するとともに自車位
置マークを重ねて描画する。かかるナビゲーション装置
では、自車位置マークをディスプレイ画面上の所定位置
に固定表示し、地図を車両の移動に従ってスクロールす
るのが普通であり、常に車両位置周辺の地図が一目で判
るようになっている。このため、ナビゲーション装置で
は、円滑に地図スクロールができるように適時に車両位
置に応じた地図データを地図記録媒体より読み取る必要
がある。

【０００３】地図データは地図を図葉単位に分割して作
成されて地図記録媒体に記録、管理されている。この図
葉は、一般に表示できる画面の大きさに比べて十分大き
い。かかる図葉１枚分のデータだけをメモリにロードし
ておく方法は、車両が現図葉の境界にさしかかった時に
新規地図データの更新が必要になる。図１８はかかる地
図データ更新タイミングの説明図であり、４は現在車両
が属する領域に応じた図葉、０〜８（４は除く）は周辺
の隣接図葉、ＷＤは車両周辺の１画面分のサイズに応じ
たウィンドウである。車両の移動に応じてウィンドウＷ
Ｄが隣接図葉の境界線に到達した時、新規地図データの
更新が必要になる。しかし、かかる地図データ更新方法
では境界を越える部分で地図データの更新に時間がかか
り、地図スクロールが不連続になり、また、画面がチラ
ついているように見えるようになる。

【０００４】そこで、車両が次に進入する隣接領域を予
測し、車両が実際に該隣接領域に進入する前に隣接図葉
の地図データを地図記録媒体より先読みする方法が考え
られる。例えば、自車が現在走行している方向に道路を
延長して中心図葉の境界に接している隣接図葉を先読み
する手法や、中心図葉を対角線で４つの三角形に分割
し、どの三角形内を自車が走行しているかで対応する隣
接図葉を予測して先読みする手法が考えられる。しか
し、日本国内の道路網はアメリカのように縦横の道路が
碁盤目状に張り巡らされたような画一的なものは稀で、
ほとんどの道路は比較的範囲の狭い図葉内においても歪
曲している。つまり、上記のような手法を用いて次の図
葉を予測しようとしても、確実な予測ができず、予測を
誤った場合には、そ都度、再度の予測をしなおす必要が
あり、最終的には隣接図葉のほとんどを先読みすること
になる。これでは、結局のところ予測に要した多大な計
算時間が無駄になり、効率が悪く、プロセッサ（ＣＰ
Ｕ）のスループットを低下する。

【０００５】コンピュータシステムにおいて、ＣＰＵが
プログラムに基づいて演算処理を実行するタイミングに
は偏りがあり、頻繁な演算と閑散としたアイドルタイム
が混在する。ナビゲーション装置の地図スクロール表示
では、ＣＰＵが活発に演算している時間は総ＣＰＵ時間
の３割と云われ、残りの７割はつまりアイドルタイムで
あり、ＣＰＵは活動していない。一方では、地図スクロ
ール表示は地図データを地図記録媒体より読み込む時間
がネックとなり、体感的に遅く感じられる。これはＣＤ
−ＲＯＭなどの地図記録媒体にアクセスして地図データ
を主記憶上に読み込む速度がハードディスクなどに比べ
て遅いことに起因している。

【０００６】

【発明が解決しようとする課題】以上のように、従来の
地図データの先読み法では、ＣＰＵ処理に無駄があり、
しかも、ＣＰＵのアイドルタイムが多い問題があった。
また、従来の地図スクロール方法では、地図スクロール
が不連続になり、画面がチラツク問題があった。更に従
来の地図スクロール方法では、地図スクロール表示にお
けるデータ更新がその他の処理に比べて非常に重く、長
いデータ更新時間によりその他の重要な処理の実行が遅
れ、ユーザからの要求を受け付けられなくなったり、経
路探索の実行速度が極端にダウンしたりするなどの問題
があった。

【０００７】従って本発明の目的は、隣接図葉を予測せ
ず、ＣＰＵのアイドルタイムを有効に利用し、該アイド
ルタイムにおいて現図葉及び周辺の８つの図葉を先読み
できるようにすることである。本発明の別の目的は、並
列処理により実行可能なデータ更新スレッド、地図描画
スレッド、画面表示スレッドを設け、これらスレッドの
優先度を状況に応じてダイナミックに割り当て、かつ、
変更することにより地図スクロールを円滑に行えるよう
にすることである。本発明の別の目的は、先読みと動的
な割り当て可能な優先度を用いた地図描画アルゴリズム
によりＣＰＵの負荷がそれほど大きくない時に優先度を
低くセットしたスレッドでデータ更新をするようにし、
従来再描画のデータ更新時に一時的に発生する大きな負
荷を回避し、他の重要な処理の実行が遅れないようにす
ることである。

【０００８】

【課題を解決するための手段】上記課題は本発明によれ
ば、車両が属する領域に応じた中心図葉と該領域の周辺
領域に応じた隣接図葉をメモリに先読みするナビゲーシ
ョン装置の地図データの先読み方法において、(1) 地図
データの先読みを行う先読みスレッドを用意すると共に
該先読みスレッドの優先度を低くし、(2) ＣＰＵの空き
時間を監視し、(3) 該ＣＰＵ空き時間に先読みスレッド
を起動し、(4) 先読みスレッドにより中心図葉及び周辺
の隣接図葉を地図記録媒体より読出してメモリに格納す
る先読み方法により達成される。かかる先読み方法によ
れば、隣接図葉を予測せず、ＣＰＵのアイドルタイムを
有効に利用し、該アイドルタイムにおいて中心図葉及び
周辺の図葉を先読みすることができる。

【０００９】上記課題は本発明によれば、車両の移動に
伴って車両位置周辺の地図をスクリーンに表示するナビ
ゲーション装置の地図スクロール方法において、(1) 地
図データを地図記録媒体より読み取って地図バッファに
記憶されているデータを更新するデータ更新制御、地図
バッファに記憶されている地図データに基づいて地図画
像を発生してＶＲＡＭに描画する地図描画制御、ＶＲＡ
Ｍから車両位置周辺の地図画像を切り出してスクリーン
に表示する画面表示制御のそれぞれを並列処理により実
行可能なデータ更新スレッド、地図描画スレッド、画面
表示スレッドを用意し、(2) これらスレッドの優先度を
低くすると共に、データ更新完了前は上記各スレッドの
うち、データ更新スレッドの優先度を最高にし、データ
更新完了後であって地図描画完了前は地図描画スレッド
の優先度を最高にし、地図描画完了後であって画面表示
完了前は画面表示スレッドの優先度を最高にし、(3) 地
図スクロール処理に際して優先度が最高のスレッドを実
行する地図スクロール方法により達成される。

【００１０】かかる方法によれば、地図スクロール制御
の各段階において最も重要な役割を担うスレッドを最優
先とすることで円滑なスクロールが可能になる。スレッ
ドの優先度の概念を用いることにより、各制御（データ
更新制御、地図描画制御、画面表示制御）間の綿密な負
荷計算に基づくスケジューリングをカーナビ開発者は行
う必要がなくなる。また、(1) 車両が属する領域に応じ
た中心図葉に隣接する８つの隣接図葉に対して先読みス
レッドを用意し、(2) 車両が進入した隣接図葉の先読み
スレッドを前記データ更新スレッドとして地図データを
読み出し、(3) 車両が進入した図葉に対する隣接図葉に
対しては、前記データ更新スレッド、地図描画スレッ
ド、画面表示スレッドより優先度を低く設定した先読み
スレッドにより地図データを先読みさせることで、車両
が進入した図葉のデータを最優先で読み出すことがで
き、その結果、車両位置周辺の地図画像を高速に表示で
き、地図スクロールを円滑に行なうことができる。

【００１１】更に、地図スクロールに必要なデータを用
意する先読みスレッドの優先度を低くすることでＣＰＵ
負荷が小さい時に地図データの先読みが行なわれるよう
になり、その結果、再描画時に一時的に大きな負荷が発
生することで他の処理が遅延してしまうことを防止で
き、システム全体の効率を大幅に改善できる。また、こ
の場合、(1) 車両が属する領域に応じた中心図葉を４分
割し、(2) 画面に表示されている中心点がいずれの分割
領域に属するか判断し、(3) 該所属分割領域に隣接する
領域に応じた隣接図葉の先読みスレッドの優先度を他の
隣接図葉の先読みスレッドの優先度より高くし、(4) 優
先度の高い隣接図葉をより早く先読みするようにすれ
ば、車両が次に進入する可能性の高い隣接図葉を早めに
先読みできるため、車両位置周辺の地図画像を確実に表
示でき、地図スクロールを円滑に行うことができる。ま
た、既に地図バッファに読み込まれている隣接図葉以外
の隣接図葉のみを先読みすることにより、先読みの負荷
を小さくでき、先読みに要する時間を短縮でき、確実に
中心図葉及び周辺８個の隣接図葉を先読みして地図バッ
ファに格納できる。

【００１２】

【発明の実施の形態】（Ａ）地図データの先読み（第１
実施例） （ａ）本発明の描画手法 Java言語を実装言語とし、優先度を低くした（例えば最
低にした）スレッドをＣＰＵ空き時間に自動的に起動す
るようにし、該スレッドにデータの先読み機能を付加す
る。これにより、ＣＰＵのアイドルタイムに自動的に地
図データを先読みして主記憶にバッファリングする先読
みスレッドを実現する。スレッドは、処理を並列に実行
する。先読みスレッドは、優先度が低いため起動しても
システムの応答性にはほとんど影響を与えない。

【００１３】（ｂ）地図データ管理 図１（ａ）の実線で示すように中心図葉及び隣接図葉よ
りなる３×３（＝９）枚の図葉に番号０〜８を付し、該
図葉番号を用いて地図データの管理を行う。すなわち、
図葉番号０〜８のHashtableを設け、該Hashtableにより
地図データの管理を行う。このため、車両が移動して隣
接図葉に進入すると図葉番号の振り替えが必要になる。
例えば、図１（ａ）に示すように自車が移動して中心図
葉の真下の隣接図葉番号７の図葉に進入した場合、中心
図葉は隣接図葉番号７の図葉に更新される。この時、元
の中心図葉４は図１（ｂ）に示すように隣接図葉番号１
の図葉になる。また、元の隣接図葉番号３の図葉は０に
なり、５は２になり、６は３に、７は４に、８は５にな
る。すなわち、自車が移動して中心図葉の真下の隣接図
葉番号７の図葉に進入すると、図１（ｃ）に示すように
旧図葉番号を新図葉番号に振り替える必要がある。一般
的に、自車が進入した図葉の旧図葉番号をＣ、着目して
いる図葉の旧図葉番号をＢ、着目している図葉の新図葉
番号をＡとすれば次式 Ａ＝Ｂ＋（４−Ｃ） (1) が成立する。図１（ｃ）の場合、Ｃ＝７として(1)式の
計算をすれば、新図葉番号Ａが求まる。

【００１４】ところで、図１（ａ）に示すように自車が
中心図葉の真下の隣接図葉番号７の図葉に進入した場
合、進入後も利用できる図葉(地図データ)の旧図葉番号
は３，４，５，６，７，８であり、進入後に先読みしな
ければならない図葉(地図データ)の新図葉番号は６，
７，８である（図１（ｄ））。すなわち、旧図葉番号
３，４，５，６，７，８に(1)式を適用して新図葉番号
に振り替えれば新たに地図データを読み込む必要はな
く、また、新図葉番号６，７，８の図葉(地図データ)の
みを先読みすればよいことになる。図１（ｄ）に示す関
係が判っていれば、新図葉番号への振り替え処理及び先
読み処理の効率をあげることができる。そこで、自車が
進入する隣接図葉の旧図葉番号Ｃに対応させて、進入
後も利用できる図葉（地図データ）の旧図葉番号の配列
ＡＲ１と、進入後に先読みすべき図葉（地図データ）
の新図葉番号の配列ＡＲ１を保存しておき、Hashutable
の変更操作の計算コストを削減する。図２は、ＣとＡＲ
１，ＡＲ２の関係 Ｃ＝｛｛ＡＲ１｝，｛ＡＲ２｝｝ を示すテーブルである。

【００１５】図３はハッシュテーブルの説明図である。
図１の実線で示す状態において、ハッシュテーブルＨＴ
は図３（ａ）に示すように図葉番号０〜８に対応して地
図データｕとしてＧ₀〜Ｇ₈を対応つける。かかる状態に
おいて自車が中心図葉の真下の隣接図葉番号７の図葉に
進入すると、ハッシュテーブルＨＴは図３（ｂ）に示す
ように更新される。すなわち、新図葉番号０〜５に対応
して地図データｕとしてＧ₃〜Ｇ₈を対応つける。また、
新図葉番号６〜８に対応する地図データは主記憶装置に
読出されていないから、ｕ＝０とする。

【００１６】（ｃ）ナビゲーション装置の要部構成 図４はナビゲーション装置の描画系の機能構成図であ
り、１０は地図データを記憶する地図記録媒体（例えば
ＣＤ−ＲＯＭ）、１１は自車位置等に基づいてＣＤ−Ｒ
ＯＭ１０より所定の地図データを読み出すと共に、自車
位置に応じてディスプレイ画面に表示される地図上の画
面中心位置を計算する地図読出制御部、１２はＣＤ−Ｒ
ＯＭから読み出された地図データを記憶する地図バッフ
ァ、１３は地図描画部であり、地図バッファに記憶され
た地図情報を用いて地図画像を発生するもの、１４は地
図画像を記憶するＶＲＡＭ、１５は地図読出制御部１１
より入力される画面中心位置に基づいてＶＲＡＭ１４よ
り１画面分の地図画像を切り出す地図切出し制御部、１
６はディスプレイ装置、１７は自車の位置を測定する位
置測定装置である。地図読出制御部１１、地図描画部１
３、地図切出し制御部１５は実際にはＣＰＵ（図５）に
より構成される。

【００１７】図５はＣＰＵ構成のナビゲーション装置の
ブロック図であり、図４と同一部分には同一符号を付し
ている。１０は地図記録媒体（ＣＤ−ＲＯＭ）、１４は
ＶＲＡＭ、１６はディスプレイ装置、１７は位置測定装
置、２０はナビゲーション制御を行うプロセッサ（ＣＰ
Ｕ）、２１はＣＤ−ＲＯＭ制御部、２２はリモコンイン
タフェース部、２３は外部メモリ、２４はバスである。
ＣＰＵ２０において、３１は演算処理ハードウェア部、
３２はプログラムメモリ（ＲＯＭ）で、ナビゲーション
制御用の各種プログラム（経路誘導制御、マップマッチ
ング制御、地図スクロール制御等のプログラム）を記憶
するもの、３３は主記憶装置（ＲＡＭ）で、ＣＤ−ＲＯ
Ｍから読み取った地図データやハッシュテーブル、その
他処理結果を記憶するものである。地図スクロール用の
プログラムには、図３に示す地図読出し制御、地図描画
制御、地図切り出し制御を行うようにプログラミングさ
れている。

【００１８】（ｄ）先読みアルゴリズム 図６は本発明の先読み制御処理の流れ図であり、（ａ）
はメイン処理のフロー、（ｂ）は先読みスレッドの処理
フローである。先読みスレッドの優先度を最低にしてお
き、ＣＰＵが空きになった時にのみ該先読みスレッドを
起動して先読みを行うようにする。先読みスレッドの優
先度を最低にしてもＣＰＵのアイドル時間は総ＣＰＵ時
間の７割であるから、余裕をもって隣接図葉の地図デー
タをＣＤ−ＲＯＭ１１から読出して主記憶装置３３に格
納することができる。

【００１９】ＣＰＵ２０は管理プログラムの制御でナビ
ゲーションのメイン処理を実行すると共に、自分が空き
になったか監視する（ステップ１０１〜１０２）。空き
になれば、地図先読みが必要か、すなわち、車両が隣接
領域に進入して地図の先読みが必要になっているか調べ
る（ステップ１０３）。隣接領域に進入しておらず先読
みが不要であればステップ１０１に戻る。一方、先読み
が必要であれば、先読みスレッドを起動し（ステップ１
０４）、以後、高優先度のイベント発生を待つ（ステッ
プ１０５）。高優先度のイベントが発生すれば、すなわ
ち、ＣＰＵの空きが解消すれば、先読みスレッドを停止
し（ステップ１０６）、メイン処理を実行する（ステッ
プ１０１）。

【００２０】先読みスレッドは、起動されると初期化す
る（ステップ２０１）。ついで、ＣＰＵが空きかチェッ
クし、空きでなければ所定時間（例えば１秒間）待っ
て、ＣＰＵの空きをチェックする（ステップ２０２〜２
０３）。ＣＰＵが空きであれば、すなわち、停止が指示
されていなければ、ハッシュテーブルＨＴ（図３）を参
照して先読みすべき隣接図葉を識別し、該隣接図葉をＣ
Ｄ−ＲＯＭ１０より読出して主記憶装置３３に格納する
（ステップ２０４）。以後、全隣接地図の読み出しが完
了したかチェックし（ステップ２０５）、完了してなけ
れば、ステップ２０２以降の処理を繰り返し、全隣接地
図の読み出しが完了すれば先読み処理を終了する。

【００２１】以下は先読みスレッドのアルゴリズムをプ
ログラム化したものである。 (1). if（ＣＰＵがアイドル) (2). for(隣接８図葉uに対して) (3). if(隣接図葉uの先読みスレッドを初期化されていない) (4). 隣接図葉uの先読みスレッドを初期化 (5). if(隣接図葉uの地図データ読み込みが終了していない) (6). 隣接図葉uの先読みスレッドを起動 (7). else (8). 先読みスレッドを停止 (9). wait 1 second (1)において、ＣＰＵに空き時間があるかどうかチェッ
クされる。ＣＰＵが空き時間の場合(2)〜(6)が実行され
る。まず、対応する隣接８図葉に対して先読みスレッド
が初期化されているかどうかチェックする(3)。初期化
されていない場合には、先読みスレッドを初期化する
(4)。すでに対応する先読みスレッドが初期化されてお
り、先読みがまだ終了していないのであれば(5)、その
先読みスレッドを起動し、隣接図葉の先読みを実行する
(6)。ＣＰＵに空き時間がない場合は、先読みスレッド
を１秒間休ませる。

【００２２】以上では、地図データの先読み（データ更
新）に重点をおいて説明したが、地図スクロールする場
合には、データ更新制御のほかに、地図描画制御、画面
表示制御が必要である。以下では、これら制御用にスレ
ッドを用意し、これらを並列処理する実施例について説
明する。

【００２３】（Ｂ）マルチスレッドによる地図の並列描
画制御（第２実施例） （ａ）概要 一般的な、地図描画手法では再描画時にＣＰＵに多大な
負荷が一時的にかかる。これにより、再描画だけでなく
システム全体のパフォーマンスもダウンさせてしまう。
このため、結果として、画面がちらついたり、システム
ダウンしたかのようになり、一時的にユーザからの操作
を受け付けなくなる。このような問題を解決するため
に、再描画時に必要となる部分の地図データをあらかじ
め再描画が呼び出される前に先読みする手法が有効であ
り、（Ａ）で説明した。ところで、スクリーンに地図を
描画するためには、(1) 先読みによる地図データの更新
制御（データ更新制御）、(2) ＶＲＡＭへの地図画像の
描画制御（地図描画制御）、(3) ＶＲＡＭから地図画像
を読み取ってスクリーンに表示する制御（画面表示制
御）が必要であり、これらの制御を連携し、効率よく地
図をスクリーン上でスクロール表示する必要がある。そ
こで、（Ｂ）においては、スレッドプログラミングを基
本にした並列処理により地図スクロール表示を実現す
る。スレッドプログラミングは並列処理を実現するため
のもので、マルチタスクＯＳによってサポートされてい
るものである。以下では、並列処理の優先度設定が容易
にできるJava言語を用いて説明する。

【００２４】ＣＰＵの負荷が比較的小さい時間（例えば
アイドルタイム）に地図データを先読みをするにあたっ
て、たとえば、「このタスクとあのタスクを同時に行な
うとどれだけの計算量を必要とし・・・」というよう
に、あらかじめプログラマーがきっちりしたＣＰＵ使用
のスケジューリングを作るのは非常に困難である。一
方、スレッドの優先度の概念を用いると、あるタスクＡ
と別のタスクＢについて、相対的な数値を与えるだけ
で、ＣＰＵ使用のスケジューリングを自動的に行なって
くれる。プログラマーはタスクの優先度を指定するだけ
で、その実行スケジューリングを考える必要がなくな
る。つまり、Ａが優先度１０、Ｂが優先度１と宣言する
だけで、ＡはＢに対して１０倍の時間、ＣＰＵを使用す
ることができる。本発明は、以上のようなスレッドの優
先度を用いて、必要に応じてその優先度を動的に変化さ
せると同時に、低い優先度で地図データの先読みを行な
うことで、地図描画のみならずシステム全体のパフォー
マンスをあげる。

【００２５】（ｂ）マルチスレッドによる描画手法 ナビゲーション装置（図４参照）において地図データを
使ってスクリーンに地図を描画するには、次の３つのス
テップが必要である。 step 1：地図データが保存されている記憶媒体１０から
地図データを読み出し、メモリ（地図バッファ）１２に
ロードする（データ更新）。 step 2：メモリ１２にロードされたデータを地図として
画面に表示できるようにオフスクリーンで加工する。す
なわち、地図データを用いてビットイメージの地図画像
をＶＲＡＭ１４に描画する（地図描画）。 step 3：step 2でＶＲＡＭに描画した画像データを用い
て地図を画面(スクリーン)１６に表示する(画面表示)。

【００２６】一般に、これらstepの処理コストの関係
は、 step 3 << step 2 < step 1 となる。step 1とstep 2の処理時間を比較した場合、st
ep 1はstep 2の約1.5倍の時間が必要であることが実験
により確認されている。また、step 1, step 2にくらべ
step 3は無視できる程度の処理時間しか必要としない。
以上から、システムから描画の要求があって、はじめて
上記の３つのステップを実行するのではなく、step 1を
ＣＰＵの暇な時間にあらかじめ処理しておくという方法
(先読み)が有効である。この処理方法については、後述
する。まず、先読みを除いた基本的な描画部分について
述べる。

【００２７】（ｃ）描画モデル 描画を行うために、まず図７のような描画モデルを考え
る。このモデルでは、Java言語に代表されるスレッドが
利用されており、以下の４つのスレッドが同時実行され
る。４１はデータ管理スレッドであり、描画スレッド群
（データ更新スレッド、地図描画スレッド、画面表示ス
レッド）の管理を行なうもので、具体的には、状況に応
じて描画スレッド群の優先度を動的に割り当てる。４２
はデータ更新スレッドであり、地図データが保存されて
いる記憶媒体（ＣＤ−ＲＯＭ）１０から地図データを読
み出し、地図バッファ１２にロードする。このデータ更
新スレッドは図３における地図読み出制御部１１に相当
するものである。４３は地図描画スレッドであり、地図
バッファ１２にロードされた地図データを用いてビット
イメージの地図画像を発生してＶＲＡＭ１４に格納す
る。この地図描画スレッドは図３の地図描画部１３に相
当するものである。４４は画面表示スレッドで、地図描
画スレッドによりＶＲＡＭ１４に描画された地図のうち
自車位置に応じた地図部分を切り出してスクリーン１６
に表示する。この地図描画スレッド４４は図３の地図切
り出し制御部１５に相当するものである。

【００２８】データ管理スレッド４１は、描画に関する
すべてを管理するスレッドであり、最も優先して実行さ
れなければならない。このデータ管理スレッド４１のも
と、前述のstep 1〜step 3に対応する描画スレッド群
(データ更新スレッド４２、地図描画スレッド４３、画
面表示スレッド４４)が存在する。描画スレッド群はそ
れぞれが連鎖的に動作するのではなく、マルチスレッド
により独立、並行に動作する。これによりデータ更新ス
レッド４２がデータを収集しながら、地図描画スレッド
４３が更新された部分を描画するといった並行作業が可
能となる。しかしながら、何らかのルールを定めない
と、それぞれのスレッドは独立に自分のタスクを遂行し
ようとする。このため、地図描画スレッド４３によるＶ
ＲＡＭ１４への地図描画が完成していないのに、画面表
示スレッド４４が地図を切り出して画面表示を行なおう
とするなど、スレッド間の競合が生じる場合がある。

【００２９】そこで、本発明では、描画命令が発生した
場合、状況に応じてデータ管理スレッド４１の制御で描
画スレッド群４２〜４４の優先度を動的に割り当て、か
つ、変更できるようにする。この場合、当然のことであ
るが、描画スレッド群４２〜４４の優先度は、データ管
理スレッド４１の優先度よりも小さいものとする。又、
ＣＰＵの負荷が低いときに実行されるように各スレッド
の優先度を低く設定する。図８はかかる優先度の状況を
示す説明図である。優先度とはスレッド間でＣＰＵ占有
時間を変化させるためのものである。すなわち、優先度
が高くなるほど実行されやすくなり、また低くなるほど
実行は後回しにされる。この特性を利用することによ
り、必要な処理を優先的に行なわせ、ＣＰＵの空き時間
にその他の処理を行なわせることが可能になる。以下で
は、この優先度割り当てを用いた地図の再描画方法を説
明する。

【００３０】（ｄ）動的な優先度の割り当て データ管理スレッド４１が描画スレッド群４２〜４４に
対して動的な優先度を割り当てる場合、次の状況を考え
なければならない。 状況１：描画に必要な部分のデータ更新が完了してい
るか否か。 状況２：地図描画が完了しているか否か。 状況３：画面表示が完了しているか否か。 これら状況の組み合わせは、全部で８通りある。しか
し、描画というものがデータ更新→地図描画→画面表示
のステップで進むことを考慮すると、例えばデータ更新
が終了していないのに地図描画が終了しているといった
状況はなくなるので、次の４通りが残る。 状況１：データ更新、地図描画、画面表示の全てが終
了していない。 状況２：データ更新は終了しているが、地図描画、画
面表示が終了していない。 状況３：データ更新、地図描画は終了しているが画面
表示が終了していない。 状況４：データ更新、地図描画、画面表示のすべてが
終了している。

【００３１】そして、これら４つの状況の間には時間的
な関係も存在する。つまり、状況４の前の状況というの
は状況３しかなく、また状況３の前の状況は状況２しか
なく、状況２の前には状況１しかない。よって、その時
の処理アルゴリズムも、状況１→状況２→状況３→状況
４の順でチェックし、動的な優先度の割当を行えばよい
ということになる。その時の優先度の割り当て基準は、
図９（ａ）〜（ｄ）のようになる。

【００３２】図９（ａ）は状況１における優先度割当基
準であり、優先度はデータ更新スレッド４２＞地図描画
スレッド４３＞画面表示スレッド４４の順にする。図９
（ｂ）は状況２における優先度割当基準であり、優先度
は地図描画スレッド４３＞画面表示スレッド４４＞デー
タ更新スレッド４２の順にする。図９（ｃ）は状況３に
おける優先度割当基準であり、優先度は画面表示スレッ
ド４４＞データ更新スレッド４２＞地図描画スレッド４
３の順にする。図９（ｄ）は状況４における優先度割当
基準であり、優先度はデータ更新スレッド４２＝地図描
画スレッド４３＝画面表示スレッド４４とする。以上の
ように各状況に応じて各スレッドの優先度を動的に割り
当てることにより矛盾なく、しかも、効率よく地図スク
ロール制御が可能になる。

【００３３】以上よりデータ管理スレッド４１による描
画スレッド群４２〜４４の動的な優先度割り当てアルゴ
リズムは図１０のようになる。このアルゴリズムでは、
状況１→状況２→状況３→状況４の順で状況が変化する
ことを利用した構造になっている。つまり、“描画部分
のデータ更新未完了”は状況１に対応し、“地図描画未
完了”は状況２に、“画面表示未完了”は状況３にそれ
ぞれ対応し、“画面表示完了”は状況４に対応してい
る。アルゴリズムでは例えば、再描画命令が新たに発生
した場合、まず、データ管理スレッド４１は、描画部分
のデータがすでに更新されているかどうかを確認する
（ステップ３０１）。更新されていれば次の段階に移行
するが、更新過程であった場合は、データ更新スレッド
４２を最優先とし、地図描画スレッド４３、画面表示ス
レッド４４の順に優先度を割り当てる。そして、データ
の更新が終了すると（ステップ３０２、３０３）、地図
の描画が終了したかどうかの確認を行ない（ステップ３
０４）、終了していなければ、今度は地図描画スレッド
４２を最優先した優先度の変更を行う（ステップ３０
５、３０６）。このようにして、各描画段階において最
も重要な役割を担うスレッドを最優先とするで、スレッ
ド間の同期を取ることなく競合の回避を実現する。

【００３４】（ｅ）描画への先読みの導入 以上の方法により、地図は一応、描画できる。しかし、
データ更新は地図描画、画面表示に比べて非常に大きな
処理コストを必要とする。たとえ、マルチスレッドで
ユーザとのやりとり（リモコンインタフェース制御）、
ＧＰＳデータ獲得、経路探索等を実装したとして
も、地図スクロール表示におけるデータ更新はその他の
処理に比べて非常に重く、長いデータ更新時間によりそ
の他のスレッドの実行速度を遅延する。その結果ユーザ
からの要求を受け付けなくなったり、経路探索の実行速
度が極端にダウンしたりする。

【００３５】このような、問題を解決するために地図の
再描画の要求が発生していない場合、つまりＣＰＵに余
裕がある時に、あらかじめ再描画要求の発生を見込んで
おいて、そのための準備をする先読み処理が有効であ
る。地図スクロール表示に際して、データ更新コストが
最も大きく、データ更新さえできていれば地図描画、お
よび画面表示はわずかなコストで実現できる。よって最
もコストの大きい地図更新のためのデータ保存をあらか
じめ準備して行なう。このデータの保存とは、未知の地
図部分のデジタルデータをＣＤ−ＲＯＭより先読みして
いることに他ならない。まず、この先読みすべき地図の
部分について説明し、先読みの方法および全体のシステ
ムにおける先読みの位置付けを明確にする。

【００３６】(e-1) 先読みすべき部分 ナビゲーション等の地図データは、地図を図葉単位で分
割して作成してCD-ROM等の地図記録媒体に記憶、管理さ
れている。この図葉は、一般に表示できる画面の大きさ
に比べて十分大きく、かつ図葉１枚のデータだけをメモ
リにロードしておく方法において、新規地図データ更新
の要求が発生するのは、図１１のように図葉の境界にさ
しかかった時である。そして、この境界を越える部分で
データの更新に時間がかかり、それが原因で画面がチラ
ついているように見えるのである。そこで本発明では、
現在画面に表示している部分の中心点が含まれている図
葉（中心図葉）に隣接する８つの図葉（隣接図葉）のデ
ータを先読みする。ちょうどこの部分は図１１の隣接図
葉１，２，３，４，５，６，７，８を示す。

【００３７】(e-2) 先読みの方法 先読みでは、それぞれ１つの隣接図葉に先読みスレッド
を１つ用意する。つまり、先読みスレッドは全部で８つ
あることになる。この先読みスレッドにも前述までの優
先度の概念を利用する。つまり、これら８つの図葉デー
タのうち、次に描画される可能性の高い図葉ほど高い優
先度を設定する。具体的には図１２に示すように８つの
先読みスレッドの優先度を決定する。すなわち、中心図
葉を４つの領域に分割し、現在画面に表示している部分
の中心点が、この領域のどこに含まれているかで、各隣
接図葉の先読みスレッドの優先度を決定する。図１３は
画面表示部分の中心が属する領域と各隣接図葉の優先度
の関係説明図表である。このように隣接図葉の先読みス
レッドに優先度を割り当てることで、先読みの中でも特
に将来使用される可能性の高い図葉のデータを優先的に
読み取って早めに保存することが可能になる。

【００３８】(e-3) 先読みスレッドの優先度の位置付け 先読みスレッドは補助的な役割を果たすものであり、そ
の優先度はデータ管理スレッド４１、データ更新スレッ
ド４２、地図描画スレッド４３、画面表示スレッド４４
よりも低い優先度でなければならない。図１４は先読み
スレッドの優先度の位置付け説明図である。データ更新
スレッド４２と先読みスレッド５１〜５８は、機能的に
同じである。しかし、データ更新スレッド４１の起動時
に全ての先読みスレッド５１〜５８が起動するのではな
い。再描画時に先読みスレッドにより次に表示すべき部
分のデータが準備されていない場合に限り、そのデータ
の先読みを行っていた先読みスレッドがデータ更新スレ
ッド４２として扱われる。それ以外の先読みスレッドは
他のスレッド群４３，４４より低い優先度で実行され
る。すなわち、車両が所定の領域に進入した場合、該領
域に対応する隣接図葉の先読みスレッドをデータ更新ス
レッド４２として実行し、以後、地図描画スレッド４
３、画面表示スレッド４４を実行し、これらスレッド４
３、４４の実行完了後に他の先読みスレッドを起動して
他の隣接図葉を先読みする。

【００３９】(e-4) 差分情報を用いることによる先読み
の効率性の向上 自車の移動により中心図葉が変化する毎に、新たな隣接
８図葉の地図データを先読みするためのスレッドを用意
するが、ここでは、その際の効率を向上させる方法につ
いて述べる。例えば、図１５のように１〜２５までの図
葉があり、自車の中心図葉が９から１３に移動したとす
る。自車が図葉９にいた時にすでに、図葉３，４，５，
８，９，１０，１３，１４，１５の地図データは完全で
はなくともその一部分は先読みとデータ更新（データ更
新で読まれるのは９だけ）により地図バッファ１２（図
７）に保存されている。次に、自車が図葉１３に移動す
ると該図葉１３の先読みスレッドがデータ更新スレッド
４１として扱われ、新たに図葉７，８，９，１２，１
４，１７，１８，１９に関する先読みスレッドが準備さ
れる。

【００４０】しかし、この先読みスレッドのうち８，
９，１４は既に中心図葉が９であった時にある程度その
地図データが地図バッファ１２に取り込まれているはず
である。つまり、新規の中心図葉１３で先読みすべき部
分は、すでに地図バッファ１２にある程度保存されて
いる図葉８，９，１４と、新しい先読みスレッド７，
１２，１７，１８，１９ということになる。以上をまと
めると、中心図葉がｐからｃに変更される時、 (cの先読み部分で既にデータの１部が地図バッファにある部分) ＝（cの先読み部分)∩(pの先読み部分) (2) (cで先読みスレッドを新規に用意する部分) (3) ＝（cの先読み部分)∩(pの先読み以外の部分) ということになる。このような差分情報を用いれば先読
み時間を短縮できる

【００４１】。図１６は差分情報を用いた再描画アルゴ
リズムのフロー図であり、図１０のアルゴリズムに少し
変更を加えた形のアルゴリズムになっている。アルゴリ
ズム中のステップ４０１では、(3)式を満足する図葉(前
回の中心図葉ｐに対する先読み部分と新規の中心図葉ｃ
での先読み部分との差分となる部分)に対してのみ新し
い先読みスレッドを用意し開始する。(2)式を満足する
図葉は(重複する部分)は前回の先読みスレッドをそのま
ま使用する。以上、先読みと動的な優先度を用いたカー
ナビ用の描画アルゴリズム（図１６）により、再描画の
データ更新時に一時的にかかる大きな負荷をＣＰＵの負
荷がそれほど大きくない時に優先度を低くセットしたス
レッドで更新しておくことで、回避することができる。

【００４２】（Ｃ）評価実験 本手法の有効性を示すために、実際に市販のナビ研ＣＤ
−ＲＯＭを使用し、一定方向に画面スクロールさせるこ
とで強制的に再描画を発生させ、データ更新・地図描画
・地図表示の各必要処理時間をそれぞれ先読みがある場
合と、ない場合とで比較を行った。尚、評価はSun Ultr
al上で行った。図１７（ａ），（ｂ）は実験結果のグラ
フで、（ａ）は先読みしない場合、（ｂ）は先読みした
場合である。先読みがある場合も、ない場合も、スクロ
ール時の再描画におけるＶＲＡＭへの地図描画時間、Ｖ
ＲＡＭから読み取ってスクリーンに表示する地図表示時
間はある範囲内に収まって大差がない。しかし、ＣＤ−
ＲＯＭより地図データを読み取って更新するデータ更新
時間は、先読みなしの場合において再描画の時、ａ〜ｆ
で示すように突出している。これは一時的に非常に大き
な負荷がＣＰＵにかかっていることを意味している。一
方、先読み有りの場合には、突出はなくなっており、デ
ータ更新時間はほとんど目立たなくなっている（グラフ
では０にかなり近い値になっている）。これは、先読み
しない場合において一時的に突出したＣＰＵ負荷が一定
に分散されていることを意味し、先読みの利点が明らか
である。このように先読みにより、再描画時の処理コス
トを分散し、これにより、再描画時のシステムへの一時
的な負荷を軽減することができた。

【００４３】つぎに、先読みを用いた時のシステム全体
のパフォーマンスの向上について次の図１７（ｃ）に示
す。先読みがない場合に比べ、先読みがある場合はシス
テムの負荷が分散されただけでなく、全体として再描画
時のパフォーマンスも約２３％向上したことになる。つ
まり、先読みは負荷分散だけでなく、システム全体のパ
フォーマンスを向上させることができる。以上、本発明
を実施例により説明したが、本発明は請求の範囲に記載
した本発明の主旨に従い種々の変形が可能であり、本発
明はこれらを排除するものではない。

【００４４】

【発明の効果】以上本発明によれば、(1) 地図データの
先読みを行う先読みスレッドを用意すると共に該先読み
スレッドの優先度を低くし、(2) ＣＰＵの空き時間を監
視し、(3) 該ＣＰＵ空き時間に先読みスレッドを起動
し、(4) 先読みスレッドにより中心図葉及び周辺の隣接
図葉を地図記録媒体より読出してメモリに格納するよう
にしたから、進入する隣接図葉を予測する必要がなく、
また、ＣＰＵのアイドルタイムを有効に利用でき、該ア
イドルタイムにおいて中心図葉及び周辺の図葉を地図バ
ッファに先読みすることができる。

【００４５】本発明によれば、(1) 地図データを地図記
録媒体より読み取って地図バッファに既に記憶されてい
るデータを更新するデータ更新制御、地図バッファに記
憶されている地図データに基づいて地図画像を発生して
ＶＲＡＭに描画する地図描画制御、ＶＲＡＭから車両位
置周辺の地図画像を切り出してスクリーンに表示する画
面表示制御のそれぞれを並列処理により実行可能なデー
タ更新スレッド、地図描画スレッド、画面表示スレッド
を用意し、(2) これらスレッドの優先度を低くすると共
に、データ更新完了前は上記各スレッドのうち、データ
更新スレッドの優先度を最高にし、データ更新完了後で
あって地図描画完了前は地図描画スレッドの優先度を最
高にし、地図描画完了後であって画面表示完了前は画面
表示スレッドの優先度を最高にし、(3) 地図スクロール
処理に際して優先度が最高のスレッドを実行するように
したから、地図スクロール制御の各描画段階において最
も重要な役割を担うスレッドを最優先に実行でき、スレ
ッド間の同期を取ることなく各スレッドの競合回避を実
現でき、円滑な地図スクロールが可能になった。

【００４６】また、本発明によれば、(1) 車両が属する
領域に応じた中心図葉に隣接する８つの隣接図葉に対応
して先読みスレッドを用意し、(2) 車両が進入した隣接
図葉の先読みスレッドを前記データ更新スレッドとして
該隣接図葉を先読みし、(3)他の隣接図葉に応じた先読
みスレッドの優先度を前記地図描画スレッド、画面表示
スレッドの優先度より低くして該他の隣接図葉を先読み
するようにしたから、車両が進入した隣接図葉を最優先
で先読みできるため車両位置周辺の地図画像を確実に表
示でき、地図スクロールを円滑に行うことができる。

【００４７】また、本発明によれば、地図スクロールに
必要なデータ更新スレッドの優先度を低くし、ＣＰＵ負
荷が低いときに、地図データの先読みを行うようにした
から、従来再描画のデータ更新時に一時的にかかる大き
な負荷を回避でき、これにより、他の重要な処理の遅延
を防止でき、システム効率を大幅に改善できる。また、
本発明によれば、(1) 車両が属する領域に応じた中心図
葉を４分割し、(2) 画面に表示されている中心点がいず
れの分割領域に属するか判断し、(3) 該所属分割領域に
隣接する領域に応じた隣接図葉の先読みスレッドの優先
度を他の隣接図葉の先読みスレッドの優先度より高く
し、(4) 優先度の高い隣接図葉をより早く先読みするよ
うにしたから、車両が次に進入する可能性の高い隣接図
葉を早めに先読みできるため、車両位置周辺の地図画像
を確実に表示でき、地図スクロールを円滑に行うことが
できる。

【００４８】また、本発明によれば、既に地図バッファ
に読み込まれている隣接図葉以外の隣接図葉（差分図
葉）のみを先読みするようにしたから、先読みの負荷を
小さくでき、先読みに要する時間を短縮でき、確実に中
心図葉及び周辺８個の隣接図葉を先読みして地図バッフ
ァに格納できる。

【図面の簡単な説明】

【図１】地図データ管理説明図である。

【図２】進入先の旧図葉番号Ｃと進入後利用可能な旧図
葉番号配列ＡＲ１及び進入後先読みが必要な新図葉配列
ＡＲ２の対応図表である。

【図３】ハッシュテーブルの内容説明図である。

【図４】ナビゲーション装置の要部構成図である。

【図５】ＣＰＵを備えたナビゲーション装置の構成図で
ある。

【図６】先読み制御処理フローである。

【図７】マルチスレッドによる描画モデル説明図であ
る。

【図８】スレッド間の優先度に関する位置付け説明図で
ある。

【図９】各状況における優先度割り当て説明図である。

【図１０】動的優先度の割り当て処理フローである。

【図１１】データ更新要求発生のタイミング説明図であ
る。

【図１２】予測のために中心図葉を４つに分割した分割
領域説明図である。

【図１３】先読みスレッド間の優先度割り当て説明図で
ある。

【図１４】先読みスレッドの優先度に関する位置付け説
明図である。

【図１５】先読みの差分説明図である。

【図１６】差分情報を用いた再描画アルゴリズムであ
る。

【図１７】評価実験結果説明図である。

【図１８】従来の地図データの更新タイミング説明図で
ある。

【符号の説明】

１０・・地図記録媒体（ＣＤ−ＲＯＭ） １４・・ＶＲＡＭ １６・・ディスプレイ装置 １７・・位置測定装置 ２０・・プロセッサ（ＣＰＵ） ３１・・演算処理ハードウェア部 ３２・・プログラムメモリ ３３・・主記憶装置

Claims (5)

【特許請求の範囲】
1. 【請求項１】 車両が属する領域に応じた中心図葉と該
   領域の周辺領域に応じた隣接図葉をメモリに先読みする
   ナビゲーション装置の地図データの先読み方法におい
   て、 地図データの先読みを行う先読みスレッドを用意すると
   共に該先読みスレッドの優先度を低くし、ＣＰＵの空き
   時間を監視し、 該ＣＰＵ空き時間に先読みスレッドを起動し、先読みス
   レッドにより中心図葉及び周辺の隣接図葉を地図記録媒
   体より読出してメモリに格納することを特徴とする地図
   データの先読み方法。
2. 【請求項２】 車両の移動に伴って車両位置周辺の地図
   をスクリーンに表示するナビゲーション装置の地図スク
   ロール方法において、 地図データを地図記録媒体より読み取って地図バッファ
   に既に記憶されているデータを更新するデータ更新制
   御、地図バッファに記憶されている地図データに基づい
   て地図画像を発生してＶＲＡＭに描画する地図描画制
   御、ＶＲＡＭから車両位置周辺の地図画像を切り出して
   スクリーンに表示する画面表示制御のそれぞれを並列処
   理により実行可能なデータ更新スレッド、地図描画スレ
   ッド、画面表示スレッドを用意し、 これらスレッドの優先度を低くすると共に、データ更新
   完了前は上記各スレッドのうち、データ更新スレッドの
   優先度を最高にし、データ更新完了後であって地図描画
   完了前は地図描画スレッドの優先度を最高にし、地図描
   画完了後であって画面表示完了前は画面表示スレッドの
   優先度を最高にし、 地図スクロール処理に際して優先度が最高のスレッドを
   実行する、ことを特徴とする地図スクロール方法。
3. 【請求項３】 車両が属する領域に応じた中心図葉に隣
   接する８つの隣接図葉に対して先読みスレッドを用意
   し、 車両が進入した隣接図葉の先読みスレッドを前記データ
   更新スレッドとして扱うことで該図葉データを読みだ
   し、 車両が進入した図葉の隣接図葉に関しては、前記地図更
   新スレッド、地図描画スレッド、画面表示スレッドより
   優先度を低く設定した先読みスレッドにより地図データ
   を先読みすることを特徴とする請求項２記載の地図スク
   ロール方法。
4. 【請求項４】 中心図葉を４分割し、画面に表示されて
   いる中心点がいずれの分割領域に属するか判断し、該所
   属分割領域に隣接する領域に応じた隣接図葉の先読みス
   レッドの優先度を他の隣接図葉の先読みスレッドの優先
   度より高くし、優先度の高い隣接図葉をより早く先読み
   することを特徴とする請求項３記載の地図スクロール方
   法。
5. 【請求項５】 既に地図バッファに読み込まれている隣
   接図葉以外の隣接図葉のみを先読みすることを特徴とす
   る請求項３記載の地図スクロール方法。