Framework for efficient optimal multilevel image thresholding

Martin Luessi, Marco Eichmann, Guido M. Schuster, Aggelos K. KatsaggelosJ. Electronic Imaging 2009 · DOI

TL;DR

This paper introduces a novel framework for efficient multilevel image thresholding by categorizing objective functions into two classes. This allows for the application of dynamic programming (DP) and advanced matrix searching algorithms, leading to significant speedups (orders of magnitude) compared to traditional exhaustive search methods, without sacrificing optimality.

What Problem Does This Paper Address?

Image thresholding is a fundamental image processing technique used to segment images into different classes, often representing foreground and background. Multilevel thresholding extends this to segmenting an image into more than two classes. The core challenge lies in finding the optimal thresholds that define these classes. Traditional methods often rely on analyzing image histograms and optimizing an objective function. However, finding these optimal thresholds can be computationally expensive, especially as the number of gray levels and classes increases. Exhaustive search, a brute-force approach, becomes intractable for practical image sizes and segmentation needs. This paper aims to provide a more efficient and systematic way to find optimal multilevel thresholds by developing a framework that classifies objective functions and leverages efficient algorithms.

Methods

The paper proposes a framework based on two classes of objective functions:

  • Class 1: Dynamic Programming (DP) Solvable Functions: For objective functions where the "class cost" (a component of the overall objective function) depends only on the boundary gray levels of a class, a dynamic programming approach, specifically a shortest path algorithm on a trellis, can be employed. This reduces the complexity from exponential (exhaustive search) to polynomial, specifically O(ML²), where M is the number of classes and L is the number of gray levels. The paper demonstrates that this DP approach can be applied to methods like the maximum entropy method.
  • Class 2: Functions Exploiting Matrix Properties: For objective functions that satisfy the "convex quadrangle inequality," more advanced algorithms can be used. This property allows the problem of finding optimal thresholds to be reformulated as finding row-wise maxima in a specific matrix. The paper introduces two algorithms for this:
  • Divide-and-Conquer: This algorithm achieves a time complexity of O(ML log L).
  • SMAWK Algorithm: This algorithm, which exploits total monotonicity of the matrix, further reduces the complexity to O(ML).

The paper also details the precalculation of auxiliary arrays (like cumulative probabilities and weighted sums) to enable O(1) calculation of class costs, which is crucial for the efficiency of the DP and matrix searching algorithms.

Datasets

The paper uses the "Lena" image (converted to grayscale) for execution time measurements. For experiments with more than 256 gray levels, interpolated versions of the Lena image histogram are used. Additionally, "Fishing Boat" and randomly generated histograms are used to analyze the influence of histogram structure on execution times. No new benchmarks are introduced; the focus is on evaluating the performance of existing thresholding methods with the proposed efficient algorithms.

Key Insights and Ideas

  • Categorization is Key: The core insight is that by categorizing objective functions into two classes based on their mathematical properties, we can systematically apply highly efficient algorithms. This moves beyond ad-hoc optimizations for specific methods.
  • DP for Shortest Paths: Recognizing that many thresholding problems can be framed as finding the shortest path in a trellis structure is a powerful simplification, enabling efficient DP solutions.
  • Matrix Properties Unlock Speed: The connection between optimal thresholding and matrix searching (specifically, finding row-wise maxima in structured matrices) is a significant finding. Exploiting properties like convex quadrangle inequality and total monotonicity leads to dramatic speedups.
  • O(ML) is Achievable: The paper demonstrates that for certain classes of objective functions, including those of the Otsu and minimum cross-entropy methods, optimal multilevel thresholds can be found in O(ML) time, a substantial improvement over O(ML²) DP or intractable exhaustive search.
  • Practical Speedups: The experimental results confirm that these theoretical speedups translate into real-world performance gains, with algorithms being orders of magnitude faster.

Key Results

  • Algorithmic Complexity: The paper presents algorithms with time complexities of O(ML²), O(ML log L), and O(ML) for multilevel image thresholding.
  • Significant Speedups: Experimental results show that algorithms combining DP with matrix searching (Divide-and-Conquer and SMAWK) are more than 10 times faster than the standard DP algorithm. The O(ML) SMAWK-based approach offers speedups of up to 2560 times for large L and M compared to the O(ML²) DP.
  • Otsu and Minimum Cross-Entropy: The paper shows that the objective functions for the Otsu method and the multilevel extension of the minimum cross-entropy method belong to the efficient classes, allowing their optimal thresholds to be found in O(ML) time.
  • Histogram Influence: Execution times for matrix searching algorithms are influenced by histogram structure, with random histograms yielding times close to worst-case scenarios.

Limitations and Future Work

  • Focus on Efficiency, Not Performance: The paper explicitly states that its scope is not to analyze the segmentation performance of different thresholding algorithms, but rather their computational efficiency. The proposed algorithms yield the same optimal results as the original methods, but faster.
  • Constant Factors: While theoretical complexities are provided, the paper acknowledges that constant factors in the algorithms can influence practical performance, especially for smaller L and M. This is observed in the slight advantage of the Divide-and-Conquer over SMAWK in some scenarios.
  • Implementation Complexity: The paper notes that implementing the SMAWK algorithm in low-level languages like ANSI C is involved.
  • Future Work: The paper's framework and efficient algorithms lay the groundwork for further research into optimizing other thresholding methods and exploring their segmentation performance in conjunction with these faster computation techniques. The authors also suggest that the presented algorithms can be used in real-time systems.

Summary updated

BibTeX
@article{luessi2009framework,
  author = {Martin Luessi and Marco Eichmann and Guido M. Schuster and Aggelos K. Katsaggelos},
  title = {{Framework for efficient optimal multilevel image thresholding}},
  journal = {J. Electronic Imaging},
  year = {2009},
  doi = {10.1117/1.3073891},
}
Figure