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

焦佳琛 ， 包能勝 ， 姜佳華

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

0 引言

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

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

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

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

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

圖2 古籍黑白處理后的典型問題

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

1 古籍文本圖像前處理

通過對圖像進行適當(dāng)?shù)那疤幚?，可以突出圖像中有用的信息，并消除無用的部分.而處理后的插圖是否保持原狀并不重要，我們只需保留文字即可.

1.1 二值化

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

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

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

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

1.2 直方圖均衡化

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

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

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

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

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

1.3 對比度拉伸

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

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

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

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

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

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

2 免疫算法

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

2.1 生物免疫

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1 傳統(tǒng)算法

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

步驟一：識別抗原.將抗原識別為輸入信息.

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

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

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

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

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

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

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

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

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

2.2.2 改進的陽性選擇算法

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

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

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

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

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

基于改進的陽性選擇算法的邊緣檢測算法分為以下6個步驟.

步驟一：隨機生成多個檢測器dm；自定義多個長度為L的字符串集合，組成自我集合S.

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

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

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

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

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

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

3 實驗結(jié)果

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

3.1 圖像處理對比

本文選取了該雕版印刷的兩個典型部位的圖像，應(yīng)用改進的陽性選擇算法進行了處理.圖5左邊圖片為待處理原圖，該圖因為古籍紙張久遠而出現(xiàn)了強烈的黃色背景，極大影響美觀.圖6左邊圖片為待處理原圖，該圖背景較淡但字體模糊且出現(xiàn)斷點等瑕疵.

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

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

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

3.2 文件大小對比

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

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

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

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

4 結(jié)論

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

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

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

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