異常検知　SPADE登場からの1年間

# 概要

- SPADE～PaDiM～PatchCoreに関連するリンクとメモです。
- 2021/09/05 まとめて試せるレポジトリの紹介を追加しました。
- 2021/10/09 Gaussian AD の日本語解説記事があったのでリンクを追加。
- 2021/10/26 PatchCoreの処理の流れについて追記しました。
- 2022/06/07 PatchCoreの公式実装公開とスコアの更新について追記しました。→ [リンク](#202267追記-202256にpatchcoreの公式実装が出ました)
 
# この1年の流れ
- この欠陥の検出をニューラルネットワークの再学習なしでしています。しかもSOTA。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/6cd3e845-9027-e998-6d94-6d72b0cfbd2c.png)
- 最近までAutoEncoderが強かったです。
- 2020/05にSPADEが登場しました。
- その後にSOTAを更新しているのはSPADEの派生です。
- Image-levelの精度は99.1%までいってしまいました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/357e034b-6e7b-9a1b-06b1-5017ae32685c.png)

https://paperswithcode.com/sota/anomaly-detection-on-mvtec-ad


# 評価に使うデータ MVTec AD

マシンビジョン業界で有名なHALCONの会社であるMVTECが作ったデータベースです。
2019/06に[CVPRで発表](https://openaccess.thecvf.com/content_CVPR_2019/html/Bergmann_MVTec_AD_--_A_Comprehensive_Real-World_Dataset_for_Unsupervised_Anomaly_CVPR_2019_paper.html)。

- 15のカテゴリー
- 5354枚の画像
- 70種類の欠陥と対応したマスク

せっかくなので、一例をちょっと細かく紹介します。
画像は、15カテゴリー中の一つ「cable（線を剥いてある3芯のケーブル）」のテスト画像です。
70種類の欠陥のうち8種類の欠陥が「cable」で発生します。
それらの欠陥のひとつ「bent_wire（銅線が折れている）」が発生している画像です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/2926605e-96b6-ab6a-0e63-c51a8b6a131e.png)
折れた銅線の画素を白く塗ったマスク画像が用意されています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/c1b3c706-afcd-bcb4-63be-68f8098deac4.png)

良品の画像が手に入りやすい現実を表していて、このパターンの画像はこれが全部と数は少ないです。
cableの良品テスト画像は58枚。トレーニング画像（良品のみ）は224枚。
他もこういう調子で分類されています。


データは[「こちら」](https://www.mvtec.com/company/research/datasets/mvtec-ad/)からダウンロードできる。1時間くらいかかりました。

# 評価指標 ROCAUC/AUROC

論文によって2つの呼び方をしていますが、意味はどちらも同じです。
①ROC area under the curve (ROCAUC)
②the Area Under the Receiver Operating Characteristic curve (AUROC)

こちらの説明が分かりやすいです。しかも小テスト付き。

https://developers.google.com/machine-learning/crash-course/classification/roc-and-auc

今回の問題での例で説明します。PatchCoreの論文に載っているSPADEのROC Curveがこちらです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/6f95ad96-0032-57f5-d606-9660d5ba3a40.png)

グラフの説明
1)異常検知の閾値を変えながらプロットします。
2)縦軸がTure-Positive Rate(検知できた異常画像の数を異常画像全体で割ったもの)
3)横軸がFalse-Positive Rate(誤検知した正常画像（偽陽性）の数を正常画像全体で割ったもの)
4)とても感度が高い（許容する範囲が広い）設定にすると、すべて陽性になってグラフの右上（1，1）に到達します。
5)とても感度が低い（許容する範囲が狭い）設定にすると、陽性になるものが全然なくて、グラフの左下（0，0）に到達します。
6)あとはその間をプロットしています。ランダムなとき（0，0）と（1，1）を結ぶ直線です。青い「grid」の線は間違えすぎてやばい状態です。


すごく上手くいくと下のグラフのようになります。PatchCoreのグラフです。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/9ce01e06-0d34-3f4b-036c-9b42df718a82.png)

そしてこのグラフの下側の面積（≦ 100%）がAUROCです。最初の偽陽性が出るまで感度を高めたときに全てのTure-Positiveが出れば100%です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/f22bc845-ff52-d59f-5d71-6da653ffa099.png)

画像単位で比率をだしていましたが、画素単位での比較もあります。
画像単位のほうをimage-levelと呼んでいます。

# Deep Nearest Neighbor Anomaly Detection [2020/02]

必ず引用されているのがLiron Bergman, Niv Cohen, Yedid Hoshen　の3人の論文。

- 「画像」単位の異常検知
- ImageNetで訓練したResNetを利用する（再訓練なし）
- 正常な画像$y$を変換した特徴量$f_y$を保持する
- 推論では入力した画像の特徴量$f$と$f_y$のk-Nearest Neighbor distanceで判定

の組み合わせが登場します。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/436c4e34-efa6-a85e-df85-859da50d7e23.png)

確かにこの方式の原点ですね。
ただし、異常個所を表すセグメンテーションの表示はまだ出てきません。

https://arxiv.org/abs/2002.10445

# SPADE: Sub-Image Anomaly Detection with Deep Pyramid Correspondences [2020/05]

SPADEは上の論文からBergmanを除いた二人です。
異常個所を表示する拡張をしてSPADEになりました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/3684e2f1-8e48-fb27-f18e-5215c508d84a.png)

- **画素」単位の異常検知 → 異常個所の表示**
- ImageNetで訓練したResNetを利用する（再訓練なし）
- 正常な画像$y$の各画素$p$を変換した特徴量$F(y,p)$を保持する
- 推論では入力した画像の画素の特徴量$f$と$F(y,p)$のk-Nearest Neighbor distanceで判定
- 解像度と深い特徴抽出を両立するために、feature pyramidの各層をconcatする
　![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/8f61b863-8707-e9c7-0d11-dc71f5c7ce3d.png)

メモ

- 評価基準としてMVTec ADデータセットとROCAUCが登場。PROとか短縮したのが分からなくなたらこの論文を見る。
- 入力画像：224x224。出力は１～３ブロック目(56ｘ56，28ｘ28，14ｘ14)の最終層を同じ重みで結合。
- 画素ごとのスコアは[ガウシアンフィルタ](https://pillow.readthedocs.io/en/stable/reference/ImageFilter.html#PIL.ImageFilter.GaussianBlur)($\sigma=4$)でスムージング。

https://arxiv.org/abs/2005.02357v3



公式実装はみつかりませんでした。↓は非公式ですが検出例やグラフが充実しています。

https://github.com/byungjae89/SPADE-pytorch

# Gaussian AD [2020/05]

この論文はICPR2020。読めてないです。

https://arxiv.org/abs/2005.14140


これだけ公式実装があった。

https://github.com/byungjae89/MahalanobisAD-pytorch

2021/10/09追加：日本語解説。なぜ2021/9/10にこれを選んだのだろう？と思いましたが、参考になる内容でした。

https://ai-scholar.tech/articles/error-detection/pretrained_features

# PaDiM: a Patch Distribution Modeling Framework for Anomaly Detection and Localization [2020/11]

SPADEは画素ごとにkNNで距離を出すので推論が遅いです。
それを克服するために正常な画像のデータを統計量にしておくというアイデアで高速化しました。
性能もこの時点でのSOTAです。
**速くなるのはわかるですが、SPADEと比べて性能が一気に上がる理由がよくわかりません。誰か教えてください。**

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/3af15179-d632-088a-df88-2e866846e08a.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/d0fd892d-9219-3558-4b06-c7a2fa548401.png)

- 「画素」単位の異常検知 → 異常個所の表示
- ImageNetで訓練したResNetを利用する（再訓練なし）
- 正常な画像$y$の各画素$p$を変換した特徴量の平均$\mu_{i_j}$ と共分散行列$\Sigma_{ij}$を保持する
- **推論では入力した画像の画素の特徴量$f$とのマハラノビス距離で判定する**
- 解像度と深い特徴抽出を両立するために、feature pyramidの各層をconcatする
- **高速化のために特徴量を削減している。PCAよりランダムサンプリングのほうが性能が良かった。**

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/cb968bb6-f9eb-38c0-8142-5db354cd3600.png)

マハラノビス距離についてはこちらの説明を参照してください。

https://mathwords.net/mahalanobis

https://arxiv.org/abs/2011.08785

やはり非公式実装。　

https://github.com/xiahaifeng1995/PaDiM-Anomaly-Detection-Localization-master

PaDiMの日本語解説。

https://salty-vanilla.github.io/portfolio/post/padim/

https://medium.com/axinc/padim-%E5%86%8D%E5%AD%A6%E7%BF%92%E4%B8%8D%E8%A6%81%E3%81%A7%E4%B8%8D%E8%89%AF%E5%93%81%E6%A4%9C%E7%9F%A5%E3%82%92%E8%A1%8C%E3%81%86%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92%E3%83%A2%E3%83%87%E3%83%AB-69add653fbd3

# PatchCore: Towards Total Recall in Industrial Anomaly Detection [2021/06]

PaDiMとは違った方法で高速化しています。具体的には正常画像を効率的に間引いたサンプルをPatchCoreと呼ばれるモジュールに保持しています。
- Image-levelのAUROCスコア99.1％。データを１%まで間引いてもスコアは99.0％。
- このときのエラーの閾値も従来より低い。
- cold-startという言葉を好んで使っている。one-class classificationを指すとの説明付きだがニュアンスがよくわからない。


ランダムサンプリングと比べて効率的な様子がわかる図です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/e6d1381d-0208-a3bd-b776-b56c2c644b85.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/7cc5449d-12bd-6eb6-8def-c0b4b91435aa.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/cf661ab3-c10b-5038-ffda-2de8473a71be.png)


https://arxiv.org/abs/2106.08265v1

非公式実装が早くも２つ。

https://github.com/hcw-00/PatchCore_anomaly_detection

https://github.com/evanfebrianto/PatchCore-AnomalyDetection

### (2022/6/7追記) 2022/5/6にPatchCoreの公式実装が出ました。
このタイミングで論文にも変更がありスコアが上がっています。
Image-levelのAUROCスコアが99.1％ → 99.6％。
以下が差分です。
・backboneをWide ResNet 50 から 101 に変更。
・画像サイズを(224 x 224)から(320 x 320)に変更。
・加えてDenseNet201とResNext101をアンサンブル。 
・データのサンプリングは100%から1%に下げて速度を確保。

Wide ResNet 50と画像サイズ(224 x 224)は事前学習済みのネットワークを使った先行研究に合わせたものでした。
fastflow（更新直前までのSOTAでnormalizing flowを利用）など別方式の後続の論文に対抗して縛りを緩めたのだと思われます。

https://github.com/amazon-research/patchcore-inspection

# PatchCoreの処理内容 (2021/10/26追記)

## 処理の流れ
1. wide resnet50 の中で2ブロック目（28ｘ28）と3ブロック目（14ｘ14）の出力を使う 
1. 位置に敏感にならないように周囲の特徴量と合わせる。下みたいに書いてるが、実際には単に3x3のglobal average pooling。平均化のサイズ$p = 3$, 
    ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/dafaa1b4-3206-d3db-c703-5a708e05328f.png)
    ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/a9dc94ac-e076-d006-e7b3-03e7c93236f3.png)

1. サンプリングはこんな風に書いているが、間引かず全部集めている。サンプリングのstreide $s = 1$。 
   ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/db465ed4-36b0-5e3e-6081-82bb8811a482.png)

1. 二つのブロックの対応する特徴量をconcatする。方法はPaDiMと同じ。小さいほうをバイリニアで大きくして結合。結局28ｘ28のmapに対応した特徴量になる。 

1. 採用する次元をランダムサンプリングで選んで次元削減する高速化。
   ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/a4ec9ad8-8a26-5589-e182-d063f500323e.png)

1. サンプル数を減らす高速化。貪欲法（サブサンプルの2個目からは今までの選択要素から最も遠いものを選択）で$l$個のサンプルを決める。サブサンプルの個数$l$ はデータに対する比率(1%～）で決める。
    ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/25041d3f-3a51-c686-6b7c-a3a6ff340c2f.png)

## 補足事項

### ランダムサンプリング

Johnson–Lindenstrauss の補題が根拠。
サンプルの数mに対して削減後の次元nが大きければ、ランダムサンプリングが結構高い確率でサンプル同士の距離を再現するといっている。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/f9e786b0-264f-6ab2-4435-66cd3f21ff32.png)

https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma

https://aip.riken.jp/uploads/20190319symposium_16-takeda.pdf

証明はこれがとても丁寧。
http://dopal.cs.uec.ac.jp/okamotoy/lect/2010/metemb/ho4.pdf


以上の背景から以下を使っています。

https://scikit-learn.org/stable/modules/random_projection.html

### 貪欲法で正しくサンプルを選べる？

- k個のサブサンプルで近似したいので、他の全部の点がサブサンプルした点から離れないようにしたいです。このような問題をk-center 問題といいます。
    ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/171e3e40-70e7-f149-288a-1cdf8344286f.png)
    ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/6e74684b-cf6f-8f69-294f-8f962e8fa6d6.png)

- k-centerはNP困難なのだそうです。最適解は諦めて貪欲法で近似します。
    - サブサンプルの2個目からは今までの選択要素から最も遠いものを選択していきます。
- 得られた解は最適解の距離の2倍以内（2近似解）に抑えられます。
    - 三角不等式を使って証明します。
       ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/a99d843d-981b-13ef-0d68-36288be19a52.png)

イラストはこちらから引用しました。

http://satemochi.blog.fc2.com/blog-entry-27.html

2近似解になることについて日本語の証明。ありがたいです。

http://dopal.cs.uec.ac.jp/okamotoy/lect/2017/geomcover/handout04.pdf

https://en.wikipedia.org/wiki/Metric_k-center

コード

https://github.com/hcw-00/PatchCore_anomaly_detection/blob/59b67d9f8dd7a7c9e75203ca57e01cedbb1807ba/sampling_methods/kcenter_greedy.py

# まとめて試せるレポジトリの紹介 (2021/09/05追記)

SPADE, PaDiM, PatchCoreをまとめて実装しているレポジトリがありました。ありがたい。

https://github.com/rvorias/ind_knn_ad

streamlitによるwebアプリが実装されており、手元の写真による評価が簡単です。
↓雑誌の文字と同じ色のペンが乗ってもちゃんと反応していました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/79edaee1-fb27-1952-e9ce-00fb9cdb214e.png)
ただし、ヒートマップの表示は要注意です。色の割り当てを画像１枚ごとに決めています。
なので、正常な画像でもまだら模様を作ってしまいます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/e55fe4b9-3d24-e6f8-8537-0515b51109b6.png)

#### 対策してみた
streamlit_app.pyを改造して固定にしてしまうのが楽そうです。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/69454c45-2cb1-71c8-cd5c-0adc8fad2cc8.png)

しかし、適切な値がモデルと画像ごとに違う。。。GUIを足してみました。緑で囲っている部分です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1017728/d132e311-06a3-15ea-3471-bb7e3f1a9263.png)

~~↓改造を入れたレポジトリです。~~  本家にマージしてもらいました。 

https://github.com/h1day/ind_knn_ad