大津の二値化(判別分析法)の式変形とか
背景
画像処理の勉強をしていたら「判別分析法」という二値化方法が出てきました。
調べて見ると「大津の二値化」の別名らしく、これを機に中身を勉強してみました。
大津の二値化概要
二値化はグレースケール画像を「閾値」を用いて輝度の異なる二つのクラスに分類します。
ここで大津の二値化(判別分析法)とは、閾値をそれっぽくうまく選ぶ手法の一つです。
まず大津の二値化では、クラス内分散とクラス間分散を考えます。
クラス内分散
まずクラス内分散は、各クラスの分散、を用いて
\begin{align}
S^2_w = \frac{n_1}{n} S^2_1 + \frac{n_2}{n} S^2_2
\end{align}
と定義されます。
各クラスの分散が小さくシャープになるような閾値はを小さくします。
クラス間分散
クラス間分散は、各クラスの平均、と全体の平均を用いて
\begin{align}
S^2_b = \frac{n_1}{n} (\mu_1 - \mu)^2 + \frac{n_2}{n} (\mu_2 - \mu)^2
\end{align}
と定義されます。
各クラスの平均値が全体の平均から離れるような閾値はを大きくします。
分離度X
ここで分離度を以下で定義します。
\begin{align}
X = \frac{S^2_b}{S^2_w}
\end{align}
ここで全分散に対して
\begin{align}
S^2 = S^2_b + S^2_w
\end{align}
の関係(あとで導出)を用いると
\begin{align}
X = \frac{S^2_b}{S^2 - S^2_b}
\end{align}
となり、は閾値の位置に依存しないのではにのみ依存します。
閾値tの決め方
大津の二値化では分離度最大となる時の閾値をもっともそれっぽい閾値として選択します。
最大の時にが最大となるので、
が最大となる時の閾値を探しましょう。
数式処理
僕がつまづいたのは
\begin{align}
S^2 = S^2_b + S^2_w
\end{align}
ってなんだよというところです。
そこで色々式変形のあとを残しておきます
の式変形
まずについて、
\begin{align}
S^2_b &= \frac{n_1}{n} (\mu_1 - \mu)^2 + \frac{n_2}{n} (\mu_2 - \mu)^2 \\
&= \frac{n_1}{n} \left( \mu_1^2 -2\mu_1 \mu + \mu^2 \right) + \frac{n_2}{n} \left( \mu_2^2-2\mu_2 \mu + \mu^2 \right) \\
&=\frac{1}{n} \left( n_1 \mu_1^2 + n_2 \mu_2^2 \right) + \frac{n_1 + n_2}{n} \mu^2 -2 \frac{1}{n} \mu \left( n_1 \mu_1 + n_2 \mu_2 \right)
\end{align}
ここで、、より、
\begin{align}
S^2_b &= \frac{1}{n} \left( n_1 \mu_1^2 + n_2 \mu_2^2 \right) + \mu^2 -2 \mu^2 \\
&= \frac{1}{n} \left( n_1 \mu_1^2 + n_2 \mu_2^2 \right) - \mu^2
\end{align}
と表すことができます。上式はあとで使います。
またもうちょっと頑張ると、
\begin{align}
S^2_b &= \frac{1}{n} \left( n_1 \mu_1^2 + n_2 \mu_2^2 \right) - \mu^2 \\
&= \frac{1}{n^2} \left[ n n_1 \mu_1^2 + n n_2 \mu^2 - n^2 \mu^2 \right] \\
&= \frac{1}{n^2} \left[ \left(n_1 + n_2 \right) n_1 \mu_1^2 + \left(n_1 + n_2 \right) n_2 \mu^2_2 - \left( n_1 \mu_1 + n_2 \mu_2 \right)^2 \right] \\
&= \frac{1}{n^2}\left[ n_1 n_2 \mu_1^2 + n_1 n_2 \mu_2^2 + \left( n_1^2 \mu_1^2 + n_2^2
\mu_2^2 \right) - \left( n_1^2 \mu_1^2 + n_2^2 \mu_2^2 + 2n_1 n_2 \mu_1 \mu_2 \right) \right] \\
&= \frac{n_1 n_2}{n^2} \left( \mu_1^2 -2 \mu_1 \mu_2 + \mu_2^2 \right) \\
&= \frac{n_1 n_2}{n^2} \left( \mu_1 - \mu_2 \right)^2
\end{align}
となります。この式はよく見かけますね。実際使うときもこの形が楽です。
全分散の導出
について式変換しておきます。
\begin{align}
S^2_1 &= \frac{1}{n_1} \sum_1 \left( x_i - \mu_1 \right)^2 \\
S^2_2 &= \frac{1}{n_2} \sum_2 \left( x_i - \mu_2 \right)^2
\end{align}
から、
\begin{align}
S^2_w &= \frac{n_1}{n} S^2_1 + \frac{n_2}{n} S^2_2 \\
&= \frac{1}{n} \left[ \sum_1 \left( x_i - \mu_1 \right)^2 + \sum_2 \left( x_i - \mu_2 \right)^2 \right] \\
&= \frac{1}{n} \left[ \sum_1 \left( x_i^2 -2 \mu_1 x_i + \mu_1^2 \right) + \sum_2 \left( x_i^2 -2 \mu_2 x_i + \mu_2^2 \right) \right] \\
&= \frac{1}{n} \left[ \left( \sum_1 x_i^2 + \sum_2 x_i^2 \right) -2 \left( \mu_1 \sum_1 x_i + \mu_2 \sum_2 x_i \right) + \left( \mu_1^2 \sum_1 1 + \mu_2^2 \sum_2 1 \right) \right] \\
&= \frac{1}{n} \left[ \sum_{all} x_i^2 -2 \left( n_1 \mu_1^2 + n_2 \mu_2^2 \right) + \left( n_1 \mu_1^2 + n_2 \mu_2^2 \right) \right] \\
&= \frac{1}{n} \sum_{all} x_i^2 -\frac{1}{n} \left( n_1 \mu_1^2 + n_2 \mu_2^2 \right)
\end{align}
やっと準備が整いました。
\begin{align}
S^2_w &= \frac{1}{n} \sum_{all} x_i^2 -\frac{1}{n} \left( n_1 \mu_1^2 + n_2 \mu_2^2 \right) \\
S^2_b &= \frac{1}{n} \left( n_1 \mu_1^2 + n_2 \mu_2^2 \right) - \mu^2
\end{align}
から、
\begin{align}
S^2_b + S^2_w &= \\
&= \frac{1}{n} \sum_{all} x_i^2 - \mu^2 \\
&= \frac{1}{n} \left[\sum_{all} x_i^2 - n \mu^2 \right] \\
&= \frac{1}{n} \left[\sum_{all} x_i^2 - 2 n \mu^2 + n\mu^2 \right] \\
&= \frac{1}{n} \left[\sum_{all} x_i^2 - 2 n \mu \left( \frac{1}{n} \sum_{all} x_i \right) + n\mu^2 \right] \\
&= \frac{1}{n} \left[\sum_{all} x_i^2 - 2 \mu \sum_{all} x_i + \mu^2 \sum_{all} 1 \right] \\
&= \frac{1}{n} \left[\sum_{all} \left( x_i^2 -2 \mu x_i + \mu^2 \right) \right] \\
&= \frac{1}{n} \sum_{all} \left( x_i - \mu \right)^2 \\
&= S^2
\end{align}
やっとでました。
疲れたよもう