(57)【要約】【課題】レイアウトに適したコンテンツをカテゴリから効率よく選び出すことを目的とする。【解決手段】コンテンツ選択方法が、類似する複数のコンテンツをまとめて仮想コンテンツを生成する工程と、前記複数のコンテンツと前記仮想コンテンツとを木構造にまとめてコンテンツツリーを生成する工程と、前記コンテンツツリーを用いて、レイアウトに適したコンテンツ又は仮想コンテンツを選択する工程とを備えたことによって課題を解決する。【選択図】図２
2012155671.tif 000002
【特許請求の範囲】
【請求項１】
類似する複数のコンテンツをまとめて仮想コンテンツを生成する工程と、
前記複数のコンテンツと前記仮想コンテンツとを木構造にまとめてコンテンツツリーを生成する工程と、
前記コンテンツツリーを用いて、レイアウトに適したコンテンツ又は仮想コンテンツを選択する工程とを備えたことを特徴とするコンテンツ選択方法。
【請求項２】
類似する複数のコンテンツをまとめて仮想コンテンツを生成する手段と、
前記複数のコンテンツと前記仮想コンテンツとを木構造にまとめてコンテンツツリーを生成する手段と、
前記コンテンツツリーを用いて、レイアウトに適したコンテンツ又は仮想コンテンツを選択する手段とを備えたことを特徴とするコンテンツ選択装置。
【請求項３】
請求項１に記載のコンテンツ選択方法の各工程をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自動レイアウトに用いるコンテンツを選択する技術に関し、レイアウトに用いるコンテンツの選択にかかる処理時間をおさえる技術に関する。
【背景技術】
【０００２】
従来、与えられた画像や部分文書などのコンテンツを自動的にレイアウトして文書を作成する自動レイアウト技術がある。しかしながら、与えられたコンテンツが多い場合、与えられたコンテンツが掲載用のエリアにおさまらないこともある。このとき、文書を作成する装置等は、掲載するコンテンツを選び出すことが必要となる。
例えば、予めコンテンツに重要度を設定し、掲載する候補のコンテンツの組合せを変えてレイアウトを試行し、レイアウトと重要度との両面で適したコンテンツの組合せを求める方法が開示されている（特許文献１参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平１１−２８２８３４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ここで、コンテンツが選び出されてレイアウトが行われるとき、選ばれるコンテンツには異なる情報が含まれることが望まれる。例えば、製品情報に関して文書が作成されるとき、価格、スペック、最近のニュース等、いくつかの情報が含まれることが望まれる。
そのため、予めコンテンツをカテゴリに分けて、それぞれのカテゴリからレイアウトに適したコンテンツを選び出して文書を作成することが考えられる。しかしながら、特許文献１では、このようにカテゴリに分けられたコンテンツからコンテンツを選び出すことは考慮されていないので、異なる方法が必要となる。
【０００５】
また、カテゴリからコンテンツを選び出すにあたり、単純な方法としては、選び出す組合せの全てのレイアウトを試行・評価し、最も評価がよいコンテンツの組合せを求めることが考えられる。
しかしながら、コンテンツ数が増加すると、その組合せも急激に増加するので、コンテンツを選び出す処理時間も長くなる。
【０００６】
本発明はこのような問題点に鑑みなされたもので、レイアウトに適したコンテンツをカテゴリから効率よく選び出すことを目的とする。
【課題を解決するための手段】
【０００７】
そこで、本発明に係るコンテンツ選択方法は、類似する複数のコンテンツをまとめて仮想コンテンツを生成する工程と、前記複数のコンテンツと前記仮想コンテンツとを木構造にまとめてコンテンツツリーを生成する工程と、前記コンテンツツリーを用いて、レイアウトに適したコンテンツ又は仮想コンテンツを選択する工程とを備えたことを特徴とする。
【発明の効果】
【０００８】
本発明によれば、レイアウトに適したコンテンツをカテゴリから効率よく選び出すことができる。
【図面の簡単な説明】
【０００９】
【図１】コンピュータ装置のハードウェア構成の一例を示す図である。
【図２】コンピュータ装置の機能構成の一例を示す図である。
【図３】コンテンツツリー生成処理に係るフローチャートの一例を示す図である。
【図４】コンテンツツリーの構成の一例を示す図である。
【図５】仮想コンテンツの構成の一例を示す図である。
【図６】コンテンツ評価選択処理に係るフローチャートの一例を示す図である。
【図７】コンテンツツリーの一例を示す図である。
【図８】候補コンテンツ拡張処理に係るフローチャートの一例を示す図である。
【図９】候補コンテンツ組合決定処理に係るフローチャートの一例を示す図である。
【図１０】仮想コンテンツのデータ構造の一例を示す図である。
【図１１】計算コストの算出式の一例を示す図である。
【図１２】計算コストの比較結果の一例を示す図である。
【発明を実施するための形態】
【００１０】
以下、本発明の実施形態について図面に基づいて説明する。なお、実施形態は、本発明を限定するものではなく、また、実施形態で説明されている全ての構成が本発明の課題を解決するための手段に必須であるとは限らない。
【００１１】
＜第１の実施形態＞
本実施形態を適用するコンピュータ装置１００について図１を参照して説明する。図１は、コンピュータ装置１００のハードウェア構成の一例を示す図である。なお、コンピュータ装置１００は、情報処理装置（コンピュータ）の一例である。
ＣＰＵ（Central Processing Unit）１０１は、コンピュータ装置１００全体を制御する。ＲＯＭ（Read Only Memory）１０２は、変更を必要としないプログラムやパラメータを格納する。ＲＡＭ（Random Access Memory）１０３は、外部装置などから供給されるプログラムやデータを一時記憶する。
外部記憶装置１０４は、コンピュータ装置１００に固定して設置されたハードディスクやメモリカード、着脱可能なフレキシブルディスク（ＦＤ）やCompact Disk（ＣＤ）等の光ディスク、磁気や光カード、ＩＣカード、メモリカードなどである。
【００１２】
入力デバイスインターフェイス１０５は、ユーザの操作を受け、データを入力するポインティングデバイスやキーボードなどの入力デバイス１０９とのインターフェイスである。出力デバイスインターフェイス１０６は、コンピュータ装置１００の保持するデータや供給されたデータを表示するためのモニタやプリンタなどの出力デバイス１１０とのインターフェイスである。
通信インターフェイス１０７は、インターネットなどのネットワーク回線１１１に接続するためのネットワークインターフェイスである。システムバス１０８は、各ユニット（１０１〜１０７）を通信可能に接続する。
【００１３】
ここで、本実施形態のコンテンツ選択方法に係る文書作成プログラムは、外部記憶装置１０４に格納されており、ＣＰＵ１０１によって実行される。ＣＰＵ１０１が、外部記憶装置１０４に格納された文書作成プログラムの手順に従って処理を行うことによって、コンピュータ装置１００における機能及び後述するフローチャートに係る処理が実現される。なお、文書作成プログラムは、ＲＯＭ１０２に格納されていてもよい。
例えば、コンピュータ装置１００は、文書作成プログラムを実行し、予めカテゴリごとに分類したコンテンツに係る各種の情報を保持する。そして、コンピュータ装置１００は、指定された複数のカテゴリから、それぞれ指定された数のコンテンツを選び出し、文書を作成する。このとき、コンピュータ装置１００は、レイアウトに適したコンテンツを選び出す。
【００１４】
コンピュータ装置１００の機能について図２を用いて説明する。図２は、コンピュータ装置１００の機能構成の一例を示す図である。
コンテンツ管理部２０１は、カテゴリ分けされたコンテンツを管理（外部記憶装置１０４に保管など）する。
本実施形態において、コンテンツは、文書の一部を静止画像として切り出した画像データである。例えば、Ｗｅｂページの一部分が矩形領域により指定され、該矩形領域の文書の描画イメージを静止画像として得られる画像データである。しかしながら、コンテンツは、写真などの画像であってもよく、コンテンツは、これらに限定されない。
また、カテゴリは、コンテンツのグループを表す。本実施形態において、カテゴリは、コンテンツに含まれる情報によった分類である。例えば、「価格」、「スペック」、「ニュース」等のカテゴリがある。
【００１５】
また、コンテンツ管理部２０１は、コンテンツの外接矩形領域のサイズも保持して管理する。本実施形態において、コンテンツやカテゴリなどのコンテンツ管理部２０１で保持される情報は、外部記憶装置１０４に記憶されている。或いは、コンテンツ管理部２０１で保持される情報は、ネットワーク上の情報処理装置に記憶され、通信インターフェイス１０７を介して取得されてもよい。本実施形態におけるコンテンツの管理方法は、これらに限定されない。
カテゴリ取得部２０２は、入力デバイス１０９より指定されるコンテンツを選び出すカテゴリの情報を得る。より具体的には、カテゴリ取得部２０２は、コンテンツを選び出す複数のカテゴリと、それぞれのカテゴリから選び出すコンテンツの数（コンテンツ選出数）を得る。例えば、カテゴリは、「価格」、「スペック」、「ニュース」として得られる。また、例えば、コンテンツ選出数は、「価格」から１つ、「スペック」から１つ、「ニュース」から２つとして得られる。
【００１６】
文書情報取得部２０３は、入力デバイス１０９を介して文書の作成に必要な情報（テンプレート等）を得る。本実施形態において、文書の作成には、自動レイアウト技術が用いられる。本実施形態の自動レイアウト技術は、特許文献「特登録４０６５５４５号公報」に記載の方法により実現される。
前記特許文献に記載の自動レイアウト技術では、コンテンツを配置するための複数の部分領域を含むテンプレートが用いられる。加えて、テンプレートの各部分領域に配置するコンテンツとの対応付けも用いられる。そして、コンテンツが対応付いたテンプレートが用いられて、各々のコンテンツのサイズと配置とが決定されることで文書が生成される。
そのため、文書情報取得部２０３は、利用するテンプレートと、テンプレートの各部分領域に対していずれのカテゴリからコンテンツを配置するかを指定した情報を得る。
【００１７】
コンテンツツリー生成部２０４は、カテゴリごとのコンテンツを形状の類似度（形状類似度）により整理したコンテンツツリーを生成する。コンテンツツリー生成部２０４におけるコンテンツツリー生成処理の詳細については図３を用いて後述する。ここでは、コンテンツツリーについて図４（ｄ）を用いて説明する。図４（ｄ）は、５つのコンテンツからなるカテゴリのコンテンツツリーの一例を示す。
コンテンツツリーを表現するにあたり、「Ｃ」で始まる文字列が書かれた四角形は、コンテンツを表す。また、「Ｖ」で始まる文字列が書かれた網掛けされた四角形は、仮想コンテンツを表す。また、「Ｒ」で始まる文字列が書かれた円は、コンテンツツリーのルートノードを表す。
即ち、Ｃ１〜Ｃ５は、コンテンツであり、Ｖ１〜Ｖ３は、仮想コンテンツであり、Ｒ１は、ルートである。そして、これら要素の間の直線は、親子関係を表す。例えば、Ｖ１の子コンテンツは、Ｃ１及びＣ２である。
【００１８】
仮想コンテンツは、２つのコンテンツの形状を代表する領域である。ここで、図１０は、仮想コンテンツのデータ構造の一例を示す図である。ポインタ１００４及びポインタ１００５は、この仮想コンテンツが代表した２つのコンテンツを指し示す情報である。例えば、ポインタ１００４及びポインタ１００５の値は、異なるコンテンツへのメモリアドレス（ポインタ）である。
高さ１００１及び幅１００２は、仮想コンテンツの領域の高さと幅とを示す情報である。本実施形態において、仮想コンテンツは、２つのコンテンツの外接矩形として作成される領域である。そのため、高さ１００１及び幅１００２には、ポインタ１００４及びポインタ１００５の外接矩形の高さと幅とがそれぞれ記憶される。
【００１９】
また、形状類似度１００３は、２つのコンテンツ（ポインタ１００４及びポインタ１００５が指定するコンテンツ）の間の形状類似度を記憶する。形状類似度の算出方法、及び仮想コンテンツの作成方法については、図３を用いて説明する。
また、コンテンツツリー生成部２０４において実行されるコンテンツツリー生成処理によって作成されるコンテンツツリーは、カテゴリと対応付けられてＲＡＭ１０３に記憶される。或いは、外部記憶装置１０４に記憶されてもよい。本実施形態において、コンテンツツリーの記憶方法は、これらに限定されない。
【００２０】
コンテンツ評価選択部２０５は、それぞれのカテゴリから選び出すコンテンツを決定する。より具体的には、コンテンツ評価選択部２０５は、カテゴリ取得部２０２より得られたコンテンツ選出数と同数のコンテンツを、それぞれのカテゴリから選び出す。本実施形態では、この処理をコンテンツ評価選択処理と称し、その処理の詳細については図６を用いて説明する。
ここでは、例を挙げてコンテンツ評価選択処理を説明する。例えば、カテゴリとして、カテゴリａ、カテゴリｂ、及びカテゴリｃの３つがあるとする。そして、各カテゴリに対応するコンテンツツリーが図７に示すような構造をしている場合を想定する。
即ち、カテゴリａは、図７（ａ）に示すルートがＲａのコンテンツツリーと対応し、カテゴリｂは、図７（ｂ）に示すルートがＲｂのコンテンツツリーと対応し、カテゴリｃは、図７（ｃ）に示すルートがＲｃのコンテンツツリーと対応するものとする。
まず、コンテンツ評価選択部２０５がカテゴリから選び出すコンテンツを求めるにあたり、その候補となるコンテンツを候補コンテンツと称することにする。候補コンテンツは、カテゴリごとに存在し、実際のコンテンツ又は仮想コンテンツの集合である。
【００２１】
はじめに、コンテンツ評価選択部２０５は、候補コンテンツを、コンテンツツリーのルートの子コンテンツにより初期化する（Ｓ６０１）。例えば、コンテンツ評価選択部２０５は、図７に示す３つのコンテンツツリーからは、候補コンテンツを、各カテゴリに対応して「Ｖａ５、Ｖｂ６」、「Ｖｂ５、Ｖｂ６」、「Ｖｃ２、Ｖｃ３」として初期化する。
次に、コンテンツ評価選択部２０５は、候補コンテンツを、コンテンツツリーのルートから順に、コンテンツ選出数より１つ多めにコンテンツ（又は仮想コンテンツ）を選び出すことで拡張する（Ｓ６０２）。
例えば、コンテンツ評価選択部２０５は、各カテゴリから１つずつコンテンツを選び出すとき（つまりコンテンツ選出数が「１」のとき）、各候補コンテンツの要素数が「２」となるように拡張する。ただし、図７を用いた例では、候補コンテンツは、初期化によって２つずつあるので、候補コンテンツの拡張として具体的な処理は行われず、「Ｖａ５、Ｖｂ６」、「Ｖｂ５、Ｖｂ６」、「Ｖｃ２、Ｖｃ３」のままとなる。
【００２２】
次に、コンテンツ評価選択部２０５は、候補コンテンツをレイアウトに適したコンテンツ（又は仮想コンテンツ）のみに絞り込む（Ｓ６０３）。これは、候補コンテンツから選び出す組合せ全てのレイアウトを試行・評価することで求められる。例えば、コンテンツ評価選択部２０５は、８通りの組合せの各々についてレイアウトを試行・評価する。８通りとは「Ｖａ５、Ｖｂ５、Ｖｃ２」、「Ｖａ５、Ｖｂ５、Ｖｃ３」、「Ｖａ５、Ｖｂ６、Ｖｃ２」、「Ｖａ５、Ｖｂ６、Ｖｃ３」、「Ｖａ６、Ｖｂ５、Ｖｃ２」、「Ｖａ６、Ｖｂ５、Ｖｃ３」、「Ｖａ６、Ｖｂ６、Ｖｃ２」、「Ｖａ６、Ｖｂ６、Ｖｃ３」である。より詳細なレイアウトの試行・評価方法については後述する。
これによって、コンテンツ評価選択部２０５は、最もよいレイアウトが得られる組合せを求める。その結果、例えば、候補コンテンツは、最適なレイアウトの組合せである「Ｖａ６、Ｖｂ５、Ｖｃ２」となる。
次に、コンテンツ評価選択部２０５は、仮想コンテンツを含むと判断した場合、候補コンテンツを拡張する処理を行い、他方、全てが実際のコンテンツであると判断した場合、処理を終了する（Ｓ６０４）。先の例では、候補コンテンツは、Ｖａ６、Ｖｂ５、及びＶｃ２であり、仮想コンテンツが含まれているので処理が継続され、候補コンテンツの拡張が行われる。
【００２３】
コンテンツ評価選択部２０５は、候補コンテンツの拡張として、前述のとおり、コンテンツ選出数より１つ多めにコンテンツ（又は仮想コンテンツ）を選び出すことで拡張する。より具体的には、コンテンツ評価選択部２０５は、形状類似度が低い仮想コンテンツの代わりに、その仮想コンテンツの子コンテンツを候補コンテンツに加えることで、候補コンテンツを拡張する。
例えば、コンテンツ評価選択部２０５は、候補コンテンツの拡張としては、形状類似度が低い仮想コンテンツを得るが、ここでは仮想コンテンツが１つしかないので形状類似度に関わらず、Ｖａ６を選ぶ。そして、コンテンツ評価選択部２０５は、Ｖａ６の子コンテンツであるＶａ４及びＶａ２を得る。その結果、候補コンテンツは、「Ｖａ４、Ｖａ２」となる。同様に、Ｖｂ５及びＶｃ２に対しても拡張が行われる。その結果、先の例において、候補コンテンツは、「Ｖａ４、Ｖａ２」、「Ｖｂ４、Ｃｂ８」、「Ｃｃ４、Ｃｃ５」となる。
【００２４】
次に、再び候補コンテンツの絞込みが行われる。より具体的には、８通りの組合せのレイアウトを試行・評価して選び出す。その結果、例えば、候補コンテンツは、最適レイアウトの組合せである「Ｖａ２、Ｃｂ８、Ｃｃ５」となる。
しかしながら、未だ仮想コンテンツを含む候補コンテンツがあるので、処理が継続され、候補コンテンツの拡張が行われる。候補コンテンツの拡張では、仮想コンテンツを含む候補コンテンツＶａ２については拡張が行われて、候補コンテンツがＣｃ４及びＣｃ５となる。一方で、候補コンテンツＣｂ８、Ｃｃ５には仮想コンテンツが含まれないので、候補コンテンツの拡張は行われない。その結果、候補コンテンツは、「Ｃｃ４、Ｃｃ５」、Ｃｂ８、及びＣｃ５となる。
【００２５】
さらに、再び候補コンテンツの絞込みが行われる。より具体的には、２通りの組合せのレイアウトを試行・評価して選び出す。その結果、例えば、候補コンテンツは、最適レイアウトの組合せである「Ｃｃ４、Ｃｂ８、Ｃｃ５」となる。このとき、候補コンテンツには、仮想コンテンツが含まれない。そのため、候補コンテンツとして残ったコンテンツが、コンテンツ評価選択部２０５で求めるコンテンツとなり、処理が終了される。
このように、コンテンツ評価選択部２０５では、候補コンテンツの拡張と絞込みにより、候補コンテンツがコンテンツツリー上を葉へ向かって辿ることになる。最終的に、それぞれのコンテンツツリーにおいて、候補コンテンツは、葉（実際のコンテンツ）に到達する。このようにして、コンテンツ評価選択部２０５は、コンテンツを決定する。
コンテンツ評価選択部２０５において求められたコンテンツは、カテゴリと対応付けられてＲＡＭ１０３に記憶される。或いは、外部記憶装置１０４に記憶されてもよい。本実施形態において、選び出されたコンテンツの記憶方法は、これらに限定されない。
【００２６】
文書作成部２０９は、コンテンツ評価選択部２０５よりコンテンツを得て文書を作成する。より具体的には、文書作成部２０９は、コンテンツ評価選択部２０５よりコンテンツを得て、コンテンツ評価選択処理の過程で求められたコンテンツの配置を得る。そして、文書作成部２０９は、コンテンツとレイアウトとを元に、ＰＤＦなどの電子文書を作成して外部記憶装置１０４に保存する。
ここで、例えば、出力デバイスインターフェイス１０６に接続されたプリンタに電子文書が出力される構成としてもよい。また、例えば、作成される電子文書の描画イメージがモニタに表示される構成としてもよい。即ち、本実施形態において、電子文書の作成方法、及びその出力方法は、これらに限定されない。
【００２７】
コンテンツツリー生成部２０４が、あるカテゴリのコンテンツからコンテンツツリーを生成するコンテンツツリー生成処理について図３を用いて説明する。図３は、コンテンツツリー生成処理に係るフローチャートの一例を示す図である。
コンテンツツリー生成処理は、コンテンツツリー生成部２０４により、カテゴリ取得部２０２より得たカテゴリのそれぞれに対して実行される。また、コンテンツツリー生成処理では、処理の開始時に、あるカテゴリのコンテンツの集合をコンテンツグループとして与えられる。例えば、図４（ａ）に示す５つのコンテンツＣ１〜Ｃ５が与えられる。
【００２８】
Ｓ３０１では、コンテンツツリー生成部２０４は、コンテンツグループを構成するコンテンツの数が２つ以下であるか否かを判断する。このとき、コンテンツツリー生成部２０４は、コンテンツ数が２つ以下であると判断した場合、Ｓ３０５の処理を行う。他方、コンテンツツリー生成部２０４は、コンテンツ数が２つより多いと判断した場合、Ｓ３０２の処理を行う。例えば、図４（ａ）に示すコンテンツＣ１〜Ｃ５がコンテンツグループであるとき、５つのコンテンツからなるので、Ｓ３０２の処理が行われる。
Ｓ３０２では、コンテンツツリー生成部２０４は、コンテンツグループ内において、最も形状類似度が大きいコンテンツの組合せを特定する。より具体的には、コンテンツツリー生成部２０４は、コンテンツグループを構成するコンテンツから２つのコンテンツを選ぶ組合せ全てについて、形状類似度を計算する。そして、コンテンツツリー生成部２０４は、最も形状類似度が大きい２つのコンテンツを得る。
【００２９】
ここで、形状類似度は、コンテンツ間の形状の類似性を測る指標である。形状類似度は、形状が類似していると判断されるほど大きな値をとる。本実施形態における２つのコンテンツ間の形状類似度は、次のように算出される。
まず、コンテンツツリー生成部２０４は、２つのコンテンツの左上頂点を一致させてコンテンツを重ねる。このとき、コンテンツツリー生成部２０４は、コンテンツの回転については行わない。そして、コンテンツツリー生成部２０４は、両コンテンツが重なる領域の面積を、コンテンツの両方ともに外接する矩形領域の面積で割った値を形状類似度とする。
図５の例を用いてより詳細に説明する。コンテンツ５０１とコンテンツ５０２とは、形状類似度を計算する対象の２つのコンテンツである。コンテンツ５０１及びコンテンツ５０２の左上頂点を一致させたときの重なる領域は、領域５０３（斜線部）である。そして、両コンテンツに外接する矩形領域は、外接矩形領域５０４（太線枠）である。
よって、領域５０３の面積を外接矩形領域５０４の面積で割ったものが形状類似度となる。なお、形状類似度の算出方法は、コンテンツのアスペクト比率の差などとしてもよい。例えば、コンテンツツリー生成部２０４が、両コンテンツの上辺のアスペクト比率を得て、その差の絶対値の逆数などを求めることが考えられる。本実施形態において、形状類似度の算出方法は、これらに限定されるものではない。
【００３０】
Ｓ３０３では、コンテンツツリー生成部２０４は、Ｓ３０２で得た２つのコンテンツの形状を代表する仮想コンテンツを作成する。より具体的には、コンテンツツリー生成部２０４は、Ｓ３０２で得た２つのコンテンツの左上頂点を重ねたときの外接矩形領域を仮想コンテンツとして作成する。例えば、図５に示すコンテンツ５０１とコンテンツ５０２とを重ねたとき、外接矩形領域５０４が仮想コンテンツとして作成される。
そして、コンテンツツリー生成部２０４は、仮想コンテンツの子コンテンツとして、Ｓ３０２で得たコンテンツを関連付けて記憶する。さらに、コンテンツツリー生成部２０４は、仮想コンテンツを、Ｓ３０２で求めた形状類似度を関連付けて記憶する。例えば、Ｓ３０２において、図４（ａ）に示す５つのコンテンツの間でＣ１及びＣ２の形状類似度が最も大きいとき、図４（ｂ）に示すように仮想コンテンツＶ１が生成されて、Ｃ１及びＣ２が子コンテンツとなるように関連付けられる。
なお、仮想コンテンツとして作成する領域については、両コンテンツの面積を一致させてから作成するなどしてもよい。本実施形態において、仮想コンテンツの作成方法は、これらに限定されるものではない。
【００３１】
Ｓ３０４では、コンテンツツリー生成部２０４は、コンテンツグループからＳ３０２で得たコンテンツを取り除き、Ｓ３０３で得た仮想コンテンツを加える。
例えば、図４（ａ）に示すようにコンテンツグループがＣ１〜Ｃ５とする。このとき、Ｓ３０３において、図４（ｂ）に示すようにコンテンツＣ１及びＣ２をまとめて、仮想コンテンツＶ１が作成された場合、コンテンツグループは、Ｖ１、Ｃ３、Ｃ４、及びＣ５となる。
コンテンツツリー生成部２０４は、Ｓ３０４の処理が終わると、Ｓ３０１の処理を行い、コンテンツ数が２つ以下になるまでＳ３０２〜Ｓ３０４の処理を繰り返す。そして、コンテンツ数が２つ以下となると、Ｓ３０５の処理が行われる。
Ｓ３０５では、コンテンツツリー生成部２０４は、コンテンツグループを構成するコンテンツや仮想コンテンツを、コンテンツツリーのルートの子コンテンツとして関連付けて記憶する。例えば、図４（ｃ）に示すＶ３及びＶ２がコンテンツグループを構成するとき、Ｖ３及びＶ２を子コンテンツとするルートが割り当てられ、図４（ｄ）に示すコンテンツツリーが得られることになる。
【００３２】
コンテンツ評価選択部２０５が複数のカテゴリから選び出すコンテンツを決定するコンテンツ評価選択処理について図６を用いて説明する。図６は、コンテンツ評価選択処理に係るフローチャートの一例を示す図である。コンテンツ評価選択処理は、コンテンツ評価選択部２０５において実行される。
Ｓ６０１の候補コンテンツ初期化処理では、コンテンツ評価選択部２０５は、それぞれのカテゴリの候補コンテンツを初期化する。より具体的には、コンテンツ評価選択部２０５は、カテゴリ取得部２０２よりカテゴリを得る。そして、コンテンツ評価選択部２０５は、カテゴリごとに、対応するコンテンツツリーを得て、そのルートの子コンテンツを候補コンテンツとする。また、候補コンテンツは、カテゴリごとに区別されて記憶される。
【００３３】
例えば、カテゴリが３つ存在し、図７に示す３つのコンテンツツリーがある場合について説明する。ルートノードＲａのコンテンツツリーからは、候補コンテンツとしてＶａ６及びＶａ５が得られることになる。ルートノードＲｂのコンテンツツリーからは、候補コンテンツとしてＶｂ６及びＶｂ５が得られることになる。ルートノードＲｃのコンテンツツリーからは、候補コンテンツとしてＶｃ３及びＶｃ２が得られることになる。そのため、カテゴリごとに候補コンテンツ「Ｖａ５、Ｖｂ６」、「Ｖｂ５、Ｖｂ６」、「Ｖｃ２、Ｖｃ３」が得られることになる。
Ｓ６０２の候補コンテンツ拡張処理では、コンテンツ評価選択部２０５は、候補コンテンツ数と、コンテンツ選出数に「１」を加えた数とが同じとなるように、候補コンテンツを拡張する。より具体的には、コンテンツ評価選択部２０５は、カテゴリ取得部２０２からコンテンツ選出数を得る。そして、これに「１」を加えた数となるように、候補コンテンツを拡張する。候補コンテンツの拡張は、候補コンテンツのうち最も形状類似度が小さい仮想コンテンツの子コンテンツを候補コンテンツとすることで行われる。候補コンテンツ拡張処理の詳細については図８を用いて後述する。
【００３４】
Ｓ６０３の候補コンテンツ組合決定処理では、コンテンツ評価選択部２０５は、候補コンテンツからレイアウトに適した組合せを選び出す。候補コンテンツ組合決定処理の詳細については図９を用いて後述する。
次に、Ｓ６０４では、コンテンツ評価選択部２０５は、候補コンテンツに仮想コンテンツが含まれるか否かを判断する（コンテンツ決定判定処理）。このとき、コンテンツ評価選択部２０５は、仮想コンテンツが含まれないと判断した場合、処理を終了し、他方、仮想コンテンツが含まれると判断した場合、Ｓ６０２の処理を行う。
【００３５】
候補コンテンツ拡張処理について図８を用いて説明する。図８は、候補コンテンツ拡張処理に係るフローチャートの一例を示す図である。
Ｓ８０１では、コンテンツ評価選択部２０５は、カテゴリ取得部２０２より得たカテゴリの全てに対して処理を終えたか否かを判定する。処理済みであるか否かの判定は、カテゴリごとに処理済みを示すフラグなどを設け、全てのフラグがＯＮである場合、処理済みとして判断される。
このとき、コンテンツ評価選択部２０５は、未処理のカテゴリがあると判断した場合、該カテゴリの処理済みを示すフラグなどをＯＮとし、Ｓ８０２の処理を行い、未処理のカテゴリがないと判断した場合、本処理を終了する。
【００３６】
Ｓ８０２では、コンテンツ評価選択部２０５は、Ｓ８０１で得た未処理のカテゴリに対応する候補コンテンツを得る。Ｓ８０３では、コンテンツ評価選択部２０５は、カテゴリ取得部２０２から未処理のカテゴリに対応するコンテンツ選出数を得る。
Ｓ８０４では、コンテンツ評価選択部２０５は、Ｓ８０３で得たコンテンツ選出数に「１」を加えた数の候補コンテンツが存在するか否かを判断する。このとき、コンテンツ評価選択部２０５は、候補コンテンツの数が十分であると判断した場合、Ｓ８０１の処理を行い、他方、候補コンテンツの数が不十分であると判断した場合、Ｓ８０５の処理を行う。ただし、候補コンテンツに仮想コンテンツが含まれない場合、コンテンツ評価選択部２０５は、候補コンテンツの数が不十分であってもＳ８０１の処理を行う。
【００３７】
Ｓ８０５では、コンテンツ評価選択部２０５は、Ｓ８０２で得た候補コンテンツの中から、最も形状類似度が低い仮想コンテンツを特定する。そして、コンテンツ評価選択部２０５は、候補コンテンツから該仮想コンテンツを除き、該仮想コンテンツの子コンテンツを候補コンテンツに加える。
これにより仮想コンテンツは、コンテンツツリー上において、より実際のコンテンツに近い異なる仮想コンテンツへと置き換えられる。或いは、仮想コンテンツは、実際のコンテンツへと置き換えられる。
【００３８】
例えば、Ｓ８０２において、図７（ａ）に示すルートノードＲａのコンテンツツリーのＶａ５及びＶａ６が、候補コンテンツとして得られたとする。このとき、Ｓ８０３で得たコンテンツ選出数が「２」である場合、Ｓ８０４では、３つの候補コンテンツが存在するか否かが判断される。
この場合は２つであるので、存在しないと判断され、Ｓ８０５の処理が行われる。Ｓ８０５では、３つの候補コンテンツが選び出される。このとき、Ｖａ５に比べてＶａ６の形状類似度が小さいとする。この場合、Ｖａ６の代わりに、子コンテンツであるＶａ２及びＶａ４が候補コンテンツに加えられる。その結果としてＶａ２とＶａ４とＶａ５とが候補コンテンツとなる。
【００３９】
候補コンテンツ組合決定処理の詳細について図９を用いて説明する。図９は、候補コンテンツ組合決定処理に係るフローチャートの一例を示す図である。
Ｓ９０１では、コンテンツ評価選択部２０５は、カテゴリ取得部２０２より得たカテゴリの全てに対応する候補コンテンツを取得する。例えば、図７に示す「Ｖａ５、Ｖａ６」、「Ｖｂ５、Ｖｂ６」、「Ｖｃ２、Ｖｃ３」がカテゴリのそれぞれの候補コンテンツであるとき、これらが得られることになる。
Ｓ９０２では、コンテンツ評価選択部２０５は、Ｓ９０１で取得した候補コンテンツの組合せごとにレイアウトを評価する。例えば、Ｓ９０１において、図７に示す「Ｖａ５、Ｖａ６」、「Ｖｂ５、Ｖｂ６」、「Ｖｃ２、Ｖｃ３」が候補コンテンツとして選ばれているとする。このとき、組合せとして８通りのコンテンツの組合せがある。８通りとは「Ｖａ５、Ｖｂ５、Ｖｃ２」、「Ｖａ５、Ｖｂ５、Ｖｃ３」、「Ｖａ５、Ｖｂ６、Ｖｃ２」、「Ｖａ５、Ｖｂ６、Ｖｃ３」、「Ｖａ６、Ｖｂ５、Ｖｃ２」、「Ｖａ６、Ｖｂ５、Ｖｃ３」、「Ｖａ６、Ｖｂ６、Ｖｃ２」、「Ｖａ６、Ｖｂ６、Ｖｃ３」である。
【００４０】
コンテンツ評価選択部２０５は、これらの組合せごとにコンテンツを自動レイアウト技術によりレイアウトする。自動レイアウトは、前述の文書情報取得部２０３において説明した特許文献の技術を用いて行う。そして、コンテンツ評価選択部２０５は、文書領域のうちのコンテンツが利用する領域の割合によりレイアウトを評価する。
なお、コンテンツ評価選択部２０５は、コンテンツの配置の対象性や、辺の揃い具合などを考慮してレイアウトを評価してもよい。本実施形態におけるレイアウト評価方法は、これらに限定されるものではない。
そして、コンテンツ評価選択部２０５は、最もレイアウトの評価がよい候補コンテンツの組合せを特定する。
【００４１】
Ｓ９０３では、コンテンツ評価選択部２０５は、Ｓ９０２で得た候補コンテンツの組合せを、それぞれのカテゴリの候補コンテンツとする。例えば、Ｓ９０１において、「Ｖａ５、Ｖａ６」、「Ｖｂ５、Ｖｂ６」、「Ｖｃ２、Ｖｃ３」が候補コンテンツとして選ばれているとする。このとき、Ｓ９０２において「Ｖａ６、Ｖｂ５、Ｖｃ２」の組合せが選ばれたとする。この場合、Ｓ９０３においては、Ｖａ６、Ｖｂ５、及びＶｃ２がカテゴリのそれぞれの候補コンテンツとなる。
以上の処理によれば、カテゴリのそれぞれからレイアウトに適したコンテンツを選び出すことができる。
【００４２】
本実施形態では、特に、カテゴリのそれぞれからコンテンツを選び出す全ての組合せのレイアウトを評価する場合と比べ、仮想コンテンツをレイアウトすることで、実際のコンテンツをレイアウトする回数を減らすことができる。その結果、レイアウトに適したコンテンツを選び出す処理時間を短縮することができる。
以下では、本実施形態のコンテンツ選択方法の場合と、コンテンツの組合せ全てのレイアウトを試行・評価し、最も評価がよいコンテンツの組合せを求める場合とにおける計算コストについてより具体的に説明する。なお、前者を本手法、後者を比較手法と表記する。
計算コストを求めるにあたり、カテゴリごとのコンテンツ数は同じであり、カテゴリから選び出すコンテンツ数も同じであるとする。このとき、本手法及び比較手法による計算コストは、図１１（ａ）に示す式を用いて算出される。なお、各変数の定義は、図１１（ｃ）に示すとおりである。
【００４３】
本手法の計算コストについてより詳細に説明する。本手法は、大きく分けてコンテンツツリー生成処理とコンテンツ評価選択処理とに分けることができる。図１１（ａ）の第１項が前者の計算コストにあたり、第２項が後者の計算コストにあたる。
まず、コンテンツツリー生成処理の計算コスト（第１項）について説明する。
図３に示すコンテンツツリー生成処理では、コンテンツ数の増加にともない、Ｓ３０２〜Ｓ３０４の処理の回数が増加する。この中でも、Ｓ３０２の最も形状類似度が大きいコンテンツの組合せを求める部分では、２つのコンテンツ間の形状類似度を求める計算が、コンテンツ数の二乗の回数繰り返される。そのため、形状類似度の計算コストがコンテンツツリー生成処理の大部分を占めると考えられる。
よって、コンテンツツリー生成処理の計算コストは、カテゴリごとのコンテンツ数ｎ、形状類似度の計算コストＳとしたとき、Ｓ×ｎ3となる。さらに、カテゴリごとにコンテンツツリーを作ることから、カテゴリ数ｇとしたとき、全コンテンツツリーを生成するための計算コストは、およそｇ×Ｓ×ｎ3となる。
【００４４】
次に、コンテンツ評価選択処理の計算コスト（第２項）について説明する。図６に示すコンテンツ評価選択処理のＳ６０２〜Ｓ６０４のうち、レイアウト試行・評価が伴うＳ６０３が最も計算コストがかかる。
Ｓ６０３では、カテゴリからＭ個の候補コンテンツを選び出す組合せ全てのレイアウトについて試行が行われる。そのため、レイアウトの試行・評価にかかる計算コストＬ、コンテンツ選出数に「１」を加えた数をＭとしたとき、Ｓ６０３の候補コンテンツ組合決定処理の計算コストは、Ｌ×Ｍgとなる。
また、Ｓ６０３の処理は、候補コンテンツが実際のコンテンツとなるまで繰り返される。この繰り返しの回数は、コンテンツツリーの高さをＨとしたとき、Ｍ−１個のコンテンツが実際のコンテンツになるまでコンテンツツリー上を徐々に辿っていくことを考えると、最大でＨ×（Ｍ−１）回の繰り返しが発生する。そのため、ここでは繰り返し回数を多めに見積もってＨ×（Ｍ−１）回と考える。なお、コンテンツツリーは、２分木となることから、Ｈは、ｌｏｇ2ｎ≦Ｈ≦ｎ−１の範囲の値をとる。
以上より、コンテンツ評価選択処理の計算コストは、およそＨ×（Ｍ−１）×Ｌ×Ｍgとなる。
【００４５】
続いて、比較手法の計算コストについて詳細に説明する。比較手法では、各カテゴリからコンテンツを選び出す全ての組合せに対して、レイアウトが試行・評価される。そのため、レイアウトを試行・評価する回数は、次のとおりになる。
まず、１つのカテゴリからコンテンツを選び出す組合せ数は、カテゴリを構成するコンテンツ数がｎ、カテゴリから選び出す数が（Ｍ−１）であることから、nＣM-1となる。そのため、各カテゴリからコンテンツを選び出す全ての組合せ数は（nＣM-1）gとなり、この回数だけレイアウト試行・評価が行われる。よって、比較手法の計算コストは、およそＬ×（nＣM-1）gとなる。
【００４６】
次に、本手法と比較手法との計算コストを比較する。
まず、カテゴリから選び出すコンテンツ数が１つであり、かつコンテンツツリーの高さＨが最も高いとき、つまりＭ＝２、Ｈ＝ｎ−１としたときの計算コストの差について説明する。このとき、比較手法と従来手法との計算コストは、図１１（ｂ）に示すようになる。
図１２に本手法と比較手法との計算コストの差（比較結果の一例）を示す。図１２では、Ｓ＝１、Ｌ＝１０００としたとき、比較手法の計算コストから本手法の計算コストを引いた値が示されている。そのため、正の値をとるとき、比較手法に比べて本手法の計算コストが小さいことを示す。図１２の灰色の欄は、本手法の計算コストが小さいところを示す。図１２によると、一部の範囲においては、比較手法が高速であるが、多くの範囲において本手法が高速であることが分かる。
【００４７】
また、ｇの値の範囲ごとにより詳細に両者を比較する。
まず、ｇ≧３である場合について説明する。本手法は、ｎが大きいとき、第１項が支配的となり第２項は無視できる。また、比較手法と比べると、Ｌは、Ｓより圧倒的に大きいことが予想できることから、本手法の速度が速いことが予想できる。ただし、ｎが小さいとき、本手法の第２項が無視できなくなることがある。例えば、図１２において、ｎ＝２において比較手法が早いことがこれにあたる。しかしながら、多くの範囲において本手法が高速であることが分かる。
【００４８】
次に、ｇ＝２においては、ｎが大きいときは、比較手法が高速である。しかしながら、実際は、ＬがＳに比べて圧倒的に大きいことから、ｎが一定数に至るまでは本手法が速いことがある。例えば、図１２においては、ｎが４００までは本手法が高速であることが示されている。
次に、ｇ＝１においては、本件が対象としている組合せの問題は生じないので、比較手法が高速となる。
以上より、Ｍ＝２の場合において、ほとんどの場合において本手法が高速であるといえる。また、Ｍが大きくなると、比較手法はより計算コストが増える。一方で、本手法も第２項が増える。しかしながら、比較手法の方が計算コストの増加は大きいと予想される。そのため、比較手法に比べて本手法がより高速になると考えられる。よって、本手法は比較手法に比べて、多くの場合において高速になることが分かる。
したがって、本実施形態によれば、コンテンツ数が多くなったとしても、処理時間をおさえながら、レイアウトに適したコンテンツを選び出すことができる。
【００４９】
＜第２の実施形態＞
第１の実施形態では、コンテンツツリー生成処理において、コンテンツツリーとしては２分木構造を採用した。しかしながら、完全な二分木とするとき、コンテンツツリーのルートに近づくほど、形状類似度が低下する。形状類似度が低下しすぎると、仮想コンテンツによるレイアウトが実際のコンテンツをレイアウトした場合と異なる可能性が大きくなり、仮想コンテンツによるレイアウトの妥当性が損なわれる。
そこで、本実施形態では、コンテンツツリーの生成時に、コンテンツ間の形状類似度がある閾値以下に低下したとき、仮想コンテンツを作成する処理が止められる。より具体的には、コンテンツツリー生成処理のＳ３０２の直後に、Ｓ３０２で得た形状類似度が閾値以下であるとき、Ｓ３０５の処理が行われるようにすることで実現される。
上述した構成によれば、仮想コンテンツと実際のコンテンツの形状とが大きく異なることがおさえられ、仮想コンテンツによるレイアウトの妥当性が損なわれることがなくなる。
【００５０】
＜第３の実施形態＞
第１の実施形態では、コンテンツツリー生成処理については、コンテンツ評価選択処理を行う直前に実行されることが想定されていた。しかしながら、この構成に限られるものではなく、本実施形態では、全てのカテゴリに対してコンテンツツリー生成処理が予め実行されている。
上述した構成によれば、コンテンツ評価選択処理のみを行えばよいので、より処理速度を向上することができる。
【００５１】
＜第４の実施形態＞
第１の実施形態では、自動レイアウトに利用するテンプレートについては指定されることを想定していた。しかしながら、この構成に限られるものでななく、本実施形態では、テンプレートを生成する、或いは予め用意しておいたテンプレートを利用するなどの方法により、テンプレートが得られる。
例えば、用紙サイズなどを得て、用紙サイズと配置するコンテンツ数から、マトリクス状に部分領域を作成するなどして、テンプレートが作成されてもよい。或いは、予めテンプレートを保持しておいて、それらが利用されるようにしてもよい。
このとき、テンプレートの部分領域とカテゴリとの対応は定まらない。そのため、適当な１つの対応付けを定めて処理されてもよい。或いは、候補コンテンツ組合決定処理においてレイアウトが試行されるとき、部分領域とカテゴリとの対応付けの組合せごとにレイアウトが試行され、最もよいレイアウトを与える対応付けが選択されるようにしてもよい。
上述した構成によれば、テンプレートを指定する必要がなくなる。
【００５２】
＜第５の実施形態＞
第１の実施形態では、予めカテゴリ分けされたコンテンツがコンテンツ管理部２０１に保持されている構成を採用した。しかしながら、この構成に限られるものではなく、例えば、文書作成プログラムは、カテゴリを作成する手段を含んでもよい。本実施形態では、例えば図２に示す構成にカテゴリ生成部が含まれる。
カテゴリ生成部により作成されるカテゴリは、ユーザが入力デバイス１０９を介して、明示的に示すコンテンツのグループであってもよい。
ここで、例えば、Ｗｅｂページから切り出された画像データである場合、切り出された領域内のテキスト情報などからキーワードなどのメタデータを抽出することができる。そこで、カテゴリ生成部は、コンテンツのカテゴリとしてメタデータを利用してもよい。例えば、カテゴリ生成部は、メタデータでコンテンツを検索し、その検索結果を１つのカテゴリとして扱ってもよい。
上述した構成によれば、様々なカテゴリが作成できるようになり、柔軟な文書の作成が可能となる。
【００５３】
＜第６の実施形態＞
第１の実施形態では、本手法と比較手法との速度について説明した。このとき、一部の場合において、比較手法が高速となることがあった。そこで、比較手法が早くなる場合においては、比較手法を用いてコンテンツを選択することが考えられる。
より具体的には、本実施形態では、図１１（ａ）に示す数式を用いて、計算コストの比較が行われる。そして、より少ない計算コストとなる手法が選択される。或いは、予めカテゴリ数が１つのときは比較手法を用いるなどの規則を用意しておき、規則に従って手法が選択されてもよい。
上述した構成によれば、本手法の速度が悪い場合において、比較手法が用いられることで、処理速度をより早くすることができる。
なお、本発明はコンピュータ内のプログラムによって実現できることは当然である。また、第１の実施形態から第６の実施形態までに示した構成については、適宜に組み合わせて採用することができる。
【００５４】
＜その他の実施形態＞
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（又はＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【００５５】
上述した実施形態の構成によれば、レイアウトに適したコンテンツをカテゴリから効率よく選び出すことができる。
【００５６】
以上、本発明の好ましい実施形態について詳述したが、本発明は係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００５７】
２０１  コンテンツ管理部、２０２  カテゴリ取得部、２０３  文書情報取得部、２０４  コンテンツツリー生成部、２０５  コンテンツ評価選択部、２０６  文書作成部
【図１】
2012155671.tif 000003
【図２】
2012155671.tif 000004
【図３】
2012155671.tif 000005
【図４】
2012155671.tif 000006
【図５】
2012155671.tif 000007
【図６】
2012155671.tif 000008
【図７】
2012155671.tif 000009
【図８】
2012155671.tif 000010
【図９】
2012155671.tif 000011
【図１０】
2012155671.tif 000012
【図１１】
2012155671.tif 000013
【図１２】
2012155671.tif 000014