(57)【要約】  画像のコラージュを作成するコンピュータ実施方法(700)において、表示領域に第１の画像をシードすることによって(710)コラージュを開始する。複数の試行レイアウト配置に、コラージュに追加される追加画像を提供する(720)。試行レイアウト配置に対して、オクルージョンコストを生成する(730)。オクルージョンコストは、試行配置によってオクルージョンされる画像顕著性及びオクルージョンされる表示領域顕著性を表す。コラージュを、オクルージョンコストが生成された試行レイアウト配置のうちの１つを反映するように更新することによって、コラージュに画像を追加する(740)。【選択図】図７
2009535696.tif 000002
【特許請求の範囲】
【請求項１】
画像のコラージュを加法的に生成するコンピュータ実施方法（700）であって、
第１の画像を表示領域内にシード（710）して、前記コラージュを開始し、
複数の試行レイアウト配置に、前記コラージュに追加される追加画像を提供（720）し、
前記複数の試行レイアウト配置のうちの１つの試行レイアウト配置に対してオクルージョンコストを生成（730）し、そのオクルージョンコストが、前記１つの試行配置によってオクルージョンされる画像顕著性及びオクルージョンされる表示領域顕著性を表し、及び
前記コラージュに画像を追加（740）し、前記コラージュは、前記オクルージョンコストが生成された前記複数の試行レイアウト配置のうちの１つを反映するように更新されていることを含む、コンピュータ実施方法（700）。
【請求項２】
前記複数の画像を前記コラージュ内に逐次に組み込む（750）ことを更に含み、前記組み込むことは、前記複数の画像が前記コラージュ内に組み込まれるまで、前記提供すること、前記生成すること、及び前記追加することを繰り返すことを含む、請求項１に記載のコンピュータ実施方法（700）。
【請求項３】
前記第１の画像を表示領域内にシード（710）して、前記コラージュを開始することが、
所定の面積を有する表示領域内に第１の画像をシードして、前記コラージュを開始することを含む、請求項１に記載のコンピュータ実施方法（700）。
【請求項４】
前記所定の面積を有する表示領域内に第１の画像をシード（710）して、前記コラージュを開始することが、
コラージュされている画像の結合される画像面積に比例して自動的にスケーリングされる所定の面積を有する表示領域内に第１の画像をシードして、前記コラージュを開始することを更に含む、請求項３に記載のコンピュータ実施方法（700）。
【請求項５】
前記第１の画像を表示領域内にシード（710）して、前記コラージュを開始することが、
第１の画像を前記表示領域の中心位置にシードして、前記コラージュを開始することを含む、請求項１に記載のコンピュータ実施方法（700）。
【請求項６】
前記複数の試行レイアウト配置に、前記コラージュに追加される追加画像を提供（720）することが、
前記表示領域内の前記追加画像の複数の２次元位置から成る複数の試行レイアウトを生成し、前記追加画像が前記コラージュの上方にｚ方向に順序付けされ、及び
前記表示領域内の前記追加画像の複数の２次元位置から成る複数の試行レイアウトを生成し、前記追加画像が前記コラージュの下方にｚ方向に順序付けされることを含む、請求項１に記載のコンピュータ実施方法（700）。
【請求項７】
前記試行レイアウト配置に対してオクルージョンコストを生成（730）することが、
一様な顕著性を前記表示領域に与え、及び
前記複数の試行レイアウト配置の各々に対して前記オクルージョンコストを生成することを更に含む、請求項１に記載のコンピュータ実施方法（700）。
【請求項８】
前記コラージュに画像を追加（740）し、前記コラージュは、前記オクルージョンコストが生成された前記複数の試行レイアウト配置のうちの１つを反映するように更新されていることは、
前記コラージュに画像を追加し、前記コラージュは、前記オクルージョンコストが生成された前記試行レイアウト配置のうちの最も低いオクルージョンコストレイアウト配置を反映するように更新されることを含む、請求項１に記載のコンピュータ実施方法（700）。
【請求項９】
画像のコラージュを反復的に生成するコンピュータ実施方法（1200）であって、
表示領域内でコラージュされるべき複数の画像に対する画像顕著性データを受け取り（1210）、
前記表示領域内で前記複数の画像の初期コラージュレイアウトを生成（1220）し、及び
前記初期コラージュレイアウトを最適化すること（1230）を含み、前記最適化することが、最小化されたレイアウトオクルージョンコストに対する選択を通じて前記初期コラージュレイアウトを反復的に調整することを含む、コンピュータ実施方法（1200）。
【請求項１０】
前記最小化されたレイアウトオクルージョンコストに対する選択を通じて前記初期コラージュレイアウトを反復的に調整することを含む、前記最適化すること（1230）が、
複数のｚ方向に順序付けされたレイアウトからｚ方向の順序付けレイアウトの最低のオクルージョンコストを選択し、及び
複数の２次元的に調整されたレイアウトから２次元的に調整された最低のレイアウトオクルージョンコストを選択することを更に含む、請求項９に記載のコンピュータ実施方法（1200）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、画像のコラージュを生成することに関する。より詳細には、本発明の実施形態は、画像のコラージュの生成においてオクルージョンコスト情報を使用することに関する。
【０００２】
背景
何十年もの間、アナログ画像の内容を提示する最も一般的なフォーマットのうちの１つはコラージュであった。コラージュにおいて写真を技巧的に並置することによって、眼により非常に容易に検出され得る繰返し構造のない視覚的に魅力のあるレイアウトが生成される。コラージュは、画像を視覚的に表示する他のより構造化された別の方法から脱却した、何らかの秩序性の欠如を表す。しかしながら、優れたコラージュは、部分的に内容自体の分析に依存する。例えば、画像をオーバラップさせることは重要であるが、それが、積層されることによって画像の顔又は他の何らかの重要なオブジェクトが隠れるという結果にならないことが重要である。
【０００３】
アナログ画像の優れたコラージュを手作業で作成することは、非常に大きな労働力を要するプロセスであり、画像を何度も再配置して再順序付けする必要がある。同様に、デジタル画像の優れたコラージュを手作業で作成することもまた、非常に大きな労働力を要するプロセスであり、例えば画像編集コンピュータプログラムを用いてデジタル画像の配置及び位置を操作するために非常に多くの時間を費やす必要がある。
【０００４】
現在、デジタル画像のコラージュを作成する自動化方法があるが、それらには多くの欠点がある。これらの既存の自動化方法は、２つのカテゴリに分類される傾向があり、即ち、安全（safe）コラージュ作成方法、及び積極的（aggressive）コラージュ作成方法である。
【０００５】
安全コラージュ作成方法では、コラージュは、画像間のオーバラップ量が非常にわずかしかない状態で作成される。安全方法で作成されるコラージュは、技巧的に作成されたコラージュに比べて、画像のタイリングに類似するように見えることが多い。この最小限のオーバラップは、顔及び他の重要な画像細部のオクルージョン（occlusion）を防止するのに役立つが、一般に、視覚的に満足のいかない非常につまらないコラージュという結果になる。
【０００６】
積極的コラージュ作成方法では、コラージュは、１つの画像が別の画像の上に積極的にオーバラップして作成される。積極的方法を使用して作成されるコラージュは、画像を表示領域に効率よく詰め込むが、それら画像の最も関心のある内容が不明瞭になることが多い。優れたコラージュをこのように作成することは可能であるが、画像の顔又は関心のある領域が任意にオクルージョンされ、そのため、視覚的に満足のいかないコラージュという結果になりやすい。
【０００７】
デジタルカメラの使用、及びパーソナルコンピュータ等の強力な表示装置の使用が急速に増加することによって、魅力的な方法でマルチメディアコンテンツを表示する必要性がますます広がってきている。コラージュは、画像を表示するための満足のいく一般的な方法である。しかしながら、上述したように、デジタル画像の優れたコラージュを作成する現在の方法は、大きな労働力を要するか、又は満足のいかないコラージュが自動的に作成されるという結果になる欠点がある。
【０００８】
本明細書に組み込まれ、本明細書の一部を形成する添付図面は、オクルージョンコストを生成する技術の実施形態を示し、説明と共に、後述する原理を説明するのに役立つ。
【０００９】
本明細書で参照される図面は、特に言及されない限り、一律の縮尺に従って描かれているものと理解されるべきではない。
【００１０】
発明の詳細な説明
ここで、本発明の実施形態について詳細に言及し、それらの例を添付図面に示す。一方、本発明では、それらの例が本発明をこれらの実施形態に限定するように意図されていないということは理解されよう。それとは反対に、提示される技術は、添付の特許請求の範囲によって定義されるような様々な実施形態の思想及び範囲内に含まれ得る、代替形態、変更形態及び等価物を包含するように意図されている。更に、以下の詳細な説明では、本発明が完全に理解されるように、多数の特定の詳細を説明する。しかしながら、本発明は、これらの特定の詳細なしに実施され得る。また、本発明の態様を不必要に不明瞭にしないように、良く知られた方法、手続き、構成要素及び回路については詳細に説明していない。
【００１１】
特に明記しない限り、以下の論考から明らかであるように、本詳細な説明を通して、「シードする（seeding：供給する）」、「提供する」、「生成する」、「追加する」、「組み込む」、「繰り返す」、「スケーリングする」、「〜に与える、〜に帰する、〜に原因すると考える、〜に属すると考える（attribute）」、「最適化する」、「配置する」、「選択する」、「調整する」、「表示する」、「計算する」、「更新する」、「表示する」、「最小化する」、「取得する」、「回転させる」及び「受け取る」等の用語を利用する論考は、コンピュータシステム（図１のコンピュータ１００等）又は同様の電子コンピューティングデバイスの動作及びプロセスに関係する。コンピュータシステム又は同様の電子コンピューティングデバイスは、コンピュータシステムのレジスタ及びメモリ内の物理（電子）量として表されるデータを操作して、コンピュータシステムのメモリ又はレジスタ、或いは他のこうした情報記憶装置、伝送装置又は表示装置内において物理量として同様に表される他のデータに変換する。また、本発明は、例えば光コンピュータ、仮想コンピュータ及び機械コンピュータ等の他のコンピュータシステムの使用にも適している。更に、本発明の実施形態では、ステップのうちの１つ又は複数を手作業で実行してもよいということは理解されるべきである。
【００１２】
コンピュータシステム環境例
ここで図１を参照すると、本発明の一部は、例えばコンピュータシステムのコンピュータ使用可能媒体に存在するコンピュータ可読命令及びコンピュータ実行可能命令から成る。即ち、図１は、本発明の後述する実施形態を実施するために使用され得るタイプのコンピュータの一例を示す。図１は、本発明の実施形態によって使用される１つの例示的なコンピュータシステム１００を示す。理解されるように、図１のシステム１００は単に例示的なものであり、本発明は、汎用ネットワークコンピュータシステム、埋込式コンピュータシステム、ルータ、スイッチ、サーバ装置、クライアント装置、様々な中間装置／ノード、スタンドアロンのコンピュータシステム、デジタルカメラ、携帯端末等を含む、多数の異なるコンピュータシステムで又はその内部で動作することができる。図１に示すように、図１のコンピュータシステム１００は、例えばフロッピー（登録商標）ディスク（Ｒ）、コンパクトディスク等の周辺コンピュータ可読媒体１０２が結合されることによく適合している。
【００１３】
図１のシステム１００は、情報を伝えるためのアドレス／データバス１０４と、バス１０４に結合され、情報及び命令を処理するためのプロセッサ１０６Ａとを含む。また、図１に示すように、システム１００は、複数のプロセッサ１０６Ａ、１０６Ｂ及び１０６Ｃが存在するマルチプロセッサ環境にもよく適している。逆に、システム１００はまた、例えばプロセッサ１０６Ａ等の単一のプロセッサを有することにもよく適している。プロセッサ１０６Ａ、１０６Ｂ及び１０６Ｃは、任意の様々なタイプのマイクロプロセッサとすることができる。また、システム１００は、バス１０４に結合され、プロセッサ１０６Ａ、１０６Ｂ及び１０６Ｃのために情報及び命令を格納する、コンピュータ使用可能揮発性メモリ１０８、例えばランダムアクセスメモリ（ＲＡＭ）等のデータ記憶機構も含む。また、システム１００は、バス１０４に結合され、プロセッサ１０６Ａ、１０６Ｂ及び１０６Ｃのために静的情報及び命令を格納する、コンピュータ使用可能不揮発性メモリ１１０、例えば読み取り専用メモリ（ＲＯＭ）も含む。また、システム１００には、バス１０４に結合されて、情報及び命令を格納するためのデータ記憶ユニット１１２（例えば、磁気又は光ディスク、及びディスクドライブ）も存在する。また、システム１００は、バス１０４に結合され、情報及びコマンド選択をプロセッサ１０６Ａ、又はプロセッサ１０６Ａ、１０６Ｂ及び１０６Ｃに伝えるための、英数字キー及びファンクションキーを含むオプションの英数字入力装置１１４も含む。また、システム１００は、バス１０４に結合され、ユーザ入力情報及びコマンド選択をプロセッサ１０６Ａ、又はプロセッサ１０６Ａ、１０６Ｂ及び１０６Ｃに伝えるためのオプションのカーソル制御装置１１６も含む。また、本実施形態のシステム１００は、バス１０４に結合され、情報を表示するためのオプションの表示装置１１８も含む。
【００１４】
更に図１を参照すると、図１のオプションの表示装置１１８は、液晶装置、ブラウン管、プラズマディスプレイ装置、又はユーザが認識可能なグラフィック画像及び英数字文字を生成するために適した他の表示装置とすることができる。オプションのカーソル制御装置１１６によって、コンピュータユーザが、表示装置１１８の表示画面における可視記号（カーソル）の移動の信号を動的に送ることが可能になる。当該技術分野では、変位の所与の方向又は仕方に関する移動の信号を送ることができる、英数字入力装置１１４上のトラックボール、マウス、タッチパッド、ジョイスティック又は特別なキーを含む、カーソル制御装置１１６の多くの具現化形態が知られている。代案として、特別なキー及びキーシーケンスコマンドを使用して、英数字入力装置１１４からの入力を介して、カーソルを方向付け及び／又は付勢することができることは理解されよう。また、システム１００は、例えば音声コマンド等の他の手段によってカーソルが方向付けられることにもよく適している。また、システム１００は、システム１００を外部エンティティと結合するためのＩ／Ｏデバイス１２０も含む。例えば、一実施形態では、Ｉ／Ｏデバイス１２０は、システム１００と、限定されないがインターネット等の外部ネットワークとの間の有線通信又は無線通信を可能にするためのモデムである。
【００１５】
更に図１を参照すると、システム１００に対して他の様々な構成要素が示されている。特に、存在する場合、オペレーティングシステム１２２、アプリケーション１２４、モジュール１２６、及びデータ１２８が、コンピュータ使用可能揮発性メモリ１０８、例えばランダムアクセスメモリ（ＲＡＭ）及びデータ記憶ユニット１１２のうちの１つ又はいくつかの組合せに一般に存在するものとして示されている。一実施形態では、本発明は、例えば、ＲＡＭ１０８内の記憶場所、及びデータ記憶ユニット１１２内の記憶領域に、アプリケーション１２４又はモジュール１２６として格納される。
【００１６】
オクルージョンコスト計算（occlusion costing）
オクルージョンコスト計算は、表示領域に表示されるべき１つ又は複数の画像の相対位置（単数または複数）、及びそれらの間の任意の可能性のあるオーバラップに関連付けられる、量的オクルージョンコストを求める手段である。画像に対するオクルージョンコストを導出するために使用される方法の一例を、表１に示すコストの数式によって示す。
【００１７】
表１の式は、例えば顕著性マップ（saliency map）等、顕著性情報の使用に依存する。更に後述されるように、顕著性マップ、及び画像顕著性を求めるための他の多くの技術が知られている。顕著性マップは、例えば、一般に特定の画像に対し顕著な領域（顕著領域）の対応するマッピングを提供する。一般に、画像の画素程度に小さい場合もある、画像領域に対する顕著性は、顕著性マップ／データにおいて対応するスコアを有する。例えば、画像の顕著性マップは、画像のグレイスケールマップから構成され得る。こうした顕著性マップにおいて、顕著性の値を、スケールに、例えば０〜２５５に割り当てることができ、最高の顕著性は白色画素及び２５５の値で表され、最低の顕著性は黒色画素及び０の値で表される。表１〜表５及び表７に示される式は、これらの対応する顕著性値を合計して、表示領域内の画像、レイアウト又はレイアウトの一部に対する特定のオクルージョンコストを求めるための技術である。
【００１８】
【表１】
2009535696.tif 000003
【００１９】
表１の式は、画像のオクルージョンされる領域に対する顕著性のレベルを計算し、それを、画像全体における顕著性の総和で除算する。その結果は、画像の或る領域がレイアウト方向において隠される、即ちオクルージョンされることに対するオクルージョンコストである。例えば、一実施形態では、表１の式を使用して、表示領域に単独で表示されるべき単一の画像のレイアウト方向に対するオクルージョンコストを求める。また、それを使用して、合計することによって、表示領域に同時に表示されている複数の画像のレイアウトに対するオクルージョンコストを計算することもできる。コスト値は、０〜１の範囲で生成され、百分率としてみなされ得る。１に近いコストは概して全オクルージョンに等しく、０に近いコストは、非常にわずかなオクルージョンを示す。
【００２０】
オクルージョンコストが、表示領域内に表示されている画像の単一のレイアウトに対して計算される場合、計算は、その画像に対する顕著性データを利用して、その画像のレイアウトのオクルージョンコストを求める。画像に２つ以上のレイアウトがある場合、その画像の各レイアウトに対してオクルージョンコストを求めることができる。表示領域において同時に表示するために２つ以上の画像が処理されている場合、複数の画像の各々に対してオクルージョンコストを計算して、表示領域内に複数の画像を同時に提示するためのレイアウトのオクルージョンコストを求めることができる。表示領域内に複数の画像を同時に提示するために２つ以上のレイアウトがある場合、複数の画像の各レイアウトに対してオクルージョンコストを求めることができる。
【００２１】
いくつかの実施形態において、オクルージョンコストを求めることに組み込まれるべき非線形性として、追加のユーザ指定値をオクルージョンコスト計算に直接的に加えることができる。他の実施形態では、オクルージョンコスト計算に使用される顕著性データ（画像顕著性マップ等）に、追加のユーザ指定パラメータを直接的に加えてもよい。例えば、特定の顔（又は特定の画像領域）がオクルージョンされないことが重要である場合、その顔は、画像顕著性データ／マップにおいてユーザ定義パラメータを設定することによって顕著性が高いものとしてマークされ得る。例えば、顔は、顕著性が高い特徴を含むものとしてマークされ得る。これによって、大部分の場合、こうした事前にマークされた顔がオクルージョンされる場合、オクルージョンコストを求めることから、（１又は１に近い）高いオクルージョンコストがもたらされることが確実になる。
【００２２】
また、表１に示されたオクルージョンコスト関数に追加の変数を含めることもでき、それによって、各画像のスケールに関連する項がその関数に追加される。このため、画像のスケールが拡大される場合、そのスケールに関連するコストが低減される。その理由は、スケールが増大することによって、オクルージョンされるか又は別の画像のオクルージョンをもたらす画像のインスタンスが増大するという結果になるためである。表２は、スケーリング情報が追加されたオクルージョンコスト関数のサンプルを示す。
【００２３】
表２に示されるオクルージョンコスト関数の例では、「ｎ」及び「ｍ」を条件付きの値として設定することができる。「ｎ」及び「ｍ」の値が大きいか又は小さいことによって、画像のスケーリングがより積極的になるか又はそれ程積極的でなくなるという結果になる。また、「ｎ」及び「ｍ」の値を、レイアウト方向制約コントローラ３２５及び画像顕著性生成部コントローラ３１５にユーザ指定パラメータとして入力することも可能であり、その結果、レイアウト方向生成及び画像顕著性生成が、１つ又は複数の画像のスケールに従って調整される。
【００２４】
【表２】
2009535696.tif 000004
【００２５】
本発明のいくつかの実施形態において、オクルージョンコストの計算は、レイアウトにおける画像のオクルージョンの面積補償に基づいてオクルージョンコストをより良好に計算するように更に改良され得る。例えば、表示領域に画像を表示する（又は複数の画像を同時に表示する）ために、顕著性データを受け取り、レイアウト方向データを受け取った後、顕著性及び特定のレイアウトに関連するデータを使用して、レイアウトにおける特定の画像のオクルージョンコストを最適に求めることができる。各画像の位置、及び各画像が別の画像と又は表示領域のエッジと如何にオーバラップするかに基づき、オクルージョンコストを求めることができる。そして、以下の３つの相互依存成分に基づいてオクルージョンコストを計算することができる。即ち、表示領域の全顕著性密度、可視の部分顕著性、及びその全情報内容に基づく画像のスケーリングである。
【００２６】
表３に、面積補償オクルージョンコスト計算の特定の例示を示す。表３の式の非簡略化バージョン（等号の左側）には、それぞれ以下の３つの相互依存成分に関連する３つの成分が含まれる。即ち、表示領域の全顕著性密度、可視の部分顕著性、及びその全情報内容に基づく画像のスケーリングである。
【００２７】
【表３】
2009535696.tif 000005
【００２８】
表３において、この計算の表示領域部分における全顕著性密度は、表示領域内で取り込まれる可視顕著性の量を最大限にしようと試みる。この計算の可視の部分顕著性の部分は、１つの画像を別の画像の上にオーバラップさせることによって、又は画像の一部を表示領域のエッジでクロッピングすることによって、レイアウトにおいてオクルージョンされる顕著性の量を最小化しようとする。画像をその内容に基づいてスケーリングすることに向けられる計算の部分は、情報の内容量が多い画像（例えば、風景、屋根、木等）のスケールを増大させ、情報の内容量が少ない画像（例えば単一の顔）のスケールを低減させる方向に、画像コストを重み付けすることによって、表示領域にわたる顕著性の均一な分布をもたらそうとする。計算のフレーム成分の面積は、表示領域の面積である。
【００２９】
一実施形態において、面積補償オクルージョンコストが、表示領域内に同時に表示されるべき２つ以上の画像を含むレイアウトに対して計算されている場合、これは、レイアウトにおける各画像に対して面積補償オクルージョンコストを計算し、その後、レイアウト全体に対して面積補償オクルージョンコストを計算することを含む。各独立した画像のコストの幾何平均（相乗平均）を計算することによって、レイアウト全体に対する面積補償オクルージョンコストを生成することができる。複数の画像が共有表示領域において同時に表示されるレイアウトに対する面積補償オクルージョンコスト計算の関数の一例を表４に示す。
【００３０】
【表４】
2009535696.tif 000006
【００３１】
オクルージョンコスト計算を用いるコラージュ生成の本技術の概要
オクルージョンコスト計算を用いるコラージュ生成の本技術は、画像のコラージュを生成するための方法及びシステムを提供する。本方法及びシステムは、コラージュを生成するためにオクルージョンコスト計算の技術を適用する。これらの技術を適用することによって、本発明の実施形態は、画像領域の著しいオーバラップを提供するが、顔及び他の関心のある領域等、コラージュ画像の顕著領域のオクルージョンを最小化する、コラージュを生成する。本発明のいくつかの実施形態は、顕著性マップ等の顕著性情報を利用して、画像に存在する顔及び他の関心のあるオブジェクト等、顕著領域を識別する。こうした顕著性データを使用することによって、本発明の実施形態は、レイアウトのオクルージョンコストを計算し、顕著であると識別される画像領域のオクルージョンを最小化するコラージュを生成する。また、本発明のいくつかの実施形態は、コラージュが表示されている表示領域に与えられる（attributed）顕著性も利用する。これによって、本発明は、画像顕著性のオクルージョンを表示領域顕著性のオクルージョンと平衡させるオクルージョンコストを計算することが可能になる。これによって、本発明のいくつかの実施形態は、画像のオーバラップを表示領域の効率的な使用と平衡させるコラージュを生成することが可能になる。
【００３２】
コラージュの生成にオクルージョンコスト計算を適用する際、何百も（又は更にそれより多く）の画像のコラージュを自動的に生成することができる。こうしたコラージュが生成され、画像がすべての次元（位置、スケール、回転及びｚ方向の順序（z-order））において自由に移動が可能である場合、コラージュを生成するための解のセットは、本質的に無限である。このため、本発明の実施形態は、解のセットを簡略化しようとする。
【００３３】
例えば、一実施形態において、各画像のスケール及び回転は固定される。これらの自由度を制限することによって、解のセットが制限され、従来の最適化技術を適用することが可能になる。角度の多様性がコラージュの重要な特徴であるため、本発明の一実施形態は、コラージュのレイアウトの前に方向付けの割り当てを強制する。更に、本発明の一実施形態は、レイアウトの前に画像サイズを設定する。レイアウトの前にこれらの制限を適用する利点は、画像回転及びスケーリングが共に計算コストがかかるということである。このため、コラージュ生成中にこれらの操作を繰返し再実行しないことによって、コラージュ生成時間が大幅に短縮される。
【００３４】
本発明の一実施形態において、コラージュレイアウトの「効率」も、コラージュ生成前に固定される。この文脈では、「効率」は、レイアウトの総面積に対する画像の面積の和の比として定義される。低い効率は、画像に、あちこち移動するための十分な空間があり、コラージュ生成中に、仮にあったとしてもわずかにしかオーバラップしないことを示す。高い効率は、画像間で実質的なオーバラップを強制し、顔等の顕著領域の好ましくないオクルージョンの危険性を増大させる。コラージュの生成前にレイアウトの効率を固定することによって、別の自由度が制約され、コラージュを生成するための解のセットがより扱い易くなる。
【００３５】
オクルージョンコスト計算を用いるコラージュ生成の例示的なシステム
図２は、本発明による、コラージュ生成の例示的なシステム２００のブロック図である。システム２００は、デジタル画像の画像データから画像のコラージュを自動的に生成する。システム２００は、画像ローダ２０５と、生成部セレクタ２１０と、加法的コラージュ生成部２１５と、反復的コラージュ生成部２２０とから成る。
【００３６】
画像ローダ２０５は、画像データを受け取り及び操作するためのものであり、一実施形態において、この画像データを提供するコンピュータシステム１００等のコンピュータシステムに結合されている。また、図２に示すように、画像ローダ２０５は、生成部セレクタ２１０にも結合されている。画像ローダ２０５は、更に、生成部セレクタ２１０を介して、加法的コラージュ生成部２１５及び反復的コラージュ生成部２２０に結合されている。加法的コラージュ生成部２１５及び反復的コラージュ生成部２２０は共に、生成されたコラージュを、例えば表示装置又はコンピュータシステム１００の一部に出力するための出力に結合されている。画像ローダ２０５の機能については、図４及び図５に関連して更に説明される。
【００３７】
生成部セレクタ２１０は、画像ローダ２０５に結合するように構成されており、一実施形態において、画像ローダ２０５の一部である。生成部セレクタ２１０は、上記コラージュを生成する際に使用するコラージュレイアウト生成部を選択する。一実施形態において、生成部セレクタ２１０は、この選択を、表示領域においてコラージュされている画像の数に基づいて行う。限定ではなく一例として、一実施形態において、生成部セレクタ２１０は、表示領域内で１５個以下の画像がコラージュされている場合、加法的コラージュ生成部２１５を選択する。同様に、係る実施形態において、生成部セレクタ２１０は、表示領域内で１６個以上の画像がコラージュされている場合、反復的コラージュ生成部２２０を選択する。こうした選択メカニズムは有利である。これは、少数の画像をコラージュにしている際、加法的コラージュ生成部２１５が比較的より効率的であり、多数の画像をコラージュにしている際、反復的コラージュ生成部２２０が比較的より効率的であるからである。
【００３８】
他の実施形態では、コラージュ生成部の選択に対する他のブレークポイントが使用されることは理解される。また、いくつかの実施形態において、生成部セレクタ２１０は、コラージュを生成するための所望のコラージュ効率、又は所望の速度等、ブレークポイントの数又は他の選択基準のユーザ入力に基づいて、加法的コラージュ生成部２１５又は反復的コラージュ生成部２２０を選択することも理解される。また、いくつかの実施形態において、生成部セレクタ２１５とコラージュ生成部のうちの一方（２１５又は２２０）とが利用されないことも理解される。
【００３９】
加法的コラージュ生成部２１５は、生成部セレクタ２１０により命令される際に画像データを受け取るように、画像ローダ２０５に結合するように構成されている。加法的コラージュ生成部２１５は、画像及び表示領域のオクルージョンを最小化するように設計された方法で、表示領域に画像を逐次追加することによってコラージュを生成する。加法的コラージュ生成部２１５については、図６〜図１０に関連して更に説明する。
【００４０】
反復的コラージュ生成部２２０は、生成部セレクタ２１０により命令される際に画像データを受け取るように、画像ローダ２０５に結合するように構成されている。反復的コラージュ生成部２２０は、表示領域内の複数の画像の初期レイアウトのオクルージョンコストを反復的に最小化することによってコラージュを生成する。反復的コラージュ生成部２２０については、図１１〜図１７に関連して更に説明する。
【００４１】
本発明のいくつかの実施形態において、システム２００のコラージュ生成要素（２１５及び２２０）は逐次的に利用される。例えば、１つの係る実施形態において、加法的コラージュ生成部２１５が、生成部セレクタ２１０によって選択され、加法的コラージュ生成プロセス（後述する）を使用して複数の画像の初期コラージュレイアウトを生成する。そして、この加法的に生成されたコラージュが、初期コラージュレイアウトとして反復的コラージュ生成部２２０に結合される。反復的コラージュ生成部２２０は、（後述するように）オクルージョンコストを最小化するために選択的に画像に対してｚ方向の順序付け（z-ordering）及び／又はナッジング（nudging）を行うことによって、この初期コラージュの反復的最適化を実行する。
【００４２】
例示的な画像
図３は、本発明の一実施形態による、表示領域３００に配置されている複数の例示的な画像（３０５、３１０、３１５、３２０、３２５及び３３０）を示す。図３に示される配置は、表示領域内の複数の画像の初期構造化レイアウトの一例である。また、構造化レイアウトは、タイル化エッジ間（tiled edge-to-edge）レイアウト、画像のわずかにオーバラップしたレイアウト、及びパターン又は計画に従って生成された他のレイアウトも含む。係る複数の画像の初期レイアウトは、反復的コラージュ生成部２２０の一実施形態において使用される。
【００４３】
オブジェクトを認識し、画像の顕著な（又は関心のある）部分を決定する技術は知られており、Laurent Itti、 Christof Koch及びErnst Niebur 著、「A Model of Saliency-Based Visual Attention for Rapid Scene Analysis」（IEEE Transactions on Pattern Analysis and Machine Intelligence, 1998年11月）、並びにPaul Viola及びMichael Jones著、「Robust Real-Time Object Detection」（Second International Workshop on Statistical and Computational Theories of Vision - Modeling, Learning, Computing, and Sampling, 2001年７月13日）等の著作物に記載されている。
【００４４】
画像（３０５、３１０、３１５、３２０、３２５及び３３０）の各々は、顕著領域及び非顕著領域を含む。画像３０５では、野球帽を被っている２人の人間が顕著領域とみなされる。画像３１０では、ヨット及び太陽が顕著領域である。画像３１５では、家が顕著領域である。画像３２０では、飛行機が顕著領域である。画像３２５では、両腕を広げている人が顕著領域である。画像３３０では、自転車が顕著領域である。また、これらの画像（３０５、３１０、３１５、３２０、３２５及び３３０）の各々は、何もない空間等の非顕著領域も含む。本発明は、これらの例示的な画像等の画像から、顕著領域の不明瞭化を最小限にしながら画像のオーバラップを促進するコラージュを生成しようとする。本発明は、当該技術分野において知られている画像顕著性マップ等の技術を利用して、画像の顕著領域を識別する。一実施形態において、画像データローダ２０５は、例えば画像のビットマップ等の画像データから係る顕著性マップを生成する。
【００４５】
例示的な画像データローダ
図４は、本発明の一実施形態による、例示的な画像データローダ２０５のブロック図である。画像ローダ２０５は、画像データ受取部４０５と、画像顕著性生成部４１０と、画像スケーリング部４１５と、画像回転部４２０とから成る。図４に示すように、画像データ受取部４０５、画像顕著性生成部４１０、画像スケーリング部４１５及び画像回転部４２０はすべて、互いに且つ共通の出力に結合されている。これによって、必要に応じて、画像データローダ２０５の要素間での情報の交換が可能になる。また、これによって、画像データローダ２０５は、画像ビットマップ、スケーリングされ及び／又は回転した画像ビットマップ、画像顕著性マップ、スケーリングされ及び／又は回転した画像顕著性マップ、及び他の画像データ等の画像データを、システム２００の他の要素に出力することが可能になる。一実施形態において、画像データローダは、係る画像データを、コラージュを生成するために使用される画像タイルの形態（図５の５１０及び５１０Ａ）で出力する。
【００４６】
画像データ受取部４０５は、コンピュータシステム１００等の画像データ源から、画像ビットマップ及び顕著性マップ等の画像データを受け取るか又は取得する。この画像データは、必要に応じて、画像顕著性生成部４１０、画像スケーリング部４１５及び画像回転部４２０に結合される。
【００４７】
画像顕著性生成部４０５は、画像の重要な領域又は関心のある領域を識別する画像顕著性データを生成する。いくつかの実施形態において、顕著性マップの形態をとるこの画像顕著性データは、画像のビットマップ等の画像データから生成される。画像の画像顕著性データは、顕著性マップ、顔認識情報及び他の画像分析情報等の情報を含む。画像顕著性生成部４１０は、顕著性を求めて顔等のオブジェクトを認識する技術等、良く知られた及び確立された画像処理技術に基づいて顕著性データを生成する。また、いくつかの実施形態において、画像顕著性情報は、画像の特定の顕著性領域のユーザによるマーキング等、ユーザ指定パラメータ又は制約に基づいても生成される。
【００４８】
そして、画像顕著性生成部４０５は、画像の顕著領域のランキング又はマッピング等の形態で各画像に対する顕著性データを出力する。例えば、本発明のいくつかの実施形態において、画像顕著性データをグレイスケール画像として表してもよく、その場合、各画素の値は、その画素に対する顕著性スコアである。本発明の他の実施形態において、各画像はマップの形態で渡される顕著性データを有し、それは、マップの各セクションの相対的な顕著性を示すスコアを含むことができる。顕著性データは、画像内の特別な「関心」の分布を表し、そのため、画像のいずれの領域が可視のままであるべきか、及びいずれが安全にオクルージョンされ得るかを表す。
【００４９】
画像スケーリング部４１５は、画像及び／又は画像の顕著性データをスケーリングする。例えば、一実施形態において、画像及び顕著性データは、或る一定面積までスケーリングされる。一実施形態において、この一定面積は、自由度（画像スケール）を低減し、そのため複数の画像からコラージュを生成するための解のセットを簡略化するように、コラージュ生成プロセスを通して固定されたままである。係る実施形態において、画素面積は、一定の線寸法ではなく一定面積として設定される。これによって、画像アスペクト比の多様性を補償する必要性が低減されるか又は除去される。例えば、一実施形態において、画像スケーリング部４１５は、画像及び／又は顕著性マップを３０，０００画素の設定面積にスケーリングする。
【００５０】
画像回転部４２０は、画像データ及び／又は画像顕著性データを回転させる。本発明の一実施形態において、各画像の画像データ及び／又は顕著性データは、ランダムに様々な角度（許容可能な範囲内）で回転させる。別の実施形態では、事前設定パターンに従って、各画像の画像データ及び／又は顕著性データを回転させる。例えば、第１の画像のデータは回転させず、第２の画像のデータを右に１０度回転させ、第３の画像のデータを左に１０度回転させ、その後、後続する画像でパターンを繰り返す。一実施形態では、画像回転部４２０は、回転しスケーリングされた画像及び顕著性データを、コラージュ生成に使用される画像タイル（５１０及び５１０Ａ）として出力する。一実施形態では、この回転は、コラージュ生成プロセスを通して固定されたままであり、それによって自由度（画像回転）が低減され、そのため、複数の画像からコラージュを生成するための解のセットが簡略化される。
【００５１】
図５は、本発明の一実施形態による、画像ロードプロセス中に実行される例示的な画像操作を示す。一例として、一実施形態において、画像データ受取部４０５は、画像３０５等の画像のビットマップ等の画像データを受け取るか又は取得する。画像データ受取部４０５は、この画像データを画像顕著性生成部４１０に渡し、そこで画像データから顕著性マップ５０５が生成される。顕著性マップ５０５は、グレイスケール画像の形態であり、これは、顕著な領域ほど明るい領域として示し、顕著でない領域ほど暗い領域として示す。係る顕著性マップにおいて、顕著性の値は、スケール、例えば０〜２５５に割り当てられることができ、最高顕著性は白色画素及び２５５の値によって表され、最低顕著性は黒色画素及び０の値によって表される。顕著性マップ５０５において、領域５０６及び５０７（画像３０５では２人の人間によって占有されていた）は、高い顕著性を示すようにより明るい陰影として表される。顕著性マップ５０５の残りは比較的暗く、そのため、領域５０６及び５０７を除き顕著性が低いか又は全くないことを示す。
【００５２】
画像顕著性生成部４１０は、画像データ及び顕著性データを画像スケーリング部４１５に渡す。画像スケーリング部４１５は、顕著性マップ５０５及び画像３０５を一定の面積（この場合は小さい方）までスケーリングする。画像スケーリング部４１５は、スケーリングされた画像マップ及びスケーリングされた画像を画像回転部４２０に渡す。画像回転部４２０は、スケーリングされた顕著性マップ及びスケーリングされた画像を右におよそ１０度回転させ、スケーリングされ回転した画像顕著性タイル５１０、及びスケーリングされ回転した画像タイル５１０Ａを出力する。画像データローダ２０５は、これらのタイル（５１０、５１０Ａ）の一方又は両方を出力として提供する。加法的コラージュ生成部２１５及び反復的コラージュ生成部２２０等のコラージュ生成部は、係る画像タイル（５１０及び５１０Ａ）を利用してコラージュを生成する。
【００５３】
画像タイル５１０は、スケールダウンされた顕著性領域５０６Ａ及び５０７Ａを含む、スケーリングされ回転した画像顕著性マップ５０５Ａから成る。画像タイル５１０は、顕著性マップ５０７Ａを包囲する透明領域５１１を囲む可視境界を有するように（例示の目的で）示される。実際には、境界も透明である。透明境界及び透明領域５１１によって、コラージュにおいてタイル５１０の真下に位置する画像又は表示領域空間を見ることが可能になる。
【００５４】
画像タイル５１０Ａは、スケーリングされ回転した画像３０５Ａから成る。また、画像タイル５１０Ａも、画像３０５Ａを包囲する透明領域５１１Ａを囲む可視境界を有するように（例示の目的で）示される。実際には、タイル５１０Ａの境界も透明である。透明な境界及び透明な領域５１１Ａによって、コラージュにおいてタイル５１０Ａの真下に位置する画像又は表示領域空間を見ることが可能になる。
【００５５】
また、図３の残りの画像の追加画像タイルも、タイル５１０Ａを生成するために使用されるこの同じプロセスを介して生成される。これによって、例えば図９、図１０、図１３、図１４、図１６及び図１７に様々に現れるスケーリングされ回転した画像３１０Ａ、３１５Ａ、３２０Ａ、３２５Ａ及び３３０Ａがもたらされる。
【００５６】
例示的な動作方法
以下の論考は、例示的な実施形態の説明を通して本発明の動作を詳細に示す。図７及び図１２を参照すると、フローチャート７００及び１２００はそれぞれ、本発明の様々な実施形態によって使用される例示的なステップを示す。フローチャート７００及び１２００は、様々な実施形態において、コンピュータ可読命令及びコンピュータ実行可能命令の制御下でプロセッサによって実行されるプロセスを含む。コンピュータ可読命令及びコンピュータ実行可能命令は、例えば、図１のコンピュータ使用可能揮発性メモリ１０８、コンピュータ使用可能不揮発性メモリ１１０及び／又はデータ記憶ユニット１１２等のデータ記憶機構に存在する。例えば図１のプロセッサ１０６Ａ、及び／又はプロセッサ１０６Ａ、１０６Ｂ及び１０６Ｃが協働して制御又は動作されるように、コンピュータ可読命令及びコンピュータ実行可能命令が使用される。フローチャート７００及び１２００では特定のステップが開示されているが、係るステップは例示的なものである。即ち、実施形態は、様々な他のステップ又はフローチャート７００及び１２００に列挙されるステップの変形を実行するのによく適している。フローチャート７００及び１２００のステップは、提示されたものとは異なる順序で実行されてもよく、フローチャート７００及び１２００のすべてのステップを実行しなくてもよいことは理解される。
【００５７】
オクルージョンコスト計算を用いる加法的コラージュ生成
図６は、本発明の一実施形態による、例示的な加法的コラージュ生成部２１５のブロック図を示す。図示されるように、加法的コラージュ生成部２１５は、画像シード部６０５と、試行レイアウト提供部６１０と、オクルージョンコスト生成部６１５と、画像追加部６２０とからなり、これらはすべて、必要に応じて、互いに結合されて情報の交換を可能にする。画像シード部６０５は、画像データ及び画像顕著性データを、例えば画像タイル５１０及び５１０Ａの形態で、入力として受け取るように構成されている。画像追加部６２０は、加法的コラージュ生成部２１５によって複数の画像から生成されるコラージュ等の情報を出力するように構成される。加法的コラージュ生成部２１５の要素は、図示された構成とは異なるが同じ動作を達成する他の構成で結合又は配置されてもよいことは理解される。加法的コラージュ生成部２１５の要素の動作については、図７のフローチャート７００の適切な要素と、図８、図９及び図１０に示された画像とに関連して説明する。
【００５８】
図７は、画像のコラージュを加法的に生成する、本発明の一実施形態による方法のフローチャート７００である。フローチャート７００の７１０において、一実施形態では、表示領域内に第１の画像をシードする（seed：供給する）ことによってコラージュを開始する。加法的コラージュ生成部２１５は、画像シード部６０５を使用して、画像タイル５１０又は５１０Ａ等の初期画像を表示領域にシードすることによって、コラージュのレイアウトを開始する。画像シード部６０５は、画像を表示領域の任意の部分にシードすることができる。
【００５９】
本発明の一実施形態において、表示領域の寸法は、画像シード部６０５によって、表示領域内でコラージュされているすべての画像の面積より１０％大きい面積等、所定の面積に設定される。一方、本発明の別の実施形態では、表示領域の寸法（及び面積）は、画像シード部６０５によって変更される。例えば、本発明の一実施形態では、画像シード部６０５は、表示領域の寸法（及び面積）を、表示領域内でコラージュされている画像の総面積に比例して、所定の面積からスケールアップ又はスケールダウンする。別の例では、画像シード部６０５は、ユーザ入力に従って表示領域のサイズを設定する。
【００６０】
コラージュを生成するこの加法的な方法では、表示領域の面積及び寸法の設定は、特定のコラージュ効率を強制するようには行われない（ただし、それに関して幾分か支援はする）。そうではなく、コラージュの表示領域のサイズを増大又は低減するように、且つコラージュのアスペクト比を選択するように行われる。コラージュ効率は、代りに、コラージュが加法的に生成されている表示領域の背景に与えられる顕著性によって主に制御される。
【００６１】
画像シード部６０５によって設定されるコラージュ寸法及び面積は、生成されるコラージュの結果に寄与する。例えば、コラージュされるべき画像の面積よりわずかに大きい表示領域面積を事前定義することによって、コラージュの作成に十分な空間が可能になる。更に、加法的コラージュ生成部２１５は、表示領域の寸法にほぼ一致するアスペクト比になるようコラージュを生成する。寸法を予め決定しなくとも、加法的方法は依然として動作可能であるが、普通でない様々なアスペクト比のコラージュが生成される。更に、画像シード部６０５が表示領域の寸法を設定するため、画像を、定義された表示領域内の特定の場所に意図的にシードすることができる。例えば、一実施形態では、画像シード部６０５は、初期画像を表示領域の中心にシードする。これによって、コラージュは、強制的に、この初期画像から表示領域のエッジに向かって外側に生成される。
【００６２】
図８は、本発明の一実施形態による、表示領域内にシードされた例示的な画像を示す。画像シード部６０５は、矩形表示領域３００の寸法を定義する。いくつかの実施形態において、これらの寸法は、特に正方形、楕円形又は円形等、矩形以外の他の形状で定義される。図８において、画像シード部６０５は、画像３０５Ａを表示領域３００の中心にシードして、コラージュ８００の初期画像を形成する。画像３０５Ａは、画像タイル５１０（図５）からのものと同じスケーリングされ回転した画像である。しかしながら、画像タイル５１０Ａの透明境界及び透明領域５１１は可視でなく、従って、加法的生成のこの中間ステップにおいてコラージュが観察者に実際にいかに見えるかを示す。
【００６３】
フローチャート７００の７２０において、一実施形態では、複数の試行レイアウト配置を提供する。試行レイアウト配置の各々において、コラージュレイアウトに追加画像を追加する。試行レイアウト提供部６１０は、複数の試行レイアウト配置を生成及び提供する。試行レイアウト配置部６１０は、追加画像を逐次受け取るか、又は表示領域３００内で一緒になるようにコラージュされている複数の画像から追加画像を選択する。例えば、本発明の一実施形態において、試行レイアウト提供部６１０は、コラージュされている複数の画像から１つの画像を選択し、それを使用して特定の複数の試行レイアウト配置を生成する。この例によれば、この特定の複数の試行配置は、次にオクルージョンコスト生成部６１５に渡される。
【００６４】
図９は、本発明の一実施形態による、コラージュレイアウトに追加された例示的な画像を示す。図９は、試行レイアウト提供部６１０によって生成された特定の複数の試行レイアウト配置からの１つの試行レイアウト配置の例である。図９に示された試行レイアウト配置は、表示領域３００内でコラージュ８００に追加された追加画像３１０Ａから成る。なお、画像３０５Ａは、先に図８で示されたものと同じ２次元位置にとどまっていることに留意されたい。この特定の複数の試行レイアウトの他の試行レイアウトでは、画像３０５Ａの２次元位置は固定されたままであり、追加画像（この場合は３１０Ａ）の２次元位置及びｚ方向の順序付けされる位置は変化する。そして、一実施形態では、複数の試行レイアウト配置のうちのいくつかは、既存のコラージュより上方にｚ方向に順序付けされた追加画像の複数の２次元位置からなり、複数の試行レイアウト配置のうちのいくつかは、既存のコラージュより下方にｚ方向に順序付けされた追加画像の複数の２次元位置から成る。
【００６５】
一実施形態では、複数の試行レイアウトの総数は、予め設定されている。一方、別の実施形態では、試行レイアウトの数は、例えばコラージュ生成タイムラインを短くするためのユーザ入力に応じて変化する。同様に、例えばデジタルカメラ等の計算能力が低減したいくつかの実施形態では、コラージュ生成の速度を向上させるように、生成される試行レイアウト配置の数が少ない。
【００６６】
フローチャート７００の７３０において、一実施形態では、複数の試行レイアウト配置のうちの１つの試行レイアウト配置に対して、オクルージョンコストを生成する。オクルージョンコストは、試行レイアウト配置によってオクルージョンされる画像顕著性及びオクルージョンされる表示領域顕著性を表す。オクルージョンコスト生成部６１５は、この試行レイアウト配置に対するオクルージョンコストを生成する。一実施形態において、オクルージョンコスト生成部は、特定の複数の試行レイアウト配置の１０％又は１００％等、或る部分に対するオクルージョンコストを計算する。
【００６７】
オクルージョンコスト生成部は、コラージュが生成されている表示領域（表示領域３００等）の内部領域に顕著性を与える（attribute）。一実施形態において、この表示領域顕著性は予め決定されているが、別の実施形態では、この表示領域顕著性は、ユーザ入力を介してオクルージョンコスト生成部６１５によって制御される。一実施形態において、例えば、オクルージョンコスト生成部６１５は、表示領域によって包含される全領域の各画素に一様な所定の顕著性を与える。表示領域顕著性に対する正確な画素値によって、コラージュのオーバラップに関する積極性の精密なレベルの制御、及び結果としての効率が与えられる。例えば、一実施形態において、画像顕著性マップにおける顕著性が０（顕著性なし）から２５５（最高顕著性）まで変化する場合、オクルージョンコスト生成部６１５は、表示領域の各画素の顕著性を１０の値（低顕著性）に設定することができる。より高い一様な顕著性を表示領域の画素に与えることによって、より積極的にオーバラップして表示領域のより少ない部分を覆う、より効率的なコラージュがもたらされる。同様に、より低い一様な顕著性を表示領域の画素に与えることによって、オーバラップに積極的でなく表示領域のより多くの部分を覆う、より効率の低いコラージュがもたらされる。表１(先に示した）は、オクルージョンコスト生成部６１５が、オクルージョンされる画像顕著性を表すと共にオクルージョンされる表示領域顕著性を表すオクルージョンコストを生成するために使用され得る、１つの式を示す。
【００６８】
オクルージョンコストは、特定のレイアウトにおいて可視である部分（fractional：分数の）顕著性の逆数である。表５は、オクルージョンコスト生成部６１５が、表示領域内において特定の試行レイアウト配置で可視である部分顕著性を生成するために使用することができる１つの式を示す。部分顕著性は、０〜１の間で変化し、数が大きいほどより可視の顕著性が高いことを示す。この部分可視顕著性計算に基づき、オクルージョンコスト生成部６１５は、表１に示される式によって計算されるオクルージョンコストと一致するオクルージョンコストを生成する。
【００６９】
【表５】
2009535696.tif 000007
【００７０】
表１及び表５に示される式は例示的なものであり、理解されるように、試行レイアウト配置に対するオクルージョンコストを計算する他の計算を利用することができ、この場合、オクルージョンコストは、その試行レイアウト配置によってオクルージョンされる画像顕著性とオクルージョンされる表示領域顕著性とを表す。オクルージョンコスト生成部６１５は、試行レイアウト配置に対する生成されたオクルージョンコストを画像追加部６２０に渡す。
【００７１】
フローチャート７００の７４０において、一実施形態では、コラージュに画像を追加する。一実施形態において、画像がコラージュに追加されると、コラージュは、オクルージョンコストが計算された試行レイアウト配置のうちの１つを反映するように更新される。画像追加部６２０は、コラージュに新たな画像を追加する。一実施形態において、画像追加部６２０は、オクルージョンコストを受け取る試行レイアウト配置の各々に関してオクルージョンコストを比較する。この比較に基づき、画像追加部６２０は、オクルージョンコストが最も低い試行レイアウト配置を選択する。そして、画像追加部６２０は、最も低いコスト試行レイアウト配置から、コラージュに追加画像を追加する。新たな画像（追加画像）は、追加画像が最も低いコストの試行レイアウト配置内に現れるものと同じｚ方向に順序付けられた位置及び２次元位置においてコラージュに追加される。
【００７２】
フローチャート７００の７５０において、一実施形態では、コラージュされるべき複数の画像の残りの画像は、複数の画像からのすべての画像が逐次にコラージュに追加されるまで、ブロック７２０、７３０及び７４０を繰り返すことによって、コラージュ内に加法的に組み込まれる。
【００７３】
図１０は、本発明の一実施形態によって作成された例示的なコラージュ８００を示す。図１０は、図３に示された複数の画像（３０５、３１０、３１５、３２０、３２５及び３３０）から加法的（追加式）に生成された例示的な結果としてのコラージュを示す。各画像は、上述したプロセスを通して画像タイルに変換されている。そして、画像タイルは、表示領域３００内に加法的にコラージュされている。コラージュは、上述した画像タイルの一部である、スケーリングされ回転した画像３０５Ａ、３１０Ａ、３１５Ａ、３２０Ａ、３２５Ａ及び３３０Ａから成る。なお、図１０では、画像の積極的なオーバラップがかなりあることに留意されたい。これは、表示領域３００の顕著性に対して高い値が設定されているためである。より低い表示領域顕著性の値を選択することによって、表示領域３００にわたってより広く間隔をおいて配置された画像がもたらされる。より寸法の小さい表示領域を選択することによって、表示領域３００内でコラージュ８００を包囲する空所がより少なくなる。
【００７４】
オクルージョンコスト計算を用いる反復的コラージュ生成
図１１は、本発明の一実施形態による、反復的コラージュ生成部２２０のブロック図である。図示するように、反復的コラージュ生成部２２０は、初期レイアウト生成部１１０５と、レイアウト調整部１１１０と、オクルージョンコスト生成部１１１５と、レイアウト最適化部１１２０とからなり、これらはすべて互いに結合されて、必要に応じて情報を交換するのを可能にする。初期レイアウト生成部１１０５は、例えば画像タイル５１０及び５１０Ａの形態で、画像データ及び画像顕著性データを入力として受け取るように構成されている。レイアウト最適化部１１２０は、反復的コラージュ生成部２２０によって複数の画像から生成されるコラージュ等の情報を出力するように構成されている。反復的コラージュ生成部２２０の要素が、図示された構成とは異なるが同じ動作を達成する他の構成で結合又は配置され得ることは理解される。
【００７５】
一実施形態において、初期レイアウト生成部１１０５は、複数の画像から初期コラージュレイアウトを生成するものである。初期コラージュレイアウトが入力として提供されるいくつかの実施形態では、初期レイアウト生成部１１０５は使用されない。一実施形態において、レイアウト調整部１１１０は、コラージュレイアウトを増分的に調整するものである。一実施形態において、オクルージョンコスト生成部１１１５は、増分的に調整されたコラージュレイアウト等、コラージュレイアウトに対するオクルージョンコストを計算するものである。一実施形態において、レイアウト最適化部１１２０は、オクルージョンコストが最低である増分的に調整されたレイアウトを選択するものである。反復的コラージュ生成部２２０のこれら要素のさらなる動作については、図１２のフローチャート１２００の適切な要素と、図１３、図１４、図１５、図１６及び図１７に示された画像とに関連して説明する。
【００７６】
図１２は、画像のコラージュを反復的に生成する、本発明の一実施形態による方法のフローチャート１２００である。フローチャート７００の１２１０において、一実施形態では、表示領域内でコラージュされるべき複数の画像に関して、画像顕著性データを受け取る。反復的コラージュ生成部２２０は、初期レイアウト生成部１１０５を使用して、この画像顕著性データを受け取る。本発明のいくつかの実施形態において、初期レイアウト生成部１１０５は、画像ビットマップ、画像顕著性データ、及び画像タイル（画像タイル５１０及び５１０Ａ（図５）など）等の画像データから成る種々の画像情報を受け取る。
【００７７】
フローチャート１２００の１２２０において、一実施形態では、複数の受け取られた画像から表示領域内で初期コラージュレイアウトを生成する。一実施形態において、初期レイアウト生成部１１０５は、画定された表示領域内に画像タイルを配置することによって、画像タイル５１０又は５１０Ａ等、複数の受け取った画像タイルからこの初期コラージュレイアウトを生成する。初期レイアウト生成部１１０５は、アスペクト比及びコラージュ効率に対する予め定義された値、又はユーザが選択した値を使用することによって、表示領域の寸法（反復的コラージュ生成プロセスを通じて一定のままである）を決定する。例えば、一実施形態において、ユーザ入力に応じて、初期レイアウト生成部１１０５は、アスペクト比が１．３３：１であり効率が１．１５である矩形表示領域を生成する。これは、生成された表示領域内でコラージュされたすべての画像の総面積が、コラージュの総領域の面積より１５％大きくなることを意味する。
【００７８】
一実施形態において、初期レイアウト生成部１１０５は、パターン、格子、又は他の何らかの構造化手段に従って、画像タイル等の画像をレイアウトする。図３は、パターンに従って生成される複数の画像（３０５、３１０、３１５、３２０、３２５及び３３０）の初期コラージュレイアウトの例である。初期レイアウト生成部１１０５は、パターンに従って画像を表示領域３００内に配置することによって、図１３に示された初期コラージュレイアウトを生成している。別の実施形態では、初期レイアウト生成部は、画像タイル等の画像を、表示領域内にランダムに又は擬似ランダムに配置して、初期コラージュレイアウトを生成する。
【００７９】
図１３は、本発明の一実施形態による、複数の画像の例示的な初期コラージュレイアウトを示す。図１３において、初期コラージュ生成部１１０５は、表示領域３００内に画像３０５Ａ、３１０Ａ、３１５Ａ、３２０Ａ、３２５Ａ及び３３０Ａをランダムに配置して、この複数の画像の初期コラージュレイアウト１３００を生成する。上述したように、画像（３０５Ａ、３１０Ａ、３１５Ａ、３２０Ａ、３２５Ａ及び３３０Ａ）の各々は、タイル５１０Ａ等の画像タイルの一部であり、したがってコラージュ生成プロセスを通じて維持される事前設定された画像スケール及び回転を有する。この事前設定されたスケール及び回転は、反復的コラージュ生成プロセスの一部としてコラージュ１３００に対して課される可能性のある画像のｘ−ｙ位置、又はｚ方向の順序付けのいかなる変化にも関わらず維持される。
【００８０】
フローチャート１２００の１２２０において、一実施形態では、初期コラージュレイアウトを最適化する。最適化は、最小化オクルージョンコストに対する選択を通して初期レイアウトを反復的に調整することを含む。本発明の一実施形態において、この反復的調整及び選択は、コラージュレイアウトに対して所定の効率が達成されるまで継続される。本発明の一実施形態では、この反復的調整及び選択は、例えば１００回の反復等、所定数の調整反復が達成されるまで継続される。レイアウト調整部１１１０、オクルージョンコスト生成部１１１５、及びレイアウト最適化部１１２０は、協力して動作して、初期コラージュレイアウトのこの最適化を実施する。表６は、初期コラージュレイアウトの反復的最適化を実行する方法を説明する例示的な擬似コード構造を示す。
【００８１】
【表６】
2009535696.tif 000008
【００８２】
一実施形態において、オクルージョンコスト生成部１１１５は、初期コラージュレイアウトにおいて可視である部分顕著性に対する、すべてのタイルに存在する全顕著性の比から、初期コラージュレイアウトに対するオクルージョンコストを計算する。この第２の部分、即ち「初期コラージュレイアウトにおいて可視である部分顕著性」は、コラージュの「平坦化」レイアウトから計算される。コラージュのレイアウトを平坦化することは、コラージュのスナップショットを観察者に見えるように、撮ることとして考えることができる。しかしながら、各画像（例えば、タイル５１０Ａに関連付けられる画像データ）に対してフルカラー画像データを使用せずに、スナップショットは、代わりにコラージュの各画像に対して対応する顕著性マップを使用してレンダリングされる（例えば、画像タイル５１０Ａの画像データの代りに画像タイル５１０の顕著性データを使用する）。そして、この平坦化コラージュレイアウトに対する顕著性は、スナップショットにおいて可視である顕著性を合計すること（Ｓｖ）によって計算される。
【００８３】
表７は、コラージュレイアウトのオクルージョンコストを計算するためにオクルージョンコスト生成部１１１５によって使用される例示的な式を示す。そして、この初期レイアウトのオクルージョンコストは、レイアウト最適化部１１２０によって「事前スコア」として保持される。この事前スコアを使用して、将来のコラージュレイアウトを初期レイアウトより良いか又は悪いかとして評価する。
【００８４】
【表７】
2009535696.tif 000009
【００８５】
前述したように、オクルージョンコストは、コラージュレイアウトにおける可視顕著性の分数の逆関数である。表７の式における関連変数は、可視顕著性ＳＶ及び全顕著性ＳＴである。ＳＴは、すべての画像（図５の画像タイル５１０及び５１０Ａ等）にわたって加算された全顕著性である。ＳＶは、平坦化プロセスが実行された後にすべての画像タイルにわたって全可視顕著性を加算することによって同じコラージュレイアウトに対して得られる。平坦化によって、一般にいくつかの画像タイルにおいていくらかの顕著性のオクルージョンがもたらされるため、ＳＶは、一般にＳＴより小さくなり、対応するオクルージョンコストは１未満になる。
【００８６】
オクルージョンコスト生成部１１１５が初期コラージュレイアウトのオクルージョンコスト「事前スコア」を計算した後、初期レイアウトのＺ方向の順序付けの最適化が実行される。最も一般的な場合、これには、ｚ方向の順序内の画像のすべての順列に対するオクルージョンコストの計算が含まれる。しかしながら、計算の複雑性及び／又は計算時間を低減するために、いくつかの実施形態において、ｚ方向の順序付けの順列のサブセットに対してのみオクルージョンコストが計算される。
【００８７】
例えば、本発明の一実施形態において、レイアウトオクルージョンコストは、画像タイルにおいてコラージュにおける複数の画像のうちの他のすべての画像の上方及び下方に画像をｚ方向に順序付けするために計算される。このｚ方向の順序付けの最適化は、簡単なプロセスである。レイアウト調整器１１１０は、画像タイル等の各画像を以下の２つの位置のうちの一方でコラージュに順に追加する。即ち、ｚ方向の順序の上側（任意の他の画像の前）、又はｚ方向の順序の下側（任意の他の画像の下）である。そして、オクルージョンコスト生成部１１２０は、上述したように画像タイルの各位置に対してオクルージョンコストを計算する。レイアウト最適化部１１２０は、最低コストのレイアウトを、画像タイルに対する最適なｚ方向の順序位置として選択する。そして、コラージュレイアウトは、計算されたオクルージョンコストに基づく最低レイアウトオクルージョンコストを反映するように更新される。そして、このｚ方向の順序付け、計算、及び更新は、コラージュ内の複数の画像タイルの画像の各々に対して繰り返される。ｚ方向の順序付けは、すべての画像タイルがこのように順序付けられたときに完了する。同様に、表示領域内における画像のｚ方向順序の順列のより大きいセットに対してオクルージョンコストを計算する本発明の実施形態において、同様の最適化プロセス、即ちｚ方向の順序付け、計算、及び更新が続く。
【００８８】
図１４は、本発明の一実施形態による、コラージュレイアウトのオクルージョンコストを最小化する画像の例示的なｚ方向の順序付けを示す。図１４に示されたコラージュレイアウト１３００のすべての要素は、図１３で行われていた画像顕著性のオクルージョン（画像３０５Ａの右側の人の下半分）をなくすように、画像３０５Ａが画像３３０Ａの上に最適にｚ方向の順序付けがされていることを除いて、図１３に示されたコラージュレイアウト１３００と同一である。
【００８９】
ｚ方向の順序付けが実行された後、オクルージョンコスト生成部１１１５はコラージュレイアウトを平坦化し、レイアウトのオクルージョンコストを求める。表６の擬似コードによって示されるように、その後、ｚ方向の順序付けされたレイアウトに対するこのオクルージョンコストは、先に格納された事前スコアに取って代る。
【００９０】
そして、表示領域内の各画像（画像タイル等）の２次元ｘ−ｙ位置を最適化し、最低の２次元的に調整されたレイアウトのオクルージョンコストを有するコラージュレイアウトを選択するように、同様の反復プロセスが続く。ここでも、レイアウト調整部１１１０、オクルージョンコスト生成部１１１５及びレイアウト最適化部１１２０が協力して動作し、各画像タイルを２次元でわずかにナッジし（nudge：動かし）、各ナッジング動作後に計算されたオクルージョンコストから各画像の最適な２次元位置を反復的に選択する。一実施形態において、各画像タイルは、元の位置から４つの方向（上、下、左及び右）にわずかにナッジされている。
【００９１】
例えば、レイアウト調整部１１１０は、単一の画像のｘ−ｙ位置に対してわずかな調整を行う。そして、オクルージョンコスト生成部１１１５は、調整されたレイアウトを平坦化し、このわずかに２次元的に調整されたレイアウトに対してオクルージョンコストを計算する。そして、レイアウト最適化部１１２０は、このわずかに調整されたレイアウトのオクルージョンコストを、格納されたレイアウトのスコアと比較する。レイアウト最適化部１１２０は、調整されたレイアウトがより小さいオクルージョンコストを有する場合、調整されたレイアウトを反映するように格納されたレイアウトを更新する。そして、この更新されたレイアウトは、レイアウト調整部が次のわずかなナッジング調整を行う有効なレイアウトとなる。反復的ナッジング、平坦化、計算、及び更新は、複数のコラージュされる画像タイルの各画像タイルが最適にナッジされるまで継続する。
【００９２】
図１５は、本発明の一実施形態による、例示的な画像に対する例示的な２次元ナッジングの可能性を示す。図１５において、画像タイル５１０Ａは、今度の場合も可視で表示されており、透明領域５１１及び画像３０５Ａを包囲する。位置１５０１は、画像タイル５１０Ａの左上隅の元の位置を表す。位置１５０２、１５０３、１５０４及び１５０５は、画像調整部１１１０がナッジングプロセス中に画像タイル５１０Ａをナッジすることができるわずかな距離を表す。例えば、一実施形態では、位置１５０２は、元の位置１５０１の上のわずかな距離１５２０、例えば１０画素である。この例によれば、位置１５０３は元の位置１５０１の１０画素右のわずかな距離１５２２であり、位置１５０４は、元の位置１５０１の１０画素下方のわずかな距離１５２１であり、位置１５０５は、元の位置１５０１の１０画素左のわずかな距離１５２３である。オクルージョンコスト生成部１１１５は、元の位置と、考えられるナッジされた位置１５０２、１５０３、１５０４及び１５０５の各々とに対するオクルージョンコストを生成する。レイアウト最適化部１１２０は、比較を実行し、最低オクルージョンコストを提示するナッジされた位置を選択する。いくつかの実施形態において、レイアウトは、図１５に示されたものより少ない方向若しくは多い方向、又は多くの距離若しくは少ない距離にナッジされ得ることは理解される。
【００９３】
図１６は、本発明の一実施形態による、コラージュレイアウトのオクルージョンコストを最小化する例示的な画像ナッジングを示す。図１６に示されたコラージュ１３００のすべての要素は、画像３０５Ａが画像タイル３３０Ａの上方の、その先の位置のわずか左の２次元位置にナッジされていることを除いて、図１４に示されたコラージュレイアウト１３００と同じである。
【００９４】
一実施形態において、上述したｚ方向の順序付け及びナッジングの選択的調整動作は、反復的に選択されるコラージュによって所定の又は最適なオクルージョンコストに達するまで繰り返される。別の実施形態では、上述したｚ方向の順序付け及びナッジングの選択的調整動作は、所定数の係る調整の反復に達するまで繰り返される。係る反復の所定数の一例は１００である。これは、コラージュを反復的に生成するのに費やされる時間及び／又は計算資源の量を制限するのに有用である。また、それは、ユーザが選択したコラージュ効率レベルが特定の複数の画像に対して達成不可能である場合、フェールセーフ終了基準としても有用である。別の実施形態では、ｚ方向の順序付け及びナッジングの選択的調整動作は、画像を任意の方向にナッジするか又は任意の画像のｚ方向の順序位置を変更することによって、全オクルージョンコストをそれ以上下げることができなくなるまで継続する。
【００９５】
図１７は、本発明の一実施形態によって作成された例示的なコラージュを示す。図１７は、図３に示された複数の画像（３０５、３１０、３１５、３２０、３２５及び３３０）から反復的に生成された例示的な結果としてのコラージュを示す。図１７に示されたコラージュは、上述したｚ方向の順序付け及びナッジングの選択的調整動作の多数の反復の結果である。各画像は、上述したプロセスを通して画像タイルに変換されている。そして、画像タイルは、表示領域３００内に反復的にコラージュされている。コラージュは、上述した画像タイルの一部であるスケーリングされ回転した画像３０５Ａ、３１０Ａ、３１５Ａ、３２０Ａ、３２５Ａ及び３３０Ａから成る。なお、図１７では、非常に積極的な画像のオーバラップがあることに留意されたい。これは、コラージュ１３００の反復的生成に対して高い効率が設定されているためである。より低い効率を選択することによって、オーバラップがさほど積極的でなく、表示領域３００にわたってより広く間隔をおいて配置された画像がもたらされる。
【図面の簡単な説明】
【００９６】
【図１】本発明の実施形態によって使用される例示的なコンピュータシステムの図である。
【図２】本発明によるコラージュ生成の例示的なシステムのブロック図である。
【図３】本発明の一実施形態による、表示領域に配置される複数の例示的な画像を示す図である。
【図４】本発明の一実施形態による、例示的な画像データローダのブロック図である。
【図５】本発明の一実施形態による、画像ロードプロセス中に実行される例示的な画像操作を示す図である。
【図６】本発明の一実施形態による、例示的な加法的コラージュ生成部のブロック図である。
【図７】本発明の一実施形態による、画像のコラージュを加法的に生成する方法のフローチャートである。
【図８】本発明の一実施形態による、表示領域内にシードされる例示的な画像を示す図である。
【図９】本発明の一実施形態による、コラージュレイアウトに追加される例示的な画像を示す図である。
【図１０】本発明の一実施形態によって作成される例示的なコラージュを示す図である。
【図１１】本発明の一実施形態による、反復的コラージュ生成部のブロック図である。
【図１２】本発明の一実施形態による、画像のコラージュを反復的に生成する方法のフローチャートである。
【図１３】本発明の一実施形態による、複数の画像の例示的な初期コラージュレイアウトを示す図である。
【図１４】本発明の一実施形態による、コラージュレイアウトのオクルージョンコストを最小化するための画像の例示的なｚオーダリングを示す図である。
【図１５】本発明の一実施形態による、例示的な画像に対する例示的な２次元ナッジングの可能性を示す図である。
【図１６】本発明の一実施形態による、コラージュレイアウトのオクルージョンコストを最小化するための例示的な画像ナッジングを示す図である。
【図１７】本発明の一実施形態によって作成される例示的なコラージュを示す図である。
【図１】
2009535696.tif 000010
【図２】
2009535696.tif 000011
【図３】
2009535696.tif 000012
【図４】
2009535696.tif 000013
【図５】
2009535696.tif 000014
【図６】
2009535696.tif 000015
【図７】
2009535696.tif 000016
【図８】
2009535696.tif 000017
【図９】
2009535696.tif 000018
【図１０】
2009535696.tif 000019
【図１１】
2009535696.tif 000020
【図１２】
2009535696.tif 000021
【図１３】
2009535696.tif 000022
【図１４】
2009535696.tif 000023
【図１５】
2009535696.tif 000024
【図１６】
2009535696.tif 000025
【図１７】
2009535696.tif 000026
【国際調査報告】
2009535696.tif 000027
2009535696.tif 000028
2009535696.tif 000029