模板優化的字符識別方法和系統的製作方法
2023-11-12 04:07:42
專利名稱：模板優化的字符識別方法和系統的製作方法
技術領域：
本發明涉及一種字符識別方法和系統，尤其涉及一種模板優化的統計模式識別法和執行該方法的系統。
背景技術：
我國漢字識別技術的研究工作起始於八十年代初，其發展主要經歷了兩個階段。第一階段是整個八十年代，這一階段主要研究的是漢字識別的各種算法及識別方案探索。第二階段從九十年代開始，漢字OCR技術進入了一個重要、蓬勃發展的時期，將實驗室的研究成果推向市場，並出現了不少的漢字識別新算法和新技術。
目前，印刷體漢字識別技術已經很成熟，算法種類繁多，但基本都是包括輸入、預處理、識別、後處理等幾個環節。這裡，預處理包括二值化、去噪、糾斜、版面分析、切分、歸一化等過程，識別包括預分類、單字識別等過程。其中，識別部分是漢字識別系統的核心。
識別方法主要有統計模式識別和結構模式識別兩大類。結構模式識別是設法提取文字的結構特徵及其組字規律，用這些信息作為識別漢字的依據。統計模式識別發展較早，也比較成熟，要點是提取待識模式的一組統計特徵，然後按照一定的準則確定決策函數，並根據該決策函數進行分類判斷。其中，模板匹配法就是統計模式識別中的一種經典的方法。模板匹配法首先要提取標準漢字模式的特徵，將這些特徵集合存儲起來稱作字典，識別時將待識模式與字典中的標準漢字模式特徵一一匹配。如1985年4月1日提交的公開號為CN85100085的中國專利申請，公開了一種印刷漢字識別裝置，提取漢字筆劃與背景點存儲，以執行自上而下地進行模板匹配的方法。這種方法具有匹配簡單、抗幹擾能力強等特點，但也存在著一定的不足，如在支持漢字、字體較多的情況下，需要存儲與匹配的模式特徵的數據量就會大大地增加。
發明內容
針對現有技術中存在的缺陷，本發明的目的是提供一種利用公共模板進行字符識別的方法和系統。
就本發明一方面來說，所提出的字符識別方法包括步驟由訓練字符集中至少一個訓練字符構成一個字型，將所述字型逐次放到與其在不同組成部分上相似的字型所組成的不同待聚類集合中進行聚類並提取公共模板，將提取出來的所述字型的多級公共模板保存起來；參考提取出來的多級公共模板，提取所述字型的最後一級公共模板並保存起來；對於每個字型，將其內碼與指向其各級公共模板的指針對應存儲，以生成所述字型的索引表；對待識字符集進行識別時，將一個待識字符與找到的一個字型索引表所指向的各級公共模板進行逐級匹配並記錄匹配結果，以獲取候選字符。
上述方法中，在與查找到的字型索引表所指向的一級公共模板進行匹配之前，如果已經有匹配記錄，則直接應用所記錄的匹配結果來確定與所述公共模板是否匹配。
上述獲取候選字符的步驟進一步包括如果與各級公共模板都匹配，則將相應內碼所表示的文本字符作為所述待識字符的候選字符；如果與其中一級公共模板不匹配，則終止與該字型的匹配，與查找到的下一個字型索引表所指向的公共模板進行逐級匹配。
上述方法中，提取所述字型的多級公共模板並存儲起來進一步包括A、查找與一個字型在第一組成部分上相似的字型，將找到的字型與所述字型放到同一待聚類集合中進行聚類，以抽取相似部分作為集合中每個字型的第一級公共模板並保存起來；B、對於所述字型餘下的部分，查找對應部分相似的字型，將找到的字型與所述字型放到同一待聚類集合中進行聚類，以抽取相似部分作為集合中每個字型的下一級公共模板並保存起來；C、重複步驟B，提取第一字型的多級公共模板並保存起來。
上述方法中，第一級公共模板是偏旁公共模板，第二級公共模板是類公共模板。
上述方法中，第一級公共模板是類公共模板，第二級公共模板是偏旁公共模板。
上述方法中，步驟A進一步包括挑選待提取偏旁，查找與所述字型偏旁相同的字型，將找到的字型與所述字型放在同一待聚類集合中進行聚類，對類中所有字型點陣疊加以生成集合中每個字型的偏旁公共模板。
上述方法中，步驟A進一步包括在字體相似的字型點陣上框出一塊完全包含待提取偏旁的區域，作為點陣疊加的掩碼區域。
上述方法中，步驟B進一步包括用掩碼掩去第一字型中被提取偏旁公共模板的部分，剩下的部分與其它字型共同參與類公共模板的提取。
上述方法中，步驟B進一步包括基於初始化粗分類跳變規則來查找與第一字型對應部分相似的字型。
上述步驟B中，對待聚類集合進行收集的過程與對集合內字型進行聚類的過程交叉進行，在一個預定閾值下收集到一個待聚類集合中但未聚類成功的字型，參與下一次待聚類集合的收集。
上述方法中，在識別一個待識字符的過程中找到一個字型索引表，是按照所述待識字符的外形特徵查找正確分類而找到的。
上述方法中，訓練字符集中每個訓練字符都是一個字型。
上述方法中，每個字型的字體信息連同其內碼一起保存在字型索引表中。
上述方法中，字型是通過從訓練字符集中選擇內碼相同字體不同的單字符點陣進行聚類並對聚在一塊的字符進行點陣疊加而形成的。
上述方法中，形成一個字型的各個字符的字體信息之一連同所述字型的內碼一起保存在所述字型的索引表中。
上述方法中，進一步提取形成所述字型的各個字符的差異部分，作為所述字型的變體模板並保存起來，指向所述字型每個變體模板的指針與形成所述變體模板的各個字符的字體信息之一對應起來保存在所述字型的索引表中。
上述方法中，獲取候選字符的步驟進一步包括如果與各級模板都匹配，則將相應的內碼和字體信息共同表示的文本字符作為所述待識字符的候選字符；如果與其中一級模板不匹配，則終止與所述字型的匹配，與查找到的下一個字型索引表所指向的公共模板進行逐級匹配。
上述方法中，如果與各級模板都匹配則將相應的內碼和字體信息共同表示的文本字符作為所述待識字符的候選字符進一步包括如果找到的一個字型索引表中包括指向多個變體模板的指針，則所述待識字符在與表中指針指向的各級公共模板都匹配成功之後，只要與其中一個變體模板匹配成功，就認為所述字型匹配成功。
就本發明另一方面來說，所提出的字符識別系統包括模板生成部分和字符識別部分，字符識別部分包括識別單元；模板生成部分包括字型存儲單元、公共模板提取單元、模板輸出單元和字典。其中，公共模板提取單元包括多級公共模板提取模塊和最後一級公共模板提取模塊，字典包括字型索引表存儲模塊和模板存儲模塊。
多級公共模板提取模塊，用於針對字型存儲單元內所有字型中一個字型的不同組成部分，依次在由對應部分相似的字型組成的不同待聚類集合中進行聚類並提取出該字型的各級公共模板；最後一級公共模板提取模塊，用於參考提取出來的多級公共模板，提取所述字型的最後一級公共模板；模板輸出單元，用於接收公共模板提取單元提取出來的所述各級公共模板並保存到模板存儲模塊中，而且將指向模板存儲模塊中所述字型各級公共模板的指針保存到字型索引表存儲模塊內所述字型的索引表中；識別單元包括公共模板匹配模塊，用於將一個待識字符與找到的一個字型索引表中指針指向的公共模板進行逐級匹配。
上述識別單元還包括候選字符輸出模塊，用於所述待識字符在公共模板匹配模塊內與所述表中指針指向的各級模板都匹配成功的時候，將相應內碼所表示的文本字符作為候選字符輸出。
上述系統中，模板生成部分進一步包括字型生成單元，用於從訓練字符集中選擇內碼相同字體不同的單字符點陣進行聚類並對聚在一塊的字符進行點陣疊加，將疊加而成的字型保存到字型存儲單元中。
上述系統中，模板生成部分進一步包括變體模板提取單元，用於提取形成所述字型的各個字符的差異部分，作為所述字型的各個變體模板。
上述系統中，模板輸出單元還用於接收變體模板提取單元提取出來的變體模板並保存到字典的模板存儲模塊中，而且將指向模板存儲模塊中一個字型所有變體模板的指針保存到索引表存儲模塊內所述字型的索引表中。
上述系統中，識別單元進一步包括變體模板匹配模塊，用於待識字符由公共模板匹配單元與找到的字型索引表中指針指向的各級公共模板都匹配成功之後，與所述表中指針指向的變體模板進行匹配。
上述系統中，識別單元進一步包括分類器，用於按照所述待識字符的外形特徵查找正確分類，以便模板匹配模塊與找到的所述分類中的字型索引表所指向的模板進行逐級匹配。
本發明具有以下優勢根據字符點陣的特點提取不同字符間的公共部分，從而減小了字典的存儲量；無論匹配成功與否，公共模板上的點不必重複匹配，從而提高了字符識別系統的識別速度。因此，從這兩個角度出發優化了以模板點為特徵基礎的模式識別系統
通過閱讀下面結合附圖對本發明實施例進行的描述，本發明的這些和其他優勢將更容易理解。
圖1是根據本發明一個實施例的識別系統總體框圖；圖2是按照本發明一個實施例的模板生成階段的流程圖；圖3示出按照本發明一個實施例進行偏旁公共模板提取的流程圖；圖4示出按照本發明一個實施例在進行類公共模板提取的流程圖；圖5是以一個具體字符為例說明本實施例的字型指針效果圖；圖6是按照本發明一個實施例通過模板匹配對字符進行識別的流程圖；圖7進一步詳細描繪了圖6所示的實施例的字符識別流程。
具體實施例方式
在統計模式識別法中，漢字特徵是以n維向量X＝[x1，x2，…，xn]的形式表示的，字典中包含每類漢字的n維特徵向量。識別某個漢字就是用距離和/或相似度公式，判別該漢字的n維特徵向量和字典中哪類標準漢字的n維特徵向量最接近。距離度量通常有歐氏距離、城市塊距離和馬氏距離等，常用的距離和相似度公式分別如公式(1)和(2)所示D(X,G)=i=1n[X(i)-G(i)]2...(1)]]>R(X，G)＝(X，G)/(|X||G|)(2)式(1)中，D(X，G)表示向量X和G之間的歐氏距離。式(2)中，R(X，G)表示相似度，(X，G)為向量X和G的內積，|X|、|G|分別表示向量X和G的模。
本發明的字符識別方法是一種統計模式識別法，基於用點來存儲漢字特徵的識別系統。現有的漢字識別系統中，是將每個漢字的特徵點組合成一個點的序列存儲，漢字的特徵點比如從筆劃提取的普通點以及交點、拐點等各種特殊點，每個點的序列稱為一個模板。識別時，將待識別點陣與每一個模板進行匹配。因為提取漢字模板點時，一般都將漢字歸一化為48×48的點陣，在很多相似的字型上就會提取大量相同或相近的模板點。當系統包含大量的漢字時，很多點都是重複存儲的，識別時，這些相同的點又會被重複的匹配，因此在速度和存儲空間上造成了浪費。
本發明的字符識別方法包括模板生成階段和利用模板進行字符識別的階段。這樣一種方法優越性主要體現在兩方面，模板生成階段中各級模板的提取過程和識別階段中待識別字符點陣與模板逐級匹配的過程。各級模板的提取過程包括步驟提取偏旁公共模板，提取類公共模板，提取字型公共模板，還可以進一步包括提取變體模板的步驟。利用模板進行字符識別的階段通常包括三個過程，字符識別的預處理過程、字符識別過程和字符識別的後處理過程。
本發明所支持的字體、字數較多，拿這種大字符集直接進行聚類的話，計算起來將非常複雜而且聚類結果不利於供提取公共模板使用。因此為了提高聚類效率與聚類結果使用上的便利，下述實施例中所有公共模板的提取，都是將待提取字符按照某種規則分組收集，然後對各組內的字符進行聚類。
圖1是根據本發明一個實施例的識別系統總體框圖，點劃線以上為字符識別部分11，點劃線以下為模板生成部分12。
模板生成部分12包括圖像輸入單元101，它可以是掃描儀、傳真機或數位相機等圖像輸入裝置，還包括預處理單元102、字型生成單元121、字型存儲單元122、公共模板提取單元123、變體模板提取單元124、模板輸出單元125和字典126。其中，公共模板提取單元123包括多級公共模板提取模塊1231最後一級公共模板提取模塊1232，字典126包括字型索引表存儲模塊1261和模板存儲模塊1262。
圖像輸入單元101用於將輸入的列印文檔或手寫文檔轉換為數字圖像數據。預處理單元102用於在原始的圖像數據上進行去除噪聲、二值化等預處理，然後進行行列切分，逐個提取單個字符點陣，將所得到的單字符點陣歸一化成標準的48×48點陣。字型生成單元121用於從預處理後的訓練字符集中選擇內碼相同字體不同的單字符點陣進行聚類並對聚在一塊的字符進行點陣疊加，將疊加而成的字型保存到字型存儲單元122中。公共模板提取單元123中的多級公共模板提取模塊1231用於針對字型存儲單元122內所有字型中一個字型的不同組成部分，依次在由對應部分相似的字型組成的不同待聚類集合中進行聚類並提取出該字型的各級公共模板。最後一級公共模板提取模塊1232，用於參考提取出來的多級公共模板，提取該字型的最後一級公共模板。變體模板提取單元124用於提取形成該字型的各個字符的差異部分，作為該字型的各個變體模板。模板輸出單元125用於接收公共模板提取單元123和變體模板提取單元124為一個字型依次提取出來的各級公共模板和變體模板，並將收到的模板保存到模板存儲模塊1262中，而且將指向模板存儲模塊1262中該字型各級公共模板的指針和指向其中該字型所有變體模板的指針保存到字型索引表存儲模塊1261內該字型的索引表中。由此可見，字典126中的模板存儲模塊1262是用來保存公共模板提取單元123和變體模板提取單元124提取出來的各級公共模板和變體模板的資料庫。
應當指出，倘若某字型上述三級公共模板的和能夠使其和其他字型區分開，則對於這個字型來說不需要變體模板提取單元124。而當形成一個字型的內碼相同字體相似的字符組中存在若干個差異較大的字符時，公共模板提取單元123可以從這個字符組中提取出來的公共模板點過少。因此，提取出來的上述三級公共模板的組合不足以使該字型和其他字型區分，這時可以將比較相似的字符放在一起，以便差異較大的字符被分到不同組中，在公共模板點之外的差異部分上提取這些重新組合起來的字符的公共點，從公共點中選取一些點作為該字型的一個變體模板，從而增加了字型間的區分點。
優選的是，模板生成部分包括字型生成單元121。不過，該部分也可以不包括字型生成單元121，從圖像輸入單元101輸入的訓練字符集經過預處理後，直接發送給公共模板提取單元123進行處理。在這種情況下，是將不同字體相同內碼的字符作為不同字型來對待，以單個字符作為多級公共模板提取的基本單元。
在上述字型索引表中，字型的內碼連同該字型的字體信息一起與指向該字型各級公共模板的指針對應存儲。字型的字體信息有可能採用以下三種形式存儲在字型索引表中。一種形式，字型的字體是從形成該字型的各個字符所屬的不同字體中選出的一種有代表性的字體，一個字型內碼對應一種字體；另一種形式，字型的字體是從形成該字型一個變體模板的各個字符所屬的不同字體中選出的一種有代表性的字體，一個字型多個變體模板中的每一個對應一種字體；第三種形式，在模板生成部分不包括字型生成單元121的情況下，一個字型就對應該字型所屬的字體。當字型索引表中包括該字型的字體信息時，字符識別系統既能夠將待識字符轉換成正確的文本字符，又能夠使轉換後的文本字符具有正確或近似正確的字體。當然，字型索引表中也可以不包含該字型的字體信息，轉換後的文本字符統一採用一種指定的字體。可見，這樣的字符識別系統不能夠識別待識字符的字體。
字符識別部分11同樣也包括圖像輸入單元101和預處理單元102，此外還包括識別單元111、後處理單元112和文本數據輸出單元113。其中，識別單元111包括分類器1111、公共模板匹配模塊1112、變體模板匹配模塊1113和候選字符輸出模塊1114。
圖像輸入單元101和預處理單元102在字符識別部分11與在模板生成部分12中使用的差別在於處理對象不同。它們在字符識別部分11中處理的是待識別數據，而在模板生成部分12中處理的是訓練字符集。分類器1111用來按照所述待識字符的外形特徵查找正確分類，以便公共模板匹配模塊1112和變體模板匹配模塊1113將一個待識字符與找到的所述分類中所包含字型的索引表所指向的模板進行逐級匹配。候選字符輸出模塊1114用於所述待識字符在公共模板匹配模塊1112和變體模板匹配模塊1113內與該字型索引表中指針指向的各級模板都匹配成功的時候，將相應內碼所表示的文本字符作為候選字符輸出，同時輸出所生成的表示各個候選字符與對應的圖像數據匹配程度的數值。後處理單元112用於在獲得的候選字符的基礎上通過上下文關係來校正識別單元111的誤識別結果。文本數據輸出單元113用於輸出已被轉換成正確文本數據的文檔。
優選的是，字符識別部分包括分類器1111，分類的目的是在一個大的字符集中快速選出一個數目相對很小的候選字符子集，並保證這個子集中包含待識別字符所屬正確類別的概率儘可能大。不過，字符識別部分也可以不包括分類器1111，從圖像輸入單元101輸入的待識別字符集經過預處理後，直接傳輸給識別單元111中的模板匹配模塊1113，按照任意順序與每個字型索引表指向的字典126中的模板進行逐級匹配。顯然，在這種情況下匹配速度將比前端有分類器的模板匹配模塊的速度低得多。
倘若某個待識字符與一個只包括各級公共模板的字型匹配成功，那麼不必對該待識字符進行後續的變體模板的匹配，即對於這個待識字符來說不需要變體模板匹配模塊1113。
倘若待識字符與某個字型的某級公共模板進行匹配時，該公共模板在前期其他字型匹配時已經匹配過，那麼不必對該公共模板進行重複匹配，只要應用前面輸出的匹配距離即可。
下面參照圖2，描述圖1中模板生成部分12按照本發明一個實施例進行操作的過程。
首先在步驟201，輸入訓練樣本集。大量實際採集所得的多字體字符樣本通過圖像輸入單元101，例如掃描儀、傳真機或數位相機等，轉換成圖像數據。
在步驟202，對來自圖像輸入單元101的圖像數據進行預處理。利用現有技術對原始圖像數據進行去除噪聲、二值化等必要的預處理。對預處理後的圖像數據進行版面分析以及單字符切分。而後，將所得到的單字符點陣歸一化成標準的48×48點陣。
在步驟203，對每一個歸一化後的單字符點陣，標定其對應的文本字符的內碼與字體。挑出內碼相同字體不同的字符點陣組成待聚類集合，對每個待聚類集合中各個字符點陣進行聚類，將聚在一起的字符進行點陣疊加以形成一個字型。因此，形成一個字型的所有字符所屬的各種字體組成一個字體組，字體組中的字體都是很相似的。從字體組中選出的一種有代表性的字體作為該字型的字體。
在字體聚類後，以字型為基本單元分別在步驟204上提取偏旁公共模板、在步驟205上提取類公共模板、在步驟206上提取字型公共模板。
有的字型用上述三種模板的和不足以使其和其他字型區分，這時在步驟207上對該字型的公共模板進行區分性學習，從而生成變體模板。
偏旁公共模板的提取偏旁公共模板提取是在字體聚類後，以字型為基本單元進行操作的。同一個待聚類集合中的各個字型是按照相同偏旁與相似字體來收集的，按偏旁之間的相似程度在集合中進行聚類，對聚到同一類中的字型提取偏旁的公共部分，形成偏旁公共模板。圖3示出按照本發明一個實施例進行偏旁公共模板提取的流程圖。
在步驟301中挑選待提取偏旁。待提取偏旁要具備以下三個特徵第一，偏旁筆畫較少，在整個漢字中所佔的位置不要超過一半；第二，屬於該偏旁的字型的數量較多；第三，偏旁在整個字型中的位置，左右結構中要選取左偏旁，上下結構中選取上偏旁。
在步驟302，以每一個待提取偏旁為核心，將屬於同一偏旁的字型挑出形成文本文件，稱為偏旁序列文本文件。
在步驟303，將偏旁相同而且字體相似的所有字型收集起來，組成一個待聚類集合。重複這個過程，直到所有偏旁相同字體類似的字型都劃分到相應的待聚類集合中。
在步驟304，對於一個待聚類集合，根據其中一個字型所包含的待提取偏旁的形狀、位置、大小，在標準48×48點陣上框出一塊完全包含該偏旁的區域，從而得到這個待聚類集合的掩碼區域。重複這個過程，直到所有待聚類集合都被手工創建了掩碼區域。所有這樣的區域以字體和偏旁內碼為索引存儲在掩碼字典中。
因為偏旁相同字體相似的字型在偏旁部分十分相似，而且掩碼區域不需要嚴格的準確，所以用一個字型作代表做出掩碼即可。掩碼存儲在掩碼字典中，可見掩碼字典是一種用來存儲掩碼的資料庫。如果在點陣疊加時不提供掩碼區域，就會擴大差異區域，影響聚類效果。
在步驟305，對於每個待聚類集合，按偏旁的相似程度對集合中的各個字型進行聚類。將聚在一起的字型進行點陣疊加，在掩碼區域根據點陣提取筆劃及背景上的公共點，作為該待聚類集合中各個字型的偏旁公共模板。
在步驟306，將提取出來的偏旁公共模板保存在字典126所包括的模板存儲模塊1262中，為每個字型建立指向模板存儲模塊1262中相應偏旁公共模板的指針，並將字型的內碼和字體與指向該字型偏旁公共模板的指針對應起來保存到字典126所包括的字型索引表存儲模塊1261中，從而建立起該字型的索引表。
最後，在步驟307上用掩碼掩去有偏旁公共模板字型的偏旁部分的點陣，剩下的部分與其他字型共同參與類公共模板的提取。
類公共模板的提取類公共模板提取是在偏旁公共模板提取之後進行操作的。待聚類字型集合是通過識別系統中預分類的粗分類來界定的。這裡的粗分類是字符識別中任意一種預分類方法，例如按點陣幾何形狀計算的粗分類。在現有技術中幾乎所有的文字識別都要有粗分類這一步。因為本實施例的識別過程是以粗分類為單位進行跳變的，那麼相同公共模板的字型聚集在同一個粗分類或鄰近的粗分類之間，更能有效地提高識別速度。
類公共模板求取過程中的聚類是在屏蔽了點陣偏旁的情況下進行的，因此降低了偏旁的幹擾。收集到同一待聚類集合中的各個字型按照屏蔽偏旁後的點陣的相似度聚類。對於聚好的每一個類，類中所有字型點陣疊加，分別生成前景背景點陣，提取公共模板點，作為這一類字型中每個字型的類公共模板。若公共模板點過少，則將如上所述聚合而成的大類拆分為兩個小類，重新求取模板。
類公共模板提取與偏旁公共模板提取不同。在進行偏旁公共模板的提取時，分組方式是不重疊的，即一個字型屬於哪個待聚類集合是確定的，因此聚類只在一個集合中循環進行。而進行類公共模板的提取時，分組對於字型的歸屬界限不是絕對的，一個字型可能屬於某一個分組也可能屬於該分組的一個相鄰分組，因此有存在冗餘的必要，類公共模板提取過程中待聚類集合中字型的收集與聚類過程是交叉進行的。
圖4示出按照本發明一個實施例在進行類公共模板的提取時，收集待聚類字型與聚類穿插在一起的整個過程。
首先，在步驟401上初始化粗分類跳變規則。類公共模板提取中，待聚類字型的分組收集是通過識別系統中預分類的粗分類來界定的。因為識別的過程是以粗分類為單位進行跳變的，而粗分類通常不是一維編碼，所以需要首先初始化分類跳變規則。對於每一個粗分類而言，其他粗分類按照與該分類的距離，基於一定的規則排列成一維序列，比如按照與該粗分類的距離由小到大的順序排列。
在步驟402上創建空聚合鍊表，並設定一個初始的相似度閾值。在本實施例中，相似度是指字型歸一化點陣疊加起來之後相同點的數量，因此根據經驗將初始的相似度閾值設定為歸一化點陣總點數的0.6左右。
在步驟403上找到第一個粗分類。
在步驟404上以所找到的粗分類為中心收集字型。以該粗分類為基準四周跳變選擇滿足閾值的待聚類字型，如果該字型已經存在於某個聚類中，則跳過。
在判定步驟405上檢測收集到的字型數量是否達到一個預定數值以及分類跳變是否達到一定程度。如果收集到的字型數少於該數值並且分類跳變還未遠到一定程度，則在步驟406上根據步驟1中給定的編碼分類規則，跳變到下一個粗分類。接著流程返回到步驟404，以這個粗分類為中心重新收集字型。此流程在步驟404-405上循環，直到足夠多的字型(比如100個以上)參與聚類或分類跳變足夠遠時，流程就繼續進行到步驟407。
在步驟407，在這個字型數足夠多的待聚類集合內，按照字型與相應的粗分類之間的相似度進行聚類，並將合格分類放入聚合鍊表。
然後，在判定步驟408上檢測是否所有粗分類都已經在該閾值下收集過。若否，則在步驟209上找到一個未收集過的粗分類。接著流程回到步驟204，以這個粗分類為中心重新收集字型。若是，則流程繼續進行到步驟410。
在判定步驟410上檢測相似度閾值是否已經降低到一定程度，例如歸一化點陣總點數的0.2以下。如果降到預定數值以下，則流程繼續進行到步驟412。否則，在步驟411上降低閾值，而後重複步驟403-410。
在步驟412上輸出聚合鍊表，並創建類公共模板。
最後，在步驟413上將創建的類公共模板保存在字典126的模板存儲模塊1262中，為每個字型建立指向模板存儲模塊1262中相應類公共模板的指針，並將指向該字型類公共模板的指針保存到字典126的字型索引表存儲模塊1261中相應的字型索引表中。
對於聚好的每一個類，將類中所有字型點陣疊加，由先前的描述可知這時的點陣是屏蔽了偏旁的點陣，從而生成前景背景點陣，提取公共模板點作為該類字中每一個字型的類公共模板。若公共模板點過少，將聚好的大類拆分為兩個小類，重新求取模板。
應當注意的是，在統計模式識別中偏旁公共模板的提取和類公共模板的提取作為兩個過程，它們的先後次序並不是固定不變的。在生成公共模板的實際過程中，可以根據具體情況決定先進行哪一個過程。
字型公共模板的提取字型公共模板的提取是在類公共模板提取之後進行操作的。由於事先已經將內碼相同字體不同的單字符點陣聚類成字型，所以提取字型公共模板時字型已存在，不需要再次聚類。這一級模板的提取是參考偏旁和類公共模板的點，在字型前、背景樣張上分別提取筆劃點和背景點。也就是說，一個字型經過偏旁和類公共模板提取之後，在該字型提取了偏旁和類公共模板點的位置上不需再提取字型模板點。
倘若某字型上述三種模板的和不足以使其和其他字型區分，則對模板進行學習，通過參考該字型的各級公共模板來提取形成該字型的各個字符的差異部分，從而生成變體模板，以增加字型間的區分點。
各級公共模板的創建完成而且保存在模板存儲模塊1262中之後，每一個字型包括指向相應的偏旁、類和字型公共模板的指針，也可以進一步包括指向變體模板的指針，將該字型的內碼和字體與指向其各級模板的各個指針對應存儲，從而生成該字型的索引表。圖5是以一個具體字符為例說明根據本實施例所得到的字型索引表，圖中示出字體為方正姚體的「扯」字內碼與指向其各級公共模板的指針對應存儲在該字型的索引表中，指向「扯」字每一級公共模板的指針都指示了該級公共模板在模板存儲模塊1262中的存儲地址。通過該字型的偏旁公共模板指針，可以找到模板存儲模塊1262中地址A03處保存的「扯」字的偏旁公共模板(用●表示)。類似地，通過類公共模板指針，可以找到模板存儲模塊1262中地址B10處保存的「扯」字的類公共模板(用■表示)。仍然類似，通過字型公共模板指針，可以找到模板存儲模塊1262中地址C07處保存的「扯」字的字型公共模板(用□表示)。從圖5還可以看出，「扯」、「扮」、「拌」等多個字型公用一個偏旁公共模板，「扯」、「杜」、「址」等多個字型公用一個類公共模板。圖5所示的字型只包含一種字體，否則，字體相似的多個「扯」字將公用一個字型公共模板。如果這些不同字體之間差異較大的話，還將生成「扯」字的變體模板。
按照本實施例對待識字符進行識別時前期過程與傳統的字符識別方法相同，是根據待識點陣的外形特徵找到待識字符所在的粗、細分類。不同的是，傳統方法是將待識字符與這些小分類中各個字型的模板進行匹配，而本發明是與各個字型的公共模板進行逐級匹配。只有待識點陣與該字型所有各級模板的匹配距離之和較小時，才認為匹配成功。
圖6是按照本發明通過模板匹配對字符進行識別的流程圖。待識字符在與一個字型的某一級公共模板進行匹配時，需要記錄匹配結果並執行如圖6所示的操作。首先在步驟601，查看這一級公共模板是否在先前的字型匹配過程中被匹配過。若沒有匹配過，則在步驟602中與之匹配，並記錄匹配距離。若匹配過，則在步驟603中根據匹配記錄直接累加先前輸出的匹配距離，不再重複匹配。接著，在步驟604中查看累加後的匹配距離，並分兩種情況處理。若匹配距離較小，則在步驟605中在該距離基礎上繼續匹配該字型的其他模板。若距離足夠大，則認為該字型與待識點陣不匹配，不再匹配該字型的其他模板，結束整個流程。
由此可見，本實施例所述方法對於識別速度的提高，主要體現在識別流程中待識點陣與字型的各級模板的匹配過程中。一方面，只要某個待識字符與一個字型的一級公共模板匹配過一次，以後的若干個待識字符與該公共模板進行匹配時都可以應用第一次匹配的記錄，而不必重複匹配。另一方面，一個待識字符在與一個字型的各級模板進行逐級匹配時，只要其中一級模板匹配不成功，就不再與該字型的其他模板進行匹配。因此，從這兩方面來說都大量地節省了重複性匹配的過程。
圖7進一步詳細描繪了圖6所示的實施例的字符識別流程。字符識別的前期過程採用跟模板生成前期過程同樣的處理，首先將紙件文檔轉換成圖像數據，然後進行去噪聲、二值化等必要的預處理，對預處理後的數據作版面分析以及單字符切分從而獲得單字符點陣，將所得到的單字符點陣歸一化成標準的48×48點陣。
參考現有技術中粗細分類識別技術，計算歸一化後的字符點陣的粗細分類編碼，然後按照粗細分類跳變規則找到一個小分類，基於這個小分類所包含的各個字型的索引表進行模板匹配，具體步驟如下在步驟701，對於該分類中第一個字型索引表，將待識字符點陣與該索引表中指針指向的偏旁公共模板作匹配，並記錄匹配距離。在判定步驟702上檢測偏旁公共模板是否拒識。如果拒識，則終止與該偏旁公共模板的匹配並返回步驟701，查找下一個字型索引表以進行模板匹配。否則，流程繼續進行到步驟703。
在步驟703上，將待識字符點陣與類公共模板作匹配，記錄匹配距離並將該匹配距離同偏旁公共模板匹配距離相加。在判定步驟704上檢測類公共模板是否拒識，以及類公共模板匹配距離與偏旁公共模板匹配距離之和是否大於預定閾值。如果拒識或大於預定閾值，則終止與該類公共模板的匹配並返回步驟701，查找下一個字型索引表以進行模板匹配。否則，流程繼續進行到步驟705。
在步驟705，將待識字符點陣與字型公共模板作匹配，記錄匹配距離並將該匹配距離同偏旁和類公共模板匹配距離相加。在判定步驟706上檢測字型公共模板是否拒識，以及字型公共模板距離與偏旁和類公共模板距離之和是否大於預定閾值。如果拒識或大於預定閾值，則終止匹配並返回步驟701，查找下一個字型索引表以進行模板匹配。否則，流程繼續進行到步驟707。
在步驟707，將待識字符點陣與變體模板作匹配，記錄匹配距離並將該匹配距離同偏旁、類和字型公共模板匹配距離相加。在判定步驟708上檢測變體模板是否拒識，以及變體模板距離與偏旁、類和字型公共模板距離之和是否大於預定閾值。如果拒識或大於預定閾值，則終止匹配並返回步驟701，與下一個字型進行模板匹配。否則，指向上述各級模板的指針所對應的字型內碼和字體，結合起來表示的文本字符在步驟709上被加入到候選字符列表中。
在判定步驟710上檢測候選字符的匹配距離是否小於一個預定閾值。如果小於該閾值，則在判定步驟711上認為該候選字符是待識字符的正確字符。在這一步驟，終止匹配並返回步驟701，與下一個字型進行模板匹配。
否則，在步驟712上根據分類的遠近、字體、可信度等標準對加入的候選字符進行伸縮匹配。伸縮匹配就是按照一定的規則調整模板點的位置，減小由於文字點陣受到擠壓、膨脹、移位等變形帶來的影響。為了避免匹配距離的計算出現偏差造成誤識別，進行伸縮匹配時，變體模板與類公共模板、偏旁公共模板、字型公共模板要組合在一起計算。也就是說，將這四個模板結合成一個模板，按同一個規則伸縮匹配。
重複步驟701至710，直到該待識別字符與該類中所有字型都進行過模板匹配為止。
如果找到的一個字型索引表中包括指向多個變體模板的指針，則所述待識字符在與表中指針指向的各級公共模板都匹配成功之後，只要與其中一個變體模板匹配成功，就認為所述字型匹配成功並將相應的內碼和字體信息共同表示的文本字符作為候選字符。
前面的描述已經指出，本發明公共模板的提取順序可以改變，比如先提取類公共模板再提取偏旁公共模板。另外還應當指出，待識別字符與各級公共模板進行匹配的順序與這些公共模板被提取出來的順序無關，而且模板匹配的順序可以改變，比如先匹配類公共模板再匹配偏旁公共模板。就匹配順序來說，優選的是先與所包含字型的數量較多的公共模板進行匹配。
實驗結果表明，通過採用本發明，一個可以識別國標GBK2312全部漢字、56種字體的印刷漢字識別系統在不降低識別率的情況下，字典126中的模板存儲量只有原來的3/5。文件尺寸銳減的原因在於，不必為每個字型都存儲一個對應模板，只需要存儲多個字型共用的模板。這樣的話，就可以將字典126的模板存儲模塊1262中所存儲的一個偏旁公共模板、一個類公共模板和一個字型公共模板組合起來作為對應字型的模板，有時還要進一步組合一個變體模板。通過採用本發明，字符識別過程中模板匹配時間僅佔原匹配時間的1/2左右。
由此看來，本發明極大地降低了印刷體漢字識別系統信息的冗餘量，對提高識別速度及減小字典存儲量起到了顯著的優化作用。
顯然，本領域的技術人員可以對本發明進行各種改動和變型而不脫離本發明的精神和範圍。這樣，倘若本發明的這些修改和變型屬於本發明權利要求及其等同技術的範圍之內，則本發明也意圖包含這些改動和變型在內。
權利要求
1.一種模板優化的字符識別方法，該方法包括步驟由訓練字符集中至少一個訓練字符構成一個字型，將所述字型逐次放到與其在不同組成部分上相似的字型所組成的不同待聚類集合中進行聚類並提取公共模板，將提取出來的所述字型的多級公共模板保存起來；參考提取出來的多級公共模板，提取所述字型的最後一級公共模板並保存起來；對於每個字型，將其內碼與指向其各級公共模板的指針對應存儲，以生成所述字型的索引表；對待識字符集進行識別時，將一個待識字符與找到的一個字型索引表所指向的各級公共模板進行逐級匹配並記錄匹配結果，以獲取候選字符。
2.如權利要求1所述的方法，其特徵在於在與找到的字型索引表所指向的一級公共模板進行匹配之前，如果已經有匹配記錄，則直接應用所記錄的匹配結果來確定與所述公共模板是否匹配。
3.如權利要求1或2所述的方法，其特徵在於所述獲取候選字符的步驟進一步包括如果與各級公共模板都匹配，則將相應內碼所表示的文本字符作為所述待識字符的候選字符；如果與其中一級公共模板不匹配，則終止與該字型的匹配，與查找到的下一個字型索引表所指向的公共模板進行逐級匹配。
4.如權利要求1所述的方法，其特徵在於提取所述字型的多級公共模板並存儲起來進一步包括A、查找與一個字型在第一組成部分上相似的字型，將找到的字型與所述字型放到同一待聚類集合中進行聚類，以抽取相似部分作為集合中每個字型的第一級公共模板並保存起來；B、對於所述字型餘下的部分，查找對應部分相似的字型，將找到的字型與所述字型放到同一待聚類集合中進行聚類，以抽取相似部分作為集合中每個字型的下一級公共模板並保存起來；C、重複步驟B，提取第一字型的多級公共模板並保存起來。
5.如權利要求4所述的方法，其特徵在於第一級公共模板是偏旁公共模板，第二級公共模板是類公共模板。
6.如權利要求4所述的方法，其特徵在於第一級公共模板是類公共模板，第二級公共模板是偏旁公共模板。
7.如權利要求5所述的方法，其特徵在於步驟A進一步包括挑選待提取偏旁，查找與所述字型偏旁相同的字型，將找到的字型與所述字型放在同一待聚類集合中進行聚類，對類中所有字型點陣疊加以生成集合中每個字型的偏旁公共模板。
8.如權利要求7所述的方法，其特徵在於步驟A進一步包括在字體相似的字型點陣上框出一塊完全包含待提取偏旁的區域，作為點陣疊加的掩碼區域。
9.如權利要求8所述的方法，其特徵在於步驟B進一步包括用掩碼掩去第一字型中被提取偏旁公共模板的部分，剩下的部分與其它字型共同參與類公共模板的提取。
10.如權利要求9所述的方法，其特徵在於步驟B進一步包括基於初始化粗分類跳變規則來查找與第一字型對應部分相似的字型。
11.如權利要求10所述的方法，其特徵在於所述的步驟B中，對待聚類集合進行收集的過程與對集合內字型進行聚類的過程交叉進行，在一個預定閾值下收集到一個待聚類集合中但未聚類成功的字型，參與下一次待聚類集合的收集。
12.如權利要求1所述的方法，其特徵在於在識別一個待識字符的過程中找到一個字型索引表，是按照所述待識字符的外形特徵查找正確分類而找到的。
13.如權利要求1所述的方法，其特徵在於訓練字符集中每個訓練字符都是一個字型。
14.如權利要求13所述的方法，其特徵在於每個字型的字體信息連同其內碼一起保存在字型索引表中。
15.如權利要求1所述的方法，其特徵在於所述字型是通過從訓練字符集中選擇內碼相同字體不同的單字符點陣進行聚類並對聚在一塊的字符進行點陣疊加而形成的。
16.如權利要求15所述的方法，其特徵在於形成一個字型的各個字符的字體信息之一連同所述字型的內碼一起保存在所述字型的索引表中。
17.如權利要求16所述的方法，其特徵在於進一步提取形成所述字型的各個字符的差異部分，作為所述字型的變體模板並保存起來，指向所述字型每個變體模板的指針與形成所述變體模板的各個字符的字體信息之一對應起來保存在所述字型的索引表中。
18.如權利要求15或17所述的方法，其特徵在於所述獲取候選字符的步驟進一步包括如果與各級模板都匹配，則將相應的內碼和字體信息共同表示的文本字符作為所述待識字符的候選字符；如果與其中一級模板不匹配，則終止與所述字型的匹配，與查找到的下一個字型索引表所指向的公共模板進行逐級匹配。
19.如權利要求18所述的方法，其特徵在於如果與各級模板都匹配則將相應的內碼和字體信息共同表示的文本字符作為所述待識字符的候選字符進一步包括如果找到的一個字型索引表中包括指向多個變體模板的指針，則所述待識字符在與表中指針指向的各級公共模板都匹配成功之後，只要與其中一個變體模板匹配成功，就認為所述字型匹配成功。
20.一種模板優化的字符識別系統，包括模板生成部分和字符識別部分，字符識別部分包括識別單元；其特徵在於模板生成部分包括字型存儲單元、公共模板提取單元、模板輸出單元和字典，其中，公共模板提取單元包括多級公共模板提取模塊和最後一級公共模板提取模塊，字典包括字型索引表存儲模塊和模板存儲模塊，多級公共模板提取模塊，用於針對字型存儲單元內所有字型中一個字型的不同組成部分，依次在由對應部分相似的字型組成的不同待聚類集合中進行聚類並提取出該字型的各級公共模板；最後一級公共模板提取模塊，用於參考提取出來的多級公共模板，提取所述字型的最後一級公共模板；模板輸出單元，用於接收公共模板提取單元提取出來的所述各級公共模板並保存到模板存儲模塊中，而且將指向模板存儲模塊中所述字型各級公共模板的指針保存到字型索引表存儲模塊內所述字型的索引表中；識別單元包括公共模板匹配模塊，用於將一個待識字符與找到的一個字型索引表中指針指向的公共模板進行逐級匹配。
21.如權利要求20所述的系統，其特徵在於所述的識別單元還包括候選字符輸出模塊，用於所述待識字符在公共模板匹配模塊內與所述表中指針指向的各級模板都匹配成功的時候，將相應內碼所表示的文本字符作為候選字符輸出。
22.如權利要求20所述的系統，其特徵在於模板生成部分進一步包括字型生成單元，用於從訓練字符集中選擇內碼相同字體不同的單字符點陣進行聚類並對聚在一塊的字符進行點陣疊加，將疊加而成的字型保存到字型存儲單元中。
23.如權利要求22所述的系統，其特徵在於模板生成部分進一步包括變體模板提取單元，用於提取形成所述字型的各個字符的差異部分，作為所述字型的各個變體模板。
24.如權利要求23所述的系統，其特徵在於模板輸出單元還用於接收變體模板提取單元提取出來的變體模板並保存到字典的模板存儲模塊中，而且將指向模板存儲模塊中一個字型所有變體模板的指針保存到索引表存儲模塊內所述字型的索引表中。
25.如權利要求24所述的系統，其特徵在於識別單元進一步包括變體模板匹配模塊，用於待識字符由公共模板匹配單元與找到的字型索引表中指針指向的各級公共模板都匹配成功之後，與所述表中指針指向的變體模板進行匹配。
26.如權利要求20或25所述的系統，其特徵在於識別單元進一步包括分類器，用於按照所述待識字符的外形特徵查找正確分類，以便模板匹配模塊與找到的所述分類中的字型索引表所指向的模板進行逐級匹配。
全文摘要
一種模板優化的字符識別方法和系統。由訓練字符集中至少一個訓練字符構成一個字型，公共模板提取單元將所述字型逐次放到與其在不同組成部分上相似的字型所組成的不同待聚類集合中進行聚類並提取公共模板，參考提取出來的多級公共模板，提取所述字型的最後一級公共模板，將提取出來的該字型的各級公共模板保存到字典的模板存儲模塊中。模板輸出單元將每個字型的內碼與指向該字型各級公共模板的指針對應存儲，以生成該字型的索引表並保存到字典的字型索引表存儲模塊中。在識別單元對待識字符集進行識別時，其中的公共模板匹配模塊將一個待識字符與找到的一個字型索引表所指向的各級公共模板進行逐級匹配並記錄匹配結果，以獲取候選字符。
文檔編號G06K9/68GK1916940SQ20051009087
公開日2007年2月21日 申請日期2005年8月18日 優先權日2005年8月18日
發明者劉芝, 康凱, 徐劍波 申請人:北大方正集團有限公司, 北京北大方正技術研究院有限公司