基于圖表示和匹配的表單定位與提取

譚婷，呂淑靜，呂岳,

（1. 華東師范大學 上海多維度信息處理重點實驗室，上海 200062; 2. 中國郵政集團公司上海研究院 圖像分析與智能系統(tǒng)聯(lián)合實驗室，上海 200062）

表單作為重要的信息載體在實際生活和工作中有著廣泛的運用，表單中某些特定字段、圖案、符號等都有可能包含用戶感興趣的重要信息，如訂貨單中的訂單號、發(fā)票的具體項目及金額、快遞運單中的收貨地址和手機號碼等。人工錄入的方式采集數(shù)據(jù)，費時費力，而且容易出錯，因此利用計算機對表單圖像進行自動化信息提取有著強烈的應用需求，可以大幅度降低工作量，提升工作效率。

表單自動化處理的主要過程包括表單圖像采集、表單定位、信息區(qū)域提取、識別等[1]。其中表單定位和提取是表單識別前重要的預處理過程，預先獲取表單關鍵信息區(qū)域有利于更方便、準確地識別表單填寫的內容信息。本文方法主要工作是對物流快遞表單中與用戶信息相關的文本區(qū)域進行定位和提取，如快遞表單上收/寄件人姓名、電話號碼、地址等信息。該處理過程得到文本圖像塊可用于后續(xù)識別工作的輸入數(shù)據(jù)，建立字符圖像數(shù)據(jù)庫，圖像特征學習的訓練樣本，具有廣闊的應用前景。

表單提取過程中常見的方法是檢測表單中的直線，將其作為表單提取的參考位置[2-3]。基于直線的檢測法所處理的對象更傾向于類似于表格類結構化的表單，但對缺乏框線和非固定形式的非結構化表單的處理存在明顯的不足。

另一類表單定位與提取的方法是采用對表單的布局或表單元素進行描述的方法，如建立搜索分類樹[4]或設定提取信息的關聯(lián)指令[5]。這種對表單的布局或表單元素進行描述的方法缺乏靈活性。

表單圖像具有特定的布局方式，因此采用參考模板來提取表單也是一種重要的研究方法，如使用空白表單模板與待匹配表單基準點對齊[6-7]或使用傅里葉-梅林變換重定向表單[8]的方向。Cesarini[9]提出通過屬性圖結點的具體數(shù)值和圖的模型特征實現(xiàn)剛性配準，建立待處理圖和參考圖的對應。

以往的模板匹配方法依賴于對基準點的嚴格要求和預先約定，而基于非層次有向關系屬性圖[9]方法在尋找對應區(qū)域位置時，難以避免預先識別關鍵字。本文將模板匹配和圖匹配的方法相結合，提出一種基于圖表示和匹配的表單定位與提取方法。

圖匹配方法在計算機視覺領域有著廣泛的應用，如特征點對應[10-11]、形狀匹配[12]、目標檢測和識別[13-15]、視頻分析[16]，圖像的視覺特征在圖匹配過程中考慮兩圖之間最小結構失真以實現(xiàn)對應。

本文方法在處理多個類別的表單圖像時，需要預先選取對應類別表單圖像中已有的圖案區(qū)域設計匹配待處理表單的參考表單模板圖，該過程避免了對字符的識別，簡化了分類提取的過程。另外，圖匹配方法適用于混雜場景下目標檢測和異常點判別，結合這一優(yōu)勢，在定位表單時采用圖匹配的方法對定位的正確性進行驗證。

1 表單圖表示

1.1 參考表單的圖表示

1.1.1 參考表單關鍵區(qū)域的選取

本文在建立參考表單圖表示時，由用戶手動選擇能反映表單特征的關鍵區(qū)域，比如具有可區(qū)分特征的表單公司標志、特定圖案、字符塊等。由于表單圖像上字符較多，背景較為復雜，后續(xù)圖匹配過程需要足夠多的關鍵區(qū)域實現(xiàn)配準，同時匹配計算量適度，建議選取5～8個圖案完整、清晰、大小適中的圖像塊作為關鍵區(qū)域，圖1給出一個從郵政快遞包裹面單上選取關鍵區(qū)域的例子。

圖1 參考表單關鍵區(qū)域選取樣例Fig.1 An example for key area selection of reference form

1.1.2 關鍵區(qū)域的圖表示

以關鍵區(qū)域為圖結點，建立如圖2(a)所示參考表單的全連接無向圖表示。將該無向圖定義為q=(V,E;o,φ)，其中V為圖結點，對應表單的關鍵區(qū)域。E為圖的邊，對應結點間的相互連接關系。ω表示每個結點v的結點屬性，φ表示每個結點v在圖q中的結構屬性。圖2(b)為圖2(a)中結點v7的結構屬性表示。

圖2 參考表單圖樣例Fig.2 An example for graph of reference form

1)結點屬性 o。SIFT對圖像局部特征的描述具有良好旋轉和尺度不變性，對光照有較強的魯棒性。采用SIFT來描述圖的結點屬性表示為

式中：fij為128維的SIFT特征向量，表示vi中第j個特征點；M為正整數(shù)，表示結點vi的特征維度。

2)結構屬性 φ 。 φ表示結點vi結構屬性，它包括兩個子屬性：結點權重屬性 ω 和夾角屬性 θ，結點vi的結構屬性表示為 φi={ωi,θi}。

權重屬性 ωi。該屬性表示以結點vi為固定端點，vi與其所有鄰接點vj連接邊eij的長度的向量集合。該屬性表示如下：

如v7射線簇屬性為{e71, e72, e73, e74, e75, e76,e78}。

夾 角 屬 性 θi。 α(eij,eik)表 示 圖 中 以 結 點vi為頂點，eij和eik分別為與鄰接點vj和vk連接邊緣所組成的夾角，結點vi所具有的夾角屬性表示為以vi為頂點的夾角向量集合 θi，表示如下：

根據(jù)上述描述， 即為參考表單關鍵區(qū)域的圖表示。

q=(V,E;o,φ)

1.2 待處理表單的圖表示

1.2.1 待處理表單候選關鍵區(qū)域的選取

本文采用選擇性搜索方法[17]將待處理表單分割得到許多圖像小塊，這些圖像塊中包含與參考表單關鍵區(qū)域對應的區(qū)域或部分的區(qū)域。如圖3所示，該算法使得灰度相似且位置相近的像素合并，然后根據(jù)圖像塊的大小、灰度梯度實現(xiàn)圖像塊粗略過濾，選擇圖案、字符相對較集中的區(qū)域作為待處理表單圖像的候選關鍵區(qū)域。

圖3 待處理表單候選關鍵區(qū)域選取樣例Fig.3 An example for candidate key area selection of test form

1.2.2 候選結點篩選

為提高匹配參考表單圖的效率，比較候選關鍵區(qū)域與關鍵區(qū)域的結點屬性ω相似度，篩選出相似度最高的前3個圖像塊作為圖匹配的候選結點，建立關鍵區(qū)域與候選關鍵區(qū)域的對應關系，去除大量相似度過小的候選關鍵區(qū)域，降低匹配復雜度。

1.2.3 候選關鍵區(qū)域圖表示

對候選結點參照參考表單圖建立的過程，建立如圖4(b)所示待處理表單的全連接圖G。與參考表單圖全連接不同的是，對應同一關鍵區(qū)域的3個候選關鍵區(qū)域間不連接。隨后，對圖G中標簽互異的候選子圖g進行結點和結構屬性描述。

圖4 候選同構圖Fig.4 Candidate isomorphic graph

2 表單圖匹配

由于圖像分割策略局限性，分割的候選關鍵區(qū)域可能出現(xiàn)欠分割和過分割的問題。另外，對應于關鍵區(qū)域的位置出現(xiàn)局部遮擋，容易得到錯誤的候選關鍵區(qū)域。為此，通過對參考表單與待處理表單進行圖匹配，驗證和確認關鍵區(qū)域是否對應準確。

2.1 候選同構圖

給定 G=(V，E)和 G1=(V1，E1)是兩個圖，假設存在雙射 ? :V→V1使得對所有x,y∈V均有xy∈E等價于 ? (x)?(y)∈ E1，則稱G和G1是同構的。假設參考表單圖表示為 q =(Vq,Eq;oq,φq)，待處理表單圖表示為 G =(VG,EG;oG,φG)，圖g與圖q中對應的候選結點賦予與q中相同的標簽，如圖4(a)中的{a}對應于圖4(b)中的{a1,a2,a3}。圖G中結點標簽互異的圖g與圖q，恰好滿足 ?這一映射關系，故稱圖g為圖q的同構圖。因此，圖像匹配過程為從圖G中尋找一個與圖q最相似的同構圖g，或尋找與子圖qs最相似的同構子圖gs，是一個圖匹配的問題。通過度量同構圖g與圖q的相似性，找到相似差異最小的同構圖gm或同構子圖gsm，作為與圖q最佳匹配圖。如圖4所示，按照同構映射 ? 的定義，在圖4(b)所示圖G中，圖4(a)所示圖q：{a,b,c,d}對應的候選同構圖有 g1：{a1,b1,c1,d1}, g2：{a1, b1, a, d2},···,g64： {a3,b3,c3,d3}。圖匹配目的即為在圖4(b)所示的圖G中找到最佳匹配的候選同構圖gm：{a2,b1,c2,d2}。 ?表示篩選與對應關鍵區(qū)域最相似的前3個候選關鍵區(qū)域，這些候選區(qū)域中，可能包含了紋理相似，但在表單上位置不同的圖案區(qū)域，從而導致候選圖中對應的結點出現(xiàn)較大幅度的位置偏差，如圖4(b)中b2和d2。因此，需要進一步度量圖結構的相似度，尋找圖G中與參考表單圖q最相似的同構圖，如gm，或去除誤匹配結點的最相似的同構子圖，如果d2為誤匹配結點，則目標匹配為同構子圖 gsm：{a2,b1,c2}。

2.2 距離度量

將表單進行圖表示和屬性定義，然后通過度量G中同構圖g和q間的屬性差異，衡量兩圖間的距離，距離越小則表示子圖g和q的結構越相似，根據(jù)屬性的差異，確定最相似的同構圖gm或同構子圖gsm?？梢詮囊韵聨讉€方面度量圖的差異。

1)結點相似度

對g和q中結點 Vg和 V 的SIFT特征點采取最近鄰匹配進而得到匹配特征點對的F-Score值F1(oi)，則圖結點間的相似距離定義為

2)結構相似度

向量余弦相似度來表示：

式中 dθ(i)∈ [0,1]。

式中：EX、DX分別為變量X的均值和方差。則該圖的權重相似距離為

式中 dω(i)∈ [0,1]。

同構圖g和圖q對應結點的相似度定義為

在進行參考表單q與g的圖匹配時，考慮到g與q對應結點缺失或選擇錯誤的情況，若g與q對應結點紋理極為相似，但實際位置并不匹配，較高的紋理相似度會對圖的相似度有一定程度的干擾；同樣的，當夾角、射線簇邊緣相似度過高，同樣會影響該結點的整體相似度的評判。故需對當前匹配的g中的結點剪枝，對結點vi中 do(i)、dθ(i)、 dω(i)設置一定的閾值，不符合條件的vi設值為離群點，同時將離群點納入相似度量的整體評價中，即對g和q的子圖進行匹配，尋找一個與q最相似的同構子圖gsm。該離群點相似度度量如下：

離群點相似度，用經剪枝過后的離群點數(shù)量(outlier Number，ON)表示：

式中： dNum∈[0,1]， Nq表 示圖q中結點 V 的數(shù)量，圖g和圖q的相似距離表示為

式中：ci∈{0，1}，0表示離群點，1表示符合閾值要求的結點， d (q,g)值越小則兩圖的相似度越大；故在G中，將與q相似距離最小的gm或gsm作為G與q的最終匹配結果：

通過圖相似性度量，得到與參考表單圖最佳匹配的同構圖gm或同構子圖gsm，圖5給出了一個待處理熱敏表單最佳匹配結果。

圖5 熱敏表單圖匹配結果Fig.5 Graph matching result for free form

2.3 待處理表單定位

如圖5所示，參考表單與待處理表單的關鍵區(qū)域僅實現(xiàn)了部分對應，且匹配出的圖像塊不完整或輪廓不吻合，這是由于圖像分割算法對復雜的字符圖案分割不準確所致，這將直接導致表單提取的位置不準確。因此，本文在提取后處理過程中對匹配關鍵區(qū)域的位置進行修正，即迭代建立參考表單與待處理表單的位置映射函數(shù)，以此提高表單提取的準確性。通過映射函數(shù)，實現(xiàn)待處理表單上任意感興趣區(qū)域的定位，從而完成表單信息的提取。

3 實驗及分析

3.1 數(shù)據(jù)集

對快遞包裹分揀機中采集的兩類快遞表單圖像，建立多聯(lián)表單(table like form，TF)和熱敏表單(free form，F(xiàn)F)兩類實驗數(shù)據(jù)集，TF和FF共計1 477幅灰度快遞表單圖像。這些表單圖像的分辨率偏轉角度不同，且未進行歸一化處理。其中TF為表格類圖像，該類表單由制表單位統(tǒng)一印刷，表單內容依據(jù)表格線布局，包括中國郵政國內快遞小包郵件詳情單(C-XB)和EMS國內標準快遞(EMS-MULT)，這些圖像的字符和圖案較為清晰，其中有部分圖像具有褶皺、模糊、扭曲或缺損、遮擋或字跡重疊等問題。FF數(shù)據(jù)集為非表格類表單圖像，該類表單常見于物流集散點、商家網(wǎng)點自行打印，包括EMS標準快遞(EMS-FLAT)和韻達快遞表單(YUNDA)，除存在上述TF數(shù)據(jù)集中特點以外，該數(shù)據(jù)集中表單印刷墨跡清晰度不一。另外，為驗證算法在光照、尺度、旋轉變換等情況下具有良好的魯棒性，本實驗將TF、FF數(shù)據(jù)集記為o-i，對o-i進行了旋轉、縮放、亮度調節(jié)等擴展數(shù)據(jù)集。旋轉擴展是對o-i分別旋轉45°、90°、135°、180°，新增 r-1、r-2、r-3、r-4 擴展數(shù)據(jù)集。縮放擴展是對o-i縮擴放至原表單圖像的75%、50%、125%、150%，新增s-1、s-2、e-1、e-2擴展數(shù)據(jù)集。亮度調節(jié)擴展是對o-i的亮度提高至原來的125%、150%和降低至原來的75%、50%，新增b-1、b-2、d-1、d-2擴展數(shù)據(jù)集。經過數(shù)據(jù)集擴充，本文實驗的表單圖像共計19 201幅。

3.2 評價標準

本文通過表單圖匹配的置信度和表單相關信息的提取結果準確率來分析算法的性能。

首先，采用表單圖匹配的置信度來衡量根據(jù)圖匹配所建立的參考表單圖像與待處理圖像的映射是否可靠，該置信度由重疊率(average overlap，AO)和平均準確率 (mean average precision，MAP)來評定。如果映射的置信度高，那么表單信息提取的準確性也會提高。重疊率定義為映射過程中關鍵區(qū)域重合度比例的均值：

式中：nl為關鍵區(qū)域的數(shù)量，為參考表單關鍵區(qū)域的位置，為待處理表單圖像上關鍵區(qū)域的定位結果， o verlap(·)表示區(qū)域的重疊率。

MAP是當重疊率AO高于某一閾值T時，則待處理表單的匹配位置為準確位置，故MAP表示為

式中：num(AO≥ T)表示閾值為T時準確定位的圖像數(shù)量，I為測試圖像的數(shù)量。

此外，采用標注工具LableImg標記待處理表單中提取區(qū)域真值，計算真值與檢測目標交疊率(intersection-over-union，IOU)，準確表示為

其中，IOU DetectionResult和GroundTruth表示信息提取區(qū)域檢測位置和工具標注區(qū)域真值位置。

3.3 實驗結果及分析

通過實驗對TF、FF數(shù)據(jù)集分別計算了閾值T為0.5、0.6、0.7、0.8、0.9時圖像的平均準確率和圖像的平均重疊率(mean average overlap，MAO)。當T=0.8時，表示驗證過程中參考表單和待處理表單中關鍵區(qū)域相互映射的重疊區(qū)域高于80%，實驗表明：此時用于定位的映射關系相對準確，能實現(xiàn)大部分圖像的準確定位和提取。因此本文實驗將該閾值對應的MAP作為算法準確定位的置信度。

表1是TF、FF數(shù)據(jù)集的平均準確率和重疊率的實驗統(tǒng)計情況，其中MAO反映了樣本中通過映射關鍵區(qū)域的整體重合情況。數(shù)據(jù)顯示：TF、FF中原圖像數(shù)據(jù)集和擴展數(shù)據(jù)集的MAO主要分別在90%以上和80%以上，說明根據(jù)圖匹配建立的關鍵區(qū)域映射關系，能較好的實現(xiàn)待處理表單與參考表單上關鍵區(qū)域的位置對應，因此可以通過這種映射進行表單的提取。TF、FF數(shù)據(jù)集的MAP大部分在87%～98%和75%～86%，這表明本文算法對多聯(lián)表單和熱敏表單具有良好的定位準確率。圖6中，當T=0.9時，F(xiàn)F數(shù)據(jù)集的MAP相對TF數(shù)據(jù)集低約20%～30%，波動幅度較大，原因有以下兩點：1)TF數(shù)據(jù)集中，關鍵區(qū)域均為表單出廠印制圖案和字符，同類表單的差異較小，F(xiàn)F數(shù)據(jù)集表單印制要求不統(tǒng)一，故而差異較大；2)FF數(shù)據(jù)集為非表格類表單，其內容的自由度較大，選取關鍵區(qū)域的難度較大，可參照的關鍵區(qū)域少，因此建立表單映射時嚴格匹配的特征點對較少，因此對閾值高的AO的MAP值相對較低。圖6，TF中原圖像數(shù)據(jù)集在進行旋轉、亮度調節(jié)變換后，平均準確率的變化趨于重合， FF數(shù)據(jù)集的平均準確率僅有小幅度范圍內的波動。因此，該表單提取算法對旋轉和亮度變化的圖像具有良好的穩(wěn)定性。另外，圖6中圖像縮至75%，T=0.8時，TF、FF數(shù)據(jù)集的分別為79.83%、70.11%，與原圖像數(shù)據(jù)集o-i相比MAP分別下降了48.89%、19.54%， TF數(shù)據(jù)集s-2與原圖數(shù)據(jù)集o-i和其他擴展數(shù)據(jù)集偏離幅度較大，F(xiàn)F數(shù)據(jù)集也有明顯的降低。出現(xiàn)這種變化的原因有：圖像縮小比率過大時，表單圖像上關鍵區(qū)域塊紋理信息損失較多，這將導致圖匹配時可參考的正確位置少，同時過度縮小的圖像使得關鍵區(qū)域中對應的特征點位置出現(xiàn)偏差，建立表單的映射關系缺乏準確的參考點，則重合度偏差大，準確率下降，定位不準確。總體來說，算法對旋轉、亮度調節(jié)、放大變換、小幅度縮小變換的表單圖像的提取能保持良好的穩(wěn)定性。

表1 多聯(lián)表單和熱敏表單的平均重疊率和平均準確率Table1 Mean average overlap (MAO) and mean Average Precision (MAP) of TF and FF datasets

圖6 多聯(lián)表單和熱敏表單平均準確率Fig.6 Mean average precision (MAP) of TF and FF

本文實驗通過計算提取結果與LableImg工具標記真值交疊率來評估定位的準確性。常見目標檢測系統(tǒng)中常將0.8交疊率值作為正確檢測閾值，本文在評估提取區(qū)域的準確率和平均交疊率時，這兩組值變化趨勢與映射置信度變化大致相似。因此，僅在表2中列出兩類圖像評估結果的平均情況。對比表1和表2，說明圖匹配結果越準確映射變換置信度越高，定位和提取的準確率越高。當IOU閾值為0.8時，多聯(lián)表單和熱敏表單提取準確率分別為97.41%和83.93%，說明本文算法對這兩類表單具有良好的定位與提取效果。

通過圖匹配結果對待處理表單的候選關鍵位置進行修正，使參考表單到待處理表單的位置映射關系更加準確。通過對上述圖匹配和映射后置信度的評估，驗證了算法能對表單圖像進行良好的定位。據(jù)此，圖7～10所示為表單圖像中用戶感興趣關鍵區(qū)域的定位與提取結果，其中圖7和圖8為TF類表單圖像，圖9和圖10為FF類表單圖像。圖7～10中(b)圖的提取結果自上往下分別表示提取的收貨人地址、姓名、手機號。上述4組表單圖像具有不同分辨率、亮度、方向偏轉、面單褶皺和形變的差異，定位結果說明本文算法能適應不同圖像質量差異和不同類別的圖像。由于保證了準確定位的置信度，分割得到的表單區(qū)域的字符較為完整、清晰、準確。此外，對表單分割得到的圖像塊進行簡單的字符連通域合并，得到圖7中4組表單相關信息的提取結果。

表2 多聯(lián)表單和熱敏表單的提取準確率Table2 Extraction precision of TF and FF datasets

本文方法與文獻[10, 13-14]中方法類似，均為采用模板匹配的方法解決表單填寫內容提取的問題，該方法的關鍵問題是實現(xiàn)參考表單和待處理圖像配準。文獻[10, 13]中采用傅里葉-梅林算法以表單局部區(qū)域或全局圖像為配準目標，能實現(xiàn)不同方向的表單矯正，但該方法難以適應參考表單和待處理表單不同尺度的情況，不能準確找到表單圖案的對應位置。此外文獻[13]提取文本字符時的像素投票策略對圖像噪聲較為敏感，處理分揀機中現(xiàn)實采集到的污損和局部遮擋難以達到理想的提取效果。文獻[14]中預先設定表單配準起始和終止參考點，作為表單方向校準的基準點，該方法更適用于具有相同分辨率、亮度和對比度的掃描圖像，另外，當基準點出現(xiàn)異物遮擋或缺損的情況難以靈活處理。本文方法采用表單圖匹配的方法以解決上述處理過程中存在的不足，根據(jù)不同表單已有的圖案選取多個參考關鍵區(qū)域構建圖，采用圖匹配的配準方式以解決單一參考基準點魯棒性差的問題。此外圖匹配配準方式能更好的適應不同尺度、方向、分辨率、光照條件的圖像，以及基準位置局部遮擋的問題。

圖7 C-XB表單定位和提取結果Fig.7 Results for C-XB form Location and extraction

圖8 EMS-MULT表單定位和提取結果Fig.8 Results for EMS-MULT form Location and extraction

圖9 YUNDA表單定位和提取結果Fig.9 Results for YUNDA form Location and extraction

圖10 EMS-FLAT表單定位和提取結果Fig.10 Results for EMS-FLAT form Location and extraction

4 結束語

本文提出了一種基于圖表示和匹配的表單定位與提取方法，實驗表明：本文方法適用于局部遮擋和不同類別、分辨率、方向、旋轉、光照條件下的表單圖像的處理，是一種通用的表單圖像準確定位和相關區(qū)域的提取方法。雖然本文方法實現(xiàn)了大部分表單圖像相關信息的準確定位和提取，但在縮小和單面形變幅度較大的圖像上表現(xiàn)效果不佳，下一步將考慮采用不同方法建立表單關鍵區(qū)域的映射，以適應縮小比例大和較大范圍形變圖像的處理，同時，采用更為準確的后處理方法，去除無關的空白區(qū)域，使表單相關信息的提取精確到完整的字符串。