基于模糊Ｈｉｔ－Ｍｉｓｓ變換的信息填涂卡識(shí)別方法研究

（1.哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院 哈爾濱 150001；2.中國(guó)科學(xué)院 自動(dòng)化研究所 北京 100080）

摘 要：介紹了一個(gè)針對(duì)信息填涂卡識(shí)別的OMR技術(shù)，這是自動(dòng)閱卷系統(tǒng)中非常關(guān)鍵的一個(gè)環(huán)節(jié)。介紹了模糊HitMiss變換的原理，并基于該原理，詳細(xì)介紹了OMR算法。為了增強(qiáng)系統(tǒng)的魯棒性和適應(yīng)性，對(duì)識(shí)別信度進(jìn)行評(píng)估，并由用戶根據(jù)實(shí)際情況設(shè)定適當(dāng)?shù)拈撝怠?shí)驗(yàn)結(jié)果表明，本文方法性能優(yōu)越，有很高的實(shí)用價(jià)值。

關(guān)鍵詞：自動(dòng)閱卷系統(tǒng)；光學(xué)標(biāo)記識(shí)別；模糊HitMiss變換

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)05-1822-03

Research on optical mark card reader based on blur HitMiss transform

XIA Yong1，XIAO Baihua2，ZHU Yuanping2

(1.School of Computer Science Technology Harbin Institute of Technology，Harbin 150001 China；2.Institute of Automation Chinese Academy of Sciences Beijing 100080 China)

Abstract:This paper introduced the technology of reading optical mark card which was the key of automatic paper reader.Introduced and used blur HitMiss transform for OMR.In order to increase the robustness and adaptability of system，evaluated recognition confidence.The user can set the valid confidence threshold. The experimental result confirms the advantage and applicability of our algorithm.

Key words:automatic paper reader; OMR(optical marker recognition); blur HitMiss transform(BHMT)

目前，OMR在標(biāo)準(zhǔn)化閱卷、問(wèn)卷調(diào)查、選票統(tǒng)計(jì)、人口普查等領(lǐng)域有著廣泛的應(yīng)用。OMR技術(shù)一般采用光電對(duì)管閱讀技術(shù)，就是采用了兩個(gè)光電器件，即半導(dǎo)體發(fā)光管和光敏管。在識(shí)別時(shí)，由發(fā)光管發(fā)出光照射到選項(xiàng)涂點(diǎn)區(qū)域上，通過(guò)光敏管接收來(lái)自選項(xiàng)涂點(diǎn)區(qū)域的反射光。因?yàn)檫x項(xiàng)填涂的情況直接決定了反射光的強(qiáng)弱，所以根據(jù)此特性可以判定選項(xiàng)是否填涂。但這種方式存在以下幾個(gè)缺陷：a）對(duì)紙張有較高的要求，成本高;b）保存與查閱不方便;c）需要購(gòu)買(mǎi)專門(mén)的涂點(diǎn)標(biāo)記識(shí)別設(shè)備，需要較大的硬件投入;d）速度慢，對(duì)于大批量的閱卷而言效率較低。 傳統(tǒng)的OMR閱卷機(jī)存在著種種弊端，因而一種新的基于圖像灰度分析的涂點(diǎn)識(shí)別技術(shù)應(yīng)運(yùn)而生^[1~3]。其基本方法就是先利用高速掃描儀將所有紙質(zhì)文檔掃描為圖像格式進(jìn)行保存，然后利用圖像識(shí)別技術(shù)對(duì)文檔圖像中的選項(xiàng)區(qū)域進(jìn)行涂點(diǎn)識(shí)別。該方法的優(yōu)點(diǎn)主要是無(wú)須專門(mén)的光學(xué)標(biāo)記閱卷設(shè)備，對(duì)填涂卡紙張也沒(méi)有特殊要求，成本低廉，無(wú)論對(duì)大型還是小型的閱卷應(yīng)用都比較合適。另外，由于采用了圖像格式來(lái)保存紙質(zhì)文檔，文檔的保存與查詢非常方便。

盡管信息填涂卡的識(shí)別原理相對(duì)簡(jiǎn)單，但其要求有很高的識(shí)別率，對(duì)于正常的掃描樣本應(yīng)達(dá)到100％的識(shí)別率，否則很難得到大規(guī)模的應(yīng)用。由于OMR算法相對(duì)簡(jiǎn)單，目前很少有論文涉及填涂卡選項(xiàng)識(shí)別的具體算法，本文將對(duì)該內(nèi)容進(jìn)行較為詳細(xì)的分析。在圖像識(shí)別過(guò)程中需要用到圖像匹配算法，而基于Hausdorff距離的方法在圖像匹配中有著廣泛的應(yīng)用^[4，5]，但該方法對(duì)噪聲很敏感。在文獻(xiàn)[6，7]中介紹了一種模糊HitMiss變換，這也是一種較為常見(jiàn)的圖像匹配方法，對(duì)噪聲有較強(qiáng)的抑制能力，特別適合掃描文檔類圖像的處理。本文主要基于該方法研制了一個(gè)高效的填涂卡自動(dòng)識(shí)別系統(tǒng)。

1 模糊HitMiss變換

HitMiss變換（HitMiss transform，HMT）是一種數(shù)學(xué)形態(tài)學(xué)的圖像處理方法，在分析物體的結(jié)構(gòu)和形狀等方面有廣泛的應(yīng)用。數(shù)學(xué)形態(tài)學(xué)是由一組形態(tài)學(xué)的代數(shù)運(yùn)算子組成的。最基本的形態(tài)學(xué)算子有腐蝕、膨脹、開(kāi)運(yùn)算和閉運(yùn)算。HitMiss是構(gòu)建在這些基本運(yùn)算之上的一種復(fù)合運(yùn)算。由于數(shù)學(xué)形態(tài)學(xué)的原理簡(jiǎn)單、運(yùn)算速度快，近年來(lái)在圖像處理等領(lǐng)域有大量的研究和應(yīng)用。

一個(gè)二值圖像X的HitMiss變換可以用下式來(lái)表示^[8]：

X（τf，τb）=(XΘτf)∩(XCΘτb)(1)

其中：表示HMT；Θ表示腐蝕變換；XC是X的補(bǔ)集，也就是X的背景圖像；結(jié)構(gòu)算子S=（τf，τb），τf表示Hit算子，τb表示Miss算子。

HitMiss變換盡管方法簡(jiǎn)單、操作方便，但對(duì)噪聲很敏感。在文獻(xiàn)[7]中提出了一種模糊HitMiss變換（BHMT），具體表示如下：

X（τf，τb；βf，βb）=((Xβf)Θτf)∩((XC

βb)Θτb)(2)

其中：表示HMT；Θ表示腐蝕變換；表示膨脹變換；XC是X的補(bǔ)集，也就是X的背景圖像；結(jié)構(gòu)算子S=（τf，τb），τf表示Hit算子，τb表示Miss算子。

對(duì)比式（1）和（2）可見(jiàn)，式（2）在執(zhí)行HMT時(shí)，對(duì)圖像前景X和背景XC均進(jìn)行了膨脹，目的就是容忍噪聲的干擾。

在掃描文檔中，一般存在兩種噪聲，即邊緣噪聲和隨機(jī)噪聲。對(duì)于邊緣噪聲，主要是由于圖像中物體的邊緣在進(jìn)行二值化處理時(shí)引起的，一般這種噪聲為1、2個(gè)像素寬度。對(duì)于隨機(jī)噪聲，可能是由于掃描儀本身有污點(diǎn)等原因造成，獨(dú)立于圖像本身。這類噪聲最為常見(jiàn)的就是椒鹽噪聲。HMT對(duì)這兩種噪聲都不具備較強(qiáng)的容忍能力，而B(niǎo)HMT可以通過(guò)選擇恰當(dāng)?shù)那熬芭c背景的膨脹算子達(dá)到容忍這兩類噪聲的能力^[7]。

2 填涂卡識(shí)別方法

2.1 涂點(diǎn)識(shí)別的一般方法

信息填涂卡中涂點(diǎn)識(shí)別問(wèn)題可看成是一個(gè)基于模式的模式識(shí)別問(wèn)題。一般而言，可以利用空白的信息卡建立模板信息，然后將該模板與待識(shí)別信息卡進(jìn)行匹配，最后基于匹配結(jié)果給出是否填涂的判斷。對(duì)于模板的建立方法，可以分為兩步：a)標(biāo)記信息卡中的定位塊，從而建立一個(gè)整體模板；b)對(duì)需要進(jìn)行填涂的選項(xiàng)區(qū)域進(jìn)行標(biāo)記，從而建立局部模板。由于在信息卡掃描的過(guò)程中可能會(huì)存在一定的傾斜，為了使得待識(shí)別信息卡的填涂區(qū)域能夠基于模板被準(zhǔn)確標(biāo)定，需要對(duì)信息卡圖像進(jìn)行傾斜校正。

對(duì)于涂點(diǎn)區(qū)域的識(shí)別，可以采用基于二值圖像方法進(jìn)行識(shí)別和基于灰度圖像方法進(jìn)行識(shí)別。基于二值圖像的方法算法簡(jiǎn)單，但有較大的應(yīng)用局限性。基于灰度圖像的方法算法相對(duì)復(fù)雜。

基于二值圖像的識(shí)別方法就是先對(duì)圖像進(jìn)行二值化，然后對(duì)填涂區(qū)域黑點(diǎn)進(jìn)行統(tǒng)計(jì)，超過(guò)一定閾值，即認(rèn)為被填涂。這種方法對(duì)無(wú)紋理背景的填涂區(qū)域的判定很有效，速度也很快，但不能直接用于有紋理背景填涂區(qū)域的判斷。這主要是因?yàn)樵趫D像二值化時(shí)，紋理背景很可能會(huì)被當(dāng)做前景，從而造成誤判。一種改進(jìn)的方法就是對(duì)模板也進(jìn)行同樣的操作，統(tǒng)計(jì)模板中填涂區(qū)域的黑點(diǎn)數(shù)，以此值作為一個(gè)閾值。但這種方法仍然缺乏對(duì)邊緣噪聲的容忍性。

基于灰度圖像的識(shí)別方法就是直接利用待識(shí)別填涂卡的填涂區(qū)域的灰度信息，灰度越深說(shuō)明填涂的可能性越大。基于灰度的方法很難利用模板的信息，這是因?yàn)閷?duì)于同一張信息卡，經(jīng)過(guò)兩次掃描后得到的兩幅圖像在灰度上可能并不是很一致。一般而言，可以建立一個(gè)灰度強(qiáng)度的函數(shù)，對(duì)填涂區(qū)域灰度強(qiáng)度進(jìn)行統(tǒng)計(jì)，超過(guò)一定的閾值就判定為被填涂。但這種統(tǒng)計(jì)結(jié)果有時(shí)與人們的主觀感知并不是很一致。如果是彩色圖像，往往可以利用色差等信息來(lái)輔助對(duì)填涂區(qū)域進(jìn)行判定。但本文中僅考慮更通用的情況，即灰度圖像的情況。

本文提出了一種基于二值與灰度信息混合的涂點(diǎn)識(shí)別方法，可以較好地適應(yīng)二值圖像、灰度圖像，以及有無(wú)背景紋理等情況。此外，為了使識(shí)別的結(jié)果與人的主觀感覺(jué)盡可能接近，本文對(duì)識(shí)別結(jié)果給出信度評(píng)估結(jié)果，用戶可根據(jù)具體情況，設(shè)定信度閾值。

2.2 識(shí)別預(yù)處理

圖1為一個(gè)掃描的答題卡圖像。其中除了需要填涂的選項(xiàng)區(qū)域外，還有很多用于定位的信息塊。根據(jù)填涂區(qū)域的情況，將選項(xiàng)分為無(wú)背景紋理選項(xiàng)和有背景紋理選項(xiàng)。對(duì)于無(wú)背景紋理選項(xiàng)的識(shí)別相對(duì)簡(jiǎn)單，在本文中就不具體介紹。本文主要介紹有紋理背景選項(xiàng)的識(shí)別方法。

假定填涂標(biāo)準(zhǔn)為完全涂滿整個(gè)選項(xiàng)區(qū)域。在進(jìn)行涂點(diǎn)識(shí)別前，首先需要建立空白信息卡圖像模板，然后基于當(dāng)前信息卡圖像的定位塊或模板圖像得到當(dāng)前信息卡圖像上需要進(jìn)行識(shí)別的涂點(diǎn)選項(xiàng)區(qū)域。假定當(dāng)前信息卡的一個(gè)問(wèn)題選項(xiàng)圖像為U，而對(duì)應(yīng)的模板選項(xiàng)圖像為V。假定該問(wèn)題的備選項(xiàng)數(shù)目為N，U的各個(gè)備選項(xiàng)圖像為U1，…，UN，V的備選項(xiàng)為V1，…，VN。由于當(dāng)前信息卡的選項(xiàng)區(qū)域是計(jì)算機(jī)自動(dòng)分析出來(lái)的，與真實(shí)的位置可能會(huì)存在一定的微小偏差；而模板信息卡的選項(xiàng)區(qū)域是人工定義的，所以可以認(rèn)為其選項(xiàng)區(qū)域是準(zhǔn)確的。為了便于比較兩幅圖像的相似度，利用以下方法來(lái)進(jìn)行計(jì)算。

假定兩幅具有同樣尺寸大小的圖像分別為A和B。函數(shù)n(X)表示圖像X內(nèi)黑點(diǎn)的數(shù)量。P為A中的任意一個(gè)像素點(diǎn)，Q為B中與P對(duì)應(yīng)的點(diǎn)。

P與Q的相似度定義為

f(P，Q)=1 P與Q具有相同的灰度值0 其他（3）

圖像A到B的相似度定義為

SAB=f(A，B)=n(A)i=1f(Pi，Qi)/[n(A)](4)

圖像B到A的相似度定義為

SBA=f(B，A)=n(B)i=1f(Qi，Pi)/[n(B)](5)

圖像A與B之間的相似度定義為

S=min(SAB，SBA)(6)

2.3 識(shí)別算法

對(duì)于有背景紋理的選項(xiàng)的識(shí)別算法描述如下：

a)若圖像為非二值的灰度或彩色圖像，則對(duì)U和V分別利用二值化方法對(duì)圖像進(jìn)行二值化，其灰度閾值分別為GU和GV，并分別得到圖像UB和VB。若圖像本身就是二值圖像，則用UB和VB分別表示U和V。UB中的備選項(xiàng)分別為UB1，…，UBN。VB中的備選項(xiàng)分別為VB1，…，VBN。

b）不失一般性，僅考慮UBi的識(shí)別過(guò)程，這里i=1-N。為了表述的方便，用X表示UBi，用Y表示VBi。

c)將X的區(qū)域向上下左右四個(gè)方向分別擴(kuò)充幾個(gè)像素點(diǎn)，得到新圖像X′以便進(jìn)行選項(xiàng)區(qū)域的微調(diào)。

d)對(duì)X′進(jìn)行膨脹得到圖像PX′，膨脹的結(jié)構(gòu)元素如圖2所示。

e)將Y的圖像在PX′中進(jìn)行滑動(dòng)，對(duì)某一個(gè)滑動(dòng)點(diǎn)而言，PX′中就存在一個(gè)與Y對(duì)應(yīng)的子圖像用Z來(lái)表示。計(jì)算各個(gè)不同滑動(dòng)位置從Y到Z的相似度，以具有最大相似度的滑動(dòng)位置為匹配點(diǎn)。

f）根據(jù)Z的坐標(biāo)在圖像X′中得到相應(yīng)的圖像W。對(duì)W向四個(gè)方向各擴(kuò)充幾個(gè)像素點(diǎn)，得到新圖像W′。

g)將Y的圖像在W′中滑動(dòng)，利用與e)類似的方法，得到一個(gè)最佳匹配點(diǎn)，并從W′中提取出相應(yīng)的圖像，定義為R。這樣就得到了經(jīng)過(guò)微調(diào)后的當(dāng)前信息卡中問(wèn)題選項(xiàng)的精確圖像。該圖像與模板進(jìn)行了較好的配準(zhǔn)。下面將對(duì)R和Y進(jìn)行比較，從而得到識(shí)別結(jié)果。

h)基于BHMT對(duì)當(dāng)前填涂區(qū)域與模板進(jìn)行變換，基于一定的閾值判定是否匹配，若匹配成功則說(shuō)明沒(méi)有填涂；否則需要進(jìn)行后續(xù)基于灰度分析的判定過(guò)程。這里BHMT采用的前景與背景的膨脹結(jié)構(gòu)元素均如圖2所示。在對(duì)背景圖像進(jìn)行操作時(shí)，應(yīng)對(duì)圖像進(jìn)行反白處理，然后再進(jìn)行相應(yīng)的操作。

i)將模板圖像Y進(jìn)行膨脹得到新圖像PY，膨脹的結(jié)構(gòu)元素如圖2所示。將R與PY進(jìn)行差分，得到差分圖像D。

j)根據(jù)R的坐標(biāo)，在原始灰度圖像U中得到原始的問(wèn)題選項(xiàng)圖像RS。

k)基于當(dāng)前選項(xiàng)塊區(qū)域圖像RS和差分圖像D，給出識(shí)別結(jié)果，具體方法如下：

定義灰度函數(shù)g(x)表示點(diǎn)x的灰度值，h(x)表示點(diǎn)x的灰度強(qiáng)度值，值越大表示灰度越深。如果原始圖像U為非二值的灰度或彩色圖像，則

h(x)=0g(x)＞GU

GU-g(x)GM≤g(x)≤GU

GU-GMg(x)＜GM(7)

其中:GU為二值化的灰度閾值；GM為能保證可靠填涂的灰度值。GU在a)的圖像二值化時(shí)就已經(jīng)得到了，而GM的值為定位塊的平均灰度值。定位塊的定義如圖1所示。

如果原始圖像為二值圖像，則

h(x)=0 g(x)=255

1 g(x)=0(8)

假定x為RS中的任意一個(gè)點(diǎn)，而x′為D中與x對(duì)應(yīng)的點(diǎn)，則用f(x)表示點(diǎn)x的加權(quán)灰度強(qiáng)度值，則

f(x)=h(x)×h(x′)(9)

圖像RS的灰度強(qiáng)度為

f(RS)=ni=1f(xi)(10)

其中：n為圖像RS中所有點(diǎn)的數(shù)量。

該選項(xiàng)最終的識(shí)別結(jié)果為

recog(Ui)=f(RS)/用最深灰度涂滿時(shí)的圖像灰度強(qiáng)度值=ni=1f(xi)/[(n-m)(GU-GM)]U為非二值的灰度或彩色圖像

ni=1f(xi)/(n-m)U為二值圖像(11)

顯然該輸出結(jié)果的取值為0~1。根據(jù)實(shí)際情況，可以選擇不同的信度閾值，以達(dá)到可靠的識(shí)別結(jié)果。

3 實(shí)驗(yàn)結(jié)果與結(jié)論

基于本文方法開(kāi)發(fā)的自動(dòng)閱卷系統(tǒng)界面如圖3所示。該系統(tǒng)可人工定義模板、設(shè)置答案、識(shí)別學(xué)生考號(hào)、自動(dòng)識(shí)別客觀題并根據(jù)答案數(shù)據(jù)自動(dòng)生成分?jǐn)?shù)。選用了200幅各種類型的信息填涂卡，其中需填涂的選項(xiàng)區(qū)域共約8 000個(gè)，圖像類型包括彩色、灰度和二值；填涂區(qū)域背景包括有紋理和無(wú)紋理兩種情況。利用本文的方法，在樣本集上達(dá)到了100％的識(shí)別率。

基于實(shí)驗(yàn)結(jié)果，本文的算法簡(jiǎn)單高效，對(duì)圖像背景有很強(qiáng)的自適應(yīng)能力，有很強(qiáng)的實(shí)用價(jià)值。將數(shù)學(xué)形態(tài)學(xué)中的經(jīng)典方法HitMiss變換的改進(jìn)方法模糊HitMiss變換引入填涂卡識(shí)別問(wèn)題中來(lái)，取得了較好的實(shí)驗(yàn)效果。此外，還將圖像的灰度信息與二值信息進(jìn)行了結(jié)合，充分利用這兩類信息不同的特點(diǎn)，提高了系統(tǒng)的魯棒性與自適應(yīng)能力。

由于信息填涂卡的類型多種多樣，除了要求選項(xiàng)涂滿這種最為常用的情況外，還有要求在選項(xiàng)區(qū)域進(jìn)行畫(huà)線、畫(huà)圈、打勾、打叉等填涂模式。由于這些填涂方式大多出現(xiàn)在選票統(tǒng)計(jì)、調(diào)查問(wèn)卷等領(lǐng)域，填涂方式可能很不規(guī)范，這為自動(dòng)化識(shí)別提出了較高的要求，也是下一步需要深入研究的內(nèi)容。

參考文獻(xiàn)：

［1］ANDROULIDAKISI，ANDROULIDAKIS N.On a versatile and costless OMR system[J].WSEAS Trans on Computers，2005，4(2):160165.

[2]HUSSMANN S，CHAN L，F(xiàn)UNG C，et al.Lowcost and highspeed optical mark reader based on an intelligent line camera[C]//Proc of SPIE：The International Society for Optical Engineering.2003:200208.

[3]CHINNASARN K，RANGSANSERI Y.Imageprocessing oriented optical mark reader[C]//Proc of SPIE:The International Society for Optical Engineering.1999:702708.

[4]HUTTENLOCHER D P，KLANDERMAN G A，RUCKLIDGE W J.Comparing images using the Hausdorff distance[J].IEEE Trans on Pattern Analysis and Machine Intelligence 1993，15(9):850863.

[5]HUTTENLOCHER D P，RUCKLIDGEW.A multiresolution technique for comparing images using the Hausdorff distance[C]//Proc of IEEE Conference on Computing Vision and Pattern Recognition.[S.l.]:IEEE Press，1993:705706.

[6]BLOOMBERG D，MARAGOS P.Generalized hitmiss operations[C]//Proc of SPIE.1990:116128.

[7]BLOOMBERG D，VINCENT L.Pattern matching using the blur HitMiss transform [J].Journal of Electronic Imaging，2000，9(2):140150.

[8]SERRA J.Image analysis and mathematical morphology [M].[S.l.]:Acad Press，1982.