論文紹介_エッジ保存系の画像フィルタ

論文紹介 エッジ保存系の画像フィルタ CTO室 芳賀

目次 • Side Window Filter • Curvature Filter 2

[1-1] Side Window Filter https://arxiv.org/abs/1905.07177 Yin, Hui & Gong, Yuanhao & Qiu, Guoping. (2019). Side Window Filtering. 8750-8758. 10.1109/CVPR.2019.00896.

• https://arxiv.org/abs/1905.07177

概要 • CVPR2019 oral • 既存のフィルタ処理（ Box Filter, Gaussian Filter, Guided Filter etc…）をエッジが保存するように適用できるフレームワーク • 様々なタスクに応用でき高品質な結果 – アーティファクト等も抑制 • 非常にシンプルなアルゴリズム • 計算量も既存の定数倍（3~10）程度 通常のBoxフィルタを適用※ エッジはぼやける 元画像 BoxフィルタのSide Window Filterバージョンを適用※ エッジやコーナーなど細かい構 造が保たれる 4 [1-2] より引用 ※10回繰り返し

導入 • エッジ保存アルゴリズム – 大域的最適化：高品質 低速 • TV algorithm – 局所的最適化：高速 低品質 • 線形：Box Filter, Gaussian Filter • 非線形：Median Filter, Bilateral Filter, Guided Filter • なるべく元画像に近い出力になるよう処理したい – 注目画素 𝑖 における処理 𝐼𝑖′ = ෍ 𝑤𝑖𝑗 𝐼𝑗 𝑗∈Ω𝑖 𝐼𝑖 ：位置 𝑖 の処理前の画素値 𝐼𝑖′ ：位置 𝑖 の処理後の画素値 𝑤𝑖𝑗 ：フィルタの重み (𝑖, 𝑗 の位置関係等に依存) Ω𝑖 ：位置 𝑖 の近傍 𝐸𝑖 ：エネルギー 2 𝐸𝑖 = 𝐼𝑖 − 𝐼𝑖′ 2 = 𝐼𝑖 − ෍ 𝑤𝑖𝑗 𝐼𝑗 𝑗∈Ω𝑖 𝐸𝑖 が小さい ⇔ 元画像に近い 5

エッジに対する方針 • エッジの向きや種類等を統一的に扱うことは線形な処理では不可能 • SWFでは画像において考えられる以下の3つのエッジに注目する step edge ramp edge 画 素 値 6 roof edge

Side Window Filter (SWF)[1-1] • 通常のフィルタ：注目画素を中心とした近傍で計算 注目画素 7x7のGaussian Filterを例に • side window：注目画素を端においた近傍で計算 L R U D NW NE SW SE – 斜め等様々なパターン（下例）が考えられるが、計算効率上8つに絞っている … 7

アルゴリズム • 画素ごとに以下ループ – Side Windowの集合 𝑆 ={L, R, U, D, NW, NE, SW, SE} ごとに以下 を計算 1 𝐼𝑛′ = 𝑁𝑛 ෍ 𝑤𝑖𝑗 𝐼𝑗 , 𝑗∈Ω𝑛 𝑖 𝑁𝑛 = ෍ 𝑤𝑖𝑗 , 𝑤：フィルタ係数 𝐼：フィルタ係数 – 以下の 𝐼𝑚 で注目画素値を更新 𝐼𝑚 = argmin || 𝐼𝑖 − 𝐼𝑖′ ||22 𝑛∈𝑆 𝑗∈Ω𝑛 𝑖 各SWFで定義された近傍 元の画素値との二乗誤差 𝑛∈𝑆 • フィルタをかけたうえで元の画素値に近いものを選んできて特徴を損ない にくくしている 8

具体例 • 7x7のBoxフィルタに対し各SWFを適用した場合 0 255 通常のBoxフィルタ 注目画素の7x7近傍 ′ 𝐼𝑁𝑊 =0, 𝐼′ = 0 × 4 × 7 + 255 × 3 × 7 ≅ 109 , 7×7 𝐼𝑈′ = 109 , |𝐼 − 𝐼 ′ | = 109 |𝐼 − 𝐼𝑈′ | = 109 ′ |𝐼 − 𝐼𝑁𝑊 |=0 ′ 𝐼𝑁𝐸 = 191 , ′ |𝐼 − 𝐼𝑁𝐸 | = 191 𝐼𝑅′ = 191 , |𝐼 − 𝐼𝑅′ | = 191 元の画素値が保存される 𝐼𝐿′ = 0 , |𝐼 − 𝐼𝐿′ | = 0 ′ 𝐼𝑆𝑊 =0, ′ |𝐼 − 𝐼𝑆𝑊 |=0 ′ 𝐼𝑆𝐸 = 191 , 𝐼𝐷′ = 109 , |𝐼 − 𝐼𝐷′ | = 109 ′ |𝐼 − 𝐼𝑆𝐸 | = 191 • 他のエッジパターンについても通常のBoxフィルタより元画素値に近い値 になることが示される [1-1] 9

結果 • フィルタ係数 𝑤𝑖𝑗 として様々な既存のフィルタ処理を適用 既存のフィルタ SWF適用バージョン 既存フィルタの特徴・用途 box filter (BOX) S-BOX 画像のぼかし、高速 gaussian filter (GAU) S-GAU 自然なぼかし median filter (MED) S-MED ピークノイズの除去 bilateral filter (BIL) S-BIL 画素値の情報も重みに用いて輪郭をぼ けにくくする guided filter (GUI) S-GUI 効果はbilateralと似ているがより高速 – SWFを適用することでより既存の効果の品質を向上させられる – 次のページ以降でいくつか紹介 • CPUでの計算時間 – 3~10倍程度の増加にとどまるとの結果[1-1] – アルゴリズムの最適化やGPU等を用いた並列化でより高速に 10

各種比較 • 一般画像に対するsmoothing, denoising結果 – 赤枠が既存、緑枠がSWF版 smoothing （数値はSSIM） [1-1] Fig.4より引用 denoising （数値はPSNR） [1-1] Fig.5より引用 11

その他タスクへのSWF適用結果 • フィルタや考え方を応用すれば一般的なタスクに適用可能 – image enhancement, HDR, structure preserving, colorization, etc… • 以下の図はHDR、colorizationの例 HDR colorization (着色) 従来[1-4] SWF版 従来[1-3] SWF版 [1-1] Fig.10より引用 [1-1] Fig.7より引用 エッジ周りのアーティファクトが 抑えられている 12 エッジを超えた色の染み込 みが抑えられている

参考文献 • [1-1] Yin, Hui & Gong, Yuanhao & Qiu, Guoping. (2019). Side Window Filtering. 8750-8758. 10.1109/CVPR.2019.00896. • [1-2] Side Window Filtering (CVPR2019 oral, #5176) https://github.com/YuanhaoGong/SideWindowFilter • [1-3] F. Durand and J. Dorsey. Fast bilateral filtering for the display of highdynamic-range images. ACM Trans. on Graphics, 21(3):257–266, 2002. • [1-4] A. Levin, D. Lischinski, and Y. Weiss. Colorization using optimization. ACM Trans on Graphics, 23(3):689–694, 2004. 13

• https://github.com/YuanhaoGong/SideWindowFilter

[2-1] Curvature Filter https://github.com/YuanhaoGong/CurvatureFilter Gong, Yuanhao & Sbalzarini, Ivo. (2017). Curvature Filters Efficiently Reduce Certain Variational Energies. IEEE Transactions on Image Processing. 26. 1786-1798. 10.1109/TIP.2017.2658954.

• https://github.com/YuanhaoGong/CurvatureFilter

概要 • 正則化が支配的な変分モデルにおいて、正則化項のエネルギー(最小 化対象)を逐次的に減らす離散フィルタ – 用途としてはエッジ保存denoisingやstructure除去など • 従来より高速にほどよい局所解に収束 • 局所的な画素値の曲率に注目した 3つの正則化モデルを例示 – ガウス曲率正則化（GC) • GCフィルタは画像を可展面（後述）に均す – 平均曲率正則化（MC) – Total Variation 正則化（TV) • アルゴリズムとしてはシンプルかつパラメータフリー 15 [2-2] より引用

方針 • 変分モデルによる画像処理 – denoising, super-resolution, … • 大域的最適解を求めるのは制約※や実用面で難がある • 正則化が支配的なケースで近似解でもいいから高速に求めたい • 正則化項に注目して最小化するアプローチ – 高速に動くフィルタリング処理で逐次的に ℰΦ1 𝑈 を減らしていく – 𝜆, ℰΦ0 𝑈, 𝐼 はアルゴリズム上明示的に扱わない • 論文後半で任意のdata-fitting項を明示的に扱う方法について論じている ℰ 𝑈 = ℰΦ0 𝑈, 𝐼 + 𝜆ℰΦ1 𝑈 エ ネ ル ギ ー ※data-fitting項が解析的である必要があるなど 全エネルギー total energy 元画像との差分 data-fitting term ℰ 𝑈 ℰ Φ1 𝑈 ℰΦ0 𝑈, 𝐼 試行回数 16 モデルの誤差 regularization term 𝐼：元画像 𝑈：処理後画像 𝜆 ：正則化係数

準備 • 曲率（二次元曲面） – 法曲率 – 主曲率(𝜅1 , 𝜅2 )：法曲率の最大値と最小値 – ガウス曲率：𝜅1 ⋅ 𝜅2 𝜅1 +𝜅2 – 平均曲率： 2 • 可展的(developable) – 円柱側面、円錐側面など – ガウス曲率=0 [2-3] より引用 17

正則化モデル • 画像を滑らかな2次元曲面で考える（画素値曲面） • 各点での曲率が制約（正則化）を満たすように逐次的に処理 – アルゴリズムとしては全て3x3のフィルタ計算に落とし込む GC regularization MC regularization TV regularization 曲面のモデル 区分的に可展 曲率最小 区分的に平坦 最小化 ガウス曲率の絶対値 平均曲率の絶対値 勾配のノルム 正則化項 𝐺𝐶 ℰΦ 𝑈 = න 𝜅1 𝜅2 𝑑 𝑥Ԧ = න 𝐾 𝑈 𝑑𝑥Ԧ 1 Ω 𝐾 𝑈 𝑥Ԧ = Ω 2 𝑈𝑥𝑥 𝑈𝑦𝑦 − 𝑈𝑥𝑦 2 1 + 𝑈𝑥2 + 𝑈𝑦2 𝜅1 + 𝜅2 𝑑𝑥Ԧ = න 𝐻 𝑈 𝑑𝑥Ԧ 2 Ω Ω 2 1 + 𝑈𝑦 𝑈𝑥𝑥 − 2𝑈𝑥 𝑈𝑦 𝑈𝑥𝑦 + 1 + 𝑈𝑥2 𝑈𝑦𝑦 𝑀𝐶 ℰΦ 𝑈 =න 1 𝐻 𝑈 𝑥Ԧ = 2 1 + 𝑈𝑥2 + 𝑈𝑦2 data-fitting項の増加を抑える （ ℰΦ0 の増加の最小化） エ ネ ル ギ ー 試行回数 ℰ 𝑈 ℰ Φ1 𝑈 ℰΦ0 𝑈, 𝐼 𝑆𝑚 𝑥Ԧ = argmin |𝑆𝑖 𝑥Ԧ − 𝑈 𝑥Ԧ | 𝑆𝑖 𝑥Ԧ 制約を満たす候補 （ ℰΦ1 の減少） 18 𝑇𝑉 ℰΦ 𝑈 = ||∇𝑈||𝑝 1 3/2 𝑈 𝑥Ԧ ： 𝑥Ԧ における注目画素値 𝑆𝑖 𝑥Ԧ ：近傍(3x3)から計算される候補 いくつかのパターン 𝑖 𝑆𝑚 𝑥Ԧ ：処理後の画素値

GC (Gaussian Curvature) フィルタ[2-1] • 画素ごとアルゴリズム概要 – 注目画素の周囲8pxの組み合わせによる画素値を高さとしたいくつかの接平面を考える • 接平面の集合を 𝑇 とする – 注目画素値がそれらの接平面に乗るように補正すべき量 𝑑𝑖 = 𝑆𝑖 𝑥Ԧ − 𝑈 𝑥Ԧ を計算 – 補正量の絶対値 |𝑑𝑖 | が最も小さいもの 𝑑𝑚 で注目画素を補正 |𝑑𝑚 | = min |𝑑𝑖 | 𝑇𝑖 ∈ 𝑇 𝑖∈𝑇 注目画素 𝑑𝑖 • 処理する画素の順番 – 画素を右図の色のように4種類にラベリング – 青→赤→黄→緑という順番で処理 – 各色内で並列化可能 19 補正

GCフィルタの各 𝑑𝑖 • 8方向の接平面を考える 𝑑1 = 𝑈 𝑥 − 1, 𝑦 + 𝑈 𝑥 + 1, 𝑦 /2 − 𝑈(𝑥, 𝑦) 𝑑3 𝑑2 • アルゴリズムの意味 – 𝑑𝑖 ：局所的なGC正則化項がゼロ（次ページ） – 最も変化の少ない 𝑑𝑖 で補正 • data-fitting項の増加をimplicitに抑制 20 𝑑4 𝑑5 𝑑7 𝑑6 𝑑8

理論的補足 • 可展面は局所的に接平面で近似可能[2-1] – 可展面では任意の点で主曲率（ 𝜅1,2 ）のどちらかが0 – 主曲率の片方（絶対値の小さい方）を0にすることがGC正則化につながる • Eulerの定理より 𝑑𝑖 は主曲率と固有角度 𝜃𝑖 から以下のように近似で きる 2 2 𝑑𝑖 ≈ 𝜅1 cos 𝜃𝑖 + 𝜅2 sin 𝜃𝑖 – GCフィルタでは min 𝑑𝑖 = 𝑑𝑚 ≈ min 𝜅𝑖 という離散的な近似 𝑖=1,…,8 – よって、 𝑑𝑚 を減らすことは主曲率のsparseな最小化につながる • エネルギーの収束性 – GCフィルタ操作は単調（証明あり）かつ下に有界（≥0） – 単調収束定理により局所解に収束する 21

• https://ja.wikipedia.org/wiki/オイラーの定理_(微分幾何学)
• https://ja.wikipedia.org/wiki/単調収束定理

GCフィルタの特徴 • 画像における可展面のメリット[2-4] – エッジやコーナーが保存される – なだらかな勾配グラデーションも保存される – 小さいスケールの特徴に乗ったノイズも除去できる • パラメータフリー • 計算複雑性がO(N) Input split-Bregman[2-6]によるTV最適化 可展面にノイズが乗った画像 𝜆：小 𝜆：大 GCフィルタ 10 iteration – 従来手法[2-5]の約7倍高速 [2-1] Fig.9より引用 ノイズが取りきれ ていない 22 でこぼこのような artifactが発生 可展面が保存さ れている

適用例 • denoising – iterationは10回程度で十分 – ごましおノイズに強いイメージ Input GCフィルタ10回 上段：ガウシアンノイズ 下段：ごましおノイズ [2-1] Fig.8より引用 23 細かいstructureも保存されている

他2つのCurvatureフィルタ • GCフィルタ同様の考え方・近似で3x3領域内の計算に落とし込める – MCフィルタ[2-1] – TVフィルタ[2-1] • 効果の違い[2-2] – GC • 特徴を保存 – MC • GCとTVの中間 – TV • 特徴もノイズも除去 [2-2] より引用 24

一般のdata-fitting項を扱う上での応用 • totalのエネルギーを下げないようにするトリック – ここまでdata-fitting項は陽に扱っていないため局所最適化問題となっていた※ • 正則化項の減少量がdata-fitting項の増加量を上回るときに画素値 を更新する（明示的に ℰΦ0 , 𝜆ℰΦ1 を計算） – 勾配法を使ったsolver（ ）と違いdata-fitting項が解析的でな くてもよい 上記の変更を行った TVフィルタ（iter=30） Primal/Dual法 – Spatially Adaptive Regularization[2-1] – 結果としては様々なパターンで sub-optimalに安定してしまう Split-Bregman, Multi-Grid, Primal/Dual [2-7] [2-1] Fig.18より引用 ※更新によってはdata-fitting項の増加でtotalのエネルギーが増加してしまう可能性もあるため 25

参考文献 • [2-1] Gong, Yuanhao & Sbalzarini, Ivo. (2017). Curvature Filters Efficiently Reduce Certain Variational Energies. IEEE Transactions on Image Processing. 26. 17861798. 10.1109/TIP.2017.2658954. • [2-2] Curvature filters are efficient solvers for variational models. https://github.com/YuanhaoGong/CurvatureFilter • [2-3] https://slidesplayer.net/slide/16186926/ • [2-4] M. Ibrahim, K. Chen, and C. Brito-Loeza. (2015). “A novel variational model for image registration using Gaussian curvature.” [Online]. Available: https://arxiv.org/abs/1504.07643 • [2-5] S.-H. Lee and J. K. Seo, “Noise removal with Gauss curvature-driven diffusion,” IEEE Trans. Image Process., vol. 14, no. 7, pp. 904–909, Jul. 2005 • [2-6] T. Goldstein and S. Osher, “The split Bregman method for L1-regularized problems,” SIAM J. Imag. Sci., vol. 2, no. 2, pp. 323–343, 2009. • [2-7] A. Chambolle and T. Pock, “A first-order primal-dual algorithm for convex problems with applications to imaging,” J. Math. Imag. Vis., vol. 40, no. 1, pp. 120–145, 2011. 26

• https://github.com/YuanhaoGong/CurvatureFilter
• https://arxiv.org/abs/1504.07643