2维最大类间平均离差阈值选取快速递推算法

Fast Recursive Two-dimensional Maximum between-cluster Average Deviation Thresholding Algorithms

阈值分割是广泛使用的最为有效的图像分割方法之一。阈值选取是阈值分割的关键。Otsu提出的基于L2范数的最大类间方差法是备受关注的一种方法,而基于L1范数的最大类间平均离差法则更为简捷,效果很好。2维最大类间平均离差阈值选取方法分割精确、抗噪性能好,其效果优于2维最大类间方差法,但存在计算量大、难以实用等缺点。提出了2维最大类间平均离差阈值选取的两种不同的快速递推算法,都可将计算复杂性由O(L4)减少为O(L2)。给出了2维最大类间平均离差两种快速递推算法的分割结果及运行时间,并与原始算法及原有的快速算法进行了分析和比较。实验结果表明,这两种递推算法都可以大幅度地提高运算速度,运行时间可减少到原始算法的0.1%,使2维最大类间平均离差阈值分割方法更为实用,目前已被应用于红外目标、车牌、指纹等自动识别系统中。

Thresholding is one of the widely used and efficient techniques for image segmentation in digital image processing. Threshold selection is crucial to thresholding. The maximum between-cluster variance algorithm based on L2-Norm, which was proposed by Otsu, is one of the most famous methods. And the maximum between-cluster average deviation thresholding algorithm based on L1-Norm is simpler and has good performance. The two-dimensional maximum between-cluster average deviation thresholding algorithm, which has high accuracy of segmentation and good resistance to noise, has better performance than the maximum between-cluster variance algorithm, but the two-dimensional algorithm requires a large amount of computation and is impractical in applications. In this paper, two fast recursive two-dimensional maximum between-cluster average deviation thresholding algorithms are proposed, whose computational complexities are only O （L^2）, while the computational complexity of the originall algorithm is O （L^4） . Using those two reeursive algorithms, the results and processing time of the two-dimensional maximum between-cluster average deviation thresholding algorithm are given, which are compared with the original algorithm. Experimental results show that both of those two reeursive algorithms can greatly reduce the processing time, which is only 0.1% of that of the original algorithm. Currently the proposed algorithms have been used in automatic infrared target, vehicle license plate and fingerprint recognition system.