(57)【要約】【課題】  ２つの系列ＡとＢとを対応付ける場合に、系列Ａと系列Ｂとの対応付けを求めることによって、探索漏れなく、探索区間を狭めることができ、計算時間の削減を可能とする。【解決手段】  本発明は、イベント系列Ａとイベント系列Ｂを読み込み、系列Ａを分割するためのルールを読み込んで、イベント系列Ａを複数に分割し、分割されたイベント系列Ａの系列Ａ部分列それぞれについて、対応付く可能性のあるイベント系列Ｂの系列Ｂ部分列を選択し、系列Ａ部分列と系列Ｂ部分列とを対応付け、対応付けられた結果同士を組み合わせることにより、全区間にわたる対応付けを行う。【選択図】  図１
2005331612.tif 000002
【特許請求の範囲】
【請求項１】
シナリオから得られるイベント系列Ａと、映像から得られるイベント系列Ｂとの対応付けを任意の個数求めるための系列の対応付け方法において、
前記イベント系列Ａを記憶手段から読み込む系列Ａ読み込みステップと、
前記イベント系列Ｂを記憶手段から読み込む系列Ｂ読み込みステップと、
前記系列Ａを分割するためのルールを分割ルール記憶手段から読み込んで、前記イベント系列Ａを複数に分割する系列Ａ分割ステップと、
前記系列Ａ分割ステップで分割されたイベント系列Ａの系列Ａ部分列それぞれについて、対応付く可能性のある前記イベント系列Ｂの系列Ｂ部分列を選択する系列Ｂ選択ステップと、
前記系列Ａ部分列と前記系列Ｂ部分列とを対応付ける区間内対応付けステップと、
前記区間内対応付けステップで対応付けられた結果同士を組み合わせることにより、全区間にわたる対応付けを行い、記憶手段に出力する区間間対応付けステップと、
からなることを特徴とする系列対応付け方法。
【請求項２】
前記系列Ｂ選択ステップは、
予めイベントの発生に必要な最小の時間が設定されているイベント必要時間記憶手段から、該イベントの発生に必要な最小な時間を読み込み、個々の前記系列Ａ部分列に対して、必要な最小時間を求め、該最小時間の情報を用いて前記系列Ｂ部分列を求める請求項１記載の系列対応付け方法。
【請求項３】
シナリオから得られるイベント系列Ａと、映像から得られるイベント系列Ｂとの対応付けを任意の個数求めるための系列の対応付け装置であって、
前記イベント系列Ａを記憶手段から読み込む系列Ａ読み込み手段と、
前記イベント系列Ｂを記憶手段から読み込む系列Ｂ読み込み手段と、
前記系列Ａを分割するためのルールを分割ルール記憶手段から読み込んで、前記イベント系列Ａを複数に分割する系列Ａ分割手段と、
前記系列Ａ分割手段で分割されたイベント系列Ａの系列Ａ部分列それぞれについて、対応付く可能性のある前記イベント系列Ｂの系列Ｂ部分列を選択する系列Ｂ選択手段と、
前記系列Ａ部分列と前記系列Ｂ部分列とを対応付ける区間内対応付け手段と、
前記区間内対応付け手段で対応付けられた結果同士を組み合わせることにより、全区間にわたる対応付けを行う区間間対応付け手段と、
を有することを特徴とする系列対応付け装置。
【請求項４】
予めイベントの発生に必要な最小の時間が設定されているイベント必要時間記憶手段を更に有し、
前記系列Ｂ選択手段は、
前記イベント必要時間記憶手段から、該イベントの発生に必要な最小な時間を読み込み、個々の前記系列Ａ部分列に対して、必要な最小時間を求め、該最小時間の情報を用いて前記系列Ｂ部分列を求める手段を含む請求項３記載の系列対応付け装置。
【請求項５】
シナリオから得られるイベント系列Ａと、映像から得られるイベント系列Ｂとの対応付けを任意の個数求めるための系列の対応付けプログラムであって、
コンピュータに前記請求項１または２記載の方法を実行させることを特徴とする系列対応付けプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、系列対応付け方法及び装置及びプログラムに係り、特に、２つの系列ＡとＢの対応付けるための系列対応付け方法及び装置及びプログラムに関する。詳しくは、２つの系列ＡとＢの最適な対応付けを、複数個求めるための系列対応付け方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
２つの系列、例えば、シナリオから得られる単語の系列と当該シナリオに対する映像の音声認識結果の系列、とを対応付けることにより、字幕の表示タイミングを自動的に付与する、映像に関して説明するための情報（メタデータ）の付与を行うといった研究がなされている（例えば、特許文献1、非特許文献１参照）。
【特許文献１】特開平１０−２５４４７８「音声原稿最適照合装置及び方法」
【非特許文献１】柳沼良知、坂内正夫「ＤＰマッチングを用いたドラマ映像・音声・シナリオ文書の対応付け手法の一提案」電子情報通信学会論文誌Ｄ−II，Ｖｏｌ．Ｊ７９−Ｄ−II，Ｎｏ．５，  ｐｐ．７４７−７５５，１９９６
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、上記従来のシナリオから得られる単語列と映像の音声認識から得られる単語列との対応付け技術における対応付け方法は、ＤＰマッチングを用いるものであり、これは最適な対応付けを高速に発見するアルゴリズムであり、正解の候補となる複数の対応付けを求めることは困難である。しかしながら、最適な経路が正しくない可能性もあり、オペレータによる作業で正しい経路を求めるような場合には、複数の経路を求める必要がある。
【０００４】
本発明は、上記の点に鑑みなされたもので、高速に最適な任意個の対応付けを求めることが可能な系列対応付け方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
図１は、本発明の原理を説明するための図である。
【０００６】
本発明は、シナリオから得られるイベント系列Ａと、映像から得られるイベント系列Ｂとの対応付けを任意の個数求めるための系列の対応付け方法において、
イベント系列Ａを記憶手段から読み込む系列Ａ読み込みステップ（ステップ１）と、
イベント系列Ｂを記憶手段から読み込む系列Ｂ読み込みステップ（ステップ２）と、
系列Ａを分割するためのルールを分割ルール記憶手段から読み込んで、イベント系列Ａを複数に分割する系列Ａ分割ステップ（ステップ３）と、
系列Ａ分割ステップで分割されたイベント系列Ａの系列Ａ部分列それぞれについて、対応付く可能性のあるイベント系列Ｂの系列Ｂ部分列を選択する系列Ｂ選択ステップ（ステップ４）と、
系列Ａ部分列と系列Ｂ部分列とを対応付ける区間内対応付けステップ（ステップ５）と、
区間内対応付けステップで対応付けられた結果同士を組み合わせることにより、全区間にわたる対応付けを行い、記憶手段に出力する区間間対応付けステップ（ステップ６）と、からなる。
【０００７】
また、本発明は、系列Ｂ選択ステップ（ステップ４）において、
予めイベントの発生に必要な最小の時間が設定されているイベント必要時間記憶手段から、該イベントの発生に必要な最小な時間を読み込み、個々の系列Ａ部分列に対して、必要な最小時間を求め、該最小時間の情報を用いて系列Ｂ部分列を求める。
【０００８】
図２は、本発明の原理構成図である。
【０００９】
本発明は、シナリオから得られるイベント系列Ａと、映像から得られるイベント系列Ｂとの対応付けを任意の個数求めるための系列の対応付け装置であって、
イベント系列Ａを記憶手段７から読み込む系列Ａ読み込み手段１と、
イベント系列Ｂを記憶手段８から読み込む系列Ｂ読み込み手段２と、
系列Ａを分割するためのルールを分割ルール記憶手段９から読み込んで、イベント系列Ａを複数に分割する系列Ａ分割手段３と、
系列Ａ分割手段３で分割されたイベント系列Ａの系列Ａ部分列それぞれについて、対応付く可能性のあるイベント系列Ｂの系列Ｂ部分列を選択する系列Ｂ選択手段４と、
系列Ａ部分列と系列Ｂ部分列とを対応付ける区間内対応付け手段５と、
区間内対応付け手段５で対応付けられた結果同士を組み合わせることにより、全区間にわたる対応付けを行い、対応付け記憶手段１１に出力する区間間対応付け手段６と、を有する。
【００１０】
また、本発明は、予めイベントの発生に必要な最小の時間が設定されているイベント必要時間記憶手段を更に有し、
系列Ｂ選択手段４は、
イベント必要時間記憶手段１０から、該イベントの発生に必要な最小な時間を読み込み、個々の系列Ａ部分列に対して、必要な最小時間を求め、該最小時間の情報を用いて系列Ｂ部分列を求める手段を含む。
【００１１】
本発明は、シナリオから得られるイベント系列Ａと、映像から得られるイベント系列Ｂとの対応付けを任意の個数求めるための系列の対応付けプログラムであって、コンピュータに上記の系列対応付け方法を実行させるプログラムである。
【発明の効果】
【００１２】
本発明は、系列Ａと系列Ｂを対応付ける、対応付け問題において、系列Ａを複数個に分割し、分割された部分と対応付く可能性のある系列Ｂの要素を選択し、対応付けを行うことにより、最適な任意個の対応付けを、全探索よりも少ない計算量で求めることができる。
【発明を実施するための最良の形態】
【００１３】
以下、図面と共に本発明の実施の形態を説明する。
【００１４】
図３は、本発明の一実施の形態における対応付け装置の構成を示す。
【００１５】
同図に示す対応付け装置は、系列Ａ読み込み部１、系列Ｂ読み込み部２、系列Ａ分割部３、系列Ｂ選択部４、区間内対応付け部５、区間間対応付け部６、系列Ａ記憶部７、系列Ｂ記憶部８、系列Ａ分割ルール記憶部９、イベント必要時間記憶部10、対応付け記憶部11から構成される。
【００１６】
系列Ａ読み込み部１は、系列Ａ記憶部７から系列Ａの情報を読み取る。
【００１７】
系列Ｂ読み込み部２は、系列Ｂ記憶部８から系列Ｂの情報を読み取る。
【００１８】
系列Ａ分割部３は、系列Ａ読み込み部１から系列Ａを受け取り、系列Ａ分割ルール記憶部９に記憶されている分割ルールを用いて系列Ａを複数個に分割する。
【００１９】
系列Ｂ選択部４は、系列Ａ分割部３で分割された系列Ａのブ部に対して、対応付く可能性のある系列Ｂ中の要素を、イベント必要時間記憶部10に記憶されている選択ルールを用いて選択する。
【００２０】
区間内対応付け部５は、系列Ａ分割部３で分割された系列Ａ中の候補と、系列Ｂ選択部で選択された系列Ｂ中の候補とを対応付け（対応付けをＲｏｕｔｅｉとおく（ｉ＝０，１，…，Ｎ））、評価値Ｅｉ＝Ｆ（Ｒｏｕｔｅｉ）がある基準を満たす対応付けを区間内対応付け結果とする。ここで、対応付け方法としては、例えば、全探索によって実現が可能であるが、他の方法で求めても構わない。また、経路の選択基準は、予め定めた閾値より良い評価値を持つ対応付け、あるいは、予め定めた所定の数（Ｐ）個の対応付けを選択しても構わない。
【００２１】
区間間対応付け部６は、区間内対応付け部５で求めた区間内対応付け結果同士を組み合わせ（求められる対応付けをＲｉとおく（ｉ＝０，１，２，…，Ｌ））、評価値Ｖｉ＝Ｅ（Ｒｉ）がある基準を満たす場合、全体の対応付けとして、対応付け記憶部１1に格納する。
【００２２】
系列Ａ記憶部７は、系列Ａの情報を格納する。その例を図４に示す。同図の例では、系列Ａの情報として、ＩＤ，イベント、時間から構成される。
【００２３】
系列Ｂ記憶部８は、系列Ｂの情報を格納する。その例を図５に示す。同図の例では、系列Ｂの情報として、ＩＤ，イベント、時間から構成される。
【００２４】
系列Ａ分割ルール記憶部９は、系列Ａを分割するためのルールが格納される。このルールは、実施者が予め問題に合わせて設計するものとする。
【００２５】
イベント必要時間記憶部１０は、イベントが発生するのに必要な最小限の時間を記憶する。これは、実施者が予め問題に合わせて設計する。イベント必要時間記憶部１０は、各イベント毎にイベント必要時間テーブルを有しており、実験的に得られたデータが設定される。
【００２６】
対応付け記憶部１１は、図６に示すような対応付け結果が格納される。
【００２７】
次に、上記の構成における動作を説明する。
【００２８】
図７は、本発明の一実施の形態における全体のフローチャートである。
【００２９】
ステップ１０１）  系列Ａ読み込み部1が系列Ａを系列Ａ記憶部7から読み込む。
【００３０】
ステップ１０２）  系列Ｂ読み込み部２が系列Ｂを系列Ｂ記憶部8から読み込む。
【００３１】
ステップ１０３）  系列分割部3が系列Ａ分割ルール記憶部９から読み込む情報を用いて、系列Ａを複数個に分割する。なお、系列Ａ分割ルール記憶部９に記憶されるルールは、系列Ａを複数の部分列に分割できるルールであればよい。
【００３２】
ステップ１０４）  系列Ｂ選択部４が、ステップ１０３で分割されたＡの部分に対して、対応付く可能性のある系列Ｂ中の要素を、イベント必要時間記憶部１０のイベントの発生に必要な最小限の時間の情報を用いて選択する。
【００３３】
ステップ１０５）  区間内対応付け部5がステップ１０４で分割されたＡの部分と、ステップ１０４で選択されたＡの部分と対応付く可能性のある系列Ｂ中の要素とを、全探索により対応付けを行い、ｐ番目に最適な対応付けまでを候補として選択する。
【００３４】
ステップ１０６）  区間間対応付け部６が、ステップ105で求められた区間内対応付け間の組み合わせにより全区間にわたる対応付けを作成し、最適な任意個の対応付けを候補として選択し、対応付け記憶部１１に格納する。
【００３５】
次に、上記のステップ１０３の系列分割処理について詳細に説明する。
【００３６】
図８は、本発明の一実施の形態における系列分割処理のフローチャートである。
【００３７】
ステップ８０１）  系列Ａ分割ルール記憶部９から実施者が予め定めた系列Ａを分割するためのルールを読み込む。
【００３８】
ステップ８０２）  ルールに基づいて系列Ａを分割し、
Ａ＝｛Ｋ１，Ｋ２，…，Ｋｋ、ｍａｘ｝
とする。ここで、Ｋ１＝｛Ａ１，…，Ａｘ｝である。
【００３９】
系列Ｗの要素数をＮ（Ｗ）と表すこととすると、このステップ１０３によって、
Ｏ（Ｄ（Ｎ（Ａ），Ｎ（Ｂ）））＝Ｎ（Ａ）！・Ｎ（Ｂ）！          （１）
の計算である問題が、
Ｏ（Ｄ（Ｎ（Ａ），Ｎ（Ｂ）））＝σ｛Ｎ（Ｋｉ）！・Ｎ（Ｂ）！｝    （２）
となる。ここで、Ｎ（Ａ）=ΣＮ（Ｋｉ）であるから、式（１）＞式（２）は明らかである。
【００４０】
次に、ステップ１０４の系列選択処理についてについて説明する。
【００４１】
ステップ９０１）  イベント必要時間記憶部１０のイベント必要時間テーブルからイベントの発生に必要な最小の時間を読み込む。
【００４２】
ステップ９０２）  ｘ＝１と初期化する。
【００４３】
ステップ９０３）  系列Ａ部分列Ｘｘに対して、Ｘ０〜Ｘｘ−１までに必要な最小時間（ｍｉｎ）を求めて、Ｓ（Ｘｘ）＝ｍｉｎとする。
【００４４】
ステップ９０４）  Ｘｘ＋１からＸｘ＿ｍａｘまでに必要な最小時間（ｍｉｎ）を求めて、映像の終了時間Ｔからｍｉｎを引いて、Ｌ（Ｘｘ）＝Ｔ−ｍｉｎとする。
【００４５】
ステップ９０５）  ｉ＝０と初期化する。
【００４６】
ステップ９０６）  Ｓ（Ｘｘ）＜Ｔｉｍｅ（Ｂｉ）＜Ｌ（Ｘｘ）を満たせばステップ９０７に移行し、そうでなければステップ９０８に移行する。ここでＳ（Ｘｘ）は系列Ａ部分列Ｘｘが始まる時間、Ｔｉｍｅ（Ｂｉ）は、系列Ｂ中のイベントＢｉの発生時刻を返す関数である。
【００４７】
ステップ９０７）  系列Ａ部分列Ｘｘに対応する系列Ｂ部分列Ｍ（Ｘｘ）にＢｉを加える。
【００４８】
ステップ９０８）  ｉ＜ｂ＿ｍａｘであればステップ９０９へ移行し、そうでなければステップ９１０に移行する。
【００４９】
ステップ９０９）  ｉをインクリメントする。
【００５０】
ステップ９１０）  ｘ＜ｘ＿ｍａｘであればステップ９１１へ移行し、そうでなければ処理を終了する。
【００５１】
ステップ９１１）  ｘをインクリメントする。
【００５２】
上記のステップ１０４によって、
Ｏ（Ｄ（Ｎ（Ｋｉ），Ｎ（Ｂ）＝Ｎ（Ｋｉ）！・Ｎ（Ｂ）！
の計算である問題の、Ｂを小さくすることができる。従って計算量を削減できる。
【００５３】
次に、上記のステップ１０５の全探索による対応付け処理について説明する。
【００５４】
図１０は、本発明の一実施の形態における全探索による対応付け処理のフローチャートである。
【００５５】
ステップ１００１）  ｘ=１と初期化する。
【００５６】
ステップ１００２）  系列Ａ部分列ＫｘとＫｘに対応する系列Ｂ部分列Ｍ（Ｋｘ）の要素について、可能なすべての対応付けを全探索により求め、Ｒｏｕｔｅ１，Ｒｏｕｔｅ２，…，Ｒｏｕｔｅｐｘとする。この可能なすべての対応付けを求める方法については後述する。
【００５７】
ステップ１００３）  ｐ=１と初期化する。
【００５８】
ステップ１００４）  Ｅｐ＝Ｆ（Ｒｏｕｔｅｐ）によってＲｏｕｔｅｐを評価する。
【００５９】
ステップ１００５）  ｐ＜ｐ＿ｍａｘならばステップ１００６へ移行し、そうでなければステップ１００７に移行する。
【００６０】
ステップ１００６）  ｐをインクリメントする。
【００６１】
ステップ１００７）  評価値Ｅｐが区間ｘ毎に予め定められた要件を満たす場合、区間内対応付け候補として、Ｒｏｕｔｅ１ｘ，…，Ｒｏｕｔｅｐ＿ｍａｘｘとする。予め定める用件は、例えば、評価値Ｅｐが最適な予め定めたｐｘ＿ｍａｘ個の対応付けでもよいし、または、Ｅｐ＞Ｔｈｘの閾値処理でも構わない。
【００６２】
ステップ１００８）  ｘ＜ｋ＿ｍａｘであれば、ステップ１００９に移行し、そうでなければ終了する。
【００６３】
ステップ１００９）  ｘ（区間のカウント）をインクリメントしてステップ１００２に移行する。
【００６４】
ステップ１００２の可能なすべての対応付けは、例えば、以下のような方法で行うことができる。
【００６５】
系列Ａ部分列Ｋｘ中のイベント｛Ａａ，…，Ａ，，｝と映像から検出したＫｘと対応付く可能性のあるイベントＭ（Ｋｘ）＝｛Ｂｂ，…，Ｂｃ｝とを対応付ける組を考える場合には、
・カウンタｉ１をｉ１＝ｂと初期化する。
・カウンタｉ２をｉ２＝ｉ１＋１と初期化する。
・カウンタｉ３をｉ３＝ｉ２＋１と初期化する。
・
・
これに続けて
・カウンタｉＭをｉＭ＝ｉ（Ｍ−１）＋１と初期化する。
但し、Ｍ＝，，−ａである。ここで、対応付け｛（Ａａ，Ｂｉ１），（Ａａ＋１，Ｂｉ２），…，（Ａａ＋ｉＭ，ＢｉＭ）｝を生成する。
【００６６】
ｂ＜ｉ１＜ｉ２＜ｉ３＜…＜ｉＭ＜ｃ
の大小関係を保ったまま、取り得るカウンタの値を求めることによって対応付ける全ての組を生成できる。
【００６７】
次に、ステップ１０６の対応付けの組み合わせの処理について説明する。
【００６８】
図１１は、本発明の一実施の形態における対応付けの組み合わせ処理のフローチャートである。
【００６９】
ステップ１１０１）  区間間対応付け部６において、区間ｘ内対応付けの間の組み合わせを作成する。
【００７０】
区間ｘ内の区間内対応付け候補
Ｒｏｕｔｅ１ｘ，Ｒｏｕｔｅ２ｘ，…，Ｒｏｕｔｅｐｘ＿ｍａｘｘ
から１つの候補を選び、これを、ｘ＝１からｋ＿ｍａｘまでのすべての区間について行い、１つの対応付けＲｑが作成できる。
【００７１】
Ｒｑ＝｛Ｒｏｕｔｅｊ１，Ｒｏｕｔｅｋ２，Ｒｏｕｔｅｌ３，…，Ｒｏｕｔｅｍｋ＿ｍａｘ｝
ここで、Ｒｑは、区間１の経路候補にうち、ｊ番目の候補が選択され、区間２の経路候補のうちｋ番目の候補が選択され、区間３の経路候補のうち、１番目の経路が選択され、・・・、区間ｋ＿ｍａｘの経路候補のうち、ｍ番目の経路が選択されていることを示している。
【００７２】
対応付けＲの構成方法は、区間において、区間内対応付け候補の選び方の数だけ存在するので、
【００７３】
【数１】
2005331612.tif 000003
になるが、これを列挙し、Ｒ１，Ｒ２，…，Ｒｑ，…，ＲＱとする。
【００７４】
ステップ１１０２）  すべてのＲｑ（１≦ｑ≦Ｑ）について、評価を行い、評価値
Ｖｑ＝Ｅ（Ｒｑ）
が基準を満たすものを対応付け候補とする。基準は予め定めた最適なｎ個の対応付けでも構わないし、またＶｑ＞ｔｈの閾値による判定でも構わない。
【実施例】
【００７５】
以下、図面と共に、本発明の実施例を説明する。
【００７６】
本実施例では、野球のスコアブックに記録されているイベント系列（系列Ａ）と映像から音響解析を用いて検出した打球音もしくは捕球音イベント系列（系列Ｂ）との対応付け問題を例に説明する。但し、テニスや卓球などにおいて記録されているイベント系列（系列Ａ）と映像から音響解析を用いて検出した打球音イベント系列（系列Ｂ）とを対応付ける場合にも適用可能である。
【００７７】
さらに、台本から選択した単語の系列（系列Ａ）と映像からキーワードスポッティングで認識した単語の系列（系列Ｂ）とを対応付ける場合にも適用可能である。
【００７８】
前述の実施の形態におけるステップ１０１で、系列Ａ記憶部７から読み込むイベント系列Ａの例を図１２に示す。図１２に示す１つの行が１球のイベントになり、１カラム目にはＩＤ、が、その２カラム目にはストライク・ボール・ヒットなどの１球１球のイベントの結果、３カラム目はそのときにランナーがいるか、いないかのフラグ、４カラム目は、ある打者に関して初球であるか否かのフラグである。また、スコアブックには、時間に関する情報は含まれないので、“ＮＵＬＬ”とする。また、getColumn(m,n)によって、ＩＤ＝ｍのｎカラム目の情報を得ることができる。
【００７９】
前述のステップ１０２で系列Ｂ記憶部８から読み込む、時系列のイベント系列Ｂは、図１３のようになる。ここでは、映像から打球音と捕球音を自動検出し、２カラム目にイベントとして打球音もしくは捕球音、３カラム目はその検出時刻とする。
【００８０】
前述のステップ１０３における系列Ａの分割方法を、図１４を用いて説明する。
【００８１】
ステップ２３０１）  系列Ａ分割部３は、分割のルールＤｉｖ（）を系列Ａ分割ルール記憶部１２から読み込む。
【００８２】
ステップ２３０２）  ｉ＝０と初期化する（ｉは系列Ａのイベントのカウント）。
【００８３】
ステップ２３０３）  ｘ=０と初期化する（ｘは区間のカウント）。
【００８４】
ステップ２３０４）  Ｄｉｖ（ｉ）が１であるか判定する。１であれば、即ち打者の切り替わりのタイミングであるので、ステップ２３０５に移行する。そうでなければ、ステップ２３０６に移行する。
【００８５】
ここで、Ｄｉｖ（ｉ）は系列ＡのgetColumn（ｉ，４）＝１であれば、１を、getColumn（ｉ，４）＝０であれば０を返す関数である。
【００８６】
ステップ２３０５）  ｘをインクリメントする。
【００８７】
ステップ２３０６）  系列Ａのｉ番目のイベントＡｉをＸｘの要素に加える。
【００８８】
ステップ２３０７）  ｉがＮ（Ａ）より大きいか判定し、大きければ終了する。大きくなければステップ２３０８に移行する。
【００８９】
ステップ２３０８）  ｉをインクリメントしてステップ２３０４に移行する。
【００９０】
野球の例では、系列Ａを打席区分に分割した。しかし、打席区分でなくとも、分割されていればよい。テニスや卓球の場合には、１ゲームに分割する方法が考えられるが、複数に分割されていればよい。これらの分割方法は、系列Ａ分割ルール記憶部１２に格納される実施者が作成するルールに依るものである。
【００９１】
上記の図１４のフローチャートの動作を野球に適用すると図１５に示すようになる。
【００９２】
次に、前述のステップ１０４における系列Ｂの選択処理について説明する。
【００９３】
図１６は、本発明の一実施例の系列Ｂ選択処理のフローチャートである。
【００９４】
ステップ２４０１）  系列Ｂ選択部４は、イベント必要時間記憶部１０から系列Ａの１つ１つのイベント必要時間テーブルを読み込む。
【００９５】
野球におけるイベント必要時間テーブルの例を図１７に示す。イベント必要時間テーブルのデータは、スコアブックに記されている、ランナーの有無、及び打席の初球か否かに場合分けて観測的に求めた値である。その観測データを図１８に示す。テニスや卓球についても、ラリーの最中か、サーブか、さらにはゲームの最初であるか、コートチェンジの有無、セットの最初であるか否かなどのケースに分けて、同様の知識を実験的に得ることが可能である。
【００９６】
また、台本中の単語などについても、台本から得られる情報であるモーラ数と、実際に話した場合に必要な時間との関係が指摘されており、台本から必要な最小時間を得ることが可能である。その場合は、１モーラあたりに必要な時間が、イベント必要時間テーブルに記入されている。その例を図１９に示す。
【００９７】
ステップ２４０２）  ｘ＝０と初期化する。
【００９８】
ステップ２４０３）  Ｘ０からＸｘ−１までに必要な最短の時間を、ステップ２４０１で読み込んだイベント必要時間テーブルによる求める。ここで、イベント必要時間テーブルには、シチュエーション毎に、イベントに必要な最短の時間が保持されているため、ステップ２４０３で求める時間Ｓ（Ｘｘ）は、すべてのイベントが考え得る最小の時間で起きた場合に、Ｘｘが始まる時刻である。
【００９９】
ステップ２４０４）  イベント必要時間テーブルを用いて、Ｘｘ＋１からＸｘ＿ｍａｘまでに必要な最短時間（ｍｉｎ）を求め、映像の終了時刻Ｔからｍｉｎを引くことで、Ｘｘを含む可能性のある最終時刻Ｌ（Ｘｘ）とする。
【０１００】
ここで、ｍｉｎは、Ｘｘ以降のイベントが起きるのに必要な最小限の時間であるので、最終時刻Ｌ（Ｘｘ）よりも後の時間には、Ｘｘ中のイベントは含まれない。
【０１０１】
ステップ２４０５）  ｉ＝０と初期化する。
【０１０２】
ステップ２４０６）  Ｘｘ中のイベントＢｉの発生時刻Ｔｉｍｅ（Ｂｉ）が、
Ｓ（Ｘｘ）＜Ｔｉｍｅ（Ｂｉ）＜Ｌ（Ｘｘ）
を満たしていれば、ステップ２４０７へ移行し、そうでなければステップ２４０８に移行する。
【０１０３】
ステップ２４０７）  Ｍ（Ｘｘ）にＢｉを加える（Ｍ（Ｘｘ）は系列Ａ部分列Ｘｘに対応する系列Ｂ部分列）。
【０１０４】
ステップ２４０８）  １＜ｂ＿ｍａｘであれば、ステップ２４０９へ移行し、そうでなければステップ２４１０に移行する。
【０１０５】
ステップ２４０９）  ｉをインクリメントする。
【０１０６】
ステップ２４１０）  ｘ＜ｘ＿ｍａｘであればステップ２４１１へ移行し、そうでなければ処理を終了する。
【０１０７】
ステップ２４１１）  ｘをインクリメントする。
【０１０８】
ここで、ステップ２４０３の開始時刻決定処理について説明する。
【０１０９】
図２０は、本発明の一実施例の開始時刻決定処理のフローチャートである。
【０１１０】
ステップ４１０１）  ｉ＝０、ｍｉｎ＝０と初期化する。
【０１１１】
ステップ４１０２）  系列Ｂ選択部４は、系列Ａ記憶部７から
runner=getComumn（ｉ，３），
firstball=getColumn（ｉ，４）
によってシチュエーション情報を取得する。
【０１１２】
ステップ４１０３）  既に読み込んである、イベント必要時間テーブルの情報から、ステップ４１０２で取得したシチュエーション情報に適する必要時間を取得し、ｍｉｎ＿ｔｍｐにセットする。
【０１１３】
ステップ４１０４）  ｍｉｎにｍｉｎ＿ｔｍｐを加えて、ｍｉｎにセットする。
【０１１４】
ステップ４１０５）  ｉがＩ＿ＭＡＸ（Ｘｘ−１に含まれる最後のイベントのＩＤ）以下であれば、ステップ４１０６へ移行し、そうでなければステップ４１０７に移行する。
【０１１５】
ステップ４１０６）  ｉをインクリメントしてステップ４１０２に移行する。
【０１１６】
ステップ４１０７）  Ｓ（Ｘ）にｍｉｎをセットして当該処理を終了する。
【０１１７】
次に、ステップ２４０４の最終時刻決定処理について説明する。
【０１１８】
図２１は、本発明の一実施例の最終時刻決定処理のフローチャートである。
【０１１９】
ステップ４２０１）  ｉ＝Ｉ＿ＭＩＮ（Ｘｘ＋１に含まれる最初のイベントのＩＤ，ｍｉｎ＝０と初期化する。
【０１２０】
ステップ４２０２）  系列Ｂ選択部４は、系列Ａ記憶部７から
runner=getComumn（ｉ，３），
firstball=getColumn（ｉ，４）
によってシチュエーション情報を取得する。
【０１２１】
ステップ４２０３）  既に読み込んである、イベント必要時間テーブルの情報から、ステップ４２０２で取得したシチュエーション情報に適する、必要時間を取得し、ｍｉｎ＿ｔｍｐにセットする。
【０１２２】
ステップ４２０４）  ｍｉｎにmin_ｔｍｐを加えて、ｍｉｎにセットする。
【０１２３】
ステップ４２０５）  ｉがＩ＿ＭＡＸ（Ｘｘ＿ｍａｘに含まれる最後のイベントのＩＤ）以下であれば、ステップ４２０６へ移行し、そうでなければステップ４２０７に移行する。
【０１２４】
ステップ４２０６）  ｉをインクリメントしてステップ４２０２に移行する。
【０１２５】
ステップ４２０７）  Ｌ（Ｘ）にＴ−ｍｉｎをセットして終了する。但し、Ｔは映像の長さである。
【０１２６】
なお、上記のステップ２３０３及びステップ２３０４の操作は、イベント時間テーブルを置き換えることにより、テニス、卓球の打球音とスコアとの対応付け、あるいは、台本と映像との対応付けなどに利用可能である。
【０１２７】
テニス・卓球等の打球音を伴うスポーツでは、１打１打の記録が記載されている場合と、得点経過のみが記載されている場合において、それぞれのイベントの必要時間テーブルの設定をそれぞれ変化させて適用することが可能である。例えば、１打１打が記録されている場合には、図２２に示すような必要時間テーブルの設定となり、得点経過のみ記載されている場合は、図２３に示すような設定となる。
【０１２８】
また、本発明を台本と映像との対応付けに適用する場合は、系列Ａを台本からわかる話し手の切り替わりとし、系列Ｂを話者認識技術によって得られる話者の切り替わりとして適用可能である。
【０１２９】
上記の図７〜図１１、図１４、図１５、図２０、図２１に示す動作をプログラムとして構築し、系列対応付け装置として利用されるコンピュータにインストールし、ＣＰＵ等の制御手段により実行させる、または、ネットワークを介して流通させることが可能である。
【０１３０】
なお、本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１３１】
本発明は、シナリオと映像や、野球、テニス、卓球等のスポーツの映像と観測データとを対応付ける技術に適用可能である。
【図面の簡単な説明】
【０１３２】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態における対応付け装置の構成図である。
【図４】本発明の一実施の形態における系列Ａ記憶部の情報の例である。
【図５】本発明の一実施の形態における系列Ｂ記憶部の情報の例である。
【図６】本発明の一実施の形態における対応付け記憶部の格納例である。
【図７】本発明の一実施の形態における全体のフローチャートである。
【図８】本発明の一実施の形態における系列分割処理のフローチャートである。
【図９】本発明の一実施の形態における系列選択処理のフローチャートである。
【図１０】本発明の一実施の形態における全探索による対応付け処理のフローチャートである。
【図１１】本発明の一実施の形態における対応付け組み合わせ処理のフローチャートである。
【図１２】本発明の一実施例のイベント系列Ａの例である。
【図１３】本発明の一実施例のイベント系列Ｂの例である。
【図１４】本発明の一実施例の系列Ａの分割方法のフローチャートである。
【図１５】本発明の一実施例の系列Ｂ選択処理のフローチャートである。
【図１６】本発明の一実施例の系列Ｂ選択処理を野球に適用した例を示す図である。
【図１７】本発明の一実施例のイベント必要時間テーブルである。
【図１８】本発明の一実施例のイベント必要時間テーブルを作成するための観測データの例である。
【図１９】本発明の一実施例の台本から得られるイベント必要時間テーブルである。
【図２０】本発明の一実施例の開始時刻決定処理のフローチャートである。
【図２１】本発明の一実施例の最終時刻決定処理のフローチャートである。
【図２２】本発明の一実施例のイベント必要時間テーブルの例（１打１打が記載されている場合）である。
【図２３】本発明の一実施例のイベント必要時間テーブルの例（得点経過のみ記載されている場合）である。
【符号の説明】
【０１３３】
１  系列Ａ読み込み手段、系列Ａ読み込み部
２  系列Ｂ読み込み手段、系列Ｂ読み込み部
３  系列Ａ分割手段、系列Ａ分割部
４  系列Ｂ選択手段、系列Ｂ選択部
５  区間内対応付け手段、区間内対応付け部
６  区間間対応付け手段、区間間対応付け部
７  系列Ａ記憶手段、系列Ａ記憶部
８  系列Ｂ記憶手段、系列Ｂ記憶部
９  系列Ａ分割ルール記憶手段、系列Ａ分割ルール記憶部
１０  イベント必要時間記憶手段、イベント必要時間記憶部
１１  対応付け記憶手段、対応付け記憶部
【図１】
2005331612.tif 000004
【図２】
2005331612.tif 000005
【図３】
2005331612.tif 000006
【図４】
2005331612.tif 000007
【図５】
2005331612.tif 000008
【図６】
2005331612.tif 000009
【図７】
2005331612.tif 000010
【図８】
2005331612.tif 000011
【図９】
2005331612.tif 000012
【図１０】
2005331612.tif 000013
【図１１】
2005331612.tif 000014
【図１２】
2005331612.tif 000015
【図１３】
2005331612.tif 000016
【図１４】
2005331612.tif 000017
【図１５】
2005331612.tif 000018
【図１６】
2005331612.tif 000019
【図１７】
2005331612.tif 000020
【図１８】
2005331612.tif 000021
【図１９】
2005331612.tif 000022
【図２０】
2005331612.tif 000023
【図２１】
2005331612.tif 000024
【図２２】
2005331612.tif 000025
【図２３】
2005331612.tif 000026