メディアオブジェクトの時空間レイアウト
確定された時空間レイアウト仕様（２０）は、相対的時空間レイアウト仕様（１４）にしたがって自動的に生成される。相対的時空間レイアウト仕様（１４）は、メディアオブジェクトタイプの相対的な空間的位置及び時間的順序を記述する。確定された時空間レイアウト仕様(20)は、ある時間にわたる表示領域（４６）内のメディアオブジェクト（１８）のレイアウトを記述する。確定された時空間レイアウト仕様（２０）を生成するプロセスは、メディアオブジェクト（１８）の各々について、それぞれのレンダリング期間にわたる表示領域（４６）内のそれぞれのウィンドウに対応するそれぞれの時空間スロットを決定することを含み、この場合、該レンダリング期間において、メディアオブジェクト（１８）はレンダリングされるようにスケジューリングされている。確定された時空間レイアウト仕様（２０）は出力される。
【発明の詳細な説明】
【背景技術】
【０００１】
個人や組織は、静止画、テキスト、グラフィックス、アニメ画像（動画グラフィックス）、フルモーションビデオ画像などのデジタルコンテンツの大量のコレクション（収集物）を速やかに蓄積している。このコンテンツを、文書、カタログ、プレゼンテーション、スチール写真、コマーシャルビデオ、ホームムービー、及び、１つ以上の関連するデジタルコンテンツファイルを記述しているメタデータなどの様々な異なる形態で個別に、または、それらの形態を組み合わせて提示することができる。これらのコレクションは、その数が多くなると共にますます多様化してきているので、個人や組織は、彼らのコレクション中のデジタルコンテンツを編成して提示するためのシステム及び方法を次第に要求するようになるだろう。この要求を満たすためには、デジタルイメージ（画像）コンテンツを編成して提示するための様々な異なるシステム及び方法が必要である。
【発明の概要】
【０００２】
本発明は、１側面において、相対的な時空間レイアウト仕様にしたがって、確定された時空間レイアウト仕様（または、明確に限定された時空間レイアウト仕様。以下同じ）を自動的に生成する方法を特徴とする。この相対的な時空間レイアウト仕様は、メディアオブジェクトタイプの相対的な空間的位置及び時間的順序を記述する。この確定された時空間レイアウト仕様は、ある時間にわたる表示領域内のメディアオブジェクトのレイアウトを記述する。確定された時空間レイアウト仕様を生成するプロセスには、メディアオブジェクトのそれぞれについて、それぞれのレンダリング期間にわたって、表示領域内のそれぞれのウィンドウに対応するそれぞれの時空間スロットを決定することが含まれ、該レンダリング期間において、メディアオブジェクトがレンダリングされるようにスケジューリング（計画）されている。この確定された時空間レイアウト仕様は出力される。
【０００３】
本発明は、また、コンピュータに上述の方法を実施させるコンピュータ読み取り可能命令を格納する装置及びコンピュータ読み取り可能媒体を特徴とする。
【０００４】
本発明の他の特徴及び利点は、以下の説明、並びに、図面及び特許請求の範囲から明らかになるであろう。
【図面の簡単な説明】
【０００５】
【図１】相対的な時空間レイアウト仕様にしたがって１組のメディアオブジェクトを処理して、確定された時空間レイアウト仕様を生成する時空間レイアウト生成器を備える時空間レイアウト生成システムの１実施形態のブロック図である。
【図２】時空間レイアウト生成方法の１実施形態の流れ図である。
【図３】相対的な時空間レイアウト仕様の１実施形態の線図である。
【図４】図３の相対的時空間レイアウト仕様にしたがって生成されたメディアオブジェクトの確定された時空間レイアウトの１実施形態の略図である。
【図５Ａ】メディアオブジェクトの確定された時空間レイアウトの１実施形態から抽出された１組の画像フレームの略図である。
【図５Ｂ】図５Ａに示すイメージフレーム（画像フレーム）の要素と、対応する相対的な時空間レイアウト仕様の要素との間の対応関係を示す。
【図６】相対的な時空間レイアウト仕様の１実施形態の２つの表現の略図である。
【図７】相対的な時空間レイアウト仕様の１実施形態の２つの表現の略図である。
【図８】相対的な時空間レイアウト仕様の１実施形態の２つの表現の略図である。
【図９Ａ】相対的な時空間レイアウト仕様の１実施形態の２つの表現の略図である。
【図９Ｂ】図９Ａに示された相対的な時空間レイアウト仕様にしたがって生成されたメディアオブジェクトの確定された時空間レイアウトの１実施形態の線図である。
【図１０】図１に示す時空間レイアウト生成システムの１実施形態のブロック図である。
【図１１】図２の時空間レイアウト生成方法の１実施形態で使用される多次元最適化処理の１実施形態のブロック図である。
【図１２】図２の時空間レイアウト生成方法の１実施形態において、図１１の多次元最適化処理と共に使用される適応型スケジューリング処理の１実施形態のブロック図である。
【図１３】図１の時空間レイアウト生成システムの１実施形態を実施するようにプログラムされたコンピュータシステムの１実施形態のブロック図である。
【発明を実施するための形態】
【０００６】
以下の説明では、同様の要素には同じ参照番号が付されている。さらに、図面は、例示的な実施形態の主要な特徴を概略的に例示することが意図されている。図面は、実際の実施形態の全ての特徴を示すことも、図示した要素の相対的な寸法を示すことも意図されておらず、一律の縮尺に従わずに描かれている。
【０００７】
Ｉ．導入
後で詳細に説明する実施形態は、メディアオブジェクトのコレクションを時空間レイアウトに編成することができ、該レイアウトにおいて、メディアオブジェクトの各々は、空間的かつ時間的に分割されたスケジューリングされたレンダリング（またはプレゼンテーション（提示など））空間内のそれぞれのスロットに割り当てられる。
【０００８】
時空間レイアウトは、典型的には、プレゼンテーション空間の時空間スロットへの空間的及び時間的分割を誘導し、メディアオブジェクトの該スロットへの割り当てを誘導する相対的な時空間レイアウト仕様（以下、相対的時空間レイアウト仕様という）にしたがって生成される。相対的時空間レイアウト仕様は、メディアオブジェクトタイプの相対的空間レイアウト、及び、該メディアオブジェクトタイプを特定のレンダリングシーケンスで配列するためのスケジュールの一般的な仕様である。相対的時空間レイアウト仕様は、任意のメディアオブジェクトまたはメディアオブジェクトメタデータ（たとえば、持続時間、アスペクト比、解像度など）に関係なく相対的時空間レイアウトを規定（または指定）する。いくつかの実施形態では、相対的時空間レイアウト仕様は、マルチメディア関連の熟練した技能者によって任意の特定のメディアオブジェクトとは無関係に生成される。こうして、相対的時空間レイアウト仕様は、不慣れなユーザーが、該ユーザーのメディアオブジェクトのコレクションの高品質のプレゼンテーションを生成するために利用可能なやり方で、マルチメディアを専門とする熟練技能者の技能及び美的センスを具現化することができる。
【０００９】
本明細書で説明される実施形態は、コンシューマー（消費者）向けの応用領域において大きな利点を提供し、それらの実施形態は、本質的にむらがあって（すなわち、統一性がない）、様々な異なるフォーマット及び解像度のコンテンツを有するメディアオブジェクトに対して、複雑なイベントを適切な形態で記録（または文書化）できるようにする。
【００１０】
II．用語の定義
「メディアオブジェクト」という用語は、テキスト、音声（オーディオ）、グラフィックス、アニメ画像（または動画グラフィックス）、静止画像、フルモーションビデオ、及び、物体の電子的表現物を含む、任意の形態のデジタルコンテンツを広く指す。このコンテンツを、ひとまとめにして、文書、注釈、プレゼンテーション、音楽、スチール写真、コマーシャルビデオ、ホームムービー、及び、１つ以上の関連するデジタルコンテンツファイルを記述するメタデータを含む様々な異なる形態で個別に、または、いくつかを組み合わせて提示することができる。イメージベースのメディアオブジェクト（あるいは単に「画像」）を、任意のタイプのデジタル画像すなわち電子画像の完全なバージョンまたは部分的なバージョンとすることができ、それらの画像には、イメージセンサ（たとえば、ビデオカメラ、（電子）スチールカメラ、または、光学スキャナー）によって撮像された画像、または、そのような画像の処理されたバージョン（たとえば、フィルタリングされたバージョン、再フォーマットされたバージョン、強調または他の変更を施されたバージョン）、コンピュータによって生成されたビットマップもしくはベクターグラフィック画像、テキスト画像（たとえば、テキスト（文字）を含むビットマップ画像）、図像的画像（iconographic image）が含まれる。「メディアオブジェクト」という用語は、１つ以上のメディアオブジェクトの凝集したグループまたはコレクションから形成された単一要素メディアオブジェクトと複数要素メディアオブジェクトの両方を包含する。特定の多要素メディアオブジェクトへの単一要素メディアオブジェクトの割り当ては、構成要素である単一要素メディアオブジェクト同士が関連するということを意味している。一般に、複数要素メディアオブジェクト中の単一要素メディアオブジェクトのタイプは同じ場合も異なる場合もある。メディアオブジェクトは典型的には、１つ以上のコンピュータ読み取り可能媒体上の１つ以上のデータベースに格納される。メディアオブジェクトは、ローカルなデータベース、または、ローカルエリアネットワーク及びグローバル通信ネットワークを介してアクセス可能な１つ以上のリモートのデータベースに物理的に格納することができる。いくつかのメディアオブジェクトは、ピアツーピア・ネットワーク接続を介してアクセス可能なリモートのデータベースに格納することもできる。
【００１１】
本明細書で使用される「相対的時空間レイアウト」という用語は、メディアオブジェクトタイプの相対的な空間的配列及び相対的な時間的順序を指し、この場合、メディアオブジェクトタイプの絶対位置、及び、メディアオブジェクトの絶対レンダリング時間は指定されない。相対的時空間レイアウト仕様は、ある時間にわたるメディアオブジェクトタイプの相対的な空間位置を記述する。
【００１２】
本明細書で使用される「確定された時空間レイアウト」という用語は、メディアオブジェクトの位置、寸法（または次元）、及び、スケジューリングされたレンダリング期間（または周期）を記述する確定された時空間レイアウト仕様にしたがって、特定の順番で表示領域に並べられたメディアオブジェクトのレイアウトを指す。
【００１３】
「データ構造」という用語は、データが編成されて格納される物理的なレイアウト（またはフォーマット）を広く指す。
【００１４】
「コンピュータ」は、コンピュータ読み取り可能媒体に一時的にまたは永久的に格納されるコンピュータ読み取り可能命令（たとえばソフトウェア）にしたがってデータを処理する機械である。特定のタスクを実行する１組のそのような命令は、プログラムまたはソフトウェアプログラムと呼ばれる。
【００１５】
「コンピュータ読み取り可能媒体」という用語は、コンピュータが読み出すことが可能な情報を格納できる任意の媒体を指す。コンピュータ読み取り可能媒体の例には、不揮発性形態を含むあらゆる形態のコンピュータ読み取り可能メモリ（但し、これらには限定されない）を含む、命令及びデータを明白に具現化するのに適した記憶装置であり、該不揮発性形態には、EPROM、EEPROM、及びフラッシュメモリデバイス（装置）などの半導体記憶装置や、内部ハードディスク及びリムーバルハードディスクなどの磁気ディスク、光磁気ディスク、DVD-ROM／RAM、及びCD-ROM/RAMなどがある。
【００１６】
III. 概要
図１は、相対的時空間レイアウト仕様１４にしたがってメディアオブジェクト１８の組１６を処理して、確定された時空間レイアウト仕様２０を生成する時空間レイアウト生成器１２を備える時空間レイアウト生成システム１０の１実施形態を示す。この相対的時空間レイアウト仕様は、メディアオブジェクトタイプの相対的な空間位置及び相対的な時間的順序を記述し、一方、この確定された時空間レイアウト仕様２０は、ある時間にわたる表示領域内のメディアオブジェクト１８のレイアウトを記述する。
【００１７】
図２は、時空間レイアウト生成器１２によって実施される方法の１実施形態を示す。図２の方法によれば、時空間レイアウト生成器１２は、相対的時空間レイアウト仕様１４にしたがって、確定された時空間レイアウト仕様２０を自動的に生成する（図２のブロック２２）。このプロセスでは、時空間レイアウト生成器１２は、メディアオブジェクト１８の各々について、それぞれのレンダリング期間にわたる表示領域内のそれぞれのウィンドウに対応するそれぞれの時空間スロットを決定する。このレンダリング期間において、メディアオブジェクトは、レンダリングされるようにスケジューリングされる。
【００１８】
時空間レイアウト生成器１２は、確定された時空間レイアウト仕様２０を出力する（図２のブロック２４）。いくつかの実施形態では、時空間レイアウト生成器１２は、確定された時空間レイアウト仕様２０をコンピュータ読み取り可能媒体に格納することによって該仕様２０を出力する。これらの実施形態では、時空間レイアウト生成器１２は、典型的には、空間的かつ時間的に分割されたスケジューリングされたレンダリング（またはプレゼンテーション）空間におけるスロットへのメディアオブジェクト１８の割り当てを記述するデータ構造（たとえば、テーブルまたはリスト）を含む仕様の形態で、確定された時空間レイアウト仕様２０を出力する。いくつかの実施形態では、この仕様は、XML（拡張マークアップ言語）ファイルフォーマットでコンピュータ読み取り可能媒体に格納される。
【００１９】
いくつかの実施形態では、時空間レイアウト生成システム１０は、確定された時空間レイアウト仕様２０にしたがってメディアオブジェクト１８の確定された時空間レイアウトをレンダリングする（レンダリングとは、描画、及び／または、視覚的に表示することを意味する）。たとえば、いくつかの実施形態では、時空間レイアウト生成システム１０は、ディスプレイにメディアオブジェクト１８の確定された時空間レイアウトをレンダリングする。このディスプレイを、たとえば、LCD（液晶ディスプレイ）、プラズマディスプレイ、ELディスプレイ（エレクトロルミネセント・ディスプレイ）、及びFED（電界放出ディスプレイ）などのフラットパネルディスプレイとすることができる。他の実施形態では、時空間レイアウト生成システム１０は、印刷媒体（たとえば、１枚以上の紙）にメディアオブジェクト１８の確定された時空間レイアウトをレンダリングする。
【００２０】
いくつかの実施形態では、確定された時空間レイアウト仕様２０は、ビデオプレーヤーがメディアオブジェクト１８の対応する時空間レイアウトを表示するためにレンダリングすることが可能な出力ビデオファイルに対応（または一致）する。これらの実施形態では、出力ビデオファイルは、ビデオファイルフォーマット（たとえば、AVI、MOV、MPEG-2、MPEG-4、Ogg、ASF、RealMedia、及び3gp）にしたがってコンピュータ読み取り可能媒体に格納される。いくつかの実施形態では、確定された時空間レイアウト仕様２０は、機械（たとえばコンピュータ）に、メディアオブジェクト１８の時空間レイアウトに対応する合成（または複合）ビデオを提示（または表示）させる構文解析可能なビデオ再生命令に対応（または一致）する。これらの実施形態では、これらの命令は、メディアオブジェクト１８の時空間レイアウトをレンダリングするためにスクリプトインタプリタ（たとえば、Adobe Flash（商標）プレーヤー）が実行または構文解析可能なマルチメディアオーサリングスクリプト言語（たとえば、Adobe Flash（商標））にしたがってコンピュータ読み取り可能媒体に格納される。いくつかの実施形態では、確定された時空間レイアウト仕様２０は、メディアオブジェクト１８の時空間レイアウトを表示領域に表示するやり方を記述するビデオ合成仕様（たとえば、スクリプト）に対応（または一致）する。これらの実施形態では、ビデオ合成仕様は、メディアオブジェクト１８の時空間レイアウトをレンダリングするために処理されることが可能な出力ビデオファイル（たとえば、AVIファイル）、または、１組の構文解析可能なビデオ再生命令（たとえば、Adobe Flash（商標）スクリプトやAviSynthスクリプト）を生成するビデオオーサリングツール（たとえば、Adobe Flash（商標）やAviSynth）によって処理される。
【００２１】
IV．相対的時空間レイアウトの指定
A．導入
上述したように、相対的時空間レイアウト仕様１４は、特定の時間的順序でメディアオブジェクトタイプの空間的レイアウトを記述し、この場合、メディアオブジェクトタイプの絶対位置、及び、メディアオブジェクトタイプの絶対レンダリング時間（期間）は指定されない。メディアオブジェクトタイプの相対的な空間位置を、たとえば、メディアオブジェクトタイプの相対的な空間位置を、互いに関連して、または、共通の基準点（たとえば、共通の座標系の端点すなわちエッジポイント）に関連して記述する任意のタイプのフロアプランモデル（floor plan model）にしたがって記述することができる。相対的時空間レイアウト仕様１４は、相対的なレンダリング空間（描画空間）のスロットへの分解を記述し、この場合、該スロットの各々は、メディアオブジェクトタイプのちょうど１つを含む。
【００２２】
図３は、相対的レンダリング空間の再帰的分割（または再帰的細分）モデルに対応（または一致）する相対的時空間レイアウト仕様１４の１実施形態を示す。この実施形態では、この分割モデルは、木構造２６に編成される２値時空間分割モデルである。木構造２６は、それぞれのメディアオブジェクトタイプに対応するリーフ（葉）ノード２８、３０、３２、３４、及び、該木構造２６によって分割されている相対的レンダリング空間の各区分に対応する内部ノード３６、３８、４０を有する。例示的な実施形態では、垂直のバー「｜」は、相対的レンダリング空間の垂直方向の空間分割（または分離）を示し、エムダッシュ「―」は、相対的レンダリング空間の水平方向の分割を示している。はるかに大きいという記号「＞＞」は、相対的レンダリング空間の時間的分割を示しており、相対的なレンダリングの順番は、左側の子ノードが右側の子ノードよりも先である。したがって、木構造２６によって指定される相対的レンダリング空間の再帰的分割は、２つの連続する写真メディアオブジェクトタイプの実例（インスタンス）の左側の時空間スロットに割り当てられている該ビデオメディアオブジェクトタイプの第１の実例（インスタンス）と、該ビデオメディアオブジェクトタイプの第２の実例（インスタンス）に対応し、この場合、写真メディアオブジェクトタイプの連続する実例は、右上の時空間スロットが該ビデオメディアオブジェクトタイプの第２の実例を含む右下の時空間スロットの上になるようにレンダリングされる。
【００２３】
図４は、２つのビデオ（すなわち、ビデオ_1とビデオ_2）及び２つの写真（すなわち、写真_1と写真_2）の確定された時空間レイアウトの例示的な実施例を示し、これらのビデオ及び写真は、２値木構造２６によって表される時空間分割仕様にしたがって、スケジューリングされたレンダリング空間４２中のそれぞれのスロットに割り当てられている。
【００２４】
木構造２６によって表される時空間分割仕様を、相対的レンダリング空間の再帰的時空間分割を規定する類似のテキストスキーマ（textual schema）を用いて指定することもできる。このスキーマによると、
・垂直バー「｜」は、相対的レンダリング空間の垂直方向の空間分割を示し、ここで、垂直バーの左側で識別される要素（すなわち、１つ以上のメディアオブジェクトタイプの１つ以上の実例）は、垂直バーの右側で識別される要素の左に配置される。
・ダッシュ「―」は、相対的レンダリング空間の水平方向の分割を示し、ここで、水平バーの左側で識別される要素（すなわち、１つ以上のメディアオブジェクトタイプの１つ以上の実例）は、水平バーの右側で識別される要素の上に配置される。
・はるかに大きいという記号「＞＞」は、相対的レンダリング空間の時間的分割を示し、該空間において、該記号の左側の要素は該記号の右側の要素に先行する。
【００２５】
いくつかの実施形態では、このスキーマは、さらに、相対的時空間レイアウト仕様の設計者が、スロットのうちの指定されたスロットに対して１つ以上のメディアオブジェクト選択基準を指定できるようにするタグまたは他のメタデータを含む。かかるメディアオブジェクト選択基準に応じて、時空間レイアウト生成器１２は、割り当てられるメディアオブジェクトがメディアオブジェクト選択基準を満たすというユーザーの指示に基づいて、組１６内のメディアオブジェクト１８の１つを指定されたスロットに割り当てる。該スキーマに含めることができるメディアオブジェクト選択基準タグの種々のタイプの中には以下のものがある。
・メディアタイプ指定（すなわち、「_MediaType_」）の反対側の下線は、確定された時空間レイアウトにおける対応する時空間スロットに割り当てられたメディアオブジェクトが、ユーザーが該確定された時空間レイアウト仕様２０によって伝えられることを望むテーマ(主題)を表すものとして該ユーザーによって識別された特定のメディアタイプ（MediaType）のメディアオブジェクトであるべきことを示している。
・メディアタイプ指定（すなわち、「MediaType！」）の直後の感嘆符（「！」）は、確定された時空間レイアウトにおける対応する時空間スロットに割り当てられたメディアオブジェクトが、ユーザーによって、確定された時空間レイアウト仕様２０の気候イベントを表すものとして識別された特定のメディアタイプ（MediaType）のメディアオブジェクトであるべきことを示している。
【００２６】
したがって、上記のスキーマによれば、図３に示す木構造２６によって表される時空間相対的分割仕様は、単一の表現からなるコンピュータ言語における以下のテキスト記述によって等価的に指定される。
ビデオ｜（（写真）＞＞写真）―ビデオ）
【００２７】
図５Ａは、連続する時間ｔ１、ｔ２、ｔ３、ｔ４、ｔ５、ｔ６におけるメディアオブジェクトの確定された時空間レイアウトの１実施形態から抽出された１組の画像フレームを示す。この実施形態は、以下の相対的分割仕様にしたがって、ユーザーによって選択された１０個の写真メディアオブジェクトと２つのビデオメディアオブジェクトの組から生成された。
【数１】
【００２８】
図５Ｂは、図５Ａに示す画像フレームの要素と、対応する相対的分割仕様の要素との間の対応関係を示す。この例では、表示領域４６の左上隅のウィンドウ内にレンダリングされた写真４４は、確定された時空間レイアウトの主題に関する写真としてユーザーによって選択され、表示領域４６の右上隅にあるビデオ４８は、確定された時空間レイアウトの気候ビデオとしてユーザーによって選択された。
【００２９】
Ｂ．相対的時空間レイアウト仕様の例示的な実施形態
前のセクションで説明した相対的時空間分割法によって、様々な異なる相対的時空間レイアウトを指定することができる。以下の相対的時空間レイアウトは、本明細書において例示のためだけに記載されたものであり、これらの分割法を用いて記述可能な可能性のある相対的レイアウトの数及び種類を制限するものではない。
【００３０】
図６は、同じ相対的時空間レイアウトのテキスト仕様５０及びグラフィック仕様（図的仕様）５２の実施形態を示す。これらの実施形態では、ビデオメディアオブジェクトタイプの２つの実例（インスタンス）が、隣り合っている写真メディアオブジェクトタイプの２つの実例の上のスロットにある写真メディアオブジェクトタイプの主題的インスタンス（主題に関する実例）の左側にあるそれぞれのスロットにおいて隣接して上下に配置されている。
【００３１】
図７は、同じ相対的時空間レイアウトのテキスト仕様５４及びグラフィック仕様５６の実施形態を示す。これらの実施形態は、１組の時空間スロットへのメディアオブジェクトタイプの第１の割り当てを指定し、この場合、１組の時空間スロットへのメディアオブジェクトタイプの第２の割り当てが、該第１の割り当てに時間的に後続する。これらの割り当ての各々は、ビデオメディアオブジェクトタイプのそれぞれの実例を含む３つの垂直方向に分散したスロットの左側にあるスロット内に配置されたビデオメディアオブジェクトタイプのそれぞれの実例から構成される。
【００３２】
図８は、同じ相対的時空間レイアウトのテキスト仕様５８及びグラフィック仕様６０の実施形態を示す。このテキスト記述は、コンピュータ言語が単一の表現の前に一連のステートメント（または文）を有することができることを示している。これらのステートメントは、変数の値を部分的な表現（該部分的な表現を、その後、最終的な表現に結合することができる）に設定することができる。これらの実施形態は、メディアオブジェクトタイプの第２の配列の左側に配置されるメディアオブジェクトタイプの第１の配列を指定する。この第１の配列では、ビデオメディアオブジェクトタイプの実例が、写真メディアオブジェクトタイプの左側の主題的インスタンスと写真メディアオブジェクトタイプの右側のインスタンスとをそれぞれが含む一対の隣り合ったスロットの上に配置されたスロットに割り当てられている。第２の配列は、スロットの３つのシーケンス（並び）の垂直方向の配列からなり、ここで、
・一番上のシーケンス内のスロットはそれぞれ、次のメディアオブジェクトタイプのインスタンスの並び、すなわち、ブランク、写真、ブランク、写真、ブランク、写真、ブランク、写真、ブランク、写真、がこの順で並んだものを含み、
・中間にあるシーケンス内のスロットはそれぞれ、次のメディアオブジェクトタイプのインスタンスの並び、すなわち、写真、ブランク、写真、ブランク、写真、ブランク、写真、ブランク、がこの順で並んだものを含み、
・一番下のシーケンス内のスロットはそれぞれ、次のメディアオブジェクトタイプのインスタンスの並び、すなわち、ブランク、写真、ブランク、写真、ブランク、写真、ブランク、写真、がこの順で並んだものを含む。
【００３３】
これらの実施形態のうちのいくつかでは、「ブランク」メディアオブジェクトタイプは、スロットの空間（spatial dimension）を満たすグラフィックメディアオブジェクトに対応し、該スロット（または該スロットの空間）に対して、該メディアオブジェクトタイプには同じ色（たとえば白）が割り当てられた。これらの実施形態のうちの他の実施形態では、「ブランク」メディアオブジェクトタイプは、設計者が、連続するメディアオブジェクトの間のギャップまたは他の移行部分を表すために選択した何らかの他のコンテンツからなる。
【００３４】
図９Ａは、同じ相対的時空間レイアウトのテキスト仕様６２及びグラフィック仕様６４の実施形態を示す。これらの実施形態は、メディアオブジェクトタイプの第２の配列（「PHOTOS」）の上に配置されたメディアオブジェクトタイプの第１（「TOP」）の配列を指定する。第１の配列は、テキストメディアオブジェクトタイプの第１のインスタンス、ブランクメディアオブジェクトのインスタンス、及びテキストメディアオブジェクトタイプの第２のインスタンスの水平方向の配列からなり、該ブランクメディアオブジェクトのインスタンスの左側にテキストメディアオブジェクトタイプの該第１のインスタンスがあり、テキストメディアオブジェクトタイプの該第２のインスタンスの左側に該ブランクメディアオブジェクトのインスタンスがある。第２の配列は、メディアオブジェクトタイプの左側グループ、メディアオブジェクトタイプの中間のグループ、及び、メディアオブジェクトタイプの右側グループの水平方向の配列からなり、メディアオブジェクトタイプの該中間のグループの左側にメディアオブジェクトタイプの該左側グループがあり、メディアオブジェクトタイプの該右側グループの左側にメディアオブジェクトタイプの該中間のグループがある。該左側グループと該右側グループのそれぞれは、各々のスロットが写真メディアオブジェクトタイプのそれぞれのインスタンスを含むところの３つのスロットの垂直方向の配列からなり、中間のグループは、各々のスロットが写真メディアオブジェクトタイプのそれぞれのインスタンスを含むところの２つのスロットの垂直方向の配列からなる。
【００３５】
図９Ｂは、図９Ａに示す相対的時空間レイアウト仕様に対応するメディアオブジェクトの確定された時空間レイアウト６６の例示的な実施形態を示す。
【００３６】
Ｖ．時空間レイアウト生成器の例示的な実施形態
Ａ．導入
図１０は、時空間レイアウト生成器１２の実施形態７２、ディスプレイ７４、１組の相対的時空間レイアウト仕様７８を格納しているデータベース７６を備える時空間レイアウト生成システム１０の実施形態７０を示す。時空間レイアウト生成器７２は、メタデータ抽出モジュール８０、最適化モジュール８２、及び、出力生成モジュール８４を備える。
【００３７】
時空間レイアウト生成器７２は、メディアオブジェクト８８のコレクション８６に作用する。該コレクション（またはメディアオブジェクト８８）を、ユーザーによって指定することができ、または、時空間レイアウト生成器７２によって自動的に識別することができる。メタデータ抽出モジュール８０は、メディアオブジェクト８８の各々から、アスペクト比、及び（妥当な場合には）持続時間を含む種々のパラメータに対する値を抽出して、抽出した値を最適化モジュール８２に渡す。
【００３８】
最適化モジュール８２は、多次元最適化処理にしたがってメディアオブジェクト８８の確定された時空間レイアウトにおけるスロットを画定（または定義）する空間パラメータ及び時間パラメータの値を決定する。最適化モジュール８２は、メディアオブジェクト８８の確定された時空間レイアウトにおけるスロットを画定する空間パラメータ及び時間パラメータの値を決定する処理において、種々の多次元最適化法のうちの任意の１つを使用することができる。使用可能な最適化法の例示的なタイプには、シミュレーテッドアニーリング最適化法（simulated annealing optimization method）、山登り最適化法（hill climbing optimization method）、滑降シンプレックス最適化法（downhill simplex optimization method）、最急降下最適化法（steepest descent optimization method）、及び、遺伝的最適化法（genetic optimization method）があるが、これらには限定されない。
【００３９】
最適化モジュール８２は、パラメータ値を出力生成モジュール８４に渡し、該出力生成モジュール８４は、受け取ったパラメータ値から確定された時空間レイアウト仕様９０を生成する。
【００４０】
時空間レイアウト生成システム１０は、ディスプレイ７４に、該確定された時空間レイアウト仕様９０に対応するメディアオブジェクト８８の確定された時空間レイアウトをレンダリングする。
【００４１】
Ｂ．確定された時空間レイアウトを決定するためのシミュレーテッドアニーリング最適化処理の例示的な実施形態
１．導入
このセクションでは、メイン呼び出しプロセスと主シミュレーテッドアニーリングルーチンを含むシミュレーテッドアニーリング法の例示的な実施形態を説明する。シミュレーテッドアニーリング法は、確定された時空間レイアウトの候補を特徴付ける目的関数（objective function）を最適化するプロセスにしたがって、空間パラメータ値及び時間パラメータ値からなる異なるそれぞれの組によって画定されたメディアオブジェクト８８の確定された時空間レイアウトの連続する候補を通じて、メディアオブジェクト８８の確定された時空間レイアウトの最初の候補から、確定された時空間レイアウト仕様９０に対応する最終の確定された時空間レイアウトまでの、メディアオブジェクト８８の確定された時空間レイアウトの一連の連続する候補を確定することを含む。
【００４２】
２．主シミュレーテッドアニーリングルーチンの例示的な実施形態
図１１は、確定された時空間レイアウト仕様２０を生成する際に、図２の時空間レイアウト生成法の１実施形態で使用される主シミュレーテッドアニーリング最適化ルーチンの１実施形態を示す。
【００４３】
図１１の主シミュレーテッドアニーリング最適化ルーチンによれば、最適化モジュール８２は、Accept変数の値を０に初期化する（図１１のブロック９２）。最適化モジュール８２は、無作為の（すなわち任意の）レイアウト候補を決定する（図１１のブロック９４）。レイアウト候補は、典型的には、表示領域においてメディアオブジェクト８８のそれぞれの確定されたレイアウトを画定する空間パラメータ及び時間パラメータの値を含む状態ベクトルによって指定される。最適化モジュール８２は、レイアウト候補を特徴付ける目的関数のスコアと現在のスコアの差（Δscore）を求める（図１１のブロック９６）。
【００４４】
Δscore＞０の場合（図１１のブロック９８）は、最適化モジュール８２は、現在のスコアを候補スコアと同じに設定し（図１１のブロック１００）、Acceptの値をインクリメント（増分）し（図１１のブロック１０２）、現在の確定された時空間レイアウトを、確定された時空間レイアウトの候補と同じに設定する（図１１のブロック１０４）。繰り返しの回数がＮ（たとえば１００）に等しくない場合（図１１のブロック１０６）は、プロセスは繰り返され、そうでない場合には、最適化モジュール８２は、Accept変数の値をメイン呼び出しプロセスに返す（図１１のブロック１０７）。
【００４５】
Δscore≦０の場合（図１１のブロック９８）は、最適化モジュール８２は、移動受理確率関数（move acceptance probability function）ｆ（Δscore,ｔ）がＰより大きいか否か（図１１のブロック１０８）を判定する。ここで、Ｐは、ランダム（無作為）に生成されたそれぞれの疑似確率値を有するパラメータである。いくつかの実施形態では、ランダムな移動関数（random move function）は、ｅΔscore/tによって与えられ、Ｐは［０、１）の範囲のランダムな値（または乱数値）を有する。ｆ（Δscore,ｔ）＞Ｐの場合（図１１のブロック１０８）は、最適化モジュール８２は、現在のスコアを候補スコアと同じに設定し（図１１のブロック１００）、Accept値をインクリメント（図１１のブロック１０２）し、現在の確定された時空間レイアウトを確定された時空間レイアウトの候補と同じに設定する（図１１のブロック１０４）。ｆ（Δscore,ｔ）≦Ｐ（図１１のブロック１０８）で、かつ、繰り返しの回数がＮに等しくない場合（図１１のブロック１０６）は、プロセスは繰り返される。ｆ（Δscore,ｔ）≦Ｐ（図１１のブロック１０８）で、かつ、繰り返しの回数がＮ（たとえば１００）に等しい場合（図１１のブロック１０６）は、最適化モジュール８２は、Accept変数の値をメイン呼び出しプロセスに返す（図１１のブロック１０７）。
【００４６】
３．メイン呼び出しプロセスの例示的な実施形態
図１１のシミュレーテッドアニーリング最適化法は典型的には、主シミュレーテッドアニーリングルーチンの繰り返し回数、及び温度パラメータｔを設定するクーリングスケジュール（cooling schedule）を制御するメイン呼び出しプロセスによって何度も呼び出され、該温度（または該クーリングスケジュール）によって、任意の特定のレイアウト候補がより低い目的関数スコアを有するにもかかわらず受け入れられる可能性が調整される。いくつかの実施形態では、メイン呼び出しプロセスは、最適化モジュール８２が主シミュレーテッドアニーリングルーチンから戻る毎に、温度パラメータｔを変更する。種々の異なるアニーリングスケジュールを使用して温度パラメータを変更することができる。たとえば、いくつかの実施形態では、温度パラメータは、最適化モジュール８２が主シミュレーテッドアニーリングルーチンから戻る毎に減少させられる。温度パラメータを減少させる量を、一定量とすることができ、または、費やした時間配分の一部（または割合）の関数として、または、現在の温度値の関数として、変化させることができる。
【００４７】
図１２は、図２の時空間レイアウト生成法の１実施形態において図１１の主シミュレーテッドアニーリングルーチンと共に使用される適応型クーリングスケジュールの１実施形態を示す。図１２の方法によれば、最適化モジュール８２は、温度パラメータｔの値を初期値（典型的には高い値）に初期化する。最適化モジュール８２は、次に、ループカウンタRacceptが高い値Ｈから低い値Ｌに逐次減少していくFORループの実行を開始する（図１２のブロック１１０）。Accept変数の現在の値がループカウンタの現在の値に等しい場合（図１２のブロック１１２）は、最適化モジュール８２は次の繰り返しに進む（図１２のブロック１１０）。上述したように、Accept変数の値は、図１１の主シミュレーテッドアニーリングルーチンによって設定される。Accept変数の現在の値がループカウンタの現在の値に等しくない場合（図１２のブロック１１２）は、最適化モジュール８２は、図１１の主シミュレーテッドアニーリングルーチンを現在の温度値ｔで実行することによってAccept変数の値を設定する（図１２のブロック１１４）。Accept変数の返された値が現在のループカウント値よりも大きい場合（図１２のブロック１１６）は、最適化モジュール８２は温度値を小さくする（図１２のブロック１１８）。いくつかの実施形態では、最適化モジュール８２は、一定の割合（たとえば１％）だけ現在の温度値を減少させる。Accept変数の返された値が現在のループカウント値以下の場合（図１２のブロック１１６）は、最適化モジュール８２は温度値を大きくする（図１２のブロック１１８）。いくつかの実施形態では、最適化モジュール８２は、一定の割合（たとえば１％）だけ現在の温度値を増加させる。
【００４８】
いくつかの実施形態では、最適化モジュール８２は、図１２のブロック１１０のFORループを抜けた後でシミュレーテッドアニーリング法を終了する。
【００４９】
他の実施形態では、最適化モジュール８２は、図１２のブロック１１０のFORループを抜けた後で、非適応型クーリングスケジュールを使用して図１１の主シミュレーテッドアニーリングルーチンの実行を継続する。このプロセスでは、温度パラメータｔの値は、指定された繰り返し数（たとえば１０００）に対して、図１２の適応型クーリングプロセスの終わりの時点における値から一定の割合（たとえば１％）だけ減少させられる。これらの実施形態のうちのいくつかでは、最適化モジュール８２は、この指定された繰り返し数の後（すなわち、該繰り返し回数だけ実行された後）、シミュレーテッドアニーリング法を終了する。これらの実施形態のうちの他の実施形態では、最適化モジュール８２は、この指定された繰り返し数の後（すなわち、該繰り返し回数だけ実行された後）、図１１の主シミュレーテッドアニーリングルーチンの実行を継続する。このプロセスでは、最適化モジュール８２は、繰り返す毎に温度パラメータｔの値を０に設定して、指定された繰り返し数（たとえば１０００）だけ図１１の主シミュレーテッドアニーリングルーチンを実行する。
【００５０】
４．確定された時空間レイアウト候補の各々にスコアをつける
上述したように、最適化モジュール８２は、確定された時空間レイアウト候補の各々についてそれぞれのスコアを計算する。いくつかの実施形態では、スコアは、各メディアオブジェクトのパラメータが、該メディアオブジェクトに割り当てられた時空間スロットの対応するパラメータにどれだけの近さで合致するかを測る個々のマッチングスコアの重み付けされた幾何平均（または相乗平均）である。これらの実施形態のうちのいくつかでは、各メディアオブジェクトに対するそれぞれのマッチングスコアは、種々の要素（または要因）から計算され、該要素の少なくともいくつかによって、メディアオブジェクト及びそれの現在のスロットに対する特定のパラメータ（たとえば、アスペクト比や持続時間）の値のそれぞれの比に関して該現在のスロットに対するメディアオブジェクトの近似度が測られる。
【００５１】
いくつかの実施形態では、グラフィックメディアオブジェクト（たとえば、写真やビデオ）に対するマッチングスコアは、ひずみファクター（distort factor。または歪み率）及びエリアファクターの関数である。歪みファクターは、メディアオブジェクトのアスペクト比がそれの現在のスロットのアスペクト比にどれだけの近似度で合致しているかを測るものである。エリアファクターは、メディアオブジェクトに割り当てられている表示領域の一部（または小部分）が、利用可能な表示領域の均等な分割部にどれだけの近似度で一致するかを測るものである。いくつかの実施形態では、マッチングスコアは、歪みファクターとエリアファクターの重み付き平均（加重平均）に対応（または一致）する。これらの実施形態のうちのいくつかでは、歪みファクターは、エリアファクターよりも大きく重み付けされている。
【００５２】
いくつかの実施形態では、時間ベースではないメディアオブジェクト（たとえば写真）の各々のマッチングスコアは、該オブジェクトの現在のスロットの持続時間が、該メディアオブジェクトについて指定された好ましい持続時間にどれだけの近さで合致しているかを測る持続時間ファクターをさらに含む。好ましい持続時間を、ユーザーが指定することができ、または、デフォルト（既定値）として指定することができる。持続時間ファクターは、典型的には、歪みファクターとエリアファクターの重み付き平均（加重平均）に含められる。
【００５３】
いくつかの実施形態では、時間ベースのメディアオブジェクト（たとえばビデオ）の各々のマッチングスコアは、該オブジェクトの持続時間が、該オブジェクトの現在のスロットの持続時間にどれだけの近さで合致しているかを測る持続時間ファクターをさらに含む。持続時間ファクターは、典型的には、歪みファクターとエリアファクターの重み付き平均（加重平均）に含められる。
【００５４】
いくつかの実施形態では、テキストベースのメディアオブジェクトのマッチングスコアは、ユーザーによってまたはデフォルト（既定値）として設定されることができる、高さ、幅、及び持続時間の好ましい値の関数である。これらの実施形態のいくつかでは、テキストベースのメディアオブジェクトのマッチングスコアは、幅ファクターと高さファクターと持続時間ファクターの積に一致（または相当）する。幅ファクターは、スロットの幅に対する好ましい幅の比と、該好ましい幅に対するスロットの幅の比との小さい方に一致（または相当する）。高さファクターは、スロットの高さに対する好ましい高さの比と、該好ましい高さに対するスロットの高さの比との小さい方に一致（または相当）する。持続時間ファクターは、スロットの持続時間が、テキストベースのメディアオブジェクトについて指定された好ましい持続時間にどれだけの近さで合致するかを測るものである。
【００５５】
いくつかの実施形態では、マッチングスコアは、指定された閾値寸法を下回る１つ以上の空間的寸法または時間的寸法（時間的長さ）を有するスロットに割り当てられたメディアオブジェクトのマッチングスコアを減少させる１つ以上のペナリゼーションファクター（penalization factor）をさらに含む。
【００５６】
VI．時空間レイアウト生成システムの例示的なアーキテクチャ
時空間レイアウト生成システム１０の実施形態を、任意の特定のハードウェア、ファームウェア、またはソフトウェア構成に限定されない、１つ以上の別個のモジュール（またはデータ処理コンポーネント）によって実施することができる。例示した実施形態では、それらのモジュールを、デジタル電子回路（たとえば、デジタル信号プロセッサ（DSP）などの特定用途向け集積回路）、または、コンピュータハードウェア、ファームウェア、デバイスドライバ、または、ソフトウェアを含む任意のコンピューティング環境またはデータ処理環境で実施することができる。いくつかの実施形態では、モジュールの機能は、単一のデータ処理コンポーネントに組み合わされる。いくつかの実施形態では、１つ以上のモジュールの各々のそれぞれの機能は、複数のデータ処理コンポーネントのそれぞれの組によって実行される。
【００５７】
いくつかの実施例では、時空間レイアウト生成システム１０の実施形態によって実行される方法を実施するための処理命令（たとえば、コンピュータソフトウェアなどのコンピュータ読み取り可能コード）、並びに、（生成された）データは、１つ以上のコンピュータ読み取り可能媒体に格納される。これらの命令及びデータを具現化する（たとえば記憶する）のに適した記憶装置には、たとえば、EPROM、EEPROM、及びフラッシュメモリ装置（デバイス）などの半導体記憶装置や、内部ハードディスク及びリムーバルハードディスクなどの磁気ディスク、光磁気ディスク、DVD-ROM/RAM、及びCD-ROM/RAMなどの不揮発性コンピュータ読み取り可能メモリのあらゆる形態が含まれる。
【００５８】
一般に、時空間レイアウト生成システム１０の実施形態を、コンピュータ（たとえば、ラップトップまたはノートブックコンピュータ、デスクトップコンピュータ、ワークステーションコンピュータ、及びサーバーコンピュータ）を含む様々な電子装置のうちの任意の１つで実施することができる。
【００５９】
図１３は、コンピュータ１４０で動作する１つ以上のソフトウェアモジュールによって実施される時空間レイアウト生成システム１０の１実施形態１３８を示す。コンピュータ１４０は、処理ユニット１４２、システムメモリ１４４、及び、処理ユニット１４２をコンピュータ１４０の種々のコンポーネントに結合するシステムバス１４６を備える。処理ユニット１４２は、典型的には、１つ以上のプロセッサを備えており、該プロセッサの各々を、市販されている種々のプロセッサのうちの任意の１つの形態とすることができる。システムメモリ１４４は、典型的には、コンピュータ１４０の始動ルーチンを含む基本入力／出力システム（BIOS）を格納している読み出し専用メモリ（ROM）、並びに、ランダムアクセスメモリ（RAM）を備える。システムバス１４６を、メモリバス、周辺バス（または周辺機器用バス）、またはローカルバスとすることができ、かつ、PCI、VESA、マイクロチャネル（Microchannel）、ISA、及びEISAを含む任意の種々のバスプロトコルと互換性があるものとすることができる。コンピュータ１４０はまた、永続型（または持続型）記憶装置１４８（たとえば、ハードディスク装置、フロッピーディスク装置、CDROM装置、磁気テープ装置、フラッシュメモリ装置、デジタルビデオディスク）を備え、該記憶装置１４８は、システムバス１４６に接続されて、データ、データ構造、及び、コンピュータ実行可能命令用の不揮発性または永続性の記憶を提供する１つ以上のコンピュータ読み取り可能媒体ディスクを含む。
【００６０】
ユーザーは、１つ以上の入力装置１５０（たとえば、キーボード、コンピュータマウス、マイクロホン、ジョイスティック、及びタッチパッド）を使用してコンピュータ３０と相互作用（たとえば、コマンドまたはデータの入力）をすることができる。情報を、表示モニター１５２においてユーザーに表示されるグラフィカルユーザーインターフェース（GUI）を介して表示（提示）することができ、該表示モニター１５２は、ディスプレイコントローラ１５４によって制御される。コンピュータ３０は典型的には、スピーカーやプリンタなどの周辺出力装置も備える。１つ以上の遠隔にあるコンピュータを、ネットワークインターフェースカード（NIC）１５６を介してコンピュータ１４０に接続することができる。
【００６１】
図１３に示すように、システムメモリ１４４はまた、時空間レイアウト生成システム１３８、GUIドライバ１５８、並びに、メディアオブジェクト１８と中間の処理データと出力データを含む他のデータ１６０を格納する。時空間レイアウト生成システム１３８は、GUIドライバ１５８及びユーザー入力１５０とインターフェース（または連携）して、確定された時空間レイアウト仕様の生成を制御する。いくつかの実施形態では、時空間レイアウト生成システム１３８は、さらに、確定された時空間レイアウト仕様２０を処理することによって、該仕様２０によって指定されたメディアオブジェクト１８の時空間レイアウトをレンダリングするように構成された少なくとも１つのビデオプレーヤー及びスクリプトインタプリタを備える。いくつかの実施形態では、時空間レイアウト生成システム１３８は、ユーザーに、確定された時空間レイアウト仕様２０を生成する処理を案内（または誘導）するグラフィカルユーザーインターフェースを生成する際に、GUIドライバ１５８、ユーザー入力１５０、相対的時空間レイアウト仕様１４、及び、他のデータ構造とインターフェース（または連携）する。時空間レイアウト生成システム１３８は、また、GUIドライバ１５８、確定された時空間レイアウト仕様２０、及び他のデータ構造とインターフェース（または連携）して、メディアオブジェクト１８の確定された時空間レイアウトの表示モニター１５２におけるユーザーへの提示（プレゼンテーション）を制御する。この提示（プレゼンテーション）をレンダリングするために使用される種々のメディアオブジェクト１８を永続型記憶装置１４８に局所的に格納することができ、及び／または、該オブジェクト１８を遠隔で格納してNIC１５６を介して該オブジェクト１８にアクセスすることができる。
【００６２】
VII．結論
本明細書で説明した実施形態は、メディアオブジェクトのコレクションを時空間レイアウトに編成することができ、この場合、各メディアオブジェクトは、空間的及び時間的に分割されたスケジューリングされたレンダリング（またはプレゼンテーション）空間中のそれぞれのスロットに割り当てられる。時空間レイアウトは、典型的には、プレゼンテーション空間の空間的及び時間的区分を時空間スロットへと誘導し、及び、それらのスロットへのメディアオブジェクトの割り当てを誘導する相対的時空間レイアウト仕様にしたがって生成される。いくつかの実施形態では、相対的時空間レイアウト仕様は、任意の特定のメディアオブジェクトとは無関係にマルチメディア関連の熟練技能者によって生成される。こうして、相対的時空間レイアウト仕様は、不慣れなユーザーが該ユーザーのメディアオブジェクトのコレクションの高品質の提示（プレゼンテーション）を生成するために利用できるようなやり方で、マルチメディア専門の技能者の技能及び美的センスを具現化することができる。本明細書で説明した実施形態は、コンシューマー向けの応用領域において大きな利点を提供し、それらの実施形態は、本質的に不統一なコンテンツであって、様々な異なるフォーマット及び解像度のコンテンツを有するメディアオブジェクトに対して、複雑なイベントを適切な形態で記録（または文書化）できるようにする。他の実施形態も特許請求の範囲に含まれる。
【背景技術】
【０００１】
個人や組織は、静止画、テキスト、グラフィックス、アニメ画像（動画グラフィックス）、フルモーションビデオ画像などのデジタルコンテンツの大量のコレクション（収集物）を速やかに蓄積している。このコンテンツを、文書、カタログ、プレゼンテーション、スチール写真、コマーシャルビデオ、ホームムービー、及び、１つ以上の関連するデジタルコンテンツファイルを記述しているメタデータなどの様々な異なる形態で個別に、または、それらの形態を組み合わせて提示することができる。これらのコレクションは、その数が多くなると共にますます多様化してきているので、個人や組織は、彼らのコレクション中のデジタルコンテンツを編成して提示するためのシステム及び方法を次第に要求するようになるだろう。この要求を満たすためには、デジタルイメージ（画像）コンテンツを編成して提示するための様々な異なるシステム及び方法が必要である。
【発明の概要】
【０００２】
本発明は、１側面において、相対的な時空間レイアウト仕様にしたがって、確定された時空間レイアウト仕様（または、明確に限定された時空間レイアウト仕様。以下同じ）を自動的に生成する方法を特徴とする。この相対的な時空間レイアウト仕様は、メディアオブジェクトタイプの相対的な空間的位置及び時間的順序を記述する。この確定された時空間レイアウト仕様は、ある時間にわたる表示領域内のメディアオブジェクトのレイアウトを記述する。確定された時空間レイアウト仕様を生成するプロセスには、メディアオブジェクトのそれぞれについて、それぞれのレンダリング期間にわたって、表示領域内のそれぞれのウィンドウに対応するそれぞれの時空間スロットを決定することが含まれ、該レンダリング期間において、メディアオブジェクトがレンダリングされるようにスケジューリング（計画）されている。この確定された時空間レイアウト仕様は出力される。
【０００３】
本発明は、また、コンピュータに上述の方法を実施させるコンピュータ読み取り可能命令を格納する装置及びコンピュータ読み取り可能媒体を特徴とする。
【０００４】
本発明の他の特徴及び利点は、以下の説明、並びに、図面及び特許請求の範囲から明らかになるであろう。
【図面の簡単な説明】
【０００５】
【図１】相対的な時空間レイアウト仕様にしたがって１組のメディアオブジェクトを処理して、確定された時空間レイアウト仕様を生成する時空間レイアウト生成器を備える時空間レイアウト生成システムの１実施形態のブロック図である。
【図２】時空間レイアウト生成方法の１実施形態の流れ図である。
【図３】相対的な時空間レイアウト仕様の１実施形態の線図である。
【図４】図３の相対的時空間レイアウト仕様にしたがって生成されたメディアオブジェクトの確定された時空間レイアウトの１実施形態の略図である。
【図５Ａ】メディアオブジェクトの確定された時空間レイアウトの１実施形態から抽出された１組の画像フレームの略図である。
【図５Ｂ】図５Ａに示すイメージフレーム（画像フレーム）の要素と、対応する相対的な時空間レイアウト仕様の要素との間の対応関係を示す。
【図６】相対的な時空間レイアウト仕様の１実施形態の２つの表現の略図である。
【図７】相対的な時空間レイアウト仕様の１実施形態の２つの表現の略図である。
【図８】相対的な時空間レイアウト仕様の１実施形態の２つの表現の略図である。
【図９Ａ】相対的な時空間レイアウト仕様の１実施形態の２つの表現の略図である。
【図９Ｂ】図９Ａに示された相対的な時空間レイアウト仕様にしたがって生成されたメディアオブジェクトの確定された時空間レイアウトの１実施形態の線図である。
【図１０】図１に示す時空間レイアウト生成システムの１実施形態のブロック図である。
【図１１】図２の時空間レイアウト生成方法の１実施形態で使用される多次元最適化処理の１実施形態のブロック図である。
【図１２】図２の時空間レイアウト生成方法の１実施形態において、図１１の多次元最適化処理と共に使用される適応型スケジューリング処理の１実施形態のブロック図である。
【図１３】図１の時空間レイアウト生成システムの１実施形態を実施するようにプログラムされたコンピュータシステムの１実施形態のブロック図である。
【発明を実施するための形態】
【０００６】
以下の説明では、同様の要素には同じ参照番号が付されている。さらに、図面は、例示的な実施形態の主要な特徴を概略的に例示することが意図されている。図面は、実際の実施形態の全ての特徴を示すことも、図示した要素の相対的な寸法を示すことも意図されておらず、一律の縮尺に従わずに描かれている。
【０００７】
Ｉ．導入
後で詳細に説明する実施形態は、メディアオブジェクトのコレクションを時空間レイアウトに編成することができ、該レイアウトにおいて、メディアオブジェクトの各々は、空間的かつ時間的に分割されたスケジューリングされたレンダリング（またはプレゼンテーション（提示など））空間内のそれぞれのスロットに割り当てられる。
【０００８】
時空間レイアウトは、典型的には、プレゼンテーション空間の時空間スロットへの空間的及び時間的分割を誘導し、メディアオブジェクトの該スロットへの割り当てを誘導する相対的な時空間レイアウト仕様（以下、相対的時空間レイアウト仕様という）にしたがって生成される。相対的時空間レイアウト仕様は、メディアオブジェクトタイプの相対的空間レイアウト、及び、該メディアオブジェクトタイプを特定のレンダリングシーケンスで配列するためのスケジュールの一般的な仕様である。相対的時空間レイアウト仕様は、任意のメディアオブジェクトまたはメディアオブジェクトメタデータ（たとえば、持続時間、アスペクト比、解像度など）に関係なく相対的時空間レイアウトを規定（または指定）する。いくつかの実施形態では、相対的時空間レイアウト仕様は、マルチメディア関連の熟練した技能者によって任意の特定のメディアオブジェクトとは無関係に生成される。こうして、相対的時空間レイアウト仕様は、不慣れなユーザーが、該ユーザーのメディアオブジェクトのコレクションの高品質のプレゼンテーションを生成するために利用可能なやり方で、マルチメディアを専門とする熟練技能者の技能及び美的センスを具現化することができる。
【０００９】
本明細書で説明される実施形態は、コンシューマー（消費者）向けの応用領域において大きな利点を提供し、それらの実施形態は、本質的にむらがあって（すなわち、統一性がない）、様々な異なるフォーマット及び解像度のコンテンツを有するメディアオブジェクトに対して、複雑なイベントを適切な形態で記録（または文書化）できるようにする。
【００１０】
II．用語の定義
「メディアオブジェクト」という用語は、テキスト、音声（オーディオ）、グラフィックス、アニメ画像（または動画グラフィックス）、静止画像、フルモーションビデオ、及び、物体の電子的表現物を含む、任意の形態のデジタルコンテンツを広く指す。このコンテンツを、ひとまとめにして、文書、注釈、プレゼンテーション、音楽、スチール写真、コマーシャルビデオ、ホームムービー、及び、１つ以上の関連するデジタルコンテンツファイルを記述するメタデータを含む様々な異なる形態で個別に、または、いくつかを組み合わせて提示することができる。イメージベースのメディアオブジェクト（あるいは単に「画像」）を、任意のタイプのデジタル画像すなわち電子画像の完全なバージョンまたは部分的なバージョンとすることができ、それらの画像には、イメージセンサ（たとえば、ビデオカメラ、（電子）スチールカメラ、または、光学スキャナー）によって撮像された画像、または、そのような画像の処理されたバージョン（たとえば、フィルタリングされたバージョン、再フォーマットされたバージョン、強調または他の変更を施されたバージョン）、コンピュータによって生成されたビットマップもしくはベクターグラフィック画像、テキスト画像（たとえば、テキスト（文字）を含むビットマップ画像）、図像的画像（iconographic image）が含まれる。「メディアオブジェクト」という用語は、１つ以上のメディアオブジェクトの凝集したグループまたはコレクションから形成された単一要素メディアオブジェクトと複数要素メディアオブジェクトの両方を包含する。特定の多要素メディアオブジェクトへの単一要素メディアオブジェクトの割り当ては、構成要素である単一要素メディアオブジェクト同士が関連するということを意味している。一般に、複数要素メディアオブジェクト中の単一要素メディアオブジェクトのタイプは同じ場合も異なる場合もある。メディアオブジェクトは典型的には、１つ以上のコンピュータ読み取り可能媒体上の１つ以上のデータベースに格納される。メディアオブジェクトは、ローカルなデータベース、または、ローカルエリアネットワーク及びグローバル通信ネットワークを介してアクセス可能な１つ以上のリモートのデータベースに物理的に格納することができる。いくつかのメディアオブジェクトは、ピアツーピア・ネットワーク接続を介してアクセス可能なリモートのデータベースに格納することもできる。
【００１１】
本明細書で使用される「相対的時空間レイアウト」という用語は、メディアオブジェクトタイプの相対的な空間的配列及び相対的な時間的順序を指し、この場合、メディアオブジェクトタイプの絶対位置、及び、メディアオブジェクトの絶対レンダリング時間は指定されない。相対的時空間レイアウト仕様は、ある時間にわたるメディアオブジェクトタイプの相対的な空間位置を記述する。
【００１２】
本明細書で使用される「確定された時空間レイアウト」という用語は、メディアオブジェクトの位置、寸法（または次元）、及び、スケジューリングされたレンダリング期間（または周期）を記述する確定された時空間レイアウト仕様にしたがって、特定の順番で表示領域に並べられたメディアオブジェクトのレイアウトを指す。
【００１３】
「データ構造」という用語は、データが編成されて格納される物理的なレイアウト（またはフォーマット）を広く指す。
【００１４】
「コンピュータ」は、コンピュータ読み取り可能媒体に一時的にまたは永久的に格納されるコンピュータ読み取り可能命令（たとえばソフトウェア）にしたがってデータを処理する機械である。特定のタスクを実行する１組のそのような命令は、プログラムまたはソフトウェアプログラムと呼ばれる。
【００１５】
「コンピュータ読み取り可能媒体」という用語は、コンピュータが読み出すことが可能な情報を格納できる任意の媒体を指す。コンピュータ読み取り可能媒体の例には、不揮発性形態を含むあらゆる形態のコンピュータ読み取り可能メモリ（但し、これらには限定されない）を含む、命令及びデータを明白に具現化するのに適した記憶装置であり、該不揮発性形態には、EPROM、EEPROM、及びフラッシュメモリデバイス（装置）などの半導体記憶装置や、内部ハードディスク及びリムーバルハードディスクなどの磁気ディスク、光磁気ディスク、DVD-ROM／RAM、及びCD-ROM/RAMなどがある。
【００１６】
III. 概要
図１は、相対的時空間レイアウト仕様１４にしたがってメディアオブジェクト１８の組１６を処理して、確定された時空間レイアウト仕様２０を生成する時空間レイアウト生成器１２を備える時空間レイアウト生成システム１０の１実施形態を示す。この相対的時空間レイアウト仕様は、メディアオブジェクトタイプの相対的な空間位置及び相対的な時間的順序を記述し、一方、この確定された時空間レイアウト仕様２０は、ある時間にわたる表示領域内のメディアオブジェクト１８のレイアウトを記述する。
【００１７】
図２は、時空間レイアウト生成器１２によって実施される方法の１実施形態を示す。図２の方法によれば、時空間レイアウト生成器１２は、相対的時空間レイアウト仕様１４にしたがって、確定された時空間レイアウト仕様２０を自動的に生成する（図２のブロック２２）。このプロセスでは、時空間レイアウト生成器１２は、メディアオブジェクト１８の各々について、それぞれのレンダリング期間にわたる表示領域内のそれぞれのウィンドウに対応するそれぞれの時空間スロットを決定する。このレンダリング期間において、メディアオブジェクトは、レンダリングされるようにスケジューリングされる。
【００１８】
時空間レイアウト生成器１２は、確定された時空間レイアウト仕様２０を出力する（図２のブロック２４）。いくつかの実施形態では、時空間レイアウト生成器１２は、確定された時空間レイアウト仕様２０をコンピュータ読み取り可能媒体に格納することによって該仕様２０を出力する。これらの実施形態では、時空間レイアウト生成器１２は、典型的には、空間的かつ時間的に分割されたスケジューリングされたレンダリング（またはプレゼンテーション）空間におけるスロットへのメディアオブジェクト１８の割り当てを記述するデータ構造（たとえば、テーブルまたはリスト）を含む仕様の形態で、確定された時空間レイアウト仕様２０を出力する。いくつかの実施形態では、この仕様は、XML（拡張マークアップ言語）ファイルフォーマットでコンピュータ読み取り可能媒体に格納される。
【００１９】
いくつかの実施形態では、時空間レイアウト生成システム１０は、確定された時空間レイアウト仕様２０にしたがってメディアオブジェクト１８の確定された時空間レイアウトをレンダリングする（レンダリングとは、描画、及び／または、視覚的に表示することを意味する）。たとえば、いくつかの実施形態では、時空間レイアウト生成システム１０は、ディスプレイにメディアオブジェクト１８の確定された時空間レイアウトをレンダリングする。このディスプレイを、たとえば、LCD（液晶ディスプレイ）、プラズマディスプレイ、ELディスプレイ（エレクトロルミネセント・ディスプレイ）、及びFED（電界放出ディスプレイ）などのフラットパネルディスプレイとすることができる。他の実施形態では、時空間レイアウト生成システム１０は、印刷媒体（たとえば、１枚以上の紙）にメディアオブジェクト１８の確定された時空間レイアウトをレンダリングする。
【００２０】
いくつかの実施形態では、確定された時空間レイアウト仕様２０は、ビデオプレーヤーがメディアオブジェクト１８の対応する時空間レイアウトを表示するためにレンダリングすることが可能な出力ビデオファイルに対応（または一致）する。これらの実施形態では、出力ビデオファイルは、ビデオファイルフォーマット（たとえば、AVI、MOV、MPEG-2、MPEG-4、Ogg、ASF、RealMedia、及び3gp）にしたがってコンピュータ読み取り可能媒体に格納される。いくつかの実施形態では、確定された時空間レイアウト仕様２０は、機械（たとえばコンピュータ）に、メディアオブジェクト１８の時空間レイアウトに対応する合成（または複合）ビデオを提示（または表示）させる構文解析可能なビデオ再生命令に対応（または一致）する。これらの実施形態では、これらの命令は、メディアオブジェクト１８の時空間レイアウトをレンダリングするためにスクリプトインタプリタ（たとえば、Adobe Flash（商標）プレーヤー）が実行または構文解析可能なマルチメディアオーサリングスクリプト言語（たとえば、Adobe Flash（商標））にしたがってコンピュータ読み取り可能媒体に格納される。いくつかの実施形態では、確定された時空間レイアウト仕様２０は、メディアオブジェクト１８の時空間レイアウトを表示領域に表示するやり方を記述するビデオ合成仕様（たとえば、スクリプト）に対応（または一致）する。これらの実施形態では、ビデオ合成仕様は、メディアオブジェクト１８の時空間レイアウトをレンダリングするために処理されることが可能な出力ビデオファイル（たとえば、AVIファイル）、または、１組の構文解析可能なビデオ再生命令（たとえば、Adobe Flash（商標）スクリプトやAviSynthスクリプト）を生成するビデオオーサリングツール（たとえば、Adobe Flash（商標）やAviSynth）によって処理される。
【００２１】
IV．相対的時空間レイアウトの指定
A．導入
上述したように、相対的時空間レイアウト仕様１４は、特定の時間的順序でメディアオブジェクトタイプの空間的レイアウトを記述し、この場合、メディアオブジェクトタイプの絶対位置、及び、メディアオブジェクトタイプの絶対レンダリング時間（期間）は指定されない。メディアオブジェクトタイプの相対的な空間位置を、たとえば、メディアオブジェクトタイプの相対的な空間位置を、互いに関連して、または、共通の基準点（たとえば、共通の座標系の端点すなわちエッジポイント）に関連して記述する任意のタイプのフロアプランモデル（floor plan model）にしたがって記述することができる。相対的時空間レイアウト仕様１４は、相対的なレンダリング空間（描画空間）のスロットへの分解を記述し、この場合、該スロットの各々は、メディアオブジェクトタイプのちょうど１つを含む。
【００２２】
図３は、相対的レンダリング空間の再帰的分割（または再帰的細分）モデルに対応（または一致）する相対的時空間レイアウト仕様１４の１実施形態を示す。この実施形態では、この分割モデルは、木構造２６に編成される２値時空間分割モデルである。木構造２６は、それぞれのメディアオブジェクトタイプに対応するリーフ（葉）ノード２８、３０、３２、３４、及び、該木構造２６によって分割されている相対的レンダリング空間の各区分に対応する内部ノード３６、３８、４０を有する。例示的な実施形態では、垂直のバー「｜」は、相対的レンダリング空間の垂直方向の空間分割（または分離）を示し、エムダッシュ「―」は、相対的レンダリング空間の水平方向の分割を示している。はるかに大きいという記号「＞＞」は、相対的レンダリング空間の時間的分割を示しており、相対的なレンダリングの順番は、左側の子ノードが右側の子ノードよりも先である。したがって、木構造２６によって指定される相対的レンダリング空間の再帰的分割は、２つの連続する写真メディアオブジェクトタイプの実例（インスタンス）の左側の時空間スロットに割り当てられている該ビデオメディアオブジェクトタイプの第１の実例（インスタンス）と、該ビデオメディアオブジェクトタイプの第２の実例（インスタンス）に対応し、この場合、写真メディアオブジェクトタイプの連続する実例は、右上の時空間スロットが該ビデオメディアオブジェクトタイプの第２の実例を含む右下の時空間スロットの上になるようにレンダリングされる。
【００２３】
図４は、２つのビデオ（すなわち、ビデオ_1とビデオ_2）及び２つの写真（すなわち、写真_1と写真_2）の確定された時空間レイアウトの例示的な実施例を示し、これらのビデオ及び写真は、２値木構造２６によって表される時空間分割仕様にしたがって、スケジューリングされたレンダリング空間４２中のそれぞれのスロットに割り当てられている。
【００２４】
木構造２６によって表される時空間分割仕様を、相対的レンダリング空間の再帰的時空間分割を規定する類似のテキストスキーマ（textual schema）を用いて指定することもできる。このスキーマによると、
・垂直バー「｜」は、相対的レンダリング空間の垂直方向の空間分割を示し、ここで、垂直バーの左側で識別される要素（すなわち、１つ以上のメディアオブジェクトタイプの１つ以上の実例）は、垂直バーの右側で識別される要素の左に配置される。
・ダッシュ「―」は、相対的レンダリング空間の水平方向の分割を示し、ここで、水平バーの左側で識別される要素（すなわち、１つ以上のメディアオブジェクトタイプの１つ以上の実例）は、水平バーの右側で識別される要素の上に配置される。
・はるかに大きいという記号「＞＞」は、相対的レンダリング空間の時間的分割を示し、該空間において、該記号の左側の要素は該記号の右側の要素に先行する。
【００２５】
いくつかの実施形態では、このスキーマは、さらに、相対的時空間レイアウト仕様の設計者が、スロットのうちの指定されたスロットに対して１つ以上のメディアオブジェクト選択基準を指定できるようにするタグまたは他のメタデータを含む。かかるメディアオブジェクト選択基準に応じて、時空間レイアウト生成器１２は、割り当てられるメディアオブジェクトがメディアオブジェクト選択基準を満たすというユーザーの指示に基づいて、組１６内のメディアオブジェクト１８の１つを指定されたスロットに割り当てる。該スキーマに含めることができるメディアオブジェクト選択基準タグの種々のタイプの中には以下のものがある。
・メディアタイプ指定（すなわち、「_MediaType_」）の反対側の下線は、確定された時空間レイアウトにおける対応する時空間スロットに割り当てられたメディアオブジェクトが、ユーザーが該確定された時空間レイアウト仕様２０によって伝えられることを望むテーマ(主題)を表すものとして該ユーザーによって識別された特定のメディアタイプ（MediaType）のメディアオブジェクトであるべきことを示している。
・メディアタイプ指定（すなわち、「MediaType！」）の直後の感嘆符（「！」）は、確定された時空間レイアウトにおける対応する時空間スロットに割り当てられたメディアオブジェクトが、ユーザーによって、確定された時空間レイアウト仕様２０の気候イベントを表すものとして識別された特定のメディアタイプ（MediaType）のメディアオブジェクトであるべきことを示している。
【００２６】
したがって、上記のスキーマによれば、図３に示す木構造２６によって表される時空間相対的分割仕様は、単一の表現からなるコンピュータ言語における以下のテキスト記述によって等価的に指定される。
ビデオ｜（（写真）＞＞写真）―ビデオ）
【００２７】
図５Ａは、連続する時間ｔ１、ｔ２、ｔ３、ｔ４、ｔ５、ｔ６におけるメディアオブジェクトの確定された時空間レイアウトの１実施形態から抽出された１組の画像フレームを示す。この実施形態は、以下の相対的分割仕様にしたがって、ユーザーによって選択された１０個の写真メディアオブジェクトと２つのビデオメディアオブジェクトの組から生成された。
【数１】
【００２８】
図５Ｂは、図５Ａに示す画像フレームの要素と、対応する相対的分割仕様の要素との間の対応関係を示す。この例では、表示領域４６の左上隅のウィンドウ内にレンダリングされた写真４４は、確定された時空間レイアウトの主題に関する写真としてユーザーによって選択され、表示領域４６の右上隅にあるビデオ４８は、確定された時空間レイアウトの気候ビデオとしてユーザーによって選択された。
【００２９】
Ｂ．相対的時空間レイアウト仕様の例示的な実施形態
前のセクションで説明した相対的時空間分割法によって、様々な異なる相対的時空間レイアウトを指定することができる。以下の相対的時空間レイアウトは、本明細書において例示のためだけに記載されたものであり、これらの分割法を用いて記述可能な可能性のある相対的レイアウトの数及び種類を制限するものではない。
【００３０】
図６は、同じ相対的時空間レイアウトのテキスト仕様５０及びグラフィック仕様（図的仕様）５２の実施形態を示す。これらの実施形態では、ビデオメディアオブジェクトタイプの２つの実例（インスタンス）が、隣り合っている写真メディアオブジェクトタイプの２つの実例の上のスロットにある写真メディアオブジェクトタイプの主題的インスタンス（主題に関する実例）の左側にあるそれぞれのスロットにおいて隣接して上下に配置されている。
【００３１】
図７は、同じ相対的時空間レイアウトのテキスト仕様５４及びグラフィック仕様５６の実施形態を示す。これらの実施形態は、１組の時空間スロットへのメディアオブジェクトタイプの第１の割り当てを指定し、この場合、１組の時空間スロットへのメディアオブジェクトタイプの第２の割り当てが、該第１の割り当てに時間的に後続する。これらの割り当ての各々は、ビデオメディアオブジェクトタイプのそれぞれの実例を含む３つの垂直方向に分散したスロットの左側にあるスロット内に配置されたビデオメディアオブジェクトタイプのそれぞれの実例から構成される。
【００３２】
図８は、同じ相対的時空間レイアウトのテキスト仕様５８及びグラフィック仕様６０の実施形態を示す。このテキスト記述は、コンピュータ言語が単一の表現の前に一連のステートメント（または文）を有することができることを示している。これらのステートメントは、変数の値を部分的な表現（該部分的な表現を、その後、最終的な表現に結合することができる）に設定することができる。これらの実施形態は、メディアオブジェクトタイプの第２の配列の左側に配置されるメディアオブジェクトタイプの第１の配列を指定する。この第１の配列では、ビデオメディアオブジェクトタイプの実例が、写真メディアオブジェクトタイプの左側の主題的インスタンスと写真メディアオブジェクトタイプの右側のインスタンスとをそれぞれが含む一対の隣り合ったスロットの上に配置されたスロットに割り当てられている。第２の配列は、スロットの３つのシーケンス（並び）の垂直方向の配列からなり、ここで、
・一番上のシーケンス内のスロットはそれぞれ、次のメディアオブジェクトタイプのインスタンスの並び、すなわち、ブランク、写真、ブランク、写真、ブランク、写真、ブランク、写真、ブランク、写真、がこの順で並んだものを含み、
・中間にあるシーケンス内のスロットはそれぞれ、次のメディアオブジェクトタイプのインスタンスの並び、すなわち、写真、ブランク、写真、ブランク、写真、ブランク、写真、ブランク、がこの順で並んだものを含み、
・一番下のシーケンス内のスロットはそれぞれ、次のメディアオブジェクトタイプのインスタンスの並び、すなわち、ブランク、写真、ブランク、写真、ブランク、写真、ブランク、写真、がこの順で並んだものを含む。
【００３３】
これらの実施形態のうちのいくつかでは、「ブランク」メディアオブジェクトタイプは、スロットの空間（spatial dimension）を満たすグラフィックメディアオブジェクトに対応し、該スロット（または該スロットの空間）に対して、該メディアオブジェクトタイプには同じ色（たとえば白）が割り当てられた。これらの実施形態のうちの他の実施形態では、「ブランク」メディアオブジェクトタイプは、設計者が、連続するメディアオブジェクトの間のギャップまたは他の移行部分を表すために選択した何らかの他のコンテンツからなる。
【００３４】
図９Ａは、同じ相対的時空間レイアウトのテキスト仕様６２及びグラフィック仕様６４の実施形態を示す。これらの実施形態は、メディアオブジェクトタイプの第２の配列（「PHOTOS」）の上に配置されたメディアオブジェクトタイプの第１（「TOP」）の配列を指定する。第１の配列は、テキストメディアオブジェクトタイプの第１のインスタンス、ブランクメディアオブジェクトのインスタンス、及びテキストメディアオブジェクトタイプの第２のインスタンスの水平方向の配列からなり、該ブランクメディアオブジェクトのインスタンスの左側にテキストメディアオブジェクトタイプの該第１のインスタンスがあり、テキストメディアオブジェクトタイプの該第２のインスタンスの左側に該ブランクメディアオブジェクトのインスタンスがある。第２の配列は、メディアオブジェクトタイプの左側グループ、メディアオブジェクトタイプの中間のグループ、及び、メディアオブジェクトタイプの右側グループの水平方向の配列からなり、メディアオブジェクトタイプの該中間のグループの左側にメディアオブジェクトタイプの該左側グループがあり、メディアオブジェクトタイプの該右側グループの左側にメディアオブジェクトタイプの該中間のグループがある。該左側グループと該右側グループのそれぞれは、各々のスロットが写真メディアオブジェクトタイプのそれぞれのインスタンスを含むところの３つのスロットの垂直方向の配列からなり、中間のグループは、各々のスロットが写真メディアオブジェクトタイプのそれぞれのインスタンスを含むところの２つのスロットの垂直方向の配列からなる。
【００３５】
図９Ｂは、図９Ａに示す相対的時空間レイアウト仕様に対応するメディアオブジェクトの確定された時空間レイアウト６６の例示的な実施形態を示す。
【００３６】
Ｖ．時空間レイアウト生成器の例示的な実施形態
Ａ．導入
図１０は、時空間レイアウト生成器１２の実施形態７２、ディスプレイ７４、１組の相対的時空間レイアウト仕様７８を格納しているデータベース７６を備える時空間レイアウト生成システム１０の実施形態７０を示す。時空間レイアウト生成器７２は、メタデータ抽出モジュール８０、最適化モジュール８２、及び、出力生成モジュール８４を備える。
【００３７】
時空間レイアウト生成器７２は、メディアオブジェクト８８のコレクション８６に作用する。該コレクション（またはメディアオブジェクト８８）を、ユーザーによって指定することができ、または、時空間レイアウト生成器７２によって自動的に識別することができる。メタデータ抽出モジュール８０は、メディアオブジェクト８８の各々から、アスペクト比、及び（妥当な場合には）持続時間を含む種々のパラメータに対する値を抽出して、抽出した値を最適化モジュール８２に渡す。
【００３８】
最適化モジュール８２は、多次元最適化処理にしたがってメディアオブジェクト８８の確定された時空間レイアウトにおけるスロットを画定（または定義）する空間パラメータ及び時間パラメータの値を決定する。最適化モジュール８２は、メディアオブジェクト８８の確定された時空間レイアウトにおけるスロットを画定する空間パラメータ及び時間パラメータの値を決定する処理において、種々の多次元最適化法のうちの任意の１つを使用することができる。使用可能な最適化法の例示的なタイプには、シミュレーテッドアニーリング最適化法（simulated annealing optimization method）、山登り最適化法（hill climbing optimization method）、滑降シンプレックス最適化法（downhill simplex optimization method）、最急降下最適化法（steepest descent optimization method）、及び、遺伝的最適化法（genetic optimization method）があるが、これらには限定されない。
【００３９】
最適化モジュール８２は、パラメータ値を出力生成モジュール８４に渡し、該出力生成モジュール８４は、受け取ったパラメータ値から確定された時空間レイアウト仕様９０を生成する。
【００４０】
時空間レイアウト生成システム１０は、ディスプレイ７４に、該確定された時空間レイアウト仕様９０に対応するメディアオブジェクト８８の確定された時空間レイアウトをレンダリングする。
【００４１】
Ｂ．確定された時空間レイアウトを決定するためのシミュレーテッドアニーリング最適化処理の例示的な実施形態
１．導入
このセクションでは、メイン呼び出しプロセスと主シミュレーテッドアニーリングルーチンを含むシミュレーテッドアニーリング法の例示的な実施形態を説明する。シミュレーテッドアニーリング法は、確定された時空間レイアウトの候補を特徴付ける目的関数（objective function）を最適化するプロセスにしたがって、空間パラメータ値及び時間パラメータ値からなる異なるそれぞれの組によって画定されたメディアオブジェクト８８の確定された時空間レイアウトの連続する候補を通じて、メディアオブジェクト８８の確定された時空間レイアウトの最初の候補から、確定された時空間レイアウト仕様９０に対応する最終の確定された時空間レイアウトまでの、メディアオブジェクト８８の確定された時空間レイアウトの一連の連続する候補を確定することを含む。
【００４２】
２．主シミュレーテッドアニーリングルーチンの例示的な実施形態
図１１は、確定された時空間レイアウト仕様２０を生成する際に、図２の時空間レイアウト生成法の１実施形態で使用される主シミュレーテッドアニーリング最適化ルーチンの１実施形態を示す。
【００４３】
図１１の主シミュレーテッドアニーリング最適化ルーチンによれば、最適化モジュール８２は、Accept変数の値を０に初期化する（図１１のブロック９２）。最適化モジュール８２は、無作為の（すなわち任意の）レイアウト候補を決定する（図１１のブロック９４）。レイアウト候補は、典型的には、表示領域においてメディアオブジェクト８８のそれぞれの確定されたレイアウトを画定する空間パラメータ及び時間パラメータの値を含む状態ベクトルによって指定される。最適化モジュール８２は、レイアウト候補を特徴付ける目的関数のスコアと現在のスコアの差（Δscore）を求める（図１１のブロック９６）。
【００４４】
Δscore＞０の場合（図１１のブロック９８）は、最適化モジュール８２は、現在のスコアを候補スコアと同じに設定し（図１１のブロック１００）、Acceptの値をインクリメント（増分）し（図１１のブロック１０２）、現在の確定された時空間レイアウトを、確定された時空間レイアウトの候補と同じに設定する（図１１のブロック１０４）。繰り返しの回数がＮ（たとえば１００）に等しくない場合（図１１のブロック１０６）は、プロセスは繰り返され、そうでない場合には、最適化モジュール８２は、Accept変数の値をメイン呼び出しプロセスに返す（図１１のブロック１０７）。
【００４５】
Δscore≦０の場合（図１１のブロック９８）は、最適化モジュール８２は、移動受理確率関数（move acceptance probability function）ｆ（Δscore,ｔ）がＰより大きいか否か（図１１のブロック１０８）を判定する。ここで、Ｐは、ランダム（無作為）に生成されたそれぞれの疑似確率値を有するパラメータである。いくつかの実施形態では、ランダムな移動関数（random move function）は、ｅΔscore/tによって与えられ、Ｐは［０、１）の範囲のランダムな値（または乱数値）を有する。ｆ（Δscore,ｔ）＞Ｐの場合（図１１のブロック１０８）は、最適化モジュール８２は、現在のスコアを候補スコアと同じに設定し（図１１のブロック１００）、Accept値をインクリメント（図１１のブロック１０２）し、現在の確定された時空間レイアウトを確定された時空間レイアウトの候補と同じに設定する（図１１のブロック１０４）。ｆ（Δscore,ｔ）≦Ｐ（図１１のブロック１０８）で、かつ、繰り返しの回数がＮに等しくない場合（図１１のブロック１０６）は、プロセスは繰り返される。ｆ（Δscore,ｔ）≦Ｐ（図１１のブロック１０８）で、かつ、繰り返しの回数がＮ（たとえば１００）に等しい場合（図１１のブロック１０６）は、最適化モジュール８２は、Accept変数の値をメイン呼び出しプロセスに返す（図１１のブロック１０７）。
【００４６】
３．メイン呼び出しプロセスの例示的な実施形態
図１１のシミュレーテッドアニーリング最適化法は典型的には、主シミュレーテッドアニーリングルーチンの繰り返し回数、及び温度パラメータｔを設定するクーリングスケジュール（cooling schedule）を制御するメイン呼び出しプロセスによって何度も呼び出され、該温度（または該クーリングスケジュール）によって、任意の特定のレイアウト候補がより低い目的関数スコアを有するにもかかわらず受け入れられる可能性が調整される。いくつかの実施形態では、メイン呼び出しプロセスは、最適化モジュール８２が主シミュレーテッドアニーリングルーチンから戻る毎に、温度パラメータｔを変更する。種々の異なるアニーリングスケジュールを使用して温度パラメータを変更することができる。たとえば、いくつかの実施形態では、温度パラメータは、最適化モジュール８２が主シミュレーテッドアニーリングルーチンから戻る毎に減少させられる。温度パラメータを減少させる量を、一定量とすることができ、または、費やした時間配分の一部（または割合）の関数として、または、現在の温度値の関数として、変化させることができる。
【００４７】
図１２は、図２の時空間レイアウト生成法の１実施形態において図１１の主シミュレーテッドアニーリングルーチンと共に使用される適応型クーリングスケジュールの１実施形態を示す。図１２の方法によれば、最適化モジュール８２は、温度パラメータｔの値を初期値（典型的には高い値）に初期化する。最適化モジュール８２は、次に、ループカウンタRacceptが高い値Ｈから低い値Ｌに逐次減少していくFORループの実行を開始する（図１２のブロック１１０）。Accept変数の現在の値がループカウンタの現在の値に等しい場合（図１２のブロック１１２）は、最適化モジュール８２は次の繰り返しに進む（図１２のブロック１１０）。上述したように、Accept変数の値は、図１１の主シミュレーテッドアニーリングルーチンによって設定される。Accept変数の現在の値がループカウンタの現在の値に等しくない場合（図１２のブロック１１２）は、最適化モジュール８２は、図１１の主シミュレーテッドアニーリングルーチンを現在の温度値ｔで実行することによってAccept変数の値を設定する（図１２のブロック１１４）。Accept変数の返された値が現在のループカウント値よりも大きい場合（図１２のブロック１１６）は、最適化モジュール８２は温度値を小さくする（図１２のブロック１１８）。いくつかの実施形態では、最適化モジュール８２は、一定の割合（たとえば１％）だけ現在の温度値を減少させる。Accept変数の返された値が現在のループカウント値以下の場合（図１２のブロック１１６）は、最適化モジュール８２は温度値を大きくする（図１２のブロック１１８）。いくつかの実施形態では、最適化モジュール８２は、一定の割合（たとえば１％）だけ現在の温度値を増加させる。
【００４８】
いくつかの実施形態では、最適化モジュール８２は、図１２のブロック１１０のFORループを抜けた後でシミュレーテッドアニーリング法を終了する。
【００４９】
他の実施形態では、最適化モジュール８２は、図１２のブロック１１０のFORループを抜けた後で、非適応型クーリングスケジュールを使用して図１１の主シミュレーテッドアニーリングルーチンの実行を継続する。このプロセスでは、温度パラメータｔの値は、指定された繰り返し数（たとえば１０００）に対して、図１２の適応型クーリングプロセスの終わりの時点における値から一定の割合（たとえば１％）だけ減少させられる。これらの実施形態のうちのいくつかでは、最適化モジュール８２は、この指定された繰り返し数の後（すなわち、該繰り返し回数だけ実行された後）、シミュレーテッドアニーリング法を終了する。これらの実施形態のうちの他の実施形態では、最適化モジュール８２は、この指定された繰り返し数の後（すなわち、該繰り返し回数だけ実行された後）、図１１の主シミュレーテッドアニーリングルーチンの実行を継続する。このプロセスでは、最適化モジュール８２は、繰り返す毎に温度パラメータｔの値を０に設定して、指定された繰り返し数（たとえば１０００）だけ図１１の主シミュレーテッドアニーリングルーチンを実行する。
【００５０】
４．確定された時空間レイアウト候補の各々にスコアをつける
上述したように、最適化モジュール８２は、確定された時空間レイアウト候補の各々についてそれぞれのスコアを計算する。いくつかの実施形態では、スコアは、各メディアオブジェクトのパラメータが、該メディアオブジェクトに割り当てられた時空間スロットの対応するパラメータにどれだけの近さで合致するかを測る個々のマッチングスコアの重み付けされた幾何平均（または相乗平均）である。これらの実施形態のうちのいくつかでは、各メディアオブジェクトに対するそれぞれのマッチングスコアは、種々の要素（または要因）から計算され、該要素の少なくともいくつかによって、メディアオブジェクト及びそれの現在のスロットに対する特定のパラメータ（たとえば、アスペクト比や持続時間）の値のそれぞれの比に関して該現在のスロットに対するメディアオブジェクトの近似度が測られる。
【００５１】
いくつかの実施形態では、グラフィックメディアオブジェクト（たとえば、写真やビデオ）に対するマッチングスコアは、ひずみファクター（distort factor。または歪み率）及びエリアファクターの関数である。歪みファクターは、メディアオブジェクトのアスペクト比がそれの現在のスロットのアスペクト比にどれだけの近似度で合致しているかを測るものである。エリアファクターは、メディアオブジェクトに割り当てられている表示領域の一部（または小部分）が、利用可能な表示領域の均等な分割部にどれだけの近似度で一致するかを測るものである。いくつかの実施形態では、マッチングスコアは、歪みファクターとエリアファクターの重み付き平均（加重平均）に対応（または一致）する。これらの実施形態のうちのいくつかでは、歪みファクターは、エリアファクターよりも大きく重み付けされている。
【００５２】
いくつかの実施形態では、時間ベースではないメディアオブジェクト（たとえば写真）の各々のマッチングスコアは、該オブジェクトの現在のスロットの持続時間が、該メディアオブジェクトについて指定された好ましい持続時間にどれだけの近さで合致しているかを測る持続時間ファクターをさらに含む。好ましい持続時間を、ユーザーが指定することができ、または、デフォルト（既定値）として指定することができる。持続時間ファクターは、典型的には、歪みファクターとエリアファクターの重み付き平均（加重平均）に含められる。
【００５３】
いくつかの実施形態では、時間ベースのメディアオブジェクト（たとえばビデオ）の各々のマッチングスコアは、該オブジェクトの持続時間が、該オブジェクトの現在のスロットの持続時間にどれだけの近さで合致しているかを測る持続時間ファクターをさらに含む。持続時間ファクターは、典型的には、歪みファクターとエリアファクターの重み付き平均（加重平均）に含められる。
【００５４】
いくつかの実施形態では、テキストベースのメディアオブジェクトのマッチングスコアは、ユーザーによってまたはデフォルト（既定値）として設定されることができる、高さ、幅、及び持続時間の好ましい値の関数である。これらの実施形態のいくつかでは、テキストベースのメディアオブジェクトのマッチングスコアは、幅ファクターと高さファクターと持続時間ファクターの積に一致（または相当）する。幅ファクターは、スロットの幅に対する好ましい幅の比と、該好ましい幅に対するスロットの幅の比との小さい方に一致（または相当する）。高さファクターは、スロットの高さに対する好ましい高さの比と、該好ましい高さに対するスロットの高さの比との小さい方に一致（または相当）する。持続時間ファクターは、スロットの持続時間が、テキストベースのメディアオブジェクトについて指定された好ましい持続時間にどれだけの近さで合致するかを測るものである。
【００５５】
いくつかの実施形態では、マッチングスコアは、指定された閾値寸法を下回る１つ以上の空間的寸法または時間的寸法（時間的長さ）を有するスロットに割り当てられたメディアオブジェクトのマッチングスコアを減少させる１つ以上のペナリゼーションファクター（penalization factor）をさらに含む。
【００５６】
VI．時空間レイアウト生成システムの例示的なアーキテクチャ
時空間レイアウト生成システム１０の実施形態を、任意の特定のハードウェア、ファームウェア、またはソフトウェア構成に限定されない、１つ以上の別個のモジュール（またはデータ処理コンポーネント）によって実施することができる。例示した実施形態では、それらのモジュールを、デジタル電子回路（たとえば、デジタル信号プロセッサ（DSP）などの特定用途向け集積回路）、または、コンピュータハードウェア、ファームウェア、デバイスドライバ、または、ソフトウェアを含む任意のコンピューティング環境またはデータ処理環境で実施することができる。いくつかの実施形態では、モジュールの機能は、単一のデータ処理コンポーネントに組み合わされる。いくつかの実施形態では、１つ以上のモジュールの各々のそれぞれの機能は、複数のデータ処理コンポーネントのそれぞれの組によって実行される。
【００５７】
いくつかの実施例では、時空間レイアウト生成システム１０の実施形態によって実行される方法を実施するための処理命令（たとえば、コンピュータソフトウェアなどのコンピュータ読み取り可能コード）、並びに、（生成された）データは、１つ以上のコンピュータ読み取り可能媒体に格納される。これらの命令及びデータを具現化する（たとえば記憶する）のに適した記憶装置には、たとえば、EPROM、EEPROM、及びフラッシュメモリ装置（デバイス）などの半導体記憶装置や、内部ハードディスク及びリムーバルハードディスクなどの磁気ディスク、光磁気ディスク、DVD-ROM/RAM、及びCD-ROM/RAMなどの不揮発性コンピュータ読み取り可能メモリのあらゆる形態が含まれる。
【００５８】
一般に、時空間レイアウト生成システム１０の実施形態を、コンピュータ（たとえば、ラップトップまたはノートブックコンピュータ、デスクトップコンピュータ、ワークステーションコンピュータ、及びサーバーコンピュータ）を含む様々な電子装置のうちの任意の１つで実施することができる。
【００５９】
図１３は、コンピュータ１４０で動作する１つ以上のソフトウェアモジュールによって実施される時空間レイアウト生成システム１０の１実施形態１３８を示す。コンピュータ１４０は、処理ユニット１４２、システムメモリ１４４、及び、処理ユニット１４２をコンピュータ１４０の種々のコンポーネントに結合するシステムバス１４６を備える。処理ユニット１４２は、典型的には、１つ以上のプロセッサを備えており、該プロセッサの各々を、市販されている種々のプロセッサのうちの任意の１つの形態とすることができる。システムメモリ１４４は、典型的には、コンピュータ１４０の始動ルーチンを含む基本入力／出力システム（BIOS）を格納している読み出し専用メモリ（ROM）、並びに、ランダムアクセスメモリ（RAM）を備える。システムバス１４６を、メモリバス、周辺バス（または周辺機器用バス）、またはローカルバスとすることができ、かつ、PCI、VESA、マイクロチャネル（Microchannel）、ISA、及びEISAを含む任意の種々のバスプロトコルと互換性があるものとすることができる。コンピュータ１４０はまた、永続型（または持続型）記憶装置１４８（たとえば、ハードディスク装置、フロッピーディスク装置、CDROM装置、磁気テープ装置、フラッシュメモリ装置、デジタルビデオディスク）を備え、該記憶装置１４８は、システムバス１４６に接続されて、データ、データ構造、及び、コンピュータ実行可能命令用の不揮発性または永続性の記憶を提供する１つ以上のコンピュータ読み取り可能媒体ディスクを含む。
【００６０】
ユーザーは、１つ以上の入力装置１５０（たとえば、キーボード、コンピュータマウス、マイクロホン、ジョイスティック、及びタッチパッド）を使用してコンピュータ３０と相互作用（たとえば、コマンドまたはデータの入力）をすることができる。情報を、表示モニター１５２においてユーザーに表示されるグラフィカルユーザーインターフェース（GUI）を介して表示（提示）することができ、該表示モニター１５２は、ディスプレイコントローラ１５４によって制御される。コンピュータ３０は典型的には、スピーカーやプリンタなどの周辺出力装置も備える。１つ以上の遠隔にあるコンピュータを、ネットワークインターフェースカード（NIC）１５６を介してコンピュータ１４０に接続することができる。
【００６１】
図１３に示すように、システムメモリ１４４はまた、時空間レイアウト生成システム１３８、GUIドライバ１５８、並びに、メディアオブジェクト１８と中間の処理データと出力データを含む他のデータ１６０を格納する。時空間レイアウト生成システム１３８は、GUIドライバ１５８及びユーザー入力１５０とインターフェース（または連携）して、確定された時空間レイアウト仕様の生成を制御する。いくつかの実施形態では、時空間レイアウト生成システム１３８は、さらに、確定された時空間レイアウト仕様２０を処理することによって、該仕様２０によって指定されたメディアオブジェクト１８の時空間レイアウトをレンダリングするように構成された少なくとも１つのビデオプレーヤー及びスクリプトインタプリタを備える。いくつかの実施形態では、時空間レイアウト生成システム１３８は、ユーザーに、確定された時空間レイアウト仕様２０を生成する処理を案内（または誘導）するグラフィカルユーザーインターフェースを生成する際に、GUIドライバ１５８、ユーザー入力１５０、相対的時空間レイアウト仕様１４、及び、他のデータ構造とインターフェース（または連携）する。時空間レイアウト生成システム１３８は、また、GUIドライバ１５８、確定された時空間レイアウト仕様２０、及び他のデータ構造とインターフェース（または連携）して、メディアオブジェクト１８の確定された時空間レイアウトの表示モニター１５２におけるユーザーへの提示（プレゼンテーション）を制御する。この提示（プレゼンテーション）をレンダリングするために使用される種々のメディアオブジェクト１８を永続型記憶装置１４８に局所的に格納することができ、及び／または、該オブジェクト１８を遠隔で格納してNIC１５６を介して該オブジェクト１８にアクセスすることができる。
【００６２】
VII．結論
本明細書で説明した実施形態は、メディアオブジェクトのコレクションを時空間レイアウトに編成することができ、この場合、各メディアオブジェクトは、空間的及び時間的に分割されたスケジューリングされたレンダリング（またはプレゼンテーション）空間中のそれぞれのスロットに割り当てられる。時空間レイアウトは、典型的には、プレゼンテーション空間の空間的及び時間的区分を時空間スロットへと誘導し、及び、それらのスロットへのメディアオブジェクトの割り当てを誘導する相対的時空間レイアウト仕様にしたがって生成される。いくつかの実施形態では、相対的時空間レイアウト仕様は、任意の特定のメディアオブジェクトとは無関係にマルチメディア関連の熟練技能者によって生成される。こうして、相対的時空間レイアウト仕様は、不慣れなユーザーが該ユーザーのメディアオブジェクトのコレクションの高品質の提示（プレゼンテーション）を生成するために利用できるようなやり方で、マルチメディア専門の技能者の技能及び美的センスを具現化することができる。本明細書で説明した実施形態は、コンシューマー向けの応用領域において大きな利点を提供し、それらの実施形態は、本質的に不統一なコンテンツであって、様々な異なるフォーマット及び解像度のコンテンツを有するメディアオブジェクトに対して、複雑なイベントを適切な形態で記録（または文書化）できるようにする。他の実施形態も特許請求の範囲に含まれる。
【特許請求の範囲】
【請求項１】
コンピュータによって実施される方法であって、
メディアオブジェクトタイプの相対的な空間位置及び時間的順序を記述する相対的時空間レイアウト仕様（１４）にしたがって、確定された時空間レイアウト仕様（２０）を自動的に生成するステップであって、前記確定された時空間レイアウト仕様（２０）は、ある時間にわたる表示領域（４６）におけるメディアオブジェクト（１８）のレイアウトを記述することからなる、ステップと、
前記確定された時空間レイアウト仕様（２０）を出力するステップ
を含み、
前記生成するステップは、前記メディアオブジェクト（１８）の各々について、それぞれのレンダリング期間にわたって前記表示領域（４６）内のそれぞれのウィンドウに対応するそれぞれの時空間スロットを決定するステップを含み、前記レンダリング期間において、前記メディアオブジェクト（１８）はレンダリングされるようにスケジューリングされることからなる、方法。
【請求項２】
前記決定するステップは、多次元最適化処理にしたがって、前記ウィンドウの空間パラメータの値及び前記レンダリング期間の時間パラメータの値を決定するステップを含む、請求項１の方法。
【請求項３】
前記決定するステップは、確定された時空間レイアウトの候補を特徴付ける目的関数を最適化する処理にしたがって、空間パラメータ値及び時間パラメータ値からなる異なるそれぞれの組によって画定された前記メディアオブジェクト（１８）の確定された時空間レイアウトの連続する候補を通じて、前記メディアオブジェクト（１８）の確定された時空間レイアウトの最初の候補から、前記確定された時空間レイアウト仕様（２０）に対応する最終の確定された時空間レイアウトまでの、前記メディアオブジェクト（１８）の確定された時空間レイアウトの一連の連続する候補を確定するステップを含む、請求項２の方法。
【請求項４】
前記決定するステップは、シミュレーテッドアニーリング最適化処理にしたがって、前記空間パラメータ及び前記時間パラメータの値を確定するステップを含む、請求項２の方法。
【請求項５】
前記確定するステップは、前記シミュレーテッドアニーリング処理の１つ以上の繰り返しの各々の間に受け入れられるランダムな動きの一部が連続的に下がる前記確定された時空間レイアウトの候補のうちの連続する候補の数に依存する適応型クーリングスケジュールで、前記シミュレーテッドアニーリング最適化処理を繰り返し実施するステップを含む、請求項４の方法。
【請求項６】
前記相対的時空間レイアウト仕様（１４）は、前記スロットのうちの指定されたスロットに対するメディアオブジェクト選択基準を含み、前記生成するステップは、割り当てられるメディアオブジェクトが前記メディアオブジェクト選択基準に合致するというユーザーの指示に基づいて、前記メディアオブジェクト（１８）のうちの１つを前記指定されたスロットに割り当てるステップを含む、請求項１の方法。
【請求項７】
メモリ（１４４）と、
前記メモリ（１４４）に結合された処理ユニット（１４２）
を備える装置であって、
前記処理ユニットは、
メディアオブジェクトタイプの相対的な空間位置及び時間的順序を記述する相対的時空間レイアウト仕様（１４）にしたがって、確定された時空間レイアウト仕様（２０）を自動的に生成するステップと、
前記確定された時空間レイアウト仕様（２０）を出力するステップ
を含む処理を実行するように動作可能であり、
前記確定された時空間レイアウト仕様（２０）は、ある時間にわたる表示領域（４６）内のメディアオブジェクト（１８）のレイアウトを記述し、
前記生成するステップは、前記メディアオブジェクト（１８）の各々について、それぞれのレンダリング期間にわたって前記表示領域（４６）内のそれぞれのウィンドウに対応するそれぞれの時空間スロットを決定するステップを含み、前記レンダリング期間において、前記メディアオブジェクト（１８）はレンダリングされるようにスケジューリングされることからなる、装置。
【請求項８】
前記決定するステップにおいて、前記処理ユニット（１４２）は、多次元最適化処理にしたがって、前記ウィンドウの空間パラメータの値及び前記レンダリング期間の時間パラメータの値を決定するステップを含む処理を実行するように動作可能である、請求項７の装置。
【請求項９】
前記決定するステップにおいて、前記処理ユニット（１４２）は、確定された時空間レイアウトの候補を特徴付ける目的関数を最適化する処理にしたがって、空間パラメータ値及び時間パラメータ値からなる異なるそれぞれの組によって画定された前記メディアオブジェクト（１８）の確定された時空間レイアウトの連続する候補を通じて、前記メディアオブジェクト（１８）の確定された時空間レイアウトの最初の候補から、前記確定された時空間レイアウト仕様（２０）に対応する最終の確定された時空間レイアウトまでの、前記メディアオブジェクト（１８）の確定された時空間レイアウトの一連の連続する候補を確定するステップを含む処理を実行するように動作可能である、請求項８の装置。
【請求項１０】
前記決定するステップにおいて、前記処理ユニットは、シミュレーテッドアニーリング最適化処理にしたがって、前記空間パラメータ及び時間パラメータの値を確定するステップを含む処理を実行するように動作可能である、請求項８の装置。
【請求項１１】
メディアオブジェクトタイプの相対的な空間位置及び時間的順序を記述する相対的時空間レイアウト仕様（１４）にしたがって、確定された時空間レイアウト仕様（２０）を自動的に生成するステップであって、前記確定された時空間レイアウト仕様（２０）は、ある時間にわたって表示領域（４６）におけるメディアオブジェクト（１８）のレイアウトを記述することからなる、ステップと、
前記確定された時空間レイアウト仕様（２０）を出力するステップ
を含む処理をコンピュータ（１４０）に実施させるコンピュータ読み取り可能命令を格納するコンピュータ読み取り可能媒体（１４４、１４８）であって、
前記生成するステップは、前記メディアオブジェクト（１８）の各々について、それぞれのレンダリング期間にわたって前記表示領域（４６）内のそれぞれのウィンドウに対応するそれぞれの時空間スロットを決定するステップを含み、前記レンダリング期間において、前記メディアオブジェクト（１８）はレンダリングされるようにスケジューリングされることからなる、コンピュータ読み取り可能媒体。
【請求項１２】
前記決定するステップにおいて、前記コンピュータ読み取り可能命令は、前記コンピュータ（１４０）に、多次元最適化処理にしたがって、前記ウィンドウの空間パラメータの値及び前記レンダリング期間の時間パラメータの値を決定するステップを含む処理を実施させることからなる、請求項１１のコンピュータ読み取り可能媒体。
【請求項１３】
前記決定するステップにおいて、前記コンピュータ読み取り可能命令は、前記コンピュータ（１４０）に、確定された時空間レイアウトの候補を特徴付ける目的関数を最適化する処理にしたがって、空間パラメータ値及び時間パラメータ値からなる異なるそれぞれの組によって画定された前記メディアオブジェクト（１８）の確定された時空間レイアウトの連続する候補を通じて、前記メディアオブジェクト（１８）の確定された時空間レイアウトの最初の候補から、前記確定された時空間レイアウト仕様（２０）に対応する最終の確定された時空間レイアウトまでの、前記メディアオブジェクト（１８）の確定された時空間レイアウトの一連の連続する候補を確定するステップを含む処理を実施させる、請求項１２のコンピュータ読み取り可能媒体。
【請求項１４】
前記決定するステップにおいて、前記コンピュータ読み取り可能命令は、前記コンピュータ（１４０）に、シミュレーテッドアニーリング最適化処理にしたがって、前記空間パラメータ及び前記時間パラメータの値を確定するステップを含む処理を実施させる、請求項１３のコンピュータ読み取り可能媒体。
【請求項１５】
前記確定するステップにおいて、前記コンピュータ読み取り可能命令は、前記コンピュータ（１４０）に、前記シミュレーテッドアニーリング処理の１つ以上の繰り返しの各々の間に、目的関数スコアが連続的に向上する前記確定された時空間レイアウトの候補のうちの連続する候補の数に依存する適応型クーリングスケジュールで、前記シミュレーテッドアニーリング最適化処理を繰り返し実施するステップを含む処理を実施させる、請求項１４のコンピュータ読み取り可能媒体。
【請求項１】
コンピュータによって実施される方法であって、
メディアオブジェクトタイプの相対的な空間位置及び時間的順序を記述する相対的時空間レイアウト仕様（１４）にしたがって、確定された時空間レイアウト仕様（２０）を自動的に生成するステップであって、前記確定された時空間レイアウト仕様（２０）は、ある時間にわたる表示領域（４６）におけるメディアオブジェクト（１８）のレイアウトを記述することからなる、ステップと、
前記確定された時空間レイアウト仕様（２０）を出力するステップ
を含み、
前記生成するステップは、前記メディアオブジェクト（１８）の各々について、それぞれのレンダリング期間にわたって前記表示領域（４６）内のそれぞれのウィンドウに対応するそれぞれの時空間スロットを決定するステップを含み、前記レンダリング期間において、前記メディアオブジェクト（１８）はレンダリングされるようにスケジューリングされることからなる、方法。
【請求項２】
前記決定するステップは、多次元最適化処理にしたがって、前記ウィンドウの空間パラメータの値及び前記レンダリング期間の時間パラメータの値を決定するステップを含む、請求項１の方法。
【請求項３】
前記決定するステップは、確定された時空間レイアウトの候補を特徴付ける目的関数を最適化する処理にしたがって、空間パラメータ値及び時間パラメータ値からなる異なるそれぞれの組によって画定された前記メディアオブジェクト（１８）の確定された時空間レイアウトの連続する候補を通じて、前記メディアオブジェクト（１８）の確定された時空間レイアウトの最初の候補から、前記確定された時空間レイアウト仕様（２０）に対応する最終の確定された時空間レイアウトまでの、前記メディアオブジェクト（１８）の確定された時空間レイアウトの一連の連続する候補を確定するステップを含む、請求項２の方法。
【請求項４】
前記決定するステップは、シミュレーテッドアニーリング最適化処理にしたがって、前記空間パラメータ及び前記時間パラメータの値を確定するステップを含む、請求項２の方法。
【請求項５】
前記確定するステップは、前記シミュレーテッドアニーリング処理の１つ以上の繰り返しの各々の間に受け入れられるランダムな動きの一部が連続的に下がる前記確定された時空間レイアウトの候補のうちの連続する候補の数に依存する適応型クーリングスケジュールで、前記シミュレーテッドアニーリング最適化処理を繰り返し実施するステップを含む、請求項４の方法。
【請求項６】
前記相対的時空間レイアウト仕様（１４）は、前記スロットのうちの指定されたスロットに対するメディアオブジェクト選択基準を含み、前記生成するステップは、割り当てられるメディアオブジェクトが前記メディアオブジェクト選択基準に合致するというユーザーの指示に基づいて、前記メディアオブジェクト（１８）のうちの１つを前記指定されたスロットに割り当てるステップを含む、請求項１の方法。
【請求項７】
メモリ（１４４）と、
前記メモリ（１４４）に結合された処理ユニット（１４２）
を備える装置であって、
前記処理ユニットは、
メディアオブジェクトタイプの相対的な空間位置及び時間的順序を記述する相対的時空間レイアウト仕様（１４）にしたがって、確定された時空間レイアウト仕様（２０）を自動的に生成するステップと、
前記確定された時空間レイアウト仕様（２０）を出力するステップ
を含む処理を実行するように動作可能であり、
前記確定された時空間レイアウト仕様（２０）は、ある時間にわたる表示領域（４６）内のメディアオブジェクト（１８）のレイアウトを記述し、
前記生成するステップは、前記メディアオブジェクト（１８）の各々について、それぞれのレンダリング期間にわたって前記表示領域（４６）内のそれぞれのウィンドウに対応するそれぞれの時空間スロットを決定するステップを含み、前記レンダリング期間において、前記メディアオブジェクト（１８）はレンダリングされるようにスケジューリングされることからなる、装置。
【請求項８】
前記決定するステップにおいて、前記処理ユニット（１４２）は、多次元最適化処理にしたがって、前記ウィンドウの空間パラメータの値及び前記レンダリング期間の時間パラメータの値を決定するステップを含む処理を実行するように動作可能である、請求項７の装置。
【請求項９】
前記決定するステップにおいて、前記処理ユニット（１４２）は、確定された時空間レイアウトの候補を特徴付ける目的関数を最適化する処理にしたがって、空間パラメータ値及び時間パラメータ値からなる異なるそれぞれの組によって画定された前記メディアオブジェクト（１８）の確定された時空間レイアウトの連続する候補を通じて、前記メディアオブジェクト（１８）の確定された時空間レイアウトの最初の候補から、前記確定された時空間レイアウト仕様（２０）に対応する最終の確定された時空間レイアウトまでの、前記メディアオブジェクト（１８）の確定された時空間レイアウトの一連の連続する候補を確定するステップを含む処理を実行するように動作可能である、請求項８の装置。
【請求項１０】
前記決定するステップにおいて、前記処理ユニットは、シミュレーテッドアニーリング最適化処理にしたがって、前記空間パラメータ及び時間パラメータの値を確定するステップを含む処理を実行するように動作可能である、請求項８の装置。
【請求項１１】
メディアオブジェクトタイプの相対的な空間位置及び時間的順序を記述する相対的時空間レイアウト仕様（１４）にしたがって、確定された時空間レイアウト仕様（２０）を自動的に生成するステップであって、前記確定された時空間レイアウト仕様（２０）は、ある時間にわたって表示領域（４６）におけるメディアオブジェクト（１８）のレイアウトを記述することからなる、ステップと、
前記確定された時空間レイアウト仕様（２０）を出力するステップ
を含む処理をコンピュータ（１４０）に実施させるコンピュータ読み取り可能命令を格納するコンピュータ読み取り可能媒体（１４４、１４８）であって、
前記生成するステップは、前記メディアオブジェクト（１８）の各々について、それぞれのレンダリング期間にわたって前記表示領域（４６）内のそれぞれのウィンドウに対応するそれぞれの時空間スロットを決定するステップを含み、前記レンダリング期間において、前記メディアオブジェクト（１８）はレンダリングされるようにスケジューリングされることからなる、コンピュータ読み取り可能媒体。
【請求項１２】
前記決定するステップにおいて、前記コンピュータ読み取り可能命令は、前記コンピュータ（１４０）に、多次元最適化処理にしたがって、前記ウィンドウの空間パラメータの値及び前記レンダリング期間の時間パラメータの値を決定するステップを含む処理を実施させることからなる、請求項１１のコンピュータ読み取り可能媒体。
【請求項１３】
前記決定するステップにおいて、前記コンピュータ読み取り可能命令は、前記コンピュータ（１４０）に、確定された時空間レイアウトの候補を特徴付ける目的関数を最適化する処理にしたがって、空間パラメータ値及び時間パラメータ値からなる異なるそれぞれの組によって画定された前記メディアオブジェクト（１８）の確定された時空間レイアウトの連続する候補を通じて、前記メディアオブジェクト（１８）の確定された時空間レイアウトの最初の候補から、前記確定された時空間レイアウト仕様（２０）に対応する最終の確定された時空間レイアウトまでの、前記メディアオブジェクト（１８）の確定された時空間レイアウトの一連の連続する候補を確定するステップを含む処理を実施させる、請求項１２のコンピュータ読み取り可能媒体。
【請求項１４】
前記決定するステップにおいて、前記コンピュータ読み取り可能命令は、前記コンピュータ（１４０）に、シミュレーテッドアニーリング最適化処理にしたがって、前記空間パラメータ及び前記時間パラメータの値を確定するステップを含む処理を実施させる、請求項１３のコンピュータ読み取り可能媒体。
【請求項１５】
前記確定するステップにおいて、前記コンピュータ読み取り可能命令は、前記コンピュータ（１４０）に、前記シミュレーテッドアニーリング処理の１つ以上の繰り返しの各々の間に、目的関数スコアが連続的に向上する前記確定された時空間レイアウトの候補のうちの連続する候補の数に依存する適応型クーリングスケジュールで、前記シミュレーテッドアニーリング最適化処理を繰り返し実施するステップを含む処理を実施させる、請求項１４のコンピュータ読み取り可能媒体。
【図１】
【図２】
【図３】
【図４】
【図５Ａ】
【図５Ｂ】
【図６】
【図７】
【図８】
【図９Ａ】
【図９Ｂ】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５Ａ】
【図５Ｂ】
【図６】
【図７】
【図８】
【図９Ａ】
【図９Ｂ】
【図１０】
【図１１】
【図１２】
【図１３】
【公表番号】特表２０１１−５２４０３５（Ｐ２０１１−５２４０３５Ａ）
【公表日】平成２３年８月２５日（２０１１．８．２５）
【国際特許分類】
【出願番号】特願２０１１−５０８４５１（Ｐ２０１１−５０８４５１）
【出願日】平成２０年５月６日（２００８．５．６）
【国際出願番号】ＰＣＴ／ＵＳ２００８／００５８４２
【国際公開番号】ＷＯ２００９／１３６８８８
【国際公開日】平成２１年１１月１２日（２００９．１１．１２）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（５１１０７６４２４）ヒューレット−パッカード デベロップメント カンパニー エル．ピー． (155)
【氏名又は名称原語表記】Ｈｅｗｌｅｔｔ‐Ｐａｃｋａｒｄ Ｄｅｖｅｌｏｐｍｅｎｔ Ｃｏｍｐａｎｙ， Ｌ．Ｐ．
【Ｆターム（参考）】
【公表日】平成２３年８月２５日（２０１１．８．２５）
【国際特許分類】
【出願日】平成２０年５月６日（２００８．５．６）
【国際出願番号】ＰＣＴ／ＵＳ２００８／００５８４２
【国際公開番号】ＷＯ２００９／１３６８８８
【国際公開日】平成２１年１１月１２日（２００９．１１．１２）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（５１１０７６４２４）ヒューレット−パッカード デベロップメント カンパニー エル．ピー． (155)
【氏名又は名称原語表記】Ｈｅｗｌｅｔｔ‐Ｐａｃｋａｒｄ Ｄｅｖｅｌｏｐｍｅｎｔ Ｃｏｍｐａｎｙ， Ｌ．Ｐ．
【Ｆターム（参考）】
[ Back to top ]