(57)【要約】【課題】  ＭＳＴを見付けるために必要な計算の複雑性が中程度であり、続くセグメンテーションの実行が容易であって、セグメントの数を厳密に指定することを可能とする画像セグメンテーション方法を提供すること。【解決手段】  グラフ理論技法を使用した画像セグメンテーション方法であって、画像のピクセルがグラフの頂点で表される画像セグメンテーション方法。最小全域木が生成され、木の辺が形態学的特性に従って続けて除去されて全域森が残され、全域森の木が画像のセグメントに対応する。除去する辺の選択は、木のエネルギー関数およびその辺の除去により生成される木のエネルギー関数に依存することができる。【選択図】  図７
2008522273.tif 000002
【特許請求の範囲】
【請求項１】
画像のピクセルがグラフの頂点で表され、ピクセルの隣接が前記グラフの辺で表され、前記辺に、隣接するピクセル間の非類似性測定値を表す重みが割り当てられ、前記グラフの最小全域木（またはその近似）が生成され、辺が前記最小全域木から続けて除去されて全域森が生成され、該全域森の木が前記画像のセグメントに対応する、画像セグメンテーション方法であって、
前記全域森から除去する辺の選択が、前記森の全体の頂点または辺にわたって計算される形態学的特性に依存する、画像セグメンテーション方法。
【請求項２】
辺を選択するための判断基準は、前記辺から該辺が存在する木の葉までの距離の測定値に依存する、請求項１に記載の画像セグメンテーション方法。
【請求項３】
辺を選択するための判断基準は、前記辺の除去によって生成される２つの木の測定値に依存する、請求項１に記載の画像セグメンテーション方法。
【請求項４】
前記辺のための判断基準は、前記辺を含む前記木の中のピクセルの関数と前記辺の除去により生成される２つの木の中のピクセルの関数の値の和との差である、請求項３に記載の画像セグメンテーション方法。
【請求項５】
前記関数はエネルギー関数である、請求項４に記載の画像セグメンテーション方法。
【請求項６】
木の中のピクセルの前記エネルギー値は、前記木の中のピクセルの前記ピクセル値と前記木の平均ピクセル値との二乗差に関連する、請求項５に記載の画像セグメンテーション方法。
【請求項７】
前記辺を選択するための判断基準は、前記辺の除去により生成される２つの木のサイズの測定値に依存する、請求項３に記載の画像セグメンテーション方法。
【請求項８】
サイズは木を形成する頂点の数として測定される、請求項７に記載の画像セグメンテーション方法。
【請求項９】
木の各辺の前記測定値は再帰アルゴリズムにより計算される、請求項１乃至８のいずれか１項に記載の画像セグメンテーション方法。
【請求項１０】
前記測定値は、前記木の葉に接合する第１の辺のセットに対して初期値に設定され、前記第１の辺のセットに接合する次の辺のセットに対して増分または累積され、すべての辺が検討されるまでこのプロセスが繰り返される、請求項９に記載の画像セグメンテーション方法。
【請求項１１】
前記測定値は前記木の葉に接合する辺の初期値に設定され、これら辺は一時的に除去され、前記測定値が増分または累積され、残っている辺がなくなるまでこのプロセスが繰り返される、請求項９または１０に記載の画像セグメンテーション方法。
【請求項１２】
辺の重みが前記累積プロセスに含まれる、任意の請求項１１に記載の画像セグメンテーション方法。
【請求項１３】
前記測定値の累積は、前記木に残っている葉が２枚になったときに中止され、前記測定値は前記木の残りの葉に対して一定の値に設定される、請求項１１または１２に記載の画像セグメンテーション方法。
【請求項１４】
前記測定値は、請求項９乃至１３のいずれか１項に記載のアルゴリズムと略同様の結果を生成するアルゴリズムを使用して計算される、請求項２に記載の画像セグメンテーション方法。
【請求項１５】
前記辺を選択するための判断基準は前記グラフの前記ピクセル値に依存する、請求項１乃至１４のいずれか１項に記載の画像セグメンテーション方法。
【請求項１６】
前記頂点または辺を除去するプロセスは、前記グラフの全体の前記頂点または辺にわたって所定の走査順で実行される、請求項１乃至１５のいずれか１項に記載の画像セグメンテーション方法。
【請求項１７】
前記走査順はラスタパターンである、請求項１６に記載の画像セグメンテーション方法。
【請求項１８】
前記辺を選択するための判断基準は前記グラフの前記辺の重みに依存する、請求項１乃至１７のいずれか１項に記載の画像セグメンテーション方法。
【請求項１９】
選択される辺は、前記辺の重みと請求項２乃至１５のいずれか１項により導出される前記測定値との積が最大の辺である、請求項１８に記載の画像セグメンテーション方法。
【請求項２０】
前記辺の選択前に、辺を除去すべき木の選択が行われる、請求項１乃至１９のいずれか１項に記載の画像セグメンテーション方法。
【請求項２１】
前記木を選択するための判断基準は、以下の特性、すなわち前記木の前記頂点の計数、前記木の辺の平均重み、前記木の辺の合計重み、前記ピクセル値の関数、および前記木の辺の重みの関数のうちの任意またはすべての特性の組み合わせに依存する、請求項２０に記載の画像セグメンテーション方法。
【請求項２２】
画像のピクセルがグラフの頂点で表され、ピクセルの隣接が前記グラフの辺で表され、前記辺に、隣接するピクセル間の非類似性の測定値を表す重みが割り当てられ、前記グラフの最小全域木（またはその近似）が生成され、辺が前記最小全域木から続けて除去されて全域森が生成され、該森の木が前記画像のセグメントに対応する画像セグメンテーション方法であって、
前記全域森から除去する辺の選択が、辺の除去により生成される２つの木の測定値に依存する、画像セグメンテーション方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理または映像処理あるいはその両方に関し、特に、グラフ理論技法を使用しての画像データのセグメンテーションに関する。
【背景技術】
【０００２】
セグメンテーションは、ノイズ軽減ならびに画像データおよび映像データの圧縮を含む多くの用途で有用であり、多種多様な画像セグメンテーション手法がこれまで提案されてきた。このような提案には、閾値処理、ウォーターシェッドアルゴリズム（watershed algorithm）、形態学的スケール−スペース変換（morphological scale-space transform）またはフィルタリング、領域分割・併合、クラスタ化、周波数領域技法、および動き推定を含む技法が含まれる。しかし、低から中程度の処理リソースを使用してマルチコンポーネント画像の良質な階層的セグメンテーションを生成する手法は、これら手法の中にもしあったとしても少数である。
【０００３】
本発明は、グラフ理論として知られている数学の分野からのいくつかの概念を用いる。グラフ理論において用いられる用語の簡単な説明は以下のとおりである。
【０００４】
グラフは、線（辺として知られている）で共に結び付けることができる点（頂点として知られている）からなる。そのグラフの一例を図１に示す。
【０００５】
頂点次数とは頂点に接合する辺の数である。図１では、頂点次数の範囲は０〜３である。頂点は、次数１を有する場合に葉と呼ばれ、図１のグラフには３つの葉がある。
【０００６】
辺および頂点は両方とも、関連する数または重みを有することができる。これら重みはある物理的意味を有することができ、たとえば、頂点が町を表し、辺が道を表すグラフでは、辺の重みは道の長さを表し得る。
【０００７】
グラフＧの部分グラフとは、頂点がＧの頂点の部分集合であり、かつ辺がＧの辺の部分集合であるグラフである。部分グラフは、Ｇのすべての頂点を有する場合にＧの全域部分グラフである。Ｇ中の経路は、各辺が前の辺と頂点を共有する別個の辺の集合である。より厳密な定義については、非特許文献１を参照のこと。
【０００８】
木とは、任意の所与の頂点から他の任意の頂点までに厳密に１つの経路しかないグラフである。森とは、木の不連結集合である。グラフＧの全域木または全域森とは、Ｇの全域部分グラフである木または森である。辺重み付きグラフにおいて、最短または経済的全域木としても知られている最小全域木（ＭＳＴ）とは、木の中の辺の重みの和を最小化する全域木である。
【０００９】
辺重み付きグラフの最小全域木を見つける既知のアルゴリズムが存在している。１つはクルスカル（Kruskal）のアルゴリズムであり、これは部分最小全域木の集合を保持し、頂点が別の全域木にある重み最小（または最も軽い）の辺を繰り返し足していく。もう１つはプリム（Prim）のアルゴリズムであり、これは、１つの頂点から始まり、木をまだその木に入っていない頂点に接合する最軽量の辺を繰り返し足していき、次いでその頂点を木に入れることによって木を構築していく。以下にさらに詳細に説明する図４および図５において、図５は図４の最小全域木を示す。
【００１０】
グラフ理論の画像への適用についてこれより検討する。グラフの頂点を用いてピクセルを表し、辺を用いてピクセルの隣接を表すことができる。本明細書では、一方のピクセルが他方のピクセルのすぐ上、すぐ下、すぐ左、またはすぐ右にある場合、２つのピクセルが隣接し、したがってそれら２つのピクセルに接合する辺がある。これは隣接の４連結定義であり、６連結定義または８連結定義を用いることも可能である。４連結定義を用いる場合、画像は図２に示すグラフで表すことができる。画像境界上のピクセルを表していない各頂点の次数は４である。なお、グラフ理論において用いられる「辺」なる言葉は、画像のエッジの概念または画像の境界とはまったく関係がない。
【００１１】
このようなグラフでの辺の重みを用いて、隣接するピクセル間の相違の、ある測定値を表すことができる。たとえば、輝度画像では、辺の重みを、２つの輝度値の絶対差として定義することができる。
【００１２】
図３は、示すピクセル値を有する例示的な５×４輝度画像を示し、図４は、隣接するピクセル値の絶対差に等しい辺の重みが関連付けられた、この画像を表すグラフを示す。
【００１３】
ＭＳＴは、画像セグメンテーションアルゴリズムのベースとして使用することができる。辺が木から除去されると２つの木が形成され、各木が画像の文脈の中で、頂点、すなわち画像のセグメントの連結された部分集合を記述することが分かる。したがって、画像をＮ個のセグメントに分けるには、Ｎ−１の辺がＭＳＴから除去される。除去するものとして選択される辺が単に、ＭＳＴ中のＮ−１の最大重み（または最大重量）の辺であることがこれまでに提案されている。たとえば、図５で表される画像を２つのセグメントに分けるには、重み４を有する辺が除去されて、図６に示すセグメンテーションが生成される。
【００１４】
３つのセグメントが必要であれば、２番目に最も重い辺（重み３を有する）も除去されて、図７に示すセグメンテーションが生成される。
【００１５】
【非特許文献１】Bollobas, Bela. Graph theory - an introductory course. Springer-Verlag, New York, 1979
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかし、この方法にはいくつかの欠点があることが分かっている。
【００１７】
本発明の目的は、改良された画像セグメンテーション方法を提供することである。
【課題を解決するための手段】
【００１８】
本発明の第１の態様によれば、画像のピクセルがグラフの頂点で表され、ピクセルの隣接がグラフの辺で表され、辺に、隣接するピクセルの非類似性の測定値を表す重みが割り当てられ、グラフの最小全域木（またはその近似）が生成され、辺が最小全域木から続けて除去されて全域森が生成され、全域森の木が画像のセグメントに対応する画像セグメンテーション方法であって、全域木から除去される辺の選択が、森の頂点または辺の形態学的特性に依存する、画像セグメンテーション方法が提供される。
【００１９】
本発明者らが明らかにした特に不利な点は、多くの場合に、上述した従来技術による基準を用いて辺を選択することにより、セグメントのサイズに巨大な不均衡があることである。ＭＳＴを見つける従来技術によるプロセスでは、元のグラフから最も重い辺の多くが除去されるが、残っている辺の中で最も重い辺が多くの場合にその木の葉の近傍に見られることが分かっている。これは、重い辺を除去すると、多くの場合に１つのピクセルしか有さない新しいセグメントが生成されることを意味する。
【００２０】
本発明は、各段階でＭＳＴからどの辺を除去すべきかを選択する新規の方法を用いることにより従来技術の制約を解消する。本発明の裏にある概念は、辺の除去により妥当なサイズのセグメントが生成される可能性の測定値を使用することにある。
【００２１】
好ましくは、辺の選択基準は、辺からその辺が存在する木の葉までの距離測定値に依存する。別法として、基準は、辺の除去により発生する２つの木に依存することができる。一実施形態では、基準はサイズ測定値に依存することができ、たとえばサイズ測定値に頂点の数を使用することができる。別の実施形態では、基準は、辺を含む木の中のピクセルの関数と、辺の除去により発生する２つの木の中のピクセルの関数の値の和との差に依存することができる。
【００２２】
この新規のアルゴリズムには非常に魅力的ないくつかの特徴がある。ＭＳＴを見付けるために必要な計算の複雑性が中程度であり、続くセグメンテーションの実行が非常に容易である。閾値ベースのいくつかのアルゴリズムと異なり、セグメントの数を厳密に指定することが可能である。特に、このアルゴリズムは、好ましくは、所与の数のセグメントへのセグメンテーションが常に、より多くのセグメントへのセグメンテーションの内に含まれるという点で階層的である。この方法は、マルチコンポーネント画像データ（たとえば、Ｒ、Ｇ、Ｂの値で記述される画像）に対しても機能する。２つ以上の成分で記述される画像、たとえばＲＧＢ画像では、辺の重みは、成分間の絶対差または二乗差の和、最大絶対差、または他の任意の適した測定値であってよい。
【００２３】
本発明は、本明細書において実質的に説明する方法を実施するように適合される装置であって、一実施形態では、デジタル回路を含むことができる装置も提供する。本発明は、データ圧縮方法、データ圧縮装置、および他の画像または映像処理アプリケーションで具現することができる。
【００２４】
本発明について、添付図面を参照して単なる例としてこれより説明する。
【発明を実施するための最良の形態】
【００２５】
本明細書では「セクルージョン（seclusion）」と呼ぶ新規の特性を、セグメンテーションの各段階で画像中のあらゆるピクセルに対して計算することができる。木の葉が「露出」していることを考えると、本明細書では、ある意味で葉から「遠い」頂点が「セクルード（seclude：分離）」されるものと考える。そして、セクルージョンとは頂点がセクルードされる程度である。
【００２６】
セクルージョンは、以下のアルゴリズムによって木または森に対して計算することができる。
【００２７】
・現セクルージョン値Ｓを０に設定する。
【００２８】
・森に辺が残っている場合、
・Ｓを増分させ、
・すべての葉の頂点のセクルージョンをＳに設定し、
・すべての葉の頂点およびそれに接合する辺を除去し、
・１つの頂点が残っている場合、セクルージョンをＳ＋１に設定する。
【００２９】
図８は、図５のグラフのあらゆるピクセルに対してセクルージョンがどのように計算されるかを示す。各段階において、除去された葉を白色で示す。
【００３０】
木または森の中のすべての頂点に対してセクルージョンを計算する方法について説明した。辺のセクルージョンは、２つの頂点のセクルージョン、たとえば２つのセクルージョン値のうちの最小値として定義することができる。図５の辺のセクルージョンマップを図９に示す。
【００３１】
別法として、辺のセクルージョン値を、上記セクルージョンアルゴリズムを変更したものを使用して直接計算することもできる。
【００３２】
除去する辺を選択するには、元の辺の重みと辺のセクルージョン値が、たとえば乗算によって結合される。図１０は、元の辺の重みとセクルージョンマップとの積を示す。
【００３３】
画像を２つのセグメントにセグメント化するには、結合値１８を有する辺が選択されて、図１１に示すセグメンテーションが生成される。セグメンテーションプロセスを続けるために、セクルージョンマップが図１１に示す森に対して再び計算される。その結果として得られる頂点セクルージョンマップを図１２に示し、辺セクルージョンマップを図１３に示す。図１４は、新しいセクルージョン値と辺の重みとの積を示す。
【００３４】
整数処理が用いられている場合に多く発生するように、ここで次の最高辺値の選択について曖昧さが生じる。同点の辺を、セクルージョンの高いほうを優先して重み付ける場合、値８を有する２つの辺のうちの左側にある辺が選択され、図１５に示すセグメンテーションが得られる。
【００３５】
上記例は、ＭＳＴセグメンテーションがプロセスの初期段階で非常に小さなセグメントを生成しないようにすることの保証を助けるためにセクルージョンマップをどのように用いることができるかを示している。もちろん、セクルージョンに付された重要度と重い辺で森を切断することの重要度との間にはトレードオフがある。このトレードオフは、セクルージョンと辺の重み付けを組み合わせる関数の選択に反映させることができる。
【００３６】
セクルージョンは、辺または頂点からの木の葉までの距離を推定するという点で「一次元」測定値として考えることができる。セクルージョンプロセスへの単純な変更を用いて、頂点の数、すなわち辺の除去によって発生する２つの木の「面積」を測定することができる。この変更では、測定される数量は、除去中の葉に関連する数量を、その葉が接続していた頂点に加算することによって累積される。
【００３７】
上述したセクルージョン測定または変更された測定のいずれでも、重みの付いたセクルージョン値が直接計算されるように、再帰的プロセスに、辺の重み自体を累積することをさらに含むことができる。この場合、除去する辺の選択のためにセクルージョン値を辺の重みで乗算する必要はなく、単に重み付き測定値を最大限に利用するだけである。
【００３８】
実際の画像をセグメント化する際のセクルージョン処理の利点についてこれより説明する。図１６は、３６０×２８８ピクセルにダウンコンバートされた、ＥＢＵ標準テストスライドセットからの「幾何学的デザインの池（formal pond）」画像の輝度成分を示す。図１７および図１８は、上述した従来技術によるＭＳＴ手法を用いてこの画像を６４セグメントおよび４０００セグメントのそれぞれにセグメント化しようとした結果得られるセグメント境界を示し、図１９は、ＭＳＴ手法と共に上述したセクルージョン処理を用いて６４セグメントにセグメンテーションした結果を示す。
【００３９】
セクルージョンマップは厳密に計算する必要はない。たとえば、セクルージョンマップの良好な近似を、処理がラスタ走査パターンを辿るにつれて森から「配置済み」の葉を除去することにより得ることができる。この短縮プロセスを図２０に示す。
【００４０】
この短縮は非対称であり、必然的に不完全であるが、特定の実施形態では、アルゴリズムの全体の性能に及ぼす影響はわずかである。たとえば、図２１は、図１９において用いられる「正しい」セクルージョン処理と比較するための、「幾何学的デザインの池」の６４領域へのセグメンテーションに対する短縮の影響を示す。
【００４１】
同様の短縮を、上述したセクルージョン測定値を変更したものに対して用いることができる。
【００４２】
ＭＳＴへの近似を見つけることにより、処理時間を短縮することも可能であり得る。たとえば、プリムのアルゴリズムの動作中、接合する辺の最小の重みを探して木全体を探索する必要があらゆる段階であるわけではないように、辺の重みがある基準に従って、たとえば予め計算された辺の重みの分布に基づいて「十分に小さい」と考えられる場合にその辺を加算することができる。
【００４３】
本発明に対するさらなる改良についてこれより述べる。セグメンテーションプロセスの所与の段階において、セクルージョン値と辺の重みとを組み合わせたものを用いて、森からどの辺を除去すべきかを判断してきた。この判断は２つの部分、すなわち森の中のどの木から辺を除去すべきかの判断およびその木からどの辺を除去すべきかの判断を有するものと考えることができる。本発明の好ましい実施形態では、木の他の容易に測定可能な特性を、第１部の判断を行うために使用することができ、次いで、本発明自体の方法を用いて第２部の判断を行うことができる。たとえば、合計または平均で最高の辺の重みを有する木を選択してもよく、または頂点の最も多い木、他のある測定値、または測定値の組み合わせを採用してもよい。このような実施形態には２つの利点がある。第１の利点は、どの木を分けるかを判断する際に追加情報を考慮に入れることができることである。第２の利点は、選択値を計算する必要があるのが選択された木に対してのみであることである。
【００４４】
通常、途中までの上記セクルージョン計算プロセスを通して、２枚の葉のみを有する単純な木が得られることが観察されている。上述したプロセスの残りの部分は、単に、２枚の葉を続けて除去して現セクルーション値を増分させることである。一実施形態では、これに代えて、プロセスは、２枚の葉を有する単純な木が得られ、現セクルージョン値がその木の残りに割り当てられたときに終了する。この変更はセクルージョンの計算を加速化することができ、または少なくとも、２枚の葉を有する木の処理のために第２のメソッドに戻る必要性をなくす。この代替の手法は、木の中央領域において辺の重みと比較してセクルージョンが過度に強調されるように見えることを抑制するため、状況によっては主観的な性能の向上をもたらすことができる。
【００４５】
さらなる実施形態では、第２または代替の数量または測定値を、木の辺の除去中に計算してもよい。この第２または代替の数量または測定値は、辺の除去により木のある関数が低減する量である。
【００４６】
木Ｔの関数をｆ（Ｔ）と定義し、辺ｅの除去により木Ｔが２つの木ＵおよびＶに分かれる場合、辺の除去により関数が低減する量は以下の数式（１）
【００４７】
【数１】
2008522273.tif 000003
【００４８】
により与えられる。
【００４９】
適した関数は木の「エネルギー」を表す。このようなエネルギー関数の例を以下の数式（２）に示す。
【００５０】
【数２】
2008522273.tif 000004
【００５１】
である。式中、
ｘiはピクセルｌの輝度値であり、
Ｔは考慮中の木であり、
[外１]
2008522273.tif 000005
は木の平均輝度値である。
【００５２】
上記定義を用いると、上記数式（２）によるエネルギーの低減（「辺ｅのエネルギー」として考えることができる）は、以下の数式（３）
【００５３】
【数３】
2008522273.tif 000006
【００５４】
と書くことができる。式中、Ｎは示される木の頂点の数を指す。
【００５５】
セクルージョンが計算される方法は、この数量を木全体にわたって計算するように容易に適合することができる。これは、葉から内側に作業しながら、出会った頂点の数を計数し、出会ったピクセル値の和を求めることによって行うことができる。この方法を図２２〜図２５を参照してより詳細に説明することができる。図２２〜図２５は前の説明で使用したものと同じ入力データに基づいている。
【００５６】
これら図では、ピクセル値（この場合、輝度値）が各ピクセルまたはグラフの頂点に対応する円内に示される。最小全域木の辺が、頂点を結ぶ線として示される。
【００５７】
例示的な実施形態では、ピクセルは、行の左から右に、かつグラフの上から下に走査するラスタ順に検討される。したがって、ラスタ順で走査して、木の葉（１辺しか付いていない頂点）が特定されて処理される。各段階において、出会った頂点の数ｎおよびこれら頂点の輝度値の累積和ｓが記録される。木の葉では、ｎ＝１であり、ｓは葉のピクセル値である。処理済みの頂点は、図２２では四角い枠で囲まれて示される。
【００５８】
頂点が処理されると、対応する辺が木から除去される。したがって、ラスタ走査パス中に新たに作成された葉に、同じラスタ走査パス中に後で出会うことができ、これもまたグラフの左上の場合と同様に処理することができる。このため、この第１のラスタ走査パス段階により、図２２に示すように、累積された頂点計数およびグラフの２０個の頂点のうちの８個の和の計算が得られる。
【００５９】
図２３では、第１の段階中に除去された辺を点線で示す。新しい葉が現れ、ここでも、ラスタ走査パターンによりいくつかの頂点を１パスで処理することができる。
【００６０】
図２４では、木の２枚の葉だけが残っており、これら葉が両方とも除去される。単一の孤立ピクセル（値８を有する）が残り、すべての辺がグラフから除去されているため、この孤立ピクセルを処理する必要はない。なお、このサイズのグラフからすべての辺を除去するのに３回のパスで十分であるという保証はない。
【００６１】
最終段階では、すべての辺に戻り、上で導出された数式（３）を適用し、処理がその辺の除去に妥当であったピクセルの累積値に基づいて各辺のエネルギー値を得る。例示的な画像での２０個すべてのピクセルのピクセル値の累積合計は９３であり、木の平均輝度値
[外２]
2008522273.tif 000007
は４．６５である。したがって、たとえば、図２４の最下行の左から３番目の辺の辺エネルギーは以下の数式（４）〜（６）に示すように計算され、
【００６２】
【数４】
2008522273.tif 000008
【００６３】
上記式により辺エネルギーは５４．５である。
【００６４】
すべての辺の各エネルギー値を図２５に示す。
【００６５】
この方法を用いて除去する辺を選択する場合、このエネルギーが最大の辺が選択される。この例では、これはエネルギー５７．４を有する辺であり、この辺が除去されることになる。
【００６６】
本発明によるセグメンテーションアルゴリズムについて二次元画像を参照して説明した。同じ手法を、連続画像中のピクセル間の連結性を適宜定義して画像シーケンスに使用することもできる。
【図面の簡単な説明】
【００６７】
【図１】線と、当該線で結び付けることができる点からなるグラフを示した図である。
【図２】５×４画像のグラフを示した図である。
【図３】小輝度画像を示した図である。
【図４】図３の辺重み付きグラフを示した図である。
【図５】図４の最小全域木を示した図である。
【図６】図５の２つのセグメントへのＭＳＴセグメンテーションを示した図である。
【図７】図５の３つのセグメントへのＭＳＴセグメンテーションを示した図である。
【図８】セクルージョンを計算する際の連続した段階を示した図である。
【図９】図５のセクルージョンマップを示した図である。
【図１０】セクルージョンと辺の重みとの積を示した図である。
【図１１】セクルージョン処理を使用した図５の２つのセグメントへのセグメンテーションを示した図である。
【図１２】頂点セクルージョンマップを示した図である。
【図１３】辺セクルージョンマップを示した図である。
【図１４】変更されたセクルージョン値と辺の重みとの積を示した図である。
【図１５】セクルージョン処理を使用した図５の３つのセグメントへのセグメンテーションを示した図である。
【図１６】例示的なテスト画像を示した図である。
【図１７】説明した従来技術によるアルゴリズムを使用して図１６の６４のセグメントへのセグメンテーションを試みた結果を示した図である。
【図１８】説明した従来技術によるアルゴリズムを使用しての図１６の４０００のセグメントへのセグメンテーションの結果を示した図である。
【図１９】本発明の実施形態を使用しての図１６の６４のセグメントへのセグメンテーションの結果を示した図である。
【図２０】簡易化された選択計算を示した図である。
【図２１】本発明の代替の実施形態を使用しての図１６の６４のセグメントへのセグメンテーションの結果を示した図である。
【図２２】エネルギー計算に基づく例示的な方法の第１の段階を示した図である。
【図２３】エネルギー計算に基づく方法の第２の段階を示した図である。
【図２４】エネルギー計算に基づく方法の第３の段階を示した図である。
【図２５】エネルギー計算に基づく方法の第４の段階を示した図である。
【図１】
2008522273.tif 000009
【図２】
2008522273.tif 000010
【図３】
2008522273.tif 000011
【図４】
2008522273.tif 000012
【図５】
2008522273.tif 000013
【図６】
2008522273.tif 000014
【図７】
2008522273.tif 000015
【図８】
2008522273.tif 000016
【図９】
2008522273.tif 000017
【図１０】
2008522273.tif 000018
【図１１】
2008522273.tif 000019
【図１２】
2008522273.tif 000020
【図１３】
2008522273.tif 000021
【図１４】
2008522273.tif 000022
【図１５】
2008522273.tif 000023
【図１６】
2008522273.tif 000024
【図１７】
2008522273.tif 000025
【図１８】
2008522273.tif 000026
【図１９】
2008522273.tif 000027
【図２０】
2008522273.tif 000028
【図２１】
2008522273.tif 000029
【図２２】
2008522273.tif 000030
【図２３】
2008522273.tif 000031
【図２４】
2008522273.tif 000032
【図２５】
2008522273.tif 000033
【手続補正書】
【提出日】平成19年7月30日(2007.7.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
画像のピクセルがグラフの頂点で表され、ピクセルの隣接が前記グラフの辺で表され、前記辺に、隣接するピクセル間の非類似性測定値を表す重みが割り当てられ、前記グラフの最小全域木（またはその近似）が生成され、辺が前記最小全域木から続けて除去されて全域森が生成され、該全域森の木が前記画像のセグメントに対応する、画像セグメンテーション方法であって、
前記全域森から除去する辺の選択が、前記辺から該辺が存在する木の葉までの距離の測定値に依存する、画像セグメンテーション方法。
【請求項２】
辺を選択するための判断基準は、前記辺の除去によって生成される２つの木の測定値に依存する、請求項１に記載の画像セグメンテーション方法。
【請求項３】
前記辺のための測定値は、前記辺を含む前記木の中のピクセルの関数と前記辺の除去により生成される２つの木の中のピクセルの関数の値の和との差である、請求項２に記載の画像セグメンテーション方法。
【請求項４】
前記関数はエネルギー関数である、請求項３に記載の画像セグメンテーション方法。
【請求項５】
木の中のピクセルの前記エネルギー値は、前記木の中のピクセルの前記ピクセル値と前記木の平均ピクセル値との二乗差に関連する、請求項４に記載の画像セグメンテーション方法。
【請求項６】
前記辺を選択するための速度は、前記辺の除去により生成される２つの木のサイズの測定値に依存する、請求項２に記載の画像セグメンテーション方法。
【請求項７】
サイズは木を形成する頂点の数として測定される、請求項６に記載の画像セグメンテーション方法。
【請求項８】
木の各辺の前記測定値は再帰アルゴリズムにより計算される、請求項１乃至７のいずれか１項に記載の画像セグメンテーション方法。
【請求項９】
前記測定値は、前記木の葉に接合する第１の辺のセットに対して初期値に設定され、前記第１の辺のセットに接合する次の辺のセットに対して増分または累積され、すべての辺が検討されるまでこのプロセスが繰り返される、請求項８に記載の画像セグメンテーション方法。
【請求項１０】
前記測定値は前記木の葉に接合する辺の初期値に設定され、これら辺は一時的に除去され、前記測定値が増分または累積され、残っている辺がなくなるまでこのプロセスが繰り返される、請求項８または９に記載の画像セグメンテーション方法。
【請求項１１】
辺の重みが前記累積プロセスに含まれる、請求項１０に記載の画像セグメンテーション方法。
【請求項１２】
前記測定値の累積は、前記木に残っている葉が２枚になったときに中止され、前記測定値は前記木の残りの葉に対して一定の値に設定される、請求項１０または１１に記載の画像セグメンテーション方法。
【請求項１３】
前記辺を選択するための判断基準は前記グラフの前記ピクセル値に依存する、請求項１乃至１２のいずれか１項に記載の画像セグメンテーション方法。
【請求項１４】
前記頂点または辺を除去するプロセスは、前記グラフの全体の前記頂点または辺にわたって所定の走査順で実行される、請求項１乃至１３のいずれか１項に記載の画像セグメンテーション方法。
【請求項１５】
前記走査順はラスタパターンである、請求項１４に記載の画像セグメンテーション方法。
【請求項１６】
前記辺を選択するための判断基準は前記グラフの前記辺の重みに依存する、請求項１乃至１５のいずれか１項に記載の画像セグメンテーション方法。
【請求項１７】
選択される辺は、前記辺の重みと請求項１乃至１６のいずれか１項により導出される前記測定値との積が最大の辺である、請求項１６に記載の画像セグメンテーション方法。
【請求項１８】
前記辺の選択前に、辺を除去すべき木の選択が行われる、請求項１乃至１７のいずれか１項に記載の画像セグメンテーション方法。
【請求項１９】
前記木を選択するための判断基準は、以下の特性、すなわち前記木の前記頂点の計数、前記木の辺の平均重み、前記木の辺の合計重み、前記ピクセル値の関数、および前記木の辺の重みの関数のうちの任意またはすべての特性の組み合わせに依存する、請求項１８に記載の画像セグメンテーション方法。
【国際調査報告】
2008522273.tif 000034
2008522273.tif 000035
2008522273.tif 000036