(57)【要約】  画像処理装置（１００）は、移動体の現在位置に関する情報、移動体が保有するエネルギー量に関する情報、および、移動体が所定区間を走行する際に消費するエネルギー量に関する情報を取得する取得部（１０１）と、取得部により取得された情報に基づき、複数の領域を地図情報により特定する領域特定部（１０３）と、領域特定部により複数の領域が特定された後、取得部により取得された情報に基づき、複数の領域に移動体が到達可能であるか否かを探索する探索部（１０４）と、探索部により探索された複数の領域を表示部（１１０）に表示させる表示制御部（１０６）と、を備える。
2013125019.tif 000002
【特許請求の範囲】
【請求項１】
地図情報により特定される複数の領域を用いて移動体の到達可能範囲に関する情報を処理する画像処理装置であって、
前記移動体の現在位置に関する情報、前記移動体が保有するエネルギー量に関する情報、および、前記移動体が所定区間を走行する際に消費するエネルギー量に関する情報を取得する取得手段と、
前記取得手段により取得された情報に基づき、前記複数の領域を地図情報により特定する領域特定手段と、
前記領域特定手段により前記複数の領域が特定された後、前記取得手段により取得された情報に基づき、前記複数の領域に前記移動体が到達可能であるか否かを探索する探索手段と、
前記探索手段により探索された複数の領域を表示手段に表示させる表示制御手段と、
を備えることを特徴とする画像処理装置。
【請求項２】
前記領域特定手段は、前記移動体のエネルギー消費率の最大値および前記移動体が保有するエネルギー量に基づき、前記複数の領域を特定することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記領域特定手段は、前記取得手段により取得される所定区間を走行する際に消費するエネルギー量に関する情報を前記移動体の速度を変えながら取得し、前記エネルギー消費率の最大値を取得することを特徴とする請求項２に記載の画像処理装置。
【請求項４】
地図情報により特定される複数の領域を用いて移動体の到達可能範囲に関する情報を処理する画像処理方法であって、
前記移動体の現在位置に関する情報、前記移動体が保有するエネルギー量に関する情報、および、前記移動体が所定区間を走行する際に消費するエネルギー量に関する情報を取得する取得工程と、
前記取得工程により取得された情報に基づき、前記複数の領域を地図情報により特定する領域特定工程と、
前記領域特定工程により前記複数の領域が特定された後、前記取得工程により取得された情報に基づき、前記複数の領域に前記移動体が到達可能であるか否かを探索する探索工程と、
前記探索工程により探索された複数の領域を表示手段に表示させる表示制御工程と、
を含むことを特徴とする画像処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、移動体の残存エネルギー量に基づいて移動体の到達可能範囲を生成する画像処理装置および画像処理方法に関する。ただし、この発明の利用は、画像処理装置および画像処理方法に限らない。
【背景技術】
【０００２】
従来、移動体の現在地点に基づいて、移動体の到達可能範囲を生成する処理装置が知られている（たとえば、下記特許文献１参照。）。下記特許文献１では、移動体の現在地点を中心に地図上の全方位を放射状に分割し、分割領域ごとに移動体の現在地点から最も遠い到達可能な交差点を地図情報のノードとして取得する。そして、取得した複数のノードを結んで得られるベジュ曲線を移動体の到達可能範囲として表示している。【０００３】
また、移動体のバッテリー残容量および電力消費量に基づいて、各道路における移動体の現在地点からの到達可能範囲を生成する処理装置が知られている（たとえば、下記特許文献２参照。）。下記特許文献２では、移動体の現在地点に接続する複数の道路において移動体の電力消費量を算出し、移動体のバッテリー残容量および電力消費量に基づいて各道路における移動体の走行可能距離を算出する。そして、移動体の現在地点と、当該現在地点から走行可能距離だけ離れた移動体の複数の到達可能地点とを地図情報のノードとして取得し、複数のノードを結んで得られる線分の集合体を移動体の到達可能範囲として表示している。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平１１−０１６０９４号公報
【特許文献２】特開平０７−０８５３９７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した特許文献１の技術では、移動体の現在地点を中心に各方位における移動体から最も遠い到達地点のみを取得しているので、移動体の到達可能範囲の輪郭しか得られない。このため、移動体の現在地点と移動体から最も遠い到達地点との間に、海や湖など移動体が走行することのできない領域が含まれていたとしても、この移動体が走行することのできない領域を除外して移動体の到達可能範囲を取得することができないという問題点が一例として挙げられる。【０００６】
また、上述した特許文献２の技術では、移動体の到達可能範囲として道路のみを取得しているので、道路以外の範囲を移動体の到達可能範囲に含めることができない。また、移動体の到達可能範囲が移動体の走行可能な道路に沿った線分の集合体で表示されるので、到達可能範囲の輪郭を取得することができない。このため、移動体の到達可能範囲を見やすく、かつ漏れなく表示することが困難であるという問題点が一例として挙げられる。【０００７】
さらに、上述の各文献では、移動体が到達可能な範囲のノードをすべて探索するため、探索処理に時間がかかるという問題点を挙げることができる。特に、到達可能な領域の表示を効率的に画像処理し、短時間で高速に表示することができなかった。
【課題を解決するための手段】
【０００８】
上述した課題を解決し、目的を達成するため、請求項１の発明にかかる画像処理装置は、地図情報により特定される複数の領域を用いて移動体の到達可能範囲に関する情報を処理する画像処理装置であって、前記移動体の現在位置に関する情報、前記移動体が保有するエネルギー量に関する情報、および、前記移動体が所定区間を走行する際に消費するエネルギー量に関する情報を取得する取得手段と、前記取得手段により取得された情報に基づき、前記複数の領域を地図情報により特定する領域特定手段と、前記領域特定手段により前記複数の領域が特定された後、前記取得手段により取得された情報に基づき、前記複数の領域に前記移動体が到達可能であるか否かを探索する探索手段と、前記探索手段により探索された複数の領域を表示手段に表示させる表示制御手段と、を備えることを特徴とする。【０００９】
また、請求項４の発明にかかる画像処理方法は、地図情報により特定される複数の領域を用いて移動体の到達可能範囲に関する情報を処理する画像処理方法であって、前記移動体の現在位置に関する情報、前記移動体が保有するエネルギー量に関する情報、および、前記移動体が所定区間を走行する際に消費するエネルギー量に関する情報を取得する取得工程と、前記取得工程により取得された情報に基づき、前記複数の領域を地図情報により特定する領域特定工程と、前記領域特定工程により前記複数の領域が特定された後、前記取得工程により取得された情報に基づき、前記複数の領域に前記移動体が到達可能であるか否かを探索する探索工程と、前記探索工程により探索された複数の領域を表示手段に表示させる表示制御工程と、を含むことを特徴とする。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施の形態１にかかる画像処理装置の機能的構成の一例を示すブロック図である。
【図２】図２は、画像処理装置による画像処理の手順の一例を示すフローチャートである。
【図３】図３は、ナビゲーション装置のハードウェア構成の一例を示すブロック図である。
【図４】図４は、メッシュデータと到達可能ノードとの関係を説明する図である。
【図５−１】図５−１は、ナビゲーション装置による到達可能地点探索の一例について模式的に示す説明図である。
【図５−２】図５−２は、ナビゲーション装置による到達可能地点探索の一例について模式的に示す説明図である。
【図５−３】図５−３は、ナビゲーション装置による到達可能地点探索の一例について模式的に示す説明図である。
【図５−４】図５−４は、ナビゲーション装置による到達可能地点探索の一例について模式的に示す説明図である。
【図６】図６は、ナビゲーション装置による到達可能地点探索の一例について示す説明図である。
【図７】図７は、ナビゲーション装置による到達可能地点をメッシュデータで示す一例の説明図である。
【図８】図８は、ナビゲーション装置によるクローニング処理の一例を示す説明図である。
【図９】図９は、ナビゲーション装置によるオープニング処理の一例を示す説明図である。
【図１０】図１０は、ナビゲーション装置による車両の到達可能範囲抽出の一例を模式的に示す説明図である。
【図１１】図１１は、ナビゲーション装置による車両の到達可能範囲抽出後のメッシュデータの一例を模式的に示す説明図である。
【図１２】図１２は、ナビゲーション装置による車両の到達可能範囲抽出の別の一例について模式的に示す説明図である。
【図１３】図１３は、ナビゲーション装置による画像処理の手順の一例を示すフローチャートである。
【図１４】図１４は、ナビゲーション装置による推定消費電力量算出処理の手順の一例を示すフローチャートである。
【図１５−１】図１５−１は、ナビゲーション装置によるメッシュ作成処理の手順の一例を示すフローチャートである。
【図１５−２】図１５−２は、ナビゲーション装置によるメッシュ作成処理を説明する図である。
【図１６−１】図１６−１は、ナビゲーション装置による到達可能地点探索処理の手順の一例を示すフローチャートである（その１）。
【図１６−２】図１６−２は、ナビゲーション装置による到達可能地点探索処理の手順の一例を示すフローチャートである（その２）。
【図１６−３】図１６−３は、注目したリンクを候補に加えるか判断処理する手順の一例を示すフローチャートである。
【図１７−１】図１７−１は、ナビゲーション装置による到達可能範囲輪郭抽出処理の手順の一例を示すフローチャートである（その１）。
【図１７−２】図１７−２は、ナビゲーション装置による到達可能範囲輪郭抽出処理の手順の一例を示すフローチャートである（その２）。
【図１８】図１８は、勾配がある道路を走行する車両にかかる加速度の一例を模式的に示した説明図である。
【図１９】図１９は、ナビゲーション装置による到達可能地点探索処理後の表示例の一例について示す説明図である。
【図２０】図２０は、ナビゲーション装置による識別情報付与処理後の表示例の一例について示す説明図である。
【図２１】図２１は、ナビゲーション装置によるクローニング処理（膨張）後の表示例の一例について示す説明図である。
【図２２】図２２は、ナビゲーション装置によるクローニング処理（縮小）後の表示例の一例について示す説明図である。
【発明を実施するための形態】
【００１１】
以下に添付図面を参照して、この発明にかかる画像処理装置および画像処理方法の好適な実施の形態を詳細に説明する。
【００１２】
（実施の形態１）
図１は、実施の形態１にかかる画像処理装置の機能的構成の一例を示すブロック図である。実施の形態１にかかる画像処理装置１００は、移動体の残存エネルギー量に基づいて探索された移動体の到達可能地点に基づいて移動体の到達可能範囲を生成し表示部１１０に表示させる。また、画像処理装置１００は、取得部１０１、領域特定部１０３、探索部１０４、変更部１０５、表示制御部１０６によって構成される。
【００１３】
ここで、エネルギーとは、たとえば、ＥＶ（Ｅｌｅｃｔｒｉｃ  Ｖｅｈｉｃｌｅ）車などの場合、電気などに基づくエネルギーであり、ＨＶ（Ｈｙｂｒｉｄ  Ｖｅｈｉｃｌｅ）車、ＰＨＶ（Ｐｌｕｇ−ｉｎ  Ｈｙｂｒｉｄ  Ｖｅｈｉｃｌｅ）車などの場合は電気などに基づくエネルギーおよび、たとえばガソリンや軽油、ガスなどに基づくエネルギーである。また、エネルギーとは、たとえば燃料電池車の場合、電気などに基づくエネルギーおよび、たとえば水素や水素原料になる化石燃料などである（以下、ＥＶ車、ＨＶ車、ＰＨＶ車、燃料電池車は単に「ＥＶ車」という）。また、エネルギーとは、たとえば、ガソリン車、ディーゼル車など（以下、単に「ガソリン車」という）の場合、たとえば、ガソリンや軽油、ガスなどに基づくエネルギーである。たとえば残存エネルギーとは、たとえば、移動体の燃料タンクやバッテリー内、高圧タンクなどに残っているエネルギーであり、後の移動体の走行に用いることのできるエネルギーである。
【００１４】
取得部１０１は、画像処理装置１００を搭載した移動体の現在地点に関する情報や、移動体の現在地点において当該移動体が保有するエネルギー量である初期保有エネルギー量に関する情報を取得する。具体的には、取得部１０１は、たとえば、ＧＰＳ衛星から受信したＧＰＳ情報などを用いて、自装置の現在位置を算出することによって現在地点に関する情報（位置情報）を取得する。
【００１５】
また、取得部１０１は、たとえば、ＣＡＮ（Ｃｏｎｔｒｏｌｌｅｒ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）など通信プロトコルによって動作する車内通信網を介して、エレクトロニックコントロールユニット（ＥＣＵ：Ｅｌｅｃｔｒｏｎｉｃ  Ｃｏｎｔｒｏｌ  Ｕｎｉｔ）によって管理されている移動体の残存エネルギー量を、初期保有エネルギー量として取得する。
【００１６】
取得部１０１は、移動体の速度に関する情報や、渋滞情報、移動体情報を取得してもよい。移動体の速度に関する情報とは、移動体の速度、加速度である。また、取得部１０１は、たとえば、記憶部（不図示）に記憶された地図情報から道路に関する情報を取得してもよいし、傾斜センサなどから道路勾配などを取得してもよい。道路に関する情報とは、たとえば、道路種別や、道路勾配、路面状況などにより移動体に生じる走行抵抗である。
【００１７】
さらに、取得部１０１は、移動体が所定区間を走行する際に消費するエネルギーである推定エネルギー消費量を取得する。所定区間とは、たとえば、道路上の一の所定地点（以下、「ノード」とする）と当該一のノードに隣り合う他のノードとを結ぶ区間（以下、「リンク」とする）である。ノードとは、たとえば、交差点やスタンドであってもよいし、所定の距離で区切られたリンク間の接続地点であってもよい。ノードおよびリンクは、記憶部に記憶された地図情報を構成する。地図情報は、たとえば、交差点（点）、道路（線や曲線）、領域（面）やこれらを表示する色などを数値化したベクタデータで構成される。
【００１８】
具体的には、取得部１０１は、第一情報と、第二情報と、第三情報と、を含む消費エネルギー推定式に基づいて、所定区間における推定エネルギー消費量を推定する。より具体的には、取得部１０１は、移動体の速度に関する情報や移動体情報に基づいて、所定区間における推定エネルギー消費量を推定する。移動体情報とは、移動体の重量（乗車人数や積載荷物による重量も含む）、回転体の重量など、移動体走行時に消費または回収されるエネルギー量を変化させる要因となる情報である。なお、道路勾配が明らかな場合、取得部１０１は、さらに第四情報を加えた消費エネルギー推定式に基づいて、所定区間における推定エネルギー消費量を推定してもよい。
【００１９】
消費エネルギー推定式とは、所定区間における移動体のエネルギー消費量を推定する推定式である。具体的には、消費エネルギー推定式は、エネルギー消費量を増減させる異なる要因である第一情報、第二情報および第三情報を含む多項式である。また、道路勾配が明らかな場合、消費エネルギー推定式には、さらに第四情報が加えられる。消費エネルギー推定式についての詳細な説明は後述する。
【００２０】
第一情報は、移動体に備えられた装備品により消費されるエネルギーに関する情報である。また、移動体の加減速時を含む走行時および停止時に消費されるエネルギーに関する情報である。
【００２１】
具体的には、第一情報は移動体の走行に関係しない要因で消費されるエネルギー量である。より具体的には、第一情報は移動体に備えられたエアコン、カーオーディオ、ヘッドライト、ウインカー、ブレーキポンプなどの装備品によって消費されるエネルギー量である。
【００２２】
第二情報は、移動体の加減速時に消費および回収されるエネルギーに関する情報である。移動体の加減速時とは、移動体の速度が時間的に変化している走行状態である。具体的には、移動体の加減速時とは、所定時間内において、移動体の速度が変化する走行状態である。所定時間とは、一定間隔の時間の区切りであり、たとえば、単位時間当たりなどである。回収されるエネルギーとは、ＥＶ車の場合、たとえば、移動体の走行時にバッテリーに充電される電力である。また、回収されるエネルギーとは、ガソリン車の場合、たとえば、消費される燃料を低減（燃料カット）し節約することのできる燃料である。
【００２３】
第三情報は、移動体の走行時に生じる抵抗により消費されるエネルギーに関する情報である。移動体の走行時とは、所定時間内において、移動体の速度が一定、加速もしくは減速している走行状態である。移動体の走行時に生じる抵抗とは、移動体の走行時に移動体の走行状態を変化させる要因である。具体的には、移動体の走行時に生じる抵抗とは、気象状況、道路状況、車両状況などにより移動体に生じる各種抵抗である。
【００２４】
気象状況により移動体に生じる抵抗とは、たとえば、雨、風などの気象変化による空気抵抗である。道路状況により移動体に生じる抵抗とは、道路勾配、路面の舗装状態、路面上の水などによる路面抵抗である。車両状況により移動体に生じる抵抗とは、タイヤの空気圧、乗車人数、積載重量などにより移動体にかかる負荷抵抗である。
【００２５】
具体的には、第三情報は、空気抵抗や路面抵抗、負荷抵抗を受けた状態で、移動体を一定速度、加速もしくは減速で走行させたときのエネルギー消費量である。より具体的には、第三情報は、たとえば、向かい風により移動体に生じる空気抵抗や、舗装されていない道路から受ける路面抵抗などを、移動体が一定速度、加速もしくは減速で走行するときに消費されるエネルギー消費量である。
【００２６】
第四情報は、移動体が位置する高度の変化により消費および回収されるエネルギーに関する情報である。移動体が位置する高度の変化とは、移動体の位置する高度が時間的に変化している状態である。具体的には、移動体が位置する高度の変化とは、所定時間内において、移動体が勾配のある道路を走行することにより高度が変化する走行状態である。
【００２７】
また、第四情報は、所定区間内における道路勾配が明らかな場合に求めることができる付加的な情報であり、これによりエネルギー消費量の推定精度を向上することができる。なお、道路の傾斜が不明な場合、または計算を簡略化する場合、移動体が位置する高度の変化はないものとして、後述する消費エネルギー推定式における道路勾配θ＝０としてエネルギー消費量を推定することができる。
【００２８】
領域特定部１０３は、到達可能範囲を表示するために後述する画像処理をおこなう際に用いるデータの領域を決定するとともに、このデータを複数の領域に分割する。具体的には、地図情報を複数の領域に分割する。表示制御部１０６は、この領域特定部１０３で分割された複数の領域に基づき表示部１１０上に到達可能範囲を表示する。
【００２９】
より具体的には、領域特定部１０３は、取得部１０１により取得された車両の単位距離あたりのエネルギー消費量を示すエネルギー消費率が最もよいときのエネルギー消費率を用い、このエネルギー消費率の最大値と、蓄積しているエネルギー量とに基づき、車両が到達できる到達可能範囲を決定する。そして、この最大到達範囲を外接円として含む正方形状のメッシュデータを最大範囲とする。
【００３０】
領域特定部１０３は、分割数決定部１０３ａを有する。分割数決定部１０３ａは、この最大範囲を複数ｎ等分したときの一の領域の大きさを、地図情報を複数の領域に分割したときの一の領域の大きさとし、地図情報をｍ×ｍ画素のメッシュデータに分割する。このとき、メッシュデータの周辺のたとえば４画素分を空白にするために、ｎ＝（ｍ／２）−４とする。
【００３１】
探索部１０４は、記憶部に記憶された地図情報、取得部１０１によって取得された移動体の現在地点および初期保有エネルギー量、ならびに取得部１０１によって取得された推定エネルギー消費量に基づいて、移動体が現在地点から到達可能な地点である複数の到達可能地点を探索する。
【００３２】
具体的には、探索部１０４は、移動体の現在地点から移動可能なすべての経路において、それぞれ、移動体の現在地点を始点とし、移動体からの経路上の所定地点同士を結ぶ所定区間における推定エネルギー消費量の累計が最小となるように所定地点および所定区間を探索する。
【００３３】
より具体的には、探索部１０４は、移動体の現在地点を始点として、移動体の現在地点から移動可能なすべてのリンク、これらのリンクにそれぞれ接続するノード、これらのノードから移動可能なすべてのリンクと、移動体の到達可能なすべてのノードおよびリンクを順に探索する。このとき、探索部１０４は、新たな一のリンクを探索するごとに、一のリンクが接続する経路の推定エネルギー消費量を累計し、推定エネルギー消費量の累計が最小となるように当該一のリンクに接続するノードおよびこのノードに接続する複数のリンクを探索する。
【００３４】
たとえば、探索部１０４は、当該一のリンクおよび他のリンクが同一のノードに接続されている場合、このノードに接続する複数のリンクのうち、移動体の現在地点から当該ノードまでの推定エネルギー消費量の累計の少ないリンクの推定エネルギー消費量を使って当該ノードの推定エネルギー消費量の累計を算出する。このように推定エネルギー消費量の少ないリンクの推定エネルギー消費量を使うことにより、当該ノードの推定エネルギー消費量の正しい累計を算出することができる。
【００３５】
そして、探索部１０４は、探索されたノードおよびリンクで構成される複数の経路において、それぞれ、推定エネルギー消費量の累計が移動体の初期保有エネルギー量の範囲内にあるすべてのノードを移動体の到達可能地点として探索対象とする。
【００３６】
また、探索部１０４は、移動体の移動が禁止された所定区間を、移動体の到達可能地点を探索するための候補から除いて当該到達可能地点を探索してもよい。移動体の移動が禁止された所定区間とは、たとえば、一方通行の逆走となるリンク、時間規制や季節規制により通行禁止区間となるリンクである。時間規制とは、たとえば、通学路や行事などに設定されることにより、ある時間帯で通行が禁止されることである。季節規制とは、たとえば、大雨や大雪などにより通行が禁止されることである。
【００３７】
探索部１０４は、複数の所定区間のうち、一の所定区間の次に選択する他の所定区間の重要度が当該一の所定区間の重要度よりも低い場合、他の所定区間を、移動体の到達可能地点を探索するための候補から除いて当該到達可能地点を探索してもよい。所定区間の重要度とは、たとえば、道路種別などである。道路種別とは、法定速度や、道路の勾配、道路幅、信号の有無などの道路状態の違いにより区別することのできる道路の種類である。具体的には、道路種別とは、一般国道、高速道路、一般道路、市街地などを通る細街路などである。細街路とは、たとえば、市街地内にある幅員４メートル未満の建築基準法に規定された道路である。
【００３８】
探索部１０４は、付与部１０４ａを有する。付与部１０４ａは、探索部１０４によって探索された複数の到達可能地点に基づいて、領域特定部１０３によって分割された複数の領域にそれぞれ移動体が到達可能であるか否かを識別する識別情報を付与する。具体的には、付与部１０４ａは、領域特定部１０３によって分割された一の領域に移動体の到達可能地点が含まれる場合、その一の領域に移動体が到達可能であることを識別する到達可能の識別情報を付与する。その後、付与部１０４ａは、領域特定部１０３によって分割された一の領域に移動体の到達可能地点が含まれない場合、その一の領域に移動体が到達不可能であることを識別する到達不可能の識別情報を付与する。
【００３９】
より具体的には、付与部１０４ａは、ｍ×ｍに分割されたメッシュデータの各領域に、到達可能の識別情報「１」または到達不可能の識別情報「０」を付与することで、ｍ行ｍ列の２次元行列データのメッシュデータに変換する。領域特定部１０３および付与部１０４ａは、このように地図情報を分割してｍ行ｍ列の２次元行列データのメッシュデータに変換し、２値化されたラスタデータとして扱う。
【００４０】
変更部１０５は、領域特定部１０３によって分割された複数の領域に対して識別情報の変更処理をおこなう第１変更部１０５ａおよび第２変更部１０５ｂを備える。具体的には、変更部１０５は、第１変更部１０５ａおよび第２変更部１０５ｂによって、地図情報が分割されてなるメッシュデータを２値化されたラスタデータとして扱い、クローニング処理（膨張処理後に縮小処理をおこなう処理）をおこなう。また、変更部１０５は、第１変更部１０５ａおよび第２変更部１０５ｂによって、オープニング処理（縮小処理後に膨張処理をおこなう処理）をおこなってもよい。
【００４１】
具体的には、第１変更部１０５ａは、識別情報が付与された一の領域に隣り合う他の領域に到達可能の識別情報が付与されている場合、当該一の領域の識別情報を到達可能の識別情報に変更する（膨張処理）。より具体的には、第１変更部１０５ａは、矩形状の一の領域の、左下、下、右下、右、右上、上、左上、左の８方向に隣り合う他の領域のうちのいずれかの領域に到達可能の識別情報である「１」が付与されている場合、当該一の領域の識別情報を「１」に変更する。
【００４２】
第２変更部１０５ｂは、第１変更部１０５ａによる識別情報の変更後、識別情報が付与された一の領域に隣り合う他の領域に到達不可能の識別情報が付与されている場合、当該一の領域の識別情報を到達不可能の識別情報に変更する（縮小処理）。より具体的には、第２変更部１０５ｂは、矩形状の一の領域の、左下、下、右下、右、右上、上、左上、左の８方向に隣り合う他の領域のうちのいずれかの領域に到達不可能の識別情報である「０」が付与されている場合、当該一の領域の識別情報を「０」に変更する。第１変更部１０５ａによる膨張処理と、第２変更部１０５ｂによる縮小処理は、同じ回数ずつおこなう。
【００４３】
このように、付与部１０４ａは、領域特定部１０３によって分割された複数の領域のうち、移動体が現在地点から到達可能な地点である到達可能地点を含む領域に、当該移動体が到達可能であることを識別する到達可能の識別情報を付与して当該移動体の到達可能範囲とする。その後、変更部１０５は、到達可能の識別情報を付与した領域に隣り合う領域にも到達可能の識別情報を付与し、移動体の到達可能範囲に欠損点が生じないように各領域の識別情報を変更する。
【００４４】
表示制御部１０６は、変更部１０５によって識別情報が付与された領域の識別情報に基づいて、移動体の到達可能範囲を地図情報とともに表示部１１０に表示させる。具体的には、表示制御部１０６は、変更部１０５によって識別情報が付与された複数の画像データであるメッシュデータをベクタデータに変換し、記憶部に記憶された地図情報とともに表示部１１０に表示させる。また、表示制御部１０６は、付与部１０４ａによって識別情報が付与された領域の識別情報に基づいて、移動体の到達可能範囲を地図情報とともに表示部に表示させてもよい。
【００４５】
つぎに、画像処理装置１００による画像処理について説明する。図２は、画像処理装置による画像処理の手順の一例を示すフローチャートである。図２のフローチャートにおいて、画像処理装置１００は、まず、取得部１０１によって、移動体の現在地点に関する情報、および、移動体の現在地点において移動体が保有するエネルギー量である初期保有エネルギー量に関する情報、を取得する（ステップＳ２０１，Ｓ２０２）。このとき、画像処理装置１００は、移動体情報も取得してもよい。
【００４６】
そして、画像処理装置１００は、取得部１０１によって、移動体が所定区間を走行する際に消費するエネルギーである推定エネルギー消費量を取得する（ステップＳ２０３）。このとき、画像処理装置１００は、移動体の経路上の所定地点同士を結ぶ複数の所定区間における推定エネルギー消費量をそれぞれ算出する。
【００４７】
つぎに、画像処理装置１００は、領域特定部１０３により、ベクタデータからなる地図情報を複数の領域に分割し、ラスタデータからなるメッシュデータに変換し、メッシュデータの最大範囲とメッシュデータの分割数とを決める（ステップＳ２０４）。この際、領域特定部１０３は、取得部１０１により取得された車両のエネルギー消費率が最もよいときのエネルギー消費率を用い、このエネルギー消費率の最大値と、蓄積しているエネルギー量とに基づき、車両が到達できる最大到達範囲を決定する。また、分割数決定部１０３ａにより、メッシュデータを所定数に分割する。
【００４８】
この後、探索部１０４によって、記憶部に記憶された地図情報と、ステップＳ２０２，Ｓ２０３において取得した初期保有エネルギー量および推定エネルギー消費量とに基づいて、移動体の複数の到達可能地点を探索する（ステップＳ２０５）。
【００４９】
つぎに、画像処理装置１００は、ステップＳ２０５において探索した複数の到達可能地点に基づいて、ステップＳ２０４において分割した複数の領域にそれぞれ、付与部１０４ａによって到達可能の識別情報を付与する（ステップＳ２０６）。その後、画像処理装置１００は、ステップＳ２０６において識別情報を付与した複数の領域の識別情報に基づいて、表示制御部１０６によって移動体の到達可能範囲を表示部１１０に表示させ（ステップＳ２０７）、以上の処理を終了する。
【００５０】
以上説明したように、実施の形態１にかかる画像処理装置１００は、地図情報を複数の領域に分割して各領域ごとに移動体が到達可能か否かを探索し、各領域にそれぞれ移動体が到達可能であることを識別する到達可能の識別情報を付与する。そして、画像処理装置１００は、到達可能の識別情報が付与された領域に基づいて移動体の到達可能範囲を生成する。このため、画像処理装置１００は、海や湖、山脈など移動体の走行不可能な領域を除いた状態で移動体の到達可能範囲を生成することができる。したがって、画像処理装置１００は、移動体の到達可能範囲を正確に表示することができる。
【００５１】
また、画像処理装置１００は、地図情報を分割した複数の領域を画像データに変換し、当該複数の領域にそれぞれ到達可能の識別情報を付与した後、クローニングの膨張処理をおこなう。このため、画像処理装置１００は、移動体の到達可能範囲内の欠損点を除去することができる。
【００５２】
また、画像処理装置１００は、地図情報を分割した複数の領域を画像データに変換し、当該複数の領域にそれぞれ到達可能の識別情報を付与した後、オープニングの縮小処理をおこなう。このため、画像処理装置１００は、移動体の到達可能範囲の孤立点を除去することができる。
【００５３】
このように、画像処理装置１００は、移動体の到達可能範囲の欠損点や孤立点を除去することができるので、移動体の走行可能範囲を２次元のなめらかな面でかつ見やすく表示することができる。また、画像処理装置１００は、地図情報を複数の領域に分割して生成したメッシュデータの輪郭を抽出する。このため、画像処理装置１００は、移動体の到達可能範囲の輪郭をなめらかに表示することができる。
【００５４】
また、画像処理装置１００は、移動体の到達可能地点を探索する道路を絞り込んで、移動体の到達可能地点を探索する。このため、画像処理装置１００は、移動体の到達可能地点を探索する際の処理量を低減することができる。移動体の到達可能地点を探索する道路を絞り込むことで、探索可能な到達可能地点が少なくなったとしても、上述したようにクローニングの膨張処理がおこなわれることにより、移動体の到達可能範囲内に生じる欠損点を除去することができる。したがって、画像処理装置１００は、移動体の到達可能範囲を生成するための処理量を低減することができる。また、画像処理装置１００は、移動体の走行可能範囲を２次元のなめらかな面で見やすく表示することができる。
【００５５】
また、先に領域特定部１０３において、車両が到達できる最大到達範囲のメッシュデータと、分割数とを決定する処理をおこなう。そして、この後に探索部１０４により移動体の現在地点から移動可能なすべての経路において、領域特定部１０３において分割されたメッシュに到達可能なノードがあるか否かを探索する処理を付与部１０４ａにておこなう。これにより、全体処理時間を短縮でき、また、到達可能なすべてのノード情報を記憶部に格納する必要がなくメモリ量を減らすことができる。
【００５６】
最大消費メモリ量は、メッシュの数で決まる。たとえばｍ×ｍ画素が１００×１００であれば、１万ノード分のメモリがあればよい。これに対し、車両が到達できる最大到達範囲のメッシュデータを領域特定部１０３で決定せずに、到達可能なすべてのノード情報から決定する場合、その到達可能なすべてのノード情報を記憶部に格納する必要が生じ、ノード探索において計算した量に比例してメモリを消費するため、到達可能範囲が遠くなるほど、必要なメモリ量が増大するものとなる。このように、実施の形態によれば、探索時に必要なメモリ量を大幅に少なくすることができ、短時間で処理結果を表示出力できるようになる。
【実施例１】
【００５７】
以下に、本発明の実施例１について説明する。本実施例では、車両に搭載されるナビゲーション装置３００を画像処理装置１００として、本発明を適用した場合の一例について説明する。【００５８】
（ナビゲーション装置３００のハードウェア構成）
つぎに、ナビゲーション装置３００のハードウェア構成について説明する。図３は、ナビゲーション装置のハードウェア構成の一例を示すブロック図である。図３において、ナビゲーション装置３００は、ＣＰＵ３０１、ＲＯＭ３０２、ＲＡＭ３０３、磁気ディスクドライブ３０４、磁気ディスク３０５、光ディスクドライブ３０６、光ディスク３０７、音声Ｉ／Ｆ（インターフェース）３０８、マイク３０９、スピーカ３１０、入力デバイス３１１、映像Ｉ／Ｆ３１２、ディスプレイ３１３、カメラ３１４、通信Ｉ／Ｆ３１５、ＧＰＳユニット３１６、各種センサ３１７を備えている。各構成部３０１〜３１７は、バス３２０によってそれぞれ接続されている。【００５９】
ＣＰＵ３０１は、ナビゲーション装置３００の全体の制御を司る。ＲＯＭ３０２は、ブートプログラム、推定エネルギー消費量算出プログラム、到達可能地点探索プログラム、識別情報付与プログラム、地図データ表示プログラムなどのプログラムを記録している。ＲＡＭ３０３は、ＣＰＵ３０１のワークエリアとして使用される。すなわち、ＣＰＵ３１は、ＲＡＭ３０３をワークエリアとして使用しながら、ＲＯＭ３０２に記録された各種プログラムを実行することによって、ナビゲーション装置３００の全体の制御を司る。【００６０】
推定エネルギー消費量算出プログラムでは、車両の推定エネルギー消費量を算出する消費エネルギー推定式に基づいて、一のノードと隣り合うノードとを結ぶリンクにおける推定エネルギー消費量を算出する。到達可能地点探索プログラムでは、推定プログラムにおいて算出された推定エネルギー消費量に基づいて、車両の現在地点での残存エネルギー量で到達可能な複数の地点（ノード）が探索される。識別情報付与プログラムでは、探索プログラムにおいて探索された複数の到達可能地点に基づいて、地図情報を分割した複数の領域に、車両が到達可能であることを識別する識別情報が付与される。地図データ表示プログラムでは、識別情報付与プログラムによって識別情報が付与された複数の領域に基づいて、車両の到達可能範囲をディスプレイ３１３に表示させる。【００６１】
磁気ディスクドライブ３０４は、ＣＰＵ３０１の制御にしたがって磁気ディスク３０５に対するデータの読み取り／書き込みを制御する。磁気ディスク３０５は、磁気ディスクドライブ３０４の制御で書き込まれたデータを記録する。磁気ディスク３０５としては、たとえば、ＨＤ（ハードディスク）やＦＤ（フレキシブルディスク）を用いることができる。【００６２】
また、光ディスクドライブ３０６は、ＣＰＵ３０１の制御にしたがって光ディスク３０７に対するデータの読み取り／書き込みを制御する。光ディスク３０７は、光ディスクドライブ３０６の制御にしたがってデータが読み出される着脱自在な記録媒体である。光ディスク３０７は、書き込み可能な記録媒体を利用することもできる。着脱可能な記録媒体として、光ディスク３０７のほか、ＭＯ、メモリカードなどを用いることができる。【００６３】
磁気ディスク３０５および光ディスク３０７に記録される情報の一例としては、地図データ、車両情報、道路情報、走行履歴などが挙げられる。地図データは、カーナビゲーションシステムにおいて車両の到達可能地点を探索するときや、車両の到達可能範囲を表示するときに用いられ、建物、河川、地表面などの地物（フィーチャ）を表す背景データ、道路の形状をリンクやノードなどで表す道路形状データなどを含むベクタデータである。【００６４】
音声Ｉ／Ｆ３０８は、音声入力用のマイク３０９および音声出力用のスピーカ３１０に接続される。マイク３０９に受音された音声は、音声Ｉ／Ｆ３０８内でＡ／Ｄ変換される。マイク３０９は、たとえば、車両のダッシュボード部などに設置され、その数は単数でも複数でもよい。スピーカ３１０からは、所定の音声信号を音声Ｉ／Ｆ３０８内でＤ／Ａ変換した音声が出力される。【００６５】
入力デバイス３１１は、文字、数値、各種指示などの入力のための複数のキーを備えたリモコン、キーボード、タッチパネルなどが挙げられる。入力デバイス３１１は、リモコン、キーボード、タッチパネルのうちいずれか一つの形態によって実現されてもよいが、複数の形態によって実現することも可能である。【００６６】
映像Ｉ／Ｆ３１２は、ディスプレイ３１３に接続される。映像Ｉ／Ｆ３１２は、具体的には、たとえば、ディスプレイ３１３全体を制御するグラフィックコントローラと、即時表示可能な画像情報を一時的に記録するＶＲＡＭ（Ｖｉｄｅｏ  ＲＡＭ）などのバッファメモリと、グラフィックコントローラから出力される画像データに基づいてディスプレイ３１３を制御する制御ＩＣなどによって構成される。【００６７】
ディスプレイ３１３には、アイコン、カーソル、メニュー、ウインドウ、あるいは文字や画像などの各種データが表示される。ディスプレイ３１３としては、たとえば、ＴＦＴ液晶ディスプレイ、有機ＥＬディスプレイなどを用いることができる。【００６８】
カメラ３１４は、車両内部あるいは外部の映像を撮影する。映像は静止画あるいは動画のどちらでもよく、たとえば、カメラ３１４によって車両外部を撮影し、撮影した画像をＣＰＵ３０１において画像解析したり、映像Ｉ／Ｆ３１２を介して磁気ディスク３０５や光ディスク３０７などの記録媒体に出力したりする。【００６９】
通信Ｉ／Ｆ３１５は、無線を介してネットワークに接続され、ナビゲーション装置３００およびＣＰＵ３０１のインターフェースとして機能する。ネットワークとして機能する通信網には、ＣＡＮやＬＩＮ（Ｌｏｃａｌ  Ｉｎｔｅｒｃｏｎｎｅｃｔ  Ｎｅｔｗｏｒｋ）などの車内通信網や、公衆回線網や携帯電話網、ＤＳＲＣ（Ｄｅｄｉｃａｔｅｄ  Ｓｈｏｒｔ  Ｒａｎｇｅ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ）、ＬＡＮ、ＷＡＮなどがある。通信Ｉ／Ｆ３１５は、たとえば、公衆回線用接続モジュールやＥＴＣ（ノンストップ自動料金支払いシステム）ユニット、ＦＭチューナー、ＶＩＣＳ（Ｖｅｈｉｃｌｅ  Ｉｎｆｏｒｍａｔｉｏｎ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｙｓｔｅｍ）（登録商標）／ビーコンレシーバなどである。【００７０】
ＧＰＳユニット３１６は、ＧＰＳ衛星からの電波を受信し、車両の現在位置を示す情報を出力する。ＧＰＳユニット３１６の出力情報は、後述する各種センサ３１７の出力値とともに、ＣＰＵ３０１による車両の現在位置の算出に際して利用される。現在位置を示す情報は、たとえば、緯度・経度、高度などの、地図データ上の１点を特定する情報である。【００７１】
各種センサ３１７は、車速センサ、加速度センサ、角速度センサ、傾斜センサなどの、車両の位置や挙動を判断するための情報を出力する。各種センサ３１７の出力値は、ＣＰＵ３０１による車両の現在位置の算出や、速度や方位の変化量の算出に用いられる。【００７２】
図１に示した画像処理装置１００の取得部１０１、領域特定部１０３、探索部１０４、変更部１０５、表示制御部１０６は、上述したナビゲーション装置３００におけるＲＯＭ３０２、ＲＡＭ３０３、磁気ディスク３０５、光ディスク３０７などに記録されたプログラムやデータを用いて、ＣＰＵ３０１が所定のプログラムを実行し、ナビゲーション装置３００における各部を制御することによってその機能を実現する。【００７３】
（ナビゲーション装置３００による推定エネルギー消費量算出の概要）
本実施例のナビゲーション装置３００は、自装置が搭載された車両の推定エネルギー消費量を算出する。具体的には、ナビゲーション装置３００は、たとえば、速度、加速度、車両の勾配に基づいて、第一情報と、第二情報と、第三情報と、を含む消費エネルギー推定式のいずれか一つ以上の式を用いて、所定区間における車両の推定エネルギー消費量を算出する。所定区間とは、道路上の一のノード（たとえば交差点）と当該一のノードに隣り合う他のノードとを結ぶリンクである。【００７４】
より具体的には、ナビゲーション装置３００は、プローブで提供される渋滞情報や、サーバを介して取得した渋滞予測データ、記憶装置に記憶されたリンクの長さや道路種別などに基づいて、車両がリンクを走行し終わるのに要する旅行時間を算出する。そして、ナビゲーション装置３００は、次の（１）式〜（４）式に示す消費エネルギー推定式のいずれかを用いて単位時間当たりの推定エネルギー消費量を算出し、車両がリンクを旅行時間で走行し終える際の推定エネルギー消費量を算出する。【００７５】
【数１】
2013125019.tif 000003
【００７６】
【数２】
2013125019.tif 000004
【００７７】
上記（１）式に示す消費エネルギー推定式は、加速時および走行時における単位時間当たりの消費エネルギーを推定する理論式である。ここで、εは正味熱効率、ηは総伝達効率である。移動体の加速度αと道路勾配θから重力の加速度ｇとの合計を合成加速度｜α｜とすると、合成加速度｜α｜が負の場合の消費エネルギー推定式は、上記（２）式で表される。すなわち、上記（２）式に示す消費エネルギー推定式は、減速時における単位時間当たりの消費エネルギーを推定する理論式である。このように、加減速時および走行時における単位時間当たりの消費エネルギー推定式は、走行抵抗と走行距離と正味モータ効率と伝達効率との積で表される。【００７８】
上記（１）式および（２）式において、右辺第１項は、移動体に備えられた装備品により消費されるエネルギー消費量（第一情報）である。右辺第２項は、勾配成分によるエネルギー消費量（第四情報）および転がり抵抗成分によるエネルギー消費量（第三情報）である。右辺第３項は、空気抵抗成分によるエネルギー消費量（第三情報）である。また、（１）式の右辺第４項は、加速成分によるエネルギー消費量（第二情報）である。（２）式の右辺第４項は、減速成分によるエネルギー消費量（第二情報）である。【００７９】
上記（１）式および（２）式では、モータ効率と駆動効率は一定と見なしている。しかし、実際には、モータ効率および駆動効率はモータ回転数やトルクの影響により変動する。そこで、次の（３）式および（４）式に単位時間当たりの消費エネルギーを推定する実証式を示す。【００８０】
合成加速度｜α＋ｇ・ｓｉｎθ｜が正の場合の推定エネルギー消費量を算出する実証式、すなわち、加速時および走行時における単位時間当たりの推定エネルギー消費量を算出する実証式は、次の（３）式で表される。また、合成加速度｜α＋ｇ・ｓｉｎθ｜が負の場合の推定エネルギー消費量を算出する実証式、すなわち、減速時における単位時間当たりの推定エネルギー消費量を算出する実証式は、次の（４）式で表される。【００８１】
【数３】
2013125019.tif 000005
【００８２】
【数４】
2013125019.tif 000006
【００８３】
上記（３）式および（４）式において、係数ａ１，ａ２は、車両状況などに応じて設定される常数である。係数ｋ１は、加減速時を含む走行時および停止時におけるエネルギー消費量に基づく変数である。係数ｋ２，ｋ３は、加減速時を含む走行時におけるエネルギー消費量に基づく変数である。また、速度Ｖ、加速度Ａとしており、その他の変数は、上記（１）式および（２）式と同様である。右辺第１項は、上記（１）式および（２）式の右辺第１項に相当する。係数ｋ１は前述した燃費係数ｋ１に相当する。【００８４】
また、上記（３）式および（４）式において、右辺第２項は、上記（１）式および（２）式の、右辺第２項の勾配抵抗成分のエネルギーと、右辺第４項の加速度抵抗成分のエネルギーとに相当する。右辺第３項は、上記（１）式および（２）式の、右辺第２項の転がり抵抗成分のエネルギーと、右辺第３項の空気抵抗成分のエネルギーに相当する。（４）式の右辺第２項のβは、位置エネルギーと運動エネルギーの回収分（以下、「回収率」とする）である。【００８５】
また、ナビゲーション装置３００は、上述したように車両がリンクを走行するのに要する旅行時間を算出し、車両がリンクを走行するときの平均速度および平均加速度を算出する。そして、ナビゲーション装置３００は、リンクにおける車両の平均速度および平均加速度を用いて、次の（５）式または（６）式に示す消費エネルギー推定式に基づいて、車両がリンクを旅行時間で走行し終える際の推定エネルギー消費量を算出してもよい。【００８６】
【数５】
2013125019.tif 000007
【００８７】
【数６】
2013125019.tif 000008
【００８８】
上記（５）式に示す消費エネルギー推定式は、車両が走行するリンクの高度差Δｈが正の場合の、リンクにおける推定エネルギー消費量を算出する理論式である。高度差Δｈが正の場合とは、車両が上り坂を走行している場合である。上記（６）式に示す消費エネルギー推定式は、車両が走行するリンクの高度差Δｈが負の場合の、リンクにおける推定エネルギー消費量を算出する理論式である。高度差Δｈが負の場合とは、車両が下り坂を走行している場合である。高度差がない場合は、上記（５）式に示す消費エネルギー推定式を用いるのが好ましい。【００８９】
上記（５）式および（６）式において、右辺第１項は、移動体に備えられた装備品により消費されるエネルギー消費量（第一情報）である。右辺第２項は、加速抵抗によるエネルギー消費量（第二情報）である。右辺第３項は、位置エネルギーとして消費されるエネルギー消費量である（第四情報）。右辺第４項は、単位面積当たりに受ける空気抵抗および転がり抵抗（走行抵抗）によるエネルギー消費量（第三情報）である。【００９０】
ナビゲーション装置３００は、道路勾配が明らかでない場合、上記（１）式〜（６）式に示す消費エネルギー推定式の道路勾配θ＝０として車両の推定エネルギー消費量を算出してもよい。【００９１】
つぎに、上記（１）式〜（６）式で用いる回収率βについて説明する。上記（５）式において、右辺第２項をリンクにおける加速成分のエネルギー消費量Ｐａｃｃとすると、加速成分のエネルギー消費量Ｐａｃｃは、リンクにおける全エネルギー消費量（左辺）から、アイドリング時のエネルギー消費量（右辺第１項）と走行抵抗によるエネルギー消費量（右辺第４項）を減じたものであり、次の（７）式で表される。【００９２】
【数７】
2013125019.tif 000009
【００９３】
なお、上記（７）式では、車両は道路勾配θの影響を受けていないこととする（θ＝０）。すなわち、上記（５）式の右辺第３項をゼロとする。そして、上記（７）式を上記（５）式に代入することで、次の（８）式に示す回収率βの算出式を得ることができる。【００９４】
【数８】
2013125019.tif 000010
【００９５】
回収率βは、ＥＶ車では０．７〜０．９程度であり、ＨＶ車では０．６〜０．８程度であり、ガソリン車では０．２〜０．３程度である。なお、ガソリン車の回収率とは、加速時に要するエネルギーと減速時に回収するエネルギーとの割合である。【００９６】
（ナビゲーション装置３００におけるメッシュデータの範囲と到達可能ノードとの関係について）
図４は、メッシュデータと到達可能ノードとの関係を説明する図である。たとえば、分割された一つのメッシュデータの領域４０１があったとする。この領域４０１に対し、（ａ）に示すように探索結果、６つの到達可能ノードがある場合この領域４０１は到達可能範囲として表示されることになる。同様に、（ｂ）に示すように、探索結果、一つの到達可能ノードだけがある場合でも、この領域４０１は到達可能範囲として表示されることになる。【００９７】
このように、一つのメッシュの領域４０１を単位として到達可能、あるいは不可能の範囲として表示部１１０に表示する場合、一つの領域４０１内での到達可能ノード数は最低一つあればよく、複数あっても変わらない。また複数ある場合には領域４０１を到達可能ノードとして決定するまでの処理期間中、複数の到達可能ノードの情報をメモリに格納保持しておかねばならず、メモリ量が増大し、処理効率を向上できない。このため、この実施例では、一つの領域４０１内での到達可能ノード数は最低一つあればこの領域４０１に到達可能範囲の識別情報を付与し、探索部１０４はそれ以降も探索を続けるものの、複数の到達可能ノードの情報をメモリに格納保持しないこととする。【００９８】
（ナビゲーション装置３００における到達可能地点探索の概要）
本実施例のナビゲーション装置３００は、自装置が搭載された車両の現在地点から到達可能な複数のノードを車両の到達可能地点として探索する。具体的には、ナビゲーション装置３００は、上記（１）〜（６）式に示す消費エネルギー推定式のいずれか一つ以上を用いてリンクにおける推定エネルギー消費量を算出する。そして、ナビゲーション装置３００は、リンクにおける推定エネルギー消費量の累計が最小となるように車両の到達可能なノードを探索し到達可能地点とする。以下に、ナビゲーション装置３００による到達可能地点探索の一例について説明する。【００９９】
図５−１〜図５−４は、ナビゲーション装置３００による到達可能地点探索の一例について模式的に示す説明図である。図５−１〜図５−４では、地図データのノード（たとえば交差点）を丸印とし、隣り合うノード同士を結ぶリンク（道路上の所定区間）を線分で示す（図５−１，５−２についても同様にノードおよびリンクを図示）。【０１００】
図５−１に示すように、ナビゲーション装置３００は、まず、車両の現在地点５００から最も近いリンクＬ１＿１を探索する。そして、ナビゲーション装置３００は、リンクＬ１＿１に接続するノードＮ１＿１を探索し、到達可能地点を探索するためのノード候補（以下、単に「ノード候補」という）に追加する。【０１０１】
つぎに、ナビゲーション装置３００は、消費エネルギー推定式を用いて、車両の現在地点５００とノード候補としたノードＮ１＿１とを結ぶリンクＬ１＿１における推定エネルギー消費量を算出する。そして、ナビゲーション装置５００は、リンクＬ１＿１における推定エネルギー消費量３ｗｈを、たとえばノードＮ１＿１に関連付けて記憶装置（磁気ディスク３０５や光ディスク３０７）に書き出す。【０１０２】
つぎに、図５−２に示すように、ナビゲーション装置３００は、ノードＮ１＿１に接続するすべてのリンクＬ２＿１，Ｌ２＿２，Ｌ２＿３を探索し、到達可能地点を探索するためのリンク候補（以下、単に「リンク候補」という）とする。つぎに、ナビゲーション装置３００は、消費エネルギー推定式を用いて、リンクＬ２＿１における推定エネルギー消費量を算出する。【０１０３】
そして、ナビゲーション装置３００は、リンクＬ２＿１における推定エネルギー消費量４ｗｈとリンクＬ１＿１における推定エネルギー消費量３ｗｈとを累計した累計エネルギー量７ｗｈを、リンクＬ２＿１に接続するノードＮ２＿１に関連付けて記憶装置に書き出す（以下、「累計エネルギー量をノードに設定」とする）。【０１０４】
さらに、ナビゲーション装置３００は、リンクＬ２＿１の場合と同様に、消費エネルギー推定式を用いて、リンクＬ２＿２，Ｌ２＿３における推定エネルギー消費量をそれぞれ算出する。そして、ナビゲーション装置３００は、リンクＬ２＿２における推定エネルギー消費量５ｗｈとリンクＬ１＿１における推定エネルギー消費量３ｗｈとを累計した累計エネルギー量８ｗｈを、リンクＬ２＿２に接続するノードＮ２＿２に設定する。【０１０５】
また、ナビゲーション装置３００は、リンクＬ２＿３における推定エネルギー消費量３ｗｈとリンクＬ１＿１における推定エネルギー消費量３ｗｈとを累計した累計エネルギー量６ｗｈを、リンクＬ２＿３に接続するノードＮ２＿３に設定する。このとき、ナビゲーション装置３００は、累計エネルギー量を設定したノードがノード候補でない場合には、そのノードをノード候補に追加する。【０１０６】
つぎに、図５−３に示すように、ナビゲーション装置３００は、ノードＮ２＿１に接続するすべてのリンクＬ３＿１，Ｌ３＿２＿１、ノードＮ２＿２に接続するすべてのリンクＬ３＿２＿２，Ｌ３＿３，Ｌ３＿４、およびノードＮ２＿３に接続するリンクＬ３＿５を探索し、リンク候補とする。つぎに、ナビゲーション装置３００は、消費エネルギー推定式を用いて、リンクＬ３＿１〜リンクＬ３＿５における推定エネルギー消費量を算出する。【０１０７】
そして、ナビゲーション装置３００は、リンクＬ３＿１における推定エネルギー消費量４ｗｈをノードＮ２＿１に設定した累計エネルギー量７ｗｈに累計し、リンクＬ３＿１に接続するノードＮ３＿１に累計エネルギー量１１ｗｈを設定する。また、ナビゲーション装置３００は、リンクＬ３＿３〜Ｌ３＿５においてもリンクＬ３＿１の場合と同様に、各リンクＬ３＿３〜Ｌ３＿５にそれぞれ接続するノードＮ３＿３〜Ｎ３＿５に累計エネルギー量１３ｗｈ，１２ｗｈ，１０ｗｈを設定する。【０１０８】
具体的には、ナビゲーション装置３００は、リンクＬ３＿３における推定エネルギー消費量５ｗｈをノードＮ２＿２に設定した累計エネルギー量８ｗｈに累計し、ノードＮ３＿３に累計エネルギー量１３ｗｈを設定する。ナビゲーション装置３００は、リンクＬ＿３＿４における推定エネルギー消費量４ｗｈをノードＮ２＿２に設定した累計エネルギー量８ｗｈに累計し、ノードＮ３＿４に累計エネルギー量１２ｗｈを設定する。ナビゲーション装置３００は、リンクＬ３＿５における推定エネルギー消費量４ｗｈをノードＮ２＿３に設定した累計エネルギー量６ｗｈに累計し、ノードＮ３＿５に累計エネルギー量１０ｗｈを設定する。【０１０９】
一方、ナビゲーション装置３００は、ノードＮ３＿２のように一のノードに複数のリンクＬ３＿２＿１，Ｌ３＿２＿２が接続する場合には、車両の現在地点５００から一のノードＮ３＿２までの複数の経路における累計エネルギー量のうち、最小の累計エネルギー量１０ｗｈを当該一のノードＮ３＿２に設定する。【０１１０】
具体的には、ナビゲーション装置３００は、リンクＬ３＿２＿１における推定エネルギー消費量４ｗｈをノード２＿１に設定した累計エネルギー量７ｗｈに累計し（＝累計エネルギー量１１ｗｈ）、リンクＬ３＿２＿２における推定エネルギー消費量２ｗｈをノード２＿２に設定した累計エネルギー量８ｗｈに累計する（＝累計エネルギー量１０ｗｈ）。そして、ナビゲーション装置３００は、車両の現在地点５００からリンクＬ３＿２＿１までの経路の累計エネルギー量１１ｗｈと、車両の現在地点５００からリンクＬ３＿２＿２までの経路の累計エネルギー量１０ｗｈとを比較し、最小の累計エネルギー量となるリンクＬ３＿２＿２側の経路の累計エネルギー量１０ｗｈをノードＮ３＿２に設定する。【０１１１】
ナビゲーション装置３００は、上述したノードＮ２＿１〜Ｎ２＿３のように車両の現在地点５００から同一階層のノードが複数存在する場合、たとえば、同一レベルのノードのうち、累計エネルギー量が少ないノードに接続するリンクから順に推定エネルギー消費量および累計エネルギー量を算出する。具体的には、ナビゲーション装置３００は、ノードＮ２＿３、ノードＮ２＿１、ノードＮ２＿２の順に、各ノードに接続するリンクにおける推定エネルギー消費量をそれぞれ算出し、各ノードにおける累計エネルギー量に累計する。このように、推定エネルギー消費量および累計エネルギー量を算出するノードの順番を特定することにより、残存エネルギー量で到達可能な範囲を効率的に算出することができる。【０１１２】
その後、ナビゲーション装置３００は、ノードＮ３＿１〜Ｎ３＿５からさらに深い階層のノードへと、上述したような累計エネルギー量の累計を続けていく。そして、ナビゲーション装置３００は、あらかじめ設定された指定エネルギー量以下の累計エネルギー量が設定されたすべてのノードを車両の到達可能地点とする。【０１１３】
具体的には、たとえば指定エネルギー量を１０ｗｈとした場合、図５−４に斜線で塗りつぶされた丸印で示すように、ナビゲーション装置３００は、１０ｗｈ以下の累計エネルギー量が設定されたノードＮ１＿１，Ｎ２＿１，Ｎ２＿２，Ｎ２＿３，Ｎ３＿２，Ｎ３＿５を車両の到達可能地点とする。あらかじめ設定された指定エネルギー量とは、たとえば、車両の現在地点５００での残存エネルギー量（初期保有エネルギー量）である。【０１１４】
図５−４に示す車両の現在地点５００と複数のノードおよびリンクとで構成された地図データ５４０は到達可能地点探索を説明するための一例であり、ナビゲーション装置３００は、実際には図６に示すように図５−４に示す地図データ５４０よりも広い範囲でさらに多くのノードおよびリンクを探索する。【０１１５】
図６は、ナビゲーション装置３００による到達可能地点探索の一例について示す説明図である。上述したように異なるメッシュの領域ごとに、含まれる道路（細街路を除く）について累計エネルギー量を算出し続けていく場合、図６に示すように、該当するノードにおける累計エネルギー量を詳細に探索することができる。この際、ナビゲーション装置３００は、たとえばリンクの重要度などに基づいて、移動体の到達可能地点を探索する道路を絞り込むこととしてもよい。【０１１６】
（ナビゲーション装置３００における地図データ分割の概要）
本実施例のナビゲーション装置３００は、分割数決定部１０３ａにより記憶装置に記憶された地図データを分割する。具体的には、ナビゲーション装置３００は、ベクタデータで構成される地図データを、たとえば６４×６４画素のメッシュデータ（Ｘ，Ｙ）に変換し、地図データをラスタデータ（画像データ）にする。【０１１７】
図７は、ナビゲーション装置３００による到達可能地点をメッシュデータで示す一例の説明図である。図７には、到達可能地点に基づいて識別情報が付与された６４×６４画素のメッシュデータ（Ｘ，Ｙ）をスクリーン座標で図示している。【０１１８】
つぎに、ナビゲーション装置３００の付与部１０４ａは、メッシュデータ（Ｘ，Ｙ）の一の領域に車両の到達可能地点が含まれる場合、当該一の領域に車両が到達可能であることを識別する到達可能の識別情報として、たとえば「１」を付与する（図７では１画素をたとえば黒色で描画）。一方、ナビゲーション装置３００は、メッシュデータ（Ｘ，Ｙ）の一の領域に車両の到達可能地点が含まれない場合、当該の一の領域に車両が到達不可能であることを識別する到達不可能の識別情報として、たとえば「０」を付与する（図７では１画素をたとえば白色で描画）。【０１１９】
このように、ナビゲーション装置３００は、地図データを分割した各領域にそれぞれ識別情報を付与したｍ行ｍ列の２次元行列データ（Ｙ，Ｘ）のメッシュデータに変換し、地図データを２値化されたラスタデータとして扱う。メッシュデータの各領域は、それぞれ一定範囲の矩形状の領域で表される。具体的には、図７に示すように、たとえば、複数の到達可能地点の点群が黒色で描画されたｍ×ｍ画素のメッシュデータ（Ｘ，Ｙ）が生成される。メッシュデータ（Ｘ，Ｙ）の原点（０，０）は左上である。【０１２０】
（ナビゲーション装置３００における識別情報付与の概要・その１）
つぎに、ナビゲーション装置３００の変更部１０５は、ｍ行ｍ列の２次元行列データ（Ｙ，Ｘ）のメッシュデータに対してクローニング処理（膨張処理後に縮小処理をおこなう処理）をおこなう。【０１２１】
図８は、ナビゲーション装置によるクローニング処理の一例を示す説明図である。（Ａ）〜（Ｃ）は、各領域にそれぞれ識別情報が付与されたｍ行ｍ列の２次元行列データ（Ｙ，Ｘ）のメッシュデータである。（Ａ）には、地図データの分割処理後、はじめて識別情報が付与されたメッシュデータ９００を示す。すなわち、（Ａ）に示すメッシュデータ９００は、図８に示すメッシュデータと同一である。【０１２２】
また、（Ｂ）には、（Ａ）に示すメッシュデータ９００に対してクローニング処理（膨張）をおこなった後のメッシュデータ９１０を示す。（Ｃ）には、（Ｂ）に示すメッシュデータ９１０に対してクローニング処理（縮小）をおこなった後のメッシュデータ９２０を示す。（Ａ）〜（Ｃ）に示すメッシュデータ９００，９１０，９２０において、到達可能の識別情報が付与された複数の領域によって生成される車両の到達可能範囲９０１，９１１，９２１を黒く塗りつぶした状態で示す。【０１２３】
（Ａ）に示すように、識別情報付与後のメッシュデータ９００には、車両の到達可能範囲９０１内に含まれる到達不可能な領域からなる欠損点９０２（ハッチングされた到達可能範囲９０１内の白地部分）が生じている。欠損点９０２は、たとえば、ナビゲーション装置３００による到達可能地点探索処理の負荷を低減させるためにノードおよびリンクを探索する道路を絞り込んだ場合に、到達可能地点となるノード数が少なくなることにより生じる。【０１２４】
つぎに、（Ｂ）に示すように、ナビゲーション装置３００は、識別情報付与後のメッシュデータ９００に対してクローニングの膨張処理をおこなう。クローニングの膨張処理では、識別情報付与後のメッシュデータ９００の、到達可能の識別情報が付与されている領域に隣り合う一の領域の識別情報が、到達可能の識別情報に変更される。これにより、膨張処理前（識別情報付与後）の車両の到達可能範囲９０１内に生じていた欠損部９０２が消滅する。【０１２５】
また、膨張処理前の車両の到達可能範囲９０１の最外周の領域に隣り合うすべての領域の識別情報が、到達可能な識別情報に変更される。このため、膨張処理後の車両の到達可能範囲９１１の外周は、膨張処理をおこなうごとに、膨張処理前の車両の到達可能範囲９０１の最外周の各領域の外周を囲むように１画素分ずつ広がる。【０１２６】
その後、（Ｃ）に示すように、ナビゲーション装置３００は、メッシュデータ９１０に対してクローニングの縮小処理をおこなう。クローニングの縮小処理では、膨張処理後のメッシュデータ９１０の、到達不可能の識別情報が付与されている領域に隣り合う一の領域の識別情報が、到達不可能の識別情報に変更される。【０１２７】
このため、膨張処理後の車両の到達可能範囲９１１の最外周の各領域が、縮小処理がおこなわれるごとに１画素分ずつ到達不可能な領域となり、膨張処理後の車両の到達可能範囲９１１の外周が縮まる。これにより、縮小処理後の車両の到達可能範囲９２１の外周は、膨張処理前の車両の到達可能範囲９０１の外周とほぼ同様となる。【０１２８】
ナビゲーション装置３００は、上述した膨張処理および縮小処理は同じ回数ずつおこなう。具体的には、膨張処理が２回おこなわれた場合、その後の縮小処理も２回おこなわれる。膨張処理と縮小処理との処理回数を等しくすることで、膨張処理によって到達可能の識別情報に変更された車両の到達可能範囲の外周部分のほぼすべての領域の識別情報を、縮小処理によって元の到達不可能の識別情報に変更することができる。このようにして、ナビゲーション装置３００は、車両の到達可能範囲内の欠損点９０２を除去し、かつ外周を明瞭に表示可能な車両の到達可能範囲９２１を生成することができる。【０１２９】
（ナビゲーション装置３００における識別情報付与の概要・その２）
ナビゲーション装置３００は、２次元行列データ（Ｙ，Ｘ）のメッシュデータに対してオープニング処理（縮小処理後に膨張処理をおこなう処理）をおこない、外周を明瞭に表示可能な車両の到達可能範囲を生成してもよい。具体的には、ナビゲーション装置３００は、次のようにオープニング処理をおこなう。【０１３０】
図９は、ナビゲーション装置によるオープニング処理の一例を示す説明図である。（Ａ）〜（Ｃ）は、各領域にそれぞれ識別情報が付与されたｍ行ｍ列の２次元行列データ（Ｙ，Ｘ）のメッシュデータである。（Ａ）には、識別情報付与後のメッシュデータ１０００を示す。（Ｂ）には、（Ａ）に対するオープニング処理（縮小）後のメッシュデータ１０１０を示す。また、（Ｃ）には、（Ｂ）に対するオープニング処理（膨張）後のメッシュデータ１０２０を示す。（Ａ）〜（Ｃ）に示すメッシュデータ１０００，１０１０，１０２０において、到達可能の識別情報が付与された複数の領域によって生成される車両の到達可能範囲１００１，１０１１，１０２１を黒く塗りつぶした状態で示す。【０１３１】
（Ａ）に示すように、識別情報付与後のメッシュデータ１０００における車両の到達可能範囲１００１の外周に孤立点１００２が多く生じている場合、識別情報付与後のメッシュデータ１０００に対してオープニング処理をおこなうことで、孤立点１００２を除去することができる。具体的には、（Ｂ）に示すように、ナビゲーション装置３００は、識別情報付与後のメッシュデータ１０００に対してオープニングの縮小処理をおこなう。【０１３２】
オープニングの縮小処理では、識別情報付与後のメッシュデータ１０００の、到達不可能の識別情報が付与されている領域に隣り合う一の領域の識別情報が、到達不可能の識別情報に変更される。これにより、縮小処理前（識別情報付与後）の車両の到達可能範囲１００１内に生じていた孤立点１００２が除去される。【０１３３】
このため、識別情報付与後の車両の到達可能範囲１００１の最外周の各領域が、縮小処理がおこなわれるごとに１画素分ずつ到達不可能な領域となり、識別情報付与後の車両の到達可能範囲１００１の外周が縮まる。また、識別情報付与後の車両の到達可能範囲１００１に生じていた孤立点１００２が除去される。【０１３４】
その後、（Ｃ）に示すように、ナビゲーション装置３００は、メッシュデータ１０１０に対してオープニングの膨張処理をおこなう。オープニングの膨張処理では、縮小処理後のメッシュデータ１０１０の、到達不可能の識別情報が付与されている領域に隣り合う一の領域の識別情報が、到達可能の識別情報に変更される。このため、膨張処理後の車両の到達可能範囲１０２１の外周は、膨張処理をおこなうごとに、縮小処理後の車両の到達可能範囲１０１１の最外周の各領域の外周を囲むように１画素分ずつ広がる。【０１３５】
ナビゲーション装置３００は、オープニング処理においても、クローニング処理と同様に膨張処理および縮小処理は同じ回数ずつおこなう。このように膨張処理と縮小処理との処理回数を等しくすることで、縮小処理によって縮まった車両の到達可能範囲１０１１の外周を広げ、縮小処理後の車両の到達可能範囲１０２１の外周を縮小処理前の車両の到達可能範囲１００１の外周に戻すことができる。このようにして、ナビゲーション装置３００は、孤立点１００２が生じず、かつ外周を明瞭に表示可能な車両の到達可能範囲１０２１を生成することができる。【０１３６】
（ナビゲーション装置３００における到達可能範囲の輪郭抽出の概要・その１）
本実施例のナビゲーション装置３００は、ｍ行ｍ列の２次元行列データ（Ｙ，Ｘ）のメッシュデータに付与された識別情報に基づいて、車両の到達可能範囲の輪郭を抽出する。具体的には、ナビゲーション装置３００は、たとえば、フリーマンのチェインコードを用いて車両の到達可能範囲の輪郭を抽出する。より具体的には、ナビゲーション装置３００は、次のように車両の到達可能範囲の輪郭を抽出する。【０１３７】
図１０は、ナビゲーション装置による車両の到達可能範囲抽出の一例を模式的に示す説明図である。また、図１１は、ナビゲーション装置による車両の到達可能範囲抽出後のメッシュデータの一例を模式的に示す説明図である。図１０（Ａ）には、領域１１００に隣り合う領域１１１０〜１１１７の隣接方向を示す数字（以下、「方向指数（チェインコード）」という）と、方向指数に対応する８方向の矢印とを示す。図１０（Ｂ）には、ｈ行ｈ列の２次元行列データ（Ｙ，Ｘ）のメッシュデータ１１２０を一例として示す。また、図１０（Ｂ）には、到達可能の識別情報が付与された領域１１２１〜１１３４および当該領域１１２１〜１１３４に囲まれた到達可能の識別情報が付与された領域をハッチングで図示する。【０１３８】
方向指数は、単位長さの線分の向いている方向を示す。メッシュデータ（Ｘ，Ｙ）において、方向指数に対応する座標は、（Ｘ＋ｄｘ，Ｙ＋ｄｙ）となる。具体的には、図１０（Ａ）に示すように、領域１１００から左下に隣り合う領域１１１０へ向かう方向の方向指数は「０」である。領域１１００から下に隣り合う領域１１１１へ向かう方向の方向指数は「１」である。領域１１００から右下に隣り合う領域１１１２へ向かう方向の方向指数は「２」である。【０１３９】
また、領域１１００から右に隣り合う領域１１１３へ向かう方向の方向指数は「３」である。領域１１００から右上に隣り合う領域１１１４へ向かう方向の方向指数は「４」である。領域１１００から上に隣り合う領域１１１５へ向かう方向の方向指数は「５」である。領域１１００から左上に隣り合う領域１１１６へ向かう方向の方向指数は「６」である。領域１１００から左に隣り合う領域１１１７へ向かう方向の方向指数は「７」である。【０１４０】
ナビゲーション装置３００は、領域１１００に隣り合う到達可能の識別情報「１」が付与された領域を左回りに検索する。また、ナビゲーション装置３００は、領域１１００に隣り合う到達可能の識別情報が付与された領域の検索開始点を、前回の方向指数に基づいて決定する。具体的には、ナビゲーション装置３００は、他の領域から領域１１００へ向かう方向指数が「０」であった場合、領域１１００の左に隣り合う領域、すなわち方向指数「７」の方向に隣り合う領域１１１７から検索を開始する。【０１４１】
同様に、ナビゲーション装置３００は、他の領域から領域１１００へ向かう方向指数が「１」〜「７」であった場合、領域１１００の左下、下、右下、右、右上、上、左上に隣り合う領域、すなわちそれぞれ方向指数「０」、「１」、「２」、「３」、「４」、「５」、「６」の方向に隣り合う領域１１１０〜１１１６から検索を開始する。そして、ナビゲーション装置３００は、領域１１００から各領域１１１０〜１１１７のいずれか一の領域から到達可能の識別情報「１」を検出した場合、到達可能の識別情報「１」を検出した領域１１１０〜１１１７に対応する方向指数「０」〜「７」を、領域１１００に関連付けて記憶装置に書き込む。【０１４２】
具体的には、ナビゲーション装置３００は、次のように車両の到達可能範囲の輪郭を抽出する。図１０（Ｂ）に示すように、ナビゲーション装置３００は、まず、ｈ行ｈ列の２次元行列データ（Ｙ，Ｘ）のメッシュデータ１１２０のａ行ａ列の領域から行単位で到達可能の識別情報が付与された領域を検索する。【０１４３】
メッシュデータ１１２０のａ行目のすべての領域には到達不可能の識別情報が付与されているので、つぎに、ナビゲーション装置３００は、メッシュデータ１１２０のｂ行ａ列の領域からｂ行ｈ列の領域に向かって到達可能の識別情報を検索する。そして、ナビゲーション装置３００は、メッシュデータ１１２０のｂ行ｅ列の領域１１２１において到達可能の識別情報を検出した後、メッシュデータ１１２０のｂ行ｅ列の領域１１２１から左回りに、車両の到達可能範囲の輪郭となる到達可能の識別情報を有する領域を検索する。【０１４４】
具体的には、ナビゲーション装置３００は、領域１１２１の左に隣り合うｂ行ｄ列の領域は既に検索済みのため、まず、領域１１２１の左下に隣り合う領域１１２２から左回りに、到達可能の識別情報を有する領域があるか否かを検索する。そして、ナビゲーション装置３００は、領域１１２２の到達可能の識別情報を検出し、領域１１２１から領域１１２２へ向かう方向の方向指数「０」を、領域１１２１に関連付けて記憶装置に記憶する。【０１４５】
つぎに、ナビゲーション装置３００は、前回の方向指数「０」であるため、領域１１２２の左に隣り合うｃ行ｃ列の領域から左回りに、到達可能の識別情報を有する領域があるか否かを検索する。そして、ナビゲーション装置３００は、領域１１２２の左下に隣り合う領域１１２３の到達可能の識別情報を検出し、領域１１２２から領域１１２３へ向かう方向の方向指数「０」を、前回の方向指数に関連付けて記憶装置に記憶する。【０１４６】
以降、ナビゲーション装置３００は、前回の方向指数に基づいて検索開始点を決定し、検索開始点から左回りに到達可能の識別情報を有する領域があるか否かを検索する処理を、方向指数に対応する矢印が領域１１２１に戻ってくるまで繰り返しおこなう。具体的には、ナビゲーション装置３００は、領域１１２２の左に隣り合う領域から左回りに、到達可能の識別情報を有する領域があるか否かを検索し、領域１１２３の下に隣り合う領域１１２４の到達可能の識別情報を検出して、方向指数「１」を前回の方向指数に関連付けて記憶装置に記憶する。【０１４７】
同様に、ナビゲーション装置３００は、前回の方向指数に基づいて検索開始点を決定した後、検索開始点から左回りに到達可能の識別情報を有する領域を検索し、到達可能の識別情報を有する領域１１２４〜１１３４を順次検出する。そして、ナビゲーション装置３００は、方向指数を取得するごとに前回の方向指数に関連付けて記憶装置に記憶する。【０１４８】
その後、ナビゲーション装置３００は、領域１１３４の右上に隣り合うｂ行ｆ列の領域から左回りに、到達可能の識別情報を有する領域があるか否かを検索し、領域１１３４の上に隣り合う領域１１２１の到達可能の識別情報を検出して、方向指数「５」を前回の方向指数に関連付けて記憶装置に記憶する。これにより、記憶装置には、方向指数「０」→「０」→「１」→「０」→「２」→「３」→「４」→「３」→「２」→「５」→「５」→「６」→「６」→「５」がこの順で記憶される。【０１４９】
このようにナビゲーション装置３００は、最初に検出した領域１１２１から、当該領域１１２１に隣り合う到達可能の識別情報を有する領域１１２２〜１１３４を左回りに順次検索し方向指数を取得する。そして、ナビゲーション装置３００は、領域１１２１から方向指数に対応する方向の一の領域を塗りつぶすことで、図１１に示すように、車両の到達可能範囲の輪郭１２０１および当該輪郭１２０１に囲まれた部分１２０２からなる車両の到達可能範囲１２００を有するメッシュデータを生成する。【０１５０】
（ナビゲーション装置３００における到達可能範囲の輪郭抽出の概要・その２）
本実施例のナビゲーション装置３００による車両の到達可能範囲抽出の別の一例について説明する。ナビゲーション装置３００は、たとえば、到達可能の識別情報が付与された２次元行列データ（Ｙ，Ｘ）のメッシュデータの経度緯度情報に基づいて、車両の到達可能範囲の輪郭を抽出してもよい。具体的には、ナビゲーション装置３００は、次のように車両の到達可能範囲の輪郭を抽出する。【０１５１】
図１２は、ナビゲーション装置による車両の到達可能範囲抽出の別の一例について模式的に示す説明図である。図１２に示すようなｄ行ｈ列の２次元行列データ（Ｙ，Ｘ）のメッシュデータ１３００を例に説明する。ナビゲーション装置３００は、メッシュデータ１３００の、到達可能の識別情報「１」が付与された領域を検索する。具体的には、ナビゲーション装置３００は、まず、ａ行ａ列の領域からａ行ｈ列の領域に向かって到達可能の識別情報「１」を検索する。【０１５２】
メッシュデータ１３００のａ行目のすべての領域には到達不可能の識別情報「０」が付与されているので、つぎに、ナビゲーション装置３００は、ｂ行ａ列の領域からｂ行ｈ列の領域に向かって到達可能の識別情報「１」を有する領域を検索する。そして、ナビゲーション装置３００は、到達可能の識別情報「１」を有するｂ行ｃ列の領域１３０１の最小経度ｐｘ１、最小緯度ｐｙ１（領域１３０１の左上座標）を取得する。【０１５３】
つぎに、ナビゲーション装置３００は、ｂ行ｄ列の領域からｂ行ｈ列の領域に向かって到達可能の識別情報「１」を有する領域を検索する。そして、ナビゲーション装置３００は、到達可能の識別情報「１」を有する領域と、到達可能の識別情報「０」を有する領域との境界を検索し、到達可能の識別情報「１」を有するｂ行ｆ列の領域１３０２の最大経度ｐｘ２、最大緯度ｐｙ２（領域１３０２の右下座標）を取得する。【０１５４】
つぎに、ナビゲーション装置３００は、ｂ行ｃ列の領域１３０１の左上座標（ｐｘ１，ｐｙ１）と、ｂ行ｆ列の領域１３０２の右下座標（ｐｘ２，ｐｙ２）とを対向する頂点とする矩形領域を塗りつぶす。【０１５５】
つぎに、ナビゲーション装置３００は、メッシュデータ１３００のｂ行ｇ列からｂ行ｈ列の領域へ、さらにｃ行ａ列からｃ行ｈ列に向かって到達可能の識別情報「１」を検索する。そして、ナビゲーション装置３００は、到達可能の識別情報「１」を有するｃ行ｄ列の領域１３０３の最小経度ｐｘ３、最小緯度ｐｙ３（領域１３０３の左上座標）を取得する。【０１５６】
つぎに、ナビゲーション装置３００は、ｃ行ｅ列の領域からｃ行ｈ列の領域に向かって到達可能の識別情報「１」を有する領域を検索する。そして、ナビゲーション装置３００は、到達可能の識別情報「１」を有する領域と、到達可能の識別情報「０」を有する領域との境界を検索し、到達可能の識別情報「１」を有するｃ行ｆ列の領域１３０４の最大経度ｐｘ４、最大緯度ｐｙ４（領域１３０４の右下座標）を取得する。【０１５７】
つぎに、ナビゲーション装置３００は、ｃ行ｄ列の領域１３０３の左上座標（ｐｘ３，ｐｙ３）と、ｃ行ｆ列の領域１３０４の右下座標（ｐｘ４，ｐｙ４）とを対向する頂点とする矩形領域を塗りつぶす。【０１５８】
その後、ナビゲーション装置３００は、ｃ行ｇ列の領域からｃ行ｈ列の領域へ、さらにさらにｄ行ａ列からｄ行ｈ列に向かって到達可能の識別情報「１」を有する領域を検索する。ナビゲーション装置３００は、ｃ行ｇ列の領域からｄ行ｈ列までのすべての領域には到達不可能の識別情報「０」が付与されているので、処理を終了する。【０１５９】
このように、２次元行列データ（Ｙ，Ｘ）のメッシュデータ１３００の各行ごとに、到達可能の識別情報「１」を有する領域を塗りつぶすことにより、車両の到達可能範囲を取得することができる。【０１６０】
（ナビゲーション装置３００における画像処理）
上述のように、ナビゲーション装置３００は、車両の残存エネルギー量に基づいて探索された移動体の到達可能なノードに基づいて移動体の到達可能範囲を生成しディスプレイ３１３に表示させる。以下、たとえば、ナビゲーション装置３００がＥＶ車に搭載されている場合を例に説明する。【０１６１】
図１３は、ナビゲーション装置による画像処理の手順の一例を示すフローチャートである。図１３のフローチャートにおいて、ナビゲーション装置３００は、まず、たとえば、通信Ｉ／Ｆ３１５を介して、自装置が搭載された車両の現在地点（ｏｆｘ，ｏｆｙ）を取得する（ステップＳ１３０１）。つぎに、ナビゲーション装置３００は、たとえば、通信Ｉ／Ｆ３１５を介して、車両の現在地点（ｏｆｘ，ｏｆｙ）における車両の初期保有エネルギー量を取得する（ステップＳ１３０２）。【０１６２】
つぎに、ナビゲーション装置３００は、メッシュデータ生成をおこなう。この際、メッシュデータの最大範囲と分割数を決定する（ステップＳ１３０３）。この後、ナビゲーション装置３００は、到達可能ノード探索処理をおこなう（ステップＳ１３０４）。つぎに、ナビゲーション装置３００は、到達可能ノードが含まれるメッシュの領域に識別情報付与処理をおこなう（ステップＳ１３０５）。つぎに、ナビゲーション装置３００は、車両の到達可能範囲の輪郭を抽出する（ステップＳ１３０６）。その後、ナビゲーション装置３００は、ディスプレイ３１３に車両の到達可能範囲を表示し（ステップＳ１３０７）、処理を終了する。【０１６３】
（ナビゲーション装置３００における推定消費電力量算出処理）
つぎに、ナビゲーション装置３００による推定消費電力量算出処理について説明する。図１４は、ナビゲーション装置による推定消費電力量算出処理の手順の一例を示すフローチャートである。図１４に示すフローチャートでは、上述したステップＳ１３０４でおこなう処理である。【０１６４】
図１４のフローチャートにおいて、ナビゲーション装置３００は、まず、通信Ｉ／Ｆ３１５を介して、プローブデータなどを加工した渋滞情報や渋滞予測データを取得する（ステップＳ１４０１）。つぎに、ナビゲーション装置３００は、リンクの長さや、リンクの道路種別を取得する（ステップＳ１４０２）。【０１６５】
つぎに、ナビゲーション装置３００は、ステップＳ１４０１，Ｓ１４０２で取得した情報に基づいて、リンクの旅行時間を算出する（ステップＳ１４０３）。リンクの旅行時間とは、車両がリンクを走行し終わるのに要する時間である。つぎに、ナビゲーション装置３００は、ステップＳ１４０１〜Ｓ１４０３で取得した情報に基づいて、リンクの平均速度を算出する（ステップＳ１４０４）。リンクの平均速度とは、車両がリンクを走行する際の平均速度時間である。【０１６６】
つぎに、ナビゲーション装置３００は、リンクの標高データを取得する（ステップＳ１４０５）。つぎに、ナビゲーション装置３００は、車両の設定情報を取得する（ステップＳ１４０６）。つぎに、ナビゲーション装置３００は、ステップＳ１４０１〜Ｓ１４０６で取得した情報に基づいて、上述した（１）式〜（６）式のいずれか一つ以上の消費エネルギー推定式を用いて、リンクにおける推定消費電力量を算出し（ステップＳ１４０７）、本フローチャートによる処理を終了する。【０１６７】
（ナビゲーション装置３００におけるメッシュ作成処理）
つぎに、ナビゲーション装置３００におけるメッシュ作成処理について説明する。図１５−１は、ナビゲーション装置によるメッシュ作成処理の手順の一例を示すフローチャートであり、図１３のステップＳ１３０３の処理に相当する。また、図１５−２は、ナビゲーション装置によるメッシュ作成処理を説明する図である。【０１６８】
はじめに、ナビゲーション装置３００は、上述したエネルギー推定式を用いて、最も良いエネルギー消費率（最大エネルギー消費率）を求める（ステップＳ１５０１）。たとえば、このナビゲーション装置３００が搭載された車両を平均速度１ｋｍ／ｈ〜１５０ｋｍ／ｈで可変し走行したときの最もよい速度におけるエネルギー消費率［ｋｍ／ｋＷｈ］を求める。このエネルギー消費率はあらかじめ測定された値を用いてもよい。【０１６９】
つぎに、車両のバッテリー等に蓄積しているエネルギー量により、最高エネルギー消費率での移動距離を計算する（ステップＳ１５０２）。図１５−２（ａ）に示すように、車両の現在地点５００を中心として最高エネルギー消費率での移動距離による最大到達範囲５００ａは円形となる。つぎに、図１５−２（ｂ）に示すように、最大到達範囲５００ａの上端、下端、右端、左端を結んだ正方形をメッシュデータの有効範囲（上記最大範囲）４００とする（ステップＳ１５０３）。そして、図１５−２（ｃ）に示すように、メッシュデータの有効範囲を、縦横のメッシュ数で等分し、複数のメッシュの領域４０１を作成し（ステップＳ１５０４）、以上の処理を終了する。【０１７０】
（ナビゲーション装置３００における到達可能地点探索処理）
つぎに、ナビゲーション装置３００による到達可能地点探索処理について説明する。図１６−１，図１６−２は、ナビゲーション装置による到達可能地点探索処理の手順の一例を示すフローチャートである。はじめに、上記作成したすべてのメッシュの領域４０１（図１５−２参照）に対して「未到達」状態にする（ステップＳ１６０１）。たとえば未到達の識別情報「０」を付与する。【０１７１】
つぎに、探索始点と一番近いリンクに接続するノードを候補に加える（ステップＳ１６０２）。つぎに、ノード候補が一つでもあれば（ステップＳ１６０３：Ｙｅｓ）、ステップＳ１６０４に移行するが、ノード候補が一つもなければ（ステップＳ１６０３：Ｎｏ）、処理を終了する。このノード候補とは未計算ノードで、つぎに計算対象になる候補である。【０１７２】
ステップＳ１６０４では、現在の候補の中で一番積算消費エネルギーの小さいノードＮを選ぶ（ステップＳ１６０４）。そして、このノードＮが指定エネルギー量より大きい場合には（ステップＳ１６０５：Ｙｅｓ）、ステップＳ１６０６に移行するが、このノードＮが指定エネルギー量より小さい場合には（ステップＳ１６０５：Ｎｏ）、処理を終了する。すなわち、エネルギー最小のノードが、指定エネルギー量より大きいということはこれ以上計算しても、全部到達できないノードであるため、処理を終了する。【０１７３】
ステップＳ１６０６では、ノードＮに接続するリンクの一つを注目し（ステップＳ１６０６）、この注目したリンクを候補に加えるか判断する（ステップＳ１６０７）。この処理の詳細は後述する。そして、ステップＳ１６０７の判断結果、候補に加えることになった場合には（ステップＳ１６０８：Ｙｅｓ）、ステップＳ１６０９に移行するが、候補に加えない場合には（ステップＳ１６０８：Ｎｏ）、ステップＳ１６２０に移行する。【０１７４】
ステップＳ１６０９では、注目したリンクの先にあるノードをノードＮ２とし、ノードＮ２がどのメッシュ４０１に該当するか計算する（ステップＳ１６０９）。つぎに、当該メッシュ４０１が「到達」状態であれば（ステップＳ１６１０：Ｙｅｓ）、該当メッシュ４０１に隣接するすべてのメッシュについて「到達」状態か調べ（ステップＳ１６１１）、ステップＳ１６１３に移行する。一方、到達状態でなければ（ステップＳ１６１０：Ｎｏ）、当該メッシュ４０１を「到達」状態にし（ステップＳ１６１２）、ステップＳ１６１６に移行する。【０１７５】
ステップＳ１６１３では、当該メッシュに隣接するすべてのメッシュが到達状態であれば（ステップＳ１６１３：Ｙｅｓ）、ステップＳ１６１４に移行し、当該メッシュに隣接するメッシュの一部が到達していなければ（ステップＳ１６１３：Ｎｏ）、ステップＳ１６１６に移行する。ステップＳ１６１４では、このリンクの属性が細街路であれば（ステップＳ１６１４：Ｙｅｓ）、ステップＳ１６２０に移行し、このリンクの属性が細街路でなければ（ステップＳ１６１４：Ｎｏ）、ステップＳ１６１５に移行する。ここで、まわりのメッシュがすべて到達状態なら、同じ道が遠くのメッシュまで続くのは国道や県道などの道路に限られるため、細街路などの格の低い道路を探索する必要はない。そのため細街路のリンクの探索を中止したり、大通りから細い道に入るのを抑制することで処理を高速化できるようになる。この格とは、道路の重要度のことであり、たとえば、高速道路・有料道路・国道・県道・主要地方道は格が高く、それ以外の道路は格が低いものとして定義しておく。【０１７６】
ステップＳ１６１５では、一つ前のリンクとこのリンクの属性を比較し、格の高い道路から格の低い道路に入るか判断する（ステップＳ１６１５）。比較の結果、格の高い道路から格の低い道路に入る場合には（ステップＳ１６１５：Ｙｅｓ）、ステップＳ１６２０に移行し、格の高い道路から格の低い道路に入るものでなければ（ステップＳ１６１５：Ｎｏ）、注目したリンクのエネルギー消費量を計算する（ステップＳ１６１６）。【０１７７】
つぎに、注目したリンクの先にあるノードＮ２までの積算エネルギー量を計算する（ステップＳ１６１７）。Ｎ２までの積算エネルギー量＝ノードＮまでの積算エネルギー量＋注目したリンクのエネルギー量である。そして、既にノードＮ２に到達したノードが無いまたは既にノードＮ２に到達した別の経路があるが今回の（ステップＳ１６１７で算出した）積算エネルギー量の方が小さい場合には（ステップＳ１６１８：Ｙｅｓ）、ステップＳ１６１９に移行し、ノードＮ２に到達したノードがあるまたは既にノードＮ２に到達した別の経路があるが今回の積算エネルギー量の方が大きい場合には（ステップＳ１６１８：Ｎｏ）、ステップＳ１６２０に移行する。【０１７８】
ステップＳ１６１９では、ノードＮ２に求めた積算エネルギー量を設定し、ノードＮ２が候補ではない場合、ノードＮ２を候補に加える（ステップＳ１６１９）。そして、ステップＳ１６２０では、他にリンクＬに接続するリンクがあれば（ステップＳ１６２０：Ｙｅｓ）、ステップＳ１６０６に戻り、他にリンクＬに接続するリンクがなければ（ステップＳ１６２０：Ｎｏ）、ノードＮを候補から外し（ステップＳ１６２１）、ステップＳ１６０３に戻る。これは、ノードＮについて計算を終えたため候補から外すことになる。この候補は未計算ノードであり、次に計算対象になる候補を指す。【０１７９】
図１６−３は、注目したリンクを候補に加えるか判断処理する手順の一例を示すフローチャートである。以下の処理は、ステップＳ１６０７の処理の詳細例である。図示のように、注目したリンクが通行禁止の道路であるとき（ステップＳ１６２２：Ｙｅｓ）、一方通行の逆走にあたるとき（ステップＳ１６２３：Ｙｅｓ）、時間規制や季節規制にあたるときには（ステップＳ１６２４：Ｙｅｓ）、いずれも注目したリンクを候補に加えず（ステップＳ１６２５）、処理を終了する。一方、注目したリンクが通行禁止の道路でなく（ステップＳ１６２２：Ｎｏ）、一方通行の逆走でなく（ステップＳ１６２３：Ｎｏ）、さらに、時間規制や季節規制に該当しないときには（ステップＳ１６２４：Ｎｏ）、注目したリンクを候補に加え（ステップＳ１６２６）、処理を終了する。【０１８０】
（ナビゲーション装置３００における到達可能範囲輪郭抽出処理）
つぎに、ナビゲーション装置３００による識別情報付与処理について説明する。図１７−１，１７−２は、ナビゲーション装置による到達可能範囲輪郭抽出処理の手順の一例を示すフローチャートである。図１７−１，１７−２のフローチャートは、上述したステップＳ１３０６でおこなう処理の一例であり、上述したナビゲーション装置３００における到達可能範囲の輪郭抽出の概要・その２に示す到達可能範囲輪郭抽出処理である。【０１８１】
図１７−１，１７−２のフローチャートにおいて、ナビゲーション装置３００は、まず、ｍｙ行ｍｘ列の２次元行列データのメッシュデータを取得する（ステップＳ１９０１）。つぎに、ナビゲーション装置３００は、ステップＳ１９０１で取得したメッシュデータの各領域の経度緯度情報を取得する（ステップＳ１９０２）。【０１８２】
つぎに、ナビゲーション装置３００は、メッシュデータのｉ行ｊ列の領域の識別情報を検索するために、変数ｉを初期化し、変数ｉに１を加算する（ステップＳ１９０３，Ｓ１９０４）。つぎに、ナビゲーション装置３００は、変数ｉがｍｙ行を超えているか否かを判断する（ステップＳ１９０５）。【０１８３】
変数ｉがｍｙ行を超えていない場合（ステップＳ１９０５：Ｎｏ）、ナビゲーション装置３００は、変数ｊを初期化し、変数ｊに１を加算する（ステップＳ１９０６，Ｓ１９０７）。つぎに、ナビゲーション装置３００は、変数ｊがｍｘ列を超えているか否かを判断する（ステップＳ１９０８）。【０１８４】
変数ｊがｍｘ列を超えていない場合（ステップＳ１９０８：Ｎｏ）、ナビゲーション装置３００は、メッシュデータのｉ行ｊ列の領域の識別情報が「１」であるか否かを判断する（ステップＳ１９０９）。ｉ行ｊ列の領域の識別情報が「１」である場合（ステップＳ１９０９：Ｙｅｓ）、ナビゲーション装置３００は、メッシュデータのｉ行ｊ列の領域の左上座標（ｐｘ１，ｐｙ１）を取得する（ステップＳ１９１０）。ｉ行ｊ列の領域の左上座標（ｐｘ１，ｐｙ１）とは、ｉ行ｊ列の領域の最小経度ｐｘ１、最小緯度ｐｙ１である。ｉ行ｊ列の領域の識別情報が「１」でない場合（ステップＳ１９０９：Ｎｏ）、ステップＳ１９０７に戻る。【０１８５】
つぎに、ナビゲーション装置３００は、変数ｊがｍｘ列を超えていないか否かを判断する（ステップＳ１９１１）。変数ｊがｍｘ列を超えている場合（ステップＳ１９１１：Ｎｏ）、ナビゲーション装置３００は、メッシュデータのｉ行ｊ列の領域の右下座標（ｐｘ２，ｐｙ２）を取得する（ステップＳ１９１２）。ｉ行ｊ列の領域の右下座標（ｐｘ２，ｐｙ２）とは、ｉ行ｊ列の領域の最大経度ｐｘ２、最大緯度ｐｙ２である。【０１８６】
つぎに、ナビゲーション装置３００は、ステップＳ１９１０において取得した左上座標（ｐｘ１，ｐｙ１）と、ステップＳ１９１２において取得した右下座標（ｐｘ２，ｐｙ２）とを地図データに設定する（ステップＳ１９１６）。そして、ナビゲーション装置３００は、左上座標（ｐｘ１，ｐｙ１）と、右下座標（ｐｘ２，ｐｙ２）とを対向する頂点とする矩形領域を塗りつぶし（ステップＳ１９１７）、ステップＳ１９０４に戻り、以降の処理を繰り返しおこなう。【０１８７】
一方、変数ｊがｍｘ列を超えていない場合（ステップＳ１９１１：Ｙｅｓ）、ナビゲーション装置３００は、変数ｊに１を加算し（ステップＳ１９１３）、メッシュデータのｉ行ｊ列の領域の識別情報が「１」であるか否かを判断する（ステップＳ１９１４）。ｉ行ｊ列の領域の識別情報が「１」でない場合（ステップＳ１９１４：Ｎｏ）、ナビゲーション装置３００は、メッシュデータのｉ行ｊ−１列の領域の右下座標（ｐｘ２，ｐｙ２）を取得し（ステップＳ１９１５）、ステップＳ１９１６以降の処理をおこなう。【０１８８】
また、ｉ行ｊ列の領域の識別情報が「１」である場合（ステップＳ１９１４：Ｙｅｓ）、ステップＳ１９１１に戻り、以降の処理を繰り返しおこなう。そして、変数ｉがｍｙ行を超えている場合（ステップＳ１９０５：Ｙｅｓ）、ナビゲーション装置３００は、本フローチャートによる処理を終了する。変数ｊがｍｘ列を超えている場合（ステップＳ１９０８：Ｙｅｓ）、ステップＳ１９０４に戻り、以降の処理を繰り返しおこなう。【０１８９】
（道路勾配について）
つぎに、上記（１）式〜（６）式の右辺に変数として用いられる道路勾配θについて説明する。図１８は、勾配がある道路を走行する車両にかかる加速度の一例を模式的に示した説明図である。図１８に示すように、道路勾配がθの坂道を走行する車両には、車両の走行に伴う加速度Ａ（＝ｄｘ／ｄｔ）と、重力加速度ｇの進行方向成分Ｂ（＝ｇ・ｓｉｎθ）がかかる。たとえば、上記（１）式を例に説明すると、上記（１）式の右辺第２項は、この車両の走行に伴う加速度Ａと、重力加速度ｇの進行方向成分Ｂの合成加速度Ｃを示している。また、車両が走行する区間の距離Ｄとし、走行時間Ｔとし、走行速度Ｖとする。【０１９０】
道路勾配θを考慮せずに電力消費量の推定をおこなった場合、道路勾配θが小さい領域では推定消費電力量と実際の消費電力量との誤差が小さいが、道路勾配θが大きい領域では推定した推定消費電力量と実際の消費電力量との誤差が大きくなってしまう。このため、ナビゲーション装置３００では、道路勾配、すなわち第四情報を考慮して燃費の推定をおこなうことで推定精度が向上する。【０１９１】
車両が走行する道路の勾配は、たとえば、ナビゲーション装置３００に搭載された傾斜計を用いて知ることができる。また、ナビゲーション装置３００に傾斜計が搭載されていない場合は、たとえば、地図データに含まれる道路の勾配情報を用いることができる。【０１９２】
（走行抵抗について）
つぎに、車両に生じる走行抵抗について説明する。ナビゲーション装置３００は、たとえば、次の（１１）式により走行抵抗を算出する。一般的に、走行抵抗は、道路種別や、道路勾配、路面状況などにより、加速時や走行時に移動体に生じる。【０１９３】
【数９】
2013125019.tif 000011
【０１９４】
（ナビゲーション装置によるクローニング処理後の表示例）
つぎに、ナビゲーション装置によるクローニング処理後の表示例について説明する。図１９は、ナビゲーション装置による到達可能地点探索処理後の表示例の一例について示す説明図である。図２０は、ナビゲーション装置による識別情報付与処理後の表示例の一例について示す説明図である。また、図２１は、ナビゲーション装置によるクローニング処理（膨張）後の表示例の一例について示す説明図である。図２２は、ナビゲーション装置によるクローニング処理（縮小）後の表示例の一例について示す説明図である。【０１９５】
図１９に示すように、たとえば、ディスプレイ３１３には、地図データとともに、ナビゲーション装置３００によって探索された複数の車両の到達可能地点が表示される。図１９に示すディスプレイ３１３の状態は、ナビゲーション装置３００によって到達可能地点探索処理がおこなわれたときの、ディスプレイに表示される情報の一例である。具体的には、図１３のステップＳ１３０４の処理がおこなわれた状態である。【０１９６】
つぎに、ナビゲーション装置３００によって地図データが複数の領域に分割され、到達可能地点に基づいて各領域に到達可能または到達不可能の識別情報が付与されることで、図２０に示すように、ディスプレイ３１３には、到達可能の識別情報に基づく車両の到達可能範囲２２００が表示される。この段階では、車両の到達可能範囲２２００内に、到達不可能な領域からなる欠損点が生じている。【０１９７】
つぎに、ナビゲーション装置３００によってクローニングの膨張処理がおこなわれることにより、図２１に示すように、欠損点の除去された車両の到達可能範囲２３００が生成される。その後、ナビゲーション装置３００によってクローニングの縮小処理がおこなわれることにより、図２２に示すように、車両の到達可能範囲２４００の外周は、クローニングがおこなわれる前の車両の到達可能範囲２２００の外周とほぼ同様の大きさとなる。【０１９８】
そして、ナビゲーション装置３００によって車両の到達可能範囲２４００の輪郭２４０１を抽出することで、車両の到達可能範囲２４００の輪郭をなめらかに表示することができる。また、クローニングによって欠損点を除去しているため、車両の到達可能範囲２４００は、２次元のなめらかな面２４０２で表示される。【０１９９】
以上説明したように、ナビゲーション装置３００によれば、地図情報を複数の領域に分割して各領域ごとに移動体が到達可能か否かを探索し、各領域にそれぞれ移動体が到達可能または到達不可能であることを識別する到達可能または到達不可能の識別情報を付与する。そして、ナビゲーション装置３００は、到達可能の識別情報が付与された領域に基づいて、移動体の到達可能範囲を生成する。このため、ナビゲーション装置３００は、海や湖、山脈など移動体の走行不可能な領域を除いた状態で移動体の到達可能範囲を生成することができる。したがって、画像処理装置１００は、移動体の到達可能範囲を正確に表示することができる。【０２００】
また、ナビゲーション装置３００は、地図情報を分割した複数の領域を画像データに変換し、当該複数の領域にそれぞれ到達可能または到達不可能の識別情報を付与した後、クローニングの膨張処理をおこなう。このため、ナビゲーション装置３００は、移動体の到達可能範囲内の欠損点を除去することができる。【０２０１】
また、ナビゲーション装置３００は、地図情報を分割した複数の領域を画像データに変換し、当該複数の領域にそれぞれ到達可能または到達不可能の識別情報を付与した後、オープニングの縮小処理をおこなう。このため、ナビゲーション装置３００は、移動体の到達可能範囲の孤立点を除去することができる。【０２０２】
このように、ナビゲーション装置３００は、移動体の到達可能範囲の欠損点や孤立点を除去することができるので、移動体の走行可能範囲を２次元のなめらかな面でかつ見やすく表示することができる。また、ナビゲーション装置３００は、地図情報を複数の領域に分割して生成したメッシュデータの輪郭を抽出する。このため、ナビゲーション装置３００は、移動体の到達可能範囲の輪郭をなめらかに表示することができる。【０２０３】
また、ナビゲーション装置３００は、移動体の到達可能地点を探索する道路を絞り込んで、移動体の到達可能地点を探索する。このため、ナビゲーション装置３００は、移動体の到達可能地点を探索する際の処理量を低減することができる。移動体の到達可能地点を探索する道路を絞り込むことで、探索可能な到達可能地点が少なくなったとしても、上述したようにクローニングの膨張処理がおこなわれることにより、移動体の到達可能範囲内に生じる欠損点を除去することができる。したがって、ナビゲーション装置３００は、移動体の到達可能範囲を検出するための処理量を低減することができる。また、ナビゲーション装置３００は、移動体の走行可能範囲を２次元のなめらかな面で見やすく表示することができる。【０２０４】
そして、ナビゲーション装置３００は、到達可能地点に基づいて表示するメッシュデータの最大範囲と分割数を決めた後に探索をおこなう。これにより、すべての到達可能地点の情報を記憶部に記憶することがないため、全体の処理量を削減でき、メモリ容量を削減することができる。【０２０５】
なお、本実施の形態で説明した画像処理方法は、あらかじめ用意されたプログラムをパーソナル・コンピュータやワークステーションなどのコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネットなどのネットワークを介して配布することが可能な伝送媒体であってもよい。
【符号の説明】
【０２０６】
１００  画像処理装置
１０１  取得部
１０３  領域特定部
１０３ａ  分割数決定部
１０４  探索部
１０４ａ  付与部
１０５  変更部
１０６  表示制御部
１１０  表示部
【図１】
2013125019.tif 000012
【図２】
2013125019.tif 000013
【図３】
2013125019.tif 000014
【図４】
2013125019.tif 000015
【図５−１】
2013125019.tif 000016
【図５−２】
2013125019.tif 000017
【図５−３】
2013125019.tif 000018
【図５−４】
2013125019.tif 000019
【図６】
2013125019.tif 000020
【図７】
2013125019.tif 000021
【図８】
2013125019.tif 000022
【図９】
2013125019.tif 000023
【図１０】
2013125019.tif 000024
【図１１】
2013125019.tif 000025
【図１２】
2013125019.tif 000026
【図１３】
2013125019.tif 000027
【図１４】
2013125019.tif 000028
【図１５−１】
2013125019.tif 000029
【図１５−２】
2013125019.tif 000030
【図１６−１】
2013125019.tif 000031
【図１６−２】
2013125019.tif 000032
【図１６−３】
2013125019.tif 000033
【図１７−１】
2013125019.tif 000034
【図１７−２】
2013125019.tif 000035
【図１８】
2013125019.tif 000036
【図１９】
2013125019.tif 000037
【図２０】
2013125019.tif 000038
【図２１】
2013125019.tif 000039
【図２２】
2013125019.tif 000040
【手続補正書】
【提出日】平成26年7月4日(2014.7.4)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
移動体の現在位置に関する情報、前記移動体が保有するエネルギー量に関する情報、および、前記移動体が所定区間を走行する際に消費するエネルギー量に関する情報を取得する取得手段と、
地図情報を複数の領域に分割する領域特定手段と、
前記取得手段により取得された情報に基づき、前記移動体が到達可能である到達可能地点を探索する探索手段と、
前記複数の領域のうち、前記到達可能地点を含む領域を表示手段に表示させる表示制御手段と、
を備えることを特徴とする画像処理装置。
【請求項２】
前記領域特定手段は、前記移動体のエネルギー消費率の最大値および前記移動体が保有するエネルギー量に基づき、前記複数の領域を特定することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記探索手段によって探索された到達可能地点の情報を保持する記憶部をさらに備え、
前記記憶部は、前記到達可能地点が、前記複数の領域の一つに複数存在する場合には、当該一つの領域に含まれる前記到達可能地点の情報の一部を保持しない、
ことを特徴とする請求項１または２に記載の画像処理装置。
【請求項４】
コンピュータが、
移動体の現在位置に関する情報、前記移動体が保有するエネルギー量に関する情報、および、前記移動体が所定区間を走行する際に消費するエネルギー量に関する情報を取得し、
取得された情報に基づき、前記移動体が到達可能である到達可能地点を探索し、
複数の領域に分割した地図情報の各領域のうち、前記到達可能地点を含む領域を表示手段に表示させることを特徴とする画像処理方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
上述した課題を解決し、目的を達成するため、請求項１の発明にかかる画像処理装置は、移動体の現在位置に関する情報、前記移動体が保有するエネルギー量に関する情報、および、前記移動体が所定区間を走行する際に消費するエネルギー量に関する情報を取得する取得手段と、地図情報を複数の領域に分割する領域特定手段と、前記取得手段により取得された情報に基づき、前記移動体が到達可能である到達可能地点を探索する探索手段と、前記複数の領域のうち、前記到達可能地点を含む領域を表示手段に表示させる表示制御手段と、を備えることを特徴とする。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
また、請求項４の発明にかかる画像処理方法は、コンピュータが、移動体の現在位置に関する情報、前記移動体が保有するエネルギー量に関する情報、および、前記移動体が所定区間を走行する際に消費するエネルギー量に関する情報を取得し、取得された情報に基づき、前記移動体が到達可能である到達可能地点を探索し、複数の領域に分割した地図情報の各領域のうち、前記到達可能地点を含む領域を表示手段に表示させることを特徴とする。
【国際調査報告】
2013125019.tif 000041
2013125019.tif 000042
2013125019.tif 000043
2013125019.tif 000044