(57)【要約】【課題】初期設定が容易で計算コストが小さい道路抽出法が望まれる。【解決手段】現在のウィンドウの所定の距離だけ、現在の方向の前方に道路の境界があるか判定するステップ１０１と、ウィンドウの前方が道路の境界と交差しなければ、前方に所定の距離だけ移動し、ステップ１０１に戻るステップ１０２と、ウィンドウの前方の右半分が道路の境界と交差すれば、方向を左に所定の角度だけ変更して、ステップ１０１に戻るステップ１０３と、ウィンドウの前方の左半分が道路の境界と交差すれば、方向を右に所定の角度だけ変更して、ステップ１０１に戻るステップ１０４とからなり、ウィンドウの軌跡を抽出された道路とする。【選択図】図１
2009080314.tif 000002
【特許請求の範囲】
【請求項１】
エッジ抽出された画像に対して、ウィンドウの初期位置と初期移動方向との指定を受ける初期設定部と、
該初期設定部により画定されるウィンドウが道路の中央に位置するように移動させるセンタリング部と、
該センタリング部によりセンタリングされたウィンドウを現在の移動方向の前方に第１の距離だけ移動させた場合に、ウィンドウが道路の境界と交差するか否かにより道路の境界が存在するか否かを判定する交差判定部と、
該交差判定部により、ウィンドウの前方が道路の境界と交差しないと判定されると、前方に第２の距離だけ移動させた後に前記交差判定部による処理を継続し、ウィンドウの前方が道路の境界と交差しないと判定されると、現在の移動方向を交差しない方向に所定の角度だけ回転させ、前記交差判定部による処理を継続するウィンドウ移動処理部と、を有し、
該ウィンドウ移動処理部によるウィンドウの移動の軌跡に沿って、道路を画定することを特徴とする道路抽出装置。
【請求項２】
ウィンドウの前方の全体が道路の境界と交差すると、道路の終端に達したものとして道路抽出処理を終了することを特徴とする請求項１に記載の道路抽出装置。
【請求項３】
エッジ抽出された画像に対して、ウィンドウの初期位置と初期方向とが指定されると、  該ウィンドウを、道路の中央に位置するように移動させる第１のステップと、
現在のウィンドウの第１の距離だけ、現在の方向の前方に、道路の境界があるか否かを判定する第２のステップと、
ウィンドウの前方が道路の境界と交差しなければ、前方に第２の距離だけ移動させた後に前記第２のステップに戻り、ウィンドウの前方の右半分が道路の境界と交差すれば、移動方向を左に第１の角度だけ変更して前記第２のステップに戻し、ウィンドウの前方の左半分が道路の境界と交差すれば、方向を右に第２の角度だけ変更して前記第２のステップに戻す第３のステップと、
ウィンドウの移動の軌跡に沿って、道路を画定する第４のステップと
を有することを特徴とする道路抽出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、道路抽出技術に関し、特に、衛星画像や航空画像に基づいて道路を抽出し地図を作成する技術に関する。
【背景技術】
【０００２】
道路抽出法に関しては、既に多くの手法が提案されている。
例えば、道路上にいわゆるリボンスネークを粗く置き、スネークのエネルギーを最小化することによってスネークを道路に沿うようにさせて道路を抽出する手法が報告されている（下記非特許文献１参照）。
【０００３】
また、高速道路のように鮮明なパターンの画像に対しては、重みが道路の中央で重く、端で軽いテンプレートを生成して、順次テンプレートを移動させながらテンプレートマッチングを繰り返す手法が試みられている（下記非特許文献２参照）。
さらに、領域分割を行った後に、細線化処理を行って道路領域の骨格線を抽出する手法も提案されている（下記非特許文献３参照）。
【０００４】
【非特許文献１】Laptev, I. et al.：Automatic extraction of roads from aerial images based on scale-space and snakes：URL=http://citeseer.ist.psu.edu/328566.html
【非特許文献２】Park, S-R. and Kim, T.：Semi-automatic road extraction algorithm from IKONOS images using template matching：22nd Asian Conference on Remote Sensing, vol.2, pp.1209-1213 (2001)
【非特許文献３】村山健二・他3名：分割K-平均法による領域分割結果を用いた航空写真からの道路抽出：写真とリモートセンシング、vol.42、no.2、pp.4-11 (2003)
【発明の開示】
【発明が解決しようとする課題】
【０００５】
非特許文献１に記載の手法では、スネークの初期設定に手間がかかり、しかも最小化の演算量が多いため計算コストが高くなるという問題がある。また、非特許文献２に記載の手法では、回転についても考慮する必要があるため、テンプレートマッチングに要する演算量が多く、計算コストが高くなるという問題点がある。さらに、非特許文献３に記載の手法では、細線化処理は雑音の影響を受けやすく、それを修正するために後処理に手間がかかるという問題がある。
【０００６】
本発明は、初期設定が容易であり、かつ、計算コストが小さい道路抽出法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一観点によれば、エッジ抽出された画像に対して、ウィンドウの初期位置と初期移動方向との指定を受ける初期設定部と、該初期設定部により画定されるウィンドウが道路の中央に位置するように移動させるセンタリング部と、該センタリング部によりセンタリングされたウィンドウを現在の移動方向の前方に第１の距離だけ移動させた場合に、ウィンドウが道路の境界と交差するか否かにより道路の境界が存在するか否かを判定する交差判定部と、該交差判定部により、ウィンドウの前方が道路の境界と交差しないと判定されると、前方に第２の距離だけ移動させた後に前記交差判定部による処理を継続し、ウィンドウの前方が道路の境界と交差しないと判定されると、現在の移動方向を交差しない方向に所定の角度だけ回転させ、前記交差判定部による処理を継続するウィンドウ移動処理部と、を有し、該ウィンドウ移動処理部によるウィンドウの移動の軌跡に沿って、道路を画定することを特徴とする道路抽出装置が提供される。前記第１の距離と前記第２の距離とは、予め決められて記憶装置に格納してＣＰＵが参照できるようにしておくのが好ましい。両方の距離は同じでも異なっても良い。また、所定の角度は、予め決められているのが好ましいが、一般的には鋭角であり、１５°程度が好ましい。交差の頻度が高ければ、所定の角度を小さくし、交差の頻度が低ければ、所定の角度を大きくするように制御しても良い。また、交差した座標を記憶させておき、この座標を道路の幅方向の画定に利用することもできる。また、ウィンドウの前方の全体が道路の境界と交差すると、道路の終端に達したものとして道路抽出処理を終了することが好ましい。
【０００８】
本発明の他の観点によれば、エッジ抽出された画像に対して、ウィンドウの初期位置と初期方向とが指定されると、該ウィンドウを、道路の中央に位置するように移動させる第１のステップと、現在のウィンドウの第１の距離だけ、現在の方向の前方に、道路の境界があるか否かを判定する第２のステップと、ウィンドウの前方が道路の境界と交差しなければ、前方に第２の距離だけ移動させた後に前記第２のステップに戻り、ウィンドウの前方の右半分が道路の境界と交差すれば、移動方向を左に第１の角度だけ変更して前記第２のステップに戻し、ウィンドウの前方の左半分が道路の境界と交差すれば、方向を右に第２の角度だけ変更して前記第２のステップに戻す第３のステップと、ウィンドウの移動の軌跡に沿って、道路を画定する第４のステップと、を有することを特徴とする道路抽出方法が提供される。
【０００９】
本発明は、上記ステップをコンピュータに実行させるためのプログラムであっても良く、或いは、プログラムを記録したコンピュータ読みとり可能な記録媒体であっても良い。
【発明の効果】
【００１０】
（１）最初にオペレータがウィンドウの初期位置と初期方向を指定するだけで、半自動的に道路を抽出するので、手間がかからない。
（２）最適化やテンプレートマッチングなどのような計算コストが掛かるプロセスを含まず、効率的に道路が求まる。
（３）エッジ画像に多少の雑音が存在しても、それに対して耐える能力を備えている。
【発明を実施するための最良の形態】
【００１１】
以下に、本発明の一実施の形態による道路抽出技術について図面を参照しながら説明を行う。図１は、本実施の形態による道路抽出処理の概要を示すフローチャート図である図２は、本実施の形態による道路抽出方法における道路とウィンドウとの関係を示す図である。図１に示すように、処理を開始すると（ｂｅｇｉｎ）、前処理として入力画像をクラスタリングにより画像分割し、エッジ検出演算子を適用して生成された画像に対して、ウィンドウの初期位置と初期方向とが設定されると（ステップ１０１）、ウィンドウを道路の中央に位置付けるように移動させる（ステップ１０２）。
【００１２】
図２（ａ）は、ウィンドウの初期位置と初期方向を指定するベクトルを矢印で示す図である。初期位置はベクトルの始点により指定され、ベクトルを挟む二本の線は道路の境界を示す線である。図２（ｂ）のベクトルは、点線で示された元のベクトル（図２（ａ））を２本の境界線の幅方向の中央に移動させた様子を示す図である。図２（ｃ）は、ベクトルから決まるウィンドウを示す図である。ウィンドウは、道路の幅をＷとすると、道路幅方向にＷ／２、道路の延在する方向にＷ／３程度の大きさで設けるのが好ましい。ベクトルの方向にウィンドウの移動を妨げる境界が存在しないので、ウィンドウはこの方向に所定の距離だけ移動できる。図２(d)はウィンドウが移動した結果を示す図である。ここで、点線はウィンドウの軌跡を示す。このようにして、現在のウィンドウについて、現在の方向の所定の距離だけ前方に道路の境界があるか否かを判定する（ステップ１０３）。ウィンドウの前方が道路の境界と交差しなければ（ＹＥＳ）、前方に所定の距離だけ移動させる（ステップ１０４）、ステップ１０３に戻る。図２（ｅ）は、境界線が曲がっている場合を示す。まず、ウィンドウは境界線と交差するまで現在の方向に移動を繰り返す。図２（ｆ）はウィンドウが移動して、ウィンドウの右側が境界線と交差した様子を示す図である。ウィンドウの前方の右半分が道路の境界と交差すれば、方向を左に所定の角度、例えば１５°程度、交差した境界と反対の境界の方向に進行方向を変更して（ステップ１０５）、ステップ１０３に戻る。図２（ｇ）は、ウィンドウが所定の角度だけ方向を左向きに変えた様子を示す図である。方向を変更した結果、ウィンドウは境界線と交差しなくなるため、新たな方向に向けて移動することになる。図２（ｈ）は、新たな方向に移動する様子を示した図である。ここで、図２（ｆ）の時点における矢印の始点位置を（ｘ，ｙ）として表し、方向を変更した後の始点の位置を（ｘｗ，ｙｗ）とする。このように、ウィンドウの前方の左半分が道路の境界と交差すれば、方向を右に所定の角度だけ変更して、ステップ１０３に戻る（ステップ１０６）。ウィンドウの前方の全体が道路の境界と交差すれば、道路の終端に達したとして、終了する（ステップ１０７）ウィンドウの軌跡（点線）を、抽出された道路の中心線として、道路を画定する。
【００１３】
以上に説明した道路抽出法は、障害物の間を通り抜ける自律走行ロボットの軌跡抽出にたとえると理解しやすい。道路の境界を障害物に対応させると、境界追跡はロボットの走行に対応する。ロボットは障害物の間を走行する。ロボットの右側が障害物に衝突しそうになると、ロボットは走行の向きを左側に変えて衝突を避ける。同様に、ロボットの左側が障害物に衝突しそうとなると、ロボットは走行の向きを右側に変えて衝突を避ける。本実施の形態による道路抽出法では、ウィンドウが境界との衝突を避けながら、境界の間をすり抜けて道路上を移動する。したがって、このウィンドウの軌跡が道路に他ならない。
【００１４】
図３は本実施の形態による道路抽出装置一構成例を示すハードウェアシステムの機能ブロック図である。図３に示す道路抽出装置は、入力装置と、出力装置と、抽出処理装置と、記憶装置と、を含んで構成されている。入力装置は、例えば、マウス３０１とキーボード３０２とがシステムに接続されている。マウス３０１とキーボード３０２とは、コマンドの起動やパラメータの入力などに使われる。出力装置としては、ディスプレイ３１４がシステムに接続されている。ディスプレイ３１４は、画像データ、システムの状態、および、入力のプロンプトなどを表示する。
【００１５】
道路抽出処理装置３０３は、初期設定モジュール３０４と、センタリングモジュール３０５と、交差計算モジュール３０６と、ウィンドウの移動モジュール３０７と、ウィンドウの方向変更モジュール３０８と、を含む。記憶装置３０９は、濃淡画像３１０、エッジ画像３１１、初期位置・方向データ３１２、および、ウィンドウ情報３１３を含む。初期設定モジュール３０４は、マウス３０１操作に応じて、初期位置・方向データ３１２の入力を受け付ける。センタリングモジュール３０５は、記憶装置３０９に格納されているエッジ画像３１１と初期位置・方向データ３１２と、にアクセスし、エッジに対するウィンドウのセンタリングの結果をウィンドウ情報３１３として記憶装置３０９内のウィンドウ情報３１３に書き込む。交差計算モジュール３０６は、エッジ画像３１１とウィンドウ情報３１３とにアクセスし、その結果に依存してウィンドウの移動モジュール３０７またはウィンドウの方向変更モジュール３０８を呼び出す。ウィンドウの移動モジュール３０７は、ウィンドウ情報３１３を更新し、濃淡画像３１０とエッジ画像３１１とにウィンドウの軌跡を描いた後に、交差計算モジュール３０６に制御を移す。ウィンドウの方向変更モジュール３０８は、方向の変更に応じてウィンドウ情報３１３を更新し、交差計算モジュール３０６に制御を移す。
【００１６】
図４（ａ）は、本実施の形態による道路抽出処理の流れを示すフローチャート図である。図４（ｂ）は、４点、(x, y)、(xc, yc)、(xr, yr)、(xl, yl)の間の位置関係を示す図である。座標(x, y)、(xc, yc)、(xr, yr)、(xl, yl)は、それぞれ、図２に示すベクトルの始点位置、終点位置、ウィンドウの右前側のコーナーの位置、ウィンドウの左前側のコーナーの位置である。
【００１７】
まず、ステップ４０１において、ベクトルの始点と終点とに対応する２点(x0, y0)と(x1, y1)とがシステムに入力される。ステップ４０２において、この２点を端点とする線分と水平線の成す角度tを算出する。角度ｔは、反時計回りに測るものとする。次に、ステップ４０３において、Centering関数を呼んで、道路の中央に位置する点(x, y)と点(x0, y0)付近における道路幅width（Ｗ）を求める。
【００１８】
次いで、ステップ４０４において、ウィンドウの長さlとウィンドウの幅の半分の長さwとを、道路幅width（Ｗ）から計算する。例示的に示すと、図２（ｃ）に示すように、道路幅Ｗは、ウィンドウ幅２ｗの２倍である（Ｗはｗの４倍である）。この程度であることが、経験的には好ましい。定数Ａと定数Ｂとは、経験から決められる数である。ここで、点(x, y)をウィンドウの代表点と呼ぶことにする。
【００１９】
ステップ４０５で、ウィンドウの代表点(x, y)から距離l、角度tにある点(xc, yc)を算出する。ステップ４０６とステップ４０７とで、２点(x, y)と(xc, yc)とを端点とする線分と垂直であり、かつ、点(xc, yc)から距離がwである点(xr, yr)と点(xl, yl)とを算出する。次に、ステップ４０８において、ブール値を返すcrossPoint関数を呼んで、２点(xc, yc)と(xr, yr)とを端点とする線分とエッジ画像上の境界線とが交差しているか否かをチェックする。ここで、crossPoint関数は、交差すれば値Tを返し、交差しなければ値Fを返す。２点(xc, yc)と(xl, yl)とを端点とする線分の場合にも、同様のチェックを行う。このチェックの結果は４通りに分かれる。
【００２０】
そのうち、いずれの線分も交差しない場合には（ステップ４０９）、ステップ４１０において、ウィンドウの代表点(x, y)から距離l、角度tの点(xw, yw)を算出し、ステップ４１１において、２点(x, y)と(xw, yw)とを端点とする線分を画像に描き、ステップ４１２において、ウィンドウの代表点を点(xw, yw)に移動する。２点(xc, yc)と(xr, yr)とを端点とする線分だけが交差する場合（ステップ４１３）、ステップ４１４で、角度tを所定の角度Dtだけ増加させる。２点(xc, yc)と(xl,yl)とを端点とする線分だけが交差する場合（ステップ４１５）、ステップ４１６において、角度tを所定の角度Dtだけ減少させる。両方の線分が交差する場合は処理を終了する。それ以外の３つの場合は、ステップ４０５に戻ってループする。
【００２１】
図５は、図４（ａ）のステップ４０３で呼んでいるCentering関数による詳細な処理例を示すフローチャート図である。まず、ステップ５０１において、入力点(x0, y0)から距離D、角度−tの点(x1, y1)を算出する。距離Dは道路の幅より十分長い値の定数である。次に、ステップ５０２で、crossPoint関数を呼んで、２点(x0, y0)と(x1, y1)とを端点とする線分と境界線との交点(xr, yr)を求める。ステップ５０３で、実際に交点が求まったか否かを判定する。交点が求まらなければ、Centering関数は値Fを返して処理を終了する。交点が求められれば、ステップ５０４からステップ５０５にかけて、入力点(x0, y0)から距離D、角度tの点(x1, y1)を算出し、前と同様にして交点(xl, yl)を求める。ステップ５０６で、実際に交点が求まったか否か判定する。交点が求まらなければ、Centering関数は値Fを返して処理を終了する。交点が求められれば、ステップ５０７とステップ５０８とで、２点(xr, yr)と(xl, yl)との中点(x, y)と距離widthとを算出した後、値Tを返して処理を終了する。
【００２２】
尚、crossPoint関数は、crossPoint(xs, ys, xe, ye, x, y)の形式で呼ばれる。(xs, ys)は線分の始点、(xe, ye)は線分の終点である。ステップ４０８で、(xe, ye)は(xr, yr)と(xl, yl)であり、ステップ５０２および５０５で(xe, ye)は始点から十分離れた点(x1, y1)になる。
【００２３】
図６は、図４（ａ）のステップ４０８と図５のステップ５０２とステップ５０５とで呼ばれているcrossPoint関数の詳細な処理例を示すフローチャート図である。crossPoint関数は、２点(xs, ys)と(xe, ye)とを引数として、この２点を端点とする線分と境界線との交点(x, y)があるか否かをチェックし、交点があれば値Tを、交点がなければ値Fを返す。尚、交点が複数ある場合は、点(xs, ys)に最も近い交点を求める。まず、ステップ６０１において、点(xs, ys)と点(xe, ye)との間の距離distanceを計算する。次に、ステップ６０２において、刻みstepをdistanceから算出する。これ以降は、変数tについてのループを形成している。１．５は、２０．５から３０．５程度が好ましい。まず、ステップ６０３で、変数tに初期値０．０を設定する。次に、ステップ６０４で変数tの値が１．０を超えているか否かを判定する。１．０を超えていれば、交点は存在しないため、値Fを返して処理を終了する。１．０を超えていなければ、ステップ６０５において、点(xs, ys)と点(xe, ye)とをt対(１．０、…、t)に内分する点(x,y)を算出する。ステップ６０６において、エッジ画像imgの点(x,y)が、境界線上にあるか否かを判定する。すなわち、白画素であるか否かを判定する。境界線上にあれば、値Ｔを返して処理を終了する。境界線上になければ、ステップ６０７において、変数tの値を刻みstepだけ増加させて、ステップ６０４に戻り、ループさせる。尚、エッジ画像imgは２値画像であり、値ＷＨＩＴＥを取る画素は境界線を表す。
【００２４】
図７は、図４（ａ）のステップ４１１で呼ばれているdrawLine関数の詳細を示すフローチャート図である。drawLine関数は、２点(xs, ys)と(xe, ye)とを引数として、この２点を端点とする線分を画像imgに描く。この関数とcrossPoint関数とはほぼ同一であり、前者がステップ７０６で画像imgに書き込みしていて、値WHITEの線分を描いているのに対して、後者がステップ６０６で画像imgの値を参照していて、境界線の画素か判断している点が異なる。
【００２５】
図８Ａ(a)は郊外を撮影した５００×５００画素の大きさの衛星画像の例を示す図である。図に示す衛星画像は、画像のほぼ中央を左右に横切る道路Ｒ１と、いくつかの正方形の建屋Ｈ１、Ｈ２、…と、を含んでいる。図８Ａ（ｂ）は、図８Ａ（ａ）の衛星画像に、エッジ検出演算子を作用させてエッジを取り出し、雑音を除去したものである。衛星画像が不鮮明であるため、Ｙ１で示すように、道路の領域と建屋との領域が一部で融合してしまっている。図８Ｂ（ｃ）は、道路の左側に初期位置と初期方向を設定して、本実施の形態による道路抽出法による処理を適用した結果を示す図である。初期位置での道路幅は１３．３画素である。ウィンドウの進行方向の長さと横方向の長さとは、それぞれこの道路幅の１／３と１／２とした。また、移動の距離は、道路幅の１／３方向の変更角度は１５度に設定した例を示す。方向の初期位置付近から衛星画像の右端まで道路のほぼ中心の線Ｌ１が生成されている。図８Ｂ（ｄ）は、元の衛星画像に生成された線を重ねた図である。多少ジグザグしているが道路Ｌ２が抽出されていることが分かる。尚、図８Ａ（ｂ）の画像のように、道路が大きく歪んでいる場合でも、抽出可能であることが本実施の形態による道路抽出技術の大きな特徴である。
【００２６】
以上に説明したように、本実施の形態による道路抽出技術は以下の利点を有する。
（１）最初にウィンドウの初期位置と初期方向が指定されると、自動的に道路を抽出することができ、処理に手間がかからないという利点がある。
（２）最適化やテンプレートマッチングなどのような計算コストを要するプロセスを含まず、効率的に道路を抽出することができる。
（３）エッジ画像に多少の雑音が存在しても、それに対して耐える能力を備えている。
【００２７】
尚、上記道路抽出技術は、画像中に連続的に延在する事物を抽出する際に用いることができる。道路以外にも河川などの抽出にも有る程度利用可能である。
【産業上の利用可能性】
【００２８】
本発明は、道路抽出装置に利用可能である。
【図面の簡単な説明】
【００２９】
【図１】本発明の一実施の形態による道路抽出処理の流れを示すフローチャート図である。
【図２】本実施の形態による道路抽出処理の様子を示す図である。
【図３】本実施の形態による道路抽出処理を実行するハードウェアシステムの一構成例を示す機能ブロック図である。
【図４】本実施の形態による道路抽出技術における処理の流れを示すフローチャート図である。
【図５】Centering関数の詳細な処理例を示すフローチャート図である。
【図６】crossPoint関数の詳細な処理例を示すフローチャート図である。
【図７】drawLine関数の詳細な処理例を示すフローチャート図である。
【図８Ａ】本実施の形態による道路抽出処理を衛星画像に適用した例を示す画像である。
【図８Ｂ】本実施の形態による道路抽出処理を衛星画像に適用した例を示す画像である。
【符号の説明】
【００３０】
３０１…マウス、３０２…キーボード、３０３…処理装置、３０４…初期設定モジュール、３０５…センタリングモジュール、３０６…交差計算モジュール、３０７…ウィンドウの移動モジュール、３０８…ウィンドウの方向変更モジュール、３０９…記憶装置、３１０…濃淡画像、３１１…エッジ画像、３１２…初期位置・方向データ、３１３…ウィンドウ情報、３１４…ディスプレイ
【図１】
2009080314.tif 000003
【図２】
2009080314.tif 000004
【図３】
2009080314.tif 000005
【図４】
2009080314.tif 000006
【図５】
2009080314.tif 000007
【図６】
2009080314.tif 000008
【図７】
2009080314.tif 000009
【図８Ａ】
2009080314.tif 000010
【図８Ｂ】
2009080314.tif 000011