パッチマッチ:ランダム探索による高速なパッチベース手法

ここまでで紹介してきた基本的なパッチベースでのインペインティング手法では、「一番適したパッチを探してはその部分にコピーして埋めていく」という戦略が取られている分、各パッチの探索がソース領域からの全探索的に探すなので、どうしても全体の計算コストが高くなります。そこで、この計算コストを改善する意味で提案されて研究が続けられているのが、パッチ探索をランダム探索に行うことでパッチごとの対応領域探索の高速化を目指す「パッチマッチ(patch match)」という手法です。

パッチマッチは、以下の3段階の処理により、対応パッチのランダム探索を高速に行うことができるアルゴリズムです(注:パッチマッチはAdobe SystemsとPrinceton大学らの研究により開発されたアルゴリズムで、Adobe Systemsが特許取得済みです)。

パッチマッチの処理手順

  1. 最近傍フィールド(NNF)のランダム初期化
  2. 近傍マッチの伝播(フィールドの更新処理1)
  3. 近傍のみでのランダム探索(フィールドの更新処理2)

パッチマッチは最近傍フィールド(Nearest Neighbor Field:NNF)という「画像Aの各座標ごとに、その座標のパッチが対応する画像Bのパッチ(最も値の近いパッチ)の座標値が保存されてあるフィールド」を最初に初期化し(処理1)、近傍周辺だけをランダム探索する更新処理(2、3)を繰り返してフィールドを更新していく処理です。NNFでは、各座標に保存されている、その座標に対応する画像B上の座標を「オフセット」と呼びます(画像Aのある座標がどれくらいオフセットでずれたかという意味です)。そのNNFのオフセット値を、各座標ごとにすべて探索すると計算時間がかかるので「画像の一貫性」を利用することで(後述)近似的に高速探索するのがパッチマッチ処理です。それでは1～3の処理をもう少し詳しく説明しましょう。

NNF

まずは1の処理で画像Aと同じ画素数(縦と横の幅)でNNFを作成し、NNFのすべての座標において、ランダムにオフセット値を適当に割り当てておきます。パッチマッチのように近似探索をする時には、このようにランダムに与えた「初期解(initial guess)」を幾つか探索したい空間(ここでは画像の座標空間)に散りばめておいて、その周辺のみの近似探索に持ち込むというアプローチがよく用いられます。

次に2、3の更新処理です。1回の2、3の処理で最適の値を(近似)探索したいNNF上の座標をaとしましょう。その時、まず2の処理において、aに割り当てるオフセット値の候補として、NNF上の座標の隣の2つの座標(1つ左隣の座標と1つ上隣の座標)に納められているオフセットを用意します。次に3の処理では、それら2つの候補値の座標の周辺の狭い領域のみで、最も値が近いパッチのランダム探索を行います。このランダム探索により一番値が近いパッチの座標がオフセット値として(近似的に)決定します。その決定したオフセットをNNFの座標aに新たに保存することでNNFが座標aに対して更新され、座標aに対する1回の繰り返し処理が完了です。これら2、3の更新処理をNNF上の対象領域中の全ての座標において繰り返し行う事で、NNF全体の対応パッチ探索が高速に完了できるというのがパッチマッチの処理の流れです。

パッチマッチの処理の流れ

2の処理で座標aの周辺に納められているピクセルのフィールド値が示す対応パッチの場所を候補値として利用するわけですが、これは一般的な画像であればいつも成り立つ「画像上の近傍領域の一貫性」をうまく利用していると言えます。同じ風景を撮影した画像同志であれば、画像中の注目座標周辺のピクセル値のパッチ内の画素値は大体同じようなものになっている場合がほとんどです。従って、注目座標の近くだけでランダムに探索することで、少ない計算コストで高速に探索できるわけです。

画像の一貫性

こうして2,3の処理を欠損領域のすべての座標で行った時点でNNFが欠損領域域のすべてにおいてオフセット値の最良値の探索が完了します。そして完成したNNFを用いて、あとは対象領域の各座標を対応する各パッチで埋める処理を行えばインペインティング処理が完成します(ただし、パッチマッチはあくまで近似探索なので、必ずしも一番似ているパッチが、完成したNNFの書く座標に保存されているわけでないことは注意です。それほど見え方が近くないパッチが探索されて、それを使用してしまう場合はあり得ます。)

パッチマッチはこのように「画像間(もしくは画像中の別の領域間)で、対応するパッチを見つけてくる」という仕組みなので、インペインティング以外にもパッチ対応を用いる画像編集技術であれば使用することができます。すなわち、インペインティング以外にもこのあと紹介する「リシャッフリング」や次回紹介する「リターゲティング」でも使用することができる汎用性のある対応探索アルゴリズムとなっています。それでは次回、その「リシャッフリング」での応用例を紹介して、パッチマッチの紹介を終わりにしましょう。