Haze Removal （霧除去）のメモ

# 概要

　画像から霧を除去するアルゴリズムについて、簡単に紹介します。

論文は、以下を引用しています。

http://kaiminghe.com/publications/cvpr09.pdf

霧除去のプログラムは、以下のブログが参考になります。

https://nsr-9.hatenablog.jp/entry/2021/08/10/203000

Soft Mattingに関しては、以下のアドレスが参考になります。

https://stackoverflow.com/questions/55353735/how-to-do-alpha-matting-in-python


# 一般的な霧除去のモデル 
　一般的な霧除去のモデルは、

```math
I(x)=J(x)t(x)+A(1-t(x))
```
と書ける。$I(x)$は観測された画像、$J(x)$は霧が取り除かれた画像、$A$は大気光であり、$t$は透過マップ（霧に相当）である。
　求めたいのは霧が取り除かれた画像$J(x)$である。観測された画像おいて$I(x)$，輝度の高いピクセルの輝度値を大気光$A$とする。ここで求めたいのは、透過マップ$t$である。


# Dark channel
　Dark channel は、

```math
J^{dark}(x)= \min_{c\in{R,G,B}} \left\{ \min_{y\in\Omega(x)} \left\{J^c(y)  \right\} \right\}
```
で定義される。$J^c$は$J(x)$のRGB配列であり、$\Omega(x)$はlocal patchである。この式を使うことによって、画像の白い領域が取り除かれる。

　$J(x)$は、Haze free（霧がない画像）ならば、

```math
J^{dark}(x) \approx 0
```
となる。
　霧除去のモデルにおいて、透過マップを$\tilde{t}$とおき（以後、洗練された透過マップを$t$と置くため）、各channel において local patch ごとに最小値を取り、

```math
\min_{y\in\Omega(x)} \left\{I^c(y)\right\} =\tilde{t}(x) \min_{y\in\Omega(x)} \left\{J^c(y)\right\} +(1-\tilde{t}(x)) A^c
```
式変形を行い、各channel ごとに最小値を取れば

```math
\begin{align}
\min_{c\in{R,G,B}} \left\{ \min_{y\in\Omega(x)} \left\{\frac{I^c(y)}{A^c}\right\}\right\} &= \tilde{t}(x) \min_{c\in{R,G,B}} \left\{ \min_{y\in\Omega(x)} \left\{\frac{J^c(y)}{A^c}\right\}\right\} +(1-\tilde{t}(x)) 
\end{align}
```
となる。$J(x)$は、Haze free ならば、画像は負のピクセル値を取らないこと（$A^c>0$であるが、真黒な画像は$A^c=0$になりえる）より、

```math
\begin{align}
\min_{c\in{R,G,B}} \left\{ \min_{y\in\Omega(x)} \left\{\frac{J^c(y)}{A^c}\right\}\right\} =0
\end{align}
```
となる。よって、透過マップ$\tilde{t}$は、

```math
\begin{align}
 \tilde{t}(x) = 1 - \min_{c\in{R,G,B}} \left\{ \min_{y\in\Omega(x)} \left\{\frac{I^c(y)}{A^c}\right\}\right\} 
\end{align}
```
となる。画像が白っぽい場合、ピクセル値は$255$に近いので（大気光も$255$に近い）、透過マップ$\tilde{t}$の2項目は、

```math
\begin{align}
\min_{c\in{R,G,B}} \left\{ \min_{y\in\Omega(x)} \left\{\frac{I^c(y)}{A^c}\right\}\right\} \approx 1
\end{align}
```
となる。透過マップ$\tilde{t}$は、

```math
\begin{align}
 \tilde{t}(x)  \approx 0
\end{align}
```
となり、画像の白っぽい場所は、透過マップがゼロになる。

　実際の計算では、パラメータ$\omega(0<\omega<1)$を導入し

```math
\begin{align}
 \tilde{t}(x) = 1 - \omega\min_{c\in{R,G,B}} \left\{ \min_{y\in\Omega(x)} \left\{\frac{I^c(y)}{A^c}\right\}\right\} 
\end{align}
```
を計算する。
　論文では、$\omega=0.95$、patch サイズは$15\times 15$に設定している。


# Soft Matting
　透過マップを洗練させるため（patch の境界を滑らかにするため）、Soft Matting を行う。

 誤差関数を

```math
\begin{align}
E(t) = t^TLt +\lambda (t-\tilde{t})^T (t-\tilde{t})
\end{align}
```
とする。$L$は、Matting Laplacian 行列であり、

```math
\begin{align}
L_{ij} = \sum_{k|(i,j)\in w_k}\left(\delta_{ij}-\frac{1}{|w_k|}\left\{1+(I_i-\mu_k)^T \left(\sigma_k + \frac{\epsilon}{|w_k|} U_3 \right)^{-1}(I_j-\mu_k) \right\}  \right)
\end{align}
```
$w_k$はwindowであり、$I_i$は観測された画像である。例えば、windowを$3\times 3$とすると、$I_i$の成分は、$81(=9\times 9)$個ある。$\mu_k$は$w_k$におけるカラーごとの平均、$\sigma_k$は$w_k$におけるカラーの共分散行列、$\epsilon$は微小量、$U_3$は$3\times 3$の単位行列である。パラメータは、$\lambda\approx10^{-4}$程度である。

 誤差関数を最小化を考えると（$L$は正定値対称行列？）、

```math
\begin{align}
&\frac{\partial E(t)}{\partial t^T}=0 \\
& \Rightarrow  2Lt+\lambda(t-\tilde{t}) = 0 \\
& \Rightarrow  (L+\lambda U )t= \lambda \tilde{t}\\
\end{align}
```
を$t$について解けばよい。係数$2$は、$\lambda$に入れて規格化した。 論文では、共役勾配法を用いて解いている。$t$について解けたので、一般的な霧除去のモデルに戻り、

```math
J(x) = \frac{I(x)-A}{\max(t(x),t_0)}+A
```
を計算すれば、霧が除去された画像が得られる。分母の$\max(t(x),t_0)$は、$t(x)$の値がゼロを取りえるので、$t$の下限を設定している。


# 処理結果

　以下のアドレスから、ダウンロードした霧画像を使い、霧除去を行う。

https://www.pakutaso.com/20150822215post-5836.html

　patch サイズや window サイズは、小さめの$3\times 3$で行った。

　処理を行う霧がかかった画像は、以下の画像である。
![TSU863_kirinosaki_TP_V4.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1521272/07c95149-8a3d-41c1-8550-393d148e6536.jpeg)


　この画像から透過マップを$\tilde{t}$を求めて、可視化してみると以下の画像になり、画像の白い部分が取り除かれていることがわかる。
　![tilde_TSU863_kirinosaki_TP_V4.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1521272/070ccc3d-4a22-6bcd-4bdf-acdf4894cc12.jpeg)

　Soft Matting を使い透過マップ$\tilde{t}$を洗練された$t$は、以下の画像となる。
![t_TSU863_kirinosaki_TP_V4.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1521272/d37a9ff8-965f-f788-c4c8-7c1bec122d3c.jpeg)

　最終的に霧を除去した画像は、以下の画像となる。
![_TSU863_kirinosaki_TP_V4.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1521272/5ae417ff-0a54-d1ff-13aa-9e7cd3cac7d0.jpeg)


# まとめ

画像処理は、奥が深い。