Total Variation minimization による画像拡大
ダウンロード
tvresize-1.1.tar.gz (20120414) / ソースを見る
ビルド & 使い方
libpng と boost が必要。
$ make
$ ./tvresize
Usage: tvresize -s <scale> -c <iteration count> [-f <smoothness>] src.png dst.png
-s と -c は必須でパラメータは整数値のみ。 -f は滑らかさを表すパラメータで 1.0 以上の実数値。デフォルト値は 1.0 で、このとき拡大画像を単純な box フィルタで元のサイズに縮小すると元画像と完全に一致する。値を大きいほど元画像からズレを許容して滑らかな画像を生成する。
これは何
"Total Variation Based Interpolation", F. Guichard, F. Malgouyres, 1998 を実装してみたつもりなんだけど、「縮小画像が元画像と一致する拘束条件のもとで \( \int | \nabla \phi | \) を最小化する」という基本的アイデアを漠然と理解しただけで、全然まともに読んでないので何か違う方程式を解いているかもしれない。
少なくとも最小化の方法は論文とは違っている。まず最小化したい値
\[
\block{align*}{
\int \D x \D y | \nabla \phi |
}
\]
が極小点にいるとき、変分原理から次の偏微分方程式が成り立つ。
\[
\block{align*}{
\nabla \left( \frac{\nabla \phi}{|\nabla \phi|} \right) = 0
}
\]
これを二次元の場合にバラして整理する。
\[
\block{align*}{
(\partial_x \phi)^2 {\partial_y}^2 \phi + (\partial_y \phi)^2 {\partial_x}^2 \phi - 2 \partial_x \phi \partial_y \phi \partial_x \partial_y \phi = 0
}
\]
次にこれを中心差分で差分化すると、運よく (?) \( \phi(x, y) \) について線形になっている。そこで \( \phi(x, y) \) について解くと、
\[
\block{align}{
\delta_x \phi(x, y) &\equiv \frac{\phi(x+1, y) - \phi(x-1, y)}{2}
\\
\delta_y \phi(x, y) &\equiv \frac{\phi(x, y+1) - \phi(x, y-1)}{2}
}
\]
\[
\block{align}{
\phi(x, y) = \frac{
2 \delta_x \phi \delta_y \phi \delta_x \delta_y \phi
- (\delta_x \phi)^2 \left\{ \phi(x, y-1) + \phi(x, y+1) \right\}
- (\delta_y \phi)^2 \left\{ \phi(x-1, y) + \phi(x+1, y) \right\}
}
{4 \left\{ (\delta_x \phi)^2 + (\delta_y \phi)^2 \right\}}
}
\]
となるので、これを Jacobi 法よろしく単純に反復する。…と収束しないので、少しもとの \( \phi \) を混ぜつつ反復している。
ちょっと調べてみると、 TV 最小化の計算手法はかなり研究されているよう。上記の単純な方法が他の賢い手法と比べてどのくらい遅いのかは確かめていない（適当）。
追記(20120415): 上の式変形には気をつけなければいけないところがあって、拘束条件をラグランジュの未定乗数法か何かで取り入れたとすると、その項には次のように \( \left| \nabla \phi \right| \) がかかる。
\[
\block{align*}{
\nabla \left( \frac{\nabla \phi}{|\nabla \phi|} \right) + (\text{constraint terms}) = 0
}
\]
\[
\block{align*}{
(\partial_x \phi)^2 {\partial_y}^2 \phi + (\partial_y \phi)^2 {\partial_x}^2 \phi - 2 \partial_x \phi \partial_y \phi \partial_x \partial_y \phi + {\left| \nabla \phi \right|}^{3} (\text{constraint terms}) = 0
}
\]
\[
\block{align*}{
\phi(x, y) = (\cdots) + \sqrt{(\delta_x \phi)^2 + (\delta_y \phi)^2} \ (\text{constraint terms})
}
\]
でも、結果がいまいちなので、この係数は今のところ取り込んでいなかったりする。これは単純に間違いというわけではなくて、原論文でいう射影演算子 P の任意性をどう取るか、ということに対応していると思うんだけど、よく考えていない。
例
左から原画像、このプログラムの結果、 lanczos3 での結果。
cd ../
Yasuhiro Fujii <y-fujii at mimosa-pudica.net>