(57)【要約】      （修正有）【課題】画像間の類似牲を評価するための改良された方法を提供する。【解決手段】少なくとも１つの画像を表現する方法は、画像の少なくとも１つの領域の色情報及び色相関情報に基づいて少なくとも１つの記述子を導出することを含み、記述子は、上記領域内の画素の値を用いて導出される少なくとも１つの記述子要素を有し、或る領域の少なくとも１つの記述子要素は非ウェーブレット変換を用いて導出される。表現は画像の比較に用いることができる。【選択図】図２Ｂ
2006135938.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. Dailianas、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）には、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）に記載されているのと同じ方法でビデオフレームを特徴付けしていくショット遷移の検出方法が提案されている。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）の方法と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）の方法の違いは、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）の方法を用いる場合、フレームの周辺を廃棄し、フレームをその中心部分のみに縮小することである。このような手法は、大きな情報損失につながり、ビデオ中に大きな動きが存在する場合、誤ったビデオの分割及び／又は大きな過分割を生じる可能性がある。
【００１０】
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）の方法と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）の方法の両方に共通する欠陥は、ごく少数の最大振幅の係数のみを保持することによってハール分解を効率的に打ち切ることができるという仮定である。これに関連して(to put this in context)、画像平面のマルチスケールハール分解を１２８×１２８画素から開始して２×２画素まで行うと、１６３８３個の係数が生じる。画像検索又はビデオ処理の目的で、このような特徴ベクトルは実際、高速で効率的な実施態様には大きすぎる場合がある。しかし、このベクトルを振幅に基づいてごく少数の係数、例えば著者等が示唆するように最大振幅を有する４０個又は６０個の係数に打ち切ることは、数学的にその次元数を下げる方法であり、いくつかの問題を挙げれば、当業者には承知の通り、画像の空間的に不均一な表現を与える記述子を生じることであり、ノイズの影響を非常に受けやすく、且つ、ビデオ分割の場合に高いビデオの動き及びショット内の照明効果の影響を非常に受けやすい。符号のみを保持することによる打ち切り系列の量子化は、問題をさらに大きくする。
【００１１】
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）の方法及び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）の方法に伴う別の欠点は、ハール分解の計算が、画像領域の係数をその領域内の全ての画素値に基づいて計算するために計算量の増加を伴うことである。
【００１２】
本発明では、例えば、所与の画像に類似している一組の画像から画像を検索するため、又はデジタルビデオ中のフレームの切れ目（例えばショット遷移又は照明及び他の効果）を検出するために、画像間の類似性を評価する方法を提案する。この方法は、空間的に敏感な色内容及び色相関の情報を１つ又は複数の画像スケールで、且つ１つ又は複数の画像チャネルにわたって取得する画像記述子の抽出に依拠する。この方法の１つの特徴は、以前の方法とは異なり、記述子が空間的に敏感な色内容及び色相関の情報を画像平面にわたって均一に、且つ複数のスケールで取得しながらも、上記のハール分解と比較してサイズが小さく、よって人工的な打ち切りプロセスを行う必要性が少なくなるように記述子を抽出できることである。本方法のもう１つの特徴は、以前の方法と異なり、記述子による原画像の完全な再構成が可能でありながら、計算負荷が上記のハール分解と比べて少ない記述子を抽出できることである。
【００１３】
上記に鑑みて、本発明の目的は、例えば所与の画像に類似している一組の画像から画像を検索するため、又はデジタルビデオ中のフレームの切れ目（例えばショット遷移又は照明及び他の効果）を検出するために、画像間の類似性を評価するための改良された方法を提供することである。
【００１４】
ビデオ分割のために、提案する方法論は、非圧縮デジタルビデオフレームとＭＰＥＧ圧縮デジタルビデオフレームの両方の再現を可能にする。後者の場合、復元を行うことなくＩフレームを表現することができる。
【００１５】
本発明の態様を添付の特許請求の範囲に記載する。
【００１６】
一実施形態の特徴は、
（ｉ）空間的に敏感な色内容及び色相関の情報を１つ又は複数の画像スケールで、且つ１つ又は複数の画像チャネルにわたって取得する画像記述子の抽出であって、少なくとも１つのスケールに固有でチャネルに固有の画像表現の記述子は、
少なくとも１つの記述子要素タイプの全ての領域記述子要素を、それぞれの領域の画素のサブセットのみを用いて計算すること、
及び／又は
全ての記述子要素タイプの全ての領域記述子要素の計算に用いる画素は、それぞれの領域の画素の単なるサブセットであること、
及び／又は
記述子要素の総数は上記表現の画素数よりも少なく、上記特性は、記述子のいかなる後処理（例えば打ち切り）にも依存せず記述子抽出プロセスに固有であること
を特徴とする、画像記述子の抽出、
（ｉｉ）上記記述子を組み合わせて１つのマルチスケールでマルチチャネルの記述子にすること、及び
（ｉｉｉ）結果として得られる記述子を使用して、画像間の類似性を評価すること
を含む。
【００１７】
本発明の特定の実施形態の概要を以下で、添付図面を参照して説明する。
【００１８】
本発明の第１の実施形態は記述子の抽出に関する。
【００１９】
デジタル画像Ｆｉ（ｘ，ｙ）を検討する。ここで、（ｘ，ｙ）は空間座標を表し、ｘ＝０．．．Ｍ−１及びｙ＝０．．．Ｎ−１である。本発明の一実施形態において、Ｆｉは色空間ＹＣｂＣｒで表されるが、これに制限されるものではなく、本発明は、いかなるチャネル数のいかなる色空間にも適用可能である。本発明の一実施形態において、Ｆｉの空間解像度は７２０×５７６画素である、すなわち、Ｍ＝７２０及びＮ＝５７６であるが、これに限定されるものではなく、本発明は、いかなる空間解像度にも適用可能である。本発明の一実施形態において、記述子を抽出する最高解像度として６４×６４画素を選択するが、これに限定されるものではなく、本発明は他の解像度にも適用可能である。したがって、Ｆｉをリサンプリングして、６４×６４画素の画像Ｆｉ（６４×６４）を得る。本発明の一実施形態において、このリサンプリングプロセスは、図１に示すような単純なブロック平均プロセスであるが、リサンプリング機構の選択は限定されない。より具体的に言えば、図１は、Ｙチャネルのブロック平均リサンプリングプロセスを示すが、これに限定されるものではなく、このプロセスは、いかなる色空間のいかなるチャネルにも用いることができる。本発明の別の実施形態において、記述子を抽出する最高スケールはＦｉの解像度に一致し、最初のリサンプリングは必要とされない。
【００２０】
図２は、本発明の一実施形態における、このスケールの記述子の計算を示す。より具体的には、図２は、Ｙチャネルの記述子の計算を示すが、これに限定されるものではなく、同様の手法を全てのカラーチャネルに適用する。図２Ａにおいて、２×２の窓を画像の左上の角に適用する。この窓は局所近傍を指定する。この近傍の画素ＦＹｉ（６４×６４）（０，０），ＦＹｉ（６４×６４）（１，０），ＦＹｉ（６４×６４）（０，１）及びＦＹｉ（６４×６４）（１，１）について、記述子要素χ１〜χ４を次のように計算することができる。
【００２１】
【数１】
2006135938.tif 000003
【００２２】
上記の式において、要素χ１は色内容情報を取得し、要素χ２、χ３及びχ４は色相関情報を取得する。
【００２３】
ＦＹｉ（６４×６４）の記述子をＶＹｉ（６４×６４）とすると、これらの値は、次のように記述子に書き換えることができる。
【００２４】
【数２】
2006135938.tif 000004
【００２５】
次に、図２Ｂに示すように、２×２の窓を２画素右にスライドさせ、画素ＦＹｉ（６４×６４）（２，０），ＦＹｉ（６４×６４）（３，０），ＦＹｉ（６４×６４）（２，１）及びＦＹｉ（６４×６４）（３，１）を含む新たな近傍を形成する。記述子要素χ１〜χ４を再び、新たな画素値について計算し、その後、記述子位置ＶＹｉ（６４×６４）（５）〜ＶＹｉ（６４×６４）（８）に格納する。図２Ｃ及び図２Ｄに示すように、一組の行について計算が全て完了すると、スライド窓を２画素下に移動させ、左から右へのスライドを再び開始し、画像全体を処理し終えるまで続ける。これにより、Ｙ平面について６４×６４画素のスケールで、画像の空間的に敏感な色内容及び色相関を取得する記述子ＶＹｉ（６４×６４）の計算が完了する。
【００２６】
本明細書に概要を説明する発明は、空間的に敏感な色内容及び色相関の情報を取得する記述子の計算を含む。
【００２７】
別の実施形態は、記述子要素χ１〜χ４を、以下に記載するように導出される記述子要素ψ１及びψ２で置き換える。
【００２８】
【数３】
2006135938.tif 000005
【００２９】
上に示す式（Ｉ）及び（ＩＩ）において、ψ１は色内容情報を取得し、ψ２は色相関情報を取得する。記述子要素の数は、記述子要素の導出に使用される画素数よりも少ない。
【００３０】
さらに別の実施形態は、記述子要素χ１〜χ４を、以下に記載するように導出される記述子要素φ１〜φ４で置き換える。
【００３１】
【数４】
2006135938.tif 000006
【００３２】
上に示す式（ＩＩＩ）〜（ＶＩ）において、φ１は色内容情報を取得し、φ２〜φ４は色相関情報を取得する。
【００３３】
本発明の別の実施形態では、図３の方式により記述子要素を抽出する。図３Ａにおいて、４×４の窓を画像の左上の角に適用する。この窓は、１６画素を含む局所近傍を指定する。この近傍の画素について、以下の記述子要素を計算する。
【００３４】
【数５】
2006135938.tif 000007
【数６】
2006135938.tif 000008
【数７】
2006135938.tif 000009
【数８】
2006135938.tif 000010
【００３５】
上記の式において、ψ１は色内容情報を取得し、ψ２、ψ３及びψ４は色相関情報を取得する。当業者は、式（６）〜（９）を変更して、必要な計算の数を減らしてもよいことを理解するであろう。
【００３６】
これらの値は、一連の式（lines of equation）（５）に沿って記述子ＶＹｉ（６４×６４）として書き表すことができ、次に、図３Ｂに示すように、４×４の窓を４画素右にスライドさせて新たな近傍を形成し、新たな画素値について記述子要素を再び計算し、以下同様の操作を行う。図３Ｃ及び図３Ｄに示すように、一組の行の計算が全て完了すると、スライド窓を２画素下へ移動させ、左から右へのスライドを再び開始し、画像全体を処理し終えるまで続ける。
【００３７】
本発明の代替的な実施形態において、色内容及び／又は色相関の記述子要素の計算は、近傍画素の関数（例えば中央値、最大値、最小値等）に依拠してもよい。
【００３８】
さらに、上記の説明は、２×２画素及び４×４画素のサイズのスライド近傍窓を検討するが、これに限定されるものではない。代替的な実施形態は、例えば、所与の計算に関する要求又は近傍測定プロセス自体に合わせて、任意のサイズ及び／又は幾何形状及び／又はスライドステップを近傍窓に指定し、重複する窓又は重複しない窓を生じることができる。
【００３９】
上記の説明では、ＦＹｉ（６４×６４）の全ての位置で同一の近傍窓及び記述子抽出プロセスを用いる。代替的な実施態様では、そうである必要はない。代替的な実施形態は、画像中の異なる位置で異なる近傍パラメータ及び／又は記述子抽出プロセスを使用してもよい。例えば、本発明の代替的な実施形態は、速い記述子抽出プロセスを画像の周辺に用い、遅いが強力な記述子抽出プロセスを画像の中心に用いる。
【００４０】
次に、ＦＹｉ（６４×６４）を新たなより低いスケールにリサンプリングする。一実施形態において、この新たなスケールは３２×３２画素である。次に、６４×６４の画像の場合と全く同じ方法で新たな記述子ＶＹｉ（３２×３２）を計算する。なお、このリサンプリングは実際には計算を必要としない場合もあり得る。式（１）に見られるように、この新たな画素値は、χ１の値として以前に計算し、ＶＹｉ（６４×６４）（１），ＶＹｉ（６４×６４）（５），ＶＹｉ（６４×６４）（９），．．．，ＶＹｉ（６４×６４）（４０９３）に格納している。一実施形態では、このように、記述子ＶＹｉ（６４×６４），ＶＹｉ（３２×３２），ＶＹｉ（１６×１６），ＶＹｉ（８×８），ＶＹｉ（４×４），及びＶＹｉ（２×２）を計算する。
【００４１】
本明細書において概要を説明する発明は、画像Ｆｉの１つ又は複数のスケールで記述子を抽出することを含む。上記の説明において、最も細かい又は最大又は最高スケール、最も粗い又は最小又は最低スケール、スケールの数及びスケール間の関係は、本発明の可能な一実施形態を示すに過ぎず、代替的な実施形態は、例えばシステムの計算能力に合うように、異なるそのようなパラメータを使用してもよい。
【００４２】
本発明の一実施形態では、以降の処理を行う前に、これらのスケールに固有の記述子から特定の要素を除去する。本発明の一実施形態では、２ｂ×２ｂ、２ｂ−１×２ｂ−１、２ｂ−２×２ｂ−２等、例えば、６４×６４、３２×３２、１６×１６等のスケールでの式（１）〜（４）において概要を説明した記述子抽出プロセスの場合、ＶＹｉのχ１要素を、最低スケールのχ１要素を除いて全て除去してもよい。これは、２ｂ−ｋ×２ｂ−ｋのスケールのχ１要素を、２ｂ−ｋ−１×２ｂ−ｋ−１のスケールのχ１値、並びに２ｂ−ｋ×２ｂ−ｋのスケールのχ２要素、χ３要素、及びχ４要素から直接計算できるためである。なお、この特性は常に当てはまるわけではない。例えば、２ｂ×２ｂ、２ｂ−２×２ｂ−２、２ｂ−４×２ｂ−４等、例えば、６４×６４、１６×１６、４×４等のスケールで記述子を計算する場合には当てはまらない。また、記述子抽出プロセスの一部としてχ１要素、χ２要素、χ３要素及びχ４要素のサブセットのみを計算する場合には当てはまらない。同一の特性が式（ＩＩＩ）〜（ＶＩ）の変換に当てはまる。
【００４３】
同一の記述子抽出プロセスをＦｉのＣｂチャネル及びＣｒチャネルに適用すると、記述子ＶＣｂｉ（６４×６４），．．．，ＶＣｂｉ（２×２）及びＶＣｒｉ（６４×６４），．．．，ＶＣｒｉ（２×２）が得られる。これらのスケールに固有でチャネルに固有の記述子は、全体で、画像の空間的に敏感な色内容及び色相関の情報を複数のスケールで、且つ複数のチャネルにわたって取得する。
【００４４】
上記の説明において、ＦｉはＹＣｂＣｒ色空間にあると仮定し、記述子の抽出に全てのチャネルを用いる。代替的な実施態様は、記述子を計算する前に画像を新たな色空間で表現してもよいし、かつ／又は記述子の計算に色平面のサブセットのみを使用してもよい。
【００４５】
上記の説明では、Ｆｉの異なるカラーチャネルにわたる記述子を同一スケールで計算する。代替的な実施態様では、そうである必要はない。例えば、本発明の代替的な実施形態はＹチャネルの記述子を、Ｃｂ及び／又はＣｒチャネルの記述子よりも多いスケールで、及び／又はそれとは異なるスケールで計算する。このような微調整により、特定の画像又はビデオ素材により良く適合して、性能を高めることができる。
【００４６】
上記の説明では、Ｆｉの全てのカラーチャネルに同一の近傍窓及び記述子抽出プロセスを用いる。代替的な実施態様では、そうである必要はない。代替的な実施形態は、チャネル毎に異なる近傍パラメータ及び／又は記述子抽出プロセスを使用してもよい。例えば、本発明の代替的な実施形態は、速い記述子抽出プロセスをＣｂチャネル及びＣｒチャネルに用い、遅いが強力な記述子抽出プロセスをＹチャネルに用いる。このような微調整により、特定の画像又はビデオ素材により良く適合して、システムの性能を高めることができる。
【００４７】
本発明の一実施形態では、記述子要素の一部又は全てを、整数部と小数部を持つ実数で表現する。本発明の別の実施形態では、記述子要素の一部又は全てを、例えば小数部を切り捨てるか又は切り上げる(round)ことによって、整数形式で表現する。本発明のさらに別の実施形態では、記述子要素の一部又は全てを、スケーリングによって整数形式で表現する。例えば、式（１）〜（４）は、小数部が３つの値、すなわち、．２５、．５０及び．７５しか取り得ない実数を生成する。記述子要素χ１に４の値を掛け、記述子要素χ２、χ３及びχ４に２の値を掛けることによって、情報を全く損失せずに整数表現が得られる。本発明のさらに別の実施形態では、記述子要素の一部又は全てを、何らかの方法で整数形式で表現し、その後、例えば３ビット又は４ビット長の短い値に量子化する。
【００４８】
したがって、本発明の一実施形態では、画像Ｆｉをその記述子ＶＣ１ｉ（Ｃ１ＳＣｑ），．．．，ＶＣ１ｉ（Ｃ１ＳＣ１），ＶＣ２ｉ（Ｃ２ＳＣｑ），．．．，ＶＣ２ｉ（Ｃ２ＳＣ１），．．．，ＶＣｐｉ（ＣｐＳＣｑ），．．．，ＶＣｐｉ（ＣｐＳＣ１）で表現する。ここで、Ｃ１，Ｃ２，．．．，ＣｐはＦｉの第１、第２及び第ｐのカラーチャネルであり、Ｃ１ＳＣｑはチャネルＣ１の最高の記述子スケールであり、Ｃ１ＳＣ１はチャネルＣ１の最低の記述子スケールであり、Ｃ２ＳＣｑはチャネルＣ２の最高の記述子スケールであり、Ｃ２ＳＣ１はチャネルＣ２の最低の記述子スケールであり、以下同様である。これらのスケールに固有でチャネルに固有の記述子は、全体で、画像の空間的に敏感な色内容及び色相関の情報を複数のスケール（好ましくは２つ以上）で、且つ複数のチャネル（好ましくは２つ以上）にわたって取得する。
【００４９】
次に、これらの記述子を融合すなわち連結させて、次の処理のために１つの記述子にする。これを図４に示す。
【００５０】
この実施形態では、ステップ４１００において、上記で説明したように、スケールに固有でチャネルに固有の記述子を抽出する。ステップ４２５０において、これらの記述子を融合させてマルチスケールでマルチチャネルの記述子Ｖｉにする。ステップ４４００において、記述子Ｖｉ及びＶｊを用いて、画像Ｆｉと画像Ｆｊの類似度（similarity measure）Ｄｊ，ｉを計算する。ステップ４９００において、類似度を用いて、２つの画像の類似性又は非類似性を評価する。
【００５１】
次に、このプロセスの様々なステップをより詳しく検討する。
【００５２】
ステップ４４００において、類似度の計算には多くのオプションがある。例えば、本発明の一実施形態において、それぞれｎ個の要素からなる２つの記述子Ｖｉ及びＶｊの間のＬ１距離は、次式により与えられる類似度として計算することができる。
【００５３】
【数９】
2006135938.tif 000011
【００５４】
本明細書に概要を説明する発明は、画像記述子を使用して、画像間の少なくとも２つの値を含む類似度を計算することを含む。
【００５５】
記述子の距離を計算するための式（１０）のＬ１距離は、本発明の可能な１実施態様に関連するに過ぎない。代替的な実施態様は、式（１０）を、Ｌ２距離を計算する次式（１１）で置き換える。
【００５６】
【数１０】
2006135938.tif 000012
【００５７】
このような様々な距離メトリックが上記の関連文献に記載されている。
【００５８】
さらに、代替的な実施態様は、式（１０）を次式（１２）で置き換える。この式（１２）は、重み付きＬ１距離を計算する。
【００５９】
【数１１】
2006135938.tif 000013
【００６０】
ここで、ｗ（ｌ）はｌ番目の記述子要素の重み係数である。さらに、重みの適用はまた、式（１１）のＬ２距離、又は上記文献に記載されている任意の他の適切な距離メトリックとともに用いてもよい。
【００６１】
類似度の処理には多くのオプションがある。本発明の一実施形態では、ステップ４９００において、類似度Ｄｊ，ｉに閾値処理関数を適用する。すなわち、ある閾値ｔｈｒについて、
【００６２】
【数１２】
2006135938.tif 000014
【００６３】
である場合、２つの画像は異なるものと見なし、ステップ４９００において「非類似」の決定を行う。そうでない場合、２つの画像は類似しているものと見なし、「類似」の決定を生じる。
【００６４】
本明細書に概要を説明する実施形態は、少なくとも２つの値を含む上記類似度を使用して、画像間の類似性又は非類似性を確認することを含む。
【００６５】
上で概要を説明した閾値処理方式の結果、ステップ４９００において二分決定が生じ、例えば「１」が「類似」を示し、「０」が「非類似」を示す。本発明の別の実施形態において、ステップ４９００の決定は二分ではなく、少なくとも３つの値を含む。このような場合、処理ステップ４９００の結果の記述には、「決定」という用語よりも「尤度」という用語のほうが優れている。例えば、本発明の一実施形態において、ステップ４９００は３つの閾値を用いる。類似度が第１の閾値を下回る場合、「非類似」を示す類似性の尤度「０」を生じる。類似度が第１の閾値を上回るが、第１の閾値よりも高い第２の閾値を下回る場合、「おそらく非類似」を示す類似性の尤度「１」を生じる。類似度が第２の閾値を上回るが、第２の閾値よりも高い第３の閾値を下回る場合、「おそらく類似」を示す類似性の尤度「２」を生じる。類似度が第３の閾値を上回る場合、「類似」を示す類似性の尤度「３」を生じる。本発明のさらに別の実施形態において、尤度は、閾値処理によってではなく、類似度の一定範囲（例えば０〜１）への正規化により生成される。
【００６６】
図４に従う本発明の好ましい実施形態において、ステップ４９００は、二分決定又は多値の尤度を生じる。ここで、当該尤度は、一定範囲（例えば０〜１）への正規化後にステップ４４００において生成される類似度であってもよい。本発明の代替的な実施形態では、ステップ４９００は全く実施されず、本発明による処理の最終的な結果は、ステップ４４００によって生成される正規化されていない類似度である。
【００６７】
ステップ４９００において行われる類似性の評価の意味は、本発明を実施する用途に依存する。
【００６８】
本発明の一実施形態において、Ｆｉ及びＦｊは時間順の画像である。例えば、これらはビデオＦｚのフレームであり、ＦｊとＦｉの間にフレームの切れ目（例えばショット遷移又は照明効果等）が存在するかどうかを確かめることを目的とする。その場合、ステップ４９００における決定は、ＦｊとＦｉの類似度がそのようなフレームの切れ目を示すかどうかとなる。このようなシステムは、ビデオを分割する目的で用いられることになる。このような用途において、ステップ４９００の好ましい出力は二分決定であり、ビデオの分割を可能にする。
【００６９】
本発明の別の実施形態において、Ｆｊ及びＦｉは時間順でない個別の画像である。例えば、Ｆｊは一組の画像Ｆｚの画像であり、ＦｉはＦｚ内部又は外部の別の画像であり、Ｆｚ中の、Ｆｉに類似している画像を見出すことを目的とする。その場合、ステップ４９００の決定は、ＦｊとＦｉの類似度が、それらの画像が類似していることを示すかどうかとなる。このようなシステムは、問い合わせによる画像の検索に、又はデータベース中の画像の分類に用いられる。そのような用途において、ステップ４９００の好ましい出力は、二分決定ではなく、多値の尤度、好ましくは一定範囲に正規化された類似度であり、ランク付けされた類似画像リストの作成を可能にする。
【００７０】
上記は、本発明の２つの可能な用途に過ぎない。
【００７１】
本発明の一実施形態において、ステップ４４００の記述子Ｖｉ及びＶｊの一方又は両方は画像ではなく画像群を表す。
【００７２】
例えば、本発明の一実施形態において、Ｖｊは、画像クラスタＦｊを形成する画像Ｆｊ１，Ｆｊ２，．．．，Ｆｊｇの記述子Ｖｊ１，Ｖｊ２，．．．，Ｖｊｇの関数（例えば平均(average)又は中央値(median)）である。例えば、Ｆｊは車を表す画像クラスタであり得る。その場合、画像Ｆｉについて、記述子Ｖｉ及びＶｊ間の類似性を確認することは、Ｆｉが特定の画像に類似しているかどうかではなく、それが特定の画像クラス又は画像クラスタに類似しているかどうかを示す。一組の画像Ｆｚは、そのようなクラスタを任意数含むことができ、そのような処理は、所与の画像が最も良く適合する特定のクラスタを示すことになる。さらに、クラスタは、Ｖｊによってだけでなく、その画像の記述子の共分散行列等の他の統計量によっても表現することができる。共分散行列は、ステップ４４００において、より複雑な類似度（例えばマハラノビス距離又は最尤度）の計算を可能にする。
【００７３】
ビデオを分割するための本発明の別の実施形態において、ＶｊはフレームＦｊ１，Ｆｊ２，．．．，Ｆｊｇの記述子Ｖｊ１，Ｖｊ２，．．．，Ｖｊｇの関数（例えば平均又は中央値）である。これらのフレームは、全てがフレームＦｉに先行しても、全てがそれに後続しても、又は、一部が先行して一部が後続してもよい。
【００７４】
本明細書に概要を説明する実施形態は、少なくとも２つの値を含む上記類似度を使用して、画像間の類似性又は非類似性を確認することを含む。
【００７５】
ビデオを分割するための本発明の上記の実施形態では、ステップ４９００において、２つのフレームＦｉ及びＦｊ間の類似度を用いて、フレームの切れ目を検出する。本発明の代替的な実施形態は、この類似度だけでなく、フレームＦｉ及びＦｊの周囲のフレーム間の類似度も用いる。
【００７６】
例えば、本発明の一実施形態において、ｊ＝ｉ−１であり、フレームの切れ目の検出は、類似度Ｄｉ＋ｋ−１，ｉ＋ｋに依拠し、∀ｋ∈［−ｔ１，ｔ２］である。好ましい実施形態において、ｔ１＝ｔ２＝ｔである。したがって、フレームＦｉ＋ｋは、フレームＦｉを中心とする時間窓を形成する。次に、次の場合にのみ、Ｆｉ−１及びＦｉ間でフレームの切れ目を検出する。
【００７７】
【数１３】
2006135938.tif 000015
【００７８】
式（１４）及び（１５）によれば、各類似度Ｄｉ−１，ｉは、Ｄｉ−１，ｉを中心とする２ｔ＋１のサイズの時間窓内にあると考えられる。その場合、Ｄｉ−１，ｉが時間窓内の最大距離であり、且つ、時間窓内の２番目に大きい距離よりも少なくともｔｈｒ倍大きい場合にのみ、フレームＦｉ−１とフレームＦｉの間で切れ目を検出する。このような時間適応的な方式は、フレーム間の高い動きレベルから生じる誤った検出の数を低減することを目的とする。フレームの切れ目を検出するためにそのような時系列を処理するそのような方式はいくつかある。
【００７９】
本発明の好ましい実施形態では、多くのスケールで、且つ複数のチャネルにわたって記述子を抽出することが明確に理解されるべきである。しかし、本発明の代替的な実施形態において、そうである必要はない。例えば、本発明の一実施形態では、複数のスケールで、但し単一のチャネルのみについて記述子を抽出する。本発明の別の実施形態では、単一のスケールについて、但し複数のチャネルにわたって記述子を抽出する。本発明のさらに別の実施形態では、単一のスケールで、且つ単一のチャネルについて記述子を抽出する。
【００８０】
さらに、上記の実施形態では、フレームの切れ目を検出するために、連続フレームの全ての対の処理を検討した。代替的な実施形態は、フレームをより粗く処理してもよい。代替的な実施形態は、４番目毎のフレームのみを処理し、さらに別の実施形態は、１６番目毎のフレームのみを処理する。このような向上により、ビデオ分割システムの速度がさらに上がる。
【００８１】
さらに、上記の説明は、各フレームがその画素値で表される未圧縮のデジタルビデオの処理に関する。本発明は、復元していないＭＰＥＧ圧縮ビデオにも直接適用することができる。
【００８２】
ＭＰＥＧビデオの性質は、当業者にはよく知られており、John Watkinson著「The MPEG Handbook」（「The MPEG Handbook: MPEG-1, MPEG-2, MPEG-4」, Focal Press, Oxford 2001, ISBN:0-240-51656-7）に専門的に記載されている。
【００８３】
ＭＰＥＧ圧縮ビデオに関する本発明の一実施形態では、ビデオのＩフレームのみを処理する。より具体的には、ＩフレームのＤＣ表現のみを処理する。すなわち、８×８画素の各ブロックについて、そのＤＣＴ変換のＤＣ成分のみを取る。事実上、ＩフレームのＤＣ表現は単に、８×８のブロック平均を用いて圧縮前の原フレームをリサンプリングしたものである。ＤＣ成分は、圧縮ビデオストリームから復元を行うことなく直接取り出すことができるため、本発明は、ＭＰＥＧ圧縮ビデオのＩフレームの処理に直接適用できることが明らかである。
【００８４】
本発明は、例えばコンピュータシステムにおいて、適切なソフトウェア及び／又はハードウェアの変更を施して実施することができる。例えば、本発明は、プロセッサ又は制御装置等の制御又は処理手段、メモリ、磁気記憶装置、ＣＤ、ＤＶＤ等の画像記憶手段を含むデータ記憶手段、ディスプレイ若しくはモニタ又はプリンタ等のデータ出力手段、キーボード等のデータ入力手段、及びスキャナ等の画像入力手段、又はそのような構成要素の任意の組み合わせ並びに追加の構成要素を有するコンピュータ又は同様の装置を用いて実施することができる。本発明の態様は、ソフトウェア及び／又はハードウェア形態で、又は特定用途向け装置において提供するか、又は集積回路等の特定用途向けモジュールを提供することができる。本発明の一実施形態による装置中のシステムの構成要素は、他の構成要素から遠隔して、例えばインターネットを介して設けられてもよい。
【００８５】
コンピュータシステムの形態の適切な装置のブロック図を図５に示し、この図において、制御ユニット１０１００は、画像記憶手段１０２００、記述子記憶手段１０３００及びディスプレイ１０４００に接続される。画像記憶手段１０２００は、上記の実施形態により表現又は比較される画像に対応するデータを記憶する。これは、１つの画像、複数の画像、画像クラスタ、画像シーケンス又は画像データベース全体に対応するデータであってもよい。記述子記憶手段１０３００は、データベースであってもよく、制御ユニット１０１００により計算される副記述子（sub-descriptors）を含む導出された記述子をすべて記憶する。制御ユニットの動作の結果は、ディスプレイ１０４００上でユーザに対して表示する。
【００８６】
「スケール」及び「解像度」という用語は、本明細書において置き換え可能に用いられる。画像の領域は画像全体又は画像の部分を意味し得る。
【図面の簡単な説明】
【００８７】
【図１】本発明の一実施形態によるＹチャネルのブロック平均リサンプリングプロセスを示す図である。
【図２Ａ】本発明の一実施形態における１つのスケールの記述子の計算を示す図である。
【図２Ｂ】本発明の一実施形態における１つのスケールの記述子の計算を示す図である。
【図２Ｃ】本発明の一実施形態における１つのスケールの記述子の計算を示す図である。
【図２Ｄ】本発明の一実施形態における１つのスケールの記述子の計算を示す図である。
【図３Ａ】本発明のさらなる実施形態による１つのスケールの記述子の計算を示す図である。
【図３Ｂ】本発明のさらなる実施形態による１つのスケールの記述子の計算を示す図である。
【図３Ｃ】本発明のさらなる実施形態による１つのスケールの記述子の計算を示す図である。
【図３Ｄ】本発明のさらなる実施形態による１つのスケールの記述子の計算を示す図である。
【図４】本発明の一実施形態による複数の画像を比較するフロー図である。
【図５】本発明の実施形態の実施に適した処理装置の概略図である。
【図１】
2006135938.tif 000016
【図２Ａ】
2006135938.tif 000017
【図２Ｂ】
2006135938.tif 000018
【図２Ｃ】
2006135938.tif 000019
【図２Ｄ】
2006135938.tif 000020
【図３Ａ】
2006135938.tif 000021
【図３Ｂ】
2006135938.tif 000022
【図３Ｃ】
2006135938.tif 000023
【図３Ｄ】
2006135938.tif 000024
【図４】
2006135938.tif 000025
【図５】
2006135938.tif 000026
【外国語明細書】
2006135938.tif 000027
2006135938.tif 000028
2006135938.tif 000029
2006135938.tif 000030
2006135938.tif 000031
2006135938.tif 000032
2006135938.tif 000033
2006135938.tif 000034
2006135938.tif 000035
2006135938.tif 000036
2006135938.tif 000037
2006135938.tif 000038
2006135938.tif 000039
2006135938.tif 000040
2006135938.tif 000041
2006135938.tif 000042
2006135938.tif 000043
2006135938.tif 000044
2006135938.tif 000045
2006135938.tif 000046
2006135938.tif 000047
2006135938.tif 000048
2006135938.tif 000049
2006135938.tif 000050
2006135938.tif 000051
2006135938.tif 000052
2006135938.tif 000053
2006135938.tif 000054
2006135938.tif 000055
2006135938.tif 000056
2006135938.tif 000057
2006135938.tif 000058
2006135938.tif 000059
2006135938.tif 000060
2006135938.tif 000061