A closed-form solution to multi-level image thresholding

Abstract

This paper proposes an analytical formulation relying on the least square error. Similar results were also found for the cross correlation, within-class, and between-class variance. At first, a continuous distribution is hypothesized (for derivation purposes only) to produced a modified form of the well-known OTSU method. This hypothesis is “identical” to Otsu in terms of output performance and the need for an exhaustive search. However, apart from being derived from the continuous form, the proposed scheme requires less computational power. It turns out that the optimum threshold equals the average of the adjacent regions’ means. For some images, the scheme can result in multi-level thresholdeds. A direct form was then suggested to obtain a non-exhaustive solution. The idea is simply to approximate the non-continuous error function (used by the least square formulation and OTSU) with a forth order polynomial defined in the normalized gray intensity range [0,1]. The optimum threshold can then be found as a function of the roots of a second order polynomial whose coefficients are the solution of a 2x2 linear system. The performance of the proposed non-exhaustive solution is slightly inferior to OTSU in general, however; some images produced improved performance. Nevertheless, The proposed scheme can be easily generalized to the multi-level case without the need for an exhaustive search. For n+1 levels (i.e. n thresholds), the output is obtained by solving an nxn linear system followed by finding the roots of a n-order polynomial. The computational cost is clearly superior to the exhaustive search. In addition, as validated with some images, the performance is encouraging. Extension to the general clustering case is highly envolved with the exception of the two-level case (for any dimension) that has been successfully derived in this work.