The optimal All-Partial-Sums algorithm in commutative semigroups and its applications for image thresholding segmentation

The design and analysis of multidimensional All-Partial-Sums (APS) algorithms are considered. We employ the sequence length as the performance measurement criterion for APS algorithms and corresponding thresholding methods, which is more sophisticated than asymptotic time complexity under the straight-line program computation model. With this criterion, we propose the piling algorithm to minimize the sequence length, then we show this algorithm is an optimal APS algorithm in commutative semigroups in the worst case. The experimental results also show the algorithmic efficiency of the piling algorithm. Furthermore, the theoretical works of APS algorithm will help to construct the higher dimensional thresholding methods.