概論 : 特徴検出・領域分割・パターン認識

情報科の講義で扱われた内容の整理メモです。
数学的厳密性はあまりありませんのであしからず。

#目次
1.特徴検出
2.領域分割
3.パターン認識基礎
4.おまけ-行列の計算

#1. 特徴検出

• テンプレートマッチング
• 特徴検出
• 線形フィルタ
• ガウシアンフィルタ
• 特徴VectorとSIFT特徴
• Hough変換

###テンプレートマッチング
【概要】入力画像から物体を検出するための手法

point. 手順
1: 入力画像をラスタスキャン(左から右・上から下に1画素ずつ走査)
2: 入力画像とテンプレート(走査対象)との類似度を比較し
3: 類似度 > 閾値 となった部分を出力

point. 相違度/類似度について
相違度SSD，相違度SAD，類似度NCCの3つがある
(相違度は似ていないと値が大きくなる．類似度は似ていると値が大きくなる)
・相違度SSD ... 画素差の二乗和
・相違度SAD ... 画素差の絶対値和
・類似度NCC ... 内積cosの求値(スカラー和/二乗和root二乗和root)

advanced. 連続値による検出
通常の方法では離散値による検出だが，連続値(サブピクセル)による検出も可能
・等角直線フィッティング
・パラボラフィッティング

advanced. 高速化
計算量を減らすことで高速化を得る
・残差逐次検定
・粗密探査法

###特徴検出
【概要】入力画像の特徴となる角(コーナー)や境界を検出する方法
利用例) 物体追跡

###特徴検出A. ハリスのコーナー検出
【概要】コーナーとエッジの検出方法

point. 手順A
0: Structure Tensor Matrix の固有値に角だと思われる値を定義
1: 入力グレースケール画像の各画素の下記値を計算
  ・Structure Tensor
  ・固有値
2: 上の2値からR値を計算
3: R = Maxima && R > 閾値 となった部分を出力

point. 手順B (固有値を計算しない方法)
1: 入力グレースケール画像の各画素の Structure Tensor を計算
2: det A・tr A を計算
    (detA = ab - dc = λ1*λ2)
    (trA = a + d = λ1 + λ2)
3: 上の2値からR値を計算
    R = detA - k(trA)^2 ( k : 任意パラメタ)
4: Maxima = R && R > 閾値 となった部分を出力

point. StructureTensorMatrix
輝度値変化に関する特徴を得る特殊な行列のこと．求値方法は割愛

###特徴検出B. ケニーの輪郭検出
【概要】境界の検出方法

point. 手順
1: 入力画像にガウシアンフィルタをかける
2: 勾配強度と勾配方向を計算する
3: 勾配強度 = Maxima となる各画素において
    if ( x > 画素p && x > 画素q ) x == 0
  と各勾配強度の比較計算を行う
  (最も勾配強度が強いものだけを残す処理)
4: 閾値処理により境界判断を行う

###補足. 線形フィルタ
【概要】周辺の重み付き和により画像を加工することができる
利用例) ぼかす・先鋭化する

###補足. ガウシアンフィルタ
【概要】ガウス関数により畳み込むことで画像を平滑化できる

point. 特徴
・低周波成分のみを通すローパスフィルタとなる
・ガウス関数->(フーリエ変換)->ガウス関数
・複数のガウシアンフィルタはひとつにまとめられる

###特徴vectorとSIFT特徴
【概要】画像同士の似た場所の対応付けを行う方法

対応付けに適すると判断された「特徴点」の周囲をVector化して値として扱えるようにした「特徴Vector」を用いて比較を行う

回転・拡大縮小・並行移動に変化をできるだけ少なく対応したVectorが望ましい => SIFT特徴 を利用

point. SIFT特徴
DoGというアルゴリズムを用いることで，特徴点の大小に合わせて検出を行う窓の大きさが決定されるため拡大縮小に対応．
また，検出された特徴点から36等分された方向を計算しその方向に合わせて検出を行う窓を回転させるので回転に対しても対応

###Hough変換
【概要】直線や円の検出方法

point. 特徴
・直線や円の一部が壊れていても検出することが可

point. 手順
0: 直線や円を数式で表す
1: 入力画像からエッジ画像を出力
2: 全エッジ画像において計算をする
3: パラメタ空間に置いて値の大きなセルを検出

#2. 領域分割

• 画像領域分割概要
• 閾値法(大津法)
• 領域成長法
• クラスタリング(k-means法)
• 識別器
• グラフカット法(フローネットワーク)
• 動的輪郭モデル
• 局面再構成法
• モーフォロジー演算
• オプティカルフロー

###閾値法(大津法)
【概要】閾値の前後で前景・背景に分ける方法

自動的に閾値を求めるアルゴリズムの代表例として
  Pタイル法・大津法・Sauvola法
がある。

point. 手順
1: 入力画像からヒストグラムを出力
2: 閾値t候補を[1, 256]範囲で動かし分離度を計算
    分離度 = クラス間分散/クラス内分散
3: 分離度が最大となるところを閾値tと決定する

● 分離度最大 ≒ クラス間分散; 大 ≒ クラス内分散; 小
● 黒/白両領域の距離が大きく(山と山が遠く)なるように閾値を選択
    ≒ クラス間分散; 大
● 黒/白両領域の分散が小さく(山が細く)なるように閾値を選択
    ≒ クラス内分散; 小

point. 大津法の特徴
・ヒストグラムの双方性(山ふたつっぽさ)の低いもの/グラデーションには弱い
  <= 二値化を用いたアルゴリズムのため
  => 解決策として Adaptive thresholding を用いる

###領域成長法

【概要】画像を二値/多値の領域に分ける方法

point. 手順
1: 画像上に1点(seed)を手動または自動で用意する
2: 境界規則に達するまで前景領域を成長させる

point. 領域成長法の特徴
・ボケた(似た)境界には弱い

###クラスタリング(k-means法)

パス

###識別器

パス

###グラフカット領域分割(フローネットワーク)

【概要】フローネットワークを利用した領域分割

point. 手順
1: 画像上に前景と背景の2点を指定する
2: 境界をネットワークを用いて計算しながら，各画素を前景と背景にいい感じで分類する

cf. ネットワークのカット
フローネットワークにおいて「カットの容量」とは，グラフをS側/T側に分断した際，分断ラインをまたぐコストのうち S->T 片方向 のみの和のことを指す．
T->S向きとなる逆方向の流れに関しては =0 とみなす

point. グラフカット領域分割の特徴
・良 ) 高速かつ高精度
・良 ) 高次元化しやすい
・良 ) UIとの相性が良い
・良 ) 塊のような領域には強い
・悪 ) ボケた(似た)境界/小さい細い薄い境界には弱い

###動的輪郭モデル
【概要】領域境界を少しずつ変形して分割を行う領域分割

エッジを通るように境界領域をなめらかに変化させる

境界を表現する方法で
  Snakes法・Level Set法
の2種類がある

手法	境界表現	ノイズ	高速性	トポロジー変化	実装性
Snakes法	陽的	強い	速い	不可	易
LevelSet法	陰的	強い	速い	可	難

手法	その他の特徴
Snakes法	パラメタや初期輪郭線に強依存
LevelSet法	速度の選択が難

「陽的に表現」 ... ポリライン(頂点と線分)/ポリゴンメッシュで結ぶこと
「陰的に表現」 ... 高次元のスカラー場で結ぶこと

###局面再構成法
パス

###モーフォロジー演算
【概要】集合論の概念によりノイズの除去を行う画像処理法

集合A-入力画像 と 集合B-StructureElement に
  膨張('Dilation')処理・収縮('Erosion')処理
というニ演算をかける

point. 膨張と収縮
「膨張」... 外側を辿り輪郭を描く ; 画像が一回り太る
「収縮」... 内側を動き塗りつぶしをする ; 画像が一回り痩せる

point. 膨張と収縮の組み合わせ
「オープニング (収縮->膨張)」... 外側(前景)の点や線などのゴミを消去
「クロージング (膨張->収縮)」... 内側(背景)の穴などのゴミを消去

advanced. Top-hat Transform
オープニングやクロージングをかけた画像と元画像の差分によって，邪魔なグラデーションを消去する方法

手法	計算方法	消せる曖昧な境界
TopHat法	元画像 - opened	暗い背景との境界
BottomHat法	closed - 元画像	明るい背景との境界

###オプティカルフロー
【概要】移動をVector量とすることでトラッキングを行う動画処理法

オプティカルフローのアルゴリズム例として
  ブロックマッチング法・ルーカス･カナデ法
がある

point. ブロックマッチング法
前フレームにおける注目点を中心とした窓を用いて，次フレームをトレースする方法．計算量 : 大

cf. 擬似逆行列
連立方程式が解ける/解けないに関わらず，全ての方程式をなるべく満たす解を得る解き方

\begin{pmatrix}
1 & 2 \\
3 & 4 \\
5 & 6
\end{pmatrix}
\begin{pmatrix}
x  \\
y \\
\end{pmatrix}
=
\begin{pmatrix}
1 \\
2 \\
3
\end{pmatrix}

を

A
\begin{pmatrix}
x  \\
y \\
\end{pmatrix}
=
b

と表したとき

\begin{pmatrix}
x  \\
y \\
\end{pmatrix}
=(A^{\mathrm{T}}A)^{\mathrm{-1}}A^{\mathrm{T}}b

で解く

#3. パターン認識基礎

• クラス分類概要
• プロトタイプ法
• kNN法
• 決定木
• SVM
• パーセプトロン
• ニューラルネットワーク
• 主成分分析
• オートエンコーダー

###クラス分類概要
【概要】様々なデータをタイプ別に分類すること．教師あり学習

最終工程の識別処理に様々な方法が存在する
例 ) プロトタイプ法・K-近傍法・決定木・SVM・NN

point. 手順
1: 前処理
2: 特徴抽出
3: クラス分類

###プロトタイプ法 (withマハラノビス距離)

各教師データラベルの重心のような代表点を「プロトタイプ」として設定して，求めたいデータに一番近いものを探しラベルを決定する方法．最も単純なクラス分析

集合具合が密のクラスと疎のクラスをEuclid距離で "一番近い" を探すのは微妙 => 分散を利用した マハラノビス距離 を利用

point. マハラノビス距離

class:p = 
\begin{pmatrix}
x_{p} \\
y_{p} \\
\end{pmatrix}
,
data = 
\begin{pmatrix}
x_{d} \\
y_{d} \\
\end{pmatrix}
,
分散共分散行列:S = 
\begin{pmatrix}
a & b \\
c & d \\
\end{pmatrix}

Euclid距離 :

\sqrt{
\begin{pmatrix}
x_{p} - x_{d} \\
y_{p} - y_{d} \\
\end{pmatrix}
^\intercal
*
\begin{pmatrix}
x_{p} - x_{d} \\
y_{p} - y_{d} \\
\end{pmatrix}
}

マハラノビス距離 :

\sqrt{
\begin{pmatrix}
x_{p} - x_{d} \\
y_{p} - y_{d} \\
\end{pmatrix}
^\intercal
*
S^{-1}
*
\begin{pmatrix}
x_{p} - x_{d} \\
y_{p} - y_{d} \\
\end{pmatrix}
}

cf. 単位行列風な形の2x2逆行列
単位行列風な形の2x2逆行列は結果を知ると暗算で求めることができる

\begin{pmatrix}
a & 0 \  \\
0 & a \\
\end{pmatrix}
^{-1}
=
\frac{1}{a*a-0*0}
\begin{pmatrix}
a & -0 \  \\
-0 & a \\
\end{pmatrix}
=
\begin{pmatrix}
\frac{1}{a} & 0 \\
0 & \frac{1}{a} \\
\end{pmatrix}

###kNN (k-近傍法)

教師データ数が十分多い上で，求めたいデータから距離が最も近い設定したk個のデータで所属に関する多数決を行いラベルを決定する方法

point. kNN法の特徴
・良 ) 精度が高い
・悪 ) 十分な教師データ数を必要とするためメモリ消費が大きい
・悪 ) 下手な実装をするとありとあらゆる距離を求めるため計算量が増える

###決定木

空間の分割を二分木で表現

###SVM

空間の分割を線形的(直線/超平面)に表現

###パーセプトロン

ニューロンの振る舞いを利用して空間の分割を線形的に表現
これを並列/直列につなぎ層状にすることで線形分離不可能なデータ群を線形分離可能な状態に落とし込むことができる => ニューラルネットワーク

###ニューラルネットワーク

パス

###主成分分析
【概要】データ群におけるばらつきの最も大きな線を見つける方法

様々なクラス分類の次元削減に利用ができる

point.手順
0: データ郡のプロット
1: 平均値が原点となるように平行移動
2: 分散共分散行列行列を計算
3: 各データを固有Vectorに射影し第一主成分得点を求値

point. 第一主成分得点
解釈付けのしやすい特徴的な量を表す
第一主成分得点 = (Vdata - Vmed)･Vu

第一主成分得点 = 
\left(
\begin{pmatrix}
d_{1} \\
d_{2} \\
\dots \\
d_{n}
\end{pmatrix}
-
\begin{pmatrix}
m_{1} \\
m_{2} \\
\dots \\
m_{n}
\end{pmatrix}
\right)
\cdot
\begin{pmatrix}
u_{1} \\
u_{2} \\
\dots \\
u_{n}
\end{pmatrix}\\
=
(d_{1}-m_{1})*u_{1}+(d_{2}-m_{2})*u_{2}+\dots+(d_{n}-m_{n})*u_{n}

**advanced. 次元削減** 寄与率 (=k番目方向までの分散/全方向の分散) がある程度以上となる最小の次元kまで圧縮が可能

###オートエンコーダー

【概要】ニューラルネットワークの一種でデータの特徴解析に特化した手法

NN内の重みパラメタを読むことで特徴を抽出する
利用例 ) 次元削減・deep learning の前処理

出力結果を必要としないため，NNと異なり教師データを利用しない

#4. おまけ-行列の計算

A = 
\begin{pmatrix}
a & b \\
c & d \\
\end{pmatrix}

で考える

###行列式 detA 2x2

det A = ad-bc

###逆行列 Aインバース 2x2

A^{\mathrm{-1}}=
\frac{1}{ad-bc}
\begin{pmatrix}
d & -b \\
-c & a \\
\end{pmatrix}