JPH08263468A - マルチメディア・ストーリ提供方法及び装置 - Google Patents

Abstract

(57)【要約】 【課題】 マルチメディア・エピソードを構成及び再生
するための改良された方法及び装置を提供する。 【解決手段】 マルチメディア・システムがマルチメデ
ィア・オブジェクトを時間間隔の範囲として表現し、各
時間間隔が最小及び最大により制限され、時間関係がオ
ブジェクトの統合セットに提供される。時間的な不確定
性を有するこうしたシステムでは伸縮可能なタイムライ
ンが提供される。このタイムラインはバネ系に則って、
オブジェクトが最小及び最大長だけでなく、静止長にも
関連付けられるようにモデル化される。バネが特定の長
さにおいて静止し、力が加えられると特定の度合いで伸
縮するように、上記タイムライン上に配置されるマルチ
メディア・オブジェクトも特定の長さで静止し、必要に
応じて伸縮しうる。バネは静止長に復帰する傾向がある
ので、マルチメディア・オブジェクトも必要に応じて可
能な最小の度合いで伸縮しうる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は一般に、コンピュー
タ・システム上でマルチメディア文書を可変再生時間に
より構成及び再生することに関し、特に、マルチメディ
ア文書再生時間が可変されるときに、文書内のマルチメ
ディア・エピソードが時間的に正しく提供されるよう
に、これらを構成及び再生することに関する。

【０００２】

【従来の技術】電子マルチメディア文書は、百科辞典な
どのマルチメディア文書を記憶するために普及しつつあ
る。なぜならこの媒体は、テキスト、図形、動画ビデ
オ、音声など（これらが結合されてマルチメディア文書
を形成する）を含む大量のデータを記憶することができ
るからである。マルチメディア文書のユーザは、通常、
コンピュータ入出力を介して、フラグメント、セグメン
トまたはマルチメディア・オブジェクトと呼ばれる（以
降ではエピソード（episode）として参照する）マルチ
メディア情報を提供または受信する。一般に、これらの
マルチメディア・エピソードは、音声及びビデオ・クリ
ップ、音楽レコーディング、スピーチ、タイプ入力テキ
スト、静止画、図面、動画、舞踏ダンス・ステップなど
の、音声及びビジュアル情報形式を取りうる知覚的性質
を有する情報を含む。

【０００３】コンピュータの出力として提供されるエピ
ソードは"再生（played）"されると言われる。ビジュア
ル出力は表示（display）として再生され、音声出力は
音響（sound）として再生され、時に表示を伴う。マル
チメディア文書を構成または再生するためにコンピュー
タ・ユーザは１つ以上のエピソードを選択し、それらを
特定の順序で再生しなければならず、その順序は順次的
若しくは同時、またはオーバラップしうる。マルチメデ
ィア文書が特定の種類の時間的制限により構成及び（ま
たは）再生される関連エピソードを有する場合、これは
ストーリと呼ばれる。

【０００４】小数のエピソードを有するストーリを構成
または再生することは比較的容易であるが、特定の従来
方法では非常に多数のエピソードを有するストーリを構
成または再生することができない。更に特定の従来方法
は、可変時間において再生されうるエピソードをスケジ
ュールする方法を提供しない。可変再生時間のエピソー
ドをスケジュールする方法を提供する従来方法は、ユー
ザが大域再生時間、すなわちストーリ全体の再生に要す
る時間を制限することを可能にしない。更に従来方法
は、ストーリの再生の間に最適エピソード再生時間とス
ケジュールされるエピソード再生時間との差の変化を均
等に分配しない。

【０００５】

【発明が解決しようとする課題】従って本発明の目的
は、マルチメディア・エピソードを構成及び再生するた
めの改良された方法及び装置を提供することである。

【０００６】本発明の別の目的は、マルチメディア・ス
トーリを可変大域再生時間により再生する改良された方
法及び装置を提供することである。

【０００７】本発明の更に別の目的は、マルチメディア
・ストーリの大域再生時間の可変性を識別し、ユーザに
大域再生時間を選択する機能を提供する改良された方法
及び装置を提供することである。

【０００８】更に本発明の別の目的は、ストーリの大域
再生時間を複数の大域再生時間から選択し、エピソード
再生時間をストーリ内で公正にスケジュールする改良さ
れた方法及び装置を提供することである。

【０００９】

【課題を解決するための手段】本発明によれば、マルチ
メディア・オブジェクトが時間間隔の範囲として表現さ
れるマルチメディア・システムが提供され、各時間間隔
は最小及び最大により制限され、時間関係がオブジェク
トの統合セットに提供される。時間的な不確定性を有す
るこうしたシステムでは、伸縮可能なタイムラインが提
供される。伸縮可能なタイムラインはバネ系に則って、
オブジェクト（またはバネ）が最小及び最大長だけでな
く静止長（length at rest）にも関連付けられるように
モデル化される。バネが特定の長さにおいて静止し、力
が加えられると特定の度合いで伸縮するように、伸縮可
能なタイムライン上に配置されるマルチメディア・オブ
ジェクトも特定の長さで静止し必要に応じて伸縮しう
る。バネは静止長に復帰する傾向があるので、マルチメ
ディア・オブジェクトも必要に応じて可能な最小の度合
いで伸縮しうる。本発明によるシステムは、"このマル
チメディア表現を１０分以内で提供できるか？もし可能
であればどのように全てのオブジェクトがスケジュール
されるべきか？"と言った質問に応えることができる。
全ての所与の制限を満足する解が存在するとき、その解
は対応する静止長から"最小に"逸脱する時間間隔のセッ
トを含み、また最適長（静止長）と所与の時間間隔（ス
ケジュール時間）との差の変化が均等に分配される。

【００１０】

【発明の実施の形態】図１を参照すると、代表的なハー
ドウェア環境が示され、これは例えばＩＢＭのPersonal
System/2（ＰＳ／２）ファミリのパーソナル・コンピ
ュータなどによる。このハードウェアには中央処理ユニ
ット（ＣＰＵ）１０が含まれ、これはインテル社のＸ８
６アーキテクチャに準拠するものであったり、ＩＢＭの
PowerPCマイクロプロセッサなどの、縮小命令セット・
コンピュータ（ＲＩＳＣ）マイクロプロセッサなどであ
る。ＣＰＵ１０はシステム・バス１２に接続され、シス
テム・バス１２には更に、読出し／書込み用メモリすな
わちランダム・アクセス・メモリ（ＲＡＭ）１４、読出
し専用メモリ（ＲＯＭ）１６、入出力（Ｉ／Ｏ）アダプ
タ１８、及びユーザ・インタフェース・アダプタ２２が
接続される。ＲＡＭ１４は、アプリケーション・プログ
ラム・コード及びデータのための一時記憶を提供し、Ｒ
ＯＭ１６は通常、基本入出力システム（ＢＩＯＳ）コー
ドを含む。Ｉ／Ｏアダプタ１８は１つ以上の直接アクセ
ス記憶装置（ＤＡＳＤ）に接続され、図１ではＤＡＳＤ
がフロッピー・ドライブ１９、ハードディスク・ドライ
ブ２０、及びＣＤ−ＲＯＭ２１として表されている。ハ
ードディスク・ドライブ２０は通常、コンピュータのオ
ペレーティング・システム（ＯＳ）（例えばＩＢＭのＯ
Ｓ／２オペレーティング・システム）及び様々なアプリ
ケーション・プログラムを記憶する。こうした各アプリ
ケーション・プログラムは、システム・バス１２を介し
て、ＲＡＭ１４に選択的にロードされる。ユーザ・イン
タフェース・アダプタ２２は、キーボード２４、マウス
２６、及び（または）他のユーザ・インタフェース装置
（図示せず）をシステム・バス１２に接続する。

【００１１】パーソナル・コンピュータまたはワークス
テーションは表示装置３８を含み、図１ではこれは陰極
線管（ＣＲＴ）表示装置として示されるが、液晶表示装
置（ＬＣＤ）または他の好適な表示装置であってもよ
い。表示装置３８は表示アダプタ３６を介してシステム
・バス１２に接続される。インテル社のActionMedia II
表示アダプタなどのマルチメディア・アダプタが、シス
テム・バス１２及びマイク３２、スピーカ２８、並び
に、音声／ビデオ捕獲及び再生のためのビデオ・カメラ
３０に接続される。マルチメディア・アダプタ３４は、
例えばＩＢＭのマルチメディア・プレゼンテーション・
マネージャ／２などの好適なソフトウェアによりサポー
トされる。当業者には理解されるように、他のマルチメ
ディア・ハードウェア及びソフトウェアも、システムに
組み込まれることが可能であり、こうしたものには、例
えばビデオ・カセット・レコーダ（ＶＣＲ）、レーザ・
ディスク・プレーヤ、サランド・サウンド（surround s
ound）・プロセッサなどが含まれる。

【００１２】本発明の実施では、ストーリ内のマルチメ
ディア・オブジェクトは、それらが再生される時間間隔
を定義するものと見なされる。最小及び最大により制限
される時間間隔の範囲を扱うことができれば好都合であ
る。例えば、ビデオ・セグメントは３０フレーム／秒、
或いはそれよりも遅いまたは速いレートで再生される。
同様に、音声セグメント、図形動画、テキスト・セグメ
ントまたは静止フレームも、それらが提供される受諾速
度の範囲及び再生時間に関連付けられうる。所与の制限
に依存して適切な速度が各セグメントに対応して選択さ
れうる。その結果、伸縮性が有用となる。直観的には表
現を伸縮可能なタイムラインにマッピングすることを考
えてみよう。類比的に所与の関係に従い接続されるバネ
のセットを含むマルチメディア表現を想像されたい。こ
の類比によれば、各マルチメディア・オブジェクトが３
つ組の長さに関連付けられ、バネの圧縮時の長さに対応
して最小長に、伸長時の長さに対応して最大長に、また
静止時に対応して最適長に関連付けられる。

【００１３】マルチメディア・ストーリは、エピソード
のリストから選択することにより構成される。各エピソ
ードは、上述の３つ組の長さに関連付けられねばならな
い。これは例えば、図２に示されるユーザ対話画面を用
いて達成される。エピソードのリストからエピソードが
選択される。選択エピソードは画面の左上隅に、アイコ
ン２０１により図式的に表現される。ユーザはポインテ
ィング・カーソルにより、それぞれ"最小"、"最適"また
は"最大"に対応するボタン２０２、２０３または２０４
をクリックすることにより、３つ組の長さの１つを選択
する。次にスライダ２０５をクリックし、タイムライン
２０６上でドラッグすることによりユーザは時間を設定
する。図示の例ではユーザは"最適"に対応するボタン２
０３を選択しており、スライダ２０５を１０秒に設定し
ている。代わりにユーザはウィンドウ２０７内に時間を
タイプ入力することもできる。ウィンドウ２０７及びス
ライダ２０５内に示される時間は、スライダが移動され
るとき、ウィンドウ内に表示される値がその移動に従い
変化するように、また反対に、ウィンドウ２０７内への
タイプ入力値に従いスライダ２０５が移動するようにリ
ンクされる。ユーザは選択長に対応する値に満足する
と"設定"ボタン２０８を選択し、そして３つ組の全ての
長さを選択すると"完了"ボタン２０９を選択する。"完
了"ボタン２０８を選択する以前の任意の時点で"取り消
し"ボタン２１０を選択すると、そのプロセスが取り消
される。図示の例では最小長が２秒、最大長が１９．９
秒に選択されている。タイムライン２０６の端部の矢印
ボタン２１１及び２１２は、スライダ２０５を１ステッ
プ毎に移動するために使用されうる。図ではタイムライ
ンが０秒乃至２０秒に及ぶように示されるが、ウィンド
ウの下隅の矢印ボタン２１３または２１４のいずれか適
切な方を選択することにより、この範囲を伸縮すること
が可能である。従って、ストーリを形成する様々なエピ
ソードに対応して広い範囲の時間に調整することができ
る。

【００１４】図２に示されるユーザ対話画面は、エピソ
ード・リスト内の各エピソードに対応して３つ組の長さ
を設定するために使用されうる１例であり、他の技法も
使用されうる。要するに、各エピソードに対応して３つ
組の長さがシステムに入力されることが必要である。

【００１５】一般的に、マルチメディア・オーサリング
（authoring）は、ビデオ・セグメント、イメージ、図
形、音声セグメント、またはテキスト・セグメントなど
のマルチメディア・オブジェクトの順序付けまたは統合
プロセスである。特定の順序付けが提供されたマルチメ
ディア・オブジェクトのセットはストーリと呼ばれる。
ストーリに関するオブジェクトの順序付けは、時間次元
と空間次元の両者において実行されうる。本発明は特
に、時間的レイアウトを獲得する問題、またはマルチメ
ディア・オブジェクトを時間次元において順序付けする
問題に関する。時間はマルチメディア・システムにおい
て本質的な次元であり、しばしばマルチメディア・オブ
ジェクトの基本測定（basic measure）を提供する。時
間はまた、様々なマルチメディア・オブジェクトを相関
付ける参照を提供する。従来、時間に関する推理が人口
知能（ＡＩ）分野における多くの研究活動のテーマであ
り、多くの形式主義（formalism）が時間推理に対応し
て提案された。

【００１６】本発明は、互いに関係を有しうる、または
有さないマルチメディア・セグメント／オブジェクトの
セットを使用する。ストーリ内で使用されるこれらのセ
グメントのサブセットが選択される。選択セグメントは
ストーリのエピソードと呼ばれる。ストーリ内のエピソ
ードは、ストーリを定義するように一緒にスケジュール
される。このスケジューリングは時間的レイアウトにお
いて表現されうる。時間的レイアウトは時間制限を有す
る。図３乃至図６は４つのタイプの時間制限の例を示
す。図３では矩形ボックスにより表される２つのエピソ
ードＡ及びＢが順次的にスケジュールされ、従ってエピ
ソードＡの終りにエピソードＢが開始するようにスケジ
ュールされる。この時間制限は"meet（Ａ,Ｂ）"と命名
される。等価の時間制限グラフでは、ノードＡが、ノー
ドＡからノードＢを指し示す矢印を介してノードＢに接
続される。図４では、エピソードＡ及びＢが同時に開始
するようにスケジュールされる。この時間制限は"cobeg
in（Ａ,Ｂ）"と命名される。時間制限グラフでは、点線
で示されるダミー・ノードが、ノードＡ及びＢを指し示
すそれぞれの矢印を介してノードＡ及びＢの両者に接続
される。図５では、エピソードＡ及びＢが同時に終了す
るようにスケジュールされる。この時間制限は"coend
（Ａ,Ｂ）"と命名される。時間制限グラフでは、ノード
Ａ及びＢが、ダミー・ノードを指し示すそれぞれの矢印
を介してダミー・ノードに接続される。図６では、エピ
ソードＡ及びＢが同時に開始し、同時に終了するように
スケジュールされる。この時間制限は"co-occur（Ａ,
Ｂ）"と命名される。時間制限グラフは、"cobegin（Ａ,
Ｂ）"及び"coend（Ａ,Ｂ）"に対応する時間制限グラフ
の組合わせである。

【００１７】図７は、様々な時刻において異なる時間を
有して発生する複数エピソードを有するストーリの例を
示す。"ビデオ１"、"テキスト"及び"音声１"としてそれ
ぞれ識別される３つのエピソード４０１、４０２及び４
０３が図４の場合のように同時に開始する。時間関係が
４０４に"cobegin（ビデオ１,テキスト）"として、及び
４０５に"cobegin（テキスト,音声１）"として示され
る。"ビデオ２"として識別されるエピソード４０６は、
図３の場合のようにエピソード４０１の終了後に開始す
る。時間関係は４０７に"meet（ビデオ１,ビデオ２）"
として示される。第５のエピソード４０８は"描画"とし
て識別され、エピソード４０６の間に発生し、図５の場
合のようにエピソード４０６と一緒に終了する。４０９
に示される時間関係は"coend（ビデオ２,描画）"であ
る。第３のエピソード４０３もエピソード４０６及び４
０８と一緒に終了する。４１０に示される時間関係は"c
oend（描画,音声１）"である。或いは、エピソード４０
１及び４０６を組合わせと見なすと、これら２つのエピ
ソード及びエピソード４０３の組合わせが図６の場合の
ように一緒に開始し一緒に終了する。時間関係は"co-oc
cur（ビデオ１,ビデオ２）"として表現されうる。

【００１８】本発明の実施においてこれらの時間関係が
確立される１方法は、図８に示されるユーザ対話画面に
よる。ストーリに対応して使用可能なエピソードがエピ
ソード・リストから選択され、図形画面の"カンバス（c
anvas）"域５０１に個々のアイコンとして表示される。
ユーザはポインティング・カーソル（ここでは矢印５０
２として示される）により、１対のエピソード・アイコ
ンをクリックすることによりそれらを選択する。次に、
カンバス域５０１上に開かれるウィンドウ５０３内のボ
タンを用いてユーザは所望の時間関係を選択する。４つ
の時間関係ボタン、すなわち関係"meet"に対応するボタ
ン５０４、関係"cobegin"に対応するボタン５０５、関
係"coend"に対応するボタン５０６、及び関係"co-occu
r"に対応するボタン５０７が示される。３つの他のボタ
ンが更にウィンドウ５０３内に示される。それらは"分
離（separate）"に対応するボタン５０８、"除去（remo
ve）"に対応するボタン５０９、及び"変更（change）"
に対応するボタン５１０である。分離ボタン５０８は、
ストーリ内の２つのエピソード間で時間関係を除去する
ことを可能にし、除去ボタン５０９はストーリからある
エピソードを除去することを可能にする。時間関係ボタ
ン５０４乃至５０７との組合わせにより、ボタン５０８
及び５０９はマルチメディア・ストーリを創作するため
の基本編集ツールである。プロセスがストーリ・"カン
バス"５０１上に図形表示５１１を生成する。アイコン
５１２により表されるエピソードなどのストーリにまだ
組み込まれていないエピソードは、ユーザによる創作の
間にストーリの図形表現の脇に示される。エピソード・
アイコン及び変更ボタン５１０を選択することにより図
２に示される画面が表示され、ユーザはそのエピソード
に対応する３つ組の長さを変更することができる。

【００１９】本発明の好適な実施例は、図１に一般に示
されるようなハードウェア・プラットフォーム上で実現
される。図９乃至図１１は本発明のオペレーションの論
理を示すフローチャートである。この時点において、ユ
ーザは既に図８に示されるような編集ツールを用いてマ
ルチメディア・ストーリを既に創作しており、ストーリ
内の個々のエピソードの再生時間を時間制限及び３つの
バネ定数に従い調整することが所望される。プロセスは
入力ブロック６０１で、時間制限及び３つのバネ定数を
入力することにより開始する。これは例えば、図８及び
図２に示されるような画面を用いて達成される。入力は
機能ブロック６０２で一貫性をチェックされる。次に判
断ブロック６０３で、機能ブロック６０２におけるチェ
ックにもとづき入力が一貫するか否かが判断される。矛
盾が見い出されるとこのことが出力ブロック６０４でユ
ーザに報告され、プロセスは停止する。時間制限網にお
ける矛盾のチェック・プロセスについては、R．Dechte
r、I．Meiri及びJ．Pearlによる"Temporal Constraint
Networks"（Artificial Intelligence、49、1991、pp．
61-95）に述べられている。

【００２０】矛盾が見い出されないものと仮定すると、
機能ブロック６０５における次のステップで大域最小長
及び最大長（これについてもR．Dechterらによる上記参
考文献で述べられる）を獲得する。図１２に示される時
間制限テーブルが、機能ブロック６０６で構築される。
このテーブルを用いて同等の再生時間のパスのセットが
機能ブロック６０７で決定される。機能ブロック６０７
により生成される方程式のセットがバネ定数と一緒に機
能ブロック６０８に入力として提供され、最小コストか
つ公正なスケジュールを生成する。より詳細には、機能
ブロック６０８において各エピソードの最小コストかつ
公正なスケジュール、及び大域再生時間のために、大域
長制限を用いることなく探索が実施される。これは２次
計画法（quadratic programming）などの、既知の探索
技術を用いて達成される（S．Glassによる"Linear Prog
ramming Methods and Applications"、McGraw-Hill（19
75）参照）。

【００２１】エピソード再生の"コスト"は、エピソード
の指定最適再生時間とスケジュール再生時間との差とし
て定義される。最小コストのスケジュールとは、スケジ
ュール（すなわち各エピソードへの再生時間の割当て）
結果において、各エピソードの再生コストの合計が、時
間制限並びに指定の下限及び上限を満足する再生時間の
全ての可能な正当な割当てに対して最小となることを意
味する。公正なスケジュールとは、再生コストの合計の
分配がエピソード間で均等であることを意味する。すな
わち、あるエピソードは良好な品質（すなわち小さな再
生コスト）により再生されず、別のエピソードは低品質
（すなわち大きな再生コスト）により再生される。公正
なスケジュールでは２つのエピソードがほぼ同一の品質
により再生される。

【００２２】機能ブロック６０８の探索の結果は、スト
ーリ内の各エピソードに対する最小コストかつ公正な再
生時間、及び大域再生時間である。この大域再生時間
（ブロック６０８で生成される）及び大域最小長及び最
大長（ブロック６０５で生成される）が機能ブロック６
０９でユーザに報告される。ユーザは判断ブロック６１
０で、この大域再生時間を受諾するかまたは拒絶するか
を促される。結果が受諾される場合、出力ブロック６１
１でマルチメディア・ストーリに対応するスケジュール
が出力され、マルチメディア文書がそのスケジュールに
従い実行され、プロセスは終了する。

【００２３】本発明の特定の特長はその柔軟性であり、
この場合にはユーザが大域長を拒絶することを可能にす
る。それによりユーザは機能ブロック６１２で、ブロッ
ク６０９で報告された大域最小長と最大長との間で大域
長を入力するように促される。次に機能ブロック６１３
で大域長制限が時間制限テーブルに追加される。プロセ
スはその後、時間制限テーブルに対してこの追加が繰り
返される。より詳細には、同等の再生時間を有するパス
のセットが機能ブロック６１４で決定される。機能ブロ
ック６１４で生成される方程式のセットが、バネ定数と
一緒に機能ブロック６１５に入力として提供される。最
小コストかつ公正なスケジュールに対する探索が、今度
は大域長制限を用いて機能ブロック６１５で実行され
る。次に出力ブロック６１６でスケジュールが出力さ
れ、マルチメディア文書が実行される。

【００２４】図１２に示される時間制限テーブルは、図
１３乃至図１５のフローチャートに示されるプロセスに
より構築される。ここで表記"Table（Ａ,Ｂ）＝１"（Ａ
は行、Ｂは列を表す）は、エピソードＡの終りにエピソ
ードＢが再生を開始することを意味する。このプロシー
ジャは、図９に示される機能ブロック６０６（及び多
分、図１１の機能ブロック６１３）により呼ばれ、図１
３の機能ブロック８０１でｎ行及びｎ列のテーブルによ
り開始する。ここでｎはオブジェクトまたはエピソード
の数である。テーブル内の全ての要素が機能ブロック８
０２で０とマークされ、機能ブロック８０３で関係が選
択される。すなわち、時間制限により関連付けられる１
対のエピソード（すなわちオブジェクト）が選択され
る。選択対の間の時間制限は最初は"現制限"である。判
断ブロック８０４では、４つのタイプの時間制限のどれ
が現制限であるかが判断される。この判断にもとづき、
プロセスは分岐する。

【００２５】現制限が"meet（Ａ,Ｂ）"の場合、時間制
限テーブル内の行Ａ及び列Ｂに対応して"１"が機能ブロ
ック８０５で入力される。これはエピソード（オブジェ
クト）ＢがエピソードＡの後に発生することを示す。次
に判断ブロック８０６（図１４）で処理されるべき他の
残りの関係が存在するか否かが判断される。肯定の場
合、機能ブロック８０７で次の関係が選択され、プロセ
スは判断ブロック８０４に戻り、この次の関係の制限の
タイプを判断する。例えば制限が"cobegin（Ａ,Ｂ）"の
場合、プロセスは機能ブロック８０８に分岐し、ダミー
・ノードがテーブルに追加される。これは例えば"ダミ
ー１"行及び列をテーブルに追加することにより達成さ
れる（図１２参照）。次に機能ブロック８０９（図１
４）で、行"ダミーｉ"、列Ａに対して"１"がテーブルに
入力される。これはエピソード（オブジェクト）Ａが"
ダミーｉ"の後に発生することを示す。同様に、行"ダミ
ーｉ"、列Ｂに対しても"１"がテーブルに入力され、エ
ピソード（オブジェクト）Ｂが"ダミーｉ"の後に発生す
ることを示す。次に判断ブロック８０６で、再度、処理
されるべき他の残りの関係が存在するか否かが判断され
る。肯定の場合、次の関係が機能ブロック８０７で選択
され、プロセスは再度判断ブロック８０４に戻り、この
次の関係の制限のタイプを判断する。例えば制限が"coe
nd（Ａ,Ｂ）"の場合、プロセスは機能ブロック８１０
（図１４）に分岐し、再度ダミー・ノードがテーブルに
追加される。これは例えば"ダミー２"行及び列をテーブ
ルに追加することにより達成される。次に機能ブロック
８１１で、行Ａ、列"ダミーｉ"に対して"１"がテーブル
に入力され、エピソード（オブジェクト）Ａが"ダミー
ｉ"以前に発生することを示す。同様に行Ｂ、列"ダミ
ー"に対しても"１"がテーブルに入力され、エピソード
（オブジェクト）Ｂが"ダミーｉ"以前に発生することを
示す。次に判断ブロック８０６で処理されるべき他の残
りの関係が存在するか否かが判断される。肯定の場合、
次の関係が機能ブロック８０７で選択され、プロセスは
判断ブロック８０４に戻り、この次の関係の制限のタイ
プを判断する。例えば制限が"co-occur（Ａ,Ｂ）"の場
合、プロセスは機能ブロック８１２（図１４）に分岐す
る。この時間制限に対して２つのダミー・ノードがテー
ブルに追加される。これは例えば"ダミーｉ"及び"ダミ
ーｊ"行及び列をテーブルに追加することにより達成さ
れる。次に機能ブロック８１４で、行"ダミーｉ"、列Ａ
に対して"１"がテーブルに入力され、エピソード（オブ
ジェクト）Ａが"ダミーｉ"の後に発生することを示す。
同様に、行"ダミーｉ"、列Ｂに対しても"１"がテーブル
に入力され、エピソード（オブジェクト）Ｂが"ダミー
ｉ"の後に発生することを示す。また、行Ａ、列"ダミー
ｊ"に対して"１"がテーブルに入力され、エピソード
（オブジェクト）Ａが"ダミーｊ"以前に発生することを
示す。同様に、行Ｂ、列"ダミーｊ"に対しても"１"がテ
ーブルに入力され、エピソード（オブジェクト）Ｂが"
ダミーｊ"以前に発生することを示す。次に判断ブロッ
ク８０６で、処理されるべき他の残りの関係が存在する
か否かが判断される。否定の場合、プロセスは機能ブロ
ック８１５（図１５）に移行し、ルート・ダミーがテー
ブルに追加される。次に機能ブロック８１６で、別のエ
ピソード（オブジェクト）により時間的に先行されない
テーブル内の各エピソード、すなわち入力度（indegre
e）が０であるオブジェクトに対して、フロント・ダミ
ーすなわち"フロントｉ"がテーブルに追加される。次に
テーブル内の行"ルート"、列"フロントｉ"に"１"が設定
され、別の"１"が行"フロントｉ"、列"オブジェクト"に
設定される。同様にしてテール・ダミーが機能ブロック
８１７で追加され、次に機能ブロック８１８で、別のオ
ブジェクトにより後続されない各オブジェクト（すなわ
ち出力度（outdegree）が０）に対して後続ダミー、す
なわち"ビハインドｉ"がテーブルに追加される。次にテ
ーブル内の行"オブジェクト"、列"ビハインドｉ"に"１"
が設定され、行"ビハインドｉ"、列"テール"に別の"１"
が設定される。完了したテーブルが出力ブロック８１９
で出力され、図９乃至図１１の主フローチャートで述べ
られる計算において使用される。

【００２６】上述のプロセスは例を示すことにより、よ
り明確に理解されよう。ここで図１６が、機能ブロック
８１５以降のオペレーション以前のオリジナル時間制限
グラフを示し、図１８が、図１６のグラフに対応する時
間制限テーブルを示すものとする。図１８のテーブルか
ら図１６の時間制限グラフに対応して、エピソードＣが
エピソードＡ及びＢの後に開始し、エピソードＤ及びＥ
がエピソードＣの後に開始することが理解される。機能
ブロック８１５乃至８１８において、それぞれルート・
ダミー、フロント・ダミー、テール・ダミー、及び後続
ダミーを追加するプロセスの結果、図１７に示される時
間制限グラフが生成され、これに対応する時間制限テー
ブルが図１９に示される。

【００２７】図１０及び図１１に戻り、機能ブロック６
０７及び６１４における計算のプロシージャが、図２０
乃至図２２のフローチャートに示されるプロシージャに
従い実行される。図２０乃至図２２を参照すると、同等
の再生時間を有するパスのセットの制限を決定するプロ
セスは図１２に示されるテーブルを使用する。プロセス
は機能ブロック９０１でｉを１に設定することにより開
始される。次に判断ブロック９０２で、ルート・ノード
の行ｒ、列ｉに対応するテーブル入力が"１"に設定され
ているか否かを判断する。行ｒ（ルート）、列ｉに対応
するテーブル入力が０の場合、ｉが機能ブロック９０３
で１だけ増分され、判断ブロック９０４でｉがＮ以下か
否かが判断される。ここでＮはテーブル内の行及び列の
数、すなわちテーブル内のノードの数である。肯定の場
合、プロセスは判断ブロック９０２にループして戻る。
ｉがルート・ノードｒより後の場合（Table（ｒ,ｉ）＝
１）、機能ブロック９０５でpath（ｉ,１）が＜ｒ＞に
設定され、参照カウント（ｉ）が１に設定され、"OPEN"
が"OPEN"∪｛ｉ｝に設定され、その後、機能ブロック９
０３でｉが増分される。ここで表記"path（ｉ）"はノー
ドｉに至る全てのパスのセットを意味し、表記"path
（ｉ,ｋ）"はノードｉに至るｋ番目のパスを意味する。
すなわちpath（ｉ,ｋ）はpath（ｉ）に属する要素であ
る。

【００２８】この初期探索の完了により、プロセスは主
ループに入力し、判断ブロック９０６で"OPEN"が空のセ
ットか否かが判断される。肯定の場合、プロセスは終了
する。否定の場合には、機能ブロック９０７で入力度
（ｉ）が参照カウント（ｉ）に等しくなるようにオブジ
ェクトｉが"OPEN"から選択される。用語"入力度（indeg
ree）"は、オブジェクトへの入力接続数を表す。図５を
参照すると、ダミー・ノードは入力度として２を有す
る。ノードｉの入力度は、テーブル内の列ｉにおける"
１"の数に等しい。選択オブジェクトは現オブジェクト
である。次に判断ブロック９０８で、現オブジェクトの
入力度が２以上か否かが判断される。否定の場合、更に
判断ブロック９０９（図２２）で現オブジェクトの出力
度が２以上か否かが判断される。用語"出力度（outdegr
ee）"はオブジェクトからの出力接続の数を表す。図４
を参照すると、ダミー・ノードは出力度として２を有す
る。ノードｉの出力度はテーブル内の行ｉにおける"１"
の数に等しい。現オブジェクトｉの出力度が２よりも小
さいと、プロシージャforward_path（current_obj）が
機能ブロック９１０で呼ばれる。

【００２９】このプロシージャが図２３に図式的に示さ
れ、また図２４のフローチャートによっても示される。
次にこれらの図について説明する。プロシージャforwar
d_path（current_obj）が呼ばれると、機能ブロック１
１０１で変数Ｓが現オブジェクトに至るパス数、すなわ
ちpath（current_obj）セットのサイズに設定される。
機能ブロック１１０２でｉが最初に１に設定され、次に
判断ブロック１１０３でｉがＳ以下か否かが判断され
る。肯定の場合、機能ブロック１１０４で、path（curr
ent_obj,ｉ）がapend（path（current_obj,ｉ）,＜curr
ent_obj＞）に設定される。次に機能ブロック１１０５
でｉの値が増分され、プロセスは判断ブロック１１０３
へループして戻る。判断ブロック１１０３でｉがＳより
も大きいと判断されると、機能ブロック１１０６で、Ta
ble（current_obj,ｊ）＝と１なる各オブジェクトｊに
対して、path（ｊ）がpath（current_obj）とpath
（ｊ）との合併（union）に設定される。この時点で図
２２のブロック９１２に復帰する。図２３に示される例
において、ノードＮからＮ'へのフォワード・パスがプ
ロシージャにより単一ノードＮ'へと低減される。

【００３０】図２２を再度参照して、判断ブロック９０
９で現オブジェクトの出力度が２以上の場合、機能ブロ
ック９１１でプロシージャsplit_path（current_obj）
が呼ばれる。

【００３１】このプロシージャが図２５に図式的に示さ
れ、また図２６のフローチャートによっても示される。
次にこれらの図について説明する。プロシージャsplit_
path（current_obj）が呼ばれると、機能ブロック１３
０１で変数Ｓが現オブジェクトに至るパス数、すなわち
path（current_obj）セットのサイズに設定される。機
能ブロック１３０２でｉが最初に１に設定され、次に判
断ブロック１３０３でｉがＳ以下か否かが判断される。
肯定の場合、機能ブロック１３０４で、path（current_
obj,ｉ）がapend（path（current_obj,ｉ）,＜current_
obj＞）に設定される。次に機能ブロック１３０５でｉ
の値が増分され、プロセスは判断ブロック１３０３へル
ープして戻る。判断ブロック１３０３でｉがＳよりも大
きいと判断されると、機能ブロック１３０６で、Table
（current_obj,ｊ）＝１となる各オブジェクトｊに対し
てpath（ｊ）が、path（current_obj）とpath（ｊ）と
＜current_obj＞との合併（union）に設定される。この
時点で図２２のブロック９１２に復帰する。図２５に示
される例において、ノードｘ₁及びｘ₂へ至るパスがプロ
シージャにより２つのパスに分割される。

【００３２】図２２を再度参照して、機能ブロック９１
０または９１１のいずれかのプロシージャからの復帰が
生じると、機能ブロック９１２でTable（current_obj,
ｉ）＝１となるように、全てのオブジェクトｉが（まだ
それが"OPEN"内に存在しない場合）"OPEN"に挿入され
る。現オブジェクトが"OPEN"から消去され、機能ブロッ
ク９１３で参照カウント（ｉ）が１だけ増分される。そ
の後、判断ブロック９０６（図２１）へ復帰し、再
度、"OPEN"が空か否かが判断される。否定の場合、プロ
セスは機能ブロック９０７及び判断ブロック９０８のオ
ペレーションを繰り返す。現オブジェクトの入力度が２
以上であることが判明すると、機能ブロック９１４でプ
ロシージャgenerate_equations（current_obj）が呼ば
れる。

【００３３】このプロシージャが図２７に図式的に示さ
れ、また図２８及び図２９のフローチャートによっても
示される。次にこれらの図について説明する。プロシー
ジャgenerate_equations（current_obj）が呼ばれる
と、機能ブロック１５０１で変数Ｓが現オブジェクトに
至るパス数、すなわちpath（current_obj）セットのサ
イズに設定される。機能ブロック１５０２でｉが最初に
１に設定され、次に判断ブロック１５０３でｉがＳ−１
以下か否かが判断される。肯定の場合、機能ブロック１
５０４でｊが１に設定され、次に判断ブロック１５０５
でｊの値がＳ以下か否かが判断される。肯定の場合、更
に判断ブロック１５０６で、path（current_obj,ｉ）の
先頭（head）がpath（current_obj,ｊ）の先頭と同一か
否かが判断される。肯定の場合、出力ブロック１５０７
で、path（current_obj,ｉ）がpath（current_obj,ｊ）
と同一の長さを有することが出力される。機能ブロック
１５０８でｉの値が増分され、再度判断ブロック１５０
３でｉがＳ−１以下か否かが判断される。path（curren
t_obj,ｉ）の先頭がpath（current_obj,ｊ）の先頭と同
一でないと、機能ブロック１５０９でｊが１だけ増分さ
れ、再度判断ブロック１５０５でｊがＳ以下か否かが判
断される。ｊがＳよりも大きいとｉが機能ブロック１５
０８で増分され、再度判断ブロック１５０３でｉがＳ−
１以下か否かが判断される。ｉがＳに等しいと主プロシ
ージャへ復帰する。図２７に示される図式表現は出力ブ
ロック１５０７の出力を示しており、ノードｘ₀からノ
ードｘ₁を介してノードｘ_nへ至るパスが、ノードｘ₂を
介するパスに等しいことを示す。更に、ノードｘ₀から
ノードｘ₂を介してノードｘ_nへ至るパスが、ノードｘ₃
及びｘ₄を介するパスに等しいことを示す。

【００３４】まとめとして、本発明の構成に関して以下
の事項を開示する。

【００３５】（１）コンピュータにより、複数のエピソ
ードを含むマルチメディア・ストーリを大域時間制限内
に提供する方法であって、上記ストーリ内の上記の各エ
ピソードに対応して、最小、最適及び最大時間の３つ組
を上記コンピュータに入力するステップと、上記ストー
リ内の上記エピソードの時間制限を上記コンピュータに
入力するステップと、上記時間制限から上記ストーリ内
において同等の再生時間を有するパスのセットを決定す
るステップであって、上記パスが共通の開始ノードと終
了ノード間のノードにより定義される、上記決定ステッ
プと、上記の各エピソードの上記３つ組時間、及び上記
ストーリ内において上記同等の再生時間を有する上記パ
スのセットにもとづき、大域長制限に関係無しに上記の
各エピソードの最小コストかつ公正なスケジュール及び
時間を探索するステップと、上記ストーリ内の上記各エ
ピソードの上記最小コストかつ公正なスケジュール及び
上記時間にもとづき、大域長を生成するステップと、を
含む、方法。 （２）ユーザに上記生成大域長を受諾または拒絶するか
の任意選択を提供するステップと、上記ユーザが上記生
成大域長を拒絶する場合、上記ユーザに上記大域長制限
を入力するように促すステップと、上記入力大域長制限
を時間制限テーブルに追加するステップと、上記時間制
限から上記ストーリ内において同等の再生時間を有する
パスのセットを決定するステップであって、上記パスが
共通の開始ノード及び終了ノードの間のノードにより定
義される、上記決定ステップと、上記の各エピソードの
上記３つ組時間、及び上記ストーリ内において上記同等
再生時間を有する上記パスのセットにもとづき、上記大
域長制限内において、上記の各エピソードの上記最小コ
ストかつ公正なスケジュール及び上記時間を探索するス
テップと、を含む、上記（１）記載の方法。 （３）上記ユーザが上記生成大域長を受諾する場合、上
記ストーリの上記エピソードのスケジュールを出力する
ステップを含む、上記（２）記載の方法。 （４）上記大域長制限内で上記最小コストかつ公正なス
ケジュールを見い出した後に、上記ストーリの上記エピ
ソードのスケジュールを出力するステップを含む、上記
（２）記載の方法。 （５）上記時間制限テーブルを構築するステップを含
み、上記同等の再生時間を有する上記パスのセットの上
記決定ステップが上記時間制限テーブルの探索により実
行される、上記（２）記載の方法。 （６）複数のエピソードを含むマルチメディア・ストー
リを大域時間制限内に提供する装置であって、上記スト
ーリ内の上記の各エピソードに対応して、最小、最適及
び最大時間の３つ組を入力する手段と、上記ストーリ内
の上記エピソードの時間制限を入力する手段と、上記時
間制限から、上記ストーリ内において同等の再生時間を
有するパスのセットを決定する中央プロセッサ手段であ
って、上記パスが共通の開始ノードと終了ノード間のノ
ードにより定義され、上記中央プロセッサ手段が、上記
の各エピソードの上記３つ組時間、及び上記ストーリ内
において上記同等の再生時間を有する上記パスのセット
にもとづき、大域長制限に関係無しに上記各エピソード
の最小コストかつ公正なスケジュール及び時間を探索
し、上記ストーリ内の上記各エピソードの上記最小コス
トかつ公正なスケジュール及び上記時間にもとづき、大
域長を生成する、上記中央プロセッサ手段と、ユーザが
上記生成大域長を受諾する場合、上記ストーリの上記エ
ピソードのスケジュールを出力する出力手段と、を含
む、装置。 （７）上記中央プロセッサ手段が、ユーザに上記生成大
域長を受諾または拒絶するかの任意選択を提供する手段
と、上記ユーザが上記生成大域長を拒絶する場合、上記
ユーザに大域長制限を入力するように促す手段と、上記
入力大域長制限を時間制限テーブルに追加する手段と、
上記時間制限から、上記ストーリ内において同等の再生
時間を有するパスのセットを決定する手段であって、上
記パスが共通の開始ノード及び終了ノードの間のノード
により定義される、上記決定手段と、上記の各エピソー
ドの上記３つ組時間、及び上記ストーリ内において上記
同等再生時間を有する上記パスのセットにもとづき、上
記大域長制限内において、上記の各エピソードの上記最
小コストかつ公正なスケジュール及び上記時間を探索す
る手段と、を含む、上記（６）記載の装置。

【００３６】

【発明の効果】以上説明したように本発明によれば、マ
ルチメディア・エピソードを構成及び再生するための改
良された方法及び装置を提供することができる。

【００３７】更に本発明によれば、マルチメディア・ス
トーリを可変大域再生時間により再生する改良された方
法及び装置を提供することができる。

【００３８】更に本発明によれば、マルチメディア・ス
トーリの大域再生時間の可変性を識別し、ユーザに大域
再生時間を選択する機能を提供する改良された方法及び
装置を提供することができる。

【００３９】更に本発明によれば、ストーリの大域再生
時間を複数の大域再生時間から選択し、エピソード再生
時間をストーリ内で公正にスケジュールする改良された
方法及び装置を提供することができる。

【図面の簡単な説明】

【図１】本発明が実現されうるハードウェア構成を示す
ブロック図である。

【図２】マルチメディア・ストーリのエピソードに対応
する最小、最適及び最大再生時間を入力するためのコン
ピュータ画面を示す図である。

【図３】時間制限の１タイプを示すブロック図である。

【図４】別のタイプの時間制限を示すブロック図であ
る。

【図５】更に別のタイプの時間制限を示すブロック図で
ある。

【図６】更に別のタイプの時間制限を示すブロック図で
ある。

【図７】ストーリ内のエピソードの図形表現及びそれら
の時間制限を示すブロック図である。

【図８】エピソードを時間制限に関連付けることによ
り、ストーリを創作するコンピュータ画面を示す図であ
る。

【図９】本発明による基本プロセスの論理のフローチャ
ートを示す図である。

【図１０】本発明による基本プロセスの論理のフローチ
ャートを示す図である。

【図１１】本発明による基本プロセスの論理のフローチ
ャートを示す図である。

【図１２】同等の再生時間を有するパスのセットの制限
を決定するために使用される時間制限テーブル例を示す
図である。

【図１３】図１２の時間制限テーブルを構築するプロセ
スの論理のフローチャートを示す図である。

【図１４】図１２の時間制限テーブルを構築するプロセ
スの論理のフローチャートを示す図である。

【図１５】図１２の時間制限テーブルを構築するプロセ
スの論理のフローチャートを示す図である。

【図１６】ルート・ノード及びテール・ノードを追加す
るプロセスを表すために使用される時間制限グラフを示
す図である。

【図１７】ルート・ノード及びテール・ノードを追加す
るプロセスを表すために使用される時間制限グラフを示
す図である。

【図１８】図１６の時間制限グラフに対応する時間制限
テーブルを示す図である。

【図１９】図１７の時間制限グラフに対応する時間制限
テーブルを示す図である。

【図２０】時間制限テーブルから同等の再生時間を有す
るパスのセットを決定するプロセスの論理のフローチャ
ートを示す図である。

【図２１】時間制限テーブルから同等の再生時間を有す
るパスのセットを決定するプロセスの論理のフローチャ
ートを示す図である。

【図２２】時間制限テーブルから同等の再生時間を有す
るパスのセットを決定するプロセスの論理のフローチャ
ートを示す図である。

【図２３】図２２のプロセスから呼ばれるプロセスforw
ard_path（current_obj）の図形表現を示す図である。

【図２４】プロシージャforward_path（current_obj）
のプロセスの論理のフローチャートを示す図である。

【図２５】図２２のプロセスから呼ばれるプロセスspli
t_path（current_obj）の図形表現を示す図である。

【図２６】プロシージャsplit_path（current_obj）の
プロセスの論理のフローチャートを示す図である。

【図２７】図２１のプロセスから呼ばれるプロセスgene
rate_equations（current_obj）の図形表現を示す図で
ある。

【図２８】プロシージャgenerate_equations（current_
obj）のプロセスの論理のフローチャートを示す図であ
る。

【図２９】プロシージャgenerate_equations（current_
obj）のプロセスの論理のフローチャートを示す図であ
る。

【符号の説明】

１０ ＣＰＵ １２ システム・バス １４ ＲＡＭ １６ ＲＯＭ １８ Ｉ／Ｏアダプタ １９ フロッピー・ドライブ ２０ ハードディスク・ドライブ ２１ ＣＤ−ＲＯＭ ２２ ユーザ・インタフェース ２４ キーボード ２６ マウス ２８ スピーカ ３０ ビデオ・カメラ ３２ マイク ３４ マルチメディア・アダプタ ３６ 表示アダプタ ３８ 表示装置 ２０１、５１２ アイコン ２０２、２０３、２０４ ボタン ２０８ "設定"ボタン ２０９ "完了"ボタン ２１０ "取り消し"ボタン ２０５ スライダ ２０６ タイムライン ２０７、５０３ ウィンドウ ２１１、２１２、２１３、２１４、４０１、４０２、４
０３、４０６、４０７、４０８、４１０ 矢印ボタン ４０４、４０５ エピソード ５０１ カンバス域 ５０８ 分離ボタン ５０９ 除去ボタン ５１０ 変更ボタン ５１１ 図形表示

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ユンワ・ソン アメリカ合衆国10583、ニューヨーク州ス カースデイル、フェズント・ラン 23

Claims (7)

【特許請求の範囲】
1. 【請求項１】コンピュータにより、複数のエピソードを
   含むマルチメディア・ストーリを大域時間制限内に提供
   する方法であって、 上記ストーリ内の上記の各エピソードに対応して、最
   小、最適及び最大時間の３つ組を上記コンピュータに入
   力するステップと、 上記ストーリ内の上記エピソードの時間制限を上記コン
   ピュータに入力するステップと、 上記時間制限から上記ストーリ内において同等の再生時
   間を有するパスのセットを決定するステップであって、
   上記パスが共通の開始ノードと終了ノード間のノードに
   より定義される、上記決定ステップと、 上記の各エピソードの上記３つ組時間、及び上記ストー
   リ内において上記同等の再生時間を有する上記パスのセ
   ットにもとづき、大域長制限に関係無しに上記の各エピ
   ソードの最小コストかつ公正なスケジュール及び時間を
   探索するステップと、 上記ストーリ内の上記各エピソードの上記最小コストか
   つ公正なスケジュール及び上記時間にもとづき、大域長
   を生成するステップと、 を含む、方法。
2. 【請求項２】ユーザに上記生成大域長を受諾または拒絶
   するかの任意選択を提供するステップと、 上記ユーザが上記生成大域長を拒絶する場合、上記ユー
   ザに上記大域長制限を入力するように促すステップと、 上記入力大域長制限を時間制限テーブルに追加するステ
   ップと、 上記時間制限から上記ストーリ内において同等の再生時
   間を有するパスのセットを決定するステップであって、
   上記パスが共通の開始ノード及び終了ノードの間のノー
   ドにより定義される、上記決定ステップと、 上記の各エピソードの上記３つ組時間、及び上記ストー
   リ内において上記同等再生時間を有する上記パスのセッ
   トにもとづき、上記大域長制限内において、上記の各エ
   ピソードの上記最小コストかつ公正なスケジュール及び
   上記時間を探索するステップと、 を含む、請求項１記載の方法。
3. 【請求項３】上記ユーザが上記生成大域長を受諾する場
   合、上記ストーリの上記エピソードのスケジュールを出
   力するステップを含む、請求項２記載の方法。
4. 【請求項４】上記大域長制限内で上記最小コストかつ公
   正なスケジュールを見い出した後に、上記ストーリの上
   記エピソードのスケジュールを出力するステップを含
   む、請求項２記載の方法。
5. 【請求項５】上記時間制限テーブルを構築するステップ
   を含み、上記同等の再生時間を有する上記パスのセット
   の上記決定ステップが上記時間制限テーブルの探索によ
   り実行される、請求項２記載の方法。
6. 【請求項６】複数のエピソードを含むマルチメディア・
   ストーリを大域時間制限内に提供する装置であって、 上記ストーリ内の上記の各エピソードに対応して、最
   小、最適及び最大時間の３つ組を入力する手段と、 上記ストーリ内の上記エピソードの時間制限を入力する
   手段と、 上記時間制限から、上記ストーリ内において同等の再生
   時間を有するパスのセットを決定する中央プロセッサ手
   段であって、上記パスが共通の開始ノードと終了ノード
   間のノードにより定義され、上記中央プロセッサ手段
   が、上記の各エピソードの上記３つ組時間、及び上記ス
   トーリ内において上記同等の再生時間を有する上記パス
   のセットにもとづき、大域長制限に関係無しに上記各エ
   ピソードの最小コストかつ公正なスケジュール及び時間
   を探索し、上記ストーリ内の上記各エピソードの上記最
   小コストかつ公正なスケジュール及び上記時間にもとづ
   き、大域長を生成する、上記中央プロセッサ手段と、 ユーザが上記生成大域長を受諾する場合、上記ストーリ
   の上記エピソードのスケジュールを出力する出力手段
   と、 を含む、装置。
7. 【請求項７】上記中央プロセッサ手段が、 ユーザに上記生成大域長を受諾または拒絶するかの任意
   選択を提供する手段と、 上記ユーザが上記生成大域長を拒絶する場合、上記ユー
   ザに大域長制限を入力するように促す手段と、 上記入力大域長制限を時間制限テーブルに追加する手段
   と、 上記時間制限から、上記ストーリ内において同等の再生
   時間を有するパスのセットを決定する手段であって、上
   記パスが共通の開始ノード及び終了ノードの間のノード
   により定義される、上記決定手段と、 上記の各エピソードの上記３つ組時間、及び上記ストー
   リ内において上記同等再生時間を有する上記パスのセッ
   トにもとづき、上記大域長制限内において、上記の各エ
   ピソードの上記最小コストかつ公正なスケジュール及び
   上記時間を探索する手段と、 を含む、請求項６記載の装置。