基于SVM的流程圖像角點(diǎn)分類(lèi)

孫連山， 張沙沙， 侯　濤， 趙　曉

(陜西科技大學(xué) 電氣與信息工程學(xué)院， 陜西 西安　710021)

0　引言

流程圖代表著一個(gè)龐大的、有用的圖像子集，可以直觀地描述一個(gè)工作過(guò)程的具體步驟，具有重要的語(yǔ)義[1].流程圖像中蘊(yùn)含的豐富信息，對(duì)于檢索和查新至關(guān)重要.基于圖像匹配的檢索技術(shù)已經(jīng)得到了廣泛關(guān)注[2,3].考慮到具有相同或相似語(yǔ)義的流程圖布局多樣，為了實(shí)現(xiàn)基于流程圖像匹配的檢索必須首先識(shí)別流程圖像的語(yǔ)義，即將流程圖像識(shí)別為描述流程圖的文本信息.現(xiàn)有流程圖像識(shí)別研究大體分為兩類(lèi).一類(lèi)是基于連通域的方法提取結(jié)構(gòu)元素輪廓，然后通過(guò)輪廓擬合、BSM (Blurred Shape Model)、幾何矩描述子等幾何信息對(duì)結(jié)構(gòu)元素逐一進(jìn)行識(shí)別[3-5]；另一類(lèi)采用矢量化方法提取結(jié)構(gòu)中的邊線和結(jié)構(gòu)元素之間的結(jié)合點(diǎn)，基于直線段序列以及直線段與結(jié)合點(diǎn)之間的組合對(duì)流程圖結(jié)構(gòu)進(jìn)行識(shí)別[6-8].這些方法雖然能較好地處理清晰的流程圖像，但無(wú)法正確處理包含文圖粘連和斷邊等情況的模糊流程圖像.

角點(diǎn)是圖像的重要局部特征，已被廣泛應(yīng)用于計(jì)算機(jī)視覺(jué)和圖像處理的眾多領(lǐng)域當(dāng)中[9].流程圖像中的角點(diǎn)是直線或曲線線條的交匯點(diǎn).流程圖的圖元結(jié)構(gòu)可表示為特定類(lèi)型的角點(diǎn)組合，如矩形圖元可表示為左上(┌)、右上(┐)、左下(└)、右下(┘)等四類(lèi)角點(diǎn)的組合.流程圖像的角點(diǎn)不受圖文粘連和斷邊的影響，善加利用可以解決現(xiàn)有流程圖像識(shí)別研究所面臨的挑戰(zhàn).自動(dòng)檢測(cè)流程圖像角點(diǎn)并正確地實(shí)現(xiàn)角點(diǎn)分類(lèi)是充分利用角點(diǎn)特征識(shí)別和理解流程圖像的基礎(chǔ).

現(xiàn)有角點(diǎn)檢測(cè)算法只計(jì)算角點(diǎn)的位置，而未涉及角點(diǎn)分類(lèi).現(xiàn)有角點(diǎn)分類(lèi)研究關(guān)注于一般圖像的角點(diǎn)分類(lèi)問(wèn)題，所采用的分類(lèi)方法也相對(duì)簡(jiǎn)單[10-13].如文獻(xiàn)[10]根據(jù)角點(diǎn)鄰域中不同等值線的梯度幅值將一般圖像中的角點(diǎn)分為L(zhǎng)、Y和X等類(lèi)型；文獻(xiàn)[11]根據(jù)角點(diǎn)的歸一化各向異性方向?qū)?shù)將一般圖像中的角點(diǎn)分為簡(jiǎn)單點(diǎn)，Y型角點(diǎn)和星形角點(diǎn)等；文獻(xiàn)[12]根據(jù)角點(diǎn)兩側(cè)曲線段的曲率變化情況將角點(diǎn)分為6類(lèi)，并基于有向面積對(duì)角點(diǎn)分類(lèi)；文獻(xiàn)[13]分析并定義了特定于視網(wǎng)膜血管圖像的角點(diǎn)類(lèi)型，包括終點(diǎn)、中間點(diǎn)、T型點(diǎn)、Y型點(diǎn)和交叉點(diǎn)，并采用矩形探測(cè)器識(shí)別血管分叉點(diǎn)和血管投影交叉點(diǎn).現(xiàn)有角點(diǎn)分類(lèi)研究所定義的角點(diǎn)類(lèi)型不適用于流程圖像理解，相應(yīng)的角點(diǎn)分類(lèi)方法也相對(duì)簡(jiǎn)單而不能對(duì)流程圖像角點(diǎn)進(jìn)行準(zhǔn)確地分類(lèi).

本文結(jié)合流程圖的結(jié)構(gòu)特征，定義特定于流程圖像的角點(diǎn)分類(lèi)模型，然后采用經(jīng)典角點(diǎn)檢測(cè)算法得到候選角點(diǎn)，最后提取角點(diǎn)鄰域的網(wǎng)格密度特征和外圍特征，訓(xùn)練SVM分類(lèi)器實(shí)現(xiàn)角點(diǎn)分類(lèi)，為自動(dòng)識(shí)別和理解流程圖像奠定基礎(chǔ).

1　流程圖角點(diǎn)類(lèi)型分析

流程圖包括兩類(lèi)典型結(jié)構(gòu)元素，一類(lèi)是具有規(guī)則幾何形狀的封閉圖元，如矩形、菱形、平行四邊形、橢圓、圓等；另一類(lèi)是與圖元相連的各類(lèi)連接線，如直線、折線、箭頭、扭線等.這些結(jié)構(gòu)元素均由簡(jiǎn)單的直線或曲線構(gòu)成，多條直線或曲線的交匯點(diǎn)就構(gòu)成了流程圖像的角點(diǎn).如表1所示，在流程圖像中的封閉圖元、連接線、以及二者之間的連接處均可識(shí)別得到特定類(lèi)型的角點(diǎn).流程圖像中的結(jié)構(gòu)元素往往可抽象地表示為特定類(lèi)型的角點(diǎn)組合.

表1　流程圖像角點(diǎn)分類(lèi)

續(xù)表1

結(jié)構(gòu)元素名稱(chēng)結(jié)構(gòu)元素角點(diǎn)及命名矩形?連接線連接線?連接線(Rb?1)(Rb?2)(Rb?3)(Rb?4)菱形?連接線(Db?1)(Db?2)(Db?3)(Db?4)橢圓?連接線(Rb?1)(Rb?2)

表1分析并總結(jié)了可從八類(lèi)典型的流程圖結(jié)構(gòu)元素組合模式中提取得到的角點(diǎn)以及這些角點(diǎn)的鄰域圖示.這些角點(diǎn)可分為兩類(lèi)，一類(lèi)是僅屬于單個(gè)圖元或連接線的獨(dú)立型角點(diǎn)，如表1中上半部分角點(diǎn)；另一類(lèi)是位于圖元和連接線連接處的連接型角點(diǎn)，如表1下半部分角點(diǎn).根據(jù)角點(diǎn)鄰域所蘊(yùn)含的流程圖像結(jié)構(gòu)信息，可將角點(diǎn)進(jìn)一步分類(lèi).如表1中與矩形相關(guān)的角點(diǎn)可分為四類(lèi)，按照從上到下從左到右的順序依次為┌(R-1)、┐(R-2)、└(R-3)、┘(R-4).折線上的部分角點(diǎn)與矩形獨(dú)立型角點(diǎn)的鄰域相同，將兩種情況中的角點(diǎn)歸為同一類(lèi).同樣矩形-連接線與連接線-連接線模式中的角點(diǎn)也可以歸為同一類(lèi).

2　角點(diǎn)檢測(cè)

現(xiàn)有角點(diǎn)檢測(cè)算法大致可以分為三類(lèi)[9]：以Harris算法[14]為代表的基于灰度強(qiáng)度的方法，以曲率尺度空間(Curvature Scale Space，CSS)算法[15]為代表的基于邊緣輪廓的方法，以及以SUSAN[16]算法為代表的基于模型的角點(diǎn)檢測(cè)方法.這些方法各有優(yōu)缺點(diǎn)，適用的對(duì)象也不同.

流程圖結(jié)構(gòu)元素可分為直線型元素和曲線型元素.直線型元素包括矩形、菱形和連接線等，其邊緣輪廓局部曲率變化明顯，實(shí)驗(yàn)表明采用基于邊緣輪廓的方法(如CSS方法)即可以達(dá)到較理想的角點(diǎn)檢測(cè)效果；曲線型元素多指圓或橢圓，其邊緣輪廓局部曲率變化不明顯，實(shí)驗(yàn)表明采用基于灰度強(qiáng)度的方法(如Harris方法)可避免真實(shí)角點(diǎn)漏檢，再配合冗余角點(diǎn)篩除，即可達(dá)到較理想的角點(diǎn)檢測(cè)效果.因此，本文采取CSS和Harris角點(diǎn)檢測(cè)方法分別檢測(cè)與直線型元素和曲線型元素相關(guān)的角點(diǎn).未來(lái)應(yīng)研究針對(duì)流程圖的特定角點(diǎn)檢測(cè)算法，進(jìn)一步提高角點(diǎn)檢測(cè)的全面性和準(zhǔn)確性.

2.1　流程圖結(jié)構(gòu)提取

本文中提到的流程圖像角點(diǎn)檢測(cè)特指針對(duì)流程圖結(jié)構(gòu)圖像的角點(diǎn)檢測(cè)，識(shí)別這些角點(diǎn)對(duì)自動(dòng)識(shí)別和理解流程圖結(jié)構(gòu)至關(guān)重要.因此，在獲得原始流程圖像之后，首先要進(jìn)行圖文分割，提取原始流程圖像中的結(jié)構(gòu)圖層.

為了減少圖像本身質(zhì)量問(wèn)題以及圖像中文本對(duì)結(jié)構(gòu)圖像角點(diǎn)檢測(cè)的影響，在開(kāi)始檢測(cè)角點(diǎn)之前，首先對(duì)流程圖像進(jìn)行二值化和降噪處理.其次，采用連通域標(biāo)記算法[17]，計(jì)算并刪除面積小于指定閾值的連通域以去掉文字，實(shí)現(xiàn)圖文分割，得到流程圖結(jié)構(gòu)圖像；最后，為減少邊線粗細(xì)對(duì)角點(diǎn)檢測(cè)的影響，對(duì)提取的流程圖結(jié)構(gòu)圖像進(jìn)行單像素化[18].圖1展示了在真實(shí)流程圖中注入文圖粘連以及斷邊情況后的流程圖結(jié)構(gòu)提取效果.顯然，文圖粘連影響結(jié)構(gòu)元素的整體輪廓，無(wú)法基于輪廓正確識(shí)別結(jié)構(gòu)元素形狀.但如圖中圓圈標(biāo)記部分所示，能夠組成菱形和矩形的角點(diǎn)位置和類(lèi)型則未受影響，結(jié)構(gòu)元素的角點(diǎn)組合基本完整保留下來(lái)，達(dá)到了結(jié)構(gòu)提取的目的.

圖1　流程圖結(jié)構(gòu)提取

2.2　基于CSS的直線型結(jié)構(gòu)元素角點(diǎn)檢測(cè)

CSS 算法將不同尺度下圖像邊緣輪廓曲線的局部曲率極大值點(diǎn)作為候選角點(diǎn)，然后在多個(gè)尺度下跟蹤定位角點(diǎn).對(duì)于一條平面曲線l，不同尺度σ下的曲率.

(1)

采用CSS算法在同一尺度不同曲率下對(duì)流程圖像結(jié)構(gòu)元素進(jìn)行角點(diǎn)檢測(cè)的效果顯示，直線型結(jié)構(gòu)元素上的角點(diǎn)檢測(cè)全面準(zhǔn)確，而曲線型結(jié)構(gòu)元素上的角點(diǎn)隨曲率變化出現(xiàn)定位不準(zhǔn)及漏檢情況.為了采用CSS算法獲得直線型結(jié)構(gòu)元素上的準(zhǔn)確角點(diǎn)，本文將曲線型結(jié)構(gòu)元素上的角點(diǎn)視為圓角點(diǎn)并同虛假角點(diǎn)一起過(guò)濾掉.下面分別介紹圓角點(diǎn)及虛假角點(diǎn)的判定方法.

(2)

式(2)中：u為候選角點(diǎn)的位置參數(shù)，K(u)是候選角點(diǎn)的曲率，T(u)為與角點(diǎn)支持域自適應(yīng)的動(dòng)態(tài)局部閾值，與候選角點(diǎn)u處的局部平均曲率成正比.當(dāng)Rc=1時(shí)表示角點(diǎn)為圓角點(diǎn)，給予濾除.

(3)

式(3)中：Cc為需要判定的候選角點(diǎn)，∠Cc為角點(diǎn)Cc的角，θobtuse為真正角點(diǎn)的最大鈍角值，實(shí)驗(yàn)中設(shè)θobtuse=162°，當(dāng)Cc>θobtuse時(shí)，Cc為虛假角點(diǎn).

2.3　基于Harris的曲線型結(jié)構(gòu)元素角點(diǎn)檢測(cè)

Harris算法通過(guò)判斷角點(diǎn)的響應(yīng)函數(shù)值來(lái)確定角點(diǎn)存在與否，對(duì)于紋理豐富的曲線邊緣可以提取出大量有用的角點(diǎn).本文采用Harris算法針對(duì)曲線型結(jié)構(gòu)元素進(jìn)行角點(diǎn)檢測(cè).

流程圖中曲線型結(jié)構(gòu)元素基本位于整體結(jié)構(gòu)中周邊位置，對(duì)已經(jīng)識(shí)別的角點(diǎn)進(jìn)行邊界搜索并覆蓋掉邊界包圍的區(qū)域得到流程圖中未識(shí)別的結(jié)構(gòu)元素，然后采用Harris角點(diǎn)檢測(cè)算法對(duì)CSS角點(diǎn)檢測(cè)方法未識(shí)別的曲線型結(jié)構(gòu)元素再進(jìn)行檢測(cè).

在檢測(cè)過(guò)程中，曲線上容易產(chǎn)生角點(diǎn)聚簇現(xiàn)象.針對(duì)此問(wèn)題，本文采用距離篩選方法，計(jì)算所有點(diǎn)之間的歐式距離.當(dāng)兩個(gè)候選角點(diǎn)間的距離小于指定閾值時(shí)，可刪掉其中之一以減少冗余.

3　角點(diǎn)分類(lèi)

3.1　角點(diǎn)特征提取

角點(diǎn)鄰域蘊(yùn)含豐富的結(jié)構(gòu)信息，是對(duì)角點(diǎn)進(jìn)行分類(lèi)的依據(jù).首先，以檢測(cè)到的每個(gè)角點(diǎn)為中心截取一定大小像素的角點(diǎn)鄰域圖像；其中經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證，當(dāng)以角點(diǎn)為中心點(diǎn)向四邊擴(kuò)展20像素得到41×41像素的角點(diǎn)領(lǐng)域圖像能更好的體現(xiàn)出角點(diǎn)的特征區(qū)別；其次，參照漢字識(shí)別中的特征提取方法，提取角點(diǎn)鄰域圖像的網(wǎng)格特征和外圍特征[20].

網(wǎng)格特征是指將二值化后的圖像等分為n×n個(gè)網(wǎng)格后，每個(gè)網(wǎng)格內(nèi)目標(biāo)像素所占比例.雖然網(wǎng)格特征能較好地反映圖像內(nèi)部區(qū)域特征信息，但仍存在網(wǎng)格特征相似但不同類(lèi)型的角點(diǎn).即采用單一網(wǎng)格特征不能充分體現(xiàn)角點(diǎn)間的差異.

外圍特征是指將圖像從四邊分別向?qū)呥M(jìn)行掃描，每一邊分為m個(gè)區(qū)域，計(jì)算每個(gè)區(qū)域碰到指定目標(biāo)的面積占整個(gè)面積的比值.外圍特征主要反應(yīng)了角點(diǎn)的輪廓特征，為了加強(qiáng)角點(diǎn)細(xì)節(jié)特征的描述，分別計(jì)算一次外圍特征與二次外圍特征.一次外圍特征是計(jì)算從開(kāi)始掃描到第一次碰到目標(biāo)的面積占整個(gè)面積的比值；二次外圍特征是計(jì)算第一次穿過(guò)目標(biāo)邊與第二次再次碰到目標(biāo)邊之間的面積占整個(gè)面積的比值.

網(wǎng)格與外圍特征結(jié)合可以較好地描述角點(diǎn)鄰域所蘊(yùn)含的結(jié)構(gòu)信息.具體來(lái)講，將角點(diǎn)n×n等分，計(jì)算n2維網(wǎng)格特征，然后再?gòu)?個(gè)方向計(jì)算每個(gè)m區(qū)域的一次和二次外圍特征，構(gòu)成2×4×m維特向量，最終從角點(diǎn)鄰域提取得到一個(gè)n2+8×m維的特征向量.本文根據(jù)實(shí)驗(yàn)效果決定n和m的實(shí)際取值.

3.2　基于角點(diǎn)的SVM分類(lèi)

流程圖像角點(diǎn)分類(lèi)屬于多類(lèi)分類(lèi)問(wèn)題，可采用支持向量機(jī)(Support Vector Machine,SVM)予以實(shí)現(xiàn).SVM本身是一個(gè)二值分類(lèi)器，可以通過(guò)組合多個(gè)二分類(lèi)器來(lái)實(shí)現(xiàn)多分類(lèi)器的構(gòu)造，主要方法有one-against-one(1-a-1)，one-against-rest ( 1-a-r)，決策樹(shù)SVM( DTSVM)等方法[21],本文采用1-a-1方法構(gòu)建多類(lèi)分類(lèi)器.SVM的基本思想是通過(guò)核函數(shù)將低維不可分?jǐn)?shù)據(jù)映射到高維特征空間來(lái)解決非線性可分問(wèn)題.其本質(zhì)是求解核函數(shù)和二次規(guī)劃問(wèn)題.

SVM是一種監(jiān)督學(xué)習(xí)方法，在提取角點(diǎn)樣本特征后，應(yīng)將角點(diǎn)樣本分類(lèi)標(biāo)注，作為SVM分類(lèi)器的訓(xùn)練樣本集.本文采用徑向基核函數(shù)(Radial Basis Function,RBF)作為SVM分類(lèi)的核函數(shù).RBF核函數(shù)具有較寬的收斂范圍，是較理想的分類(lèi)依據(jù)函數(shù)，可以將一個(gè)樣本映射到一個(gè)更高維的空間.利用MATLAB中的LIBSVM工具箱來(lái)實(shí)現(xiàn)SVM多分類(lèi)，其中在目標(biāo)函數(shù)里引入懲罰因子c對(duì)其進(jìn)行懲罰，體現(xiàn)重視離群點(diǎn)帶來(lái)?yè)p失的程度.通過(guò)參數(shù)調(diào)優(yōu)設(shè)置懲罰因子c，使得數(shù)據(jù)在高維特征空間中的線性可分度最大.

3.3　交叉驗(yàn)證

使用RBF核時(shí)需要兩個(gè)參數(shù)：(c,g)，懲罰系數(shù)c是對(duì)誤差的寬容度，值越高，說(shuō)明誤差越?。籫是選擇徑向基函數(shù)作為核函數(shù)后該函數(shù)自帶的一個(gè)參數(shù)，決定了數(shù)據(jù)映射到新的特征空間后的分布.由于預(yù)先并不知道哪一對(duì)和是最佳的，因此必須要進(jìn)行參數(shù)搜索,目標(biāo)是確定一對(duì)好的(c,g) ,使分類(lèi)器能夠正確地預(yù)測(cè)未知數(shù)據(jù).因此,常見(jiàn)的方法是把訓(xùn)練數(shù)據(jù)分成兩部分,一部分作為未知數(shù)據(jù)，在這批數(shù)據(jù)上的預(yù)測(cè)精度很大程度上反映了對(duì)未知數(shù)據(jù)的分類(lèi)性能.對(duì)這一過(guò)程的改進(jìn),即交叉驗(yàn)證.本文用的是K-折交叉驗(yàn)證(K-fold CrossValidation，K-CV).將原始數(shù)據(jù)均分成K組，將每個(gè)子集數(shù)據(jù)分別做一次驗(yàn)證集，其余的K-1組子集數(shù)據(jù)作為訓(xùn)練集，這樣會(huì)得到K個(gè)模型，用這K個(gè)模型最終驗(yàn)證集的分類(lèi)準(zhǔn)確率的平均數(shù)作為此K-CV下分類(lèi)器的性能指標(biāo).

4　結(jié)果與分析

本文關(guān)注流程圖像的角點(diǎn)檢測(cè)和分類(lèi)，與針對(duì)一般圖像[10-12]、血管圖像[13]的角點(diǎn)檢測(cè)方法在角點(diǎn)模型、檢測(cè)方法上存在較大差異，無(wú)法直接對(duì)比.因此，本節(jié)僅介紹針對(duì)本文方法的實(shí)驗(yàn)驗(yàn)證與總結(jié)分析，包括實(shí)驗(yàn)數(shù)據(jù)、實(shí)驗(yàn)方式、實(shí)驗(yàn)環(huán)境以及實(shí)驗(yàn)結(jié)果分析等.

實(shí)驗(yàn)數(shù)據(jù)來(lái)源于CLEP-IP 2012[22]，其公開(kāi)的數(shù)據(jù)集包括從真正的文獻(xiàn)中獲取的150張流程圖，所有圖像都是二值形式并且僅包含單一的流程圖.實(shí)驗(yàn)中選取其中50張流程圖，結(jié)合從網(wǎng)絡(luò)上爬取的50張流程圖共100張作為實(shí)驗(yàn)對(duì)象.實(shí)驗(yàn)平臺(tái)為MATLAB R2014a，Intel(R) Core(TM) i3處理器，4 GB內(nèi)存，Windows 7操作系統(tǒng).

4.1　角點(diǎn)檢測(cè)實(shí)驗(yàn)分析

將流程圖預(yù)處理后根據(jù)連通域面積實(shí)現(xiàn)文圖分割提取流程結(jié)構(gòu)圖像，針對(duì)其中直線型和曲線型結(jié)構(gòu)元素采用CSS和Harris結(jié)合的角點(diǎn)檢測(cè)方法，實(shí)驗(yàn)效果如圖2所示.

圖2　角點(diǎn)檢測(cè)實(shí)驗(yàn)結(jié)果

CSS角點(diǎn)檢測(cè)方法對(duì)流程圖中直線型元素可以達(dá)到理想的角點(diǎn)檢測(cè)效果(空心角點(diǎn))，Harris角點(diǎn)檢測(cè)方法針對(duì)曲線型結(jié)構(gòu)元素檢測(cè)時(shí)出現(xiàn)冗余，經(jīng)過(guò)篩選可減少冗余角點(diǎn)并保留E圖元的絕大部分角點(diǎn)結(jié)構(gòu)信息(實(shí)心角點(diǎn)).

得到候選角點(diǎn)后獲取角點(diǎn)鄰域圖像，然后對(duì)其進(jìn)行分類(lèi)標(biāo)注.在實(shí)際檢測(cè)到的流程圖像角點(diǎn)中，除表1中總結(jié)的構(gòu)成結(jié)構(gòu)元素的重要角點(diǎn)以外，還有來(lái)自預(yù)處理后保留的箭頭上的角點(diǎn)、直線上噪點(diǎn)產(chǎn)生的角點(diǎn)、斜線上誤檢的角點(diǎn)以及曲線上冗余的角點(diǎn).如圖3所示，前三行為實(shí)驗(yàn)中出現(xiàn)的表1中總結(jié)的角點(diǎn)，后兩行為實(shí)驗(yàn)中出現(xiàn)的其他類(lèi)型角點(diǎn).按照角點(diǎn)類(lèi)型命名中第一個(gè)參數(shù)分為A、D、Db、Eb、E(包括El與Er)、L、R、Rb 8類(lèi).

圖3　實(shí)驗(yàn)中出現(xiàn)的流程圖像角點(diǎn)

4.2　角點(diǎn)分類(lèi)實(shí)驗(yàn)分析

對(duì)角點(diǎn)進(jìn)行特征提取，實(shí)驗(yàn)中采用不同維數(shù)特征進(jìn)行結(jié)果對(duì)比.由表2所示，m為計(jì)算外圍特征時(shí)每邊劃分的區(qū)域數(shù)，n為角點(diǎn)等分網(wǎng)格化參數(shù)，特征向量維數(shù)為n2+8×m.實(shí)驗(yàn)中截取的2 000張角點(diǎn)圖像作為訓(xùn)練集TrainData，650做測(cè)試集為T(mén)estData.提取不同維數(shù)的特征采用LIBSVM進(jìn)行角點(diǎn)的多分類(lèi)并統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果如表2所示.實(shí)驗(yàn)表明，隨著特征維數(shù)提高，訓(xùn)練集的角點(diǎn)識(shí)別率不斷提高，而過(guò)擬合使得測(cè)試集角點(diǎn)識(shí)別率下降.因此，實(shí)驗(yàn)采用m和n取8時(shí)角點(diǎn)分類(lèi)結(jié)果.首先將角點(diǎn)圖像8×8等分，計(jì)算網(wǎng)格特征構(gòu)成64維特征值，再將圖像4×4等分，分別從4個(gè)方向掃描得到外圍特征構(gòu)成64維特征值，最后每一個(gè)角點(diǎn)可以用128維特征值表示.

表2　不同特征維數(shù)的角點(diǎn)識(shí)別率

對(duì)于SVM參數(shù)的優(yōu)化，本實(shí)驗(yàn)選擇網(wǎng)絡(luò)搜索優(yōu)化方式，利用LIBSVM中g(shù)rid.py參數(shù)工具，可以自動(dòng)進(jìn)行參數(shù)尋優(yōu)，最終得到最佳參數(shù)

c=3.031 25，g=9.007 812 5.

利用參數(shù)工具得到的c，g值在SVM中建模，對(duì)角點(diǎn)類(lèi)型進(jìn)行預(yù)測(cè).將實(shí)驗(yàn)數(shù)據(jù)集均分為5組，每組角點(diǎn)520張.在分類(lèi)過(guò)程中，根據(jù)角點(diǎn)本身類(lèi)型(真/假)以及檢測(cè)結(jié)果(真/假)，可能出現(xiàn)以下幾種情況：本身是真，檢測(cè)結(jié)果也為真(TP)；本身是真，檢測(cè)結(jié)果為假(FN)；本身是假，檢測(cè)結(jié)果為真(FP).計(jì)算角點(diǎn)檢測(cè)查準(zhǔn)率(P)和查全率(R)來(lái)分析檢測(cè)結(jié)果：

查準(zhǔn)率(P)：檢測(cè)到的真角點(diǎn)數(shù)占實(shí)際真角點(diǎn)數(shù)的百分比，即

(4)

式(4)中：TP是檢測(cè)結(jié)果為真且本身為真的角點(diǎn)個(gè)數(shù)；FP為檢測(cè)結(jié)果為真但本身為假的(被誤檢)的角點(diǎn)數(shù).

查全率(R)：檢測(cè)到的真角點(diǎn)數(shù)占應(yīng)該被檢測(cè)到角點(diǎn)數(shù)的百分比，即

(5)

式(5)中：FN為本身為真而檢測(cè)結(jié)果為假的角點(diǎn)數(shù).

實(shí)驗(yàn)對(duì)5組角點(diǎn)數(shù)據(jù)集采用交叉驗(yàn)證方式，角點(diǎn)檢測(cè)結(jié)果如表3所示.根據(jù)每一組訓(xùn)練集來(lái)進(jìn)行測(cè)試集角點(diǎn)類(lèi)型的檢測(cè)，并計(jì)算查全率和查準(zhǔn)率以及每一角點(diǎn)類(lèi)型的平均值.從實(shí)驗(yàn)結(jié)果總結(jié)分析，對(duì)測(cè)試集角點(diǎn)分類(lèi)結(jié)果較理想，對(duì)5組中8類(lèi)角點(diǎn)的實(shí)驗(yàn)結(jié)果求均值得到查準(zhǔn)率為89.1%，查全率為91.6%.其中曲線型結(jié)構(gòu)元素角點(diǎn)(E，Eb)相對(duì)于直線型結(jié)構(gòu)元素角點(diǎn)的識(shí)別率低，直線型結(jié)構(gòu)元素中Rb以及角點(diǎn)特征相對(duì)復(fù)雜的A角點(diǎn)查準(zhǔn)率也相對(duì)較低.查全率和查準(zhǔn)率低的原因有三個(gè)：一是曲線形結(jié)構(gòu)元素的角點(diǎn)檢測(cè)受限于目前角點(diǎn)檢測(cè)技術(shù)，角點(diǎn)檢測(cè)定位不精確并出現(xiàn)冗余問(wèn)題；二是E圖元本身尺度問(wèn)題使得曲線局部角點(diǎn)特征有曲度差異，例如經(jīng)過(guò)預(yù)處理后得到的曲率較大的El-1角點(diǎn)與R-1角點(diǎn)會(huì)容易誤檢測(cè)；三是在實(shí)際流程圖中存在角度不同以及形式多樣問(wèn)題，細(xì)分種類(lèi)較多，樣本差距越大SVM對(duì)數(shù)據(jù)擬合程度不夠，分類(lèi)性能也就變差.

表3　各組角點(diǎn)分類(lèi)結(jié)果

為了降低角點(diǎn)誤分類(lèi)對(duì)后續(xù)流程圖結(jié)構(gòu)識(shí)別和理解的影響，對(duì)LIBSVM中預(yù)估函數(shù)返回的每個(gè)角點(diǎn)不同類(lèi)型的分類(lèi)概率做統(tǒng)計(jì)，將較高分值的前幾位所對(duì)應(yīng)的類(lèi)型依次作為預(yù)測(cè)值的候選類(lèi)型，

以此提高角點(diǎn)類(lèi)型預(yù)測(cè)準(zhǔn)確率.表3中統(tǒng)計(jì)第一組角點(diǎn)數(shù)據(jù)集的前三位候選類(lèi)型(Top3R)查全率.結(jié)果表明，三候選角點(diǎn)類(lèi)型中對(duì)各類(lèi)角點(diǎn)類(lèi)型預(yù)測(cè)準(zhǔn)確率有明顯提高.

5　結(jié)論

提出了一種針對(duì)流程圖像的角點(diǎn)檢測(cè)與分類(lèi)方法，從角點(diǎn)特征分析流程圖像并定義流程圖像角點(diǎn)分類(lèi)模型，采用角點(diǎn)鄰域的網(wǎng)格特征和外為特征訓(xùn)練SVM分類(lèi)器實(shí)現(xiàn)角點(diǎn)分類(lèi).針對(duì)公開(kāi)數(shù)據(jù)集圖像的實(shí)驗(yàn)表明采用CSS與Harris結(jié)合的方法可以全面準(zhǔn)確地檢測(cè)流程圖角點(diǎn)，并達(dá)到較好的角點(diǎn)分類(lèi)結(jié)果.本文的研究成果為進(jìn)一步開(kāi)展基于角點(diǎn)的流程圖識(shí)別研究工作奠定基礎(chǔ).

[1] Bhatti N,Hanbury A.Image search in patents:A review[J].International Journal on Document Analysis and Recognition (IJDAR),2013,16(4):309-329.

[3] Adams S.Electronic non-text material in patent applications-some questions for patent offices,applicants and searchers[J].World Patent Information,2005,27(2):99-103.

[5] Thean A,Deltorn J M,Lopez P,et al.Textual summarisation of flowcharts in patent drawings for CLEF-IP 2012[J].Aorn Journal,2012,32(2):1-21.

[6] Escalera S,Forn,Alicia S,et al.Blurred shape model for binary and grey-level symbol recognition[J].Pattern Recognition Letters,2009,30(15):1 424-1 433.

[7] Roland M,René S,Andrs H,et al.Visual structure analysis of flow charts in patent images[C]// CLEF2012 Evaluation Labs and Workshop.Roma,Italy:Online Working Notes,2012:115-133.

[8] Sas J,Markowska Kaczmar U.Logical structure recognition of diagram images[C]//2015 Federated Conference on Computer Science and Information Systems.Lódz,Poland:FedCSIS,2015:215-224.

[9] 章為川,孔祥楠,宋文.圖像的角點(diǎn)檢測(cè)研究綜述[J].電子學(xué)報(bào),2015,43(11):2 315-2 321.

[10] Ryu J B,Park H H,Park J.Corner classification using harris algorithm[J].Electronic Letter,2011,47(9):536-538.

[11] Shui L,Zhang W C.Corner detection and classification using anisotropic directional derivative representations[J].IEEE Transaction on Image Processing,2013,22(8):3 204-3 218.

[12] 曾接賢,黃華川,張桂梅.基于有向面積的角點(diǎn)分類(lèi)算法[J].中國(guó)圖象圖形學(xué)報(bào),2008,13(6):1 159-1 165.

[13] 趙曉芳,林土勝.視網(wǎng)膜血管圖像特征點(diǎn)自動(dòng)提取和分類(lèi)[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(8):14-17.

[14] Zhang C P,Wei X G.Rectangle detection based on Harris corner[J].Optics & Precision Engineering,2014,152(3):3 479-3 491.

[15] Zhang X,Lei M,Yang D,et al.Multi-scale curvature product for robust image corner detection in curvature scale space[J].Pattern Recognition Letters,2007,28(5):545-554.

[16] 韓建峰,宋麗麗.改進(jìn)的字符圖像細(xì)化算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2013,25(1):62-66.

[17] He L,Ren X,Gao Q,et al.The connected-component labeling problem:A review of state-of-the-art algorithms[J].Pattern Recognition,2017,70:25-43.

[18] 王家隆,郭成安.一種改進(jìn)的圖像模板細(xì)化算法[J].中國(guó)圖象圖形學(xué)報(bào),2004,9(3):297-301.

[19] Awrangjeb M,Lu G.An improved curvature scale-space corner detector and a robust corner matching approach for transformed image identification[J].IEEE Transactions on Image Processing,2008,17(12):2 425-2 441.

[20] 剛亞州,黃元元,戴群.一種快速名片字符識(shí)別算法[J].計(jì)算機(jī)應(yīng)用研究,2014,31(9):2 859-2 863.

[21] 王道明,魯昌華,蔣薇薇,等.基于粒子群算法的決策樹(shù)SVM多分類(lèi)方法研究[J].電子測(cè)量與儀器學(xué)報(bào),2015,29(4):611-615.

[22] Piroi F,Lupu M,Hanbury A,et al.CLEF-IP 2011:Retrieval in the intellectual property domain,September 2011[DB/OL].http://www.ifs.tuwien.ac.at/ ～clef-ip/download/2012/ index.shtml,2012-09-04.