(57)【要約】  コンピュータシステム内に画像を表示する。この画像は、目に見える特徴部を内部に有するコンテンツを含む。このコンテンツは、修正画像を生成する際に追加コンテンツが与えられるように定義されたコンテンツ領域を有する。画像上に配置すべきセマンティックマークを含む入力を受け取る。セマンティックマークは、領域の内側の内部領域部分及び領域の外側の外部領域部分を示す。画像に適用するパッチベースの最適化アルゴリズムを使用して、領域のための追加コンテンツを決定する。パッチベースの最適化アルゴリズムは、（ｉ）内部領域部分のための追加コンテンツを、セマンティックマークが示していない画像の領域ではなく外部領域部分に基づいて識別し、（ｉｉ）領域の残りの部分のための追加コンテンツを、外部領域部分に制限されずに識別する。領域内に追加コンテンツを有する修正画像を記憶する。【選択図】      図３Ｆ
2012526479.tif 000002
【特許請求の範囲】
【請求項１】
修正画像を生成するためのコンピュータ実施方法であって、
修正画像を生成する際に追加コンテンツを与えられるように定義されたコンテンツ領域を有し、目に見える特徴部を内部に有するコンテンツを含む画像をコンピュータシステム内に表示するステップと、
前記領域の内側の内部領域部分及び前記領域の外側の外部領域部分を示す、前記画像上に配置すべきセマンティックマークを含む入力を受け取るステップと、
（ｉ）前記内部領域部分のための前記追加コンテンツを、前記画像の前記セマンティックマークが示していない領域ではなく前記外部領域部分に基づいて識別し、（ｉｉ）前記領域の残りの部分のための前記追加コンテンツを、前記外部領域部分に制限されずに識別する、前記画像に適用するパッチベースの最適化アルゴリズムを使用して、前記領域のための前記追加コンテンツを決定するステップと、
前記領域内に前記追加コンテンツを有する前記修正画像を記憶するステップと、
を含むことを特徴とする方法。
【請求項２】
前記領域が、前記コンテンツを含んでいない穴を前記画像内に含み、前記修正画像が穴埋め処理で生成される、
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記穴が、前記コンテンツを以前に含んでいなかった前記領域内に前記特徴部が延びるようにして埋められる、
ことを特徴とする請求項２に記載の方法。
【請求項４】
前記画像が写真であり、前記特徴部が物理的対象であり、前記領域が、前記物理的対象の前記特徴部内で欠けている構造に対応して定義される、
ことを特徴とする請求項１に記載の方法。
【請求項５】
前記セマンティックマークが、線ツール、弧ツール、ブラシツール、領域選択ツール、及びこれらの組み合わせのうちの少なくとも１つを使用して作成される、
ことを特徴とする請求項１に記載の方法。
【請求項６】
前記内部領域部分を示すために、前記セマンティックマークの一部が前記領域内に配置され、前記外部領域部分を示すために、前記セマンティックマークの別の部分が前記領域外に配置される、
ことを特徴とする請求項１に記載の方法。
【請求項７】
前記パッチベースの最適化アルゴリズムが前記セマンティックマークを別々に処理するように、前記セマンティックマークを前記画像内の少なくとも１つの他のセマンティックマークと区別する識別特徴が前記セマンティックマークに割り当てられる、
ことを特徴とする請求項１に記載の方法。
【請求項８】
前記セマンティックマークが互いに交わり、前記パッチベースの最適化アルゴリズムが、前記セマンティックマークを別々に処理する、
ことを特徴とする請求項７に記載の方法。
【請求項９】
前記パッチベースの最適化処理のための追加のセマンティック制約を定義する別の入力を受け取るステップをさらに含む、
ことを特徴とする請求項１に記載の方法。
【請求項１０】
前記追加の制約が、
前記パッチベースの最適化アルゴリズムの整合性側面のために定義された第１の検索空間制限と、
前記パッチベースの最適化アルゴリズムの完全性側面のために定義された第２の検索空間制限と、
のうちの少なくとも一方を含み、
前記第１の検索空間制限が、前記画像の少なくとも第１の領域が前記追加コンテンツ内で使用されないようにし、前記第２の検索空間制限が、前記画像の前記第２の検索空間制限によって示される第２の領域に対して前記追加コンテンツが完全であることを求める、
ことを特徴とする請求項９に記載の方法。
【請求項１１】
前記外部領域部分が、前記領域を有する前記画像から分離した別の画像内に位置する、
ことを特徴とする請求項１に記載の方法。
【請求項１２】
有形プログラム担体内で明白に具体化された、命令を含むコンピュータプログラム製品であって、前記命令が、プロセッサによる実行時に、
修正画像を生成する際に追加コンテンツを与えられるように定義されたコンテンツ領域を有する、目に見える特徴部を内部に有するコンテンツを含む画像をコンピュータシステム内に表示するステップと、
前記領域の内側の内部領域部分及び前記領域の外側の外部領域部分を示す、前記画像上に配置すべきセマンティックマークを含む入力を受け取るステップと、
（ｉ）前記内部領域部分のための前記追加コンテンツを、前記画像の前記セマンティックマークが示していない領域ではなく前記外部領域部分に基づいて識別し、（ｉｉ）前記領域の残りの部分のための前記追加コンテンツを、前記外部領域部分に制限されずに識別する、前記画像に適用するパッチベースの最適化アルゴリズムを使用して、前記領域のための前記追加コンテンツを決定するステップと、
前記領域内に前記追加コンテンツを有する前記修正画像を記憶するステップと、
を含む方法を実施する、
ことを特徴とするコンピュータプログラム製品。
【請求項１３】
コンピュータ可読記憶媒体内で明白に具体化されたコンピュータプログラム製品であって、該コンピュータプログラム製品が命令を含み、該命令が、実行時に、
修正画像を生成する際に追加コンテンツを与えられるように定義されたコンテンツ領域を有する、目に見える特徴部を内部に有するコンテンツを含む画像をコンピュータシステム内に表示する画像表示領域と、
前記領域の内側の内部領域部分及び前記領域の外側の外部領域部分を示す、前記画像上に配置すべきセマンティックマークを含む入力を受け取るための入力コントロールと、
を含むグラフィカルユーザインターフェイスをディスプレイ装置上に生成し、
（ｉ）前記内部領域部分のための前記追加コンテンツを、前記画像の前記セマンティックマークが示していない領域ではなく前記外部領域部分に基づいて識別し、（ｉｉ）前記領域の残りの部分のための前記追加コンテンツを、前記外部領域部分に制限されずに識別する、前記画像に適用するパッチベースの最適化アルゴリズムを使用して、前記領域のための前記追加コンテンツが決定され、前記領域内に前記追加コンテンツを有する前記修正画像が記憶される、
ことを特徴とするコンピュータプログラム製品。
【請求項１４】
前記領域が、前記コンテンツを含んでいない穴を前記画像内に含み、前記修正画像が穴埋め処理で生成される、
ことを特徴とする請求項１３に記載のコンピュータプログラム製品。
【請求項１５】
前記画像が写真であり、前記特徴部が物理的対象であり、前記領域が、前記物理的対象の前記特徴部内で欠けている構造に対応して定義される、
ことを特徴とする請求項１３に記載のコンピュータプログラム製品。
【請求項１６】
前記入力コントロールが、線ツール、弧ツール、ブラシツール、領域選択ツール、及びこれらの組み合わせのうちの少なくとも１つを含む、
ことを特徴とする請求項１３に記載のコンピュータプログラム製品。
【請求項１７】
前記入力コントロールが、前記パッチベースの最適化アルゴリズムが前記セマンティックマークを別々に処理するように、前記セマンティックマークを前記画像内の少なくとも１つの他のセマンティックマークと区別する識別特徴を前記セマンティックマークに関連付ける、
ことを特徴とする請求項１２又は１３に記載のコンピュータプログラム製品。
【請求項１８】
修正画像を生成する際に追加コンテンツを与えられるように定義されたコンテンツ領域を有する、目に見える特徴部を内部に有するコンテンツを含む画像を表示するディスプレイ装置と、
前記特徴部の少なくとも一部を示す、前記画像上に配置すべきセマンティックマークを含む入力を受け取るための入力装置と、
を備え、前記セマンティックマークが、該セマンティックマークの内部領域部分及び外部領域部分が形成されるように前記領域の境界と交わり、
（ｉ）前記内部領域部分のための前記追加コンテンツを、前記画像の前記セマンティックマークが示していない領域ではなく前記外部領域部分に基づいて識別し、（ｉｉ）前記領域の残りの部分のための前記追加コンテンツを、前記外部領域部分に制限されずに識別する、前記画像に適用するパッチベースの最適化アルゴリズムを使用して、前記領域のための前記追加コンテンツを決定する画像エディタ要素をさらに備える、
ことを特徴とするシステム。
【請求項１９】
前記入力装置が、線ツール、弧ツール、ブラシツール、領域選択ツール、及びこれらの組み合わせのうちの少なくとも１つを含む、
ことを特徴とする請求項１８に記載のシステム。
【請求項２０】
前記入力装置が、前記パッチベースの最適化アルゴリズムが前記セマンティックマークを別々に処理するように、前記セマンティックマークを前記画像内の少なくとも１つの他のセマンティックマークと区別する識別特徴を前記セマンティックマークに関連付ける、
ことを特徴とする請求項１８に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
〔関連出願との相互参照〕
本出願は、両方ともに「画像の領域に追加コンテンツを与えることによる修正画像の生成（ＧＥＮＥＲＡＴＩＮＧ  Ａ  ＭＯＤＩＦＩＥＤ  ＩＭＡＧＥ  ＷＩＴＨ  ＡＤＤＩＴＩＯＮＡＬ  ＣＯＮＴＥＮＴ  ＰＲＯＶＩＤＥＤ  ＦＯＲ  Ａ  ＲＥＧＩＯＮ  ＴＨＥＲＥＯＦ）」という名称が付けられた、２００９年５月６日に出願された米国仮特許出願第６１／２１５，４６５号及び２００９年５月２１日に出願された米国特許出願第１２／４５４，６６６号に対する優先権を主張するものであり、これらの出願の各々はその内容全体が引用により本明細書に組み入れられる。
【０００２】
本明細書は、デジタル画像処理に関する。
【背景技術】
【０００３】
既存の画像処理技術には、パッチベースの技術を使用してコンテンツを操作するものがある。この処理は、画像コンテンツの（ピクセル群などの）パッチを分析又は合成することを伴うことができる。例えば、パッチベースの方法は、画像及びビデオコンテンツのノイズ除去、超解像の実施のような画像解像度の強化、画像コンテンツの圧縮、再ターゲット化などによる画像のアスペクト比の変更、画像コンテンツの再シャッフル、画像のスティッチング、画像コンテンツの編集、及びテクスチャ合成を行う際に使用される。パッチベースの方法は、合成操作に関して利点を有することができる。例えば、構造、テクスチャ、繰り返しパターン、及び冗長性を処理することができる。
【０００４】
異なる方法で画像を仕上げるための技術が試行されており、これらはパッチベースの技術に依拠することがある。例えば、画像内の他の場所のコンテンツを分析することにより、画像内の穴に対応するコンテンツを見つけようと試みる穴埋め技術が存在する。ユーザがソース領域を手動で選択し、次にこの領域を対象領域にコピーして穴を埋めるクローニング技術も存在する。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】ＷＥＸＬＥＲ，Ｙ、ＳＨＥＣＨＴＭＡＮ，Ｅ、及びＩＲＡＮＩ，Ｍ著「ビデオの時空間補完（Ｓｐａｃｅ−ｔｉｍｅ  ｃｏｍｐｌｅｔｉｏｎ  ｏｆ  ｖｉｄｅｏ）」、ＩＥＥＥ議事録、ＰＡＭＩ第２９巻、第３号（２００７年３月）４６３〜４７６ページ
【非特許文献２】ＳＩＭＡＫＯＶ，Ｄ、ＣＡＳＰＩ，Ｙ、ＳＨＥＣＨＴＭＡＮ，Ｅ、及びＩＲＡＮＩ，Ｍ著（２００８年）「双方向類似性を用いた視覚データの要約（Ｓｕｍｍａｒｉｚｉｎｇ  ｖｉｓｕａｌ  ｄａｔａ  ｕｓｉｎｇ  ｂｉｄｉｒｅｃｔｉｏｎａｌ  ｓｉｍｉｌａｒｉｔｙ）」、コンピュータビジョン及びパターン認識（Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ）、ＣＶＰＲ２００８、ＩＥＥＥ会議
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は、ユーザが提供したセマンティック情報を使用する画像修正に関する。
【課題を解決するための手段】
【０００７】
第１の態様では、修正画像を生成するためのコンピュータ実施方法が、コンピュータシステム内に画像を表示するステップを含む。この画像は、目に見える特徴部を内部に有するコンテンツを含み、このコンテンツは、修正画像を生成する際に追加コンテンツが与えられるように定義された領域を有する。方法は、領域の内側の内部領域部分と領域の外側の外部領域部分とを示す、画像上に配置すべきセマンティックマークを含む入力を受け取るステップを含む。方法は、画像に適用するパッチベースの最適化アルゴリズムを使用して領域のための追加コンテンツを決定するステップを含み、このパッチベースの最適化アルゴリズムは、（ｉ）内部領域部分のための追加コンテンツを、画像のセマンティックマークが示していない領域ではなく外部領域部分に基づいて識別し、（ｉｉ）領域の残りの部分のための追加コンテンツを外部領域部分に制限されずに識別する。方法は、領域内に追加コンテンツを有する修正画像を記憶するステップを含む。
【０００８】
実施構成は、以下の特徴のうちのいずれか又は全てを含むことができる。領域は、コンテンツを含んでいない穴を画像内に含むことができ、修正画像を穴埋め処理で生成することができる。この穴は、以前にコンテンツを含んでいなかった領域内に特徴部が延びるようにして埋めることができる。画像は写真とすることができ、特徴部は物理的対象とすることができ、領域は、特徴部内で欠けている物理的対象の構造に対応して定義することができる。セマンティックマークは、線ツール、弧ツール、ブラシツール、領域選択ツール、及びこれらの組み合わせのうちの少なくとも１つを使用して作成することができる。内部領域部分を示すために、セマンティックマークの一部を領域内に配置することができ、外部領域部分を示すために、セマンティックマークの別の部分を領域外に配置することができる。セマンティックマークには、パッチベースの最適化アルゴリズムがセマンティックマークを別々に処理するように、セマンティックマークを画像内の少なくとも１つの他のセマンティックマークと区別する識別特徴を割り当てることができる。セマンティックマークは互いに交わることができ、パッチベースの最適化アルゴリズムは、セマンティックマークを別々に処理することができる。方法は、パッチベースの最適化処理のための追加のセマンティック制約を定義する別の入力を受け取るステップをさらに含む。この追加の制約は、パッチベースの最適化アルゴリズムの整合性側面のために定義された第１の検索空間制限、及びパッチベースの最適化アルゴリズムの完全性側面のために定義された第２の検索空間制限の少なくとも一方を含むことができ、第１の検索空間制限は、画像の少なくとも第１の領域が追加コンテンツ内で使用されないようにし、第２の検索空間制限は、画像の第２の検索空間制限によって示される第２の領域に対して追加コンテンツが完全であることを求める。外部領域部分は、領域を有する画像から分離した別の画像内に位置することができる。
【０００９】
プロセッサによる実行時に方法を実施する命令を含む、有形プログラム担体内で明白に具体化されたコンピュータプログラム製品を使用して方法を実施することができる。
【００１０】
第２の態様では、グラフィカルユーザインターフェイスが、修正画像を生成する際に追加コンテンツが与えられるように定義されたコンテンツ領域を有する、目に見える特徴部を内部に有するコンテンツを含む画像をコンピュータシステム内に表示する画像表示領域を含む。このグラフィカルユーザインターフェイスは、領域の内側の内部領域部分と領域の外側の外部領域部分とを示す、画像上に配置すべきセマンティックマークを含む入力を受け取るための入力コントロールを含む。領域のための追加コンテンツは、画像に適用するパッチベースの最適化アルゴリズムを使用して決定され、このパッチベースの最適化アルゴリズムは、（ｉ）内部領域部分のための追加コンテンツを、画像のセマンティックマークが示していない領域ではなく外部領域部分に基づいて識別し、（ｉｉ）領域の残りの部分のための追加コンテンツを、外部領域部分に制限されずに識別し、領域内に追加コンテンツを有する修正画像が記憶される。
【００１１】
実施構成は、以下の特徴のうちのいずれか又は全てを含むことができる。領域は、コンテンツを含んでいない穴を画像内に含むことができ、修正画像を穴埋め処理で生成することができる。画像は写真とすることができ、特徴部は物理的対象とすることができ、領域は、特徴部内で欠けている物理的対象の構造に対応して定義することができる。入力コントロールは、線ツール、弧ツール、ブラシツール、領域選択ツール、及びこれらの組み合わせのうちの少なくとも１つを含むことができる。入力コントロールは、パッチベースの最適化アルゴリズムがセマンティックマークを別々に処理するように、セマンティックマークを画像内の少なくとも１つの他のセマンティックマークと区別する識別特徴をセマンティックマークに関連付けることができる。
【００１２】
グラフィカルユーザインターフェイスは、実行時にディスプレイ装置上にグラフィカルユーザインターフェイスを生成する命令を含む、コンピュータ可読記憶媒体内で明白に具体化されたコンピュータプログラム製品を使用して実現することができる。
【００１３】
第３の態様では、システムが、修正画像を生成する際に追加コンテンツが与えられるように定義されたコンテンツ領域を有する、目に見える特徴部を内部に有するコンテンツを含む画像を表示するディスプレイ装置を含む。システムは、特徴部の少なくとも一部を示す、画像内に配置すべきセマンティックマーク、を含む入力を受け取るための入力装置を含み、このセマンティックマークは、セマンティックマークの内部領域部分及び外部領域部分が形成されるように領域の境界と交わる。システムは、画像に適用するパッチベースの最適化アルゴリズムを使用して領域のための追加コンテンツを決定する画像エディタ要素を含み、パッチベースの最適化アルゴリズムは、（ｉ）内部領域部分のための追加コンテンツを、画像のセマンティックマークが示してない領域ではなく外部領域部分に基づいて識別し、（ｉｉ）領域の残りの部分のための追加コンテンツを、外部領域部分に制限されずに識別する。
【００１４】
実施構成は、以下の特徴のうちのいずれか又は全てを含むことができる。入力装置は、線ツール、弧ツール、ブラシツール、領域選択ツール、及びこれらの組み合わせのうちの少なくとも１つを含むことができる。入力装置は、パッチベースの最適化アルゴリズムがセマンティックマークを別々に処理するように、セマンティックマークを画像内の少なくとも１つの他のセマンティックマークと区別する識別特徴をセマンティックマークに関連付けることができる。
【００１５】
本明細書で説明する主題の特定の実施形態は、以下の利点の１又はそれ以上を実現するように実施することができる。画像編集を改善することができる。ユーザが、画像内の１又はそれ以上の特徴をマークするための入力を行うことにより、ソース画像内のセマンティックを保持することができる。ユーザは、補完すべき穴又はその他の画像領域内に延びる特徴部をマークすることができ、この特徴部とマッチする、コンテンツを埋めるためのコンテンツを選択する際にこのマークを使用することができる。
【００１６】
本明細書で説明する主題の１又はそれ以上の実施形態の詳細を、添付図面及び以下の説明に示す。以下の説明、添付図面、及び特許請求の範囲から、主題の他の特徴、態様、及び利点が明らかになるであろう。
【００１７】
特許又は出願ファイルは、カラーで作成された少なくとも１つの図面を含む。（単複の）カラー図面を含む本特許又は特許出願公報の複写物は、依頼に応じて、及び必要な料金の支払いを受けて特許庁により提供される。
【図面の簡単な説明】
【００１８】
【図１】修正画像を生成することができるシステム例を示す図である。
【図２】画像修正の制約の例を示す概略図である。
【図３Ａ】画像修正の別の例を示す図である。
【図３Ｂ】画像修正の別の例を示す図である。
【図３Ｃ】画像修正の別の例を示す図である。
【図３Ｄ】画像修正の別の例を示す図である。
【図３Ｅ】画像修正の別の例を示す図である。
【図３Ｆ】画像修正の別の例を示す図である。
【図３Ｇ】画像修正の別の例を示す図である。
【図４】画像修正の別の例を示す図である。
【図５Ａ】画像修正の別の例を示す図である。
【図５Ｂ】画像修正の別の例を示す図である。
【図５Ｃ】画像修正の別の例を示す図である。
【図５Ｄ】画像修正の別の例を示す図である。
【図６】方法例のフロー図である。
【発明を実施するための形態】
【００１９】
様々な図面における同様の参照番号及び記号表示は同様の要素を示す。
【００２０】
図１には、修正画像を生成できるシステム例１００を示している。システム１００はコンピュータ装置１０２を含み、この装置は、以下に限定されるわけではないが、パーソナルコンピュータ、サーバ装置、ワークステーション、又はハンドヘルド装置などのいずれのプロセッサベースの装置であってもよい。
【００２１】
システム１００は、ここではコンピュータ装置１０２により生成されるグラフィカルユーザインターフェイス（ＧＵＩ）１０４を含む。例えば、このＧＵＩ１０４を、コンピュータ装置に接続されたディスプレイ装置１０６上に表示することができる。ＧＵＩ１０４は、ユーザに初期画像及び／又は修正画像を示すためなどの画像の操作において使用される。
【００２２】
システム１００は、いくつか例を挙げると、メモリ、ハードドライブ、又は光ディスクなどの形の、データを記憶するのに適したいずれかの技術を使用して実装することができる少なくとも１つのリポジトリ１０８を含む。リポジトリ１０８は、修正していない画像及び／又は修正した画像などの１又はそれ以上の画像を含むことができる。システム１００は、例えばＧＵＩ１０４内に（単複の）画像を表示することにより、リポジトリ１０８内の１又はそれ以上の画像をユーザが利用できるようにすることができる。
【００２３】
システム１００は、キーボード、マウス、ポインティングデバイス、トラックボール、ジョイスティック、トラックパッド、又はその他のいずれかの装置などの、ユーザがコンピュータ装置１０２を制御し、及び／又はこれに応答できるようにする少なくとも１つの入力装置１１０を含む。ユーザは、修正に１又はそれ以上の制約を適用するなどの、画像処理に影響を与える入力を行うことができる。
【００２４】
システム１００は、画像内で穴埋めを行うことによって画像を修正することなどのいくつかの目的のいずれかのために使用することができ、これについては以下で具体例として使用する。他の用途として、以下に限定されるわけではないが、写真の被写体である物理的対象内で欠けている構造に対応する画像コンテンツを追加するように写真を修正することが挙げられる。一般的には、この修正は、初期画像の領域内に、この画像の別の領域から選択した情報を追加するステップを含む。ここでは、これらの及びその他の動作が、メモリ内又はディスク上などのコンピュータ可読記憶装置に記憶されたプロセッサ実行命令を使用して実装できる画像エディタ要素１１２によって行われる。画像エディタ要素１１２は、ＧＵＩ１０４内の画像表示領域１１４及び入力制御領域１１６などに表示するための出力を生成することができる。
【００２５】
少なくとも整合性基準に従うパッチベースの最適化を使用して画像修正処理を行うことができる。パッチベースの最適化アルゴリズムが、ＷＥＸＬＥＲ，Ｙ、ＳＨＥＣＨＴＭＡＮ，Ｅ、及びＩＲＡＮＩ，Ｍ著「ビデオの時空間補完（Ｓｐａｃｅ−ｔｉｍｅ  ｃｏｍｐｌｅｔｉｏｎ  ｏｆ  ｖｉｄｅｏ）」、ＩＥＥＥ議事録、ＰＡＭＩ第２９巻、第３号（２００７年３月）４６３〜４７６ページに記載されており、この文献はその内容全体が引用により本明細書に組み入れられる。ここでは、ユーザ定義によるセマンティック制約を考慮するパッチベースの最適化アルゴリズムが、以下を含むことができる。
【００２６】
欠けている領域境界を円滑に補間することにより、修正画像を初期化することができる。
【００２７】
最初に最も粗いスケールを使用してソース画像内の穴を埋め、その後より細かいスケールへと反復的に補間するマルチスケールアルゴリズムを開始することができる。例えば、最も細かいスケールがソース画像のスケールに一致するガウスピラミッドを使用することができる。
【００２８】
少なくとも１つのユーザ指定による制約下で、反復的に繰り返す伝播及びランダム検索ステップを使用して最近傍処理を行うことができる。
【００２９】
個々のピクセルに、その全ての重複するパッチの最近傍に基づいて色票を割り当てることができる。
【００３０】
新たな色を取得するには、色票を平均化し、又はクラスタ化して最も大きなクラスタ又はモードを選択することができる。
【００３１】
結果を改善するために、上記３つのステップを一定の反復回数にわたって、又は画像の変化が所定量未満になるまで、或いは別の終了基準に基づいて繰り返すことができる。
【００３２】
上記４つのステップを、マルチスケールアルゴリズムの一部として繰り返すことができる。
【００３３】
パッチベースの最適化では、最近傍技術を使用することができる。例えば、初期画像内のパッチに（例えば５×５のピクセルパッチなどの所定数のピクセルに）最近傍処理を適用することができる。初期画像内の個々のパッチ座標を２次元オフセット空間にマッピングする最近傍フィールドを求めることができる。オフセットは、初期画像内のパッチと修正画像内の対応するパッチとの間におけるパッチ座標の調整を表す。例えば、初期画像内の初期パッチａが、修正画像内に最近傍パッチｂを有する。この場合、最近傍フィールドｆは、次式のように定義される。ｆ（ａ）＝ｂ−ａ
【００３４】
最近傍フィールドのオフセット値は、アレイに記憶することができる。例えば、このアレイは、初期画像と同じ寸法を有することができる。
【００３５】
パッチベースの最適化は、初期オフセットの組から開始する。次に、初期オフセットに基づく反復的更新を最近傍フィールドに適用する。個々の反復では、良好なパッチオフセットが隣接するパッチに伝播され、最適なオフセットの近傍でランダム検索が行われる。
【００３６】
初期オフセットは、オフセットフィールドに値をランダムに割り当てることにより、又は事前情報を使用して生成することができる。画像ピラミッドを使用する階層的細密化処理では、前のレベルからの最初の推測を現在のレベル用に使用することができる。最終的な画像解像度に達しなかった場合、現在の推定解を画像ピラミッド内の次に高い解像度に再スケールし、上記４つのステップをマルチスケールアルゴリズムの一部として繰り返す。例えば、ランダムな初期化に基づいてアルゴリズムを数回反復することができ、次にこれを利用可能な最初の推測と融合した後で残りの反復を行うことができる。
【００３７】
反復処理では、パッチオフセットをオフセットアレイ全体にわたって走査順に調べることができる。個々の反復は、伝播ステップ及びランダム検索ステップを含む。伝播ステップでは、マッピングｆ（ｘ，ｙ）が調べられていると仮定する。近隣マッピングｆ（ｘ−１，ｙ）及びｆ（ｘ，ｙ−１）を使用して、マッピングｆ（ｘ，ｙ）を改善する。例えば、ｆ（ｘ−１，ｙ）が良好なマッピングであった場合、処理は、これを（ｘ，ｙ）に使用しようと試みる。１回おきなどのいくつかの反復では、オフセット／マッピング品質に関する情報が逆方向に伝播されるようにオフセットを逆の順序で調べることができる。
【００３８】
マッピングは、パッチ距離関数を使用して評価することができる。あらゆる距離関数を使用することができる。いくつかの実施構成では、自然画像、及び／又はビデオ及び３次元形状などのその他のデータソースに、Ｌｐ、Ｌ１、又はクランプドＬ２などの共通の距離関数を、又は他のいずれかのスカラー関数を使用することができる。いくつかの実施構成では、パッチ距離関数Ｄが、隣接する重複パッチのための最適なオフセットが高い確率で類似するように選択される。この確率が高い程、アルゴリズムは速く収束する。
【００３９】
ランダム検索ステップでは、処理が、より良いマッピングを求めて（すなわち、ソースパッチまでの距離メトリックがより低い目標パッチを求めて）修正画像内をランダムに検索することにより、マッピングｆ（ｘ，ｙ）を改善しようと試みる。いくつかの実施構成では、目標パッチからの距離が連続的に減少するパッチを評価することができる。例えば、フィールド［−１，１］×［−１，１］内で選択される方向を均一にランダムに選択し、指数関数を使用して最大ピクセル半径ｗからの距離を減少させる。ランダム検索でより良いマッピングが見つかった場合、これが現在のマッピングに取って代わる。
【００４０】
基準が満たされた場合には反復が中断する。いくつかの実施構成では、修正したオフセットの一部が閾値を下回るかどうかが基準となる。いくつかの実施構成では、５回などの一定の反復回数が使用される。パッチベースの最適化を行うことにより、修正画像が初期画像に対応するように生成される。例えば、修正画像は、初期画像の画像の穴を埋めたバージョン、又は特徴部にコンテンツを選択的に追加したバージョンとすることができる。上述したようにして生成された中間画像は、最初に推測したよりも改善されていると推定されるが、画像補完の問題を満足に解決していない可能性がある。従って、質の高い最終的な解を計算するために、内部ループで反復オフセット最適化を使用して処理全体を反復的に繰り返す。
【００４１】
いくつかの実施構成では、例えば、画像領域間の両方向（例えば、初期画像内のパッチから修正画像内のパッチへ、及びその逆）において良好な対応性を見出すもののような双方向類似性測度を使用することができる。例えば、画像領域が十分に類似している場合、既存の双方向類似性法は、部分的に連続する解に収束することができ、多くの際立つ領域が最小限の歪みで出力にコピーされる。例えば、ソース画像内の近隣のパッチのほとんどのオフセットがほぼ同一になることができる。別の例として、画像領域が特に類似していない場合、真の双方向類似性が、画像内のランダムパッチの類似性に近くなり得る。
【００４２】
いくつかの実施構成では、双方向類似性アルゴリズムが、少なくとも以下の動作を含むことができる。整合性ステップでは、アルゴリズムが、穴の中の全てのパッチに対して穴の外の最も近傍のパッチを求める。完全性ステップでは、アルゴリズムが、穴の外の全てのパッチに対して穴の中の最も近傍のパッチを求める。これらの検索により、ソース画像と目標画像の間の両方向において最近傍票が生成される。これらの票を使用して、個々の内部ループの反復において（例えば平均化又はクラスタ化によって）穴の中の個々のピクセルの色を計算する。ユーザ定義による制約という状況では、完全性項を使用して、ユーザが穴の中に含めたいと望む領域を定義し、穴がユーザ定義領域に関しては完全になるが、アルゴリズムが領域を穴の中のどこに配置するかをユーザが正確に指定しないようにすることができる。
【００４３】
パッチベースの最適化アルゴリズムでは、修正画像内の全てのパッチが初期画像に由来するものであるかどうかに関する整合性基準を使用することができる。すなわち、画像エディタ要素１１２は、目標画像に関し、穴を埋めるために使用される全てのパッチがソース画像内のどこかに存在して、目標画像がソース画像と整合するようになることを確実にしようすることができる。例えば、修正画像内の個々のパッチは、初期画像内に少なくとも１つの対応するパッチを有するべきである。対照的に、修正画像内のパッチが初期画像内に対応するパッチを有していない場合、整合性基準は満たされない。修正画像における整合性は、最終的に複数のスケールでの局所的整合性が、目標画像において全体的に整合した自然な出力を生むように複数のスケールで処理することよって得ることができる。
【００４４】
双方向類似性計算は、整合性項に加えて完全性項を使用する。完全性項は、２つ例を挙げると、穴埋め用途のためのアルゴリズムにおいて、或いは補完の再ターゲット化及び／又は再シャッフルとの組み合わせにおいて使用することができる。いくつかの実施構成では、ユーザが、画像内の穴をマークし、１又はそれ以上の検索空間制約を追加し、出力サイズを小さくすること（すなわち再ターゲット化）を指定し、他のいくつかの領域をあちこちに動かすこと（すなわち再シャッフル）を指定することができ、その後システムがこれらをまとめて実行して出力を合成することができる。
【００４５】
例えば、完全性項は、ソース画像からの全てのコンテンツが目標画像内のどこかに存在することを確実にしようすることができる。完全性基準は、初期画像内の全てのパッチが修正画像内に表されているかどうかに関する。例えば、初期画像が複数の同一のパッチを含む場合、完全性基準は、これらのパッチの少なくとも１つが修正画像内で見出されるべきであることを指定する。対照的に、初期画像内の一意的なパッチが修正画像内に対応するパッチを有していない場合、完全性基準は満たされない。
【００４６】
例えば、再ターゲット化を行うために、双方向又は単方向の類似性アルゴリズムの内部ループ内で最近傍アルゴリズムを反復的に実行することができる。
【００４７】
双方向類似性計算の例が、ＳＩＭＡＫＯＶ，Ｄ、ＣＡＳＰＩ，Ｙ、ＳＨＥＣＨＴＭＡＮ，Ｅ、及びＩＲＡＮＩ，Ｍ著（２００８年）「双方向類似性を用いた視覚データの要約（Ｓｕｍｍａｒｉｚｉｎｇ  ｖｉｓｕａｌ  ｄａｔａ  ｕｓｉｎｇ  ｂｉｄｉｒｅｃｔｉｏｎａｌ  ｓｉｍｉｌａｒｉｔｙ）」、コンピュータビジョン及びパターン認識（Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ）、ＣＶＰＲ２００８、ＩＥＥＥ会議に記載されている。
【００４８】
図２には、画像修正のための制約例を概略的に示している。ここでは、画像２００が、一区画の土地とその上にある建物を示す初期画像である。画像２００は、現在画像コンテンツを欠いている穴２０２を含む。画像２００には、穴２０２の代わりに納得できる外観を作成する修正処理が行われる。
【００４９】
３つのシナリオ例を示し、（ａ）、（ｂ）、及び（ｃ）のラベルを付けている。シナリオ（ａ）及び（ｂ）は、類似性アルゴリズムにおいて整合性項のみに対応する。このことを、これらの例を示す行に「整合性」という名前を付けることによって示している。すなわち、シナリオ（ａ）及び（ｂ）は、最終的に穴２０２内に配置されるコンテンツが図２００内に確実に存在するようにすることに焦点を置く。
【００５０】
シナリオ（ａ）は、検索空間の制限に関する。すなわち、この例で青色で示している領域２０４が、穴２０２を埋めるパッチを見つけるための検索空間となる。対照的に、この例で暗灰色で示している領域２０６は、穴埋め手順のための検索空間として使用されない。ユーザは、１又はそれ以上の理由から検索空間を領域２０４に絞り込むことができる。例えば、画像２００が、家のそばの地面上に黄色及び赤色の花を含むことに注目されたい。ユーザが穴２０２に花を含めたくないと仮定する。従って、ユーザは領域２０４を、この領域が花を含まずに画像２００の残りの部分を含むように定義することができる。このようにして、埋められる穴が画像２００に対して整合性を有すると同時に、穴に花が含まれないことが確実になる。
【００５１】
ユーザは、いずれかのツールを使用して、システム１００（図１）内に画像２００が表示されているときに領域２０４及び／又は２０６をマークすることなどにより、この定義を行うことができる。他のあらゆる形状の領域２０４及び／又は領域２０６を使用することができる。
【００５２】
シナリオ（ｂ）は、複数インデックス検索空間の制約に関する。ここでは、ユーザが、穴の境界を横切ってセマンティックマーク２０８及び２１０を配置し、一対のセマンティックマーク２１２を、その一方の部分２１２Ａが穴の中に存在し、もう一方の部分２１２Ｂが穴の外に存在するように配置する。セマンティックマークの意義は、例えばマーク２０８の穴の外にある部分が示す領域のみを検索することに基づいて、マーク２０８の穴の中の部分が埋められるようにすることである。このようなセマンティック画像補完の１つの解釈の仕方は、これによりユーザが、補完処理において穴の境界近くのいずれの（単複の）特徴部を穴の中に拡張すべきかをセマンティックに示せるようになるということである。例えば、ユーザは、画像２００内の家の角を続けて穴２０２の中に垂直に下ろしたいと望むことができる。従って、ユーザは、この角の少なくとも一部をマーク２０８で示すことができる。これにより、この角の画像情報が、マーク２０８で示される穴の部分のための検索空間として使用され、さらに穴のこの部分を埋める際に、屋根又は花などの画像２００内のどこか別の場所からの情報が使用されないようにすることが確実になる。同様に、ユーザはマーク２１０を配置して、家の土台の基線が穴の中に延びることを示すことができる。
【００５３】
一対のセマンティックマーク２１２も、穴の一部のための検索空間を定義することに関する。詳細には、部分２１２Ａは穴の領域を示し、部分２１２Ｂは、部分２１２Ａが示す領域に使用すべき検索空間を定義する。すなわち、マーク２１２により、ユーザは、花の群れなどの穴２０２の外部の特定の特徴部を、穴の中の特定の領域のための検索空間とすべきであることを指定できるようになる。
【００５４】
いくつかの実施構成では、穴を含む画像とは別の画像内にマーク２１２Ｂを配置することができる。すなわち、穴の一部を埋めるための検索空間は、修正中の画像の外部のコンテンツを含むこともできる。例えば、ある人物の類似する画像が存在し、これらの画像の一方では人物の目が閉じていると仮定する。この場合、ユーザは、片方又は両方の目を穴としてマークし、コンテンツをどこに配置すべきかを示すためのマークを穴の中に追加し、別の画像内の開いた目にセマンティックマークを関連付けることができる。
【００５５】
穴２０２の、マーク２０８〜２１２のいずれによっても示されていない残りの部分については、アルゴリズムが画像２００全体を検索空間として使用する。すなわち、穴の中のセマンティックマークが付いていない領域は、特定のセマンティック検索空間のみに限定されない。
【００５６】
シナリオ（ｃ）では、下の行にその旨のラベルで示すように完全性側面も考慮される。すなわち、アルゴリズムは、埋められた穴が画像２００に対して整合しているだけでなく、この穴が、画像２００の少なくとも一部に対して完全であることも確実にする。このことは、１又はそれ以上のユーザ定義によるセマンティック制約を考慮しながら双方向類似性アルゴリズムを実行することに対応する。
【００５７】
まず、この例では、ユーザは、画像２００全体を覆う青色の領域２１４によって示すように、整合性側面のための検索空間を限定しない。すなわち、アルゴリズムは、穴の中に配置する全てのコンテンツを、画像２００内のどこかで確実に見つけることができるようにする。
【００５８】
次に、ユーザは、穴を画像コンテンツで埋める際に、この中に画像２００内の黄色い花が確実に含まれるようにしたいと望む。ユーザにとっての１つの選択肢は、一方の部分が穴の中にあってもう一方の部分が黄色い花を示す対２１２などのセマンティックマークを使用することであると考えられる。これには、シナリオ（ｂ）において部分２１２Ａを配置した方法と同様に、ユーザが穴の中の正確な場所を指定することが必要となる。しかしながら、ここでは、ユーザはセマンティック完全性マーク２１６で黄色い花を示す。マーク２１６は、画像２００のマークで示す部分に関して穴を完全にすべきであることをアルゴリズムに指示する。すなわち、アルゴリズムは、穴をコンテンツで埋める際に、マーク２１６で示されるコンテンツが全て穴の中のどこかで確実に見出されるようにする。このようにして、ユーザは、画像修正処理にセマンティック完全性制約を選択的に適用することができる。黄色い花のみとは対照的に、ユーザが画像２００全体をマーク２１６でマークしたとしたら、アルゴリズムは、画像２００の全てのコンテンツを穴の中に配置する必要があるであろう。
【００５９】
シナリオ（ａ）、（ｂ）及び（ｃ）の組み合わせを使用することもできる。例えば、マーク２０８を、シナリオ（ａ）の検索空間制限と組み合わせて使用することができる。別の例として、同じ画像修正処理において少なくとも１つの整合性制約及び完全性制約を適用することができる。
【００６０】
いくつかの実施構成では、２又はそれ以上のセマンティックマークが重なることができる。例えば、穴の中のパッチが２又はそれ以上のセマンティックマークによって示されている（例えば、パッチが、パッチに関連する２つのインデックス／色を有する）場合、これらのマークが示す全ての領域内のためのパッチを検索すべきである。
【００６１】
図３Ａ〜図３Ｇには、別の画像修正の例を示している。この例では、写真の被写体内の構造の欠けた画像コンテンツを、いかにしてユーザからの誘導で与えることができるかをより詳細に説明する。図３Ａには、ツール３００が示されている。例えば、画像エディタ要素１１２によってツール３００を生成し、その出力をＧＵＩ１０４（図１）内に表示することができる。画像３００Ａは、木製の柵を含む背景の前を飛んでいる鷲を示している。ここで行うべき修正は、鷲を削除して、柵及び周辺の枝葉の自然な画像を作り出すことである。
【００６２】
図３Ｂは、ユーザがコントロール３０４を使用して、削除すべき画像コンテンツを示すことができることを示している。ここでは、コントロール３０４は描画ツールであり、ユーザは、鷲の境界の周囲をトレースし始めている。マーキングには、投げ縄ツール又は色感知ツールなどのあらゆる種類のツールを使用することができる。このツールは、画像エディタ要素１１２によって生成され、入力制御領域１１６内に表示される。
【００６３】
図３Ｃは、画像から鷲を削除したことを示している。最初は、画像内の以前鷲が見えていた部分に穴が残る。いくつかの実施構成では、穴を除去して画像を補完するために、予備穴埋め技術を適用することができる。ここでは、例えば、予備穴埋め技術により、以前に鷲の画像が占めていた領域内の枝葉のコンテンツは埋められているが、柵の上部及び下部の棒の部分、並びに中央の杭のほぼ全体が欠けている。これは、棒及び杭に関するセマンティック情報を、この時点では穴埋め技術の支援に利用可能できないことによって生じる。
【００６４】
しかしながら、図３Ｄでは、ユーザが、画像内の重要な特徴部をマークすることによってセマンティック情報を入力できるようにするツール３０６を起動している。ツール３０６は、ユーザがいくつかの別個のセマンティック特徴部をマークするためのオプション間で選択を行えるようにするメニュー３０８を含む。ここでは、これらのオプションが（赤色から黒色までの）色としてラベル表示され、ユーザが赤色のオプションを選択している。ツール３０６には、以下に限定されるわけではないが、線ツール、弧ツール、ブラシツール、領域選択ツール、及びこれらの組み合わせを含むあらゆる種類の入力コントロールを含めることができる。
【００６５】
図３Ｅでは、ユーザが、ツール３０６でマーキングを開始する。まず、ここでは鷲を削除したことによって生じた穴３１０が表示されている点に注目されたい。予備穴埋め技術を適用している間は、穴の形状及び場所に関する情報を保持することができる。例えば、穴３１０を示すことにより、ユーザが画像上に正しいマーキングを行うのを支援することができる。ここでは、ユーザがツール３０６を使用して線３１２を引いている。ユーザは、穴３１０に影響されない柵の支柱と基本的に一致するように線３１２を引く。ここでは、ユーザがメニュー内で「赤色」を選択したため、線３１２が赤色を使用して表示される。
【００６６】
図３Ｆは、ユーザが同じ又は異なるマーキングツールを使用して、画像内に１又はそれ以上の追加マークを入力できることを示している。ここでは、別の柵の支柱が線３１４でマークされ、鷲を削除した後に少ししか残っていなかった中央の柵の支柱が線３１６を使用してマークされている。線３１２、３１４、及び３１６は、同じ赤色でラベル表示されたマーキングツールで作成されたため全て赤色である。同様に、（この図では緑色でラベル表示された）別のマーキングツールを使用して、上部及び下部の棒を線３１８及び３２０でそれぞれマークする。このようにして、ユーザは、（柵及び棒などの）関心のある特徴部をマークし、これらが別々に取り扱われるように異なってラベル表示している。
【００６７】
次に、マークした領域に基づいて画像補完を実施する。特に、鷲によって生じた穴は、ユーザが与えた情報を使用して埋められる。ここでは、例えば、棒３１８が、内部領域部分３２２及び外部領域部分３２４を有する。すなわち、内部領域部分３２２は、線３１８の穴の中に存在する部分であり、外部領域部分３２４は、線３１８の穴の外に存在する部分である。内部領域部分３２２を埋めるための画像コンテンツ（例えば、これらの場所で穴を埋めるために適用できるパッチ）を探す場合、システムは、外部領域部分３２４及び同じツールでマークした他のいずれかの領域のみを参照する。ここでは、同じ緑色であるという理由で、この領域には線３２０が含まれる。対照的に、背景の枝葉及び柵の支柱などの、緑色ツールでマークされなかった画像の残り部分は、内部領域部分３２２を埋める際に使用されない。線３２０の穴を横切る部分も、同じ情報に基づいて埋められる。
【００６８】
同様に、線３１６は、赤色ツールでマークされていない領域は参照せずに、穴の外にある赤色ツールでマークされた部分に基づいて埋められる内部領域部分３２６を有する。ここでは、線３１２は完全に穴の外に存在し、従って穴埋めのための情報ソースとして機能する。対照的に、線３１６は、下端にある穴の外の残り部分を除き、その長さのほとんどが穴埋めの対象になる。
【００６９】
画像エディタツール１１０（図１）では、ツールからのマーキングが部分的に重なることができる。例えば、線３１８及び３２０は、線３１２と重っている。マークは異なるツールで作成されたものであるため、これらのそれぞれの領域の画像補完は別々に扱われて干渉しない。
【００７０】
図３Ｇには、結果として得られる画像３３０を示している。ここでは、画像エディタツール１１２（図１）が、ユーザのマーキングによって示される領域からの画像情報を描くことにより穴を補完している。上述したように、画像補完はパッチベースの最適化を使用して行うことができる。例えば、外部領域部分からのパッチを内部領域部分内でランダムに分散させ、次に良好なマッピング伝播及びランダムマッピングの反復段階を使用して、このマッピングを精密化することができる。その後、ユーザのマーキングのいずれにも含まれない残りの穴の部分が、同じパッチベースの最適化アルゴリズムを使用して埋められる。すなわち、穴全体にわたって同じ穴埋め技術を適用するが、マークされた領域に関しては、他の対応する（単複の）マークされた領域からのみ参照を行う。
【００７１】
図４には、別の画像修正の例を示している。ここでは、画像４００Ａにパエストゥムのヘラの第２神殿の写真を示している。画像には、埋めるべき穴は存在しないが、神殿はいくつかの構造を欠いており、ユーザは、システム（図１の画像エディタ要素１１０など）に、画像修正を行ってこの状況に対処してほしいと望む。
【００７２】
画像４００Ｂに示すように、ユーザは、１又はそれ以上のマーキングを行って、欠けた構造をいかにして作成すべきかに関するセマンティックを定義することができる。ここでは、ユーザが線４０２を作成して、登り蛇腹を復元するための画像情報をどこから取得すべきかを定義する。具体的には、線４０２を構造の無傷の部分に沿って描き、物理的構造内の素材が欠けている領域内に延ばす。従って、ユーザが無傷の構造部分をマークしたことにより、システムはこの部分のみを参照して、欠けている物理的構造部分を再現するための画像パッチを発見する。同様に、ユーザは、ペディメントの物理的対象内の欠けている部分に対応するマーク４０４、及び蛇腹の欠けた部分に対応する線４０６を作成する。
【００７３】
画像４００Ｃは、画像修正の結果を示している。図から分かるように、物理的構造が欠けていた場所に画像パッチを追加することにより、登り蛇腹、ペディメント、及び蛇腹が復元されている。ユーザが、これらの領域のためのそれぞれの情報ソースをセマンティックに定義したので、結果は自然かつもっともらしく見える。
【００７４】
図５Ａには、画像修正の別の例を示している。ここでは、初期画像５００が庭の写真であり、背景には、芝生、日時計の台座、及び庭内に入る入り口を有する石壁が存在する。この例では、ユーザが、台座及び入り口を削除して、自然な修正画像を生成したいと望む。
【００７５】
図５Ｂは、ユーザが台座及び入り口を削除して穴５０２が残ったところを示している。画像修正の目的は、画像内の別の場所でコンテンツを計画的に選択し、このコンテンツで穴５０２を埋めることである。図５Ｃは、ユーザが、１又はそれ以上のマークを入力して、修正処理のための検索空間を定義できることを示している。ここでは、ユーザがマーク５０４を入力して、穴の上部において連続すべき壁の縁の穴埋め処理を導いている。ユーザは、マーク５０６Ａを穴の中に、及び対応するマーク５０６Ｂを穴の外に入力する。マーク５０６Ｂは、マーク５０６Ａの領域のための画像コンテンツを選択する場所を示している。同様に、ユーザは、マーク５０８Ａを穴の中に、対応するマーク５０８Ｂを穴の外に入力する。マーク５０８Ｂは、マーク５０８Ａの領域のための画像コンテンツを選択する場所を示している。異なる色のマークによって示すように、ユーザは、それぞれのマークに異なるマーキングツールを使用する。
【００７６】
穴を埋めるためのコンテンツ選択は、ユーザがマークを入力することによって作成したセマンティック誘導に支援されるパッチベースの最適化アルゴリズムを使用して行われる。図５Ｄには、パッチベースの最適化アルゴリズム後に得られる修正画像５１０を示している。ここでは、マーク５０４、５０６Ａ、及び５０８Ａの全てに対応するコンテンツが、穴５０２だけでなくユーザがマークしなかった穴５０２の残りの部分にも充填されており、この残りの部分は、パッチベースの最適化アルゴリズムが、伝播フェーズ及びこの中のランダム検索フェーズに導かれるいずれかの画像領域を参照することによって埋めたものである。
【００７７】
図６には、修正画像を生成する方法例６００を示している。方法６００は、プロセッサが、例えばシステム１００（図１）内の有形コンピュータ可読媒体に記憶された命令を実行することにより実施することができる。１又はそれ以上の追加ステップを実施することができる。
【００７８】
ステップ６１０において、コンピュータシステム内に画像を表示する。例えば、ＧＵＩ１０４（図１）内に、画像２００、３０２Ａ、及び４００Ａのいずれか又は全てを表示することができる。画像は、目に見える特徴部を内部に有するコンテンツを含み、このコンテンツは、修正画像を生成する際に追加コンテンツが与えられるように定義された領域を有する。例えば、画像２００及び３０２Ａは、いくつかの画像コンテンツを削除することなどによって生じる、画像内に形成された穴を有することができる。別の例として、画像４００Ａなどのように、画像内に示される物理的対象から構造が欠けていることがある。
【００７９】
ステップ６２０において、特徴部の少なくとも一部を示す、画像上に配置すべきセマンティックマークを含む入力を受け取る。例えば、ユーザは、入力装置１１０を使用してツール３０６を使用し、マーク２０８、２１０、２１２、３１２〜３１６、３２０〜３２２、及び４０２〜４０６のいずれかを作成することができる。セマンティックマークは、領域の内側の内部領域部分及び領域の外側の外部領域部分を示す。例えば、マーク２０８、２１０、２１２、３１２〜３１６、３２０〜３２２、及び４０２〜４０６を、これらが、欠けた構造のそれぞれの穴又は領域の内部領域部分及び外部領域部分を示すように配置する。外部領域部分は、同じ画像内又は別の画像内に位置することができる。
【００８０】
ステップ６３０において、画像に適用するパッチベースの最適化アルゴリズムを使用して、領域のための追加コンテンツを決定する。例えば、画像エディタ要素１１２（図１）が、パッチベースの最適化アルゴリズムを適用することができる。パッチベースの最適化アルゴリズムは、内部領域部分のための追加コンテンツを、セマンティックマークが示していない画像の領域ではなく外部領域部分に基づいて識別する。パッチベースの最適化アルゴリズムは、領域の残りの部分のための追加コンテンツを、外部領域部分に制限されずに識別する。
【００８１】
ステップ６４０において、領域内に追加コンテンツを有する修正画像を記憶する。例えば、画像３３０又は４００Ｃ、或いは画像２００内で穴２０２が埋められた場合に得られる画像のいずれか又は全てをリポジトリ１０８（図１）に記憶することができる。
【００８２】
本明細書で説明した主題及び動作の実施形態は、本明細書に開示した構造及びこれらの構造的同等物を含むデジタル電子回路又はコンピュータソフトウェア、ファームウェア又はハードウェアにおいて、或いはこれらの１又はそれ以上の組み合わせにおいて実現することができる。本明細書で説明した主題の実施形態は、データ処理装置が実行するために、又はデータ処理装置の動作を制御するためにコンピュータ記憶媒体上で符号化された１又はそれ以上のコンピュータプログラム、すなわちコンピュータプログラム命令の１又はそれ以上のモジュールとして実現することができる。これとは別に、或いはこれに加えて、プログラム命令は、データ処理装置が実行するのに適した受信機装置へ送信するための情報を符号化するように生成された、機械により生成された電気的、光学的、又は電磁的信号などの人為的に生成された伝播信号上で符号化することができる。コンピュータ記憶媒体は、コンピュータ可読記憶装置、コンピュータ可読記憶基板、ランダム又はシリアルアクセスメモリアレイ又は装置、或いはこれらの１又はそれ以上の組み合わせとすることができ、或いはコンピュータ記憶媒体をこれらに含めることができる。さらに、コンピュータ記憶媒体は伝播信号ではないが、コンピュータ記憶媒体を、人為的に生成された伝播信号内で符号化されたプログラム命令の供給元又は供給先とすることができる。コンピュータ記憶媒体は、１又はそれ以上の別個の物理的構成要素又は媒体（複数のＣＤ、ディスク、又はその他の記憶装置など）とすることもでき、或いはコンピュータ記憶媒体をこれらに含めることもできる。
【００８３】
本明細書で説明した動作は、１又はそれ以上のコンピュータ可読記憶装置上に記憶された、又はその他の供給元から受け取ったデータに基づく、データ処理装置による動作として実施することができる。
【００８４】
「データ処理装置」という用語は、一例としてプログラマブルプロセッサ、コンピュータ、１チップシステム又は複数チップシステム、或いはこれらの組み合わせなどの、データを処理するための全ての種類の装置、機器、及び機械を含む。装置は、ＦＰＧＡ（フィールドプログラマブルゲートアレイ）又はＡＳＩＣ（特定用途向け集積回路）などの専用ロジック回路を含むことができる。装置はまた、ハードウェアに加え、プロセッサファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、クロスプラットフォームランタイム環境、バーチャルマシン、又はこれらの１又はそれ以上の組み合わせを構成するコードなどの、対象となるコンピュータプログラムのための実行環境を作り出すコードを含むこともできる。これらの装置及び実行環境により、ウェブサービス、分散コンピューティング、及びグリッドコンピューティングインフラストラクチャなどの様々な異なるコンピューティングモデルインフラストラクチャを実現することができる。
【００８５】
（プログラム、ソフトウェア、ソフトウェアアプリケーション、スクリプト、又はコードとしても知られている）コンピュータプログラムは、コンパイラ型言語又はインタープリタ型言語、宣言型言語又は手続き型言語などのいずれかの形のプログラミング言語で書くことができ、スタンドアローンプログラムとして、或いはモジュール、構成要素、サブルーチン、オブジェクト、又はコンピューティング環境での使用に適したその他のユニットなどとしてのいずれかの形で展開することができる。コンピュータプログラムは、必須ではないが、ファイルシステム内のファイルに対応することができる。プログラムは、他のプログラム又はデータを保持するファイル部分（マークアップ言語文書に記憶された１又はそれ以上のスクリプトなど）に、対象となるプログラムに特化した単一のファイルに、又は複数の協調ファイル（１又はそれ以上のモジュール、サブプログラム、又はコードの一部を記憶するファイルなど）に記憶することができる。コンピュータプログラムは、１つのコンピュータ上で、或いは１つの場所に配置された、又は複数の場所にわたって分散され通信ネットワークによって相互接続された複数のコンピュータ上で実行されるように展開することができる。
【００８６】
本明細書で説明した処理及び論理フローは、１又はそれ以上のコンピュータプログラムを実行し、入力データに基づいて動作して出力を生成することにより動作を実行する１又はそれ以上のプログラマブルプロセッサによって実行することができる。これらの処理及びロジックフローを、ＦＰＧＡ（フィールドプログラマブルゲートアレイ）又はＡＳＩＣ（特定用途向け集積回路）などの専用ロジック回路によって実行することもでき、装置をこれらの回路として実現することもできる。
【００８７】
一例として、コンピュータプログラムの実行に適したプロセッサとして、汎用及び専用の両方のマイクロプロセッサ、及びあらゆる種類のデジタルコンピュータのいずれか１つ又はそれ以上のプロセッサが挙げられる。一般的に、プロセッサは、読み取り専用メモリ又はランダムアクセスメモリ、或いはこれらの両方から命令及びデータを受け取る。コンピュータの必須要素は、命令に従って動作を実行するためのプロセッサ、及び命令及びデータを記憶するための１又はそれ以上のメモリ装置である。一般に、コンピュータは、磁気ディスク、光磁気ディスク、又は光ディスクなどの、データを記憶するための１又はそれ以上の大容量記憶装置も含み、或いはこれらからデータを受け取ること、これらにデータを転送すること、又はこれらの両方を行うように動作可能に結合される。しかしながら、コンピュータはこのような装置を有する必要はない。さらに、コンピュータを別の装置に、例えばごくわずかな例を挙げれば、携帯電話、携帯情報端末（ＰＤＡ）、携帯オーディオ又はビデオプレーヤ、ゲーム機、全地球測位システム（ＧＰＳ）受信機、又は（ユニバーサルシリアルバス（ＵＳＢ）、フラッシュドライブなどの）ポータブル記憶装置に組み込むことができる。一例として、コンピュータプログラム命令及びデータを記憶するのに適した装置として、ＥＰＲＯＭ、ＥＥＰＲＯＭ、及びフラッシュメモリ装置などの半導体メモリ装置、内部ハードディスク又は着脱可能ディスクなどの磁気ディスク、光磁気ディスク、並びにＣＤ−ＲＯＭディスク及びＤＶＤ−ＲＯＭディスクを含む全ての形の不揮発性メモリ、媒体、及びメモリ装置が挙げられる。プロセッサ及びメモリを専用ロジック回路で補い、又はこれに組み込むこともできる。
【００８８】
ユーザとのやりとりを可能にするために、本明細書で説明した主題の実施形態を、ユーザに情報を表示するためのＣＲＴ（陰極線管）又はＬＣＤ（液晶ディスプレイ）モニタなどのディスプレイ装置、ユーザがコンピュータに入力を与えられるようにするマウス又はトラックボールなどのポインティングデバイスを有するコンピュータ上で実現することができる。他の種類の装置を使用してユーザとのやりとりを可能にすることもでき、例えば、ユーザに提供されるフィードバックを、視覚フィードバック、聴覚フィードバック又は触覚フィードバックなどのいずれかの形の知覚フィードバックとし、ユーザからの入力を、音響入力、発話入力、又は触覚入力などのいずれかの形で受け取ることができる。また、コンピュータは、ユーザが使用する装置との間で文書を送受信することにより、例えば、ユーザのクライアント装置上のウェブブラウザから受け取った要求に応じてこのウェブブラウザへウェブページを送信することにより、ユーザとやりとりすることができる。
【００８９】
本明細書で説明した主題の実施形態は、データサーバなどとしてのバックエンド構成要素を含む、又はアプリケーションサーバなどのミドルウェア構成要素を含む、又はユーザが本明細書で説明した主題の実施構成とやりとりできるようにするグラフィカルユーザインターフェイス又はウェブブラウザを有するクライアントコンピュータなどのフロントエンド構成要素を含む、或いは１又はそれ以上のこのようなバックエンド構成要素、ミドルウェア構成要素、又はフロントエンド構成要素のいずれかの組み合わせを含むコンピュータシステム内で実現することができる。システムの構成要素は、いずれかの形又は媒体の通信ネットワークなどのデジタルデータ通信によって相互接続することができる。通信ネットワークの例として、ローカルエリアネットワーク（「ＬＡＮ」）及び広域ネットワーク（「ＷＡＮ」）、ネットワーク間ネットワーク（インターネットなど）、並びにピアツーピアネットワーク（アドホックピアツーピアネットワークなど）が挙げられる。
【００９０】
コンピュータシステムは、クライアント及びサーバを含むことができる。一般に、クライアントとサーバは互いに離れており、通常は通信ネットワークを介してやりとりする。このクライアントとサーバの関係は、それぞれのコンピュータ上で実行されて互いにクライアント−サーバの関係を有するコンピュータプログラムによって生じる。いくつかの実施形態では、（例えば、クライアント装置とやりとりしているユーザにデータを表示し、ユーザからユーザ入力を受け取るために）サーバがクライアント装置へ（ＨＴＭＬページなどの）データを送信する。サーバでは、クライアント装置で生成された（ユーザとのやりとりの結果などの）データをクライアント装置から受け取ることができる。
【００９１】
本明細書は、多くの特定の実施構成の詳細を含むが、これらを、本発明又は特許請求できるものの範囲を限定するものと解釈すべきではなく、本発明の特定の実施形態に固有の特徴を説明するものと解釈すべきである。本明細書において異なる実施形態を背景として説明したいくつかの特徴を、単一の実施形態において組み合わせて実現することもできる。逆に、単一の実施形態を背景として説明した様々な特徴を、複数の実施形態において別個に、又はいずれかの好適な部分を組み合わせて実現することもできる。さらに、上記では特徴を特定の組み合わせで機能するものとして説明し、最初はこのように特許請求している場合さえもあるが、場合によっては、特許請求する組み合わせから生じる１又はそれ以上の特徴をこれらの組み合わせから削除することができ、特許請求する組み合わせを、部分的組み合わせ又は部分的組み合わせの変形に向けることができる。
【００９２】
同様に図面には動作を特定の順序で示しているが、このことを、望ましい結果を達成するにはこのような動作を図示の特定の順序又は順番で実施し、又は図示の動作を全て実施する必要があると理解すべきではない。いくつかの状況では、マルチタスク及び並列処理が有利となり得る。さらに、上述した実施形態において様々なシステム構成要素を分離していても、このような分離が全ての実施形態において必要であると理解すべきではなく、説明したプログラム構成要素及びシステムを単一のソフトウェア製品に一般的に統合し、又は複数のソフトウェア製品にパッケージ化できると理解されたい。
【００９３】
以上、本発明の特定の実施形態について説明した。他の実施形態は、以下の特許請求の範囲に含まれる。場合によっては、特許請求の範囲に記載した機能を異なる順序で実行して、なおも望ましい結果を得ることができる。また、望ましい結果を達成するために、添付の図に示した処理を必ずしも図示の特定の順序又は順番で行う必要はない。いくつかの実施構成では、マルチタスク及び並列処理が有利となり得る。
【符号の説明】
【００９４】
３１２  線
３１４  線
３１６  線
３１８  線
３２０  線
３２２  内側領域部分
３２４  外側領域部分
【図１】
2012526479.tif 000003
【図２】
2012526479.tif 000004
【図３Ａ】
2012526479.tif 000005
【図３Ｂ】
2012526479.tif 000006
【図３Ｃ】
2012526479.tif 000007
【図３Ｄ】
2012526479.tif 000008
【図３Ｅ】
2012526479.tif 000009
【図３Ｆ】
2012526479.tif 000010
【図３Ｇ】
2012526479.tif 000011
【図４】
2012526479.tif 000012
【図５Ａ】
2012526479.tif 000013
【図５Ｂ】
2012526479.tif 000014
【図５Ｃ】
2012526479.tif 000015
【図５Ｄ】
2012526479.tif 000016
【図６】
2012526479.tif 000017
【国際調査報告】
2012526479.tif 000018
2012526479.tif 000019
2012526479.tif 000020