識別手寫輸入的方法
2023-04-29 00:59:21 1
專利名稱：識別手寫輸入的方法
技術領域：
本發明涉及手寫識別，具輸入涉及個體字識別。
人手寫輸入的機器識別是個困難的問題，隨著筆基(pen-based)計算裝置的最近迅速增長，手寫輸入的機器識別已成為一個重要問題被提出來。人手寫輸入的機器識別當前具有各種應用。
對於人手寫輸入的機器識別的一個當前應用例子在EO和New-ton產品之類的個人數字輔助裝置中可以看到。這種類型的產品通常具有一個觸摸敏感的螢光屏，用戶能在它上面寫手寫字。然後，這類裝置對手寫輸入諸如字母數字輸入進行數位化，隨後處理該輸入，以試圖識別手寫的信息內容。
按照一種先有技術的手寫識別技術，對於依序識別每個字母數字字符串可以作出最佳判斷，由此得到的字符串包括識別活動性的結果。這種方法存在多種缺點。它受礙於難以識別待識別的候選輸入(在目前情況下是字母數字符)的空間邊界。當這些邊界不正確地就位時，因它缺少筆劃或包含從相鄰字符引入額外的材料，故不能準確地識別該字符。
對於人手寫輸入的機器識別的一個重要問題是識別出一個輸入的結束和下一個輸入的開始的能力。例如，一個明顯的問題是從其隨後的手寫輸入段、字或字母數字輸入的開始定位這個手寫輸入段、字或字母數字的結束。分辨手寫輸入的這種不良識別導致對手寫輸入的信息內容的差和不準確的解釋。
據此，現在需要一種能從第二個手寫輸入段的開始檢測出第一手寫輸入段的結束的手寫識別技術，藉此對該手寫輸入的信息內容提供較準確的解釋。
圖1示出按照本發明的優選實施例的操作流程圖。
圖2示出按照本發明的優選實施例的一個顯示器的示例圖。
圖3示出按照本發明的優選實施例的另一個顯示器的示例圖。
圖4示出按照本發明的優選實施例的又一個顯示器的示例圖。
圖5示出按照本發明的優選實施例的再一個顯示器的示例圖。
手寫字符輸入典型地以離散的連續段的形式從用戶收集到。一個離散的連續段是由一個或多個筆劃組成的，這裡，一個筆劃是指在筆尖與一個數位化圖形輸入卡或紙之類的輸入裝置相接觸期間由筆尖留下的印記。一個筆劃可由輸入裝置以大致規則的時間間隔取樣的一系列點來表示。每個點最少由一個X座標和一個Y座標來描述。筆劃可以利用一個數位化圖形輸入卡以電學方式捕獲，或者另一個實施例中，利用圖像中線條的檢測過程從一個被掃描的或被傳真的圖像中得到，這種以電學方式捕獲輸入的方法在本領域內是可以理解的。
總的來說，這裡所公開的本發明確定兩個離散的連續段是構成同一手寫字符輸入的一部分還是構成一個以上的手寫字符輸入的一部分。在本發明中，一個或多個離散的連續段是待識別的手寫輸入的單元。手寫輸入是以電學方式捕獲的輸入，它包括但並不限制於以下方面手寫輸入；電子輸入；由壓力捕獲的輸入例如印模輸入；以電學方式接收的輸入，例如通過傳真、尋呼機或其它裝置來的輸入。例如，本發明判定兩個離散的連續段是構成同一個字的一部分還是構成幾個單獨分離的字的一部分。在一種優選方法中，本發明計算基本上與書寫軸平行配置的一個或多個基本上平行的距離，並將這些距離與一個或多個的預定閾值相比較。預定閾值規定了對於離散的連續段要判認為屬於單獨分離的手寫輸入例如單獨分離的手寫字的最小距離量度。該基本上平行的距離就必須超過這種預定閾值。書寫軸是一道線，手寫輸入沿著它增加筆劃。書寫方向是每個後繼的手寫輸入增加的方向。在英文中，手寫輸入典型地沿水平書寫軸增加，每個後繼的字母數字輸入在書寫方向上為從左到右地沿水平軸跟隨在前一個輸入之後。在根據本發明教導的實施中，各種其它的書寫軸和書寫方向的替代方案也是可能的。
在一個優選實施例中，手寫軸是水平的，手寫輸入形成一序列的字。這個優選實施例中，基本上平行的距離沿水平方向計算，該輸出表明離散的連續段是否屬於單獨分離(separate)的字。在另一優選實施例中，手寫軸是水平的，手寫輸入形成一序列單獨分離的字符，它們可以是字母數字字符、在諸如漢語語言中的表意字符、或其它形式的字符、或書面通信的符號。在這個另一實施例中，該輸出表明離散的連續段是否屬於單獨分離的字符。在又一優選實施例中，手寫軸是垂直的，手寫輸入形成一序列單獨分離的字符，它們可以是字母數字字符、表意字符或者其它手寫文本。在該優選實施例中，書寫軸是垂直的，基本上平行的距離在垂直方向上對準，該輸出表明的連續段是否屬於單獨分離的字符。在一個優選實施例中，手寫軸是垂直的，手寫輸入形成一序列單獨分離的字、字母數字輸入、或其它的手寫輸入例如一個垂直的字或號碼錶。在該優選的實施例中，書寫軸是垂直的，基本上平行的距離在垂直方向上對準，該輸出表明離散的連續段屬於單獨分離的手寫輸入例如單獨分離的字。如上所述和將進一步討論的，本發明通過公開一些優選實施例表明，書寫軸可以存在任何角度，手寫輸入更通常地可以解釋為對應於含有一個或多個離散的連續段的離散元素(它們可包括但也不限於字符和文字)。將這裡所說明的方法應用到各個優選實施例的任一個實施例時，只需要改變所應用的座標系統就可使這種變動可按照本文的教導來做。
參看圖1，該圖示出本發明的一個優選方法。本發明可用於具有離散的連續段的一個或多個手寫輸入。本發明的優選實施例可用於具有離散的連續段的兩個或多個手寫輸入。為了便於說明起見，這裡只應用兩個離散的連續段S1和S2來說明。圖1示例的優選方法在步驟110由諸如PDA或其它裝置接收由兩個離散的連續段S1和S2組成的手寫輸入。具有接收手寫書入功能的其它裝置包括但不限於下列裝置計算機，數據機，尋呼機，電話機，數字或交互式或其它電視機，帶有數字圖形輸入卡的裝置，傳真裝置，掃描裝置，以及具有捕獲手寫輸入能力的任何裝置。在步驟120，最好一接收手寫輸入就辨認兩個離散的連續段S1和S2之間基本的垂直邊界b1和b2。判定基本上垂直於書寫軸的邊界b1和b2是通過在筆劃順序S1中找出沿書寫方向有最大位移點並在筆劃順序S2中找出沿書寫方向有最小位移點來實現的。基本上垂直的邊界b1是在筆劃順序S1中沿書寫方向具有最大位移的點的位移值。基本上垂直的邊界b2是在筆劃順序S2中沿書寫方向具有最小位移的點的位移值。依次計算S1中每一點在書寫方向上的位移，將該值與一個初始時為很大負值的存儲值相比較，便可判定沿書寫方向具有最大位移的基本上垂直的邊界b1。如果計算出的位移值大於存儲值，則該存儲值由這個計算出的位移值取代。在所有的點都被檢測之後，存儲值便具有在該筆劃順序中尋找到的最大位移值的值。一個相似的程序是以一個很大的正值開始的，通過計算S2中依序的每點在書寫方向上的位移並將該值與一個初始時為很大正值的存儲值相比較，尋找出沿書寫方向具有最小位移的S2中的點。如果計算出的位移值小於存儲值，則該存儲值由這個計算出的位移值取代。本優選的方法在步驟130，計算出一個第一基本平行的距離d＇；這裡，d＇＝b2－b1。
參看圖1，在步驟140將第一基本上平行的距離d＇與第一預定閾值t＇相比較。如果d＇大於或等於t＇，則在步驟145本優選方法斷定第一連續的離散段S1和第二連續的離散段S2屬於手寫輸入的不同段。例如，如果d＇大於t＇，則本優選方法斷定S1和S2是手寫輸入的不同字、字符或其它元素。預定閾值t＇的選擇按照具體的實施例作出。關於閾值t＇的選取將在別處詳述。
如果d＇的值小於閾值t＇，則發生進一步的處理。為了判定兩個離散的連續段S1和S2是否組成手寫輸入中個別的離散的連續段S1和S2，諸如單獨的字、字符或其它元素，需要計算一個第二基本上平行的距離d″。計算幾個基本上平行的距離並選取那些距離中最短的一個，便尋找出該第二基本上平行的距離d″。在優選實施例中，這是在步驟150首先計算由離散的連續段S1和S2一起對著垂直於書寫軸最大尺度來完成的。在步驟160再將此最大尺度劃分成為基本上平行於書寫軸的許多等高的節。然後，在步驟170為每節尋找出在S1與S2之間基本上平行的距離。在步驟180從許多節中選擇出在S1與S2之間基本上平行的最小或最短距離為d″。在圖1所示的優選方法中，一旦找出基本上水平的距離d″後，將距離d″與第一基本上水平的距離d＇相結合，有助於最終判定S1和S2是否是同一手寫輸入的一部分，還是手寫輸入的單獨分離的離散的連續段的一部分。在步驟190，計算d＇和d"的加權平均值，優選的加權平均值的公式是dw＝(q＇d＇＋q″d″)/(q＇＋q″)。憑對實際手寫數據的經驗測試業已發現採用d＇和d″的加權平均比之單獨的d＇或d″更精確。在一個優選實施例中，q＇＝q″，但適當地選取q＇與q″兩者不相等，能使結果進一步優化。此外，q＇和q″各自可等於零，但不能同時等於零。
在步驟195將加權平均值dw與第二閾值t″相比較。如果加權平均值dw小於閾值t″，則在步驟197本優選方法斷定S1和S2是手寫輸入同一段的一部分。如果加權平均值dw大於或等於閾值t″，則在步驟199本優選方法將斷定S1和S2是手寫輸入的不同的離散的連續段。
本優選方法選擇t＇和t″是具體實施例的細節。在一個實施例中，設定t＇值可在一大組數據中測量d＇值並能從偽選擇中選取最佳地區分開真實分割點的值來實現。在另一優選實施例中，t＇可以設定為一個常數，它對應於輸入裝置上諸輸入導向件(guide)之間距離的某個分數值。在又一優選實施例中，t＇值動態地變化可以作為在垂直於書寫軸的S1與S2上測量所得到尺度的一個分數值。在再一個實施例中，t＇值可以在該方法執行之前由用戶直接設定。在所示的優選實施例中，t＇設定為垂直於書寫軸的S1與S2上測量所得到尺度的1/3，它對英文、字母數字文本可給出良好的結果。許多其它的設定t＇的方式也可以考慮，它們對於不同的解決方案可能是最佳的。在不同的實施例中確定t″的各種方式與為確定t＇所敘述的那些方式相似。
圖2示出一個用於一種優選實施例的圖解表示。該實施例中，離散的連續段S1210和S2220對應於兩個英文單字，書寫軸230是水平的，書寫方向270為從左到右。在該優選實施例中，對於任一點沿書寫方向的位移簡單地是有關該點的X座標值，因而基本上垂直的邊界b1240是S1210中最右點的X座標值，基本上垂直的邊界b2250是S2220中最左點的X座標值。基本上平行的距離d＇260是b1與b2之間展開的距離。
如圖3所示的另一個圖解，離散的連續段S1310和S2320對應於兩個漢字，書寫軸330是垂直的，書寫方向370為從上到下。在該實施例中，對於任一點沿書寫方向370的位移簡單地是有關該點的Y座標值乘以-1(假定是標準座標系統，其中當座標值從下向上移動時Y值增加)，因而基本上垂直的邊界b1340是S1310中最下點的Y座標值乘-1，基本上垂直的邊界b2350是S2320中最上點的Y座標值乘-1。
在其它實施例中，b1和b2的值可以計算，使手寫輸入作簡單的幾何旋轉，將座標系統中兩個基本軸之一對準到書寫軸上，然後應用如上敘述的方法。這種運算簡單明了，人們結合這裡的講解是能理解的。另外，在其它實施例中，當書寫方向並不與座標系統中兩個基本軸之一對準時，可簡單地將離散的連續段幾何投影到書寫軸上，然後應用三角學計算投影點對座標系統原點的位移，便可計算出沿書寫方向上各筆劃點的位移。這是眾所周知的數學方法，這裡可以採用。
如前所述，如果d＇小於t＇，則計算過程繼續進行。在許多情況下，事實上屬於單獨的字或字符的段的位置可使d＇小，甚至是負的，但它仍可能判定S1和S2屬於不同的字或字符。圖4為一個實施例示出這種情況的一個例子，其中，S1410和S2420是兩個英文字。在這個例子中，d＇460實際為負值，b1440大於b2450。在這個例子中，書寫軸430是水平的，書寫方向470為從左到右。
在書寫軸為水平的一個實施例中，由S1和S2對著的、垂直於書寫軸的最大尺度可藉助於尋找出S1和S2中呈現出的最小和最大Y座標值來計算。為了尋找出最小Y座標值，將一個存儲值初始賦以一個很大的正值，然後依次檢測S1和S2中的每一個點，若其Y座標值小於該存儲值，則對存儲值指配以那個Y座標值。用類似的方法尋找出最大的Y座標值。將最大與最小的Y座標值相減，便能計算出垂直於書寫軸的尺度。S1和S2中的所有座標點均處於這個尺度之內。
在一個優選實施例中，只考慮S1和S2的點的一個子集，即只考慮所涉及的邊界附近處一個固定數目的點，可以更有效地完成這一計算過程。因為這些點子才最可能對所作的量度造成影響。
在書寫軸為垂直方向的另一個實施例中，由S1和S2對著的、垂直於書寫軸的最大尺度可藉助於尋找出S1和S2中呈現的最小和最大X座標值來計算。為了尋找出最小X座標值，將一個存儲值初始賦以一個很大的正值，然後依次檢測S1和S2中的每一個點，若其X座標值小於該存儲值，則對存儲值指配以那個X座標值。類同的方法用來尋找出最大的X座標值。將最大與最小的X座標值相減，便能計算出垂直於書寫軸的尺度。
在書寫軸既非水平方向也非垂直方向的另一個實施例中，可以旋轉圖像平面來使書寫軸對準座標系統中的X或Y軸；上面敘述了當書寫軸既非水平也非垂直時基本上平行的距離d＇的計算。
一旦尋找出垂直於書寫軸的尺度，一個優選實施例便將這個尺度劃分成為基本上平行於書寫軸的一些節(band)，以使每一節描述為通過S1和S2的一個狹窄部分。在每一節內，尋找出在書寫方向上具有最大位移的S1中的那個點，並尋找出在書寫方向上具有最小位移的S2中的那個點。對於S1來說，對每一節的存儲值初始化到一個很大的負值，便能有效地完成這一工作。依次地檢驗S1中的每一點。首先，檢驗其垂直於書寫軸的位移，看它處於哪個節中。由於諸多節在垂直於書寫軸方向上跨越S1和S2的整個尺度，所以它對於S1和S2中的任一點可保證尋找到這樣一個節。如果優選實施例中按上述在計算垂直尺度時只考慮S1和S2內的一個點子集，則垂直尺度可能不包含S1和S2中的全部點，因而必須檢驗每一點，以保證它位於一個節內。如果不是這樣，則對它不作進一步的考慮。當辨認出該節之後，將書寫方向內該點的位移與關於該節的存儲值相比較。如果位移值較大，便將它指配給存儲值。當S1中的全部點都這樣地檢驗過之後，每一節內的存儲值將包含這樣的點的最大位移，即S1中那個節內遇到有最大位移的點。如果S1中無點處在一個給定的節內，則存儲值將保留在初始的很大負值上。對於S2採用一個類似的程序利用在每節內初始化到很大正值的第二存儲值，以尋找出S2中每節內在書寫方向上具有最小位移的點的最小位移量。如果S2中一個給定節內無點存在，則對於該節的第二存儲值保留在其初始的很大正值上。
在這個操作結束時，每節具有兩個存儲值，對應於該節中在S1書寫方向上的最大位移值以及該節中在S2書寫方向上的最小位移值。如果任一個存儲值從其初始的很大負值或正值未改變，則該節的信息不用於任何進一步的計算中。否則，為每節計算從S2的點位移的存儲值中減去S1的點的位移的存儲值得到一個距離。這些距離的最小值是檢測依次對每節的距離來找到的，並將找到的最小值存儲起來。該最小距離基本上是水平的距離d″。如果d″小於零，則對它指定為零；當S1和S2相接觸或重疊時，會發生這種情況。
圖5示出一個實施例，其中，書寫軸是水平的，書寫方向為從左到右。在這個實施例中，節510的數目為10。尋找位於每節520內的S1的最右點，尋找位於那節530內的S2的最左點。對於S1來說，這是通過對每節將存儲值初始化到一個很大的負值完成的。依次檢驗S1中的每一點。首先，檢查它的Y座標，看看哪節位於其內。這些節跨越整個高度，即S1和S2的尺度540，所以可保證對S1和S2中的任一點尋找到一個節。一旦識別出該節，就將該點的X座標值與該節的存儲值相比較。如果X座標值較大，則將它指配給存儲值。當S1中的全部點這樣地檢驗過之後，每節內的存儲值將包含S1中那節所遇到的最右點的X座標值。如果在S1中無點處在一個給定的節內，則存儲值將保留在其初始的很大的負值上。對於S2使用一個類似的程序，在每節內應用一個初始化到很大正值的第二存儲值，以尋找出S2中每節內最左點的X座標值。
如前所述，對每節根據存儲的位置計算出d″值。從多節的量值中選擇出S1和S2之間基本上平行的最小或最短距離，作為d″值。然後，利用加權平均，將距離d"與d＇組合，與t″相比較。根據同t″的比較，本發明的方法可斷定離散的連續段S1和S2是否屬於同一手寫輸入或分離的手寫輸入。
本領域的技術人員顯然知道，這裡公開的發明可以用無數的方式作出改動，並採用許多不同於具體地提出和上面所說明的優選形式。因此，所附的權利要求書意在覆蓋對本發明的所有改動，它們都落在本發明及其等效項的精神實質和範疇之內。
權利要求
1.一種識別手寫輸入的方法，其特徵在於，包括以下步驟接收手寫字符輸入，該手寫字符輸入包含有至少第一和第二兩個離散的連續段；至少計算該第一和第二離散的連續段之間基本上平行的距離；應用該基本上平行的距離來判定該第一和第二離散的連續段是否屬於單獨分離的手寫字符輸入。
2.根據權利要求1的方法，其特徵在於，至少有下列步驟之一(a)計算步驟，用以計算基本上平行的至少一個距離包括計算第一和第二離散的連續段之間多個基本上平行的距離的步驟，其中，進一步選擇的計算多個基本上平行的距離的步驟中，還包括識別具有最小值的基本上平行的距離的步驟，其中，進一步選擇的、利用平行距離來判定第一和第二離散的連續段是否屬於分離的手寫輸入的步驟中包括利用具有最小值的基本上平行的距離來判定第一和第二離散的連續段是否屬於分離的手寫輸入的步驟。(b)還包括以下步驟識別第一和第二離散的連續段的每一個的基本上垂直的邊界；計算第一和第二離散的連續段的基本上垂直的邊界之間的距離；其中，進一步選擇的、利用平行距離來判定第一和第二離散的連續節段是否屬於分離的手寫輸入的步驟中包括對第一和第二離散的連續段還應用基本上垂直的邊界之間的距離來判定第一和第二離散的連續段是否屬於分離的手寫輸入的步驟。
3.一種識別手寫輸入的方法，其特徵在於，它包括以下步驟接收手寫輸入，該手寫輸入含有至少第一和第二兩個離散的連續段；識別第一和第二離散的連續段的每一個的基本上垂直的邊界；計算第一和第二離散的連續段的基本上垂直的邊界之間的第一距離；當該第一距離至少不超過第一預定閾值時，計算在第一和第二離散的連續段之間至少一個基本上平行的距離；應用該第一距離和該基本上平行的距離來判定第一和第二離散的連續段是否屬於分離的手寫輸入。
4.根據權利要求3的方法，其特徵在於，利用第一距離和基本上平行的距離來判定第一和第二離散的連續段是否屬於分離的手寫輸入的步驟中包括將加權的第一距離和加權的基本上平行的距離相加以得到一個總值、將該總值除以2以得到一個最終值、將該最終值與第二預定閾值相比較的步驟。
5.根據權利要求4的方法，其特徵在於，至少具有下列情況之一(a)第一和第二預定閾值相同；(b)第一和第二預定閾值不同；(c)對第一距離和基本上平行的距離兩者加上加權係數，以分別得到加權第一距離和加權基本上平行的距離，以使第一距離等於加權的第一距離，基本上平行的距離等於加權的基本上平行的距離。
6.根據權利要求3的方法，其特徵在於，在計算第一和第二離散的連續段在基本上垂直的邊界之間的第一距離的步驟中包括以下步驟當基本上平行的距離值為正時，應用這基本上平行的距離作為基本上平行的距離；當基本上平行的距離值為負時，便應用預定值作為基本上平行的距離；其中，進一步選擇的預定值為零。
7.根據權利要求3的方法，其特徵在於，在計算至少一個基本上平行的距離的步驟中包括計算在第一和第二離散的連續段之間多個基本上平行的距離的步驟。
8.根據權利要求7的方法，其特徵在於，計算多個基本上平行的距離的步驟進一步包括識別具有最小值的基本上平行的距離的步驟；其中進一步選擇的、應用第一距離和基本上平行的距離來判定第一和第二離散的連續段是否屬於分離的手寫輸入的步驟中包括利用具有最小值的基本上平行的距離和第一距離來判定第一和第二離散的連續段是否屬於分離的手寫輸入的步驟。
9.一種識別手寫輸入的方法，其特徵在於，它包括以下步驟接收手寫輸入，該手寫輸入含有至少第一和第二兩個離散的連續段，它們的配置基本上平行於一個書寫軸；識別第一和第二離散的連續段的每一個的垂直於書寫軸的一個邊界；計算第一和第二離散的連續段的邊界之間的第一距離；當該第一距離至少超過一個第一預定閾值時，可斷定第一和第二離散的連續段屬於分離的手寫輸入；當該第一距離並不是至少超過第一預定閾時，計算在第一和第二離散的連續段之間的至少一個基本上垂直的距離，該基本上垂直的距離是基本上垂直於書寫軸的；應用該第一距離和基本上平行的距離來判定第一和第二離散的連續段距離是否屬於分離的手寫輸入。
10.一種判定兩個離散的連續段屬於分離的手寫輸入的方法，其特徵在於，包括以下步驟接收手寫輸入，該手寫輸入含有至少第一和第二兩個離散的連續段；識別第一和第二離散的連續段的每一個的基本上垂直的一個邊界，這種基本上垂直的邊界是互相間最鄰近的邊界；計算第一和第二離散的連續段的基本上垂直的邊界之間的一個間隔距離；當該間隔距離至少超過一個第一預定閾值時，可斷定第一和第二離散的連續段屬於分離的手寫輸入；當該間隔距離並不是至少超過第一預定閾時，計算第一和第二離散的連續段的多個部分之間的多個基本上平行的間隔距離；應用該間隔距離和基本上平行的諸間隔距離中的最小一個距離來判定第一和第二離散的連續段是否屬於分離的手寫輸入。
全文摘要
本發明判定手寫輸入S
文檔編號G06K9/62GK1128073SQ95190365
公開日1996年7月31日 申請日期1995年5月8日 優先權日1994年5月10日
發明者約漢·L·C·西伯德 申請人:摩託羅拉公司