📘

Otsu's Threshold

HardImage Processing 📚 Computer 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:

The input list pixels is used to calculate the probability of each intensity $i$ , which is $p(i) = \frac{\text{number of pixels with intensity } i}{\text{total number of pixels}}$ . For the given input, $p(0) = \frac{5}{10} = 0.5$ and $p(255) = \frac{5}{10} = 0.5$ .
The class probabilities $w_0(t)$ and $w_1(t)$ are calculated for each candidate threshold $t$ . Since $p(0) = 0.5$ and $p(255) = 0.5$ , when $t = 0$ , $w_0(t) = 0.5$ and $w_1(t) = 0.5$ .
The between-class variance $\sigma_B^2(t)$ is calculated for each $t$ . For $t = 0$ , $\sigma_B^2(t) = w_0(t) \cdot w_1(t) \cdot (\mu_0(t) - \mu_1(t))^2 = 0.5 \cdot 0.5 \cdot (0 - 255)^2 = 0.5 \cdot 0.5 \cdot 65025 = 16281.25$ , which is the maximum possible value for $\sigma_B^2(t)$ given the input.
The final output is the threshold value that maximizes $\sigma_B^2(t)$ , which in this case is $0$ since it results in the largest between-class variance.

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

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.

👑

Continue the full explanation

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

🔒

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.