パッチマッチ

ランダムオフセットで初期化する場合、画像の全範囲にわたって独立した均一サンプルを使用します。${\displaystyle B}$このアルゴリズムは、ピラミッドの前のレベルの初期推定値を使用することを避けています。これは、アルゴリズムが局所的最小値に陥るのを回避できるためです。

初期化後、アルゴリズムは、${\displaystyle NNF}$反復処理では、オフセットをスキャン順（左から右、上から下）に調べ、それぞれに伝播とランダム検索が行われます。

私たちは改善しようと努めています${\displaystyle f(x,y)}$既知のオフセットを使用して${\displaystyle f(x-1,y)}$そして${\displaystyle f(x,y-1)}$パッチオフセットが同じであると仮定します。つまり、アルゴリズムは新しい値を取得します。${\displaystyle f(x,y)}$である${\displaystyle \arg \min \limits _{(x,y)}{D(f(x,y)),D(f(x-1,y)),D(f(x,y-1))}}$なので、もし${\displaystyle f(x,y)}$正しいマッピングを持ち、コヒーレント領域にある${\displaystyle R}$すると、${\displaystyle R}$下と右側${\displaystyle f(x,y)}$正しいマッピングで埋められます。あるいは、偶数回の反復では、アルゴリズムは異なる方向を探索し、新しい値を埋めます。${\displaystyle \arg \min \limits _{(x,y)}\{D(f(x,y)),D(f(x+1,y)),D(f(x,y+1))\}}$。

させて${\displaystyle v_{0}=f(x,y)}$私たちは改善を試みます${\displaystyle f(x,y)}$指数関数的に減少する距離にある候補オフセットのシーケンスをテストすることによって${\displaystyle v_{0}}$

$u_i=v_0+w\alpha^iR_i$

どこ${\displaystyle R_{i}}$は一様乱数です${\displaystyle [-1,1]\times [-1,1]}$、${\displaystyle w}$は、最大画像サイズに設定される大きなウィンドウ検索半径であり、${\displaystyle \alpha }$は固定比率で、多くの場合 1/2 に設定されます。このアルゴリズムの部分では、${\displaystyle f(x,y)}$ランダムなプロセスによって局所最適解から脱出する。

よく用いられる停止基準は、反復回数を4～5回程度に設定することである。反復回数が少なくても、このアルゴリズムはうまく機能する。