JP5111095B2 - コンテンツを意識した画像の再構成方法 - Google Patents

Description

本発明は、包括的には画像処理に関し、特に画像の再構成に関する。

印刷装置及び表示装置の多様性及び多機能性は、マルチメディアコンテンツのデザイナーにレンダリング及び閲覧に対する要求を課す。例えば、デザイナーは、ウェブコンテンツ用に様々な代案を提供すると共に、選択メニューに多く見られる画像のごく小さな「サムプリント」、小さくて低解像度の携帯電話画面、少し大きなＰＤＡ画面から、大型で高解像度のワイドフラットパネルディスプレイ、及びプロジェクタースクリーンまで多岐にわたる様々なレンダリングアプリケーション及びレンダリング装置用に様々なレイアウトを設計しなければならない。画像を最初に意図したレンダリングアプリケーション及びレンダリング装置とは異なるレンダリングアプリケーション及びレンダリング装置に適合させることを画像の再構成と呼ぶ。

従来の画像の再構成は通常スケーリング及びクロッピングを伴う。画像のスケーリングは、画像のコンテンツを無視し、通常は均一にしか適用することができないため不十分である。スケーリングはまた、画像のアスペクト比を変更する必要がある時には、視覚的な歪みを生じるため良好に機能しない。クロッピングは、画像の周辺部からしかピクセルを削除できないため限定される。より効果的なサイズ変更は、全体的な画像のコンテンツを出力装置の幾何学的制約と共に考慮することでのみ達成される。

画像のサイズ変更は代替的な画像の再構成ツールである。画像のサイズ変更は、ソース画像をターゲットディスプレイのサイズに均一にサイズ変更することで機能する。画像のサイズ変更中、画像コンテンツ中の重要な特徴は維持しながら画像のサイズを変更したいという要求がある。これはトップダウン法又はボトムダウン法によって行うことができる。トップダウン法は、顔検出器等のツールを用いて画像中の重要な領域を検出し、ボトムアップ法は、視覚的顕著性による方法に依存してソース画像の視覚的顕著性マップを構築する。顕著性マップが構築されたら、クロッピングを用いて画像の最も重要な領域を表示することができる。

一方法は、顕著性マップ又は顔検出器の出力に基づいてサムネイル画像を自動生成する（Suh他著「自動的なサムネイルクロッピング及びその効果（Automatic thumbnail cropping and its effectiveness）」（UIST '03: Proceedings of the 16th annual ACM symposium on User interface software and technology, ACM Press, New York, NY, USA, 95-104, 2003））。ソース画像がクロッピングされて画像中の最も顕著な領域が取り込まれる。別の方法は画像をモバイル装置に適合させる（Chen他著「画像を小型ディスプレイに適合させるための視覚的な注意モデル（A visual attention model for adapting images on small displays）」（Multimedia Systems 9, 4, 353-364, 2003））。この方法では、画像中の最も重要な領域が自動的に検出されてモバイル装置に送信される。

別の方法は合成規則に加えて目の追跡を用いて画像を知的にクロッピングする（Santella他著「半自動写真クロッピングのための注視ベースの対話（Gaze-based interaction for semiautomatic photo cropping）」（ACM Human Factors in Computing Systems (CHI), 711-780, 2006）（参照により本明細書中に援用される））。この方法では、ユーザが画像を見て、その間に目の動きが記録される。この記録は、重要な画像コンテンツを識別するために用いられ、その後、任意のサイズ又はアスペクト比のクロップを自動生成することができる。

上記は全て、従来の画像のサイズ変更操作及びクロッピング操作に依存して画像を再構成する。

別の方法は、コンテンツとテンプレートとの間の明確な分離を維持する適応的な格子ベースの文書レイアウトを用いる（Jacobs他著「適応的な格子ベースの文書レイアウト（Adaptive grid-based document layout）」（Proceedings of ACM SIGGRAPH, 838-847, 2003））。デザイナーがいくつかの考え得るテンプレートを構築する。コンテンツが表示される時、最も適切なテンプレートが用いられる。

画像のサイズ変更と画像のクロッピングとの折衷案は、非線形のデータに依存するスケーリングを画像の再構成に用いることである（Liu他著「魚眼ビューワーピングを用いる自動的な画像の再構成（Automatic Image Retargeting with Fisheye-View Warping）」（ACM UIST, 153-162, 2005））。Liu他は、低レベルの顕著性及び高レベルの物体認識等の画像情報を用いてソース画像中の重要な領域を見付ける。次に、非線形画像ワーピング関数を適用して、周囲の文脈を保持しながら画像の重要な側面を強調する。

別の方法は、自動的で非写実的な方法を大きな画像の小型ディスプレイへの再構成に用いる（Setlur他著「自動的な画像の再構成（Automatic Image Retargeting）」（Mobile and Ubiquitous Multimedia (MUM), ACM Press, 2005））。Setlur他は、画像を背景層と前景物体とに分解する。この再構成方法は、画像を複数の領域に分割し、重要な領域を識別し、それらの領域を削除し、結果として生じるギャップを埋め、残りの画像をサイズ変更し、重要な領域を再度挿入する。

別の方法は、ユーザ指定の領域を保存しながら画像を新たな形状にワーピングする、特徴を意識したテクスチャマッピングを用いる（Gal他著「特徴を意識したテクスチャ化（Feature aware texturing）」（Eurographics Symposium on Rendering, 2006））。Gal他は、画像中の類似性制約への適応に適したラプラス編集技法の特定の公式を解く。しかし、局所的制約が画像全体に伝播して全ての制約に一度に適応し、時として失敗する場合がある。

別の方法は、いくつかの画像から新たなフォトモンタージュを合成する（Agarwala他著「対話型デジタルフォトモンタージュ（Interactive digital photomontage）」（ACM Trans. Graph. 23, 3, 294-302, 2004））。ユーザは、様々な入力画像からＲＯＩを選択し、次にそれらを出力画像に合成する。別の方法は、ドラッグアンドドロップによるペーストを用いる（Jia他著「ドラッグアンドドロップによるペースト（Drag-and-drop pasting）」（Proceedings of SIGGRAPH, 2006））。Jia他は、ソース画像とターゲット画像との間の最適な境界を求める。別の方法は画像の集合からコラージュ画像を生成する（Rother他著「オートコラージュ（Autocollage）」（Proceedings of SIGGRAPH 2006））。これらの合成方法はいずれも、画像の再構成に対処していない。

別の方法はマッティングと合成とを同時に解決する（Wang他著「同時でのマッティング及び合成（Simultaneous Matting and Compositing）」（Microsoft Research Technical Report, MSR-TR-2006-63 (May) 2006））。Wang他は、ユーザが前景物体のサイズをスケーリングし、この物体を元の背景上にペーストして戻すことを可能にする。

別の方法はコスト関数に基づき画像を共に「縫い合わせる」（Zomet他著「偽エッジの最小化によるシームレスな画像の縫い合わせ（Seamless image stitching by minimizing false edges）」（IEEE Transactions on Image Processing 15, 4, 969-977, 2005））。Zomet他は、縫い合わせ画像の勾配と入力画像の勾配との間のＬ_１誤差ノルムを最小化する。

画像の外観を変えることは、コンテンツの基本的な概念は保存しながら入力画像とは異なるテクスチャを有する出力画像を生成することを目標とするテクスチャ合成の分野で広く記載されてきた（Freeman他に２００５年７月１９日付で発行された米国特許第６，９１９，９０３号「テクスチャの合成及びピクセル画像への転送（Texture synthesis and transfer for pixel images）」）。この方法は画像の再構成を考慮していない。

別の方法は物体の削除を行う（Bertalmio他著「構造及びテクスチャ画像の同時修復（Simultaneous structure and texture image inpainting）」（Proceedings IEEE Conference on Computer Vision and Pattern Recognition, 707-714, 2000））。Bertalmio他は、画像の修復を用いて、情報を境界から内部へ、絵画の修復を模してスムーズに伝播させる。

パッチベースの方法、手法は、自動ガイダンスを用いて合成の順序付けを決める（「断片に基づく画像補完（Fragment-based image completion）」（Proceedings of ACM SIGGRAPH, 303-312, 2003）及びCriminisi他著「実例ベースの修復による物体の削除（Object removal by exemplar-based inpainting）」（IEEE Conference on Computer Vision and Pattern Recognition, 417-424, 2003））。

別の対話型の方法は、強力な（strong）視覚構造が欠損している画像の修復を、ユーザ指定の曲線に沿って構造を伝播させることにより提供する（Sun他著「構造伝播による画像補完（Image completion with structure propagation）」（Proceedings of ACM SIGGRAPH, 2005））。

従って、コンテンツを意識した画像の再構成のためのシームの適用を提供することが望まれる。

本発明は、幾何学的制約及び画像コンテンツ制約を用いる、コンテンツを意識した画像の再構成方法を提供する。本発明は、コンテンツを意識した画像の再構成をサポートする最小エネルギーシームの適用を提供する。シームの適用は、長方形（又は正方形）形状を保存しながら画像のサイズを小さく又は大きくすることができる。

本明細書中で定義する場合、シーム（seam）とは、上端から下端へ、又は左端から右端へ延びる画像中の最適なｎ連結のピクセル集合であり、最適さは画像のエネルギーにより定義される。１つのシームは１ピクセル幅である。

シームを画像に適用することによって、画像のサイズを変更することができる。適用は、シームを削除又は挿入して、例えば画像のアスペクト比を例えば４：３から１６：９に変更することであり得る。好ましい一実施の形態において、シームは８連結である。

シーム操作を両方向に適用することにより、ソース画像をより小さな又はより大きなディスプレイ用に再構成することができる。シームの選択及び順序が、エネルギー関数により定義される画像のコンテンツを保存する。

シームの適用は、画像コンテンツの引き伸ばし及び物体の削除にも用いることができる。本発明は、画像のエネルギーを定義するための様々な視覚的顕著性の測度を提供し、再構成プロセスを案内するためにユーザ入力を含めることもできる。シームの順序をメモリに記憶することにより、マルチサイズ画像を生成して画像の任意のサイズへのリアルタイム再構成をサポートすることができる。

本発明は、コンテンツを意識した画像の再構成のためのシームの適用を提供することができる。

図１Ａに示すように、本発明の実施形態は、ソース画像１００からターゲット画像１０９へのコンテンツを認識した再構成を行う方法を提供する。再構成は、ターゲット画像において、長方形形状（矩形形状）を保存しながら、ソース画像のサイズを変更することができる。なお、ここで、長方形形状（矩形形状）とは、正方形形状を含む。

本方法への入力はソース画像１００である。このソース画像から、エネルギー関数１１１を用いてエネルギー画像１１２を生成する。最小化関数１２１を用いて、１つ又は複数の最小エネルギーシーム１２２を求める（１２０）。次に各シーム１２２を、ソース画像１００に１回又は複数回適用して（１３０）、ターゲット画像１０９を生成することができる。シーム１２２を適用する（１３０）最適な順序１３２は目的関数１３１に基づき得る。

シーム１２２の適用は、画像の長方形形状を保存しながら、画像のサイズを大きく又は小さくする、アスペクト比を変更する、コンテンツすなわち選択した物体を削除する、又はソース画像のコンテンツを引き伸ばすことができる。この再構成は、ピクセル強度領域又は勾配領域において行うことができる。

本発明の実施形態は、画像の様々な部分のピクセルを徐々に削除又は挿入することによって画像のサイズを変更することができるシームの適用を用いる。この再構成は、エネルギー関数１１１を用いてソース画像のピクセルの「重要度」を定義する。この再構成は、勾配の大きさ、エントロピー、視覚的顕著性、視線移動、及び物体検出（例えば顔、歩行者）等のいくつかの種類のエネルギー関数をサポートすることができる。

シームは、画像を上端から下端へ、又は左端から右端へ横切る１ピクセル幅のピクセル集合として定義される。シームを連続的に削除又は挿入することにより、画像のサイズの両方向での縮小及び引き伸ばしを行うことができる。画像の縮小の場合、シームの選択により、高エネルギーピクセルを保持しながら低エネルギーピクセルの方を多く削除することで基本的な画像構造が確実に保存される。

コンテンツの引き伸ばしの場合、シームの挿入順序１３２により、元の画像コンテンツと人工的に挿入されるピクセルとの間のバランスが保証される。これは事実上、コンテンツを意識した形で画像の再構成を定義する。シームの削除及び挿入を用いて、アスペクト比の変更、画像の再構成、画像コンテンツの引き伸ばし、及び物体の削除を行うことができる。

さらに、シームの削除及び挿入の適用順序１３２を記憶し、シームを縦方向及び横方向に注意深くインタリーブすることによって、マルチサイズ画像を規定することができる。このような画像は、コンテンツを意識した形でサイズを連続的に変化させることができる。デザイナーがマルチサイズ画像を一度製作しておくと、クライアントアプリケーションにおいて、必要とされるサイズに応じて、画像をリアルタイムでサイズ変更して、正確なレイアウト又はディスプレイに合わせることができる。

本発明の方法は、エネルギー画像１１２を用いてピクセルを気付かれない形で削除又は挿入する。特に、本発明では、ピクセルが周囲のピクセルに溶け込んでいる（blendする）場所でのみ、当該ピクセルを削除又は挿入する。近傍ピクセルに類似する又は溶け込むピクセルは低エネルギーを有すると呼び、近傍ピクセルに類似していないピクセルは高エネルギーを有すると呼ぶこととする。したがって、本発明では、次式のエネルギー関数１１１に従ってソース画像１００からエネルギー画像１１２を生成する。

ここで、Ｉ（ｘ，ｙ）は特定のピクセルである。上述したように、他のエネルギー関数も用いることができる。

エネルギー関数が与えられた状態で、基本的な長方形（又は正方形）形状を保存しながらソース画像のサイズを変更するにはいくつかの方法がある。最適な戦略は、ターゲット画像のエネルギーをできるだけ多く最大化する。すなわち、本発明では、エネルギーのより高いピクセルを保持し、エネルギーの最も低いピクセルから昇順に削除する。しかしこれは、ピクセルの各行又は各列から異なる数のピクセルを削除する場合があるため、画像の形状を変える可能性がある。

画像を歪ませたくない場合、各行から同数の低エネルギーピクセルを削除することができる。これにより、画像の形状が保存されるが、可視のジグザグ効果が生じて画像のコンテンツは破壊される。画像の形状及び視覚的コヒーレンスの両方を保存するには、クロッピングを用いることができる。すなわち、エネルギーの最も高いターゲット画像のサイズのサブウインドウをソース画像中に位置付ける。ピクセルの削除とクロッピングとの中間のような別の考え得る戦略は、エネルギーの最も低いピクセル列全体を削除することである。しかし、これもなお目障りなアーティファクトを生じる。

したがって、本発明では、クロッピング又は列の削除よりも制約が少ないにもかかわらず、１ピクセルの削除よりも良好に画像のコンテンツ及び形状を保存することができる方法を用いる。これが本発明のシームの適用（１３０）及びシーム１２２の定義につながる。

図１Ｂ及び図１Ｅに示すように、ソース画像１００はｎ×ｍピクセルを有する。すなわち、画像は、ｎ及びｍでそれぞれインデックス付けされる縦方向及び横方向の２つの寸法を有する。

シームは、ソース画像Ｉ１００を貫く１ピクセル幅のピクセル集合である。シームは、画像の一端から向かいの端まで延びることができる。これらの端は、上端及び下端、又は左端及び右端であり得る。シームは、それが方向付けられた向きの特定の寸法（dimension）に沿って、各インデックスにつき正確に１ピクセルを有する。例えば、向きの寸法が縦方向である場合、縦方向のシームは正確にｎピクセルを有する。

縦方向のシーム１０１は次のように表される。

ここで、ｘはマッピングｘ：［１，・・・，ｎ］→［１，・・・，ｍ］である。すなわち、縦方向のシーム１０１は、画像１００のｎ行のピクセルの各行につきピクセルを１つだけ含む上端から下端までの８連結の経路である。

同様に、横方向のシーム１０２は次のように表される。

ここで、ｙはマッピングｙ：［１，・・・，ｍ］→［１，・・・，ｎ］である。すなわち、横方向のシーム１０２は、画像１００のｍ列のピクセルの各列につきピクセルを１つだけ含む左端から右端までの８連結の経路である。

シームｓ、例えば縦方向のシーム｛ｓ_ｉ｝１０１のピクセルは次のように表される。

なお、画像から行又は列全体を削除する場合と同様に、画像からシームのピクセルを削除しても局所的な効果しかない。画像の全ピクセルは左（又は上）にシフトされて、削除されたピクセルが補償される。視覚的な影響があっても、シームに沿ってのみ見られるだけであり、残りの画像はそのままの状態で残る。削除又は挿入されたピクセルのエネルギーが低い場合、視覚的影響は無視できる程度となる。

画像が２４０×３２０画像、すなわち、２４０行及び３２０列を有する場合、４：３のアスペクト比を有する。４：３画像から１６：９画像へのアスペクト比の変更は、縦方向のシームを挿入することによって、又は横方向のシームを削除することによって行うことができる。１０６本の縦方向のシームを挿入することにより、２４０×４２６画像が得られる。６０行を削除することにより、１８０×３２０画像が得られる。いずれも、１６：９のアスペクト比を有する画像となる。前者の方法は、ピクセルを追加するだけで、元のピクセルは削除しないという利点を有する。

｜ｘ（ｉ）−ｘ（ｉ−１）｜≦１という制約を｜ｘ（ｉ）−ｘ（Ｉ−１）｜≦ｋに置き換え、ｋ＝０の場合の列（若しくは行）全体又はピース毎の連結ピクセル（一定縮尺でない図１Ｄを参照）、又は１≦ｋ≦ｍの任意の値に関して完全な又は部分的に切断されたピクセル（図１Ｅを参照）を得ることができる。

エネルギー関数ｅ（Ｉ）が与えられると、シームのエネルギーを次のように定義することができる。

以下の最小化関数１２１を用いて最適な最小エネルギーシームｓ^＊１２２を見付ける（それの位置を正確に求める（locate））。

最適な最小エネルギーシームｓ^＊１２２は動的計画法を用いて見付けることができる。第１のステップは、画像のピクセルを１回に１行ずつトラバースして、各エントリの全ての考え得るシームの累積最小エネルギーＭを次のように求める。

このプロセスの最後に、Ｍの最後の行の最小値は、最小連結の縦方向のシームの端を示す。したがって、第２のステップでは、行Ｍのこの最小値から後戻りして最適シーム１２２の経路を見付ける。最適な最小エネルギーの横方向のシームも同様に見付けることができる。

図１Ｆは、エネルギー画像１１２を強度勾配の大きさに関して示す。図１Ｇ及び図１Ｈは、シーム１２２を求める（１２０）ために用いられる対応する縦方向及び横方向の経路マップを示す。

エネルギー保存測度
本発明のコンテンツを意識した再構成の様々な戦略の効果を評価するために、ソース画像１００の全てのピクセルの平均エネルギーを再構成中に次のように求める。

ピクセルをランダムに削除した場合、平均は変わらないが、コンテンツを意識した再構成では、低エネルギーピクセルを削除し高エネルギーピクセルを保持するため、平均が増加する。

使用できる画像重要度測度にはいくつかのよく知られたもの、例えば、Ｌ_１ノルム、勾配のＬ_２ノルム、顕著性測度、及びハリスのコーナー測度がある。

離散的な画像のサイズ変更
アスペクト比の変更
ソース画像Ｉのアスペクト比をｎ×ｍからｎ×ｍ’に変更する。ここで、ｍ−ｍ’＝ｃ（或る定数）である。これは、画像Ｉからｃ本の縦方向のシームを連続的に削除することによって達成することができる。従来のスケーリングとは対照的に、本発明によるシームの適用（１３０）は、エネルギー関数１１１により定義される画像の重要な部分を変えない。事実上、これは画像の不均一でコンテンツを意識したサイズ変更を生じる。図２Ａはソース画像を示す。図２Ｂは、本発明の実施形態によるターゲット画像を示す。図２Ｃ及び図２Ｄは、従来のスケーリング及びクロッピングを示す。

図３Ａ及び図３Ｂに示すように、ｎ×ｍからｎ×ｍ’への同じアスペクト比補正を、行数をｍ／ｍ’倍に増やすことによっても達成することができる。この手法の付加価値は、画像からいかなるピクセルも削除しないことである。画像サイズを大きくするための本発明の戦略を以下に詳述する。

最適なシーム順序を用いる再構成
画像の再構成は、アスペクト比の変更をｎ×ｍのサイズの画像Ｉがｎ’×ｍ’のサイズに再構成されるように一般化する。ｍ’＜ｍ及びｎ’＜ｎであると仮定する。ピクセルの削除の最適な順序１３２は、以下の目的関数１３１の最適化である。

ここで、ｋ＝ｒ＋ｃ，ｒ＝（ｍ−ｍ’），ｃ＝（ｎ−ｎ’）であり、α_ｉは、ステップｉにおいて横方向又は縦方向のどちらのシームを削除するかを判定するパラメータである。

所望のターゲット画像サイズｎ’×ｍ’毎に、横方向及び縦方向のシームの適用（１３０）の最適な順序のコストを指定する輸送マップ（transport map）Ｔを用いて最適な順序を求める。

すなわち、輸送マップＴのエントリＴ（ｒ，ｃ）は、ｎ−ｒ×ｍ−ｃのサイズの画像を得るために必要な最小コストを格納する。動的計画法を用いてＴを求める。

Ｔ（０，０）＝０から開始してエントリ（ｒ，ｃ）毎に求め、ｎ−ｒ×ｍ−ｃ＋１のサイズの画像から横方向のシームを削除するか、又はｎ−ｒ＋１×ｍ−ｃのサイズの画像から縦方向のシームを削除するかの２つのオプションのうち最良の方を選択する。

ここで、Ｉ_{ｎ−ｒ×ｍ−ｃ}はｎ−ｒ×ｍ−ｃのサイズの画像を示し、Ｅ（ｓ^ｘ（Ｉ））及びＥ（ｓ^ｙ（Ｉ））はそれぞれのシームの適用のコストである。

輸送マップＴ及びターゲットサイズｎ’×ｍ’（ここで、ｎ’＝ｎ−ｒ及びｍ’＝ｍ−ｃ）が与えられると、Ｔ（ｒ，ｃ）から後戻りして、Ｔ（０，０）に到達するまで現在のエントリの上近傍及び左近傍の最小値へ連続的に移動することにより最適な経路を求めることができる。左近傍の選択は縦方向のシームの適用に対応し、上近傍の選択は横方向のシームの適用に対応する。

画像サイズを大きくする
縦方向のシーム及び横方向のシームを削除するプロセスは時間発展過程として表すことができる。本発明では、Ｉ^（ｔ）を、ソース画像Ｉからｔ本のシームを削除した後に生成されるより小さな画像として示す。

画像のサイズを大きくするには、この時間発展の「逆」を近似し、画像に新たな「人工」シームを挿入する。したがって、ソース画像Ｉのサイズを１だけ大きくするには、画像ソースＩ中の最適な縦方向（横方向）シームｓを求め、ピクセルをその左近傍及び右近傍、又は縦方向シームの場合には上近傍及び下近傍と平均化することによってシームｓのピクセルを複製する。

時間発展の表記法を用いて、結果として得られるターゲット画像をＩ^（−１）として示す。このプロセスを繰り返すと、同一シームを選択することによって伸長アーティファクトが生じる。効果的に大きくするために、元の画像コンテンツと挿入ピクセルとの間でバランスを取ることが重要である。

したがって、画像のサイズをｋだけ大きくするには、削除用の最初のｋ本のシームを求め、これらのシームを順番に複製して画像Ｉ^（−ｋ）を得る。これは、時間を遡ってトラバースして、さもなければシームの削除により削除されていたであろうピクセルをより大きな画像から回復するプロセスと見なすことができる。

例えば５０％よりも大きく過剰に画像サイズを大きくする場合にコンテンツを意識した形であり続けるために、プロセスをいくつかのステップに分ける。各ステップにおいて、前のステップの画像のサイズの数分の１以上引き伸ばさず、実質的に重要なコンテンツを伸長から保護する。

コンテンツの引き伸ばし
画像のサイズを大きくする代わりに、本発明による画像の再構成は、画像のサイズ及び形状を保存しながら、画像のコンテンツを拡大する又は引き伸ばすために用いることができる。これは、シームの削除と標準的な画像スケーリングとを組み合わせることにより達成することができる。画像のコンテンツをできる限り保存するために、まず、従来の画像スケーリングを用いて画像のサイズを大きくする。次に、より大きな画像にシームの削除を適用して、画像を元のサイズに縮小する（図４Ａ及び図４Ｂを参照）。なお、削除されたピクセルは事実上ソース画像のサブピクセルとなる。コンテンツの引き延ばしは事実上、データ駆動型ズームインに類似している。ズームアウト又はコンテンツの縮小も同様に行うことができる。

勾配領域におけるシームの削除
ソース画像から複数のシームを削除すると依然としてターゲット画像中に目立つ視覚的アーティファクトが生じる場合がある。これを克服するために、シームの削除をポアソンの再構成と組み合わせることができる（Tumblin他に２００６年５月２日付で発行された米国特許第７，０３８，１８５号「勾配画像を直接生成するカメラ（Camera for directly generating a gradient image）」を参照）。

具体的には、エネルギー画像１１２を上述のように求め、ただし、ソース画像からシームを削除する代わりに、勾配領域で作業を行い、ソース画像のｘ及びｙの導関数（勾配）からシームを削除する。このプロセスの最後に、ポアソンソルバを用いてターゲット画像１０９を再構成する。

物体の削除
ソース画像から物体を削除することもできる。物体に関連するピクセルを印付けし、次に、全ての印付けされたピクセルが無くなるまで画像からシームを削除する。ターゲット削除領域のピクセル数に関して縦方向又は横方向の寸法のうち小さい方を自動的に判定し、それに従って縦方向又は横方向の削除を行うことができる（図５Ａ及び図５Ｂを参照）。図６Ａ及び図６Ｂに示す例では、物体（１つの靴）が削除される。物体の削除後、画像は元のサイズに大きくされる。なお、この例は従来の修復又はテクスチャ合成では達成することが難しいであろう。

マルチサイズ画像
これまでは、ターゲット画像１０９のサイズが既知であるものと仮定してきた。しかし、これは場合によっては可能でないかもしれない。例えば、ウェブページに埋め込まれた画像を考える。ページデザイナーはウェブページが最終的に表示されるサイズを事前に知らない。したがって、デザイナーは単一のターゲット画像を生成することができない。異なるシナリオでは、ユーザは、様々なサイズのターゲット画像を探求（explore）して、最も適したサイズを選択したいかもしれない。

シームの適用はピクセル数において線形であり、したがって画像の再構成は、削除又は挿入されるシーム数において線形である。平均で、４００×５００のサイズの画像を１００×１００に２秒で再構成することができる。しかし、複数の異なるサイズの画像に関して数十又は数百のシームを決めることは、リアルタイムで行う場合には困難なタスクである。

この問題に対処するため、本発明は、（ｍ×ｎ）のサイズのソース画像１００に関して１×１からｍ×ｎまで、さらに大きくはＮ’×Ｍ’まで（Ｎ’＞ｎ，Ｍ’＞ｍの場合）の全範囲の再構成サイズを符号化するマルチサイズ画像の表現を提供する。この情報は、リアルタイムでの連続的な画像の再構成を可能にする。異なる視点から、これは、シームの適用の時間発展の暗黙的なプロセスの明示的な表現の記憶と見なすことができる。

まず、図７Ａに示すソース画像の幅を変更する場合を考える。ピクセル毎にそのピクセルを削除したシームのインデックスを符号化するｎ×ｍのサイズのインデックスマップＶを定義する。すなわち、Ｖ（ｉ，ｊ）＝ｔは、縦方向のｔ番目のシームの削除によりピクセル（ｉ，ｊ）が削除されることを意味する（図７Ｂを参照）。シームの削除の順序又はインデックスは暗いものから明るいものの順で示される。幅ｍ’の画像を得るには、行毎に、シームインデックスがｍ−ｍ’以上の全てのピクセルを集めるだけでよい。

例えば、１番目のシームにより削除されるピクセルにはインデックス番号１が与えられ、インデックス番号が２０のシームにより削除されるピクセルよりも重要でないと見なされる。

この表現は、画像の引き伸ばし及び画像の縮小をサポートする。例えば、Ｍ’＞ｍのサイズまでの画像の引き伸ばしをサポートしたい場合、上述のようにｎ×Ｍ’のサイズまでのシームの挿入を用いて画像を引き伸ばす。

しかし、ｋ番目のシームのピクセルを２つの近傍シームのピクセルと平均化する代わりに、本発明では、そのシーム内のソース画像ピクセルを修正せずに、画像に新たなピクセルをｋ番目のシームとその左（又は右）のピクセル近傍との平均として挿入する。挿入されたシームには−１から始まる負のインデックスが与えられる。

ソース画像をｋ（ｍ＜ｋ＜Ｍ’）だけ引き伸ばすには、引き伸ばし画像からシームインデックスが（ｍ−（ｍ＋ｋ））＝−ｋよりも大きい全てのピクセルを集めるという全く同じ手順を用いて、ｍ−（−ｋ）＝ｍ＋ｋのサイズの画像を得る。

画像の高さの引き伸ばし又は縮小のために横方向のインデックスマップＨを求めることも同様に達成される（図７Ｃを参照）。しかし、インデックスマップＨ及びＶを個別に求めながらの両画像寸法におけるサイズ変更のサポートは、問題を生じる可能性がある。これは、横方向のシーム及び縦方向のシームが２箇所以上で交差する可能性があり（図７Ｂ及び図７Ｃを参照）、一方向でのシームの削除が他方向のインデックスマップに影響を及ぼす恐れがあるためである。これを回避する１つの方法は、一方向でのシームの削除を可能にし、他方向では縮退シーム（degenerate seams）、すなわち行又は列を用いることである。

一貫したインデックスマップの構築
横方向のインデックスマップＨ及び縦方向のインデックスマップＶをマルチサイズ画像に対して個別に求めることは機能しない。原因を見るために、定義から始める。全ての横方向のシームが全ての縦方向のシームインデックスと交差し、全ての縦方向のシームが全ての横方向のシームインデックスと交差する場合、マップＨ及びＶは一貫している。

一貫性は、任意の寸法のシームの削除により、インデックスマップ構造を保持しながら他方の寸法で正確に１ピクセルが削除されることを保証する。一貫性が保たれない場合、１本の横方向のシームを削除すると、異なる数のピクセルを有する縦方向のシームが残る可能性があり、画像の長方形構造が影響を受ける。

シームを１つ（又は２つ）の寸法の行又は列に限定する外に、時間的に０連結のシームに制限される、この問題に対する別の手法を記載した。これらは、ソース画像Ｉ^（０）に空間的に連結されたシームである。

このようなシームの場合、ＨマップとＶマップとの間の一貫性の考え得る唯一の違反は、対角線のシームの段差で起こり得る。本方法はまず、時間的に０連結のシームを一方向（例えば縦）において求め、次に、他方向のシームを求める際に対角線に制約を課す。

一貫性の違反がなぜ対角線においてのみ生じるのかを理解するために、一般性を失うことなく、或る縦方向のシームｊ∈｛１，・・・，ｍ｝が一貫性の制約に違反するものと仮定する。これは、このシームが全ての横方向のシーム１，・・・，ｎと交差しないことを意味する。したがって、このシームは、或る横方向のシームｉ∈｛１，・・・，ｎ｝と２回以上接することになる。

シームｊがシームｉと交差するピクセルをｐ及びｑとして示す。ピクセルｐ及びｑは縦方向のシームｊの一部であるため、同一行にはあり得ない。しかし、これらのピクセルは横方向のシームｉの一部でもあり、同一列にはあり得ない。

２つの角がｐ及びｑで定義される長方形を検討する。シームｉ及びｊはこの長方形内で連結しており、角に接する。しかし、一方は縦方向のシームであり、他方は横方向のシームである。これが起こる唯一の可能性は、長方形が実際には正方形であり、両方のシームが正方形の対角線を通る場合である。

なお、上記の推論は、全てのシームが画像中の１箇所で連結しているという事実に依拠するが、これは、非０連結シームを用いる場合には当てはまらない（図１Ｅを参照）。本発明では、両方向で時間的に０連結のシームに制限するため、シーム１２２を求める（１２０）時間発展過程を、各寸法の全てのシームを同時に求めることに置き換えることができる。なぜなら、０連結のシームの場合、ソースサイズの画像を調べて、行の各対を個別に処理することができるからである。

行の対毎に、１行の全てのピクセルを次の行の全てのピクセルにつなぐ１エッジ経路の最適な集合を見付けることができる。画像の上端から下端までのグローバルな複数のシーム経路はそれらの１エッジ経路の連なりである。

一対の行間の最良の１エッジ経路を見付けることは、１行（列）の各ピクセルが他の行（列）の３つの近傍ピクセルに連結している加重分配問題に類似している。本発明では、よく知られたハンガリアンアルゴリズムを用いてこの加重分配問題を解く。ハンガリアンアルゴリズムは例えば、K. Murty著の教科書「ネットワークプログラミング（Network Programming）」（Prentice Hall, Englewood Cliffs, N.J., 1992, pp. 168-187）に記載されている。

一方の寸法においてマルチシーム経路を見付けたら、このプロセスを他方の寸法で繰り返すが、第１の方向のシームのいずれかで既に使用した対角線エッジは全てマスクする。これにより、図７Ｂ及び図７Ｃの一貫しないシームにそれぞれ対応する図８Ａ及び図８Ｂの一貫したシームの場合に示されるように、第２の寸法のシームが第１の寸法と一貫していることが保証される。

［発明の効果］
本発明の実施形態は、コンテンツを意識した画像の再構成のためのシームの適用を提供する。シームは、ソース画像中の最適な最小エネルギー経路として求められる。ピクセルは、シームに沿って削除又は挿入することができる。

シームの適用は、アスペクト比の変更、画像のサイズ変更、コンテンツの引き伸ばし及び物体の削除を含む様々な画像操作演算に用いることができる。シームの適用は、様々な顕著性測度及びユーザ入力と統合して、再構成プロセスを案内することができる。さらに、本発明は、リアルタイムでの連続的な再構成をサポートするマルチサイズ画像のデータ構造を提供する。

本発明を好ましい実施形態の例として説明してきたが、本発明の精神及び範囲内で様々な他の適応及び変更を行うことができることが理解される。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲に入る変形及び変更を全て網羅することである。

本発明の一実施形態による画像の再構成方法の流れ図である。 本発明の一実施形態によるシームを含む画像である。 本発明の別の実施形態によるシームを含む画像である。 本発明の別の実施形態によるシームを含む画像である。 本発明の別の実施形態によるシームを含む画像である。 （１Ｆ）本発明の一実施形態によるエネルギー画像、（１Ｇ）縦方向のシームインデックスマップ、および、（１Ｈ）本発明の別の実施形態による横方向のシームインデックスマップである。 （２Ａ）本発明の一実施形態によるソース画像、（２Ｂ）２Ａのソース画像のターゲット画像、および、（２Ｃ）２Ａの画像からスケーリングにより得られるターゲット画像、（２Ｄ）２Ａの画像からクロッピングにより得られるターゲット画像である。 （３Ａ）本発明の一実施形態によるソース画像、および、（３Ｂ）３Ａの画像から得られる引き伸ばしターゲット画像である。 （４Ａ）本発明の一実施形態によるソース画像、および、（４Ｂ）４Ａの画像から得られる引き伸ばしたコンテンツを有するターゲット画像である。 （５Ａ）本発明の一実施形態によるソース画像、および、（５Ｂ）５Ａの画像から得られる物体を削除したターゲット画像である。 （６Ａ）本発明の一実施形態によるソース画像、および、（６Ｂ）６Ａの画像から得られる、物体を削除しサイズを変更したターゲット画像である。 （７Ａ）本発明の一実施形態によるソース画像、（７Ｂ）７Ａの画像に対応する横方向のインデックスマップ、および、（７Ｃ）７Ａの画像に対応する縦方向のインデックスマップである。 （８Ａ）本発明の一実施形態による、７Ｂのマップに対応する一貫したインデックスマップ、および、（８Ｂ）７Ｃのマップに対応する一貫したインデックスマップである。

Claims (27)

1. コンテンツを意識した画像の再構成方法であって、
   画像スケーリングを用いて画像のサイズを大きくして、それをソース画像とすること、
   エネルギー関数に従って前記ソース画像からエネルギー画像を生成すること、
   前記エネルギー画像から、前記ソース画像の一端から向かいの端まで延びる各シームが最小エネルギーを有するように、１つ又は複数のシームを最小化関数に従って求めること、及び
   各シームを前記ソース画像から削除して、該ソース画像のコンテンツ及び長方形形状を保存するターゲット画像を得て、前記ソース画像を元の画像のサイズに縮小すること
   を含む、
   コンテンツを意識した画像の再構成方法。
2. 前記ソース画像のピクセルは、縦方向の寸法においてインデックスｎにより、横方向の寸法においてインデックスｍによりインデックス付けされ、各最小エネルギーシームは、前記ソース画像の一端から他端まで延び、各シームのピクセルの数は該シームの向きの前記寸法の前記インデックスに対応し、該シームは縦方向のシーム及び横方向のシームを含む、請求項１に記載のコンテンツを意識した画像の再構成方法。
3. 前記シームを目的関数に従う最適な順序で適用することをさらに含む、請求項２に記載のコンテンツを意識した画像の再構成方法。
4. 特定のシームが繰り返し適用される、請求項１に記載のコンテンツを意識した画像の再構成方法。
5. 前記適用は、前記ソース画像のアスペクト比を変更する、請求項１に記載のコンテンツを意識した画像の再構成方法。
6. 前記適用は、前記ソース画像から物体を削除する、請求項１に記載のコンテンツを意識した画像の再構成方法。
7. 前記適用は、前記ソース画像のサイズを保存しながら該ソース画像の前記コンテンツを引き伸ばす、請求項１に記載のコンテンツを意識した画像の再構成方法。
8. 前記エネルギー画像の前記生成は、前記ソース画像の強度領域において行われる、請求項１に記載のコンテンツを意識した画像の再構成方法。
9. 前記エネルギー画像の前記生成は、前記ソース画像の勾配領域において行われる、請求項１に記載のコンテンツを意識した画像の再構成方法。
10. 前記エネルギー関数は勾配の大きさである、請求項１に記載のコンテンツを意識した画像の再構成方法。
11. 前記エネルギー関数はエントロピーである、請求項１に記載のコンテンツを意識した画像の再構成方法。
12. 前記エネルギー関数は視覚的顕著性に基づく、請求項１に記載のコンテンツを意識した画像の再構成方法。
13. 前記エネルギー関数は視線移動に基づく、請求項１に記載のコンテンツを意識した画像の再構成方法。
14. 前記最適な順序を記憶して、前記ソース画像のサイズをリアルタイムで変更することを可能にすることをさらに含む、請求項３に記載のコンテンツを意識した画像の再構成方法。
15. 近傍ピクセルに類似するピクセルは低エネルギーを有し、近傍ピクセルに類似していないピクセルは高エネルギーを有する、請求項２に記載のコンテンツを意識した画像の再構成方法。
16. 前記エネルギー関数は、
    

    

    であり、ここで、Ｉ（ｘ，ｙ）は特定のピクセルである、請求項１に記載のコンテンツを意識した画像の再構成方法。
17. 前記適用は、前記ターゲット画像のエネルギーを最大化する、請求項１に記載のコンテンツを意識した画像の再構成方法。
18. 前記縦方向のシームは、
    

    

    であり、ここで、ｘはマッピングｘ：［１，・・・，ｎ］→［１，・・・，ｍ］であり、前記横方向のシームは、
    

    

    であり、ここで、ｙはマッピングｙ：［１，・・・，ｍ］→［１，・・・，ｎ］である、請求項３に記載のコンテンツを意識した画像の再構成方法。
19. 前記シームの前記ピクセルは８連結である、請求項１８に記載のコンテンツを意識した画像の再構成方法。
20. 前記シームの前記ピクセルはピース毎に連結されている、請求項１８に記載のコンテンツを意識した画像の再構成方法。
21. 前記シームの前記ピクセルは切断されている、請求項１８に記載のコンテンツを意識した画像の再構成方法。
22. 前記縦方向のシーム｛ｓ_ｉ｝（１０１）の前記ピクセルは、
    

    

    であり、前記縦方向のシームの前記エネルギーは、
    

    

    であり、前記最適な最小エネルギーシームｓ^＊は、
    

    

    である、請求項１８に記載のコンテンツを意識した画像の再構成方法。
23. 前記最適な最小エネルギーシームｓ^＊は、動的計画法を用いて見付けられる、請求項２２に記載のコンテンツを意識した画像の再構成方法。
24. 前記エネルギー関数はユーザ入力に基づく、請求項１に記載のコンテンツを意識した画像の再構成方法。
25. 前記エネルギー関数は物体検出に基づく、請求項１に記載のコンテンツを意識した画像の再構成方法。
26. エントリＴ（ｒ，ｃ）を含む横方向及び縦方向のインデックスシームマップＴを構築することをさらに含む、請求項２に記載のコンテンツを意識した画像の再構成方法。
27. 横方向及び縦方向のシームの削除の前記最適な順序は、
    

    

    を用いて計算され、ここで、Ｉ_{ｎ−ｒ×ｍ−ｃ}はｎ−ｒ×ｍ−ｃのサイズの画像を示し、Ｅ（ｓ^ｘ（Ｉ））及びＥ（ｓ^ｙ（Ｉ））は前記それぞれのシームの適用のコストである、請求項３に記載のコンテンツを意識した画像の再構成方法。

Images