基于草繪的圖形手勢識別系統(tǒng)

基于草繪的圖形手勢識別系統(tǒng)摘要：當今計算機輔助教學系統(tǒng)目前已在教學中大量應用，傳統(tǒng)的數(shù)學幾何教學過程中，老師們要在黑板上板書很多圖形。這樣首先增加了老師們的負擔，其次，由于在人為作圖過程中難免會出現(xiàn)一些不準確的地方，勢必會造成學生們理解上的誤差。因此，開發(fā)一個基于草繪的圖形手勢識別系統(tǒng)顯的很有必要。本文主要就是介紹了一個簡單的識別系統(tǒng)，由于作者水平有限，能力有限，開發(fā)目的也并非是開發(fā)一個完整的產(chǎn)品，而是實踐軟件開發(fā)過程以及熟悉圖形圖像知識體系，所以系統(tǒng)相對脆弱，存在著諸多功能和健壯性上等等的缺陷，并不能應用到實際當中。開發(fā)背景：首先為了研究基于草繪的圖形手勢識別系統(tǒng)，參考閱讀了大量的國內(nèi)國外論文。目前來看，關于這方面的研究國外比擬多，而國內(nèi)相對較少，國內(nèi)比擬具有權威性的研究這方面的機構主要集中在中科院，浙江大學，以及中國傳媒大學。通過查閱資料獲知，最近的一篇關于手勢識別系統(tǒng)的國內(nèi)的論文是在2007年12份，中科院發(fā)表的《基于筆交互的智能動態(tài)幾何可視化白板系統(tǒng)》的論文。論文比擬詳細的介紹了系統(tǒng)中可以實現(xiàn)的功能，總結如下：一，手繪的草圖中可以識別的一些根本圖形，包括：點，線，角，三角形，圓，矩形。二，可以實現(xiàn)動態(tài)幾何的處理，例如：給定一個三角形，分別作出三條角平分線，那么我們固定三角形的兩個頂點，隨意拖動另一個頂點，角平分線將始終相交于一點。本文中主要研究的是對根本圖形以及一些手勢的識別。當然通過查閱，發(fā)現(xiàn)了國外有很多關于草圖，手勢識別的算法，并且算法之間各不相同，在論文中會挑選出幾種算法予以介紹。系統(tǒng)簡介：基于草繪的圖形手勢識別系統(tǒng)主要實現(xiàn)的功能主要分為兩局部，一：對根本圖形的識別：包括直線，三角形，矩形，圓，菱形，橢圓。二：對一些復雜圖形以及局部手勢的識別：刪除手勢，球，圓柱，立方體。如圖1。其中：球體用一個圓和圓內(nèi)一點來表示，以此來區(qū)別和圓的表示。立方體用一直角加一斜線來表示，圓柱用一橢圓和一豎線表示，刪除手勢用波浪線來表示。圖1開發(fā)系統(tǒng)的知識能力狀況：本系統(tǒng)打算在VisualC++6.0MFC框架下做，因為MFC已經(jīng)提供了很多已有的對話框顯示以及消息觸發(fā)等的功能。而本人之前沒有學習過C++,MFC根本上可以脫離C++編程語言模式。至少我用C語言的編程習慣根本能適應MFC的開發(fā)。當然由于本人確實沒有C++的編程根底，加上對計算機圖形學也是略懂一點，這勢必導致了工程的不成熟和諸多錯誤。所以，本工程的出發(fā)點就是研究性學習，主要學習了國內(nèi)外關于這方面的研究的現(xiàn)狀，以及各種方法的比擬，并比擬之后總和選擇了一個相對簡單的實現(xiàn)方法，來完成這個系統(tǒng)。本工程的另一個目的也是感受，體驗軟件工程的編程思想，為以后自己在工程開發(fā)中積累根底經(jīng)驗。系統(tǒng)設計的關鍵技術以及研究得到的算法：系統(tǒng)中主要的難點就是對用戶輸入的草圖的識別。顯然用戶的不定性導致了每個人輸入的圖形的千差萬別，同時由于在輸入過程中鼠標的滑動帶來的誤差也勢必導致輸入圖形的不精確性，這就需要我們對于這些草圖進行識別。而工程中的關鍵技術就是如何識別出不同的輸入，并且能保證誤差處在一個可容忍的限定內(nèi)。通過對國內(nèi)外論文的搜集，總結出以下幾種方法：算法一：JoaquimA.Jorge和ManuelJ.Fonseca發(fā)表的一篇論文《ASimpleApproachtoRecogniseGeometricShapesInteractively》中提到了一個識別算法，算法的根本思想是：當用戶輸入一些草圖后，我們對草圖進行處理，求出三個特殊的圖形，草圖所包圍的封閉區(qū)域圍成的圖形，我們稱這個圖形為凸形，用ch表示；第二個圖形是用戶輸入的草圖的最小外圍矩形，我們用er表示；第三個圖形是用戶輸入的草圖中的最大內(nèi)接三角形，我們用lt來表示，相應的圖形如圖2；相應的這些圖形的面積和周長，以前面加A或者L表示。凸形的面積就用Ach表示。圖2確定了三個根本圖形之后就可以根據(jù)這些圖形的面積和周長比值范圍來區(qū)分不同的輸入。如圖3和圖4：圖3圖4具體的比例對應關系如下：刪除手勢：Len/Pch，在這個比率關系上刪除手勢相對于其他的圖形有著較大的區(qū)別，刪除手勢的比率在2~4之間，而其他的都在1.5一下。如圖5所示：圖5同理其他圖形：圓如圖6：圖6線段：圖7三角形：圖8矩形：圖9菱形和橢圓：圖10本人認為這個算法相比照擬好，比擬簡單，并且在處理不同的圖形上，自由發(fā)揮度也比擬大，但是同樣難免會在個別圖形的識別上存在這誤差，比方在處理橢圓和菱形的時候，由于用戶輸入的要求誤差較小，所以很難加以清晰區(qū)分。算法二：DeanRubine在他的論文《StatisticalSingle-StrokeGestureRecognition》中提到了另一個算法：其原理是，第一步：允許用戶自己事先定義圖形和手勢，定義完這些圖形，手勢之后，第二步：用戶輸入各種各樣的圖形進行采樣，大約需要用戶輸入每一個相同類的草圖10-20次，例如，輸入三角形草圖10-20次，第三步：程序?qū)γ恳活惒輬D抽取特征值〔這個提取特征值是在連續(xù)輸入一類草圖之后立即采取的〕，使用一個線性判斷函數(shù)來對這些特征值分析，最終確定每一個類定義的圖形、手勢的權值當用戶對所有定義的草圖采樣結束之后，就把這些權值作為區(qū)分不同圖形的標志。至此，識別系統(tǒng)完成。當用戶再次輸入一個草圖時，就可以識別這個草圖屬于哪類精確的圖形。換言之：草圖、手勢識別分兩部完成，第一步：從輸入中提取特征值，第二步：使用線性判斷函數(shù)來確定草圖、手勢屬于哪一類。而選擇特征值的標準有以下幾個：對于每個輸入點特征在常量時間內(nèi)是可計算的，輸入中小的改變應該引起每個特征也有相應的改變，特征應該有意義，使它可以用于手勢語義。要有足夠的特征區(qū)分所有的手勢〔從執(zhí)行效率的角度考慮，不能有太多的手勢〕。而實際中用到的特征值有：1.手勢初始角的余弦〔f1〕和正弦〔f2〕2.邊界盒對角線的長度〔f3〕和角〔f4〕3.第一個采樣點和最后一個采樣點之間的距離〔f5〕4.第一個采樣點和最后一個采樣點之間角的余弦〔f6〕和正弦〔f7〕5.手勢的總長度〔f8〕6.總的角度(f9)7.每個采樣點的角度絕對值的和〔f10〕8.每個采樣點的角度平方的和〔f11〕9.手勢的最大速度〔f12〕10.手勢的持續(xù)時間〔f13〕如圖11：圖11而特征值的計算如圖11：圖11計算完所有的特征值之后：對這些特征值進一步的處理，例如我們現(xiàn)在計算得到了一個C類圖形的全部特征值。C類圖形的權值用下面的一個公式得到：其中：Ec是手勢類c訓練實例的數(shù)量，fcei是手勢類c的第e個實例的第i個特征，式子左邊f(xié)ci是特征的平均值。然后根據(jù)不同的特征值范圍就可以區(qū)分出不同的圖形。此算法雖然比擬人性化，可以允許用戶輸入自己定義的圖形和手勢，但是仍然存在這缺乏，首先當用戶定義的圖形、手勢過多時，那么在特征值的選取上就需要選擇更多的特征值，以區(qū)別，其次，也極有可能出現(xiàn)無法區(qū)分不同類的圖形、手勢的問題，同時，由于所有的特征值都是基于向量的概念，在圖形的輸入繪制上方向就顯的重要起來，逆時針和順時針輸入都會產(chǎn)生不同的權值。再次，所有的輸入必須是一筆完成，但在現(xiàn)實中，當用戶輸入一個較為復雜的圖形，那么需要多筆畫輸入，系統(tǒng)將無法為其效勞。所以，這個算法有其局限性和需要改良之處。除此之外，我還找了幾篇關于草圖識別的論文，關于這方面的研究，國外的論文比擬多一些。其中比擬代表性的還有：ChrisCalhoum,ThomasF.Stahovich,TolgaKurtoglu,LeventBurakKara發(fā)表的《RecognizingMulti-StrokeSymbols》中提到的一個算法，這篇論文中主要采用了一個比擬好的思想，先是對用戶輸入的草圖進行去噪處理。根本過程是：第一步：分割草圖，尋找分割點當用戶輸入一個草圖之后，由于圖形的不同形狀，那么在用戶輸入過程中的速度不一樣，這樣設置一個速度閥，低于這個時間閥，就在相應的像素點設置斷點，這樣，一個草圖就會被分割成很多個斷點。具體舉例如下：當輸入一個草圖矩形的時候，由于矩形和我們輸入方式的特點，必然會在矩形拐角的時候，筆的速度會變慢，那么我們就把四個拐點作為斷點。如圖12：圖12其中的速度V是根據(jù)單位時間內(nèi)走過的像素點來確定的。第二步：當我們確定了所有的斷點之后，剩下的就是去噪了。去噪后的斷點間的連線只分為弧和線段，方法是在相鄰兩個鄰點之間做連線，那么這兩個斷點之間的每個像素點到這條連線就有矢量距距離，如圖13：圖13圖13中的上半局部是原始圖形抽象出來的像素點，曲線AB是用戶輸入的草圖，AB為斷點，直線AB是A,B兩斷點的連線，假設連線左邊的像素點到直線的距離為正，那么右邊的像素點那么為負。那么所有的距離加起來有個權值，我們同樣設置一個權值閥，在此例中，去噪后的圖形，AB間的連線只會出現(xiàn)直線段，左弧，右弧度三種情況，并且所有去噪后的兩個相鄰斷點之間的連線都只有這三種情況。圖13中，根據(jù)權值閥判定，A,B之間應該是個左弧，圖13的下半局部就是去噪后的圖形。當完成這兩步之后，就可以根據(jù)去噪之后的圖形進行判定最終屬于哪類精確圖形，而怎么判定，論文中并沒有給出明確算法，只是提到，每個圖形都有事先給定的標準，然后，去噪后的圖形最符合哪個精確圖形的標準，就判定它屬于那個精確圖形。系統(tǒng)設計和實現(xiàn)：由于本系統(tǒng)主要的局部還是研究目前已有的算法。而前面也已給本系統(tǒng)做了簡單介紹。主要思路是，首先先把所有能夠識別的草圖分成兩局部，一：簡單圖形，直線，三角形，矩形，圓，菱形，橢圓，刪除手勢。二：復雜圖形：，球，圓柱，立方體。提示用戶輸入的是簡單圖形還是復雜圖形。然后用戶使用鼠標左鍵輸入草圖，點擊右鍵會觸發(fā)一個消息，對所輸入的圖形進行判斷。判斷的算法采取了上述中的算法一：JoaquimA.Jorge和ManuelJ.Fonseca發(fā)表的一篇論文《ASimpleApproachtoRecogniseGeometricShapesInteractively》中提到了一個識別算法。而這個算法的重點在于如何求得那三個圖形。即：草圖所包圍的封閉區(qū)域圍成的圖形ch，用戶輸入的草圖的最小外圍矩形er，用戶輸入的草圖中的最大內(nèi)接三角形lt。同樣查閱了很多資料，結合自己的一些簡單想法，首先把用戶輸入的圖形的所有的像素點都存在了一個二維數(shù)組中，數(shù)組中記錄了每一個像素點的X坐標和Y坐標。當用戶輸入一個草圖之后，將草圖圍成的區(qū)域劃分成由每一條水平線段組成〔所有的面都是由線組成〕。那么每條線段的左右兩點的坐標差，就是線段的距離，所有的線段的距離之和，就是所圍圖形的面積。而圖形的州長就是數(shù)組里元素的總個數(shù)。這樣就可以求得Pch和Ach。而對最小外圍矩形er，方法主要有求得這個草圖曲線區(qū)域的路徑，然后用API函數(shù)得到路徑的外接矩形。然后旋轉草圖曲線，重復前面的過程，直到找到最小的矩形。而對于最大內(nèi)接三角形lt，我一直在尋找，但是到目前為之仍然沒有尋找到到一個適宜的可信的算法。沒有方法為了完成系統(tǒng)的設計，我只能選擇了一個近似的方法。在草圖中選取八個點，然后計算這八個點中任意三點圍成的面積，選擇面積最大的那個值。這八個點是選擇了最左邊，最右邊，最上面，最下面，以前他們相鄰兩點之間的一個點，組成了八個點。這樣就可以求出Pch，Ach，Per，Aer，Plt，Ale。剩下的工作就是來確定每個圖形的比率范圍，簡單圖形如下：線段：Pch/Ach>105；三角形：Alt/Ach>0.8矩形：Pch/Per>0.9圓：Pch/Ach<13.2；菱形：Alt/Aer<0.5橢圓：Ach*Ach/Aer*Alt<1.47刪除手勢：Aer/Pch>1.7復雜圖形：球：Pch/Ach>105<13.2〔事先判斷了隸屬于哪類圖形〕；圓柱：14>Pch/Ach<100立方體：Pch/Per>0.9以下是局部試驗結果截圖，并且局部圖形已經(jīng)給用紅色線段給出了判斷之后并且規(guī)整成了準確圖形，其中黑色線是原始圖形。圖14圖15圖16圖17圖18圖19圖20圖21圖22圖23工程結論、討論：正如我前面講到的，由于本人編程根底比擬薄弱，能力有限，尤其對C++預言學習不夠，本論文重點在于學習研究國內(nèi)外有關草繪草圖手勢識別方面的論文和文獻以及熟悉軟件開發(fā)過程，同時希望通過本小工程讓自己熟悉圖形圖像的根本編程原理，對以后的圖形圖像的學習提供前言根底。為此，我前后一共閱讀了國內(nèi)外此方面的論文約10余篇，詳細研究了其中的6篇。就工程本身而言，存在著各種各樣的錯誤和缺乏，尤其在處理菱形，橢圓，以及圓這三個圖形時，會出現(xiàn)判斷錯誤的現(xiàn)象。JoaquimA.Jorge和ManuelJ.Fonseca的論文中提到識別率可以到達93%以上，由于在局部的算法技術實現(xiàn)方面我并未完全按照論文介紹的方法執(zhí)行，所以在這三個圖形的識別率中沒有到達90%。本身工程中還存在著功能上的缺陷，對于簡單圖形和復雜圖形這兩個不同類的識別采用的是，系統(tǒng)要求用戶首先選擇：輸入的是為簡單圖形還是復雜圖形。下一步需要改良的是，不需要用戶告訴機器，草圖為簡單圖形還是復雜圖形，應當機器自己識別，這就要求在識別復雜圖形的問題上繼續(xù)挖掘它們的特征值，以此區(qū)分出和簡單圖形的不同。同時，從工程試驗結果的截圖中可以看出，僅僅能給出局部圖形的輸出詳細信息。例如，在輸出圓的同時，給出了圓的半徑，在輸出矩形的時候同樣給出了矩形的邊長，這樣就可以根據(jù)這些信息繪出準確圖形，遺憾的是并不是所有的圖形都給出了輸出信息，大局部僅是判斷出形狀而已，深層原因還是技術上沒有自己研究過這類問題。當然本論文的重點不是輸出形狀，而是判斷草圖形狀。相關參考文獻：JoaquimA.Jorge,ManuelJ.Fonseca,〞ASimpleApproachtoRecogniseGeometricShapesInteractively〞.DepartamentodeEngenhariaInformaticaIST/UTL,Av.RoviscoPaisManuelJ.Fonseca,CesarPimentel,JoaquimA.Jorge“AnOnlineScribbleRecognizerforCalligraphicInterfaces〞DepartmentofInformationSystemsandComputerScienceINESC-ID/IST/TechnicalUniversityofLisbonR.AlvesRedol,9,1000-029LisboaChrisCalhoun,ThomasF.Stahovich,TolgaKurtoglu,LeventBurakKara,〞