Otsu's Threshold

hardPROImage ProcessingComputer Vision 1

Implement Otsu's method to find the optimal binarization threshold that maximizes between-class variance.

Given a list of pixel intensities (values 0-255), find the threshold $t$ that best separates the pixels into two classes (foreground and background) by maximizing the between-class variance $\sigma_B^2$ .

Algorithm:

For each candidate threshold $t$ from 0 to 255:

Class probabilities:
- $w_0(t) = \sum_{i=0}^{t} p(i)$ (background weight)
- $w_1(t) = \sum_{i=t+1}^{255} p(i)$ (foreground weight)
Class means:
- $\mu_0(t) = \frac{\sum_{i=0}^{t} i \cdot p(i)}{w_0(t)}$
- $\mu_1(t) = \frac{\sum_{i=t+1}^{255} i \cdot p(i)}{w_1(t)}$
Between-class variance: $\sigma_B^2(t) = w_0(t) \cdot w_1(t) \cdot (\mu_0(t) - \mu_1(t))^2$
The optimal threshold maximizes $\sigma_B^2(t)$ .

where $p(i)$ is the probability of intensity $i$ (histogram normalized by total pixel count).

Return the threshold value (integer) that maximizes $\sigma_B^2$ .

Example

Input

pixels = [0, 0, 0, 0, 0, 255, 255, 255, 255, 255]
num_bins = 256

Output

Reasoning

pixels holds 10 intensities: five at $0$ (black) and five at $255$ (white). num_bins is $256$ , one bin per possible intensity. Normalising the counts gives $p(0) = \frac{5}{10} = 0.5$ , $p(255) = 0.5$ , and $p(i) = 0$ for every other $i$ .
At $t = 0$ the background class is $\{0\}$ and the foreground is $\{255\}$ : $w_0 = 0.5$ , $w_1 = 0.5$ , $\mu_0 = 0$ , $\mu_1 = 255$ .
So $\sigma_B^2(0) = 0.5 \cdot 0.5 \cdot (0 - 255)^2 = 0.25 \cdot 65025 = 16256.25$ .
Now try $t = 1, 2, \dots, 254$ . No pixel lies in $1..254$ , so every one of these thresholds produces exactly the same two classes and the same $\sigma_B^2 = 16256.25$ . At $t = 255$ the foreground is empty ( $w_1 = 0$ ), so $\mu_1$ is undefined and that split is not a candidate.
Notice that 255 thresholds tie for the maximum. The tie rule in the constraints (return the smallest) is what makes the answer 0, not anything special about $t = 0$ itself.

Constraints

Input: List of pixel intensities (integers 0-255), number of bins (256)
Return: Optimal threshold as an integer
If multiple thresholds give the same maximum variance, return the smallest
Use pure Python (no numpy)
At least 2 distinct intensity values in the input

More from Computer Vision 1

Semi-Global Matching Cost Aggregationhard Compute Depth Map from Disparitymedium Stereo Rectification Checkeasy Oriented BRIEF Descriptorhard Gaussian Scale Spacemedium

Concept primerPREVIEW

Background Knowledge

Otsu's method is a widely used technique in image processing for automatic thresholding. The goal is to find the optimal threshold that separates the image into two classes: foreground and background. This is achieved by maximizing the between-class variance, which measures the difference between the two classes. The underlying concept is based on the assumption that the image histogram can be modeled as a mixture of two Gaussian distributions, one for the foreground and one for the background.

The key to Otsu's method is the calculation of class probabilities, class means, and between-class variance. Class probabilities ( $w_0$ and $w_1$ ) represent the proportion of pixels in each class, given a threshold $t$ . Class means ( $\mu_0$ and $\mu_1$ ) represent the average intensity of each class. The between-class variance ( $\sigma_B^2$ ) measures the difference between the two classes and is used as the criterion for selecting the optimal threshold.

In the context of image processing, thresholding is a crucial step in image segmentation, object detection, and feature extraction. Otsu's method provides an efficient and effective way to determine the optimal threshold, eliminating the need for manual tuning or trial-and-error approaches. By understanding the underlying theory and algorithm, developers can apply Otsu's method to various image processing tasks and improve the accuracy of their applications.

Algorithm/Approach

The general approach to solving this problem involves iterating over all possible threshold values (0-255) and calculating the between-class variance for each threshold. The threshold that maximizes the between-class variance is selected as the optimal threshold. This approach can be viewed as a brute-force search, where the algorithm evaluates each possible solution and chooses the best one.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.