Scene Completion Using Millions of Photographs
はじめに
http://graphics.cs.cmu.edu/projects/scene-completion/ のような物を実装してみました。そのときに苦労した点など書いていこうかと思います。*1
紹介
元の論文を読めば分かるのですが、違いもあるかもしれないので私の(再)実装の概要を書いておきます。
まず、APIでflickrから写真を大量に集めます。今回は長辺が600pxぐらいの画像を風景写真を中心に13万枚ほど使っています。
事前にそれらの写真のgist*2を計算しておきます。
入力は編集したい画像と、その画像で取り除きたい部分を示すマスクの２つの画像です。その画像のgistを計算し、先程の画像群から近いものをいくつか選び、大きさを調整します。
graph cutでマスクを最適化し、poisson blendingで合成すると穴が適当に埋められた画像ができます。
画像格納について
idやURLのハッシュなどをファイル名にしてひとつのディレクトリに入れる場合、ext4やxfsのようにlookupの速いものを使わないと大変なことになります(多分)。
gistのk-nearest検索について
今回は全ての要素との距離を毎回計算していますが、10秒ぐらいかかっているので、もっと大規模なデータなら何らかの高速化が必須です。
poisson blendingについて
疎行列の一次方程式を解く必要があるのですが、Gauss-Seidel法では遅すぎるのでmultigridの使用が必須です。
結果など
左上二枚が入力画像で、それぞれについて6つの候補を示しています。
こうしてみると、失敗のパターンというのは
- そもそも全く合わない (類似シーンが見つからない)
- うまく変換してやれば合いそう
に二分できて、どちらも元画像のデータベースを大きくすれば解決できて、特にヒューリスティックを使う必然性がないというのがこの手法の美しいところですね。
しかし、大幅にスケールが異なる場合でもtexture synthesisを使えばなんとかなる可能性もあります。それに、単に類似シーンを見つけてくるだけではなく言語的なクエリーを含めるなど、検索の自由度が高いとこれまでと全く違う仕組みの画像編集ソフトができておもしろいかもしれません。
あと、今回ここまで実装できたのはきっとComputer Vision: Algorithms and Applicationsのおかげです。この本は http://szeliski.org/Book/ で無料で公開されていて、内容も新しい(2010年)なのでComputer Vision/Graphicsな人は是非読んでみましょう。
*1:Efros氏のtalk http://video.google.com/videoplay?docid=-8639996003880499413
*2:Oliva, A. et al. Building the gist of a scene: The role of global image features in recognition. http://cvcl.mit.edu/Papers/OlivaPBR2006.pdf
