CISC 457, Lecture 19 - Otsu's Method

This method minimizes the within-class variance (i.e. the WCSS), but more efficiently than the two-means method described above.

Minimizing the WCSS (also denoted $\sigma^2_\textrm{within}$) is equivalent to maximizing the "between-class variance", denoted $\sigma^2_\textrm{between}$:

$\begin{array}{rl} \sigma^2_\textrm{between} & = \sigma^2 - \sigma^2_\textrm{within} \\ & \Bigg\downarrow \;\; (\textrm{math}) \\ & = N_1 \; N_2 \: (\mu_1 - \mu_2)^2 \end{array}$

Algorithm 1 (inefficient):

For each possible intensity value, $T$:
- $C_1 = \{ p_i \mid p_i < T \}, \qquad N_1 = | \; C_1 \; |$
- $C_2 = \{ p_i \mid p_i \geq T \}, \qquad N_2 = | \; C_2 \; |$
- Compute $\mu_1$ and $\mu_2$
- Compute $\sigma^2_\textrm{between} = N_1 \; N_2 \; (\mu_1 - \mu_2)^2$
Pick the $T$ that maximizes $\sigma^2_\textrm{between}$.

But this takes ${\cal O}( n^2 )$ time for $n$ possible intensity values.

Algorithm 2 (Otsu's Method):

Do this incrementally.

Let $n_1(T)$ = number of pixels with intensity less than $T$.

Let $n_2(T)$ = number of pixels with intensity at least $T$.

Let $n_T$ = number of pixels with intensity equal to $T$.

Let $\mu_1(T)$ = mean of the pixels with intensity less than $T$.

Let $\mu_2(T)$ = mean of the pixels with intensity at least $T$.

Then

$\displaystyle n_1(T+1) = n_1(T) + n_T \\ n_2(T+1) = n_2(T) - n_T \\ \\ \mu_1(T+1) = {\displaystyle n_1(T) \mu_1(T) + n_T T \over \displaystyle n_1(T+1) } \\ \mu_2(T+1) = {\displaystyle n_2(T) \mu_2(T) - n_T T \over \displaystyle n_2(T+1) } \\ $

The algorithm:

$n_1(0) = 0, n_2(0) = N$
$\mu_1(0) = 0, \mu_2(0) = { \sum p_i \over N }$
for $T$ = 0 to maximum intensity:
- Compute $\sigma^2_\textrm{within} = n_1(T) \; n_2(T) \; (\mu_1(T) - \mu_2(T))^2$
- Compute $n_1(T+1), n_2(T+1), \mu_1(T+1), \mu_2(T+2)$ from the equations above.
Pick the $T$ that maximizes $\sigma^2_\textrm{between}$.

This take ${\cal O}( n )$ time for $n$ possible intensity values.