(57)【特許請求の範囲】
【請求項１】
出力ページの各コマに、各コマの形状に合わせて原画像から切り出した画像をレイアウトする画像レイアウトのコマ割りを、ルートノードからのレイヤおよび各ノードから分岐するノードの数に従って水平分割または垂直分割を順次繰り返し、分岐しない終端のノードの葉をコマとして表現する順序木を生成する画像レイアウト用の順序木の生成方法であって
順序木に要求される葉数に、出力ページにレイアウトしようとする画像の数を設定し、
ルートノードから複数の子ノードを分岐させ、各子ノードを親ノードとして複数の子ノードを更に分岐させることを繰り返し、子ノードが分岐しないノードを葉とする複数の経路を探索し、探索中の経路ごとに、親ノードから子ノードを分岐させる際、生成済み葉数が前記要求される葉数に対して不足する葉数を算出し、前記不足する葉数を経路探索の継続により新たに生成できる葉数と比較し、前記新たに生成できる葉数が前記不足する葉数を満たせれば当該経路探索を継続し、満たせなければ当該経路探索を中止し、
前記生成済み葉数が前記要求される葉数を満足し、葉以外の全てのノードが複数に分岐する経路を順序木の構造として採用することを特徴とする画像レイアウト用の順序木の生成方法。
【請求項２】
探索中の経路ごとに、親ノードから子ノードを分岐させる際、当該子ノードが最初の分岐に係る第一子ノードおよび二回目以降の分岐に係る兄弟ノードのいずれであるかを識別し、
前記子ノードが第一子ノードであれば、その兄弟ノードをスタックし、
前記子ノードが兄弟ノードであれば、対応するスタックを消費し、
前記生成済み葉数が前記要求される葉数を満足し、前記スタックが消費されている経路を順序木の構造として採用することを特徴とする請求項１に記載の画像レイアウト用の順序木の生成方法。
【請求項３】
検索の深さごとに最大分岐数を設定し、各親ノードから子ノードへの分岐数が前記最大分岐数で制限されることを特徴とする請求項１または２に記載の画像レイアウト用の順序木の生成方法。
【請求項４】
検索の最大深さを設定し、各親ノードから子ノードへの分岐が前記最大深さで制限されることを特徴とする請求項１ないし３のいずれかに記載の画像レイアウト用の順序木の生成方法。
【請求項５】
出力ページの各コマに、各コマの形状に合わせて原画像から切り出した画像をレイアウトする画像レイアウトのコマ割りを、ルートノードからのレイヤおよび各ノードから分岐するノードの数に従って水平分割または垂直分割を順次繰り返し、分岐しない終端のノードの葉をコマとして表現する順序木を生成する画像レイアウト用の順序木の生成プログラムであって、
順序木に要求される葉数に、出力ページにレイアウトしようとする画像の数を設定し、
ルートノードから複数の子ノードを分岐させ、各子ノードを親ノードとして複数の子ノードを更に分岐させることを繰り返し、子ノードが分岐しないノードを葉とする複数の経路を探索し、探索中の経路ごとに、親ノードから子ノードを分岐させる際、生成済み葉数が前記要求される葉数に対して不足する葉数を算出し、前記不足する葉数を経路探索の継続により新たに生成できる葉数と比較し、前記新たに生成できる葉数が前記不足する葉数を満たせれば当該経路探索を継続し、満たせなければ当該経路探索を中止し、
前記生成済み葉数が前記要求される葉数を満足し、葉以外の全てのノードが複数に分岐する経路を順序木の構造として採用することを、コンピュータに実行させる画像レイアウト用の順序木生成プログラム。
【請求項６】
探索中の経路ごとに、親ノードから子ノードを分岐させる際、当該子ノードが最初の分岐に係る第一子ノードおよび二回目以降の分岐に係る兄弟ノードのいずれであるかを識別し、
前記子ノードが第一子ノードであれば、その兄弟ノードをスタックし、
前記子ノードが兄弟ノードであれば、対応するスタックを消費し、
生成済み葉数が前記要求される葉数を満足し、前記スタックが消費されている経路を順序木の構造として採用することを特徴とする請求項５に記載の画像レイアウト用の順序木の生成プログラム。
【請求項７】
出力ページの各コマに、各コマの形状に合わせて原画像から切り出した画像をレイアウトする画像レイアウトのコマ割りを、ルートノードからのレイヤおよび各ノードから分岐するノードの数に従って水平分割または垂直分割を順次繰り返し、分岐しない終端のノードの葉をコマとして表現する順序木を生成する画像レイアウト用の順序木の生成装置であって、
順序木に要求される葉数に、出力ページにレイアウトしようとする画像の数を設定する手段と、
ルートノードから複数の子ノードを分岐させ、各子ノードを親ノードとして複数の子ノードを更に分岐させることを繰り返し、子ノードが分岐しないノードを葉とする複数の経路を探索し、探索中の経路ごとに、親ノードから子ノードを分岐させる際、生成済み葉数が前記要求される葉数に対して不足する葉数を算出し、この葉数を経路探索の継続により新たに生成できる葉数と比較し、前記新たに生成できる葉数が前記不足する葉数を満たせれば当該経路探索を継続し、満たせなければ当該経路探索を中止する手段と、
前記生成済み葉数が前記要求される葉数を満足し、葉以外の全てのノードが複数に分岐する経路を順序木の構造として採用する手段とを具備したことを特徴とする画像レイアウト用の順序木の生成装置。
【請求項８】
探索中の経路ごとに、親ノードから子ノードを分岐させる際、当該子ノードが最初の分岐に係る第一子ノードおよび二回目以降の分岐に係る兄弟ノードのいずれであるかを識別する手段と、
前記子ノードが第一子ノードであれば、その兄弟ノードをスタックし、前記子ノードが兄弟ノードであれば、対応するスタックを消費する手段と、
生成済み葉数が前記要求される葉数を満足し、かつ前記スタックが消費されている経路を順序木の構造として採用する手段とをさらに具備したことを特徴とする請求項７に記載の画像レイアウト用の順序木の生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像レイアウト用のコマ割りに好適な順序木の生成方法、生成プログラムおよび生成装置に係り、特に、コマに対応する葉の数が要求数を満足できる多数の順序木を高速に生成できる画像レイアウト用の順序木の生成方法、生成プログラムおよび生成装置に関する。
【背景技術】
【０００２】
コマ割りされた出力ページ（レイアウトテンプレート）の各コマに、原画像から各コマ形状に合わせて切り出した画像を貼り付ける画像レイアウトが注目されている。特許文献１，２および非特許文献１には、複数のレイアウト画像を所定の順序を保ってコミック風にレイアウトする技術が開示されている。特許文献２および非特許文献２には、画像レイアウトを木構造で表現する方法が開示されている。非特許文献３には、画像レイアウトとは関係のない一般的な根付き順序木（rooted plane trees）の効率的な列挙法が開示されている。これを拡張することで、画像レイアウトに用いることができと考えられる。また、根付き木（rooted trees）の列挙法もあるが、これはルートノードに対して左右同じ形である場合を区別しないため、網羅的なレイアウトの生成には適さない。非特許文献４には、直径を持つ木（trees）の効率的な列挙法が開示されている。ここでは、生成された木から次の順序木を生成する際、ノードの追加と削除により順序木を高速に生成する技術が開示されており、ノードの深さ列を用いて木が表現されている。非特許文献５には、コミックのレイアウトを根付き木で表現できる事実を述べており，コミックをスキャンした画像の木構造を分析する技術が開示されている。非特許文献３では、最も右側のパス上の各々のノードに、新たにノードを追加することで、全ての根付き木(rooted plane tree)を効率的に生成できることが述べられており、一般的に最右拡張と呼ばれる。最右拡張は様々な実装が考えられると思われるが、チューリングマシンのようにメモリとヘッドを用いて木を列挙することで高速に生成できると考えられる。図９はそのフローチャートであり、ここでは、図１０に示したように、頂点数（ノード数）が「５」の順序木を網羅的に生成する方法を例にして説明するものとし、各ノード（○印）は、根となるルートノードへの単一の経路を辿れる。図１１に示したように、各ノードからルートノードへ至る枝の数がk本ならば、当該ノードの深さ（レイヤ）はkとなる。木の表現は非特許文献５と同様に、ノードの深さ列を用いている。
【０００３】
図９において、ステップＳ５１では、順序木の構造を表現する数値列が記憶されるメモリテーブルMに初期値が登録される。本実施形態では、図１２(a)に一例をしたように、メモリテーブルMのアドレスi=0に「０」、i=1に「１」，i=2に「０」，i=3に「０」，i=4に「０」…が登録される。ステップＳ５２では、図１２(b)に示したように、メモリテーブルM上で注目ノードを指定するためのヘッド位置headが「１」に設定される。ステップＳ５３では、ヘッド位置headに対応したメモリ値M(head)が、注目ノードのレイヤを代表する変数uに登録される。ここでは、ヘッド位置head（＝１）のメモリ値M(head)が「１」なのでu＝１となる。ステップＳ５４では、ヘッド位置headにプラス「１」した値[head＋１]のメモリ値M(head+1)にプラス「１」した値が、新たに分岐させようとする子ノードの分岐先のレイヤを代表する変数vに登録される。ここでは、メモリ値M(head+1)が「０」なのでv＝１となる。
【０００４】
ステップＳ５５では、[ノードの要求数Nreq＞head+1]の第１条件、および[u+2＞v]の第２条件がいずれも満足されているか否かが判定される。前記第１条件は、現在のノード数が要求数Nreqを満足しているための条件であり、第２条件は、親ノードのレイヤと子ノードのレイヤとが隣接するための条件である。ここでは、メモリテーブルMが[０，１，０，０，０…]であり、第１および第２条件がいずれも満足されるのでステップＳ５６へ進む。ステップＳ５６では、図１２(c)に示したように、メモリ値M(head+1)に変数vが登録されて「１」となる。これは、ヘッド位置headのノードと同一のレイヤにルートノードから子ノード（兄弟ノード）を分岐させたことを意味する。
【０００５】
ステップＳ５７では、図１２(d)に示したように、ヘッド位置headがインクリメントされる。ステップＳ５８では、現在までに生成されたノード数が要求数Nreqと比較される。ここでは、ノード数が未だ不足していると判定されるのでステップＳ５３へ戻る。なお、前記ステップＳ５５において、前記第１又は第２条件のいずれかが満足されていないと判定されると、ステップＳ６３へ進んでメモリ値M(head+1)がリセットされる。ステップＳ６４では、ヘッド位置headがデクリメントされる。
【０００６】
その後、上記の処理が繰り返されて子ノードの分岐およびヘッド位置headのインクリメントが進行し、前記ステップＳ５７でヘッド位置をインクリメントした時点で、図１２(e)に示したように、メモリテーブルMが[０，１，１，１，１，０…]、ヘッド位置headが「４」となると、ステップＳ５８では、現在のノード数が要求数Nreq（＝５）に達したと判定されるのでステップＳ５９へ進む。ステップＳ５９では、現時点でのメモリテーブルMの数値列[０，１，１，１，１]が順序木の一つとして採用される。
【０００７】
ステップＳ６０では、メモリ値M(head+1)がリセット（＝０）される。なお、この時点ではメモリ値M(head+1)が元々「０」なので実質的な変化は無い。ステップＳ６１では、図１２(f)に示したように、ヘッド位置headが後退（デクリメント）される。ステップＳ６２では、ヘッド位置headが「０」であるか否かが判定され、ここでは「０」以外と判定されるのでステップＳ５３へ戻る。
【０００８】
ステップＳ５３では、変数uに改めて「１」が登録される。ステップＳ５４では、変数vに「２」が登録される。ステップＳ５５では、前記第１および第２条件のいずれもが満足していると判定されるのでステップＳ５６へ進む。ステップＳ５６では、図１２(g)に示したように、メモリ値M(head+1)に変数vが登録されて「２」になる。これは、ヘッド位置headのノード（親ノード）から子ノードが新たに分岐されたことを意味する。
【０００９】
ステップＳ５７では、図１２(h)に示したように、ヘッド位置headがインクリメントされる。ステップＳ５８では、現在までに生成されたノード数が要求数Nreqと比較される。ここでは、要求数Nreqのノードが生成されているのでステップＳ５９へ進む。ステップＳ５９では、現時点でのメモリテーブルMの数値列[０，１，１，１，２]が順序木の一つとして採用される。ステップＳ６０では、メモリ値M(head+1)がリセット（＝０）される。なお、この時点でもメモリ値M(head+1)が元々「０」なので実質的な変化は無い。ステップＳ６１では、図１２(i)に示したように、ヘッド位置headが後退（デクリメント）される。ステップＳ６２では、ヘッド位置headが「０」であるか否かが判定され、ここでは「０」以外と判定されるのでステップＳ５３へ戻る。
【００１０】
以上の処理は、ステップＳ６２においてヘッド位置headが「０」と判定されるまで繰り返され、その結果、図１０に示したように、ノード数が「５」となる全て（１４本）の順序木が抽出されることになる。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特許第４１１１９４８号公報
【特許文献２】特開２０１０−５０５２８号公報
【非特許文献】
【００１２】
【非特許文献１】Janko Calic, David P. Gibson, and Neill W. Campbell, "Efficient Layout of Comic-like Video Summaries", IEEE Transactions on circuited systems for video technology, Vol.17, No.7, pp.931-936, 2007.
【非特許文献２】C.B.Atkins, "Adaptive Photo Collection Page Layout", IEEE International Conference on Image Processing (ICIP) 2004, pp.2897-pp.2900, 2004.
【非特許文献３】Shin-ichi Nakano, "Efficient Generation of Plane Trees", Information Processing Letters, Vol.84, no. 3, pp.167-172 (2002).
【非特許文献４】Shinichi Nakano and Takeaki Uno, "Constant Time Generation of Trees with Specified Diameter", LNCS3353, pp.33-45, 2004.
【非特許文献５】Takamasa Tanaka, Kenji Shoji, Fubito Toyama, and Juichi Miyamichi ,"Layout analysis of tree-structured scene frames in comic images" IJCAI-07, pp.2885-pp.2890, 2007.
【発明の概要】
【発明が解決しようとする課題】
【００１３】
上記のような一般的な順序木の列挙手法は、画像レイアウト用の順序木を対象としていないので画像レイアウトに用いることはできなかった。また、用いる場合にはレイアウト表現が可能かどうかを判定する基準が必要となると予想されるが、レイアウト表現が不可能な無駄な木が多数生成されるため、これが処理時間の短縮を妨げる要因の一つになると予想される。また、レイアウト表現が可能となっても、見た目の良くない木が多くなり、これも処理時間の短縮を妨げる要因の一つになると予想される。
【００１４】
まず、非特許文献５に開示されたコミックの分析では、図１３に示したように、ギロチンカットと呼ばれる横分割および縦分割を繰り返して木構造が推定される。この分析では、ルートノードからレイヤ毎に各ノードで水平分割または垂直分割が順番に繰り返され、子ノードに分岐しない終端のノードが葉すなわちコマとなる。そして、最後に深さ優先探索で左から右へ各葉に序数を割り振れば、それがコミックを読む順番となる。しかしながら、上記の従来技術では画像レイアウト用の木の生成は行われていない。
【００１５】
また、特許文献２では網羅的な木の生成は行われるものの、効率的な順序木列挙手法を基礎としておらず、非常に処理が遅くなっていた。これは、枝数の制約条件を満たす木を全て作成し、その中で葉数の条件が合うもののみを選択するのみで、葉数や枝数を組み合わせた無駄な木の生成処理が省かれていないからである。他には、深さ列を用いていないこと、チューリングマシンの様な木の効率的な生成法を用いていないことも原因だと考えられる。さらに、従来、効率的な順序木の生成法を用いて枝数の上限および葉の要求数を指定して木を生成する手法がないという技術課題があった。単純に枝の上限数と葉の要求数を指定して順序木を列挙する手法は、以下のように想定される。
【００１６】
図１４に示したように、各レイヤでの1つのノードから分岐可能なノード数が順に(３，３，３)に制限されている条件下で順序木を生成する場合、出力可能な葉数の最大値は３×３×３＝２７枚となるが、メモリテーブルMに（０，１，１）と書き込まれた時点で出力可能な最大葉数は１８枚に減少してしまう。したがって、葉の要求数Nreqが２０枚であると、これ以上の探索処理は無駄である。にもかかわらず、何も処理を行わないとメモリテーブルMに（０，１，１）と書き込まれた以降も探索が継続されてしまうという技術課題が予想される。
【００１７】
さらに、順序木を画像レイアウトに適用する場合、各ノードからは複数の子ノードが分岐しなければならないので、図１５に示したように、探索がレイヤ方向へ進行する過程では、一つの子ノード（第一子ノード）が分岐されると、これと同時に少なくとも１つの子ノード（兄弟ノード）が潜在的に分岐されることになる。しかしながら、従来、この条件および葉の要求数を指定して効率的に順序木を生成する手法がなかった。潜在的に分岐する兄弟ノードが考慮されていないとノード数が上限値を越えるような順序木まで探索範囲とされてしまうという技術課題が予想される。
【００１８】
また、出力対象領域や要求条件は変化することがあり、予め木を作成しておくのではなく、その場で条件にあった木を列挙してレイアウトに用いたい要望がある。その時でも高速にレイアウト用の木を生成できる必要がある。
【００１９】
本発明の目的は、新たに順序木を画像レイアウトに用いるにあたって、上記した従来技術の課題および予想される課題を解決し、画像レイアウトの観点から無駄な探索を検知し、これを中断して次の探索へ移行することで無駄な探索を回避できる画像レイアウト用の順序木の生成方法、生成プログラムおよび生成装置を提供することにある。
【課題を解決するための手段】
【００２０】
上記の目的を達成するために、本発明は、出力ページの各コマに、各コマの形状に合わせて原画像から切り出した画像をレイアウトする画像レイアウトのコマ割りを、ルートノードからのレイヤおよび各ノードから分岐するノードの数に従って水平分割または垂直分割を順次繰り返し、分岐しない終端のノードの葉をコマとして表現する順序木を生成する画像レイアウト用の順序木の生成方法、生成プログラムおよび生成装置であって、順序木に要求される葉数に、出力ページにレイアウトしようとする画像の数を設定し、ルートノードから複数の子ノードを分岐させ、各子ノードを親ノードとして複数の子ノードを更に分岐させることを繰り返し、子ノードが分岐しないノードを葉とする複数の経路を探索すると共に、以下のような構成を具備した点に特徴がある。
【００２１】
(1)探索中の経路ごとに、親ノードから子ノードを分岐させる際、生成済み葉数が前記要求される葉数に対して不足する葉数を算出し、前記不足する葉数を経路探索の継続により新たに生成できる葉数と比較し、前記新たに生成できる葉数が前記不足する葉数を満たせれば当該経路探索を継続し、満たせなければ当該経路探索を中止し、前記生成済み葉数が前記要求される葉数を満足し、葉以外の全てのノードが複数に分岐する経路を順序木の構造として採用するようにした。
【００２３】
(2)探索中の経路ごとに親ノードから子ノードを分岐させる際、当該子ノードが最初の分岐に係る第一子ノードおよび二回目以降の分岐に係る兄弟ノードのいずれであるかを識別し、前記子ノードが第一子ノードであれば、その兄弟ノードをスタックし、前記子ノードが兄弟ノードであれば、対応するスタックを消費し、葉数が前記要求される葉数を満足し、前記スタックが消費されている経路を順序木の構造として採用するようにした。
【発明の効果】
【００２４】
本発明によれば、以下のような効果が達成される。
【００２５】
(1)画像レイアウト用の木の作成にあたって、レイアウトとして表現できない木や見た目の良くない木の生成を省くことができるので、順序木を用いて効率的かつ網羅的に木を生成でき、また、探索中の経路ごとに親ノードから子ノードを分岐させる際、生成済みの葉数が要求される葉数に対して不足する葉数を算出し、この不足する葉数を当該経路探索の継続により新たに生成できる葉数と比較し、新たに生成できる葉数が不足する葉数を満たせれば当該経路探索を継続し、満たせなければ当該経路探索を中止するようにしたので、要求される葉数を満足できないことが明らかな経路の探索を途中で停止できるようになる。
【００２７】
(2)探索中の経路ごとに親ノードから子ノードを分岐させる際、子ノードが最初の分岐に係る第一子ノードおよび二回目以降の分岐に係る兄弟ノードのいずれであるかを識別し、子ノードが第一子ノードであれば、その兄弟ノードをスタックする一方、子ノードが兄弟ノードであれば、対応するスタックを消費し、最終的に、葉数が要求される葉数を満足し、かつスタックが消費されている経路を順序木の構造として採用するようにしたので、葉数が要求を満足していても画像レイアウト用に不適な順序木を排除できるようになる。
【図面の簡単な説明】
【００２８】
【図１】第１の枝刈り手法を説明するための図である。
【図２】第２の枝刈り手法を説明するための図である。
【図３】本発明の一実施形態の動作を示したフローチャートである。
【図４】メモリテーブルMの初期状態を示した図である。
【図５】変数vの計算手順を示したフローチャートである。
【図６】第一子ノードおよび兄弟ノードの一例を示した図である。
【図７】画像レイアウト用の順序木を作成する装置の機能ブロック図である。
【図８】画像レイアウト用の順序木を作成する装置をコンピュータシステムで構成した場合のブロック図である。
【図９】順序木を生成する従来技術の一例を示したフローチャートである。
【図１０】頂点数（ノード数）が「５」の順序木の生成方法を示した図である。
【図１１】順序木の構造を示した図である。
【図１２】メモリテーブルMの数値列が変化する様子を示した図である。
【図１３】順序木を利用した画像レイアウト用のコマ割り方法を示した図である。
【図１４】探索を進めてもノードを十分に分岐させられない様子を示した図である。
【図１５】兄弟ノードが潜在的に発生する様子を示した図である。
【発明を実施するための形態】
【００２９】
以下、図面を参照して本発明の実施の形態について詳細に説明する。本発明は、順序木に要求される葉数(以下では単に「要求数」と記す)Nreqを予め設定し、ルートノードから複数の子ノードを分岐させ、各子ノードを親ノードとして複数の子ノードを更に分岐させることを繰り返し、子ノードが分岐しないノードを葉（ノード）とする複数の経路を探索し、葉数が要求数Nreqを満足する経路を順序木の構造として採用する網羅的な探索方法において、各ノードから分岐可能な枝数（子ノード数）および分岐の深さ（レイヤ）に上限が設定される条件下で、主に以下の２つの枝刈り手法を採用することで無駄な探索処理を回避するようにした点に特徴がある。
【００３０】
(1)第１の枝刈り手法では、探索中の経路ごとに、親ノードから子ノードを分岐させる際、葉の要求数Nreqに対する不足数を算出し、これを経路探索の継続により新たに生成できる葉数と比較する。そして、探索を継続することにより新たに生成できる葉数が、不足する葉数を満たすことができれば当該経路探索を継続し、満たすことができなければ当該経路探索を中止するようにした。
【００３１】
すなわち、図１(a)に示したように、メモリテーブルMに（０，１，１）と書き込まれて探索範囲が限定され、その結果、探索を継続することにより新たに生成できる葉数が不足数に満たないと判定されると、それから先の探索を中止し、同図(b)に示したように、メモリテーブルMを（０，１，２）に書き換えて探索範囲を拡張する。
【００３２】
(2)第２の枝刈り手法では、探索中の経路ごとに、親ノードから子ノードを分岐させる際、当該子ノードが最初の分岐に係る第一子ノードおよび二回目以降の分岐に係る兄弟ノードのいずれであるかを判定し、第一子ノードであれば、その潜在的な兄弟ノードをスタックする一方、分岐された子ノードが兄弟ノードであれば、対応するスタックを消費する。そして、生成済みの葉数が前記要求数Nreqを満足し、かつスタックが全て消費されている経路を順序木の構造として採用するようにした。
【００３３】
すなわち、図２に示したように、ある親ノードから子ノードが分岐する形態は、同図(a)に示したように第一子ノードである場合と、同図(b)に示したように兄弟ノードである場合とに分類できる。そして、画像レイアウトのコマ割り表現する順序木では、各ノード（親ノード）からは複数のノード（子ノード）が分岐することが要求されるので、分岐された子ノードが第一子ノードであれば、その兄弟ノードも必ず分岐されなければならず、第一子ノードしか分岐しない親ノードを含む順序木は採用できない。
【００３４】
そこで、本発明では、図２(c)に示したように、親ノードから第一子ノードが分岐されるごとに、この分岐により潜在的（将来的）に分岐される兄弟ノードをスタックして分岐予約すると共に、その後、図２(d)に示したように、兄弟ノードへの分岐が実行されるごとに対応するスタックを消費し、スタックが全て消費されていれば全ての親ノードが複数の子ノードに分岐されている判断できるようにした。
【００３５】
また、本発明ではコミック風のレイアウトを実現するために、以下の４つの制約条件(a)、(b) ，(c)，(d)を全て満たす順序木を作成する。なお、５つ目の制約条件(e)はノードへのラベルの貼り方なので、先にルートノードの分割方向を決めておく、または後から決めても良い。
【００３６】
(a)各ノードからの枝の分岐数を深さ(レイヤ)ごとに制限（レイヤごとに枝分岐の最大数を設定）
【００３７】
(b)分岐の深さを制限（最大レイヤを設定）
【００３８】
(c)枝の数は2本以上
【００３９】
(d)葉の総数を指定
【００４０】
(e)ルートノードの分割線の方向を指定（必須ではない）
【００４１】
たとえば，最大深さを「3」，分岐数の上限をレイヤ0で「5」，レイヤ1で「4」，レイヤ2で「3」とし、ルートノードを水平分割から始める場合はH(5,4,3)と表記する。葉の数に合わせて、適用する木の制約構造を予め決めておいても良い。この制約を満たす順序木を作成することで、見た目に悪いと決めた範囲（深さや枝数上限)を除外できる。例えば、この場合、４以上の深さになるレイアウトはコマが細か過ぎるだろうと判断して除外して指定している[制約(b)]。第２レイヤのノードから分割できる最大数は３となっているが、４以上の分割になるレイアウトはコマが細かすぎるだろうと判断して除外して指定している[制約(a)]。また、制約(c)のようにそもそもレイアウト表現できない順序木の生成を省略できる。また、画像枚数を決めてから処理するため、制約(d)を指定できることは重要である。  次いで、図３のフローチャートを参照して本発明の一実施形態の動作を詳細に説明する。ステップＳ１では、順序木の構造を表現する数値列を記憶するメモリテーブルMに初期値が登録される。本実施形態では、図４に示したように、メモリテーブルMのアドレスi=0に「０」、i=1に「１」，i=2に「０」，i=3に「０」，i=4に「０」…が登録される。本実施形態では、後に詳述するように、メモリテーブルMの各アドレスに書き込まれる変数vが、新たに分岐されたノードの分岐先レイヤを表している。したがって、本実施形態では図６(a)に示した木構造からノード探索が進行する。
【００４２】
ステップＳ２では、各種のパラメータが初期化される。本実施形態では、注目するメモリアドレスiを指定するためのヘッド位置headに「１」がセットされ、生成済みの葉数N1に「１」がセットされ、前記第１の枝刈り手法を実現するためにノードの分岐先レイヤを指令する変数V'に「０」がセットされ、前記親ノードから第一子ノードの分岐により潜在的に生じる兄弟ノードの分岐／未分岐を管理するスタックは、既に出力されている第１子ノード「１」に関して潜在的に分岐されている（実際には、未だ分岐されていない）兄弟ノードを示す「１」がスタックされた状態とされる。
【００４３】
ステップＳ３では、これまでに生成済みの葉数N1が要求数Nreqと比較され、初めは生成済みの葉数N1が要求数Nreqに満たないと判定されるのでステップＳ４へ進む。ステップＳ４では、注目ノードのレイヤを代表する変数uにメモリ値M(head)が登録される。ステップＳ５では、新たに分岐させようとするノードの分岐先レイヤを代表する変数vが計算される。変数vの計算方法については、後に図５のフローチャートを参照して詳述するものとし、初めは従来技術と同様に、ヘッド位置headにプラス「１」した値[head＋１]のメモリ値M(head+1)にプラス「１」した値が変数vに設定されるものとして説明を続ける。ここでは、メモリ値M(head+1)が「０」なのでv＝１となる。
【００４４】
ステップＳ６では、新たに分岐させようとしている子ノード(v)が、図６(b)に示した第一子ノード、図６(c)に示した兄弟ノード、のいずれであるのかが、前記変数u，vの大小関係を比較することで識別される。ここでは、u＜vであれば第一子ノードと識別されてステップＳ１４へ進み、u≧vであれば兄弟ノードと識別されてステップＳ７へ進む。最初は変数u，vがいずれも「１」でu≧vが成立するので、兄弟ノードを分岐させるべくステップＳ７へ進む。
【００４５】
ステップＳ７では、兄弟ノードを新たに分岐させると、その親ノードからの分岐数が上限値を越えるか否かが判定される。越えると判定されればステップＳ１８へ進み、越えないと判定されればステップＳ８へ進む。ステップＳ８では、この兄弟ノード(v)から延びる経路上で生成可能な葉数の最大数N2が算出される。この生成可能な最大葉数N2は、枝数の制限および深さの制限から計算できる。
【００４６】
ステップＳ９では、要求数Nreqから生成済み葉数N1を減じることで不足している葉数N3が算出される。ステップＳ１０では、前記生成可能な最大葉数N2と不足葉数N3とを比較することで、兄弟ノード(v)から深さ方向への探索を更に進めることにより前記要求数Nreqを満足できる順序木を生成可能であるか否かが判定される。
【００４７】
ここで、N3＞N2であって生成不可能であれば、探索方向を深さ方向へ切り替えるべくステップＳ１８へ進み、変数vをインクリメントした値が変数v'に登録される。これに対して、生成可能と判断されれば、前記兄弟ノード(v)を実際に分岐させるべくステップＳ１１へ進む。ステップＳ１１では、メモリ値M(head+1)に変数vが登録されて分岐が実行され、ヘッド位置headがインクリメントされ、さらに生成済みの葉数N1がインクリメントされる。ステップＳ１２では、前記図２(d)を参照して説明したように、前記分岐させた兄弟ノード(v)に対応した要素とスタックの末尾の値とが等しければ、当該要素が前記スタックから消費される。ステップＳ１３では、ヘッド位置headが「０」であるか否かが判定される。ここでは、「０」以外と判定されるのでステップＳ３へ戻って上記の処理が繰り返される。
【００４８】
一方、前記ステップＳ６において、新たに分岐させようとしている子ノード(v)が第一子ノードと判定されるとステップＳ１４へ進む。ステップＳ１４では、変数v（第一子ノードの分岐先レイヤ）がレイヤの深さに関する制限値v_maxと比較され、さらに前記スタックに登録されている潜在的兄弟ノード数が、葉数の要求数Nreqから生成済みの葉数N(v)を減じた不足葉数N3と比較される。
【００４９】
v≦v_maxであって第一子ノードの分岐先レイヤが制限範囲内であり、かつ潜在的兄弟ノード数が要求数Nreqから生成済み葉数N1を減じた不足数N3よりも小さく、全ての潜在的兄弟ノードが実際に分岐されても依然として葉数が要求数Nreqを満足できないのであれば、更に経路探索を進めるべくステップＳ１５へ進む。
【００５０】
ステップＳ１５では、新たに第一子ノードを分岐させるべくメモリ値M(head+1)に変数vが登録され、さらにヘッド位置headがインクリメントされる。ここでは、前記ステップＳ１０とは異なり、葉数N1がインクリメントされない。ステップＳ１６では、前記ステップＳ１５で第一子ノードを新たに分岐させたことにより潜在的に分岐される兄弟ノードの分岐先レイヤ（変数v）が前記スタックの末尾に追加される。
【００５１】
これに対して、前記ステップＳ１４において、v＞v_maxと判定されるか、あるいはスタックされている潜在的兄弟ノード数が不足葉数N3よりも少なくないと判定されると、この以上の深さ方向への探索は不要と判定されてステップＳ１７へ進む。ステップＳ１７では、メモリ値M(head+1)が変数u以下であることを条件に葉数N1がデクリメントされる。さらに、メモリ値M(head+1)がリセット（＝０）され、ヘッド位置headが後退（デクリメント）される。
【００５２】
その後、前記ステップＳ３において、生成済の葉数N1が要求数Nreqに達したと判定されるとステップＳ２０へ進む。ステップＳ２０では、スタックが空であるか否かが判定される。空であればステップＳ２１へ進み、メモリテーブルMの数値列を順序木として採用してステップＳ２２へ進む。
【００５３】
これに対して、スタックが空でなければ、潜在的兄弟ノード数の少なくとも一つが未分岐である、すなわち複数に分岐していない親ノードを含む順序木であると判定されてステップＳ２２へジャンプする。ステップＳ２２では、メモリ値M(head+1)がu以下であることを条件に生成済み葉数N1がデクリメントされる。また、メモリ値M(head+1)がリセット（＝０）され、ヘッド位置headが後退（デクリメント）される。
【００５４】
図５は、前記ステップＳ５で実行される変数v（子ノードの分岐先レイヤ）の計算方法を示したフローチャートである。
【００５５】
ステップＳ３１では、ヘッド位置headにプラス「１」した値[head＋１]のメモリ値M(head+1)にプラス「１」した値が、新たに分岐させようとする子ノードの分岐先レイヤを代表する変数vに登録される。ステップＳ３２では、前記第１の枝刈り手法を適用して子ノードを分岐させる際の分岐先レイヤv'が既登録であるか否かが判定される。既登録であればステップＳ３３へ進み、変数vにv'が登録される。ステップＳ３４では、変数v'がリセットされる。
【００５６】
一方、前記ステップＳ３２において、変数v'が未登録と判定されるとステップＳ３５へ進み、メモリ値M(head)が変数vと比較される。M(head)＞vであれば、子ノードとして第一子ノードを分岐させた直後と判定され、潜在的な兄弟ノードの分岐を優先させるべくステップＳ３６へ進む。ステップＳ３６では、スタック末尾に分岐可能な兄弟ノードがスタックされているか否かが判定される。スタックされていればステップＳ３７へ進み、スタック末尾の値が変数vに代入される。
【００５７】
本実施形態によれば、探索中の経路ごとに親ノードから子ノードを分岐させる際に、それまでに生成されている葉数N1の要求数Nreqに対する不足数N3を算出し、これを経路探索の継続により新たに生成できる葉数と比較し、新たに生成できる葉数が、不足している葉数を満たせなければ当該経路探索を中止するようにしたので、葉の要求数を満足できないことが明らかな経路の探索を途中で停止できるようになる。
【００５８】
また、本実施形態によれば、探索中の経路ごとに親ノードから子ノードを分岐させる際、子ノードが第一子ノードおよび兄弟ノードのいずれであるかを識別し、第一子ノードであれば、その兄弟ノードをスタックする一方、兄弟ノードであれば対応するスタックを消費し、最終的に、葉数が要求数を満足し、かつスタックが消費されている経路を順序木の構造として採用するようにしたので、葉数が要求を満足していても画像レイアウト用に不適な順序木を排除できるようになる。
【００５９】
図７は、前記画像レイアウトのコマ割りに利用できる順序木を生成する順序木生成装置の機能ブロック図である。
【００６０】
要求数設定部２０１には、葉数の要求数Nreqが設定される。探索部２０２は、ルートノードから複数の子ノードを分岐させ、各子ノードを親ノードとして複数の子ノードを更に分岐させることを繰り返し、子ノードが分岐しないノードを葉とする複数の経路を探索する。比較部２０３は、探索中の経路ごとに、親ノードから子ノードを分岐させる際、葉の要求数Nreqに対する不足数N2を算出し、これを経路探索の継続により新たに生成できる葉数N3と比較する。探索制限部２０４は、新たに生成できる葉数が前記不足する葉数を満たせれば当該経路探索を継続し、満たせなければ当該経路探索を中止させる。
【００６１】
子ノード識別部２０５は、探索中の経路ごとに、親ノードから子ノードを分岐させる際、当該子ノードが最初の分岐に係る第一子ノードおよび二回目以降の分岐に係る兄弟ノードのいずれであるかを識別する。スタック管理部２０６は、分岐された子ノードが第一子ノードであれば、その潜在的な兄弟ノードをスタックする一方、分岐された子ノードが兄弟ノードであれば、対応するスタックを消費する。順序木出力部２０７は、生成済みの葉数N1が要求数Nreqを満足し、かつスタックが全て消費されている経路を順序木の構造として採用する。
【００６２】
図８は、前記画像レイアウトのコマ割りに利用できる順序木の生成装置をコンピュータシステムで構成した場合のブロック図であり、図３のフローチャートで示した順序木の生成方法をコンピュータに実行させるためのプログラムがCD-ROM等の記録メディア１０２に記録され、この記録メディア１０２を読み取るドライブ装置１０１と、オペレーティングシステムと共に、前記読み取られたプログラムおよび入力された条件が一時記憶されるHDD１０３と、葉の要求数Nreqやレイヤごとの最大ノード数などが入力されるキーボードやマウス等の入力装置１０４と、各種のデータやプログラムが不揮発に記憶されたROM１０５と、前記プログラムを実行するCPU１０６と、前記CPU１０６にワークエリアを提供するRAM１０７と、生成された順序木を出力する出力装置１０８とを主要な構成としている。
【符号の説明】
【００６３】
２０１…要求数設定部，２０２…探索部，２０３…比較部，２０４…探索制限部，２０５…子ノード識別部，２０６…スタック管理部，２０７…順序木出力部
【図１】
0005601666.tif 000002
【図２】
0005601666.tif 000003
【図３】
0005601666.tif 000004
【図４】
0005601666.tif 000005
【図５】
0005601666.tif 000006
【図６】
0005601666.tif 000007
【図７】
0005601666.tif 000008
【図８】
0005601666.tif 000009
【図９】
0005601666.tif 000010
【図１０】
0005601666.tif 000011
【図１１】
0005601666.tif 000012
【図１２】
0005601666.tif 000013
【図１３】
0005601666.tif 000014
【図１４】
0005601666.tif 000015
【図１５】
0005601666.tif 000016