(57)【要約】    【課題】  要素のレイアウト配置処理を効率的に行うことが可能な印刷装置を提供する。    【解決手段】  構造化言語で記述されたコンテンツの構造化文章を複数の要素から成る解析木に置き換えてから印刷するプリンタ１００において、前記構造化文章から得た前記解析木のルートのノードから開始して下層のノードに向う再帰的処理を行うように制御するコントローラ１０１を有する。【選択図】      図１
2006103280.tif 000002
【特許請求の範囲】
【請求項１】
構造化言語で記述されたコンテンツの構造化文章を複数の要素から成る解析木に置き換えてから印刷する印刷装置において、
前記構造化文章から得た前記解析木のルートのノードから開始して下層のノードに向う再帰的処理を行うように制御する制御手段を有することを特徴とする印刷装置。
【請求項２】
構造化言語で記述されたコンテンツの構造化文章を複数の要素から成る解析木に置き換えてから印刷する印刷装置の制御方法において、
前記構造化文章から得た前記解析木のルートのノードから開始して下層のノードに向う再帰的処理を行うように制御する制御ステップを有することを特徴とする印刷装置の制御方法。
【請求項３】
構造化言語で記述されたコンテンツの構造化文章を複数の要素から成る解析木に置き換えてから印刷する印刷装置において、
前記構造化文章を解析して各要素を配置する要素配置手段を具備し、
前記要素配置手段は、開始タグと終了タグとから成る要素を単位とする木構造に分解して成る要素構造体を形成する要素構造体形成手段と、前記要素構造体に配置情報から成るレイアウト構造体を関連付ける関連付け手段と、前記要素に子要素が存在していれば子要素群に割り当て可能な最大領域を仮設定する領域設定手段と、前記子要素相互間で干渉が存在するか否かを判定する判定手段と、前記判定手段の判定結果に基づき前記子要素を配置する子要素配置手段と、前記子要素配置手段により前記子要素を配置した結果に基づき前記領域設定手段により設定される仮設定領域を子要素配置領域を包含する最小領域となるようにリサイズするリサイズ手段と、前記子要素を配置する矩形領域を前記矩形領域の１つの頂点である始点の座標及び前記始点と点対称に位置する終点の座標を前記レイアウト構造体に記憶する記憶手段と、前記レイアウト構造体を媒介として前記始点を前記木構造の下層に属する要素に引き渡し且つ前記終点を前記木構造の上層に属する要素に引き渡す処理をルートとなる要素から再帰的に実行する実行手段とから成ることを特徴とする印刷装置。
【請求項４】
構造化言語で記述されたコンテンツの構造化文章を複数の要素から成る解析木に置き換えてから印刷する印刷装置の制御方法において、
前記構造化文章を解析して各要素を配置する要素配置ステップを具備し、
前記要素配置ステップは、開始タグと終了タグとから成る要素を単位とする木構造に分解して成る要素構造体を形成する要素構造体形成ステップと、前記要素構造体に配置情報から成るレイアウト構造体を関連付ける関連付けステップと、前記要素に子要素が存在していれば子要素群に割り当て可能な最大領域を仮設定する領域設定ステップと、前記子要素相互間で干渉が存在するか否かを判定する判定ステップと、前記判定ステップの判定結果に基づき前記子要素を配置する子要素配置ステップと、前記子要素配置ステップにより前記子要素を配置した結果に基づき前記領域設定ステップにより設定される仮設定領域を子要素配置領域を包含する最小領域となるようにリサイズするリサイズステップと、前記子要素を配置する矩形領域を前記矩形領域の１つの頂点である始点の座標及び前記始点と点対称に位置する終点の座標を前記レイアウト構造体に記憶する記憶ステップと、前記レイアウト構造体を媒介として前記始点を前記木構造の下層に属する要素に引き渡し且つ前記終点を前記木構造の上層に属する要素に引き渡す処理をルートとなる要素から再帰的に実行する実行ステップとから成ることを特徴とする印刷装置の制御方法。
【請求項５】
マークアップ言語で記述された構造化文書を解析して、各要素をノードとする全体の木構造を構築する木構造構築手段と、前記全体の木構造の各要素をページに割り付け可能か再帰的に判定しながらページ毎の木構造へ順次コピーするページ毎木構造構築手段と、前記ページ毎の木構造に基づいて印刷を行う印刷手段とを有することを特徴とする印刷装置。
【請求項６】
マークアップ言語で記述された構造化文書を解析して、各要素をノードとする全体の木構造を構築する木構造構築ステップと、前記全体の木構造の各要素をページに割り付け可能か再帰的に判定しながらページ毎の木構造へ順次コピーするページ毎木構造構築ステップと、前記ページ毎の木構造に基づいて印刷を行う印刷ステップとを有することを特徴とする印刷装置の制御方法。
【請求項７】
請求項２または４または６に記載の印刷装置の制御方法を実現するためのコンピュータ読み取り可能なプログラムコードを有することを特徴とする制御プログラム。
【請求項８】
請求項７に記載の制御プログラムを格納したことを特徴とする記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルデータ放送や、インターネットを始めとするデータ通信を用いて配信するコンテンツの印刷（印字）に関し、特に、印刷オブジェクトのレイアウトを表現するコンピュータ言語（例えば、データをタグによって区切ることでデータ構造を表現する言語、即ち、マークアップ言語）で構成するコンテンツの印刷装置、その印刷装置を制御する制御方法、制御プログラム及びこの制御プログラムを格納した記憶媒体に関する。
【背景技術】
【０００２】
以下、本発明と関連する従来技術について説明する。
【０００３】
なお、ここに挙げる従来技術は、表示を目的としているため、例えば、ある注目領域だけを高速でレイアウトするものであって、コンテンツ全体を総括的に配置するとする本発明の印刷装置における応用分野とは必ずしも対比をなすものではない。
【０００４】
まず、第１の従来技術として、ツリーにおける情報量がルートから下位レベルになるにつれて指数関数的に増大する事象に対する緩和に関するものであって、ブランチを有するノードリンク構造のレイアウト処理において、ノードリンク構造の密度を均一化する技術が提案されている（特許文献１参照）。この特許文献１は、表示系、特に、高品質のアニメーション分野への応用を想定している。
【０００５】
次に、第２の従来技術として、局所的なレイアウト技術の適用によって、大きな構造のレイアウトの結果生じる問題点を軽減する技術、具体的には、負曲率を有する空間にレイアウトされたノードリンク構造の局所的な再レイアウトを可能にする技術が提案されている（特許文献２参照）。ノードのレイアウトは、その親のレイアウト及びその親から始まる２世代または３世代のノード構造にだけ依存する。それゆえ、レイアウトは、最初に、ルートに最も近いノードをレイアウトして、次に、構造が走査されるにつれてノードを追加することにより増分的に行うことができる。この第２の従来技術（特許文献２）は、常に構造のルートノードまたは基底のリーフで開始するのではなく、どの任意の要素から（配置を）開始しても表示を生成できるレイアウト技術である。その応用分野は、アニメーションに限らず、ウエブ関連構造の可視化及びハイパーテキスト階層等の大きなノードリンク構造のためのブラウザ等である。
【０００６】
更に、第３の従来技術として、レイアウトされたノードリンク構造をディスプレイ上に表示するための空間マッピングに関するものであって、特に、ルートノードから再帰的に処理が実行されるのではなく、構造内の任意の要素からマッピングを開始できる技術が提案されている（特許文献３参照）。この第３の従来技術（特許文献３）によれば、マッピングを常にノードリンク構造の固定部から始めるのではなく、効率的なマッピングをもたらす開始ノードを検知できる。よって、アニメーション等の短時間に繰り返しマッピングを必要とする処理に有効である。また、ノードリンク構造の対話式ブラウザ、ウエブ関連構造の可視化及びハイパーテキスト階層等の大きなノードリンク構造を対象としたブラウザ等の分野にも応用できる。
【特許文献１】特開平８−１２９６４９号公報
【特許文献２】特開２０００−６７２５３号公報
【特許文献３】特開２０００−１５５８５６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
デジタルテレビはもとより、最近では、携帯電話やデジタルカメラ等も、マークアップ言語で記述したコンテンツを取り扱うことが多くなってきている。
【０００８】
ところが、このような機器では資源が限られているため、コンテンツを印刷データに変換する過程でレイアウトは、特に、メモリ資源を消費して負荷の大きい処理となっている。
【０００９】
また、画像が表示可能領域をはみ出すような場合、表示系ではスクロールバーが現れて操作者に領域の選択を促すことができる。また、印刷系では、前記コンテンツを出力媒体にマッピングするに際して、再現性が高く、視覚的に違和感のないレイアウト手法が求められる。
【００１０】
一方、対象とする要素の配置によって、先行した要素ブロックと干渉するケースでは、先行した要素を再配置するために前記要素ブロックを再帰的に参照する必要がる。この場合でも、印刷系では、全てのコンテンツファイルを解析し、ページに割り付けてから最終出力するので、表示系のように、ある注目領域だけを高速でレイアウトする手法は適用できない。レイアウトが厳密には規定されない構造化文書を、複数の要素ブロックから成る解析木に置き換えて出力媒体に印刷する系では、前記要素ブロックを出力媒体に効率的に配置することが可能な手法が求められる。
【００１１】
また、前記要素ブロックを出現順に配置していくと、前記要素ブロックが重なり合って、要素ブロック同士が干渉する場合がある。この要素ブロック同士の干渉を回避するために、レイアウト処理を再帰的に実行する必要がある。
【００１２】
本発明は、上述したような従来技術の有する問題点を解消するためになされたもので、その目的は、要素のレイアウト配置処理を効率的に行うことが可能な印刷装置、印刷装置の制御方法、制御プログラム及び記憶媒体を提供することにある。
【課題を解決するための手段】
【００１３】
上記目的を達成するため、本発明の印刷装置は、構造化言語で記述されたコンテンツの構造化文章を複数の要素から成る解析木に置き換えてから印刷する印刷装置において、前記構造化文章から得た前記解析木のルートのノードから開始して下層のノードに向う再帰的処理を行うように制御する制御手段を有することを特徴とする。
【００１４】
また、上記目的を達成するため、本発明の印刷装置は、構造化言語で記述されたコンテンツの構造化文章を複数の要素から成る解析木に置き換えてから印刷する印刷装置において、前記構造化文章を解析して各要素を配置する要素配置手段を具備し、前記要素配置手段は、開始タグと終了タグとから成る要素を単位とする木構造に分解して成る要素構造体を形成する要素構造体形成手段と、前記要素構造体に配置情報から成るレイアウト構造体を関連付ける関連付け手段と、前記要素に子要素が存在していれば子要素群に割り当て可能な最大領域を仮設定する領域設定手段と、前記子要素相互間で干渉が存在するか否かを判定する判定手段と、前記判定手段の判定結果に基づき前記子要素を配置する子要素配置手段と、前記子要素配置手段により前記子要素を配置した結果に基づき前記領域設定手段により設定される仮設定領域を子要素配置領域を包含する最小領域となるようにリサイズするリサイズ手段と、前記子要素を配置する矩形領域を前記矩形領域の１つの頂点である始点の座標及び前記始点と点対称に位置する終点の座標を前記レイアウト構造体に記憶する記憶手段と、前記レイアウト構造体を媒介として前記始点を前記木構造の下層に属する要素に引き渡し且つ前記終点を前記木構造の上層に属する要素に引き渡す処理をルートとなる要素から再帰的に実行する実行手段とから成ることを特徴とする。
【００１５】
また、上記目的を達成するため、本発明の印刷装置は、マークアップ言語で記述された構造化文書を解析して、各要素をノードとする全体の木構造を構築する木構造構築手段と、前記全体の木構造の各要素をページに割り付け可能か再帰的に判定しながらページ毎の木構造へ順次コピーするページ毎木構造構築手段と、前記ページ毎の木構造に基づいて印刷を行う印刷手段とを有することを特徴とする。
【００１６】
また、上記目的を達成するため、本発明の印刷装置の制御方法は、構造化言語で記述されたコンテンツの構造化文章を複数の要素から成る解析木に置き換えてから印刷する印刷装置の制御方法において、前記構造化文章から得た前記解析木のルートのノードから開始して下層のノードに向う再帰的処理を行うように制御する制御ステップを有することを特徴とする。
【００１７】
また、上記目的を達成するため、本発明の印刷装置の制御方法は、構造化言語で記述されたコンテンツの構造化文章を複数の要素から成る解析木に置き換えてから印刷する印刷装置の制御方法において、前記構造化文章を解析して各要素を配置する要素配置ステップを具備し、前記要素配置ステップは、開始タグと終了タグとから成る要素を単位とする木構造に分解して成る要素構造体を形成する要素構造体形成ステップと、前記要素構造体に配置情報から成るレイアウト構造体を関連付ける関連付けステップと、前記要素に子要素が存在していれば子要素群に割り当て可能な最大領域を仮設定する領域設定ステップと、前記子要素相互間で干渉が存在するか否かを判定する判定ステップと、前記判定ステップの判定結果に基づき前記子要素を配置する子要素配置ステップと、前記子要素配置ステップにより前記子要素を配置した結果に基づき前記領域設定ステップにより設定される仮設定領域を子要素配置領域を包含する最小領域となるようにリサイズするリサイズステップと、前記子要素を配置する矩形領域を前記矩形領域の１つの頂点である始点の座標及び前記始点と点対称に位置する終点の座標を前記レイアウト構造体に記憶する記憶ステップと、前記レイアウト構造体を媒介として前記始点を前記木構造の下層に属する要素に引き渡し且つ前記終点を前記木構造の上層に属する要素に引き渡す処理をルートとなる要素から再帰的に実行する実行ステップとから成ることを特徴とする。
【００１８】
更に、上記目的を達成するため、本発明の印刷装置の制御方法は、マークアップ言語で記述された構造化文書を解析して、各要素をノードとする全体の木構造を構築する木構造構築ステップと、前記全体の木構造の各要素をページに割り付け可能か再帰的に判定しながらページ毎の木構造へ順次コピーするページ毎木構造構築ステップと、前記ページ毎の木構造に基づいて印刷を行う印刷ステップとを有することを特徴とする。
【発明の効果】
【００１９】
本発明によれば、処理負担が軽減し且つ効率的な処理が可能である。
【発明を実施するための最良の形態】
【００２０】
以下、本発明の実施の形態について、図面を参照しながら説明する。
【００２１】
＜用語の定義＞
W3C(World Wide Web Consortium)が定めているXHTML1.1TM(eXtensible Hyper Text Markup Language)及び規格CSS2.0TM(Ｃａｓｃａｄｉｎｇ Style Sheet 2.0)で定める仕様書を本稿と共に読むと、語彙のみならず、本発明の広い範囲を理解する上で役に立つ。
【００２２】
また、特許請求の範囲を含み、本実施の形態で言うところの「ノードリンク構造」とは、ノードとリンクとに区別できる項目を含み、各リンクが２つ以上のノードに関係している構造を言う。また、ノードリンク関係とは、ノードのパス及び要素間のリンクに基づく要素間の関係である。また、説明文の中で、「カレント」とは、その時点で注目している処理対象のことである。例えば、カレント要素とは、その時点で処理対象となっている要素、即ち、「現要素」の意味で用いている。また、「Boxモデル」とは、前記W3C 規格CSS2.0において導入している矩形領域の描画モデルである。また、「行Box」とは、テキスト・文字を配置する領域を総括して呼ぶ名称として用いている。
【００２３】
（第１の実施の形態）
まず、第１の実施の形態について、図１〜図１５に基づき説明する。
【００２４】
本発明において重要なことは、コンテンツを入力するコンテンツ入力手段と、前記コンテンツ入力手段により入力したコンテンツを解釈実行する解釈実行手段と、前記解釈実行手段の解釈実行結果により印刷データを作成する印刷データ作成手段とを備える。
【００２５】
また、前記コンテンツは、データをタグによって区切ることでデータ構造を表現するマークアップ言語で記述されている。
【００２６】
ここで、要素ブロックのページへの割り付けは、要素全体ツリーからページ内要素ツリーに要素を順次コピーすることから始まる。そして、ページ内要素ツリーが要素の割付で一杯になったとき、改ページ処理を行う。このとき、ページ後端にかかる要素の配置可能な範囲を算出して、はみ出した部分を分割して、次のページに送る。
【００２７】
前記印刷オブジェクトの配置を管理する管理手段は、子要素を持たないブロックはそのまま配置する第１の配置手段と、子要素を持つブロックは大きさを確定せず仮配置する仮配置手段と、兄弟要素に干渉するか否かを判定する判定手段と、前記判定手段の判定結果に基づき前記兄弟要素を配置する第２の配置手段と、親要素の配置処理を再開し子要素を包含する大きさにサイズを拡大する拡大手段とから成る。
【００２８】
XML系言語で記述されたコンテンツの構造化文章の解析において、開始タグと終了タグとから成る要素を単位とする要素構造体を作成する。次に、前記要素構造体の相互関連を解析し、木構造を構築する。しかる後に、前記要素構造体に、スタイル構造体とレイアウト構造体を関連付ける。一方、ページ毎の属性は、ページ情報構造体に纏めて格納し、新たにページが生成する毎に対応する情報を参照する。
【００２９】
ここで、要素ブロックのページへの割り付けは、全体の要素ツリーからページ毎の要素ツリーを構築するために、要素を順次コピーすることから始まる。そして、前記ページ毎の要素ツリーが完成した時（例えば、要素の割付で一杯になったとき）、改ページ処理を行う。このとき、ページ後端にかかる要素の配置可能な範囲を算出して、はみ出した部分を分割して、次のページに送る。このページ毎の要素ツリーに基づいて印刷処理を行う。
【００３０】
＜システムの概要＞
図１は、本実施の形態に係る印刷装置の概要構成を示す図であり、同図において、１００は本実施の形態に係る印刷装置（Printer）で、パーソナルコンピュータ（PC）１０３ａや個人向けペン入力小型情報機器（PDA）１０３ｂ、デジタル放送機器（DTV）１０３ｃ等のホスト(Host)機器１０３より有線または無線の接続形態で入力するコンテンツ(Contents)を解釈して印刷データ(Print-data)に変換するコントローラ(Controller：制御手段)１０１、前記印刷データに基づきページメディア（Page Media）１０４上に画像を形成するプリントエンジン(Print Engine)１０２を含む。
【００３１】
なお、ここで言うコントローラ１０１の実態は、中央演算処理装置（CPU）、主記憶装置、補助記憶装置及びインタフェースを含むシングルボードコンピュータで、例えば、リナックス・オペレーティングシステム(Linux OS)の制御下で動作する。
【００３２】
＜要素ツリーの構築＞
図２（ａ）は、構造化文書を字句解析、構文解析により得た解析木或いはノードリンクのグラフ図である。
【００３３】
図２（ａ）に示す解析木の実体は、多方向分岐リストで、本実施の形態では、「全要素ツリー」と称する。この全要素ツリーの図において左側が<head>、右側が<body>で、各ノードは、３つのデータ構造体が相互に関連づけられる。即ち、核となる要素情報体である「要素構造体」２０１、レイアウトの指定を含む「スタイル構造体」２０２及びレイアウト制御情報を格納する「レイアウト構造体」２０３である。
【００３４】
＜レイアウトの手順＞
図２（ｂ）は、レイアウトの手順を示す図である。
【００３５】
前記要素ブロックを出力媒体に効率的に配置する手順を以下に説明する。
【００３６】
まず、要素ツリーを「ルート」、即ち、本実施の形態では、<html>から順に辿り、要素毎の「スタイル構造体」２０２に基づいて要素、BOXモデル、文字、画像をページの単位で、順次レイアウトする。
【００３７】
まず、単純な例として、親子２層の場合について説明する。
【００３８】
親要素は、子要素の配置範囲を「レイアウト構造体」２０３を媒介として子要素に伝える（配置指示）。子要素は、前記配置指定内に要素の展開を試みるが、親要素が推定した初期の配置範囲より狭い範囲内に収まるとか、逆にはみ出す場合も有り得る。レイアウトが終了したとき、子要素は、最終的に配置したオブジェクトの最右下端を「終点」として、「レイアウト構造体」２０３を媒介として親要素に伝える（配置結果）。
【００３９】
次に、レイヤーが２層以上である場合について説明する。
【００４０】
上記親子２層からも類推できるように、レイアウトの進行と共に２つのパラメータが逆方向に伝わる。即ち、レイアウト可能範囲は、親要素から子要素へ、子要素から孫要素へといったように、レイヤーの上から下層方向に伝わる。
【００４１】
一方、前記「終点」は、逆に、孫要素から子要素へ、更に親要素へといったように、レイヤーの下層から上層に順次伝わる。
【００４２】
＜レイアウト構造体＞
図３（ａ）、（ｂ）は、レイアウト構造体２０３を説明する図で、ここでは、レイアウト処理によって操作するパラメータを説明している。
【００４３】
レイアウト構造体２０３には、配置した要素の位置情報、子要素の配置可能範囲、出力する文字列のフォントメトリック情報等のレイアウト情報を保持する。
【００４４】
以下に、一部の重要なパラメータを、図３（ａ）、（ｂ）を用いて解説する。
【００４５】
「rc」は、配置情報における表現ではレクタングルで、ある矩形領域を示している。「rc_child」は、子要素配置情報で、全子要素の配置が完了した後の子要素範囲を表す領域である。「xmax,ymax」は、子要素最大終点で、現在の要素に含まれる子要素を１つずつ配置する毎に更新していく子要素の最大終点位置を管理するための位置情報、或いは、子要素毎の終点位置（right,bottom）の最大値を管理する変数である。「right,bottom」は、カレント要素終点位置で、現在の要素の配置が終了した際に、親要素へ通知する現在の要素（子要素）の終点位置の情報である。
【００４６】
＜レイアウトの基本形＞
図４は、各種要素類におけるスタイル指定と配置ルールとの対応を示す図である。
【００４７】
図４（ａ）は、インライン（inline）要素の配置を示す図であり、各要素は、左詰めで配置していき、横幅を超えるときは、ラインフィード（line feed:改行）となる。
【００４８】
図４（ｂ）は、ブロック(block)要素の配置を示す図であり、各要素は、常に上下の縦方向に配置され、左右に並ぶことはない。
【００４９】
図４（ｃ）は、絶対位置指定の配置の様子を示す図であり、この場合、位置が明示的に指定される。依って、各ブロックが重なり合うことがある。その場合、記述の順に重なる。即ち、後出のブロックが上層になる。
【００５０】
図４（ｄ）は、相対配置指定の様子を示す図であり、この場合、各ブロックが重なることのないように配置される。
【００５１】
図４（ｅ）は、フロートスタイルに対するブロックの位置を示す図であり、各ブロックは、右配置か左配置かをスタイル表現により明示的に指定した場合の配置を示している。
【００５２】
＜要素の絶対配置＞
図５は、要素を配置する場合の親要素と子要素との関係とBOXモデルを説明する図であり、同図において、５０１は親要素、５０２は子要素である。
【００５３】
子要素５０２は、親要素５０１から引き継いだレイアウト構造体を参照する。即ち、前記レイアウト構造体には、子要素５０２の配置可能範囲（rc_child）が格納されている。例えば、親要素５０１が<body>「図２（ａ）参照」であれば、ページ構造体が保持するPage BOXの大きさが、配置範囲（rc_child）として子要素５０２に引き継がれる。
【００５４】
図６は、要素に対応するBOXモデルの座標を説明する図である。
【００５５】
図６（ａ）は、親要素と子要素の基準点の関係を示す図で、絶対配置なら原点(0,0)を基準点として採用し、相対配置なら親要素からの相対座標(sx,sy)を基準点として採用する。
【００５６】
図６（ｂ）は、「終点」を説明する図で、width、heightで決まる位置、或いは子要素のうち最右下端をrc_childの終点とする。
【００５７】
なお、本実施の形態において適用しているBOXモデルは、rc_childから(left,top)の位置を基点として、marginによる余白（rc_margin）、borderによる外枠（rc_border）、paddingによる要素隙間（rc_padding）を順に決定し、paddingの内側を子要素の配置範囲（rc_child）と定義している。
【００５８】
図７及び図８は、要素を配置する手順を示す図で、レイアウト構造体の各パラメータ、特に、「終点」の決定プロセスを示している。
【００５９】
まず、カレント要素のwidth,heightがauto指定であった場合は、親要素が指定した「配置範囲の左上」を仮の「終点」としてレイアウト構造体に格納する。
【００６０】
次に、カレント要素に含まれる全ての子要素について同様の処理を再帰的に行う。このときも、子要素に対してカレント要素の配置情報を伝達する際に、レイアウト構造体を利用する。即ち、子要素は、カレント要素から引き渡されたレイアウト構造体を参照して、自分の配置範囲、開始点を得てレイアウト処理を行う。
【００６１】
更に、カレント要素は、配下の要素の最終配置位置、即ち、終点(right,bottom)を親要素へ通知する。そして、全ての子要素の配置が完了すると、カレント要素は、子要素の配置範囲が分る。最終配置では、全ての子要素の最大範囲（right,bottom）が、カレント要素のwidth,heightを超える場合や、auto指定であった場合は、カレント要素の配置範囲（rc_child）の終点を更新する。
【００６２】
ここで、更新されたrc_childの終点(right,bottom)を基準点として、BOXモデルのpadding, border, marginそれぞれの終点を求め直す。そして、カレント要素の最終配置の終点(right,bottom)を親要素へ通知する。
【００６３】
以下、前述の処理を更に図７及び図８と対応させて、各ステップを順に説明する。
【００６４】
図７は、配置をしようとしている要素ツリーを示す図で、ルートである<html>７０１の下にページメディアに対応する<body>７０２、その下に親要素<parent>７０３、更に現要素<current>７０４があり、その下に、３つの子要素<child>７０５が属する。
【００６５】
図８（ａ）は、親要素の暫定配置を行う説明図である。この時点で、親要素に含まれる子要素の配置が不明であるので、カレント要素の配置範囲（rc_child）は、配置可能な領域内で最大の大きさ（紙等の出力媒体のページサイズに基づいて定まる）を持っている。また、最大終点(xmax,ymax)は、初期値としてrc_childの左上を指している。
【００６６】
図８（ｂ）は、子要素の配置を行う説明図である。子要素の配置過程で、子要素の終了位置(right,bottom)を親要素へ通知する。親要素では、親要素が管理している最大終点(xmax,ymax)と子要素の終了位置(right,bottom)との比較を行い、子要素の終了位置(right,bottom)が大きければ、親要素の最大終点(xmax,ymax)を更新する。
【００６７】
図８（ｃ）は、最大終点(xmax,ymax)を更新する説明図である。最大終点(xmax,ymax)は、子要素の終了位置(right,bottom)で更新される。
【００６８】
図８（ｄ）は、同様に２つ目の子要素の配置を行う説明図である。
【００６９】
図８（ｅ）は、最後の子要素の配置を行う説明図である。３つ目の子要素の終点は、Y方向のみ大きいので、ymaxのみが更新され、xmaxは更新されない。
【００７０】
図８（ｆ）は、全ての子要素の配置が完了し、親要素に処理が戻る説明図である。親要素は、子要素の配置結果から、親要素自身の最終配置を行う。全ての子要素の配置が完了し、親要素の管理するxmax,ymaxは、子要素の配置毎に更新される。親要素の最終配置では、最大終点(xmax,ymax)の位置へ親要素のrc_childの終点位置を設定する。
【００７１】
図８（ｇ）は、rc_childの終点を基点としてpadding,border,marginの終点が決定される説明図である。
【００７２】
図８（ｈ）は、以上の結果によるレイアウトの最終形を示した図である。
【００７３】
図９は、配置をしようとしている要素ツリーを示す図であり、同図において、ルートであるhtml９０１の下にページメディアに対応するbody９０２、その下に親要素（parent）９０３、その下に現要素（current）９０４があり、その下に３つの子要素（child）９０５が属する。更に１つの子要素（child）の下に２つの孫要素（descendant）９０６が属する。
【００７４】
図１０は、要素のレイアウト処理動作の流れを示すフローチャートである。
【００７５】
まず、ステップＳ１００１では、要素のハンドルを取得する、これにより、解析木に関連する構造体のポインターから、処理対象のレイアウトに関するデータテーブルが解る。次に、ステップＳ１００２で、レイアウト構造体から、rc_child情報を取得し、親要素から引き継いだrc_parentをrc_childの暫定値として採用する。次に、ステップＳ１００３で、未配置の子要素を有しているか否か、即ち、処理対象の子要素がカレント要素の下に存在するか否かを判断する。そして、未配置の子要素を有している、即ち、処理対象の子要素がカレント要素の下に存在すると判断された場合は、ステップＳ１００４へ進んで、子要素を配置するために自分自身のルーチン(DoNode)に再入した後、前記ステップＳ１００３へ戻る。
【００７６】
一方、前記ステップＳ１００３において、未配置の子要素を有していない、即ち、処理対象の子要素がカレント要素の下に存在しないと判断された場合は、ステップＳ１００５へ進んで、rc_childを更新し、最終の(xmax,ymax)をrc_childとする。次に、ステップＳ１００６で、rc_childの終点を基準としてボックスモデル(Box Model)を形成し、padding,border,margineの終点を決める。次に、ステップＳ１００７で、xmax,ymaxを更新し、right,bottomを前回のxmax,ymaxと比較して大きい方をxmax,ymaxに採用し、その後、リターン(return)する。
【００７７】
図１１は、要素を配置した結果を表している。同図においては、親要素（parent）の中に１つの現要素<current>が配置され、この現要素<current>の中に３つの子要素（child）が配置され、１つの子要素（child）の中に２つの孫要素（descendant）が配置されている。
【００７８】
＜インライン要素の相対配置＞
図１２は、行ボックスの配置モデルを示す図、図１３は、インライン子要素を相対配置する説明図である。
【００７９】
インライン子要素の配置は、親要素が指定した配置範囲（rc_child）の枠内に、相対開始位置(sx,sy)から開始する。動作的には、親要素が用意したレイアウト構造体を子要素が参照する。例えば、body要素の場合、PageBOXの領域をrc_child、PageBOXの左上(sx,sy)を基準としてオブジェクトを配置する。
【００８０】
親要素は、情報をレイアウト構造体へ格納し、カレント要素に引き渡す。カレント要素は、配下のインライン子要素について再帰呼び出しを行う。このときも、カレントインライン子要素は、インライン子要素にレイアウト構造体を媒介して配置情報を引き渡す。インライン子要素は、インライン親要素から引き渡されたレイアウト構造体を参照し、自分の配置範囲、開始位置を知り、同様にレイアウト処理を行う。
【００８１】
子要素を持たない本文及び画像はsx,syを「開始位置」、width,heightを「サイズ」として、行BOX配置処理を行う。行BOX配置では、本文の文字列や画像の横方向がwidthやrc_childを超えた場合に改行処理を行う。改行処理では、sxを折り返したrc_child左端に設置し、syを更新する。本文の文字列は、syをline-height分増加させた位置へ更新する。画像の場合、syを画像の高さheight分増加させた位置へ更新する。
【００８２】
行BOX配置では、それぞれの行BOXに対しBOXモデルを適用する。BOXモデルは、行BOXの本文や画像のrc_childのtopをsyとし、marginによる余白（rc_margin）、borderによる外枠（rc_border）、paddingによる要素隙間（rc_padding）を順に決定していく。
【００８３】
インライン子要素では、行BOXの最終配置位置をsx,syと置き換えて、親要素であるカレントインライン子要素へ通知する。カレントインライン子要素では、通知されたsx,syを自身のsx,syに置き換え、同様に親要素に通知する。更に、カレントインライン子要素にインライン子要素（前のインライン子要素の兄弟要素）が含まれる場合には、更新した相対開始位置(sx,sy)を次のインライン子要素に引き渡すことで、次のインライン子要素を前のインライン子要素の次の位置へ配置できる。
【００８４】
全てのインライン子要素の呼び出しが完了したら、カレントインライン子要素の最終配置処理を行う。
【００８５】
このカレントインライン子要素の最終配置処理では、子要素が更新したsyにline-height分を加算した位置を親要素へ通知し、親要素は、開始Y座標のblk_syを前記加算した位置に置き換える。
【００８６】
カレントインライン子要素では、インライン子要素の最大sx位置を自分の最終配置位置の終点(right,bottom)として親ブロック要素へ通知する。親ブロック要素では、全てのインライン子要素の終点(right,bottom)の最大位置を自身の子要素配置範囲のrc_childに置き換え、ブロック要素の最終配置を行う。
【００８７】
＜ブロック要素の相対配置＞
図１４は、ブロック要素の配置のモデル図、図１５は、ブロック要素を実際に相対配置する図である。
【００８８】
ブロック要素の配置では、親要素で指定した子要素配置範囲（rc_child）で示される領域の中に、同じく親要素で指定したブロック要素開始Y座標（blk_sy）から配置を開始する。即ち、親要素がレイアウト構造体を引き渡し、カレント要素は、それを参照する。例えば、body要素は、PageBOXをrc_childとして、即ち、PageBOXのtopをblk_syとして引き継ぐ。
【００８９】
ブロック要素の配置では、子要素配置範囲（rc_child）及びブロック要素開始Y座標（blk_sy）にブロック要素のBOXモデルを適用する。BOXモデルは、rc_childとblk_syを基点に、marginによる余白（rc_margin）、borderによる外枠（rc_border）、paddingによる要素隙間（rc_padding）を順に決定し、paddingの内側を子要素の配置範囲（rc_child）及び子要素のブロック要素開始Y座標(blk_sy)とする。
【００９０】
なお、width、heightがauto指定であった場合は、親要素が指定した配置範囲(rc_child)の最大位置に終点を仮配置する。ここで、仮配置の情報は、レイアウト構造体に格納される。次に、カレント要素に含まれる他の全ての子要素について、前記処理を再帰的に実行する。このとき、子要素に対してカレント要素の仮配置情報を伝達するために、レイアウト構造体を引き渡す。
【００９１】
子要素は、親要素から引き渡されたレイアウト構造体を参照し、自身の配置範囲、開始位置を知り、レイアウト処理を行う。子要素では、最終配置位置(right,bottom)を親要素（カレント要素）へ通知する。更に、子要素では、親要素（カレント要素）が管理しているブロック要素開始Y座標(blk_sy)を更新する。
【００９２】
親要素であるカレント要素の配下にある全ての子要素の呼び出しが完了したら、カレント要素の最終配置を行う。この最終配置では、全ての子要素の最大座標(right,bottom)が、カレント要素のwidth、heightを超える場合やauto指定であった場合は、子要素の配置情報（rc_child）で定める「終点」を更新する。
【００９３】
次に、更新されたrc_childの終点(right,bottom)を基点にBOXモデルのpadding,border,marginの終点を求め直す。最後に、カレント要素では、自分の最終配置位置の終点(right,bottom)を親要素へ通知して、親要素が管理しているブロック要素開始Y座標(blk_sy)を更新する。
【００９４】
従来においては、要素ツリーを辿りながら要素を配置する処理は、出力媒体が表示スクリーンであるため、選択した部分に限定して処理を高速化する手法が適用されている。
【００９５】
一方、印刷出力等、ページメディアへの出力に際しては、コンテンツ全体を処理しつつ印刷出力する。
【００９６】
そこで、本発明は、出力媒体であるページメディアに出力する場合の効率的な処理技術を提供するものである。
【００９７】
処理対象である要素の配置に関連して、既に配置した要素ブロックに影響が出るケースで、例えば、ページの後端処理では、先行する要素を参照する必要が発生する。
【００９８】
従来においては、ノードリンクを毎回辿る必要があった。
【００９９】
本実施の形態では、構造化文章を解析して得られる要素ツリー全体から、出力するページ内に収容可能な要素群だけを取り出す処理において、レイアウトに不可欠な情報を集約して成るレイアウト構造体を、出力媒体は、解析木を下流に向かう制御の遷移のみならず、上流に戻る処理においても共通して適用可能である。
【０１００】
本実施の形態によれば、注目する１つのノードの処理に適用するものであるが、同時に、リンクされている全てのノードにも繰り返し実行可能である。実際は、ルートとなる要素に対して実行するだけで、その下層のノードに対しても内部で再帰的に実行され、制御が戻った時には、既にレイアウトが完了している。
【０１０１】
また、印刷へ応用を想定した手法、即ち、コンテンツファイルを走査しつつ、全体のレイアウトが早く収束する。
【０１０２】
更に、印刷装置側の処理負担が軽減し且つ効率的な処理が可能である。
【０１０３】
（その他の実施の形態）
以上が本発明の実施の形態の説明であるが、本発明は、これら実施の形態に限られるものではなく、特許請求の範囲で示した機能、または実施の形態の構成が持つ機能を達成できる構成であれば、どのようなものであっても適用可能である。
【０１０４】
また、本発明の目的は、前述した実施の形態の機能を実現するソフトウェアのプログラムコードを記憶した記憶媒体を、システム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）が記憶媒体に格納されたプログラムコードを読み出し実行することによっても、達成されることは言うまでもない。この場合、記憶媒体から読み出されたプログラムコード自体が本発明の新規な機能を実現することになり、そのプログラムコードを記憶した記憶媒体及びプログラムは本発明を構成することになる。
【０１０５】
また、プログラムコードを供給するための記憶媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭ等を用いることができる。
【０１０６】
また、コンピュータが読み出したプログラムコードを実行することにより、前述した実施の形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳ（オペレーティングシステム）等が実際の処理の一部または全部を行い、その処理によって前述した実施の形態の機能が実現される場合も含まれることは言うまでもない。
【０１０７】
更に、記憶媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵ等が実際の処理の一部または全部を行い、その処理によって前述した実施の形態の機能が実現される場合も含まれることは言うまでもない。
【図面の簡単な説明】
【０１０８】
【図１】第１の実施の形態に係る印刷装置の概要を示す図である。
【図２】第１の実施の形態に係る印刷装置における要素ツリーと構造体及びレイアウトの手順を示す図である。
【図３】第１の実施の形態に係る印刷装置におけるレイアウト構造体のデータ構成を説明する図である。
【図４】第１の実施の形態に係る印刷装置における各要素の種類とスタイル指定による配置ルールを説明する図である。
【図５】第１の実施の形態に係る印刷装置における要素の絶対配置における親子関係とボックスモデルを説明する図である。
【図６】第１の実施の形態に係る印刷装置における要素の絶対配置におけるボックスモデルの座標点を説明する図である。
【図７】第１の実施の形態に係る印刷装置における要素ツリーの一例を示す図である。配置手順の例を示す図である。
【図８】第１の実施の形態に係る印刷装置における要素の配置手順の一例を示す図である。
【図９】第１の実施の形態に係る印刷装置における要素ツリーの一例を示す図である。
【図１０】第１の実施の形態に係る印刷装置におけるレイアウト処理動作の流れを示すフローチャートである。
【図１１】第１の実施の形態に係る印刷装置におけるレイアウトの結果を示す図である。
【図１２】第１の実施の形態に係る印刷装置におけるボックスの配置モデル図である。
【図１３】第１の実施の形態に係る印刷装置におけるインライン要素を相対配置する図である。
【図１４】第１の実施の形態に係る印刷装置におけるブロック要素の配置モデル図である。
【図１５】第１の実施の形態に係る印刷装置におけるブロック要素を相対配置する図である。
【符号の説明】
【０１０９】
１００      印刷装置（プリンタ）
１０１      制御手段（コントローラ）
【図１】
2006103280.tif 000003
【図２】
2006103280.tif 000004
【図３】
2006103280.tif 000005
【図４】
2006103280.tif 000006
【図５】
2006103280.tif 000007
【図６】
2006103280.tif 000008
【図７】
2006103280.tif 000009
【図８】
2006103280.tif 000010
【図９】
2006103280.tif 000011
【図１０】
2006103280.tif 000012
【図１１】
2006103280.tif 000013
【図１２】
2006103280.tif 000014
【図１３】
2006103280.tif 000015
【図１４】
2006103280.tif 000016
【図１５】
2006103280.tif 000017