基于手绘识别的程序设计教学系统研究与实现

2010-08-24金贵朝袁贞明

制造业自动化 2010年14期

关键词：草图流程图手绘

金贵朝，袁贞明

JIN Gui-chao1, YUAN Zhen-ming2

（1.杭州师范大学钱江学院，杭州 310012；2.杭州师范大学信息科学与工程学院，杭州 310036）

1 程序设计课在教学中存在的问题

1.1 过多地注重语法学习，忽视分析问题能力培养

目前为初学者提供的编程环境一般是解释编译器，要得到算法的结果，必须要求用户先保证输入语法的正确性，为帮助学生避免语法出错，容易导致教师花大量的时间介绍语法细节，而忽略了算法的讲解，这样做很容易造成学生在程序设计时思路不清晰，设计出的程序容易产生计算机难以发现的逻辑错误。

程序设计的基本步骤应包括分析问题、设计算法、编写程序和调试程序等，但由于实际教学中过多地强调语法，使得其它步骤经常被忽视，而教育专家则发现学生在分析问题和设计算法时，能极好地提高分析问题的能力与培养编程思维。换言之，程序设计教学是个综合过程，仅仅注重语法是很不正确的，会导致程序设计课应有的能力培养目标缺失。

1.2 流程图与程序之间存在概念上的差异

流程图采用图形化形象思维方式表现程序设计思想，程序则是由某种具体程序设计语言搭建起来的逻辑单元。然而，形象化的图形与抽象的逻辑模块之间并不是一一对应的，特别是在表达循环和分支结构时，按语句行顺序书写程序成了学生学习中的障碍，经常导致学生会画流程图但是不会写程序的现象出现。

2 基于手绘识别的程序设计教学系统设计

2.1 采用流程图进行程序设计教学的优势

为克服以上教学弊端，我们建议计算机教师选择程序流程图作为可视化的算法设计环境。选择流程图的原因如下：

1）流程图涉及到最少的语法知识

通过减少在语法上花费过多的精力，学生能在分析问题、寻找解决问题的策略上多下功夫。

2）流程图已被程序工作者普遍采用

美国国家标准化协会 (ANSI)规定了一些常用的流程图符号。流程图采用简单规范的符号，画法简单；用流程图描述算法结构清晰、直观，逻辑性强，不容易产生“歧义”，已被程序工作者普遍采用。

3）流程图易于理解

对于程序设计的初学者来说，流程图比结构化的代码更容易理解和接受。Thad Crews[1]对此进行了实验证明，借助流程图进行程序设计教学使学生掌握程序设计更快、更准确和更自信。因此，为提高学生的学习效率，Thad Crews还专门为程序设计课的教学设计了一个流程图解析器，但该流程图解析器不支持手绘草图识别。

2.2 基于手绘识别的C程序教学系统

我们所开发的C程序教学系统试图帮助教师充分利用流程草图进行程序设计教学。该系统为用户提供了一个流程图的手绘界面，是一个可视化的环境，其操作界面如图1所示。

系统启动后，等待用户绘制图形，教师在该系统上很容易进行流程草图的绘制，同时，由于该系统基于手绘草图识别技术，教师每绘制一个流程图符号，系统均能进行识别。师绘制好流程图后，只需在系统的右下角，点击“生成代码”按钮，系统即对整个流程图的结构进行逻辑判断，并且自动转换为C程序。

系统的左边是程序设计的流程图，而右边是相对应的C程序框架，同时还能进行编译和运行。教师引导学生通过对比学习，很容易帮助学生建立起流程图和程序代码的联系，既掌握了分析问题的能力，同时也切实提高了学生编写代码的能力。

图2 草图识别技术方案

3 系统实现

3.1 基于SVM的手绘草图识别技术

程序流程图涉及到平行四边形、矩形、菱形、六边形、圆、圆角矩形等图形符号，本系统采用基于SVM的在线草图识别技术，对流程图符号进行分类识别，技术路线如图2所示，主要包括三个模块，分别是样本数据获取、SVM分类器训练和基于SVM的手绘图形在线识别。

1）样本数据的获取模块：先采用基于Tablet SDK的手绘采集方法来获得用户训练样本的基本参数，并以XML文件格式存储用户所绘制的图形数据。设置该模块的目的为便于系统升级后，采用不同的预处理方法、选择不同的特征甚至分类器时，不需要用户重新输入训练样本。

2）SVM分类器训练模块：先加载训练数据文件，然后对训练数据进行预处理，最后根据样本数据的特征值设置SVM分类器。

系统通过计算相邻采样点之间的距离、设置一定的阈值去除噪声点，然后对图形进行平移、缩放等归一化处理。本系统利用具有旋转不变性的Zernike矩[2]提取图形特征，由于Zernike具有旋转不变性，但对于缩放和平移是变化的，因此在预处理过程中，系统需进行归一化以使得它们具有相同的尺度，并且它们的质心在相同的位置。

3）基于SVM的手绘图形在线识别模块：该模块同样先采用基于Tablet SDK的手绘采集方法在线得到手绘图形参数，然后对手绘图形进行预处理，计算基于Zernike矩的特征值，最后用已训练好的SVM分类器进行流程图符号的分类识别。

通过基于SVM的草图识别技术，系统可识别出用户绘制的流程图符号，如图3-5所示。

图3 矩形草图识别结果

图4 平行四边形草图识别结果

图5 菱形草图识别结果

3.2 程序流程图逻辑自动解析

本系统不仅能通过手绘草图识别技术识别流程图中的每个学科符号，而且通过对流程图逻辑的自动识别算法实现正向工程即C程序代码的自动生成。

流程图程序逻辑的识别主要基于基本图元的组合信息，把每个图元作为基本节点进行存储，并结合流程图逻辑结构知识，构造流程图逻辑关系图，进行存储和遍历访问。

流程图一般可用最基本的三种数据结构来表示，本系统也把流程图分为三种结构来进行存储。

1）顺序结构

顺序结构是流程图的基础部分，用于最小分支的顺序结构图可以是矩形、平行四边形、圆角矩形。

其中矩形和平行四边形为单进单出模块，入度为1，出度为1；圆角矩形为单进或单出模块，用于流程图的开始和结束。

2）分支结构

系统识别为菱形时，需压入堆栈S，然后根据所上下文信息进行数据更新，若符合分支模块的特点，则创建为分支模块。进行数据结构的存贮更新，创建完毕后需进行出栈更新操作。

分支模块的特点是：入度为1，出度为2，且出度的两个方向最终会相交，如图6所示。

图6 分支模块

3）循环结构

系统识别为判断框时，需压入堆栈S，然后根据所绘制的图元进行数据更新，若符合循环模块，则创建为循环模块，进行数据结构的存贮更新，创建完毕后需进行出栈更新操作。

循环模块的特点是：入度为2，出度为2，且出度方向有一条边最终指回该模块，如图7所示。

图7 循环模块

通过对流程图的构造，采用递归访问法，实现流程图逻辑自动识别算法。

4 实验研究与分析

我们通过运用本系统，进行了程序设计教学的实验研究。

表1 A组与B组教学设计片段

1）研究对象：杭州师范大学计算机科学与技术专业共78名大一学生，按照平行班分成两组：A组39人、B组39人。

2）研究方法：对比实验法。

3）研究过程：A组采用多媒体PPT辅助教学，B组采用本系统辅助教学，最后对A组与B组的教学效果进行评估。

4）教学设计片段：如表1所示。

图8 程序流程图

图9 自动生成C代码

5）研究结果：A组中，有24位同学能根据所提供的问题进行分析并绘制出其流程图，但这24位同学中，只有11位同学能正确编写代码，其余13位无法将流程图转换为C程序代码。另外的15位同学，均未能正确绘制流程图，其中有6位同学能正确编写程序代码。

B组中，有30位同学能正确绘制流程图，其中有26位同学能正确编写出C程序代码。另外的9位同学，未能正确绘制流程图。

6) 实验表明：传统的教学方法，往往将流程图的绘制和编写程序两个紧密相关的过程割裂开来，要么忽视问题的分析与算法的设计，要么忽视程序编写能力的培养，不能有效地实现概念之间的关联，影响了学习效率。

采用本系统进行教学，能把教师绘制的流程图转换成可执行程序并自动运行。绘制流程图的过程就是引导学生进行思考分析和提高学生自上而下程序设计思想的过程，学生的主要精力和聚焦点主要放在程序设计的整体结构和思路上，可减少学生对于语法细节的过度关注，不过多拘泥于语法，在教学中可以腾出更多的时间帮助学生思考如何用流程图来设计算法，培养学生分析问题和设计算法的能力和思路。同时，教师在绘制流程图的过程中，可在操作框中添加一些必要的语句，帮助学生掌握一些必要的程序设计的语法。

采用本系统进教学，能帮助学生克服不懂得如何将流程图表达的算法转换成某种高级语言程序的困难，促进学生对程序设计等问题的进一步理解，提高教学效果。