(57)【要約】【課題】同一タイムコードや、不連続なタイムコードが存在している記録領域においても、映像信号を正確に検索する。【解決手段】タイムコード分布の分割により検索用２分木を生成し、タイムコードを２分木の節点に保持する。指定されたタイムコードを２分検索により正確かつ効率的に検索し、タイムコードに対応する映像信号を記録領域より呼び出し出力する。指定されたタイムコードを持つ映像が複数存在しても、検索用２分木を端点まで検索することにより前記タイムコードを持つ全ての映像を検索する。【選択図】図１
2008287544.tif 000002
【特許請求の範囲】
【請求項１】
映像信号と相関するタイムコードを記録した領域から所望の映像信号を検索する映像信号検索方法において、所望の映像信号に相関するタイムコードが指定され、前記タイムコードに対応する映像信号を、検索用２分木を用いて記録領域から検索することを特徴とする映像信号検索方法。
【請求項２】
指定されたタイムコードを持つ映像が複数存在しても、前記検索用２分木を最後の節点まで検索することにより前記タイムコードを持つ全ての映像を検索できることを特徴とする請求項１記載の映像信号検索方法。
【請求項３】
タイムコードの分布を中間から分割し、２つのタイムコードグループに分け、さらにタイムコードのグループを分割が出来なくなるまで繰り返し、検索用２分木を生成することを特徴とする検索用２分木生成方法。
【請求項４】
タイムコードを連続する期間でグループ分けを行い、タイムコードを分割する時に連続するタイムコードの始点または終点のタイムコードの値のみで分割を行い、前記検索用２分木の高さを押さえることで検索効率の高い２分木を生成することを特徴とする請求項３記載の検索用２分木生成方法。
【請求項５】
記録領域にデータが追加または削除されるたびに前記検索用２分木を再生成することを特徴とする請求項３記載の検索用２分木生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、不連続なタイムコードが存在する映像信号、記録位置とタイムコードの大小関係が一致しない映像信号及び同一タイムコードが複数存在する映像信号においても、所望の映像信号を正確に検索することができる映像信号検索方法、及び検索用２分木生成方法に関する。
【背景技術】
【０００２】
従来より、検索するタイムコードと現在のタイムコードとを比較して、検索するタイムコードが現在のタイムコードより大きい場合には順方向に、小さい場合は逆方向に、現在の映像信号のアドレスから所望のタイムコードが見つかるまで検索する方法が知られている。また、指定された所望の映像信号の記録位置に対応するタイムコードに相関する位置情報を読み出し、読み出した当該位置情報に基づき所望の映像信号を順次検索する方法が知られている（例えば、特許文献１参照。）。
【特許文献１】特開２００３−１１６０９１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、従来のタイムコードを用いた映像信号の検索方法では、不連続なタイムコードが存在する映像信号や、記録位置とタイムコードの大小関係が一致しない映像信号では、所望の映像信号を検索することができないという問題点があった。またタイムコードを映像信号の始点のフレームから順次検索していくため、Ｎフレームの映像信号から所望のフレームを検索する時には、検索回数のオーダはＯ（Ｎ）になり、検索効率が悪い。
【０００４】
このような課題に鑑みて本発明は、不連続なタイムコードが存在する映像信号、記録位置とタイムコードの大小関係が一致しない映像信号及び同一タイムコードが複数存在する映像信号においても、映像信号を正確かつ効率的に検索することができる映像信号検索方法を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の映像信号検出方法は前記課題を解決するために、タイムコード分布の分割により検索用２分木を生成し、タイムコードを２分木の節点に保持する。指定されたタイムコードを２分検索により正確かつ効率的に検索し、タイムコードに対応する映像信号を記録領域より呼び出し出力する。指定されたタイムコードを持つ映像が複数存在しても、検索用２分木を端点まで検索することにより前記タイムコードを持つ全ての映像を検索する。タイムコードの分布を中間から分割し、２つのタイムコードグループに分ける。さらに前記タイムコードのグループを分割が出来なくなるまで、分割を繰り返し、検索用２分木を生成する。
【０００６】
タイムコードの分布を中間で分割することにより、検索用２分木は完全２分木に近づき、検索効率が向上する。またタイムコードを連続する期間にグループ分けを行い、２分木に分割する対象数を減らすことで、２分木の高さを抑え、検索効率を向上する。
【発明の効果】
【０００７】
本発明の映像信号検索方法は、タイムコードと映像信号の情報を保持した検索用２分木から指定されたタイムコードに対応する映像信号を検索する。これにより本発明は、同一タイムコードや、不連続なタイムコードが存在している映像信号においても、映像信号を正確に検索することができる。
【０００８】
本発明の検索用２分木生成方法はタイムコードの分布を中間で分割することにより、検索用２分木は完全２分木となりタイムコードの検索回数は映像信号のフレーム数ＮとするとＯ（ｌｏｇ2Ｎ）となり従来の検索方法の最悪の場合のＯ（Ｎ）に対し、検索効率が向上する。
【０００９】
またタイムコードをＭ個のグループに分けた場合はタイムコードの検索回数はＯ（ｌｏｇ2Ｍ）となり、さらに検索効率が向上する。
【発明を実施するための最良の形態】
【００１０】
以下、本発明の形態について図面を参照しながら詳細に説明する。
【００１１】
（検索手段）
検索用２分木を用いた映像信号検索方法を、一秒間で３０フレームのシステムの例を用いて説明する。記録領域の映像信号が図１に示すタイムコードに対応している時、検索用２分木生成手段により図２に示す検索用２分木を生成する。
【００１２】
図２に示す白色の節点はタイムコードの分布を大小に分けるタイムコードの値を持った検索用２分木の節点である。灰色の節点は連続するタイムコードの映像信号を持つ検索用２分木の節点である。検索用２分木の節点の左側には遅いタイムコードを持つ節点、右側には早いタイムコードを持つ節点が接続される。
【００１３】
指定されたタイムコードと白色の節点に保持されているタイムコードの値を比較し、検索用２分木を走査していく。白色の節点を走査していき、映像信号を含む灰色の節点に到達すれば、その節点に所望の映像信号へのアドレスがある。映像信号へのアドレスより記録領域から映像信号を呼び出し、検索を終了する。
【００１４】
図１に示す検索キーとなるタイムコードＴＣ  Ｘ“１０：１５：００：００”に対応する映像を検索する例を用いて検索方法の詳細を説明する。図２の検索用２分木の始めの節点ＴＣ２が持つタイムコードＴＣ２  “１０：１２：００：００”とタイムコードＴＣ  Ｘを比較し、ＴＣ２より大きいので２分木の右側の節点ＴＣ４に移動する。タイムコードＴＣ  ＸはタイムコードＴＣ４より小さいのでＴＣ４の左側の節点Ｂに移動する。節点Ｂは映像信号を持つ節点なので、この節点に所望の映像があることがわかる。
【００１５】
また映像は連続している事から、節点Ｂの始点のタイムコードＴＣ２とタイムコードＴＣ  Ｘの差００：０３：００：００より、所望の映像が節点Ｂの始点の映像１８，０００フレームから５，４００フレーム後の２３，４００フレームにあるのが分かる。さらに節点Ｂの次に節点Ｄがある事から節点Ｄにも所望の映像信号がある事がわかり、同じように節点Ｄの始点の映像４６，８００フレームから５，４００フレーム後の５２，２００フレームに所望の映像がある事が分かる。節点Ｄの次は節点がないＮＵＬＬなので、検索を終了する。
【００１６】
図２に示す検索用２分木の場合、６１，２００フレームの中から任意のフレームを検索する時、最悪の場合でも４回の走査で完了する。
【００１７】
（検索用２分木生成手段）
検索用２分木の生成手段の詳細を説明する。検索用２分木を完全２分木にするために、検索用２分木生成手段はタイムコードの分布を中間で分割しタイムコードの大小で検索用２分木の節点に振り分けていく。タイムコードの分布の分割は分割されたタイムコードの分布にも再帰的に行われ、タイムコードの分布が分割できなくなるまで行う。
【００１８】
（２分木の構成）
２分木の節点は映像信号への情報を持つ構造体より構成されている。図３に構造体の例を示す。構造体は以下の情報により構成されている。
・連続したタイムコードの映像期間の最初のタイムコードを保持するＨＥＡＤ  ＴＣ
・連続したタイムコードの映像期間の最後のタイムコードを保持するＥＮＤ  ＴＣ
・タイムコードＨＥＡＤ  ＴＣに対応する映像信号のアドレスＨＥＡＤ  ＶＩＤＥＯ
・本構造体より小さいタイムコードを保持する構造体のアドレスＳＭＡＬＬ  ＰＯＩＮＴＥＲ
・本構造体より大きいタイムコードを保持する構造体のアドレスＬＡＲＧＥ  ＰＯＩＮＴＥＲ
・本構造体と同じ大きさのタイムコードを保持する構造体のアドレスＥＱＵＡＬ  ＰＯＩＮＴＥＲ
図３の構造体は図４の連続するタイムコードのグループＢの構造体を示す。
【００１９】
前記構造体はＨＥＡＤ  ＴＣに１０：１２：００：００、ＥＮＤ  ＴＣに１０：２０：００：００を保持し、ＨＥＡＤ  ＶＩＤＥＯはフレームへのアドレス１８，０００を保持する。
【００２０】
ＳＭＡＬＬ  ＰＯＩＮＴＥＲにはグループＢより小さいタイムコードのグループＡへのアドレスＡが入力され、ＬＡＲＧＥ  ＰＯＩＮＴＥＲ、  ＥＱＵＡＬ  ＰＯＩＮＴＥＲはそれぞれグループＣへのアドレス、グループＤへのアドレスが入力される。
【００２１】
（２分木生成手段の詳細）
図５のタイムコードを用いて、検索用２分木生成手段の詳細を説明する。タイムコードが連続し単調増加する期間でグループ分けを行う。図５の場合、Ａ、Ｂ、Ｃ、Ｄ、Ｅの五個のグループが生成される。完全２分木に近い２分木を生成するために、タイムコード全体をタイムコードの分布の中間で分割する。無駄な分割を避けるためにタイムコードの分割は前記グループの始点または終点のタイムコードの値で行う。図５のタイムコード分布の場合、グループＥの最初のタイムコードＴＣ０でタイムコード全体の分割を行う。
【００２２】
図６に分割後のタイムコードを示す。タイムコード全体はＴＣ０より小さいグループと大きいグループに分割される。グループＡはタイムコードＴＣ０を含むので、グループＡはタイムコードＴＣ０より小さいタイムコード期間と大きいタイムコード期間に分割され、それぞれグループＡ１、Ａ２となる。分割に使われたタイムコードＴＣ０を保持する節点ＮＯＤＥ  ＴＣ０が生成され、ＨＥＡＤ  ＴＣ、ＥＮＤ  ＴＣにはタイムコードＴＣ０を入力し、その他の変数にはＮＵＬＬを入力する。節点ＮＯＤＥ  ＴＣ０は検索用２分木の初めの節点ＲＯＯＴとして定義される。
【００２３】
図７に節点ＮＯＤＥ  ＴＣ０の構造体と検索用２分木を示す。同じように分割されたタイムコードのグループをタイムコードの分布の中間で分割し、２分木を作成していく。タイムコードＴＣ０より小さいグループＡ１、Ｂ、Ｄのタイムコード分布を中間で分割する。
【００２４】
図８に示すように、最も中間値に近いグループＡ１の始点のタイムコードＴＣ１を選び、タイムコード  ＴＣ１の値でグループＡ１、Ｂ、Ｄのタイムコードを分割する。グループＢ、ＤはタイムコードＴＣ１を含んでいるので、タイムコードＴＣ１より小さいグループＢ１、Ｄ１と大きいグループＢ２、Ｄ２に分割される。節点ＮＯＤＥ  ＴＣ１を生成し、ＨＥＡＤ  ＴＣ、  ＥＮＤ  ＴＣにタイムコードＴＣ１を入力する。節点ＮＯＤＥ  ＴＣ０のＳＭＡＬＬ  ＰＯＩＮＴＥＲにＴＣ１のアドレスを入力する。同じように、タイムコードＴＣ１より小さいグループＢ１、Ｄ１のタイムコード分布を中間で分割する。
【００２５】
図８に示すように、グループＢ１のＨＥＡＤ  ＴＣ、ＴＣ２を選択しグループＢ１、Ｄ１を分割する。この時グループＤ１はＴＣ２を含んでいるため、タイムコードＴＣ２より小さいグループＤ１と大きいグループＤ１−２に分割する。節点ＮＯＤＥ  ＴＣ２を作成し、ＨＥＡＤ  ＴＣ、  ＥＮＤ  ＴＣにタイムコードＴＣ２を入力する。節点ＮＯＤＥ  ＴＣ１のＳＭＡＬＬ  ＰＯＩＮＴＥＲにＮＯＤＥ  ＴＣ２のアドレスを入力する。
【００２６】
このときの検索用２分木を図９に示す。ＴＣ２より小さいグループはＤ１のみなので、節点ＮＯＤＥ  Ｄ１を作成し、ＨＥＡＤ  ＴＣ、  ＥＮＤ  ＴＣにグループＤ１のタイムコードの始点、終点の値を入力し、ＨＥＡＤ  ＶＩＤＥＯにはＨＥＡＤ  ＴＣに対応する映像信号へのアドレスを入力し、その他の変数にはＮＵＬＬを入力する。節点ＮＯＤＥ  ＴＣ２のＳＭＡＬＬ  ＰＯＩＮＴＥＲにＮＯＤＥ  Ｄ１のアドレスを入力する。ＴＣ２より大きいグループＢ１、  Ｄ１−２はこれ以上分割できないので、節点ＮＯＤＥ  Ｂ１、ＮＯＤＥ  Ｄ１−２を生成し、タイムコード、映像信号のアドレスをそれぞれの変数に入力する。
【００２７】
節点ＮＯＤＥ  ＴＣ２のＬＡＲＧＥ  ＰＯＩＮＴＥＲに節点ＮＯＤＥ  Ｂ１のアドレスを入力し、ＮＯＤＥ  Ｂ１のＥＱＵＡＬ  ＰＯＩＮＴＥＲに節点ＮＯＤＥ  Ｄ１−２のアドレスを入力する。節点ＮＯＤＥ  Ｂ１、ＮＯＤＥ  Ｄ１−２のその他の変数にはＮＵＬＬを入力する。
【００２８】
以上を全てのタイムコードグループが分割できなくなるまで繰り返し、検索用の２分木を構築していく。
【００２９】
図１０に図５のタイムコードを分割した結果と図１１に完成した検索用２分木を示す。
【００３０】
以上説明したように、本発明の映像信号検索方法は、タイムコードと映像信号の情報を保持した検索用２分木から指定されたタイムコードに対応する映像信号を検索する。これにより本発明は、同一タイムコードや、不連続なタイムコードが存在している映像信号においても、映像信号を正確に検索することができる。
【００３１】
本発明の検索用２分木生成方法はタイムコードの分布を中間で分割することにより、検索用２分木は完全２分木となりタイムコードの検索回数は映像信号のフレーム数ＮとするとＯ（ｌｏｇ2Ｎ）となり従来の検索方法の最悪の場合のＯ（Ｎ）に対し、検索効率が向上する。
【００３２】
またタイムコードをＭ個のグループに分けた場合はタイムコードの検索回数はＯ（ｌｏｇ2Ｍ）となり、さらに検索効率が向上する。
【産業上の利用可能性】
【００３３】
本発明の映像信号検索方法は、同一タイムコードや、不連続なタイムコードが存在している記録領域においても、映像信号を正確に検索することがきるため、映像編集装置等にも適用可能である。
【図面の簡単な説明】
【００３４】
【図１】検索手段を説明するためのタイムコードとフレームの関係を示す図
【図２】複数映像が検索された時の、映像の選択方法を説明するための図
【図３】検索用２分木を構成する構造体を説明するための図
【図４】検索用２分木を構成する構造体を説明するためのタイムコードとフレームの関係を示す図
【図５】検索用２分木生成手段を説明するためのタイムコードとフレームの関係を示す図
【図６】検索用２分木生成手段を説明するための図５のタイムコードの分割後のタイムコードとフレームの関係を示す図
【図７】検索用２分木の始めの節点ＲＯＯＴを説明するための図
【図８】検索用２分木生成手段を説明するための図６のタイムコードの分割後のタイムコードとフレームの関係を示す図
【図９】検索用２分木生成手段を説明するための図８のタイムコードとフレームを保持する２分木を示す図
【図１０】検索用２分木生成後のタイムコード分割完了後のタイムコードとフレームの関係を示す図
【図１１】生成された検索用２分木を示す図
【符号の説明】
【００３５】
ＴＣ０〜ＴＣ５  タイムコード
ＴＣ  Ｘ  検索キーとなるタイムコード
Ａ、Ｂ、Ｃ、Ｄ、Ｅ  タイムコードのグループ
【図１】
2008287544.tif 000003
【図２】
2008287544.tif 000004
【図３】
2008287544.tif 000005
【図４】
2008287544.tif 000006
【図５】
2008287544.tif 000007
【図６】
2008287544.tif 000008
【図７】
2008287544.tif 000009
【図８】
2008287544.tif 000010
【図９】
2008287544.tif 000011
【図１０】
2008287544.tif 000012
【図１１】
2008287544.tif 000013