(57)【要約】【課題】道案内のための歩道情報を適切に生成する。【解決手段】実施形態における歩道情報生成装置は、歩道の領域を表す画像データから、前記領域の幅方向の中心線を抽出する細線化処理を行なう細線化手段と、前記細線化手段により抽出された前記中心線を長手方向に分割して複数の線を生成するセグメンテーション処理を行なうセグメンテーション手段と、前記セグメンテーション手段により生成された前記複数の線の各々を線分の座標列を示すベクターデータに変換するベクター化手段と、を有する。【選択図】図１
2019211976.tif 000002
【特許請求の範囲】
【請求項１】
歩道の領域を表す画像データから、前記領域の幅方向の中心線を抽出する細線化処理を行なう細線化手段と、
前記細線化手段により抽出された前記中心線を長手方向に分割して複数の線を生成するセグメンテーション処理を行なうセグメンテーション手段と、
前記セグメンテーション手段により生成された前記複数の線の各々を線分の座標列を示すベクターデータに変換するベクター化手段と、
を備えた歩道情報生成装置。
【請求項２】
前記ベクター化手段により変換されたベクターデータにより示される前記線分の座標列が示す所定の位置と前記歩道の領域の境界との距離に基づいて、前記歩道の幅員を算出する幅員算出手段、
をさらに備えた請求項１に記載の歩道情報生成装置。
【請求項３】
前記ベクターデータにより座標列として示される線分のうち、同一座標の分岐点から延びる複数の線分であって、前記分岐点を一端とする線分を抽出し、前記抽出した線分の１つを残した上で、前記抽出した線分のうち所定の長さ未満の他の線分を削除する削除手段、
をさらに備えた請求項１または２に記載の歩道情報生成装置。
【請求項４】
前記ベクターデータで示される、反りを有する線分を、基準となる線分と、当該線分に直線的に連なる線分とに変換することで、前記反りを修正する修正手段、
をさらに備えた請求項１乃至３のいずれか１項に記載の歩道情報生成装置。
【請求項５】
歩道情報生成装置が行なう歩道情報生成方法であって、
歩道の領域を表す画像データから、前記領域の幅方向の中心線を抽出する細線化処理を行ない、
前記抽出された前記中心線を長手方向に分割して複数の線を生成するセグメンテーション処理を行ない、
前記生成された前記複数の線の各々を線分の座標列を示すベクターデータに変換する、
歩道情報生成方法。
【請求項６】
請求項１乃至４のいずれか１項に記載の歩道情報生成装置の前記各手段としてプロセッサを機能させる歩道情報生成処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、歩道情報生成装置、方法およびプログラムに関する。
【背景技術】
【０００２】
車または人を道案内するシステムを構築するためには、属性情報付きの道路ネットワーク情報が不可欠である。道路ネットワーク情報とは、道路網をノードとリンクで表した情報のことである。道案内を行なうシステムは、道路ネットワーク情報を探索し、利用者に最適な経路を提示する。さらに、道幅および一方通行の制約等、様々な属性情報が道路ネットワーク情報に備わっていれば、道案内を行なうシステムは、この道路ネットワーク情報を考慮して最適な経路を探索することが可能になる。
【０００３】
近年、障がい者にとってバリアとなる場所を記した歩道ネットワーク情報のニーズが高まっている。例えば、車椅子利用者は、車椅子の幅以上の幅員がない歩道を通ることはできない。このため、彼らに道案内を行なうシステムを実現するためには、歩道の中心線と、この歩道の幅員とに関する情報をそれぞれ収集することが望ましい。歩道の中心線と幅員に関する情報があれば、歩道同士を連結して歩道ネットワーク情報を作成することが可能である。
【０００４】
歩道の中心線と、この歩道の幅員に関するデータを、現地調査または手作業で作成するには多大なコストがかかる。ただし、歩道の領域を二次元ポリゴン化した歩道ポリゴンデータ（単にポリゴンデータと称することがある）を含む電子地図データが一般的に存在するので、このデータから歩道の中心線を自動的に抽出することで、道路情報の生成の自動化に寄与することが考えられる。ここでキーとなる技術は、面積を有する形状の中心線を求める、いわゆる「細線化」という画像処理で、代表的な手法は、例えば非特許文献１に開示される。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Zhang, T. Y. and Suen, Ching Y., “A Fast Parallel Algorithms ForThinning Digital Patterns”,Communication of the ACM,Vol 27, No. 3,Maret 1984, pp.236-239.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、歩道領域の端の部分は、曲がった形状となっているため、この歩道領域を、機械的にそのまま細線化すると、歩道中心線も端が曲がった形状になってしまう。このような線を連結して歩道ネットワーク情報を作成することは、スムースな道案内が実現できないため、望ましくない。
【０００７】
また、歩道ポリゴンデータを細線化処理しただけでは、どのような細線化アルゴリズムを用いても余計な線分が発生してしまうことがあり、正しい歩道ネットワーク情報を作成することの妨げになってしまう。
上記のように、歩道中心線の曲がった形状及び余分な線分については別処理で修正する必要があるが、上記の歩道ポリゴンデータを細線化処理した結果は、そのまま修正に用いるには適していない。
【０００８】
この発明は上記事情に着目してなされたもので、その目的とするところは、道案内のための歩道情報を適切に生成することができるようにした歩道情報生成装置、方法およびプログラムを提供することにある。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、この発明の一実施形態における歩道情報生成装置の第１の態様は、歩道情報生成装置が、歩道の領域を表す画像データから、前記領域の幅方向の中心線を抽出する細線化処理を行なう細線化手段と、前記細線化手段により抽出された前記中心線を長手方向に分割して複数の線を生成するセグメンテーション処理を行なうセグメンテーション手段と、前記セグメンテーション手段により生成された前記複数の線の各々を線分の座標列を示すベクターデータに変換するベクター化手段と、を備えるようにしたものである。
【００１０】
この発明の歩道情報生成装置の第２の態様は、第１の態様において、前記ベクター化手段により変換されたベクターデータにより示される前記線分の座標列が示す所定の位置と前記歩道の領域の境界との距離に基づいて、前記歩道の幅員を算出する幅員算出手段、をさらに備えるようにしたものである。
【００１１】
この発明の歩道情報生成装置の第３の態様は、第１または第２の態様において、前記ベクターデータにより座標列として示される線分のうち、同一座標の分岐点から延びる複数の線分であって、前記分岐点を一端とする線分を抽出し、前記抽出した線分の１つを残した上で、前記抽出した線分のうち所定の長さ未満の他の線分を削除する削除手段、をさらに備えるようにしたものである。
【００１２】
この発明の歩道情報生成装置の第４の態様は、第１乃至第３の態様のいずれか１つにおいて、前記ベクターデータで示される、反りを有する線分を、基準となる線分と、当該線分に直線的に連なる線分とに変換することで、前記反りを修正する修正手段、をさらに備えるようにしたものである。
【００１３】
本発明の一実施形態における、歩道情報生成装置が行なう歩道情報生成方法の一つの態様は、歩道の領域を表す画像データから、前記領域の幅方向の中心線を抽出する細線化処理を行ない、前記抽出された前記中心線を長手方向に分割して複数の線を生成するセグメンテーション処理を行ない、前記生成された前記複数の線の各々を線分の座標列を示すベクターデータに変換するようにしたものである。
【００１４】
本発明の一実施形態における歩道情報生成処理プログラムの一つの態様は、第１乃至第４の態様のいずれか１つにおける歩道情報生成装置の前記各手段としてプロセッサを機能させるものである。
【発明の効果】
【００１５】
この発明の一実施形態における歩道情報生成装置の第１の態様によれば、歩道中心線を長手方向に分割することで複数の線が生成され、線分の座標列を示すベクターデータに変換される。このため、歩行者、特に車椅子利用者等に対する道案内に有効な歩道情報を適切に作成することができる。
【００１６】
この発明の一実施形態における歩道情報生成装置の第２の態様によれば、ベクターデータの所定の位置を含む、歩道の幅員が算出される。このため、歩行者、特に車椅子利用者等が通過できるか判定するのに有効な歩道情報を作成することができる。
【００１７】
この発明の一実施形態における歩道情報生成装置の第３の態様によれば、ベクターデータに基づいて、歩道中心線における分岐のうち所定の長さ以下である不要な分岐が除去される。このため、スムースな道案内に利用できる適切な歩道情報を作成することができる。
【００１８】
この発明の一実施形態における歩道情報生成装置の第４の態様によれば、ベクターデータに基づいて、歩道中心線の余分な反りが修正される。このため、正しい道案内に利用できる適切な歩道情報を作成することができる。
【００１９】
すなわち、本発明によれば、道案内のための歩道情報を適切に生成することが可能になる。
【図面の簡単な説明】
【００２０】
【図１】本発明の一実施形態における歩道中心線生成装置の一適用例を示す図。
【図２】歩道ポリゴンデータの一例を示す図。
【図３】歩道ポリゴンデータの一例を示す図。
【図４】本発明の一実施形態における歩道中心線生成装置の処理手順の一例を示す図。
【図５】本発明の一実施形態における歩道中心線生成装置によるビットマップ生成処理の手順の一例を示す図。
【図６】歩道ポリゴンデータから生成されたビットマップの一例を示す図。
【図７】歩道ポリゴンデータから生成されたビットマップの一例を示す図。
【図８】細線化処理を適用した結果の一例を示す図。
【図９】細線化処理を適用した結果の一例を示す図。
【図１０】本発明の一実施形態における歩道中心線生成装置によるセグメンテーション処理の手順の一例を示す図。
【図１１】細線化画像におけるピクセルのナンバリングの一例を示す図。
【図１２】セグメンテーション処理の結果の一例を示す図。
【図１３】セグメンテーション処理の結果の一例を示す図。
【図１４】ベクター化処理の結果の一例を示す図。
【図１５】ベクター化処理の結果の一例を示す図。
【図１６】本発明の一実施形態における歩道中心線生成装置による幅員算出処理の手順の一例を示す図。
【図１７】幅員算出処理における距離の二乗の代入結果の一例を示す図。
【図１８】歩道の境界までの間の最短距離の検出結果の一例を示す図。
【図１９】幅員の出力データの一例を示す図。
【図２０】幅員の出力データの一例を示す図。
【図２１】不要な分岐点の一例を示す図。
【図２２】本発明の一実施形態における歩道中心線生成装置による不要セグメント除去処理の手順の一例を示す図。
【図２３】不要セグメント除去処理の結果の一例を示す図。
【図２４】本発明の一実施形態における歩道中心線生成装置による反り修正処理の手順の一例を示す図。
【図２５】反り修正処理の一例を示す図。
【図２６】反り修正処理の結果の一例を示す図。
【図２７】反り修正処理後の出力データの一例を示す図。
【図２８】反り修正処理の一例を示す図。
【図２９】反り修正処理の結果の一例を示す図。
【図３０】反り修正処理後の出力データの一例を示す図。
【図３１】歩道の幅員を可視化した例を示す図。
【図３２】歩道の幅員を可視化した例を示す図。
【図３３】不要セグメント除去処理および反り修正処理を施さなかったときの出力例を示す図。
【図３４】不要セグメント除去処理および反り修正処理を施したときの出力例を示す図。
【発明を実施するための形態】
【００２１】
以下、図面を参照しながら、この発明に係わる一実施形態を説明する。  
図１は、本発明の一実施形態における歩道中心線生成装置の一適用例を示す図である。  
図１に示すように、歩道中心線生成装置（歩道情報生成装置）１０は、歩道ポリゴンデータ保存部１００、ビットマップ生成部１０１、細線化部１０２、セグメンテーション部１０３、ベクター化部１０４、緯度経度変換部１０５、不要セグメント除去部（削除手段）１０６、反り修正部１０７、幅員算出部１０８、幅員付き歩道中心線データ保存部１０９を備える。各部の詳細については後述する。
【００２２】
また、歩道中心線生成装置１０は、パーソナルコンピュータ（ＰＣ）などのコンピュータデバイスを用いたシステムにより実現可能である。例えば、コンピュータデバイスは、ＣＰＵ（Central Processing Unit）などのプロセッサと、プロセッサに接続されるメモリと、入出力インタフェースとを備える。このうちメモリは、不揮発性メモリなどの記憶媒体を有する記憶装置により構成される。
【００２３】
ビットマップ生成部１０１、細線化部１０２、セグメンテーション部１０３、ベクター化部１０４、緯度経度変換部１０５、不要セグメント除去部１０６、反り修正部１０７、幅員算出部１０８の機能は、例えば、プロセッサがメモリに格納されているプログラムを読み出して実行することにより実現される。なお、これらの機能の一部または全部は、特定用途向け集積回路（ＡＳＩＣ）などの回路によって実現されてもよい。  
歩道ポリゴンデータ保存部１００および幅員付き歩道中心線データ保存部１０９は、上記メモリのうち随時書込および読み出しが可能な不揮発性メモリに設けられる。
【００２４】
地図を販売する国内の多くの企業は、歩道が存在する範囲を航空写真からトレースし、この歩道を歩道ポリゴンデータとしてディジタル化した地図を販売している。本発明の一実施形態では、この歩道ポリゴンデータを利用して歩道中心線を示すベクターデータを作成する。
【００２５】
図２および図３は、歩道ポリゴンデータの異なる２つの例を示す図である。  
図２、図３に示すように、歩道ポリゴンデータは、緯度（例えば図３の一列目に記載した35.6931…）および経度（例えば図３の一列目に記載した139.7027…）のリストである。このリストにおいて、緯度経度を行方向に順に接続して形成される領域が歩道の領域を表す。このような歩道ポリゴンデータが歩道ポリゴンデータ保存部１００に保存されている。
【００２６】
次に、歩道中心線生成装置１０による処理について説明する。図４は、本発明の一実施形態における歩道中心線生成装置の処理手順の一例を示す図である。  
（ビットマップの生成）
最初に、ビットマップ生成部１０１は、歩道ポリゴンデータをビットマップ（歩道ビットマップと称することもある）に変換するビットマップ生成処理を行なう（Ｓ１）。
【００２７】
ビットマップ生成処理の具体例を以下のＳ１１〜Ｓ１８にて説明する。図５は、本発明の一実施形態における歩道中心線生成装置によるビットマップ生成処理の手順の一例を示す図である。  
まず、ビットマップ生成部１０１は、歩道ポリゴンデータ保存部１００から歩道ポリゴンデータを読み出す（Ｓ１１）。このビットマップ生成処理では、歩道が位置する地域により、緯度経度１度分の長さが異なることを考慮する。
【００２８】
また、緯度経度は小数点で表されるので、ビットマップ生成部１０１は、歩道ポリゴンデータをビットマップに変換する前に、所望の精度に応じて、歩道ポリゴンデータの緯度経度に十分に大きな値を掛けて整数化する（Ｓ１２）。
【００２９】
この例では、歩道ポリゴンデータの緯度経度に10000000を掛けて、小数点以下を切り捨てることで整数化している。ビットマップ生成部１０１は、例えば、図２に示した歩道ポリゴンデータの最初の行の緯度「35.692694242」、経度「139.702499333」を「356926942」「1397024993」という値にそれぞれ変換する。
【００３０】
そして、ビットマップ生成部１０１は、例えば図２に示したような歩道ポリゴンデータを形成する各行における緯度の最大値と緯度の最小値との差分を横幅とし、経度の最大値と経度の最小値との差分を縦幅とするビットマップを作成し（Ｓ１３）、このビットマップの全体に歩道ポリゴンデータをモノクロで描画する（Ｓ１４）。図２に示した歩道ポリゴンデータでは、横幅1819、縦幅2420となる。
【００３１】
次に、ビットマップ生成部１０１は、歩道ポリゴンデータの中心座標を求める（Ｓ１５）。  
この中心座標は、例えば図２に示すような歩道ポリゴンデータを形成する各行の緯度の平均値と経度の平均値とからなる。  
例えば、図２に示したポリゴンデータでは、中心座標（緯度、経度）は（35.69277105, 139.7025096）となる。
【００３２】
次に、ビットマップ生成部１０１は、歩道が位置する地域における緯度経度で１度分移動したときのx座標における移動距離mx、およびy座標における移動距離myを以下の式（１）、（２）でそれぞれ算出する（Ｓ１６）。
【００３３】
mx = equational_radius*cos(polygon_center_latitude*PI/180)*PI/180  …式（１）
my = polar_radius*PI/180  …式（２）
式（１）のequational_radiusは赤道半径の6378137[m]で、式（２）のpolar_radiusは極半径の6356752.314[m]であり、式（１）のpolygon_cener_latitudeは、図２の歩道ポリゴンデータでは35.69277105である。このとき、式（１）のmxは90408.9198508[m]となり、式（２）のmyは110946.257613[m]となる。
【００３４】
次に、ビットマップ生成部１０１は、歩道ポリゴンデータから最初に作成されたビットマップの縦幅にmx/myを掛けてリサイズする（Ｓ１７）。  
結果的に、図２に示した歩道ポリゴンデータは、横幅1819、縦幅1972にリサイズされる。
【００３５】
この状態では、ビットマップの端に歩道ポリゴンのどこかが接触しているはずであるが、この後の処理のために歩道ポリゴンの周囲に１ピクセルのマージンを設け、横幅1821、縦幅1974のビットマップ画像を出力する（Ｓ１８）。これによりＳ１の処理が終了する。
【００３６】
図６および図７は、歩道ポリゴンデータから生成されたビットマップの一例を示す図である。  
図２に示した歩道ポリゴンデータをビットマップ化した例が図６であり、図３に示した歩道ポリゴンデータをビットマップ化した例が図７である。
【００３７】
（歩道ビットマップの細線化）
次に、細線化部１０２は、いわゆる細線化アルゴリズムを用いて歩道ビットマップを細線化する細線化処理を行なう（Ｓ２）。細線化とは、歩道の領域から、当該領域の幅方向の中心線を抽出する処理のことである。細線化については様々なアルゴリズムが提案されているが、ここでは上記の非特許文献１に開示されるZhang-Suenの手法を適用する。
【００３８】
具体的には、細線化部１０２は、Ｓ１で生成された歩道ビットマップをラスタスキャンし、注目画素を中心に３×３の画像値のパターンを観測し、注目画素が以下の条件（１）、（２）、（３）を満たすとき、この注目画素の値を白画素の値にする。
【００３９】
（１）境界上にある黒画素であること。
（２）白画素に変更しても連結性が保存されること。
（３）端点でないこと。
【００４０】
図８および図９は、細線化処理を適用した結果の一例を示す図である。  
図８に示した領域内の線は、図６に示したビットマップにZhang-Suenの細線化処理を適用した結果である。また、図９に示した領域内の線は、図７に示したビットマップにZhang-Suenの細線化処理を適用した結果である。
【００４１】
（細線化画像のセグメンテーション）
次に、後処理のベクトル化のために、セグメンテーション部１０３は、細線化画像のセグメンテーション処理を行なう（Ｓ３）。セグメンテーションとは、細線化画像における中心線を、当該中心線の端点、分岐点をもとに長手方向に分割して複数の線を生成する処理である。
【００４２】
セグメンテーション処理の具体例を以下のＳ３１〜Ｓ３３にて説明する。図１０は、本発明の一実施形態における歩道中心線生成装置によるセグメンテーション処理の手順の一例を示す図である。  
まず、セグメンテーション部１０３は、細線化画像における背景のピクセルの値を「０」に設定し、細線化画像における中心線が描画されている部分のピクセルの値を「１」に設定する。
【００４３】
図１１は、細線化画像におけるピクセルのナンバリングの一例を示す図である。セグメンテーション部１０３は、細線化画像をラスタスキャンし（Ｓ３１）、注目するピクセルをＰ１とし、このＰ１の値が「１」であるとき、Ｐ１に隣接する８つのピクセルを図１１のようにＰ２〜Ｐ９にナンバリングする。セグメンテーション部１０３は、これらＰ２〜Ｐ９のピクセルにおける値が「１」であるピクセルの数Ａをカウントする。この結果が、Ａ＝１であれば、セグメンテーション部１０３は、ピクセルＰ１を端点に設定する。
【００４４】
また、Ａ＝１以外であれば、セグメンテーション部１０３は、ナンバリングしたピクセルの値をＰ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６、Ｐ７、Ｐ８、Ｐ９、Ｐ２の順に調べ、これら調べた計９つの値でなる配列を生成し、この配列における、０の次に１になる箇所Ｂの数をカウントし、Ｂ≧３であれば、ピクセルＰ１を分岐点とする（Ｓ３２）。すべての端点および分岐点を見つけた後は、セグメンテーション部１０３は、これらの点間で線が存在する組を輪郭追跡により探し、２点の組のリストを作成する（Ｓ３３）。以後、これら２点の組でつながれた線をセグメントと呼ぶこととする。
図１２および図１３は、セグメンテーション処理の結果の一例を示す図である。図１２は、図８に示した細線化処理結果にセグメンテーション処理を適用した結果である。図１３は、図９に示した細線化処理結果にセグメンテーション処理を適用した結果である。Eと記された点は検出された端点を、Bと記された点は検出された分岐点を表している。
【００４５】
例えば図１２では、seg_id:0〜seg_id:4にそれぞれ対応する５つのセグメントが存在し、１つ目の分岐点からseg_id:0、seg_id:1、seg_id:4にそれぞれ対応するセグメントが延び、２つ目の分岐点からseg_id:2、seg_id:3、seg_id:4にそれぞれ対応するセグメントが延びる。図１３では、セグメントは一つである。セグメンテーション部の処理が完了した段階では、二点間の線はビットマップのままである。
【００４６】
（セグメントのベクター化、経度緯度変換）
ベクター化部１０４は、上記の２点の組のリストに対して、ベクター化（ベクターデータ化と称することもある）処理を実施する（Ｓ４）。ベクター化処理とは、セグメンテーション処理で示される複数のビットマップとしての線の各々を座標列である歩道ベクターデータに変換することである。具体的には、例えば、文献「画像情報教育振興協会、ディジタル画像処理[改訂新版]、ISBN-10: 490347450X」の194ページに記載の２分割法を用いる。  
図１４および図１５は、ベクター化処理の結果の一例を示す図である。図１４は、図１２に示したセグメンテーション処理結果にベクター化処理を適用した結果である。図１５は、図１３に示したセグメンテーション処理結果にベクター化処理を適用した結果である。これらの図における複数の線分を形成する黒い点がベクター化処理によって求められた座標である。
ベクター化処理の結果、図１２のseg_id:0、seg_id:3、seg_id:4にそれぞれ対応するセグメントは、図１４に示すように２つの線分がポイントを介して連なってなるセグメントとなり、これらのセグメントを構成するポイントは３つとなる。その他のセグメントは、１つの線分でなるセグメントであり、これらのセグメントを構成するポイントは２つである。  
ベクター化したポイントはビットマップ上の座標である。ここで、緯度経度変換部１０５は、この座標を緯度経度に換算する（Ｓ５）。
【００４７】
（幅員算出）
Ｓ１〜Ｓ４までで、歩道ポリゴンデータを緯度経度１度分の比を考慮してビットマップ化し、歩道中心線を細線化処理により求め、ベクターデータ化までを行なった。次に、幅員算出部１０８は、歩道の幅員を求めるための幅員算出処理を行なう（Ｓ６）。ここでは、幅員算出部１０８は、ベクターデータにより示される線分の座標列が示す所定の位置と歩道の領域の境界との距離に基づいて、歩道の幅員を算出する。
【００４８】
幅員算出処理の具体例を以下のＳ６１〜Ｓ６７にて説明する。図１６は、本発明の一実施形態における歩道中心線生成装置による幅員算出処理の手順の一例を示す図である。  
まず、幅員算出部１０８は、ベクター化されたデータであるベクターデータを形成する座標列が示す所定の１つのポイントに対し、当該ポイントの横方向のビットマップの画素分の配列を作成し（Ｓ６１）、この配列において、対応する画素に歩道が描かれている場合のみ、上記のポイントから各画素までの距離の二乗Ｈを計算し、このＨを対応する要素（画素）の値として代入する（Ｓ６２）。  
図１７は、幅員算出処理における距離の二乗の代入結果の一例を示す図である。ただし、図１７では、画素数を省略して実際より少ない数とし、上記のＨが代入されていない要素を省略して表記している。
【００４９】
次に、幅員算出部１０８は、Ｓ６１で作成された配列で数値（Ｈ）が代入された各要素から、ビットマップの垂直方向をそれぞれ走査し（Ｓ６３）、この垂直方向における上記要素から歩道の境界（歩道と歩道外（背景）とを隔てる境界）までの間で最短距離となるピクセルを検出し（Ｓ６４）、この最短距離の二乗Ｖを計算する（Ｓ６５）。
【００５０】
次に、幅員算出部１０８は、各要素について計算された個々のＨとＶとを足した結果から最小値を選択し、この値の平方根の２倍を、対象とするポイントにおけるビットマップ上での幅員Wbとして計算する（Ｓ６６）。
【００５１】
図１８は、歩道の境界までの間の最短距離の検出結果の一例を示す図である。図１８に示した例では、(H, V)=(25, 9)のときのＨとＶの和である３４（＝２５＋９）が、個々の要素についてのＨとＶの和における最小値となり、幅員算出部１０８は、上記の３４の平方根の２倍を、対象とするポイントにおけるビットマップ上での幅員Wbとして計算する。
【００５２】
次に、幅員算出部１０８は、この幅員Wbを以下の式（３）で実際の距離Wrに変換する（Ｓ６７）。  
Wr = Wb*mx/10000000  …式（３）
ここまでの結果から、次のような結果が出力できる。図１９および図２０は、幅員の出力データの一例を示す図である。図２、６、８、１２、１４、１７、１８に対応する出力データの例は図１９である。また、図３、７、９、１３、１５に対応する出力データの例は図２０である。
【００５３】
図１９、２０のroad_idは、処理対象とする地域の歩道のidである。seg_idは、同じ行のroad_idに対応する歩道を構成するセグメント（セグメンテーション処理による線）のidであり、point_idは歩道ベクターデータにおける歩道中心線上のポイント（座標）の連結順序（0,1,2,…）のidを示す。latitudeおよびlongitudeは、各ポイントの緯度経度である。widthは幅員である。
【００５４】
図１９に示した例では、road_id「8870」の歩道について、seg_id「0」、「1」、「2」、「3」、「4」にそれぞれ対応するセグメントが存在し、seg_id「0」に対応するセグメントはpoint _id「0」（ここでは分岐点）、「1」、「2」（ここでは端点）にそれぞれ対応するポイントが存在し、point _id「0」に対応するポイントの緯度経度、幅員は最上段の「35.6927…」、「139.7024…」、「685.8085…」である。
【００５５】
幅員算出部１０８は、歩道ベクターデータを構成する各ポイントの前後の線分の傾きを微分し、この値に対して垂直方向に走査し、境界を検出することで幅員を求めてもよい。ただし計算誤差が生じにくいように、ベクター化時に十分に多いポイント数を設定する。
【００５６】
（不要なセグメントの除去）
縦横比が１対１に近い直方体のような形状の歩道では、どのような細線化アルゴリズムを用いても、理想とする中心線を求めることは困難である。図２１は、不要な分岐点の一例を示す図である。図２１は図１４に示したベクター化処理結果における、望ましくない箇所に生じている分岐点を示す結果である。
【００５７】
そこで、不要セグメント除去部１０６は、この望ましくない箇所に対応するセグメントを除去する不要セグメント除去処理を行なう（Ｓ７）。ここで、不要セグメント除去部１０６は、ベクターデータにより緯度経度の座標列として示される線分のうち、同一座標の分岐点から延びる複数の線分であって、分岐点を一端として他方が端点である線分を抽出し、抽出した線分の１つを残した上で、抽出した線分のうち所定の長さ未満の他の線分を削除する。
【００５８】
不要セグメント除去処理の具体例を以下のＳ７１〜Ｓ７３にて説明する。図２２は、本発明の一実施形態における歩道中心線生成装置によるビットマップ生成処理の手順の一例を示す図である。  
不要セグメント除去部１０６は、図１９または図２０に示すような出力データを参照し、このデータにおける、あるroad_idにかかる各行に、同一の分岐点から延びた複数の線分に対応する各seg_id（例えば、図１９に示すseg_id:0,seg_id:1、図１９に示すseg_id:2,seg_id:3）にかかる行が存在し、かつ、これらの線分が、分岐点を一端とし他方が端点である線分であるときで（Ｓ７１のＹＥＳ）、これらの線分の中に一定の長さ（例えば３ｍ）未満の線分があれば（Ｓ７２のＹＥＳ）、不要セグメント除去部１０６は、上記の、分岐点を一端とし他方が端点である線分のうち１つを残した上で、上記の一定の長さ未満の他の線分を削除するように出力データを修正する処理を行なう（Ｓ７３）。
【００５９】
Ｓ７１の処理で、出力データを参照し、この出力データにおける、あるroad_idにかかる各行に、同一の分岐点から延びた複数の線分に対応する各seg_idに対応する行が存在するか否かは、例えば、不要セグメント除去部１０６により、出力データにおける同一のroad_id、および同一のseg_idにかかる各point_idのうちの先頭もしくは末尾のpoint_idにかかる行を抽出し、これらの行に同一の緯度経度に対応する複数の行があるか否かを調べればよい。
【００６０】
また、Ｓ７１の処理で、同一の分岐点から延びた各線分が、分岐点を一端とし他方が端点である線分であるか否かは、この他方のポイントの緯度経度と同一の緯度経度のポイントが出力データ中の同一のroad_idにかかる各ポイントの中にないか否かを、不要セグメント除去部１０６により確認すればよい。
【００６１】
また、Ｓ７２の処理で、例えば、不要セグメント除去部１０６は、２つのポイントを有する線分のポイント間の長さについては、この長さをヒュベニの公式等で求めればよい。また、不要セグメント除去部１０６は、３つ以上のポイントを有する線分の長さについては、ポイント間の各線分これらの長さを求めた上で、これらの長さを合計すればよい。
【００６２】
図２３は、不要セグメント除去処理の結果の一例を示す図である。図２３に示した例では、図２１で示した分岐点から延びる複数の線分のうち一定の長さ以下の線分（例えば、図１９に示すseg_id:1,seg_id:2に対応する線分）が削除されたことを示す。
【００６３】
また、上記の削除後は、不要セグメント除去部１０６は、上記のあるroad_idにかかる各行の緯度経度を確認することで、削除後の各線分（例えば、図１９に示すseg_id:0,seg_id:3,seg_id:4に対応する線分）に交点または分岐点が含まれていないか否かを確認し、含まれていなければ、該当する各線分に対応するseg_idを一つのseg_idにまとめるように、出力データを修正する処理を行なう。
【００６４】
（ベクターデータの反りを修正）
一般的に歩道の端は、アール（カーブ半径）を持たせてある、いわゆる巻き込み部分となっているため、歩道中心線のベクターデータは、歩道の端に近づくにつれ、曲がった形状になる。そこで、反り修正部１０７は、この曲がった形状を整形する反り修正処理を行なう（Ｓ８）。
【００６５】
反り修正処理の具体例を以下のＳ８１〜Ｓ８３にて説明する。図２４は、本発明の一実施形態における歩道中心線生成装置による反り修正処理の手順の一例を示す図である。  
反り修正部１０７は、不要セグメント削除後の出力データにおける、個々のroad_idにかかる行のなかの、個々のseg_idに対応する線分について、端点を有するか否かを確認する（Ｓ８１）。端点を有するか否かは、同じseg_idにかかる各行のうち先頭もしくは末尾のpoint_idにかかる行の緯度経度と同一の緯度経度が同一road_idにかかる各行に存在しないことを反り修正部１０７により確認すればよい。
【００６６】
図２５は、反り修正処理の一例を示す図である。  
線分が端点を有するのであれば、この端点を図２５に示す端点Ａとし、この端点Ａのpoint_idが、同じseg_idに対応する各point_idのうち先頭のpoint_idだとすると、反り修正部１０７は、このpoint_idを、上記の各point_idのうち末尾方向に辿り、先頭のpoint_idと、それより一つ末尾側のpoint_idにそれぞれ対応するポイント間の長さが一定以上（例えば５ｍ）である線分を基準となる線分として探す（Ｓ８２）。
【００６７】
この、長さが一定以上の部分を図２５に示すベクトルＢＣとすると、反り修正部１０７は、ベクトルＣＢとベクトルＢＡのcosθを求め、ベクトルＣＢのＢ側をcosθ|ＢＡ|の長さ分だけ延長し、点Ｂの直前までのポイントに対応するpoint_idをすべて削除する。また、端点Ａのpoint_idが、同じseg_idにかかる各point_idのうち末尾のpoint_idである場合は、反り修正部１０７は、上記の各point_idのうち末尾方向の逆方向に辿り、末尾方向に辿ったときと同じ処理を実施する。つまり、反り修正部１０７は、反りを有する線分を、基準となる線分と、当該線分に直線的に連なる線分とに変換することで、反りを修正する（Ｓ８３）。
【００６８】
以上の処理の結果、反りが修正された歩道ベクターデータが生成される。図２６は、反り修正処理の結果の一例を示す図である。図２７は、反り修正処理後の出力データの一例を示す図である。図２５で示される反りを修正した結果を可視化した例が図２６であり、反り修正処理により、図１９に示される数値データが不要セグメント除去処理および反り修正処理により図２７に示される数値データに変換される。
【００６９】
図２８は、反り修正処理の一例を示す図である。図２９は、反り修正処理の結果の一例を示す図である。図３０は、反り修正処理後の出力データの一例を示す図である。  
図２８で示される反りを修正した結果を可視化した例が図２９であり、反り修正処理により、図２０に示される数値データが不要セグメント除去処理および反り修正処理により図３０に示される数値データに変換される。最終的な出力データは、幅員付き歩道中心線データ保存部１０９に保存される。
【００７０】
図３１および図３２は、歩道の幅員を可視化した例を示す図である。図２６に示した反り修正結果に対して歩道の幅員を可視化した例が図３１であり、図２９に示した反り修正結果に対して歩道の幅員を可視化した例が図３２である。このように幅員を可視化すると、車椅子利用者等が歩道を通過できるか判断するのに有効である。
【００７１】
図３３は、不要セグメント除去処理および反り修正処理を施さなかったときの出力例を示す図である。この図３３では、隣接する複数の歩道中心線に対して、不要セグメント除去処理および反り修正処理をともに施さなかった場合の出力例である。対照的に、図３４は、不要セグメント除去処理および反り修正処理を施したときの出力例を示す図である。
【００７２】
以上説明したように、本発明の一実施形態における歩道中心線生成装置は、セグメンテーション処理およびベクター化処理により、歩道ネットワーク情報を作成するための歩道中心線データのベクター化を自動で行なうことができる。このため、車椅子利用者等に対する道案内システムに必要な歩道情報を適切に生成することが可能となる。  
また、ベクター化したデータを元に、歩道中心線の不要な分岐および余分な反りを修正することで、スムースで正しく経路案内するために利用できる適切な形状の歩道中心線の生成が可能となる。
【００７３】
なお、本発明は、上記実施形態に限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で種々に変形することが可能である。また、各実施形態は適宜組み合わせて実施してもよく、その場合組み合わせた効果が得られる。更に、上記実施形態には種々の発明が含まれており、開示される複数の構成要件から選択された組み合わせにより種々の発明が抽出され得る。例えば、実施形態に示される全構成要件からいくつかの構成要件が削除されても、課題が解決でき、効果が得られる場合には、この構成要件が削除された構成が発明として抽出され得る。
【００７４】
また、各実施形態に記載した手法は、計算機（コンピュータ）に実行させることができるプログラム（ソフトウエア手段）として、例えば磁気ディスク（フロッピー（登録商標）ディスク、ハードディスク等）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤ、ＭＯ等）、半導体メモリ（ＲＯＭ、ＲＡＭ、フラッシュメモリ等）等の記録媒体に格納し、また通信媒体により伝送して頒布することもできる。なお、媒体側に格納されるプログラムには、計算機に実行させるソフトウエア手段（実行プログラムのみならずテーブル、データ構造も含む）を計算機内に構成させる設定プログラムをも含む。本装置を実現する計算機は、記録媒体に記録されたプログラムを読み込み、また場合により設定プログラムによりソフトウエア手段を構築し、このソフトウエア手段によって動作が制御されることにより上述した処理を実行する。なお、本明細書でいう記録媒体は、頒布用に限らず、計算機内部あるいはネットワークを介して接続される機器に設けられた磁気ディスク、半導体メモリ等の記憶媒体を含むものである。
【符号の説明】
【００７５】
１０…歩道中心線生成装置、１００…歩道ポリゴンデータ保存部、１０１…ビットマップ生成部、１０２…細線化部、１０３…セグメンテーション部、１０４…ベクター化部、１０５…緯度経度変換部、１０６…不要セグメント除去部、１０７…反り修正部、１０８…幅員算出部、１０９…幅員付き歩道中心線データ保存部。
【図１】
2019211976.tif 000003
【図２】
2019211976.tif 000004
【図３】
2019211976.tif 000005
【図４】
2019211976.tif 000006
【図５】
2019211976.tif 000007
【図６】
2019211976.tif 000008
【図７】
2019211976.tif 000009
【図８】
2019211976.tif 000010
【図９】
2019211976.tif 000011
【図１０】
2019211976.tif 000012
【図１１】
2019211976.tif 000013
【図１２】
2019211976.tif 000014
【図１３】
2019211976.tif 000015
【図１４】
2019211976.tif 000016
【図１５】
2019211976.tif 000017
【図１６】
2019211976.tif 000018
【図１７】
2019211976.tif 000019
【図１８】
2019211976.tif 000020
【図１９】
2019211976.tif 000021
【図２０】
2019211976.tif 000022
【図２１】
2019211976.tif 000023
【図２２】
2019211976.tif 000024
【図２３】
2019211976.tif 000025
【図２４】
2019211976.tif 000026
【図２５】
2019211976.tif 000027
【図２６】
2019211976.tif 000028
【図２７】
2019211976.tif 000029
【図２８】
2019211976.tif 000030
【図２９】
2019211976.tif 000031
【図３０】
2019211976.tif 000032
【図３１】
2019211976.tif 000033
【図３２】
2019211976.tif 000034
【図３３】
2019211976.tif 000035
【図３４】
2019211976.tif 000036