映像ナビゲーション方法、映像ナビゲーションシステム、及び映像ナビゲーションプログラム
【課題】ディスプレイ装置上で、特に小型ディスプレイ装置上で、映像ショットのナビゲーションを自動的に可能にするための、より良いプロセスを提供する。
【解決手段】映像ショットにセグメンテーションされた映像に対して、限定された画面サイズであり且つキーフレームより大きな画面サイズを有するディスプレイ装置上でキーフレームを表示する映像ブラウザを用いて映像のナビゲーションを可能にするコンピュータを用いた映像ナビゲーション方法であって、映像ショットの時間的な順序を維持しながら、映像ショットを類似性によってクラスタリングし、ツリーの経路長を最小限に抑えながら、映像ショットのクラスタに対して階層的に組織化されたナビゲーションツリーを生成する。
【解決手段】映像ショットにセグメンテーションされた映像に対して、限定された画面サイズであり且つキーフレームより大きな画面サイズを有するディスプレイ装置上でキーフレームを表示する映像ブラウザを用いて映像のナビゲーションを可能にするコンピュータを用いた映像ナビゲーション方法であって、映像ショットの時間的な順序を維持しながら、映像ショットを類似性によってクラスタリングし、ツリーの経路長を最小限に抑えながら、映像ショットのクラスタに対して階層的に組織化されたナビゲーションツリーを生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ディスプレイ装置における映像ブラウザに関し、詳しくは、時間的に順序付けられた映像キーフレームの類似性に基づくナビゲーション階層を用いて短いナビゲーション経路によりディスプレイ装置上でリニア映像をナビゲートするための映像ナビゲーション方法、映像ナビゲーションシステム、及び映像ナビゲーションプログラムに関する。
【背景技術】
【０００２】
ユーザがディスプレイ装置上で映像を再生する時は、映像における特定のシーンにアクセスすることが望ましい。ディスプレイ装置上のナビゲーション支援機能（navigation aid）は、ユーザが、所望のシーンまで映像をナビゲートすることを可能にする。ディジタル・ビデオ・ディスク（ＤＶＤ）の場合、ＤＶＤは、記憶されている映像のシーンインデクスをキーフレームの形態でユーザに与える。一方、大部分の自動的に生成されるナビゲーション支援機能では、映像におけるシーンを自動的に検出することが困難なため、シーンの代わりにショットが用いられる。ショットは、シーンよりはるかに短いため、これは、はるかにより大きな数（一般に映像の毎分に対して１０個以上）のキーフレームを生じる。テレビジョン画面又はコンピュータ画面などの画面上に数個のキーフレームを表示するＤＶＤ手法では、ある特定のショットにアクセスしたい場合、数百個のキーフレームまでスケールアップしてはくれない。各画面上に数個のキーフレームを表示する余地しかない携帯電話などの小型の装置では、状況はさらに悪い。
【０００３】
さらに、映像をナビゲートするための大部分のインタフェースは、特別に設計されたリモコン（例えば、ＴＩＶＯリモコン）又はマウスのどちらかに依存する。携帯電話のように小型ディスプレイを備え且つマウスを備えていない装置上では、映像についての情報を提供するスペースが制限され、ユーザ入力のオプションが限定されているため、映像をナビゲートするのは困難である。
【０００４】
【非特許文献１】AN,C.-H.,et al.,"Fractal Image Compression by Improved Balanced Tree Clustering,"Proceedings of SPIE, Volume 3164, Apprications of Digital Image Processing XX, pages 554-562(1997).
【０００５】
【非特許文献２】GEVA,S.,"K-Tree: A Height Balanced Tree Structured Vector Quantizer,"Proceedings of the 2000 IEEE Signal Processing Society Workshop, Volume 1,pages 271-280(2000).
【０００６】
【非特許文献３】GIRGENSOHN,A.,et al.,"Home Video Editing Made Easy-Balancing Automation and User Control,"Proceedings of Human-Computer Interaction(INTERACT'01),IOS Press, Tokyo,Japan, 8 pages(2001).
【０００７】
【非特許文献４】ZHANG,T.,"BIRCH: An Efficient Data Clustering Method for Very Large Databases,"Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Canada,pages 103-114(1996).
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、ディスプレイ装置上で、特に小型ディスプレイ装置上で、映像ショットのナビゲーションを自動的に可能にするための、より良いプロセスを提供することにある。
【課題を解決するための手段】
【０００９】
上記目的を達成するために請求項１に記載の発明は、映像ショットにセグメンテーションされた映像に対して、限定された画面サイズであり且つキーフレームより大きな画面サイズを有するディスプレイ装置上でキーフレームを表示する映像ブラウザを用いて映像のナビゲーションを可能にするコンピュータを用いた映像ナビゲーション方法であって、前記方法は、前記映像ショットの時間的な順序を維持しながら、前記映像ショットを類似性によってクラスタリングする工程と、前記ツリーの経路長を最小限に抑えながら、前記映像ショットのクラスタに対して階層的に組織化されたナビゲーションツリーを生成する工程と、含むことを特徴としている。
【００１０】
請求項９に記載の発明は、映像ショットにセグメンテーションされた映像に対して限定された画面サイズを有するディスプレイ装置上でキーフレームを表示する映像ブラウザを用いて映像のナビゲーションを可能にする映像ナビゲーションシステムであって、前記システムは、前記映像ショットの時間的な順序が維持されながら、類似性によってクラスタリングされた映像ショットを取得するクラスタリング手段と、前記ツリーの経路長が最小限に抑えられながら、前記クラスタリングされた映像ショットから階層的に組織化されたナビゲーションツリーを生成するツリー生成手段と、を含むことを特徴としている。
【００１１】
請求項１７に記載の発明は、映像ショットにセグメンテーションされた映像に対して限定された画面サイズを有するディスプレイ装置上でキーフレームを表示する映像ブラウザを用いて映像のナビゲーションを可能にするための映像ナビゲーションプログラムであって、コンピュータを、前記映像ショットの時間的な順序が維持されながら、類似性によってクラスタリングされた映像ショットを取得するクラスタリング手段、及び、前記ツリーの経路長が最小限に抑えられながら、前記クラスタリングされた映像ショットから階層的に組織化されたナビゲーションツリーを生成するツリー生成手段、として機能させるための映像ナビゲーションプログラムであることを特徴としている。
【発明の効果】
【００１２】
本発明によれば、映像ショットにセグメンテーションされた映像に対して、限定された画面サイズを有するディスプレイ装置上で、キーフレームを表示する映像ブラウザを用いた映像のナビゲーションを可能にするためのコンピュータを用いた方法が、提供されている。映像ショットは、映像ショットの時間的な順序が維持されながら、類似性によってクラスタリングされる。映像ショットのクラスタに対して、ツリーの経路長が最小限に抑えられながら、階層的に組織化されたナビゲーションツリーが生成される。
【発明を実施するための最良の形態】
【００１３】
以下、図面を参照して本発明の実施の形態の一例を詳細に説明する。
【００１４】
＜I．前書き＞
映像ディスプレイ装置用のナビゲーション支援機能は、ショットをショットの階層にクラスタリングする工程を含むことができる。クラスタリングは、異なるグループへのオブジェクトの分類である。階層処理は、以前に確立したクラスタを用いて、連続的なクラスタを見出す。凝集型の階層クラスタリングは、別々のクラスタとしての各要素から始まり、それらを連続的により大きなクラスタに併合する「ボトムアップ」クラスタリング手法である。凝集型の階層クラスタリングは、時間的な順序を維持するクラスタリングツリーを生成するのに最適である。次にどのクラスタを併合すべきかを決定する時は、クラスタの全ての対を考慮するのではなく、時間的に隣接しているクラスタの対のみを考慮する。これはクラスタリング処理の時間複雑度を大幅に減少させる。
【００１５】
別の種類の階層クラスタリングは、「トップダウン」クラスタリングである。これは、セット全体から始まり、それを連続的により小さいクラスタに分割してゆく。しかしながら、トップダウンクラスタリング手法（例えばｋ平均法）は、時間的な順序を維持するには、それほど最適ではない。一方、トップダウンクラスタリング手法は、バランスの取れたツリーを生成するように適用することができる。バランスの取れたツリーは、その高さができるだけ小さく保たれたツリーである。ツリーの高さは、根ノードから葉ノードまでの最も長い経路である。単一のノードを有するツリーは「１」の高さを有している。
【００１６】
現在、汎用されている凝集型の階層クラスタリング処理は、時間的な順序によるもので、クラスタにおける要素数を制限しない。これは、結果として、バランスの取れていないクラスタツリーを生成する。他の汎用されている処理は、クラスタリングとバランスの取れたツリーとを組み合わせているが、トップダウンクラスタリング処理専用で、時間的な順序は維持されない。
【００１７】
本発明は、クラスタの要素数を制限するため、ボトムアップクラスタリング手法をトップダウン処理と組み合わせて使用している。完全なクラスタリングツリーを生成するのではなく、このクラスタリング処理は、クラスタツリーの各レベルを別々に処理し、凝集型の階層クラスタリングによって生成されるツリー構造を使用しない。
【００１８】
携帯電話又は他の小型ディスプレイ装置上において、リニア映像内のナビゲーションを可能にする設計が提供されている。映像は、映像ショットに分割され、映像ショットの階層にセグメンテーションされる。この設計は、画面の階層を提供する。各画面は、キーフレームのグリッドを含んでおり、これらのキーフレームの各々は、１つ又はそれ以上のショットのいずれかを表わしている。キーフレームは、映像ショットにおける一時点のフレーム又はスナップショットである。グリッドの要素が、ショットのグループを表わしている時は、グループにおける最も重要なショット及びグループにおける第１のショットの両方が示されており、ショットのグループは、ツリーをナビゲートすることによって到達することができる。
【００１９】
タイムラインは、目に見えるグリッド内の要素のそれぞれと関連した映像の部分を示す。ユーザは、階層的にグループ化されているショットをナビゲートして、映像を再生するための出発点を選択する。ユーザのナビゲーションを助けるため、映像ショットは、時間的な順序に保たれ、視覚的な類似性によってクラスタリングされている。類似性によるクラスタリングは、全映像ショットへの短いナビゲーション経路を保証するため行なわれる。類似性によるクラスタリングは、ナビゲーション経路の長さに対する制約があると、同様の映像ショットを一緒にグループ化することができない場合があるので、近似である。
【００２０】
このようなツリーは、ショットの時間的な順序を維持しつつ、ユーザに予測できるナビゲーションを与えることが望ましい。非常に長いナビゲーション経路を回避するため、ある程度バランスの取れたツリーを有することも望ましい。ショットは、視覚的な類似性などの基準によってグループ化されて、ユーザが、ナビゲーション経路を選択するのをより容易にすべきである。
【００２１】
ショットを時間的な順序に保つという要件は、視覚的な類似性などのクラスタリング基準を用いる場合、非常にバランスの悪いクラスタツリーを生ずる場合がある。一方、視覚的な類似性にもっぱら基づき、時間的な制約に基づかないクラスタツリーは、一般に、よりバランスの取れたものであるが、ユーザに同じ予測性を与えない。本発明は、時間的な順序を維持しながら、ある程度バランスの取れたツリーを生成し、その平均ナビゲーション経路長は、バランスの取れたツリーにおける経路長よりもわずかに長いだけである、ショット類似性の尺度に基づく階層クラスタリング手法を記述する。
【００２２】
＜II．技術的な詳細＞
図１は、本発明の実施形態による映像ショットの階層例１００を示す。この例では、３９個の映像ショットが「階層構造」即ち「ツリー」に組織化されている。映像ショットは、ツリーの葉におけるキーフレームによって表わされている。これらの葉は、ツリーにおいて、７個のクラスタにグループ化されている。クラスタ１１０は、葉のうちの４枚、即ち、映像ショット１１１〜１１４を含んでいる。５個のクラスタ１２１〜１２５の各々は、６枚の葉、即ち、６個の映像ショットを含んでいる。クラスタ１４０は、５枚の葉、即ち、映像ショット１４１〜１４５を含んでいる。
【００２３】
クラスタ１４０の左上のコーナーにおける映像要素１５０は、映像ショットを表すキーフレームである。このキーフレーム上にオーバーレイ（重ねて表示）されている第二のキーフレーム１５１、即ち、ピクチャー・イン・ピクチャー（親画面上に子画面が表示された画像）は、クラスタ１１０における４個の映像ショット１１１〜１１４を代表する（represent）。このレプリゼンテーションは、「４セグメント」と標識が付いている枝１５５又はショットで示されている。この例におけるピクチャー・イン・ピクチャーは、クラスタ１１０における映像ショットの第１のキーフレーム１１１を示している。このように、ツリーは、枝１５５を介して、映像要素１５０からクラスタ１１０における葉まで、降りてゆくことができる。
【００２４】
クラスタ１６０は、ツリーの根である。クラスタ１６０は、６個の映像要素１６１〜１６６を含んでいる。これらの映像要素の各々は、ピクチャー・イン・ピクチャー要素であり、ツリーのより下層の映像ショットのクラスタを代表している。これらのレプリゼンテーションは、枝１７１〜１７６によって示されている。枝１７１には、クラスタ１４０における５個の映像ショット１４１〜１４５と、クラスタ１１０における４個の映像ショットとに対して、「９セグメント」の標識が付いている。枝１７１〜１７６には、各々、クラスタ１２１〜１２６の各々における６個の映像ショットに対して、「６セグメント」の標識が付いている。このように、ツリーは、枝１７１〜１７６を介して、映像要素１６１〜１６６から、クラスタ１４０における映像要素及びその葉まで、及びクラスタ１２１〜１２５における葉まで、降りてゆくことができる。
【００２５】
図１におけるツリーの例は「３」の高さを有している。即ち、クラスタ１６０は第１の階層レベルに在り、クラスタ１１０は第３の階層レベルに在り、また、他のクラスタは第２の階層レベルに在る。また、このツリーは「６」の分岐係数（branching factor）を有している。即ち、ツリーにおける各クラスタは、各要素が、ピクチャー・イン・ピクチャー要素か映像ショット要素か否かに拘わらず、６個以上の要素を含むことができない。
【００２６】
図２〜図４は、ユーザが、図１に示した映像ショットの階層をナビゲートする際に生ずる絞り込みフォーカス（narrowing focus）を示す。
【００２７】
図２は、図１における階層の根として示される全体の映像１６０を表わす、本発明の実施形態に係る映像ブラウザの設計例を示す。設計（design）は、２×３グリッドの映像要素を含んでいる。映像要素のレイアウトは、映像全体を表わしている。これら６個の映像要素１６１〜１６６は、図１のクラスタ１６０、即ち、ツリーの根に由来する。映像要素は、映像ショットを代表するキーフレームとすることができる。また、映像要素は、映像ショットの別のクラスタを代表するピクチャー・イン・ピクチャーとすることができる。及び／又は、映像要素は、ツリーのより下層のピクチャー・イン・ピクチャー要素とすることができる。この例では、６個の映像要素は、ピクチャー・イン・ピクチャー要素である。
【００２８】
ピクチャー・イン・ピクチャーの場合は、第２のキーフレームが、第１のキーフレーム上にオーバーレイされている。第２のキーフレームは、一般に、映像要素の左上のコーナーにオーバーレイされているが、映像要素の任意の他の領域でオーバーレイさせることができる。例えば、６個の映像要素１６１〜１６６は、各々、左上のコーナーにオーバーレイされている第２のキーフレーム２１１〜２１６を有している。追加のキーフレーム及び情報も、映像要素の任意の領域でオーバーレイさせることができる。例えば、映像要素には、対応する右下のコーナーで映像要素上にオーバーレイされている数字によって示されるように、１〜６の番号が付けられている。
【００２９】
映像要素１６０のグリッドは、映像タイムライン２２０及びコンテキストセンシティブ・ヘルプ（文脈依存ヘルプ）２２５の上方に配置されている。映像タイムラインは、映像全体の長さ、及びグリッドにおける映像要素によって表わされる映像の部分の長さを示す。グリッド１６０の下方に示されている映像タイムライン２２０では、映像タイムラインの数字は、映像全体の時間の長さを分単位で表わす。この映像例は、長さが７分である。映像タイムラインの内容は、部分に分割されており、各部分は、合計の映像時間長に対する対応する映像要素の時間長を表わしている。交互に色が変わる着色部分の各々は、映像タイムライン中に現れているように、付番された映像要素のうちの１つに対応している。
【００３０】
全部の図において、映像タイムラインの全部分は、交互に変化する色として示されているが、別々の色として示すこともできる。図２は、６個の映像要素に対する、映像タイムラインにおける６個の部分を示している。第１の部分２３０は長さ約１.５分であり、第２の部分２４０は長さ約０.５分であり、第３の部分２５０は長さちょうど１分以下であり、第４の部分２６０は長さ約１.５分であり、第５の部分２７０は長さ約１分であり、第６の部分２８０は長さ約１.５分である。実施形態では、タイムラインの数字は、他の時間単位を表わすことができる。実施形態では、タイムラインの内容は、交互のパターン又は別々のパターンなどの他の方法で表示することができる。
【００３１】
映像タイムライン２２０の下には、ブラウザをナビゲートする際に、ユーザを助けるよう、コンテキストセンシティブ・ヘルプ２２５を表示することができる。具体的には、ヘルプテキストは、映像ショットの階層内でいかにナビゲートするか、また、映像の再生をいかにして開始するかを示している。この例では、ヘルプテキストは、追加の対話オプションを提供している。「Ｔｏｐ：０,」では、ユーザが、彼の又は彼女の装置で「０」を押すと、主画面が表示される、即ち、映像全体を表わす映像要素が表示される。
【００３２】
図２は、この映像例の主画面を示す。「ｕｐ：＊,」では、ユーザが「＊,」を押すと、映像階層における１レベル上の画面が表示される。「ｐｌａｙｂａｃｋ：＃＜ｎ＞,」では、ユーザが、「＃」及び６個の数字１〜６のうちの１つを押すと、ブラウザは、対応するサブクラスタの初めから映像を再生する。また、ユーザが６個の数字１〜６のうちの１つを押すと、ブラウザは下層にある対応するサブクラスタまでナビゲートする。即ち、図１のツリーを降下し、ツリーの次の階層レベルに対応する画面が表示される。
【００３３】
図３は、本発明の実施形態による、図１の中間の階層レベルにおけるクラスタを表わす映像ブラウザの設計例を示す。設計は、図２におけるように、２×３グリッドの映像要素を含んでいるが、これは、両図の場合共、同じディスプレイ装置を使用しているからである。映像要素のレイアウトは、映像の一部分を表わしている。これら６個の映像要素１４１〜１４５及び１５０は、図１の第２のツリーレベルにおけるクラスタ１４０に由来する。この例では、映像要素１５０は、ピクチャー・イン・ピクチャー要素であり、映像要素１４１〜１４５は、それぞれ、映像ショットを代表するキーフレームである。映像要素には、対応する右下のコーナーで映像要素上にオーバーレイされている数字によって示されるように、１〜６の番号が付けられている。
【００３４】
映像要素１４０のグリッドは、映像タイムライン３２０の上方に配置されている。映像タイムライン３２０は、各映像要素の長さを示す。クラスタ１４０における映像ショットの長さは、約１.５分である。タイムラインの交互に色が変わる着色部分の各々は、映像タイムライン中に現れているように、付番された映像要素のうちの１つに対応している。タイムラインのグレイ領域は、ツリーの他の部分によってカバーされている。図３は、６個の映像要素に対して、映像タイムラインに６個の部分を示している。第１の部分３３０は長さ約０.８分であり、第２の部分３４０及び第３の部分３５０の各々は長さ約０.１分であり、第４の部分３６０は長さ約０.３分であり、第５の部分３７０及び第６の部分３８０の各々は長さ約０.１分である。
【００３５】
映像タイムライン３２０は、図２に示すレイアウトと同様に、コンテキストセンシティブ・ヘルプ（図示せず）の上方に配置することができる。図３のコンテキストセンシティブ・ヘルプは、図２のそれと同様の方法で作用する。しかしながら、図３の例では、「ｐｌａｙｂａｃｋ：＃＜ｎ＞,」でユーザが「１」を押すと、ブラウザは、図１のツリーを降下し、ツリーの次の階層レベルに対応する画面が表示される。「ｐｌａｙｂａｃｋ：＃＜ｎ＞,」では、ユーザが「２」〜「６」のうちのいずれかを押すと、ブラウザは、付番されたキーフレームに対応する映像ショットを再生する。
【００３６】
図４は、本発明の実施形態による、図１の最低の階層レベルにおけるクラスタを表わす映像ブラウザの設計例を示す。設計は、図２及び図３におけるように、２×３グリッドの映像要素を含んでいるが、これは、全三図のどの場合も、同じディスプレイ装置を使用しているからである。映像要素のレイアウトは、映像の部分を表わしている。これら４個の映像要素１１１〜１１４は、図１の最低のツリーレベルにおけるクラスタ１１０に由来する。これらの映像要素は、各々、映像ショットを代表するキーフレームである。映像要素には、対応する右下のコーナーで映像要素上にオーバーレイされている数字によって示されるように、１〜４の番号が付けられている。
【００３７】
映像要素１１０のグリッドは、映像タイムライン４２０の上方に配置されている。映像タイムライン４２０は、各映像要素の長さを示す。クラスタ１１０における映像ショットの長さは、約０.８分である。タイムラインの交互に色が変わる着色部分の各々は、映像タイムライン中に現れているように、付番された映像要素のうちの１つに対応している。タイムラインのグレイ領域は、ツリーの他の部分によってカバーされている。
【００３８】
映像タイムライン４２０は、図２に示すレイアウトと同様に、コンテキストセンシティブ・ヘルプ（図示せず）の上方に配置することができる。図４のコンテキストセンシティブ・ヘルプは、図２のそれと同様の方法で作用する。しかしながら、図４の例では、この最下層のツリーレベルは、他のキーフレーム画面へのリンクを有していない。「ｐｌａｙｂａｃｋ：＃＜ｎ＞，」では、ユーザが、数字１〜６のうちのいずれかを押すと、ブラウザは、付番されたキーフレームに対応する映像ショットを再生する。
【００３９】
図５〜図９は、それぞれ、本発明の実施形態による、２×２、３×２、４×２、４×３、及び４×４グリッドの映像要素を含む映像ブラウザの設計例を示す。映像ブラウザ設計における映像要素の数は、ディスプレイのサイズに基づいて変化する。携帯電話などの小型ディスプレイ装置では、要素の数は、より小型の電話ディスプレイ（図５におけるものなど）の２×２グリッドと、図９に示すようなより大型のディスプレイの４×４グリッドとの間の数にすることができる。要素のグリッドは、列×行と定義される。設計は、図２に示すような２×３、及び、図６に示すような３×２などの非正方形グリッドの場合も有効である。図２及び図６は、同数であるがレイアウトが異なる映像要素を含んでいる。非正方形グリッドの他の例は、図７に示すような４×２、図８に示すような３×４、及び４×３である。実施形態においては、他のグリッド寸法の組合せが使用できる。
【００４０】
図９は、映像要素上にオーバーレイされている数字及び文字を含む映像ブラウザの設計例を示す。この４×４グリッドの例では、最初の９個の映像要素上に、数字「１」〜「９」がオーバーレイされており、残りの７個の映像要素上に、文字「Ａ」〜「Ｇ」がオーバーレイされている。このように、彼の又は彼女の装置において、「１」〜「９」又は「Ａ」〜「Ｇ」を押すことによって、ユーザは、１６個の映像要素のうちの１つを選択することができる。図８は、同様に、映像要素上にオーバーレイされている数字及び文字の使用を示す。図５及び図７は、オーバーレイされている文字及び数字を含まない映像要素の例である。
【００４１】
各グリッド映像要素の設計は、その映像要素が、単一のショットを表わしているか、ショットのクラスタを表わしているか、によって異なる。その映像要素が、単一のショットを表わしている場合は、映像要素は、図４の映像要素１１１〜１１４に示すように、ショットからの単一のキーフレームを示す。映像要素が、ショットのクラスタを表わしている場合は、映像要素は、クラスタにおける何らかの重要な働き（function）に基づく「最も重要な」ショットに由来するキーフレームを示す。最も重要なショットに由来するキーフレームには、時間的に第１のショットに由来するキーフレームがオーバーレイする。結果は、図３の左上の要素に示すようなピクチャー・イン・ピクチャーである。また、各グリッドの映像要素は、キーパッド上のどのキーが１セットのショットへとナビゲートするのか、あるいは、どのキーがショットの再生を開始するのか、を示す文言を有するオプションのオーバーレイも有している。このオーバーレイは、タッチスクリーンの場合は除去される。
【００４２】
図１０は、小型装置における、本発明の実施形態に係る、映像ショットのキーフレームのナビゲーションの例を示す。完全な映像を表わしている三つの画面１０１０、１０２０、及び１０３０が示されている。画面１０２０は、ユーザが、第１の画面１０１０の第１の映像要素１０４０を選択した後の、映像の一部を表わしている。映像要素１０４０は、画面１０２０で表わされている映像ショットのうちの最も重要なキーフレームに対応すると共に、画面１０２０における第１の映像要素１０６０に対応する、時間的に第１の映像ショットを表わしているオーバーレイされたキーフレーム１０５０を示す。画面１０３０は、ユーザが、第２の画面１０２０の第１の映像要素１０６０を選択した後の、映像の一部を表わしている。映像要素１０６０は、画面１０３０で表わされている映像ショットのうちの最も重要なキーフレームに対応すると共に、画面１０３０における第１の映像要素１０８０に対応する、時間的に第１のショットを表わしているオーバーレイされたキーフレーム１０７０を示す。
【００４３】
画面１０２０では、２個の映像要素１０７１及び１０７２は、２個の映像ショットに対する二つの最も重要なキーフレームである。ユーザは、これら２個の映像ショットのどちらでも再生することができる。画面１０３０では、４個の映像要素１０８０〜１０８３は、４個の映像ショットに対する最も重要なキーフレームである。画面１０３０では、ユーザは、これらの４個の映像ショットのうちのいずれでも再生することができる。各画面の下のタイムラインは、分単位の映像の時間を表わしており、交互に変化する色で映像の選択された部分及び映像要素を示す。
【００４４】
クラスタの距離を決定する距離関数については、任意の適切な視覚的類似性尺度（visual similarity measurement）の逆数が使用できる。例えば、色ヒストグラム又は色相関曲線が使用できる。クラスタ距離を求めるのに使用される他の距離関数は、テキスト・トランスクリプト及び同じ認識された面の発生に基づくテキスト類似性である。
【００４５】
ショットの類似性を決定する距離関数については、任意の適切な視覚的類似性尺度の逆数が使用できる。例えば、色ヒストグラム又は色相関曲線が使用できる。色ヒストグラムは、一般に２次元（２Ｄ）又は３次元（３Ｄ）色空間における任意の一組の色範囲のそれぞれの画素数を数えることによって導き出される画像における色分布の表現である。色相関曲線は、色の対同士の空間相関を画素間の距離の関数として計算する。色ヒストグラム及び色相関曲線についての詳細は、それらが関連技術で周知であるので、ここでは、これ以上詳細には論じない。視覚的類似性に対して使用される距離関数の他の例は、テキスト・トランスクリプト及び同じ認識された面の発生に基づくテキスト類似性である。
【００４６】
「最も重要な」又は代表的なショットを選択するためには、いくつかの異なる手法が使用できる。重要な関数の詳細については、それらが関連技術で周知であるので、ここでは、これ以上詳細には論じない。実施形態では、代表的なショットが最も重要なショットであろうとなかろうと、１セットのショットにおける代表的なショットを選択するための手法が使用可能である。実施形態では、代表的なショットを選択するための他の手法の例は、最も長いショット、最大量のオーディオ・エネルギーを有するショット、及び映像がトランスクリプトを有する場合には最大量のテキストを有するショットである。別の手法は、クラスタリングの距離尺度を用いて、クラスタにおける他のショットに最も類似したショットを選択することである。
【００４７】
クラスタリングの距離尺度を用いる場合は、「最も重要な」ショットは、同じクラスタにおける他のショットに最も類似し、かつ、シブリング（兄弟）クラスタにおけるショットに最も類似していないショットである。所与のクラスタに対して、シブリングクラスタは、ツリーにおける同じ階層レベルのクラスタである。類似性は、他のクラスタメンバーに対する合計の距離を計算することによって、又はシブリングクラスタのメンバーである全てのショットに対する合計距離の重み付き合計値を減じることによって、各候補ショットについて求められる。最も少ない合計距離を有するショットが、最も重要なショットとして選択される。
【００４８】
シブリングクラスタの使用は、１つの階層レベルでは選択されたショットを生じさせるかもしれないが、次のより低い階層レベルでは、生じさせないかもしれない。なぜなら、その階層レベルでは、シブリングクラスタに対して、十分識別力のある累乗（power）を有さないからである。シブリングクラスタに対する距離の重みをゼロに設定することによって、そのクラスタ自身のメンバーに対する類似性のみが考慮されるであろう。例えば、図１０においては、これは映像要素１０４０の場合であり、映像要素１０４０は、他のクラスタ全てに対して十分には異なっていないため、画面１０２０における６個のクラスタの全てを代表していない。オーバーレイされているキーフレーム１０５０は、クラスタの真に第１のショットであり、したがって、再び、１０６０及び１０８０として現れている。
【００４９】
上記のように、ボトムアップクラスタリング手法は、クラスタ要素の数を限定するために、トップダウン処理と組み合わせて用いる。本実施形態での処理は、完全なクラスタリングツリーを生成するのではなく、クラスタツリーの各階層レベルを別々に処理し、凝集型の階層クラスタリングによって生成されるツリー構造を使用しない。処理の詳細については、図１１、図１２（Ａ）、及び図１２（Ｂ）に関連して説明する。
【００５０】
図１１、図１２（Ａ）、及び図１２（Ｂ）におけるクラスタリング処理の基本的な概要は、以下の通りである。
【００５１】
１．ツリーにおける最大葉数を、分岐係数ｂの次に高い累乗として求める。
【００５２】
２．全ての映像ショットを、いかなるクラスタもｂh-1個を超える要素を有することがないｂ個のクラスタにクラスタリングする。時間的に隣接した要素を有するクラスタの対のみを併合し、併合したクラスタの要素が多くなりすぎそうな対はスキップする（併合しない）。ｂ個のクラスタしか存在しない場合には、併合を一旦停止する。
【００５３】
３．サブクラスタの要素を再帰的に（recursively）クラスタリングして、クラスタ要素の最大数をｂ分の一に減らす。
【００５４】
４．併合できるサブクラスタがもはや無いため、クラスタをサブクラスタリングすると、ｂ個を超えるサブクラスタが生ずる場合は、そのクラスタを望ましくないとしてマークし、より高い階層レベルにおけるクラスタリングにおいて、望ましくないクラスタが生成された点まで後戻りして、望ましくないクラスタを、要素の最大数を超えるであろうクラスタと全く同様に処理しながら、クラスタリングを繰り返す。
【００５５】
５．ツリーの根が、ｂ個を超えるサブクラスタを有している場合は、ツリーの最大高さを上げて、クラスタリング処理をやり直す。
【００５６】
図１１は、本発明の実施形態による、クラスタリングを初期化するための、また、再帰的なクラスタリング処理を呼び出すための、処理の流れの例を示す。処理は、ステップ１１００で始まる。ステップ１１０２では、三つの入力が、処理に入力される。第１の入力は、特定の装置表示画面に表示することができる映像要素の数であるツリー分岐係数「ｂ」である。第２の入力は、時間的な順序での映像におけるショットのリストである。第３の入力は、クラスタ距離を求めるのに使用される距離関数である。クラスタ距離は、組合せクラスタにおける要素の最大ペアワイズ距離として、又は併合すべきクラスタ同士の間の境界を形成する二つの映像ショットの距離として、計算することができる。
【００５７】
例えば、時間的な順序、「ａｂｃｄｅｆｇ」での下記のショットを仮定し、また、それらは、クラスタＡが、要素ａ〜ｄを含み、かつ、クラスタＢが、要素ｅ〜ｇを含むようにクラスタリングされている、と仮定しよう。この例に対して最大ペアワイズ距離を用いると、ＡとＢとの間の距離は、距離ａｅ、ａｆ、ａｇ、ｂｅ、ｂｆ、ｂｇ、ｃｅ、ｃｆ、ｃｇ、ｄｅ、ｄｆ、又はｄｇの最大値である。併合すべきクラスタ同士の間の境界を形成している二つの映像ショットの距離を用いると、ＡとＢとの間の距離は、クラスタＡとＢとの時間的な境界における距離、即ち、要素ｄとｅとの間の距離である。
【００５８】
ステップ１１０４では、ショットのリストからショット数「ｎ」が求められる。実施形態では、ショット数は、別法として、ステップ１１０２で入力される。ステップ１１０６では、高さ「ｈ」及び分岐係数「ｂ」を有する選択されたバランスの取れたツリーにおける最大葉数は、「ｂh」として求められる。この決定は、全ての映像ショットを葉で保持することができるであろう所与の分岐係数「ｂ」について、バランスの取れたツリーの最小高さ「ｈ」を見出すことによって行なわれる。この「ｈ」は、ショット数より小さくない分岐係数ｂの最も小さい累乗であり、したがって、ｂh＞＝ｎである。このように、ステップ１１０６では、バランスの取れたツリーの最小高さ「ｈ」も同様に求められる。
【００５９】
例えば、ステップ１１０６で、分岐係数ｂ＝６が入力され、ステップ１１０８で、ｎ＝１００個の映像ショットが求められる、と仮定しよう。ステップ１１０６では、映像ショットを葉として保持できる最も小さいバランスの取れたツリーは、最大ｂh＝（６3）＝２１６個のショットを保持することができ、これは、分岐係数の累乗をｈ＝１から始まって昇順に調べることによって求められる。ｈ＝１では、ｂh＝（６1）＝６は、１００より小さく、したがって、１００個のショットを保持できるほど大きくはない。ｈ＝２では、ｂh＝（６2）＝３６は、１００より小さく、したがって、１００個のショットを保持できるほど大きくはない。しかしながら、ｈ＝３では、ｂh＝（６3）＝２１６は、１００個のショットより大きく、したがって、２１６枚の葉を有するツリーは、１００個のショットを保持するには十分な大きさである。
【００６０】
ステップ１１０８では、構築すべきクラスタツリーにおける葉数の限界値「ｌ」は、ステップ１１０６で求めた最大葉数ｂhとなるよう、即ち、限界値ｌ＝ｂhとなるよう初期化される。この限界値は、クラスタツリーをバランスの取れた状態に保つのに使用される。この限界値は、クラスタツリーをバランスの取れた状態に保つため、後の処理では、ｌ／ｂとして使用される。上記の例を、分岐係数ｂ＝６及びショット数ｎ＝１００、さらに、再帰の第１の反復を処理する、と仮定しよう。各クラスタにおける要素数のこの限界値は、ショットを葉として保持することができる最も小さいバランスの取れたツリーにおける最大葉数、即ち、ステップ１１０６で見出された最大葉数ｂh＝２１６を分岐係数ｂ＝６で割った値、即ち、２１６／６＝３６である。別法として、クラスタにおける要素数の新しい限界値は、分割すべきクラスタにおける要素数より小さい分岐係数の最も大きい累乗とすることができる。この場合には、生成されるサブツリーは、同様のショットを共にグループ化することを犠牲にして、より短いナビゲーション経路を有することができる。
【００６１】
ステップ１１１０では、図１２（Ａ）及び（Ｂ）における再帰的な処理が、三つのパラメータ、即ち、ステップ１１０２で入力されたショットのリスト、距離関数、及びステップ１１０８で初期化された限界値ｌと共に呼び出される。
【００６２】
ステップ１１１２では、図１２（Ａ）及び（Ｂ）の処理は、失敗の表示を戻し、次いで、ステップ１１１４では、ツリーの高さｈが、１だけ上げられる。再帰の一番上の呼出しが失敗を戻した（これは、ツリーの根ノードの故と思われる）以上、処理は、再び、より大きな高さのツリーで適用しなければならない（再帰では後戻りする道がないからである）。処理は、ステップ１１０８にループバックし、限界値ｌを再初期化してから再帰の第１の呼出しを、新しいツリー高さｈで再開する。ツリーの高さが上げられており、これは、最も長いナビゲーション経路が、類似性によるクラスタリングの無いバランスの取れたツリーにおけるそれよりも長くなる唯一の状況である。一般に、これは、映像ショット数が、分岐係数の累乗よりわずかに小さい場合にのみ生ずる。
【００６３】
ステップ１１１２で、図１２（Ａ）及び（Ｂ）の処理が失敗の表示を戻さない場合は、図１２（Ａ）及び（Ｂ）の処理は、ツリーを戻す。図１１の処理は、ステップ１１２０で終了する。
【００６４】
図１２（Ａ）及び（Ｂ）は、本発明の実施形態による、時間的な順序でのボトムアップの階層クラスタリング処理を、トップダウンのクラスタ要素数制限と組み合わせて適用する再帰的な処理の例を示す。この再帰的な処理は、図１１における処理によって呼び出され、図１１で求めた初期化を用いて、再帰の第１の反復を行う。処理は、ステップ１２００で始まる。ステップ１２１０では、クラスタリングを初期化するため、各ショットが、それ自体のクラスタ内に入れられる。ステップ１２２０では、時間的に隣接したクラスタ同士が、対にされる。ステップ１２２２では、最も小さい距離を有する対が、図１２（Ａ）及び（Ｂ）の処理の呼出しの際にパラメータの１つとして渡された距離関数を用いて見出される。上記のように、各クラスタは、同じクラスタ内の他のショットに最も類似し、かつ、シブリングクラスタ内のショットに最も類似していないショットとすることができるキーフレームによって表わされる。
【００６５】
ステップ１２２４では、ステップ１２２２で見い出された最も小さい距離を有する対に対するクラスタの組合せ基数が、基数限界値ｌを分岐係数ｂで割った値、即ち、ｌ／ｂを超える場合、あるいは、対が望ましくないとマークされた場合は、この対は無視される。処理は、ループバックして、ステップ１２２６で、次の最も小さい距離を有するクラスタ対が見出される。組合せ基数が、基数限界値を超えるため無視されたクラスタの対に対しては、クラスタの他の対より類似性が少ないクラスタ同士を併合できるが、このステップは、ツリーの高さを限定する。望ましくないとマークされたため無視されたクラスタの対については、図１２（Ｂ）と関連して、以下で説明する。
【００６６】
ステップ１２２４では、ステップ１２２２又はステップ１２２６のどちらかで見い出された最も小さい距離を有する対に対するクラスタの組合せ基数が、基数限界値ｌを分岐係数ｂで割った値、即ち、ｌ／ｂの値を超えない場合は、対は、ステップ１２２８で併合され、クラスタのリスト内に併合されたクラスタを有する二つの個々のクラスタに置き換わる。この限界値ｌ／ｂは、クラスタツリーをバランスの取れた状態に保つのに使用される。
【００６７】
ステップ１２３０では、分岐係数より大きいクラスタ数が存在する場合、及びステップ１２３２で、より多くのサブクラスタを併合できる場合は、処理は、ステップ１２２０にループバックして、クラスタリングを継続する。ステップ１２３２では、クラスタ数をツリーの分岐係数まで減らさないと、より多くのクラスタを併合できないことが有り得る。例えば、分岐係数３及びクラスタＡ、Ｂ、Ｃ、及びＤを仮定しよう。任意の二つのクラスタの組合わせが、大きすぎる場合、即ち、対ＡＢ、ＢＣ、又はＣＤのうちのいずれかに対するクラスタの組合せ基数が、限界値ｌを超える場合は、より多くのクラスタを併合できない。さらに、クラスタＡＢ、ＢＣ、又はＣＤが、望ましくないとマークされる場合は、より多くのクラスタを併合できない。望ましくないクラスタについての追加の詳細は、図１２（Ｂ）に関連して、以下で説明する。ステップ１２３０では、分岐係数より大きいクラスタ数が存在する場合、及びステップ１２３２で、より多くのクラスタを併合できない場合は、ステップ１２３４で、この失敗が、再帰的なクラスタリング処理の呼出し者に戻され、処理は、ステップ１２８０で終了する。このような失敗は、以下、図１２（Ｂ）に関連した説明の中で取り扱う。
【００６８】
図１２（Ａ）のステップ１２３０では、クラスタ数が、分岐係数ｂより小さいか、あるいは、それに等しい場合、及びステップ１２３６で、全てのクラスタが、処理されていない場合は、即ち、クラスタのそれぞれが、まだ再帰的に処理されていない場合は、コネクタ１は、図１２（Ａ）を図１２（Ｂ）に接続する。
【００６９】
図１２（Ｂ）は、ツリーの葉における各クラスタに対する、図１２（Ａ）及び（Ｂ）のクラスタリング処理の再帰的な呼出しの例を示す。図１２（Ｂ）はまた、図１２（Ａ）及び（Ｂ）が、失敗の表示を戻す（これは、ショットが、与えられた高さのツリーにフィットしない場合に生ずる）時、失敗を処理する。図１２（Ａ）及び（Ｂ）を通る第１の反復は、単一のショットしか含んでいないクラスタから始まった。時間的に隣接したクラスタの対は、ｂ個のクラスタしか残らなくなるまで併合された。それらｂ個のクラスタのそれぞれについて、ツリーの葉が、分岐係数ｂより多くのサブクラスタを含む場合は、図１２（Ａ）及び（Ｂ）の処理が、再帰的に適用される。図１２（Ａ）及び（Ｂ）の処理が、呼び出され、ツリーが戻されるごとに、新しいサブツリーが生成される。
【００７０】
ステップ１２４０では、ｂ個のクラスタの次に構築すべきクラスタツリーにおける葉数の限界値「ｌ２」は、最大葉数ｂx、即ち、限界値ｌ2＝ｂxであるように初期化される。この「ｘ」は、処理されるべき次の組合せクラスタのショット数より小さくない分岐係数の最も小さい累乗であり、したがって、ｂx＞＝ｘである。この限界値は、クラスタツリーをバランスの取れた状態に保つため、後の処理では、ｌ／ｂとして使用される。上記の例を、分岐係数ｂ＝６及びショット数ｎ＝１００、さらに、再帰の第１の反復を処理する、と仮定しよう。各クラスタにおける要素数のこの限界値は、ショットを葉として保持することができる最も小さいバランスの取れたツリーにおける最大葉数、即ち、ステップ１１０６で見出された最大葉数ｂh＝２１６を分岐係数ｂ＝６で割った値、即ち、２１６／６＝３６である。別法として、クラスタにおける要素数の新しい限界値は、分割すべきクラスタにおける要素数より小さい分岐係数の最も大きい累乗とすることができる。この場合には、生成されるサブツリーは、同様のショットを共にグループ化することを犠牲にして、より短いナビゲーション経路を有することができる。
【００７１】
ステップ１２４２では、図１２（Ａ）及び（Ｂ）における再帰的な処理が、三つのパラメータ、即ち、次の組合せクラスタに対するショットのリスト、距離関数、及びステップ１２４０で初期化された限界値ｌ2と共に呼び出される。パラメータ限界値ｌ2は、図１２（Ａ）でステップ１２００から始まる場合は、限界値ｌとなる。
【００７２】
ステップ１２４４では、図１２（Ａ）及び（Ｂ）の処理が、失敗の表示を戻さない場合は、コネクタ２は、図１２（Ｂ）を図１２（Ａ）に接続し、処理は、ループバックして、ステップ１２３６で、それ以上の組合せクラスタを全て処理する。ステップ１２４４で、図１２（Ａ）及び（Ｂ）の処理が、失敗の表示を戻す場合は、ステップ１２４６で、限界値ｌ2は、ｂ（分岐係数）倍に、即ち、ｌ2＝ｌ2 ×ｂにすることができる。
【００７３】
ステップ１２４８で、クラスタにおける要素数の限界値ｌ2が、以前の限界値を分岐係数で割った値より小さかった場合は、処理は、新しい限界値ｌ2でステップ１２４２にループバックし、同じクラスタに再帰が再び適用される。以下は、限界値が、以前の限界値を分岐係数で割った値より小さくなり得る場合の例である。４個のクラスタＡ、Ｂ、Ｃ、及びＤ、分岐係数４、及び下記の基数、即ち、Ａ：１０；Ｂ：２０；Ｃ：５０；Ｄ：３０を仮定しよう。ツリーの最大葉数は、ｂh＝４4＝２５６となり、各サブクラスタの限界値は、ｂh／ｂ＝４3＝６４となろう。しかしながら、Ａの基数は、４2＝１６より大きくなく、したがって、それは、高さ２のサブツリーにフィットすることができよう。後で高さ２のツリーを構築して、Ａに対して失敗する場合は、３の高さでＡに対して再び処理を呼び出すことができる。
【００７４】
ステップ１２４８で、クラスタにおける要素数の限界値ｌ2が、以前の限界値を分岐係数で割った値より大きかった場合は、ステップ１２５４で、そのクラスタは、望ましくないとマークされる。処理は、ステップ１２５６における再帰で、ツリーの次のより高いレベルまで後戻りする。ステップ１２５８で、処理は、二つのクラスタを併合することによって望ましくないクラスタが生成された前の点まで、クラスタリング内を後戻りする。コネクタ３は、図１２（Ｂ）を図１２（Ａ）のステップ１２２０に接続する。図１２（Ａ）及び（Ｂ）の再帰的な処理の呼出し者は、次いで、ステップ１２５８で後戻りの際に見出された点から、ステップ１２４６で求められた新しい限界値ｌ2で、クラスタリングを継続することができる。望ましくないとマークされたクラスタは、要素数の限界値を超えるであろうクラスタと全く同様に処理される、即ち、それらは、併合することができるクラスタの対を探索する際に無視される。
【００７５】
例えば、４個のサブクラスタが時間的な順序、即ち、Ａ、Ｂ、Ｃ、及びＤで存在している、と仮定しよう。Ｂ及びＣは、最も少ない距離を有し、単一のクラスタＢＣに組み合わされている。クラスタＢＣに処理を再帰的に適用する場合、それは、与えられた高さのツリーにフィットすることができず、図１２（Ａ）及び（Ｂ）の処理は、失敗の表示を戻し、図１２（Ｂ）のステップ１２５４で、クラスタＢＣは、望ましくないとマークされる。処理は、Ｂ及びＣが併合されて、ＢＣが形成された、４個のサブクラスタを有する点まで、再帰内を後戻りする。クラスタＢＣは、ステップ１２６０で、望ましくないとマークされる。この時点で、再帰的な処理の呼出し者は、なお、Ａ及びＢ又はＣ及びＤを組み合わせ、次いで、処理を再帰的にＡＢ又はＣＤのどちらかに適用しようと企てることができる。これは、ＡＢ及びＣＤが、以前に望ましくないとマークされたことがなく、かつ、それらの基数が、限界値を超えていないことを仮定している。
【００７６】
ステップ１２３０に戻って、クラスタ数が、分岐係数ｂに等しいか、あるいは、それより小さい場合、及び全ての組合せクラスタが、ステップ１２３６で処理されていた場合は、ステップ１２７０で、ツリーは、再帰的なクラスタリング処理の呼出し者に戻され、処理は、ステップ１２８０で終了する。
【００７７】
＜III．評価＞
実施形態において、初期設計及びレイアウト処理は、Ｊａｖａ（登録商標）ベースである。１２９個のショットを含む特定のテスト映像の場合で、本発明の処理（２）を二つの別の処理、処理（１）及び処理（３）と比較した。処理の結果として生じたツリーを、図１３〜図１５に示す。
【００７８】
別の処理（１）に対して、図１３は、類似性クラスタリング無しで生じたバランスの取れたツリーの例を示す。このバランスの取れたツリーは、左側が充実している。処理（２）に対して、図１４は、本発明の実施形態による、類似性クラスタリング及びツリー高さの制限を行なって生じたツリーの例を示す。この処理（２）は、上記の図１〜図１２（Ｂ）に関連して論じた。処理（３）に対して、図１５は、類似性クラスタリングを行うと共に、ツリー高さに対する限界値無しで生じたツリーの例を示す。
【００７９】
処理（１）及び処理（２）の各々は、「３」の高さを有するツリーを生じた。処理（３）は、「５」の高さを有するツリーを生じた。図１６は、本発明の実施形態によるものであり、図１３〜図１５のツリーを生ずる処理に対する処理結果を比較する表の例を示す。行１〜行５において、表は、各処理における特定の長さのナビゲーション経路によって到達可能な映像ショット数をリスト化している。
【００８０】
図１６に示すように、処理（２）、即ち、時間的な順序でのバランスの取れた凝集型の階層クラスタリング処理における平均ナビゲーション経路長「２.９２」は、処理（１）、即ち、純粋なバランスの取れた手法における平均ナビゲーション経路長「２.８７」よりわずかに高い。処理（３）、即ち、ツリーバランスを問題としないクラスタリング手法は、処理（２）よりも、かなり高い平均経路長「３.３７」と、はるかに高い最大経路長「５」とを有している。
【００８１】
＜IV．システムハードウェア、ソフトウェア、及び構成要素＞
図１７は、本発明の実施形態による、ディスプレイ装置及び映像ブラウザの例を示す。ディスプレイ装置１７００は、一般に、ディスプレイ１７０５、少なくとも１つのメモリ１７１０、少なくとも１つのプロセッサ１７２０、及び少なくとも１つの記憶装置又はある種のレポジトリー１７３０を備えている。装置１７００は、さらに、ソフトウェア１７４０を備えている。このソフトウェア１７４０は、ユーザが、映像をナビゲートできるようにする、本実施形態に係る「映像ブラウザ」を備えている。本実施形態では、ソフトウェアは、Ｊａｖａ（登録商標）ベースである。
【００８２】
ディスプレイ装置１７００は、映像１７５０を、例えば、記憶装置１７３０に記憶する。別法として、記憶装置１７３０及び（又は）ソフトウェア１７４０は、インターネット１７７０を介してアクセスされる遠隔コンピュータ１７６０上に保持されている。本発明の焦点は、携帯電話又はパーソナル・ディジタル・アシスタント（ＰＤＡ）などのより小型のディスプレイ装置に合わせてあるが、ディスプレイ装置は、また、コンピュータ又はテレビジョンなどの任意の他のより大きな装置とすることもできる。
【００８３】
本発明の実施形態は、本開示の教示に従ってプログラムされた従来の汎用又は専用ディジタルコンピュータ（複数も可）又はマイクロプロセッサ（複数も可）を用いて実施することができるコンピュータを用いた方法及びシステムを含むことができる。適切なソフトウェア・コーディングが、プログラマーによって、本開示の教示に基づき容易に作成可能である。本発明の実施形態は、ここで提示された特徴のうちの任意のものを行なうためのコンピュータによって実行可能な命令のプログラムを備えることができる。
【００８４】
本発明の実施形態は、コンピュータで読み取り可能な記憶媒体などのコンピュータで読み取り可能な媒体を含むことができる。コンピュータで読み取り可能な記憶媒体は、コンピュータをプログラムして、ここで提示された特徴のうちの任意のものを行なうのに使用することができる、記憶された命令を有することができる。記憶媒体は、フロッピー（登録商標）ディスク、光ディスク、ＤＶＤ、ＣＤ-ＲＯＭ、マイクロドライブ、及び磁気光ディスクを含む任意のタイプのディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＤＲＡＭ、フラッシュメモリ、又は命令及び（又は）データを記憶するのに適した任意の媒体又は装置を含むことができる（但し、これらに限定されない）。
【００８５】
本発明は、汎用／専用コンピュータ（複数も可）又はマイクロプロセッサ（複数も可）などのコンピュータのハードウェアを制御するためのソフトウェア、及びそれらと人間のユーザ又は本発明の結果を利用する他の機構との対話を可能にするためのソフトウェアの両方を含むことができる。このようなソフトウェアは、デバイスドライバ、オペレーティングシステム、実行環境／コンテナ、ユーザインタフェース、及びユーザアプリケーションを含むことができる（但し、これらに限定されない）。
【００８６】
本発明の実施形態は、本発明の処理を実行するためのコードを提供する工程を含むことができる。この提供する工程は、ユーザに任意のやり方でコードを提供する工程を含むことができる。例えば、この提供する工程は、コードを含むディジタル信号をユーザに送信する工程；物理的な媒体上のコードをユーザに提供する工程；又はコードを利用可能にする任意の他の方法を含むことができる。
【００８７】
本発明の実施形態は、本発明の実施形態の処理のうちの任意のものを行なうための、コンピュータで実行することができるコードを送信するための、コンピュータで実行される方法を含むことができる。この送信する工程は、インターネットなどのネットワークの任意の部分を介した転送；ワイヤ、大気又は空間を介した転送；又は任意の他のタイプの送信による転送を含むことができる。この送信する工程は、コードの送信を開始する工程；又は任意の領域又は国から別の領域又は国へコードを通過させる工程を含むことができる。ユーザへの送信は、その送信がそこから送られた場所を問わず、任意の領域又は国におけるユーザによって受信される任意の送信を含むことができる。
【００８８】
本発明の実施形態は、本発明の実施形態の処理のうちの任意のものを行なうためコンピュータにおいて実行することができるコードを含む信号を含むことができる。この信号は、インターネットなどのネットワークを介して；ワイヤ、大気又は空間を介して；又は任意の他のタイプの送信による信号を含むことができる。信号全体は、同時に搬送する必要はない。信号は、その転送期間に亘って、経時的に延長することができる。信号は、現在搬送されているもののスナップショットと考えるべきではない。
【００８９】
本発明の実施形態の以上の記述は、図解及び説明の目的で付与された。網羅的である意図、又は、本発明を開示された形態どおりのものに限定する意図はない。当該技術の通常の知識を有する人には、多くの修正及び変形は明らかであろう。例えば、開示された本発明の実施形態で行なわれる工程は、別の順序で行うことができ、ある工程は省略することができ、また、追加の工程を加えることができる。本発明の他の実施形態を開発することができる。しかもそれらは、本発明の主旨及び範囲、及びクレームを逸脱せずに開発することができることを理解されたい。実施形態は全て、本発明の原理及びその応用が最も良く説明されるよう選択し、かつ記述し、それにより、当該技術の通常の知識を有する他の人々が、各種の実施形態について、また、想定される特定の用途に適した各種の修正と共に本発明を理解できるようにした。本発明の範囲は、クレーム及びそれらの等価物によって定義されることが意図されている。
【図面の簡単な説明】
【００９０】
【図１】本発明の実施形態に係る映像ショットの階層例を示す図である。
【図２】本発明の実施形態に係る図１で階層の根として図示された映像全体を表わす映像ブラウザの設計例を示す図である。
【図３】本発明の実施形態に係る図１の中間の階層レベルのクラスタを表わす映像ブラウザの設計例を示す図である。
【図４】本発明の実施形態に係る図１の最低の階層レベルのクラスタを表わす映像ブラウザの設計例を示す図である。
【図５】本発明の実施形態に係る２×２グリッドの映像要素を含む映像ブラウザの設計例を示す図である。
【図６】本発明の実施形態に係る３×２グリッドの映像要素を含む映像ブラウザの設計例を示す図である。
【図７】本発明の実施形態に係る４×２グリッドの映像要素を含む映像ブラウザの設計例を示す図である。
【図８】本発明の実施形態に係る４×３グリッドの映像要素を含む映像ブラウザの設計例を示す図である。
【図９】本発明の実施形態に係る４×４グリッドの映像要素を含む映像ブラウザの設計例を示す図である。
【図１０】本発明の実施形態に係る小型の装置上の映像ショットのキーフレームのナビゲーションの例を示す図である。
【図１１】本発明の実施形態に係る、クラスタリングを初期化すると共に再帰的なクラスタリング処理を呼び出すための、処理の流れの例を示すフローチャートである。
【図１２】（Ａ）及び（Ｂ）は、本発明の実施形態に係る、時間的な順序でのボトムアップの階層クラスタリング処理とトップダウンのクラスタ要素数制限とを組み合わせて適用する再帰的な処理の例を示すフローチャートである。
【図１３】類似性クラスタリング無しで生じたバランスの取れたツリーの例を示す図である。
【図１４】本発明の実施形態による類似性クラスタリング及びツリー高さの制限を行なって生じたツリーの例を示す図である。
【図１５】類似性クラスタリングを行うと共にツリー高さに対する限界値無しで生じたツリーの例を示す図である。
【図１６】図１３〜図１５のツリーを生ずる各処理に対する処理結果を比較する表の例を示す図である。
【図１７】本発明の実施形態に係るディスプレイ装置及び映像ブラウザの例を示すブロック図である。
【技術分野】
【０００１】
本発明は、ディスプレイ装置における映像ブラウザに関し、詳しくは、時間的に順序付けられた映像キーフレームの類似性に基づくナビゲーション階層を用いて短いナビゲーション経路によりディスプレイ装置上でリニア映像をナビゲートするための映像ナビゲーション方法、映像ナビゲーションシステム、及び映像ナビゲーションプログラムに関する。
【背景技術】
【０００２】
ユーザがディスプレイ装置上で映像を再生する時は、映像における特定のシーンにアクセスすることが望ましい。ディスプレイ装置上のナビゲーション支援機能（navigation aid）は、ユーザが、所望のシーンまで映像をナビゲートすることを可能にする。ディジタル・ビデオ・ディスク（ＤＶＤ）の場合、ＤＶＤは、記憶されている映像のシーンインデクスをキーフレームの形態でユーザに与える。一方、大部分の自動的に生成されるナビゲーション支援機能では、映像におけるシーンを自動的に検出することが困難なため、シーンの代わりにショットが用いられる。ショットは、シーンよりはるかに短いため、これは、はるかにより大きな数（一般に映像の毎分に対して１０個以上）のキーフレームを生じる。テレビジョン画面又はコンピュータ画面などの画面上に数個のキーフレームを表示するＤＶＤ手法では、ある特定のショットにアクセスしたい場合、数百個のキーフレームまでスケールアップしてはくれない。各画面上に数個のキーフレームを表示する余地しかない携帯電話などの小型の装置では、状況はさらに悪い。
【０００３】
さらに、映像をナビゲートするための大部分のインタフェースは、特別に設計されたリモコン（例えば、ＴＩＶＯリモコン）又はマウスのどちらかに依存する。携帯電話のように小型ディスプレイを備え且つマウスを備えていない装置上では、映像についての情報を提供するスペースが制限され、ユーザ入力のオプションが限定されているため、映像をナビゲートするのは困難である。
【０００４】
【非特許文献１】AN,C.-H.,et al.,"Fractal Image Compression by Improved Balanced Tree Clustering,"Proceedings of SPIE, Volume 3164, Apprications of Digital Image Processing XX, pages 554-562(1997).
【０００５】
【非特許文献２】GEVA,S.,"K-Tree: A Height Balanced Tree Structured Vector Quantizer,"Proceedings of the 2000 IEEE Signal Processing Society Workshop, Volume 1,pages 271-280(2000).
【０００６】
【非特許文献３】GIRGENSOHN,A.,et al.,"Home Video Editing Made Easy-Balancing Automation and User Control,"Proceedings of Human-Computer Interaction(INTERACT'01),IOS Press, Tokyo,Japan, 8 pages(2001).
【０００７】
【非特許文献４】ZHANG,T.,"BIRCH: An Efficient Data Clustering Method for Very Large Databases,"Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Canada,pages 103-114(1996).
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、ディスプレイ装置上で、特に小型ディスプレイ装置上で、映像ショットのナビゲーションを自動的に可能にするための、より良いプロセスを提供することにある。
【課題を解決するための手段】
【０００９】
上記目的を達成するために請求項１に記載の発明は、映像ショットにセグメンテーションされた映像に対して、限定された画面サイズであり且つキーフレームより大きな画面サイズを有するディスプレイ装置上でキーフレームを表示する映像ブラウザを用いて映像のナビゲーションを可能にするコンピュータを用いた映像ナビゲーション方法であって、前記方法は、前記映像ショットの時間的な順序を維持しながら、前記映像ショットを類似性によってクラスタリングする工程と、前記ツリーの経路長を最小限に抑えながら、前記映像ショットのクラスタに対して階層的に組織化されたナビゲーションツリーを生成する工程と、含むことを特徴としている。
【００１０】
請求項９に記載の発明は、映像ショットにセグメンテーションされた映像に対して限定された画面サイズを有するディスプレイ装置上でキーフレームを表示する映像ブラウザを用いて映像のナビゲーションを可能にする映像ナビゲーションシステムであって、前記システムは、前記映像ショットの時間的な順序が維持されながら、類似性によってクラスタリングされた映像ショットを取得するクラスタリング手段と、前記ツリーの経路長が最小限に抑えられながら、前記クラスタリングされた映像ショットから階層的に組織化されたナビゲーションツリーを生成するツリー生成手段と、を含むことを特徴としている。
【００１１】
請求項１７に記載の発明は、映像ショットにセグメンテーションされた映像に対して限定された画面サイズを有するディスプレイ装置上でキーフレームを表示する映像ブラウザを用いて映像のナビゲーションを可能にするための映像ナビゲーションプログラムであって、コンピュータを、前記映像ショットの時間的な順序が維持されながら、類似性によってクラスタリングされた映像ショットを取得するクラスタリング手段、及び、前記ツリーの経路長が最小限に抑えられながら、前記クラスタリングされた映像ショットから階層的に組織化されたナビゲーションツリーを生成するツリー生成手段、として機能させるための映像ナビゲーションプログラムであることを特徴としている。
【発明の効果】
【００１２】
本発明によれば、映像ショットにセグメンテーションされた映像に対して、限定された画面サイズを有するディスプレイ装置上で、キーフレームを表示する映像ブラウザを用いた映像のナビゲーションを可能にするためのコンピュータを用いた方法が、提供されている。映像ショットは、映像ショットの時間的な順序が維持されながら、類似性によってクラスタリングされる。映像ショットのクラスタに対して、ツリーの経路長が最小限に抑えられながら、階層的に組織化されたナビゲーションツリーが生成される。
【発明を実施するための最良の形態】
【００１３】
以下、図面を参照して本発明の実施の形態の一例を詳細に説明する。
【００１４】
＜I．前書き＞
映像ディスプレイ装置用のナビゲーション支援機能は、ショットをショットの階層にクラスタリングする工程を含むことができる。クラスタリングは、異なるグループへのオブジェクトの分類である。階層処理は、以前に確立したクラスタを用いて、連続的なクラスタを見出す。凝集型の階層クラスタリングは、別々のクラスタとしての各要素から始まり、それらを連続的により大きなクラスタに併合する「ボトムアップ」クラスタリング手法である。凝集型の階層クラスタリングは、時間的な順序を維持するクラスタリングツリーを生成するのに最適である。次にどのクラスタを併合すべきかを決定する時は、クラスタの全ての対を考慮するのではなく、時間的に隣接しているクラスタの対のみを考慮する。これはクラスタリング処理の時間複雑度を大幅に減少させる。
【００１５】
別の種類の階層クラスタリングは、「トップダウン」クラスタリングである。これは、セット全体から始まり、それを連続的により小さいクラスタに分割してゆく。しかしながら、トップダウンクラスタリング手法（例えばｋ平均法）は、時間的な順序を維持するには、それほど最適ではない。一方、トップダウンクラスタリング手法は、バランスの取れたツリーを生成するように適用することができる。バランスの取れたツリーは、その高さができるだけ小さく保たれたツリーである。ツリーの高さは、根ノードから葉ノードまでの最も長い経路である。単一のノードを有するツリーは「１」の高さを有している。
【００１６】
現在、汎用されている凝集型の階層クラスタリング処理は、時間的な順序によるもので、クラスタにおける要素数を制限しない。これは、結果として、バランスの取れていないクラスタツリーを生成する。他の汎用されている処理は、クラスタリングとバランスの取れたツリーとを組み合わせているが、トップダウンクラスタリング処理専用で、時間的な順序は維持されない。
【００１７】
本発明は、クラスタの要素数を制限するため、ボトムアップクラスタリング手法をトップダウン処理と組み合わせて使用している。完全なクラスタリングツリーを生成するのではなく、このクラスタリング処理は、クラスタツリーの各レベルを別々に処理し、凝集型の階層クラスタリングによって生成されるツリー構造を使用しない。
【００１８】
携帯電話又は他の小型ディスプレイ装置上において、リニア映像内のナビゲーションを可能にする設計が提供されている。映像は、映像ショットに分割され、映像ショットの階層にセグメンテーションされる。この設計は、画面の階層を提供する。各画面は、キーフレームのグリッドを含んでおり、これらのキーフレームの各々は、１つ又はそれ以上のショットのいずれかを表わしている。キーフレームは、映像ショットにおける一時点のフレーム又はスナップショットである。グリッドの要素が、ショットのグループを表わしている時は、グループにおける最も重要なショット及びグループにおける第１のショットの両方が示されており、ショットのグループは、ツリーをナビゲートすることによって到達することができる。
【００１９】
タイムラインは、目に見えるグリッド内の要素のそれぞれと関連した映像の部分を示す。ユーザは、階層的にグループ化されているショットをナビゲートして、映像を再生するための出発点を選択する。ユーザのナビゲーションを助けるため、映像ショットは、時間的な順序に保たれ、視覚的な類似性によってクラスタリングされている。類似性によるクラスタリングは、全映像ショットへの短いナビゲーション経路を保証するため行なわれる。類似性によるクラスタリングは、ナビゲーション経路の長さに対する制約があると、同様の映像ショットを一緒にグループ化することができない場合があるので、近似である。
【００２０】
このようなツリーは、ショットの時間的な順序を維持しつつ、ユーザに予測できるナビゲーションを与えることが望ましい。非常に長いナビゲーション経路を回避するため、ある程度バランスの取れたツリーを有することも望ましい。ショットは、視覚的な類似性などの基準によってグループ化されて、ユーザが、ナビゲーション経路を選択するのをより容易にすべきである。
【００２１】
ショットを時間的な順序に保つという要件は、視覚的な類似性などのクラスタリング基準を用いる場合、非常にバランスの悪いクラスタツリーを生ずる場合がある。一方、視覚的な類似性にもっぱら基づき、時間的な制約に基づかないクラスタツリーは、一般に、よりバランスの取れたものであるが、ユーザに同じ予測性を与えない。本発明は、時間的な順序を維持しながら、ある程度バランスの取れたツリーを生成し、その平均ナビゲーション経路長は、バランスの取れたツリーにおける経路長よりもわずかに長いだけである、ショット類似性の尺度に基づく階層クラスタリング手法を記述する。
【００２２】
＜II．技術的な詳細＞
図１は、本発明の実施形態による映像ショットの階層例１００を示す。この例では、３９個の映像ショットが「階層構造」即ち「ツリー」に組織化されている。映像ショットは、ツリーの葉におけるキーフレームによって表わされている。これらの葉は、ツリーにおいて、７個のクラスタにグループ化されている。クラスタ１１０は、葉のうちの４枚、即ち、映像ショット１１１〜１１４を含んでいる。５個のクラスタ１２１〜１２５の各々は、６枚の葉、即ち、６個の映像ショットを含んでいる。クラスタ１４０は、５枚の葉、即ち、映像ショット１４１〜１４５を含んでいる。
【００２３】
クラスタ１４０の左上のコーナーにおける映像要素１５０は、映像ショットを表すキーフレームである。このキーフレーム上にオーバーレイ（重ねて表示）されている第二のキーフレーム１５１、即ち、ピクチャー・イン・ピクチャー（親画面上に子画面が表示された画像）は、クラスタ１１０における４個の映像ショット１１１〜１１４を代表する（represent）。このレプリゼンテーションは、「４セグメント」と標識が付いている枝１５５又はショットで示されている。この例におけるピクチャー・イン・ピクチャーは、クラスタ１１０における映像ショットの第１のキーフレーム１１１を示している。このように、ツリーは、枝１５５を介して、映像要素１５０からクラスタ１１０における葉まで、降りてゆくことができる。
【００２４】
クラスタ１６０は、ツリーの根である。クラスタ１６０は、６個の映像要素１６１〜１６６を含んでいる。これらの映像要素の各々は、ピクチャー・イン・ピクチャー要素であり、ツリーのより下層の映像ショットのクラスタを代表している。これらのレプリゼンテーションは、枝１７１〜１７６によって示されている。枝１７１には、クラスタ１４０における５個の映像ショット１４１〜１４５と、クラスタ１１０における４個の映像ショットとに対して、「９セグメント」の標識が付いている。枝１７１〜１７６には、各々、クラスタ１２１〜１２６の各々における６個の映像ショットに対して、「６セグメント」の標識が付いている。このように、ツリーは、枝１７１〜１７６を介して、映像要素１６１〜１６６から、クラスタ１４０における映像要素及びその葉まで、及びクラスタ１２１〜１２５における葉まで、降りてゆくことができる。
【００２５】
図１におけるツリーの例は「３」の高さを有している。即ち、クラスタ１６０は第１の階層レベルに在り、クラスタ１１０は第３の階層レベルに在り、また、他のクラスタは第２の階層レベルに在る。また、このツリーは「６」の分岐係数（branching factor）を有している。即ち、ツリーにおける各クラスタは、各要素が、ピクチャー・イン・ピクチャー要素か映像ショット要素か否かに拘わらず、６個以上の要素を含むことができない。
【００２６】
図２〜図４は、ユーザが、図１に示した映像ショットの階層をナビゲートする際に生ずる絞り込みフォーカス（narrowing focus）を示す。
【００２７】
図２は、図１における階層の根として示される全体の映像１６０を表わす、本発明の実施形態に係る映像ブラウザの設計例を示す。設計（design）は、２×３グリッドの映像要素を含んでいる。映像要素のレイアウトは、映像全体を表わしている。これら６個の映像要素１６１〜１６６は、図１のクラスタ１６０、即ち、ツリーの根に由来する。映像要素は、映像ショットを代表するキーフレームとすることができる。また、映像要素は、映像ショットの別のクラスタを代表するピクチャー・イン・ピクチャーとすることができる。及び／又は、映像要素は、ツリーのより下層のピクチャー・イン・ピクチャー要素とすることができる。この例では、６個の映像要素は、ピクチャー・イン・ピクチャー要素である。
【００２８】
ピクチャー・イン・ピクチャーの場合は、第２のキーフレームが、第１のキーフレーム上にオーバーレイされている。第２のキーフレームは、一般に、映像要素の左上のコーナーにオーバーレイされているが、映像要素の任意の他の領域でオーバーレイさせることができる。例えば、６個の映像要素１６１〜１６６は、各々、左上のコーナーにオーバーレイされている第２のキーフレーム２１１〜２１６を有している。追加のキーフレーム及び情報も、映像要素の任意の領域でオーバーレイさせることができる。例えば、映像要素には、対応する右下のコーナーで映像要素上にオーバーレイされている数字によって示されるように、１〜６の番号が付けられている。
【００２９】
映像要素１６０のグリッドは、映像タイムライン２２０及びコンテキストセンシティブ・ヘルプ（文脈依存ヘルプ）２２５の上方に配置されている。映像タイムラインは、映像全体の長さ、及びグリッドにおける映像要素によって表わされる映像の部分の長さを示す。グリッド１６０の下方に示されている映像タイムライン２２０では、映像タイムラインの数字は、映像全体の時間の長さを分単位で表わす。この映像例は、長さが７分である。映像タイムラインの内容は、部分に分割されており、各部分は、合計の映像時間長に対する対応する映像要素の時間長を表わしている。交互に色が変わる着色部分の各々は、映像タイムライン中に現れているように、付番された映像要素のうちの１つに対応している。
【００３０】
全部の図において、映像タイムラインの全部分は、交互に変化する色として示されているが、別々の色として示すこともできる。図２は、６個の映像要素に対する、映像タイムラインにおける６個の部分を示している。第１の部分２３０は長さ約１.５分であり、第２の部分２４０は長さ約０.５分であり、第３の部分２５０は長さちょうど１分以下であり、第４の部分２６０は長さ約１.５分であり、第５の部分２７０は長さ約１分であり、第６の部分２８０は長さ約１.５分である。実施形態では、タイムラインの数字は、他の時間単位を表わすことができる。実施形態では、タイムラインの内容は、交互のパターン又は別々のパターンなどの他の方法で表示することができる。
【００３１】
映像タイムライン２２０の下には、ブラウザをナビゲートする際に、ユーザを助けるよう、コンテキストセンシティブ・ヘルプ２２５を表示することができる。具体的には、ヘルプテキストは、映像ショットの階層内でいかにナビゲートするか、また、映像の再生をいかにして開始するかを示している。この例では、ヘルプテキストは、追加の対話オプションを提供している。「Ｔｏｐ：０,」では、ユーザが、彼の又は彼女の装置で「０」を押すと、主画面が表示される、即ち、映像全体を表わす映像要素が表示される。
【００３２】
図２は、この映像例の主画面を示す。「ｕｐ：＊,」では、ユーザが「＊,」を押すと、映像階層における１レベル上の画面が表示される。「ｐｌａｙｂａｃｋ：＃＜ｎ＞,」では、ユーザが、「＃」及び６個の数字１〜６のうちの１つを押すと、ブラウザは、対応するサブクラスタの初めから映像を再生する。また、ユーザが６個の数字１〜６のうちの１つを押すと、ブラウザは下層にある対応するサブクラスタまでナビゲートする。即ち、図１のツリーを降下し、ツリーの次の階層レベルに対応する画面が表示される。
【００３３】
図３は、本発明の実施形態による、図１の中間の階層レベルにおけるクラスタを表わす映像ブラウザの設計例を示す。設計は、図２におけるように、２×３グリッドの映像要素を含んでいるが、これは、両図の場合共、同じディスプレイ装置を使用しているからである。映像要素のレイアウトは、映像の一部分を表わしている。これら６個の映像要素１４１〜１４５及び１５０は、図１の第２のツリーレベルにおけるクラスタ１４０に由来する。この例では、映像要素１５０は、ピクチャー・イン・ピクチャー要素であり、映像要素１４１〜１４５は、それぞれ、映像ショットを代表するキーフレームである。映像要素には、対応する右下のコーナーで映像要素上にオーバーレイされている数字によって示されるように、１〜６の番号が付けられている。
【００３４】
映像要素１４０のグリッドは、映像タイムライン３２０の上方に配置されている。映像タイムライン３２０は、各映像要素の長さを示す。クラスタ１４０における映像ショットの長さは、約１.５分である。タイムラインの交互に色が変わる着色部分の各々は、映像タイムライン中に現れているように、付番された映像要素のうちの１つに対応している。タイムラインのグレイ領域は、ツリーの他の部分によってカバーされている。図３は、６個の映像要素に対して、映像タイムラインに６個の部分を示している。第１の部分３３０は長さ約０.８分であり、第２の部分３４０及び第３の部分３５０の各々は長さ約０.１分であり、第４の部分３６０は長さ約０.３分であり、第５の部分３７０及び第６の部分３８０の各々は長さ約０.１分である。
【００３５】
映像タイムライン３２０は、図２に示すレイアウトと同様に、コンテキストセンシティブ・ヘルプ（図示せず）の上方に配置することができる。図３のコンテキストセンシティブ・ヘルプは、図２のそれと同様の方法で作用する。しかしながら、図３の例では、「ｐｌａｙｂａｃｋ：＃＜ｎ＞,」でユーザが「１」を押すと、ブラウザは、図１のツリーを降下し、ツリーの次の階層レベルに対応する画面が表示される。「ｐｌａｙｂａｃｋ：＃＜ｎ＞,」では、ユーザが「２」〜「６」のうちのいずれかを押すと、ブラウザは、付番されたキーフレームに対応する映像ショットを再生する。
【００３６】
図４は、本発明の実施形態による、図１の最低の階層レベルにおけるクラスタを表わす映像ブラウザの設計例を示す。設計は、図２及び図３におけるように、２×３グリッドの映像要素を含んでいるが、これは、全三図のどの場合も、同じディスプレイ装置を使用しているからである。映像要素のレイアウトは、映像の部分を表わしている。これら４個の映像要素１１１〜１１４は、図１の最低のツリーレベルにおけるクラスタ１１０に由来する。これらの映像要素は、各々、映像ショットを代表するキーフレームである。映像要素には、対応する右下のコーナーで映像要素上にオーバーレイされている数字によって示されるように、１〜４の番号が付けられている。
【００３７】
映像要素１１０のグリッドは、映像タイムライン４２０の上方に配置されている。映像タイムライン４２０は、各映像要素の長さを示す。クラスタ１１０における映像ショットの長さは、約０.８分である。タイムラインの交互に色が変わる着色部分の各々は、映像タイムライン中に現れているように、付番された映像要素のうちの１つに対応している。タイムラインのグレイ領域は、ツリーの他の部分によってカバーされている。
【００３８】
映像タイムライン４２０は、図２に示すレイアウトと同様に、コンテキストセンシティブ・ヘルプ（図示せず）の上方に配置することができる。図４のコンテキストセンシティブ・ヘルプは、図２のそれと同様の方法で作用する。しかしながら、図４の例では、この最下層のツリーレベルは、他のキーフレーム画面へのリンクを有していない。「ｐｌａｙｂａｃｋ：＃＜ｎ＞，」では、ユーザが、数字１〜６のうちのいずれかを押すと、ブラウザは、付番されたキーフレームに対応する映像ショットを再生する。
【００３９】
図５〜図９は、それぞれ、本発明の実施形態による、２×２、３×２、４×２、４×３、及び４×４グリッドの映像要素を含む映像ブラウザの設計例を示す。映像ブラウザ設計における映像要素の数は、ディスプレイのサイズに基づいて変化する。携帯電話などの小型ディスプレイ装置では、要素の数は、より小型の電話ディスプレイ（図５におけるものなど）の２×２グリッドと、図９に示すようなより大型のディスプレイの４×４グリッドとの間の数にすることができる。要素のグリッドは、列×行と定義される。設計は、図２に示すような２×３、及び、図６に示すような３×２などの非正方形グリッドの場合も有効である。図２及び図６は、同数であるがレイアウトが異なる映像要素を含んでいる。非正方形グリッドの他の例は、図７に示すような４×２、図８に示すような３×４、及び４×３である。実施形態においては、他のグリッド寸法の組合せが使用できる。
【００４０】
図９は、映像要素上にオーバーレイされている数字及び文字を含む映像ブラウザの設計例を示す。この４×４グリッドの例では、最初の９個の映像要素上に、数字「１」〜「９」がオーバーレイされており、残りの７個の映像要素上に、文字「Ａ」〜「Ｇ」がオーバーレイされている。このように、彼の又は彼女の装置において、「１」〜「９」又は「Ａ」〜「Ｇ」を押すことによって、ユーザは、１６個の映像要素のうちの１つを選択することができる。図８は、同様に、映像要素上にオーバーレイされている数字及び文字の使用を示す。図５及び図７は、オーバーレイされている文字及び数字を含まない映像要素の例である。
【００４１】
各グリッド映像要素の設計は、その映像要素が、単一のショットを表わしているか、ショットのクラスタを表わしているか、によって異なる。その映像要素が、単一のショットを表わしている場合は、映像要素は、図４の映像要素１１１〜１１４に示すように、ショットからの単一のキーフレームを示す。映像要素が、ショットのクラスタを表わしている場合は、映像要素は、クラスタにおける何らかの重要な働き（function）に基づく「最も重要な」ショットに由来するキーフレームを示す。最も重要なショットに由来するキーフレームには、時間的に第１のショットに由来するキーフレームがオーバーレイする。結果は、図３の左上の要素に示すようなピクチャー・イン・ピクチャーである。また、各グリッドの映像要素は、キーパッド上のどのキーが１セットのショットへとナビゲートするのか、あるいは、どのキーがショットの再生を開始するのか、を示す文言を有するオプションのオーバーレイも有している。このオーバーレイは、タッチスクリーンの場合は除去される。
【００４２】
図１０は、小型装置における、本発明の実施形態に係る、映像ショットのキーフレームのナビゲーションの例を示す。完全な映像を表わしている三つの画面１０１０、１０２０、及び１０３０が示されている。画面１０２０は、ユーザが、第１の画面１０１０の第１の映像要素１０４０を選択した後の、映像の一部を表わしている。映像要素１０４０は、画面１０２０で表わされている映像ショットのうちの最も重要なキーフレームに対応すると共に、画面１０２０における第１の映像要素１０６０に対応する、時間的に第１の映像ショットを表わしているオーバーレイされたキーフレーム１０５０を示す。画面１０３０は、ユーザが、第２の画面１０２０の第１の映像要素１０６０を選択した後の、映像の一部を表わしている。映像要素１０６０は、画面１０３０で表わされている映像ショットのうちの最も重要なキーフレームに対応すると共に、画面１０３０における第１の映像要素１０８０に対応する、時間的に第１のショットを表わしているオーバーレイされたキーフレーム１０７０を示す。
【００４３】
画面１０２０では、２個の映像要素１０７１及び１０７２は、２個の映像ショットに対する二つの最も重要なキーフレームである。ユーザは、これら２個の映像ショットのどちらでも再生することができる。画面１０３０では、４個の映像要素１０８０〜１０８３は、４個の映像ショットに対する最も重要なキーフレームである。画面１０３０では、ユーザは、これらの４個の映像ショットのうちのいずれでも再生することができる。各画面の下のタイムラインは、分単位の映像の時間を表わしており、交互に変化する色で映像の選択された部分及び映像要素を示す。
【００４４】
クラスタの距離を決定する距離関数については、任意の適切な視覚的類似性尺度（visual similarity measurement）の逆数が使用できる。例えば、色ヒストグラム又は色相関曲線が使用できる。クラスタ距離を求めるのに使用される他の距離関数は、テキスト・トランスクリプト及び同じ認識された面の発生に基づくテキスト類似性である。
【００４５】
ショットの類似性を決定する距離関数については、任意の適切な視覚的類似性尺度の逆数が使用できる。例えば、色ヒストグラム又は色相関曲線が使用できる。色ヒストグラムは、一般に２次元（２Ｄ）又は３次元（３Ｄ）色空間における任意の一組の色範囲のそれぞれの画素数を数えることによって導き出される画像における色分布の表現である。色相関曲線は、色の対同士の空間相関を画素間の距離の関数として計算する。色ヒストグラム及び色相関曲線についての詳細は、それらが関連技術で周知であるので、ここでは、これ以上詳細には論じない。視覚的類似性に対して使用される距離関数の他の例は、テキスト・トランスクリプト及び同じ認識された面の発生に基づくテキスト類似性である。
【００４６】
「最も重要な」又は代表的なショットを選択するためには、いくつかの異なる手法が使用できる。重要な関数の詳細については、それらが関連技術で周知であるので、ここでは、これ以上詳細には論じない。実施形態では、代表的なショットが最も重要なショットであろうとなかろうと、１セットのショットにおける代表的なショットを選択するための手法が使用可能である。実施形態では、代表的なショットを選択するための他の手法の例は、最も長いショット、最大量のオーディオ・エネルギーを有するショット、及び映像がトランスクリプトを有する場合には最大量のテキストを有するショットである。別の手法は、クラスタリングの距離尺度を用いて、クラスタにおける他のショットに最も類似したショットを選択することである。
【００４７】
クラスタリングの距離尺度を用いる場合は、「最も重要な」ショットは、同じクラスタにおける他のショットに最も類似し、かつ、シブリング（兄弟）クラスタにおけるショットに最も類似していないショットである。所与のクラスタに対して、シブリングクラスタは、ツリーにおける同じ階層レベルのクラスタである。類似性は、他のクラスタメンバーに対する合計の距離を計算することによって、又はシブリングクラスタのメンバーである全てのショットに対する合計距離の重み付き合計値を減じることによって、各候補ショットについて求められる。最も少ない合計距離を有するショットが、最も重要なショットとして選択される。
【００４８】
シブリングクラスタの使用は、１つの階層レベルでは選択されたショットを生じさせるかもしれないが、次のより低い階層レベルでは、生じさせないかもしれない。なぜなら、その階層レベルでは、シブリングクラスタに対して、十分識別力のある累乗（power）を有さないからである。シブリングクラスタに対する距離の重みをゼロに設定することによって、そのクラスタ自身のメンバーに対する類似性のみが考慮されるであろう。例えば、図１０においては、これは映像要素１０４０の場合であり、映像要素１０４０は、他のクラスタ全てに対して十分には異なっていないため、画面１０２０における６個のクラスタの全てを代表していない。オーバーレイされているキーフレーム１０５０は、クラスタの真に第１のショットであり、したがって、再び、１０６０及び１０８０として現れている。
【００４９】
上記のように、ボトムアップクラスタリング手法は、クラスタ要素の数を限定するために、トップダウン処理と組み合わせて用いる。本実施形態での処理は、完全なクラスタリングツリーを生成するのではなく、クラスタツリーの各階層レベルを別々に処理し、凝集型の階層クラスタリングによって生成されるツリー構造を使用しない。処理の詳細については、図１１、図１２（Ａ）、及び図１２（Ｂ）に関連して説明する。
【００５０】
図１１、図１２（Ａ）、及び図１２（Ｂ）におけるクラスタリング処理の基本的な概要は、以下の通りである。
【００５１】
１．ツリーにおける最大葉数を、分岐係数ｂの次に高い累乗として求める。
【００５２】
２．全ての映像ショットを、いかなるクラスタもｂh-1個を超える要素を有することがないｂ個のクラスタにクラスタリングする。時間的に隣接した要素を有するクラスタの対のみを併合し、併合したクラスタの要素が多くなりすぎそうな対はスキップする（併合しない）。ｂ個のクラスタしか存在しない場合には、併合を一旦停止する。
【００５３】
３．サブクラスタの要素を再帰的に（recursively）クラスタリングして、クラスタ要素の最大数をｂ分の一に減らす。
【００５４】
４．併合できるサブクラスタがもはや無いため、クラスタをサブクラスタリングすると、ｂ個を超えるサブクラスタが生ずる場合は、そのクラスタを望ましくないとしてマークし、より高い階層レベルにおけるクラスタリングにおいて、望ましくないクラスタが生成された点まで後戻りして、望ましくないクラスタを、要素の最大数を超えるであろうクラスタと全く同様に処理しながら、クラスタリングを繰り返す。
【００５５】
５．ツリーの根が、ｂ個を超えるサブクラスタを有している場合は、ツリーの最大高さを上げて、クラスタリング処理をやり直す。
【００５６】
図１１は、本発明の実施形態による、クラスタリングを初期化するための、また、再帰的なクラスタリング処理を呼び出すための、処理の流れの例を示す。処理は、ステップ１１００で始まる。ステップ１１０２では、三つの入力が、処理に入力される。第１の入力は、特定の装置表示画面に表示することができる映像要素の数であるツリー分岐係数「ｂ」である。第２の入力は、時間的な順序での映像におけるショットのリストである。第３の入力は、クラスタ距離を求めるのに使用される距離関数である。クラスタ距離は、組合せクラスタにおける要素の最大ペアワイズ距離として、又は併合すべきクラスタ同士の間の境界を形成する二つの映像ショットの距離として、計算することができる。
【００５７】
例えば、時間的な順序、「ａｂｃｄｅｆｇ」での下記のショットを仮定し、また、それらは、クラスタＡが、要素ａ〜ｄを含み、かつ、クラスタＢが、要素ｅ〜ｇを含むようにクラスタリングされている、と仮定しよう。この例に対して最大ペアワイズ距離を用いると、ＡとＢとの間の距離は、距離ａｅ、ａｆ、ａｇ、ｂｅ、ｂｆ、ｂｇ、ｃｅ、ｃｆ、ｃｇ、ｄｅ、ｄｆ、又はｄｇの最大値である。併合すべきクラスタ同士の間の境界を形成している二つの映像ショットの距離を用いると、ＡとＢとの間の距離は、クラスタＡとＢとの時間的な境界における距離、即ち、要素ｄとｅとの間の距離である。
【００５８】
ステップ１１０４では、ショットのリストからショット数「ｎ」が求められる。実施形態では、ショット数は、別法として、ステップ１１０２で入力される。ステップ１１０６では、高さ「ｈ」及び分岐係数「ｂ」を有する選択されたバランスの取れたツリーにおける最大葉数は、「ｂh」として求められる。この決定は、全ての映像ショットを葉で保持することができるであろう所与の分岐係数「ｂ」について、バランスの取れたツリーの最小高さ「ｈ」を見出すことによって行なわれる。この「ｈ」は、ショット数より小さくない分岐係数ｂの最も小さい累乗であり、したがって、ｂh＞＝ｎである。このように、ステップ１１０６では、バランスの取れたツリーの最小高さ「ｈ」も同様に求められる。
【００５９】
例えば、ステップ１１０６で、分岐係数ｂ＝６が入力され、ステップ１１０８で、ｎ＝１００個の映像ショットが求められる、と仮定しよう。ステップ１１０６では、映像ショットを葉として保持できる最も小さいバランスの取れたツリーは、最大ｂh＝（６3）＝２１６個のショットを保持することができ、これは、分岐係数の累乗をｈ＝１から始まって昇順に調べることによって求められる。ｈ＝１では、ｂh＝（６1）＝６は、１００より小さく、したがって、１００個のショットを保持できるほど大きくはない。ｈ＝２では、ｂh＝（６2）＝３６は、１００より小さく、したがって、１００個のショットを保持できるほど大きくはない。しかしながら、ｈ＝３では、ｂh＝（６3）＝２１６は、１００個のショットより大きく、したがって、２１６枚の葉を有するツリーは、１００個のショットを保持するには十分な大きさである。
【００６０】
ステップ１１０８では、構築すべきクラスタツリーにおける葉数の限界値「ｌ」は、ステップ１１０６で求めた最大葉数ｂhとなるよう、即ち、限界値ｌ＝ｂhとなるよう初期化される。この限界値は、クラスタツリーをバランスの取れた状態に保つのに使用される。この限界値は、クラスタツリーをバランスの取れた状態に保つため、後の処理では、ｌ／ｂとして使用される。上記の例を、分岐係数ｂ＝６及びショット数ｎ＝１００、さらに、再帰の第１の反復を処理する、と仮定しよう。各クラスタにおける要素数のこの限界値は、ショットを葉として保持することができる最も小さいバランスの取れたツリーにおける最大葉数、即ち、ステップ１１０６で見出された最大葉数ｂh＝２１６を分岐係数ｂ＝６で割った値、即ち、２１６／６＝３６である。別法として、クラスタにおける要素数の新しい限界値は、分割すべきクラスタにおける要素数より小さい分岐係数の最も大きい累乗とすることができる。この場合には、生成されるサブツリーは、同様のショットを共にグループ化することを犠牲にして、より短いナビゲーション経路を有することができる。
【００６１】
ステップ１１１０では、図１２（Ａ）及び（Ｂ）における再帰的な処理が、三つのパラメータ、即ち、ステップ１１０２で入力されたショットのリスト、距離関数、及びステップ１１０８で初期化された限界値ｌと共に呼び出される。
【００６２】
ステップ１１１２では、図１２（Ａ）及び（Ｂ）の処理は、失敗の表示を戻し、次いで、ステップ１１１４では、ツリーの高さｈが、１だけ上げられる。再帰の一番上の呼出しが失敗を戻した（これは、ツリーの根ノードの故と思われる）以上、処理は、再び、より大きな高さのツリーで適用しなければならない（再帰では後戻りする道がないからである）。処理は、ステップ１１０８にループバックし、限界値ｌを再初期化してから再帰の第１の呼出しを、新しいツリー高さｈで再開する。ツリーの高さが上げられており、これは、最も長いナビゲーション経路が、類似性によるクラスタリングの無いバランスの取れたツリーにおけるそれよりも長くなる唯一の状況である。一般に、これは、映像ショット数が、分岐係数の累乗よりわずかに小さい場合にのみ生ずる。
【００６３】
ステップ１１１２で、図１２（Ａ）及び（Ｂ）の処理が失敗の表示を戻さない場合は、図１２（Ａ）及び（Ｂ）の処理は、ツリーを戻す。図１１の処理は、ステップ１１２０で終了する。
【００６４】
図１２（Ａ）及び（Ｂ）は、本発明の実施形態による、時間的な順序でのボトムアップの階層クラスタリング処理を、トップダウンのクラスタ要素数制限と組み合わせて適用する再帰的な処理の例を示す。この再帰的な処理は、図１１における処理によって呼び出され、図１１で求めた初期化を用いて、再帰の第１の反復を行う。処理は、ステップ１２００で始まる。ステップ１２１０では、クラスタリングを初期化するため、各ショットが、それ自体のクラスタ内に入れられる。ステップ１２２０では、時間的に隣接したクラスタ同士が、対にされる。ステップ１２２２では、最も小さい距離を有する対が、図１２（Ａ）及び（Ｂ）の処理の呼出しの際にパラメータの１つとして渡された距離関数を用いて見出される。上記のように、各クラスタは、同じクラスタ内の他のショットに最も類似し、かつ、シブリングクラスタ内のショットに最も類似していないショットとすることができるキーフレームによって表わされる。
【００６５】
ステップ１２２４では、ステップ１２２２で見い出された最も小さい距離を有する対に対するクラスタの組合せ基数が、基数限界値ｌを分岐係数ｂで割った値、即ち、ｌ／ｂを超える場合、あるいは、対が望ましくないとマークされた場合は、この対は無視される。処理は、ループバックして、ステップ１２２６で、次の最も小さい距離を有するクラスタ対が見出される。組合せ基数が、基数限界値を超えるため無視されたクラスタの対に対しては、クラスタの他の対より類似性が少ないクラスタ同士を併合できるが、このステップは、ツリーの高さを限定する。望ましくないとマークされたため無視されたクラスタの対については、図１２（Ｂ）と関連して、以下で説明する。
【００６６】
ステップ１２２４では、ステップ１２２２又はステップ１２２６のどちらかで見い出された最も小さい距離を有する対に対するクラスタの組合せ基数が、基数限界値ｌを分岐係数ｂで割った値、即ち、ｌ／ｂの値を超えない場合は、対は、ステップ１２２８で併合され、クラスタのリスト内に併合されたクラスタを有する二つの個々のクラスタに置き換わる。この限界値ｌ／ｂは、クラスタツリーをバランスの取れた状態に保つのに使用される。
【００６７】
ステップ１２３０では、分岐係数より大きいクラスタ数が存在する場合、及びステップ１２３２で、より多くのサブクラスタを併合できる場合は、処理は、ステップ１２２０にループバックして、クラスタリングを継続する。ステップ１２３２では、クラスタ数をツリーの分岐係数まで減らさないと、より多くのクラスタを併合できないことが有り得る。例えば、分岐係数３及びクラスタＡ、Ｂ、Ｃ、及びＤを仮定しよう。任意の二つのクラスタの組合わせが、大きすぎる場合、即ち、対ＡＢ、ＢＣ、又はＣＤのうちのいずれかに対するクラスタの組合せ基数が、限界値ｌを超える場合は、より多くのクラスタを併合できない。さらに、クラスタＡＢ、ＢＣ、又はＣＤが、望ましくないとマークされる場合は、より多くのクラスタを併合できない。望ましくないクラスタについての追加の詳細は、図１２（Ｂ）に関連して、以下で説明する。ステップ１２３０では、分岐係数より大きいクラスタ数が存在する場合、及びステップ１２３２で、より多くのクラスタを併合できない場合は、ステップ１２３４で、この失敗が、再帰的なクラスタリング処理の呼出し者に戻され、処理は、ステップ１２８０で終了する。このような失敗は、以下、図１２（Ｂ）に関連した説明の中で取り扱う。
【００６８】
図１２（Ａ）のステップ１２３０では、クラスタ数が、分岐係数ｂより小さいか、あるいは、それに等しい場合、及びステップ１２３６で、全てのクラスタが、処理されていない場合は、即ち、クラスタのそれぞれが、まだ再帰的に処理されていない場合は、コネクタ１は、図１２（Ａ）を図１２（Ｂ）に接続する。
【００６９】
図１２（Ｂ）は、ツリーの葉における各クラスタに対する、図１２（Ａ）及び（Ｂ）のクラスタリング処理の再帰的な呼出しの例を示す。図１２（Ｂ）はまた、図１２（Ａ）及び（Ｂ）が、失敗の表示を戻す（これは、ショットが、与えられた高さのツリーにフィットしない場合に生ずる）時、失敗を処理する。図１２（Ａ）及び（Ｂ）を通る第１の反復は、単一のショットしか含んでいないクラスタから始まった。時間的に隣接したクラスタの対は、ｂ個のクラスタしか残らなくなるまで併合された。それらｂ個のクラスタのそれぞれについて、ツリーの葉が、分岐係数ｂより多くのサブクラスタを含む場合は、図１２（Ａ）及び（Ｂ）の処理が、再帰的に適用される。図１２（Ａ）及び（Ｂ）の処理が、呼び出され、ツリーが戻されるごとに、新しいサブツリーが生成される。
【００７０】
ステップ１２４０では、ｂ個のクラスタの次に構築すべきクラスタツリーにおける葉数の限界値「ｌ２」は、最大葉数ｂx、即ち、限界値ｌ2＝ｂxであるように初期化される。この「ｘ」は、処理されるべき次の組合せクラスタのショット数より小さくない分岐係数の最も小さい累乗であり、したがって、ｂx＞＝ｘである。この限界値は、クラスタツリーをバランスの取れた状態に保つため、後の処理では、ｌ／ｂとして使用される。上記の例を、分岐係数ｂ＝６及びショット数ｎ＝１００、さらに、再帰の第１の反復を処理する、と仮定しよう。各クラスタにおける要素数のこの限界値は、ショットを葉として保持することができる最も小さいバランスの取れたツリーにおける最大葉数、即ち、ステップ１１０６で見出された最大葉数ｂh＝２１６を分岐係数ｂ＝６で割った値、即ち、２１６／６＝３６である。別法として、クラスタにおける要素数の新しい限界値は、分割すべきクラスタにおける要素数より小さい分岐係数の最も大きい累乗とすることができる。この場合には、生成されるサブツリーは、同様のショットを共にグループ化することを犠牲にして、より短いナビゲーション経路を有することができる。
【００７１】
ステップ１２４２では、図１２（Ａ）及び（Ｂ）における再帰的な処理が、三つのパラメータ、即ち、次の組合せクラスタに対するショットのリスト、距離関数、及びステップ１２４０で初期化された限界値ｌ2と共に呼び出される。パラメータ限界値ｌ2は、図１２（Ａ）でステップ１２００から始まる場合は、限界値ｌとなる。
【００７２】
ステップ１２４４では、図１２（Ａ）及び（Ｂ）の処理が、失敗の表示を戻さない場合は、コネクタ２は、図１２（Ｂ）を図１２（Ａ）に接続し、処理は、ループバックして、ステップ１２３６で、それ以上の組合せクラスタを全て処理する。ステップ１２４４で、図１２（Ａ）及び（Ｂ）の処理が、失敗の表示を戻す場合は、ステップ１２４６で、限界値ｌ2は、ｂ（分岐係数）倍に、即ち、ｌ2＝ｌ2 ×ｂにすることができる。
【００７３】
ステップ１２４８で、クラスタにおける要素数の限界値ｌ2が、以前の限界値を分岐係数で割った値より小さかった場合は、処理は、新しい限界値ｌ2でステップ１２４２にループバックし、同じクラスタに再帰が再び適用される。以下は、限界値が、以前の限界値を分岐係数で割った値より小さくなり得る場合の例である。４個のクラスタＡ、Ｂ、Ｃ、及びＤ、分岐係数４、及び下記の基数、即ち、Ａ：１０；Ｂ：２０；Ｃ：５０；Ｄ：３０を仮定しよう。ツリーの最大葉数は、ｂh＝４4＝２５６となり、各サブクラスタの限界値は、ｂh／ｂ＝４3＝６４となろう。しかしながら、Ａの基数は、４2＝１６より大きくなく、したがって、それは、高さ２のサブツリーにフィットすることができよう。後で高さ２のツリーを構築して、Ａに対して失敗する場合は、３の高さでＡに対して再び処理を呼び出すことができる。
【００７４】
ステップ１２４８で、クラスタにおける要素数の限界値ｌ2が、以前の限界値を分岐係数で割った値より大きかった場合は、ステップ１２５４で、そのクラスタは、望ましくないとマークされる。処理は、ステップ１２５６における再帰で、ツリーの次のより高いレベルまで後戻りする。ステップ１２５８で、処理は、二つのクラスタを併合することによって望ましくないクラスタが生成された前の点まで、クラスタリング内を後戻りする。コネクタ３は、図１２（Ｂ）を図１２（Ａ）のステップ１２２０に接続する。図１２（Ａ）及び（Ｂ）の再帰的な処理の呼出し者は、次いで、ステップ１２５８で後戻りの際に見出された点から、ステップ１２４６で求められた新しい限界値ｌ2で、クラスタリングを継続することができる。望ましくないとマークされたクラスタは、要素数の限界値を超えるであろうクラスタと全く同様に処理される、即ち、それらは、併合することができるクラスタの対を探索する際に無視される。
【００７５】
例えば、４個のサブクラスタが時間的な順序、即ち、Ａ、Ｂ、Ｃ、及びＤで存在している、と仮定しよう。Ｂ及びＣは、最も少ない距離を有し、単一のクラスタＢＣに組み合わされている。クラスタＢＣに処理を再帰的に適用する場合、それは、与えられた高さのツリーにフィットすることができず、図１２（Ａ）及び（Ｂ）の処理は、失敗の表示を戻し、図１２（Ｂ）のステップ１２５４で、クラスタＢＣは、望ましくないとマークされる。処理は、Ｂ及びＣが併合されて、ＢＣが形成された、４個のサブクラスタを有する点まで、再帰内を後戻りする。クラスタＢＣは、ステップ１２６０で、望ましくないとマークされる。この時点で、再帰的な処理の呼出し者は、なお、Ａ及びＢ又はＣ及びＤを組み合わせ、次いで、処理を再帰的にＡＢ又はＣＤのどちらかに適用しようと企てることができる。これは、ＡＢ及びＣＤが、以前に望ましくないとマークされたことがなく、かつ、それらの基数が、限界値を超えていないことを仮定している。
【００７６】
ステップ１２３０に戻って、クラスタ数が、分岐係数ｂに等しいか、あるいは、それより小さい場合、及び全ての組合せクラスタが、ステップ１２３６で処理されていた場合は、ステップ１２７０で、ツリーは、再帰的なクラスタリング処理の呼出し者に戻され、処理は、ステップ１２８０で終了する。
【００７７】
＜III．評価＞
実施形態において、初期設計及びレイアウト処理は、Ｊａｖａ（登録商標）ベースである。１２９個のショットを含む特定のテスト映像の場合で、本発明の処理（２）を二つの別の処理、処理（１）及び処理（３）と比較した。処理の結果として生じたツリーを、図１３〜図１５に示す。
【００７８】
別の処理（１）に対して、図１３は、類似性クラスタリング無しで生じたバランスの取れたツリーの例を示す。このバランスの取れたツリーは、左側が充実している。処理（２）に対して、図１４は、本発明の実施形態による、類似性クラスタリング及びツリー高さの制限を行なって生じたツリーの例を示す。この処理（２）は、上記の図１〜図１２（Ｂ）に関連して論じた。処理（３）に対して、図１５は、類似性クラスタリングを行うと共に、ツリー高さに対する限界値無しで生じたツリーの例を示す。
【００７９】
処理（１）及び処理（２）の各々は、「３」の高さを有するツリーを生じた。処理（３）は、「５」の高さを有するツリーを生じた。図１６は、本発明の実施形態によるものであり、図１３〜図１５のツリーを生ずる処理に対する処理結果を比較する表の例を示す。行１〜行５において、表は、各処理における特定の長さのナビゲーション経路によって到達可能な映像ショット数をリスト化している。
【００８０】
図１６に示すように、処理（２）、即ち、時間的な順序でのバランスの取れた凝集型の階層クラスタリング処理における平均ナビゲーション経路長「２.９２」は、処理（１）、即ち、純粋なバランスの取れた手法における平均ナビゲーション経路長「２.８７」よりわずかに高い。処理（３）、即ち、ツリーバランスを問題としないクラスタリング手法は、処理（２）よりも、かなり高い平均経路長「３.３７」と、はるかに高い最大経路長「５」とを有している。
【００８１】
＜IV．システムハードウェア、ソフトウェア、及び構成要素＞
図１７は、本発明の実施形態による、ディスプレイ装置及び映像ブラウザの例を示す。ディスプレイ装置１７００は、一般に、ディスプレイ１７０５、少なくとも１つのメモリ１７１０、少なくとも１つのプロセッサ１７２０、及び少なくとも１つの記憶装置又はある種のレポジトリー１７３０を備えている。装置１７００は、さらに、ソフトウェア１７４０を備えている。このソフトウェア１７４０は、ユーザが、映像をナビゲートできるようにする、本実施形態に係る「映像ブラウザ」を備えている。本実施形態では、ソフトウェアは、Ｊａｖａ（登録商標）ベースである。
【００８２】
ディスプレイ装置１７００は、映像１７５０を、例えば、記憶装置１７３０に記憶する。別法として、記憶装置１７３０及び（又は）ソフトウェア１７４０は、インターネット１７７０を介してアクセスされる遠隔コンピュータ１７６０上に保持されている。本発明の焦点は、携帯電話又はパーソナル・ディジタル・アシスタント（ＰＤＡ）などのより小型のディスプレイ装置に合わせてあるが、ディスプレイ装置は、また、コンピュータ又はテレビジョンなどの任意の他のより大きな装置とすることもできる。
【００８３】
本発明の実施形態は、本開示の教示に従ってプログラムされた従来の汎用又は専用ディジタルコンピュータ（複数も可）又はマイクロプロセッサ（複数も可）を用いて実施することができるコンピュータを用いた方法及びシステムを含むことができる。適切なソフトウェア・コーディングが、プログラマーによって、本開示の教示に基づき容易に作成可能である。本発明の実施形態は、ここで提示された特徴のうちの任意のものを行なうためのコンピュータによって実行可能な命令のプログラムを備えることができる。
【００８４】
本発明の実施形態は、コンピュータで読み取り可能な記憶媒体などのコンピュータで読み取り可能な媒体を含むことができる。コンピュータで読み取り可能な記憶媒体は、コンピュータをプログラムして、ここで提示された特徴のうちの任意のものを行なうのに使用することができる、記憶された命令を有することができる。記憶媒体は、フロッピー（登録商標）ディスク、光ディスク、ＤＶＤ、ＣＤ-ＲＯＭ、マイクロドライブ、及び磁気光ディスクを含む任意のタイプのディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＤＲＡＭ、フラッシュメモリ、又は命令及び（又は）データを記憶するのに適した任意の媒体又は装置を含むことができる（但し、これらに限定されない）。
【００８５】
本発明は、汎用／専用コンピュータ（複数も可）又はマイクロプロセッサ（複数も可）などのコンピュータのハードウェアを制御するためのソフトウェア、及びそれらと人間のユーザ又は本発明の結果を利用する他の機構との対話を可能にするためのソフトウェアの両方を含むことができる。このようなソフトウェアは、デバイスドライバ、オペレーティングシステム、実行環境／コンテナ、ユーザインタフェース、及びユーザアプリケーションを含むことができる（但し、これらに限定されない）。
【００８６】
本発明の実施形態は、本発明の処理を実行するためのコードを提供する工程を含むことができる。この提供する工程は、ユーザに任意のやり方でコードを提供する工程を含むことができる。例えば、この提供する工程は、コードを含むディジタル信号をユーザに送信する工程；物理的な媒体上のコードをユーザに提供する工程；又はコードを利用可能にする任意の他の方法を含むことができる。
【００８７】
本発明の実施形態は、本発明の実施形態の処理のうちの任意のものを行なうための、コンピュータで実行することができるコードを送信するための、コンピュータで実行される方法を含むことができる。この送信する工程は、インターネットなどのネットワークの任意の部分を介した転送；ワイヤ、大気又は空間を介した転送；又は任意の他のタイプの送信による転送を含むことができる。この送信する工程は、コードの送信を開始する工程；又は任意の領域又は国から別の領域又は国へコードを通過させる工程を含むことができる。ユーザへの送信は、その送信がそこから送られた場所を問わず、任意の領域又は国におけるユーザによって受信される任意の送信を含むことができる。
【００８８】
本発明の実施形態は、本発明の実施形態の処理のうちの任意のものを行なうためコンピュータにおいて実行することができるコードを含む信号を含むことができる。この信号は、インターネットなどのネットワークを介して；ワイヤ、大気又は空間を介して；又は任意の他のタイプの送信による信号を含むことができる。信号全体は、同時に搬送する必要はない。信号は、その転送期間に亘って、経時的に延長することができる。信号は、現在搬送されているもののスナップショットと考えるべきではない。
【００８９】
本発明の実施形態の以上の記述は、図解及び説明の目的で付与された。網羅的である意図、又は、本発明を開示された形態どおりのものに限定する意図はない。当該技術の通常の知識を有する人には、多くの修正及び変形は明らかであろう。例えば、開示された本発明の実施形態で行なわれる工程は、別の順序で行うことができ、ある工程は省略することができ、また、追加の工程を加えることができる。本発明の他の実施形態を開発することができる。しかもそれらは、本発明の主旨及び範囲、及びクレームを逸脱せずに開発することができることを理解されたい。実施形態は全て、本発明の原理及びその応用が最も良く説明されるよう選択し、かつ記述し、それにより、当該技術の通常の知識を有する他の人々が、各種の実施形態について、また、想定される特定の用途に適した各種の修正と共に本発明を理解できるようにした。本発明の範囲は、クレーム及びそれらの等価物によって定義されることが意図されている。
【図面の簡単な説明】
【００９０】
【図１】本発明の実施形態に係る映像ショットの階層例を示す図である。
【図２】本発明の実施形態に係る図１で階層の根として図示された映像全体を表わす映像ブラウザの設計例を示す図である。
【図３】本発明の実施形態に係る図１の中間の階層レベルのクラスタを表わす映像ブラウザの設計例を示す図である。
【図４】本発明の実施形態に係る図１の最低の階層レベルのクラスタを表わす映像ブラウザの設計例を示す図である。
【図５】本発明の実施形態に係る２×２グリッドの映像要素を含む映像ブラウザの設計例を示す図である。
【図６】本発明の実施形態に係る３×２グリッドの映像要素を含む映像ブラウザの設計例を示す図である。
【図７】本発明の実施形態に係る４×２グリッドの映像要素を含む映像ブラウザの設計例を示す図である。
【図８】本発明の実施形態に係る４×３グリッドの映像要素を含む映像ブラウザの設計例を示す図である。
【図９】本発明の実施形態に係る４×４グリッドの映像要素を含む映像ブラウザの設計例を示す図である。
【図１０】本発明の実施形態に係る小型の装置上の映像ショットのキーフレームのナビゲーションの例を示す図である。
【図１１】本発明の実施形態に係る、クラスタリングを初期化すると共に再帰的なクラスタリング処理を呼び出すための、処理の流れの例を示すフローチャートである。
【図１２】（Ａ）及び（Ｂ）は、本発明の実施形態に係る、時間的な順序でのボトムアップの階層クラスタリング処理とトップダウンのクラスタ要素数制限とを組み合わせて適用する再帰的な処理の例を示すフローチャートである。
【図１３】類似性クラスタリング無しで生じたバランスの取れたツリーの例を示す図である。
【図１４】本発明の実施形態による類似性クラスタリング及びツリー高さの制限を行なって生じたツリーの例を示す図である。
【図１５】類似性クラスタリングを行うと共にツリー高さに対する限界値無しで生じたツリーの例を示す図である。
【図１６】図１３〜図１５のツリーを生ずる各処理に対する処理結果を比較する表の例を示す図である。
【図１７】本発明の実施形態に係るディスプレイ装置及び映像ブラウザの例を示すブロック図である。
【特許請求の範囲】
【請求項１】
映像ショットにセグメンテーションされた映像に対して、限定された画面サイズであり且つキーフレームより大きな画面サイズを有するディスプレイ装置上でキーフレームを表示する映像ブラウザを用いて映像のナビゲーションを可能にするコンピュータを用いた映像ナビゲーション方法であって、前記方法は、
前記映像ショットの時間的な順序を維持しながら、前記映像ショットを類似性によってクラスタリングする工程と、
前記ツリーの経路長を最小限に抑えながら、前記映像ショットのクラスタに対して階層的に組織化されたナビゲーションツリーを生成する工程と、
を含む映像ナビゲーション方法。
【請求項２】
前記映像ショットをクラスタリングする工程は、
前記ツリーにおける最大葉数をｂhとして求める工程を含み、
分岐係数ｂは、前記ディスプレイ装置に表示されるキーフレームの最大数を含むと共に、前記ツリーの高さｈは、最も小さな高さを含むことにより、前記最大葉数ｂhは映像ショット数より大きいか又はそれに等しい、
ことを特徴とする、請求項１に記載の映像ナビゲーション方法。
【請求項３】
前記映像ショットをクラスタリングする工程は、
時間的に隣接した要素を有するクラスタの対を併合すると共に、併合されたクラスタ対が限界値ｂh-1を超える要素を有している場合は、その対を併合しない工程と、
ｂ個のクラスタに一旦到達したら、併合を停止する工程と、
をさらに含むことを特徴とする、請求項２に記載の映像ナビゲーション方法。
【請求項４】
前記映像ショットをクラスタリングする工程は、
前記サブクラスタの要素を再帰的にクラスタリングすると共に、各階層レベルの再帰の前に最大のクラスタ要素数をｂ分の１に減らす工程と、
をさらに含むことを特徴とする、請求項３に記載の映像ナビゲーション方法。
【請求項５】
階層的に組織化されたナビゲーションツリーを生成する工程は、
クラスタのサブクラスタリングが、併合することができるサブクラスタが無いために、ｂ個を超えるサブクラスタを生ずる場合は、そのクラスタを望ましくないとマークする工程と、
より高い階層レベルにおけるクラスタリングにおいて、前記望ましくないクラスタが生成された点まで後戻りする工程と、
望ましくないクラスタを、要素の限界値を超えるであろうクラスタのように処理しながら、クラスタリングを繰り返す工程と、
を含むことを特徴とする、請求項４に記載の映像ナビゲーション方法。
【請求項６】
前記ツリーの根がｂ個を超えるサブクラスタを有している場合は、前記ツリーの最大高さを上げると共に、クラスタリングをクラスタリングの開始点から繰り返す工程をさらに含むことを特徴とする、請求項５に記載の映像ナビゲーション方法。
【請求項７】
前記クラスタにおける第１のショットをオーバーレイされた前記クラスタにおける最も重要なショットのキーフレームを介して前記ディスプレイ装置に階層的に組織化された映像を表示する工程をさらに含むことを特徴とする、請求項１に記載の映像ナビゲーション方法。
【請求項８】
前記ディスプレイ装置にタイムラインを表示して、各クラスタに関連する映像の一部分を示す工程と、
前記ディスプレイ装置にコンテキストセンシティブ・ヘルプを表示して、前記ツリーのナビゲーションの際にユーザを助ける工程と、
をさらに含むことを特徴とする、請求項１に記載の映像ナビゲーション方法。
【請求項９】
映像ショットにセグメンテーションされた映像に対して限定された画面サイズを有するディスプレイ装置上でキーフレームを表示する映像ブラウザを用いて映像のナビゲーションを可能にする映像ナビゲーションシステムであって、前記システムは、
前記映像ショットの時間的な順序が維持されながら、類似性によってクラスタリングされた映像ショットを取得するクラスタリング手段と、
前記ツリーの経路長が最小限に抑えられながら、前記クラスタリングされた映像ショットから階層的に組織化されたナビゲーションツリーを生成するツリー生成手段と、
を含むことを特徴とする映像ナビゲーションシステム。
【請求項１０】
前記クラスタリング手段は、
前記ツリーにおける最大葉数をｂhとして求める手段を含み、
分岐係数ｂは、前記ディスプレイ装置に表示されるキーフレームの最大数を含むと共に、前記ツリーの高さｈは、最も小さな高さを含むことにより、前記最大葉数ｂhは映像ショット数より大きいか又はそれに等しい、
ことを特徴とする、請求項９に記載の映像ナビゲーションシステム。
【請求項１１】
前記クラスタリング手段は、
時間的に隣接した要素を有するクラスタの対を併合すると共に、併合されたクラスタ対が限界値ｂh-1を超える要素を有している場合は、その対を併合しない併合手段と、
ｂ個のクラスタに一旦到達したら、併合を停止する併合停止手段と、
をさらに含むことを特徴とする、請求項１０に記載の映像ナビゲーションシステム。
【請求項１２】
前記クラスタリング手段は、
前記サブクラスタの要素を再帰的にクラスタリングすると共に、各階層レベルの再帰の前に最大のクラスタ要素数をｂ分の１に減らす再帰処理手段と、
をさらに含むことを特徴とする、請求項１１に記載の映像ナビゲーションシステム。
【請求項１３】
前記ツリー生成手段は、
クラスタのサブクラスタリングが、併合することができるサブクラスタが無いために、ｂ個を超えるサブクラスタを生ずる場合は、そのクラスタを望ましくないとマークするマーキング手段と、
より高い階層レベルにおけるクラスタリングにおいて、前記望ましくないクラスタが生成された点まで後戻りする後戻り手段と、
望ましくないクラスタを、要素の限界値を超えるであろうクラスタのように処理しながら、クラスタリングを繰り返す反復処理手段と、
を含むことを特徴とする、請求項１２に記載の映像ナビゲーションシステム。
【請求項１４】
前記ツリーの根がｂ個を超えるサブクラスタを有している場合は、前記ツリーの最大高さを上げると共に、クラスタリングをクラスタリングの開始点から繰り返すツリー再生成手段をさらに含むことを特徴とする、請求項１３に記載の映像ナビゲーションシステム。
【請求項１５】
前記クラスタにおける第１のショットをオーバーレイされた前記クラスタにおける最も重要なショットのキーフレームを介して前記ディスプレイ装置に階層的に組織化された映像を表示するツリー表示手段をさらに含むことを特徴とする、請求項１４に記載の映像ナビゲーションシステム。
【請求項１６】
各クラスタに関連する映像の一部分を示すタイムラインを前記ディスプレイ装置に表示するタイムライン表示手段と、
前記ツリーのナビゲーションの際にユーザを助けるコンテキストセンシティブ・ヘルプを前記ディスプレイ装置に表示するヘルプ表示手段と、
をさらに含むことを特徴とする、請求項１５に記載の映像ナビゲーションシステム。
【請求項１７】
映像ショットにセグメンテーションされた映像に対して限定された画面サイズを有するディスプレイ装置上でキーフレームを表示する映像ブラウザを用いて映像のナビゲーションを可能にするための映像ナビゲーションプログラムであって、
コンピュータを、
前記映像ショットの時間的な順序が維持されながら、類似性によってクラスタリングされた映像ショットを取得するクラスタリング手段、
及び、前記ツリーの経路長が最小限に抑えられながら、前記クラスタリングされた映像ショットから階層的に組織化されたナビゲーションツリーを生成するツリー生成手段、
として機能させるための映像ナビゲーションプログラム。
【請求項１】
映像ショットにセグメンテーションされた映像に対して、限定された画面サイズであり且つキーフレームより大きな画面サイズを有するディスプレイ装置上でキーフレームを表示する映像ブラウザを用いて映像のナビゲーションを可能にするコンピュータを用いた映像ナビゲーション方法であって、前記方法は、
前記映像ショットの時間的な順序を維持しながら、前記映像ショットを類似性によってクラスタリングする工程と、
前記ツリーの経路長を最小限に抑えながら、前記映像ショットのクラスタに対して階層的に組織化されたナビゲーションツリーを生成する工程と、
を含む映像ナビゲーション方法。
【請求項２】
前記映像ショットをクラスタリングする工程は、
前記ツリーにおける最大葉数をｂhとして求める工程を含み、
分岐係数ｂは、前記ディスプレイ装置に表示されるキーフレームの最大数を含むと共に、前記ツリーの高さｈは、最も小さな高さを含むことにより、前記最大葉数ｂhは映像ショット数より大きいか又はそれに等しい、
ことを特徴とする、請求項１に記載の映像ナビゲーション方法。
【請求項３】
前記映像ショットをクラスタリングする工程は、
時間的に隣接した要素を有するクラスタの対を併合すると共に、併合されたクラスタ対が限界値ｂh-1を超える要素を有している場合は、その対を併合しない工程と、
ｂ個のクラスタに一旦到達したら、併合を停止する工程と、
をさらに含むことを特徴とする、請求項２に記載の映像ナビゲーション方法。
【請求項４】
前記映像ショットをクラスタリングする工程は、
前記サブクラスタの要素を再帰的にクラスタリングすると共に、各階層レベルの再帰の前に最大のクラスタ要素数をｂ分の１に減らす工程と、
をさらに含むことを特徴とする、請求項３に記載の映像ナビゲーション方法。
【請求項５】
階層的に組織化されたナビゲーションツリーを生成する工程は、
クラスタのサブクラスタリングが、併合することができるサブクラスタが無いために、ｂ個を超えるサブクラスタを生ずる場合は、そのクラスタを望ましくないとマークする工程と、
より高い階層レベルにおけるクラスタリングにおいて、前記望ましくないクラスタが生成された点まで後戻りする工程と、
望ましくないクラスタを、要素の限界値を超えるであろうクラスタのように処理しながら、クラスタリングを繰り返す工程と、
を含むことを特徴とする、請求項４に記載の映像ナビゲーション方法。
【請求項６】
前記ツリーの根がｂ個を超えるサブクラスタを有している場合は、前記ツリーの最大高さを上げると共に、クラスタリングをクラスタリングの開始点から繰り返す工程をさらに含むことを特徴とする、請求項５に記載の映像ナビゲーション方法。
【請求項７】
前記クラスタにおける第１のショットをオーバーレイされた前記クラスタにおける最も重要なショットのキーフレームを介して前記ディスプレイ装置に階層的に組織化された映像を表示する工程をさらに含むことを特徴とする、請求項１に記載の映像ナビゲーション方法。
【請求項８】
前記ディスプレイ装置にタイムラインを表示して、各クラスタに関連する映像の一部分を示す工程と、
前記ディスプレイ装置にコンテキストセンシティブ・ヘルプを表示して、前記ツリーのナビゲーションの際にユーザを助ける工程と、
をさらに含むことを特徴とする、請求項１に記載の映像ナビゲーション方法。
【請求項９】
映像ショットにセグメンテーションされた映像に対して限定された画面サイズを有するディスプレイ装置上でキーフレームを表示する映像ブラウザを用いて映像のナビゲーションを可能にする映像ナビゲーションシステムであって、前記システムは、
前記映像ショットの時間的な順序が維持されながら、類似性によってクラスタリングされた映像ショットを取得するクラスタリング手段と、
前記ツリーの経路長が最小限に抑えられながら、前記クラスタリングされた映像ショットから階層的に組織化されたナビゲーションツリーを生成するツリー生成手段と、
を含むことを特徴とする映像ナビゲーションシステム。
【請求項１０】
前記クラスタリング手段は、
前記ツリーにおける最大葉数をｂhとして求める手段を含み、
分岐係数ｂは、前記ディスプレイ装置に表示されるキーフレームの最大数を含むと共に、前記ツリーの高さｈは、最も小さな高さを含むことにより、前記最大葉数ｂhは映像ショット数より大きいか又はそれに等しい、
ことを特徴とする、請求項９に記載の映像ナビゲーションシステム。
【請求項１１】
前記クラスタリング手段は、
時間的に隣接した要素を有するクラスタの対を併合すると共に、併合されたクラスタ対が限界値ｂh-1を超える要素を有している場合は、その対を併合しない併合手段と、
ｂ個のクラスタに一旦到達したら、併合を停止する併合停止手段と、
をさらに含むことを特徴とする、請求項１０に記載の映像ナビゲーションシステム。
【請求項１２】
前記クラスタリング手段は、
前記サブクラスタの要素を再帰的にクラスタリングすると共に、各階層レベルの再帰の前に最大のクラスタ要素数をｂ分の１に減らす再帰処理手段と、
をさらに含むことを特徴とする、請求項１１に記載の映像ナビゲーションシステム。
【請求項１３】
前記ツリー生成手段は、
クラスタのサブクラスタリングが、併合することができるサブクラスタが無いために、ｂ個を超えるサブクラスタを生ずる場合は、そのクラスタを望ましくないとマークするマーキング手段と、
より高い階層レベルにおけるクラスタリングにおいて、前記望ましくないクラスタが生成された点まで後戻りする後戻り手段と、
望ましくないクラスタを、要素の限界値を超えるであろうクラスタのように処理しながら、クラスタリングを繰り返す反復処理手段と、
を含むことを特徴とする、請求項１２に記載の映像ナビゲーションシステム。
【請求項１４】
前記ツリーの根がｂ個を超えるサブクラスタを有している場合は、前記ツリーの最大高さを上げると共に、クラスタリングをクラスタリングの開始点から繰り返すツリー再生成手段をさらに含むことを特徴とする、請求項１３に記載の映像ナビゲーションシステム。
【請求項１５】
前記クラスタにおける第１のショットをオーバーレイされた前記クラスタにおける最も重要なショットのキーフレームを介して前記ディスプレイ装置に階層的に組織化された映像を表示するツリー表示手段をさらに含むことを特徴とする、請求項１４に記載の映像ナビゲーションシステム。
【請求項１６】
各クラスタに関連する映像の一部分を示すタイムラインを前記ディスプレイ装置に表示するタイムライン表示手段と、
前記ツリーのナビゲーションの際にユーザを助けるコンテキストセンシティブ・ヘルプを前記ディスプレイ装置に表示するヘルプ表示手段と、
をさらに含むことを特徴とする、請求項１５に記載の映像ナビゲーションシステム。
【請求項１７】
映像ショットにセグメンテーションされた映像に対して限定された画面サイズを有するディスプレイ装置上でキーフレームを表示する映像ブラウザを用いて映像のナビゲーションを可能にするための映像ナビゲーションプログラムであって、
コンピュータを、
前記映像ショットの時間的な順序が維持されながら、類似性によってクラスタリングされた映像ショットを取得するクラスタリング手段、
及び、前記ツリーの経路長が最小限に抑えられながら、前記クラスタリングされた映像ショットから階層的に組織化されたナビゲーションツリーを生成するツリー生成手段、
として機能させるための映像ナビゲーションプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１６】
【図１７】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１６】
【図１７】
【図１３】
【図１４】
【図１５】
【公開番号】特開２０１０−２８１８４（Ｐ２０１０−２８１８４Ａ）
【公開日】平成２２年２月４日（２０１０．２．４）
【国際特許分類】
【出願番号】特願２００８−１８３６２８（Ｐ２００８−１８３６２８）
【出願日】平成２０年７月１５日（２００８．７．１５）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
【公開日】平成２２年２月４日（２０１０．２．４）
【国際特許分類】
【出願日】平成２０年７月１５日（２００８．７．１５）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
[ Back to top ]