2013年9月B題數(shù)模論文

碎紙片的拼接復(fù)原摘要關(guān)鍵詞：?jiǎn)栴}重述破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上的接復(fù)原工作需由人工完成，雖然準(zhǔn)確率較高，但效率很低。特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時(shí)間內(nèi)完成任務(wù)。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們?cè)噲D開發(fā)碎紙片的自動(dòng)拼接技術(shù)，以提高拼接復(fù)原效率。本題要求討論以下問(wèn)題：1.對(duì)于給定的來(lái)自同一頁(yè)印刷文字文件的碎紙機(jī)破碎紙片（僅縱切），建立碎紙片拼接復(fù)原模型和算法，并針對(duì)附件1、附件2給出的中、英文各一頁(yè)文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過(guò)程需要人工干預(yù)，寫出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。復(fù)原結(jié)果以圖片形式及表格形式表達(dá)。2.對(duì)于碎紙機(jī)既縱切又橫切的情形，要求我們?cè)O(shè)計(jì)拼接復(fù)原模型和算法，并針對(duì)附件3、附件4給出的中、英文各一頁(yè)文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過(guò)程需要人工干預(yù)，寫出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。復(fù)原結(jié)果表達(dá)要求同上。3.上述所給碎片數(shù)據(jù)均為單面打印文件。但是，從現(xiàn)實(shí)情形出發(fā)，還可能有雙面打印文件。附件5給出了一頁(yè)英文印刷文字雙面打印文件的碎片數(shù)據(jù)。我們需要嘗試設(shè)計(jì)相應(yīng)的碎紙片拼接復(fù)原模型與算法，并就附件5的碎片數(shù)據(jù)給出拼接復(fù)原結(jié)果，結(jié)果表達(dá)要求同上。問(wèn)題分析本題需要解決的三個(gè)問(wèn)題是層層遞進(jìn)、逐步深入的。（1）單面打印、僅縱切碎片的復(fù)原分析第一問(wèn)復(fù)原對(duì)象為單面打印、僅縱切的規(guī)則矩形碎片，由于很難提取到足夠的差異化幾何特征，故無(wú)法像不規(guī)則碎片那樣利用碎片角點(diǎn)、曲率、形狀等幾何特征進(jìn)行復(fù)原。考慮從數(shù)字圖像處理的角度出發(fā)，在碎片邊緣，根據(jù)碎片內(nèi)容、以像素為處理對(duì)象，進(jìn)行碎片特征信息的提取。首先，將附件給出的灰度圖二值化，得到對(duì)應(yīng)的二值圖。進(jìn)而提取碎片左、右兩側(cè)邊緣灰度值，則每張圖片可以得到兩個(gè)特征列向量。將這些特征向量?jī)蓛杀容^，計(jì)算匹配度，則把匹配度最大的兩個(gè)碎片進(jìn)行配對(duì)。如此反復(fù)，可將19個(gè)碎片全部拼接完成。解決思路如下圖所示：圖一問(wèn)題一解決思路（2）單面打印、既縱切又橫切碎片的復(fù)原分析第二問(wèn)復(fù)原對(duì)象為單面打印、既縱切又橫切的碎片。據(jù)此特點(diǎn)，考慮先拼接出最左邊第一列碎片，接下來(lái)從第一行開始，逐行向下拼接。鑒于第二問(wèn)碎片數(shù)量及特征維度較第一問(wèn)有所增加，可以預(yù)計(jì)，當(dāng)碎片數(shù)量增大到一定程度時(shí)，對(duì)同一碎片，問(wèn)題一模型代碼將可能返回不止一個(gè)匹配程度較高的碎片。這些得到的高匹配碎片組成一個(gè)高匹配碎片集。在該碎片集中，有且僅有唯一的碎片與已有碎片正確匹配。為了從高匹配碎片集中篩選出唯一正確的匹配碎片，此時(shí)考慮加入人工干預(yù)。解決思路如下圖所示：圖二問(wèn)題二解決思路（3）雙面打印、既縱切又橫切碎片的復(fù)原分析第三問(wèn)復(fù)原對(duì)象為雙面打印的、既縱切又橫切的碎片。文檔的雙面打印使碎片數(shù)量在第二問(wèn)的基礎(chǔ)上又增加了一倍。根據(jù)前面分析可知，在第二問(wèn)已經(jīng)出現(xiàn)一塊目標(biāo)碎片對(duì)應(yīng)多塊高度匹配碎片的可能性，則在第三問(wèn)中，這種可能性將大大增加。這就需要考慮設(shè)置區(qū)分度更大的匹配準(zhǔn)則。如果鄰接的兩碎片正反兩面都有文字，那么在非常逼近切割線位置處，正反兩面的邊緣像素吻合度將非常高，則與切割線距離值相等的兩側(cè)灰度值之差的平方越小，則此差平方沿切割線方向的累積和最小的碎片，即為所求的最優(yōu)匹配碎片。解決思路如下圖所示：圖三問(wèn)題三解決思路問(wèn)題假設(shè)假設(shè)所給碎片全部為規(guī)則的理想矩形。假設(shè)不同碎片圖像間不存在任何重疊部分。假設(shè)文檔圖像不存在任何傾斜、黑邊（點(diǎn)）、畸變或殘缺。假設(shè)符號(hào)說(shuō)明符號(hào)說(shuō)明模型建立與求解5.1問(wèn)題一的模型建立與求解5.1.1縱切碎紙片的拼接復(fù)原模型建立假設(shè)本題所給碎紙片均為碎紙機(jī)均縱向均勻切割成的規(guī)則矩形，則圖像均為對(duì)齊狀態(tài)，可直接進(jìn)行特征提取。除文檔邊緣圖像外，每張圖像的左、右兩側(cè)均為切割線，則圖像左、右兩側(cè)的邊緣像素（即切割線兩側(cè)的像素）是我們感興趣的部分。邊緣像素灰度匹配程度最大的兩幅圖像即為相鄰。邊緣灰度匹配法原理數(shù)字圖像可看成由像素點(diǎn)組成的矩陣，每個(gè)像素點(diǎn)的值為0—255間的任意數(shù)值。將數(shù)字圖像二值化處理后，所有像素點(diǎn)值為0或1。圖像左（右）邊緣的像素點(diǎn)值可認(rèn)為一組列向量，向量的行數(shù)與碎片像素行數(shù)相同，則每個(gè)碎片對(duì)應(yīng)左、右兩組列向量。我們稱這些向量為“邊緣特征向量”。任取一個(gè)碎片的其中一個(gè)向量作為模板向量，逐次比較該模板向量與其余所有碎片向量間的笛卡爾距離。兩組向量的笛卡爾距離由下式計(jì)算：d其中，n為碎片個(gè)數(shù)，d為笛卡爾距離，a、b為兩特征向量的對(duì)應(yīng)位置元素。由上式可知，使得笛卡爾距離最大的向量所對(duì)應(yīng)的碎片與模板碎片相鄰，其中切割線由兩組列向量形成。邊緣特征向量的確定設(shè)碎片個(gè)數(shù)為m，為每個(gè)碎片i建立左（left）、右（right）兩個(gè)用于匹配的邊緣特征向量Ail和A尋找匹配碎片假設(shè)其中的一個(gè)碎片為A，其左側(cè)的某個(gè)元素Ai，j與另外一塊碎片B的右側(cè)的相對(duì)應(yīng)的元素BiSUM=把所得到j(luò)個(gè)值分別平方后進(jìn)行加運(yùn)算。利用MIN函數(shù)求出其中的最小值，賦值給一個(gè)新建數(shù)組Ca，b，其中a5.1.2縱切碎紙片的拼接復(fù)原模型的求解原始圖像最左側(cè)碎紙片的確定（求解過(guò)程均采用附件一中的碎片圖像）假設(shè)原始圖像最左側(cè)碎紙片的左邊像素灰度值為A(i，j)，從附件一中找出A(i，1)=1的碎紙片，其在附件中的標(biāo)號(hào)為8，從而可以確定在原始文檔中碎紙片8為第一列。碎紙片的融合復(fù)原以碎紙片8為參考列，根據(jù)最優(yōu)匹配原則，假設(shè)其右側(cè)邊緣處灰度值為1的像素坐標(biāo)為，與其匹配的行匹配鏈的坐標(biāo)為，利用公式可得到碎紙片8與其它碎紙片的距離分別為845、629、1227、2289、3009、4301、761、2890、192、867、6534、239、2801、52、4530、2303、4308、1208，顯然，碎紙片8與碎紙片14的距離最短，從而可以確定，在原始文檔中碎紙片14為第二列。根據(jù)上述方法，可以確定，所有碎紙片在原始文檔中從第1列到19列的順序依次為：8→14→12→15→3→10→2→16→1→4→5→9→13→18→1→7→17→0→6。5.2問(wèn)題二的模型建立與求解5.2.1縱橫切碎片拼接復(fù)原模型的建立灰度圖像二值化二值圖像就是指只有兩個(gè)灰度級(jí)的圖像，二值圖像具有存儲(chǔ)空間小，處理速度快，可以方便地對(duì)圖像進(jìn)行布爾邏輯運(yùn)算等特點(diǎn)。更重要的是，在二值圖像的基礎(chǔ)上，還可以進(jìn)一步對(duì)圖像處理，獲得該圖像的一些幾何特征或者其他更多特征。 圖像在二值化操作前要對(duì)圖像進(jìn)行處理，因此在圖像進(jìn)行處理后，我們?cè)佾@取圖像的直方圖以幫助選取閾值。整個(gè)流程如下所示：

讀取圖像→灰度圖像→圖像增強(qiáng)→圖像直方圖→二值化處理圖像二值化是圖像數(shù)據(jù)預(yù)處理的重要技術(shù)，如果二值化過(guò)程中閾值選取不當(dāng)會(huì)損失原圖像的許多有用信息。圖像二值化處理的方法包括全局閾值法、局部閾值法，本文將采用全局閾值法進(jìn)行圖像的處理?；叶葓D像二值化處理的matlab程序：I=imread('Fig.jpg');

figure(1)

imshow(I)

J=find(I<150);

I(J)=0;

J=find(I>=150);

I(J)=255;

title('圖像二值化(域值為150)');

figure(2)

imshow(I)

clc;

I=imread('Fig3.24.jpg');

bw=im2bw(I,0.5);

figure(3);

imshow(bw)

計(jì)算兩碎片的上下間距對(duì)于邊緣相同碎紙片的拼接,理想的計(jì)算機(jī)拼接過(guò)程應(yīng)與人工拼接過(guò)程類似，即拼接時(shí)要判斷碎紙片內(nèi)的字跡斷線或碎片內(nèi)的文字內(nèi)容是否匹配。利用現(xiàn)有技術(shù)，可以獲取碎片文字所在行的幾何特征信息，比如文字行的行高、文字行的間距等信息，碎片復(fù)原時(shí)可利用這些信息進(jìn)行拼接。由于文檔的文字行方向和文檔邊緣平行，如果碎片內(nèi)的文字行方向在碎片邊緣斷裂，那么與它相鄰的碎紙片在邊緣處一應(yīng)有相同高度、相同間距的文字行，憑此特征可以很容易從大量碎片中挑選出符合文字內(nèi)容拼接的碎片。首先假設(shè)碎片像素高度為，每行的像素寬度保存在數(shù)組，內(nèi)，每行的空白點(diǎn)數(shù)保存在數(shù)組，內(nèi)，總的文字圖像像素高度設(shè)為0，則文字行高和可按下述算法計(jì)算：（1）0，表示從碎片最低點(diǎn)開始從上往下掃描。（2），判斷>否，如果大于，結(jié)束，否則轉(zhuǎn)（3）。（3）判斷<20否，也即判斷該行碎片寬度是否小于20個(gè)像素寬度、如果小于，轉(zhuǎn)2，否則轉(zhuǎn)（4）。（4）判斷—<5否，也即判斷該行白點(diǎn)個(gè)數(shù)與該行像素點(diǎn)寬度的差是否在5范圍內(nèi)，小于5，表示該行是空白行，轉(zhuǎn)（5），否則表示不是空白行，轉(zhuǎn)（2）。（5）記下該行的序號(hào)，尋找下一個(gè)空白行號(hào),判斷是否存在，如果存在，轉(zhuǎn)（6），否則表示掃描到最高點(diǎn)，掃描過(guò)程結(jié)束。（6）判斷—>10否，即要求文字塊圖像高度應(yīng)大于某個(gè)最小值，這里10，如果不作此限制，那么表格線也可能被認(rèn)為是文字行，這里是不允許的。若大于文字圖像最小高度，轉(zhuǎn)（7），否則轉(zhuǎn)（2）。（7）計(jì)算行，，內(nèi)的文字圖像個(gè)數(shù)，注意文字圖像的寬度與高度的比值應(yīng)該在-3之間，不在此范圍內(nèi)比值范圍內(nèi)的圖像不應(yīng)該統(tǒng)計(jì)。（8）判斷是否>0，大于則，，轉(zhuǎn)（9），如果等于0，不累加文字總個(gè)數(shù)和文字行高度，也轉(zhuǎn)（9），顯然,行位置就是文字行的Y坐標(biāo)位置。（9），尋找下一個(gè)序號(hào)為的空間行，應(yīng)該小于，同時(shí)第+1行不是空白點(diǎn)行，如果存在，則-1，轉(zhuǎn)（2），否則結(jié)束。計(jì)算出行高度后，考慮到碎片內(nèi)文字行高度和小于碎片像素高度，而碎片像素高度一般遠(yuǎn)小于10000，可將這兩個(gè)數(shù)按公式*1000+合并成為一個(gè)數(shù)，然后對(duì)不同方向的合并數(shù)進(jìn)行排序，這樣能更有效地選取行高和最小的目標(biāo)方向。確定匹配準(zhǔn)則對(duì)于附件中切割規(guī)則的碎片，其鄰接碎片上均有文字，那么在非常逼近切割線的位置處，邊緣像素吻合度將非常高。假設(shè)其中的一個(gè)碎片為A，其右側(cè)邊緣處灰度值為0的像素坐標(biāo)為Ai，j，假設(shè)與A鄰接的碎片為B，其左側(cè)邊緣處灰度值為0的像素坐標(biāo)為Bi，j，對(duì)Bi，j與Ai對(duì)應(yīng)于原始圖像最左側(cè)碎片的確定根據(jù)碎片左側(cè)碎片文字位置的特征，其左側(cè)一列像素的灰度值均為1，利用這種方法可以找出所有符合條件的碎片。但是在實(shí)際操作中，符合條件的碎片數(shù)目往往會(huì)大于原始圖像的行數(shù)，因此僅僅選取碎片左側(cè)一列的灰度值為參考是不科學(xué)的，為了達(dá)到選取目的，我們需選擇左側(cè)兩列，甚至更多列的灰度值為參考。利用此方法可以找出左側(cè)碎片，并根據(jù)圖像命名對(duì)它們進(jìn)行隨機(jī)排列。拼接過(guò)程中的人工干預(yù)由于計(jì)算機(jī)在數(shù)字圖像處理方面的缺陷，讓計(jì)算機(jī)對(duì)碎片進(jìn)行完全意義上的自動(dòng)化拼接幾乎是不可能的，為保證拼接的質(zhì)量及準(zhǔn)確性，需要在拼接過(guò)程中加入人工干預(yù)過(guò)程。一般情況下，拼接碎片時(shí)先利用計(jì)算機(jī)搜索與目標(biāo)碎片匹配的未拼接碎片，并根據(jù)匹配程度按順序顯示待選碎片，此時(shí)可利用人工干預(yù)的方法，從多個(gè)待選碎片中選出符合文字內(nèi)容的碎片，這種半自動(dòng)拼接方法提高了計(jì)算機(jī)拼接的準(zhǔn)確性，拼接效率也比純?nèi)斯じ?。將匹配好?1行匹配鏈融合具體模型同模型一。5.2.2縱橫切碎片拼接復(fù)原模型的求解原始圖像最左側(cè)碎片的確定（求解過(guò)程均采用附件三中的碎片圖像）假設(shè)原始圖片左側(cè)碎片的左列灰度值為A(i，j)，從附件三找出A(i，1)=1的碎片共有19塊，其在附件中的標(biāo)號(hào)分別為：168、29、7、38、61、11、49、46、62、67、71、80、106、135、14、94、125、184、89。但我們所需的左側(cè)碎片數(shù)僅為11塊，顯然，找出的碎片并不符合我們的要求，需要進(jìn)一步篩選。擴(kuò)大左側(cè)碎片的搜索范圍，令A(yù)(i，1)=A(i，2)=A(i，3)=A(i，4)=1，符合要求的碎片共有11塊，其標(biāo)號(hào)分別為：7、168、38、14、94、49、89、29、61、71、125，由此便確定了左側(cè)碎片，并假設(shè)這些碎片在原始文檔中所在行的位置分別為：A、B、C、D、E、F、G、H、I、J、K。確定每一行的行匹配鏈（1）以碎片7為匹配起點(diǎn)，從左至右依次進(jìn)行拼接。根據(jù)模型二最優(yōu)匹配原則，碎片7右側(cè)邊緣處灰度值為1的像素與209碎片距離最近，因此碎片7與碎片209左右鄰接，從而得到第一條匹配鏈：7→209。（2）以碎片209為起點(diǎn)，與其右側(cè)邊緣處灰度值為1的像素距離最短的碎片共有4塊，標(biāo)號(hào)分別為：73、7、173、138，對(duì)此匹配過(guò)程進(jìn)行人工干預(yù)，發(fā)現(xiàn)碎片209與碎片138的文字內(nèi)容最匹配，因此可以確定碎片129與碎片138左右鄰接，從而得到第二條匹配鏈：7→209→138。（3）根據(jù)步驟（1）、（2）所用方法可以確定以碎片7為起點(diǎn)的行匹配鏈：7→209→138→158→126→68→175→45→174→0→137→53→56→93→153→70→166→32→196；以碎片168為起點(diǎn)的行匹配鏈：168→100→76→62→142→30→41→23→147→191→50→179→120→86→195→26→1→87→18；以碎片38為起點(diǎn)的行匹配鏈：38→148→46→161→24→35→81→189→122→103→130→193→88→167→25→8→9→105→74；以碎片14為起點(diǎn)的行匹配鏈：14→128→3→159→82→199→135→12→73→160→203→169→134→39→31→51→107→115→176；以碎片94為起點(diǎn)的行匹配鏈：94→34→84→183→90→47→121→42→124→144→77→112→149→97→136→164→127→58→43；以碎片49為起點(diǎn)的行匹配鏈：49→54→65→143→186→2→57→192→178→118→190→95→11→22→129→28→91→188→141；以碎片89為起點(diǎn)的行匹配鏈：89→146→102→154→114→40→151→207→155→140→185→108→117→4→101→113→194→119→123；以碎片29為起點(diǎn)的行匹配鏈：29→64→111→201→5→92→180→48→37→75→55→44→206→10→104→98→172→171→59；以碎片61為起點(diǎn)的行匹配鏈：61→19→78→67→69→99→162→96→131→79→63→116→163→72→6→177→20→52→36；以碎片71為起點(diǎn)的行匹配鏈：71→156→83→132→200→17→80→33→202→198→15→133→170→205→85→15→165→27→60以碎片125為起點(diǎn)的行匹配鏈：125→13→182→109→197→16→184→110→187→66→106→150→21→173→157→(異常)→204→139→145 值得一提的是，標(biāo)號(hào)為181的碎片不能夠和其它任何碎片進(jìn)行匹配，而且最后一行匹配鏈的第16列無(wú)碎片可拼接，根據(jù)題目要求，已在附錄二中將其單獨(dú)列出。確定每一行行匹配鏈的順序根據(jù)原始圖像中頂部像素的灰度值均為1的規(guī)律，并結(jié)合人工干預(yù)的方法，可以確定F行匹配鏈為原始文檔的第一行。以F行匹配鏈為參考，根據(jù)最優(yōu)匹配原則，假設(shè)F行匹配鏈的下側(cè)邊緣處灰度值為1的像素坐標(biāo)為，與其匹配的行匹配鏈的坐標(biāo)為，利用公式可得到F行匹配鏈與其它行匹配鏈的距離分別為1925、894、3226、1286、2709、3651、1028、45、1396、2450，顯然，F(xiàn)行匹配鏈與I行匹配鏈的距離最短，從而可以確定在原始文檔中I行匹配鏈為第二行。根據(jù)上述方法，可以確定所有行匹配鏈在原始文檔中的順序依次為：F→I→B→C→J→D→E→K→H→A→G。5.3問(wèn)題三的模型建立與求解5.3.1雙面橫、縱切碎紙片的拼接模型建立與求解模型建立（1）確定匹配準(zhǔn)則如果鄰接的兩碎片正反兩面都有文字，那么在非常逼近切割線位置處，正反兩面的邊緣像素吻合度都會(huì)很高，即目標(biāo)碎片右側(cè)灰度值為0的像素，與待匹配碎片左側(cè)灰度值為0的像素的距離很小，那么距離平方的累積和最小的碎片即為所求的最優(yōu)匹配。對(duì)于附件中切割規(guī)則的碎片，其鄰接碎片上均有文字，那么在非常逼近切割線的位置處，邊緣像素吻合度將非常高。由于附件5中原始文檔為正反兩面打印，則假設(shè)待拼接碎片為B，其a面左側(cè)邊緣處灰度值為0的像素坐標(biāo)為Bai，j，b面為Bbi，j；參考碎片為A，其右側(cè)邊緣處灰度值為0的像素坐標(biāo)為Ai，jMinaMin比較Mina1與Mina2的大小，確定與參考碎片a面的最小距離Mina，從而確定與參考碎片Minb1Minb2比較Minb1與Minb2的大小，確定與參考碎片b面的最小距離Minb對(duì)于正反面均有文字的碎片而言，一旦找到參考碎片a面的最優(yōu)匹配碎片，就可以確定參考碎片b面的最優(yōu)匹配碎片。即參考碎片正反面的最優(yōu)匹配碎片分別為同一碎片的兩個(gè)面。因此，只需Mina與Min=Mina+Minb圖N模型三匹配準(zhǔn)則示意圖在拼接碎片時(shí)，可先計(jì)算目標(biāo)碎片正反面與所有未拼接碎片正反面在所有可能拼接位置處的距離相等的像素對(duì)差平方的累積和，然后對(duì)其和進(jìn)行降序排列，排在前面的碎片與目標(biāo)碎片鄰接的可能性最高。（2）算法設(shè)計(jì)基于文字行特征的碎片半自動(dòng)拼接算法設(shè)計(jì)如下：分析所有碎紙片圖像，獲取所有碎紙片的邊界。獲取所有碎紙片內(nèi)文字行方向線特征。從碎片內(nèi)挑選一未拼接糾偏碎片，按文字向上方向放置到計(jì)算機(jī)屏幕上。在計(jì)算機(jī)屏幕上人工選擇某一碎片，計(jì)算該碎片某一邊界（上、下、左、右）與未接碎片邊界（上、下、左、右）可能拼接位置處的距離相等的灰度值差平方的累積和：a計(jì)算該碎片反面與未拼接碎片反面在可能拼接位置處距離相等的灰度值差平方的累積和：a求碎片正、反面沿切割線距離相等的灰度值的兩個(gè)累積和：a將此和按遞減順序排列，按遞減順序依次顯示未拼接碎片，人工選擇碎片并拼接到計(jì)算機(jī)屏幕上。保存已拼接好的部分，并從未拼接碎片集合中刪除所選碎片。判斷未拼接碎片集合是否為空，若是，則保存計(jì)算機(jī)屏幕上的拼接正反面圖像，轉(zhuǎn)⑨。否則，轉(zhuǎn)④。代碼返回已完成拼接的完整圖像。5.3.2雙面縱橫切碎片拼接復(fù)原模型的求解原始圖像最左側(cè)碎片的確定（求解過(guò)程均采用附件5中的碎片圖像）假設(shè)原始圖片左側(cè)碎片的左列灰度值為A(i，j)，從附件5找出A(i，1)=1的碎片共有27塊，其在附件中的標(biāo)號(hào)分別為：23b、136b、5a、146b、143b、83a、90a、52b、13a、35a、54b、172a、105a、9b、54b、140b、76a、42a、169a、180b、116a、201b、157b、148a、199b、51a、109b。但我們所需的左側(cè)碎片數(shù)僅為22塊，顯然，找出的碎片并不符合我們的要求，需要進(jìn)一步篩選。擴(kuò)大左側(cè)碎片的搜索范圍，令A(yù)(i，1)=A(i，2)=A(i，3)=1，符合要求的碎片共有22塊，其標(biāo)號(hào)分別為：143b、42a、180b、90a、35a、201b、148a、105a、109b、54b、136b、5a、140b、180b、76a、90a、13a、116a、172a、157b、9b、51a。由此便確定了左側(cè)碎片，并假設(shè)這些碎片在原始文檔中所在行的位置分別為：A、B、C、D、E、F、G、H、I、J、K、L、M、N、O、P、Q、R、S、T、U、V。確定每一行的行匹配鏈（1）以碎片143b為匹配起點(diǎn)，從左至右依次進(jìn)行拼接。根據(jù)模型三最優(yōu)匹配原則，碎片143b右側(cè)邊緣處灰度值為0的像素與碎片200b距離最近，因此碎片143b與碎片200b左右鄰接，從而得到第一條匹配鏈：143b→200b。（2）以碎片200b為起點(diǎn)，與其右側(cè)邊緣處灰度值為0的像素距離最短的碎片共有5塊，標(biāo)號(hào)分別為：24a,76b、102a、86b、191a，對(duì)此匹配過(guò)程進(jìn)行人工干預(yù)，發(fā)現(xiàn)碎片200b與碎片86b的文字內(nèi)容最匹配，因此可以確定碎片200b與碎片86b左右鄰接，從而得到第二條匹配鏈：143b→200b→86b。（3）根據(jù)步驟（1）、（2）所用方法可以確定以碎片143b為起點(diǎn)的行匹配鏈：143b→200b→86b→187b→131b→56b→138a→45a→137b→61b→94b→98a→121a→38a→30a→42b。并依次確定以標(biāo)號(hào)為42a、180b、90a、35a、201b、148a、105a、109b、54b、136b、5a、140b、180b、76a、90a、13a、116a、172a、157b、9b、51a的碎片為起點(diǎn)的行匹配鏈。（4）原始文檔正面某一行的左側(cè)碎片在其反面的位置為相同行的右側(cè)，根據(jù)這個(gè)規(guī)律，可將步驟三中的22個(gè)行匹配鏈區(qū)分為正反兩面。正面的行匹配鏈為：136b→47a→20a→164b→81b→189b→29a→18b→108a→66a→110a→174b→183b→150a→155a→140a5a→152a→147a→60b→59a→14a→79a→144a→120b→22a→124b→192a→25b→44a→178a→76b143b→200b→86b→187b→131b→56b→138a→45a→137b→61b→94b→98a→121a→38a →30a→42b83a→39b→97a→175a→72b→93b→132b→87a→198b→181b→34a→156a→206b→173b →194b→169b90a→203b→162b→2a→139b→70b→41a→170b→151b→1b→166b→115b→65b→191a→37b→180a13a→24a→57a→142a→208a→64b→102b→17b→12a→28b→154b→197a→158a→58a→207a→116b35a→159a→73b→193b→163a→130a→21b→202a→53b→177b→16b→19b→92b→190b→50a→201a172a→122a→182b→40a→127a→188a→68b→8b→117b→167a→75b→63b→67a→46a→163a→157a105a→204a→141a→135b→27a→80b→0b→185a→176a→126b→74b→32a→69a→4a→77a→148b9b→145a→82b→205a→15b→101a→118b→129b→62a→52b→71b→33b→119a→160b→95a→51b54b→196b→112a→103a→55b→100b→106b→91a→49b→26b→113a→134a→104a→6a→123a→109a反面的行匹配鏈為：140b→155b→150b→183a→174a→110b→66b→108b→18a→29b→189a→81a→164a→20b→47b→136a76a→178b→44b→25a→192b→124a→22b→120a→144b→79b→14b→59b→60a→147b→152b→5b42a→30b→38b→121b→98b→94a→61a→137a→45b→138b→56a→131a→187a→86a→200a→143a169a→194a→173a→206a→156b→34b→181a→198a→87b→132a→93a→72a→175b→97b→39a→83b180b→37a→191b→65a→115a→166a→1a→151a→170a→41b→70a→139a→2b→162a→203a→90b116a→207b→58b→158b→197b→154a→28a→12b→17a→102a→64a→208b→142b→57b→24b→13b201b→50b→190a→92a→19a→16a→177a→53a→202b→21a→130b→163b→193a→73a→159b→35b157b→163b→46b→67b→63a→75a→167b→117a→8a→68a→188b→127b40b→182a→122b→172b148a→77b→4b→69b→32b→74a→126a→176b→185b→0a→80a→27b→135a→141b→204b→105b51a→95b→160a→119b→33a→71a→52a→62b→129a→118a→101b→15a→205b→82a→145b→9a109b→123b→6b→104b→134b→113b→26a→49a→91b→106a→100a→55a→103b→112b→196a→54a確定每一行行匹配鏈的順序根據(jù)原始圖像中頂部像素的灰度值均為1的規(guī)律，并結(jié)合人工干預(yù)的方法，可以確定K行匹配鏈為原始文檔正面的第一行。以K行匹配鏈為參考，根據(jù)最優(yōu)匹配原則，假設(shè)K行匹配鏈的下側(cè)邊緣處灰度值為1的像素坐標(biāo)為，與其匹配的行匹配鏈的坐標(biāo)為，利用公式可得到K行匹配鏈與其它正面行匹配鏈的距離分別為896、1294、3906、3286、1700、329、1043、985、2301、861，顯然，F(xiàn)行匹配鏈與L行匹配鏈的距離最短，從而可以確定在原始文檔中L行匹配鏈為第二行。根據(jù)上述方法，可以確定所有行匹配鏈在原始文檔正面中的順序依次為：K→L→A→N→P→Q→E→S→H→U→J。根據(jù)上述方法，可以確定所有行匹配鏈在原始文檔反面中的順序依次為：M→O→B→D→C→R→F→T→G→V→I。模型優(yōu)缺點(diǎn)分析6.1模型優(yōu)點(diǎn)6.1.1基于灰度的文字特征提取，碎片差異化明顯、魯棒性強(qiáng)對(duì)于規(guī)則碎片的處理，傳統(tǒng)的對(duì)不規(guī)則碎片提取碎片角點(diǎn)、曲率等幾何特征的思路很難提取到足夠的有用信息。本文從像素角度出發(fā)，將碎片二值化后，通過(guò)提取碎片邊緣文字的灰度值得到特征向量，不同碎片的特征向量差異化明顯。運(yùn)用這種基于灰度的文字特征提取方法，不僅可以復(fù)原本題的中、英文黑白規(guī)則碎片，也適用帶有文字和表格的混合碎片等。6.1.2半自動(dòng)拼接，效率高、精度好由于計(jì)算機(jī)數(shù)字分析圖像能力的缺陷，讓計(jì)算機(jī)對(duì)碎片進(jìn)行完全意義上的自動(dòng)化拼接幾乎不太可能。本文在拼接過(guò)程中加入人工干擾過(guò)程，當(dāng)程序給出多個(gè)待匹配碎片時(shí)，用戶再根據(jù)人腦進(jìn)一步分析結(jié)果舍棄或拼接待選碎片。這種半自動(dòng)拼接方法綜合利用了計(jì)算機(jī)高速計(jì)算能力以及人的文字圖像識(shí)別和理解能力，拼接效率比純?nèi)斯じ?，拼接?zhǔn)確性也好于純計(jì)算機(jī)拼接法。6.1.3高度優(yōu)化的算法和代碼，性能良好、可靠度高本文算法和代碼均充分結(jié)合題目實(shí)際情況進(jìn)行優(yōu)化，執(zhí)行性能良好，結(jié)果可靠度高。從算法角度看，加入了“智能排序”和“自動(dòng)剔除”功能，當(dāng)程序給出的匹配結(jié)果不止一個(gè)時(shí)，則根據(jù)與目標(biāo)碎片的匹配度從高到低依次排序，用戶只需進(jìn)行很少次數(shù)的匹配即可得到正確的碎片。當(dāng)某一塊碎片已匹配成功后，程序?qū)⒆詣?dòng)從待匹配碎片集合中剔除該碎片，保證后續(xù)匹配過(guò)程只檢測(cè)最新的碎片集合，從而實(shí)現(xiàn)人工干預(yù)的簡(jiǎn)潔性和代碼執(zhí)行的高效性。從代碼角度看，主要通過(guò)MATLAB軟件編寫代碼，使用了各類循環(huán)體、數(shù)組和“超級(jí)矩陣”（cell矩陣）等高效處理策略、函數(shù)，從而將幾百行的代碼壓縮到20行以內(nèi)，代碼執(zhí)行效率和可讀性有明顯提高。6.2模型缺點(diǎn)6.2.1碎片理想化帶來(lái)的局限性本題所給碎片較為理想化（擺正、規(guī)則且無(wú)噪聲干擾等），而實(shí)際情況中遇到的很多碎片圖像可能是彩色的、傾斜的、不規(guī)則的，甚至是殘缺、畸變的。故本文建立的模型在應(yīng)用領(lǐng)域上有一定的局限性。例如，當(dāng)使用掃描儀等設(shè)備采集到碎片圖像很容易帶有黑邊、黑點(diǎn)和干擾噪聲，如果不加入相關(guān)的圖像預(yù)處理措施，那么這些噪聲將在一定程度上對(duì)本文所建立的模型產(chǎn)生不良影響。6.2.2匹配準(zhǔn)則易受外界影響基于像素平方和（SSD）的匹配準(zhǔn)則雖然是一種簡(jiǎn)單有效的匹配準(zhǔn)則，但因?yàn)樗苯永脠D像的灰度值，所以對(duì)匹配區(qū)域的光照變化十分敏感，一旦待匹配的兩塊碎片在接縫區(qū)域的曝光不一致，則匹配準(zhǔn)則的準(zhǔn)確性將受到影響。另外，這種匹配準(zhǔn)則還對(duì)碎片的旋轉(zhuǎn)和縮放比較敏感。模型的推廣與改進(jìn)7.1模型推廣7.1.1碎片類型的推廣除了復(fù)原本文所給定附件中的碎片，該模型還普遍適用于多語(yǔ)言文字碎片，表格文檔碎片，甚至是非文檔類（如人物圖片碎片、景物碎片）等規(guī)則碎片。7.1.2應(yīng)用領(lǐng)域的推廣除了應(yīng)用于碎紙機(jī)規(guī)則切割出的碎紙片，拼接復(fù)原技術(shù)還可廣泛應(yīng)用于衛(wèi)星遙感【文獻(xiàn)A】、海底勘探【文獻(xiàn)B】、地表植被測(cè)繪【文獻(xiàn)C】、無(wú)人機(jī)監(jiān)視和搜索【文獻(xiàn)D】、機(jī)器人視覺(jué)【文獻(xiàn)E】、視頻監(jiān)控【文獻(xiàn)F】、醫(yī)學(xué)探查【文獻(xiàn)G】、電子穩(wěn)像【文獻(xiàn)H】和虛擬現(xiàn)實(shí)【文獻(xiàn)I】等領(lǐng)域圖像拼接復(fù)原。7.2模型改進(jìn)7.2.1碎片傾斜時(shí)，預(yù)置“糾偏”處理本題所給碎片均為擺正的規(guī)則矩形，而實(shí)際情況中，由于人在使用碎紙機(jī)、掃描儀等設(shè)備時(shí)引入的操作偏差，我們更多地遇到的是碎片傾斜情況。若其他條件保持不變，僅將碎片變?yōu)閮A斜的，則在進(jìn)行碎片特征提取前，需先進(jìn)行碎片的“糾偏”?？梢岳谩熬S格納——威利（WVD）”糾偏法【標(biāo)注參考文獻(xiàn)：胡奇《文檔圖像拼接技術(shù)的研究》】等來(lái)實(shí)現(xiàn)。7.2.2碎片不規(guī)則時(shí)，提取幾何特征本題所給碎片均為規(guī)則矩形，而實(shí)際情況中，碎紙片可能是由于某種原因被撕碎成不規(guī)則的形狀，此時(shí)處理對(duì)象變?yōu)椴灰?guī)則的、具有邊角、曲率等幾何特征的碎片。對(duì)于這些碎片的處理角度不再是像素，而考慮盡可能多地提取碎片的幾何特征?？梢酝ㄟ^(guò)輪廓特征、角點(diǎn)檢測(cè)、SIFT等算法實(shí)現(xiàn)【標(biāo)注參考文獻(xiàn)：蔡麗歡《圖像拼接方法及其關(guān)鍵技術(shù)研究》】。7.2.3二值文檔圖像帶黑邊時(shí)，設(shè)計(jì)黑邊過(guò)濾算法【標(biāo)注參考文獻(xiàn)：胡奇《文檔圖像拼接技術(shù)的研究》】通過(guò)掃描儀等設(shè)備采集碎片圖像時(shí)，最容易產(chǎn)生的畸變就是黑邊。黑邊一般是在文檔的外圍，因此僅分析文檔周邊即可。根據(jù)黑邊的特征和文字的特征就可以去掉黑邊。該特征用兩個(gè)量來(lái)表達(dá)，一個(gè)是黑像素個(gè)數(shù)，另一個(gè)是黑像素到白像素和白像素到黑像素的個(gè)數(shù)。算法設(shè)計(jì)及區(qū)域選擇如下圖所示:圖N黑邊過(guò)濾算法流程圖圖N區(qū)域選擇示意圖參考文獻(xiàn)【A】LaurieGibson.AutomationtechnologywithIKONOSsatelliteimagery[C]//Sensors,Systems,andNext-GenerationSatellitesV,ProceedingsofSPIE,2001,4540:650-660.【B】S.Negahdaripour,X.Xu,A.Khamene.Avisionsystemforreal-timeposi-tioning,navigation,andvideomosaicingofseafloorimageryintheapplicationofROVs/AUVs[C]//ApplicationsofComputerVision,FourthIEEEWorkshoponProceedings,1998,(8):248-249.【C】MariaG.Almeida,BernardoF.TRudorff,YosioE.Shimabukuro.NOAA-AVHRRimagemosaicsappliedtovegetationidentification[C]//Geo-SpatialImageandDataExploitationII,ProceedingsofSPIE,2001,4383:31-35.【D】N.Heinze,M.Esswein,W.Krüger,etal..AutomaticimageexploitationsystemforsmallUAVs[C]//AirborneIntelligence,Surveillance,Reconnaissance(ISR)SystemsandApplicationsV.Proc.ofSPIE,2008,6946:69460G1-10.【E】B.Kaya,A.Berkay,F.Erzincanli.Robotassistedtilingofglassmosaicswithimageprocessing[J].IndustrialRobot,2005,32(5):388-392.【F】TomRiley,MarkBernhardt,CatherineCowell,etal..Implementingadvancedimageprocessingtechnologyinsensorsystemsforsecurityandsurveillance[C]//OpticsandPhotonicsforCounterterrorismandCrimeFightingIII,Proc.ofSPIE,2007,6741:67410W1-12.【G】K.Loewke,D.Camarillo,W.Piyawattanametha,D.Breeden,etal.Real-timeimagemosaicingwithahand-helddual-axesconfocalmicroscope[C]//ProgressinBiomedicalOpticsandImaging.Proc.ofSPIE,2008,6851:68510F1-9.【H】王建東.羅軍.基于圖像拼接的全幀視頻穩(wěn)定算法[J].紅外技術(shù),2007,29(8):435-439.【I】R.Szeliski.VideoMosaicsforVirtualEnvironment[J].IEEEComputerGraphicsandApplications,1996,16(2):22-30.【】蔡麗歡.廖英豪.郭東輝.圖像拼接方法及其關(guān)鍵技術(shù)研究[J].計(jì)算機(jī)技術(shù)與發(fā)展.2008(03)【】胡奇.文檔圖像拼接技術(shù)的研究[D].哈爾濱工程大學(xué).2005.附件附件一：第一問(wèn)MATLAB程序——基于最優(yōu)匹配的縱切圖像拼接%%讀取圖片clc,clear,closeallpicstr=dir('*.bmp');[r,c]=size(picstr);fori=1:rpic{i}=imread(picstr(i).name);lcol{i}=pic{i}(:,1);rcol{i}=pic{i}(:,72);end%%最優(yōu)匹配[rowcol]=size(pic{1});forii=1:rforjj=1:r%jj=7;d(ii,jj)=sum((double(lcol{ii})-double(rcol{jj})).^2);d1(ii,jj)=sum((double(rcol{ii})-double(lcol{jj})).^2);endend%%找到第一幅圖片位置[valdir]=min(d)forii=1:rflag=1;forjj=1:length(lcol{ii})if(lcol{ii}(jj)~=255)flag=0;%endendif(flag==1)dir2=ii;endendresult=[];result(1)=dir2;forii=2:rresult(ii)=dir(result(ii-1));end%%重現(xiàn)復(fù)原圖片warningofffigure,imshow([pic{result}])*********************************************************附件二：第二問(wèn)MATLAB程序——橫、縱兩切圖形的拼接第一步：從209張碎片中求出11行圖片%%第二問(wèn),橫切縱切圖片的復(fù)原.clc,clear,closeallpicstr=dir('*.bmp');[r,c]=size(picstr);fori=1:rpic{i}=imread(picstr(i).name);lcol{i}=double(pic{i}(:,1:4));rcol{i}=double(pic{i}(:,69:72));end[row0col0]=size(lcol{1});%%檢測(cè)每幅圖片最左邊四列的灰度值.forii=1:rrcol{ii}=rcol{ii}(:,1)+rcol{ii}(:,2)+rcol{ii}(:,3)+rcol{ii}(:,4);lcol{ii}=lcol{ii}(:,1)+lcol{ii}(:,2)+lcol{ii}(:,3)+lcol{ii}(:,4);endforii=1:rforjj=1:rd(ii,jj)=sum((double(lcol{ii})-double(rcol{jj})).^2);endend%%[valdir]=min(d)A(1,:)=([49,54,65,143,186,2,57,192,178,118,190,95,11,22,129,28,91,188,141]+1);%forii=1:rA(3,:)=([168,100,76,62,142,30,41,23,147,191,50,179,120,86,195,26,1,87,18]+1);%endA(11,:)=([89,146,102,154,114,40,151,207,155,140,185,108,117,4,101,113,194,119,123]+1);%%找出最左邊的圖片kk=1;forii=1:rflag=1;forjj=1:length(lcol{ii})if(lcol{ii}(jj)~=1020)flag=0;continue;endendif(flag==1)dir2(kk)=ii;kk=kk+1;endenddir2A(4,:)=([38,148,46,161,24,35,81,189,122,103,130,193,88,167,25,8,9,105,74]+1);kk=1;forii