"データベースに格納されているリファレンス映像から、クエリ映像を検索する映像検索装置であって、前記リファレンス映像およびクエリ映像を一定時間長のセグメントに分割し、前記各セグメントから予め定められた数のフレームを選択する映像分割部と、前記選択されたフレームから映像の特徴を示す特徴量を抽出する特徴量抽出部と、前記抽出した特徴量を1つ以上の量子化識別子に変換する特徴量量子化部と、前記リファレンス映像のセグメント情報と対応する量子化識別子の集合に基づいて、転置インデックスを構成するリストに前記セグメントの映像識別子と時刻情報を格納する特徴量蓄積部と、前記クエリ映像のセグメント情報と対応する量子化識別子の集合に基づいて、前記転置インデックスを参照し、投票により、前記クエリ映像の全部または一部を含むリファレンス映像の映像識別子および時刻情報を特定する転置インデックス検索部と、を備えることを特徴とする映像検索装置。前記特徴量抽出部は、前記選択された各フレームについて、予め定義された1つ以上の領域毎に特徴量を抽出し、前記特徴量量子化部は、前記領域毎に抽出された特徴量を量子化識別子に変換し、前記特徴量蓄積部は、前記領域毎の量子化識別子に基づいて、前記各領域に対応する転置インデックスを構成するリストに前記領域の映像識別子と時刻情報を格納することを特徴とする請求項1記載の映像検索装置。前記特徴量量子化部は、ベクトル量子化を行なうためのコードブックを有し、特徴量に対して最近傍となる代表ベクトルにベクトル量子化をすることによって、特徴量を量子化識別子に変換することを特徴とする請求項1または請求項2記載の映像検索装置。前記特徴量量子化部は、前記最近傍から近い順にkkは自然数個の代表ベクトルにベクトル量子化をすることによって、特徴量を量子化識別子に変換することを特徴とする請求項3記載の映像検索装置。前記特徴量量子化部は、特徴量と予め定義された基底との内積の値を規定の閾値で離散化することによって、特徴量を量子化識別子に変換することを特徴とする請求項1または請求項2記載の映像検索装置。前記特徴量量子化部は、前記内積を離散化する際に、1つ以上の値に離散化することによって、特徴量を量子化識別子に変換することを特徴とする請求項5記載の映像検索装置。前記転置インデックス検索部は、前記クエリ映像の各セグメントの量子化識別子に対応する転置インデックスを参照し、前記転置インデックスに登録されているリファレンス映像の映像識別子、およびリファレンス映像のセグメントの時刻情報と前記クエリ映像のセグメントの時刻情報とのオフセット値に投票を行ない、得票数が一定値以上かつ一定の範囲内で極大となるリファレンス映像の映像識別子およびオフセット値を検出候補とすることを特徴とする請求項1記載の映像検索装置。前記クエリ映像の各セグメントに割り当てられている量子化識別子idそれぞれについて、前記転置インデックスに登録されているリファレンス映像の映像識別子をvとし、リファレンス映像のセグメントの時刻情報をt’とし、クエリ映像のセグメントの時刻情報をtとしたときに、前記転置インデックス検索部は、投票時に前記t,idの情報を、前記vおよびオフセット値t’-t毎に記録し、前記検出候補それぞれについて、t,idのリストを参照し、隣り合うリストの要素のtが一定以上離れている箇所でリストを分割し、前記分割したリストそれぞれに対応するスコアを算出し、前記算出したスコアを前記リスト内の最大のtから最小のtを減算した値を用いて正規化し、前記正規化した値を検出結果とすることを特徴とする請求項7記載の映像検索装置。前記転置インデックス検索部は、前記t,idのリストのスコアを、リスト内の要素の個数とすることを特徴とする請求項8記載の映像検索装置。前記転置インデックス検索部は、前記t,idのリストのスコアを、リスト内の要素のうち、前記idに関連付けられた重要度の和とし、前記重要度は、転置インデックスに蓄積されているセグメント数を、転置インデックスのid番目のリストのサイズで除算したものの対数とすることを特徴とする請求項8記載の映像検索装置。前記転置インデックス検索部は、隣接するtについて同じidが出現した際には、スコアを一度しか加算しないことを特徴とする請求項10記載の映像検索装置。データベースに格納されているリファレンス映像から、クエリ映像を検索するプログラムであって、前記リファレンス映像およびクエリ映像を一定時間長のセグメントに分割し、前記各セグメントから予め定められた数のフレームを選択する処理と、前記選択されたフレームから映像の特徴を示す特徴量を抽出する処理と、前記抽出した特徴量を1つ以上の量子化識別子に変換する処理と、前記リファレンス映像のセグメント情報と対応する量子化識別子の集合に基づいて、転置インデックスを構成するリストに前記セグメントの映像識別子と時刻情報を格納する処理と、前記クエリ映像のセグメント情報と対応する量子化識別子の集合に基づいて、前記転置インデックスを参照し、投票により、前記クエリ映像の全部または一部を含むリファレンス映像の映像識別子および時刻情報を特定する処理と、の一連の処理を、コンピュータに実行させることを特徴とするプログラム。前記選択された各フレームについて、予め定義された1つ以上の領域毎に特徴量を抽出する処理と、前記領域毎に抽出された特徴量を量子化識別子に変換する処理と、前記領域毎の量子化識別子に基づいて、前記各領域に対応する転置インデックスを構成するリストに前記領域の映像識別子と時刻情報を格納する処理と、をさらに含むことを特徴とする請求項12記載のプログラム。しかしながら、特許文献1および2で開示されている手法では、動画コンテンツ1つから1つの特徴量を抽出するため、例えば、動画コンテンツを2つに分割する等の時間軸方向の編集が行なわれると検出ができなくなるという問題がある。非特許文献1で開示されている手法では、画面全体から1つの特徴量のみを抽出しているため、テロップやロゴを挿入するような空間的編集が行なわれると検出ができなくなる問題がある。また、非特許文献2で開示されている手法では、1画面から数十個の特徴点を抽出し、それら全てをマッチングさせているため、特徴点の抽出およびマッチングに時間がかかりすぎるという問題がある。本発明は、このような事情に鑑みてなされたものであり、リファレンス映像の時間軸上の一部分を切り出したり、リファレンス映像にテロップやロゴが挿入されたりした映像を含むクエリ映像であっても、そのクエリ映像の検索を可能とし、その処理を高速に行なうことができる映像検索装置およびプログラムを提供することを目的とする。1上記の目的を達成するために、本発明は、以下のような手段を講じた。すなわち、本発明の映像検索装置は、データベースに格納されているリファレンス映像から、クエリ映像を検索する映像検索装置であって、前記リファレンス映像およびクエリ映像を一定時間長のセグメントに分割し、前記各セグメントから予め定められた数のフレームを選択する映像分割部と、前記選択されたフレームから映像の特徴を示す特徴量を抽出する特徴量抽出部と、前記抽出した特徴量を1つ以上の量子化識別子に変換する特徴量量子化部と、前記リファレンス映像のセグメント情報と対応する量子化識別子の集合に基づいて、転置インデックスを構成するリストに前記セグメントの映像識別子と時刻情報を格納する特徴量蓄積部と、前記クエリ映像のセグメント情報と対応する量子化識別子の集合に基づいて、前記転置インデックスを参照し、投票により、前記クエリ映像の全部または一部を含むリファレンス映像の映像識別子および時刻情報を特定する転置インデックス検索部と、を備えることを特徴とする。このように、リファレンス映像およびクエリ映像を一定時間長のセグメントに分割し、各セグメントから予め定められた数のフレームを選択し、選択されたフレームから映像の特徴を示す特徴量を抽出し、抽出した特徴量を1つ以上の量子化識別子に変換し、リファレンス映像のセグメント情報と対応する量子化識別子の集合に基づいて、転置インデックスを構成するリストにセグメントの映像識別子と時刻情報を格納し、クエリ映像のセグメント情報と対応する量子化識別子の集合に基づいて、転置インデックスを参照し、投票により、クエリ映像の全部または一部を含むリファレンス映像の映像識別子および時刻情報を特定するので、クエリ映像の全部または一部が、リファレンス映像の時間軸上の一部分を切り出したり、リファレンス映像にテロップやロゴが挿入されたりしたものであっても、クエリ映像の検索が可能となり、検索時間を短縮し、検索の精度を高めることが可能となる。2また、本発明の映像検索装置において、前記特徴量抽出部は、前記選択された各フレームについて、予め定義された1つ以上の領域毎に特徴量を抽出し、前記特徴量量子化部は、前記領域毎に抽出された特徴量を量子化識別子に変換し、前記特徴量蓄積部は、前記領域毎の量子化識別子に基づいて、前記各領域に対応する転置インデックスを構成するリストに前記領域の映像識別子と時刻情報を格納することを特徴とする。このように、前記選択された各フレームについて、予め定義された1つ以上の領域毎に特徴量を抽出し、前記特徴量量子化部は、前記領域毎に抽出された特徴量を量子化識別子に変換し、前記特徴量蓄積部は、前記領域毎の量子化識別子に基づいて、前記各領域に対応する転置インデックスを構成するリストに前記領域の映像識別子と時刻情報を格納するので、一つのフレームから複数の特徴量を抽出することが可能となり、検索精度を向上させることが可能となる。3また、本発明の映像検索装置において、前記特徴量量子化部は、ベクトル量子化を行なうためのコードブックを有し、特徴量に対して最近傍となる代表ベクトルにベクトル量子化をすることによって、特徴量を量子化識別子に変換することを特徴とする。このように、ベクトル量子化を行なうためのコードブックを有し、特徴量に対して最近傍となる代表ベクトルにベクトル量子化をすることによって、特徴量を量子化識別子に変換し、量子化識別子に基づいてマッチングを行なうので、検索時間を短縮することが可能となる。4また、本発明の映像検索装置において、前記特徴量量子化部は、前記最近傍から近い順にkkは自然数個の代表ベクトルにベクトル量子化をすることによって、特徴量を量子化識別子に変換することを特徴とする。このように、前記最近傍から近い順にkkは自然数個の代表ベクトルにベクトル量子化をすることによって、類似した特徴量同士が同一の量子化識別子を共有する確率を向上させ、検索の精度を高めることが可能となる。5また、本発明の映像検索装置において、前記特徴量量子化部は、特徴量と予め定義された基底との内積の値を規定の閾値で離散化することによって、特徴量を量子化識別子に変換することを特徴とする。このように、特徴量と予め定義された基底との内積の値を規定の閾値で離散化することによって、特徴量を量子化識別子に変換し、量子化識別子に基づいてマッチングを行なうので、検索時間を短縮することが可能となる。6また、本発明の映像検索装置において、前記特徴量量子化部は、前記内積を離散化する際に、1つ以上の値に離散化することによって、特徴量を量子化識別子に変換することを特徴とする。このように、前記内積を離散化する際に、1つ以上の値に離散化することによって、類似した特徴量同士が同一の量子化識別子を共有する確率を向上させ、検索時間を短縮し、検索の精度を高めることが可能となる。7また、本発明の映像検索装置において、前記転置インデックス検索部は、前記クエリ映像の各セグメントの量子化識別子に対応する転置インデックスを参照し、前記転置インデックスに登録されているリファレンス映像の映像識別子、およびリファレンス映像のセグメントの時刻情報と前記クエリ映像のセグメントの時刻情報とのオフセット値に投票を行ない、得票数が一定値以上かつ一定の範囲内で極大となるリファレンス映像の映像識別子およびオフセット値を検出候補とすることを特徴とする。このように、前記クエリ映像の各セグメントの量子化識別子に対応する転置インデックスを参照し、前記転置インデックスに登録されているリファレンス映像の映像識別子、およびリファレンス映像のセグメントの時刻情報と前記クエリ映像のセグメントの時刻情報とのオフセット値に投票を行ない、得票数が一定値以上かつ一定の範囲内で極大となるリファレンス映像の映像識別子およびオフセット値を検出候補とするので、検索時間を短縮することが可能となる。8また、本発明の映像検索装置において、前記クエリ映像の各セグメントに割り当てられている量子化識別子idそれぞれについて、前記転置インデックスに登録されているリファレンス映像の映像識別子をvとし、リファレンス映像のセグメントの時刻情報をt’とし、クエリ映像のセグメントの時刻情報をtとしたときに、前記転置インデックス検索部は、投票時に前記t,idの情報を、前記vおよびオフセット値t’-t毎に記録し、前記検出候補それぞれについて、t,idのリストを参照し、隣り合うリストの要素のtが一定以上離れている箇所でリストを分割し、前記分割したリストそれぞれに対応するスコアを算出し、前記算出したスコアを前記リスト内の最大のtから最小のtを減算した値を用いて正規化し、前記正規化した値を検出結果とすることを特徴とする。このように、投票時にt,idの情報を、vおよびオフセット値t’-t毎に記録し、検出候補それぞれについて、t,idのリストを参照し、隣り合うリストの要素のtが一定以上離れている箇所でリストを分割し、分割したリストそれぞれに対応するスコアを算出し、算出したスコアをリスト内の最大のtから最小のtを減算した値を用いて正規化し、正規化した値を検出結果とするので、検索の精度を高めることが可能となる。9また、本発明の映像検索装置において、前記転置インデックス検索部は、前記t,idのリストのスコアを、リスト内の要素の個数とすることを特徴とする。10また、本発明の映像検索装置において、前記転置インデックス検索部は、前記t,idのリストのスコアを、リスト内の要素のうち、前記idに関連付けられた重要度の和とし、前記重要度は、転置インデックスに蓄積されているセグメント数を、転置インデックスのid番目のリストのサイズで除算したものの対数とすることを特徴とする。このように、t,idのリストのスコアを、リスト内の要素のうち、idに関連付けられた重要度の和とし、重要度は、転置インデックスに蓄積されているセグメント数を、転置インデックスのid番目のリストのサイズで除算したものの対数とするので、多くのセグメントに出現する量子化識別子の重要度が小さくなり、特定のセグメントに固有の量子化識別子の重要度が大きくなり、検索の精度を高めることが可能となる。11また、本発明の映像検索装置において、前記転置インデックス検索部は、隣接するtについて同じidが出現した際には、スコアを一度しか加算しないことを特徴とする。このように、部分リストのスコアを計算する際に、隣接するtについて同じr,idが出現した際には、スコアを一度しか加算しないようにすることで、特に動きの少ない領域において、偶然無関係な特徴の量子化識別子が連続して一致してしまうことによる誤検出を削減し、検索の精度を高めることが可能となる。12また、本発明のプログラムは、データベースに格納されているリファレンス映像から、クエリ映像を検索するプログラムであって、前記リファレンス映像およびクエリ映像を一定時間長のセグメントに分割し、前記各セグメントから予め定められた数のフレームを選択する処理と、前記選択されたフレームから映像の特徴を示す特徴量を抽出する処理と、前記抽出した特徴量を1つ以上の量子化識別子に変換する処理と、前記リファレンス映像のセグメント情報と対応する量子化識別子の集合に基づいて、転置インデックスを構成するリストに前記セグメントの映像識別子と時刻情報を格納する処理と、前記クエリ映像のセグメント情報と対応する量子化識別子の集合に基づいて、前記転置インデックスを参照し、投票により、前記クエリ映像の全部または一部を含むリファレンス映像の映像識別子および時刻情報を特定する処理と、の一連の処理を、コンピュータに実行させることを特徴とする。このように、リファレンス映像およびクエリ映像を一定時間長のセグメントに分割し、各セグメントから予め定められた数のフレームを選択し、選択されたフレームから映像の特徴を示す特徴量を抽出し、抽出した特徴量を1つ以上の量子化識別子に変換し、リファレンス映像のセグメント情報と対応する量子化識別子の集合に基づいて、転置インデックスを構成するリストにセグメントの映像識別子と時刻情報を格納し、クエリ映像のセグメント情報と対応する量子化識別子の集合に基づいて、転置インデックスを参照し、投票により、クエリ映像の全部または一部を含むリファレンス映像の映像識別子および時刻情報を特定するので、クエリ映像の全部または一部が、リファレンス映像の時間軸上の一部分を切り出したり、リファレンス映像にテロップやロゴが挿入されたりしたものであっても、クエリ映像の検索が可能となり、検索時間を短縮し、検索の精度を高めることが可能となる。13また、本発明のプログラムは、前記選択された各フレームについて、予め定義された1つ以上の領域毎に特徴量を抽出する処理と、前記領域毎に抽出された特徴量を量子化識別子に変換する処理と、前記領域毎の量子化識別子に基づいて、前記各領域に対応する転置インデックスを構成するリストに前記領域の映像識別子と時刻情報を格納する処理と、をさらに含むことを特徴とする。このように、前記選択された各フレームについて、予め定義された1つ以上の領域毎に特徴量を抽出し、前記特徴量量子化部は、前記領域毎に抽出された特徴量を量子化識別子に変換し、前記特徴量蓄積部は、前記領域毎の量子化識別子に基づいて、前記各領域に対応する転置インデックスを構成するリストに前記領域の映像識別子と時刻情報を格納するので、1つのフレームから複数の特徴量を抽出することが可能となり、検索精度を向上させることが可能となる。本発明によれば、クエリ映像を一定時間長のセグメントに分割し、前記各セグメントから予め定められた数のフレームを選択し、前記選択されたフレームから映像の特徴を示す特徴量を抽出し、前記抽出した特徴量を1つ以上の量子化識別子に変換し、前記量子化識別子に対応する転置インデックスを構成するリストに前記選択されたフレームの映像識別子と時刻情報を格納するので、クエリ映像の全部または一部が、リファレンス映像の時間軸上の一部分を切り出したり、リファレンス映像にテロップやロゴが挿入されたりしたものであっても、クエリ映像の検索が可能となり、検索時間を短縮し、検索の精度を高めることが可能となる。以下、本発明の実施形態について図面を参照して説明する。本実施形態では、予め検出を行なおうとする著作権コンテンツをリファレンス映像として入力し、特徴量を抽出し、さらに特徴量を量子化し、データベースを構築しておく。その後、入力されたクエリ映像を用いて、リファレンス映像を検索する。図1は、本発明の実施形態に係る映像検索装置のブロック図である。図1に示すように、映像検索装置10は、映像分割部11、特徴量抽出部12、特徴量量子化部13、特徴量蓄積部14、データベース15、およびデータベース検索部16から構成されている。また、これらの構成要素は、制御バス17に接続され、相互に信号の送受信を行なうことができる。映像分割部11は、リファレンス映像をブロックに分割する。図2は、分割の様子を示す図である。この分割は、空間の分割と時間方向の分割を含む。空間方向の分割は、図3に示すように、任意の形状の矩形によって定義される。図2に示した例は、図3Bに示す分割を採用し、R4の矩形に対応するブロックを示している。なお、図3Aは、画面全体を1つの矩形領域とした場合である。キャプションやロゴなどが挿入されることを想定しないのであれば、この矩形領域を利用する。図3Bは、編集が行なわれる場所を予め決めない場合の矩形領域の設定である。図3Cは、画面下や画面右に字幕などの編集が想定される場合の矩形領域の設定である。どちらか片方に編集が行なわれても、他方の矩形領域に影響がない。時間方向の分割は、連続するフレームを一定の時間例えば0.5秒毎で区切ることによって行なわれる。矩形のIDがrの矩形かつ、時間方向にt番目のブロックをBr,tと表記する。仮に30fpsの映像を0.5秒毎に区切ると、各ブロック中には15枚のフレームが存在することになる。特徴量抽出部12は、映像分割部11で得られた各ブロックBr,tから特徴量を抽出する。これは単純に、Br,tに含まれる全てのフレームから特徴ベクトルを抽出しても良いが、抽出される特徴量の数を制限したい場合にはフレームを一定間隔でサンプリングしてから特徴量を抽出しても良い。例えば、DCT係数を利用する手法や局所特徴領域を記述するために広く用いられているScaleinvariantfeaturetransformSIFTを用いることができる。ここで、Br,tから抽出された特徴量の集合をFr,tとする。下記にDCT係数のACAlternatingCurrent成分を特徴量とする際の抽出法を説明する。まず、部分フレームを8x8画素に縮小し、離散コサイン変換DCTを行なう。得られたDCT係数のうち、AC成分をジグザグスキャン順にM個取得することでM次元の特徴量を得る。特徴量量子化部13は、特徴量抽出部12で抽出された各特徴量集合Fr,t内の特徴量を、それぞれ0~N-1までの値に量子化し、量子化IDの集合Wr,t整数値を作成する。Wr,t内のIDの数は、予め最大数が決められているか、量子化時のソフト割り当ての個数によって決定される。以下、DCT係数のAC成分を特徴量とした際のWr,tの作成法を説明する。M次元の特徴量の各次元をそれぞれ、正の値であれば1、負の値であれば0にバイナリ化する。これによりM次元の特徴量はNビットのビット列に変換される。このビット列は2^M通り存在し、このビット列を10進数表記した0~2^M-1が量子化後の値となるN=2^M。この手順により、Wr,tが得られる。但し、特徴量の微小な変化によって量子化IDが変化してしまうことに対応するため、ソフト割り当てを行なう。ソフト割り当ては、例えば、下記の文献に記載されている技術を用いて行なうことが可能である。JPhilbinOChumMIsardJSivicandAZissermanLostinquantizationImprovingparticularobjectretrievalinlargescaleimagedatabasesinProcofCVPR2008図5は、ソフト割り当ての一例を示す図である。このソフト割り当てとは、量子化時に特徴量を1つのIDだけに割り当てるのではなく、複数の量子化IDに割り当てることである。本発明では、Fr,tの各特徴量fの各次元について、絶対値が小さいものからK次元のビットを自由に反転させたIDにも割り当てることで、合計2^K個のIDに割り当てが行なわれる。IDの最大数が定められている場合には、IDの最大数を超えるまで、絶対値の小さいものから順番にビット反転を行なったIDを割り当てることを繰り返す。なお、一般的な特徴ベクトルについて、ベクトル量子化を用いて量子化を行なっても良い。予め特徴量の集合からk-meansクラスタリングを行ない、N個の代表ベクトルを求めておく。Fr,t内の特徴量をそれぞれ最も近い代表ベクトルに割り当て、その代表ベクトルのIDを量子化IDとする。また、最も近い代表ベクトルではなく、最も近いK個の代表ベクトルに割り当てることでソフト割り当てを実現することができる。以上のようにして、Wr,tの作成を行なう。なお、量子化IDの重複は許さないものとする。特徴量蓄積部14は、量子化IDの集合Wr,tを、図6に示す転置インデックスに保存する。転置インデックスは矩形毎に個別に用意する。図6に示すように、Wr,t内の全てのIDについて、対応するリストにブロックBr,tの情報を登録する。登録する情報は、リファレンス映像のビデオID、ブロックの時刻情報tとする。この登録を全てのr,tに対して行なう。特徴量蓄積部14は、これらの登録情報をデータベース15に格納する。一方、データベース検索部16は、リファレンス映像からクエリ映像の検索を行なう。検索を行なう際には、クエリ映像は、リファレンス映像を蓄積した場合と同様に、ブロックに分割し、特徴量を抽出し、量子化を行なう。ブロックの分割法はリファレンス映像を蓄積した際と同じにしなければならないが、特徴量を抽出する際に抽出される特徴量の数を削減したり、量子化を行なう際にソフト割り当てを行なうIDの数を削減することで、探索速度を向上させることができる。データベース検索部16は、クエリ映像から抽出されたWr,tそれぞれについて、Wr,t内のすべての量子化IDについて、転置インデックスの該当するリストを参照し、対応するブロックIDのリストを取得する。リスト中のブロックIDをt’とすると、対応するオフセットt’-tに投票を行なう。同時に、投票時の情報r,t,idをオフセット値t’-t毎に保存する。ここでidは量子化識別子である。また、その際、tについて昇順にソートされるように保存する。図7は、投票の様子を示す図である。全てのWr,tについて投票が終了すると、各オフセット値のスコアについて、閾値以上かつ極大の値を持つオフセット値のリストを取得する。その後、それぞれのオフセット値について、下記の処理を行なう。オフセット値t’-tについて、対応するr,t,idのリストを取得する。このリストは、前述のとおりtについて昇順にソートされている。このリストを、隣り合うtが一定以上の間隔が開いている箇所で分割することによって、部分リストに分割する。その後、それぞれの部分リストについて、スコアを計算する。最も単純には、リスト内の要素の数をスコアとする。要素の数ではなく、それぞれの要素に、idに基づく重みを利用しても良い。この重みには、文書検索で用いられるInverseDocumentFrequencyIDFを用いることができる。本発明の場合、IDFは、蓄積している映像のセグメント数をD、id番目の転置インデックスのリストのサイズをD’とすると、IDF=logD’/Dと求めることができる。更に、スコアを部分リスト内の最大のtと最小のtの差=検出したコピー領域の長さに応じて、この差が大きくなるほどスコアを小さくするように正規化しても良い。最も簡単にはスコアを最大のtから最小のtを引いた値で除算する。また、部分リストのスコアを計算する際に、隣接するtについて同じr,idが出現した際には、スコアを一度しか加算しないようにしても良い。この処理を全てのオフセットについて行なった後、部分リストのスコアでソートし、上位の結果を検索結果とする。以上説明したように、本実施形態によれば、クエリ映像を一定時間長のセグメントに分割し、前記各セグメントから予め定められた数のフレームを選択し、前記選択されたフレームから映像の特徴を示す特徴量を抽出し、前記抽出した特徴量を1つ以上の量子化識別子に変換し、前記量子化識別子に対応する転置インデックスを構成するリストに前記選択されたフレームの映像識別子と時刻情報を格納するので、クエリ映像の全部または一部が、リファレンス映像の時間軸上の一部分を切り出したり、リファレンス映像にテロップやロゴが挿入されたりしたものであっても、クエリ映像の検索が可能となり、検索時間を短縮し、検索の精度を高めることが可能となる。"