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