基于手繪識別的程序設(shè)計教學系統(tǒng)研究與實現(xiàn)

金貴朝，袁貞明

JIN Gui-chao1, YUAN Zhen-ming2

（1.杭州師范大學 錢江學院，杭州 310012；2.杭州師范大學 信息科學與工程學院，杭州 310036）

1 程序設(shè)計課在教學中存在的問題

1.1 過多地注重語法學習，忽視分析問題能力培養(yǎng)

目前為初學者提供的編程環(huán)境一般是解釋編譯器，要得到算法的結(jié)果，必須要求用戶先保證輸入語法的正確性，為幫助學生避免語法出錯，容易導致教師花大量的時間介紹語法細節(jié)，而忽略了算法的講解，這樣做很容易造成學生在程序設(shè)計時思路不清晰，設(shè)計出的程序容易產(chǎn)生計算機難以發(fā)現(xiàn)的邏輯錯誤。

程序設(shè)計的基本步驟應包括分析問題、設(shè)計算法、編寫程序和調(diào)試程序等，但由于實際教學中過多地強調(diào)語法，使得其它步驟經(jīng)常被忽視，而教育專家則發(fā)現(xiàn)學生在分析問題和設(shè)計算法時，能極好地提高分析問題的能力與培養(yǎng)編程思維。換言之，程序設(shè)計教學是個綜合過程，僅僅注重語法是很不正確的，會導致程序設(shè)計課應有的能力培養(yǎng)目標缺失。

1.2 流程圖與程序之間存在概念上的差異

流程圖采用圖形化形象思維方式表現(xiàn)程序設(shè)計思想，程序則是由某種具體程序設(shè)計語言搭建起來的邏輯單元。然而，形象化的圖形與抽象的邏輯模塊之間并不是一一對應的，特別是在表達循環(huán)和分支結(jié)構(gòu)時，按語句行順序書寫程序成了學生學習中的障礙，經(jīng)常導致學生會畫流程圖但是不會寫程序的現(xiàn)象出現(xiàn)。

2 基于手繪識別的程序設(shè)計教學系統(tǒng)設(shè)計

2.1 采用流程圖進行程序設(shè)計教學的優(yōu)勢

為克服以上教學弊端，我們建議計算機教師選擇程序流程圖作為可視化的算法設(shè)計環(huán)境。選擇流程圖的原因如下：

1）流程圖涉及到最少的語法知識

通過減少在語法上花費過多的精力，學生能在分析問題、尋找解決問題的策略上多下功夫。

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

美國國家標準化協(xié)會 (ANSI)規(guī)定了一些常用的流程圖符號。流程圖采用簡單規(guī)范的符號，畫法簡單；用流程圖描述算法結(jié)構(gòu)清晰、直觀，邏輯性強，不容易產(chǎn)生“歧義”，已被程序工作者普遍采用。

3）流程圖易于理解

對于程序設(shè)計的初學者來說，流程圖比結(jié)構(gòu)化的代碼更容易理解和接受。Thad Crews[1]對此進行了實驗證明，借助流程圖進行程序設(shè)計教學使學生掌握程序設(shè)計更快、更準確和更自信。因此，為提高學生的學習效率，Thad Crews還專門為程序設(shè)計課的教學設(shè)計了一個流程圖解析器，但該流程圖解析器不支持手繪草圖識別。

2.2 基于手繪識別的C程序教學系統(tǒng)

我們所開發(fā)的C程序教學系統(tǒng)試圖幫助教師充分利用流程草圖進行程序設(shè)計教學。該系統(tǒng)為用戶提供了一個流程圖的手繪界面，是一個可視化的環(huán)境，其操作界面如圖1所示。

系統(tǒng)啟動后，等待用戶繪制圖形，教師在該系統(tǒng)上很容易進行流程草圖的繪制，同時，由于該系統(tǒng)基于手繪草圖識別技術(shù)，教師每繪制一個流程圖符號，系統(tǒng)均能進行識別。師繪制好流程圖后，只需在系統(tǒng)的右下角，點擊“生成代碼”按鈕，系統(tǒng)即對整個流程圖的結(jié)構(gòu)進行邏輯判斷，并且自動轉(zhuǎn)換為C程序。

系統(tǒng)的左邊是程序設(shè)計的流程圖，而右邊是相對應的C程序框架，同時還能進行編譯和運行。教師引導學生通過對比學習，很容易幫助學生建立起流程圖和程序代碼的聯(lián)系，既掌握了分析問題的能力，同時也切實提高了學生編寫代碼的能力。

圖2 草圖識別技術(shù)方案

3 系統(tǒng)實現(xiàn)

3.1 基于SVM的手繪草圖識別技術(shù)

程序流程圖涉及到平行四邊形、矩形、菱形、六邊形、圓、圓角矩形等圖形符號，本系統(tǒng)采用基于SVM的在線草圖識別技術(shù)，對流程圖符號進行分類識別，技術(shù)路線如圖2所示，主要包括三個模塊，分別是樣本數(shù)據(jù)獲取、SVM分類器訓練和基于SVM的手繪圖形在線識別。

1）樣本數(shù)據(jù)的獲取模塊：先采用基于Tablet SDK的手繪采集方法來獲得用戶訓練樣本的基本參數(shù) ，并以XML文件格式存儲用戶所繪制的圖形數(shù)據(jù)。設(shè)置該模塊的目的為便于系統(tǒng)升級后，采用不同的預處理方法、選擇不同的特征甚至分類器時，不需要用戶重新輸入訓練樣本。

2）SVM分類器訓練模塊：先加載訓練數(shù)據(jù)文件，然后對訓練數(shù)據(jù)進行預處理，最后根據(jù)樣本數(shù)據(jù)的特征值設(shè)置SVM分類器。

系統(tǒng)通過計算相鄰采樣點之間的距離、設(shè)置一定的閾值去除噪聲點，然后對圖形進行平移、縮放等歸一化處理。本系統(tǒng)利用具有旋轉(zhuǎn)不變性的Zernike矩[2]提取圖形特征，由于Zernike具有旋轉(zhuǎn)不變性，但對于縮放和平移是變化的，因此在預處理過程中，系統(tǒng)需進行歸一化以使得它們具有相同的尺度，并且它們的質(zhì)心在相同的位置。

3）基于SVM的手繪圖形在線識別模塊：該模塊同樣先采用基于Tablet SDK的手繪采集方法在線得到手繪圖形參數(shù)，然后對手繪圖形進行預處理，計算基于Zernike矩的特征值，最后用已訓練好的SVM分類器進行流程圖符號的分類識別。

通過基于SVM的草圖識別技術(shù)，系統(tǒng)可識別出用戶繪制的流程圖符號，如圖3-5所示。

圖3 矩形草圖識別結(jié)果

圖4 平行四邊形草圖識別結(jié)果

圖5 菱形草圖識別結(jié)果

3.2 程序流程圖邏輯自動解析

本系統(tǒng)不僅能通過手繪草圖識別技術(shù)識別流程圖中的每個學科符號，而且通過對流程圖邏輯的自動識別算法實現(xiàn)正向工程即C程序代碼的自動生成。

流程圖程序邏輯的識別主要基于基本圖元的組合信息，把每個圖元作為基本節(jié)點進行存儲，并結(jié)合流程圖邏輯結(jié)構(gòu)知識，構(gòu)造流程圖邏輯關(guān)系圖，進行存儲和遍歷訪問。

流程圖一般可用最基本的三種數(shù)據(jù)結(jié)構(gòu)來表示，本系統(tǒng)也把流程圖分為三種結(jié)構(gòu)來進行存儲。

1）順序結(jié)構(gòu)

順序結(jié)構(gòu)是流程圖的基礎(chǔ)部分，用于最小分支的順序結(jié)構(gòu)圖可以是矩形、平行四邊形、圓角矩形。

其中矩形和平行四邊形為單進單出模塊，入度為1，出度為1；圓角矩形為單進或單出模塊，用于流程圖的開始和結(jié)束。

2）分支結(jié)構(gòu)

系統(tǒng)識別為菱形時，需壓入堆棧S，然后根據(jù)所上下文信息進行數(shù)據(jù)更新，若符合分支模塊的特點，則創(chuàng)建為分支模塊。進行數(shù)據(jù)結(jié)構(gòu)的存貯更新，創(chuàng)建完畢后需進行出棧更新操作。

分支模塊的特點是：入度為1，出度為2，且出度的兩個方向最終會相交，如圖6所示。

圖6 分支模塊

3）循環(huán)結(jié)構(gòu)

系統(tǒng)識別為判斷框時，需壓入堆棧S，然后根據(jù)所繪制的圖元進行數(shù)據(jù)更新，若符合循環(huán)模塊，則創(chuàng)建為循環(huán)模塊，進行數(shù)據(jù)結(jié)構(gòu)的存貯更新，創(chuàng)建完畢后需進行出棧更新操作。

循環(huán)模塊的特點是：入度為2，出度為2，且出度方向有一條邊最終指回該模塊，如圖7所示。

圖7 循環(huán)模塊

通過對流程圖的構(gòu)造，采用遞歸訪問法，實現(xiàn)流程圖邏輯自動識別算法。

4 實驗研究與分析

我們通過運用本系統(tǒng)，進行了程序設(shè)計教學的實驗研究。

表1 A組與B組教學設(shè)計片段

1）研究對象：杭州師范大學計算機科學與技術(shù)專業(yè)共78名大一學生，按照平行班分成兩組：A組39人、B組39人。

2）研究方法：對比實驗法。

3）研究過程：A組采用多媒體PPT輔助教學，B組采用本系統(tǒng)輔助教學，最后對A組與B組的教學效果進行評估。

4）教學設(shè)計片段：如表1所示。

圖8 程序流程圖

圖9 自動生成C代碼

5）研究結(jié)果：A組中，有24位同學能根據(jù)所提供的問題進行分析并繪制出其流程圖，但這24位同學中，只有11位同學能正確編寫代碼，其余13位無法將流程圖轉(zhuǎn)換為C程序代碼。另外的15位同學，均未能正確繪制流程圖，其中有6位同學能正確編寫程序代碼。

B組中，有30位同學能正確繪制流程圖，其中有26位同學能正確編寫出C程序代碼。另外的9位同學，未能正確繪制流程圖。

6) 實驗表明：傳統(tǒng)的教學方法，往往將流程圖的繪制和編寫程序兩個緊密相關(guān)的過程割裂開來，要么忽視問題的分析與算法的設(shè)計，要么忽視程序編寫能力的培養(yǎng)，不能有效地實現(xiàn)概念之間的關(guān)聯(lián)，影響了學習效率。

采用本系統(tǒng)進行教學，能把教師繪制的流程圖轉(zhuǎn)換成可執(zhí)行程序并自動運行。繪制流程圖的過程就是引導學生進行思考分析和提高學生自上而下程序設(shè)計思想的過程，學生的主要精力和聚焦點主要放在程序設(shè)計的整體結(jié)構(gòu)和思路上，可減少學生對于語法細節(jié)的過度關(guān)注，不過多拘泥于語法，在教學中可以騰出更多的時間幫助學生思考如何用流程圖來設(shè)計算法，培養(yǎng)學生分析問題和設(shè)計算法的能力和思路。同時，教師在繪制流程圖的過程中，可在操作框中添加一些必要的語句，幫助學生掌握一些必要的程序設(shè)計的語法。

采用本系統(tǒng)進教學，能幫助學生克服不懂得如何將流程圖表達的算法轉(zhuǎn)換成某種高級語言程序的困難，促進學生對程序設(shè)計等問題的進一步理解，提高教學效果。

5 結(jié)論

本文針對目前程序設(shè)計教學存在的問題，設(shè)計和開發(fā)了一個基于手繪識別的程序教學系統(tǒng)，并進行了實驗研究。實驗表明，該系統(tǒng)有助于學生學習程序設(shè)計，且該系統(tǒng)具有易用性、有效性、自然交互性等特點。但仍然存在一些問題值得研究，如系統(tǒng)的識別率和可靠性有待我們繼續(xù)完善和提高。

[1] Thad Crews,Uta Ziegler.The Flowchart Interpreter for Introductory Programming Courses[A].SIGCSE 1999,276-280.

[2] 楊政武,方濤.基于Zernike矩的圖像歸一化技術(shù)的研究[J].計算機工程,2004,30(12)：34-36.

[3] 梁爽,孫正興.手繪草圖識別方法研究[J].計算機工程,2005,31(19)：170-172.