(57)【要約】本発明は、マルチメディアデータに索引付けをし、そして検索するための方法に関する。特に、本発明は、マルチメディアデータの少なくとも２つのセット間の非類似性尺度を提供するために形状情報を使用して、前記マルチメディアデータの少なくとも２つのセットを比較する方法を提供する。本発明は、画像及びビデオシーケンス・データベースにおけるそれらの内容に基づき、画像、及びシーケンスの部分を検索する際の使用を見出す。
2006523345.tif 000002
【特許請求の範囲】
【請求項１】
マルチメディアデータの少なくとも２つのセット間の非類似性尺度を提供するために形状情報を使用して、前記マルチメディアデータの少なくとも２つのセットを比較する方法であって、第１のセットが参照セットを形成し、及び第２のセットが前記第１のセットと相対的に比較され、前記方法は、
ａ）マルチメディアデータの各セットについて輪郭点の１セットを用意すること、
ｂ）関連付けられた輪郭点を定義するために、前記第１のセットの輪郭点を前記第２のセットの輪郭点と関連付けること、
ｃ）前記関連付けられた輪郭点の間の距離を計算すること
のステップを含み、前記関連付けられた輪郭点の間の距離が、マルチメディアデータの前記セット間の非類似性尺度を決定するために使用され、それによって前記セット間の類似の程度の指標を提供する方法。
【請求項２】
マルチメディアデータの各セットのための輪郭点の前記セットが、マルチメディアデータの各セットの境界をトレースすることによって得られる、請求項１に記載の方法。
【請求項３】
輪郭点の前記セットがダウンサンプリングされて、各セットにおけるほぼ等しい間隔で離れた輪郭点の等しい数を生じる、請求項１又は２に記載の方法。
【請求項４】
輪郭点の前記セットが、互いに関連付けられる前にトランスレーションされ、そしてスケールサイズを正規化される、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
輪郭点の各セットについて開始点を確立するステップをさらに含み、前記開始点が、各セットについて全ての輪郭点を定義することによって確立され、その個々の輪郭の計算された重心点からの開始点の距離がそれらの個々の重心からの最も離れた輪郭点のユーザ定義された第１のパーセントＰ１よりも大きい、請求項１〜４のいずれか一項に記載の方法。
【請求項６】
前記方法は、前記ユーザが前記第１のパーセントＰ１を入力することを可能にするステップを含む、請求項５に記載の方法。
【請求項７】
開始点が、隣接する態様で確立される、請求項４又は５に記載の方法。
【請求項８】
隣接する開始点が、輪郭点の総数のユーザ定義されたパーセントＰ２未満を含むグループに分割される、請求項７に記載の方法。
【請求項９】
前記ユーザが前記第２のパーセントＰ２を入力することを可能にするステップを含む、請求項８に記載の方法。
【請求項１０】
開始点の各グループが、前記重心から最も離れている開始点によって表わされる、請求項８又は９に記載の方法。
【請求項１１】
参照開始点が、最大の数の開始点を有する輪郭点のセット上の最も離れた開始点又は最大の初期領域として得られ、及び比較されるべき前記セット上の各開始点について、比較されるべき前記セットが、その開始点を前記参照開始点と整列させるために回転される、請求項５〜１０のいずれか一項に記載の方法。
【請求項１２】
前記関連付けられた輪郭点が、輪郭点の前記セットの夫々に制御点を与えること、次に各セットの前記輪郭に沿って逐次的に前記制御点を移動することによって互いに関連付けられ、及び前記輪郭についての前記制御点の移動が、各セットからの輪郭点を互いに関連付けるために使用される、請求項１〜１１のいずれか一項に記載の方法。
【請求項１３】
各セットについての前記制御点の前記移動が、各セットの整列された開始点で開始される、請求項１２に記載の方法。
【請求項１４】
前記輪郭についての前記制御点の移動の各ステップで、２つの制御点間の距離、第１セット上の制御点と第２セット上の次の輪郭点との間の距離、及び第２セット上の制御点と第１セット上の次の輪郭点との間の距離が計算され、これら計算された距離の最小値を有する輪郭点が互いに関連付けられる、請求項１２又は１３に記載の方法。
【請求項１５】
前記制御点が前記輪郭点の全てに関して移動するまで、前記輪郭点が割り当てられる、請求項１２〜１４のいずれか一項に記載の方法。
【請求項１６】
各セットのスケールサイズを正規化された周線の尺度を得、前記周線の最小を決定し、そして関連付けられた輪郭点間の距離の平均及び標準偏差をさらに決定することによって、前記非類似性尺度が決定される、請求項１〜１５のいずれか一項に記載の方法。
【請求項１７】
前記非類似性尺度が、下記式
2006523345.tif 000025
（ここで、Ｄ（Ａ，Ｂ）はセットＡとセットＢとの間の非類似性であり、
ｃは、値の便利な範囲へと前記非類似性の値を再スケールするユーザ定義された定数を示し、
ｃｉｒｍｉｎは、最小の周線であり、
2006523345.tif 000026
｜Ｖ｜は、関連付けられた輪郭点の間の前記距離の標準偏差である）
によって提供される、請求項１６に記載の方法。
【請求項１８】
複数の非類似性尺度が計算され、各非類似性尺度が、比較される前記セットの特定の配置に関連付けられ、及び前記セット間の同等性のレベルの全体的表示を提供する最終の非類似性尺度が、計算された全ての非類似性尺度の最低値として与えられる、請求項１〜１７のいずれか一項に記載の方法。
【請求項１９】
添付の図面の１以上に関して記載された実質的に前記のような方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチメディアデータに索引付けをし、そして検索するための方法に関する。より詳細には、本発明は、マルチメディアデータオブジェクトから抽出された形状特徴情報に基づき、マルチメディア情報の少なくとも２つのセットの間の類似性索引（インデックス）を計算することに関する。
【背景技術】
【０００２】
大画像及びビデオシーケンス・データベースが、娯楽、ビジネス、芸術、エンジニアリング及び科学のような分野において多くのマルチメディア用途に使用されている。それらの内容に基づき、画像、又はシーケンスの部分を検索することが、重要な操作になっている。
【０００３】
形状分析方法は、オブジェクの認識、マッチング、登録及び分析のためのシステムにおいて重要な役割を果たす。しかしながら、形状による検索はまだ、内容に基づいた探索の最も困難な局面の一つであると考えられている。
【０００４】
マルチメディアデータ検索に対する解決の鍵は次の通りである：考慮されるべきマルチメディアデータの特徴のタイプ、及びこれら特徴をいかに表現するか、及び特徴の間でいかに比較するか。
【０００５】
形状分析研究における共通の問題は、形状記述/マッチング方法の品質をいかに判断するかである。すべての方法が、全ての種類の形状、及び全てのタイプの用途に適している訳ではない。一般に、有用な形状分析スキームは、下記条件を満たすべきである：
・変換(transformations)に対する頑強性−分析の結果は、トランスレーション、回転及びスケーリング、並びに境界シーケンスを定義する際に使用される開始点に対して不変でなければならない；このことは、これら変換が定義によって、オブジェクトの形状を変更しないので、要求される、
・特徴抽出効率−特徴ベクトル(記述子)が、効率的に計算されるべきである、
・特徴マッチング効率−マッチングは典型的に、オンラインで実行される故に、距離メトリックが非常に小さい計算上のコストを要求しなければならない、
・変形(deformations)に対する頑強性−分析の結果は、細分化プロセスによって、又は小さい形状変形により導入された空間ノイズに対して頑強でなければならない、
・人間の判断に対応する−形状類似性/非類似性尺度(similarity/dissimilarity measure)は、人間の判断にできるだけ対応するべきである。
【０００６】
形状を表わす既知の方法は、MPEG-7によって採用された記述子、Zernikeモーメント[A. Khotayazan and Y. H. Hong. Invariant image recognition by zernike moments. IEEE Trans.PAMI, 第12巻:第489〜497頁, 1990年]及びＣＳＳ[Farzin Mokhtarian, Sadegh Abbasi and Josef Kittler. Robust and Efficient Shape Indexing through Curvature Scale Space. British Machine Vision Conference, 1996年]、を含む。Zernikeモーメント形状記述子について、Zernike基本関数が、画像内のオブジェクトの形状を調査するために様々な形状について定義される。次に、固定サイズの画像が、基本関数上に投影され、そして得られた値が形状記述子として使用される。湾曲スケール空間記述子について、オブジェクトの輪郭が抽出され、そして輪郭に沿った湾曲点の変化が、スケールを付された空間(scaled space)において表される。次に、ピーク値に関する位置が、z次元ベクトルとして表される。
【０００７】
Zernikeモーメント及びＣＳＳ記述子は、明らかな有利点、例えば非常に速い特徴マッチング及びコンパクトな表現を有する。不幸にも、コンパクトな形状記述子(すなわち、Zernikeモーメント)の大多数は、形状変形に対して頑強でない。ＣＳＳのような他は頑強である。しかし、そのような記述子のマッチングは、多くの偽陽性を生じる。ＣＳＳ方法の検索精度は、特に少数の凹状又は凸状を有するカーブについて、時々貧弱でありうる。特に、この表現は、様々な凸状カーブを区別することができない。コンパクトな記述子の他の不利点は、それらの抽出が、通常、計算的に高価であることである。それはデータベースを作成するために問題でないけれども(特徴抽出はオフラインで実行される)、これは、バイナリーマスクとして用意される２つの形状の迅速なオンライン比較のためにそれらを使用することを困難に(又は不可能にさえ)する。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
バイナリーマスクとして用意される２つの形状の迅速なマッチングのための計算的に効率的な形状記述／マッチング方法を提供することが本発明の目的である。この方法は、形状変形に対して頑強であり、そして多くの偽陽性リターンを生じないことが本発明の更なる目的である。本発明の技術がオンライン環境において実装されうることがなお更なる目的である。
【課題を解決するための手段】
【０００９】
従って、本発明は、２つの形状の非類似性の尺度を得るための改善された技術を提供する。好ましい実施態様に従い、マルチメディアデータの少なくとも２つのセット間の非類似性尺度を提供するために形状情報を使用して、前記マルチメディアデータの少なくとも２つのセットを比較する方法が提供され、第１のセットが参照セットを形成し、及び第２のセットが前記第１のセットと相対的に比較され、前記方法は、
マルチメディアデータの各セットについて輪郭点の１セットを用意すること、
関連付けられた輪郭点を定義するために、前記第１のセットの輪郭点を前記第２のセットの輪郭点と関連付けること、
前記関連付けられた輪郭点の間の距離を計算すること
のステップを含み、前記関連付けられた輪郭点の間の距離が、マルチメディアデータの前記セット間の非類似性尺度を決定するために使用され、それによって前記セット間の類似の程度の指標を提供する。
【００１０】
望ましくは、マルチメディアデータの各セットのための輪郭点のセットが、マルチメディアデータの各セットの境界をトレースすることによって得られる。
【００１１】
輪郭点の前記セットがダウンサンプリングされて、各セットにおけるほぼ等しい間隔で離れた輪郭点の等しい数を生じうる。
【００１２】
望ましくは、輪郭点の前記セットが、互いに関連付けられる前にトランスレーションされ、そしてスケールサイズを正規化される。
【００１３】
本方法は、輪郭点の各セットについて開始点を確立するステップをさらに含んでよく、前記開始点が、各セットについて全ての輪郭点を定義することによって確立され、その個々の輪郭の計算された重心点からの開始点の距離がそれらの個々の重心からの最も離れた輪郭点のユーザ定義された第１のパーセントＰ１よりも大きい。ユーザが、第１のパーセントＰ１を入力することを可能にされてよい。
【００１４】
望ましくは、開始点が、隣接する態様で確立される。典型的に、隣接する開始点が、輪郭点の総数のユーザ定義されたパーセントＰ２未満を含むグループに分割される。ユーザが、第２のパーセントＰ２を入力することを可能にされてよい。
【００１５】
典型的に、開始点の各グループが、前記重心から最も離れている開始点によって表わされる。
【００１６】
望ましくは、参照開始点が、最大の数の開始点を有する輪郭点のセット上の最も離れた開始点又は最大の初期領域として得られ、及び比較されるべき前記セット上の各開始点について、比較されるべき前記セットが、その開始点を前記参照開始点と整列させるために回転される。
【００１７】
望ましくは、関連付けられた輪郭点が、輪郭点の前記セットの夫々に制御点を与えること、次に各セットの前記輪郭に沿って逐次的に前記制御点を移動することによって互いに関連付けられ、及び前記輪郭についての前記制御点の移動が、各セットからの輪郭点を互いに関連付けるために使用される。
【００１８】
好ましくは、各セットについての前記制御点の前記移動が、各セットの整列された開始点で開始される。
【００１９】
典型的に、前記輪郭についての前記制御点の移動の各ステップで、２つの制御点の間の距離、第１セット上の制御点と第２セット上の次の輪郭点との間の距離、及び第２セット上の制御点と第１セット上の次の輪郭点との間の距離が計算され、これら計算された距離の最小値を有する輪郭点が互いに関連付けられる。
【００２０】
通常、前記制御点が前記輪郭点の全てに関して移動するまで、前記輪郭点が割り当てられる。
【００２１】
各セットのスケールサイズを正規化された周線の尺度を得、前記周線の最小を決定し、そして関連付けられた輪郭点間の距離の平均及び標準偏差をさらに決定することによって、前記非類似性尺度が決定されてよい。
【００２２】
典型的に、前記非類似性尺度が、下記式
2006523345.tif 000003
（ここで、Ｄ（Ａ，Ｂ）はセットＡとセットＢとの間の非類似性であり、
ｃは、値の便利な範囲へと前記非類似性の値を再スケールするユーザ定義された定数を示し、
ｃｉｒｍｉｎは、最小の周線であり、
2006523345.tif 000004
｜Ｖ｜は、関連付けられた輪郭点の間の前記距離の標準偏差である）
によって提供される。
【００２３】
好ましい実施態様では、複数の非類似性尺度が計算され、各非類似性尺度が、比較される前記セットの特定の配置に関連付けられ、及び前記セット間の同等性のレベルの全体的表示を提供する最終の非類似性尺度が、計算された全ての非類似性尺度の最低値として与えられる。
【００２４】
本発明のこれらの及び他の特徴は、下記図面に関連していま記載されるだろう。
【発明を実施するための最良の形態】
【００２５】
本発明の幾つかの実施態様が、添付の図面に関して以下に記載される。
【００２６】
本発明に従い、形状情報を使用してマルチメディアデータの少なくとも２つのセットを比較して、非類似性程度を提供する方法が提供される。本発明内では、特徴をいかに表すかの概念が形状記述として考えられてよい。一方、特徴の比較は、形状マッチングとして考えられてよい。非類似性程度又は尺度は、データの第１セットと前記第１セットに対して試験される第２セットとの間の類似性の指標を提供する。マルチメディアデータの該セットは、典型的にバイナリー画像又は輪郭の形式で提供される。本発明の方法論は、２つの主な段階（特徴抽出（１）及び特徴マッチング（２））において作動可能であるソフトウェアシーケンスにおいて典型的に実装される。図１は、そのような段階を与えるために適応された本発明に従うフローシーケンスを示す。
【００２７】
第１段階では、入力されたバイナリー画像からの形状の境界がトレースされる。抽出された輪郭は、トランスレーションされ及びスケールサイズを正規化され、そして両方の形状について最も可能性ある開始点が見積もられる。
【００２８】
第２段階では、非類似性尺度が、第１段階において抽出された特徴を使用して計算される。両方の形状からの開始点は、対に割り当てられる。開始点の与えられた対のための非類似性尺度を評価する前に、これら点の間の回転が見積もられ、そして該形状のうちの１つが回転される。２つの形状の間の非類似性は、開始点の各対について計算される。最低の全体的非類似性は、２つの形状の間の非類似性程度尺度として得られる。
【００２９】
シーケンスフローは、逐次的動作を形成するように以下に示される一連の個々のステップにさらに分けられうる。
【００３０】
輪郭トレース(ステップ１００)
輪郭トレースステップでは、境界ピクセルの順序づけられたシーケンスが、抽出される。−そのようなセットを抽出するために、輪郭トレースのような技術(輪郭追随(border following)又は境界追随(boundary following)として当業者にまた知られうる)が、入力されたバイナリー画像に適用される。そのようなトレースアルゴリズムの応用は、形状に存在するどんな「穴」も無視する。例えば、図２に関して、「Ａ」（３）のような形状がトレースされるべきである場合、アルゴリズムによってトレースされた輪郭は、「Ａ」（４）の外側の(灰色)ピクセルに類似するだろう。
【００３１】
トレースアルゴリズムを説明するために、ピクセルの８近隣(8-neighborhood)の概念[T. Pavladis, Algorithms for Graphics and Image Processing, Computer Science Press, Rockville, Maryland, 1982年]が、最初に定義される必要がある。図３に示されるように、ピクセルＣ（６）の８近隣（５）が、角頂又は辺をそれらピクセルと共有するピクセルＣ１、Ｃ２、Ｃ３、Ｃ４、Ｃ５、Ｃ６、Ｃ７及びＣ８と名付けられた８個のピクセルのセットである。
【００３２】
トレースアルゴリズムが、図４に示されるように動作する：ディジタル形状(黒いピクセルのバックグラウンド上の白いピクセルのグループ)が与えらると、１つの白いピクセルが、開始輪郭ピクセル（６）として配置され且つ宣言される。開始ピクセルを配置することは、多くの様式で実行されうる。輪郭が時計回りの方向でトレースされるという仮定を使用して、開始ピクセルは、左の隣接したピクセルが白くないという制限を満足しなければならない。いまや、その座標が格納され、そして開始ピクセルが現在の輪郭ピクセルとしてセットされる。
【００３３】
現在の輪郭ピクセルから、探索が、その近隣において次の輪郭ピクセルのために実行される。この探索を実行するために、現在の方向（８）は非常に重要である。それは、前の輪郭ピクセルを現在の輪郭ピクセルと結ぶ線として定義されうる。該現在の方向が、現在のピクセル隣接におけるどのピクセルから次の輪郭ピクセルの探索を開始するべきであるかを決定するために使用される。現在の方向が現在のピクセル近隣探索の間に変わらないことに留意すべきである。次の輪郭ピクセルが現在の輪郭ピクセルになる時(１つのステップが輪郭において進む)に限り、それは変化する。トレースが開始する時、現在のピクセルはまた、開始ピクセルである。この場合、現在の方向は、開始ピクセルをその上のピクセル（７）と結ぶ方向として定義される。この方向は、開始ピクセルを選択する際になされた制限の故に採用されうる。
【００３４】
現在の輪郭ピクセル及び前の輪郭ピクセルが、角頂(これは、現在の方向から直接的に決定されうる)を単に共有する場合、探索は、現在の方向の左９０度に位置するピクセル（９）から開始する。より悪い場合では、６個の影を付したピクセル（１０）がチェックされなければならない。示された例において、探索は、第４のピクセル（１１）で終了する。
【００３５】
現在の輪郭ピクセル及び前の輪郭ピクセルが辺を共有するなら、探索は、現在の方向の左４５度に位置するピクセル（１２）から開始する。現在の輪郭ピクセルの左側のピクセルがチェックされる必要はない。なぜならば、前の輪郭ピクセル近隣が探索されたとき、それは既にチェックされたからである。例が、図４(ｄ)に示される。今度は、より悪い場合では、現在の輪郭ピクセル近隣の７個の影を付したピクセル（１３）が検査されなければならない。例において、探索は、第２のピクセル（１４）で終了する。
【００３６】
トレースされた輪郭からの次の白いピクセルが見つけられるとき、アルゴリズムはこのピクセルへと移動して、それを現在の輪郭ピクセルにする。その座標は格納され、現在の方向が更新され、そしてその近隣が上に説明されたように検査される。この手続きは、開始ピクセルが再び訪れられるまで続く。
【００３７】
提案されたトレースアルゴリズムは、容易に且つ効率的に実装されうる。モジュラス８操作又はルックアップテーブルが、現在のピクセル近隣のどのピクセルがチェックされるべきか及びどの順序でかを決定するために使用されうる。上記は好ましいトレースアルゴリズムであるが、任意の適切な代替がまた本発明の文脈において使用されうることが理解されるだろう。全体の輪郭並びにその個別のセグメントの長さが、形状分析アルゴリズムの次の段階で知られなければならない故に、輪郭トレース中に輪郭ピクセルの間の距離を決定し且つ格納することは便利である。それは、フリーマンコード(Freeman code)又はチェーンコード(chain code)として文献(参照：Freeman H. Computer processing of Line-Drawing Images, Computing Surveys  第6巻, 第1号, 1974年3月)において知られた概念を使用して非常に効率的な様式において実行されうる。
【００３８】
チェーンコードは、一連のピクセルを接続する線セグメントの方向の観点で境界を記載する。表示は、４−又は８−接続性に基づきうる。各セグメントの方向が、図３に示される番号付けスキームを使用してコードされる。従って、輪郭ピクセルの座標を有するベクトルが輪郭トレースの後に格納されるだけでなく、ピクセル間の方向のベクトルも格納されるだろう。
【００３９】
次に、抽出された輪郭を使用して、該技術は、比較されるべき２つの画像の夫々に正規化ステップを適用する（ステップ１０５）。この正規化ステップは典型的に、２つのサブステップを含む：第１に、抽出された輪郭がダウンサンプリングされ、次にダウンサンプリングされた輪郭が、トランスレーションされ且つ互いに関して正規化される。
【００４０】
輪郭ダウンサンプリング(ステップ１０５ｂ)
前の段階から、データの各セットが輪郭ピクセルの順序づけられたシーケンス(ｘ，ｙ)としていま用意され又は示されること及びチェーンコードがまた利用可能であることが理解されるだろう。この段階の目的は、輪郭ピクセルのセットから輪郭点のベクトルを抽出することであり、それはカーブに沿って等しく分布されるだろう。
【００４１】
本発明の形状分析スキームにおいて使用される類似性程度尺度が、形状カーブに沿った対応する形状制御点の間の距離に基づく故に、この段階が要求される。これから発生して、両方の比較された形状についての輪郭点のほぼ等しい数が要求される（図１を参照）。形状における輪郭ピクセルの数がスケール変化により著しく変わりうることは明らかであろう。もう一つの問題は、近接の輪郭ピクセルの間の垂直の及び水平のセグメントが夫々単位長さを有し、一方対角線のセグメントがルート２で寄与するという事実に関連する。この事実の故に、輪郭の異なる部分における輪郭ピクセルの主観的な数がまた、回転後に変化する。制御点を導入するための最後の理由は、輪郭を表す点の数に依存するアルゴリズムの計算上のコストである。典型的なＣＩＦシーケンス(352×288ピクセル)からえられた領域の輪郭のうちの幾つかは、1000よりも多いピクセルを有しうる。実験は、ほとんどの場合、最も重要な輪郭特徴を保存するために100個の点が輪郭を表わすのに十分であることを示す。
【００４２】
少数の角頂又はセグメントを使用して、輪郭カーブを近似するための多くの発見的アプローチがある。一般的なアプローチは、選択された近似エラーが達成されるまで、輪郭セグメントを分割し又は合併することである。提案されたダウンサンプリングアルゴリズムにおいて、主な目的は、輪郭点が輪郭に沿ってほとんど等しく分布されるだろう様式で（すなわち、輪郭ピクセルの全体のセットから）輪郭点を抽出することであり、ほぼ等しい距離であるピクセルのサブセットが選択されるだろう。これは、輪郭ピクセルシーケンスの１回の走査中に容易に実行されうる。
【００４３】
形状についての輪郭点の最大数は、輪郭ピクセルのその数によって決定される。両方の形状が同数の輪郭点を有しなければならない故に、両方の形状についての輪郭点の最大数は、輪郭ピクセルのより少ない数を有する形状における輪郭ピクセルの数によって定義される。形状記述子がデータベース内に格納される場合、輪郭点の数は、このデータベースにおける全ての形状のために固定されるべきである。
【００４４】
本発明の技術によれば、輪郭点の選択は、非常に単純で且つ効率的な様式において提供される。アイデアは、輪郭点のためのピクセルを選択しながら輪郭に沿って移動することである。輪郭に沿ったピクセルの位置は、チェーンコードから効率的に計算されうる。
【００４５】
図５（ｂ）に示されているように、輪郭点の「理想的な」位置への輪郭長さにおいて最も接近した位置を有するピクセルのみが選択される。選択されたピクセルの座標は、輪郭点ベクトル（ｘ座標のための一つ及びｙ座標のための一つ）にコピーされる。
【００４６】
この点から始めて、形状の輪郭は、輪郭点（角頂）の順序づけられたシーケンス(ｘ(ｓ))，ｙ(ｓ))によって表される。ここで、ｓは、輪郭における位置を示し、且つ０〜Ｎの整数値を有することができ、ここでＮは、形状を示すために使用される輪郭点の総数を示す。
【００４７】
トランスレーション及びスケール正規化（ステップ１０５ｃ）
明らかに、画像中の一つの位置から他への領域の移動及び／又はそのサイズの変更は、形状分析に影響してはならない。形状の中心がトランスレーション、回転及びスケーリングに対して不変である故に、本発明は、トランスレーション問題を解決する方法の一部として形状の重心の位置を利用する。示されたアプローチでは、オブジェクトカーブの重心が座標（０，０）にトランスレーションされ、これは該オブジェクトカーブトランスレーションを不変にする。スケーリング不変性は、形状エリアによって形状カーブを正規化することによって得られうる(例えば、Dinggang Shen, Horace H. S., Discriminative wavelet shape descriptors for recognition of 2-D patterns, Pattern Recognition 第32巻, 第151〜156頁, 1999年を参照)。このトランスレーション及びスケーリング不変性は、次のサブセクションに記載されるようなレギュラーモーメントを使用して達成されうる。
【００４８】
モーメントの計算
レギュラーモーメントｍｐｑの定義は、
［式１］
2006523345.tif 000005
である。
【００４９】
バイナリー画像について、上記式は以下の離散式形式で表されうる。
［式２］
2006523345.tif 000006
【００５０】
示されたスキームでは、形状正規化のために必要とされる全ての低次モーメントが、境界輪郭点から導き出される。このアプローチは、上記の定義式からモーメントを計算することに比較してはるかに速い。境界からモーメントを計算するために、単純なチェーンコードから形状のエリアを得るための、"Herbert Freeman. Computer processing of Line-Drawing Images, Computing Surveys, 第6巻, 第1号, 1974年3月"に示されるものと類似の方法が使用されうる。ここに、この方法は、モーメントｍ０１及びｍ１０のために拡張される。
【００５１】
図６（ａ）に関して、アルゴリズムは、一つの輪郭点から他の輪郭点に輪郭のまわりに時計回りの方向（１５）で移動する。モーメントは、現在及び前の輪郭点並びにｘ（又はｙ）軸から生成された台形の適切なモーメントの合計として計算される[モーメントｍ’０１について、台形は、現在の、前の及びｙ軸から作成される]。そのような台形（１７）の例が、ｍ’００及びｍ’０１のみについて図６（ｂ）に示される。台形の角頂は（ｘ（ｃ），ｙ（ｃ））、（ｘ（ｐ），ｙ（ｐ））、（ｘ（ｐ），ｙ（０））及び（ｘ（ｃ），０）であり、ここでｃ及びｐは、現在及び前の輪郭点を夫々示す。
【００５２】
式２から、台形の角頂の関数として台形の低次モーメント（ｍ’００，ｍ’１０，ｍ’０１)の式が、容易に得られうる：
［式３］
2006523345.tif 000007
［式４］
2006523345.tif 000008
［式５］
2006523345.tif 000009
【００５３】
ｍ’００及びｍ’１０は、形状の上の境界からの角頂について負の値（減算コンポーネント（１８））及び底の境界からの角頂について正の値（加算コンポーネント１９）を有することは注目せよ。同様に、ｍ’０１は、形状の左部について負の値及び右部について正の値を有する（図に示されていない）。
【００５４】
全体の形状の低次モーメントは、全ての台形のモーメントの合計として以下のように計算されうる：
［式６］
2006523345.tif 000010
ここで、ｖは、形状の全ての角頂（輪郭点）のセットを示す。
【００５５】
形状の全ての必要なモーメント（ｍ’００，ｍ’１０，ｍ’０１)の計算は、角頂の数に線形の時間をとる。式３、４及び５は多くの共通のコンポーネント（合計）を有する故に、それらは非常に効率的な様式で実装されうる。
【００５６】
正規化
低次モーメントを使用して、形状の中心の座標は、以下のように計算されうる：
［式７］
2006523345.tif 000011
ここで、ｘｃ及びｙｃは、形状の重心の座標である。
【００５７】
スケーリング不変性は、中心モーメントｍ００によって形状角頂の座標を再スケールすることによって得られうる。予想されるサイズと比較して、現在のオブジェクトサイズの倍率は、
［式８］
2006523345.tif 000012
であり、ここで、ＡＲＥＡは、選択された定数である（全ての比較された形状について同じ）。
【００５８】
最後に、トランスレーション、及びスケールを正規化された形状は、下記の変換に従い角頂座標を変更することによって得られうる：
［式９］
2006523345.tif 000013
【００５９】
形状のトランスレーション及びサイズ正規化の例が、図７に示される。MPEG-7テストセットからのオリジナルの形状が図７（ａ）に示され、一方図７（ｂ）は同じ形状の再スケールされ（５倍小さい）かつトランスレーションされたバージョンを示す。最後に、図７（ｃ）は、上記輪郭の抽出された角頂を示し、及び図７（ｄ）は、トランスレーション及びスケール正規化後の角頂を示す。
【００６０】
この記載の残りについて、我々は（ｘ（ｓ），ｙ（ｓ））のシーケンスによりトランスレーション及びスケール正規化された輪郭を示す。
【００６１】
開始点の抽出（ステップ１１０）
オブジェクト領域の回転、又は領域の境界のトレースが開始した点を変更することが、形状分析に影響してはならないことが理解されるだろう。この問題への一つの可能な解決策は、輪郭点の全ての対について類似性／非類似性尺度を評価することでありうる。
【００６２】
示されたアプローチでは、最も可能性ある開始点のセットが、探索を促進するために形状から選択される。選択されたセットは主として形状に依存し、そして全体のセットからの開始点の幾つかだけがその変形によって影響されるだろうことが予想される。選択された開始点の数は、２つのパラメーターによって制御されうる。ユーザが最適のマッチのための探索のスピード及び正確さを選択することを可能にするために、開始点の１より多いセットが、１つの形状についてデータベース中に格納されうる。
【００６３】
本発明の好ましい実装に従い、開始点を選択するための以下のスキームが使用される：
１．重心から最も離れた輪郭点を見つける(重心からの距離ｄｍａｘ）、
２．閾値距離Ｔｄが定義される。重心からＴｄと等しい又はＴｄよりもより離れている輪郭点が、潜在的な開始点としてマーク付けされる。閾値距離Ｔｄは、最大の距離の断片として表されうる：
［式１０］
2006523345.tif 000014
ここで、パラメーターｐｄは、範囲〈０,１〉における実数である。
３．マーク付けされた輪郭点の各連続的なグループについて、一つが、輪郭のこの部分のための開始点として選択される。実験は、グループにおいて最も離れた輪郭点がよい選択であることを示す。あまりにも多い輪郭点がちょうど１つの開始点によって表されるだろう状況を回避するために、マーク付けされた点の最大の数Ｔｎが導入され、それは一つの開始点によって表されうる：
［式１１］
2006523345.tif 000015
ここで、Ｎは、形状を示す全ての輪郭点の数を示し、及びｐｎは、範囲〈０,１〉内の数を示す。
もしグループがＴｎよりも多くの点を有する場合、それは、Ｔｎと等しい又はＴｎよりも少ない点を有するより小さいグループに分割される。次に、各グループは、１つの開始点（重心から最も離れているもの）によって表される。
【００６４】
２つの形状の間の最適な回転のための検索の強度は、ｐｄ及びｐｎによって変化しうる。それは、パラメーターｐｄ及びｐｎを変更して、最適な回転整列のために速い、通常の又は広範囲な探索を実行することによって可能である。探索は後のステップで実行されるけれども、探索の強度は、いかに多くの開始点がこの段階で選択されるかに依存する。従って、それは、工程の全体的効率に対する重要な貢献因子でありうる。しかしながら、ほとんどの場合、良い結果がｐｄ＝０．７及びｐｎ＝１／２０として値を選択することによって達成されうる。それらは、長い形状のために約２〜４個の開始点及び円い形状のために約２０個の開始点を生じる。抽出された開始点セットの例が、図９に示される。
【００６５】
マッチング（ステップ１２０）
この段階において、２つの形状の間の最良の回転整列のための探索が実行される。開始点の抽出されたセットが、探索空間を狭めるために使用される。各チェックされた回転について、類似性／非類似性尺度が計算される。この探索中に得られた最低の非類似性尺度が、２つの形状の間の最終的な非類似程度ととられる。開始点の与えられたセットについて非類似性尺度を計算することの詳細な記載が、次のサブセクションで説明される。
【００６６】
示された技術では、好ましい探索が以下のように作動する：
１．類似性／非類似性尺度が評価されるだろう両方の形状から開始点対のセットが生成される。現在の実装では、該対が、次の様式で結合される：（ｓｐｒｅｆ，ｓｐ１），（ｓｐｒｅｆ，ｓｐ２），・・・（ｓｐｒｅｆ，ｓｐｋ）、ここで、ｓｐｒｅｆは、参照として選択された形状からの最も離れた開始点であり、及びｋは、回転されたものとして選択された形状からの開始点の総数である。通常、回転されるものであるべき開始点のより少ない数を有する形状及び参照形状であるべきより多い開始点を有する形状を選択することがよい（この決定は用途指向的である）。両方の形状が同じ数の開始点を有する場合、より小さな初期エリアを有する形状(正規化前)が、回転、及び参照形状としてより大きなエリアを有するそれのために選択される。
２．開始点の各対についての回転（図８の例を参照）が補償され、そして非類似性が評価される。最低の非類似性尺度を有する対が選択される（それを(ｓｐｒｅｆ，ｓｐｘ）とする）。
３．ｓｐｘの近隣からの開始点を有するｓｐｒｅｆの対のための非類似性が、ステップ２にあるように評価される。ｓｐｘ近隣が探索され、及び対（．．．（ｓｐｒｅｆ，ｓｐｘ−２），（ｓｐｒｅｆ，ｓｐｘ−１），（ｓｐｒｅｆ，ｓｐｘ＋１），（ｓｐｒｅｆ，ｓｐｘ＋２）．．．）についての非類似性尺度が計算される。非類似性値が増加し始めるまで、探索が両方向において続けられる。
４．すべてのチェックされた開始点対から得られた最低の非類似性尺度が、形状の間の最終の非類似性尺度ととらえられる。
【００６７】
開始点の間の回転が、図８に示されたように補償されうる。両方の形状からの開始点の間の主観的な回転が、これら開始点とこれら形状の整列された重心との間の角αとして推定されうる。回転は、形状のうちの一つを約角度α回転することによって補償される。回転された形状についての輪郭点の新しい座標が、次の式から計算されうる：
［式１２］
2006523345.tif 000016
［式１３］
2006523345.tif 000017
【００６８】
類似性／非類似性尺度
示された類似性/非類似性メトリックは、２つの形状の輪郭点の間の距離に基づく。２つの形状の間の類似性/非類似性を計算する前に、両方の形状からの輪郭点の間の対応問題が、最初に解決されなければならない。輪郭点の単純な割り当てが、それらの索引付け（開始点から開始する）に基づくことができ、しかしそれは形状変形（特に、輪郭ノイズ）に対して頑強でない。そのような単純な割り当ての例が、図１０に示される。図１０（ａ）及び（ｂ）は、非類似性の程度が計算されなければならない形状を示す。図１０（ｂ）に示される形の角頂が、細分化ノイズによって悪くされるという点を除いて、両方の形状は同一である。図１０（ｃ）は、単純な輪郭点割り当てを示す。この例から、輪郭点の上記割り当てが失敗することは明らかである。示された方法において、この問題に対する半最適な解決策が提案される。それは、形状に沿って移動する２つの制御点を利用する。それは変形及びノイズ頑強であり、及び複雑性はまだＯ（Ｎ）である。
【００６９】
2006523345.tif 000018
【００７０】
このようにして、制御点が、できるだけ緊密に輪郭に沿って一緒に移動する。通常、それらは１ステップの間に一つの位置だけ前進するが、それらのうちの一つが、それがそれらの間でより小さな距離を生成する場合、２つの位置だけを移動しうる。言いかえれば、輪郭のいくつかの部分では、形状Ａからの制御点がより速く移動することができ、一方、他の部分について、形状Ｂからの制御点がより速く移動することができる。この場合、より速い手段が、１ステップ当たり、輪郭点シーケンスにおける２つの位置だけ移動する。そのような様式において、いくつか輪郭点がスキップされることに留意すべきである。１つの輪郭点をスキップする間のステップの例が、図１１（ｂ）に示される。
2006523345.tif 000019
【００７１】
図１０（ｄ）は、図１０（ａ）及び（ｂ）で示される形状における輪郭点が、動く制御点によって割り当てられる様式を示す。（図１０（ｃ）と比較して）改良が、点割り当てを示す線の減少された複雑性（特に、形状の部分{2}及び{4}について）によって可視化される。
【００７２】
このように割り当てられた輪郭点の間の距離は、２つの形状の間の類似性/非類似性を計算するために使用される。
【００７３】
２つの輪郭に沿って同時に走査する場合、両方の形状からの輪郭点の間の測定された距離は比較的小さくなければならない。その上、それらはカーブに沿って変化してはならない。形状が類似する場合、これら距離の標準偏差は、小さく、そして形状の間の非類似性の程度に強く依存しなければならない。提案されたメトリックは、この事実をうまく利用する。それは両方に基づく：割り当てられた輪郭点の間の幾何学的な距離、及び両方の輪郭に沿ったそれら変化。
【００７４】
輪郭の間の平均距離は、下記式から計算されうる：
［式１４］
2006523345.tif 000020
2006523345.tif 000021
【００７５】
距離の標準偏差は、下記式から計算されうる：
［式１５］
2006523345.tif 000022
【００７６】
提案された非類似性程度は、：
［式１６］
2006523345.tif 000023
のように定義され、ここで、
・ｃは、非類似性程度メトリックの値を値の都合の良い範囲に再スケールする(アルゴリズムの較正)選択された定数を示す；
・ｃｉｒｍｉｎは、両方の正規化された形状の周囲の最小周囲である。
ｃｉｒｍｉｎは、２つの形状の複雑さに依存して、非類似性メトリックを該２つの形状の非類似性のヒト認識に調整する。小さな相違がそれほど重要でない２つのより複雑な形状の間の相違と対照的に、２つの簡単な形状の間の小さな相違でさえ重要であるとしてヒトは知覚することが現在の発明者によって観察された。形状がサイズを正規化されると仮定すると、周囲は、形状の複雑性の尺度として使用されうる。
【００７７】
そのような非類似性程度尺度は、非常に同様の形状についてゼロに近い値、及び有意に異なる形状について１以上の値を与える。これに基づき、類似性程度尺度パーセントが、
［式１７］
2006523345.tif 000024
のように定義されうる。
【００７８】
それは、0％〜10％の値を与える（有意に異なる形状について0％に近い値、及び類似の形状について100％に近い値）。
【００７９】
データの２セットの間の非類似性尺度を提供するための方法が記載されたことが理解されるだろう。本発明に従うそのような方法は、データの第１のセット又は参照セットと第１のセットに対して比較される第２のセットとの間のリアルタイム比較を可能にする。照会画像に対して類似の形状を有する画像についてのデータベースを探索するために使用されるとき、そのような技術の使用が検索の性能に有利である。示された方法は、MPEG7コア実験CE−形状-1(部分Ｂ)におけるすべての既存の形状マッチングアルゴリズムより優れている。既存の方法と比較して、提案された形状分析技術は、バイナリー画像から直接的に得られた形状の間のオンライン類似性計算について非常に速い。
【００８０】
本発明に従う技術を実装することによって、バイナリー形状の画像の間の多くの比較を要求するアプリケーションを効率的に開発することが可能である。一つの例が、高度な画像データベースである。画像の間の類似性を決定するとき、多くの特徴、例えば色及びテクスチャが使用されうる。しかしながら、他の重要な特徴は、場面(scene)に存在するオブジェクトの形状である。そのため、このアプローチは、ブラウズ及び探索及び検索のために画像の大きなアーカイブを索引付けするときに重要なツールである。その上、その効率により、それはビデオクリップに成功裡に適用されることができ、及びビデオアーカイブからの形状ベースの検索において用途を見出す。ビデオ管理ツールの現在の制作者は典型的に、ビデオの一時的なセグメント及び抽出されたキーフレームに基づいた使用特徴だけを使用する。しかしながら、これらシステムの次世代は、より精巧な特徴を要求するだろう。そして、提案されたアプローチは、このための理想的な候補である。同様の技術が既に使用されている別の例のアプリケーションは、商標ロゴデータベースである。新しい商標又はロゴがデザインされるとき、その形状特徴が、既存の商標又はロゴにあまりにも似ているかいないかを決定するために使用されうる。本発明によって提供されるような技術を使用することは、尺度又は非類似性値が経験的な比較を可能にするように計算されることを可能にする。
【００８１】
本発明は、それらの好ましい実施態様に関して記載され、及び以上に概略されたステップのいずれかのシーケンスは、本発明の技術を示しており、及び添付された請求項の観点において必要であるとみなされる以外は、それらのシーケンスのステップのいずれか一つのセットに本出願を制限することは意図されない。
【図面の簡単な説明】
【００８２】
【図１】本発明に従う形状分析アルゴリズムの主ステップを示す図である。
【図２】本発明の観点に従い実装された輪郭トレースの例を示す図である。
【図３】本発明の方法ステップにおいて利用される８近隣を示す図である。
【図４】本発明において使用されるような輪郭トレースステップを記載する図である。
【図５】輪郭点が本発明に従いどのように選択されるかを示す図である。
【図６】本発明に従い輪郭のモーメントを計算するために使用される領域を示す図である。
【図７】MPEG-7テスト画像を使用して、トランスレーション及びサイズ正規化の例を与える図である。
【図８】MPEG-7テスト画像を使用して、回転補償の例を与える図である。
【図９】MPEG-7テスト画像を使用して、開始点抽出の例を与える図である。
【図１０】２つの形状の輪郭点を割り当てること（単純な割り当て、及び本発明による）の例を与える図である。
【図１１】本発明に従う輪郭点割り当てのサンプルステップを示す図である。
【図１】
2006523345.tif 000027
【図２】
2006523345.tif 000028
【図３】
2006523345.tif 000029
【図４】
2006523345.tif 000030
【図５】
2006523345.tif 000031
【図６】
2006523345.tif 000032
【図７】
2006523345.tif 000033
【図８】
2006523345.tif 000034
【図９】
2006523345.tif 000035
【図１０】
2006523345.tif 000036
【図１１】
2006523345.tif 000037
【国際調査報告】
2006523345.tif 000038
2006523345.tif 000039
2006523345.tif 000040
2006523345.tif 000041