(57)【要約】  一面において、ページ（１０２）上に配置されるグラフィック・オブジェクト（１００）のそれぞれの目標レンダリング・サイズが、グラフィック・オブジェクト（１００）に割り当てられた対応する公称サイズに基づいて確かめられる。ページ（１０２）上のグラフィック・オブジェクト（１００）の異なる候補レイアウトが構築される。候補レイアウトにおけるグラフィック・オブジェクト（１００）の実際のレンダリング・サイズの１つ１つを、それらの目標レンダリング・サイズと比較することに基づいて、グラフィック・オブジェクト（１００）の最終レイアウト（９８）が決定される。他の面において、グラフィック・オブジェクト（１００）へのそれぞれの公称サイズの２つ以上の異なる候補割当て（１４２、１４４）が決定される。２つ以上の候補割当て（１４２、１４４）のそれぞれに基づいて、ページ（１０２）上のグラフィック・オブジェクト（１００）の１つまたは複数の候補レイアウト（１２０）から成る対応する組が構築される。【選択図】図７
2010532042.tif 000002
【特許請求の範囲】
【請求項１】
ページ（１０２）上にグラフィック・オブジェクト（１００）を配置する方法であって、
前記グラフィック・オブジェクト（１００）ごとに、前記グラフィック・オブジェクト（１００）に割り当てられた対応する公称サイズに基づいて、前記ページ（１０２）上の前記グラフィック・オブジェクト（１００）の対応する目標レンダリング・サイズを確かめるステップと、
前記ページ上の前記グラフィック・オブジェクト１つ１つの対応する異なる候補レイアウトを構築するステップであって、前記候補レイアウトごとに、前記ページ（１０２）上の前記グラフィック・オブジェクト（１００）の対応する前記実際のレンダリング・サイズを計算するステップを含む構築するステップと、
実際のレンダリング・サイズの１つ１つを、前記目標レンダリング・サイズの対応する１つ１つと比較することに少なくとも一部、基づいて、前記ページ（１０２）上の前記グラフィック・オブジェクト（１００）の最終レイアウト（９８）を決定するステップと、
グラフィック・オブジェクト（１００）の前記最終レイアウト（９８）を出力するステップと
を含む方法。
【請求項２】
前記確かめるステップは、
前記目標レンダリング・サイズのそれぞれを、前記グラフィック・オブジェクト（１００）を配置するために割り振られた前記ページ（１０２）の総面積の一部分（fraction）にセットし、その割合を、すべてのグラフィック・オブジェクト（１００）に割り当てられたそれぞれの公称サイズの合計に対する対応する前記公称サイズの比率に等しくしているステップ
を含む
請求項１に記載の方法。
【請求項３】
前記決定するステップは、
前記候補レイアウト（１２０）における前記グラフィック・オブジェクト（１００）の実際のレンダリング・サイズと、前記対応する目標レンダリング・サイズが一致する度合いに基づいて、前記候補レイアウト（１２０）ごとに、対応するレイアウト・スコアを計算するステップ
を含み、
前記計算するステップは、
前記候補レイアウト（１２０）ごとに、前記対応する目標レンダリング・サイズに対する前記実際のレンダリング・サイズの比率に基づいて、前記候補レイアウト（１２０）における前記グラフィック・オブジェクト（１００）のそれぞれに対して、対応するグラフィック・オブジェクト・スコアを計算するステップと、
前記対応するグラフィック・オブジェクト・スコアから、前記対応するレイアウト・スコアを計算するステップと
を含む
請求項１に記載の方法。
【請求項４】
前記決定するステップは、
一連の逐次レイアウトを繰り返し構築するステップ
を含み、
前記一連の逐次レイアウトのそれぞれは、
前記一連の逐次レイアウト中の直前のレイアウトに追加される前記グラフィック・オブジェクトの１つ（５２４、５２８、５３２）
を含み、
前記直前の逐次レイアウトにおける前記追加グラフィック・オブジェクト（５２４、５２８、５３２）のそれぞれ異なる相対的位置で定められた現在候補レイアウトに対して算出される、前記比較の１つ１つから計算されるそれぞれのスコアに基づいて、繰返しごとに、前記逐次レイアウトの現在の１つが、前記直前の逐次レイアウトから構築される
請求項１に記載の方法。
【請求項５】
ページ（１０２）上にグラフィック・オブジェクト（１００）を配置する方法であって、
前記グラフィック・オブジェクト（１００）への対応する公称サイズの２つ以上のそれぞれ互いに異なる候補割当て（１４２、１４４）を決定するステップと、
前記ページ（１０２）上の前記グラフィック・オブジェクト（１００）の１つまたは複数の候補レイアウト（１２０）から成る対応する組を、前記２つ以上の候補割当て（１４２、１４４）のそれぞれに基づいて構築するステップと、
前記１つまたは複数の候補レイアウト（１２０）を出力するステップと
を含む方法。
【請求項６】
前記決定するステップは、
前記グラフィック・オブジェクト（１３６）のそれぞれを、一組の所定のグラフィック・オブジェクト型クラスから選択された対応するクラスに分類するステップと、
一連のグラフィック・オブジェクト（１３６）を、前記グラフィック・オブジェクト（１３６）にそれぞれ割り当てられたクラスに基づいて生成するステップと、
前記一連のグラフィック・オブジェクトから、１つまたは複数の候補割当て（１４２、１４４）を作成するステップと
を含む
請求項５に記載の方法。
【請求項７】
前記決定するステップは、前記候補割当て（１４２、１４４）の対応する１つ１つに対して、
１つまたは複数の公称サイズから成る第１の組から選択された対応する公称サイズを、前記グラフィック・オブジェクト（１３６）のランダムな数のランダム選択物に割り当てるステップと、
それぞれが前記第１の組の公称サイズの最小のものよりも小さい１つまたは複数の公称サイズから成る第２の組から選択された対応する公称サイズを、前記グラフィック・オブジェクト（１３６）の他の１つ１つに割り当てるステップと
を含む
請求項５に記載の方法。
【請求項８】
前記決定するステップは、
前記候補割当て（１４２、１４４）の１つ１つを互いに比較するステップと、
前記比較するステップに基づいて、互いに異なるものと判定された前記候補割当て（１４２、１４４）の１つまたは複数を選択するステップと
を含み、
前記出力するステップは、
前記候補レイアウトの選択されなかったもの１つ１つの対応する仕様書（Specification）を出力するのを控え（omit）ながら、前記候補割当て（１４２、１４４）の選択されたもの１つ１つに対応する前記候補レイアウト１つ１つの対応する仕様書を出力するステップ
を含む
請求項５に記載の方法。
【請求項９】
ページ（１０２）上にグラフィック・オブジェクト（１００）を配置するシステムであって、
前記グラフィック・オブジェクト（１００）ごとに、前記グラフィック・オブジェクト（１００）に割り当てられた対応する公称サイズに基づいて、前記ページ（１０２）上の前記グラフィック・オブジェクト（１００）の対応する目標レンダリング・サイズを確かめ、
前記ページ（１０２）上の前記グラフィック・オブジェクト（１００）１つ１つの対応する異なる候補レイアウトを構築し、その構築することは、前記候補レイアウトごとに、前記ページ（１０２）上の前記グラフィック・オブジェクト（１００）の対応する実際のレンダリング・サイズを計算することを含み、
前記実際のレンダリング・サイズの１つ１つを、前記目標レンダリング・サイズの対応する１つ１つと比較することに少なくとも一部、基づいて、前記ページ（１０２）上の前記グラフィック・オブジェクト（１００）の最終レイアウト（９８）を決定し、
グラフィック・オブジェクト（１００）の前記最終レイアウト（９８）を出力する
ように作動するページ・レイアウト作成モジュール
を備えるシステム。
【請求項１０】
ページ（１０２）上にグラフィック・オブジェクト（１００）を配置するシステムであって、
前記グラフィック・オブジェクト（１００）への対応する公称サイズの２つ以上のそれぞれ互いに異なる候補割当て（１４２、１４４）を決定し、
前記ページ（１０２）上の前記グラフィック・オブジェクト（１００）の１つまたは複数の候補レイアウト（１２０）から成る対応する組を、前記２つ以上の候補割当て（１４２、１４４）のそれぞれに基づいて構築し、
前記１つまたは複数の候補レイアウト（１２０）を出力する
ように作動するページ・レイアウト作成モジュール
を備えるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の引用）
本出願は、それぞれ参照によって本明細書中に組み入れられている以下の同時係属中の出願にも関係する。
・２００３年９月３０日に出願された米国特許出願第１０／６７５，７２４号。
・２００３年９月３０日に出願された米国特許出願第１０／６７５，８２３号。
・２００５年５月１２日に出願された米国特許出願第１１／１２７，３２６号。
・２００５年５月１２日に出願された米国特許出願第１１／１２８，５４３号。
・２００４年４月２３日に出願された米国特許出願第１０／８３１，４３６号。
・２００５年４月１５日に出願された米国特許出願第１１／１２６，６３７号。
・２００５年６月１０日に出願された米国特許出願第１１／１５１，１６７号。
・２００５年３月１日に出願された米国特許出願第１１／０６９，５１２号。
・２００４年１１月１２日に出願された米国特許出願第１０／９８７，２８８号。
・２００６年３月１日に出願された米国特許出願第１１／３６４，９３３号。
【背景技術】
【０００２】
個人や団体は、静止画、テキスト、グラフィクス、動画、フルモーション・ビデオ画像を含め、デジタル画像コンテンツの大コレクションをすばやく蓄積しようとする。
このデジタル画像コンテンツは、個別に表示されるか、あるいは、文書、カタログ、プレゼンテーション、スチール写真、コマーシャル・ビデオ、ホーム・ビデオ、および、１つまたは複数の関連するデジタル・コンテンツ・ファイルを記述したメタデータを含め、多種多様な異なる形式で組み合わされることがある。
これらのコレクションの数と多様性が増すにつれて、個人や団体は、自分のコレクションの中でデジタル・コンテンツを編成して、表示するシステムおよび方法をますます必要とするようになる。
このような要望を満たすために、デジタル画像コンテンツを編成し、表示する異なる様々なシステムおよび方法が提案されてきた。
【０００３】
例えば、ユーザーがデジタル・フォトアルバムを手動で作成できるようにする手動デジタル画像アルバム作成システムがいくつかある。
これらのアルバム作成システムは一般に、画像コレクションを編成して、１つまたは複数のページ上にこれらの画像をレイアウトするツールを提供する。
デジタル・フォトアルバムを手動で作成する普通タイプのツールの中には、アルバムのページに載せる上記画像コレクションの中から一部の画像を選択するツール、このページ上の画像を手動で配置し直すグラフィカル・ユーザー・インターフェース、および、アルバムに載せる画像の様々な特性（例えば、サイズや向き）を変更する基本画像編集ツールがある。
ユーザーは通常、完全手動のデジタル画像アルバム作成システムを用いてデジタル・フォトアルバムを作成するプロセスが面倒で、時間がかかることがわかる。
【０００４】
いくつかの自動デジタル画像アルバム作成システムにより、ユーザーは、デジタル画像に関連するメタデータで指定された日付および時間に従って、デジタル画像を編成して、アルバム・ページを作成することができる。
また、これらの画像アルバム作成システムにより、通常、ユーザーは、デジタル・フォトアルバム・ページに載せる画像にアノテーションを付与することもできる。
いくつかの自動デジタル画像アルバム作成システムは、デジタル・フォトアルバムを作成するためにユーザーが選択できるあらかじめ定められた様々なレイアウト・テンプレートを提供する。
これらの自動デジタル画像アルバム作成システムでは、ユーザーが上記画像コレクションからの画像を、選択レイアウト・テンプレート上のあらかじめ定められた様々な画像位置に割り当てると、このシステムは、選択レイアウト・テンプレート上のあらかじめ定められた様々な画像位置に指定されたパラメータに従って、画像のサイズ、配置、回転、フレーミングを自動的に調整する。
【０００５】
いくつかのデジタル画像アルバム作成システムは、ユーザーからの最小限の入力でアルバム・ページを自動的に作成するように設計されている。
このようなシステムの１つには、ページ作成モジュール（page creator module）と画像配置モジュールが含まれる。
ページ作成モジュールは、第１の遺伝的進化（genetic evolution）アルゴリズムに基づいて、コレクション中の画像をアルバム・ページに割り当てる。
画像配置モジュールは、第２の遺伝的進化アルゴリズムに基づいて所与のページに割り当てられる画像用のページ・レイアウトの遺伝的構造（genetic structure）を作り出す。
これらの遺伝的構造は、所与のページ上に配置される画像の位置、縮尺、回転の向きを定める。
レイアウト評価モジュールは、上記レイアウトを、いくつかの他の好みおよびページ要件と比較する。
適切なレイアウトが作成されているときには、その最終アルバム・レイアウトが表示され、印刷され、あるいは他の方法で後で転送され得る。
【０００６】
他の自動デジタル画像アルバム作成システムは、イベントで編成され、かつ一組のアルバム作成パラメータに基づいて自動的にレイアウトされるアルバムを、ユーザーに表示するページ・レイアウト・モジュールを含む。
ページ上にレイアウトされる画像の数は、パラメトリック法によるか、あるいは、これらの画像の属性の解析により、決定される。
このパラメトリック法は、ページを一組のグリッド・スクエアに分けて、これらのグリッド・スクエア上に画像をレイアウトする一組のルールに基づいて、このページ上にレイアウトされる画像の数を決定する。
このシステムでは、ページ上の画像の実際のレイアウトはまた、これらの画像の属性（例えば、画像のサイズ）を、一組のテンプレートに合わせることにより、決定されうる。
【０００７】
他の自動デジタル画像アルバム作成システムは、それぞれの画像が、同一ページ上にある他の画像に力を加えると仮定する力モデル（force model）に基づいて、ページ上に画像を自動的に位置づける。
この力は、画像を隔てる距離の関数である。
このシステムは、それぞれの画像を、その画像に作用する正味力（net force）の方向に、その正味力の関数である距離だけ移動させることで、このページ上の画像の初期レイアウトを変更する。
【０００８】
必要とされるものは、ページ上にグラフィック・オブジェクトを自動的に配置するシステムおよび方法であって、それらは、それぞれのレイアウトにおいて１つまたは複数のグラフィック・オブジェクトの相対的サイズに対する明示的な好みにより誘導または制御され得るものである。
【発明の概要】
【課題を解決するための手段】
【０００９】
一面において、本発明は、ページ上にグラフィック・オブジェクトを配置する方法を特徴づける。
この方法により、グラフィック・オブジェクトごとに、グラフィック・オブジェクトに割り当てられた対応する公称サイズに基づいて、ページ上のグラフィック・オブジェクトの対応する目標レンダリング・サイズが確かめられる。
ページ上のグラフィック・オブジェクト１つ１つの対応する異なる候補レイアウトが構築される。
このプロセスにおいて、候補レイアウトごとに、ページ上のグラフィック・オブジェクトのそれぞれの実際のレンダリング・サイズが計算される。
実際のレンダリング・サイズの１つ１つを、目標レンダリング・サイズの対応する１つ１つと比較することに少なくとも一部、基づいて、ページ上のグラフィック・オブジェクトの最終レイアウトが決定される。
グラフィック・オブジェクトの最終レイアウトが出力される。
【００１０】
一面において、本発明は、ページ上にグラフィック・オブジェクトを配置する方法を特徴づける。
この方法により、これらのグラフィック・オブジェクトへの対応する公称サイズの２つ以上の候補割当てが決定される。
これらの候補割当てはそれぞれ互いに異なっている。
ページ上のグラフィック・オブジェクトの１つまたは複数の候補レイアウトから成る対応する組が、２つ以上の候補割当てのそれぞれに基づいて構築される。
１つまたは複数の候補レイアウトが出力される。
【００１１】
本発明の他の特徴および利点は、図面および特許請求の範囲を含め、以下の説明から明らかになろう。
【図面の簡単な説明】
【００１２】
【図１】ページ上のグラフィック・オブジェクトのレイアウトの略図である。
【図２】構成単一要素グラフィック・オブジェクトから形成されている多要素グラフィック・オブジェクトが破線楕円で特定されている、図１に示されるグラフィック・オブジェクトのレイアウトの略図である。
【図３Ａ】６つの構成グラフィック・オブジェクトから形成された多要素グラフィック・オブジェクトの表示の略図である。
【図３Ｂ】６つの構成グラフィック・オブジェクトから形成された多要素グラフィック・オブジェクトの表示の略図である。
【図３Ｃ】６つの構成グラフィック・オブジェクトから形成された多要素グラフィック・オブジェクトの表示の略図である。
【図３Ｄ】６つの構成グラフィック・オブジェクトから形成された多要素グラフィック・オブジェクトの表示の略図である。
【図４】１つまたは複数のページ上にグラフィック・オブジェクトを配置するシステムの一実施形態のブロック図である。
【図５】図４のシステムで実施されるグラフィック・オブジェクト配置方法の一実施形態の流れ図である。
【図６】ページ上に配置されるグラフィック・オブジェクトに、それぞれの公称サイズ、およびそれぞれの縦横比（aspect ratio）を割り当てる動作を含むページ・レジスタの一実施形態の略図である。
【図７】ページ上にグラフィック・オブジェクトを配置する方法の一実施形態の流れ図である。
【図８】ページ上のグラフィック・オブジェクトの異なるレイアウトをインタラクティブに閲覧するユーザー・インターフェースの略図である。
【図９】グラフィック・オブジェクトの選択候補配置をメイン・ウィンドウに表示し、また、グラフィック・オブジェクトの代替配置をサイド・ウィンドウに表示するユーザー・インターフェースの略図である。
【図１０】グラフィック・オブジェクトの代替配置のうちユーザーで選択された１つをメイン・ウィンドウに表示する図８のユーザー・インターフェースの略図である。
【図１１】グラフィック・オブジェクトへのそれぞれの公称サイズの１つまたは複数の割当てに基づいて、ページ上にグラフィック・オブジェクトの１つまたは複数の配置を作成する方法の一実施形態の流れ図である。
【図１２】ページ上にレイアウトされるグラフィック・オブジェクトへのそれぞれの公称サイズの候補割当てを作成する方法の一実施形態の流れ図である。
【図１３Ａ】一連のグラフィック・オブジェクトの略図である。
【図１３Ｂ】図１３Ａに示されるグラフィック・オブジェクトが一組の所定のオブジェクト型クラスのそれぞれに分布する略図である。
【図１３Ｃ】図１３Ｂに示されるグラフィック・オブジェクトの分布に基づいて、一連のグラフィック・オブジェクトを作成する方法の一実施形態の略図である。
【図１３Ｄ】図１３Ｃに示される方法により、図１３Ａに示されるグラフィック・オブジェクトから作成された一連のグラフィック・オブジェクトの略図である。
【図１４Ａ】図１３Ｄに示される順序にてグラフィック・オブジェクトへのそれぞれの公称サイズの候補割当ての実施形態の略図である。
【図１４Ｂ】図１３Ｄに示される順序にてグラフィック・オブジェクトへのそれぞれの公称サイズの候補割当ての実施形態の略図である。
【図１５Ａ】図１３Ｄに示される順序にてグラフィック・オブジェクトへのそれぞれの公称サイズの候補割当ての実施形態の略図である。
【図１５Ｂ】図１３Ｄに示される順序にてグラフィック・オブジェクトへのそれぞれの公称サイズの候補割当ての実施形態の略図である。
【図１６Ａ】図１３Ｄに示される順序にてグラフィック・オブジェクトへのそれぞれの公称サイズの候補割当ての実施形態の略図である。
【図１６Ｂ】図１３Ｄに示される順序にてグラフィック・オブジェクトへのそれぞれの公称サイズの候補割当ての実施形態の略図である。
【図１７】グラフィック・オブジェクトへのそれぞれの公称サイズの候補割当てを作成する方法の一実施形態の流れ図である。
【図１８】グラフィック・オブジェクトへのそれぞれの公称サイズの割当てを比較する方法の一実施形態の流れ図である。
【図１９Ａ】図１３Ｂに示されるグラフィック・オブジェクトに割当てられた公称サイズが、この組の所定のオブジェクト型クラスのそれぞれに分布する略図である。
【図１９Ｂ】それぞれのオブジェクト型クラス中の公称サイズが大きさの順に分類されている、図１９Ａに示されるグラフィック・オブジェクトに割り当てられた公称サイズの分布の略図である。
【図２０】１つまたは複数のページ上にグラフィック・オブジェクトを配置するシステムの一実施形態のブロック図である。
【図２１】複数のページ上にグラフィック・オブジェクトを配置する方法の一実施形態の流れ図である。
【図２２】ページの区画と、このページ区画に対応する階層木構造の略図である。
【図２３Ａ】ページ上のグラフィック・オブジェクトのレイアウトを評価する方法の実施形態の流れ図である。
【図２３Ｂ】ページ上のグラフィック・オブジェクトのレイアウトを評価する方法の実施形態の流れ図である。
【図２４】木構造を通るパスの実現可能性を判定する方法の一実施形態の流れ図である。
【図２５】ページ上のグラフィック・オブジェクトの相対レイアウトを通る一組のパスを生成する方法の一実施形態の流れ図である。
【図２６Ａ】典型的な候補相対レイアウトに関して、図２５の方法により生成されるパスの組を示す。
【図２６Ｂ】典型的な候補相対レイアウトに関して、図２５の方法により生成されるパスの組を示す。
【図２６Ｃ】典型的な候補相対レイアウトに関して、図２５の方法により生成されるパスの組を示す。
【図２６Ｄ】典型的な候補相対レイアウトに関して、図２５の方法により生成されるパスの組を示す。
【図２６Ｅ】典型的な候補相対レイアウトに関して、図２５の方法により生成されるパスの組を示す。
【図２６Ｆ】典型的な候補相対レイアウトに関して、図２５の方法により生成されるパスの組を示す。
【図２６Ｇ】典型的な候補相対レイアウトに関して、図２５の方法により生成されるパスの組を示す。
【図２６Ｈ】典型的な候補相対レイアウトに関して、図２５の方法により生成されるパスの組を示す。
【図２６Ｉ】典型的な候補相対レイアウトに関して、図２５の方法により生成されるパスの組を示す。
【図２６Ｊ】典型的な候補相対レイアウトに関して、図２５の方法により生成されるパスの組を示す。
【図２７】木構造のノードのバウンディング・ボックスを評価する方法の一実施形態の流れ図である。
【図２８】ページ上にグラフィック・オブジェクトの初期配置を作成する方法の一実施形態の流れ図である。
【図２９Ａ】ページの異なる区画と、対応する階層木構造の略図である。
【図２９Ｂ】ページの異なる区画と、対応する階層木構造の略図である。
【図２９Ｃ】ページの異なる区画と、対応する階層木構造の略図である。
【図３０Ａ】第１のグラフィック・オブジェクトの表示と、その表示を記述する木構造の略図である。
【図３０Ｂ】第２のグラフィック・オブジェクトの表示と、その表示を記述する木構造の略図である。
【図３０Ｃ】図３０Ａに示される第１のグラフィック・オブジェクトと図３０Ｂに示される第２のグラフィック・オブジェクトに対応する葉ノードを含む粗な木構造と、この粗木構造から得られる対応する改善された木構造の略図である。
【図３０Ｄ】図３０Ｃに示される粗な木構造と改善された木構造に対応する、ページ上のグラフィック・オブジェクトの相対レイアウトである。
【図３１Ａ】ページ上にグラフィック・オブジェクトのレイアウトを作成する方法の一実施形態の第１の部分の流れ図である。
【図３１Ｂ】ページ上にグラフィック・オブジェクトのレイアウトを作成する方法の一実施形態の第２の部分の流れ図である。
【図３２】ページ・スペースの一領域を木構造の根ノードに割り当てる方法の一実施形態の流れ図である。
【図３３】ページ・スペースの複数領域を木構造のノードの子に割り振る方法の一実施形態の流れ図である。
【発明を実施するための形態】
【００１３】
以下の説明では、同じ要素を識別するのに、同じ参照番号が使用される。さらに、図面は、典型的な実施形態の主な特徴を略示することを目的としている。図面は、実際の実施形態のあらゆる特徴も、これらの描かれた要素の相対的寸法も示すつもりはなく、定尺では描かれていない。
【００１４】
（Ｉ．序説）
ここで詳細に説明される実施形態は、１つまたは複数のページ上にグラフィック・オブジェクトを配置する方法を提供する。
これらの実施形態は、それぞれのレイアウト（または配置）において１つまたは複数のグラフィック・オブジェクトの相対的サイズに対する明示的な好みにより誘導または制御され得る。
いくつかの実施形態は、このような特徴を活用して、グラフィック・オブジェクトの異なる１つ１つを特別に目立たせる（すなわち、特徴づける）代替配置を作成する。
このようにして、これらの代替配置は、ページ上のグラフィック・オブジェクトの可能な配置の分布にわたるレイアウトのサンプリングをもたらす。
いくつかの実施形態は、このような特徴を活用して、ユーザーが、１つまたは複数のグラフィック・オブジェクトの相対的サイズに対する好みを入力できるようにし、そこで、このような相対的サイズの好みが、特定のレイアウトにおいてグラフィック・オブジェクトの一部のものを１つ１つ目立たせる（例えば、さらに大きくする）か、あるいは目立たなくする（例えば、さらに小さくする）ように、レイアウト作成プロセスを誘導する。
このようにして、ユーザーは、グラフィック・オブジェクトの特定配置に留意してないときでも、ユーザーの美的好みを満たすような上記グラフィック・オブジェクトの特定レイアウトまでこのシステムを誘導することができる。
【００１５】
ここで使用される「ページ（page）」という語は、グラフィック・オブジェクトのレイアウトが印刷されうる個別の物理媒体（例えば、一枚の紙）で具現される物理ページや、例えば、電子表示装置によりユーザーに表示されうるグラフィック・オブジェクトのレイアウトを収める仮想ページ、デジタル・ページ、または電子ページを含め、グラフィック・オブジェクトがレイアウトされうる任意タイプの個別エリアをさす。
【００１６】
「グラフィック・オブジェクト（graphic object）」という語は、概括的に言えば、画像やテキスト（文章）を含め、物理ページまたは仮想ページ上にレンダリングされうる任意タイプの視覚的に感知できるコンテンツをさす。
画像ベースのグラフィック・オブジェクト（あるいは、単に「画像（image）」）は、イメージ・センサ（例えば、ビデオ・カメラ、静止画カメラ、または光学式スキャナ）により取り込まれた画像、または、このような画像を処理した（例えば、フィリタリングされたり、再フォーマットされたり、改良されたりなどして、変更された）もの、コンピュータで生成されたビットマップ画像またはベクターグラフィック画像、テキスト画像（例えば、テキストを含むビットマップ画像）、および、アイコン画像（iconographic image）を含め、任意タイプのデジタル画像または電子画像の完全なもの、または部分的なものでありうる。
「グラフィック・オブジェクト」という語は、単一要素グラフィック・オブジェクトと、１つまたは複数のグラフィック・オブジェクトの結合力あるグループまたはコレクションから形成された多要素グラフィック・オブジェクトとを両方とも含む。
特定の多要素グラフィック・オブジェクトへの単一要素グラフィック・オブジェクトの割当ては、構成単一要素グラフィック・オブジェクトが結び付けられることを意味する。
一般に、多要素グラフィック・オブジェクト中の単一要素グラフィック・オブジェクトの型は同一であるか、あるいは異なってもよい。
【００１７】
いくつかの実施例では、画像ベースのグラフィック・オブジェクト（例えば、写真などの画像）は、固定エリア画像または可変エリア画像と呼ばれることがある。
これらの実施例では、固定エリア画像のエリアまたはサイズは、作成されたレイアウトでは変更されないが、しかるに、可変エリア画像のサイズは、変更できるようになる。
可変エリア画像は、同一ページ上にレンダリングされた画像の相対エリアに関連する制約を持つことも、持たないこともある。
【００１８】
図示される実施形態では、画像ベースのグラフィック・オブジェクトのそれぞれには、対応する縦横比（aspect ratio）が割り当てられる。
この縦横比は、画像幅に対する画像高さの比率として定義される。
それぞれの可変エリア画像には、さらに、対応する正のスカラー値公称サイズも割り当てられることがある。
「公称サイズ（nominal size）」という語は、実際のサイズ、またはレンダリングされたサイズとは異なることも、異ならないこともある指定サイズまたは理論サイズをさす。
グラフィック・オブジェクトの「サイズ（size）」は、グラフィック・オブジェクトで占有されるページのエリアの大きさをさす。
いくつかの実施形態では、画像に割り当てられる公称サイズの値をユーザーがセットできるようにしている。
他の実施形態では、グラフィック・オブジェクト配置システムは、これらの公称サイズの値をグラフィック・オブジェクトに自動的に割り当てる。
【００１９】
図１は、複数の単一要素グラフィック・オブジェクト（１２〜３２）を含む典型的なページ１０を示している。
【００２０】
図２に示されるように、単一要素グラフィック・オブジェクト（１２〜３２）のうち選択されたものが１つ１つ集められて、グラフィック・オブジェクト４２を形成することがある。グラフィック・オブジェクト４２では、構成グラフィック・オブジェクト（すなわち、１４〜２４）は、グラフィック・オブジェクトのレイアウトにおいて互いに近づけてページに載せるようにもくろまれている。
図２に示される例では、多要素グラフィック・オブジェクト４２は、異なる型の単一要素グラフィック・オブジェクト（例えば、画像ベースのグラフィック・オブジェクトやテキスト形式グラフィック・オブジェクト）を含むことがある。
さらに、多要素グラフィック・オブジェクトの単一要素グラフィック・オブジェクトは、任意に、または特定の順序づけられた連なり（例えば、ビデオ・クリップの時間的に順序づけられた一連のキーフレーム）で、配置されることがある。
他のグラフィック・オブジェクトとの結合力ある関係をまったく持たない単一要素グラフィック・オブジェクトは、１つしか表示を持たない「退化した（degenerate）」グラフィック・オブジェクトである。
【００２１】
図３Ａ〜図３Ｄに示されるように、構成グラフィック・オブジェクトを２つ以上有するグラフィック・オブジェクト５２は、２つ以上のやり方で表示（または、配置）されることがある。
いくつかの実施例では、多要素グラフィック・オブジェクト中の単一要素グラフィック・オブジェクトの表示は、単一要素グラフィック・オブジェクトの水平配置と垂直配置に限定される。
これらの実施例の一部において、上記表示はさらに、単一要素グラフィック・オブジェクトのいくつかの好ましい水平配置と垂直配置に限定されることがある。
例えば、一実施例は、同一多要素グラフィック・オブジェクト中の画像の右側または下方にのみテキスト形式グラフィック・オブジェクトが現われるような表示だけを可能にしている。
このような場合、画像とテキスト・ブロックを含むグラフィック・オブジェクトが２つの異なるやり方で表示されることがある。
図３Ａ〜図３Ｄは、一連（sequence）の６つのグラフィック・オブジェクト５４（例えば、ビデオ・キーフレーム）を含むグラフィック・オブジェクト５２が４つの異なるやり方で表示されうることを示している。
【００２２】
一般に、グラフィック・オブジェクトは、「ストリクト・エリア（strict area）」スタイルまたは「ブリック（brick）」スタイルにより、ページ上にレイアウトされることがある。
ストリクト・エリア・スタイルのレイアウトでは、同一ページ上のグラフィック・オブジェクトの相対エリアは、あらかじめ指定された割合に応じる。
例えば、ユーザーは、同一ページ上のすべてのグラフィック・オブジェクトが同一エリアを持つという条件をつけることがある。
ブリック・スタイルのレイアウトでは、同一ページ上のグラフィック・オブジェクトの相対エリアは、画像間に空きスペースがないように選択される。
ストリクト・エリア・スタイルのレイアウトと、ブリック・スタイルのレイアウトに関するさらなる詳細は、２００４年９月３０日に出願された米国特許出願第１０／６７５，７２４号と、２００４年９月３０日に出願された米国特許出願第１０／６７５，８２３号から入手できる。
【００２３】
（ＩＩ．ページ上にグラフィック・オブジェクトを配置する一般フレームワーク）
図４は、ページ割当てモジュール６２、ページ・レイアウト作成モジュール６４、および、ユーザーがグラフィック・オブジェクト配置システム６０と対話するときに使うユーザー・インターフェース・モジュール６６を含む、１つまたは複数のページ上にグラフィック・オブジェクト７０を配置するシステム６０の一実施形態を示している。
一般に、グラフィック・オブジェクト配置システム６０のモジュール（６２〜６６）は、特定のハードウェア構成またはソフトウェア構成には限定されず、もっと適切に言えば、それらのモジュールは、デジタル電子回路、あるいは、コンピュータのハードウェア、ファームウェア、デバイス・ドライバ、またはソフトウェアを含む、任意のコンピューティング環境または処理環境に導入されることがある。
例えば、いくつかの実施例では、これらのモジュールは、デスクトップ・コンピュータやワークステーション・コンピュータ、デジタル静止画カメラ、デジタル・ビデオカメラ、プリンタ、スキャナ、および携帯用電子装置（例えば、携帯電話、ラップトップ・コンピュータやノートブック・コンピュータ、携帯情報端末）を含む、多種多様なデジタル式およびアナログ式の電子装置のどれか１つの装置のハードウェアに組み込まれる。
いくつかの実施例では、モジュール（６２〜６６）を実行するコンピュータ処理命令と、モジュール（６２〜６６）により生成されるデータは、１つまたは複数の機械可読媒体に保存される。
これらの命令やデータを確実に収めるのに適している記憶装置は、例えば、半導体メモリ素子（例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュ・メモリ素子）、磁気ディスク（例えば、内部ハードディスクやリムーバブル・ディスク）、光磁気ディスク、および、ＣＤ−ＲＯＭを含む、あらゆる形式の不揮発性メモリを含む。
【００２４】
図５は、ページ割当てモジュール６２とページ・レイアウト作成モジュール６４とが協働して、１つまたは複数のページのそれぞれにグラフィック・オブジェクトの対応するレイアウトを作成するときに用いる方法の一実施形態を示している。
【００２５】
ページ割当てモジュール６２は、１つまたは複数のページにグラフィック・オブジェクトを割り当てる（図５のブロック６８）。
ページ割当てモジュール６２は、グラフィック・オブジェクト７０のコレクションを処理する。このコレクションは、ユーザーで指定されるか、あるいは、グラフィック・オブジェクト配置システム６０で自動的に識別されることがある。
ページ割当てモジュール６２は、多種多様なページ割当て方法のどれか１つを用いて、１つまたは複数のページにグラフィック・オブジェクト７０を割り当てる。
いくつかの手法では、ページ割当てモジュール６２は、１つのページ、あるいはユーザー指定またはデフォルトの一定数のページ上にレイアウトされうるユーザー指定またはデフォルトの最大数のグラフィック・オブジェクト７０などのページ埋め（page-filling）基準に基づいて、ページにグラフィック・オブジェクト７０を割り当てる。
これらの手法では、ページ割当てモジュール６２は、グラフィック・オブジェクトのユーザー指定の配置、あるいはグラフィック・オブジェクト７０に関連するメタデータに関して指定されるデフォルト配置ルールなど、１つまたは複数の配置基準により、ページにグラフィック・オブジェクト７０を割り当てることがある。
例えば、ページ割当てモジュール６２は、グラフィック・オブジェクト７０に関連する日付および時間のメタデータに基づいて、発生順にページにグラフィック・オブジェクト７０を割り当てる。
別法として、ページ割当てモジュール６２は、グラフィック・オブジェクト７０のイベント・ベースの解析に基づいて、ページにグラフィック・オブジェクト７０を割り当てることがある。
ページ割当てモジュール６２は、ページへのグラフィック・オブジェクト７０の割当てを指定するグラフィック・オブジェクト・ページ割当てデータ７２を、初期レイアウト作成モジュール６４に渡す。
【００２６】
ページ・レイアウト作成モジュール６４は、グラフィック・オブジェクト割当てデータ７２により、それぞれのページ上の対応するグラフィック・オブジェクトの最終レイアウト７４または確定レイアウト７４を出力する（図５のブロック７６）。
ここで使用される「確定レイアウト（determinate layout）」と「最終レイアウト（final layout）」という語は、グラフィック・オブジェクトの位置および寸法が指定されているページ上のグラフィック・オブジェクトのレイアウトをさすように、同じ意味で使用される。
いくつかの実施形態では、ページ・レイアウト作成モジュール６４は、グラフィック・オブジェクトのサイズを、グラフィック・オブジェクトに割り当てられた公称サイズに近づける最終レイアウトの作成を促進する採点、評価、または適格の機能に基づいて、ページの所与の１つに対して最終レイアウトを決定する。
このような採点、評価、または適格の機能は、以下で詳しく説明されるように、多種多様な異なるレイアウト作成の実施形態において利用されることがある。
いくつかの実施例では、ページ・レイアウト作成モジュール６４は、特定のファイル形式（例えば、ＰＤＦまたはＸＭＬ）で構成されている仕様書（specification）の形式で最終レイアウト７４を出力する。
【００２７】
ページ・レイアウト作成モジュール６４は、１つまたは複数のページ上のグラフィック・オブジェクト７０の最終レイアウト７４をユーザー・インターフェース・モジュール６６に出力し、そこで、最終レイアウトをディスプレイ７７上に表示（またはレンダリング）する（図５のブロック７８）。
いくつかの実施例では、ユーザー・インターフェース・モジュール６６により、ユーザーは、グラフィック・オブジェクト配置システム６０で自動的に生成されたページをインタラクティブに閲覧することができる。
また、ユーザー・インターフェース・モジュール６６により、ユーザーは、これらのページに編集を指定することもできる。
所与のページに指定されたどんな編集も、ユーザー・インターフェース・モジュール６６により解釈される。
ユーザー・インターフェース・モジュール６６は、解釈されたユーザー・コマンド命令をページ・レイアウト作成モジュール６４に送る。
ページ・レイアウト作成モジュール６４は、図５の方法の１つまたは複数の面を繰り返して、ユーザー・インターフェース・モジュール６６から受け取られた編集により、１つまたは複数のページの修正最終レイアウト７４を決定する。
ユーザー・インターフェース・モジュール６６は、その修正最終レイアウト７４をユーザーに表示する。
次に、ユーザーは、修正ページを閲覧するか、これらの１つまたは複数の修正ページに編集を指定するか、あるいは、システム６０に命じて、これらのページの一部または全部をレンダリングすることがある。
【００２８】
（ＩＩＩ．相対エリア・ベースの制御を用いてページ上にグラフィック・オブジェクトを配置する）
（Ａ．前置き）
以下で詳しく説明されるように、ページ・レイアウト作成モジュール６４は、それぞれのページ・レイアウトにおける１つまたは複数のグラフィック・オブジェクトの相対的サイズに対する明示的な好みにより誘導または制御され得る。
このような特徴により、ユーザーは、１つまたは複数のグラフィック・オブジェクトの相対的サイズに対する好みを入力することができ、そこで、このような相対的サイズの好みから、ページ・レイアウト作成モジュール６４は、ユーザーの好みに応じて、特定のレイアウトにおいてグラフィック・オブジェクトの一部のものを１つ１つ目立たせる（例えば、さらに大きくする）か、あるいは目立たなくする（例えば、さらに小さくする）。
これにより、ユーザーは、グラフィック・オブジェクトの特定配置に留意してないときでも、ユーザーの美的好みを満たすような上記グラフィック・オブジェクトの特定レイアウトまでこのシステムを誘導することができる。
いくつかの実施形態では、ページ・レイアウト作成モジュール６４は、１つまたは複数のグラフィック・オブジェクトの相対的サイズに対する明示的な好みを利用して、これらのグラフィック・オブジェクトの異なる１つ１つを特別に目立たせることで、ページ上のグラフィック・オブジェクトの可能な配置の広範分布にわたる代替レイアウトのサンプリングをもたらす。
このような特徴により、ユーザーは、最終レイアウトを選択してレンダリングする前に、多種多様な異なるページ・レイアウトをすばやく閲覧することができる。
【００２９】
図６を参照すると、ページ・レイアウト作成モジュール６４は、ページ割当てモジュール６２（図４を参照）により生成されたページ割当てデータ７２とそれぞれのページを指定する対応するページ・レジスタとに基づいて、最終ページ・レイアウト７４を作成する。
図示される実施形態では、それぞれのページは、ページ上に配置されるようにスケジュールされているグラフィック・オブジェクト（例えば、ＩＭＧ＿１、ＩＭＧ＿２、…、ＩＭＧ＿Ｎ）のリストと、そのリスト中のグラフィック・オブジェクトそれぞれへの対応する縦横比の値（例えば、ａ１、ａ２、…、ａＮ）および対応する公称サイズの値（例えば、ｅ１、ｅ２、…、ｅＮ）の割当てとを含むページ・レジスタ８０によって指定される。
上に説明されるように、画像ベースのグラフィック・オブジェクト（例えば、画像）の縦横比は、グラフィック・オブジェクトの幅に対するその高さの比率として定義される。
公称サイズの値（例えば、ｅ１、ｅ２、…、ｅＮ）は、ユーザーまたはグラフィック・オブジェクト配置システム６４によりセットされることがある。
ページ上の一組のグラフィック・オブジェクトのどんな特定レイアウトの視覚的外観も、そのページに関してページ・レジスタで指定される縦横比の値と公称サイズの値との結び付きによって決定され、その場合、それらの縦横比の値と公称サイズの値との結び付きが異なれば、一般に、視覚的外観の異なるページ・レイアウトが作成されることになる。
【００３０】
（Ｂ．相対エリアの制御を用いてページ・レイアウトを作成する）
（１．概要）
図７は、それぞれのレイアウト（または配置）において１つまたは複数のグラフィック・オブジェクトの相対的サイズに対する明示的な好みにより誘導または制御できるようにするやり方で、ページ・レイアウト作成モジュール６４がページ上に一組のグラフィック・オブジェクトを配置する方法の一実施形態を示している。
【００３１】
図７の方法により、ページ・レイアウト作成モジュール６４は、グラフィック・オブジェクトごとに、グラフィック・オブジェクトに割り当てられた対応する公称サイズに基づいて、ページ上のグラフィック・オブジェクトの対応する目標レンダリング・サイズを確かめる（図７のブロック８２）。
いくつかの実施形態では、ページ・レイアウト作成モジュール６４は、グラフィック・オブジェクトｉごとの目標レンダリング・サイズ（ｔｉ）を、グラフィック・オブジェクトを配置するために割り振られたページの総面積（ＡALLOCATED）の一部分（fraction）にセットする。
その場合、この割合は、このページ上に配置されるグラフィック・オブジェクトの全部（Ｎ）に割り当てられたそれぞれの公称サイズの合計に対する対応する公称サイズ（ｅｉ）の比率に等しい。
すなわち、次式となる。
【００３２】
【数１】
2010532042.tif 000003
【００３３】
ページ・レイアウト作成モジュール６４は、ページ上のグラフィック・オブジェクト１つ１つのそれぞれ異なる候補レイアウトを構築する（図７のブロック８４）。
このプロセスにおいて、ページ・レイアウト作成モジュール６４は、候補レイアウトごとに、ページ上のグラフィック・オブジェクトのそれぞれの実際のレンダリング・サイズを計算する。
以下で詳しく説明されるように、これらの異なる候補レイアウトは、木構造ベースのページ区分手法と、遺伝的（genetic）アルゴリズム・ベースのグラフィック・オブジェクト配置手法を含む（ただし、それらには限定されない）、多種多様な異なるやり方で構築されることがある。
【００３４】
ページ・レイアウト作成モジュール６４は、実際のレンダリング・サイズの１つ１つを、目標レンダリング・サイズの対応する１つ１つと比較することに少なくとも一部、基づいて、ページ上のグラフィック・オブジェクトの最終レイアウトを決定する（図７のブロック８６）。
いくつかの実施形態では、ページ・レイアウト作成モジュール６４は、グラフィック・オブジェクトのサイズをグラフィック・オブジェクトに割り当てられた公称サイズに近づける最終レイアウトの作成を促進する採点、評価、または適格の機能に基づいて、所与のページに対して最終レイアウトを決定する。
このような採点、評価、または適格の機能は、以下で詳しく説明されるように、多種多様な異なるレイアウト作成システムに組み込まれることがある。
【００３５】
グラフィック・オブジェクトの最終レイアウトが決定された（図７のブロック８６）後で、ページ・レイアウト作成モジュール６４は、グラフィック・オブジェクトの最終レイアウトを出力する（図７のブロック８８）。
ページ・レイアウト作成モジュール６４は、最終ページ・レイアウトを記述するデータ構造（例えば、テーブルまたはリスト）を含む仕様書の形式で最終レイアウトを出力することがある。
いくつかの実施形態では、この仕様書は、ＸＭＬ（eXtensible Markup Language）ファイル形式で機械可読媒体に保存される。
仕様書を確実に収めるのに適している記憶装置は、例えば、半導体メモリ素子（例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュ・メモリ素子）、磁気ディスク（例えば、内部ハードディスクやリムーバブル・ディスク）、光磁気ディスク、および、ＣＤ−ＲＯＭを含む（ただし、それらには限定されない）、あらゆる形式の不揮発性コンピュータ読取り可能媒体と揮発性コンピュータ読取り可能媒体とを含む。
最終レイアウト仕様書は、ディスプレイまたは印刷媒体（例えば、紙）上で最終レイアウトをレンダリングするために、ユーザー・インターフェース・モジュール６６または印刷モジュールで使用されることがある。
【００３６】
（２．相対エリア制御用に構成された典型的なタイプのページ・レイアウト作成モジュール）
一般に、ページ・レイアウト作成モジュール６４は、多種多様な異なるやり方で所与のページ上のグラフィック・オブジェクトの最終レイアウトを決定することがある。
【００３７】
いくつかの実施形態では、ページ・レイアウト作成モジュール６４は、それぞれのページの木構造ベースの区分を用いて、所与のページに対して最終レイアウトを決定する。
このプロセスにおいて、ページ・レイアウト作成モジュール６４は、一連の逐次レイアウトを繰り返し構築する。これらのレイアウトはそれぞれ、この一連の逐次レイアウト中の直前のレイアウトに追加されるグラフィック・オブジェクトの追加の１つを含む。
このような繰返しごとに、ページ・レイアウト作成モジュール６４は、それぞれのスコアに基づいて、これらの逐次レイアウトの現在の１つを、その直前の逐次レイアウトから構築する。
これらのスコアは、実際のレンダリング・サイズの１つ１つを、目標レンダリング・サイズの対応する１つ１つと比較することから、計算される。また、これらのスコアは、直前の逐次レイアウトにおける追加グラフィック・オブジェクトのそれぞれ異なる相対的位置で定められた現在候補レイアウトに対して、算出される。
木構造ベースのページ区分の実施形態の構造および動作に関するさらなる詳細は、下記のセクションＩＶに記載される。
【００３８】
他の実施形態では、ページ・レイアウト作成モジュール６４は、遺伝的アルゴリズムにより、所与のページ上に配置されるグラフィック・オブジェクトの位置、縮尺、回転の向きを定める対応する遺伝的構造を進化させ、かつ、いくつかの好みおよびページ要件とともに、上述の採点、評価、または適格の機能に基づいて、その結果得られるレイアウトから最終レイアウトを選択することで、所与のページに対して最終レイアウトを決定する。
遺伝的進化ベースのグラフィック・オブジェクト配置の実施形態の構造および動作に関するさらなる詳細は、例えば、米国特許第６，６３６，６４８号と米国特許出願公報第２００２／０１２２０６７号に記載される。
【００３９】
他の実施形態では、ページ・レイアウト作成モジュール６４は、それぞれの画像が同一ページ上に位置づけられる他の画像に力を加えると仮定する力モデルに基づいて、ページ上に画像を位置づけることで、所与のページに対して最終レイアウトを決定する。
この力は、画像を隔てる距離の関数である。
それぞれの画像は、その画像に作用する正味力の方向に、その正味力の関数である距離だけ移動する。
力モデル・ベースのグラフィック・オブジェクト配置の実施形態の構造および動作に関するさらなる詳細は、例えば、米国特許第６，６３６，６５０号に記載される。
【００４０】
使用されるグラフィック配置モデルのタイプに関係なく、ページ・レイアウト作成モジュール６４のそれぞれの実施形態は、グラフィック・オブジェクトのサイズをグラフィック・オブジェクトに割り当てられた公称サイズに近づける最終レイアウトの作成を促進する採点、評価、または適格の機能に基づいて、所与の組のグラフィック・オブジェクトに対して最終ページ・レイアウトを決定する。
いくつかの実施形態では、ページ・レイアウト作成モジュール６４は、候補レイアウトにおけるグラフィック・オブジェクトの実際のレンダリング・サイズが対応する目標レンダリング・サイズと一致する度合いに基づいて、候補レイアウトごとに、対応するレイアウト・スコアを計算する。
採点の機能は一般に、所与のレイアウトにおけるグラフィック・オブジェクトの実際のサイズがこれらのグラフィック・オブジェクトに割り当てられた公称サイズにどれくらい近いかの指標となる測度（metric）を、取り入れている。
これらの実施形態の一部では、ページ・レイアウト作成モジュール６４は、対応する目標レンダリング・サイズに対する実際のレンダリング・サイズの比率に基づいて、候補レイアウトごとに、これらのグラフィック・オブジェクトのそれぞれに対して、対応するグラフィック・オブジェクト・スコアを計算する。
ページ・レイアウト作成モジュール６４は、候補レイアウトごとに、それぞれのグラフィック・オブジェクト・スコアから、対応するレイアウト・スコアを計算する。
【００４１】
典型的な一実施形態では、レイアウト・スコア（layout_score）は、以下の擬似コードにより、所与の候補ページ・レイアウトに対して計算される。
【００４２】
layout_score=SINITIAL;
group_multiplier=MINITIAL;
フォトごとに、{
比率=actual_area/target_area
graphic_object_score=1.0;
(比率<σ1)の場合、{
graphic_object_score=比率/σ1
(比率<σ2)の場合、{
graphic_object_score=
(graphic_object_score)2;
}
}
(graphic_object_score<δT)の場合、{
group_multiplier=
group_multiplier*θPENALTY;
}
layout_score=layout_score +
graphic_object_score;
｝
layout_score= layout_score* group_multiplier
【００４３】
この典型的な実施形態では、パラメータＳINITIALは、初期レイアウト・スコアであり、一般に、０．０にセットされる。
パラメータＭINITIALは、group-multiplier変数の初期値であり、これは一般に１．０にセットされる。
変数「actual_area」は、所与の候補ページ・レイアウトにおけるグラフィック・オブジェクトの実際のレンダリング・サイズに対応する。
また、変数「target_area」は、図７のブロック８２において確かめられるグラフィック・オブジェクトの目標レンダリング・サイズに対応する。
パラメータσ１は、［０，１］の範囲内の値を持つ第１の比率しきい値（ratio threshold）であって、この比率しきい値は、グラフィック・オブジェクトのそれぞれの実際のエリアがそれらの目標エリアに対して小さいと見なされるためにスコアを減点しなければならないグラフィック・オブジェクトを、特定するものである。
パラメータσ２は、［０，１］の範囲内でσ１よりも小さい値を持つ第２の比率しきい値であって、この比率しきい値は、グラフィック・オブジェクトのそれぞれの実際のエリアがそれらの目標エリアに対して過度に小さいと見なされるためにスコアをさらに減点しなければならないグラフィック・オブジェクトを、特定するものである。
典型的な一実施例では、σ１＝０．９であり、またσ２＝０．５である。
パラメータδＴは、総合レイアウト・スコアを減点しなければならないほどスコアが低いと見なされるグラフィック・オブジェクトを特定するグラフィック・オブジェクト・スコアしきい値であって、これは、「group_multiplier」変数の値を、ペナルティー係数パラメータθPENALTYでセットされた大きさだけ下げることで得られる。
典型的な一実施例では、δＴ＝０．２５であり、またθPENALTY＝０．８である。
【００４４】
これらの実施形態では、ページ・レイアウト作成モジュール６４は一般に、ユーザー・インターフェース・モジュール６６に出力されてユーザーに表示する最終レイアウトとして、最高レイアウト・スコアを持つレイアウトを選択する。
いくつかの実施形態では、ページ・レイアウト作成モジュール６４は、最高採点レイアウトの複数のもの１つ１つに対して仕様書を保存する。
ユーザーの要求に応じて、これらのレイアウト仕様書の１つまたは複数をユーザー・インターフェース・モジュール６６に出力して、１つまたは複数の代替レイアウトを閲覧することもある。
【００４５】
（Ｃ．相対エリアの制御を用いて代替レイアウトを作成する）
（１．グラフィック・オブジェクト・レイアウトを閲覧するユーザー・インターフェース）
図８は、システム６０（図４を参照）により自動的に生成されるページをインタラクティブに閲覧するユーザー・インターフェース９０の一実施形態を示している。
ユーザー・インターフェース９０は、メイン・ウィンドウ９２、グラフィック・オブジェクト閲覧ウィンドウ９４、レイアウト閲覧ウィンドウ９６を含む。
メイン・ウィンドウ９２は、ページ１０２上のグラフィック・オブジェクト１００（すなわち、ＩＭＧ＿４４３、ＩＭＧ＿４２９、ＩＭＧ＿４２１、ＩＭＧ＿４２３、ＩＭＧ＿４２５、ＩＭＧ＿４４２）の現在のレイアウト９８を表示している。
グラフィック・オブジェクト閲覧ウィンドウ９４は、グラフィック・オブジェクト１００の低解像度のサムネイル画像１０４の配列（array）を含む。
レイアウト閲覧ウィンドウ９６は、アルバム（図８に示される典型的なアルバムでは、単一ページから成っている）の複数ページの現在のレイアウトの低解像度サムネイル画像１０６を含む。
【００４６】
ユーザー・インターフェース９０は、グラフィック・オブジェクト１００のうち、１つまたは複数の点で現在のレイアウト９８とは異なる指定された数の代替レイアウトをシステム６０に作成させる要求を出すオプションをユーザーに提供する。
代替レイアウトの数は、ユーザーにより指定されることがある。別法として、代替レイアウトの数はデフォルトの数であることもある。
ユーザーは、システム６０に代替レイアウトを作成させる要求において、１つまたは複数のグラフィック・オブジェクト１００の相対的サイズに対する好みを入力することがある。
このような相対的サイズの好みは、特定のレイアウトにおいてグラフィック・オブジェクトの一部のものを１つ１つ目立たせる（例えば、さらに大きくする）か、あるいは目立たなくする（例えば、さらに小さくする）点で、レイアウト作成プロセスを誘導する。
ページ・レイアウト作成モジュール６４は、以下で述べられるランダム化されたやり方で、または、以下で述べられるあらかじめ定められた方法により、あるいは、ユーザーの好みにより（ユーザーの好みが、この要求で指定される場合）、指定された数の代替レイアウトのページに等しい数のページ・レジスタを生成する。
以下で詳しく説明されるように、それぞれのページ・レジスタが、グラフィック・オブジェクトへのそれぞれの公称サイズの一意の割当てを含むように（例えば、図６を参照）、ページ・レイアウト作成モジュール６４は、ページ・レジスタを生成する。
【００４７】
図９は、メイン・ウィンドウ１１５とサイド・ウィンドウ１１８を含むユーザー・インターフェース１１３を示している。
メイン・ウィンドウ１１５は、ユーザーで選択されたレイアウト１１６を表示する。
サイド・ウィンドウ１１８は、ページ・レイアウト作成モジュール６４により生成されたグラフィック・オブジェクト１００の代替配置１２０のサムネイル画像を表示する。
現在のレイアウト９８のサムネイル１０６（図８を参照）は、図９に「Variation１」と標記される、サイド・ウィンドウ１１８（すなわち、「変形形態」）の上端に含まれる。
ユーザーは、例えばポインタ（例えば、コンピュータのマウス）を用いて、サイド・ウィンドウ１１８内の対応するサムネイル画像１２０を選択することで、メイン・ウィンドウ１１５に表示される代替配置を選択することがある。
ユーザーは、「＜＜Apply」ボタン１２２を選択することで、ユーザー・インターフェース９０のメイン・ウィンドウに表示される現在のレイアウト９８（図８を参照）を、代替配置のうちの選択された１つに代える。
図１０は、ユーザーが「＜＜Apply」ボタン１２２を選択した後のユーザー・インターフェース９０を示しているが、一方、代替レイアウト１１６のサムネイル画像（すなわち、「variation２」）が選択された。
【００４８】
（２．代替グラフィック・オブジェクト・レイアウトを作成する）
（ａ．概要）
いくつかの実施形態では、ページ・レイアウト作成モジュール６４は、以下の処理ステップにより、所与の組のグラフィック・オブジェクトの代替レイアウトを作成する。
１．グラフィック・オブジェクトの縦横比とグラフィック・オブジェクトに割り当てられた公称サイズとの一意の結び付きをそれぞれが含む一組のページ・レジスタを生成する。
２．それぞれのページ・レジスタに対して候補レイアウトを作成する。
３．１つまたは複数のやり方で、異なるものと判定される候補レイアウトの１つ１つを選択する。
ステップ１において生成されるページ・レジスタは一般に、それぞれ異なる候補ページ・レイアウトを作成させる。なぜなら、これらの代替ページ・レジスタが、グラフィック・オブジェクトの縦横比とグラフィック・オブジェクトの公称サイズとの一意の結び付きを含むからである。
【００４９】
システム６０のいくつかの実施形態により、ユーザーは、この組の代替候補レイアウトにおいて、グラフィック・オブジェクトの１つまたは複数が目立たせられる（例えば、さらに大きくなる）べきか、あるいは目立たなくされられる（例えば、さらに小さくなる）べきという条件をつけることができる。
これらの実施形態では、上述の作業の流れは同一である。しかしながら、ユーザーで指定される好みにより、候補レイアウトごとに、これらの選択グラフィック・オブジェクトは、目立たせられるか、あるいは、目立たなくさせられる。
これらの実施形態により、ページ・レイアウト作成モジュール６４は、以下の処理ステップにより、所与の組のグラフィック・オブジェクトの代替レイアウトを作成する。
１．グラフィック・オブジェクトの縦横比とグラフィック・オブジェクトに割り当てられた公称サイズとの一意の結び付きをそれぞれが含み、また、ユーザーの好みにより、グラフィック・オブジェクトの選択されたものを１つ１つ目立たせるか、あるいは、目立たなくする一組のページ・レジスタを生成する。
２．それぞれのページ・レジスタに対して候補レイアウトを作成する。
３．１つまたは複数のやり方で、異なるものと判定され、また、ユーザーの好みにより、グラフィック・オブジェクトの選択されたものを１つ１つ目立たせるか、あるいは、目立たなくする候補レイアウトの１つ１つを選択する。
【００５０】
図１１は、ページ上にグラフィック・オブジェクトの１つまたは複数の代替配置を作成する方法の一実施形態を示している。
【００５１】
図１１の方法により、ページ・レイアウト作成モジュール６４は、グラフィック・オブジェクトへの対応する公称サイズの２つ以上の候補割当てを決定する（図１１のブロック１１０）。
以下で詳しく説明されるように、これらの候補割当てはそれぞれ互いに異なっている。
【００５２】
ページ・レイアウト作成モジュール６４は、１つまたは複数の候補割当てのそれぞれに基づいて、ページ上のグラフィック・オブジェクトの１つまたは複数の候補レイアウトから成る対応する組を構築する（図１１のブロック１１２）。
上で説明されるように、これらの異なる候補レイアウトは、木構造ベースのページ区分手法と、遺伝的アルゴリズム・ベースのグラフィック・オブジェクト配置手法を含む（ただし、それらには限定されない）、多種多様な異なるやり方で構築されることがある。
【００５３】
ページ・レイアウト作成モジュール６４は、これらの候補レイアウトの１つまたは複数を出力する（図１１のブロック１１４）。
いくつかの実施形態では、ページ・レイアウト作成モジュール６４は、そのレイアウトが他のレイアウトとは異なるものと判定される候補レイアウトを、１つ１つ出力する。
【００５４】
（ｂ．異なる候補割当てを決定する）
これらのグラフィック・オブジェクトへのそれぞれの公称サイズの１つまたは複数の候補割当てを、ページ・レイアウト作成モジュール６４が決定できる異なる方法が多数ある（図１１のブロック１１０）。
このセクションに述べられる実施形態は、ページ・レイアウト作成モジュール６４で異なる候補レイアウトを作成させそうな候補割当てを含む一組のページ・レジスタを生成することを目的としている。
【００５５】
図１２は、ページ上にレイアウトされるグラフィック・オブジェクトへのそれぞれの公称サイズの候補割当てを作成する方法の一実施形態を示している。
この方法により、ページ・レイアウト作成モジュール６４は、これらのグラフィック・オブジェクトのそれぞれを、一組の所定のグラフィック・オブジェクト型クラスから選択された対応するクラスに分類する（図１２のブロック１３０）。
ページ・レイアウト作成モジュール６４は、一連のグラフィック・オブジェクトを、これらのグラフィック・オブジェクトにそれぞれ割り当てられたクラスに基づいて生成する（図１２のブロック１３２）。
いくつかの実施形態では、この一連のグラフィック・オブジェクトは、異なる候補レイアウトにおいて、これらのグラフィック・オブジェクトの異なるものを１つ１つ特徴づける（または、目立たせる）ように設計される。
ページ・レイアウト作成モジュール６４は、この一連のグラフィック・オブジェクトから、１つまたは複数の候補割当てを作成する（図１２のブロック１３４）。
【００５６】
一般に、この組の所定のグラフィック・オブジェクト型クラスは、多種多様の異なるグラフィック・オブジェクト型クラスを含むことがある（図１２のブロック１３０を参照）。
図１３Ａ〜図１６Ｂ、図１９Ａ、図１９Ｂに示される実施形態では、これらのグラフィック・オブジェクトは、ポートレート・クラス（Ｐ）、ランドスケープ・クラス（Ｌ）、正方形クラス（Ｓ）、ワイド・ランドスケープ・クラス（Ｗ）、ナロー・ポートレート・クラス（Ｎ）から選択された対応するクラスに分類される。
この種の分類は、写真などの画像ベースのグラフィック・オブジェクトを分類するのに特に適している。
これらのクラスはそれぞれ、クラス中のグラフィック・オブジェクトの縦横比（すなわち、高さ／幅）により定められる。
この種の典型的な一実施形態では、ポートレート・クラス（Ｐ）は、約４：３の縦横比を持つ画像を含み、ランドスケープ・クラス（Ｌ）は、約３：４の縦横比を持つ画像を含み、正方形クラス（Ｓ）は、約１：１の縦横比を持つ画像を含み、ワイド・ランドスケープ・クラス（Ｗ）は、３：４よりも小さい縦横比を持つ画像を含み、さらに、ナロー・ポートレート・クラス（Ｎ）は、４：３よりも大きい縦横比を持つ画像を含む。
【００５７】
図１３Ａは、グラフィック・オブジェクト型クラスに対応する最初の文字と、それに続く順序番号（sequence number）に対応する数字とでそれぞれが標記されている典型的な一連の９つのグラフィック・オブジェクト１３６（すなわち、Ｐ１、Ｌ２、Ｐ３、Ｐ４、Ｌ５、Ｓ６、Ｗ７、Ｌ８、Ｎ９）を示している。
図１３Ｂは、この組の所定のオブジェクト型クラス（Ｗ、Ｌ、Ｓ、Ｐ、Ｎ）のそれぞれへのグラフィック・オブジェクト１３６の分布１３８を示している。
【００５８】
一般に、ページ・レイアウト作成モジュール６４は、多くの異なるやり方で、一連のグラフィック・オブジェクトを、これらのグラフィック・オブジェクトにそれぞれ割り当てられたクラスに基づいて生成することがある（図１２のブロック１３２）。
いくつかの実施形態では、ページ・レイアウト作成モジュール６４は、これらのグラフィック・オブジェクトのそれぞれ直前のものを１つ１つ選択したグラフィック・オブジェクト型クラスとは異なるグラフィック・オブジェクト型クラスの１つ１つから、一連のグラフィック・オブジェクトとして、これらのグラフィック・オブジェクトの連続する１つ１つを選択する。
例えば、図１３Ｃは、このような一連のグラフィック・オブジェクトを生成する典型的な一方法を示している。
この方法では、ページ・レイアウト作成モジュール６４は、図１３Ｃに示される順序づけられた一連のスキャンラインに従って左から右へ、分布１３８をスキャンする。
ページ・レイアウト作成モジュール６４は、スキャンラインの順番にグラフィック・オブジェクト１３６を順序づける。
その結果得られるグラフィック・オブジェクト１３６の一連のもの（１４０）が図１３Ｄに示されている。
【００５９】
ページ・レイアウト作成モジュール６４は、多種多様な異なるやり方で、一連のグラフィック・オブジェクト１４０から、１つまたは複数の候補割当てを作成することがある（図１２のブロック１３４を参照）。
【００６０】
いくつかの実施形態では、このページ上にレイアウトされるグラフィック・オブジェクトの組で、それぞれのグラフィック・オブジェクト型クラスが表現される場合に、ページ・レイアウト作成モジュール６４は、そのオブジェクト型クラスの１つの画像が特徴づけられる１つの対応する候補割当てを作成する。
これらの実施形態の一部では、これらのグラフィック・オブジェクト型クラスの表現されたものそれぞれがこれらのグラフィック・オブジェクトの少なくとも１つを含む場合に、ページ・レイアウト作成モジュール６４は、表現された対応するグラフィック・オブジェクト型クラスのグラフィック・オブジェクトの対応する１つに、これらの公称サイズの最大の１つが割り当てられる候補割当ての対応する１つを作成する。
このタイプの典型的な一実施形態では、ページ・レイアウト作成モジュール６４は、以下の擬似コードにより、それぞれの候補割当てを含むページ・レジスタを生成する（「候補割当て作成プロセスＡ」）。
【００６１】
Ｉ．候補割当て作成プロセスＡ
マーカ＝０にセット（Set）する
(i=0; i<C; i++)の場合（for）{
あらゆるグラフィック・オブジェクトで、新たな「現在」ページ・レジスタをスタートする
一連のグラフィック・オブジェクト中で「マーカ」位置のグラフィック・オブジェクトを選択する
マーカ＝マーカ＋１
この選択グラフィック・オブジェクトを、ページ上で「特徴づけられる」と称する
他のすべてのグラフィック・オブジェクトを、「特徴づけられない」と称する
これらの名称を現在ページ・レジスタに保存する
この現在ページ・レジスタを、代替ページ・レジスタのリストに登録する
}
【００６２】
このプロセスにおいて、変数Ｃは、このページ上にレイアウトされるグラフィック・オブジェクトの組で表現されるグラフィック・オブジェクト型クラスの数である。
【００６３】
図１４Ａと図１４Ｂは、それぞれ、順序づけられた一連のグラフィック・オブジェクト１４０中のグラフィック・オブジェクトへの公称サイズ（１４６、１４８）の対応する割当てを含む典型的なページ・レジスタ（１４２、１４４）を示している。
ページ・レジスタ１４２は、候補割当て作成プロセスＡのｆｏｒループの１回目の繰返し後に生成される。
マーカは、プロセスＡのｆｏｒループの１回目の繰返し中に増分された後で、一連のグラフィック・オブジェクト中の２番目のグラフィック・オブジェクト（すなわち、Ｌ２）に位置づけられる。
１番目のグラフィック・オブジェクト（Ｗ７）は、４という公称サイズの割当てによって、ページ・レジスタ１４２の中で特徴づけられるが、しかるに、その他のグラフィック・オブジェクトには、１という対応する公称サイズが割り当てられている。
ページ・レジスタ１４４は、上記擬似コードのｆｏｒループの２回目の繰返し後に生成される。そこでは、マーカ「Ｍ」が、一連のグラフィック・オブジェクト１４０中の３番目のグラフィック・オブジェクト（すなわち、Ｓ６）に位置づけられ、また、その値は２回目のｆｏｒループ繰返し中に増分されている。
２番目のグラフィック・オブジェクト（Ｌ２）は、４という公称サイズの割当てによって、ページ・レジスタ１４４の中で特徴づけられるが、しかるに、その他のグラフィック・オブジェクトには、１という対応する公称サイズが割り当てられている。
【００６４】
このページ上にレイアウトされるグラフィック・オブジェクトの組で表現されるグラフィック・オブジェクト型クラスの数（Ｃ）が、呼出しモジュール（例えば、ユーザー・インターフェース９０）で要求された代替レイアウトの数よりも多いか、あるいは等しい場合には、ページ・レイアウト作成モジュール６４は、候補割当て作成プロセスＡにより生成された代替ページ・レジスタから候補レイアウトを作成して、その要求された数の候補レイアウトを出力する。
【００６５】
このページ上にレイアウトされるグラフィック・オブジェクトの組で表現されるグラフィック・オブジェクト型クラスの数（Ｃ）が、呼出しモジュール（例えば、ユーザー・インターフェース９０）で要求された代替レイアウトの数よりも少ない場合には、１つまたは複数の追加候補割当て作成プロセスを実行して、その要求された数の代替レイアウトを満たすのに充分な数の候補割当てを作成する。
いくつかの実施形態では、候補レイアウト作成モジュール６４は、第１の組の１つまたは複数の公称サイズか、あるいは、第２の組の１つまたは複数の公称サイズから選択された対応する公称サイズがこれらのグラフィック・オブジェクトに割り当てられ、しかも、第２の組の公称サイズのそれぞれが第１の組の公称サイズの最小のものよりも小さいような、追加の代替候補割当てを作成する。
図示される実施形態では、第１の組は、４というただ１つの公称サイズから成り、また、第２の組は、１というただ１つの公称サイズから成っている。
これらの代替候補割当てはそれぞれ、第１の組の公称サイズから選択された公称サイズが割り当てられた異なる数のグラフィック・オブジェクトを持っている。
この種の典型的な一実施形態では、ページ・レイアウト作成モジュール６４は、以下の擬似コードにより、それぞれの候補割当てを含む追加のページ・レジスタを生成する（「候補割当て作成プロセスB」）。
このプロセスにおいて、ＮADDITIONAL＝ＮREQUESTED−ＮGENERATED。ここで、ＮREQUESTEDは、呼出しモジュールで要求された代替レイアウトの数であり、また、ＮGENERATEDは、ページ・レイアウト作成モジュール６４ですでに作成された候補割当ての数である。
また、Ｎは、このページ上に配置される写真（photo）の数である。
【００６６】
ＩＩ．候補割当て作成プロセスＢ
(NADDITIONAL>N-2)の場合（if）に、
then{
(i=2; i<N; i++)では（for）{
あらゆるグラフィック・オブジェクトで、新たな「現在」ページ・レジスタをスタートする
一連のグラフィック・オブジェクト中で「マーカ」位置以降のｉ枚の写真を選択する（必要に応じて、その一連のグラフィック・オブジェクトの始まりまでラップ（wrap）する）
マーカ＝（マーカ＋ｉ）モジュロ（modulo）（Ｎ）
この選択グラフィック・オブジェクトを、ページ上で「特徴づけられる」と称する
他のすべてのグラフィック・オブジェクトを、「特徴づけられない」と称する
これらの名称を現在ページ・レジスタに追加する
この現在ページ・レジスタを、代替ページ・レジスタのリストに追加する
}
}
そうでない場合（else）{
(i=1; i≦NADDITIONAL; i++)では（for）{
あらゆるグラフィック・オブジェクトで、新たな「現在」ページ・レジスタをスタートする
x=(2*i-1)/(2* NADDITIONAL)
x=x*(N-2)
x=x+2
一連のグラフィック・オブジェクト中で「マーカ」位置以降のｘ枚の写真を選択する（必要に応じて、その一連のグラフィック・オブジェクトの始まりまでラップする）
マーカ＝（マーカ＋ｘ）モジュロ（modulo）（Ｎ）
この選択グラフィック・オブジェクトを、ページ上で「特徴づけられる」と称する
他のすべてのグラフィック・オブジェクトを、「特徴づけられない」と称する
これらの名称を現在ページ・レジスタに保存する
この現在ページ・レジスタを、代替ページ・レジスタのリストに追加する
}
}
【００６７】
図１５Ａと図１５Ｂはそれぞれ、プロセスＡが完了した直後に、条件（ＮADDITIONAL＞Ｎ−２）が真であった（すなわち、プロセスＢの第１のｆｏｒループに進むよう制御を強制する）と仮定して、順序づけられた一連のグラフィック・オブジェクト１４０中のグラフィック・オブジェクトへの公称サイズ（１５６、１５８）の対応する割当てを含む典型的なページ・レジスタ（１５２、１５４）を示している。
ページ・レジスタ１５２は、このｆｏｒループの１回目の繰返し後に生成される。
マーカ「Ｍ」は、一連のグラフィック・オブジェクト１４０中のグラフィック・オブジェクト（すなわち、Ｌ８）に位置づけられている。なぜなら、「候補割当て作成プロセスＡ」の終了時には、このマーカがグラフィック・オブジェクトＬ５をポイントしていたことになり、また、「候補割当て作成プロセスＢ」の１回目のｆｏｒ−ｌｏｏｐ繰返し中に、その値が２だけ増分されたからである。
オブジェクトＬ５とオブジェクトＰ３は、４という公称サイズの割当てによって、ページ・レジスタ１５２の中で特徴づけられるが、しかるに、その他のグラフィック・オブジェクトには、１という対応する公称サイズが割り当てられている。
ページ・レジスタ１５４は、候補割当て作成プロセスＢの第１のｆｏｒループの２回目の繰返し後に生成され、そこでは、マーカ「Ｍ」が、一連のグラフィック・オブジェクト１４０中のグラフィック・オブジェクトＬ２に位置づけられている。
８番目のオブジェクトＬ８、９番目のオブジェクトＰ４、および１番目のオブジェクトＷ７は、４という公称サイズの割当てによって、ページ・レジスタ１５４の中で特徴づけられるが、しかるに、その他のグラフィック・オブジェクトには、１という対応する公称サイズが割り当てられている。
【００６８】
図１６Ａと図１６Ｂはそれぞれ、プロセスＡが完了した直後に、条件（ＮADDITIONAL＞Ｎ−２）が偽であった（すなわち、プロセスＢの第２のｆｏｒループに進むよう制御を強制する）と仮定して、順序づけられた一連のグラフィック・オブジェクト１４０中のグラフィック・オブジェクトへの公称サイズ（１６６、１６８）の対応する割当てを含む典型的なページ・レジスタ（１６２、１６４）を示している。
ページ・レジスタ１６２は、候補割当て作成プロセスＢの第２のｆｏｒループの１回目の繰返し後に生成され、そこでは、マーカ「Ｍ」が、一連のグラフィック・オブジェクト１４０中のグラフィック・オブジェクトＰ４に位置づけられている。
オブジェクトＬ５、オブジェクトＰ３、およびオブジェクトＬ８は、４という公称サイズの割当てによって、ページ・レジスタ１６２の中で特徴づけられるが、しかるに、その他のグラフィック・オブジェクトには、１という対応する公称サイズが割り当てられている。
ページ・レジスタ１６４は、候補割当て作成プロセスＢの第２のｆｏｒループの２回目の繰返し後に生成され、そこでは、マーカ「Ｍ」が、一連のグラフィック・オブジェクト１４０中のグラフィック・オブジェクトＰ３に位置づけられている。
オブジェクトＰ４、オブジェクトＷ７、オブジェクトＬ２、オブジェクトＳ６、オブジェクトＰ１、オブジェクトＮ９、オブジェクトＬ５は、４という公称サイズの割当てによって、ページ・レジスタ１６４の中で特徴づけられるが、しかるに、その他のグラフィック・オブジェクトには、１という対応する公称サイズが割り当てられている。
【００６９】
いくつかの実施形態では、その要求された数の代替候補ページ・レイアウトを満たすために、追加の代替候補割当てを必要とする場合には、ページ・レイアウト作成モジュール６４は、代替候補割当てをランダムに作成する。
例えば、いくつかの実施形態では、これらの候補割当ての対応する１つ１つに対して、ページ・レイアウト作成モジュール６４は、１つまたは複数の公称サイズから成る第１の組から選択された対応する公称サイズを、このページ上にレイアウトされるグラフィック・オブジェクトのランダムな数のランダム選択物に割り当てる。
また、ページ・レイアウト作成モジュール６４は、１つまたは複数の公称サイズから成る第２の組から選択された対応する公称サイズを、これらのグラフィック・オブジェクトの他の１つ１つに割り当てる。
これらの実施形態の一部では、この第２の組の公称サイズのそれぞれは、この第１の組の公称サイズの最小のものよりも小さい。
図１７は、この種の典型的な一実施形態を示している。
【００７０】
図１７の候補割当て作成方法により、このページ上にレイアウトされる現在のランダムな一連のグラフィック・オブジェクトが生成される（図１７のブロック１７０）。
対応する候補レイアウトにおいて特徴づける上記現在のランダムな一連のグラフィック・オブジェクト中の現在のランダムな数（Ｒ）のグラフィック・オブジェクトから成る現在の一組が決定される（図１７のブロック１７２）。
いくつかの実施形態では、この現在の一組のグラフィック・オブジェクトとして、上記現在のランダムな一連のグラフィック・オブジェクト中の最初のＲ個のグラフィック・オブジェクトが選択される。
１つまたは複数の公称サイズから成る第１の組から選択された対応する公称サイズが、上記現在のランダムな一連のグラフィック・オブジェクト中の上記現在の一組のグラフィック・オブジェクトに割り当てられる（図１７のブロック１７４）。
１つまたは複数の公称サイズから成る第２の組から選択された対応する公称サイズが、上記現在のランダムな一連のグラフィック・オブジェクト中の他のグラフィック・オブジェクトに割り当てられる。そこでは、この第２の組の公称サイズのそれぞれは、この第１の組の公称サイズの最小のものよりも小さい（図１７のブロック１７６）。
現在の割当てが、前に作成されたすべての候補割当てと比較される（図１７のブロック１７８）。
現在の割当てが、前に作成されたすべての候補割当てとは異なる場合（図１７のブロック１８０）には、現在の割当てが、代替候補割当てのリストに追加される（図１７のブロック１８２）。
そうでなく、現在の割当てが、前に作成されたすべての候補割当てのどれにも類似する（すなわち、大して違わない）場合には、現在の割当てが廃棄される（図１７のブロック１８４）。
【００７１】
図１７のプロセスは、代替候補割当てのリストが所望の長さを持つまで、あるいは、最高回数の試行が行われるまで、繰り返されることがある。
【００７２】
図１８は、グラフィック・オブジェクトへのそれぞれの公称サイズの割当てを比較する（図１７のブロック１７８を参照）方法の一実施形態の流れ図である。
この方法により、これらのグラフィック・オブジェクトが、それぞれ、一組の所定のグラフィック・オブジェクト型クラスから選択された対応するクラスに分類される（図１８のブロック１８６）。
現在の割当てと、前に作成された候補割当てのそれぞれに対して、ページ・レイアウト作成モジュール６４は、これらのグラフィック・オブジェクトに割当てられた公称サイズを、これらのグラフィック・オブジェクト型クラスのそれぞれに分布させる（図１８のブロック１８８）。
図１９Ａは、図１３Ｂに示されるグラフィック・オブジェクト１７６に割り当てられた典型的な一組の公称サイズを、上記組の所定のオブジェクト型クラスのそれぞれに分布させたもの１９２を示している。
現在割当て用の分布を、前に作成された候補割当て用にもたらされた分布と比較する（図１８のブロック１９０）。
図１９Ｂは、図１９Ａに示されるグラフィック・オブジェクトに割り当てられた公称サイズの分布１９４を示しており、そこでは、それぞれのオブジェクト型クラス中の公称サイズが、大きさの順に分類されている。
割当てを比較する基礎として、分布１９４が使用されることがある。
例えば、２つの割当てが、図１９Ｂに示されるタイプのものと同一の分布を持つ場合には、これらの割当ては、同一のものと見なされる。そうでなければ、これらの割当ては、異なるものと見なされる。
【００７３】
図１８に示される比較プロセスも使用して、図１２のブロック１３４から出力される候補割当てが一意であることを保証することがある。
【００７４】
（ＩＶ．典型的なページ・レイアウト生成実施形態）
（Ａ．前置き）
このセクションに述べられる実施形態では、ページ・レイアウト作成モジュール６４は、それぞれのページの木構造ベースの区分を用いて、所与のページに対して最終レイアウトを決定する。
このプロセスにおいて、ページ・レイアウト作成モジュール６４は、一連の逐次レイアウトを繰り返し構築する。これらのレイアウトはそれぞれ、この一連の逐次レイアウト中の直前のレイアウトに追加されるグラフィック・オブジェクトの１つを含む。
このような繰返しごとに、ページ・レイアウト作成モジュール６４は、それぞれのスコアに基づいて、これらの逐次レイアウトの現在の１つを、その直前の逐次レイアウトから構築する。
これらのスコアは、実際のレンダリング・サイズの１つ１つを、目標レンダリング・サイズの対応する１つ１つと比較することから、計算される。また、これらのスコアは、直前の逐次レイアウトにおける追加グラフィック・オブジェクトのそれぞれ異なる相対的位置で定められる現在候補レイアウトに対して、算出される。
【００７５】
図２０は、初期レイアウト作成モジュール２６４、レイアウト評価モジュール２６６、最終レイアウト作成モジュール２７０を含むページ・レイアウト作成モジュール６４の一実施形態を示している。
【００７６】
一般に、ページ・レイアウト作成モジュール６４のモジュール（２６４〜２７０）は、特定のハードウェア構成やソフトウェア構成にはまったく限定されず、もっと適切に言えば、それらのモジュールは、デジタル電子回路、あるいは、コンピュータのハードウェア、ファームウェア、デバイス・ドライバ、またはソフトウェアを含む、任意のコンピューティング環境または処理環境に導入されることがある。
例えば、いくつかの実施例では、これらのモジュールは、デスクトップ・コンピュータやワークステーション・コンピュータ、デジタル静止画カメラ、デジタル・ビデオカメラ、プリンタ、スキャナ、および携帯用電子装置（例えば、携帯電話、ラップトップ・コンピュータやノートブック・コンピュータ、携帯情報端末）を含む、多種多様なデジタル式およびアナログ式の電子装置のどれか１つの装置のハードウェアに組み込まれうる。
いくつかの実施例では、モジュール（２６４〜２７０）を実行するコンピュータ処理命令と、モジュール（２６４〜２７０）により生成されるデータは、１つまたは複数の機械可読媒体に保存される。
これらの命令やデータを確実に収めるのに適している記憶装置は、例えば、半導体メモリ素子（例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュ・メモリ素子）、磁気ディスク（例えば、内部ハードディスクやリムーバブル・ディスク）、光磁気ディスク、および、ＣＤ−ＲＯＭを含め、あらゆる形式の不揮発性メモリを含む。
【００７７】
図２１は、初期レイアウト作成モジュール２６４、レイアウト評価モジュール２６６、および最終レイアウト作成モジュール２７０が、協働して、１つまたは複数のページ上にグラフィック・オブジェクトのレイアウトを作成するときに用いる方法の一実施形態を示している。
【００７８】
初期レイアウト作成モジュール２６４は、グラフィック・オブジェクト割当てデータ７８に基づいて、それぞれのページ上に、グラフィック・オブジェクト７０の初期配置２８０（または、初期相対レイアウト）を作成する（図２１のブロック２８２）。
ここで使用される「相対レイアウト（relative layout）」という語は、これらのグラフィック・オブジェクトの相対的位置が指定されるが、ただし、これらのグラフィック・オブジェクトの絶対的位置が指定されないページ上のグラフィック・オブジェクトのレイアウトをさす。
いくつかの実施例では、初期レイアウト作成モジュール２６４は、グラフィック・オブジェクトに対応する葉ノードと、対応するページの境界線（division）に対応する内部ノードとを有する２分木を表す対応するデータ構造２６８に、それぞれの相対ページ・レイアウトの仕様書を保存している。
初期レイアウト作成モジュール２６４は、ページ上のグラフィック・オブジェクト７０の初期配置２８０を、最終レイアウト作成モジュール２７０に渡す。
【００７９】
最終レイアウト作成モジュール２７０は、初期レイアウト作成モジュール２６４より受け取った初期配置から、ページ上にグラフィック・オブジェクトの最終配置を作成する（図２１のブロック２８８）。
このプロセスにおいて、最終レイアウト作成モジュール２７０は、１つまたは複数のページ上のグラフィック・オブジェクトの対応する確定レイアウト２９０を決定する。
ここで使用される「確定レイアウト（determinate layout）」または「最終レイアウト（final layout）」という語は、グラフィック・オブジェクトの位置および寸法が指定されているページ上のグラフィック・オブジェクトのレイアウトをさす。
最終レイアウト作成モジュール２７０は、１つまたは複数のページ上のグラフィック・オブジェクトの最終確定レイアウト２９０を、ユーザー・インターフェース・モジュール６６に出力する。
【００８０】
１つまたは複数のページ上にグラフィック・オブジェクトの初期配置２８０および最終配置２９０を作成するプロセスにおいて（図２１のブロック２８２、ブロック２８８）、初期レイアウト作成モジュール２６４と最終レイアウト作成モジュール２７０は、１つまたは複数のページ上にグラフィック・オブジェクト７０の様々な候補配置と一組の最終配置を作成する。
初期レイアウト作成モジュール２６４と最終レイアウト作成モジュール２７０は、これらの配置の仕様書をレイアウト評価モジュール２６６に渡し、そこで、レイアウト実現可能性を決定し、ページ上のグラフィック・オブジェクトに対して様々なレイアウト寸法を算出し、さらに、候補配置に対してスコアを算出する。
以下で詳しく説明されるように、実現可能性テスト結果、寸法、スコアは、初期レイアウト作成モジュール２６４と最終レイアウト作成モジュール２７０で使用されて、作成された様々な候補配置から、グラフィック・オブジェクトの初期配置８０と最終配置２９０とを選択する。
【００８１】
（Ｂ．木構造）
図２２を参照すると、初期レイアウト作成モジュール２６４は、それぞれのページ３００を、対応する木構造３０２で表現される対応する候補相対レイアウトに従って分割する。
木構造３０２のそれぞれの葉ノードは、ページ３００上の対応するグラフィック・オブジェクト（ＧＯ１、ＧＯ２、ＧＯ３、ＧＯ４、ＧＯ５、ＧＯ６）に対応する。
木構造３０２のそれぞれの内部ノード（Ｈ、Ｖ）は、対応するページ３００上の水平境界線か、または垂直境界線のいずれか１つに対応する。
ページ３００の典型的な候補相対レイアウトと、対応する木構造３０２では、根Ｈノード１０４は、ページ３００の水平境界線３０６を表している。
左側内部Ｖノード３０８は、ページ３００の上部垂直境界線３１０を表し、また、右側内部Ｖノード３１２は、ページ３００の下部垂直境界線３１４を表している。
内部Ｈノード（３１６、３１８）はそれぞれ、ページ３００の水平境界線（３２２、３２０）を表している。
木構造３０２内の葉ノードの位置は、ページ３００上の対応するグラフィック・オブジェクト（ＧＯ１、ＧＯ２、ＧＯ３、ＧＯ４、ＧＯ５、ＧＯ６）の一意の相対的位置を指定する。
【００８２】
（Ｃ．候補レイアウト評価）
候補レイアウト評価は、候補レイアウトが実現可能であるかどうか判定するステップと、これらのグラフィック・オブジェクトに対して寸法を算出するステップと、レイアウト・スコアを算出するステップのうち１つまたは複数のステップを含むことがある。
レイアウト評価モジュール２６６は、いくつかの異なる評価方法を自由に処理できる。
どの方法が選択されるかは、レイアウトの評価の要求を出すモジュールの要件や、所望のレイアウト・スタイルによって決まることもある。
方法実行時間、計算機資源、メモリ制約などの他の要因も、レイアウト評価法の選択に影響を及ぼすこともある。
【００８３】
レイアウト評価法を選択するプロセスが、図２３Ａと図２３Ｂに示されている。
【００８４】
図２３Ａを参照すると、ブリック・レイアウト・スタイルが要望される（ブロック２７１）場合に、ページ上にレイアウトされるグラフィック・オブジェクトの組の中に固定エリアのグラフィック・オブジェクトが少なくとも１つあるかどうか判定が行われる（ブロック２７３）。
図示される実施形態では、ブリック・スタイルのレイアウトは、すべてのグラフィック・オブジェクトが可変エリアのものである場合にのみ、実現可能であると見なされる。
それゆえ、このレイアウトにおいて、固定エリアのグラフィック・オブジェクトが少なくとも１つある（ブロック２７３）場合には、レイアウト評価プロセスの実行が終了する（ブロック２７５）。
【００８５】
すべてのグラフィック・オブジェクトが、可変エリア・タイプのものであると仮定すると、隣り合ったグラフィック・オブジェクト間の間隔に明示的な制約を受けるグラフィック・オブジェクト・エリアの算出が、呼出しモジュールで必要とされるかどうか第２の判定が行われる（ブロック２７７）。
その応答が肯定的である場合には、以下で詳しく説明されるように、その候補木が実現可能なレイアウトを表現するかどうかについて、最初にチェックが行われる（ブロック２７９）。
このレイアウトが実現不可能である場合（ブロック２７９）には、呼出しモジュールにそのことを知らせて、この候補レイアウトを廃棄する（ブロック２８１）。
このレイアウトが実現可能である場合（ブロック２７９）には、呼出しモジュールにそのことを知らせて（必要である場合）、以下で詳しく説明される線形システム・ベースのエリア決定評価法を使用して、そのレイアウトを評価する（ブロック２８３）。
【００８６】
呼出しモジュールが、グラフィック・オブジェクト間の間隔に関連する制約への固守（adherence）を必要としない場合（ブロック２７７）には、２つの処理手順のいずれかが、レイアウト評価モジュール２６６により実行される。
第１の処理手順では、レイアウト評価モジュール２６６は、候補レイアウトが実現可能であることを確認して、線形システム・ベースのエリア決定評価プロセスを使用する（ブロック２８５）。
第２の処理手順では、レイアウト評価モジュール６６は、レイアウト実現可能性をテストしないで、バウンディング・ボックス・ベースのエリア決定評価プロセスを使用する（ブロック２８７）。
代表的な実施例では、第２の処理手順（ブロック２８７）は、第１の処理手順（ブロック２８５）よりも速い。
いくつかの実施形態では、以下のルールを使用して、レイアウトの評価に、第１の処理手順と第２の処理手順のどちらを使用すべきか選択する。
すなわち、呼出しモジュールが初期レイアウト作成モジュール６４である場合には、第２の処理手順（ブロック２８７）を使用する。
また、呼出しモジュールが最終レイアウト作成モジュール２７０である場合には、第１の処理手順（ブロック２８５）を使用する。
【００８７】
図２３Ｂを参照すると、ストリクト（strict）・エリア・レイアウト・スタイルが要望される場合（ブロック２８９）に、候補レイアウトに固定エリアのグラフィック・オブジェクトが少なくとも１つあること、あるいは、隣り合ったグラフィック・オブジェクト間の間隔に明示的な制約を受けるグラフィック・オブジェクト・エリアの算出が、呼出しモジュールで必要とされることが、真であるかどうか判定が行われる（ブロック２９１）。
【００８８】
候補レイアウトに固定エリアのグラフィック・オブジェクトが少なくとも１つあるか、あるいは、隣り合ったグラフィック・オブジェクト間の間隔に明示的な制約を受けるグラフィック・オブジェクト・エリアの算出が呼出しモジュールで必要とされる（ブロック２９１）場合には、その候補木が、以下で詳しく説明される実現可能なレイアウトを表現するかどうかについて、最初にチェックが行われる（ブロック２９３）。
このレイアウトが実現不可能である場合には、そのことを呼出しモジュールに知らせる。
このレイアウトが実現可能である場合には、そのことを呼出しモジュールに知らせて（必要である場合）、以下で詳しく説明されるパス・ベースのエリア決定評価プロセスを使用して、そのレイアウトを評価する（ブロック２９５）。
【００８９】
候補レイアウトに固定エリアのオブジェクトがまったくなく、かつ、隣り合ったグラフィック・オブジェクト間の間隔に明示的な制約を受けるグラフィック・オブジェクト・エリアの算出が、呼出しモジュールでは必要とされない場合（ブロック２９１）には、２つの利用可能な処理手順のいずれかに従うことができる。
第１の処理手順では、レイアウト評価モジュール６６は、候補レイアウトが実現可能であることを確認して、パス・ベースのエリア決定評価プロセスを使用する（ブロック２９７）。
第２の処理手順では、レイアウト評価モジュール６６は、レイアウト実現可能性をテストしないで、バウンディング・ボックス・ベースのエリア決定評価プロセスを使用する（ブロック２９９）。
代表的な実施例では、第２の処理手順（ブロック２９９）は、第１の処理手順（ブロック２９７）よりも速い。
いくつかの実施形態では、以下のルールを使用して、レイアウトの評価に、第１の処理手順と第２の処理手順のどちらを使用すべきか選択する。
すなわち、呼出しモジュールが初期レイアウト作成モジュール２６４である場合には、第２の処理手順（ブロック２９９）を使用する。
また、呼出しモジュールが最終レイアウト作成モジュール２７０である場合には、第１の処理手順（ブロック２９７）を使用する。
【００９０】
（１．候補木構造の実現可能性）
（ａ．概要）
いくつかの実施形態では、レイアウト評価モジュール６６は、現在の候補木構造が、実現可能な候補相対レイアウトを表現するかどうか、最初に判定する。
【００９１】
固定エリアのグラフィック・オブジェクトと、グラフィック・オブジェクト間の任意のユーザー指定およびシステム指定の固定間隔の考慮を含め、構成グラフィック・オブジェクトが、ページ上で利用可能なスペース内に収まる場合に、候補相対レイアウトが実現可能である。
上述の実施形態では、ページ上に固定エリアのグラフィック・オブジェクトがまったくなく、かつ、隣り合ったグラフィック・オブジェクト間の間隔に制約がない場合には、どんなレイアウトも実現可能である。
したがって、図２３Ａと図２３Ｂから推定され得るように、選択エリア決定モジュールが、パス・ベースのエリア決定モジュールか、線形システム・ベースのエリア決定モジュールのいずれかである場合にのみ、レイアウト実現可能性が考慮される。
選択エリア決定モジュールが、バウンディング・ボックス・ベースのエリア決定である場合には、レイアウト実現可能性は考慮されない。
【００９２】
（ｂ．候補木構造の実現可能性を判定する）
図２４は、レイアウト評価モジュール６６が候補木構造の実現可能性を判定するときに用いる一実施形態を示している。
【００９３】
レイアウト評価モジュール６６は、図９〜図１０Ｊに関連して、以下で説明されるパス生成プロセスにより、候補木構造を通るパスＰｉを生成する（図２４のブロック４１０）。
【００９４】
レイアウト評価モジュール６６は、それぞれのパスＰｉに対してパス長さＬ（Ｐｉ）を計算する（図２４のブロック４１２）。
パスＰｉが垂直である場合には、その長さは次式の通りである。
【００９５】
【数２】
2010532042.tif 000004
【００９６】
グラフィック・オブジェクトの高さ（ＨGO）は、次式のように書き表すことができる。
【００９７】
【数３】
2010532042.tif 000005
【００９８】
ここで、Ａは、グラフィック・オブジェクトのエリア（面積）であり、ａは、その高さをその幅で除算した比率として定義される縦横比であり、さらに、Ｑは、その面積の平方根である。
それゆえ、Ｐｉが垂直パスである場合には、その長さは、次式のように書く表すことができる。
【００９９】
【数４】
2010532042.tif 000006
【０１００】
ここで、Ｋｉは、式（２）中の最初の２つの項の合計（すなわち、パスＰｉに沿ったすべての一定距離）であり、Ｑｉ，ｊは、パスＰｉ上のｊ番目の可変エリアのオブジェクトの面積の平方根であり、さらに、ａｉ，ｊは、パスＰｉ上のｊ番目の可変エリアのオブジェクトの縦横比である。
上記総和項は、パスＰｉ上の可変エリアのグラフィック・オブジェクトの高さの合計に対応することに留意されたい。
【０１０１】
同様な導出から、水平パスＰｉの長さは、次式のように書く表すことができる。
【０１０２】
【数５】
2010532042.tif 000007
【０１０３】
ここで、Ｋｉは、パスＰｉに沿って、固定エリアのグラフィック・オブジェクトの幅と水平の一定距離との合計である。
【０１０４】
レイアウト評価モジュール２６６は、これらのパスの一定距離の項（Ｋｉ）を、対応する利用可能なページ・スペースの寸法と比較する（図２４のブロック４１４）。
【０１０５】
それぞれの一定距離の項が、利用可能なページ・スペース内に収まる（すなわち、それぞれのパスＰｉに対して、Ｋｉ≦対応するページ・スペースの寸法）場合には（図２４のブロック４１６）、レイアウト評価モジュール２６６は、このレイアウトを、実現可能であると称する（図２４のブロック４１８）。
そうでなければ、レイアウト評価モジュール２６６は、このレイアウトを、実現不可能であると称する（図２４のブロック４２０）。
【０１０６】
（ｃ．パスを生成する）
（ｉ．パス生成法の概要）
図２５は、ページ上のグラフィック・オブジェクトの相対レイアウトを通る一組のパスを生成する方法の一実施形態の流れ図を示している。
【０１０７】
簡単に言えば、図２５のパス生成法は、相対レイアウトに対応する木構造内のそれぞれのノードに対して、１回実行される。
すなわち、それぞれのノードは１つずつ順番に「現在ノード」となり、それに関して、パス生成法の対応するインスタンスがブロック４２８から始まる。
このパス生成法のそれぞれのインスタンスの出力は、現在ノードに対応する一組のパスである。
現在ノードが終端ノード（すなわち、葉ノード）であるときには、ブロック４３２において、現在ノードに対して、２つの新たなパスが確立される。
現在ノードが内部ノードであるときには、パス生成法の現在インスタンスは、２つの段階に分けられる。
第１の段階では、ブロック４３４とブロック４３６において、現在ノードの左側子ノードと右側子ノードとに対して、パス生成法の対応するインスタンスが実行される。
第２の段階では、ブロック４３８〜ブロック４５０において、左側子ノード用のパスと右側子ノード用のパスを組み合わせて、現在ノードのパスを形成する。
ノードが根ノードであるときには、パス生成法の対応するインスタンスから得られるパスは、処理されている相対レイアウトに対する一組のパス全部である。
【０１０８】
（ｉｉ．パス生成法の詳細な説明）
初めに、パス生成法は、ブロック４２８にて、所与の候補相対レイアウトの根ノードから始まる。
パス生成法は、内部ノードと終端ノードのそれぞれに対してパスを再帰的に決定して、現在の候補相対レイアウトを通る一組のパス全部を得る。
この再帰的プロセスにおいて、このプロセスに現在ノードを入力して、この現在ノードが終端ノードであるかどうか、ブロック４３０において、決定がなされる。
【０１０９】
この現在ノードが終端ノードである場合には、終端ノードに対応づけられるグラフィック・オブジェクトを１回のステップで通る水平パス（例えば、左から右へ）と、このグラフィック・オブジェクトを１回のステップで通る垂直パス（例えば、上から下へ）という２つの新たなパスが、ブロック４３２においてスタートする。
ブロック４３２の後で、現在の終端ノードに対応づけられるパス生成法のインスタンスが完結する。
【０１１０】
現在ノードが終端ノードでない場合には（ブロック４３０）、ブロック４３４とブロック４３６は、パス生成法の対応するインスタンスで、ノード４２８から始まって処理される現在ノードとして、現在内部ノードの２つの子ノード（すなわち、左側子ノードと右側子ノード）を投入する。
現在親ノードに対して実行中のパス生成法のインスタンスは、子ノードに対してパス生成法のインスタンスを実行している間は、保留状態にある。
図示される実施形態では、右側子ノードに対するパス生成法のインスタンスは、左側子ノードに対するパス生成法のインスタンスが終了した後で実行される。
左側子ノードと右側子ノードに対して実行されるパス生成法のインスタンスの結果は、２組のパスである。
【０１１１】
ブロック４３７〜ブロック４５０では、これら２つの子ノードに対して決定されるパスが組み合わされる。
ブロック４３７は、現在ノードに対してパス・リストを確立する。
ブロック４３８は、現在内部ノードが水平境界線を表しているか、垂直境界線を表しているかどうか判定する。
現在内部ノードが水平境界線を表している場合、現在内部ノードは、その子の水平パスを継承（inherit）して（ブロック４４０、ブロック４４２）、その子の垂直パスを組み合わせる（ブロック４４４）。
特に、現在内部ノードが水平境界線を表している場合には、現在内部ノードは、その左側の子のＮＬＨ個の水平パスのそれぞれ（ブロック４４０）と、その右側の子のＮＲＨ個の水平パスのそれぞれ（ブロック４４２）を継承する。
ブロック４４４において、現在内部ノードは、左側の子のＮＬＶ個の垂直パスのそれぞれを１つずつ順番に右側の子のＮＲＶ個の垂直パスのそれぞれに連結して、現在ノードの（ＮＬＶ＊ＮＲＶ）個の垂直パスを形成することで、新たな一組の垂直パスを得る。
パスの総数は、ＮＬＨ＋ＮＲＨ＋（ＮＬＶ×ＮＲＶ）である。
【０１１２】
現在内部ノードが垂直境界線を表している場合、現在内部ノードは、その子の垂直パスを継承して（ブロック４４６、ブロック４４８）、その子の水平パスを組み合わせる（ブロック４５０）。
特に、現在内部ノードが垂直境界線を表している場合には、現在内部ノードは、その左側の子のＮＬＶ個の垂直パスのそれぞれ（ブロック４４６）と、その右側の子のＮＲＶ個の垂直パスのそれぞれ（ブロック４４８）を継承する。
ブロック４５０において、現在内部ノードは、左側の子のＮＬＨ個の水平パスのそれぞれを１つずつ順番に右側の子のＮＲＨ個の水平パスのそれぞれに連結して、現在ノードの（ＮＬＨ＊ＮＲＨ）個の水平パスを形成することで、新たな一組の水平パスを得る。
したがって、パスの数は、ＮＬＶ＋ＮＲＶ＋（ＮＬＨ×ＮＲＨ）である。
【０１１３】
ノードに対して実行されているパス生成法の所与のインスタンスが終了すると（例えば、ブロック４３２、ブロック４４４、ブロック４５０の後）、プロセス制御は、その所与のインスタンスを呼び出したインスタンスに戻る。
根ノードに対して起動されたインスタンスが終了すると、この根ノードに対応づけられるパスの組は、相対レイアウトに対する全パスの組となり、パス生成法が終わる。
【０１１４】
（ｉｉｉ．典型的な候補相対レイアウトへのパス生成法の適用）
図２６Ａ〜図２６Ｊは、典型的な相対レイアウト４５３に対応する木構造４５２のそれぞれのノードに対して、図２５のパス生成法により生成されるパスを示している。
【０１１５】
図２６Ａは、上記パス生成法が始まる前の木構造４５２と対応する候補相対レイアウト４５３とを示している。
候補相対レイアウト４５２における水平境界線と垂直境界線は、破線として示されている。
【０１１６】
図２６Ｂ〜図２６Ｊのそれぞれは、図面中に丸で囲まれている対応する現在ノードに対してパス生成法のインスタンスが終了するまで生成されてきたパスが、対応するノード位置に示されている木構造４５２の対応するバージョン（変形例）を示している。
対応するパスは、相対レイアウト４５３に重ねられた矢印として示されている。
この木構造では、これらのパスはそれぞれ、対応するグラフィック・オブジェクトのリストに先行する矢印で表されている。
グラフィック・オブジェクトのリストに先行する右向き矢印は、これらのグラフィック・オブジェクトを通る水平パスを示している。
グラフィック・オブジェクトのリストに先行する下向き矢印は、これらのグラフィック・オブジェクトを通る垂直パスを示している。
例えば、「→ＧＯ４」は、グラフィック・オブジェクトＧＯ４を通る水平パスを示し、また、「→ＧＯ４、ＧＯ５」は、グラフィック・オブジェクトＧＯ４とグラフィック・オブジェクトＧＯ５を通る水平パスを示している。
【０１１７】
図２６Ｂは、図２５のブロック４３２において生成されて、グラフィック・オブジェクトＧＯ１に対応する終端ノード４５５を通る水平パスと垂直パスを示している。
【０１１８】
図２６Ｃは、図２５のブロック４３２において生成されて、グラフィック・オブジェクトＧＯ２に対応する終端ノード４５７を通る水平パスと垂直パスを示している。
図２６Ｄは、図２５のブロック４３２において生成されて、グラフィック・オブジェクトＧＯ３に対応する終端ノード４５９を通る水平パスと垂直パスを示している。
図２６Ｅは、垂直親ノード４６１に対して図２５のブロック４４０〜ブロック４４４において生成された、ＧＯ２とＧＯ３を通るパスの組合せを垂直親ノード４６１の所に示している。
【０１１９】
図２６Ｆは、図２５のブロック４３２において生成されて、グラフィック・オブジェクトＧＯ４に対応する終端ノード４６３を通る水平パスと垂直パスを示している。
図２６Ｇは、図２５のブロック４３２において生成されて、グラフィック・オブジェクトＧＯ５に対応する終端ノード４６５を通る水平パスと垂直パスを示している。
図２６Ｈは、垂直親ノード４６７に対して図２５のブロック４４０〜ブロック４４４において生成された、ＧＯ２とＧＯ３を通るパスの組合せを垂直親ノード４６７の所に示している。
【０１２０】
図２６Ｉは、水平親ノード４６９に対して図２５のブロック４４６〜ブロック４５０において生成された、垂直ノード４６１と垂直ノード４６７を通るパスの組合せを水平親ノード４６９の所に示している。
【０１２１】
図２６Ｊは、候補相対レイアウト４５３を通る全パスの組、すなわち、垂直根ノード４７１に対して図２５のブロック４４６〜ブロック４５０において生成された垂直ノード４６９と終端ノード４５５とを通るパスの組合せに対応するものを、垂直根ノード４７１の所に示している。
【０１２２】
（２．候補木構造を評価する）
本出願のこのセクションに述べられる実施形態では、候補相対レイアウトを評価するのに用いられるスコアは、ページ上でグラフィック・オブジェクトが占有するエリアの測度によって決まる。
【０１２３】
（ａ．グラフィック・オブジェクトのエリアを決定する）
レイアウト評価モジュール２６６は、バウンディング・ボックス・ベースの決定プロセス、パス・ベースの決定プロセス、または線形システム・ベースの決定プロセスに基づいて、候補相対レイアウトの所与のインスタンスで指定されるグラフィック・オブジェクトで占有されたエリアを計算する。
【０１２４】
（ｉ．グラフィック・オブジェクト・エリアのバウンディング・ボックス・ベースの決定）
図示される実施形態では、バウンディング・ボックス決定プロセスの目的は、所与の木構造内のそれぞれの内部ノードに対して、縦横比および公称サイズ値を算出することである。
それぞれのバウンディング・ボックスは、それが包囲するボックスで求められる。
【０１２５】
以下でさらに詳しく説明されるように、バウンディング・ボックスは、グラフィック・オブジェクトの公称サイズを用いて算出される。
上述のように、これらの公称サイズは、現在ページのページ・レジスタに記録されるものと想定される。
いくつかの実施例では、バウンディング・ボックス特徴付け（characterization）プロセスは、図２７に示されるように、葉ノードから始まって、深さ優先探索（depth-first search）の順に根ノードに向けて進む。
【０１２６】
任意の内部ノードの縦横比および公称サイズの公式が以下に与えられる。
一般に、縦横比ａおよび公称サイズｅを持つどんな画像バウンディング・ボックスでも、√ａｅおよび√ｅ／ａの量は、それぞれ、その画像バウンディング・ボックスの公称高さと公称幅である。
任意の内部ノードに対する縦横比ａおよび公称サイズｅは、その２つの子の縦横比および公称サイズの関数である。
以下の式では、ａｒおよびｅｒは、右側子ノードの縦横比および公称サイズであり、また、ａｌおよびｅｌは、左側子ノードの縦横比および公称サイズである。
したがって、この右側子ノードと左側子ノードとが並んで配置される場合には、それらの子ノードを包囲するバウンディング・ボックスの縦横比および公称サイズは、次式となる。
【０１２７】
【数６】
2010532042.tif 000008
【０１２８】
【数７】
2010532042.tif 000009
【０１２９】
ここで、
【０１３０】
【数８】
2010532042.tif 000010
【０１３１】
式（６）中の縦横比は、大きい方の公称高さを上記２つの公称幅の合計で除算した比率であり、また、式（７）中の公称サイズは、大きい方の公称高さと上記２つの公称幅の合計との積である。
式（８）中の最大値を求めることにより、２つの子ノード・ボックスのどちらが名目的に高いか決定され、それゆえ、親ノード・ボックスの高さが制御される。
【０１３２】
これら２つの子ノードが、互いに上下に配置されるボックスを表現する場合には、それらの子ノードを包囲するバウンディング・ボックスの縦横比および公称サイズは、次式となる。
【０１３３】
【数９】
2010532042.tif 000011
【０１３４】
【数１０】
2010532042.tif 000012
【０１３５】
ここで、
【０１３６】
【数１１】
2010532042.tif 000013
【０１３７】
この場合、式（１１）により、２つの子ノード・ボックスのどちらが名目的に広いか決定され、それゆえ、親ノード・ボックスの幅が制御される。
【０１３８】
根ノードのバウンディング・ボックスは、対応する木構造で指定されたページのレイアウト全体の形状および公称サイズを表す。
根ノードのバウンディング・ボックスは、ここでは、「主バウンディング・ボックス」と呼ばれる。
【０１３９】
主バウンディング・ボックスの縦横比および公称サイズが既知であるときには、グラフィック・オブジェクトｉに対するバウンディング・ボックス・ベースのエリア（面積）Ａｉは、次式のように算出される。
【０１４０】
【数１２】
2010532042.tif 000014
【０１４１】
ここで、ｅｉおよびｅｐｂｂはそれぞれ、グラフィック・オブジェクトｉの公称サイズおよび主バウンディング・ボックスの公称サイズであり、また、Ａｐｂｂは、次式のように算出される主バウンディング・ボックスの面積であり、
【０１４２】
【数１３】
2010532042.tif 000015
【０１４３】
ここで、Ａpageは、使用できるページ・スペースの面積である。
【０１４４】
図２７は、レイアウト評価モジュール２６６が、木構造のノード用のバウンディング・ボックスの相対的な高さおよび幅の寸法を計算するときに用いる再帰的プロセスの一実施形態の流れ図を示している。
【０１４５】
このプロセスは、現在ノードとして根ノードから始まる。
現在ノードが終端ノードであるかどうか決定を下す（図２７のブロック４８０）。
現在ノードが終端ノードである場合には、関連するグラフィック・オブジェクトの公称高さおよび公称幅を持つバウンディング・ボックスが確立される（図２７のブロック４８２）。
現在ノードが終端ノードでない場合には、現在ノードの２つの子ノード（すなわち、左側子ノードと右側子ノード）が、同一再帰的プロセスに投入される（図２７のブロック４８４、ブロック４８６）。
これら２つの子のバウンディング・ボックスを組み合わせて、以下のように現在ノード用のバウンディング・ボックスを形成する。
レイアウト評価モジュール２６６は、現在ノードが水平境界線であるか、垂直境界線であるか判定する（図２７のブロック４８８）。
現在ノードが水平境界線を表している場合には、このバウンディング・ボックスの公称幅が、これら２つの子のバウンディング・ボックスの広い方の公称幅にセットされ（図２７のブロック４９０）、また、このバウンディング・ボックスの公称高さが、これら２つの子のバウンディング・ボックスの公称高さの合計にセットされる。
現在ノードが垂直境界線を表している場合には（図２７のブロック４８８）、このバウンディング・ボックスの公称高さが、これら２つの子のバウンディング・ボックスの高い方の公称高さにセットされ（図２７のブロック４９４）、また、このバウンディング・ボックスの公称幅が、これら２つの子のバウンディング・ボックスの公称幅の合計にセットされる。
このプロセスは、根ノード用のバウンディング・ボックスが算出されるまで続く。
【０１４６】
（ｉｉ．グラフィック・オブジェクト・エリアのパス・ベースの決定）
ストリクト・エリア・スタイルのレイアウトでは、それぞれの可変エリアのグラフィック・アセンブリ（集成体）は、変数ｅで表される割当て（assigned）公称サイズを持っている。
構成単一要素グラフィック・オブジェクト（例えば、ビデオからの一連のキーフレーム）を２つ以上持つ多要素グラフィック・オブジェクトに関連して、単一集計公称サイズは、グラフィック・オブジェクト全体に割り当てられ、また、この多要素グラフィック・オブジェクト中の個々のグラフィック・オブジェクトの公称サイズは、上記集計公称サイズをこの多要素グラフィック・オブジェクト中のグラフィック・オブジェクトの数で除算したものに等しいようにセットされる。
このセクションの残りの部分では、パスＰｉ上のそれぞれのグラフィック・オブジェクトｊは、正の公称サイズｅｊを持つ単一要素グラフィック・オブジェクトであると、想定される。
公称サイズは実際のエリア（面積）に比例するから、上で定義される変数Ｑを一般化して、次式のように公称サイズ（絶対エリアではなく）の平方根を反映させることができる。
【０１４７】
【数１４】
2010532042.tif 000016
【０１４８】
ここで、ｇは、ｇ２に公称サイズを乗算したものが絶対測定可能エリア（例えば、平方インチ）であるような正のスカラーである。
Ｑを√ｅで除算した比率は、すべての可変エリアのグラフィック・オブジェクトに共通の定数であり、したがって、ｇと同一の値が、ページ上のすべての可変エリアのグラフィック・オブジェクトに使用される。
したがって、上記の式（４）と式（５）において、Ｑにｇ・√ｅを代入する場合、ｇをこれらの総和項から引っ張り出して、次式を得ることができる。
【０１４９】
【数１５】
2010532042.tif 000017
【０１５０】
【数１６】
2010532042.tif 000018
【０１５１】
ここで、ｅｉ，ｊは、パスＰｉ上のｊ番目の可変エリアのグラフィック・オブジェクトの公称サイズである。
【０１５２】
パスＰｉが垂直パスであり、また、ページ上の利用可能なエリアが高さＨPAGEを持つ場合には、次のｇｉの方程式を解いて、この利用可能なエリアが高い限り、Ｐｉがぴったり合う値が与えられる。
【０１５３】
【数１７】
2010532042.tif 000019
【０１５４】
同様に、パスＰｉが水平パスであり、また、利用可能なエリアが幅ＷPAGEを持つ場合には、次のｇｉの方程式を解いて、この利用可能なエリアの全幅にわたって、このパスがぴったり合う値が与えられる。
【０１５５】
【数１８】
2010532042.tif 000020
【０１５６】
一実施形態では、可変エリアのグラフィック・オブジェクト用のエリアをできるだけ広くするが、それでも、Ｐｉが垂直パスであるか、水平パスであるかどうかにより、方程式（１７）か、方程式（１８）のいずれかを用いて（それぞれのＰｉに対して）ｇｉを求めることで、すべてのグラフィック・オブジェクトが、ページの利用可能なエリアに完全に入れるようにしている。
このレイアウトは、上で説明されるように、実現可能であると前もって判定されているため、ｇｉのそれぞれの解は正となる。
次式のように、ｇ＊が、すべてのパスの中で最小の解であると定められる場合には、
【０１５７】
【数１９】
2010532042.tif 000021
【０１５８】
ｊ番目の可変エリアのグラフィック・オブジェクトのエリア（面積）Ａｊは、次式のように算出される。
【０１５９】
【数２０】
2010532042.tif 000022
【０１６０】
ここで、ｅｊは、ｊ番目の可変エリアのグラフィック・オブジェクトに割り当てられた公称サイズである。
【０１６１】
（ｉｉｉ．グラフィック・オブジェクト・エリアの線形システム・ベースの決定）
ブリック・スタイルのレイアウトでは、グラフィック要素のエリアは、最初にＱの値を算出することで決定される。
Ｑの値が既知であると、これらの値を二乗して、絶対測定可能なエリア（例えば、平方インチ）を算出できる。
（Ｉ）グラフィック要素で占有されるエリアの高さは、ページ上の利用可能なエリアの高さに等しいことを強いられる、（ＩＩ）グラフィック要素で占有されるエリアの幅は、ページ上の利用可能なエリアの幅に等しいことを強いられるという２つの仮説シナリオに対して、Ｑの値が算出される。
たいていの場合、シナリオ（Ｉ）とシナリオ（ＩＩ）の一方だけが、実現可能な解を与えることになる。なぜなら、他方のシナリオでは、強いられない寸法が、上記の利用可能なスペースよりも大きくなるからである。
実現可能な解を与えるシナリオを選択して、最終の組のグラフィック要素のエリアを作り出す。
【０１６２】
シナリオ（Ｉ）またはシナリオ（ＩＩ）のいずれかにおいて、Ｎ個の未知数を持つ一次連立方程式の解として、Ｑの値が算出される。ここで、Ｎは、グラフィック要素の数である。
上記方程式のうちのＮ−１個のそれぞれは、完全な木構造の内部ノードから得られる。なぜなら、Ｎ個のグラフィック要素を収める木には、ちょうど（Ｎ−１）個の内部ノードがあるからである。
【０１６３】
このエリアの垂直の境界線またはカット（切れ目）を表現する内部ノードでは、最初に２つの垂直パス（その２つの子それぞれから１つのパス）を得て、これらの垂直パスの長さを等しくセットすることにより、対応する方程式が導き出される。
上記の式（１５）を参照して、左側の子からの垂直パスをＰＬと表し、また、右側の子からの垂直パスをＰＲと表すと、対応する式は、次式によって与えられる。
【０１６４】
【数２１】
2010532042.tif 000023
【０１６５】
ここで、変数ｊは、ＰＲに沿ったグラフィック・オブジェクトを指示し、また、ｋは、ＰＬに沿ったグラフィック・オブジェクトを指示する。
式（２１）を配列し直すと、次式が与えられる。
【０１６６】
【数２２】
2010532042.tif 000024
【０１６７】
このエリアの水平の境界線またはカット（切れ目）を表現する内部ノードでも、上記の状況と類似している。
２つの水平パスを得て、これらの水平パスの長さを等しくセットすることにより、次式が与えられる。
【０１６８】
【数２３】
2010532042.tif 000025
【０１６９】
それぞれの内部ノードに対して、式（２２）または式（２３）の形式の方程式を構築することで、Ｎ個の未知数に対して、Ｎ−１個の方程式が得られる。
【０１７０】
シナリオＩでは、根ノードからの任意の垂直パスの長さを、利用可能なエリアの高さに等しくセットすることで、Ｎ番目の方程式が得られる。
シナリオＩＩでは、根ノードからの任意の水平パスの長さを、利用可能なエリアの幅に等しくセットすることで、Ｎ番目の方程式が得られる。
【０１７１】
シナリオＩおよびシナリオＩＩの双方の場合、Ｎ個の方程式は、行列・ベクトル形式（Ａｘ＝ｂ）で書き表される。
この行列は、グラフィック要素縦横比のゼロおよび正並びに負の平方根と、グラフィック要素縦横比の平方根の正および負の逆数（inverse）とのみを含む。
ベクトルｘのＮ個の要素は、Ｑの変数である。
ベクトルｂのＮ個の要素の中で、（Ｎ−１）個が、式（２１）または式（２２）のいずれかの式の右辺として算出される。その他は、利用可能なエリアの高さ（シナリオＩ）または幅（シナリオＩＩ）（対応する行を得るのに用いられたパスに沿った一定距離を引く）に等しい。
逆数（inverse）（Ａ）＊ｂを算出すれば、Ｑ値のベクトルが与えられる。
【０１７２】
（ｂ．木構造を採点する）
いくつかの実施形態では、初期レイアウト作成モジュール６４は、最高の適性またはスコアを持つものを特定することで、候補レイアウトを選択する。
これらのスコアは、上記のセクションＩＩＩのＢ．２項に述べられるタイプの採点、評価、または適格の機能を用いて、レイアウト評価モジュール２６６で算出される。
この採点、評価、または適格の機能は、グラフィック・オブジェクトのサイズがグラフィック・オブジェクトに割り当てられた公称サイズに近づくような最終レイアウトの作成を促進する。
いくつかの実施形態では、レイアウト評価モジュール２６６は、候補レイアウトにおけるグラフィック・オブジェクトの実際のレンダリング・サイズが対応する目標レンダリング・サイズと一致する度合いに基づいて、候補レイアウトごとに、対応するレイアウト・スコアを計算する。
採点の機能は一般に、所与のレイアウトにおけるグラフィック・オブジェクトの実際のサイズがこれらのグラフィック・オブジェクトに割り当てられた公称サイズにどれくらい近いかの指標となる測度を、取り入れている。
これらの実施形態の一部では、レイアウト評価モジュール２６６は、対応する目標レンダリング・サイズに対する実際のレンダリング・サイズの比率に基づいて、候補レイアウトごとに、これらのグラフィック・オブジェクトのそれぞれに対して、対応するグラフィック・オブジェクト・スコアを計算する。
レイアウト評価モジュール２６６は、候補レイアウトごとに、それぞれのグラフィック・オブジェクト・スコアから、対応するレイアウト・スコアを計算する。
【０１７３】
いくつかの実施形態では、レイアウト評価モジュール２６６で使用される採点、評価、または適格の機能は、上記のセクションＩＩＩのＢ．２項に述べられる擬似コードで定められる目標レイアウト・スコア機能に対応する。
【０１７４】
いくつかの実施形態では、レイアウト評価モジュール２６６で使用される採点、評価、または適格の機能は、上記のセクションＩＩＩのＢ．２項に述べられる擬似コードで定められる目標レイアウト・スコア機能を、１つまたは複数の他の測度と組み合わせる。
適格または採点の機能に含まれることも含まれないこともある他の測度は、カバー範囲（すなわち、グラフィック・オブジェクトで占有されるページの一部）と一貫性（consistency）（すなわち、ページ上のグラフィック・オブジェクトで占有されるエリアのむら（variation））を含むが、ただし、それらには限定されない。
【０１７５】
例えば、ストリクト・エリア・レイアウト・スタイルを要望する実施形態では、レイアウト評価モジュール２６６は、上記のセクションＩＩＩのＢ．２項に述べられる擬似コードで定められる目標レイアウト・スコア機能をカバー範囲と組み合わせるレイアウト・スコアを算出する。
いくつかの実施形態では、カバー範囲は、ページ上のグラフィック・オブジェクト・エリアの合計として算出される。
これらのエリアは、パス・ベースのエリア決定法によるか、あるいはバウンディング・ボックス・ベースのエリア決定法により、算出された場合もある。
【０１７６】
ブリック・レイアウト・スタイルを要望する実施形態では、レイアウト・スコアは、上記のセクションＩＩＩのＢ．２項に述べられる擬似コードで定められる目標レイアウト・スコア機能を、カバー範囲および一貫性の双方と組み合わせる。
これらの実施形態の一部では、この組み合わされたレイアウト・スコア（Score）は、式（２４）により計算される。
【０１７７】
【数２４】
2010532042.tif 000026
【０１７８】
ａ１、ａ２、ａ３のパラメータは、経験的に決定された重み係数である。
変数αは、ページ上の利用可能なエリアの縦横比が主バウンディング・ボックスの縦横比とどれくらいよく一致するかの尺度となる。
変数υは、一貫性の尺度となる。
いくつかの実施形態では、変数αおよび変数υは、それぞれ、０と１との範囲内の値を取り、その場合、０は、低いカバー範囲および一貫性に対応し、また、１は、高いカバー範囲および一貫性に対応する。
これらの実施形態では、変数αは、次式のように算出される。
【０１７９】
【数２５】
2010532042.tif 000027
【０１８０】
ここで、page_aspectは、ページ上の利用可能なエリアの縦横比であり、また、pbb_aspectは、主バウンディング・ボックス（すなわち、根ノードに対応づけられるバウンディング・ボックス）の縦横比である。
変数υは、次式のように算出される。
【０１８１】
【数２６】
2010532042.tif 000028
【０１８２】
式（２６）では、グラフィック・オブジェクト・エリアは、線形システム・ベースのエリア決定法によるか、あるいはバウンディング・ボックス・ベースのエリア決定法により、算出されることがある。
これらの実施形態では、一貫性の測度υは、最小グラフィック・オブジェクト・エリアを最大グラフィック・オブジェクト・エリアで除算したものであると定義される。
【０１８３】
他の実施形態は、ブリック・スタイルのレイアウトに対して、異なる採点機能を用いることがある。
例えば、式（２４）により算出されたスコアは、所定のしきい値よりも低いαおよび／またはυの値に対して減点（penalize）される。
いくつかの実施例では、αおよび／またはυの値は、グラフィック・オブジェクト間のどんなスペースも考慮入れることがある。
【０１８４】
（Ｖ．ページ上にグラフィック・オブジェクトの初期配置を作成する）
（Ａ．グラフィック・オブジェクトの初期配置を作成するプロセスの概要）
図２８は、ページ上にグラフィック・オブジェクト２７０の初期配置２８０を形成する２分木構造が初期レイアウト作成モジュール２６４で生成されるときに用いる方法の一実施形態の流れ図を示している。
【０１８５】
初期レイアウト作成モジュール２６４は、一組のグラフィック・オブジェクトから選択された第１のグラフィック・オブジェクトに対して、ページのうちの選択された１つに相対的位置を定める第１のノードを含む現在木構造を起動する（図２８のブロック５０１）。
【０１８６】
初期レイアウト作成モジュール２６４は、現在木構造と、上記組のグラフィック・オブジェクトから選択された別のグラフィック・オブジェクトに対して上記選択ページ上の対応する相対的位置を定める対応するノードとをそれぞれが含む候補木構造を生成する（図２８のブロック５０３）。
初期レイアウト作成モジュール２６４は、現在木構造に１つのグラフィック・オブジェクトを追加することで、それぞれの候補木構造を生成する。
【０１８７】
（以下で説明される拡張プロセスを用いて）現在木構造内の多要素グラフィック・オブジェクトが拡張された後で、初期レイアウト作成モジュール２６４は、それらの候補木構造に対して、対応する初期サイズ寸法に少なくとも一部、基づいて、対応する実現可能性テスト結果とスコアを得る（図２８のブロック５０７）。
これらのスコアおよび実現可能性テスト結果は、レイアウト評価モジュール２６６から得られる。
レイアウト評価モジュール２６６により実現不可能とみなされる候補木構造があれば、それは考慮の対象から排除される。
【０１８８】
初期レイアウト作成モジュール２６４は、算出されたスコアに基づいて、これらの候補木構造の１つを現在木構造として選択する（図２８のブロック５０９）。
【０１８９】
初期レイアウト作成モジュール２６４は、現在木構造内の対応するノードにより、上記組のグラフィック・オブジェクトすべてに対して、ページ上の相対的位置が定められるまで、作成するプロセス（図２８のブロック５０３）、得るプロセス（図２８のブロック５０７）、選択するプロセス（図２８のブロック５０９）を繰り返す（図２８のブロック５１１）。
【０１９０】
図２８のプロセスは、グラフィック・オブジェクトがレイアウトされる１つまたは複数のページのそれぞれに対して、繰り返される。
【０１９１】
図２８に定められるプロセスでは、木構造生成プロセスは、ただ１つのグラフィック・オブジェクトから始まり、ページに割り当てられるグラフィック・オブジェクトのすべてが追加されるまで、追加のグラフィック・オブジェクトが１つずつ木構造に追加される。
ページに割り当てられるグラフィック・オブジェクトの総数がＭである場合には、このページに対するレイアウトは、次式のように、増大する一連の２分木内の最後のものに対応する。
【０１９２】
【数２７】
2010532042.tif 000029
【０１９３】
ここで、ｐ≧１の場合のＴ（ｐ）は、ｐ個の終端ノードを持つ木を表す。
中間の木｛Ｔ｛ｐ｝：１≦ｐ≦Ｎ−１｝のそれぞれは、発展性ある（viable）レイアウトを作成する。
【０１９４】
図２９Ａ〜図２９Ｃは、木構造生成プロセスの異なる段階において、あるページの異なる区画と、対応する階層木構造とを示しており、そこでは、括弧に入れた数字は、対応するグラフィック・オブジェクト（Ａ、Ｂ、Ｃ、Ｄ）に割り当てられた公称サイズである。
この木構造内のそれぞれのノードは、ページのレイアウトにおけるバウンディング・ボックスに対応づけられる。
それぞれの内部ノードは、その２つの子ノードのボックスの周りのバウンディング・ボックスに対応づけられ、また、それぞれの葉ノードは、対応するグラフィック・オブジェクトが配置されるセルに対応づけられる。
【０１９５】
前のレイアウトに新たなセルを導くことで、木構造に、それぞれの新たなグラフィック・オブジェクトが追加される。
したがって、部分木構造５２４を図２９Ｂに示される新たな内部Ｈノード５２６に代えることで、図２９Ａに示される部分木構造５２４にグラフィック・オブジェクトＣが追加される。
この新たな内部Ｈノード５２６は、新たなセルＣ（２）に対応する新たな葉ノード５２８と、代えられた部分木５２４との親となる。
同様に、部分木構造５２８を図２９Ｃに示される新たな内部Ｖノード５３０に代えることで、図２９Ｂに示される部分木構造５２８にグラフィック・オブジェクトＤが追加される。
この新たな内部Ｖノード５３０は、新たなセルＤ（３）に対応する新たな葉ノード５３２と、代えられた部分木５２８との親となる。
図２９Ａ〜図２９Ｃに示される例では、代えられる選択部分木（５２４と５２８）は、たまたま葉ノードであった。しかしながら、一般に、内部ノードに根づいている部分木も含め、どんな部分木も選択されたかもしれない。
部分木は、部分木の根を、そこから出るすべてのノードと合わせたものと称されるノードとして定義される。
部分木の根が内部ノードである場合には、その部分木は、内部ノードと、その子である終端ノードとを両方とも含む。
【０１９６】
以下で詳しく説明されるように、初期レイアウト作成モジュール２６４は、利用可能な新たなセル位置ごとに、新たなグラフィック・オブジェクトの可能なあらゆる表示に対応する候補相対レイアウトのコレクションを評価することで、前のレイアウトに、どのセルが取り入れられるか選択する。
しかしながら、これらの候補相対レイアウトをそれぞれ評価する前に、多要素グラフィック・オブジェクトの候補相対レイアウトに対応する粗なグラフィック・オブジェクト木構造を拡張して（あるいは、変形して）、これらのグラフィック・オブジェクトの個々の構成グラフィック・オブジェクトに葉が対応するような改善された（または、完全な）木構造を形成する。
【０１９７】
典型的な一例示において、図３０Ａは、グラフィック・オブジェクト５４０（ＧＯ１）およびその対応する木構造５４２の一表示を示している。
図３０Ｂは、グラフィック・オブジェクト５４４（ＧＯ４）およびその対応する木構造５４６の一表示を示している。
図３０Ｃは、水平根ノードと、図２９Ａおよび図２９Ｂにそれぞれ示されるグラフィック・オブジェクト表示（５４０、５４４）に対応する２つの終端ノードとから成る粗な木構造３４８を示している。
図３０Ｃに示されるように、グラフィック・オブジェクト表示（５４０、５４４）を表す終端ノードの代りに木構造（５４２、５４６）を用いることで、粗な木構造５４８を拡張して、改善された木構造３５０を形成する。
図３０Ｄは、この結果として得られる、改善された木構造５５０に対応する候補相対レイアウトを、ページ５５２に示している。
【０１９８】
（Ｂ．グラフィック・オブジェクトの初期配置を作成する典型的なプロセス）
図３１Ａと図３１Ｂは、初期レイアウト作成モジュール２６４が、候補相対レイアウトを作成して、これらの候補相対レイアウトの１つを、ページ上のグラフィック・オブジェクトの初期配置８０として選択するときに用いる典型的な方法の一実施形態を示している（図２０を参照）。
【０１９９】
ブロック５６０は、１番目のグラフィック・オブジェクト（ＧＯ）の第１の表示で、現在候補レイアウトＴを起動する。
ブロック３６２は、現在候補レイアウトＴをレイアウト評価モジュール２６６に送る（図２０を参照）。
上で詳しく説明されるように、レイアウト評価モジュール２６６は、候補相対レイアウトの実現可能性を確認し、現在候補レイアウトＴにおけるグラフィック・オブジェクトに対する初期サイズ寸法を決定し、少なくとも一部、これらの初期サイズ寸法に基づいて、現在候補レイアウトＴに対してスコアScore（Ｔ）を算出する。
【０２００】
上記レイアウト評価モジュールがこの候補レイアウトを実現不可能とみなす場合には、この候補レイアウトは廃棄され、このプロセスは、直接、ブロック５６８に移る。
【０２０１】
この候補レイアウトが実現可能である場合には、ブロック５６４は、これが、１番目のグラフィック・オブジェクトの第１の表示であるかどうか判定する。
これが、１番目のグラフィック・オブジェクトの第１の表示である場合には、ブロック５６６は、木Ｔを現在最適レイアウトBest_Tに指定して、ブロック５６８に進む。
これが、１番目のグラフィック・オブジェクトの第１の表示でない場合には、ブロック５７０は、Score（Ｔ）を、最適の木に対応するレイアウト用のスコアScore（Best_T）と比較し、そこでは、上で説明されるやり方で採点が行われることがある。
Score（Ｔ）がScore（Best_T）よりも大きい場合には、ブロック５６６は、現在候補レイアウトＴを、新たなBest_Tに指定して、ブロック５６８に進む。
Score（Ｔ）がScore（Best_T）以下である場合には、最適現在候補レイアウトの指定を変更せず、このプロセスは、ブロック５６８に進む。
【０２０２】
ブロック５６８は、１番目のグラフィック・オブジェクトのどんな追加表示も利用可能であるかどうか判定する。
１番目のグラフィック・オブジェクトのもっと多くの表示が利用可能である場合には、ブロック５７２は、１番目のグラフィック・オブジェクトの次の表示を取り込んで、新たな現在候補レイアウトＴを形成し、このプロセスは、その新たな現在候補レイアウトに対して繰り返される。ブロック５６８が１番目のグラフィック・オブジェクトの追加表示がまったくないと判定する場合には、このプロセスは、図３１Ｂ中のブロック５７４に進む。
【０２０３】
ブロック５７４は、現在候補レイアウトに追加されるグラフィック・オブジェクトがこれ以上あるかどうか判定する。
現在候補レイアウトに追加されるグラフィック・オブジェクトがもうない場合には、この初期配置作成プロセスからの最終レイアウトとして、現在Best_Tが選択され、このプロセスは、ブロック５７６において終了する。
【０２０４】
ブロック５７４が、現在候補レイアウトに追加されるグラフィック・オブジェクトがあると判定する場合には、ブロック５７８は、現在最適レイアウトBest_Tを、新たな現在候補レイアウトＴに指定する。
ブロック５８０は、次の現在グラフィック・オブジェクトを取り込む。
ブロック５８２は、現在グラフィック・オブジェクトの第１の表示を取り込む（または、決定する）。
ブロック５８４は、現在候補レイアウトＴにおいて、現在グラフィック・オブジェクトの表示を評価すべき第１の位置を選択する。
この位置は、現在候補レイアウトＴの内部ノードまたは外部ノード（すなわち、葉）のいずれであってもよい。
ブロック５８６において、第１の位置に新たなノードを追加することで、代替候補レイアウトＴ'が作成される。
この新たなノードの１つの子は、現在候補レイアウトＴの部分木であり、しかも、その根は、Ｔにおける上記第１の位置である。
この新たなノードの他方の子は、このレイアウトに追加されている現在グラフィック・オブジェクトの現在表示である。
代替現在候補レイアウトＴ'において、この新たなノードに水平境界線が割り当てられる。
【０２０５】
ブロック５８８は、代替候補レイアウトＴ'をレイアウト評価モジュール２６６に送る。
上で詳しく説明されるように、レイアウト評価モジュール２６６は、候補相対レイアウトの実現可能性を確認し、代替候補レイアウトＴ'におけるグラフィック・オブジェクトに対する初期サイズ寸法を決定し、少なくとも一部、これらの初期サイズ寸法に基づいて、代替候補レイアウトＴ'に対してスコアScore（Ｔ'）を算出する。
【０２０６】
上記レイアウト評価モジュールが、この候補レイアウトを実現不可能と見なす場合には、この候補レイアウトは廃棄され、このプロセスは、直接、ブロック５９４に移る。
【０２０７】
この候補レイアウトが実現可能である場合には、ブロック５９０は、これが、現在グラフィック・オブジェクトの第１の位置および第１の表示であるかどうか判定する。
これが現在グラフィック・オブジェクトの第１の位置および第１の表示である場合には、ブロック５９２は、代替候補レイアウトＴ'を最適現在レイアウトBest＿Ｔに指定して、ブロック５９４に進む。
これが現在グラフィック・オブジェクトの第１の位置および第１の表示でない場合には、ブロック５９６は、Score（Ｔ'）を、最適現在レイアウトに対応するレイアウト用のスコアScore（Best＿Ｔ）と比較し、そこでは、上で説明されるやり方で採点が行われることがある。
Score（Ｔ'）がScore（Best＿Ｔ）よりも大きい（代替候補レイアウトＴ'が現在候補レイアウトＴよりも良いことを示す）場合には、ブロック５９２は、Ｔ'を最適現在レイアウトBest＿Ｔに指定し、このプロセスは、ブロック５９４に進む。
Score（Ｔ'）がScore（Best＿Ｔ）以下である場合には、最適現在レイアウトの指定を変更せず、処理は、同じブロック５９４に進む。
【０２０８】
ブロック５９４において、現在位置の所に新たなノードを追加することで、他の代替現在レイアウトＴ'が作成される。
この新たなノードの１つの子はＴの部分木であり、その根は、Ｔの上記位置である。
この新たなノードの他方の子は、現在このレイアウトに追加されているグラフィック・オブジェクトの現在表示である。
ブロック５９４の代替現在レイアウトＴ'において、この新たなノードに水平境界線が割り当てられる。
【０２０９】
ブロック５９７は、代替候補レイアウトＴ'をレイアウト評価モジュール２６６に送る。
レイアウト評価モジュール２６６は、候補相対レイアウトの実現可能性を確認し、代替候補レイアウトＴ'におけるグラフィック・オブジェクトに対する初期サイズ寸法を決定し、少なくとも一部、これらの初期サイズ寸法に基づいて、代替候補レイアウトＴ'に対してスコアScore（Ｔ'）を算出する。
【０２１０】
上記レイアウト評価モジュールが、この候補レイアウトを実現不可能と見なす場合には、この候補レイアウトは廃棄され、このプロセスは、直接、ブロック６０２に移る。
【０２１１】
この候補レイアウトが実現可能である場合には、ブロック５９８は、代替現在候補レイアウトＴ'に対応するレイアウト用のスコアScore（Ｔ'）を決定して、Score（Ｔ'）をScore（Best＿Ｔ）と比較する。
ブロック５７０、ブロック５９６、ブロック５９８は、同一の、または異なる採点方法を使用することがある。
Score（Ｔ'）がScore（Best＿Ｔ）よりも大きい場合には、ブロック６００は、代替現在レイアウトＴ'を最適現在レイアウトBest＿Ｔに指定し、このプロセスはブロック６０２に進む。
ブロック５９８が、Ｔ'のスコアがBest＿Ｔのスコア以下であると判定する場合には、このプロセスは、直接、ブロック６０２に進む。
【０２１２】
ブロック６０２は、現在候補レイアウトＴにおいて利用可能な追加位置があるかどうか判定する。
現在候補レイアウトＴにおいて追加位置が利用可能である場合には、ブロック６０４は、現在候補レイアウトＴにおいて、現在グラフィック・オブジェクトの表示を評価すべき新たな位置を選択する。
ブロック５８６〜ブロック６０２は、同じ現在グラフィック・オブジェクトの表示を用いて、繰り返される。
【０２１３】
ブロック６０２が、現在候補レイアウトＴにおいて追加位置がまったく利用できないと判定すると、このプロセスは、ブロック６０６に進む。
ブロック６０６は、考慮すべき現在グラフィック・オブジェクトの追加表示があるかどうか判定する。
グラフィック・オブジェクトの追加表示が利用可能である場合には、このプロセスは、ブロック６０７に進み、そこで、現在グラフィック・オブジェクトの次の表示を取り込む。
ブロック５８４は、現在候補レイアウトＴにおいて、現在グラフィック・オブジェクトの表示を評価すべき第１の位置を選択する。
ブロック５８６〜ブロック６０４は、現在候補レイアウトＴにおいて、利用可能な位置ごとに現在グラフィック・オブジェクトＴの次の表示を評価する。
【０２１４】
ブロック６０６が、考慮すべき現在グラフィック・オブジェクトの表示がもうないと判定すると、このプロセスはブロック５７４に進み、そこで、現在候補レイアウトに追加されるグラフィック・オブジェクトがあるかどうか判定する。
ブロック５７４が、現在候補レイアウトに追加されるグラフィック・オブジェクトがもうないと判定すると、最終確定レイアウトとして現在Best＿Ｔが選択され、このプロセスは、ブロック５７６において終了する。
【０２１５】
（ＶＩ．ページ上にグラフィック・オブジェクトの最終配置を作成する）
上で説明されるように、最終レイアウト作成モジュール２７０は、グラフィック・オブジェクト配置システム６０にレイアウト変更モジュール６８が含まれるかどうかにより、初期レイアウト作成モジュール２６４またはレイアウト変更モジュール６８のいずれかから、ページ区画を表現する木構造を受け取る。
木構造のそれぞれの葉ノードは、縦横比の値（ａ）、および、ストリクト・エリア・スタイルのレイアウトの場合には、公称サイズの値（ｅ）を持ち、また、それぞれの内部ノードは、ページ上の水平境界線または垂直境界線のいずれかを示す。
最終レイアウト作成モジュール２７０は、それぞれのページ上のグラフィック・オブジェクトのエリアを決定し、次に、ページ・スペースの正確な領域をそれぞれのノードに割り振る。
ページのこれらの割振り領域は、対応する木構造と同様にネスト（nest）される。
これらの割振り領域は、ここでは、「セル（cells）」と呼ばれる。
いくつかの実施例では、或るセルが既知であると、そのセルに割り当てられるグラフィック・オブジェクトの位置は、このグラフィック・オブジェクトを、このセルの中心に置くことで、決定される。
【０２１６】
（Ａ．グラフィック・オブジェクト・エリアを決定する）
これらのグラフィック・オブジェクトのエリアは、所望の精度、所望のレイアウト・スタイル、利用可能な計算機資源に応じて、バウンディング・ボックス・ベースのエリア決定法か、パス・ベースのエリア決定法か、線形システム・ベースのエリア決定法のいずれかにより決定される。
ときには、上記のグラフィック・オブジェクト・エリア決定法の１つを用いて、レイアウト評価モジュール２６６が直前の上流側レイアウト・モジュールに対して計算したグラフィック・オブジェクト・エリアが、最終レイアウト作成モジュール２７０で使用されることもある。
その他の場合、最終レイアウト作成モジュール２７０は、上記のグラフィック・オブジェクト・エリア決定法の別の１つを用いてグラフィック・オブジェクト・エリアを算出するよう、レイアウト評価モジュール２６６に指示することもある。
【０２１７】
（Ｂ．木構造内のノードの周りのバウンディング・ボックスを決定する）
絶対エリアが算出された後で、木構造内のそれぞれのノードの周りで、バウンディング・ボックスが評価される。
このプロセスを達成するのに必要な実際のステップは、図２７に示されるように、バウンディング・ボックス・ベースのエリア決定に関連して上述のバウンディング・ボックスを算出するプロセスとまったく類似している。ただし、次の２つの例外がある。
第１に、これらの公称サイズは、たまたま実際のグラフィック・オブジェクト・エリアである。
第２に、内部ノードに割り当てられた間隔は、無視されるのではなく、もっと適切に言えば、ブロック４９２およびブロック４９６の算出の合計に加えられる。
【０２１８】
（Ｃ．グラフィック・オブジェクトにページ・スペースを割り振る）
（１．ページ・スペース割振りプロセスの概要）
いくつかの実施形態では、ノードにページ・スペースの領域を割り振るプロセスは、ページをセルに分けて、それぞれのグラフィック・オブジェクトを、その対応するセルの中に位置づけるものである。
このページは、最初の長方形としてページの使用できるエリア全体から始めて、ページを複数の長方形に分割することで、セルに分けられる。
それぞれの分割は、幅優先探索の順に根ノードから始まって、内部ノードの対応する１つに対して線分を引くことで達成される。
【０２１９】
垂直境界線に対応する内部ノードの場合には、最終レイアウト作成モジュール２７０は、利用可能な領域の幅に沿って、水平位置ｘを選択する。
１つの式で表すと、ｘ∈（０，１）となる。ここで、ｘ＝０は、利用可能な領域内の最左端の位置を表し、また、ｘ＝１は、利用可能な領域内の最右端の位置を表す。
この場合、次式が成り立つ。
【０２２０】
【数２８】
2010532042.tif 000030
【０２２１】
ここで、ａ１、ｅ１およびａｒ、ｅｒは、内部ノードの左側の子および右側の子に対する、バウンディング・ボックスの縦横比およびエリア（面積）である。
このように式で表すと、比率として幅が直接に利用される。
水平境界線に対する類似の公式は、高さを使用する。すなわち、利用可能なスペースの高さに沿った垂直位置がｙ∈（０，１）で示される場合（ここで、ｙ＝０は最下位の位置を表し、また、ｙ＝１は最上位の位置を表す）、次式が成り立つ。
【０２２２】
【数２９】
2010532042.tif 000031
【０２２３】
ここで、ａｂ、ｅｂおよびａｔ、ｅｔは、内部ノードの下側の子および上側の子に対して、バウンディング・ボックスの縦横比およびエリア（面積）である。
【０２２４】
この結果、ページ上に得られるグラフィック・オブジェクトのレイアウトは、図２０に示されるグラフィック・オブジェクトの最終レイアウト２９０を形成している。
【０２２５】
（２．グラフィック・オブジェクトにページ・スペースを割り振る詳細なプロセス）
図３２は、ページ上の物理的なスペース領域を現在木構造の根ノードに割り振る方法の一実施形態を示している。
この方法により、レイアウト・スタイルが決定される（図３２のブロック６３０）。
ストリクト・エリア・スタイルのレイアウトでは、このページの使用できるエリア全体が根ノードに割り当てられる（図３２のブロック６３２）。
ブリック・スタイルのレイアウトでは、根ノードに割り当てられたページ・スペースは、この根ノードに対応づけられるバウンディング・ボックスの高さおよび幅を持っている（図３２のブロック６３４、ブロック６３６）。
次に、根ノードに割り当てられた領域が、利用可能なページ・スペースの中心に位置づけられる（図３２のブロック６３８）。
【０２２６】
図３３は、ページ・スペースの領域を木構造のノードの子に割り振る方法の一実施形態を示している。
このプロセスにおいて、それぞれの内部ノードに割り当てられたスペース領域は、その２つの直接の子の間に配分（divide）される。
このような配分は、現在木構造の根ノードを現在ノードにセットして、再帰的プロセスを実行することで達成される。
【０２２７】
この再帰的プロセスにおいて、現在ノードが終端ノードであるかどうか決定がなされる（図３３のブロック６４０）。
現在ノードが終端ノード（すなわち、葉ノード）である場合には、このプロセスは終了する（図３３のブロック６４２）。
現在ノードが内部ノードである場合には、現在ノードが単一要素グラフィック・オブジェクトを２つ以上持つ多要素グラフィック・オブジェクト（ＧＯ）に対応する木の根ノードであるかどうかの判定が、行われる（図３３のブロック６４４）。
これが当てはまる場合には、現在ノードに割り当てられた領域は、その領域の高さおよび幅を、前に現在ノードに対して算出されたバウンディング・ボックスの高さおよび幅になるように再び割り当てることで、圧縮され（図３３のブロック６４６）、また、この領域の位置は、前に現在ノードに割り当てられた領域の中心に置かれる。
ブリック・スタイルのレイアウトでは、これは、なんの効果もない。
ストリクト・エリア・スタイルのレイアウトでは、これは、グラフィック要素を２つ以上持つグラフィック・アセンブリ（例えば、一連のキーフレーム）において、画像をまとめる効果がある。
【０２２８】
現在ノードが、多要素グラフィック・オブジェクトに対応する木の根ノードではないと判定される場合には（図３３のブロック６４４）、現在ノードの左側の子および右側の子に対して、スペース領域の高さおよび幅を算出する（図３３のブロック６４８）。
【０２２９】
現在ノードが水平ページ境界線である場合には、右の子および左の子に割り当てられる領域の高さ（ＨＲ、ＨＬ）は、次式で与えられる。
【０２３０】
【数３０】
2010532042.tif 000032
【０２３１】
【数３１】
2010532042.tif 000033
【０２３２】
ここで、ＨNODEは現在ノードのスペース領域の高さであり、Ｓはノード間隔であり、Ｌは左側子ノードのバウンディング・ボックスの高さであり、さらに、Ｒは、右側子ノードのバウンディング・ボックスの高さである。
左側の子および右側の子に割り当てられる領域の幅は、現在ノードに割り当てられた領域の幅に等しくセットされる。
【０２３３】
現在ノードが垂直ページ境界線である場合には、右の子および左の子に割り当てられる領域の幅（ＷＲ、ＷＬ）は、次式で与えられる。
【０２３４】
【数３２】
2010532042.tif 000034
【０２３５】
【数３３】
2010532042.tif 000035
【０２３６】
ここで、ＷNODEは現在ノードのスペース領域の幅である。
左側の子および右側の子に割り当てられる領域の高さは、現在ノードに割り当てられた領域の高さに等しくセットされる。
【０２３７】
現在ノードが水平ページ境界線である場合には（図３３のブロック６５０）、左側の子のスペース領域は、現在ノードに割り当てられたスペース領域の上側境界のできるだけ近くに位置づけられる（図３３のブロック６５２）。
右側の子のスペース領域は、現在ノードに割り当てられたスペース領域の下側境界のできるだけ近くに位置づけられる（図３３のブロック６５４）。
【０２３８】
現在ノードが垂直ページ境界線である場合には（図３３のブロック６５０）、左側の子のスペース領域は、現在ノードに割り当てられたスペース領域の左側境界のできるだけ近くに位置づけられる（図３３のブロック６５６）。
右側の子のスペース領域は、現在ノードに割り当てられたスペース領域の右側境界のできるだけ近くに位置づけられる（図３３のブロック６５８）。
【０２３９】
左側子ノードの子にスペース領域を割り振り（図３３のブロック６６０）、また、右側子ノードの子にスペース領域を割り振る（図３３のブロック６６２）ために、上述のプロセスが繰り返される。
現在ノードのすべての子（直接、またはそれ以外）にページ・スペース領域が割り当てられるまで、このプロセスは繰り返される。
【０２４０】
（ＶＩＩ．結論）
ここで詳細に説明される実施形態は、１つまたは複数のページ上にグラフィック・オブジェクトを配置する方法を提供する。
これらの実施形態は、それぞれのレイアウト（または配置）において１つまたは複数のグラフィック・オブジェクトの相対的サイズに対する明示的な好みにより誘導または制御され得る。
いくつかの実施形態は、このような特徴を活用して、グラフィック・オブジェクトの異なる１つ１つを特別に目立たせる（すなわち、特徴づける）代替配置を作成する。
このようにして、これらの代替配置は、ページ上のグラフィック・オブジェクトの可能な配置の分布にわたるレイアウトのサンプリングをもたらす。
いくつかの実施形態は、このような特徴を活用して、ユーザーが、１つまたは複数のグラフィック・オブジェクトの相対的サイズに対する好みを入力できるようにし、そこで、このような相対的サイズの好みが、特定のレイアウトにおいてグラフィック・オブジェクトの一部のものを１つ１つ目立たせる（例えば、さらに大きくする）か、あるいは目立たなくする（例えば、さらに小さくする）ように、レイアウト作成プロセスを誘導する。
このようにして、ユーザーは、グラフィック・オブジェクトの特定配置に留意してないときでも、ユーザーの美的好みを満たすような上記グラフィック・オブジェクトの特定レイアウトまでこのシステムを誘導することができる。
【０２４１】
他の実施形態は、併記の特許請求の範囲の範囲内にある。
【符号の説明】
【０２４２】
６０  システム
６２  ページ割当てモジュール
６４  ページ・レイアウト作成モジュール
６６  ユーザー・インターフェース・モジュール
７０  グラフィック・オブジェクト
９８  最終レイアウト
１００  グラフィック・オブジェクト
１０２  ページ
１２０  候補レイアウト
２６４  初期レイアウト作成モジュール
２６６  レイアウト評価モジュール
２７０  最終レイアウト作成モジュール
【図１】
2010532042.tif 000036
【図２】
2010532042.tif 000037
【図３Ａ】
2010532042.tif 000038
【図３Ｂ】
2010532042.tif 000039
【図３Ｃ】
2010532042.tif 000040
【図３Ｄ】
2010532042.tif 000041
【図４】
2010532042.tif 000042
【図５】
2010532042.tif 000043
【図６】
2010532042.tif 000044
【図７】
2010532042.tif 000045
【図８】
2010532042.tif 000046
【図９】
2010532042.tif 000047
【図１０】
2010532042.tif 000048
【図１１】
2010532042.tif 000049
【図１２】
2010532042.tif 000050
【図１３Ａ】
2010532042.tif 000051
【図１３Ｂ】
2010532042.tif 000052
【図１３Ｃ】
2010532042.tif 000053
【図１３Ｄ】
2010532042.tif 000054
【図１４Ａ】
2010532042.tif 000055
【図１４Ｂ】
2010532042.tif 000056
【図１５Ａ】
2010532042.tif 000057
【図１５Ｂ】
2010532042.tif 000058
【図１６Ａ】
2010532042.tif 000059
【図１６Ｂ】
2010532042.tif 000060
【図１７】
2010532042.tif 000061
【図１８】
2010532042.tif 000062
【図１９Ａ】
2010532042.tif 000063
【図１９Ｂ】
2010532042.tif 000064
【図２０】
2010532042.tif 000065
【図２１】
2010532042.tif 000066
【図２２】
2010532042.tif 000067
【図２３Ａ】
2010532042.tif 000068
【図２３Ｂ】
2010532042.tif 000069
【図２４】
2010532042.tif 000070
【図２５】
2010532042.tif 000071
【図２６Ａ】
2010532042.tif 000072
【図２６Ｂ】
2010532042.tif 000073
【図２６Ｃ】
2010532042.tif 000074
【図２６Ｄ】
2010532042.tif 000075
【図２６Ｅ】
2010532042.tif 000076
【図２６Ｆ】
2010532042.tif 000077
【図２６Ｇ】
2010532042.tif 000078
【図２６Ｈ】
2010532042.tif 000079
【図２６Ｉ】
2010532042.tif 000080
【図２６Ｊ】
2010532042.tif 000081
【図２７】
2010532042.tif 000082
【図２８】
2010532042.tif 000083
【図２９Ａ】
2010532042.tif 000084
【図２９Ｂ】
2010532042.tif 000085
【図２９Ｃ】
2010532042.tif 000086
【図３０Ａ】
2010532042.tif 000087
【図３０Ｂ】
2010532042.tif 000088
【図３０Ｃ】
2010532042.tif 000089
【図３０Ｄ】
2010532042.tif 000090
【図３１Ａ】
2010532042.tif 000091
【図３１Ｂ】
2010532042.tif 000092
【図３２】
2010532042.tif 000093
【図３３】
2010532042.tif 000094
【国際調査報告】
2010532042.tif 000095
2010532042.tif 000096