ダイナミックプログラミング

最大尤度しきい値選定法を多値化の場合に拡張することは容易である。各画素を $k-1$ 個のしきい値 $\{k_1,\ldots,k_{K-1}\}$ によって $K$ クラス $\{C_1,\ldots,C_K\}$ に分類することを考える。ここで、各 $C_j \ \ \ (j=1,\ldots,K)$ は、その濃淡値が $[k_{j-1}+1,\ldots,k_j]$ の範囲にある画素の 集合とする。ただし、 $k_0=0$ および $k_K=L$ である。このとき、前節と同様に、 しきい値に依存して各クラスの統計量が計算できる。ここでは、これらを $\omega(k_j,k_{j-1})$, $\bar{g}(k_j,k_{j-1})$, および $\sigma^2(k_j,k_{j-1})$ で表す。

同様な計算によって、異なる分散を持つ正規分布の仮定のもので同時分布の最大対数 尤度は、

$$\hat{l}(G,\Theta;\hat{B}(k_1,\ldots,k_{K-1})) = N \sum_{j=1}^K \omega(k_j,k_{j-1}) \log(\omega(k_j,k_{j-1})) -\frac{N}{2}\log(2\pi)$$

$$-\frac{N}{2} \sum_{j=1}^K \omega(k_j,k_{j-1})\log(\sigma^2(k_j,k_{j-1})) -\frac{N}{2}$$ (183)

となる。定数項を無視すると、これは、評価基準

$$J(k_1,\ldots,k_{K-1})= \sum_{j=1}^K \omega(k_j,k_{j-1}) \log(\frac{\sigma(k_j,k_{j-1})}{\omega(k_j,k_{j-1})})$$ (184)

を最小化することと等価になる。これは、Kittler らの多値化の基準と同じである。 従って、この基準を最小とするような最適なしきい値を探せば良いことになる。

最適なしきい値を探索するために、ダイナミックプログラミングの手法を利用する [16,127]。

今、

$$Q(k,m) = \omega(k,m) \log(\frac{\sigma(k,m)}{\omega(k,m)}), \ \ \ k > m$$ (185)

とすると、最小化すべき目的関数は、

$$J_{K,L}(k_1,\ldots,k_{K-1}) = \sum_{j=1}^K Q(k_j,k_{j-1})$$ (186)

となる。ここで、 $0 = k_0 < k_1 < \cdots < k_{K-1} < k_K = L$ である。 さらに、部分和

$$J_{M,l}(k_1,\ldots,k_{M-1}) = \sum_{j=1}^M Q(k_j,k_{j-1})$$ (187)

を定義する。ここで、 $0 = k_0 < k_1 < \cdots < k_{M-1} < k_M = l$ である。ま た、

$$J_M^*(l) = \min_{1 \leq k_1 < \cdots < k_{M-1} < l} J_{M,l}(k_1,\ldots,k_{M-1})$$ (188)

とする。これらの記法を用いると、次のように最適性の原理が満足されていることが わかる。

$$J_M^*(l) = \min_{M-1 < k_{M-1} < l} \{J_{M-1}^*(k_{M-1}) + Q(l,k_{M-1}) \}$$ (189)

従って、最適なしきい値は $M = 2,3,\ldots,K-1$ に対して、 $J_M^*(l), \ \ l = M,\ldots,L-K+M$ を計算することにより求めることができる。このアルゴリズムの計 算時間は $O(KL^2)$ である。