(57)【要約】【課題】Ｗｅｂページからユーザにより指定されたコンテンツだけをレイアウトすることができる情報処理装置、印刷方法およびプログラムを提供する。【解決手段】Ｗｅｂページ情報をビットマップデータに変換する変換部１０２と、Ｗｅｂページ情報が表示された表示部１０５に、ビットマップデータのイメージ画像を、Ｗｅｂページ情報と切り換えて表示する表示制御部１０６と、表示されたイメージ画像から出力領域の指定の入力を受け付ける受付部１０３と、ビットマップデータから、出力領域に対応する対応領域を抽出する抽出部１０７と、抽出された対応領域を出力ページ上に配置したレイアウトを表すレイアウト情報を生成するレイアウト生成部１０４と、を備えた。【選択図】図１
2012137838.tif 000002
【特許請求の範囲】
【請求項１】
取得されたＷｅｂページ情報をビットマップデータに変換する変換部と、
前記Ｗｅｂページ情報が表示された表示部に、変換された前記ビットマップデータのイメージ画像を、前記Ｗｅｂページ情報と切り換えて表示する表示制御部と、
表示された前記イメージ画像から出力対象となる出力領域の指定の入力を受け付ける受付部と、
前記ビットマップデータから、受け付けられた前記出力領域に対応する対応領域を抽出する抽出部と、
抽出された前記対応領域を出力ページ上に配置したレイアウトを表すレイアウト情報を生成するレイアウト生成部と、
を備えたことを特徴とする情報処理装置。
【請求項２】
前記受付部は、複数の前記出力領域の指定を受け付け、
前記レイアウト生成部は、予め定められたソート順に応じて前記レイアウト情報を生成すること、
を特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記ソート順は、前記出力領域の長さが長い順であって、
前記レイアウト生成部は、複数の前記出力領域を、前記出力領域の長さが長い順に前記出力ページの空き領域に配置するレイアウトを表す前記レイアウト情報を生成すること、
を特徴とする請求項２に記載の情報処理装置。
【請求項４】
前記Ｗｅｂページ情報は構造情報を有し、
前記レイアウト生成部は、前記構造情報に基づいてレイアウトを生成すること、
を特徴とする請求項１に記載の情報処理装置。
【請求項５】
取得されたＷｅｂページ情報をビットマップデータに変換する変換ステップと、
前記Ｗｅｂページ情報が表示された表示部に、変換された前記ビットマップデータのイメージ画像を、前記Ｗｅｂページ情報と切り換えて表示する表示制御ステップと、
表示された前記イメージ画像から出力対象となる出力領域の指定の入力を受け付ける受付ステップと、
前記ビットマップデータから、受け付けられた前記出力領域に対応する対応領域を抽出する抽出ステップと、
抽出された前記対応領域を出力ページ上に配置したレイアウトを表すレイアウト情報を生成するレイアウト生成ステップと、
を含むことを特徴とするレイアウト生成方法。
【請求項６】
コンピュータを、
取得されたＷｅｂページ情報をビットマップデータに変換する変換ステップと、
前記Ｗｅｂページ情報が表示された表示部に、変換された前記ビットマップデータのイメージ画像を、前記Ｗｅｂページ情報と切り換えて表示する表示制御ステップと、
表示された前記イメージ画像から出力対象となる出力領域の指定の入力を受け付ける受付ステップと、
前記ビットマップデータから、受け付けられた前記出力領域に対応する対応領域を抽出する抽出ステップと、
抽出された前記対応領域を出力ページ上に配置したレイアウトを表すレイアウト情報を生成するレイアウト生成ステップ、
として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、レイアウト生成方法、およびプログラムに関する。
【背景技術】
【０００２】
従来、ＨＴＭＬ（Ｈｙｐｅｒ  Ｔｅｘｔ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）言語等で記述され、表示画面に表示されるＷｅｂページ上のデータの一部を印刷する場合、バナー広告等のユーザにとって不要なデータを除いたり、必要な領域だけを指定したりして印刷することは困難である。
【０００３】
このような課題を解決する目的で、ユーザから指定された任意の領域の画像を出力する印刷装置が提案されている（例えば、特許文献１参照。）。特許文献１では、Ｗｅｂページをビットマップに変換し、ビットマップをＷｅｂページから切り替えてブラウザ画面上に表示し、表示した画面上でユーザから指定された領域を印刷データとして出力する方法が開示されている。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１に開示されている印刷装置では、Ｗｅｂページ上の不要な部分を除去して印刷することを主目的とするものであり、Ｗｅｂページ上の必要な画像だけを集めて効率的にレイアウトすることまでは考慮されていない。一方、所望のコンテンツを含むＷｅｂページを印刷して利用するケースは多く、環境への負荷軽減や、紙コスト削減のためには無駄なコンテンツを省くだけでは十分でなく、必要なコンテンツをなるべく少ない枚数で印刷することが要求される。
【０００５】
本発明は、上記に鑑みてなされたものであって、Ｗｅｂページからユーザにより指定されたコンテンツだけをレイアウトすることができる情報処理装置、レイアウト生成方法、およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上述した課題を解決し、目的を達成するために、本発明にかかる情報処理装置は、取得されたＷｅｂページ情報をビットマップデータに変換する変換部と、前記Ｗｅｂページ情報が表示された表示部に、変換された前記ビットマップデータのイメージ画像を、前記Ｗｅｂページ情報と切り換えて表示する表示制御部と、表示された前記イメージ画像から出力対象となる出力領域の指定の入力を受け付ける受付部と、前記ビットマップデータから、受け付けられた前記出力領域に対応する対応領域を抽出する抽出部と、抽出された前記対応領域を出力ページ上に配置したレイアウトを表すレイアウト情報を生成するレイアウト生成部と、を備えたことを特徴とする。
【０００７】
また、本発明にかかる印刷方法は、取得されたＷｅｂページ情報をビットマップデータに変換する変換ステップと、前記Ｗｅｂページ情報が表示された表示部に、変換された前記ビットマップデータのイメージ画像を、前記Ｗｅｂページ情報と切り換えて表示する表示制御ステップと、表示された前記イメージ画像から出力対象となる出力領域の指定の入力を受け付ける受付ステップと、前記ビットマップデータから、受け付けられた前記出力領域に対応する対応領域を抽出する抽出ステップと、抽出された前記対応領域を出力ページ上に配置したレイアウトを表すレイアウト情報を生成するレイアウト生成ステップと、を含むことを特徴とする。
【０００８】
また、本発明にかかる印刷プログラムは、コンピュータを、取得されたＷｅｂページ情報をビットマップデータに変換する変換ステップと、前記Ｗｅｂページ情報が表示された表示部に、変換された前記ビットマップデータのイメージ画像を、前記Ｗｅｂページ情報と切り換えて表示する表示制御ステップと、表示された前記イメージ画像から出力対象となる出力領域の指定の入力を受け付ける受付ステップと、前記ビットマップデータから、受け付けられた前記出力領域に対応する対応領域を抽出する抽出ステップと、抽出された前記対応領域を出力ページ上に配置したレイアウトを表すレイアウト情報を生成するレイアウト生成ステップ、として機能させることを特徴とする。
【発明の効果】
【０００９】
本発明によれば、Ｗｅｂページから所望のコンテンツだけをまとめたドキュメントを容易に作成できるという効果を奏する。
【図面の簡単な説明】
【００１０】
【図１】図１は、本実施の形態にかかるＷｅｂページ印刷支援システムの構成を示すブロック図である。
【図２】図２は、情報処理装置による対応領域抽出処理の手順を示すフローチャートである。
【図３】図３は、情報処理装置による印刷データの生成処理の手順を示すフローチャートである。
【図４】図４は、レイアウト生成部によるレイアウトの手順の詳細を示すフローチャートである。
【図５】図５は、矩形のコンテンツの一例を示す図である。
【図６】図６は、ＦＦＤＨによるコンテンツの一例の配置方法を概略的に示すフローチャートである。
【図７】図７は、ＦＦＤＨにより生成した最密充填レイアウトの一例を示す図である。
【図８】図８は、配置領域における行を示す図である。
【図９−１】図９−１は、ブロックが異なる出力ページに配置される例を示す図である。
【図９−２】図９−２は、ブロックが異なる出力ページに配置される例を示す図である。
【図１０】図１０は、本実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。
【図１１】図１１は、プレビュー表示処理の手順を示すフローチャートである。
【図１２】図１２は、他の例にかかるプレビュー表示処理の手順を示すフローチャートである。
【図１３】図１３は、本実施の形態にかかる情報処理装置のハードウェア構成を示す説明図である。
【発明を実施するための形態】
【００１１】
以下に添付図面を参照して、この発明にかかる情報処理装置の最良な実施の形態を詳細に説明する。図１は、本実施の形態にかかるＷｅｂページ印刷支援システムの構成を示すブロック図である。ネットワークから取得したＷｅｂページの印刷を支援するＷｅｂページ印刷システムは、図１に示すように、情報処理装置１００と、情報処理装置１００に接続された画像出力装置２００とから構成される。
【００１２】
まず、情報処理装置１００は、Ｗｅｂページ情報取得部１０１と、変換部１０２と、受付部１０３と、レイアウト生成部１０４と、表示部１０５と、表示制御部１０６と、抽出部１０７と、印刷データ生成部１０８と、通信制御部１０９と、記憶部１１０と、プレビュー画面生成部１１１とを主に備える。
【００１３】
Ｗｅｂページ情報取得部１０１は、通信制御部１０９を介してＷｅｂページ情報を取得し、取得したＷｅｂページ情報を記憶部１１０に保存する。また、Ｗｅｂページ情報取得部１０１は、取得したＷｅｂページ情報を後述する表示制御部１０６に表示させる。
【００１４】
変換部１０２は、Ｗｅｂページ情報取得部１０１により取得されたＷｅｂページ情報をビットマップデータに変換する。例えば、変換部１０２は、まず、表示部１０５に表示されているＷｅｂページ情報をキャプチャする。そして、変換部１０２は、キャプチャしたＷｅｂページ情報をセルの集合であるビットマップデータに変換する。
【００１５】
表示制御部１０６は、記憶部１１０からＷｅｂページ情報を取得し、取得したＷｅｂページ情報を表示部１０５に表示する。また、表示制御部１０６は、表示部１０５に表示したＷｅｂページ情報を、変換部１０２により変換されたビットマップデータのイメージ画像に切り換えて表示する。
【００１６】
受付部１０３は、表示部１０５に表示されたビットマップデータのイメージ画像から出力領域の指定をユーザから受け付ける。ここで、出力領域とは、画像出力装置２００により出力する対象となる領域のことである。例えば、受付部１０３は、表示部１０５に表示されたビットマップデータのイメージ画像のうち出力対象となる領域を矩形のアイコン操作により受け付ける。
【００１７】
抽出部１０７は、ビットマップデータから対応領域を抽出し、抽出した対応領域のビットマップデータを記憶部１１０に保存する。ここで、対応領域とは、ビットマップデータのうち、ユーザにより指定を受け付けた出力領域に対応するビットマップデータ上の領域のことである。例えば、抽出部１０７は、受付部１０３から入力を受け付けた出力領域を受け取り、受け取った出力領域から対応領域を決定し、決定した対応領域をビットマップデータから抽出する。
【００１８】
また、記憶部１１０が抽出した対応領域のビットマップデータを保存する方法としては、複数の方法がある。ここで、記憶部１１０は、対応領域のビットマップデータを、すでに記憶しているローカルフォルダに保存することとする。なお、抽出部１０７は、対応領域のビットマップデータの保存先を記憶部１１０のほか、サーバやクラウド上の所定領域としてもよい。
【００１９】
記憶部１１０は、受付部１０３により出力領域が受け付けられたタイミングで、対応領域のビットマップデータをファイル形式でフォルダに蓄積する。なお、フォルダは、予め定められた所定のフォルダであっても良いし、ユーザにより指定されたフォルダであっても良い。
【００２０】
また、記憶部１１０は、Ｗｅｂページ情報の取得先であるＷｅｂサイトの階層構造や、Ｗｅｂページの構造等の構造情報に応じてフォルダ毎にカテゴライズしてビットマップデータを保存してもよい。例えば、階層構造を利用する例としては、記憶部１１０は、上位階層が等しい下位階層のデータを同一フォルダに割り当てて、対応領域のビットマップデータを保存してもよい。また、ページ情報を利用する例としては、記憶部１１０は、同一の出力ページにレイアウトされた対応領域のビットマップデータは同一フォルダに保存してもよい。
【００２１】
レイアウト生成部１０４は、抽出部１０７により抽出された対応領域を出力ページ上に配置したレイアウトを表すレイアウト情報（以下、レイアウトという。）を生成する。ここで、出力ページとは、画像出力装置２００により出力されるページであって、例えば、１枚の印刷用紙に印刷されるページのことである。
【００２２】
また、レイアウト生成部１０４は、記憶部１１０により同一フォルダに格納されたビットマップデータを対象としてそれぞれのレイアウトを決定する。また、記憶部１１０に、Ｗｅｂページの構造に従って階層構造上にビットマップデータが保存されている場合、レイアウト生成部１０４は、当該階層構造に従って対応領域のビットマップデータをレイアウトしてもよい。例えば、レイアウト生成部１０４は、記憶部１１０に上位フォルダと下位フォルダが存在する場合、上位フォルダに存在するビットマップデータを下位フォルダに存在するビットマップデータよりも出力ページの上位にレイアウトする。
【００２３】
このように、記憶部１１０が抽出された対応領域のビットマップデータを分類・整理してフォルダを管理することで、Ｗｅｂページの構造がレイアウト結果に反映される。
【００２４】
印刷データ生成部１０８は、レイアウト生成部１０４により生成されたレイアウトに従って印刷データを生成する。ここで、印刷データとは、画像出力装置２００により出力されるデータであって、１または複数の出力ページからなるデータのことである。
【００２５】
通信制御部１０９は、ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）と通信し、Ｗｅｂページ情報を受信する。また、通信制御部１０９は、画像出力装置２００と通信し、印刷データ生成部１０８により生成された印刷データを画像出力装置２００に送信する。
【００２６】
次に、画像出力装置２００の詳細について説明する。画像出力装置２００は、図１に示すように、通信制御部２０１と、出力部２０２とを主に備える。
【００２７】
通信制御部２０１は、情報処理装置１００と通信し、情報処理装置１００から印刷データを受信する。
【００２８】
出力部２０２は、あらかじめ受け付けた印刷設定に従って、通信制御部２０１を介して情報処理装置１００から受信した印刷データを出力する。例えば、出力部２０２は、印刷データを印刷用紙に印刷する。
【００２９】
次に、以上のように構成された情報処理装置１００による対応領域を抽出する対応領域抽出処理の手順について説明する。図２は、情報処理装置１００による対応領域抽出処理の手順を示すフローチャートである。
【００３０】
Ｗｅｂページ情報取得部１０１は、通信制御部１０９を介してＷＷＷからＷｅｂページ情報を取得する（ステップＳ１０１）。ここで、Ｗｅｂページ情報取得部１０１は、取得したＷｅｂページ情報を記憶部１１０に保存する。
【００３１】
表示制御部１０６は、表示部１０５にＷｅｂページ情報取得部１０１により取得されたＷｅｂページ情報を表示部１０５に表示する（ステップＳ１０２）。変換部１０２は、Ｗｅｂページ情報取得部１０１により取得されたＷｅｂページ情報をビットマップデータに変換する（ステップＳ１０３）。
【００３２】
表示制御部１０６は、表示部１０５に表示されているＷｅｂページ情報を、変換部１０２により変換されたビットマップデータのイメージ画像に切り換えて表示する（ステップＳ１０４）。
【００３３】
受付部１０３は、出力領域の指定を受け付ける(ステップＳ１０５)。例えば、受付部１０３は、ビットマップデータのイメージ画像上に大きさを変動可能な矩形のアイコン操作により出力領域の指定を受け付ける。
【００３４】
抽出部１０７は、ビットマップデータから対応領域を抽出する（ステップＳ１０６）。抽出部１０７は、抽出した対応領域を記憶部１１０に保存する（ステップＳ１０７）。
【００３５】
次に、情報処理装置１００による印刷データの生成処理の手順について説明する。図３は、情報処理装置１００による印刷データの生成処理の手順を示すフローチャートである。
【００３６】
レイアウト生成部１０４は、抽出部１０７により抽出された対応領域のビットマップデータを出力ページにレイアウトする（ステップＳ２０１）。ここで、レイアウト生成部１０４によるレイアウト方法の詳細を説明する。図４は、レイアウト生成部１０４によるレイアウトの手順の詳細を示すフローチャートである。
【００３７】
レイアウト生成部１０４は、記憶部１１０から対応領域のビットマップデータ（以下、コンテンツデータという。）を取得する（ステップＳ１）。レイアウト生成部１０４は、取得したビットマップデータに基づき、最密充填レイアウト生成処理を実行する（ステップＳ２）。レイアウト生成部１０４は、ステップＳ２で生成した最密充填レイアウトに基づき出力ページ毎の最終レイアウトを決定する（ステップＳ３）。レイアウト生成部１０４は、決定した最終レイアウトを示すレイアウトデータを、印刷データ生成部１０８に渡す。
【００３８】
ここで、図４のステップＳ２における最密充填レイアウト生成処理について、より詳細に説明する。なお、実際に入力されるコンテンツとしてのデータは、様々な形状が想定されるが、以下では説明の簡潔化のため矩形であることとする。なお、コンテンツデータによる画像を含む最小の矩形を想定してもよいし、コンテンツデータによる画像に対してマージンなどを考慮した矩形を想定してもよい。以下では、煩雑さを避けるため、「コンテンツデータによる画像」を単に「コンテンツ」と呼ぶ。
【００３９】
まず、ここで用いる矩形のコンテンツの一例を説明する。図５は、矩形のコンテンツの一例を示す図である。図５に示すように、レイアウト生成部１０４は、様々な大きさ（幅×高さ）を有する複数の矩形コンテンツを、幅Ｗ、高さＨの配置領域２００上に配置する際のレイアウトを生成する。ここで、幅Ｗは有限の値を持ち、高さＨは、無限大の値を持つものとする。また、このフローチャートにおいてレイアウトとは、出力ページ内の印刷可能な配置領域２００上におけるコンテンツの配置を示し、レイアウトデータは、レイアウトにおけるコンテンツの配置を示す情報（例えば座標情報）からなるものとする。また、出力ページとは、一度に表示を行うための領域をいい、以下では、幅Ｗを持つ配置領域を一度に表示を行う所定の高さｈ毎に区切った各領域を出力ページと呼ぶ。
【００４０】
ステップＳ２の最密充填レイアウトでは、予め決められた幅を持ち、高さが無限の領域に対して、下記の条件を満たし、且つ、高さを最小にするように複数のコンテンツを配置する問題として考えて、各コンテンツのレイアウトを決める。
（１）コンテンツの形状が矩形であって、幅および高さが有理数値である。
（２）回転を許容しない。
（３）各コンテンツが互いに重ならない。
【００４１】
ここで、（３）の各コンテンツが互いに重ならないという条件は、２つのコンテンツＣｉおよびＣｊについて、下記の式(１)〜式（４）のうち少なくとも１つが成立することと等価である。なお、式(１)〜式（４）において、値ｗおよび値ｈは、それぞれコンテンツの幅および高さ、値ｘおよび値ｙは、それぞれコンテンツの一端（例えば左下隅）のｘ座標およびｙ座標である。
ｘｉ＋ｗｉ≦ｘｊ    …（１）
ｘｊ＋ｗｊ≦ｘｉ    …（２）
ｙｉ＋ｈｉ≦ｙｊ    …（３）
ｙｊ＋ｈｊ≦ｙｉ    …（４）
【００４２】
各コンテンツに対して、式(１)〜式(４)のうち何れを採用するかを決める場合、単純に見積もって４(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＋１    …（５）
【００５４】
＜ページレイアウトの生成＞
次に、上述した図４のステップＳ３における、出力ページ毎の最終レイアウトの生成について説明する。図４のステップＳ２において、図６を用いて説明した手順に従い最密充填レイアウトによる初期ページレイアウトを生成した後に、配置領域を、幅が配置領域の幅と一致し、所定の高さを持つ出力ページ単位に分割する。図９−１および図９−２は、ブロックが異なる出力ページに配置される例を示す図である。図９−１に例示されるように、あるブロックが異なる出力ページに跨って配置されてしまうことがある。図９−１の例では、配置領域３００に配置されたブロック３０１〜３０４のうち、ブロック３０３が出力ページを跨いで配置されてしまっている。このままでは、コンテンツが途中で分断されてしまう結果となり、好ましくない。そこで、本実施形態では、各ブロックが出力ページを跨がないようにレイアウトを調整して、出力ページ毎の最終レイアウトを生成する。
【００５５】
本実施形態では、出力ページを跨いで配置されたブロックを、次の出力ページの先頭に移動させる。ここで、次の出力ページとは、出力ページを跨いで配置されたブロックの上端が属する出力ページから見た次の出力ページをいう。すなわち、図９−１の例では、図９−２に示すように、出力ページを跨いで配置されているブロック３０３を次出力ページの先頭に移動させ、当該ブロック３０３より下に配置された各ブロックも、当該ブロック３０３の移動に伴い下方に位置をずらす。以降、この処理を出力ページ毎に順次、繰り返して行うことで、最終的には全てのコンテンツが出力ページを跨がないように配置されたレイアウトを生成することができる。
【００５６】
図１０は、本実施形態によるページレイアウトの生成方法の一例の処理を示すフローチャートである。先ず、ステップＳ２０で、レイアウト生成部１０４は、出力ページのページレイアウトを取得する。なお、ステップＳ２０で取得されるページレイアウトは、処理の対象となる出力ページに係るブロックからなるレイアウトである。出力ページが第１ページ目の場合は、初期ページレイアウトから出力ページのページレイアウトを取得することになる。
【００５７】
次のステップＳ２１で、レイアウト生成部１０４は、出力ページのページレイアウトにページを跨るブロックがあるか否かを判定する。若し、レイアウト生成部１０４は、出力ページを跨るブロックが無いと判定したら（ステップＳ２１：Ｎｏ）、処理をステップＳ２３に移行する。
【００５８】
一方、ステップＳ２１で、レイアウト生成部１０４は、出力ページのレイアウトに出力ページを跨るブロックがあると判定したら（ステップＳ２１：Ｙｅｓ）、処理をステップＳ２２に移行する。ステップＳ２２では、レイアウト生成部１０４は、出力ページのレイアウト中において出力ページを跨って配置されたブロックが、出力ページの次の出力ページの先頭に配置されるように、当該ブロックおよび当該ブロックの下に配置される各ブロックを下方へずらして再配置する。レイアウト生成部１０４は、ブロックの再配置が終了すると、処理をステップＳ２３に移行する。
【００５９】
ステップＳ２３では、レイアウト生成部１０４は、現在のブロックの配置状態に従い、出力ページにおけるページレイアウトを生成し、当該出力ページのページレイアウトを決定する。そして、レイアウト生成部１０４は、処理をステップＳ２４に移行し、全ての出力ページについてページレイアウトが決定されたか否かを判定する。若し、レイアウト生成部１０４は、ページレイアウトが決定されていない出力ページが存在すると判定したら（ステップＳ２４：Ｎｏ）、処理をステップＳ２０に戻し、ステップＳ２３でページレイアウトが決定された次の出力ページを出力ページとして、処理を繰り返す。
【００６０】
一方、ステップＳ２４で、レイアウト生成部１０４は、全ての出力ページについてページレイアウトを決定したと判定したら（ステップＳ２４：Ｙｅｓ）、一連の処理を終了する。この場合、レイアウト生成部１０４は、未配置のブロックが存在しない場合に、全ての出力ページについてページレイアウトを決定したと判定する。
【００６１】
このように、本実施形態によれば、様々なサイズのコンテンツを複数ページに亘る配置領域に配置する場合に、出力ページ数がなるべく小さくなり、且つ、コンテンツが出力ページで分断されないようなレイアウトを自動的に生成できる。
【００６２】
また、配置領域に対して様々なサイズのコンテンツを配置する場合、全てのコンテンツが出力ページを跨がないように出力ページ区切りを設けることができる保証が無く、出力ページを跨いで配置されるコンテンツが発生する可能性が高い。すなわち、コンテンツが配置された状態でコンテンツを区切らないように幅方向の線（ページ区切り）を引くためには、幅方向に見たときに、コンテンツの上辺または下辺が揃っているなどの条件が必要となる。図９−１は、効率的な配置であっても、適当なページ区切りが見つからない例を示す図である。
【００６３】
なお、ここでは、レイアウト生成部１０４によるレイアウト処理の一例として、図４および図６のフローチャートを用いて、ＦＦＤＨによる配置方法を示したが、これに限定されない。例えば、レイアウト生成部１０４は、モノクロコンテンツとカラーコンテンツを分ける方法によりレイアウト生成してもよい。また、レイアウト生成部１０４は、元のＷｅｂページの構造化情報に基づいてレイアウトを生成してもよい。
【００６４】
図３に戻り、ステップＳ２０２において、印刷データ生成部１０８は、出力ページにレイアウトされたビットマップデータを取得する（ステップＳ２０２）。
【００６５】
次に、情報処理装置１００によるプレビュー表示処理の手順について説明する。図１１は、プレビュー表示処理の手順を示すフローチャートである。
【００６６】
レイアウト生成部１０４は、抽出部１０７により抽出された対応領域のビットマップデータを出力ページにレイアウトする（ステップＳ５０１）。印刷データ生成部１０８は、印刷データを生成する（ステップＳ５０２）。
【００６７】
プレビュー画面生成部１１１は、印刷データ生成部１０８により生成された印刷データのプレビュー画面を生成する(ステップＳ５０３)。表示制御部１０６は、プレビュー画面生成部１１１により生成されたプレビュー画面を表示部１０５に表示する（ステップＳ５０４）。例えば、プレビュー画面生成部１１１は、Ｗｅｂページ記述言語（例えばｈｔｍｌ）で記述されたファイルを同一ブラウザ上に表示する。
【００６８】
次に、情報処理装置１００によるプレビュー表示処理の他の例について説明する。図１２は、他の例にかかるプレビュー表示処理の手順を示すフローチャートである。
【００６９】
ステップＳ６０１の処理は、図１１のフローチャートのステップＳ５０１の処理と同様である。また、ステップＳ６０２の処理は、図１１のフローチャートのステップＳ５０３と同様である。また、ステップＳ６０３の処理は、図１１のステップＳ５０４の処理と同様である。
【００７０】
つまり、図１２に示す他の例にかかるプレビュー表示処理では、図１１のフローチャートにおけるステップＳ５０２の処理が省略される。図１１のフローチャートのステップＳ５０２では、プレビュー画面生成部１１１は、プレビューのタイミングでレイアウト結果を反映したプレビュー画面を生成した。しかし、図１２のように、プレビュー画面生成部１１１は、印刷データのプレビュー画面の生成に代えて、ｈｔｍｌ上で各々のビットマップデータを配置した画像を生成してブラウザで表示してもよい。この場合、印刷データ生成部１０８は、出力が指示されてから始めて印刷データを生成するため、プレビュー表示の時間を短縮することができる。
【００７１】
また、以上のように構成されたＷｅｂページ印刷支援システムは、例えば、ブラウザのプラグイン等として実装することもできる。この場合、表示制御部１０６は、ツールバー等にレイアウト実行ボタンが追加されるＩＦ（Ｉｎｔｅｒｆａｃｅ）を表示部１０５に表示することとなる。受付部１０３は、ユーザからこのレイアウト実行ボタンの押下を受け付ける。受付部１０３から押下指示を受信した表示制御部１０６は、ブラウザ上にレイアウト結果を表示する。なお、受付部１０３によりユーザから再度レイアウト実行ボタンの押下が受け付けられた場合、レイアウト生成部１０４は、最初に生成したレイアウトと異なるレイアウトを生成し、表示制御部１０６に表示させる。これら一連の処理の繰り返しにより、Ｗｅｂページ印刷支援システムは、ユーザに所望のレイアウト結果を提示することができる。
【００７２】
このように、本実施の形態によれば、Ｗｅｂページ情報を変換したビットマップデータのイメージ画像から出力領域の指定を受け付け、ビットマップデータから対応領域を抽出し、レイアウトするので、Ｗｅｂページからユーザにより指定されたコンテンツだけをレイアウトすることができる。
【００７３】
次に、本実施の形態にかかる情報処理装置のハードウェア構成について図１３を用いて説明する。図１３は、本実施の形態にかかる情報処理装置のハードウェア構成を示す説明図である。
【００７４】
図１３に示すように、本実施の形態にかかる情報処理装置１００は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）５１などの制御装置と、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）５２やＲＡＭ（ＲＡＮＤＯＭ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）５３などの記憶装置と、ネットワークに接続して通信を行う通信Ｉ／Ｆ５４と、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）ドライブ装置などの外部記憶装置と、ディスプレイ装置などの表示装置と、キーボードやマウスなどの入力装置と、各部を接続するバス６１を備えており、通常のコンピュータを利用したハードウェア構成となっている。
【００７５】
本実施の形態にかかる情報処理装置１００で実行されるレイアウト生成プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅｃｏｒｄａｂｌｅ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録されてコンピュータプログラムプロダクトとして提供される。
【００７６】
また、本実施の形態にかかる情報処理装置１００で実行されるレイアウト生成プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、本実施の形態にかかる情報処理装置１００で実行されるレイアウト生成プログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。
【００７７】
また、本実施の形態のレイアウト生成プログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。
【００７８】
本実施の形態にかかる情報処理装置１００で実行されるレイアウト生成プログラムは、上述した各部（変換部１０２、表示制御部１０６、受付部１０３、抽出部１０７、レイアウト生成部１０４）を含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵ５１（プロセッサ）が上記記憶媒体からレイアウト生成プログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、上述した各部が主記憶装置上に生成されるようになっている。
【符号の説明】
【００７９】
１００  情報処理装置
１０１  Ｗｅｂページ情報取得部
１０２  変換部
１０３  受付部
１０４  レイアウト生成部
１０５  表示部
１０６  表示制御部
１０７  抽出部
１０８  印刷データ生成部
１０９、２０１  通信制御部
１１０  記憶部
１１１  プレビュー画面生成部
２００  画像出力装置
２０２  出力部
【先行技術文献】
【特許文献】
【００８０】
【特許文献１】特開２００７−０９４９５０号公報
【非特許文献】
【００８１】
【非特許文献１】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.
【図１】
2012137838.tif 000003
【図２】
2012137838.tif 000004
【図３】
2012137838.tif 000005
【図４】
2012137838.tif 000006
【図５】
2012137838.tif 000007
【図６】
2012137838.tif 000008
【図７】
2012137838.tif 000009
【図８】
2012137838.tif 000010
【図９−１】
2012137838.tif 000011
【図９−２】
2012137838.tif 000012
【図１０】
2012137838.tif 000013
【図１１】
2012137838.tif 000014
【図１２】
2012137838.tif 000015
【図１３】
2012137838.tif 000016