*PatchMatch とは 　データ（主に画像）から類似する部位を見つけて対応付けるアルゴリズムの１つです．PatchMatchでは，画像の連続性をうまく利用して効率的に対応を見つけ出します．図１は，PatchMatchを使って２枚の画像から密なオプティカルフローを計算した例を示します． [img:7wtk] {{small:図１ ２枚の画像とそのオプティカルフロー　比較：[link:オプティカルフロー (optical flow)]}} 　この対応付けのアルゴリズムはさまざまな用途に利用できます．次の動画は，PatchMatchの論文[1]の筆者が公開しているデモ動画です．ここでは，画像編集の機能が紹介されています． [youtube:fMe19oTz6vk] {{small:[1]Connelly Barnes, Eli Shechtman, Adam Finkelstein, and Dan B Goldman, "PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing" ACM Transactions on Graphics, 2009}} {{small:[link:http://gfx.cs.princeton.edu/gfx/pubs/Barnes_2009_PAR/patchmatch.pdf] }} *サンプルコード (C++) ライブラリ：[link:simplesp] サンプルコード：simplesp/sample/sp/opticalflow ２枚の画像からオプティカルフローを推定します． *問題設定 　画像{$I_A$}の各部位について，画像{$I_B$}で最も類似する部位を探索したいとします． [img:hgcd] {{small:図２ 入力する２枚の画像}} 　まずは，ブロックマッチングに基づく方法を考えます．具体的には，図３に示す様に比較するブロックを１つずつ変えて，その中で最も類似するブロックを見つけ出します．この探索方法を全探索，或いは力任せ探索(brute force search)と呼びます． [img:vkh7] {{small:図３ 画像上を走査してブロックを比較}} 　部位{$X$}を基準として，見つけた対応の位置を{$C(X)$}とします．この情報を画像{$I_A$}の各部位について計算した結果をNNF(Nearest-Neighbor Field)と呼びます． 　全探索によってNNFを計算する場合，その計算量は膨大になります．PatchMatchでは，このNNFを効率的に計算することを考え，近似的なNNFであるANNF(Approximate NNF)を計算します．{{small:図１のオプティカルフォローはまさにこのANNFです．}} *アルゴリズム 　画像の連続性を考えると，画像上で近接する部位の対応は似た傾向になることが期待できます．PatchMatchではその傾向をヒントに，効率的に対応を探索します．ここでは，そのアルゴリズムを説明します． １．Initialization ランダムに対応{$C$}を設定する ２．Propagation 画像上で近接する部位の対応{$C$}を伝播させる ３．Search 現在の対応{$C$}を基準に所定の範囲内で再度ランダムに対応を設定する ここで，２と３の処理は交互に繰り返して{$C$}を更新します． **Initialization 　画像{$I_A$}の各部位{$X$}について，その対応の位置{$C(X)$}をランダムに設定します．ランダムの効果で，低い数値ではありますが一定確率では正しい対応の位置が設定できます．とはいえ，画像には数十万以上の画素があって，そのすべてにランダムに設定することを考えると，確率は低くても正しい対応の数は画像上でそれなりの数が得られると考えられます． 　図４は，対応の位置を設定した例を示します．図４では，画像{$I_A$}の２つの部位（青と緑のブロック）についての対応を表示しています．青のブロックは間違った対応の位置が設定されていますが，緑のブロックは正しい対応の位置が設定されています． [img:md1n] {{small:図４ Initialization}} 　また，各部位{$X$}の{$C(X)$}について，その評価値{$E(X,C(X))$}を計算します．評価値はブロックの類似度で，SAD(Sum of Absolute Difference)などを使って計算するとします． **Propagation 　画像上の各部位{$X$}について，その周囲の部位{$X'$}の対応{$C(X')$}を伝播させます．その評価値{$E(X,C(X'))$}が元の評価値{$E(X,C(X))$}より高い場合，{$C(X)$}を置き換えます．この伝播の操作で，{$C(X)$}を置き換えた結果を図５に示します． [img:5skx] {{small:図４ Propagation}} **Search 　対応の精度を上げるため，現在の{$C(X)$}を基準に所定の範囲内で再度ランダムに対応{$C'(X)$}を設定します．その評価値{$E(X,C'(X))$}が元の評価値{$E(X,C(X))$}より高い場合，{$C(X)$}を置き換えます．なお，ランダムの範囲は繰り返しの計算ごとに徐々に狭くします． [img:q79m] {{small:図４ Search}}