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

焦佳琛 ， 包能勝 ， 姜佳華

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

0 引言

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

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

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

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

圖1 古籍數字化處理典型問題

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

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

1 古籍文本圖像前處理

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

1.1 二值化

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

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

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

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

1.2 直方圖均衡化

直方圖是多種空間域處理技術的基礎，直方圖操作可用于圖像增強.直方圖在軟件中計算簡單，且具有圖像平移、旋轉、縮放不變性等眾多優點，而且有助于商用硬件實現，廣泛地應用于圖像處理的各個領域[8].

一幅數字圖像中灰度級rk出現的概率近似為：

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

則變換函數的離散形式為

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

1.3 對比度拉伸

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

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

其中，K為韋伯常數.當應用到人的視覺刺激時，韋伯對比度定義為：

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

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

圖3 三種前處理方法的結果比較

2 免疫算法

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

2.1 生物免疫

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

（1）抗原：是指所有能誘發機體免疫應答的物質.它能被淋巴細胞表面的抗原受體識別、結合，活化淋巴細胞，產生免疫應答產物；

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

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

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

（5）免疫學習：該過程會提高免疫細胞的個體親和度，擴大群體規模并保存最優個體；

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

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

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

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

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

2.2 免疫算法及其實現

通過模擬人體的免疫過程，誕生了人工免疫算法.免疫系統和人工免疫算法之間有一定的對應，關系如表1.

表1 免疫系統和免疫算法的對照關系[12]

2.2.1 傳統算法

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

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

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

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

其中，OPj為所求問題的目標函數，l為不同抗體間的距離.

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

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

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

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

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

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

2.2.2 改進的陽性選擇算法

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

根據以上機理，Forrest等[14]于1994年在計算機異常監測領域內首次使用陰性選擇算法進行變化檢測.算法使用隨機生成的檢測器去檢測“自我”集合，并只保留不能檢測出“自我”內容的檢測器，最后將這些檢測器用于異常監測.

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

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

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

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

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

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

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

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

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

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

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

3 實驗結果

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

3.1 圖像處理對比

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

圖5 圖像一處理結果

圖6 圖像二處理結果

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

3.2 文件大小對比

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

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

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

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

4 結論

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

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

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

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