(57)【要約】【課題】大きさの異なる複数の矩形(ブロック)を画面上に、ブロック間の相対サイズと各ブロックのアスペクト比を維持しつつ、ブロック間の隙間を小さくするレイアウト方法およびレイアウトシステムを提供する。【解決手段】大きさの異なる複数のブロックを、ブロック間の相対サイズと各ブロックのアスペクト比を維持しながら一画面上にレイアウトした後、各ブロック間の隙間を出来るだけ小さくする、或いは無くするために、任意の画像ブロックの相対サイズ及びアスペクト比を維持しながら、任意のブロックのサイズを調整する。【選択図】図１
2010191669.tif 000002
【特許請求の範囲】
【請求項１】
大きさの異なる複数のブロックを一画面内に表示させるブロックレイアウト方法であって、
相対サイズとアスペクト比を持つブロックを格納する複数のレイアウトパターンを取得するステップと、
前記レイアウトパターンにしたがって前記ブロックを配置した場合、前記レイアウトパターンのそれぞれについて前記ブロックの面積占有率を計算し、面積占有率が最大であるレイアウトパターンを選出して前記レイアウトパターンに前記ブロックを当て嵌めるステップと、
各ブロックの相対サイズとアスペクト比を維持しつつ、各ブロックのサイズを調整して各ブロック間の隙間を小さくするステップと、
を有することを特徴とするブロックレイアウト方法。
【請求項２】
大きさの異なる複数のブロックを一画面内に表示させるブロックレイアウト方法であって、
相対サイズとアスペクト比を持つブロックのレイアウトを二分木構造に対応させて、レイアウトパターンを取得するステップと、
ノードとなるブロックを一つずつ前記二分木構造のレイアウトパターンに追加するステップと、
ノードを増やすたびに各ブロックの占有する面積の一画面の総面積に占める比率が最大になる子二分木を取得するステップと、
この処理を繰り返して、全てのブロックを追加し終わった時点で得られた二分木に対応するレイアウトを最適レイアウトとして取得するステップと、
各ブロックの相対サイズとアスペクト比を維持しつつ、各ブロックのサイズを調整して各ブロック間の隙間を小さくするステップと、
を有することを特徴とするブロックレイアウト方法。
【請求項３】
前記のサイズ調整は、大小の二つの子ノードのアスペクト比を維持しながら、大きい方のブロックのサイズを縮小し、小さい方のブロックのサイズを拡大し、併せて親ノードのサイズも調整することで隙間を減らすことを特徴とする請求項２記載のブロックレイアウト方法。
【請求項４】
前記のサイズ調整は、サイズ調整前後の二つ子ノードの面積和を一定にすることを特徴とする請求項３記載のブロックレイアウト方法。
【請求項５】
前記のサイズ調整は、サイズ調整前後の二つ子ノードの一辺の長さの和を一定にすることを特徴とする請求項３記載のブロックレイアウト方法。
【請求項６】
前記のサイズ調整は、二分木構造の深さ優先順で行うことを特徴とする請求項１乃至５のいずれか１項に記載のブロックレイアウト方法。
【請求項７】
前記の深さ優先順でのサイズ調整は、調整限界を設定して、前記の調整ステップごとに調整量を確認し、前記調整限界を超える場合には調整量を調整限界までに抑えることを特徴とする請求項６記載のブロックレイアウト方法。
【請求項８】
前記のサイズ調整は、全ブロックの調整量を累積した総調整量を設定して、前記の深さ優先順でのサイズ調整を終わった後に、前記ブロックごとに累積した総調整量を確認し、前記設定した総調整量を超える場合には前記総調整量に抑えるよう再調整することを特徴とする請求項７記載のブロックレイアウト方法。
【請求項９】
前記のサイズ調整は、前記深さ優先順の調整と前記再調整の実行後、前記ブロック間の隙間が解消できない場合には、前記ブロックごとのアスペクト比の調整を一定範囲で許容することを特徴とする請求項８記載のブロックレイアウト方法。
【請求項１０】
画像ブロックの元となるデータを記憶した記憶手段と、前記記憶手段に接続されたブロックレイアウト生成手段と、前記ブロックレイアウト生成手段に接続された出力手段とを有するブロックレイアウトシステムであって、
前記ブロックレイアウト生成手段は、一画面内に表示させる前記ブロックを配置可能な複数のレイアウトパターンを予め記憶しており、
前記相対サイズとアスペクト比を持つブロックをレイアウトパターンに従って配置した場合、前記レイアウトパターンのそれぞれについて前記ブロックの面積占有率を計算し、面積占有率が最大であるレイアウトパターンを選出し、前記レイアウトパターンに前記ブロックを当て嵌め、
各ブロックの相対サイズとアスペクト比を維持しつつ、各ブロック間の隙間を小さくするように各ブロックのサイズを調整して生成される画像データを出力装置に表示させることを特徴とするブロックレイアウトシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画面上における矩形から成るブロックのレイアウト方法に係り、特にブロック間の隙間を減らすレイアウト方法及びレイアウトシステムに関する。
【背景技術】
【０００２】
デジタル製品の普及により、デバイスにデータを蓄積しやすくなっている。また、インターネットの普及やメモリカードの容量増大により、データをデバイス間で移動しやすくなり、場所の制約なく手元のデバイスでデータを閲覧する便利さが実現されている。
【０００３】
画像などのデータを一覧するために、全てのデータ（画像）を同じサイズの矩形から成るブロックに収めてサムネイル形式で表示することが行われているが、画面上に表示されるサイズが同じであるため、ユーザにとって、どのデータ（画像）が重要かどうか判別しにくい。
【０００４】
限られたスペース（画面）を最大限に利用して、全てのデータを視覚化する技術として、treemapがよく使われている。treemapはデータごとの属性（例えば、重要度）を画面に占める面積にマッピングして全てのデータを一画面に表示する。一画面に各データの占めるスペースを割り当てるため、時々細長いブロックを割り当てることがある。そのような場合には、画像を変形しないようにアスペクト比を維持したいとの要求を満たすことができない。そこで、画面上におけるデータ（画像）の配置を工夫した提案がなされている（例えば、特許文献１、特許文献２参照。）。
【０００５】
前者は、選択された複数の画像を所定の領域にレイアウトする方法である。初期レイアウトは、所定領域に対して画像を均等に割付ける。初期レイアウトで生じたに画像の重なり、隔たりの非均等性や中心に対する非対称性を調整するために、それぞれの評価関数を用いて、画像の位置を順に調整する。調整の方法は、画像をＸ方向、Ｙ方向に微小量移動させ、各評価関数を計算する。係るステップを繰り返して、所定の調整回数や評価関数が所定量に達した段階で終了するものである。
【０００６】
後者は、画面のレイアウトを二分木に対応して、個々のデータを矩形から成るブロックとして配置する方法で、全てのデータを、相対的なサイズとアスペクト比(縦横比)を維持しながら、１画面における総ブロックの占める面積を最大になるようにレイアウトするものである。具体的には、レイアウトを二分木（テンプレート）に抽象化する。ノード（ブロック）を一つずつ二分木に追加して、ノードを増やすたびに画面にブロックの占有する面積（スペース）を画面の総面積に対する比率が最大になる子二分木を発見する。この処理を繰り返して、全てのブロックを追加し終わった時点で得られた二分木に対応する画面のレイアウトとするものである。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００８−１５９０７７号公報
【特許文献２】特開２００８−３０１２６４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、相対サイズやアスペクト比を維持しながら、全てのデータをブロックとして視覚化する場合、ブロック間に隙間が生じて、画面の表示スペースが有効に活用されないという問題がある。さらに、デバイスの表示スペースに生じる不規則な隙間のため、見栄えが良くなかった。
【０００９】
そこで、本発明は、上記した問題に鑑みてなされたもので、大きさの異なる複数の矩形(ブロック)を画面上に、ブロック間の相対サイズと各ブロックのアスペクト比を維持しつつ、ブロック間の隙間を小さくするレイアウト方法およびレイアウトシステムを提供するものである。
【課題を解決するための手段】
【００１０】
本発明の一態様によれば、大きさの異なる複数のブロックを一画面内に表示させるブロックレイアウト方法であって、相対サイズとアスペクト比を持つブロックを格納する複数のレイアウトパターンを取得するステップと、前記レイアウトパターンにしたがって前記ブロックを配置した場合、前記レイアウトパターンのそれぞれについて前記ブロックの面積占有率を計算し、面積占有率が最大であるレイアウトパターンを選出して前記レイアウトパターンに前記ブロックを当て嵌めるステップと、各ブロックの相対サイズとアスペクト比を維持しつつ、各ブロックのサイズを調整して各ブロック間の隙間を小さくするステップと、を有することを特徴とするブロックレイアウト方法が提供される。
【００１１】
また、本発明の別の一態様によれば、大きさの異なる複数のブロックを一画面内に表示させるブロックレイアウト方法であって、相対サイズとアスペクト比を持つブロックのレイアウトを二分木構造に対応させて、レイアウトパターンを取得するステップと、ノードとなるブロックを一つずつ前記二分木構造のレイアウトパターンに追加するステップと、ノードを増やすたびに各ブロックの占有する面積の一画面の総面積に占める比率が最大になる子二分木を取得するステップと、この処理を繰り返して、全てのブロックを追加し終わった時点で得られた二分木に対応するレイアウトを最適レイアウトとして取得するステップと、各ブロックの相対サイズとアスペクト比を維持しつつ、各ブロックのサイズを調整して各ブロック間の隙間を小さくするステップと、を有することを特徴とするブロックレイアウト方法が提供される。
【００１２】
また、本発明の別の一態様によれば、画像ブロックの元となるデータを記憶した記憶手段と、前記記憶手段に接続されたブロックレイアウト生成手段と、前記ブロックレイアウト生成手段に接続された出力手段とを有するブロックレイアウトシステムであって、前記ブロックレイアウト生成手段は、一画面内に表示させる前記ブロックを配置可能な複数のレイアウトパターンを予め記憶しており、前記相対サイズとアスペクト比を持つブロックをレイアウトパターンに従って配置した場合、前記レイアウトパターンのそれぞれについて前記ブロックの面積占有率を計算し、面積占有率が最大であるレイアウトパターンを選出し、前記レイアウトパターンに前記ブロックを当て嵌め、各ブロックの相対サイズとアスペクト比を維持しつつ、各ブロック間の隙間を小さくするように各ブロックのサイズを調整して生成される画像データを出力装置に表示させることを特徴とするブロックレイアウトシステムが提供される。
【発明の効果】
【００１３】
本発明によれば、大きさの異なる複数の矩形(ブロック)を画面上に、ブロック間の相対サイズと各ブロックのアスペクト比を維持しつつ、ブロック間の隙間を小さくするので、画面の表示スペースを有効に活用することができる。また、最適のレイアウトを少ない計算量で算出できる。さらに、レイアウトされたブロックの見栄えが良くなり、看者に対する訴求力を高めることができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施形態に係るブロックのレイアウトシステムの構成例を示すブロック図である。
【図２】面積和固定の条件下で、ノードを水平方向に分割する場合のサイズ調整を説明する図である。
【図３】面積和固定の条件下で、ノードを上下方向に分割する場合のサイズ調整を説明する図である。
【図４】辺長和固定の条件下で、ノードを水平方向に分割する場合のサイズ調整を説明する図である。
【図５】辺長和固定の条件下で、ノードを上下方向に分割する場合のサイズ調整を説明する図である。
【図６】面積和固定の条件下で、ノードを水平方向に分割し、調整限界を超える場合のサイズ調整を説明する図である。
【図７】面積和固定の条件下で、ノードを上下方向に分割し、調整限界を超える場合のサイズ調整を説明する図である。
【図８】辺長和固定の条件下で、ノードを水平方向に分割し、調整限界を超える場合のサイズ調整を説明する図である。
【図９】辺長和固定の条件下で、ノードを上下方向に分割し、調整限界を超える場合のサイズ調整を説明する図である。
【図１０】深さ優先順によるサイズ調整の処理の流れを示すフローチャートである。
【図１１】総当たりサイズ調整を示す説明する図である。
【図１２】幅優先順による総当りサイズ調整の処理の流れを示すフローチャートである。
【図１３】アスペクト比調整を示す説明する図である。
【図１４】ブロックのサイズ調整機能を実行する最適レイアウトの決定の処理の流れを示すフローチャートである。
【図１５】最適二分木の選出の詳細を示すフローチャートである。
【図１６】深さ優先順でのブロックサイズ調整の詳細を示すフローチャートである。
【発明を実施するための形態】
【００１５】
以下、本発明の一実施の形態について、図面を参照して説明する。尚、各図において同一箇所については同一の符号を付すとともに、重複した説明は省略する。
【００１６】
本発明において、複数のデータを１画面上にレイアウトして表示するために、個々のデータに付随する情報あるいは指標を矩形にマッピングする。マッピングされた矩形をブロックと定義している。例えば、データが画像の場合、ブロックは画像を拡大あるいは縮小した状態で表示される。文字のようにデータが画像でない場合、ブロックはデータの縮約版となり、ブロックの一辺の長さ（幅）、高さ、色などによってマッピングする。
【００１７】
一般に、大きく表示されたデータは見る者に注目されやすい。そこで、本発明では、重要なものを画面上に大きく表示する。つまり、矩形で表されるブロックのサイズ（辺の長さ、高さ）を重要度に正比例して拡大あるいは縮小する。本発明において、重要度は、特に限定されたものではなく、例えば、画像の場合、ユーザが自分の興味のある画像に対して重要度を高く設定することができる。画像以外のデータでは、利用者に薦める度合いや一番見せたい指標を重要度として使うことができる。したがって、各ブロックのサイズ及びアスペクト比は同じとは限らない。
【００１８】
本発明は、所定の画像表示領域内（例えば、携帯電話機の液晶ディスプレイ）に、複数の画像ブロックを、各画像ブロックをできる限り大きなサイズでレイアウトする。所定の画像表示領域内に各ブロックを、互いに重なることなく、上下又は水平方向に、配置する。各ブロックを拡大／縮小して配置するが、各ブロックのアスペクト比及びブロック間の相対サイズは変更しない。したがって、全ブロックを画像表示領域に収めるために、全てのブロックを同一倍率で適当に拡大／縮小する。
【００１９】
図1は、本発明の実施形態に係るブロックのレイアウトシステムの構成例を示すブロック図である。図１に示すように、ブロックレイアウトシステム１は、ブロックレイアウト生成装置１０と、ブロックレイアウト生成装置１０に接続された記憶装置２０と、ブロックレイアウト生成装置１０に接続された出力装置３０とを備えている。ブロックレイアウト生成装置１０、記憶装置２０、出力装置３０は必ずしもそれぞれ別の装置でなくともよい。例えば、ブロックレイアウト生成装置１０、記憶装置２０はパーソナルコンピュータ、出力装置３０はパーソナルコンピュータに接続されたモニタとすることができる。
【００２０】
記憶装置２０は、ブロックを生成する元となる複数のデータを記憶保持しており、それらのデータをブロックレイアウト生成装置１０に出力する機能を有する。記憶装置２０は、例えば、ＨＤＤレコーダ、ＤＶＤプレーヤ、ハードディスク記憶装置などである。ここで、「データ」は静止画像でも動画でもよく、静止画には、文書作成ソフトウエアで作成された電子文書も含まれる。
【００２１】
出力装置３０は、ブロックレイアウト生成装置１０が出力したレイアウト後のブロックをユーザが画像として視認可能な内容で出力する装置である。例えば、液晶ディスプレイ装置、プリンタ装置、携帯電話機などである。
【００２２】
ブロックレイアウト生成装置１０は、記憶装置２０から入力された各データから、ブロックを生成し、各ブロックの大きさができる限り大きくなるようにブロックのレイアウトを決定し、各ブロック間の隙間が小さくなるように各ブロックサイズを調整したレイアウトデータを出力装置３０に出力する。ブロック生成とは、各データから矩形の幅と高さを取得することである。たとえば、静止画の場合、静止画の幅と高さを読み取ることである。一般データの場合、データの特徴を表す二つの指標を矩形の幅と高さに対応すれば好適である。
【００２３】
ブロックレイアウト生成装置１０は、演算処理装置（ＣＰＵ）４０、主メモリ（ＲＡＭ）５０、読出し専用メモリ（ＲＯＭ）６０、入力装置（例えば、キーボード、操作パネルなど）７０、必要な場合にはハードディスク装置等の外部記憶装置（図示しない）を具備している。例えば、コンピュータ、ワークステーションなどの情報処理装置、或いは家電製品に搭載可能なマイクロコンピュータなどである。演算処理装置（ＣＰＵ）４０、主メモリ（ＲＡＭ）５０、読出し専用メモリ（ＲＯＭ）６０、及び入力装置７０はバス８０を介して互いにデータの受け渡しが可能に接続されている。また、バス８０にはグラフィック・ボード９０が接続されており、グラフィック・ボード９０は、ＣＰＵ４０からの制御に従ってレイアウトを表示させるため、例えば、ビットマップ形式の画像データを生成する。また、演算処理装置（ＣＰＵ）４０、主メモリ（ＲＡＭ）５０、読出し専用メモリ（ＲＯＭ）６０によって演算部１５を構成する。演算部１５は、後述する序列データ生成部１０１，ブロック生成部１０２，レイアウト生成部１０３として機能する。
【００２４】
ＲＯＭ６０、若しくは外部記憶装置（図示しない）などに、情報処理装置をブロックレイアウト生成装置１０として機能させるためのプログラム、又はレイアウト生成方法をコンピュータに実行させるためのプログラムが記憶されており、このプログラムを主メモリ５０上に載せ、ＣＰＵがこれを実行することによりブロックレイアウト生成装置１０が実現され、若しくはレイアウト生成方法が実行される。
【００２５】
次に、以上のように構成されたレイアウトシステムによるレイアウト生成について説明する。
【００２６】
本発明においては、大きさの異なる複数のブロックを、ブロック間の相対サイズと各ブロックのアスペクト比を維持しながら一画面上にレイアウトし、ブロック間の隙間をなるべく小さくする。係る最適レイアウトを少ない計算量で算出するために、ブロックの配置を二分木構造に対応させる。ここでの二分木構造は、全てのノードが子ノードを持たない末端ノード（葉ノード）であるか、二つの子ノードを持つ全二分木である。
【００２７】
レイアウトを二分木（テンプレート）に抽象化し、ノード（ブロック）を一つずつ二分木に追加して、ノードを増やすたびに画面にブロックの占有する面積（スペース）を画面の総面積に対する比率が最大になる子二分木を発見する。この処理を繰り返して、全てのブロックを追加し終わった時点で得られた二分木に対応する画面レイアウトを最適レイアウトとするものである。
【００２８】
大きさの異なる複数のブロックを、ブロック間の相対サイズと各ブロックのアスペクト比を維持しながら一画面上にレイアウトした後、各ブロック間の隙間を出来るだけ小さくする、或いは無くするために、任意の画像ブロックの相対サイズ及びアスペクト比を維持しながら、任意のブロックのサイズを調整する。
【００２９】
本発明にあっては、最適なサイズ調整を実現する観点からサイズ調整について評価する。すなわち、一画面領域でブロック間が隙間をなるべく少なくなるようにレイアウトされ、画面領域が有効使用されている割合を示すものである。本発明にあっては、この割合を、サイズ調整付き評価関数と定義する。すなわち、サイズ調整付き評価関数は、末端ノードのサイズを調整する前にある面積と、全ての調整を行った後にある面積の差分（絶対値差）を計算し、全部の末端ノードに対するこれらの差分和を末端ノードの面積和から引かれた値が、画面の面積に対しする比率と表すことができる。
【００３０】
以上の定義から、ｗｉ、ｈｉ＝調整前のデータｉ(末端ノードｉ）の辺の長さと高さ、ｗｉ’、ｈｉ’＝調整後の末端ノードｉの辺の長さと高さ、ｗ、ｈ＝ページ（画面）の辺の長さと高さ、λ＝ブロックの調整量の和を調整する係数とすると、サイズ調整付き評価関数は、下記の（１）式で算出することができる。
【数１】
2010191669.tif 000003
【００３１】
本発明にあっては、一つのノード（ブロック）を二分木（Ｌ（ｉ）,初期Ｌ（０）＝ＮＵＬＬ）に追加する際に、サイズ調整付き評価関数が最大となる二分木(Ｌ（ｉ＋１））を選ぶ。この処理を(ｉ＝０，・・・，Ｎ−１)で繰り返す。全てのブロックを追加し終わった時点で、得られた二分木(Ｌ（Ｎ），Ｎはブロック数)に対応する画面レイアウトを、最適レイアウトとするものである。
【００３２】
最適レイアウトを求める計算量(=O(N3))は、下に示す（２）式の通り、評価関数の計算する回数×毎回の計算量で予測できる。したがって、二分木全パターンの探索に比べて計算量が少なくて済むことがわかる。
【数２】
2010191669.tif 000004
【００３３】
上記したサイズ調整は、ある親ノードの二つ子ノードのアスペクト比を維持しながら、大きい方（横／縦）のサイズを縮小し、小さい方のサイズを拡大し、親ノードのサイズも同時に調整することで隙間を減らすものである。この調整を二分木の深さ優先順で繰り返して行う。深さ優先順によるノードの探索は、根ノードから出来るだけ遠くの末端ノードから探索を開始し、その後はバックトラックして、既に探索したノードの子である最も近くのノードまで戻るように、探索する。そもそも、各末端ノードは、それぞれ或る観点によって重み付けされた固有の大きさを持っている。例えば、重み付けされた固有の大きさとしての重要度は、相対サイズ及びアスペクト比で表されるから、ゼロとはならない。したがって、末端ノードから相対サイズ及びアスペクト比を求めていく、深さ優先順による探索が好適である。式１の特例として、λ＝０に場合、評価関数によるレイアウトの決定プロセスとサイズ調整プロセスを分離して行うことができる。
【００３４】
（サイズ調整）
上記したサイズ調整は、サイズ調整前後の二つの子ノードの面積和を一定にすることで実現することができる。以下、二つの子ノードの面積和を一定にする場合を分けて説明する。
【００３５】
(１）アスペクト比固定、二つの子ノードの面積和を固定、ノードを水平方向に分割して、サイズ調整を行う場合である。この場合には、二つの子ノードの高さを一致させることにより、隙間を無くすることができる。以上の条件で、図２に示すようにサイズ調整の前後の二つの子ノードを表し、サイズ調整係数をａ１、ａ２とすると、以下の関係式（３）式、（４）式が成立する。
【００３６】
（二つの子ノードの面積和を一定にする）
【数３】
2010191669.tif 000005
（二つの子ノードの高さを一致させる⇒  隙間なくなる）
【数４】
2010191669.tif 000006
【００３７】
これら、連立方程式の解は、次のようになる。
【数５】
2010191669.tif 000007
【００３８】
したがって、サイズ調整後の子ノードのサイズは、次の（７）式乃至（９）式で表される。
【数６】
2010191669.tif 000008
【００３９】
同様に、サイズ調整後の親ノードのサイズは、次の（１０）式、（１１）式で表される。
【数７】
2010191669.tif 000009
【００４０】
(２）アスペクト比固定、二つの子ノードの面積和を固定して、ノードを上下方向に分割して、サイズ調整を行う場合である。この場合には、二つの子ノードの辺の長さ（幅）を一致させることにより、隙間を無くすることができる。以上の条件から、図３に示すようにサイズ調整の前後の二つの子ノードを表し、サイズ調整係数をａ１、ａ２とすると、以下の関係式（１２）式、（１３）式が成立する。
【００４１】
（二つの子ノードの面積和を一定にする）
【数８】
2010191669.tif 000010
（二つの子ノードの辺の長さを一致させる⇒  隙間なくなる）
【数９】
2010191669.tif 000011
【００４２】
これら、連立方程式の解は、次のようになる。
【数１０】
2010191669.tif 000012
したがって、サイズ調整後の子ノードのサイズは、次の（１６）式乃至（１８）式で表される。
【数１１】
2010191669.tif 000013
【００４３】
同様に、サイズ調整後の親ノードのサイズは、次の（１９）式、（２０）式で表される。
【数１２】
2010191669.tif 000014
【００４４】
上記したサイズ調整は、サイズ調整前後の二つの子ノードの辺の長さの和を一定にすることでも実現することができる。以下、場合分けして説明する。
【００４５】
（３）アスペクト比固定、子ノードの辺の長さの和を固定、ノードを水平方向に分割して、サイズ調整を行う場合である。この場合には、二つの子ノードの高さを一致させることにより、隙間を無くすることができる。以上の条件から、図４に示すようにサイズ調整の前後の二つの子ノードを表し、サイズ調整係数をａ１、ａ２とすると、以下の関係式（２１）式、（２２）式が成立する。
【００４６】
（二つの子ノードの辺の長さの和を一定にする）
【数１３】
2010191669.tif 000015
（二つの子ノードの高さを一致させる⇒  隙間なくなる）
【数１４】
2010191669.tif 000016
【００４７】
これら、連立方程式の解は、次のようになる。
【数１５】
2010191669.tif 000017
したがって、サイズ調整後の子ノードのサイズは、次の（２５）式乃至（２７）式で表される。
【数１６】
2010191669.tif 000018
【００４８】
同様に、サイズ調整後の親ノードのサイズは、次の（２８）式、（２９）式で表される。
【数１７】
2010191669.tif 000019
【００４９】
（４）アスペクト比固定、子ノードの辺の長さの和を固定、ノードを上下方向に分割して、サイズ調整を行う場合である。この場合には、二つの子ノードの辺の長さを一致させることにより、隙間を無くすることができる。以上の条件から、図５に示すようにサイズ調整の前後の二つの子ノードを表し、サイズ調整係数をａ１、ａ２とすると、以下の関係式（３０）式、（３１）式が成立する。
【数１８】
2010191669.tif 000020
（二つの子ノードの辺の長さを一致させる⇒  隙間なくなる）
【数１９】
2010191669.tif 000021
【００５０】
これら、連立方程式の解は、次のようになる。
【数２０】
2010191669.tif 000022
したがって、サイズ調整後の子ノードのサイズは、次の（３４）式乃至（３６）式で表される。
【数２１】
2010191669.tif 000023
【００５１】
同様に、サイズ調整後の親ノードのサイズは、次の（３７）式、（３８)式で表される。
【数２２】
2010191669.tif 000024
【００５２】
上記の子ノードのサイズ調整は、一方の拡大と他方の縮小が同時に発生する。言いかえれば、ａ１＞１．０であれば、ａ２＜１．０が成立する。逆にａ１＜１．０であれば、ａ２＞１．０が成立する。以後の説明では、特段の指摘がない限り、ａ１≦１．０、ａ２≧１．０とする。
【００５３】
（調整限界を考慮したサイズ調整）
上記した深さ優先順でのサイズ調整を無制限に行うと、各ブロックの相対サイズが著しく変化し、例えば元々のサイズで表わされている重要度等にも影響を与える。
【００５４】
そこで、調整限界を設けて、上記の調整ステップごとに調整量をチェックし、調整限界を超えた場合には、調整限界までに抑えることが好適である。例えば、調整限界を当初の相対サイズのプラスマイナス１０％とする場合、縮小する限界がα１＝（１.０-１０％）＝０．９で、拡大する限界がα２＝（１.０＋１０％）＝１．１である。尚、調整限界は、システム設計の際に、デフォルトで設定しておき、ユーザが任意に設定変更可能とすることも好適である。
以下に、深さ優先順で調整限界を超えた場合のサイズ調整について説明する。
【００５５】
（５）アスペクト比固定、面積和を固定、ノードを水平方向に分割してサイズ調整を行う場合である。
【００５６】
以上の条件から、図６に示すようにサイズ調整後の二つの子ノードを表し、サイズ調整係数をａ１、ａ２とし、以下の関係式（３９）式が成立する。
【数２３】
2010191669.tif 000025
ブロック１の調整係数が限界α１を下回った場合、調整係数は、次のようになる。
【数２４】
2010191669.tif 000026
ブロック２の調整係数が限界α２を超えた場合、調整係数は、次のようになる。
【数２５】
2010191669.tif 000027
【００５７】
したがって、サイズ調整後の子ノードのサイズは、次の（４４）式乃至（４６）式で表される。
【数２６】
2010191669.tif 000028
【００５８】
同様に、サイズ調整後の親ノードのサイズは、次の（４７）式、（４８）式で表される。
【数２７】
2010191669.tif 000029
【００５９】
（６）アスペクト比固定、面積和を固定、ノードを上下方向に分割してサイズ調整を行う場合である。
【００６０】
以上の条件から、図７に示すようにサイズ調整後の二つの子ノードを表し、サイズ調整係数をａ１、ａ２とし、以下の関係式（４９）式が成立する。
【数２８】
2010191669.tif 000030
ブロック１の調整係数が限界α１を下回った場合、調整係数は、次のようになる。
【数２９】
2010191669.tif 000031
ブロック２の調整係数が限界α２を超えた場合、調整係数は、次のようになる。
【数３０】
2010191669.tif 000032
【００６１】
したがって、サイズ調整後の子ノードのサイズは、次の（５４）式乃至（５６）式で表される。
【数３１】
2010191669.tif 000033
【００６２】
同様に、サイズ調整後の親ノードのサイズは、次の（５７）式、（５８）式で表される。
【数３２】
2010191669.tif 000034
【００６３】
（７）アスペクト比固定、積み上げ辺長固定、ノードを水平方向に分割してサイズ調整を行う場合である。
【００６４】
以上の条件から、図８に示すようにサイズ調整後の二つの子ノードを表し、サイズ調整係数をａ１、ａ２とし、以下の関係式（５９）式が成立する。
【数３３】
2010191669.tif 000035
ブロック１の調整係数が限界α１を下回った場合、調整係数は、次のようになる。
【数３４】
2010191669.tif 000036
ブロック2の調整係数が限界α2を超えた場合、調整係数は、次のようになる。
【数３５】
2010191669.tif 000037
【００６５】
したがって、サイズ調整後の子ノードのサイズは、次の（６４）式乃至（６６）式で表される。
【数３６】
2010191669.tif 000038
【００６６】
同様に、サイズ調整後の親ノードのサイズは、次の（６７）式、（６８）式で表される。
【数３７】
2010191669.tif 000039
【００６７】
（８）アスペクト比固定、積み上げ辺長固定、ノードを上下方向に分割してサイズ調整を行う場合である。
【００６８】
以上の条件から、図９に示すようにサイズ調整後の二つの子ノードを表し、サイズ調整係数をａ１、ａ２とし、以下の関係式（６９）式が成立する。
【数３８】
2010191669.tif 000040
ブロック１の調整係数が限界α１を下回った場合、調整係数は、次のようになる。
【数３９】
2010191669.tif 000041
ブロック２の調整係数が限界α2を超えた場合、調整係数は、次のようになる。
【数４０】
2010191669.tif 000042
【００６９】
したがって、サイズ調整後の子ノードのサイズは、次の（７４）式乃至（７６）式で表される。
【数４１】
2010191669.tif 000043
【００７０】
同様に、サイズ調整後の親ノードのサイズは、次の（７７）式、（７８）式で表される。
【数４２】
2010191669.tif 000044
【００７１】
図１０により、上述した、深さ優先順によるサイズ調整をソフトウエア処理で実現する場合の処理の流れについて説明する。
【００７２】
図１０に示すように、まず、深さ優先順のノードリストを初期状態としてスタックＳに記録する（ステップＳ１００１）。次に、スタックＳが空か否か判定する（ステップＳ１００２）。空であれば終了し、空でなければ、スタック先頭を取り出し、レジスタに書き込む（ステップＳ１００３）。
【００７３】
次に、子ノードが空か否か判定する（ステップＳ１００４）。空であれば（Node）は葉である）、ステップＳ１００２に移り、空でなければサイズ調整係数ａ１、ａ２を（５），（６）式、或いは、（１４），（１５）式、或いは、（２３），（２４）式、或いは、（３２），（３３）式のいずれかによって算出する（ステップＳ１００５）。
【００７４】
次いで、サイズ調整係数ａ１、ａ２が調整各自の調整限界を超えるか否か判定する（ステップＳ１００６、ステップＳ１００７）。ブロック１の調整係数ａ１が限界α１を下回った場合には、（４０），（４１）式、或いは、（５０），（５１）式、或いは、（６０），（６１）式、或いは、（７０），（７１）式のいずれかによって新しいａ１、ａ２を算出する（ステップＳ１００８）。ブロック１の調整係数ａ１が限界α１を下回っていない場合には、ブロック２の調整係数ａ２をチェックする。ａ２が限界α2を超えた場合には、（４２），（４３）式、或いは、（５２），（５３）式、或いは、（６２），（６３）式、或いは、（７２），（７３）式のいずれかによって 新しいａ１、ａ２を算出する（ステップＳ１００９）。調整限界まで抑えた調整係数ａ１とａ２を算出したら、Nodeと子ノードのサイズを更新する（ステップＳ１０１０）。
【００７５】
（総当たりサイズ調整）
上記したサイズ調整は、深さ優先順でのサイズ調整を終わった後に、ブロックごとに実施された総調整量をチェックし、調整限界を超えた場合にその調整限界に抑えるまで再調整することが好適である。図１１に示すように、子ノードのサイズ調整は親ノードを経由して他の子ノードにも影響する。そのため、上述の調整方法で子ノードの調整係数を調整限界α以下に抑えても、最終的に調整係数が調整限界αを超える可能性が残る。そこで、全てのノードについてサイズ調整を終了後、末端ノードの調整係数をチェックして、調整係数が調整限界を超えた場合、その調整係数を調整限界までに設定して、末端ノードのサイズを再調整する。この総当たりサイズ調整は、幅優先順で探索するのが好適である。幅優先順では、親を持たずしかも最上位のノードである根ノード（root node）から探索を開始し、隣接した全てのノードを探索していく。探索した最も近いノードのそれぞれに対して同様のことを繰り返してノードを処理する。
【００７６】
図１２により、上述した、幅優先順による総当りサイズ調整をソフトウエア処理で実現する場合の処理の流れについて説明する。
【００７７】
図１２に示すように、まず、幅優先順のノードリストを初期状態としてキューＱに記録する（ステップＳ１２０１）。次に、キューＱが空か否か判定する（ステップＳ１２０２）。空であれば終了し、空でなければ、キューＱから先頭要素Node(調整係数ａ)を取り出し、レジスタに書き込む（ステップ１２０３）。
【００７８】
次に、Nodeの子ノードが空か否か判定する（ステップＳ１２０４）。空でなければ、Nodeの二つの子ノードの調整係数ａ１、ａ２を取得して（ステップＳ１２０5）、Nodeの調整係数ａを子ノードに掛け算の積み重ねを行って、ａ１＊ａをａ１と設定し、ａ２＊ａをａ２に設定して（ステップＳ１２０６）、ステップＳ１２０２に戻る。子ノードが空であれば、Nodeは葉であることがわかり、調整係数ａが調整限界以内かどうかを判定する（ステップＳ１２０７）。ここで、ａ＜１．０の場合、ａがα1を下回ったかどうかをチェックする；ａ＞１．０の場合、ａがα２を超えたかどうかをチェックする。Ｙｅｓであれば、調整限界の値をサイズ調整係数ａに設定する（ステップＳ１２０８）。次いで、Nodeのサイズを更新し（ステップＳ１２０９）、ステップＳ１２０２に戻る。
【００７９】
（アスペクト比調整）
次に、アスペクト比調整について説明する。上述した深さ優先順によるサイズ調整と幅優先順による総当たりサイズ調整を行った場合であっても、各ブロック間に若干の隙間が残ることがある。これまでのサイズ調整は、個々のブロックが持つ元々のアスペクト比を固定して行っている。
【００８０】
しかしながら、総当たりサイズ調整の後に、ブロックごとのアスペクト比を可能な範囲で調整することで、ブロック間の隙間をさらに減らすことが可能となる。調整可能な範囲は、各ブロックが元々備えている特徴を損なわない程度でなければならないことは言うまでもない。
【００８１】
そこで、本実施形態におけるアスペクト比調整は、図１３に示すように、末端ノードの配分されたスペース内で、隙間の存在する方向に隙間を埋めるように、一方のノードの辺長を伸ばす。アスペクト比の調整には、調整の限界βを設けて、アスペクト比調整限界βを超える場合、調整量を限界βまでに設定する。アスペクト比調整限界βに達しなければ、隙間がなくなるまで、ブロックの一辺の長さを伸ばす。
【００８２】
（ブロックのサイズ調整処理の全体的な流れ）
ここで、上述してきたブロックのサイズ調整処理の全体的な流れについて、図１４により、ブロックのサイズ調整機能を実行する最適レイアウトの決定をソフトウエア処理で実現する場合の処理の流れを説明する。
【００８３】
一つのノード（ブロック）を二分木（Ｌ（ｉ），初期Ｌ（０）は空である）に追加する（ステップＳ１４０１）。ｉ番目のデータを二分木に追加する場合に得られる複数の候補二分木に対応するパターン（Ｋ個、Ｋ＝２ｉ＋１）を取得する（ステップＳ１４０２）。次いで、Ｋ個パターンから最適二分木（サイズ調整付きレイアウト配置）を選出する（ステップＳ１４０３）。
【００８４】
この最適二分木の選出の詳細について、図１５に示す処理フローにしたがって説明する。
【００８５】
まず、候補二分木数 ← Ｋ，  j  ← １，Objectmax  ＝０ を設定する（ステップＳ１５０１）。次に、j番目の二分木に対応するパターンを取得する（ステップＳ１５０２）。あるパターンに基づいて、画面にレイアウトされるブロックごとのサイズを算出する（ステップＳ１５０３）。このブロックサイズは、例えば、上記特許文献２（特開２００８−３０１２６４号）に提示された方法を用いて算出することができるので、詳細は省略する。次に、深さ優先順でブロックサイズを調整する（ステップＳ１５０４）。この深さ優先順でのブロックサイズ調整の詳細について、図１６に示す処理フローにしたがって説明する。まず、初期のレイアウトを設定する（ステップＳ１６０１）。ここで、初期レイアウトは、あるパターンに基づいて各ブロックのサイズを決めた後のレイアウトである。次に、ノードのアスペクト比を維持しながら深さ優先順にサイズを調整する（ステップＳ１６０２）。深さ優先順によるサイズ調整の詳細は、上述した通りである。総当たりサイズ調整によって調整限界をチェックする（ステップＳ１６０３）。総当たりサイズ調整の詳細についても、上述した通りである。これらのサイズ調整を済ませてレイアウトが決まる（ステップＳ１６０４）。
【００８６】
図１５に戻り、最適二分木の選出の説明を続ける。深さ優先順でブロックサイズの調整後、次いで、評価関数（Object（j))値を算出する（ステップＳ１５０５）。次に、Objectmax ＜ Object（j) か否かを判定する（ステップＳ１５０６）。Ｙｅｓであれば、Object（j)  → Objectmax とし（ステップＳ１５０９）、Ｎｏであれば、j＜K  （Kは候補二分木数）か否かを判定する（ステップＳ１５０７）。Ｙｅｓであれば、j＋１  → jとし（ステップＳ１５０８）、ステップＳ１５０２に戻る。図１４に戻り、サイズ調整機能を備えたレイアウトの決定の説明を続ける。最適二分木の選出後、次いで、ｉ＜Ｎ  (Ｎはデータ数）か否かを判定する（ステップＳ１４０４）。Ｙｅｓであれば、ｉ＋１→ｉとし（ステップＳ１４０５）、ステップＳ１４０２に戻る。Ｎｏであれば、末端ノードのアスペクト比を調整してさらに隙間を減らして（ステップＳ１４０６）、レイアウトを決定する。アスペクト比の調整の詳細については、上述した通りである。本実施形態によれば、大きさの異なる複数の矩形(ブロック)を画面上に、ブロック間の相対サイズと各ブロックのアスペクト比を維持しつつ、ブロック間の隙間を小さくするので、画面の表示スペースを有効に活用することができる。また、最適のレイアウトを少ない計算量で算出できる。さらに、レイアウトされたブロックの見栄えが良くなり、看者に対する訴求力を高めることができる。
【００８７】
なお、本発明は上記の実施形態のそのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記の実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【符号の説明】
【００８８】
１０…ブロックレイアウト生成装置、２０…記憶装置、３０…出力装置、４０…演算処理装置、５０…主メモリ、６０…読出し専用メモリ、７０…入力装置。
【図１】
2010191669.tif 000045
【図２】
2010191669.tif 000046
【図３】
2010191669.tif 000047
【図４】
2010191669.tif 000048
【図５】
2010191669.tif 000049
【図６】
2010191669.tif 000050
【図７】
2010191669.tif 000051
【図８】
2010191669.tif 000052
【図９】
2010191669.tif 000053
【図１０】
2010191669.tif 000054
【図１１】
2010191669.tif 000055
【図１２】
2010191669.tif 000056
【図１４】
2010191669.tif 000057
【図１５】
2010191669.tif 000058
【図１６】
2010191669.tif 000059
【図１３】
2010191669.tif 000060