Adobe Photoshop CS5に実装されるPatchMatchの実力

動画：Adobe Photoshop CS5の新機能はもはやえげつないレベル… | ◆めっつぉ：スクエニ&ガジェットニュースとしてAdobe Photoshop CS5の新機能が紹介され話題になっている。

概要を知るには動画で見るのが手っ取り早いが、本エントリではSIGGRAPH2009で発表された元論文*1を参照して、その詳細を紹介したい。

本エントリで紹介する画像は全て元論文からの引用であり、高解像度画像にリンクしている。「失業者が出るレベル」とコメントされているが、高解像度画像によりそのクオリティを確認してもらいたい。

PatchMatchの概要

Adobe Photoshop CS5の新機能は、近似画像ないし近似画像領域を発見するための無作為近隣探索アルゴリズムであるPatchMatchによって実現されている。最近隣探索(nearest-neighbor search)は先行研究でも利用されていたが、計算量が大きくインタラクティブな画像編集には使うことができなかった。PatchMatchは先行技術に比べ20倍から100倍の高速化を実現し、Adobe Photoshop CS5への実装が可能となった。

このアルゴリズムの鍵は、ランダムサンプリングによっていくつかの良いパッチマッチング画像を得ることができれば、自然画像の特性によってその周囲に連鎖的にマッチング画像を見つけることができると言うアイデアである。このPatchMatchを利用することで、retargeting（構図変換）、画像補完、reshuffling（画像再配置）などが可能となる。さらに既存手法では利用できなかったユーザレベルの制御を可能とする、複数の拘束条件の付与手段が提供されており、合成結果の品質が大きく向上している。

上図（リンク先に2900x1438 pixel画像）(a)の元画像に対し、紫色で示された隠蔽領域(hole)に加え、赤/緑/青で示された拘束条件(constraints)を示すガイド線を指定する(b)。このガイド線によって、屋根の輪郭線の連続性が保存される。補完画像(c)において欠けた部分が近傍の類似パッチにより補完されていることが分かる。次にretageting（構図変換）のためにユーザが赤い拘束ガイド線を指定し(d)、横方向に縮小すると、全体の形を保ったまま自動的に2本の柱が削除される。さらにresuffling（画像再配置）により屋根を上方向に持ち上げている(f)。

アルゴリズムの概要

画像のアスペクト比を変えるretargeting（構図変換）、不要な部分を削除し埋め合わせる画像補完、画像の一部を掴んで自由に再配置するreshuffling（画像再配置）などの画像処理においては、インタラクションが不可欠である。しかし、対象の構造を保ったまま画像の変形を行うことは計算量が大きく、高速な処理が難しいという課題があった。

ボトルネックとなっていたのは、画像内から最も類似した画像パッチ（小さな画像片）を発見する近隣探索処理である。ある部分を補完するには、類似した他の部分から画像パッチを引っ張ってきて埋める処理を行うが、PatchMatchアルゴリズムではこの検索を高速に行うことができる。自然画像は局所的に類似領域が近接する性質があり、この性質を上手く使えば、検索空間を小さくすることができるのである。

その検索は3段階のフェイズで行われる。画像Aと画像Bがあり、画像A中のパッチに近似したパッチを画像Bから発見する場合を考える。

初期化(Initialization)：まず各パッチは対応するパッチをランダムに与えられる（赤・青・緑）。
伝搬(Propagation)：青いパッチは、上方の緑、左方の赤の近傍をチェックし、適合度がより高まるか確認する。
検索(Search)：赤の方が適合度が高い場合、その近傍に青に対応する領域がある事が期待されるので、近傍を検索し適合度が高い点を見つける。

このようにして自然画像の特性を利用して、連鎖的に適合度の高い点を見つけることができる。

次の図は提案手法における伝搬例を示している。一番左の2枚が元画像である。そして上列の右側3枚は、左下の元画像から取得した、右上画像の各要素の近似パッチ画像を用いて合成したものである。下列の右側3枚は、パッチの対応関係を可視化したものである。近似画像パッチの検索スキャンは水平ラインに沿って行われているが、第1回目のパスにおいても良い近似が得られていることが分かる。5回スキャンを繰り返すとほぼ変化が収束し、小さなオレンジ色の花が良く一致していることが分かる（拡大画像を参照すること）。

この検索において、解像度にかかわらず従来手法*2と比較して20倍から100倍の高速化、1/20以下のメモリ使用量に抑えられている。この検索の効率化が、次に述べる魔法のような画像処理をインタラクティブに実現する鍵となったのだ。

解像度(Megapixels)	処理時間(秒)		使用メモリ(MB)
解像度(Megapixels)	本手法	kd-tree	本手法	kd-tree
0.1	0.68	15.2	1.7	33.9
0.2	1.54	37.2	3.4	68.9
0.35	2.65	87.7	5.6	118.3

編集ツール

さらに画像編集の精度を向上させるため、画像編集ツールで近隣探索における拘束条件を指定することができるようになっている。次の図はユーザによって拘束条件を与えた画像補完の例を示している。

鳥を入力画像から削除してみる(a)。ユーザは隠蔽領域をマスクし、類似パッチ画像検索における検索空間に対する拘束条件を指定する(b)。数秒後に補完画像が生成される(c)。次に花に囲まれたオブジェを入力画像から削除してみる(d)。ユーザが隠蔽領域をマスクすると(e)、補完画像が生成される(f)。同じ入力画像(g)に対し、隠蔽領域をマスクし、さらに花と屋根の輪郭線に対する拘束条件を指定すると(h)、花の色と屋根が変化した補完画像が生成される(i)。

次に変形に対する拘束条件を与えた場合について示す。元画像(a)に対して、拘束条件無しにretargetを行うと、ビルの境界線が崩れた画像が生成される(b)。カラー線で示した拘束条件を指定すると、境界線が保存された画像が生成される(c)。

元画像(a)に対して、拘束条件無しにretargetを行うと酷い有様だが(b)、カラー線で示した拘束条件を指定すると、直線が生成され、円は制限されたスペースにフィットするように縮小されて配置される(c)。

ここで、直線の拘束条件を与えたときの推測過程について図を用いて説明する。L_kは元画像Sにおける直線である。L_k上の点p_iについて画像Tにおける最近接点をNN(p_i)とする。画像Tにおける点q_iはL_k上の最近接点NN(q_i)をもつ。ここで、全てのそのような点NN(p_i)とq_iを集めることで、画像Tにおけるベストな線M_kを求めることができる。その後、点を推定線M_k上に投影することで、指定された直線を保ちながら対象画像をretargetすることが可能となる。

既存手法との比較

次にRubinsteinらによる手法*3及び、Wangらによる手法*4とのRetargeting結果の比較を挙げる。子供の例では既存手法のRetargetingでは子供が不自然に変形してしまっているが、本手法では子供は変形されずに保存されている。建物と道路の例では既存手法では直線であるべき線が崩れてしまっているが、本手法では直線が保たれ自然な変形が実現できていることが分かる。

さらに本手法ではインタラクティブに操作が可能なので、次の図に示すような画像編集操作がストレス無く行える（動画参照）。よくよく見ると不自然な部分が残っていたり、ゴーストやぼけが発生したりするが、高速に処理が可能なので、新たな拘束条件を追加したり、修正したりするなどのトライ&エラーが容易く行えるのは既存手法にはない大きなメリットである。

将来のリアルタイム処理や動画処理のためには、最初のランダムサンプリングを入力画像に併せて最適化することや、より高度なGPUインプリメンテーションが必要となる。論文の最後では、動画処理への応用についての記載されており、数年後には同じレベルの編集が動画に対しても行えるようになることが期待される。写真の証拠能力には疑問符が付く昨今だが、動画に関しても、もはやうかうかしていられないかもしれない。

Adobe Photoshop CS5の新機能の鍵となるのは高速に近似近傍画像を探索できるPatchMatchアルゴリズムである。このアルゴリズムはリアルタイムでインタラクティブなインタフェースを実現するのに充分高速であり、従来は実用的な時間、精度では実現できなかった近傍画像探索に基づく高度な画像処理を可能としている。また、このアルゴリズムは単純なため、ハイレベルのセマンティックな制御を導入することが可能であり、近傍探索における拘束条件を与えることで、ユーザが直感的に処理結果を最適化できる点は、ツールの使い勝手を大きく向上させるだろう。本手法の応用範囲は広く、CS5で実現されたレベルはまだ最初のとっかかりに過ぎない。近年、長足の進歩を遂げる画像処理研究成果から見て、しばらくの間はPhotoshopに毎年魔法のような新機能が追加されると期待しても良いのではないだろうか。

参考エントリ

*1:Connelly Barnes, Eli Shechtman, Adam Finkelstein, and Dan B Goldman. PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing. ACM Transactions on Graphics (Proc. SIGGRAPH). 28(3) August 2009.

*2:HERTZMANN, A., JACOBS, C. E., OLIVER, N., CURLESS, B., AND SALESIN, D. 2001. Image analogies. In ACM SIGGRAPH, 327.340.

*3:RUBINSTEIN, M., SHAMIR, A., AND AVIDAN, S. 2008. Improved seamcarving for video retargeting. ACM SIGGRAPH 27, 3.

*4:WANG, Y.-S., TAI, C.-L., SORKINE, O., AND LEE, T.-Y. 2008. Optimized scale-and-stretch for image resizing. In ACM SIGGRAPH Asia, ACM, New York, NY, USA, 1.8.

A Successful Failure