林业科学  2012, Vol. 48 Issue (4): 87-92   PDF    
0

文章信息

张广群, 汪杭军
Zhang Guangqun, Wang Hangjun
基于多目标遗传算法的管孔组合特征识别
Multi-Objective Genetic Based Pore Combination Recognition
林业科学, 2012, 48(4): 87-92.
Scientia Silvae Sinicae, 2012, 48(4): 87-92.

文章历史

收稿日期:2011-01-11
修回日期:2011-02-15

作者相关文章

张广群
汪杭军

基于多目标遗传算法的管孔组合特征识别
张广群, 汪杭军    
浙江农林大学信息工程学院 临安 311300
摘要: 提出一种管孔组合方式的自动识别方法。提取木材显微横切面的边缘后,基于类圆区域面积直方图,通过最大类间方差将封闭区域分为2类,将导管与其他形状相似、大小不同的组织分开;同时,引入封闭区域平均面积作为另一目标函数。最后采用管孔集邻接度来判断管孔的组合方式。试验表明该方法能够对各种导管的分布和组合获得满意的分割效果,并给出管孔的组合方式。
关键词:管孔集邻接度    多目标优化    导管分割    管孔组合    最大类间方差    阔叶树材    
Multi-Objective Genetic Based Pore Combination Recognition
Zhang Guangqun, Wang Hangjun    
School of Information and Technology, Zhejiang A&F University Lin'an 311300
Abstract: This paper proposes an automatic method of pore combination recognition, which is an important feature to hardwood recognition. After extracting edge from wood microscopic cross-section, based on area histogram of the similar circle regions, the method classifies all regions into two classes with maximum between-class variance, so as to distinguish the pore from other textures, which are similar in shapes but different in sizes. Meanwhile, second objective function about average area of closed regions is used to improve the pore segmentation performance. At last, the method uses adjacency degree of pore set to judge pore combination. The experiments demonstrate that the task of pore segmentation can be completed successfully for all kinds of pore distribution and combination, and also the correct combinations of pores are given.
Key words: adjacency degree of pore set    multi-objective optimization    pore segmentation    pore combination    maximum between-class variance    hard wood    

管孔组合对于阔叶树材的识别是一个重要的特征。随着计算机视觉技术和图像处理技术的发展,有效、准确的木材识别成为可行(汪杭军等,2009)。图像处理技术最早应用到测量导管的长度(Ribeiro et al., 2001),尽管该方法比传统的方法在速度、精度和精确程度方面表现出显著的优点,但是安完成相关任务仍旧需要许多手工劳动,因此在没有人工干预的情况下如何进行导管以及管孔组合的自动识别显得非常重要。汪杭军等(2011)通过纹理方法进行了木材树种的识别研究,但是该方法不能获取图像中木材组织的语义对象。通过图像分割是获得语义对象的一种可行途径。目前图像分割的方法有3类:基于边缘的图像分割、基于区域的图像分割和基于像素聚类的图像分割(Zhang, 1996; Pen et al., 2001),每种方法都有其各自的特点,而数学形态学是一种建立在集合论基础上的方法, 由于它对噪声鲁棒性好、速度快等优点,现已广泛应用于图像分割中(Haralick et al., 1987),例如Qi等(2007)利用数学形态学应用于横切面的导管分割,获得了较好的结果。

在木材横切面上,封闭区域除了导管之外,还有木纤维和轴向薄壁。图 1给出了University of Wisconsin (2012)中一个橡树横切面显微示意图,从图中可看到木材的这3种组织纹理结构表现为形状相似、大小不同,并且不同的树种导管大小变化差异很大。因此,Qi等(2007)的方法有一个缺点,合理的分割结果依赖于封闭区域面积相关的参数,通过该参数从木纤维、轴向薄壁上选择出导管。该参数是一个与图像和木材种类相关的阈值,通常需要人工设定。为了自动地分割导管而无须人工进行干预,有必要设计一个对不同阔叶树材都通用的自适应导管分割算法。

图 1 木材横截面的细胞结构 Fig.1 The cell structure of wood corss section

本文提出了一种基于类圆区域的面积直方图方法,自动计算封闭区域最佳阈值,该阈值可用于对导管进行分割。该方法的思想来源于一种通用的基于灰度直方图的图像分割Otsu算法(Otsu,1979)。基于类圆区域的面积直方图,将图像分割后,把所有封闭区域按照面积进行排序,并对具有相同面积的区域进行合并计数, 然后用最大类间方差把封闭区域分成2类,其中最大的一类就是导管; 但是该方法对散孔材和单管孔木材的分割效果较好,而半散孔材、环孔材和除了单管孔外其他管孔组合木材的效果较差。这是由于不同的管孔组合,管孔的大小分布是不一样的,其中散孔材中导管的大小是比较均匀的,但是在其他的组合方式上却差别很大。因此,仅通过最大类间方差法不能获得理想的结果。

多目标优化遗传算法的应用日益受到学者们的关注。单目标优化中目标函数与适应度函数一般是一致的,但对于多目标优化,适应度函数的分配和选择是一个多准则的优化问题。适应度分配策略有基于聚类、准则和Pareto3种(Zitzler et al., 2004)。为了克服以上提到的最大类间方差的缺点,本文用基于聚类的策略(Ishibucki et al., 1996),将单目标变成多目标问题。根据木材学领域知识,导管在横切面上占的面积比例相对较少,引入与封闭区域平均面积相关的参数作为第2个目标函数。进一步的试验显示, 采用多目标函数后对不同种类的阔叶树材均能获得满意的导管分割效果。

根据获得的导管,采用管孔外接圆与周围相邻的区域是否相交来判断它们的邻接关系; 然后通过管孔的邻接度来判断管孔的组合方式; 最后的试验显示了得到的管孔组合方式与实际的比较一致,说明本文提出的方法是有效的。

1 基于数学形态学的图像分割

在20世纪60年代早期,Matheron(1975)最早使用数学形态学处理二值图像。数学形态学的基本思想是用具有一定形态的结构元素对图像进行处理。目前数学形态学在图像处理和计算机视觉中的识别和缺陷的检测方面得到了广泛应用(Cordeiro,2001黄海龙等,2011王栋等,2009)。

这里把数学形态学的2个最基本的操作膨胀和腐蚀应用于图像边缘的检测。假定所有木材都是灰度图像。设f(x, y)是输入的灰度图像,b(x, y)是给定的定义在R2上的结构元素。膨胀操作定义如下:

(1)

式中:Db是属于b(x, y)的区域。

腐蚀操作是:

(2)

根据式(1)和式(2)定义的2个最基本操作,将它们用于图像边缘检测。假设E(x, y)是图像边缘的函数,计算如下:

(3)

若结构元素上灰度膨胀操作的值是正的,则将使图像锐化,并且可以减少和消除一些黑色区域(这通常可以用来去噪)。作为一种非线性图像处理和分析理论的数学形态学,它的最大优点是简单和可靠。图 2显示了对图 1进行边缘提取以后的效果,从图中可以看到,绝大部分的木纤维、轴向薄壁和导管均被提取出来。

图 2图 1进行边缘提取后的效果 Fig.2 Edge extraction result of Fig. 1
2 导管面积阈值的最大类间方差算法

Otsu算法是阈值图像分割中最经典的方法之一(李春干等,2010), 它通过对输入的灰度图像的直方图进行分析,自动选择阈值把一幅给定的图像分为前景和背景2部分。显然,Otsu算法能够进行扩展,用于获取区分导管和其他封闭区域面积的最佳阈值。

假设f(x, y)是输入的灰度图像函数。用数学形态学对图像进行边缘分割后,将所有的封闭区域的按面积排序,然后计算各个封闭区域面积的个数,这样得到一个面积分布函数,称为面积直方图(area histogram,AH)。将这些面积排序后的区域记为S = {n0, n1, n2, …, nL-1},其中L表示不同面积的个数,ni表示第i个面积的封闭区域的个数。阈值t把所有封闭区域划分为2类,C0表示{n0, n1, …, nt}的面积区域,C1表示{nt+1, nt+2, …, nL-1}的面积区域。其中C1代表导管,C0代表除导管外其他细胞的结构。

由封闭区域的面积概率分布Pi=ni/N, Pi≥0, ,其中N是图像中封闭区域的总个数,Pi是封闭区域面积为ni的概率。则C0C1类的概率分别为:

(4)
(5)

C0C1类的均值均分别为:

(6)
(7)

μ为所有封闭区域的平均面积,则可以得到:

(8)
(9)

定义类间方差为:

(10)

使σ2取最大值的t就是所求的最佳阈值。最简单的方法就是遍历区域范围0~(L-1)内所有面积并计算方差,最后得到使方差最大的阈值。随着图像维数的增加,该方法计算量将变得非常复杂。为了能有效地决定图像的阈值,下面通过遗传算法改进类方差的计算。

3 基于多目标阈值的算法

遗传算法是一种高效的随机搜索演化方法,通过它可以克服Otsu方法计算时间长的缺点。首先,采用最大类间方差作为单目标适应函数; 然后,引入和封闭区域平均面积相关的参数作为第2个目标函数, 用于提高导管分割的性能。

3.1 编码

所有的封闭区域进行排序并且按照面积计数,表示为{n0, n1, n2, …, nL-1}。为了快速计算和编码需要,可将它映射为{0, 1, …, L-1},其中L是不同面积的封闭区域的个数。根据面积用染色体编码成二进制串,代表某个阈值。

3.2 初始化

随机产生数量为N的初始种群,初始种群的规模一般不易过大。随机产生的种群要尽量覆盖整个搜索空间。在0到L-1之间划分N等分,然后每个子区域内同等概率随机产生种群。

3.3 适应度函数

根据式(10),可以将最大类间方差σ2作为适应度函数。因此,染色体所代表的方差越大,就越有可能逼近最优解;但是单个目标函数通常不能获得满意的问题答案。根据木材学知识,导管在木材横切面中所占的比例较少,大部分区域还是被木材的其他组织所占,另外还要加上杂质等噪音的影响。因此引入和封闭区域平均面积相关的参数作为第2个目标函数,从而可以排除很多导管外的其他用组织和噪音的干扰,提高导管分割的性能。使用基于聚类的策略,把多个目标整合到单一的参数化目标。式(11)给出了多目标的适应度函数:

(11)

式中: τ0是类C0的平均面积;τ1是类C1的平均面积。这2类是通过阈值t用最大类间方差法划分而成的。系数a, b是2个目标的比例,在试验中取1~4。通过多目标优化,即最大化σ2和使ψ2最小化,能使导管分割的效果更加理想。

3.4 选择

采用轮盘赌方法进行选择操作,它是一种基于比例的选择,采用回放式的随机采样方法,利用个体适应度所占比例的大小决定其子孙保留的可能性。具体做法为:首先, 计算群体中个体的适应度,依次进行累加,分别记为Si, 最后一个累加值为Sn; 其次,在[0 Sn]区间内随机生成数K; 第三,依次用SiK相比较,从第1个个体开始累加,直到累加值大于此随机数K,此时最后一个累加的便是要选择的个体。重复第二、三步,直至满足所需的个体数目为止,形成用于繁殖的个体。

3.5 交叉和变异操作

在当前的种群中,选取2个个体按设定的交叉概率进行交叉操作; 然后根据一定的变异概率,从种群中随机选择若干个个体,再随机地在这若干个个体中选择某一位进行变异运算,从而形成新一代群体。

3.6 终止条件

设定终止条件为达到最大迭代次数M或当前群体的平均适应度值与上一代群体的平均适应度值的比值在范围为[1.0,1.005 ]之间。为防止种群退化,影响收敛速度,本文采用种群更新机制。计算新的群体中适应度值最小的个体,和上一代群体中个体适应度值最大的比较。如果小于原来群体中适应度最大值,则用原来群体中适应度值最大的个体替换新群体中适应度值最小的个体,形成新的群体,然后重新进行选择、交叉、变异等操作,直至满足循环终止条件为止。

终止条件满足时,将最后一代群体中适应度最大的个体作为本算法所寻求的最优结果,将其解码为n0, n1, n2, …, nL-1之间的面积阀值t,即所求的最佳分割阈值。

4 管孔组合判别

管孔的组合形式可以分为单管孔、复管孔和管孔团3种,如图 3所示。从图中管孔的组合形式可以观察到,2个或者2个以上管孔相邻连成某一角度的排列,或者由多个管孔聚在一起形成了管孔的不同组合。

图 3 管孔的3种组合形式 Fig.3 Three composition forms of porous wood a.单管孔Solitany pore; b.复管孔Multiple pores; c.管孔团Pore cluster.

由于管孔轮廓的不规则性,相邻管孔之间其重心的外接圆都会相交, 因此可以通过判断管孔外接圆是否相交来判断管孔是否相邻。定义管孔i的邻接度为与其相邻的管孔数目,记为adjacent(i)。

相邻的管孔可以认为在同一个集合内,称为管孔集(pore set),记为I ={n0, n1, …, nL-1},其中L为集合内相邻管孔的个数。定义管孔集邻接度(adjacency degree of pore set)如下:

(12)

可以根据式(12)管孔集邻接度来判断管孔的组合,判断方式如下:

单管孔:管孔集邻接度=1;

复管孔: 1<管孔集邻接度<2;

管孔团:管孔集邻接度≥2。

5 试验和结果

为了评价本文所提出方法的性能和效果,选择不同导管分布和组合形式的9种阔叶树材标本进行试验,如图 4左列图像所示。试验所有的算法采用了Microsoft Visual C++ Version 6.0进行编码并且运行在CPU为AMD Athlon 64 3000+、1G内存和Microsoft Windows XP操作系统的计算机上。

图 4 2种算法的比较 Fig.4 Comparison between two algorithms 左列是原始木材图像;中间列是单目标GA方法运行结果;右列是多目标GA方法运行的结果。Left: original wood images; middle: results of sigle-objective genetic algorithm; right: results of multi-objective genetic algorithm.

表 1给出了单目标和多目标2种遗传算法在运行时间、阈值和导管数目的对比结果。算法中一些参数设置如下:种群数为20、总代数为30、交叉的概率为0.9、变异的概率为0.001。

表 1 2种算法的对比结果 Tab.1 Result of the comparison between algorithms

表 1中可以看到, 多目标遗传算法的运行时间比单目标遗传算法还多一些,这是因为计算第2目标函数需要花费额外的时间所致; 但是多目标遗传算法得到的阈值要小很多,因此也就得到了更多的导管的数目,那些原本被认为是非导管而删除得到了保留,从而使结果更加准确、可靠。

图 4的中间和右列的导管提取效果也说明了表 1所给出的结论。从罗浮柿(Diospyros morrisiana)和枫香(Liquidamba formosana)可以看到单目标遗传算法对散孔材和单孔材的导管提取效果特别有效; 但是从板栗(Castanea mollissima)、糙叶树(Aphananthe aspera)、臭辣树(Evodia fargesii)和苦木(Picrasma quassioides)中也能明显看出,单目标遗传算法对半散孔材、环孔材和除了单管孔外其他管孔组合木材的效果均不理想,因此这个方法对有孔材的分布和组合形式是敏感的。由于散孔材和单孔材的导管的大小彼此是相近的,所以最大类间方差方法特别适合于以这2种封闭区域占主要成分的木材种类的导管提取。引入第2个目标函数后,通过减小阈值可以从噪音中获得更多的导管,如图 4右列所示。多目标遗传算法能提高导管分割的性能,并表明本文所提出的方法——自动地从横截面中提取导管是有效的。

提取导管后,为了评估所提出的管孔组合判别方法的性能,又从9种阔叶树材中选择了3种典型的树种:罗浮柿、枫香和糙叶树。图 5就是通过管孔集邻接度判断管孔组合算法后的结果,其中同一管孔集中的不同管孔均用红色进行填充,而在枫香中为了区别不同的管孔集使用了不同的颜色进行填充。图 5中的结果显示提出的管孔组合的自动判别方式是可行的。

图 5 管孔组合判别后的结果 Fig.5 Results of pore combination recognition
6 结论

本文采用机器视觉和模式识别方法讨论了从横截面图像中木材导管的分割和管孔组合特征自动获取问题。所提方法最大的特点是利用遗传算法,能够对各种导管分布和组合的树种都获得满意的分割效果,并进行管孔组合方式的判别,同时也提高了算法的效率。

由于导管是阔叶树材识别最重要的特征之一,因此导管的提取以及对管孔的分布和组合特征的判别是进行木材树种自动识别的基础。本文给出的方法为木材识别的研究提供了一种可行的途径。为了将导管清晰地显示,木材图像的分辨率往往很高,因此导管提取与特征判断的效率将受到很大的影响。如何针对不同的图像分辨率,快速、有效地提取导管及其分布和组合特征是今后需要研究的一个方向。

参考文献(References)
[] 黄海龙, 王宏, 李徽. 2011. 一种基于教学形态学的签名真伪鉴别方法. 东北大学学报, 32(6): 854–858.
[] 李春干, 邵国凡. 2010. 面向对象的Spot 5图像森林分类. 林业科学, 46(8): 130–139. DOI:10.11707/j.1001-7488.20100820
[] 王栋, 陈映鹰, 秦平. 2009. 基于形态学和盲源分离合成孔径雷达水平提取. 同济大学学报:自然科学版, 37(12): 1673–1678.
[] 汪杭军, 张广群, 祁亨年, 等. 2009. 木材识别方法研究综述. 浙江林学院学报, 26(6): 896–902.
[] 汪杭军, 汪碧辉. 2011. 一种新的针叶材自动识别方法. 林业科学, 47(10): 141–145. DOI:10.11707/j.1001-7488.20111022
[] Cordeiro M. 2001. Algorithmic patterns for morphological image processing. Prentice-Hall Press.
[] Haralick R M, Sternberg S R, Zhuang X. 1987. Image analysis using mathematical morphology. IEEE Trans Pattern Anal Mach Intell, 9(4): 532–550.
[] Ishibuchi H, Murata T.1996.Multi-objective genetic local search algorithm. Proc Int Conf. Evolutionary Computation, Nagoya, Japan.
[] Matheron G. 1975. Random sets and integral geometry. Wiley Press.
[] Otsu N. 1979. A threshold selection method from gray-level histograms. IEEE Transactions on Systems, Man, and Cybernetics, 9(1): 62–66. DOI:10.1109/TSMC.1979.4310076
[] Peng B, Zhang L, Zhang D. 2011. Automatic image sementation by dynamic region merging. IEEE Transactions on Image Processing, 20(12): 3592–3605. DOI:10.1109/TIP.2011.2157512
[] Qi H, Chen F, Ma L. 2007. Pore feature segmentation based on mathematical morphology. Annual Conference of the IEEE Industrial Electronics Society, Taipei, Taiwan, 2474-2477.
[] Ribeiro T P, Filho M T, Cruvinel P E.2001.Algorithm for analyzing anatomical structure of wood from Brazilian forest species based on digital imaging processes techniques. Proceedings of the XIV Brazilian Symposium on Computer Graphics and Image Processing, Florianópolis, Brazil, 392.
[] Univeristy of Wisconsin. 2012. Fibers and vessles in cross section of oak wood. http://digicoll.library.wisc.edu/WebZ/FETCH?sessioid=01-46120-740525216&recno=12&resultset=2&format=F&next=html/nffull.html&bad=error/badfetch.html&entitytopercno=12&entitycurrecno=12&entityreturnTo=brief.
[] Zhang Y J. 1996. A survey on evaluation methods for image segmentation. Pattern Recognition, 29(8): 1335–1346. DOI:10.1016/0031-3203(95)00169-7
[] Zitzler E, Laumanns M, Bleuler S. A tutorial on evolutionary multiobjective optimization. Proceedings of the Workshop on Multiple objective Metaheuristics. Berlin, Germany, Springer-Verlag: 3-37.