少なくとも1つの画像及び画像群を表現する方法、画像及び/又は画像群を比較する方法、画像又は画像群を符号化する方法、画像又は画像シーケンスを復号する方法、符号化されたデータの使用、装置、コンピュータプログラム、システム、及びコンピュータ読み取り可能な記憶媒体
【課題】所与の画像に類似している一組の画像から画像を検索するため、又はデジタルビデオ中のフレームの切れ目(例えばショット遷移又は照明及び他の効果)を検出するために、画像間の類似性を評価する方法を提供する。
【解決手段】画像を表現及び解析する方法は、1つ又は複数のスケールで、且つ1つ又は複数のカラーチャネルについて画像の複数の記述子を生成することであって、当該記述子は、領域内の色内容及び色相関の情報を取得する、記述子を生成することと、記述子をスケール、カラーチャネル、特徴部の意味、及び領域等の特性に基づいて複数の方法で関連付けることと、画像の類似性を評価するためにこのような画像表現を比較することとを含む。
【解決手段】画像を表現及び解析する方法は、1つ又は複数のスケールで、且つ1つ又は複数のカラーチャネルについて画像の複数の記述子を生成することであって、当該記述子は、領域内の色内容及び色相関の情報を取得する、記述子を生成することと、記述子をスケール、カラーチャネル、特徴部の意味、及び領域等の特性に基づいて複数の方法で関連付けることと、画像の類似性を評価するためにこのような画像表現を比較することとを含む。
【発明の詳細な説明】
【技術分野】
【0001】
[発明の背景]
本発明は、画像を表現する方法及び装置、並びに画像間の類似性を評価する方法及び装置に関する。
【0002】
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)には、ビデオシーケンス中のショット遷移を検出するための方法が提示されている。シーケンス中のフレーム毎に、RGB色空間の3次元ヒストグラムを作成する。次に、シーケンス中の連続フレーム間の差を、それぞれのヒストグラム間の差として計算する。ヒストグラム間の差は、ビンに関連する(bin-wise)差の絶対値の和として計算する。次に、所定の固定閾値を上回る距離を探索することによって、ショット遷移を特定する。よって、この方法は、空間的に敏感でない(spatially insensitive)色内容(colour content)情報のみに基づいて、ショット遷移を検出する。したがって、この方法は、空間的配置及び色相関の中に存在する豊富な情報を利用していない。
【0003】
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)には、ビデオシーケンス中のショット遷移を検出するための異なる方法が提示されている。シーケンス中のフレーム毎に、エッジマップを計算する。次に、第1のフレームには存在するが第2のフレームには存在しないエッジの数と、第2のフレームには存在するが第1のフレームには存在しないエッジの数とに基づいて、シーケンス中の連続フレーム間の差を計算する。このとき、この差の測度の時系列における鋭いピークは、ショット遷移の存在を示す。したがって、この方法は、空間相関情報の一種であるエッジ情報のみに基づいてショット遷移を検出する。この原理は正しいが、この方法は、フレームの色内容の中に存在する豊富な情報を利用していない。さらに、エッジマップの作成プロセスは計算コストが高く、また、フレーム内の最も強い色の切れ目のみを示すことを意図している。さらに、この方法は、動きに極めて敏感である。したがって、著者等は、この欠点に対処するために画像の位置合わせ技法の使用を提案しているが、こうしたプロセスは計算コストが高い。
【0004】
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)色内容情報のみに基づいてショット遷移を検出する。この原理は正しいが、この方法は、空間的な色相関の中に存在する豊富な情報を利用していない。さらに、このようなビデオの単純な処理は、ノイズ及び動きに対する高い敏感性をもたらす。この動きに対する敏感性の問題には、動き補償アルゴリズムにより対処することもできるが、こうしたプロセスは計算コストが高い。
【0005】
W. Xiongの米国特許出願公開第2003/0091235号明細書「Shot Boundary Detection」(2003年5月15日公開)には、異なるタイプの情報の組み合わせに基づいてショット遷移を検出するための方法が提示されている。この方法は、2フレーム間でブロックに基づく差を計算すること、及び、この差が固定閾値を越える場合、ショット遷移候補を宣言することを含む。この場合、ショット遷移は、2フレーム間の色及び/又はエッジの差も固定閾値を越えることを要求することによって検証する。ブロックに基づく差を計算するために、フレームをブロックに分割し、ブロック平均を計算する。次に、対応するブロック間の差を閾値処理して、2つのブロックが類似しているか異なっているかを判定し、2フレーム間で異なるブロックの数を閾値処理して、2つのフレームが類似しているか異なっているかを判定する。色の差は、ビンに関連する差の絶対値の和であり、エッジの差は、エッジ強度及びエッジ方向の情報を取得するエッジヒストグラムを用いる。
【0006】
Y. Nakajima、M. Sugano、H. Yanagiharaの米国特許出願公開第2004/0091044号明細書「Picture Searching Apparatus」(KDDI CORPORATION(日本)、2004年5月13日公開)には、(a)画像間の相関、(b)サブサンプリング画像間の相関、(c)画像間の動き、及び(d)サブサンプリング画像間の動き、に基づいてショット遷移を検出するための方法が提示されている。ここでは、画像間及びサブサンプリング画像間の相関を、画素に関連する差又はヒストグラムの差として測定し、画像間及びサブサンプリング画像間の動きを、様々な動きベクトルの差に基づいて測定する。
【0007】
H. Jafarkhani、B. Shahrarayの米国特許第6,542,619号明細書「Method for Analyzing Video」(AT&T CORP.(アメリカ)、2003年4月1日交付)には、ショット遷移の検出方法が提示されており、この方法は、ビデオフレームの2つの1次元射影、すなわち行射影及び列射影を作成することと、各射影に対してウェーブレット変換を実行し、高周波成分(すなわちウェーブレット係数)のみを保持することと、各変換の高周波成分の自己相関をとることとを含む。一連のビデオフレームについて、結果として得られた自己相関係数の時間曲線が所定の最大値を示すとき、ショット遷移を指示する。したがって、この方法は、ウェーブレット変換によって提供される空間的に敏感な色内容及び色相関の情報を使用するが、この情報は、フレームではなくフレーム射影に関連するものであり、大きな情報損失を生じる。
【0008】
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)、すなわち、スケーリング関数の係数(平均強度)とごく少数の最大振幅のウェーブレット係数のみを保持する。次に、打ち切った分解を量子化する、すなわち、ウェーブレット係数の符号のみを保持する。したがって、画像検索目的で画像を特徴付ける単一の画像記述子を形成する。
【0009】
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」の方法の違いは、後者の方法を用いる場合、フレームの周辺を廃棄し、フレームをその中心部分のみに縮小することである。このような手法は、大きな情報損失につながり、ビデオ中に大きな動きが存在する場合、誤ったビデオの分割及び/又は大きな過分割を生じる可能性がある。
【0010】
上述の方法の両方に共通する欠陥は、ごく少数の最大振幅の係数のみを保持することによってウェーブレット分解を効率的に打ち切ることができるという仮定である。これに関連して(to put this in context)、画像平面のマルチスケールウェーブレット分解を128×128画素から開始して2×2画素まで行うと、16383個のウェーブレット係数が生じる。当業者には承知の通り、この系列を振幅に基づいてごく少数の係数、例えば著者等が示唆するように最大振幅を有する40個又は60個の係数に打ち切る場合、いくつかの問題を挙げれば、結果として、ノイズの影響を非常に受けやすく、画像検索及びビデオ分割の場合に部分遮蔽の影響を受けやすく、且つ、ビデオ分割の場合に高いビデオの動き及びショット内の照明効果の影響を受けやすい記述子が生じる。符号のみを保持することによる打ち切り系列の量子化は、問題をさらに大きくする。
【0011】
これらの方法に伴う別の重要な問題は、ハールウェーブレット分解の係数に付随する意味情報を利用していないことである。こうした意味情報には、係数が表現する特定の色情報、例えばRGBのR又はYCbCrのY、係数が存在する特定の画像スケール、例えば、細部を取得する高い画像スケールの係数なのか、粗い画像情報を取得する低い画像スケールの係数なのか、等がある。
【発明の概要】
【発明が解決しようとする課題】
【0012】
本明細書では、例えば、所与の画像に類似している一組の画像から画像を検索するため、又はデジタルビデオ中のフレームの切れ目(例えばショット遷移又は照明及び他の効果)を検出するために、画像間の類似性を評価する方法を記載する。この方法は、空間的に敏感な色内容及び色相関の情報を1つ又は複数の画像スケールで、且つ1つ又は複数の画像チャネルにわたって取得する画像記述子の抽出と、それに続く、意味内容で区別される1つではなく複数の記述子における記述子の組み合わせと、上記意味内容を効果的に利用する複数の決定の枠組みにおけるこれらの記述子の使用とに依拠する。したがって、以前の方法とは異なり、画像間に複雑な関係を確立することが可能であり、例えば、2つの画像は同一シーンを表すが、一方に極めて大きな遮蔽(例えばカメラから歩いて入ってきた人物)があること、又は、2つの画像は同一シーンを表すが、異なる照明条件下で取り込まれたこと、又は、2つのフレームは同一ショットに属するが、全体的な照明効果のために非常に異なって見えることを確認することが可能である。
【課題を解決するための手段】
【0013】
[発明の概要]
本発明の態様を添付の特許請求の範囲に記載する。
【0014】
本発明の一態様によれば、画像の1つ又は複数の領域について色情報及び/又は色相関情報を取得する副記述子(sub-descriptors)をその特性(例えば、領域、スケール、色、色相関、カラーチャネル等)に基づいて関連付け、2つ以上の記述子を形成する。
【0015】
副記述子は、色及び/又は色相関の情報を同様に取得する要素を有してもよい。その場合、副記述子要素も副記述子を構成し得る。例えば、ハールウェーブレット変換に関する或る画像領域の4つの測定値LL、HL、LH及びHHがともに、その画像領域の副記述子を形成する。しかし、LLのみ又はHHのみを単独で副記述子と見なしてもよい。
【0016】
「副記述子を関連付ける」ステップは、副記述子をその構成要素に分割すること、及び、当該要素を対応する特性に応じてグループ分け又は関連付けすることを含み得る。
【図面の簡単な説明】
【0017】
【図1】本発明の一実施形態によるYチャネルのブロック平均リサンプリングプロセスを示す図である。
【図2A】本発明の一実施形態における1つのスケールの記述子の計算を示す図である。
【図2B】本発明の一実施形態における1つのスケールの記述子の計算を示す図である。
【図2C】本発明の一実施形態における1つのスケールの記述子の計算を示す図である。
【図2D】本発明の一実施形態における1つのスケールの記述子の計算を示す図である。
【図3A】本発明のさらなる実施形態による1つのスケールの記述子の計算を示す図である。
【図3B】本発明のさらなる実施形態による1つのスケールの記述子の計算を示す図である。
【図3C】本発明のさらなる実施形態による1つのスケールの記述子の計算を示す図である。
【図3D】本発明のさらなる実施形態による1つのスケールの記述子の計算を示す図である。
【図4】本発明の一実施形態による複数の画像を比較するフロー図である。
【図5】本発明のさらなる実施形態による複数の画像を比較するフロー図である。
【図6】本発明のさらなる実施形態による複数の画像を比較するフロー図である。
【図7】本発明のさらなる実施形態による複数の画像を比較するフロー図である。
【図8】本発明のさらなる実施形態による複数の画像を比較するフロー図である。
【図9】本発明のさらなる実施形態による複数の画像を比較するフロー図である。
【図10】本発明の実施形態の実施に適した処理装置の概略図である。
【発明を実施するための形態】
【0018】
本発明の実施形態を以下に、添付図面を参照して記載する。
【0019】
デジタル画像Fi(x,y)を検討する。ここで、(x,y)は空間座標を表し、x=0...M−1及びy=0...N−1である。本発明の一実施形態において、Fiは色空間YCbCrで表されるが、これに制限されるものではなく、本発明の実施形態は、いかなるチャネル数のいかなる色空間にも適用可能である。本発明の一実施形態において、Fiの空間解像度は720×576画素である、すなわち、M=720及びN=576であるが、これに限定されるものではなく、本発明の実施形態は、いかなる空間解像度にも適用可能である。本発明の一実施形態において、記述子を抽出する最高解像度として64×64画素を選択するが、これに限定されるものではなく、本発明の実施形態は他の解像度にも適用可能である。したがって、Fiをリサンプリングして、64×64画素の画像Fi(64×64)を得る。本発明の一実施形態において、このリサンプリングプロセスは、図1に示すような単純なブロック平均プロセスであるが、リサンプリング機構の選択は限定されない。より具体的に言えば、図1は、Yチャネルのブロック平均リサンプリングプロセスを示すが、これに限定されるものではなく、このプロセスは、いかなる色空間のいかなるチャネルにも用いることができる。本発明の別の実施形態において、記述子を抽出する最高スケールはFiの解像度に一致し、最初のリサンプリングは必要とされない。
【0020】
図2は、本発明の一実施形態における、このスケールの記述子の計算を示す。より具体的には、図2は、Yチャネルの記述子の計算を示すが、これに限定されるものではなく、同様の手法を全てのカラーチャネルに適用する。図2Aにおいて、2×2の窓を画像の左上の角に適用する。この窓は局所近傍を指定する。この近傍の画素FYi(64×64)(0,0),FYi(64×64)(1,0),FYi(64×64)(0,1)及びFYi(64×64)(1,1)について、2次元ハール変換係数LL,HL,LH及びHHを次のように計算することができる。
【0021】
【数1】
【0022】
上記の式において、LLは色内容情報を取得し、HL、LH及びHHは色相関情報を取得する。当業者は、式(1)〜(4)を変更して、例えば、先ず横方向の計算を行い、次に縦方向の計算を行うことによって、必要な計算の数を減らしてもよいことを理解するであろう。式(1)〜(4)によるハール係数、又はその最適化を、分母の値を2ではなく4として計算することも一般的である。
【0023】
FYi(64×64)の記述子をVYi(64×64)とすると、これらの値は、次のように記述子として書き表すことができる。
【0024】
【数2】
【0025】
次に、図2Bに示すように、2×2の窓を2画素右にスライドさせ、画素FYi(64×64)(2,0),FYi(64×64)(3,0),FYi(64×64)(2,1)及びFYi(64×64)(3,1)を含む新たな近傍を形成する。ハール変換係数LL,HL,LH,及びHHを再び、新たな画素値について計算し、その後、記述子位置VYi(64×64)(5)〜VYi(64×64)(8)に格納する。図2C及び図2Dに示すように、一組の行について計算が全て完了すると、スライド窓を2画素下に移動させ、左から右へのスライドを再び開始し、画像全体を処理し終えるまで続ける。これにより、画像の空間的に敏感な色内容及び色相関をY平面について64×64画素のスケールで取得する記述子VYi(64×64)の計算が完了する。
【0026】
本発明の実施形態は、空間的に敏感な色内容及び色相関の情報を取得する記述子の計算に関する。したがって、
【0027】
上記の説明において、LL,HL,LH及びHHの式(1)〜(4)は、近傍内で行うことができる測定の一例に過ぎず、一実施形態を示すに過ぎない。ハール変換は、ウェーブレット変換の単純な例であり、信号の多重解像度の時間周波数表現を生じる。本発明の別の実施形態は、ハール変換ではなく、別の同様であるが、より複雑なウェーブレット変換、すなわち2次元ドーブシ(Daubechies')ウェーブレット変換を用いる。上記の変換とは異なり、この変換は、スライドステップ(sliding step)が2画素である4×4の窓において動作する、すなわち、結果として得られる近傍は重なり合う。図3にこれを示す。図3Aにおいて、4×4の窓を画像の左上の角に適用する。この窓は局所近傍を指定する。この近傍の画素について、以下の記述子要素を計算する。
【0028】
【数3】
【数4】
【数5】
【数6】
【0029】
ここで、
【0030】
【数7】
【0031】
である。
【0032】
上記の式において、a1はスケーリング関数の係数であり、色内容情報を取得し、a2、a3及びa4はウェーブレット変換の係数であり、色相関情報を取得する。当業者は、式(6)〜(13)を変更して、必要な計算の数を減らしてもよいことを理解するであろう。これらの値は、一連の式(lines of equation)(5)に沿って記述子VYi(64×64)として書き表すことができ、次に、図3Bに示すように、4×4の窓を2画素右にスライドさせて新たな近傍を形成し、新たな画素値について記述子要素を再び計算し、以下同様の操作を行う。図3Cに示すように、スライド窓が画像の右端に達すると、完全な4×4の近傍を形成するのに十分な画素がなくなる。この問題はいくつかの方法で対処することができる。これらの方法の1つは、図3Cに示すように、データが鏡映されていると仮定することである。もう1つの手法は、データが周期的であると仮定することである。他の手法も存在する。これと同じ問題が、スライド窓が画像の下端に達するときにも生じ、上記のように対処することができる。図3Dに示すように、一組の行の計算が全て完了すると、スライド窓を2画素下へ移動させ、左から右へのスライドを再び開始し、画像全体を処理し終えるまで続ける。
【0033】
上記の説明では、ウェーブレット変換を使用して記述子を計算する。代替的な実施形態は、色内容及び色相関の記述子要素を計算するための他のプロセスに依拠してもよい。例えば、代替的な実施形態は、色内容及び色相関の記述子要素を生成するが、上記のプロセスとは異なり、画素近傍毎に計算する記述子要素の数は近傍の画素数よりも少なく、格納及び処理により便利な小さな記述子を生じるが、依然として画像を空間的に均一にカバーする記述子抽出プロセスに依拠してもよい。さらに別の代替的な実施形態は、上記のプロセスとは異なり、近傍画素のサブセットのみに基づいて近傍の記述子要素を計算し、速度を大幅に改善する記述子抽出プロセスに依拠してもよい。
【0034】
例えば、図2Aに示すような局所近傍の画素FYi(64×64)(0,0),FYi(64×64)(1,0),FYi(64×64)(0,1)及びFYi(64×64)(1,1)について、本発明の代替的な実施形態は、記述子要素χ1〜χ4を次のように計算する。
【0035】
【数8】
【0036】
したがって、局所画素平均を表す要素χ1は色内容情報を取得し、要素χ2、χ3及びχ4はそれぞれ、或る画素と別の画素の差を表し、色相関情報を取得する。これらの値は、一連の式(5)に沿って記述子VYi(64×64)として書き表すことができ、次に、図2Bに示すように、2×2の窓を2画素右にスライドさせて新たな近傍を形成し、新たな画素値について記述子要素を再び計算し、以下同様の操作を行う。
【0037】
本発明のさらに別の代替的な実施形態は、式(14)〜(17)を以下に示す式(I)〜(IV)で置き換える。
【0038】
【数9】
【0039】
上に示す式において、φ1は色内容情報を取得し、φ2〜φ4は色相関情報を取得する。
【0040】
本発明のさらに別の代替的な実施形態は、式(14)〜(17)を以下に示す式(18)及び(19)で置き換える。
【0041】
【数10】
【0042】
上に示す式において、ψ1は色内容情報を取得し、ψ2は色相関情報を取得する。
【0043】
さらに、上記の説明及び図は、2×2画素及び4×4画素のサイズのスライド近傍窓を検討するが、これに制限されるものではない。代替的な実施形態は、例えば、所与の計算に関する要求又は近傍測定プロセス自体に合わせて、任意のサイズ及び/又は幾何形状及び/又はスライドステップを近傍窓に指定することができる。
【0044】
上記の説明では、FYi(64×64)の全ての位置で同一の近傍窓及び記述子抽出プロセスを用いる。代替的な実施態様では、そうである必要はない。代替的な実施形態は、画像中の異なる位置で異なる近傍パラメータ及び/又は記述子抽出プロセスを使用してもよい。例えば、本発明の代替的な実施形態は、式(1)〜(4)のもの又は式(14)〜(17)のものような速い記述子抽出プロセスを画像の周辺に用い、式(6)〜(9)のもののような遅いがより強力な記述子抽出プロセスを画像の中心に用いる。
【0045】
次に、FYi(64×64)を新たなより低いスケールにリサンプリングする。一実施形態において、この新たなスケールは32×32画素である。次に、64×64の画像の場合と全く同じ方法で新たな記述子VYi(32×32)を計算する。なお、このリサンプリングは実際には計算を必要としない場合もあり得る。式(1)に見られるように、この新たな画素値は、LL値として以前に計算し、VYi(64×64)(1),VYi(64×64)(5),VYi(64×64)(9),...,VYi(64×64)(4093)に格納している。したがって、一実施形態では、記述子VYi(64×64),VYi(32×32),VYi(16×16),VYi(8×8),VYi(4×4),及びVYi(2×2)を計算する。
【0046】
本明細書において概要を説明する本発明の実施形態は、画像Fiの1つ又は複数のスケールで記述子を抽出することを含む。したがって、
【0047】
上記の説明において、最も細かい又は最大又は最高スケール、最も粗い又は最小又は最低スケール、スケールの数及びスケール間の関係は、本発明の可能な一実施形態を示すに過ぎず、代替的な実施形態は、例えばシステムの計算能力に合うように、異なるそのようなパラメータを使用してもよい。
【0048】
本発明の一実施形態では、以降の処理を行う前に、これらのスケールに固有の記述子から特定の要素を除去する。本発明の一実施形態では、2b×2b、2b-1×2b-1、2b-2×2b-2等、例えば、64×64、32×32、16×16等のスケールでの式(1)〜(4)すなわちハール変換において概要を説明した記述子抽出プロセスの場合、VYiのLL要素を、最低スケールのLL要素を除いて全て除去してもよい。これは、2b-k×2b-kのスケールのLL要素を、2b-k-1×2b-k-1のスケールのLL値、並びに2b-k×2b-kのスケールのHL要素、LH要素、及びHH要素から直接計算できるためである。なお、この特性は常に当てはまるわけではない。例えば、2b×2b、2b-2×2b-2、2b-4×2b-4等、例えば、64×64、16×16、4×4等のスケールで記述子を計算する場合には当てはまらない。また、記述子抽出プロセスの一部としてLL要素、HL要素、LH要素及びHH要素のサブセットのみを計算する場合には当てはまらない。
【0049】
同等の特性がドーブシウェーブレット変換に当てはまる。すなわち、2b×2b、2b-1×2b-1、2b-2×2b-2等、例えば、64×64、32×32、16×16等のスケールでのドーブシウェーブレット変換に対する本発明の一実施形態において、VYiのa1要素を、最低スケールのa1要素を除いて全て除去してもよい。
【0050】
同等の特性が式(14)〜(17)の変換に当てはまる。すなわち、本発明の一実施形態において、2b×2b、2b-1×2b-1、2b-2×2b-2等、例えば、64×64、32×32、16×16等のスケールでのその変換について、VYiのχ1要素を、最低スケールのχ1要素を除いて全て除去してもよい。同一の特性が、式(I)〜(IV)の変換にも当てはまる。
【0051】
同一の記述子抽出プロセスをFiのCbチャネル及びCrチャネルに適用すると、記述子VCbi(64×64),...,VCbi(2×2)及びVCri(64×64),...,VCri(2×2)が得られる。これらのスケールに固有でチャネルに固有の記述子は、全体で、画像の空間的に敏感な色内容及び色相関の情報を複数のスケールで、且つ複数のチャネルにわたって取得する。
【0052】
上記の説明において、FiはYCbCr色空間にあると仮定し、記述子の抽出に全てのチャネルを用いる。代替的な実施態様は、記述子を計算する前に画像を新たな色空間で表現してもよいし、かつ/又は記述子の計算に色平面のサブセットのみを使用してもよい。
【0053】
上記の説明では、Fiの異なるカラーチャネルにわたる記述子を同一スケールで計算する。代替的な実施態様では、そうである必要はない。例えば、本発明の代替的な実施形態はYチャネルの記述子を、Cb及び/又はCrチャネルの記述子よりも多いスケールで、及び/又はそれとは異なるスケールで計算する。このような微調整により、特定の画像又はビデオ素材により良く適合して、性能を高めることができる。
【0054】
上記の説明では、Fiの全てのカラーチャネルに同一の近傍窓及び記述子抽出プロセスを用いる。代替的な実施態様では、そうである必要はない。代替的な実施形態は、チャネル毎に異なる近傍パラメータ及び/又は記述子抽出プロセスを使用してもよい。例えば、本発明の代替的な実施形態は、速い記述子抽出プロセスをCbチャネル及びCrチャネルに用い、遅いがより強力な記述子抽出プロセスをYチャネルに用いる。このような微調整により、特定の画像又はビデオ素材により良く適合して、システムの性能を高めることができる。
【0055】
本発明の一実施形態では、記述子要素の一部又は全てを、整数部と小数部を持つ実数で表現する。本発明の別の実施形態では、記述子要素の一部又は全てを、例えば小数部を切り捨てるか又は切り上げる(round)ことによって、整数形式で表現する。本発明のさらに別の実施形態では、記述子要素の一部又は全てを、スケーリングによって整数形式で表現する。例えば、式(1)〜(4)は、小数部が3つの値、すなわち、.25、.50及び.75しか取り得ない実数を生成する。したがって、記述子要素に4の値を掛けることによって、情報を全く損失せずに整数表現が得られる。本発明のさらに別の実施形態では、記述子要素の一部又は全てを、何らかの方法で整数形式で表現し、その後、例えば3ビット又は4ビット長の短い値に量子化する。
【0056】
したがって、本発明の一実施形態では、画像Fiをその記述子VC1i(C1SCq),...,VC1i(C1SC1),VC2i(C2SCq),...,VC2i(C2SC1),...,VCpi(CpSCq),...,VCpi(CpSC1)で表現する。ここで、C1,C2,...,CpはFiの第1、第2及び第pのカラーチャネルであり、C1SCqはチャネルC1の最高の記述子スケールであり、C1SC1はチャネルC1の最低の記述子スケールであり、C2SCqはチャネルC2の最高の記述子スケールであり、C2SC1はチャネルC2の最低の記述子スケールであり、以下同様である。これらのスケールに固有でチャネルに固有の記述子は、全体で、画像の空間的に敏感な色内容及び色相関の情報を複数のスケール(好ましくは2つ以上)で、且つ複数のチャネル(好ましくは2つ以上)にわたって取得する。
【0057】
従来技術において一般的な手法と同様に、画像Fiのこれらの記述子をすべて融合すなわち連結させて、記述子Vj又は画像Fjとの比較のために1つの記述子Viにすると、比較速度及びFiとFjの関係の理解の両方に関して性能が非最適になる可能性がある。
【0058】
本発明の一実施形態は、スケールに固有でチャネルに固有の記述子を融合させて、異なるスケールを取得する少なくとも2つの記述子にすることを特徴とする。例えば、6つの異なるスケールの、スケールに固有でチャネルに固有の記述子の場合、本発明の一実施形態は、同一の6つのスケールで、スケールに固有なマルチチャネル記述子を生成する。別の実施形態は、1つが低スケールでもう1つが高スケールの、2つのスケール指向性のマルチチャネル記述子を生成し、さらに別の実施形態は、1つが低スケールで、1つが中スケールで、もう1つが高スケールの、3つのスケール指向性のマルチチャネル記述子を生成する。本発明の好ましい実施形態では、記述子を実際に、複数のチャネルにわたって計算し、融合させてスケール指向性の記述子にするが、代替的な実施形態は、単一のチャネルについてのみ記述子を計算し、それらを融合させてスケール指向性の記述子にする。
【0059】
前の段落の文章に沿った本発明の一実施形態を図4に示す。ステップ4100において、上記で説明したように、スケールに固有でチャネルに固有の記述子を抽出する。ステップ4250において、これらの記述子を融合させて、スケール指向性でマルチチャネルの記述子Vi(SCQ),...,Vi(SCA)の組にする。ここで、SCA及びSCQはそれぞれ最低の記述子スケール及び最高の記述子スケールである。ステップ4300において、現在のスケールC_SCを最低のスケールSCAに設定する。ステップ4400において、現在のスケールC_SCの記述子Vi(C_SC)及びVj(C_SC)のみを用いて、画像Fiと画像Fjとの類似度(similarity measure)Dj,i(C_SC)を計算する。ステップ4500において、類似度を用いて、2つの画像の類似性又は非類似性に関する仮決定を行う。ステップ4600において、類似度及び/又は仮決定を調査して、より高いスケールでの処理が望ましいかどうかを判定する。そのような処理が望ましくないと決定された場合、プロセスはステップ4900に進み、2つの画像の類似性又は非類似性に関する最終決定を行う。そうでない場合、プロセスはステップ4700に進み、処理すべきより高いスケールの記述子が残っているかどうかを調べる。より高いスケールの記述子が利用可能である場合、プロセスはステップ4800に進んで現在のスケールC_SCを上げ、次にステップ4400に進み、新たなスケールで新たな類似度を計算し、以下同様の操作を行う。一方で、より高いスケールの記述子が利用可能でない場合、プロセスはステップ4900に進み、2つの画像の類似性又は非類似性に関する最終決定を行う。
【0060】
図4に示すようなスケール指向性の逐次構成の目的は、2つの画像間の類似性又は非類似性を可能な限り速く、可能な限り少ない計算で確認することである。したがって、そのような方式は、利用可能な記述子をすべて融合させて1つの記述子にする方式と比較して、システムの速度を高めることができる。
【0061】
次に、このプロセスの様々なステップをより詳しく検討する。ステップ4400において、類似度の計算には多くのオプションがある。例えば、本発明の一実施形態において、それぞれn個の要素からなる2つの記述子Vi及びVjの間のL1距離は、次式により与えられる類似度として計算することができる。
【0062】
【数11】
【0063】
本明細書に概要を説明する発明の実施形態は、上記記述子を使用して、画像間の少なくとも2つの値を含む1つ又は複数の類似度を計算することに関する。したがって、
【0064】
記述子の距離を計算するための式(20)のL1距離は、本発明の可能な一実施態様に関連するに過ぎない。代替的な実施態様は、式(20)を、L2距離を計算する次式(21)で置き換える。
【0065】
【数12】
【0066】
このような様々な距離メトリックが関連文献に記載されている。
【0067】
さらに、代替的な実施態様は、式(20)を次式(22)で置き換える。この式(22)は、重み付きL1距離を計算する。
【0068】
【数13】
【0069】
ここで、w(l)はl番目の記述子要素の重み係数である。さらに、重みの適用はまた、式(21)のL2距離、又は文献に記載されている任意の他の適切な距離メトリックとともに用いてもよい。
【0070】
類似度の処理には多くのオプションがある。本発明の一実施形態では、ステップ4500において、類似度Dj,iに閾値処理関数を適用する。すなわち、閾値thrについて、
【0071】
【数14】
【0072】
である場合、2つの画像は大きく異なるものと見なし、ステップ4500において「非類似」の仮決定を行う。これに基づいて、ステップ4600は、さらなる処理が必要ないと決定し、ステップ4900においてこの仮決定を最終決定とする(finalise)。一方、ステップ4500において(23)の関係が満たされない場合、このステップにおいて、「類似」の仮決定を行う。これに基づいて、ステップ4600は、さらなる処理が望ましいと決定する。より高いスケールの記述子が利用可能である場合、プロセスはステップ4400にループバックする。そうでない場合、ステップ4900において「類似」の仮決定を最終決定とする。
【0073】
本明細書に概要を説明する発明の実施形態は、少なくとも2つの値を含む上記類似度を使用して、画像間の類似性又は非類似性を確認することに及ぶ。したがって、
【0074】
本発明の代替的な実施形態において、
【0075】
【数15】
【0076】
である場合、2つの画像は類似しているものと見なし、ステップ4500において「類似」の仮決定を行う。これに基づいて、ステップ4600は、さらなる処理が必要ないと決定し、ステップ4900においてこの仮決定を最終決定とする。一方、ステップ4500において(24)の関係が満たされない場合、このステップにおいて「非類似」の仮決定を行う。これに基づいて、ステップ4600は、さらなる処理が望ましいと決定する。より高いスケールの記述子が利用可能である場合、プロセスはステップ4400にループバックする。そうでない場合、ステップ4900において「非類似」の仮決定を最終決定とする。
【0077】
提案する発明のさらに別の実施形態は、2つの閾値thr1及びthr2を用いる。ここで、thr1<thr2である。すると、
【0078】
【数16】
【0079】
である場合、2つの画像は類似しているものと見なし、ステップ4500において「類似」の仮決定を行う。これに基づいて、ステップ4600は、さらなる処理が必要ないと決定し、ステップ4900においてこの仮決定を最終決定とする。一方、ステップ4500において(25)の関係が満たされない場合、このステップにおいて「非類似」の仮決定を行う。次に、ステップ4600において、
【0080】
【数17】
【0081】
である場合、ステップ4600は、さらなる処理が必要ないと決定し、ステップ4900においてこの仮決定を最終決定とする。そうでない場合、ステップ4600は、さらなる処理が望ましいと決定する。より高いスケールの記述子が利用可能である場合、プロセスはステップ4400にループバックする。そうでない場合、ステップ4900において「非類似」の仮決定を最終決定とするか、又は別法として、ステップ4900において、新たな「おそらく」という決定を生じる。この「おそらく」という決定は、全ての記述子スケールを使い果たした後で確信の持てる決定に至らなかったことを示す。
【0082】
ステップ4900において行われる決定の意味は、特定の実施態様に依存する。
【0083】
本発明の一実施形態において、Fi及びFjは時間順の画像である。例えば、これらはビデオFzのフレームであり、FjとFiの間にフレームの切れ目(例えばショット遷移又は照明効果等)が存在するかどうかを確かめることを目的とする。その場合、ステップ4900における決定は、FjとFiの類似度がそのようなフレームの切れ目を示すかどうかとなる。このようなシステムは、ビデオを分割する目的で用いられることになる。
【0084】
本発明の別の実施形態において、Fj及びFiは時間の順序がない個別の画像である。例えば、Fjは一組の画像Fzの画像であり、FiはFz内部又は外部の別の画像であり、Fz中の、Fiに類似している画像を見出すことを目的とする。その場合、ステップ4900の決定は、FjとFiの類似度が、それらの画像が類似していることを示すかどうかとなる。このようなシステムは、問い合わせによる画像の検索に、又はデータベース中の画像の分類に用いられる。
【0085】
本発明の一実施形態において、ステップ4400の記述子Vi及びVjの一方又は両方は画像ではなく画像群を表す。
【0086】
例えば、本発明の一実施形態において、Vjは、画像クラスタFjを形成する画像Fj1,Fj2,...,Fjgの記述子Vj1,Vj2,...,Vjgの関数(例えば平均(average)又は中央値(median))である。例えば、Fjは車を表す画像クラスタであり得る。その場合、画像Fiについて、記述子Vi及びVj間の類似性を確認することは、Fiが特定の画像に類似しているかどうかではなく、それが特定の画像クラス又は画像クラスタに類似しているかどうかを示す。一組の画像Fzは、そのようなクラスタを任意数含むことができ、そのような処理は、所与の画像が最も良く適合する特定のクラスタを示すことになる。さらに、クラスタは、Vjによってだけでなく、その画像の記述子の共分散行列等の他の統計量によっても表現することができる。共分散行列は、ステップ4400において、より複雑な類似度(例えばマハラノビス距離又は最尤度)の計算を可能にする。
【0087】
ビデオを分割するための本発明の別の実施形態において、VjはフレームFj1,Fj2,...,Fjgの記述子Vj1,Vj2,...,Vjgの関数(例えば平均又は中央値)である。これらのフレームは、全てがフレームFiに先行しても、全てがそれに後続しても、又は、一部が先行して一部が後続してもよい。
【0088】
本明細書に概要を説明する発明の実施形態は、少なくとも2つの値を含む上記類似度を使用して、画像間の類似性又は非類似性を確認することに及ぶ。したがって、
【0089】
ビデオを分割するための本発明の上記の実施形態では、ステップ4500において、2つのフレームFi及びFj間の類似度を用いて、フレームの切れ目を検出する。本発明の代替的な実施形態は、この類似度だけでなく、フレームFi及びFjの周囲のフレーム間の類似度も用いる。
【0090】
例えば、本発明の一実施形態において、j=i−1であり、フレームの切れ目の検出は、類似度Di+k-1,i+kに依拠し、∀k∈[−t1,t2]である。好ましい実施形態において、t1=t2=tである。したがって、フレームFi+kは、フレームFiを中心とする時間窓を形成する。次に、次の場合にのみ、Fi-1及びFi間でフレームの切れ目を検出する。
【0091】
【数18】
【0092】
式(27)及び(28)によれば、各類似度Di-1,iは、Di-1,iを中心とする2t+1のサイズの時間窓内にあると考えられる。その場合、Di-1,iが時間窓内の最大距離であり、且つ、時間窓内の2番目に大きい距離よりも少なくともthr倍大きい場合にのみ、フレームFi-1とフレームFiの間で切れ目を検出する。このような時間適応的な方式は、フレーム間の高い動きレベルから生じる誤った検出の数を低減することを目的とする。フレームの切れ目を検出するためにそのような時系列を処理するそのような方式はいくつかある。
【0093】
本発明の好ましい実施形態において、スケール指向性の記述子の処理において使用する閾値及び制御パラメータはいずれもスケール指向性である。
【0094】
代替的な実施形態において、スケール指向性の記述子の逐次処理は、ユーザによる指示又はこのプロセスを使用する自動システムによる指示に従って、最高スケールの記述子を処理し終える前に終了する。これは、例えばリアルタイムのオンライン用途で、またシステムがデータレートに付いて行けない場合に、システムの速度をさらに高めるために行うことができる。
【0095】
本発明の別の実施形態を図5に示す。ステップ5100において、上で説明したように、スケールに固有でチャネルに固有の記述子を抽出する。ステップ5250において、これらの記述子を融合させて、スケール指向性のマルチチャネル記述子Vi(SCQ),...,Vi(SCA)の組にする。ここで、SCA及びSCQはそれぞれ最低の記述子スケール及び最高の記述子スケールである。ステップ5410、...、5490において、スケール指向性の記述子の対Vi(SCA)及びVj(SCA),...,Vi(SCQ)及びVj(SCQ)を使用して、画像Fiと画像Fjの間の類似度Dj,i(SCA),...,Dj,i(SCQ)を計算する。したがって、複数の類似度を記述子のスケール毎に1つずつ計算する。ステップ5510、...、5590において、各類似度を用いて、2つの画像の類似性又は非類似性に関する仮決定を行う。したがって、複数の仮決定を、記述子のスケール毎に1つずつ行う。次に、ステップ5900において、複数の仮決定を用いて、2つの画像の類似性又は非類似性に関する最終決定を行う。
【0096】
図5に示すようなスケール指向性の並列構成の目的は、異なるスケールでの類似性の決定を処理することによって、画像Fiと画像Fjの間の関係のより徹底した調査を可能にするためである。したがって、このようなシステムは、最終的な類似性の決定だけでなく、「これらの画像は非常に粗いレベルでは類似しているが、細部では著しく異なる」といった付加的な情報も提供することができる。対照的に、スケールに固有でチャネルに固有の記述子を融合させて単一のマルチスケールでマルチチャネルの記述子にするシステムは、2つの画像に関して1つの類似性の決定しか提供することができない。
【0097】
したがって、所与の画像Fiに類似している一組の画像から画像を検索するための本発明の一実施形態では、図5に示すような方式により、検索結果を階層形式で提示することができる。最初に、粗いレベルでFiに類似している(すなわち、低スケールの記述子によれば類似している)一組の画像FAを提示し、次に、FAのサブセットであり、より細かい詳細レベルでFiに類似している一組の画像FBを提示し、以下同様の順序で提示する。
【0098】
フレームの切れ目検出及びビデオ分割のための本発明の別の実施形態において、図5に示すような方式により、異なる粒度(すなわち粗い、中程度、細かい、等)で分割を行うことができる。
【0099】
図5において、ステップ5100は図4のステップ4100と類似しており、ステップ4100について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0100】
同様に、ステップ5250は図4のステップ4250と類似しており、ステップ4250について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0101】
同様に、ステップ5410、...、5490の各々は図4のステップ4400と類似しており、ステップ4400について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0102】
同様に、ステップ5510、...、5590の各々は図4のステップ4500と類似しており、ステップ4500について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0103】
本発明の一実施形態において、ステップ5510、...、5590の仮決定は二分決定であり、例えば「1」が「類似」を示し、「0」が「非類似」を示す。
【0104】
本発明の別の実施形態において、ステップ5510、...、5590の仮決定は二分ではなく、少なくとも3つの値を含む。このような場合、処理ステップ5510、...、5590の結果の記述には、「仮決定」という用語よりも「尤度」という用語のほうが優れている。例えば、本発明の一実施形態において、ステップ5510、...、5590の各々は3つの閾値を用いる。類似度が第1の閾値を下回る場合、「非類似」を示す類似性の尤度「0」を生じる。類似度が第1の閾値を上回るが、第1の閾値よりも高い第2の閾値を下回る場合、「おそらく非類似」を示す類似性の尤度「1」を生じる。類似度が第2の閾値を上回るが、第2の閾値よりも高い第3の閾値を下回る場合、「おそらく類似」を示す類似性の尤度「2」を生じる。類似度が第3の閾値を上回る場合、「類似」を示す類似性の尤度「3」を生じる。本発明の別の実施形態において、尤度は、閾値処理によってではなく、類似度の一定範囲(例えば0〜1)への正規化により生成される。
【0105】
本発明の一実施形態のステップ5900において、二分仮決定又は尤度をZj,i(SCA),...,Zj,i(SCQ)として示すと、FiとFjが類似しているという最終決定は、次の場合にのみ行う。
【0106】
【数19】
【0107】
ここで、thrfは閾値であり、WSCA,...,WSCQは、各スケール指向性の決定又は尤度に与える重要度を制御する重みである。これらの重みは、所望であれば、WSCA=...=WSCQ=1を設定することによって排除することができる。
【0108】
ステップ5510、...、5590により少なくとも3つの値を含む尤度を生成する本発明の別の実施形態において、2つの画像は、式(29)の条件が当てはまり、さらに、新たな第2の閾値を下回る個別の尤度がないか、又は所与の数以下である場合にのみ、類似しているものと見なす。
【0109】
本発明の好ましい実施形態において、スケール指向性の記述子の処理において使用する閾値及び制御パラメータはいずれもスケール指向性である。
【0110】
本実施形態において説明するような一組の記述子の並列処理において、最終的な決定に至るために使用することのできるこのような方式は多くある。
【0111】
本発明の一実施形態は、スケールに固有でチャネルに固有の記述子を融合させて、異なるカラーチャネルにわたる少なくとも2つの記述子にすることを特徴とする。例えば、Yチャネル、Cbチャネル及びCrチャネルにわたるスケールに固有でチャネルに固有の記述子の場合、本発明の一実施形態は、3つのマルチスケールでチャネル指向性の記述子を生成するが、別の実施形態は、1つがYチャネル用、もう1つがCbチャネル及びCrチャネル用の2つのマルチスケールでチャネル指向性の記述子を生成する。本発明の好ましい実施形態では、記述子を実際に複数のスケールで計算し、融合させてチャネル指向性の記述子にするが、代替的な実施形態は、単一のスケールでのみ記述子を計算し、それらを融合させてチャネル指向性の記述子にする。
【0112】
前の段落の文章に沿った本発明の一実施形態を図6に示す。ステップ6100において、上記で説明したように、スケールに固有でチャネルに固有の記述子を抽出する。ステップ6250において、これらの記述子を融合させて、マルチスケールでチャネル指向性の記述子VCCAi,...,VCCQiの組にする。ここで、CCA,...,CCQはカラーチャネル又はカラーチャネル群である。例えば、本発明の一実施形態において、CCAはYチャネルを表し、CCBはCbCrのチャネル対を表す。本発明の別の実施形態において、CCAはRGBのRチャネルを表し、CCBはGチャネルを表し、CCCはBチャネルを表す。ステップ6410、...、6490において、チャネル指向性の記述子対VCCAi及びVCCAj,...,VCCQi及びVCCQjを用いて、画像Fiと画像Fjの類似度DCCAj,i,...,DCCQj,iを計算する。このように、複数の類似度を、チャネル指向性の記述子毎に1つずつ計算する。ステップ6510、...、6590において、各類似度を用いて、2つの画像の類似性又は非類似性に関する仮決定を行う。したがって、複数の仮決定を、チャネル指向性の記述子毎に1つずつ行う。次に、ステップ6900において、複数の仮決定を用いて、2つの画像の類似性又は非類似性に関する最終決定を行う。
【0113】
図6に示すようなチャネル指向性の並列構成の目的は、異なるカラーチャネルにわたる類似性の決定を処理して、画像に関する異なる情報を取得することによって、画像Fiと画像Fjの間の関係のより徹底した調査を可能にすることである。したがって、このようなシステムは、最終的な類似性の決定だけでなく、「これらの画像は色差(chrominance)チャネルでは類似しているが、輝度チャネルでは類似していない」といった付加的な情報も提供することができる。対照的に、スケールに固有でチャネルに固有の記述子を融合させて単一のマルチスケールでマルチチャネルの記述子にするシステムは、2つの画像に関して1つの類似性の決定しか提供することができない。
【0114】
したがって、フレームの切れ目(例えばショット遷移又は照明効果等)を検出するための本発明の一実施形態において、図6に示すようなシステムは、フレームの切れ目を確実に検出するだけでなく、ショット遷移を他の照明効果と分離する。例えば、2つのフレームが色差と輝度の両方に関して著しく異なることが分かった場合、これはショット遷移を示す。一方、2つのフレームが輝度に関しては著しく異なるが、色差に関してはほとんど変わらないことが分かった場合、これは、ショット遷移でなく全体的な照明効果を示す。
【0115】
所与の画像Fiに類似している一組の画像から画像を検索するための本発明の代替的な実施形態では、図6に示すような方式により、問い合わせ画像に意味的に類似している画像、例えば同一の風景又は都市景観のものであるが、異なる時刻に異なる照明条件で取り込まれた画像を検索することができる。
【0116】
図6において、ステップ6100は図5のステップ5100と類似しており、ステップ5100について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0117】
同様に、ステップ6250は図5のステップ5250と類似しており、ステップ5200について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0118】
同様に、ステップ6410、...、6490は図5のステップ5410、...、5490と類似しており、ステップ5410、...、5490について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0119】
同様に、ステップ6510、...、6590は図5のステップ5510、...、5590と類似しており、ステップ5510、...、5590について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0120】
同様に、ステップ6900は図5のステップ5900と類似しており、ステップ5900について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0121】
本発明の別の実施形態は、スケールに固有でチャネルに固有の記述子を最初に、スケールに固有でチャネルに固有の、特徴部の意味に指向性を持つ(feature-semantics-oriented)記述子に分割すること、及び、それらを次に融合させて、特徴部の意味の異なる少なくとも2つの記述子にすることを特徴とする。例えば、本発明の一実施形態において、6つの異なるスケールで3つの異なるカラーチャネルにわたる、スケールに固有でチャネルに固有の記述子の場合、全部で18個の記述子が最初に利用可能である。これらの18個の記述子を、半分が色内容要素(例えば式(1)のLL)のみを含み、他の半分が色相関要素(例えば(2)〜(4)のHL、LH及びHH)のみを含む36個の記述子に分割する。次に、これらの36個の記述子を融合させて、1つが複数のスケールで、且つ異なるチャネルにわたる全ての色内容要素を含み、もう1つが複数のスケールで、且つ異なるチャネルにわたる全ての色相関要素を含む2つの記述子にする。本発明の別の実施形態では、最初の各記述子を3つ以上の記述子に分割する。例えば、各記述子を、LL、HL、LH及びHHタイプの要素のそれぞれに1つずつの、4つの記述子に分割する。次に、これらの記述子を融合させて、異なるスケールで、且つ異なるチャネルにわたって1タイプの要素のみ(例えばLLのみ又はHHのみ)をそれぞれ含む4つの最終的な記述子にする。本発明の好ましい実施形態では、記述子を実際に複数のスケールで複数のチャネルにわたって計算するが、代替的な実施形態は、記述子を単一のスケールのみで、及び/又は単一のチャネルのみについて計算してもよい。
【0122】
前の段落の文章に沿った本発明の一実施形態を図7に示す。ステップ7100において、上記で説明したように、スケールに固有でチャネルに固有の記述子を抽出する。ステップ7200において、上記で説明したように、これらの記述子を特徴部の意味に応じて分割する。ステップ7250において、結果として得られる記述子を融合させて、マルチスケールでマルチチャネルの、特徴部の意味に指向性を持つ記述子VFSAi,...,VFSQiの組にする。ここで、FSA,...,FSQは特徴部のタイプを表す。例えば、本発明の一実施形態において、FSAはLL要素を表し、FSBはHL要素、LH要素及びHH要素を表す。本発明の別の実施形態において、FSAはLL要素を表し、FSBはHL要素を表し、FSCはLH要素を表し、FSDはHH要素を表す。ステップ7410、...、7490において、特徴部の意味に指向性を持つ記述子対VFSAi及びVFSAj,...,VFSQi及びVFSQjを用いて、画像Fiと画像Fjの間の類似度DFSAj,i,...,DFSQj,iを計算する。したがって、複数の類似度を、特徴部の意味に指向性を持つ記述子毎に1つずつ計算する。ステップ7510、...、7590において、各類似度を用いて、2つの画像の類似性又は非類似性に関する仮決定を行う。このように、複数の仮決定を、特徴部の意味に指向性を持つ記述子毎に1つずつ行う。次に、ステップ7900において、複数の仮決定を用いて、2つの画像の類似性又は非類似性に関する最終決定を行う。
【0123】
図7に示すような特徴部の意味に指向性を持つ並列構成の目的は、異なる特徴部のタイプに基づく類似性の決定を処理して、画像に関する異なる情報を取得することによって、画像Fiと画像Fjの間の関係のより徹底した調査を可能にすることである。したがって、このようなシステムは、最終的な類似性の決定だけでなく、「これらの画像は局所エッジに関しては類似しているが、色内容に関しては類似していない」といった付加的な情報も提供することができる。対照的に、スケールに固有でチャネルに固有の記述子を融合させて単一のマルチスケールでマルチチャネルの記述子にするシステムは、2つの画像に関して1つの類似性の決定しか提供することができない。
【0124】
したがって、フレームの切れ目(例えばショット遷移又は照明効果等)を検出するための本発明の一実施形態において、図7に示すようなシステムは、フレームの切れ目を確実に検出するだけでなく、ショット遷移を他の照明効果と分離する。例えば、2つのフレームが色内容と色相関の両方に関して著しく異なることが分かった場合、これはショット遷移を示す。一方、2つのフレームが色内容に関しては著しく異なるが、色相関に関してはほとんど変わらないことが分かった場合、これは、ショット遷移でなく全体的な照明効果を示す。
【0125】
所与の画像Fiに類似している一組の画像から画像を検索するための本発明の代替的な実施形態では、図7に示すような方式により、問い合わせ画像に意味的に類似している画像、例えば同一シーンのものであるが、異なる照明条件又は異なる機材で取り込まれたためにコントラストレベルの異なる画像を検索することができる。
【0126】
図7において、ステップ7100は図6のステップ6100と類似しており、ステップ6100について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0127】
図7において、ステップ7200は図6のステップ6200と類似しており、ステップ6200について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0128】
同様に、ステップ7250は図6のステップ6250と類似しており、ステップ6250について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0129】
同様に、ステップ7410、...、7490は図6のステップ6410、...、6490と類似しており、ステップ6410、...、6490について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0130】
同様に、ステップ7510、...、7590は図6のステップ6510、...、6590と類似しており、ステップ6510、...、6590について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0131】
同様に、ステップ7900は図6のステップ6900と類似しており、ステップ6900について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0132】
本発明の別の実施形態は、スケールに固有でチャネルに固有の記述子を最初に、スケールに固有でチャネルに固有の領域指向性の記述子に分割すること、及び、それらを次に融合させて、画像内の異なる領域をカバーする少なくとも2つの記述子にすることを特徴とする。例えば、本発明の一実施形態において、5つの異なるスケール64×64、32×32、...、4×4で3つの異なるカラーチャネルにわたる、スケールに固有でチャネルに固有の記述子の場合、全部で15個の記述子が最初に利用可能である。これらの15個の記述子を、15個の記述子からなる4つの組に分割する。各組は、画像の特定の象限に対応する要素のみを含む。すなわち、1組が左上の象限用、1組が右上の象限用、1組が左下の象限用、1組が右下の象限用である。次に、これらの記述子を融合させて、1つが複数のスケールで、且つ異なるチャネルにわたる全ての記述子要素を画像の左上の象限について含み、1つが同様の記述子要素を画像の右上の象限について含み、以下同様である4つの記述子にする。本発明の別の実施形態では、画像の縦スライスに対応する複数の領域指向性の記述子を形成する。さらに別の実施形態では、画像の横スライスに対応する複数の領域指向性の記述子を形成する。本発明の好ましい実施形態では、記述子を実際に複数のスケールで複数のチャネルにわたって計算するが、代替的な実施形態は、記述子を単一のスケールのみで、及び/又は単一のチャネルのみについて計算してもよい。
【0133】
前の段落の文章に沿った本発明の一実施形態を図8に示す。ステップ8100において、上記で説明したように、スケールに固有でチャネルに固有の記述子を抽出する。ステップ8200において、上記で説明したように、これらの記述子を画像領域に応じて分割する。ステップ8250において、結果として得られる記述子を融合させて、マルチスケールでマルチチャネルの領域指向性記述子VREAi,...,VREQiの組にする。ここで、REA,...,REQは画像領域を表す。例えば、本発明の一実施形態において、REAは画像の左上の象限を表し、REBは画像の右上の象限を表し、RECは画像の左下の象限を表し、REDは画像の右下の象限を表す。ステップ8410、...、8490において、領域指向性の記述子対VREAi及びVREAj,...,VREQi及びVREQjを用いて、画像Fiと画像Fjの間の類似度DREAj,i,...,DREQj,iを計算する。このように、複数の類似度を、領域指向性の記述子毎に1つずつ計算する。ステップ8510、...、8590において、各類似度を用いて、2つの画像の類似性又は非類似性に関する仮決定を行う。したがって、複数の仮決定を、領域指向性の記述子毎に1つずつ行う。次に、ステップ8900において、複数の仮決定を用いて、2つの画像の類似性又は非類似性に関する最終決定を行う。
【0134】
図7に示すような領域指向性の並列構成の目的は、画像の異なる領域から生じる類似性の決定を処理することによって、画像Fiと画像Fjの間の関係のより徹底した調査を可能にすることである。したがって、このようなシステムは、最終的な類似性の決定を提供し、「これらの画像は或る領域では非常に類似しているが、他の領域では類似していない」といった情報を提供し、且つ、異なる画像の対応する領域間の関係を特定することができる。対照的に、スケールに固有でチャネルに固有の記述子を融合させて単一のマルチスケールでマルチチャネルの記述子にするシステムは、2つの画像に関して1つの類似性の決定しか提供することができない。
【0135】
したがって、所与の画像Fiに類似している一組の画像から画像を検索するための本発明の一実施形態では、図8に示すような方式により、問い合わせ画像に部分的に類似している画像、例えば同一シーンのものであるが、カメラの視野(optical field)に突然歩いて入ってきてシーンの左側部分を遮る人物により生じる遮蔽を有する画像を検索することができる。
【0136】
同様に、フレームの切れ目を検出するための本発明の代替的な実施形態において、図8に示すようなシステムは、フレームの切れ目を確実に検出するだけでなく、ショット遷移を他のショット内障害(例えば、カメラに近い速度で(at speed close to the camera)移動し、視野を短い間遮る人物)と分離する。
【0137】
図8において、ステップ8100は図7のステップ7100と類似しており、ステップ7100について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0138】
同様に、ステップ8200は図7のステップ7200と類似しており、ステップ7200について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0139】
同様に、ステップ8250は図7のステップ7250と類似しており、ステップ7250について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0140】
同様に、ステップ8410、...、8490は図7のステップ7410、...、7490と類似しており、ステップ7410、...、7490について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0141】
同様に、ステップ8510、...、8590は図7のステップ7510、...、7590と類似しており、ステップ7510、...、7590について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0142】
同様に、ステップ8900は図7のステップ8900と類似しており、ステップ8900について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0143】
本発明の好ましい実施形態では、多くのスケールで、且つ複数のチャネルにわたって記述子を抽出することが明確に理解されるべきである。しかし、本発明の代替的な実施形態において、そうである必要はない。例えば、スケール指向性の枠組みを実現するために、単一のカラーチャネルについて、及び/又は単一の画像領域について記述子を抽出してもよい。同様に、チャネル指向性の枠組みを実現するために、単一のスケールで、及び/又は単一の画像領域について記述子を抽出してもよい。同様に、特徴部の意味に指向性を持つ枠組みを実現するために、単一のスケールで、及び/又は単一のチャネルについて、及び/又は単一の画像領域について記述子を抽出してもよい。同様に、領域指向性の枠組みを実現するために、単一のスケールで、及び/又は単一のチャネルについて記述子を抽出してもよい。
【0144】
また、本明細書中で説明する逐次構成及び並列構成は、特定の記述子の分割又は指向に限定されないことが明確に理解されるべきである。特定の構成を特定の記述子の指向に適用するのは単に例示を目的とするものである。例えば、上記の実施形態は、スケール指向性の記述子についてのみ逐次構成を検討する。本発明の代替的な実施形態は、他の記述子の指向に逐次構成を使用する。例えば、本発明の代替的な実施形態は、チャネル指向性の記述子を逐次構成で処理し、チャネルのうちの1つにおいて所与の画像に類似していない画像を迅速にフィルタリングで除去し、他のチャネルの処理を不要にすることを目指す。本発明のさらに別の代替的な実施形態は、特徴部の意味に指向性を持つ記述子を逐次構成で、上記と同じ原理で処理する。本発明のさらに別の代替的な実施形態は、領域指向性の記述子を逐次構成で、上記と同じ原理で処理する。
【0145】
また、システムは、複数の記述子の指向に依拠してもよいことが明確に理解されるべきである。例えば、本発明の一実施形態では、スケールに固有でチャネルに固有の記述子を最初に計算した後に、スケール指向性で特徴部の意味に指向性を持つ記述子を形成する。例えば、4つの記述子、すなわち、低スケールの色内容要素用の1つの記述子、高スケールの色内容要素用の1つの記述子、低スケールの色相関要素用の1つの記述子、及び高スケールの色相関要素用の1つの記述子を形成する。本発明の一実施形態では、そのような記述子を、上述のように並列構成で処理する。本発明の別の実施形態では、そのような記述子を、上述のように逐次構成で処理する。本発明のさらに別の実施形態では、図9に示すようなハイブリッド構成を用いる。図9において、SCA及びSCQはそれぞれ最低の記述子スケール及び最高の記述子スケールであり、FSA,...,FSQは特徴部のタイプを表す。
【0146】
このハイブリッドの枠組みは、単一の記述子の指向にも利用することができる。例えば、1つの代替的な実施形態は逐次構成に依拠し、それによって、各ループにおいて、単一ではなく少数のスケール指向性記述子を、組み込まれた並列構成で処理する。このように、本発明の異なる実施形態は、単一の記述子の指向に依拠するか、複数の記述子の指向に依拠するかに関わらず、逐次構成又は並列構成又はハイブリッド構成に依拠してもよいことも明確に理解されるべきである。また、図9は、並列構成を逐次構成に埋め込む1つの可能なハイブリッド構成を例示目的で示すに過ぎないことを明確に理解すべきである。代替的な実施形態は他のハイブリッド構成、例えば、1つ又は複数の逐次構成を並列構成に埋め込む構成を使用する。
【0147】
図9に示すように、画像を最初に、粗い開始スケールで処理し、確信の持てる決定に至らない場合、画像を次に細かいスケールで処理し、以下同様の操作を行い、確信の持てる決定に至るか、又は利用可能/許容可能なスケールを使い果たすまで続ける。
【0148】
好ましい実施形態では、各スケールについて、並列処理される画像毎に4つの記述子があり、それぞれの結果を組み合わせて、そのスケールの決定を得る。これは図9と類似しているが、使用される記述子は以下の、(i)輝度から抽出される色内容、(ii)輝度から抽出される色相関、(iii)色差から抽出される色内容、及び(iv)色差から抽出される色相関である。
【0149】
代替案では、2つの色内容記述子(1つが輝度用、もう1つが色差(chrominance)用)を開始スケールのみについて用いる。全ての他のスケールについては、2つの色相関記述子のみを用いる。
【0150】
さらに、上記の実施形態では、フレームの切れ目を検出するために、連続フレームの全ての対の処理を検討した。代替的な実施形態は、フレームをより粗く処理してもよい。代替的な実施形態は、4番目毎のフレームのみを処理し、さらに別の実施形態は、16番目毎のフレームのみを処理する。このような向上により、ビデオ分割システムの速度がさらに上がる。
【0151】
さらに、上記の説明は、各フレームがその画素値で表される未圧縮のデジタルビデオの処理に関する。本発明は、復元していないMPEG圧縮ビデオにも直接適用することができる。
【0152】
MPEGビデオの性質は、当業者にはよく知られており、J. Watkinsonの著書「The MPEG Handbook: MPEG-1, MPEG-2, MPEG-4」(Focal Press, Oxford 2001, ISBN:0-240-51656-7)に専門的に記載されている。
【0153】
MPEG圧縮ビデオに関する本発明の一実施形態では、ビデオのIフレームのみを処理する。より具体的には、IフレームのDC表現のみを処理する。すなわち、8×8画素の各ブロックについて、そのDCT変換のDC成分のみを取る。事実上、IフレームのDC表現は単に、8×8のブロック平均を用いて圧縮前の原フレームをリサンプリングしたものである。DC成分は、圧縮ビデオストリームから復元を行うことなく直接取り出すことができるため、本発明の実施形態は、MPEG圧縮ビデオのIフレームの処理に直接適用できることが明らかである。
【0154】
本発明は、例えばコンピュータシステムにおいて、適切なソフトウェア及び/又はハードウェアの変更を施して実施することができる。例えば、本発明は、プロセッサ又は制御装置等の制御又は処理手段、メモリ、磁気記憶装置、CD、DVD等の画像記憶手段を含むデータ記憶手段、ディスプレイ若しくはモニタ又はプリンタ等のデータ出力手段、キーボード等のデータ入力手段、及びスキャナ等の画像入力手段、又はそのような構成要素の任意の組み合わせ並びに追加の構成要素を有するコンピュータ又は同様の装置を用いて実施することができる。本発明の態様は、ソフトウェア及び/又はハードウェア形態で、又は特定用途向け装置において提供するか、又は集積回路等の特定用途向けモジュールを提供することができる。本発明の一実施形態による装置中のシステムの構成要素は、他の構成要素から遠隔して、例えばインターネットを介して設けられてもよい。
【0155】
コンピュータシステムの形態の適切な装置のブロック図を図10に示し、この図において、制御ユニット10100は、画像記憶手段10200、記述子記憶手段10300及びディスプレイ10400に接続される。画像記憶手段10200は、上記の実施形態により表現又は比較される画像に対応するデータを記憶する。これは、1つの画像、複数の画像、画像クラスタ、画像シーケンス又は画像データベース全体に対応するデータであってもよい。記述子記憶手段10300は、データベースであってもよく、制御ユニット10100により計算される副記述子(sub-descriptors)を含む導出された記述子をすべて記憶する。制御ユニットの動作の結果は、ディスプレイ10400上でユーザに対して表示する。
【0156】
「スケール」及び「解像度」という用語は、本明細書において置き換え可能に用いられる。画像の領域は画像全体又は画像の部分を意味し得る。「記述子」という用語は、決定を行うプロセスにおいて使用され得る、画像又は画像の部分の導出された表現を指す。「副記述子」という用語は、関連付けられて記述子を形成する、画像又は画像の部分の導出された表現を指す。しかし、当業者であれば、この区別は便宜的なものに過ぎず、各用語は、上述の方法の特定の点を指すことを認識するであろう。特定の実施形態の各副記述子は、異なる実施形態では記述子として機能する場合があり、その逆の場合も同様である。したがって、特定の実施形態では記述子という用語のみが用いられる。
【技術分野】
【0001】
[発明の背景]
本発明は、画像を表現する方法及び装置、並びに画像間の類似性を評価する方法及び装置に関する。
【0002】
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)には、ビデオシーケンス中のショット遷移を検出するための方法が提示されている。シーケンス中のフレーム毎に、RGB色空間の3次元ヒストグラムを作成する。次に、シーケンス中の連続フレーム間の差を、それぞれのヒストグラム間の差として計算する。ヒストグラム間の差は、ビンに関連する(bin-wise)差の絶対値の和として計算する。次に、所定の固定閾値を上回る距離を探索することによって、ショット遷移を特定する。よって、この方法は、空間的に敏感でない(spatially insensitive)色内容(colour content)情報のみに基づいて、ショット遷移を検出する。したがって、この方法は、空間的配置及び色相関の中に存在する豊富な情報を利用していない。
【0003】
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)には、ビデオシーケンス中のショット遷移を検出するための異なる方法が提示されている。シーケンス中のフレーム毎に、エッジマップを計算する。次に、第1のフレームには存在するが第2のフレームには存在しないエッジの数と、第2のフレームには存在するが第1のフレームには存在しないエッジの数とに基づいて、シーケンス中の連続フレーム間の差を計算する。このとき、この差の測度の時系列における鋭いピークは、ショット遷移の存在を示す。したがって、この方法は、空間相関情報の一種であるエッジ情報のみに基づいてショット遷移を検出する。この原理は正しいが、この方法は、フレームの色内容の中に存在する豊富な情報を利用していない。さらに、エッジマップの作成プロセスは計算コストが高く、また、フレーム内の最も強い色の切れ目のみを示すことを意図している。さらに、この方法は、動きに極めて敏感である。したがって、著者等は、この欠点に対処するために画像の位置合わせ技法の使用を提案しているが、こうしたプロセスは計算コストが高い。
【0004】
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)色内容情報のみに基づいてショット遷移を検出する。この原理は正しいが、この方法は、空間的な色相関の中に存在する豊富な情報を利用していない。さらに、このようなビデオの単純な処理は、ノイズ及び動きに対する高い敏感性をもたらす。この動きに対する敏感性の問題には、動き補償アルゴリズムにより対処することもできるが、こうしたプロセスは計算コストが高い。
【0005】
W. Xiongの米国特許出願公開第2003/0091235号明細書「Shot Boundary Detection」(2003年5月15日公開)には、異なるタイプの情報の組み合わせに基づいてショット遷移を検出するための方法が提示されている。この方法は、2フレーム間でブロックに基づく差を計算すること、及び、この差が固定閾値を越える場合、ショット遷移候補を宣言することを含む。この場合、ショット遷移は、2フレーム間の色及び/又はエッジの差も固定閾値を越えることを要求することによって検証する。ブロックに基づく差を計算するために、フレームをブロックに分割し、ブロック平均を計算する。次に、対応するブロック間の差を閾値処理して、2つのブロックが類似しているか異なっているかを判定し、2フレーム間で異なるブロックの数を閾値処理して、2つのフレームが類似しているか異なっているかを判定する。色の差は、ビンに関連する差の絶対値の和であり、エッジの差は、エッジ強度及びエッジ方向の情報を取得するエッジヒストグラムを用いる。
【0006】
Y. Nakajima、M. Sugano、H. Yanagiharaの米国特許出願公開第2004/0091044号明細書「Picture Searching Apparatus」(KDDI CORPORATION(日本)、2004年5月13日公開)には、(a)画像間の相関、(b)サブサンプリング画像間の相関、(c)画像間の動き、及び(d)サブサンプリング画像間の動き、に基づいてショット遷移を検出するための方法が提示されている。ここでは、画像間及びサブサンプリング画像間の相関を、画素に関連する差又はヒストグラムの差として測定し、画像間及びサブサンプリング画像間の動きを、様々な動きベクトルの差に基づいて測定する。
【0007】
H. Jafarkhani、B. Shahrarayの米国特許第6,542,619号明細書「Method for Analyzing Video」(AT&T CORP.(アメリカ)、2003年4月1日交付)には、ショット遷移の検出方法が提示されており、この方法は、ビデオフレームの2つの1次元射影、すなわち行射影及び列射影を作成することと、各射影に対してウェーブレット変換を実行し、高周波成分(すなわちウェーブレット係数)のみを保持することと、各変換の高周波成分の自己相関をとることとを含む。一連のビデオフレームについて、結果として得られた自己相関係数の時間曲線が所定の最大値を示すとき、ショット遷移を指示する。したがって、この方法は、ウェーブレット変換によって提供される空間的に敏感な色内容及び色相関の情報を使用するが、この情報は、フレームではなくフレーム射影に関連するものであり、大きな情報損失を生じる。
【0008】
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)、すなわち、スケーリング関数の係数(平均強度)とごく少数の最大振幅のウェーブレット係数のみを保持する。次に、打ち切った分解を量子化する、すなわち、ウェーブレット係数の符号のみを保持する。したがって、画像検索目的で画像を特徴付ける単一の画像記述子を形成する。
【0009】
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」の方法の違いは、後者の方法を用いる場合、フレームの周辺を廃棄し、フレームをその中心部分のみに縮小することである。このような手法は、大きな情報損失につながり、ビデオ中に大きな動きが存在する場合、誤ったビデオの分割及び/又は大きな過分割を生じる可能性がある。
【0010】
上述の方法の両方に共通する欠陥は、ごく少数の最大振幅の係数のみを保持することによってウェーブレット分解を効率的に打ち切ることができるという仮定である。これに関連して(to put this in context)、画像平面のマルチスケールウェーブレット分解を128×128画素から開始して2×2画素まで行うと、16383個のウェーブレット係数が生じる。当業者には承知の通り、この系列を振幅に基づいてごく少数の係数、例えば著者等が示唆するように最大振幅を有する40個又は60個の係数に打ち切る場合、いくつかの問題を挙げれば、結果として、ノイズの影響を非常に受けやすく、画像検索及びビデオ分割の場合に部分遮蔽の影響を受けやすく、且つ、ビデオ分割の場合に高いビデオの動き及びショット内の照明効果の影響を受けやすい記述子が生じる。符号のみを保持することによる打ち切り系列の量子化は、問題をさらに大きくする。
【0011】
これらの方法に伴う別の重要な問題は、ハールウェーブレット分解の係数に付随する意味情報を利用していないことである。こうした意味情報には、係数が表現する特定の色情報、例えばRGBのR又はYCbCrのY、係数が存在する特定の画像スケール、例えば、細部を取得する高い画像スケールの係数なのか、粗い画像情報を取得する低い画像スケールの係数なのか、等がある。
【発明の概要】
【発明が解決しようとする課題】
【0012】
本明細書では、例えば、所与の画像に類似している一組の画像から画像を検索するため、又はデジタルビデオ中のフレームの切れ目(例えばショット遷移又は照明及び他の効果)を検出するために、画像間の類似性を評価する方法を記載する。この方法は、空間的に敏感な色内容及び色相関の情報を1つ又は複数の画像スケールで、且つ1つ又は複数の画像チャネルにわたって取得する画像記述子の抽出と、それに続く、意味内容で区別される1つではなく複数の記述子における記述子の組み合わせと、上記意味内容を効果的に利用する複数の決定の枠組みにおけるこれらの記述子の使用とに依拠する。したがって、以前の方法とは異なり、画像間に複雑な関係を確立することが可能であり、例えば、2つの画像は同一シーンを表すが、一方に極めて大きな遮蔽(例えばカメラから歩いて入ってきた人物)があること、又は、2つの画像は同一シーンを表すが、異なる照明条件下で取り込まれたこと、又は、2つのフレームは同一ショットに属するが、全体的な照明効果のために非常に異なって見えることを確認することが可能である。
【課題を解決するための手段】
【0013】
[発明の概要]
本発明の態様を添付の特許請求の範囲に記載する。
【0014】
本発明の一態様によれば、画像の1つ又は複数の領域について色情報及び/又は色相関情報を取得する副記述子(sub-descriptors)をその特性(例えば、領域、スケール、色、色相関、カラーチャネル等)に基づいて関連付け、2つ以上の記述子を形成する。
【0015】
副記述子は、色及び/又は色相関の情報を同様に取得する要素を有してもよい。その場合、副記述子要素も副記述子を構成し得る。例えば、ハールウェーブレット変換に関する或る画像領域の4つの測定値LL、HL、LH及びHHがともに、その画像領域の副記述子を形成する。しかし、LLのみ又はHHのみを単独で副記述子と見なしてもよい。
【0016】
「副記述子を関連付ける」ステップは、副記述子をその構成要素に分割すること、及び、当該要素を対応する特性に応じてグループ分け又は関連付けすることを含み得る。
【図面の簡単な説明】
【0017】
【図1】本発明の一実施形態によるYチャネルのブロック平均リサンプリングプロセスを示す図である。
【図2A】本発明の一実施形態における1つのスケールの記述子の計算を示す図である。
【図2B】本発明の一実施形態における1つのスケールの記述子の計算を示す図である。
【図2C】本発明の一実施形態における1つのスケールの記述子の計算を示す図である。
【図2D】本発明の一実施形態における1つのスケールの記述子の計算を示す図である。
【図3A】本発明のさらなる実施形態による1つのスケールの記述子の計算を示す図である。
【図3B】本発明のさらなる実施形態による1つのスケールの記述子の計算を示す図である。
【図3C】本発明のさらなる実施形態による1つのスケールの記述子の計算を示す図である。
【図3D】本発明のさらなる実施形態による1つのスケールの記述子の計算を示す図である。
【図4】本発明の一実施形態による複数の画像を比較するフロー図である。
【図5】本発明のさらなる実施形態による複数の画像を比較するフロー図である。
【図6】本発明のさらなる実施形態による複数の画像を比較するフロー図である。
【図7】本発明のさらなる実施形態による複数の画像を比較するフロー図である。
【図8】本発明のさらなる実施形態による複数の画像を比較するフロー図である。
【図9】本発明のさらなる実施形態による複数の画像を比較するフロー図である。
【図10】本発明の実施形態の実施に適した処理装置の概略図である。
【発明を実施するための形態】
【0018】
本発明の実施形態を以下に、添付図面を参照して記載する。
【0019】
デジタル画像Fi(x,y)を検討する。ここで、(x,y)は空間座標を表し、x=0...M−1及びy=0...N−1である。本発明の一実施形態において、Fiは色空間YCbCrで表されるが、これに制限されるものではなく、本発明の実施形態は、いかなるチャネル数のいかなる色空間にも適用可能である。本発明の一実施形態において、Fiの空間解像度は720×576画素である、すなわち、M=720及びN=576であるが、これに限定されるものではなく、本発明の実施形態は、いかなる空間解像度にも適用可能である。本発明の一実施形態において、記述子を抽出する最高解像度として64×64画素を選択するが、これに限定されるものではなく、本発明の実施形態は他の解像度にも適用可能である。したがって、Fiをリサンプリングして、64×64画素の画像Fi(64×64)を得る。本発明の一実施形態において、このリサンプリングプロセスは、図1に示すような単純なブロック平均プロセスであるが、リサンプリング機構の選択は限定されない。より具体的に言えば、図1は、Yチャネルのブロック平均リサンプリングプロセスを示すが、これに限定されるものではなく、このプロセスは、いかなる色空間のいかなるチャネルにも用いることができる。本発明の別の実施形態において、記述子を抽出する最高スケールはFiの解像度に一致し、最初のリサンプリングは必要とされない。
【0020】
図2は、本発明の一実施形態における、このスケールの記述子の計算を示す。より具体的には、図2は、Yチャネルの記述子の計算を示すが、これに限定されるものではなく、同様の手法を全てのカラーチャネルに適用する。図2Aにおいて、2×2の窓を画像の左上の角に適用する。この窓は局所近傍を指定する。この近傍の画素FYi(64×64)(0,0),FYi(64×64)(1,0),FYi(64×64)(0,1)及びFYi(64×64)(1,1)について、2次元ハール変換係数LL,HL,LH及びHHを次のように計算することができる。
【0021】
【数1】
【0022】
上記の式において、LLは色内容情報を取得し、HL、LH及びHHは色相関情報を取得する。当業者は、式(1)〜(4)を変更して、例えば、先ず横方向の計算を行い、次に縦方向の計算を行うことによって、必要な計算の数を減らしてもよいことを理解するであろう。式(1)〜(4)によるハール係数、又はその最適化を、分母の値を2ではなく4として計算することも一般的である。
【0023】
FYi(64×64)の記述子をVYi(64×64)とすると、これらの値は、次のように記述子として書き表すことができる。
【0024】
【数2】
【0025】
次に、図2Bに示すように、2×2の窓を2画素右にスライドさせ、画素FYi(64×64)(2,0),FYi(64×64)(3,0),FYi(64×64)(2,1)及びFYi(64×64)(3,1)を含む新たな近傍を形成する。ハール変換係数LL,HL,LH,及びHHを再び、新たな画素値について計算し、その後、記述子位置VYi(64×64)(5)〜VYi(64×64)(8)に格納する。図2C及び図2Dに示すように、一組の行について計算が全て完了すると、スライド窓を2画素下に移動させ、左から右へのスライドを再び開始し、画像全体を処理し終えるまで続ける。これにより、画像の空間的に敏感な色内容及び色相関をY平面について64×64画素のスケールで取得する記述子VYi(64×64)の計算が完了する。
【0026】
本発明の実施形態は、空間的に敏感な色内容及び色相関の情報を取得する記述子の計算に関する。したがって、
【0027】
上記の説明において、LL,HL,LH及びHHの式(1)〜(4)は、近傍内で行うことができる測定の一例に過ぎず、一実施形態を示すに過ぎない。ハール変換は、ウェーブレット変換の単純な例であり、信号の多重解像度の時間周波数表現を生じる。本発明の別の実施形態は、ハール変換ではなく、別の同様であるが、より複雑なウェーブレット変換、すなわち2次元ドーブシ(Daubechies')ウェーブレット変換を用いる。上記の変換とは異なり、この変換は、スライドステップ(sliding step)が2画素である4×4の窓において動作する、すなわち、結果として得られる近傍は重なり合う。図3にこれを示す。図3Aにおいて、4×4の窓を画像の左上の角に適用する。この窓は局所近傍を指定する。この近傍の画素について、以下の記述子要素を計算する。
【0028】
【数3】
【数4】
【数5】
【数6】
【0029】
ここで、
【0030】
【数7】
【0031】
である。
【0032】
上記の式において、a1はスケーリング関数の係数であり、色内容情報を取得し、a2、a3及びa4はウェーブレット変換の係数であり、色相関情報を取得する。当業者は、式(6)〜(13)を変更して、必要な計算の数を減らしてもよいことを理解するであろう。これらの値は、一連の式(lines of equation)(5)に沿って記述子VYi(64×64)として書き表すことができ、次に、図3Bに示すように、4×4の窓を2画素右にスライドさせて新たな近傍を形成し、新たな画素値について記述子要素を再び計算し、以下同様の操作を行う。図3Cに示すように、スライド窓が画像の右端に達すると、完全な4×4の近傍を形成するのに十分な画素がなくなる。この問題はいくつかの方法で対処することができる。これらの方法の1つは、図3Cに示すように、データが鏡映されていると仮定することである。もう1つの手法は、データが周期的であると仮定することである。他の手法も存在する。これと同じ問題が、スライド窓が画像の下端に達するときにも生じ、上記のように対処することができる。図3Dに示すように、一組の行の計算が全て完了すると、スライド窓を2画素下へ移動させ、左から右へのスライドを再び開始し、画像全体を処理し終えるまで続ける。
【0033】
上記の説明では、ウェーブレット変換を使用して記述子を計算する。代替的な実施形態は、色内容及び色相関の記述子要素を計算するための他のプロセスに依拠してもよい。例えば、代替的な実施形態は、色内容及び色相関の記述子要素を生成するが、上記のプロセスとは異なり、画素近傍毎に計算する記述子要素の数は近傍の画素数よりも少なく、格納及び処理により便利な小さな記述子を生じるが、依然として画像を空間的に均一にカバーする記述子抽出プロセスに依拠してもよい。さらに別の代替的な実施形態は、上記のプロセスとは異なり、近傍画素のサブセットのみに基づいて近傍の記述子要素を計算し、速度を大幅に改善する記述子抽出プロセスに依拠してもよい。
【0034】
例えば、図2Aに示すような局所近傍の画素FYi(64×64)(0,0),FYi(64×64)(1,0),FYi(64×64)(0,1)及びFYi(64×64)(1,1)について、本発明の代替的な実施形態は、記述子要素χ1〜χ4を次のように計算する。
【0035】
【数8】
【0036】
したがって、局所画素平均を表す要素χ1は色内容情報を取得し、要素χ2、χ3及びχ4はそれぞれ、或る画素と別の画素の差を表し、色相関情報を取得する。これらの値は、一連の式(5)に沿って記述子VYi(64×64)として書き表すことができ、次に、図2Bに示すように、2×2の窓を2画素右にスライドさせて新たな近傍を形成し、新たな画素値について記述子要素を再び計算し、以下同様の操作を行う。
【0037】
本発明のさらに別の代替的な実施形態は、式(14)〜(17)を以下に示す式(I)〜(IV)で置き換える。
【0038】
【数9】
【0039】
上に示す式において、φ1は色内容情報を取得し、φ2〜φ4は色相関情報を取得する。
【0040】
本発明のさらに別の代替的な実施形態は、式(14)〜(17)を以下に示す式(18)及び(19)で置き換える。
【0041】
【数10】
【0042】
上に示す式において、ψ1は色内容情報を取得し、ψ2は色相関情報を取得する。
【0043】
さらに、上記の説明及び図は、2×2画素及び4×4画素のサイズのスライド近傍窓を検討するが、これに制限されるものではない。代替的な実施形態は、例えば、所与の計算に関する要求又は近傍測定プロセス自体に合わせて、任意のサイズ及び/又は幾何形状及び/又はスライドステップを近傍窓に指定することができる。
【0044】
上記の説明では、FYi(64×64)の全ての位置で同一の近傍窓及び記述子抽出プロセスを用いる。代替的な実施態様では、そうである必要はない。代替的な実施形態は、画像中の異なる位置で異なる近傍パラメータ及び/又は記述子抽出プロセスを使用してもよい。例えば、本発明の代替的な実施形態は、式(1)〜(4)のもの又は式(14)〜(17)のものような速い記述子抽出プロセスを画像の周辺に用い、式(6)〜(9)のもののような遅いがより強力な記述子抽出プロセスを画像の中心に用いる。
【0045】
次に、FYi(64×64)を新たなより低いスケールにリサンプリングする。一実施形態において、この新たなスケールは32×32画素である。次に、64×64の画像の場合と全く同じ方法で新たな記述子VYi(32×32)を計算する。なお、このリサンプリングは実際には計算を必要としない場合もあり得る。式(1)に見られるように、この新たな画素値は、LL値として以前に計算し、VYi(64×64)(1),VYi(64×64)(5),VYi(64×64)(9),...,VYi(64×64)(4093)に格納している。したがって、一実施形態では、記述子VYi(64×64),VYi(32×32),VYi(16×16),VYi(8×8),VYi(4×4),及びVYi(2×2)を計算する。
【0046】
本明細書において概要を説明する本発明の実施形態は、画像Fiの1つ又は複数のスケールで記述子を抽出することを含む。したがって、
【0047】
上記の説明において、最も細かい又は最大又は最高スケール、最も粗い又は最小又は最低スケール、スケールの数及びスケール間の関係は、本発明の可能な一実施形態を示すに過ぎず、代替的な実施形態は、例えばシステムの計算能力に合うように、異なるそのようなパラメータを使用してもよい。
【0048】
本発明の一実施形態では、以降の処理を行う前に、これらのスケールに固有の記述子から特定の要素を除去する。本発明の一実施形態では、2b×2b、2b-1×2b-1、2b-2×2b-2等、例えば、64×64、32×32、16×16等のスケールでの式(1)〜(4)すなわちハール変換において概要を説明した記述子抽出プロセスの場合、VYiのLL要素を、最低スケールのLL要素を除いて全て除去してもよい。これは、2b-k×2b-kのスケールのLL要素を、2b-k-1×2b-k-1のスケールのLL値、並びに2b-k×2b-kのスケールのHL要素、LH要素、及びHH要素から直接計算できるためである。なお、この特性は常に当てはまるわけではない。例えば、2b×2b、2b-2×2b-2、2b-4×2b-4等、例えば、64×64、16×16、4×4等のスケールで記述子を計算する場合には当てはまらない。また、記述子抽出プロセスの一部としてLL要素、HL要素、LH要素及びHH要素のサブセットのみを計算する場合には当てはまらない。
【0049】
同等の特性がドーブシウェーブレット変換に当てはまる。すなわち、2b×2b、2b-1×2b-1、2b-2×2b-2等、例えば、64×64、32×32、16×16等のスケールでのドーブシウェーブレット変換に対する本発明の一実施形態において、VYiのa1要素を、最低スケールのa1要素を除いて全て除去してもよい。
【0050】
同等の特性が式(14)〜(17)の変換に当てはまる。すなわち、本発明の一実施形態において、2b×2b、2b-1×2b-1、2b-2×2b-2等、例えば、64×64、32×32、16×16等のスケールでのその変換について、VYiのχ1要素を、最低スケールのχ1要素を除いて全て除去してもよい。同一の特性が、式(I)〜(IV)の変換にも当てはまる。
【0051】
同一の記述子抽出プロセスをFiのCbチャネル及びCrチャネルに適用すると、記述子VCbi(64×64),...,VCbi(2×2)及びVCri(64×64),...,VCri(2×2)が得られる。これらのスケールに固有でチャネルに固有の記述子は、全体で、画像の空間的に敏感な色内容及び色相関の情報を複数のスケールで、且つ複数のチャネルにわたって取得する。
【0052】
上記の説明において、FiはYCbCr色空間にあると仮定し、記述子の抽出に全てのチャネルを用いる。代替的な実施態様は、記述子を計算する前に画像を新たな色空間で表現してもよいし、かつ/又は記述子の計算に色平面のサブセットのみを使用してもよい。
【0053】
上記の説明では、Fiの異なるカラーチャネルにわたる記述子を同一スケールで計算する。代替的な実施態様では、そうである必要はない。例えば、本発明の代替的な実施形態はYチャネルの記述子を、Cb及び/又はCrチャネルの記述子よりも多いスケールで、及び/又はそれとは異なるスケールで計算する。このような微調整により、特定の画像又はビデオ素材により良く適合して、性能を高めることができる。
【0054】
上記の説明では、Fiの全てのカラーチャネルに同一の近傍窓及び記述子抽出プロセスを用いる。代替的な実施態様では、そうである必要はない。代替的な実施形態は、チャネル毎に異なる近傍パラメータ及び/又は記述子抽出プロセスを使用してもよい。例えば、本発明の代替的な実施形態は、速い記述子抽出プロセスをCbチャネル及びCrチャネルに用い、遅いがより強力な記述子抽出プロセスをYチャネルに用いる。このような微調整により、特定の画像又はビデオ素材により良く適合して、システムの性能を高めることができる。
【0055】
本発明の一実施形態では、記述子要素の一部又は全てを、整数部と小数部を持つ実数で表現する。本発明の別の実施形態では、記述子要素の一部又は全てを、例えば小数部を切り捨てるか又は切り上げる(round)ことによって、整数形式で表現する。本発明のさらに別の実施形態では、記述子要素の一部又は全てを、スケーリングによって整数形式で表現する。例えば、式(1)〜(4)は、小数部が3つの値、すなわち、.25、.50及び.75しか取り得ない実数を生成する。したがって、記述子要素に4の値を掛けることによって、情報を全く損失せずに整数表現が得られる。本発明のさらに別の実施形態では、記述子要素の一部又は全てを、何らかの方法で整数形式で表現し、その後、例えば3ビット又は4ビット長の短い値に量子化する。
【0056】
したがって、本発明の一実施形態では、画像Fiをその記述子VC1i(C1SCq),...,VC1i(C1SC1),VC2i(C2SCq),...,VC2i(C2SC1),...,VCpi(CpSCq),...,VCpi(CpSC1)で表現する。ここで、C1,C2,...,CpはFiの第1、第2及び第pのカラーチャネルであり、C1SCqはチャネルC1の最高の記述子スケールであり、C1SC1はチャネルC1の最低の記述子スケールであり、C2SCqはチャネルC2の最高の記述子スケールであり、C2SC1はチャネルC2の最低の記述子スケールであり、以下同様である。これらのスケールに固有でチャネルに固有の記述子は、全体で、画像の空間的に敏感な色内容及び色相関の情報を複数のスケール(好ましくは2つ以上)で、且つ複数のチャネル(好ましくは2つ以上)にわたって取得する。
【0057】
従来技術において一般的な手法と同様に、画像Fiのこれらの記述子をすべて融合すなわち連結させて、記述子Vj又は画像Fjとの比較のために1つの記述子Viにすると、比較速度及びFiとFjの関係の理解の両方に関して性能が非最適になる可能性がある。
【0058】
本発明の一実施形態は、スケールに固有でチャネルに固有の記述子を融合させて、異なるスケールを取得する少なくとも2つの記述子にすることを特徴とする。例えば、6つの異なるスケールの、スケールに固有でチャネルに固有の記述子の場合、本発明の一実施形態は、同一の6つのスケールで、スケールに固有なマルチチャネル記述子を生成する。別の実施形態は、1つが低スケールでもう1つが高スケールの、2つのスケール指向性のマルチチャネル記述子を生成し、さらに別の実施形態は、1つが低スケールで、1つが中スケールで、もう1つが高スケールの、3つのスケール指向性のマルチチャネル記述子を生成する。本発明の好ましい実施形態では、記述子を実際に、複数のチャネルにわたって計算し、融合させてスケール指向性の記述子にするが、代替的な実施形態は、単一のチャネルについてのみ記述子を計算し、それらを融合させてスケール指向性の記述子にする。
【0059】
前の段落の文章に沿った本発明の一実施形態を図4に示す。ステップ4100において、上記で説明したように、スケールに固有でチャネルに固有の記述子を抽出する。ステップ4250において、これらの記述子を融合させて、スケール指向性でマルチチャネルの記述子Vi(SCQ),...,Vi(SCA)の組にする。ここで、SCA及びSCQはそれぞれ最低の記述子スケール及び最高の記述子スケールである。ステップ4300において、現在のスケールC_SCを最低のスケールSCAに設定する。ステップ4400において、現在のスケールC_SCの記述子Vi(C_SC)及びVj(C_SC)のみを用いて、画像Fiと画像Fjとの類似度(similarity measure)Dj,i(C_SC)を計算する。ステップ4500において、類似度を用いて、2つの画像の類似性又は非類似性に関する仮決定を行う。ステップ4600において、類似度及び/又は仮決定を調査して、より高いスケールでの処理が望ましいかどうかを判定する。そのような処理が望ましくないと決定された場合、プロセスはステップ4900に進み、2つの画像の類似性又は非類似性に関する最終決定を行う。そうでない場合、プロセスはステップ4700に進み、処理すべきより高いスケールの記述子が残っているかどうかを調べる。より高いスケールの記述子が利用可能である場合、プロセスはステップ4800に進んで現在のスケールC_SCを上げ、次にステップ4400に進み、新たなスケールで新たな類似度を計算し、以下同様の操作を行う。一方で、より高いスケールの記述子が利用可能でない場合、プロセスはステップ4900に進み、2つの画像の類似性又は非類似性に関する最終決定を行う。
【0060】
図4に示すようなスケール指向性の逐次構成の目的は、2つの画像間の類似性又は非類似性を可能な限り速く、可能な限り少ない計算で確認することである。したがって、そのような方式は、利用可能な記述子をすべて融合させて1つの記述子にする方式と比較して、システムの速度を高めることができる。
【0061】
次に、このプロセスの様々なステップをより詳しく検討する。ステップ4400において、類似度の計算には多くのオプションがある。例えば、本発明の一実施形態において、それぞれn個の要素からなる2つの記述子Vi及びVjの間のL1距離は、次式により与えられる類似度として計算することができる。
【0062】
【数11】
【0063】
本明細書に概要を説明する発明の実施形態は、上記記述子を使用して、画像間の少なくとも2つの値を含む1つ又は複数の類似度を計算することに関する。したがって、
【0064】
記述子の距離を計算するための式(20)のL1距離は、本発明の可能な一実施態様に関連するに過ぎない。代替的な実施態様は、式(20)を、L2距離を計算する次式(21)で置き換える。
【0065】
【数12】
【0066】
このような様々な距離メトリックが関連文献に記載されている。
【0067】
さらに、代替的な実施態様は、式(20)を次式(22)で置き換える。この式(22)は、重み付きL1距離を計算する。
【0068】
【数13】
【0069】
ここで、w(l)はl番目の記述子要素の重み係数である。さらに、重みの適用はまた、式(21)のL2距離、又は文献に記載されている任意の他の適切な距離メトリックとともに用いてもよい。
【0070】
類似度の処理には多くのオプションがある。本発明の一実施形態では、ステップ4500において、類似度Dj,iに閾値処理関数を適用する。すなわち、閾値thrについて、
【0071】
【数14】
【0072】
である場合、2つの画像は大きく異なるものと見なし、ステップ4500において「非類似」の仮決定を行う。これに基づいて、ステップ4600は、さらなる処理が必要ないと決定し、ステップ4900においてこの仮決定を最終決定とする(finalise)。一方、ステップ4500において(23)の関係が満たされない場合、このステップにおいて、「類似」の仮決定を行う。これに基づいて、ステップ4600は、さらなる処理が望ましいと決定する。より高いスケールの記述子が利用可能である場合、プロセスはステップ4400にループバックする。そうでない場合、ステップ4900において「類似」の仮決定を最終決定とする。
【0073】
本明細書に概要を説明する発明の実施形態は、少なくとも2つの値を含む上記類似度を使用して、画像間の類似性又は非類似性を確認することに及ぶ。したがって、
【0074】
本発明の代替的な実施形態において、
【0075】
【数15】
【0076】
である場合、2つの画像は類似しているものと見なし、ステップ4500において「類似」の仮決定を行う。これに基づいて、ステップ4600は、さらなる処理が必要ないと決定し、ステップ4900においてこの仮決定を最終決定とする。一方、ステップ4500において(24)の関係が満たされない場合、このステップにおいて「非類似」の仮決定を行う。これに基づいて、ステップ4600は、さらなる処理が望ましいと決定する。より高いスケールの記述子が利用可能である場合、プロセスはステップ4400にループバックする。そうでない場合、ステップ4900において「非類似」の仮決定を最終決定とする。
【0077】
提案する発明のさらに別の実施形態は、2つの閾値thr1及びthr2を用いる。ここで、thr1<thr2である。すると、
【0078】
【数16】
【0079】
である場合、2つの画像は類似しているものと見なし、ステップ4500において「類似」の仮決定を行う。これに基づいて、ステップ4600は、さらなる処理が必要ないと決定し、ステップ4900においてこの仮決定を最終決定とする。一方、ステップ4500において(25)の関係が満たされない場合、このステップにおいて「非類似」の仮決定を行う。次に、ステップ4600において、
【0080】
【数17】
【0081】
である場合、ステップ4600は、さらなる処理が必要ないと決定し、ステップ4900においてこの仮決定を最終決定とする。そうでない場合、ステップ4600は、さらなる処理が望ましいと決定する。より高いスケールの記述子が利用可能である場合、プロセスはステップ4400にループバックする。そうでない場合、ステップ4900において「非類似」の仮決定を最終決定とするか、又は別法として、ステップ4900において、新たな「おそらく」という決定を生じる。この「おそらく」という決定は、全ての記述子スケールを使い果たした後で確信の持てる決定に至らなかったことを示す。
【0082】
ステップ4900において行われる決定の意味は、特定の実施態様に依存する。
【0083】
本発明の一実施形態において、Fi及びFjは時間順の画像である。例えば、これらはビデオFzのフレームであり、FjとFiの間にフレームの切れ目(例えばショット遷移又は照明効果等)が存在するかどうかを確かめることを目的とする。その場合、ステップ4900における決定は、FjとFiの類似度がそのようなフレームの切れ目を示すかどうかとなる。このようなシステムは、ビデオを分割する目的で用いられることになる。
【0084】
本発明の別の実施形態において、Fj及びFiは時間の順序がない個別の画像である。例えば、Fjは一組の画像Fzの画像であり、FiはFz内部又は外部の別の画像であり、Fz中の、Fiに類似している画像を見出すことを目的とする。その場合、ステップ4900の決定は、FjとFiの類似度が、それらの画像が類似していることを示すかどうかとなる。このようなシステムは、問い合わせによる画像の検索に、又はデータベース中の画像の分類に用いられる。
【0085】
本発明の一実施形態において、ステップ4400の記述子Vi及びVjの一方又は両方は画像ではなく画像群を表す。
【0086】
例えば、本発明の一実施形態において、Vjは、画像クラスタFjを形成する画像Fj1,Fj2,...,Fjgの記述子Vj1,Vj2,...,Vjgの関数(例えば平均(average)又は中央値(median))である。例えば、Fjは車を表す画像クラスタであり得る。その場合、画像Fiについて、記述子Vi及びVj間の類似性を確認することは、Fiが特定の画像に類似しているかどうかではなく、それが特定の画像クラス又は画像クラスタに類似しているかどうかを示す。一組の画像Fzは、そのようなクラスタを任意数含むことができ、そのような処理は、所与の画像が最も良く適合する特定のクラスタを示すことになる。さらに、クラスタは、Vjによってだけでなく、その画像の記述子の共分散行列等の他の統計量によっても表現することができる。共分散行列は、ステップ4400において、より複雑な類似度(例えばマハラノビス距離又は最尤度)の計算を可能にする。
【0087】
ビデオを分割するための本発明の別の実施形態において、VjはフレームFj1,Fj2,...,Fjgの記述子Vj1,Vj2,...,Vjgの関数(例えば平均又は中央値)である。これらのフレームは、全てがフレームFiに先行しても、全てがそれに後続しても、又は、一部が先行して一部が後続してもよい。
【0088】
本明細書に概要を説明する発明の実施形態は、少なくとも2つの値を含む上記類似度を使用して、画像間の類似性又は非類似性を確認することに及ぶ。したがって、
【0089】
ビデオを分割するための本発明の上記の実施形態では、ステップ4500において、2つのフレームFi及びFj間の類似度を用いて、フレームの切れ目を検出する。本発明の代替的な実施形態は、この類似度だけでなく、フレームFi及びFjの周囲のフレーム間の類似度も用いる。
【0090】
例えば、本発明の一実施形態において、j=i−1であり、フレームの切れ目の検出は、類似度Di+k-1,i+kに依拠し、∀k∈[−t1,t2]である。好ましい実施形態において、t1=t2=tである。したがって、フレームFi+kは、フレームFiを中心とする時間窓を形成する。次に、次の場合にのみ、Fi-1及びFi間でフレームの切れ目を検出する。
【0091】
【数18】
【0092】
式(27)及び(28)によれば、各類似度Di-1,iは、Di-1,iを中心とする2t+1のサイズの時間窓内にあると考えられる。その場合、Di-1,iが時間窓内の最大距離であり、且つ、時間窓内の2番目に大きい距離よりも少なくともthr倍大きい場合にのみ、フレームFi-1とフレームFiの間で切れ目を検出する。このような時間適応的な方式は、フレーム間の高い動きレベルから生じる誤った検出の数を低減することを目的とする。フレームの切れ目を検出するためにそのような時系列を処理するそのような方式はいくつかある。
【0093】
本発明の好ましい実施形態において、スケール指向性の記述子の処理において使用する閾値及び制御パラメータはいずれもスケール指向性である。
【0094】
代替的な実施形態において、スケール指向性の記述子の逐次処理は、ユーザによる指示又はこのプロセスを使用する自動システムによる指示に従って、最高スケールの記述子を処理し終える前に終了する。これは、例えばリアルタイムのオンライン用途で、またシステムがデータレートに付いて行けない場合に、システムの速度をさらに高めるために行うことができる。
【0095】
本発明の別の実施形態を図5に示す。ステップ5100において、上で説明したように、スケールに固有でチャネルに固有の記述子を抽出する。ステップ5250において、これらの記述子を融合させて、スケール指向性のマルチチャネル記述子Vi(SCQ),...,Vi(SCA)の組にする。ここで、SCA及びSCQはそれぞれ最低の記述子スケール及び最高の記述子スケールである。ステップ5410、...、5490において、スケール指向性の記述子の対Vi(SCA)及びVj(SCA),...,Vi(SCQ)及びVj(SCQ)を使用して、画像Fiと画像Fjの間の類似度Dj,i(SCA),...,Dj,i(SCQ)を計算する。したがって、複数の類似度を記述子のスケール毎に1つずつ計算する。ステップ5510、...、5590において、各類似度を用いて、2つの画像の類似性又は非類似性に関する仮決定を行う。したがって、複数の仮決定を、記述子のスケール毎に1つずつ行う。次に、ステップ5900において、複数の仮決定を用いて、2つの画像の類似性又は非類似性に関する最終決定を行う。
【0096】
図5に示すようなスケール指向性の並列構成の目的は、異なるスケールでの類似性の決定を処理することによって、画像Fiと画像Fjの間の関係のより徹底した調査を可能にするためである。したがって、このようなシステムは、最終的な類似性の決定だけでなく、「これらの画像は非常に粗いレベルでは類似しているが、細部では著しく異なる」といった付加的な情報も提供することができる。対照的に、スケールに固有でチャネルに固有の記述子を融合させて単一のマルチスケールでマルチチャネルの記述子にするシステムは、2つの画像に関して1つの類似性の決定しか提供することができない。
【0097】
したがって、所与の画像Fiに類似している一組の画像から画像を検索するための本発明の一実施形態では、図5に示すような方式により、検索結果を階層形式で提示することができる。最初に、粗いレベルでFiに類似している(すなわち、低スケールの記述子によれば類似している)一組の画像FAを提示し、次に、FAのサブセットであり、より細かい詳細レベルでFiに類似している一組の画像FBを提示し、以下同様の順序で提示する。
【0098】
フレームの切れ目検出及びビデオ分割のための本発明の別の実施形態において、図5に示すような方式により、異なる粒度(すなわち粗い、中程度、細かい、等)で分割を行うことができる。
【0099】
図5において、ステップ5100は図4のステップ4100と類似しており、ステップ4100について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0100】
同様に、ステップ5250は図4のステップ4250と類似しており、ステップ4250について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0101】
同様に、ステップ5410、...、5490の各々は図4のステップ4400と類似しており、ステップ4400について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0102】
同様に、ステップ5510、...、5590の各々は図4のステップ4500と類似しており、ステップ4500について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0103】
本発明の一実施形態において、ステップ5510、...、5590の仮決定は二分決定であり、例えば「1」が「類似」を示し、「0」が「非類似」を示す。
【0104】
本発明の別の実施形態において、ステップ5510、...、5590の仮決定は二分ではなく、少なくとも3つの値を含む。このような場合、処理ステップ5510、...、5590の結果の記述には、「仮決定」という用語よりも「尤度」という用語のほうが優れている。例えば、本発明の一実施形態において、ステップ5510、...、5590の各々は3つの閾値を用いる。類似度が第1の閾値を下回る場合、「非類似」を示す類似性の尤度「0」を生じる。類似度が第1の閾値を上回るが、第1の閾値よりも高い第2の閾値を下回る場合、「おそらく非類似」を示す類似性の尤度「1」を生じる。類似度が第2の閾値を上回るが、第2の閾値よりも高い第3の閾値を下回る場合、「おそらく類似」を示す類似性の尤度「2」を生じる。類似度が第3の閾値を上回る場合、「類似」を示す類似性の尤度「3」を生じる。本発明の別の実施形態において、尤度は、閾値処理によってではなく、類似度の一定範囲(例えば0〜1)への正規化により生成される。
【0105】
本発明の一実施形態のステップ5900において、二分仮決定又は尤度をZj,i(SCA),...,Zj,i(SCQ)として示すと、FiとFjが類似しているという最終決定は、次の場合にのみ行う。
【0106】
【数19】
【0107】
ここで、thrfは閾値であり、WSCA,...,WSCQは、各スケール指向性の決定又は尤度に与える重要度を制御する重みである。これらの重みは、所望であれば、WSCA=...=WSCQ=1を設定することによって排除することができる。
【0108】
ステップ5510、...、5590により少なくとも3つの値を含む尤度を生成する本発明の別の実施形態において、2つの画像は、式(29)の条件が当てはまり、さらに、新たな第2の閾値を下回る個別の尤度がないか、又は所与の数以下である場合にのみ、類似しているものと見なす。
【0109】
本発明の好ましい実施形態において、スケール指向性の記述子の処理において使用する閾値及び制御パラメータはいずれもスケール指向性である。
【0110】
本実施形態において説明するような一組の記述子の並列処理において、最終的な決定に至るために使用することのできるこのような方式は多くある。
【0111】
本発明の一実施形態は、スケールに固有でチャネルに固有の記述子を融合させて、異なるカラーチャネルにわたる少なくとも2つの記述子にすることを特徴とする。例えば、Yチャネル、Cbチャネル及びCrチャネルにわたるスケールに固有でチャネルに固有の記述子の場合、本発明の一実施形態は、3つのマルチスケールでチャネル指向性の記述子を生成するが、別の実施形態は、1つがYチャネル用、もう1つがCbチャネル及びCrチャネル用の2つのマルチスケールでチャネル指向性の記述子を生成する。本発明の好ましい実施形態では、記述子を実際に複数のスケールで計算し、融合させてチャネル指向性の記述子にするが、代替的な実施形態は、単一のスケールでのみ記述子を計算し、それらを融合させてチャネル指向性の記述子にする。
【0112】
前の段落の文章に沿った本発明の一実施形態を図6に示す。ステップ6100において、上記で説明したように、スケールに固有でチャネルに固有の記述子を抽出する。ステップ6250において、これらの記述子を融合させて、マルチスケールでチャネル指向性の記述子VCCAi,...,VCCQiの組にする。ここで、CCA,...,CCQはカラーチャネル又はカラーチャネル群である。例えば、本発明の一実施形態において、CCAはYチャネルを表し、CCBはCbCrのチャネル対を表す。本発明の別の実施形態において、CCAはRGBのRチャネルを表し、CCBはGチャネルを表し、CCCはBチャネルを表す。ステップ6410、...、6490において、チャネル指向性の記述子対VCCAi及びVCCAj,...,VCCQi及びVCCQjを用いて、画像Fiと画像Fjの類似度DCCAj,i,...,DCCQj,iを計算する。このように、複数の類似度を、チャネル指向性の記述子毎に1つずつ計算する。ステップ6510、...、6590において、各類似度を用いて、2つの画像の類似性又は非類似性に関する仮決定を行う。したがって、複数の仮決定を、チャネル指向性の記述子毎に1つずつ行う。次に、ステップ6900において、複数の仮決定を用いて、2つの画像の類似性又は非類似性に関する最終決定を行う。
【0113】
図6に示すようなチャネル指向性の並列構成の目的は、異なるカラーチャネルにわたる類似性の決定を処理して、画像に関する異なる情報を取得することによって、画像Fiと画像Fjの間の関係のより徹底した調査を可能にすることである。したがって、このようなシステムは、最終的な類似性の決定だけでなく、「これらの画像は色差(chrominance)チャネルでは類似しているが、輝度チャネルでは類似していない」といった付加的な情報も提供することができる。対照的に、スケールに固有でチャネルに固有の記述子を融合させて単一のマルチスケールでマルチチャネルの記述子にするシステムは、2つの画像に関して1つの類似性の決定しか提供することができない。
【0114】
したがって、フレームの切れ目(例えばショット遷移又は照明効果等)を検出するための本発明の一実施形態において、図6に示すようなシステムは、フレームの切れ目を確実に検出するだけでなく、ショット遷移を他の照明効果と分離する。例えば、2つのフレームが色差と輝度の両方に関して著しく異なることが分かった場合、これはショット遷移を示す。一方、2つのフレームが輝度に関しては著しく異なるが、色差に関してはほとんど変わらないことが分かった場合、これは、ショット遷移でなく全体的な照明効果を示す。
【0115】
所与の画像Fiに類似している一組の画像から画像を検索するための本発明の代替的な実施形態では、図6に示すような方式により、問い合わせ画像に意味的に類似している画像、例えば同一の風景又は都市景観のものであるが、異なる時刻に異なる照明条件で取り込まれた画像を検索することができる。
【0116】
図6において、ステップ6100は図5のステップ5100と類似しており、ステップ5100について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0117】
同様に、ステップ6250は図5のステップ5250と類似しており、ステップ5200について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0118】
同様に、ステップ6410、...、6490は図5のステップ5410、...、5490と類似しており、ステップ5410、...、5490について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0119】
同様に、ステップ6510、...、6590は図5のステップ5510、...、5590と類似しており、ステップ5510、...、5590について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0120】
同様に、ステップ6900は図5のステップ5900と類似しており、ステップ5900について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0121】
本発明の別の実施形態は、スケールに固有でチャネルに固有の記述子を最初に、スケールに固有でチャネルに固有の、特徴部の意味に指向性を持つ(feature-semantics-oriented)記述子に分割すること、及び、それらを次に融合させて、特徴部の意味の異なる少なくとも2つの記述子にすることを特徴とする。例えば、本発明の一実施形態において、6つの異なるスケールで3つの異なるカラーチャネルにわたる、スケールに固有でチャネルに固有の記述子の場合、全部で18個の記述子が最初に利用可能である。これらの18個の記述子を、半分が色内容要素(例えば式(1)のLL)のみを含み、他の半分が色相関要素(例えば(2)〜(4)のHL、LH及びHH)のみを含む36個の記述子に分割する。次に、これらの36個の記述子を融合させて、1つが複数のスケールで、且つ異なるチャネルにわたる全ての色内容要素を含み、もう1つが複数のスケールで、且つ異なるチャネルにわたる全ての色相関要素を含む2つの記述子にする。本発明の別の実施形態では、最初の各記述子を3つ以上の記述子に分割する。例えば、各記述子を、LL、HL、LH及びHHタイプの要素のそれぞれに1つずつの、4つの記述子に分割する。次に、これらの記述子を融合させて、異なるスケールで、且つ異なるチャネルにわたって1タイプの要素のみ(例えばLLのみ又はHHのみ)をそれぞれ含む4つの最終的な記述子にする。本発明の好ましい実施形態では、記述子を実際に複数のスケールで複数のチャネルにわたって計算するが、代替的な実施形態は、記述子を単一のスケールのみで、及び/又は単一のチャネルのみについて計算してもよい。
【0122】
前の段落の文章に沿った本発明の一実施形態を図7に示す。ステップ7100において、上記で説明したように、スケールに固有でチャネルに固有の記述子を抽出する。ステップ7200において、上記で説明したように、これらの記述子を特徴部の意味に応じて分割する。ステップ7250において、結果として得られる記述子を融合させて、マルチスケールでマルチチャネルの、特徴部の意味に指向性を持つ記述子VFSAi,...,VFSQiの組にする。ここで、FSA,...,FSQは特徴部のタイプを表す。例えば、本発明の一実施形態において、FSAはLL要素を表し、FSBはHL要素、LH要素及びHH要素を表す。本発明の別の実施形態において、FSAはLL要素を表し、FSBはHL要素を表し、FSCはLH要素を表し、FSDはHH要素を表す。ステップ7410、...、7490において、特徴部の意味に指向性を持つ記述子対VFSAi及びVFSAj,...,VFSQi及びVFSQjを用いて、画像Fiと画像Fjの間の類似度DFSAj,i,...,DFSQj,iを計算する。したがって、複数の類似度を、特徴部の意味に指向性を持つ記述子毎に1つずつ計算する。ステップ7510、...、7590において、各類似度を用いて、2つの画像の類似性又は非類似性に関する仮決定を行う。このように、複数の仮決定を、特徴部の意味に指向性を持つ記述子毎に1つずつ行う。次に、ステップ7900において、複数の仮決定を用いて、2つの画像の類似性又は非類似性に関する最終決定を行う。
【0123】
図7に示すような特徴部の意味に指向性を持つ並列構成の目的は、異なる特徴部のタイプに基づく類似性の決定を処理して、画像に関する異なる情報を取得することによって、画像Fiと画像Fjの間の関係のより徹底した調査を可能にすることである。したがって、このようなシステムは、最終的な類似性の決定だけでなく、「これらの画像は局所エッジに関しては類似しているが、色内容に関しては類似していない」といった付加的な情報も提供することができる。対照的に、スケールに固有でチャネルに固有の記述子を融合させて単一のマルチスケールでマルチチャネルの記述子にするシステムは、2つの画像に関して1つの類似性の決定しか提供することができない。
【0124】
したがって、フレームの切れ目(例えばショット遷移又は照明効果等)を検出するための本発明の一実施形態において、図7に示すようなシステムは、フレームの切れ目を確実に検出するだけでなく、ショット遷移を他の照明効果と分離する。例えば、2つのフレームが色内容と色相関の両方に関して著しく異なることが分かった場合、これはショット遷移を示す。一方、2つのフレームが色内容に関しては著しく異なるが、色相関に関してはほとんど変わらないことが分かった場合、これは、ショット遷移でなく全体的な照明効果を示す。
【0125】
所与の画像Fiに類似している一組の画像から画像を検索するための本発明の代替的な実施形態では、図7に示すような方式により、問い合わせ画像に意味的に類似している画像、例えば同一シーンのものであるが、異なる照明条件又は異なる機材で取り込まれたためにコントラストレベルの異なる画像を検索することができる。
【0126】
図7において、ステップ7100は図6のステップ6100と類似しており、ステップ6100について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0127】
図7において、ステップ7200は図6のステップ6200と類似しており、ステップ6200について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0128】
同様に、ステップ7250は図6のステップ6250と類似しており、ステップ6250について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0129】
同様に、ステップ7410、...、7490は図6のステップ6410、...、6490と類似しており、ステップ6410、...、6490について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0130】
同様に、ステップ7510、...、7590は図6のステップ6510、...、6590と類似しており、ステップ6510、...、6590について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0131】
同様に、ステップ7900は図6のステップ6900と類似しており、ステップ6900について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0132】
本発明の別の実施形態は、スケールに固有でチャネルに固有の記述子を最初に、スケールに固有でチャネルに固有の領域指向性の記述子に分割すること、及び、それらを次に融合させて、画像内の異なる領域をカバーする少なくとも2つの記述子にすることを特徴とする。例えば、本発明の一実施形態において、5つの異なるスケール64×64、32×32、...、4×4で3つの異なるカラーチャネルにわたる、スケールに固有でチャネルに固有の記述子の場合、全部で15個の記述子が最初に利用可能である。これらの15個の記述子を、15個の記述子からなる4つの組に分割する。各組は、画像の特定の象限に対応する要素のみを含む。すなわち、1組が左上の象限用、1組が右上の象限用、1組が左下の象限用、1組が右下の象限用である。次に、これらの記述子を融合させて、1つが複数のスケールで、且つ異なるチャネルにわたる全ての記述子要素を画像の左上の象限について含み、1つが同様の記述子要素を画像の右上の象限について含み、以下同様である4つの記述子にする。本発明の別の実施形態では、画像の縦スライスに対応する複数の領域指向性の記述子を形成する。さらに別の実施形態では、画像の横スライスに対応する複数の領域指向性の記述子を形成する。本発明の好ましい実施形態では、記述子を実際に複数のスケールで複数のチャネルにわたって計算するが、代替的な実施形態は、記述子を単一のスケールのみで、及び/又は単一のチャネルのみについて計算してもよい。
【0133】
前の段落の文章に沿った本発明の一実施形態を図8に示す。ステップ8100において、上記で説明したように、スケールに固有でチャネルに固有の記述子を抽出する。ステップ8200において、上記で説明したように、これらの記述子を画像領域に応じて分割する。ステップ8250において、結果として得られる記述子を融合させて、マルチスケールでマルチチャネルの領域指向性記述子VREAi,...,VREQiの組にする。ここで、REA,...,REQは画像領域を表す。例えば、本発明の一実施形態において、REAは画像の左上の象限を表し、REBは画像の右上の象限を表し、RECは画像の左下の象限を表し、REDは画像の右下の象限を表す。ステップ8410、...、8490において、領域指向性の記述子対VREAi及びVREAj,...,VREQi及びVREQjを用いて、画像Fiと画像Fjの間の類似度DREAj,i,...,DREQj,iを計算する。このように、複数の類似度を、領域指向性の記述子毎に1つずつ計算する。ステップ8510、...、8590において、各類似度を用いて、2つの画像の類似性又は非類似性に関する仮決定を行う。したがって、複数の仮決定を、領域指向性の記述子毎に1つずつ行う。次に、ステップ8900において、複数の仮決定を用いて、2つの画像の類似性又は非類似性に関する最終決定を行う。
【0134】
図7に示すような領域指向性の並列構成の目的は、画像の異なる領域から生じる類似性の決定を処理することによって、画像Fiと画像Fjの間の関係のより徹底した調査を可能にすることである。したがって、このようなシステムは、最終的な類似性の決定を提供し、「これらの画像は或る領域では非常に類似しているが、他の領域では類似していない」といった情報を提供し、且つ、異なる画像の対応する領域間の関係を特定することができる。対照的に、スケールに固有でチャネルに固有の記述子を融合させて単一のマルチスケールでマルチチャネルの記述子にするシステムは、2つの画像に関して1つの類似性の決定しか提供することができない。
【0135】
したがって、所与の画像Fiに類似している一組の画像から画像を検索するための本発明の一実施形態では、図8に示すような方式により、問い合わせ画像に部分的に類似している画像、例えば同一シーンのものであるが、カメラの視野(optical field)に突然歩いて入ってきてシーンの左側部分を遮る人物により生じる遮蔽を有する画像を検索することができる。
【0136】
同様に、フレームの切れ目を検出するための本発明の代替的な実施形態において、図8に示すようなシステムは、フレームの切れ目を確実に検出するだけでなく、ショット遷移を他のショット内障害(例えば、カメラに近い速度で(at speed close to the camera)移動し、視野を短い間遮る人物)と分離する。
【0137】
図8において、ステップ8100は図7のステップ7100と類似しており、ステップ7100について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0138】
同様に、ステップ8200は図7のステップ7200と類似しており、ステップ7200について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0139】
同様に、ステップ8250は図7のステップ7250と類似しており、ステップ7250について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0140】
同様に、ステップ8410、...、8490は図7のステップ7410、...、7490と類似しており、ステップ7410、...、7490について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0141】
同様に、ステップ8510、...、8590は図7のステップ7510、...、7590と類似しており、ステップ7510、...、7590について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0142】
同様に、ステップ8900は図7のステップ8900と類似しており、ステップ8900について上で説明した全ての方法論、拡張及び変更がここでも当てはまる。
【0143】
本発明の好ましい実施形態では、多くのスケールで、且つ複数のチャネルにわたって記述子を抽出することが明確に理解されるべきである。しかし、本発明の代替的な実施形態において、そうである必要はない。例えば、スケール指向性の枠組みを実現するために、単一のカラーチャネルについて、及び/又は単一の画像領域について記述子を抽出してもよい。同様に、チャネル指向性の枠組みを実現するために、単一のスケールで、及び/又は単一の画像領域について記述子を抽出してもよい。同様に、特徴部の意味に指向性を持つ枠組みを実現するために、単一のスケールで、及び/又は単一のチャネルについて、及び/又は単一の画像領域について記述子を抽出してもよい。同様に、領域指向性の枠組みを実現するために、単一のスケールで、及び/又は単一のチャネルについて記述子を抽出してもよい。
【0144】
また、本明細書中で説明する逐次構成及び並列構成は、特定の記述子の分割又は指向に限定されないことが明確に理解されるべきである。特定の構成を特定の記述子の指向に適用するのは単に例示を目的とするものである。例えば、上記の実施形態は、スケール指向性の記述子についてのみ逐次構成を検討する。本発明の代替的な実施形態は、他の記述子の指向に逐次構成を使用する。例えば、本発明の代替的な実施形態は、チャネル指向性の記述子を逐次構成で処理し、チャネルのうちの1つにおいて所与の画像に類似していない画像を迅速にフィルタリングで除去し、他のチャネルの処理を不要にすることを目指す。本発明のさらに別の代替的な実施形態は、特徴部の意味に指向性を持つ記述子を逐次構成で、上記と同じ原理で処理する。本発明のさらに別の代替的な実施形態は、領域指向性の記述子を逐次構成で、上記と同じ原理で処理する。
【0145】
また、システムは、複数の記述子の指向に依拠してもよいことが明確に理解されるべきである。例えば、本発明の一実施形態では、スケールに固有でチャネルに固有の記述子を最初に計算した後に、スケール指向性で特徴部の意味に指向性を持つ記述子を形成する。例えば、4つの記述子、すなわち、低スケールの色内容要素用の1つの記述子、高スケールの色内容要素用の1つの記述子、低スケールの色相関要素用の1つの記述子、及び高スケールの色相関要素用の1つの記述子を形成する。本発明の一実施形態では、そのような記述子を、上述のように並列構成で処理する。本発明の別の実施形態では、そのような記述子を、上述のように逐次構成で処理する。本発明のさらに別の実施形態では、図9に示すようなハイブリッド構成を用いる。図9において、SCA及びSCQはそれぞれ最低の記述子スケール及び最高の記述子スケールであり、FSA,...,FSQは特徴部のタイプを表す。
【0146】
このハイブリッドの枠組みは、単一の記述子の指向にも利用することができる。例えば、1つの代替的な実施形態は逐次構成に依拠し、それによって、各ループにおいて、単一ではなく少数のスケール指向性記述子を、組み込まれた並列構成で処理する。このように、本発明の異なる実施形態は、単一の記述子の指向に依拠するか、複数の記述子の指向に依拠するかに関わらず、逐次構成又は並列構成又はハイブリッド構成に依拠してもよいことも明確に理解されるべきである。また、図9は、並列構成を逐次構成に埋め込む1つの可能なハイブリッド構成を例示目的で示すに過ぎないことを明確に理解すべきである。代替的な実施形態は他のハイブリッド構成、例えば、1つ又は複数の逐次構成を並列構成に埋め込む構成を使用する。
【0147】
図9に示すように、画像を最初に、粗い開始スケールで処理し、確信の持てる決定に至らない場合、画像を次に細かいスケールで処理し、以下同様の操作を行い、確信の持てる決定に至るか、又は利用可能/許容可能なスケールを使い果たすまで続ける。
【0148】
好ましい実施形態では、各スケールについて、並列処理される画像毎に4つの記述子があり、それぞれの結果を組み合わせて、そのスケールの決定を得る。これは図9と類似しているが、使用される記述子は以下の、(i)輝度から抽出される色内容、(ii)輝度から抽出される色相関、(iii)色差から抽出される色内容、及び(iv)色差から抽出される色相関である。
【0149】
代替案では、2つの色内容記述子(1つが輝度用、もう1つが色差(chrominance)用)を開始スケールのみについて用いる。全ての他のスケールについては、2つの色相関記述子のみを用いる。
【0150】
さらに、上記の実施形態では、フレームの切れ目を検出するために、連続フレームの全ての対の処理を検討した。代替的な実施形態は、フレームをより粗く処理してもよい。代替的な実施形態は、4番目毎のフレームのみを処理し、さらに別の実施形態は、16番目毎のフレームのみを処理する。このような向上により、ビデオ分割システムの速度がさらに上がる。
【0151】
さらに、上記の説明は、各フレームがその画素値で表される未圧縮のデジタルビデオの処理に関する。本発明は、復元していないMPEG圧縮ビデオにも直接適用することができる。
【0152】
MPEGビデオの性質は、当業者にはよく知られており、J. Watkinsonの著書「The MPEG Handbook: MPEG-1, MPEG-2, MPEG-4」(Focal Press, Oxford 2001, ISBN:0-240-51656-7)に専門的に記載されている。
【0153】
MPEG圧縮ビデオに関する本発明の一実施形態では、ビデオのIフレームのみを処理する。より具体的には、IフレームのDC表現のみを処理する。すなわち、8×8画素の各ブロックについて、そのDCT変換のDC成分のみを取る。事実上、IフレームのDC表現は単に、8×8のブロック平均を用いて圧縮前の原フレームをリサンプリングしたものである。DC成分は、圧縮ビデオストリームから復元を行うことなく直接取り出すことができるため、本発明の実施形態は、MPEG圧縮ビデオのIフレームの処理に直接適用できることが明らかである。
【0154】
本発明は、例えばコンピュータシステムにおいて、適切なソフトウェア及び/又はハードウェアの変更を施して実施することができる。例えば、本発明は、プロセッサ又は制御装置等の制御又は処理手段、メモリ、磁気記憶装置、CD、DVD等の画像記憶手段を含むデータ記憶手段、ディスプレイ若しくはモニタ又はプリンタ等のデータ出力手段、キーボード等のデータ入力手段、及びスキャナ等の画像入力手段、又はそのような構成要素の任意の組み合わせ並びに追加の構成要素を有するコンピュータ又は同様の装置を用いて実施することができる。本発明の態様は、ソフトウェア及び/又はハードウェア形態で、又は特定用途向け装置において提供するか、又は集積回路等の特定用途向けモジュールを提供することができる。本発明の一実施形態による装置中のシステムの構成要素は、他の構成要素から遠隔して、例えばインターネットを介して設けられてもよい。
【0155】
コンピュータシステムの形態の適切な装置のブロック図を図10に示し、この図において、制御ユニット10100は、画像記憶手段10200、記述子記憶手段10300及びディスプレイ10400に接続される。画像記憶手段10200は、上記の実施形態により表現又は比較される画像に対応するデータを記憶する。これは、1つの画像、複数の画像、画像クラスタ、画像シーケンス又は画像データベース全体に対応するデータであってもよい。記述子記憶手段10300は、データベースであってもよく、制御ユニット10100により計算される副記述子(sub-descriptors)を含む導出された記述子をすべて記憶する。制御ユニットの動作の結果は、ディスプレイ10400上でユーザに対して表示する。
【0156】
「スケール」及び「解像度」という用語は、本明細書において置き換え可能に用いられる。画像の領域は画像全体又は画像の部分を意味し得る。「記述子」という用語は、決定を行うプロセスにおいて使用され得る、画像又は画像の部分の導出された表現を指す。「副記述子」という用語は、関連付けられて記述子を形成する、画像又は画像の部分の導出された表現を指す。しかし、当業者であれば、この区別は便宜的なものに過ぎず、各用語は、上述の方法の特定の点を指すことを認識するであろう。特定の実施形態の各副記述子は、異なる実施形態では記述子として機能する場合があり、その逆の場合も同様である。したがって、特定の実施形態では記述子という用語のみが用いられる。
【特許請求の範囲】
【請求項1】
少なくとも1つの画像を表現する方法であって、
画像の少なくとも1つの領域について色情報及び/又は色相関情報を取得する1つ以上の副記述子を生成することと、
少なくとも2つの記述子を生成するために、前記副記述子または副記述子要素を、対応する特性に応じて関連付けることと
を含む、少なくとも1つの画像を表現する方法。
【請求項2】
副記述子は、画像の複数の領域について生成され、
たとえば、前記領域の各々は、n×n画素のサイズのブロックに対応する
請求項1に記載の方法。
【請求項3】
画像の複数の重複しない領域の各々について副記述子を導出することを含む請求項1または2に記載の方法。
【請求項4】
前記画像の複数の表現を複数のスケールで生成するために、前記画像を処理することと、
前記複数のスケールについて副記述子を導出することと
を含み、
たとえば前記処理はダウンサンプリングを含み、
たとえば前記ダウンサンプリングは、画素ブロックを平均することを含む
請求項1〜3のいずれか一項に記載の方法。
【請求項5】
複数のカラーチャネルの各々について前記画像を処理することと、
前記チャネルの各々について副記述子を導出することと
を含み、
任意選択で、同一スケールが異なるカラーチャネルに用いられ、
任意選択で、異なるスケールが異なるチャネルに用いられる、
請求項1〜4のいずれか一項に記載の方法。
【請求項6】
副記述子を導出する異なるプロセスが、異なる領域及び/又は異なるスケール及び/又は異なるカラーチャネルに用いられる、請求項1〜5のいずれか一項に記載の方法。
【請求項7】
或る領域の少なくとも1つの副記述子要素、あるいは
或る領域の複数の副記述子要素の各々又は全て
が、前記領域の画素のサブセットのみを用いて導出される、請求項1〜6のいずれか一項に記載の方法。
【請求項8】
前記副記述子要素を導出するために用いられる計算は、結果として得られる副記述子要素の数が、前記副記述子要素を導出するために用いられる画素数よりも少ないようになっている、請求項1〜7のいずれか一項に記載の方法。
【請求項9】
特定の記述子要素を除去することによって副記述子の次元数を下げることを含む、請求項1〜8のいずれか一項に記載の方法。
【請求項10】
前記複数の副記述子又は副記述子要素は、色、色相関、カラーチャネル、スケール、領域のうちの1つ又は複数に基づいて関連付けられる、請求項1〜9のいずれか一項に記載の方法。
【請求項11】
副記述子又は副記述子要素は、
特性の単一の値について、又は、
単一のスケール、又は低スケール及び高スケール、又は低スケール、中スケール及び高スケール等の特性の値の範囲について、
必要な変更を加えて関連付けられる、請求項1〜10のいずれか一項に記載の方法。
【請求項12】
画像群を表現する方法であって、
請求項1〜11のいずれか一項に記載の方法を用いて各画像の表現を導出することと、
前記表現を用いて前記画像群を表現することと
を含み、
任意選択で、たとえば前記表現の関数を導出して前記画像群を表現することを含み、
前記関数は、平均、中央値、算術平均、共分散等の統計測度を含む、
請求項1〜11のいずれか一項に記載の方法。
【請求項13】
画像及び/又は画像群を比較する方法であって、
請求項1〜12のいずれか一項に記載の方法を用いて導出された表現のそれぞれを比較することを含み、
前記比較は、特性に応じて対応する記述子を比較することを含む
画像及び/又は画像群を比較する方法。
【請求項14】
請求項1〜13のいずれか一項に記載の方法を用いて画像又は画像群を符号化する方法、または、
そのような方法により符号化されたデータの、例えば伝送、中継又は受信による、使用、または、
そのような方法を用いて符号化された画像又は画像シーケンスを復号する方法。
【請求項15】
請求項1〜14のいずれか一項に記載の方法を実行するための、装置、コンピュータプログラム、システム、又はコンピュータ読み取り可能な記憶媒体であって、
たとえば、請求項1〜12のいずれか一項に記載の方法により画像又は画像群を表現する装置、または、請求項13に記載の方法により画像及び/又は画像群を比較する装置であって、たとえば、画像データ及び/又は画像記述子を記憶する記憶手段と、前記方法を実行する処理手段とを備えるもの。
【請求項1】
少なくとも1つの画像を表現する方法であって、
画像の少なくとも1つの領域について色情報及び/又は色相関情報を取得する1つ以上の副記述子を生成することと、
少なくとも2つの記述子を生成するために、前記副記述子または副記述子要素を、対応する特性に応じて関連付けることと
を含む、少なくとも1つの画像を表現する方法。
【請求項2】
副記述子は、画像の複数の領域について生成され、
たとえば、前記領域の各々は、n×n画素のサイズのブロックに対応する
請求項1に記載の方法。
【請求項3】
画像の複数の重複しない領域の各々について副記述子を導出することを含む請求項1または2に記載の方法。
【請求項4】
前記画像の複数の表現を複数のスケールで生成するために、前記画像を処理することと、
前記複数のスケールについて副記述子を導出することと
を含み、
たとえば前記処理はダウンサンプリングを含み、
たとえば前記ダウンサンプリングは、画素ブロックを平均することを含む
請求項1〜3のいずれか一項に記載の方法。
【請求項5】
複数のカラーチャネルの各々について前記画像を処理することと、
前記チャネルの各々について副記述子を導出することと
を含み、
任意選択で、同一スケールが異なるカラーチャネルに用いられ、
任意選択で、異なるスケールが異なるチャネルに用いられる、
請求項1〜4のいずれか一項に記載の方法。
【請求項6】
副記述子を導出する異なるプロセスが、異なる領域及び/又は異なるスケール及び/又は異なるカラーチャネルに用いられる、請求項1〜5のいずれか一項に記載の方法。
【請求項7】
或る領域の少なくとも1つの副記述子要素、あるいは
或る領域の複数の副記述子要素の各々又は全て
が、前記領域の画素のサブセットのみを用いて導出される、請求項1〜6のいずれか一項に記載の方法。
【請求項8】
前記副記述子要素を導出するために用いられる計算は、結果として得られる副記述子要素の数が、前記副記述子要素を導出するために用いられる画素数よりも少ないようになっている、請求項1〜7のいずれか一項に記載の方法。
【請求項9】
特定の記述子要素を除去することによって副記述子の次元数を下げることを含む、請求項1〜8のいずれか一項に記載の方法。
【請求項10】
前記複数の副記述子又は副記述子要素は、色、色相関、カラーチャネル、スケール、領域のうちの1つ又は複数に基づいて関連付けられる、請求項1〜9のいずれか一項に記載の方法。
【請求項11】
副記述子又は副記述子要素は、
特性の単一の値について、又は、
単一のスケール、又は低スケール及び高スケール、又は低スケール、中スケール及び高スケール等の特性の値の範囲について、
必要な変更を加えて関連付けられる、請求項1〜10のいずれか一項に記載の方法。
【請求項12】
画像群を表現する方法であって、
請求項1〜11のいずれか一項に記載の方法を用いて各画像の表現を導出することと、
前記表現を用いて前記画像群を表現することと
を含み、
任意選択で、たとえば前記表現の関数を導出して前記画像群を表現することを含み、
前記関数は、平均、中央値、算術平均、共分散等の統計測度を含む、
請求項1〜11のいずれか一項に記載の方法。
【請求項13】
画像及び/又は画像群を比較する方法であって、
請求項1〜12のいずれか一項に記載の方法を用いて導出された表現のそれぞれを比較することを含み、
前記比較は、特性に応じて対応する記述子を比較することを含む
画像及び/又は画像群を比較する方法。
【請求項14】
請求項1〜13のいずれか一項に記載の方法を用いて画像又は画像群を符号化する方法、または、
そのような方法により符号化されたデータの、例えば伝送、中継又は受信による、使用、または、
そのような方法を用いて符号化された画像又は画像シーケンスを復号する方法。
【請求項15】
請求項1〜14のいずれか一項に記載の方法を実行するための、装置、コンピュータプログラム、システム、又はコンピュータ読み取り可能な記憶媒体であって、
たとえば、請求項1〜12のいずれか一項に記載の方法により画像又は画像群を表現する装置、または、請求項13に記載の方法により画像及び/又は画像群を比較する装置であって、たとえば、画像データ及び/又は画像記述子を記憶する記憶手段と、前記方法を実行する処理手段とを備えるもの。
【図1】
【図2A】
【図2B】
【図2C】
【図2D】
【図3A】
【図3B】
【図3C】
【図3D】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図2A】
【図2B】
【図2C】
【図2D】
【図3A】
【図3B】
【図3C】
【図3D】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【公開番号】特開2011−108262(P2011−108262A)
【公開日】平成23年6月2日(2011.6.2)
【国際特許分類】
【外国語出願】
【出願番号】特願2011−10051(P2011−10051)
【出願日】平成23年1月20日(2011.1.20)
【分割の表示】特願2005−278247(P2005−278247)の分割
【原出願日】平成17年9月26日(2005.9.26)
【出願人】(501253316)ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】MITSUBISHI ELECTRIC R&D CENTRE EUROPE B.V.
【住所又は居所原語表記】20 Frederick Sanger Road, The Surrey Research Park, Guildford, Surrey GU2 5YD, Great Britain
【Fターム(参考)】
【公開日】平成23年6月2日(2011.6.2)
【国際特許分類】
【出願番号】特願2011−10051(P2011−10051)
【出願日】平成23年1月20日(2011.1.20)
【分割の表示】特願2005−278247(P2005−278247)の分割
【原出願日】平成17年9月26日(2005.9.26)
【出願人】(501253316)ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】MITSUBISHI ELECTRIC R&D CENTRE EUROPE B.V.
【住所又は居所原語表記】20 Frederick Sanger Road, The Surrey Research Park, Guildford, Surrey GU2 5YD, Great Britain
【Fターム(参考)】
[ Back to top ]