(57)【特許請求の範囲】
【請求項１】
画像内のオブジェクトの形状を表現する方法であって、
前記画像のうち、前記オブジェクトの境界の内側の部分を順序付けるステップと、
前記画像の順序付けられた部分に対して中央軸を導出するステップと、
前記中央軸をセグメント化して順序付きツリーを生成するステップと、
前記順序付きツリーを構成する複数のノードの中の１以上のノードについて、単一ソース／単一シンクの有向非循環グラフを有するデータ構造で書き換え、前記順序付きツリーを部分的順序付きツリーに変換することによって、前記オブジェクトの形状を表現するステップと
を有することを特徴とするオブジェクト形状を表現する画像空間を順序付ける方法。
【請求項２】
前記順序付けは、ボロノイ順序付け関数を用いて、前記内側部分の画素を前記境界上の最も近接する点に射影する
ことを特徴とする請求項１記載のオブジェクト形状を表現する画像空間を順序付ける方法。
【請求項３】
前記中央軸は、前記内側部分の順序付けにおける不連続ステップの値を有する
ことを特徴とする請求項１記載のオブジェクト形状を表現する画像空間を順序付ける方法。
【請求項４】
前記順序付きツリーのルートノードは、前記中央軸の最大値を表し、該順序付きツリーの各エッジは、２つの分岐の間の中央軸セグメントを表し、
前記順序付きツリーにおけるノードの親子関係は、前記中央軸の値が減少する方向に伝わっている
ことを特徴とする請求項１記載のオブジェクト形状を表現する画像空間を順序付ける方法。
【請求項５】
複数のオブジェクトを複数の部分的順序付きツリーによって表現し、該複数の部分的順序付きツリーを比較することによって前記複数のオブジェクトについて対応する類似性スコアを決定する
ことを特徴とする請求項１記載のオブジェクト形状を表現する画像空間を順序付ける方法。
【請求項６】
前記複数の部分的順序付きツリーをデータベースに格納し、  前記データベースを入力オブジェクトで問合せることにより、前記部分的順序付きツリーの類似性スコアに基づいて該入力オブジェクトに類似する出力オブジェクトを取得するステップを更に有する
ことを特徴とする請求項１記載のオブジェクト形状を表現する画像空間を順序付ける方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は概して、画像空間の順序付けに関し、特にビデオオブジェクトのセグメント化に関するオブジェクト形状を表現する画像空間を順序付ける方法に関する。
【０００２】
【従来の技術】
ＩＳＯ ＭＰＥＧ−１およびＭＰＥＧ−２等の古い映像規格は、主に映像信号の時間的および空間的圧縮を扱う比較的低レベルの仕様である。これらの規格を用いて、広範囲の適用法に亙って高圧縮率の圧縮を行うことができる。
【０００３】
ＭＰＥＧ−４等、新しい映像符号化規格（"Information Technology  Generic coding of audio/visual objects," ISO/IEC FDIS 14496-2(MPEG4 Visual), Nov.1998参照）は、任意形状のオブジェクトを、別々のビデオオブジェクトプレーン（（ＶＯＰ）video object planes）として符号化および復号化することを可能にするものである。これら新しい規格は、自然のデータと合成のデータとが統合され、かつ、あらゆる方法でアクセスされる、インタラクティブ映像等のマルチメディアにおける適用を可能とすることが意図されている。例えば、ある映像から別の映像へ移動する像またはオブジェクトを「カット・アンド・ペースト」したい場合がある。そのオブジェクトを識別するためには、まず、映像が「セグメント化」されなければならない。映像（アーカイブされている場合も新たに取得された場合も含む）の量が与えられると、セグメント化プロセスは完全に自動的に行われるかまたは半自動的に行われる。
【０００４】
半自動的である場合、第１の画像に対してセグメント化を行う。この場合、オブジェクト追跡の問題が起こる。自動的である場合、まずオブジェクトを識別すること、次にオブジェクトを追跡することが問題となる。いずれの場合も、セグメント化プロセスは、ユーザが必要とする入力を最小化するよう企図されていなければならず、明らかに、まったく入力を必要としないのが最適である。
【０００５】
ビデオシーケンスの各画像は、ＶＯＰを用いて任意形状の画像領域にセグメント化される。各ＶＯＰは、例えば、形状、動きおよびテクスチャという点でビデオオブジェクトを記述する。上記規格では、ソース画像からＶＯＰの画像を生成する厳密な方法は定義されていない。通常の輝度成分および彩度成分に加えて、形状情報により、「自然な」オブジェクトが表現されるものとする。形状データを、セグメント化マスクとして、またはグレイスケールアルファプレーンとして提供することにより、複数のオーバーレイしたオブジェクトを表現することができる。ビデオオブジェクトは、オプティカルフロー、色および輝度等の低レベルの特徴に関連して広範囲に変化するため、ＶＯＰセグメント化は非常に困難な問題である。
【０００６】
多くのセグメント化方法が知られている。領域ベースのセグメント化方法には、メッシュベース、動きモデルベースおよび分割併合（split-and-merge）の方法がある。これら方法は、輝度等の空間的特徴に基づいているため、誤った輪郭を生成する可能性があり、場合によっては、前景のオブジェクトが背景に併合されてしまう可能性もある。最近では、形態素時空間セグメント化（morphological spatio-temporal segmentation）が使用されている。この場合、空間的（輝度）および時間的（動き）領域両方からの情報が、ベクトルを用いて追跡される。この複雑な方法は、空間的領域を時間的領域に誤って割当てる可能性があり、かつ、複数のオブジェクトを含むビデオシーケンスに適用することが困難である。
【０００７】
最も新しくＭＰＥＧ委員会が規格化したものは、正式には「マルチメディアコンテンツ記述インタフェース（Multimedia Content Description Interface）」と呼ばれるＭＰＥＧ−７（"MPEG-7 Context, Objectives and Technical Roadmap," ISO/IEC N2729, March 1999参照）である。本質的に、この規格は、あらゆるタイプのマルチメディア情報を記述するために使用することができる１組のディスクリプタを開発しようとするものである。この記述は、コンテンツ自体に関連付けられており、ユーザが必要とする素材を高速かつ効率的に探索することができるようにする。この規格は、それより前の符号化規格に取って代ろうとするものではなく、他の規格表現、特にＭＰＥＧ−４に基づくものであることに留意することが重要である。これは、マルチメディアコンテンツは、異なるオブジェクトに分解することができるものであり、各オブジェクトは、一意のディスクリプタのセットに割当てることが可能であるためである。また、この規格は、コンテンツが格納されるフォーマットとは無関係である。ＭＰＥＧ−７ディスクリプタは、圧縮データまたは非圧縮データに付加することが可能である。
【０００８】
マルチメディアコンテンツのディスクリプタは、多くの方法で使用することができる（例えば、"MPEG-7 Applications," ISO/IEC N2728, March 1999参照）。以下の説明の目的で、最も興味深いのは、データベース探索および検索に対する適用である。最も一般的なケースでは、ユーザは、所望のオブジェクトについていくつかの属性を指定する。これら属性は、特定のオブジェクトのテクスチャ、動きおよび形状を記述するディスクリプタを含むことができる。
【０００９】
【発明が解決しようとする課題】
形状表現の問題は、新しい問題ではないが、非常に難しい問題である。多くの方法が既に存在するが、それらの中には閉輪郭の幾何学的特質に基づくものもあり、ある種の２Ｄバイナリ信号の分解に基づくものもある。"Description of Core Experiment for Motion/Shape," ISO/IEC N2690, March 1999 に列挙されているように、ＭＰＥＧ委員会には、既に多くの提案がなされている。輪郭に基づく提案には、曲率スケール空間および正規化輪郭があり、分解に基づく提案には、ウェーブレットベースの輪郭記述、ゼルニケモーメントおよび多層固有ベクトルがある。
【００１０】
形状記述はすべて、スケールおよび回転不変量である必要がある。最も重要なのは、形状ディスクリプタの有効性は、類似性ベースの検索におけるその性能によって判断される、ということである。従って、形状の構造的情報を獲得することができ、かつ境界内のノイズに対して頑健である、コンパクトなディスクリプタに対し、最も好ましい結果をもたらすことが期待されている。
【００１１】
【課題を解決するための手段】
本発明に係るオブジェクト形状を表現する画像空間を順序付ける方法においては、画像内のオブジェクトの形状を表現する方法であって、画像のうち、オブジェクトの境界の内側の部分を順序付けるステップと、画像の順序付けられた部分に対して中央軸を導出するステップと、中央軸をセグメント化して順序付きツリーを生成するステップと、順序付きツリーを構成する複数のノードの中の１以上のノードについて、単一ソース／単一シンクの有向非循環グラフを有するデータ構造で書き換え、順序付きツリーを部分的順序付きツリーに変換することによって、オブジェクトの形状を表現するステップとを有する。
【００１２】
また、順序付けは、ボロノイ順序付け関数を用いて、内側部分の画素を境界上の最も近接する点に射影する。
【００１３】
また、中央軸は、内側部分の順序付けにおける不連続ステップの値を有する。
【００１４】
また、順序付きツリーのルートノードは、中央軸の最大値を表し、順序付きツリーの各エッジは、２つの分岐の間の中央軸セグメントを表し、順序付きツリーにおけるノードの親子関係は、中央軸の値が減少する方向に伝わっている。
【００１６】
また、複数のオブジェクトを複数の部分的順序付きツリーによって表現し、複数の部分的順序付きツリーを比較することによって複数のオブジェクトについて対応する類似性スコアを決定する。
【００１７】
さらに、複数の部分的順序付きツリーをデータベースに格納し、  データベースを入力オブジェクトで問合せることにより、部分的順序付きツリーの類似性スコアに基づいて入力オブジェクトに類似する出力オブジェクトを取得するステップを更に有する。
【００１８】
【発明の実施の形態】
［概論］
閉曲線の外部に関して２次元（２Ｄ）空間を順序付ける簡単かつ有効な方法について説明する。以下に示す例では、２Ｄ空間は画像であり、閉曲線は、画像のグラフィックまたはビデオオブジェクトの推定された境界を表す。順序付けを用いて、画像のシーケンスにおけるオブジェクト表面を決定することができる。また、オブジェクトの形状の表現を導出するために閉曲線の内部に関する順序付けについても説明する。
【００１９】
以下、２Ｄ画像の順序付けが、２つの特定の適用例、すなわち、ビデオオブジェクトのセグメント化および形状表現における問題に対して役立つことを示す。後述するように、これら２つの適用例は、２Ｄ空間のみの順序付けに基づいているが、この順序付けの方法は、閉曲線を種々の、すなわちＮ次元の表面に置換えることができ、より高次元空間に容易に汎化される。
【００２０】
［ビデオオブジェクトセグメント化］
映像等、画像のシーケンスにおいて、ビデオオブジェクトセグメント化の問題は、以下のように述べることができる。すなわち、全体に輝度関数が定義された３Ｄ空間があるとすると、その輝度関数により、オブジェクトの表面がその空間に射影すると推論する。換言すれば、ビデオオブジェクトセグメント化において、所定のオブジェクトに対応する映像の静止画像の各々の領域を見つけなければならない。
【００２１】
米国特許出願第９／２３６，８３８号公報" Object Boundary Detection Using a Constrained Viterbi Search "には、この問題の解決法のつとつが提供されている。ここでは、問題となる領域が統合されることによってボリュームが定義される。このボリュームは、正確なセグメント化に対応するものであり、内部がその問題のボリュームである対応する表面の位置を突止めるものである。
【００２２】
本実施の形態に示す解決法は、この方法に非常に近いが、対応する表面の位置を突止める手段は、異なる方法、すなわち、２Ｄ画像の順序付けによって実現される。
【００２３】
［形状表現］
形状表現の第２の問題は、セグメント化問題と幾分か関係しているが、ここでは、オブジェクトの表面を定義することではなく、オブジェクトの形状に対する一意の表現を定義することに関係する。
【００２４】
正式には、この問題は以下のように述べられる。すなわち、特定の瞬間においてオブジェクトを含むボリュームの表面の「スナップショット」となる、オブジェクト境界の輪郭が与えられた場合に、結果としての形状を定義する特徴を表現する手段を決定する。
【００２５】
上述したように、かかる表現を有する動機づけの１つは、探索および検索の適用法を容易にするということである。かかる表現を見つける多くの周知の技術に関する問題は、特定の形状が構造的に類似した形状に歪むことにより、常に類似した表現が生成されるとは限らない、ということである。
【００２６】
例えば、多くの一般的な表現技術は、形状の曲率に基づいている。しかしながら、透視変換またはアフィン変換によって可能なある方法によって形状が歪められる場合、曲率を有する表現が非常に異なる結果をもたらす可能性が非常に高い。同様に、ウェーブレットまたは固有ベクトル分解に基づく他の方法、もしくは、モーメントを抽出する手段にも、同様の問題が発生する。
【００２７】
この問題を解決する手がかりは、オブジェクトの構造的表現を定義することである。このように、形状は、元の形状の構造的特徴全体を変えずに境界の局所的な特徴を変更するよう、変化することができる。
【００２８】
説明されている、形状のかかる構造的表現を得るための方法は、セグメント化の問題に対して用いられるものと同じ順序付けの定義に基づいている。
【００２９】
［ボロノイ順序付けの定義］
ビデオオブジェクトセグメント化および形状表現の上述した問題の解決法において、閉輪郭に関する空間の順序付けは、きわめて重要な要素である。
【００３０】
図１に示すように、画像空間Ｉ内の閉輪郭ＣおよびＣの開始点矢印バーｘ0が与えられている場合、順序付け関数φ（矢印バーｙ，矢印バーｘ0）は、以下のように定義される。
【００３１】
【数１】
0004545277.tif 000002
【００３２】
【数２】
0004545277.tif 000003
【００３３】
すなわち、画像空間Ｉにおける特定の点の順序付けは、その点を曲線上のパラメータ化した点に射影することによって得られる。点ｙにおける関数の値は、Ｃ上のｙに最も近接した点と開始点との間の、輪郭Ｃに沿った右回りの距離である。射影は、上記式における内部最小化を満足するよう直交している。複数の点がこの条件を満足する場合、ｓの最小値が選択される。
【００３４】
レベルセットまたは距離ポテンシャルとは対照的に、上記順序付け関数は、オブジェクトの形状を空間に直接は射影せず、オブジェクトの周囲の「流れ（flow）」を射影する。この順序付けは、オブジェクト形状の柔軟な含意を画像空間に射影する。
【００３５】
順序付けを更に説明するために、図２の（ａ）および図２の（ｂ）は各々、上述した関数に従って画像の外側部分と内側部分とに対して行われる順序付けを示す。順序付けの「流れ」は、開始から終了に明から暗で示されている。
【００３６】
［オブジェクト境界の決定］
図３は、画像３０１の入力シーケンスからのオブジェクト境界３０９を決定する方法３００を示す。本方法は、初期境界推定３０２および反復ビタビ表面最適化３０４を含んでいる。
【００３７】
［動きフィールド抽出］
図３に示すように、複数解像度オプティカルフローを用いて、画像の入力シーケンス（映像３０１）から非常に密な動きフィールド（ＭＦ）を抽出する（３１０）。ここで手がかりとなる概念は、映像３０１がビデオオブジェクトを含む場合、入力映像に、背景と異なってまとまって移動する画素のクラスタが存在するということである。動きがシーケンス内の画像毎に点対応であると仮定すると、画像全体をまとまって移動する画素のクラスタを捜すことができる。
【００３８】
密な動きフィールドは、正確な角度から見なければ必ずしも有益な情報を与えるものではない。入力映像には多くの情報が存在し得るため、ここではシーン内のオブジェクトの単純な表現を捜す。
【００３９】
密な動きフィールドによって示される情報はすべて、切取って同様の動きの領域に分けられた単一の画像に還元することができる。このようにして、各画素のすべての経路を見つけた後、主成分分析（ＰＣＡ）３２０を使用して３次元空間の情報に要約することができる。
【００４０】
［主成分分析］
一般に、動き推定は、２つの画像間の対応付けの手段を提供する。抽出された動きフィールドが経時にわたってある程度の点対応を示すとすると、初期画像平面における各画素に対する動き経路を考える。これら対応する点の速度は、主成分分析によって分析される特徴ベクトルとして使用される。
【００４１】
本質的に、ＰＣＡは、実質的に同様の動きベクトルを有する密な動きフィールドにおける画素のクラスタを識別する。かかるグループのエッジの画素は、オブジェクトの境界を近似する。
【００４２】
動き経路の速度から第１の主成分を抽出することにより、動き経路の速度のＰＣＡから初期空間位置と結合された特徴ベクトルを生成する。初期位置は相互に排他的であるため、これら特徴ベクトルは、関数型の３Ｄ表面のサンプルを形成する。
【００４３】
表面の特徴は、以下のようにして決定される。ピークおよび鞍点は、動きフィールド分析により、ジッタと、２つの異なるオブジェクトの２つの動きの間の動き経路、すなわち動き不連続性を結び付ける滑らかさと、が低下する、同様または同種の動きの領域である。いかなる表面においても同様に、ピークおよび鞍点を見つけるために、その表面のうちのいずれかの部分が消えている場所を決定する。
【００４４】
ピークに関連する領域を見つけるために、ピークの周囲の半高さ領域をとり、その領域を主成分空間から実空間に戻すように変換する。そのピークに関連する動き経路を見つけることにより、ピークを画像平面上の点に変換することができ、それによって初期推定されたオブジェクト境界の輪郭（ＩＯＢ）３０６が推定される。
【００４５】
図３に示すように、このプロセスは、境界を推定するプロセスを完了する。当然のことながら、オブジェクト境界を推定する他の方法、例えばダイナミックスネーク（dynamic snakes）等を用いて同様のタスクを達成することも可能である。
【００４６】
なお、オブジェクト境界を推定する本方法の主な強みは、密な動き情報を抽出し、この十分な情報を、ＰＣＡを用いて管理可能かつ意味のあるデータセットに翻訳することができる、ということである。更に、主成分領域のデータの分析は、基礎となる映像のシーンに存在する複数のオブジェクトを検出することに十分役立つ。
【００４７】
［初期オブジェクト境界を用いる画像のボロノイ順序付け］
ステップ３２５（順序付けエンジン）において、推定されたオブジェクト境界を用いて上述したように画像３０１の各々が順序付けられる。初期オブジェクト境界の外側の画像の部分におけるすべての点（画素）は、ボロノイ順序付け関数を用いて初期オブジェクト境界上の最も近接した点に射影される。このボロノイ順序付けは、局所的な領域をその周囲（perimeter）を用いて順序付けすることにより、初期オブジェクト境界に関するより多くの情報を符号化する。探索空間を順序付けすることにより、ボロノイ順序付き画像（ＶＯＩ）３０７を生成するために、探索空間を限定するだけでなく、動的計画法によって画像のシーケンスにおけるオブジェクト表面３０９を見つけることができるようにする。
【００４８】
［順序付き探索］
オブジェクト境界３０６とこの境界の外側のボロノイ順序付き画像３０７とを推定すると、次に、順序付き探索（３３０）を実行することによって、オブジェクト表面３０９をより適切に推定する近接した輪郭のセットを捜し出すことができる。これら新たな輪郭のセットは、推定されたオブジェクト境界３０６の外側に存在し、画像シーケンス３０１から導出される補足情報３０８を取入れることによって見付け出される。
【００４９】
なお、推定されたオブジェクト境界３０６は、動き情報のみによって決定されたものである。初期オブジェクト境界の周囲の順序付き探索３３０は、初期境界の近似した形状を維持しつつ推定値を更に正確にしようとするものである。
【００５０】
順序付き探索３３０は、以下のようにして定義することができる。
Ｉが、初期輪郭
【００５１】
【数３】
0004545277.tif 000004
【００５２】
の周囲の順序付き空間を示すものとする。かつ、
【００５３】
【数４】
0004545277.tif 000005
【００５４】
が、Ｃを包囲する新たな輪郭であるものとする。
【００５５】
点矢印バーｘ’（ｓ）における画像輝度の関数である、ある目的関数Ｊ（矢印バーｘ’（ｓ））が与えられると、動的計画法を用いてＣ’を見つけることができる。動的計画法手順の目的は、順序付き経路を維持しつつコストを最大化することである。以下の条件が満たされる場合にのみ、経路がＣの周囲で順序付けられる。
【００５６】
【数５】
0004545277.tif 000006
【００５７】
本質的に、上記条件は、新たな輪郭のセットが、順序が常に増加している、すなわち、Ｃ’の順序付けがそのパラメータ化と共に単調に増加している経路に従うことを確実にする。これにより、経路が、振動およびバックトラックしてその空間内の初期輪郭Ｃのグローバルな特徴を保持しない点になることが防止される。当然のことながら、ある程度の偏差は許容されるが、それは、順序付き空間によって定義される限界内にあるよう制限される。
【００５８】
［動き分析エッジフィルタ］
順序付き探索３３０では、目的関数を用いて、最後に選択される経路が決定される。１つの態様において、目的関数は、画像内の各点のエッジ強度を決定する。この態様の主な欠点は、画像が、真のオブジェクト境界に直接関係しない多くの無用な情報を含むことである。ある意味で、未加工のエッジ情報は、ノイズとみなすことができ、それはフィルタリングする必要がある（３４０）。
【００５９】
エッジ情報をフィルタリングするために、再び動きを利用する。オブジェクト境界における動きは、通常不連続であるため、推定することが困難である。従って、視覚情報を導入し、この情報を動きを用いて強化する。オブジェクト境界では、不連続な動きを含むエッジが最もあり得る点であるため、これらエッジは強化される。これに対して、連続的または一貫した動きを呈するエッジは、非境界点である可能性が最も高いため、弱められる。
【００６０】
以下に、複数の画像の輪郭間の滑らかさを推定するために、どのようにエッジマップも使用できるかを説明する。これは、隣接した画像におけるオブジェクト境界の時間射影をバイアスすることで行われる。この反復フィードバック３４５プロセスを次に説明する。経時亘るオブジェクトの境界（画像シーケンス）の滑らかな射影は、該オブジェクトの表面上に収束する。
【００６１】
［反復ビタビ表面最適化］
オブジェクトは滑らかな表面を有する傾向にあるため、これら滑らかさの制約を考慮しながらオブジェクト表面を繰返し探索することができる。本質的に、本実施の形態における初期境界および動き拡張エッジ情報の順序付けを説明する反復プロセスによって、境界を再推定する。採られる方法は、上述した米国特許出願第９／２３６，８３８号公報に記載されている方法と類似している。まず、輪郭最適化を用いて、単一画像問題に対する解が求められる。次に、その解が反復フレームワークに挿入され、表面最適化を用いて複数の画像に対して汎化される。
【００６２】
まず、単一画像問題に対する解を考える。この目的は、順序付き探索３３０を用いて輪郭を見つけることである。スコア関数は、以下の形態である。
【００６３】
【数６】
0004545277.tif 000007
【００６４】
ここで、（ｘ1，…，ｘn，ｘ(n+1)）は経路であり、（ｘ1，…，ｘn）は１画素引いた別の経路であり、ｘ，ｙは、順序付けに起因する歪み画像の座標を表す。
【００６５】
画像の各画素をグラフのノードとみなし、順序が厳密に増加して画素が隣接しているノードのみを結合することにより、問題が有向非循環グラフにおける最短経路アルゴリズムに還元されることが明らかとなる。この問題は、任意の点における最大スコアを追跡しながら、上記スコア関数の幅優先アプリケーションを用いて解くことができる。この計算は、順序付けられた隣接する画素から生成されるトレリス（trellis）に適用されるビタビ方法のアプリケーションと同等のものである。
【００６６】
ここまで、単一画像に対する輪郭最適化について説明した。ここでは、異なる画像の輪郭間の動的相互作用から生じる複雑さを解決するために、オブジェクト境界を再推定する反復表面最適化技術に頼る。
【００６７】
表面最適化を達成するために、表面Ｓのエネルギ関数が以下のように公式化される。
【００６８】
【数７】
0004545277.tif 000008
【００６９】
ここで、各項は、動き不連続性、視覚的不連続性および滑らかさを表す。ある点におけるエネルギ関数は、２つの部分に分割することが可能である。
【００７０】
第１の部分は、画像の輝度または表面の形状に依存するものであり、動きおよび視覚的不連続性の説明となるものである。これらのエネルギは外部的なものであり、表面を外側に向けるものであって、初期境界推定および動きエッジ分析において説明されるものである。
【００７１】
第２の部分は、経時に亘る表面の形状に依存する。すなわち、これは、内部的なエネルギであり、構造的制約を与える。なお、滑らかさは、それだけでは比較的弱い構造的制約であるが、空間の定義された順序付けと共に用いられることにより、構造的制約が非常に強力になる。
【００７２】
表面最適化に滑らかさを組込むために、各境界は、強いエッジとして、前の画像と次の画像の動き強化エッジ画像に射影される。この時、エッジ／動きスコア化に対する射影によって、後の境界再推定の反復において、あるレベルまでの収束が可能となると共に時を経て表面の滑らかさに達することができるようになる。
【００７３】
オブジェクトの表面（経時に亘る境界）が突き止められた後は、画像のシーケンスからオブジェクトをセグメント化することは容易となる。
【００７４】
［複数のオブジェクト］
本実施の形態によるオブジェクトセグメント化の方法について、単一のオブジェクトのコンテキストでのみ述べたが、本方法は、複数のオブジェクトに対しても拡張することができる。
【００７５】
更に洞察するために、複数のオブジェクトのセグメント化について２つの異なる仮定の下で簡単に説明する。１つ目は、遮蔽が殆ど無いかまたはまったく無い場合であり、２つ目は、高い割合で遮蔽がある場合である。これら２つの場合のいずれにおいても、複数のオブジェクトの各々に対し初期オブジェクト境界が推定される。抽出された動きフィールドから、同じ方法でＰＣＡを実行することができるが、関数上の表面を画像空間に戻すようマッピングする手順をはるかに入念に行わなければならない。この手順は、Ｋ平均クラスタリング手順が分割の初期数を知っているのと同様に、シーンにおけるオブジェクトの数を知る必要がある。
【００７６】
［遮蔽無し］
画像に遮蔽がまったく無く、かつ、初期オブジェクト境界推定が正確に導き出された場合、複数のオブジェクト境界は、独立したオーバラップしない領域として現れる。そして、これら領域は、順序付けエンジンステップ３２５によって別々に順序付けされ、反復ビタビ表面最適化ステップ３０４に個々に与えられる。
【００７７】
［遮蔽有り］
複数のビデオオブジェクトの間に遮蔽がある場合、反復ビタビ表面最適化は、ボロノイ順序付き画像の各々に対し同時に行われる。近傍する画像からの境界の時間の射影によってもたさられる滑らかさと同様に、隣接するオブジェクト間の一貫した定義を維持するよう、近傍するオブジェクトの境界を空間的に射影することができる。そうすることにより、近傍するオブジェクトの境界を、真の境界に十分に収束させることができる。
【００７８】
［オブジェクト形状の表現］
上記説明において、画像のうち、オブジェクトの境界Ｃの外側である部分に、ボロノイ順序付けを用いることについて説明した。Ｃの補足的な内部空間において、順序付けは補足的な機能性を有する。オブジェクト境界の探索において順序付けの外側の射影（outside projection）を使用する一方で、オブジェクト形状表現に対し、順序付けの内側の射影（inside projection）を使用する。
【００７９】
順序付けの単純な操作からいかにこの表現が導出されるかについて述べ、この表現を周囲重み付け中央軸（Perimeter Weighted Medial Axis（ＰＷＭＡ））と呼ぶことにする。更に、この表現は、新たなデータ構造に頑健に変換することができる、ということを述べる。なお、これを部分的順序付きツリー（Partially Ordered Tree（ＰＯＴ））と呼ぶことにする。最後に、構造を一致させるか、または複数の部分的順序付きツリーを比較することができる動的計画方法について述べる。
【００８０】
［中央軸から重み付けされた周囲］
ＰＷＭＡは、Ｃの内側に亙って関数χCによって以下のように定義される。
【００８１】
【数８】
0004545277.tif 000009
【００８２】
すなわち、上記関数は、初期オブジェクト境界Ｃ内で行われる順序付けのあらゆる不連続ステップの値を含む。
【００８３】
まず、画像の内側部分の大半に亙ってχCがゼロであることを観測する。このサンプルケースでは、境界が円形である場合、１／２の値を有する中心点を除いて、すべての部分がゼロであることが分る。次に、ある点がゼロ以外である場合、その点は、その境界における２つの隣接しない点の間で等距離にある。その非ゼロ点の値は、それら２つの隣接しない点の間で周囲（perimeter）に沿って最小距離、すなわち、非ゼロ点が及ぶ境界の長さである。
【００８４】
言換えれば、χCは、物体の形状の「スケルトン」を表し、更に、それは、末端が中心点より低い値を有するように「重み付けされた」スケルトンである。
【００８５】
Ｃが単純な閉輪郭である場合、ＰＷＭＡの別の特徴は、非ゼロ点が常に、ルートノードが最大値でありノードが下降すると値が減少するツリーを形成することである。更に、オブジェクトの形状がＰＷＭＡにおいてある含意を有することが明らかである。このようにして、ＰＷＭＡにおける「結合点（joints）」での構造的歪みを説明することができる。
【００８６】
［ＰＷＭＡの順序付きツリーへの変換］
ＰＷＭＡが、ルートツリーとしてコンパクトな表現になるとすると、これらツリー構造を比較する頑健な方法を定義することが必要となる。比較方法は、構造的マッチングにおいて、および構造的変化性に対して頑健でなければならない。
【００８７】
構造的マッチングについて述べる場合、あるツリーから別のツリーにおけるすべてのノードおよびエッジの最適対応を決定する。１つのツリーから別のツリーへの構造的マッチングは、Ｐ完全性問題とＮＰ完全性問題との間の難点に存在する可能性のある、現在未解決の問題であるグラフ同型の問題に関連している。ここでの問題に対する手がかりとなる観測は、ＰＷＭＡが順序付きツリーになるということである。
【００８８】
ＰＷＭＡは、以下のステップにより順序付きツリーに変換される。
１．ツリーのルートノードは、ＰＷＭＡの最大値にある。
２．ツリーの各エッジは、任意の２ノード間のＰＷＭＡ線分を表す。
３．各ノードは、等間隔の３つ以上の非ゼロラインが交差するか、または１つが終端するＰＷＭＡの点に対応する。
４．ＰＷＭＡの値が減少する方向に親子関係が順次発生する。すなわち、下位のノードほどＰＷＭＡの弱いセグメントを表す。
【００８９】
最後の観測は、ＰＷＭＡ構造が２Ｄ平面にあり、それを、それらの反時計回りの角度に関して順序付けすることができる、ということである。単純なＰＷＭＡ構造は、上記特徴を有する順序付きツリーである。ノードはセグメント化点を表し、エッジはセグメント化点間の情報を表す。
【００９０】
［順序付きツリーの比較］
順序付きツリーに対し、マッチング用の分析は比較的簡単である（Cormen等による"Introduction to Algorithms," MIT Press, 1990 参照）。３つのツリーとそれらの複数の子について考える。マッチングに対する相互に再帰的な関係が、シーケンスマッチング問題を介して発生する。
【００９１】
基本として、ルートノードだけを有する２つのツリーが完全に一致するものとする。図４のツリーＡ４０１およびツリーＢ４０２に対し、本実施の形態による帰納的（inductive）ステップに対し最長共通部分列（ＬＣＳ）比較手順を用いる。
【００９２】
【数９】
0004545277.tif 000010
【００９３】
ここで、ｅanおよびｅbnは、サブツリーＴan４０４およびＴbn４０５に向かうエッジ４０３である。シーケンス内でサブツリーをマッチングさせるためにＴｒｅｅＣｏｍｐａｒｅ（ツリー比較）手順を呼出すことにより、再帰が発生する。すなわち、
【００９４】
【数１０】
0004545277.tif 000011
【００９５】
なお、すべての動的計画法問題の場合と同様に、可能なツリー比較の数は有限である。このように、順序付きツリーの計算コストは、以下の式によって制限される。
【００９６】
【数１１】
0004545277.tif 000012
【００９７】
更に、この種の構造的マッチングは、分岐の喪失に対して頑健である。
【００９８】
問題は、セグメント化によってもたらされるノイズによる。このプロセスでは、同じ深さのサブツリーのみが比較されることは明らかである。そのため、セグメント化方法におけるノイズにより、ツリーに余分のノードおよびエッジが擬似的に付加される場合、その子の深さが増大し、この小さい誤配列が重大な不一致をもたらすこととなる。
【００９９】
［部分的順序付きツリー］
図５に示すように、ここで説明するＰＷＭＡマッチング中に新たなレベルの頑健性を強要するために、部分的順序付きツリー（（ＰＯＴ）Partially Ordered Tree）５００と呼ばれる新たなデータ構造を導入する。部分的順序付きツリーは、再帰的グラフ状データ構造である。図５において、主要素（例えば、ノード５０１、エッジ５０２）は太線で示し、従要素は細線５０３で示す。
【０１００】
部分的順序付きツリーにおけるＰＯＴ主ノードは、単一ソース／単一シンクの有向非循環グラフ（ＤＡＧ）を含む。このグラフのエッジをＰＯＴ従エッジと呼び、そのノードをＰＯＴ従ノードと呼ぶことにする。ＰＯＴ従エッジは、データベクトルと、ＰＯＴ主エッジと呼ばれる別のＰＯＴ主ノードへの参照と、を含む。
【０１０１】
なお、ＰＯＴ主グラフと言う場合は、ＰＯＴ主要素がもたらすグラフのことを言う。ＰＯＴ主ノードのＰＯＴ従グラフと言う場合は、ＰＯＴ主ノードが含むＤＡＧのことを言う。ＰＯＴ主グラフは、２つの特別な制約を有する。すなわち、１）ＰＯＴ主グラフの部分グラフは、ルートツリーであり、２）このルートツリーに無いエッジはいずれも、ノードから下位へ降りるのみである。なお、順序付きツリーはＰＯＴツリーの特別なケースであり、各ＰＯＴ従グラフは、単に線形グラフである。
【０１０２】
［ＰＷＭＡの部分的順序付きツリーへの変換］
上述したように、順序付きツリーは、部分的順序付きツリーの特別なケースであり、ＰＷＭＡを部分的順序付きツリーに変換するための開始点となるものである。本実施の形態による初期構造を得るために、ＰＷＭＡの順序付きツリーへの変換と同じ変換が実行される。ＰＯＴとするために、ＰＯＴ従グラフに並行経路を付加することによって、代替セグメント化および表現をコード化する。
【０１０３】
図６および図７に示すように、入力は初期オブジェクト境界３０６であり、出力は部分的順序付きツリー６０２であり、変換のステップは、以下の通りである。
【０１０４】
１．図７の（ａ）に示すように、境界７００によって定義されるオブジェクトの内側部分に対し、（ボロノイ）順序付けを施す（ステップ３２５）。
【０１０５】
２．順序付けからＰＷＭＡ７０１を導出する（ステップ６２０）。図７の（ｂ）において、オブジェクトの形状の「スケルトン」が比較的細いことは、末端が中心点より低い値を有するようなＰＷＭＡの重み付けがなされていることを示している。
【０１０６】
３．ノードおよびエッジ７０２（図７の（ｃ））により、ＰＷＭＡ７０１をセグメント化する（ステップ６３０）。
【０１０７】
４．セグメント化したＰＷＭＡから順序付きツリー７０３（図７の（ｄ））を生成する（ステップ６４０）。
【０１０８】
５．順序付きツリーを部分的順序付きツリー７０４（図７の（ｅ））に変換する（ステップ６５０）。
【０１０９】
順序付きツリーとは対象的に、ＰＯＴの構造上の自由度により、構造的変化に対する双対性および頑健性等の複雑な情報を符号化することができる。ＰＯＴのコアがまだ元の順序付きツリーであり、順序付きツリーのノードと部分的順序付きツリーのノードとの間に単純な同型が存在するが、部分的順序付きツリーは、その下位の部分的順序付けによる柔軟性と、その下位に向かう経路とをより多く有する。
【０１１０】
ＰＯＴ従グラフにおける並行経路は、各分岐の種々のあり得るセグメント化を符号化する。従って、セグメントをスキップすることができる場合を考慮すると、次のＰＯＴ主子からのＰＯＴ従枝が、並行経路としてコピーされる。擬似ノードの可能性を考慮すると、ＰＯＴ従グラフにおける並行経路を付加して余分なＰＯＴ主エッジを有する問題のノードをバイパスすることにより、ノードを無視する可能性を付加することができる。
【０１１１】
［ＰＯＴ比較］
ＰＯＴの構造的比較では、順序付きツリーに対して同様の分析を行うが、ＬＣＳ比較を用いる代りに、ＤＡＧ比較アルゴリズムを用いる（Lin等による"Coding and Comparison of DAGs as a novel neural structure with application to on-line handwritten recognition, "  IEEE Trans Signal Processing, 1996参照）。
【０１１２】
【数１２】
0004545277.tif 000013
【０１１３】
シーケンスの要素マッチングの代りに、ＤＡＧにおけるエッジのマッチングを行う。ＤＡＧのエッジに関連するサブツリーのマッチングに対しＰＯＴ比較関数を呼出すことにより、再帰が発生する。すなわち、
【０１１４】
【数１３】
0004545277.tif 000014
【０１１５】
なお、すべての動的計画法の場合と同様に、可能なＰＯＴ比較の数は有限である。従って、ＰＯＴ比較が比較の大部分であるとすると、順序付きツリーの計算コストは、以下の式によって制限される。
【０１１６】
【数１４】
0004545277.tif 000015
【０１１７】
図８は、単純なシステム８００を示す。ここでは、まず２つの輪郭８０１−８０１が別個に変換され（６００）、その後、上述した手順を用いて比較され（８１０）、類似性スコア８２０が得られる。
【０１１８】
［適用例：形状クエリ］
ＰＯＴ比較プロセスによって補足される部分的順序付きツリーの構造により、エッジの喪失に対するだけでなく擬似的セグメント化点に対しても頑健な比較方法が得られる。オブジェクトの中央軸をこの中間ＰＯＴ表現に変換し、ＰＯＴ比較を類似性基準として使用することにより、所与の形状について、直観的にその形状と類似した他の形状を見つけることができる。
【０１１９】
図９は、このタスクを実行するデータベース検索システム９００を示す。このデータベース検索の適用例において、ユーザ９０１は、入力クエリ９０２を用いて１つまたは一連のデータベース９１０に問合せを行う。このクエリは、画像、オブジェクト境界等の形態とすることができる。クエリは、手書きされたものであっても、ローカルに取得されたものでもどちらでもよい。データベースインタフェースコントローラ９２０は、その入力に類似する出力９０３を検索する。
【０１２０】
第１のステップとして、クエリが、部分的順序付きツリー６００に変換される。ステップ８１０では、変換された輪郭（ＰＯＴ）が、データベース９１０に格納された輪郭と比較される。高速かつ効率的な探索手順を可能とするために、輪郭データベースは、各々が対応するヘッダ情報を有すると共に事前計算されたＰＯＴ表現を含む多くの輪郭から構成されているものとする。
【０１２１】
マルチメディアコンテンツにかかるヘッダ情報を付加することは、実際には、新たなＭＰＥＧ−７規格の意向である。データベースインタフェースコントローラは、あるデータの要求を制御するために、データベース自体の外側に存在する。クエリとの比較を行うために、コントローラは、データベースに格納された輪郭のＰＯＴをＰＯＴ比較８１０に受渡す。上述したように、ＰＯＴ比較の出力は、類似性スコアである。この値に基づいて、最も類似する輪郭９０３がユーザに対し検索結果として与えられる。
【０１２２】
要約すると、ＰＷＭＡのＰＯＴ表現およびＰＯＴ比較は、形状の効率的かつ頑健なクエリを可能とする多くの有用な利点を有している。
１．圧縮
ＰＷＭＡのＰＯＴ表現は、未加工の点よりもコンパクトな形状表現方法である。
２．拡張性
ＰＷＭＡのＰＯＴ表現は、異なる詳細度に対して異なるレベルで閾値化することができる。更に、ＰＯＴ比較は、これら詳細における変化に対して頑健である。
３．形状柔軟性
ＰＷＭＡのＰＯＴ表現はまた、類似性スコアを維持しながら結合部における曲げの影響を受け易い構造の概念を符号化する。
４．頑健性
ＰＯＴ表現は、ＰＷＭＡの構造の複数の表現を符号化する。ＰＯＴ比較は、効率的に、多項式時間における動的計画法アルゴリズムを用いて各々に対するこれらあり得る表現すべてをチェックし、頑健な類似性基準を与える。
５．適応性
ＰＯＴ表現を用いることにより、ＰＯＴ比較はまた、問合せ中にいずれの経路が使用されているか追跡することができる。システムは、その類似性基準を調整するためにＰＯＴ表現を適応的に簡潔にすることを選択することができる。
６．汎化
ＰＯＴ表現を用いて、同様の部分構造を構造的に一緒に併合することにより、複数クラスの形状に対して、表現の構築を探求することができる。
【０１２３】
閉曲線の外側および内側に関して空間を順序付けする方法について説明した。
第１の順序付けを用いて、画像のシーケンスに亙るオブジェクトの境界を決定することができ、第２の順序付けを用いて、オブジェクトの形状を表現することができる。両方の決定は、映像特徴抽出の適用例において適用が可能である。
【０１２４】
本発明を、好ましい実施の形態の例として説明したが、本発明の精神および範囲内において他の様々な適用および変更が可能であることは理解されるべきである。従って、本発明の真の精神および範囲内にあるかかるすべての変形態様および変更態様を網羅することが、特許請求の範囲の目的である。
【０１２５】
【発明の効果】
上述のように、本発明のオブジェクト形状を表現する画像空間を順序付ける方法は、画像内のオブジェクトの形状を表現する方法を提供する。画像のうちオブジェクトの境界の内側の部分が順序付けされる。この順序付けでは、ボロノイ順序付け関数を用いてその内側部分の画素が境界の最も近接する部分に射影される。
【０１２６】
画像の順序付けられた部分について、中央軸が導出される。この中央軸は、上記内側部分の順序付けにおける不連続ステップの値を含む。中央軸がセグメント化されることにより、順序付きツリーが生成される。この順序付きツリーのルートノードは、中央軸の最大値を表し、順序付きツリーの各エッジは、２つの分岐の間の中央軸セグメントを表す。
【０１２７】
順序付きツリーのノードの親子関係は、中央軸の値が減少する方向に伝わっている。この順序付きツリーが部分的順序付きツリーに変換されることにより、オブジェクトの形状が表現される。
【図面の簡単な説明】
【図１】  順序付け関数を定義するブロック図である。
【図２】  （ａ），（ｂ）はそれぞれ、図１に示す曲線の外側部分および内側部分のボロノイ順序付けを示す。
【図３】  オブジェクト表面探索を実行するための空間順序付けの方法の流れ図である。
【図４】  本発明に従ってマッチングされる２つの順序付きツリーの図である。
【図５】  部分的順序付きツリーの図である。
【図６】  輪郭を部分的順序付きツリーに変換する方法の流れ図である。
【図７】  （ａ）乃至（ｅ）はそれぞれ、オブジェクト、その中央軸のグラフ、セグメント化された中央軸、順序付きツリーおよび部分的順序付きツリーである。
【図８】  部分的順序付きツリーを比較する方法の流れ図である。
【図９】  オブジェクト形状を比較するシステムのブロック図である。
【符号の説明】
３０２  初期境界推定ステップ、３０４  反復ビタビ表面最適化ステップ、３４０  フィルタリングステップ、３２５  順序付けエンジンステップ、６２０  周囲重み付き中央軸ステップ、６３０  ノード／エッジセグメント化ステップ、６４０  順序付きツリー生成ステップ、６５０  部分的順序付きツリー変換ステップ、７０１  中央軸（ＰＷＭＡ）。
【図１】
0004545277.tif 000016
【図２】
0004545277.tif 000017
【図３】
0004545277.tif 000018
【図４】
0004545277.tif 000019
【図５】
0004545277.tif 000020
【図６】
0004545277.tif 000021
【図７】
0004545277.tif 000022
【図８】
0004545277.tif 000023
【図９】
0004545277.tif 000024