基于決策樹分析的激光打印文件黑色墨跡量化分析研究

牟小彬，李睿麟，程衛(wèi)國

?

基于決策樹分析的激光打印文件黑色墨跡量化分析研究

牟小彬，李睿麟，程衛(wèi)國

（上海市公安局，上海 200083）

摘要：目的 研究利用圖像掃描分析系統(tǒng)量化分析激光打印文件黑色墨跡的方法，優(yōu)選可用于打印機種類區(qū)分的量化參數(shù)。方法 使用圖像掃描分析系統(tǒng)，采用每英寸800像素點的分辨率，對市場上9個主流品牌18種型號共18臺激光打印機360頁打印樣本的面積、周長、灰度等特征進行整幅測量。通過決策樹C4.5算法建立數(shù)學(xué)模型，對測量所得參數(shù)值進行數(shù)據(jù)分析。結(jié)果 發(fā)現(xiàn)閾值分別設(shè)置為80、117、128、160時，測量所得的29項參數(shù)116組測量數(shù)值中閾值為128的中位灰度值，閾值為80的灰度眾數(shù)值，閾值為117、最小測量面積為1的字塊面積標(biāo)準(zhǔn)差，閾值為80的面積比值，閾值為160、最小測量面積為1的字塊面積標(biāo)準(zhǔn)差，閾值為80的中位灰度值，閾值為80、最小測量面積為1的字塊圓度標(biāo)準(zhǔn)差，閾值為128的對稱分布值，閾值為117的面積比值，閾值為160的中位灰度值，閾值為117、最小測量面積為1的字塊圓度平均值等11組參數(shù)組合能夠?qū)颖菊_區(qū)分。結(jié)論 不同種類激光打印機打印樣本在上述11組參數(shù)所衡量的灰度、面積、圓度、打印墨跡數(shù)量等特征及特征的組合上存在差別，通過量化方法區(qū)分激光打印機打印樣本具有可行性。

關(guān)鍵詞：文件檢驗；激光打印；量化分析；決策樹

激光打印文件的量化分析檢驗一直是個難點。不同種類激光打印機由于制造工藝的差異，打印文件在墨跡的灰度、打印線條的粗細(xì)和粗糙程度、筆畫周圍散落墨粉點的數(shù)量等方面存在差別，如何通過量化的方法表現(xiàn)這些特征的差異，以區(qū)分不同種類的激光打印機打印文件，成為亟待解決的問題。ImageXaminer圖像掃描分析系統(tǒng)可對打印文件的灰度、線條打印質(zhì)量、碳粉附著性、色間滲透等參數(shù)進行測量，對打印文件質(zhì)量進行量化分析。本文運用ImageXaminer圖像掃描分析系統(tǒng)，對打印文件的墨跡微觀特征進行量化，并通過決策樹分析方法，找出與激光打印機種類區(qū)分相關(guān)性較強的參數(shù)項組合，對量化區(qū)分激光打印機打印文件的方法進行探索，為違法宣傳品印制機具的排查比對，以及添加、換頁文件的檢驗鑒定等案件檢驗提供新的思路。

1 材料與方法

1.1 實驗材料

選取市場上9個主流品牌18種型號的激光打印機各1臺（見表1）。根據(jù)激光打印機制作的違法宣傳品所具有的黑白打印、同一內(nèi)容重復(fù)出現(xiàn)等特點，將打印電子文檔設(shè)置為宋體、黑色、五號字，內(nèi)容由案件中常用漢字“的、了、法、是、我”隨機組合而成，使用同一電子文檔在同品牌A4幅面紙張上打印文件20頁，分別編號，共360份樣本。使用ImageXaminer圖像掃描分析系統(tǒng)（ImageXpert，美國），采用800dpi分辨率進行掃描錄入樣本，并選取等大的目標(biāo)區(qū)域（regions of interest，下文簡稱ROI）對打印文件進行整幅測量。

表 1 實驗用激光打印機品牌和型號Table 1 Laser printer brands and models used in the experiment

1.2 參數(shù)選擇

ImageXaminer圖像掃描分析系統(tǒng)可實現(xiàn)圖像增強、圖像形態(tài)改變、目標(biāo)區(qū)域運算、面積測量、灰度測量、線條、邊緣測量、連通區(qū)域測量、相關(guān)區(qū)域測量、霍夫變換算法、向量、文字識別、二維碼解碼、條紋測量等測量運算。在實驗過程中對適用于打印文件整幅測量的參數(shù)進行篩選，發(fā)現(xiàn)連通區(qū)域測量、灰度測量、面積測量三類參數(shù)適用于打印文件整幅測量。連通區(qū)域測量是指根據(jù)設(shè)定的像素極性、灰度閾值、最小測量面積等測量條件，將待測ROI中的字符劃分為若干個連通區(qū)域，并對具有相同明暗極性的連通像素群或由相同明暗極性像素群圍成的整塊像素群（包括明、暗兩類像素）的面積、周長、圓度、背景噪聲等微觀特征進行量化測量?；叶戎禍y量是指根據(jù)設(shè)定的像素極性、灰度閾值等測量條件，對明、暗像素的灰度、明暗線條數(shù)量、對比度等微觀特征進行量化測量。面積測量是指根據(jù)設(shè)定的像素極性、灰度閾值等測量條件，對明暗像素的面積、面積比值等微觀特征進行量化測量。

進一步對上述三類參數(shù)中反映打印文件灰度、面積、周長、背景噪聲等特征參數(shù)項進行優(yōu)選，篩選出29項測量參數(shù)。（1）衡量打印文件灰度特征參數(shù)項：有平均灰度、灰度標(biāo)準(zhǔn)差、輪廓平均灰度、輪廓灰度標(biāo)準(zhǔn)差、暗線條數(shù)量、明線條數(shù)量、暗線條灰度標(biāo)準(zhǔn)差、明線條灰度標(biāo)準(zhǔn)差、暗線條平均灰度、亮線條平均灰度、對稱分布值、中位灰度值、灰度眾數(shù)值、對比度；（2）打印文件面積特征的參數(shù)項：面積、面積比值、字塊總面積、墨塊總面積；（3）打印文件周長特征的參數(shù)項：字塊總周長、墨塊總周長；（4）打印文件背景噪聲特征的參數(shù)項有背景噪聲；（5）打印文件墨跡數(shù)量特征參數(shù)項：字塊數(shù)量、墨塊數(shù)量；（6）綜合衡量打印文件面積、打印墨跡數(shù)量的參數(shù)項：字塊面積平均值、字塊面積標(biāo)準(zhǔn)差；（7）綜合衡量打印文件灰度、打印墨跡數(shù)量的參數(shù)項：字塊灰度平均值、字塊灰度標(biāo)準(zhǔn)差；（8）綜合衡量打印文件圓度特征（字塊線條的粗糙程度）、打印墨跡數(shù)量的參數(shù)項：字塊圓度平均值、字塊圓度標(biāo)準(zhǔn)差。

1.3 測量條件選擇

ImageXaminer圖像掃描分析系統(tǒng)可以自定義灰度閾值及測量的面積范圍，為了更加全面的、恰當(dāng)?shù)姆从炒蛴颖镜那闆r，本實驗對測量條件進行了如下設(shè)置：

1.3.1 灰度閾值設(shè)置

由于打印機品牌、型號、使用環(huán)境等相關(guān)因素的影響，打印件打印文字墨跡粉堆積感及底灰不同，簡單來說，就是人眼觀察到的顏色深淺不同；從圖像上來說，就是墨跡的灰度不同。在灰度圖像中的每個像素都是從0～255的亮度值，通常把0定義為“黑”，255定義為“白”。閾值就是臨界值，是基于圖片亮度的一個分界值，默認(rèn)值是50%中性灰（即128），也就是當(dāng)選擇灰度閾值為128時，亮度低于128的即被認(rèn)為“黑”，在利用系統(tǒng)對打印件相關(guān)參量的測量中，可以自行定義閾值，而閾值的確定決定了準(zhǔn)入計算的亮度值。一般在閾值較小的情況下，墨粉淺淡的筆畫不參與計算；在閾值較大的情況下，可以充分地識別墨點，但有時也會把紙張上的深色纖維點算入，閾值過大，超出了樣本的最大灰度極限，則無法測量。

系統(tǒng)會根據(jù)閾值選擇所測部分，閾值設(shè)定不同，同一參數(shù)的測量值會隨之變化，如針對同一張樣本，對字塊面積平均值參數(shù)進行測量，設(shè)定最小測量面積為1，當(dāng)灰度閾值設(shè)置為80時測量值為0.117，當(dāng)灰度閾值設(shè)置為117時測量值為0.18，當(dāng)灰度閾值設(shè)置為128時測量值為0.198，當(dāng)灰度閾值設(shè)置為160時測量值為0.161。為了全面反映各樣本的量化測量情況，實驗中選擇亮度較深的80，此時一些淺淡的筆畫不參與計算；中間值117，此時筆畫周圍的散落墨粉點基本不參與計算；默認(rèn)值128，此時筆畫周圍的散落墨粉點大部分參與計算；亮度較淺的160，此時除筆畫周圍的散落墨粉外，頁面上的散落墨粉點和疵點也參與計算，共4種閾值設(shè)置。

1.3.2 最小測量面積設(shè)定

打印機墨跡的連通區(qū)域測量過程中可以自定義參與計算的最小墨跡面積，該設(shè)置最小面積定義為≥1，即1為最小的數(shù)量級，系統(tǒng)默認(rèn)最小值為100，可自行設(shè)定任意值。系統(tǒng)會根據(jù)最小測量面積選擇參與測量的墨點，最小準(zhǔn)入測量面積不同，同一參數(shù)的測量值也會隨之變化。如針對同一張樣本，對字塊面積平均值參數(shù)進行測量，設(shè)定灰度閾值為128，當(dāng)最小測量面積為1時測量值為0.198，最小測量面積為1時測量值為0.149。但當(dāng)選擇系統(tǒng)默認(rèn)最小值100時，背景噪聲為0，無法測量，為了充分反映筆畫周圍的細(xì)微墨點分布情況，實驗中選擇最小測量面積為系統(tǒng)最小值1。根據(jù)上述測量條件設(shè)置，測量參數(shù)共計29項116組。

2 數(shù)據(jù)分析

2.1 算法選擇

本實驗收集打印樣本360份，每份樣本具有116個屬性，并已知每個樣本的分類標(biāo)號（樣本屬于哪一臺打印機），可以通過“監(jiān)督學(xué)習(xí)”的分類算法建立分類模型?！氨O(jiān)督學(xué)習(xí)”分類算法比較著名的有決策樹，樸素貝葉斯，神經(jīng)網(wǎng)絡(luò)，支持向量機等。這些算法里，決策樹學(xué)習(xí)算法是最廣泛應(yīng)用的一種方法，這種算法的分類精度與其他算法相比具有相當(dāng)?shù)母偁幜?，并且十分高效。支持向量機具有很好的魯棒性，計算復(fù)雜性不取決于維數(shù)，因此避免了“維數(shù)災(zāi)難”，但是它對于大樣本分類和多分類問題存在不足。神經(jīng)網(wǎng)絡(luò)具有非常強的非線性擬合能力，但是它最大的缺點即是缺乏解釋能力。樸素貝葉斯的前提條件太過嚴(yán)苛，需要屬性之間具有獨立性。所以，針對本實驗的特點，選擇決策樹模型作為分類方法。常用決策樹算法有ID3算法和C4.5算法，下面依次介紹這兩種算法。

2.1.1 決策樹算法簡介

決策樹是一種由節(jié)點和有向邊組成的樹狀結(jié)構(gòu)，樹中包含三種節(jié)點（見圖1）：1、根節(jié)點，沒有入邊，但有零條或多條出邊；2、內(nèi)部節(jié)點，有一條入邊和兩條或多條出邊；3、葉節(jié)點或終節(jié)點，有一條入邊，但沒有出邊。決策樹中每個非葉節(jié)點表示一個特征屬性的測試，每個分支代表這個特征屬性在某個值域上的輸出，而每個葉節(jié)點存放一個類別。使用決策樹進行決策的過程就是從根節(jié)點開始，測試待分類項中相應(yīng)的特征屬性，并按照其值選擇輸出分支，直到到達葉節(jié)點，將葉節(jié)點存放的類別作為決策結(jié)果。

圖 1 決策樹節(jié)點示意圖Fig.1 The nodes in a decision tree

構(gòu)造決策樹的關(guān)鍵步驟就是分裂屬性。分裂屬性就是在某個節(jié)點按照某一特征屬性的不同劃分構(gòu)造不同的分支，其目標(biāo)是讓各個分裂子集中的待分類項屬于同一類別。構(gòu)造決策樹的關(guān)鍵性內(nèi)容是進行屬性選擇度量，屬性選擇度量是一種選擇分裂準(zhǔn)則。屬性選擇度量的算法有很多，一般使用自頂向下遞歸分治法，并采用不回溯的貪心算法，著名的有ID3算法和C4.5算法。

2.1.2 IDID3算法原理

ID3算法的核心思想就是以信息增益度量屬性選擇，選擇分裂后信息增益最大的屬性進行分裂?；靖拍钊缦拢涸O(shè)S為用類別對樣本空間的劃分，則S的熵定義為：。其中表示第i 個類別在整個樣本空間中出現(xiàn)的概率，可以用屬于此類別的樣本數(shù)量除以整個樣本數(shù)量作為估計，m為樣本類別數(shù)。

現(xiàn)假設(shè)樣本空間S按照屬性A進行劃分，則A對S劃分的期望信息為：。 v表示S根據(jù)屬性A進行劃分得到的子類數(shù)，表示第j個子類。信息增益即為：。為了能更清楚地說明ID算法，舉例如下：假設(shè)總共有50個人，20個男人，30個女人。20個男人和30個女人這個總體就是S，男人的比例為20/50=0.4，女人的比例為30/50=0.6，所以Entropy（S） = ? （0.4×log20.4+0.6×log20.6）=0.971?，F(xiàn)在假設(shè)20個男人當(dāng)中有10個單眼皮和10個雙眼皮，30個女人中有9個單眼皮，21個雙眼皮。則這20個男人就是S1，單眼皮男人和雙眼皮男人的比例都是0.5，Entropy（S1） = ? （0.5×log20.5+0.5×log20.5）=1。則這30個女人就是S2，單眼皮女人和雙眼皮女人的比例各是0.3、0.7，Entropy（S2） = ? （0.3×log20.3+0.7×log20.7）=0.881。此時A表示按照眼皮單雙來劃分人這個規(guī)則，則EntropyA （S）=0.4×1+0.6×0.881=0.9286，gain（A） =0.971?0.9286= ? 0.0424。 ID3算法就是在每次需要分裂時，計算每個屬性的增益，然后選擇增益最大的屬性進行分裂。

2.1.3 C4.5算法原理

C4.5算法相比于ID3算法最主要的改進即是分裂屬性的選擇由根據(jù)信息增益變?yōu)樾畔⒃鲆媛?，信息增益率的計算過程如下：

C4.5選擇具有最大信息增益率的屬性作為分裂屬性。C4.5算法產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。因此，選擇決策樹C4.5算法作為模型建立的方法。

3 結(jié)果與討論

對18臺激光打印機360頁樣本進行連通區(qū)域測量、灰度測量、面積測量，對閾值設(shè)置分別為80、117、128、160時，測量所得的29項參數(shù)116組測量數(shù)值應(yīng)用決策樹學(xué)習(xí)算法對其進行分類，訓(xùn)練出的決策樹模型見圖2。

從實驗結(jié)果中可以看出：使用閾值為128的中位灰度值，閾值為80的灰度眾數(shù)值，閾值為117、最小測量面積為1的字塊面積標(biāo)準(zhǔn)差，閾值為80的面積比值，閾值為160、最小測量面積為1的字塊面積標(biāo)準(zhǔn)差，閾值為80的中位灰度值，閾值為80、最小測量面積為1的字塊圓度標(biāo)準(zhǔn)差，閾值為128的對稱分布值，閾值為117的面積比值，閾值為160的中位灰度值，閾值為117、最小測量面積為1的字塊圓度平均值等11組參數(shù)，能夠分類18臺激光打印機的打印樣本，經(jīng)測試集測試分類正確率達100%，且得到的決策樹只有6層，結(jié)構(gòu)簡單，上述11組參數(shù)對于實驗用18臺打印機的分類具有較強相關(guān)性，可以正確區(qū)分本實驗中的9個品牌18種型號共18臺激光打印機360頁打印樣本。18臺不同型號的打印機連續(xù)打印的20頁樣本，雖然在單個參數(shù)上存在數(shù)值交叉的現(xiàn)象，但是通過11組參數(shù)組合可以區(qū)分。如，雖然3號機與5號機在閾值為117、最小測量面積為1的字塊面積標(biāo)準(zhǔn)差中存在數(shù)值交叉（見圖3），但是通過閾值為128的中位灰度值可以區(qū)分（見圖4）；2號機與12號機在閾值為128的中位灰度值中存在數(shù)值交叉（見圖4），但是通過閾值為80、最小測量面積為1的字塊圓度標(biāo)準(zhǔn)差可以區(qū)分（見圖5）。另外，通過上述實驗也發(fā)現(xiàn)在連通區(qū)域測量時，閾值設(shè)定為160，部分樣本超出了其測量的閾值，該樣本無測量值，數(shù)值顯示為0，一旦出現(xiàn)這種情況，則應(yīng)舍棄該參數(shù)值。

圖 2 決策樹模型。（A） 閾值為128的中位灰度值；（B）閾值為80的灰度眾數(shù)值，閾值為117、最小測量面積為1的字塊面積標(biāo)準(zhǔn)差；（C）閾值為80的灰度眾數(shù)值，閾值為80的面積比值，閾值為80的灰度眾數(shù)值，閾值為160、最小測量面積為1的字塊面積標(biāo)準(zhǔn)差；（D） 閾值為80的中位灰度值，閾值為80、最小測量面積為1的字塊圓度標(biāo)準(zhǔn)差，閾值為80、最小測量面積為1的字塊圓度標(biāo)準(zhǔn)差，閾值為128的對稱分布值，閾值為80的中位灰度值，閾值為117的面積比值，閾值為160的中位灰度值；（E） 閾值為128的中位灰度值，閾值為117、最小測量面積為1的字塊圓度平均值，閾值為80的面積比值。Fig.2 Decision tree. （A） gray128： Median Gray Level； （B） gray80： Mode Gray， connect117+1： Stat. area stdev； （C） gray80： Mode Gray，Area80： Area Coverage， gray80： Mode Gray， connect160+1： Stat. area stdev； （D） gray80： Median Gray Level， connect80+1： Stat.roundness stdev， connect80+1： Stat.roundness stdev， gray128： Distribution symmetry， gray80： Median Gray Level， Area117： Area Coverage，gray160： Median Gray Level； （E） gray128： Median Gray Level， connect117+1： Stat.roundness average， Area80： Area Coverage.

本實驗中篩選出的與激光打印機分類相關(guān)性較強的11組參數(shù)是中位灰度值、灰度眾數(shù)值、字塊面積標(biāo)準(zhǔn)差、面積比值、對稱分布值、字塊圓度標(biāo)準(zhǔn)差、字塊圓度平均值等7項參數(shù)在不同閾值下的參數(shù)組合，從參數(shù)所衡量的打印文件特征中可以看出不同激光打印機打印樣本在灰度、面積、圓度、打印墨跡數(shù)量等特征及特征的組合上存在差別，可以用于不同種類激光打印機打印樣本。從決策樹模型分類結(jié)果中可以看出，5號機（惠普P2055d）與6號機（惠普M401dn），9號機（兄弟HL-2250DN）與10號機（兄弟HL-2240D），11號機（理光SP310DN）與12號機（理光SP200），15號機（柯尼卡美能達 MAGICOLOR 1650EN）與16號機（柯尼卡美能達 MAGICOLOR 1700W），17號機（京瓷FS-1040）與18號機（FS-1060 DN）的樣本在接近樹的底層才被區(qū)分開來，說明同品牌相近類型的打印機在主要的分類屬性上具有很強的相關(guān)性。

本實驗通過9個品牌18種型號共18臺激光打印機360頁打印樣本進行實驗研究，發(fā)現(xiàn)不同激光打印機打印樣本在閾值為128的中位灰度值等11組參數(shù)上具有特殊性和相對穩(wěn)定性，通過11組參數(shù)組合可以區(qū)分不同種類激光打印機打印樣本，通過量化方法區(qū)分激光打印機打印樣本具有可行性。

圖 3 閾值為117、最小測量面積為1的字塊面積標(biāo)準(zhǔn)差Fig.3 Stat. Area Stdev threshold of 117 and minimum area of 1pixels

圖 4 閾值為128的中位灰度值Fig.4 Median gray lever threshold of 128

圖 5 閾值為80、最小測量面積為1的字塊圓度標(biāo)準(zhǔn)差Fig.5 Stat. roundness Stdev threshold of 80 and minimum area of1pixels

參考文獻

［1］ 梁政，韓星周，郝紅光. 利用ImageXpress系統(tǒng)灰度特征區(qū)分激光打印復(fù)印一體機的打印及復(fù)印文件初探. 刑事技術(shù)，2013（4）：36-40.

［2］ 韓星周，梁政，郝紅光. 激光連續(xù)打印文件特征變化的實驗探究. 北京：中國人民公安大學(xué)出版社，2013：91-93.

［3］ 王潔，牟小彬，程衛(wèi)國. 噴墨類打印機打印文件量化分析研究初探. 北京：中國人民公安大學(xué)出版社，2013：86-91.

［4］ Tan PN， Steinbach M， Kumar V. Introduction to data mining. New Jersey： Addison Wesley， 2005：150-168.

［5］ Rokach L， Maimon O. Data mining with decision trees. Singapore：World Scientifi c Publishing Company， 2008：77-81.

中圖分類號：DF794.2

文獻標(biāo)識號：A

文章編號：1008-3650（2016）01-0065-05

收稿日期：2015-03-06

基金項目：上海市公安局科研項目（2014002）

作者簡介：牟小彬，高級工程師，碩士，研究方向為文件檢驗。 E-mail： gaomusihuo@163.com

Quantitative Analysis of Black Laser Printing Based on Decision Tree

MU Xiaobin， LI Ruilin， CHENG Weiguo （Shanghai Municipal Public Security Bureau， Shanghai 200083， China）

ABSTRACT：Objective To explore an assay to classify short-term printing samples produced with different laser printers using ImageXaminer and quantitative analysis. Methods 360 pages of short-term printing sample from 18 different laser printers were collected and 116 features， such as area， perimeter， gray scale， were scanned and measured by the ImageXaminer. Samples of different laser printers were input at the resolution of 800dpi and full-page measured by choosing the same-size target region. The corresponding mathematical model was established based on decision tree algorithm C4.5， and the measured values of 116 parameters were analyzed to fi nd out the appropriate ones which had a strong correlation to the classifi cation of different laser printers. Results Short-term printing samples of different laser printers could be correctly classified according to the comprehensive analysis of the following 11 parameters： median gray level threshold of 128， mode gray threshold of 80， Stat. Area Stedv threshold of 117 and the minimum area of 1 pixel， area coverage ratio threshold of 80， Stat. Area Stedv threshold of 160 and the minimum area of 1 pixel， median gray level threshold of 80， Stat. roundness Stdev threshold of 80 and the minimum area of 1 pixel， distribution symmetry threshold of 128， area coverage ratio threshold of 117， median gray level threshold of 160，Stat. roundness Average threshold of 117 and the minimum area of 1 pixel. These 11 parameters have quite strong correlation to the classifi cation of different laser printers. Conclusions It is feasible to make a distinction between short-term printing samples produced with different laser printers by using the quantitative analysis method of the ImageXaminer.

KEY WORDS：document examination； laser printing； quantitative analysis； decision tree