基於遺傳算法和字符識別技術的碎片復原方法
2023-10-05 23:53:09 1
基於遺傳算法和字符識別技術的碎片復原方法
【專利摘要】本發明公開了一種基於遺傳算法和字符識別技術的碎片復原方法，包括下述步驟：S1、建立英文字符資料庫，通過字符提取技術，獲取各個字符的灰度矩陣；S2、對字符進行識別，判斷需要識別的字符並是否有被切割；S3、對碎片進行分行聚類，所述分行聚類的基礎是上述的字符識別技術和基準線距離信息，通過聚類向量、聚類中心和聚類距離，完成這一分行聚類過程；S4、經過分行聚類技術後，然後通過行內拼接技術，完成每一行的行內碎片拼接；S5、利用行間拼接技術進行碎片拼接。本發明可以廣泛應用在各類碎紙機產生的縱橫切碎片復原工作中，並在一定程度上同時保證了效率和準確度，為司法取證、歷史文獻修復以及軍事情報的獲取等領域提供支持。
【專利說明】基於遺傳算法和字符識別技術的碎片復原方法
【技術領域】
[0001] 本發明涉及碎片復原的研究領域，特別涉及一種基於遺傳算法和字符識別技術的 碎片復原方法。
【背景技術】
[0002] 破碎紙片的修復技術常運用在司法取證、歷史文獻修復以及軍事情報的獲取等領 域上，但面對數量巨大的碎片，人工修複方式效率顯得低下，需要開發復原效率高的自動拼 接技術，以提高需求方的工作效率，最大化地從碎紙片中獲取到準確度高的信息
[0003] 碎紙片目前被分為三個部分，分別是①具有不規則邊緣的手撕型碎片，②被碎紙 機切碎的條型碎片，③被碎紙機粉碎的橫縱切的碎片。對於第①種碎片，國內外學者都給出 不同的自動拼接方案。有些學者將不規則的碎片簡化成為多邊形，利用多邊形的特點來對 碎片進行拼接，但是這種方法僅僅能夠對規模數量小的碎片進行拼接。另外有學者根據碎 片邊緣的周長以及邊角的形狀來對碎片進行半自動的拼接。還有學者根據碎片文本文字的 形狀設計了 一種自動拼接算法。
[0004] 對於第②種條形的碎片，由於碎片中所包含的信息量大，所以能根據碎片之間的 相關性來將其拼接。有一篇文獻介紹的是利用英文單詞的平均長度以及碎片邊緣的二值化 矩陣，比對兩張碎片之間的文本特徵來對紙片進行拼接。有一些學者提出來一種文字識別 的算法，得出每個英文字母的特定的直方圖，對在兩碎片邊緣上被切的字符進行拼接，但是 缺點是，當原文本的文字行數下降的時候，也就是不能保證兩碎片間有足夠多的被切文字 時，該算法失效。
[0005] 對於第③種碎片，也就是縱橫切的碎片，拼接這些碎片可理解為解決一個NP問 題。Biesingeret等學者提出了一種改進了的遺傳算法去拼接這些碎片。Schauer等學者 利用成本函數公式去計算兩張碎片邊緣灰度值的相似度。還有學者提出用蟻群優化的方法 和最近鄰方法。
【發明內容】
[0006] 本發明的主要目的在於克服現有技術的缺點與不足，提供一種基於遺傳算法和字 符識別技術的碎片復原方法，解決針對碎紙機處理的文本文檔碎紙的拼接復原問題。
[0007] 為了達到上述目的，本發明採用以下技術方案：
[0008] 基於遺傳算法和字符識別技術的碎片復原方法，包括下述步驟：
[0009] S1、建立英文字符資料庫，通過字符提取技術，在字符圖像中提取不同字體、不同 字號的26個大小寫英文字母的灰度矩陣；在獲取各個字符的灰度矩陣後，將分別通過各個 字符的灰度矩陣統計字符的大小和字符基準線距離兩方面信息，並將其儲存在英文字符數 據庫；
[0010] S2、對字符進行識別，若需要識別的字符並沒有被切割，直接上述的字符提取技 術，將需要識別的字符提取出來；若需要識別的字符並切割，可先將其進行拼接後，再利用 上述的字符提取技術，將需要識別的字符提取出來；
[0011] S3、對碎片進行分行聚類，由於處理對象是縱橫切碎片，需要先對碎片進行分行， 將屬於同一橫行的碎片找出來；這一過程稱為分行聚類，每一行被稱為每一類；所述分行 聚類的基礎是上述的字符識別技術和基準線距離信息，通過聚類向量、聚類中心和聚類距 離，完成這一分行聚類過程；
[0012] S4、經過分行聚類技術後，所有碎片已經分到各自所屬行中；然後通過行內拼接技 術，完成每一行的行內碎片拼接；
[0013] S5、利用行間拼接技術進行碎片拼接，行間拼接技術主要的基礎是基準線位置；利 用相鄰兩個文本行的基準線間距一致原理完成這一操作。
[0014] 優選的，步驟S1中，建立英文資料庫的具體步驟為：
[0015] S1. 1、以字符提取技術得到的每個字符的邊緣為邊界，提取每個字符的灰度矩陣， 並以之為基礎，建立英文字符的資料庫，即針對字符圖像矩陣L= (、)#,，pXq指的是字 符圖像矩陣的規模，定義其中包含的一個字符的邊緣值如下：
[0016] 左邊緣（Leftmost side) :min {j 11。· = 1，i = 1，· · ·，p ; j = 1，· · ·，q};
[0017] 右邊緣（Rightmost side) :max {j 11。· = 1，i = 1，· · ·，p ; j = 1，· · ·，q};
[0018] 上邊緣（Top edge) :min{i 11。= 1, i = 1, · · · , p ; j = 1, · · · , q};
[0019] 下邊緣（Bottom edge) :max {i 11。· = 1，i = 1，· · ·，p ; j = 1，· · ·，q};
[0020] SI. 2、通過上述字符提取技術得到的每個字符的灰度矩陣是資料庫的儲存內容 之一，以便與接下來的字符識別工作；
[0021] S1. 3、字符的大小特徵信息包括字符的高度和寬度；這兩個信息都可以通過字符 的灰度矩陣得到；具體方法為：
[0022] 字符的高度定義為，字符灰度矩陣的行數，即上邊緣與下邊緣之間的距離；
[0023] 字符的寬度定義為，字符灰度矩陣的列數，即左邊緣與右邊緣之間的距離；
[0024] S1. 4、若將所有英文字符放在同一行中，並進行水平投影，便可得到一投影條形 圖；投影條形圖最頂端的水平線稱為上基準線，最底端的水平線稱為下基準線；對於不同 的字符，都存在字符和上下基準線之間的距離，即每個字符都和基準線有兩個距離，所述兩 個距離包括和上基準線的距離以及和下基準線的距離；將這兩個基準線距離儲存在資料庫 中。
[0025] 優選的，步驟S2中，字符識別技術的步驟為：
[0026] S2. 1、將需要識別的字符提取出來，並根據需要識別的字符的大小特徵信息在英 文字符資料庫中尋找是否存在與之相同高度和寬度的字符，如不存在，可直接判斷該字符 不能被識別，如存在，將需要識別的字符的灰度矩陣，和資料庫中與之有相同大小特徵的字 符的灰度矩陣進行對比匹配；
[0027] S2. 2、為了衡量標準化，設定一個閾值，若兩者灰度矩陣的相同元素個數高於閾 值，需要識別的字符將被認為和資料庫中的字符相匹配，並確定已被識別；若低於閾值，需 要識別的字符將被認為無法識別；
[0028] S2. 3、如果需要識別的字符被成功識別，其基準線的位置通過調用資料庫裡該字 符的基準線距離也被確定。
[0029] 優選的，步驟S3中，分行聚類的具體步驟為：
[0030] S3. 1、針對每張碎片的圖像矩陣，確定聚類向量；
[0031] S3. 2、在原始的完整文檔中，最左端的碎片包含著每一個文本行開始的信息，同時 最左端的碎片也存在一個共同特徵：碎片的左端存在較大面積的留白，利用這一特徵篩選 出文檔中的最左端碎片，由於每張最左端碎片開啟著縱橫切碎片的每個橫行，將這些最左 端碎片被稱為聚類中心；
[0032] S3. 3、其它碎片將根據聚類距離分配到離其距離最短的聚類中心所屬類；聚類距 離指的是其它碎片的聚類向量(^=(叫，&2， &3，&4)1和聚類中心的聚類向量(^=(<， a2'，a3'，a/ )τ之間的距離；明顯地，聚類距離是衡量兩個聚類向量之間相似程度的一個 指標；根據聚類向量的定義，如果兩張碎片最後一個可識別行的兩條基準線位置一致，即a 2 = a2' ,a3 = a3',表明這兩張碎片一定處於同一類；若1^_.cp表示第j張碎片與聚類中心 Cp的聚類向量之間的距離，那麼可定義如下：
[0033]
【權利要求】
1. 基於遺傳算法和字符識別技術的碎片復原方法，其特徵在於，包括下述步驟： 51、 建立英文字符資料庫，通過字符提取技術，在字符圖像中提取不同字體、不同字號 的26個大小寫英文字母的灰度矩陣；在獲取各個字符的灰度矩陣後，將分別通過各個字 符的灰度矩陣統計字符的大小和字符基準線距離兩方面信息，並將其儲存在英文字符數據 庫； 52、 對字符進行識別，若需要識別的字符並沒有被切割，直接上述的字符提取技術，將 需要識別的字符提取出來；若需要識別的字符並切割，可先將其進行拼接後，再利用上述的 字符提取技術，將需要識別的字符提取出來； 53、 對碎片進行分行聚類，由於處理對象是縱橫切碎片，需要先對碎片進行分行，將屬 於同一橫行的碎片找出來；這一過程稱為分行聚類，每一行被稱為每一類；所述分行聚類 的基礎是上述的字符識別技術和基準線距離信息，通過聚類向量、聚類中心和聚類距離，完 成這一分行聚類過程； 54、 經過分行聚類技術後，所有碎片已經分到各自所屬行中；然後通過行內拼接技術， 完成每一行的行內碎片拼接； 55、 利用行間拼接技術進行碎片拼接，行間拼接技術主要的基礎是基準線位置；利用相 鄰兩個文本行的基準線間距一致原理完成這一操作。
2. 根據權利要求1所述的基於遺傳算法和字符識別技術的碎片復原方法，其特徵在 於，步驟S1中，建立英文資料庫的具體步驟為： S1. 1、以字符提取技術得到的每個字符的邊緣為邊界，提取每個字符的灰度矩陣，並以 之為基礎，建立英文字符的資料庫，即針對字符圖像矩陣L= (、)_,，pXq指的是字符圖 像矩陣的規模，定義其中包含的一個字符的邊緣值如下： 左邊緣（Leftmost side) :min {j 11。· = 1，i = 1，…，p ; j = 1，...，q}； 右邊緣（Rightmost side) :max {j 11。· = 1，i = 1，...，p ; j = 1，...，q}; 上邊緣（Top edge) :min {i 11。. = 1，i = 1，...，p ; j = 1，...，q}; 下邊緣（Bottom edge) :max {i 11。· = 1，i = 1，...，p ; j = 1，...，q}； SI. 2、通過上述字符提取技術得到的每個字符的灰度矩陣是資料庫的儲存內容之一， 以便與接下來的字符識別工作； S1. 3、字符的大小特徵信息包括字符的高度和寬度；這兩個信息都可以通過字符的灰 度矩陣得到；具體方法為： 字符的高度定義為，字符灰度矩陣的行數，即上邊緣與下邊緣之間的距離； 字符的寬度定義為，字符灰度矩陣的列數，即左邊緣與右邊緣之間的距離； 51. 4、若將所有英文字符放在同一行中，並進行水平投影，便可得到一投影條形圖；投 影條形圖最頂端的水平線稱為上基準線，最底端的水平線稱為下基準線；對於不同的字符， 都存在字符和上下基準線之間的距離，即每個字符都和基準線有兩個距離，所述兩個距離 包括和上基準線的距離以及和下基準線的距離；將這兩個基準線距離儲存在資料庫中。
3. 根據權利要求1所述的基於遺傳算法和字符識別技術的碎片復原方法，其特徵在 於，步驟S2中，字符識別技術的步驟為： 52. 1、將需要識別的字符提取出來，並根據需要識別的字符的大小特徵信息在英文字 符資料庫中尋找是否存在與之相同高度和寬度的字符，如不存在，可直接判斷該字符不能 被識別，如存在，將需要識別的字符的灰度矩陣，和資料庫中與之有相同大小特徵的字符的 灰度矩陣進行對比匹配； S2. 2、為了衡量標準化，設定一個閾值，若兩者灰度矩陣的相同元素個數高於閾值，需 要識別的字符將被認為和資料庫中的字符相匹配，並確定已被識別；若低於閾值，需要識別 的字符將被認為無法識別； 52. 3、如果需要識別的字符被成功識別，其基準線的位置通過調用資料庫裡該字符的 基準線距離也被確定。
4. 根據權利要求1所述的基於遺傳算法和字符識別技術的碎片復原方法，其特徵在 於，步驟S3中，分行聚類的具體步驟為： 53. 1、針對每張碎片的圖像矩陣，確定聚類向量； S3. 2、在原始的完整文檔中，最左端的碎片包含著每一個文本行開始的信息，同時最左 端的碎片也存在一個共同特徵：碎片的左端存在較大面積的留白，利用這一特徵篩選出文 檔中的最左端碎片，由於每張最左端碎片開啟著縱橫切碎片的每個橫行，將這些最左端碎 片被稱為聚類中心； S3. 3、其它碎片將根據聚類距離分配到離其距離最短的聚類中心所屬類；聚類距 離指的是其它碎片的聚類向量CV= (&1，&2，&3，&4) 1和聚類中心的聚類向量(^'= (a/，a2'，a3'，a/ )τ之間的距離；明顯地，聚類距離是衡量兩個聚類向量之間相似程 度的一個指標；根據聚類向量的定義，如果兩張碎片最後一個可識別行的兩條基準線位置 一致，即a 2 = a2'，a3 = a3',表明這兩張碎片一定處於同一類；若4.(：,表示第j張碎片與 聚類中心Cp的聚類向量之間的距離，那麼可定義如下：
S3. 4、通過步驟S3. 3中的式子進行計算： S3. 41計算其它碎片和各聚類中心的距離〃; S3. 42 :如果巧/:.中的兩個分量均不大於閾值，表明第j張碎片與聚類中心Cp屬於同一 類； S3. 43 :利用上述步驟將所有碎片歸入m類中，並統計每一類的碎片數目。
5. 根據權利要求4所述的基於遺傳算法和字符識別技術的碎片復原方法，其特徵在 於，步驟S3. 1中，確定聚類向量的步驟為： S3. 1. 1 :如果圖像矩陣的第一行元素全為0,表明該碎片的最上方位置不存在不可識 別行，令叫=0 ;否則，執行下一步； S3. 1. 2 :如果碎片的第一行為可識別行，表明碎片的最上方位置不存在不可識別行，令 ai = 0 ;否則，令ai = lp h表示第一不可識別行最下方水平位置； S3. 1. 3 :如果圖像矩陣的最後一行元素全為0,表明碎片的最下方位置不存在不可識 別行，令a4 = 0 ;否則，執行下一步； S3. 1. 4 :如果碎片的最後一行為可識別行，令a4 = 0 ;否則，令a4 = 12, 12是最後一不 可識別行最上方水平位置； S3. 1. 5 :如果碎片中存在至少一個可識別行，選取最下方的一個可識別行，並根據其中 的可識別字符確定該可識別行的基準線位置，其中，la表示上基準線位置，lb表示下基準線 位置；否則，令a 2 = 0, a3 = 0 ; S3. L 6 :得到碎片的聚類向量CV = (a^ a2, a3, a4)T。
6. 根據權利要求4所述的基於遺傳算法和字符識別技術的碎片復原方法，其特徵在 於，步驟S3. 2中，在碎片中獲取聚類中心的具體步驟為： S3. 2. 1 :初始化計數變量t = 1 ; S3. 2. 2 :初始化聚類中心的數量p = 0和計數變量j = 1 ; S3. 2. 3 :如果第j張碎片的圖像矩陣的第1到第t列元素全為0,令p = p+1 ; S3. 2. 4 :如果 j〈mXn，j = j+Ι，返回步驟 S3. 2. 3 ; 53. 2. 5 :如果p>m, t = t+1，返回步驟S3. 2. 2 ;如果p = m，表示m張碎片被獲取，或稱 為m個聚類中心，m張碎片的圖像矩陣的第1到第t列元素全為0,同時，將m個聚類中心記
7. 根據權利要求1所述的基於遺傳算法和字符識別技術的碎片復原方法，其特徵在 於，步驟S4中，行內拼接技術的具體步驟為： 54. 1、構建行內碎片之間的距離矩陣； S4. 2、第一階段的行內拼接，利用字符識別技術，以邊緣字符為媒介，完成相鄰碎片的 拼接； S4. 2、第二階段的行內拼接，通過第一階段行內拼接後，同一行的碎片被記做認，兄… ，，利用上面構建距離矩陣的方法，計算D (Jk，1)，k，1 = 1，2,…，r，並以此構造一個新的 距離矩陣。
8. 根據權利要求7所述的基於遺傳算法和字符識別技術的碎片復原方法，其特徵在 於，步驟S4. 1的具體為： 對於每張碎片而言，都存在兩個垂直邊緣；而行內拼接技術主要是依靠這兩個邊緣 提供的信息量完成；假設現通過上述分行聚類技術後，得到處於同一橫行的碎片集合為 Up j2，…，jj，於是一個ηΧη的距離矩陣可以用如下方法定義： 令第jp張碎片圖像矩陣的右邊緣為七,第j,張碎片圖像矩陣的左邊緣 為
；那麼，可用歐氏距離定義第jp張碎片和第j,張 碎片的距離為：
其中
是第jp張碎片和第j,張碎片拼合後邊緣字符； 能否被識別的示性變量，定義如下：
9. 根據權利要求7所述的基於遺傳算法和字符識別技術的碎片復原方法，其特徵在 於，步驟S4. 2具體為： 假設現通過上述分行聚類技術後，得到處於同一橫行的碎片集合為Ui，j2，…，jn}，並 得到碎片之間的距離矩陣，於是第一階段的行內拼接步驟如下： a、 對於任一給定的 k(k = 1，2, 3,…，η)，如果 D(jk, iD-Inf，1 = 1，2, 3,…，η,碎片 jk 被記作（jk); b、 如果下面等式存在：
,kt 兩兩互異，那麼碎片 ;被記作(i*: Λ :，人）； 最後碎片
被寫作
^其 中
進一步，
丨可以記作·
，其 中，J
通過第一階段的行內拼接，{ji, j2,…，jj用{Ji, J2,…，Jr}表不。
10. 根據權利要求1所述的基於遺傳算法和字符識別技術的碎片復原方法，其特徵在 於，步驟S5中，假定第p (P = 1，2,…，m)行的上下基準線位置分別為/=.和? ?那麼基準線 間距可以定義為和之間的距離；對於一個文本文檔而言，基準線間距都是相同的。
【文檔編號】G06F17/30GK104143095SQ201410338609
【公開日】2014年11月12日 申請日期:2014年7月16日 優先權日:2014年7月16日
【發明者】樊鎖海, 許荷東, 莊子煒, 鄭晶 申請人:暨南大學