(57)【特許請求の範囲】
【請求項１】
各データが時系列的に連続しているデータ系列をクエリーとして与え、該データ系列に類似する個所を参照データ系列の中で検索するデータ系列検索装置において、
前記参照データ系列を構成する複数の参照データの各々を予め分類し、特徴が類似している参照データ群を１つの集合とする複数の集合および各集合を代表する代表参照データを予め用意し、前記複数の集合の各々と関連付けて、各集合の中に含まれる参照データの時間軸上の位置および代表参照データを予め記憶した記憶手段と，
前記クエリーのデータ系列を入力する入力手段と、
当該入力されたクエリーのデータ系列を構成する複数のデータの各々について、もっとも距離が近い代表参照データを有する集合を検出する第１の情報処理手段と、
当該検出された１以上の集合の中に含まれる参照データの時間軸上の位置に基づいて、前記検出された１以上の集合の中に含まれ、時間軸上で連続する参照データで構成される部分参照データ系列を取得する第２の情報処理手段と
を具え、当該取得された部分参照データ系列を前記クエリーのデータ系列に対する検索結果とすることを特徴とするデータ系列検索装置。
【請求項２】
各データの値が時系列的に連続しているデータ系列をクエリーとして与え、該部分的なデータ系列に類似する個所を参照データ系列の中で検索するデータ系列検索方法であって、
前記参照データ系列を構成する複数の参照データの各々が分類され、特徴が類似している参照データ群を１つの集合とする複数の集合および各集合を代表する代表データが予め用意されており、前記複数の集合の各々と関連付けて、各集合の中に含まれる参照データの時間軸上の位置および代表参照データが予めデータ処理装置の記憶手段に記憶されており，
該データ処理装置が有する情報処理手段が前記クエリーのデータ系列を構成する複数のデータの各々について、もっとも距離が近い代表参照データを有する集合を検出する第１のステップと、
前記情報処理手段が当該検出された１以上の集合の中に含まれる参照データの時間軸上の位置に基づいて、前記検出された１以上の集合の中に含まれ、時間軸上で連続する参照データで構成される部分参照データ系列を取得する第２のステップと、
を具え、当該取得された部分参照データ系列を前記クエリーのデータ系列に対する検索結果とすることを特徴とするデータ系列検索方法。
【請求項３】
請求項２に記載のデータ系列検索方法において、前記第２のステップでは、前記情報処理手段が前記時間軸上で連続する部分参照データ系列の中からさらに順次性を有する部分参照データ系列を最終的な検索結果として取得することを特徴とするデータ系列検索方法。
【請求項４】
請求項２に記載のデータ系列検索方法において、前記第１のステップでは、前記情報処理手段がクエリーのデータに距離がもっとも距離が近い代表参照データが検出されるごとに、該代表参照データを有する集合内の参照データに対して得点を与え、前記第２のステップでは、前記情報処理手段が各前記参照データの得点を時間軸上に並べたヒストグラム分布を作成し、当該作成されたヒストグラム分布に基づき連続する部分参照データ系列を取得することを特徴とするデータ系列検索方法。
【請求項５】
請求項２に記載のデータ系列検索方法において、前記データ処理装置は表示手段をさらに有し、前記情報処理手段が、逐次クエリーとして入力される前記データ系列に対する前記検索された部分参照データ系列のうち、最も時刻の進んだフレームを逐次上書きして前記表示手段に表示させる第３のステップをさらに具えることを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データが時系列的に変化するデータ系列と、類似するデータ系列を複数組のデータ系列の中から検出したり、１つの大きなデータ系列の中から検出する場合に好適なデータ系列検索装置および方法に関する。
【０００２】
【従来の技術】
近年、ＤＶＤ（デジタル・ビデオ・ディスク）やデジタルＴＶ放送の普及とともに膨大な量の動画像コンテンツが一般家庭でも簡単に手に入れることができるようになってきている。一方では、ＰＣ（パーソナルコンピュータ）の高性能化、記憶装置の大容量化も進んでおり、ＰＣあるいはＰＣの機能を有する装置動画像を取り込むニーズが高まってきている。この大きな流れの中で、動画像の検索や，理解、認識などの動画像処理はますます重要な技術となってきている。
【０００３】
動画像検索において、ユーザが膨大な動画像ＤＢ（データベース）の中から所望の区間を選び出すためには、制作者が予め付与した出演者やあらすじ等の情報やユーザの手入力によるインデックス、および画像理解に基づき自動生成されたインデックスをてがかりにする方法が提案されている。
【０００４】
従来の動画像検索に関連した第１の方法としてはＩＰＭネットワークによりシンボル化された動画像ＤＢを記述し、クエリーの（検索の元となる）動画像についてもシンボル化を行い、対応するネットワークを検索する方法が提案されている。（遠藤他、”動画像の自己組織化ネットワークによるモデル化とその動的特徴の可視化”信学技法ＰＲＭＵ９７−７８，ｐｐ．４９−５４，Ｊｕｌｙ，１９９７）。
【０００５】
また、この方法に関連する文献としては以下のものがある。
【０００６】
・矢部他、”ジェスチャ動画像と意味的記述単語系列のネットワーク構造対応に基づくジェスチャ認識”人工知能学会全国大会（第１３回）論文集、Ｓ３−０５，ｐｐ９５−９８、Ｊｕｎｅ，１９９９．
・伊藤他，”時系列標準パターンの任意区間によるスポッティングのためのＲｅｆｅｒｅｎｃｅ  Ｉｎｔｅｒｖａｌ−ｆｒｅｅ連続ＤＰ（ＲＩＦＣＤＰ），”信学論，ＶｏｌＪ７９Ｄ−ＩＩ，Ｎｏ．９，ｐｐ１４７４−１４８３、Ｓｔｅｐ．，１９９６．
・西村他、”動作者適応のためのオンライン教示可能なジェスチャ動画像の認識システム、”信学論、Ｖｏｌ．Ｊ８１−Ｄ−ＩＩ、Ｎｏ．８，ｐｐ１８２２−１８３０，Ａｕｇ．，１９９８．
・西村他”距離画像を用いた低解像度特長によるジェスチャのスポッティング認識，”人工知能学会全国大会（第１３回）論文集、Ｓ３−０６，ｐｐ９９−１０２，Ｊｕｎｅ，１９９９．
第２の方法として、アクティブ検索により動画像ＤＢおよびクエリーの画像特徴ベクトルのヒストグラムを計算し、類似度を求めて検索する以下の提案として以下のものがある。
【０００７】
・柏野他，”マルチモーダルアクティブ検索を用いた画像・音響系列の高速検索，”信学技報，ＰＲＭＵ９８−８０、ｐｐ５１−５８、Ｓｅｐ．，１９９８．
第３の方法としてカット単位での代表画像の特徴を記号化して検索に用いる提案として以下のものがある。
【０００８】
・長坂他，”時系列フレームの圧縮符号化に基づく映像シーンの高速分類方法”，信学論，ＶｏｌＪ８１−Ｄ−ＩＩ，Ｎｏ．８，ｐｐ．１８３１−１８３７，Ａｕｇ．，１９９８．
【０００９】
【発明が解決しようとする課題】
上述の第１の方法はデータベース中の動画像の各フレームとクエリーの動画像の各フレームとのマッチング（距離計算）を行うために、動画像のフレーム数が多いほどマッチングの計算時間が膨大となり、リアルタイムで検索を行うことが難しいという問題がある。
【００１０】
第２の方法は、区間限定のＣＭ検索のように任意の入力区間に未対応であるためにクエリー入力がフレーム単位で逐次行われ，その度に検索を行うといった、区間が限定されない画像の実時間検索には向いていない。
【００１１】
そこで、本発明の目的は、フレームワイズの検索を行う上で、動画像データなど、時系列的にデータが変化するデータ系列の逐次入力される記号系列をフレームワイズに検索を行うことができるデータ系列検索装置および方法を提供することにある。
【００１２】
【課題を解決するための手段】
このような目的を達成するために、本発明は例えば特許請求の範囲に記載されるように構成する。
【００２１】
【発明の実施の形態】
以下、図面を参照して本発明の実施形態を詳細に説明する。
【００２２】
最初に本実施形態のデータ系列検索方法について図１を参照して説明する。
【００２３】
(第１の実施形態）
本実施形態では、逐次入力されるクエリーのフレーム画像において、一定区間のフレーム窓を図１に示すように時間軸に沿って移動させながらフレーム単位で、検索のための情報処理を行い、クエリーの連続のフレーム画像（動画像）と類似する参照動画像部分を検出する。以下にその検索処理内容を説明する。
【００２４】
（ａ）参照動画像によるＶＱ空間の作成
クエリー画像の比較の対象となる参照動画像からフレーム単位で画像の特徴量を取得する。本実施例では１つのフレームをいくつかに分割し、画像の色情報または輝度情報を用いてＮ（正の整数）要素をもつ特徴ベクトルする。この特徴ベクトルを使用して画像の特徴が類似しているフレーム同士を集め１つの集合（セントロイド（ｃｅｎｔｒｏｉｄ）と呼ばれる）を形成し、複数のフレーム画像の集合群に動画像を分類する。画像の分類方法としては、周知の方法を使用することができる。本実施形態では量子化と呼ばれる方法を使用する。より具体的には、あるフレーム画像の特徴ベクトルと、すでに存在する１つの集合の中の全特徴ベクトルとの間の２乗誤差が一定距離以内であれば、そのフレーム画像を比較の対象となった集合の中に組み入れる。また、上記２乗誤差が一定距離以内でない場合には、そのフレーム画像を代表特徴ベクトル（セントロイドベクトル）とする新しい集合を作成する。このようにして参照動画像を量子化すると、図１に示すような複数の集合が形成される。この複数の集合群をＶＱ空間と呼ぶことにする。
【００２５】
セントロイドベクトルV(i)を以下のように定義する。ただし、i=1,2.....,M,  Mはセントロイド総数、Nは特徴要素数である。
【００２６】
【数１】
0003916813.tif 000002
【００２７】
また、集合に含まれるフレーム画像を識別するためにフレーム画像のフレーム番号τを記憶するテーブルZ(i)を用意する。iはセントロイド（集合）の識別番号である。テーブルZ(i)の内容を数式で表現すると以下のようになる。
【００２８】
【数２】
0003916813.tif 000003
【００２９】
ただし、K(i)はセントロイド番号iに属するリファレンス（参照）フレームの総数となる。以後、
【００３０】
【外１】
0003916813.tif 000004
【００３１】
は
【００３２】
【外２】
0003916813.tif 000005
【００３３】
と略して表す。
【００３４】
（ｂ）ヒストグラムの作成
クエリーとしての動画像が、各フレーム単位でＶＱ空間と同様に特徴ベクトルの形態で入力されてくるとする。時刻tにおけるクエリー入力フレームの特徴ベクトルf(t)は、
【００３５】
【数３】
0003916813.tif 000006
【００３６】
であり、ＶＱ空間の各セントロイドベクトル（代表特徴ベクトル）とクエリーのフレーム画像との２乗誤差の和を最小にするセントロイドの番号をこのフレーム画像に対するＶＱコードm(t)とする。
【００３７】
【数４】
0003916813.tif 000007
【００３８】
t≧Tとして時刻tまでの区間Tの間での入力フレームシーケンス
【００３９】
【数５】
0003916813.tif 000008
【００４０】
を考えると、対応するVQコードシーケンスは、
【００４１】
【数６】
0003916813.tif 000009
【００４２】
である。このとき、対応するリファレンスフレームシーケンスは（２）式より以下のようになる。
【００４３】
【数７】
0003916813.tif 000010
【００４４】
時刻tにおいてはK(m(t))個のレファレンスフレームが存在する。これをt-Tからtまでの長さTの区間で、横軸が参照動画像のフレーム番号uとして、縦軸を各レファレンスフレームののヒストグラムh(t,u)として（図１参照）、各リファレンスフレーム番号に対応するセロノイド番号が何度ヒットされたかの統計を求める。
【００４５】
【数８】
0003916813.tif 000011
【００４６】
【数９】
0003916813.tif 000012
【００４７】
【数１０】
0003916813.tif 000013
【００４８】
次の時刻t+1になった場合には、これまでのt-Tの時刻に関してのヒストグラムを減少させ、新たなt+1でのヒストグラムを増加させるように、フレーム窓の区間を移動させる。
【００４９】
（ｃ）クラスタリング
これまでに作成したヒストグラムを基にフレーム単位でのクラスタリングを行う。本実施形態でのクラスタリングは設定したスレッショルド（しきい値）よりも大きい区間[Cmin,Cmax]をクラスタとして検出する（図１参照）。
【００５０】
上述のデータ系列検索方法にしたがって、パーソナルコンピュータにより動画像検索の実験を行った。動画像(参照(リファレンス），クエリーとも）にはすでにキャプチャリング、特徴化を行ったものを用いた。特徴化方法は龍谷大学が提唱する６０要素からなるベクトルとした。テレビの放映画像２００，０００フレーム(２時間分)を用いてVQ空間のセントロイド数は１３，３１６であった。
【００５１】
参照動画像と同一のクエリー画像を用いて検索を行った結果、少なくともクエリーと同一の区間を参照動画像中で検出することができた。
【００５２】
(実施形態２）
上述の実施形態では、フレームの順次性を考慮していないために、参照画像のある一部分のフレーム順序が逆になったような動画像がクエリーとなった場合、参照画像の上記一部分の動画像が検出結果として得られてしまう。そこで、このようなことが無いようにフレームの順次性を考慮した第２実施形態を次に説明する。
【００５３】
（１）時間順序性を顧慮したヒストグラムの作成
ヒストグラムの、フレームの時間順序性を考慮した作成方法は以下のとおりである。(7)式に関して、
【００５４】
【外３】
0003916813.tif 000014
【００５５】
の代わりに
【００５６】
【外４】
0003916813.tif 000015
【００５７】
を考慮した(8) 式を採用する。
【００５８】
【数１０】
0003916813.tif 000016
【００５９】
ここで
【００６０】
【外５】
0003916813.tif 000017
【００６１】
は式（９）の通り。
【００６２】
【数１１】
0003916813.tif 000018
【００６３】
ここで、
【００６４】
【外６】
0003916813.tif 000019
【００６５】
【数１２】
0003916813.tif 000020
【００６６】
となる式である。
【００６７】
１つめの条件において、
【００６８】
【外７】
0003916813.tif 000021
【００６９】
は時刻t-1で存在していたクラスタが参照画像上の時刻の増加方向に伸びる場合、または、時刻t-1でクラスタは存在せず開始点となりうる場合に
【００７０】
【外８】
0003916813.tif 000022
【００７１】
となり、それ以外は空となる値である。１つ目の条件では
【００７２】
【外９】
0003916813.tif 000023
【００７３】
を漸化的に、今回の
【００７４】
【外１０】
0003916813.tif 000024
【００７５】
のうち前回伸びていたクラスタの時刻
【００７６】
【外１１】
0003916813.tif 000025
【００７７】
よりも先になるものが存在する場合に
【００７８】
【外１２】
0003916813.tif 000026
【００７９】
とする。２つ目の条件では、値
【００８０】
【外１３】
0003916813.tif 000027
【００８１】
【外１４】
0003916813.tif 000028
【００８２】
がクラスタの開始点となりうる参照画像上の時刻で、時刻t-1でのヒストグラム上のフレーム番号
【００８３】
【外１５】
0003916813.tif 000029
【００８４】
とそのｕ軸上の２つ前まで、つまり，
【００８５】
【外１６】
0003916813.tif 000030
【００８６】
におけるヒストグラムの値がそれぞれ0である場合に真となる値である。
【００８７】
なお、式中ではクラスタが伸びるための条件として、前回伸びているクラスタから時刻２以内で再びヒストグラムが投票されること、また、新しくクラスタが開始する条件として前回のクラスタから時刻２以上離れていることとしている。
【００８８】
（２）クラスタリング
検索結果として参照動画像を求めるクラスタリング時に、時刻ｔにおいて、
上記(10)式の
【００８９】
【外１７】
0003916813.tif 000031
【００９０】
で空でないものを探す（クラスタが伸びつづけている）
ヒストグラム中
【００９１】
【外１８】
0003916813.tif 000032
【００９２】
以前に一定区間Tc（例えばヒストグラム作成のためのTの４分の１）以上連続して非０でない区間を持つ
【００９３】
【外１９】
0003916813.tif 000033
【００９４】
を探す。
【００９５】
該当する
【００９６】
【外２０】
0003916813.tif 000034
【００９７】
に対応した非０でない区間の開始時刻および
【００９８】
【外２１】
0003916813.tif 000035
【００９９】
を、それぞれクラスタの開始時刻および終了時刻とする。
【０１００】
（３）動画検索アプリの検索結果表示方法
動画像の検索結果の表示例を図２に示す。上記方法でクラスタリングされた空でない
【０１０１】
【外２２】
0003916813.tif 000036
【０１０２】
を全て表示していく。
【０１０３】
時刻tにおいての結果は上記２の方法でクラスタリングしたものであるとする。次の時刻t+1では空でない
【０１０４】
【外２３】
0003916813.tif 000037
【０１０５】
を新たに求めることができる。クラスタリングの方法から伸びた差分は
【０１０６】
【外２４】
0003916813.tif 000038
【０１０７】
であるから、既に表示してある対応する結果部分にそれぞれに対応する
【０１０８】
【外２５】
0003916813.tif 000039
【０１０９】
のうち、最も時刻の進んだフレームを上書きするようにする。表示する位置は、例えば伸びたクラスタの元である対応する
【０１１０】
【外２６】
0003916813.tif 000040
【０１１１】
から最も近い画像の位置とする（画像に対応させて最新の
【０１１２】
【外２７】
0003916813.tif 000041
【０１１３】
を記憶する）。これを繰り返していくと、クエリーが逐次入力された場合の検索された結果が、動画像として表示されていくことになる。ある時刻において
【０１１４】
【外２８】
0003916813.tif 000042
【０１１５】
が空になった場合にはその画像を削除し、他の空でない
【０１１６】
【外２９】
0003916813.tif 000043
【０１１７】
に対応する画像でレイアウトし直す。
【０１１８】
（実施形態３）
上述の実施形態で説明したデータ系列検索方法にしたがって、動画像などのデータ系列と類似する個所を参照データ系列の中から検索（検出）するデータ系列検索装置を次に第３実施形態として説明する。
【０１１９】
図３は第３実施形態のシステム構成を示す。データ系列検索装置は汎用のパーソナルコンピュータが後述のプログラムを実行することにより実現されるので、パーソナルコンピュータの構成の説明は簡単に留める。
【０１２０】
図３において、ＣＰＵ１０、システムメモリ１１、入出力インターフェース（Ｉ／Ｏ）１２、ハードディスク記憶装置（ＨＤＤと略記する）１３、入力装置１４および出力装置１５がバスに記憶されている。なお、バスにはＣＤＲＯＭ読取装置（不図示）も接続されている。
【０１２１】
ＣＰＵ１０は図５に示す処理プログラムを実行してデータ系列の検索を行う。また、オペレーティングシステム（ＯＳ）にしたがって、システム制御を行う。
【０１２２】
システムメモリ１１はＣＰＵ１０が実行すべきプログラムをローディングすると共に、ＣＰＵ１０に対する入出力データを一時記憶する。出力装置１５（本例の場合表示装置）に出力するデータもシステムメモリ１１に一時記憶される。
【０１２３】
Ｉ／Ｏ１２を介して、検索対象の動画像、すなわち、クエリーの動画像が外部装置、たとえば、ビデオカメラ等から入力される。ＨＤＤ１３はＯＳ用のプログラムデータ系列検索用のプログラムを保存目的のために記憶する。入力装置１４としてはマウスのようなポインティングデバイスおよびキーボードを使用することができる。入力装置１４からはＣＰＵ１０に対する動作指示、本形態の場合には、データ系列検索用のプログラムの起動の指示を入力する。出力装置１５は、検索結果を出力する。本実施形態では出力装置１５として表示装置を使用するが、他に、プリンタや通信装置を使用することもできる。
【０１２４】
被検索の対象となる参照動画像はＩ／Ｏ１２を介して逐次入力されるものとする。また、上述した量子化により複数のセントロイド、すなわち、画像の特徴が類似するフレーム番号を集めた複数組の集合がテーブルの形態で、ＨＤＤ１３に保存されているものとする。上記テーブルは、図４に示すようにセントロイド番号ごとにそのセントロイドに含まれるフレーム画像のフレーム番号が記載されている。また、各セントロイド番号に対応させて、そのセントロイドを代表するフレーム画像（代表特徴点）の特徴データもテーブルに記載されている。以下、このテーブルを参照テーブルと呼ぶことにする。
図５〜図８を参照して図４のシステムのデータ系列検索動作を説明する。
【０１２５】
図５はデータ系列検索プログラムのメイン処理手順を示し，図６〜図８はメイン処理手順中の個別処理の詳細を示す。図５の処理プログラムは、入力装置１４からのユーザによる起動指示に応じて、ＨＤＤ１３からシステムメモリ１１にロードされＣＰＵ１０により実行される。
【０１２６】
図５のプログラムが起動されると、ＣＰＵ１０は、外部装置からクエリーの動画像をＩ／Ｏ１２を介して入力し、従来と同様にして特徴化して、特徴化された特徴データをシステムメモリ１１に一時記憶する（ステップＳ１０）。次に、ＣＰＵ１０はフレーム窓として使用するバッファ（システムメモリ内）にクエリーの動画像の先頭から所定数、説明の便宜上、３枚のフレーム画像を取り込む（ステップＳ２０）。
【０１２７】
次に、ＣＰＵ１０は取り込んだ３枚のフレー画像の第１枚目のフレーム画像番号を距離計算の対象として設定する（ステップＳ３０）。ＣＰＵ１０は、第１枚目のフレーム画像の特徴が最短距離にある代表特徴データのセントロイド番号を特徴データの距離計算により取得する（ステップＳ４０）。この処理は、図６を使用して後で詳細に説明する。
【０１２８】
たとえば、セントロイド番号１が取得されると、ＣＰＵ１０は参照テーブルを参照して、セントロイド番号１の集合に含まれる参照動画像のフレーム番号（以下、参照フレーム番号と略記する）を取得する。たとえば、セントロイド番号１の集合には、参照フレーム番号１〜５が含まれているとすると、各参照フレーム番号のヒストグラムの値（得点）を記憶する変数がそれぞれ１だけインクリメントされる。この例では、参照フレーム番号１〜５のヒストグラムのそれぞれの値が初期値０から１にインクリメントされる（ステップＳ６０）。
【０１２９】
次にＣＰＵ１０はクエリーのフレーム番号を第１番目のフレーム番号から第２番目のフレーム番号に変更して、フレーム番号の特徴データと類似する代表特徴データを有するセントロイド番号を検出する（ステップＳ６０→Ｓ３０〜Ｓ４０）。
【０１３０】
検出されたセントロイド番号の集合内の参照フレーム番号を参照テーブルから取得すると、参照フレーム番号に対応する全てのヒストグラムの値を１だけインクリメントする（ステップＳ４０）。このようにして、ステップＳ３０〜Ｓ６０の処理を繰り返して、バッファに格納した３枚のクエリーの特徴データに類似するセントロイドおよびそのセントロイドに含まれる参照フレーム番号を検出する。また、その参照フレーム番号のヒストグラムの値がインクリメントされて行く（図１参照）。
【０１３１】
バッファに格納された３枚のフレーム画像についてヒストグラムが計算されると、ＣＰＵ１０は手順をステップＳ１０に戻し、バッファをＦＩＦＯ（ファーストインファーストアウト）する。具体的には、バッファの記憶内容を前送りし、最初の記憶データを破棄して、新しい次のデータ、この場合、第４番目のクエリーのフレーム画像の特徴データをバッファに格納する（ステップＳ７０→Ｓ７５→Ｓ１０）。以下、ＣＰＵ１０はステップＳ３０〜Ｓ６０の手順を繰り返して、第２番目〜第４番目のフレーム画像の特徴データのそれぞれについて、最短距離の代表特徴データを有するセントロイド番号を検出する。また、そのセントロイドに含まれる参照フレーム番号を検出して、ヒストグラムの値をインクリメントする。
【０１３２】
クエリーの動画像の全てのフレーム画像について、上述の処理を終了すると、ＣＰＵ１０はヒストグラムの値の分布において、ヒストグラムの値がしきい値以上となる山の部分の参照フレーム画像の連続区間を検出する（図１のクラスタ部分）。
【０１３３】
検出されたフレーム画像の時間軸上の連続区間は参照フレーム番号の形態で与えられるので、ＣＰＵ１０は連続区間の開始の参照フレーム番号と、最終の参照フレーム番号を出力装置１５から出力する。
【０１３４】
図５のステップＳ４０の最短距離のセントロイド番号の検出処理の詳細を図６を参照して説明する。
【０１３５】
図６において、ＣＰＵ１０は、セントロイド番号を初期値１に設定する（ステップＳ１００）。次に、設定されたセントロイド番号に対応する代表特徴データを参照テーブルから取得する。取得した代表特徴データと、クエリー側の特徴データとの距離計算を従来と同様の計算方法で行う（ステップＳ１１０）。
【０１３６】
距離の計算結果が得られると、これまでに得られた最小の距離計算結果と比較する。なお、距離計算結果が第１回目の場合には、これまでに得られた最小値として予めステップＳ１００で大きな値を初期設定しておけばよい。これにより、セントロイド番号１の特徴データについての距離計算結果が、これまでの最小の距離計算結果としてシステムメモリ１１に一時格納される（ステップＳ１２０→Ｓ１３０）。
ＣＰＵ１０は手順をステップＳ１４０からＳ１００に戻し、セントロイド番号を次の番号、この場合”２”に更新し、セントロイド番号２の代表特徴データと、クエリー側の特徴データとの間の距離を計算する。距離の計算結果は、これまでに得られた最小値と比較され、新たに得られた距離計算結果がこれまでの最小値よりも小さい場合には、新しく得られた距離計算結果が、これまでに得られた最小値に変更される。また、この時使用されたセントロイド番号がシステムメモリ１１に更新的に一時記憶される。このようにして、ステップＳ１００〜Ｓ１４０の手順を繰り返して最後のセントロイド番号まで距離計算を繰り返すと、システムメモリ１１には、最小の距離計算結果が得られた時のセントロイド番号が一時記憶されていることになる。
【０１３７】
図５のステップＳ５０のヒストグラム作成処理を図７を参照して説明する。図７において、上述のセントロイド番号検出処理により検出されたセントロイド番号がシステムメモリ１１に一時記憶されているので、参照テーブルを参照し、セントロイド番号の示す集合に含まれる参照フレーム番号のヒストグラムの値に対しては、加算値を”１”とし、それ以外の参照フレーム番号のヒストグラムの値に対しては加算値”０”が与えられる（ステップＳ２１０）。
【０１３８】
本実施形態では、参照フレーム番号１から最終の番号まで、参照フレーム番号を更新しながら（ステップＳ２００）、ヒストグラムの値の加算処理を一括して行う（ステップＳ２００〜Ｓ２３０のループ処理）。加算されたヒストグラムの値は、参照フレーム番号に関連付けられてシステムメモリ１１内に一時記憶される。
【０１３９】
図５のクエリー画像と合致（類似も含む）する参照動画像部分の検出処理を図８を参照して説明する。説明の便宜上、図１に示すヒストグラムが作成されているものとする。図８の処理手順はフラグを使用する。このフラグはヒストグラム分布でしきい値以上となる参照フレーム番号の連続性の有無をオン／オフで表す。より具体的には、ヒストグラム分布中で、図１のＣｍｉｎでヒストグラムの値がしきい値を超えると、フラグがオンのままとなり、Ｃｍａｘでしきい値以下になるとフラグがオフになる。したがって、フラグがオフからオンに切り替わる時点の参照フレーム番号が検索結果の開始フレーム番号であり、フラグがオンからオフに切り替わる時点の参照フレーム番号が検索結果の最終フレーム番号となる。
【０１４０】
ＣＰＵ１０は参照フレーム番号を初期値”１”，フラグを初期値オフに設定する（ステップＳ３００）。設定された参照フレーム番号のヒストグラムの値をシステムメモリ１１から読み出して、予め定められているしきい値と比較する。図１の例では、参照フレーム番号１のヒストグラムの値は”０”であるので、ステップＳ３１０の比較判定ではＮＯ（ヒストグラムの値（得点）はしきい値よりも小）の判定が得られる。
【０１４１】
このため、手順はステップＳ３１０→Ｓ３１１へと進み、フラグがオンであるか否かが判定される。この判定処理は、ヒストグラム分布の値がしきい値より大きい部分から小さい部分に切り替わる個所、すなわち、最終フレーム番号部分を検出するための判定処理である。フラグはオフであるので、判定結果はＮＯの判定（参照フレーム番号１は最終フレーム番号ではない）が得られる。
【０１４２】
したがって、手順はステップＳ３１１→Ｓ３４０→Ｓ３００へと進み、処理対象の参照フレーム番号が”２”に更新される。図１を見ると明らかなように、参照フレーム番号２のヒストグラムの値は”０”なので、手順はステップＳ３００→Ｓ３１０→Ｓ３１１→Ｓ３４０→Ｓ３００の経路を進む。この手順経路はヒストグラムの値がしきい値を超える参照フレーム番号Ｃｍｉｎに処理対象の参照フレーム番号が到着するまで繰り返される。
【０１４３】
処理対象の参照フレーム番号がＣｍｉｎに更新されると、ステップＳ３１０のしきい値との比較判定処理で、判定結果がＹＥＳとなる。続いて、現在のフラグの判定処理によりフラグがオフであることが確認される。これにより手順は、ステップＳ３１０→Ｓ３２０→Ｓ３３０と進み、ここで、フラグがオフからオンに変更される。また、検索結果の開始フレーム番号としてＣｍｉｎがシステムメモリ１１に登録され、検査結果部分のフレーム長さが値”１”に初期設定される。
【０１４４】
手順はステップＳ３３０→Ｓ３４０→Ｓ３００へと進み、処理対象の参照フレーム番号がＣｍｉｎ+１に更新される。図１に示すように、このフレーム位置のヒストグラムの値はしきい値よりも大きいのでステップＳ３１０の判定結果はＹＥＳとなる。現在のフラグはオンなので、手順はステップＳ３１０→Ｓ３２０→Ｓ３２５へと進み、これまでの検索結果部分の長さ”１”に値”１”が加算され、検索結果部分のフレーム長さが”２”に更新される。
【０１４５】
以後、図１のヒストグラム分布中で、処理対象の参照フレーム番号がＣｍａｘまで、ステップＳ３００〜Ｓ３２５→Ｓ３４０→Ｓ３００の手順経路が繰り返し実行されて、検索結果部分の長さの計数が行われる。
【０１４６】
処理対象の参照フレーム番号がＣｍａｘ＋１になると、図１のヒストグラムではヒストグラムの値がしきい値以下となるので、手順はステップＳ３００→Ｓ３１０→Ｓ３１１の経路を進む。フラグはオンになっているので、ステップＳ３１１の判定処理はＹＥＳ判定、すなわち、ヒストグラム分布の山の終了の判定が得られる。本実施形態では雑音除去のためにステップＳ３１２の判定処理を設け、ヒストグラム分布の山の時間軸上の長さ（参照フレームの連続の長さ）がしきい値以上となった場合に、参照フレームの連続部分を検索結果として確定している。本例では、ステップＳ３１２の判定処理がＹＥＳ判定となるなるので、現在の参照フレーム番号（Ｃｍａｘ＋１）から数値１を引いた値が連続部の終了フレーム番号として、システムメモリ１１に登録される。また、フラグがオフされる（ステップＳ３１２〜Ｓ３１４）．
以下、ＣＰＵ１０は上述の処理手順にしたがって、処理対象の参照フレーム番号を更新しながら（ステップＳ３００）、図１のヒストグラムの山の部分の開始および終了位置（参照フレーム番号）を検出する。
【０１４７】
検出された参照フレームの開始番号および終了番号が、クエリーについての検索結果として出力される。以上述べた処理手順は第１の実施形態の方法をソフトウェアで実現するが、第２の実施形態についても（９）式〜（１１）式を使用して、ヒストグラムのフレームの順次性を確認する処理手順を実行すればよく、詳細な説明を要しないであろう。
【０１４８】
上述の実施形態の他に次の実施形態を実施できる。
【０１４９】
１）第１の実施形態ではヒストグラムの山の部分を検出する条件を、
（ａ）ヒストグラムの値がしきい値以上であること
（ｂ）山の長さがしきい値以上であること
（ｃ）ヒストグラムの分布曲線が連続であること
と定めているが、用途に応じて異なる検出条件を定めてもよい。
【０１５０】
たとえば、上記（ｃ）の代わりに、２つの山が検出された場合に、前の山の終了位置と後の山の開始位置の間の距離がしきい値以下の場合、２つの山は連続とみなすというような条件を設定することもできる。また、（ａ）、（ｂ）で使用する閾値の値をキーボード等から入力することにより可変設定すると、検索精度をユーザが調整することができる。
【０１５１】
２）検索結果の出力の形態は、参照フレームの開始番号および終了番号を文字の形態で出力する方法、参照フレームの開始番号と、以後の参照フレームの枚数を文字の形態で出力する方法、さらにはヒストグラムの分布曲線の形態で図形表示する方法、参照フレーム開始番号〜終了番号までの間の参照部分動画像を表示画面に表示する方法等用途に応じて適宜定めればよい。
【０１５２】
３）本実施形態ではデータ系列として、動画像を例に説明したが、他のデータ系列、たとえば、音声データやアナログあるいはデジタルの信号波形など、連続的に値が変化する信号，データ系列に対して本発明を適用できる。
【０１５３】
４）フレーム窓に記憶する特徴データはクエリ画像のフレーム画像が入力されるごとに更新される。そこで、フレーム窓に新たに記憶されたと特徴データと、参照テーブルの代表点の特徴データとの距離計算を行い、その距離計算結果をシステムメモリ１１に記憶しておくとよい。これにより、この特徴データがフレーム窓に記憶されている間、この特徴データを使用した距離計算はその都度行う必要はなく、システムメモリ１１に一時記憶した距離計算結果を使用することができる。これにより、距離計算時間を短縮することができる。また、フレーム窓に新規に格納されるクエリー画像の特徴データは変化するが前の時刻の特徴データと現在の時刻の特徴データの差分値を求め、この差分値を使用して、前回の距離計算結果に対する補正値を求めることにより、距離計算時間を短縮することもできる。
【０１５４】
５）図５の処理プログラムを記録しておく記憶媒体は、ＲＯＭ，ＲＡＭのようなＩＣメモリ、ハードディスクのような固定記憶装置、フロッピーディスク、ＭＯなどの携帯用記録媒体とすることができる。また、このような記録媒体に記録された処理プログラムが圧縮されたり暗号化されたとしても、本発明で定義されている記録媒体に該当することは言うまでもない。さらに、図５の処理プログラムが、電話線のような、通信ネットワークや、ＲＳ２３２Ｃのような通信ケーブルを介して外部装置からデータ系列検索装置にダウンロードされる場合には、外部装置上の図５の処理プログラムを記憶する記憶装置等が本発明の記録媒体に該当する。
【０１５５】
６）上述した実施形態は本発明を説明するための１実施形態であって、上記実施形態に対して種々の変形を行っても、その変形した実施形態が本願特許請求に範囲に記載した技術思想に合致する場合には、その改良形態は特許権の侵害となる。
【０１５６】
【発明の効果】
本発明では、時系列的にデータが連続するデータ系列では、データの値が急激に変化することはまれであって、データの特徴が部分的に変化する点に着目し、参照データ系列を構成する複数の参照データを複数の集合に分類しておく。また、各集合を代表する代表参照データが用意される。これら代表参照データとクエリー側のデータ系列の各データとの距離を計算する。従来では参照データ系列の各参照データとクエリー側の各データとの間の距離を計算しなければならなかったので、本発明の方が距離計算回数が大幅に低減される。また、クエリーの画像と類似する代表参照データを有する集合が検出されると、その集合に含まれる参照データで時系列的に連続するものを取得することにより、クエリーに類似する個所についての参照データ系列の中の検索結果とすることができる。
【０１５７】
さらに、得られた検索結果の中で、データの順次性を調べることにより、データの並び順がクエリーのデータ系列とは逆順となったような部分参照データ系列を検索結果から排除することができる。
【０１５８】
さらにはヒストグラム分布のような情報処理として計算時間の短い統計的手法を使用して、特定の１以上の集合の中に散在する複数の参照データから時間軸の連続する部分参照データ系列を見かけ上作成することができる。
【０１５９】
以上の結果、距離計算の計算時間が短縮され、もって、逐次入力されたクエリーのデータ系列（記号化されたデータ系列）をフレームワイズ，リアルタイムに検索することが可能となる。
【図面の簡単な説明】
【図１】本発明第１の実施形態のデータ系列検索方法を説明するための説明図である。
【図２】本発明第２の実施形態の検索結果の出力例を示す説明図である。
【図３】本発明第３の実施形態のシステム構成を示すブロック図である。
【図４】各セントロイドに含まれる参照データのフレーム番号を記載した参照テーブルの一例を示す説明図である。
【図５】ＣＰＵ１０が実行する処理プログラムの内容を示すフローチャートである。
【図６】ＣＰＵ１０が実行する処理プログラムの内容を示すフローチャートである。
【図７】ＣＰＵ１０が実行する処理プログラムの内容を示すフローチャートである。
【図８】ＣＰＵ１０が実行する処理プログラムの内容を示すフローチャートである。
【符号の説明】
１０  ＣＰＵ
１１  システムメモリ
１２  Ｉ／Ｏ
１３  ＨＤＤ
１４  入力装置
１５  出力装置
【図１】
0003916813.tif 000044
【図２】
0003916813.tif 000045
【図３】
0003916813.tif 000046
【図４】
0003916813.tif 000047
【図５】
0003916813.tif 000048
【図６】
0003916813.tif 000049
【図７】
0003916813.tif 000050
【図８】
0003916813.tif 000051