相対位置に基く制御によるページ上のグラフィックスオブジェクトの配置
グラフィックスオブジェクト(72)のユーザ指定レイアウト(80)を受け取る。ユーザ指定レイアウト(80)から、相対レイアウト仕様(84)を導出する。相対レイアウト仕様(84)に従って、グラフィックスオブジェクト(74)の最終レイアウト(102)を決定する。最終レイアウト(102)は、ページ(82)上のグラフィックスオブジェクト(72)のサイズ寸法、及び位置に関する仕様を含む。グラフィックスオブジェクト(72)の最終レイアウト(102)を出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願の相互参照］
本願は、下記の同時係属出願にも関連し、各出願は、参照により本明細書に援用される。
・２００３年９月３０日に出願された米国特許出願第１０／６７５，７２４号
・２００３年９月３０日に出願された米国特許出願第１０／６７５，８２３号
・２００５年５月１２日に出願された米国特許出願第１１／１２７，３２６号
・２００５年５月１２日に出願された米国特許出願第１１／１２８，５４３号
・２００４年４月２３日に出願された米国特許出願第１０／８３１，４３６号
・２００５年４月１５日に出願された米国特許出願第１１／１２６，６３７号
・２００５年６月１０日に出願された米国特許出願第１１／１５１，１６７号
・２００５年３月１日に出願された米国特許出願第１１／０６９，５１２号
・２００４年１１月１２日に出願された米国特許出願第１０／９８７，２８８号
・２００６年３月１日に出願された米国特許出願第１１／３６４，９３３号
・２００７年６月２７日に出願された米国特許出願第１１／７６９，６７１号
【背景技術】
【０００２】
人、及び組織は、静止画像、テキスト、グラフィック、アニメーショングラフィック、及びフルモーションビデオ画像のような大量のデジタル画像コンテンツを急速に蓄積している。これらのコンテンツは、個別に表現される場合もあれば、文書、カタログ、プレゼンテーション、静止画写真、商用ビデオ、家庭用ビデオ、及び１以上の関連デジタルコンテンツファイルを表すメタデータといったように、広く様々な形で結合される場合もある。こうした収集物の数が増加し、その多様性が増加するのに従って、人、及び組織は、デジタルコンテンツを自分達の収集物として編集、及び表現するシステム、及び方法を益々必要としている。この要求を満たすために、デジタル画像コンテンツを編集、及び表示するための種々のシステム、及び方法が提案されている。
【０００３】
例えば、ユーザがデジタルフォトアルバムを手作業で作成することが可能な幾つかの手動型のデジタル画像アルバム化システムが存在する。こうしたシステムは一般に、多数の画像を編集し、画像を１以上のページ上にレイアウトするツールを提供する。中でもデジタルフォトアルバムを手作業で作成する一般的タイプのツールは、多数の画像の中からアルバムの１ページに表示される一部の画像を選択するツール、ページ上の画像を手動で再配置するためのグラフィカルユーザインタフェース、及び、アルバムに表示される画像のサイズ、及び向きのような種々の特徴を変更するための基本的な画像編集ツールである。ユーザは通常、完全手動型のデジタル画像アルバム化システムを使用してデジタルフォトアルバムを作成するプロセスが、退屈で、時間を要するものであることを知っている。
【０００４】
一部の自動化されたデジタル画像アルバム化システムによれば、ユーザは、画像に関連するメタデータとして指定された日付や時刻に従ってデジタル画像をアルバムページとして編集することが出来る。こうしたシステムによれば、一般にユーザは、デジタルフォトアルバムに表示される画像に注釈を付けることも出来る。自動化されたデジタル画像アルバム化システムによっては、種々の所定のレイアウトテンプレートを備え、ユーザは、そうしたレイアウトテンプレートを選択し、デジタルフォトアルバムを作成出来る場合がある。こうしたシステムでは、ユーザが、多数の画像の中から幾つかの画像を選択されたレイアウトテンプレート上の種々の所定の画像位置に割当てると、システムは、それらの画像のサイズ、位置、回転、及び枠組みを、選択されたテンプレート上の種々の所定の画像位置について指定されたパラメタに従って自動的に調節する。
【０００５】
デジタル画像アルバム化システムの中には、ユーザからの最小限の入力で、アルバムページを自動的に生成するように設計されるものがある。そのようなシステムの一つとして、ページ作成器モジュール、及び画像配置モジュールが挙げられる。ページ作成器モジュールは、多数の画像を、第１の遺伝進化アルゴリズムに基いてアルバムページに割当てる。画像配置モジュールは、所与のページに割当てられた画像についてのページレイアウトの遺伝構造を、第２の遺伝進化アルゴリズムに基いて生成する。これらの遺伝構造は、所与のページに配置される画像の位置、縮尺、及び回転姿勢を決定する。ページレイアウト発生器モジュールは、それらのレイアウトを特定の他の好み、及びページ要件と比較する。適当なレイアウトが生成されると、最終的なアルバムレイアウトは表示され、印刷され、又は後の使用に備えて転送される場合がある。
【０００６】
他の自動デジタル画像アルバム化システムとしては、イベントによって編集され、一組のアルバム化パラメタに基いて自動的にレイアウトされたアルバムをユーザに対し表示する、ページレイアウトモジュールを含むものがある。１ページ上にレイアウトされる画像の数は、パラメトリック法によって決定され、又は画像の属性の分析によって決定される。パラメトリック法は、１ページを一組の正方格子に分割し、１ページ上にレイアウトされる画像の数を、画像をそれらの正方格子上にレイアウトするための一組の規則に基いて決定する。このシステムでは、ページ上の画像の実際のレイアウトは、画像のサイズのような画像の属性を一組のテンプレートに適合させることによって決定される場合がある。
【０００７】
さらに他の自動デジタル画像アルバム化システムは、各画像が同じページ上に配置される他の画像に対して力を加えることを仮定する力学モデルに基いて、画像をページ上に自動的に位置決めする場合がある。力は、画像間を隔てる距離の関数である。システムは、各画像をその画像に対して加わる総合的な力の向きにその総合的な力の関数として決まる距離だけ動かすことによって、ページ上の画像の初期レイアウトを変更する。
【０００８】
グラフィックスオブジェクトをページ上に自動的に配置するシステム、及び方法であって、各レイアウトにおけるグラフィックスオブジェクトのうちの１以上の相対位置についての明確な好みによって管理され、又は制御されることが可能なものが必要とされている。
【発明の概要】
【課題を解決するための手段】
【０００９】
［概要］
一態様において、本発明は、どのグラフィックスオブジェクトのユーザ指定レイアウトを受け取ったかに応じた方法を特徴とする。ユーザ指定レイアウトから、相対レイアウト仕様が導出される。相対レイアウト仕様は、グラフィックスオブジェクトの相対位置を表す。グラフィックスオブジェクトの最終レイアウトは、相対レイアウト仕様に従って決定される。最終レイアウトは、ページ上のグラフィックスオブジェクトのサイズ寸法、及び位置の仕様を含む。グラフィックスオブジェクトの最終レイアウトは、出力される。
【００１０】
本発明は、上に記載した方法を実施するように構成された装置、及び上に記載した方法をコンピュータに実施させるためのコンピュータ読取可能命令を記憶するコンピュータ読取可能媒体をさらに特徴とする。
【００１１】
本発明の他の特徴、及び利点は、図面、及び特許請求の範囲の記載を含めて、下記の説明から明らかになるであろう。
【図面の簡単な説明】
【００１２】
【図１】ページ上のグラフィックスオブジェクトのレイアウトを示す概略図である。
【図２】図１に示したグラフィックスオブジェクトのレイアウトを示す概略図であり、図中、複数の単一要素グラフィックスオブジェクトから形成されるマルチ要素グラフィックスオブジェクトは、破線楕円で示される。
【図３Ａ】６つの要素グラフィックスオブジェクトから形成されるマルチ要素グラフィックスオブジェクトの一例を示す図である。
【図３Ｂ】６つの要素グラフィックスオブジェクトから形成されるマルチ要素グラフィックスオブジェクトの一例を示す図である。
【図３Ｃ】６つの要素グラフィックスオブジェクトから形成されるマルチ要素グラフィックスオブジェクトの一例を示す図である。
【図３Ｄ】６つの要素グラフィックスオブジェクトから形成されるマルチ要素グラフィックスオブジェクトの一例を示す図である。
【図４】グラフィックスオブジェクトを１以上のページ上に配置するシステムの一実施形態を示すブロック図である。
【図５】図４のシステムにより実施されるグラフィックスオブジェクト配置方法の一実施形態を示すフロー図である。
【図６】グラフィックスオブジェクトのユーザ指定レイアウトの一例を示す概略図である。
【図７】図６に示したユーザ指定レイアウトから導出される相対レイアウト仕様の一例を示す概略図である。
【図８】図７に示した相対レイアウト仕様に従って請求項４のシステムにより決定される、グラフィックスオブジェクトの最終レイアウトの一例を示す概略図である。
【図９】グラフィックスオブジェクトのユーザ指定レイアウトを作成するためのユーザコマンドを受け取るグラフィカルユーザインタフェースの一実施形態を示す図である。
【図１０】グラフィックスオブジェクトのユーザ指定レイアウトを作成するためのユーザコマンドを受け取るグラフィカルユーザインタフェースの一実施形態を示す図である。
【図１１】図４に示したグラフィックスオブジェクト配置システムの一実施形態を示すブロック図である。
【図１２】グラフィックスオブジェクトのユーザ指定レイアウトの画像、及びユーザ指定レイアウトを機械認識したものの一例を示す図である。
【図１３Ａ】グラフィックスオブジェクトのユーザ指定レイアウトの例、並びに、水平（ｘ）軸、及び垂直（ｙ）軸に沿った位置の関数として、グラフィックスオブジェクトのカウント数の水平投影、及び垂直投影から導出されるヒストグラムの例を示す図である。
【図１３Ｂ】図１３Ａに示したユーザ指定レイアウトを表すツリー構造の概略図である。
【図１４Ａ】図１３Ａのユーザ指定レイアウトにおけるグラフィックスオブジェクト間のパーティションの一例を示す図である。
【図１４Ｂ】図１４Ａに示したユーザ指定レイアウト分割を表す二分木構造を示す概略図である。
【図１５Ａ】図１３Ａのユーザ指定レイアウトにおけるグラフィックスオブジェクト間のパーティションの一例を示す図である。
【図１５Ｂ】図１５Ａに示したユーザ指定レイアウト分割を表す二分木構造を示す概略図である。
【図１６】ツリー構造の１つのノードのバウンディングボックスの特徴を決定する方法の一実施形態を示すフロー図である。
【図１７】ページ上の空白領域をツリー構造のルートノードに割当てる方法の一実施形態を示すフロー図である。
【図１８】ページ上の種々の空白領域をツリー構造の１つのノードの子ノードに割当てる方法の一実施形態を示すフロー図である。
【図１９】図４のグラフィックスオブジェクト配置システムの一実施形態が組み込まれた装置の一実施形態を示すブロック図である。
【発明を実施するための形態】
【００１３】
[詳細な説明]
下記の説明において、同じ参照符号は、同じ要素を識別するために使用される。また、図面は、例示的実施形態の主な特徴を概略的に示すことを意図している。図面は、実際の実施形態のあらゆる特徴を示すことを意図するものでも、描かれた要素の相対的寸法を示すことを意図するものでもなく、原寸どおりに描かれてもいない。
【００１４】
１．序論
本明細書において詳細に説明される種々の実施形態は、グラフィックスオブジェクトを１以上のページ上に配置する種々の方法を提供する。これらの実施形態は、各レイアウト（又は、配置）におけるグラフィックスオブジェクトの相対位置についての明確な好みによって管理され、又は制御されることができる。同時に、それらの実施形態は、それらの好みから、指定された設計上の制限（例えば、ページサイズ、マージン、及びガッター余白制限）に従ったグラフィックスオブジェクトの最終レイアウトを自動生成することができる。このように、ユーザは、より専門的に、かつより美術的に美しい形でクリーナを表示しながら、それらの実施形態を、ユーザのグラフィックスオブジェクト配置の一般的な好みに合致するグラフィックスオブジェクトの特定のレイアウトへと誘導することができる。
【００１５】
本明細書において、「ページ」という用語は、その上にグラフィックスオブジェクトをレイアウトすることが可能な任意のタイプの独立した領域を意味し、例えば、グラフィックスオブジェクトを印刷することが可能な独立した物理媒体として実施される物理的ページ（例えば、一片の用紙）、及び例えば電子表示装置によりユーザに対して表示することが可能なグラフィックスオブジェクトのレイアウトを含む仮想的、デジタル的、又は電子的なページを含む。
【００１６】
「グラフィックスオブジェクト」という用語は、物理的ページ、又は仮想的ページ上に描画することが可能な任意のタイプの視覚的に知覚可能なコンテンツを幅広く意味し、例えば、画像、及びテキストを含む。画像ベースのグラフィックスオブジェクト（又は、単に「画像」）は、任意のタイプのデジタル画像、又は電子画像であってよく、完全な画像であっても、部分的な画像であってもよく、例えば、画像センサ（例えば、ビデオカメラ、静止画カメラ、又は光学スキャナ）により撮影された画像、又はそのような画像を処理（フィルタリング、再整形、拡大、若しくはその他変更）したもの、テキスト画像（例えば、テキストを含むビットマップ画像）、及び図形的画像を含む。「グラフィックスオブジェクト」という用語は、単一要素グラフィックスオブジェクトと、１以上のグラフィックスオブジェクトの団結グループ、又は集まりから形成されるマルチ要素グラフィックスオブジェクトとの両方を包含する。特定のマルチ要素グラフィックスオブジェクトに対する単一要素グラフィックスオブジェクトの割当ては、構成要素となる複数の単一要素グラフィックスオブジェクトを互いに関連付けることを意味する。一般に、マルチ要素グラフィックスオブジェクトに含まれる複数の単一要素グラフィックスオブジェクトは、同じタイプのものであってもよいし、異なるタイプのものであってもよい。グラフィックスオブジェクトは通常、１以上のコンピュータ読取可能媒体上の１以上のデータベースに記憶される。
【００１７】
一部の実施形態において、画像ベースのグラフィックスオブジェクト(例えば、写真のような画像）は、固定面積画像として指定される場合もあれば、可変面積画像として指定される場合もある。これらの実施形態では、固定面積画像の面積やサイズが、生成されるレイアウトにおいて変更されることはないが、可変面積画像のサイズを変更することは許される。可変面積画像は、同じページ上に描画される画像の相対面積に関して制限を有する場合もあれば、有しない場合もある。
【００１８】
例示的実施形態として、画像ベースのグラフィックスオブジェクトはそれぞれ、個別のアスペクト比を有する。アスペクト比は、画像の幅に対する画像の高さの比として定義される。各可変面積画像には、正のスカラー値の公称サイズが割当てられる場合がある。「公称サイズ」とは、指定サイズ、又は理論上のサイズを意味し、公称サイズは、実際のサイズ、すなわち描画されるサイズとは異なる場合もあれば、異ならない場合もある。グラフィックスオブジェクトの「サイズ」とは、そのグラフィックスオブジェクトが占めるページ上の面積の大きさを意味する。実施形態によっては、ユーザは、画像に割当てられる公称サイズ値を設定することが出来る場合がある。他の実施形態において、グラフィックスオブジェクト配置システムは、公称サイズ値をグラフィックスオブジェクトに自動的に割当てる場合がある。
【００１９】
図１は、複数の単一要素グラフィックスオブジェクト１２〜３２を含むページ１０の一例を示している。
【００２０】
図２に示すように、単一要素グラフィックスオブジェクト１２〜３２のうちの選択されたものは、グラフィックスオブジェクト４２としてグループ化される場合があり、グラフィックスオブジェクト４２を構成するグラフィックスオブジェクト（すなわち、１４〜２４）は、ページ上のグラフィックスオブジェクトのレイアウトにおいて、互いに近くに表示されることを意図している。図２に示す例において、マルチ要素グラフィックスオブジェクト４２は、異なるタイプの複数の単一要素グラフィックスオブジェクト（例えば、画像ベースのグラフィックスオブジェクトとテキストのグラフィックスオブジェクト）を含む場合がある。また、マルチ要素グラフィックスオブジェクトの単一要素グラフィックスオブジェクトは、自由に配置される場合もあれば、特定の順序（例えば、ビデオクリップのキーフレームの一時的な並び順序）で配置される場合もある。他のいずれのグラフィックスオブジェクトとの間にも密接な関係を有しない単一要素グラフィックスオブジェクトは、単一の表現形態しか持たない「退化」グラフィックスオブジェクトである。
【００２１】
図３Ａ〜図３Ｄに示すように、構成要素として２以上のグラフィックスオブジェクトを含むグラフィックスオブジェクト５２は、２以上の方法（すなわち、配置）で表示することができる。実施形態によっては、マルチ要素グラフィックスオブジェクトにおける単一要素グラフィックスオブジェクトの表示は、グラフィックスオブジェクトの水平配置、又は垂直配置に制限される場合がある。そのような実施形態では、場合によっては、表示は、単一要素グラフィックスオブジェクトの特定の好ましい水平配置、及び垂直配置にさらに制限される場合がある。例えば、ある実施形態は、同一のマルチ要素グラフィックスオブジェクト内において、テキストのグラフィックスオブジェクトを、画像の右、又は下に表示することしか許可しない場合がある。この場合、画像、及びテキストブロックを含むグラフィックスオブジェクトは、２つの異なる方法で表示される場合がある。図３Ａ〜図３Ｄは、一連の６個のグラフィックスオブジェクト５４（例えば、ビデオキーフレーム）を含むグラフィックスオブジェクト５２を、４つの異なる方法で表示することが出来ることを示している。
【００２２】
一般にグラフィックスオブジェクトは、「厳密面積」スタイル、又は「レンガ」スタイルに従って、ページ上にレイアウトされる。厳密面積スタイルレイアウトの場合、同一ページ上にある複数のグラフィックスオブジェクトの相対面積は、所定の比率に適合する場合がある。例えばユーザは、同一ページ上にある全てのグラフィックスオブジェクトに同じ面積を与えることを指示する場合がある。レンガスタイルレイアウトの場合、同一ページ上のグラフィックスオブジェクトの相対面積は、画像間に空きスペースが全く生じないように選択される。厳密面積スタイルレイアウト、及びレンガスタイルレイアウトの詳細については、２００４年９月３０日に出願された米国特許出願第１０／６７５，７２４号、及び２００４年９月３０日に出願された米国特許出願第１０／６７５，８２３号から得られる。
【００２３】
ＩＩ．グラフィックスオブジェクトをページ上に配置する一般的枠組み
図４は、グラフィックスオブジェクト６２を１以上のページ上に配置するためのシステム６０の一実施形態を示している。システム６０は、ページレイアウト発生器モジュール６４、及びユーザインタフェースモジュール６６を含み、ユーザは、ユーザインタフェースモジュール６６を通してグラフィックスオブジェクト配置システム６０と情報をやり取りすることができる。グラフィックスオブジェクト６２は、１以上のローカル画像データベース、又はリモート画像データベースに記憶される場合がある。グラフィックスオブジェクト配置システム６０のモジュールが、特定のハードウェア構成、又はソフトウェア構成に制限されることはなく、それらは、いかなる計算環境、又は処理環境において実施してもよく、例えば、デジタル電子回路として実施され、あるいは、コンピュータハードウェア、ファームウェア、デバイスドライバ、又はソフトウェアとして実施される場合がある。
【００２４】
図５は、ユーザインタフェースモジュール６６、及びページレイアウト発生器モジュール６４が協働し、ページ上のグラフィックスオブジェクト６２のうちの幾つかについてそれぞれ、個別のレイアウトを生成する方法の一実施形態を示している。
【００２５】
各ページについて、ユーザインタフェースモジュール６６は、グラフィックスオブジェクト６２のうちの幾つかについてそれぞれ、個別のユーザ指定レイアウト６８を受け取る（図５、ブロック６８）。以下で詳しく説明するように、一部の実施形態において、ユーザは、例えばグラフィックスベースのレイアウトツールにコマンドを入力することによって、又はグラフィックスオブジェクトレイアウトの手書きモックアップ（すなわち、概略図、又はラフスケッチ）を入力し、その手書きモックアップにおける種々の要素と、グラフィックスオブジェクト６２の対応する要素との間のマッピングを行うことによって、グラフィックスオブジェクトレイアウトを生成する場合がある。
【００２６】
ページレイアウト発生器モジュール６４は、ユーザ指定レイアウトから相対レイアウト仕様を導出する（図５、ブロック７０）。本明細書において、「相対レイアウト」という用語は、ページ上のグラフィックスオブジェクトのレイアウトであって、グラフィックスオブジェクトの相対位置は指定されるが、グラフィックスオブジェクトの絶対位置は指定されないものを意味する。相対レイアウト仕様は、グラフィックスオブジェクトの相対位置を表す。相対レイアウト仕様は、グラフィックスオブジェクトの相対位置を表す任意のタイプの間取図に対応する場合がある。相対レイアウト仕様は、グラフィックスオブジェクトの相互間の関係について、又は共通の基準点（例えば、ページ上の角のポイント、又は端のポイント）に対する関係について、グラフィックスオブジェクトの相対位置を表す場合がある。
【００２７】
ページレイアウト発生器モジュール６４は、各ページ上のグラフィックスオブジェクトの最終レイアウト７２を、対応する相対レイアウト仕様に従って決定する（図５、ブロック７４）。最終レイアウト７２はそれぞれ、ページ上のグラフィックスオブジェクトのサイズ寸法、及び位置の仕様を含む。本明細書において、「レイアウトの決定」、と「最終レイアウト」は同じ意味で使用され、ページ上のグラフィックスオブジェクトのレイアウトを意味し、当該レイアウトの中に、グラフィックスオブジェクトの位置、及び寸法が指定される。一部の実施形態において、ページレイアウト発生器モジュール６４は、指定された設計制限（例えば、ページ寸法、マージン、及びガッター余白制限）に従ってグラフィックスオブジェクトのサイズ、及び位置を変更することにより、各ページについて、ユーザ指定レイアウトにおけるグラフィックスオブジェクトの相対位置を維持し、かつレイアウトの外観の美しさを向上させるようなグラフィックスオブジェクトの最終レイアウトを決定する場合がある。
【００２８】
ページレイアウト発生器モジュール６４は、グラフィックスオブジェクト７２の最終レイアウトを出力する（図５、ブロック７６）。実施形態によっては、ページレイアウト発生器モジュール６４は、特定のファイルフォーマット（例えばＰＤＦ、又はＸＭＬ）を有する仕様書の形で最終レイアウト７２を出力する場合がある。ページレイアウト発生器モジュール６４は、グラフィックスオブジェクト６２の最終レイアウト７２をユーザインタフェースモジュール６６に出力し、ユーザインタフェースモジュール６６は、その最終レイアウト７２をディスプレイ７８に表示（すなわち描画）する。実施形態によっては、ユーザインタフェースモジュール６６は、グラフィックスオブジェクト配置システム６０により自動生成されたページをユーザが対話的にブラウジングすることを許可する場合がある。さらに、ユーザインタフェース６６によれば、ユーザは、ページに対する編集を指示することができる。所与のページについて指示された編集は、ユーザインタフェースモジュール６６によって解釈される。ユーザインタフェースモジュール６６は、解釈されたユーザコマンド命令をページレイアウト発生器モジュール６４へ送信する。ページレイアウト発生器モジュール６４は、図５の方法の１以上の態様を繰り返すことにより、ユーザインタフェースモジュール６６から受信した編集に従って、１以上のページの修正された最終レイアウト７２を決定することができる。例えばユーザは、スケッチを調節し、それを再提出するかもしれない。あるいはユーザは、画像をクロッピングし、ページレイアウト発生器モジュールに、そのクロッピングされた画像を使用して、ページを再フォーマットさせる場合がある。ユーザインタフェースモジュール６６は、修正された最終レイアウト７２をユーザに提示する。その後ユーザは、修正されたページをブラウジングし、１以上の修正されたページに対する編集を指示し、又はページの一部若しくは全部を描画すべきことをシステム６０に命じる場合がある。
【００２９】
図６は、グラフィックスオブジェクト（Ａ〜Ｋ）のユーザ指定レイアウト８０の一例を示している。グラフィックスオブジェクトレイアウト８０は、グラフィックスオブジェクトＡ〜Ｋの相対位置を、グラフィックスオブジェクト相互間におけるそれらの位置、及びグラフィックスオブジェクトがレイアウトされるページ８２の特徴に対するそれらの位置の両方の両方について示している。
【００３０】
図７は、ユーザ指定レイアウト８０から導出可能な相対レイアウト仕様８４の一例を示している。相対レイアウト仕様８４は、グラフィックスオブジェクトＡ〜Ｋのうちの隣り合うもの同士の間に、パーティション８６〜１００（ディビジョンとも呼ばれる）を示している。パーティション８６〜１００は、ページ８２を複数のセルに分割し、各セルは、グラフィックスオブジェクトＡ〜Ｋのうちのちょうど一つを含む。
【００３１】
図８は、相対レイアウト仕様８４（図７参照）に従ってページレイアウト発生器モジュール６４により決定されたグラフィックスオブジェクトＡ〜Ｋの最終レイアウト１０２の一例を示している。図７に示した最終レイアウト１０２は、レンガスタイルレイアウトに対応し、当該レイアウトにおいて、ページ８２上のグラフィックスオブジェクトＡ〜Ｋの相対面積は、ページ８２の端と、グラフィックスオブジェクトＡ〜Ｋとの間における指定されたマージン空間、及びグラフィックスオブジェクトのうちの隣り合うもの同士の間における指定されたガッター余白部を除いて、画像間に空きスペースが全く生じないように選択される。
【００３２】
ＩＩＩ．相対位置に基く制御によるページ上のグラフィックスオブジェクトの配置
Ａ．はじめに
ページレイアウト発生器モジュール６４は、各ページレイアウトにおけるグラフィックスオブジェクトの相対位置、又は面積についての明確な好みによって管理され、又は制御されることができる。この機能によれば、ユーザは、グラフィックスオブジェクトの相対位置についての好みを入力することができ、それによってページレイアウト発生器モジュール６４に、ユーザのグラフィックスオブジェクト配置の一般的好みに合致するグラフィックスオブジェクトの特定のレイアウトを生成させ、同時に、より専門的に、かつより美術的に美しい形でクリーナを表示させることができる。
【００３３】
以下で詳細に説明するように、ページレイアウト発生器モジュール６４は、グラフィックスオブジェクトのユーザ指定レイアウトを受け取り、ユーザ指定レイアウトから相対レイアウト仕様を導出し、相対レイアウト仕様に従ってグラフィックスオブジェクトの最終レイアウトを決定する。
【００３４】
Ｂ．グラフィックスオブジェクトのユーザ指定レイアウトの受け取り
一般に、ページレイアウト発生器モジュール６４は、グラフィックスオブジェクトのユーザ指定レイアウトを、種々の方法で受け取ることが出来る。例えばユーザは、グラフィックベースのレイアウトツールを使用して、グラフィックスオブジェクトレイアウトを生成する場合がある。あるいはユーザは、グラフィックスオブジェクトレイアウトの手書きモックアップ（すなわち、概略図、又はラフスケッチ）の画像、並びにその手書きモックアップ上の種々のグラフィックス要素をページ上にレイアウトされるグラフィックスオブジェクトの対応するデジタルファイルにリンクするマッピング（例えば、インデックス、その他の参照情報）を入力する場合がある。
【００３５】
１．グラフィックスオブジェクトのユーザ指定レイアウトを作成するためのグラフィカルユーザインタフェース
図９は、ユーザが、選択されたグラフィックスオブジェクトの表現をページ上に配置するためのコマンドを入力することによりユーザ指定レイアウトを作成するための、ユーザインタフェース１１０の一実施形態を示している。グラフィカルユーザインタフェース１１０は一般に、レイアウトツールによって生成され、レイアウトツールは、ユーザがページ上のグラフィックス要素のサイズ、及び位置を調節出来るようにするための種々のグラフィックスベースの機能（例えば、Microsoft(R)のPowerPoint(R)、及びMicrosoft(R)のVisio(R)のようなソフトウェアアプリケーションプログラムによって一般に提供される機能）を備えたソフトウェアアプリーケーションプログラムによって実施される。
【００３６】
ユーザインタフェース１１０は、レイアウトウィンドウ１１２、及びグラフィックスオブジェクトブラウジングウィンドウ１１４を含む。レイアウトウィンドウ１１２はページ１１６を表示し、その上にユーザは、ユーザ指定グラフィックスオブジェクトレイアウトを作成することができる。グラフィックスオブジェクトブラウジングウィンドウ１１４は、ページ１１６上にレイアウトすることが可能なグラフィックスオブジェクトの解像度を下げたものからなる一列のサムネイル１１８を含む。各グラフィックスオブジェクトサムネイル１１８は、そのグラフィックスオブジェクトサムネイルにより表現されるグラフィックスオブジェクトに対応するファイルに（例えばポインタ、その他の参照情報、又はインデックスによって）リンクされる。
【００３７】
ユーザは、グラフィックスオブジェクトブラウジングウィンドウ１１４から、幾つかのグラフィックスオブジェクトサムネイル１１８を、レイアウトウィンドウ１１２にあるページ１１６上の所望の位置へドラッグすることができる。図９に示すように、ユーザは、グラフィックスオブジェクトサムネイルＡをグラフィックスオブジェクトブラウジングウィンドウ１１４からページ１１６の左上角の位置へドラッグする場合がある。グラフィックスオブジェクトサムネイルをページ１１６上に位置決めした後、ユーザは、グラフィックスオブジェクトサムネイルの縁上の一点、又は角の一点を選択し、選択した点をページ１１６上の所望の位置まで動かすことにより、グラフィックスオブジェクトサムネイルをリサイズすることができる。例えば、ユーザは、図９に破線矢印で概略的に示されているように、グラフィックスオブジェクトサムネイルＡの４つの縁をそれぞれ外向きの方向へドラッグすることにより、グラフィックスオブジェクトサムネイルＡのサイズを拡大することができる。図１０は、ユーザが、グラフィックスオブジェクトサムネイルＤをページ１１６の左端に接する位置までドラッグし、グラフィックスオブジェクトサムネイルＤのサイズを破線矩形で示すサイズまで縮小した後に生成されるレイアウトを示している。
【００３８】
ユーザがユーザ指定グラフィックスオブジェクトレイアウトを作成する際に、レイアウトツールは、ページ１１６上の種々のグラフィックスオブジェクトの位置、及びサイズを記録する間取り仕様を管理する。一部の実施形態において、間取り仕様は、ページ１１６上にレイアウトされるグラフィックスオブジェクトサムネイルのバウンディングボックスの左上角、及び右下角のページ座標を記録する場合がある。さらに、間取り仕様は、バウンディングボックスと、当該バウンディングボックスにより表現されるグラフィックスオブジェクトサムネイルにリンクされたグラフィックスオブジェクトファイルのうちの対応するものとの間のマッピングを記録する場合がある。以下で詳しく説明するように、ページレイアウト発生器モジュール６４は、間取り仕様から相対レイアウト仕様を生成する。
【００３９】
２．グラフィックスオブジェクトのユーザ指定レイアウトの画像の受け取り
図１１は、グラフィックスオブジェクト配置システム６０（図４参照）の一実施形態１２０を示している。システム１２０は、ページ上のグラフィックスオブジェクトのユーザ指定レイアウトの画像１２６から間取り仕様１２８を生成する画像分析モジュール１２４を含む、ページレイアウト発生器モジュール６４の一実施形態１２２を含む。このプロセスにおいて、画像分析モジュール１２４は、画像１２６におけるグラフィックスオブジェクトの位置、及びサイズを決定し、その情報を間取り仕様１２８として記録する。ユーザ指定レイアウトの画像１２６は通常、用紙上に生成され、デジタルスキャンにより画像ファイルに変換されたグラフィックスオブジェクトレイアウトの手書きスケッチに対応し、又はタッチスクリーンディスプレイ、若しくはグラフィックスタブレットのようなタッチパッド上に生成されるグラフィックスオブジェクトレイアウトの手書きスケッチに対応する。
【００４０】
実施形態によっては、間取り仕様は、画像１２６上にレイアウトされたグラフィックスオブジェクトのバウンディングボックスの左上角、及び右下角のページ座標を記憶する場合がある。さらに、間取り仕様は、バウンディングボックスの座標と、画像１２６上のグラフィックスオブジェクトにリンクされ、データベース１３０に記憶されたグラフィックスオブジェクトファイルのうちの対応するものとの間のマッピングを記録する場合がある。
【００４１】
実施形態によっては、画像分析モジュール１２４は、画像１２６からグラフィックスオブジェクト識別子を抽出し、（例えば、抽出された識別子をデータベース１３０内の索引として使用することにより、）抽出された識別子により示されるグラフィックスオブジェクトファイルを求めることにより、そのマッピングを決定する場合がある。他の実施形態において、ユーザは、画像１２６上の種々のグラフィックスオブジェクトと、データベース１３０に記憶された画像ファイルのうちの対応するものとの間のマッピングを、グラフィカルユーザインタフェースを介して入力する場合がある。
【００４２】
図１２は、グラフィックスオブジェクトのユーザ指定レイアウト１３２の画像の一例、及び画像分析モジュール１２４によってユーザ指定レイアウト１３２から導出された間取り仕様のグラフィック表現１３４の一例を示している。ユーザ指定レイアウト１３２上の各グラフィックスオブジェクトには、それぞれ識別子（すなわち、Ａ〜Ｋ）が付されている。画像分析モジュール１２４は、それらの識別子を抽出し、ユーザ指定レイアウト１３２上の種々のグラフィックスオブジェクトと、データベース１３０内のグラフィックスオブジェクトファイルのうちの対応するものとの間の対応関係を判断する。以下で詳細に説明するように、ページレイアウト発生器モジュール６４は、間取り仕様から相対レイアウト仕様を生成する。
【００４３】
３．グラフィックスオブジェクトのユーザ指定レイアウトに対する条件の付加
実施形態によっては、ページレイアウト発生器モジュール６４は、ユーザ指定レイアウトから相対レイアウト仕様を導出するページレイアウト発生器モジュール６４の能力を向上させるために、ユーザ指定グラフィックスオブジェクトレイアウトに対し、特定の条件を課す場合がある。例えば、以下で説明する一部の実施形態において、ページレイアウト発生器モジュール６４は、ユーザ指定レイアウトにおける水平投影、及び垂直投影に基いて、相対レイアウト仕様を解明する場合がある。そのような実施形態では、場合によっては、ページレイアウト発生器モジュール６４は、ユーザ指定グラフィックスオブジェクトレイアウトに対し、下記の条件を課す場合がある。
・ユーザ指定レイアウトにおいて、各グラフィックス要素は、完全にページ内になければならない。
・ユーザ指定レイアウトにおいて、各グラフィックス要素は、ページ上の他のいずれのグラフィックス要素とも重なってはならない。
・ユーザ指定レイアウトにおいて、グラフィックス要素は、ページの一連の領域ニ分割によって生成されるパーティションによってグラフィックス要素を互いに分離することが可能な形で配置されなければならない。ただし、各分割は、ページ１１６の矩形領域を２つのより小さな矩形領域に分割する水平分割、又は垂直分割であるものとする。
【００４４】
実施形態によっては、ユーザ指定グラフィックスオブジェクトレイアウトが上記要件の一つに違反するという判定結果に応答し、システム６０は、そのユーザ指定グラフィックスオブジェクトレイアウトを修正しなければならないことをユーザに知らせるエラーメッセージを発行する場合がある。
【００４５】
Ｃ．ユーザ指定レイアウトからの相対レイアウト仕様の導出
ページレイアウト発生器モジュール６４は、非常に様々な方法で、ユーザ指定レイアウトから相対レイアウト仕様を導出することができる。このプロセスにおいて、ページレイアウト発生器モジュール６４は、ユーザ指定レイアウトから、グラフィックスオブジェクトの相互間における、又は共通の基準点(例えば、ページの角のポイント、又は端のポイント）に対するグラフィックスオブジェクトの相対位置の表現を導出する。相対レイアウト仕様は通常、各セルが、ユーザ指定レイアウトにおいて指定されたちょうど一つのグラフィックスオブジェクトを含むものになるような、ページのセルへの分解を表す。実施形態によっては、間取りモデルは、２進空間分割モデルのような再帰分割（又は、分割）モデルに対応する場合があり、２進空間分割モデルは、ツリー構造として構成されることがある。
【００４６】
ページレイアウト発生器モジュール６４は通常、ユーザ指定グラフィックスオブジェクトレイアウトの表現を記憶する間取り仕様から、相対レイアウト仕様を導出する。実施形態によっては、間取り仕様は、ユーザが、グラフィックスオブジェクト６２のそれぞれについて指定したページの種々の矩形領域の左上角、及び右下角のページ座標を含む場合がある。ページレイアウト発生器モジュール６４は、矩形領域の位置を分析することにより、種々の矩形領域との間に一対一の関係を有する一組のセルを生成することが可能な、ページの一連のパーティション（又は、ディビジョン）を特定する。これらのパーティションは通常、一連のパーティションを記録する階層ツリー構造として編成され、当該一連のパーティションから、矩形領域に対応する一組のセルを決定することができる。実施形態によっては、ページレイアウト発生器モジュール６４は、相対レイアウト仕様をそれぞれ個別の二分木データ構造に記憶する場合があり、二分木データ構造は、グラフィックスオブジェクトに対応するリーフノード、及び対応するページのパーティションに対応する内側ノードを有する。
【００４７】
実施形態によっては、ページレイアウト発生器モジュール６４は、ユーザ指定レイアウトの水平ヒストグラムプロファイル、及び垂直ヒストグラムプロファイルを求め、グラフィックスオブジェクトを相互に分離するパーティションを求めることにより、ユーザ指定レイアウトからグラフィックスオブジェクトの相対レイアウトを解明する場合がある。
【００４８】
一例として、図１３Ａは、ページ１４２上のグラフィックスオブジェクト（すなわち、グラフィックスオブジェクトＬ、Ｍ、Ｎ、Ｏ）のユーザ指定レイアウト１４０の一例を示している。図１３はさらに、水平ヒストグラムプロファイル１４４、及び垂直ヒストグラムプロファイル１４６も示している。水平ヒストグラムプロファイル１４４は、グラフィックスオブジェクトＬ〜Ｏのカウント数の垂直投影から、水平軸（ｘ）に沿った位置の関数として計算される。垂直ヒストグラムプロファイル１４４は、グラフィックスオブジェクトＬ〜Ｏのカウント数の水平投影から、垂直軸（ｙ）に沿った位置の関数として計算される。これらの実施形態によれば、ページレイアウト発生器モジュール６４は、水平ヒストグラム１４４、及び垂直ヒストグラム１４６における極小値に基いて、ページ１４２を分割するパーティションを決定する。
【００４９】
一実施形態において、ページレイアウト発生器モジュール６４は、まず、図１３Ａ、及び図１３Ｂに示すように、ページ１４２の全体を含むバウンディングボックス１５２に関連する１つのノード１５０を有する初期ツリー１４８を生成する。ページレイアウト発生器モジュール６４は、ヒストグラム１４４におけるゼロ値を識別し、識別されたゼロ値のうちの１つを選択し、選択されたゼロ値の位置にあるパーティションを使用して、現在ノード１５０を２つのノードに分割する。図１３Ａに示す例において、ヒストグラム１４４、１４６には、単一のゼロ値１５４しか存在しない。ページレイアウト発生器モジュール６４は、ゼロ値１５４の位置に水平パーティションを生成する（図１４Ａ参照）。水平パーティション（Ｈ）は、ノード１５０を２つのノード１５８、１６０に分割し、ノード１５８、１６０は、図１４Ａ、及び図１４Ｂに示すようにンディングボックス１６６、１６４に関連する。
【００５０】
もし、あるノードがグラフィックスオブジェクトを１つしか有しないバウンディングボックスに関連する場合、そのノードは、それ以上分割されない。例えば、図１４Ａ、及び図１４Ｂに示す分割プロセスの段階において、ノード１５８は、バウンディングボックス１６４に関連し、従って、それ以上分割されない。もし、あるノードが、２以上のグラフィックスオブジェクトを含むバウンディングボックスに関連する場合、そのノードは、現在ノードとして指定され、プロセスは繰り返される。図１４Ａ、及び図１４Ｂに示す分割プロセスの段階において、ノード１６０は、バウンディングボックス１６６に関連し、バウンディングボックス１６６は、３つのグラフィックスオブジェクトＭ〜Ｏを含む。従って、この段階の結果、ノード１６０には、現在ノードのラベルが付され、プロセスは繰り返される。
【００５１】
ノード１６０について分割プロセスを繰り返すプロセスの一例として、ページレイアウト発生器モジュール６４は、現在ノード１６０に関連するバウンディングボックス１６６におけるグラフィックスオブジェクトの水平ヒストグラム、及び垂直ヒストグラムを求める場合がある。ページレイアウト発生器モジュール６４は、水平ヒストグラムにおける２つのゼロのうちの最初のものを選択し、現在ノード１６０を２つのノード１７２、１７４に分割する垂直パーティション１７０を使用して、現在ノード１６０を分割する（図１５Ａ参照）。その後、ページレイアウト発生器モジュール６４は、グラフィックスオブジェクトＮ、及びＯを含み、かつ現在ノード１７４に関連するバウンディングボックスにおけるグラフィックスオブジェクトの水平ヒストグラム、及び垂直ヒストグラムを求める（図１５Ｂ参照）。ページレイアウト発生器モジュール６４は、水平ヒストグラムにおけるゼロのみを選択し、現在ノード１７４を２つのノード１８０、１８２に分割する垂直パーティションを使用して、現在ノード１７４を分割する（図１５Ｂ参照）。図１５Ｂに示すツリー構造の例において、内部ノード１５０、１６０、１７４は、パーティション１５６、１７０、１７８にそれぞれ対応するのに対し、リーフノード１５８、１７２、１８０、１８２は、グラフィックスオブジェクトＬ、Ｍ、Ｎ、Ｏにそれぞれ対応する。
【００５２】
Ｄ．相対レイアウト仕様に基づくグラフィックスオブジェクトの最終レイアウトの決定
１．概要
ページレイアウト発生器モジュール６４は、相対レイアウト仕様から、ページ上のグラフィックスオブジェクトの最終配置を決定、又は生成する。上で説明したように、相対レイアウト仕様は、非常に様々な間取りモデルのうちの任意の１つを反映するデータ構造に対応する場合がある。下記の実施形態は、２進空間分割モデルに対応する相対レイアウト仕様を例として説明され、当該モデルに従って、グラフィックスオブジェクトの相対位置が、二分木構造に記録される。
【００５３】
２．ページ上のグラフィックスオブジェクトの最終配置の生成
実施形態によっては、ページレイアウト発生器モジュール６４は、ページ上の種々のグラフィックスオブジェクトの相対位置を表す個別のツリー構造を受け取る場合がある。ツリー構造の各リーフノードは、アスペクト比値（ａ）を有し、厳密面積スタイルレイアウトの場合、さらに公称サイズ値（ｅ）を有する。ツリー構造の各内部ノードは、ページ上での水平分割と垂直分割のいずれかを示す。ページレイアウト発生器モジュール６４は、各ページ上の種々のグラフィックスオブジェクトの面積を求め、その後、ページ空間の正確な領域をツリー構造の各ノードに割当てる。ページの割当て済み領域は、対応するツリー構造と同様に入れ子構造を成す。本明細書において、この割当て済み領域は、「セル」と呼ばれる。実施形態によっては、セルが分かった後、そのセルに割当てられるグラフィックスオブジェクトの位置は、そのグラフィックスオブジェクトをセル内の中央に位置決めすることによって決定される場合がある。
【００５４】
ａ．グラフィックスオブジェクトの面積の決定
グラフィックスオブジェクトの面積は、所望の精度、所望のレイアウトスタイル、及び利用可能な計算リソースに応じて、バウンディングボックスに基く面積決定法、パスに基く面積決定法、又は線形システムに基く面積決定法によって決定される。
【００５５】
ｉ．バウンディングボックスに基くグラフィックスオブジェクト面積の決定
例示的実施形態として、バウンディングボックス決定プロセスの目的は、所与のツリー構造における各内部ノードについて、アスペクト比値、及び公称サイズ値を計算することである。各バウンディングボックスは、そのバウンディングボックスに包含されるボックスによって決定される。
【００５６】
後で詳しく説明するように、バウンディングボックスは、グラフィックスオブジェクトのアスペクト比、及び公称サイズを使用して計算される。厳密面積スタイルレイアウトの場合、各グラフィックスオブジェクトの公称サイズは、間取り仕様上の対応する矩形の面積に等しくなるようにセットされる場合がある。実施形態によっては、バウンディングボックス特性評価プロセスは、リーフノードから開始され、図１６に示すように深さ優先順で、ルートノードへ向けて実行される場合がある。
【００５７】
任意の内部ノードのアスペクト比、及び公称サイズを求める式は、下記のとおりである。一般に、アスペクト比ａ、及び公称サイズｅを有する任意の画像バウンディングボックスの場合、
【数１】
及び
【数２】
の大きさがそれぞれ、画像バウンディングボックスの公称高さ、及び公称幅となる。任意の内部ノードについてのアスペクト比ａ、及び公称サイズｅは、その内部ノードの２つの子ノードのアスペクト比、および公称サイズの関数となる。下記の式において、ａｒ、及びｅｒは、右側子ノードのアスペクト比、及び公称サイズであり、ａｌ、及びｅｌは、左側子ノードのアスペクト比、及び公称サイズである。従って、もし、右側子ノードと左側子ノードが横並びに配置された場合、それらを取り囲むバウンディングボックスのアスペクト比、及び公称サイズは、下記のようになる。
【００５８】
【数３】
【００５９】
【数４】
【００６０】
ただし、
【数５】
である。
【００６１】
式（１）におけるアスペクト比は、大きい方の公称高さを２つの公称幅の合計で割った比であり、式（２）における公称サイズは、大きい方の公称高さと、２つの公称幅の合計との積である。式（３）における最大値を見付けることにより、２つの子ノードボックスのうちのいずれが名目上高く、従って、親ノードボックスの高さを支配するのかを判断することができる。
【００６２】
もし、２つの子ノードが、順に重ねて配置されたボックスを表す場合、それらを包含するバウンディングボックスのアスペクト比、及び公称サイズは、下記のようになる。
【００６３】
【数６】
【００６４】
【数７】
【００６５】
ただし、
【数８】
である。
【００６６】
この場合、式（６）から、２つの子ノードボックスのうちのいずれの幅が名目上広く、従って親ノードボックスの幅を支配するのかを判断することができる。
【００６７】
ルートノードのバウンディングボックスは、対応するツリー構造により指定されるページのレイアウト全体の形、及び公称サイズを有する。本明細書において、ルートノードのバウンディングボックスは、「主バウンディングボックス」と呼ばれる。
【００６８】
主バウンディングボックスのアスペクト比、及び公称サイズが分かっている場合、グラフィックスオブジェクトｉについてのバウンディングボックスに基づく面積Ａｉは、下記のように計算される。
【００６９】
【数９】
【００７０】
ただし、ｅｉ、及びｅｐｂｂは、グラフィックスオブジェクトｉ、及び主バウンディングボックスのそれぞれの公称サイズであり、Ａｐｂｂは、下記のように計算される主バウンディングボックスの面積である。
【００７１】
【数１０】
【００７２】
ただし、Ａｐａｇｅは、使用可能なページ空間の面積である。
【００７３】
図１６は、再帰プロセスの一実施形態を示すフロー図であり、ページレイアウト発生器モジュール６４は、この再帰プロセスにより、ツリー構造の種々のノードについて、バウンディングボックスの相対的な高さ寸法、及び幅寸法を計算する。
【００７４】
このプロセスは、現在ノードとしてのルートノードから開始される。現在ノードが終端ノードであるか否かを判断する(図１６、ブロック４８０）。もし現在ノードが終端ノードであった場合、関連グラフィックスオブジェクトの公称高さ、及び公称幅を有するバウンディングボックスを決定する（図１６、ブロック４８２）。もし現在ノードが終端ノードではなかった場合、現在ノードの２つの子ノード（すなわち、左側子ノード、及び右側子ノード）を同じ再帰プロセスに提出する（図１６、ブロック４８４、４８６）。現在ノードについてのバウンディングボックスを形成するために、下記のように、２つの子ノードのバウンディングボックスを結合する。ページレイアウト発生器モジュール６４は、現在ノードが水平分割であるか、それとも垂直分割であるかを判断する（図１６、ブロック４８８）。もし現在ノードが水平分割を表している場合、バウンディングボックスの公称幅は、２つの子ノードのバウンディングボックスのうちの幅の広い方の公称幅にセットされ（図１６、ブロック４９０）、バウンディングボックスの公称高さは、２つの子ノードのバウンディングボックスの公称高さの合計にセットされる。もし現在ノードが垂直分割を表している場合、（図１６、ブロック４８８）、バウンディングボックスの公称高さは、２つの子ノードのバウンディングボックスのうちの高い方の公称高さにセットされ（図１６、ブロック４９４）、バウンディングボックスの公称幅は、２つの子ノードのバウンディングボックスの公称幅の合計にセットされる。このプロセスは、ルートノードについてのバウンディングボックスの計算が完了するまで続けられる。
【００７５】
ｉｉ．パスに基くグラフィックスオブジェクト面積の決定
パスに基く面積決定法によれば、ページレイアウト発生器モジュール６４は、２００７年６月２７日に出願された米国特許出願第１１／７６９，６７１号の図９〜図１０Ｊ、及び図２４のブロック４１０に関係して以下に記載するパス生成プロセスに従って、ツリー構造を通るパスＰｉを生成する。
【００７６】
ページレイアウト発生器モジュール６４は、各パスＰｉについてパス長さＬ（Ｐｉ）を計算する。もしパスＰｉが垂直であった場合、その長さは、下記のようになる。
【００７７】
【数１１】
【００７８】
グラフィックスオブジェクトの高さ（ＨＧＯ）は、下記のように書き表すことができる。
【００７９】
【数１２】
【００８０】
ただし、Ａは、グラフィックスオブジェクトの面積であり、ａは、高さを幅で割った比として定義されるアスペクト比であり、Ｑは、面積の平方根である。従って、もしＰｉが垂直パスであれば、その長さは下記のように書き表すことができる。
【００８１】
【数１３】
【００８２】
ただし、Ｋｉは、式（９）における最初の２つの項（すなわち、パスＰｉに沿った全ての固定距離）の合計であり、Ｑｉ，ｊは、パスＰｉ上の第ｊの可変面積オブジェクトの面積の平方根であり、ａｉ，ｊは、パスＰｉ上の第ｊの可変面積オブジェクトのアスペクト比である。なお、加算項は、パスＰｉ上の可変面積グラフィックスオブジェクトの高さの合計に対応する。
【００８３】
同様の計算により、水平パスＰｉの長さは、下記のように書き表すことができる。
【００８４】
【数１４】
【００８５】
ただし、Ｋｉは、パスＰｉに沿った固定面積グラフィックスオブジェクトの水平固定距離、及び幅の合計である。厳密面積スタイルレイアウトの場合、各可変面積グラフィックスアセンブリには、公称サイズが割当てられ、公称サイズは変数ｅで表される。マルチ要素グラフィックスオブジェクトの場合、当該オブジェクトは、構成要素として２以上の単一要素グラフィックスオブジェクト（例えば、ビデオからの一連のキーフレームなど）を含み、単一の集合体公称サイズが、グラフィックスオブジェクト全体に割当てられ、マルチ要素グラフィックスオブジェクト内の個々のグラフィックスオブジェクトの公称サイズは、その集合体公称サイズをそのグラフィックスオブジェクト内のグラフィックスオブジェクトの数で割ったサイズに等しくなるようにセットされる。このセクションの残りの部分では、パスＰｉ上の各グラフィックスオブジェクトｊが、正の公称サイズｅｊを有する単一要素グラフィックスオブジェクトであるものと仮定する。公称サイズは実際の面積に比例するので、上で定義された変数Ｑは、（絶対面積ではなく）公称サイズの平方根を反映するように、下記のように一般化することができる。
【００８６】
【数１５】
【００８７】
ただし、ｇは、ｇ２に公称サイズを乗じたものが、絶対測定可能面積（例えば、平方インチ）になるような、正のスカラー値である。Ｑを
【数１６】
で割った比は、全ての可変面積グラフィックスオブジェクトにわたって一定であり、従って、ページ上の全ての可変面積グラフィックスオブジェクトについて、同じ値のｇが使用される。従って、上式（１１）、及び式（１２）において、Ｑを
【数１７】
に置き換え、ｇを加算項の外に出すと、式は下記のようになる。
【００８８】
【数１８】
【００８９】
【数１９】
【００９０】
ただし、ｅｉ，ｊは、パスＰｉ上の第ｊの可変面積グラフィックスオブジェクトの公称サイズである。
【００９１】
もしＰｉが垂直パスであり、ページ上の使用可能エリアの高さがＨＰＡＧＥである場合、下記の式をｇｉについて解くことにより、使用可能エリアの高さが高い限り、Ｐｉが正確であるときの値が得られる。
【００９２】
【数２０】
【００９３】
同様に、もしＰｉが水平パスであり、使用可能エリアの幅がＷＰＡＧＥである場合、下記の式をｇｉについて解くことにより、そのパスが、使用可能エリアの幅全体にわたってちょうど適合するときの値が得られる。
【００９４】
【数２１】
【００９５】
ツリー構造により実施される各水平パスについて、ＷＰＡＧＥ＞Ｋｉであるものと仮定し、さらに、ツリー構造により実施される各垂直パスについて、ＨＰＡＧＥ＞Ｋｉであるものと仮定する。これは、各パスに沿った固定距離がそれぞれの寸法内に適合することを意味し、従って、ツリー構造によって表されるレイアウトは「実現可能」であり、全てのグラフィックスオブジェクトがページ上に収まるような、可変面積グラフィックスオブジェクトの面積について正の値が存在することを意味する。
【００９６】
一実施形態において、可変面積グラフィックスオブジェクトの面積は、可能な限り広く作成されるが、それでも、Ｐｉが垂直パスであるか、それとも水平パスであるかに応じて式（１６）又は式（１７）を使用し、（各パスＰｉについて）ｇｉについて解くことにより、全てのグラフィックスオブジェクトをページの使用可能エリアに完全に収めることができる。上記のように、レイアウトが実現可能なものであることを前提としているので、ｇｉについての各解は正になる。もし、ｇ＊を全てのパスにわたる最小の解として下記のように定義した場合、
【数２２】
第ｊの可変面積グラフィックスオブジェクトの面積Ａｊは、下記のように計算される。
【数２３】
ただし、ｅｉは、第ｊの可変面積グラフィックスオブジェクトに割当てられた公称サイズである。
【００９７】
ｉｉｉ．線形システムに基くグラフィックスオブジェクト面積の決定
レンガスタイルレイアウトの場合、グラフィックス要素の面積は、まずＱの値を計算することによって決定される。Ｑの値が分かった後、それらを二乗し、絶対測定可能面積（例えば、平方インチを単位として表される）を求める。Ｑの値は、次の２つの仮説に基いて計算される：（１）グラフィックス要素が占めるエリアの高さは、ページ上の使用可能エリアの高さに等しくなるように拘束される。（２）グラフィックス要素が占めるエリアの幅は、ページ上の使用可能エリアの幅に等しくなるよう拘束される。大抵の場合、仮説（Ｉ）と仮説（ＩＩ）のいずれか一方のみが、実現可能な解を生成する。なぜなら、他方の仮説においては、他方の（拘束されていない）寸法が、使用可能空間より大きくなるからである。最終的な一組のグラフィックス要素エリアを生成するために、実現可能な解を生成する仮説が選択される。
【００９８】
仮説（Ｉ）と仮説（ＩＩ）のいずれにおいても、Ｑの値は、Ｎ個の未知数を有する線形システムの式の解として計算される。ただし、Ｎは、グラフィックス要素の数である。Ｎ−１個の式はそれぞれ、完全なツリー構造の内部ノードから得られる。なぜなら、Ｎ個のグラフィック要素を有するツリーには、ちょうど（Ｎ−１）個の内部ノードが存在するからである。
【００９９】
垂直分割、又は領域切断を表す内部ノードの場合、対応する式は、まずその内部ノードの２つの子ノードのそれぞれから１つ、合わせて２つの垂直パスを得て、それらの長さを同じ長さにセットすることによって導出される。上記の式（１１）を参照すると、左側子ノードからの垂直パスをＰＬで表し、右側子ノードからの垂直パスをＰＲで表した場合、対応する式は、下記のようになる。
【０１００】
【数２４】
【０１０１】
ただし、変数ｊは、ＰＲ上でグラフィックスオブジェクトを索引付けし、変数ｋは、ＰＬ上でグラフィックスオブジェクトを索引付けする。式（２０）を変形すると、下記のようになる。
【０１０２】
【数２５】
【０１０３】
この状況は、水平分割、又は領域切断を表す内部ノードの場合に似ている。２つの水平パスを得て、それらの長さを同じ長さにセットすると、下記の式が得られる。
【０１０４】
【数２６】
【０１０５】
各内部ノードについて式（２０）又は（２２）の形の式を作成することにより、Ｎ個の未知数について、Ｎ−１個の式が得られる。
【０１０６】
仮説Ｉの場合、第Ｎの式は、ルートノードからの任意の垂直パスの長さを、使用可能エリアの高さに等しくなるようにセットすることによって得られる。仮説ＩＩの場合、第Ｎの式は、ルートノードからの任意の水平パスの長さを、使用可能エリアの幅に等しくなるようにセットすることによって得られる。
【０１０７】
仮説Ｉと仮説ＩＩのいずれの場合も、Ｎ個の式は、行列ベクトル（Ａｘ＝ｂ）の形で書かれる。行列は、ゼロ、グラフィックス要素アスペクト比の正、及び負の平方根、並びにグラフィックス要素アスペクト比の平方根の正の逆数、及び負の逆数のみを含む。ベクトルｘのＮ個の要素は、Ｑ個の変数である。ベクトルｂのＮ個の要素のうち、（Ｎ−１）個は、式（２０）、又は式（２１）の右辺に従って計算され、残りは、使用可能エリアの高さ（仮説Ｉ）、又は幅（仮説ＩＩ）（から対応する行を得るために使用されるパスに沿った固定距離を差し引いたもの）に等しくなる。逆行列（Ａ）＊ｂを計算することにより、Ｑ値のベクトルが得られる。
【０１０８】
ｂ．ツリー構造におけるノードの周りのバウンディングボックスの決定
絶対面積を計算した後、ツリー構造における各ノードの周りにバウンディングボックスを描画する。このプロセスを達成するために必要な実際のステップは、２点を除き、図１６に示したようなバウンディングボックスに基く面積決定に関係して上で説明したバウンディングボックスを計算するためのプロセスと全く同様である。第１に、公称サイズは偶然に、実際のグラフィックスオブジェクト面積と等しくなることがある。第２に、内部ノードに割当てられる間隔は、無視されるのではなく、代わりにブロック４９２、及び４９６の計算において合計に加算される。
【０１０９】
ｃ．ページ空間のグラフィックスオブジェクトへの割当て
【０１１０】
ｉ．ページ空間割当てプロセスの概要
実施形態によっては、ページ上の空白領域をノードに割当てるプロセスは、ページを複数のセルに分割し、各グラフィックスオブジェクトをそれぞれのセルの中に位置決めすることを含む場合がある。ページのセルへの分割は、まずページの使用可能エリア全体を第１の矩形とし、ページを複数の矩形に分割することにより開始される。各分割は、ルートノードから開始し、横型探索の順序で各内部ノードについて１本のラインセグメントを描くことにより達成される。
【０１１１】
垂直分割に対応する内部ノードの場合、ページレイアウト発生器モジュール６４は、使用可能領域の幅に沿って水平位置ｘを選択する。これを式で表すと例えば、ｘ∈（０，１）のようになる。ただしｘ＝０は、使用可能領域における最も左側の位置を表し、ｘ＝１は、使用可能領域における最も右側の位置を表す。この場合、下記のようになる。
【０１１２】
【数２７】
【０１１３】
ただし、ａｌ、ｅｌ、及びａｒ、ｅｒは、内部ノードの左側子ノード、及び右側子ノードについてのバウンディングボックスのアスペクト比、及び面積である。この式は、幅を比率として直接使用する。水平分割の場合の同様の式は、高さを使用する。すなわち、もしｙ＝０が最下位置を表し、ｙ＝１が最上位置を表すものとし、使用可能空間の高さ方向における垂直位置をｙ∈（０，１）で表した場合、下記のようになる。
【０１１４】
【数２８】
【０１１５】
ただし、ａｂ、ｅｂ、及びａｔ、ｅｔは、内部ノードの最下部、及び最上部の子ノードについてのバウンディングボックスのアスペクト比、及び面積である。
【０１１６】
ｉｉ．ページ空間をグラフィックスオブジェクトに割当てるプロセスの詳細
図１７は、ページ上の空きの物理領域を現在のツリー構造のルートノードに割当てる方法の一実施形態を示している。この方法に従って、レイアウトスタイルは決定される（図１７、ブロック６３０）。厳密面積スタイルレイアウトの場合、ページの使用可能エリア全体をルートノードに割当てる（図１７、ブロック６３２）。レンガスタイルレイアウトの場合、ルートノードに割当てられるページ空間は、ルートノードに関連するバウンディングボックスの高さ、及び幅を有する（図１７、ブロック６３４、６３６）。次に、ルートノードに割当てられた領域を、使用可能なページ空間の中央に位置決めする（図１７、ブロック６３８）。
【０１１７】
図１８は、空きページ領域をツリー構造のあるノードの子ノードに割当てる方法の一実施形態を示している。このプロセスでは、各内部ノードに割当てられる空き領域は、その内部ノードの２つの直接の子ノードの間で分割される。この分割は、現在のツリー構造のルートノードを現在ノードにセットし、再帰プロセスを実施することにより達成される。
【０１１８】
再帰プロセスでは、現在ノードが終端ノードであるか否かを判断する（図１８、ブロック６４０）。もし現在ノードが終端ノード（すなわち、リーフノード）であった場合、プロセスは終了する（図１８、ブロック６４２）。もし現在ノードが内部ノードであった場合は、現在ノードが２以上の単一要素グラフィックスオブジェクトを含むマルチ要素グラフィックスオブジェクト（ＧＯ）に対応するツリーのルートノードであるか否かを判断する（図１８、ブロック６４４）。もしそうであれば、現在ノードに割当てられた領域の高さ、及び幅を、現在ノードについて前回計算されたバウンディングボックスの高さ、及び幅と等しくなるように再割当てすることによって、現在ノードに割当てられた領域を圧縮し（図１８、ブロック６４６）、その領域の位置を、現在ノードに前回割当てられた領域の中央に位置決めする。レンガスタイルレイアウトの場合、これは何も影響を及ぼさない。厳密面積レイアウトの場合、これは、２以上のグラフィックス要素（例えば、一連のキーフレームなど）を含むグラフィックスアセンブリにおいて、複数の画像をまとめて引き抜く作用を有する。
【０１１９】
もし現在ノードがマルチ要素グラフィックスオブジェクトに対応するツリーのルートノードではないと判断された場合（図１８、ブロック６４４）、現在ノードの左側子ノード、及び右側子ノードについての空き領域の高さ、及び幅を計算する（図１８、ブロック６４８）。
【０１２０】
もし現在ノードが水平ページ分割であった場合、右側子ノード、及び左側子ノードに割当てられる領域の高さ（ＨＲ，ＨＬ）は、下記の式から得られる。
【０１２１】
【数２９】
【０１２２】
【数３０】
【０１２３】
ただし、ＨＮＯＤＥは、現在ノード空き領域の高さであり、Ｓは、ノード間隔であり、Ｌは、左側子ノードバウンディングボックスの高さであり、Ｒは、右側子ノードバウンディングボックスの高さである。左側子ノード、及び右側子ノードに割当てられる領域の幅は、現在ノードに割当てられた領域の幅に等しくなるようにセットされる。
【０１２４】
もし現在ノードが垂直ページ分割であった場合、右側子ノード、及び左側子ノードに割当てられる領域の幅（ＷＲ，ＷＬ）は、下記の式から得られる。
【０１２５】
【数３１】
【０１２６】
【数３２】
【０１２７】
ただし、ＷＮＯＤＥは、現在ノード空白領域の幅である。左側子ノード、及び右側子ノードに割当てられる領域の高さは、現在ノードに割当てられた領域の高さに等しくなるようにセットされる。
【０１２８】
もし現在ノードが水平ページ分割であった場合（図１８、ブロック６５０）、左側子ノードの空き領域は、現在ノードに割当てられた空き領域の上側境界に可能な限り近づけて配置される（図１８、ブロック６５２）。右側子ノードの空き領域は、現在ノードに割当てられた空き領域の下側境界に可能な限り近づけて配置される（図１８、ブロック６５４）。
【０１２９】
もし現在ノードが垂直分割であった場合（図１８、ブロック６５０）、左側子ノードの空き領域は、現在ノードに割当てられた空き領域の左側境界に可能な限り近づけて配置される（図１８、ブロック６５６）。右側子ノードの空き領域は、現在ノードに割当てられた空き領域の右側境界に可能な限り近づけて配置される（図１８、ブロック６５８）。
【０１３０】
上記のプロセスを繰り返すことにより、種々の空き領域が、左側子ノードの子ノード（図１８、ブロック６６０）、及び右側子ノードの子ノード（図１８、ブロック６６２）に割当てられる。このプロセスは、ページ上の空き領域が現在ノードの全ての子ノードに（直接的、又は他の形で）割当てられるまで繰り返される。
【０１３１】
３．グラフィックスオブジェクトの最終レイアウトの出力
ページレイアウト発生器モジュール６４は通常、最終レイアウトを表すデータ構造（例えば、表、又はリスト）を含む仕様書の形で、最終レイアウトを出力する。実施形態によっては、この仕様書は、ＸＭＬ（拡張マークアップ言語）ファイルフォーマットの形で機械読取可能な媒体に記憶される場合がある。仕様書を実際に実施するのに適した記憶装置には、あらゆる形の不揮発性コンピュータ読取可能媒体、及び揮発性コンピュータ読取可能媒体が含まれ、限定はしないが、例えば、ＥＰＲＯＭ、ＭＥＥＰＲＯＭ、及びフラッシュメモリデバイスのような半導体メモリデバイス、内蔵ハードディスクやリムーバブルディスクのような磁気ディスク、光磁気ディスク、及びＣＤ−ＲＯＭが挙げられる。最終レイアウト仕様は、ユーザインタフェースモジュール６６、又は印刷モジュールにより、最終レイアウトを表示装置に描画し、又は印刷媒体（例えば、用紙）に印刷するために使用される場合がある。
【０１３２】
ＩＶ．グラフィックスオブジェクト配置システムの例示的アーキテクチャ
グラフィックスオブジェクト配置システム６０の種々の実施形態は、１以上の個別のモジュール（又は、データ処理コンポーネント）によって実施され、それらが、何らかの特定のハードウェア、ファームウェア、又はソフトウェア構成に制限されることはない。例示的実施形態において、モジュールは、いかなる計算環境、又はデータ処理環境において実施されてもよく、例えば、デジタル電子回路（例えば、デジタル信号プロセッサ（ＤＳＰ）のような特定用途向け集積回路）として実施され、あるいはコンピュータハードウェア、ファームウェア、デバイスドライバ、又はソフトウェアとして実施される場合がある。実施形態によっては、複数のモジュールの機能が、単一のデータ処理コンポーネントとして結合される場合がある。また、実施形態によっては、モジュールの１以上の機能はそれぞれ、一組のデータ処理コンポーネントによって実施される場合がある。
【０１３３】
実施形態によっては、グラフィックスオブジェクト配置システム６０の種々の実施形態により実施される方法を実施するための処理命令（例えば、コンピュータソフトウェアのような機械読取可能なコード）、及び当該処理命令が生成するデータは、１以上の機械読取可能な媒体に記憶される場合がある。それらの命令、及びデータを実際に実施するのに適した記憶装置には、あらゆる形の不揮発性コンピュータ読取可能メモリが含まれ、例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、及びフラッシュメモリデバイスのような半導体メモリデバイス、内蔵ハードディスクやリムーバブルハードディスクのような磁気ディスク、光磁気ディスク、ＤＶＤ−ＲＯＭ／ＲＡＭ、及びＣＤ−ＲＯＭ／ＲＡＭなどが含まれる。
【０１３４】
一般に、グラフィックスオブジェクト配置システム６０の種々の実施形態は、非常に様々な電子装置のうちのいずれの形で実施してもよく、例えば、デスクトップコンピュータ、ワークステーションコンピュータ、ビデオレコーディングデバイス（例えば、ＶＣＲ、及びＶＤＲ）、ケーブル、又は、有料ビデオ番組をデコードし、再生する機能を備えた衛星セットトップボックス、及びデジタルカメラデバイスの形で実施される場合がある。処理リソース、及び記憶リソースの効率的使用のために、グラフィックスオブジェクト配置システム６０は、実施形態によっては、控えめな処理能力、及び控えめな記憶容量を有する比較的小さく、安価な構成要素を使用して実施される場合がある。その結果、そのような実施形態は、サイズ、処理能力、及び記憶容量に大きな制限がある小型カメラ環境への組み込みに非常に適し、限定はしないが例えば、携帯電子装置（例えば、携帯電話機、コードレス電話機、スマートカードのような携帯メモリデバイス、携帯情報端末（ＰＤＡ）、半導体デジタルオーディオプレイヤ、ＣＤプレイヤ、ＭＣＤプレイヤ、ゲームコントローラ、ポケットベル、及び小型静止画カメラ、又は小型ビデオカメラ）、ｐｃカメラ、及び他の組み込み環境への組み込みに非常に適している。
【０１３５】
図１９は、本明細書に記載するグラフィックスオブジェクト配置システム７６０の実施形態のうちのいずれかを含むコンピュータシステム７６０の一実施形態を示している。コンピュータシステム６０は、処理ユニット７６２（ＣＰＵ）、システムメモリ７６４、並びに、処理ユニット７６２をコンピュータシステム７６０の種々のコンポーネントに接続するシステムバス６６を含む。処理ユニット７６２は通常、１以上のプロセッサを含み、各プロセッサは、種々の市販のプロセッサのうちのいずれの形態のものであってもよい。システムメモリ７６４は通常、コンピュータシステム７６０の開始ルーチンを含む基本的な入出力システム（ＢＩＯＳ）を記憶するリードオンリーメモリ（ＲＯＭ）と、ランダムアクセスメモリ（ＲＡＭ）とを含む。システムバス７６６は、メモリバスであっても、周辺機器用バスであっても、ローカルバスであってもよく、ＰＣＩ、ＶＥＳＡ、マイクロチャネル、ＩＳＡ、及びＥＩＳＡのような種々のバスプロトコルのうちのいずれかと互換性を有するものであってもよい。コンピュータシステム７６０はさらに、永久記憶装置７６８（例えば、ハードディスクドライブ、フロッピーディスクドライブ、ＣＤＲＯＭドライブ、磁気テープドライブ、フラッシュメモリデバイス、及びデジタルビデオディスク）を含み、永久記憶装置７６８は、システムバス７６６に接続され、データ、データ構造、及びコンピュータ実行可能命令のための不揮発性記憶装置、又は永久記憶装置として機能する１以上のコンピュータ読取可能媒体を含む。
【０１３６】
ユーザは、１以上の入力デバイス７７０（例えば、キーボード、コンピュータマウス、マイクロフォン、ジョイスティック、及びタッチパッド）を使用して、コンピュータ７６０と対話（例えば、コマンド、又はデータの入力を）することができる。情報は、ディスプレイモニタ７７２に表示されたグラフィカルユーザインタフェース（ＧＵＩ）を通してユーザに表示され、ディスプレイモニタ７７２は、ディスプレイコントローラ７７４によって制御される。また、コンピュータシステム７６０は通常、スピーカ、及びプリンタのような周辺出力装置をさらに含む。１以上のリモートコンピュータが、ネットワークインタフェースカード（ＮＩＣ）７７６を通してコンピュータシステム７６０に接続される場合がある。
【０１３７】
図１２に示すように、システムメモリ７６４はさらに、グラフィックスオブジェクト配置システム７６０、ＧＵＩドライバ７７８、並びに、グラフィックスオブジェクト６２、中間処理データ、及び出力データに対応するグラフィックスオブジェクトファイルを有するデータベース７８０を記憶する。実施形態によっては、グラフィックスオブジェクト配置システム７６０は、グラフィックスオブジェクトのユーザ指定レイアウトの作成、及びグラフィックスオブジェクトの最終レイアウトの作成を制御するために、ＧＵＩドライバ７７８、及びユーザ入力７７０に接続される場合がある。実施形態によっては、グラフィックスオブジェクト配置システム７６０は、ディスプレイモニタ７７２上に画像データを描画し、ユーザ指定グラフィックスオブジェクトレイアウト、及びそれら自体のグラフィックスオブジェクトに対する種々の処理を実施するグラフィックスアプリケーションプログラムをさらに含む場合がある。
【０１３８】
Ｖ．結び
本明細書に詳細に記載される実施形態によれば、グラフィックスオブジェクトを１以上のページ上に配置する種々の方法が得られる。これらの実施形態は、各レイアウト（又は、配置）におけるグラフィックスオブジェクトの相対位置についての明確な好みによって管理され、又は制御されることができる。同時に、これらの実施形態は、それらの好みから、指定された設計上の制限（例えば、ページ寸法、マージン、及びガッター余白制限）に従ってグラフィックスオブジェクトの最終レイアウトを自動生成することができる。このように、ユーザは、より専門的に、かつより美術的に美しい形でクリーナを表示しながら、それらの実施形態を、ユーザの一般的なグラフィックス配置の好みに合致するグラフィックスオブジェクトの特定のレイアウトに導くことができる。
【０１３９】
他の実施形態は、特許請求の範囲内である。
【技術分野】
【０００１】
［関連出願の相互参照］
本願は、下記の同時係属出願にも関連し、各出願は、参照により本明細書に援用される。
・２００３年９月３０日に出願された米国特許出願第１０／６７５，７２４号
・２００３年９月３０日に出願された米国特許出願第１０／６７５，８２３号
・２００５年５月１２日に出願された米国特許出願第１１／１２７，３２６号
・２００５年５月１２日に出願された米国特許出願第１１／１２８，５４３号
・２００４年４月２３日に出願された米国特許出願第１０／８３１，４３６号
・２００５年４月１５日に出願された米国特許出願第１１／１２６，６３７号
・２００５年６月１０日に出願された米国特許出願第１１／１５１，１６７号
・２００５年３月１日に出願された米国特許出願第１１／０６９，５１２号
・２００４年１１月１２日に出願された米国特許出願第１０／９８７，２８８号
・２００６年３月１日に出願された米国特許出願第１１／３６４，９３３号
・２００７年６月２７日に出願された米国特許出願第１１／７６９，６７１号
【背景技術】
【０００２】
人、及び組織は、静止画像、テキスト、グラフィック、アニメーショングラフィック、及びフルモーションビデオ画像のような大量のデジタル画像コンテンツを急速に蓄積している。これらのコンテンツは、個別に表現される場合もあれば、文書、カタログ、プレゼンテーション、静止画写真、商用ビデオ、家庭用ビデオ、及び１以上の関連デジタルコンテンツファイルを表すメタデータといったように、広く様々な形で結合される場合もある。こうした収集物の数が増加し、その多様性が増加するのに従って、人、及び組織は、デジタルコンテンツを自分達の収集物として編集、及び表現するシステム、及び方法を益々必要としている。この要求を満たすために、デジタル画像コンテンツを編集、及び表示するための種々のシステム、及び方法が提案されている。
【０００３】
例えば、ユーザがデジタルフォトアルバムを手作業で作成することが可能な幾つかの手動型のデジタル画像アルバム化システムが存在する。こうしたシステムは一般に、多数の画像を編集し、画像を１以上のページ上にレイアウトするツールを提供する。中でもデジタルフォトアルバムを手作業で作成する一般的タイプのツールは、多数の画像の中からアルバムの１ページに表示される一部の画像を選択するツール、ページ上の画像を手動で再配置するためのグラフィカルユーザインタフェース、及び、アルバムに表示される画像のサイズ、及び向きのような種々の特徴を変更するための基本的な画像編集ツールである。ユーザは通常、完全手動型のデジタル画像アルバム化システムを使用してデジタルフォトアルバムを作成するプロセスが、退屈で、時間を要するものであることを知っている。
【０００４】
一部の自動化されたデジタル画像アルバム化システムによれば、ユーザは、画像に関連するメタデータとして指定された日付や時刻に従ってデジタル画像をアルバムページとして編集することが出来る。こうしたシステムによれば、一般にユーザは、デジタルフォトアルバムに表示される画像に注釈を付けることも出来る。自動化されたデジタル画像アルバム化システムによっては、種々の所定のレイアウトテンプレートを備え、ユーザは、そうしたレイアウトテンプレートを選択し、デジタルフォトアルバムを作成出来る場合がある。こうしたシステムでは、ユーザが、多数の画像の中から幾つかの画像を選択されたレイアウトテンプレート上の種々の所定の画像位置に割当てると、システムは、それらの画像のサイズ、位置、回転、及び枠組みを、選択されたテンプレート上の種々の所定の画像位置について指定されたパラメタに従って自動的に調節する。
【０００５】
デジタル画像アルバム化システムの中には、ユーザからの最小限の入力で、アルバムページを自動的に生成するように設計されるものがある。そのようなシステムの一つとして、ページ作成器モジュール、及び画像配置モジュールが挙げられる。ページ作成器モジュールは、多数の画像を、第１の遺伝進化アルゴリズムに基いてアルバムページに割当てる。画像配置モジュールは、所与のページに割当てられた画像についてのページレイアウトの遺伝構造を、第２の遺伝進化アルゴリズムに基いて生成する。これらの遺伝構造は、所与のページに配置される画像の位置、縮尺、及び回転姿勢を決定する。ページレイアウト発生器モジュールは、それらのレイアウトを特定の他の好み、及びページ要件と比較する。適当なレイアウトが生成されると、最終的なアルバムレイアウトは表示され、印刷され、又は後の使用に備えて転送される場合がある。
【０００６】
他の自動デジタル画像アルバム化システムとしては、イベントによって編集され、一組のアルバム化パラメタに基いて自動的にレイアウトされたアルバムをユーザに対し表示する、ページレイアウトモジュールを含むものがある。１ページ上にレイアウトされる画像の数は、パラメトリック法によって決定され、又は画像の属性の分析によって決定される。パラメトリック法は、１ページを一組の正方格子に分割し、１ページ上にレイアウトされる画像の数を、画像をそれらの正方格子上にレイアウトするための一組の規則に基いて決定する。このシステムでは、ページ上の画像の実際のレイアウトは、画像のサイズのような画像の属性を一組のテンプレートに適合させることによって決定される場合がある。
【０００７】
さらに他の自動デジタル画像アルバム化システムは、各画像が同じページ上に配置される他の画像に対して力を加えることを仮定する力学モデルに基いて、画像をページ上に自動的に位置決めする場合がある。力は、画像間を隔てる距離の関数である。システムは、各画像をその画像に対して加わる総合的な力の向きにその総合的な力の関数として決まる距離だけ動かすことによって、ページ上の画像の初期レイアウトを変更する。
【０００８】
グラフィックスオブジェクトをページ上に自動的に配置するシステム、及び方法であって、各レイアウトにおけるグラフィックスオブジェクトのうちの１以上の相対位置についての明確な好みによって管理され、又は制御されることが可能なものが必要とされている。
【発明の概要】
【課題を解決するための手段】
【０００９】
［概要］
一態様において、本発明は、どのグラフィックスオブジェクトのユーザ指定レイアウトを受け取ったかに応じた方法を特徴とする。ユーザ指定レイアウトから、相対レイアウト仕様が導出される。相対レイアウト仕様は、グラフィックスオブジェクトの相対位置を表す。グラフィックスオブジェクトの最終レイアウトは、相対レイアウト仕様に従って決定される。最終レイアウトは、ページ上のグラフィックスオブジェクトのサイズ寸法、及び位置の仕様を含む。グラフィックスオブジェクトの最終レイアウトは、出力される。
【００１０】
本発明は、上に記載した方法を実施するように構成された装置、及び上に記載した方法をコンピュータに実施させるためのコンピュータ読取可能命令を記憶するコンピュータ読取可能媒体をさらに特徴とする。
【００１１】
本発明の他の特徴、及び利点は、図面、及び特許請求の範囲の記載を含めて、下記の説明から明らかになるであろう。
【図面の簡単な説明】
【００１２】
【図１】ページ上のグラフィックスオブジェクトのレイアウトを示す概略図である。
【図２】図１に示したグラフィックスオブジェクトのレイアウトを示す概略図であり、図中、複数の単一要素グラフィックスオブジェクトから形成されるマルチ要素グラフィックスオブジェクトは、破線楕円で示される。
【図３Ａ】６つの要素グラフィックスオブジェクトから形成されるマルチ要素グラフィックスオブジェクトの一例を示す図である。
【図３Ｂ】６つの要素グラフィックスオブジェクトから形成されるマルチ要素グラフィックスオブジェクトの一例を示す図である。
【図３Ｃ】６つの要素グラフィックスオブジェクトから形成されるマルチ要素グラフィックスオブジェクトの一例を示す図である。
【図３Ｄ】６つの要素グラフィックスオブジェクトから形成されるマルチ要素グラフィックスオブジェクトの一例を示す図である。
【図４】グラフィックスオブジェクトを１以上のページ上に配置するシステムの一実施形態を示すブロック図である。
【図５】図４のシステムにより実施されるグラフィックスオブジェクト配置方法の一実施形態を示すフロー図である。
【図６】グラフィックスオブジェクトのユーザ指定レイアウトの一例を示す概略図である。
【図７】図６に示したユーザ指定レイアウトから導出される相対レイアウト仕様の一例を示す概略図である。
【図８】図７に示した相対レイアウト仕様に従って請求項４のシステムにより決定される、グラフィックスオブジェクトの最終レイアウトの一例を示す概略図である。
【図９】グラフィックスオブジェクトのユーザ指定レイアウトを作成するためのユーザコマンドを受け取るグラフィカルユーザインタフェースの一実施形態を示す図である。
【図１０】グラフィックスオブジェクトのユーザ指定レイアウトを作成するためのユーザコマンドを受け取るグラフィカルユーザインタフェースの一実施形態を示す図である。
【図１１】図４に示したグラフィックスオブジェクト配置システムの一実施形態を示すブロック図である。
【図１２】グラフィックスオブジェクトのユーザ指定レイアウトの画像、及びユーザ指定レイアウトを機械認識したものの一例を示す図である。
【図１３Ａ】グラフィックスオブジェクトのユーザ指定レイアウトの例、並びに、水平（ｘ）軸、及び垂直（ｙ）軸に沿った位置の関数として、グラフィックスオブジェクトのカウント数の水平投影、及び垂直投影から導出されるヒストグラムの例を示す図である。
【図１３Ｂ】図１３Ａに示したユーザ指定レイアウトを表すツリー構造の概略図である。
【図１４Ａ】図１３Ａのユーザ指定レイアウトにおけるグラフィックスオブジェクト間のパーティションの一例を示す図である。
【図１４Ｂ】図１４Ａに示したユーザ指定レイアウト分割を表す二分木構造を示す概略図である。
【図１５Ａ】図１３Ａのユーザ指定レイアウトにおけるグラフィックスオブジェクト間のパーティションの一例を示す図である。
【図１５Ｂ】図１５Ａに示したユーザ指定レイアウト分割を表す二分木構造を示す概略図である。
【図１６】ツリー構造の１つのノードのバウンディングボックスの特徴を決定する方法の一実施形態を示すフロー図である。
【図１７】ページ上の空白領域をツリー構造のルートノードに割当てる方法の一実施形態を示すフロー図である。
【図１８】ページ上の種々の空白領域をツリー構造の１つのノードの子ノードに割当てる方法の一実施形態を示すフロー図である。
【図１９】図４のグラフィックスオブジェクト配置システムの一実施形態が組み込まれた装置の一実施形態を示すブロック図である。
【発明を実施するための形態】
【００１３】
[詳細な説明]
下記の説明において、同じ参照符号は、同じ要素を識別するために使用される。また、図面は、例示的実施形態の主な特徴を概略的に示すことを意図している。図面は、実際の実施形態のあらゆる特徴を示すことを意図するものでも、描かれた要素の相対的寸法を示すことを意図するものでもなく、原寸どおりに描かれてもいない。
【００１４】
１．序論
本明細書において詳細に説明される種々の実施形態は、グラフィックスオブジェクトを１以上のページ上に配置する種々の方法を提供する。これらの実施形態は、各レイアウト（又は、配置）におけるグラフィックスオブジェクトの相対位置についての明確な好みによって管理され、又は制御されることができる。同時に、それらの実施形態は、それらの好みから、指定された設計上の制限（例えば、ページサイズ、マージン、及びガッター余白制限）に従ったグラフィックスオブジェクトの最終レイアウトを自動生成することができる。このように、ユーザは、より専門的に、かつより美術的に美しい形でクリーナを表示しながら、それらの実施形態を、ユーザのグラフィックスオブジェクト配置の一般的な好みに合致するグラフィックスオブジェクトの特定のレイアウトへと誘導することができる。
【００１５】
本明細書において、「ページ」という用語は、その上にグラフィックスオブジェクトをレイアウトすることが可能な任意のタイプの独立した領域を意味し、例えば、グラフィックスオブジェクトを印刷することが可能な独立した物理媒体として実施される物理的ページ（例えば、一片の用紙）、及び例えば電子表示装置によりユーザに対して表示することが可能なグラフィックスオブジェクトのレイアウトを含む仮想的、デジタル的、又は電子的なページを含む。
【００１６】
「グラフィックスオブジェクト」という用語は、物理的ページ、又は仮想的ページ上に描画することが可能な任意のタイプの視覚的に知覚可能なコンテンツを幅広く意味し、例えば、画像、及びテキストを含む。画像ベースのグラフィックスオブジェクト（又は、単に「画像」）は、任意のタイプのデジタル画像、又は電子画像であってよく、完全な画像であっても、部分的な画像であってもよく、例えば、画像センサ（例えば、ビデオカメラ、静止画カメラ、又は光学スキャナ）により撮影された画像、又はそのような画像を処理（フィルタリング、再整形、拡大、若しくはその他変更）したもの、テキスト画像（例えば、テキストを含むビットマップ画像）、及び図形的画像を含む。「グラフィックスオブジェクト」という用語は、単一要素グラフィックスオブジェクトと、１以上のグラフィックスオブジェクトの団結グループ、又は集まりから形成されるマルチ要素グラフィックスオブジェクトとの両方を包含する。特定のマルチ要素グラフィックスオブジェクトに対する単一要素グラフィックスオブジェクトの割当ては、構成要素となる複数の単一要素グラフィックスオブジェクトを互いに関連付けることを意味する。一般に、マルチ要素グラフィックスオブジェクトに含まれる複数の単一要素グラフィックスオブジェクトは、同じタイプのものであってもよいし、異なるタイプのものであってもよい。グラフィックスオブジェクトは通常、１以上のコンピュータ読取可能媒体上の１以上のデータベースに記憶される。
【００１７】
一部の実施形態において、画像ベースのグラフィックスオブジェクト(例えば、写真のような画像）は、固定面積画像として指定される場合もあれば、可変面積画像として指定される場合もある。これらの実施形態では、固定面積画像の面積やサイズが、生成されるレイアウトにおいて変更されることはないが、可変面積画像のサイズを変更することは許される。可変面積画像は、同じページ上に描画される画像の相対面積に関して制限を有する場合もあれば、有しない場合もある。
【００１８】
例示的実施形態として、画像ベースのグラフィックスオブジェクトはそれぞれ、個別のアスペクト比を有する。アスペクト比は、画像の幅に対する画像の高さの比として定義される。各可変面積画像には、正のスカラー値の公称サイズが割当てられる場合がある。「公称サイズ」とは、指定サイズ、又は理論上のサイズを意味し、公称サイズは、実際のサイズ、すなわち描画されるサイズとは異なる場合もあれば、異ならない場合もある。グラフィックスオブジェクトの「サイズ」とは、そのグラフィックスオブジェクトが占めるページ上の面積の大きさを意味する。実施形態によっては、ユーザは、画像に割当てられる公称サイズ値を設定することが出来る場合がある。他の実施形態において、グラフィックスオブジェクト配置システムは、公称サイズ値をグラフィックスオブジェクトに自動的に割当てる場合がある。
【００１９】
図１は、複数の単一要素グラフィックスオブジェクト１２〜３２を含むページ１０の一例を示している。
【００２０】
図２に示すように、単一要素グラフィックスオブジェクト１２〜３２のうちの選択されたものは、グラフィックスオブジェクト４２としてグループ化される場合があり、グラフィックスオブジェクト４２を構成するグラフィックスオブジェクト（すなわち、１４〜２４）は、ページ上のグラフィックスオブジェクトのレイアウトにおいて、互いに近くに表示されることを意図している。図２に示す例において、マルチ要素グラフィックスオブジェクト４２は、異なるタイプの複数の単一要素グラフィックスオブジェクト（例えば、画像ベースのグラフィックスオブジェクトとテキストのグラフィックスオブジェクト）を含む場合がある。また、マルチ要素グラフィックスオブジェクトの単一要素グラフィックスオブジェクトは、自由に配置される場合もあれば、特定の順序（例えば、ビデオクリップのキーフレームの一時的な並び順序）で配置される場合もある。他のいずれのグラフィックスオブジェクトとの間にも密接な関係を有しない単一要素グラフィックスオブジェクトは、単一の表現形態しか持たない「退化」グラフィックスオブジェクトである。
【００２１】
図３Ａ〜図３Ｄに示すように、構成要素として２以上のグラフィックスオブジェクトを含むグラフィックスオブジェクト５２は、２以上の方法（すなわち、配置）で表示することができる。実施形態によっては、マルチ要素グラフィックスオブジェクトにおける単一要素グラフィックスオブジェクトの表示は、グラフィックスオブジェクトの水平配置、又は垂直配置に制限される場合がある。そのような実施形態では、場合によっては、表示は、単一要素グラフィックスオブジェクトの特定の好ましい水平配置、及び垂直配置にさらに制限される場合がある。例えば、ある実施形態は、同一のマルチ要素グラフィックスオブジェクト内において、テキストのグラフィックスオブジェクトを、画像の右、又は下に表示することしか許可しない場合がある。この場合、画像、及びテキストブロックを含むグラフィックスオブジェクトは、２つの異なる方法で表示される場合がある。図３Ａ〜図３Ｄは、一連の６個のグラフィックスオブジェクト５４（例えば、ビデオキーフレーム）を含むグラフィックスオブジェクト５２を、４つの異なる方法で表示することが出来ることを示している。
【００２２】
一般にグラフィックスオブジェクトは、「厳密面積」スタイル、又は「レンガ」スタイルに従って、ページ上にレイアウトされる。厳密面積スタイルレイアウトの場合、同一ページ上にある複数のグラフィックスオブジェクトの相対面積は、所定の比率に適合する場合がある。例えばユーザは、同一ページ上にある全てのグラフィックスオブジェクトに同じ面積を与えることを指示する場合がある。レンガスタイルレイアウトの場合、同一ページ上のグラフィックスオブジェクトの相対面積は、画像間に空きスペースが全く生じないように選択される。厳密面積スタイルレイアウト、及びレンガスタイルレイアウトの詳細については、２００４年９月３０日に出願された米国特許出願第１０／６７５，７２４号、及び２００４年９月３０日に出願された米国特許出願第１０／６７５，８２３号から得られる。
【００２３】
ＩＩ．グラフィックスオブジェクトをページ上に配置する一般的枠組み
図４は、グラフィックスオブジェクト６２を１以上のページ上に配置するためのシステム６０の一実施形態を示している。システム６０は、ページレイアウト発生器モジュール６４、及びユーザインタフェースモジュール６６を含み、ユーザは、ユーザインタフェースモジュール６６を通してグラフィックスオブジェクト配置システム６０と情報をやり取りすることができる。グラフィックスオブジェクト６２は、１以上のローカル画像データベース、又はリモート画像データベースに記憶される場合がある。グラフィックスオブジェクト配置システム６０のモジュールが、特定のハードウェア構成、又はソフトウェア構成に制限されることはなく、それらは、いかなる計算環境、又は処理環境において実施してもよく、例えば、デジタル電子回路として実施され、あるいは、コンピュータハードウェア、ファームウェア、デバイスドライバ、又はソフトウェアとして実施される場合がある。
【００２４】
図５は、ユーザインタフェースモジュール６６、及びページレイアウト発生器モジュール６４が協働し、ページ上のグラフィックスオブジェクト６２のうちの幾つかについてそれぞれ、個別のレイアウトを生成する方法の一実施形態を示している。
【００２５】
各ページについて、ユーザインタフェースモジュール６６は、グラフィックスオブジェクト６２のうちの幾つかについてそれぞれ、個別のユーザ指定レイアウト６８を受け取る（図５、ブロック６８）。以下で詳しく説明するように、一部の実施形態において、ユーザは、例えばグラフィックスベースのレイアウトツールにコマンドを入力することによって、又はグラフィックスオブジェクトレイアウトの手書きモックアップ（すなわち、概略図、又はラフスケッチ）を入力し、その手書きモックアップにおける種々の要素と、グラフィックスオブジェクト６２の対応する要素との間のマッピングを行うことによって、グラフィックスオブジェクトレイアウトを生成する場合がある。
【００２６】
ページレイアウト発生器モジュール６４は、ユーザ指定レイアウトから相対レイアウト仕様を導出する（図５、ブロック７０）。本明細書において、「相対レイアウト」という用語は、ページ上のグラフィックスオブジェクトのレイアウトであって、グラフィックスオブジェクトの相対位置は指定されるが、グラフィックスオブジェクトの絶対位置は指定されないものを意味する。相対レイアウト仕様は、グラフィックスオブジェクトの相対位置を表す。相対レイアウト仕様は、グラフィックスオブジェクトの相対位置を表す任意のタイプの間取図に対応する場合がある。相対レイアウト仕様は、グラフィックスオブジェクトの相互間の関係について、又は共通の基準点（例えば、ページ上の角のポイント、又は端のポイント）に対する関係について、グラフィックスオブジェクトの相対位置を表す場合がある。
【００２７】
ページレイアウト発生器モジュール６４は、各ページ上のグラフィックスオブジェクトの最終レイアウト７２を、対応する相対レイアウト仕様に従って決定する（図５、ブロック７４）。最終レイアウト７２はそれぞれ、ページ上のグラフィックスオブジェクトのサイズ寸法、及び位置の仕様を含む。本明細書において、「レイアウトの決定」、と「最終レイアウト」は同じ意味で使用され、ページ上のグラフィックスオブジェクトのレイアウトを意味し、当該レイアウトの中に、グラフィックスオブジェクトの位置、及び寸法が指定される。一部の実施形態において、ページレイアウト発生器モジュール６４は、指定された設計制限（例えば、ページ寸法、マージン、及びガッター余白制限）に従ってグラフィックスオブジェクトのサイズ、及び位置を変更することにより、各ページについて、ユーザ指定レイアウトにおけるグラフィックスオブジェクトの相対位置を維持し、かつレイアウトの外観の美しさを向上させるようなグラフィックスオブジェクトの最終レイアウトを決定する場合がある。
【００２８】
ページレイアウト発生器モジュール６４は、グラフィックスオブジェクト７２の最終レイアウトを出力する（図５、ブロック７６）。実施形態によっては、ページレイアウト発生器モジュール６４は、特定のファイルフォーマット（例えばＰＤＦ、又はＸＭＬ）を有する仕様書の形で最終レイアウト７２を出力する場合がある。ページレイアウト発生器モジュール６４は、グラフィックスオブジェクト６２の最終レイアウト７２をユーザインタフェースモジュール６６に出力し、ユーザインタフェースモジュール６６は、その最終レイアウト７２をディスプレイ７８に表示（すなわち描画）する。実施形態によっては、ユーザインタフェースモジュール６６は、グラフィックスオブジェクト配置システム６０により自動生成されたページをユーザが対話的にブラウジングすることを許可する場合がある。さらに、ユーザインタフェース６６によれば、ユーザは、ページに対する編集を指示することができる。所与のページについて指示された編集は、ユーザインタフェースモジュール６６によって解釈される。ユーザインタフェースモジュール６６は、解釈されたユーザコマンド命令をページレイアウト発生器モジュール６４へ送信する。ページレイアウト発生器モジュール６４は、図５の方法の１以上の態様を繰り返すことにより、ユーザインタフェースモジュール６６から受信した編集に従って、１以上のページの修正された最終レイアウト７２を決定することができる。例えばユーザは、スケッチを調節し、それを再提出するかもしれない。あるいはユーザは、画像をクロッピングし、ページレイアウト発生器モジュールに、そのクロッピングされた画像を使用して、ページを再フォーマットさせる場合がある。ユーザインタフェースモジュール６６は、修正された最終レイアウト７２をユーザに提示する。その後ユーザは、修正されたページをブラウジングし、１以上の修正されたページに対する編集を指示し、又はページの一部若しくは全部を描画すべきことをシステム６０に命じる場合がある。
【００２９】
図６は、グラフィックスオブジェクト（Ａ〜Ｋ）のユーザ指定レイアウト８０の一例を示している。グラフィックスオブジェクトレイアウト８０は、グラフィックスオブジェクトＡ〜Ｋの相対位置を、グラフィックスオブジェクト相互間におけるそれらの位置、及びグラフィックスオブジェクトがレイアウトされるページ８２の特徴に対するそれらの位置の両方の両方について示している。
【００３０】
図７は、ユーザ指定レイアウト８０から導出可能な相対レイアウト仕様８４の一例を示している。相対レイアウト仕様８４は、グラフィックスオブジェクトＡ〜Ｋのうちの隣り合うもの同士の間に、パーティション８６〜１００（ディビジョンとも呼ばれる）を示している。パーティション８６〜１００は、ページ８２を複数のセルに分割し、各セルは、グラフィックスオブジェクトＡ〜Ｋのうちのちょうど一つを含む。
【００３１】
図８は、相対レイアウト仕様８４（図７参照）に従ってページレイアウト発生器モジュール６４により決定されたグラフィックスオブジェクトＡ〜Ｋの最終レイアウト１０２の一例を示している。図７に示した最終レイアウト１０２は、レンガスタイルレイアウトに対応し、当該レイアウトにおいて、ページ８２上のグラフィックスオブジェクトＡ〜Ｋの相対面積は、ページ８２の端と、グラフィックスオブジェクトＡ〜Ｋとの間における指定されたマージン空間、及びグラフィックスオブジェクトのうちの隣り合うもの同士の間における指定されたガッター余白部を除いて、画像間に空きスペースが全く生じないように選択される。
【００３２】
ＩＩＩ．相対位置に基く制御によるページ上のグラフィックスオブジェクトの配置
Ａ．はじめに
ページレイアウト発生器モジュール６４は、各ページレイアウトにおけるグラフィックスオブジェクトの相対位置、又は面積についての明確な好みによって管理され、又は制御されることができる。この機能によれば、ユーザは、グラフィックスオブジェクトの相対位置についての好みを入力することができ、それによってページレイアウト発生器モジュール６４に、ユーザのグラフィックスオブジェクト配置の一般的好みに合致するグラフィックスオブジェクトの特定のレイアウトを生成させ、同時に、より専門的に、かつより美術的に美しい形でクリーナを表示させることができる。
【００３３】
以下で詳細に説明するように、ページレイアウト発生器モジュール６４は、グラフィックスオブジェクトのユーザ指定レイアウトを受け取り、ユーザ指定レイアウトから相対レイアウト仕様を導出し、相対レイアウト仕様に従ってグラフィックスオブジェクトの最終レイアウトを決定する。
【００３４】
Ｂ．グラフィックスオブジェクトのユーザ指定レイアウトの受け取り
一般に、ページレイアウト発生器モジュール６４は、グラフィックスオブジェクトのユーザ指定レイアウトを、種々の方法で受け取ることが出来る。例えばユーザは、グラフィックベースのレイアウトツールを使用して、グラフィックスオブジェクトレイアウトを生成する場合がある。あるいはユーザは、グラフィックスオブジェクトレイアウトの手書きモックアップ（すなわち、概略図、又はラフスケッチ）の画像、並びにその手書きモックアップ上の種々のグラフィックス要素をページ上にレイアウトされるグラフィックスオブジェクトの対応するデジタルファイルにリンクするマッピング（例えば、インデックス、その他の参照情報）を入力する場合がある。
【００３５】
１．グラフィックスオブジェクトのユーザ指定レイアウトを作成するためのグラフィカルユーザインタフェース
図９は、ユーザが、選択されたグラフィックスオブジェクトの表現をページ上に配置するためのコマンドを入力することによりユーザ指定レイアウトを作成するための、ユーザインタフェース１１０の一実施形態を示している。グラフィカルユーザインタフェース１１０は一般に、レイアウトツールによって生成され、レイアウトツールは、ユーザがページ上のグラフィックス要素のサイズ、及び位置を調節出来るようにするための種々のグラフィックスベースの機能（例えば、Microsoft(R)のPowerPoint(R)、及びMicrosoft(R)のVisio(R)のようなソフトウェアアプリケーションプログラムによって一般に提供される機能）を備えたソフトウェアアプリーケーションプログラムによって実施される。
【００３６】
ユーザインタフェース１１０は、レイアウトウィンドウ１１２、及びグラフィックスオブジェクトブラウジングウィンドウ１１４を含む。レイアウトウィンドウ１１２はページ１１６を表示し、その上にユーザは、ユーザ指定グラフィックスオブジェクトレイアウトを作成することができる。グラフィックスオブジェクトブラウジングウィンドウ１１４は、ページ１１６上にレイアウトすることが可能なグラフィックスオブジェクトの解像度を下げたものからなる一列のサムネイル１１８を含む。各グラフィックスオブジェクトサムネイル１１８は、そのグラフィックスオブジェクトサムネイルにより表現されるグラフィックスオブジェクトに対応するファイルに（例えばポインタ、その他の参照情報、又はインデックスによって）リンクされる。
【００３７】
ユーザは、グラフィックスオブジェクトブラウジングウィンドウ１１４から、幾つかのグラフィックスオブジェクトサムネイル１１８を、レイアウトウィンドウ１１２にあるページ１１６上の所望の位置へドラッグすることができる。図９に示すように、ユーザは、グラフィックスオブジェクトサムネイルＡをグラフィックスオブジェクトブラウジングウィンドウ１１４からページ１１６の左上角の位置へドラッグする場合がある。グラフィックスオブジェクトサムネイルをページ１１６上に位置決めした後、ユーザは、グラフィックスオブジェクトサムネイルの縁上の一点、又は角の一点を選択し、選択した点をページ１１６上の所望の位置まで動かすことにより、グラフィックスオブジェクトサムネイルをリサイズすることができる。例えば、ユーザは、図９に破線矢印で概略的に示されているように、グラフィックスオブジェクトサムネイルＡの４つの縁をそれぞれ外向きの方向へドラッグすることにより、グラフィックスオブジェクトサムネイルＡのサイズを拡大することができる。図１０は、ユーザが、グラフィックスオブジェクトサムネイルＤをページ１１６の左端に接する位置までドラッグし、グラフィックスオブジェクトサムネイルＤのサイズを破線矩形で示すサイズまで縮小した後に生成されるレイアウトを示している。
【００３８】
ユーザがユーザ指定グラフィックスオブジェクトレイアウトを作成する際に、レイアウトツールは、ページ１１６上の種々のグラフィックスオブジェクトの位置、及びサイズを記録する間取り仕様を管理する。一部の実施形態において、間取り仕様は、ページ１１６上にレイアウトされるグラフィックスオブジェクトサムネイルのバウンディングボックスの左上角、及び右下角のページ座標を記録する場合がある。さらに、間取り仕様は、バウンディングボックスと、当該バウンディングボックスにより表現されるグラフィックスオブジェクトサムネイルにリンクされたグラフィックスオブジェクトファイルのうちの対応するものとの間のマッピングを記録する場合がある。以下で詳しく説明するように、ページレイアウト発生器モジュール６４は、間取り仕様から相対レイアウト仕様を生成する。
【００３９】
２．グラフィックスオブジェクトのユーザ指定レイアウトの画像の受け取り
図１１は、グラフィックスオブジェクト配置システム６０（図４参照）の一実施形態１２０を示している。システム１２０は、ページ上のグラフィックスオブジェクトのユーザ指定レイアウトの画像１２６から間取り仕様１２８を生成する画像分析モジュール１２４を含む、ページレイアウト発生器モジュール６４の一実施形態１２２を含む。このプロセスにおいて、画像分析モジュール１２４は、画像１２６におけるグラフィックスオブジェクトの位置、及びサイズを決定し、その情報を間取り仕様１２８として記録する。ユーザ指定レイアウトの画像１２６は通常、用紙上に生成され、デジタルスキャンにより画像ファイルに変換されたグラフィックスオブジェクトレイアウトの手書きスケッチに対応し、又はタッチスクリーンディスプレイ、若しくはグラフィックスタブレットのようなタッチパッド上に生成されるグラフィックスオブジェクトレイアウトの手書きスケッチに対応する。
【００４０】
実施形態によっては、間取り仕様は、画像１２６上にレイアウトされたグラフィックスオブジェクトのバウンディングボックスの左上角、及び右下角のページ座標を記憶する場合がある。さらに、間取り仕様は、バウンディングボックスの座標と、画像１２６上のグラフィックスオブジェクトにリンクされ、データベース１３０に記憶されたグラフィックスオブジェクトファイルのうちの対応するものとの間のマッピングを記録する場合がある。
【００４１】
実施形態によっては、画像分析モジュール１２４は、画像１２６からグラフィックスオブジェクト識別子を抽出し、（例えば、抽出された識別子をデータベース１３０内の索引として使用することにより、）抽出された識別子により示されるグラフィックスオブジェクトファイルを求めることにより、そのマッピングを決定する場合がある。他の実施形態において、ユーザは、画像１２６上の種々のグラフィックスオブジェクトと、データベース１３０に記憶された画像ファイルのうちの対応するものとの間のマッピングを、グラフィカルユーザインタフェースを介して入力する場合がある。
【００４２】
図１２は、グラフィックスオブジェクトのユーザ指定レイアウト１３２の画像の一例、及び画像分析モジュール１２４によってユーザ指定レイアウト１３２から導出された間取り仕様のグラフィック表現１３４の一例を示している。ユーザ指定レイアウト１３２上の各グラフィックスオブジェクトには、それぞれ識別子（すなわち、Ａ〜Ｋ）が付されている。画像分析モジュール１２４は、それらの識別子を抽出し、ユーザ指定レイアウト１３２上の種々のグラフィックスオブジェクトと、データベース１３０内のグラフィックスオブジェクトファイルのうちの対応するものとの間の対応関係を判断する。以下で詳細に説明するように、ページレイアウト発生器モジュール６４は、間取り仕様から相対レイアウト仕様を生成する。
【００４３】
３．グラフィックスオブジェクトのユーザ指定レイアウトに対する条件の付加
実施形態によっては、ページレイアウト発生器モジュール６４は、ユーザ指定レイアウトから相対レイアウト仕様を導出するページレイアウト発生器モジュール６４の能力を向上させるために、ユーザ指定グラフィックスオブジェクトレイアウトに対し、特定の条件を課す場合がある。例えば、以下で説明する一部の実施形態において、ページレイアウト発生器モジュール６４は、ユーザ指定レイアウトにおける水平投影、及び垂直投影に基いて、相対レイアウト仕様を解明する場合がある。そのような実施形態では、場合によっては、ページレイアウト発生器モジュール６４は、ユーザ指定グラフィックスオブジェクトレイアウトに対し、下記の条件を課す場合がある。
・ユーザ指定レイアウトにおいて、各グラフィックス要素は、完全にページ内になければならない。
・ユーザ指定レイアウトにおいて、各グラフィックス要素は、ページ上の他のいずれのグラフィックス要素とも重なってはならない。
・ユーザ指定レイアウトにおいて、グラフィックス要素は、ページの一連の領域ニ分割によって生成されるパーティションによってグラフィックス要素を互いに分離することが可能な形で配置されなければならない。ただし、各分割は、ページ１１６の矩形領域を２つのより小さな矩形領域に分割する水平分割、又は垂直分割であるものとする。
【００４４】
実施形態によっては、ユーザ指定グラフィックスオブジェクトレイアウトが上記要件の一つに違反するという判定結果に応答し、システム６０は、そのユーザ指定グラフィックスオブジェクトレイアウトを修正しなければならないことをユーザに知らせるエラーメッセージを発行する場合がある。
【００４５】
Ｃ．ユーザ指定レイアウトからの相対レイアウト仕様の導出
ページレイアウト発生器モジュール６４は、非常に様々な方法で、ユーザ指定レイアウトから相対レイアウト仕様を導出することができる。このプロセスにおいて、ページレイアウト発生器モジュール６４は、ユーザ指定レイアウトから、グラフィックスオブジェクトの相互間における、又は共通の基準点(例えば、ページの角のポイント、又は端のポイント）に対するグラフィックスオブジェクトの相対位置の表現を導出する。相対レイアウト仕様は通常、各セルが、ユーザ指定レイアウトにおいて指定されたちょうど一つのグラフィックスオブジェクトを含むものになるような、ページのセルへの分解を表す。実施形態によっては、間取りモデルは、２進空間分割モデルのような再帰分割（又は、分割）モデルに対応する場合があり、２進空間分割モデルは、ツリー構造として構成されることがある。
【００４６】
ページレイアウト発生器モジュール６４は通常、ユーザ指定グラフィックスオブジェクトレイアウトの表現を記憶する間取り仕様から、相対レイアウト仕様を導出する。実施形態によっては、間取り仕様は、ユーザが、グラフィックスオブジェクト６２のそれぞれについて指定したページの種々の矩形領域の左上角、及び右下角のページ座標を含む場合がある。ページレイアウト発生器モジュール６４は、矩形領域の位置を分析することにより、種々の矩形領域との間に一対一の関係を有する一組のセルを生成することが可能な、ページの一連のパーティション（又は、ディビジョン）を特定する。これらのパーティションは通常、一連のパーティションを記録する階層ツリー構造として編成され、当該一連のパーティションから、矩形領域に対応する一組のセルを決定することができる。実施形態によっては、ページレイアウト発生器モジュール６４は、相対レイアウト仕様をそれぞれ個別の二分木データ構造に記憶する場合があり、二分木データ構造は、グラフィックスオブジェクトに対応するリーフノード、及び対応するページのパーティションに対応する内側ノードを有する。
【００４７】
実施形態によっては、ページレイアウト発生器モジュール６４は、ユーザ指定レイアウトの水平ヒストグラムプロファイル、及び垂直ヒストグラムプロファイルを求め、グラフィックスオブジェクトを相互に分離するパーティションを求めることにより、ユーザ指定レイアウトからグラフィックスオブジェクトの相対レイアウトを解明する場合がある。
【００４８】
一例として、図１３Ａは、ページ１４２上のグラフィックスオブジェクト（すなわち、グラフィックスオブジェクトＬ、Ｍ、Ｎ、Ｏ）のユーザ指定レイアウト１４０の一例を示している。図１３はさらに、水平ヒストグラムプロファイル１４４、及び垂直ヒストグラムプロファイル１４６も示している。水平ヒストグラムプロファイル１４４は、グラフィックスオブジェクトＬ〜Ｏのカウント数の垂直投影から、水平軸（ｘ）に沿った位置の関数として計算される。垂直ヒストグラムプロファイル１４４は、グラフィックスオブジェクトＬ〜Ｏのカウント数の水平投影から、垂直軸（ｙ）に沿った位置の関数として計算される。これらの実施形態によれば、ページレイアウト発生器モジュール６４は、水平ヒストグラム１４４、及び垂直ヒストグラム１４６における極小値に基いて、ページ１４２を分割するパーティションを決定する。
【００４９】
一実施形態において、ページレイアウト発生器モジュール６４は、まず、図１３Ａ、及び図１３Ｂに示すように、ページ１４２の全体を含むバウンディングボックス１５２に関連する１つのノード１５０を有する初期ツリー１４８を生成する。ページレイアウト発生器モジュール６４は、ヒストグラム１４４におけるゼロ値を識別し、識別されたゼロ値のうちの１つを選択し、選択されたゼロ値の位置にあるパーティションを使用して、現在ノード１５０を２つのノードに分割する。図１３Ａに示す例において、ヒストグラム１４４、１４６には、単一のゼロ値１５４しか存在しない。ページレイアウト発生器モジュール６４は、ゼロ値１５４の位置に水平パーティションを生成する（図１４Ａ参照）。水平パーティション（Ｈ）は、ノード１５０を２つのノード１５８、１６０に分割し、ノード１５８、１６０は、図１４Ａ、及び図１４Ｂに示すようにンディングボックス１６６、１６４に関連する。
【００５０】
もし、あるノードがグラフィックスオブジェクトを１つしか有しないバウンディングボックスに関連する場合、そのノードは、それ以上分割されない。例えば、図１４Ａ、及び図１４Ｂに示す分割プロセスの段階において、ノード１５８は、バウンディングボックス１６４に関連し、従って、それ以上分割されない。もし、あるノードが、２以上のグラフィックスオブジェクトを含むバウンディングボックスに関連する場合、そのノードは、現在ノードとして指定され、プロセスは繰り返される。図１４Ａ、及び図１４Ｂに示す分割プロセスの段階において、ノード１６０は、バウンディングボックス１６６に関連し、バウンディングボックス１６６は、３つのグラフィックスオブジェクトＭ〜Ｏを含む。従って、この段階の結果、ノード１６０には、現在ノードのラベルが付され、プロセスは繰り返される。
【００５１】
ノード１６０について分割プロセスを繰り返すプロセスの一例として、ページレイアウト発生器モジュール６４は、現在ノード１６０に関連するバウンディングボックス１６６におけるグラフィックスオブジェクトの水平ヒストグラム、及び垂直ヒストグラムを求める場合がある。ページレイアウト発生器モジュール６４は、水平ヒストグラムにおける２つのゼロのうちの最初のものを選択し、現在ノード１６０を２つのノード１７２、１７４に分割する垂直パーティション１７０を使用して、現在ノード１６０を分割する（図１５Ａ参照）。その後、ページレイアウト発生器モジュール６４は、グラフィックスオブジェクトＮ、及びＯを含み、かつ現在ノード１７４に関連するバウンディングボックスにおけるグラフィックスオブジェクトの水平ヒストグラム、及び垂直ヒストグラムを求める（図１５Ｂ参照）。ページレイアウト発生器モジュール６４は、水平ヒストグラムにおけるゼロのみを選択し、現在ノード１７４を２つのノード１８０、１８２に分割する垂直パーティションを使用して、現在ノード１７４を分割する（図１５Ｂ参照）。図１５Ｂに示すツリー構造の例において、内部ノード１５０、１６０、１７４は、パーティション１５６、１７０、１７８にそれぞれ対応するのに対し、リーフノード１５８、１７２、１８０、１８２は、グラフィックスオブジェクトＬ、Ｍ、Ｎ、Ｏにそれぞれ対応する。
【００５２】
Ｄ．相対レイアウト仕様に基づくグラフィックスオブジェクトの最終レイアウトの決定
１．概要
ページレイアウト発生器モジュール６４は、相対レイアウト仕様から、ページ上のグラフィックスオブジェクトの最終配置を決定、又は生成する。上で説明したように、相対レイアウト仕様は、非常に様々な間取りモデルのうちの任意の１つを反映するデータ構造に対応する場合がある。下記の実施形態は、２進空間分割モデルに対応する相対レイアウト仕様を例として説明され、当該モデルに従って、グラフィックスオブジェクトの相対位置が、二分木構造に記録される。
【００５３】
２．ページ上のグラフィックスオブジェクトの最終配置の生成
実施形態によっては、ページレイアウト発生器モジュール６４は、ページ上の種々のグラフィックスオブジェクトの相対位置を表す個別のツリー構造を受け取る場合がある。ツリー構造の各リーフノードは、アスペクト比値（ａ）を有し、厳密面積スタイルレイアウトの場合、さらに公称サイズ値（ｅ）を有する。ツリー構造の各内部ノードは、ページ上での水平分割と垂直分割のいずれかを示す。ページレイアウト発生器モジュール６４は、各ページ上の種々のグラフィックスオブジェクトの面積を求め、その後、ページ空間の正確な領域をツリー構造の各ノードに割当てる。ページの割当て済み領域は、対応するツリー構造と同様に入れ子構造を成す。本明細書において、この割当て済み領域は、「セル」と呼ばれる。実施形態によっては、セルが分かった後、そのセルに割当てられるグラフィックスオブジェクトの位置は、そのグラフィックスオブジェクトをセル内の中央に位置決めすることによって決定される場合がある。
【００５４】
ａ．グラフィックスオブジェクトの面積の決定
グラフィックスオブジェクトの面積は、所望の精度、所望のレイアウトスタイル、及び利用可能な計算リソースに応じて、バウンディングボックスに基く面積決定法、パスに基く面積決定法、又は線形システムに基く面積決定法によって決定される。
【００５５】
ｉ．バウンディングボックスに基くグラフィックスオブジェクト面積の決定
例示的実施形態として、バウンディングボックス決定プロセスの目的は、所与のツリー構造における各内部ノードについて、アスペクト比値、及び公称サイズ値を計算することである。各バウンディングボックスは、そのバウンディングボックスに包含されるボックスによって決定される。
【００５６】
後で詳しく説明するように、バウンディングボックスは、グラフィックスオブジェクトのアスペクト比、及び公称サイズを使用して計算される。厳密面積スタイルレイアウトの場合、各グラフィックスオブジェクトの公称サイズは、間取り仕様上の対応する矩形の面積に等しくなるようにセットされる場合がある。実施形態によっては、バウンディングボックス特性評価プロセスは、リーフノードから開始され、図１６に示すように深さ優先順で、ルートノードへ向けて実行される場合がある。
【００５７】
任意の内部ノードのアスペクト比、及び公称サイズを求める式は、下記のとおりである。一般に、アスペクト比ａ、及び公称サイズｅを有する任意の画像バウンディングボックスの場合、
【数１】
及び
【数２】
の大きさがそれぞれ、画像バウンディングボックスの公称高さ、及び公称幅となる。任意の内部ノードについてのアスペクト比ａ、及び公称サイズｅは、その内部ノードの２つの子ノードのアスペクト比、および公称サイズの関数となる。下記の式において、ａｒ、及びｅｒは、右側子ノードのアスペクト比、及び公称サイズであり、ａｌ、及びｅｌは、左側子ノードのアスペクト比、及び公称サイズである。従って、もし、右側子ノードと左側子ノードが横並びに配置された場合、それらを取り囲むバウンディングボックスのアスペクト比、及び公称サイズは、下記のようになる。
【００５８】
【数３】
【００５９】
【数４】
【００６０】
ただし、
【数５】
である。
【００６１】
式（１）におけるアスペクト比は、大きい方の公称高さを２つの公称幅の合計で割った比であり、式（２）における公称サイズは、大きい方の公称高さと、２つの公称幅の合計との積である。式（３）における最大値を見付けることにより、２つの子ノードボックスのうちのいずれが名目上高く、従って、親ノードボックスの高さを支配するのかを判断することができる。
【００６２】
もし、２つの子ノードが、順に重ねて配置されたボックスを表す場合、それらを包含するバウンディングボックスのアスペクト比、及び公称サイズは、下記のようになる。
【００６３】
【数６】
【００６４】
【数７】
【００６５】
ただし、
【数８】
である。
【００６６】
この場合、式（６）から、２つの子ノードボックスのうちのいずれの幅が名目上広く、従って親ノードボックスの幅を支配するのかを判断することができる。
【００６７】
ルートノードのバウンディングボックスは、対応するツリー構造により指定されるページのレイアウト全体の形、及び公称サイズを有する。本明細書において、ルートノードのバウンディングボックスは、「主バウンディングボックス」と呼ばれる。
【００６８】
主バウンディングボックスのアスペクト比、及び公称サイズが分かっている場合、グラフィックスオブジェクトｉについてのバウンディングボックスに基づく面積Ａｉは、下記のように計算される。
【００６９】
【数９】
【００７０】
ただし、ｅｉ、及びｅｐｂｂは、グラフィックスオブジェクトｉ、及び主バウンディングボックスのそれぞれの公称サイズであり、Ａｐｂｂは、下記のように計算される主バウンディングボックスの面積である。
【００７１】
【数１０】
【００７２】
ただし、Ａｐａｇｅは、使用可能なページ空間の面積である。
【００７３】
図１６は、再帰プロセスの一実施形態を示すフロー図であり、ページレイアウト発生器モジュール６４は、この再帰プロセスにより、ツリー構造の種々のノードについて、バウンディングボックスの相対的な高さ寸法、及び幅寸法を計算する。
【００７４】
このプロセスは、現在ノードとしてのルートノードから開始される。現在ノードが終端ノードであるか否かを判断する(図１６、ブロック４８０）。もし現在ノードが終端ノードであった場合、関連グラフィックスオブジェクトの公称高さ、及び公称幅を有するバウンディングボックスを決定する（図１６、ブロック４８２）。もし現在ノードが終端ノードではなかった場合、現在ノードの２つの子ノード（すなわち、左側子ノード、及び右側子ノード）を同じ再帰プロセスに提出する（図１６、ブロック４８４、４８６）。現在ノードについてのバウンディングボックスを形成するために、下記のように、２つの子ノードのバウンディングボックスを結合する。ページレイアウト発生器モジュール６４は、現在ノードが水平分割であるか、それとも垂直分割であるかを判断する（図１６、ブロック４８８）。もし現在ノードが水平分割を表している場合、バウンディングボックスの公称幅は、２つの子ノードのバウンディングボックスのうちの幅の広い方の公称幅にセットされ（図１６、ブロック４９０）、バウンディングボックスの公称高さは、２つの子ノードのバウンディングボックスの公称高さの合計にセットされる。もし現在ノードが垂直分割を表している場合、（図１６、ブロック４８８）、バウンディングボックスの公称高さは、２つの子ノードのバウンディングボックスのうちの高い方の公称高さにセットされ（図１６、ブロック４９４）、バウンディングボックスの公称幅は、２つの子ノードのバウンディングボックスの公称幅の合計にセットされる。このプロセスは、ルートノードについてのバウンディングボックスの計算が完了するまで続けられる。
【００７５】
ｉｉ．パスに基くグラフィックスオブジェクト面積の決定
パスに基く面積決定法によれば、ページレイアウト発生器モジュール６４は、２００７年６月２７日に出願された米国特許出願第１１／７６９，６７１号の図９〜図１０Ｊ、及び図２４のブロック４１０に関係して以下に記載するパス生成プロセスに従って、ツリー構造を通るパスＰｉを生成する。
【００７６】
ページレイアウト発生器モジュール６４は、各パスＰｉについてパス長さＬ（Ｐｉ）を計算する。もしパスＰｉが垂直であった場合、その長さは、下記のようになる。
【００７７】
【数１１】
【００７８】
グラフィックスオブジェクトの高さ（ＨＧＯ）は、下記のように書き表すことができる。
【００７９】
【数１２】
【００８０】
ただし、Ａは、グラフィックスオブジェクトの面積であり、ａは、高さを幅で割った比として定義されるアスペクト比であり、Ｑは、面積の平方根である。従って、もしＰｉが垂直パスであれば、その長さは下記のように書き表すことができる。
【００８１】
【数１３】
【００８２】
ただし、Ｋｉは、式（９）における最初の２つの項（すなわち、パスＰｉに沿った全ての固定距離）の合計であり、Ｑｉ，ｊは、パスＰｉ上の第ｊの可変面積オブジェクトの面積の平方根であり、ａｉ，ｊは、パスＰｉ上の第ｊの可変面積オブジェクトのアスペクト比である。なお、加算項は、パスＰｉ上の可変面積グラフィックスオブジェクトの高さの合計に対応する。
【００８３】
同様の計算により、水平パスＰｉの長さは、下記のように書き表すことができる。
【００８４】
【数１４】
【００８５】
ただし、Ｋｉは、パスＰｉに沿った固定面積グラフィックスオブジェクトの水平固定距離、及び幅の合計である。厳密面積スタイルレイアウトの場合、各可変面積グラフィックスアセンブリには、公称サイズが割当てられ、公称サイズは変数ｅで表される。マルチ要素グラフィックスオブジェクトの場合、当該オブジェクトは、構成要素として２以上の単一要素グラフィックスオブジェクト（例えば、ビデオからの一連のキーフレームなど）を含み、単一の集合体公称サイズが、グラフィックスオブジェクト全体に割当てられ、マルチ要素グラフィックスオブジェクト内の個々のグラフィックスオブジェクトの公称サイズは、その集合体公称サイズをそのグラフィックスオブジェクト内のグラフィックスオブジェクトの数で割ったサイズに等しくなるようにセットされる。このセクションの残りの部分では、パスＰｉ上の各グラフィックスオブジェクトｊが、正の公称サイズｅｊを有する単一要素グラフィックスオブジェクトであるものと仮定する。公称サイズは実際の面積に比例するので、上で定義された変数Ｑは、（絶対面積ではなく）公称サイズの平方根を反映するように、下記のように一般化することができる。
【００８６】
【数１５】
【００８７】
ただし、ｇは、ｇ２に公称サイズを乗じたものが、絶対測定可能面積（例えば、平方インチ）になるような、正のスカラー値である。Ｑを
【数１６】
で割った比は、全ての可変面積グラフィックスオブジェクトにわたって一定であり、従って、ページ上の全ての可変面積グラフィックスオブジェクトについて、同じ値のｇが使用される。従って、上式（１１）、及び式（１２）において、Ｑを
【数１７】
に置き換え、ｇを加算項の外に出すと、式は下記のようになる。
【００８８】
【数１８】
【００８９】
【数１９】
【００９０】
ただし、ｅｉ，ｊは、パスＰｉ上の第ｊの可変面積グラフィックスオブジェクトの公称サイズである。
【００９１】
もしＰｉが垂直パスであり、ページ上の使用可能エリアの高さがＨＰＡＧＥである場合、下記の式をｇｉについて解くことにより、使用可能エリアの高さが高い限り、Ｐｉが正確であるときの値が得られる。
【００９２】
【数２０】
【００９３】
同様に、もしＰｉが水平パスであり、使用可能エリアの幅がＷＰＡＧＥである場合、下記の式をｇｉについて解くことにより、そのパスが、使用可能エリアの幅全体にわたってちょうど適合するときの値が得られる。
【００９４】
【数２１】
【００９５】
ツリー構造により実施される各水平パスについて、ＷＰＡＧＥ＞Ｋｉであるものと仮定し、さらに、ツリー構造により実施される各垂直パスについて、ＨＰＡＧＥ＞Ｋｉであるものと仮定する。これは、各パスに沿った固定距離がそれぞれの寸法内に適合することを意味し、従って、ツリー構造によって表されるレイアウトは「実現可能」であり、全てのグラフィックスオブジェクトがページ上に収まるような、可変面積グラフィックスオブジェクトの面積について正の値が存在することを意味する。
【００９６】
一実施形態において、可変面積グラフィックスオブジェクトの面積は、可能な限り広く作成されるが、それでも、Ｐｉが垂直パスであるか、それとも水平パスであるかに応じて式（１６）又は式（１７）を使用し、（各パスＰｉについて）ｇｉについて解くことにより、全てのグラフィックスオブジェクトをページの使用可能エリアに完全に収めることができる。上記のように、レイアウトが実現可能なものであることを前提としているので、ｇｉについての各解は正になる。もし、ｇ＊を全てのパスにわたる最小の解として下記のように定義した場合、
【数２２】
第ｊの可変面積グラフィックスオブジェクトの面積Ａｊは、下記のように計算される。
【数２３】
ただし、ｅｉは、第ｊの可変面積グラフィックスオブジェクトに割当てられた公称サイズである。
【００９７】
ｉｉｉ．線形システムに基くグラフィックスオブジェクト面積の決定
レンガスタイルレイアウトの場合、グラフィックス要素の面積は、まずＱの値を計算することによって決定される。Ｑの値が分かった後、それらを二乗し、絶対測定可能面積（例えば、平方インチを単位として表される）を求める。Ｑの値は、次の２つの仮説に基いて計算される：（１）グラフィックス要素が占めるエリアの高さは、ページ上の使用可能エリアの高さに等しくなるように拘束される。（２）グラフィックス要素が占めるエリアの幅は、ページ上の使用可能エリアの幅に等しくなるよう拘束される。大抵の場合、仮説（Ｉ）と仮説（ＩＩ）のいずれか一方のみが、実現可能な解を生成する。なぜなら、他方の仮説においては、他方の（拘束されていない）寸法が、使用可能空間より大きくなるからである。最終的な一組のグラフィックス要素エリアを生成するために、実現可能な解を生成する仮説が選択される。
【００９８】
仮説（Ｉ）と仮説（ＩＩ）のいずれにおいても、Ｑの値は、Ｎ個の未知数を有する線形システムの式の解として計算される。ただし、Ｎは、グラフィックス要素の数である。Ｎ−１個の式はそれぞれ、完全なツリー構造の内部ノードから得られる。なぜなら、Ｎ個のグラフィック要素を有するツリーには、ちょうど（Ｎ−１）個の内部ノードが存在するからである。
【００９９】
垂直分割、又は領域切断を表す内部ノードの場合、対応する式は、まずその内部ノードの２つの子ノードのそれぞれから１つ、合わせて２つの垂直パスを得て、それらの長さを同じ長さにセットすることによって導出される。上記の式（１１）を参照すると、左側子ノードからの垂直パスをＰＬで表し、右側子ノードからの垂直パスをＰＲで表した場合、対応する式は、下記のようになる。
【０１００】
【数２４】
【０１０１】
ただし、変数ｊは、ＰＲ上でグラフィックスオブジェクトを索引付けし、変数ｋは、ＰＬ上でグラフィックスオブジェクトを索引付けする。式（２０）を変形すると、下記のようになる。
【０１０２】
【数２５】
【０１０３】
この状況は、水平分割、又は領域切断を表す内部ノードの場合に似ている。２つの水平パスを得て、それらの長さを同じ長さにセットすると、下記の式が得られる。
【０１０４】
【数２６】
【０１０５】
各内部ノードについて式（２０）又は（２２）の形の式を作成することにより、Ｎ個の未知数について、Ｎ−１個の式が得られる。
【０１０６】
仮説Ｉの場合、第Ｎの式は、ルートノードからの任意の垂直パスの長さを、使用可能エリアの高さに等しくなるようにセットすることによって得られる。仮説ＩＩの場合、第Ｎの式は、ルートノードからの任意の水平パスの長さを、使用可能エリアの幅に等しくなるようにセットすることによって得られる。
【０１０７】
仮説Ｉと仮説ＩＩのいずれの場合も、Ｎ個の式は、行列ベクトル（Ａｘ＝ｂ）の形で書かれる。行列は、ゼロ、グラフィックス要素アスペクト比の正、及び負の平方根、並びにグラフィックス要素アスペクト比の平方根の正の逆数、及び負の逆数のみを含む。ベクトルｘのＮ個の要素は、Ｑ個の変数である。ベクトルｂのＮ個の要素のうち、（Ｎ−１）個は、式（２０）、又は式（２１）の右辺に従って計算され、残りは、使用可能エリアの高さ（仮説Ｉ）、又は幅（仮説ＩＩ）（から対応する行を得るために使用されるパスに沿った固定距離を差し引いたもの）に等しくなる。逆行列（Ａ）＊ｂを計算することにより、Ｑ値のベクトルが得られる。
【０１０８】
ｂ．ツリー構造におけるノードの周りのバウンディングボックスの決定
絶対面積を計算した後、ツリー構造における各ノードの周りにバウンディングボックスを描画する。このプロセスを達成するために必要な実際のステップは、２点を除き、図１６に示したようなバウンディングボックスに基く面積決定に関係して上で説明したバウンディングボックスを計算するためのプロセスと全く同様である。第１に、公称サイズは偶然に、実際のグラフィックスオブジェクト面積と等しくなることがある。第２に、内部ノードに割当てられる間隔は、無視されるのではなく、代わりにブロック４９２、及び４９６の計算において合計に加算される。
【０１０９】
ｃ．ページ空間のグラフィックスオブジェクトへの割当て
【０１１０】
ｉ．ページ空間割当てプロセスの概要
実施形態によっては、ページ上の空白領域をノードに割当てるプロセスは、ページを複数のセルに分割し、各グラフィックスオブジェクトをそれぞれのセルの中に位置決めすることを含む場合がある。ページのセルへの分割は、まずページの使用可能エリア全体を第１の矩形とし、ページを複数の矩形に分割することにより開始される。各分割は、ルートノードから開始し、横型探索の順序で各内部ノードについて１本のラインセグメントを描くことにより達成される。
【０１１１】
垂直分割に対応する内部ノードの場合、ページレイアウト発生器モジュール６４は、使用可能領域の幅に沿って水平位置ｘを選択する。これを式で表すと例えば、ｘ∈（０，１）のようになる。ただしｘ＝０は、使用可能領域における最も左側の位置を表し、ｘ＝１は、使用可能領域における最も右側の位置を表す。この場合、下記のようになる。
【０１１２】
【数２７】
【０１１３】
ただし、ａｌ、ｅｌ、及びａｒ、ｅｒは、内部ノードの左側子ノード、及び右側子ノードについてのバウンディングボックスのアスペクト比、及び面積である。この式は、幅を比率として直接使用する。水平分割の場合の同様の式は、高さを使用する。すなわち、もしｙ＝０が最下位置を表し、ｙ＝１が最上位置を表すものとし、使用可能空間の高さ方向における垂直位置をｙ∈（０，１）で表した場合、下記のようになる。
【０１１４】
【数２８】
【０１１５】
ただし、ａｂ、ｅｂ、及びａｔ、ｅｔは、内部ノードの最下部、及び最上部の子ノードについてのバウンディングボックスのアスペクト比、及び面積である。
【０１１６】
ｉｉ．ページ空間をグラフィックスオブジェクトに割当てるプロセスの詳細
図１７は、ページ上の空きの物理領域を現在のツリー構造のルートノードに割当てる方法の一実施形態を示している。この方法に従って、レイアウトスタイルは決定される（図１７、ブロック６３０）。厳密面積スタイルレイアウトの場合、ページの使用可能エリア全体をルートノードに割当てる（図１７、ブロック６３２）。レンガスタイルレイアウトの場合、ルートノードに割当てられるページ空間は、ルートノードに関連するバウンディングボックスの高さ、及び幅を有する（図１７、ブロック６３４、６３６）。次に、ルートノードに割当てられた領域を、使用可能なページ空間の中央に位置決めする（図１７、ブロック６３８）。
【０１１７】
図１８は、空きページ領域をツリー構造のあるノードの子ノードに割当てる方法の一実施形態を示している。このプロセスでは、各内部ノードに割当てられる空き領域は、その内部ノードの２つの直接の子ノードの間で分割される。この分割は、現在のツリー構造のルートノードを現在ノードにセットし、再帰プロセスを実施することにより達成される。
【０１１８】
再帰プロセスでは、現在ノードが終端ノードであるか否かを判断する（図１８、ブロック６４０）。もし現在ノードが終端ノード（すなわち、リーフノード）であった場合、プロセスは終了する（図１８、ブロック６４２）。もし現在ノードが内部ノードであった場合は、現在ノードが２以上の単一要素グラフィックスオブジェクトを含むマルチ要素グラフィックスオブジェクト（ＧＯ）に対応するツリーのルートノードであるか否かを判断する（図１８、ブロック６４４）。もしそうであれば、現在ノードに割当てられた領域の高さ、及び幅を、現在ノードについて前回計算されたバウンディングボックスの高さ、及び幅と等しくなるように再割当てすることによって、現在ノードに割当てられた領域を圧縮し（図１８、ブロック６４６）、その領域の位置を、現在ノードに前回割当てられた領域の中央に位置決めする。レンガスタイルレイアウトの場合、これは何も影響を及ぼさない。厳密面積レイアウトの場合、これは、２以上のグラフィックス要素（例えば、一連のキーフレームなど）を含むグラフィックスアセンブリにおいて、複数の画像をまとめて引き抜く作用を有する。
【０１１９】
もし現在ノードがマルチ要素グラフィックスオブジェクトに対応するツリーのルートノードではないと判断された場合（図１８、ブロック６４４）、現在ノードの左側子ノード、及び右側子ノードについての空き領域の高さ、及び幅を計算する（図１８、ブロック６４８）。
【０１２０】
もし現在ノードが水平ページ分割であった場合、右側子ノード、及び左側子ノードに割当てられる領域の高さ（ＨＲ，ＨＬ）は、下記の式から得られる。
【０１２１】
【数２９】
【０１２２】
【数３０】
【０１２３】
ただし、ＨＮＯＤＥは、現在ノード空き領域の高さであり、Ｓは、ノード間隔であり、Ｌは、左側子ノードバウンディングボックスの高さであり、Ｒは、右側子ノードバウンディングボックスの高さである。左側子ノード、及び右側子ノードに割当てられる領域の幅は、現在ノードに割当てられた領域の幅に等しくなるようにセットされる。
【０１２４】
もし現在ノードが垂直ページ分割であった場合、右側子ノード、及び左側子ノードに割当てられる領域の幅（ＷＲ，ＷＬ）は、下記の式から得られる。
【０１２５】
【数３１】
【０１２６】
【数３２】
【０１２７】
ただし、ＷＮＯＤＥは、現在ノード空白領域の幅である。左側子ノード、及び右側子ノードに割当てられる領域の高さは、現在ノードに割当てられた領域の高さに等しくなるようにセットされる。
【０１２８】
もし現在ノードが水平ページ分割であった場合（図１８、ブロック６５０）、左側子ノードの空き領域は、現在ノードに割当てられた空き領域の上側境界に可能な限り近づけて配置される（図１８、ブロック６５２）。右側子ノードの空き領域は、現在ノードに割当てられた空き領域の下側境界に可能な限り近づけて配置される（図１８、ブロック６５４）。
【０１２９】
もし現在ノードが垂直分割であった場合（図１８、ブロック６５０）、左側子ノードの空き領域は、現在ノードに割当てられた空き領域の左側境界に可能な限り近づけて配置される（図１８、ブロック６５６）。右側子ノードの空き領域は、現在ノードに割当てられた空き領域の右側境界に可能な限り近づけて配置される（図１８、ブロック６５８）。
【０１３０】
上記のプロセスを繰り返すことにより、種々の空き領域が、左側子ノードの子ノード（図１８、ブロック６６０）、及び右側子ノードの子ノード（図１８、ブロック６６２）に割当てられる。このプロセスは、ページ上の空き領域が現在ノードの全ての子ノードに（直接的、又は他の形で）割当てられるまで繰り返される。
【０１３１】
３．グラフィックスオブジェクトの最終レイアウトの出力
ページレイアウト発生器モジュール６４は通常、最終レイアウトを表すデータ構造（例えば、表、又はリスト）を含む仕様書の形で、最終レイアウトを出力する。実施形態によっては、この仕様書は、ＸＭＬ（拡張マークアップ言語）ファイルフォーマットの形で機械読取可能な媒体に記憶される場合がある。仕様書を実際に実施するのに適した記憶装置には、あらゆる形の不揮発性コンピュータ読取可能媒体、及び揮発性コンピュータ読取可能媒体が含まれ、限定はしないが、例えば、ＥＰＲＯＭ、ＭＥＥＰＲＯＭ、及びフラッシュメモリデバイスのような半導体メモリデバイス、内蔵ハードディスクやリムーバブルディスクのような磁気ディスク、光磁気ディスク、及びＣＤ−ＲＯＭが挙げられる。最終レイアウト仕様は、ユーザインタフェースモジュール６６、又は印刷モジュールにより、最終レイアウトを表示装置に描画し、又は印刷媒体（例えば、用紙）に印刷するために使用される場合がある。
【０１３２】
ＩＶ．グラフィックスオブジェクト配置システムの例示的アーキテクチャ
グラフィックスオブジェクト配置システム６０の種々の実施形態は、１以上の個別のモジュール（又は、データ処理コンポーネント）によって実施され、それらが、何らかの特定のハードウェア、ファームウェア、又はソフトウェア構成に制限されることはない。例示的実施形態において、モジュールは、いかなる計算環境、又はデータ処理環境において実施されてもよく、例えば、デジタル電子回路（例えば、デジタル信号プロセッサ（ＤＳＰ）のような特定用途向け集積回路）として実施され、あるいはコンピュータハードウェア、ファームウェア、デバイスドライバ、又はソフトウェアとして実施される場合がある。実施形態によっては、複数のモジュールの機能が、単一のデータ処理コンポーネントとして結合される場合がある。また、実施形態によっては、モジュールの１以上の機能はそれぞれ、一組のデータ処理コンポーネントによって実施される場合がある。
【０１３３】
実施形態によっては、グラフィックスオブジェクト配置システム６０の種々の実施形態により実施される方法を実施するための処理命令（例えば、コンピュータソフトウェアのような機械読取可能なコード）、及び当該処理命令が生成するデータは、１以上の機械読取可能な媒体に記憶される場合がある。それらの命令、及びデータを実際に実施するのに適した記憶装置には、あらゆる形の不揮発性コンピュータ読取可能メモリが含まれ、例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、及びフラッシュメモリデバイスのような半導体メモリデバイス、内蔵ハードディスクやリムーバブルハードディスクのような磁気ディスク、光磁気ディスク、ＤＶＤ−ＲＯＭ／ＲＡＭ、及びＣＤ−ＲＯＭ／ＲＡＭなどが含まれる。
【０１３４】
一般に、グラフィックスオブジェクト配置システム６０の種々の実施形態は、非常に様々な電子装置のうちのいずれの形で実施してもよく、例えば、デスクトップコンピュータ、ワークステーションコンピュータ、ビデオレコーディングデバイス（例えば、ＶＣＲ、及びＶＤＲ）、ケーブル、又は、有料ビデオ番組をデコードし、再生する機能を備えた衛星セットトップボックス、及びデジタルカメラデバイスの形で実施される場合がある。処理リソース、及び記憶リソースの効率的使用のために、グラフィックスオブジェクト配置システム６０は、実施形態によっては、控えめな処理能力、及び控えめな記憶容量を有する比較的小さく、安価な構成要素を使用して実施される場合がある。その結果、そのような実施形態は、サイズ、処理能力、及び記憶容量に大きな制限がある小型カメラ環境への組み込みに非常に適し、限定はしないが例えば、携帯電子装置（例えば、携帯電話機、コードレス電話機、スマートカードのような携帯メモリデバイス、携帯情報端末（ＰＤＡ）、半導体デジタルオーディオプレイヤ、ＣＤプレイヤ、ＭＣＤプレイヤ、ゲームコントローラ、ポケットベル、及び小型静止画カメラ、又は小型ビデオカメラ）、ｐｃカメラ、及び他の組み込み環境への組み込みに非常に適している。
【０１３５】
図１９は、本明細書に記載するグラフィックスオブジェクト配置システム７６０の実施形態のうちのいずれかを含むコンピュータシステム７６０の一実施形態を示している。コンピュータシステム６０は、処理ユニット７６２（ＣＰＵ）、システムメモリ７６４、並びに、処理ユニット７６２をコンピュータシステム７６０の種々のコンポーネントに接続するシステムバス６６を含む。処理ユニット７６２は通常、１以上のプロセッサを含み、各プロセッサは、種々の市販のプロセッサのうちのいずれの形態のものであってもよい。システムメモリ７６４は通常、コンピュータシステム７６０の開始ルーチンを含む基本的な入出力システム（ＢＩＯＳ）を記憶するリードオンリーメモリ（ＲＯＭ）と、ランダムアクセスメモリ（ＲＡＭ）とを含む。システムバス７６６は、メモリバスであっても、周辺機器用バスであっても、ローカルバスであってもよく、ＰＣＩ、ＶＥＳＡ、マイクロチャネル、ＩＳＡ、及びＥＩＳＡのような種々のバスプロトコルのうちのいずれかと互換性を有するものであってもよい。コンピュータシステム７６０はさらに、永久記憶装置７６８（例えば、ハードディスクドライブ、フロッピーディスクドライブ、ＣＤＲＯＭドライブ、磁気テープドライブ、フラッシュメモリデバイス、及びデジタルビデオディスク）を含み、永久記憶装置７６８は、システムバス７６６に接続され、データ、データ構造、及びコンピュータ実行可能命令のための不揮発性記憶装置、又は永久記憶装置として機能する１以上のコンピュータ読取可能媒体を含む。
【０１３６】
ユーザは、１以上の入力デバイス７７０（例えば、キーボード、コンピュータマウス、マイクロフォン、ジョイスティック、及びタッチパッド）を使用して、コンピュータ７６０と対話（例えば、コマンド、又はデータの入力を）することができる。情報は、ディスプレイモニタ７７２に表示されたグラフィカルユーザインタフェース（ＧＵＩ）を通してユーザに表示され、ディスプレイモニタ７７２は、ディスプレイコントローラ７７４によって制御される。また、コンピュータシステム７６０は通常、スピーカ、及びプリンタのような周辺出力装置をさらに含む。１以上のリモートコンピュータが、ネットワークインタフェースカード（ＮＩＣ）７７６を通してコンピュータシステム７６０に接続される場合がある。
【０１３７】
図１２に示すように、システムメモリ７６４はさらに、グラフィックスオブジェクト配置システム７６０、ＧＵＩドライバ７７８、並びに、グラフィックスオブジェクト６２、中間処理データ、及び出力データに対応するグラフィックスオブジェクトファイルを有するデータベース７８０を記憶する。実施形態によっては、グラフィックスオブジェクト配置システム７６０は、グラフィックスオブジェクトのユーザ指定レイアウトの作成、及びグラフィックスオブジェクトの最終レイアウトの作成を制御するために、ＧＵＩドライバ７７８、及びユーザ入力７７０に接続される場合がある。実施形態によっては、グラフィックスオブジェクト配置システム７６０は、ディスプレイモニタ７７２上に画像データを描画し、ユーザ指定グラフィックスオブジェクトレイアウト、及びそれら自体のグラフィックスオブジェクトに対する種々の処理を実施するグラフィックスアプリケーションプログラムをさらに含む場合がある。
【０１３８】
Ｖ．結び
本明細書に詳細に記載される実施形態によれば、グラフィックスオブジェクトを１以上のページ上に配置する種々の方法が得られる。これらの実施形態は、各レイアウト（又は、配置）におけるグラフィックスオブジェクトの相対位置についての明確な好みによって管理され、又は制御されることができる。同時に、これらの実施形態は、それらの好みから、指定された設計上の制限（例えば、ページ寸法、マージン、及びガッター余白制限）に従ってグラフィックスオブジェクトの最終レイアウトを自動生成することができる。このように、ユーザは、より専門的に、かつより美術的に美しい形でクリーナを表示しながら、それらの実施形態を、ユーザの一般的なグラフィックス配置の好みに合致するグラフィックスオブジェクトの特定のレイアウトに導くことができる。
【０１３９】
他の実施形態は、特許請求の範囲内である。
【特許請求の範囲】
【請求項１】
グラフィックスオブジェクト(72)のユーザ指定レイアウト(80)を受け取るステップと、
前記ユーザ指定レイアウト(80)から、前記グラフィックスオブジェクト(72)の相対位置を表す相対レイアウト仕様(84)を導出するステップと、
前記相対レイアウト仕様(84)に従って、前記グラフィックスオブジェクト(72)のページ(82)上のサイズ寸法、及び位置に関する仕様を含む前記グラフィックスオブジェクト(72)の最終レイアウト(102)を決定するステップと、
前記グラフィックスオブジェクト(72)の最終レイアウト(102)を出力するステップと
からなる方法。
【請求項２】
前記受け取るステップは、前記グラフィックスオブジェクト(72)のページ(116)上の対応する位置へのマッピングを前記ユーザから受け取ることを含む、請求項１に記載の方法。
【請求項３】
前記受け取るステップは、グラフィカルユーザインタフェース(110)上に前記ユーザ指定レイアウトを構築するコマンドを前記ユーザから受け取ることを含む、請求項１に記載の方法。
【請求項４】
前記受け取るステップは、ページ上の前記グラフィックスオブジェクト(72)の表現のレイアウトの画像(126)、及び前記グラフィックスオブジェクト(72)の表現と対応するものとの間のマッピングを、前記ユーザから受け取ることを含む、請求項１に記載の方法。
【請求項５】
前記導出するステップは、前記ユーザ指定レイアウト(80)における前記グラフィックスオブジェクト(72)間の分割(86-100)を解明するステップを含む、請求項１に記載の方法。
【請求項６】
前記解明するステップは、前記ユーザ指定レイアウト(140)の水平ヒストグラムプロファイル、及び垂直ヒストグラムプロファイル(144, 146)を判定し、前記グラフィックスオブジェクトを相互に分離するパーティション(156, 170, 178)を決定するステップを含む、請求項５に記載の方法。
【請求項７】
前記判定するステップは、前記相対レイアウト仕様(84)に従って前記グラフィックスオブジェクト(72)のサイズ寸法を計算し、計算されたサイズ寸法に少なくとも一部基いて前記相対レイアウト仕様(84)に従って前記ページ(82)上の前記グラフィックスオブジェクト(72)の位置の仕様を生成することを含む、請求項１に記載の方法。
【請求項８】
ページ上にグラフィックスオブジェクトを配置するためのコンピュータ読取可能媒体であって、コンピュータに、
グラフィックスオブジェクトのユーザ指定レイアウトを受け取るステップと、
前記ユーザ指定レイアウトから、前記グラフィックスオブジェクトの相対位置を表す相対レイアウト仕様を導出するステップと、
前記相対レイアウト仕様に従って、前記グラフィックスオブジェクトのページ上のサイズ寸法、及び位置に関する仕様を含む前記グラフィックスオブジェクトの最終レイアウトを決定するステップと、
前記グラフィックスオブジェクトの最終レイアウトを出力するステップと
を含む処理を実施させるコンピュータ読取可能命令を記憶するコンピュータ読取可能媒体。
【請求項９】
コンピュータ読取可能メモリ(764, 768)と、
グラフィックスオブジェクト(72)のユーザ指定レイアウト(80)を受け取り、
前記ユーザ指定レイアウト(80)から、前記グラフィックスオブジェクト(72)の相対位置を表す相対レイアウト仕様(84)を導出し、
前記相対レイアウト仕様(84)に従って、前記グラフィックスオブジェクト(72)のページ(82)上のサイズ寸法、及び位置に関する仕様を含む前記グラフィックスオブジェクト(72)の最終レイアウト(102)を決定し、
前記グラフィックスオブジェクト(72)の最終レイアウト(102)を出力するように構成された処理装置ユニット(762)と
からなる装置。
【請求項１０】
グラフィックスオブジェクト(72)のユーザ指定レイアウト(80)を受け取る手段と、
前記ユーザ指定レイアウト(80)から、前記グラフィックスオブジェクト(72)の相対位置を表す相対レイアウト仕様(84)を導出する手段と、
前記相対レイアウト仕様(84)に従って、前記グラフィックスオブジェクト(72)のページ(82)上のサイズ寸法、及び位置に関する仕様を含む前記グラフィックスオブジェクト(72)の最終レイアウト(102)を決定する手段と、
前記グラフィックスオブジェクト(72)の最終レイアウト(102)を出力する手段と
からなる装置。
【請求項１】
グラフィックスオブジェクト(72)のユーザ指定レイアウト(80)を受け取るステップと、
前記ユーザ指定レイアウト(80)から、前記グラフィックスオブジェクト(72)の相対位置を表す相対レイアウト仕様(84)を導出するステップと、
前記相対レイアウト仕様(84)に従って、前記グラフィックスオブジェクト(72)のページ(82)上のサイズ寸法、及び位置に関する仕様を含む前記グラフィックスオブジェクト(72)の最終レイアウト(102)を決定するステップと、
前記グラフィックスオブジェクト(72)の最終レイアウト(102)を出力するステップと
からなる方法。
【請求項２】
前記受け取るステップは、前記グラフィックスオブジェクト(72)のページ(116)上の対応する位置へのマッピングを前記ユーザから受け取ることを含む、請求項１に記載の方法。
【請求項３】
前記受け取るステップは、グラフィカルユーザインタフェース(110)上に前記ユーザ指定レイアウトを構築するコマンドを前記ユーザから受け取ることを含む、請求項１に記載の方法。
【請求項４】
前記受け取るステップは、ページ上の前記グラフィックスオブジェクト(72)の表現のレイアウトの画像(126)、及び前記グラフィックスオブジェクト(72)の表現と対応するものとの間のマッピングを、前記ユーザから受け取ることを含む、請求項１に記載の方法。
【請求項５】
前記導出するステップは、前記ユーザ指定レイアウト(80)における前記グラフィックスオブジェクト(72)間の分割(86-100)を解明するステップを含む、請求項１に記載の方法。
【請求項６】
前記解明するステップは、前記ユーザ指定レイアウト(140)の水平ヒストグラムプロファイル、及び垂直ヒストグラムプロファイル(144, 146)を判定し、前記グラフィックスオブジェクトを相互に分離するパーティション(156, 170, 178)を決定するステップを含む、請求項５に記載の方法。
【請求項７】
前記判定するステップは、前記相対レイアウト仕様(84)に従って前記グラフィックスオブジェクト(72)のサイズ寸法を計算し、計算されたサイズ寸法に少なくとも一部基いて前記相対レイアウト仕様(84)に従って前記ページ(82)上の前記グラフィックスオブジェクト(72)の位置の仕様を生成することを含む、請求項１に記載の方法。
【請求項８】
ページ上にグラフィックスオブジェクトを配置するためのコンピュータ読取可能媒体であって、コンピュータに、
グラフィックスオブジェクトのユーザ指定レイアウトを受け取るステップと、
前記ユーザ指定レイアウトから、前記グラフィックスオブジェクトの相対位置を表す相対レイアウト仕様を導出するステップと、
前記相対レイアウト仕様に従って、前記グラフィックスオブジェクトのページ上のサイズ寸法、及び位置に関する仕様を含む前記グラフィックスオブジェクトの最終レイアウトを決定するステップと、
前記グラフィックスオブジェクトの最終レイアウトを出力するステップと
を含む処理を実施させるコンピュータ読取可能命令を記憶するコンピュータ読取可能媒体。
【請求項９】
コンピュータ読取可能メモリ(764, 768)と、
グラフィックスオブジェクト(72)のユーザ指定レイアウト(80)を受け取り、
前記ユーザ指定レイアウト(80)から、前記グラフィックスオブジェクト(72)の相対位置を表す相対レイアウト仕様(84)を導出し、
前記相対レイアウト仕様(84)に従って、前記グラフィックスオブジェクト(72)のページ(82)上のサイズ寸法、及び位置に関する仕様を含む前記グラフィックスオブジェクト(72)の最終レイアウト(102)を決定し、
前記グラフィックスオブジェクト(72)の最終レイアウト(102)を出力するように構成された処理装置ユニット(762)と
からなる装置。
【請求項１０】
グラフィックスオブジェクト(72)のユーザ指定レイアウト(80)を受け取る手段と、
前記ユーザ指定レイアウト(80)から、前記グラフィックスオブジェクト(72)の相対位置を表す相対レイアウト仕様(84)を導出する手段と、
前記相対レイアウト仕様(84)に従って、前記グラフィックスオブジェクト(72)のページ(82)上のサイズ寸法、及び位置に関する仕様を含む前記グラフィックスオブジェクト(72)の最終レイアウト(102)を決定する手段と、
前記グラフィックスオブジェクト(72)の最終レイアウト(102)を出力する手段と
からなる装置。
【図１】
【図２】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図３Ｄ】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３Ａ】
【図１３Ｂ】
【図１４Ａ】
【図１４Ｂ】
【図１５Ａ】
【図１５Ｂ】
【図１６】
【図１７】
【図１８】
【図１９】
【図２】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図３Ｄ】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３Ａ】
【図１３Ｂ】
【図１４Ａ】
【図１４Ｂ】
【図１５Ａ】
【図１５Ｂ】
【図１６】
【図１７】
【図１８】
【図１９】
【公表番号】特表２０１０−５４１０９７（Ｐ２０１０−５４１０９７Ａ）
【公表日】平成２２年１２月２４日（２０１０．１２．２４）
【国際特許分類】
【出願番号】特願２０１０−５２７９５３（Ｐ２０１０−５２７９５３）
【出願日】平成２０年９月２６日（２００８．９．２６）
【国際出願番号】ＰＣＴ／ＵＳ２００８／０１１１８５
【国際公開番号】ＷＯ２００９／０４５３３６
【国際公開日】平成２１年４月９日（２００９．４．９）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（５０３００３８５４）ヒューレット−パッカード デベロップメント カンパニー エル．ピー． (1,145)
【Ｆターム（参考）】
【公表日】平成２２年１２月２４日（２０１０．１２．２４）
【国際特許分類】
【出願日】平成２０年９月２６日（２００８．９．２６）
【国際出願番号】ＰＣＴ／ＵＳ２００８／０１１１８５
【国際公開番号】ＷＯ２００９／０４５３３６
【国際公開日】平成２１年４月９日（２００９．４．９）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（５０３００３８５４）ヒューレット−パッカード デベロップメント カンパニー エル．ピー． (1,145)
【Ｆターム（参考）】
[ Back to top ]