Efficient Multilevel Image Thresholding

Image thresholding is a very common operation in image processing. Multilevel image thresholding means that the goal is to find more than one threshold. Most existing methods find the optimal thresholds by either minimizing or maximizing an objective function that depends on the position of the thresholds.

Using an algorithm that evaluates the objective function for every possible combination of thresholds becomes intractable even for relatively low numbers of gray levels and thresholds, as the number of possible combination increases dramatically. In this project we define classes of objective functions for which we propose algorithms with low time complexities for finding the optimal thresholds.

We presented preliminary results of this work at ICIP 2006 Luessi:2006:16 and more recently in the SPIE Journal of Electronic Imaging Luessi:2009:597.

We provide the source code of all ANSI C implementations used in this work. The source code consist of optimal multilevel thresholding algorithms for the Otsu method, the algorithms included are based on exhaustive search, dynamic programming, dynamic programming and divide-and-conquer matrix searching, and dynamic programming and SMAWK matrix searching. All algorithms are optimal but have different time complexities. The algorithms can either be used as a standalone application for timing measurements (on Linux systems) or from Matlab (mex files).

Source code: thresholding.zip