(57)【要約】【課題】  グラフィカルオブジェクトの境界情報を処理する改良された方法を提供する。【解決手段】  本発明にかかる方法は、少なくとも境界情報によって画定されるグラフィカルオブジェクトを含むグラフィカル画像（２０４）を受け取ること、境界情報から複数の頂点を決定すること、および少なくとも複数の頂点、グラフィカル画像、およびグラフィカル画像を解析することにより１組の頂点間の輪郭を検出するように働く所定の関数を利用して、近似された境界（２０６）を作成することを含むことができる。
2006501530.tif 000002
【特許請求の範囲】
【請求項１】
グラフィカルオブジェクトの境界情報を処理するシステムであって、
少なくとも前記境界情報（２０５）によって画定される前記グラフィカルオブジェクトを含むグラフィカル画像（２０４）を受け取るコードと、
前記グラフィカル画像の１対の点（ｖ１、ｖ２）の間の輪郭（４０１）を検出するコードと、
前記境界情報から複数の頂点を決定するコードであって、前記検出するコードによって検出された、前記複数の頂点のうちの隣接する頂点間の各輪郭が、歪み判断基準内で前記境界情報の各エッジを近似する、決定するコードと
を備えるグラフィカルオブジェクトの境界情報を処理するシステム。
【請求項２】
少なくともグラフィカル画像（２０４）、前記複数の頂点、および、前記検出するコードを利用して、近似された境界を作成するコード
をさらに備える請求項１に記載のシステム。
【請求項３】
前記所定の関数は、前記グラフィカル画像に関連付けられた勾配を計算するように働き、
前記計算された勾配は、縮尺パラメータによって限定された前記グラフィカル画像の各空間区域にわたって計算される
請求項１に記載のシステム。
【請求項４】
前記決定するコードは、発見的な値よりも短い各エッジに関連付けられた前記境界情報の点を解析する
請求項１に記載のシステム。
【請求項５】
前記決定するコードは、重み付けされた非循環グラフであるエッジ集合のエッジに関連付けられた頂点対を解析する
請求項１に記載のシステム。
【請求項６】
前記複数の頂点を決定するコードは、探索可能な頂点の集合からの頂点を解析し、
前記探索可能な頂点の集合は、
（ａ）第１の発見的な値よりも大きな曲率に関連付けられた頂点、および、
（ｂ）次の制約条件
（ｉ）隣接する頂点間の距離を最大にすることが、第２の発見的な値よりも小さいこと、および
（ｉｉ）前記検出するコードによって検出された隣接する頂点間の各輪郭が、歪み判断基準内で前記境界情報の各エッジを近似すること
を条件として、
前記隣接する頂点間の距離を最大にすることにより再帰的に成長された頂点
を含む
請求項１に記載のシステム。
【請求項７】
グラフィカルオブジェクトの境界情報を処理する方法であって、
少なくとも前記境界情報によって画定される前記グラフィカルオブジェクトを含むグラフィカル画像を受け取ること（６０１）と、
前記境界情報から複数の頂点を決定すること（６０５）であって、該複数の頂点のうちの隣接する頂点が、歪み判断基準内で前記境界情報の各エッジを近似する各輪郭に関連付けられ、前記各輪郭が、所定の関数による前記グラフィカル画像の解析によって検出されることと、
少なくとも前記複数の頂点をデータ構造体で符号化すること（６０７）であって、前記境界情報を表すこと
を含むグラフィカルオブジェクトの境界情報を処理する方法。
【請求項８】
前記所定の関数は、隣接する頂点間の最短経路を決定するように働き、
前記最短経路は、前記グラフィカル画像から計算された勾配によって重み付けされ、
前記所定の関数は、縮尺パラメータによって定義されたピクセル近傍を利用して前記勾配を計算するように働く
請求項７に記載の方法。
【請求項９】
前記決定することは、発見的な値よりも短いエッジに関連付けられた頂点対を解析する
請求項７に記載の方法。
【請求項１０】
前記決定することは、探索可能な頂点の集合から頂点を選択し、
前記探索可能な頂点の集合は、
（ａ）第１の発見的な値よりも大きな曲率に関連付けられた頂点、および、
（ｂ）次の制約条件
（ｉ）隣接する頂点間の距離を最大にすることが、第２の発見的な値よりも小さいこと、および
（ｉｉ）隣接する頂点間の各輪郭が、歪み判断基準内で前記境界情報の各エッジを近似すること
を条件として、前記隣接する頂点間の距離を最大にすることにより再帰的に成長された頂点を含む
請求項７に記載のグラフィカルオブジェクトの境界情報を処理する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の分野］
本発明は、包括的には、コンピュータグラフィックスに関し、より詳細には、グラフィカルオブジェクトの境界情報を処理するシステムおよび方法に関する。
【背景技術】
【０００２】
［発明の背景］
さまざまな画像処理技法を可能にするために、いくつかのマルチメディアアプリケーションによって、形状符号化が利用されている。
例えば、デジタル写真エディタアプリケーションによって、形状符号化が利用されている。
形状が符号化または画定された後、デジタル写真エディタアプリケーションによって、ユーザは、符号化された形状内部のグラフィカル情報のみを変更することが可能になる。
例えば、形状内部のグラフィカル情報を、新たな背景上に「切り取りおよび貼り付け（cut-and-pasted）」することができる。
【０００３】
形状の符号化には、さまざまなデータ構造体およびアルゴリズムが使用されてきた。
例えば、領域ベースの手法が開発されている。
領域ベースの方式は、オブジェクト領域を表す１および背景領域を表す０を有する２値画像であるサポートマップによってオブジェクトを符号化する。
このように、形状符号化は、２値画像符号化問題に変換される。
例示の領域ベースのアルゴリズムは、ジョイントバイナリ画像グループ（ＪＢＩＧ）、ＪＢＩＧ２、およびムービングピクチャエキスパートグループ−４（ＭＰＥＧ−４）によって開発されたアルゴリズムを含む。
【０００４】
境界ベースのアルゴリズムも、多く利用される。
例えば、ユーザは、グラフィカル画像におけるオブジェクトの境界の各ピクセルを手動で選択することができる。
選択された各ピクセルの座標は、境界を画定するために記憶することができる。
さらに、記憶された座標によって画定された境界に近似するために、チェーン符号化、ポリゴン近似、高次の曲線当てはめ（スプライン）近似、ポリゴン近似とスプライン近似の組み合わせなど、さまざまな方式が使用されてきた。
これらの近似アルゴリズムは、境界を表すのに必要なデータ量をさまざまな度合いで削減する。
【特許文献１】米国特許第５７７４５９５号
【非特許文献１】SCHUSTER G M ET AL: "OPERATIONALLY OPTIMAL VERTEX-BASED SHAPE CODING", IEEE SIGNAL PROCESSING MAGAZINE, IEEE INC. NEW YORK US, vol. 15 no. 6, November 1998 (1998-11), pages 91-108, ISSN 1053-5888
【非特許文献２】ORANGE C M ET AL: "Magnetic contour tracing", VISUALIZATION AND MACHINE VISION, 1994. PROCEEDINGS., IEEE WORKSHOP ON SEATTLE, WA, USA 24 JUNE 1994, LOS ALAMITOS, CA USA, 1994, IEEE COMPUT. SOC. 1994, pages 33-44, ISBN: 0-8186-5875-4
【非特許文献３】Huitao LuoおよびAlexandros Eleftheriadis著のDesigning an Interactive Tool for Video Object Segmentation and Annotation, ACM Multimedia 1999
【非特許文献４】T. H. Cormen、C. E. Leiserson、およびR. L. Rivest著のIntroduction to Algorithms, chapter 25.2, MIT Press, 1990
【非特許文献５】G. H. SchusterおよびA. K. Katsaggelos著「An Optimal Polygonal Boundary Encoding Scheme in the Rate Distortion Sense」IEEE Trans. Image Processing, vol.7, no.1, 1998
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、既知の形状符号化アルゴリズムは、基となるグラフィカル画像（例えば、ビットマップ、ビデオ画像など）を提示するのに利用されるアルゴリズムから独立したものとなっている。
したがって、既知の形状符号化アルゴリズムは、基となるグラフィカル画像とは別にかなりのデータ量を必要とする。
【課題を解決するための手段】
【０００６】
［発明の概要］
一実施の形態では、本発明は、グラフィカルオブジェクトの境界情報を処理する方法を対象とする。
この方法は、少なくとも境界情報によって画定されるグラフィカルオブジェクトを含むグラフィカル画像を受け取ること、境界情報から複数の頂点を決定すること、および少なくとも複数の頂点、グラフィカル画像、およびグラフィカル画像を解析することにより１組の頂点間の輪郭を検出するように働く所定の関数を利用して、近似された境界を作成することを含むことができる。
【発明を実施するための最良の形態】
【０００７】
［発明の詳細な説明］
本発明の実施の形態は、グラフィカル画像においてオブジェクトの境界を画定する符号化情報に関係している。
これらの実施の形態では、境界はすでに画定されているものと仮定される。
例えば、ユーザが、グラフィカル画像から点を選択して境界を画定することができる。
境界は、例えば、グラフィカル画像からの１組のピクセルによって表すことができる。
【０００８】
図１は、本発明の実施の形態による例示のシステム１００を示している。
このシステム１００は、画像符号化１０１および形状符号化１０２を行う。
形状符号化１０２は、形状依存符号化（shape dependent coding）を行う。
具体的には、形状符号化１０２は、形状符号化１０２に関連付けられたデータで表される基となる画像を参照することにより、オブジェクトの形状または境界を画定する。
オブジェクトの境界は、基となるグラフィカル画像と高い相関性を有する。
この高度な相関性のため、形状符号化１０２は、境界を表すのに必要なデータ量を削減することができる。
形状符号化１０２は、境界のノード点要素の座標を直接符号化することによらずに、境界を表すのに必要なデータ量を削減する。
正確に言えば、形状符号化１０２は、原画像からの点要素を検出するメカニズムまたは機能によって境界を符号化する。
【０００９】
境界（または形状）と基となるグラフィカル画像との間の相関を除去することが、本発明以前の重要な課題であったことが理解されよう。
特に、テクスチャ画像とその画像の境界との間の相関は、数学的に閉じた形の解で表すのが非常に難しい。
本発明の実施の形態は、後に詳述するように、基となるグラフィカル画像から境界を漸進的に検出する「ラバーバンド関数（Rubberband function）」を使用する。
【００１０】
画像符号化１０１および形状符号化１０２により生成されたデータは、例えばネットワーク１０３を介して伝達される。
受信システムにおいて、画像は、まず復号される（１０４）。
次いで、それぞれのオブジェクトの境界が、復元された画像データを利用して復号される（１０５）。
具体的には、各境界を画定するデータは、１組の頂点を含む。
各頂点は、境界上の単一の点を表す。
一方、この１組の頂点は、境界上の点の比較的小さな部分集合を表す。
ラバーバンド関数は、復元された画像データを解析することによって頂点間の残りの点を検出し、境界の「欠けている点を満たす」。
さらに、後に詳述するように、各頂点に関連付けられたパラメータが、ラバーバンド関数を効率的に作動させ、かつ、基となるグラフィカル画像の解析を適切に拡大縮小するように、この関数のオペレーションを制限する。
【００１１】
画像および形状が復号されると、要求に応じて、さらなる処理１０６を行うことができる。
この処理は、適切なマルチメディアアプリケーションを介したユーザによる画像処理を含むことができる。
【００１２】
図２は、本発明の実施の形態を実施する例示のコンピュータシステム２００のブロック図を示している。
このシステム２００は、グラフィカル情報をユーザに提示する表示装置２０１を含む。
システム２００は、ソフトウェア命令を実行する中央処理装置（ＣＰＵ）２０２をさらに含む。
ＣＰＵ２０２は、任意の汎用ＣＰＵとすることができ、ＣＰＵ２０２が、本明細書で説明するような本発明のオペレーションをサポートする限り、本発明は、ＣＰＵ２０２のアーキテクチャによって限定されるものではない。
【００１３】
また、コンピュータシステム２００は、ランダムアクセスメモリ（ＲＡＭ）２０３も含む。
このＲＡＭ２０３は、ＳＲＡＭ、ＤＲＡＭ、ＳＤＲＡＭなどとすることができる。
コンピュータシステム２００は、ＲＯＭ２０７を含む。
このＲＯＭ２０７は、ＰＲＯＭ，ＥＰＲＯＭ、ＥＥＰＲＯＭなどとすることができる。
ＲＡＭ２０３およびＲＯＭ２０７は、当該技術分野において既知なように、ユーザデータおよびシステムデータならびにプログラムを保持する。
【００１４】
本発明のさまざまな要素は、実行可能命令を介して実施された場合、基本的には、このようなさまざまな要素のオペレーションを定義するコードとなる。
実行可能命令またはコードは、可読媒体（例えば、ハードドライブ媒体、光媒体、ＰＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、テープ媒体、カートリッジ媒体など）から得ることもできるし、通信媒体（例えば、インターネット）からデータ信号を介して伝達することもできる。
実際には、可読媒体には、情報の記憶または転送を行うことができるあらゆる媒体が含まれ得る。
【００１５】
例えば、本発明の実施の形態は、境界符号化アルゴリズム２０９（後に詳述）を定義する実行可能命令またはコードを、本発明の実施の形態に従って媒体ドライブ２０８（例えばハードドライブ）に記憶する。
これらの実行可能命令またはコードは、ＲＡＭ２０３にロードして、ＣＰＵ２０２によって実行することができる。
ＣＰＵ２０２は、実行可能命令の制御の下、本発明の実施の形態に従って、グラフィカル画像２０４および境界定義２０５を処理し、符号化境界２０６を生成することができる。
【００１６】
さらに、コンピュータシステム２００は、通信アダプタ２１０を備える。
この通信アダプタ２１０は、コンピュータシステム２００をネットワーク２１１に接続するようになっている。
ネットワーク２１１は、電話ネットワーク、ローカルエリアネットワーク（ＬＡＮ）および／またはワイドエリアネットワーク（ＷＡＮ）、イーサネット（登録商標）ワーク、ならびに／またはインターネットワークの１つまたは複数のものとすることができる。
コンピュータシステム２００は、符号化境界２０６を別のシステムへ通信して、この別のシステムが、本発明の実施の形態に従って、伝達された情報から境界を復元することを可能にすることができる。
【００１７】
本発明の実施の形態の読み手の理解を助けるために、次に図３を参照する。
この図３は、グラフィカル画像３００を示している。
グラフィカル画像３００は、境界３０１を含む。
境界３０１は、比較的大きな１組のピクセルとして表される。
後に詳述するように、本発明の実施の形態は、１組の頂点（図３に示すようなｖ０、ｖ１、ｖ２、およびｖ３）を選択する。
各頂点は、２つのパラメータ（ｗｉ，ｓｉ）に関連付けられている。
パラメータ「ｗｉ」は、ラバーバンド関数の幅を表し、パラメータ「ｓｉ」は、ラバーバンド関数の縮尺を表す。
ラバーバンド関数は、２つのパラメータを利用して、基となるグラフィカル画像の解析に基づき、隣接する頂点間の経路を定義する。
ラバーバンド関数が、基となるグラフィカル画像を解析するので、大幅な符号化の改善が達成される。
具体的には、基となるグラフィカル画像の解析によって、基となるグラフィカル画像と境界定義との間の相関の除去が可能になる。
【００１８】
符号化アルゴリズムを詳細に説明する前に、ラバーバンド関数を説明することが適当である。
ラバーバンド関数は、グラフィカル画像において選択されたまたは特定された点間の境界を漸進的に検出する関数である。
ラバーバンド関数を先に実施したものは、Huitao LuoおよびAlexandros Eleftheriadis著のDesigning an Interactive Tool for Video Object Segmentation and Annotation, ACM Multimedia 1999に詳細に説明されている。
この文献は、参照により本明細書に援用される。
本発明の実施の形態は、ラバーバンド関数のこの先に実施したものの機能の多くを利用する。
加えて、本発明の実施の形態は、縮尺パラメータｓｉの使用など、本発明の特徴を追加して利用することもできる。
【００１９】
図４は、本発明の実施の形態に従ってラバーバンド関数により検出された境界４０１の例示の説明図を示している。
検出プロセスは、２つの頂点（ｖ１およびｖ２）を特定することにより行われる。
さらに、２つのパラメータを利用して、ラバーバンド関数のエッジ検出オペレーションが定義される。
最初に、パラメータ「ｗ」を空間制約として利用し、検出プロセスに関連付けられた探索区域が限定される。
パラメータ「ｗ」は、エッジ検出が実行される長方形４０２の幅を画定する。
次に、パラメータ「ｓ」（図示せず）を利用して、後に詳述するように、勾配関数の縮尺が定義される。
【００２０】
ラバーバンド関数は、２つの頂点、供給されたパラメータ、および基となるグラフィカル画像を利用して、輪郭Ｂ'＝（ｂ'０，ｂ'１，ｂ'２，ｂ'３，…ｂ'ｎ）を検出する。
ここで、ｂ'ｉは、検出された輪郭のｉ番目のピクセルであり、ｂ'０＝ｖ１であり、ｂ'ｎ＝ｖ２である。
輪郭（Ｂ'）は、基となるグラフィカル画像の勾配によって生成された重みに基づいて頂点（ｖ１およびｖ２）間の最短経路を計算することにより検出される。
【００２１】
さらに、ラバーバンド関数は、グラフとして画像をモデル化する。
このグラフは、各ピクセルが頂点であり、かつ、各頂点が（図５の頂点５０１によって示されるように）その８つの近傍ピクセルにリンクする８つのエッジのみを有するグラフである。
ラバーバンド関数の基本手順は、２つのステップ、すなわち以下のようなローカル特徴計算ステップおよびグラフ探索ステップを含む。
【００２２】
第１のステップにおいて、スケーラブルエッジ検出演算子によってローカル画像勾配の特徴が計算される。
この画像勾配の計算は、ローカル画像の所与の点における変化（例えば、グレースケール値または赤／緑／青（ＲＧＢ）値の変化）の相対的な量を決定する。
さらに、画像勾配は、ローカルな近傍上の変化に基づいて決定することができる。
画像勾配の目的は、より大きな勾配に関連付けられた経路がより小さな距離または重みに関連付けられるように、最短経路解析を重み付けすることである。
この目的のため、スケーラブルカーネルを有するラプラシアン（Laplacian with scalable kernels）、ガウシアンのラプラシアン（ＬｏＧ（Laplacian of Gaussian））演算子などの複数の異なる演算子を使用することができる。
図５にエッジ５０２として示すような各グラフエッジｅ（ｐ，ｑ）に対して、好ましくは、重みまたはローカル距離ｄｉｓｔ（ｐ，ｑ）を次のように定義することができる。
ｄｉｓｔ（ｐ，ｑ）＝１／（勾配（ｑ）＋ｃ）、
ここで、ｃは小さな定数である。
【００２３】
上記重みの定義により、画像は、重み付けされた有向グラフに変換される。
このグラフにおいて、ラバーバンド関数は、２つの頂点ｖ１、ｖ２を２つの基準点として使用する。
エッジ検出問題、すなわち、ｖ１からｖ２へのオブジェクトの輪郭を検出することは、次に、最短経路探索解析として処理される。
具体的には、輪郭は、ｖ１から開始してｖ２で終了する最短距離経路を特定することによって検出される。
この解析は、ダイクストラのアルゴリズム（例えば、T. H. Cormen、C. E. Leiserson、およびR. L. Rivest著のIntroduction to Algorithms, chapter 25.2, MIT Press, 1990を参照。
これによって、この文献の開示は、参照により本明細書に援用される）または例として後に詳述する制御されたフラッディングアルゴリズムを使用することによって行うことができる。
【００２４】
前述したように、ｖ１およびｖ２は、グラフ探索の基準点を決定し、ｗは、ラバーバンドの幅である。ｗは、ｖ１およびｖ２と共に、ダイクストラ探索アルゴリズムが実行される長方形の形状の近傍を画定する。この近傍の確定は、探索の複雑度を効果的に削減すると共に、近くの強い無関係な勾配の影響を除去することによってアルゴリズムの性能を改善する。
パラメータ「ｓｉ」は、画像勾配が計算される縮尺または近傍を決定する。
一般的に言えば、大きな縮尺ほど、画像のテクスチャノイズを除去する一方、縮尺が小さいほど、空間局在性（spatial localization）の改善を提供する。
【００２５】
エッジ検出の目的ではあるが、検出結果が、形状符号化用に許容できる限り、ｗおよびｓは共に、任意の値とすることができる。
さらに、ｗおよびｓは、レートと歪みとのトレードオフを表すように選択することができる。
実施の形態では、ｗｉは、３つの値｛１，１５，３１｝から選択され、ｓｉは、４つの値｛１，２，４，６｝から選択される（共にピクセルにおいて）。
したがって、（これらの値に限定される）ｗｉおよびｓｉは共に、本発明の実施の形態に従って符号化されるわずか２ビットのデータによって表すことができる。
好ましいコードワード設計に関するさらに詳細な内容は、後に詳述する。
【００２６】
本発明の実施の形態を厳密な数学的観点から説明する前に、例示のプロセスフローチャート６００を示す図６を次に参照する。
このプロセスフローチャート６００は、本発明の実施の形態による比較的高いレベルの境界情報処理を説明するものである。
【００２７】
ステップ６０１において、グラフィカル画像が受け取られる。
ステップ６０２において、グラフィカル画像におけるオブジェクトの境界定義が受け取られる。
例えば、ユーザは、境界の各点または各ピクセルを指定することができる。
【００２８】
この境界定義から、探索可能頂点集合が特定される（ステップ６０３）。
探索可能頂点集合は、最終的な境界符号化データ構造体の頂点として利用できる境界定義の許容可能な点を定義する。
探索可能頂点集合は、境界符号化アルゴリズムの複雑度を削減するために、境界定義ほど多くの点またはピクセルを含まないことが好ましい。
後に詳述するように、さまざまな判断基準を使用して、境界定義から点を選択し、探索可能頂点集合を形成することができる。
【００２９】
ステップ６０４において、探索可能頂点集合で選択された頂点対に対して、ラバーバンド関数が、各頂点対の間で、十分な精度を有する境界定義の各部分または各「エッジ」に近似するかどうかが判断される。
探索可能頂点集合における頂点対の解析は、アルゴリズムの複雑度を削減するために、選択された対に限定されることが好ましい。
歪み解析用の頂点対の選択の判断基準は、後に詳述する。
【００３０】
ステップ６０４において行われる判断は、２つの輪郭間の歪みまたは形状の差を評価するためのものである。
このため、複数のメトリックが適用可能である。
好ましい実施態様では、面積差メトリック（area difference metric）が使用される。
この場合、ステップ６０４における判断は、選択された各頂点対に対してラバーバンド関数によって検出された輪郭と、その頂点対間の境界定義の１組の点との間の閉区域が、歪み判断基準（Ｄｍａｘ）より小さいかどうかを評価する。
例えば、ｖ２０およびｖ３５が、探索可能頂点集合の頂点であると仮定する。
さらに、ｖ２０＝ｂ５７であり、ｖ３６＝ｂ７２である（すなわち、ｖ２０は、境界定義のｂ５７に対応し、ｖ３６は、境界定義のｂ７２に対応する）と仮定する。
ｖ２０およびｖ３５が、歪み判断基準（Ｄｍａｘ）を満たす場合には、これは、ラバーバンド関数の処理を介して点ｂ５７から点ｂ７２によって画定される境界情報の各エッジを近似するために（それらの各パラメータｗ、ｓを有する）ｖ２０およびｖ３５を利用できることを意味する。
【００３１】
ステップ６０５において、ステップ６０４で歪み判断基準（Ｄｍａｘ）を満たすと判断された頂点対から、頂点対集合（Ｖｐ）が形成される。
あるいは、歪み判断基準に従って頂点対を分離する代わりに、歪み判断基準を満たさない頂点対に無限大の距離または重みを割り当てて、最短経路解析からそれらを考慮しないようにすることができる（以下のステップ６０６を参照）。
【００３２】
頂点対集合（Ｖｐ）から、境界をトラバースする最短経路が、ステップ６０６において特定される。
上述したように、歪み判断基準を満たす各頂点対を利用して、各頂点対に関連付けられた各エッジを近似することができる。
最短経路は、最小の頂点数で境界全体をトラバースする経路である。
この最短経路の頂点は、集合Ｖｆとして指定される。
【００３３】
Ｖｆの頂点は、後に詳述するように、ステップ６０７において差分符号化（differentially encoded）される。
ステップ６０８において、各パラメータｗおよびｓが、差分符号化されたＶｆの頂点に関連付けられて、本発明の実施の形態による符号化境界データ構造体を形成する。
ステップ６０９において、プロセスフローは終了する。
【００３４】
本発明の実施の形態を数学的により詳細に説明するには、いくつかの用語を定義することが適当である。
ｂｉを境界のｉ番目のピクセルとすると、集合Ｂ＝｛ｂ０，ｂ１，ｂ２，ｂ３，…ｂｎ｝は境界定義である。
ｌ>ｋとなるＢの２つの点（ｂｋおよびｂｌ）を与えると、エッジは、点ｂｋから点ｂｌ（ｂｋおよびｂｌを含む）として画定される。
【００３５】
点ｂｋ，ｂｌに関連付けられたエッジと、ラバーバンド関数によって特定された検出境界との差を評価するために、エッジ歪み関数（ｄ（ｂｋ，ｂｌ））が定義される。
上述したように、エッジによって囲まれた領域の面積サイズを使用することができ、検出境界を選択されたメトリックとして使用して、歪みを評価することができる。
読み手の便宜のため、図７は、エッジ７０３とラバーバンド関数が検出した境界７０２（これらの双方は点ｂｋおよびｂｌを含む）とによって画定された区域７０１を図的に示している。
しかしながら、本発明の実施の形態に従って他の適切なメトリックを利用できることも理解されよう。
【００３６】
一般的に、符号化解析は、順序付けられた頂点集合
【００３７】
【数１】
2006501530.tif 000003
【００３８】
およびその対応するエッジ集合Ｅ＝｛ｅｉ：ｅｉ＝ｅ（ｖｉ，ｖｉ＋１），ｉ＝０，１，…，Ｎｖ−２，ｖｉ∈Ｖ｝の形で、境界定義（Ｂ）の最適な表現を見つけ出す。
ここで、ｖｉはｉ番目の頂点であり、ＮＶはＶｆの頂点の総数であり、ｅｉはＥのｉ番目のエッジである。
この表現において、各エッジｅｉ＝ｅ（ｖｉ，ｖｉ＋１）は、以下の４つ組に関連付けられる。
（ｆｉ，ｐｉ，ｖｉ，ｖｉ＋１），（ｉ＝０，１，…，ＮＶ−２）
ここで、ｆｉは関数であり、所定の関数集合Ｆ＝｛ｆ（０），ｆ（１），…｝の１つである。
（ｐｉ，ｖｉ，ｖｉ＋１）は、関数ｆｉによって使用されて境界Ｂｉ'＝｛ｂ０（ｉ），ｂ１（ｉ），…，ｂｌ（ｉ）｝を生成するパラメータである。
ｐｉは、一般に、頂点パラメータｖｉおよびｖｉ＋１に加えてｆｉによって使用されるパラメータを示すことに留意されたい。
Ｂｉ'は、境界Ｂの部分表現とみなされる。
境界
【００３９】
【数２】
2006501530.tif 000004
【００４０】
は、互いに連結されると、境界
【００４１】
【数３】
2006501530.tif 000005
【００４２】
を構成する。
この境界Ｂ'は、元の境界Ｂの近似表現とみなされる。
【００４３】
最適化問題は、一般的なレートおよび歪みの意味で定式化することができる。
ｒ（ｆｉ，ｐｉ，ｖｉ，ｖｉ＋１）が、エッジｅ（ｖｉ，ｖｉ＋１）を符号化するのに使用されるレート（例えば、ビットレート）を示すものとする。
この場合、境界全体の符号化レートは、
【００４４】
【数４】
2006501530.tif 000006
【００４５】
となる。
したがって、最適化は次のように定式化される。
【００４６】
【数５】
2006501530.tif 000007
【００４７】
ただし、以下を条件とする。
【００４８】
【数６】
2006501530.tif 000008
【００４９】
Ｆ、Ｐ、Ｖは、ｆｉ、ｐｉ、ｖｉがそれぞれ選択される探索可能集合または許容可能集合を指すことに留意されたい。
加えて、形状差関数ｄｉｆｆ（Ｂ，Ｂ'）は、ＢとＢ'との間の符号化歪みを評価する。
この関数は、２つの方法でエッジ歪みｄ（ｂｋ，ｂｌ）に関連付けることができる。
第１の方法は、以下の最大演算子である。
【００５０】
【数７】
2006501530.tif 000009
【００５１】
第２の方法は、以下の総和演算子である。
【００５２】
【数８】
2006501530.tif 000010
【００５３】
これより前では、本発明の実施の形態を読み手に説明する便宜上、最大演算子を実施する本発明の実施の形態を説明してきた。
総和演算子は、幾分、概念的にはより複雑ではあるが、総和演算子は、本発明の別の実施の形態に従って実施するのに比較的直接的なものである（例えば、G. H. SchusterおよびA. K. Katsaggelos著「An Optimal Polygonal Boundary Encoding Scheme in the Rate Distortion Sense」IEEE Trans. Image Processing, vol.7, no.1, 1998を参照。
これによって、この文献の開示は、参照により本明細書に援用される）。
【００５４】
上記に定式化された最適化問題は、最短経路グラフ探索問題としてモデル化され、動的計画法（ＤＰ）で解が求められる。
グラフのモデル化の基本原理は、符号化レートおよび各エッジの歪みの双方をローカルに決定できるということである。
【００５５】
順序付けられた頂点集合Ｖｆは、頂点集合Ｂから探索される一方、関数ｆｉおよびパラメータｐｉは、ラバーバンドの定義空間から探索される。
上述したように、ｗｉを３つの値｛１，１５，３１｝から選択し、ｓｉを４つの値｛１，２，４，６｝から選択することによって、許容可能パラメータ集合Ｐが限定されることが好ましい。
Ｂから２つの任意の頂点ｂｋ、ｂｌを与えると、ｂｋからｂｌへのエッジを符号化するのに必要なレートは、次のように決定される。
ｒ（ｅ（ｂｋ，ｂｌ））＝ｒ（ｆ＊，ｐ＊，ｂｋ，ｂｌ）
ここで、（ｆ＊，ｐ＊）は、以下の式によって決定される。
【００５６】
【数９】
2006501530.tif 000011
【００５７】
ここで、関数ｄ（）は、上記で定義した歪み関数である。
したがって、その結果として、この関数およびパラメータの探索は、頂点探索から分離することができる。
さらに、所与のエッジｅ（ｂｋ，ｂｌ）の重みは、頂点ｂｋおよびｂｌによって一意に決定することができる。
したがって、所与のエッジの重み（ｗ（ｂｋ，ｂｌ））を以下のように定義することができる。
ｄ＊（ｂｋ，ｂｌ）<Ｄｍａｘの場合には、ｗ（ｂｋ，ｂｌ）＝ｒ（ｂｋ，ｂｌ）、それ以外の場合には、∞
ここで、ｄ＊（ｂｋ，ｂｌ）＝ｄ（ｆ＊，ｐ＊，ｂｋ，ｂｌ）であり、上記で説明したように定義されるｆ＊、ｐ＊を有する。
重み定義により、重み付けされた有向グラフＧは、頂点集合Ｖ＝Ｂおよびエッジ集合Ｅ＝｛（ｂｋ，ｂｌ），∀ｋ≠ｌ｝で定義される。
次に、上記で定義した最適化問題は、次のように、グラフＧにおける最短経路問題として定式化することができる。
まず、最初の頂点ｖ０＝ｂ０がすでに決定されていると仮定し、最適解Ｖｆの最初のｉ個の頂点｛ｖ０，…，ｖｉ｝および各エッジ｛ｅ（ｖ０，ｖ１），…，ｅ（ｖｉ―１，ｖｉ）｝を符号化するのに使用されるレートをＲｉとして表記するものと仮定する。
【００５８】
この場合、その結果として、グラフＧにおけるｖ０＝ｂｍからｖｉ＝ｂｎへの最短経路に対応する（それ以外の場合には、Ｖｆは、仮定されるような最適解ではない）
【００５９】
【数１０】
2006501530.tif 000012
【００６０】
となる。
したがって、この問題は、ｎ＝１，２，…，ＮＢ−１についてｖ０＝ｂｏからｖｉ＝ｂｎへの最短経路を見つけ出すことにより漸進的に解くことができる。
閉じた境界Ｂの場合、
【００６１】
【数１１】
2006501530.tif 000013
【００６２】
であることに留意されたい。
また、
【００６３】
【数１２】
2006501530.tif 000014
【００６４】
でもある。
グローバルな最小値を見つけ出すために、Ｖの最初の頂点ｖ０を、Ｂのあらゆる頂点位置にわたって移動させて、対応する
【００６５】
【数１３】
2006501530.tif 000015
【００６６】
を比較することができる。
【００６７】
したがって、最小化問題は、数学的観点から解くことができる。
しかしながら、最短経路探索に基づくそのままの形の解は、容易に分かるほどの複雑度を有する。
その理由は、最短経路探索の各ラウンドは、θ（｜Ｖ｜２＋｜Ｅ｜）の複雑度を有する一方、最初の頂点ｖ０をあらゆる可能なものに変更することは、この複雑度をθ（｜Ｖ｜３＋｜Ｅ｜・｜Ｖ｜）にさらに増大させるからである。
したがって、以下の制約および発見的方法を利用して、複雑度を削減することが好ましい。
【００６８】
最初の頂点ｖ０は、最も曲率の高いＢの点と決定される。
説明を簡単にするために、ｖ０＝ｂ０となるようにＢのラベルを付け替えるものとする。
この発見的方法は、符号化品質にほとんど影響を与えることなく、最短経路探索の複雑度をθ（｜Ｖ｜２＋｜Ｅ｜）に削減する。
【００６９】
Ｇのエッジ集合は、Ｅ＝｛（ｂｋ，ｂｌ），ｋ<ｌ｝となるように限定される。
これにより、Ｇは、重み付けされた非循環有向グラフになり、探索の複雑度は、θ（｜Ｖ｜＋｜Ｅ｜）にさらに削減される。
【００７０】
Ｂの各点ｂｌに対して、（ｌ−ｋ）<Ｌｓを要求することにより、Ｇの可能なエッジｅ（ｂｋ，ｂｌ）はさらに制約される。
ここで、Ｌｓは、発見的方法によって決定される定数である。
この要求により、｜Ｅ｜＝Ｌｓ・｜Ｖ｜となり、複雑度はθ（Ｌｓ・｜Ｖ｜）となる。
【００７１】
Ｇの頂点数は、２つの方法により境界定義Ｂの点をサブサンプリングすることによって削減されることが好ましい。
第１に、頂点集合
【００７２】
【数１４】
2006501530.tif 000016
【００７３】
は、ｂ０（ｓ）＝ｂ０と設定して、次のように再帰的に成長することによって得られることが好ましい。
ｂｉ（ｓ）＝ｂｋ，ｂｋ∈Ｂが決定されたものと仮定すると、ｂｉ＋１（ｓ）＝ｂｌは、０<（ｌ−ｋ）<ｎｓかつｄ＊（ｂｋ，ｂｌ）<Ｄｍａｘを条件としてｌを最大にするｂｉ∈Ｂを探すことによって決定される。
ここで、ｄ＊（）は、上記で定義した歪み関数であり、ｎｓは、発見的方法によって設定された定数である。
第２に、別の頂点集合
【００７４】
【数１５】
2006501530.tif 000017
【００７５】
が、所定の閾値よりも大きなローカルな曲率を有するＢの点を特定することによって決定される。
次いで、Ｇの最終的なまたは探索可能な頂点集合が、Ｖ＝Ｂ（ｓ）∪Ｂ（ｃ）として定義される。
一般的に言えば、Ｖが、ｎによってサブサンプリングされると、複雑度は、θ（Ｌｓ・｜Ｖ｜／ｎ２）になる。
【００７６】
一般的に、本発明の実施の形態に従って符号化された境界情報の符号化要素は、４つ組（ｆｉ，ｐｉ，ｖｉ，ｖｉ＋１）である。
本発明の実施の形態によれば、符号化要素は、好ましくは、符号化の４つ組（ｒｉ，ｃｉ，ｗｉ，ｓｉ）によって表すことができる。
ここで、（ｒｉ，ｃｉ）は、頂点ｖｉの行および列の座標であり、ｗｉおよびｓｉは、それぞれ、エッジｅ（ｖｉ，ｖｉ＋１）に対応するラバーバンドの幅および縮尺である。
付加的な冗長を除去するために、頂点座標は、（ｄｒｉ，ｄｃｉ，ｗｉ，ｓｉ）の形に差分符号化されることが好ましい。
ここで、ｄｒｉ＝ｒｉ−ｒｉ−１，ｄｃｉ＝ｃｉ−ｃｉ−１である。
【００７７】
以下の表１は、本発明の実施の形態に従って境界を符号化するのに利用できる例示のコードワードを示している。
さらに、表２は、本発明の実施の形態に従って、符号化された形状データをバイナリファイルに保存する（または、ネットワークを介してそれらのデータをストリーミングする）のに使用される例示のビットストリーム構文を示している。
【００７８】
【表１】
2006501530.tif 000018
【００７９】
【表２】
2006501530.tif 000019
【００８０】
ｒ［ｉｎｔ（１６）］は、整数変数「ｒ」を１６ビットで符号化することを指す一方、ｗ［ｕｎｉｔ（２）］は、符号なし整数変数「ｗ」を２ビットで符号化することを意味することに留意されたい。
本発明の実施の形態では、整数ｘをビット長ｌで符号化することは、ｘを２（ｌ−１）で加えてｘを［０，２ｌ）にマッピングすることにより実施される一方、符号なし整数をビット長ｌで符号化することは、その最も左のｌビットを保存することを伴う。
表２では、差分座標（ｄｒ，ｄｃ）の符号化に使用されるビット長ｌは、頂点集合Ｖ全体にわたってそれらの絶対極大値を見つけ出すことによって決定される。
また、表２に記載したビットストリーム構文は、１つのオブジェクト（境界）のみを記載しているが、これを複数のオブジェクトのフォーマットに拡張することは簡単であることに留意することも適当である。
【００８１】
本発明の実施の形態は、既知の境界符号化アルゴリズムまたは形状符号化アルゴリズムにいくつかの利点を提供する。
具体的には、本発明の実施の形態によって、情報量を大幅に削減して境界を符号化することが可能になる。
具体的には、最小限の頂点数を選択して境界を表すことができる。
本発明の実施の形態は、この最小限の頂点数および基となる画像から境界を復元するので、この最小限の頂点数は、境界を記述するのに十分である。
したがって、本発明の実施の形態は、境界データと基となる画像データとの相関を除去するように働き、したがって、所望の符号化効率を達成する。
本発明の実施の形態によって、閉じた形の数学的表現を必要とせずに、境界データと基となる画像データとの相関を除去することがさらに可能になる。
その上、本発明の実施の形態は、探索可能頂点集合を生成すること、および、可能なエッジ集合を限定することによって符号化プロセスの複雑度をさらに削減し、それによって、ユーザ指向アプリケーションに適切な処理効率を達成する。
【００８２】
ラバーバンド関数は、効率的な方法で境界を符号化することに加えて、ユーザ入力に関連して境界を画定するのに利用することができる。
図８は、本発明の実施の形態に従って、ラバーバンド関数およびユーザとの対話を利用して境界定義を作成することを示す例示のフローチャート８００を示している。
ステップ８０１において、入力画像が受け取られる。
この入力画像は、任意の個数の適切なグラフィカルフォーマットの１つとすることができる。
ステップ８０２において、入力画像（グレースケール表現またはカラー表現のいずれか）が、まず、スケーラブルエッジ検出器によって処理される。
複数の縮尺で勾配を計算することが有利である。
【００８３】
ステップ８０３において、ユーザとの対話および自動縮尺選択を利用して輪郭を成長させるために、ラバーバンドユーザインタフェースが使用される。
具体的には、ユーザは、グラフィカル画像の各オブジェクトの境界上で複数の頂点を選択する。
ステップ８０３において、ユーザが、例えばマウス周辺機器でユーザインタフェースを操作するに従って、対応する輪郭が、利用可能なローカル勾配情報に基づいて自動的に表示される。
上述したように、ラバーバンド関数は、２つの基準点間または２つの頂点間の輪郭を検出する。
さらに、ラバーバンド関数は、その探索解析を、２つの基準点および幅パラメータによって画定された長方形の区域に限定する。
このユーザインタフェースによって、ユーザは、基準点および幅パラメータを選択することが可能になる。
その上、縮尺パラメータは、後に詳述するように、ユーザとの対話から自動的に決定される。
検出された輪郭が、ユーザ入力によって定義された境界セグメントと一致すると、制御点（各頂点対）は、ユーザからの適切な入力（例えば、１つまたはいくつかのマウスクリック）によって固定することができる。
この対話プロセスは、閉じた境界が画定されるまで繰り返される。
【００８４】
ステップ８０４において、ユーザとの対話をさらに利用して、閉じた境界の後処理およびノード編集を実行することができる。
ステップ８０５において、ユーザが選択したオブジェクトを定義するために、オブジェクト記述データ構造体（例えば、境界定義、サポートマップなど）が作成される。
ステップ８０６において、グラフィカル情報（すなわち、入力画像およびオブジェクト記述データ構造体）を適切なフォーマットに変換することができる。
この適切なフォーマットには、画像交換フォーマット（ＧＩＦ）、ＭＰＥＧ−４、ポータブルネットワークグラフィックス（ＰＮＧ）などが含まれるが、これらに限定されるものではない。
【００８５】
ユーザ入力に関連してオブジェクトの境界を画定する本発明の実施の形態によれば、ラバーバンド関数の実施態様を、「制御されたフラッディング（Controlled Flooding）」アルゴリズムと呼ぶことができる。
この制御されたフラッディングアルゴリズムは、近傍のノイズの存在に対してより強固であるので、ダイクストラの探索アルゴリズムを上回る改良アルゴリズムである。
その上、ラバーバンド関数の他の実施態様を説明した初期の刊行物（例えば、Designing an Interactive Tool for Video Object Segmentation and Annotation, ACM Multimedia 1999）には、適応型閾値が開示されていないことが理解されよう。
制御されたフラッディングアルゴリズムでは、適応型閾値Ｔを使用して、グラフ探索プロセスが制御される。
あらゆるピクセル対の元のローカル距離がＴよりも大きい場合には、その距離は無限大に設定される。
このように、グラフ探索が、これらの点に到達することが防止される。
後に詳述するように、このワークにおけるこのローカル距離の定義により、この閾値処理尺度は、グラフ探索が弱い勾配を有する領域に到達することを防止することと等価となる。
【００８６】
アルゴリズムは、一方の制御点から開始し、探索プロセスが他方の制御点に到達するまで、閾値をδＴ（δＴ>０）ずつ増加させるように制御して探索プロセスを繰り返す。
このように、強い近傍のエッジは、強いエッジによって２つの制御点に接続されないと、実際の輪郭の検出からこの探索アルゴリズムを逸らす確率が低くなる。
【００８７】
この概念を図９Ａ〜図９Ｃに示す。
図９Ａには、近傍のパターンを示す。
ユーザは、輪郭Ｂを所望の結果として、２つの制御点ｆおよびｅを選択している。
しかしながら、別の輪郭Ａが近傍に存在し、Ａはより強い勾配を有するので、図９Ｂによって示すように、グローバルな最小値が得られると、グラフの探索結果は、輪郭Ａに引き付けられる。
これは、ダイクストラのアルゴリズムが使用される場合に頻繁に発生する一般的な問題である。
しかしながら、制御されたフラッディングアルゴリズムが適用されると、制御点ｆおよびｅから輪郭Ａ上の点への探索経路が、閾値Ｔによって防止されるので、グラフ探索は、輪郭Ａに到達することができない。
成功した探索結果を図９Ｃに示す。
【００８８】
制御されたフラッディングアルゴリズムを詳細に説明するには、補助データ構造体および関係する関数を定義することが適当である。
データ構造体Ｌは、探索プロセスをガイドするのに使用されるアクティブリストである。
以下の４つの関数が、Ｌ用に定義されている。
１．ｐｕｓｈ（Ｌ，ｐ，ｄ）（プッシュ）は、ピクセルｐおよびその（開始点からの）累積経路距離ｄ＝Ｃ（ｐ）をリストに保存するのに使用される。
２．ｐｏｐ（Ｌ，ｐ）（ポップ）は、累積経路が現リストにおいて最小であるピクセルｐを取り出すのに使用される。
３．ｎｕｍ（Ｌ）は、リストに保存されたピクセルの個数を返すのに使用される。
４．ｒｅｍｏｖｅ（Ｌ，ｐ）（削除）は、ピクセルｐがリストに存在する場合に、リストからピクセルｐを削除するのに使用される。
【００８９】
Ｌを実施するのに利用されるデータ構造体に応じて、これらの関数を実施するのに、さまざまな実施態様を利用することができる。
データ構造体Ｌの例示の実施態様は、ピクセルの累積経路距離ｄに関して記憶されたリストである。
挿入／取り出し性能を改善するために、当該技術分野において既知の「バケット」構造体など、他のソート構造体を利用することもできる。
【００９０】
ｐ，ｑが、２つの８接続ピクセルであると仮定すると、関数Ｄｉｓｔ（ｐ，ｑ）は、ｐとｑとの間のローカル距離を定義する（関数Ｄｉｓｔ（）の例示の定義は後に詳述する）。
Ｎ（ｐ）は、ピクセルｐの８接続近傍集合を示す。
さらに、ｐｔｒ（ｐ）を、ピクセルｐの最適な経路ポインタとする。
すなわち、ｐｔｒ（ｐ）が、最適な経路上のその前のピクセルを指すものとする。
この場合、制御されたフラッディングアルゴリズムは、図１０の擬似コードで表現することができる。
【００９１】
図１０の擬似コードでは、ステップ１００１〜１００４は、補助データ構造体を初期化する。
ステップ１００５〜１０２７は、探索解析を行う。
これらのステップのうち、ステップ１００６〜１０２４は、（現閾値Ｔによって制約される）制約された探索関数である。
ステップ１０１０〜１０１２は、閾値比較を行い、閾値によって成長が制限されると、変数「ｆｌａｇ＿ｔｈｒｅｓｈｏｌｄ（フラグ閾値）」が設定される。
ステップ１０２１〜１０２３では、「ｆｌａｇ＿ｔｈｒｅｓｈｏｌｄ」が設定されていると、現在のピクセルが、バックアップアクティブリスト（Ｌ２）にプッシュされる。
このオペレーションの目的は、今後のプロセスの可能な開始ピクセルとしてこのピクセルを保存することである。
現アクティブリスト（Ｌ１）のすべてのピクセルが処理される（すなわち、グラフが、現閾値が許容するのと同程度に成長する）と、閾値が、ステップ１０２５においてδＴだけ増加され、バックアップアクティブリスト（Ｌ２）が、現アクティブリスト（Ｌ１）に移動され、他方の基準点ｅ（終了点）に到達するまで、プロセス全体が繰り返される。
【００９２】
グラフ探索プロセスの精度を維持するのに重要な事項は、関数Ｄｉｓｔ（ｐ，ｑ）の適当なローカル距離定義を定義することである。
概念的には、この関数は、ピクセルｐ、ｑにおけるエッジの勾配の大きさおよび向きに関係付けられるべきである。
しかしながら、ユーザの主観的なエッジの理解が、画像のグレースケールまたはＲＧＢ成分における信号の不連続と異なることがある。
テクスチャ性の高い領域は、「均一」とみなすことができ、そのテクスチャに関連付けられた強い勾配は、ユーザの視点からは「エッジ」として見えない。
その理由は、観察の異なる縮尺に応じて、「均一性」の定義が変化するからである。
ユーザの予想と一致するセグメント化の結果を生成するには、適当な縮尺を選択することが有利である。
【００９３】
この目的を達成するために、ラバーバンドによって定義された近傍区域が利用される。
ユーザは、（関係する境界セグメントがラバーバンドの内部に位置することを確認するために）このラバーバンド長方形のサイズおよび位置を制御するので、自身がオブジェクトを観察する縮尺を暗に指定することも行う。
したがって、この近傍区域内の画像の特徴解析により、意図した縮尺を決定することが容易になる。
したがって、ＭＤＬ（最小記述長（minimal description length））原理に基づくアルゴリズムが、自動的な縮尺の選択を行う。
【００９４】
本発明の実施の形態によれば、領域ベースエッジ検出器が利用される。
この領域ベースエッジ検出器は、異なる近傍のサイズに基づいてエッジ強度を計算するスケーラブル演算子である。
領域ベースエッジ検出器は、ラプラシアンやガウシアンのラプラシアン（ＬｏＧ）などの従来のスケーラブル演算子よりも大きな空間局在性を実証する。
なお、領域ベースエッジ検出器が好ましいが、従来のスケーラブル演算子も、自動的な縮尺の選択に関連して本発明の実施の形態に従い利用することができる。
【００９５】
領域ベースエッジ検出器では、エッジは、異なる領域間の境界として検出される。
図１１に示すように、ピクセルｐについて、そのエッジの勾配は、３つの領域Ｒ＝Ｒ１＋Ｒ２、Ｒ１、およびＲ２にわたって解析される。
領域均一性関数（region homogeneity function）Ｈ（・）が定義され、勾配の大きさが、ｍａｇ＝１／２［Ｈ（Ｒ１）＋Ｈ（Ｒ２）］−Ｈ（Ｒ）として定義される。
異なる角度を利用して勾配を検出するために、領域テンプレートをＲ（θ）、Ｒ１（θ）、およびＲ２（θ）に回転させることができる。
次いで、最終的な勾配（大きさおよび向き）が、次のように定義される。
【００９６】
【数１６】
2006501530.tif 000020
【００９７】
正確な勾配の定義は、均一性関数Ｈ（・）の定義ならびに近傍領域テンプレートＲ、Ｒ１、およびＲ２の定義に依存する。
本発明の実施の形態では、Ｒは、円盤であり、Ｒ１およびＲ２は、それぞれ、各ピクセルを中心とする半円盤である。
向きは、範囲［０，π）から一様にサブサンプリングされた４つの角度にわたって計算される。
円盤の半径は、エッジ検出器の倍率ｓを表すのに使用される。
倍率ｓを含めることにより、前述の大きさおよび向きの方程式は、次のように表現することができる。
【００９８】
【数１７】
2006501530.tif 000021
【００９９】
均一性関数Ｈ（・）は、より柔軟な方法で設計することができる。
本発明の実施の形態によれば、標準偏差尺度が利用される。
ただし、任意の個数の他の適切な尺度を利用することもできる。
この標準偏差尺度は、次のように表現することができる。
【０１００】
【数１８】
2006501530.tif 000022
【０１０１】
ここで、ｖｉは、ピクセル特徴ベクトル（pixel feature vector）であり、‖・‖は、ユークリッドノルムである。
【０１０２】
【数１９】
2006501530.tif 000023
【０１０３】
は、次のように定義される。
【０１０４】
【数２０】
2006501530.tif 000024
【０１０５】
さまざまな画像タイプに応じて、特徴ベクトルｖの長さは、１（グレースケール）、３（ＲＧＢ）、またはｎ（マルチスペクトル）とすることができる。
【０１０６】
特定の演算子の縮尺ｓに対して、ローカル距離尺度が、上述した勾配定義に基づき定義される。
【０１０７】
【数２１】
2006501530.tif 000025
【０１０８】
を点ｐにおける勾配ベクトルとし、
【０１０９】
【数２２】
2006501530.tif 000026
【０１１０】
を、ベクトルｐ−ｑに垂直な単位ベクトルとする（上述したように、向きは、範囲［０，π）で計算され、したがって、この節で述べたすべてのベクトルは、この範囲にマッピングされる）。
この勾配は、まず、以下によって線形にマッピングされ、その大きさが［０，１］の範囲にされる。
【０１１１】
【数２３】
2006501530.tif 000027
【０１１２】
ここで、ｇｍａｘおよびｇｍｉｎは、それぞれ、画像全体にわたる極大の勾配の大きさおよび極小の勾配の大きさである。
次いで、２つの近傍ピクセル対ｐとｑとの間のローカル距離が、次のように定義される。
Ｄｉｓｔ（ｐ，ｑ）＝Ｄｉｓｔｍａｇ（ｐ，ｑ）＋Ｄｉｓｔｏｒｉ（ｐ，ｑ）
ここで、Ｄｉｓｔｍａｇ（ｐ，ｑ）は、次のように定義される。
【０１１３】
【数２４】
2006501530.tif 000028
【０１１４】
また、Ｄｉｓｔｏｒｉ（ｐ，ｑ）は、次のように定義される。
【０１１５】
【数２５】
2006501530.tif 000029
【０１１６】
ここで、ｗ１、ｗ２は、重み係数であり、<，>は、ドット積演算子である。
【０１１７】
したがって、説明したスケーラブルエッジ検出器およびローカル距離定義を制御されたフラッディングアルゴリズムと共に利用することにより、輪郭ｃ（ｓ）を、２つの基準点ｆおよびｅとリンクして縮尺ｓで生成することができる。
次に、残りの事項は、適切な縮尺ｓを選択してアルゴリズムを実行することである。
【０１１８】
設計の観点から、縮尺が小さいほど、その縮尺による輪郭の結果は、空間的により正確になるが、テクスチャの近傍に敏感になる一方、縮尺が大きいほど、その縮尺による輪郭の結果は、テクスチャ領域との分離が良好に行われるが、空間的な精度を失うおそれがある。
このエッジ指向型アルゴリズムは、局所化された解であるので、ＭＤＬ原理を使用することにより、グローバルな尺度を組み合わせて、局所化されたバイアスが最終的な結果においてバランスされる。
【０１１９】
設計の観点から、縮尺が小さいほど、その縮尺による輪郭の結果は、空間的により正確になるが、テクスチャの近傍に敏感になる一方、縮尺が大きいほど、その縮尺による輪郭の結果は、テクスチャ領域との分離が良好に行われるが、空間的な精度を失うおそれがある。
このエッジ指向型アルゴリズムは、局所化された解であるので、ＭＤＬ原理を使用することにより、グローバルな尺度を組み合わせて、局所化されたバイアスが最終的な結果においてバランスされる。
【０１２０】
一般的な意味として、ＭＤＬ原理は、次のように定式化される。
【０１２１】
【数２６】
2006501530.tif 000030
【０１２２】
ここで、ｘは、記述／符号化される入力データであり、θは、モデル化パラメータであり、Ｐθ（ｘ）は、θが与えられた場合のｘの統計的分布であり、ｌｏｇＰθ（ｘ）およびＤＬ（θ）は、データおよびモデル化パラメータの記述／符号化長である。
ＭＤＬ原理によれば、データの符号化長およびモデル化パラメータの符号化長の合計を最小にすることによって、最適なデータモデル化方法が複数のモデルから選択される。
【０１２３】
この原理を輪郭解析に関連付けるために、本発明の実施の形態は、図１１に示すように、輪郭ｃ（ｓ）が、ラバーバンドの定義した近傍を２つの領域Ｒ１およびＲ２に分離することを考慮する。
入力データは、この近傍のピクセル色である一方、モデル化パラメータは、（１）セグメント化輪郭ｃ（ｓ）、（２）領域Ｒ１およびＲ２のそれぞれのピクセル色の統計的分布を記述するモデル化データを含む。
各領域の各ピクセル色成分が、空間的に独立し、同一のガウス分布を共有すると仮定すると、ＭＤＬ方程式は、以下の閉じた形に変換される。
ＤＬ＝Ｎ１・ｌｏｇσ１＋Ｎ２・ｌｏｇσ２＋ＤＬ（ｃ（ｓ））＋定数
ここで、σ１およびσ２は、それぞれ、領域Ｒ１およびＲ２のピクセル色の標準偏差であり、ＤＬ（ｃ（ｓ））は、輪郭ｃ（ｓ）の符号化長である。
最初の２つの項は、グローバルな均一性尺度である一方、最後の項は、境界の滑らかさの尺度である。
【０１２４】
したがって、最終的なセグメント化の結果は、導出されたＭＤＬ方程式から極小値を生成する輪郭ｃ（ｓ）から選択される。
オペレーション中、本発明の実施の形態は、４つの縮尺１、２、４、６（ピクセル）で候補となるセグメント化輪郭を計算することが好ましい。
可能な縮尺パラメータは、複雑度と性能とのトレードオフとして、特定の部分集合に限定される。
ＭＤＬ方程式は、候補となる各セグメント化輪郭に適用される。
最終的なセグメント化の結果（選択された縮尺に関連付けられた結果）は、ＭＤＬ方程式を最小にする候補である。
【０１２５】
図１２は、縮尺パラメータｓの自動的な選択を示すフローチャート１２００を示している。
ステップ１２０１において、グラフィカル画像の２つの頂点が（例えば、ユーザによって）特定される。
ステップ１２０２において、複数の輪郭が、２つの頂点間で検出される。
各輪郭は、異なる縮尺パラメータに関連付けられている。
ステップ１２０３において、（例えば、輪郭によって画定される領域間の分散を最小化することにより）ＭＤＬ方程式を最小にする縮尺パラメータが、最適な縮尺パラメータとして選択される。
【０１２６】
本発明の実施の形態は、ユーザとの対話と関連してオブジェクトの境界を画定するのに利用された場合にいくつかの利点を提供する。
具体的には、本発明の実施の形態は、自動的な縮尺の選択を使用することによって、主観的なユーザの予想とより多く一致することを達成する。
具体的には、２つの基準点間でラバーバンド関数を初期化する際に、ユーザによって画定された長方形区域内で、縮尺が解析される。
したがって、自動的な縮尺の選択は、ユーザの主観的な境界の知覚に関連して行われる。
特に、開示した自動的な縮尺の選択は、テクスチャ画像に関連した輪郭を検出する際に優れた性能を示す。
さらに、本発明の実施の形態は、適応型閾値探索判断基準を使用して、より高い空間的精度を達成することによって、強い近傍エッジによる異常な結果を生成する可能性が低い。
【図面の簡単な説明】
【０１２７】
【図１】本発明の実施の形態による、境界情報を符号化する例示のシステムを示す図である。
【図２】本発明の実施の形態を実施するのに利用できる例示のコンピュータシステムを示す図である。
【図３】例示の境界および例示の頂点を含むグラフィカル画像を示す図である。
【図４】本発明の実施の形態に従ってラバーバンド関数により検出された例示の境界を示す図である。
【図５】本発明の実施の形態による例示のピクセルおよびその関連したエッジを示す図である。
【図６】図６は、本発明の実施の形態による境界情報処理ステップの例示のプロセスフローチャート６００である。
【図７】本発明の実施の形態によるエッジおよびラバーバンド関数が検出した境界によって画定された例示の差分区域（difference area）を示す図である。
【図８】図８は、本発明の実施の形態によるオブジェクト境界の画定を示す例示のフローチャートである。
【図９Ａ】本発明の実施の形態によるグラフ探索プロセスの制御に適応型閾値を使用した場合に関連した例示の輪郭、および使用しない場合に関連した例示の輪郭を示す図である。
【図９Ｂ】本発明の実施の形態によるグラフ探索プロセスの制御に適応型閾値を使用した場合に関連した例示の輪郭、および使用しない場合に関連した例示の輪郭を示す図である。
【図９Ｃ】本発明の実施の形態によるグラフ探索プロセスの制御に適応型閾値を使用した場合に関連した例示の輪郭、および使用しない場合に関連した例示の輪郭を示す図である。
【図１０】図１０は、本発明の実施の形態による特定された頂点間の輪郭を検出する例示の擬似コードである。
【図１１】本発明の実施の形態によるエッジ検出用の領域テンプレートを示す図である。
【図１２】図１２は、本発明の実施の形態による縮尺パラメータを自動的に選択するフローチャートである。
【符号の説明】
【０１２８】
１０１・・・画像符号化、
１０２・・・形状符号化、
１０３・・・ネットワーク、
１０４・・・画像復号、
１０５・・・形状復号、
２０１・・・表示装置、
２０４・・・グラフィカル画像、
２０５・・・境界定義、
２０６・・・符号化境界、
２０８・・・媒体ドライブ、
２０９・・・境界符号化アルゴリズム、
２１０・・・通信アダプタ、
２１１・・・ネットワーク、
【図１】
2006501530.tif 000031
【図２】
2006501530.tif 000032
【図３】
2006501530.tif 000033
【図４】
2006501530.tif 000034
【図５】
2006501530.tif 000035
【図６】
2006501530.tif 000036
【図７】
2006501530.tif 000037
【図８】
2006501530.tif 000038
【図９Ａ】
2006501530.tif 000039
【図９Ｂ】
2006501530.tif 000040
【図９Ｃ】
2006501530.tif 000041
【図１０】
2006501530.tif 000042
【図１１】
2006501530.tif 000043
【図１２】
2006501530.tif 000044
【国際調査報告】
2006501530.tif 000045
2006501530.tif 000046
2006501530.tif 000047