画像処理方法、画像処理装置、プログラムおよび記憶媒体
【課題】複数ページに亘るコンテンツの各ページに対する適切なレイアウトを自動生成可能とする。
【解決手段】配置領域に対するコンテンツの配置の際に、例えばＦＦＤＨを用いて最密充填レイアウトを生成する。生成された最密充填レイアウトにおいて、ページを跨いで配置されるコンテンツが発生した場合、当該コンテンツを含む、高さが左端のコンテンツの高さで定義され、配置領域の幅を持つブロックを次以降のページに移動させて、コンテンツがページで分断される事態を解消する。ブロック単位で処理を行うことで、複数ページに亘るコンテンツの各ページに対するレイアウトを容易に自動生成することができる。また、ブロック内でコンテンツを移動させてもページ数が増えることがなく、より高い自由度でページレイアウトを生成することができる。
【解決手段】配置領域に対するコンテンツの配置の際に、例えばＦＦＤＨを用いて最密充填レイアウトを生成する。生成された最密充填レイアウトにおいて、ページを跨いで配置されるコンテンツが発生した場合、当該コンテンツを含む、高さが左端のコンテンツの高さで定義され、配置領域の幅を持つブロックを次以降のページに移動させて、コンテンツがページで分断される事態を解消する。ブロック単位で処理を行うことで、複数ページに亘るコンテンツの各ページに対するレイアウトを容易に自動生成することができる。また、ブロック内でコンテンツを移動させてもページ数が増えることがなく、より高い自由度でページレイアウトを生成することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンテンツのページレイアウトを自動的に生成する画像処理方法、画像処理装置、プログラムおよび記憶媒体に関する。
【背景技術】
【０００２】
従来より、レイアウトに関する技術が研究、開発されており、集積回路のレイアウトやクロックレイアウトなど多方面で応用されている。こういったレイアウト技術は、テキストやイメージで構成された複数のコンテンツを紙面上に配置する場合にも適用することができる。
【０００３】
特許文献１には、各コンテンツデータをそれぞれ１つの矩形領域と対応させ、ドキュメントページ内において各矩形領域のサイズに応じて自動的にレイアウトを決定する方法が開示されている。特許文献１によれば、コンテンツデータに対応する矩形をグリッド状のレイアウト領域に配置し、その後、最適化アルゴリズムなどを用いてコンテンツ同士の重複を除去する。特許文献１では、さらに、レイアウト領域上の各グリッドに定義された重みに基づきレイアウトを最適化することで、コンテンツの中央寄せなども可能としている。
【０００４】
ところで、例えば半導体回路などのレイアウトを決定する場面では、如何に効率的な配置を行うかが非常に重要であり、そのための様々な手法が研究されている。同様の手法は、紙面レイアウトにも適用可能である。すなわち、半導体回路のレイアウト決定手法を紙面レイアウトに適用することで、ロール紙の先端から複数の例えば画像コンテンツを並べる際、配置する領域に対応するロールの長さがなるべく小さくなるようにレイアウトを決定する事ができる。
【０００５】
レイアウトの効率性を重視したレイアウト手法として、特許文献２では、コンテンツを紙面に対して効率良く割り付けて印刷する技術が開示されている。特許文献２によれば、印刷対象コンテンツを異なる配置で印刷可能領域に割り付けて複数の割付候補を生成した上で、印刷対象コンテンツの印刷可能領域に対する占有率に基づいて最終的な割付を決定することで、余白の少ない効率的なレイアウト生成を可能としている。
【０００６】
一方、一般的に、レイアウト対象として紙を利用する場合は、ページ単位でレイアウトが扱われる事が多い。そのため、レイアウト生成時に、単純に領域の長さだけを考慮すると、コンテンツがページを跨いで配置されてしまう、ページ内にコンテンツの配置される領域が少量であったとしても新たなページが作成されてしまう、などといった不都合が生じるおそれがある。
【０００７】
この不都合に対する解決方法は、様々に提案されている。例えば特許文献３では、構造化言語で記述された文書に対して、コンテンツの途中で改ページが発生した場合に、分断される要素の相関性に応じてコンテンツ全体を次ページにずらしたり、最低限必要な行数だけページ内に収めるなどのレイアウト変更を行う方法について開示されている。
【０００８】
また、特許文献４では、集約印刷時の転写紙枚数が集約率に応じて最大となるように文書のレイアウトやページ区切り位置を調整する方法が開示されている。特許文献４によれば、例えば図表などのコンテンツが複数のページに亘る場合、図表の配置を変更したりサイズを縮小するなどの処理が行われる。
【０００９】
さらに、特許文献５には、ページ内に含まれるコンテンツが少量である場合に、そのページの大部分が余白となり見栄えが劣るという課題を解決するために、コンテンツ間の距離を調整してレイアウトを変更するようにした技術が開示されている。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述した特許文献１によれば、従来ではユーザー側に委ねられていたレイアウト作業が自動化されるため、作業負荷の軽減に繋がる一方で、各コンテンツデータを効率的に配置する、という観点は考慮されていないという問題点があった。
【００１１】
また、上述した特許文献２では、そもそも、生成された複数の割付候補の中に精度の高いレイアウトが存在している保証がないという問題点があった。また、特許文献２によれば、占有率は、印刷対象コンテンツの印刷媒体上の印刷領域に占める割合として定義される。そのため、見た目に目立つ広範囲の余白と、コンテンツ間のマージンとが同様に扱われるおそれがある。さらに、特許文献２では、上述したようなページという概念を踏まえたレイアウトのあり方ついては触れられていない。
【００１２】
さらにまた、上述した特許文献３〜特許文献５の技術は、コンテンツのレイアウトそのものを生成する手法ではない。すなわち、特許文献３〜特許文献５の技術は、ページの区切りに応じてレイアウトを調整する手法に関するものであり、コンテンツを複数ページに亘る紙面上に配置する自動レイアウトを提供するものではない。
【００１３】
本発明は、上記に鑑みてなされたものであって、複数ページに亘るコンテンツの各ページに対する適切なレイアウトを自動生成可能な画像処理方法、画像処理装置、プログラムおよび記憶媒体を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上述した課題を解決し、目的を達成するために、本発明は、幅と、所定の高さ毎に順序付けて区切られた領域からなるページ領域とが定義される配置領域に対して複数のコンテンツを配置して出力する画像処理方法であって、配置領域の高さ方向に対して、コンテンツを、幅方向に一列に配置されるコンテンツのうち高さが最大のコンテンツの上端および下端からなる範囲内に配置すると共に、配置領域の幅を持ち、高さが最大のコンテンツの上端および下端で高さが定義されるブロックを、配置領域の高さ方向の一方の端を先頭として、隣接するブロックと接するように順次配置し、配置領域の幅方向に対して、コンテンツを、隣接するコンテンツと接すると共に配置領域の幅を超えず、且つ、全コンテンツが配置された際のブロックによる全体の高さが近似的に最小となるように配置する最密充填レイアウト生成ステップと、最密充填レイアウト生成ステップにより、ブロックがページ領域を跨いで配置されている場合に、ページ領域を跨いだブロックを、ブロックが跨ぐページ領域のうち順序が後以降のページ領域に移動させてブロックの再配置を行う最終レイアウト生成ステップとを有するを特徴とする。
【００１５】
また、本発明は、幅と、所定の高さ毎に順序付けて区切られた領域からなるページ領域とが定義される配置領域に対して複数のコンテンツを配置して出力する画像処理装置であって、配置領域の高さ方向に対して、コンテンツを、幅方向に一列に配置されるコンテンツのうち高さが最大のコンテンツの上端および下端からなる範囲内に配置すると共に、配置領域の幅を持ち、高さが最大のコンテンツの上端および下端で高さが定義されるブロックを、配置領域の高さ方向の一方の端を先頭として、隣接するブロックと接するように順次配置し、配置領域の幅方向に対して、コンテンツを、隣接するコンテンツと接すると共に配置領域の幅を超えず、且つ、全コンテンツが配置された際のブロックによる全体の高さが近似的に最小となるように配置する最密充填レイアウト生成手段と、最密充填レイアウト生成手段により、ブロックがページ領域を跨いで配置されている場合に、ページ領域を跨いだブロックを、ブロックが跨ぐページ領域のうち順序が後以降のページ領域に移動させてブロックの再配置を行う最終レイアウト生成手段とを有することを特徴とする。
【発明の効果】
【００１６】
本発明によれば、配置領域の高さ方向に対して、コンテンツを、幅方向に一列に配置されるコンテンツのうち高さが最大のコンテンツの上端および下端からなる範囲内に配置すると共に、配置領域の幅を持ち、高さが最大のコンテンツの上端および下端で高さが定義されるブロックを、配置領域の高さ方向の一方の端を先頭として、隣接するブロックと接するように順次配置し、配置領域の幅方向に対して、コンテンツを、隣接するコンテンツと接すると共に配置領域の幅を超えず、且つ、全コンテンツが配置された際のブロックによる全体の高さが近似的に最小となるように配置し、ブロックがページ領域を跨いで配置されている場合に、ページ領域を跨いだブロックを、ブロックが跨ぐページ領域のうち順序が後以降のページ領域に移動させてブロックの再配置を行うようにしている。そのため、コンテンツの配置をブロック単位で調整することができ、複数ページに亘るコンテンツの各ページに対する適切なレイアウトを自動的に生成可能であるという効果を奏する。
【図面の簡単な説明】
【００１７】
【図１】図１は、本発明に適用可能な画像処理装置の一例の構成を示すブロック図である。
【図２】図２は、本発明で想定するコンテンツのレイアウトについて説明するための略線図である。
【図３】図３は、本発明の第１の実施形態による画像処理を概念的に示す一例のフローチャートである。
【図４】図４は、ＦＦＤＨによるコンテンツの一例の配置方法を概略的に示すフローチャートである。
【図５】図５は、ＦＦＤＨにより生成した最密充填レイアウトの一例を示す略線図である。
【図６】図６は、ブロックおよび行の定義を説明するための略線図である。
【図７−１】図７−１は、ブロックがページを跨いで配置される例を説明するための略線図である。
【図７−２】図７−２は、ブロックがページを跨がないで配置される例を説明するための略線図である。
【図８】図８は、本発明の第１の実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。
【図９−１】図９−１は、効率的な配置であっても適当なページ区切りが見つからない例を説明するための略線図である。
【図９−２】図９−２は、本発明の第１の実施形態によるコンテンツの配置方法の効果を説明するための略線図である。
【図１０】図１０は、本発明の第２の実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。
【図１１】図１１は、ブロック自体の位置を調整する処理を示す一例のフローチャートである。
【図１２】図１２は、ブロック内でコンテンツの位置を調整する処理を示す一例のフローチャートである。
【図１３】図１３は、本発明の第４の実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。
【図１４】図１４は、発明の本第５の実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。
【発明を実施するための形態】
【００１８】
以下に添付図面を参照して、この発明に係る画像処理方法の最良な実施の形態を詳細に説明する。図１は、本発明に適用可能な画像処理装置１００の一例の構成を示す。図１に例示されるように、本発明に適用可能な画像処理装置１００は、一般的なコンピュータによって構成することができる。
【００１９】
画像処理装置１００において、内部バス１１０に対してＣＰＵ(Central Processing Unit)１０１、Ｉ／Ｏ(Input/Output)部１０２、ＲＯＭ(Read Only Memory)１０３、ＲＡＭ(Random Access Memory)１０４およびハードディスクドライブ（ＨＤＤ）１０５が接続される。内部バス１１０に接続される各部は、内部バス１１０を介して互いにデータのやりとりを行うことができるようになっている。
【００２０】
ＨＤＤ１０５は、各種のプログラムやデータが格納される。例えばＯＳ(Operating System)や、この発明に係る画像処理方法を実行するための画像処理プログラムなどがＨＤＤ１０５に格納される。また、画像入力部１１から入力された画像データがＨＤＤ１０５に格納される。ＣＰＵ１０１は、ＲＯＭ１０３に予め記憶されたプログラムや、ＨＤＤ１０５に格納されたプログラムに従い、ＲＡＭ１０４をワークメモリとして用いて、この画像処理装置１００の全体の動作を制御する。Ｉ／Ｏ部１０２は、画像入力部１１および画像出力部１２などを含む、この画像処理装置１００に接続される外部機器との間でのデータの入出力を管理する。
【００２１】
この画像処理装置１００で処理されるコンテンツデータとしての画像データは、画像入力部１１から画像入力装置１００に対して入力され、Ｉ／Ｏ部１０２を介してＨＤＤ１０５に格納されたり、ＣＰＵ１０１に供給される。画像入力部１１は、例えばスキャナ、複写機、スキャン機能や印刷機能を複合的に備える複合機といった、画像を取り込んで出力する機能を備える。画像入力部１１がＡＤＦ(Auto Document Feeder)を備え、複数の画像を連続して自動的に取り込み出力できるようにしてもよい。これに限らず、画像入力部１１がインターネットやＬＡＮ(Local Area Network)といったネットワークを介して通信を行う通信機能を備え、ネットワークに接続された記憶媒体から画像データを取り込むようにしてもよい。
【００２２】
なお、画像処理装置１００は、コンテンツデータとしてテキストデータを処理することもできる。テキストデータは、例えば、画像処理装置１００に接続されたキーボード（図示しない）や、外部機器からＩ／Ｏ部１０２を介して画像処理装置１００に入力される。
【００２３】
この画像処理装置１００で処理されたコンテンツデータは、Ｉ／Ｏ部１０２を介して画像出力部１２に対して出力される。画像出力部１２は、例えばプリンタやディスプレイといった、コンテンツデータから画像を形成して出力する機能を備える。画像処理装置１００は、画像入力部１１から入力されたコンテンツデータの１または複数をページ単位に配置したレイアウトデータを生成し、画像出力部１２に対して出力する。画像出力部１２は、画像処理装置１００から供給されたレイアウトデータに従い、コンテンツデータのページ単位での印刷や表示出力を行う。
【００２４】
＜第１の実施形態＞
本発明では、図２に例示されるように、様々な大きさ（幅×高さ）を有する複数の矩形コンテンツを、幅Ｗ、高さＨの配置領域２００上に配置する際のレイアウトを生成する。ここで、幅Ｗは有限の値を持ち、高さＨは、無限大の値を持つものとする。また、レイアウトとは、配置領域２００上におけるコンテンツの配置を示し、レイアウトデータは、レイアウトにおけるコンテンツの配置を示す情報（例えば座標情報）からなるものとする。また、ページとは、一度に表示を行うための領域をいい、以下では、幅Ｗを持つ配置領域を、一度に表示を行う所定の高さｈ毎に区切った各領域をページと呼ぶ。
【００２５】
図３は、本発明の第１の実施形態による画像処理を概念的に示す一例のフローチャートである。この図３のフローチャートにおける各処理は、ＣＰＵ１０１により、本第１の実施形態による画像処理プログラムに従い実行される。
【００２６】
ステップＳ１で複数のコンテンツデータが画像処理装置１００に取得される。次のステップＳ２で、画像処理装置１００は、ステップＳ１で取得された複数のコンテンツデータに基づき、最密充填レイアウトを生成する。そして、次のステップＳ３で、ステップＳ２で生成された最密充填レイアウトに基づきページ毎の最終レイアウトを決定する。このステップＳ３で決定された最終レイアウトを示すレイアウトデータが、画像出力部１２に対して出力される。
【００２７】
＜最密充填レイアウトの生成＞
図３のステップＳ２における最密充填レイアウトの生成処理について、より詳細に説明する。なお、実際に入力されるコンテンツデータは、様々な形状が想定されるが、以下では、説明のため、コンテンツデータによる画像が矩形であるものとする。ここで、コンテンツデータによる画像を含む最小の矩形を想定してもよいし、コンテンツデータによる画像に対してマージンなどを考慮した矩形を想定してもよい。以下では、煩雑さを避けるため、「コンテンツデータによる画像」を単に「コンテンツ」と呼ぶ。
【００２８】
ステップＳ２の最密充填レイアウトでは、予め決められた幅を持ち、高さが無限の領域に対して、下記の条件を満たし、且つ、高さを最小にするように複数のコンテンツを配置する問題として考えて、各コンテンツのレイアウトを決める。
（１）コンテンツの形状が矩形であって、幅および高さが有理数値である。
（２）回転を許容しない。
（３）各コンテンツが互いに重ならない。
【００２９】
ここで、（３）の各コンテンツが互いに重ならないという条件は、２つのコンテンツＣｉおよびＣｊについて、下記の式(１)〜式（４）のうち少なくとも１つが成立することと等価である。なお、式(１)〜式（４）において、値ｗおよび値ｈは、それぞれコンテンツの幅および高さ、値ｘおよび値ｙは、それぞれコンテンツの一端（例えば左下隅）のｘ座標およびｙ座標である。
ｘｉ＋ｗｉ≦ｘｊ …（１）
ｘｊ＋ｗｊ≦ｘｉ …（２）
ｙｉ＋ｈｉ≦ｙｊ …（３）
ｙｊ＋ｈｊ≦ｙｉ …（４）
【００３０】
各コンテンツに対して、式(１)〜式(４)のうち何れを採用するかを決める場合、単純に見積もって４(n(n-1)/2)通りの可能性があるといえる。この問題は、一般的に箱詰め問題と称され、ＮＰ困難に属しており、実用的な演算時間で解決することが極めて困難であると考えられる。そこで、本実施形態では、最適解に近似する最適近似解をできるだけ簡単な手順で求める手法を用いて、最密充填レイアウトの生成を行う。
【００３１】
このような問題を解決するために、上述の各条件を満たし、且つ、評価値すなわち最適解からの外れ度が定まっている基本的なアルゴリズムとして、ＦＦＤＨ(First-Fit Decreasing-Height)やＮＦＤＨ(Next-Fit Decreasing-Height)などが知られている。本発明の第１の実施形態では、ＦＦＤＨを用いて最密充填レイアウトの生成を行う。ＦＦＤＨについては、「E.G.Coffman, JR., M.R.Garey, D.S.Johonson, R.E.Tarjan(Bell Lab.&Stanford Univ.) "Performance bounds for level-oriented two-dimensional packing algorithms", SIAM J. Comput, vol.9., pp808-826, No.4, 1980.」（非特許文献１）に記載がある。
【００３２】
図４は、ＦＦＤＨによるコンテンツの一例の配置方法を概略的に示すフローチャートである。この図４のフローチャートにおける各処理は、ＣＰＵ１０１により、本第１の実施形態による画像処理プログラムに従い実行される。ＦＦＤＨによれば、先ず、コンテンツを高さの大きい順にソートして、ソート順で１番目のコンテンツ（すなわち最も高さの高いコンテンツ）を、配置領域の配置開始位置に配置して、処理を開始する。以下では、説明のため、配置開始位置を配置領域の左上隅とする。
【００３３】
図４のフローチャートによる処理の開始に先立って、何らかのコンテンツ（例えばソート順で１番目のコンテンツ）が配置領域に配置されているものとする。これを最後に配置されたコンテンツとして、図４のフローチャートによる処理が開始される。ステップＳ１０で、全てのコンテンツについて配置が完了したか否かが判定され、完了していないと判定されたら、処理がステップＳ１１に移行される。一方、完了していると判断されたら、図４のフローチャートによる一連の処理が終了する。
【００３４】
ステップＳ１１で、直前に選択したコンテンツに対してソート順で次のコンテンツを選択する。次のステップＳ１２で、ステップＳ１１で選択されたコンテンツがソート順で最後のコンテンツか否かが判定される。若し、最後のコンテンツではないと判定されたら、処理はステップＳ１３に移行される。
【００３５】
ステップＳ１３では、ステップＳ１１で選択されたコンテンツが、最後に配置したコンテンツの右隣に配置可能な否かが判定される。すなわち、最後に配置したコンテンツの右端から配置領域の右端までの幅が、ステップＳ１１で選択されたコンテンツの幅以上であれば、当該選択されたコンテンツが配置可能であると判定される。若し、配置不可であると判定されたら、処理はステップＳ１０に戻され、全てのコンテンツについて配置が完了していなければソート順でさらに次のコンテンツが選択され（ステップＳ１１）、処理が繰り返される。
【００３６】
一方、ステップＳ１３で配置可能であると判定されたら、処理はステップＳ１４に移行され、最後に配置したコンテンツの右隣にステップＳ１１で選択されたコンテンツが配置される。コンテンツの配置位置を示す情報は、例えばＲＡＭ１０４に記憶される。そして、処理がステップＳ１０に戻される。
【００３７】
上述のステップＳ１２で、ステップＳ１１で選択されたコンテンツがソート順で最後のコンテンツであると判定されたら、処理はステップＳ１５に移行される。ステップＳ１５では、未配置のコンテンツのうち、ソート順が最も早い（すなわち高さが最も高い）コンテンツを、最後に配置したコンテンツに対して幅方向の左端に配置されるコンテンツの下に、配置領域に対して左詰めで配置する。コンテンツの配置位置を示す情報は、例えばＲＡＭ１０４に記憶される。そして、処理はステップＳ１１に戻される。
【００３８】
図５は、上述のようにしてＦＦＤＨにより生成した最密充填レイアウトの一例を示す。この例では、幅が「１０」の配置領域に、８個のコンテンツが配置されている。この、図３のステップＳ２において生成された最密充填レイアウトを、初期ページレイアウトと呼ぶ。
【００３９】
図５および図４のフローチャートによる処理で分かるように、ＦＦＤＨによる最密充填レイアウトでは、コンテンツの右隣には、当該コンテンツと高さが同じかまたは低いコンテンツが配置される。また、左端のコンテンツについては、コンテンツの下には当該コンテンツと高さが同じかまたは低いコンテンツが配置される。以下、配置領域の幅を持ち、左端のコンテンツの上下端で高さおよび配置領域における高さ方向の位置が規定される領域を、「ブロック」と呼び、ブロックとブロックとの区切りを、「行」と呼ぶ（図６参照）。
【００４０】
ここで、図５の例では、各コンテンツは、上端を揃えて一列に配置されている。これに限らず、左端のブロックに対して右方向に一列に配置される一連のブロックは、上下端が左端のブロックの上端および下端からなる範囲を越えなければ、他の配置でもよい。
【００４１】
なお、ＦＦＤＨでは、最適解に対する評価値が下記の式(５)のようになることが知られている。式(５)は、コンテンツの高さと幅とをそれぞれ「１」に正規化した場合の例である。また、式(５)において、値ＨalgはＦＦＤＨにより求められる高さ、値Ｈoptは最適解を表す。
Ｈalg≦１.７×Ｈopt＋１ …（５）
【００４２】
＜第１の実施形態によるページレイアウトの生成＞
次に、上述した図３のステップＳ３における、ページ毎の最終レイアウトの生成について説明する。図３のステップＳ２において、図４を用いて説明した手順に従い最密充填レイアウトによる初期ページレイアウトを生成した後に、配置領域を、幅が配置領域の幅と一致し、所定の高さを持つページ単位に分割する。このとき、図７−１に例示されるように、あるブロックがページに跨って配置されてしまうことがある。図７−１の例では、配置領域３００に配置されたブロック３０１〜３０４のうち、ブロック３０３がページを跨いで配置されてしまっている。このままでは、コンテンツが途中で分断されてしまう結果となり、好ましくない。そこで、本発明の第１の実施形態では、各ブロックがページを跨がないようにレイアウトを調整して、ページ毎の最終レイアウトを生成する。
【００４３】
本第１の実施形態では、ページを跨いで配置されたブロックを、次のページの先頭に移動させる。ここで、次のページとは、ページを跨いで配置されたブロックの上端が属するページから見た次のページをいう。すなわち、図７−１の例では、ページを跨いで配置されているブロック３０３を次ページの先頭に移動させ、当該ブロック３０３より下に配置された各ブロックも、当該ブロック３０３の移動に伴い下方に位置をずらす。以降、この処理をページ毎に順次、繰り返して行うことで、最終的には全てのコンテンツがページを跨がないように配置されたレイアウトを生成することができる。
【００４４】
図８は、本第１の実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。この図８のフローチャートにおける各処理は、ＣＰＵ１０１により、本第１の実施形態による画像処理プログラムに従い実行される。先ず、ステップＳ２０で、対象ページのページレイアウトを取得する。なお、ステップＳ２０で取得されるページレイアウトは、処理の対象となる対象ページに係るブロックからなるレイアウトである。対象ページが第１ページ目の場合は、初期ページレイアウトから対象ページのページレイアウトを取得することになる。
【００４５】
次のステップＳ２１で、対象ページのページレイアウトにページを跨るブロックがあるか否かを判定する。若し、ページを跨るブロックが無いと判定されたら、処理はステップＳ２３に移行される。
【００４６】
一方、ステップＳ２１で、対象ページのレイアウトにページを跨るブロックがあると判定されたら、処理はステップＳ２２に移行される。ステップＳ２２では、対象ページのレイアウト中においてページを跨って配置されたブロックが、対象ページの次のページの先頭に配置されるように、当該ブロックおよび当該ブロックの下に配置される各ブロックを下方へずらして再配置する。ブロックの再配置が終了すると、処理はステップＳ２３に移行される。
【００４７】
ステップＳ２３では、現在のブロックの配置状態に従い、対象ページにおけるページレイアウトを生成し、当該対象ページのページレイアウトを決定する。そして、処理はステップＳ２４に移行され、全てのページについてページレイアウトが決定されたか否かが判定される。若し、ページレイアウトが決定されていないページが存在すると判定されたら、処理はステップＳ２０に戻され、ステップＳ２３でページレイアウトが決定された次のページを対象ページとして、処理が繰り返される。
【００４８】
一方、ステップＳ２４で、全てのページについてページレイアウトが決定されたと判定されたら、一連の処理が終了される。この場合、未配置のブロックが存在しない場合に、全てのページについてページレイアウトが決定されたと判定する。
【００４９】
このように、本発明の第１の実施形態によれば、様々なサイズのコンテンツを複数ページに亘る配置領域に配置する場合に、出力ページ数がなるべく小さくなり、且つ、コンテンツがページで分断されないようなレイアウトを自動的に生成できる。
【００５０】
また、配置領域に対して様々なサイズのコンテンツを配置する場合、全てのコンテンツがページを跨がないようにページ区切りを設けることができる保証が無く、ページを跨いで配置されるコンテンツが発生する可能性が高い。すなわち、コンテンツが配置された状態でコンテンツを区切らないように幅方向の線（ページ区切り）を引くためには、幅方向に見たときに、コンテンツの上辺または下辺が揃っているなどの条件が必要となる。図９−１は、効率的な配置であっても、適当なページ区切りが見つからない例を示す。
【００５１】
本発明の第１の実施形態によれば、コンテンツを配置する際に、配置領域の幅方向については、図９−２に例示されるように、左端に配置されたコンテンツ２０１の高さからはみ出ない範囲２０２に収まるコンテンツを探索していくため、ブロック単位での配置の入れ替えが可能となる。したがって、ページ間でコンテンツが分断されないような各ページのレイアウトを、最密充填レイアウトによる初期ページレイアウトの配置から容易に決定することが可能となる。
【００５２】
＜第２の実施形態＞
次に、本発明の第２の実施形態について説明する。本第２の実施形態では、上述した第１の実施形態の処理に対し、さらに、ページに跨るブロックが存在する場合に、当該ブロック以降のブロックから対象ページ内に収まるブロックを探索する。そして、探索されたブロックとページに跨るブロックとを入れ替えて再配置を行う。これにより、効率的なページレイアウトを簡易に生成することができる。
【００５３】
図４を用いて説明した最密充填レイアウトの生成方法によれば、新しいブロックの形成時には、その時点で未配置のコンテンツの中で高さが最大のコンテンツが当該ブロックの左端に配置されることになる。そのため、ブロックは、下方に配置されるに従い高さが単調に減少（または非増加）する。したがって、あるブロックがページを跨いで配置された場合、当該ブロックの下に、当該ブロックと配置を交換することでブロックがページを跨ぐ事態を解消可能な高さのブロックが存在している可能性がある。
【００５４】
そこで、本第２の実施形態では、あるブロックがページを跨いで配置された場合、当該ブロックの下に位置するブロックから順次、対象ブロックと配置を交換した際にページ内に収まるか否かを判定する。そして、ページ内に収まる高さのブロックが存在したら、そのブロックの配置と、ページを跨るブロックの配置とを入れ替える。ブロックがページを跨いで配置される毎に同様の処理を繰り返すことで、最終的には、全てのコンテンツがページを跨がないようなページレイアウトを生成することができる。
【００５５】
図７を用いて、より具体的に説明する。図７−１に示される例では、配置領域３００に対してブロック３０１〜３０４が配置され、それらのうち、ブロック３０３がページを跨いで配置されブロック３０３に含まれるコンテンツがページ区切りで分断されてしまっている。このようなコンテンツの分断は、特にコンテンツの内容が図や表などの場合、好ましくない。
【００５６】
ここで、上述した処理により、ページを跨いで配置されたブロック３０３の直下に配置されるブロックから順次、ブロック３０３との配置交換を試みる。図７−１の例では、１ページの高さ「１１」に対して上から高さがそれぞれ「６」、「３」および「３」のブロック３０１〜３０３が配置され、ブロック３０３が高さ「１」だけページからはみ出している。ブロック３０３を取り去ると、ブロック３０３の直上のブロック３０２とページ下端との間に高さ「２」の余裕が生じる。一方、ブロック３０３の１つ下に配置されるブロック３０４は、高さが「２」であるため、ブロック３０３とブロック３０４とを入れ替えて再配置を行うことで、ブロックがページを跨ぐ事態が解消されることが分かる。
【００５７】
図７−２は、図７−１の状態から、ブロック３０３とブロック３０４とを入れ替えて再配置した場合の例を示す。対象ページに対して、ブロック３０４がページを跨がずに配置されていることが分かる。このような再配置を行うことで、効率性を保持しつつ、ブロックがページを跨いでしまう事態を解消することができる。
【００５８】
図１０は、本第２の実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。この図１０のフローチャートにおける各処理は、ＣＰＵ１０１により、本第２の実施形態による画像処理プログラムに従い実行される。先ず、ステップＳ３０で、上述したステップＳ２０と同様にして、対象ページのページレイアウトを取得する。そして、次のステップＳ３１で、対象ページのページレイアウトにページを跨るブロックがあるか否かを判定する。若し、ページを跨るブロックが無いと判定されたら、処理はステップＳ３７に移行される。
【００５９】
一方、ステップＳ３１で、対象ページのレイアウトにページを跨るブロックがあると判定されたら、処理はステップＳ３２に移行される。ステップＳ３２では、ページを跨ると判定されたブロックの直上に配置されるブロックの下端から、対象ページの下端までの高さｙが求められる。
【００６０】
次のステップＳ３３で、対象ブロックの下にさらにブロックが配置されているか否かが判定される。ステップＳ３３による判定が、ステップＳ３１でページを跨るブロックがあると判定された直後の判定であれば、当該ページを跨るブロックが対象ブロックとされる。若し、対象ブロックの直下にさらにブロックが配置されていると判定されたら、処理はステップＳ３４に移行される。
【００６１】
ステップＳ３４では、対象ブロックの直下に配置されたブロックをページを跨るブロックと入れ替えて配置した場合に、ブロックが対象ページ内に収まるか否かが判定される。例えば、ステップＳ３２で求められた高さｙと、対象ブロックの直下に配置されたブロックの高さｈbとを比較し、高さｙが高さｈb以上であれば、当該ブロックが対象ページ内に収まると判定される。
【００６２】
若し、ステップＳ３４で、高さｈbが高さｙよりも高く、対象ブロックとページを跨ぐブロックとを入れ替えて配置した際に、対象ブロックがページ内に収まらないと判定されたら、処理はステップＳ３３に戻される。そして、直前にページを跨ぐブロックとの入れ替えを試みられたブロックを新たな対象ブロックとして、当該対象ブロックの直下に配置されているブロックについて、同様にして判定が行われる。
【００６３】
一方、ステップＳ３４で、高さｈbが高さｙ以内であって、対象ブロックとページを跨ぐブロックとを入れ替えて配置した際に、対象ブロックがページ内に収まると判定されたら、処理はステップＳ３５に移行される。ステップＳ３５では、当該対象ブロックとページを跨ぐブロックとが入れ替えられて、ブロックの再配置がなされる。この場合、当該対象ブロックがページを跨ぐブロックの直上のブロックの直下に配置されると共に、ページを跨ぐブロックが対象ページの次ページの先頭に配置される。そして、このブロックの直下から、当該対象ブロックの直下から配置されていた各ブロックが、順序を変えずに配置される。ステップＳ３５でブロックの再配置が行われると、処理はステップＳ３７に移行される。
【００６４】
上述のステップＳ３３で、対象ブロックの下にブロックが配置されていないと判定されたら、処理はステップＳ３６に移行される。この場合には、対象ページ内に収まるようにページを跨ぐブロックと入れ替え可能なブロックが存在しないことを意味する。そこで、ステップＳ３６では、当該ページを跨ぐブロックを対象ページの次ページの先頭に配置されるように、当該ブロックおよび当該ブロックの下に配置される各ブロックを下方にずらして再配置する。ブロックの再配置が終了すると、処理はステップＳ３７に移行される。
【００６５】
ステップＳ３７では、現在のブロックの配置状態に従い、対象ページにおけるページレイアウトを生成し、当該対象ページのページレイアウトを決定する。そして、処理はステップＳ３８に移行され、全てのページについてページレイアウトが決定されたか否かが判定される。若し、ページレイアウトが決定されていないページが存在すると判定されたら、処理はステップＳ３０に戻され、ステップＳ３７でページレイアウトが決定された次のページを対象ページとして、処理が繰り返される。
【００６６】
一方、ステップＳ３８で、全てのページについてページレイアウトが決定されたと判定されたら、一連の処理が終了される。この場合、未配置のブロックが存在しない場合に、全てのページについてページレイアウトが決定されたと判定する。
【００６７】
このように、本発明の第２の実施形態によれば、様々なサイズのコンテンツを複数ページに亘る配置領域に配置する場合に、出力ページ数がなるべく小さくなり、且つ、コンテンツがページで分断されないようなレイアウトを自動的に生成できる。
【００６８】
また、本第２の実施形態によれば、最密充填レイアウト生成により、新しいブロックの形成時には、その時点で未配置のコンテンツの中で高さが最大のコンテンツが当該ブロックの左端に配置されることになる。そのため、ブロックは、下方に配置されるに従い高さが単調に減少（または非増加）する。したがって、ブロックがページを跨いで配置されてしまった場合、直下のブロックから順次、ブロックの高さを調べていき、ページ内に収まる高さのブロックがあれば、そのブロックとページを跨ぐブロックとを入れ替えて再配置を行うことで、簡易に効率的なページレイアウトを生成することができる。
【００６９】
＜第３の実施形態＞
次に、本発明の第３の実施形態について説明する。本第３の実施形態では、上述した第１または第２の実施形態で生成された最終的なページレイアウトに対して、さらに調整を加えることで、より好ましいページレイアウトを生成する。この場合、ブロック自体の位置を調整する方法と、ブロック内でコンテンツの位置を調整する方法とが考えられる。
【００７０】
先ず、第１の方法として、ブロック自体の位置をページ内で調整する方法について説明する。すなわち、上述した第１および第２の実施形態により生成されるページレイアウトでは、最終ページに対して１つのブロックのみが配置され、そのページの残り全ての領域が空白という事態が起こり得る。そこで、上述した第１または第２の実施形態で説明した方法でページレイアウトを生成し、全ページ数が決定された後に、ブロック自体の位置をページ内およびページ間で調整する。
【００７１】
図１１は、ブロック自体の位置を調整する処理を示す一例のフローチャートである。この図１１のフローチャートにおける各処理は、ＣＰＵ１０１により、本第３の実施形態による画像処理プログラムに従い実行される。先ず、ステップＳ４０で、図４を用いて説明したようにして最密充填レイアウトを取得し、次のステップＳ４１で、最密充填レイアウトから初期ページレイアウトを生成する。この初期ページレイアウトでは、既に説明したように、ページを跨いで配置されるブロックが存在する可能性がある。次のステップＳ４２で、初期ページレイアウトに基づきブロック単位で再配置を行い、ページを跨ぐブロックが全ページに亘って存在しないようにする。ステップＳ４２での処理は、図８または図９を用いて説明した手順に従い、ページを跨ぐブロックを次のページの先頭に移動させたり、他のブロックとの入れ替えを行うことで、ブロックがページを跨いで配置される事態を解消する。
【００７２】
ステップＳ４２までの処理により全ページのレイアウトが決定し、レイアウトに必要な全ページ数が確定すると、処理はステップＳ４３に移行される。ステップＳ４３では、ブロックの位置調整を行う。
【００７３】
ステップＳ４３での処理として、例えばページ下部の空白部分のページ間でのバラツキが小さくなるように、ブロックを再配置することが考えられる。一例として、ステップＳ４２の処理が終了した時点で、全ブロックの高さの合計をページ数で除して、１ページに配置されるブロックの合計高さの平均値ｈavgを算出する。そして、最終ページに配置されるブロックの合計高さが平均値ｈavgに近くなるように、各ページから１つずつ、ブロックを最終ページに移動させる。
【００７４】
また、ページ内でブロックの再配置を行ってページ毎のレイアウトを調整することもできる。例えば、ページ内の下部に生じた空白を、ブロック間のマージンとして割り当てることが考えられる。一例として、下記の式（６）に例示されるように、各ページにおいて、下部の空白領域の高さＭをブロック数ｎ−１で除して、ブロック間に対して等分にブロック間マージンＢＭを割り当てる。
ＢＭ＝Ｍ／(ｎ−１) …（６）
【００７５】
勿論、このページ内でのブロック再配置と、上述したページ間でのブロックの移動とを組み合わせて実行してもよい。すなわち、ページ下部の空白部分のページ間でのバラツキが小さくなるようにブロックを再配置した後に、ページ内でのブロックの再配置を行い空白部分を均一化する。
【００７６】
次に、第２の方法として、ブロック内でコンテンツの位置を調整する方法について説明する。ブロック内でコンテンツを移動させても、ブロック自体を移動させない限りはページ数が増加することはない。そこで、ブロック内で例えば水平方向にコンテンツを移動させて、左右のバランスを調整する方法が考えられる。このとき、ブロック内に配置されるコンテンツのサイズや形状（アスペクト比）などを考慮してコンテンツの移動を行うと好ましい。
【００７７】
図１２は、ブロック内でコンテンツの位置を調整する処理を示す一例のフローチャートである。この図１２のフローチャートにおける各処理は、ＣＰＵ１０１により、本第３の実施形態による画像処理プログラムに従い実行される。先ず、ステップＳ５０で、図４を用いて説明したようにして最密充填レイアウトを取得し、次のステップＳ５１で、最密充填レイアウトから初期ページレイアウトを生成する。この初期ページレイアウトでは、既に説明したように、ページを跨いで配置されるブロックが存在する可能性がある。次のステップＳ５２で、初期ページレイアウトに基づきブロック単位で再配置を行い、ページを跨ぐブロックが全ページに亘って存在しないようにする。ステップＳ５２での処理は、図８または図９を用いて説明した手順に従い、ページを跨ぐブロックを次のページの先頭に移動させたり、他のブロックとの入れ替えを行うことで、ブロックがページを跨いで配置される事態を解消する。
【００７８】
ステップＳ５２までの処理により全ページのレイアウトが決定すると、処理がステップＳ５３に移行される。ステップＳ５３では、ブロック内でのコンテンツの位置調整を行う。
【００７９】
ステップＳ５３において、ブロックの視覚的な中心や、コンテンツの視覚的な中心は、例えば「Steven J.Harrington, J.Femando Naveda, Rhys Price Jones, Paul Roetling, Nishant Thakker, "Aesthetic Measures for Automated Document Layout"」（非特許文献２）に示される方法で算出可能である。例えば、ブロック内コンテンツ全体の水平方向の位置は下記の式(７)〜式(９)で、ブロック内コンテンツの左右のバランス度は下記の式（１０）でそれぞれ算出することができる。
【数１】
【数２】
【数３】
【数４】
【００８０】
なお、上述の式（７）〜式（１０）で用いられる各変数の意味は、次の通りである。
(ｘi,ｙi)：コンテンツiのｘｙ座標
(ｘc,ｙc)：ブロックの視覚的な中心
Ｍi：コンテンツの視覚的中心
(ｄx,ｄy)：ブロックの視覚的中心からの最大距離
ｄh：ブロックの高さ
【００８１】
また、ブロック内ではコンテンツを自由に移動させることができるため、例えば、ステップＳ５３において、ブロック内のコンテンツの中心位置がブロックの中央に近付くように、コンテンツの位置調整を行うこともできる。ブロック内コンテンツの中心位置は例えば下記の式（１１）および式（１２）により、バランス度は式（１３）により、それぞれ算出することができる。
【数５】
【数６】
【数７】
【００８２】
ブロックおよびコンテンツのレイアウト調整方法は、上述の例に限定されるものではない。例えば、上述した非特許文献２に記載されている幾つかの指標を用いてブロック間のコンテンツの配置を調整することもできる。
【００８３】
本発明に適用可能な最密充填レイアウトでは、コンテンツは基本的に左詰め（または右詰め）で配置される。一方、レイアウトとしては、幅方向のバランスがとれた方が一般的に見やすいとされている。本第３の実施形態によれば、ブロック内部でコンテンツの左右のバランスを調整する事で、レイアウトの効率性は保持しつつ、より美しいレイアウトを実現することができる。
【００８４】
また、本発明に適用可能な最密充填レイアウトでは、ブロック単位で見ると、基本的にコンテンツが左上詰め（または右上詰め）で配置される。一方、レイアウトとしては、コンテンツの重心がブロックの中央付近に位置していた方がバランスが良く、一般的に見やすいとされている。本第３の実施形態によれば、ブロック内部でコンテンツの重心位置を調整することで、レイアウトの効率性を保持しつつ、より美しいレイアウトを実現することができる。
【００８５】
＜第４の実施形態＞
次に、本発明の第４の実施形態について説明する。本第４の実施形態では、コンテンツに対する倍率の可変量や、アスペクトの可変量を取得し、これら取得された可変量に基づきコンテンツのサイズを変更することで、ブロックをページを跨がずに配置する。
【００８６】
図１３は、本第４の実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。この図１３のフローチャートにおける各処理は、ＣＰＵ１０１により、本第４の実施形態による画像処理プログラムに従い実行される。
【００８７】
この図１３のフローチャートは、例えば述した図８のフローチャートにおけるステップＳ２１や、図９のフローチャートにおけるステップＳ３１の判定において、ページに跨るブロックがあると判定された場合の処理に対応する。ページに跨るブロックがあると判定されると、ステップＳ６０において、当該ブロックに含まれるコンテンツに対する倍率およびアスペクト比の少なくとも一方の可変量を取得する。
【００８８】
可変量は、例えば画像処理装置１００に対するユーザ操作により、コンテンツ毎に指定することができる。これに限らず、可変量を予め画像処理プログラムにより指定するようにしてもよい。また、可変量は、ブロックに対する可変量であってもよい。さらに、コンテンツがテキストの場合は可変量を小さく、画像の場合は可変量を大きくといったように、可変量をコンテンツの種類に応じて指定するようにしてもよい。
【００８９】
なお、コンテンツがテキストであるか画像であるかは、例えばテキストが画像として入力される場合には、後述する第５の実施形態で説明する解析処理によって、判定することが考えられる。テキストがテキストデータで入力される場合には、データの種類に基づいて判定可能であることはいうまでもない。
【００９０】
可変量が取得されると、処理はステップＳ６１に移行され、可変量の範囲内でコンテンツまたはブロックを変形させた場合に、当該ブロックがページ内に収まるか否かが判定される。例えば、指定された可変量の範囲内でコンテンツを変形させ、それに伴いブロックを変形させて高さを調整することで当該ブロックがページ内に収まるか否かが判定される。若し、変形により当該ブロックがページ内に収まると判定されたら、処理はステップＳ６２に移行され、ページ内に収まるように当該ブロックの高さを調整する。
【００９１】
一方、ステップＳ６１で、可変量の範囲内で変形を行っても当該ブロックがページ内に収まらない、すなわち、当該ブロックがページを跨いでしまうと判定されたら、処理はステップＳ６３に移行される。そして、当該ブロックが次のページの先頭に配置され、それに伴い当該ブロックの下に配置されるブロックの位置も下方にずらされる。
【００９２】
＜第５の実施形態＞
次に、本発明の第５の実施形態について説明する。本第５の実施形態では、画像処理装置１００に対してコンテンツの内容を解析するコンテンツ解析機能を持たせる。そして、配置領域に配置するコンテンツの内容をコンテンツ解析機能によって解析し、解析結果に基づきブロックの入れ替えなどを行う。
【００９３】
コンテンツ解析機能は、例えばＣＰＵ１０１上で動作するプログラムとして実現される。コンテンツの解析方法としては、既存の技術を適用することができる。コンテンツの解析結果として得られる情報としては、例えば下記のような情報が考えられる。
分類：テキスト／イメージ
視覚情報：色／密度など
構造情報：見出し／タイトル／本文など
意味情報：コンテンツ間やブロック間の相関／重要度
【００９４】
先ず、入力されたコンテンツがテキストおよびイメージの何れであるかを解析する。例えば、入力された画像データに対して文字検出を行い、検出結果に基づきコンテンツがテキストおよびイメージの何れであるかを判定する。
【００９５】
なお、テキストは、テキストデータとして入力することもできる。この場合、表示範囲などテキストのレイアウトに関する情報が共に入力されるものとする。これに限らず、画像処理装置１００側において、入力されたテキストデータに対して表示範囲を設定するようにしてもよい。
【００９６】
コンテンツがイメージであれば、例えば画素毎の色情報に基づきＲＧＢ値のヒストグラムを作成して色に関する解析を行うことが考えられる。また例えば、画像データの空間周波数を解析することで、画像の密度に関する情報を取得することが考えられる。
【００９７】
コンテンツデータがテキストであれば、テキストの構造を解析し、見出し、タイトルおよび本文などをそれぞれ抽出することが考えられる。例えば、検出された文字（文字群）の位置や大きさ、装飾などに基づき、テキストの構造を解析することが考えられる。また、テキストデータがＨＴＭＬ(Hyper Text Markup Language)やＸＭＬ(Extensible Markup Language)といったマークアップ言語で記述されたテキストデータとして入力されている場合は、タグに基づき構造解析を行うことができる。これに限らず、テキストデータに用いられている単語を抽出してテキストの意味解析を行うことも考えられる。
【００９８】
上述した視覚情報や構造情報の解析結果に基づき、コンテンツ間の相関やコンテンツの重要度を解析することができる。また、コンテンツ毎の解析結果を用いて、それぞれコンテンツが１または複数配置されたブロック間での相関やブロックの重要度を解析することも可能である。
【００９９】
図１４は、本第５の実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。この図１４のフローチャートにおける各処理は、ＣＰＵ１０１により、本第５の実施形態による画像処理プログラムに従い実行される。この図１４のフローチャートにおいては、ページを跨ぐブロックがあった場合に、上述した解析結果を行って当該ブロックの直上に配置されるブロックと、当該ブロックより下方に配置されるブロックとの相関を順次、求める。そして、相関を示す相関値が予め定めた閾値ｔｈより高いと判定されたブロックとの配置の入れ替えを行う。
【０１００】
先ず、ステップＳ７０で、上述したステップＳ２０と同様にして、対象ページのページレイアウトを取得する。そして、次のステップＳ７１で、対象ページのページレイアウトにページを跨るブロックがあるか否かを判定する。若し、ページを跨るブロックが無いと判定されたら、処理はステップＳ７９に移行される。
【０１０１】
一方、ステップＳ７１で、対象ページのレイアウトにページを跨るブロックがあると判定されたら、処理はステップＳ７２に移行される。ステップＳ７２では、ページを跨ると判定されたブロックの直上に配置されるブロックの下端から、対象ページの下端までの高さｙが求められる。
【０１０２】
次のステップＳ７３で、対象ブロックの下にさらにブロックが配置されているか否かが判定される。ステップＳ７３による判定が、ステップＳ７１でページを跨るブロックがあると判定された直後の判定であれば、当該ページを跨るブロックが対象ブロックとされる。若し、対象ブロックの直下にさらにブロックが配置されていると判定されたら、処理はステップＳ７４に移行される。
【０１０３】
ステップＳ７４では、対象ブロックの直下に配置されたブロックをページを跨るブロックと入れ替えて配置した場合に、ブロックが対象ページ内に収まるか否かが判定される。例えば、ステップＳ７２で求められた高さｙと、対象ブロックの直下に配置されたブロックの高さｈbとを比較し、高さｙが高さｈb以上であれば、当該ブロックが対象ページ内に収まると判定される。
【０１０４】
若し、ステップＳ７４で、高さｈbが高さｙよりも高く、対象ブロックとページを跨ぐブロックとを入れ替えて配置した際に、対象ブロックがページ内に収まらないと判定されたら、処理はステップＳ７３に戻される。そして、直前にページを跨ぐブロックとの入れ替えを試みられたブロックを新たな対象ブロックとして、当該対象ブロックの直下に配置されているブロックについて、同様にして判定が行われる。
【０１０５】
一方、ステップＳ７４で、高さｈbが高さｙ以内であって、対象ブロックとページを跨ぐブロックとを入れ替えて配置した際に、対象ブロックがページ内に収まると判定されたら、処理はステップＳ７５に移行される。ステップＳ７５では、当該対象ブロックと、ページを跨ぐブロックの直上に配置されるブロックとの相関が算出される。そして、次のステップＳ７６で、この相関が予め決められた閾値ｔｈよりも高いか否かが判定される。
【０１０６】
若し、算出された相関が閾値ｔｈよりも高いと判定されたら、処理はステップＳ７７に移行され、当該対象ブロックとページを跨ぐブロックとが入れ替えられて、ブロックの再配置がなされる。この場合、当該対象ブロックがページを跨ぐブロックの直上のブロックの直下に配置されると共に、ページを跨ぐブロックが対象ページの次ページの先頭に配置される。そして、このブロックの直下から、当該対象ブロックの直下から配置されていたブロックが、順序を変えずに配置される。ステップＳ７７でブロックの再配置が行われると、処理はステップＳ７９に移行される。
【０１０７】
一方、ステップＳ７６で、相関が閾値ｔｈ以下であると判定されたら、処理はステップＳ７３に戻され、次のブロックについて処理が繰り返される。
【０１０８】
上述のステップＳ７３で、対象ブロックの下にブロックが配置されていないと判定されたら、処理はステップＳ７８に移行される。ステップＳ７８では、当該ページを跨ぐブロックを対象ページの次ページの先頭に配置されるように、当該ブロックおよび当該ブロックの下に配置される各ブロックを下方にずらして再配置する。ブロックの再配置が終了すると、処理はステップＳ７９に移行される。
【０１０９】
ステップＳ７９では、現在のブロックの配置状態に従い、対象ページにおけるページレイアウトを生成する。そして、処理はステップＳ８０に移行され、全てのページについてページレイアウトが決定されたか否かが判定される。若し、ページレイアウトが決定されていないページが存在すると判定されたら、処理はステップＳ７０に戻され、ステップＳ７９でページレイアウトが決定された次のページを対象ページとして、処理が繰り返される。
【０１１０】
一方、ステップＳ８０で、全てのページについてページレイアウトが決定されたと判定されたら、一連の処理が終了される。この場合、未配置のブロックが存在しない場合に、全てのページについてページレイアウトが決定されたと判定する。
【０１１１】
なお、上述では、ステップＳ７６において相関が閾値ｔｈよりも高いと判定されたブロックを直接的に入れ替えに用いているが、これはこの例に限定されない。例えば、ページを跨ぐブロックの下に配置され、且つ、ページ内に収まると判定された対象ブロックが複数存在する場合も考えられる。このような場合に、当該対象ブロック全てについて、ページを跨ぐブロックの直上のブロックとの相関を求め、最も相関の高いブロックを選択して入れ替えに用いてもよい。
【０１１２】
このように、本第５の実施形態では、ステップＳ７４でブロックの高さｈに基づきブロックの入れ替えが可能だと判断されても、入れ替えられたブロックと当該ブロックの直上に配置されるブロックとの相関が低いと判定されると、その入れ替えを行わない。これにより、ブロックの入れ替えによって内容的に無関係のブロックが配置されることが抑制される。
【０１１３】
なお、上述した各実施形態による画像処理装置１００で実行される画像処理プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ(Compact Disk)、ＤＶＤ(Digital Versatile Disk)等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【０１１４】
また、上述した各実施形態による画像処理装置１００で実行される画像処理プログラムを、インターネットなどのネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また、上述した各実施形態による画像処理装置１００で実行される画像処理プログラムをインターネットなどのネットワーク経由で提供または配布するように構成しても良い。
【０１１５】
また、上述した各実施形態による画像処理装置１００で実行される画像処理プログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。
【０１１６】
上述した各実施形態による画像処理装置１００で実行される画像処理プログラムは、上述した最密充填レイアウトを生成するモジュールと、最密充填レイアウトに基づき各ページのレイアウトを生成するモジュールとを含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵ１０１（プロセッサ）が例えばＨＤＤ１０５から画像処理プログラムを読み出して実行することにより、上述の各モジュールが主記憶装置（ＲＡＭ１０４）上にロードされ、最密充填レイアウト生成モジュールと、ページレイアウト生成モジュールとが主記憶装置上に生成されるようになっている。
【０１１７】
なお、上述では、本発明に適用可能な画像処理装置１００が一般的なコンピュータとして構成されるように説明したが、これはこの例に限定されない。例えば、本発明による画像処理装置１００は、コピー機能、プリンタ機能、スキャナ機能およびファクシミリ機能のうち少なくとも２つの機能を有する複合機に適用することができる。また、本発明による画像処理装置１００は、複写機、プリンタ、スキャナ装置、ファクシミリ装置などの画像形成装置であれば何れにも適用することができる。
【符号の説明】
【０１１８】
１１ 画像入力部
１２ 画像出力部
１００ 画像処理装置
１０１ ＣＰＵ
１０２ Ｉ／Ｏ部
１０５ ＨＤＤ
２００ 配置領域
【先行技術文献】
【特許文献】
【０１１９】
【特許文献１】特許第４０４７３２６号公報
【特許文献２】特開２００５−２７５６８２公報
【特許文献３】特開２００６−２５９８１９公報
【特許文献４】特開２００７−１５０６９８公報
【特許文献５】特開２００７−１１５７７公報
【技術分野】
【０００１】
本発明は、コンテンツのページレイアウトを自動的に生成する画像処理方法、画像処理装置、プログラムおよび記憶媒体に関する。
【背景技術】
【０００２】
従来より、レイアウトに関する技術が研究、開発されており、集積回路のレイアウトやクロックレイアウトなど多方面で応用されている。こういったレイアウト技術は、テキストやイメージで構成された複数のコンテンツを紙面上に配置する場合にも適用することができる。
【０００３】
特許文献１には、各コンテンツデータをそれぞれ１つの矩形領域と対応させ、ドキュメントページ内において各矩形領域のサイズに応じて自動的にレイアウトを決定する方法が開示されている。特許文献１によれば、コンテンツデータに対応する矩形をグリッド状のレイアウト領域に配置し、その後、最適化アルゴリズムなどを用いてコンテンツ同士の重複を除去する。特許文献１では、さらに、レイアウト領域上の各グリッドに定義された重みに基づきレイアウトを最適化することで、コンテンツの中央寄せなども可能としている。
【０００４】
ところで、例えば半導体回路などのレイアウトを決定する場面では、如何に効率的な配置を行うかが非常に重要であり、そのための様々な手法が研究されている。同様の手法は、紙面レイアウトにも適用可能である。すなわち、半導体回路のレイアウト決定手法を紙面レイアウトに適用することで、ロール紙の先端から複数の例えば画像コンテンツを並べる際、配置する領域に対応するロールの長さがなるべく小さくなるようにレイアウトを決定する事ができる。
【０００５】
レイアウトの効率性を重視したレイアウト手法として、特許文献２では、コンテンツを紙面に対して効率良く割り付けて印刷する技術が開示されている。特許文献２によれば、印刷対象コンテンツを異なる配置で印刷可能領域に割り付けて複数の割付候補を生成した上で、印刷対象コンテンツの印刷可能領域に対する占有率に基づいて最終的な割付を決定することで、余白の少ない効率的なレイアウト生成を可能としている。
【０００６】
一方、一般的に、レイアウト対象として紙を利用する場合は、ページ単位でレイアウトが扱われる事が多い。そのため、レイアウト生成時に、単純に領域の長さだけを考慮すると、コンテンツがページを跨いで配置されてしまう、ページ内にコンテンツの配置される領域が少量であったとしても新たなページが作成されてしまう、などといった不都合が生じるおそれがある。
【０００７】
この不都合に対する解決方法は、様々に提案されている。例えば特許文献３では、構造化言語で記述された文書に対して、コンテンツの途中で改ページが発生した場合に、分断される要素の相関性に応じてコンテンツ全体を次ページにずらしたり、最低限必要な行数だけページ内に収めるなどのレイアウト変更を行う方法について開示されている。
【０００８】
また、特許文献４では、集約印刷時の転写紙枚数が集約率に応じて最大となるように文書のレイアウトやページ区切り位置を調整する方法が開示されている。特許文献４によれば、例えば図表などのコンテンツが複数のページに亘る場合、図表の配置を変更したりサイズを縮小するなどの処理が行われる。
【０００９】
さらに、特許文献５には、ページ内に含まれるコンテンツが少量である場合に、そのページの大部分が余白となり見栄えが劣るという課題を解決するために、コンテンツ間の距離を調整してレイアウトを変更するようにした技術が開示されている。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述した特許文献１によれば、従来ではユーザー側に委ねられていたレイアウト作業が自動化されるため、作業負荷の軽減に繋がる一方で、各コンテンツデータを効率的に配置する、という観点は考慮されていないという問題点があった。
【００１１】
また、上述した特許文献２では、そもそも、生成された複数の割付候補の中に精度の高いレイアウトが存在している保証がないという問題点があった。また、特許文献２によれば、占有率は、印刷対象コンテンツの印刷媒体上の印刷領域に占める割合として定義される。そのため、見た目に目立つ広範囲の余白と、コンテンツ間のマージンとが同様に扱われるおそれがある。さらに、特許文献２では、上述したようなページという概念を踏まえたレイアウトのあり方ついては触れられていない。
【００１２】
さらにまた、上述した特許文献３〜特許文献５の技術は、コンテンツのレイアウトそのものを生成する手法ではない。すなわち、特許文献３〜特許文献５の技術は、ページの区切りに応じてレイアウトを調整する手法に関するものであり、コンテンツを複数ページに亘る紙面上に配置する自動レイアウトを提供するものではない。
【００１３】
本発明は、上記に鑑みてなされたものであって、複数ページに亘るコンテンツの各ページに対する適切なレイアウトを自動生成可能な画像処理方法、画像処理装置、プログラムおよび記憶媒体を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上述した課題を解決し、目的を達成するために、本発明は、幅と、所定の高さ毎に順序付けて区切られた領域からなるページ領域とが定義される配置領域に対して複数のコンテンツを配置して出力する画像処理方法であって、配置領域の高さ方向に対して、コンテンツを、幅方向に一列に配置されるコンテンツのうち高さが最大のコンテンツの上端および下端からなる範囲内に配置すると共に、配置領域の幅を持ち、高さが最大のコンテンツの上端および下端で高さが定義されるブロックを、配置領域の高さ方向の一方の端を先頭として、隣接するブロックと接するように順次配置し、配置領域の幅方向に対して、コンテンツを、隣接するコンテンツと接すると共に配置領域の幅を超えず、且つ、全コンテンツが配置された際のブロックによる全体の高さが近似的に最小となるように配置する最密充填レイアウト生成ステップと、最密充填レイアウト生成ステップにより、ブロックがページ領域を跨いで配置されている場合に、ページ領域を跨いだブロックを、ブロックが跨ぐページ領域のうち順序が後以降のページ領域に移動させてブロックの再配置を行う最終レイアウト生成ステップとを有するを特徴とする。
【００１５】
また、本発明は、幅と、所定の高さ毎に順序付けて区切られた領域からなるページ領域とが定義される配置領域に対して複数のコンテンツを配置して出力する画像処理装置であって、配置領域の高さ方向に対して、コンテンツを、幅方向に一列に配置されるコンテンツのうち高さが最大のコンテンツの上端および下端からなる範囲内に配置すると共に、配置領域の幅を持ち、高さが最大のコンテンツの上端および下端で高さが定義されるブロックを、配置領域の高さ方向の一方の端を先頭として、隣接するブロックと接するように順次配置し、配置領域の幅方向に対して、コンテンツを、隣接するコンテンツと接すると共に配置領域の幅を超えず、且つ、全コンテンツが配置された際のブロックによる全体の高さが近似的に最小となるように配置する最密充填レイアウト生成手段と、最密充填レイアウト生成手段により、ブロックがページ領域を跨いで配置されている場合に、ページ領域を跨いだブロックを、ブロックが跨ぐページ領域のうち順序が後以降のページ領域に移動させてブロックの再配置を行う最終レイアウト生成手段とを有することを特徴とする。
【発明の効果】
【００１６】
本発明によれば、配置領域の高さ方向に対して、コンテンツを、幅方向に一列に配置されるコンテンツのうち高さが最大のコンテンツの上端および下端からなる範囲内に配置すると共に、配置領域の幅を持ち、高さが最大のコンテンツの上端および下端で高さが定義されるブロックを、配置領域の高さ方向の一方の端を先頭として、隣接するブロックと接するように順次配置し、配置領域の幅方向に対して、コンテンツを、隣接するコンテンツと接すると共に配置領域の幅を超えず、且つ、全コンテンツが配置された際のブロックによる全体の高さが近似的に最小となるように配置し、ブロックがページ領域を跨いで配置されている場合に、ページ領域を跨いだブロックを、ブロックが跨ぐページ領域のうち順序が後以降のページ領域に移動させてブロックの再配置を行うようにしている。そのため、コンテンツの配置をブロック単位で調整することができ、複数ページに亘るコンテンツの各ページに対する適切なレイアウトを自動的に生成可能であるという効果を奏する。
【図面の簡単な説明】
【００１７】
【図１】図１は、本発明に適用可能な画像処理装置の一例の構成を示すブロック図である。
【図２】図２は、本発明で想定するコンテンツのレイアウトについて説明するための略線図である。
【図３】図３は、本発明の第１の実施形態による画像処理を概念的に示す一例のフローチャートである。
【図４】図４は、ＦＦＤＨによるコンテンツの一例の配置方法を概略的に示すフローチャートである。
【図５】図５は、ＦＦＤＨにより生成した最密充填レイアウトの一例を示す略線図である。
【図６】図６は、ブロックおよび行の定義を説明するための略線図である。
【図７−１】図７−１は、ブロックがページを跨いで配置される例を説明するための略線図である。
【図７−２】図７−２は、ブロックがページを跨がないで配置される例を説明するための略線図である。
【図８】図８は、本発明の第１の実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。
【図９−１】図９−１は、効率的な配置であっても適当なページ区切りが見つからない例を説明するための略線図である。
【図９−２】図９−２は、本発明の第１の実施形態によるコンテンツの配置方法の効果を説明するための略線図である。
【図１０】図１０は、本発明の第２の実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。
【図１１】図１１は、ブロック自体の位置を調整する処理を示す一例のフローチャートである。
【図１２】図１２は、ブロック内でコンテンツの位置を調整する処理を示す一例のフローチャートである。
【図１３】図１３は、本発明の第４の実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。
【図１４】図１４は、発明の本第５の実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。
【発明を実施するための形態】
【００１８】
以下に添付図面を参照して、この発明に係る画像処理方法の最良な実施の形態を詳細に説明する。図１は、本発明に適用可能な画像処理装置１００の一例の構成を示す。図１に例示されるように、本発明に適用可能な画像処理装置１００は、一般的なコンピュータによって構成することができる。
【００１９】
画像処理装置１００において、内部バス１１０に対してＣＰＵ(Central Processing Unit)１０１、Ｉ／Ｏ(Input/Output)部１０２、ＲＯＭ(Read Only Memory)１０３、ＲＡＭ(Random Access Memory)１０４およびハードディスクドライブ（ＨＤＤ）１０５が接続される。内部バス１１０に接続される各部は、内部バス１１０を介して互いにデータのやりとりを行うことができるようになっている。
【００２０】
ＨＤＤ１０５は、各種のプログラムやデータが格納される。例えばＯＳ(Operating System)や、この発明に係る画像処理方法を実行するための画像処理プログラムなどがＨＤＤ１０５に格納される。また、画像入力部１１から入力された画像データがＨＤＤ１０５に格納される。ＣＰＵ１０１は、ＲＯＭ１０３に予め記憶されたプログラムや、ＨＤＤ１０５に格納されたプログラムに従い、ＲＡＭ１０４をワークメモリとして用いて、この画像処理装置１００の全体の動作を制御する。Ｉ／Ｏ部１０２は、画像入力部１１および画像出力部１２などを含む、この画像処理装置１００に接続される外部機器との間でのデータの入出力を管理する。
【００２１】
この画像処理装置１００で処理されるコンテンツデータとしての画像データは、画像入力部１１から画像入力装置１００に対して入力され、Ｉ／Ｏ部１０２を介してＨＤＤ１０５に格納されたり、ＣＰＵ１０１に供給される。画像入力部１１は、例えばスキャナ、複写機、スキャン機能や印刷機能を複合的に備える複合機といった、画像を取り込んで出力する機能を備える。画像入力部１１がＡＤＦ(Auto Document Feeder)を備え、複数の画像を連続して自動的に取り込み出力できるようにしてもよい。これに限らず、画像入力部１１がインターネットやＬＡＮ(Local Area Network)といったネットワークを介して通信を行う通信機能を備え、ネットワークに接続された記憶媒体から画像データを取り込むようにしてもよい。
【００２２】
なお、画像処理装置１００は、コンテンツデータとしてテキストデータを処理することもできる。テキストデータは、例えば、画像処理装置１００に接続されたキーボード（図示しない）や、外部機器からＩ／Ｏ部１０２を介して画像処理装置１００に入力される。
【００２３】
この画像処理装置１００で処理されたコンテンツデータは、Ｉ／Ｏ部１０２を介して画像出力部１２に対して出力される。画像出力部１２は、例えばプリンタやディスプレイといった、コンテンツデータから画像を形成して出力する機能を備える。画像処理装置１００は、画像入力部１１から入力されたコンテンツデータの１または複数をページ単位に配置したレイアウトデータを生成し、画像出力部１２に対して出力する。画像出力部１２は、画像処理装置１００から供給されたレイアウトデータに従い、コンテンツデータのページ単位での印刷や表示出力を行う。
【００２４】
＜第１の実施形態＞
本発明では、図２に例示されるように、様々な大きさ（幅×高さ）を有する複数の矩形コンテンツを、幅Ｗ、高さＨの配置領域２００上に配置する際のレイアウトを生成する。ここで、幅Ｗは有限の値を持ち、高さＨは、無限大の値を持つものとする。また、レイアウトとは、配置領域２００上におけるコンテンツの配置を示し、レイアウトデータは、レイアウトにおけるコンテンツの配置を示す情報（例えば座標情報）からなるものとする。また、ページとは、一度に表示を行うための領域をいい、以下では、幅Ｗを持つ配置領域を、一度に表示を行う所定の高さｈ毎に区切った各領域をページと呼ぶ。
【００２５】
図３は、本発明の第１の実施形態による画像処理を概念的に示す一例のフローチャートである。この図３のフローチャートにおける各処理は、ＣＰＵ１０１により、本第１の実施形態による画像処理プログラムに従い実行される。
【００２６】
ステップＳ１で複数のコンテンツデータが画像処理装置１００に取得される。次のステップＳ２で、画像処理装置１００は、ステップＳ１で取得された複数のコンテンツデータに基づき、最密充填レイアウトを生成する。そして、次のステップＳ３で、ステップＳ２で生成された最密充填レイアウトに基づきページ毎の最終レイアウトを決定する。このステップＳ３で決定された最終レイアウトを示すレイアウトデータが、画像出力部１２に対して出力される。
【００２７】
＜最密充填レイアウトの生成＞
図３のステップＳ２における最密充填レイアウトの生成処理について、より詳細に説明する。なお、実際に入力されるコンテンツデータは、様々な形状が想定されるが、以下では、説明のため、コンテンツデータによる画像が矩形であるものとする。ここで、コンテンツデータによる画像を含む最小の矩形を想定してもよいし、コンテンツデータによる画像に対してマージンなどを考慮した矩形を想定してもよい。以下では、煩雑さを避けるため、「コンテンツデータによる画像」を単に「コンテンツ」と呼ぶ。
【００２８】
ステップＳ２の最密充填レイアウトでは、予め決められた幅を持ち、高さが無限の領域に対して、下記の条件を満たし、且つ、高さを最小にするように複数のコンテンツを配置する問題として考えて、各コンテンツのレイアウトを決める。
（１）コンテンツの形状が矩形であって、幅および高さが有理数値である。
（２）回転を許容しない。
（３）各コンテンツが互いに重ならない。
【００２９】
ここで、（３）の各コンテンツが互いに重ならないという条件は、２つのコンテンツＣｉおよびＣｊについて、下記の式(１)〜式（４）のうち少なくとも１つが成立することと等価である。なお、式(１)〜式（４）において、値ｗおよび値ｈは、それぞれコンテンツの幅および高さ、値ｘおよび値ｙは、それぞれコンテンツの一端（例えば左下隅）のｘ座標およびｙ座標である。
ｘｉ＋ｗｉ≦ｘｊ …（１）
ｘｊ＋ｗｊ≦ｘｉ …（２）
ｙｉ＋ｈｉ≦ｙｊ …（３）
ｙｊ＋ｈｊ≦ｙｉ …（４）
【００３０】
各コンテンツに対して、式(１)〜式(４)のうち何れを採用するかを決める場合、単純に見積もって４(n(n-1)/2)通りの可能性があるといえる。この問題は、一般的に箱詰め問題と称され、ＮＰ困難に属しており、実用的な演算時間で解決することが極めて困難であると考えられる。そこで、本実施形態では、最適解に近似する最適近似解をできるだけ簡単な手順で求める手法を用いて、最密充填レイアウトの生成を行う。
【００３１】
このような問題を解決するために、上述の各条件を満たし、且つ、評価値すなわち最適解からの外れ度が定まっている基本的なアルゴリズムとして、ＦＦＤＨ(First-Fit Decreasing-Height)やＮＦＤＨ(Next-Fit Decreasing-Height)などが知られている。本発明の第１の実施形態では、ＦＦＤＨを用いて最密充填レイアウトの生成を行う。ＦＦＤＨについては、「E.G.Coffman, JR., M.R.Garey, D.S.Johonson, R.E.Tarjan(Bell Lab.&Stanford Univ.) "Performance bounds for level-oriented two-dimensional packing algorithms", SIAM J. Comput, vol.9., pp808-826, No.4, 1980.」（非特許文献１）に記載がある。
【００３２】
図４は、ＦＦＤＨによるコンテンツの一例の配置方法を概略的に示すフローチャートである。この図４のフローチャートにおける各処理は、ＣＰＵ１０１により、本第１の実施形態による画像処理プログラムに従い実行される。ＦＦＤＨによれば、先ず、コンテンツを高さの大きい順にソートして、ソート順で１番目のコンテンツ（すなわち最も高さの高いコンテンツ）を、配置領域の配置開始位置に配置して、処理を開始する。以下では、説明のため、配置開始位置を配置領域の左上隅とする。
【００３３】
図４のフローチャートによる処理の開始に先立って、何らかのコンテンツ（例えばソート順で１番目のコンテンツ）が配置領域に配置されているものとする。これを最後に配置されたコンテンツとして、図４のフローチャートによる処理が開始される。ステップＳ１０で、全てのコンテンツについて配置が完了したか否かが判定され、完了していないと判定されたら、処理がステップＳ１１に移行される。一方、完了していると判断されたら、図４のフローチャートによる一連の処理が終了する。
【００３４】
ステップＳ１１で、直前に選択したコンテンツに対してソート順で次のコンテンツを選択する。次のステップＳ１２で、ステップＳ１１で選択されたコンテンツがソート順で最後のコンテンツか否かが判定される。若し、最後のコンテンツではないと判定されたら、処理はステップＳ１３に移行される。
【００３５】
ステップＳ１３では、ステップＳ１１で選択されたコンテンツが、最後に配置したコンテンツの右隣に配置可能な否かが判定される。すなわち、最後に配置したコンテンツの右端から配置領域の右端までの幅が、ステップＳ１１で選択されたコンテンツの幅以上であれば、当該選択されたコンテンツが配置可能であると判定される。若し、配置不可であると判定されたら、処理はステップＳ１０に戻され、全てのコンテンツについて配置が完了していなければソート順でさらに次のコンテンツが選択され（ステップＳ１１）、処理が繰り返される。
【００３６】
一方、ステップＳ１３で配置可能であると判定されたら、処理はステップＳ１４に移行され、最後に配置したコンテンツの右隣にステップＳ１１で選択されたコンテンツが配置される。コンテンツの配置位置を示す情報は、例えばＲＡＭ１０４に記憶される。そして、処理がステップＳ１０に戻される。
【００３７】
上述のステップＳ１２で、ステップＳ１１で選択されたコンテンツがソート順で最後のコンテンツであると判定されたら、処理はステップＳ１５に移行される。ステップＳ１５では、未配置のコンテンツのうち、ソート順が最も早い（すなわち高さが最も高い）コンテンツを、最後に配置したコンテンツに対して幅方向の左端に配置されるコンテンツの下に、配置領域に対して左詰めで配置する。コンテンツの配置位置を示す情報は、例えばＲＡＭ１０４に記憶される。そして、処理はステップＳ１１に戻される。
【００３８】
図５は、上述のようにしてＦＦＤＨにより生成した最密充填レイアウトの一例を示す。この例では、幅が「１０」の配置領域に、８個のコンテンツが配置されている。この、図３のステップＳ２において生成された最密充填レイアウトを、初期ページレイアウトと呼ぶ。
【００３９】
図５および図４のフローチャートによる処理で分かるように、ＦＦＤＨによる最密充填レイアウトでは、コンテンツの右隣には、当該コンテンツと高さが同じかまたは低いコンテンツが配置される。また、左端のコンテンツについては、コンテンツの下には当該コンテンツと高さが同じかまたは低いコンテンツが配置される。以下、配置領域の幅を持ち、左端のコンテンツの上下端で高さおよび配置領域における高さ方向の位置が規定される領域を、「ブロック」と呼び、ブロックとブロックとの区切りを、「行」と呼ぶ（図６参照）。
【００４０】
ここで、図５の例では、各コンテンツは、上端を揃えて一列に配置されている。これに限らず、左端のブロックに対して右方向に一列に配置される一連のブロックは、上下端が左端のブロックの上端および下端からなる範囲を越えなければ、他の配置でもよい。
【００４１】
なお、ＦＦＤＨでは、最適解に対する評価値が下記の式(５)のようになることが知られている。式(５)は、コンテンツの高さと幅とをそれぞれ「１」に正規化した場合の例である。また、式(５)において、値ＨalgはＦＦＤＨにより求められる高さ、値Ｈoptは最適解を表す。
Ｈalg≦１.７×Ｈopt＋１ …（５）
【００４２】
＜第１の実施形態によるページレイアウトの生成＞
次に、上述した図３のステップＳ３における、ページ毎の最終レイアウトの生成について説明する。図３のステップＳ２において、図４を用いて説明した手順に従い最密充填レイアウトによる初期ページレイアウトを生成した後に、配置領域を、幅が配置領域の幅と一致し、所定の高さを持つページ単位に分割する。このとき、図７−１に例示されるように、あるブロックがページに跨って配置されてしまうことがある。図７−１の例では、配置領域３００に配置されたブロック３０１〜３０４のうち、ブロック３０３がページを跨いで配置されてしまっている。このままでは、コンテンツが途中で分断されてしまう結果となり、好ましくない。そこで、本発明の第１の実施形態では、各ブロックがページを跨がないようにレイアウトを調整して、ページ毎の最終レイアウトを生成する。
【００４３】
本第１の実施形態では、ページを跨いで配置されたブロックを、次のページの先頭に移動させる。ここで、次のページとは、ページを跨いで配置されたブロックの上端が属するページから見た次のページをいう。すなわち、図７−１の例では、ページを跨いで配置されているブロック３０３を次ページの先頭に移動させ、当該ブロック３０３より下に配置された各ブロックも、当該ブロック３０３の移動に伴い下方に位置をずらす。以降、この処理をページ毎に順次、繰り返して行うことで、最終的には全てのコンテンツがページを跨がないように配置されたレイアウトを生成することができる。
【００４４】
図８は、本第１の実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。この図８のフローチャートにおける各処理は、ＣＰＵ１０１により、本第１の実施形態による画像処理プログラムに従い実行される。先ず、ステップＳ２０で、対象ページのページレイアウトを取得する。なお、ステップＳ２０で取得されるページレイアウトは、処理の対象となる対象ページに係るブロックからなるレイアウトである。対象ページが第１ページ目の場合は、初期ページレイアウトから対象ページのページレイアウトを取得することになる。
【００４５】
次のステップＳ２１で、対象ページのページレイアウトにページを跨るブロックがあるか否かを判定する。若し、ページを跨るブロックが無いと判定されたら、処理はステップＳ２３に移行される。
【００４６】
一方、ステップＳ２１で、対象ページのレイアウトにページを跨るブロックがあると判定されたら、処理はステップＳ２２に移行される。ステップＳ２２では、対象ページのレイアウト中においてページを跨って配置されたブロックが、対象ページの次のページの先頭に配置されるように、当該ブロックおよび当該ブロックの下に配置される各ブロックを下方へずらして再配置する。ブロックの再配置が終了すると、処理はステップＳ２３に移行される。
【００４７】
ステップＳ２３では、現在のブロックの配置状態に従い、対象ページにおけるページレイアウトを生成し、当該対象ページのページレイアウトを決定する。そして、処理はステップＳ２４に移行され、全てのページについてページレイアウトが決定されたか否かが判定される。若し、ページレイアウトが決定されていないページが存在すると判定されたら、処理はステップＳ２０に戻され、ステップＳ２３でページレイアウトが決定された次のページを対象ページとして、処理が繰り返される。
【００４８】
一方、ステップＳ２４で、全てのページについてページレイアウトが決定されたと判定されたら、一連の処理が終了される。この場合、未配置のブロックが存在しない場合に、全てのページについてページレイアウトが決定されたと判定する。
【００４９】
このように、本発明の第１の実施形態によれば、様々なサイズのコンテンツを複数ページに亘る配置領域に配置する場合に、出力ページ数がなるべく小さくなり、且つ、コンテンツがページで分断されないようなレイアウトを自動的に生成できる。
【００５０】
また、配置領域に対して様々なサイズのコンテンツを配置する場合、全てのコンテンツがページを跨がないようにページ区切りを設けることができる保証が無く、ページを跨いで配置されるコンテンツが発生する可能性が高い。すなわち、コンテンツが配置された状態でコンテンツを区切らないように幅方向の線（ページ区切り）を引くためには、幅方向に見たときに、コンテンツの上辺または下辺が揃っているなどの条件が必要となる。図９−１は、効率的な配置であっても、適当なページ区切りが見つからない例を示す。
【００５１】
本発明の第１の実施形態によれば、コンテンツを配置する際に、配置領域の幅方向については、図９−２に例示されるように、左端に配置されたコンテンツ２０１の高さからはみ出ない範囲２０２に収まるコンテンツを探索していくため、ブロック単位での配置の入れ替えが可能となる。したがって、ページ間でコンテンツが分断されないような各ページのレイアウトを、最密充填レイアウトによる初期ページレイアウトの配置から容易に決定することが可能となる。
【００５２】
＜第２の実施形態＞
次に、本発明の第２の実施形態について説明する。本第２の実施形態では、上述した第１の実施形態の処理に対し、さらに、ページに跨るブロックが存在する場合に、当該ブロック以降のブロックから対象ページ内に収まるブロックを探索する。そして、探索されたブロックとページに跨るブロックとを入れ替えて再配置を行う。これにより、効率的なページレイアウトを簡易に生成することができる。
【００５３】
図４を用いて説明した最密充填レイアウトの生成方法によれば、新しいブロックの形成時には、その時点で未配置のコンテンツの中で高さが最大のコンテンツが当該ブロックの左端に配置されることになる。そのため、ブロックは、下方に配置されるに従い高さが単調に減少（または非増加）する。したがって、あるブロックがページを跨いで配置された場合、当該ブロックの下に、当該ブロックと配置を交換することでブロックがページを跨ぐ事態を解消可能な高さのブロックが存在している可能性がある。
【００５４】
そこで、本第２の実施形態では、あるブロックがページを跨いで配置された場合、当該ブロックの下に位置するブロックから順次、対象ブロックと配置を交換した際にページ内に収まるか否かを判定する。そして、ページ内に収まる高さのブロックが存在したら、そのブロックの配置と、ページを跨るブロックの配置とを入れ替える。ブロックがページを跨いで配置される毎に同様の処理を繰り返すことで、最終的には、全てのコンテンツがページを跨がないようなページレイアウトを生成することができる。
【００５５】
図７を用いて、より具体的に説明する。図７−１に示される例では、配置領域３００に対してブロック３０１〜３０４が配置され、それらのうち、ブロック３０３がページを跨いで配置されブロック３０３に含まれるコンテンツがページ区切りで分断されてしまっている。このようなコンテンツの分断は、特にコンテンツの内容が図や表などの場合、好ましくない。
【００５６】
ここで、上述した処理により、ページを跨いで配置されたブロック３０３の直下に配置されるブロックから順次、ブロック３０３との配置交換を試みる。図７−１の例では、１ページの高さ「１１」に対して上から高さがそれぞれ「６」、「３」および「３」のブロック３０１〜３０３が配置され、ブロック３０３が高さ「１」だけページからはみ出している。ブロック３０３を取り去ると、ブロック３０３の直上のブロック３０２とページ下端との間に高さ「２」の余裕が生じる。一方、ブロック３０３の１つ下に配置されるブロック３０４は、高さが「２」であるため、ブロック３０３とブロック３０４とを入れ替えて再配置を行うことで、ブロックがページを跨ぐ事態が解消されることが分かる。
【００５７】
図７−２は、図７−１の状態から、ブロック３０３とブロック３０４とを入れ替えて再配置した場合の例を示す。対象ページに対して、ブロック３０４がページを跨がずに配置されていることが分かる。このような再配置を行うことで、効率性を保持しつつ、ブロックがページを跨いでしまう事態を解消することができる。
【００５８】
図１０は、本第２の実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。この図１０のフローチャートにおける各処理は、ＣＰＵ１０１により、本第２の実施形態による画像処理プログラムに従い実行される。先ず、ステップＳ３０で、上述したステップＳ２０と同様にして、対象ページのページレイアウトを取得する。そして、次のステップＳ３１で、対象ページのページレイアウトにページを跨るブロックがあるか否かを判定する。若し、ページを跨るブロックが無いと判定されたら、処理はステップＳ３７に移行される。
【００５９】
一方、ステップＳ３１で、対象ページのレイアウトにページを跨るブロックがあると判定されたら、処理はステップＳ３２に移行される。ステップＳ３２では、ページを跨ると判定されたブロックの直上に配置されるブロックの下端から、対象ページの下端までの高さｙが求められる。
【００６０】
次のステップＳ３３で、対象ブロックの下にさらにブロックが配置されているか否かが判定される。ステップＳ３３による判定が、ステップＳ３１でページを跨るブロックがあると判定された直後の判定であれば、当該ページを跨るブロックが対象ブロックとされる。若し、対象ブロックの直下にさらにブロックが配置されていると判定されたら、処理はステップＳ３４に移行される。
【００６１】
ステップＳ３４では、対象ブロックの直下に配置されたブロックをページを跨るブロックと入れ替えて配置した場合に、ブロックが対象ページ内に収まるか否かが判定される。例えば、ステップＳ３２で求められた高さｙと、対象ブロックの直下に配置されたブロックの高さｈbとを比較し、高さｙが高さｈb以上であれば、当該ブロックが対象ページ内に収まると判定される。
【００６２】
若し、ステップＳ３４で、高さｈbが高さｙよりも高く、対象ブロックとページを跨ぐブロックとを入れ替えて配置した際に、対象ブロックがページ内に収まらないと判定されたら、処理はステップＳ３３に戻される。そして、直前にページを跨ぐブロックとの入れ替えを試みられたブロックを新たな対象ブロックとして、当該対象ブロックの直下に配置されているブロックについて、同様にして判定が行われる。
【００６３】
一方、ステップＳ３４で、高さｈbが高さｙ以内であって、対象ブロックとページを跨ぐブロックとを入れ替えて配置した際に、対象ブロックがページ内に収まると判定されたら、処理はステップＳ３５に移行される。ステップＳ３５では、当該対象ブロックとページを跨ぐブロックとが入れ替えられて、ブロックの再配置がなされる。この場合、当該対象ブロックがページを跨ぐブロックの直上のブロックの直下に配置されると共に、ページを跨ぐブロックが対象ページの次ページの先頭に配置される。そして、このブロックの直下から、当該対象ブロックの直下から配置されていた各ブロックが、順序を変えずに配置される。ステップＳ３５でブロックの再配置が行われると、処理はステップＳ３７に移行される。
【００６４】
上述のステップＳ３３で、対象ブロックの下にブロックが配置されていないと判定されたら、処理はステップＳ３６に移行される。この場合には、対象ページ内に収まるようにページを跨ぐブロックと入れ替え可能なブロックが存在しないことを意味する。そこで、ステップＳ３６では、当該ページを跨ぐブロックを対象ページの次ページの先頭に配置されるように、当該ブロックおよび当該ブロックの下に配置される各ブロックを下方にずらして再配置する。ブロックの再配置が終了すると、処理はステップＳ３７に移行される。
【００６５】
ステップＳ３７では、現在のブロックの配置状態に従い、対象ページにおけるページレイアウトを生成し、当該対象ページのページレイアウトを決定する。そして、処理はステップＳ３８に移行され、全てのページについてページレイアウトが決定されたか否かが判定される。若し、ページレイアウトが決定されていないページが存在すると判定されたら、処理はステップＳ３０に戻され、ステップＳ３７でページレイアウトが決定された次のページを対象ページとして、処理が繰り返される。
【００６６】
一方、ステップＳ３８で、全てのページについてページレイアウトが決定されたと判定されたら、一連の処理が終了される。この場合、未配置のブロックが存在しない場合に、全てのページについてページレイアウトが決定されたと判定する。
【００６７】
このように、本発明の第２の実施形態によれば、様々なサイズのコンテンツを複数ページに亘る配置領域に配置する場合に、出力ページ数がなるべく小さくなり、且つ、コンテンツがページで分断されないようなレイアウトを自動的に生成できる。
【００６８】
また、本第２の実施形態によれば、最密充填レイアウト生成により、新しいブロックの形成時には、その時点で未配置のコンテンツの中で高さが最大のコンテンツが当該ブロックの左端に配置されることになる。そのため、ブロックは、下方に配置されるに従い高さが単調に減少（または非増加）する。したがって、ブロックがページを跨いで配置されてしまった場合、直下のブロックから順次、ブロックの高さを調べていき、ページ内に収まる高さのブロックがあれば、そのブロックとページを跨ぐブロックとを入れ替えて再配置を行うことで、簡易に効率的なページレイアウトを生成することができる。
【００６９】
＜第３の実施形態＞
次に、本発明の第３の実施形態について説明する。本第３の実施形態では、上述した第１または第２の実施形態で生成された最終的なページレイアウトに対して、さらに調整を加えることで、より好ましいページレイアウトを生成する。この場合、ブロック自体の位置を調整する方法と、ブロック内でコンテンツの位置を調整する方法とが考えられる。
【００７０】
先ず、第１の方法として、ブロック自体の位置をページ内で調整する方法について説明する。すなわち、上述した第１および第２の実施形態により生成されるページレイアウトでは、最終ページに対して１つのブロックのみが配置され、そのページの残り全ての領域が空白という事態が起こり得る。そこで、上述した第１または第２の実施形態で説明した方法でページレイアウトを生成し、全ページ数が決定された後に、ブロック自体の位置をページ内およびページ間で調整する。
【００７１】
図１１は、ブロック自体の位置を調整する処理を示す一例のフローチャートである。この図１１のフローチャートにおける各処理は、ＣＰＵ１０１により、本第３の実施形態による画像処理プログラムに従い実行される。先ず、ステップＳ４０で、図４を用いて説明したようにして最密充填レイアウトを取得し、次のステップＳ４１で、最密充填レイアウトから初期ページレイアウトを生成する。この初期ページレイアウトでは、既に説明したように、ページを跨いで配置されるブロックが存在する可能性がある。次のステップＳ４２で、初期ページレイアウトに基づきブロック単位で再配置を行い、ページを跨ぐブロックが全ページに亘って存在しないようにする。ステップＳ４２での処理は、図８または図９を用いて説明した手順に従い、ページを跨ぐブロックを次のページの先頭に移動させたり、他のブロックとの入れ替えを行うことで、ブロックがページを跨いで配置される事態を解消する。
【００７２】
ステップＳ４２までの処理により全ページのレイアウトが決定し、レイアウトに必要な全ページ数が確定すると、処理はステップＳ４３に移行される。ステップＳ４３では、ブロックの位置調整を行う。
【００７３】
ステップＳ４３での処理として、例えばページ下部の空白部分のページ間でのバラツキが小さくなるように、ブロックを再配置することが考えられる。一例として、ステップＳ４２の処理が終了した時点で、全ブロックの高さの合計をページ数で除して、１ページに配置されるブロックの合計高さの平均値ｈavgを算出する。そして、最終ページに配置されるブロックの合計高さが平均値ｈavgに近くなるように、各ページから１つずつ、ブロックを最終ページに移動させる。
【００７４】
また、ページ内でブロックの再配置を行ってページ毎のレイアウトを調整することもできる。例えば、ページ内の下部に生じた空白を、ブロック間のマージンとして割り当てることが考えられる。一例として、下記の式（６）に例示されるように、各ページにおいて、下部の空白領域の高さＭをブロック数ｎ−１で除して、ブロック間に対して等分にブロック間マージンＢＭを割り当てる。
ＢＭ＝Ｍ／(ｎ−１) …（６）
【００７５】
勿論、このページ内でのブロック再配置と、上述したページ間でのブロックの移動とを組み合わせて実行してもよい。すなわち、ページ下部の空白部分のページ間でのバラツキが小さくなるようにブロックを再配置した後に、ページ内でのブロックの再配置を行い空白部分を均一化する。
【００７６】
次に、第２の方法として、ブロック内でコンテンツの位置を調整する方法について説明する。ブロック内でコンテンツを移動させても、ブロック自体を移動させない限りはページ数が増加することはない。そこで、ブロック内で例えば水平方向にコンテンツを移動させて、左右のバランスを調整する方法が考えられる。このとき、ブロック内に配置されるコンテンツのサイズや形状（アスペクト比）などを考慮してコンテンツの移動を行うと好ましい。
【００７７】
図１２は、ブロック内でコンテンツの位置を調整する処理を示す一例のフローチャートである。この図１２のフローチャートにおける各処理は、ＣＰＵ１０１により、本第３の実施形態による画像処理プログラムに従い実行される。先ず、ステップＳ５０で、図４を用いて説明したようにして最密充填レイアウトを取得し、次のステップＳ５１で、最密充填レイアウトから初期ページレイアウトを生成する。この初期ページレイアウトでは、既に説明したように、ページを跨いで配置されるブロックが存在する可能性がある。次のステップＳ５２で、初期ページレイアウトに基づきブロック単位で再配置を行い、ページを跨ぐブロックが全ページに亘って存在しないようにする。ステップＳ５２での処理は、図８または図９を用いて説明した手順に従い、ページを跨ぐブロックを次のページの先頭に移動させたり、他のブロックとの入れ替えを行うことで、ブロックがページを跨いで配置される事態を解消する。
【００７８】
ステップＳ５２までの処理により全ページのレイアウトが決定すると、処理がステップＳ５３に移行される。ステップＳ５３では、ブロック内でのコンテンツの位置調整を行う。
【００７９】
ステップＳ５３において、ブロックの視覚的な中心や、コンテンツの視覚的な中心は、例えば「Steven J.Harrington, J.Femando Naveda, Rhys Price Jones, Paul Roetling, Nishant Thakker, "Aesthetic Measures for Automated Document Layout"」（非特許文献２）に示される方法で算出可能である。例えば、ブロック内コンテンツ全体の水平方向の位置は下記の式(７)〜式(９)で、ブロック内コンテンツの左右のバランス度は下記の式（１０）でそれぞれ算出することができる。
【数１】
【数２】
【数３】
【数４】
【００８０】
なお、上述の式（７）〜式（１０）で用いられる各変数の意味は、次の通りである。
(ｘi,ｙi)：コンテンツiのｘｙ座標
(ｘc,ｙc)：ブロックの視覚的な中心
Ｍi：コンテンツの視覚的中心
(ｄx,ｄy)：ブロックの視覚的中心からの最大距離
ｄh：ブロックの高さ
【００８１】
また、ブロック内ではコンテンツを自由に移動させることができるため、例えば、ステップＳ５３において、ブロック内のコンテンツの中心位置がブロックの中央に近付くように、コンテンツの位置調整を行うこともできる。ブロック内コンテンツの中心位置は例えば下記の式（１１）および式（１２）により、バランス度は式（１３）により、それぞれ算出することができる。
【数５】
【数６】
【数７】
【００８２】
ブロックおよびコンテンツのレイアウト調整方法は、上述の例に限定されるものではない。例えば、上述した非特許文献２に記載されている幾つかの指標を用いてブロック間のコンテンツの配置を調整することもできる。
【００８３】
本発明に適用可能な最密充填レイアウトでは、コンテンツは基本的に左詰め（または右詰め）で配置される。一方、レイアウトとしては、幅方向のバランスがとれた方が一般的に見やすいとされている。本第３の実施形態によれば、ブロック内部でコンテンツの左右のバランスを調整する事で、レイアウトの効率性は保持しつつ、より美しいレイアウトを実現することができる。
【００８４】
また、本発明に適用可能な最密充填レイアウトでは、ブロック単位で見ると、基本的にコンテンツが左上詰め（または右上詰め）で配置される。一方、レイアウトとしては、コンテンツの重心がブロックの中央付近に位置していた方がバランスが良く、一般的に見やすいとされている。本第３の実施形態によれば、ブロック内部でコンテンツの重心位置を調整することで、レイアウトの効率性を保持しつつ、より美しいレイアウトを実現することができる。
【００８５】
＜第４の実施形態＞
次に、本発明の第４の実施形態について説明する。本第４の実施形態では、コンテンツに対する倍率の可変量や、アスペクトの可変量を取得し、これら取得された可変量に基づきコンテンツのサイズを変更することで、ブロックをページを跨がずに配置する。
【００８６】
図１３は、本第４の実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。この図１３のフローチャートにおける各処理は、ＣＰＵ１０１により、本第４の実施形態による画像処理プログラムに従い実行される。
【００８７】
この図１３のフローチャートは、例えば述した図８のフローチャートにおけるステップＳ２１や、図９のフローチャートにおけるステップＳ３１の判定において、ページに跨るブロックがあると判定された場合の処理に対応する。ページに跨るブロックがあると判定されると、ステップＳ６０において、当該ブロックに含まれるコンテンツに対する倍率およびアスペクト比の少なくとも一方の可変量を取得する。
【００８８】
可変量は、例えば画像処理装置１００に対するユーザ操作により、コンテンツ毎に指定することができる。これに限らず、可変量を予め画像処理プログラムにより指定するようにしてもよい。また、可変量は、ブロックに対する可変量であってもよい。さらに、コンテンツがテキストの場合は可変量を小さく、画像の場合は可変量を大きくといったように、可変量をコンテンツの種類に応じて指定するようにしてもよい。
【００８９】
なお、コンテンツがテキストであるか画像であるかは、例えばテキストが画像として入力される場合には、後述する第５の実施形態で説明する解析処理によって、判定することが考えられる。テキストがテキストデータで入力される場合には、データの種類に基づいて判定可能であることはいうまでもない。
【００９０】
可変量が取得されると、処理はステップＳ６１に移行され、可変量の範囲内でコンテンツまたはブロックを変形させた場合に、当該ブロックがページ内に収まるか否かが判定される。例えば、指定された可変量の範囲内でコンテンツを変形させ、それに伴いブロックを変形させて高さを調整することで当該ブロックがページ内に収まるか否かが判定される。若し、変形により当該ブロックがページ内に収まると判定されたら、処理はステップＳ６２に移行され、ページ内に収まるように当該ブロックの高さを調整する。
【００９１】
一方、ステップＳ６１で、可変量の範囲内で変形を行っても当該ブロックがページ内に収まらない、すなわち、当該ブロックがページを跨いでしまうと判定されたら、処理はステップＳ６３に移行される。そして、当該ブロックが次のページの先頭に配置され、それに伴い当該ブロックの下に配置されるブロックの位置も下方にずらされる。
【００９２】
＜第５の実施形態＞
次に、本発明の第５の実施形態について説明する。本第５の実施形態では、画像処理装置１００に対してコンテンツの内容を解析するコンテンツ解析機能を持たせる。そして、配置領域に配置するコンテンツの内容をコンテンツ解析機能によって解析し、解析結果に基づきブロックの入れ替えなどを行う。
【００９３】
コンテンツ解析機能は、例えばＣＰＵ１０１上で動作するプログラムとして実現される。コンテンツの解析方法としては、既存の技術を適用することができる。コンテンツの解析結果として得られる情報としては、例えば下記のような情報が考えられる。
分類：テキスト／イメージ
視覚情報：色／密度など
構造情報：見出し／タイトル／本文など
意味情報：コンテンツ間やブロック間の相関／重要度
【００９４】
先ず、入力されたコンテンツがテキストおよびイメージの何れであるかを解析する。例えば、入力された画像データに対して文字検出を行い、検出結果に基づきコンテンツがテキストおよびイメージの何れであるかを判定する。
【００９５】
なお、テキストは、テキストデータとして入力することもできる。この場合、表示範囲などテキストのレイアウトに関する情報が共に入力されるものとする。これに限らず、画像処理装置１００側において、入力されたテキストデータに対して表示範囲を設定するようにしてもよい。
【００９６】
コンテンツがイメージであれば、例えば画素毎の色情報に基づきＲＧＢ値のヒストグラムを作成して色に関する解析を行うことが考えられる。また例えば、画像データの空間周波数を解析することで、画像の密度に関する情報を取得することが考えられる。
【００９７】
コンテンツデータがテキストであれば、テキストの構造を解析し、見出し、タイトルおよび本文などをそれぞれ抽出することが考えられる。例えば、検出された文字（文字群）の位置や大きさ、装飾などに基づき、テキストの構造を解析することが考えられる。また、テキストデータがＨＴＭＬ(Hyper Text Markup Language)やＸＭＬ(Extensible Markup Language)といったマークアップ言語で記述されたテキストデータとして入力されている場合は、タグに基づき構造解析を行うことができる。これに限らず、テキストデータに用いられている単語を抽出してテキストの意味解析を行うことも考えられる。
【００９８】
上述した視覚情報や構造情報の解析結果に基づき、コンテンツ間の相関やコンテンツの重要度を解析することができる。また、コンテンツ毎の解析結果を用いて、それぞれコンテンツが１または複数配置されたブロック間での相関やブロックの重要度を解析することも可能である。
【００９９】
図１４は、本第５の実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。この図１４のフローチャートにおける各処理は、ＣＰＵ１０１により、本第５の実施形態による画像処理プログラムに従い実行される。この図１４のフローチャートにおいては、ページを跨ぐブロックがあった場合に、上述した解析結果を行って当該ブロックの直上に配置されるブロックと、当該ブロックより下方に配置されるブロックとの相関を順次、求める。そして、相関を示す相関値が予め定めた閾値ｔｈより高いと判定されたブロックとの配置の入れ替えを行う。
【０１００】
先ず、ステップＳ７０で、上述したステップＳ２０と同様にして、対象ページのページレイアウトを取得する。そして、次のステップＳ７１で、対象ページのページレイアウトにページを跨るブロックがあるか否かを判定する。若し、ページを跨るブロックが無いと判定されたら、処理はステップＳ７９に移行される。
【０１０１】
一方、ステップＳ７１で、対象ページのレイアウトにページを跨るブロックがあると判定されたら、処理はステップＳ７２に移行される。ステップＳ７２では、ページを跨ると判定されたブロックの直上に配置されるブロックの下端から、対象ページの下端までの高さｙが求められる。
【０１０２】
次のステップＳ７３で、対象ブロックの下にさらにブロックが配置されているか否かが判定される。ステップＳ７３による判定が、ステップＳ７１でページを跨るブロックがあると判定された直後の判定であれば、当該ページを跨るブロックが対象ブロックとされる。若し、対象ブロックの直下にさらにブロックが配置されていると判定されたら、処理はステップＳ７４に移行される。
【０１０３】
ステップＳ７４では、対象ブロックの直下に配置されたブロックをページを跨るブロックと入れ替えて配置した場合に、ブロックが対象ページ内に収まるか否かが判定される。例えば、ステップＳ７２で求められた高さｙと、対象ブロックの直下に配置されたブロックの高さｈbとを比較し、高さｙが高さｈb以上であれば、当該ブロックが対象ページ内に収まると判定される。
【０１０４】
若し、ステップＳ７４で、高さｈbが高さｙよりも高く、対象ブロックとページを跨ぐブロックとを入れ替えて配置した際に、対象ブロックがページ内に収まらないと判定されたら、処理はステップＳ７３に戻される。そして、直前にページを跨ぐブロックとの入れ替えを試みられたブロックを新たな対象ブロックとして、当該対象ブロックの直下に配置されているブロックについて、同様にして判定が行われる。
【０１０５】
一方、ステップＳ７４で、高さｈbが高さｙ以内であって、対象ブロックとページを跨ぐブロックとを入れ替えて配置した際に、対象ブロックがページ内に収まると判定されたら、処理はステップＳ７５に移行される。ステップＳ７５では、当該対象ブロックと、ページを跨ぐブロックの直上に配置されるブロックとの相関が算出される。そして、次のステップＳ７６で、この相関が予め決められた閾値ｔｈよりも高いか否かが判定される。
【０１０６】
若し、算出された相関が閾値ｔｈよりも高いと判定されたら、処理はステップＳ７７に移行され、当該対象ブロックとページを跨ぐブロックとが入れ替えられて、ブロックの再配置がなされる。この場合、当該対象ブロックがページを跨ぐブロックの直上のブロックの直下に配置されると共に、ページを跨ぐブロックが対象ページの次ページの先頭に配置される。そして、このブロックの直下から、当該対象ブロックの直下から配置されていたブロックが、順序を変えずに配置される。ステップＳ７７でブロックの再配置が行われると、処理はステップＳ７９に移行される。
【０１０７】
一方、ステップＳ７６で、相関が閾値ｔｈ以下であると判定されたら、処理はステップＳ７３に戻され、次のブロックについて処理が繰り返される。
【０１０８】
上述のステップＳ７３で、対象ブロックの下にブロックが配置されていないと判定されたら、処理はステップＳ７８に移行される。ステップＳ７８では、当該ページを跨ぐブロックを対象ページの次ページの先頭に配置されるように、当該ブロックおよび当該ブロックの下に配置される各ブロックを下方にずらして再配置する。ブロックの再配置が終了すると、処理はステップＳ７９に移行される。
【０１０９】
ステップＳ７９では、現在のブロックの配置状態に従い、対象ページにおけるページレイアウトを生成する。そして、処理はステップＳ８０に移行され、全てのページについてページレイアウトが決定されたか否かが判定される。若し、ページレイアウトが決定されていないページが存在すると判定されたら、処理はステップＳ７０に戻され、ステップＳ７９でページレイアウトが決定された次のページを対象ページとして、処理が繰り返される。
【０１１０】
一方、ステップＳ８０で、全てのページについてページレイアウトが決定されたと判定されたら、一連の処理が終了される。この場合、未配置のブロックが存在しない場合に、全てのページについてページレイアウトが決定されたと判定する。
【０１１１】
なお、上述では、ステップＳ７６において相関が閾値ｔｈよりも高いと判定されたブロックを直接的に入れ替えに用いているが、これはこの例に限定されない。例えば、ページを跨ぐブロックの下に配置され、且つ、ページ内に収まると判定された対象ブロックが複数存在する場合も考えられる。このような場合に、当該対象ブロック全てについて、ページを跨ぐブロックの直上のブロックとの相関を求め、最も相関の高いブロックを選択して入れ替えに用いてもよい。
【０１１２】
このように、本第５の実施形態では、ステップＳ７４でブロックの高さｈに基づきブロックの入れ替えが可能だと判断されても、入れ替えられたブロックと当該ブロックの直上に配置されるブロックとの相関が低いと判定されると、その入れ替えを行わない。これにより、ブロックの入れ替えによって内容的に無関係のブロックが配置されることが抑制される。
【０１１３】
なお、上述した各実施形態による画像処理装置１００で実行される画像処理プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ(Compact Disk)、ＤＶＤ(Digital Versatile Disk)等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【０１１４】
また、上述した各実施形態による画像処理装置１００で実行される画像処理プログラムを、インターネットなどのネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また、上述した各実施形態による画像処理装置１００で実行される画像処理プログラムをインターネットなどのネットワーク経由で提供または配布するように構成しても良い。
【０１１５】
また、上述した各実施形態による画像処理装置１００で実行される画像処理プログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。
【０１１６】
上述した各実施形態による画像処理装置１００で実行される画像処理プログラムは、上述した最密充填レイアウトを生成するモジュールと、最密充填レイアウトに基づき各ページのレイアウトを生成するモジュールとを含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵ１０１（プロセッサ）が例えばＨＤＤ１０５から画像処理プログラムを読み出して実行することにより、上述の各モジュールが主記憶装置（ＲＡＭ１０４）上にロードされ、最密充填レイアウト生成モジュールと、ページレイアウト生成モジュールとが主記憶装置上に生成されるようになっている。
【０１１７】
なお、上述では、本発明に適用可能な画像処理装置１００が一般的なコンピュータとして構成されるように説明したが、これはこの例に限定されない。例えば、本発明による画像処理装置１００は、コピー機能、プリンタ機能、スキャナ機能およびファクシミリ機能のうち少なくとも２つの機能を有する複合機に適用することができる。また、本発明による画像処理装置１００は、複写機、プリンタ、スキャナ装置、ファクシミリ装置などの画像形成装置であれば何れにも適用することができる。
【符号の説明】
【０１１８】
１１ 画像入力部
１２ 画像出力部
１００ 画像処理装置
１０１ ＣＰＵ
１０２ Ｉ／Ｏ部
１０５ ＨＤＤ
２００ 配置領域
【先行技術文献】
【特許文献】
【０１１９】
【特許文献１】特許第４０４７３２６号公報
【特許文献２】特開２００５−２７５６８２公報
【特許文献３】特開２００６−２５９８１９公報
【特許文献４】特開２００７−１５０６９８公報
【特許文献５】特開２００７−１１５７７公報
【特許請求の範囲】
【請求項１】
幅と、所定の高さ毎に順序付けて区切られた領域からなるページ領域とが定義される配置領域に対して複数のコンテンツを配置して出力する画像処理方法であって、
前記配置領域の高さ方向に対して、コンテンツを、幅方向に一列に配置されるコンテンツのうち高さが最大のコンテンツの上端および下端からなる範囲内に配置すると共に、前記配置領域の幅を持ち、該高さが最大のコンテンツの上端および下端で高さが定義されるブロックを、前記配置領域の高さ方向の一方の端を先頭として、隣接する該ブロックと接するように順次配置し、
前記配置領域の幅方向に対して、コンテンツを、隣接するコンテンツと接すると共に該配置領域の幅を超えず、且つ、全コンテンツが配置された際の前記ブロックによる全体の高さが近似的に最小となるように配置する最密充填レイアウト生成ステップと、
前記最密充填レイアウト生成ステップにより、前記ブロックが前記ページ領域を跨いで配置されている場合に、該ページ領域を跨いだ該ブロックを、該ブロックが跨ぐページ領域のうち順序が後以降のページ領域に移動させてブロックの再配置を行う最終レイアウト生成ステップと
を有する
ことを特徴とする画像処理方法。
【請求項２】
前記最密充填レイアウト生成ステップは、
前記コンテンツを高さの高い順に順序付ける順序付けステップと、
配置対象の全コンテンツのうち前記順序付けステップにより最も高さが高いと順序付けられたコンテンツを、前記配置領域の幅方向の一方の端と、高さ方向の一方の端とに接するように配置する第１の配置ステップと、
前記順序付けステップにより未配置のコンテンツのうち最も高さが高いと順序付けられたコンテンツを、直前に配置されたコンテンツが属する前記ブロック内に他のコンテンツと重ならずに配置可能か否かを判定する判定ステップと、
前記判定ステップにより配置可能であると判定された場合に、前記未配置のコンテンツのうち最も高さが高いと順序付けされたコンテンツを前記直前に配置されたコンテンツが属するブロック内に該直前に配置されたコンテンツに接するように配置し、
前記判定ステップにより配置可能ではないと判定された場合に、前記未配置のコンテンツのうち最も高さが高いと順序付けされたコンテンツを、前記直前に配置されたコンテンツが属するブロックに接し、且つ、前記幅方向の一方の端に接するように配置する第２の配置ステップと
を有する
ことを特徴とする請求項１記載の画像処理方法。
【請求項３】
前記最終レイアウト生成ステップは、
前記ページ領域を跨いだブロックを、該ブロックが跨ぐページ領域のうち順序が後のページ領域の先頭に移動させると共に、該移動に伴い該ブロックより後ろに配置されるブロックの位置をずらしてブロックの再配置を行う
ことを特徴とする請求項１または請求項２に記載の画像処理方法。
【請求項４】
前記最終レイアウト生成ステップは、
前記ページ領域を跨いだブロックの後ろに配置されたブロックから、高さが該ページ領域を跨いだブロックの直上に配置されたブロックの下端と、該ページ領域の下端との間による高さ以下のブロックを検索し、検索された該ブロックと、該ページ領域を跨いだブロックとを入れ替えてブロックの再配置を行う
ことを特徴とする請求項１または請求項２に記載の画像処理方法。
【請求項５】
コンテンツの内容を解析してコンテンツ間の相関を求める解析ステップをさらに有し、
前記最終レイアウト生成ステップは、
前記解析ステップで求められた、前記検索されたブロックと前記ページ領域を跨いだブロックとの前記相関に基づき前記入れ替えを行うブロックを選択する
ことを特徴とする請求項４に記載の画像処理方法。
【請求項６】
前記最終レイアウト生成ステップは、
前記検索によって複数のブロックが得られた場合に、検索された該複数のブロックのうち、前記解析ステップで求められた、前記ページ領域を跨いだブロックとの相関が最も高いブロックを、前記入れ替えを行うブロックに決定する
ことを特徴とする請求項５に記載の画像処理方法。
【請求項７】
前記最終レイアウト生成ステップは、
コンテンツを該コンテンツに指定された範囲内で変形させる変形ステップを有し、
前記ページ領域を跨いだブロック内のコンテンツを前記変形ステップにより前記範囲内で変形させ、該コンテンツの変形に伴い該ブロックを変形させて該ブロックの高さの調整を行ったときに、該高さの調整後の該ページ領域を跨いだブロックが前記ページ領域に収まらない場合に、該ページ領域を跨いだブロックの前記移動を行う
ことを特徴とする請求項１乃至請求項６の何れか１項に記載の画像処理方法。
【請求項８】
前記変形ステップが行う前記変形は、前記コンテンツに対する縮小処理である
ことを特徴とする請求項７に記載の画像処理方法。
【請求項９】
前記変形ステップが行う前記変形は、前記コンテンツのアスペクト比の変更処理である
ことを特徴とする請求項７に記載の画像処理方法。
【請求項１０】
前記最終レイアウト生成ステップは、
前記ブロック内でコンテンツの幅方向の配置を調整するステップを有する
ことを特徴とする請求項１乃至請求項９の何れか１項に記載の画像処理方法。
【請求項１１】
前記最終レイアウト生成ステップは、
前記ページ領域内にブロックが配置されない空白領域を前記ページ領域のそれぞれで均一化するように、前記ブロックを該ページ領域間で移動させるステップをさらに有する
ことを特徴とする請求項１乃至請求項１０の何れか１項に記載の画像処理装置。
【請求項１２】
前記最終レイアウト生成ステップは、
前記ページ領域の再下段に配置されるブロックの下辺と該ページ領域の下辺との間の空白部を分割して、該ページ領域内に配置される各ブロック間にそれぞれ配置するステップをさらに有する
ことを特徴とする請求項１乃至請求項１０の何れか１項に記載の画像処理方法。
【請求項１３】
幅と、所定の高さ毎に順序付けて区切られた領域からなるページ領域とが定義される配置領域に対して複数のコンテンツを配置して出力する画像処理装置であって、
前記配置領域の高さ方向に対して、コンテンツを、幅方向に一列に配置されるコンテンツのうち高さが最大のコンテンツの上端および下端からなる範囲内に配置すると共に、前記配置領域の幅を持ち、該高さが最大のコンテンツの上端および下端で高さが定義されるブロックを、前記配置領域の高さ方向の一方の端を先頭として、隣接する該ブロックと接するように順次配置し、
前記配置領域の幅方向に対して、コンテンツを、隣接するコンテンツと接すると共に該配置領域の幅を超えず、且つ、全コンテンツが配置された際の前記ブロックによる全体の高さが近似的に最小となるように配置する最密充填レイアウト生成手段と、
前記最密充填レイアウト生成手段により、前記ブロックが前記ページ領域を跨いで配置されている場合に、該ページ領域を跨いだ該ブロックを、該ブロックが跨ぐページ領域のうち順序が後以降のページ領域に移動させてブロックの再配置を行う最終レイアウト生成手段と
を有する
ことを特徴とする画像処理装置。
【請求項１４】
幅と、所定の高さ毎に順序付けて区切られた領域からなるページ領域とが定義される配置領域の高さ方向に対して、コンテンツを、幅方向に一列に配置されるコンテンツのうち高さが最大のコンテンツの上端および下端からなる範囲内に配置すると共に、前記配置領域の幅を持ち、該高さが最大のコンテンツの上端および下端で高さが定義されるブロックを、前記配置領域の高さ方向の一方の端を先頭として、隣接する該ブロックと接するように順次配置し、
前記配置領域の幅方向に対して、コンテンツを、隣接するコンテンツと接すると共に該配置領域の幅を超えず、且つ、全コンテンツが配置された際の前記ブロックによる全体の高さが近似的に最小となるように配置する最密充填レイアウト生成ステップと、
前記最密充填レイアウト生成ステップにより、前記ブロックが前記ページ領域を跨いで配置されている場合に、該ページ領域を跨いだ該ブロックを、該ブロックが跨ぐページ領域のうち順序が後以降のページ領域に移動させてブロックの再配置を行う最終レイアウト生成ステップと
をコンピュータに実行させるプログラム。
【請求項１５】
請求項１４に記載のプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【請求項１】
幅と、所定の高さ毎に順序付けて区切られた領域からなるページ領域とが定義される配置領域に対して複数のコンテンツを配置して出力する画像処理方法であって、
前記配置領域の高さ方向に対して、コンテンツを、幅方向に一列に配置されるコンテンツのうち高さが最大のコンテンツの上端および下端からなる範囲内に配置すると共に、前記配置領域の幅を持ち、該高さが最大のコンテンツの上端および下端で高さが定義されるブロックを、前記配置領域の高さ方向の一方の端を先頭として、隣接する該ブロックと接するように順次配置し、
前記配置領域の幅方向に対して、コンテンツを、隣接するコンテンツと接すると共に該配置領域の幅を超えず、且つ、全コンテンツが配置された際の前記ブロックによる全体の高さが近似的に最小となるように配置する最密充填レイアウト生成ステップと、
前記最密充填レイアウト生成ステップにより、前記ブロックが前記ページ領域を跨いで配置されている場合に、該ページ領域を跨いだ該ブロックを、該ブロックが跨ぐページ領域のうち順序が後以降のページ領域に移動させてブロックの再配置を行う最終レイアウト生成ステップと
を有する
ことを特徴とする画像処理方法。
【請求項２】
前記最密充填レイアウト生成ステップは、
前記コンテンツを高さの高い順に順序付ける順序付けステップと、
配置対象の全コンテンツのうち前記順序付けステップにより最も高さが高いと順序付けられたコンテンツを、前記配置領域の幅方向の一方の端と、高さ方向の一方の端とに接するように配置する第１の配置ステップと、
前記順序付けステップにより未配置のコンテンツのうち最も高さが高いと順序付けられたコンテンツを、直前に配置されたコンテンツが属する前記ブロック内に他のコンテンツと重ならずに配置可能か否かを判定する判定ステップと、
前記判定ステップにより配置可能であると判定された場合に、前記未配置のコンテンツのうち最も高さが高いと順序付けされたコンテンツを前記直前に配置されたコンテンツが属するブロック内に該直前に配置されたコンテンツに接するように配置し、
前記判定ステップにより配置可能ではないと判定された場合に、前記未配置のコンテンツのうち最も高さが高いと順序付けされたコンテンツを、前記直前に配置されたコンテンツが属するブロックに接し、且つ、前記幅方向の一方の端に接するように配置する第２の配置ステップと
を有する
ことを特徴とする請求項１記載の画像処理方法。
【請求項３】
前記最終レイアウト生成ステップは、
前記ページ領域を跨いだブロックを、該ブロックが跨ぐページ領域のうち順序が後のページ領域の先頭に移動させると共に、該移動に伴い該ブロックより後ろに配置されるブロックの位置をずらしてブロックの再配置を行う
ことを特徴とする請求項１または請求項２に記載の画像処理方法。
【請求項４】
前記最終レイアウト生成ステップは、
前記ページ領域を跨いだブロックの後ろに配置されたブロックから、高さが該ページ領域を跨いだブロックの直上に配置されたブロックの下端と、該ページ領域の下端との間による高さ以下のブロックを検索し、検索された該ブロックと、該ページ領域を跨いだブロックとを入れ替えてブロックの再配置を行う
ことを特徴とする請求項１または請求項２に記載の画像処理方法。
【請求項５】
コンテンツの内容を解析してコンテンツ間の相関を求める解析ステップをさらに有し、
前記最終レイアウト生成ステップは、
前記解析ステップで求められた、前記検索されたブロックと前記ページ領域を跨いだブロックとの前記相関に基づき前記入れ替えを行うブロックを選択する
ことを特徴とする請求項４に記載の画像処理方法。
【請求項６】
前記最終レイアウト生成ステップは、
前記検索によって複数のブロックが得られた場合に、検索された該複数のブロックのうち、前記解析ステップで求められた、前記ページ領域を跨いだブロックとの相関が最も高いブロックを、前記入れ替えを行うブロックに決定する
ことを特徴とする請求項５に記載の画像処理方法。
【請求項７】
前記最終レイアウト生成ステップは、
コンテンツを該コンテンツに指定された範囲内で変形させる変形ステップを有し、
前記ページ領域を跨いだブロック内のコンテンツを前記変形ステップにより前記範囲内で変形させ、該コンテンツの変形に伴い該ブロックを変形させて該ブロックの高さの調整を行ったときに、該高さの調整後の該ページ領域を跨いだブロックが前記ページ領域に収まらない場合に、該ページ領域を跨いだブロックの前記移動を行う
ことを特徴とする請求項１乃至請求項６の何れか１項に記載の画像処理方法。
【請求項８】
前記変形ステップが行う前記変形は、前記コンテンツに対する縮小処理である
ことを特徴とする請求項７に記載の画像処理方法。
【請求項９】
前記変形ステップが行う前記変形は、前記コンテンツのアスペクト比の変更処理である
ことを特徴とする請求項７に記載の画像処理方法。
【請求項１０】
前記最終レイアウト生成ステップは、
前記ブロック内でコンテンツの幅方向の配置を調整するステップを有する
ことを特徴とする請求項１乃至請求項９の何れか１項に記載の画像処理方法。
【請求項１１】
前記最終レイアウト生成ステップは、
前記ページ領域内にブロックが配置されない空白領域を前記ページ領域のそれぞれで均一化するように、前記ブロックを該ページ領域間で移動させるステップをさらに有する
ことを特徴とする請求項１乃至請求項１０の何れか１項に記載の画像処理装置。
【請求項１２】
前記最終レイアウト生成ステップは、
前記ページ領域の再下段に配置されるブロックの下辺と該ページ領域の下辺との間の空白部を分割して、該ページ領域内に配置される各ブロック間にそれぞれ配置するステップをさらに有する
ことを特徴とする請求項１乃至請求項１０の何れか１項に記載の画像処理方法。
【請求項１３】
幅と、所定の高さ毎に順序付けて区切られた領域からなるページ領域とが定義される配置領域に対して複数のコンテンツを配置して出力する画像処理装置であって、
前記配置領域の高さ方向に対して、コンテンツを、幅方向に一列に配置されるコンテンツのうち高さが最大のコンテンツの上端および下端からなる範囲内に配置すると共に、前記配置領域の幅を持ち、該高さが最大のコンテンツの上端および下端で高さが定義されるブロックを、前記配置領域の高さ方向の一方の端を先頭として、隣接する該ブロックと接するように順次配置し、
前記配置領域の幅方向に対して、コンテンツを、隣接するコンテンツと接すると共に該配置領域の幅を超えず、且つ、全コンテンツが配置された際の前記ブロックによる全体の高さが近似的に最小となるように配置する最密充填レイアウト生成手段と、
前記最密充填レイアウト生成手段により、前記ブロックが前記ページ領域を跨いで配置されている場合に、該ページ領域を跨いだ該ブロックを、該ブロックが跨ぐページ領域のうち順序が後以降のページ領域に移動させてブロックの再配置を行う最終レイアウト生成手段と
を有する
ことを特徴とする画像処理装置。
【請求項１４】
幅と、所定の高さ毎に順序付けて区切られた領域からなるページ領域とが定義される配置領域の高さ方向に対して、コンテンツを、幅方向に一列に配置されるコンテンツのうち高さが最大のコンテンツの上端および下端からなる範囲内に配置すると共に、前記配置領域の幅を持ち、該高さが最大のコンテンツの上端および下端で高さが定義されるブロックを、前記配置領域の高さ方向の一方の端を先頭として、隣接する該ブロックと接するように順次配置し、
前記配置領域の幅方向に対して、コンテンツを、隣接するコンテンツと接すると共に該配置領域の幅を超えず、且つ、全コンテンツが配置された際の前記ブロックによる全体の高さが近似的に最小となるように配置する最密充填レイアウト生成ステップと、
前記最密充填レイアウト生成ステップにより、前記ブロックが前記ページ領域を跨いで配置されている場合に、該ページ領域を跨いだ該ブロックを、該ブロックが跨ぐページ領域のうち順序が後以降のページ領域に移動させてブロックの再配置を行う最終レイアウト生成ステップと
をコンピュータに実行させるプログラム。
【請求項１５】
請求項１４に記載のプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７−１】
【図７−２】
【図８】
【図９−１】
【図９−２】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７−１】
【図７−２】
【図８】
【図９−１】
【図９−２】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１０−２１９６８６（Ｐ２０１０−２１９６８６Ａ）
【公開日】平成２２年９月３０日（２０１０．９．３０）
【国際特許分類】
【出願番号】特願２００９−６１８６３（Ｐ２００９−６１８６３）
【出願日】平成２１年３月１３日（２００９．３．１３）
【出願人】（０００００６７４７）株式会社リコー (37,907)
【Ｆターム（参考）】
【公開日】平成２２年９月３０日（２０１０．９．３０）
【国際特許分類】
【出願日】平成２１年３月１３日（２００９．３．１３）
【出願人】（０００００６７４７）株式会社リコー (37,907)
【Ｆターム（参考）】
[ Back to top ]