(57)【特許請求の範囲】
【請求項１】
クエリ映像と目標映像を比較する方法であって、
クエリ映像のフレームおよび目標映像のフレームを複数のブロックに分割するステップと、
ブロックに対する平均明度値を計算するステップと、
ブロックに対する平均明度値の時間的変化から極小値および極大値を抽出するステップとを含み、抽出された極小値および極大値が主要極小値および主要極大値であり、更に、
主要極小値および主要極大値から主要上昇部および主要下降部を取得するステップと、
主要上昇部および主要下降部を用いて、クエリ映像と目標映像の間にアラインメントが存在するかどうかを判定するステップと
を含む、方法。
【請求項２】
クエリ映像と目標映像の間の類似性距離を計算するステップを含む、請求項１に記載の方法。
【請求項３】
アラインメントが存在すると分かったときに、クエリ映像と目標映像の間の類似性距離を計算するステップが実行される、請求項２に記載の方法。
【請求項４】
最良類似性距離を計算するステップと、最良類似性距離を所与の閾値と比較してクエリ映像および目標映像が複製物であるかどうかを判定するステップとを含む、請求項２に記載の方法。
【請求項５】
主要でない極小値および主要でない極大値は除外される、請求項１に記載の方法。
【請求項６】
主要上昇部および主要下降部をそれらの傾斜に従ってソートするステップと、より大きな傾斜を有するものをアラインメントの判定に用いるステップとを含む、請求項１に記載の方法。
【請求項７】
類似性距離を求めるために、シーケンスマッチングを用いるステップを含む、請求項２に記載の方法。
【請求項８】
類似性距離を求めるために、キーフレームのペアごとのマッチングを用いるステップを含む、請求項２に記載の方法。
【請求項９】
クエリ映像と目標映像を区間のリストに区分化するステップと、区間内の主要上昇部／下降部を選択するステップとを含み、区間のサイズは映像の長さに基づいて適合されている、請求項１に記載の方法。
【請求項１０】
クエリ映像が目標映像の複製物でないと判定されたときに、目標映像を保持する映像データベース内にクエリ映像を記憶するステップを含む、請求項４に記載の方法。
【請求項１１】
クエリ映像のフレームおよび目標映像のフレームを複数のブロックに分割するステップと、
ブロックに対する平均明度値を計算するステップと、
ブロックに対する平均明度値の時間的変化から極小値および極大値を抽出するステップとを含み、抽出された極小値および極大値が主要極小値および主要極大値であり、更に、
主要極小値および主要極大値から主要上昇部および主要下降部を取得するステップと、
主要上昇部および主要下降部を用いて、クエリ映像と目標映像の間にアラインメントが存在するかどうかを判定するステップと
を含む方法を実行するようにプログラムされまたは構成された、装置。
【請求項１２】
クエリ映像と目標映像の間の類似性距離を計算するようにプログラムされまたは構成された、請求項１１に記載の装置。
【請求項１３】
アラインメントが存在すると分かったときに、クエリ映像と目標映像の間の類似性距離の計算が実行されるようにプログラムされまたは構成された、請求項１１に記載の装置。
【請求項１４】
最良類似性距離を計算し、最良類似性距離を所与の閾値と比較して、クエリ映像および目標映像が複製物であるかどうかを判定するようにプログラムされまたは構成された、請求項１１に記載の装置。
【請求項１５】
主要でない極小値および主要でない極大値は除外される、請求項１１に記載の装置。
【請求項１６】
主要上昇部および主要下降部をそれらの傾斜に従ってソートし、より大きな傾斜を有するものをアラインメントの判定に用いるようにプログラムされまたは構成された、請求項１１に記載の装置。
【請求項１７】
類似性距離を求めるために、シーケンスマッチングを用いるようにプログラムされまたは構成された、請求項１２に記載の装置。
【請求項１８】
類似性距離を求めるために、キーフレームのペアごとのマッチングを用いるようにプログラムされまたは構成された、請求項１２に記載の装置。
【請求項１９】
クエリ映像と目標映像を区間のリストに区分化し、各区間内の主要上昇部／下降部を選択するようにプログラムされまたは構成され、区間のサイズは映像の長さに基づいて適合されている、請求項１１に記載の装置。
【請求項２０】
クエリ映像が目標映像の複製物でないと判定されたときに、目標映像を保持する映像データベース内にクエリ映像を記憶するようにプログラムされまたは構成された、請求項１４に記載の装置。
【請求項２１】
クエリ映像のフレームおよび目標映像のフレームを複数のブロックに分割するステップと、
ブロックに対する平均明度値を計算するステップと、
ブロックに対する平均明度値の時間的変化から極小値および極大値を抽出するステップとを含み、抽出された極小値および極大値が主要極小値および主要極大値であり、更に、
主要極小値および主要極大値から主要上昇部および主要下降部を取得するステップと、
主要上昇部および主要下降部を用いてクエリ映像と目標映像の間にアラインメントが存在するかどうかを判定するステップと
を含む、映像コンテンツを管理する方法を実行するための機械実行可能なプログラムを記憶した非一時的なコンピュータ読み取り可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、映像を比較するための方法および装置に関する。
【背景技術】
【０００２】
たとえばＹｏｕＴｕｂｅ（登録商標）、Ｇｏｏｇｌｅ  Ｖｉｄｅｏ、およびＹａｈｏｏ！  Ｖｉｄｅｏなどの動画共有ウェブサイトでは、映像コンテンツはユーザによってサイトにアップロードされ、検索エンジンによって他者が利用できるようにすることができる。現在のウェブ映像検索エンジンは、ユーザによって入力された特定のテキストクエリに基づいて、それらの関連するスコアに従ってランク付けされた検索結果のリストを提供すると考えられる。ユーザは次いで、関心のある１つまたは複数の映像を見つけるために結果を検討しなければならない。
【０００３】
ユーザがホストに映像をアップロードし、映像を取得し、何らかの修正を行って再びそれらを分配するのは容易なので、映像検索結果には潜在的に非常に多くの複製物、またはほぼ複製物のコンテンツが存在する。このような複製物は、それらの全体的なコンテンツおよび主観的印象に基づいてユーザによって「本質的に同じ」であると見なされることになる。たとえば複製物映像コンテンツは、同一またはほぼ同一のコンテンツであるが異なるファイルフォーマットである、異なる符号化パラメータを有する、および／または長さが異なる、映像シーケンスを含み得る。他の差異としては、色および／もしくは照明の変更などの光度測定的な変動、ならびに／またはキャプション、ロゴおよび／もしくは縁取りの追加または改変などの空間および時間ドメインでの軽微な編集動作の場合がある。これらの例は網羅的なリストを意図するものではなく、複製物映像には他のタイプの差異も生じ得る。
【０００４】
複製物映像の急増により、ユーザが実際に欲しいコンテンツをユーザが見つけることが難しくまたは不便になり得る。例として、ＹｏｕＴｕｂｅ、Ｇｏｏｇｌｅ  Ｖｉｄｅｏ、Ｙａｈｏｏ！  Ｖｉｄｅｏからのサンプル的な照会に基づくと、検索結果にリストされた中で平均で２７％より多いほぼ複製物の映像が存在することが分かり、人気のある映像は結果内で最も複製されたものである。検索結果における高い比率の複製物映像を前提として、ユーザは検索結果をより分けてユーザが必要とする映像を見つけるのにかなりの時間をかけなければならず、すでに見た映像の類似のコピーを繰り返し視聴しなければならない。複製物の結果は、映像検索、取り出し、およびブラウジングのユーザの体験の価値を低下させる。さらにこのような複製された映像コンテンツは、ネットワークに全体にわたって複製された映像データを記憶し、伝送することによりネットワークオーバヘッドを増加させる。
【０００５】
映像コピーおよび類似性検出に対する研究は、異なる特性を識別し、それらにマッチングアルゴリズムを適用することに基づいている。一般に、映像コピー検出技法は、２つのカテゴリ、すなわち、ペアごとのキーフレーム比較手法とシーケンスマッチング手法とに分類される。
【０００６】
ペアごとのキーフレーム比較手法では、映像からキーフレームが抽出され、映像間の重複の程度を測定するためにキーフレーム間のペアごとの比較が実行される。キーフレームマッチング手法は通常は、映像を表すように、映像を一連のキーフレームに区分化する。各キーフレームは次いで領域に分割され、目立った局所領域から特性が抽出される。特性はたとえば、各領域に対する色、テクスチャ、角部、または形状特性とすることができる。キーフレームマッチングは、フレームの時間的順序における変更または挿入／削除など、かなりの程度の編集を受けた近似するコピーを検出することができる。しかし、キーフレーム内には全く多くの局所的特性があるので、キーフレームを識別し、各キーフレームから局所的特性を抽出し、映像クリップをデータベース内の大量の映像とマッチングさせるためにそれらの間の計量距離（ｍｅｔｒｉｃ  ｄｉｓｔａｎｃｅ）の比較を行うのは計算法的に費用がかかる。
【０００７】
最近の研究は、特性ベクトルの高速指標付けにより、または統計情報を用いて特性ベクトルの次元を低くすることにより、キーフレームマッチング方法の速度を改善することに向けられている。しかしオンライン分析の場合は、映像をキーフレームに区分化するコスト、およびクエリ映像から局所的特性を抽出するコストの両方は依然として避けられない。Ｗｅｂ２．０映像共有環境におけるオンラインリアルタイム映像複製検出を実現することが現実の課題となる。キーフレームマッチング手法は、データベース映像を集約し分類するためのきめの細かい分析を用いたオフライン映像冗長性検出に、より適している。
【０００８】
シーケンスマッチングでは、複数のフレームを有するある時間間隔が、クエリ映像と目標映像の類似性を比較する基準となる。通常、これは、クエリ映像フレームおよび目標映像フレームの両方から特性のシーケンスを抽出するものであり、これはたとえば順序、動き、色、および図心をベースとする特性とすることができる。抽出された特性シーケンスは次いで、映像間の類似性距離を求めるために比較される。たとえば順序識別特性が用いられる場合は、各映像フレームは最初にＮ１×Ｎ２ブロックに分割され、各ブロックの平均の明度が計算される。次いで各フレームに対して、ブロックがそれらの平均の明度に従ってランク付けされる。ランキング順位はそのフレームの順序尺度と見なされる。一方の映像に対する順序尺度のシーケンスは、他方のそれと比較されて両者の類似性が評価される。
【０００９】
シーケンスマッチングは、複製物映像間での重複位置の始まりを確定することを可能にする。シーケンスマッチング手法は、ほとんど同一な映像、ならびにコーディングおよびフレーム分解能変更などのフォーマット変更を有する映像のコピー、および空間および時間ドメインでの軽微な編集を有するものを識別するのに適している。具体的には、空間的および時間的な順序識別特性を用いることにより、映像デジタル化／符号化プロセス（たとえば色、輝度、およびヒストグラム等化、符号化パラメータにおける変化）、および表示フォーマット変換（たとえばレターボックスまたはピラーボックスへの変換）、および部分的コンテンツの変更（たとえばクロッピングおよびズームイン）によって導入された映像歪みの検出が可能になる。
【００１０】
キーフレームマッチング手法とは異なりシーケンスマッチング手法は、必要な計算が比較的容易であり、特に順序尺度を用いたときにフレームのコンパクトな表示をもたらす。シーケンスマッチングは計算の効率が良い傾向があり、ライブ映像を処理するためにリアルタイムの計算を実行することができる。たとえば１つのフレームの２×２分割を用いた順序尺度は、各フレームを表すのに４次元しか必要とせず、２つのフレーム間の必要な比較点がより少ない。しかし動画共有ウェブサイトにおける映像複製物検出は、映像クリップを大量のデータベース映像と比較する必要があり、通常、これはリアルタイムで実行されなければならない。映像の順序識別特性の順次比較は、時間のかかるプロセスである。「順次走査」の時間的複雑さを示すために、より短いクエリ映像クリップＣをより長い目標映像シーケンスＴに対して「スライド」させ、各点にて類似性距離を計算することを考える。順次走査は、Ｑ（（ｍ−ｎ＋１）×ｎ）の時間的複雑さを有し、ただし、ｍはＴ内のデータ点の数、およびｎはＣ内のデータ点の数である。たとえば持続時間が５分で３０フレーム／秒のクエリ映像を、合計１０個の映像からなる１組の目標映像と比較することを考え、目標映像のそれぞれは３０フレーム／秒にて１０分の持続時間を有するものとする。２×２分割を有する空間的な順序尺度を用いると仮定すると、順次走査は約２４６億回の演算を必要とする。Ｗｅｂ２．０環境においてユーザクエリに対するタイムリーな応答をもたらすように、映像複製検出プロセスの速度は改善されなければならない。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Ｆｉｎｋ、Ｐｒａｔｔ、およびＧａｎｄｈｉ、「Ｉｎｄｅｘｉｎｇ  ｏｆ  Ｔｉｍｅ  Ｓｅｒｉｅｓ  ｂｙ  Ｍａｊｏｒ  Ｍｉｎｉｍａ  ａｎｄ  Ｍａｘｉｍａ」、２００３年、ＩＥＥＥ
【発明の概要】
【課題を解決するための手段】
【００１２】
本発明の第１の態様によれば、クエリ映像と目標映像を比較する方法では、クエリ映像のフレームおよび目標映像のフレームは、複数のブロックに分割される。各ブロックに対して平均明度値が計算される。各ブロックに対する平均明度値の時間的変化から極小値および極大値が抽出される。極小値および極大値から上昇部および下降部が取得される。上昇部および下降部は、クエリ映像と目標映像の間にアラインメントが存在するかどうかを判定するのに用いられる。
【００１３】
本発明による方法は、２つの映像間の比較空間を低減することによって効率的な映像複製検出をもたらす。
【００１４】
一実施形態では、クエリ映像と目標映像の間の類似性距離が計算される。一実施形態では、アラインメントが存在すると分かったときにのみ、クエリ映像と目標映像の間の類似性距離の計算が実行される。一実施形態では、最良類似性距離が計算され、クエリ映像および目標映像が複製物であるかどうかを判定するために所与の閾値と比較される。
【００１５】
これは特に、映像検索結果を改善するために映像データストア内の映像の類似性に関する情報を保持することは有用であるが、たとえばアーカイブされたコンテンツを体系化するなど他の目的のためにも有利となり得る。映像複製物および類似性検出は、検索、トピック追跡、および著作権保護におけるその潜在力のために有用である。
【００１６】
本発明による方法は、所与の映像がデータストアに追加されるときに適用することができる。しかしこれは、たとえば、データストアによって保持された映像コンテンツの類似性に関する情報を精緻化するために、前にデータストアに追加された映像コンテンツを管理するために用いることができる。
【００１７】
一実施形態では、データストア内に含まれる映像ファイルのいずれも所与の映像ファイルとして取り出すことができ、データストア内の類似した映像ファイルを検出するためのクエリとして働く。
【００１８】
一実施形態では、いくつかの重要な極大および極小を用いて映像シーケンスを圧縮し、それらの極値点に基づいて主要上昇部／下降部を取得し、次いでそれらの主要上昇部／下降部に従ってクエリ映像を目標映像にアラインメントさせることによって潜在的な映像マッチング位置を検出するために、時系列マッチング技法が用いられる。潜在的アラインメント位置に基づいて、既存の映像複製物検出技法（たとえばシーケンスマッチング手法、またはペアごとのキーフレーム比較手法）を、映像類似性距離を計算するために適用することができる。最良マッチング類似性距離が閾値より小さい場合は、２つの映像は複製物と見なされる。
【００１９】
映像間の少数の潜在的マッチング位置を提示するために主要極値点をアラインメントさせることにより、本発明による方法は、２つのやり方で映像検出計算コストを低減することができる。第１には映像冗長性検出技法を適用する前に非常に異なる映像を除去することによるものであり、第２には類似した映像に対する多くの不要な比較を省くことによるものである。２つの映像間の少数の潜在的アラインメント位置を前提として、シーケンスマッチング手法（たとえば順序識別特性）は、最良マッチング位置を検出するために１つの映像を別の映像の全体にわたって走査する必要はなく、ペアごとのキーフレーム比較手法の場合は、比較するキーフレームの総数は、アラインメントされた位置の範囲内に限定されることになる。したがって提案される本発明は、両方のタイプの映像複製物検出手法とともに、それらの計算コストを低減するために用いることができる。
【００２０】
本発明の一実施形態は、動画共有ウェブサイトにおいてユーザフィーチャーを提供するために用いることができ、または映像コンテンツプロバイダによってロイヤルティ支払いを追跡し、および可能性のある著作権侵害を検出するために用いることができ、あるいはコンテンツ配給ネットワークによってネットワークトラフィックを低減し映像コンテンツの保管を管理するために用いることができる。本発明は、既存の映像複製システムに、それらの処理時間を改善するために採用することができる。これは特に、映像検索結果を改善するためにデータストア内の映像ファイルの類似性に関する情報を保持するために有用であるが、たとえばアーカイブされたコンテンツを体系化するなど他の目的のためにも有利となり得る。映像複製物および類似性検出は、検索、トピック追跡、および著作権保護におけるその潜在力のために有用である。
【００２１】
本発明の第２の態様によれば、装置は第１の態様による方法を実行するようにプログラムされまたは構成される。
【００２２】
本発明の第３の態様によれば、第１の態様による方法を実行するための機械実行可能なプログラムを記憶したデータ記憶媒体が提供される。
【００２３】
次に本発明のいくつかの実施形態について、実施例のみとして添付の図面を参照して説明する。
【図面の簡単な説明】
【００２４】
【図１】本発明による方法を概略的に示す図である。
【図２】目標映像に対する明度における時間的変化を概略的に示すグラフである。
【図３】クエリ映像に対する明度における時間的変化を概略的に示すグラフである。
【図４】図１の方法を実施するための装置を概略的に示す図である。
【発明を実施するための形態】
【００２５】
図１を参照すると、複製物映像検出手順に関わる映像は、複数のフレームを備える。ステップ１では、映像内の各フレームはＮ１×Ｎ２ブロックに分割される。ステップ２では、ブロックのそれぞれに対する平均明度値が計算される。ヒストグラム等化などの映像修正技法は、フレーム全体に対する明度の平均値を、グレイスケールの中間値に調整することができる。このような場合では映像全体の時間的変化は平坦化され、その場合は極値点をベースとするデータ圧縮には適さない。分割されたブロックからの時間的明度変化を用いることにより、ブロックのそれぞれは分割された部分領域における明度変化の変動を保持できるのでこの問題は回避される。
【００２６】
ステップ３では、各ブロックに対する平均明度値の時間的変化から、重要な極小値および極大値が抽出される。ステップ４では、抽出された極小値および極大値から、主要上昇部／下降部が取得される。
【００２７】
重要な極小値および極大値を選択するプロセスは、映像明度の時間的変化を表す本質的な情報の大部分を捕捉するためのある種のデータ圧縮と考えることができる。この目的は、主要極小および極大のみを保持し、他の点を取り除くことによって、軽微な増減を切り捨てることである。ユーザ修正、映像歪み、およびフォーマット変換により、一般には映像複製物検出において完全な一致はない。時間的明度の軽微な変化を無視することにより、映像検出アルゴリズムは比較的ノイズの影響を受けにくくなる。
【００２８】
主要極値点を抽出するのに適した１つの技法は、引用により本明細書に組み込まれる、Ｆｉｎｋ、Ｐｒａｔｔ、およびＧａｎｄｈｉ「Ｉｎｄｅｘｉｎｇ  ｏｆ  Ｔｉｍｅ  Ｓｅｒｉｅｓ  ｂｙ  Ｍａｊｏｒ  Ｍｉｎｉｍａ  ａｎｄ  Ｍａｘｉｍａ」、２００３年、ＩＥＥＥによって提案されたものである。
【００２９】
この技法では圧縮率はパラメータＲによって制御され、これは常に１より大きい。重要な極小の定義は以下に示される：数列ａ１，…，ａｎのうちのａｍの点は、ｉ≦ｍ≦ｊであり、ａｍがａｉ，…，ａｊの中で最小であり、ａｉ／ａｍ＞Ｒ、およびａｊ／ａｍ＞Ｒである添え字ｉおよびｊが存在する場合は極小である。同様にａｍは、ｉ≦ｍ≦ｊであり、ａｍがａｉ，…，ａｊの中で最大であり、ａｍ／ａｉ＞Ｒ、およびａｍ／ａｊ＞Ｒである添え字ｉおよびｊが存在する場合は重要な極大である。Ｒを増加させると選択される点がより少なくなる。
【００３０】
この技法は、線形的な時間と、一定のメモリとを必要とする。これを適用することによって、すべての重要な点の値および添え字を取得することができる。またこれは、もとの数列を記憶せずに、新しい点が到着するのに従ってそれらを処理することを可能にする。これはユーザが映像をウェブサイトにアップロードする時間の間に、主要極値を抽出することによってクエリ映像をオンライン処理するために用いることができる。他の実施形態では、他の技法を主要極値点を抽出するために用いることができる。
【００３１】
ステップ１から４は、複製検出手順に関わる映像のそれぞれに対して実行される。
【００３２】
ステップ５では、分割されたブロックからの主要上昇部／下降部の位置を用いて、クエリ映像Ｑを目標映像Ｔとアラインメントさせる試みがなされる。
【００３３】
映像のそれぞれはＮ１×Ｎ２の時系列を含んでおり、それらの時系列のそれぞれは主要上昇部／下降部のリストを有するので、映像シーケンス内には非常に多くの主要上昇部／下降部がある。少な過ぎる主要上昇部／下降部を一致させようと試みると、潜在的アラインメント位置の数が減少することになり、結果として一致する位置の漏れを生じ得る。これはユーザ編集（たとえば挿入、削除、または置換）の場合に、選択された主要上昇部／下降部が複製物映像間の重複するフレームの外側となり得る場合に起こり得る。一方、多過ぎる点のマッチングは、多くの潜在的アラインメント位置を生じることになり、これは次の段階で類似性距離を計算するのに必要な時間を増加させることになる。さらに、主要上昇部／下降部は映像内の残りの上昇部／下降部と比較した相対的な情報であるので、比較される映像の長さが大きく異なるときは（たとえば２時間に比べて３０秒）、短い方の映像に対する主要上昇部／下降部は、長い方の映像内では主要でない上昇部／下降部と見なされ得る。
【００３４】
有効性と効率とのバランスをもたらすように、映像を区間のリストに区分化し、各区間内の主要上昇部／下降部を選択するために、適応型の区間が用いられる。区間の長さは、比較される映像の短い方の長さに基づいて適合されている。比較される映像の１つが短いときは、区間の長さは短くなる。そうでなければ区間の長さは長くなる。この技法は、主要上昇部／下降部が、映像の長さ全体にわたって一様に分布することを確実にする。これは長い方の映像内に、短い映像に対する潜在的な重複するフレームを表す、主要上昇部／下降部が存在することを確実にする。
【００３５】
いくつかのブロックは、平均明度値において大きな変動を含み、他のブロックは明度値において比較的軽微な増減を有し得るので、ブロック内に保持される情報量を表すために、主要上昇部／下降部における傾斜の変動を用いることができる。この実施形態ではステップ６で、クエリ映像Ｑ内のすべての分割ブロックの全体にわたって主要上昇部／下降部が、それらの傾斜に従ってソートされる。ステップ７ではソートされたリストから最も深みのある傾斜変化を有する主要上昇部／下降部のいくつかが選択されて、ステップ８で実行されるアラインメントプロセス時にクエリ映像Ｑを表すものとなる。
【００３６】
アラインメントプロセス時には、クエリ映像Ｑの選択された主要上昇部／下降部の間の相対位置と、それらの相対的な傾斜変化との両方が、目標映像Ｔにおけるそれらに対するマッチングのときに基準として用いられる。比較される映像ＱとＴの間にアラインメントが存在しない場合はそれらは複製物ではないと見なされ、マッチング処理は９で終了される。比較される映像ＱとＴのアラインメントが存在することが分かった場合は複製マッチング処理は継続する。
【００３７】
次にステップ１０では、アラインメント位置のそれぞれに対して、クエリ映像Ｑと目標映像Ｔの間の類似性距離が計算される。類似性距離を計算するために、シーケンスマッチング手法またはペアごとのキーフレーム比較などの既存の映像複製物検出技法を適用することができる。ステップ１１では、クエリ映像Ｑと目標映像Ｔの間の最良類似性距離が求められる。最良類似性距離は次いでステップ１２で、予め規定された閾値と比較される。最良類似性距離が予め規定された閾値より小さい場合は、比較された映像は複製物であると見なされる。
【００３８】
図２ａは目標映像クリップを表し、図２ｂは縁取りが追加されていることを除いて図２ａのものと類似のクエリ映像である。各映像に対して、各フレームは４×４ブロックに分割されている。図２ｃは、目標映像の場合のブロックのそれぞれに対する明度の変化のグラフを示す。図２ｄは、クエリ映像の場合の明度の時間的変化を示す。クエリ映像の場合の明度の時間的変化は、同様なトレースに従うことが分かる。それらは、等しい時間間隔で測定された値のシーケンスを含んだ１組の時系列と見ることができる。
【００３９】
輝度、色、色相の変更、ヒストグラム等化、モザイクの追加、ガウス雑音、ガンマ補正、フレームのサイズ変更またはクロッピングなどの、様々なタイプの歪み、修正およびフォーマット変換を有する１組の複製物映像を用いた実験時において、本発明による方法は良好な性能をもたらすことが見出された。映像複製検出時間は、これまでに知られている手法より約１０倍まで速いことが見出された。さらに、これまでに知られている映像複製検出技法によって得られるものと同レベルの精度が保たれた。
【００４０】
図４を参照すると映像管理装置は、映像ファイルを保持するデータベースまたは記憶装置１３を含む。データベース１３は、インターネットを通じて一般にユーザがアクセス可能なもの、またはたとえばアクセスが制限されたライブラリまたは他の保管場所とすることができる。これらの可能なものの代わりにまたはそれらに加えて、他のタイプの記憶装置またはデータベースを用いることができる。
【００４１】
ユーザは、ユーザインターフェース１４を通じて映像Ｑを提出することによって、ユーザがデータベース１３に追加したい映像Ｑを送信する。映像Ｑは、映像データベース１３およびまた分割器１５に送られる。
【００４２】
動作の段階１では、分割器１５は映像Ｑの各フレームをＮ１×Ｎ２ブロックに分割し、ブロックのそれぞれに対して平均明度値を計算する。
【００４３】
段階２では平均明度値データが分割器１５からプロセッサ１６によって受け取られる。プロセッサ１６は、各ブロックに対する平均明度値の時間的変化から重要な極小値および極大値を抽出する。プロセッサ１６は次いで、重要な極小値および極大値を用いて主要上昇部／下降部を取得する。
【００４４】
段階３は、提出された映像Ｑと、データベース１３に保持された他の映像との間の可能性のあるアラインメントを検出することを目的とするアラインメント動作である。アライナ１７は、データベース１３に記憶された１つまたは複数の目標映像Ｔに対して同様なやり方によって取得された主要上昇部／下降部と比較するために、プロセッサ１６から主要上昇部／下降部を受け取る。（１つまたは複数の）目標映像Ｔはクエリ映像Ｑと事実上同時に分析することができ、（１つまたは複数の）映像Ｔはクエリ映像Ｑとほぼ並列に分割器１５に加えられ、それにより必要なデータはデータベース１３に記憶された（１つまたは複数の）映像から抽出されていて、アライナ１７によるクエリ映像Ｑとのアラインメントが存在するかどうかの判定のために利用可能となる。
【００４５】
クエリ映像Ｑといずれの目標映像Ｔとの間にもアラインメントが検出されなかった場合は、その旨のメッセージがライン１８上を映像データベース１３に送られ、クエリ映像Ｑは、記憶するためにデータベース１３によってユーザインターフェース１４から受け入れられる。
【００４６】
アラインメントが検出されたときは段階４において、クエリ映像Ｑと１つまたは複数の目標映像Ｔとの間のアラインメント位置のそれぞれに対して、クエリ映像Ｑと１つまたは複数の目標映像Ｔとの間の類似性距離が計算器１９にて計算される。計算器１９は、それらの中から最良類似性距離を見出す。類似性距離が予め規定された閾値より小さい場合は、比較された映像は複製物であると見なされる。クエリ映像が複製物であると見なされるべきかどうかについて通知するために、メッセージがライン２０上を映像データベース１３に送られる。
【００４７】
クエリ映像Ｑが複製物ではないことが分かった場合は、映像データベース１３はそれを記憶のために受け入れる。
【００４８】
クエリ映像Ｑが複製物であることが分かった場合は、次いで一実施形態では映像データベース１３は、ユーザにそれを通知するためのメッセージを伴ってまたは伴わずに、クエリ映像を拒絶する。
【００４９】
代替実施形態または代替形態では、クエリ映像Ｑが複製物であることが分かった場合は、映像データベース１３に受け入れられるが、好ましくはそれが一致した目標映像Ｔへの参照を有して、複製物として表示される。複製物映像はグループに一緒に集めることができる。データベース上で行われる検索がグループの１つを呼び出したときは、他のグループ要素は検索結果から削除することができ、またはいずれの複製物も他の非複製物の後に提示される傾向をもつように、検索結果においてそうでない場合に受け得るよりも低いランキングが与えられる。
【００５０】
図４の映像管理装置は、クエリ映像Ｑが提出される前に、映像データベース１３内に保持された映像が１５および１６にて分割され処理されるように変更することができる。たとえば一実施形態では、複製物について調べるように映像が提出されたときに得られたデータは保持され、ライン２１を通じて映像データベース１３に送って記憶することができる。その映像がその後にデータベース１３に受け入れられなかった場合は、そのデータは削除される。映像がデータベースに受け入れられたときは、それに関連付けられたデータは保持され、ライン２２を通じてアライナ１９での使用に利用可能となる。別の実施形態では映像データベース１３内の映像は、必ずしも複製物のテストに用いられていなくても、１５および１６にて分割および処理することができる。たとえばデータ処理は、新しい映像を受け取るためにデータベースを開放する前の準備段階の一部として実行することができる。
【００５１】
「プロセッサ」として名前が付けられたいずれの機能ブロックを含む、図に示された様々な要素の機能は、専用のハードウェア、ならびに適当なソフトウェアに関連してソフトウェアを実行することができるハードウェアを用いることによって実現することができる。プロセッサによって実現されるとき、これらの機能は、単一の専用プロセッサ、単一の共有されたプロセッサ、その一部を共有することができる複数の個別のプロセッサによって実現することができる。さらに「プロセッサ」という用語の明示的な使用は、ソフトウェアを実行することができるハードウェアを排他的に指すと解釈されるべきではなく、非限定的に、デジタル信号プロセッサ（ＤＳＰ）ハードウェア、ネットワークプロセッサ、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、ソフトウェアを記憶するためのリードオンリメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、および不揮発性記憶装置を暗黙に含むことができる。従来型および／またはカスタムの他のハードウェアも含むことができる。
【００５２】
本発明は、その趣旨または本質的な特徴から逸脱せずに、他の特定の形で実施することができる。説明した実施形態は、すべての点で例示に過ぎず、限定的と見なされるべきではない。したがって本発明の範囲は上記の説明によってではなく、添付の特許請求の範囲によって示される。特許請求の範囲と均等な意味および範囲内に含まれるすべての変更形態は、それらの範囲に包含されるものとする。
【図１】
0005711387.tif 000002
【図２Ａ】
0005711387.tif 000003
【図２Ｂ】
0005711387.tif 000004
【図２Ｃ】
0005711387.tif 000005
【図２Ｄ】
0005711387.tif 000006
【図３】
0005711387.tif 000007