紹介論文_S. Baker & T.Kanade (2020)“Limits on Super Resolution and How to Break them”

紹介論文: S. Baker & T. Kanade (2002), “Limits on Super-Resolution and How to Break them” CTO室 富田望

超解像とは • 入力画像より高い解像度の画像を得る手法 • 複数枚の低解像画像の情報を合わせ、高解像 度の画像を復元する (マルチフレーム超解像。特に deep learning (以下DL) だと入力1枚のみ使用するシングルフレーム超解像という のも多いですが、今回DLの手法は扱いません) • 応用:衛星写真、監視カメラ、医療画像など [4] Fig.1 より引用 • 右のような最適化問題としての定式化が多い – これを直接解いたり、DL なら学習したり • 出力 Su を適当にダウンサンプルすると入力 Lo𝑖 に戻る、という拘束 • 出力画像がなめらか、などの正則化（Prior） 1 𝑁 Su = argmin ෍ 𝜌(Lo𝑖 , 𝐻𝑖 Su ) + 𝑈(Su) Su 𝑖=1

この論文の概要 • たくさん合成すればいくらでも高解像度にできそうに思えるが、そうではない – 拡大率を上げていくと急速に問題が困難になる • たとえノイズがなくとも、入力枚数を増やしても情報が増えなくなっていく • → Priorの方が優勢になり、滑らかすぎる画像が生成されてしまう • 前半:原因の解析 – 理想的な場合における解析 – 究極的には画像の(8bit)量子化が制約となっている • 後半:対策 – 適切なPriorを用いること – 顔画像の超拡大のデモ 2

Outline • イントロ: 拡大率を上げると急速に困難になる • 前半:原因の解析 – 定式化 – 定理1: 可逆性 – 定理2: 条件数 – 定理3: 解の体積 • 後半:対策 – Hallucination Algorithm: Feature Pyramidを使ったより適切なPrior – 顔画像・文字画像での実験 3

イントロ: 拡大率を上げていくと… • 拡大率𝑀倍のときは𝑀2 枚合成すれば、トータルのピクセル数は入出力 で同じなので、情報量としては同じでは？ • 実際に再構成をかけてみると、拡大率が上がるとだんだん悪くなる。16 倍拡大(256枚合成)まで行くとかなりダメ – Gaussian blurをかけてランダムに平行移動、縮小したものを入力としている 4 [1] Fig.1 より引用

（理想化した）超解像の定式化 高解像度画像 Su(𝒑) (𝒑 = (𝑝, 𝑞) ∈ 𝒁2 ) を低解像度画像 Lo𝑖 (𝒎) (𝑖 = 1, … , 𝑁, 𝒎 = (𝑚, 𝑛) ∈ 𝒁2 ) から求める – 外界の光: 𝐸(𝒛) ここでは高解像度画像 Su 𝒑 そのものとする 𝐸 𝒛 = Su 𝒑 for all 𝒛 ∈ 𝑝 − 0.5, 𝑝 + 0.5 × 𝑞 − 0.5, 𝑞 + 0.5 , 𝒑 = 𝑝, 𝑞 ∈ 𝒁2 – 位置合わせは既知とし、簡単のため平行移動に限定 • 𝒙 = 𝑟𝑖 𝒛 = 𝐸 𝒛 = Su 𝒑 𝒙 = 𝑟𝑖 𝒛 PSF (光学系・ センサー) 1 𝒛 + 𝒄𝑖 𝑀 – ぼけ・センサー応答: Point Spread Function (以下PSF) • 外界の光がどのようにぼけるかを表す • Lo𝑖 𝒎 = 𝐸𝑖 ∗ PSF𝑖 𝒎 = ‫׬‬Lo 𝐸𝑖 𝒙 ⋅ PSF𝑖 𝒙 − 𝒎 𝑑𝒙 𝑖 – 拡大率: 𝑀 Lo𝑖 (𝒎) 1 • Su(𝒑) = Lo1 ( 𝒎) 𝑀 5

（理想化した）超解像の定式化: PSFのモデル • PSFは2段階に分けられるとする PSF𝑖 𝒙 = 𝑤𝑖 ∗ 𝑎𝑖 𝒙 – 光学系によるボケ 𝑤𝑖 – CCD受光部の形状 𝑎𝑖 • 𝑤𝑖 は特に仮定を置かない – 非負、かつ積分して1になればよい • 𝑎𝑖 は正方形を仮定 – CCDのチップ全面を受光部が覆っているわ けではない(配線) – センサー幅を 𝑆 とする (0 ≤ 𝑆 ≤ 1) [1] Fig.2より引用 6

結局行列計算とみなせる • 以下のような形にまとめられる Lo𝑖 𝒎 = ෍ 𝑊𝑖 𝒎, 𝒑 ⋅ Su(𝒑) 𝒑 1 1 𝑊𝑖 𝑚, 𝑝 = 2 න PSF𝑖 𝒛 + 𝒄𝑖 − 𝒎 𝑑𝒛 𝑀 𝒑 𝑀 • 1式目は 𝒑, 𝒎 についてベクトルの添え字とみなすと、行列計算 Lo𝑖 = 𝑊𝑖 Su とみることができる – 可逆性、条件数を議論することができる（定理1, 2） 7

定理1: PSFが正方形の時の可逆性 • 光学系が理想的な場合を考える (𝑤 𝒙 = 𝛿 𝒙 , ∴ PSF 𝒙 = 𝑎(𝒙)) Lo𝑖 𝒎 = ෍ 𝑊𝑖 𝒎, 𝒑 ⋅ Su(𝒑) 𝒑 1 1 𝑊𝑖 𝑚, 𝑝 = 2 න 𝑎𝑖 𝒛 + 𝒄𝑖 − 𝒎 𝑑𝒛 𝑀 𝒑 𝑀 • 定理1: 𝑀・𝑆 が2以上の整数である場合、平行移動 𝒄𝑖 をどのようにとっ てもこれらの式は不可逆になり、そのnull spaceの次元は少なくとも 𝑀 ⋅ 𝑆 − 1 2 となる。そうでなければ、可逆であるような 𝒄𝑖 の取り方が常 に存在する。 8

証明概略 • 受光部で高解像度画像 Su を積分した時、𝒄𝑖 にか かわらず0になるのはもとの画像がどのような場合か？ • 右図のような状態で積分結果が0とする。ここから上 下方向に微小にずらしても0のままであるのはどういう 場合か？ – 𝑀・𝑆が整数の場合、上端と下端にかかっている場所が同じ 値を取っていればよい → Su が上下方向に 𝑀・𝑆 周期で同じ値を取り、 その合計が0であればよい → null space は (𝑀・𝑆 − 1) 次元 左右方向も同様なので結局 𝑀・𝑆 − 1 2 次元 – 𝑀・𝑆 が非整数の場合、上端も下端も0でなければ微小に 動かすと積分結果も0でなくなる 9 Su （幅 1/M になって いる） PSF (= 受光部、幅 S)

実験 • 1024枚の画像を1.5倍拡大と2枚拡大にかける • 2倍拡大だと周期2pxのnull spaceがアーティファクトとして見える(図左) • 1.5倍拡大なら可逆なのでPrior入れなくても問題ない(図中央) • 滑らかさをPriorとして入れると2倍でもOK (図右) [1] Fig.4より引用 • Priorがあれば気にしなくてもいい？しかしMが大きくなると状況が変わる（定理3） 10

前提知識:条件数 条件数とは: • 行列の最大の特異値と最小の特異値の比 – 特異値: 正方行列の場合は固有値の絶対値と一致するが、正方行列以外でも求まる 𝑤1 Cond(𝐴) = 𝑤𝑛 • 一次方程式 𝑏 = 𝐴𝑥 から 𝑥 を求めたいとき、 𝐴 の条件数が大きいことを “悪条 件” という • 大きいほど数値計算として不安定: 𝑏 の小さな誤差が結果 𝑥 に大きな誤差として 表れてしまう 11

定理2: 任意のPSFについて条件数の解析 • 定理1は𝑤が理想的な場合だったが、その仮定をゆるめたもの Lo𝑖 𝒎 = ෍ 𝑊𝑖 𝒎, 𝒑 ⋅ Su(𝒑) 𝒑 1 1 𝑊𝑖 𝑚, 𝑝 = 2 න PSF𝑖 𝒛 + 𝒄𝑖 − 𝒎 𝑑𝒛 𝑀 𝒑 𝑀 • 定理2: 𝑤𝑖 𝒙 を非負・積分すると1となる任意の関数とする。このとき、 上の式の条件数は少なくとも 𝑀 ⋅ 𝑆 2 で増大する。 12

証明概略 • 行列Aの条件数 Cond(A) は、その最 大の特異値と最小の特異値の比 Lo𝑖 𝒎 = ෍ 𝑊𝑖 𝒎, 𝒑 ⋅ Su(𝒑) 𝒑 – 任意のベクトル 𝒙, 𝒚 について、 𝒙 2 𝐴𝒚 2 Cond 𝐴 ≥ 𝒚 2 𝐴𝒙 2 • 右の2つの入力 Su(𝒑) はどちらもノルム は同じ • 出力 Lo(𝒎) の方は – 上では全ピクセル +1 – 下では1/ 𝑀 ⋅ 𝑆 2 以下になることが示せる • この2つの入力を𝒙, 𝒚として上式に代入す ればよい 13 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 -1 +1 -1 +1 -1 +1 -1 -1 +1 -1 +1 -1 +1 -1 +1 +1 -1 +1 -1 +1 -1 +1 -1 -1 +1 -1 +1 -1 +1 -1 +1 +1 -1 +1 -1 +1 -1 +1 -1 -1 +1 -1 +1 -1 +1 -1 +1 +1 -1 +1 -1 +1 -1 +1 -1 -1 +1 -1 +1 -1 +1 -1 +1

定理2の意味 • 定理1と違って任意のwでよいが、示していることは弱い。無限の精度で 計算できれば原理上無問題 – これだけではイントロで見た画質の劣化を説明できない • 結局拡大率が大きくなるほど「ほとんどnull」になるような解がたくさん存 在してしまうのが効く（次の定理3） 14

定理3: 任意のPSFについての解の（超）体積 • ノイズがなく、無限の精度で計算できるのであれば、定理2は問題になら ないはず • 実際には画像は常に量子化されている（e.g. 8bit） • int[・]を入力を一番近い整数に丸める演算子とすると、 Su 𝒛 𝒛 Lo𝑖 𝒎 = int[න PSF𝑖 + 𝒄𝑖 − 𝒎 𝑑𝒛] 2 𝑀 𝒑 𝑀 • この式の解はもはや唯一ではなく、ある体積を持つ集合 {Su 𝒛 } となる • 定理3: Lo𝑖 𝒎 が与えられた時、上の式を満たす Su 𝒛 の領域の体 積は、漸近的に少なくとも 𝑀 ⋅ 𝑆 2⋅𝑛 の速度で増大する(nは定数)。 15

証明概略 式 Su 𝒛 𝒛 Lo𝑖 𝒎 = int[න PSF𝑖 + 𝒄𝑖 − 𝒎 𝑑𝒛] 2 𝑀 𝒑 𝑀 ⋯ (∗) の解 {Su 𝒛 } は Su 𝒛 𝒛 Lo𝑖 𝒎 − 0.5 = න PSF𝑖 + 𝒄𝑖 − 𝒎 𝑑𝒛 2 𝑀 𝒑 𝑀 の解となる Su 𝒛 を含む。0 ≤ PSF𝑖 ≤ 1/𝑆 2 なので、このSu(z)の任意のピクセルに 𝑀 ⋅ 𝑆 2 を足してもやはり (∗) の解。1つのピクセルだけでなくて分散して足してもOK。 Su(z)のピクセル数を固定してそれをnとすれば、一辺 𝑀 ⋅ 𝑆 2 のn次元単体がす べて(∗) の解ということになり、この体積は 定数 × 𝑀 ⋅ 𝑆 2⋅𝑛 。 16

再構成誤差の増加 • 以下の3通りについて、RMS誤差を比較 • 1枚 → 複数枚: 入力枚数増加の寄与 • 定理3 →複数枚再構成: Priorの寄与 Prior Su-Res. – 複数枚再構成結果 – 1枚だけで再構成 – 定理3からの予測（まったくPriorを使わない場 合） • 拡大率が小さいとPriorはむしろ害となる （ノイズがなければ） • 拡大率が上がると拘束だけでは解が全然 決まらなくなり、Priorの寄与の方が大きく なってくる → のっぺりした画像になってしまう 17 [1] Fig.1 より引用

ではどうするか • 認識ベースの再構成アルゴリズムを提案 – 画像の特徴量を利用してPriorを決める – “Hallucinating Face” – あまり細かくは説明しません – “Hallucinate”: • 幻覚を感じる、起こさせる / そこにないものを知覚する • 超解像の文脈での初出は 85 年、NNで指紋を超解像するものらしい 18

認識ベースの方法 • Laplaian PyramidとGaussian Pyramidの微分を特徴量とする – 各ピクセルで（Laplacian、dG/dx, dG/dy, d2G/dx2, d2G/dy2）の5つの画像 pyramidを作る。あるピクセルの特徴量を、これら5つのpyramidの値を並べたベクトルとする – 入力画像の各pixelについて、学習画像中で一番この特徴量が近い画像のpixelを取ってき て、そのピクセル上でのGradientが一致するようにPriorを設定 – さらに顔の場合は同じ座標のpixelだけを使用 • 600枚程度の顔のデータセットFERETを使用（顔はあらかじめalignしてcrop） 19

結果（顔画像） • 8倍拡大でもだいぶ顔らしい画像に復 元できる（20年前だと思うとなかなか） • 一番下の列で、入力の口にあたる箇所 が白いことをもってちゃんと口が開いてい ることを復元できている • 拡大率はこのあたりが限界だった – 入力サイズがこの半分だと、人が見ても顔 かどうかもわからない画像になってくる。 Detection もほぼ無理なので監視カメラ 用途ではこの倍率で十分という主張 [2] Fig.16より引用 20

結果（文字） • 文字が表示されているウィンドウ の一部を学習用、一部をテスト 用に使用して2倍拡大 – まったく同じfontが画像中に存在 するという意味で有利な入力だ が、学習のときに特に位置合わ せとかはしないでよい • “was” とかうまくいっている 21 [2] Fig.19より引用

weakpoints • 照明条件にあまりロバストでないので実際に監視カメラでやってみると(従 来手法より悪くはならないまでも)そこまで劇的に良くはないとか、 • 何もないところに顔を見てしまうとか 22 [1] Fig.14 より引用 [2] Fig.7 より引用

まとめ・所感 • マルチフレーム超解像の解の候補数は、拡大率を上げるにしたがって急 速に増大してしまい、Priorの寄与が大きくなっていく – 画像が量子化されていることで（ノイズがなくとも）発生 • ドメインを絞ってPriorを学習データから得る Hallucination Algorithm により、大拡大率でも顔を復元するデモ – テストデータではなかなかうまくいくが、少し条件が変わると厳しい • GANで超解像するときの作っている感はそんなに新しいものでもなかった • ノイズがある場合結果が悪くなるのか、逆にディザ的な効果でむしろ良く なったりするのか気になった 23

参考文献 • [1] S. Baker and T. Kanade, “Limits on Super-Resolution and How to Break Them,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, no. 9, pp. 1167–1183, Nov. 2002, doi: 10.1109/TPAMI.2002.1033210. • [2] S. Baker and T. Kanade, “Hallucinating faces,” Feb. 2000, pp. 83–88, doi: 10.1109/AFGR.2000.840616. • [3] K. Nasrollahi and T. Moeslund, “Super-resolution: A comprehensive survey,” Machine Vision and Applications, vol. 25, pp. 1423–1468, Aug. 2014, doi: 10.1007/s00138-014-0623-4. • [4] L. Yue, H. Shen, J. Li, Q. Yuan, H. Zhang, and L. Zhang, “Image superresolution: The techniques, applications, and future,” Signal Processing, vol. 128, pp. 389–408, Nov. 2016, doi: 10.1016/j.sigpro.2016.05.002. • [5] B. Wronski et al., “Handheld Multi-Frame Super-Resolution,” ACM Trans. Graph., vol. 38, no. 4, pp. 1–18, Jul. 2019, doi: 10.1145/3306346.3323024. 24

• https://doi.org/10.1109/TPAMI.2002.1033210
• https://doi.org/10.1109/AFGR.2000.840616
• https://doi.org/10.1007/s00138-014-0623-4
• https://doi.org/10.1016/j.sigpro.2016.05.002
• https://doi.org/10.1145/3306346.3323024

おまけ:（古典的な）超解像の歴史 • ’74 最初の超解像 – 最初10年くらいはずっと周波数ドメイン （理論的・計算量的に扱いやすかった） 今回の手法 • ’87 最初の空間ドメイン超解像 – 周波数ドメインでは一般的な動きを扱え なかった – 特にPrior付きの最適化アルゴリズムがメイ ンストリームに Sparse coding • ’08 Sparse coding法登場 – ブラックホールの撮影でも使われていた • (’14 SRCNN、’17 SRGAN) [3] Fig.2 より引用 25 Pixel3の手法 [5]の源流