(57)【特許請求の範囲】
【請求項１】
フレーム内符号化フレームおよびフレーム間符号化フレームのシーケンスに対応する圧縮ビットストリームで表されるフレームを識別する方法であって、前記圧縮ビットストリームは、関連するフレーム間符号化フレームから最も密接にマッチするフレーム内符号化フレームへの変位を表す、各フレーム間符号化フレームに関連する各ビットを含み、
第１のフレーム間符号化フレームに関連する、前記圧縮ビットストリーム内のビットに基づいて、該第１のフレーム間符号化フレームの変位の大きさを決定するステップと、
該決定された変位の大きさに基づいて、前記第１のフレーム間符号化フレームを識別するステップとを含み、
前記第１のフレーム間符号化フレームは、複数のマクロブロックを含み、
該マクロブロックはそれぞれ、関連するマクロブロックから、前記最も密接にマッチするフレーム内符号化フレームへの変位の大きさを表す、前記第１のフレーム間符号化フレームに関連するビットの各部分に関連し、
前記第１のフレーム間符号化フレームの前記変位の大きさは、前記第１のフレーム間符号化フレーム内の複数のマクロブロックそれぞれに関連する、前記圧縮ビットストリーム内のビットの前記各部分それぞれに基づいて、マクロブロック当たりの変位の大きさ平均を計算することにより、決定され、
前記複数のマクロブロックそれぞれについて、前記マクロブロックに関連する前記変位の大きさが閾値未満であるか否かを決定するステップと、
前記閾値未満の前記変位の大きさを有する前記複数のマクロブロックについて、ランレングスに対応する値を計算するステップと、をさらに含み、
前記第１のフレーム間符号化フレームはさらに、前記計算された値に基づいて識別される、
フレームを識別する方法。
【請求項２】
前記圧縮ビットストリームの符号化に使用した少なくとも１つのパラメータに基づいて、前記計算された変位の大きさの平均と、前記計算された値とを正規化するステップをさらに含む、請求項１記載の方法。
【請求項３】
前記少なくとも１つのパラメータは、フレームフォーマット、フレームサイズ、フレーム速度、およびビットレートのうちの少なくとも１つである、請求項２記載の方法。
【請求項４】
前記閾値は、前記計算された平均変位量である、請求項１記載の方法。
【請求項５】
前記計算された値は、前記閾値未満の前記変位量を有する複数のマクロブロックのランレングスに対応する複数の値のうちの１つであり、前記方法はさらに、
前記各ランレングスを、それぞれが異なるランレングス範囲に対応する複数のカテゴリのうちの１つにそれぞれ分類するステップを含み、
前記複数の値はそれぞれ、前記複数のカテゴリのそれぞれ１つに分類されたランレングスに対応し、前記第１のフレーム間符号化フレームはさらに、該複数の値に基づいて識別される、請求項１記載の方法。
【請求項６】
前記計算された平均変位量と前記計算された値とを組み合わせるステップをさらに含み、
前記第１のフレーム間符号化フレームは、該平均変位量と前記値とを組み合わせたものに基づいて識別される、請求項１記載の方法。
【請求項７】
フレーム内符号化フレームおよびフレーム間符号化フレームのシーケンスに対応する圧縮ビットストリームで表されるフレームを識別する方法であって、前記圧縮ビットストリームは、関連するフレーム間符号化フレームから最も密接にマッチするフレーム内符号化フレームへの変位を表す、各フレーム間符号化フレームに関連する各ビットを含み、
第１のフレーム間符号化フレームに関連する、前記圧縮ビットストリーム内のビットに基づいて、該第１のフレーム間符号化フレームの変位の大きさを決定するステップと、
該決定された変位の大きさに基づいて、前記第１のフレーム間符号化フレームを識別するステップとを含み、
前記ビデオシーケンスは、隣接したフレーム間符号化フレームの各シリーズから形成されるショットを含み、該ショットの第１のものは、前記第１のフレーム間符号化フレームを含む隣接したフレーム間符号化フレームの第１のシリーズから形成され、前記フレーム間符号化フレームはそれぞれ複数のマクロブロックを含み、該マクロブロックはそれぞれ、前記マクロブロックから最も密接にマッチした前記フレーム内符号化フレームのマクロブロックまでの変位量を表す、そのフレーム間符号化フレームに関連する前記ビットの各部分に関連し、前記方法は、
前記フレーム間符号化フレームの複数のマクロブロックに関連したビットの各部分に基づいて、前記第１のショットを形成する前記近接するフレーム間符号化フレームのそれぞれに対するマクロブロック当たりの平均変位量を計算するステップと、
前記第１のショットの前記隣接したフレーム間符号化フレームそれぞれのマクロブロック当たりの前記計算された平均変位量に基づいて、前記第１のショットのフレーム当たりの平均変位量を計算するステップと、
前記第１のショットを形成する前記隣接したフレーム間符号化フレームそれぞれのマクロブロック当たりの前記計算された平均変位量と、前記第１のショットのフレーム当たりの前記計算された平均変位量と比較するステップと、
該比較に基づいて、前記第１のフレーム間符号化フレームのマクロブロック当たりの前記計算された平均変位量を、前記ショットの代表として選択するステップと、を含み、
前記決定された変位量は、前記第１のフレーム間符号化フレームのマクロブロック当たりの前記選択された平均変位量である、フレームを識別する方法。
【請求項８】
フレーム内符号化フレームおよびフレーム間符号化フレームのシーケンスに対応する圧縮ビットストリームで表されるフレームを識別する方法であって、前記圧縮ビットストリームは、関連するフレーム間符号化フレームから最も密接にマッチするフレーム内符号化フレームへの変位を表す、各フレーム間符号化フレームに関連する各ビットを含み、
第１のフレーム間符号化フレームに関連する、前記圧縮ビットストリーム内のビットに基づいて、該第１のフレーム間符号化フレームの変位の大きさを決定するステップと、
該決定された変位の大きさに基づいて、前記第１のフレーム間符号化フレームを識別するステップとを含み、
前記第１のフレーム間符号化フレームの幅および高さに基づいて、前記第１のフレーム間符号化フレームの前記決定された変位量を正規化するステップをさらに含む、フレームを識別する方法。
【請求項９】
フレーム内符号化フレームおよびフレーム間符号化フレームを有するビデオシーケンスに対応する圧縮ビデオビットストリームにおけるフレームを識別する方法であって、前記フレーム間符号化フレームはそれぞれ複数のマクロブロックを有し、前記圧縮ビットストリームは、（ｉ）最も密接にマッチする前記フレーム内符号化フレームへの前記関連するフレーム間符号化フレームの変位量と、（ｉｉ）最も密接にマッチする前記フレーム内符号化フレームへの変位量が閾値未満である前記関連するフレーム間符号化フレームの複数のマクロブロックのランレングスの数と、を表す、前記フレーム間符号化フレームに関連するビットを含み、
第１のフレーム間符号化フレームの変位量、および第２のフレーム間符号化フレームの変位量に基づいて、第１および第２のフレーム間符号化フレームを識別するステップと、
前記第１のフレーム間符号化フレームに関連するマクロブロックのランレングスの数、および前記第２のフレーム間符号化フレームに関連するマクロブロックのランレングスの数に基づいて、前記識別された第１および第２のフレーム間符号化フレームのうちの一方だけを識別するステップと
を含むフレームを識別する方法。
【請求項１０】
前記フレーム間符号化フレームそれぞれに関連するランレングスの数は、前記最も密接にマッチングするフレーム内符号化フレームへの変位量が前記閾値未満である前記フレーム間符号化フレームに関連するマクロブロックの多数のランレングスのうちの１つであり、
前記多数のランレングスはそれぞれ、多数のランレングス範囲のうちの１つに関連付けられ、前記１つのフレーム間符号化フレームは、前記多数のランレングス範囲それぞれにおける前記フレーム間符号化フレームに関連するマクロブロックのランレングスの数に基づいて識別される、請求項９記載の方法。
【請求項１１】
前記第１のフレーム間符号化フレームに関連するマクロブロックのランレングスの数の発生頻度と、前記第２のフレーム間符号化フレームに関連するマクロブロックのランレングスの数の発生頻度とを比較するステップをさらに含み、
前記１つのフレーム間符号化フレームは、前記第１のフレーム間符号化フレームに関連する発生頻度と、前記第２のフレーム間符号化フレームに関連する発生頻度との差に基づいて、識別される、請求項９記載の方法。
【請求項１２】
フレーム内符号化フレームおよびフレーム間符号化フレームのシーケンスに対応する圧縮ビットストリームを格納するよう構成されたメモリであって、前記圧縮ビットストリームは、前記関連するフレーム間符号化フレームから最も密接にマッチする前記フレーム内符号化フレームまでの変位を表す、前記フレーム間符号化フレームそれぞれに関連するビットを含む、メモリと、
第１のフレーム間符号化フレームに関連する圧縮ビットストリームにおけるビットに基づいて、前記第１のフレーム間符号化フレームの変位量を決定し、該決定された変位量に基づいて、前記第１のフレーム間符号化フレームを識別するよう構成されたプロセッサとを備え、
前記第１のフレーム間符号化フレームは、複数のマクロブロックを含み、
該マクロブロックはそれぞれ、前記格納された圧縮ビットストリームにおける第１のフレーム間符号化フレームに関連する前記ビットの各部分に関連し、該ビットの各部分は、前記関連するマクロブロックから前記最も密接にマッチングするフレーム内符号化フレームまでの変位量を表し、
前記プロセッサはさらに、前記第１のフレーム間符号化フレームの前記複数のマクロブロックに関連する前記変位量に基づいて、マクロブロック当たりの平均変位量を計算するよう構成される、フレームを識別するシステム。
【請求項１３】
前記プロセッサはさらに、前記複数のマクロブロックそれぞれに関連する前記変位量が閾値未満であるか否かを決定し、関連する変位量が前記閾値未満であると決定された前記フレーム間符号化フレームそれぞれの前記複数のマクロブロックのランレングスに対応する値を計算し、前記第１のフレーム間符号化フレームに関連するマクロブロックの前記ランレングスに対応する前記計算された値にさらに基づいて、前記第１のフレーム間符号化フレームを識別するよう構成される、請求項１２記載のシステム。
【請求項１４】
前記プロセッサはさらに、前記ランレングスそれぞれを、異なるランレングスの範囲に対応する、複数のカテゴリのうちの１つに分類し、該複数のカテゴリそれぞれ内の前記フレーム間符号化フレームそれぞれに関連するマクロブロックのランレングスの数を計算するよう構成され、
前記第１のフレーム間符号化フレームに関連するマクロブロックの前記ランレングスに対応する前記計算された値は、前記複数のカテゴリのうちの１つにおける前記第１のフレーム間符号化フレームに関連するマクロブロックのランレングスの前記計算された数である、請求項１３記載のシステム。
【請求項１５】
前記プロセッサはさらに、前記計算された平均変位量と、前記フレーム間符号化フレームのランレングスの前記計算された数とを組み合わせて、該組み合わされた変位量とランレングスの数に基づいて、前記第１のフレーム間符号化フレームを識別するよう構成される、請求項１４記載のシステム。
【請求項１６】
フレーム内符号化フレームおよびフレーム間符号化フレームのシーケンスに対応する圧縮ビットストリームを格納するよう構成されたメモリであって、前記圧縮ビットストリームは、前記関連するフレーム間符号化フレームから最も密接にマッチする前記フレーム内符号化フレームまでの変位を表す、前記フレーム間符号化フレームそれぞれに関連するビットを含む、メモリと、
第１のフレーム間符号化フレームに関連する圧縮ビットストリームにおけるビットに基づいて、前記第１のフレーム間符号化フレームの変位量を決定し、該決定された変位量に基づいて、前記第１のフレーム間符号化フレームを識別するよう構成されたプロセッサとを備え、
前記第１のフレーム間符号化フレームは、複数のマクロブロックを含み、
該マクロブロックはそれぞれ、前記格納された圧縮ビットストリームにおける第１のフレーム間符号化フレームに関連する前記ビットの各部分に関連し、該ビットの各部分は、前記関連するマクロブロックから前記最も密接にマッチングするフレーム内符号化フレームまでの変位量を表し、
前記プロセッサはさらに、前記第１のフレーム間符号化フレームの前記複数のマクロブロックに関連する前記変位量に基づいて、マクロブロック当たりの平均変位量を決定し、前記複数のマクロブロックそれぞれに関連する前記変位量が閾値未満であるか否かを決定し、前記複数のマクロブロックのうち、前記関連する変位量が前記閾値未満であると決定されたもののランレングスに対応する値を計算し、前記計算された値にさらに基づいて、前記第１のフレーム間符号化フレームを識別するよう構成される、フレームを識別するシステム。
【請求項１７】
フレーム内符号化フレームおよびフレーム間符号化フレームのシーケンスに対応する圧縮ビットストリームを格納するよう構成されたメモリであって、前記圧縮ビットストリームは、前記関連するフレーム間符号化フレームから最も密接にマッチする前記フレーム内符号化フレームまでの変位を表す、前記フレーム間符号化フレームそれぞれに関連するビットを含む、メモリと、
第１のフレーム間符号化フレームに関連する圧縮ビットストリームにおけるビットに基づいて、前記第１のフレーム間符号化フレームの変位量を決定し、該決定された変位量に基づいて、前記第１のフレーム間符号化フレームを識別するよう構成されたプロセッサとを備え、
前記シーケンスは、隣接した前記フレーム間符号化フレームの各シリーズから形成されるショットを含み、
第１のショットは、前記第１のフレーム間符号化フレームを含む隣接したフレーム間符号化フレームの第１のシリーズから形成され、
隣接したフレーム間符号化フレームの前記第１のシリーズはそれぞれ、複数のマクロブロックを含み、
前記複数のマクロブロックはそれぞれ、前記格納された圧縮ビットストリームにおける該フレーム間符号化フレームに関連する前記ビットの各部分に関連し、該ビットの各部分は、前記関連するマクロブロックから前記最も密接にマッチングするフレーム内符号化フレームまでの変位量を表し、
前記プロセッサはさらに、前記第１のフレーム間符号化フレームの前記複数のマクロブロックの前記変位量に基づいて、近接するフレーム間符号化フレームの第１のシリーズそれぞれに対するマクロブロック当たりの平均変位量を計算し、前記第１のショットを形成する前記フレーム間符号化フレームの前記第１のシリーズのマクロブロック当たりの前記計算された平均変位量に基づいて、前記第１のショットのフレーム当たりの平均変位量を計算し、（ｉ）隣接するフレーム間符号化フレームの前記第１のシリーズそれぞれのマクロブロック当たりの前記計算された平均変位量と、フレーム当たりの前記計算された平均変位量との比較と、（ｉｉ）前記計算されたフレーム当たりの平均変位量と、のうちの一方に基づいて、前記第１のショットを表す前記第１のフレーム間符号化フレームを選択するように構成される、フレームを識別するシステム。
【請求項１８】
フレーム内符号化フレームおよびフレーム間符号化フレームのシーケンスに対応する圧縮ビットストリームを格納するよう構成されたメモリであって、前記フレーム間符号化フレームそれぞれは、複数のマクロブロックを有し、前記圧縮ビットストリームは、前記フレーム間符号化フレームそれぞれに関連し、（ｉ）最も密接にマッチングする前記フレーム内符号化フレームへの前記関連するフレーム間符号化フレームの変位量と、（ｉｉ）前記関連するフレーム間符号化フレームの前記複数のマクロブロックのうち、前記最も密接にマッチングするフレーム内符号化フレームへの変位量が閾値未満であるもののランレングスの数、を表すビットを含むメモリと、
第１のフレーム間符号化フレームの前記変位量、および第１のフレーム間符号化フレームに関連するマクロブロックのランレングスの数に基づいて、前記第１のフレーム間符号化フレームを識別するよう構成されるプロセッサと
を備えたフレームを識別するシステム。
【請求項１９】
ランレングスの数は、前記関連するフレーム間符号化フレームの前記複数のマクロブロックのうち、前記最も密接にマッチングするフレーム内符号化フレームへの前記変位量が閾値未満であるもののランレングスの多数の数のうちの１つであり、
ランレングスの異なる数はそれぞれ、異なるランレングスの範囲に関連する複数のカテゴリのうちの１つに関連付けられ、
前記プロセッサはさらに、前記複数のカテゴリそれぞれにおけるランレングスの数に基づいて、前記第１のフレーム間符号化フレームを識別するよう構成される、請求項１８記載のシステム。
【請求項２０】
前記プロセッサはさらに、前記第１のフレーム間符号化フレームに関連するマクロブロックの前記変位量と、前記ランレングスの数とを組み合わせ、該変位量とランレングスの数とを組み合わせたものに基づいて、前記第１のフレーム間符号化フレームを識別するよう構成される、請求項１８記載のシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、概して圧縮されたビットストリームにおける情報の識別に関し、特に圧縮されたビットストリームの所望のセグメントの識別に関する。本発明は、高精細度テレビ（ＨＤＴＶ）放送信号、あるいはインターネットまたはその他の通信ネットワークを介して通信されうるその他の圧縮した形のビデオ情報等のように、符号化ビデオシーケンスにおいて所望のフレームまたはショットを識別する際の使用に特に適する。
【０００２】
【従来の技術】
デジタルカラービデオ信号の帯域幅を圧縮する基本的方法が、動画専門家グループ（ＭＰＥＧ）に採用されている。ＭＰＥＧ基準では、画像のフルフレームについての情報を時々のみ作り出すことによって、高データ圧縮度を達成している。フルの画像フレーム、すなわちフレーム内符号化フレームは、「Ｉフレーム」または「アンカーフレーム」としばしば呼ばれ、他のいかなるフレームから独立したフルフレーム情報を含む。画像差分フレーム、すなわちフレーム間符号化フレームは「Ｂフレーム」および「Ｐフレーム」、または「予測フレーム」と呼ばれることが多く、これは、Ｉフレーム間で符号化され、基準フレームに関する画像の差分、すなわ残余のみを反映している。
【０００３】
通常、ビデオシーケンスのそれぞれのフレームは、より小さな画像要素、すなわち画素のデータブロックに分割される。それぞれのブロックは離散的コサイン変換（ＤＣＴ）関数の影響を受けて、統計的に依存した空間的ドメイン画素を独立周波数ドメインＤＣＴ係数に変換する。マクロブロックと呼ばれる、それぞれの８×８、または１６×１６ブロックの画素は、ＤＣＴ関数の影響を受けて、符号化信号を提供する。ＤＣＴ係数は通常エネルギー集中的であるため、１つのマクロブロックにおいて少数の係数のみが、映像情報の主な部分を含む。例えば、マクロブロックがオブジェクトのエッジ境界を含む場合、変換後のそのブロックのエネルギー、すなわちＤＣＴ係数で表されるものは、比較的大きなＤＣ係数を含み、係数のマトリクスにわたってＡＣ係数がランダムに分散される。一方、非エッジマクロブロックは通常、同様の大きなＤＣ係数と、そのブロックに関連する他の係数よりも実質的に大きな隣接ＡＣ係数とを特徴とする。ＤＣＴ係数は通常、適応量子化の影響を受けてから、送信媒体に関してランレングス符号化および可変長符号化される。このため、送信データのマクロブロックは通常、８×８のマトリクスよりも少ないコード語を含む。
【０００４】
フレーム内符号化データ、すなわち符号化ＰまたはＢフレームデータのマクロブロックは、予測画素とマクロブロックにおける実際の画素の間の差分のみを表す。フレーム内符号化データおよびフレーム間符号化データのマクロブロックはまた、用いる量子化のレベル、マクロブロックのアドレスインジケータまたはロケーションインジケータ、およびマクロブロックのタイプ等の情報も含む。後者の情報は、「ヘッダ」または「オーバーヘッド」情報と呼ばれている。
【０００５】
それぞれのＰフレームは、最後に現れたＩフレームまたはＰフレームから予測される。それぞれのＢフレームは、Ｂフレームがそれらの間に配置されているＩフレームまたはＰフレームから予測される。予測符号化プロセスには、Ｉフレームのどのマクロブロックの変位量が現在符号化されているＢフレームまたはＰフレームのブロックと最も密接にマッチしているかを示す、「移動ベクトル」としばしば呼ばれる変位ベクトルの生成を含む。Ｉフレームにおけるマッチするブロックの画素データが、符号化されているＰフレームまたはＢフレームのブロックから画素毎に減じられ、残余が現れる。変換された残余およびベクトルは、ＰフレームまたはＢフレームの符号化されたデータの一部を形成する。
【０００６】
インターネット上でのビデオ配信等の新しいデジタルビデオサービスの到来と共に、ビデオシーケンスにおける情報を識別する信号処理技術がますます必要になっている。例えば、突然であれ、徐々にであれ、情景変化、および情景の特徴または特性を識別することは、画像変化の索引付けのために有用であり、それにより、関心のある情景を自動的にかつ容易に識別することができる。将来必ず、かなりの量のデジタルビデオマテリアルが、上述のように圧縮または符号化されたデータの形で提供されるだろう。可能な場合に、解凍した、または複号化した形ではなく圧縮した形のビデオシーケンス情報上で動作すると、データサイズが小さく、かつ処理ステップの数が少ないため、通常より迅速に処理することができる。従って、データ上で動作する前に、フルフレーム解凍を行う必要なく、圧縮したデータ上で直接動作可能な技術が必要とされている。
【０００７】
圧縮データからビデオの索引付けする特徴抽出における従来の作業は、主にDC係数抽出を強調していた。論文“Rapid Scene Analysis on Compressed Video",IEEE Transactions on Circuits and Systems for Video Technology, Vol.5, No.6, December 1995, page 533-544において、YeoおよびLiuは、ＭＰＥＧ−２圧縮ビデオドメインにおける情景変化検出へのアプローチを説明している。また、著者は、圧縮していない全画像データのシーケンスをベースにした情景変化を検出するこれまでの努力や、他者の様々な圧縮ビデオ処理技術を検討している。YeoおよびLiuは、オリジナルの画像の空間的に低減したバージョン、いわゆるＤＣ画像、および圧縮ビデオから抽出したＤＣシーケンスを用いて、情景分析動作を促進する、ということを紹介した。彼らの「ＤＣ画像」は、オリジナルの画像の１ブロックにおける画素の平均値である画素からできており、ＤＣシーケンスは、ＤＣ画像の数の低減した画素の組み合わせである。なお、ＤＣ画像抽出ベースの技術はＩフレームに良好であるが、これは、ＩフレームからのＤＣ値の抽出が比較的簡単であるためであることに留意する。しかし、その他のタイプのフレームについては、さらなる計算が必要である。
【０００８】
Proc.SPIE Conf.on Storage and Retrieval for Image and Video Databases,January 1998において発表された論文において、Won他は、ＤＣ係数に費やすビットを利用してフレームにエッジを配置することによって、圧縮ＭＰＥＧ−２ビデオから特徴を抽出する方法を説明している。しかし、彼らの研究は、Ｉフレームのみに限定されている。Kobla他は、同じ会報において、Yeo他のＤＣ画像抽出を用いてビデオクリップを特徴づけるビデオ軌跡を形成する方法を説明している。Feng他(IEEE International Conference on Image Processing,Vol.II,pp.821-824,Sept.16-19,1996)は、ＤＣ画像を抽出することなく、ＭＰＥＧ−２フレームのマクロブロックにわたるビット割り当てを用いて、突然の情景変化を検出する。Feng他の技術は、圧縮ビットストリームをパースするのに必要な分に加えてかなりの計算を行う必要がないので、計算的に最も簡単である。
【０００９】
「Methods of scene change detection and fade detection for indexing of video sequences」（出願第０９／２３１，６９８号、１９９９年、１月１４日）、「Methods of scene fade detection for indexing of video sequence」（出願第０９／２３１，６９９号、１９９９年１月１４日）、「Methods of Feature Extraction for Video Sequence」（出願第０９／２３６，８３８号、１９９９年１月２５日）と題する以前出願され、同一の譲渡人に譲渡された係属中の米国特許出願に記載される、本発明者らおよび協力者の従来作業によれば、Feng他のアプローチのある態様とYeo他のアプローチのある態様との組み合わせを用いて正確かつ簡単な情景変化検出を行う、計算的に簡単な技法が考案されている。ＤＣ画像抽出をベースにした技術を用いることによって、情景またはオブジェクト変化があると疑われるものが連続したフレームのグループ内で正確に見つけられると、見つけた情景の近傍のＰフレームまたはＢフレーム情報に適当なビット割り当てをベースにした技術および／または適当なＤＣ残余係数処理技術を適用することによって、切点を迅速にかつ正確に配置することが確認されている。この組み合わせた方法は、ＭＰＥＧ−２フレームシーケンスあるいはＭＰＥＧ−４の多オブジェクトシーケンスのいずれにも適用することができる。ＭＰＥＧ−４の場合には、各オブジェクトの領域を重み付け要素として用いて、フレームの各オブジェクトにおける変化の重み付け合計を用いるのが有利であることがわかっている。
【００１０】
【発明が解決しようとする課題】
しかし、先に進展した技術にかかわらず、圧縮ビットストリームから所望のフレーム、オブジェクト、ショット、またはシーケンスを識別する簡単な技術が依然として必要とされている。
【００１１】
【課題を解決するための手段】
本発明は、フレーム内符号化されたフレーム、例えばＩフレームとフレーム間符号化されたフレーム、例えばＢフレームおよびＰフレームを含むビデオシーケンスに相当する圧縮ビットストリームにおいて表現されるフレームに対する記述子に向けられている。これは、Ｉフレームはアンカーフレームとも呼ばれ、ＢフレームおよびＰフレームは予測フレームとしばしば呼ばれることが理解されよう。本明細書で使用される場合、「フレーム」という用語は、大部分の現行ＭＰＥＧ規格下で定義されるフレーム、ならびに現行のＭＰＥＧ−４規格下で定義されるフレームを含む。この用語はまた、将来のＭＰＥＧまた同様のビデオ規格、あるいは他の非ビデオ規格で定義される可能性のある圧縮ビットストリームの他のセグメントを網羅するよう意図される。
【００１２】
本発明の記述子は、当業者には充分に理解される任意の数の理由により、所望のフレームを索引付け、選択、またはそうでない場合には識別するために使用できる。例えば、記述子は、圧縮ビットストリームのビットからの、シーケンス全体内のフレームまたはショットの識別に使用することができる。すなわち、クエリフレームに最も密接にマッチする、ビデオシーケンス内の隣接フレームのサブセットは、関心のあるオブジェクトを含むか、あるいは新しい情景の開始を表す。
【００１３】
ビデオシーケンスの圧縮ビットストリームは、フレーム内符号化フレームおよびフレーム間符号化フレームそれぞれに関連するビットを含む。フレーム間符号化フレームに関して、ビットは通常、関連するフレーム間符号化フレーム、例えばＢフレームまたはＰフレームから、最も密接にマッチするフレーム内符号化フレーム、例えばＩフレームへの変位を含む、多数の各種パラメータを表す。従来のＭＰＥＧ規格下では、表された変位は、慣習的に変位ベクトル（時に移動ベクトルとも呼ばれる）により特徴付けられる。
【００１４】
また、ＭＰＥＧ規格、例えばＭＰＥＧ−２規格下では、フレーム内符号化フレームへの変位は、直接的または間接的に表されることも認識されよう。より詳細には、大部分の現行ＭＰＥＧプロトコル下では、特定のＢフレームに関連したビットが、適用可能なＩフレームへの変位を直接表す。しかし、特定のＢフレームに関連するビットもまたＰフレームへの変位を直接表すことができ、Ｐフレームは、適用可能なＩフレームへのさらなる変位を直接表す関連ビットを有する。従って、このような場合、関心のある特定のＢフレームの変位を表すビットは、適用可能なＩフレームへの変位を間接的に表す。
【００１５】
本発明によれば、フレーム間符号化フレームの変位量は、該フレーム間符号化フレームに関連する圧縮ビットストリームのビットに基づいて決定される。好ましくは、圧縮ビットストリームはエントロピ復号化であり、変位量は、エントロピ復号化圧縮ビットストリームから決定される。次に、決定された変位量に基づいてフレーム間符号化フレームが識別される。換言すれば、圧縮ビットストリームのビットから決定される変位量は、所望のフレームとしてフレーム間符号化フレームを識別するために使用される記述子として機能する。変位量は、フレーム自体のみ、またはビデオシーケンス全体、またはシーケンスのサブセット、すなわち特定のショットを特徴付けるよう機能しうる。このように、決定された変位量を用いて、例えばクエリに最も密接にマッチし、関心のあるオブジェクトを含むか、あるいは新しいシーンの開始を表す、シーケンスにおける特定のフレーム、特定のショット、あるいはシーケンスのセットにおける特定のシーケンスさえも、フレームを識別することで、識別できる。
【００１６】
例えば、ビデオシーケンスの所望のフレームに索引を付けるために、ビデオシーケンス内の各フレームの圧縮ビットストリームのビットによって表される、決定された変位量を、クエリフレームの変位量と比較できる。クエリフレームの変位量に最も密接にマッチする変位量を有するビデオシーケンスのフレームが、識別される。このフレームはここで、ビデオシーケンスに索引付けるため、シーンの開始フレームを検索するため、または先行フレームには現れなかった関心のあるオブジェクトの画像を有するフレームを見つけるため等、任意の数の目的のために使用しうる。
【００１７】
典型的に、各フレーム間符号化フレームは複数のマクロブロックを含み、各マクロブロックは、関連するマクロブロックから最も密接にマッチするフレーム内符号化フレームへの変位を表すビットの各部分に関連する。本発明の一態様によれば、各フレーム間符号化フレームの変位量は、該フレーム間符号化フレームに関連する圧縮ビットストリーム内のビットの一部に基づいて、該フレームについてのマクロブロック当たりの平均変位量を決定することにより、決定される。これは単に、全マクロブロックの決定された変位量の合計和を、適用可能なフレームに含まれるマクロブロックの総数でただ除算するだけで、達成できる。次に、所望のフレーム間符号化フレームが、決定された平均変位量に基づいて選択される。
【００１８】
本発明のさらなる態様によれば、適用可能なマクロブロックに関連するビットの適用可能部分で表される、決定変位量は、そのマクロブロックについての変位量が閾値未満である場合には、例えばゼロに設定される。好ましくは、閾値は、適用可能なフレームについての決定された平均変位量である。変位量が閾値未満であるマクロブロックのランレングスに対応する値が決定される。好ましくは、この値は、適用可能なランレングスの数に等しい。例えば、該値は数３であってもよく、これは、変位量が閾値未満であるマクロブロックのランを有するランレングスが３つあることを示す。次に、決定された変位量、例えば平均変位量、およびランレングスに対応する決定値の双方に基づいて、所望のフレーム間符号化フレームを識別できる。換言すれば、圧縮ビットストリームのビットから決定された変位量、およびマクロブロックの決定された変位量から決定されるランレングスの対応値は共に、所望のフレーム間符号化フレームを識別するために使用できる記述子として機能する。このマルチパラメータ記述子により、上述したランレングスなしの記述子と比較して、適用可能なフレームの幾分強化された特徴付けが提供される。
【００１９】
決定されたランレングスの合計は、閾値未満の変位量を有するマクロブロックの総数に等しい。有利なことに、決定されたランレングス各々は、異なるランレングス範囲にそれぞれ対応する複数のカテゴリのうちの１つに分類される。好ましくは、３つのカテゴリ、すなわち短い、中間、および長いランレングス範囲、が使用される。各カテゴリ内のランレングスの数が計算される。次に、決定された変位量と、各カテゴリ内のランレングスの決定された数とに基づいて、フレーム間符号化フレームを識別することができる。すなわち、必要であれば、変位量および各カテゴリ内のランレングスは、所望のフレーム間符号化フレームを識別するために使用される記述子として機能できる。このマルチパラメータ記述子により、上述したランレングスなしのマルチパラメータの記述子と比較して、適用可能なフレームのさらに強化された特徴付けが提供される。
【００２０】
精度を向上させるために、記述子が正規化されると有利である。変位量は通常、フレーム幅に基づいて正規化される。しかし、異なる符号化プロトコルとの互換性を保証するため、変位量およびランレングスに対応する値は、符号化ビットストリームの符号化に使用される１つまたは複数のパラメータに基づいて、正規化されることが好ましい。特に、変位量および値は、符号化フレーム形式、フレームサイズ、フレーム速度、および／またはビットレートに基づいて正規化される。
【００２１】
処理効率をさらに向上させるため、決定された変位量を、決定されたランレングスと組み合わせてもよい。この点に関して、パラメータを組み合わせて、例えばただ１つの値に減らしてもよい。そして、組み合わされた変位量とランレングスは、所望のフレーム間符号化フレームを識別するために使用できる。
【００２２】
上述したように、ビデオシーケンスは、それぞれ、隣接フレーム間符号化フレームの各シリーズから形成される複数のショットを含みうる。場合によっては、上述したように、ショットを形成する各フレーム間符号化フレームのマクロブロックについて、マクロブロック当たりの平均変位量を決定するだけでなく、ショット全体の全マクロブロックについて、フレーム毎のマクロブロック当たりの平均変位量の平均を決定することが望ましいことがある。このような場合、代替の実施において、ショットにおける各フレーム間符号化フレームのマクロブロック当たりの、決定された変位量が、フレーム毎のマクロブロック当たりの平均変位量の決定された平均と比較される。次に、ショットを最もよく表すフレーム間符号化フレームのマクロブロック当たりの決定された平均変位量が、比較に基づいて識別される。例えば、マクロブロック当たりの平均変位量が、ショット全体のフレーム毎のマクロブロック当たりの決定された平均変位量に最も近いショット内のフレーム間符号化フレームを、全体としてあるいはショット内の関心のある特定のコンテンツとして、ショットを最もよく代表するものとして識別することができる。あるいは、フレーム、例えば任意に選択されたフレームは、フレーム毎のマクロブロック当たりの決定平均変位量に関連付けられ、上述した比較を行うことなく、この関連に基づいて識別されうる。
【００２３】
本発明の好ましい実施形態において、ビデオシーケンスに対応する圧縮ビデオビットストリームにおける所望フレームは、各フレーム間符号化フレームに関連する圧縮ビットストリームのビットから決定される記述子に基づいて、識別される。ビットは、（ｉ）最も密接にマッチするフレーム内符号化に対する、関連フレーム間符号化フレームの、マクロブロック当たりの変位量、および／または（ｉｉ）最も密接にマッチするフレーム内符号化フレームへの変位量が閾値量未満である関連フレーム間符号化フレームの複数のマクロブロックのランレングスの、例えば数、に相当する値を表す。フレーム間符号化フレームのうちの２つ、またはそれ以上がまず、フレーム間符号化フレームのマクロブロック当たりの各変位量に基づいて、識別される。次に、これらフレーム間符号化フレームの１つのみが、該フレーム間符号化フレームに関連するランレングスの数に基づいて、識別される。
【００２４】
本発明のさらに別の態様によれば、２つまたはそれ以上のフレーム間符号化フレームそれぞれに関連するランレングスの数の発生頻度が、２つまたはそれ以上のフレーム間符号化フレームのうちの他方に関連するランレングスの数の発生頻度と比較される。所望のフレーム間符号化フレームは、発生頻度の差に基づいて識別される。
【００２５】
圧縮ビットストリームは、メモリに格納できる。そして、プロセッサは、格納された圧縮ビットストリーム内のビットに基づいて、フレーム間符号化フレームの変位量を決定し、続いて、上述したように、決定された変位量および／またはランレングスに基づいて、所望のフレーム間符号化フレームを識別することができる。必要であれば、プロセッサは、平均変位量を決定し、閾値未満の変位量をゼロに設定し、変位量が閾値未満である複数のマクロブロックについてのランレングスを決定し、ランレングスを分類し、各カテゴリ内のランレングスの数を計算し、上述したように、決定された変位量を決定されたランレングスと組み合わせるよう、さらに構成されてもよい。
【００２６】
【発明の実施の形態】
図１は、圧縮ビットストリーム１００の簡略図である。圧縮ビットストリーム１００は、フレーム内符号化フレーム１１０Ａを表すビット１１０ａ1〜１１０ａnと、フレーム間符号化フレーム１１０Ｂを表すビット１１０ｂ1〜１１０ｂnと、フレーム１１０Ｃを表すビット１１０ｃ1〜１１０ｃnと、フレーム間符号化フレーム１１０Ｄを表すビット１１０ｄ1〜１１０ｄnと、を含む。図１に示すように、フレーム１１０Ａ〜１１０Ｄはさらに、ショット１２０を表す。当業者には認識されるように、圧縮ビットストリーム１００のビットは、実際には、通常数百または数千のフレームを表し、こういったフレームは通常、多数の異なるショットを表す。ショットは、圧縮ビットストリーム１００によって完全に表される、映画等のフルビデオシーケンスを形成する。当業者には理解されるように、圧縮ビットストリーム１００は、多数の様々な符号化プロトコルのうちの任意のものに従って符号化できる。
【００２７】
各フレーム１１０Ａ〜１１０Ｄに関連する各ビットは、適用可能なフレームの各マクロブロックに関連するパラメータを表す。特に、図２に示すように、ビット１１０ｂ1〜１１０ｂnの各部分は、マクロブロック１１０ａａ、１１０ａｂ、１１０ａｃ、１１０ａｄ、１１０ａｅから、１１０ａｎのパラメータを表す。フレーム間符号化フレームの各マクロブロックに関連するビットで表されるパラメータは、適用可能なマクロブロックから最も密接にマッチするフレーム間符号化フレームまでの変位量を示す変位ベクトルを表すビットを含む。図２に示すように、圧縮ビットストリーム１００は、フレーム１１０Ａのマクロブロック１１０ｂａについての、最も密接にマッチするフレーム内符号化フレーム、この場合フレーム１１０Ａへの変位ベクトル１１０ａａ1を含む。また図示のように、各マクロブロックを表すビットも、最も密接にマッチするフレーム内符号化フレーム１１０Ａにおける情報からの残余または差分を表すＤＣＴ係数ビット１１０ａａ2を含む。マクロブロック１１０ｂａに関連するビットはさらに、量子化ビット１１０ａａ3と、アドレスおよびタイプ情報ビット１１０ａａ4を含む。同様に、マクロブロック１１０ｂｂ〜１１０ｂｎは、適用可能なマクロブロックのパラメータを定義する、変位ベクトルビットと、ＤＣＴ係数ビットと、量子化ビットと、アドレスおよびタイプ情報ビットを含む。
【００２８】
図３に示すように、フレーム内符号化フレーム１１０Ａを表す、圧縮ビットストリーム１１０内のビットの各部分は、フレーム１１０Ａのマクロブロック１１０ａａ〜１１０ａｎそれぞれに関連する。しかし、フレーム１１０Ａ等のフレーム内符号化フレームには、図２のフレーム１１０Ｂ等、フレーム間符号化フレームの場合のように、そのフレームと別のフレームとの差分を表す変位ベクトルビットおよびＤＣＴ係数ビット１１０ａａ２がない。マクロブロック１１０ａａに関連するビットはまた、量子化ビット１１０ａａ３と、アドレスおよびタイプ情報ビット１１０ａａ４も含まれる。
【００２９】
図４に示すように、各マクロブロック１１０は、１６列および１６行の画素４５０を表す。必要ならば、各マクロブロックは、１６画素ｘ１６画素のブロック以外のものを表してもよい。
【００３０】
図５は、それぞれマクロブロックに分割された、フレーム内符号化フレーム１１０Ａおよびフレーム間符号化フレーム１１０Ｂの簡略図を示す。フレーム内符号化フレーム１１０Ａの場合、フレーム全体は、マクロブロック１１０ａａから１１０ａｐに分割されており、マクロブロック１１０ａｆ〜１１０ａｈおよび１１０ａｊ〜１１０ａｌの画素により形成される話している頭４００の画像を含む。
【００３１】
フレーム間符号化フレーム１１０Ｂは、マクロブロック１１０ｂａから１１０ｂｐを含み、かつマクロブロック１１０ｂｆ〜１１０ｂｈおよび１１０ｂｊ〜１１０ｂｌにおける画素によって形成される、話している頭４００と類似の話している頭４００’の画像を有する。フレーム間符号化フレーム１１０Ｂはさらに話している頭４１０および４２０を含み、話している頭４１０は、マクロブロック１１０ｂａ、１１０ｂｂ、１１０ｂｅ、および１１０ｂｆの画素で形成される。話している頭４２０は、マクロブロック１１０ｂｉ、１１０ｂｊ、１１０ｂｍ、および１１０ｂｎの画素で形成される。
【００３２】
ブロック１１０ａｇと１１０ｂｇ、１００ａｈと１００ｂｈ、１１０ａｋと１１０ｂｋ、１１０ａｌと１１０ｂｌにイメージ化されるように、話している頭４００と４００’間の類似性のため、マクロブロック１１０ｂｇ、ｂｈ、ｂｋ、およびｂｌの変位ベクトルの大きさは、比較的小さい。一方、マクロブロック１１０ａａ、１１０ａｂ、１１０ａｅ、および１１０ａｆの画像からマクロブロック１１０ｂａ、１１０ｂｂ、１１０ｂｅ、１１０ｂｆに示される画像にはかなりの変化があるため、各マクロブロック１１０ｂａ、ｂｂ、ｂｅ、およびｂｆを表すには、比較的大きな変位ベクトルおよびＤＣＴ係数が必要である。同様に、マクロブロック１１０ｂｉ、１１０ｂｊ、１１０ｂｍ、および１１０ｂｎは、フレーム内符号化フレーム１１０Ａに対する差分を定義するために、比較的大きな変位ベクトル、およびＤＣＴ係数が必要である。従って、共にビデオシーケンスの時間空間的圧縮の複雑さを示す、ビット１１０ｂａで表される変位ベクトルおよびビットｂａ２で表される残余データは、マクロブロック１１０ｂａ、１１０ｂｂ、１１０ｂｅ、１１０ｂｆ、１１０ｂｉ、１１０ｂｊ、１１０ｂｍ、および１１０ｂｎでは比較的大きく、マクロブロック１１０ｂｇ、１１０ｂｈ、１１０ｂｉ、１１０ｂｋ、および１１０ｂｌでは比較的小さい。
【００３３】
大きな変位ベクトルおよび残余は、同じ量子化ステップサイズについて符号化するためにより多くのビットをとるため、変位ベクトルに費やされるビットの数ｘおよび残余に費やされるビットの数４は、変位ベクトルおよび残余のサイズに基づいて、マクロブロック毎に、またフレーム毎に変化する。従って、ビデオシーケンスの時間空間的圧縮の複雑さは、変位ベクトルおよび関心のあるフレームの残余を表す、圧縮ビデオビットストリーム１００におけるビットの数に基づいて、決定されうる。
【００３４】
図６に例示的に図示されるように、マクロブロック１１０ｂａビットを表す圧縮ビットストリーム１００におけるビットのセグメントは、変位ベクトルの大きさを表す多数のビットｘ1と、ＤＣＴ係数を表す多数のビットｙ1を有する。他のマクロブロック１１０ｂａのビットもまた、図２を参照して上述したように、量子化ステップのサイズと、アドレスおよびタイプ情報を表すために、ビットストリームセグメントに含まれている。マクロブロック１１０ｂｃを表す圧縮ビットストリーム１００のビットのセグメントは、マクロブロックについての、変位ベクトルの大きさを表す多数のビットｘ3と、ＤＣＴ係数を表す多数のビットｙ3を含む。また、マクロブロック１１０ｂｋに関連する圧縮ビットストリーム１００のビットも図示されている。ビットストリームのこのセグメントにおいて表されるように、マクロブロック１００ｂｋの変位ベクトルの大きさは、多数のビットｘ11と、ＤＣＴ係数１を表す多数のビットｙ11で表される。
【００３５】
図６からわかるように、マクロブロック１１０ｂａの変位ベクトルを表すビットｘ1の数は、マクロブロック１１０ｂｃおよび１１０ｂｋの変位ベクトルを表すビットｘ3およびｘ11の数を上回る。同様に、変位ベクトルビットｘ11の数は、変位ベクトルビットｘ3よりも大きい。また、ＤＣＴ係数ビットｙ1の数は、ＤＣＴ係数ビットｙ3およびｙ11を上回る。これらの相違は、図５に示すように、フレーム間符号化フレーム１１０Ｂのマクロブロックと、最も密接にマッチするフレーム内符号化フレーム１１０Ａ間の差分を鑑みて、各マクロブロックに必要とされる、変位ベクトルのサイズと、ＤＣＴ係数のサイズを反映する。
【００３６】
従って、ビット消費、すなわち図１のフレーム間符号化フレーム１１０Ｂ〜１１０Ｄの各マクロブロックの、変位ベクトルの大きさおよびＤＣＴ係数を表すビットｘおよびｙの数は、圧縮ビットストリーム１００の適用可能なマクロブロックに関連するビットから容易に決定できる。図６に示すように、図１の圧縮ビットストリーム１００は、可変長符号化解析、すなわちエントロピ復号化の影響を受けて、各マクロブロックに関連する適用可能なビットをセグメント化する。ＤＣＴを復号化する必要はない。
【００３７】
必要であれば量子化ステップサイズと結合されたビット消費を使用して、時間空間的圧縮の複雑さを表す。一方、時間空間的圧縮の複雑さは、ビデオシーケンスに索引付けるため、シーケンス内で情景またはオブジェクトの変化を見つけるため、または任意の他の理由により、所望のフレームを識別するためのマッチング基準として使用されうる。
【００３８】
図７は、フレーム内符号化フレーム１１０Ａのマクロブロックビットのセグメント化を示す。例示的な理由により、マクロブロック１１０ａａ、１１０ａｆ、および１１０ａｋに関連するビットを有する、圧縮ビットストリーム１００のセグメントのみを図示する。図示のように、マクロブロック１１０ａａについて、多数のビットｙ’1がＤＣＴ係数を表す。マクロブロック１１０ａａを表すビットのセグメントもまた、図示のように、量子化、アドレスおよびタイプビットを含む。なお、図示のブロックはフレーム内符号化フレームの一部を形成し、変位ベクトルビットは必要ない。従って、フレーム１１０Ａのマクロブロックセグメントは、そのようなビットをいずれも含まない。マクロブロック１１０ａｆおよび１１０ａｋに関連する画像により、これらマクロブロックについてのＤＣＴ係数を表すために必要なビットｙ’6およびｙ’11の数は、マクロブロック１１０ａａに関連するビットｙ’1の数よりも大きい。
【００３９】
変位ベクトルおよび／またはＤＣＴ係数１記述子についてのビットｘおよびｙの決定された数は、各フレーム毎に構築されうる。特に、各フレーム毎に、変位ベクトルについて２つの「圧縮複雑性マトリクス」Ｃmvと、ＤＣＴ係数についてのＣresとは、適用可能フレームにおける各マクロブロックの、変位ベクトルの符号化に必要なビットの数およびＤＣＴ係数、すなわち残余の符号化に必要なビットの数を使用して、以下のように構築することができる。
【００４０】
Ｃmv＝｛Ｒmv（ｉ，ｊ）｝                                      （１）
【００４１】
Ｃres＝｛Ｒres（ｉ，ｊ）｝                                    （２）
【００４２】
但し、ＲmvおよびＲresは、マクロブロックｉからｊにわたる変位ベクトルおよび残余にそれぞれ対応するレートマトリクスである。
【００４３】
マクロブロックがフレーム内符号化フレームとして符号化される場合、その変位ベクトルビットの消費はゼロ、すなわちＣmv＝０であり、その残余のビットの消費、すなわちＣresは、フレーム内符号化に費やされたビットに等しい。
【００４４】
図１０は、フレーム１１０Ｂに対する圧縮複雑性マトリクス７１０および７２０を示す。変位ベクトル用のマトリクス７１０は、図５に示すマクロブロック１１０ｂａ〜１１０ｂｐに関連するビットｘ1〜ｘ16の数で埋められる。マトリクス７２０は、マクロブロック１１０ｂａ〜１１０ｂｐに関連するＤＣＴ係数を表すビットｙ1〜ｙ16の数で埋められる。
【００４５】
図９は、フレーム１１０Ａに対する圧縮複雑性マトリクス７３０および７４０を示す。フレーム１１０Ａはフレーム内符号化フレームであるため、マクロブロック１１０ａａ〜１１０ａｐについての変位ベクトルを表すマトリクス７３０は、ゼロで埋められる。マトリクス７４０は、マクロブロック１１０ａａ〜１１０ａｐに関連するＤＣＴ係数を表すビットｙ’1〜ｙ’16の数で埋められる。
【００４６】
各マクロブロックの量子化パラメータＱＰもまた、マトリクスＱに構築されることが好ましい。変位ベクトルビット消費は量子化ステップサイズにより直接影響を受けないが、量子化ステップサイズは、残余ビット消費に直接影響することがある。量子化ステップサイズ値は、各マクロブロック毎に異なってもよいため、好ましくは、各マクロブロックについての量子化ビットの数もまた、マトリクスの形式に編成され、量子化ステップサイズ値は、記述子の一部として含まれる。
【００４７】
フレームのマクロブロックＣavgmv当たりの変位ベクトルに費やされるビットの平均数は、Ｃmvから計算できる。ＭｘＮはマクロブロックの数である（図５に示されるフレームの場合にはＭ（幅）＝４、Ｎ（高さ）＝４である）場合、フレームにおけるマクロブロック当たりの変位ベクトルを表すビットの平均数は、図７Ａに示すように、フレーム１１０Ｂｘ1からｘ16のビットｘ、およびフレームマクロブロックに関連するあらゆる変位ベクトルのビットｘ、の数を合計し、その合計を、フレームにおけるマクロブロックの数、フレーム１１０Ｂの場合には数１６で除算することで、計算できる。この平均は、フレームの時間的複雑さの非常に有用な測定であり、例えばクエリフレームよりもはるかに変位が多いか、または少ないフレームを考慮から外すための第１のマッチング基準として使用されうる。例えば、ＭＰＥＧビデオ圧縮システムにおいて、変位ベクトルビットの平均数により、静止オブジェクトおよび移動オブジェクトの容易な区別が促進される。各フレームにおける変位について、マクロブロック当たりに費やされるビットの最大数、およびマクロブロック当たりに費やされるビットの最小数を計算することもできる。
【００４８】
各フレームのマクロブロックＣavgres毎の残余の平均圧縮複雑性も同様に、ＤＣＴ係数について、フレーム１１０Ｂｙ1〜ｙ16のビットｙの数を合計して、合計したものをマクロブロックの数、フレーム１１０Ｂの場合には数１６で除算することで、計算できる。この数もまた、さらなるフレームの分類またはマッチングに使用される。
【００４９】
次に、変位ベクトルの「ランレングス」が、移動ベクトルレートマトリクスの各要素によって表されるビットｘの数と、例えば適用可能フレームについてマクロブロック当たりの変位ベクトルに費やされるビットの平均数に等しい閾値と比較することにより、計算される。より詳細には、閾値よりも小さな変位ベクトルマトリクスにおけるビットｘの数で形成されるさらなる変位ベクトル閾値マトリクスＣthreshmv（ｉ，ｊ）は、ゼロに設定される。閾値に等しいかまたはそれよりも大きな、表されるビットｘの数は、マトリクスに保持される。閾値は、記述子の一部として有利に設けられる。
【００５０】
移動ベクトル閾値マトリクスにおいて、ゼロのランレングスが決定される。ゼロの総数Ｎ0もまた、すべてのランレングスを合計することによって決定される。次に、ランレングスは、３つのカテゴリ、例えば短い、中間、および長い、に分類される。ＱＣＩＦ画像の場合、短い範囲は、例えばフレーム中のマクロブロックの総数の６％未満、中間範囲が約９〜１０％まで、そして長い範囲は、中間範囲（例えば１０％）の上限よりも上として定義される。これらのパーセント範囲は、別の場合にも適用可能であり、また、必要ならば変更できる。
【００５１】
３つのカテゴリ、例えばＮsr、Ｎmr、およびＮIrそれぞれにおける要素の数が決定される。これらの数は、マッチングのためのランレングス特徴として使用される。同一フレームを変換されたもの、または鏡面反射したものが根本的に異なった記述子を生成しないようにするために、３つの異なるレベルまたはカテゴリが使用される。さらに、この分類により計算が簡易化されて、異なるサイズのオブジェクトまたはフレームの比較を助ける。大部分が短いランであるフレームには、例えば、頭および肩のシーケンスが含まれ、一方、大部分が長いランであるフレームには、静止オブジェクト、または非常にゆっくりと動いているオブジェクトのシーケンス、またはハイアクションが集中しているフレームを含む可能性が高い。ゆっくりと動いているオブジェクトと高速で動いているオブジェクトとの組み合わせを有するフレームは、大部分、中間長のランを有する可能性が高い。
【００５２】
図１１は、フレーム１１０Ｂのマクロブロックについての変位ベクトルを表すビットの数の閾値マトリクス７１０’を示す。多数のマトリクス要素は、閾値に基づいてゼロに設定されている。図６を再度参照して、閾値は、例示的なビットストリームセグメントと関係するライン５１０で表される。このため、フレーム１１０Ｂの場合、マクロブロック１１０ｂｃ等、図６においてライン５１０で表されるビットの閾値数よりも少ない数のビットを有するマクロブロックは、マトリクス７１０’においてゼロに設定されている。
【００５３】
マトリクスの左上の角から始まって、該マトリクスの右下の角で終わるラスタスキャンパスを用いて、ランレングス８１０〜８３０が決定される。図示のように、ランレングス８１０は、２つの要素、１つの要素のランレングス８２０と、５つの要素のランレングス８３０と、からなる。従って、ランレングス８２０は短い範囲に分類され、ランレングス８１０と８３０は長い範囲に分類される。
【００５４】
図８は、フレームマクロブロックのある画素により形成される画像４００’’を有するフレーム間符号化フレーム１１０Ｃおよび１１０Ｄを示す。画像は、フレーム１１０Ａで図示された画像と同様であるが、わずかに異なる。
【００５５】
図１２は、フレーム１１０Ｃ、１１０Ｄのいずれかについての、変位ベクトル閾値マトリクス８００を示す。マトリクスは、フレームの閾値に基づいてゼロに設定された多数の要素を含む。これらゼロの要素は、ランレングス８４０〜８７０を形成する。ランレングス８４０は５つの要素からなり、ランレングス８５０および８６０はそれぞれ、２つの要素からなり、ランレングス８７０はただ１つの要素からなる。従って、ランレングス８７０は短い範囲に分類され、ランレングス８４０、８５０、および８６０は長い範囲に分類される。
【００５６】
従って、記述子は、Ｃavgmv、Ｃmv、Ｎ0、Ｎsr、Ｎmr、Ｎlr、Ｃavgres、Ｃres、Ｑ、および付加的に圧縮形式、圧縮速度、フレームサイズ、およびフレーム速度からなる。記述子がシーケンスの各フレームに生成（ｄｅｖｅｌｏｐ）された後、短いものへの記述子を決定できる。まず、ビデオシーケンスは、任意の所望の情景変更検出技術を使用して、一時的にショットにセグメント化される。ショット全体Ｃshotmvにわたるマクロブロック当たりの変位ベクトルに費やされるビットの平均数が計算される。フレームは、Ｃshotmvに最も近いＣavemvを有するフレームのグループから、無作為に選択され、その記述子が、ショット全体の記述子として使用される。代替として、Ｃshotmvに最も近いＣavemvを有するフレームを、ショットを表すものとして選択してもよい。別の代替として、ショットにわたる各パラメータの平均値を計算し、その結果得られるパラメータの平均値を使用して、ショットの記述子を構成する。
【００５７】
上述した記述子を、同様のフレームまたはショットをマッチするために使用できる。すなわち、マッチングにおける第１パスとして、フレームまたはショットのグループ内の潜在的なマッチの第１のリストを、画像４２０’および４００’’またはクエリショットを含む図６のクエリフレーム６１０等のクエリフレームの、マクロブロック当たりの変位ベクトルの平均ビット消費と同様の、すなわちある数値的範囲内の、マクロブロック当たりの変位ベクトルの平均ビット消費に基づいて、作成できる。次に、各記述子におけるすべてのランレングスの合計Ｎ0が、クエリフレームのすべてのランレングスの合計との潜在的なマッチングに関して、第１のパスからの候補すべてをさらにランクするための第２のパスとして使用される。あるいは、所定の最も頻繁なランレングスのカテゴリが、マッチングについて検査される。２つの候補フレームまたはショットが、適用可能なランレングス値について同じ値を有する場合、そのランレングスの頻度を使用して、フレームまたはショットのさらなるランク付けを行うことができる。フレームまたはショットが、最も普通のランレングスカテゴリについて同じ値を持たない場合、そのフレームまたはショットは、「不適（ｉｎｆｅｒｉｏｒ）」マッチングカテゴリに配置される。「不適」マッチングカテゴリのフレームまたはショットは、通常これ以上ランク付けされない。
【００５８】
図１３は、上記技術の実施に使用できる処理システム９００の簡略図である。システム９００は、バス９３０によりメモリ９２０に接続されたプロセッサ９１０を含む。入出力（Ｉ／Ｏ）ポート９４０により、情報が処理システムに対して入出力される。メモリは、プロセッサに上記記述子を作成および／または使用するよう指示するプログラミング９２０ａを含む。図示のように、メモリ９２０はデータベース９２０ｂを備える。構築された記述子をデータベース９２０ｂに格納できるため、プロセッサ９１０が、プログラミング９２０ａに従って、クエリ、例えばＩ／Ｏポート９４０を介して受信した圧縮ビットストリームを処理し、データベース９２０ｂにおける記述子に基づいて、メモリ９２０に格納してもよい、圧縮ビットストリーム内に表される適切なフレーム、ショット、またはシーケンスを識別できる。
【００５９】
処理システム９００は、スタンドアロン式システムでもよく、またはインターネット等のネットワークにＩ／Ｏポート９４０を介して接続されてもよいことが認識されるであろう。また、システム９００は、多重処理システムとして実施されてもよいことを理解されたい。この点において、システムの１つまたは複数が、記述子を生成するようプログラムされて、別のシステムが、別のシステムによって構築された記述子に基づいて、フレーム、ショット、またはフルシーケンスを識別するよう別個にプログラムしてもよい。また、予め構築された記述子を格納しているメモリは、別個に、かつ関心のあるフレーム等を識別するために記述子を利用するプロセッサから離れて配置されてもよいことを認識されたい。このような場合、メモリに格納される記述子は、ネットワークリンクを介して、例えば別個のインターネットウェブサイトにアクセス可能である。
【００６０】
次に図１４を参照して、ステップ１００５において、プロセッサ９１０が、Ｉ／Ｏポート９４０およびバス９３０を介して、圧縮ビデオビットストリームを受信する。ステップ１０１０において、プロセッサ９１０は、メモリ９２０に格納されたプログラミング９２０ａに従って、各フレームの各マクロブロックについて変位ベクトルの数を決定する。次に、ステップ１０１５において、プロセッサは、各フレームの各マクロブロックについて、ＤＣＴ係数の数を決定する。ステップ１０２０および１０２５において、変位ベクトルビット数マトリクスＣmvおよびＤＣＴ係数ビット数マトリクスＣresが構築される。ステップ１０３０および１０３５において、マクロブロック当たりの変位ベクトルビットの平均数Ｃavgmv、ならびにマクロブロック当たりのＤＣＴ係数ビットの平均数Ｃavgresが計算される。
【００６１】
次に、ステップ１０４０において、プロセッサ９１０は、変位ベクトルマトリクスにおける変位ベクトルの数が、閾値、好ましくはＣargmv未満であるかどうかを決定し、ステップ１０４５において、マトリクスＣmvの、閾値未満のビット数を反映する要素がゼロに設定される。ステップ１０５０で示されるように、各マトリクスの他の要素は保持される。
【００６２】
ステップ１０５５において、閾値マトリクスＣthreshmvが構築され、各フレームのゼロビットのランレングスが、プロセッサ９１０により計算される。次にステップ１０６０において、プロセッサは、各フレームランレングスを分類し、ステップ１０６５において、各カテゴリ内のランレングスの数を計算する。ステップ１０７０において、プロセッサはさらに、各フレーム合計ランレングスを計算する。次に、ステップ１０７５において、記述子が、適用可能なフレームについて構築される。記述子は、データベース９２０ｂへの格納のために、バス９３０を介してメモリ９２０に向けられてもよい。
【００６３】
次に図１５を参照して、圧縮ビデオビットストリームにおいて表される各ショットを表すために、特定のフレーム記述子を選択しうる。ステップ１１０５において、該ショットに適切な記述子を決定するため、プロセッサ９１０は、メモリ９２０に格納されたプログラミング９２０ａに従って、圧縮ビデオビットストリームをショットにセグメント化する。次にステップ１１１０において、プロセッサは、ショットセグメント内の全フレームにわたる、マクロブロック当たりの変位ベクトルビットの平均数Ｃshotmvを計算する。次にステップ１１１５において、計算されたショットの平均は、ショット内の各フレームのマクロブロック当たりの変位ビット数の計算された平均値と比較される。
【００６４】
次にステップ１１２０において、プロセッサは、ショット全体についてのマクロブロックあたりの変位ベクトルビットの平均数と最も近い、例えばほぼ等しい、ショット内のフレームについてのマクロブロック当たりの変位ベクトルビットの平均数を決定する。ステップ１１２５および１１３０に示されるように、ショットについての変位ベクトルビットの平均数に有利に匹敵する変位ベクトルビットの平均数を有するフレームが、さらなる分析のために選択され、その他のフレームは無視される。ステップ１１３５において、選択フレームについてのマクロブロックあたりの変位の平均数が、閾値と比較される。ステップ１１４０において、閾値と最も有利に匹敵するフレームが、ショットを表すものとして選択され、ステップ１１３０に示すように、その他のフレームは無視される。別のアプローチでは、プロセッサが４つのパラメータすべてについてショットにわたる平均値を決定してから、結果得られた個々のパラメータの平均値を使用して、ショットの記述子を構成する。
【００６５】
上記技術の周知のテスト画像（シーケンス）への適用は、得られる記述子および実行できる分析の性質を理解する上で有用である。このため、シーケンス「Ａｋｉｙｏ」が分析されている。「Ａｋｉｙｏ」シーケンスの「背景」オブジェクト（オブジェクト番号０）に関連する移動ビット消費を表すマトリクスは、マクロブロックの１１ｘ９アレイから構成され、各マクロブロックは、画素の１６ｘ１６アレイからなり、以下のように表される。
【００６６】
移動ビット消費
Akiyo:（１０フレーム／秒）オブジェクト番号０
サイズ  １１ｘ９（単位：マクロブロック）（マクロブロックサイズ１６ｘ１６）（背景）
０００００００００００
０００００００００００
０００００００００００
０００００００２０００
０００００００００００
０００２０００７６００
００４００００００８０
０２０００００００００
０００００００００００
【００６７】
「背景」オブジェクトについて予想されるように、移動情報の複雑さは低い。マクロブロック当たりのビットの平均数（９９個のマクロブロック）は、０．３１である。
【００６８】
この場合、閾値処理後に得られる出力マトリクスは、閾値（０．３１）が低いため、入力マトリクスと同じであろう。左上から右下に走査した、オブジェクトのランレングス表現は、次のようになる。
【００６９】
40 2 17 2 3 7 0 6 4 4 6 8 2 2 20（閾値Ｔ＝０）
【００７０】
同様に、９ｘ８アレイで構成される「Akiyoの頭および肩」（オブジェクト番号１）についての移動ビット消費は、次のようになる。
【００７１】
オブジェクト番号１  サイズ９ｘ８（Akiyoの頭および肩）
0 0 0 10 21 15 0 0 0
0 0 0 4 2 2 0 0 0
0 0 0 0 22 16 18 4 0 0
0 0 0 14 2 4 2 0 0
0 0 6 4 22 22 2 5 0
0 4 6 2 2 29 6 0 0
0 2 0 2 2 2 6 0 4
0 0 0 0 2 2 2 2 0
【００７２】
マクロブロックあたりのビットの平均数は、３．７７であり、「背景」に関連する数よりはかなり大きな数である。閾値処理後のマトリクスは、この場合、次のようになる。
【００７３】
0 0 0 10 21 15 0 0 0
0 0 0 4 0 0 0 0 0
0 0 0 22 16 18 4 0 0
0 0 0 14 0 4 0 0 0
0 0 6 4 22 22 0 5 0
0 4 6 0 0 29 6 0 0
0 0 0 0 0 0 6 0 4
0 0 0 0 0 0 0 0 0
【００７４】
同様に、ランレングス表現は、はるかに多くのデータを含み、次のようになる。
【００７５】
3 10 0 21 0 15 6 4 0 2 0 2 6 22 0 16 0 18 0 4 5 14
0 2 0 4 0 2 4 6 0 4 0 22 0 22 0 2 0 5 2 4 0 6 0 2
0 2 0 29 0 6 1 4 4 2 0 2 0 2 0 2 1    閾値Ｔ＝０
【００７６】
オブジェクト番号０およびオブジェクト番号１の対応する残余ビット消費は、次のようになる。
【００７７】
残余ビット消費  オブジェクト番号０
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 13 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 8 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 16 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
オブジェクト番号１
0 0 0 5 0 28 0 0 0
0 0 0 18 24 22 0 0 0
0 0 0 69 55 25 14 0 0
0 0 0 56 96 61 21 0 0
0 0 0 28 9 26 31 17 0
0 23 0 7 36 8 19 0 0
0 16 0 5 63 5 14 0 0
0 0 0 0 18 47 51 25 0
【００７８】
オブジェクト番号０の残余に関連するマクロブロック当たりの平均ビットは、０．３７であり、オブジェクト番号１では１３．０８である。各ランレングス表現は、次のようになる。
オブジェクト番号０
40 13 20 8 20 16 20（閾値Ｔ＝０．３７）
オブジェクト番号１
5 28 6 18 0 24 0 22 6 69 0 55 0 25 0 14 5 56 0 96 0 61 0 21 5 28 1 26
0 31 0 17 2 23 2 36 1 19 3 16 2 63 1 14 6 18 0 47 0 51 0 25 1    （閾値Ｔ＝１３）
【００７９】
ニュースシーケンスからの画像モニタも分析された。
【００８０】
ニュースシーケンスからモニタ（１０フレーム／秒）  サイズ６ｘ５
移動複雑性マトリクスＣmv
0 4 0 4 15 16
2 26 7 33 6 20
0 4 32 0 26 16
0 0 2 2 26 21
0 0 0 2 2 0
平均ビット／マクロブロック＝８．８６
モニタ
閾値処理後のマトリクス
0 0 0 0 15 16
0 26 0 33 0 20
0 0 32 0 26 16
0 0 0 0 26 21
0 0 0 0 0 0
Ｎ0＝２０、Ｎsr＝７、Ｎmr＝１、Ｎlr＝０
残余複雑性マトリクスＣres
0 19 0 49 169 33
7 82 33 49 248 32
0 24 26 0 76 0
0 0 48 36 64 9
0 0 0 14 20 0
平均ビット／マクロブロック＝９４．３６    ＱＰ＝１２
【００８１】
上に示した最初の２例は、ＭＰＥＧ−４オブジェクトの記述子である。シーケンス「Akiyo」の背景等、移動の少ないオブジェクトは、ニュースシーケンスのモニタのようなアクティビティの多いオブジェクトから非常に容易に区別される。
【００８２】
図２５は、ＭＰＥＧ−２形式の空間時間的複雑さの例を示す。ＭＰＥＧ−２のプロパティは通常、ＭＰＥＧ−４オブジェクトのものほど均質ではないため、ばらつきが見られることがわかる。しかし、ＭＰＥＧ−２の場合でさえも、本発明による記述子により、空間時間的に類似するフレームの簡単かつ効率的なクラスタ化が可能になる。
【００８３】
なお、より大きなＭＰＥＧ−２フレームの変位複雑さは（ＭＰＥＧ−４の場合のオブジェクトと比較して）、より高いように見えるが、これは、解像度の高いデータはより大きな変位ベクトルを与えるためである。従って、現在のマッチング基準を利用しながら、フレームサイズについての情報を得ることが重要である。また、記述子は、変位ベクトルビットが省かれている場合を除いて、フレーム間符号化フレームならびにフレーム内符号化フレームに適用可能であることに留意する。
【００８４】
本発明による記述子は、オブジェクトへのセグメント化が容易に利用可能であることから、主にＭＰＥＧ−４に適用されている。オブジェクトは多少なりと均質なプロパティを有するため、通常、上記記述子を利用した比較は、有効な結果をもたらす。２つのマルチオブジェクトＭＰＥＧ−４シーケンスは、同様に配置されたオブジェクトのオブジェクト毎の比較を用いて、比較されてきた。基本的な変位補償情報が記述子に使用されてきたため、結果は、残余のＤＣＴ符号化と組み合わせたブロック変位補償を使用する、任意の圧縮ビデオシンタックスに容易に適用可能であるべきである。さらに、セグメント化されていないフレームもまた合成オブジェクトと考えることができるため、このアプローチは、かかるフレームにも適用されよう。その場合、記述子は、シーケンスを単一オブジェクトとして扱うことで、シーケンスに対して生成される。かかる「合成」オブジェクトの特徴は均質ではないため、個々のオブジェクトの記述子との比較はいずれも、有効な結果をもたらす可能性が低い。しかし、フレームに基づく記述子の２つのセット間の比較は、有用な結果を提供する。
【００８５】
本研究はまた、ターゲットとする適用が、最低予期品質が高いマルチメディアデータベースであることから、ＭＰＥＧ−１ビットレートにも集中している。本研究はまた、フルフレーム速度、すなわち２５または３０フレーム／秒に主に関連している。なお、変位複雑さ特徴は、フレーム速度の関数として変化する。しかし、変位ベクトルに費やされるビットの割り当ては、より低いビットレートであってもそれほど変化しないことが確認されている。残余ビット割り当てだけが、ビットレートの変化によって大きく影響される。また、レート制御方策の変更は変位プロパティにあまり影響しないが、残余情報をかなり変更することがわかっている。これらの要因により、変位プロパティに大きく基づいた特徴を強化する記述子がもたらされた。しかし、残余情報は、ある状況において有用である可能性がある異なる情報を提供するために、生成され、保持される。例えば、２つのオブジェクトが同じ変位プロパティを有するが、同じＱＰ（量子化パラメータ）を使用すると、一方のオブジェクトは、残余の符号化のために他方よりも多くのビットを必要とし、前者は、後者よりも時間空間的に複雑である。しかし、一方のオブジェクトの量子化ステップサイズが他方のオブジェクトのものに等しいか、または大きいが、第２のオブジェクトに費やされた残余符号化ビットが第１のオブジェクトのものよりも少ない場合、この２つのオブジェクトの時間空間的な複雑さに関しては何の結論も得られない。すなわち、残余ビット割当は、この点に関して常に結論的な情報を提供するとは限らない。
【００８６】
図１７において、典型的な記述子値が、ＭＰＥＧ−４オブジェクトの普通に知られているセットについて図示される。記述子の使用を、この図１７を参照することによって説明できる。記述子を使用するためのステップのシーケンスは、いくつかの異なる形式をとることができ、また、２つの特定のサーチ手順によって説明されうる。
【００８７】
第１のおよび好ましい手順は、「縦続」として識別され、ここでは、フレームまたはショットセットを狭めるために、一度に１つの記述子特徴が比較される。例えば、第１の特徴が採用されるサーチの第１段階において、クエリに「マッチング」する１０個のフレームまたはショットが、１００個のフレームまたはショットから得られ、第２の段階において、異なった記述子特徴を使用して、５個のフレームまたはショットの「マッチング」が、第１の段階で見出された１０個のフレームまたはショットから得られるものと想定する。
【００８８】
縦続サーチにおいて有用な特徴の１セットは、Ｃavgmvのシーケンスの後に、Ｎsr、Ｎmr、Ｎlrを含むランレングス特徴セットが続いたものである。マッチングテストの結果は、上述した記述子が、クエリオブジェクトと移動が類似するオブジェクトを見つけるために適していることを示す。第１の段階は、変位特徴が著しく異なる候補を削除し、第２の段階は、全体的な変位複雑さが同じであるが、変位密度の分布が異なる候補を削除する。マッチングは時に、意味的にクエリシーケンスとはかなり異なるが、２つの意味論的に類似しないフレームのＭＰＥＧ−２／４ベースの圧縮の複雑さ同様であり得るため、このことを予想することができる。例えば、コンテナ船のオブジェクトは、移動の複雑さにおいてＡｋｉｙｏの頭および肩と似ている。その場合、ランレングスの特徴を含む比較の第２段階は通常、意味論的に同様のオブジェクトをより近くするが、テクスチャにおける相違によって船を頭および肩の画像から分ける。プロセスの目的が、一層複雑な方法によって更に処理することができる候補の短いリストを生成することであるから、この場合にはこのような最終識別が行われる。本システムは、所望の結果を達成する。
【００８９】
図１６は、クエリを、圧縮ビデオビットストリーム１００で表される適切なフレームまたはショットにマッチする際に、処理システム９００により行われる動作のフローチャートである。ステップ１２０５において、Ｉ／Ｏポート９４０を介してクエリを受信し、バス９３０を介してプロセッサ９１０に送信される。ステップ１２１０において、メモリ９２０に格納されたプログラミング９２０ａに従って、プロセッサがデータベース９２０ｂに格納された記述子を検索し、各フレームまたはショットのマクロブロック当たりの変位ベクトルビットの平均数を、クエリと比較する。なお、クエリが圧縮ビデオビットストリームを含む場合、マッチングフレームまたはショットを識別するために、プロセッサは、上述した動作の一部またはすべてを実行し、クエリに対する記述子を構築して、予め構築され、メモリ９２０ｂに格納された記述子と比較する。あらゆる場合において、クエリと有利に比較されるマクロブロックあたりの変位ベクトルビットの平均数を有するフレームまたはショットは、ステップ１２１５に示すように、さらなる分析について考慮される。ステップ１２２０に示すように、その他のフレームは無視される。
【００９０】
ステップ１２２５において、マッチする可能性のあるフレームの１つまたは複数のランレングスが、クエリと比較される。クエリと有利に比較される、適用可能なカテゴリ内のランレングスを多数有するフレームは、ステップ１２３０に示すように、さらなる処理のために識別される一方、その他のフレームは無視される。ステップ１２３５において、プロセッサ９１０は、クエリに対してまだ考慮されるフレームについての残余ビットの平均数をさらに考慮する。記述子において、最も密接にマッチする残余ビットの平均数を有するフレームまたはショットは、クエリに対する最適マッチングとして識別される。従って、マッチングフレームのリストを、類似性の降順に形成することができる。
【００９１】
様々なＭＰＥＧ−４のオブジェクトに関する本発明による技術を用いた第１および第２の段階のマッチングの具体例を、図２６、図２７、および図２８に示す。
【００９２】
第２のサーチ手順は、比較を行うために、記述子特徴の重み付けした組み合わせを使用する。様々な特徴に与えられる特定の重みは、その特徴の性質およびスケールが異なるため、複雑な考察を伴う。重み付け手順は、単純な正規化技術を使用して、テストとクエリ記述子の間のフィールド毎の相違を組み合わせる。これは、各フィールドにおける相違を、クエリ記述子における対応するクエリにより除算することからなる。結果得られる正規化された相違を次に加算して、クエリ記述子とテスト記述子との間の相違合計を得る。
【００９３】
上記記述子はまた、比較的簡単な装置に適用でき、より複雑な装置による、より少ないデータセット上でのより上位レベルのＭＰＥＧ−７記述子の計算を容易にすることができる、中間ＭＰＥＧ−７記述子としても有用である。
【００９４】
上述した技術を採用する際のさらなるステップとして、時間的セグメント化マーカを生成してもよく、これらのマーカは、入力ビデオシーケンスと関連して、情景変更の特定のタイプを見つけだし、識別する。その後、ビデオシーケンスの特徴を本発明に従って抽出してもよい。
【００９５】
要約すると、記述子は、オブジェクト／フレームにおける各マクロブロックの変位ベクトルおよび残余を符号化するために必要とされるビットの数に基づいて構築される。変位ベクトルおよび残余の圧縮複雑性マトリクスは、可能な限りビットレートとは無関係に作成される。フレームのマクロブロック当たりの変位ベクトルに費やされるビットの平均数を、計算することができる。この平均は、フレームの変位の複雑さについての有用な尺度である。低ビットレートのＭＰＥＧ−４では、この平均により、静止オブジェクトと移動オブジェクトの間の区別が容易になる。フレームのマクロブロック当たりの残余の平均圧縮複雑性もまた、フレームの分類および／またはマッチングにおいて有用である。フレームのランレングスは、多くの要素を強制的にゼロにする低ビットレートにおいて特に有用である。決定には走査順を使用することが好ましいが、他の任意の順を使用できる。ランレングス構造は、単純な形での、圧縮複雑性の空間的分散の形状表現である。ランレングスを決定する前に閾値が使用され、ここで、特定の閾値未満のすべての要素がゼロに設定される。閾値は、記述子の一部として与えられることが好ましい。それにより、記述子は、シーケンスの各フレームについて作成される。
【００９６】
ショットについての記述子は、まず、好ましくは任意の既知の情景変更検出技術を用いて、ビデオシーケンスを一時的にショットに分割することにより生成される。ショット内の全フレームの平均に最も近いフレームのグループ内に入る、ショットのフレームのフレーム記述子が、そのショットの記述子として使用される。情景遷移からレート制御を行うために、最初のいくつかのフレームを、ショット平均を決定する際にスキップしてもよい。
【００９７】
マクロブロック当たりの変位ベクトルに費やされる平均ビット、ならびにマクロブロック当たりの平均圧縮複雑性は、候補をランク付けるマッチング基準として機能できる。次に、各表現におけるランレングス情報を使用して、候補をさらにランク付けることができる。その後、等しく索引付けられたランレングス、すなわちフレームの短い、中間の、および長いレングスのランレングスを、クエリフレームの対応するランレングスと比較する。本発明は様々なソースからの単一フレームまたはショットのマッチングに関して上述したが、上記技術をショットの集まりに適用することが本発明の範囲内にあることを認識されたい。例えば、アクション映画は一行に移動複雑性が高いショットをいくつか有するが、より落ちついた映画は、一行に時間空間的複雑さが低いショットを多数有する。これらの特徴を集めて、映画全体のマッチング基準を提供するために使用できる。また、上述したシーケンスのステップは、互いに時間的に近接している必要はなく、実際には時間的に離れている。特に、記述子を作成して格納し、後にマッチングを見つけるために使用してもよい。
【００９８】
フレーム間符号化フレームデータ、すなわち符号化されたＰまたはＢフレームデータのマクロブロックはまた、ＤＣＴ係数のマトリクスからなる。しかし、これら係数は、予測された８ｘ８画素のマトリクスと実際の８ｘ８画素のマトリクスとの間の相違を表す。
【００９９】
上述した記述子は、すべてのビットストリームおよびクエリが同じ符号化規格に対応する場合には良好な結果をもたらすが、ビットストリームおよび／またはクエリが異なる符号化規格に対応する場合、より満足度の低い結果をもたらす。
【０１００】
従って、本発明の第２の実施形態により、上述した記述子よりもより頑強な、ビデオシーケンスにおける変位アクティビティの空間的な分散についての記述子を、さらに以下で説明する。この大きさ記述子は、移動ベクトルの大きさを、マクロブロックにおける変位アクティビティの密度の測定として使用する。マトリクスＣmmvは、所与のフレームの各マクロブロックの変位ベクトルの大きさを表す、圧縮ビットストリーム１００のビットを使用することで、構築される。マクロブロック当たりの移動ベクトルの大きさ平均Ｃavgmmvが計算される。Ｃavgmmvは、Ｃavgmmv未満のＣmmvの要素をゼロに設定することで表される大きさを設定することで、マトリクスＣmmvの閾値として使用される。ゼロのランは、上述したように、長さに基づいて３つのカテゴリに分類される。各カテゴリのランの数Ｃmmvが計算される。そうすると、各フレームの記述子は、４つのパラメータ、すなわち変位ベクトルの平均大きさ、短い、中間、および長いランレングスの数からなる。特徴抽出は依然として圧縮ドメインで行われ、単純であるため、これは非常に高速である。ＭＰＥＧ−７テストコンテンツセットでのテストに基づいて、大きさ記述子により、ビデオの高速かつ正確な索引付けを行うことができる。これは、フレームサイズ、フレーム速度、符号化ビットレート等の符号化パラメータにおけるノイズおよび変化に対して耐性がある。
【０１０１】
より具体的には、各フレーム間符号化フレームについて、「アクティビティマトリクス」Ｃmmvが以下のように構築される。
【０１０２】
Ｃmmv＝｛Ｒ（ｉ，ｊ）｝＝√（ｘ2i,j＋ｙ2i,j）                （３）
【０１０３】
但し、（ｘｉ，ｊ、ｙｉ，ｊ）は、（ｉ，ｊ）番目のブロックに関連する変位ベクトルの大きさである。
【０１０４】
フレーム内符号化フレームの場合、Ｒ（ｉ，ｊ）＝０である。フレームＣavgmmvのマクロブロック当たりの移動ベクトルの大きさ平均は、以下のように計算される。なお、前（左側）のΣの範囲ｉ＝０〜Ｍ、後（右側）のΣの範囲ｊ＝０〜Ｎである。
【０１０５】
Ｃavgmmv＝１／ＭＮ・ΣΣＣmmv（ｉ，ｊ）                      （４）
【０１０６】
図１８は、フレーム１１０Ｂについての、本発明の第２の実施形態による変位ベクトルの大きさマトリクス１４００を示す。図示のように、マトリクスはマクロブロック１１０ｂａ〜１１０ｂｐについての圧縮ビットストリーム１００における変位ベクトルの大きさを表す実際のビット１１０ｂａ1〜１１０ｂｐ1を含む。
【０１０７】
移動ベクトルレートマトリクスの「ランレングス」特徴は、ＣavgmmvをＣmmvに対する閾値として使用して、以下のように計算される。
【０１０８】
Ｃmv（ｉ，ｊ）≧Ｃavgmvならば、
Ｃthreshmv（ｉ，ｊ）＝Ｃmv（ｉ，ｊ）
それ以外では、
Ｃthreshmv（ｉ，ｊ）＝０（５）
【０１０９】
上述したように、マトリクスにおけるゼロのランレングスは、ラスタスキャン順を用いて計算される。ランレングスは、フレーム幅に関して正規化された３つのカテゴリ、すなわち短い、中間、および長い、に分類される。例えば、カテゴリは、短いランが幅の１／３以下、中間のランが幅の１／３よりも大きくかつ幅の２／３未満、長いランが幅の２／３以上のすべてのラン、と定義することができる。Ｎsrは短いランの数であり、Ｎmrは中間ランの数であり、またＮlrは長いランの数である。
【０１１０】
図１９に示すように、フレーム１１０Ｂの閾値マトリクスＣthreshmmv１５００は、ゼロに設定された多数の要素を有する。結果得られるランレングス１５１０、１５２０、および１５３０それぞれは、１個、２個、および５個のゼロ要素の長さを表す。従って、ランレングス１５１０は、短いランレングスに分類され、ランレングス１５２０は中間のランレングスに分類され、ランレングス１５３０は長いランレングスに分類される。
【０１１１】
図２０は、フレーム１１０Ｃの閾値マトリクスＣthreshmmvを表す。ここまで、フレームの各マクロブロックについての変位ベクトルの大きさを表すマトリクスのいくつかの要素がゼロに設定されており、その結果、ランレングス１５６０、１５７０、１５８０、および１５９０が得られる。ラン１５６０は、５のレングスを有し、ラン１５７０および１５８０は２のランレングスを有し、ラン１５９０は１のランレングスを有する。従って、ランレングス１５６０は長い範囲に分類され、ランレングス１５７０および１５８０は中間ランレングスに分類され、ランレングス１５９０は短い範囲に分類される。このため、図２０に示すように、長い範囲には１つのランレングス、中間の範囲には２つのランレングス、短い範囲にはたった１つのランレングスがある。
【０１１２】
記述子は、Ｃavgmmv、Ｎsr、Ｎmr、Ｎlrからなる構造を有するように構成される。なお、記述子は、フレームにおける別個の移動オブジェクトの数およびサイズと、フレームにわたるそれらの分散を間接的に表現する。話している頭等の単一の大きなオブジェクトを有するフレームの場合、短いランレングスの数は多い傾向があり、一方サッカーの試合の航空写真等、いくつかの小さなオブジェクトを有するフレームの場合、短いランレングスの数は少なくなる傾向がある。
【０１１３】
図１３を参照して、処理システム９００は、本発明の第２の実施形態の大きさ記述子を作成し、それを使用するよう容易にマッチする。より詳細には、図２１を参照して、プログラミング９２０ａは、システム９００が、ステップ１６０５に示すように、Ｉ／Ｏポート９３０を介して圧縮ビデオビットストリーム１００を受信できるように構成される。プロセッサ９１０は、ステップ１６１０に反映されるように、圧縮ビットストリーム内の適用可能なビットに基づいて、各フレームのマクロブロック当たりの変位ベクトルの大きさを決定する。次に、ステップ１６１５において、プロセッサ９１０は、適用可能なフレームそれぞれについて、変位ベクトルの大きさマトリクスＣmmvを構築する。ステップ１６２０において、適用可能なフレームのマクロブロック当たりの変位ベクトルの大きさ平均Ｃavgmmvは、プロセッサ９１０によって決定される。
【０１１４】
次に、ステップ１６２５において、各マクロブロックの変位ベクトル１１０ｂａ1〜１１０ｂｐ1の大きさは、マクロブロック当たりの大きさ平均Ｃavgmmvと比較され、フレームにわたって、マクロブロック当たりの大きさ平均、すなわち閾値未満の大きさを決定する。ステップ１６３０において、閾値未満の大きさがゼロに設定される。ステップ１６３５に示すように、残余の大きさは保持される。ステップ１６４０において、閾値マトリクスＣthreshmmvが構築される。ステップ１６４０において、プロセッサ９１０が、マトリクス内のゼロの大きさのランレングスを計算する。ステップ１６４５において、プロセッサ９１０がランレングスを分類する。ステップ１６５０において、カテゴリ毎のランレングスの数を計算する。ステップ１６５５において、決定されたマクロブロック当たりの変位の大きさ平均と、各フレームについての各カテゴリ内のランレングスとを使用して、記述子が構築される。次に、プロセッサ９１０は、記述子をデータベース９２０ｂに格納するために、バス９３０を介して記述子をメモリ９２０に配向できる。
【０１１５】
ショット内のフレーム間符号化フレームすべての記述子を計算して、ショット全体の変位ベクトルにおける、マクロブロック当たりの変位ベクトルの大きさ平均Ｃshotmmvを計算することで、ショットの記述子を構築できる。Ｃshotmmvに最も近いＣavgmmvを有するフレームが識別される。代替として、ショットのフレーム間符号化フレームすべてにわたるＣavgmmv値の中央値Ｃmedmmvを計算してもよく、Ｃmedmmvに最も近いＣavgmmvを有するフレームを識別し、その記述子をショット記述子として使用する。さらなる代替として、フレーム間符号化フレームをショットから無作為に識別し、その記述子をショット記述子として使用する。別の代替は、４つの記述子パラメータそれぞれの平均値または中央値を見つけてから、結果得られる４つの記述子パラメータそれぞれの平均値または中央値を使用してショット記述子を形成する。この後者の場合、ショットの任意に選択されたフレームを、平均値または中央値に基づいて識別してもよい。
【０１１６】
図１３および図２２を参照して、プロセッサ９１０は、ステップ１７０５に示すように、圧縮ビデオストリーム１００をショットに分割できる。ステップ１７１０において、ショットの全フレームにわたる、マクロブロック当たりの変位ベクトルの計算された大きさの平均値または中央値Ｃavgmmv計算する。ステップ１７１５において、ショットの各フレームについての大きさ平均が、ショットの大きさの平均値または中央値と比較される。ステップ１７２０に反映されるように、プロセッサ９１０は、該比較に基づいて、いずれのマクロブロック当たりの大きさ平均が、ショット全体のマクロブロック当たりの平均値または中央値と有利に比較されるかを決定する。ステップ１７２５において、マクロブロック当たりの大きさ平均に最も密接にマッチするフレームが、ショットを表すものとして選択される。ステップ１７３０に示すように、その他のフレームは無視される。ここでもまた、プロセッサ９１０は、選択フレームの記述子を、ショット全体の記述子として格納するために、データベース７２０ｂに配向することができる。
【０１１７】
フレームまたはショットの記述子が構築されると、クエリフレームまたはショットＳaと、記述されたフレームまたはショットＳとの間の「距離」Ｄ（Ｓ，Ｓa）を以下のようにして計算できる。
【０１１８】
Ｗtot＝Ｃavgmmv（Ｓa）＋Ｎsr（Ｓa）＋Ｎmr（Ｓa）＋Ｎlr（Ｓa）（６）
【０１１９】
0004618621.tif 000002
【０１２０】
あるいは、上述したように、一度に１つの記述子特徴を使用して、その他の特徴で引き続きサーチを精錬する「縦続」サーチを行うことができる。縦続手順はより低速であるが、時にわずかに高い精度がもたらされる。これら手順は双方とも、抽出およびマッチングの簡易さを保持しつつ、個々の特徴を正規化する。これらのサーチ手順を用いて良好な結果が得られるが、ある実施においては、他のより正式な正規化方法、例えば、ランレングス特徴間の相関を説明するマハラノビス（Mahalanobis）距離を用いるもの等、が有利に使用される場合がある。
【０１２１】
次に、図１３および図２３を参照して、ステップ１８０５において、プロセッサ９１０はプログラミング９２０ａに従って、代替のマッチング技術の１つを使用して、Ｉ／Ｏポート９４０およびバス９３０を介してクエリを受信する。ステップ１８１０において、プロセッサ９１０は、クエリに対する重み付きパラメータＷを決定する。ステップ１８５０において、プロセッサ９１０は記述子をデータベース９２０ｂから検索して、記述子とクエリの間の距離が決定される。ステップ１８２０において、プロセッサ９１０は、記述子とクエリの間の最小距離を識別する。ステップ１８２５において、最小距離の記述子を有するフレームまたはショットが、クエリに対する最適マッチングとして識別される。ステップ１８３０に示すように、その他のフレームは無視される。
【０１２２】
図１３および図２４を参照して、代替のクエリマッチング動作では、ステップ１９０５において、プロセッサ９１０がプログラミング９２０ａに従って、Ｉ／Ｏポート９４０およびバス９３０を介してクエリを受信する。ステップ１９１０において、記述子がデータベース９２０ｂから検索され、適用可能な場合、フレームまたはショットのマクロブロック当たりの大きさ平均が、クエリと比較され、クエリと最も有利にマッチされる大きさ平均をが識別される。ステップ１９１５において、最も有利にマッチする大きさ平均に関連するフレームまたはショットが、さらなる処理のために識別される。ステップ１９２０に示すように、その他のフレームまたはショットは無視される。ステップ１９２５において、プロセッサ９１０は、識別されたフレームまたはショットの１つまたは複数のランレングスカテゴリにおけるランレングスの数が、クエリの要件と有利にマッチするか否かを決定する。ステップ１９３０において、最も密接にマッチするランレングスの数に関連するフレームまたはショット、あるいはランレングスの数は、最も密接にマッチするフレームまたはショットとして識別される。ステップ１９２０において、その他のフレームまたはショットは無視される。従って、マッチするショットのリストを、上述したように、類似性の降順で形成することができる。
【０１２３】
大きさ記述子は、フレーム記述子を計算することにより、ＭＰＥＧ−７テストセット全体のＭＰＥＧ−１ビデオシーケンスに適用されてきている。改良された記述子により、映画または他の番組内の意味論的ショット分類およびマッチングが可能になる。一貫して得られる精度値は、番組内で１／１０〜５／５の範囲である。例えば、項目Ｖ２（ポルトガルのテレビニュース）では、ニュースキャスターをサーチする際に５／５の精度が得られる。しかし、サッカーショットをサーチする場合、精度は１／１０に低下する。なお、サッカーシーケンスでのリコール（recall）は１／２である一方、ニュースキャスターでのリコールは、０．０１未満であることに留意する。テストコンテンツとの結果は、大きさ記述子が、類似時間空間的アクティビティがショットにもマッチング可能であることを示す。同じ番組内で、意味論的クラスが、時間空間的アクティビティの密度および分散に関して、広範に広がっている場合、大きさ記述子は良好に機能する（perform)。スポーツおよびニュースはこのようなコンテンツの良い例であるが、他のコンテンツもこのような索引付けに役立つ。
【０１２４】
複数番組にわたるマッチングは実施可能であるが、番組内のマッチングよりもわずかに成功率が低い。コンテンツのノイズレベルの差が、番組にわたるマッチングの精度にわずかに影響する。さらに、番組内では、フレームの大きさ記述子は意味論的文脈内にあるため、意味論的なマッチングを提供する。番組にわたっての場合、マッチング手順は、より非意味論的な低レベルのマッチングを行う。例えば、クイズショー、ドラマ、およびバスケットボールの試合等を組み合わせたものにわたってのマッチングを試みる場合、クイズショーはドラマとマッチングする際、情報量で負ける（gets overwhelmed by matching form drama)。これは、直接測定されるものが時間空間的特徴であるため、非意味論的には正しい。バスケットボールの試合は、アクティビティの密度がはるかに高いため、クイズまたはドラマによる影響を受けない。クイズショーをそれ自体で索引付ける場合、大きさ記述子は、個人のクローズアップ、３人の競技者全員等の意味論的に同様なカテゴリにフレームを分類することができる。
【０１２５】
ターゲットとする用途が最低予期品質が高いマルチメディアデータベースであるため、大きさ記述子のテストは、ＭＰＥＧ−１ビットレートにも集中する。従って、テストにおいて、フルフレーム速度、すなわち３０フレームまたは２５フレーム／秒がまた使用されている。移動ベクトルの大きさ平均は、ランレングス特徴であるため、フレーム速度およびフレームサイズに対して、正規化しやすい。移動ベクトルプロパティは、ビットレートによってそれほど変化しない。レート制御方策の変更は移動プロパティにあまり影響しない。従って、大きさ記述子は符号化パラメータの変更に対して耐性がある。これは、圧縮ドメイン特徴抽出に重要である。
【０１２６】
大きさ記述子は、映画等の番組内の、および番組にわたっての索引付けに効果的である。これは、抽出およびマッチングが容易な低レベルの記述子であるため、ビデオ索引付けの際に、他の記述子と組み合わせて使用すると有益である。１時間のコンテンツの特徴を、最適化していないコードを有する３３３ＭＨｚのＰＣ上で約１０分で抽出できる。４つのパラメータと絶対距離のみを使用するため、マッチングの複雑さも低い。ある実施では、クラスタ化方策により、現在の複雑さからさらにサーチの複雑さを低減することが可能である。このようなクラスタ化により、ビデオシーケンスのマルチレベルの表現が容易になる。大きさ記述子はフレームベースであるため、ショット、ショットの集合等を記述するよう容易に拡張できる。また、これは、コンテンツベースの処理、インテリジェントマルチメディア提示、監視等、他の用途にも有用である。
【０１２７】
大きさ記述子は低レベルであるとともに単純な記述子であるため、意味論的マッチングは行わない。上述した精度値およびリコール値は、低レベルの記述子に対する基準としてはおそらく強すぎる、厳密な意味論的マッチングに基づく。例えば、基準が、話している頭のみを検索し、ニュースキャスターは検索しないというものである場合、精度は５／５にまでなる。大きさ記述子の目的は主に、続いて補助記述子、例えば色による、または移動等の関連する特徴のより高度な記述子による分類が行われるよう、番組の単純な初期分類を行うことである。しかし、実施によっては、大きさ記述子を最終的な分類として使用してもよい。
【０１２８】
様々なＭＰＥＧ−１オブジェクトを有するショットの大きさ記述子の具体例を、図２９に示す。
【図面の簡単な説明】
【図１】  圧縮ビデオビットストリームを示す。
【図２】  特定フレームのマクロブロックに関連する、図１の圧縮ビットストリームのビットを示す。
【図３】  別のフレームのマクロブロックに関連する、図１の圧縮ビットストリームのビットを示す。
【図４】  １６ｘ１６画素からなるマクロブロックを示す。
【図５】  図１の圧縮ビットストリームで表されるあるフレームのマクロブロックと関連させた画像を示す。
【図６】  図１の圧縮ビットストリームで表されるフレームのマクロブロックについて、マクロブロックビットのセグメント化を示す。
【図７】  図１の圧縮ビットストリームで表される別のフレームのマクロブロックについて、マクロブロックビットのセグメント化を示す。
【図８】  図１の圧縮ビットストリームで表される他のフレームのマクロブロックに関連させた画像、およびクエリフレームのマクロブロックに関連させた画像を示す。
【図９】  本発明による、図１の圧縮ビットストリームで表されるフレームの圧縮複雑マトリクスを示す。
【図１０】  本発明による、図１の圧縮ビットストリームで表される別のフレームの圧縮複雑マトリクスを示す。
【図１１】  本発明による図１０のフレームのランレングスを示す。
【図１２】  本発明による図１の圧縮ビットストリームで表される別のフレームのランレングスを示す。
【図１３】  本発明の実施に利用できる処理システムを示す。
【図１４】  本発明に従って、図１３の処理システムによって行われる動作のフローチャートである。
【図１５】  本発明に従って、図１３の処理システムによってオプションとして行われるさらなる動作のフローチャートである。
【図１６】  本発明に従って、クエリにマッチするフレームまたはショットを識別するため、図１３の処理システムによって行われるさらなる動作のフローチャートである。
【図１７】  ＨＤＴＶの分野において知られているＭＰＥＧ−４オブジェクトのセットを、本発明の第１の実施形態により導出される記述子とともにリストしたテーブルである。
【図１８】  本発明の第２の実施形態により、図１の圧縮ビットストリームで表されたフレームの圧縮複雑マトリクスを示す。
【図１９】  図１８の圧縮複雑マトリクスで表されるフレームのランレングスを示す。
【図２０】  本発明の第２の実施形態による、図１の圧縮ビットストリームで表される他のフレームのランレングスを示す。
【図２１】  本発明の第２の実施形態による、図１３の処理システムによって行われる動作のフローチャートである。
【図２２】  本発明の第２の実施形態による、図１３の処理システムによってオプションとして行われるさらなる動作のフローチャートである。
【図２３】  本発明の第２の実施形態によりフレームまたはショットをクエリとマッチさせるため、図１３の処理システムによって行われる第１のさらなる代替動作のフローチャートである。
【図２４】  本発明の第２の実施形態によりフレームまたはショットをクエリとマッチさせるため、図１３の処理システムによって行われる第２の代替動作のフローチャートである。
【図２５】  ＭＰＥＧ−２形式の空間時間的複雑さの例（テーブル１）を示す。
【図２６】  ＭＰＥＧ−４のオブジェクトに関する本発明による技術を用いた具体例（テーブル２）を示す。
【図２７】  ＭＰＥＧ−４のオブジェクトに関する本発明による技術を用いた第１の段階のマッチングの具体例（テーブル３）を示す。
【図２８】  ＭＰＥＧ−４のオブジェクトに関する本発明による技術を用いた第２の段階のマッチングの具体例（テーブル４）を示す。
【図２９】  ＭＰＥＧ−１オブジェクトを有するショットの大きさ記述子の具体例（テーブル５）を示す。
【符号の説明】
１００  圧縮ビットストリーム、９００  処理システム、９１０  プロセッサ、９２０  メモリ、９３０  バス、９４０  入出力（Ｉ／Ｏ）ポート。
【図１】
0004618621.tif 000003
【図２】
0004618621.tif 000004
【図３】
0004618621.tif 000005
【図４】
0004618621.tif 000006
【図５】
0004618621.tif 000007
【図６】
0004618621.tif 000008
【図７】
0004618621.tif 000009
【図８】
0004618621.tif 000010
【図９】
0004618621.tif 000011
【図１０】
0004618621.tif 000012
【図１１】
0004618621.tif 000013
【図１２】
0004618621.tif 000014
【図１３】
0004618621.tif 000015
【図１４】
0004618621.tif 000016
【図１５】
0004618621.tif 000017
【図１６】
0004618621.tif 000018
【図１７】
0004618621.tif 000019
【図１８】
0004618621.tif 000020
【図１９】
0004618621.tif 000021
【図２０】
0004618621.tif 000022
【図２１】
0004618621.tif 000023
【図２２】
0004618621.tif 000024
【図２３】
0004618621.tif 000025
【図２４】
0004618621.tif 000026
【図２５】
0004618621.tif 000027
【図２６】
0004618621.tif 000028
【図２７】
0004618621.tif 000029
【図２８】
0004618621.tif 000030
【図２９】
0004618621.tif 000031