基于产生式规则的乔灌木识别推理算法研究

2020-03-11杜雨菲吴保国

计算机工程与应用 2020年5期

杜雨菲，吴保国，陈栋

北京林业大学信息学院，北京100083

1 引言

在生态建设日益推进的今天，公众对树木的认知有了更为深层的需求，从仅仅知道某树种的名称，演变到学习该树种的相关知识，即从“认树识树”，演变为了“认树识树知树”。通常情况下，公众进行树种识别主要是通过阅读挂在树上的标牌、查阅植物学家编制的树种检索表、树种图册等方式。然而，标牌上展示的知识有限，利用植物检索表识别树种需要林学专业知识，树种图册携带不便，均不适用于普通人群对树种知识的学习。随着人工智能技术和图像处理技术的快速发展，国内外很多研究人员采用机器学习方法构建了植物图像分类模型[1-5]，并以模型为基础研建了植物识别App，利用拍摄的树叶、花果等对树种进行识别[5-7]，达到了一定的识别精度。美国的Leafsnap 是世界上首款运用智能识别技术的植物识别App[8]，国内比较成熟的有形色App[8]和花伴侣[9]，可以根据植物的形态照片对开花的植物进行识别。除此之外，还有研究人员提出了基于交互式检索采用专家问答的方式进行植物识别的设想[10-11]。然而，由于开花植物的花形特征较为显著，乔灌木较少开花且枝叶特征较为细微，基于图像处理和机器学习技术构建的植物识别App多用于开花植物的识别，较少用于乔灌木识别；由于机器学习算法的准确率与样品选取量的问题，对开花植物的识别率不高，对乔灌木植物的识别率更不容乐观，容易对使用者造成误导；植物识别App 没有显示植物识别的过程，使用户丧失了进一步探究植物相关知识以及获得辨识能力的机会；采用专家系统的方法可以弥补上述不足，但现有的植物识别专家系统还停留在设想和设计阶段。鉴于乔灌木识别专家系统的匮乏，以北京乔灌木枝叶检索表[12]中的专家知识为例，对专家知识进行提取整理，利用枝叶特征图片对每条规则进行直观解释，建立了乔灌木识别知识库，设计了乔灌木识别推理算法，研建了北京市乔灌木识别专家系统，实现了对北京市乔灌木树种的有效识别，使公众可以在生活中感受丰富的树种知识，为森林生态建设服务。

2 专家知识构成及表示

2.1 树木学专家识别树种的知识构成

树木学专家通过树木的树皮、枝、叶、花、果等部位来识别树木的科、属、种、名。经过长期的知识积累，树木学专家编制了树种检索表[13]。为了方便识别北京市的乔灌木树种，刘一樵[12]编制了《北京市乔灌木枝叶检索表》，根据枝叶形状分为针形（条形、钻形或鳞形）、复叶、单叶对生、单叶互生（叶全缘）、单叶互生（叶有锯齿或裂片）5类，分别编制检索表。该检索表中的知识包含了详细的枝叶特征文字描述，根据不同的叶形特点，枝叶检索知识又细分为5 种：针形、条形、钻形或鳞形；复叶；单叶对生；单叶互生、全缘；单叶互生、有锯齿或裂片。树种知识包含了树种的名称、拉丁名、造林技术、图片等信息。

本研究的树种识别方式以北京市乔灌木枝叶检索表作为参照，表1 为该枝叶检索表进行检索的示例：首先在首编号为1的枝叶特征中，确定该树种的枝叶特征符合“叶针形，条形”，尾编号为2；继续查询首编号与尾编号相同的枝叶特征，即在首编号为2 的枝叶特征中，确定该树种的枝叶特征符合“叶针形，单生或2～5 枚束生”，尾编号为3；继续查询首编号为3的枝叶特征，确定该树种的枝叶特征符合“叶单生，在长枝上螺旋状着生，在短枝上簇生”，该条件对应的尾编号为“雪松”，至此，完成了树种的检索与识别。

表1 枝叶检索表示例

图1 规则推理树

图2 二级规则推理树

本文研究了上述检索方式的知识结构，构建了枝叶检索知识的规则推理树（图1），每类枝叶特征均对应一个二级规则推理树。图2是以“针叶、条形、钻形、鳞形”为例的二级规则推理树示例，在树的每一个节点都要判断下一步应该走哪一条路径，每一个分支路径都拥有一个枝叶特征值，通过选择枝叶特征的值来决定下一个节点，在下一个节点再重复上述过程，就可以最终找到所需要的节点。存在不同规则推理路径最终节点为同一树种的情况，这种冗余路径增强了树种检索与识别的效果。

2.2 专家知识表示

专家知识表示方法通常有6种：一阶谓词表示法[14]、产生式规则表示法[15]、框架表示法[16]、语义网络表示法[17]、剧本[18]以及本体论[19]。产生式规则表示法适合表示因果关系的知识，能够清晰明确地表示知识之间的规则，表示形式与人类求解问题时的逻辑思维相似，易于理解，已经多次被应用在专家系统的构建中[20-22]。因此，本研究采取产生式规则表示法对枝叶检索知识进行表示，例如雪松的检索规则可以表达为：IF 叶针形，条形and 叶针形，单生或2～5枚束生and 叶单生，在长枝上螺旋状着生，在短枝上簇生THEN 雪松。

为了方便在计算机中进行规则的存储和调用，在推理规则树的基础上，构建了枝叶检索知识规则推理树的链式双亲表示模型，如图3所示。每个节点都有头指针和尾指针，父节点的尾指针指向子节点的头指针，检索过程由指针进行链接完成。在一级模型中，枝叶特征导航节点是头节点，其头指针为空，尾指针为T0，据此链接到头指针为T0的节点，再根据“T1、T2、T3、T4、T5”这5 种尾指针，链接到对应的枝叶特征种类二级模型中。图4 是枝叶检索知识规则推理树的链式双亲表示二级模型的示例，尾指针为0 的节点没有子节点。例如，父节点“针形、条形、钻形、鳞形”的头指针为空，尾指针为1，子节点“叶针形、条形”的头指针与其父节点相同，尾指针为2。诸如此类，直到检索到尾指针为“0”的节点结束树种识别过程。

图3 枝叶检索知识规则推理树的链式双亲表示

图4 二级链式双亲表示

3 知识库与推理算法设计

3.1 知识库设计

根据树种识别专家知识的表示，本研究设计了6个关系，分别是：存储枝叶特征分类规则的导航表，存储针形、复叶、单叶对生、单叶对生、单叶互生乔灌木树种识别推理规则表。各个表之间的关系如图5所示。

通过导航表，根据枝叶特征分类推理规则来从5种不同类型的乔灌木树种识别推理规则表（表名分别为T1、T2、T3、T4、T5）中选择推理规则表进行知识搜索，定位到所要识别的树种；然后通过造林树种表（表名为Trees）获取该树种对应的树种知识，帮助用户深入了解所识别树种的知识。

导航表包含规则表序号、枝叶描述、表名和枝叶描述图片名称属性，通过枝叶描述和枝叶描述图片定位到乔灌木树种识别推理规则表T1～T5种中的1种推理规则表。5种乔灌木树种识别推理规则表结构相同，包含了首节点，尾节点，枝叶描述，枝叶描述图片名称，树种编号属性，通过识别推理规则对树种进行识别，得到满足规则的树种编号，通过造林树种表得到该树种的知识。

导航表T0的关系模式如下：

T0（规则表序号，枝叶描述，表名，枝叶描述图片名称）

每类推理规则表的序号和表名均存储在推理规则导航表的“规则表序号”“表名”字段中；推理规则导航表的“枝叶描述”字段存储对推理规则表进行分类的枝叶特征，这是导航的基本依据。

针形、条形、钻形或鳞形叶乔灌木树种识别推理规则表T1、复叶乔灌木树种识别推理规则表T2、单叶对生乔灌木树种识别推理规则表T3、单叶互生全缘叶乔灌木树种识别推理规则表T4、单叶互生有锯齿或裂片叶乔灌木树种识别推理规则表T5的关系模式相同，表Ti(i=1,2,…,5)的关系模式如下：

Ti（首节点，尾节点，枝叶描述，枝叶描述图片名称，树种编号）

造林树种表中存储造林树种知识，关系模式如下：

Trees（树种编号，树种学名，树种别名，树种拉丁名，树种描述，树种分布，树种描述图片名称，造林技术，……）

图5 表之间的关系

本研究中每类乔灌木树种识别推理规则的实现关键在于“首节点”和“尾节点”。“首节点”和“尾节点”共同标识一条推理规则，因此，采用“首节点”和“尾节点”作为每类推理规则表的联合主键。在树种的识别过程中，需要通过查找“首节点”与上一规则的“尾节点”相同的规则，每个“首节点”“尾节点”都是大于等于0 的整数。当“尾节点”的值为0 时，代表该条规则已经结束，树种识别完成，立即读取该记录的树种编号，到造林树种表中查询其树种名称、树种、树种拉丁名、树种描述、树种分布等信息。“枝叶描述”是用户进行枝叶特征选择的基础，“树种编号”字段存储了规则结束对应的树种编号，是与造林树种表进行连接的外键。由于用户缺乏相关专业知识，难以对文本描述的枝叶特征进行理解和判断，因此，使用图片对推理规则涉及的所有枝叶特征进行直观展示，辅助用户进行枝叶特征的理解和判断。“枝叶描述图片名称”字段中以“img/表名/图名”的形式存储对应枝叶特征图片的路径和名称，通过路径和名称获取枝叶描述图片。由于“首节点”和“尾节点”是每类推理规则表的联合主键，因此，图片均以“图-首节点-尾节点”的形式进行命名，可以唯一标识每类推理规则下的图片。

由于表T1～T5 的关系模式相同，这里只给出表T1的实例（表2），T2～T5的实例不再赘述。

表2 推理规则表T1实例

3.2 推理算法设计

推理机制的选择需要与知识表示方式相匹配[20-21]。根据推理过程进行的方向，可以将推理机制分为3 种：正向推理、反向推理和双向推理[22]。正向推理机制是数据驱动推理，推理基础是逻辑演绎的推理链，与产生式规则表示法表示的知识结构吻合。因此，根据产生式规则表示法的特点，选择正向推理机制。本研究的推理算法设计主要包括枝叶特征读取、乔灌木识别两部分，具体推理算法如下：

步骤1 根据推理规则导航表T0中所有推理规则表对应的枝叶描述、枝叶描述图片，选定其中一类推理规则表。

步骤2 查询选定的推理规则表Ti(i=1,2,…,5)中所有首节点为1的枝叶特征记录，根据其对应的枝叶描述、枝叶描述图片，选择与事实一致的枝叶特征。

步骤3 获取选择的枝叶特征对应的尾节点，判断该尾节点是否为0，不为0进行步骤4，若为0转向步骤5。

步骤4 在推理规则表Ti 中查询所有首节点与步骤3中尾节点相同的枝叶特征记录，根据其对应的枝叶描述、枝叶描述图片，选择与事实一致的枝叶特征，转向步骤3。

步骤5 获取该枝叶特征对应的树种编号，查询造林树种表Trees中对应的树种信息并进行展示。

步骤6 推理结束。

根据乔灌木识别的推理算法，考虑数据库存储和编程特点和计算机的可操作性，设计了整个系统的推理数据流程，如图6所示。

图6 乔灌木识别推理流程图

图7 总体框架设计图

4 系统设计与实现

4.1 系统体系结构与功能结构设计

北京市乔灌木识别专家系统的总体框架设计如图7所示。用户可以通过网络访问到系统界面，对系统进行操作，系统通过访问枝叶检索知识、树种知识库，调取相应的知识和规则，对用户的行为做出响应，输出结果。北京市乔灌木识别专家系统的功能结构如图8所示，该系统主要包括以下3个功能模块：

（1）树种识别功能包括交互式枝叶特征提问，识别步骤退回、树种信息展示。其中识别步骤退回功能在页面中实时显示用户选择枝叶特征的路径，用户不仅能根据路径进行植物识别知识的学习，还能判断已经选择的枝叶特征是否有误，如果有误，可以返回上一步骤进行重新选择。树种信息展示功能是在树种识别结束后，通过被识别出的树种编号查询树种知识库，将该树种的信息、图片展示在页面中。

（2）树种组合条件查询可以根据乔灌木的树种编号、树种学名、树种别名、树种描述、树种分布、造林技术等条件进行组合查询，从树种知识库中查询满足条件所有树种，用户选择后浏览该树种的相关信息。

（3）知识库维护功能包括知识查询、知识增加、知识更新、知识删除，分别实现对枝叶检索知识库、树种知识库中的知识进行查询、增加、更新和删除，达到维护知识库的效果。

本系统以Java 为开发语言，采用了Spring MVC（Model，View，Control）框架，使将系统分为了3个层次：数据持久层、业务逻辑层和表现层。数据持久层：使用SQL Server 作为系统的数据库，使用Hibernate 框架对数据库操作进行封装；业务逻辑层：基于Spring框架，实现了用户知识查询的接口；表现层：使用Ajax、JQuery技术与接口进行数据的交互，实现系统的异步刷新，减少页面刷新次数，使基本功能由浏览器分流，用户友好性较强。

4.2 核心功能实现

北京市乔灌木识别专家系统核心功能的实现主要依靠2个关键算法：乔灌木识别算法、退回算法。

（1）乔灌木识别算法的实现

本算法包括3 部分：枝叶特征知识的读取、树种知识的读取、枝叶（树种）描述与图片的展示。依据图6设计的乔灌木识别推理数据流程图，具体的算法流程图如图9 所示。根据Spring MVC 架构的层次，代码的编写分为数据持久层、业务逻辑层和表现层，关键代码如下所示：

数据持久层：

String hql="from T1 where node=?"；

List list = find（hql，node）；

String hql="from Trees where treeNode=?"；

List list = find（hql，treeNode）；

业务逻辑层：

if（"T1".equals（type））{

List

list=selectTreeService.findSelectT1（node）；

returnWithJSONArray（response，list）；

……

}else if（"T5".equals（type））{

List list=

selectTreeService.findSelectT5（node）；

returnWithJSONArray（response，list）；}

表现层：

$.ajax（{

type：'POST'，

async：false，

url："../../selectTree/selectTreeTextDetail"，

dataType："json"，

data：{type：type，node：node}，

cache：false，

success：function（data）{ result=data；}}）；

If（node != 0）{

var result=_this.stepData（type，node）；

_this.detailStepShow（result，stepCount）；

}else{

var result=_this.findData（type，node）；

var endResult =

_this.endData（result.treeNode）；

this.endStepShow（endResult，stepCount）；}

（2）退回算法的实现

若只进行了一次枝叶特征问答，退回上一步需要从T0 表中查询所有记录；在已经进行了至少两次枝叶特征问答的情况下，通过节点的查找与链接，退回上一步。具体算法为：从存储已经选择的枝叶特征记录的数组中获取最后一条记录的首节点，利用该首节点在该子表中查询出首节点相同的所有枝叶特征记录，具体的算法流程如图10所示。由于本算法是在读取枝叶特征记录算法的基础上，增加了部分算法逻辑，因此代码的编写主要在表现层，关键代码如下所示：

表现层：

if（node=="1"）{ //从T0表查询所有记录

type = T0；

node= T0；

图8 功能结构图

var result=_this.stepData（type，node）；

_this.detailStepShow（result，stepCount）；

}else{

var endResult=_this.stepData1

（type，stepRecordArray[stepCount−1]）；

var node=endResult.node；

stepRecordArray.length=stepRecordArray.length−1；

var result=_this.stepData（type，node）；

_this.detailStepShow（result，stepCount）；}

图9 树种识别算法实现流程图

图10 退回算法实现流程图

4.3 运行实例

北京市乔灌木识别专家系统主要提供了根据枝叶特征来识别北京市乔灌木树种的服务，识别过程中为避免用户专业知识储备不足会造成枝叶特征选择疑惑的情况，采集了每个枝叶特征所对应的图片进行辅助选择。页面上方显示在该树种识别的过程中枝叶特征的选择路径，方便用户进行系统的知识学习；下方为枝叶特征单选框，选定某种枝叶特征后，页面右方会有相应的枝叶特征图片展示。以雪松为例，树种识别的过程和最终结果分别如图11和图12所示。

图11 树种识别过程

图12 树种识别结果

系统运行环境要求操作系统为64 位的Windows Server 2008 或更新的操作系统，WWW 服务器为Tomcat 7。硬件要求内存为16 GB，硬盘空间大于等于100 GB，处理器为Intel®Xeon®CPU E5-2620 v2 @2.10 GHz。使用JMeter开源测试工具，模拟多用户并发访问系统，对系统的性能进行评估。测试结果如图13所示，虚拟并发用户数为1 000时，系统平均响应时间约为20 ms，运行情况良好，能够有效地为公众提供树种识别服务。