[[380911]]

國際上碎紙恢復還原相關案例

案例1：德國情報機構(gòu)“斯塔西”文件恢復工程，試圖尋找一種非人工干預的新技術，可以在5年內(nèi)，將那些在德國統(tǒng)一前夕被前東德情報機構(gòu)撕成6億多塊碎紙片的絕密文件(手工恢復要400年)進行還原。[1]其中應標的德國弗勞恩霍得研究院設計科技公司(Fraunhofer Institute for Design Technology)宣布，已經(jīng)開發(fā)出一種名為“E-Puzzler”的先進儀器，專門用于完成還原工作。該儀器能夠精確識別紙質(zhì)碎片的特征并將它們重組，還原文件的內(nèi)容高達70%。弗勞恩霍得研究院稱，如果德國政府批準“E-Puzzler”正式投入使用，那么完成全部工作的時間將縮短至5年，平均每年耗資700萬英鎊。

案例2：美國國防部高級研究計劃局(DARPA)曾表示，軍方常在戰(zhàn)場上收集到撕碎的文件殘片，但恢復文件原樣卻是一件望而生畏的艱巨任務，需要大量人工干預，效率極低，而有價值重要情報通常都是有時限的。2011年10月29日，DARPA組織了一場碎紙復原挑戰(zhàn)賽，旨在尋找到高效的算法，對碎紙機處理后的碎紙屑進行復原。全美9000支隊伍參與角逐，最終由來自舊金山的三名程序員組成的名為“All Your Shreds Are Belong To U.S.”參賽隊伍獲勝。其解決方案是：基于計算機視覺、圖形學、紙張碎片的邊緣性狀等特征，設計出自動搜尋到最可能匹配的紙張碎片的仿真算法，同時對可能的碎片對進行人工篩選。然而考慮到實際問題的復雜性以及安全保密管理要求的規(guī)范性，此種方案并未能夠真正投入軍方使用。

圖1：DARPA碎紙復原挑戰(zhàn)賽競賽題和復原圖

碎紙恢復還原研究現(xiàn)狀及研究進展

傳統(tǒng)上，恢復還原工作大部分都是由人工半自動方式完成，準確率較高，但效率很低。隨著計算機技術的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術，以提高恢復還原效率。雖然國內(nèi)外對這項工作進行了一些研究，但由于碎紙自動修復技術應用背景的特殊性，目前公開的可以參考研究資料并不多，提出的解決方法主要有兩種：一是基于輪廓的拼接[2,3];二是基于內(nèi)容的拼接[4,5]。其中，前者的研究較多一些?；谳喞乃槠詣悠唇臃椒?，可分為兩個步驟：局部形狀匹配分析和全局恢復重建(目前大部分研究都是以第一步為主)。

針對局部形狀分析研究，碎片通常被表示為其輪廓曲線的形式，以輪廓曲線的方法進行局部形狀匹配分析。Wolfson H[6]提出了一種基于弧長-累積轉(zhuǎn)角圖分析(Arclength Versus Total Turning Angle Graph)的形狀匹配方法來解決工業(yè)中工件自動裝配和識別的問題，這是一種通過串匹配的方式來尋找最大公共子段的方法。為了解決大規(guī)模文物碎片的修復問題，Leit?o H C等人[7]給出了一種基于多尺度的二維碎片拼接方法，該方法通過對輪廓采樣點的曲率串進行多尺度分析，利用動態(tài)規(guī)劃技術對匹配對進行精化處理。布朗大學的Kimia B等學者[8]提出了一種基于彈性匹配的碎片自動拼接算法，該方法可以提高匹配的效率，但對雙對應曲線的采樣分布有較強的依賴性。

對于全局恢復重建方法，朱良家、周宗潭和胡德文[9]提出了一種實現(xiàn)全局一致性最大的松弛法全局匹配方法。松弛法通過局部輪廓匹配產(chǎn)生的候選匹配，對不同碎片之間在空間上的約束關系來剔除部分不合理匹配，保留在全局意義下更優(yōu)的匹配，并取得了很好的效果。何鵬飛，周宗潭，胡德文[10]提出基于蟻群優(yōu)化(ACO)的全局匹配算法，其采用基于ψ-s分析的局部輪廓匹配方法，利用多Agent間接通信和直接利用變化媒介質(zhì)，在ACO算法的框架下將碎片全局匹配問題看作是一個求解整體且沒有矛盾的最小拼接代價的優(yōu)化問題。

碎紙恢復還原基本原理

通常來說，碎片恢復還原工作主要分為以下三個步驟：

1.對紙質(zhì)碎片進行預處理，即通過特征檢測提取等一系列圖像預處理過程，將紙質(zhì)碎片數(shù)字化。

2.圖像碎片匹配，即通過各種匹配算法模型找出相互匹配的圖像碎片。

3.圖像碎片的拼合，將步驟2中找到的相互匹配的圖像碎片拼合在一起得到最終的正確結(jié)果。

文獻10主要是對條狀及粒狀碎紙機碎紙的拼接復原問題進行分析、建模，并討論單面及雙面碎紙片復原的問題。本文結(jié)合文獻10的建模方法對上述三個步驟進行簡要概述。

預處理包括特征提取、圖像掃描、圖像分割等技術手段。特征提取的關鍵技術是紙輪廓提取，其直接影響著碎紙拼接結(jié)果的精度和效率。利用碎紙輪廓的形狀特征，通過輪廓信息尋找輪廓形狀的相似性進行局部形狀匹配，再逐步完成全局的恢復重建。針對圖像掃描技術的應用，文獻10利用matlab軟件對碎紙片進行了雙面掃描，根據(jù)像素值提取0-1矩陣(0代表有字部分，1代表空白部分)。通過紙張像素分析，將至少有一面全為非0的紙張?zhí)暨x出來，放入單面打印紙張;其余的紙片為雙面打印。此外，對于圖像分割的預處理技術，文獻2提出了一種基于Level Set方法的圖像分割算法，之后再對提取出的輪廓進行鏈碼提取操作，根據(jù)紙片的大小，設定閾值，過濾掉鏈碼面積。小于閾值的區(qū)域，即所得到的鏈碼就是我們要提取的輪廓信息部分。(水平集方法是一種描述曲線以曲率相關的速度演化的有效方法，在醫(yī)學圖像處理、自然現(xiàn)象的模擬以及計算機視覺等領域得到了廣泛的應用。)

國內(nèi)外研究者對于圖像碎片復原方法的研究主要集中在步驟2——圖像碎片匹配算法模型的研究上。文獻10在完成數(shù)據(jù)0-1矩陣提取的前提下，分別建立了三種模型以適應不同類型的紙質(zhì)碎片拼接，包括條狀單面打印碎紙片的拼接模型、條狀雙面打印碎紙片的拼接模型及針對粒裝正反面打印碎紙片的拼接模型(聚類模型)。其中前兩種類型的圖像碎片匹配模型流程圖分別如圖2、圖3所示。第三種模型則是基于粒裝雙面拼接技術，其應用了聚類模型來衡量矩陣相關性，將強相關矩陣對應的圖像碎片劃分成一類，之后再利用模型二進一步實現(xiàn)拼接。

對于雙面碎紙的情況，文獻10定義了能夠拼接在一起的條件，條件1、2滿足其一，即可拼接成功：

條件1：第i張碎紙片a面的右邊界與第j張碎紙片a面的左邊界拼接成功，且第i張碎紙片b面的左邊界與第j張碎紙片b面的右邊界拼接成功;

條件2：第i張碎紙片a面的右邊界與第j張碎紙片b面的左邊界拼接成功，且第i張碎紙片b面的右邊界與第j張碎紙片a面的左邊界拼接成功。

圖2條狀單面打印碎紙片的拼接模型，其算法核心步驟為Step3，計算左右邊界歐式距離為公式(1);Ai代表第i張碎紙片的左邊界像素矩陣，Bj代表第j張碎紙片的右邊界像素矩陣。圖3條狀雙面打印碎紙片的拼接模型定義了碎紙片的a、b雙面，其中Ari代表第i張碎紙片a面右邊界對應的0-1矩陣;Ali代表第i張碎紙片a面左邊界對應的0-1矩陣;Bri代表第i張碎紙片b面右邊界對應的0-1矩陣;Bli代表第i張碎紙片b面左邊界對應的0-1矩陣;Jij，Lij，Mij，Nij為兩張碎紙片相應邊界的差值矩陣;pij，qij分別代表a~a面拼接的匹配度和b~b面拼接的匹配度;表示A的2-范數(shù)。

歐式距離計算公式：

紙張碎片相應邊界的差值矩陣公式：

兩兩碎紙片的匹配度計算公式：

 

圖2：條狀單面打印碎紙片的拼接模

圖3：條狀雙面打印碎紙片的拼接模型

在匹配算法模型中，較為創(chuàng)新的一種策略是基于群智能優(yōu)化的全局匹配算法來實現(xiàn)圖像匹配[11,12]。群智能優(yōu)化算法是一種離散優(yōu)化問題的元啟發(fā)式算法，其利用生物種群行為優(yōu)化機制來完成對問題的求解。通過優(yōu)化的搜索學習策略將碎紙拼接匹配問題轉(zhuǎn)換成優(yōu)化問題，模擬種群生物的進化機制來不斷迭代，最終尋找到碎紙對匹配的最優(yōu)解。

在碎片還原恢復的最后階段，是將相互匹配的圖像拼接起來，恢復圖像原貌。在此階段，有幾點值得注意的是，考慮到會存在遺失碎片的可能以及相應的虛擬重建等問題，圖像碎片的拼合還需確保兩兩匹配碎片間匹配邊界拼合的嚴密性。[13]同時，由于碎片在數(shù)字化過程中的不同位置，導致了各個碎片與自身原始位置產(chǎn)生了角度變化，即部分碎片的局部坐標系也產(chǎn)生了不同，對于在拼合前的相互匹配的兩兩碎片，就需要根據(jù)共有的曲線或直線段的不同角度，將它們轉(zhuǎn)化到同一個坐標系中。

思考與建議

縱觀目前國內(nèi)外碎紙標準規(guī)范情況，美國在碎紙方面的標準有《NSA/CSS Specification 02-01，High Security Paper Shredder》，其要求碎紙顆粒寬度不大于5mm，碎紙顆粒的面積不大于5mm2;德國標準《DIN 63399》代替了原來的《DIN 32757》標準，新的標準定義了七種安全等級，其中最高等級P-7對應的建議如：考慮采用最高安全預防措施的情況的帶有非常機密數(shù)據(jù)的數(shù)據(jù)載體，材料顆粒表面5mm2，對于整齊顆粒條寬1mm;國內(nèi)碎紙一級標準應滿足碎紙顆粒達到2mm*1mm的紙質(zhì)載體銷毀要求，以確保紙質(zhì)及其同行載體銷毀的安全性。此外，對于一般辦公室使用的碎紙機碎紙后的顆粒尺寸也能達到2mm*0.8mm，碎紙機桶一般能盛放粉碎后的A4紙1000張，一張A4紙張按2mm*1mm標準粉碎后產(chǎn)生碎紙顆粒31185個。

因此，無論是從粉碎顆粒的規(guī)格大小還是顆粒粉碎數(shù)量來看，對于有相似性候選顆粒進行計算機碎紙恢復模型分析的復雜度是呈指數(shù)級增長的。綜上所述，從目前碎紙拼接恢復還原技術的研究趨勢分析，結(jié)合國家秘密載體銷毀安全保密要求，針對涉密紙張粉碎銷毀提出以下幾點安全性相關建議：

1、紙張安全銷毀設備的研制亟需滿足自主可控的信息化建設要求。以國產(chǎn)化軟硬件等安全可靠的支撐環(huán)境為依托，研制符合系統(tǒng)建設以及分級保護要求的紙張安全銷毀設備，確保設備全生命周期中具備有效可控的安全防護措施以及運維管理措施。

2、明確載體銷毀分級標準規(guī)范要求，確保涉密載體銷毀過程安全可控，安全評估載體銷毀中存在的失泄密風險。建議參照國外碎紙標準，對不同密級涉密載體以及定密等中間過程產(chǎn)生的涉密載體按照分級銷毀技術要求進行銷毀，防止因粉碎不徹底而導致可能通過拼接恢復還原出信息。

3、在粉碎過程中，嚴格執(zhí)行安全保密管理措施，流程化人工干預方式以及干預時間點。結(jié)合碎紙拼接還原技術，目前仍需依賴人工干預手段進行恢復，那么反觀紙質(zhì)粉碎銷毀過程，人工干預問題對安全保密有著重要的影響。

4、從現(xiàn)實情況來看，許多碎紙自動拼接模型的仿真實驗數(shù)據(jù)庫和實際情報處理的大規(guī)模碎紙數(shù)據(jù)量相比差距甚遠，綜合考慮碎紙顆粒被掃描的速度和拼接候選等因素，實際利用碎紙自動拼接還原技術進行大規(guī)模碎紙顆粒還原恢復還存在一定難度。

參考文獻

[1] 春風, 麥吉爾. 前東德情報機構(gòu)被撕碎的16000袋絕密文件將修復[J]. 蘭臺世界月刊, 2009(23):58-59.

[2] 張欣, 卜彥龍, 朱良家,等. 物證復原系統(tǒng)中的碎紙輪廓提取技術研究[J]. 計算機仿真, 2006, 23(11):184-187.

[3] 賈海燕, 朱良家, 周宗潭,等. 一種碎紙自動拼接中的形狀匹配方法[J]. 計算機仿真, 2006, 23(11):180-183.

[4] 金明婭, 孫丹蕾, 趙艷,等. 單面英文碎紙片的拼接復原及算法實現(xiàn)[J]. 延安大學學報(自然科學版), 2015, 34(1):14-18.

[5] 陳黎黎, 國紅軍. 基于文檔內(nèi)容的碎紙拼接技術[J]. 衡水學院學報, 2014(4):34-37.

[6] Wolfson H. On Curve Matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990, 12(5):483-489.

[7] Leit?o H C D G, Stolfi J. A Multiscale Method for the Reassembly of Two-Dimensional Fragmented Objects[M]. IEEE Computer Society, 2002.

[8] Mcbride J C, Kimia B. Archaeological Fragment Reconstruction Using Curve-Matching[C]// Computer Vision and Pattern Recognition Workshop, 2003. CVPRW '03. Conference on. IEEE, 2003.

[9] Zhu L, Zhou Z, Hu D. Globally consistent reconstruction of ripped-up documents.[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2007, 30(1):1-13.

[10] 王晨, 曾騫. 關于碎紙機中碎紙片拼接復原的研究[J]. 大眾科技, 2014(3):15-17.

[11] 何鵬飛, 周宗潭, 胡德文. 基于蟻群優(yōu)化算法的碎紙拼接[J]. 計算機工程與科學, 2011, 33(7):67-73.

[12] 張亮, ZhangLiang. 基于聚類優(yōu)化模型的碎紙自動拼接方法研究[J]. 計算機應用與軟件, 2015, 32(12):218-221.

[13] 廖敏瑜, 謝睿誠, 余聲宇. 碎紙片自動拼接復原[J]. 汕頭大學學報(自然科學版), 2018(1).