オブジェクトを位置付ける方法、並びに、予め定められたスペースにイメージを位置付ける方法
【課題】 最小量の空スペース及び最大のレイアウト設計多様性を有し、イメージのクロッピングを控え、従来のグラフィック配置ソフトウェアに関連する欠点を最小化した、グラフィックイメージをページに効率的に配置するソフトウェアソリューションを提供する。
【解決手段】 スペース内のオブジェクトのレイアウトを組み立てることによってオブジェクトを位置付ける方法において、少なくとも１つのノード、及び、各々が１つのオブジェクトに対応する少なくとも１つのリーフを有するツリー構造を生成するステップと、ツリー構造中の各ノードのバウンディングボックスであって、各々がノードの下位にあるサブツリー中の何れのオブジェクトも全て含むバウンディングボックスを特徴付けるステップと、ノードに関連するバウンディングボックスに従って、スペース内の領域をツリー構造中の各ノードに割り当てるステップとを含む。
【解決手段】 スペース内のオブジェクトのレイアウトを組み立てることによってオブジェクトを位置付ける方法において、少なくとも１つのノード、及び、各々が１つのオブジェクトに対応する少なくとも１つのリーフを有するツリー構造を生成するステップと、ツリー構造中の各ノードのバウンディングボックスであって、各々がノードの下位にあるサブツリー中の何れのオブジェクトも全て含むバウンディングボックスを特徴付けるステップと、ノードに関連するバウンディングボックスに従って、スペース内の領域をツリー構造中の各ノードに割り当てるステップとを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、要素の計算配置の分野に関し、特に、写真又はグラフィックイメージをページ上に効率的に配置又は位置付けることに関する。すなわち、本発明は、フォトアルバムの自動ページレイアウトに関する。
【背景技術】
【０００２】
現在、視覚的に美しいフォーマットでグラフィックイメージを収集して表示するコンピュータソフトウェアがユーザに提供されている。このようなコンピュータソフトウェアは、ユーザにより選択され、様々な様式で配置された一連のページを備えたフォトアルバムと呼ばれるものを作成する（develop）。本明細書では、フォトアルバムのページは、固定サイズのページに配置された複数のグラフィックイメージ又はピクチャを指す。本明細書では、グラフィックイメージ又はピクチャは、矩形の境界を有すると考えることができるような、テキストを含め、略あらゆるもののソフトウェア描写を指す。グラフィックファイルの例としては、.gif、.tiff、及び.jpegグラフィック表現が挙げられるが、境界を有する略何れのイメージも含むことができる。例えば、楕円形ブロックのテキストは、任意の境界を含む、楕円形ブロックの上下左右の側に接する矩形の境界を有するグラフィックイメージ又はピクチャとして考えることができる。
【０００３】
グラフィックイメージをフォトアルバムのページのどこに、どのように配置するかを判断するに際して、ソフトウェアは、環境に固有の様々な問題に対処しなければならない。例えば、ページ上のピクチャの枚数，互いに対するピクチャのサイズ，ピクチャの空間的分布，利用可能な空きスペース，及びキャプションの存在は全て、選択されたグラフィックイメージをフォトアルバムのページに配置する際に考慮される。
【０００４】
グラフィックイメージを配置する従来のソフトウェアシステムにおいては、配置は、往々にして「手で」行われる。このプロセスでは、ユーザは、ブランクページドキュメントを開き、デジタルグラフィックイメージをインポートしていた。ソフトウェアは、ユーザがイメージをページのあちこちに移動できるようにし、おそらくは美しいピクチャレイアウトを達成するようにサイズ変更を可能にすることにより、フォトアルバムのページ上に「レイアウト」生成した。手で写真の移動及びサイズ変更を行うプロセスは、面倒で時間のかかるものであり得る。これに応じて、開発者は、レイアウトプロセスを少なくとも一部自動化することを意図した自動ソフトウェアパッケージを作成した。
【０００５】
特定のソフトウェアパッケージは、イメージを行列に配置することによってレイアウトプロセスを自動化している。イメージが、全て同じサイズ及び形状の別個の領域に強制的に入るようにすることから、この種類のソフトウェアパッケージを使用して作成されるレイアウトはイメージのアスペクト比を考慮せず、グラフィックイメージがレイアウトで配置されたときに歪んで見える場合がある。この種類の方策では、ページ上に未使用の空スペースが生じる場合があり、これは視覚的に魅力がなく、利用可能なスペースを無駄にしている。
【０００６】
他のソフトウェアパッケージによっては、イメージが固定のテンプレート開口部、又は「ホール」に手動で挿入されるテンプレートを提供するものがある。テンプレートは魅力的であり、スペースを効率的に使用することができるが、利用可能なテンプレートは、テンプレートホールのアスペクト比がイメージのアスペクト比と相関しないために使用することができない場合が多い。イメージは、特定のテンプレートホール内で受け入れられる外観及びアスペクト比を提供するようにクロッピングすることができるが、クロッピングは、一般に、イメージの一部を破棄する必要があるため満足の得られるものではない。また、イメージは、テンプレートホールを通して完全に、かつクロッピングなしで現れるように縮小することができるが、このようなサイズの縮小は、イメージが小さく見え、従って見にくくなるため満足の得られるものではない場合がある。ソフトウェアパッケージによっては、ユーザが新しいテンプレートを作成できるものもあるが、テンプレート作成プロセスは、通常、手動でのレイアウトに等しいため、面倒で時間がかかる。
【０００７】
特定の、一般に利用可能なソフトウェアパッケージは、特定のレイアウト設計上の問題を有する。Ｋｏｄａｋ Ｍｅｍｏｒｙ Ａｌｂｕｍｓ（「ＫＭＡ」）は、テンプレートを使用することなくアルバムページレイアウトを自動的に生成するように見える傾向を示す。しかし、ＫＭＡは、単純に付近のイメージを拡大することによって埋めることができるであろう空きスペースを残す。また、ユーザが生成されたレイアウトを好まない場合には、ユーザに提供される代替のレイアウトは１つか２つのみである。４つ未満のレイアウトの世界は、一般に、あまりに限定的である。
【０００８】
Ｃａｎｏｎ ＰｈｏｔｏＲｅｃｏｒｄ Ｇｏｌｄ（「ＣＰＧ」）は、自動フォトアルバムページレイアウトを提供する別のソフトウェアパッケージである。一モードにおいては、ＣＰＧは、所望の数のイメージを収容するテンプレートを作成する方法を採用するように見える。しかし、このモードでは、イメージサイズが無視されて見え、これはイメージの重複をもたらす可能性がある。イメージの重複は不規則であると共に、多くの場合は過大であるため、一般に魅力的でない。別法として、ＣＰＧユーザは、ページ上で１枚のイメージを移動することができ、その間に、ソフトウェアはその他のイメージをページのあちこちにシフトして、移動中のイメージに適応する。イメージ位置シフトの制御は、でたらめに見え、場合によってはイメージが完全に隠れてしまうことになる。
【０００９】
ＬｕｍａＰｉｘからのＦｏｔｏＦｕｓｉｏｎ（「ＦＦ」）と呼ばれる別の製品は、写真の単一ページコラージュを生成する。ＦＦは、入力イメージのリストをとり、全てのイメージの単一ページレイアウトを生成し、様々な代替のレイアウトを生成する能力を提供するオートコラージュ（autocollage）機能を有する。オートコラージュ機能によって生成されるレイアウトでは、写真の間に白色スペースはほとんどないか、又は全く存在せず、写真は、壁の中のレンガのように一緒にはまる。しかし、レイアウト中の写真はクロッピングされ、写真の一部は破棄され、これは満足のいくものではない。
【００１０】
現在利用可能な何れのソフトウェア設計でも、ユーザは、提示されたイメージ全体を保持しながら、それと同時に複数のイメージの相対的なイメージサイズを指定することができない。相対的なイメージサイズの指定は、例えば、ユーザが１枚のイメージをページ上のその他の全てのイメージよりも可成り大きくしたい場合に望ましいであろう。さらに、現在利用可能なソフトウェア設計は、提示されたイメージ全体を保持しながら、それと同時に、ページ上のイメージが占める矩形領域内の空の未使用スペースを完全にはなくしていない。この矩形領域は、イメージによって仕切られる「凸閉包」（convex hull）として説明することができる。
【００１１】
特定のフロアプランニング又はレイアウトツリー構造が異なるコンテキストの中で採用されてきている。例えば、レイアウトツリー構造をＶＬＳＩ回路レイアウトに使用する者もいれば、一般のドキュメントレイアウトに使用する者もいる。しかし、ＶＬＳＩ回路レイアウトでは、回路はサイズ固定であることができるが、通常、固定のアスペクト比を有さない。従って、回路は、ｘとｙの比率保持を顧慮することなく、ｘ次元及びｙ次元において独立して変更することが可能である。フロアプランニングソリューションは、往々にしてイメージ配置設計に関連するアスペクト比保持要件により、イメージ配置設計とは大幅に異なる傾向がある。一般のドキュメントレイアウトでは、イメージレイアウトとは対照的に、アスペクト比もまた変数として考えられる。
【発明の概要】
【発明が解決しようとする課題】
【００１２】
従って、最小量の空スペース及び最大のレイアウト設計多様性を有し、それと同時に、受け取ったイメージのクロッピングを控え、従来のグラフィック配置ソフトウェアに関連する欠点を最小化した、グラフィックイメージをページに効率的に配置するソフトウェアソリューションを提供することが望ましい。
【課題を解決するための手段】
【００１３】
本発明の第１の態様によれば、物理的ページを表すスペース内のオブジェクトのレイアウトを組み立てることによってオブジェクトを位置付ける方法が提供される。本方法は、少なくとも１つのノード（node）、及び、各々が１つのオブジェクトに対応する少なくとも１つのリーフ（leaf）を有するツリー構造を生成するステップと、前記ツリー構造中の各ノードのバウンディングボックスであって、各々が前記ノードの下位にあるサブツリー中の何れのオブジェクトも全て含むバウンディングボックスを特徴付けるステップと、前記ノードに関連する前記バウンディングボックスに従って、前記スペース内の領域を前記ツリー構造中の各ノードに割り当てるステップとを含む。
【００１４】
本発明の第２の態様によれば、固定アスペクト比オブジェクトを予め定められたスペースに割り当てる方法が提供される。本方法は、１つのオブジェクトにそれぞれ対応する複数のリーフ及び少なくとも１つのノードを有するバイナリツリー構造（２分木構造）を生成するステップを含む。この場合、各ノードは、そこから分岐する全てのノード及びリーフに関連し、そこから分岐する全てのノード及びリーフを代表するものである。本方法は、バイナリツリー構造中の各ノードに適宜サイズのバウンディングボックスであって、そこから分岐する全てのノード及びリーフの境界を画定する各ノードのバウンディングボックスを画定するステップと、予め定められたスペース内にはまるように少なくとも１つの適宜サイズバウンディングボックスを操作することにより、前記予め定められたスペースにオブジェクトを位置付けるステップとをさらに含む。
【００１５】
本発明の第３の態様によれば、イメージに関連するアスペクト比を保持しながら予め定められたスペースに前記イメージを位置付ける方法が提供される。本方法は、少なくとも１つのノード、及び、各々が１枚のイメージに対応すると共に１つのノードに関連する複数のリーフを有するバイナリツリー構造を生成するステップと、前記バイナリツリー構造中の各ノードのバウンディングボックスであって、前記ノードに関連する全てのリーフの境界を確立するバウンディングボックスを特徴付けるステップと、バウンディングボックスを操作して、前記予め定められたスペースに適合させるステップとを含む。
【００１６】
本発明の全ての態様のこれら及び他の目的及び利点は、添付図面に示した好ましい実施形態の以下の詳細な開示を読んだ後に、当業者に明らかになろう。
【００１７】
本発明は、限定ではなく例として添付図面の図に示されている。
【図面の簡単な説明】
【００１８】
【図１】プリントされたページ等のような予め定められたスペースにおけるストリクトエリアレイアウトの概念を示す図である。
【図２】オブジェクト又はイメージのブリックスタイルレイアウトを示す図である。
【図３】アスペクト比及び相対面積比率の概念を示す図である。
【図４】入力及び出力を示す完全フォトアルバム作成システムの一実施形態を概略的かつ全体的に説明するフローチャートである。
【図５Ａ】ページ等のような予め定められたエリアを下位エリアに順次分割することを示す図である。
【図５Ｂ】分割された、予め定められたエリア及びそれに対応するバイナリツリー構造を示す図である。
【図６】完全フォトアルバム作成システムの一実施形態の詳細なフローチャートである。
【図７】バウンディングボックスの形成を示すフローチャートであって、図６の要素６０４と等価なフローチャートである。
【図８】図７のブロック７０１を表すフローチャートである。
【図９】図７のブロック７０２を表すフローチャートである。
【図１０】入力及び出力を含む、シングルパス設計によるフォトアルバム作成システムの一実施形態を広く概念的に説明するフローチャートである。
【図１１Ａ】シングルパス設計によるフォトアルバム作成システムの一実施形態を詳細に説明するフローチャートの第１部分である。
【図１１Ｂ】シングルパス設計によるフォトアルバム作成システムの一実施形態を詳細に説明するフローチャートの第２部分である。
【図１２】シングルパス設計によるイメージ又はオブジェクトの順次ロード（順次挿入）を示す図である。
【図１３Ａ】４つの関連イメージ及び新しいイメージ５を挿入する要望を有するツリーを示す図である。
【図１３Ｂ】新しいイメージ５を新しい水平分割ノードの下に位置付けすること、及び元のイメージ１及び４を新しい水平分割ノードの子として位置付けすることを示す図である。
【図１３Ｃ】新しいイメージ５を新しい垂直分割ノードの下に位置付けすること、及び元のイメージ１及び４を新しい垂直分割ノードの子として位置付けすることを示す図である。
【図１４】シングルパス設計による正規化プロセスのフローチャートである。
【図１５Ａ】図６の要素６０５の動作を表す図である。
【図１５Ｂ】採用される変数、並びに、図１５Ａ，図１６，及び図１７によって表されるように、要素６０５の実行に際しての使用に利用可能な値のプレロードを示す図である。
【図１６】所望の親の切断方向が垂直である場合の要素６０５の動作を示す図である。
【図１７】所望の親の切断方向が水平である場合の要素６０５の動作のフローチャートである。
【発明を実施するための形態】
【００１９】
本発明による設計は、２つの機能、すなわちユーザが選択可能であり、大部分をユーザ入力に頼る、多種多様なイメージレイアウトを作成するフル機能（full function）、及び計算集約度がフル機能よりも低いが、ユーザからのより少ない入力に基づいて視覚的に魅力的なレイアウトをより短い時間期間で生成する「シングルパス」機能（「single pass」function）を含む。
【００２０】
フル機能及びシングルパス機能の両方に関して、２つの特定のレイアウト動作モード、すなわち、「ストリクトエリア」（strict area）レイアウト及び「ブリック」（brick）レイアウトが考えられる。
【００２１】
図１は、ストリクトエリアレイアウト動作モードを示している。ストリクトエリアは、一般に、ページの特定のエリア又は下位エリア内に厳格に位置付けられたイメージを指す。概念上、ページは、ページの左半分及び右半分等、複数の下位エリアに分割することができ、ストリクトエリアレイアウトモードは、１枚のイメージをページの右半分でセンタリングし、別のイメージをページの左半分でセンタリングすることができる。ストリクトエリアレイアウト動作モードを使用する場合には、ユーザは、ページをエリアに分割する目的で使用される相対面積比率値を各イメージに提供することができる。相対面積比率値の使用により、ユーザは、１枚のイメージを、同ページ上の第２のイメージのエリアの１／３、かつ第３のイメージのエリアの１／４になるように指定することが可能になり、エリアはこの選好に従って分割され、イメージはそのように分割された各エリアにおいてセンタリングされる。相対面積比率は数値であり、上記例では、３枚全てのイメージが元々は同じ面積のものである場合、第１の相対面積比率は１．０であり、第２は３．０であり、第３は４．０である。相対面積比率は、後述する主題であるアスペクト比の概念とは無関係である。
【００２２】
数学的には、ストリクトエリア動作モードは、所与のページにおいて、イメージのエリアが、
Ａ1／ｅ1＝Ａ2／ｅ2＝∧＝ＡN／ｅN
を満たすことを示す。式中、Ｎはページ上のイメージ数であり、｛Ａi｝は実際のイメージエリアであり、｛ｅi｝はユーザ指定の相対イメージ面積比率である。ストリクトエリアレイアウトは、相対的なイメージエリアの比率を制御する。ユーザが、イメージＡをイメージＢのサイズの３倍にすると指定する場合には、ストリクトエリアレイアウトモードは、ページ上のイメージＡ及びイメージＢの正確な位置又はサイズに関わりなく、イメージＡがイメージＢのサイズの３倍になるように指示する。ストリクトエリアレイアウトは、また、ユーザがよりくだけた方法で面積制約を指定する場合にも採用することができる。例えば、ユーザは、選択された特定のイメージが同ページ上のその他のイメージよりも大きくなるべき（すなわち、厳密な乗算係数だけ大きくなるのではない）旨を指定することができる。
【００２３】
図２は、代替の「ブリックレイアウト」動作モードを示している。図２では、イメージの間に白色スペースが存在せず、イメージは壁の中のレンガのように一緒にはまっている。ブリックスタイルレイアウトは、空スペースがページ上の写真又はイメージによって仕切られた「凸閉包」に存在しないために視覚的に効率的に見える。
【００２４】
図１及び図２の両方の例はイメージのみを含んだページを示すが、本設計では、レイアウトスタイルに関わりなく、ユーザはキャプションをプリントしたり、又は各イメージの下にブロックを挿入したりすることも可能である。ユーザは、何れのレイアウトスタイルでも、空スペースの「溝幅」を指定して、イメージを分離することも可能である。
【００２５】
図３は、本設計のアスペクト比，エリア，及び相対面積比率の概念を示している。アスペクト比は、イメージの高さをイメージの幅で割った比として定義される。ボックス３０１はアスペクト比２．０を有し、ボックス３０２はアスペクト比０．５（１対２）を有する。システムは、動作全体を通してアスペクト比を保持しようと努める。各イメージは、ページ上のエリアを占める。本明細書では、「エリア」は、例えば、平方インチ単位で測定することが可能な、レンダリングイメージの固定属性である。（８．５インチ）ラ（１１．０インチ）の用紙を仮定すると、ページエリアは、９３．５平方インチである。そのページにプリントされる、高さ４．０インチ及び幅６．０インチの写真は、２４．０平方インチのエリアを有する。本明細書では、「相対面積比率」は、同じページ上の２枚のイメージのエリアを比較する際に使用されるイメージ属性である。ここで、「相対面積比率」及び「エリア」は関連するが異なる概念であり、前者は純粋に相対的な性質のものであり、後者は絶対的かつ測定可能なものである。レイアウト３０３は、相対面積比率１．０を有する第１のイメージ３０４及び相対面積比率４．０を有する第２のイメージ３０５を具備したページを示す。相対面積比率は、係数「４」だけ異なるため、それぞれの測定可能エリアの特定の数値に関わりなく、レンダリングされる出力（例えば、プリントされたページ上，物理的空間表現上，又はコンピュータディスプレイ上）における２枚のイメージの測定可能なエリアもそうである。
【００２６】
図４は、完全フォトアルバム作成システム４００のフローチャートを示している。フォトアルバム作成システム４００への入力は、アルバムに含めるべきイメージのリスト４０１であり、ここでリスト４０１は、img0.jpg，img1.jpg，及びimg2.jpgをページ１上に含み、その後にページ２上のimg3.jpg及びimg4.jpgが続く。ユーザの望みに応じて他のリストを提供することもできる。このようなリストは、各改ページの位置を示すことができる。別法として、本設計は、タイムスタンプ又は他の利用可能なコンピュータ情報を用いて改ページを判断することができる。例えば、数枚のイメージが互いに数秒間に取り込まれ、その後に休止があり、その後により多数のイメージが続いていた場合には、時間的にはっきりと分けられた２つのグループの間に改ページを位置付けることができる。フォトアルバム作成システム４００からの出力は、例えば、pdf，jpg，又は通常はグラフィック的性質の他の利用可能なフォーマットのページの集まり等のフォトアルバム出力である。
【００２７】
一般に、本設計の焦点は、システムが大まかにグラフィックイメージをツリー構造中のリーフノードに割り当てる比較的雑なレイアウト構成から、ユーザ指定のレイアウト動作モードに一貫した厳密なレイアウト構成への進展である。
【００２８】
本明細書にて使用する用語の定義を目的として、「ツリー」は、ツリーの構成要素が利用可能なページの特徴に対応する、図５Ｂの右側に示すもの等の構造である。そこから出るブランチ（分岐）を有するツリー中のポイントは、「ノード」と呼ばれ、そこから出るブランチを有さないツリー中のポイントは「リーフ」と呼ばれる。ページは、図５Ａに示す様式等、順次分割することができる。各分割は、ツリー中の１つのノードに対応する。図５Ｂの左の表現は、元のページから作成された５つの区分を表す、６つの下位エリアに分割されたページを示す。図５Ｂの右の表現は、６つの終点、すなわちリーフ５０１，５０２，５０３，５０４，５０５，及び５０６と、５つのノード５０７，５０８，５０９，５１０，及び５１１とを有するツリーである。従って、ツリー５００等のような、本設計において使用されるツリーは、リーフ５０１等の複数のリーフ，ブランチ５１２等の複数のブランチ，及びノード５０７等の複数のノードを含む。本設計は、ユーザの望み及び提示されるイメージに応じて異なるツリー構造を構築し、その結果として生じる各ツリー構造がレイアウトを形成し、複数のツリー構造及びレイアウトを用意することができる。
【００２９】
図６は、本設計の詳細なフローチャートを示している。設計システムへの入力は、ユーザがページ上に表すことを意図するイメージのリスト６０１であり、出力６１１は、イメージリスト６０１中の各イメージの位置及びサイズを示したレイアウト仕様best_Tである。基本的な動作では、システムが、複数の候補レイアウトを、各候補レイアウトのスコアと共に生成し、次に、最高スコアを有する候補レイアウトを出力６１１を介して出力することを含む。
【００３０】
好ましい動作モードは、出力best_Tが、全ての候補レイアウトの中で最高スコアを有する１つの最良のレイアウトを提供することである。しかし、ユーザが複数の代替のレイアウトを調べることを所望するシナリオでは、出力best_Tは、複数のレイアウトを表し得る。例えば、５つのレイアウトツリー構造が、ユーザがその５つの中から選択できるように望まれる場合がある。複数の代替のレイアウトシナリオでは、best_Tは、計算された他の何れのレイアウトよりも高いレイアウトスコアを有する複数の候補レイアウトを表すことができる。
【００３１】
要素６０２は、Ｎ個のリーフノードを有するレイアウトツリー構造Ｔを生成し、要素６０３は、そのようにして生成されたツリー構造を採用し、各イメージをレイアウトツリー構造Ｔ中のリーフに割り当てる。システムは、リーフ，ブランチ，及びノードをランダムに割り当てることができ、ユーザが最終的に別の設計を採用すると決定し、従って前のツリーを再訪したい場合には、試みられた初期のツリーを呼び戻すことができる。要素６０３は、そのようにして作成されたツリー中のリーフにイメージをランダムに割り当てることができる。これはランダムに行うことができ、代替のレイアウトが望まれる場合の選択肢が保持される。図５Ｂを例として採ると、６枚のイメージを受け取ることができ、（５つのノード）−（６つのリーフ）のツリーが採用される。別法として、２つの底にあるリーフ、すなわちリーフ５０２及び５０３をリーフ５０１，５０４，５０５，又は５０６の下に位置付けして、これらリーフをノードにし、ノード５１１をリーフにすることもできる。
【００３２】
要素６０２は、レイアウトツリー構造を生成する異なる方法で実施してもよい。要素６０２に必要な入力はＮ枚のイメージである。レイアウトツリー構造を生成する一方法では、Ｎ枚のリーフ及び（Ｎ−１）個のノードを有するバイナリツリー構造を生成し、その後に、各ノードに切断方向を割り当てるステップを含む。ツリー構造（すなわち、ノードとリーフの網状組織）の形状及びノードに割り当てられる切断方向は両方ともランダムであってよい。本設計の本態様では、システムは、ツリー構造を決定論的に生成し、切断方向がランダムに割り当てられ、コインを実際にはじき、表の場合はＨＯＲＩＺ（水平切断）を割り当て、裏の場合はＶＥＲＴＩＣ（垂直切断）を割り当てる。要素６０３の本実施は、イメージとツリーのリーフとの間にランダムな１対１のマッピングを生成することである。従って、要素６０２及び６０３は、候補レイアウトに一般的な枠組みを提供する。
【００３３】
次に、要素６０４が、ツリー構造Ｔ中の各ノードのサブツリー中のイメージのバウンディングボックスを特徴付ける。本明細書では、ノードの「サブツリー」は、ノード自体と共に、リーフの方向、すなわち本明細書の図面に示すツリーの概して下方向にそのノードから出る全てのブランチ，ノード，及びリーフを持つノード自身として定義される。バウンディングボックスは、イメージ、並びに、任意の関連するキャプション又は他の材料に境界を付けるスペースの領域である。要素６０５において、システムは、ツリー構造Ｔ中の各ノードのバウンディングボックスに従ってページ上の物理的なスペースを割り当てる。要素６０５からの結果は、選択されたレイアウト動作モード、又は所望のレイアウトスタイル（例えば、ストリクトエリアレイアウト又はブリックレイアウト）に呼応して指定される候補レイアウトである。要素６０４及び６０５についてさらに詳細に後述する。
【００３４】
判断要素６０６は、候補レイアウトが最初に形成された候補レイアウトであるか否かを判断し、そうである場合には、要素６０８はツリー構造Ｔを最良ツリー（ｂｅｓｔ＿Ｔ）レジスタ又は記憶位置に移す。判断要素６０６の結果が、候補レイアウトが最初に形成された候補レイアウトではなかったというものである場合には、判断要素６０７がツリー構造Ｔのスコアとbest_Tのスコアを計算する。ツリー構造Ｔのスコアがbest_Tのスコアよりも大きい場合には、ステップ６０８はＴをｂｅｓｔ＿Ｔ位置又はレジスタに移し、制御は次に判断要素６０９に移る。一方、判断要素６０７の結果が、ツリー構造Ｔのスコアがbest_Tのスコア未満であるというものである場合には、制御は判断要素６０９に移る。
【００３５】
スコアは様々な方法で計算することができる。スコアを計算する一方法は、ページ上の空スペースを査定し、ブランクスペースが最も少ないレイアウトを最良レイアウトとするものである。このスコア付けはストリクトエリアレイアウトに使用することができる。その理由は、ストリクトエリアレイアウトの場合には、相対面積比率が既に固定されていることによる。スコアを計算する別の方法は、イメージが最も一様なイメージを探すというものであり、これは、ページ上の最小イメージ面積をページ上の最大イメージ面積で割った比を求め、最も大きな結果を選択することによって達成される。ブリックスタイルレイアウトのスコア付けの場合には、スコア付けは、空スペースも、またイメージエリア一様性も、一方の最適化を犠牲にして他方が過度に悪化しないように、空スペースとイメージエリア一様性の組み合わせを求めることによって行うことができる。
【００３６】
判断要素６０９は、所望数のイメージ−リーフ割り当てが特定のツリー構造Ｔに関して考慮されたか否かを判断する。この所望数は、ユーザ、又はリモート自動プログラム等、他の制御エンティティによって決定することができる。一般に、イメージ−リーフ割り当てに大きな数が指定されるほど、より良好なレイアウトを見つけるチャンスが増える。所望数は、特定のページに対する所望のイメージ数に大きく依存する。イメージ数が少ない場合（例えば、２、３枚のイメージ）、所望数を低く設定してよい。イメージ数が多い場合には、所望数は高く、例えば１００以上であってよい。フローチャートに関して、判断６０９の結果が否定の場合には、制御は要素６０３に戻り、システムが新しいイメージ−リーフ割り当てを生成し、結果として新しいレイアウト構成が生成される。判断要素６０９の結果が肯定の場合には、制御は判断要素６１０に渡る。
【００３７】
判断要素６１０において、システムは、所望数のレイアウトツリー構造が考慮されたか否かを判断する。この場合、所望数は、ユーザ又は他の制御エンティティによって決定することができる。レイアウトツリー構造は、結果生じるレイアウトに大きく影響する。従って、レイアウトツリー構造の数が多いほど、ユーザがより良好なレイアウトを見つけるチャンスが増える。判断要素６１０の結果が肯定の場合には、その結果としてbest_Tが出力６１１に生じる。否定の場合には、システムは、Ｎ枚のリーフノードを有する新しいレイアウトツリー構造Ｔを生成することによって要素６０２を繰り返す。
【００３８】
要素６０４において、レイアウトツリー構造中の各ノード及びリーフについて、システムは、そこをルートとしたサブツリー中のイメージを包含するバウンディングボックスを特徴付ける。システムは、「ａ」で示されるアスペクト比、及び、「ｅ」で示される相対面積比率を計算する。これらパラメータから、システムは、バウンディングボックスを特徴付ける、すなわち規定（定義）する。例えば、アスペクト比４：３は、「ａ」；１．３３３３として特徴付けることができ、相対面積比率は、第１のイメージには「ｅ」；１．０、第２のイメージには、例えば「ｅ」；２．５であってもよく、これは、第２のイメージが第１のイメージよりも２．５倍大きいことが望ましいことを示す。従って、「ａ」；１．３３３３及び「ｅ」；２．５は、操作可能かつ配置可能なバウンディングボックスを規定する。
【００３９】
何れのノードへのバウンディングボックスの特徴付けでも、その２つの子（child）のバウンディングボックスの先験的な特徴付けが必要であり、これについては後述する。この先験的なバウンディングボックスの特徴付け要件により、図６中の要素６０４は、或る意味、一番下のリーフノードからツリーのノードを通して最上部、すなわちルートまでツリーを徐々に上がっていくように動作する。
【００４０】
リーフの場合、要素６０４におけるバウンディングボックスの特徴付けは、アスペクト比が、リーフに割り当てられた写真のアスペクト比に等しいという点で単純である。ストリクトエリアスタイルレイアウトの場合には、ユーザは、相対面積比率を提供し得る。別法として、システムは、リーフの相対面積比率をランダムに、又は動的に決定することができる。ブリックスタイルレイアウトの場合には、相対面積比率の初期数値は重要ではなく、ユーザ又はシステムが任意の正の値を割り当てることができる。
【００４１】
ノードの場合、システムは、図７のフローチャートに従ってバウンディングボックスを形成する。入力は、通常、ストリクトエリアスタイル指示であるか、或いはブリックスタイル指示であるかがユーザによって指定される。ブロック７０１は、システムがブリックスタイル指示を提供する場合に実行され、システムは、所望の切断種類に応じて、ノードの１つの子及びその子の全ての子の相対面積比率を調整する。現在のノードが水平切断を有する場合には、調整は、２つの子のバウンディングボックスの幅が等しくなるように行われる。現在のノードが垂直切断を有する場合には、調整は、２つの子のバウンディングボックスの高さが等しくなるように行われる。ストリクトエリアスタイル及びブリックスタイルの両方で行われるブロック７０２において、システムは、現在のノードの２つの子の相対面積比率及びアスペクト比の関数として、現在のノードの相対面積比率及びアスペクト比を計算する。
【００４２】
動作の際には、現在のノードが垂直切断を提供する場合、ブロック７０１は、右の子のサブツリー中のイメージを含む矩形が、左の子のサブツリー中のイメージを含む矩形と同じ高さを有するように右の子を調整する。同様に、現在のノードが水平切断を提供する場合、ブロック７０１は、左の子と同じ幅を有するように右の子を調整する。
【００４３】
動作の際に、左の子を調整するのとは対照的に右の子を調整するという判断は、中立である、すなわち「どちらでも構わない」。すなわち、別法として、ブロック７０１は、左の子及び左の子の全ての子を、右の子と同じ高さ又は幅を有するように調整してもよい。システムは、この時点では、変更が可能な相対面積比率を設定しているため、何れの方法を実施してもよい。
【００４４】
具体的には、ブロック７０１において、システムは、右の子及び右の子の全ての子の相対面積比率を以下の係数で乗算する。
【００４５】
【数１】
【００４６】
上記の式において、ｅ1及びａ1はそれぞれ現在のノードの左の子の相対面積比率及びアスペクト比であり、ｅr及びａrはそれぞれ右の子の相対面積比率及びアスペクト比である。
【００４７】
図８は、図７のブロック７０１を表すフローチャートを示しており、図９は、図７のブロック７０２のフローチャートを示している。図８から分かるように、要素８０１は、左右の子の相対面積比率及びアスペクト比を得る。判断８０２における水平切断（本例）が望まれているか否かに応じて、システムは、要素８０３又は８０４に従って係数を計算する。係数が計算されると、要素８０５において、システムは、そうして計算された係数で、右の子及びその右の子の全ての子の相対面積比率を乗算する。図９から分かるように、ここでも、要素９０１は左右の子の相対面積比率及びアスペクト比を得る。ここでも、本例では、システムは、これが水平切断であるか否かについて（判断は別法として、これが垂直切断であるか否かであってもよい）の判断９０２を行う。今の切断が水平である場合には、システムは、判断９０３において、右の子の相対面積比率を右の子のアスペクト比で割ったものが、左の子の相対面積比率を左の子のアスペクト比で割ったものを上回るか否かを判断する。上回る場合には、現在のノードのアスペクト比及び相対面積比率は、要素９０５において計算されるものである。その他の場合には、要素９０４において計算されるものである。今の切断が水平ではない場合には、システムは判断９０６において、右の子の相対面積比率を右の子のアスペクト比で乗算したものが、左の子の相対面積比率を左の子のアスペクト比で乗算したものを上回るか否かを判断する。上回る場合には、現在のノードのアスペクト比及び相対面積比率は、要素９０８において計算されるものである。その他の場合には、要素９０７において計算されるものである。従って、その結果は現在のノードのアスペクト比及び相対面積比率である。
【００４８】
単純な例は、次の通りである。ストリクトエリアスタイルレイアウトの場合には、ユーザが、２枚のイメージＡ及びＢに対して、イメージＡにはｅ1；１．０及びａ1；４．０を指定し、イメージＢにはｅr；２．０及びａr；２．０を指定したとする。従って、子としてイメージＡ及びイメージＢを有するノードの場合には、図９から分かるように、水平切断が望まれていると、判断要素９０３は、２．０／２．０が１．０／４．０よりも大きいか否かを計算する。この場合、１．０は０．２５よりも大きい。従って、ａは（２．０＋２．０）／１．０すなわち４．０に等しく、ｅは（２．０＋２．０）ラ１．０すなわち４．０に等しい。従って、イメージＡ及びＢを含むノードは、アスペクト比；４．０及び相対面積比率；４．０によって画定されるバウンディングボックスを有する。
【００４９】
従って、要素６０５から、システムは、ページ上のスペースの矩形領域を、ノードをルートとするサブツリー中に含まれるレイアウトツリー構造中の各ノードに関連するイメージを割り振る。スペースの矩形領域は、領域の高さ及び幅を指すのみならず、ページの境界に対する領域の絶対位置も指す。スペースをルートノードではない何れのノードにも割り振る際には、システムは、そのノードの親にスペースを既に割り振っていることを考慮する。従って、概念上、要素６０５は、ルートノードから始まってリーフノードで終わる、ツリー構造の「上から下への」作業をすることによって動作する。ステップ６０５において割り振られたスペースの領域は、ステップ６０４において決定されたバウンディングボックスとは異なる。主な違いは、スペースの領域が、平方インチ又は平方ミリメートル等距離単位で測定可能な、レンダリングされた出力ページの実際の物理的なエリアを反映している一方で、バウンディングボックスは、占めるエリアの相対的表記を使用して表現されることである。
【００５０】
動作に際し、要素６０５は、システムに、まず、ページ全体のスペースの領域をルートノードに割り当てさせる。この「ページ全体」は、物理的なページの面全体、又は物理的なページの使用可能な部分のみを表すことができる。例えば、ページ全体は、余白，ヘッダ，及びフッタに予め向けられているスペースを含まない。従って、システムは、スペースの領域の高さ及び幅をルートノードに割り当て、さらに、スペースの領域の左下位置を示す空間位置座標をさらに割り当てる。スペースの領域の中心、又はスペースの領域の右上角等、他の空間位置座標を使用してもよい。スペースの領域は、領域の概念的表現にさらに割り当てることができる。
【００５１】
スペースの領域の高さ及び幅が割り当てられると、システムは、次に、スペースの領域のアスペクト比及び面積を計算する。一般に、要素６０４において求められるルートノードのバウンディングボックスのアスペクト比は、ページのアスペクト比に等しくないであろう。
【００５２】
続いて、システムは、ノードを辿り、最終的にリーフに進む。ノードにおいて、システムは、ノードに割り振られたスペースをとり、そのスペースを重複しないサブセットに分割し、それからサブセットをノードの子に割り当てる。分割方法及び割り当て方法は、所望のレイアウトスタイルに応じて変更してもよい。要素６０５は、ブリックスタイルが採用されているかそれともストリクトエリアスタイルが採用されているかに関わりなく、図１５Ａに示すように動作する。図１５Ａから、要素１５０１は、各ノードについて、システムが、子ノードであれ、又はリーフであれ、その２つの子間にスペース領域を分割したことを示す。要素１５０２は、各リーフについて、システムが、リーフに割り当てられたスペースの領域に基づいてイメージのサイズ及び位置を決定することを述べている。図１５Ｂは、要素６０５において行われる変数のロードを含め、要素６０５において使用される変数を示す。システムは、まず、現在のノードを親に設定する。要素１５５１から、システムは特定の親「スペース領域」変数を定義し、ロードする。これら変数は、ルートノードが、評価されたノードである場合に満たされ、評価されたノードがルートノードではない場合には、これらの値は、以前に計算されている可能性がある。parent_rs_htは、親スペース領域の高さを表し、parent_rs_wdは、スペースの親領域の幅を表す。親スペース領域の左下もまた指定されるが、スペースの親領域の上部かつ／又は右等、他の測定を採用してもよい。システムは、親スペース領域の高さを親スペース領域の幅で割ったものを表す、親スペース領域のアスペクト比parent_rs_aを計算する。要素６０４から、システムは、要素１５５２において、親の左の子のバウンディングボックスの相対面積比率をleft_bb_eにロードし、親の左の子のバウンディングボックスのアスペクト比をleft_bb_aにロードし、これら値の右の子の相手方をロードする。システムは、また、要素１５５２において、親のバウンディングボックスのアスペクト比をparent_bb_aにロードする。最後に、要素１５５３が、左右の子の積及び比を計算する。判断要素１５５４において、システムは、垂直切断が望まれているか、それとも水平切断が望まれているかを判断する。垂直切断の場合には、システムは図１６のフローチャートに進み、水平切断の場合には、システムは図１７のフローチャートに進む。
【００５３】
図１６から分かるように、判断要素１６０１は、親スペース領域のアスペクト比parent_rs_aが、親のバウンディングボックスのアスペクト比parent_bb_aよりも大きいか否かを判断する。大きい場合には、動作は要素１６０２に進み、図示のように、左右のスペース領域の幅及び高さを計算する。要素１６０２から分かるように、動作は要素１６０４にわたり、左右の子のスペース領域の底部位置right_rs_bt及びleft_rs_btを計算する。動作は要素１６０５に進み、左右の子の間の間隙と、左右の子の左位置left_rs_lf及びright_rs_lfとを計算する。
【００５４】
判断要素１６０１において判断されるように、親スペース領域のアスペクト比parent_rs_aが、親のバウンディングボックスのアスペクト比未満の場合には、システムは、判断１６０３において、要素１５５３において計算された右の子の積が、要素１５５３において計算された左の子の積を上回るか否かを判断する。右の子の積right_prodが左の子の積left_prodを上回る場合には、動作は要素１６０６に進み、左右の子のスペース領域の高さright_rs_ht及びleft_rs_htを計算する。判断要素１６０３が、要素１５５３において計算された右の子の積が、要素１５５３において計算された左の子の積未満であると判断する場合には、システムは、要素１６０７において、左右の子のスペース領域の高さright_rs_ht及びleft_rs_htを計算する。従って、要素１６０７は、要素１６０６に示す計算とは異なる計算を使用して同じ変数を計算する。動作は要素１６０６又は要素１６０７から要素１６０８に進み、左右の子のスペース領域の幅left_rs_wd及びright_rs_wdを計算する。次に、動作は図示のように要素１６０４及び１６０５に進み、ページ上の左右の子の間隙のサイズ及び位置を計算する。
【００５５】
判断要素１５０４において、親切断方向が水平の場合には、動作は図１７、具体的には判断１７０１に進む。判断要素１７０１は、親スペース領域のアスペクト比parent_rs_aが親のバウンディングボックスparent_bb_aよりも大きいか否かを判断する。大きくない場合には、動作は要素１７０２に進み、図示のように左右のスペース領域の幅及び高さを計算する。動作は要素１７０２から要素１７０４に進み、左右の子のスペース領域の左側位置right_rs_lf及びleft_rs_lfを計算する。動作は要素１７０５に進み、左右の子の間の間隙と、左右の子の底部位置left_rs_bt及びright_rs_btを計算する。
【００５６】
判断要素１７０１において判断されるように、親スペース領域のアスペクト比parent_rs_aが、親のバウンディングボックスのアスペクト比よりも大きい場合には、システムは、判断１７０３において、要素１５５３において計算された右の子の比が、要素１５５３において計算された左の子の比を上回るか否かを判断する。右の子の比right_ratioが左の子の比left_ratioを上回る場合には、動作は要素１７０６に進み、左右の子のスペース領域の幅right_rs_wd及びleft_rs_wdを計算する。判断要素１７０３が、要素１５５３において計算される右の子の積が、要素１５５３において計算される左の子の積未満であると判断した場合には、システムは、要素１７０７において、左右の子のスペース領域の幅right_rs_wd及びleft_rs_wdを計算する。従って、要素１７０７は、要素１７０６に示す計算とは別の計算を使用して同じ変数を計算する。動作は要素１７０６又は要素１７０７から要素１７０８に進み、左右の子のスペース領域の高さleft_rs_ht及びright_rs_htを計算する。次に、動作は要素１７０４及び１７０５に進み、左右の子の左位置及び底部位置、並びに子の間の間隙を計算する。
【００５７】
この計算及び判断を行う要素６０５と異なる方法を採用してもよく、なお本設計の範囲内である。従って、システムは、リーフノードを通って進み、各リーフノードに割り当てられたイメージの位置及びサイズを決定する。システムは、特定のリーフノードに割り当てられたイメージのアスペクト比に等しいアスペクト比を有するスペース領域を全てのリーフノードに割り振る。システムは、利用可能なスペース領域内で可能な限り大きいイメージを配置することができる。別法として、システムは、イメージ間にスペースを提供し、それによって特定の状況でレイアウトの見た目を向上させる目的で、この可能な最大サイズよりも小さいイメージを配置してもよい。この代替の一例として、システムは、利用可能なスペース領域内で許容可能な、可能な最大高さ及び幅の０．９５に等しい高さ及び幅を有するように各イメージを指定することができる（隣接するイメージ間に白色スペースを位置付けるさらに他の方法を使用してもよい）。このようにして、要素６０５の動作が終わる。
【００５８】
最後に、図６に戻ると、複数のスコア付け関数の何れも、要素６０７に適正であることができる。イメージの相対面積比率が固定のストリクトエリアレイアウトモードでは、システムはイメージが占めるページの一部を使用することができる。このようにしてスコア付けすることで、ユーザ指定の相対面積比率を守りながら、同時にイメージを可能な限り大きくすることが可能になる。ブリックレイアウトモードでは、ユーザは相対イメージ面積比率を設定せず、相対イメージ面積比率は、レイアウトツリー構造及びイメージの特定のリーフノードへの割り当て等、全体構成によって決まる（dictated）。この場合、システムは、イメージが大きくなり、相対的に一貫した面積になることを促進させる、より複雑なスコア付け関数を採用することができる。従って、スコア付けは、所望の実施及び状況に応じて変更が可能である。
【００５９】
シングルパス動作
レイアウトプロセスを高速化するために、上記説明の図６のフローチャートから要求される処理なしで、ユーザ入力に基づいてレイアウトをシングルパスで組み立てるように、上記構成及び設計を変更することができる。
【００６０】
本設計は、ストリクトエリアスタイルを含め、何れのスタイルのレイアウトの生成にも使用することが可能であるが、ブリックスタイルレイアウトを本シングルパス設計で有利に採用することができる。
【００６１】
図１０は、本シングルパス設計によるフォトアルバム作成システムを示している。図１０によれば、ユーザは、イメージ，レイアウトスタイル，比率等のセットではなくイメージのセットを供給する。上記説明と同様に、システムは、ユーザコンピュータのフォルダ，デジタルカメラのメモリカード，オンライン写真共有ウェブサイト，又は他の同様のイメージソースを含め、様々なソースからイメージをとることができる。
【００６２】
ユーザは、改ページの位置をさらに指定する。しかし、ユーザが明示的に改ページを指定する必要はない。例えば、ユーザは、各ページが６枚以上のイメージを有さないと指定することができる。別法として、システムは、例えば４などの如き、ページ１枚あたりの最大イメージ数を提供してもよく、又はページ１枚あたり３〜７のランダムな数のイメージを設定する等、ランダム又は半分ランダムに改ページを設定してもよい。他の改ページ規定も提供することができる。
【００６３】
図１１は、シングルパス自動レイアウト設計を示している。システムは、指定されたイメージ１００１をとり、各イメージを１度に１枚ずつレイアウトに追加する。システムは、図５Ｂの右半分に示すバイナリツリー構造のようなバイナリツリー構造の形でレイアウトを書く。システムは、イメージをレイアウトツリー構造に挿入することにより各イメージをレイアウトに追加する。システムは、レイアウトツリー構造内の複数の位置の何れにイメージを挿入してもよい。本設計は、利用可能なツリー構造位置の全てにイメージを配置し、最高スコアを有するレイアウトをもたらす位置を選択する。最高スコアレイアウト位置の選択は、図１１Ｂの要素１１１０及び１１１４に表される。シングルパスフォトアルバム生成システム１０００の結果は、ｐｄｆ等のような特定のフォーマットのフォトアルバム出力である。
【００６４】
具体的には、図１１Ａから図１１Ｂに続き、要素１１０１が、第１のイメージを含む１つのリーフを有するレイアウトツリーＴを初期化する。要素１１０２がＴを正規化する。但し、この文脈中での正規化は、後述する図１４のフローチャートに従って動作する。要素１１０３は、Ｔをbest_Tスロットに移す。要素１１０４は、さらなるイメージが利用可能であるか否か、すなわちこれが唯一のイメージであるか否かを評価する。これが唯一のイメージである場合には、best_Tは要素１１０４において入力されたＴであり、動作は終わる。要素１１０４において、さらなるイメージが利用可能な場合には、要素１１０５が次のイメージを取得し、要素１１０６がツリーＴ中の最初の位置を評価する。本明細書では、「位置」という用語は、リーフ或いはノードの何れか一方として定義される。要素１１０７は、Ｔの増補コピーとしてＴ’を作成する。ここで、増補は、新しいノードをその位置の場所に追加することであり、新しいノードの一方の子が、Ｔの位置がルートであるツリー構造Ｔのサブツリーであり、新しいノードの他方の子がイメージである。ツリー構造Ｔ’において、水平切断等、所定の切断が新しいノードにおいて行われる。要素１１０８はＴ’を正規化する。判断１１０９は、その位置が最初の位置であるか否かを判断する。これが最初の位置である場合、Ｔ’は要素１１１１においてbest_Tにシフトされ、動作は要素１１１２に進む。これが最初の位置ではない場合には、要素１１１０は新たな様式のＴ’のスコア及びbest_Tのスコアを計算する。ここで、スコア付けは上述した様々な方法又は後述する方法で行うことができる。要素１１１０は、Ｔ’の結果生じたスコアがbest_Tの結果生じたスコアよりも大きい、すなわちツリーが、best_Tの結果生じたスコアよりも良好である（これは、向上したレイアウトを示す）か否かを評価する。Ｔ’のスコアがbest_Tのスコアよりも大きい場合には、Ｔ’はbest_T位置又はレジスタに移り、動作は要素１１１２に移る。Ｔ’のスコアがbest_Tのスコア未満の場合には、動作は要素１１１２に進む。
【００６５】
図１１Ｂから、要素１１１２は、要素１１０７の切断とは対照的な位置において、異なる所定の切断を有する、Ｔに新しいノードを追加したものをＴ’にシフトする。システムは要素１１１３においてＴ’を正規化し、再び要素１１１４において、Ｔ’のスコア及びbest_Tのスコアを求める。要素１１１４は、要素１１１０と同じ又は異なるスコア付け方法を使用してよく、ここでも、Ｔ’のスコアがbest_Tのスコアよりも大きい場合には、システムは変更されたツリー構造Ｔ’をbest_Tに移し、それから動作は要素１１１６に進む。要素１１１０が、Ｔ’のスコアがbest_Tのスコア未満であることを示す場合には、動作は要素１１１６に直接進む。要素１１１６は、Ｔにおいてさらなる位置（ロケーション）が利用可能か否かを判断する。さらなる位置がレイアウトツリー構造Ｔにおいて利用可能ではない場合には、動作は要素１１１８に進む。さらなるノードがレイアウトツリー構造Ｔにおいて利用可能な場合には、要素１１１７はレイアウトツリー構造Ｔ中の次のノードを評価し、動作は要素１１０７に進み、先に述べたように進む。さらなるノードがレイアウトツリー構造Ｔ中に利用可能でない場合、要素１１１８は、ページが処理に利用可能なそれ以上のイメージを有しているか否かを判断する。利用可能なイメージがそれ以上ない場合、要素１１１９においてbest_TがＴに移り、要素１１０５を使用して次のイメージが得られる。利用可能なイメージがそれ以上ない場合には、best_Tがイメージレイアウトに提供されるツリーである。
【００６６】
この設計によるイメージの順次挿入を図１２に示す。既存のレイアウトツリー構造への各イメージの挿入は以下のように動作する。Ｎ枚のイメージを有するツリーＴの場合、システムは、（Ｎ＋１）番目のイメージを追加しようと探索し得る。システムは、３つのステップでＴの特定の位置にイメージを挿入する。まず、システムはその位置をルートとするサブツリーを除去し、それを、水平向き或いは垂直向きの何れか一方を有する新しいノードで置き換える。図１３Ａは、４つの関連イメージを有するツリー１３０１及び新しいイメージ５を挿入したいという要望を示している。イメージ５のない既存のイメージレイアウトはレイアウト１３０２として示されている。図１３Ｂは、サブツリー１３０３を新しいノード１３０４で置き換えることを示している。次に、システムは、新しいイメージを新しいノードの子として配置することができる。図１３Ｂは、新しいノード１３０４の子として配置された新しいイメージ５を示している。最後に、システムは、新しいノードの他方の子として、元の位置をルートとするレイアウトツリー構造Ｔのサブツリーを配置する。図１３Ｂから、システムは、元のノードをルートとするレイアウトツリー構造Ｔのサブツリーの隣に新しいイメージであるイメージ５を位置付け、元のイメージ、ここではイメージ１及び４を新しいノード１３０４の子として位置付ける。これは、イメージ１及び４がサブツリー１３０３に含まれるためである。この３段階プロセスをさらに図１３Ｃに示す。図１３Ｃでは、システムは、新しいイメージを新しい「Ｖ」ノード１３０５に挿入する。
【００６７】
従って、動作に際し、システムは、図１３Ａに示すレイアウトにような元のレイアウトがページのアスペクト比に等しいアスペクト比を有するものと仮定する。レイアウト１３０６及び１３０７としてそれぞれページ上に示される、図１３Ｂ及び図１３Ｃの両方の試行レイアウトでは、システムは、ページの内側に適合するようにレイアウトをスケーリングする。２つの試行レイアウトは元のレイアウトと異なるアスペクト比を有し、レイアウト中のイメージは全て新しいイメージに対して調整される。システムは、既存のイメージのアスペクト比ではなくサイズを調整する。
【００６８】
レイアウトの正規化を図１４に示す。本質的に、正規化は、ブリックスタイルのような概して所望のスタイルに呼応する３つのレイアウト構造を作成し、上の図６の要素６０４及び６０５と実質的に同様である。図１４から、要素１４０１は、Ｔ中の各ノードについて、システムがそこをルートとするサブツリー中のイメージのバウンディングボックスを特徴付けることを述べている。要素１４０２は、Ｔ中の各ノードについて、バウンディングボックスに従ってページ上の物理的なスペースを割り当てるように動作する。従って、不規則な形状のイメージ、キャプション付きイメージ等を、視覚的に許容可能なフォーマットで一様に画定し配置することができる。要素１４０１及び１４０２の動作は、要素６０４及び６０５の動作と同様又は同一である。
【００６９】
システムがレイアウトを正規化すると、レイアウトは、要素１１１０、続けて要素１１４においてスコア付けられる。スコア付け関数は、レイアウトの視覚的な品質に対して大きな影響を有し得る。１つのスコア付け関数は、２つの項目、すなわち、アルファ（alpha）及び一貫性（consistency）を含む。アルファは、ページのアスペクト比がイメージのバウンディングボックスのアスペクト比とどの程度一致しているかを測定し、例えば、０〜１であり得る数値である。一貫性は、ページ上の最小の写真の面積を、ページ上の最大の写真の面積で割ったものとして計算することができる。両方の項目に関して、例えば、１．０の値は理想的であることを表し、例えば、０．０の値は最悪の利用可能なアルファ又は一貫性を表す。
【００７０】
スコア付け関数は、例えば（（１．５ラアルファ）＋一貫性）等のような初期スコアを計算することができる。他の初期スコアを計算してもよい。この初期スコアは、しきい値未満のアルファ及び／又は一貫性の値の場合にペナルティを課すことができ、システムは、上に指定したように異なるパラメータの結果生じるスコアを比較することができる。
【００７１】
上記説明は、ユーザに特定の入力を提供させることができるようにすると共に、複数のレイアウトを計算することなく視覚的に美しいレイアウトを作成することができるようにする。
【００７２】
本設計は、サイズが可変であり、おそらく固定のアスペクト比を維持することができるスケーラブルなアイテムを含め、特定種類のオブジェクト又はアイテムのフロアプラニング等、効率的な配置機能を実行する他のシステムにも適用することが可能であることが当業者に認識されよう。特に、本明細書に述べた機能及び関連する態様により、様々な種類の最適又は強化された配置機能に対処することが可能であることが認識されよう。
【００７３】
以上を要約すると、次の通りである。すなわち、本発明は、固定のアスペクト比を有するイメージのようなオブジェクトを、プリントされたページのような予め定められたスペース内に位置付けるための方法を提示する。本方法は、少なくとも１つのノード及び複数のリーフを含むバイナリツリー構造を生成する。各リーフは、イメージに対応しており、かつ、１つのノードに関連付けされる。本方法は、さらに、バイナリツリー構造中の各ノードのバウンディングボックスを特徴付けるステップを含んでおり、このバウンディングボックスは、ノードと関連する全てのリーフの境界を確立する。本方法は、また、ウンディングボックスを操作して予め定められたスペース内に適合させるステップを含む。本方法では、バイナリツリー構造内にイメージを再配置し、或いは、バイナリツリー構造を再形成し、再形成したバイナリツリー構造を用いて特徴付けステップ及び操作ステップを選択的に繰り返し行なってよい。最終的な結果として、予め定められたスペース内に全てのイメージを有する少なくとも１つの可能性のあるレイアウトが得られる。
【００７４】
上記に本発明を有利に使用することができる様式を説明することを目的として、用紙シート等の表面上への効率的なイメージの配置を実行する方法について述べたが、本発明はそれに限定されないことを認識されたい。従って、当業者が想起することができる変更，変形，又は同等の構成は何れも全て、添付の特許請求の範囲に規定される本発明の範囲内にあるものと考えるべきである。
【符号の説明】
【００７５】
３０１，３０２ ボックス
３０３ レイアウト
３０４ 第１のイメージ
３０５ 第２のイメージ
４００ 完全フォトアルバム作成システム
５００ ツリー
５０１〜５０６ リーフ
５０７〜５１１ ノード
５１２ ブランチ
１０００ シングルパスフォトアルバム生成システム
【技術分野】
【０００１】
本発明は、包括的には、要素の計算配置の分野に関し、特に、写真又はグラフィックイメージをページ上に効率的に配置又は位置付けることに関する。すなわち、本発明は、フォトアルバムの自動ページレイアウトに関する。
【背景技術】
【０００２】
現在、視覚的に美しいフォーマットでグラフィックイメージを収集して表示するコンピュータソフトウェアがユーザに提供されている。このようなコンピュータソフトウェアは、ユーザにより選択され、様々な様式で配置された一連のページを備えたフォトアルバムと呼ばれるものを作成する（develop）。本明細書では、フォトアルバムのページは、固定サイズのページに配置された複数のグラフィックイメージ又はピクチャを指す。本明細書では、グラフィックイメージ又はピクチャは、矩形の境界を有すると考えることができるような、テキストを含め、略あらゆるもののソフトウェア描写を指す。グラフィックファイルの例としては、.gif、.tiff、及び.jpegグラフィック表現が挙げられるが、境界を有する略何れのイメージも含むことができる。例えば、楕円形ブロックのテキストは、任意の境界を含む、楕円形ブロックの上下左右の側に接する矩形の境界を有するグラフィックイメージ又はピクチャとして考えることができる。
【０００３】
グラフィックイメージをフォトアルバムのページのどこに、どのように配置するかを判断するに際して、ソフトウェアは、環境に固有の様々な問題に対処しなければならない。例えば、ページ上のピクチャの枚数，互いに対するピクチャのサイズ，ピクチャの空間的分布，利用可能な空きスペース，及びキャプションの存在は全て、選択されたグラフィックイメージをフォトアルバムのページに配置する際に考慮される。
【０００４】
グラフィックイメージを配置する従来のソフトウェアシステムにおいては、配置は、往々にして「手で」行われる。このプロセスでは、ユーザは、ブランクページドキュメントを開き、デジタルグラフィックイメージをインポートしていた。ソフトウェアは、ユーザがイメージをページのあちこちに移動できるようにし、おそらくは美しいピクチャレイアウトを達成するようにサイズ変更を可能にすることにより、フォトアルバムのページ上に「レイアウト」生成した。手で写真の移動及びサイズ変更を行うプロセスは、面倒で時間のかかるものであり得る。これに応じて、開発者は、レイアウトプロセスを少なくとも一部自動化することを意図した自動ソフトウェアパッケージを作成した。
【０００５】
特定のソフトウェアパッケージは、イメージを行列に配置することによってレイアウトプロセスを自動化している。イメージが、全て同じサイズ及び形状の別個の領域に強制的に入るようにすることから、この種類のソフトウェアパッケージを使用して作成されるレイアウトはイメージのアスペクト比を考慮せず、グラフィックイメージがレイアウトで配置されたときに歪んで見える場合がある。この種類の方策では、ページ上に未使用の空スペースが生じる場合があり、これは視覚的に魅力がなく、利用可能なスペースを無駄にしている。
【０００６】
他のソフトウェアパッケージによっては、イメージが固定のテンプレート開口部、又は「ホール」に手動で挿入されるテンプレートを提供するものがある。テンプレートは魅力的であり、スペースを効率的に使用することができるが、利用可能なテンプレートは、テンプレートホールのアスペクト比がイメージのアスペクト比と相関しないために使用することができない場合が多い。イメージは、特定のテンプレートホール内で受け入れられる外観及びアスペクト比を提供するようにクロッピングすることができるが、クロッピングは、一般に、イメージの一部を破棄する必要があるため満足の得られるものではない。また、イメージは、テンプレートホールを通して完全に、かつクロッピングなしで現れるように縮小することができるが、このようなサイズの縮小は、イメージが小さく見え、従って見にくくなるため満足の得られるものではない場合がある。ソフトウェアパッケージによっては、ユーザが新しいテンプレートを作成できるものもあるが、テンプレート作成プロセスは、通常、手動でのレイアウトに等しいため、面倒で時間がかかる。
【０００７】
特定の、一般に利用可能なソフトウェアパッケージは、特定のレイアウト設計上の問題を有する。Ｋｏｄａｋ Ｍｅｍｏｒｙ Ａｌｂｕｍｓ（「ＫＭＡ」）は、テンプレートを使用することなくアルバムページレイアウトを自動的に生成するように見える傾向を示す。しかし、ＫＭＡは、単純に付近のイメージを拡大することによって埋めることができるであろう空きスペースを残す。また、ユーザが生成されたレイアウトを好まない場合には、ユーザに提供される代替のレイアウトは１つか２つのみである。４つ未満のレイアウトの世界は、一般に、あまりに限定的である。
【０００８】
Ｃａｎｏｎ ＰｈｏｔｏＲｅｃｏｒｄ Ｇｏｌｄ（「ＣＰＧ」）は、自動フォトアルバムページレイアウトを提供する別のソフトウェアパッケージである。一モードにおいては、ＣＰＧは、所望の数のイメージを収容するテンプレートを作成する方法を採用するように見える。しかし、このモードでは、イメージサイズが無視されて見え、これはイメージの重複をもたらす可能性がある。イメージの重複は不規則であると共に、多くの場合は過大であるため、一般に魅力的でない。別法として、ＣＰＧユーザは、ページ上で１枚のイメージを移動することができ、その間に、ソフトウェアはその他のイメージをページのあちこちにシフトして、移動中のイメージに適応する。イメージ位置シフトの制御は、でたらめに見え、場合によってはイメージが完全に隠れてしまうことになる。
【０００９】
ＬｕｍａＰｉｘからのＦｏｔｏＦｕｓｉｏｎ（「ＦＦ」）と呼ばれる別の製品は、写真の単一ページコラージュを生成する。ＦＦは、入力イメージのリストをとり、全てのイメージの単一ページレイアウトを生成し、様々な代替のレイアウトを生成する能力を提供するオートコラージュ（autocollage）機能を有する。オートコラージュ機能によって生成されるレイアウトでは、写真の間に白色スペースはほとんどないか、又は全く存在せず、写真は、壁の中のレンガのように一緒にはまる。しかし、レイアウト中の写真はクロッピングされ、写真の一部は破棄され、これは満足のいくものではない。
【００１０】
現在利用可能な何れのソフトウェア設計でも、ユーザは、提示されたイメージ全体を保持しながら、それと同時に複数のイメージの相対的なイメージサイズを指定することができない。相対的なイメージサイズの指定は、例えば、ユーザが１枚のイメージをページ上のその他の全てのイメージよりも可成り大きくしたい場合に望ましいであろう。さらに、現在利用可能なソフトウェア設計は、提示されたイメージ全体を保持しながら、それと同時に、ページ上のイメージが占める矩形領域内の空の未使用スペースを完全にはなくしていない。この矩形領域は、イメージによって仕切られる「凸閉包」（convex hull）として説明することができる。
【００１１】
特定のフロアプランニング又はレイアウトツリー構造が異なるコンテキストの中で採用されてきている。例えば、レイアウトツリー構造をＶＬＳＩ回路レイアウトに使用する者もいれば、一般のドキュメントレイアウトに使用する者もいる。しかし、ＶＬＳＩ回路レイアウトでは、回路はサイズ固定であることができるが、通常、固定のアスペクト比を有さない。従って、回路は、ｘとｙの比率保持を顧慮することなく、ｘ次元及びｙ次元において独立して変更することが可能である。フロアプランニングソリューションは、往々にしてイメージ配置設計に関連するアスペクト比保持要件により、イメージ配置設計とは大幅に異なる傾向がある。一般のドキュメントレイアウトでは、イメージレイアウトとは対照的に、アスペクト比もまた変数として考えられる。
【発明の概要】
【発明が解決しようとする課題】
【００１２】
従って、最小量の空スペース及び最大のレイアウト設計多様性を有し、それと同時に、受け取ったイメージのクロッピングを控え、従来のグラフィック配置ソフトウェアに関連する欠点を最小化した、グラフィックイメージをページに効率的に配置するソフトウェアソリューションを提供することが望ましい。
【課題を解決するための手段】
【００１３】
本発明の第１の態様によれば、物理的ページを表すスペース内のオブジェクトのレイアウトを組み立てることによってオブジェクトを位置付ける方法が提供される。本方法は、少なくとも１つのノード（node）、及び、各々が１つのオブジェクトに対応する少なくとも１つのリーフ（leaf）を有するツリー構造を生成するステップと、前記ツリー構造中の各ノードのバウンディングボックスであって、各々が前記ノードの下位にあるサブツリー中の何れのオブジェクトも全て含むバウンディングボックスを特徴付けるステップと、前記ノードに関連する前記バウンディングボックスに従って、前記スペース内の領域を前記ツリー構造中の各ノードに割り当てるステップとを含む。
【００１４】
本発明の第２の態様によれば、固定アスペクト比オブジェクトを予め定められたスペースに割り当てる方法が提供される。本方法は、１つのオブジェクトにそれぞれ対応する複数のリーフ及び少なくとも１つのノードを有するバイナリツリー構造（２分木構造）を生成するステップを含む。この場合、各ノードは、そこから分岐する全てのノード及びリーフに関連し、そこから分岐する全てのノード及びリーフを代表するものである。本方法は、バイナリツリー構造中の各ノードに適宜サイズのバウンディングボックスであって、そこから分岐する全てのノード及びリーフの境界を画定する各ノードのバウンディングボックスを画定するステップと、予め定められたスペース内にはまるように少なくとも１つの適宜サイズバウンディングボックスを操作することにより、前記予め定められたスペースにオブジェクトを位置付けるステップとをさらに含む。
【００１５】
本発明の第３の態様によれば、イメージに関連するアスペクト比を保持しながら予め定められたスペースに前記イメージを位置付ける方法が提供される。本方法は、少なくとも１つのノード、及び、各々が１枚のイメージに対応すると共に１つのノードに関連する複数のリーフを有するバイナリツリー構造を生成するステップと、前記バイナリツリー構造中の各ノードのバウンディングボックスであって、前記ノードに関連する全てのリーフの境界を確立するバウンディングボックスを特徴付けるステップと、バウンディングボックスを操作して、前記予め定められたスペースに適合させるステップとを含む。
【００１６】
本発明の全ての態様のこれら及び他の目的及び利点は、添付図面に示した好ましい実施形態の以下の詳細な開示を読んだ後に、当業者に明らかになろう。
【００１７】
本発明は、限定ではなく例として添付図面の図に示されている。
【図面の簡単な説明】
【００１８】
【図１】プリントされたページ等のような予め定められたスペースにおけるストリクトエリアレイアウトの概念を示す図である。
【図２】オブジェクト又はイメージのブリックスタイルレイアウトを示す図である。
【図３】アスペクト比及び相対面積比率の概念を示す図である。
【図４】入力及び出力を示す完全フォトアルバム作成システムの一実施形態を概略的かつ全体的に説明するフローチャートである。
【図５Ａ】ページ等のような予め定められたエリアを下位エリアに順次分割することを示す図である。
【図５Ｂ】分割された、予め定められたエリア及びそれに対応するバイナリツリー構造を示す図である。
【図６】完全フォトアルバム作成システムの一実施形態の詳細なフローチャートである。
【図７】バウンディングボックスの形成を示すフローチャートであって、図６の要素６０４と等価なフローチャートである。
【図８】図７のブロック７０１を表すフローチャートである。
【図９】図７のブロック７０２を表すフローチャートである。
【図１０】入力及び出力を含む、シングルパス設計によるフォトアルバム作成システムの一実施形態を広く概念的に説明するフローチャートである。
【図１１Ａ】シングルパス設計によるフォトアルバム作成システムの一実施形態を詳細に説明するフローチャートの第１部分である。
【図１１Ｂ】シングルパス設計によるフォトアルバム作成システムの一実施形態を詳細に説明するフローチャートの第２部分である。
【図１２】シングルパス設計によるイメージ又はオブジェクトの順次ロード（順次挿入）を示す図である。
【図１３Ａ】４つの関連イメージ及び新しいイメージ５を挿入する要望を有するツリーを示す図である。
【図１３Ｂ】新しいイメージ５を新しい水平分割ノードの下に位置付けすること、及び元のイメージ１及び４を新しい水平分割ノードの子として位置付けすることを示す図である。
【図１３Ｃ】新しいイメージ５を新しい垂直分割ノードの下に位置付けすること、及び元のイメージ１及び４を新しい垂直分割ノードの子として位置付けすることを示す図である。
【図１４】シングルパス設計による正規化プロセスのフローチャートである。
【図１５Ａ】図６の要素６０５の動作を表す図である。
【図１５Ｂ】採用される変数、並びに、図１５Ａ，図１６，及び図１７によって表されるように、要素６０５の実行に際しての使用に利用可能な値のプレロードを示す図である。
【図１６】所望の親の切断方向が垂直である場合の要素６０５の動作を示す図である。
【図１７】所望の親の切断方向が水平である場合の要素６０５の動作のフローチャートである。
【発明を実施するための形態】
【００１９】
本発明による設計は、２つの機能、すなわちユーザが選択可能であり、大部分をユーザ入力に頼る、多種多様なイメージレイアウトを作成するフル機能（full function）、及び計算集約度がフル機能よりも低いが、ユーザからのより少ない入力に基づいて視覚的に魅力的なレイアウトをより短い時間期間で生成する「シングルパス」機能（「single pass」function）を含む。
【００２０】
フル機能及びシングルパス機能の両方に関して、２つの特定のレイアウト動作モード、すなわち、「ストリクトエリア」（strict area）レイアウト及び「ブリック」（brick）レイアウトが考えられる。
【００２１】
図１は、ストリクトエリアレイアウト動作モードを示している。ストリクトエリアは、一般に、ページの特定のエリア又は下位エリア内に厳格に位置付けられたイメージを指す。概念上、ページは、ページの左半分及び右半分等、複数の下位エリアに分割することができ、ストリクトエリアレイアウトモードは、１枚のイメージをページの右半分でセンタリングし、別のイメージをページの左半分でセンタリングすることができる。ストリクトエリアレイアウト動作モードを使用する場合には、ユーザは、ページをエリアに分割する目的で使用される相対面積比率値を各イメージに提供することができる。相対面積比率値の使用により、ユーザは、１枚のイメージを、同ページ上の第２のイメージのエリアの１／３、かつ第３のイメージのエリアの１／４になるように指定することが可能になり、エリアはこの選好に従って分割され、イメージはそのように分割された各エリアにおいてセンタリングされる。相対面積比率は数値であり、上記例では、３枚全てのイメージが元々は同じ面積のものである場合、第１の相対面積比率は１．０であり、第２は３．０であり、第３は４．０である。相対面積比率は、後述する主題であるアスペクト比の概念とは無関係である。
【００２２】
数学的には、ストリクトエリア動作モードは、所与のページにおいて、イメージのエリアが、
Ａ1／ｅ1＝Ａ2／ｅ2＝∧＝ＡN／ｅN
を満たすことを示す。式中、Ｎはページ上のイメージ数であり、｛Ａi｝は実際のイメージエリアであり、｛ｅi｝はユーザ指定の相対イメージ面積比率である。ストリクトエリアレイアウトは、相対的なイメージエリアの比率を制御する。ユーザが、イメージＡをイメージＢのサイズの３倍にすると指定する場合には、ストリクトエリアレイアウトモードは、ページ上のイメージＡ及びイメージＢの正確な位置又はサイズに関わりなく、イメージＡがイメージＢのサイズの３倍になるように指示する。ストリクトエリアレイアウトは、また、ユーザがよりくだけた方法で面積制約を指定する場合にも採用することができる。例えば、ユーザは、選択された特定のイメージが同ページ上のその他のイメージよりも大きくなるべき（すなわち、厳密な乗算係数だけ大きくなるのではない）旨を指定することができる。
【００２３】
図２は、代替の「ブリックレイアウト」動作モードを示している。図２では、イメージの間に白色スペースが存在せず、イメージは壁の中のレンガのように一緒にはまっている。ブリックスタイルレイアウトは、空スペースがページ上の写真又はイメージによって仕切られた「凸閉包」に存在しないために視覚的に効率的に見える。
【００２４】
図１及び図２の両方の例はイメージのみを含んだページを示すが、本設計では、レイアウトスタイルに関わりなく、ユーザはキャプションをプリントしたり、又は各イメージの下にブロックを挿入したりすることも可能である。ユーザは、何れのレイアウトスタイルでも、空スペースの「溝幅」を指定して、イメージを分離することも可能である。
【００２５】
図３は、本設計のアスペクト比，エリア，及び相対面積比率の概念を示している。アスペクト比は、イメージの高さをイメージの幅で割った比として定義される。ボックス３０１はアスペクト比２．０を有し、ボックス３０２はアスペクト比０．５（１対２）を有する。システムは、動作全体を通してアスペクト比を保持しようと努める。各イメージは、ページ上のエリアを占める。本明細書では、「エリア」は、例えば、平方インチ単位で測定することが可能な、レンダリングイメージの固定属性である。（８．５インチ）ラ（１１．０インチ）の用紙を仮定すると、ページエリアは、９３．５平方インチである。そのページにプリントされる、高さ４．０インチ及び幅６．０インチの写真は、２４．０平方インチのエリアを有する。本明細書では、「相対面積比率」は、同じページ上の２枚のイメージのエリアを比較する際に使用されるイメージ属性である。ここで、「相対面積比率」及び「エリア」は関連するが異なる概念であり、前者は純粋に相対的な性質のものであり、後者は絶対的かつ測定可能なものである。レイアウト３０３は、相対面積比率１．０を有する第１のイメージ３０４及び相対面積比率４．０を有する第２のイメージ３０５を具備したページを示す。相対面積比率は、係数「４」だけ異なるため、それぞれの測定可能エリアの特定の数値に関わりなく、レンダリングされる出力（例えば、プリントされたページ上，物理的空間表現上，又はコンピュータディスプレイ上）における２枚のイメージの測定可能なエリアもそうである。
【００２６】
図４は、完全フォトアルバム作成システム４００のフローチャートを示している。フォトアルバム作成システム４００への入力は、アルバムに含めるべきイメージのリスト４０１であり、ここでリスト４０１は、img0.jpg，img1.jpg，及びimg2.jpgをページ１上に含み、その後にページ２上のimg3.jpg及びimg4.jpgが続く。ユーザの望みに応じて他のリストを提供することもできる。このようなリストは、各改ページの位置を示すことができる。別法として、本設計は、タイムスタンプ又は他の利用可能なコンピュータ情報を用いて改ページを判断することができる。例えば、数枚のイメージが互いに数秒間に取り込まれ、その後に休止があり、その後により多数のイメージが続いていた場合には、時間的にはっきりと分けられた２つのグループの間に改ページを位置付けることができる。フォトアルバム作成システム４００からの出力は、例えば、pdf，jpg，又は通常はグラフィック的性質の他の利用可能なフォーマットのページの集まり等のフォトアルバム出力である。
【００２７】
一般に、本設計の焦点は、システムが大まかにグラフィックイメージをツリー構造中のリーフノードに割り当てる比較的雑なレイアウト構成から、ユーザ指定のレイアウト動作モードに一貫した厳密なレイアウト構成への進展である。
【００２８】
本明細書にて使用する用語の定義を目的として、「ツリー」は、ツリーの構成要素が利用可能なページの特徴に対応する、図５Ｂの右側に示すもの等の構造である。そこから出るブランチ（分岐）を有するツリー中のポイントは、「ノード」と呼ばれ、そこから出るブランチを有さないツリー中のポイントは「リーフ」と呼ばれる。ページは、図５Ａに示す様式等、順次分割することができる。各分割は、ツリー中の１つのノードに対応する。図５Ｂの左の表現は、元のページから作成された５つの区分を表す、６つの下位エリアに分割されたページを示す。図５Ｂの右の表現は、６つの終点、すなわちリーフ５０１，５０２，５０３，５０４，５０５，及び５０６と、５つのノード５０７，５０８，５０９，５１０，及び５１１とを有するツリーである。従って、ツリー５００等のような、本設計において使用されるツリーは、リーフ５０１等の複数のリーフ，ブランチ５１２等の複数のブランチ，及びノード５０７等の複数のノードを含む。本設計は、ユーザの望み及び提示されるイメージに応じて異なるツリー構造を構築し、その結果として生じる各ツリー構造がレイアウトを形成し、複数のツリー構造及びレイアウトを用意することができる。
【００２９】
図６は、本設計の詳細なフローチャートを示している。設計システムへの入力は、ユーザがページ上に表すことを意図するイメージのリスト６０１であり、出力６１１は、イメージリスト６０１中の各イメージの位置及びサイズを示したレイアウト仕様best_Tである。基本的な動作では、システムが、複数の候補レイアウトを、各候補レイアウトのスコアと共に生成し、次に、最高スコアを有する候補レイアウトを出力６１１を介して出力することを含む。
【００３０】
好ましい動作モードは、出力best_Tが、全ての候補レイアウトの中で最高スコアを有する１つの最良のレイアウトを提供することである。しかし、ユーザが複数の代替のレイアウトを調べることを所望するシナリオでは、出力best_Tは、複数のレイアウトを表し得る。例えば、５つのレイアウトツリー構造が、ユーザがその５つの中から選択できるように望まれる場合がある。複数の代替のレイアウトシナリオでは、best_Tは、計算された他の何れのレイアウトよりも高いレイアウトスコアを有する複数の候補レイアウトを表すことができる。
【００３１】
要素６０２は、Ｎ個のリーフノードを有するレイアウトツリー構造Ｔを生成し、要素６０３は、そのようにして生成されたツリー構造を採用し、各イメージをレイアウトツリー構造Ｔ中のリーフに割り当てる。システムは、リーフ，ブランチ，及びノードをランダムに割り当てることができ、ユーザが最終的に別の設計を採用すると決定し、従って前のツリーを再訪したい場合には、試みられた初期のツリーを呼び戻すことができる。要素６０３は、そのようにして作成されたツリー中のリーフにイメージをランダムに割り当てることができる。これはランダムに行うことができ、代替のレイアウトが望まれる場合の選択肢が保持される。図５Ｂを例として採ると、６枚のイメージを受け取ることができ、（５つのノード）−（６つのリーフ）のツリーが採用される。別法として、２つの底にあるリーフ、すなわちリーフ５０２及び５０３をリーフ５０１，５０４，５０５，又は５０６の下に位置付けして、これらリーフをノードにし、ノード５１１をリーフにすることもできる。
【００３２】
要素６０２は、レイアウトツリー構造を生成する異なる方法で実施してもよい。要素６０２に必要な入力はＮ枚のイメージである。レイアウトツリー構造を生成する一方法では、Ｎ枚のリーフ及び（Ｎ−１）個のノードを有するバイナリツリー構造を生成し、その後に、各ノードに切断方向を割り当てるステップを含む。ツリー構造（すなわち、ノードとリーフの網状組織）の形状及びノードに割り当てられる切断方向は両方ともランダムであってよい。本設計の本態様では、システムは、ツリー構造を決定論的に生成し、切断方向がランダムに割り当てられ、コインを実際にはじき、表の場合はＨＯＲＩＺ（水平切断）を割り当て、裏の場合はＶＥＲＴＩＣ（垂直切断）を割り当てる。要素６０３の本実施は、イメージとツリーのリーフとの間にランダムな１対１のマッピングを生成することである。従って、要素６０２及び６０３は、候補レイアウトに一般的な枠組みを提供する。
【００３３】
次に、要素６０４が、ツリー構造Ｔ中の各ノードのサブツリー中のイメージのバウンディングボックスを特徴付ける。本明細書では、ノードの「サブツリー」は、ノード自体と共に、リーフの方向、すなわち本明細書の図面に示すツリーの概して下方向にそのノードから出る全てのブランチ，ノード，及びリーフを持つノード自身として定義される。バウンディングボックスは、イメージ、並びに、任意の関連するキャプション又は他の材料に境界を付けるスペースの領域である。要素６０５において、システムは、ツリー構造Ｔ中の各ノードのバウンディングボックスに従ってページ上の物理的なスペースを割り当てる。要素６０５からの結果は、選択されたレイアウト動作モード、又は所望のレイアウトスタイル（例えば、ストリクトエリアレイアウト又はブリックレイアウト）に呼応して指定される候補レイアウトである。要素６０４及び６０５についてさらに詳細に後述する。
【００３４】
判断要素６０６は、候補レイアウトが最初に形成された候補レイアウトであるか否かを判断し、そうである場合には、要素６０８はツリー構造Ｔを最良ツリー（ｂｅｓｔ＿Ｔ）レジスタ又は記憶位置に移す。判断要素６０６の結果が、候補レイアウトが最初に形成された候補レイアウトではなかったというものである場合には、判断要素６０７がツリー構造Ｔのスコアとbest_Tのスコアを計算する。ツリー構造Ｔのスコアがbest_Tのスコアよりも大きい場合には、ステップ６０８はＴをｂｅｓｔ＿Ｔ位置又はレジスタに移し、制御は次に判断要素６０９に移る。一方、判断要素６０７の結果が、ツリー構造Ｔのスコアがbest_Tのスコア未満であるというものである場合には、制御は判断要素６０９に移る。
【００３５】
スコアは様々な方法で計算することができる。スコアを計算する一方法は、ページ上の空スペースを査定し、ブランクスペースが最も少ないレイアウトを最良レイアウトとするものである。このスコア付けはストリクトエリアレイアウトに使用することができる。その理由は、ストリクトエリアレイアウトの場合には、相対面積比率が既に固定されていることによる。スコアを計算する別の方法は、イメージが最も一様なイメージを探すというものであり、これは、ページ上の最小イメージ面積をページ上の最大イメージ面積で割った比を求め、最も大きな結果を選択することによって達成される。ブリックスタイルレイアウトのスコア付けの場合には、スコア付けは、空スペースも、またイメージエリア一様性も、一方の最適化を犠牲にして他方が過度に悪化しないように、空スペースとイメージエリア一様性の組み合わせを求めることによって行うことができる。
【００３６】
判断要素６０９は、所望数のイメージ−リーフ割り当てが特定のツリー構造Ｔに関して考慮されたか否かを判断する。この所望数は、ユーザ、又はリモート自動プログラム等、他の制御エンティティによって決定することができる。一般に、イメージ−リーフ割り当てに大きな数が指定されるほど、より良好なレイアウトを見つけるチャンスが増える。所望数は、特定のページに対する所望のイメージ数に大きく依存する。イメージ数が少ない場合（例えば、２、３枚のイメージ）、所望数を低く設定してよい。イメージ数が多い場合には、所望数は高く、例えば１００以上であってよい。フローチャートに関して、判断６０９の結果が否定の場合には、制御は要素６０３に戻り、システムが新しいイメージ−リーフ割り当てを生成し、結果として新しいレイアウト構成が生成される。判断要素６０９の結果が肯定の場合には、制御は判断要素６１０に渡る。
【００３７】
判断要素６１０において、システムは、所望数のレイアウトツリー構造が考慮されたか否かを判断する。この場合、所望数は、ユーザ又は他の制御エンティティによって決定することができる。レイアウトツリー構造は、結果生じるレイアウトに大きく影響する。従って、レイアウトツリー構造の数が多いほど、ユーザがより良好なレイアウトを見つけるチャンスが増える。判断要素６１０の結果が肯定の場合には、その結果としてbest_Tが出力６１１に生じる。否定の場合には、システムは、Ｎ枚のリーフノードを有する新しいレイアウトツリー構造Ｔを生成することによって要素６０２を繰り返す。
【００３８】
要素６０４において、レイアウトツリー構造中の各ノード及びリーフについて、システムは、そこをルートとしたサブツリー中のイメージを包含するバウンディングボックスを特徴付ける。システムは、「ａ」で示されるアスペクト比、及び、「ｅ」で示される相対面積比率を計算する。これらパラメータから、システムは、バウンディングボックスを特徴付ける、すなわち規定（定義）する。例えば、アスペクト比４：３は、「ａ」；１．３３３３として特徴付けることができ、相対面積比率は、第１のイメージには「ｅ」；１．０、第２のイメージには、例えば「ｅ」；２．５であってもよく、これは、第２のイメージが第１のイメージよりも２．５倍大きいことが望ましいことを示す。従って、「ａ」；１．３３３３及び「ｅ」；２．５は、操作可能かつ配置可能なバウンディングボックスを規定する。
【００３９】
何れのノードへのバウンディングボックスの特徴付けでも、その２つの子（child）のバウンディングボックスの先験的な特徴付けが必要であり、これについては後述する。この先験的なバウンディングボックスの特徴付け要件により、図６中の要素６０４は、或る意味、一番下のリーフノードからツリーのノードを通して最上部、すなわちルートまでツリーを徐々に上がっていくように動作する。
【００４０】
リーフの場合、要素６０４におけるバウンディングボックスの特徴付けは、アスペクト比が、リーフに割り当てられた写真のアスペクト比に等しいという点で単純である。ストリクトエリアスタイルレイアウトの場合には、ユーザは、相対面積比率を提供し得る。別法として、システムは、リーフの相対面積比率をランダムに、又は動的に決定することができる。ブリックスタイルレイアウトの場合には、相対面積比率の初期数値は重要ではなく、ユーザ又はシステムが任意の正の値を割り当てることができる。
【００４１】
ノードの場合、システムは、図７のフローチャートに従ってバウンディングボックスを形成する。入力は、通常、ストリクトエリアスタイル指示であるか、或いはブリックスタイル指示であるかがユーザによって指定される。ブロック７０１は、システムがブリックスタイル指示を提供する場合に実行され、システムは、所望の切断種類に応じて、ノードの１つの子及びその子の全ての子の相対面積比率を調整する。現在のノードが水平切断を有する場合には、調整は、２つの子のバウンディングボックスの幅が等しくなるように行われる。現在のノードが垂直切断を有する場合には、調整は、２つの子のバウンディングボックスの高さが等しくなるように行われる。ストリクトエリアスタイル及びブリックスタイルの両方で行われるブロック７０２において、システムは、現在のノードの２つの子の相対面積比率及びアスペクト比の関数として、現在のノードの相対面積比率及びアスペクト比を計算する。
【００４２】
動作の際には、現在のノードが垂直切断を提供する場合、ブロック７０１は、右の子のサブツリー中のイメージを含む矩形が、左の子のサブツリー中のイメージを含む矩形と同じ高さを有するように右の子を調整する。同様に、現在のノードが水平切断を提供する場合、ブロック７０１は、左の子と同じ幅を有するように右の子を調整する。
【００４３】
動作の際に、左の子を調整するのとは対照的に右の子を調整するという判断は、中立である、すなわち「どちらでも構わない」。すなわち、別法として、ブロック７０１は、左の子及び左の子の全ての子を、右の子と同じ高さ又は幅を有するように調整してもよい。システムは、この時点では、変更が可能な相対面積比率を設定しているため、何れの方法を実施してもよい。
【００４４】
具体的には、ブロック７０１において、システムは、右の子及び右の子の全ての子の相対面積比率を以下の係数で乗算する。
【００４５】
【数１】
【００４６】
上記の式において、ｅ1及びａ1はそれぞれ現在のノードの左の子の相対面積比率及びアスペクト比であり、ｅr及びａrはそれぞれ右の子の相対面積比率及びアスペクト比である。
【００４７】
図８は、図７のブロック７０１を表すフローチャートを示しており、図９は、図７のブロック７０２のフローチャートを示している。図８から分かるように、要素８０１は、左右の子の相対面積比率及びアスペクト比を得る。判断８０２における水平切断（本例）が望まれているか否かに応じて、システムは、要素８０３又は８０４に従って係数を計算する。係数が計算されると、要素８０５において、システムは、そうして計算された係数で、右の子及びその右の子の全ての子の相対面積比率を乗算する。図９から分かるように、ここでも、要素９０１は左右の子の相対面積比率及びアスペクト比を得る。ここでも、本例では、システムは、これが水平切断であるか否かについて（判断は別法として、これが垂直切断であるか否かであってもよい）の判断９０２を行う。今の切断が水平である場合には、システムは、判断９０３において、右の子の相対面積比率を右の子のアスペクト比で割ったものが、左の子の相対面積比率を左の子のアスペクト比で割ったものを上回るか否かを判断する。上回る場合には、現在のノードのアスペクト比及び相対面積比率は、要素９０５において計算されるものである。その他の場合には、要素９０４において計算されるものである。今の切断が水平ではない場合には、システムは判断９０６において、右の子の相対面積比率を右の子のアスペクト比で乗算したものが、左の子の相対面積比率を左の子のアスペクト比で乗算したものを上回るか否かを判断する。上回る場合には、現在のノードのアスペクト比及び相対面積比率は、要素９０８において計算されるものである。その他の場合には、要素９０７において計算されるものである。従って、その結果は現在のノードのアスペクト比及び相対面積比率である。
【００４８】
単純な例は、次の通りである。ストリクトエリアスタイルレイアウトの場合には、ユーザが、２枚のイメージＡ及びＢに対して、イメージＡにはｅ1；１．０及びａ1；４．０を指定し、イメージＢにはｅr；２．０及びａr；２．０を指定したとする。従って、子としてイメージＡ及びイメージＢを有するノードの場合には、図９から分かるように、水平切断が望まれていると、判断要素９０３は、２．０／２．０が１．０／４．０よりも大きいか否かを計算する。この場合、１．０は０．２５よりも大きい。従って、ａは（２．０＋２．０）／１．０すなわち４．０に等しく、ｅは（２．０＋２．０）ラ１．０すなわち４．０に等しい。従って、イメージＡ及びＢを含むノードは、アスペクト比；４．０及び相対面積比率；４．０によって画定されるバウンディングボックスを有する。
【００４９】
従って、要素６０５から、システムは、ページ上のスペースの矩形領域を、ノードをルートとするサブツリー中に含まれるレイアウトツリー構造中の各ノードに関連するイメージを割り振る。スペースの矩形領域は、領域の高さ及び幅を指すのみならず、ページの境界に対する領域の絶対位置も指す。スペースをルートノードではない何れのノードにも割り振る際には、システムは、そのノードの親にスペースを既に割り振っていることを考慮する。従って、概念上、要素６０５は、ルートノードから始まってリーフノードで終わる、ツリー構造の「上から下への」作業をすることによって動作する。ステップ６０５において割り振られたスペースの領域は、ステップ６０４において決定されたバウンディングボックスとは異なる。主な違いは、スペースの領域が、平方インチ又は平方ミリメートル等距離単位で測定可能な、レンダリングされた出力ページの実際の物理的なエリアを反映している一方で、バウンディングボックスは、占めるエリアの相対的表記を使用して表現されることである。
【００５０】
動作に際し、要素６０５は、システムに、まず、ページ全体のスペースの領域をルートノードに割り当てさせる。この「ページ全体」は、物理的なページの面全体、又は物理的なページの使用可能な部分のみを表すことができる。例えば、ページ全体は、余白，ヘッダ，及びフッタに予め向けられているスペースを含まない。従って、システムは、スペースの領域の高さ及び幅をルートノードに割り当て、さらに、スペースの領域の左下位置を示す空間位置座標をさらに割り当てる。スペースの領域の中心、又はスペースの領域の右上角等、他の空間位置座標を使用してもよい。スペースの領域は、領域の概念的表現にさらに割り当てることができる。
【００５１】
スペースの領域の高さ及び幅が割り当てられると、システムは、次に、スペースの領域のアスペクト比及び面積を計算する。一般に、要素６０４において求められるルートノードのバウンディングボックスのアスペクト比は、ページのアスペクト比に等しくないであろう。
【００５２】
続いて、システムは、ノードを辿り、最終的にリーフに進む。ノードにおいて、システムは、ノードに割り振られたスペースをとり、そのスペースを重複しないサブセットに分割し、それからサブセットをノードの子に割り当てる。分割方法及び割り当て方法は、所望のレイアウトスタイルに応じて変更してもよい。要素６０５は、ブリックスタイルが採用されているかそれともストリクトエリアスタイルが採用されているかに関わりなく、図１５Ａに示すように動作する。図１５Ａから、要素１５０１は、各ノードについて、システムが、子ノードであれ、又はリーフであれ、その２つの子間にスペース領域を分割したことを示す。要素１５０２は、各リーフについて、システムが、リーフに割り当てられたスペースの領域に基づいてイメージのサイズ及び位置を決定することを述べている。図１５Ｂは、要素６０５において行われる変数のロードを含め、要素６０５において使用される変数を示す。システムは、まず、現在のノードを親に設定する。要素１５５１から、システムは特定の親「スペース領域」変数を定義し、ロードする。これら変数は、ルートノードが、評価されたノードである場合に満たされ、評価されたノードがルートノードではない場合には、これらの値は、以前に計算されている可能性がある。parent_rs_htは、親スペース領域の高さを表し、parent_rs_wdは、スペースの親領域の幅を表す。親スペース領域の左下もまた指定されるが、スペースの親領域の上部かつ／又は右等、他の測定を採用してもよい。システムは、親スペース領域の高さを親スペース領域の幅で割ったものを表す、親スペース領域のアスペクト比parent_rs_aを計算する。要素６０４から、システムは、要素１５５２において、親の左の子のバウンディングボックスの相対面積比率をleft_bb_eにロードし、親の左の子のバウンディングボックスのアスペクト比をleft_bb_aにロードし、これら値の右の子の相手方をロードする。システムは、また、要素１５５２において、親のバウンディングボックスのアスペクト比をparent_bb_aにロードする。最後に、要素１５５３が、左右の子の積及び比を計算する。判断要素１５５４において、システムは、垂直切断が望まれているか、それとも水平切断が望まれているかを判断する。垂直切断の場合には、システムは図１６のフローチャートに進み、水平切断の場合には、システムは図１７のフローチャートに進む。
【００５３】
図１６から分かるように、判断要素１６０１は、親スペース領域のアスペクト比parent_rs_aが、親のバウンディングボックスのアスペクト比parent_bb_aよりも大きいか否かを判断する。大きい場合には、動作は要素１６０２に進み、図示のように、左右のスペース領域の幅及び高さを計算する。要素１６０２から分かるように、動作は要素１６０４にわたり、左右の子のスペース領域の底部位置right_rs_bt及びleft_rs_btを計算する。動作は要素１６０５に進み、左右の子の間の間隙と、左右の子の左位置left_rs_lf及びright_rs_lfとを計算する。
【００５４】
判断要素１６０１において判断されるように、親スペース領域のアスペクト比parent_rs_aが、親のバウンディングボックスのアスペクト比未満の場合には、システムは、判断１６０３において、要素１５５３において計算された右の子の積が、要素１５５３において計算された左の子の積を上回るか否かを判断する。右の子の積right_prodが左の子の積left_prodを上回る場合には、動作は要素１６０６に進み、左右の子のスペース領域の高さright_rs_ht及びleft_rs_htを計算する。判断要素１６０３が、要素１５５３において計算された右の子の積が、要素１５５３において計算された左の子の積未満であると判断する場合には、システムは、要素１６０７において、左右の子のスペース領域の高さright_rs_ht及びleft_rs_htを計算する。従って、要素１６０７は、要素１６０６に示す計算とは異なる計算を使用して同じ変数を計算する。動作は要素１６０６又は要素１６０７から要素１６０８に進み、左右の子のスペース領域の幅left_rs_wd及びright_rs_wdを計算する。次に、動作は図示のように要素１６０４及び１６０５に進み、ページ上の左右の子の間隙のサイズ及び位置を計算する。
【００５５】
判断要素１５０４において、親切断方向が水平の場合には、動作は図１７、具体的には判断１７０１に進む。判断要素１７０１は、親スペース領域のアスペクト比parent_rs_aが親のバウンディングボックスparent_bb_aよりも大きいか否かを判断する。大きくない場合には、動作は要素１７０２に進み、図示のように左右のスペース領域の幅及び高さを計算する。動作は要素１７０２から要素１７０４に進み、左右の子のスペース領域の左側位置right_rs_lf及びleft_rs_lfを計算する。動作は要素１７０５に進み、左右の子の間の間隙と、左右の子の底部位置left_rs_bt及びright_rs_btを計算する。
【００５６】
判断要素１７０１において判断されるように、親スペース領域のアスペクト比parent_rs_aが、親のバウンディングボックスのアスペクト比よりも大きい場合には、システムは、判断１７０３において、要素１５５３において計算された右の子の比が、要素１５５３において計算された左の子の比を上回るか否かを判断する。右の子の比right_ratioが左の子の比left_ratioを上回る場合には、動作は要素１７０６に進み、左右の子のスペース領域の幅right_rs_wd及びleft_rs_wdを計算する。判断要素１７０３が、要素１５５３において計算される右の子の積が、要素１５５３において計算される左の子の積未満であると判断した場合には、システムは、要素１７０７において、左右の子のスペース領域の幅right_rs_wd及びleft_rs_wdを計算する。従って、要素１７０７は、要素１７０６に示す計算とは別の計算を使用して同じ変数を計算する。動作は要素１７０６又は要素１７０７から要素１７０８に進み、左右の子のスペース領域の高さleft_rs_ht及びright_rs_htを計算する。次に、動作は要素１７０４及び１７０５に進み、左右の子の左位置及び底部位置、並びに子の間の間隙を計算する。
【００５７】
この計算及び判断を行う要素６０５と異なる方法を採用してもよく、なお本設計の範囲内である。従って、システムは、リーフノードを通って進み、各リーフノードに割り当てられたイメージの位置及びサイズを決定する。システムは、特定のリーフノードに割り当てられたイメージのアスペクト比に等しいアスペクト比を有するスペース領域を全てのリーフノードに割り振る。システムは、利用可能なスペース領域内で可能な限り大きいイメージを配置することができる。別法として、システムは、イメージ間にスペースを提供し、それによって特定の状況でレイアウトの見た目を向上させる目的で、この可能な最大サイズよりも小さいイメージを配置してもよい。この代替の一例として、システムは、利用可能なスペース領域内で許容可能な、可能な最大高さ及び幅の０．９５に等しい高さ及び幅を有するように各イメージを指定することができる（隣接するイメージ間に白色スペースを位置付けるさらに他の方法を使用してもよい）。このようにして、要素６０５の動作が終わる。
【００５８】
最後に、図６に戻ると、複数のスコア付け関数の何れも、要素６０７に適正であることができる。イメージの相対面積比率が固定のストリクトエリアレイアウトモードでは、システムはイメージが占めるページの一部を使用することができる。このようにしてスコア付けすることで、ユーザ指定の相対面積比率を守りながら、同時にイメージを可能な限り大きくすることが可能になる。ブリックレイアウトモードでは、ユーザは相対イメージ面積比率を設定せず、相対イメージ面積比率は、レイアウトツリー構造及びイメージの特定のリーフノードへの割り当て等、全体構成によって決まる（dictated）。この場合、システムは、イメージが大きくなり、相対的に一貫した面積になることを促進させる、より複雑なスコア付け関数を採用することができる。従って、スコア付けは、所望の実施及び状況に応じて変更が可能である。
【００５９】
シングルパス動作
レイアウトプロセスを高速化するために、上記説明の図６のフローチャートから要求される処理なしで、ユーザ入力に基づいてレイアウトをシングルパスで組み立てるように、上記構成及び設計を変更することができる。
【００６０】
本設計は、ストリクトエリアスタイルを含め、何れのスタイルのレイアウトの生成にも使用することが可能であるが、ブリックスタイルレイアウトを本シングルパス設計で有利に採用することができる。
【００６１】
図１０は、本シングルパス設計によるフォトアルバム作成システムを示している。図１０によれば、ユーザは、イメージ，レイアウトスタイル，比率等のセットではなくイメージのセットを供給する。上記説明と同様に、システムは、ユーザコンピュータのフォルダ，デジタルカメラのメモリカード，オンライン写真共有ウェブサイト，又は他の同様のイメージソースを含め、様々なソースからイメージをとることができる。
【００６２】
ユーザは、改ページの位置をさらに指定する。しかし、ユーザが明示的に改ページを指定する必要はない。例えば、ユーザは、各ページが６枚以上のイメージを有さないと指定することができる。別法として、システムは、例えば４などの如き、ページ１枚あたりの最大イメージ数を提供してもよく、又はページ１枚あたり３〜７のランダムな数のイメージを設定する等、ランダム又は半分ランダムに改ページを設定してもよい。他の改ページ規定も提供することができる。
【００６３】
図１１は、シングルパス自動レイアウト設計を示している。システムは、指定されたイメージ１００１をとり、各イメージを１度に１枚ずつレイアウトに追加する。システムは、図５Ｂの右半分に示すバイナリツリー構造のようなバイナリツリー構造の形でレイアウトを書く。システムは、イメージをレイアウトツリー構造に挿入することにより各イメージをレイアウトに追加する。システムは、レイアウトツリー構造内の複数の位置の何れにイメージを挿入してもよい。本設計は、利用可能なツリー構造位置の全てにイメージを配置し、最高スコアを有するレイアウトをもたらす位置を選択する。最高スコアレイアウト位置の選択は、図１１Ｂの要素１１１０及び１１１４に表される。シングルパスフォトアルバム生成システム１０００の結果は、ｐｄｆ等のような特定のフォーマットのフォトアルバム出力である。
【００６４】
具体的には、図１１Ａから図１１Ｂに続き、要素１１０１が、第１のイメージを含む１つのリーフを有するレイアウトツリーＴを初期化する。要素１１０２がＴを正規化する。但し、この文脈中での正規化は、後述する図１４のフローチャートに従って動作する。要素１１０３は、Ｔをbest_Tスロットに移す。要素１１０４は、さらなるイメージが利用可能であるか否か、すなわちこれが唯一のイメージであるか否かを評価する。これが唯一のイメージである場合には、best_Tは要素１１０４において入力されたＴであり、動作は終わる。要素１１０４において、さらなるイメージが利用可能な場合には、要素１１０５が次のイメージを取得し、要素１１０６がツリーＴ中の最初の位置を評価する。本明細書では、「位置」という用語は、リーフ或いはノードの何れか一方として定義される。要素１１０７は、Ｔの増補コピーとしてＴ’を作成する。ここで、増補は、新しいノードをその位置の場所に追加することであり、新しいノードの一方の子が、Ｔの位置がルートであるツリー構造Ｔのサブツリーであり、新しいノードの他方の子がイメージである。ツリー構造Ｔ’において、水平切断等、所定の切断が新しいノードにおいて行われる。要素１１０８はＴ’を正規化する。判断１１０９は、その位置が最初の位置であるか否かを判断する。これが最初の位置である場合、Ｔ’は要素１１１１においてbest_Tにシフトされ、動作は要素１１１２に進む。これが最初の位置ではない場合には、要素１１１０は新たな様式のＴ’のスコア及びbest_Tのスコアを計算する。ここで、スコア付けは上述した様々な方法又は後述する方法で行うことができる。要素１１１０は、Ｔ’の結果生じたスコアがbest_Tの結果生じたスコアよりも大きい、すなわちツリーが、best_Tの結果生じたスコアよりも良好である（これは、向上したレイアウトを示す）か否かを評価する。Ｔ’のスコアがbest_Tのスコアよりも大きい場合には、Ｔ’はbest_T位置又はレジスタに移り、動作は要素１１１２に移る。Ｔ’のスコアがbest_Tのスコア未満の場合には、動作は要素１１１２に進む。
【００６５】
図１１Ｂから、要素１１１２は、要素１１０７の切断とは対照的な位置において、異なる所定の切断を有する、Ｔに新しいノードを追加したものをＴ’にシフトする。システムは要素１１１３においてＴ’を正規化し、再び要素１１１４において、Ｔ’のスコア及びbest_Tのスコアを求める。要素１１１４は、要素１１１０と同じ又は異なるスコア付け方法を使用してよく、ここでも、Ｔ’のスコアがbest_Tのスコアよりも大きい場合には、システムは変更されたツリー構造Ｔ’をbest_Tに移し、それから動作は要素１１１６に進む。要素１１１０が、Ｔ’のスコアがbest_Tのスコア未満であることを示す場合には、動作は要素１１１６に直接進む。要素１１１６は、Ｔにおいてさらなる位置（ロケーション）が利用可能か否かを判断する。さらなる位置がレイアウトツリー構造Ｔにおいて利用可能ではない場合には、動作は要素１１１８に進む。さらなるノードがレイアウトツリー構造Ｔにおいて利用可能な場合には、要素１１１７はレイアウトツリー構造Ｔ中の次のノードを評価し、動作は要素１１０７に進み、先に述べたように進む。さらなるノードがレイアウトツリー構造Ｔ中に利用可能でない場合、要素１１１８は、ページが処理に利用可能なそれ以上のイメージを有しているか否かを判断する。利用可能なイメージがそれ以上ない場合、要素１１１９においてbest_TがＴに移り、要素１１０５を使用して次のイメージが得られる。利用可能なイメージがそれ以上ない場合には、best_Tがイメージレイアウトに提供されるツリーである。
【００６６】
この設計によるイメージの順次挿入を図１２に示す。既存のレイアウトツリー構造への各イメージの挿入は以下のように動作する。Ｎ枚のイメージを有するツリーＴの場合、システムは、（Ｎ＋１）番目のイメージを追加しようと探索し得る。システムは、３つのステップでＴの特定の位置にイメージを挿入する。まず、システムはその位置をルートとするサブツリーを除去し、それを、水平向き或いは垂直向きの何れか一方を有する新しいノードで置き換える。図１３Ａは、４つの関連イメージを有するツリー１３０１及び新しいイメージ５を挿入したいという要望を示している。イメージ５のない既存のイメージレイアウトはレイアウト１３０２として示されている。図１３Ｂは、サブツリー１３０３を新しいノード１３０４で置き換えることを示している。次に、システムは、新しいイメージを新しいノードの子として配置することができる。図１３Ｂは、新しいノード１３０４の子として配置された新しいイメージ５を示している。最後に、システムは、新しいノードの他方の子として、元の位置をルートとするレイアウトツリー構造Ｔのサブツリーを配置する。図１３Ｂから、システムは、元のノードをルートとするレイアウトツリー構造Ｔのサブツリーの隣に新しいイメージであるイメージ５を位置付け、元のイメージ、ここではイメージ１及び４を新しいノード１３０４の子として位置付ける。これは、イメージ１及び４がサブツリー１３０３に含まれるためである。この３段階プロセスをさらに図１３Ｃに示す。図１３Ｃでは、システムは、新しいイメージを新しい「Ｖ」ノード１３０５に挿入する。
【００６７】
従って、動作に際し、システムは、図１３Ａに示すレイアウトにような元のレイアウトがページのアスペクト比に等しいアスペクト比を有するものと仮定する。レイアウト１３０６及び１３０７としてそれぞれページ上に示される、図１３Ｂ及び図１３Ｃの両方の試行レイアウトでは、システムは、ページの内側に適合するようにレイアウトをスケーリングする。２つの試行レイアウトは元のレイアウトと異なるアスペクト比を有し、レイアウト中のイメージは全て新しいイメージに対して調整される。システムは、既存のイメージのアスペクト比ではなくサイズを調整する。
【００６８】
レイアウトの正規化を図１４に示す。本質的に、正規化は、ブリックスタイルのような概して所望のスタイルに呼応する３つのレイアウト構造を作成し、上の図６の要素６０４及び６０５と実質的に同様である。図１４から、要素１４０１は、Ｔ中の各ノードについて、システムがそこをルートとするサブツリー中のイメージのバウンディングボックスを特徴付けることを述べている。要素１４０２は、Ｔ中の各ノードについて、バウンディングボックスに従ってページ上の物理的なスペースを割り当てるように動作する。従って、不規則な形状のイメージ、キャプション付きイメージ等を、視覚的に許容可能なフォーマットで一様に画定し配置することができる。要素１４０１及び１４０２の動作は、要素６０４及び６０５の動作と同様又は同一である。
【００６９】
システムがレイアウトを正規化すると、レイアウトは、要素１１１０、続けて要素１１４においてスコア付けられる。スコア付け関数は、レイアウトの視覚的な品質に対して大きな影響を有し得る。１つのスコア付け関数は、２つの項目、すなわち、アルファ（alpha）及び一貫性（consistency）を含む。アルファは、ページのアスペクト比がイメージのバウンディングボックスのアスペクト比とどの程度一致しているかを測定し、例えば、０〜１であり得る数値である。一貫性は、ページ上の最小の写真の面積を、ページ上の最大の写真の面積で割ったものとして計算することができる。両方の項目に関して、例えば、１．０の値は理想的であることを表し、例えば、０．０の値は最悪の利用可能なアルファ又は一貫性を表す。
【００７０】
スコア付け関数は、例えば（（１．５ラアルファ）＋一貫性）等のような初期スコアを計算することができる。他の初期スコアを計算してもよい。この初期スコアは、しきい値未満のアルファ及び／又は一貫性の値の場合にペナルティを課すことができ、システムは、上に指定したように異なるパラメータの結果生じるスコアを比較することができる。
【００７１】
上記説明は、ユーザに特定の入力を提供させることができるようにすると共に、複数のレイアウトを計算することなく視覚的に美しいレイアウトを作成することができるようにする。
【００７２】
本設計は、サイズが可変であり、おそらく固定のアスペクト比を維持することができるスケーラブルなアイテムを含め、特定種類のオブジェクト又はアイテムのフロアプラニング等、効率的な配置機能を実行する他のシステムにも適用することが可能であることが当業者に認識されよう。特に、本明細書に述べた機能及び関連する態様により、様々な種類の最適又は強化された配置機能に対処することが可能であることが認識されよう。
【００７３】
以上を要約すると、次の通りである。すなわち、本発明は、固定のアスペクト比を有するイメージのようなオブジェクトを、プリントされたページのような予め定められたスペース内に位置付けるための方法を提示する。本方法は、少なくとも１つのノード及び複数のリーフを含むバイナリツリー構造を生成する。各リーフは、イメージに対応しており、かつ、１つのノードに関連付けされる。本方法は、さらに、バイナリツリー構造中の各ノードのバウンディングボックスを特徴付けるステップを含んでおり、このバウンディングボックスは、ノードと関連する全てのリーフの境界を確立する。本方法は、また、ウンディングボックスを操作して予め定められたスペース内に適合させるステップを含む。本方法では、バイナリツリー構造内にイメージを再配置し、或いは、バイナリツリー構造を再形成し、再形成したバイナリツリー構造を用いて特徴付けステップ及び操作ステップを選択的に繰り返し行なってよい。最終的な結果として、予め定められたスペース内に全てのイメージを有する少なくとも１つの可能性のあるレイアウトが得られる。
【００７４】
上記に本発明を有利に使用することができる様式を説明することを目的として、用紙シート等の表面上への効率的なイメージの配置を実行する方法について述べたが、本発明はそれに限定されないことを認識されたい。従って、当業者が想起することができる変更，変形，又は同等の構成は何れも全て、添付の特許請求の範囲に規定される本発明の範囲内にあるものと考えるべきである。
【符号の説明】
【００７５】
３０１，３０２ ボックス
３０３ レイアウト
３０４ 第１のイメージ
３０５ 第２のイメージ
４００ 完全フォトアルバム作成システム
５００ ツリー
５０１〜５０６ リーフ
５０７〜５１１ ノード
５１２ ブランチ
１０００ シングルパスフォトアルバム生成システム
【特許請求の範囲】
【請求項１】
スペース内のオブジェクトのレイアウトを組み立てることによってオブジェクトを位置付ける方法であって、
少なくとも１つのノード、及び、各々が１つのオブジェクトに対応する少なくとも１つのリーフを有するツリー構造を生成するステップと、
前記ツリー構造中の各ノードのバウンディングボックスであって、各々が前記ノードの下位にあるサブツリー中の何れのオブジェクトも全て含むバウンディングボックスを特徴付けるステップと、
前記ノードに関連する前記バウンディングボックスに従って、前記スペース内の領域を前記ツリー構造中の各ノードに割り当てるステップと、
を含むことを特徴とする方法。
【請求項２】
各オブジェクトは、固定のアスペクト比及び関連する相対面積比率を有し、
前記特徴付けるステップは、
各ノードの相対面積比率及びアスペクト比を、前記ノードの子の相対面積比率及びアスペクト比の関数として確立するステップ、
を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記特徴付けるステップは、
前記子の所定の次元が等しくなるように、各ノードの少なくとも１つの子と前記子の全ての子の相対面積比率を調整するステップ、
をさらに含み、
前記調整するステップは、前記確立することに先立って行われること、
を特徴とする請求項２に記載の方法。
【請求項４】
前記確立するステップは、
左右の子の相対面積比率及びアスペクト比を求めるステップと、
左右の子のパフォーマンスメトリックを求め、かつ、前記パフォーマンスメトリックを比較するステップと、
比較されたパフォーマンスメトリック、並びに、左右の子の相対面積比率及びアスペクト比に基づいて、ノードの相対面積比率及びアスペクト比を求めるステップと、
を含むことを特徴とする請求項２に記載の方法。
【請求項５】
前記調整するステップは、
左右の子の相対面積比率及びアスペクト比を求めるステップと、
前記左右の子の相対面積比率及びアスペクト比に基づいて、前記ノードの係数を求めるステップと、
１つの子及び前記子の全ての子の相対面積比率を前記係数で乗算するステップと、
を含むことを特徴とする方法。
【請求項６】
前記割り当てるステップの後に、前記ツリー構造をスコア付けるステップと、
異なるツリー構造を生成するステップと、
前記異なるツリー構造中の各ノードに対して、前記特徴付けるステップ及び前記割り当てるステップを実行するステップと、
前記異なるツリー構造をスコア付けるステップと、
前記ツリー構造及び異なるツリー構造のうち、高いスコアを有する方を渡すステップと、
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記特徴付けるステップ及び前記割り当てるステップの後に、オブジェクトを前記ツリー構造内のリーフに再度割り当てるステップと、
前記再度割り当てられたオブジェクトに対して、前記特徴付けるステップ及び前記割り当てるステップを繰り返すステップと、
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項８】
イメージに関連するアスペクト比を保持しながら、予め定められたスペースに前記イメージを位置付ける方法であって、
少なくとも１つのノード、及び、各々が１枚のイメージに対応すると共に１つのノードに関連する複数のリーフを有するバイナリツリー構造を生成するステップと、
前記バイナリツリー構造中の各ノードのバウンディングボックスであって、前記ノードに関連する全てのリーフの境界を確立するバウンディングボックスを特徴付けるステップと、
バウンディングボックスを操作して、前記予め定められたスペースに適合させるステップと、
を含むことを特徴とする方法。
【請求項９】
各イメージは、固定のアスペクト比及び関連する相対面積比率を有し、
前記特徴付けるステップは、
各ノードの相対面積比率及びアスペクト比を、前記ノードの子の相対面積比率及びアスペクト比の関数として確立するステップ、
を含むことを特徴とする請求項８に記載の方法。
【請求項１０】
前記特徴付けるステップ及び前記操作するステップの後に、前記バイナリツリー構造内のリーフにイメージを再度割り当てるステップと、
前記再度割り当てられたイメージに対して前記特徴付けるステップ及び前記操作するステップを繰り返すステップと、
をさらに含むことを特徴とする請求項８に記載の方法。
【請求項１】
スペース内のオブジェクトのレイアウトを組み立てることによってオブジェクトを位置付ける方法であって、
少なくとも１つのノード、及び、各々が１つのオブジェクトに対応する少なくとも１つのリーフを有するツリー構造を生成するステップと、
前記ツリー構造中の各ノードのバウンディングボックスであって、各々が前記ノードの下位にあるサブツリー中の何れのオブジェクトも全て含むバウンディングボックスを特徴付けるステップと、
前記ノードに関連する前記バウンディングボックスに従って、前記スペース内の領域を前記ツリー構造中の各ノードに割り当てるステップと、
を含むことを特徴とする方法。
【請求項２】
各オブジェクトは、固定のアスペクト比及び関連する相対面積比率を有し、
前記特徴付けるステップは、
各ノードの相対面積比率及びアスペクト比を、前記ノードの子の相対面積比率及びアスペクト比の関数として確立するステップ、
を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記特徴付けるステップは、
前記子の所定の次元が等しくなるように、各ノードの少なくとも１つの子と前記子の全ての子の相対面積比率を調整するステップ、
をさらに含み、
前記調整するステップは、前記確立することに先立って行われること、
を特徴とする請求項２に記載の方法。
【請求項４】
前記確立するステップは、
左右の子の相対面積比率及びアスペクト比を求めるステップと、
左右の子のパフォーマンスメトリックを求め、かつ、前記パフォーマンスメトリックを比較するステップと、
比較されたパフォーマンスメトリック、並びに、左右の子の相対面積比率及びアスペクト比に基づいて、ノードの相対面積比率及びアスペクト比を求めるステップと、
を含むことを特徴とする請求項２に記載の方法。
【請求項５】
前記調整するステップは、
左右の子の相対面積比率及びアスペクト比を求めるステップと、
前記左右の子の相対面積比率及びアスペクト比に基づいて、前記ノードの係数を求めるステップと、
１つの子及び前記子の全ての子の相対面積比率を前記係数で乗算するステップと、
を含むことを特徴とする方法。
【請求項６】
前記割り当てるステップの後に、前記ツリー構造をスコア付けるステップと、
異なるツリー構造を生成するステップと、
前記異なるツリー構造中の各ノードに対して、前記特徴付けるステップ及び前記割り当てるステップを実行するステップと、
前記異なるツリー構造をスコア付けるステップと、
前記ツリー構造及び異なるツリー構造のうち、高いスコアを有する方を渡すステップと、
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記特徴付けるステップ及び前記割り当てるステップの後に、オブジェクトを前記ツリー構造内のリーフに再度割り当てるステップと、
前記再度割り当てられたオブジェクトに対して、前記特徴付けるステップ及び前記割り当てるステップを繰り返すステップと、
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項８】
イメージに関連するアスペクト比を保持しながら、予め定められたスペースに前記イメージを位置付ける方法であって、
少なくとも１つのノード、及び、各々が１枚のイメージに対応すると共に１つのノードに関連する複数のリーフを有するバイナリツリー構造を生成するステップと、
前記バイナリツリー構造中の各ノードのバウンディングボックスであって、前記ノードに関連する全てのリーフの境界を確立するバウンディングボックスを特徴付けるステップと、
バウンディングボックスを操作して、前記予め定められたスペースに適合させるステップと、
を含むことを特徴とする方法。
【請求項９】
各イメージは、固定のアスペクト比及び関連する相対面積比率を有し、
前記特徴付けるステップは、
各ノードの相対面積比率及びアスペクト比を、前記ノードの子の相対面積比率及びアスペクト比の関数として確立するステップ、
を含むことを特徴とする請求項８に記載の方法。
【請求項１０】
前記特徴付けるステップ及び前記操作するステップの後に、前記バイナリツリー構造内のリーフにイメージを再度割り当てるステップと、
前記再度割り当てられたイメージに対して前記特徴付けるステップ及び前記操作するステップを繰り返すステップと、
をさらに含むことを特徴とする請求項８に記載の方法。
【図３】
【図４】
【図５Ａ】
【図５Ｂ】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１Ａ】
【図１１Ｂ】
【図１３Ａ】
【図１３Ｂ】
【図１３Ｃ】
【図１４】
【図１５Ａ】
【図１５Ｂ】
【図１６】
【図１７】
【図１】
【図２】
【図１２】
【図４】
【図５Ａ】
【図５Ｂ】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１Ａ】
【図１１Ｂ】
【図１３Ａ】
【図１３Ｂ】
【図１３Ｃ】
【図１４】
【図１５Ａ】
【図１５Ｂ】
【図１６】
【図１７】
【図１】
【図２】
【図１２】
【公開番号】特開２０１０−２６２６７８（Ｐ２０１０−２６２６７８Ａ）
【公開日】平成２２年１１月１８日（２０１０．１１．１８）
【国際特許分類】
【出願番号】特願２０１０−１８０８６７（Ｐ２０１０−１８０８６７）
【出願日】平成２２年８月１２日（２０１０．８．１２）
【分割の表示】特願２００４−２８５８６７（Ｐ２００４−２８５８６７）の分割
【原出願日】平成１６年９月３０日（２００４．９．３０）
【出願人】（５０３００３８５４）ヒューレット−パッカード デベロップメント カンパニー エル．ピー． (1,145)
【Ｆターム（参考）】
【公開日】平成２２年１１月１８日（２０１０．１１．１８）
【国際特許分類】
【出願日】平成２２年８月１２日（２０１０．８．１２）
【分割の表示】特願２００４−２８５８６７（Ｐ２００４−２８５８６７）の分割
【原出願日】平成１６年９月３０日（２００４．９．３０）
【出願人】（５０３００３８５４）ヒューレット−パッカード デベロップメント カンパニー エル．ピー． (1,145)
【Ｆターム（参考）】
[ Back to top ]