高教社杯大學生數學建模競賽區評閱編號（由賽區評閱前進行編號賽區評閱記錄（可供賽區評閱時使用統一編號（由賽區送交前編號評閱編號（ 評閱前進行編號11本文圍繞碎紙片拼接問題，建立了碎紙距離模型、復原TSP模型，并設計了一維碎紙復原算法、二維碎紙復原算法、三維碎紙復原算法等算法，利用實現對問針對問題一，設計了一維碎紙復原算法（4.1.7），12碎紙的像素矩陣，并對其進行二值化處理，然后利用提取碎紙的文字特征，通過字符大小、行距等文字特征構造識別序列，并且利用識別序列的吻合度建立了碎紙距離模型（4.1.4），進而將碎紙復原問題轉化為復原TSP題（4.1.5），并用模擬退火法進行求解，得到了正確的復原圖形及序列（詳見附錄一）。針對問題二，設計了二維碎紙復原算法（見4.2.5首先對附件3和附件4的碎紙圖片進行標準化對化誤的修正后層次特征，利用層次特征對進行初步分類，對于機器不能分類的，通過編制GUI程序提高了人工判別效率，得到相應11類行特征相同的碎紙，進而將問題轉化為11個一維碎紙復原問題并進行求解，得到了正確的復原圖形及序列（詳見附錄二）。針對問題三，設計了三維碎紙復原算法（4.3.2），5的a面與b進行整合，得到416張三維碎紙，同樣對進行標準化、提取層次特征、分類等操作，將問題維度降為一維并進行求解，得到附件5正的正確復原及序列（詳見附錄三）考慮到算法的量化評價問題，本文在模型改進處提出最小干預度算法，即通過計算機識別順序與復原順序的序列逆序數，實現了最小人工干預次數對算法優劣進行刻畫。：碎紙復原算法、TSP、模擬退火法、分類降維、GUI設計一、問題重對于給定的來自同一頁印刷文字文件的碎紙機破碎紙片（僅縱切，建立碎紙片拼接復原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎片數據進34型與算法，并就附件5的碎片數據給出拼接復原結果.二、問題分析本題是研究碎紙復原問題，問題一至三，分別研究一至三維三種不同情況的碎紙復原，本文對問題的解答也是沿著這樣的思維路線，即通過降維，使高維度問題轉化為低維度問題。問題一是一個一維碎紙復原問題，首先從中提取出像素矩陣，并對其進行二值化處理，然后根據附件碎紙均為大小、形狀一致矩形選擇提取其文字特征得到基于文字特TSP問題二是一個二維碎紙復原問題，碎紙經過橫切縱切之后碎片間的文字特征減少，繼續沿用第一問模型求解計算復雜度降呈指數級遞增，計算精度也將下降，考慮分析碎紙片文字行間距、大小等特點提出對應準則模型對碎紙片進行識別分類，運用問題一模型與算法先對每一類內碎紙片進行拼接復原，而后再對得到部分拼接復原圖進行拼接復原，分類、復原過程適當進行人工干預提高復原精度。問題三是一個三維碎紙復原問題，需要在問題二的基礎上考慮碎紙片的正問題。通此外，本題是個實際問題，現實中需要考慮的因素遠遠多于題目本身，如何使模型更加貼近實際，并提供有效的拼接信息是本文的一大，通過查閱大量資料與文獻，3344三、符號說明與模型假設符號說碎片AC碎片A到碎片B碎片BDnTSP模型假假設正打印的頁邊距等格式相假設說假設3.2.1是為了保證問題一中識別序列的有效性，與實際中大多數情況相符。假設3.2.2是為了簡化問題三，當頁邊距等打印格式相同時，正的層次特征會相同，可以進行降維，與實際中大多數情況是相符四、模型的建立與求解一維碎紙復原模圖像的預處般是通過灰度化，將像素值定位為[0,255]區間內，再通過設定閥值，區分空白位置和字體，最后進行二值化。但對于非彩色的，僅需區分空白與非空白兩種情況即可。為了使能夠清晰地描述空白位置與字符位置，首先利用數學軟件對圖像進行預處理。首先將導入，得到對應的像素矩陣，由計算機圖形學相關知識可知，空白位置的像素值 式中，qijPij

通過對每張進行二值化，得到一系列的像素矩陣，可用于圖像的特征提取碎紙特征的提行拼接，如文獻[12，另一類是通過提取碎紙上的文字特征，基于文字特征進行拼接，如文獻[3][4]一維碎紙，是指切割時，僅進行橫或縱的切割，形狀如圖4-1所示。4-1一維碎紙示意圖通過觀察圖4-1和行距等，見圖4-4-2字符的特征步驟一：對進行二值化，文字為白色，空白為黑步驟二：找出所有行距、上空、下空，并標記其為灰色步驟三：找出中所有的字距，并標記其為灰色步驟四：通過行距、上空、下空、字距等特征計算出字符寬度取（代碼見附錄四getLandR.m）.基于文字特征的識別序通過分析漢字與英文字母被分割的情況可以發現，對于每個被切割開的字符，如圖4-3所示，記字符的寬度為C，被分割后的兩部分寬度分別為CRR，而對于沒被切割的字符，依舊保留寬度C。4-3字符分割示意圖基于漢字分割的定義，可構造基于文字特征的識別序列，如圖4-4所示。PAGEPAGE12 4-4識別序列示意圖對于圖4-4中的識別序列，其中無字符位置數值為0，其它數字節點代表對應的字符長度（完整的為C，不完整的為CRR）。碎紙距離的定基于4.1.3識別序列的定義，本文定義碎紙A到碎紙Bd

(LiRiCXi

Xi0或式中，dabA到碎紙BLiB的左識別序列RiA的右識別序列C為字符的寬度Xi為表示序列L或R的第in想狀況下，當兩個識別序列完全吻合時，距離為0（實際情況中，由于二值化，損失了部0TSP問題是數圖論中最著名的問題之一，即“已給一個n個點的完全圖，每條邊都若將每個碎紙看成一個點，由4.1.4距離的定義可知，點與點之間存在距離，可以看出，兩張碎紙如果吻合度低，那對應的距離也大，所以尋找吻合率最高的組合方式，實質就是尋找總距離最小的路徑，也就是尋找一條最佳TSP路徑。4-5TSP將碎紙復原抽象成復原TSP問題，即

minD (LRCX

XS.T.X

式中DTSP路徑的總距

idii1i到碎紙i+1通過求解復原TSP問題，可以得到每個點的順序，即碎紙片的拼接序列，最后利用圖像拼接，得到復原了的紙片。模擬退火模擬退火法是一種通用概率算法，用來在一個大的搜尋空間內尋找問題的最優解，具有能有效地解決NP難問題、避免陷入局部最優、對初值沒有強依賴性等特點，在各領域已獲得了廣泛地應用。算法步驟[5]步驟一:令當前溫度TT0x0，并計算相應的目標函數值E(x0)。步驟二：令T等于冷卻進度表的下一個值Ti步驟三xixjE(xj)，得到EE(xj)E(xi)。步驟四

E0

E0eTiMetropoilsTi

TiLk次擾動和接受過程（LkMarkov步驟六：判斷溫度T是否等于 利用模擬退火法求解求解TSP問題，將一個序列當成一個解，每個解對應一個目標一維碎紙復原算綜上所述，通過一維碎紙復原算法，可以實現一維碎紙的自動復原，相應的算法步驟如下：算法步驟步驟一：提取出碎紙圖像的像素矩陣，并進行二值化處理步驟二：提取出二值化處理后碎紙圖像的文字特征步驟三TSP步驟四：利用模擬退火法求解TSP問題模型求利用 對像素進行分析，得到漢字大小4040（單位：像素），考慮到英文字符的特殊性，受文獻[3]的啟示，將其視為3030（單位：像素）；通過模擬退火法求解TSP問題，取初始溫度為97，停止溫度為3，衰減系數為0.9，鏈長度為10000，利用進行運算，得到結果如表4-1所示.4-1121234567899564738 4-1附表1。二維碎紙復原模對于二維碎紙，本文的定義是切割紙片時，進行橫和縱的切割，形狀如圖4-6所示.4-6二維碎紙片示意圖3411TSP19208碎紙標準化與層次特征提fi式中，fi為像素矩陣的第i行具體做法如圖4-7所示4-7碎紙片的標準化考慮到本文對碎紙進行標準化的方式，對某些字母不能有效地分層，如圖4-8所示.如圖4-9，一些字符會使分層數增加，但是會導致提取層次特征有誤，故應該對這些特殊字符進行修正，即令其中間的空白行也變為黑色。對于標準化后的，其層次特征明顯，可提取出的層次特征，本文通過提取文字層的層次特征對進行分類，提取的步驟如下（程序見附錄四）：提取步驟步驟一：對進行標準化步驟二：對標準化后的進行修步驟三：遍歷標準化后的像素矩陣，記錄每個文字層的起始位置和結束位置；例如圖4-8的，提取的層次特征如圖4-9所示.4-9層次特征提取4.2.3通過層次特征分通過4.2.2的層次特征提取，每張都得到一組對應的層次特征，可利用這些特步驟一：對比每張的特征值，若有3-4個特征值相同，那么兩張歸為一類步驟二：對于無法分類的，記為一個集合步驟三：利用GUI程序，對于無法分類的集合，人為地逐個與已知類別進行對比，三對比程序的設計（代碼見附錄四SingleMatch.m），GUI界面如圖4-10所示.4-10GUI程4.2.5二維碎紙復原算根據4.2.4設定的分類方法，可以將將二維碎紙片復原問題轉化為多個一維碎紙片復原問題，但是由于文字特征只有原本的一小部分，且空白區域占碎紙片大部分比例，導致一維碎紙復原模型復原程度不高，需要對結果進行人工干預，如圖4-11所示.4-11轉化后的一維碎紙復原情況4-11步驟一：對二維碎紙進行標準化；步驟二：提取二步驟三：利用層次特征，進行機器劃分和小部分人工干預，實現分類；步驟四：構造多個一維碎紙問題，并進行求解；步驟五：根據步驟四的結果，進行適當的人工4.2.6模型求解利用4.2.5的碎紙復原算法分別對附件3、附件4為11個一維碎紙復原問題，并利用4.12234567894-3423456789三維碎紙復原模對于三維碎紙，本文的定義是切割紙片時，不僅進行橫和縱的切割，還需區分正面與，其形狀如圖4-12所示.4-12三維碎紙片示意圖與二維碎紙相比，三維碎紙需要區分正，算法復雜度更高三維模型的降假設3.2.2假設了正打印的頁邊距等格式相同，基于此假設，正反兩面的層次特征是相同的，所以進行分類時，可以分為一類，所以問題三可轉換為問題二，只是同樣的，利用4.2.3的分類方式，可以將問題轉化為多個一維碎紙復原問題，并利用一碎紙復原算法進行復原。而關于GUI程序，也需要進行適當修改，使之能同時對比多張（代碼見附錄MultMatch.m），如圖4-13所示.4-13三維碎紙復原算根據4.2.4設定的分類方法，可以將將二維碎紙復原問題轉化為多個一維碎紙復原問題，但是由于文字特征只有原本的一小部分，且空白區域占碎紙大部分比例，導致一維碎紙復原模型復原程度不高，需要對結果進行人工干預，如圖4-14所示.4-14轉化后的一維碎紙復原情況圖4-14中，紅圈區域代表拼接成功的碎紙，由圖可看出，一維碎紙復原模型能將大部步驟一：對三維碎紙進行標準步驟二：提取三維碎紙兩面的層次特征，并進行合并，轉化成二維碎紙復原問題；步驟三：利用層次特征，進行機器劃分和小部分人工干預，實現分類；步驟四：構造多個一維碎紙問題，并進行求步驟五：根據步驟四的結果，進行適當的人工模型求4.3.25的三維碎紙進行復原，得到結果如表4-44-54-45表4-5附件5結果通過三維碎紙復原模型，能比較有效地實現三維碎紙的復原，附件5的復原見模型優

五、模型改進與推本文采用的碎紙復原模型，綜合利用了計算機高速計算能力以及人的文字圖像識別和理解能力，拼接效率比純人工高，拼接準確性也好于純計算機拼接法。二維碎紙復原模型避免了模擬退火法解的長度過長而導致的算法復雜度快速增加，以分類降維，從而簡化問題；在人工干預部分使用GUI程序幫助人工識別，比純粹的人工干預更為高效；模型缺三維碎紙模型基于正打印的頁邊距等格式相同的假設，所以當正打印格式模型改適用彩片的改在4.1中，考慮到只有黑白兩種情況，所以并未指定閥值，而對于彩片的處理，需根據具體情況制定閥值，以便更好地二值化，若需提取更加明顯的，還需進最小干預度算在二維碎紙復原算法和三維碎紙復原算法中都需要適用人工干預，人工干預的次數代表了算法的好壞，本文在此提出一個量化人工干預程度的方式，如圖5-1所示5-1正確序列與機器識別順序由圖5-1所示，記機器識別得到的順序為T{2,1,453}，而正確的順序式G12345，此處定義序列逆序數為最小人工干預次數，即為得到正確序列，需要做2。模型推模擬退火法是是一種通用概率演算法，用來在一個大的搜尋空間內找尋命題的最優解，是解決TSP問題的有效算法，也可以較高的效率求解最大截問題、0-1背包問題、圖問題、調度問題等等碎紙復原模型實質是基于邊緣像素的吻合度的，這種思想同樣適用于音頻、的參考文張欣,卜彥龍,朱良家,周宗 物證復原系統中的碎紙輪廓提取技術研究PatrickButler,PrithwishChakraborty,NarenRamakrishan,TheDeshredder:AVisualyticApproachtoReconstructingShredded s[J].DepartmentofComputerScienceand yticsCenter,VirginiaTech,Blacksburg,VA207-HeiWangChan,EvanGillespie,DelfinoLeong，DesignandImplementationofaPaperDe-shredder.ECE412TermProjectReport.P.2-4December6,2010 在數學建模中的應用[M],：航天航空大學,，數學建模算法與應用[M]，：國防工業，2011，，，， 智能算法30個案例分析[M],：航天航空大學,2011，基于塊匹配和特征點匹配的圖象拼接算法研究[D],，西南交通大學附附錄一1、附2原結1121234567899564738 附錄二3、附4原結22345678923456789附錄三附件5正復原結正 455 附錄四程序代forifa(i)==0&&b(i)==0forforifp000(i,j)==255forifsum(p000(i,:))==mforj=1:mforiffori=1:n-if(temp(i)==1&&temp(i+1)==0)||(temp(i)==0&&temp(i+1)==1)

fori=1:2:nnforifsum(p000(record(i):record(i+1)-1,j))==record(i+1)-record(i);fork=record(i):record(i+1)-1

fori=1:nifp000(i,1)==150forj=1:m-if

fori=1:nifp000(i,m)==150forj=m:-ifp000(i,j-r(i)=m-fori=j- clearp000;forfora=0.98;%衰減系數初始溫tf=3;%停止溫度tt0;%初始化溫度Markov_length= 鏈長amountsize(x,2);%解的長度sol_new=x;%產生新解E_current=inf;%當前解的值E_best=inf;%最佳解的值sol_currrentsol_new;%當前解等于新產生的解sol_best=sol_new;%whiletforrr=1:Markov_lengthind1=0;ind2=0;while(ind1==tmp1=sol_new(ind1);sol_new(ind2)=tmp1;ind1=0;ind2=0;ind3=0;while(ind1==ind2)||(ind1==ind3)...||(ind2==ind3)||(abs(ind1-ind2)==1)ind1=ceil(rand.*amount);tmp1=ind1;tmp2=ind2;tmp3=ind3;ind2=tmp3;ind3=tmp2;ind1=tmp2;ind2=tmp1;ind1=tmp2;ind2=tmp3;ind3=tmp1;ind1=tmp3;ind2=tmp1;ind3=tmp2;ind1=tmp3;ind2=tmp2;ind3=

tmplist1=sol_new((ind1+1):(ind2-1));sol_new((ind1+ind3-ind2+2):ind3)=...fori=1:amount-1ifE_current=E_new;ifE_new<E_bestE_best=E_new;ifrand<exp(-(E_new-E_current)./t)E_current=E_new;sol_new=

t=forifsum(l(:,i))==0forifsol_best(i)==firstfori=sol_best(j)- clearp000;globalstart;globalhave;globalnum;globalstart;globalhave;globalnum;result(1:209)=-(hObject,eventdata,functionvarargout=varargout{1}=gui_State.gui_Callback=if[varargout{1:nargout}] (gui_State,(gui_State,functionun handles.output=hObject;guidata(hObject,[],...ifnargin&&,,','''functionvarargout=gui_Singleton=gui_State= mfilename,'gui_Singleton',gui_Singleton,functionpushbutton1_Callback(hObject,eventdata,handles)globalhave;globalp000;globale;iffori=istart:size(have,2)ifhave(i)==0functionpushbutton2_Callback(hObject,eventdata,handles)globalhave;globale;globalstart;functionpushbutton3_Callback(hObject,eventdata,handles)globalstart;globalhave;globalp000;fori=1:size(have,2)fori=1:size(have,2)ifhave(i)==0functionfunction (hObject,eventdata,handles,handles.output=hObject;guidata(hObject,gui_State.gui_Callback=if[varargout{1:nargout}] (gui_State,(gui_State,[],ifnargin&&,,','''functionvarargout=gui_Sing