(57)【要約】      （修正有）【課題】画像および画像群を表現する記述子を提供する。【解決手段】画像を表現及び解析する方法は、１つ又は複数のスケールで、且つ１つ又は複数のカラーチャネルについて画像の複数の記述子を生成することであって、当該記述子は、領域内の色内容及び色相関の情報を取得する、記述子を生成することと、記述子をスケール、カラーチャネル、特徴部の意味、及び領域等の特性に基づいて複数の方法で関連付けることと、画像の類似性を評価するためにこのような画像表現を比較することとを含む。【選択図】  図２Ｂ
2006092559.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つの画像を表現する方法であって、
画像の少なくとも１つの領域について色情報及び／又は色相関情報を取得する複数の副記述子を生成することと、
少なくとも２つの記述子を生成するために、前記副記述子を、対応する特性に応じて関連付けることと
を含む、少なくとも１つの画像を表現する方法。
【請求項２】
少なくとも１つの画像を表現する方法であって、
画像の少なくとも１つの領域について色情報及び色相関情報を取得する１つ又は複数の副記述子を生成することと、
少なくとも２つの記述子を生成するために、副記述子又は副記述子要素を、対応する特性に応じて関連付けることと
を含む、少なくとも１つの画像を表現する方法。
【請求項３】
副記述子は、画像の複数の領域について生成される、請求項１又は２に記載の方法。
【請求項４】
前記領域の各々は、ｎ×ｎ画素のサイズのブロックに対応する請求項３に記載の方法。
【請求項５】
画像の複数の重複しない領域の各々について副記述子を導出することを含む請求項１〜４のいずれか一項に記載の方法。
【請求項６】
前記画像の複数の表現を複数のスケールで生成するために、前記画像を処理することと、
前記複数のスケールについて副記述子を導出することと
を含む、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記処理はダウンサンプリングを含む、請求項６に記載の方法。
【請求項８】
前記ダウンサンプリングは、画素ブロックを平均することを含む請求項７に記載の方法。
【請求項９】
複数のカラーチャネルの各々について前記画像を処理することと、
前記チャネルの各々について副記述子を導出することと
を含む、請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
同一スケールが異なるカラーチャネルに用いられる、請求項６〜８のいずれか一項に従属する請求項９に記載の方法。
【請求項１１】
異なるスケールが異なるチャネルに用いられる、請求項６〜８のいずれか一項に従属する請求項９に記載の方法。
【請求項１２】
副記述子を導出する異なるプロセスが、異なる領域及び／又は異なるスケール及び／又は異なるカラーチャネルに用いられる、請求項１〜１１のいずれか一項に記載の方法。
【請求項１３】
前記複数の副記述子はウェーブレット変換により生成される、請求項１〜１２のいずれか一項に記載の方法。
【請求項１４】
前記複数の副記述子は、ハールウェーブレット変換又はドーブシウェーブレット変換により生成される、請求項１３に記載の方法。
【請求項１５】
或る領域の少なくとも１つの副記述子要素が、非ウェーブレット変換を用いて導出される、請求項１〜１２のいずれか一項に記載の方法。
【請求項１６】
或る領域の少なくとも１つの副記述子要素が、前記領域の画素のサブセットのみを用いて導出される、請求項１〜１２又は１５のいずれか一項に記載の方法。
【請求項１７】
或る領域の複数の副記述子要素の各々又は全てが、前記領域の画素のサブセットのみを用いて導出される、請求項１６に記載の方法。
【請求項１８】
前記副記述子要素を導出するために用いられる計算は、結果として得られる副記述子要素の数が、前記副記述子要素を導出するために用いられる画素数よりも少ないようになっている、請求項１〜１２又は１５〜１７のいずれか一項に記載の方法。
【請求項１９】
記述子要素が、式１〜４又は６〜９又は１４〜１７又はＩ〜ＩＶ又は１８及び１９の形の式、又は同様の式を用いて導出される、請求項１〜１８のいずれか一項に記載の方法。
【請求項２０】
特定の記述子要素を除去することによって副記述子の次元数を下げることを含む、請求項１〜１９のいずれか一項に記載の方法。
【請求項２１】
前記複数の副記述子又は副記述子要素は、色、色相関、カラーチャネル、スケール、領域のうちの１つ又は複数に基づいて関連付けられる、請求項１〜２０のいずれか一項に記載の方法。
【請求項２２】
副記述子又は副記述子要素は、
特性の単一の値について、又は、
単一のスケール、又は低スケール及び高スケール、又は低スケール、中スケール及び高スケール等の特性の値の範囲について、
必要な変更を加えて関連付けられる、請求項１〜２１のいずれか一項に記載の方法。
【請求項２３】
前記副記述子は、ＭＰＥＧ符号化Ｉフレームから復号を行うことなく直接導出される請求項１〜２２のいずれか一項に記載の方法。
【請求項２４】
画像群を表現する方法であって、
請求項１〜２３のいずれか一項に記載の方法を用いて各画像の表現を導出することと、
前記表現を用いて前記画像群を表現することと
を含む、画像群を表現する方法。
【請求項２５】
前記表現の関数を導出して前記画像群を表現することを含む、請求項２４に記載の方法。
【請求項２６】
前記関数は、平均、中央値、算術平均、共分散等の統計測度を含む、請求項２５に記載の方法。
【請求項２７】
請求項１〜２６のいずれか一項に記載の方法を用いて導出される、画像又は画像群の表現。
【請求項２８】
画像及び／又は画像群を比較する方法であって、
請求項２７に記載のそれぞれの表現を比較することを含み、
前記比較は、特性に応じて対応する記述子を比較することを含む
画像及び／又は画像群を比較する方法。
【請求項２９】
類似性を判定するための、請求項２８に記載の方法。
【請求項３０】
記述子の複数の比較を並行して行うことを含む、請求項２８又は２９に記載の方法。
【請求項３１】
記述子の複数の比較を逐次行うことを含む、請求項２８〜３０のいずれか一項に記載の方法。
【請求項３２】
２つ以上の記述子を用いて仮評価を行うことと、
前記仮評価の結果を用いて、追加の記述子に関するさらなる評価を行うべきか否かを判定することと
を含む、請求項３１に記載の方法。
【請求項３３】
異なる評価は、
同一特性の、異なる値の記述子（例えば異なるスケール、カラーチャネルの異なる値、異なる画像領域等）、又は、
（例えば前記画像の異なる特性の類似性に関する情報を導出するための）異なる特性の記述子
に関する、請求項２８〜３２のいずれか一項に記載の方法。
【請求項３４】
スケールを（粗いものから細かいものへ）上げながら連続する評価を行うことを含む請求項３３に記載の方法。
【請求項３５】
（ｉ）輝度から抽出される色内容、
（ｉｉ）輝度から抽出される色相関、
（ｉｉｉ）色差から抽出される色内容、及び
（ｉｖ）色差から抽出される色相関
のうちの１つ又は複数に基づく記述子を用いる、請求項３３又は３４に記載の方法。
【請求項３６】
少なくとも１つの評価に、（ｉ）及び（ｉｉｉ）に基づく記述子が用いられ、
少なくとも１つの、それに続く評価に、（ｉｉ）及び（ｉｖ）に基づく記述子が用いられる
請求項３５に記載の方法。
【請求項３７】
画像シーケンスの一部である画像を比較することを含み、
前記比較の結果は、前記画像間でフレームの切れ目が起こったかどうか、又は、例えばシーンの変化又は照明効果等の事象が起こったかどうかを判定するために用いられる
請求項２８〜３６のいずれか一項に記載の方法。
【請求項３８】
画像の検索に用いられる、請求項２８〜３６のいずれか一項に記載の方法。
【請求項３９】
色差及び輝度を評価することであって、
それによって、ショット遷移と照明効果とを区別するか、又は、
それによって、異なる照明条件下で取り込まれた類似する画像を検索する
色差及び輝度を評価することを含む、請求項３７又は３８に記載の方法。
【請求項４０】
請求項１〜２６のいずれか一項に記載の方法を用いて画像又は画像群を符号化する方法。
【請求項４１】
請求項４０に記載の方法を用いて符号化された画像又は画像シーケンスを復号する方法。
【請求項４２】
請求項４０に記載の方法により符号化されたデータの、例えば伝送、中継又は受信による、使用。
【請求項４３】
請求項１〜２６のいずれか一項に記載の方法により画像又は画像群を表現する装置。
【請求項４４】
請求項２９〜３９のいずれか一項に記載の方法により画像及び／又は画像群を比較する装置。
【請求項４５】
画像データ及び／又は画像記述子を記憶する記憶手段と、前記方法を実行する処理手段とを備える請求項４３又は４４に記載の装置。
【請求項４６】
請求項１〜２６又は２８〜３９のいずれか一項に記載の方法を実行するための、コンピュータプログラム、システム、又はコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の背景］
本発明は、画像を表現する方法及び装置、並びに画像間の類似性を評価する方法及び装置に関する。
【０００２】
R. Lienhart著「Comparison of Automatic Shot Boundary Detection Algorithms」（Proceedings of Image and Video Processing VII 1999, Proc. SPIE 3656-29, pp. 290-301, Jan. 1999）には、ビデオシーケンス中のショット遷移を検出するための方法が提示されている。シーケンス中のフレーム毎に、ＲＧＢ色空間の３次元ヒストグラムを作成する。次に、シーケンス中の連続フレーム間の差を、それぞれのヒストグラム間の差として計算する。ヒストグラム間の差は、ビンに関連する(bin-wise)差の絶対値の和として計算する。次に、所定の固定閾値を上回る距離を探索することによって、ショット遷移を特定する。よって、この方法は、空間的に敏感でない(spatially insensitive)色内容（colour content）情報のみに基づいて、ショット遷移を検出する。したがって、この方法は、空間的配置及び色相関の中に存在する豊富な情報を利用していない。
【０００３】
R. Zabih、J. Miller、K. Mai著「A Feature-Based Algorithm for Detecting and Classifying Scene Breaks」（Proceedings of 1995 3rd ACM International Conference on Multimedia, San Francisco, CA USA, pp. 189-200, 1995）には、ビデオシーケンス中のショット遷移を検出するための異なる方法が提示されている。シーケンス中のフレーム毎に、エッジマップを計算する。次に、第１のフレームには存在するが第２のフレームには存在しないエッジの数と、第２のフレームには存在するが第１のフレームには存在しないエッジの数とに基づいて、シーケンス中の連続フレーム間の差を計算する。このとき、この差の測度の時系列における鋭いピークは、ショット遷移の存在を示す。したがって、この方法は、空間相関情報の一種であるエッジ情報のみに基づいてショット遷移を検出する。この原理は正しいが、この方法は、フレームの色内容の中に存在する豊富な情報を利用していない。さらに、エッジマップの作成プロセスは計算コストが高く、また、フレーム内の最も強い色の切れ目のみを示すことを意図している。さらに、この方法は、動きに極めて敏感である。したがって、著者等は、この欠点に対処するために画像の位置合わせ技法の使用を提案しているが、こうしたプロセスは計算コストが高い。
【０００４】
A. Dailanas、R. B. Allen、P. England著「Comparison of Automatic Video Segmentation Algorithms」（SPIE Integration Issues in Large Commercial Media Delivery Systems, vol. 2615, pp. 2-16, Oct. 1995）には、ビデオシーケンス中のショット遷移を検出するための別の方法が提示されている。シーケンス中の連続フレーム間の差を、画素に関連する(pixel-wise)差の絶対値の和として計算する。次に、所定の固定閾値を上回る距離を探索することによって、ショット遷移を特定する。したがって、この方法は、空間的に敏感な(spatially sensitive)色内容情報のみに基づいてショット遷移を検出する。この原理は正しいが、この方法は、空間的な色相関の中に存在する豊富な情報を利用していない。さらに、このようなビデオの単純な処理は、ノイズ及び動きに対する高い敏感性をもたらす。この動きに対する敏感性の問題には、動き補償アルゴリズムにより対処することもできるが、こうしたプロセスは計算コストが高い。
【０００５】
W. Xiongの米国特許出願公開第２００３／００９１２３５号明細書「Shot Boundary Detection」（２００３年５月１５日公開）には、異なるタイプの情報の組み合わせに基づいてショット遷移を検出するための方法が提示されている。この方法は、２フレーム間でブロックに基づく差を計算すること、及び、この差が固定閾値を越える場合、ショット遷移候補を宣言することを含む。この場合、ショット遷移は、２フレーム間の色及び／又はエッジの差も固定閾値を越えることを要求することによって検証する。ブロックに基づく差を計算するために、フレームをブロックに分割し、ブロック平均を計算する。次に、対応するブロック間の差を閾値処理して、２つのブロックが類似しているか異なっているかを判定し、２フレーム間で異なるブロックの数を閾値処理して、２つのフレームが類似しているか異なっているかを判定する。色の差は、ビンに関連する差の絶対値の和であり、エッジの差は、エッジ強度及びエッジ方向の情報を取得するエッジヒストグラムを用いる。
【０００６】
Y. Nakajima、M. Sugano、H. Yanagiharaの米国特許出願公開第２００４／００９１０４４号明細書「Picture Searching Apparatus」（KDDI CORPORATION（日本）、２００４年５月１３日公開）には、（ａ）画像間の相関、（ｂ）サブサンプリング画像間の相関、（ｃ）画像間の動き、及び（ｄ）サブサンプリング画像間の動き、に基づいてショット遷移を検出するための方法が提示されている。ここでは、画像間及びサブサンプリング画像間の相関を、画素に関連する差又はヒストグラムの差として測定し、画像間及びサブサンプリング画像間の動きを、様々な動きベクトルの差に基づいて測定する。
【０００７】
H. Jafarkhani、B. Shahrarayの米国特許第６，５４２，６１９号明細書「Method for Analyzing Video」（AT&T CORP.（アメリカ）、２００３年４月１日交付）には、ショット遷移の検出方法が提示されており、この方法は、ビデオフレームの２つの１次元射影、すなわち行射影及び列射影を作成することと、各射影に対してウェーブレット変換を実行し、高周波成分（すなわちウェーブレット係数）のみを保持することと、各変換の高周波成分の自己相関をとることとを含む。一連のビデオフレームについて、結果として得られた自己相関係数の時間曲線が所定の最大値を示すとき、ショット遷移を指示する。したがって、この方法は、ウェーブレット変換によって提供される空間的に敏感な色内容及び色相関の情報を使用するが、この情報は、フレームではなくフレーム射影に関連するものであり、大きな情報損失を生じる。
【０００８】
C. E. Jacobs、A. Finkelstein、D. H. Salesin著「Fast Multiresolution Image Querying」（Proceedings of 1995 ACM SIGGRAPH Conference, Los Angeles CA, USA, Aug. 9-11, pp. 277-286, 1995）には、所与の画像に類似している画像の検索方法が提示されている。この方法を用いる場合、画像を先ずハール（Haar）ウェーブレット分解で表現する。次に、この分解を打ち切る(truncate)、すなわち、スケーリング関数の係数（平均強度）とごく少数の最大振幅のウェーブレット係数のみを保持する。次に、打ち切った分解を量子化する、すなわち、ウェーブレット係数の符号のみを保持する。したがって、画像検索目的で画像を特徴付ける単一の画像記述子を形成する。
【０００９】
Z.-Y. Zhuang、C.-T. Hsu、H.-Y. Chen、M. Ouhyoung、J.-L. Wu著「Efficient Multiresolution Scene Change detection by Wavelet Transformation」（Proceedings of 1997 IEEE International Conference on Consumer Electronics ICCE '97, Taipei, Taiwan, Jun. 11-13, pp. 250-251, 1997）には、「Fast Multiresolution Image Querying」に記載されているのと同じ方法でビデオフレームを特徴付けしていくショット遷移の検出方法が提案されている。「Fast Multiresolusion Image Querying」の方法と「Efficient Multiresolution Scene Change detection by Wavelet Transformation」の方法の違いは、後者の方法を用いる場合、フレームの周辺を廃棄し、フレームをその中心部分のみに縮小することである。このような手法は、大きな情報損失につながり、ビデオ中に大きな動きが存在する場合、誤ったビデオの分割及び／又は大きな過分割を生じる可能性がある。
【００１０】
上述の方法の両方に共通する欠陥は、ごく少数の最大振幅の係数のみを保持することによってウェーブレット分解を効率的に打ち切ることができるという仮定である。これに関連して(to put this in context)、画像平面のマルチスケールウェーブレット分解を１２８×１２８画素から開始して２×２画素まで行うと、１６３８３個のウェーブレット係数が生じる。当業者には承知の通り、この系列を振幅に基づいてごく少数の係数、例えば著者等が示唆するように最大振幅を有する４０個又は６０個の係数に打ち切る場合、いくつかの問題を挙げれば、結果として、ノイズの影響を非常に受けやすく、画像検索及びビデオ分割の場合に部分遮蔽の影響を受けやすく、且つ、ビデオ分割の場合に高いビデオの動き及びショット内の照明効果の影響を受けやすい記述子が生じる。符号のみを保持することによる打ち切り系列の量子化は、問題をさらに大きくする。
【００１１】
これらの方法に伴う別の重要な問題は、ハールウェーブレット分解の係数に付随する意味情報を利用していないことである。こうした意味情報には、係数が表現する特定の色情報、例えばＲＧＢのＲ又はＹＣｂＣｒのＹ、係数が存在する特定の画像スケール、例えば、細部を取得する高い画像スケールの係数なのか、粗い画像情報を取得する低い画像スケールの係数なのか、等がある。
【００１２】
本明細書では、例えば、所与の画像に類似している一組の画像から画像を検索するため、又はデジタルビデオ中のフレームの切れ目（例えばショット遷移又は照明及び他の効果）を検出するために、画像間の類似性を評価する方法を記載する。この方法は、空間的に敏感な色内容及び色相関の情報を１つ又は複数の画像スケールで、且つ１つ又は複数の画像チャネルにわたって取得する画像記述子の抽出と、それに続く、意味内容で区別される１つではなく複数の記述子における記述子の組み合わせと、上記意味内容を効果的に利用する複数の決定の枠組みにおけるこれらの記述子の使用とに依拠する。したがって、以前の方法とは異なり、画像間に複雑な関係を確立することが可能であり、例えば、２つの画像は同一シーンを表すが、一方に極めて大きな遮蔽（例えばカメラから歩いて入ってきた人物）があること、又は、２つの画像は同一シーンを表すが、異なる照明条件下で取り込まれたこと、又は、２つのフレームは同一ショットに属するが、全体的な照明効果のために非常に異なって見えることを確認することが可能である。
【００１３】
［発明の概要］
本発明の態様を添付の特許請求の範囲に記載する。
【００１４】
本発明の一態様によれば、画像の１つ又は複数の領域について色情報及び／又は色相関情報を取得する副記述子（sub-descriptors）をその特性（例えば、領域、スケール、色、色相関、カラーチャネル等）に基づいて関連付け、２つ以上の記述子を形成する。
【００１５】
副記述子は、色及び／又は色相関の情報を同様に取得する要素を有してもよい。その場合、副記述子要素も副記述子を構成し得る。例えば、ハールウェーブレット変換に関する或る画像領域の４つの測定値ＬＬ、ＨＬ、ＬＨ及びＨＨがともに、その画像領域の副記述子を形成する。しかし、ＬＬのみ又はＨＨのみを単独で副記述子と見なしてもよい。
【００１６】
「副記述子を関連付ける」ステップは、副記述子をその構成要素に分割すること、及び、当該要素を対応する特性に応じてグループ分け又は関連付けすることを含み得る。
【００１７】
本発明の実施形態を以下に、添付図面を参照して記載する。
【００１８】
デジタル画像Ｆｉ（ｘ，ｙ）を検討する。ここで、（ｘ，ｙ）は空間座標を表し、ｘ＝０．．．Ｍ−１及びｙ＝０．．．Ｎ−１である。本発明の一実施形態において、Ｆｉは色空間ＹＣｂＣｒで表されるが、これに制限されるものではなく、本発明の実施形態は、いかなるチャネル数のいかなる色空間にも適用可能である。本発明の一実施形態において、Ｆｉの空間解像度は７２０×５７６画素である、すなわち、Ｍ＝７２０及びＮ＝５７６であるが、これに限定されるものではなく、本発明の実施形態は、いかなる空間解像度にも適用可能である。本発明の一実施形態において、記述子を抽出する最高解像度として６４×６４画素を選択するが、これに限定されるものではなく、本発明の実施形態は他の解像度にも適用可能である。したがって、Ｆｉをリサンプリングして、６４×６４画素の画像Ｆｉ（６４×６４）を得る。本発明の一実施形態において、このリサンプリングプロセスは、図１に示すような単純なブロック平均プロセスであるが、リサンプリング機構の選択は限定されない。より具体的に言えば、図１は、Ｙチャネルのブロック平均リサンプリングプロセスを示すが、これに限定されるものではなく、このプロセスは、いかなる色空間のいかなるチャネルにも用いることができる。本発明の別の実施形態において、記述子を抽出する最高スケールはＦｉの解像度に一致し、最初のリサンプリングは必要とされない。
【００１９】
図２は、本発明の一実施形態における、このスケールの記述子の計算を示す。より具体的には、図２は、Ｙチャネルの記述子の計算を示すが、これに限定されるものではなく、同様の手法を全てのカラーチャネルに適用する。図２Ａにおいて、２×２の窓を画像の左上の角に適用する。この窓は局所近傍を指定する。この近傍の画素ＦＹｉ（６４×６４）（０，０），ＦＹｉ（６４×６４）（１，０），ＦＹｉ（６４×６４）（０，１）及びＦＹｉ（６４×６４）（１，１）について、２次元ハール変換係数ＬＬ，ＨＬ，ＬＨ及びＨＨを次のように計算することができる。
【００２０】
【数１】
2006092559.tif 000003
【００２１】
上記の式において、ＬＬは色内容情報を取得し、ＨＬ、ＬＨ及びＨＨは色相関情報を取得する。当業者は、式（１）〜（４）を変更して、例えば、先ず横方向の計算を行い、次に縦方向の計算を行うことによって、必要な計算の数を減らしてもよいことを理解するであろう。式（１）〜（４）によるハール係数、又はその最適化を、分母の値を２ではなく４として計算することも一般的である。
【００２２】
ＦＹｉ（６４×６４）の記述子をＶＹｉ（６４×６４）とすると、これらの値は、次のように記述子として書き表すことができる。
【００２３】
【数２】
2006092559.tif 000004
【００２４】
次に、図２Ｂに示すように、２×２の窓を２画素右にスライドさせ、画素ＦＹｉ（６４×６４）（２，０），ＦＹｉ（６４×６４）（３，０），ＦＹｉ（６４×６４）（２，１）及びＦＹｉ（６４×６４）（３，１）を含む新たな近傍を形成する。ハール変換係数ＬＬ，ＨＬ，ＬＨ，及びＨＨを再び、新たな画素値について計算し、その後、記述子位置ＶＹｉ（６４×６４）（５）〜ＶＹｉ（６４×６４）（８）に格納する。図２Ｃ及び図２Ｄに示すように、一組の行について計算が全て完了すると、スライド窓を２画素下に移動させ、左から右へのスライドを再び開始し、画像全体を処理し終えるまで続ける。これにより、画像の空間的に敏感な色内容及び色相関をＹ平面について６４×６４画素のスケールで取得する記述子ＶＹｉ（６４×６４）の計算が完了する。
【００２５】
本発明の実施形態は、空間的に敏感な色内容及び色相関の情報を取得する記述子の計算に関する。したがって、
【００２６】
上記の説明において、ＬＬ，ＨＬ，ＬＨ及びＨＨの式（１）〜（４）は、近傍内で行うことができる測定の一例に過ぎず、一実施形態を示すに過ぎない。ハール変換は、ウェーブレット変換の単純な例であり、信号の多重解像度の時間周波数表現を生じる。本発明の別の実施形態は、ハール変換ではなく、別の同様であるが、より複雑なウェーブレット変換、すなわち２次元ドーブシ（Daubechies'）ウェーブレット変換を用いる。上記の変換とは異なり、この変換は、スライドステップ（sliding step）が２画素である４×４の窓において動作する、すなわち、結果として得られる近傍は重なり合う。図３にこれを示す。図３Ａにおいて、４×４の窓を画像の左上の角に適用する。この窓は局所近傍を指定する。この近傍の画素について、以下の記述子要素を計算する。
【００２７】
【数３】
2006092559.tif 000005
【数４】
2006092559.tif 000006
【数５】
2006092559.tif 000007
【数６】
2006092559.tif 000008
【００２８】
ここで、
【００２９】
【数７】
2006092559.tif 000009
【００３０】
である。
【００３１】
上記の式において、ａ１はスケーリング関数の係数であり、色内容情報を取得し、ａ２、ａ３及びａ４はウェーブレット変換の係数であり、色相関情報を取得する。当業者は、式（６）〜（１３）を変更して、必要な計算の数を減らしてもよいことを理解するであろう。これらの値は、一連の式（lines of equation）（５）に沿って記述子ＶＹｉ（６４×６４）として書き表すことができ、次に、図３Ｂに示すように、４×４の窓を２画素右にスライドさせて新たな近傍を形成し、新たな画素値について記述子要素を再び計算し、以下同様の操作を行う。図３Ｃに示すように、スライド窓が画像の右端に達すると、完全な４×４の近傍を形成するのに十分な画素がなくなる。この問題はいくつかの方法で対処することができる。これらの方法の１つは、図３Ｃに示すように、データが鏡映されていると仮定することである。もう１つの手法は、データが周期的であると仮定することである。他の手法も存在する。これと同じ問題が、スライド窓が画像の下端に達するときにも生じ、上記のように対処することができる。図３Ｄに示すように、一組の行の計算が全て完了すると、スライド窓を２画素下へ移動させ、左から右へのスライドを再び開始し、画像全体を処理し終えるまで続ける。
【００３２】
上記の説明では、ウェーブレット変換を使用して記述子を計算する。代替的な実施形態は、色内容及び色相関の記述子要素を計算するための他のプロセスに依拠してもよい。例えば、代替的な実施形態は、色内容及び色相関の記述子要素を生成するが、上記のプロセスとは異なり、画素近傍毎に計算する記述子要素の数は近傍の画素数よりも少なく、格納及び処理により便利な小さな記述子を生じるが、依然として画像を空間的に均一にカバーする記述子抽出プロセスに依拠してもよい。さらに別の代替的な実施形態は、上記のプロセスとは異なり、近傍画素のサブセットのみに基づいて近傍の記述子要素を計算し、速度を大幅に改善する記述子抽出プロセスに依拠してもよい。
【００３３】
例えば、図２Ａに示すような局所近傍の画素ＦＹｉ（６４×６４）（０，０），ＦＹｉ（６４×６４）（１，０），ＦＹｉ（６４×６４）（０，１）及びＦＹｉ（６４×６４）（１，１）について、本発明の代替的な実施形態は、記述子要素χ１〜χ４を次のように計算する。
【００３４】
【数８】
2006092559.tif 000010
【００３５】
したがって、局所画素平均を表す要素χ１は色内容情報を取得し、要素χ２、χ３及びχ４はそれぞれ、或る画素と別の画素の差を表し、色相関情報を取得する。これらの値は、一連の式（５）に沿って記述子ＶＹｉ（６４×６４）として書き表すことができ、次に、図２Ｂに示すように、２×２の窓を２画素右にスライドさせて新たな近傍を形成し、新たな画素値について記述子要素を再び計算し、以下同様の操作を行う。
【００３６】
本発明のさらに別の代替的な実施形態は、式（１４）〜（１７）を以下に示す式（Ｉ）〜（ＩＶ）で置き換える。
【００３７】
【数９】
2006092559.tif 000011
【００３８】
上に示す式において、φ１は色内容情報を取得し、φ２〜φ４は色相関情報を取得する。
【００３９】
本発明のさらに別の代替的な実施形態は、式（１４）〜（１７）を以下に示す式（１８）及び（１９）で置き換える。
【００４０】
【数１０】
2006092559.tif 000012
【００４１】
上に示す式において、ψ１は色内容情報を取得し、ψ２は色相関情報を取得する。
【００４２】
さらに、上記の説明及び図は、２×２画素及び４×４画素のサイズのスライド近傍窓を検討するが、これに制限されるものではない。代替的な実施形態は、例えば、所与の計算に関する要求又は近傍測定プロセス自体に合わせて、任意のサイズ及び／又は幾何形状及び／又はスライドステップを近傍窓に指定することができる。
【００４３】
上記の説明では、ＦＹｉ（６４×６４）の全ての位置で同一の近傍窓及び記述子抽出プロセスを用いる。代替的な実施態様では、そうである必要はない。代替的な実施形態は、画像中の異なる位置で異なる近傍パラメータ及び／又は記述子抽出プロセスを使用してもよい。例えば、本発明の代替的な実施形態は、式（１）〜（４）のもの又は式（１４）〜（１７）のものような速い記述子抽出プロセスを画像の周辺に用い、式（６）〜（９）のもののような遅いがより強力な記述子抽出プロセスを画像の中心に用いる。
【００４４】
次に、ＦＹｉ（６４×６４）を新たなより低いスケールにリサンプリングする。一実施形態において、この新たなスケールは３２×３２画素である。次に、６４×６４の画像の場合と全く同じ方法で新たな記述子ＶＹｉ（３２×３２）を計算する。なお、このリサンプリングは実際には計算を必要としない場合もあり得る。式（１）に見られるように、この新たな画素値は、ＬＬ値として以前に計算し、ＶＹｉ（６４×６４）（１），ＶＹｉ（６４×６４）（５），ＶＹｉ（６４×６４）（９），．．．，ＶＹｉ（６４×６４）（４０９３）に格納している。したがって、一実施形態では、記述子ＶＹｉ（６４×６４），ＶＹｉ（３２×３２），ＶＹｉ（１６×１６），ＶＹｉ（８×８），ＶＹｉ（４×４），及びＶＹｉ（２×２）を計算する。
【００４５】
本明細書において概要を説明する本発明の実施形態は、画像Ｆｉの１つ又は複数のスケールで記述子を抽出することを含む。したがって、
【００４６】
上記の説明において、最も細かい又は最大又は最高スケール、最も粗い又は最小又は最低スケール、スケールの数及びスケール間の関係は、本発明の可能な一実施形態を示すに過ぎず、代替的な実施形態は、例えばシステムの計算能力に合うように、異なるそのようなパラメータを使用してもよい。
【００４７】
本発明の一実施形態では、以降の処理を行う前に、これらのスケールに固有の記述子から特定の要素を除去する。本発明の一実施形態では、２ｂ×２ｂ、２ｂ−１×２ｂ−１、２ｂ−２×２ｂ−２等、例えば、６４×６４、３２×３２、１６×１６等のスケールでの式（１）〜（４）すなわちハール変換において概要を説明した記述子抽出プロセスの場合、ＶＹｉのＬＬ要素を、最低スケールのＬＬ要素を除いて全て除去してもよい。これは、２ｂ−ｋ×２ｂ−ｋのスケールのＬＬ要素を、２ｂ−ｋ−１×２ｂ−ｋ−１のスケールのＬＬ値、並びに２ｂ−ｋ×２ｂ−ｋのスケールのＨＬ要素、ＬＨ要素、及びＨＨ要素から直接計算できるためである。なお、この特性は常に当てはまるわけではない。例えば、２ｂ×２ｂ、２ｂ−２×２ｂ−２、２ｂ−４×２ｂ−４等、例えば、６４×６４、１６×１６、４×４等のスケールで記述子を計算する場合には当てはまらない。また、記述子抽出プロセスの一部としてＬＬ要素、ＨＬ要素、ＬＨ要素及びＨＨ要素のサブセットのみを計算する場合には当てはまらない。
【００４８】
同等の特性がドーブシウェーブレット変換に当てはまる。すなわち、２ｂ×２ｂ、２ｂ−１×２ｂ−１、２ｂ−２×２ｂ−２等、例えば、６４×６４、３２×３２、１６×１６等のスケールでのドーブシウェーブレット変換に対する本発明の一実施形態において、ＶＹｉのａ１要素を、最低スケールのａ１要素を除いて全て除去してもよい。
【００４９】
同等の特性が式（１４）〜（１７）の変換に当てはまる。すなわち、本発明の一実施形態において、２ｂ×２ｂ、２ｂ−１×２ｂ−１、２ｂ−２×２ｂ−２等、例えば、６４×６４、３２×３２、１６×１６等のスケールでのその変換について、ＶＹｉのχ１要素を、最低スケールのχ１要素を除いて全て除去してもよい。同一の特性が、式（Ｉ）〜（ＩＶ）の変換にも当てはまる。
【００５０】
同一の記述子抽出プロセスをＦｉのＣｂチャネル及びＣｒチャネルに適用すると、記述子ＶＣｂｉ（６４×６４），．．．，ＶＣｂｉ（２×２）及びＶＣｒｉ（６４×６４），．．．，ＶＣｒｉ（２×２）が得られる。これらのスケールに固有でチャネルに固有の記述子は、全体で、画像の空間的に敏感な色内容及び色相関の情報を複数のスケールで、且つ複数のチャネルにわたって取得する。
【００５１】
上記の説明において、ＦｉはＹＣｂＣｒ色空間にあると仮定し、記述子の抽出に全てのチャネルを用いる。代替的な実施態様は、記述子を計算する前に画像を新たな色空間で表現してもよいし、かつ／又は記述子の計算に色平面のサブセットのみを使用してもよい。
【００５２】
上記の説明では、Ｆｉの異なるカラーチャネルにわたる記述子を同一スケールで計算する。代替的な実施態様では、そうである必要はない。例えば、本発明の代替的な実施形態はＹチャネルの記述子を、Ｃｂ及び／又はＣｒチャネルの記述子よりも多いスケールで、及び／又はそれとは異なるスケールで計算する。このような微調整により、特定の画像又はビデオ素材により良く適合して、性能を高めることができる。
【００５３】
上記の説明では、Ｆｉの全てのカラーチャネルに同一の近傍窓及び記述子抽出プロセスを用いる。代替的な実施態様では、そうである必要はない。代替的な実施形態は、チャネル毎に異なる近傍パラメータ及び／又は記述子抽出プロセスを使用してもよい。例えば、本発明の代替的な実施形態は、速い記述子抽出プロセスをＣｂチャネル及びＣｒチャネルに用い、遅いがより強力な記述子抽出プロセスをＹチャネルに用いる。このような微調整により、特定の画像又はビデオ素材により良く適合して、システムの性能を高めることができる。
【００５４】
本発明の一実施形態では、記述子要素の一部又は全てを、整数部と小数部を持つ実数で表現する。本発明の別の実施形態では、記述子要素の一部又は全てを、例えば小数部を切り捨てるか又は切り上げる(round)ことによって、整数形式で表現する。本発明のさらに別の実施形態では、記述子要素の一部又は全てを、スケーリングによって整数形式で表現する。例えば、式（１）〜（４）は、小数部が３つの値、すなわち、．２５、．５０及び．７５しか取り得ない実数を生成する。したがって、記述子要素に４の値を掛けることによって、情報を全く損失せずに整数表現が得られる。本発明のさらに別の実施形態では、記述子要素の一部又は全てを、何らかの方法で整数形式で表現し、その後、例えば３ビット又は４ビット長の短い値に量子化する。
【００５５】
したがって、本発明の一実施形態では、画像Ｆｉをその記述子ＶＣ１ｉ（Ｃ１ＳＣｑ），．．．，ＶＣ１ｉ（Ｃ１ＳＣ１），ＶＣ２ｉ（Ｃ２ＳＣｑ），．．．，ＶＣ２ｉ（Ｃ２ＳＣ１），．．．，ＶＣｐｉ（ＣｐＳＣｑ），．．．，ＶＣｐｉ（ＣｐＳＣ１）で表現する。ここで、Ｃ１，Ｃ２，．．．，ＣｐはＦｉの第１、第２及び第ｐのカラーチャネルであり、Ｃ１ＳＣｑはチャネルＣ１の最高の記述子スケールであり、Ｃ１ＳＣ１はチャネルＣ１の最低の記述子スケールであり、Ｃ２ＳＣｑはチャネルＣ２の最高の記述子スケールであり、Ｃ２ＳＣ１はチャネルＣ２の最低の記述子スケールであり、以下同様である。これらのスケールに固有でチャネルに固有の記述子は、全体で、画像の空間的に敏感な色内容及び色相関の情報を複数のスケール（好ましくは２つ以上）で、且つ複数のチャネル（好ましくは２つ以上）にわたって取得する。
【００５６】
従来技術において一般的な手法と同様に、画像Ｆｉのこれらの記述子をすべて融合すなわち連結させて、記述子Ｖｊ又は画像Ｆｊとの比較のために１つの記述子Ｖｉにすると、比較速度及びＦｉとＦｊの関係の理解の両方に関して性能が非最適になる可能性がある。
【００５７】
本発明の一実施形態は、スケールに固有でチャネルに固有の記述子を融合させて、異なるスケールを取得する少なくとも２つの記述子にすることを特徴とする。例えば、６つの異なるスケールの、スケールに固有でチャネルに固有の記述子の場合、本発明の一実施形態は、同一の６つのスケールで、スケールに固有なマルチチャネル記述子を生成する。別の実施形態は、１つが低スケールでもう１つが高スケールの、２つのスケール指向性のマルチチャネル記述子を生成し、さらに別の実施形態は、１つが低スケールで、１つが中スケールで、もう１つが高スケールの、３つのスケール指向性のマルチチャネル記述子を生成する。本発明の好ましい実施形態では、記述子を実際に、複数のチャネルにわたって計算し、融合させてスケール指向性の記述子にするが、代替的な実施形態は、単一のチャネルについてのみ記述子を計算し、それらを融合させてスケール指向性の記述子にする。
【００５８】
前の段落の文章に沿った本発明の一実施形態を図４に示す。ステップ４１００において、上記で説明したように、スケールに固有でチャネルに固有の記述子を抽出する。ステップ４２５０において、これらの記述子を融合させて、スケール指向性でマルチチャネルの記述子Ｖｉ（ＳＣＱ），．．．，Ｖｉ（ＳＣＡ）の組にする。ここで、ＳＣＡ及びＳＣＱはそれぞれ最低の記述子スケール及び最高の記述子スケールである。ステップ４３００において、現在のスケールＣ＿ＳＣを最低のスケールＳＣＡに設定する。ステップ４４００において、現在のスケールＣ＿ＳＣの記述子Ｖｉ（Ｃ＿ＳＣ）及びＶｊ（Ｃ＿ＳＣ）のみを用いて、画像Ｆｉと画像Ｆｊとの類似度（similarity measure）Ｄｊ，ｉ（Ｃ＿ＳＣ）を計算する。ステップ４５００において、類似度を用いて、２つの画像の類似性又は非類似性に関する仮決定を行う。ステップ４６００において、類似度及び／又は仮決定を調査して、より高いスケールでの処理が望ましいかどうかを判定する。そのような処理が望ましくないと決定された場合、プロセスはステップ４９００に進み、２つの画像の類似性又は非類似性に関する最終決定を行う。そうでない場合、プロセスはステップ４７００に進み、処理すべきより高いスケールの記述子が残っているかどうかを調べる。より高いスケールの記述子が利用可能である場合、プロセスはステップ４８００に進んで現在のスケールＣ＿ＳＣを上げ、次にステップ４４００に進み、新たなスケールで新たな類似度を計算し、以下同様の操作を行う。一方で、より高いスケールの記述子が利用可能でない場合、プロセスはステップ４９００に進み、２つの画像の類似性又は非類似性に関する最終決定を行う。
【００５９】
図４に示すようなスケール指向性の逐次構成の目的は、２つの画像間の類似性又は非類似性を可能な限り速く、可能な限り少ない計算で確認することである。したがって、そのような方式は、利用可能な記述子をすべて融合させて１つの記述子にする方式と比較して、システムの速度を高めることができる。
【００６０】
次に、このプロセスの様々なステップをより詳しく検討する。ステップ４４００において、類似度の計算には多くのオプションがある。例えば、本発明の一実施形態において、それぞれｎ個の要素からなる２つの記述子Ｖｉ及びＶｊの間のＬ１距離は、次式により与えられる類似度として計算することができる。
【００６１】
【数１１】
2006092559.tif 000013
【００６２】
本明細書に概要を説明する発明の実施形態は、上記記述子を使用して、画像間の少なくとも２つの値を含む１つ又は複数の類似度を計算することに関する。したがって、
【００６３】
記述子の距離を計算するための式（２０）のＬ１距離は、本発明の可能な一実施態様に関連するに過ぎない。代替的な実施態様は、式（２０）を、Ｌ２距離を計算する次式（２１）で置き換える。
【００６４】
【数１２】
2006092559.tif 000014
【００６５】
このような様々な距離メトリックが関連文献に記載されている。
【００６６】
さらに、代替的な実施態様は、式（２０）を次式（２２）で置き換える。この式（２２）は、重み付きＬ１距離を計算する。
【００６７】
【数１３】
2006092559.tif 000015
【００６８】
ここで、ｗ（ｌ）はｌ番目の記述子要素の重み係数である。さらに、重みの適用はまた、式（２１）のＬ２距離、又は文献に記載されている任意の他の適切な距離メトリックとともに用いてもよい。
【００６９】
類似度の処理には多くのオプションがある。本発明の一実施形態では、ステップ４５００において、類似度Ｄｊ，ｉに閾値処理関数を適用する。すなわち、閾値ｔｈｒについて、
【００７０】
【数１４】
2006092559.tif 000016
【００７１】
である場合、２つの画像は大きく異なるものと見なし、ステップ４５００において「非類似」の仮決定を行う。これに基づいて、ステップ４６００は、さらなる処理が必要ないと決定し、ステップ４９００においてこの仮決定を最終決定とする（finalise）。一方、ステップ４５００において（２３）の関係が満たされない場合、このステップにおいて、「類似」の仮決定を行う。これに基づいて、ステップ４６００は、さらなる処理が望ましいと決定する。より高いスケールの記述子が利用可能である場合、プロセスはステップ４４００にループバックする。そうでない場合、ステップ４９００において「類似」の仮決定を最終決定とする。
【００７２】
本明細書に概要を説明する発明の実施形態は、少なくとも２つの値を含む上記類似度を使用して、画像間の類似性又は非類似性を確認することに及ぶ。したがって、
【００７３】
本発明の代替的な実施形態において、
【００７４】
【数１５】
2006092559.tif 000017
【００７５】
である場合、２つの画像は類似しているものと見なし、ステップ４５００において「類似」の仮決定を行う。これに基づいて、ステップ４６００は、さらなる処理が必要ないと決定し、ステップ４９００においてこの仮決定を最終決定とする。一方、ステップ４５００において（２４）の関係が満たされない場合、このステップにおいて「非類似」の仮決定を行う。これに基づいて、ステップ４６００は、さらなる処理が望ましいと決定する。より高いスケールの記述子が利用可能である場合、プロセスはステップ４４００にループバックする。そうでない場合、ステップ４９００において「非類似」の仮決定を最終決定とする。
【００７６】
提案する発明のさらに別の実施形態は、２つの閾値ｔｈｒ１及びｔｈｒ２を用いる。ここで、ｔｈｒ１＜ｔｈｒ２である。すると、
【００７７】
【数１６】
2006092559.tif 000018
【００７８】
である場合、２つの画像は類似しているものと見なし、ステップ４５００において「類似」の仮決定を行う。これに基づいて、ステップ４６００は、さらなる処理が必要ないと決定し、ステップ４９００においてこの仮決定を最終決定とする。一方、ステップ４５００において（２５）の関係が満たされない場合、このステップにおいて「非類似」の仮決定を行う。次に、ステップ４６００において、
【００７９】
【数１７】
2006092559.tif 000019
【００８０】
である場合、ステップ４６００は、さらなる処理が必要ないと決定し、ステップ４９００においてこの仮決定を最終決定とする。そうでない場合、ステップ４６００は、さらなる処理が望ましいと決定する。より高いスケールの記述子が利用可能である場合、プロセスはステップ４４００にループバックする。そうでない場合、ステップ４９００において「非類似」の仮決定を最終決定とするか、又は別法として、ステップ４９００において、新たな「おそらく」という決定を生じる。この「おそらく」という決定は、全ての記述子スケールを使い果たした後で確信の持てる決定に至らなかったことを示す。
【００８１】
ステップ４９００において行われる決定の意味は、特定の実施態様に依存する。
【００８２】
本発明の一実施形態において、Ｆｉ及びＦｊは時間順の画像である。例えば、これらはビデオＦｚのフレームであり、ＦｊとＦｉの間にフレームの切れ目（例えばショット遷移又は照明効果等）が存在するかどうかを確かめることを目的とする。その場合、ステップ４９００における決定は、ＦｊとＦｉの類似度がそのようなフレームの切れ目を示すかどうかとなる。このようなシステムは、ビデオを分割する目的で用いられることになる。
【００８３】
本発明の別の実施形態において、Ｆｊ及びＦｉは時間の順序がない個別の画像である。例えば、Ｆｊは一組の画像Ｆｚの画像であり、ＦｉはＦｚ内部又は外部の別の画像であり、Ｆｚ中の、Ｆｉに類似している画像を見出すことを目的とする。その場合、ステップ４９００の決定は、ＦｊとＦｉの類似度が、それらの画像が類似していることを示すかどうかとなる。このようなシステムは、問い合わせによる画像の検索に、又はデータベース中の画像の分類に用いられる。
【００８４】
本発明の一実施形態において、ステップ４４００の記述子Ｖｉ及びＶｊの一方又は両方は画像ではなく画像群を表す。
【００８５】
例えば、本発明の一実施形態において、Ｖｊは、画像クラスタＦｊを形成する画像Ｆｊ１，Ｆｊ２，．．．，Ｆｊｇの記述子Ｖｊ１，Ｖｊ２，．．．，Ｖｊｇの関数（例えば平均(average)又は中央値(median)）である。例えば、Ｆｊは車を表す画像クラスタであり得る。その場合、画像Ｆｉについて、記述子Ｖｉ及びＶｊ間の類似性を確認することは、Ｆｉが特定の画像に類似しているかどうかではなく、それが特定の画像クラス又は画像クラスタに類似しているかどうかを示す。一組の画像Ｆｚは、そのようなクラスタを任意数含むことができ、そのような処理は、所与の画像が最も良く適合する特定のクラスタを示すことになる。さらに、クラスタは、Ｖｊによってだけでなく、その画像の記述子の共分散行列等の他の統計量によっても表現することができる。共分散行列は、ステップ４４００において、より複雑な類似度（例えばマハラノビス距離又は最尤度）の計算を可能にする。
【００８６】
ビデオを分割するための本発明の別の実施形態において、ＶｊはフレームＦｊ１，Ｆｊ２，．．．，Ｆｊｇの記述子Ｖｊ１，Ｖｊ２，．．．，Ｖｊｇの関数（例えば平均又は中央値）である。これらのフレームは、全てがフレームＦｉに先行しても、全てがそれに後続しても、又は、一部が先行して一部が後続してもよい。
【００８７】
本明細書に概要を説明する発明の実施形態は、少なくとも２つの値を含む上記類似度を使用して、画像間の類似性又は非類似性を確認することに及ぶ。したがって、
【００８８】
ビデオを分割するための本発明の上記の実施形態では、ステップ４５００において、２つのフレームＦｉ及びＦｊ間の類似度を用いて、フレームの切れ目を検出する。本発明の代替的な実施形態は、この類似度だけでなく、フレームＦｉ及びＦｊの周囲のフレーム間の類似度も用いる。
【００８９】
例えば、本発明の一実施形態において、ｊ＝ｉ−１であり、フレームの切れ目の検出は、類似度Ｄｉ＋ｋ−１，ｉ＋ｋに依拠し、∀ｋ∈［−ｔ１，ｔ２］である。好ましい実施形態において、ｔ１＝ｔ２＝ｔである。したがって、フレームＦｉ＋ｋは、フレームＦｉを中心とする時間窓を形成する。次に、次の場合にのみ、Ｆｉ−１及びＦｉ間でフレームの切れ目を検出する。
【００９０】
【数１８】
2006092559.tif 000020
【００９１】
式（２７）及び（２８）によれば、各類似度Ｄｉ−１，ｉは、Ｄｉ−１，ｉを中心とする２ｔ＋１のサイズの時間窓内にあると考えられる。その場合、Ｄｉ−１，ｉが時間窓内の最大距離であり、且つ、時間窓内の２番目に大きい距離よりも少なくともｔｈｒ倍大きい場合にのみ、フレームＦｉ−１とフレームＦｉの間で切れ目を検出する。このような時間適応的な方式は、フレーム間の高い動きレベルから生じる誤った検出の数を低減することを目的とする。フレームの切れ目を検出するためにそのような時系列を処理するそのような方式はいくつかある。
【００９２】
本発明の好ましい実施形態において、スケール指向性の記述子の処理において使用する閾値及び制御パラメータはいずれもスケール指向性である。
【００９３】
代替的な実施形態において、スケール指向性の記述子の逐次処理は、ユーザによる指示又はこのプロセスを使用する自動システムによる指示に従って、最高スケールの記述子を処理し終える前に終了する。これは、例えばリアルタイムのオンライン用途で、またシステムがデータレートに付いて行けない場合に、システムの速度をさらに高めるために行うことができる。
【００９４】
本発明の別の実施形態を図５に示す。ステップ５１００において、上で説明したように、スケールに固有でチャネルに固有の記述子を抽出する。ステップ５２５０において、これらの記述子を融合させて、スケール指向性のマルチチャネル記述子Ｖｉ（ＳＣＱ），．．．，Ｖｉ（ＳＣＡ）の組にする。ここで、ＳＣＡ及びＳＣＱはそれぞれ最低の記述子スケール及び最高の記述子スケールである。ステップ５４１０、．．．、５４９０において、スケール指向性の記述子の対Ｖｉ（ＳＣＡ）及びＶｊ（ＳＣＡ），．．．，Ｖｉ（ＳＣＱ）及びＶｊ（ＳＣＱ）を使用して、画像Ｆｉと画像Ｆｊの間の類似度Ｄｊ，ｉ（ＳＣＡ），．．．，Ｄｊ，ｉ（ＳＣＱ）を計算する。したがって、複数の類似度を記述子のスケール毎に１つずつ計算する。ステップ５５１０、．．．、５５９０において、各類似度を用いて、２つの画像の類似性又は非類似性に関する仮決定を行う。したがって、複数の仮決定を、記述子のスケール毎に１つずつ行う。次に、ステップ５９００において、複数の仮決定を用いて、２つの画像の類似性又は非類似性に関する最終決定を行う。
【００９５】
図５に示すようなスケール指向性の並列構成の目的は、異なるスケールでの類似性の決定を処理することによって、画像Ｆｉと画像Ｆｊの間の関係のより徹底した調査を可能にするためである。したがって、このようなシステムは、最終的な類似性の決定だけでなく、「これらの画像は非常に粗いレベルでは類似しているが、細部では著しく異なる」といった付加的な情報も提供することができる。対照的に、スケールに固有でチャネルに固有の記述子を融合させて単一のマルチスケールでマルチチャネルの記述子にするシステムは、２つの画像に関して１つの類似性の決定しか提供することができない。
【００９６】
したがって、所与の画像Ｆｉに類似している一組の画像から画像を検索するための本発明の一実施形態では、図５に示すような方式により、検索結果を階層形式で提示することができる。最初に、粗いレベルでＦｉに類似している（すなわち、低スケールの記述子によれば類似している）一組の画像ＦＡを提示し、次に、ＦＡのサブセットであり、より細かい詳細レベルでＦｉに類似している一組の画像ＦＢを提示し、以下同様の順序で提示する。
【００９７】
フレームの切れ目検出及びビデオ分割のための本発明の別の実施形態において、図５に示すような方式により、異なる粒度（すなわち粗い、中程度、細かい、等）で分割を行うことができる。
【００９８】
図５において、ステップ５１００は図４のステップ４１００と類似しており、ステップ４１００について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【００９９】
同様に、ステップ５２５０は図４のステップ４２５０と類似しており、ステップ４２５０について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１００】
同様に、ステップ５４１０、．．．、５４９０の各々は図４のステップ４４００と類似しており、ステップ４４００について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１０１】
同様に、ステップ５５１０、．．．、５５９０の各々は図４のステップ４５００と類似しており、ステップ４５００について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１０２】
本発明の一実施形態において、ステップ５５１０、．．．、５５９０の仮決定は二分決定であり、例えば「１」が「類似」を示し、「０」が「非類似」を示す。
【０１０３】
本発明の別の実施形態において、ステップ５５１０、．．．、５５９０の仮決定は二分ではなく、少なくとも３つの値を含む。このような場合、処理ステップ５５１０、．．．、５５９０の結果の記述には、「仮決定」という用語よりも「尤度」という用語のほうが優れている。例えば、本発明の一実施形態において、ステップ５５１０、．．．、５５９０の各々は３つの閾値を用いる。類似度が第１の閾値を下回る場合、「非類似」を示す類似性の尤度「０」を生じる。類似度が第１の閾値を上回るが、第１の閾値よりも高い第２の閾値を下回る場合、「おそらく非類似」を示す類似性の尤度「１」を生じる。類似度が第２の閾値を上回るが、第２の閾値よりも高い第３の閾値を下回る場合、「おそらく類似」を示す類似性の尤度「２」を生じる。類似度が第３の閾値を上回る場合、「類似」を示す類似性の尤度「３」を生じる。本発明の別の実施形態において、尤度は、閾値処理によってではなく、類似度の一定範囲（例えば０〜１）への正規化により生成される。
【０１０４】
本発明の一実施形態のステップ５９００において、二分仮決定又は尤度をＺｊ，ｉ（ＳＣＡ），．．．，Ｚｊ，ｉ（ＳＣＱ）として示すと、ＦｉとＦｊが類似しているという最終決定は、次の場合にのみ行う。
【０１０５】
【数１９】
2006092559.tif 000021
【０１０６】
ここで、ｔｈｒｆは閾値であり、ＷＳＣＡ，．．．，ＷＳＣＱは、各スケール指向性の決定又は尤度に与える重要度を制御する重みである。これらの重みは、所望であれば、ＷＳＣＡ＝．．．＝ＷＳＣＱ＝１を設定することによって排除することができる。
【０１０７】
ステップ５５１０、．．．、５５９０により少なくとも３つの値を含む尤度を生成する本発明の別の実施形態において、２つの画像は、式（２９）の条件が当てはまり、さらに、新たな第２の閾値を下回る個別の尤度がないか、又は所与の数以下である場合にのみ、類似しているものと見なす。
【０１０８】
本発明の好ましい実施形態において、スケール指向性の記述子の処理において使用する閾値及び制御パラメータはいずれもスケール指向性である。
【０１０９】
本実施形態において説明するような一組の記述子の並列処理において、最終的な決定に至るために使用することのできるこのような方式は多くある。
【０１１０】
本発明の一実施形態は、スケールに固有でチャネルに固有の記述子を融合させて、異なるカラーチャネルにわたる少なくとも２つの記述子にすることを特徴とする。例えば、Ｙチャネル、Ｃｂチャネル及びＣｒチャネルにわたるスケールに固有でチャネルに固有の記述子の場合、本発明の一実施形態は、３つのマルチスケールでチャネル指向性の記述子を生成するが、別の実施形態は、１つがＹチャネル用、もう１つがＣｂチャネル及びＣｒチャネル用の２つのマルチスケールでチャネル指向性の記述子を生成する。本発明の好ましい実施形態では、記述子を実際に複数のスケールで計算し、融合させてチャネル指向性の記述子にするが、代替的な実施形態は、単一のスケールでのみ記述子を計算し、それらを融合させてチャネル指向性の記述子にする。
【０１１１】
前の段落の文章に沿った本発明の一実施形態を図６に示す。ステップ６１００において、上記で説明したように、スケールに固有でチャネルに固有の記述子を抽出する。ステップ６２５０において、これらの記述子を融合させて、マルチスケールでチャネル指向性の記述子ＶＣＣＡｉ，．．．，ＶＣＣＱｉの組にする。ここで、ＣＣＡ，．．．，ＣＣＱはカラーチャネル又はカラーチャネル群である。例えば、本発明の一実施形態において、ＣＣＡはＹチャネルを表し、ＣＣＢはＣｂＣｒのチャネル対を表す。本発明の別の実施形態において、ＣＣＡはＲＧＢのＲチャネルを表し、ＣＣＢはＧチャネルを表し、ＣＣＣはＢチャネルを表す。ステップ６４１０、．．．、６４９０において、チャネル指向性の記述子対ＶＣＣＡｉ及びＶＣＣＡｊ，．．．，ＶＣＣＱｉ及びＶＣＣＱｊを用いて、画像Ｆｉと画像Ｆｊの類似度ＤＣＣＡｊ，ｉ，．．．，ＤＣＣＱｊ，ｉを計算する。このように、複数の類似度を、チャネル指向性の記述子毎に１つずつ計算する。ステップ６５１０、．．．、６５９０において、各類似度を用いて、２つの画像の類似性又は非類似性に関する仮決定を行う。したがって、複数の仮決定を、チャネル指向性の記述子毎に１つずつ行う。次に、ステップ６９００において、複数の仮決定を用いて、２つの画像の類似性又は非類似性に関する最終決定を行う。
【０１１２】
図６に示すようなチャネル指向性の並列構成の目的は、異なるカラーチャネルにわたる類似性の決定を処理して、画像に関する異なる情報を取得することによって、画像Ｆｉと画像Ｆｊの間の関係のより徹底した調査を可能にすることである。したがって、このようなシステムは、最終的な類似性の決定だけでなく、「これらの画像は色差(chrominance)チャネルでは類似しているが、輝度チャネルでは類似していない」といった付加的な情報も提供することができる。対照的に、スケールに固有でチャネルに固有の記述子を融合させて単一のマルチスケールでマルチチャネルの記述子にするシステムは、２つの画像に関して１つの類似性の決定しか提供することができない。
【０１１３】
したがって、フレームの切れ目（例えばショット遷移又は照明効果等）を検出するための本発明の一実施形態において、図６に示すようなシステムは、フレームの切れ目を確実に検出するだけでなく、ショット遷移を他の照明効果と分離する。例えば、２つのフレームが色差と輝度の両方に関して著しく異なることが分かった場合、これはショット遷移を示す。一方、２つのフレームが輝度に関しては著しく異なるが、色差に関してはほとんど変わらないことが分かった場合、これは、ショット遷移でなく全体的な照明効果を示す。
【０１１４】
所与の画像Ｆｉに類似している一組の画像から画像を検索するための本発明の代替的な実施形態では、図６に示すような方式により、問い合わせ画像に意味的に類似している画像、例えば同一の風景又は都市景観のものであるが、異なる時刻に異なる照明条件で取り込まれた画像を検索することができる。
【０１１５】
図６において、ステップ６１００は図５のステップ５１００と類似しており、ステップ５１００について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１１６】
同様に、ステップ６２５０は図５のステップ５２５０と類似しており、ステップ５２００について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１１７】
同様に、ステップ６４１０、．．．、６４９０は図５のステップ５４１０、．．．、５４９０と類似しており、ステップ５４１０、．．．、５４９０について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１１８】
同様に、ステップ６５１０、．．．、６５９０は図５のステップ５５１０、．．．、５５９０と類似しており、ステップ５５１０、．．．、５５９０について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１１９】
同様に、ステップ６９００は図５のステップ５９００と類似しており、ステップ５９００について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１２０】
本発明の別の実施形態は、スケールに固有でチャネルに固有の記述子を最初に、スケールに固有でチャネルに固有の、特徴部の意味に指向性を持つ（feature-semantics-oriented）記述子に分割すること、及び、それらを次に融合させて、特徴部の意味の異なる少なくとも２つの記述子にすることを特徴とする。例えば、本発明の一実施形態において、６つの異なるスケールで３つの異なるカラーチャネルにわたる、スケールに固有でチャネルに固有の記述子の場合、全部で１８個の記述子が最初に利用可能である。これらの１８個の記述子を、半分が色内容要素（例えば式（１）のＬＬ）のみを含み、他の半分が色相関要素（例えば（２）〜（４）のＨＬ、ＬＨ及びＨＨ）のみを含む３６個の記述子に分割する。次に、これらの３６個の記述子を融合させて、１つが複数のスケールで、且つ異なるチャネルにわたる全ての色内容要素を含み、もう１つが複数のスケールで、且つ異なるチャネルにわたる全ての色相関要素を含む２つの記述子にする。本発明の別の実施形態では、最初の各記述子を３つ以上の記述子に分割する。例えば、各記述子を、ＬＬ、ＨＬ、ＬＨ及びＨＨタイプの要素のそれぞれに１つずつの、４つの記述子に分割する。次に、これらの記述子を融合させて、異なるスケールで、且つ異なるチャネルにわたって１タイプの要素のみ（例えばＬＬのみ又はＨＨのみ）をそれぞれ含む４つの最終的な記述子にする。本発明の好ましい実施形態では、記述子を実際に複数のスケールで複数のチャネルにわたって計算するが、代替的な実施形態は、記述子を単一のスケールのみで、及び／又は単一のチャネルのみについて計算してもよい。
【０１２１】
前の段落の文章に沿った本発明の一実施形態を図７に示す。ステップ７１００において、上記で説明したように、スケールに固有でチャネルに固有の記述子を抽出する。ステップ７２００において、上記で説明したように、これらの記述子を特徴部の意味に応じて分割する。ステップ７２５０において、結果として得られる記述子を融合させて、マルチスケールでマルチチャネルの、特徴部の意味に指向性を持つ記述子ＶＦＳＡｉ，．．．，ＶＦＳＱｉの組にする。ここで、ＦＳＡ，．．．，ＦＳＱは特徴部のタイプを表す。例えば、本発明の一実施形態において、ＦＳＡはＬＬ要素を表し、ＦＳＢはＨＬ要素、ＬＨ要素及びＨＨ要素を表す。本発明の別の実施形態において、ＦＳＡはＬＬ要素を表し、ＦＳＢはＨＬ要素を表し、ＦＳＣはＬＨ要素を表し、ＦＳＤはＨＨ要素を表す。ステップ７４１０、．．．、７４９０において、特徴部の意味に指向性を持つ記述子対ＶＦＳＡｉ及びＶＦＳＡｊ，．．．，ＶＦＳＱｉ及びＶＦＳＱｊを用いて、画像Ｆｉと画像Ｆｊの間の類似度ＤＦＳＡｊ，ｉ，．．．，ＤＦＳＱｊ，ｉを計算する。したがって、複数の類似度を、特徴部の意味に指向性を持つ記述子毎に１つずつ計算する。ステップ７５１０、．．．、７５９０において、各類似度を用いて、２つの画像の類似性又は非類似性に関する仮決定を行う。このように、複数の仮決定を、特徴部の意味に指向性を持つ記述子毎に１つずつ行う。次に、ステップ７９００において、複数の仮決定を用いて、２つの画像の類似性又は非類似性に関する最終決定を行う。
【０１２２】
図７に示すような特徴部の意味に指向性を持つ並列構成の目的は、異なる特徴部のタイプに基づく類似性の決定を処理して、画像に関する異なる情報を取得することによって、画像Ｆｉと画像Ｆｊの間の関係のより徹底した調査を可能にすることである。したがって、このようなシステムは、最終的な類似性の決定だけでなく、「これらの画像は局所エッジに関しては類似しているが、色内容に関しては類似していない」といった付加的な情報も提供することができる。対照的に、スケールに固有でチャネルに固有の記述子を融合させて単一のマルチスケールでマルチチャネルの記述子にするシステムは、２つの画像に関して１つの類似性の決定しか提供することができない。
【０１２３】
したがって、フレームの切れ目（例えばショット遷移又は照明効果等）を検出するための本発明の一実施形態において、図７に示すようなシステムは、フレームの切れ目を確実に検出するだけでなく、ショット遷移を他の照明効果と分離する。例えば、２つのフレームが色内容と色相関の両方に関して著しく異なることが分かった場合、これはショット遷移を示す。一方、２つのフレームが色内容に関しては著しく異なるが、色相関に関してはほとんど変わらないことが分かった場合、これは、ショット遷移でなく全体的な照明効果を示す。
【０１２４】
所与の画像Ｆｉに類似している一組の画像から画像を検索するための本発明の代替的な実施形態では、図７に示すような方式により、問い合わせ画像に意味的に類似している画像、例えば同一シーンのものであるが、異なる照明条件又は異なる機材で取り込まれたためにコントラストレベルの異なる画像を検索することができる。
【０１２５】
図７において、ステップ７１００は図６のステップ６１００と類似しており、ステップ６１００について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１２６】
図７において、ステップ７２００は図６のステップ６２００と類似しており、ステップ６２００について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１２７】
同様に、ステップ７２５０は図６のステップ６２５０と類似しており、ステップ６２５０について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１２８】
同様に、ステップ７４１０、．．．、７４９０は図６のステップ６４１０、．．．、６４９０と類似しており、ステップ６４１０、．．．、６４９０について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１２９】
同様に、ステップ７５１０、．．．、７５９０は図６のステップ６５１０、．．．、６５９０と類似しており、ステップ６５１０、．．．、６５９０について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１３０】
同様に、ステップ７９００は図６のステップ６９００と類似しており、ステップ６９００について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１３１】
本発明の別の実施形態は、スケールに固有でチャネルに固有の記述子を最初に、スケールに固有でチャネルに固有の領域指向性の記述子に分割すること、及び、それらを次に融合させて、画像内の異なる領域をカバーする少なくとも２つの記述子にすることを特徴とする。例えば、本発明の一実施形態において、５つの異なるスケール６４×６４、３２×３２、．．．、４×４で３つの異なるカラーチャネルにわたる、スケールに固有でチャネルに固有の記述子の場合、全部で１５個の記述子が最初に利用可能である。これらの１５個の記述子を、１５個の記述子からなる４つの組に分割する。各組は、画像の特定の象限に対応する要素のみを含む。すなわち、１組が左上の象限用、１組が右上の象限用、１組が左下の象限用、１組が右下の象限用である。次に、これらの記述子を融合させて、１つが複数のスケールで、且つ異なるチャネルにわたる全ての記述子要素を画像の左上の象限について含み、１つが同様の記述子要素を画像の右上の象限について含み、以下同様である４つの記述子にする。本発明の別の実施形態では、画像の縦スライスに対応する複数の領域指向性の記述子を形成する。さらに別の実施形態では、画像の横スライスに対応する複数の領域指向性の記述子を形成する。本発明の好ましい実施形態では、記述子を実際に複数のスケールで複数のチャネルにわたって計算するが、代替的な実施形態は、記述子を単一のスケールのみで、及び／又は単一のチャネルのみについて計算してもよい。
【０１３２】
前の段落の文章に沿った本発明の一実施形態を図８に示す。ステップ８１００において、上記で説明したように、スケールに固有でチャネルに固有の記述子を抽出する。ステップ８２００において、上記で説明したように、これらの記述子を画像領域に応じて分割する。ステップ８２５０において、結果として得られる記述子を融合させて、マルチスケールでマルチチャネルの領域指向性記述子ＶＲＥＡｉ，．．．，ＶＲＥＱｉの組にする。ここで、ＲＥＡ，．．．，ＲＥＱは画像領域を表す。例えば、本発明の一実施形態において、ＲＥＡは画像の左上の象限を表し、ＲＥＢは画像の右上の象限を表し、ＲＥＣは画像の左下の象限を表し、ＲＥＤは画像の右下の象限を表す。ステップ８４１０、．．．、８４９０において、領域指向性の記述子対ＶＲＥＡｉ及びＶＲＥＡｊ，．．．，ＶＲＥＱｉ及びＶＲＥＱｊを用いて、画像Ｆｉと画像Ｆｊの間の類似度ＤＲＥＡｊ，ｉ，．．．，ＤＲＥＱｊ，ｉを計算する。このように、複数の類似度を、領域指向性の記述子毎に１つずつ計算する。ステップ８５１０、．．．、８５９０において、各類似度を用いて、２つの画像の類似性又は非類似性に関する仮決定を行う。したがって、複数の仮決定を、領域指向性の記述子毎に１つずつ行う。次に、ステップ８９００において、複数の仮決定を用いて、２つの画像の類似性又は非類似性に関する最終決定を行う。
【０１３３】
図７に示すような領域指向性の並列構成の目的は、画像の異なる領域から生じる類似性の決定を処理することによって、画像Ｆｉと画像Ｆｊの間の関係のより徹底した調査を可能にすることである。したがって、このようなシステムは、最終的な類似性の決定を提供し、「これらの画像は或る領域では非常に類似しているが、他の領域では類似していない」といった情報を提供し、且つ、異なる画像の対応する領域間の関係を特定することができる。対照的に、スケールに固有でチャネルに固有の記述子を融合させて単一のマルチスケールでマルチチャネルの記述子にするシステムは、２つの画像に関して１つの類似性の決定しか提供することができない。
【０１３４】
したがって、所与の画像Ｆｉに類似している一組の画像から画像を検索するための本発明の一実施形態では、図８に示すような方式により、問い合わせ画像に部分的に類似している画像、例えば同一シーンのものであるが、カメラの視野（optical field）に突然歩いて入ってきてシーンの左側部分を遮る人物により生じる遮蔽を有する画像を検索することができる。
【０１３５】
同様に、フレームの切れ目を検出するための本発明の代替的な実施形態において、図８に示すようなシステムは、フレームの切れ目を確実に検出するだけでなく、ショット遷移を他のショット内障害（例えば、カメラに近い速度で(at speed close to the camera)移動し、視野を短い間遮る人物）と分離する。
【０１３６】
図８において、ステップ８１００は図７のステップ７１００と類似しており、ステップ７１００について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１３７】
同様に、ステップ８２００は図７のステップ７２００と類似しており、ステップ７２００について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１３８】
同様に、ステップ８２５０は図７のステップ７２５０と類似しており、ステップ７２５０について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１３９】
同様に、ステップ８４１０、．．．、８４９０は図７のステップ７４１０、．．．、７４９０と類似しており、ステップ７４１０、．．．、７４９０について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１４０】
同様に、ステップ８５１０、．．．、８５９０は図７のステップ７５１０、．．．、７５９０と類似しており、ステップ７５１０、．．．、７５９０について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１４１】
同様に、ステップ８９００は図７のステップ８９００と類似しており、ステップ８９００について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【０１４２】
本発明の好ましい実施形態では、多くのスケールで、且つ複数のチャネルにわたって記述子を抽出することが明確に理解されるべきである。しかし、本発明の代替的な実施形態において、そうである必要はない。例えば、スケール指向性の枠組みを実現するために、単一のカラーチャネルについて、及び／又は単一の画像領域について記述子を抽出してもよい。同様に、チャネル指向性の枠組みを実現するために、単一のスケールで、及び／又は単一の画像領域について記述子を抽出してもよい。同様に、特徴部の意味に指向性を持つ枠組みを実現するために、単一のスケールで、及び／又は単一のチャネルについて、及び／又は単一の画像領域について記述子を抽出してもよい。同様に、領域指向性の枠組みを実現するために、単一のスケールで、及び／又は単一のチャネルについて記述子を抽出してもよい。
【０１４３】
また、本明細書中で説明する逐次構成及び並列構成は、特定の記述子の分割又は指向に限定されないことが明確に理解されるべきである。特定の構成を特定の記述子の指向に適用するのは単に例示を目的とするものである。例えば、上記の実施形態は、スケール指向性の記述子についてのみ逐次構成を検討する。本発明の代替的な実施形態は、他の記述子の指向に逐次構成を使用する。例えば、本発明の代替的な実施形態は、チャネル指向性の記述子を逐次構成で処理し、チャネルのうちの１つにおいて所与の画像に類似していない画像を迅速にフィルタリングで除去し、他のチャネルの処理を不要にすることを目指す。本発明のさらに別の代替的な実施形態は、特徴部の意味に指向性を持つ記述子を逐次構成で、上記と同じ原理で処理する。本発明のさらに別の代替的な実施形態は、領域指向性の記述子を逐次構成で、上記と同じ原理で処理する。
【０１４４】
また、システムは、複数の記述子の指向に依拠してもよいことが明確に理解されるべきである。例えば、本発明の一実施形態では、スケールに固有でチャネルに固有の記述子を最初に計算した後に、スケール指向性で特徴部の意味に指向性を持つ記述子を形成する。例えば、４つの記述子、すなわち、低スケールの色内容要素用の１つの記述子、高スケールの色内容要素用の１つの記述子、低スケールの色相関要素用の１つの記述子、及び高スケールの色相関要素用の１つの記述子を形成する。本発明の一実施形態では、そのような記述子を、上述のように並列構成で処理する。本発明の別の実施形態では、そのような記述子を、上述のように逐次構成で処理する。本発明のさらに別の実施形態では、図９に示すようなハイブリッド構成を用いる。図９において、ＳＣＡ及びＳＣＱはそれぞれ最低の記述子スケール及び最高の記述子スケールであり、ＦＳＡ，．．．，ＦＳＱは特徴部のタイプを表す。
【０１４５】
このハイブリッドの枠組みは、単一の記述子の指向にも利用することができる。例えば、１つの代替的な実施形態は逐次構成に依拠し、それによって、各ループにおいて、単一ではなく少数のスケール指向性記述子を、組み込まれた並列構成で処理する。このように、本発明の異なる実施形態は、単一の記述子の指向に依拠するか、複数の記述子の指向に依拠するかに関わらず、逐次構成又は並列構成又はハイブリッド構成に依拠してもよいことも明確に理解されるべきである。また、図９は、並列構成を逐次構成に埋め込む１つの可能なハイブリッド構成を例示目的で示すに過ぎないことを明確に理解すべきである。代替的な実施形態は他のハイブリッド構成、例えば、１つ又は複数の逐次構成を並列構成に埋め込む構成を使用する。
【０１４６】
図９に示すように、画像を最初に、粗い開始スケールで処理し、確信の持てる決定に至らない場合、画像を次に細かいスケールで処理し、以下同様の操作を行い、確信の持てる決定に至るか、又は利用可能／許容可能なスケールを使い果たすまで続ける。
【０１４７】
好ましい実施形態では、各スケールについて、並列処理される画像毎に４つの記述子があり、それぞれの結果を組み合わせて、そのスケールの決定を得る。これは図９と類似しているが、使用される記述子は以下の、（ｉ）輝度から抽出される色内容、（ｉｉ）輝度から抽出される色相関、（ｉｉｉ）色差から抽出される色内容、及び（ｉｖ）色差から抽出される色相関である。
【０１４８】
代替案では、２つの色内容記述子（１つが輝度用、もう１つが色差(chrominance)用）を開始スケールのみについて用いる。全ての他のスケールについては、２つの色相関記述子のみを用いる。
【０１４９】
さらに、上記の実施形態では、フレームの切れ目を検出するために、連続フレームの全ての対の処理を検討した。代替的な実施形態は、フレームをより粗く処理してもよい。代替的な実施形態は、４番目毎のフレームのみを処理し、さらに別の実施形態は、１６番目毎のフレームのみを処理する。このような向上により、ビデオ分割システムの速度がさらに上がる。
【０１５０】
さらに、上記の説明は、各フレームがその画素値で表される未圧縮のデジタルビデオの処理に関する。本発明は、復元していないＭＰＥＧ圧縮ビデオにも直接適用することができる。
【０１５１】
ＭＰＥＧビデオの性質は、当業者にはよく知られており、J. Watkinsonの著書「The MPEG Handbook: MPEG-1, MPEG-2, MPEG-4」（Focal Press, Oxford 2001, ISBN:0-240-51656-7）に専門的に記載されている。
【０１５２】
ＭＰＥＧ圧縮ビデオに関する本発明の一実施形態では、ビデオのＩフレームのみを処理する。より具体的には、ＩフレームのＤＣ表現のみを処理する。すなわち、８×８画素の各ブロックについて、そのＤＣＴ変換のＤＣ成分のみを取る。事実上、ＩフレームのＤＣ表現は単に、８×８のブロック平均を用いて圧縮前の原フレームをリサンプリングしたものである。ＤＣ成分は、圧縮ビデオストリームから復元を行うことなく直接取り出すことができるため、本発明の実施形態は、ＭＰＥＧ圧縮ビデオのＩフレームの処理に直接適用できることが明らかである。
【０１５３】
本発明は、例えばコンピュータシステムにおいて、適切なソフトウェア及び／又はハードウェアの変更を施して実施することができる。例えば、本発明は、プロセッサ又は制御装置等の制御又は処理手段、メモリ、磁気記憶装置、ＣＤ、ＤＶＤ等の画像記憶手段を含むデータ記憶手段、ディスプレイ若しくはモニタ又はプリンタ等のデータ出力手段、キーボード等のデータ入力手段、及びスキャナ等の画像入力手段、又はそのような構成要素の任意の組み合わせ並びに追加の構成要素を有するコンピュータ又は同様の装置を用いて実施することができる。本発明の態様は、ソフトウェア及び／又はハードウェア形態で、又は特定用途向け装置において提供するか、又は集積回路等の特定用途向けモジュールを提供することができる。本発明の一実施形態による装置中のシステムの構成要素は、他の構成要素から遠隔して、例えばインターネットを介して設けられてもよい。
【０１５４】
コンピュータシステムの形態の適切な装置のブロック図を図１０に示し、この図において、制御ユニット１０１００は、画像記憶手段１０２００、記述子記憶手段１０３００及びディスプレイ１０４００に接続される。画像記憶手段１０２００は、上記の実施形態により表現又は比較される画像に対応するデータを記憶する。これは、１つの画像、複数の画像、画像クラスタ、画像シーケンス又は画像データベース全体に対応するデータであってもよい。記述子記憶手段１０３００は、データベースであってもよく、制御ユニット１０１００により計算される副記述子(sub-descriptors)を含む導出された記述子をすべて記憶する。制御ユニットの動作の結果は、ディスプレイ１０４００上でユーザに対して表示する。
【０１５５】
「スケール」及び「解像度」という用語は、本明細書において置き換え可能に用いられる。画像の領域は画像全体又は画像の部分を意味し得る。「記述子」という用語は、決定を行うプロセスにおいて使用され得る、画像又は画像の部分の導出された表現を指す。「副記述子」という用語は、関連付けられて記述子を形成する、画像又は画像の部分の導出された表現を指す。しかし、当業者であれば、この区別は便宜的なものに過ぎず、各用語は、上述の方法の特定の点を指すことを認識するであろう。特定の実施形態の各副記述子は、異なる実施形態では記述子として機能する場合があり、その逆の場合も同様である。したがって、特定の実施形態では記述子という用語のみが用いられる。
【図面の簡単な説明】
【０１５６】
【図１】本発明の一実施形態によるＹチャネルのブロック平均リサンプリングプロセスを示す図である。
【図２Ａ】本発明の一実施形態における１つのスケールの記述子の計算を示す図である。
【図２Ｂ】本発明の一実施形態における１つのスケールの記述子の計算を示す図である。
【図２Ｃ】本発明の一実施形態における１つのスケールの記述子の計算を示す図である。
【図２Ｄ】本発明の一実施形態における１つのスケールの記述子の計算を示す図である。
【図３Ａ】本発明のさらなる実施形態による１つのスケールの記述子の計算を示す図である。
【図３Ｂ】本発明のさらなる実施形態による１つのスケールの記述子の計算を示す図である。
【図３Ｃ】本発明のさらなる実施形態による１つのスケールの記述子の計算を示す図である。
【図３Ｄ】本発明のさらなる実施形態による１つのスケールの記述子の計算を示す図である。
【図４】本発明の一実施形態による複数の画像を比較するフロー図である。
【図５】本発明のさらなる実施形態による複数の画像を比較するフロー図である。
【図６】本発明のさらなる実施形態による複数の画像を比較するフロー図である。
【図７】本発明のさらなる実施形態による複数の画像を比較するフロー図である。
【図８】本発明のさらなる実施形態による複数の画像を比較するフロー図である。
【図９】本発明のさらなる実施形態による複数の画像を比較するフロー図である。
【図１０】本発明の実施形態の実施に適した処理装置の概略図である。
【図１】
2006092559.tif 000022
【図２Ａ】
2006092559.tif 000023
【図２Ｂ】
2006092559.tif 000024
【図２Ｃ】
2006092559.tif 000025
【図２Ｄ】
2006092559.tif 000026
【図３Ａ】
2006092559.tif 000027
【図３Ｂ】
2006092559.tif 000028
【図３Ｃ】
2006092559.tif 000029
【図３Ｄ】
2006092559.tif 000030
【図４】
2006092559.tif 000031
【図５】
2006092559.tif 000032
【図６】
2006092559.tif 000033
【図７】
2006092559.tif 000034
【図８】
2006092559.tif 000035
【図９】
2006092559.tif 000036
【図１０】
2006092559.tif 000037
【外国語明細書】
2006092559.tif 000038
2006092559.tif 000039
2006092559.tif 000040
2006092559.tif 000041
2006092559.tif 000042
2006092559.tif 000043
2006092559.tif 000044
2006092559.tif 000045
2006092559.tif 000046
2006092559.tif 000047
2006092559.tif 000048
2006092559.tif 000049
2006092559.tif 000050
2006092559.tif 000051
2006092559.tif 000052
2006092559.tif 000053
2006092559.tif 000054
2006092559.tif 000055
2006092559.tif 000056
2006092559.tif 000057
2006092559.tif 000058
2006092559.tif 000059
2006092559.tif 000060
2006092559.tif 000061
2006092559.tif 000062
2006092559.tif 000063
2006092559.tif 000064
2006092559.tif 000065
2006092559.tif 000066
2006092559.tif 000067
2006092559.tif 000068
2006092559.tif 000069
2006092559.tif 000070
2006092559.tif 000071
2006092559.tif 000072
2006092559.tif 000073
2006092559.tif 000074
2006092559.tif 000075
2006092559.tif 000076
2006092559.tif 000077
2006092559.tif 000078
2006092559.tif 000079
2006092559.tif 000080
2006092559.tif 000081
2006092559.tif 000082
2006092559.tif 000083
2006092559.tif 000084
2006092559.tif 000085
2006092559.tif 000086
2006092559.tif 000087
2006092559.tif 000088
2006092559.tif 000089
2006092559.tif 000090
2006092559.tif 000091
2006092559.tif 000092
2006092559.tif 000093
2006092559.tif 000094
2006092559.tif 000095
2006092559.tif 000096
2006092559.tif 000097
2006092559.tif 000098