-
2维最大熵阈值分割综合了点灰度值和相邻区域像素点平均值的信息得到分割图像的阈值。首先,假设输入图像大小为M×N,那么像素点的灰度值f(x, y)的取值范围为0≤f(x, y)≤L-1,其中L一般取值为256, (x, y)为图像中取样点的坐标,且1≤x≤M,1≤y≤N。通过计算像素点g(x, y)的四领域像素点的灰度平均值得到平滑图像,其像素点灰度值记为0≤g(x, y)≤L-1,那么,图像中的每一个像素点将对应一个由点灰度和区域灰度均值构成的2维向量。设nij为图像点灰度值f(x, y)=i、区域灰度均值g(x, y)=j的像素点出现的频数,pij为对应(i, j)发生的概率,记为${p_{ij}} = \frac{{{n_{ij}}}}{{M \times N}}$,所得到的{piji, j=0, 1, …, L-1}构成输入图像的点灰度和区域灰度值的2维直方图。从图 1、图 2中可以看出,pij的高峰主要集中分布在平面图的对角线附近,因为图像中的目标像素点和背景像素点占图像像素比例最大,并且其内部像素灰度值较均匀,点灰度值与区域灰度值相差不大,所以集中在对角线附近。图 2中的2维直方图呈现出近似双峰的状态,分别对应图像中的目标与背景。图 1是一般的2维直方图的平面图,其中A代表目标、B代表背景、C代表边界, D代表噪声。因为图像中的边界和噪声像素比例小,所以此处不考虑C区域和D区域[12-16]。
2维熵算法中的符号如表 1所示。
Table 1. Symbol definition of the algorithm
symbol meaning s point gray threshold t gray mean value threshold of region pij probability of occurrence of vector (i, j) pA the posterior probability of object region A pB the posterior probability of background region B H(A) the 2-D entropy of object region A H(B) the 2-D entropy of background region B 2维熵算法的步骤如下:设A区和B区具有不同的概率分布,用A区和B区的后验概率分别对A区和B区的概率pij进行归一化处理,当阈值为向量(s, t)时,则:
$ {p_A} = \sum\limits_i {\sum\limits_j {{p_{ij}}} } $
(1) 式中, i=0, 1, …, s; j=0, 1, …, t。
$ {p_B} = \sum\limits_i {\sum\limits_j {{p_{ij}}} } $
(2) 式中, i=s+1, s+2, …, L-1;j=t+1, t+2, …, L-1。那么A区和B区的2维熵分别是:
$ H\left( A \right) =-\sum\limits_i {\sum\limits_j {\frac{{{p_{ij}}}}{{{p_A}}}\lg \left( {\frac{{{p_{ij}}}}{{{p_A}}}} \right)} } = \lg {p_A} + \frac{{{H_A}}}{{{p_A}}} $
(3) 式中, ${H_A} =-\sum\limits_i {\sum\limits_j {{p_{ij}}\lg {p_{ij}}} } $, 且式中条件满足i=0, 1,…, s; j=0, 1, …, t。
$ H\left( B \right) =-\sum\limits_i {\sum\limits_j {\frac{{{p_{ij}}}}{{{p_B}}}\lg } } \left( {\frac{{{p_{ij}}}}{{{p_B}}}} \right) = \lg {p_B} + \frac{{{H_B}}}{{{p_B}}} $
(4) 式中, ${H_B} =-\sum\limits_i {\sum\limits_j {{p_{ij}}\lg {p_{ij}}} } $, 且i=s+1, s+2, …, L-1;j=t+1, …, L-1。
则熵的判别式为:
$ \varphi \left( {\mathit{\boldsymbol{s}}, \mathit{\boldsymbol{t}}} \right) = H\left( A \right) + H\left( B \right) $
(5) 由于此处不考虑C区和D区,则可以简化判别式:
$ {p_B} = 1-{p_A} $
(6) $ {H_B} = {H_L}-{H_A} $
(7) 式中, ${H_L} =-\sum\limits_i {\sum\limits_j {{p_{ij}}\lg{p_{ij}}} } $, 且i=0, 1, …, L-1;j=0, 1, …, L-1。则有:
$ H\left( B \right) = \lg \left( {1-{p_A}} \right) + \frac{{{H_L}-{H_A}}}{{1-{p_A}}} $
(8) 则熵的判别式可以写为:
$ \begin{array}{l} \varphi \left( {\mathit{\boldsymbol{s}}, \mathit{\boldsymbol{t}}} \right) = H\left( A \right) + H\left( B \right) = \\ \lg \left[{{p_A}\left( {1-{p_A}} \right)} \right] + \frac{{{H_A}}}{{{p_A}}} + \frac{{{H_L} -{H_A}}}{{1 -{p_A}}} \end{array} $
(9) 通过下式可以得到最佳阈值向量(s, t):
$ \varphi \left( {\mathit{\boldsymbol{s}}, \mathit{\boldsymbol{t}}} \right) = \max \left\{ {\varphi \left( {\mathit{\boldsymbol{s}}, \mathit{\boldsymbol{t}}} \right)} \right\} $
(10) -
本文中将输入的灰度图像大小调整为280×272。遗传算法的参量包括:群体规模M=20,最大遗传代数G=1000,变异概率pf=0.2,pb=0.4。
当图像被熵分割时,每个候选的阈值都需要经过一次熵的计算。假设一次熵的计算时间是一个固定值T。对于灰度级为256的灰度图像,进行1维熵分割时需要进行256次熵的计算,因此,总的计算时间为256T。在2维熵分割时需要进行256×256次熵的计算,总的计算时间为256×256T=65536T。当采用普通遗传法与2维熵结合时,通过进行250次实验,得出其进化代数均值为104代,由于设置的种群数为20,所以实际总的计算时间为104×20T=2080T。采用改进遗传算法与2维熵结合时,同样进行250次实验,得出其进化代数均值为60代,由于种群数仍然为20,所以实际计算时间为60×20T=1200T。从表 2中的平均时间对比可知,无论是普通的遗传算法,还是经过改进的遗传算法都优于通过穷尽法计算的2维熵算法。然而,这些方法仍然比1维熵所用时间长,并且对于未加噪声的原始图像,使用1维熵分割图像的效果和用2维熵算法分割图像的效果是很接近的,这从图 5中就可以发现。但是,当图像添加噪声后,采用2维熵算法分割图像明显优于使用1维熵算法分割图像,分析图 6即可得出这一结论。
Table 2. Performance comparison of segmentation algorithms
s t average values of evolutionary algebra averagetime/s 1-D entropy(exhaustion) 66 0.479241 2-D entropy(exhaustion) 66 62 491.4612 2-D entropy(common GA) 65 141 104 9.35342 2-D entropy(modified GA) 71 105 60 0.958795 基于改进遗传算法的图像分割实验可视化为图 7和图 8。从这些结果图可知,1维和2维熵的结果接近于穷举法(对于有噪声或无噪声的图像)。通过实验证明了基于改进遗传算法最大2维熵分割是可行的。
Figure 7. a—segmented by combining 1-D entropy and GA without noise b—segmented by combining 2-D entropy and GA without noise
Figure 8. a—segmented by combining 1-D entropy and GA with noise b—segmented by combining 2-D entropy and GA with noise
需要说明的是:本文中采用MATLAB语言对遗传算法进行改进并实现。实验环境为:Window7系统,4G内存,MATLAB R2010b平台。
基于改进遗传算法的最大2维熵图像分割
Image segmentation of 2-D maximum entropy based on the improved genetic algorithm
-
摘要: 为了解决传统最大2维熵分割算法计算量大、耗时较多等缺陷,提出一种基于改进遗传算法的最大2维熵图像分割法。通过对遗传算法变异操作方式进行改进,提高遗传算法寻找最大2维熵分割阈值的速度,加速分割算法对图像的分割,并进行了仿真实验验证。结果表明,改进模型的运行时间被压缩到了0.95s,远远低于传统的最大2维熵分割法。改进的分割方法实现了分割效率的提高,同时也保证了图像的分割精度。Abstract: In order to solve the defects of traditional maximum 2-D entropy segmentation algorithm, a large amount of calculation, more time consumption, and so on, a maximum 2-D entropy segmentation method based on the improved genetic algorithm was proposed. By improving the mutation operating mode of the genetic algorithm, the speed of the genetic algorithm to find maximum 2-D entropy segmentation threshold was improved, and then image segmentation by using the segmentation algorithm was accelerated.Through theoretical analysis and simulation experiments, the results show that, the running time of the modified model is compressed to 0.95s, which is far lower than the traditional maximum 2-D entropy segmentation method. The modified segmentation method improves the segmentation efficiency and ensures the accuracy of image segmentation.
-
Key words:
- image processing /
- 2-D maximum entropy /
- genetic algorithm /
- mutation operation
-
Table 1. Symbol definition of the algorithm
symbol meaning s point gray threshold t gray mean value threshold of region pij probability of occurrence of vector (i, j) pA the posterior probability of object region A pB the posterior probability of background region B H(A) the 2-D entropy of object region A H(B) the 2-D entropy of background region B Table 2. Performance comparison of segmentation algorithms
s t average values of evolutionary algebra averagetime/s 1-D entropy(exhaustion) 66 0.479241 2-D entropy(exhaustion) 66 62 491.4612 2-D entropy(common GA) 65 141 104 9.35342 2-D entropy(modified GA) 71 105 60 0.958795 -
[1] OTSU N. A threshold selection method from gray-level histograms[J]. IEEE Transactions on Systems Man and Cybernetics, 1979, 9(1):62-66. doi: 10.1109/TSMC.1979.4310076 [2] SONG B, YANG H X, CENG J F, et al. 2-D minimum error threshold segmentation method based on mean absolute deviation from the median[J]. Laser Technology, 2015, 39(5): 717-722(in Chinese). [3] ZHENG W, ZHANG J, LI K X, et al. Improved active contour segmentation model based on phase consistency[J]. Laser Technology, 2016, 40(2): 296-302(in Chinese). [4] LAKSHMI S, SANKARANARAYANAN D V.A study of edge detection techniques for segmentation computing approaches[J]. International Journal of Computer Applications, 2011, Special Issue on CASCT(1):35-41. [5] CANNY J. A computational approach to edge detection[J].IEEE Transactions on Pattern Analysis and Machine intelligence, 1986, 8(6): 184-203. [6] DAVIS L S. A survey of edge detection techniques[J]. Computer Graphics and Image Processing, 1975, 4(3):248-270. doi: 10.1016/0146-664X(75)90012-X [7] KESAVAN H, KAPUR J N. The generalized maximum entropy principle[J]. IEEE Transactions on Systems Man and Cybernetics, 1989, 19(5):1042-1052. doi: 10.1109/21.44019 [8] DOYLE W. Operations useful for similarity-invariant pattern recognition[J]. Journal of the ACM, 1962, 9(2):259-267. doi: 10.1145/321119.321123 [9] ABUTALEB A S. Automatic thresholding of gray-level pictures using two-dimensional entropy[J]. Computer Vision Graphics and Image Processing, 1989, 47(1):22-32. doi: 10.1016/0734-189X(89)90051-0 [10] WANG Ch H, LI L, LI Y Sh et al. Seeking of tissue image digging point method based on genetic-arithmetic[J]. Optics and Precision Engineering, 2005, 13(2):231-236(in Chinese). [11] ANTONIOL G, CECCARELLI M. Microarray image gridding with stochastic search based approaches[J]. Image and Vision Computing, 2007, 25(2):155-163. doi: 10.1016/j.imavis.2006.01.023 [12] CHONG J S, ZHOU X K, WANG H Q, et al. Image thresholding segmentation based on genetic algorithm[J]. Journal of Electronics and Information Technology, 2000, 22(5):785-790(in Chinese). [13] MO L. Study on image segmentation based on RGB color image[J].Computer Science, 2016, 43(s1):168-170(in Chinese). [14] CHANG Q, WANG L, XING Ch, et al. The selection of image threshold on the basis of genetic algorithms[J]. Computer Engineering & Applications, 2002, 38(22):35-37(in Chinese). [15] HAN S Q, WANG L. A survey of thresholding methods for image segmentation[J]. Systems Engineering and Electronics, 2002, 24(6): 91-94(in Chinese). [16] LIN Q, DONG P, LIN J Y. A survey on graph cut techniques[J]. Microprocessors, 2015, 2015(1):35-39(in Chinese). [17] HOLLAND J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[J]. Quarterly Review of Biology, 1992, 6(2):126-137. [18] JIN J L, YANG X H, DING J. An improved simple genetic algorithm—accelerating genetic algorithm[J]. Systems Engineering-theory & Practice, 2001, 21(4):8-13(in Chinese). [19] PENCE C H. Is genetic drift a force?[J]. Synthese, 2017, 194(6):1967-1988. doi: 10.1007/s11229-016-1031-2 [20] SRINIVAS M, PATNAIK L M. Genetic algorithms: A survey[J]. IEEE Computer, 2002, 27(6):17-26. [21] LEE S W, LEE D J, PARK H S. A new methodology for gray-scale character segmentation and recognition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, 18(10): 1045-1050. doi: 10.1109/34.541415 [22] ROWE J E. Genetic algorithm theory[C]//Genetic and Evolutionary Computation Conference. Philadelphia, PA, USA: Association for Computing Machinery, 2011: 1029-1052. [23] WANG X P, CAO L M. Genetic algorithm: theory, application and software implementation [M]. Xi'an: Xi'an Jiaotong University Press, 2002:18-51(in Chinese). [24] ZHANG H J, ZHAO J, LUO H. A method combining genetic algorithm with simultaneous perturbation stochastic approximation for linearly constrained stochastic optimization problems[J].Journal of Combinatorial Optimization, 2016, 31(3):979-995. [25] AYO B S. An improved genetic algorithm for flight path re-routes with reduced passenger impact[J]. Journal of Computer & Communications, 2017, 5(7):65-75. [26] CHEN L P, CHEN X Y, WANG S, et al. Foreign fiber image segmentation based on maximum entropy and genetic algorithm[J]. Journal of Computer and Communications, 2017, 3(11):1-7. [27] WANG H W, LIANG Y Y, WANG Zh H. Otsu image threshold segmentation method based on new genetic algorithm [J]. Laser Technology, 2014, 38(3): 364-367(in Chinese). [28] POTTS J C, GIDDENS T D, YADAV S B. The development and evaluation of an improved genetic algorithm based on migration and artificial selection[J]. IEEE Transactions on Systems Man & Cybernetics, 1994, 24(1):73-86. [29] YANG Q W, JIANG J P, ZHANG G H. Improvement of the speed of genetic algorithm optimization [J]. Software Journal, 2001, 12 (2): 270-275(in Chinese).