基于人工免疫算法的古籍文本數(shù)字化處理

焦佳琛 ， 包能勝 ， 姜佳華

（1.智能制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室（汕頭大學(xué)）；2.汕頭大學(xué)工學(xué)院機(jī)械工程系，廣東 汕頭 515063）

0 引言

古籍一般是指清王朝滅亡前的文獻(xiàn)，他們是相關(guān)學(xué)者研究中國(guó)古代政治、歷史、文學(xué)等方面的重要資料[1].由于這些紙質(zhì)文獻(xiàn)具有稀少、易破損、易受潮、易蟲蛀等特點(diǎn)，存放單位一般將它們放在特制的房間內(nèi)并限制借閱，不利于古籍傳播和研究.雖然早在1954年中央領(lǐng)導(dǎo)就指示有關(guān)人員整理點(diǎn)校《資治通鑒》[2]，隨后制定了《三至八年（1960-1967）整理和出版古籍的重點(diǎn)規(guī)劃》.但中國(guó)古籍汗牛充棟，還有歷代文人所作的注釋、集解、輯錄、校正、箋證、索引，短期內(nèi)將所有古籍進(jìn)行整理出版并不現(xiàn)實(shí)，所以將古籍?dāng)?shù)字化顯得十分重要.

最早對(duì)中文文獻(xiàn)進(jìn)行數(shù)字化的是美國(guó)聯(lián)機(jī)檢索系統(tǒng)OCLC和RLIN，他們?cè)?978年對(duì)《朱熹大學(xué)章句索引》等書籍建立數(shù)據(jù)庫(kù).1984年臺(tái)灣開發(fā)“瀚典全文檢索系統(tǒng)”，之后香港和大陸也開始了古籍?dāng)?shù)字化的進(jìn)程[3].

數(shù)字化的古籍可以分為圖像、電子文本和混合模式[4].電子文本形式雖然簡(jiǎn)明易讀，但它也省略了大量文字外的信息.例如唐顏真卿的《祭侄贈(zèng)贊善大夫季明文》，其書法上就傾注了大量的情感，這些情感無(wú)法通過(guò)電子文本的形式呈現(xiàn).

目前，古籍?dāng)?shù)字化的方法是掃描或拍照，并進(jìn)行糾偏、拼接、去污、裁切及水印等處理[5].但這種方法也存在著明顯的缺點(diǎn)[5]：（1）文件過(guò)大，一本高清古籍影印件的大小往往有數(shù)個(gè)吉字節(jié)（GB），增加了研究者的儲(chǔ)存成本；（2）由于年代久遠(yuǎn)，古籍的紙張往往泛黃，影響閱讀；（3）因?yàn)榇娣挪划?dāng)，紙張上通常有水漬、蟲蛀等痕跡（如圖1.a）；（4）由于古代紙張較薄，背面的文字會(huì)“透”過(guò)來(lái)，與正面文字重疊（如圖1.b）；（5）由于書法和雕版印刷的特殊性，古籍紙面著墨不均勻.由于以上因素，若對(duì)影印件簡(jiǎn)單地進(jìn)行二值化，會(huì)造成文字不清且存在大量圖像噪聲，影響文件品質(zhì)（如圖2）.

圖1 古籍?dāng)?shù)字化處理典型問(wèn)題

圖2 古籍黑白處理后的典型問(wèn)題

針對(duì)以上問(wèn)題，本文研究了一種基于人工免疫算法的古籍文本數(shù)字化處理方法.該方法通過(guò)模擬免疫學(xué)的模型和原理，采用基于二進(jìn)制編碼的圖像邊緣檢測(cè)算法，追蹤文字邊緣，尋找古籍文本數(shù)字圖像上感興趣的文字或圖片，同時(shí)去除其他不感興趣的部分，舍棄冗余信息.

1 古籍文本圖像前處理

通過(guò)對(duì)圖像進(jìn)行適當(dāng)?shù)那疤幚恚梢酝怀鰣D像中有用的信息，并消除無(wú)用的部分.而處理后的插圖是否保持原狀并不重要，我們只需保留文字即可.

1.1 二值化

在256級(jí)灰度圖像中，0表示黑色，255表示白色.圖像二值化的過(guò)程就是將圖像處理后，只保留黑色和白色，即把圖像中每一個(gè)像素點(diǎn)的值都變?yōu)?或255.由于書本中包含有文字、圖像和其他可以舍棄的信息，若要保留主要信息，可以設(shè)置一個(gè)閾值，當(dāng)灰度值大于閾值時(shí)將其設(shè)置為255，小于閾值時(shí)設(shè)置為0.最大類間方差法（OTSU）是由日本學(xué)者大津展在1979年提出，是一種自適應(yīng)的閾值確定的方法[6].

該算法計(jì)算簡(jiǎn)單，不受圖像亮度和對(duì)比度的影響，在數(shù)字圖像處理上應(yīng)用廣泛.根據(jù)圖像的灰度特性，該算法將圖像分成目標(biāo)和背景兩個(gè)部分.目標(biāo)和背景之間的差別越大，則類間方差越大，同時(shí)意味著錯(cuò)誤分割的概率降低.

對(duì)于圖像L（x，y），大小為M×N，區(qū)分目標(biāo)和背景的閾值為T，目標(biāo)占據(jù)整幅圖像的比例為ω0，平均灰度μ0；背景占據(jù)整幅圖像的比例為ω1，平均灰度為μ1.圖像的總平均灰度記為μ，類間方差記為g.則有：

遍歷所有像素點(diǎn)，取類間方差g最大時(shí)的閾值T.使用OTSU方法對(duì)古籍圖像進(jìn)行目標(biāo)和背景的分離，然后使用差分進(jìn)化方法對(duì)得到的閾值進(jìn)行優(yōu)化[7].

1.2 直方圖均衡化

直方圖是多種空間域處理技術(shù)的基礎(chǔ)，直方圖操作可用于圖像增強(qiáng).直方圖在軟件中計(jì)算簡(jiǎn)單，且具有圖像平移、旋轉(zhuǎn)、縮放不變性等眾多優(yōu)點(diǎn)，而且有助于商用硬件實(shí)現(xiàn)，廣泛地應(yīng)用于圖像處理的各個(gè)領(lǐng)域[8].

一幅數(shù)字圖像中灰度級(jí)rk出現(xiàn)的概率近似為：

其中，MN為圖像的像素大小，灰度為rk的像素個(gè)數(shù)為nk，L是圖像中可能灰度級(jí)的數(shù)量，pr（rk）為直方圖.

則變換函數(shù)的離散形式為

于是，輸入圖像的灰度級(jí)rk映射到輸出圖像sk中.

1.3 對(duì)比度拉伸

圖像的對(duì)比度指的是一幅圖像中明暗區(qū)域最亮的白和最暗的黑之間不同亮度層級(jí)的測(cè)量，即指一幅圖像灰度反差的大小.差異范圍越大代表對(duì)比越大，差異范圍越小代表對(duì)比越小.對(duì)比率越高，所支持的色階越多.

韋伯定律，即感覺(jué)閾值定律，由德國(guó)生理學(xué)家E.H.韋伯研究重量差別感覺(jué)時(shí)發(fā)現(xiàn)的.感覺(jué)的差別閾限與刺激量成正比[9].ΔI表示刺激的增量，I表示原來(lái)刺激值，則：

其中，K為韋伯常數(shù).當(dāng)應(yīng)用到人的視覺(jué)刺激時(shí)，韋伯對(duì)比度定義為：

其中，I為關(guān)注點(diǎn)的亮度，Ib為背景的整體亮度.通過(guò)對(duì)圖像對(duì)比度的拉伸，改變所有像素點(diǎn)的灰度值，可以凸顯圖像中感興趣的區(qū)域并減弱其余部分[10].

本文選取了古籍中的一副原圖，用所述的三種方法進(jìn)行處理，對(duì)比圖如圖3.

圖3 三種前處理方法的結(jié)果比較

2 免疫算法

免疫學(xué)是研究人體免疫系統(tǒng)的科學(xué)，揭示了免疫系統(tǒng)識(shí)別抗原后應(yīng)答并清除的規(guī)律.免疫算法就是模擬免疫學(xué)的模型和原理，用以尋找圖像上的文字，并去除其他不感興趣的部分.

2.1 生物免疫

人類在二千多年前就發(fā)現(xiàn)曾感染并康復(fù)的人會(huì)對(duì)某些傳染病產(chǎn)生抵抗力，稱之為免疫.保證這種人體防御機(jī)制的生理功能便是免疫系統(tǒng)，它用來(lái)區(qū)分“自己”和“非己”，以保證人體健康.免疫系統(tǒng)由免疫器官、免疫細(xì)胞和免疫分子組成，能夠識(shí)別和清除對(duì)人體有害的物質(zhì)（如病原體等外來(lái)抗原、癌變細(xì)胞、凋亡細(xì)胞等）[11].免疫過(guò)程可分為先天免疫和獲得性免疫，先天免疫指機(jī)體先天具有的正常的生理防御功能，對(duì)各種不同的病原微生物和異物的入侵都能做出相應(yīng)的免疫應(yīng)答；獲得性免疫是指人體經(jīng)過(guò)感染或人工預(yù)防接種后而得到的抵抗能力.相關(guān)概念如下：

（1）抗原：是指所有能誘發(fā)機(jī)體免疫應(yīng)答的物質(zhì).它能被淋巴細(xì)胞表面的抗原受體識(shí)別、結(jié)合，活化淋巴細(xì)胞，產(chǎn)生免疫應(yīng)答產(chǎn)物；

（2）抗體：是指機(jī)體由于抗原的刺激而產(chǎn)生的具有保護(hù)作用的蛋白質(zhì)；

（3）淋巴細(xì)胞：主要由T細(xì)胞和B細(xì)胞組成，在免疫過(guò)程中兩者一同協(xié)作，產(chǎn)生抗體；

（4）免疫識(shí)別：區(qū)分“自己”和“非己”；

（5）免疫學(xué)習(xí)：該過(guò)程會(huì)提高免疫細(xì)胞的個(gè)體親和度，擴(kuò)大群體規(guī)模并保存最優(yōu)個(gè)體；

（6）免疫記憶：在免疫識(shí)別后以最優(yōu)抗體的形式保存該抗原的信息，在下次遇到時(shí)快速應(yīng)答；

（7）親和度：是指抗體與抗原之間的匹配程度；

（8）相似度：是指不同抗體間的相似程度.

在生物免疫系統(tǒng)中，免疫應(yīng)答的基本過(guò)程是：當(dāng)抗體與抗原的親和度超過(guò)閾值后，淋巴細(xì)胞識(shí)別抗原，之后淋巴細(xì)胞在協(xié)同刺激分子的參與下，發(fā)生細(xì)胞的活化、增殖、分化，產(chǎn)生效應(yīng)細(xì)胞（如殺傷性T細(xì)胞）、效應(yīng)分子（如抗體、細(xì)胞因子）和記憶細(xì)胞.最后由效應(yīng)細(xì)胞和效應(yīng)分子清除抗原，完成免疫過(guò)程[11].少量親和力高的抗體將轉(zhuǎn)化為記憶細(xì)胞，當(dāng)免疫系統(tǒng)受到相同的抗原入侵時(shí)將會(huì)快速應(yīng)答，即免疫記憶應(yīng)答.使得生物免疫系統(tǒng)具備了高度的自適應(yīng)性[12].

免疫系統(tǒng)有很強(qiáng)的分布性、自治性、多樣性、動(dòng)態(tài)性和魯棒性等特點(diǎn)[13]，為人們解決工程問(wèn)題提供了新方法.人們?cè)趫D像處理、數(shù)據(jù)挖掘、故障診斷等領(lǐng)域中使用了免疫學(xué)的原理和模型，產(chǎn)生了免疫算法.

2.2 免疫算法及其實(shí)現(xiàn)

通過(guò)模擬人體的免疫過(guò)程，誕生了人工免疫算法.免疫系統(tǒng)和人工免疫算法之間有一定的對(duì)應(yīng)，關(guān)系如表1.

表1 免疫系統(tǒng)和免疫算法的對(duì)照關(guān)系[12]

2.2.1 傳統(tǒng)算法

當(dāng)某種抗原成分侵入人體時(shí)，機(jī)體的免疫系統(tǒng)能夠識(shí)別并清除這些異物，使得機(jī)體恢復(fù)正常.將這個(gè)過(guò)程在理論上進(jìn)行抽象，便形成了免疫算法.免疫算法一般分為以下6個(gè)步驟.

步驟一：識(shí)別抗原.將抗原識(shí)別為輸入信息.

步驟二：生成初始抗體群.從記憶細(xì)胞中生成過(guò)去有效的抗體群.從保存了有效的抗體的數(shù)據(jù)庫(kù)中讀取抗體，當(dāng)記憶細(xì)胞不存在時(shí)，通過(guò)隨機(jī)決定抗體遺傳因子來(lái)生成抗體群.

步驟三：計(jì)算親和度.計(jì)算抗原和抗體v之間的親和度axv，不同抗體間的相似度ayv，w.

其中，OPj為所求問(wèn)題的目標(biāo)函數(shù)，l為不同抗體間的距離.

步驟四：分化成記憶細(xì)胞和生存細(xì)胞.計(jì)算所有抗體的濃度，當(dāng)抗體的濃度ρ超過(guò)閾值Tρ時(shí)，將抗體v分化為存儲(chǔ)細(xì)胞m.當(dāng)存儲(chǔ)細(xì)胞的數(shù)量超過(guò)上限M時(shí)，計(jì)算當(dāng)前保存的存儲(chǔ)細(xì)胞與分化出的存儲(chǔ)細(xì)胞的親和度，其中親和度最高的是與分化出的存儲(chǔ)細(xì)胞進(jìn)行交換.與新分化的記憶細(xì)胞具有相同基因的抑制細(xì)胞s被取代，與抑制細(xì)胞親和力超過(guò)Taρ1的抗體被消滅.相應(yīng)的計(jì)算公式如下.

其中，Taρ1表示給定的抗體相似度閾值，N為抗體群體中的抗體總數(shù).

步驟五：促進(jìn)和抑制抗體的產(chǎn)生.根據(jù)式（10）計(jì)算新一代殘留抗體的期望值e.從本代低親和度的抗體中消滅N/2個(gè)抗體.

其中，S是抑制細(xì)胞的總數(shù)，k是預(yù)編碼功率，Taρ2是類似度的閾值.

式（10）表示抗原和抗體的親和度越高，留在新一代的概率就越高.存活細(xì)胞和抗體的親和度越高，濃度越高的抗體留在新一代的概率就越低.

步驟六：產(chǎn)生新抗體.步驟四中被消滅的抗體被新抗體替代，用隨機(jī)數(shù)隨機(jī)決定其遺傳基因，采用交叉變異等算子能夠獲得不同類型的抗體.

2.2.2 改進(jìn)的陽(yáng)性選擇算法

并不是所有的T淋巴細(xì)胞都會(huì)發(fā)育成熟，執(zhí)行免疫任務(wù).未通過(guò)主要組織相容性復(fù)合體（Major Histocompatibility Complex，MHC）基因群審查的T細(xì)胞則會(huì)凋亡.這種選出不合格的未成熟的T淋巴細(xì)胞的過(guò)程稱為陰性選擇.

根據(jù)以上機(jī)理，F(xiàn)orrest等[14]于1994年在計(jì)算機(jī)異常監(jiān)測(cè)領(lǐng)域內(nèi)首次使用陰性選擇算法進(jìn)行變化檢測(cè).算法使用隨機(jī)生成的檢測(cè)器去檢測(cè)“自我”集合，并只保留不能檢測(cè)出“自我”內(nèi)容的檢測(cè)器，最后將這些檢測(cè)器用于異常監(jiān)測(cè).

陽(yáng)性選擇和陰性選擇正好相反.能夠識(shí)別基質(zhì)細(xì)胞表面自身主要組織相容性復(fù)合體MHC的胸腺細(xì)胞發(fā)生陽(yáng)性選擇而存活下來(lái)[15]，對(duì)親和度高的淋巴B細(xì)胞進(jìn)行克隆.陽(yáng)性選擇算法匹配常用二進(jìn)制字符串形式描述，檢測(cè)器采用特征值匹配規(guī)則構(gòu)造[16].

特征值匹配時(shí)，根據(jù)需求將長(zhǎng)度為L(zhǎng)的二進(jìn)制字符串集合S（s1，s2，…，sn）中的si分為m段長(zhǎng)度不等的特征值ej，且所有特征值的并集為空集.如果字符串集合S中的某一段特征值總能夠在另一個(gè)字符串集合M中找到閾值連續(xù)匹配的特征值[17]，則稱兩個(gè)字符串集合匹配成功.

在免疫算法中，“自我”和“非我”檢測(cè)空間是初始檢測(cè)器集合的子集R.檢測(cè)器d和自我集合S進(jìn)行特征值匹配，得到一個(gè)有效檢測(cè)器集R′，則有R′?S，并且S∩Sˉ＝?[14].

基于改進(jìn)的陽(yáng)性選擇算法的邊緣檢測(cè)算法分為以下6個(gè)步驟.

步驟一：隨機(jī)生成多個(gè)檢測(cè)器dm；自定義多個(gè)長(zhǎng)度為L(zhǎng)的字符串集合，組成自我集合S.

步驟二：將每一個(gè)檢測(cè)器dm與自我集合S進(jìn)行特征值匹配.將成功匹配的檢測(cè)器加入有效檢測(cè)器集R′中，并刪除失敗集合.

步驟三：提取待檢測(cè)圖像的非極大值抑制、梯度、最大梯度差三個(gè)特征值；

步驟四：把待檢測(cè)邊緣圖像中的二進(jìn)制串與有效檢測(cè)器集R′進(jìn)行匹配，若匹配成功，則判斷為邊緣點(diǎn)，設(shè)為1；反之則判斷為非邊緣點(diǎn)，設(shè)為0.

步驟五：一段時(shí)間后，將R′中匹配次數(shù)最多的一個(gè)二進(jìn)制串進(jìn)行復(fù)制變異取代父代[19].

步驟六：最后把得到的“0”和“1”轉(zhuǎn)化為邊緣圖像，一個(gè)處理結(jié)果案例如圖4.

圖4 陽(yáng)性選擇算法文字邊緣處理結(jié)果

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

本次算法的驗(yàn)證性實(shí)驗(yàn)所用的古籍是雕版印刷的南唐徐鍇撰寫的《說(shuō)文解字系傳》.該雕版印刷的圖書版式為框20.4 cm*14.6 cm，七行行大字不等，小字雙行二十二字，細(xì)黑口，左右雙邊，單黑魚尾.

3.1 圖像處理對(duì)比

本文選取了該雕版印刷的兩個(gè)典型部位的圖像，應(yīng)用改進(jìn)的陽(yáng)性選擇算法進(jìn)行了處理.圖5左邊圖片為待處理原圖，該圖因?yàn)楣偶垙埦眠h(yuǎn)而出現(xiàn)了強(qiáng)烈的黃色背景，極大影響美觀.圖6左邊圖片為待處理原圖，該圖背景較淡但字體模糊且出現(xiàn)斷點(diǎn)等瑕疵.

圖5 圖像一處理結(jié)果

圖6 圖像二處理結(jié)果

經(jīng)過(guò)本文人工免疫算法的處理，結(jié)果如圖5和圖6的右邊圖片.可以看出，處理后圖片中的文字清晰，保持了原有形狀，且沒(méi)有空心、斷點(diǎn)等問(wèn)題.可以認(rèn)為，人工免疫算法在保證了文字信息的基礎(chǔ)上，兼顧了美學(xué)體驗(yàn).

3.2 文件大小對(duì)比

本文從書中隨機(jī)選取了15頁(yè)內(nèi)容，包括扉頁(yè)，章首頁(yè)和正文內(nèi)容，圖像文件格式為PNG.采用本方法，對(duì)這些圖像分別進(jìn)行了處理，處理前后的原始圖片與處理后的圖片的大小對(duì)比如表2所示.

需要說(shuō)明的是，編號(hào)1的文件為扉頁(yè)，2和5的文件為章首頁(yè).由于處理的圖片中文字?jǐn)?shù)量的不同，導(dǎo)致縮放比差距較大.

假設(shè)圖片中充滿文字，則縮放比平均為1.81%.本次實(shí)驗(yàn)中使用到的《說(shuō)文解字系傳》，原色影印版本的大小為3.41 GB，如果以平均縮放比1.81%計(jì)算，則處理后的全書大小約為61.72 MB，極大的減少了古籍?dāng)?shù)字化儲(chǔ)存空間.

表2 古籍圖像文件處理前后大小比較

4 結(jié)論

本文針對(duì)古籍文件的特殊性，提出使用免疫算法處理圖像，保留文字.該方法得到的文字圖像更加清晰，文件更加小，有利于中文、歷史等相關(guān)學(xué)科工作者的閱讀和存儲(chǔ).具體結(jié)論如下：

（1）處理后的文字圖像沒(méi)有空心，筆畫連續(xù)，保持了文字的原狀.

（2）電子文件縮小50倍以上，極大地節(jié)約了儲(chǔ)存空間.

下一階段，將會(huì)提高算法處理文件的速度和保留文獻(xiàn)上的印章等信息.