スパース性と圧縮センシング その②

# はじめに
[前回記事](https://qiita.com/bokuikkun/items/8761de4fab6ac64db1a6)では圧縮センシングの概要と二音信号を用いた復元のデモを行った。本稿では、スパース表現行列$\boldsymbol{\Psi}$に焦点を置いてさらに掘り下げた実験を行ってみる。

# スパース表現の概要
自然データにみられる固有の構造は、データがある適当な座標系でスパースに表現できる。つまり、***高次元の自然データが低次元の構造を持つ場合、適切な基底や辞書を使ってスパースな表現が可能になる***、という前提に基づく。例えば、信号がSVDやフーリエ規程のような特定の基底に対してスパースである場合に加えて、訓練データそのものから構成されるオーバーコンプリート辞書（overcomplete dictionary）に対してもスパースで表現できることがある。

Wrightらの研究では、このスパース表現を用いた、分類のためのスパース表現（SRC: Sparse Representation for Classification）が、ノイズや遮蔽（=マスキング）がある場合でも顔認識の精度を向上させることを示した。以下から、例としてYale B databaseを用いてオーバーコンプリート辞書の構築とノイズや遮蔽があるケースでの画像認識の精度検証を行う。

Yale B databaseのデータの中身については[こちらの記事](https://qiita.com/bokuikkun/items/9195fee5fabdfbe91897#eigenfaces%E3%83%87%E3%83%BC%E3%82%BF%E3%82%BB%E3%83%83%E3%83%88%E3%81%AB%E3%82%88%E3%82%8B%E5%9B%BA%E6%9C%89%E9%A1%94%E3%81%AE%E8%A8%88%E7%AE%97)で少し触れている。

## SRCの概略

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/53479c6f-8a9f-a9c9-30a5-85404a3e81ea.png)

上記図のように、SRCによる分類手法はスパースベクトル$\boldsymbol{s}$が特定の人物に対応（faces行列の列添字がそれに該当）するように大きな係数をもつ持つことになる。即ち、以下の凸$\ell_1$-最小化問題を解けば良い。

```math
\begin{align}
\begin{cases}
{\rm 目的関数:}\quad&\hat{\boldsymbol{s}}
=\mathop{\rm arg~min}\limits_{\boldsymbol{s}}\|\boldsymbol{s}\|_1 \\
{\rm 制約条件:}\quad&\boldsymbol{y}
=\boldsymbol{\Theta s}
\end{cases}
\end{align}
```

ここで、$\boldsymbol{\Theta}$は全ての訓練データから構成されるオーバーコンプリート辞書である。

## デモコード

### ライブラリのインポート
まずはライブラリのインポート

```python
# Import libraries
import random

import numpy as np
import matplotlib.pyplot as plt
import scipy.io
from scipy.optimize import minimize
from skimage.transform import resize
from matplotlib.image import imread
plt.rcParams['figure.figsize'] = [7, 7]
plt.rcParams.update({'font.size': 18})
```

### データの読み込み
Yale B databaseを読み込む。これは```allFaces.mat```の```faces```というキーに1つの行列として格納されている。
この行列は二次配列がflattenされたものが列ベクトルとして格納されており、そのサイズは$(192_{(高)}\times168_{(横)})\times 2,410_{(サンプル数)}$となっていることに留意

```python
# Read data
contents = scipy.io.loadmat('../../data/allFaces.mat')
X = contents['faces']
nfaces = contents['nfaces'].reshape(-1)
m = int(contents['m'][0,0])
n = int(contents['n'][0,0])
```

上記コードで```cfaces```には38名のデータ数がリストとして格納されている。
例えば、$n$人目の最初のインデックスを取得する関数を作成して、実際に6人目（=インデックスは5）の最初のデータを出力してみると下記のようになる。

```python
def get_offset(n, _nfaces=nfaces):
    return sum(_nfaces[:n])


plt.imshow(
    np.reshape(contents['faces'][:, get_offset(5)], (m, n)).T,
    cmap='gray'
)
plt.axis('off')
plt.show()
```

出力結果は以下の通り。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/b838cdd8-ef91-bf6e-a86f-43c8884843c5.png)

### データセット作成
続いて、訓練データセットとテストデータセットを作成する。
バラつきはあるが、同一人物の画像データ（光の当たり具合や表情が微妙に変わっている）は60枚強あるので、ひとり当たり訓練データ数を```nTrain=30```、テストデータ数を```nTest=20```として38名中ランダムで20人（=```nPeoples```）で選択し抽出する。
当然、訓練データとテストデータには重複が生じ無いように配慮して、```random_split```など適当な関数を実装

```python
# Build Training and Test sets
nTrain = 30
nTest = 20
nPeople = 20

peoples = random.sample(range(len(nfaces)), nPeople)
Train = np.zeros((m*n, nTrain*len(peoples)))
Test = np.zeros((m*n, nTest*len(peoples)))


def random_split(n, _nTrain=nTrain, _nTest=nTest):
    train_idxs = random.sample(n, _nTrain)
    remainings = [num for num in n if num not in train_idxs]
    test_idxs = random.sample(remainings, _nTest)
    return train_idxs, test_idxs


for i, p in enumerate(peoples):
    offset = get_offset(p)
    idxs = range(offset, offset+nfaces[p])
    train_idxs, test_idxs = random_split(idxs)
    Train[:, i*nTrain:(i+1)*nTrain] = X[:, train_idxs]
    Test[:, i*nTest:(i+1)*nTest] = X[:, test_idxs]
```

### ダウンサンプリングとオーバーコンプリート辞書の作成
さて、訓練データセットとテストデータセットを作成できたところで、本節冒頭で記載したSRC概略図のダウンサンプリングを実施する。
scikit-imageの[skimage.transform](https://scikit-image.org/docs/stable/api/skimage.transform.html#skimage.transform.resize)を用いたが、正直画像リサイズのアルゴリズムは良くわかっていない。が、どうやら局所平均を取る（厳密には何らかの方法で新しい数値を補完してるらしい）ことによるダウンサンプリングを行なっているようだ。引数```anti_aliasing```をTrueにすることで、前処理にガウシアンフィルタを適用し、局所平均化によるノイズを軽減している。
今回は幅を$168\rightarrow10$、高さを$192\rightarrow12$へと変更し、リサイズした訓練データを全て束ねることによって、オーバーコンプリート辞書$\boldsymbol{\Theta}$を構築する。

```python
# Downsample Training Images (Build Theta)
M = nTrain*nPeople
sm = 10
sn = 12
Theta = np.zeros((sm*sn, M))

for k in range(M):
    temp = np.reshape(np.copy(Train[:, k]), (m, n))
    sampled = resize(temp, (sm, sn), anti_aliasing=True)
    Theta[:, k] = np.reshape(sampled, (sm*sn,))
```

これで作成された$\boldsymbol{\Theta}$のサイズは行$120=10_{\rm (sm)}\times12_{\rm (sn)}$、列$600=30_{\rm (nTrain)}\times20_{\rm (nPeople)}$となっている。

### 画像データの再構築と分類
では、6人目の最初のテストデータを復元してみよう。因みに、ランダムで選択した20名のリストの6人目は以下のような画像データである。

```python
plt.imshow(
    np.reshape(contents['faces'][:, get_offset(peoples[5])], (m, n)).T,
    cmap='gray'
)
plt.axis('off')
plt.show()
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/94f404db-3791-5447-11b6-f56d64e16fac.png)

訓練データと同様に、一度リサイズしてからflattenし、それを観測データ$\boldsymbol{y}_1$とする。

```python
# Downsample Test Images
sample_test = nTest*5
t1 = np.copy(Test[:, sample_test])  # Clean image
temp = np.reshape(np.copy(t1), (m, n))
sampled = resize(temp, (sm, sn), anti_aliasing=True)
y1 = np.reshape(sampled, (sm*sn,))
```

これを用いて、凸$\ell_1$-最適化を解く。

```python
# L1 Search, Testclean
eps = 0.01

# L1 Minimum norm solution s_L1
def L1_norm(x):
    return np.linalg.norm(x, ord=1)


constr = ({
    'type': 'ineq',
    'fun': lambda x:  eps - np.linalg.norm(Theta @ x - y1, 2)
})
x0 = np.linalg.pinv(Theta) @ y1  # initialize with L2 solution
res = minimize(
    L1_norm, x0,
    method='SLSQP',
    constraints=constr,
    options={'maxiter': 4000, 'disp': True}
)
s1 = res.x
```

この処理は10分程度掛かってしまうが、うまく動作すると以下のような出力を得る。

```shell
Optimization terminated successfully    (Exit mode 0)
            Current function value: 2.7742555744517174
            Iterations: 2656
            Function evaluations: 1601941
            Gradient evaluations: 2656
```

ここで、```Current function value```が経験的に小さい値である程良い結果が得られている。これで得たスパースベクトル$\boldsymbol{s}$を描画してみる。

```python
plt.plot(s1)
plt.show()
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/99a8a9bb-c5ca-88c0-7157-4aad6aed64e0.png)

可視化してみると、スパースとは言えないが、インデックス=169付近でピークがあり、特定の人物を特徴付けられていることが分かる。

次に、```Theta```の代わりに```Train```を用いて、$\boldsymbol{s}$からオリジンサイズのデータを復元してみる。

```python
plt.imshow(np.reshape(Train @ (s1),(m,n)).T,cmap='gray')
plt.axis('off')
plt.show()
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/8fcac342-29d1-c2a4-907e-429ed26bf311.png)

見た目では比較できないので、元データと復元データの差分を描画

```python
plt.imshow(np.reshape(t1 - Train @ (s1),(m,n)).T,cmap='gray')
plt.axis('off')
plt.show()
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/a81dad4e-27f4-fcb6-dbe3-f4ac0ba72a01.png)

ガウシアンフィルタを前処理として加えたとは言え、やはりエッジでの差分が目立つ。とは言え、人が観察する分には十分に復元できており、特定の人物であることが判定できる精度だと感じている。

最後に誤差の定量評価を行う。選択された20名の人物に対して、復元データとの相対誤差を計算して、棒グラフで可視化してみる。

```python
binErr = np.zeros(nPeople)
for k in range(nPeople):
    L = range(k*nTrain, (k+1)*nTrain)
    binErr[k] = np.linalg.norm(t1-Train[:, L] @ (s1[L]))/np.linalg.norm(t1)

plt.bar(range(nPeople), binErr)
plt.show()
```

結果は以下の通り。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/1c9dbf31-52f2-51d2-e018-916681984808.png)

インデックス=5（つまり、6人目）の箇所で誤差が明らかに小さくなっており、正解である、特定の人物である可能性が高いことが示唆できている。

### マスキングデータからの再構築と分類
次に、画像に一部マスキングがある場合の元画像の復元および人物の分類を行ってみる。マスキングは口髭のデータを使って単純に直積を取ることで実現する。

```python
# Read occulated data (fake mustache)
mustache = imread('../../data/mustache.jpg')
mustache = np.mean(mustache, -1)
mustache = (mustache/255).astype(int)
mustache = mustache.T
```

実際にどんな画像かを可視化してみる。

```python
plt.imshow(mustache.T,cmap='gray')
plt.axis('off')
plt.show()
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/07d6ec18-6af5-12f0-dfd4-e0fda6836585.png)

このバイナリの巻きひげデータとテストデータの直積を取る。

```python
# Downsample Test Images with Mustache mask
t2 = np.copy(Test[:, sample_test]) * mustache.reshape(n*m)
temp = np.reshape(np.copy(t2), (m, n))
sampled = resize(temp, (sm, sn), anti_aliasing=True)
y2 = np.reshape(sampled, (sm*sn,))
```

```python
plt.imshow(np.reshape(t2,(m,n)).T,cmap='gray')
plt.axis('off')
plt.show()
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/7b340bd5-a8ce-667f-f3bf-4fa7c1415257.png)

このテストケースを用いて、先ほど同様に$\ell_1$-最適化を行う。

```python
## L1 Search, Mustache
eps = 100
constr = ({
    'type': 'ineq',
    'fun': lambda x:  eps - np.linalg.norm(Theta @ x - y2, 2)
})
x0 = np.linalg.pinv(Theta) @ y2  # initialize with L2 solution
res = minimize(
    L1_norm, x0,
    method='SLSQP',
    constraints=constr,
    options={'maxiter': 4000, 'disp': True}
)
s2 = res.x
```

この出力結果は以下の通り。

```shell
Optimization terminated successfully    (Exit mode 0)
            Current function value: 6.845300326650376
            Iterations: 3434
            Function evaluations: 2070360
            Gradient evaluations: 3434
```

さて、まずは得られたスパースベクトル$\boldsymbol{s}$の分布を見てみる。

```python
plt.plot(s2)
plt.show()
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/777e28ed-3e9f-dae2-9be5-595eaef361fe.png)

この結果を見ると、顕著なピークが2つあり、その他の要素でもバラつきがあることが確認できる。
次に復元されたデータを描画する。

```python
plt.imshow(np.reshape(Train @ (s2),(m,n)).T,cmap='gray')
plt.axis('off')
plt.show()
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/5ef039d1-40fc-d904-2adc-421936a7ddb5.png)

かなり不気味なAIチックな仕上がりになってしまった。元ニキとAIニキの差分を見てみる。

```python
plt.imshow(np.reshape(t2 - Train @ (s2),(m,n)).T,cmap='gray')
plt.axis('off')
plt.show()
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/0e7011b7-6d02-dcfe-0344-89d5675ce992.png)

髭は勿論、ノイズなので明らかだが顔全体が比較的誤差として現れてしまっているように感じる。精度の定性評価としてはイマイチといったところだろうか。
最後に定量的な評価も観察する。

```python
binErr = np.zeros(nPeople)
for k in range(nPeople):
    L = range(k*nTrain, (k+1)*nTrain)
    binErr[k] = np.linalg.norm(t2-Train[:, L] @ (s2[L]))/np.linalg.norm(t2)

plt.bar(range(nPeople), binErr)
plt.show()
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/2d2c1223-06db-6d6a-2fcf-ab91026a830e.png)

このグラフだけ観察して、エラー最小の人物のラベルはインデックス=4と正解であるインデックス=5と異なっているが、5の方も次いで小さい値を取っている。
その他では、インデックス=14、16あたりが特徴として目立っている。この巻きひげのようなマスキングのケースは既存の辞書だけで表現するのは少し分が悪いといった所感である。

### オクルージョンデータからの再構築と分類
今度は、画像データの一部のピクセルを選択してランダムな値に置き換える、オクルージョンと呼ばれる欠損処理を施したテストデータを用いる。

```python
# Occlude Test Image
def occlude(x, ratio=0.3):
    randvec = np.random.permutation(n*m)
    first_ratio = randvec[:int(np.floor(ratio*len(randvec)))]
    vals_ratio = (255*np.random.rand(*first_ratio.shape)).astype(int)
    _x = np.copy(x)
    _x[first_ratio] = vals_ratio
    return _x


t3 = occlude(t1)
temp = np.reshape(np.copy(t3), (m, n))
sampled = resize(temp, (sm, sn), anti_aliasing=True)
y3 = np.reshape(sampled, (sm*sn,))
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/47e103ad-49c7-d84a-f56f-52c020c10f6b.png)

このように画像の30%のピクセルがランダムに選択され、0~255の適当の値に置換される。

```python
## L1 Search, Occlusion
eps = 100
constr = ({
    'type': 'ineq',
    'fun': lambda x:  eps - np.linalg.norm(Theta @ x - y3, 2)
})
x0 = np.linalg.pinv(Theta) @ y3  # initialize with L2 solution
res = minimize(
    L1_norm, x0,
    method='SLSQP',
    constraints=constr,
    options={'maxiter': 4000, 'disp': True}
)
s3 = res.x
```

```shell
Optimization terminated successfully    (Exit mode 0)
            Current function value: 0.8741597687516052
            Iterations: 2739
            Function evaluations: 1652772
            Gradient evaluations: 2739
```

得られたスパースベクトル$\boldsymbol{s}$の分布を見てみる。

```python
plt.plot(s3)
plt.show()
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/ff44f07e-4f47-4aa9-1b9c-84193f636eb9.png)

スパース性は良好であるが、複数の要素でピークが立っており、特定の個人だけで特徴付けられているとは言い難い。
次に、復元データおよび元データとの差分データを可視化してみる。

```python
plt.imshow(np.reshape(Train @ (s3),(m,n)).T,cmap='gray')
plt.axis('off')
plt.show()

plt.imshow(np.reshape(t3 - Train @ (s3),(m,n)).T,cmap='gray')
plt.axis('off')
plt.show()
```

出力結果はそれぞれ以下の通り。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/20fc988b-2247-e1a5-1fb8-7b6ec9f57b41.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/27a05d55-c415-806d-d09e-207fdf6febdd.png)

差分の可視化結果を見ると、加えたノイズとエッジは目立つが総じてエラーは小さそうである。
最後に定量評価を観察

```python
binErr = np.zeros(nPeople)
for k in range(nPeople):
    L = range(k*nTrain, (k+1)*nTrain)
    binErr[k] = np.linalg.norm(t1-Train[:, L] @ (s3[L]))/np.linalg.norm(t3)

plt.bar(range(nPeople), binErr)
plt.show()
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/409783/2d369275-2ae5-12de-6030-80b61bf06d1d.png)

スパースベクトル$\boldsymbol{s}$が複数のピークを持っていたので、エラーもまちまちだが、インデックス=5の人物が最小となっているので、結果としては悪くは無いようである。

# おわりに
今回は圧縮センシングとオーバーコンプリート辞書を用いた画像の分類デモンストレーションを行った。ダウンサンプリングと、取得した情報はかなり少ないものの、人間が観察する分には復元精度は割と良さそうである。
また、ノイズやマスキングを加えたテストデータによる検証も行ったが、ノイズにはある程度頑健だが、マスキングには向かないことが分かった。