道路領域決定可能プログラム及び道路領域決定方法
【課題】 地理画像から道路の異なる部分道路領域を簡単に検出可能にする。
【解決手段】地表を撮影して得られる地理画像内のエッジを検出し、地理画像を複数のメッシュに分割し、各メッシュについてそのメッシュを通過するいずれかの道路が存在する場合に、その道路のそのメッシュ内に位置する部分道路に関して、当該部分道路に平行で、かつ、そこからの距離が制限値以下である、複数の直線状のエッジ部分を、当該部分道路の境界直線に関する部分道路境界直線候補として、道路ベクトルデータに基づいて検出し、それらの候補から、その部分道路が当該メッシュ内で占有する領域に関する複数の部分道路領域候補を検出し、それらの部分道路領域候補を評価してその一つを当該メッシュ内の部分道路領域として決定し、異なるメッシュに対して決定された複数の部分道路領域を接続して上記道路ベクトルに対する道路存在領域を決定する。
【解決手段】地表を撮影して得られる地理画像内のエッジを検出し、地理画像を複数のメッシュに分割し、各メッシュについてそのメッシュを通過するいずれかの道路が存在する場合に、その道路のそのメッシュ内に位置する部分道路に関して、当該部分道路に平行で、かつ、そこからの距離が制限値以下である、複数の直線状のエッジ部分を、当該部分道路の境界直線に関する部分道路境界直線候補として、道路ベクトルデータに基づいて検出し、それらの候補から、その部分道路が当該メッシュ内で占有する領域に関する複数の部分道路領域候補を検出し、それらの部分道路領域候補を評価してその一つを当該メッシュ内の部分道路領域として決定し、異なるメッシュに対して決定された複数の部分道路領域を接続して上記道路ベクトルに対する道路存在領域を決定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、人工衛星あるいは航空機から地表を撮影して得られる地理画像を表す地理画像データから当該地表に含まれる複数の道路の存在領域を、上記地表に存在する道路に関する道路ベクトルデータを併用して検出する、道路領域決定可能プログラム及び道路領域決定方法に関する。
【背景技術】
【０００２】
地表上の道路を表す道路地図を、人工衛星あるいは航空機から地表を撮影して得られる画像から自動的に作成することができれば、当該地図を人力で作成する場合に比べて必要な労力が大幅に減り、更に、道路がその後変化した場合も、その変化を地図に迅速に反映することが可能になる。本明細書では、上記画像を地理画像と呼ぶ場合がある。このような利点を考慮して、上記地理画像から地表の地図を作成する研究が盛んに行われている。非特許文献１、２、３には、過去のいくつかの研究の概要が紹介されている。非特許文献３には、更に、ダイナミックプログラミングを用いて道路を表すエッジの追跡を行う独自の研究成果も紹介されている。
【０００３】
非特許文献１と２によれば、地理画像の解像度が低い（例えば、画素当たり２ｍ以上である）ときには、道路は一本の線として検出されるが、地理画像の解像度が高いときには、道路は平行な境界線を有する幅のある画像として検出される。したがって、両方の画像に対しては異なる技術が必要であることが記載されている。非特許文献１によれば、解像度が高い、住宅地の航空写真から直線部分を検出し、平行な線分をグループ化することにより、家や道路を抽出する研究もなされている。
【０００４】
非特許文献２によれば、衛星画像から道路を抽出するための処理は、大きくは、前処理、エッジ検出、道路追跡、グルーピングからなる。なお、高解像度の衛星画像を使用する場合には、前処理として上記エッジ検出を行う研究も紹介されている。高解像度の地理画像を使用する研究に関しては、道路追跡で平行なエッジの間の複数の直線を出発点として使用する研究として、非特許文献４から６を紹介している。
【０００５】
非特許文献１から３によれば、地理画像からの道路の検出をより正確にするために、いろいろな補助情報を利用する研究もなされている。補助情報としては、例えば地理的データベースを利用している例がある。非特許文献２は、そのような研究の例として非特許文献７を紹介している。
【０００６】
非特許文献２によれば、非特許文献４から６では、前処理として直線とエッジを検出した後、道路追跡段階では、平行なエッジの間の複数の直線を追跡の初期値として使用し、その後の道路追跡の実行は発見的手法により行っている。また、非特許文献２によれば、検出された道路要素をグルーピングする処理では、非特許文献４はリボン蛇(Ribbon Snakes)を使用し、非特許文献５と６では、コンテキストスケッチとして、道路と他の物体との関係を使用して道路要素として二つの平行な道路境界線を有する４辺形を決定し、決定されたそれらの４辺形を接続している。
【０００７】
非特許文献２によれば、非特許文献７では、エッジ検出には、シルクハット変換(top hat transformation)を用い、道路追跡の初期値の決定に地理的データベースを使用し、道路以外のものを表す直線と道路を表す直線とを区別している。その後、道路追跡処理では、パターンマッチングと、相関と領域それぞれの一様性を利用している。
【非特許文献１】高木幹雄、下田陽久監修、「画像解析ハンドブック」、財団法人東京大学出版会、１９９１年１月１７日、ｐ．１７３−１７８
【非特許文献２】Demin Xiong,"White papers: Automated Road Network Extraction from High Resolution Images," [on line]、２００２年１１月、National Consortium on Remote Sensing in Transportation, University of New Mexico, [平成１６年６月５日検索]、インターネット、＜ＵＲＬ：riker.unm.edu/DASH_new/pdf/White%20Papers/ Automated%20Road%20Network%20Extraction.pdf＞
【非特許文献３】MF Auclair Fortier, D. Ziou, C. Armenakis and S. Wang,"Survey of Work on Road Extraction in Aerial and Satellite Images," [on line], Technical Report N 247, Departement de mathematiques et informatique, Universite de Sherbrooke, Canada, [平成１６年６月５日検索]、インターネット、＜ＵＲＬ：http://www-l2ti.univ-paris13.fr/~auclair/ Publi/Auclair-TR247.pdf＞
【非特許文献４】H. Mayer, I. Laptev, A. Baumgartner, and C. Steger,"Automatic Road Extraction Based on Multi-Scale Modeling, Context, and Snakes," International Archives of Photogrammetry and Remote Sensing, volume XXXII, Part3-2W3, pages 106-113, 9-11 September 1997
【非特許文献５】A. Baumgartner, C. T. Steger, H. Mayer, and W. Eckstein," Semantic Objects and context for Finding Roads," Integrating photogrametric Techniques with Scene Analysis and Machine Vision III, Proc. SPIE 3072, pages 98-109, April 1997
【非特許文献６】A. Baumgartner, C. T. Steger, H. Mayer, and W. Eckstein,"Multi-Resolution, Semantic Objects and Context for Road Extraction," Semantic Modeling for the Acquition of Topographic Information from Images and Maps, pages 140-156, Basel Switzerland, 1997, Birkhauser Verlag
【非特許文献７】G. Bordes, G. Giraudon, and O. Jamet,"Road Modeling Based on a Cartogrphic Database for Aerial Image Interpretation," Semantic Modeling for the Acquition of Topographic Information from Images and Maps, pages 123-139, Basel Switzerland, 1997, Birkhauser Verlag
【発明の開示】
【発明が解決しようとする課題】
【０００８】
高解像度の地理画像から道路として幅のある領域（道路領域）を検出する研究は既になされている。非特許文献４から６では、道路の追跡処理には発見的方法が使用されている。非特許文献７では、道路の追跡処理にはパターンマッチングが主に使用されている。非特許文献７では、地理的データベースを使用しているが、道路探索の初期値の決定においてである。ここに列挙した非特許文献４から７では、道路を構成する複数の部分道路の検出のためのデータ処理量が多く、道路の検出に時間が掛かる。道路検出の高速化のためには、より簡単に部分道路を検出できることが望ましい。
【０００９】
したがって、本発明の目的は、地理画像から道路を構成する複数の部分道路の存在領域をより簡単に検出可能にする道路領域決定可能プログラム及び道路領域決定方法を提供することである。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、本発明は、地理画像から道路を構成する複数の部分道路の検出時に地理的データを使用する。地理的データとして、道路の中心線を近似的に直線で表す複数の道路ベクトルのそれぞれの始点と終点の位置情報を含む道路ベクトルデータという簡単な地理的なデータを使用する。より具体的には、請求項１に記載の本発明に係る道路領域決定可能プログラムは、エッジ検出手段と、領域分割手段と、部分道路境界直線候補検出手段と、部分道路領域候補検出手段と、部分道路領域決定手段と、道路領域決定手段、としてコンピュータを機能させるものである。
ここで、前記エッジ検出手段は、地表を上空から撮影して得られ、あらかじめ地理画像記憶手段に記憶された地理画像から複数のエッジを検出して当該複数のエッジを表すエッジ画像を生成する。前記領域分割手段は、前記地理画像の存在領域を複数のメッシュに分割するものである。
前記部分道路境界直線候補検出手段は、いずれかの道路が通過する複数のメッシュの各々に関して、当該道路の当該メッシュ内に位置する部分道路に対して所定の位置条件を満たす、当該メッシュ内に位置する複数の直線状のエッジ部分を、当該部分道路に対する複数の部分道路境界直線候補として、前記エッジ画像から、かつ、前記道路の中心線を近似的に直線で表す連結された複数の道路ベクトルを指定する、あらかじめ道路ベクトルデータ記憶手段に記憶された道路ベクトルデータに基づいて検出するものである。
前記部分道路領域候補検出手段は、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路境界直線候補検出手段により検出された前記複数の部分道路境界直線候補から選択された任意の二つからなる複数の組合わせにより定まる複数の領域を、当該道路の当該メッシュ内に位置する前記部分道路の存在領域に対する複数の部分道路領域候補として検出するものである。
前記部分道路領域決定手段は、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路境界直線候補検出手段により検出された前記複数の部分道路領域候補の各々について、当該部分道路領域候補が当該メッシュ内の前記部分道路の存在領域である妥当性を所定の評価基準に基づいて評価し、前記複数の部分道路領域候補に対する評価結果に基づいて前記複数の部分道路領域候補の一つを当該部分道路の当該メッシュ内の存在領域として決定するものである。
前記道路領域決定手段は、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路領域決定手段で決定された複数の部分道路領域を接続して当該道路の存在領域を決定するものである。
【００１１】
これにより、地理画像を分割して得られる複数のメッシュの各々毎に、そこを通過する道路がある場合に、その道路のうち当該メッシュ内に位置する部分道路の存在領域を、そのメッシュ内に位置する直線状エッジ部分から、上記道路ベクトルデータに基づいて決定することができ、道路の異なる部分道路の存在領域を比較的簡単に決定することができる。しかも、各メッシュを通過する道路部分に対する複数の部分道路領域候補を、他のメッシュ内の部分道路領域候補とは独立に決定するので、部分道路領域候補の決定処理が簡単に行える。更に、いずれかの道路が通過する複数のメッシュの各々毎に複数の部分道路領域候補を決定した後に、当該道路のうち当該複数のメッシュ内に位置する複数の道路部分に対する複数の部分道路領域を、それぞれのメッシュに対して検出された複数の部分道路領域候補から決定するので、複数の部分道路領域の決定が比較的容易になる。複数の部分道路領域を決定した後で、道路全体に対する道路領域をそれらの部分道路領域から決定するので、道路全体に対する道路領域の決定も比較的容易となる。
【００１２】
請求項２に記載の道路領域決定可能プログラムは、請求項１において、前記部分道路境界直線候補検出手段が前記いずれかの道路が通過する前記複数のメッシュの各々に対する前記複数の部分道路境界直線候補が満たすべき前記所定の位置条件は、部分道路境界直線候補は、当該部分道路の近傍にあり、かつ、当該部分道路に対してほぼ平行に位置することである。これにより、各メッシュを通過する道路のうち当該メッシュ内に位置する部分道路に対する部分道路境界直線候補を、直線状のエッジ部分を使用して決定することができ、メッシュ内に位置する部分道路に対する部分道路境界直線候補を非常に簡単に決定することができる。
【００１３】
請求項３に記載の道路領域決定可能プログラムは、請求項１又は２において、前期部分道路領域決定手段は、前記いずれかの道路が通過する前記複数のメッシュのそれぞれに対して検出された前記複数の部分道路領域候補の各々について、部分道路領域である妥当性を、それぞれの部分道路領域候補ごとに個別に所定の第１の評価基準に基づいて評価し、前記複数の部分道路領域候補に対する評価結果に基づいて、前記複数の部分道路領域候補の一つを、当該メッシュ内の当該道路の前記部分道路に対する暫定部分道路領域を決定する暫定部分道路領域決定手段と、前記いずれかの道路が通過する前記複数のメッシュの各々に対して決定された前記複数の暫定部分道路領域のそれぞれについて、前記複数の暫定部分道路領域の相互の位置関係に関係する第２の評価基準に基づいて、部分道路領域としての妥当性を評価し、前記複数の暫定部分道路領域に対する評価結果に基づいて、前記複数の暫定部分道路領域の各々について、当該暫定部分道路領域を当該暫定部分道路領域が属するメッシュに対して使用すべき部分道路領域として決定するか又は当該暫定部分道路領域の代わりに当該メッシュに対して使用すべき他の部分道路領域を決定する道路領域決定手段と、を備えるものである。
【００１４】
これにより、メッシュ毎にそのメッシュを通過する道路の当該メッシュ内部分に対する暫定部分道路領域を決定した後、複数のメッシュに対して決定された複数の暫定部分道路領域の位置関係に基づいて、各暫定部分道路領域を、そのまま当該暫定部分道路領域が属するメッシュに対して使用すべき部分道路領域として決定するか又は当該暫定部分道路領域の代わりに当該メッシュに対して使用すべき他の部分道路領域を決定するので、道路に対する道路領域の決定が、当該道路が通過する複数のメッシュの各々に対する複数の部分道路領域候補の検出、各メッシュに対する暫定部分道路領域の決定、複数のメッシュを通過する道路全体に対する道路領域の決定というように、段階的に進めることができるので、最終的な道路領域の決定が容易となる。
【００１５】
請求項４に記載の道路領域決定可能プログラムは、請求項３において、前記第１の評価基準は、各部分道路領域候補に属する、前記地理画像内の画素の画像値に依存する評価基準と、各部分道路領域候補の幾何学的な特徴量に依存する評価基準との両方を含むものである。これにより、各メッシュに対して検出された複数の部分道路領域候補からの暫定部分道路領域の決定が、適切に行いやすくなる。
【発明の効果】
【００１６】
本発明によれば、地理画像から道路を構成する複数の部分道路の存在領域をより簡単に検出可能になる。
【発明を実施するための最良の形態】
【００１７】
以下、本発明に係る道路領域検出可能プログラム及び道路領域検出方法の実施の形態を図面を参照して詳細に説明する。
図１は、本発明に係る、道路領域検出可能装置の一つの実施形態の概略ブロック図である。符号１は、上記装置の一つの実施の形態の全体を指す。本装置１は、処理装置１０と、記憶装置２０と、入出力装置３０とを備えている。処理装置１０は、例えばパソコン又はワークステーションにより実現される。記憶装置２０は、メインメモリとして使用されるＲＡＭ（ランダムアクセスメモリ）（図示せず）及び磁気ディスク記憶装置のような補助記憶装置（図示せず）とを含む。入出力装置３０は、キーボード及びマウス等のポインティングデバイスを含む入力装置３１と、ＣＲＴディスプレイ装置等の表示装置３２又はプリンタ３３などの出力装置を備えている。入力装置３１はパラメータの入力やコマンドの起動などに使われる。表示装置３２又はプリンタ３３は、地理画像又は検出された道路領域を示す画像などの表示又は印刷に使われる。なお、記憶装置２０内にデータが記憶されるときに、当該データが図示しないＲＡＭと図示しない補助記憶装置のいずれに記憶されるかは、あらかじめ当該データに対して決められている。
【００１８】
道路領域検出可能プログラムは、記憶装置２０に記憶され処理装置１０に組み込まれて実行されるが、図では分かりやすさのために、道路領域検出可能プログラム４０とそれを構成する複数のモジュールを、処理装置１０を示すブロックの内部に記載している。道路領域検出可能プログラム４０は、エッジ検出部１００と、領域分割部２００と、部分道路境界直線候補検出部３００と、部分道路領域候補検出部４００と、部分道路領域決定部５００と、道路領域決定部６００というモジュールを含む。
【００１９】
処理装置１０は、道路領域検出可能プログラム４０内のそれぞれのモジュールが実行されたときに、エッジを検出する機能ブロックと、地理画像の存在領域を分割する機能ブロックと、部分道路の境界直線候補を検出する機能ブロックと、部分道路の存在領域の候補を検出する機能ブロックと、部分道路の存在領域を決定する機能ブロックと、道路が存在する領域を決定する機能ブロックという複数の機能ブロックとしてコンピュータを動作させる。したがって、処理装置１０と道路領域検出可能プログラム４０のこれらのモジュールにより、それぞれのモジュールに対応する複数の機能ブロックが実現されることになる。したがって、処理装置１０と、記憶装置２０と、入出力装置３０と、エッジ検出部１００、領域分割部２００、部分道路境界直線候補検出部３００と、部分道路領域候補検出部４００と、部分道路領域決定部５００と、道路領域決定部６００は、本発明に係る。道路領域検出可能装置の一つの実施の形態を実現することになる。
【００２０】
道路領域検出可能プログラム４０は、本発明に係る道路領域検出可能プログラムの一つの実施の形態を実現するものであり、記録媒体に記録してあるいはネットワークを介して記憶装置２０に記憶され、処理装置１０で実行される。道路領域検出可能プログラム４０は、記録媒体に記録されて又はネットワークを介して販売可能である。処理装置１０が道路領域検出可能プログラム４０を実行して道路の存在領域を検出する手順は、本発明に係る道路領域検出方法の一つの実施の形態を実現する。
【００２１】
記憶装置２０には、人工衛星あるいは航空機から地表を撮影して得られる地理画像を表す地理画像データ２１と、道路ベクトルデータ２２とがあらかじめ記憶される。道路ベクトルデータ２２は、当該地表に存在する複数の道路の各々に関して、当該道路の中心線を近似的に直線で表す連結された複数の折れ線部分のそれぞれに対する始点と終点の位置情報を含むデータである。上記道路のうち、一つの折れ線状部分を道路ベクトルと呼ぶことがある。一つの道路は一つの道路ベクトルからなる場合もあり、連結された複数の道路ベクトルからなる場合もある。したがって、道路ベクトルデータは、一つの道路を一つ又は複数の道路ベクトルで表していると言うこともできる。
【００２２】
地理画像データ２１と道路ベクトルデータ２２を処理して、エッジ画像データ２３、部分道路境界直線候補データ２４、部分道路領域候補データ２５、部分道路領域データ２６、道路領域データ２７が生成され、記憶装置２０に格納される。以下では断らない限り、本実施の形態では、地理画像データ２１は、カラーの多値画像のデータであると仮定するが、本発明は、地理画像データ２１が白黒濃淡画像である場合にも適用可能である。以下では、地理画像データ２１のことを簡単化のために単に地理画像２１と呼ぶことがある。他の画像データについても同様である。また、画像データが生成又は処理されること又は記憶装置２０に記憶されることに言及するときに、簡単化のために画像データのデータという単語には言及しないで、単に画像が生成又は処理されるあるいは画像が記憶装置２０に記憶されるということがある。
【００２３】
図１に戻り、道路領域検出可能プログラム４０は、まず、エッジ検出部１００を実行する。
図２は、エッジ検出部１００の処理の概略フローチャートである。エッジ検出部１００は、地理画像内の道路を抽出する前段階として、地理画像２１内の道路の境界線や、建築物の輪郭を示すエッジ画像を検出する。本実施の形態では、後に説明するように、エッジ検出部１００によって検出されたエッジ画像に基づいて道路境界線位置を推測するので、検出されるエッジの量は適当であることが要求される。エッジが少なすぎると道路境界線を再現しにくくなり、多すぎるとノイズ分が多くなって道路境界線の決定が困難になるためである。
【００２４】
地理画像２１は、ここではＲＧＢ３原色を含むカラー画像とする。エッジ検出の前に、ステップＳ１０１において、地理画像２１の各画素のＲＧＢデータに対してＨＳＩ変換を施して、色相Ｈ、彩度Ｓ、明度Ｉの組に変換して、明度Ｉの画像を示す明度画像を生成する。この変換自体は周知である。つぎに、ステップＳ１０２において、生成された明度画像に対してヒストグラム均等化処理を行う。ヒストグラム均等化とは、画像全体又は適当な区画ごとに明度の分布を調べ、その平均値が中間値になるように、明度を一次変換して明度の分布範囲を拡大するフィルタ処理であり、それにより、全体的に明度の分布範囲が狭い画像からもエッジが検出できるようになる。
【００２５】
つぎに、ステップＳ１０３において、ヒストグラム均等化処理後の明度画像に対して、エッジ検出を実行する。この処理によって、上記明度画像内の道路や建築物の輪郭等、明度の変化が大きい部分をエッジとして抽出し、検出されたエッジを表すエッジ画像を生成する。エッジ検出方法としては、キャニー法や、ソーベルフィルタを用いたフィルタ処理などが使用できる。キャニー法に関しては、例えば、J. Canny,“A Computational Approach to Edge Detection,”IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986, vol. PAMI-8, No. 6, pp. 679〜698参照。ソーベルフィルタに関しては、例えば、尾上守夫他編集、「画像処理ハンドブック」、株式会社昭晃堂、昭和６２年６月８日、ｐ．２８０−２８１参照。
【００２６】
つぎに、ステップＳ１０４において、エッジ画像に対して２値化処理を行う。エッジ画像に対する２値化は、各画素の明度値と閾値の大小関係を調べ、閾値より大きい画素の値は、例えば「１」に、小さい画素の値は例えば「０」に変換する一般的なフィルタ処理である。これにより、エッジ画像の各画素はエッジを表す画素と、そうでない画素に２分され、２値化されたエッジ画像が得られる。閾値はあらかじめ決定されているか、２値化前のエッジ画像又はその一部分の統計情報からそれ自体公知の方法により決定することができる。つぎにステップＳ１０５において、２値化後のエッジ画像に対して小エッジの除去処理を行う。小エッジの除去とは、２値化後のエッジ画像内のエッジの中で、周囲のエッジとつながっていない、ノイズと判断できる小さなエッジを除去することを指す。以上の一連の処理で得られたエッジ画像のデータを、エッジ画像データ２３として記憶装置２０に格納して、エッジ検出部１００の処理は終了する。
【００２７】
図３は、地理画像データ２１（図１）が示す地理画像の一例を示す図である。図にはいくつかの道路が含まれていることが分かる。
図４は、道路ベクトルデータ２２（図１）を説明するための図である。同図（ａ）は、図３の地理画像２１に対応する道路ベクトルデータ２２が表す道路を図示したものである。図において、道路Ｒ１は、二つの折れ線部分（道路ベクトル）Ｒ11とＲ12を含む道路であり、道路Ｒ２については、図では一つの道路ベクトルのみが示されている。図において、黒丸は、道路の通過点を示し、道路Ｒ１の通過点として点Ｐ０、Ｐ１、Ｐ２が示され、道路Ｒ２の通過点として点Ｐ３、Ｐ４が示されている。道路Ｒ１、Ｒ２等は、図３に示された地理画像の道路の中心線の位置を表すものとして別にあらかじめ決定されたものであり、図４（ａ）において、道路Ｒ１等の位置には誤差が存在するのが普通であり、道路の中心線を正確に表すものではない。なお、本明細書では、一つの道路Ｒ１に含まれた複数の道路ベクトルの一つ、例えばＲ11を道路と呼ぶ場合もある。逆に、一つの道路ベクトルからなる道路を道路ベクトルと呼ぶこともある。
【００２８】
図４（ｂ）は、同図（ａ）に対する道路ベクトルデータ２２の例を示す図である。道路ベクトルデータ２２は、道路を構成する複数の道路ベクトルに割り当てられた道路ベクトルの識別情報２２１と、当該道路ベクトルの始点と終点に関する始点終点位置情報２２２とを含む。図では、道路Ｒ１の道路ベクトルＲ11に対する道路ベクトル識別情報２２１として記号Ｒ11が示され、始点終点位置情報２２２として点Ｐ０、Ｐ１の組が示されている。同様に、道路Ｒ１の道路ベクトルＲ12に対する道路ベクトル識別情報２２１として記号Ｒ12が示され、始点終点位置情報２２２として点Ｐ１、Ｐ２の組が示されている。道路Ｒ１には道路ベクトルＲ11、Ｒ12以外の他の道路ベクトルが含まれている場合には、それらの道路ベクトルに関するデータも道路ベクトルデータ２２に含まれる。以上のデータが道路Ｒ１に関する道路ベクトルデータである。
【００２９】
同様に、道路ベクトルデータ２２には、道路Ｒ２に関して、道路ベクトル識別情報２２１として記号Ｒ２が示され、始点終点位置情報２２２として点Ｐ３、Ｐ４の組が示されている。このように、道路ベクトルデータ２２には、複数の道路に関するデータを含むが、本明細書では、道路ベクトルデータ２２のうち、複数の道路ベクトルで構成される一つの道路、例えばＲ１に関するデータを道路ベクトルデータと呼ぶこともある。また、道路ベクトルデータ２２内の、一つの道路ベクトルに関するデータである、道路ベクトル識別情報２２１と始点終点位置情報２２２との組を道路ベクトルデータと呼ぶこともある。
【００３０】
図５は、図３に示す地理画像２１から得られたエッジ画像２３の例を示す図である。エッジ画像２３には、道路の境界線以外にも建物の輪郭線も含まれている。更に、道路の境界線もジグザグしたものであり、鮮明な直線あるいは滑らかな曲線にはなっていない部分も多い。
【００３１】
図１に戻り、道路領域検出可能プログラム４０は、領域分割部２００を実行する。領域分割部２００は、地理画像２１及びエッジ画像２３の各々が属する領域を、同じサイズを有する複数のメッシュに分割し、各メッシュの頂点位置を決定するものである。領域分割は、領域分割部２００の後に実行される部分道路境界直線候補検出部３００と、部分道路領域候補検出部４００と、部分道路領域決定部５００をメッシュ毎に行うことにより、部分道路の境界線の検出を容易にし、処理の速度と精度の向上を高めるために行われる。メッシュのサイズは、以下に述べるように、メッシュ内では、検出すべき道路が実質的に直線であり、その部分道路に対する境界線が直線であると見なすことができるという条件を少なくとも満たすように、更に、後述の処理が実行できるように、適度な値に定める。
【００３２】
道路領域検出可能プログラム４０は、領域分割部２００の実行後に、部分道路境界直線候補検出部３００を実行する。図６は、部分道路境界直線候補検出部３００の処理の概略フローチャートである。部分道路境界直線候補検出部３００は、各メッシュについて、当該メッシュを通過する道路ベクトルがある場合に、その道路の、当該メッシュ内にある部分（以下、部分道路と呼ぶことがある）の境界直線を表している可能性がある複数の直線状エッジ部分を、その部分道路の境界直線の候補としてエッジ画像２３から検出する。
【００３３】
まず、ステップＳ３０１において、前記複数のメッシュから、以下の処理を実行していない未処理のメッシュを一つ選ぶ。そのメッシュを選択メッシュと呼ぶ。ステップＳ３０２において、道路ベクトルデータ２２により示される道路ベクトルのうち、選択メッシュを通っている道路ベクトルがあるか否かを判定し、そのような道路ベクトルがある場合に、そのような道路ベクトルの全てについて当該選択メッシュ内にある部分道路を検出して、その部分道路の両端の位置の組をリストＬ１に登録する。その選択メッシュを通過する道路ベクトルが複数ある場合には、それぞれの道路ベクトルのその選択メッシュ内の部分道路をリストＬ１に登録する。
【００３４】
つぎにステップＳ３０３で、リストＬ１が空であるか否かが判定され、空の場合は、当該選択メッシュを道路ベクトルが通過していないときであるので、その選択メッシュについては以下の処理を行わず、ステップＳ３０１に戻り、次のメッシュを選択する。ステップＳ３０３での判定の結果、選択メッシュが空でないと判定された場合、ステップＳ３０４において、選択メッシュ内に位置する直線状エッジ部分を全てエッジ画像データ２３から検出する。得られた直線状エッジ部分の始点と終点の組をリストＬ２に格納する。
【００３５】
直線状エッジ部分の検出では、選択メッシュに含まれているエッジの中から、既に一つの直線としてつながっているエッジ部分を検出するだけでなく、複数のエッジ部分に分離されているが、つなげれば直線を形成する位置にある複数のエッジ部分の組を見つけ出し、それらの複数のエッジ部分の組を連結して一つの直線状エッジ部分に変換することも行う。なぜなら、部分道路の境界直線は、建物の影により、あるいは交差点の存在等により、複数の部分に分断された複数の直線状エッジ部分として検出される可能性があるからである。
【００３６】
上記直線状エッジ部分の検出法としては、例えばハフ（Hough）変換が挙げられる。例えば、“Method and Means for recognizing complex patterns"，米国特許第3,069,654号，1962参照。ハフ変換では、複数部分に切断された直線も一つの直線に復元することができる。したがって、上記のような、同じ道路の境界直線を構成するべきエッジが複数の直線状エッジ部分に分断されている場合でも、それらのエッジ部分を検出して一つの直線状エッジ部分として検出することに適している。直線状エッジ部分の検出処理は、検出対象範囲が大きいと処理時間が掛かるが、本実施の形態では、エッジ画像を複数のメッシュに分割して、メッシュ毎に直線状エッジ部分を検出するので、この問題は緩和される。逆に、各メッシュのサイズは、先に述べた条件の他に、直線状エッジ部分の検出のための時間が適度に小さい値となるという条件を満たすように定めてもよい。
【００３７】
つぎにステップＳ３０５において、得られたリストＬ２から未チェックの直線状エッジ部分を１つ選択し、ステップＳ３０６において、その直線状エッジ部分が、リストＬ１に含まれるいずれかの部分道路に対する境界直線になるための条件を満たすか否かを判定する。この判定では、選択された直線状エッジ部分がリストＬ１内のいずれかの部分道路に対して所定の位置条件を満たすか否かが判定される。この判定では、選択された直線状エッジ部分がリストＬ１内のいずれかの部分道路に対して平行であるという第１の条件が満たされるか否かが判定され、その第１の条件が満たされた場合に、更に、選択された直線状エッジ部分がその部分道路から所定の距離以内にあるという第２の条件が満たされるか否かが判定される。このように、選択された直線状エッジ部分がいずれかの部分道路に対して部分道路領域境界直線候補となるための位置条件と、この位置条件を満たすか否かの判定は非常に簡単である。
【００３８】
本実施の形態では、道路ベクトルデータ２２に含まれた道路ベクトルの始点と終点の位置には誤差があると仮定しているので、リストＬ２から選択された直線状エッジ部分の位置とリストＬ１に登録されたいずれかの部分道路の位置が所定の許容位置ずれ範囲内で一致していなくても、当該直線状エッジ部分は、当該部分道路に対する境界直線である場合もあると考えている。
【００３９】
しかし、リストＬ２から選択された直線状エッジ部分の方向は、リストＬ１に登録されたいずれかの部分道路の方向と所定の角度差の限界内で一致しないと、当該直線状エッジ部分は、当該部分道路の境界直線とはなり得ないと判断する。すなわち、道路ベクトルデータ２２で示す部分道路の位置には誤差があっても、道路ベクトルデータ２２が示す部分道路の方向には大きな誤差はないと仮定している。したがって、ステップＳ３０６での判定では、選択された直線状エッジ部分の方向と、道路ベクトルデータが示す部分道路の方向は、所定の許容角度ずれ範囲内で一致しているかがまず判断される。この許容角度ずれ範囲は、例えば、２度あるいは５度程度とすることができる。このように比較的大きな許容角度ずれ範囲を使用するのは、実際の道路ベクトルの方向も、メッシュ内という限定された範囲内では、道路ベクトルデータ２２が示す道路ベクトルの方向からずれている可能性があるので、そのような大きな角度ずれ範囲を許容してもよいとの考えに基づく。
【００４０】
ステップＳ３０６での判定では、選択された直線状エッジ部分の方向と道路ベクトルデータ２２が示す部分道路の方向とが、所定の許容角度ずれ範囲内で平行であるときには、両者の間の距離が所定の制限距離以内であるか否かを次に判定し、両者がこの距離よりも大きく隔たっているときには、当該直線状エッジ部分は、メッシュ内の部分道路の境界直線とは見なさない。ここで、所定の制限距離とは、選択された直線状エッジ部分が、画像内に含まれる可能性のある道路が通常持ち得る道路幅の最大値程度に等しい距離を言う。選択された直線状エッジ部分が、道路が通常持ち得る道路幅の最大値程度の距離よりもかなり大きくずれているときには、当該直線状エッジ部分は、部分道路の境界直線とは見なさない。この判定は、当該直線状エッジ部分と、道路ベクトルデータ２２が示す部分道路の位置との一致を判定するものではない。なお、選択された直線状エッジ部分と道路ベクトルデータ２２が示す部分道路との間の距離には、両者の間の最も近い部分間の距離を使用すればよい。
【００４１】
ステップＳ３０６での判定において、選択された直線状エッジ部分が上記第１、第２の条件の両方を満すと判定されたときには、ステップＳ３０７において、選択された直線状エッジ部分は、リストＬ１内の、上記第１、第２の条件に関する判定対象とされたいずれかの部分道路に対する部分道路境界直線候補の一つと見なされ、当該部分道路と当該選択された直線状エッジ部分との組を部分道路境界直線候補データ２４の一部として、記憶装置２０に記憶し、その後ステップＳ３０８において、選択された直線状エッジ部分をリストＬ２から削除し、処理はステップＳ３０９に進む。
【００４２】
ステップＳ３０６での判定において、選択された直線状エッジ部分が上記第１、第２の条件の少なくとも一方を満さないと判定されたときには、処理はステップＳ３０８に進み、選択された直線状エッジ部分をリストＬ２から削除し、処理はステップＳ３０９に進む。ステップＳ３０９においては、リストＬ２内の全ての直線状エッジ部分のチェックが終了したか否かが判断され、終了していないときには、ステップＳ３０５以降の処理が繰り返される。ステップＳ３０９での判定の結果、選択メッシュに関して全ての直線状エッジ部分のチェックが終了したと判断されたときには、ステップＳ３１０において、全てのメッシュでの処理が終了しているか否かを判定し、終了していないときには、ステップＳ３０１以降の処理が未処理のメッシュに関して繰り返される。
【００４３】
図７は、エッジ画像２３を分割して得られる複数のメッシュとそれらのメッシュに対して抽出された複数の部分道路境界直線候補を模式的に示す図である。図においては、一点鎖線Ｒ11、Ｒ12、Ｒ３は、図４（ａ）に示されたように、それぞれ道路ベクトルデータ２２で示される複数の道路ベクトルの例を示す。道路ベクトルＲ11とＲ12は、いずれも道路Ｒ１（図４（ａ））に属する道路ベクトルである。道路ベクトルＲ11は始点Ｐ０と終点Ｐ１を有し、道路ベクトルＲ12は、道路ベクトルＲ11の終点Ｐ１を始点とし終点Ｐ２を有する。道路ベクトルＲ３は、道路ベクトルＲ１に交叉する道路ベクトルの例であり、始点Ｐ３と終点Ｐ４とを有する。図ではエッジ画像２３は３×３個のメッシュＭ０〜Ｍ８のみを含んでいるが、これは図の簡単化のためであり、エッジ画像データ２３に含まれる実際のメッシュ数はもっと多いのが普通である。道路ベクトルＲ11、Ｒ12、Ｒ３は、複数のメッシュを通過している。例えば、道路ベクトルＲ11は、メッシュＭ０内に位置する部分道路、メッシュＭ１内に位置する部分道路、メッシュＭ４内に位置する部分道路、メッシュＭ５内に位置する部分道路に区分されることが分かる。
【００４４】
図には、道路ベクトルＲ１に対して部分道路境界直線候補検出部３００（図６）のステップＳ３０４において検出される複数の直線状エッジ部分が模式的に示されている。メッシュＭ０に関しては、直線状エッジ部分Ｅ０、Ｅ１、Ｅ５が検出されている。メッシュＭ１に関しては、直線状エッジ部分Ｅ２、Ｅ６、Ｅ９、Ｅ11が検出されている。メッシュＭ２に関しては、直線状エッジ部分Ｅ12が検出されている。メッシュＭ４に関しては、直線状エッジ部分Ｅ３、Ｅ７が検出されている。メッシュＭ５に関しては、直線状エッジ部分Ｅ４、Ｅ８、Ｅ10、Ｅ13が検出されている。なお、図では、直線状エッジ部分Ｅ０、Ｅ１のように、他の直線状エッジ部分に接続されていないものもある。図の例では、直線状エッジ部分Ｅ２からＥ４、Ｅ５からＥ８、Ｅ９からＥ10、Ｅ11からＥ13はそれぞれ連結されているが、これらの直線状エッジ部分は、直線状エッジ部分Ｅ０、Ｅ１と同様に、他の直線状エッジ部分から分離されていてもよいことは言うまでもない。
【００４５】
メッシュＭ０に関して検出された直線状エッジ部分Ｅ０は、部分道路境界直線候補検出部３００（図６）のステップＳ３０６の判定では、道路ベクトルＲ11からの距離が大きいために、道路ベクトルＲ11のうちのメッシュＭ０に属する部分道路に対する部分道路境界直線候補とは判定されないと仮定する。図においては、直線状エッジ部分Ｅ１からＥ13は、いずれも、道路ベクトルＲ１のうちのそれぞれが属するメッシュ内の部分道路に対する部分道路境界直線候補であると判定されると仮定する。
【００４６】
図８は、部分道路境界直線候補データ２４の例を示す図である。部分道路境界直線候補データ２４には、道路ベクトル識別情報（以下、識別情報を単にＩＤと呼ぶことがある）２４１、メッシュ識別情報２４２、部分道路位置情報２４３、境界直線候補位置情報２４４とを含む。図では、道路ベクトル識別情報２４１には、簡単化のために、Ｒ11等の、道路ベクトルに付した記号を識別情報として示している。メッシュ識別情報２４２には、簡単化のために、Ｍ０等の、メッシュに付した記号を識別情報として示している。メッシュ識別情報２４２には、注目する道路ベクトルＲ11が通過するメッシュの識別情報が格納され、その道路ベクトルが通過しないメッシュの識別情報は格納されない。部分道路位置情報２４３には、メッシュ内の部分道路の始点位置と終点位置との組が記憶されるが、図では、簡単化のために、図７に示した記号Ｐ０、Ｕ１等の、メッシュ内の部分道路の始点と終点の記号の組を示している。境界直線候補位置情報２４４には、メッシュ内の直線状エッジ部分の始点と終点の座標を格納すればよいが、図では分かりやすさのためにＥ１等の図７に示した直線状エッジ部分の記号と、Ｆ１、Ｇ１等のその直線状エッジ部分の始点と終点の記号の組とを示している。
【００４７】
図７の例では、図８に示すように、道路ベクトルＲ11に関しては、メッシュＭ０に対しては直線状エッジ部分Ｅ１、Ｅ５が部分道路境界直線候補として記憶され、メッシュＭ１に対しては直線状エッジ部分Ｅ２、Ｅ６が部分道路境界直線候補として記憶され、メッシュＭ４に対しては直線状エッジ部分Ｅ３、Ｅ７が部分道路境界直線候補として記憶され、メッシュＭ５に対しては直線状エッジ部分Ｅ４、Ｅ８、Ｅ１０、Ｅ１３が部分道路境界直線候補として記憶される。なお、部分道路境界直線候補データ２４には、他の道路に関しても同様なデータが記憶されるが、簡単化のためにそれらのデータは図示していない。
【００４８】
図１に戻り、道路領域検出可能プログラム４０は、部分道路領域候補検出部４００を実行する。図９は、部分道路領域候補検出部４００の処理の概略フローチャートである。部分道路領域候補検出部４００は、地理画像２１中の道路について、その道路が通過するメッシュ内のその道路が存在する可能性がある領域の複数の候補（部分道路領域候補）を部分道路境界直線候補データ２４と道路ベクトルデータ２２とから検出して、部分道路領域候補データ２５内に格納する。
【００４９】
部分道路領域候補検出部４００は、道路ベクトルデータ２２に含まれる複数の道路ベクトルのそれぞれに対して実行される。そのため、まず、ステップＳ４０１で、いずれかの未処理の道路を道路ベクトルデータ２２から選択し、ステップＳ４０２において、その選択道路に含まれるいずれかの未処理の道路ベクトルを選択し、道路ベクトルデータ２２からその選択道路ベクトルに関するデータを読み出す。具体的には、図４（ｂ）に示す道路ベクトルデータ２２の場合、一つの道路ベクトル識別情報２２１と対応する始点終点位置情報２２２との組からなる一つの道路ベクトルデータを選択し、読み出す。例えば、図４（ａ）の道路ベクトルＲ11を選択し、道路ベクトルデータ２２からその道路ベクトルＲ11に関する道路ベクトル識別情報２２１としてのＲ11と、始点終点位置情報２２２としての点Ｐ０、Ｐ１とを読み出す。以下では、選択された上記一つの道路ベクトル（今の例ではＲ11）を以下では選択道路ベクトルと呼ぶことがある。
【００５０】
つぎに、ステップＳ４０３において、選択道路ベクトル（例えばＲ11）が通過する複数のメッシュのうち未処理のメッシュを一つ選択する。上記選択道路ベクトルが通過する複数のメッシュの識別情報は、部分道路境界直線候補データ２４（図８）内に、上記選択道路ベクトルの道路ベクトル識別情報２２１であるＲ11と同じ道路ベクトル識別情報２４１に対応して記憶されている。例えば選択道路ベクトルＲ11が通過するメッシュはメッシュＭ０、Ｍ１、Ｍ４、Ｍ５である。したがって、上記ステップＳ４０３での未処理のメッシュの検出は、部分道路境界直線候補データ２４内に、上記選択された道路ベクトルの道路ベクトル識別情報２２１であるＲ11と同じ道路ベクトル識別情報２４１に対応して記憶されている複数のメッシュ識別情報２４２のうち、以下の処理を行っていない一つの未処理のメッシュ識別情報２４２を選択することにより行える。例えば、メッシュＭ０が選択される。上記選択されたメッシュを以下では選択メッシュと呼ぶことがある。
【００５１】
つぎにステップＳ４０４において、上記選択道路ベクトル（例えばＲ11）の、上記選択メッシュ内の部分道路に対する部分道路境界直線候補を部分道路境界直線候補データ２４（図８）から読み出し、リストＭに登録する。今の例では、選択道路ベクトルＲ11に対しては、メッシュＭ０に含まれる部分道路境界直線候補Ｅ１（Ｆ１，Ｇ１）とＥ５（Ｆ５，Ｇ５）が、リストＭに登録される。部分道路境界直線候補Ｅ１とＥ５は、図７に示されたように、メッシュＭ０内にあり、選択道路ベクトルＲ11に平行で、かつ、距離がある一定値以内にあり、選択道路ベクトルＲ11のうちメッシュＭ０内にある部分道路が存在する領域の境界直線となる可能性がある直線である。
【００５２】
つぎにステップＳ４０５において、リストＭに登録された部分道路境界直線候補の数が２以上であるか否かを判定する。今の例では、その数は２である。このようにリストＭに登録された部分道路境界直線候補の数が２以上である場合は、ステップＳ４０６において、リストＭに登録された複数の部分道路境界直線候補のうちの任意の二つを組み合わせて、その組と選択道路ベクトルＲ11に関する道路ベクトルデータとに基づいて選択メッシュＭ０内で選択道路ベクトルＲ11が存在する可能性がある４辺形領域を決定し、当該４辺形領域を、選択道路ベクトルＲ11に対する選択メッシュＭ０内の部分道路領域候補として、部分道路領域候補データ２５内に格納する。上記４辺形領域の決定方法は後に述べる。
【００５３】
ステップＳ４０６の終了後に、ステップＳ４０８において、選択道路ベクトル（Ｒ11）が通過するメッシュの全てを選択したか否かが判定され、まだ選択されていないメッシュがあるときには、処理はステップＳ４０３に戻り、以上の処理が繰り返される。本実施の形態では、選択道路ベクトルＲ11が通過する他のメッシュは、図８に示した部分道路境界直線候補データ２４から分かるように、メッシュＭ１、Ｍ４、Ｍ５である。したがって、これらのメッシュに関して以上の処理が繰り返される。
【００５４】
なお、ステップＳ４０５において、リストＭに登録された部分道路境界直線候補の数が１であると判定されたときには、ステップＳ４０７においてリストＭ内の部分道路境界直線候補を削除し、その後処理はステップＳ４０８に移る。なお、ステップＳ４０５において、リストＭに登録された部分道路境界直線候補の数が０であると判定される場合は生じない。部分道路境界直線候補の数が０であるようなメッシュは、ステップＳ４０３において選択されないからである。
【００５５】
以上のような処理の繰り返しにより、ステップＳ４０８において、選択道路ベクトルが通過する全てのメッシュの選択が終了したと判断されたときには、ステップＳ４０９において、選択道路ベクトル（今の例ではＲ11）が属する道路に含まれる道路ベクトルの全てが処理されたか否かが判定される。もし未処理の他の道路ベクトル（例えばＲ12）があるときには、処理はステップＳ４０２に移り、例えば、上記選択道路ベクトルＲ11につながった他の道路ベクトルＲ12について、ステップＳ４０２以降の処理が繰り返される。その後、ステップＳ４０９において、選択道路ベクトル（今の例ではＲ12）が属する道路に含まれる道路ベクトルの全てが処理されたと判定されときには、ステップＳ４１０において、処理された複数の道路ベクトルを含む道路と異なる、他の道路ベクトルを含む未処理の他の道路があるか否かが判定され、そのような未処理の他の道路があるときには、処理はステップＳ４０１に戻り、当該他の道路に含まれた複数の道路ベクトルに関してステップＳ４０１以降の処理が繰り返される。その後、ステップＳ４１０において、他の道路ベクトルを含む未処理の他の道路がないと判定されたときに、部分道路領域候補検出部４００の処理が終了する。
【００５６】
部分道路領域候補検出部４００の処理のうち、ステップＳ４０５での処理の詳細を説明する。図１０は、道路ベクトルＲ11に対して検出される部分道路領域候補の例を示す図である。メッシュＭ０に関しては、図９のステップＳ４０４では、部分道路境界直線候補Ｅ１、Ｅ５がリストＭに登録されている。一方、選択道路ベクトルＲ11のうちのメッシュＭ０内の部分道路は点Ｐ１から点Ｕ１までである。以下この部分道路を両端の点を並べてＰ0Ｕ1でもって表す。部分道路境界直線候補Ｅ１、Ｅ５と部分道路Ｐ0Ｕ1のうちでは、部分道路Ｐ0Ｕ1が一番短い。図９のステップＳ４０５では、リストＭに登録された二つの部分道路境界直線候補Ｅ１、Ｅ５上にある、部分道路Ｐ0Ｕ1を越えない長さ（今の例ではそれと同じ長さ）を有し、選択道路ベクトルＲ11に平行でともにメッシュＭ０内に位置する２辺と、選択道路ベクトルＲ11に垂直でともにメッシュＭ０内に位置する２辺とを有するという部分道路領域候補条件を満たす４辺形Ｊ11Ｊ12Ｊ52Ｊ51が、部分道路Ｐ0Ｕ1に対する部分道路領域候補として検出される。
【００５７】
図１１は、部分道路領域候補データ２５の例を示す図である。部分道路領域候補データ２５には、部分道路領域候補検出部４００により検出された部分道路領域候補に関して、道路ベクトル識別情報２５１と、メッシュ識別情報２５２と、４辺形情報２５３とが格納される。図１０に示した４辺形Ｊ11Ｊ12Ｊ51Ｊ52に関しては、例えば道路ベクトル識別情報２５１として選択道路ベクトルの道路ベクトル識別情報Ｒ11が格納され、メッシュ識別情報２５２には、メッシュＭ０の識別情報Ｍ０が格納され、４辺形情報２５３には検出された４辺形を構成する二つの部分道路境界線候補の記号Ｅ１、Ｅ５と、両候補のそれぞれ上の２頂点Ｊ11とＪ12及びＪ51とＪ52とが格納される。
【００５８】
図１０に戻り、メッシュＭ０にある部分道路境界直線候補は上記のＥ１、Ｅ５のみであり、上記部分道路領域候補条件を満たす他の部分道路領域候補はメッシュＭ０からは検出されない。メッシュＭ１に関しては、図９のステップＳ４０４では、部分道路境界直線候補Ｅ２、Ｅ６がリストＭに登録されている。一方、選択道路ベクトルＲ11のうちのメッシュＭ１内の部分道路は点Ｕ１から点Ｕ２までである。図９のステップＳ４０５では、リストＭに登録された二つの部分道路境界直線候補Ｅ２、Ｅ６と部分道路Ｕ1Ｕ2とから、部分道路Ｕ1Ｕ2に対する部分道路領域候補が、既に述べた部分道路領域候補条件を満すように決定される。この際、部分道路境界直線候補Ｅ６は、点Ｇ５からＧ６までである。一方、部分道路境界直線候補Ｅ２は点Ｆ２からＧ２までであり、部分道路Ｕ1Ｕ2及び部分道路境界直線候補Ｅ６より短いが、部分道路Ｕ1Ｕ2が存在する範囲と平行で、メッシュＭ１内に位置する範囲内にある線分Ｊ21Ｇ２まで延長可能な直線として扱われる。こうして、上記部分道路領域候補条件を満す４辺形として、部分道路境界直線候補Ｅ２上の点Ｊ21から点Ｇ２までの線分と、部分道路境界直線候補Ｅ６上の点Ｊ61から点Ｊ62までの線分とにより規定される４辺形Ｊ21Ｇ２Ｊ62Ｊ61が検出される。
【００５９】
同様に、メッシュＭ４に関しては、図９のステップＳ４０４では、部分道路境界直線候補Ｅ３、Ｅ７がリストＭに登録されている。一方、選択道路ベクトルＲ11のうちのメッシュＭ４内の部分道路は点Ｕ２から点Ｕ３までである。図９のステップＳ４０５では、リストＭに登録された二つの部分道路境界直線候補Ｅ３、Ｅ７と部分道路Ｕ2Ｕ3とから、部分道路Ｕ2Ｕ3に対する部分道路領域候補が、既に述べた部分道路領域候補条件を満すように決定される。この際、部分道路Ｕ1Ｕ2は、部分道路境界直線候補Ｅ３、Ｅ６よりも短いので、メッシュＭ０の場合と同様にして、図に示すように、上記部分道路領域候補条件を満す４辺形として、部分道路境界直線候補Ｅ３上の点Ｊ31から点Ｊ32までの線分と、部分道路境界直線候補Ｅ７上の点Ｊ71から点Ｊ72までの線分とにより規定される４辺形Ｊ31Ｊ32Ｊ72Ｊ71が検出される。
【００６０】
同様に、メッシュＭ５に関しては、図９のステップＳ４０４では、部分道路境界直線候補Ｅ４、Ｅ８がリストＭに登録されている。一方、選択道路ベクトルＲ11のうちのメッシュＭ５内の部分道路は点Ｕ３から点Ｐ１までである。図９のステップＳ４０５では、リストＭに登録された二つの部分道路境界直線候補Ｅ４、Ｅ８と部分道路Ｕ3Ｐ1とから、部分道路Ｕ3Ｐ1に対する部分道路領域候補が、既に述べた部分道路領域候補条件を満すように決定される。この際、部分道路境界直線候補Ｅ４は、点Ｇ３からＧ４までであり、部分道路Ｕ3Ｐ1より短いが、部分道路Ｕ3Ｐ1が存在する範囲と平行で、メッシュＭ４内に位置する範囲内にある線分Ｇ３Ｊ41まで延長可能な直線として扱われる。同様に、部分道路境界直線候補Ｅ８は、点Ｇ７からＧ８までであり、部分道路Ｕ3Ｐ1より短いが、部分道路Ｕ3Ｐ1が存在する範囲と平行で、メッシュＭ４内に位置する範囲内にある線分Ｇ７Ｊ81まで延長可能な直線として扱われる。こうして、上記部分道路領域候補条件を満す４辺形として、部分道路境界直線候補Ｅ４上の点Ｇ３から点Ｊ41までの線分と、部分道路境界直線候補Ｅ８上の点Ｇ８から点Ｊ81までの線分とにより規定される４辺形Ｇ３Ｊ41Ｊ81Ｇ８が検出される。
以上のようにメッシュＭ１、Ｍ４、Ｍ５に対して検出された４辺形の情報も、部分道路領域候補として、図１１に示したように部分道路領域候補データ２５内に格納される。
【００６１】
図１２は、道路ベクトルＲ11に対して検出される他の部分道路領域候補の例を示す図である。図では、メッシュＭ１に対して、部分道路境界直線候補Ｅ２上の点Ｊ21から点Ｇ２までの線分と部分道路境界直線候補Ｅ９上の点Ｊ91から点Ｊ92までの線分とにより規定される４辺形Ｊ21Ｇ２Ｊ92Ｊ91が検出される。メッシュＭ５に対して、部分道路境界直線候補Ｅ４上の点Ｇ３から点Ｊ41までの線分と部分道路境界直線候補Ｅ10上の点Ｊ101から点Ｊ102までの線分とにより規定される４辺形Ｇ３Ｊ41Ｊ102Ｊ101が検出される。
【００６２】
図１３は、道路ベクトルＲ11に対して検出される更に他の部分道路領域候補の例を示す図である。図では、メッシュＭ１に対して、部分道路境界直線候補Ｅ２上の点Ｊ21から点Ｇ２までの線分と部分道路境界直線候補Ｅ11上の点Ｊ111から点Ｊ112までの線分とにより規定される４辺形Ｊ21Ｇ２Ｊ112Ｊ111が検出される。メッシュＭ５に対して、部分道路境界直線候補Ｅ４上の点Ｇ３から点Ｊ41までの線分と部分道路境界直線候補Ｅ13上の点Ｊ131から点Ｊ132までの線分とにより規定される４辺形Ｇ３Ｊ41Ｊ132Ｊ131が検出される。
【００６３】
図１４は、道路ベクトルＲ11に対して検出される更に他の部分道路領域候補の例を示す図である。図では、メッシュＭ１に対して、部分道路境界直線候補Ｅ６上の点Ｇ５から点Ｇ６までの線分と部分道路境界直線候補Ｅ９上の点Ｊ93から点Ｊ94までの線分とにより規定される４辺形Ｇ５Ｇ６Ｊ92Ｊ91が検出される。メッシュＭ５に対して、部分道路境界直線候補Ｅ８上の点Ｇ７から点Ｊ81までの線分と部分道路境界直線候補Ｅ10上の点Ｊ103から点Ｊ102までの線分とにより規定される４辺形Ｇ７Ｊ81Ｊ102Ｊ103が検出される。
【００６４】
図１５は、道路ベクトルＲ11に対して検出される更に他の部分道路領域候補の例を示す図である。図では、メッシュＭ１に対して、部分道路境界直線候補Ｅ６上の点Ｇ５から点Ｇ６までの線分と部分道路境界直線候補Ｅ11上の点Ｊ111から点Ｊ112までの線分とにより規定される４辺形Ｇ５Ｇ６Ｊ112Ｊ111が検出される。メッシュＭ５に対して、部分道路境界直線候補Ｅ８上の点Ｇ７から点Ｊ81までの線分と部分道路境界直線候補Ｅ13上の点Ｊ133から点Ｊ132までの線分とにより規定される４辺形Ｇ７Ｊ81Ｊ132Ｊ133が検出される。
【００６５】
図１６は、道路ベクトルＲ11に対して検出される更に他の部分道路領域候補の例を示す図である。図では、メッシュＭ１に対して、部分道路境界直線候補Ｅ９上の点Ｊ95から点Ｊ96までの線分と部分道路境界直線候補Ｅ11上の点Ｆ11から点Ｇ11までの線分とにより規定される４辺形Ｊ91Ｊ92Ｇ11Ｆ11が検出される。メッシュＭ５に対して、部分道路境界直線候補Ｅ10上の点Ｊ104から点Ｊ102までの線分と部分道路境界直線候補Ｅ13上の点Ｇ12から点Ｊ132までの線分とにより規定される４辺形Ｊ104Ｊ102Ｊ132Ｇ12が検出される。
【００６６】
図１２から図１６を用いて説明したように、メッシュＭ１、Ｍ４、Ｍ５に対して検出されたいろいろな４辺形の情報は、図１１に示したように、部分道路領域候補データ２５内に部分道路領域候補として追加して格納される。
なお、以上の処理では、例えば図７から分かるように、一つの道路ベクトルのうち、一つのメッシュに属する部分道路の全長に対応して部分道路境界直線候補が存在していても、そのメッシュにおいて検出される部分道路領域候補は、当該部分道路の全長の一部に対するものであり、当該部分道路の残りの部分に対しては部分道路領域候補は検出されない場合が生じているが、検出されない部分道路領域は、後に説明するように補間により決定される。
また、図７等では、説明のために検出される部分道路境界直線候補の数は少なくしているが、一つの道路ベクトル、例えばＲ11に関して、一つのメッシュに対して実際に検出される部分道路境界直線候補の数は１０数本になることがあり、このため、同じ一つの道路ベクトルＲ11に関して一つのメッシュに対して検出される部分道路領域候補の数は数十〜百数十になると考えられる。
【００６７】
図１に戻り、道路領域検出可能プログラム４０は、部分道路領域候補検出部４００の実行後に部分道路領域決定部５００を実行する。
図１７は、部分道路領域決定部５００の処理の概略フローチャートである。部分道路領域決定部５００は、部分道路領域候補検出部４００で検出された複数の部分道路領域候補の中から実際の道路の存在領域を表す可能性が最も高い部分道路領域を決定する。
【００６８】
まず、ステップＳ５０１において、いずれかの道路に含まれたいずれかの道路ベクトルを選択する。ステップＳ５０２において、当該選択道路ベクトルが通過するメッシュであって、当該メッシュに対して当該選択道路ベクトルに対する部分道路領域候補が少なくとも一つ部分道路領域候補データ２５に含まれているメッシュを選択する。つぎにステップＳ５０３においてメッシュの選択が成功か否かを判定し、不成功の場合には、ステップＳ５０４において、当該選択道路ベクトルは廃止された道路であると判断し、部分道路領域データ２６内に、当該選択道路ベクトルに対応して廃止を示す情報を格納する。その後処理はステップＳ５０９に移動する。
【００６９】
一方、ステップＳ５０３においてメッシュ選択が成功と判断されたときには、ステップＳ５０５において、部分道路領域候補データ２５（図１１）から、当該選択道路ベクトルのうち当該選択メッシュに属する部分道路に対する部分道路領域候補を、それらが複数ある場合には、全て読み出す。具体的には、その選択メッシュに対する４辺形情報２５３（図１１）を読み出す。
【００７０】
ステップＳ５０６とＳ５０７において、それらの部分道路領域候補の各々について、部分道路領域である可能性を個別に評価する。本実施の態様では、個別評価は、各部分道路領域候補に属する、前記地理画像内の画素の画像値に依存する評価基準に基づく評価と各部分道路領域候補の幾何学的な特徴量に依存する評価基準に基づく評価の両方を行う。これにより、各メッシュに対して検出された複数の部分道路領域候補に対する評価がより適切に行いやすくなる。
【００７１】
まずステップＳ５０６では、各部分道路領域候補を地理画像２１の画像値に基づいて評価する。例えば、部分道路領域候補内の画素の色によって、例えば色の分布状態によって、その領域が道路である可能性が高いか否かを評価する。例えば、部分道路領域候補について、当該候補領域内の画素の３原色成分（Ｒ、Ｇ、Ｂ）に対応する色相Ｈの標準偏差を計算する。既に述べたように、エッジ検出部１００（図２）では、ステップＳ１０１において、地理画像２１のＲＧＢ成分を色相Ｈ、彩度Ｓ、明度Ｉの成分に変換している。したがって上記ステップＳ５０６において色相の標準偏差を求めるときに、エッジ検出部１００により生成された色相データを利用すればよい。一般に道路は、灰色等の一様な色であるので、色相の分散が小さい部分道路領域候補は、道路領域を表す可能性が高い。例えば、コンクリート道路では標準分散は３０度位である。したがって、部分道路領域候補内の画素の色の標準分散を第１の評価値とする。したがって、部分道路領域候補の第１の評価値が小さいほど、道路領域を表す可能性が高いことになる。もちろん、色の分布に関して他の物理量を評価値としてもよい。
【００７２】
つぎに、ステップＳ５０７において、各部分道路領域候補を各部分道路領域候補の幾何学的な特徴量に基づいて評価する。例えば、各部分道路領域候補が表す部分道路領域の幅により評価する。これは、複数の車線を含む道路の特徴を利用して、部分道路領域候補を評価することである。具体的には、部分道路領域候補が示す道路幅が、１車線の道路の標準的な道路幅（通常の２．７５ｍ〜３．５ｍのうちからあらかじめ定めた値）又はその複数倍に一致する場合に、最小の評価値（部分道路領域である可能性が高いことを示す評価値）を決定し、部分道路領域候補が示す道路幅が、上記標準的な道路幅又はその倍数からずれるにしたがって高い評価値を決定するように、部分道路領域候補に対して、当該部分道路領域候補が示す道路幅に依存した第２の評価値を決定する。図１８は、道路幅と第２の評価値との関係の例を示す図である。図では、１車線の標準の道路幅は３．５ｍとし、部分道路領域候補の道路幅がこの標準値の整数倍であるときに、第２の評価値を０とし、それらの値の丁度中間のときに、第２の評価値を１としている。
【００７３】
部分道路領域候補に対する最終的な評価値は、上記第１、第２の評価値を重みを付けて加算して、例えば下記の式１により決定することができる。
最終評価値＝第１の評価値＋２０×第２の評価値 （１）
【００７４】
ステップＳ５０８では、各部分道路領域候補に対して上記最終評価値を計算し、その値が最も小さい部分道路領域候補を、前記選択道路のうち選択メッシュ内に位置する部分道路が存在する道路領域である可能性が最も高い暫定部分道路領域として決定する。決定された暫定部分道路領域に関するデータを、部分道路領域データ２６内に暫定部分道路領域として格納する。
その後、ステップＳ５０９において、前記選択道路ベクトルが通過する他のメッシュであって、部分道路領域候補が部分道路領域候補データ２５に格納されているメッシュがあるか否かを判定し、あると判定された場合には、処理はステップＳ５０２に戻り、ステップＳ５０２以降の処理が、前記選択道路が通過する他のメッシュであって、部分道路領域候補が部分道路領域候補データ２５に格納されているメッシュが存在しないと判定されるまで繰り返される。
【００７５】
図１９は、部分道路領域決定部５００により決定される暫定部分道路領域の例を示す図である。図では、道路ベクトルＲ11に対して、メッシュＭ１内では４辺形Ｊ21Ｇ２Ｊ112Ｊ111が暫定部分道路領域として決定され、メッシュＭ５内では４辺形Ｇ３Ｊ41Ｊ132Ｊ131が暫定部分道路領域として決定されている。
【００７６】
図２０は、部分道路領域データ２６の例と、上記二つの暫定部分道路領域が決定されたときのその部分道路領域データ２６の値の例を示す図である。部分道路領域データ２６は、処理中の道路ベクトル（今の例ではＲ11）の道路ベクトル識別情報２６１、部分道路領域が決定されたメッシュの識別情報２６２、４辺形情報２６３、確定フラグ２６４とを含む。図の例では、道路ベクトル識別情報２６１には道路ベクトルの記号Ｒ11が格納され、メッシュ識別情報２６２には、メッシュ番号Ｍ１又はＭ５が格納され、４辺形情報２６３には、決定された４辺形の頂点Ｊ21，Ｇ２，Ｊ112，Ｊ111又はＧ３，Ｊ41，Ｊ131，Ｊ132が格納されている。確定フラグ２６４には、４辺形情報２６３が示す部分道路領域が暫定部分道路領域であることを示す値０が格納されている。後に暫定部分道路領域が最終的に部分道路領域として決定されたときには、確定フラグ２６４には４辺形情報２６３が示す部分道路領域が確定された部分道路領域であることを示す値１が設定されるようになっている。
【００７７】
以上の処理では、選択道路ベクトルに関して複数のメッシュに対して決定された複数の部分道路領域候補を個別に評価して、当該選択道路ベクトルに対する複数の暫定部分道路領域を決定した。部分道路領域決定部５００では、選択道路ベクトルに対して決定された複数の暫定部分道路領域の相互のつながりを考慮するために、更に以下の処理を実行し、決定された複数の暫定部分道路領域候補の相互の位置関係が所望の位置関係にあるか否かを判断し、最終的な部分道路領域を決定する。このために、図１７に戻り、部分道路領域決定部５００では、選択道路に対するステップＳ５０２以降の処理の繰り返しの後に、ステップＳ５０９において、前記選択道路が通過する他のメッシュであって、部分道路領域候補が部分道路領域候補データ２５に格納されているメッシュが存在しないと判定されたときに、処理はステップＳ５１０に移る。
【００７８】
ステップＳ５１０では、同じ選択道路ベクトルに関して、異なるメッシュに対して個別に決定された上記複数の暫定部分道路領域の各々と、当該暫定部分道路領域に対して最も近い位置にある他の暫定部分道路領域とが隣接する部分道路領域となるための望ましい所定の位置関係を有するか否かを判定する。例えば、それらの暫定部分道路領域の幅が所定の誤差範囲内で一致し（すなわち、それらの暫定部分道路領域の幅の相違は上記所定の誤差範囲内であり）、かつ、それらの暫定部分道路領域の中心線の位置が所定の誤差範囲内で一致するという位置関係を満たしているか否かを判定する。例えば、図１９に例示した二つの暫定部分道路領域の場合には、道路幅も中心線位置もほぼ一致しているので、上記位置関係が満たされている。このように、複数の暫定部分道路領域が上記位置関係を満たしている場合には、図１７に戻り、ステップＳ５１１において、上記暫定部分道路領域を最終的に部分道路領域として決定する。すなわち、図２０に示された部分道路領域データ２６内のそれらの暫定部分道路領域に対する確定フラグ２６４の値を１に設定する。
【００７９】
図２１は、選択道路ベクトルＲ11に対して検出された他の暫定部分道路領域の例を示す図である。図では、暫定部分道路領域として、二つの４辺形Ｊ21Ｇ２Ｊ92Ｊ91とＧ３Ｊ41Ｊ132Ｊ131が決定されている。図の場合には、これら二つの暫定部分道路領域の道路幅と中心線の位置が一致していない。このような場合には、図１７に戻り、ステップＳ５１２において、暫定部分道路領域を再決定し、最終的な部分道路領域を決定する。
【００８０】
例えば、図２１に示された左側の４辺形Ｊ21Ｇ２Ｊ92Ｊ91の左側に別の図示しない４辺形が暫定部分道路領域として更に検出されていて、上記左側の４辺形Ｊ21Ｇ２Ｊ92Ｊ91と当該別の図示しない４辺形が上記位置関係を満たすときには、図に示された右側の４辺形Ｇ３Ｊ41Ｊ132Ｊ131の代わりの暫定部分道路領域が検出される。例えば、図１７のステップＳ５０８で暫定部分道路領域を決定するときに比較対象とされた他の複数の部分道路領域候補のうち、最終評価値が所定の上限値以下の評価値を持ち、図２１の左側の４辺形Ｊ21Ｇ２Ｊ92Ｊ91に対して上記位置関係を満たすものがないかを判定する。もしそのような部分道路領域候補があるときには、図２１の右側の４辺形に代えて当該部分道路領域候補を、暫定部分道路領域に決定したうえで、更に部分道路領域に決定する。しかし、そのような代わりの部分道路領域候補が存在しないときには、図２１の右側の４辺形をそのまま部分道路領域として決定する。
【００８１】
また、図２１に示された左側の４辺形Ｊ21Ｇ２Ｊ92Ｊ91の左側に上記別の図示しない４辺形が暫定部分道路領域として検出されていて、上記左側の４辺形Ｊ21Ｇ２Ｊ92Ｊ91と当該別の図示しない４辺形も上記位置関係を満たさないときには、図２１に図示されていない上記別の４辺形と、図示された左側の４辺形と、図示された右側の４辺形のそれぞれの代わり使用可能な部分道路領域候補であって、最終評価値が上記上限値以下であり、上記位置関係を満たすものがあるか否かを判定する。上記３つの４辺形のうちのいずれか一つ又は二つ又はその全てに対して代わりに使用可能な一つ又は複数の部分道路領域候補が見つかった場合には、その一つ又は複数の部分道路領域候補を、代わりの暫定部分道路領域に決定し、更に最終的な部分道路領域に決定する。
【００８２】
図１７に戻り、こうして、ステップＳ５１１又はＳ５１２により、選択道路ベクトル（例えばＲ11）に対する部分道路領域が決定されたことになる。その後ステップＳ５１３において、前記選択道路ベクトル以外に、未処理の他の道路ベクトルがあるか否かを判定し、当該他の未処理の道路ベクトルがあると判定されたときには、処理はステップＳ５０１に戻り、ステップＳ５０１以降の処理を当該他の道路ベクトルに関して実行する。その後ステップＳ５１３において、他の未処理の道路ベクトルがないと判定されたとき、部分道路領域決定部５００の処理が終了する。
【００８３】
図１に戻り、道路領域検出可能プログラム４０は道路領域決定部６００を実行する。道路領域決定部６００では、まず、いずれかの道路の全ての道路ベクトルの複数の区間に関して決定された複数の部分道路領域を用いて、部分道路領域が決定されていない区間に対する部分道路領域を決定する。決定には、例えば、隣接する区間に対して決定された複数の部分道路領域を接続する方法を採ることができる。例えば、図１９に示された二つの４辺形Ｊ21Ｇ２Ｊ112Ｊ111とＧ３Ｊ41Ｊ132Ｊ131との間を接続する部分道路領域を補間により決定する。このような接続する４辺形としては、例えば、左側の４辺形の頂点Ｇ２、Ｊ112と右側の４辺形の頂点Ｇ３Ｊ131を頂点とする４辺形を使用することができる。図１９の点線は、このような接続用の４辺形の二つの辺を示している。あるいは図２１に示された二つの４辺形Ｊ21Ｇ２Ｊ92Ｊ91とＧ２Ｊ41Ｊ132Ｊ131が、部分道路領域として決定された場合も、同様に、例えばそれらの二つの４辺形を結ぶ４辺形Ｇ２Ｇ３Ｊ131Ｊ92を接続する４辺形として使用することができる。図２１の点線は、このような接続用の４辺形の二つの辺を示している。このようにしてそれぞれ道路を構成する複数の道路ベクトルの全てに対して、連続した領域を表すのに必要な数の部分道路領域が決定され、それらの部分道路領域により連続した一つの道路領域が決定される。
【００８４】
道路領域決定部６００は、その後、それぞれ異なる道路に属するが、互いに接続されるべき複数の道路ベクトルあるいは互いに交叉する複数の道路ベクトルに対して決定された道路領域を接続する処理を行う。
図２２は、二つの隣接した道路ベクトルＲ11とＲ12に対して決定された二つの道路領域の接続を説明するための図である。図において、左側の４辺形Ｊ13Ｇ41Ｊ132Ｆ11は、道路ベクトルＲ11に対して決定された道路領域の例であり、右側の４辺形Ｆ14Ｇ14Ｊ151Ｆ15は、道路ベクトルＲ12に対して決定された道路領域の例であるとする。道路領域決定部６００では、これらの二つの道路領域を接続するために、二つの領域の一方の上辺を延長して二つの領域の他方の上辺と接続させる。上記二つの領域のいずれかの下辺を延長して他方の領域の下辺と接続させる。いずれの領域の上辺を延長するかは、二つの領域の上辺の位置関係に依存する。二つの領域の上辺が道路領域として望ましい形になるように一方の領域の上辺が延長される。もちろん、両方の領域の上辺を延長させることが望ましい場合には、そのように行う。あるいは、一方の領域の上辺を延長とは反対の方向に後退させることが望ましい場合には、そのように行う。下辺についても同様である。図の例では、左側の４辺形Ｊ13Ｇ41Ｊ132Ｆ11の上側の辺Ｆ11Ｊ132を右方向に延長して点Ｃａで右側の４辺形の上辺に接続させる。同様に、右側の４辺形Ｆ14Ｇ14Ｊ151ＧＦ15の下側の辺Ｆ14Ｇ14を左方向に延長して点Ｃｂで左側の４辺形の下辺に接続させる。こうして、二つの道路ベクトルＲ11とＲ12に対する道路領域として、上側の一組の折れ線Ｆ11ＣａとＣａＪ151と、下側の一組の折れ線Ｊ13ＣｂとＣｂＧ14とを境界線とする連続した道路領域が決定される。
【００８５】
図２３は、交叉する道路ベクトルＲ11とＲ３に対して決定された２つの道路領域の接続を説明するための図である。図において、折れ線Ｊ13ＣｂＧ14とＦ11ＣａＪ151は、道路ベクトルＲ11とＲ12に対して決定された、図２２に既に示した道路領域を規定する境界線である。一方、直線Ｊ161Ｇ16と直線Ｆ17Ｊ171は、道路ベクトルＲ３に対して決定された一組の境界線とする。道路ベクトルＲ11とＲ３とが交叉するところでは、図に示すように４つの境界線の間の４つの交点Ｃｃ、Ｃｄ、Ｃｅ、Ｃｆが決定され、これらの点が交差点の存在領域を示し、この交差点領域内では道路の境界線が存在しないように、道路ベクトルＲ11とＲ３に対する境界線が修正される。
【００８６】
道路領域決定部６００は、以上のようにして各道路ベクトルに対して道路領域を決定した後、各道路ベクトルに対する道路幅と車線数を判別する。車線数は、当該道路ベクトルに対して決定された道路領域の道路幅と、既に図１８に関連して説明した標準的な道路幅との比で推定することができる。道路幅又は車線数の一方が場所により異なるときには、道路幅又は車線数の一方が異なる場所毎に、道路領域を区分し、それぞれの区分された道路領域毎に道路幅と車線数を決定する。
【００８７】
道路領域決定部６００は、決定された道路領域とその領域に関する道路幅と車線数等のデータを当該道路ベクトルに対応して道路領域データ２７内に記憶する。図２４は、道路領域データ２７の例を示す図である。道路領域データ２７は道路ベクトル識別情報２７１と、道路存在領域を示す一対の境界線を構成する点列の位置を示す境界線情報２７２と、道路幅２７３、車線数２７４、備考情報２７５とを含んでいる。図２２の場合、道路ベクトルＲ11に対しては、道路ベクトル識別情報２７１には、例えばその記号Ｒ11が記憶され、境界線情報２７２には、図２３の場合には、下側の境界線上の点列Ｊ13−Ｃｄ，Ｃｅ−Ｃｂ−Ｇ14と、上記点列に対応する、上側の境界線上の点列Ｆ11−Ｃｃ，Ｃｆ−Ｃａ−Ｊ151とが記憶される。道路幅２７３には、決定された道路領域の同じ道路幅の領域に対応して道路幅が記憶される。車線数２７４に関しても同じである。備考情報２７５には、例えば廃止と判断された道路ベクトルに対して廃止を示す情報が記憶される。
以上のような処理を全ての道路に対して実行することにより、地理画像２１と道路ベクトルデータ２２とから、地理画像２１内に含まれた道路の存在領域を比較的簡単に決定できることが分かる。
なお、本発明は、以上の実施の形態に限定されるものではなく、本発明の要旨を変更しない範囲で、修正あるいは変更をしてもよいことは言うまでもない。
【図面の簡単な説明】
【００８８】
【図１】本発明に係る、道路領域検出可能装置の一つの実施形態の概略ブロック図である。
【図２】エッジ検出部の処理の概略フローチャートである。
【図３】地表を撮影して得られる画像の一例を示す図である。
【図４】道路ベクトルデータを説明するための図である。
【図５】図３の画像から得られたエッジ画像の例を示す図である。
【図６】部分道路境界直線候補検出部の処理の概略フローチャートである。
【図７】エッジ画像を分割して得られる複数のメッシュとそれらのメッシュに対して抽出された複数の部分道路境界直線候補を模式的に示す図である。
【図８】部分道路境界直線候補データの例を示す図である。
【図９】部分道路領域候補検出部の処理の概略フローチャートである。
【図１０】道路ベクトルに対して検出される部分道路領域候補の例を示す図である。
【図１１】部分道路領域候補データの例を示す図である。
【図１２】道路ベクトルに対して検出される他の部分道路領域候補の例を示す図である。
【図１３】道路ベクトルに対して検出される更に他の部分道路領域候補の例を示す図である。
【図１４】道路ベクトルに対して検出される更に他の部分道路領域候補の例を示す図である。
【図１５】道路ベクトルに対して検出される更に他の部分道路領域候補の例を示す図である。
【図１６】道路ベクトルに対して検出される更に他の部分道路領域候補の例を示す図である。
【図１７】部分道路領域決定部の処理の概略フローチャートである。
【図１８】道路幅と第２の評価値との関係の例を示す図である。
【図１９】部分道路領域決定部により決定される暫定部分道路領域の例を示す図である。
【図２０】部分道路領域データの例を示す図である。
【図２１】選択道路ベクトルに対して検出された他の暫定部分道路領域の例を示す図である。
【図２２】二つの隣接した道路ベクトルに対して決定された２つの道路領域の接続を説明するための図である。
【図２３】交叉する道路ベクトルに対して決定された２つの道路領域の接続を説明するための図である。
【図２４】道路領域データの例を示す図である。
【符号の説明】
【００８９】
Ｅ０からＥ１３…直線状エッジ部分、Ｍ０〜Ｍ８…メッシュ、Ｒ１、Ｒ２、Ｒ３…道路、Ｒ11、Ｒ12…道路ベクトル。
【技術分野】
【０００１】
本発明は、人工衛星あるいは航空機から地表を撮影して得られる地理画像を表す地理画像データから当該地表に含まれる複数の道路の存在領域を、上記地表に存在する道路に関する道路ベクトルデータを併用して検出する、道路領域決定可能プログラム及び道路領域決定方法に関する。
【背景技術】
【０００２】
地表上の道路を表す道路地図を、人工衛星あるいは航空機から地表を撮影して得られる画像から自動的に作成することができれば、当該地図を人力で作成する場合に比べて必要な労力が大幅に減り、更に、道路がその後変化した場合も、その変化を地図に迅速に反映することが可能になる。本明細書では、上記画像を地理画像と呼ぶ場合がある。このような利点を考慮して、上記地理画像から地表の地図を作成する研究が盛んに行われている。非特許文献１、２、３には、過去のいくつかの研究の概要が紹介されている。非特許文献３には、更に、ダイナミックプログラミングを用いて道路を表すエッジの追跡を行う独自の研究成果も紹介されている。
【０００３】
非特許文献１と２によれば、地理画像の解像度が低い（例えば、画素当たり２ｍ以上である）ときには、道路は一本の線として検出されるが、地理画像の解像度が高いときには、道路は平行な境界線を有する幅のある画像として検出される。したがって、両方の画像に対しては異なる技術が必要であることが記載されている。非特許文献１によれば、解像度が高い、住宅地の航空写真から直線部分を検出し、平行な線分をグループ化することにより、家や道路を抽出する研究もなされている。
【０００４】
非特許文献２によれば、衛星画像から道路を抽出するための処理は、大きくは、前処理、エッジ検出、道路追跡、グルーピングからなる。なお、高解像度の衛星画像を使用する場合には、前処理として上記エッジ検出を行う研究も紹介されている。高解像度の地理画像を使用する研究に関しては、道路追跡で平行なエッジの間の複数の直線を出発点として使用する研究として、非特許文献４から６を紹介している。
【０００５】
非特許文献１から３によれば、地理画像からの道路の検出をより正確にするために、いろいろな補助情報を利用する研究もなされている。補助情報としては、例えば地理的データベースを利用している例がある。非特許文献２は、そのような研究の例として非特許文献７を紹介している。
【０００６】
非特許文献２によれば、非特許文献４から６では、前処理として直線とエッジを検出した後、道路追跡段階では、平行なエッジの間の複数の直線を追跡の初期値として使用し、その後の道路追跡の実行は発見的手法により行っている。また、非特許文献２によれば、検出された道路要素をグルーピングする処理では、非特許文献４はリボン蛇(Ribbon Snakes)を使用し、非特許文献５と６では、コンテキストスケッチとして、道路と他の物体との関係を使用して道路要素として二つの平行な道路境界線を有する４辺形を決定し、決定されたそれらの４辺形を接続している。
【０００７】
非特許文献２によれば、非特許文献７では、エッジ検出には、シルクハット変換(top hat transformation)を用い、道路追跡の初期値の決定に地理的データベースを使用し、道路以外のものを表す直線と道路を表す直線とを区別している。その後、道路追跡処理では、パターンマッチングと、相関と領域それぞれの一様性を利用している。
【非特許文献１】高木幹雄、下田陽久監修、「画像解析ハンドブック」、財団法人東京大学出版会、１９９１年１月１７日、ｐ．１７３−１７８
【非特許文献２】Demin Xiong,"White papers: Automated Road Network Extraction from High Resolution Images," [on line]、２００２年１１月、National Consortium on Remote Sensing in Transportation, University of New Mexico, [平成１６年６月５日検索]、インターネット、＜ＵＲＬ：riker.unm.edu/DASH_new/pdf/White%20Papers/ Automated%20Road%20Network%20Extraction.pdf＞
【非特許文献３】MF Auclair Fortier, D. Ziou, C. Armenakis and S. Wang,"Survey of Work on Road Extraction in Aerial and Satellite Images," [on line], Technical Report N 247, Departement de mathematiques et informatique, Universite de Sherbrooke, Canada, [平成１６年６月５日検索]、インターネット、＜ＵＲＬ：http://www-l2ti.univ-paris13.fr/~auclair/ Publi/Auclair-TR247.pdf＞
【非特許文献４】H. Mayer, I. Laptev, A. Baumgartner, and C. Steger,"Automatic Road Extraction Based on Multi-Scale Modeling, Context, and Snakes," International Archives of Photogrammetry and Remote Sensing, volume XXXII, Part3-2W3, pages 106-113, 9-11 September 1997
【非特許文献５】A. Baumgartner, C. T. Steger, H. Mayer, and W. Eckstein," Semantic Objects and context for Finding Roads," Integrating photogrametric Techniques with Scene Analysis and Machine Vision III, Proc. SPIE 3072, pages 98-109, April 1997
【非特許文献６】A. Baumgartner, C. T. Steger, H. Mayer, and W. Eckstein,"Multi-Resolution, Semantic Objects and Context for Road Extraction," Semantic Modeling for the Acquition of Topographic Information from Images and Maps, pages 140-156, Basel Switzerland, 1997, Birkhauser Verlag
【非特許文献７】G. Bordes, G. Giraudon, and O. Jamet,"Road Modeling Based on a Cartogrphic Database for Aerial Image Interpretation," Semantic Modeling for the Acquition of Topographic Information from Images and Maps, pages 123-139, Basel Switzerland, 1997, Birkhauser Verlag
【発明の開示】
【発明が解決しようとする課題】
【０００８】
高解像度の地理画像から道路として幅のある領域（道路領域）を検出する研究は既になされている。非特許文献４から６では、道路の追跡処理には発見的方法が使用されている。非特許文献７では、道路の追跡処理にはパターンマッチングが主に使用されている。非特許文献７では、地理的データベースを使用しているが、道路探索の初期値の決定においてである。ここに列挙した非特許文献４から７では、道路を構成する複数の部分道路の検出のためのデータ処理量が多く、道路の検出に時間が掛かる。道路検出の高速化のためには、より簡単に部分道路を検出できることが望ましい。
【０００９】
したがって、本発明の目的は、地理画像から道路を構成する複数の部分道路の存在領域をより簡単に検出可能にする道路領域決定可能プログラム及び道路領域決定方法を提供することである。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、本発明は、地理画像から道路を構成する複数の部分道路の検出時に地理的データを使用する。地理的データとして、道路の中心線を近似的に直線で表す複数の道路ベクトルのそれぞれの始点と終点の位置情報を含む道路ベクトルデータという簡単な地理的なデータを使用する。より具体的には、請求項１に記載の本発明に係る道路領域決定可能プログラムは、エッジ検出手段と、領域分割手段と、部分道路境界直線候補検出手段と、部分道路領域候補検出手段と、部分道路領域決定手段と、道路領域決定手段、としてコンピュータを機能させるものである。
ここで、前記エッジ検出手段は、地表を上空から撮影して得られ、あらかじめ地理画像記憶手段に記憶された地理画像から複数のエッジを検出して当該複数のエッジを表すエッジ画像を生成する。前記領域分割手段は、前記地理画像の存在領域を複数のメッシュに分割するものである。
前記部分道路境界直線候補検出手段は、いずれかの道路が通過する複数のメッシュの各々に関して、当該道路の当該メッシュ内に位置する部分道路に対して所定の位置条件を満たす、当該メッシュ内に位置する複数の直線状のエッジ部分を、当該部分道路に対する複数の部分道路境界直線候補として、前記エッジ画像から、かつ、前記道路の中心線を近似的に直線で表す連結された複数の道路ベクトルを指定する、あらかじめ道路ベクトルデータ記憶手段に記憶された道路ベクトルデータに基づいて検出するものである。
前記部分道路領域候補検出手段は、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路境界直線候補検出手段により検出された前記複数の部分道路境界直線候補から選択された任意の二つからなる複数の組合わせにより定まる複数の領域を、当該道路の当該メッシュ内に位置する前記部分道路の存在領域に対する複数の部分道路領域候補として検出するものである。
前記部分道路領域決定手段は、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路境界直線候補検出手段により検出された前記複数の部分道路領域候補の各々について、当該部分道路領域候補が当該メッシュ内の前記部分道路の存在領域である妥当性を所定の評価基準に基づいて評価し、前記複数の部分道路領域候補に対する評価結果に基づいて前記複数の部分道路領域候補の一つを当該部分道路の当該メッシュ内の存在領域として決定するものである。
前記道路領域決定手段は、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路領域決定手段で決定された複数の部分道路領域を接続して当該道路の存在領域を決定するものである。
【００１１】
これにより、地理画像を分割して得られる複数のメッシュの各々毎に、そこを通過する道路がある場合に、その道路のうち当該メッシュ内に位置する部分道路の存在領域を、そのメッシュ内に位置する直線状エッジ部分から、上記道路ベクトルデータに基づいて決定することができ、道路の異なる部分道路の存在領域を比較的簡単に決定することができる。しかも、各メッシュを通過する道路部分に対する複数の部分道路領域候補を、他のメッシュ内の部分道路領域候補とは独立に決定するので、部分道路領域候補の決定処理が簡単に行える。更に、いずれかの道路が通過する複数のメッシュの各々毎に複数の部分道路領域候補を決定した後に、当該道路のうち当該複数のメッシュ内に位置する複数の道路部分に対する複数の部分道路領域を、それぞれのメッシュに対して検出された複数の部分道路領域候補から決定するので、複数の部分道路領域の決定が比較的容易になる。複数の部分道路領域を決定した後で、道路全体に対する道路領域をそれらの部分道路領域から決定するので、道路全体に対する道路領域の決定も比較的容易となる。
【００１２】
請求項２に記載の道路領域決定可能プログラムは、請求項１において、前記部分道路境界直線候補検出手段が前記いずれかの道路が通過する前記複数のメッシュの各々に対する前記複数の部分道路境界直線候補が満たすべき前記所定の位置条件は、部分道路境界直線候補は、当該部分道路の近傍にあり、かつ、当該部分道路に対してほぼ平行に位置することである。これにより、各メッシュを通過する道路のうち当該メッシュ内に位置する部分道路に対する部分道路境界直線候補を、直線状のエッジ部分を使用して決定することができ、メッシュ内に位置する部分道路に対する部分道路境界直線候補を非常に簡単に決定することができる。
【００１３】
請求項３に記載の道路領域決定可能プログラムは、請求項１又は２において、前期部分道路領域決定手段は、前記いずれかの道路が通過する前記複数のメッシュのそれぞれに対して検出された前記複数の部分道路領域候補の各々について、部分道路領域である妥当性を、それぞれの部分道路領域候補ごとに個別に所定の第１の評価基準に基づいて評価し、前記複数の部分道路領域候補に対する評価結果に基づいて、前記複数の部分道路領域候補の一つを、当該メッシュ内の当該道路の前記部分道路に対する暫定部分道路領域を決定する暫定部分道路領域決定手段と、前記いずれかの道路が通過する前記複数のメッシュの各々に対して決定された前記複数の暫定部分道路領域のそれぞれについて、前記複数の暫定部分道路領域の相互の位置関係に関係する第２の評価基準に基づいて、部分道路領域としての妥当性を評価し、前記複数の暫定部分道路領域に対する評価結果に基づいて、前記複数の暫定部分道路領域の各々について、当該暫定部分道路領域を当該暫定部分道路領域が属するメッシュに対して使用すべき部分道路領域として決定するか又は当該暫定部分道路領域の代わりに当該メッシュに対して使用すべき他の部分道路領域を決定する道路領域決定手段と、を備えるものである。
【００１４】
これにより、メッシュ毎にそのメッシュを通過する道路の当該メッシュ内部分に対する暫定部分道路領域を決定した後、複数のメッシュに対して決定された複数の暫定部分道路領域の位置関係に基づいて、各暫定部分道路領域を、そのまま当該暫定部分道路領域が属するメッシュに対して使用すべき部分道路領域として決定するか又は当該暫定部分道路領域の代わりに当該メッシュに対して使用すべき他の部分道路領域を決定するので、道路に対する道路領域の決定が、当該道路が通過する複数のメッシュの各々に対する複数の部分道路領域候補の検出、各メッシュに対する暫定部分道路領域の決定、複数のメッシュを通過する道路全体に対する道路領域の決定というように、段階的に進めることができるので、最終的な道路領域の決定が容易となる。
【００１５】
請求項４に記載の道路領域決定可能プログラムは、請求項３において、前記第１の評価基準は、各部分道路領域候補に属する、前記地理画像内の画素の画像値に依存する評価基準と、各部分道路領域候補の幾何学的な特徴量に依存する評価基準との両方を含むものである。これにより、各メッシュに対して検出された複数の部分道路領域候補からの暫定部分道路領域の決定が、適切に行いやすくなる。
【発明の効果】
【００１６】
本発明によれば、地理画像から道路を構成する複数の部分道路の存在領域をより簡単に検出可能になる。
【発明を実施するための最良の形態】
【００１７】
以下、本発明に係る道路領域検出可能プログラム及び道路領域検出方法の実施の形態を図面を参照して詳細に説明する。
図１は、本発明に係る、道路領域検出可能装置の一つの実施形態の概略ブロック図である。符号１は、上記装置の一つの実施の形態の全体を指す。本装置１は、処理装置１０と、記憶装置２０と、入出力装置３０とを備えている。処理装置１０は、例えばパソコン又はワークステーションにより実現される。記憶装置２０は、メインメモリとして使用されるＲＡＭ（ランダムアクセスメモリ）（図示せず）及び磁気ディスク記憶装置のような補助記憶装置（図示せず）とを含む。入出力装置３０は、キーボード及びマウス等のポインティングデバイスを含む入力装置３１と、ＣＲＴディスプレイ装置等の表示装置３２又はプリンタ３３などの出力装置を備えている。入力装置３１はパラメータの入力やコマンドの起動などに使われる。表示装置３２又はプリンタ３３は、地理画像又は検出された道路領域を示す画像などの表示又は印刷に使われる。なお、記憶装置２０内にデータが記憶されるときに、当該データが図示しないＲＡＭと図示しない補助記憶装置のいずれに記憶されるかは、あらかじめ当該データに対して決められている。
【００１８】
道路領域検出可能プログラムは、記憶装置２０に記憶され処理装置１０に組み込まれて実行されるが、図では分かりやすさのために、道路領域検出可能プログラム４０とそれを構成する複数のモジュールを、処理装置１０を示すブロックの内部に記載している。道路領域検出可能プログラム４０は、エッジ検出部１００と、領域分割部２００と、部分道路境界直線候補検出部３００と、部分道路領域候補検出部４００と、部分道路領域決定部５００と、道路領域決定部６００というモジュールを含む。
【００１９】
処理装置１０は、道路領域検出可能プログラム４０内のそれぞれのモジュールが実行されたときに、エッジを検出する機能ブロックと、地理画像の存在領域を分割する機能ブロックと、部分道路の境界直線候補を検出する機能ブロックと、部分道路の存在領域の候補を検出する機能ブロックと、部分道路の存在領域を決定する機能ブロックと、道路が存在する領域を決定する機能ブロックという複数の機能ブロックとしてコンピュータを動作させる。したがって、処理装置１０と道路領域検出可能プログラム４０のこれらのモジュールにより、それぞれのモジュールに対応する複数の機能ブロックが実現されることになる。したがって、処理装置１０と、記憶装置２０と、入出力装置３０と、エッジ検出部１００、領域分割部２００、部分道路境界直線候補検出部３００と、部分道路領域候補検出部４００と、部分道路領域決定部５００と、道路領域決定部６００は、本発明に係る。道路領域検出可能装置の一つの実施の形態を実現することになる。
【００２０】
道路領域検出可能プログラム４０は、本発明に係る道路領域検出可能プログラムの一つの実施の形態を実現するものであり、記録媒体に記録してあるいはネットワークを介して記憶装置２０に記憶され、処理装置１０で実行される。道路領域検出可能プログラム４０は、記録媒体に記録されて又はネットワークを介して販売可能である。処理装置１０が道路領域検出可能プログラム４０を実行して道路の存在領域を検出する手順は、本発明に係る道路領域検出方法の一つの実施の形態を実現する。
【００２１】
記憶装置２０には、人工衛星あるいは航空機から地表を撮影して得られる地理画像を表す地理画像データ２１と、道路ベクトルデータ２２とがあらかじめ記憶される。道路ベクトルデータ２２は、当該地表に存在する複数の道路の各々に関して、当該道路の中心線を近似的に直線で表す連結された複数の折れ線部分のそれぞれに対する始点と終点の位置情報を含むデータである。上記道路のうち、一つの折れ線状部分を道路ベクトルと呼ぶことがある。一つの道路は一つの道路ベクトルからなる場合もあり、連結された複数の道路ベクトルからなる場合もある。したがって、道路ベクトルデータは、一つの道路を一つ又は複数の道路ベクトルで表していると言うこともできる。
【００２２】
地理画像データ２１と道路ベクトルデータ２２を処理して、エッジ画像データ２３、部分道路境界直線候補データ２４、部分道路領域候補データ２５、部分道路領域データ２６、道路領域データ２７が生成され、記憶装置２０に格納される。以下では断らない限り、本実施の形態では、地理画像データ２１は、カラーの多値画像のデータであると仮定するが、本発明は、地理画像データ２１が白黒濃淡画像である場合にも適用可能である。以下では、地理画像データ２１のことを簡単化のために単に地理画像２１と呼ぶことがある。他の画像データについても同様である。また、画像データが生成又は処理されること又は記憶装置２０に記憶されることに言及するときに、簡単化のために画像データのデータという単語には言及しないで、単に画像が生成又は処理されるあるいは画像が記憶装置２０に記憶されるということがある。
【００２３】
図１に戻り、道路領域検出可能プログラム４０は、まず、エッジ検出部１００を実行する。
図２は、エッジ検出部１００の処理の概略フローチャートである。エッジ検出部１００は、地理画像内の道路を抽出する前段階として、地理画像２１内の道路の境界線や、建築物の輪郭を示すエッジ画像を検出する。本実施の形態では、後に説明するように、エッジ検出部１００によって検出されたエッジ画像に基づいて道路境界線位置を推測するので、検出されるエッジの量は適当であることが要求される。エッジが少なすぎると道路境界線を再現しにくくなり、多すぎるとノイズ分が多くなって道路境界線の決定が困難になるためである。
【００２４】
地理画像２１は、ここではＲＧＢ３原色を含むカラー画像とする。エッジ検出の前に、ステップＳ１０１において、地理画像２１の各画素のＲＧＢデータに対してＨＳＩ変換を施して、色相Ｈ、彩度Ｓ、明度Ｉの組に変換して、明度Ｉの画像を示す明度画像を生成する。この変換自体は周知である。つぎに、ステップＳ１０２において、生成された明度画像に対してヒストグラム均等化処理を行う。ヒストグラム均等化とは、画像全体又は適当な区画ごとに明度の分布を調べ、その平均値が中間値になるように、明度を一次変換して明度の分布範囲を拡大するフィルタ処理であり、それにより、全体的に明度の分布範囲が狭い画像からもエッジが検出できるようになる。
【００２５】
つぎに、ステップＳ１０３において、ヒストグラム均等化処理後の明度画像に対して、エッジ検出を実行する。この処理によって、上記明度画像内の道路や建築物の輪郭等、明度の変化が大きい部分をエッジとして抽出し、検出されたエッジを表すエッジ画像を生成する。エッジ検出方法としては、キャニー法や、ソーベルフィルタを用いたフィルタ処理などが使用できる。キャニー法に関しては、例えば、J. Canny,“A Computational Approach to Edge Detection,”IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986, vol. PAMI-8, No. 6, pp. 679〜698参照。ソーベルフィルタに関しては、例えば、尾上守夫他編集、「画像処理ハンドブック」、株式会社昭晃堂、昭和６２年６月８日、ｐ．２８０−２８１参照。
【００２６】
つぎに、ステップＳ１０４において、エッジ画像に対して２値化処理を行う。エッジ画像に対する２値化は、各画素の明度値と閾値の大小関係を調べ、閾値より大きい画素の値は、例えば「１」に、小さい画素の値は例えば「０」に変換する一般的なフィルタ処理である。これにより、エッジ画像の各画素はエッジを表す画素と、そうでない画素に２分され、２値化されたエッジ画像が得られる。閾値はあらかじめ決定されているか、２値化前のエッジ画像又はその一部分の統計情報からそれ自体公知の方法により決定することができる。つぎにステップＳ１０５において、２値化後のエッジ画像に対して小エッジの除去処理を行う。小エッジの除去とは、２値化後のエッジ画像内のエッジの中で、周囲のエッジとつながっていない、ノイズと判断できる小さなエッジを除去することを指す。以上の一連の処理で得られたエッジ画像のデータを、エッジ画像データ２３として記憶装置２０に格納して、エッジ検出部１００の処理は終了する。
【００２７】
図３は、地理画像データ２１（図１）が示す地理画像の一例を示す図である。図にはいくつかの道路が含まれていることが分かる。
図４は、道路ベクトルデータ２２（図１）を説明するための図である。同図（ａ）は、図３の地理画像２１に対応する道路ベクトルデータ２２が表す道路を図示したものである。図において、道路Ｒ１は、二つの折れ線部分（道路ベクトル）Ｒ11とＲ12を含む道路であり、道路Ｒ２については、図では一つの道路ベクトルのみが示されている。図において、黒丸は、道路の通過点を示し、道路Ｒ１の通過点として点Ｐ０、Ｐ１、Ｐ２が示され、道路Ｒ２の通過点として点Ｐ３、Ｐ４が示されている。道路Ｒ１、Ｒ２等は、図３に示された地理画像の道路の中心線の位置を表すものとして別にあらかじめ決定されたものであり、図４（ａ）において、道路Ｒ１等の位置には誤差が存在するのが普通であり、道路の中心線を正確に表すものではない。なお、本明細書では、一つの道路Ｒ１に含まれた複数の道路ベクトルの一つ、例えばＲ11を道路と呼ぶ場合もある。逆に、一つの道路ベクトルからなる道路を道路ベクトルと呼ぶこともある。
【００２８】
図４（ｂ）は、同図（ａ）に対する道路ベクトルデータ２２の例を示す図である。道路ベクトルデータ２２は、道路を構成する複数の道路ベクトルに割り当てられた道路ベクトルの識別情報２２１と、当該道路ベクトルの始点と終点に関する始点終点位置情報２２２とを含む。図では、道路Ｒ１の道路ベクトルＲ11に対する道路ベクトル識別情報２２１として記号Ｒ11が示され、始点終点位置情報２２２として点Ｐ０、Ｐ１の組が示されている。同様に、道路Ｒ１の道路ベクトルＲ12に対する道路ベクトル識別情報２２１として記号Ｒ12が示され、始点終点位置情報２２２として点Ｐ１、Ｐ２の組が示されている。道路Ｒ１には道路ベクトルＲ11、Ｒ12以外の他の道路ベクトルが含まれている場合には、それらの道路ベクトルに関するデータも道路ベクトルデータ２２に含まれる。以上のデータが道路Ｒ１に関する道路ベクトルデータである。
【００２９】
同様に、道路ベクトルデータ２２には、道路Ｒ２に関して、道路ベクトル識別情報２２１として記号Ｒ２が示され、始点終点位置情報２２２として点Ｐ３、Ｐ４の組が示されている。このように、道路ベクトルデータ２２には、複数の道路に関するデータを含むが、本明細書では、道路ベクトルデータ２２のうち、複数の道路ベクトルで構成される一つの道路、例えばＲ１に関するデータを道路ベクトルデータと呼ぶこともある。また、道路ベクトルデータ２２内の、一つの道路ベクトルに関するデータである、道路ベクトル識別情報２２１と始点終点位置情報２２２との組を道路ベクトルデータと呼ぶこともある。
【００３０】
図５は、図３に示す地理画像２１から得られたエッジ画像２３の例を示す図である。エッジ画像２３には、道路の境界線以外にも建物の輪郭線も含まれている。更に、道路の境界線もジグザグしたものであり、鮮明な直線あるいは滑らかな曲線にはなっていない部分も多い。
【００３１】
図１に戻り、道路領域検出可能プログラム４０は、領域分割部２００を実行する。領域分割部２００は、地理画像２１及びエッジ画像２３の各々が属する領域を、同じサイズを有する複数のメッシュに分割し、各メッシュの頂点位置を決定するものである。領域分割は、領域分割部２００の後に実行される部分道路境界直線候補検出部３００と、部分道路領域候補検出部４００と、部分道路領域決定部５００をメッシュ毎に行うことにより、部分道路の境界線の検出を容易にし、処理の速度と精度の向上を高めるために行われる。メッシュのサイズは、以下に述べるように、メッシュ内では、検出すべき道路が実質的に直線であり、その部分道路に対する境界線が直線であると見なすことができるという条件を少なくとも満たすように、更に、後述の処理が実行できるように、適度な値に定める。
【００３２】
道路領域検出可能プログラム４０は、領域分割部２００の実行後に、部分道路境界直線候補検出部３００を実行する。図６は、部分道路境界直線候補検出部３００の処理の概略フローチャートである。部分道路境界直線候補検出部３００は、各メッシュについて、当該メッシュを通過する道路ベクトルがある場合に、その道路の、当該メッシュ内にある部分（以下、部分道路と呼ぶことがある）の境界直線を表している可能性がある複数の直線状エッジ部分を、その部分道路の境界直線の候補としてエッジ画像２３から検出する。
【００３３】
まず、ステップＳ３０１において、前記複数のメッシュから、以下の処理を実行していない未処理のメッシュを一つ選ぶ。そのメッシュを選択メッシュと呼ぶ。ステップＳ３０２において、道路ベクトルデータ２２により示される道路ベクトルのうち、選択メッシュを通っている道路ベクトルがあるか否かを判定し、そのような道路ベクトルがある場合に、そのような道路ベクトルの全てについて当該選択メッシュ内にある部分道路を検出して、その部分道路の両端の位置の組をリストＬ１に登録する。その選択メッシュを通過する道路ベクトルが複数ある場合には、それぞれの道路ベクトルのその選択メッシュ内の部分道路をリストＬ１に登録する。
【００３４】
つぎにステップＳ３０３で、リストＬ１が空であるか否かが判定され、空の場合は、当該選択メッシュを道路ベクトルが通過していないときであるので、その選択メッシュについては以下の処理を行わず、ステップＳ３０１に戻り、次のメッシュを選択する。ステップＳ３０３での判定の結果、選択メッシュが空でないと判定された場合、ステップＳ３０４において、選択メッシュ内に位置する直線状エッジ部分を全てエッジ画像データ２３から検出する。得られた直線状エッジ部分の始点と終点の組をリストＬ２に格納する。
【００３５】
直線状エッジ部分の検出では、選択メッシュに含まれているエッジの中から、既に一つの直線としてつながっているエッジ部分を検出するだけでなく、複数のエッジ部分に分離されているが、つなげれば直線を形成する位置にある複数のエッジ部分の組を見つけ出し、それらの複数のエッジ部分の組を連結して一つの直線状エッジ部分に変換することも行う。なぜなら、部分道路の境界直線は、建物の影により、あるいは交差点の存在等により、複数の部分に分断された複数の直線状エッジ部分として検出される可能性があるからである。
【００３６】
上記直線状エッジ部分の検出法としては、例えばハフ（Hough）変換が挙げられる。例えば、“Method and Means for recognizing complex patterns"，米国特許第3,069,654号，1962参照。ハフ変換では、複数部分に切断された直線も一つの直線に復元することができる。したがって、上記のような、同じ道路の境界直線を構成するべきエッジが複数の直線状エッジ部分に分断されている場合でも、それらのエッジ部分を検出して一つの直線状エッジ部分として検出することに適している。直線状エッジ部分の検出処理は、検出対象範囲が大きいと処理時間が掛かるが、本実施の形態では、エッジ画像を複数のメッシュに分割して、メッシュ毎に直線状エッジ部分を検出するので、この問題は緩和される。逆に、各メッシュのサイズは、先に述べた条件の他に、直線状エッジ部分の検出のための時間が適度に小さい値となるという条件を満たすように定めてもよい。
【００３７】
つぎにステップＳ３０５において、得られたリストＬ２から未チェックの直線状エッジ部分を１つ選択し、ステップＳ３０６において、その直線状エッジ部分が、リストＬ１に含まれるいずれかの部分道路に対する境界直線になるための条件を満たすか否かを判定する。この判定では、選択された直線状エッジ部分がリストＬ１内のいずれかの部分道路に対して所定の位置条件を満たすか否かが判定される。この判定では、選択された直線状エッジ部分がリストＬ１内のいずれかの部分道路に対して平行であるという第１の条件が満たされるか否かが判定され、その第１の条件が満たされた場合に、更に、選択された直線状エッジ部分がその部分道路から所定の距離以内にあるという第２の条件が満たされるか否かが判定される。このように、選択された直線状エッジ部分がいずれかの部分道路に対して部分道路領域境界直線候補となるための位置条件と、この位置条件を満たすか否かの判定は非常に簡単である。
【００３８】
本実施の形態では、道路ベクトルデータ２２に含まれた道路ベクトルの始点と終点の位置には誤差があると仮定しているので、リストＬ２から選択された直線状エッジ部分の位置とリストＬ１に登録されたいずれかの部分道路の位置が所定の許容位置ずれ範囲内で一致していなくても、当該直線状エッジ部分は、当該部分道路に対する境界直線である場合もあると考えている。
【００３９】
しかし、リストＬ２から選択された直線状エッジ部分の方向は、リストＬ１に登録されたいずれかの部分道路の方向と所定の角度差の限界内で一致しないと、当該直線状エッジ部分は、当該部分道路の境界直線とはなり得ないと判断する。すなわち、道路ベクトルデータ２２で示す部分道路の位置には誤差があっても、道路ベクトルデータ２２が示す部分道路の方向には大きな誤差はないと仮定している。したがって、ステップＳ３０６での判定では、選択された直線状エッジ部分の方向と、道路ベクトルデータが示す部分道路の方向は、所定の許容角度ずれ範囲内で一致しているかがまず判断される。この許容角度ずれ範囲は、例えば、２度あるいは５度程度とすることができる。このように比較的大きな許容角度ずれ範囲を使用するのは、実際の道路ベクトルの方向も、メッシュ内という限定された範囲内では、道路ベクトルデータ２２が示す道路ベクトルの方向からずれている可能性があるので、そのような大きな角度ずれ範囲を許容してもよいとの考えに基づく。
【００４０】
ステップＳ３０６での判定では、選択された直線状エッジ部分の方向と道路ベクトルデータ２２が示す部分道路の方向とが、所定の許容角度ずれ範囲内で平行であるときには、両者の間の距離が所定の制限距離以内であるか否かを次に判定し、両者がこの距離よりも大きく隔たっているときには、当該直線状エッジ部分は、メッシュ内の部分道路の境界直線とは見なさない。ここで、所定の制限距離とは、選択された直線状エッジ部分が、画像内に含まれる可能性のある道路が通常持ち得る道路幅の最大値程度に等しい距離を言う。選択された直線状エッジ部分が、道路が通常持ち得る道路幅の最大値程度の距離よりもかなり大きくずれているときには、当該直線状エッジ部分は、部分道路の境界直線とは見なさない。この判定は、当該直線状エッジ部分と、道路ベクトルデータ２２が示す部分道路の位置との一致を判定するものではない。なお、選択された直線状エッジ部分と道路ベクトルデータ２２が示す部分道路との間の距離には、両者の間の最も近い部分間の距離を使用すればよい。
【００４１】
ステップＳ３０６での判定において、選択された直線状エッジ部分が上記第１、第２の条件の両方を満すと判定されたときには、ステップＳ３０７において、選択された直線状エッジ部分は、リストＬ１内の、上記第１、第２の条件に関する判定対象とされたいずれかの部分道路に対する部分道路境界直線候補の一つと見なされ、当該部分道路と当該選択された直線状エッジ部分との組を部分道路境界直線候補データ２４の一部として、記憶装置２０に記憶し、その後ステップＳ３０８において、選択された直線状エッジ部分をリストＬ２から削除し、処理はステップＳ３０９に進む。
【００４２】
ステップＳ３０６での判定において、選択された直線状エッジ部分が上記第１、第２の条件の少なくとも一方を満さないと判定されたときには、処理はステップＳ３０８に進み、選択された直線状エッジ部分をリストＬ２から削除し、処理はステップＳ３０９に進む。ステップＳ３０９においては、リストＬ２内の全ての直線状エッジ部分のチェックが終了したか否かが判断され、終了していないときには、ステップＳ３０５以降の処理が繰り返される。ステップＳ３０９での判定の結果、選択メッシュに関して全ての直線状エッジ部分のチェックが終了したと判断されたときには、ステップＳ３１０において、全てのメッシュでの処理が終了しているか否かを判定し、終了していないときには、ステップＳ３０１以降の処理が未処理のメッシュに関して繰り返される。
【００４３】
図７は、エッジ画像２３を分割して得られる複数のメッシュとそれらのメッシュに対して抽出された複数の部分道路境界直線候補を模式的に示す図である。図においては、一点鎖線Ｒ11、Ｒ12、Ｒ３は、図４（ａ）に示されたように、それぞれ道路ベクトルデータ２２で示される複数の道路ベクトルの例を示す。道路ベクトルＲ11とＲ12は、いずれも道路Ｒ１（図４（ａ））に属する道路ベクトルである。道路ベクトルＲ11は始点Ｐ０と終点Ｐ１を有し、道路ベクトルＲ12は、道路ベクトルＲ11の終点Ｐ１を始点とし終点Ｐ２を有する。道路ベクトルＲ３は、道路ベクトルＲ１に交叉する道路ベクトルの例であり、始点Ｐ３と終点Ｐ４とを有する。図ではエッジ画像２３は３×３個のメッシュＭ０〜Ｍ８のみを含んでいるが、これは図の簡単化のためであり、エッジ画像データ２３に含まれる実際のメッシュ数はもっと多いのが普通である。道路ベクトルＲ11、Ｒ12、Ｒ３は、複数のメッシュを通過している。例えば、道路ベクトルＲ11は、メッシュＭ０内に位置する部分道路、メッシュＭ１内に位置する部分道路、メッシュＭ４内に位置する部分道路、メッシュＭ５内に位置する部分道路に区分されることが分かる。
【００４４】
図には、道路ベクトルＲ１に対して部分道路境界直線候補検出部３００（図６）のステップＳ３０４において検出される複数の直線状エッジ部分が模式的に示されている。メッシュＭ０に関しては、直線状エッジ部分Ｅ０、Ｅ１、Ｅ５が検出されている。メッシュＭ１に関しては、直線状エッジ部分Ｅ２、Ｅ６、Ｅ９、Ｅ11が検出されている。メッシュＭ２に関しては、直線状エッジ部分Ｅ12が検出されている。メッシュＭ４に関しては、直線状エッジ部分Ｅ３、Ｅ７が検出されている。メッシュＭ５に関しては、直線状エッジ部分Ｅ４、Ｅ８、Ｅ10、Ｅ13が検出されている。なお、図では、直線状エッジ部分Ｅ０、Ｅ１のように、他の直線状エッジ部分に接続されていないものもある。図の例では、直線状エッジ部分Ｅ２からＥ４、Ｅ５からＥ８、Ｅ９からＥ10、Ｅ11からＥ13はそれぞれ連結されているが、これらの直線状エッジ部分は、直線状エッジ部分Ｅ０、Ｅ１と同様に、他の直線状エッジ部分から分離されていてもよいことは言うまでもない。
【００４５】
メッシュＭ０に関して検出された直線状エッジ部分Ｅ０は、部分道路境界直線候補検出部３００（図６）のステップＳ３０６の判定では、道路ベクトルＲ11からの距離が大きいために、道路ベクトルＲ11のうちのメッシュＭ０に属する部分道路に対する部分道路境界直線候補とは判定されないと仮定する。図においては、直線状エッジ部分Ｅ１からＥ13は、いずれも、道路ベクトルＲ１のうちのそれぞれが属するメッシュ内の部分道路に対する部分道路境界直線候補であると判定されると仮定する。
【００４６】
図８は、部分道路境界直線候補データ２４の例を示す図である。部分道路境界直線候補データ２４には、道路ベクトル識別情報（以下、識別情報を単にＩＤと呼ぶことがある）２４１、メッシュ識別情報２４２、部分道路位置情報２４３、境界直線候補位置情報２４４とを含む。図では、道路ベクトル識別情報２４１には、簡単化のために、Ｒ11等の、道路ベクトルに付した記号を識別情報として示している。メッシュ識別情報２４２には、簡単化のために、Ｍ０等の、メッシュに付した記号を識別情報として示している。メッシュ識別情報２４２には、注目する道路ベクトルＲ11が通過するメッシュの識別情報が格納され、その道路ベクトルが通過しないメッシュの識別情報は格納されない。部分道路位置情報２４３には、メッシュ内の部分道路の始点位置と終点位置との組が記憶されるが、図では、簡単化のために、図７に示した記号Ｐ０、Ｕ１等の、メッシュ内の部分道路の始点と終点の記号の組を示している。境界直線候補位置情報２４４には、メッシュ内の直線状エッジ部分の始点と終点の座標を格納すればよいが、図では分かりやすさのためにＥ１等の図７に示した直線状エッジ部分の記号と、Ｆ１、Ｇ１等のその直線状エッジ部分の始点と終点の記号の組とを示している。
【００４７】
図７の例では、図８に示すように、道路ベクトルＲ11に関しては、メッシュＭ０に対しては直線状エッジ部分Ｅ１、Ｅ５が部分道路境界直線候補として記憶され、メッシュＭ１に対しては直線状エッジ部分Ｅ２、Ｅ６が部分道路境界直線候補として記憶され、メッシュＭ４に対しては直線状エッジ部分Ｅ３、Ｅ７が部分道路境界直線候補として記憶され、メッシュＭ５に対しては直線状エッジ部分Ｅ４、Ｅ８、Ｅ１０、Ｅ１３が部分道路境界直線候補として記憶される。なお、部分道路境界直線候補データ２４には、他の道路に関しても同様なデータが記憶されるが、簡単化のためにそれらのデータは図示していない。
【００４８】
図１に戻り、道路領域検出可能プログラム４０は、部分道路領域候補検出部４００を実行する。図９は、部分道路領域候補検出部４００の処理の概略フローチャートである。部分道路領域候補検出部４００は、地理画像２１中の道路について、その道路が通過するメッシュ内のその道路が存在する可能性がある領域の複数の候補（部分道路領域候補）を部分道路境界直線候補データ２４と道路ベクトルデータ２２とから検出して、部分道路領域候補データ２５内に格納する。
【００４９】
部分道路領域候補検出部４００は、道路ベクトルデータ２２に含まれる複数の道路ベクトルのそれぞれに対して実行される。そのため、まず、ステップＳ４０１で、いずれかの未処理の道路を道路ベクトルデータ２２から選択し、ステップＳ４０２において、その選択道路に含まれるいずれかの未処理の道路ベクトルを選択し、道路ベクトルデータ２２からその選択道路ベクトルに関するデータを読み出す。具体的には、図４（ｂ）に示す道路ベクトルデータ２２の場合、一つの道路ベクトル識別情報２２１と対応する始点終点位置情報２２２との組からなる一つの道路ベクトルデータを選択し、読み出す。例えば、図４（ａ）の道路ベクトルＲ11を選択し、道路ベクトルデータ２２からその道路ベクトルＲ11に関する道路ベクトル識別情報２２１としてのＲ11と、始点終点位置情報２２２としての点Ｐ０、Ｐ１とを読み出す。以下では、選択された上記一つの道路ベクトル（今の例ではＲ11）を以下では選択道路ベクトルと呼ぶことがある。
【００５０】
つぎに、ステップＳ４０３において、選択道路ベクトル（例えばＲ11）が通過する複数のメッシュのうち未処理のメッシュを一つ選択する。上記選択道路ベクトルが通過する複数のメッシュの識別情報は、部分道路境界直線候補データ２４（図８）内に、上記選択道路ベクトルの道路ベクトル識別情報２２１であるＲ11と同じ道路ベクトル識別情報２４１に対応して記憶されている。例えば選択道路ベクトルＲ11が通過するメッシュはメッシュＭ０、Ｍ１、Ｍ４、Ｍ５である。したがって、上記ステップＳ４０３での未処理のメッシュの検出は、部分道路境界直線候補データ２４内に、上記選択された道路ベクトルの道路ベクトル識別情報２２１であるＲ11と同じ道路ベクトル識別情報２４１に対応して記憶されている複数のメッシュ識別情報２４２のうち、以下の処理を行っていない一つの未処理のメッシュ識別情報２４２を選択することにより行える。例えば、メッシュＭ０が選択される。上記選択されたメッシュを以下では選択メッシュと呼ぶことがある。
【００５１】
つぎにステップＳ４０４において、上記選択道路ベクトル（例えばＲ11）の、上記選択メッシュ内の部分道路に対する部分道路境界直線候補を部分道路境界直線候補データ２４（図８）から読み出し、リストＭに登録する。今の例では、選択道路ベクトルＲ11に対しては、メッシュＭ０に含まれる部分道路境界直線候補Ｅ１（Ｆ１，Ｇ１）とＥ５（Ｆ５，Ｇ５）が、リストＭに登録される。部分道路境界直線候補Ｅ１とＥ５は、図７に示されたように、メッシュＭ０内にあり、選択道路ベクトルＲ11に平行で、かつ、距離がある一定値以内にあり、選択道路ベクトルＲ11のうちメッシュＭ０内にある部分道路が存在する領域の境界直線となる可能性がある直線である。
【００５２】
つぎにステップＳ４０５において、リストＭに登録された部分道路境界直線候補の数が２以上であるか否かを判定する。今の例では、その数は２である。このようにリストＭに登録された部分道路境界直線候補の数が２以上である場合は、ステップＳ４０６において、リストＭに登録された複数の部分道路境界直線候補のうちの任意の二つを組み合わせて、その組と選択道路ベクトルＲ11に関する道路ベクトルデータとに基づいて選択メッシュＭ０内で選択道路ベクトルＲ11が存在する可能性がある４辺形領域を決定し、当該４辺形領域を、選択道路ベクトルＲ11に対する選択メッシュＭ０内の部分道路領域候補として、部分道路領域候補データ２５内に格納する。上記４辺形領域の決定方法は後に述べる。
【００５３】
ステップＳ４０６の終了後に、ステップＳ４０８において、選択道路ベクトル（Ｒ11）が通過するメッシュの全てを選択したか否かが判定され、まだ選択されていないメッシュがあるときには、処理はステップＳ４０３に戻り、以上の処理が繰り返される。本実施の形態では、選択道路ベクトルＲ11が通過する他のメッシュは、図８に示した部分道路境界直線候補データ２４から分かるように、メッシュＭ１、Ｍ４、Ｍ５である。したがって、これらのメッシュに関して以上の処理が繰り返される。
【００５４】
なお、ステップＳ４０５において、リストＭに登録された部分道路境界直線候補の数が１であると判定されたときには、ステップＳ４０７においてリストＭ内の部分道路境界直線候補を削除し、その後処理はステップＳ４０８に移る。なお、ステップＳ４０５において、リストＭに登録された部分道路境界直線候補の数が０であると判定される場合は生じない。部分道路境界直線候補の数が０であるようなメッシュは、ステップＳ４０３において選択されないからである。
【００５５】
以上のような処理の繰り返しにより、ステップＳ４０８において、選択道路ベクトルが通過する全てのメッシュの選択が終了したと判断されたときには、ステップＳ４０９において、選択道路ベクトル（今の例ではＲ11）が属する道路に含まれる道路ベクトルの全てが処理されたか否かが判定される。もし未処理の他の道路ベクトル（例えばＲ12）があるときには、処理はステップＳ４０２に移り、例えば、上記選択道路ベクトルＲ11につながった他の道路ベクトルＲ12について、ステップＳ４０２以降の処理が繰り返される。その後、ステップＳ４０９において、選択道路ベクトル（今の例ではＲ12）が属する道路に含まれる道路ベクトルの全てが処理されたと判定されときには、ステップＳ４１０において、処理された複数の道路ベクトルを含む道路と異なる、他の道路ベクトルを含む未処理の他の道路があるか否かが判定され、そのような未処理の他の道路があるときには、処理はステップＳ４０１に戻り、当該他の道路に含まれた複数の道路ベクトルに関してステップＳ４０１以降の処理が繰り返される。その後、ステップＳ４１０において、他の道路ベクトルを含む未処理の他の道路がないと判定されたときに、部分道路領域候補検出部４００の処理が終了する。
【００５６】
部分道路領域候補検出部４００の処理のうち、ステップＳ４０５での処理の詳細を説明する。図１０は、道路ベクトルＲ11に対して検出される部分道路領域候補の例を示す図である。メッシュＭ０に関しては、図９のステップＳ４０４では、部分道路境界直線候補Ｅ１、Ｅ５がリストＭに登録されている。一方、選択道路ベクトルＲ11のうちのメッシュＭ０内の部分道路は点Ｐ１から点Ｕ１までである。以下この部分道路を両端の点を並べてＰ0Ｕ1でもって表す。部分道路境界直線候補Ｅ１、Ｅ５と部分道路Ｐ0Ｕ1のうちでは、部分道路Ｐ0Ｕ1が一番短い。図９のステップＳ４０５では、リストＭに登録された二つの部分道路境界直線候補Ｅ１、Ｅ５上にある、部分道路Ｐ0Ｕ1を越えない長さ（今の例ではそれと同じ長さ）を有し、選択道路ベクトルＲ11に平行でともにメッシュＭ０内に位置する２辺と、選択道路ベクトルＲ11に垂直でともにメッシュＭ０内に位置する２辺とを有するという部分道路領域候補条件を満たす４辺形Ｊ11Ｊ12Ｊ52Ｊ51が、部分道路Ｐ0Ｕ1に対する部分道路領域候補として検出される。
【００５７】
図１１は、部分道路領域候補データ２５の例を示す図である。部分道路領域候補データ２５には、部分道路領域候補検出部４００により検出された部分道路領域候補に関して、道路ベクトル識別情報２５１と、メッシュ識別情報２５２と、４辺形情報２５３とが格納される。図１０に示した４辺形Ｊ11Ｊ12Ｊ51Ｊ52に関しては、例えば道路ベクトル識別情報２５１として選択道路ベクトルの道路ベクトル識別情報Ｒ11が格納され、メッシュ識別情報２５２には、メッシュＭ０の識別情報Ｍ０が格納され、４辺形情報２５３には検出された４辺形を構成する二つの部分道路境界線候補の記号Ｅ１、Ｅ５と、両候補のそれぞれ上の２頂点Ｊ11とＪ12及びＪ51とＪ52とが格納される。
【００５８】
図１０に戻り、メッシュＭ０にある部分道路境界直線候補は上記のＥ１、Ｅ５のみであり、上記部分道路領域候補条件を満たす他の部分道路領域候補はメッシュＭ０からは検出されない。メッシュＭ１に関しては、図９のステップＳ４０４では、部分道路境界直線候補Ｅ２、Ｅ６がリストＭに登録されている。一方、選択道路ベクトルＲ11のうちのメッシュＭ１内の部分道路は点Ｕ１から点Ｕ２までである。図９のステップＳ４０５では、リストＭに登録された二つの部分道路境界直線候補Ｅ２、Ｅ６と部分道路Ｕ1Ｕ2とから、部分道路Ｕ1Ｕ2に対する部分道路領域候補が、既に述べた部分道路領域候補条件を満すように決定される。この際、部分道路境界直線候補Ｅ６は、点Ｇ５からＧ６までである。一方、部分道路境界直線候補Ｅ２は点Ｆ２からＧ２までであり、部分道路Ｕ1Ｕ2及び部分道路境界直線候補Ｅ６より短いが、部分道路Ｕ1Ｕ2が存在する範囲と平行で、メッシュＭ１内に位置する範囲内にある線分Ｊ21Ｇ２まで延長可能な直線として扱われる。こうして、上記部分道路領域候補条件を満す４辺形として、部分道路境界直線候補Ｅ２上の点Ｊ21から点Ｇ２までの線分と、部分道路境界直線候補Ｅ６上の点Ｊ61から点Ｊ62までの線分とにより規定される４辺形Ｊ21Ｇ２Ｊ62Ｊ61が検出される。
【００５９】
同様に、メッシュＭ４に関しては、図９のステップＳ４０４では、部分道路境界直線候補Ｅ３、Ｅ７がリストＭに登録されている。一方、選択道路ベクトルＲ11のうちのメッシュＭ４内の部分道路は点Ｕ２から点Ｕ３までである。図９のステップＳ４０５では、リストＭに登録された二つの部分道路境界直線候補Ｅ３、Ｅ７と部分道路Ｕ2Ｕ3とから、部分道路Ｕ2Ｕ3に対する部分道路領域候補が、既に述べた部分道路領域候補条件を満すように決定される。この際、部分道路Ｕ1Ｕ2は、部分道路境界直線候補Ｅ３、Ｅ６よりも短いので、メッシュＭ０の場合と同様にして、図に示すように、上記部分道路領域候補条件を満す４辺形として、部分道路境界直線候補Ｅ３上の点Ｊ31から点Ｊ32までの線分と、部分道路境界直線候補Ｅ７上の点Ｊ71から点Ｊ72までの線分とにより規定される４辺形Ｊ31Ｊ32Ｊ72Ｊ71が検出される。
【００６０】
同様に、メッシュＭ５に関しては、図９のステップＳ４０４では、部分道路境界直線候補Ｅ４、Ｅ８がリストＭに登録されている。一方、選択道路ベクトルＲ11のうちのメッシュＭ５内の部分道路は点Ｕ３から点Ｐ１までである。図９のステップＳ４０５では、リストＭに登録された二つの部分道路境界直線候補Ｅ４、Ｅ８と部分道路Ｕ3Ｐ1とから、部分道路Ｕ3Ｐ1に対する部分道路領域候補が、既に述べた部分道路領域候補条件を満すように決定される。この際、部分道路境界直線候補Ｅ４は、点Ｇ３からＧ４までであり、部分道路Ｕ3Ｐ1より短いが、部分道路Ｕ3Ｐ1が存在する範囲と平行で、メッシュＭ４内に位置する範囲内にある線分Ｇ３Ｊ41まで延長可能な直線として扱われる。同様に、部分道路境界直線候補Ｅ８は、点Ｇ７からＧ８までであり、部分道路Ｕ3Ｐ1より短いが、部分道路Ｕ3Ｐ1が存在する範囲と平行で、メッシュＭ４内に位置する範囲内にある線分Ｇ７Ｊ81まで延長可能な直線として扱われる。こうして、上記部分道路領域候補条件を満す４辺形として、部分道路境界直線候補Ｅ４上の点Ｇ３から点Ｊ41までの線分と、部分道路境界直線候補Ｅ８上の点Ｇ８から点Ｊ81までの線分とにより規定される４辺形Ｇ３Ｊ41Ｊ81Ｇ８が検出される。
以上のようにメッシュＭ１、Ｍ４、Ｍ５に対して検出された４辺形の情報も、部分道路領域候補として、図１１に示したように部分道路領域候補データ２５内に格納される。
【００６１】
図１２は、道路ベクトルＲ11に対して検出される他の部分道路領域候補の例を示す図である。図では、メッシュＭ１に対して、部分道路境界直線候補Ｅ２上の点Ｊ21から点Ｇ２までの線分と部分道路境界直線候補Ｅ９上の点Ｊ91から点Ｊ92までの線分とにより規定される４辺形Ｊ21Ｇ２Ｊ92Ｊ91が検出される。メッシュＭ５に対して、部分道路境界直線候補Ｅ４上の点Ｇ３から点Ｊ41までの線分と部分道路境界直線候補Ｅ10上の点Ｊ101から点Ｊ102までの線分とにより規定される４辺形Ｇ３Ｊ41Ｊ102Ｊ101が検出される。
【００６２】
図１３は、道路ベクトルＲ11に対して検出される更に他の部分道路領域候補の例を示す図である。図では、メッシュＭ１に対して、部分道路境界直線候補Ｅ２上の点Ｊ21から点Ｇ２までの線分と部分道路境界直線候補Ｅ11上の点Ｊ111から点Ｊ112までの線分とにより規定される４辺形Ｊ21Ｇ２Ｊ112Ｊ111が検出される。メッシュＭ５に対して、部分道路境界直線候補Ｅ４上の点Ｇ３から点Ｊ41までの線分と部分道路境界直線候補Ｅ13上の点Ｊ131から点Ｊ132までの線分とにより規定される４辺形Ｇ３Ｊ41Ｊ132Ｊ131が検出される。
【００６３】
図１４は、道路ベクトルＲ11に対して検出される更に他の部分道路領域候補の例を示す図である。図では、メッシュＭ１に対して、部分道路境界直線候補Ｅ６上の点Ｇ５から点Ｇ６までの線分と部分道路境界直線候補Ｅ９上の点Ｊ93から点Ｊ94までの線分とにより規定される４辺形Ｇ５Ｇ６Ｊ92Ｊ91が検出される。メッシュＭ５に対して、部分道路境界直線候補Ｅ８上の点Ｇ７から点Ｊ81までの線分と部分道路境界直線候補Ｅ10上の点Ｊ103から点Ｊ102までの線分とにより規定される４辺形Ｇ７Ｊ81Ｊ102Ｊ103が検出される。
【００６４】
図１５は、道路ベクトルＲ11に対して検出される更に他の部分道路領域候補の例を示す図である。図では、メッシュＭ１に対して、部分道路境界直線候補Ｅ６上の点Ｇ５から点Ｇ６までの線分と部分道路境界直線候補Ｅ11上の点Ｊ111から点Ｊ112までの線分とにより規定される４辺形Ｇ５Ｇ６Ｊ112Ｊ111が検出される。メッシュＭ５に対して、部分道路境界直線候補Ｅ８上の点Ｇ７から点Ｊ81までの線分と部分道路境界直線候補Ｅ13上の点Ｊ133から点Ｊ132までの線分とにより規定される４辺形Ｇ７Ｊ81Ｊ132Ｊ133が検出される。
【００６５】
図１６は、道路ベクトルＲ11に対して検出される更に他の部分道路領域候補の例を示す図である。図では、メッシュＭ１に対して、部分道路境界直線候補Ｅ９上の点Ｊ95から点Ｊ96までの線分と部分道路境界直線候補Ｅ11上の点Ｆ11から点Ｇ11までの線分とにより規定される４辺形Ｊ91Ｊ92Ｇ11Ｆ11が検出される。メッシュＭ５に対して、部分道路境界直線候補Ｅ10上の点Ｊ104から点Ｊ102までの線分と部分道路境界直線候補Ｅ13上の点Ｇ12から点Ｊ132までの線分とにより規定される４辺形Ｊ104Ｊ102Ｊ132Ｇ12が検出される。
【００６６】
図１２から図１６を用いて説明したように、メッシュＭ１、Ｍ４、Ｍ５に対して検出されたいろいろな４辺形の情報は、図１１に示したように、部分道路領域候補データ２５内に部分道路領域候補として追加して格納される。
なお、以上の処理では、例えば図７から分かるように、一つの道路ベクトルのうち、一つのメッシュに属する部分道路の全長に対応して部分道路境界直線候補が存在していても、そのメッシュにおいて検出される部分道路領域候補は、当該部分道路の全長の一部に対するものであり、当該部分道路の残りの部分に対しては部分道路領域候補は検出されない場合が生じているが、検出されない部分道路領域は、後に説明するように補間により決定される。
また、図７等では、説明のために検出される部分道路境界直線候補の数は少なくしているが、一つの道路ベクトル、例えばＲ11に関して、一つのメッシュに対して実際に検出される部分道路境界直線候補の数は１０数本になることがあり、このため、同じ一つの道路ベクトルＲ11に関して一つのメッシュに対して検出される部分道路領域候補の数は数十〜百数十になると考えられる。
【００６７】
図１に戻り、道路領域検出可能プログラム４０は、部分道路領域候補検出部４００の実行後に部分道路領域決定部５００を実行する。
図１７は、部分道路領域決定部５００の処理の概略フローチャートである。部分道路領域決定部５００は、部分道路領域候補検出部４００で検出された複数の部分道路領域候補の中から実際の道路の存在領域を表す可能性が最も高い部分道路領域を決定する。
【００６８】
まず、ステップＳ５０１において、いずれかの道路に含まれたいずれかの道路ベクトルを選択する。ステップＳ５０２において、当該選択道路ベクトルが通過するメッシュであって、当該メッシュに対して当該選択道路ベクトルに対する部分道路領域候補が少なくとも一つ部分道路領域候補データ２５に含まれているメッシュを選択する。つぎにステップＳ５０３においてメッシュの選択が成功か否かを判定し、不成功の場合には、ステップＳ５０４において、当該選択道路ベクトルは廃止された道路であると判断し、部分道路領域データ２６内に、当該選択道路ベクトルに対応して廃止を示す情報を格納する。その後処理はステップＳ５０９に移動する。
【００６９】
一方、ステップＳ５０３においてメッシュ選択が成功と判断されたときには、ステップＳ５０５において、部分道路領域候補データ２５（図１１）から、当該選択道路ベクトルのうち当該選択メッシュに属する部分道路に対する部分道路領域候補を、それらが複数ある場合には、全て読み出す。具体的には、その選択メッシュに対する４辺形情報２５３（図１１）を読み出す。
【００７０】
ステップＳ５０６とＳ５０７において、それらの部分道路領域候補の各々について、部分道路領域である可能性を個別に評価する。本実施の態様では、個別評価は、各部分道路領域候補に属する、前記地理画像内の画素の画像値に依存する評価基準に基づく評価と各部分道路領域候補の幾何学的な特徴量に依存する評価基準に基づく評価の両方を行う。これにより、各メッシュに対して検出された複数の部分道路領域候補に対する評価がより適切に行いやすくなる。
【００７１】
まずステップＳ５０６では、各部分道路領域候補を地理画像２１の画像値に基づいて評価する。例えば、部分道路領域候補内の画素の色によって、例えば色の分布状態によって、その領域が道路である可能性が高いか否かを評価する。例えば、部分道路領域候補について、当該候補領域内の画素の３原色成分（Ｒ、Ｇ、Ｂ）に対応する色相Ｈの標準偏差を計算する。既に述べたように、エッジ検出部１００（図２）では、ステップＳ１０１において、地理画像２１のＲＧＢ成分を色相Ｈ、彩度Ｓ、明度Ｉの成分に変換している。したがって上記ステップＳ５０６において色相の標準偏差を求めるときに、エッジ検出部１００により生成された色相データを利用すればよい。一般に道路は、灰色等の一様な色であるので、色相の分散が小さい部分道路領域候補は、道路領域を表す可能性が高い。例えば、コンクリート道路では標準分散は３０度位である。したがって、部分道路領域候補内の画素の色の標準分散を第１の評価値とする。したがって、部分道路領域候補の第１の評価値が小さいほど、道路領域を表す可能性が高いことになる。もちろん、色の分布に関して他の物理量を評価値としてもよい。
【００７２】
つぎに、ステップＳ５０７において、各部分道路領域候補を各部分道路領域候補の幾何学的な特徴量に基づいて評価する。例えば、各部分道路領域候補が表す部分道路領域の幅により評価する。これは、複数の車線を含む道路の特徴を利用して、部分道路領域候補を評価することである。具体的には、部分道路領域候補が示す道路幅が、１車線の道路の標準的な道路幅（通常の２．７５ｍ〜３．５ｍのうちからあらかじめ定めた値）又はその複数倍に一致する場合に、最小の評価値（部分道路領域である可能性が高いことを示す評価値）を決定し、部分道路領域候補が示す道路幅が、上記標準的な道路幅又はその倍数からずれるにしたがって高い評価値を決定するように、部分道路領域候補に対して、当該部分道路領域候補が示す道路幅に依存した第２の評価値を決定する。図１８は、道路幅と第２の評価値との関係の例を示す図である。図では、１車線の標準の道路幅は３．５ｍとし、部分道路領域候補の道路幅がこの標準値の整数倍であるときに、第２の評価値を０とし、それらの値の丁度中間のときに、第２の評価値を１としている。
【００７３】
部分道路領域候補に対する最終的な評価値は、上記第１、第２の評価値を重みを付けて加算して、例えば下記の式１により決定することができる。
最終評価値＝第１の評価値＋２０×第２の評価値 （１）
【００７４】
ステップＳ５０８では、各部分道路領域候補に対して上記最終評価値を計算し、その値が最も小さい部分道路領域候補を、前記選択道路のうち選択メッシュ内に位置する部分道路が存在する道路領域である可能性が最も高い暫定部分道路領域として決定する。決定された暫定部分道路領域に関するデータを、部分道路領域データ２６内に暫定部分道路領域として格納する。
その後、ステップＳ５０９において、前記選択道路ベクトルが通過する他のメッシュであって、部分道路領域候補が部分道路領域候補データ２５に格納されているメッシュがあるか否かを判定し、あると判定された場合には、処理はステップＳ５０２に戻り、ステップＳ５０２以降の処理が、前記選択道路が通過する他のメッシュであって、部分道路領域候補が部分道路領域候補データ２５に格納されているメッシュが存在しないと判定されるまで繰り返される。
【００７５】
図１９は、部分道路領域決定部５００により決定される暫定部分道路領域の例を示す図である。図では、道路ベクトルＲ11に対して、メッシュＭ１内では４辺形Ｊ21Ｇ２Ｊ112Ｊ111が暫定部分道路領域として決定され、メッシュＭ５内では４辺形Ｇ３Ｊ41Ｊ132Ｊ131が暫定部分道路領域として決定されている。
【００７６】
図２０は、部分道路領域データ２６の例と、上記二つの暫定部分道路領域が決定されたときのその部分道路領域データ２６の値の例を示す図である。部分道路領域データ２６は、処理中の道路ベクトル（今の例ではＲ11）の道路ベクトル識別情報２６１、部分道路領域が決定されたメッシュの識別情報２６２、４辺形情報２６３、確定フラグ２６４とを含む。図の例では、道路ベクトル識別情報２６１には道路ベクトルの記号Ｒ11が格納され、メッシュ識別情報２６２には、メッシュ番号Ｍ１又はＭ５が格納され、４辺形情報２６３には、決定された４辺形の頂点Ｊ21，Ｇ２，Ｊ112，Ｊ111又はＧ３，Ｊ41，Ｊ131，Ｊ132が格納されている。確定フラグ２６４には、４辺形情報２６３が示す部分道路領域が暫定部分道路領域であることを示す値０が格納されている。後に暫定部分道路領域が最終的に部分道路領域として決定されたときには、確定フラグ２６４には４辺形情報２６３が示す部分道路領域が確定された部分道路領域であることを示す値１が設定されるようになっている。
【００７７】
以上の処理では、選択道路ベクトルに関して複数のメッシュに対して決定された複数の部分道路領域候補を個別に評価して、当該選択道路ベクトルに対する複数の暫定部分道路領域を決定した。部分道路領域決定部５００では、選択道路ベクトルに対して決定された複数の暫定部分道路領域の相互のつながりを考慮するために、更に以下の処理を実行し、決定された複数の暫定部分道路領域候補の相互の位置関係が所望の位置関係にあるか否かを判断し、最終的な部分道路領域を決定する。このために、図１７に戻り、部分道路領域決定部５００では、選択道路に対するステップＳ５０２以降の処理の繰り返しの後に、ステップＳ５０９において、前記選択道路が通過する他のメッシュであって、部分道路領域候補が部分道路領域候補データ２５に格納されているメッシュが存在しないと判定されたときに、処理はステップＳ５１０に移る。
【００７８】
ステップＳ５１０では、同じ選択道路ベクトルに関して、異なるメッシュに対して個別に決定された上記複数の暫定部分道路領域の各々と、当該暫定部分道路領域に対して最も近い位置にある他の暫定部分道路領域とが隣接する部分道路領域となるための望ましい所定の位置関係を有するか否かを判定する。例えば、それらの暫定部分道路領域の幅が所定の誤差範囲内で一致し（すなわち、それらの暫定部分道路領域の幅の相違は上記所定の誤差範囲内であり）、かつ、それらの暫定部分道路領域の中心線の位置が所定の誤差範囲内で一致するという位置関係を満たしているか否かを判定する。例えば、図１９に例示した二つの暫定部分道路領域の場合には、道路幅も中心線位置もほぼ一致しているので、上記位置関係が満たされている。このように、複数の暫定部分道路領域が上記位置関係を満たしている場合には、図１７に戻り、ステップＳ５１１において、上記暫定部分道路領域を最終的に部分道路領域として決定する。すなわち、図２０に示された部分道路領域データ２６内のそれらの暫定部分道路領域に対する確定フラグ２６４の値を１に設定する。
【００７９】
図２１は、選択道路ベクトルＲ11に対して検出された他の暫定部分道路領域の例を示す図である。図では、暫定部分道路領域として、二つの４辺形Ｊ21Ｇ２Ｊ92Ｊ91とＧ３Ｊ41Ｊ132Ｊ131が決定されている。図の場合には、これら二つの暫定部分道路領域の道路幅と中心線の位置が一致していない。このような場合には、図１７に戻り、ステップＳ５１２において、暫定部分道路領域を再決定し、最終的な部分道路領域を決定する。
【００８０】
例えば、図２１に示された左側の４辺形Ｊ21Ｇ２Ｊ92Ｊ91の左側に別の図示しない４辺形が暫定部分道路領域として更に検出されていて、上記左側の４辺形Ｊ21Ｇ２Ｊ92Ｊ91と当該別の図示しない４辺形が上記位置関係を満たすときには、図に示された右側の４辺形Ｇ３Ｊ41Ｊ132Ｊ131の代わりの暫定部分道路領域が検出される。例えば、図１７のステップＳ５０８で暫定部分道路領域を決定するときに比較対象とされた他の複数の部分道路領域候補のうち、最終評価値が所定の上限値以下の評価値を持ち、図２１の左側の４辺形Ｊ21Ｇ２Ｊ92Ｊ91に対して上記位置関係を満たすものがないかを判定する。もしそのような部分道路領域候補があるときには、図２１の右側の４辺形に代えて当該部分道路領域候補を、暫定部分道路領域に決定したうえで、更に部分道路領域に決定する。しかし、そのような代わりの部分道路領域候補が存在しないときには、図２１の右側の４辺形をそのまま部分道路領域として決定する。
【００８１】
また、図２１に示された左側の４辺形Ｊ21Ｇ２Ｊ92Ｊ91の左側に上記別の図示しない４辺形が暫定部分道路領域として検出されていて、上記左側の４辺形Ｊ21Ｇ２Ｊ92Ｊ91と当該別の図示しない４辺形も上記位置関係を満たさないときには、図２１に図示されていない上記別の４辺形と、図示された左側の４辺形と、図示された右側の４辺形のそれぞれの代わり使用可能な部分道路領域候補であって、最終評価値が上記上限値以下であり、上記位置関係を満たすものがあるか否かを判定する。上記３つの４辺形のうちのいずれか一つ又は二つ又はその全てに対して代わりに使用可能な一つ又は複数の部分道路領域候補が見つかった場合には、その一つ又は複数の部分道路領域候補を、代わりの暫定部分道路領域に決定し、更に最終的な部分道路領域に決定する。
【００８２】
図１７に戻り、こうして、ステップＳ５１１又はＳ５１２により、選択道路ベクトル（例えばＲ11）に対する部分道路領域が決定されたことになる。その後ステップＳ５１３において、前記選択道路ベクトル以外に、未処理の他の道路ベクトルがあるか否かを判定し、当該他の未処理の道路ベクトルがあると判定されたときには、処理はステップＳ５０１に戻り、ステップＳ５０１以降の処理を当該他の道路ベクトルに関して実行する。その後ステップＳ５１３において、他の未処理の道路ベクトルがないと判定されたとき、部分道路領域決定部５００の処理が終了する。
【００８３】
図１に戻り、道路領域検出可能プログラム４０は道路領域決定部６００を実行する。道路領域決定部６００では、まず、いずれかの道路の全ての道路ベクトルの複数の区間に関して決定された複数の部分道路領域を用いて、部分道路領域が決定されていない区間に対する部分道路領域を決定する。決定には、例えば、隣接する区間に対して決定された複数の部分道路領域を接続する方法を採ることができる。例えば、図１９に示された二つの４辺形Ｊ21Ｇ２Ｊ112Ｊ111とＧ３Ｊ41Ｊ132Ｊ131との間を接続する部分道路領域を補間により決定する。このような接続する４辺形としては、例えば、左側の４辺形の頂点Ｇ２、Ｊ112と右側の４辺形の頂点Ｇ３Ｊ131を頂点とする４辺形を使用することができる。図１９の点線は、このような接続用の４辺形の二つの辺を示している。あるいは図２１に示された二つの４辺形Ｊ21Ｇ２Ｊ92Ｊ91とＧ２Ｊ41Ｊ132Ｊ131が、部分道路領域として決定された場合も、同様に、例えばそれらの二つの４辺形を結ぶ４辺形Ｇ２Ｇ３Ｊ131Ｊ92を接続する４辺形として使用することができる。図２１の点線は、このような接続用の４辺形の二つの辺を示している。このようにしてそれぞれ道路を構成する複数の道路ベクトルの全てに対して、連続した領域を表すのに必要な数の部分道路領域が決定され、それらの部分道路領域により連続した一つの道路領域が決定される。
【００８４】
道路領域決定部６００は、その後、それぞれ異なる道路に属するが、互いに接続されるべき複数の道路ベクトルあるいは互いに交叉する複数の道路ベクトルに対して決定された道路領域を接続する処理を行う。
図２２は、二つの隣接した道路ベクトルＲ11とＲ12に対して決定された二つの道路領域の接続を説明するための図である。図において、左側の４辺形Ｊ13Ｇ41Ｊ132Ｆ11は、道路ベクトルＲ11に対して決定された道路領域の例であり、右側の４辺形Ｆ14Ｇ14Ｊ151Ｆ15は、道路ベクトルＲ12に対して決定された道路領域の例であるとする。道路領域決定部６００では、これらの二つの道路領域を接続するために、二つの領域の一方の上辺を延長して二つの領域の他方の上辺と接続させる。上記二つの領域のいずれかの下辺を延長して他方の領域の下辺と接続させる。いずれの領域の上辺を延長するかは、二つの領域の上辺の位置関係に依存する。二つの領域の上辺が道路領域として望ましい形になるように一方の領域の上辺が延長される。もちろん、両方の領域の上辺を延長させることが望ましい場合には、そのように行う。あるいは、一方の領域の上辺を延長とは反対の方向に後退させることが望ましい場合には、そのように行う。下辺についても同様である。図の例では、左側の４辺形Ｊ13Ｇ41Ｊ132Ｆ11の上側の辺Ｆ11Ｊ132を右方向に延長して点Ｃａで右側の４辺形の上辺に接続させる。同様に、右側の４辺形Ｆ14Ｇ14Ｊ151ＧＦ15の下側の辺Ｆ14Ｇ14を左方向に延長して点Ｃｂで左側の４辺形の下辺に接続させる。こうして、二つの道路ベクトルＲ11とＲ12に対する道路領域として、上側の一組の折れ線Ｆ11ＣａとＣａＪ151と、下側の一組の折れ線Ｊ13ＣｂとＣｂＧ14とを境界線とする連続した道路領域が決定される。
【００８５】
図２３は、交叉する道路ベクトルＲ11とＲ３に対して決定された２つの道路領域の接続を説明するための図である。図において、折れ線Ｊ13ＣｂＧ14とＦ11ＣａＪ151は、道路ベクトルＲ11とＲ12に対して決定された、図２２に既に示した道路領域を規定する境界線である。一方、直線Ｊ161Ｇ16と直線Ｆ17Ｊ171は、道路ベクトルＲ３に対して決定された一組の境界線とする。道路ベクトルＲ11とＲ３とが交叉するところでは、図に示すように４つの境界線の間の４つの交点Ｃｃ、Ｃｄ、Ｃｅ、Ｃｆが決定され、これらの点が交差点の存在領域を示し、この交差点領域内では道路の境界線が存在しないように、道路ベクトルＲ11とＲ３に対する境界線が修正される。
【００８６】
道路領域決定部６００は、以上のようにして各道路ベクトルに対して道路領域を決定した後、各道路ベクトルに対する道路幅と車線数を判別する。車線数は、当該道路ベクトルに対して決定された道路領域の道路幅と、既に図１８に関連して説明した標準的な道路幅との比で推定することができる。道路幅又は車線数の一方が場所により異なるときには、道路幅又は車線数の一方が異なる場所毎に、道路領域を区分し、それぞれの区分された道路領域毎に道路幅と車線数を決定する。
【００８７】
道路領域決定部６００は、決定された道路領域とその領域に関する道路幅と車線数等のデータを当該道路ベクトルに対応して道路領域データ２７内に記憶する。図２４は、道路領域データ２７の例を示す図である。道路領域データ２７は道路ベクトル識別情報２７１と、道路存在領域を示す一対の境界線を構成する点列の位置を示す境界線情報２７２と、道路幅２７３、車線数２７４、備考情報２７５とを含んでいる。図２２の場合、道路ベクトルＲ11に対しては、道路ベクトル識別情報２７１には、例えばその記号Ｒ11が記憶され、境界線情報２７２には、図２３の場合には、下側の境界線上の点列Ｊ13−Ｃｄ，Ｃｅ−Ｃｂ−Ｇ14と、上記点列に対応する、上側の境界線上の点列Ｆ11−Ｃｃ，Ｃｆ−Ｃａ−Ｊ151とが記憶される。道路幅２７３には、決定された道路領域の同じ道路幅の領域に対応して道路幅が記憶される。車線数２７４に関しても同じである。備考情報２７５には、例えば廃止と判断された道路ベクトルに対して廃止を示す情報が記憶される。
以上のような処理を全ての道路に対して実行することにより、地理画像２１と道路ベクトルデータ２２とから、地理画像２１内に含まれた道路の存在領域を比較的簡単に決定できることが分かる。
なお、本発明は、以上の実施の形態に限定されるものではなく、本発明の要旨を変更しない範囲で、修正あるいは変更をしてもよいことは言うまでもない。
【図面の簡単な説明】
【００８８】
【図１】本発明に係る、道路領域検出可能装置の一つの実施形態の概略ブロック図である。
【図２】エッジ検出部の処理の概略フローチャートである。
【図３】地表を撮影して得られる画像の一例を示す図である。
【図４】道路ベクトルデータを説明するための図である。
【図５】図３の画像から得られたエッジ画像の例を示す図である。
【図６】部分道路境界直線候補検出部の処理の概略フローチャートである。
【図７】エッジ画像を分割して得られる複数のメッシュとそれらのメッシュに対して抽出された複数の部分道路境界直線候補を模式的に示す図である。
【図８】部分道路境界直線候補データの例を示す図である。
【図９】部分道路領域候補検出部の処理の概略フローチャートである。
【図１０】道路ベクトルに対して検出される部分道路領域候補の例を示す図である。
【図１１】部分道路領域候補データの例を示す図である。
【図１２】道路ベクトルに対して検出される他の部分道路領域候補の例を示す図である。
【図１３】道路ベクトルに対して検出される更に他の部分道路領域候補の例を示す図である。
【図１４】道路ベクトルに対して検出される更に他の部分道路領域候補の例を示す図である。
【図１５】道路ベクトルに対して検出される更に他の部分道路領域候補の例を示す図である。
【図１６】道路ベクトルに対して検出される更に他の部分道路領域候補の例を示す図である。
【図１７】部分道路領域決定部の処理の概略フローチャートである。
【図１８】道路幅と第２の評価値との関係の例を示す図である。
【図１９】部分道路領域決定部により決定される暫定部分道路領域の例を示す図である。
【図２０】部分道路領域データの例を示す図である。
【図２１】選択道路ベクトルに対して検出された他の暫定部分道路領域の例を示す図である。
【図２２】二つの隣接した道路ベクトルに対して決定された２つの道路領域の接続を説明するための図である。
【図２３】交叉する道路ベクトルに対して決定された２つの道路領域の接続を説明するための図である。
【図２４】道路領域データの例を示す図である。
【符号の説明】
【００８９】
Ｅ０からＥ１３…直線状エッジ部分、Ｍ０〜Ｍ８…メッシュ、Ｒ１、Ｒ２、Ｒ３…道路、Ｒ11、Ｒ12…道路ベクトル。
【特許請求の範囲】
【請求項１】
コンピュータを、エッジ検出手段と、領域分割手段と、部分道路境界直線候補検出手段と、部分道路領域候補検出手段と、部分道路領域決定手段と、道路領域決定手段、として機能させる道路領域決定可能プログラムであって、
前記エッジ検出手段は、地表を上空から撮影して得られ、あらかじめ地理画像記憶手段に記憶された地理画像から複数のエッジを検出して当該複数のエッジを表すエッジ画像を生成し、
前記領域分割手段は、前記地理画像の存在領域を複数のメッシュに分割し、
前記部分道路境界直線候補検出手段は、いずれかの道路が通過する複数のメッシュの各々に関して、当該道路の当該メッシュ内に位置する部分道路に対して所定の位置条件を満たす、当該メッシュ内に位置する複数の直線状のエッジ部分を、当該部分道路に対する複数の部分道路境界直線候補として、前記エッジ画像から、かつ、前記道路の中心線を近似的に直線で表す連結された複数の道路ベクトルを指定する、あらかじめ道路ベクトルデータ記憶手段に記憶された道路ベクトルデータに基づいて検出し、
前記部分道路領域候補検出手段は、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路境界直線候補検出手段により検出された前記複数の部分道路境界直線候補から選択された任意の二つからなる複数の組合わせにより定まる複数の領域を、当該道路の当該メッシュ内に位置する前記部分道路の存在領域に対する複数の部分道路領域候補として検出し、
前記部分道路領域決定手段は、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路境界直線候補検出手段により検出された前記複数の部分道路領域候補の各々について、当該部分道路領域候補が当該メッシュ内の前記部分道路の存在領域である妥当性を所定の評価基準に基づいて評価し、前記複数の部分道路領域候補に対する評価結果に基づいて前記複数の部分道路領域候補の一つを当該部分道路の当該メッシュ内の存在領域として決定し、
前記道路領域決定手段は、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路領域決定手段で決定された複数の部分道路領域を接続して当該道路の存在領域を決定する、
ことを特徴とする道路領域決定可能プログラム。
【請求項２】
前記部分道路境界直線候補検出手段が前記いずれかの道路が通過する前記複数のメッシュの各々に対する前記複数の部分道路境界直線候補が満たすべき前記所定の位置条件は、部分道路境界直線候補は、当該部分道路の近傍にあり、かつ、当該部分道路に対してほぼ平行に位置することである、
ことを特徴とする請求項１に記載の道路領域決定可能プログラム。
【請求項３】
前期部分道路領域決定手段は、
前記いずれかの道路が通過する前記複数のメッシュのそれぞれに対して検出された前記複数の部分道路領域候補の各々について、部分道路領域である妥当性を、それぞれの部分道路領域候補ごとに個別に所定の第１の評価基準に基づいて評価し、前記複数の部分道路領域候補に対する評価結果に基づいて、前記複数の部分道路領域候補の一つを、当該メッシュ内の当該道路の前記部分道路に対する暫定部分道路領域として決定する暫定部分道路領域決定手段と、
前記いずれかの道路が通過する前記複数のメッシュのそれぞれに対して決定された前記複数の暫定部分道路領域の各々について、前記複数の暫定部分道路領域の相互の位置関係に関係する第２の評価基準に基づいて、部分道路領域としての妥当性を評価し、前記複数の暫定部分道路領域に対する評価結果に基づいて、前記複数の暫定部分道路領域の各々について、当該暫定部分道路領域を当該暫定部分道路領域が属するメッシュに対して使用すべき部分道路領域として決定するか又は当該暫定部分道路領域の代わりに当該メッシュに対して使用すべき他の部分道路領域を決定する道路領域決定手段と、
を備えることを特徴とする請求項１又は２に記載の道路領域決定可能プログラム。
【請求項４】
前記第１の評価基準は、各部分道路領域候補に属する、前記地理画像内の画素の画像値に依存する評価基準と、各部分道路領域候補の幾何学的な特徴量に依存する評価基準との両方を含む、
ことを特徴とする請求項３に記載の道路領域決定可能プログラム。
【請求項５】
処理装置により実行される道路領域決定方法であって、
エッジ検出ステップと、領域分割ステップと、部分道路境界直線候補検出ステップと、部分道路領域候補検出ステップと、部分道路領域決定ステップと、道路領域決定ステップ、とを含み、
前記エッジ検出ステップは、地表を上空から撮影して得られ、あらかじめ地理画像記憶手段に記憶された地理画像から複数のエッジを検出して当該複数のエッジを表すエッジ画像を生成し、
前記領域分割ステップは、前記地理画像の存在領域を複数のメッシュに分割し、
前記部分道路境界直線候補検出ステップは、いずれかの道路が通過する複数のメッシュの各々に関して、当該道路の当該メッシュ内に位置する部分道路に対して所定の位置条件を満たす、当該メッシュ内に位置する複数の直線状のエッジ部分を、当該部分道路に対する複数の部分道路境界直線候補として、前記エッジ画像から、かつ、前記道路の中心線を近似的に直線で表す連結された複数の道路ベクトルを指定する、あらかじめ道路ベクトルデータ記憶手段に記憶された道路ベクトルデータに基づいて検出し、
前記部分道路領域候補検出ステップは、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路境界直線候補検出ステップにより検出された前記複数の部分道路境界直線候補から選択された任意の二つからなる複数の組合わせにより定まる複数の領域を、当該道路の当該メッシュ内に位置する前記部分道路の存在領域に対する複数の部分道路領域候補として検出し、
前記部分道路領域決定ステップは、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路境界直線候補検出ステップにより検出された前記複数の部分道路領域候補の各々について、当該部分道路領域候補が当該メッシュ内の前記部分道路の存在領域である妥当性を所定の評価基準に基づいて評価し、前記複数の部分道路領域候補に対する評価結果に基づいて前記複数の部分道路領域候補の一つを当該部分道路の当該メッシュ内の存在領域として決定し、
前記道路領域決定ステップは、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路領域決定ステップで決定された複数の部分道路領域を接続して当該道路の存在領域を決定する、
ことを特徴とする道路領域決定方法。
【請求項６】
前記部分道路境界直線候補検出手段が前記いずれかの道路が通過する前記複数のメッシュの各々に対する前記複数の部分道路境界直線候補が満たすべき前記所定の位置条件は、部分道路境界直線候補は、当該部分道路の近傍にあり、かつ、当該部分道路に対してほぼ平行に位置することである、
ことを特徴とする請求項５に記載の道路領域決定方法。
【請求項７】
前期部分道路領域決定ステップは、
前記いずれかの道路が通過する前記複数のメッシュのそれぞれに対して検出された前記複数の部分道路領域候補の各々について、部分道路領域である妥当性を、それぞれの部分道路領域候補ごとに個別に所定の第１の評価基準に基づいて評価し、前記複数の部分道路領域候補に対する評価結果に基づいて、前記複数の部分道路領域候補の一つを、当該メッシュ内の当該道路の前記部分道路に対する暫定部分道路領域として決定する暫定部分道路領域決定ステップと、
前記いずれかの道路が通過する前記複数のメッシュのそれぞれに対して決定された前記複数の暫定部分道路領域の各々について、前記複数の暫定部分道路領域の相互の位置関係に関係する第２の評価基準に基づいて、部分道路領域としての妥当性を評価し、前記複数の暫定部分道路領域に対する評価結果に基づいて、前記複数の暫定部分道路領域の各々について、当該暫定部分道路領域を当該暫定部分道路領域が属するメッシュに対して使用すべき部分道路領域として決定するか又は当該暫定部分道路領域の代わりに当該メッシュに対して使用すべき他の部分道路領域を決定する道路領域決定ステップと、
を含むことを特徴とする請求項５又は６に記載の道路領域決定方法。
【請求項８】
前記第１の評価基準は、各部分道路領域候補に属する、前記地理画像内の画素の画像値に依存する評価基準と、各部分道路領域候補の幾何学的な特徴量に依存する評価基準との両方を含む、
ことを特徴とする請求項７に記載の道路領域決定方法。
【請求項１】
コンピュータを、エッジ検出手段と、領域分割手段と、部分道路境界直線候補検出手段と、部分道路領域候補検出手段と、部分道路領域決定手段と、道路領域決定手段、として機能させる道路領域決定可能プログラムであって、
前記エッジ検出手段は、地表を上空から撮影して得られ、あらかじめ地理画像記憶手段に記憶された地理画像から複数のエッジを検出して当該複数のエッジを表すエッジ画像を生成し、
前記領域分割手段は、前記地理画像の存在領域を複数のメッシュに分割し、
前記部分道路境界直線候補検出手段は、いずれかの道路が通過する複数のメッシュの各々に関して、当該道路の当該メッシュ内に位置する部分道路に対して所定の位置条件を満たす、当該メッシュ内に位置する複数の直線状のエッジ部分を、当該部分道路に対する複数の部分道路境界直線候補として、前記エッジ画像から、かつ、前記道路の中心線を近似的に直線で表す連結された複数の道路ベクトルを指定する、あらかじめ道路ベクトルデータ記憶手段に記憶された道路ベクトルデータに基づいて検出し、
前記部分道路領域候補検出手段は、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路境界直線候補検出手段により検出された前記複数の部分道路境界直線候補から選択された任意の二つからなる複数の組合わせにより定まる複数の領域を、当該道路の当該メッシュ内に位置する前記部分道路の存在領域に対する複数の部分道路領域候補として検出し、
前記部分道路領域決定手段は、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路境界直線候補検出手段により検出された前記複数の部分道路領域候補の各々について、当該部分道路領域候補が当該メッシュ内の前記部分道路の存在領域である妥当性を所定の評価基準に基づいて評価し、前記複数の部分道路領域候補に対する評価結果に基づいて前記複数の部分道路領域候補の一つを当該部分道路の当該メッシュ内の存在領域として決定し、
前記道路領域決定手段は、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路領域決定手段で決定された複数の部分道路領域を接続して当該道路の存在領域を決定する、
ことを特徴とする道路領域決定可能プログラム。
【請求項２】
前記部分道路境界直線候補検出手段が前記いずれかの道路が通過する前記複数のメッシュの各々に対する前記複数の部分道路境界直線候補が満たすべき前記所定の位置条件は、部分道路境界直線候補は、当該部分道路の近傍にあり、かつ、当該部分道路に対してほぼ平行に位置することである、
ことを特徴とする請求項１に記載の道路領域決定可能プログラム。
【請求項３】
前期部分道路領域決定手段は、
前記いずれかの道路が通過する前記複数のメッシュのそれぞれに対して検出された前記複数の部分道路領域候補の各々について、部分道路領域である妥当性を、それぞれの部分道路領域候補ごとに個別に所定の第１の評価基準に基づいて評価し、前記複数の部分道路領域候補に対する評価結果に基づいて、前記複数の部分道路領域候補の一つを、当該メッシュ内の当該道路の前記部分道路に対する暫定部分道路領域として決定する暫定部分道路領域決定手段と、
前記いずれかの道路が通過する前記複数のメッシュのそれぞれに対して決定された前記複数の暫定部分道路領域の各々について、前記複数の暫定部分道路領域の相互の位置関係に関係する第２の評価基準に基づいて、部分道路領域としての妥当性を評価し、前記複数の暫定部分道路領域に対する評価結果に基づいて、前記複数の暫定部分道路領域の各々について、当該暫定部分道路領域を当該暫定部分道路領域が属するメッシュに対して使用すべき部分道路領域として決定するか又は当該暫定部分道路領域の代わりに当該メッシュに対して使用すべき他の部分道路領域を決定する道路領域決定手段と、
を備えることを特徴とする請求項１又は２に記載の道路領域決定可能プログラム。
【請求項４】
前記第１の評価基準は、各部分道路領域候補に属する、前記地理画像内の画素の画像値に依存する評価基準と、各部分道路領域候補の幾何学的な特徴量に依存する評価基準との両方を含む、
ことを特徴とする請求項３に記載の道路領域決定可能プログラム。
【請求項５】
処理装置により実行される道路領域決定方法であって、
エッジ検出ステップと、領域分割ステップと、部分道路境界直線候補検出ステップと、部分道路領域候補検出ステップと、部分道路領域決定ステップと、道路領域決定ステップ、とを含み、
前記エッジ検出ステップは、地表を上空から撮影して得られ、あらかじめ地理画像記憶手段に記憶された地理画像から複数のエッジを検出して当該複数のエッジを表すエッジ画像を生成し、
前記領域分割ステップは、前記地理画像の存在領域を複数のメッシュに分割し、
前記部分道路境界直線候補検出ステップは、いずれかの道路が通過する複数のメッシュの各々に関して、当該道路の当該メッシュ内に位置する部分道路に対して所定の位置条件を満たす、当該メッシュ内に位置する複数の直線状のエッジ部分を、当該部分道路に対する複数の部分道路境界直線候補として、前記エッジ画像から、かつ、前記道路の中心線を近似的に直線で表す連結された複数の道路ベクトルを指定する、あらかじめ道路ベクトルデータ記憶手段に記憶された道路ベクトルデータに基づいて検出し、
前記部分道路領域候補検出ステップは、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路境界直線候補検出ステップにより検出された前記複数の部分道路境界直線候補から選択された任意の二つからなる複数の組合わせにより定まる複数の領域を、当該道路の当該メッシュ内に位置する前記部分道路の存在領域に対する複数の部分道路領域候補として検出し、
前記部分道路領域決定ステップは、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路境界直線候補検出ステップにより検出された前記複数の部分道路領域候補の各々について、当該部分道路領域候補が当該メッシュ内の前記部分道路の存在領域である妥当性を所定の評価基準に基づいて評価し、前記複数の部分道路領域候補に対する評価結果に基づいて前記複数の部分道路領域候補の一つを当該部分道路の当該メッシュ内の存在領域として決定し、
前記道路領域決定ステップは、前記いずれかの道路が通過する前記複数のメッシュの各々に対して前記部分道路領域決定ステップで決定された複数の部分道路領域を接続して当該道路の存在領域を決定する、
ことを特徴とする道路領域決定方法。
【請求項６】
前記部分道路境界直線候補検出手段が前記いずれかの道路が通過する前記複数のメッシュの各々に対する前記複数の部分道路境界直線候補が満たすべき前記所定の位置条件は、部分道路境界直線候補は、当該部分道路の近傍にあり、かつ、当該部分道路に対してほぼ平行に位置することである、
ことを特徴とする請求項５に記載の道路領域決定方法。
【請求項７】
前期部分道路領域決定ステップは、
前記いずれかの道路が通過する前記複数のメッシュのそれぞれに対して検出された前記複数の部分道路領域候補の各々について、部分道路領域である妥当性を、それぞれの部分道路領域候補ごとに個別に所定の第１の評価基準に基づいて評価し、前記複数の部分道路領域候補に対する評価結果に基づいて、前記複数の部分道路領域候補の一つを、当該メッシュ内の当該道路の前記部分道路に対する暫定部分道路領域として決定する暫定部分道路領域決定ステップと、
前記いずれかの道路が通過する前記複数のメッシュのそれぞれに対して決定された前記複数の暫定部分道路領域の各々について、前記複数の暫定部分道路領域の相互の位置関係に関係する第２の評価基準に基づいて、部分道路領域としての妥当性を評価し、前記複数の暫定部分道路領域に対する評価結果に基づいて、前記複数の暫定部分道路領域の各々について、当該暫定部分道路領域を当該暫定部分道路領域が属するメッシュに対して使用すべき部分道路領域として決定するか又は当該暫定部分道路領域の代わりに当該メッシュに対して使用すべき他の部分道路領域を決定する道路領域決定ステップと、
を含むことを特徴とする請求項５又は６に記載の道路領域決定方法。
【請求項８】
前記第１の評価基準は、各部分道路領域候補に属する、前記地理画像内の画素の画像値に依存する評価基準と、各部分道路領域候補の幾何学的な特徴量に依存する評価基準との両方を含む、
ことを特徴とする請求項７に記載の道路領域決定方法。
【図１】
【図２】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図３】
【図２】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図３】
【公開番号】特開２００６−２３９５８（Ｐ２００６−２３９５８Ａ）
【公開日】平成１８年１月２６日（２００６．１．２６）
【国際特許分類】
【出願番号】特願２００４−２０１０７８（Ｐ２００４−２０１０７８）
【出願日】平成１６年７月７日（２００４．７．７）
【出願人】（０００２３３０５５）日立ソフトウエアエンジニアリング株式会社 (1,610)
【Ｆターム（参考）】
【公開日】平成１８年１月２６日（２００６．１．２６）
【国際特許分類】
【出願日】平成１６年７月７日（２００４．７．７）
【出願人】（０００２３３０５５）日立ソフトウエアエンジニアリング株式会社 (1,610)
【Ｆターム（参考）】
[ Back to top ]