JP5117670B2 - 画像及び画像群を表現する方法、画像又は画像群を比較する方法、画像又は画像群を検索する方法、各方法を実行する装置およびシステム、プログラム、及びコンピュータ読み取り可能な記憶媒体 - Google Patents

Description

本発明は、画像又は画像群を表現する方法及び装置、並びに、例えば画像シーケンスの切れ目の検出のため、又は画像の検索のために画像を比較する方法及び装置に関する。

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 3^rd 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）の方法に伴う別の欠点は、ハール分解の計算が、画像領域の係数をその領域内の全ての画素値に基づいて計算するために計算量の増加を伴うことである。

本発明では、例えば、所与の画像に類似している一組の画像から画像を検索するため、又はデジタルビデオ中のフレームの切れ目（例えばショット遷移又は照明及び他の効果）を検出するために、画像間の類似性を評価する方法を提案する。この方法は、空間的に敏感な色内容及び色相関の情報を１つ又は複数の画像スケールで、且つ１つ又は複数の画像チャネルにわたって取得する画像記述子の抽出に依拠する。この方法の１つの特徴は、以前の方法とは異なり、記述子が空間的に敏感な色内容及び色相関の情報を画像平面にわたって均一に、且つ複数のスケールで取得しながらも、上記のハール分解と比較してサイズが小さく、よって人工的な打ち切りプロセスを行う必要性が少なくなるように記述子を抽出できることである。本方法のもう１つの特徴は、以前の方法と異なり、記述子による原画像の完全な再構成が可能でありながら、計算負荷が上記のハール分解と比べて少ない記述子を抽出できることである。

上記に鑑みて、本発明の目的は、例えば所与の画像に類似している一組の画像から画像を検索するため、又はデジタルビデオ中のフレームの切れ目（例えばショット遷移又は照明及び他の効果）を検出するために、画像間の類似性を評価するための改良された方法を提供することである。

ビデオ分割のために、提案する方法論は、非圧縮デジタルビデオフレームとＭＰＥＧ圧縮デジタルビデオフレームの両方の再現を可能にする。後者の場合、復元を行うことなくＩフレームを表現することができる。

本発明の態様を添付の特許請求の範囲に記載する。

一実施形態の特徴は、
（ｉ）空間的に敏感な色内容及び色相関の情報を１つ又は複数の画像スケールで、且つ１つ又は複数の画像チャネルにわたって取得する画像記述子の抽出であって、少なくとも１つのスケールに固有でチャネルに固有の画像表現の記述子は、
少なくとも１つの記述子要素タイプの全ての領域記述子要素を、それぞれの領域の画素のサブセットのみを用いて計算すること、
及び／又は
全ての記述子要素タイプの全ての領域記述子要素の計算に用いる画素は、それぞれの領域の画素の単なるサブセットであること、
及び／又は
記述子要素の総数は上記表現の画素数よりも少なく、上記特性は、記述子のいかなる後処理（例えば打ち切り）にも依存せず記述子抽出プロセスに固有であること
を特徴とする、画像記述子の抽出、
（ｉｉ）上記記述子を組み合わせて１つのマルチスケールでマルチチャネルの記述子にすること、及び
（ｉｉｉ）結果として得られる記述子を使用して、画像間の類似性を評価すること
を含む。

本発明の特定の実施形態の概要を以下で、添付図面を参照して説明する。

本発明の第１の実施形態は記述子の抽出に関する。

デジタル画像Ｆ_ｉ（ｘ，ｙ）を検討する。ここで、（ｘ，ｙ）は空間座標を表し、ｘ＝０．．．Ｍ−１及びｙ＝０．．．Ｎ−１である。本発明の一実施形態において、Ｆ_ｉは色空間ＹＣ_ｂＣ_ｒで表されるが、これに制限されるものではなく、本発明は、いかなるチャネル数のいかなる色空間にも適用可能である。本発明の一実施形態において、Ｆ_ｉの空間解像度は７２０×５７６画素である、すなわち、Ｍ＝７２０及びＮ＝５７６であるが、これに限定されるものではなく、本発明は、いかなる空間解像度にも適用可能である。本発明の一実施形態において、記述子を抽出する最高解像度として６４×６４画素を選択するが、これに限定されるものではなく、本発明は他の解像度にも適用可能である。したがって、Ｆ_ｉをリサンプリングして、６４×６４画素の画像Ｆ_{ｉ（６４×６４）}を得る。本発明の一実施形態において、このリサンプリングプロセスは、図１に示すような単純なブロック平均プロセスであるが、リサンプリング機構の選択は限定されない。より具体的に言えば、図１は、Ｙチャネルのブロック平均リサンプリングプロセスを示すが、これに限定されるものではなく、このプロセスは、いかなる色空間のいかなるチャネルにも用いることができる。本発明の別の実施形態において、記述子を抽出する最高スケールはＦ_ｉの解像度に一致し、最初のリサンプリングは必要とされない。

図２は、本発明の一実施形態における、このスケールの記述子の計算を示す。より具体的には、図２は、Ｙチャネルの記述子の計算を示すが、これに限定されるものではなく、同様の手法を全てのカラーチャネルに適用する。図２Ａにおいて、２×２の窓を画像の左上の角に適用する。この窓は局所近傍を指定する。この近傍の画素Ｆ^Ｙ _{ｉ（６４×６４）}（０，０），Ｆ^Ｙ _{ｉ（６４×６４）}（１，０），Ｆ^Ｙ _{ｉ（６４×６４）}（０，１）及びＦ^Ｙ _{ｉ（６４×６４）}（１，１）について、記述子要素χ_１〜χ_４を次のように計算することができる。

上記の式において、要素χ_１は色内容情報を取得し、要素χ_２、χ_３及びχ_４は色相関情報を取得する。

Ｆ^Ｙ _{ｉ（６４×６４）}の記述子をＶ^Ｙ _{ｉ（６４×６４）}とすると、これらの値は、次のように記述子に書き換えることができる。

次に、図２Ｂに示すように、２×２の窓を２画素右にスライドさせ、画素Ｆ^Ｙ _{ｉ（６４×６４）}（２，０），Ｆ^Ｙ _{ｉ（６４×６４）}（３，０），Ｆ^Ｙ _{ｉ（６４×６４）}（２，１）及びＦ^Ｙ _{ｉ（６４×６４）}（３，１）を含む新たな近傍を形成する。記述子要素χ_１〜χ_４を再び、新たな画素値について計算し、その後、記述子位置Ｖ^Ｙ _{ｉ（６４×６４）}（５）〜Ｖ^Ｙ _{ｉ（６４×６４）}（８）に格納する。図２Ｃ及び図２Ｄに示すように、一組の行について計算が全て完了すると、スライド窓を２画素下に移動させ、左から右へのスライドを再び開始し、画像全体を処理し終えるまで続ける。これにより、Ｙ平面について６４×６４画素のスケールで、画像の空間的に敏感な色内容及び色相関を取得する記述子Ｖ^Ｙ _{ｉ（６４×６４）}の計算が完了する。

本明細書に概要を説明する発明は、空間的に敏感な色内容及び色相関の情報を取得する記述子の計算を含む。

別の実施形態は、記述子要素χ_１〜χ_４を、以下に記載するように導出される記述子要素ψ_１及びψ_２で置き換える。

上に示す式（Ｉ）及び（ＩＩ）において、ψ_１は色内容情報を取得し、ψ_２は色相関情報を取得する。記述子要素の数は、記述子要素の導出に使用される画素数よりも少ない。

さらに別の実施形態は、記述子要素χ_１〜χ_４を、以下に記載するように導出される記述子要素φ_１〜φ_４で置き換える。

上に示す式（ＩＩＩ）〜（ＶＩ）において、φ_１は色内容情報を取得し、φ_２〜φ_４は色相関情報を取得する。

本発明の別の実施形態では、図３の方式により記述子要素を抽出する。図３Ａにおいて、４×４の窓を画像の左上の角に適用する。この窓は、１６画素を含む局所近傍を指定する。この近傍の画素について、以下の記述子要素を計算する。

上記の式において、ψ_１は色内容情報を取得し、ψ_２、ψ_３及びψ_４は色相関情報を取得する。当業者は、式（６）〜（９）を変更して、必要な計算の数を減らしてもよいことを理解するであろう。

これらの値は、一連の式（lines of equation）（５）に沿って記述子Ｖ^Ｙ _{ｉ（６４×６４）}として書き表すことができ、次に、図３Ｂに示すように、４×４の窓を４画素右にスライドさせて新たな近傍を形成し、新たな画素値について記述子要素を再び計算し、以下同様の操作を行う。図３Ｃ及び図３Ｄに示すように、一組の行の計算が全て完了すると、スライド窓を２画素下へ移動させ、左から右へのスライドを再び開始し、画像全体を処理し終えるまで続ける。

本発明の代替的な実施形態において、色内容及び／又は色相関の記述子要素の計算は、近傍画素の関数（例えば中央値、最大値、最小値等）に依拠してもよい。

さらに、上記の説明は、２×２画素及び４×４画素のサイズのスライド近傍窓を検討するが、これに限定されるものではない。代替的な実施形態は、例えば、所与の計算に関する要求又は近傍測定プロセス自体に合わせて、任意のサイズ及び／又は幾何形状及び／又はスライドステップを近傍窓に指定し、重複する窓又は重複しない窓を生じることができる。

上記の説明では、Ｆ^Ｙ _{ｉ（６４×６４）}の全ての位置で同一の近傍窓及び記述子抽出プロセスを用いる。代替的な実施態様では、そうである必要はない。代替的な実施形態は、画像中の異なる位置で異なる近傍パラメータ及び／又は記述子抽出プロセスを使用してもよい。例えば、本発明の代替的な実施形態は、速い記述子抽出プロセスを画像の周辺に用い、遅いが強力な記述子抽出プロセスを画像の中心に用いる。

次に、Ｆ^Ｙ _{ｉ（６４×６４）}を新たなより低いスケールにリサンプリングする。一実施形態において、この新たなスケールは３２×３２画素である。次に、６４×６４の画像の場合と全く同じ方法で新たな記述子Ｖ^Ｙ _{ｉ（３２×３２）}を計算する。なお、このリサンプリングは実際には計算を必要としない場合もあり得る。式（１）に見られるように、この新たな画素値は、χ_１の値として以前に計算し、Ｖ^Ｙ _{ｉ（６４×６４）}（１），Ｖ^Ｙ _{ｉ（６４×６４）}（５），Ｖ^Ｙ _{ｉ（６４×６４）}（９），．．．，Ｖ^Ｙ _{ｉ（６４×６４）}（４０９３）に格納している。一実施形態では、このように、記述子Ｖ^Ｙ _{ｉ（６４×６４）}，Ｖ^Ｙ _{ｉ（３２×３２）}，Ｖ^Ｙ _{ｉ（１６×１６）}，Ｖ^Ｙ _{ｉ（８×８）}，Ｖ^Ｙ _{ｉ（４×４）}，及びＶ^Ｙ _{ｉ（２×２）}を計算する。

本明細書において概要を説明する発明は、画像Ｆ_ｉの１つ又は複数のスケールで記述子を抽出することを含む。上記の説明において、最も細かい又は最大又は最高スケール、最も粗い又は最小又は最低スケール、スケールの数及びスケール間の関係は、本発明の可能な一実施形態を示すに過ぎず、代替的な実施形態は、例えばシステムの計算能力に合うように、異なるそのようなパラメータを使用してもよい。

本発明の一実施形態では、以降の処理を行う前に、これらのスケールに固有の記述子から特定の要素を除去する。本発明の一実施形態では、２^ｂ×２^ｂ、２^ｂ−１×２^ｂ−１、２^ｂ−２×２^ｂ−２等、例えば、６４×６４、３２×３２、１６×１６等のスケールでの式（１）〜（４）において概要を説明した記述子抽出プロセスの場合、Ｖ^Ｙ _ｉのχ_１要素を、最低スケールのχ_１要素を除いて全て除去してもよい。これは、２^ｂ−ｋ×２^ｂ−ｋのスケールのχ_１要素を、２^{ｂ−ｋ−１}×２^{ｂ−ｋ−１}のスケールのχ_１値、並びに２^ｂ−ｋ×２^ｂ−ｋのスケールのχ_２要素、χ_３要素、及びχ_４要素から直接計算できるためである。なお、この特性は常に当てはまるわけではない。例えば、２^ｂ×２^ｂ、２^ｂ−２×２^ｂ−２、２^ｂ−４×２^ｂ−４等、例えば、６４×６４、１６×１６、４×４等のスケールで記述子を計算する場合には当てはまらない。また、記述子抽出プロセスの一部としてχ_１要素、χ_２要素、χ_３要素及びχ_４要素のサブセットのみを計算する場合には当てはまらない。同一の特性が式（ＩＩＩ）〜（ＶＩ）の変換に当てはまる。

同一の記述子抽出プロセスをＦ_ｉのＣ_ｂチャネル及びＣ_ｒチャネルに適用すると、記述子Ｖ^Ｃｂ _{ｉ（６４×６４）}，．．．，Ｖ^Ｃｂ _{ｉ（２×２）}及びＶ^Ｃｒ _{ｉ（６４×６４）}，．．．，Ｖ^Ｃｒ _{ｉ（２×２）}が得られる。これらのスケールに固有でチャネルに固有の記述子は、全体で、画像の空間的に敏感な色内容及び色相関の情報を複数のスケールで、且つ複数のチャネルにわたって取得する。

上記の説明において、Ｆ_ｉはＹＣ_ｂＣ_ｒ色空間にあると仮定し、記述子の抽出に全てのチャネルを用いる。代替的な実施態様は、記述子を計算する前に画像を新たな色空間で表現してもよいし、かつ／又は記述子の計算に色平面のサブセットのみを使用してもよい。

上記の説明では、Ｆ_ｉの異なるカラーチャネルにわたる記述子を同一スケールで計算する。代替的な実施態様では、そうである必要はない。例えば、本発明の代替的な実施形態はＹチャネルの記述子を、Ｃ_ｂ及び／又はＣ_ｒチャネルの記述子よりも多いスケールで、及び／又はそれとは異なるスケールで計算する。このような微調整により、特定の画像又はビデオ素材により良く適合して、性能を高めることができる。

上記の説明では、Ｆ_ｉの全てのカラーチャネルに同一の近傍窓及び記述子抽出プロセスを用いる。代替的な実施態様では、そうである必要はない。代替的な実施形態は、チャネル毎に異なる近傍パラメータ及び／又は記述子抽出プロセスを使用してもよい。例えば、本発明の代替的な実施形態は、速い記述子抽出プロセスをＣ_ｂチャネル及びＣ_ｒチャネルに用い、遅いが強力な記述子抽出プロセスをＹチャネルに用いる。このような微調整により、特定の画像又はビデオ素材により良く適合して、システムの性能を高めることができる。

本発明の一実施形態では、記述子要素の一部又は全てを、整数部と小数部を持つ実数で表現する。本発明の別の実施形態では、記述子要素の一部又は全てを、例えば小数部を切り捨てるか又は切り上げる(round)ことによって、整数形式で表現する。本発明のさらに別の実施形態では、記述子要素の一部又は全てを、スケーリングによって整数形式で表現する。例えば、式（１）〜（４）は、小数部が３つの値、すなわち、．２５、．５０及び．７５しか取り得ない実数を生成する。記述子要素χ_１に４の値を掛け、記述子要素χ_２、χ_３及びχ_４に２の値を掛けることによって、情報を全く損失せずに整数表現が得られる。本発明のさらに別の実施形態では、記述子要素の一部又は全てを、何らかの方法で整数形式で表現し、その後、例えば３ビット又は４ビット長の短い値に量子化する。

したがって、本発明の一実施形態では、画像Ｆ_ｉをその記述子Ｖ^Ｃ１ _{ｉ（Ｃ１ＳＣｑ）}，．．．，Ｖ^Ｃ１ _{ｉ（Ｃ１ＳＣ１）}，Ｖ^Ｃ２ _{ｉ（Ｃ２ＳＣｑ）}，．．．，Ｖ^Ｃ２ _{ｉ（Ｃ２ＳＣ１）}，．．．，Ｖ^Ｃｐ _{ｉ（ＣｐＳＣｑ）}，．．．，Ｖ^Ｃｐ _{ｉ（ＣｐＳＣ１）}で表現する。ここで、Ｃ１，Ｃ２，．．．，ＣｐはＦ_ｉの第１、第２及び第ｐのカラーチャネルであり、Ｃ１ＳＣｑはチャネルＣ１の最高の記述子スケールであり、Ｃ１ＳＣ１はチャネルＣ１の最低の記述子スケールであり、Ｃ２ＳＣｑはチャネルＣ２の最高の記述子スケールであり、Ｃ２ＳＣ１はチャネルＣ２の最低の記述子スケールであり、以下同様である。これらのスケールに固有でチャネルに固有の記述子は、全体で、画像の空間的に敏感な色内容及び色相関の情報を複数のスケール（好ましくは２つ以上）で、且つ複数のチャネル（好ましくは２つ以上）にわたって取得する。

次に、これらの記述子を融合すなわち連結させて、次の処理のために１つの記述子にする。これを図４に示す。

この実施形態では、ステップ４１００において、上記で説明したように、スケールに固有でチャネルに固有の記述子を抽出する。ステップ４２５０において、これらの記述子を融合させてマルチスケールでマルチチャネルの記述子Ｖ_ｉにする。ステップ４４００において、記述子Ｖ_ｉ及びＶ_ｊを用いて、画像Ｆ_ｉと画像Ｆ_ｊの類似度（similarity measure）Ｄ_ｊ，ｉを計算する。ステップ４９００において、類似度を用いて、２つの画像の類似性又は非類似性を評価する。

次に、このプロセスの様々なステップをより詳しく検討する。

ステップ４４００において、類似度の計算には多くのオプションがある。例えば、本発明の一実施形態において、それぞれｎ個の要素からなる２つの記述子Ｖ_ｉ及びＶ_ｊの間のＬ１距離は、次式により与えられる類似度として計算することができる。

本明細書に概要を説明する発明は、画像記述子を使用して、画像間の少なくとも２つの値を含む類似度を計算することを含む。

記述子の距離を計算するための式（１０）のＬ１距離は、本発明の可能な１実施態様に関連するに過ぎない。代替的な実施態様は、式（１０）を、Ｌ２距離を計算する次式（１１）で置き換える。

このような様々な距離メトリックが上記の関連文献に記載されている。

さらに、代替的な実施態様は、式（１０）を次式（１２）で置き換える。この式（１２）は、重み付きＬ１距離を計算する。

ここで、ｗ（ｌ）はｌ番目の記述子要素の重み係数である。さらに、重みの適用はまた、式（１１）のＬ２距離、又は上記文献に記載されている任意の他の適切な距離メトリックとともに用いてもよい。

類似度の処理には多くのオプションがある。本発明の一実施形態では、ステップ４９００において、類似度Ｄ_ｊ，ｉに閾値処理関数を適用する。すなわち、ある閾値ｔｈｒについて、

である場合、２つの画像は異なるものと見なし、ステップ４９００において「非類似」の決定を行う。そうでない場合、２つの画像は類似しているものと見なし、「類似」の決定を生じる。

本明細書に概要を説明する実施形態は、少なくとも２つの値を含む上記類似度を使用して、画像間の類似性又は非類似性を確認することを含む。

上で概要を説明した閾値処理方式の結果、ステップ４９００において二分決定が生じ、例えば「１」が「類似」を示し、「０」が「非類似」を示す。本発明の別の実施形態において、ステップ４９００の決定は二分ではなく、少なくとも３つの値を含む。このような場合、処理ステップ４９００の結果の記述には、「決定」という用語よりも「尤度」という用語のほうが優れている。例えば、本発明の一実施形態において、ステップ４９００は３つの閾値を用いる。類似度が第１の閾値を下回る場合、「非類似」を示す類似性の尤度「０」を生じる。類似度が第１の閾値を上回るが、第１の閾値よりも高い第２の閾値を下回る場合、「おそらく非類似」を示す類似性の尤度「１」を生じる。類似度が第２の閾値を上回るが、第２の閾値よりも高い第３の閾値を下回る場合、「おそらく類似」を示す類似性の尤度「２」を生じる。類似度が第３の閾値を上回る場合、「類似」を示す類似性の尤度「３」を生じる。本発明のさらに別の実施形態において、尤度は、閾値処理によってではなく、類似度の一定範囲（例えば０〜１）への正規化により生成される。

図４に従う本発明の好ましい実施形態において、ステップ４９００は、二分決定又は多値の尤度を生じる。ここで、当該尤度は、一定範囲（例えば０〜１）への正規化後にステップ４４００において生成される類似度であってもよい。本発明の代替的な実施形態では、ステップ４９００は全く実施されず、本発明による処理の最終的な結果は、ステップ４４００によって生成される正規化されていない類似度である。

ステップ４９００において行われる類似性の評価の意味は、本発明を実施する用途に依存する。

本発明の一実施形態において、Ｆ_ｉ及びＦ_ｊは時間順の画像である。例えば、これらはビデオＦ_ｚのフレームであり、Ｆ_ｊとＦ_ｉの間にフレームの切れ目（例えばショット遷移又は照明効果等）が存在するかどうかを確かめることを目的とする。その場合、ステップ４９００における決定は、Ｆ_ｊとＦ_ｉの類似度がそのようなフレームの切れ目を示すかどうかとなる。このようなシステムは、ビデオを分割する目的で用いられることになる。このような用途において、ステップ４９００の好ましい出力は二分決定であり、ビデオの分割を可能にする。

本発明の別の実施形態において、Ｆ_ｊ及びＦ_ｉは時間順でない個別の画像である。例えば、Ｆ_ｊは一組の画像Ｆ_ｚの画像であり、Ｆ_ｉはＦ_ｚ内部又は外部の別の画像であり、Ｆ_ｚ中の、Ｆ_ｉに類似している画像を見出すことを目的とする。その場合、ステップ４９００の決定は、Ｆ_ｊとＦ_ｉの類似度が、それらの画像が類似していることを示すかどうかとなる。このようなシステムは、問い合わせによる画像の検索に、又はデータベース中の画像の分類に用いられる。そのような用途において、ステップ４９００の好ましい出力は、二分決定ではなく、多値の尤度、好ましくは一定範囲に正規化された類似度であり、ランク付けされた類似画像リストの作成を可能にする。

上記は、本発明の２つの可能な用途に過ぎない。

本発明の一実施形態において、ステップ４４００の記述子Ｖ_ｉ及びＶ_ｊの一方又は両方は画像ではなく画像群を表す。

例えば、本発明の一実施形態において、Ｖ_ｊは、画像クラスタＦ_ｊを形成する画像Ｆ_ｊ１，Ｆ_ｊ２，．．．，Ｆ_ｊｇの記述子Ｖ_ｊ１，Ｖ_ｊ２，．．．，Ｖ_ｊｇの関数（例えば平均(average)又は中央値(median)）である。例えば、Ｆ_ｊは車を表す画像クラスタであり得る。その場合、画像Ｆ_ｉについて、記述子Ｖ_ｉ及びＶ_ｊ間の類似性を確認することは、Ｆ_ｉが特定の画像に類似しているかどうかではなく、それが特定の画像クラス又は画像クラスタに類似しているかどうかを示す。一組の画像Ｆ_ｚは、そのようなクラスタを任意数含むことができ、そのような処理は、所与の画像が最も良く適合する特定のクラスタを示すことになる。さらに、クラスタは、Ｖ_ｊによってだけでなく、その画像の記述子の共分散行列等の他の統計量によっても表現することができる。共分散行列は、ステップ４４００において、より複雑な類似度（例えばマハラノビス距離又は最尤度）の計算を可能にする。

ビデオを分割するための本発明の別の実施形態において、Ｖ_ｊはフレームＦ_ｊ１，Ｆ_ｊ２，．．．，Ｆ_ｊｇの記述子Ｖ_ｊ１，Ｖ_ｊ２，．．．，Ｖ_ｊｇの関数（例えば平均又は中央値）である。これらのフレームは、全てがフレームＦ_ｉに先行しても、全てがそれに後続しても、又は、一部が先行して一部が後続してもよい。

本明細書に概要を説明する実施形態は、少なくとも２つの値を含む上記類似度を使用して、画像間の類似性又は非類似性を確認することを含む。

ビデオを分割するための本発明の上記の実施形態では、ステップ４９００において、２つのフレームＦ_ｉ及びＦ_ｊ間の類似度を用いて、フレームの切れ目を検出する。本発明の代替的な実施形態は、この類似度だけでなく、フレームＦ_ｉ及びＦ_ｊの周囲のフレーム間の類似度も用いる。

例えば、本発明の一実施形態において、ｊ＝ｉ−１であり、フレームの切れ目の検出は、類似度Ｄ_{ｉ＋ｋ−１，ｉ＋ｋ}に依拠し、∀ｋ∈［−ｔ_１，ｔ_２］である。好ましい実施形態において、ｔ１＝ｔ２＝ｔである。したがって、フレームＦ_ｉ＋ｋは、フレームＦ_ｉを中心とする時間窓を形成する。次に、次の場合にのみ、Ｆ_ｉ−１及びＦ_ｉ間でフレームの切れ目を検出する。

式（１４）及び（１５）によれば、各類似度Ｄ_{ｉ−１，ｉ}は、Ｄ_{ｉ−１，ｉ}を中心とする２ｔ＋１のサイズの時間窓内にあると考えられる。その場合、Ｄ_{ｉ−１，ｉ}が時間窓内の最大距離であり、且つ、時間窓内の２番目に大きい距離よりも少なくともｔｈｒ倍大きい場合にのみ、フレームＦ_ｉ−１とフレームＦ_ｉの間で切れ目を検出する。このような時間適応的な方式は、フレーム間の高い動きレベルから生じる誤った検出の数を低減することを目的とする。フレームの切れ目を検出するためにそのような時系列を処理するそのような方式はいくつかある。

本発明の好ましい実施形態では、多くのスケールで、且つ複数のチャネルにわたって記述子を抽出することが明確に理解されるべきである。しかし、本発明の代替的な実施形態において、そうである必要はない。例えば、本発明の一実施形態では、複数のスケールで、但し単一のチャネルのみについて記述子を抽出する。本発明の別の実施形態では、単一のスケールについて、但し複数のチャネルにわたって記述子を抽出する。本発明のさらに別の実施形態では、単一のスケールで、且つ単一のチャネルについて記述子を抽出する。

さらに、上記の実施形態では、フレームの切れ目を検出するために、連続フレームの全ての対の処理を検討した。代替的な実施形態は、フレームをより粗く処理してもよい。代替的な実施形態は、４番目毎のフレームのみを処理し、さらに別の実施形態は、１６番目毎のフレームのみを処理する。このような向上により、ビデオ分割システムの速度がさらに上がる。

さらに、上記の説明は、各フレームがその画素値で表される未圧縮のデジタルビデオの処理に関する。本発明は、復元していないＭＰＥＧ圧縮ビデオにも直接適用することができる。

ＭＰＥＧビデオの性質は、当業者にはよく知られており、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）を含む導出された記述子をすべて記憶する。制御ユニットの動作の結果は、ディスプレイ１０４００上でユーザに対して表示する。

「スケール」及び「解像度」という用語は、本明細書において置き換え可能に用いられる。画像の領域は画像全体又は画像の部分を意味し得る。

本発明の一実施形態によるＹチャネルのブロック平均リサンプリングプロセスを示す図である。 本発明の一実施形態における１つのスケールの記述子の計算を示す図である。 本発明の一実施形態における１つのスケールの記述子の計算を示す図である。 本発明の一実施形態における１つのスケールの記述子の計算を示す図である。 本発明の一実施形態における１つのスケールの記述子の計算を示す図である。 本発明のさらなる実施形態による１つのスケールの記述子の計算を示す図である。 本発明のさらなる実施形態による１つのスケールの記述子の計算を示す図である。 本発明のさらなる実施形態による１つのスケールの記述子の計算を示す図である。 本発明のさらなる実施形態による１つのスケールの記述子の計算を示す図である。 本発明の一実施形態による複数の画像を比較するフロー図である。 本発明の実施形態の実施に適した処理装置の概略図である。

Claims (30)

1. 画像を表現する方法であって、
   前記画像の少なくとも１つの領域の画素値を用いて取得した少なくとも１つの色情報及び少なくとも１つの色相関情報に関する記述子要素を導出するステップと、
   前記少なくとも１つの色情報及び前記少なくとも１つの色相関情報に関する記述子要素に基づいて、少なくとも１つの記述子を導出して前記画像を表現するステップと
   を有し、
   前記領域の前記少なくとも１つの色情報及び前記少なくとも１つの色相関情報に関する記述子要素は、前記領域の近傍の画素のみを用いて導出される
   画像を表現する方法。
2. 前記少なくとも１つの色情報に関する記述子要素は、前記領域の画素平均を表し、
   前記少なくとも１つの色相関情報に関する記述子要素は、前記領域の画素に関する差分関数を表す、
   請求項１に記載の方法。
3. 前記少なくとも１つの色相関情報に関する記述子要素は、２つの画素値の差、又は画素値の２つの総和の差に基づいて表される、請求項１または２に記載の方法。
4. 前記導出される記述子要素の数は、該記述子要素の導出に使用される画素数よりも少ない、請求項１ないし請求項３のいずれか一項に記載の方法。
5. 前記記述子は、前記画像の複数の重複する領域又は重複しない領域について導出された前記記述子要素により生成される、請求項１ないし請求項４のいずれか一項に記載の方法。
6. 前記画像を処理して、複数のスケールの画像を生成し、各スケールの画像の表現を導出するステップと、
   各スケールの画像の表現に基づいて、前記複数のスケールの画像の記述子を導出するステップと
   を有する請求項１ないし請求項５のいずれか一項に記載の方法。
7. 前記画像の複数のカラーチャネルの各々について前記画像を処理して、各カラーチャネルの画像の表現を導出するステップと、
   各カラーチャネルの画像の表現に基づいて、前記複数のカラーチャネルの画像の記述子を導出するステップと
   を有する請求項１ないし請求項６のいずれか一項に記載の方法。
8. 前記画像の異なる位置の領域で、異なる記述子導出プロセスが用いられる、請求項１ないし請求項７のいずれか一項に記載の方法。
9. 前記記述子は、ＭＰＥＧ符号化Ｉフレームから、復号を行うことなく直接導出される、請求項１ないし請求項８のいずれか一項に記載の方法。
10. １つの画像の複数の記述子を関連付けて、１つの記述子を形成するステップを有する請求項１ないし請求項９のいずれか一項に記載の方法。
11. 全ての記述子要素を単一のカラーチャネルについて導出する、請求項１ないし請求項１０のいずれか一項に記載の方法。
12. 色空間ＹＣｒＣｂを用いる、請求項１ないし請求項１１のいずれか一項に記載の方法。
13. Ｙ輝度チャネルの記述子要素を導出することを含む、請求項１ないし請求項１２のいずれか一項に記載の方法。
14. 画像群を表現する方法であって、
    請求項１ないし請求項１３のいずれか一項に記載の画像を表現する方法を用いて、前記画像群の各画像の表現を導出するステップと、
    前記画像群の各画像の表現に対して関数を適用して、前記画像群を表現するステップと
    を有する画像群を表現する方法。
15. 前記関数は、平均、中央値、算術平均、共分散のいずれかの統計測度を使用する、請求項１４に記載の方法。
16. 請求項１ないし請求項１５のいずれか一項に記載の画像又は画像群を表現する方法を用いて表現を導出するステップと、
    前記画像又は画像群の表現を比較するステップと、
    前記比較の結果を用いて、画像又は画像群の類似性を判定するステップと
    を有する画像又は画像群を比較する方法。
17. 請求項１ないし請求項１５のいずれか一項に記載の画像又は画像群を表現する方法を用いて画像シーケンスの一部である画像の表現を導出するステップと、
    前記画像又は画像群の表現を比較するステップと、
    前記比較の結果を用いて、前記画像間でフレームの切れ目が起こったかどうか判定するステップと
    を有する画像又は画像群を比較する方法。
18. 請求項１６に記載の画像又は画像群を比較する方法を用いて、画像又は画像群の類似性を判定するステップと、
    前記類似性に基づいて、前記画像又は画像群を検索するステップと
    を有する画像又は画像群を検索する方法。
19. 記述子要素を導出する手段と、画像又は画像群を表現する手段とを備え、請求項１ないし請求項１５のいずれか一項に記載の方法を実行することによって画像又は画像群を表現する装置。
20. 記述子要素を導出する手段と、画像又は画像群を表現する手段と、画像又は画像群の表現を比較する手段と、画像又は画像群の類似性を判定する手段とを備え、請求項１６または１７に記載の方法を実行することによって画像又は画像群を比較する装置。
21. 記述子要素を導出する手段と、画像又は画像群を表現する手段と、画像又は画像群の表現を比較する手段と、画像又は画像群の類似性を判定する手段と、画像又は画像群を検索する手段とを備え、請求項１８に記載の方法を実行することによって画像又は画像群を検索する装置。
22. 画像記述子を記憶する記憶手段と、前記各手段を制御する処理手段とを備える、請求項１９ないし請求項２１のいずれか一項に記載の装置。
23. 記述子要素を導出する手段と、画像又は画像群を表現する手段とを備え、請求項１ないし請求項１５のいずれか一項に記載の方法を実行することによって画像又は画像群を表現するシステム。
24. 記述子要素を導出する手段と、画像又は画像群を表現する手段と、画像又は画像群の表現を比較する手段と、画像又は画像群の類似性を判定する手段とを備え、請求項１６または請求項１７に記載の方法を実行することによって画像又は画像群を比較するシステム。
25. 記述子要素を導出する手段と、画像又は画像群を表現する手段と、画像又は画像群の表現を比較する手段と、画像又は画像群の類似性を判定する手段と、画像又は画像群を検索する手段とを備え、請求項１８に記載の方法を実行することによって画像又は画像群を検索するシステム。
26. 画像記述子を記憶する記憶手段と、前記各手段を制御する処理手段とを備える、請求項２３ないし請求項２５のいずれか一項に記載のシステム。
27. コンピュータに、請求項１ないし請求項１５のいずれか一項に記載に方法を実行させることによって、前記コンピュータに画像を表現させるプログラム。
28. コンピュータに、請求項１６または請求項１７に記載に方法を実行させることによって、前記コンピュータに画像又は画像群を比較させるプログラム。
29. コンピュータに、請求項１８に記載に方法を実行させることによって、前記コンピュータに画像又は画像群を検索させるプログラム。
30. 請求項２７ないし請求項２９のいずれか一項に記載のプログラムを記憶するコンピュータ読み取り可能な記憶媒体。

Images