基于文字信息的碎紙片拼接復(fù)原算法

魯嘉琪

摘 要： 基于不同碎紙片的文字特征進(jìn)行分析，在合理假設(shè)下開發(fā)了多種算法，這些算法綜合了多向遞推、行列間距檢測(cè)、字符模式識(shí)別與必要時(shí)的人工干預(yù)等多種手段，成功解決了碎紙片的拼接復(fù)原問題。同時(shí)，多種算法相互結(jié)合也有效地降低了錯(cuò)誤拼接的概率，提高了復(fù)原文件方案的穩(wěn)定性。拼接完成后的試驗(yàn)結(jié)果表明該方案的實(shí)際拼接效果非常理想。

關(guān)鍵詞： 碎紙片拼接； 文字信息； 模式識(shí)別； 文字特征分析

中圖分類號(hào)： TN911?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2014）04?0028?04

Algorithm for torn paper restoration based on character information

LU Jia?qi

（China University of Political Science and Law， Beijing 102200， China）

Abstract： The character characteristics of different paper pieces are analyzed in this paper. Several algorithms were deve?

loped under reasonable assumptions， which synthesized multi?directional recursion， detection of space between ranks， character pattern recognition and artificial intervention when necessary， and successfully realized the recovery of torn paper pieces. The combination of various algorithms reduced the probability of error splicing effectively and improve the stability of the recovery file scheme. The experimental results after splicing show that the actual splicing effect of the scheme is very satisfactory.

Keywords： torn paper splicing； character information； pattern recognition； character feature analysis

破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。印刷體文字圖像與一般圖像之間的區(qū)別在于其顏色單調(diào)，圖像連續(xù)性較差，圖像邊緣所包含的信息量較少。因而，處理文字碎片的問題要比處理一般圖像的問題復(fù)雜。但是，文字圖像分析也具有一定的優(yōu)勢(shì)，原因在于文字的排布較為規(guī)整，行列之間的距離較為穩(wěn)定可以對(duì)碎片的大致位置進(jìn)行直接判斷。

常規(guī)文檔碎紙片計(jì)算機(jī)拼接方法一般采用改進(jìn)的模擬退火算法、蟻群算法等，利用碎片邊緣的尖點(diǎn)特征、尖角特征、面積特征等幾何特征[1]，搜索與之匹配的相鄰碎紙片并進(jìn)行拼接，但是這種基于邊界幾何特征的拼接方法并不適用于邊緣形狀相似的碎紙片。羅智中對(duì)這類邊緣相似的碎紙片的拼接，提出了利用文字行方向和表格線方向的算法，這種方法雖然利用了文字碎片中的文字圖像的幾何特征信息[2]，但是沒有文字本身獲取信息，因而還需要借助人工干預(yù)，利用人的文字圖像的識(shí)別能力和理解能力來(lái)實(shí)現(xiàn)拼接。本文針對(duì)分別針對(duì)中文、英文文件碎片設(shè)計(jì)不同拼接復(fù)原算法，并針對(duì)雙面文件開發(fā)了全自動(dòng)拼接算法。由于中文文字的字形字體十分穩(wěn)定，這有利于對(duì)同行的碎片加以聚類分析，縮小上搜索范圍，提高搜索效率。英文字母的形狀是固定的，所以可以直接對(duì)字母進(jìn)行數(shù)字信息提取，形成模塊化的信息庫(kù)，便于進(jìn)行模式識(shí)別。對(duì)于雙面打印文件的拼接問題，可以通過適當(dāng)?shù)霓D(zhuǎn)化。由于雙面所包含的信息多于單面，所以基于單面打印的算法可以在這一問題中形成優(yōu)勢(shì)互補(bǔ)，相互印證，提高算法的可靠性。

1 基于文字特征的碎紙片拼接算法

1.1 中文文件的復(fù)原算法

步驟1：確定應(yīng)拼接在文件第一列和最后一列的碎片。首先對(duì)每一個(gè)文字碎片的圖像數(shù)字化提取，將文字圖像轉(zhuǎn)化為灰度圖像矩陣。灰度圖像矩陣元素的取值范圍通常為[[0，255]]，“0”表示純黑色，“255”表示純白色，中間的數(shù)字從小到大表示由黑到白色。通過逐列檢測(cè)每張碎片灰度矩陣的左邊緣列向量。首先檢測(cè)第一列向量，篩選出灰度值全為255的一個(gè)碎片的備選集合。然后在這個(gè)集合中，檢驗(yàn)每個(gè)碎片第二列的列向量，考察其是否為“全白”。若是，則保留在備選集合中，否則將其拋棄。這樣可得到原始文件中位于第一列的碎片集合。同理，利用碎片右端的白色區(qū)域篩選出位于最后一列的碎片集合。

步驟2：排列第一列和最后一列碎片的順序。根據(jù)已經(jīng)確定的第一列和最后一列的可能集合，可以確定第一列文字碎片的排列順序。由于中文不存在大小寫的情況，文字的行間距和字高都是固定的。碎片長(zhǎng)度也是固定的。為此，可以根據(jù)第一列可能的碎片中的每一個(gè)文字碎片上下方留白部分以及文字部分的高度，確定任意文字碎片上下方連接的文字碎片。排序算法如下：

記固定的字高和行間距所占用的像素分別為[h]和[l]，對(duì)任意文字碎片[i]，從文字碎片圖像的最上方開始掃描；當(dāng)碎片是以空白時(shí)，計(jì)算空白行的高度，記作[bi]，則與第[i]個(gè)文字碎片圖像上方相連接的碎片的下方也是留白的，且留白部分的高度為[l-bi]；當(dāng)碎片[i]上方是以文字開始時(shí)，同理求出文字行高度[wi]，那么上方連接的碎片下方的文字部分高度為[h-wi]。由得到的碎片上方連接碎片的留白或者文字部分的高度，在得到的第一列文字碎片集合中找到符合上述高度條件的文字碎片，即為與碎片[i]上方連接的文字碎片。以此類推，便得到所排在有第一列所有文字碎片的連接順序。字和行高示意圖如圖1所示。

圖1 字高和行高示意圖

依照同樣的方法，檢測(cè)文字圖像最右側(cè)留白的碎片，得到的就是位于最后一列的文字碎片的集合，再用同樣的方法確定最后一列文字碎片的排列順序。

步驟3：用雙向掃描投影法篩選出屬于同一行的所有文字碎片。首先，考慮單向光照射時(shí)的投影，設(shè)想有一束光線從左側(cè)平行地射向文字碎片。由于所有的文字碎片都是由文字和空白兩個(gè)部分組成，當(dāng)光線射向文字碎片時(shí)，文字部分會(huì)阻礙光線通過而形成陰影，空白部分光線可以通過故不會(huì)形成陰影，如圖2所示。如果在文字碎片的平行方向放上一個(gè)屏，則可以在屏上形成光影交錯(cuò)的圖像。用“1”表示光線通過時(shí)出現(xiàn)陰影的點(diǎn)，所有陰影點(diǎn)的集合就可以代表文字部分；用“0”表示光線可以通過的點(diǎn)，那么這些點(diǎn)的集合就可以代表碎片的空白部分。由此，得到的0?1向量就是包含文字碎片信息的投影向量。用左側(cè)光投射所有文字碎片，得到所有文字碎片的投影特征向量。

然后，以步驟一中得到的位于第一列和最后一列文字碎片的投影特征向量為基準(zhǔn)，雙向掃描位于其他列的文字碎片。由于位于不同行的文字碎片的投影向量不同，位于同一行的文字碎片投影向量相同，在一定誤差下不同行。

圖2 光投影法示意圖

根據(jù)投影聚類的算法步驟是：

首先，求出所有碎片的投影特征向量。將第一列的元素的投影特征向量作為其所在行的投影特征向量，也就是聚類標(biāo)準(zhǔn)。然后一次為基準(zhǔn)，遍歷其余所有碎片，度量每個(gè)碎片的特征向量與聚類標(biāo)準(zhǔn)之間的歐式距離。在預(yù)先設(shè)定的閾值下篩選歐式距離小于閾值的碎片，得到每一行可能的碎片組合。最后，以最右側(cè)一列的元素為基準(zhǔn)重復(fù)上述過程。并將兩次所得的碎片集合并起來(lái)。

篩選位于同一行的文字碎片的原理是：求出除第一列和最后一列剩余的的每一個(gè)投影向量與任意給定文字碎片的投影向量的距離，根據(jù)觀察所得數(shù)據(jù)，規(guī)定兩個(gè)投影向量之間的距離小于臨界值[ρ]時(shí)，該投影向量與給定的文字碎片位于同一行。以位于第1列第[i]個(gè)文字碎片的投影向量[xi1]為例，對(duì)于任意文字碎片的投影向量[yjk]，[xi1]和[yjk]位于同一行的條件是：

[xi1-yjk<ρ]

需要進(jìn)行雙向掃描的原因是：當(dāng)以第1列第[i]行文字碎片的投影向量為基準(zhǔn)進(jìn)行掃描時(shí)，位于段首的文字碎片的上方會(huì)留白，導(dǎo)致與所在行的其他碎片匹配時(shí)會(huì)較大的偏差。

以圖3的文字碎片為例，兩個(gè)文字碎片位于同一行，但二者投影向量的距離之差大于[ρ]，這時(shí)因?yàn)樽髠?cè)的碎片位于段首空格處的下方，有一段留白。為了避免由段首空格造成的誤差，在掃描第1列第[i]行的同時(shí)，掃描最后一列第[i]行文字碎片的投影向量為基準(zhǔn)掃描，由此得到雙向掃描的投影向量的集合，取二者的并集，就是可能所有位于第[i]行的文字碎片的集合。

步驟4：從第一行第一個(gè)元素開始依次向右遞推第一行元素。搜索的方法是：在步驟2中所得的第一行碎紙片的集合[H1]中，讓按照定義的距離函數(shù)以此求得[h1]中所有元素與[a11]，取其中距離最小的碎紙片作為與[a11]匹配的第一行第二列的元素[a12]。設(shè)定停止搜索的原則如下：當(dāng)檢測(cè)到灰度矩陣最右側(cè)灰度列向量全為255，停止搜索并返回最后一個(gè)元素[a1i]。在拼接過程中返回的元素[a1i]，就是需要人工干預(yù)的步驟。

圖3 雙向掃描原理示意圖

步驟5：采用人工干預(yù)的方式確定步驟3中的待定元素[a1i]。人工干預(yù)的方法是：求得碎紙片[a1i-1]留白處的寬度[u1i]，又因?yàn)槊恳恍械淖珠g距[d]是固定的，故可以碎紙片[a1i]留白部分的寬度為[d-u1i]，按照此寬度人工搜索待定元素[a1i]。繼續(xù)搜索，停止原則步驟4所述直到確定第一行的所有元素的排列。

步驟6：對(duì)其他行執(zhí)行上述算法，即可完成全圖的拼接工作。

其流程示意圖如圖4所示。

圖4 中文文件拼接算法流程圖

1.2 英文文件的復(fù)原算法

英文文件的復(fù)原方法和中文文件的上述方法有所不同。原因在于：第一，英文文章中有大小寫的區(qū)分，大小寫的不同會(huì)影響每一行的投影特征向量，使得投影聚類法的聚類效果不佳。第二，在中文文件碎片中，絕大多數(shù)“死循環(huán)”是出現(xiàn)在碎片結(jié)尾有空白的地方。然而，在英文文件的碎片中，遞推中經(jīng)常出現(xiàn)的死循環(huán)，多是由于某個(gè)字母被拆分開以后，殘留在接縫處的信息非常少而造成的，并非是空白造成。

考慮到英文的特點(diǎn)是有固定的26個(gè)字母。如果建立一套模式識(shí)別算法，將遞推工具箱得出的結(jié)果與字母進(jìn)行模式對(duì)比和識(shí)別，就可以提高拼接結(jié)果的可信度。從而在很大程度上解決遞推算法的“死循環(huán)”問題。為此，開發(fā)了模式識(shí)別的方法來(lái)解決這個(gè)問題。模式識(shí)別的方法如下：

首先，英文字母在區(qū)分大小寫的情況下共有（26×2）個(gè)。這些字母在文件中重復(fù)的時(shí)候，其對(duì)應(yīng)的灰度矩陣是不變的。從碎片中可以提取出文章中出現(xiàn)的每個(gè)完整字母及大小寫的灰度矩陣，并記錄下來(lái)。稱這些灰度矩陣為字母矩陣。模式識(shí)別的過程就是針對(duì)某個(gè)碎片[i]，在一定的誤差要求下，將26×2個(gè)字母矩陣（部分為空矩陣，因?yàn)樵闹袥]有出現(xiàn)）逐一拿來(lái)對(duì)碎片進(jìn)行掃描。掃描分析的依據(jù)是字母矩陣與碎片灰度矩陣之間的重合部分。每一個(gè)字母矩陣掃描后會(huì)返回一個(gè)最佳重合部分和重合位點(diǎn)。如果這個(gè)重合部分與該字母矩陣的面積之比達(dá)到一定水平（例如0.95），那么就認(rèn)為在這個(gè)碎片中找到了這個(gè)對(duì)應(yīng)的字母。把所有通過誤差要求篩選的結(jié)果視為模式識(shí)別在碎片中發(fā)現(xiàn)的字母。值得注意的是，雖然在不同的誤差要求下，每一個(gè)碎片的識(shí)別結(jié)果所對(duì)應(yīng)的元素不同，但是在同一誤差要求下，一個(gè)碎片的識(shí)別結(jié)果是穩(wěn)定的。

為此，當(dāng)需要判斷兩個(gè)碎片的匹配是否可靠時(shí)，只需要對(duì)這兩個(gè)碎片[i]，[j]分別進(jìn)行模式識(shí)別，并記錄模式識(shí)別得到的個(gè)數(shù)[ki]，[kj]。然后再對(duì)拼好的碎片整體進(jìn)行模式識(shí)別。如果遞推中遇到的“死循環(huán)”是由于邊緣的空白造成的，此時(shí)整體的模式識(shí)別個(gè)數(shù)[kij]就恰等于[ki+kj]。否則，如果“死循環(huán)”是由于某個(gè)英文字母被分開成兩部分造成的，那么拼好之后，整體的模式識(shí)別結(jié)果就會(huì)比原先各自識(shí)別的結(jié)果要多。

由此得到英文文件復(fù)原的半自動(dòng)算法：

（1） 從每一行的第一列元素出發(fā)，使用“遞推工具箱”中的“向右遞推工具包”進(jìn)行遞推。從每一行的最后一列元素出發(fā)，使用“向左遞推工具包”逐一向左遞推。對(duì)每次遞推的結(jié)果進(jìn)行模式識(shí)別檢驗(yàn)。

（2） 如果模式識(shí)別檢驗(yàn)通過，則回到遞推工具箱繼續(xù)進(jìn)行遞推。

（3） 若模式識(shí)別檢驗(yàn)未通過，則進(jìn)行人工干預(yù)（仿照中文文件的做法）。

1.3 基于正反面信息的全自動(dòng)化算法

在前述問題中，需要人工干涉的時(shí)點(diǎn)都是由于碰到了空白區(qū)域相接的死循環(huán)或是殘缺字段的錯(cuò)解。由于對(duì)任意一個(gè)給定碎片的一面，其相反面信息是一一對(duì)應(yīng)可確定的，本文利用雙面文件的這個(gè)特點(diǎn)設(shè)計(jì)算法解決上述問題，步驟如下：

（1） 用擠壓空白算法確定第一列元素。從每一行的第一列元素出發(fā)，使用“遞推工具箱”中的“向右遞推工具包”進(jìn)行遞推。對(duì)每次遞推的結(jié)果進(jìn)行空白區(qū)域檢測(cè)和模式識(shí)別檢驗(yàn)。

（2） 如果檢驗(yàn)均通過，則回到遞推工具箱繼續(xù)進(jìn)行遞推。

（3） 若任意檢驗(yàn)未通過，記當(dāng)前碎片為i，通過單個(gè)碎片正反面一一對(duì)應(yīng)關(guān)系確定其相對(duì)應(yīng)面，記載該信息的碎片為j。通過遞推工具箱中的向左遞推工具搜索j的左側(cè)鄰接碎片，記為j-1。

（4） 通過單個(gè)碎片正反面一一對(duì)應(yīng)關(guān)系確定碎片j-1的相對(duì)應(yīng)面，記載此信息的碎片為k。則根據(jù)文件的正反面對(duì)應(yīng)關(guān)系可知：碎片k記為i+1，此碎片便是綜合正反面信息惟一確定的正確鄰接碎片。此處實(shí)現(xiàn)的示意圖如圖6所示。

圖5 拼接前后的模式識(shí)別示意圖

圖6 基于正反雙面信息的文件碎片拼接

通過上述算法，綜合正反面信息，可在免去人工干涉過程的同時(shí)成功避免空白字段死循環(huán)或殘缺字段錯(cuò)解，并成功搜索到下一個(gè)鄰接碎片，實(shí)現(xiàn)了碎片拼接復(fù)原的全自動(dòng)化。

2 拼接實(shí)驗(yàn)

本文根據(jù)上述半自動(dòng)拼接算法研制了相應(yīng)Matlab程序，并對(duì)一實(shí)際的中英文的文字碎紙片進(jìn)行了拼接試驗(yàn)，拼接結(jié)果圖像。可見，拼接結(jié)果是十分理想的。

3 結(jié) 論

本文的模型選用灰度矩陣的列向量的歐氏距離作為核心的目標(biāo)函數(shù)，基于這種目標(biāo)函數(shù)的優(yōu)化恰好可以使得拼接問題得到解決。針對(duì)不同種類、特點(diǎn)的具體問題，開發(fā)了靈活多變的工具箱，有助于多種算法的相互組合成大程序，使得算法在不同問題上的可移植性大大增強(qiáng)。使用工具箱建立算法的缺點(diǎn)是，對(duì)于不同的大型算法架構(gòu)，要通過修改工具箱的接口才能實(shí)現(xiàn)有效對(duì)接。對(duì)碎紙片拼接問題，開發(fā)了遞推程序包，采用人工干預(yù)和模塊識(shí)別的方法進(jìn)行碎片的匹配。但是，為了讓篩選匹配對(duì)的過程更加智能化，具有記憶性并具有更好的魯棒性。

參考文獻(xiàn)

[1] 何鵬飛，周宗譚，胡德文.基于蟻群算法的碎紙拼接[J].計(jì)算機(jī)工程與科學(xué)，2011（7）：67?73.

[2] 羅智中.基于文字特征的文檔碎紙片半自動(dòng)拼接[J].計(jì)算機(jī)工程與應(yīng)用，2012（5）：207?210.

[3] 沈艷，劉麗娜，鞠憲龍.基于CMAC神經(jīng)網(wǎng)絡(luò)的手寫體文字識(shí)別技術(shù)[J].數(shù)字技術(shù)與應(yīng)用，2011（2）：67?70.

[4] 茹少峰，周明全.基于輪廓線匹配的2?D碎片拼接研究[J].計(jì)算機(jī)應(yīng)用與軟件，2008（3）：83?85.

[5] 方靜.基于特征點(diǎn)的圖像拼接算法優(yōu)缺點(diǎn)比較[J].電腦知識(shí)與技術(shù)，2013（3）：1645?1647.

[6] 趙毅力，武仲科，張雁，等.基于圖結(jié)構(gòu)的全景圖自動(dòng)識(shí)別與拼接方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2013（6）：2067?2070.

[7] 曾仲杰，潘晴，徐如意，等.基于字符切割拼接的字段式液晶數(shù)字識(shí)別[J].計(jì)算機(jī)工程與應(yīng)用，2013（12）：110?113.

[8] BAKER S， MATTHEWS I. Lucas?Kanade 20 years on： a unifying framework part 1： the quantity approximated， the warp update rule， and the gradient descent approximation [J]. International Journal of Computer Vision， 2004， 56（3）： 221?255.

[9] RAV?ACHA， A， PRITCH， Y.， LISCHINSKI， D， et al. Dynamosaics： video mosaics with non?chronological time [C]// Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Diego， CA： IEEE， 2005： 58?65.

[10] FREEMAN W T， JONES T R， PASZTOR E C. Example?based super?resolution [J]. IEEE Computer Graphics and Applications， 2002， 22（2）： 56?65.

[11] MIKOLAJCZYK K. A comparison of affine region detectors [J]. International Journal of Computer Vision， 2005， 65（1/2）： 43?72.

為此，當(dāng)需要判斷兩個(gè)碎片的匹配是否可靠時(shí)，只需要對(duì)這兩個(gè)碎片[i]，[j]分別進(jìn)行模式識(shí)別，并記錄模式識(shí)別得到的個(gè)數(shù)[ki]，[kj]。然后再對(duì)拼好的碎片整體進(jìn)行模式識(shí)別。如果遞推中遇到的“死循環(huán)”是由于邊緣的空白造成的，此時(shí)整體的模式識(shí)別個(gè)數(shù)[kij]就恰等于[ki+kj]。否則，如果“死循環(huán)”是由于某個(gè)英文字母被分開成兩部分造成的，那么拼好之后，整體的模式識(shí)別結(jié)果就會(huì)比原先各自識(shí)別的結(jié)果要多。

由此得到英文文件復(fù)原的半自動(dòng)算法：

（1） 從每一行的第一列元素出發(fā)，使用“遞推工具箱”中的“向右遞推工具包”進(jìn)行遞推。從每一行的最后一列元素出發(fā)，使用“向左遞推工具包”逐一向左遞推。對(duì)每次遞推的結(jié)果進(jìn)行模式識(shí)別檢驗(yàn)。

（2） 如果模式識(shí)別檢驗(yàn)通過，則回到遞推工具箱繼續(xù)進(jìn)行遞推。

（3） 若模式識(shí)別檢驗(yàn)未通過，則進(jìn)行人工干預(yù)（仿照中文文件的做法）。

1.3 基于正反面信息的全自動(dòng)化算法

在前述問題中，需要人工干涉的時(shí)點(diǎn)都是由于碰到了空白區(qū)域相接的死循環(huán)或是殘缺字段的錯(cuò)解。由于對(duì)任意一個(gè)給定碎片的一面，其相反面信息是一一對(duì)應(yīng)可確定的，本文利用雙面文件的這個(gè)特點(diǎn)設(shè)計(jì)算法解決上述問題，步驟如下：

（1） 用擠壓空白算法確定第一列元素。從每一行的第一列元素出發(fā)，使用“遞推工具箱”中的“向右遞推工具包”進(jìn)行遞推。對(duì)每次遞推的結(jié)果進(jìn)行空白區(qū)域檢測(cè)和模式識(shí)別檢驗(yàn)。

（2） 如果檢驗(yàn)均通過，則回到遞推工具箱繼續(xù)進(jìn)行遞推。

（3） 若任意檢驗(yàn)未通過，記當(dāng)前碎片為i，通過單個(gè)碎片正反面一一對(duì)應(yīng)關(guān)系確定其相對(duì)應(yīng)面，記載該信息的碎片為j。通過遞推工具箱中的向左遞推工具搜索j的左側(cè)鄰接碎片，記為j-1。

（4） 通過單個(gè)碎片正反面一一對(duì)應(yīng)關(guān)系確定碎片j-1的相對(duì)應(yīng)面，記載此信息的碎片為k。則根據(jù)文件的正反面對(duì)應(yīng)關(guān)系可知：碎片k記為i+1，此碎片便是綜合正反面信息惟一確定的正確鄰接碎片。此處實(shí)現(xiàn)的示意圖如圖6所示。

圖5 拼接前后的模式識(shí)別示意圖

圖6 基于正反雙面信息的文件碎片拼接

通過上述算法，綜合正反面信息，可在免去人工干涉過程的同時(shí)成功避免空白字段死循環(huán)或殘缺字段錯(cuò)解，并成功搜索到下一個(gè)鄰接碎片，實(shí)現(xiàn)了碎片拼接復(fù)原的全自動(dòng)化。

2 拼接實(shí)驗(yàn)

本文根據(jù)上述半自動(dòng)拼接算法研制了相應(yīng)Matlab程序，并對(duì)一實(shí)際的中英文的文字碎紙片進(jìn)行了拼接試驗(yàn)，拼接結(jié)果圖像?？梢?，拼接結(jié)果是十分理想的。

3 結(jié) 論

本文的模型選用灰度矩陣的列向量的歐氏距離作為核心的目標(biāo)函數(shù)，基于這種目標(biāo)函數(shù)的優(yōu)化恰好可以使得拼接問題得到解決。針對(duì)不同種類、特點(diǎn)的具體問題，開發(fā)了靈活多變的工具箱，有助于多種算法的相互組合成大程序，使得算法在不同問題上的可移植性大大增強(qiáng)。使用工具箱建立算法的缺點(diǎn)是，對(duì)于不同的大型算法架構(gòu)，要通過修改工具箱的接口才能實(shí)現(xiàn)有效對(duì)接。對(duì)碎紙片拼接問題，開發(fā)了遞推程序包，采用人工干預(yù)和模塊識(shí)別的方法進(jìn)行碎片的匹配。但是，為了讓篩選匹配對(duì)的過程更加智能化，具有記憶性并具有更好的魯棒性。

參考文獻(xiàn)

[1] 何鵬飛，周宗譚，胡德文.基于蟻群算法的碎紙拼接[J].計(jì)算機(jī)工程與科學(xué)，2011（7）：67?73.

[2] 羅智中.基于文字特征的文檔碎紙片半自動(dòng)拼接[J].計(jì)算機(jī)工程與應(yīng)用，2012（5）：207?210.

[3] 沈艷，劉麗娜，鞠憲龍.基于CMAC神經(jīng)網(wǎng)絡(luò)的手寫體文字識(shí)別技術(shù)[J].數(shù)字技術(shù)與應(yīng)用，2011（2）：67?70.

[4] 茹少峰，周明全.基于輪廓線匹配的2?D碎片拼接研究[J].計(jì)算機(jī)應(yīng)用與軟件，2008（3）：83?85.

[5] 方靜.基于特征點(diǎn)的圖像拼接算法優(yōu)缺點(diǎn)比較[J].電腦知識(shí)與技術(shù)，2013（3）：1645?1647.

[6] 趙毅力，武仲科，張雁，等.基于圖結(jié)構(gòu)的全景圖自動(dòng)識(shí)別與拼接方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2013（6）：2067?2070.

[7] 曾仲杰，潘晴，徐如意，等.基于字符切割拼接的字段式液晶數(shù)字識(shí)別[J].計(jì)算機(jī)工程與應(yīng)用，2013（12）：110?113.

[8] BAKER S， MATTHEWS I. Lucas?Kanade 20 years on： a unifying framework part 1： the quantity approximated， the warp update rule， and the gradient descent approximation [J]. International Journal of Computer Vision， 2004， 56（3）： 221?255.

[9] RAV?ACHA， A， PRITCH， Y.， LISCHINSKI， D， et al. Dynamosaics： video mosaics with non?chronological time [C]// Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Diego， CA： IEEE， 2005： 58?65.

[10] FREEMAN W T， JONES T R， PASZTOR E C. Example?based super?resolution [J]. IEEE Computer Graphics and Applications， 2002， 22（2）： 56?65.

[11] MIKOLAJCZYK K. A comparison of affine region detectors [J]. International Journal of Computer Vision， 2005， 65（1/2）： 43?72.

為此，當(dāng)需要判斷兩個(gè)碎片的匹配是否可靠時(shí)，只需要對(duì)這兩個(gè)碎片[i]，[j]分別進(jìn)行模式識(shí)別，并記錄模式識(shí)別得到的個(gè)數(shù)[ki]，[kj]。然后再對(duì)拼好的碎片整體進(jìn)行模式識(shí)別。如果遞推中遇到的“死循環(huán)”是由于邊緣的空白造成的，此時(shí)整體的模式識(shí)別個(gè)數(shù)[kij]就恰等于[ki+kj]。否則，如果“死循環(huán)”是由于某個(gè)英文字母被分開成兩部分造成的，那么拼好之后，整體的模式識(shí)別結(jié)果就會(huì)比原先各自識(shí)別的結(jié)果要多。

由此得到英文文件復(fù)原的半自動(dòng)算法：

（1） 從每一行的第一列元素出發(fā)，使用“遞推工具箱”中的“向右遞推工具包”進(jìn)行遞推。從每一行的最后一列元素出發(fā)，使用“向左遞推工具包”逐一向左遞推。對(duì)每次遞推的結(jié)果進(jìn)行模式識(shí)別檢驗(yàn)。

（2） 如果模式識(shí)別檢驗(yàn)通過，則回到遞推工具箱繼續(xù)進(jìn)行遞推。

（3） 若模式識(shí)別檢驗(yàn)未通過，則進(jìn)行人工干預(yù)（仿照中文文件的做法）。

1.3 基于正反面信息的全自動(dòng)化算法

在前述問題中，需要人工干涉的時(shí)點(diǎn)都是由于碰到了空白區(qū)域相接的死循環(huán)或是殘缺字段的錯(cuò)解。由于對(duì)任意一個(gè)給定碎片的一面，其相反面信息是一一對(duì)應(yīng)可確定的，本文利用雙面文件的這個(gè)特點(diǎn)設(shè)計(jì)算法解決上述問題，步驟如下：

（1） 用擠壓空白算法確定第一列元素。從每一行的第一列元素出發(fā)，使用“遞推工具箱”中的“向右遞推工具包”進(jìn)行遞推。對(duì)每次遞推的結(jié)果進(jìn)行空白區(qū)域檢測(cè)和模式識(shí)別檢驗(yàn)。

（2） 如果檢驗(yàn)均通過，則回到遞推工具箱繼續(xù)進(jìn)行遞推。

（3） 若任意檢驗(yàn)未通過，記當(dāng)前碎片為i，通過單個(gè)碎片正反面一一對(duì)應(yīng)關(guān)系確定其相對(duì)應(yīng)面，記載該信息的碎片為j。通過遞推工具箱中的向左遞推工具搜索j的左側(cè)鄰接碎片，記為j-1。

（4） 通過單個(gè)碎片正反面一一對(duì)應(yīng)關(guān)系確定碎片j-1的相對(duì)應(yīng)面，記載此信息的碎片為k。則根據(jù)文件的正反面對(duì)應(yīng)關(guān)系可知：碎片k記為i+1，此碎片便是綜合正反面信息惟一確定的正確鄰接碎片。此處實(shí)現(xiàn)的示意圖如圖6所示。

圖5 拼接前后的模式識(shí)別示意圖

圖6 基于正反雙面信息的文件碎片拼接

通過上述算法，綜合正反面信息，可在免去人工干涉過程的同時(shí)成功避免空白字段死循環(huán)或殘缺字段錯(cuò)解，并成功搜索到下一個(gè)鄰接碎片，實(shí)現(xiàn)了碎片拼接復(fù)原的全自動(dòng)化。

2 拼接實(shí)驗(yàn)

本文根據(jù)上述半自動(dòng)拼接算法研制了相應(yīng)Matlab程序，并對(duì)一實(shí)際的中英文的文字碎紙片進(jìn)行了拼接試驗(yàn)，拼接結(jié)果圖像。可見，拼接結(jié)果是十分理想的。

3 結(jié) 論

本文的模型選用灰度矩陣的列向量的歐氏距離作為核心的目標(biāo)函數(shù)，基于這種目標(biāo)函數(shù)的優(yōu)化恰好可以使得拼接問題得到解決。針對(duì)不同種類、特點(diǎn)的具體問題，開發(fā)了靈活多變的工具箱，有助于多種算法的相互組合成大程序，使得算法在不同問題上的可移植性大大增強(qiáng)。使用工具箱建立算法的缺點(diǎn)是，對(duì)于不同的大型算法架構(gòu)，要通過修改工具箱的接口才能實(shí)現(xiàn)有效對(duì)接。對(duì)碎紙片拼接問題，開發(fā)了遞推程序包，采用人工干預(yù)和模塊識(shí)別的方法進(jìn)行碎片的匹配。但是，為了讓篩選匹配對(duì)的過程更加智能化，具有記憶性并具有更好的魯棒性。

參考文獻(xiàn)

[1] 何鵬飛，周宗譚，胡德文.基于蟻群算法的碎紙拼接[J].計(jì)算機(jī)工程與科學(xué)，2011（7）：67?73.

[2] 羅智中.基于文字特征的文檔碎紙片半自動(dòng)拼接[J].計(jì)算機(jī)工程與應(yīng)用，2012（5）：207?210.

[3] 沈艷，劉麗娜，鞠憲龍.基于CMAC神經(jīng)網(wǎng)絡(luò)的手寫體文字識(shí)別技術(shù)[J].數(shù)字技術(shù)與應(yīng)用，2011（2）：67?70.

[4] 茹少峰，周明全.基于輪廓線匹配的2?D碎片拼接研究[J].計(jì)算機(jī)應(yīng)用與軟件，2008（3）：83?85.

[5] 方靜.基于特征點(diǎn)的圖像拼接算法優(yōu)缺點(diǎn)比較[J].電腦知識(shí)與技術(shù)，2013（3）：1645?1647.

[6] 趙毅力，武仲科，張雁，等.基于圖結(jié)構(gòu)的全景圖自動(dòng)識(shí)別與拼接方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2013（6）：2067?2070.

[7] 曾仲杰，潘晴，徐如意，等.基于字符切割拼接的字段式液晶數(shù)字識(shí)別[J].計(jì)算機(jī)工程與應(yīng)用，2013（12）：110?113.

[8] BAKER S， MATTHEWS I. Lucas?Kanade 20 years on： a unifying framework part 1： the quantity approximated， the warp update rule， and the gradient descent approximation [J]. International Journal of Computer Vision， 2004， 56（3）： 221?255.

[9] RAV?ACHA， A， PRITCH， Y.， LISCHINSKI， D， et al. Dynamosaics： video mosaics with non?chronological time [C]// Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Diego， CA： IEEE， 2005： 58?65.

[10] FREEMAN W T， JONES T R， PASZTOR E C. Example?based super?resolution [J]. IEEE Computer Graphics and Applications， 2002， 22（2）： 56?65.

[11] MIKOLAJCZYK K. A comparison of affine region detectors [J]. International Journal of Computer Vision， 2005， 65（1/2）： 43?72.