JP2010512607A - デジタルコラージュのための画像処理システム - Google Patents

Abstract

複数の入力画像から、視覚的に魅力的なコラージュを形成する自動化プロセス向けのフレームワークを提供することが必要とされている。柔軟かつ堅固でありながら、しかも関連するソフトウェアアプリケーションと容易に接続することができるこの種の自動化プロセス向けのフレームワークを提供することが必要とされている。画像合成フレームワークは、第１のモジュール、複数の事前計算モジュール、および画像合成モジュールを有するモジュラーアーキテクチャが備えられている。第１のモジュールはアプリケーションプログラミングインターフェイスを提供し、事前計算モジュールは入力画像に関する情報を計算し、画像合成モジュールは計算された情報を入力画像と共に使用してデジタルコラージュを形成する。

Description

この説明は一般に、デジタルタペストリおよびフォトモンタージュとしても知られるデジタルコラージュを複数のデジタル画像から作成するための画像処理に関する。

複数の入力画像から、視覚的に魅力的なコラージュを形成する自動化プロセス向けのフレームワークを提供することが必要とされている。そのようなコラージュを形成することは、特に、入力画像の数が増大し、視聴者にとって魅力的な視覚画像サマリの一種としての役割を果たすコラージュを生成することが求められる場合に、困難な問題である。加えて、柔軟かつ堅固でありながら、しかも関連するソフトウェアアプリケーションと容易に接続することができるこの種の自動化プロセス向けのフレームワークを提供することは困難である。

画像タペストリまたは画像コラージュを生成する手動の方法は、知られている。たとえば、消費者の写真のコレクションを手動で区分化して結合することによって生成する方法がある。これらの写真は、商用画像編集ソフトウェアを使用することなどによって、手動でトリミングされて結合され、手動で生成されたタペストリを形成することができる。しかし、これには多大な時間を要し、ユーザ側には膨大なスキルと知識が求められる。

従来の自動化の手法は、すでに広く互換性のある画像を、継ぎ目に沿ってほぼ整合させることによって、組み合わせることに依存していた。次に必要となるのは、継ぎ目を目立たなくするために、継ぎ目を調整することだけである。しかし、すでに広く互換性があるわけではない画像を使用することが求められている。

米国特許出願第１１／５５２，３１２号明細書

Itti, L. Koch, C., and Niebur, E. 1998, "A model of saliency based visual attention for rapid scene analysis. IEEE Trans. on Pattern Analysis and Machine Intelligence 20, 11 Crow, F. 1984 "Summoned area tables for texture mapping", in Proc. ACM Siggraph, ACM, 207-212 Waltz, D, 1975 "Understanding line drawings of scenes with shadows", in the Psychology of Vision, W.P.H., Ed McGraw-Hill, New York Marriott, K and Stuckey, P, 1998, "Programming with Constraints", The MIT Press Boykov, Y Veksler, O and Zabih, R, 2001 "Fast approximate energy minimization via graph cuts", IEEE Trans on Pattern Analysis and Machine Intelligence 23, 11 Perez, P., Gagnet, M., and Blake, A. 2003 "Poisson image editing." ACM Trans. Graph. 22, 3, 313-318 Agarwala, A. et. al. 2004 "Interactive digital photomontage". ACM Trans. Graph. 23, 3, 294-302

以下の説明は、読者に基本的な理解をもたらすために、本開示の概要を簡略化して示すものである。この要約は、本開示の広範にわたる概要ではなく、本発明の主要／重要要素を識別するものでもなく、また本発明の範囲を規定するものではない。この要約の唯一の目的は、本明細書に開示される一部の概念を、これ以降提示されるさらに詳細な説明への導入として、簡略化した形式で提示することである。

複数の入力画像から、視覚的に魅力的なコラージュを形成する自動化プロセス向けのフレームワークを提供することが必要とされている。柔軟かつ堅固でありながら、しかも関連するソフトウェアアプリケーションと容易に接続することができるこの種の自動化プロセス向けのフレームワークを提供することが必要とされている。画像合成フレームワークは、第１のモジュール、複数の事前計算モジュール、および画像合成モジュールを有するモジュラーアーキテクチャが備えられている。第１のモジュールはアプリケーションプログラミングインターフェイスを提供し、事前計算モジュールは入力画像に関する情報を計算し、画像合成モジュールは計算された情報を入力画像と共に使用してデジタルコラージュを形成する。

付随する特徴の多くは、添付の図面と併せて検討される以下の詳細な説明を参照することによって、理解もより深まり、さらに容易に認識されるであろう。

本発明の説明は、付属の図面を踏まえて以下の詳細な説明を読めば、さらに深く理解されよう。

ソフトウェアアプリケーションに接続された画像合成フレームワークを示す概略図である。 画像合成フレームワークを使用してデジタルコラージュを形成する方法を示す流れ図である。 図３Ａは入力画像を示す概略図である。図３Ｂは関心領域が表示された図３Ａの入力画像を示す概略図である。図３Ｃは図３Ａの入力画像から得られた事前行列を示す概略図である。 画像合成フレームワークを使用する方法を示す流れ図である。 画像合成フレームワークを初期化して、そのフレームワークを構成し、正規化方法を指定する方法を示す流れ図である。 画像合成フレームワークを使用して入力画像をランク付けする方法を示す流れ図である。 画像合成フレームワークを使用して事前計算および画像合成を実行する方法を示す流れ図である。 画像合成フレームワークを示す状態遷移図である。 画像合成フレームワークを提供し、デジタルコラージュを形成できるようにする装置を示す概略図である。 コラージュの作成に使用するエネルギー関数を作成する方法を示す流れ図である。 最適化プロセスを示す流れ図である。

添付の図において、類似した参照番号は類似する部分を示すために使用される。

付属の図面に関連して以下に示される詳細な説明は、本発明の実施例を説明することを意図したものであり、本発明の実施例が構成されるかまたは使用されうる唯一の形態を表すことを意図したものではない。説明は、実施例の機能、および実施例を構成して操作するためのステップの順序を示す。しかし、同一または同等の機能および順序は、さまざまな実施例によって達成されうる。

本発明の実施例は、本明細書においてデジタル写真からコラージュを生成するシステムにおいて実施されることが説明され表されているが、説明されるシステムは、限定的ではなく例示的なものとして提供される。当業者であれば理解されるように、本発明の実施例は、ビデオからのスチル写真、医療用画像、ＵＶ画像、ＩＲ画像、または任意の他の適切な種類の画像など、任意の種類のデジタル画像を使用する、多種多様な種類の選択および／またはラベル付けのシステムにおける用途に適している。

図１は、画像合成フレームワーク１０８の概略図である。フレームワーク１０８は、ソフトウェアフレームワークとして、または任意の他の適切な形式で提供され、複数のモジュールを備える。フレームワーク１０８は、任意の適切な形式で入力画像１００を受信し、入力画像１００の全部または一部からデジタルコラージュ画像１０４を生成する。入力画像および出力デジタルコラージュ画像は、ＪＰＥＧ、ＢＭＰ、ＧＩＦ、およびＰＮＧを含む任意の適切な形式であってもよいが、これらに限定されることはない。入力画像は、アルファチャネルが存在し、たとえばモノクロームから３２ビットまでの任意の画像の色の深みであってもよいアルファ情報を備えることができる。出力デジタルコラージュ画像のサイズは、任意の幅および高さになるように制御することができる。

たとえば、複数の入力画像１００は、休日のようなイベントの約５０枚の写真の個人データセットであるコレクションであってもよい。写真は、サイズがさまざま異なっていることもあり、また結合するために継ぎ目に沿ってすでにほぼ整合されているわけではないという点で相互に異なっている場合もある。たとえば、写真の一部には、夜間に撮られたものもあり、また昼間に撮られたものもある。その他、景色の写真の場合もあれば、人々の肖像写真の場合もある。コラージュを形成することにより、入力画像の一部または全部の部分の混合物である単一の画像が生成される。したがって、コラージュは、たとえば家族の休日の画像をまとめるための、入力画像の一種の視覚的なサマリとしての役割を果たす。複数の入力画像が、すべて特定のイベントなどによって相互に関連している必要はない。

コラージュは、たとえば、画像コレクションの「サムネイル」として、入力画像のコレクションのことをユーザに連想させることができる。場合によっては、コラージュは、画像検索システムとしての役割を果たすことができる。たとえば、ユーザは、コラージュの１つまたは複数の部分を選択することができ、コラージュシステムは、類似した画像特性を有する１つまたは複数の画像を検索することができ、選択された領域に示された画像を提供する入力画像を検索することなどができる。

画像合成フレームワーク１０８は、パブリックであってもよく、１つまたは複数のソフトウェアアプリケーション１０５に接続できるように配置されるアプリケーションプログラミングインターフェイス（ＡＰＩ）１０６を有する第１のモジュール１０１を備える。第１のモジュール１０１は、ＡＰＩ １０６と統合されていることを示す点線で図１に示される。画像合成フレームワーク１０８はまた、１つまたは複数の事前計算モジュール１０２および画像合成モジュール１０３を備える。１つまたは複数の第１のモジュール１０１，事前計算モジュール１０２、および画像合成モジュール１０３は、ダイナミックリンクライブラリとして提供されてもよい。これらのモジュールは、任意の適切なフォーマットで提供することができる。事前計算モジュール１０２および画像合成モジュール１０３は各々、統合パブリックＡＰＩ １０６を備える第１のモジュール１０１へのプライベートインターフェイスを有する。したがって、事前計算モジュール１０２および画像合成モジュールは、統合パブリックＡＰＩ １０６を備える第１のモジュール１０１を介して制御される。

したがって、画像合成フレームワーク１０８は、モジュール１０１、１０２、１０３の結果としてモジュラーアーキテクチャを備え、それにより処理モジュールのさまざまなインスタンスが実行時にロードされて構成されるようにすることができる。画像合成フレームワークは、１つまたは複数の画像１００が入力として機能し、単一の合成された画像１０４が出力である、データ処理パイプラインを提供する。パイプラインの制御は、パブリックＡＰＩ １０６への呼び出しを通じて達成される。

第１のモジュール１０１および統合ＡＰＩ １０６は、事前計算モジュール１０２および画像合成モジュール１０３のような、プラグインモジュールをロード、構成、および実行するための機能を提供する。第１のモジュール１０１はまた、入力画像１００をロードおよびアンロードして、それらの関連データ構造を作成するための機能も提供する。このモジュールは、入力画像１００をランク付けして、さらに１つまたは複数の入力画像の関心領域（ＲｏＩ）を計算するように配置される。加えて、このモジュールは、出力画像１０４を保存する機能を提供する。

事前計算モジュール１０２は、顕在性および顔検出などの因子に基づいて入力画像１００の事前情報を計算する機能を提供する。これは、以下でさらに詳細に説明される。

画像合成モジュール１０３は、入力画像および事前計算の結果からデジタルコラージュを形成する機能を提供する。これは、任意の適切な方法で達成される。

ソフトウェアアプリケーション１０５は、画像合成フレームワーク１０８によって実行されるプロセスを制御および／または表示するユーザインターフェイス１０７を提供することができる。このユーザインターフェイスおよびソフトウェアアプリケーション１０５は、任意の適切なプログラミング言語を使用して任意の適切な方法で提供され、パブリックＡＰＩ １０６を使用して画像合成フレームワークに接続する。

ここで、画像合成フレームワーク１０８を経由するデータの流れの例は、図２を参照して説明される。情報の流れは、フレームワーク１０８に供給される画像１００のコレクション（ボックス２００）から始まる。各入力画像１００は、たとえば、あらかじめ定められた寸法に適合して、入力画像１００全体にわたり著しく変化することがないように縮小されることにより、正規化される（ボックス２０１）。たとえば、入力画像は、２４ビットのビットマップ画像として表され、それが一時ファイルとしてディスクに格納される。しかし、これは必須ではなく、入力画像の任意の適切な表現フォーマットが使用されてもよい。正規化された入力画像は、任意の適切な方法でランク付けされる（ボックス２０２）。画像ランク付けの方法の例は、以下でさらに詳細に説明される。

入力画像を正規化することにより、必要とされる処理時間は、合成画像の生成の段階の一部または全部にわたり短縮される。たとえば、画像ランク付け、関心領域の計算、事前計算モジュール処理、および画像合成モジュール処理に必要な処理は、処理されるべきデータの量を減らすための画像正規化を使用することにより、軽減される。したがって、正規化中に入力画像の寸法を可能な限り減少させることは有益である。次いで、結果として得られた合成画像は、ユーザが指定した寸法まで拡大することができる。しかし、入力画像の正規化を提供することは必須ではない。

次いで、最初のｎ個の正規化画像のような、ランク付けされ正規化された画像のサブセットは、事前計算モジュールを使用するステップを備える次の段階に供給される（ボックス２０３）。次いで、画像合成フレームワークのこのインスタンス化において使用するために選択されたそれらの事前計算モジュールは、正規化された画像のサブセットに実行される（ボックス２０３）。各事前計算モジュールは、画像内の顔に関する情報または顕在性マップなど、画像からの指定された種類の情報を抽出する。この抽出された情報は、オプションで関連する正規化された画像と同じ寸法を有する行列として表すことができる。この行列表現のような汎用表現を使用することにより、事前計算モジュールおよび画像合成モジュールをプラグ可能にすることができる、つまり、容易に交換、除去、および／または元に戻すことができるようになる。

次いで、１つまたは複数の正規化された入力画像について関心領域が計算される（ボックス２０４）。この関心領域計算プロセスは、必要に応じて、画像合成モジュールによって内部的に呼び出すことができる。この関心領域計算プロセスは、１つまたは複数の事前計算モジュールの結果を使用することができる。

事前計算モジュールの結果および正規化された画像のサブセットは、デジタルコラージュを形成する画像合成モジュールに供給される（ボックス２０５）。次いで、そのデジタルコラージュは格納される（ボックス２０６）。画像合成モジュール１０３は、事前計算モジュールによって計算された行列表現および正規化された画像自体を入力として取る。たとえば、このモジュールは、事前計算モジュールに供給されたものと同じ正規化された画像で作業を進める。このモジュールはまた、それらの画像が正規化される前に１つまたは複数の入力画像を入力として取ることもできる。これらの元の入力画像は、合成された画像をユーザが指定した寸法まで拡大するときに使用することができる。このモジュールはまた、プラグ可能であることが好ましい。このモジュールは常に、複数の正規化された画像およびそれらの関連する事前行列（またはその他の事前計算モジュールの出力）を入力として予期する。このモジュールは、単一の画像を出力として生成する。たとえば、出力画像は、正規化された入力画像およびそれらの事前行列を処理し、事前行列のユーザ定義可能な重み付け組み合わせに応じて画像の部分を取り、それを出力画像内の特定の場所に配置することによって生成される。次いで、出力画像は事後処理され、オプションでユーザが指定した寸法まで拡大することができる。

図３Ａは、正規化された入力画像３００の概略図を示し、図３Ｂは、関心領域３０１が検出された状態のこの同じ正規化された入力画像を示す。この関心領域は、以下でさらに詳細に説明されるように、任意の適切な方法で検出される。図３Ｃは、図３Ａの正規化された入力画像から得られた事前行列３０４の概略図である。事前行列が顔検出プロセスの結果を格納するために使用されると仮定する。この事前行列は入力画像と同じ寸法を有し（ただし、それは必須ではない）、関心領域３０２に対応する位置における行列内の値は、顔が検出される画像要素に関連するので、同じ指定された値（たとえば、１など）が与えられる。その他の位置３０３における行列内の値は、これとは異なる同一の指定された値（たとえば、０など）を与えられる。

各事前行列は、画像ブロックの２Ｄ配列を備え、画像ブロックは単一ピクセルまたは３２×３２ピクセルもしくは別のサイズのようなピクセルのグループである。事前計算モジュールは、そのような行列に入力画像に関する情報を取り込む。たとえば、画像内の顔を識別する事前計算モジュールは、顔が見い出される位置における行列内の高い潜在的値、および他の場所の低い値にマークを付けることができる。

１つの例において、事前計算モジュールは、潜在的行列を潜在的値のガウス分布で満たすように配置される。次いで、このモジュールは、その位置に従って画像内の情報に区別をつけて重み付けするために使用することができる。たとえば、画像内の最も重要な情報が中央に向かって含まれている場合、この事前計算モジュールは、それに応じて画像情報に重み付けすることができる。

もう１つの例において、事前計算モジュールは、潜在的行列を、入力画像の対応する領域から計算されたコントラスト値で満たすように配置される。

もう１つの例において、事前計算モジュールは、入力画像内の１つまたは複数の顔を識別して、潜在的行列内の対応する値にマークを付ける。

事前計算モジュールの各々の結果について同じ行列表現を使用することにより、事前計算モジュールのさまざまな組み合わせを交換および／または使用することが可能になる。加えて、各事前計算モジュールの結果に与えられた重みは、区別をつけて迅速かつ容易に調整することができる。たとえば、１つの実施形態において、図１のソフトウェアアプリケーション１０５は、チェックボックスおよびスライダのグラフィカル表示を提供するユーザインターフェイス１０７をもたらすように配置される。チェックボックスは、使用される事前計算モジュールの選択を可能にするように配置され、スライダは、画像合成プロセスにおいてそれらの選択された事前計算モジュールの結果に与えられる相対的重みを設定するように配置される。このようにして、ユーザ制御は、選択された事前計算モジュールおよび選択された相対的重みに応じてさまざまな結果を得るように与えられる。任意の適切なユーザインターフェイス項目は、チェックボックスおよびスライダの代わりに使用することができる。

１つの例において、画像合成フレームワークは、オブジェクト指向プログラミング言語を使用して提供されるが、これは必須ではない。ここで、オブジェクト指向プログラミング言語を使用して提供される画像合成フレームワークの例を使用する方法は、図４を参照して説明される。（入力画像１００である）外部画像ファイルがロードされる。結果として得られた画像は、画像オブジェクトとして返される（ボックス４００）。

各入力画像について、ルート画像オブジェクトが作成され（ボックス４０１）、初期化される。このプロセスの一環として、画像の正規化されたバージョンが生成され（ボックス４０２）、潜在的行列のベクトルが作成され（ボックス４０３）、初期化される（行列のベクトルのサイズは、使用される事前計算モジュールの数と等しくすることができる）。次いで、ルート画像オブジェクトが、任意の適切な方法でランク付けされる（ボックス４０１）。たとえば、それらは指定された品質（単項）および相違（２項）メトリクスに従ってランク付けされ、このランク付けに従って順序付けられる。次いで、最初のＮ個のランク付けされたルート画像オブジェクトは、事前計算モジュールの各々に渡される（ボックス４０５）。事前計算モジュールは、ルート画像オブジェクト内に格納されている正規化された画像に必要な計算を行う。結果として得られたデータは、潜在的行列オブジェクトに格納されるが、これもまたルート画像オブジェクト内に含むことができる（ボックス４０６）。次いで、ルート画像オブジェクトは、最終合成出力画像を生成する画像合成モジュールに渡される（ボックス４０７）。

前述のように、画像合成フレームワーク（ＩＳＦ）はパブリックＡＰＩを備える。言い換えれば、ＩＳＦは、画像合成プロセスを制御するためにソフトウェアアプリケーションまたはその他のエンティティによって使用されうるパブリックＡＰＩ関数のセットを公開する。ここで、このパブリックＡＰＩに適切な関数の例が示される。これらは例示としてのみ示されるものであり、類似した関数のその他の組み合わせもまた使用することができる。

図５は、ＩＳＦのインスタンス化を初期化および構成する方法を示す流れ図である。ＩＳＦの新規インスタンスは、ＩＳＦＩｎｉｔを呼び出すことによって初期化することができる（ボックス５０１）。成功すると、この関数は、ＩＳＦの現在のインスタンスにハンドルを返す（ボックス５０２）。次いで、このハンドルは、すべてのその他のＩＳＦ ＡＰＩ関数に第１のパラメータとして渡すことができる。ＩＳＦＩｎｉｔは、呼び出されるたびに一意のハンドルを返し、それによりＩＳＦの複数のインスタンスがインスタンス化されるようにすることができる。ＩＳＦのインスタンスが必要とされなくなったときに、ＩＳＦＤｅＩｎｉｔへの呼び出しを行うことができ、この関数が任意の割り振られているリソースを解放する。

ＩＳＦは、複数の方法で構成することができる（ボックス５０３）。構成は、どの事前計算および画像合成モジュールをロードするかをＩＳＦに指示するステップを備える。構成は、以下の方法のいずれかを個々に、または組み合わせて使用して達成することができる。
ＩＳＦＬｏａｄＣｏｎｆｉｇＦｉｌｅを呼び出して、どのプラグインモジュールをロードするかを指定する構成ファイルをＩＳＦにロードさせる（ボックス５０４）
ＩＳＦＬｏａｄＭｏｄｕｌｅＦｏｌｄｅｒを呼び出すことにより、指定されたフォルダ内にあるすべてのモジュールをＩＳＦにロードさせる（ボックス５０５）
ＩＳＦＬｏａｄＭｏｄｕｌｅの呼び出しを通じて個別にモジュールをＩＳＦにロードさせる（ボックス５０６）

この段階において、ＩＳＦＧｅｔＰｒｉｏｒＩｎｆｏのオプションの呼び出しを行うことができる（ボックス５０７）。これは、個々の事前計算モジュールを使用可能または使用不可にして、事前計算結果に与えられる重みを制御するために使用することができる構造体へのポインタのベクトルを返す。モジュール情報が確実に解放されるように、ＩＳＦＧｅｔＰｒｉｏｒＩｎｆｏの呼び出しは、ＩＳＦＦｒｅｅＰｒｉｏｒＩｎｆｏの呼び出しと適合させることができる。

使用される画像正規化の方法は、たとえばＩＳＦＳｅｔＮｏｒｍａｌｉｚａｔｉｏｎＩｎｆｏを使用して指定される（ボックス５０８）。

図６は、入力画像をロードして画像ランク付けを実行する方法を示す流れ図である。ＩＳＦが初期化され構成されると、ＩＳＦに指定された画像をロードさせるＩＳＦＬｏａｄＩｍａｇｅの呼び出しを行うことができる（ボックス６００）。この関数は、入力画像のセットがロードされるようにするため、複数回呼び出すことができる。画像は、ＩＳＦＵｎｌｏａｄＡｌｌＩｍａｇｅｓまたはＩＳＦＵｎｌｏａｄＩｍａｇｅを呼び出して、すべての画像または特定の画像だけをアンロードすることにより、フレームワークがビジー処理中ではない間の任意の時点においてアンロードすることができる。

必要に応じて、コールバック機能をセットアップすることができる（ボックス６０１）。たとえば、ＩＳＦＳｅｔＰｒｉｏｒＳｔａｔｕｓＣａｌｌｂａｃｋ、ＩＳＦＳｅｔＲａｎｋｉｎｇＳｔａｔｕｓＣａｌｌｂａｃｋ、およびＩＳＦＳｅｔＳｙｎｔｈＳｔａｔｕｓＣａｌｌｂａｃｋの呼び出しを行うことができる。これは、ランク付け、事前計算、および画像合成処理の段階の間に呼び出されるコールバック機能をインストールする。コールバック機能は、処理操作に関する進行状態情報を受信し、たとえばユーザに進行状態情報を表示するために使用することができる。進行状態情報は、任意の適切な種類のものである。たとえば、進行状態情報は、０から１００までの数字を備え、１００は特定の段階が処理を終了したことを知らせる働きをする。

画像ランク付けは、次に、たとえば、ＩＳＦＲｕｎＩｍａｇｅＲａｎｋｉｎｇの呼び出しを行うことによって実行される（ボックス６０２）。結果には、ＩＳＦＧｅｔＲａｎｋｉｎｇＲｅｓｕｌｔｓを呼び出すことによってクエリを行うことができ（６０３）、その後のＩＳＦＦｒｅｅＲａｎｋｉｎｇＲｅｓｕｌｔｓの呼び出しは、結果が必要とされなくなったときに行うことができる。ユーザは、ＩＳＦＭｏｖｅＩｍａｇｅＴｏＲａｎｋを呼び出すことによって指定されたランクに画像を移動することができる（ボックス６０４）。ランク付けプロセスは、図６に示されるように、オプションで一時停止および再開することができる。

図７は、事前計算モジュールを実行して画像を合成する方法を示す流れ図である。ロードされた事前計算モジュールは、たとえば、ＩＳＦＲｕｎＰｒｉｏｒＣｏｍｐｕｔｅｓの呼び出しを行うことにより実行され（ボックス７００）、このプロセスは一時停止（ボックス７０２）および再開（ボックス７０１）することができる。入力画像のいずれかの事前結果は、ＩＳＦＧｅｔＰｒｉｏｒＲｅｓｕｌｔｓの呼び出しを通じて取得することができる（ボックス７０３）。これらの結果が必要とされなくなったときに、ＩＳＦＦｒｅｅＰｒｉｏｒＲｅｓｕｌｔｓの呼び出しを行うことができる。事前計算結果が取得されると、画像合成モジュールは、たとえば、ＩＳＦＲｕｎＳｙｎｔｈＩｍａｇｅの呼び出しを行うことによって実行することができる（ボックス７０４）。合成プロセスは、一時停止（ボックス７０６）および再開（ボックス７０５）することができる。合成された画像は、たとえばＩＳＦＳａｖｅＳｙｎｔｈＩｍａｇｅを呼び出すことによって保存することができる（ボックス７０７）。画像は、ＩＳＦＧｅｔＳｙｎｔｈＩｍａｇｅの呼び出しを介してＢＩＴＭＡＰＩＮＦＯＨＥＡＤＥＲおよび画像データへのポインタとしてメモリ内に返すことができる。

ＩＳＦの各インスタンスは、一部の例において、内部状態変数を保持する。現在の状態に応じて、一部のＡＰＩ関数はエラーコードを返すことができる。これは、現在の状態が、行われている特定の関数呼び出しを禁止することを指示する。たとえば、入力画像のロードが行われる前にすべてのモジュールが確実にロードされることが要求される。ＩＳＦＧｅｔＳｔａｔｅの呼び出しは、現在の状態を決定するためにいかなる時点においても行うことができる。

図８は、１つの実施形態におけるＩＳＦのさまざまな状態を示す例示の状態遷移図である。これらの状態の異なるものは、さまざまな組み合わせで使用することができ、状態は異なる順序で使用することができる。また、すべての割り振られているリソースのクリーンアップを強制して、状態を強制的にＩＳＦ＿ＵＮＩＮＩＴＩＡＬＩＺＥＤに戻すために、ほとんどの状態からＩＳＦＤｅＩｎｉｔを呼び出すことが可能である。任意の許容状態におけるＩＳＦＬｏａｄＩｍａｇｅの呼び出しは、その状態をＩＳＦ＿ＬＯＡＤＩＭＡＧＥにリセットするように手配される。この状況において、新しい画像はまだ、ランク、関心領域、または事前計算モジュール結果など、計算されたデータをまだ何も有してはいない。状態をＩＳＦ＿ＬＯＡＤＩＭＡＧＥにリセットすることで、そのようなデータが計算されるようになる。また、一部の実施形態において、事前計算モジュールの結果はキャッシュに入れられて、可能であれば処理時間を短縮するために再使用される。

ＩＳＦがまだ初期化されていない状態から開始し（ボックス８００）、ＩＳＦは初期化され（ボックス８０１）、次いで事前計算モジュールおよび画像合成モジュールがロードされた状態に移行することができる（ボックス８０２）。次の状態は、入力画像がロードされたときに生じ（ボックス８０３）、これに続いて状態は、ランク付けプロセスが実行し（ボックス８０４）、次いで完了する（ボックス８０６）ものであってもよい。ランク付けプロセスは、一時停止状態（ボックス８０５）にすることができる。事前計算モジュールが実行しているとき、状態はボックス８０７に示され、このプロセスは一時停止することができる（ボックス８０８）。事前計算モジュールが完了すると、状態はボックス８０９に示される。次に、画像合成プロセスが生じ（ボックス８１０）、次いで完了する（ボックス８１２）。画像合成プロセスもまた、一時停止することができる（ボックス８１１）。

図９は、ＩＳＦ９０４を提供する装置９００の概略図である。装置は、入力画像を受信するように配置された画像入力９０３を有する。この入力は、ネットワーク接続、ＵＳＢ接続、ディスクドライブ、ユーザインターフェイス、またはその他の入力など、任意の適切な種類のものである。装置は、コンピュータ、または任意の他の適切な種類のプロセッサとして提供されうるプロセッサ９０５を備える。オペレーティングシステム９０６は、プロセッサおよび装置９００を制御するために提供され、メモリ９０７が存在する。画像合成フレームワーク９０４は、ソフトウェアとして、または任意の他の適切な形態で提供され、オペレーティングシステム９０６を使用して任意の適切な種類のソフトウェアアプリケーション９０２の制御の下にプロセッサ９０５で実行することができる。ソフトウェアアプリケーション９０２はオプションで、グラフィカルユーザインターフェイスまたはその他の種類のユーザインターフェイスなどの、ユーザインターフェイス９０１に接続する。

一部の実施形態において、事前計算モジュールおよび画像合成モジュールへのロードおよび接続を簡略化するため、ラッパークラスが使用される。たとえば、これらのクラスは、たとえば、ｄｌｌモジュールのロードおよびアンロードをサポートし、エクスポートされたｄｌｌ機能のプロシージャアドレスの取得を全体的にサポートするＣＰｌｕｇＩｎＷｒａｐｐｅｒクラスと呼ばれるカスタムラッパークラスから派生することができる。１つの例において、さらに派生したクラスＣＰｒｉｏｒＣｏｍｐｕｔｅＷｒａｐｐｅｒおよびＣＩｍａｇｅＳｙｎｔｈＷｒａｐｐｅｒは、エクスポートされたｄｌｌ機能にアクセスするために特定のメンバ関数を提供する。ラッパークラスは、画像合成フレームワーク、画像合成モジュール、および事前計算モジュールのクライアント側呼び出しのいずれかを囲むようにオブジェクト指向のラッパーを提供する。

たとえば、ＩＳＦの各インスタンスは、複数のＣＰｒｉｏｒＣｏｍｐｕｔｅＷｒａｐｐｅｒオブジェクト（ロードされている事前計算モジュールごとに１つ）、および単一のＣＩｍａｇｅＳｙｎｔｈＷｒａｐｐｅｒオブジェクトのベクトルを保持する。ＩＳＦの各インスタンスはまた、ＩＳＦＬｏａｄＩｍａｇｅまたはＩＳＦＬｏａｄＩｍａｇｅＦｏｌｄｅｒが呼び出されるときに作成されるルート画像オブジェクトのベクトルを保持することもできる。１つの例において、ルート画像オブジェクトは、呼び出されたＣＲｏｏｔＩｍａｇｅオブジェクトであり、これはルート画像オブジェクトのオブジェクト指向ｃ＋＋実施である。

事前計算モジュールは各々、ＩＳＦへの共通プライベートＡＰＩインターフェイスを実施する。たとえば、事前計算モジュールの基礎をなすコードは、ＣＰＣＭａｉｎクラス内に含まれる。各事前計算モジュールは、ＣＰＣＭａｉｎオブジェクトのベクトルを保持する。それにより、ＩＳＦの異なるインスタンスが、事前計算モジュールの異なる一意のインスタンスを使用することができるようになる。このようにして、各事前計算モジュールによって保持される状態情報は、各インスタンスに一意である事前情報構造体に格納することができる。さまざまな事前計算モジュールの各々は、関連するＧＵＩＤ値を有する。ＰＣＣｏｍｐｕｔｅ関数は、このＧＵＩＤ値をルート画像オブジェクトに格納することができる。それにより、画像合成モジュールは、どの事前計算モジュールによってどの潜在的行列が作成されたかを後に判別することができるようになる。

１つの例において、事前計算モジュールのプライベートＡＰＩによって提供される関数は、以下のものを備える。

ＰＣＩｎｉｔ−事前計算モジュールの新規インスタンスを初期化してハンドルを返す初期化関数

ＰＣＤｅＩｎｉｔ−事前計算モジュールを消去し、クリーンアップして、任意の割り振られているリソースを解放する

ＰＣＧｅｔＰｒｉｏｒＩｎｆｏ−現在のモジュール情報を取得するために使用される

ＰＣＦｒｅｅＰｒｉｏｒＩｎｆｏ−ＰＣＧｅｔＰｒｉｏｒＩｎｆｏ関数によって返された情報を解放するために使用される

ＰＣＳｅｔＰｒｉｏｒＩｎｆｏ−モジュール情報を設定するために使用される。たとえば、これはモジュールの使用可能化／使用不可化および加重係数の設定を含む

ＰＣＣｏｍｐｕｔｅ−これは事前計算プロセスを実行し、結果をＣＲｏｏｔＩｍａｇｅオブジェクトに保存する

画像合成モジュールは、ＩＳＦへの共通プライベートＡＰＩインターフェイスを実施する。たとえば、これは以下の関数を備える。

ＩＳＩｎｉｔ−新規画像合成モジュールのインスタンスを初期化する

ＩＳＤｅＩｎｉｔ−画像合成モジュールを消去する

ＩＳＧｅｔＳｙｎｔｈＩｎｆｏ−現在のモジュール情報を取得する

ＩＳＦｒｅｅＳｙｎｔｈＩｎｆｏ−ＩＳＧｅｔＳｙｎｔｈＩｎｆｏ関数によって返された情報を解放する

ＩＳＳｅｔＳｙｎｔｈＩｎｆｏ−指定された情報を設定する

ＩＳＳｅｔＳｔａｔｕｓＣａｌｌｂａｃｋ−コールバック機能を設定する

ＩＳＰａｕｓｅ−現在の処理操作を一時停止する

ＩＳＲｅｓｕｍｅ−ＩＳＰａｕｓｅの呼び出しの後、現在の処理操作を再開する

ＩＳＳｔｏｐ−現在の処理操作を終了する

ｌＳＳａｖｅＳｙｎｔｈＩｍａｇｅ−合成された画像を指定したファイルに保存する

ＩＳＧｅｔＳｙｎｔｈＩｍａｇｅ−合成された画像のコピーを検索する

ＩＳＦｒｅｅＳｙｎｔｈＩｍａｇｅ−ＩＳＧｅｔＳｙｎｔｈＩｍａｇｅによって返された画像データを解放する

ｌＳＳｙｎｔｈ−合成プロセスを実行する

ＩＳＳｅｔＩＳＦＳｔａｔｅＣａｌｌｂａｃｋ−ＩＳＦコールバック機能を設定するために使用される

特定の例において、関心領域の計算、画像ランク付け、事前計算モジュールの一部、および画像合成プロセスは、２００６年１０月２４日に出願された我々の以前の特許文献１において説明されている。ここで、さらにその詳細について説明される。自動的にコラージュを形成するプロセスは、ラベル付けの問題として特徴付けられる。コラージュのラベルは、それらのコラージュ領域を形成するために入力画像のどの領域が使用されるかを指定する。各々さまざまな潜在的コラージュに対応する可能なラベル付けには膨大な数がある。我々のタスクは、結果として得られるコラージュが、入力画像の楽しく参考になる良質なサマリとなるように、指定する基準に関して最適なラベル付けを見いだすことである。使用されうるラベル付けシステムの例についてのさらなる詳細は、以下に示される。

エネルギー関数は、システムが良質なコラージュを生成するために指定されたさまざまな基準を考慮することができるように、調整または設計されるさまざまな条件を含むラベル付けのエネルギーに対して作成される。エネルギー関数についてのさらなる詳細は、以下に示される。エネルギー関数は、エネルギー関数作成の一環として指定されるさまざまなパラメータまたは重みを有する。パラメータまたは重みは、さまざまな基準が考慮される度合いに影響を及ぼす。オプションで、入力画像のオブジェクト認識結果は１つまたは複数の事前計算モジュールから取得され、この情報は、エネルギー関数自体においてパラメータの一部として、またはオプションの制約指定プロセス中に使用される。エネルギー関数への１つまたは複数の制約が指定されるが、制約はたとえば、計算の複雑さを軽減することができるか、またはより優れたコラージュが生成されるように動作することができる。制約の例についてのさらなる詳細は、以下に示される。

最適化プロセスは、任意の指定されている制約を考慮して、エネルギー関数に対して実行される。任意の適切な最適化プロセスを使用することができ、例が以下に示される。最適化プロセスは、可能なラベル付けであるエネルギー関数の最大または最小（あるいは極大または極小）を見いだす。可能なラベル付けは各々、コラージュに対応する。１つまたは複数のこれらのコラージュは、格納されるかまたは表示される。
ラベル付け

ここで、問題を指定するプロセスについてのさらなる詳細が示される。ＡｕｔｏＣｏｌｌａｇｅへの入力は、入力画像の集合Ｉ＝｛Ｉ_n，．．．，Ｉ_N｝である。入力を標準化するため、各画像Ｉ_nが個々の画像の縦横比を保持しながら単位面積を有するよう拡大縮小されるように、前処理ステップが適用されたものと想定される。前述のように、コラージュの作成は、ラベル付けの問題と見なされ、以下の表記を使用して説明される。コラージュ自体は、領域Ｐにわたって定義される画像Ｉであり、コラージュの各ピクセル−位置ｐ∈Ｐは、アルゴリズムによってラベルＬ（ｐ）を割り当てられるものとする。ラベル付けＬ＝｛Ｌ（ｐ），ｐ∈Ｐ｝は、以下のようにコラージュを完全に指定する。個々のラベルは形式Ｌ（ｐ）＝（ｎ，ｓ）を有し、ここでＩ_n∈Ｉはコラージュピクセルｐの取り出される入力画像であり、ｓ∈Ｓはコラージュに関して入力画像ｎのピクセル単位の２Ｄシフトであり、Ｉ（ｐ）＝Ｉ_n（ｐ−ｓ）となる。これは、簡潔にＩ（ｐ）＝Ｓ（ｐ，Ｌ（ｐ））と表記されるが、ここでＳ（．．．）はＳ（ｐ，（ｎ，ｓ））＝Ｉ_n（ｐ−ｓ）によって定義され、Ｓ（．．．）∈［０，１］ｘ［０，１］ｘ［０，１］と正規化される。

方法は、可能なラベル付けの空間Ｌにおいて、最善のラベル付けＬ∈Ｌを見い出そうと努める。これは、エネルギーまたはコストＥ（Ｌ）を最小化するラベル付けＬを見い出すこととして表現され、以下に詳細に定義される。許容されるラベル付けの空間を効率的に検索して、低エネルギーのラベル付けを取得する最適化手順が定義されるが、ここでアルゴリズムが近似であるので、エネルギーは必ずしも大域最小である必要はない。すべての入力画像が事前に調整された他者による以前の作業において、比較すると、各ピクセルラベルは、シフト変数ｓを伴うことなく、画像索引のみで構成されていたことに留意されたい。本発明の場合、各ピクセルにおける画像索引ｎ＝１，．．．，Ｎだけではなく、許容されるシフトｓにわたっても検索する必要があるので、最適化の問題はさらに複雑である。

コラージュのエネルギー
ここで、ラベル付けＬのエネルギー関数を作成するプロセスは、図１０を参照してさらに詳細に説明される。これは、各々が最善のラベル付け（またはコラージュ）を生成するために必要とされる基準または特性を指定するように設計または調整される１つまたは複数のエネルギー項を合計することを備える。

特定の例において、エネルギー関数は、以下に示されるように４つの項を備える。しかし、これは必須ではない。さらに、これらの項のうちのいずれか１つまたは複数を使用するか、または必要に応じて他のエネルギー項を使用することも可能である。

ラベル付けＬのエネルギーは、以下に示すように４つの項を備える。
Ｅ（Ｌ）＝Ｅ_rep（Ｌ）＋ｗ_impＥ_imp（Ｌ）＋ｗ_transＥ_trans（Ｌ）＋ｗ_objＥ_obj（Ｌ） （１）
第１の項Ｅ_repは、第１に選択される画像がテクスチャ的に「興味深い」こと、および第２にそれらが相互に異なっていること、という２つの意味において最も典型的である入力画像セットから画像を選択する傾向がある。たとえば、これは、近接する複製が選択されないという効果を及ぼすことができる。Ｅ_impの項は、相当量の興味深い関心領域（ＲＯＩ）がＩ内の各画像から確実に選択されるようにする。次に、Ｅ_transは、視覚的に魅力的ではない画像間の任意の移行にペナルティを課すペアワイズの項である。最後に、Ｅ_objは、オブジェクト認識に関する情報を取り込み、（我々の実施形態における、全体が保持される顔、最上部の空）妥当な構成におけるオブジェクトの配置に有利にはたらく。以下で、これらのエネルギー項の各々が、保持されるべき制約と共に詳細に定義される。

ここで、エネルギー項Ｅ_repの例が示される。

第１の可能なエネルギー項は、使用可能にされた入力画像のコレクションから１つまたは複数の入力画像を選択するように機能する（ボックス３０００、図１０）。たとえば入力画像のうち最も興味深いものだけが選択され、たとえば空白またはわずかな詳細しか含まないものは選択されない。加えて、目立つ画像がオプションで選択される。

たとえば、使用可能な入力画像のセットから最も典型的で目立つ画像を選択するように機能するエネルギー項が提供される（図１０の３０００）。たとえば、すべての使用可能な入力画像から、最もテクスチャ的に参考となる入力画像が選択される。画像は、画像内の情報量の測度に基づいて選択することができる。オプションで選択は、画像が、顔、人物、建物、自動車、またはオブジェクト認識システムによって提供される情報を使用するその他の指定されたオブジェクトのクラスなど、特定のオブジェクトのクラスの画像を含むかどうかについての情報に基づくことができる。

非常に似通っている画像を拒否するために、システムは、色ヒストグラム、相関標識、または任意のその他の適切な測度など、画像の類似性の任意の適切な標識を使用することができる。このようにして、コラージュ内の素材の重複を減少させる。

特定の例において、選択された画像の集合Ｉに関連付けられているコストは、Ｅ_rep＝Σ_nＥ_rep（ｎ）の形であり、ここで

およびａ_nは補助の標識変数であり、コラージュに画像Ｉ_nが存在する場合１をとり、それ以外の場合は０をとり、

単項Ｄ_r（ｎ）は、画像ｎ内の情報の測度である。情報の測度は以下の式によって定義され、
Ｄ_r（ｎ）＋Ｅｎｔｒｏｐｙ（Ｉ_n）＋ｗ_faceδ（｛画像ｎが顔を含む｝） (3)
ここで、述部πが真である場合δ（π）＝１であり、ｗ_faceは、画像内の一般テクスチャ情報に相関して、顔を含む画像の影響を重み付けする。所定の画像のエントロピーを計算するために使用されるヒストグラムは、Ｌ，ａ，ｂ表色系から二次元ａ，ｂ空間に構築され、１６×１６ビンに離散化される。

（２）における第２の項は、画像間のペアワイズの距離ａ，ｂに関して表され、集合Ｉ内の各画像からその最近傍までの距離を合計する。使用している距離測度Ｖ_r∈［０，１］として、正規化カイ二乗距離が１組の画像の色ヒストグラム間で使用されてもよい。ヒストグラムは、上記のように、ａ，ｂ空間内で構築される。最も典型的な画像に有利にはたらくことに加えて、このエネルギーは、可能な限り多くの画像の使用を促進する。

相当量の興味深い関心領域がＩ内の各画像から確実に選択されるように機能するもう１つの可能なエネルギー項を提供することができる（ボックス３１００）。たとえば、このエネルギー項は、入力画像のピクセルの周囲の指定された領域の局所エントロピー測度を考慮する。この局所エントロピー測度は、画像領域の顕在性の可能な標識の例である。その他の顕在性標識が、その代わりに使用されてもよい（たとえば、非特許文献１の顕在性モデルを参照）。オプションで、このエネルギー項は、入力画像の中心が関心領域に対して有利になるように重み付けされる。しかし、これは必須ではない。このエネルギー項を使用することにより、微少な視覚的に無意味な画像フラグメントがコラージュ内に発生する尤度を減少させることが可能である。

重要コストエネルギー項とも呼ばれる、この「関心領域」エネルギー項は、ここで特定の例について詳細に説明される。重要コストは以下の形の単項で構成される。

関数Ｅ_imp（ｐ，Ｌ（ｐ））＝Ｇ（ｐ，Ｌ（ｐ））Ｔ（ｐ，Ｌ（ｐ））、ここでＴ（ｐ，Ｌ（ｐ））はピクセルｐ周囲の（３２×３２ピクセル）領域のａｂ座標における局所エントロピーを測定し、局所エントロピーの合計が所定の入力画像にわたり１になるように正規化される。ガウス重み関数Ｇ（．．．）は、ｐが描かれる入力画像の中心に有利にはたらく。

もう１つの可能なエネルギー項は、２つの入力画像の間の境界にわたる不一致の測度に基づいて画像間の移行にペナルティを課す（ボックス３２００）。たとえば、このエネルギー項はまた、いずれかの入力画像の高コントラスト境界で移行を促進するように調整される。特定の例において、そのようなエネルギー項は、移行コストとも呼ばれ、以下で詳細に説明される。

例示の移行コストは、Ｅ_trans＝Σ_p,q∈NＶ_T（ｐ，ｑ，Ｌ（ｐ），Ｌ（ｑ））の形をとり、ここでＮは近隣の（８近傍）ピクセルのすべての組の集合である。項Ｖを以下のように定義する。

ここで、輝度関数Ｓ（．．．）は上記で定義されたとおりであり、ε＝０．００１は下位桁あふれを防ぎ、‖・‖はユークリッドノルムを定義する。

合計で、Ｅ_transは、２つの入力画像間の境界にわたる不一致を測定する。このことを確認するため、最初に、L(p)≠L(q)の場合を除いてＶ_T（ｐ，ｑ，Ｌ（ｐ），Ｌ（ｑ））＝０であることを観察する。次いで、入力画像のうちの１つに強い勾配がある場合、関連する分母も大きくなるので、Ｖ_T（ｐ，ｑ，Ｌ（ｐ），Ｌ（ｑ））＝０は小さいことに留意されたい。この問題において隣接する画像が通常、一致しないことの多いかなり異なるシーンから取り出されるので、ｍｉｎ演算子が使用される。次いで、我々のエネルギーの選択は、境界にわたり良好な一致を促進する通常の効果に加えて、いずれのシーンにも高コントラスト境界で移行を促進する際に適切に機能する。

もう１つの可能なエネルギー項は、オブジェクト認識システム（たとえば、事前計算モジュール）からの情報が考慮されるようにすることができる（ボックス３３００、図１０）。たとえば、オブジェクトクラスは、入力画像に示された１つまたは複数のオブジェクトについて識別され、この情報はコラージュの作成に影響を及ぼすために使用される（ボックス３４００を参照）。１つの例において、顔が検出され、エネルギー項は、顔がコラージュに含まれている場合に、全体として顔が含まれる傾向になるように調整される。もう１つの例において、空領域が検出される場合、それらはコラージュの上部に向かってのみ含まれる傾向がある。

１つの特定の例において、Ｅ_obj＝Σ_p,q∈Nｆ（ｐ，ｑ，Ｌ（ｐ），Ｌ（ｑ））というエネルギー項を使用し、ここでＬ（ｐ）≠Ｌ（ｑ）でありｐ、ｑがＬ（ｐ）またはＬ（ｑ）の画像のいずれかの同じ顔からのピクセルである場合、常にｆ（ｐ，ｑ，Ｌ（ｐ），Ｌ（ｑ））＝∞であり、それ以外の場合は０である。明示的なエネルギーを定義することではなく、空の場合には、空を含む画像を単にラベル付けして、その情報を、そのような画像をコラージュの上部のみに配置しようと試みる制約満足化エンジンに渡す。

パラメータは、エネルギー関数について指定される。これらのパラメータは、手動で指定されるか、またはシステムの非公式テストと共に調整プロセスを使用することにより決定されてもよい。たとえば、１つの実施形態において、以下のパラメータ値が使用されるが、これらのパラメータ値は大幅に変更されることがあっても引き続き実行可能な結果をもたらすことに留意されたい。たとえば、ｗ_imp＝１０．０，ｗ_trans＝１．０，ｗ_obj＝１．０，ｗ_face＝０．０１とする。

エネルギー関数の最適化への制約は、オプションで指定される。このように制約を指定することにより、生成されるコラージュの品質を向上させることができ、また計算の複雑さを軽減することもできる。

第１の制約は、関心領域が取り出される画像全体と相対的な関心領域内に含まれる情報の量に関連する。たとえば、この制約は、入力画像の微少な認識不能なフラグメントのみが選択されてコラージュに使用される可能性を回避するために使用される。関心領域に含まれる（絶対または相対）情報量は、たとえば、指定されたしきい値を上回る必要がある。特定の例において、関心領域は、関連する入力画像情報の少なくとも９０％を取り込む必要がある。しかし、任意の適切なしきい値を使用することができる。

情報限定制約と呼ばれる、この第１の制約の特定の例において、ラベル付けに存在する、つまり一部のｓおよび一部のｐ∈ＰについてＬ（ｐ）＝（ｎ，ｓ）である任意の画像Ｉ_nは、
Ｅ_imp（Ｌ，ｎ）＞Ｔ （６）
を満たす必要があり、ここでＥ_imp（Ｌ，ｎ）∈［０．１］は、ＲＯＩに取り込まれる局所画像情報Σ_pＥ_imp（ｐ，Ｌ（ｐ））の割合である。１つの例において、Ｔ＝０．９、つまり画像情報の少なくとも９０％が取り込まれるようにする。

もう１つのオプションの制約は、本明細書において、一様シフト制約と呼ばれる。これは、所定の入力画像が、（コラージュに関して入力画像の）唯一の一意の２Ｄシフトでコラージュに現れることを指定する。たとえば、所定の入力画像Ｉ_nが唯一の一意のシフトｓでコラージュに表示される、つまりラベルＬ（ｐ）＝（ｎ，ｓ），Ｌ（ｑ）＝（ｎ，ｓ’）で２つの相異なるピクセルｐ，ｑ∈Ｐ：ｐ≠ｑを与えられ、ｓ＝ｓ’である必要がある。この制約は、部分的には計算の効率にとって有用であり、部分的には入力画像の構造が歪みをまねくことなく確実に保持されるという点において有用である。

もう１つのオプションの制約は、本明細書において、接続性制約と呼ばれる。これは、同一の入力画像から描かれるコラージュのピクセルは、好ましくは、ただし必須ではないが、合致すべきであるという相対位置基準を指定する。たとえば、画像ｎから描かれるコラージュピクセルの各集合Ｓ_n∈｛ｐ∈Ｐ：Ｌ（ｐ）＝（ｎ，ｓ），一部のｓについて｝は、４つの連結領域を形成する必要がある。これは、最適化中に促進される。

もう１つの制約は、コラージュ内のすべてのピクセルの全部または指定された部分がラベル付けされるというものである、つまり、ラベル付けされていないピクセルは視覚的に魅力的ではないコラージュの空白領域をもたらすので、これをあまり多く備えることは望ましくない。

最適化プロセスは、任意の指定されている制約を考慮して、エネルギー関数に実行される。１つの実施形態において、上記で参照された我々の以前の特許文献に説明されているように、単一段階グラフカット最適化プロセスが使用される。実施形態のもう１つのグループにおいて、ラベル付けのさまざまな態様が独立して、または（以下で詳細に説明されるように並行もしくは順次の）別個の最適化段階で最適化されるヒューリスティック手法が使用される。このような多段式の最適化プロセスを使用することにより、計算の複雑さに対処することができ、５０以上の入力画像のような、膨大な入力画像の集合に迅速かつ拡張可能なシステムを提供することができる。図１１は、１つの例による４つの最適化段階を示す。

入力画像は、どのくらい多くの情報を含み、近似の複製を拒否するかに基づいて、ランク付けプロセス４００中に静的にランク付けされる。これは、Ｅ_repエネルギー項とも呼ばれる、図１０のボックス３０００を参照して説明されているエネルギー項を使用して行われる。関心領域は、各入力画像について選択され（ボックス４１００）、指定された制約に従って最小化される。たとえば、関心領域は長方形（ここで長方形は正方形を含む）または任意のその他の指定された形状である。制約は、たとえば、前述の情報限定制約、およびすべての検出された顔が含まれるという要件であってもよい。明示的な関心領域選択プロセスを使用することによって、入力画像がテクスチャおよび情報内容に関して非常に異なっている場合でも、良好な品質のコラージュを生成することができる。入力画像をランク付けるステップおよび関心領域を選択するステップは、順次または並行して実行することができる。

次いで、パッキングの問題が解決され（ボックス４２００）、最高ランクの多くの画像を、関心領域を重複させることなく、コラージュに準備された領域に集めて配置する。また、コラージュ内のピクセルは空白のままにしておくことはできないが、この要件は必須ではない。次いで、最適化プロセス（ボックス４３００）は、２つ以上の画像の重複する領域内のコラージュのピクセル識別を修正するために使用される。以下に説明されるように、グラフカット最適化などの任意の適切な最適化プロセスを使用することができる。適切な最適化プロセスのその他の例は、信頼伝搬（ｂｅｌｉｅｆ ｐｒｏｐａｇａｔｉｏｎ）、シミュレーションアニーリング（ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ）、ＩＣＭ、およびＴＲＷを含むが、これらに限定されることはない。

ここで、これらの４つの最適化ステップは各々、特定の例を参照してさらに詳細に説明される。

イメージのランク付け。最適化のシーケンスにおいて、ランク付けステップは、コラージュエネルギー内のＥ_rep項に対応する（１）。最初に画像Ｉ_nは、部分集合Ｉ₁，．．．，Ｉ_nがどの程度典型的であるかに従って索引ｎがそれらをランク付けするように、再度ラベル付けが行われる。これは、Ｅ_rep（ｎ）が単にｎ番目の画像およびその上位ランクの先行の画像に関して独立して計算された静的ランクであるため、容易である。したがって、ｎ番目の画像は、

を最小化するものとして貪欲に選択され、項Ｅ_rep（ｎ）を適合させる（２）。次いで、結果として得られたランク付けは、以下の制約満足化ステップに渡される。

関心領域（ＲＯＩ）の最適化。各入力画像Ｉ_nのＲＯＩは、画像ごとに独立して、情報限定制約（６）、およびすべての検出された顔が含まれるという制約を満足することを前提として、ＲＯＩの領域を最小化することにより修正される。これは、任意の長方形ＲＯＩ Ｒ内の合計情報Σ_p∈RＥ_imp（ｐ，Ｌ（ｐ））の迅速なルックアップのために、合算領域テーブルを構築することによって達成される（たとえば、非特許文献２参照）。次いで、すべての長方形は列挙され、最小面積を持つ長方形を選択するために、制約の満足化が検査される。この操作は、Ｉ_n内のピクセルの数における二次であり、これは二段抽出により緩和される。これは、すべての顔が含まれるという制約の下で行われる。

制約の満足化。ここで、パッキングの下位の問題は、以下のように説明することができる。選択された画像の集合とそれらのＲＯＩを、上記で計算されたランク付けと共に与えられる。目標は、可能な限り多くの上位ランク付けされた画像をコラージュの幅および高さの中に取り込み、しかもあらゆるピクセルがいずれかの画像によって覆われる（ただし、いずれかのＲＯＩによって覆われる必要はない）という追加の制約を順守することである。

このパッキングの問題は、非重複、つまり２つのＲＯＩが交差してはならないという制約、および被覆、つまりすべてのピクセルが画像によって覆われる（ただし必ずしもＲＯＩによって覆われなくてもよい）という制約が同時に存在するので、特異なものである。一般的な手法は、変数の集合の間の制約のセット（不等式、論理式、および一次式）として問題をモデル化して、制約満足化技法を適用することにより、それらの制約を解決することである。ここで、制約を使用して問題をモデル化する１つの方法が説明される（いくつかの変形が代替として検討されうる）。この問題において、変数の集合は、

各画像の位置（ｘ_n、ｙ_n）、および画像が含まれるべきかどうかを指示するブールフラグｂ_nである。
ＲＯＩが交差しない（非重複）ことを表現するため、制約は画像にペアワイズで適用され、典型的な制約は、
ｉｆ ｂ_n ａｎｄ ｂ_m ｔｈｅｎ π₁ ｏｒ π₂，．．．，（ｂ_nかつｂ_mである場合、π₁またはπ₂である） （ｂ）
ここで、典型的な命題はπ₁＝（ｘ_n−ｘ_m＞ｗ_m＋ｗ_n）であり、ｗ_mおよびｗ_nはそれぞれＲＯＩの半値幅である。ＲＯＩの組の相対位置は交換されうるので、それらの制約は論理和集合に現れる。
コラージュのすべてのピクセルが少なくとも１つの画像の表面の下に含まれる（被覆）ことを表現するため、制約はすべてのピクセルに課せられ、典型的な制約は、
｜ｉ−ｘ_n｜≦Ｗ_n∧｜ｊ−ｙ_n｜≦Ｈ_n
ここで、Ｗ_nおよびＨ_nはそれぞれ画像ｎの半値幅であり半値高である。この制約は、ピクセル（ｉ，ｊ）がｎ番目の画像によって覆われることを課す。たとえば、そのような制約の論理和はすべてのピクセルについて課され、それらの各々が画像の（少なくとも）１つによって覆われるという要件をモデル化する。
さらなるオブジェクト依存の制約を含むことができ、たとえば、空を伴う画像がコラージュの上部のみに表示されるように要求することもできる。

制約のブール組み合わせを伴う問題は、制約プログラミング（ＣＰ）に基づく手法の影響を受けやすい。たとえば、効率的に良好な解決を得るために使用する二段階の手法が、ここで説明される。第１のステップ（分岐および限定）はＲＯＩの非重複の制約のみを考慮することにより問題を解決し、次いで第２のステップ（局所検索）が被覆の制約を順守するために解決を修正する。

１． 分岐および限定。第１の最適化ステップのフレームワークは、選択された画像の数およびそれらの品質を最大化することを目指す縦型検索である（式（２））。制約の伝搬（たとえば、非特許文献３参照）は、サブツリーに適用され、そこからサブツリーが枝取りされるか、またはその検索空間を縮小させる。実変数（ｘｎ，ｙｎ）は、制約の保守的な切り捨てでの粗い離散化により対処される。伝搬からのアクティブな制約の集合の切り替えの課題は、具象化（非特許文献４参照）により対処される。分岐および限定のステップにおいて、被覆の要件は全く考慮されない。この段階において、可能な限り多くの長方形をパッキングする問題は、ＲＯＩの重複に対する論理和の制約内で解決される。粗い離散化による場合であっても、ノードにおける分岐係数は大きい。これは、限定された数の探索する分岐を無作為に選択し、それらの各々について有界数の後戻りステップを許容することにより、対処される。

２． 局所検索。分岐および限定が終了すると、結果として得られたパッキングは、ＲＯＩ間の非重複の制約を満たすが、一般に被覆の制約は満たさない。この時点において、局所検索は、解決策を修復するために適用される。摂動は、ｂ_nではなく、（ｘ_n，ｙ_n）のみに適用されるので、選択された画像の集合は、このステップ中に修正される。このステップの効果は、この動きが被覆を増大させる場合には常に画像を移動させることであり、これは任意の決定論または確率的局所検索アルゴリズムによって行うことができる。

非重複および被覆の制約を共に満足する解決策が体系的に見いだされることを確認するため、必要に応じてステップ１）および２）を数回繰り返し、毎回制約をわずかに緩和する（式８の命題π_i）。制約満足化ステップは、複数の解決策を生成することができる。ステップ２における細分の後、これらの複数の解決策は、エネルギー関数で限定を使用して評価することができるか（式１）、または直接グラフカット最適化に与えられる。（厳密にエネルギー関数自体は、制約満足化によって搬送される際にピクセルの複数の被覆ではなく単一の被覆に対してのみ定義されるので、限定が必要とされる。）

アルファ展開によるグラフカット。各画像のシフトｓが修正されているので、グラフカット最適化は、各ピクセル−ラベルＬ（ｐ）の画像の変数ｎにのみ適用される必要がある。実際に、各ｐにおいて最大４つのｎの値が考慮される必要があるので、アルファ展開は非特許文献５に定義されているように使用される。ここで、最小化されるべき目的関数は、引き続き「動作中」である（１）のエネルギーＥの一部、つまりＷ_impＥ_imp（Ｌ）＋Ｗ_transＥ_trans（Ｌ）＋Ｗ_objＥ_obj（Ｌ）である。これらの項のうち第１は単項であり、第２および第３は２項である。このエネルギーは非メトリックと見ることができるので、上記で参照された我々の以前の特許文献に説明されているように、アルファ展開の短縮されたスキーマが使用される。アルファ展開の反復ごとに、４連結性特性が、１ピクセルずつ最適に展開された集合を拡張することによって促進される。

図１１に示されるように、混合プロセス４４００は、コラージュ内で隣接する入力画像間のシームレスな移行をもたらすために実行される。任意の適切な画像混合プロセスを使用することができる。オプションは、ポワソン混合（たとえば、非特許文献６参照）、またはエッジ感度を含むポワソン混合の拡張（たとえば、非特許文献７参照）を使用することである。

１つの実施形態において、画像色チャネルではなくαチャネルでエッジ依存の混合を使用する。これは、個々の入力画像ごとにアルファマスクを計算することによって行われる。第１のステップにおいて、特定の画像Ｉ_kについて、全ピクセルｐを備える重複領域が計算され、ここで、先行のグラフカット最適化の場合と同じであるラベルの集合Ｌ（ｐ）は、ラベルＩ_kおよび少なくとも１つのその他のラベルを含む。次いで、以下の汎関数は重複領域を最小化し、
Ｆ（α）＝∫‖ｕ（ｒ）−α（ｒ）‖²＋ｗ（ｒ）‖▽α‖²ｄｒ （９）
ここで

は、重複内に存在する画像Ｉ_nに取り込まれる。正規化定数ｇ²は平均二乗勾配であり、λ＝２０、β＝１０と設定する。関数ｕ（ｒ）は、グラフカットによって与えられた画像ラベルがＩ_kである場合、ピクセルｐにおいて値１をとり、それ以外の場合０をとる。次いで、この選択は、αをグラフカット解決策寄りに偏らせる。汎関数Ｆの最大化は、重複領域にわたりα＝０，１という境界条件に従い、ポワソン式を解くことによって計算される。最終ステップにおいて、各画像アルファマスクは、出力領域の各ピクセルｐにおいてすべての定義されたアルファマスクの合計が１になるように正規化される。その結果、シャープな接合および透明な混合がともに、コラージュ内で自動的に達成される。

αチャネルにこのエッジ依存の混合プロセスを使用することで、基となるシャープなエッジの存在または不在に従って、固有の境界に沿って切り取ること、または透明に混合することを自動的に切り替える継ぎ目が入力画像の間に作成される。

その他の実施形態において、ユーザ入力プリファレンス情報を考慮に入れることが可能である。たとえば、特定の画像がコラージュの作成に使用されるように選択するなど、ユーザが特定の制約を指定できるようにするユーザインターフェイスが提供される。次いで、それらのユーザ指定の制約は、最適化プロセス中に考慮に入れられる。加えて、ユーザインターフェイスは、ユーザが、入力画像を移動、サイズ変更、およびスワップを行えるようにして、特定の画像部分をコラージュに含むように選択できるようにする。

本明細書において使用される「コンピュータ」という用語は、命令を実行することができるなど、処理能力を備える任意の装置を示す。そのような処理能力は多くのさまざまな装置に組み入れられ、そのため「コンピュータ」という用語はＰＣ、サーバ、携帯電話、携帯情報端末、および多くのその他の装置を含むことを、当業者は理解するであろう。

本明細書において説明される方法は、記憶媒体上の機械可読の形態をとるソフトウェアによって実行することができる。ソフトウェアは、方法のステップが任意の適切な順序で、または同時に実行されうるように、並列プロセッサまたはシリアルプロセッサ上での実行に適したものであってもよい。

このことは、ソフトウェアが価値のある、単独で取引可能な商品となりうることを確認する。所望の機能を実行するために、「ダム」または標準のハードウェアで実行または制御するソフトウェアを含むことが意図されている。さらに、所望の機能を実行するために、シリコンチップの設計、または汎用プログラマブルチップの構成に使用されるような、ＨＤＬ（ハードウェア記述言語）ソフトウェアなどの、ハードウェアの構成を「記述」または定義するソフトウェアを含むことも意図されている。

プログラム命令を格納するために使用される記憶装置はネットワーク全体にわたり分散されうることを、当業者であれば理解するであろう。たとえば、リモートコンピュータは、ソフトウェアとして記述されるプロセスの例を格納することができる。ローカルまたは端末のコンピュータは、リモートコンピュータにアクセスし、ソフトウェアの一部または全部をダウンロードしてプログラムを実行することができる。あるいは、ローカルコンピュータは、必要に応じてソフトウェアの一部分をダウンロードするか、またはローカル端末において一部のソフトウェア命令を実行し、リモートコンピュータ（またはコンピュータネットワーク）において一部のソフトウェア命令を実行することができる。当業者に既知の従来の技法を使用することにより、ソフトウェア命令の全部または一部がＤＳＰ、プログラマブル論理アレイなどの専用回路によって実行されうることもまた、当業者であれば理解するであろう。

本明細書に示される任意の範囲または装置の価値は、求められている効果を失うことなく拡大または変更することができることは、当業者には明らかであろう。

上記で説明されている利点および利益が１つの実施形態に関連するか、または複数の実施形態に関連することを理解されたい。さらに、「ａｎ（ある）」項目が１つまたは複数のそのような項目を示すことを理解されたい。

本明細書において説明される方法のステップは、必要に応じて、任意の適切な順序で、または同時に実行することができる。

好ましい実施形態の上記の説明が、例示のためにのみ提示されたものであり、当業者によってさまざまな変更を加えることができることを理解されたい。上記の仕様、例、およびデータは、本発明の例示的な実施形態の構造および使用について詳細に説明する。上記で本発明のさまざまな実施形態は、ある程度詳細に、あるいは１つまたは複数の個々の実施形態を参照して説明されたが、当業者であれば、本発明の精神または範囲を逸脱することなく開示されている実施形態に数多くの変更を加えることができるであろう。

Claims (20)

1. （ｉ）複数のデジタル画像（１００）を受信するように配置された入力と、
   （ｉｉ）画像処理システムを制御するためにアプリケーション（１０５）によって使用されるように配置された少なくとも１つのアプリケーションプログラミングインターフェイス（１０６）を提供する第１のモジュール（１０１）と、
   （ｉｉ）各々前記第１のモジュールへのインターフェイスを有し、各々デジタルコラージュ（１０４）の形成に使用される情報を計算するように配置された複数の事前計算モジュール（１０２）と、
   （ｉｉｉ）前記第１のモジュールへのインターフェイスを有し、前記事前計算モジュールによって計算された前記情報に基づいて前記複数のデジタル画像の少なくとも一部からデジタルコラージュを形成するように配置された画像合成モジュール（１０３）とを備えることを特徴とする画像処理システム（１０８）。
2. 前記第１のモジュールは指定された寸法の要件を満たすために前記受信したデジタル画像の前記寸法を変更するように配置されることを特徴とする請求項１に記載の画像処理システム。
3. 前記第１のモジュールは少なくとも１つのメトリックに基づいて前記受信したデジタル画像をランク付けするように配置されることを特徴とする請求項１に記載の画像処理システム。
4. 各事前計算モジュールの出力は、値の２次元配列である潜在的行列を備え、各値は画像ブロックに関連付けられていることを特徴とする請求項１に記載の画像処理システム。
5. 前記事前計算モジュールの１つは、ガウス分布に従って重みを備える潜在的行列を生成するように配置されることを特徴とする請求項４に記載の画像処理システム。
6. 前記事前計算モジュールの１つは、所定の画像に対して、その画像から計算されたコントラスト値を備える顕在性の潜在的行列を生成するように配置されることを特徴とする請求項４に記載の画像処理システム。
7. 前記事前計算モジュールの１つは、所定の画像に対して、その画像から検出された顔に関する情報を備える顔の潜在的行列を生成するように配置されることを特徴とする請求項４に記載の画像処理システム。
8. 前記第１のモジュールはまた複数の前記受信した画像の各々に対して関心領域を決定するように配置されることを特徴とする請求項１に記載の画像処理システム。
9. 前記アプリケーションプログラミングインターフェイスは、特定の受信した画像の計算された関心領域が変更されるようにすることができる関数を備えることを特徴とする請求項１に記載の画像処理システム。
10. 前記アプリケーションプログラミングインターフェイスは、前記第１のモジュールによって決定された受信した画像のランクがオーバーライドされるようにすることができる関数を備えることを特徴とする請求項１に記載の画像処理システム。
11. 前記アプリケーションプログラミングインターフェイスは、前記事前計算および画像合成モジュールのいずれかの処理が一時停止されるようにすることができる関数を備えることを特徴とする請求項１に記載の画像処理システム。
12. 前記アプリケーションプログラミングインターフェイスは、前記事前計算および画像合成モジュールのいずれかの処理が再開されるようにすることができる関数を備えることを特徴とする請求項１に記載の画像処理システム。
13. 前記アプリケーションプログラミングインターフェイスは、前記事前計算および画像合成モジュールのいずれかにおける計算の進行状況に関する状態情報を取得するための少なくとも１つの関数を備えることを特徴とする請求項１に記載の画像処理システム。
14. 前記画像処理システムを制御するように配置されたアプリケーションをさらに備え、前記アプリケーションは表示画面においてユーザインターフェイスを表示するように配置され、前記ユーザインターフェイスは、事前計算モジュールの選択および前記選択された事前計算モジュールの結果に関連して使用されるべき相対的重みの選択を制御するための項目を備えることを特徴とする請求項１に記載の画像処理システム。
15. （ｉ）複数のデジタル画像（１００）を受信するステップと、
    （ｉｉ）第１のモジュール（１０１）において、画像処理の方法を制御するためにアプリケーション（１０５）によって使用されるように配置された少なくとも１つのアプリケーションプログラミングインターフェイス（１０６）を提供するステップと、
    （ｉｉ）複数の事前計算モジュール（１０２）を使用するステップであって、各々前記第１のモジュールへのインターフェイスを有し、デジタルコラージュ（１０４）の形成に使用される情報を計算するステップと、
    （ｉｉｉ）画像合成モジュール（１０３）を使用するステップであって、前記第１のモジュールへのインターフェイスを有し、前記事前計算モジュールによって計算された前記情報に基づいて前記複数のデジタル画像の少なくとも一部からデジタルコラージュを形成するステップとを備えることを特徴とする画像処理の方法。
16. 前記第１のモジュールを使用して、指定された寸法の要件を満たすように前記受信したデジタル画像の前記寸法を変更するステップを備えることを特徴とする請求項１５に記載の方法。
17. 前記第１のモジュールを使用して、少なくとも１つのメトリックに基づいて前記受信したデジタル画像をランク付けするステップを備えることを特徴とする請求項１５に記載の方法。
18. 各事前計算モジュールを使用して、値の２次元配列である潜在的行列を生成するステップであって、各値は画像ブロックに関連付けられているステップを備えることを特徴とする請求項１５に記載の方法。
19. 前記事前計算モジュールの１つを使用して、ガウス分布に従って重みを備える潜在的行列を生成するステップを備えることを特徴とする請求項１８に記載の方法。
20. （ｉ）複数のデジタル画像（１００）を受信するステップと、
    （ｉｉ）第１のモジュール（１０１）において、画像処理の方法を制御するためにアプリケーションによって使用されるように配置された少なくとも１つのアプリケーションプログラミングインターフェイスを提供するステップと、さらに前記第１のモジュールにおいて、受信した画像ごとに関心領域を計算するステップと、
    （ｉｉ）複数の事前計算モジュール（１０２）を使用するステップであって、各々前記第１のモジュールへのインターフェイスを有し、デジタルコラージュの形成に使用される情報を計算するステップと、
    （ｉｉｉ）画像合成モジュールを使用するステップであって、前記第１のモジュールへのインターフェイスを有し、前記事前計算モジュールによって計算された前記情報に基づいて前記複数のデジタル画像の少なくとも一部からデジタルコラージュを形成するステップとを備えるステップを実行するための装置実行可能命令を備えることを特徴とする１つまたは複数の装置読み取り可能媒体。

Images