(57)【要約】【課題】  画像中の線を識別または追跡する方法。【解決手段】  本方法は、線に属する始点を決定すること、検索窓を用いて線に属する複数の考え得る終点を識別すること、および、始点と終点を接続する複数の経路の値を計算することであって、それによって、最適な終点および経路を判定する、計算することを含む。本方法は、検索窓が非矩形であることを特徴とする。【選択図】  図１
2006004435.tif 000002
【特許請求の範囲】
【請求項１】
画像中の線を識別または追跡する方法であって、
線に属する始点を決定すること、検索窓を用いて前記線に属する複数の考え得る終点を識別すること、および、
最適な終点および／または経路を判定するために、前記始点と該終点を接続する複数の経路の値を計算することを含み、
前記検索窓は非矩形であることを特徴とする、画像中の線を識別または追跡する方法。
【請求項２】
値が計算される前記複数の経路は、その全体が前記検索窓内にある経路である請求項１に記載の画像中の線を識別または追跡する方法。
【請求項３】
前記検索窓は、始点に対応する頂点と、前記考え得る終点に対応する辺とによって画定される請求項１または２に記載の画像中の線を識別または追跡する方法。
【請求項４】
前記頂点が成す角度は、前記画像中の前記線の性質、例えば幾何学的形状、湾曲の程度に応じて可変である請求項３に記載の画像中の線を識別または追跡する方法。
【請求項５】
前記頂点が成す角度は、（ａ）前記線がほぼ直線である場合に小さく、例えば９０度未満または約４５度であるか、（ｂ）前記線が曲がりくねっている場合に大きく、例えば９０度よりも大きい、あるいは１８０度よりも大きいか、または（ｃ）前記画像の前記線の性質に関する知識がない場合に約９０度である請求項３または４に記載の画像中の線を識別または追跡する方法。
【請求項６】
前記検索窓は、前記頂点を前記始点とする扇形にほぼ対応する請求項１ないし５のいずれか一項に記載の画像中の線を識別または追跡する方法。
【請求項７】
前記終点は、前記扇形の円周部に沿って配置される請求項６に記載の画像中の線を識別または追跡する方法。
【請求項８】
前記複数の経路の値を計算するステップは、前記検索窓内の前記始点および終点を接続する直線および／または曲線経路を含む請求項１ないし７のいずれか一項に記載の画像中の線を識別または追跡する方法。
【請求項９】
複数の経路の値を計算し、最適経路を判定するために、Ｆ＊アルゴリズムのようなアルゴリズムを用いることを含む請求項１ないし８のいずれか一項に記載の画像中の線を識別または追跡する方法。
【請求項１０】
前記画像中の線を追跡するために、前記ステップを繰り返すことを含む請求項１ないし９のいずれか一項に記載の画像中の線を識別または追跡する方法。
【請求項１１】
画像中の線を識別または追跡するための検索窓であって、非矩形であり、好ましくは、ほぼ扇形の形状である、画像中の線を識別または追跡するための検索窓。
【請求項１２】
請求項１１に記載の例えばマスクの記憶を含む使用。
【請求項１３】
請求項１ないし１０のいずれか一項に記載の方法を実行する装置。
【請求項１４】
請求項１ないし１０のいずれか一項に記載の方法を実行するコンピュータプログラム。
【請求項１５】
請求項１４に記載のコンピュータプログラムを記憶するコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像中の線を検出または追跡する方法および装置に関する。
【背景技術】
【０００２】
M. A. Fischler、J. M. TenenbaumおよびH. C. Wolf著「マルチソース知識の統合技法を用いた低解像度の航空写真中の道路および線構造の検出（Detection of roads and linear structures in low-resolution aerial imagery using a multisource knowledge integration technique）」（CVGIP, 15, pp. 201-223, 1981）は、道路検出に関する文献の重要部分の先駆である。これは、Dudaの道路演算子（Duda Road Operator）を初めて用い、Ｆ＊アルゴリズムを導入している。
【０００３】
アルゴリズムの説明：検索領域（画像全体である場合もある）中の各画素に、その画素が道路に属する確率を示すコストを割り当てる。次に、Ｆ＊アルゴリズムを用いて、始めと終わりの区切り（事前に設けておかなければならない）間の最適経路を見付ける。この方法は、画像中の複数の領域に適用することができるが、これらの領域は分離しており、本文献中に、隣接領域に沿って道路を追跡する方法に対する言及はない。
【０００４】
N. Duta著「パンクロマチックＳＰＯＴ衛星画像における道路検出（Road Detection in Panchromatic SPOT Satellite Images）」（Proceedings ICPR, 2000, Track4: Applications, Robotics, Systems and Architectures, pp. 308-311）は、２段階アルゴリズムを記載している。第１段階では道路シードを見付け、第２段階ではシードを追跡または拡張する。
【０００５】
このアルゴリズムにおいて、シードは、視覚的に等質（homogeneous）であり、近隣の背景とは明確に分離されている幅２〜４画素、長さ１０〜１５画素の平行四辺形の形状の画像領域である。これは直線状である必要はない。
【０００６】
追跡段階において、このアルゴリズムは、シードを両端で拡張しようとする。拡張は常に直線状である。シードの一方の端部から開始して、アルゴリズムは、シードを扇形（この論文中では−４５°，＋４５°であるが、道路の幾何学的形状の事前知識に依存する）内で拡張するいくつかの直線セグメントを規定し、各セグメントが道路の一部である確率を計算する。この確率は、セグメント内の画素の等質性および当該セグメントと近隣の背景の分離性の尺度として定義される。いずれかのセグメントの確率が閾値を越えた場合、シードは最良のセグメントに沿って拡張され、プロセスは反復的に継続される。
【０００７】
R. Bonnefon、P. DhereteおよびJ. Desachy著「動的計画法を用いたＳＰＯＴ画像上の線形特徴の自動追跡（Automatic tracking of linear features on SPOT images using dynamic programming）」（Proceedings EOS/SPIE EUROPTO'1999 Image Signal Processing for Remote Sensing V, pp. 116-124, Sept. 1999）は、別の線追跡方法を記載している。
【０００８】
始点および開始方向に基づいて、始点を１列目の中央に、いくつかの候補点を最後の列に有する小さな検索（矩形）窓を定義する。各候補点について、検索窓中の各点に、その点の強度と、始点および候補点の強度との関数としてコストを割り当てる。次に、Ｆ＊アルゴリズムを用いて、始点と候補点の間の最適経路を判定し、経路に沿った放射測定の等質性と、Ｆ＊アルゴリズムが返した経路の総コストとを考慮して経路にマークを付ける。最も高いマークを有する候補点を新たな始点とし、新たな検索窓を用いてプロセスが継続される。図１は検索窓を示し、図２はBonnefon等の方法の追跡構造を示す。
【０００９】
本発明は、線に関する何らかの情報（シード）が得られた際に線構造を追跡する問題に関する。シードとは、検索対象である線の一部であることが分かっている短いセグメントである。
【００１０】
本アルゴリズムは、衛星画像中の道路を検出するために開発されたものであるが、他の線構造の検出にも適用することができる。
【００１１】
Fischler等は、領域中の線を検出するが、隣接領域間の連続した線構造に対して追跡を使用しない。
【００１２】
Dutaは、追跡を使用するが、拡張は常に直線セグメントである。このアルゴリズムの主な制限は、グローバルスケールでは湾曲に対処できる（或る拡張セグメントと次の拡張セグメントの間に角度を認める）が、ローカルスケールでは湾曲に対処できない（拡張セグメントは常に直線である）ことである。
【００１３】
Bonnefon等は、矩形窓を用いて追跡を行う。このアルゴリズムは、非線形の拡張を結果として生じることができるが、使用する検索窓（矩形）のために、追跡できる線にいくつかの制限がある。第１の問題として、窓内の各点の値はその点が道路である確率を表すため、最良の候補として選択される可能性が最も高い候補は、最後の列の中央の点であることが明らかである。これは、その始点からの距離が最短であるためである。これは、道路の区分的な線形性を強制するため、正のバイアスとして考えることができるが、多くの場合に、最適でない候補が選択されるという結果を生じ得る。
【００１４】
この方法のもう１つの問題は、幾何学的な観点から明らかに誤った経路を最適なものとして選択することを許容することである。例えば、このアルゴリズムでは、図３の経路が最適経路として選択される可能性があるが、道路の幾何学的な制約から、特に検索窓のサイズが予期される道路の幾何学的特徴（例えば湾曲の程度）に応じて決められていることを考慮すると、これが道路である可能性は低い。
【００１５】
このアルゴリズムは、開始方向に垂直な候補点を見付ける。この戦略は、ＬターンまたはＵターンのような特定の道路構造を追跡することを不可能にする可能性がある（図４）。この種のターンは、検索窓がどんなに大きくても追跡されない。
【００１６】
このアルゴリズムはまた、検索する道路の点はいずれも始点よりも先（推定開始方向の方向）にあると仮定する。これは、ひどく曲がりくねった道路ではそうとは限らない（図５を参照）。このシナリオにおいて、このアルゴリズムは、窓のサイズに関係なく、道路のいくつかの点を見落とすことになる。
【発明の開示】
【発明が解決しようとする課題】
【００１７】
本文書に記載される発明は、好ましくは扇形形状の窓を用いることによって、これらの限界に対処する。
【課題を解決するための手段】
【００１８】
本発明の態様は添付の特許請求の範囲に記載される。
【００１９】
一態様によれば、発明概念は、新規の検索窓（扇形形状）に基づく追跡アルゴリズムである。この新規の検索窓は、通常の道路の幾何学的形状に従来の検索窓よりも適しているため、従来の矩形窓に伴う問題に対処する。この新規の検索窓を用いた場合、幾何学的な観点から道路に属する可能性が高い画素のみが、窓中の最適経路の判定に用いられる。この新規の検索窓は、ＬターンあるいはＵターンのような特定の道路構造にも対処することができる。本発明の実施形態が呈する実施上の複雑さは、従来の矩形窓に基づく方法と同じである。
【００２０】
添付図面を参照して本発明の一実施形態を説明する。
【発明を実施するための最良の形態】
【００２１】
この実施形態のアルゴリズムは、検索窓および動的計画法（Ｆ＊アルゴリズム）を用いて、最も可能性の高い経路に沿ってシードを拡張する。本アルゴリズムは、画像中の全てのシードの両端に適用される。このプロセスの開始時において、画像中の各点の値は、その点が線構造の一部である確率を表す。これは、Dudaの道路演算子等の適切な既知の技法を用いて行うことができ、シードを判定するために用いることができる。
【００２２】
本実施形態のアルゴリズムにおいて使用される検索窓は、矩形ではなく扇形の形状を有する。各シードの各端部に対して扇形を配置する。その際、扇の頂点（始点）はシードの最後の点となり、扇の向きは線の方向の推定に基づき、扇の角度は画像中の線の幾何学的形状（湾曲の程度）の事前知識の関数となるようにする。例えば、追跡される線が衛星画像中の道路であり、画像中に存在する道路は高速道路または直線道路であることが分かっている場合、扇の角度は小さくなるはずである（通常４５度）。道路がひどく曲がりくねっていることが分かっている場合（すなわち山道）、角度は大きくなるはずである（１８０度より大きい場合もある）。道路の幾何学的形状の事前知識が得られない場合、大抵は９０度という値で上手くいくはずである。拡張端部として考慮される点は、扇形の境界を定める円周上に位置する。始点と各候補点の間の最適経路のコストの計算には、Ｆ＊アルゴリズムが用いられる。コストの低い候補を選択し、そのコストが特定の閾値を満たす場合、追跡は、その候補を別の扇形の検索窓の始点として継続することになる。図６、図７および図８は、検索窓および追跡手順を図式的に説明する。この線の拡張は、拡張を続けるべき適切な候補がなくなった時点で、あるいは画像の境界に到達した時点で終了する。次に、本アルゴリズムをシードのもう一方の端部、ならびに画像中の残りのシードに適用する。
【００２３】
本方法の利点を以下に示す。
・始点と全ての候補点の間の距離は理論上全く同じである。実際には、距離は、デジタル化のために略同じにしかならない。検索窓が矩形である場合、これらの距離間に顕著な差はない。
・扇形の中の画素のみを最適経路の一部として選択することができる。これにより、図３に示すような状況を防ぐことができる。通常の道路では、始点と開始方向の知識のおかげで道路の位置については高い確信があるため、始点の近傍において、最適経路の一部である可能性がある画素の数はごく限られている。この数は始点から離れるほど増える。扇形の検索窓はこの挙動に適合する。
【００２４】
本方法では、道路の位置に関する仮定は行わない。予期される道路の幾何学的形状がひどく曲がりくねっていることが分かっている場合、本アルゴリズムは、図９に示すように、始点よりも前に位置する道路の点、あるいはＬターンまたはＵターンに対処することができる。
【００２５】
アルゴリズムの他の特徴として以下のものがある。
・安全係数として、追跡は、候補点自体からではなく、（始点と候補点の間の最適経路に沿って）１つまたは２つ前の点から継続することができる。
【００２６】
図１０は、本アルゴリズムのフローチャート図を示す。
【００２７】
本アルゴリズムは本来、衛星画像中の道路を追跡するために設計されているが、鉄道線（train lines）、運河、海岸線、および一般に、衛星画像または航空画像中のあらゆる細い線形構造といった他の構造を追跡するためにも用いることができる。
【００２８】
リモートセンシングのシナリオ以外では、本アルゴリズムは顔の皺の検出にも用いられた。本アルゴリズムはまた、医用画像に適用することもできる。
【００２９】
本実施形態は、検索窓に扇形を使用するが、三角形のような他の非矩形形状を用いることもできる。頂点（始点）で成す角度は、０度〜３６０度の間で変化することができ、固定または可変であってもよく、用途（application）または画像に関する知識、例えば画像の性質、幾何学的形状、あるいは画像中の線の通常の湾曲の程度に関する知識によって求めることができる。
【００３０】
本明細書において、画像という用語は、文脈から明らかである場合を除き、画像全体または画像の一領域を意味する。同様に、画像の領域は画像全体を意味し得る。画像は、枠またはフィールドを含み、静止画、または映画あるいはビデオ等の画像シーケンス中の画像または関連する画像グループ中の画像に関連する。
【００３１】
画像は、グレイスケール画像またはカラー画像、または別のタイプのマルチスペクトル画像、例えばＩＲ、ＵＶあるいは他の電磁画像、または音響画像等であってもよい。
【００３２】
本発明は例えば、コンピュータシステムにおいて、適切なソフトウェアおよび／またはハードウェアの変更とともに実施することができる。例えば、本発明は、プロセッサまたは制御装置等の制御または処理手段、メモリ、磁気記憶装置、ＣＤ、ＤＶＤ等といった画像記憶手段を含むデータ記憶手段、ディスプレイあるいはモニタまたはプリンタ等のデータ出力手段、キーボード等のデータ入力手段、およびスキャナ等の画像入力手段、またはこうした構成要素の任意の組み合わせならびに追加構成要素を有するコンピュータ等を用いて実施することができる。本発明の態様は、ソフトウェアおよび／またはハードウェアの形態で、または特定用途向け装置において提供されるか、またはチップ等の特定用途向けモジュールを設けることができる。本発明の一実施形態による装置内のシステムの構成要素は、他の構成要素から遠隔して、例えばインターネットを介して設けることができる。
【図面の簡単な説明】
【００３３】
【図１】従来技術の方法の検索窓を示す図である。
【図２】従来技術の方法の追跡構造を示す図である。
【図３】従来技術の方法の考え得る経路を示す図である。
【図４】従来技術の方法の検出されない経路を示す図である。
【図５】従来技術の方法の別の検出されない経路を示す図である。
【図６】本発明の一実施形態の方法の検索窓の概略図である。
【図７】図６の検索窓をデジタル化したものを示す図である。
【図８】本発明の一実施形態の方法による線追跡を示す図である。
【図９】本発明の一実施形態の方法によって追跡することのできる線を示す図である。
【図１０】本発明の一実施形態の方法のフロー図である。
【図１】
2006004435.tif 000003
【図２】
2006004435.tif 000004
【図３】
2006004435.tif 000005
【図４】
2006004435.tif 000006
【図５】
2006004435.tif 000007
【図６】
2006004435.tif 000008
【図７】
2006004435.tif 000009
【図８】
2006004435.tif 000010
【図９】
2006004435.tif 000011
【図１０】
2006004435.tif 000012
【外国語明細書】
2006004435.tif 000013
2006004435.tif 000014
2006004435.tif 000015
2006004435.tif 000016
2006004435.tif 000017
2006004435.tif 000018
2006004435.tif 000019
2006004435.tif 000020
2006004435.tif 000021
2006004435.tif 000022
2006004435.tif 000023
2006004435.tif 000024
2006004435.tif 000025
2006004435.tif 000026
2006004435.tif 000027
2006004435.tif 000028