交差点位置抽出方法、交差点位置抽出プログラムおよび交差点位置抽出装置
【課題】交差点情報を抽出するのに要する計算時間を短縮することの可能な交差点位置抽出方法を提供する。
【解決手段】回転角θごとにＴｂ（θ；ｘ，ｙ）をＩ（ｘ，ｙ）の各画素に対してＦＦＴを用いて畳み込むことによりＨ（θ；（ｘ，ｙ））を計算し（Ｓ２０１）、交差点モデルの各分枝の方向角θｉに対応するＨ（θｉ；（ｘ，ｙ））を足し合わせることにより交差点モデルでのＤ（Ｍθ（ｘ，ｙ））を計算し（Ｓ２０２）、各画素において、Ｄ（Ｍθ（ｘ，ｙ））をθに関して微分し、微分値がゼロとなるθの値を求め、その中で最大のＤ（Ｍθ（ｘ，ｙ））をＲ（ｘ，ｙ）として抽出し（Ｓ２０３）、Ｒ（ｘ，ｙ）の極大値を検出し、画像データＩ（ｘ，ｙ）の極大値に対応する位置を交差点位置として抽出する（Ｓ１０４）。
【解決手段】回転角θごとにＴｂ（θ；ｘ，ｙ）をＩ（ｘ，ｙ）の各画素に対してＦＦＴを用いて畳み込むことによりＨ（θ；（ｘ，ｙ））を計算し（Ｓ２０１）、交差点モデルの各分枝の方向角θｉに対応するＨ（θｉ；（ｘ，ｙ））を足し合わせることにより交差点モデルでのＤ（Ｍθ（ｘ，ｙ））を計算し（Ｓ２０２）、各画素において、Ｄ（Ｍθ（ｘ，ｙ））をθに関して微分し、微分値がゼロとなるθの値を求め、その中で最大のＤ（Ｍθ（ｘ，ｙ））をＲ（ｘ，ｙ）として抽出し（Ｓ２０３）、Ｒ（ｘ，ｙ）の極大値を検出し、画像データＩ（ｘ，ｙ）の極大値に対応する位置を交差点位置として抽出する（Ｓ１０４）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、航空画像や衛星画像などの地表面画像から交差点を抽出する交差点抽出方法、交差点抽出プログラムおよび交差点抽出装置に関する。
【背景技術】
【０００２】
紙面からデジタルへの地図媒体の移行により、利用者の目的に合わせて多様かつ詳細な情報を提供することが可能になった。カーナビゲーションシステム、交通情報の管理、防災および都市計画、といったＩＴＳ（Intelligent Transport Systems; 高度交通システム）やＧＩＳ(Geographic Information System; 地理情報システム) のアプリケーションにおいて、デジタル地図は必要不可欠である。
【０００３】
最近では、航空写真に地図情報を重ね合わせる技術や、デジタル地図を３次元でわかりやすく表示する技術が用いられている。これらの技術は、デジタル地図が十分な位置精度を持ち、かつ信頼できる情報であることを前提としている。しかし、現存するデジタル地図は既存の紙地図をトレースしたり、航空写真を測量したりするなど、手作業によって作成されており、コストの面で問題がある。そのため、画像認識技術を用いて紙地図や航空画像からデジタル地図を自動的に作成または更新する技術の実現に期待が高まっている。
【０００４】
航空画像や衛星画像などの地表面画像から道路を抽出する手法は、主に二種類に分類することが可能である。一つは、初期条件を一通り与えるとバッチ処理などで自動的に地表物を認識するフルオートマチック（Full-Automatic）手法であり、もう一つは、オペレータと対話により地表物を抽出する、地図作りの支援ツール的な意味合いを持つセミオートマチック（Semi-Automatic）手法である。もっとも、これらの技術は互いに独立したものではなく、セミオートマチック手法の対話部分を自動化することにより、セミオートマチック手法をフルオートマチック手法にすることができる。
【０００５】
なお、既存の数値地図の情報を利用して、新しい地図を作成する研究も行われている（非特許文献１，２，３）
【０００６】
セミオートマチックな道路抽出手法の代表例であるロードトラッキング（Road Tracking）（非特許文献４，５，６，７）やスネークス（Snakes）（非特許文献８，９，１０）は、初期条件が良ければ複雑な住宅街の画像においても道路を正しく抽出することができる優れた方法である。しかし、これらをフルオートマチック手法に移行する際に、良い初期条件を与える方法がなく、道路を抽出する地域が単純な農地に限られていた（非特許文献１１，１２，１３）。
【０００７】
【非特許文献１】D. Klang, “Automatic detection of changes in road databases using satellite imagery,”Proceedings of International Archives of Photogrammetry and Remote Sensing, vol.32, pp.293-298, 1998.
【非特許文献２】C. Zhang, Updating of Cartographic Road Database, Ph.D thesis, Institute of Geodesy and Photogrammetry, ETH Zurich, 2003.
【非特許文献３】上瀧剛，内村圭一，胡振程，“ネットワーク型active shape models による道路地図の位置精度の向上，” 情報処理学会論文誌，vol.47，pp.3079-3089，2006.
【非特許文献４】M. Fischler, J. Tenenbaum, and H. Wolf, “Detection of roads and linear structures in low resolution aerial images using multi-source knowledge integration techniques,” Defense Advanced Research Projects Agency, pp.87-100, 1979.
【非特許文献５】D. Geman, and B. Jedynak, “An active testing model for tracking roads in satellite images,” IEEE Transaction on Pattern Analysis and Machine Intelligence, vol.18, no.1, pp.1-14, 1996.
【非特許文献６】G. Vosselman, and J. Knecht, “Road tracing by profilematching and kalman filtering,” Proceedings of Automatic Extraction of Man-Made Objects, pp.255-264, 1995.
【非特許文献７】M.N. HuijingZhao, Jun Kumagai, and R. Shibasaki, “Semi-automatic road extraction from high-resolution satellite image,” Photogrammetric Computer Vision, pp.406-411, 2002.
【非特許文献８】M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: Active contour models,” International Journal of Computer Vision, vol.1, no.4, pp.321-331, 1988.
【非特許文献９】P. Fua, and Y. Leclerc, “Model driven edge detection,” Computer Vision, vol.3, no.1, pp.45-56, 1990.
【非特許文献１０】A. Gruen, and H. Li, “Road extraction from aerial and satellite images by dynamic programming,” ISPRS Journal of Photogrammetry and Remote Sensing, vol.50, pp.11-20, 1995.
【非特許文献１１】R. Ruskone, and S. Airault, “Toward an automatic extraction of the road network by local interpretation of the scene,” 46th Photogrammetric Week, pp.147-157, 1997.
【非特許文献１２】A. Baumgartner, W. Eckstein, H. Mayer, C. Heipke, and H. Ebner, “Context-supported road extraction,” Proceedings of Proceedings of Automatic Extraction of Man-Made Objects, pp.299-308, 1997.
【非特許文献１３】I. Laptev, “Road extraction based on snakes and sophisticated line extraction,” Masters Thesis, Computational Vision and AcivePerception Lab, Royal Institute of Technology in Stockholm, Sweden, 1997.
【非特許文献１４】上瀧剛，内村圭一，胡振程，脇阪信治，有田秀昶，“交差点モデルを用いたカラーオルソ航空画像からの道路網構成，” 電子情報通信学会論文誌Ａ，vol.J88-A，pp.164-174，2005.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
ところで、本願発明者らは、上記したロードトラッキングの初期条件としてモデルマッチングにより検出した交差点位置と交差点枝方向とを利用することにより、農地以外の郊外住宅街での道路抽出に成功している（非特許文献１４）。しかし、道路抽出に要する処理時間のほとんどが交差点のモデルマッチングに費やされており、計算時間の面で問題があった。
【０００９】
本発明はかかる問題点に鑑みてなされたもので、その目的は、地表面画像を数値化した画像データから交差点情報を抽出するのに要する計算時間を短縮することの可能な交差点位置抽出方法、交差点位置抽出プログラムおよび交差点位置抽出装置を提供することにある。
【課題を解決するための手段】
【００１０】
本発明による交差点位置抽出方法は、地表面画像を数値化した画像データＩ（ｘ，ｙ）から道路の交差点情報を抽出する交差点抽出装置で実行される方法であって、以下の（Ａ１）〜（Ａ４）の各工程を含むものである。
（Ａ１）交差点枝モデルを交差点枝分解能Δθずつ回転させたときの回転角θ（＝Δθ×ｎ）（０≦ｎ≦（３６０−Δθ）／Δθ）ごとに、交差点枝モデルを数値化したテンプレート値Ｔｂ（θ；ｘ，ｙ）を、地表面画像を数値化した画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴ（Fast Fourier Transform）を用いて畳み込むことにより、回転角θごとの相関画像Ｈ（θ；（ｘ，ｙ））を生成する相関画像生成ステップ
（Ａ２）複数の分枝を有する交差点モデルにおける複数の分枝の方向角θｉに対応する相関画像Ｈ（θｉ；（ｘ，ｙ））を足し合わせることにより、交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算するマッチング値計算ステップ
（Ａ３）各画素において、マッチング値Ｄ（Ｍθ（ｘ，ｙ））をθに関して微分し、微分値がゼロとなるθの値を求め、微分値がゼロとなるθにおけるマッチング値Ｄ（Ｍθ（ｘ，ｙ））の中から最大値を抽出することにより、マッチング値マップＲ（ｘ，ｙ）を作成するマッチング値マップ作成ステップ
（Ａ４）マッチング値マップＲ（ｘ，ｙ）の極大値を検出し、画像データＩ（ｘ，ｙ）の極大値に対応する位置を交差点位置として抽出する交差点位置抽出ステップ
【００１１】
本発明による交差点位置抽出プログラムは、地表面画像を数値化した画像データＩ（ｘ，ｙ）から道路の交差点情報を抽出する交差点抽出装置で実行されるプログラムであって、以下の（Ｂ１）〜（Ｂ４）の各ステップを含むものである。
（Ｂ１）交差点枝モデルを交差点枝分解能Δθずつ回転させたときの回転角θ（＝Δθ×ｎ）（０≦ｎ≦（３６０−Δθ）／Δθ）ごとに、交差点枝モデルを数値化したテンプレート値Ｔｂ（θ；ｘ，ｙ）を、地表面画像を数値化した画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴ（Fast Fourier Transform）を用いて畳み込むことにより、回転角θごとの相関画像Ｈ（θ；（ｘ，ｙ））を生成する相関画像生成ステップ
（Ｂ２）複数の分枝を有する交差点モデルにおける複数の分枝の方向角θｉに対応する相関画像Ｈ（θｉ；（ｘ，ｙ））を足し合わせることにより、交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算するマッチング値計算ステップ
（Ｂ３）各画素において、マッチング値Ｄ（Ｍθ（ｘ，ｙ））をθに関して微分し、微分値がゼロとなるθの値を求め、微分値がゼロとなるθにおけるマッチング値Ｄ（Ｍθ（ｘ，ｙ））の中から最大値を抽出することにより、マッチング値マップＲ（ｘ，ｙ）を作成するマッチング値マップ作成ステップ
（Ｂ４）マッチング値マップＲ（ｘ，ｙ）の極大値を検出し、画像データＩ（ｘ，ｙ）の極大値に対応する位置を交差点位置として抽出する交差点位置抽出ステップ
【００１２】
本発明による交差点位置抽出装置は、以下の（Ｃ１）〜（Ｃ４）の各構成を備えたものである。
（Ｃ１）交差点枝モデルを交差点枝分解能Δθずつ回転させたときの回転角θ（＝Δθ×ｎ）（０≦ｎ≦（３６０−Δθ）／Δθ）ごとに、交差点枝モデルを数値化したテンプレート値Ｔｂ（θ；ｘ，ｙ）を、地表面画像を数値化した画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴ（Fast Fourier Transform）を用いて畳み込むことにより、回転角θごとの相関画像Ｈ（θ；（ｘ，ｙ））を生成する相関画像生成部
（Ｃ２）複数の分枝を有する交差点モデルにおける複数の分枝の方向角θｉに対応する相関画像Ｈ（θｉ；（ｘ，ｙ））を足し合わせることにより、交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算するマッチング値計算部
（Ｃ３）各画素において、マッチング値Ｄ（Ｍθ（ｘ，ｙ））をθに関して微分し、微分値がゼロとなるθの値を求め、微分値がゼロとなるθにおけるマッチング値Ｄ（Ｍθ（ｘ，ｙ））の中から最大値を抽出することにより、マッチング値マップＲ（ｘ，ｙ）を作成するマッチング値マップ計算部
（Ｃ４）マッチング値マップＲ（ｘ，ｙ）の極大値を検出し、画像データＩ（ｘ，ｙ）の極大値に対応する位置を交差点位置として抽出する交差点位置抽出部
【００１３】
本発明による交差点位置抽出方法、交差点位置抽出プログラムおよび交差点位置抽出装置では、回転角θごとに、テンプレート値Ｔｂ（θ；（ｘ，ｙ））を、Ｉ（ｘ，ｙ）の各画素に対してＦＦＴを用いて畳み込むことにより、相関画像Ｈ（θ；（ｘ，ｙ））が生成される。これにより、交差点モデルの各枝のマッチング値Ｄ（Ｍθ（ｘ，ｙ））を事前に計算しておくことができるので、その計算結果から必要な枝のマッチング値Ｄ（Ｍθ（ｘ，ｙ））を抽出し、抽出したマッチング値Ｄ（Ｍθ（ｘ，ｙ））を足し合わせるだけで、交差点モデルのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を作成することができる。
【００１４】
ここで、本発明による交差点位置抽出方法、交差点位置抽出プログラムおよび交差点位置抽出装置において、相関画像Ｈ（θ；（ｘ，ｙ））をθ方向に対してフーリエ級数展開すると共に、所定の次数を超える項を打ち切ったものを足し合わせることにより、交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算することが可能である。また、テンプレート値Ｔｂ（θ；ｘ，ｙ）と、直交基底関数列φｎ（θ）との内積をとることにより導出した基底テンプレートＢｎ（ｘ，ｙ）を画像データＩ（ｘ，ｙ）の各画素に対して畳み込むことにより、フーリエ係数Ａｎ（ｘ，ｙ）を計算したのち、フーリエ係数Ａｎ（ｘ，ｙ）と直交基底関数列φｎ（θ）との内積をとることにより導出したものを足し合わせることにより、交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算することも可能である。
【発明の効果】
【００１５】
本発明による交差点位置抽出方法、交差点位置抽出プログラムおよび交差点位置抽出装置によれば、事前に計算しておいた交差点モデルの各枝のマッチング値Ｄ（Ｍθ（ｘ，ｙ））から必要な枝のマッチング値Ｄ（Ｍθ（ｘ，ｙ））を抽出し、抽出したマッチング値Ｄ（Ｍθ（ｘ，ｙ））を足し合わせるだけで、交差点モデルのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を作成することができるようにしたので、全パターンの交差点モデルとＩ（ｘ，ｙ）とのマッチングを、Ｉ（ｘ，ｙ）の全ての画素に対して直接に行う場合や、各画素で交差点枝モデルを回転させながら、ＦＦＴを用いずにＩ（ｘ，ｙ）と直接マッチングさせる場合と比べて、計算時間を大幅に短縮することができる。
【００１６】
ここで、本発明による交差点位置抽出方法、交差点位置抽出プログラムおよび交差点位置抽出装置において、相関画像Ｈ（θ；（ｘ，ｙ））をθ方向に対してフーリエ級数展開し、次数をαで打ち切ったものを足し合わせることにより、交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算するようにした場合には、データ量をα／（３６０／Δθ）に圧縮することができる。これにより、実用的な容量のメモリを用いて交差点位置を算出することが可能となる。
【００１７】
さらに、テンプレート値Ｔｂ（θ；ｘ，ｙ）と、直交基底関数列φｎ（θ）との内積をとることにより導出した基底テンプレートＢｎ（ｘ，ｙ）を画像データＩ（ｘ，ｙ）の各画素に対して畳み込むことにより、フーリエ係数Ａｎ（ｘ，ｙ）を計算したのち、フーリエ係数Ａｎ（ｘ，ｙ）と直交基底関数列φｎ（θ）との内積をとることにより導出したものを足し合わせることにより、交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算するようにした場合には、α枚の基底テンプレートＢｎ（ｘ，ｙ）をＩ（ｘ，ｙ）の各画素に対して畳み込むだけでよくなる。その結果、（３６０／Δθ）枚の枝テンプレートを畳み込む場合と比べて、畳み込みに要する計算時間をα／（３６０／Δθ）に圧縮することができる。
【発明を実施するための最良の形態】
【００１８】
以下、本発明を実施するための最良の形態について図面を参照して詳細に説明する。
【００１９】
図１は、本発明の一実施の形態に係る交差点抽出装置１の概要構成を表したものである。なお、本発明の一実施の形態に係る交差点抽出方法は、この交差点抽出装置１の動作によって具現化されるものであるから、以下、それらを併せて説明する。
【００２０】
この交差点抽出装置１は、制御部１０、記憶部２０、表示部３０および入力部４０を有している。制御部１０は、プログラムの命令を解釈し、実行するためのもので、例えばＣＰＵ（Central Processing Unit ）を含んで構成されている。記憶部２０は、交差点抽出プログラム２１、道路候補画像データ２２および初期データ２３を記憶している。
【００２１】
ここで、交差点抽出プログラム２１は、交差点抽出のための一連の手順を制御部１０に実行させるためのものである。なお、この一連の手順の詳細については後述する。道路候補画像データ２２は、航空画像や衛星画像などの地表面画像に対して所定の処理（例えば数値化処理）がなされた画像データであり、例えば、地表面画像の各画素に対して、教師つき分類を用いてあらかじめ切り出した道路サンプルとの尤度値を割り当てて、地表面画像をグレースケール化することにより得られる。なお、道路候補画像データ２２は、これ以外の方法を用いて得られた画像データであってもよい。初期データ２３は、交差点抽出プログラム２１を実行する際にあらかじめ設定しておくデータであり、例えば、交差点テンプレート２４、枝テンプレート２５および入力パラメータ２６を含んでいる。
【００２２】
交差点テンプレート２４は、交差点モデルをテンプレート値Ｔ（ｘ，ｙ）で表したものである。交差点モデルは、図２に示したように、交差点Ｃｐを中心として放射状に延在する３本以上の道路（分枝２４Ａ）をモデル化したものであり、モデル内部の画素集合Ｓと、モデル外部の画素集合Ｂとにより構成されている。画素集合Ｓは、数１および図２に示したように、Ｎ（Ｎは３以上の整数）個の矩形枝Ｓ１、Ｓ２、……、Ｓｉ、……、ＳＮからなり、画素集合Ｂは、数２および図２に示したように、矩形枝Ｓ１の外部領域Ｂ１、矩形枝Ｓ２の外部領域Ｂ２、……、矩形枝Ｓｉの外部領域Ｂｉ、……、矩形枝ＳＮの外部領域ＢＮからなる。なお、本実施の形態では、サフィックスｉは、図２に示したように、反時計周りに増加するものとする。
【数１】
【数２】
【００２３】
矩形枝Ｓｉは、図２に示したように、幅（２Ｗ０）、長さＬ０の矩形状となっており、交差点Ｃｐを原点（ｘ０、ｙ０）とするｘｙ座標のｘ軸に対して反時計回りに角度（θｉ＋θ）の方向に延在している。なお、本実施の形態では、角度θの初期値が“０（２π）”となっているものとする。外部領域Ｂｉは、図２に示したように、矩形枝Ｓｉの両側面（矩形枝Ｓｉの延在方向ｖｉと直交する方向の両側面）に接する、幅Ｗ１、長さＬ０の矩形状の領域である。
【００２４】
交差点モデルのテンプレート値Ｔ（ｘ，ｙ）は、数３に示したように、各矩形枝Ｓｉのテンプレート値Ｔ（Ｓｉ；（ｘ，ｙ））と外部領域Ｂｉのテンプレート値Ｔ（Ｂｉ；（ｘ，ｙ））とを足し合せたもののシグマで表される。
【数３】
【００２５】
矩形枝Ｓｉのテンプレート値Ｔ（Ｓｉ；（ｘ，ｙ））は、例えば、数４に示したように、矩形枝Ｓｉの内部の画素において“１”となっており、矩形枝Ｓｉの外部の画素において“０（ゼロ）”となっている。
【数４】
【００２６】
また、外部領域Ｂｉのテンプレート値Ｔ（Ｂｉ；（ｘ，ｙ））は、例えば、数５に示したように、外部領域Ｂｉの内部の画素においてＢｉ（ｕ）となっており、外部領域Ｂｉの外部の画素において“０（ゼロ）”となっている。Ｂｉ（ｕ）は、数６に示したような箱型の関数となっている。
【数５】
【数６】
【００２７】
ここで、数６において、Ｐαはテンプレート値を調整するパラメータであり、Ｈ（ｕ）はステップ関数である。なお、さらに、入力画像のノイズによる影響を低減するために、テンプレート値Ｔ（Ｂｉ；（ｘ，ｙ））に対して、ｕ方向について分散σのガウス関数ｇ（ｕ；σ）を畳みこんでもよい。
【００２８】
なお、本実施の形態では、交差点モデルの種類として、図３（Ａ），（Ｂ）に示したような十字路の交差点モデルや、図４（Ａ），（Ｂ）に示したようなＴ字路の交差点モデル、図５（Ａ），（Ｂ）に示したような三叉路の交差点モデルがあらかじめ設定されており、各交差点モデルにおいて、矩形枝同士のなす角度の異なるモデルが複数設定されている。
【００２９】
枝テンプレート２５は、矩形状の交差点枝モデルをテンプレート値Ｔｂ（ｘ，ｙ）で表したものである。交差点枝モデルは、交差点Ｃｐを中心として放射状に延在する３本以上の道路（分枝２４Ａ）のうちの１本の道路をモデル化したものであり、図６に示したように、モデル内部の画素集合Ｓｂと、モデル外部（モデル周辺部）の画素集合Ｂｂとにより構成されている。画素集合Ｓｂは、幅（２Ｗ０）、長さＬ０の矩形状となっており、交差点Ｃｐを原点（ｘ０、ｙ０）とするｘｙ座標のｘ軸に対して反時計回りに角度（θｂ＋θ）の方向に延在している。なお、本実施の形態では、角度θの初期値が“０（２π）”となっているものとする。画素集合Ｂｂは、画素集合Ｓｂ以外の全ての領域に対応している。
【００３０】
交差点枝モデルのテンプレート値Ｔｂ（ｘ，ｙ）は、数７に示したように、画素集合Ｓｂのテンプレート値Ｔ（Ｓｂ；（ｘ，ｙ））と、画素集合Ｂｂのテンプレート値Ｔ（Ｂｂ；（ｘ，ｙ））とを足し合わせたもので表される。
【数７】
【００３１】
画素集合Ｓｂのテンプレート値Ｔ（Ｓｂ；（ｘ，ｙ））は、例えば、数８に示したように、画素集合Ｓｂの内部の画素において“１”となっており、矩形枝Ｓｉの外部の画素において“０（ゼロ）”となっている。
【数８】
【００３２】
また、画素集合Ｂｂのテンプレート値Ｔ（Ｂｂ；（ｘ，ｙ））は、例えば、数９に示したように、画素集合Ｓｂの両側面（画素集合Ｓｂの延在方向ｖｂと直交する方向の両側面）に接する、幅Ｗ１、長さＬ０の矩形状の領域の内部の画素においてＢｂ（ｕ）となっており、画素集合Ｓｂのうち上記の領域を除く領域の内部の画素において“０（ゼロ）”となっている。Ｂｂ（ｕ）は、数１０に示したような箱型の関数となっている。
【数９】
【数１０】
【００３３】
入力パラメータ２６は、例えば、上記したＷ０、Ｗ１およびＬ０や、後述の交差点枝分解能Δθやフーリエ級数の次数αなどを含んでいる。表示部３０は、例えば、制御部１０におけるプログラムの実行結果（例えば交差点位置）を表示したり、制御部１０におけるプログラムの実行に際して情報入力を支援するための表示をしたりするためのものであり、例えば液晶ディスプレイからなる。入力部４０は、制御部１０におけるプログラムの実行に際して情報を入力するためのものであり、例えばキーボードやマウスからなる。
【００３４】
次に、本実施の形態の交差点抽出装置１の動作について詳細に説明する。図７は、本実施の形態の交差点抽出装置１の交差点抽出プログラム２１における交差点抽出の手順を表したものである。
【００３５】
まず、ユーザによって交差点抽出プログラム２１の起動が要求されると、制御部１０は交差点抽出プログラム２１を記憶部２０から読み出すと共に起動したのち（ステップＳ１０１）、ユーザに対して初期データ２３の入力を要求する（ステップＳ１０２）。制御部１０は、例えば、表示部３０に入力フォームを表示する。なお、初期データ２３の一部または全てがあらかじめ記憶部４０に記憶されている場合には、ユーザによる初期データ２３の入力を省略することも可能である。
【００３６】
次に、ユーザによって初期データ２３が入力されると、制御部１０は初期データ２３に基づいて交差点抽出処理を実行する。制御部１０は、交差点抽出処理において、まず、道路候補画像データ２２（Ｉ（ｘ，ｙ））の全ての画素に対して、交差点テンプレート２４とのマッチングを行う（ステップＳ１０３）。
【００３７】
具体的には、制御部１０は、数１１に示したように、画像データＩ（ｘ，ｙ）と各矩形枝Ｓｉのテンプレート値Ｔ（Ｓｉ；（ｘ，ｙ））との相関ψ（Ｓｉ）を計算すると共に、数１２に示したように、画像データＩ（ｘ，ｙ）と外部領域Ｂｉのテンプレート値Ｔ（Ｂｉ；（ｘ，ｙ））との相関ψ（Ｂｉ）を計算する。さらに、制御部１０は、数１３に示したように、それぞれの画素集合の相関の平均値を足し合わせることにより、マッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算する。このとき、個々の矩形枝Ｓｉのマッチング値（数１４参照）がある閾値ｋよりも大きい場合、つまり、画像データＩ（ｘ，ｙ）とＴ（Ｓｉ；（ｘ，ｙ））との相関が大きい場合にだけ、上記の計算により得られた値をマッチング値Ｄ（Ｍθ（ｘ，ｙ））として採用する。その一方で、少なくとも１つの矩形枝Ｓｉのマッチング値（数１４参照）がある閾値ｋ以下となっている場合には、制御部１０は、相関が小さいと判断して、マッチング値Ｄ（Ｍθ（ｘ，ｙ））を０（ゼロ）とする。次に、制御部１０は、交差点モデルＭ（ｘ，ｙ）を交差点枝分解能Δθずつ３６０度まで回転させたときの回転角θ（＝Δθ×ｎ）（０≦ｎ≦（３６０−Δθ）／Δθ）ごとに、マッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算したのち、数１５に示したように、各画素において、各回転角θのマッチング値Ｄ（Ｍθ（ｘ，ｙ））のうち最大値を抽出し、マッチング値マップＲ（ｘ，ｙ）を作成する。
【数１１】
【数１２】
【数１３】
【数１４】
【数１５】
【００３８】
例えば、画像データＩ（ｘ，ｙ）として図８に示したような２値画像のテストデータを、テンプレート値Ｔ（ｘ，ｙ）として図４（Ｂ）に示したようなＴ字路の交差点モデルをそれぞれ用意し、個々の矩形枝Ｓｉの半分未満の画素がテストデータの“０（ゼロ）”（黒）の画素と重なり合うときにマッチング値Ｄ（Ｍθ（ｘ，ｙ））を“０（ゼロ）”とするように閾値ｋを調整した場合には、図９（Ａ），（Ｂ）に示したようなマッチング値マップＲ（ｘ，ｙ）の分布が得られる。
【００３９】
なお、図８のモデルには、交差点テンプレート２４（図２）における画素集合Ｓの幅と同じ幅の道路Ｒ１，Ｒ２が交差する交差点Ｃ１と、画素集合Ｓの幅と同じ幅の道路Ｒ１と画素集合Ｓの幅と異なる幅の道路Ｒ３とが交差する交差点Ｃ２とが含まれており、さらに、道路Ｒ１の付近に道路Ｒ１と同じ色の建物Ｃ３が含まれている。また、図９（Ａ）は、Ｒ（ｘ，ｙ）の２次元分布を表しており、図９（Ｂ）は、図９（Ａ）のＡ−Ａ線における分布を表している。
【００４０】
図９（Ａ），（Ｂ）から、図８の交差点Ｃ１，Ｃ２に対応する位置にマッチング値マップＲ（ｘ，ｙ）の鋭いピークが得られ、図８の矩形状の地表物Ｃ３に対応する位置およびその近傍においてマッチング値マップＲ（ｘ，ｙ）がゼロもしくはほとんどゼロとなっていることがわかる。従って、上記の手順により、交差点の存在しない位置に交差点が存在すると誤認することなく、交差点位置を精確に抽出することができる。
【００４１】
ところで、上記した数１３は、非線形であり、線形フィルタ処理により一度の計算でマッチング値Ｄ（Ｍθ（ｘ，ｙ））を求めることが容易ではない。そこで、本実施の形態では、数１３と同等の結果を得るために、以下に示す効率的なマッチング方法を用いる。
【００４２】
最初に、数１６に示したように、交差点枝モデルを交差点枝分解能Δθ（図１０では５度）ずつ３６０度まで回転させたときの回転角θ（＝Δθ×ｎ）（０≦ｎ≦（３６０−Δθ）／Δθ）ごとに、図６に示したような枝テンプレート２５のテンプレート値Ｔｂ（θ；（ｘ，ｙ））を、画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴを用いて畳み込むことにより、回転角θごとの相関画像Ｈ（θ；（ｘ，ｙ））を生成する（ステップＳ２０１、図７参照）。
【数１６】
【００４３】
なお、数１６を模式的に表すと、図１０のようになる。この図には、図１０の中段に例示したような回転角θ（＝０°，５°，…，３５５°）ごとのテンプレート値Ｔｂ（θ；（ｘ，ｙ））を、図１０の上段に例示したような画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴを用いて畳み込むと、図１０の下段に例示したような回転角θごとの相関画像Ｈ（θ；（ｘ，ｙ））が生成される様子が示されている。
【００４４】
次に、各種交差点モデルの分枝の方向角θｉに対応する相関画像Ｈ（θｉ；（ｘ，ｙ））を足し合わせることにより、各種交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算する（ステップＳ２０２）。例えば、図４（Ｂ）に示したような回転角θのＴ字路の交差点モデルのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を、数１７に示したようにして求めることができる。なお、ある画素におけるマッチング値Ｄ（Ｍθ（ｘ，ｙ））は、図１１に示したようなグラフになる。
【数１７】
【００４５】
次に、各画素において、マッチング値Ｄ（Ｍθ（ｘ，ｙ））をθに関して微分し、そのときにゼロ交差する（微分値がゼロとなる）θの値を求め、ゼロ交差するθが一つの場合にはそのθにおけるマッチング値Ｄ（Ｍθ（ｘ，ｙ））を抽出し、ゼロ交差するθが複数ある場合にはその中で最大のマッチング値Ｄ（Ｍθ（ｘ，ｙ））を抽出し、マッチング値マップＲ（ｘ，ｙ）を作成する（ステップＳ２０３）。ただし、ゼロ交差する位置において、足し合わせる前の各枝のマッチング値（例えば、図４（Ｂ）に示したようなＴ字路の交差点モデルでは、Ｈ（θ；（ｘ，ｙ））、Ｈ（θ＋π；（ｘ，ｙ））、Ｈ（θ＋３π／２；（ｘ，ｙ）））のどれか１つでも所定の閾値以下となっているときには、マッチング値Ｄ（Ｍθ（ｘ，ｙ））を０（ゼロ）とする。このようにして、効率的なマッチングが行われる。
【００４６】
次に、上記のようにしてマッチングを行ったのち、マッチングの結果を利用して、交差点情報を抽出する（ステップＳ１０４）。具体的には、上記のようにして数１６を用いて求められた相関画像Ｈ（θ；（ｘ，ｙ））を利用して得られたマッチング値マップＲ（ｘ，ｙ）の極大値を検出し、画像データＩ（ｘ，ｙ）の極大値に対応する位置を交差点位置として抽出する。極大値の検出には、例えば、所定の画素（注目画素）を中心とする所定の半径の円形マスクを想定し、その円形マスク内において注目画素が円形マスク内において最大値をとる場合には、その注目画素の位置を交差点位置として抽出する。このようにして、本実施の形態では交差点位置が抽出される。
【００４７】
本実施の形態では、回転角θごとに、テンプレート値Ｔｂ（θ；（ｘ，ｙ））を、画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴを用いて畳み込むことにより、相関画像Ｈ（θ；（ｘ，ｙ））が生成される。これにより、交差点モデルの各枝のマッチング値を事前に計算しておくことができるので、その計算結果から必要な枝のマッチング値を抽出し、抽出したマッチング値を足し合わせるだけで、交差点モデルのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を作成することができる。その結果、交差点テンプレート２４に含まれる全パターンの交差点モデルと画像データＩ（ｘ，ｙ）とのマッチングを、画像データＩ（ｘ，ｙ）の全ての画素に対して直接に行う場合や、各画素で交差点枝テンプレート２５を回転させながら、ＦＦＴを用いずに画像データＩ（ｘ，ｙ）と直接マッチングさせる場合と比べて、計算時間を大幅に短縮することができる。
【００４８】
ところで、上記の方法では、事前計算に際して、（３６０／Δθ）個の画像データＩ（ｘ，ｙ）のサイズと同じサイズのメモリが必要となるので、記憶部３０のメモリ容量を大きくしておくことが必要となる。例えば、交差点枝分解能Δθを３度に設定して相関画像Ｈ（θ；（ｘ，ｙ））を計算すると、１画素あたり１２０枚の画像が必要となる。図８のような小さな画像では問題ないが、航空画像や衛星画像のような大きなサイズの画像を扱う場合には問題となる。
【００４９】
そこで、数１８に示したように、相関画像Ｈ（θ；（ｘ，ｙ））をθ方向に対してフーリエ級数展開（福田礼次郎著、“理工系の基礎数学 フーリエ解析”岩波書店 １９９７年出版、参照）すると共に、高次（例えば３０を超える次数）の項を打ち切ったものを足し合わせる。そして、交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算することによりデータ量の圧縮を行うことが好ましい。数１８において、φｉ（θ）は、直交基底関数列であり、数１９のように表される。
【数１８】
【数１９】
【００５０】
ここで、αは、フーリエ級数の次数である。また、Ａｎ（ｘ，ｙ）は、相関画像Ｈ（θ；（ｘ，ｙ））の画素ごとのフーリエ係数であり、画像として表される。各画素におけるフーリエ係数Ａｎ（ｘ，ｙ）は、相関画像Ｈ（θ；（ｘ，ｙ））と、直交基底関数列｛φｉ（θ）｝との内積により導出される。
【００５１】
例えば、まず、ｉ＝０（θ＝０）のときに得られる相関画像Ｈ（０；（ｘ，ｙ））に対して、フーリエ係数Ａｎ（ｘ，ｙ）を全ての画素に対して計算する（図１２（Ａ）〜（Ｄ）参照）。次に、ｉ＝１（θ＝２π／β）（β＝（３６０／Δθ））のときに得られる相関画像Ｈ（２π／β；（ｘ，ｙ））に対して、同様に各フーリエ係数Ａｎ（ｘ，ｙ）を全ての画素に対して計算する。つまり、同図の破線で囲まれた計算ステップを右方向にずらしていくことになる。最終的に、ｉ＝β−１（θ＝２π（β−１）／β）まで同様の計算を行うことにより、α枚のフーリエ係数Ａｎ（ｘ，ｙ）画像を完成させることができる。
【００５２】
図１３（Ａ）〜（Ｃ）は、ある画素における相関画像Ｈ（θ；（ｘ，ｙ））をフーリエ級数展開した結果を表したものである。ここで、図１３（Ａ）はα＝６０のときの結果を、図１３（Ｂ）はα＝４０のときの結果を、図１３（Ｃ）はα＝３０のときの結果をそれぞれ表したものである。図１３（Ｄ）は、数１６を用いたときの結果（フーリエ級数展開前の結果）を表したものである。なお、図１３（Ａ）〜（Ｄ）の全てにおいて、交差点枝分解能Δθを３度とした。図１３（Ａ）〜（Ｄ）から、次数αを小さくした場合であっても、相関画像Ｈ（θ；（ｘ，ｙ））の形状を近似することができることがわかる。
【００５３】
このように、フーリエ級数展開を用いて、データ量をα／βに圧縮することができるので、実用的な容量のメモリを用いて交差点位置を算出することが可能となる。しかし、フーリエ係数画像の生成には多くの処理時間を要する。α枚のフーリエ係数画像を生成するためには、β枚の枝テンプレートを畳み込む必要があるからである。この畳み込みには、β回のＦＦＴと逆ＦＦＴが必要となる。また、βを十分に大きくとらないと、フーリエ係数からもとのマッチング値を復元する際に，数値的な誤差の影響で振動が生じる可能性がある。そこで、画像データＩ（ｘ，ｙ）から直接、フーリエ係数画像を求めることにより、相関画像Ｈ（θ；（ｘ，ｙ））を生成することがより好ましい。以下にその生成方法について説明する。
【００５４】
数１６に示した式に対して、θ方向に沿った直交基底関数列φｎ（θ）（ｎ＝０，１，２…）でのフーリエ級数展開を行うと、数２０に示したようになる。ここで、＜ ， ＞θは、θに関する内積演算を表す。内積演算および畳み込み演算は共に積分演算であるので、順序を交換することができ、数２０から数２１を得ることができる。なお、Ｂｎ（ｘ，ｙ）は、数２２に示したように、交差点枝モデルのテンプレート値Ｔｂ（θ；ｘ，ｙ）と、直交基底関数列φｎ（θ）との内積で計算される基底テンプレートとなる。
【数２０】
【数２１】
【数２２】
【００５５】
数２２を用いて事前に計算しておいた基底テンプレートＢｎ（ｘ，ｙ）を画像データＩ（ｘ，ｙ）の各画素に対して畳み込むことにより、直ちにフーリエ係数Ａｎ（ｘ，ｙ）を得ることができることが数２１からわかる。基底テンプレートＢｎ（ｘ，ｙ）は、交差点枝モデルのテンプレート値Ｔｂ（θ；ｘ，ｙ）だけに依存していることから、画像データＩ（ｘ，ｙ）に依存しない形で基底テンプレートＢｎ（ｘ，ｙ）を計算することができる。そのため、α枚の基底テンプレートＢｎ（ｘ，ｙ）を一度計算しておけば、後は任意の画像データＩ（ｘ，ｙ）にそのまま用いることができる．つまり、基底テンプレートＢｎ（ｘ，ｙ）を作成する際に、十分大きなβを用いて事前に計算しておくことが可能である。
【００５６】
このように、本実施の形態において、画像データＩ（ｘ，ｙ）から直接、フーリエ係数Ａｎ（ｘ，ｙ）を求めるようにした場合には、α枚の基底テンプレートＢｎ（ｘ，ｙ）を画像データＩ（ｘ，ｙ）の各画素に対して畳み込むだけでよくなる。その結果、β枚の枝テンプレートを畳み込む場合と比べて、畳み込みに要する計算時間をα／βに圧縮することができる。
【００５７】
[実施例]
上記実施の形態において示した各手法の抽出位置精度および方向分解能の誤差を比較実験により求めた。
【００５８】
一つ目の比較実験では、人工画像および航空画像として画素数が５１２×５１２のＲＧＢカラー画像のものを用意し、航空画像の各画素に対して、教師つき分類を用いてあらかじめ切り出した道路サンプルとの尤度値を割り当てて、航空画像をグレースケール化したものを航空画像の画像データＩ（ｘ，ｙ）とした。一方、人工画像については、航空画像と同一箇所の縮尺１／２５００の数値地図データから作成したものを画像データＩ（ｘ，ｙ）とした。そして、数１６を利用して導出した交差点位置および交差点方向をリファレンス値とし、このリファレンス値と、数２１を利用して導出した交差点位置および交差点方向との差（位置のＲＭＳ（Root Mean Square；平均二乗偏差）誤差、方向の絶対誤差）を計算した。その結果を表１，２に示した。なお、表１に人工画像における結果を示し、表２に航空画像における結果を示した。また、表１，２には、打ち切り次数αを２０，３０，６０とした場合の結果をそれぞれ示した。また、本比較実験では、Intel（登録商標）Core2 Duo1.6GHzのＣＰＵと、２Ｇバイトのメモリを搭載した計算機を使用した。
【表１】
【表２】
【００５９】
表１，２から、位置のＲＭＳ誤差および方向の絶対誤差の双方において、誤差が十分に小さく、実用に耐えることがわかった。
【００６０】
二つ目の比較では、一つ目の比較実験と同じものを画像データＩ（ｘ，ｙ）とした。そして、各画素で交差点枝テンプレート２５を回転させながらＦＦＴを用いずに、画像データＩ（ｘ，ｙ）と直接マッチングさせる手法（手法１）と、数１６を利用してマッチングを行う手法（手法２）と、数１８を利用してマッチングを行う手法（手法３）と、数２１を利用してマッチングを行う手法（手法４）とにおける計算の所要時間と、所要メモリとを算出した。手法１，２，４についての結果を表３に示した。なお、表３には、手法４において、次数αを２０、３０、６０に変えた場合の結果も示した。
【表３】
【００６１】
表３から、手法２，４の所要時間が、手法１の所要時間よりも大幅に小さくなっていることがわかった。また、手法４の所要メモリが、手法１の所要メモリと大差ないことがわかった。
【００６２】
三つ目の比較では、人工画像および航空画像として画素数が１０２４×１０２４のＲＧＢカラー画像をそれぞれ４枚（シーン１〜４）用意し、航空画像の各画素に対して、教師つき分類を用いてあらかじめ切り出した道路サンプルとの尤度値を割り当てて、航空画像をグレースケール化したものを航空画像の画像データＩ（ｘ，ｙ）とした。一方、人工画像については、航空画像と同一箇所の縮尺１／２５００の数値地図データから作成したものを画像データＩ（ｘ，ｙ）とした。なお、航空画像の対称エリアは典型的な３叉路および十字路交差点を多く含む郊外住宅街である。人工画像での抽出実験は、画像データＩ（ｘ，ｙ）において道路領域と背景領域が完全に分離されている場合を想定したものであり、手法４の性能限界を知ることができる。そして、抽出した交差点位置と真の交差点位置との中心位置のずれが４．５ｍ以内で各交差点枝の方向差が全て２０度以下であれば、交差点位置を精確に抽出できた（正解）と判定し、抽出率（（正解個数／交差点の全数）×１００）と、正しさ（（正解個数／抽出個数）×１００）とを算出した。また、その結果を表４，５，６，７に示した。なお、表４に人工画像における結果（全てのシーンの合計値）を示し、表５に航空画像における結果（全てのシーンの合計値）を示した。また、表６には、典型的なＴ字路交差点が多く、建物の影が少ないシーン（シーン１、図１４参照）における航空画像での結果を示し、表７には、シーン１と比べて道路幅が狭く、道路が互いに直角に交わる交差点が少ない複雑なシーン（シーン３、図１５参照）における航空画像での結果を示した。
【表４】
【表５】
【表６】
【表７】
【００６３】
表４から、合計２０９個の交差点に対して、次数α＝３０以上のときに１９５個の交差点を正しく抽出することができたことがわかる。交差点抽出の失敗（交差点を検出できなかった場合と、検出した交差点位置が大きくずれていた場合）は、交差点モデルの形状と人工画像上の交差点の形状とが互いに異なる場合に生じていたが、それでも９割以上の交差点を正しく抽出することができたことから、交差点の形状モデルとして本モデルが有効であることがわかった。また、抽出率および正さが次数α＝３０で収束したことから、α＝３０程度にまでαを小さくした場合であっても、近似精度を高く維持することができることがわかった。
【００６４】
また、表５から、抽出率および正さの双方において、数値が人工画像の場合よりも悪いことがわかった。これは、航空画像に多くのノイズが含まれていることに起因していると思われる。もっとも、抽出率および正さは次数α＝３０あたりで収束したことから、人工画像であるか航空画像であるかに拘わらず、次数α＝３０程度にまでαを小さくした場合であっても、近似精度を高く維持することができることがわかった。
【００６５】
また、表６から、８割近くの交差点を正しく抽出することができたことがわかる。また、表７から、抽出率が表６の場合よりも悪いものの、７割程度の交差点を正しく抽出することができたことがわかる。なお、詳細な原因分析により、道路の色が特徴抽出での教師つき分類で用いる道路サンプルの色と異なっていたり、影により道路領域の特徴を抽出することができなかったり等の前処理部分での失敗に起因して、交差点抽出を失敗していることがわかったが、前処理の善し悪しに拘わらず、抽出率および正さがα＝４０あたり収束したことから、典型的な郊外住宅街の画像に対して、手法４を適用する場合には、近似精度を比較的高く維持しつつ、次数α＝４０程度にまでαを小さくすることができることがわかった。
【００６６】
なお、手法４における計算時間については、次数α＝４０で画像サイズが５１２×５１２ピクセルの大きさで約１２秒であり，１ｋｍ平方メートルあたり１９２秒程度となる。例えば、北九州市の面積が５００ｋｍ２なので、単純に計算して約２７時間となる。そして、地図の更新および作成サイクルが年に２〜３回程度だとすると、この計算時間は十分実用的であるといえる。また、手法３では、高速化のために多くのメモリを費やすが、必要なメモリ量は１０２４×１０２４ピクセルのサイズで約５００Ｍバイトとなり、メモリに関しても十分実用範囲に収まっているといえる。
【００６７】
以上、実施の形態およびその変形例ならびに実施例を挙げて本発明を説明したが、本発明はこれに限定されるものではなく、種々の変形が可能である。
【００６８】
例えば、上記実施の形態では、交差点抽出プログラム２１が制御部１０にロードされることにより、上記実施の形態の交差点抽出方法が実行される場合について説明したが、図１６に示したように、交差点抽出プログラム２１を制御部１０にロードする代わりに、図７のステップＳ２０１を実行する相関画像生成部１０Ａと、図７のステップＳ２０２を実行するマッチング値計算部１０Ｂと、図７のステップＳ２０３を実行するマッチング値マップ計算部１０Ｃと、図７のステップＳ１０６を実行する交差点位置抽出部１０Ｄとをデバイス（ハードウェア）として制御部１０内に備えていてもよい。
【図面の簡単な説明】
【００６９】
【図１】本発明の一実施の形態に係る交差点位置抽出装置の概要構成図である。
【図２】交差点テンプレートの概念図である。
【図３】図２の交差点テンプレートの一構成例について説明するための概念図である。
【図４】図２の交差点テンプレートの他の構成例について説明するための概念図である。
【図５】図２の交差点テンプレートのその他の構成例について説明するための概念図である。
【図６】枝テンプレートの概念図である。
【図７】交差点位置の抽出手順について説明するための流れ図である。
【図８】道路候補画像データについて説明するための概念図である。
【図９】マッチング値マップについて説明するための概念図である。
【図１０】数１６の模式図である。
【図１１】マッチング値について説明するための概念図である。
【図１２】フーリエ係数について説明するための概念図である。
【図１３】打ち切り次数について説明するための概念図である。
【図１４】比較実験に用いた一の航空画像の画像データである。
【図１５】比較実験に用いた他の航空画像の画像データである。
【図１６】図１の交差点位置抽出装置の一変形例の概要構成図である。
【符号の説明】
【００７０】
１…交差点抽出装置、１０…制御部、１０Ａ…相関画像生成部、１０Ｂ…マッチング値計算部１０Ｂ、１０Ｃ…マッチング値マップ計算部、１０Ｄ…交差点位置抽出部、２０…記憶部、２１…交差点検出プログラム、２２…道路候補画像データ、２３…初期データ、２４…交差点テンプレート、２５…枝テンプレート、３０…表示部、４０…入力部、Ｃ１，Ｃ２…交差点、Ｃ３…建物、Ｒ１，Ｒ２，Ｒ３…道路。
【技術分野】
【０００１】
本発明は、航空画像や衛星画像などの地表面画像から交差点を抽出する交差点抽出方法、交差点抽出プログラムおよび交差点抽出装置に関する。
【背景技術】
【０００２】
紙面からデジタルへの地図媒体の移行により、利用者の目的に合わせて多様かつ詳細な情報を提供することが可能になった。カーナビゲーションシステム、交通情報の管理、防災および都市計画、といったＩＴＳ（Intelligent Transport Systems; 高度交通システム）やＧＩＳ(Geographic Information System; 地理情報システム) のアプリケーションにおいて、デジタル地図は必要不可欠である。
【０００３】
最近では、航空写真に地図情報を重ね合わせる技術や、デジタル地図を３次元でわかりやすく表示する技術が用いられている。これらの技術は、デジタル地図が十分な位置精度を持ち、かつ信頼できる情報であることを前提としている。しかし、現存するデジタル地図は既存の紙地図をトレースしたり、航空写真を測量したりするなど、手作業によって作成されており、コストの面で問題がある。そのため、画像認識技術を用いて紙地図や航空画像からデジタル地図を自動的に作成または更新する技術の実現に期待が高まっている。
【０００４】
航空画像や衛星画像などの地表面画像から道路を抽出する手法は、主に二種類に分類することが可能である。一つは、初期条件を一通り与えるとバッチ処理などで自動的に地表物を認識するフルオートマチック（Full-Automatic）手法であり、もう一つは、オペレータと対話により地表物を抽出する、地図作りの支援ツール的な意味合いを持つセミオートマチック（Semi-Automatic）手法である。もっとも、これらの技術は互いに独立したものではなく、セミオートマチック手法の対話部分を自動化することにより、セミオートマチック手法をフルオートマチック手法にすることができる。
【０００５】
なお、既存の数値地図の情報を利用して、新しい地図を作成する研究も行われている（非特許文献１，２，３）
【０００６】
セミオートマチックな道路抽出手法の代表例であるロードトラッキング（Road Tracking）（非特許文献４，５，６，７）やスネークス（Snakes）（非特許文献８，９，１０）は、初期条件が良ければ複雑な住宅街の画像においても道路を正しく抽出することができる優れた方法である。しかし、これらをフルオートマチック手法に移行する際に、良い初期条件を与える方法がなく、道路を抽出する地域が単純な農地に限られていた（非特許文献１１，１２，１３）。
【０００７】
【非特許文献１】D. Klang, “Automatic detection of changes in road databases using satellite imagery,”Proceedings of International Archives of Photogrammetry and Remote Sensing, vol.32, pp.293-298, 1998.
【非特許文献２】C. Zhang, Updating of Cartographic Road Database, Ph.D thesis, Institute of Geodesy and Photogrammetry, ETH Zurich, 2003.
【非特許文献３】上瀧剛，内村圭一，胡振程，“ネットワーク型active shape models による道路地図の位置精度の向上，” 情報処理学会論文誌，vol.47，pp.3079-3089，2006.
【非特許文献４】M. Fischler, J. Tenenbaum, and H. Wolf, “Detection of roads and linear structures in low resolution aerial images using multi-source knowledge integration techniques,” Defense Advanced Research Projects Agency, pp.87-100, 1979.
【非特許文献５】D. Geman, and B. Jedynak, “An active testing model for tracking roads in satellite images,” IEEE Transaction on Pattern Analysis and Machine Intelligence, vol.18, no.1, pp.1-14, 1996.
【非特許文献６】G. Vosselman, and J. Knecht, “Road tracing by profilematching and kalman filtering,” Proceedings of Automatic Extraction of Man-Made Objects, pp.255-264, 1995.
【非特許文献７】M.N. HuijingZhao, Jun Kumagai, and R. Shibasaki, “Semi-automatic road extraction from high-resolution satellite image,” Photogrammetric Computer Vision, pp.406-411, 2002.
【非特許文献８】M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: Active contour models,” International Journal of Computer Vision, vol.1, no.4, pp.321-331, 1988.
【非特許文献９】P. Fua, and Y. Leclerc, “Model driven edge detection,” Computer Vision, vol.3, no.1, pp.45-56, 1990.
【非特許文献１０】A. Gruen, and H. Li, “Road extraction from aerial and satellite images by dynamic programming,” ISPRS Journal of Photogrammetry and Remote Sensing, vol.50, pp.11-20, 1995.
【非特許文献１１】R. Ruskone, and S. Airault, “Toward an automatic extraction of the road network by local interpretation of the scene,” 46th Photogrammetric Week, pp.147-157, 1997.
【非特許文献１２】A. Baumgartner, W. Eckstein, H. Mayer, C. Heipke, and H. Ebner, “Context-supported road extraction,” Proceedings of Proceedings of Automatic Extraction of Man-Made Objects, pp.299-308, 1997.
【非特許文献１３】I. Laptev, “Road extraction based on snakes and sophisticated line extraction,” Masters Thesis, Computational Vision and AcivePerception Lab, Royal Institute of Technology in Stockholm, Sweden, 1997.
【非特許文献１４】上瀧剛，内村圭一，胡振程，脇阪信治，有田秀昶，“交差点モデルを用いたカラーオルソ航空画像からの道路網構成，” 電子情報通信学会論文誌Ａ，vol.J88-A，pp.164-174，2005.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
ところで、本願発明者らは、上記したロードトラッキングの初期条件としてモデルマッチングにより検出した交差点位置と交差点枝方向とを利用することにより、農地以外の郊外住宅街での道路抽出に成功している（非特許文献１４）。しかし、道路抽出に要する処理時間のほとんどが交差点のモデルマッチングに費やされており、計算時間の面で問題があった。
【０００９】
本発明はかかる問題点に鑑みてなされたもので、その目的は、地表面画像を数値化した画像データから交差点情報を抽出するのに要する計算時間を短縮することの可能な交差点位置抽出方法、交差点位置抽出プログラムおよび交差点位置抽出装置を提供することにある。
【課題を解決するための手段】
【００１０】
本発明による交差点位置抽出方法は、地表面画像を数値化した画像データＩ（ｘ，ｙ）から道路の交差点情報を抽出する交差点抽出装置で実行される方法であって、以下の（Ａ１）〜（Ａ４）の各工程を含むものである。
（Ａ１）交差点枝モデルを交差点枝分解能Δθずつ回転させたときの回転角θ（＝Δθ×ｎ）（０≦ｎ≦（３６０−Δθ）／Δθ）ごとに、交差点枝モデルを数値化したテンプレート値Ｔｂ（θ；ｘ，ｙ）を、地表面画像を数値化した画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴ（Fast Fourier Transform）を用いて畳み込むことにより、回転角θごとの相関画像Ｈ（θ；（ｘ，ｙ））を生成する相関画像生成ステップ
（Ａ２）複数の分枝を有する交差点モデルにおける複数の分枝の方向角θｉに対応する相関画像Ｈ（θｉ；（ｘ，ｙ））を足し合わせることにより、交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算するマッチング値計算ステップ
（Ａ３）各画素において、マッチング値Ｄ（Ｍθ（ｘ，ｙ））をθに関して微分し、微分値がゼロとなるθの値を求め、微分値がゼロとなるθにおけるマッチング値Ｄ（Ｍθ（ｘ，ｙ））の中から最大値を抽出することにより、マッチング値マップＲ（ｘ，ｙ）を作成するマッチング値マップ作成ステップ
（Ａ４）マッチング値マップＲ（ｘ，ｙ）の極大値を検出し、画像データＩ（ｘ，ｙ）の極大値に対応する位置を交差点位置として抽出する交差点位置抽出ステップ
【００１１】
本発明による交差点位置抽出プログラムは、地表面画像を数値化した画像データＩ（ｘ，ｙ）から道路の交差点情報を抽出する交差点抽出装置で実行されるプログラムであって、以下の（Ｂ１）〜（Ｂ４）の各ステップを含むものである。
（Ｂ１）交差点枝モデルを交差点枝分解能Δθずつ回転させたときの回転角θ（＝Δθ×ｎ）（０≦ｎ≦（３６０−Δθ）／Δθ）ごとに、交差点枝モデルを数値化したテンプレート値Ｔｂ（θ；ｘ，ｙ）を、地表面画像を数値化した画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴ（Fast Fourier Transform）を用いて畳み込むことにより、回転角θごとの相関画像Ｈ（θ；（ｘ，ｙ））を生成する相関画像生成ステップ
（Ｂ２）複数の分枝を有する交差点モデルにおける複数の分枝の方向角θｉに対応する相関画像Ｈ（θｉ；（ｘ，ｙ））を足し合わせることにより、交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算するマッチング値計算ステップ
（Ｂ３）各画素において、マッチング値Ｄ（Ｍθ（ｘ，ｙ））をθに関して微分し、微分値がゼロとなるθの値を求め、微分値がゼロとなるθにおけるマッチング値Ｄ（Ｍθ（ｘ，ｙ））の中から最大値を抽出することにより、マッチング値マップＲ（ｘ，ｙ）を作成するマッチング値マップ作成ステップ
（Ｂ４）マッチング値マップＲ（ｘ，ｙ）の極大値を検出し、画像データＩ（ｘ，ｙ）の極大値に対応する位置を交差点位置として抽出する交差点位置抽出ステップ
【００１２】
本発明による交差点位置抽出装置は、以下の（Ｃ１）〜（Ｃ４）の各構成を備えたものである。
（Ｃ１）交差点枝モデルを交差点枝分解能Δθずつ回転させたときの回転角θ（＝Δθ×ｎ）（０≦ｎ≦（３６０−Δθ）／Δθ）ごとに、交差点枝モデルを数値化したテンプレート値Ｔｂ（θ；ｘ，ｙ）を、地表面画像を数値化した画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴ（Fast Fourier Transform）を用いて畳み込むことにより、回転角θごとの相関画像Ｈ（θ；（ｘ，ｙ））を生成する相関画像生成部
（Ｃ２）複数の分枝を有する交差点モデルにおける複数の分枝の方向角θｉに対応する相関画像Ｈ（θｉ；（ｘ，ｙ））を足し合わせることにより、交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算するマッチング値計算部
（Ｃ３）各画素において、マッチング値Ｄ（Ｍθ（ｘ，ｙ））をθに関して微分し、微分値がゼロとなるθの値を求め、微分値がゼロとなるθにおけるマッチング値Ｄ（Ｍθ（ｘ，ｙ））の中から最大値を抽出することにより、マッチング値マップＲ（ｘ，ｙ）を作成するマッチング値マップ計算部
（Ｃ４）マッチング値マップＲ（ｘ，ｙ）の極大値を検出し、画像データＩ（ｘ，ｙ）の極大値に対応する位置を交差点位置として抽出する交差点位置抽出部
【００１３】
本発明による交差点位置抽出方法、交差点位置抽出プログラムおよび交差点位置抽出装置では、回転角θごとに、テンプレート値Ｔｂ（θ；（ｘ，ｙ））を、Ｉ（ｘ，ｙ）の各画素に対してＦＦＴを用いて畳み込むことにより、相関画像Ｈ（θ；（ｘ，ｙ））が生成される。これにより、交差点モデルの各枝のマッチング値Ｄ（Ｍθ（ｘ，ｙ））を事前に計算しておくことができるので、その計算結果から必要な枝のマッチング値Ｄ（Ｍθ（ｘ，ｙ））を抽出し、抽出したマッチング値Ｄ（Ｍθ（ｘ，ｙ））を足し合わせるだけで、交差点モデルのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を作成することができる。
【００１４】
ここで、本発明による交差点位置抽出方法、交差点位置抽出プログラムおよび交差点位置抽出装置において、相関画像Ｈ（θ；（ｘ，ｙ））をθ方向に対してフーリエ級数展開すると共に、所定の次数を超える項を打ち切ったものを足し合わせることにより、交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算することが可能である。また、テンプレート値Ｔｂ（θ；ｘ，ｙ）と、直交基底関数列φｎ（θ）との内積をとることにより導出した基底テンプレートＢｎ（ｘ，ｙ）を画像データＩ（ｘ，ｙ）の各画素に対して畳み込むことにより、フーリエ係数Ａｎ（ｘ，ｙ）を計算したのち、フーリエ係数Ａｎ（ｘ，ｙ）と直交基底関数列φｎ（θ）との内積をとることにより導出したものを足し合わせることにより、交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算することも可能である。
【発明の効果】
【００１５】
本発明による交差点位置抽出方法、交差点位置抽出プログラムおよび交差点位置抽出装置によれば、事前に計算しておいた交差点モデルの各枝のマッチング値Ｄ（Ｍθ（ｘ，ｙ））から必要な枝のマッチング値Ｄ（Ｍθ（ｘ，ｙ））を抽出し、抽出したマッチング値Ｄ（Ｍθ（ｘ，ｙ））を足し合わせるだけで、交差点モデルのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を作成することができるようにしたので、全パターンの交差点モデルとＩ（ｘ，ｙ）とのマッチングを、Ｉ（ｘ，ｙ）の全ての画素に対して直接に行う場合や、各画素で交差点枝モデルを回転させながら、ＦＦＴを用いずにＩ（ｘ，ｙ）と直接マッチングさせる場合と比べて、計算時間を大幅に短縮することができる。
【００１６】
ここで、本発明による交差点位置抽出方法、交差点位置抽出プログラムおよび交差点位置抽出装置において、相関画像Ｈ（θ；（ｘ，ｙ））をθ方向に対してフーリエ級数展開し、次数をαで打ち切ったものを足し合わせることにより、交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算するようにした場合には、データ量をα／（３６０／Δθ）に圧縮することができる。これにより、実用的な容量のメモリを用いて交差点位置を算出することが可能となる。
【００１７】
さらに、テンプレート値Ｔｂ（θ；ｘ，ｙ）と、直交基底関数列φｎ（θ）との内積をとることにより導出した基底テンプレートＢｎ（ｘ，ｙ）を画像データＩ（ｘ，ｙ）の各画素に対して畳み込むことにより、フーリエ係数Ａｎ（ｘ，ｙ）を計算したのち、フーリエ係数Ａｎ（ｘ，ｙ）と直交基底関数列φｎ（θ）との内積をとることにより導出したものを足し合わせることにより、交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算するようにした場合には、α枚の基底テンプレートＢｎ（ｘ，ｙ）をＩ（ｘ，ｙ）の各画素に対して畳み込むだけでよくなる。その結果、（３６０／Δθ）枚の枝テンプレートを畳み込む場合と比べて、畳み込みに要する計算時間をα／（３６０／Δθ）に圧縮することができる。
【発明を実施するための最良の形態】
【００１８】
以下、本発明を実施するための最良の形態について図面を参照して詳細に説明する。
【００１９】
図１は、本発明の一実施の形態に係る交差点抽出装置１の概要構成を表したものである。なお、本発明の一実施の形態に係る交差点抽出方法は、この交差点抽出装置１の動作によって具現化されるものであるから、以下、それらを併せて説明する。
【００２０】
この交差点抽出装置１は、制御部１０、記憶部２０、表示部３０および入力部４０を有している。制御部１０は、プログラムの命令を解釈し、実行するためのもので、例えばＣＰＵ（Central Processing Unit ）を含んで構成されている。記憶部２０は、交差点抽出プログラム２１、道路候補画像データ２２および初期データ２３を記憶している。
【００２１】
ここで、交差点抽出プログラム２１は、交差点抽出のための一連の手順を制御部１０に実行させるためのものである。なお、この一連の手順の詳細については後述する。道路候補画像データ２２は、航空画像や衛星画像などの地表面画像に対して所定の処理（例えば数値化処理）がなされた画像データであり、例えば、地表面画像の各画素に対して、教師つき分類を用いてあらかじめ切り出した道路サンプルとの尤度値を割り当てて、地表面画像をグレースケール化することにより得られる。なお、道路候補画像データ２２は、これ以外の方法を用いて得られた画像データであってもよい。初期データ２３は、交差点抽出プログラム２１を実行する際にあらかじめ設定しておくデータであり、例えば、交差点テンプレート２４、枝テンプレート２５および入力パラメータ２６を含んでいる。
【００２２】
交差点テンプレート２４は、交差点モデルをテンプレート値Ｔ（ｘ，ｙ）で表したものである。交差点モデルは、図２に示したように、交差点Ｃｐを中心として放射状に延在する３本以上の道路（分枝２４Ａ）をモデル化したものであり、モデル内部の画素集合Ｓと、モデル外部の画素集合Ｂとにより構成されている。画素集合Ｓは、数１および図２に示したように、Ｎ（Ｎは３以上の整数）個の矩形枝Ｓ１、Ｓ２、……、Ｓｉ、……、ＳＮからなり、画素集合Ｂは、数２および図２に示したように、矩形枝Ｓ１の外部領域Ｂ１、矩形枝Ｓ２の外部領域Ｂ２、……、矩形枝Ｓｉの外部領域Ｂｉ、……、矩形枝ＳＮの外部領域ＢＮからなる。なお、本実施の形態では、サフィックスｉは、図２に示したように、反時計周りに増加するものとする。
【数１】
【数２】
【００２３】
矩形枝Ｓｉは、図２に示したように、幅（２Ｗ０）、長さＬ０の矩形状となっており、交差点Ｃｐを原点（ｘ０、ｙ０）とするｘｙ座標のｘ軸に対して反時計回りに角度（θｉ＋θ）の方向に延在している。なお、本実施の形態では、角度θの初期値が“０（２π）”となっているものとする。外部領域Ｂｉは、図２に示したように、矩形枝Ｓｉの両側面（矩形枝Ｓｉの延在方向ｖｉと直交する方向の両側面）に接する、幅Ｗ１、長さＬ０の矩形状の領域である。
【００２４】
交差点モデルのテンプレート値Ｔ（ｘ，ｙ）は、数３に示したように、各矩形枝Ｓｉのテンプレート値Ｔ（Ｓｉ；（ｘ，ｙ））と外部領域Ｂｉのテンプレート値Ｔ（Ｂｉ；（ｘ，ｙ））とを足し合せたもののシグマで表される。
【数３】
【００２５】
矩形枝Ｓｉのテンプレート値Ｔ（Ｓｉ；（ｘ，ｙ））は、例えば、数４に示したように、矩形枝Ｓｉの内部の画素において“１”となっており、矩形枝Ｓｉの外部の画素において“０（ゼロ）”となっている。
【数４】
【００２６】
また、外部領域Ｂｉのテンプレート値Ｔ（Ｂｉ；（ｘ，ｙ））は、例えば、数５に示したように、外部領域Ｂｉの内部の画素においてＢｉ（ｕ）となっており、外部領域Ｂｉの外部の画素において“０（ゼロ）”となっている。Ｂｉ（ｕ）は、数６に示したような箱型の関数となっている。
【数５】
【数６】
【００２７】
ここで、数６において、Ｐαはテンプレート値を調整するパラメータであり、Ｈ（ｕ）はステップ関数である。なお、さらに、入力画像のノイズによる影響を低減するために、テンプレート値Ｔ（Ｂｉ；（ｘ，ｙ））に対して、ｕ方向について分散σのガウス関数ｇ（ｕ；σ）を畳みこんでもよい。
【００２８】
なお、本実施の形態では、交差点モデルの種類として、図３（Ａ），（Ｂ）に示したような十字路の交差点モデルや、図４（Ａ），（Ｂ）に示したようなＴ字路の交差点モデル、図５（Ａ），（Ｂ）に示したような三叉路の交差点モデルがあらかじめ設定されており、各交差点モデルにおいて、矩形枝同士のなす角度の異なるモデルが複数設定されている。
【００２９】
枝テンプレート２５は、矩形状の交差点枝モデルをテンプレート値Ｔｂ（ｘ，ｙ）で表したものである。交差点枝モデルは、交差点Ｃｐを中心として放射状に延在する３本以上の道路（分枝２４Ａ）のうちの１本の道路をモデル化したものであり、図６に示したように、モデル内部の画素集合Ｓｂと、モデル外部（モデル周辺部）の画素集合Ｂｂとにより構成されている。画素集合Ｓｂは、幅（２Ｗ０）、長さＬ０の矩形状となっており、交差点Ｃｐを原点（ｘ０、ｙ０）とするｘｙ座標のｘ軸に対して反時計回りに角度（θｂ＋θ）の方向に延在している。なお、本実施の形態では、角度θの初期値が“０（２π）”となっているものとする。画素集合Ｂｂは、画素集合Ｓｂ以外の全ての領域に対応している。
【００３０】
交差点枝モデルのテンプレート値Ｔｂ（ｘ，ｙ）は、数７に示したように、画素集合Ｓｂのテンプレート値Ｔ（Ｓｂ；（ｘ，ｙ））と、画素集合Ｂｂのテンプレート値Ｔ（Ｂｂ；（ｘ，ｙ））とを足し合わせたもので表される。
【数７】
【００３１】
画素集合Ｓｂのテンプレート値Ｔ（Ｓｂ；（ｘ，ｙ））は、例えば、数８に示したように、画素集合Ｓｂの内部の画素において“１”となっており、矩形枝Ｓｉの外部の画素において“０（ゼロ）”となっている。
【数８】
【００３２】
また、画素集合Ｂｂのテンプレート値Ｔ（Ｂｂ；（ｘ，ｙ））は、例えば、数９に示したように、画素集合Ｓｂの両側面（画素集合Ｓｂの延在方向ｖｂと直交する方向の両側面）に接する、幅Ｗ１、長さＬ０の矩形状の領域の内部の画素においてＢｂ（ｕ）となっており、画素集合Ｓｂのうち上記の領域を除く領域の内部の画素において“０（ゼロ）”となっている。Ｂｂ（ｕ）は、数１０に示したような箱型の関数となっている。
【数９】
【数１０】
【００３３】
入力パラメータ２６は、例えば、上記したＷ０、Ｗ１およびＬ０や、後述の交差点枝分解能Δθやフーリエ級数の次数αなどを含んでいる。表示部３０は、例えば、制御部１０におけるプログラムの実行結果（例えば交差点位置）を表示したり、制御部１０におけるプログラムの実行に際して情報入力を支援するための表示をしたりするためのものであり、例えば液晶ディスプレイからなる。入力部４０は、制御部１０におけるプログラムの実行に際して情報を入力するためのものであり、例えばキーボードやマウスからなる。
【００３４】
次に、本実施の形態の交差点抽出装置１の動作について詳細に説明する。図７は、本実施の形態の交差点抽出装置１の交差点抽出プログラム２１における交差点抽出の手順を表したものである。
【００３５】
まず、ユーザによって交差点抽出プログラム２１の起動が要求されると、制御部１０は交差点抽出プログラム２１を記憶部２０から読み出すと共に起動したのち（ステップＳ１０１）、ユーザに対して初期データ２３の入力を要求する（ステップＳ１０２）。制御部１０は、例えば、表示部３０に入力フォームを表示する。なお、初期データ２３の一部または全てがあらかじめ記憶部４０に記憶されている場合には、ユーザによる初期データ２３の入力を省略することも可能である。
【００３６】
次に、ユーザによって初期データ２３が入力されると、制御部１０は初期データ２３に基づいて交差点抽出処理を実行する。制御部１０は、交差点抽出処理において、まず、道路候補画像データ２２（Ｉ（ｘ，ｙ））の全ての画素に対して、交差点テンプレート２４とのマッチングを行う（ステップＳ１０３）。
【００３７】
具体的には、制御部１０は、数１１に示したように、画像データＩ（ｘ，ｙ）と各矩形枝Ｓｉのテンプレート値Ｔ（Ｓｉ；（ｘ，ｙ））との相関ψ（Ｓｉ）を計算すると共に、数１２に示したように、画像データＩ（ｘ，ｙ）と外部領域Ｂｉのテンプレート値Ｔ（Ｂｉ；（ｘ，ｙ））との相関ψ（Ｂｉ）を計算する。さらに、制御部１０は、数１３に示したように、それぞれの画素集合の相関の平均値を足し合わせることにより、マッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算する。このとき、個々の矩形枝Ｓｉのマッチング値（数１４参照）がある閾値ｋよりも大きい場合、つまり、画像データＩ（ｘ，ｙ）とＴ（Ｓｉ；（ｘ，ｙ））との相関が大きい場合にだけ、上記の計算により得られた値をマッチング値Ｄ（Ｍθ（ｘ，ｙ））として採用する。その一方で、少なくとも１つの矩形枝Ｓｉのマッチング値（数１４参照）がある閾値ｋ以下となっている場合には、制御部１０は、相関が小さいと判断して、マッチング値Ｄ（Ｍθ（ｘ，ｙ））を０（ゼロ）とする。次に、制御部１０は、交差点モデルＭ（ｘ，ｙ）を交差点枝分解能Δθずつ３６０度まで回転させたときの回転角θ（＝Δθ×ｎ）（０≦ｎ≦（３６０−Δθ）／Δθ）ごとに、マッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算したのち、数１５に示したように、各画素において、各回転角θのマッチング値Ｄ（Ｍθ（ｘ，ｙ））のうち最大値を抽出し、マッチング値マップＲ（ｘ，ｙ）を作成する。
【数１１】
【数１２】
【数１３】
【数１４】
【数１５】
【００３８】
例えば、画像データＩ（ｘ，ｙ）として図８に示したような２値画像のテストデータを、テンプレート値Ｔ（ｘ，ｙ）として図４（Ｂ）に示したようなＴ字路の交差点モデルをそれぞれ用意し、個々の矩形枝Ｓｉの半分未満の画素がテストデータの“０（ゼロ）”（黒）の画素と重なり合うときにマッチング値Ｄ（Ｍθ（ｘ，ｙ））を“０（ゼロ）”とするように閾値ｋを調整した場合には、図９（Ａ），（Ｂ）に示したようなマッチング値マップＲ（ｘ，ｙ）の分布が得られる。
【００３９】
なお、図８のモデルには、交差点テンプレート２４（図２）における画素集合Ｓの幅と同じ幅の道路Ｒ１，Ｒ２が交差する交差点Ｃ１と、画素集合Ｓの幅と同じ幅の道路Ｒ１と画素集合Ｓの幅と異なる幅の道路Ｒ３とが交差する交差点Ｃ２とが含まれており、さらに、道路Ｒ１の付近に道路Ｒ１と同じ色の建物Ｃ３が含まれている。また、図９（Ａ）は、Ｒ（ｘ，ｙ）の２次元分布を表しており、図９（Ｂ）は、図９（Ａ）のＡ−Ａ線における分布を表している。
【００４０】
図９（Ａ），（Ｂ）から、図８の交差点Ｃ１，Ｃ２に対応する位置にマッチング値マップＲ（ｘ，ｙ）の鋭いピークが得られ、図８の矩形状の地表物Ｃ３に対応する位置およびその近傍においてマッチング値マップＲ（ｘ，ｙ）がゼロもしくはほとんどゼロとなっていることがわかる。従って、上記の手順により、交差点の存在しない位置に交差点が存在すると誤認することなく、交差点位置を精確に抽出することができる。
【００４１】
ところで、上記した数１３は、非線形であり、線形フィルタ処理により一度の計算でマッチング値Ｄ（Ｍθ（ｘ，ｙ））を求めることが容易ではない。そこで、本実施の形態では、数１３と同等の結果を得るために、以下に示す効率的なマッチング方法を用いる。
【００４２】
最初に、数１６に示したように、交差点枝モデルを交差点枝分解能Δθ（図１０では５度）ずつ３６０度まで回転させたときの回転角θ（＝Δθ×ｎ）（０≦ｎ≦（３６０−Δθ）／Δθ）ごとに、図６に示したような枝テンプレート２５のテンプレート値Ｔｂ（θ；（ｘ，ｙ））を、画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴを用いて畳み込むことにより、回転角θごとの相関画像Ｈ（θ；（ｘ，ｙ））を生成する（ステップＳ２０１、図７参照）。
【数１６】
【００４３】
なお、数１６を模式的に表すと、図１０のようになる。この図には、図１０の中段に例示したような回転角θ（＝０°，５°，…，３５５°）ごとのテンプレート値Ｔｂ（θ；（ｘ，ｙ））を、図１０の上段に例示したような画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴを用いて畳み込むと、図１０の下段に例示したような回転角θごとの相関画像Ｈ（θ；（ｘ，ｙ））が生成される様子が示されている。
【００４４】
次に、各種交差点モデルの分枝の方向角θｉに対応する相関画像Ｈ（θｉ；（ｘ，ｙ））を足し合わせることにより、各種交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算する（ステップＳ２０２）。例えば、図４（Ｂ）に示したような回転角θのＴ字路の交差点モデルのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を、数１７に示したようにして求めることができる。なお、ある画素におけるマッチング値Ｄ（Ｍθ（ｘ，ｙ））は、図１１に示したようなグラフになる。
【数１７】
【００４５】
次に、各画素において、マッチング値Ｄ（Ｍθ（ｘ，ｙ））をθに関して微分し、そのときにゼロ交差する（微分値がゼロとなる）θの値を求め、ゼロ交差するθが一つの場合にはそのθにおけるマッチング値Ｄ（Ｍθ（ｘ，ｙ））を抽出し、ゼロ交差するθが複数ある場合にはその中で最大のマッチング値Ｄ（Ｍθ（ｘ，ｙ））を抽出し、マッチング値マップＲ（ｘ，ｙ）を作成する（ステップＳ２０３）。ただし、ゼロ交差する位置において、足し合わせる前の各枝のマッチング値（例えば、図４（Ｂ）に示したようなＴ字路の交差点モデルでは、Ｈ（θ；（ｘ，ｙ））、Ｈ（θ＋π；（ｘ，ｙ））、Ｈ（θ＋３π／２；（ｘ，ｙ）））のどれか１つでも所定の閾値以下となっているときには、マッチング値Ｄ（Ｍθ（ｘ，ｙ））を０（ゼロ）とする。このようにして、効率的なマッチングが行われる。
【００４６】
次に、上記のようにしてマッチングを行ったのち、マッチングの結果を利用して、交差点情報を抽出する（ステップＳ１０４）。具体的には、上記のようにして数１６を用いて求められた相関画像Ｈ（θ；（ｘ，ｙ））を利用して得られたマッチング値マップＲ（ｘ，ｙ）の極大値を検出し、画像データＩ（ｘ，ｙ）の極大値に対応する位置を交差点位置として抽出する。極大値の検出には、例えば、所定の画素（注目画素）を中心とする所定の半径の円形マスクを想定し、その円形マスク内において注目画素が円形マスク内において最大値をとる場合には、その注目画素の位置を交差点位置として抽出する。このようにして、本実施の形態では交差点位置が抽出される。
【００４７】
本実施の形態では、回転角θごとに、テンプレート値Ｔｂ（θ；（ｘ，ｙ））を、画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴを用いて畳み込むことにより、相関画像Ｈ（θ；（ｘ，ｙ））が生成される。これにより、交差点モデルの各枝のマッチング値を事前に計算しておくことができるので、その計算結果から必要な枝のマッチング値を抽出し、抽出したマッチング値を足し合わせるだけで、交差点モデルのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を作成することができる。その結果、交差点テンプレート２４に含まれる全パターンの交差点モデルと画像データＩ（ｘ，ｙ）とのマッチングを、画像データＩ（ｘ，ｙ）の全ての画素に対して直接に行う場合や、各画素で交差点枝テンプレート２５を回転させながら、ＦＦＴを用いずに画像データＩ（ｘ，ｙ）と直接マッチングさせる場合と比べて、計算時間を大幅に短縮することができる。
【００４８】
ところで、上記の方法では、事前計算に際して、（３６０／Δθ）個の画像データＩ（ｘ，ｙ）のサイズと同じサイズのメモリが必要となるので、記憶部３０のメモリ容量を大きくしておくことが必要となる。例えば、交差点枝分解能Δθを３度に設定して相関画像Ｈ（θ；（ｘ，ｙ））を計算すると、１画素あたり１２０枚の画像が必要となる。図８のような小さな画像では問題ないが、航空画像や衛星画像のような大きなサイズの画像を扱う場合には問題となる。
【００４９】
そこで、数１８に示したように、相関画像Ｈ（θ；（ｘ，ｙ））をθ方向に対してフーリエ級数展開（福田礼次郎著、“理工系の基礎数学 フーリエ解析”岩波書店 １９９７年出版、参照）すると共に、高次（例えば３０を超える次数）の項を打ち切ったものを足し合わせる。そして、交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算することによりデータ量の圧縮を行うことが好ましい。数１８において、φｉ（θ）は、直交基底関数列であり、数１９のように表される。
【数１８】
【数１９】
【００５０】
ここで、αは、フーリエ級数の次数である。また、Ａｎ（ｘ，ｙ）は、相関画像Ｈ（θ；（ｘ，ｙ））の画素ごとのフーリエ係数であり、画像として表される。各画素におけるフーリエ係数Ａｎ（ｘ，ｙ）は、相関画像Ｈ（θ；（ｘ，ｙ））と、直交基底関数列｛φｉ（θ）｝との内積により導出される。
【００５１】
例えば、まず、ｉ＝０（θ＝０）のときに得られる相関画像Ｈ（０；（ｘ，ｙ））に対して、フーリエ係数Ａｎ（ｘ，ｙ）を全ての画素に対して計算する（図１２（Ａ）〜（Ｄ）参照）。次に、ｉ＝１（θ＝２π／β）（β＝（３６０／Δθ））のときに得られる相関画像Ｈ（２π／β；（ｘ，ｙ））に対して、同様に各フーリエ係数Ａｎ（ｘ，ｙ）を全ての画素に対して計算する。つまり、同図の破線で囲まれた計算ステップを右方向にずらしていくことになる。最終的に、ｉ＝β−１（θ＝２π（β−１）／β）まで同様の計算を行うことにより、α枚のフーリエ係数Ａｎ（ｘ，ｙ）画像を完成させることができる。
【００５２】
図１３（Ａ）〜（Ｃ）は、ある画素における相関画像Ｈ（θ；（ｘ，ｙ））をフーリエ級数展開した結果を表したものである。ここで、図１３（Ａ）はα＝６０のときの結果を、図１３（Ｂ）はα＝４０のときの結果を、図１３（Ｃ）はα＝３０のときの結果をそれぞれ表したものである。図１３（Ｄ）は、数１６を用いたときの結果（フーリエ級数展開前の結果）を表したものである。なお、図１３（Ａ）〜（Ｄ）の全てにおいて、交差点枝分解能Δθを３度とした。図１３（Ａ）〜（Ｄ）から、次数αを小さくした場合であっても、相関画像Ｈ（θ；（ｘ，ｙ））の形状を近似することができることがわかる。
【００５３】
このように、フーリエ級数展開を用いて、データ量をα／βに圧縮することができるので、実用的な容量のメモリを用いて交差点位置を算出することが可能となる。しかし、フーリエ係数画像の生成には多くの処理時間を要する。α枚のフーリエ係数画像を生成するためには、β枚の枝テンプレートを畳み込む必要があるからである。この畳み込みには、β回のＦＦＴと逆ＦＦＴが必要となる。また、βを十分に大きくとらないと、フーリエ係数からもとのマッチング値を復元する際に，数値的な誤差の影響で振動が生じる可能性がある。そこで、画像データＩ（ｘ，ｙ）から直接、フーリエ係数画像を求めることにより、相関画像Ｈ（θ；（ｘ，ｙ））を生成することがより好ましい。以下にその生成方法について説明する。
【００５４】
数１６に示した式に対して、θ方向に沿った直交基底関数列φｎ（θ）（ｎ＝０，１，２…）でのフーリエ級数展開を行うと、数２０に示したようになる。ここで、＜ ， ＞θは、θに関する内積演算を表す。内積演算および畳み込み演算は共に積分演算であるので、順序を交換することができ、数２０から数２１を得ることができる。なお、Ｂｎ（ｘ，ｙ）は、数２２に示したように、交差点枝モデルのテンプレート値Ｔｂ（θ；ｘ，ｙ）と、直交基底関数列φｎ（θ）との内積で計算される基底テンプレートとなる。
【数２０】
【数２１】
【数２２】
【００５５】
数２２を用いて事前に計算しておいた基底テンプレートＢｎ（ｘ，ｙ）を画像データＩ（ｘ，ｙ）の各画素に対して畳み込むことにより、直ちにフーリエ係数Ａｎ（ｘ，ｙ）を得ることができることが数２１からわかる。基底テンプレートＢｎ（ｘ，ｙ）は、交差点枝モデルのテンプレート値Ｔｂ（θ；ｘ，ｙ）だけに依存していることから、画像データＩ（ｘ，ｙ）に依存しない形で基底テンプレートＢｎ（ｘ，ｙ）を計算することができる。そのため、α枚の基底テンプレートＢｎ（ｘ，ｙ）を一度計算しておけば、後は任意の画像データＩ（ｘ，ｙ）にそのまま用いることができる．つまり、基底テンプレートＢｎ（ｘ，ｙ）を作成する際に、十分大きなβを用いて事前に計算しておくことが可能である。
【００５６】
このように、本実施の形態において、画像データＩ（ｘ，ｙ）から直接、フーリエ係数Ａｎ（ｘ，ｙ）を求めるようにした場合には、α枚の基底テンプレートＢｎ（ｘ，ｙ）を画像データＩ（ｘ，ｙ）の各画素に対して畳み込むだけでよくなる。その結果、β枚の枝テンプレートを畳み込む場合と比べて、畳み込みに要する計算時間をα／βに圧縮することができる。
【００５７】
[実施例]
上記実施の形態において示した各手法の抽出位置精度および方向分解能の誤差を比較実験により求めた。
【００５８】
一つ目の比較実験では、人工画像および航空画像として画素数が５１２×５１２のＲＧＢカラー画像のものを用意し、航空画像の各画素に対して、教師つき分類を用いてあらかじめ切り出した道路サンプルとの尤度値を割り当てて、航空画像をグレースケール化したものを航空画像の画像データＩ（ｘ，ｙ）とした。一方、人工画像については、航空画像と同一箇所の縮尺１／２５００の数値地図データから作成したものを画像データＩ（ｘ，ｙ）とした。そして、数１６を利用して導出した交差点位置および交差点方向をリファレンス値とし、このリファレンス値と、数２１を利用して導出した交差点位置および交差点方向との差（位置のＲＭＳ（Root Mean Square；平均二乗偏差）誤差、方向の絶対誤差）を計算した。その結果を表１，２に示した。なお、表１に人工画像における結果を示し、表２に航空画像における結果を示した。また、表１，２には、打ち切り次数αを２０，３０，６０とした場合の結果をそれぞれ示した。また、本比較実験では、Intel（登録商標）Core2 Duo1.6GHzのＣＰＵと、２Ｇバイトのメモリを搭載した計算機を使用した。
【表１】
【表２】
【００５９】
表１，２から、位置のＲＭＳ誤差および方向の絶対誤差の双方において、誤差が十分に小さく、実用に耐えることがわかった。
【００６０】
二つ目の比較では、一つ目の比較実験と同じものを画像データＩ（ｘ，ｙ）とした。そして、各画素で交差点枝テンプレート２５を回転させながらＦＦＴを用いずに、画像データＩ（ｘ，ｙ）と直接マッチングさせる手法（手法１）と、数１６を利用してマッチングを行う手法（手法２）と、数１８を利用してマッチングを行う手法（手法３）と、数２１を利用してマッチングを行う手法（手法４）とにおける計算の所要時間と、所要メモリとを算出した。手法１，２，４についての結果を表３に示した。なお、表３には、手法４において、次数αを２０、３０、６０に変えた場合の結果も示した。
【表３】
【００６１】
表３から、手法２，４の所要時間が、手法１の所要時間よりも大幅に小さくなっていることがわかった。また、手法４の所要メモリが、手法１の所要メモリと大差ないことがわかった。
【００６２】
三つ目の比較では、人工画像および航空画像として画素数が１０２４×１０２４のＲＧＢカラー画像をそれぞれ４枚（シーン１〜４）用意し、航空画像の各画素に対して、教師つき分類を用いてあらかじめ切り出した道路サンプルとの尤度値を割り当てて、航空画像をグレースケール化したものを航空画像の画像データＩ（ｘ，ｙ）とした。一方、人工画像については、航空画像と同一箇所の縮尺１／２５００の数値地図データから作成したものを画像データＩ（ｘ，ｙ）とした。なお、航空画像の対称エリアは典型的な３叉路および十字路交差点を多く含む郊外住宅街である。人工画像での抽出実験は、画像データＩ（ｘ，ｙ）において道路領域と背景領域が完全に分離されている場合を想定したものであり、手法４の性能限界を知ることができる。そして、抽出した交差点位置と真の交差点位置との中心位置のずれが４．５ｍ以内で各交差点枝の方向差が全て２０度以下であれば、交差点位置を精確に抽出できた（正解）と判定し、抽出率（（正解個数／交差点の全数）×１００）と、正しさ（（正解個数／抽出個数）×１００）とを算出した。また、その結果を表４，５，６，７に示した。なお、表４に人工画像における結果（全てのシーンの合計値）を示し、表５に航空画像における結果（全てのシーンの合計値）を示した。また、表６には、典型的なＴ字路交差点が多く、建物の影が少ないシーン（シーン１、図１４参照）における航空画像での結果を示し、表７には、シーン１と比べて道路幅が狭く、道路が互いに直角に交わる交差点が少ない複雑なシーン（シーン３、図１５参照）における航空画像での結果を示した。
【表４】
【表５】
【表６】
【表７】
【００６３】
表４から、合計２０９個の交差点に対して、次数α＝３０以上のときに１９５個の交差点を正しく抽出することができたことがわかる。交差点抽出の失敗（交差点を検出できなかった場合と、検出した交差点位置が大きくずれていた場合）は、交差点モデルの形状と人工画像上の交差点の形状とが互いに異なる場合に生じていたが、それでも９割以上の交差点を正しく抽出することができたことから、交差点の形状モデルとして本モデルが有効であることがわかった。また、抽出率および正さが次数α＝３０で収束したことから、α＝３０程度にまでαを小さくした場合であっても、近似精度を高く維持することができることがわかった。
【００６４】
また、表５から、抽出率および正さの双方において、数値が人工画像の場合よりも悪いことがわかった。これは、航空画像に多くのノイズが含まれていることに起因していると思われる。もっとも、抽出率および正さは次数α＝３０あたりで収束したことから、人工画像であるか航空画像であるかに拘わらず、次数α＝３０程度にまでαを小さくした場合であっても、近似精度を高く維持することができることがわかった。
【００６５】
また、表６から、８割近くの交差点を正しく抽出することができたことがわかる。また、表７から、抽出率が表６の場合よりも悪いものの、７割程度の交差点を正しく抽出することができたことがわかる。なお、詳細な原因分析により、道路の色が特徴抽出での教師つき分類で用いる道路サンプルの色と異なっていたり、影により道路領域の特徴を抽出することができなかったり等の前処理部分での失敗に起因して、交差点抽出を失敗していることがわかったが、前処理の善し悪しに拘わらず、抽出率および正さがα＝４０あたり収束したことから、典型的な郊外住宅街の画像に対して、手法４を適用する場合には、近似精度を比較的高く維持しつつ、次数α＝４０程度にまでαを小さくすることができることがわかった。
【００６６】
なお、手法４における計算時間については、次数α＝４０で画像サイズが５１２×５１２ピクセルの大きさで約１２秒であり，１ｋｍ平方メートルあたり１９２秒程度となる。例えば、北九州市の面積が５００ｋｍ２なので、単純に計算して約２７時間となる。そして、地図の更新および作成サイクルが年に２〜３回程度だとすると、この計算時間は十分実用的であるといえる。また、手法３では、高速化のために多くのメモリを費やすが、必要なメモリ量は１０２４×１０２４ピクセルのサイズで約５００Ｍバイトとなり、メモリに関しても十分実用範囲に収まっているといえる。
【００６７】
以上、実施の形態およびその変形例ならびに実施例を挙げて本発明を説明したが、本発明はこれに限定されるものではなく、種々の変形が可能である。
【００６８】
例えば、上記実施の形態では、交差点抽出プログラム２１が制御部１０にロードされることにより、上記実施の形態の交差点抽出方法が実行される場合について説明したが、図１６に示したように、交差点抽出プログラム２１を制御部１０にロードする代わりに、図７のステップＳ２０１を実行する相関画像生成部１０Ａと、図７のステップＳ２０２を実行するマッチング値計算部１０Ｂと、図７のステップＳ２０３を実行するマッチング値マップ計算部１０Ｃと、図７のステップＳ１０６を実行する交差点位置抽出部１０Ｄとをデバイス（ハードウェア）として制御部１０内に備えていてもよい。
【図面の簡単な説明】
【００６９】
【図１】本発明の一実施の形態に係る交差点位置抽出装置の概要構成図である。
【図２】交差点テンプレートの概念図である。
【図３】図２の交差点テンプレートの一構成例について説明するための概念図である。
【図４】図２の交差点テンプレートの他の構成例について説明するための概念図である。
【図５】図２の交差点テンプレートのその他の構成例について説明するための概念図である。
【図６】枝テンプレートの概念図である。
【図７】交差点位置の抽出手順について説明するための流れ図である。
【図８】道路候補画像データについて説明するための概念図である。
【図９】マッチング値マップについて説明するための概念図である。
【図１０】数１６の模式図である。
【図１１】マッチング値について説明するための概念図である。
【図１２】フーリエ係数について説明するための概念図である。
【図１３】打ち切り次数について説明するための概念図である。
【図１４】比較実験に用いた一の航空画像の画像データである。
【図１５】比較実験に用いた他の航空画像の画像データである。
【図１６】図１の交差点位置抽出装置の一変形例の概要構成図である。
【符号の説明】
【００７０】
１…交差点抽出装置、１０…制御部、１０Ａ…相関画像生成部、１０Ｂ…マッチング値計算部１０Ｂ、１０Ｃ…マッチング値マップ計算部、１０Ｄ…交差点位置抽出部、２０…記憶部、２１…交差点検出プログラム、２２…道路候補画像データ、２３…初期データ、２４…交差点テンプレート、２５…枝テンプレート、３０…表示部、４０…入力部、Ｃ１，Ｃ２…交差点、Ｃ３…建物、Ｒ１，Ｒ２，Ｒ３…道路。
【特許請求の範囲】
【請求項１】
地表面画像を数値化した画像データＩ（ｘ，ｙ）から道路の交差点情報を抽出する交差点抽出装置で実行される交差点位置抽出方法であって、
交差点枝モデルを交差点枝分解能Δθずつ回転させたときの回転角θ（＝Δθ×ｎ）（０≦ｎ≦（３６０−Δθ）／Δθ）ごとに、前記交差点枝モデルを数値化したテンプレート値Ｔｂ（θ；ｘ，ｙ）を、前記画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴ（Fast Fourier Transform）を用いて畳み込むことにより、回転角θごとの相関画像Ｈ（θ；（ｘ，ｙ））を生成する相関画像生成ステップと、
複数の分枝を有する交差点モデルにおける前記複数の分枝の方向角θｉに対応する前記相関画像Ｈ（θｉ；（ｘ，ｙ））を足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算するマッチング値計算ステップと、
前記各画素において、前記マッチング値Ｄ（Ｍθ（ｘ，ｙ））をθに関して微分し、微分値がゼロとなるθの値を求め、微分値がゼロとなるθにおける前記マッチング値Ｄ（Ｍθ（ｘ，ｙ））の中から最大値を抽出することにより、マッチング値マップＲ（ｘ，ｙ）を作成するマッチング値マップ作成ステップと、
前記マッチング値マップＲ（ｘ，ｙ）の極大値を検出し、前記画像データＩ（ｘ，ｙ）の前記極大値に対応する位置を交差点位置として抽出する交差点位置抽出ステップと
を含むことを特徴とする交差点位置抽出方法。
【請求項２】
前記マッチング値計算ステップにおいて、前記相関画像Ｈ（θ；（ｘ，ｙ））をθ方向に対してフーリエ級数展開すると共に、所定の次数を超える項を打ち切ったものを足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算する
ことを特徴とする請求項１に記載の交差点位置抽出方法。
【請求項３】
前記マッチング値計算ステップにおいて、前記テンプレート値Ｔｂ（θ；ｘ，ｙ）と、直交基底関数列φｎ（θ）との内積をとることにより導出した基底テンプレートＢｎ（ｘ，ｙ）を前記画像データＩ（ｘ，ｙ）の各画素に対して畳み込むことにより、フーリエ係数Ａｎ（ｘ，ｙ）を計算したのち、前記フーリエ係数Ａｎ（ｘ，ｙ）と前記直交基底関数列φｎ（θ）との内積をとることにより導出したものを足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算する
ことを特徴とする請求項１または請求項２に記載の交差点位置抽出方法。
【請求項４】
地表面画像を数値化した画像データＩ（ｘ，ｙ）から道路の交差点情報を抽出する交差点抽出装置で実行される交差点位置抽出プログラムであって、
交差点枝モデルを交差点枝分解能Δθずつ回転させたときの回転角θ（＝Δθ×ｎ）（０≦ｎ≦（３６０−Δθ）／Δθ）ごとに、前記交差点枝モデルを数値化したテンプレート値Ｔｂ（θ；ｘ，ｙ）を、前記画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴ（Fast Fourier Transform）を用いて畳み込むことにより、回転角θごとの相関画像Ｈ（θ；（ｘ，ｙ））を生成する相関画像生成ステップと、
複数の分枝を有する交差点モデルにおける前記複数の分枝の方向角θｉに対応する前記相関画像Ｈ（θｉ；（ｘ，ｙ））を足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算するマッチング値計算ステップと、
前記各画素において、前記マッチング値Ｄ（Ｍθ（ｘ，ｙ））をθに関して微分し、微分値がゼロとなるθの値を求め、微分値がゼロとなるθにおける前記マッチング値Ｄ（Ｍθ（ｘ，ｙ））の中から最大値を抽出することにより、マッチング値マップＲ（ｘ，ｙ）を作成するマッチング値マップ作成ステップと、
前記マッチング値マップＲ（ｘ，ｙ）の極大値を検出し、前記画像データＩ（ｘ，ｙ）の前記極大値に対応する位置を交差点位置として抽出する交差点位置抽出ステップと
を含むことを特徴とする交差点位置抽出プログラム。
【請求項５】
前記マッチング値計算ステップにおいて、前記相関画像Ｈ（θ；（ｘ，ｙ））をθ方向に対してフーリエ級数展開すると共に、所定の次数を超える項を打ち切ったものを足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算する
ことを特徴とする請求項４に記載の交差点位置抽出プログラム。
【請求項６】
前記マッチング値計算ステップにおいて、前記テンプレート値Ｔｂ（θ；ｘ，ｙ）と、直交基底関数列φｎ（θ）との内積をとることにより導出した基底テンプレートＢｎ（ｘ，ｙ）を前記画像データＩ（ｘ，ｙ）の各画素に対して畳み込むことにより、フーリエ係数Ａｎ（ｘ，ｙ）を計算したのち、前記フーリエ係数Ａｎ（ｘ，ｙ）と前記直交基底関数列φｎ（θ）との内積をとることにより導出したものを足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算する
ことを特徴とする請求項４または請求項５に記載の交差点位置抽出プログラム。
【請求項７】
交差点枝モデルを交差点枝分解能Δθずつ回転させたときの回転角θ（＝Δθ×ｎ）（０≦ｎ≦（３６０−Δθ）／Δθ）ごとに、前記交差点枝モデルを数値化したテンプレート値Ｔｂ（θ；ｘ，ｙ）を、地表面画像を数値化した画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴ（Fast Fourier Transform）を用いて畳み込むことにより、回転角θごとの相関画像Ｈ（θ；（ｘ，ｙ））を生成する相関画像生成部と、
複数の分枝を有する交差点モデルにおける前記複数の分枝の方向角θｉに対応する前記相関画像Ｈ（θｉ；（ｘ，ｙ））を足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算するマッチング値計算部と、
前記各画素において、前記マッチング値Ｄ（Ｍθ（ｘ，ｙ））をθに関して微分し、微分値がゼロとなるθの値を求め、微分値がゼロとなるθにおける前記マッチング値Ｄ（Ｍθ（ｘ，ｙ））の中から最大値を抽出することにより、マッチング値マップＲ（ｘ，ｙ）を作成するマッチング値マップ計算部と、
前記マッチング値マップＲ（ｘ，ｙ）の極大値を検出し、前記画像データＩ（ｘ，ｙ）の前記極大値に対応する位置を交差点位置として抽出する交差点位置抽出部と
を備えたことを特徴とする交差点位置抽出装置。
【請求項８】
前記マッチング値計算部は、前記相関画像Ｈ（θ；（ｘ，ｙ））をθ方向に対してフーリエ級数展開すると共に、所定の次数を超える項を打ち切ったものを足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算する
ことを特徴とする請求項７に記載の交差点位置抽出装置。
【請求項９】
前記マッチング値計算部は、前記テンプレート値Ｔｂ（θ；ｘ，ｙ）と、直交基底関数列φｎ（θ）との内積をとることにより導出した基底テンプレートＢｎ（ｘ，ｙ）を前記画像データＩ（ｘ，ｙ）の各画素に対して畳み込むことにより、フーリエ係数Ａｎ（ｘ，ｙ）を計算したのち、前記フーリエ係数Ａｎ（ｘ，ｙ）と前記直交基底関数列φｎ（θ）との内積をとることにより導出したものを足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算する
ことを特徴とする請求項７または請求項８に記載の交差点位置抽出装置。
【請求項１】
地表面画像を数値化した画像データＩ（ｘ，ｙ）から道路の交差点情報を抽出する交差点抽出装置で実行される交差点位置抽出方法であって、
交差点枝モデルを交差点枝分解能Δθずつ回転させたときの回転角θ（＝Δθ×ｎ）（０≦ｎ≦（３６０−Δθ）／Δθ）ごとに、前記交差点枝モデルを数値化したテンプレート値Ｔｂ（θ；ｘ，ｙ）を、前記画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴ（Fast Fourier Transform）を用いて畳み込むことにより、回転角θごとの相関画像Ｈ（θ；（ｘ，ｙ））を生成する相関画像生成ステップと、
複数の分枝を有する交差点モデルにおける前記複数の分枝の方向角θｉに対応する前記相関画像Ｈ（θｉ；（ｘ，ｙ））を足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算するマッチング値計算ステップと、
前記各画素において、前記マッチング値Ｄ（Ｍθ（ｘ，ｙ））をθに関して微分し、微分値がゼロとなるθの値を求め、微分値がゼロとなるθにおける前記マッチング値Ｄ（Ｍθ（ｘ，ｙ））の中から最大値を抽出することにより、マッチング値マップＲ（ｘ，ｙ）を作成するマッチング値マップ作成ステップと、
前記マッチング値マップＲ（ｘ，ｙ）の極大値を検出し、前記画像データＩ（ｘ，ｙ）の前記極大値に対応する位置を交差点位置として抽出する交差点位置抽出ステップと
を含むことを特徴とする交差点位置抽出方法。
【請求項２】
前記マッチング値計算ステップにおいて、前記相関画像Ｈ（θ；（ｘ，ｙ））をθ方向に対してフーリエ級数展開すると共に、所定の次数を超える項を打ち切ったものを足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算する
ことを特徴とする請求項１に記載の交差点位置抽出方法。
【請求項３】
前記マッチング値計算ステップにおいて、前記テンプレート値Ｔｂ（θ；ｘ，ｙ）と、直交基底関数列φｎ（θ）との内積をとることにより導出した基底テンプレートＢｎ（ｘ，ｙ）を前記画像データＩ（ｘ，ｙ）の各画素に対して畳み込むことにより、フーリエ係数Ａｎ（ｘ，ｙ）を計算したのち、前記フーリエ係数Ａｎ（ｘ，ｙ）と前記直交基底関数列φｎ（θ）との内積をとることにより導出したものを足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算する
ことを特徴とする請求項１または請求項２に記載の交差点位置抽出方法。
【請求項４】
地表面画像を数値化した画像データＩ（ｘ，ｙ）から道路の交差点情報を抽出する交差点抽出装置で実行される交差点位置抽出プログラムであって、
交差点枝モデルを交差点枝分解能Δθずつ回転させたときの回転角θ（＝Δθ×ｎ）（０≦ｎ≦（３６０−Δθ）／Δθ）ごとに、前記交差点枝モデルを数値化したテンプレート値Ｔｂ（θ；ｘ，ｙ）を、前記画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴ（Fast Fourier Transform）を用いて畳み込むことにより、回転角θごとの相関画像Ｈ（θ；（ｘ，ｙ））を生成する相関画像生成ステップと、
複数の分枝を有する交差点モデルにおける前記複数の分枝の方向角θｉに対応する前記相関画像Ｈ（θｉ；（ｘ，ｙ））を足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算するマッチング値計算ステップと、
前記各画素において、前記マッチング値Ｄ（Ｍθ（ｘ，ｙ））をθに関して微分し、微分値がゼロとなるθの値を求め、微分値がゼロとなるθにおける前記マッチング値Ｄ（Ｍθ（ｘ，ｙ））の中から最大値を抽出することにより、マッチング値マップＲ（ｘ，ｙ）を作成するマッチング値マップ作成ステップと、
前記マッチング値マップＲ（ｘ，ｙ）の極大値を検出し、前記画像データＩ（ｘ，ｙ）の前記極大値に対応する位置を交差点位置として抽出する交差点位置抽出ステップと
を含むことを特徴とする交差点位置抽出プログラム。
【請求項５】
前記マッチング値計算ステップにおいて、前記相関画像Ｈ（θ；（ｘ，ｙ））をθ方向に対してフーリエ級数展開すると共に、所定の次数を超える項を打ち切ったものを足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算する
ことを特徴とする請求項４に記載の交差点位置抽出プログラム。
【請求項６】
前記マッチング値計算ステップにおいて、前記テンプレート値Ｔｂ（θ；ｘ，ｙ）と、直交基底関数列φｎ（θ）との内積をとることにより導出した基底テンプレートＢｎ（ｘ，ｙ）を前記画像データＩ（ｘ，ｙ）の各画素に対して畳み込むことにより、フーリエ係数Ａｎ（ｘ，ｙ）を計算したのち、前記フーリエ係数Ａｎ（ｘ，ｙ）と前記直交基底関数列φｎ（θ）との内積をとることにより導出したものを足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算する
ことを特徴とする請求項４または請求項５に記載の交差点位置抽出プログラム。
【請求項７】
交差点枝モデルを交差点枝分解能Δθずつ回転させたときの回転角θ（＝Δθ×ｎ）（０≦ｎ≦（３６０−Δθ）／Δθ）ごとに、前記交差点枝モデルを数値化したテンプレート値Ｔｂ（θ；ｘ，ｙ）を、地表面画像を数値化した画像データＩ（ｘ，ｙ）の各画素に対してＦＦＴ（Fast Fourier Transform）を用いて畳み込むことにより、回転角θごとの相関画像Ｈ（θ；（ｘ，ｙ））を生成する相関画像生成部と、
複数の分枝を有する交差点モデルにおける前記複数の分枝の方向角θｉに対応する前記相関画像Ｈ（θｉ；（ｘ，ｙ））を足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算するマッチング値計算部と、
前記各画素において、前記マッチング値Ｄ（Ｍθ（ｘ，ｙ））をθに関して微分し、微分値がゼロとなるθの値を求め、微分値がゼロとなるθにおける前記マッチング値Ｄ（Ｍθ（ｘ，ｙ））の中から最大値を抽出することにより、マッチング値マップＲ（ｘ，ｙ）を作成するマッチング値マップ計算部と、
前記マッチング値マップＲ（ｘ，ｙ）の極大値を検出し、前記画像データＩ（ｘ，ｙ）の前記極大値に対応する位置を交差点位置として抽出する交差点位置抽出部と
を備えたことを特徴とする交差点位置抽出装置。
【請求項８】
前記マッチング値計算部は、前記相関画像Ｈ（θ；（ｘ，ｙ））をθ方向に対してフーリエ級数展開すると共に、所定の次数を超える項を打ち切ったものを足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算する
ことを特徴とする請求項７に記載の交差点位置抽出装置。
【請求項９】
前記マッチング値計算部は、前記テンプレート値Ｔｂ（θ；ｘ，ｙ）と、直交基底関数列φｎ（θ）との内積をとることにより導出した基底テンプレートＢｎ（ｘ，ｙ）を前記画像データＩ（ｘ，ｙ）の各画素に対して畳み込むことにより、フーリエ係数Ａｎ（ｘ，ｙ）を計算したのち、前記フーリエ係数Ａｎ（ｘ，ｙ）と前記直交基底関数列φｎ（θ）との内積をとることにより導出したものを足し合わせることにより、前記交差点モデルでのマッチング値Ｄ（Ｍθ（ｘ，ｙ））を計算する
ことを特徴とする請求項７または請求項８に記載の交差点位置抽出装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２００９−１４０４３６（Ｐ２００９−１４０４３６Ａ）
【公開日】平成２１年６月２５日（２００９．６．２５）
【国際特許分類】
【出願番号】特願２００７−３１８８３０（Ｐ２００７−３１８８３０）
【出願日】平成１９年１２月１０日（２００７．１２．１０）
【出願人】（５０４１５９２３５）国立大学法人 熊本大学 (314)
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
【公開日】平成２１年６月２５日（２００９．６．２５）
【国際特許分類】
【出願日】平成１９年１２月１０日（２００７．１２．１０）
【出願人】（５０４１５９２３５）国立大学法人 熊本大学 (314)
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
[ Back to top ]