碎紙片的拼接復原

PAGEPAGE30碎紙片的拼接復原摘要破碎文件的拼接在司法物證復原、歷史文獻修復以及軍事情報獲取等領(lǐng)域都有著重要的應(yīng)用。本文就碎紙片的拼接復原問題進行仔細的分析和研究，并最終得到相應(yīng)的算法和程序來解決相應(yīng)問題。針對問題一，首先將題中附件1和附件2所給的各19條縱切碎片圖像信息（1980×72像素點）提取為對應(yīng)的灰度矩陣和0-1矩陣，要使19條碎片按順序拼接復原，則建立左右匹配模型和左右拼接算法，通過MATLAB編程求解，得到中文和英文各19條碎片拼接復原的順序表（見表一和表二）和拼接復原圖（見附錄一）。針對問題二，由于題中所給的中、英文碎片圖像（180×72）是11×19條，較問題一中的數(shù)據(jù)有增加，并且出現(xiàn)相鄰圖形之間為完全空白的情況，如果仍僅僅用問題一的模型和算法對其拼接，其自動匹配度大大降低，人工干預會增加。通過仔細分析，本文決定采用行高相等分組模型和左右匹配拼接模型兩種模型配合使用對附件3中文碎片進行拼接和復原。通過MATLAB軟件編程求解，得到相應(yīng)的拼接復原的順序表（見表七）和拼接復原圖（見附錄二）。對附件4，我們將在問題三中解決。針對問題三，包括問題二的附件4的情況，都是英文字母組成的碎片，附件五是由正反面兩頁組成，但是實際上可以看成是將反面去掉、將其轉(zhuǎn)接到第一頁的下方，從而組成一個長頁，所以問題三與問題二的附件4是相同的問題。我們建立相同的模型，使用同一算法來解決?？紤]到英文字母的特征，給出了一種利用標準字母位圖與碎片圖像進行對比掃描、確定標準字母在碎片圖像中的部分位圖及位置信息，再根據(jù)這種信息在其他碎片中的對應(yīng)余部分來進行相鄰碎片圖像匹配。通過C++Builder軟件編程求解，得到相應(yīng)的拼接復原順序表（附件4見表八、附件5見表九、表十）和拼接復原圖（見附錄三）。關(guān)鍵詞：圖像拼接；灰度矩陣；0-1矩陣；匹配度；MATLAB軟件問題重述破碎文件的拼接在司法物證復原、歷史文獻修復以及軍事情報獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復原工作需由人工完成，準確率較高，但效率很低。特別是當碎片數(shù)量巨大，人工拼接很難在短時間內(nèi)完成任務(wù)。隨著計算機技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復原效率。請討論以下問題：問題1.對于給定的來自同一頁印刷文字文件的碎紙機破碎紙片（僅縱切），建立碎紙片拼接復原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎片數(shù)據(jù)進行拼接復原。如果復原過程需要人工干預，請寫出干預方式及干預的時間節(jié)點。復原結(jié)果以圖片形式及表格形式表達。問題2.對于碎紙機既縱切又橫切的情形，請設(shè)計碎紙片拼接復原模型和算法，并針對附件3、附件4給出的中、英文各一頁文件的碎片數(shù)據(jù)進行拼接復原。如果復原過程需要人工干預，請寫出干預方式及干預的時間節(jié)點。復原結(jié)果表達要求同上。問題3.上述所給碎片數(shù)據(jù)均為單面打印文件，從現(xiàn)實情形出發(fā)，還可能有雙面打印文件的碎紙片拼接復原問題需要解決。附件5給出的是一頁英文印刷文字雙面打印文件的碎片數(shù)據(jù)。請嘗試設(shè)計相應(yīng)的碎紙片拼接復原模型與算法，并就附件5的碎片數(shù)據(jù)給出拼接復原結(jié)果，結(jié)果表達要求同上。解決上述三個問題的基本思路是將碎片圖像進行數(shù)字化處理，再利用各個數(shù)字圖像的鄰邊匹配關(guān)系對圖像進行拼接?；炯僭O(shè)假設(shè)模型只討論于形狀規(guī)則大小相同的碎紙片的拼接復原。假設(shè)任何種情況下，原始圖中的文字是通順連續(xù)不間隔的。（3）假設(shè)所有的圖像都是標準的縱切和橫切，不存在邊界彎曲的碎紙片。三、問題分析針對問題一:該問題要求對19條縱切碎片進行拼接復原，考慮到在實際生活中的應(yīng)用性，要提高碎紙片拼接復原的效率，于是就對其進行了匹配拼接模型的建立和求解。由于題中所給的原始數(shù)據(jù)是1980×72單色BMP圖像格式，便于觀察，但不便于模型處理，于是對19塊碎片的圖像信息通過MATLAB軟件進行提取出1980×72的灰度矩陣，將每個圖像轉(zhuǎn)化為1980×72的二維0-1矩陣，其中0代表白色，1代表黑色，首先通過觀察該19個新矩陣中的第1列數(shù)據(jù)全為0的那個矩陣所對應(yīng)的碎片即為從左到右的第一個碎片，第72列數(shù)據(jù)全為0的那個矩陣所對應(yīng)的碎片即為從右到左的第一個碎片。然后采用拼接算法將第一個碎片矩陣的第72列與其余18個碎片矩陣的第一列進行相似度匹配，匹配度最高的兩塊碎片就說明他們是緊接著的碎片，如此，采用逐條匹配的方法，進行17次的匹配，最終將19條碎紙片拼接復原。針對問題二:該問題要求對即縱切又橫切的11×19條碎片進行拼接和復原，所給的原始數(shù)據(jù)是180×72單色BMP圖像格式，同理，用MATLAB將每個圖案轉(zhuǎn)化為180×72的二維0-1矩陣，再依據(jù)圖像的前幾列數(shù)據(jù)全為0（白色），從209條碎片中找到前幾列數(shù)據(jù)全為0且列數(shù)大致相等的11條碎片，這11條碎片即為第一列的碎片。由于該題中碎片條數(shù)較多，如果再用第一問的模型求解不僅數(shù)據(jù)量大且復原效率低精度也不高，但通過問題一的分析和求解，很容易想到在問題一的模型的基礎(chǔ)上進行改進并求解。由于印刷文字的字高即行高基本上是固定值，采用行高相等的模型對209個圖像分類成無順序的11行圖像，再利用第一問的模型和解法對11行圖像按照從左到右的順序進行拼接成11條橫條圖像，再利用問題一的解法將11條橫幅按順序上下拼接成完整的復原圖。針對問題三：該問題要求對正反兩頁的碎片圖像進行拼接復原，這個問題與問題二的附件4的情況是相同的，都是英文字母組成的碎片，附件五是由正反面兩頁組成，但是實際上可以看成是將反面去掉、將其轉(zhuǎn)接到第一頁的下方，從而組成一個長頁，所以問題三與問題二的附件4是相同的問題，使用同一方法來解決?？紤]到英文字母的特征，給出了一種利用標準字母位圖與碎片圖像進行對比掃描、確定標準字母在碎片圖像中的部分位圖及位置信息，再根據(jù)這種信息在其他碎片中的對應(yīng)余部分來進行相鄰碎片圖像匹配。四、建模前的預處理從問題所給附件文件可以看出，每個問題所給出的碎片圖像具有相同的尺寸。因此，本文中假設(shè)每個問題中的所有碎片文件是相同尺寸的。4.1灰度矩陣及其0-1矩陣假設(shè)某個圖像A的的寬度和高度分別為和，單位為像素點。其灰度矩陣為，其中：，，為圖像在上數(shù)第行、左數(shù)第列處的圖像灰度值，一般的取值范圍為0～255?；叶戎禐?時，顏色為黑色；灰度值為255時，顏色為白色；灰度值取1～254的某個值時，顏色為深淺不一的灰色。在進行圖像拼接時，我們只需要考慮圖像上的某個點是不是有顏色，所以對灰度矩陣進行再次處理，得到0-1矩陣。假設(shè)為某個預定、可調(diào)的閾值，例如：，當某個灰度值超過，可以認為對應(yīng)圖像點為白色的，否則為黑色的。定義灰度矩陣的0-1矩陣如下：，當時(1)，當時(2)例如，某個灰度矩陣及其0-1矩陣如圖1所示。，，(a)灰度矩陣(b)0-1矩陣圖1灰度矩陣及其0-1矩陣的示意圖4.20-1矩陣的邊數(shù)組在求解碎片圖像拼接復原問題時，主要考慮每個碎片圖像的四邊是否與其他碎片圖像的四邊能否拼接上，至于碎片圖像的內(nèi)部像素，暫時不必考慮。因此，可以從碎片圖像0-1矩陣中進一步抽象出拼接算法所需要的本質(zhì)數(shù)據(jù)。對于圖像A，定義其四邊數(shù)組分別為：，，，式中：，稱為圖像A的左邊數(shù)組，為圖像A的右邊數(shù)組，為圖像A的上邊數(shù)組，為圖像A的下邊數(shù)組。在不影響歧義的情況下，也簡稱為左邊等等。4.3匹配度的定義對于任意兩個碎片圖像A和B，定義他們之間的匹配度為：(3)(4)稱為圖像A和B的橫向匹配度，為圖像A和B的縱向匹配度。注意：一般地，，。根據(jù)定義，，。退化情況：定義，。當接近于1時，圖像A和B在橫向上能夠拼接在一起的可能性非常大。例如，圖像2(a)分割成(b)和(c)兩個相等的部分，右邊數(shù)組和左邊數(shù)組分別為：(a)(b)(c)圖2匹配度的例子，計算得(b)和(c)的橫向匹配度為：五、模型的建立和求解5.1問題一模型算法的建立與求解5.1.1模型的建立:縱切情況下的拼接復原模型及算法實現(xiàn)假設(shè)原始圖像縱切為個等寬的碎片圖像，記為圖像，。拼接復原的目的是將這些碎片圖像重新排序為圖像，，使得將諸按順序拼接成大的圖像時，能夠復原為原來的原始圖像。1.有序指標集合假設(shè)用一個有序指標集合表示所有碎片圖像的初始順序(打亂了的順序)。如果能夠經(jīng)過有限多步的操作，得到另外一個有序指標集合，其中：，任意兩個，使得所有碎片圖像按照有序指標集合的順序從左向右依次拼接得到正確的原始(大)圖像，則稱的操作是一個可實現(xiàn)的拼接算法。例如碎片圖像個數(shù)為4，初始的有序指標集合為，。第一步先找最左邊的一個碎片，假設(shè)為，則。再找與最匹配的碎片，假設(shè)為，則。再找與最匹配的碎片，假設(shè)為，則。最后剩下的是，則。所以，按照、、、的順序?qū)⑺槠瑘D像從左向右依次拼接，得到的就是原始圖像。對于任意的有序指標集合，將其左數(shù)第個位置的數(shù)設(shè)置為，為了敘述算法時簡潔，這樣的操作簡記為。2.左、右匹配操作的實現(xiàn)再定義兩個操作的縮寫記法和。右匹配操作表示對于碎片圖像，在碎片圖像子集中尋找與圖像的右邊最匹配的碎片圖像的指標：(5)其中是常數(shù)閾值。這是因為兩個碎片圖像的匹配度雖然是比其他的匹配度大，但是如果與0很接近的話，還是不能認為是匹配度。如果沒有找到這樣的碎片圖像指標，則為空集。如果找到唯一的一個指標，則為單個指標的集合。如果找到的指標個數(shù)多于一個，例如和，則為多個指標的集合。在這種情況下，需要額外的處理操作。左匹配操作表示對于碎片圖像，在碎片圖像子集中尋找與圖像的左邊最匹配的碎片圖像的指標：(6)使用這兩個縮寫記號可以使下面的算法敘述更加簡潔。3.左、右拼接操作再定義兩個操作的縮寫記法和。右拼接操作表示以下的多步操作過程：，，；，，；………………或空集，停止。如果，則右拼接全部完成，停止。記，若，則；若，則為多指標集合。右拼接操作的結(jié)果是從碎片圖像集合中的任一個開始，連續(xù)地匹配出多個碎片圖像，使之按順序從左向右拼成大圖像時，能夠成為整個原始圖像的一部分。類似地左拼接操作表示以下的多步操作過程：，，；，，；………………或空集，停止。如果，則左拼接全部完成，停止。記，若，則；若，則為多指標集合。4.左右拼接算法的實現(xiàn)仔細觀察附件給出的碎片圖像，可以發(fā)現(xiàn)：最左邊和最右邊的兩個碎片A和B很容易確定下來，他們的圖像左端和右端均是空白，數(shù)字特征為和，這里表示非零元素個數(shù)：(7)算法步驟如下：(1)初始的有序指標集合，；(2)對圖像進行0-1化處理，并計算左邊數(shù)組和右邊數(shù)組，；(3)計算橫向匹配度矩陣，其中：，(8)(4)查找最左邊的碎片圖像指標：(9)這樣的必定存在，執(zhí)行，。(5)查找最右邊的碎片圖像指標：(10)這樣的必定存在，執(zhí)行，。(6)執(zhí)行右拼接操作，如果，則拼接全部完成，算法停止，輸出計算結(jié)果。如果，轉(zhuǎn)第(7)步。(7)執(zhí)行左拼接操作，如果，則拼接全部完成，算法停止，輸出計算結(jié)果。如果，轉(zhuǎn)第(8)步。(8)這時，指標集合，需要對指標集中剩余的個碎片圖像(,,)進行匹配度排序。前面第(6)步相當于從左指標集合開始向右匹配拼接；第(7)步相當于從右指標集合開始向左匹配拼接。下面的拼接過程與第(6)～(7)步是相似的，只不過左、右指標集是多個，例如：從開始向右匹配拼接、從開始向左匹配拼接，如果拼接完成，即，則算法停止，輸出計算結(jié)果。否則，再從開始向右匹配拼接、從開始向左匹配拼接。即對和循環(huán)，從開始向右匹配拼接、從開始向左匹配拼接，如果拼接完成，即，則算法停止，輸出計算結(jié)果。5.1.2問題一模型的求解利用MATLAB軟件編程（程序見附錄一）對附件1中19個縱切碎片圖像進行計算求解，得到的碎片排序結(jié)果如表一所示，拼接出來的完整復原圖像見附錄一圖1。表一附件1（中文）碎片復原順序表08141215031002160104050913181107170006利用程序（見附錄一）對附件2中19個碎片圖像進行計算求解，得到的碎片排序結(jié)果如表二所示，拼接出來的完整原始圖像見附錄一圖2.表二附件2（英文）碎片復原順序表030602071518110005010913100812141716045.2問題二模型算法的建立和求解5.2.1縱橫切情況下的中文拼接復原模型及算法實現(xiàn)1.碎片圖像的數(shù)字特征無論是中文、還是英文的整片印刷文章，行與行之間的距離是一個固定值，稱之標準行距，單位為像素點數(shù)。每行的最大高度也是固定值，稱之為標準字高，單位為像素點數(shù)。參見圖3。圖3標準行距與標準行高的示意圖2.尋找第一列圖像的方法每個碎片圖像的0-1矩陣為矩陣，令為一個列向量，如果矩陣的某列(列)全為0，則令，否則，令。第一列的11個圖像的最左邊應(yīng)該是連續(xù)數(shù)列全為零（白色），而且這11個圖像左邊全為零的列數(shù)大且相近，同理根據(jù)問題一中的算法，用MATLAB編程求得第一列圖像集合，屬于附件3（漢字）和附件4（英文）第一列的11條碎片圖像序號及其最左端連續(xù)數(shù)列全為零的列數(shù)分別如表三和表四所示。由于第一列的碎片圖像中存在幾條頂端邊緣或(與)底端邊緣不包含文字行，所以暫時不能給第一列圖像按順序排成一列。表三附件3(中文)第一列圖像序號圖像序號71438496171899412529168列數(shù)1211111111111311111211表四附件4（英文）第一列圖像序號圖像序號1920708186132159171191201208列數(shù)13131313111413121213133.拼接成橫條圖像按照第3節(jié)中的算法，先將所有碎片圖像按照從左到右的順序進行拼接，結(jié)果應(yīng)該得到個等寬等高的橫條形的碎片圖像組合，簡稱之為橫條圖像。按照4.1節(jié)中的分析，的最高可能值為19。于是想到一個新的行高相等模型，從中按順序先取出,再從集合中找到與屬于同一行的19條碎片。以后的任務(wù)就是將則個橫條圖像按照正確的順序從上到下進行第二次拼接，最后得到整個的原始圖像。由于行間距的存在，當某條碎片圖像的左邊或右邊的幾列像素點全部為白色的時候，無法判斷該條碎片圖像與其他碎片圖像之間的正確的拼接順序。對于這種情況，我們的想法是使用標準行高來對209塊碎片進一步分類，分成11類定義數(shù)組，其中是1×19的一維數(shù)組，即同一行的19條碎片圖像。通過對所有個橫條圖像的像素點分析，可以統(tǒng)計出標準行高和標準行距的具體數(shù)值。對于附件3中的碎片圖像分析結(jié)果得知：標準行高，標準行距碎片圖像的高度為，由于：或者可知，橫條圖像中至多包含4行文字、3個行間距，或者至多包含3行文字、4個行間距。(a)(b)(c)(d)注：深色方塊為文字行，淺色方塊為行間距行，虛線為橫條圖像的范圍圖5橫條圖像中文字行、間距行的4種可能情況這四種情況可以歸結(jié)為下列特征：(a)橫條圖像底邊包含文字行；(b)橫條圖像頂邊和底邊都不包含文字行；(c)橫條圖像頂邊包含文字行；(d)橫條圖像頂邊和底邊都包含文字行。隨機選取集合中的一條碎片，通過觀察序列，把連續(xù)0段的結(jié)束位置與緊鄰的連續(xù)0段開始的位置之間的間距稱作基準行高（比實際的字行高多2個像素點），然后再分別算出其余碎片相同的位置與之間的間距與基準行高的匹配度，選取匹配度高的前19條碎片圖像，這19條碎片圖像就屬于同一行即同一類。3.1碎片圖像的行高的統(tǒng)計信息每個碎片圖像的0-1矩陣為矩陣，令為一個列向量，如果矩陣的某行(行)全為0，則令，否則，令。、、、表示碎片圖像中所包含的第1、2、3、4個連續(xù)0段的開始位置。、、、表示碎片圖像中所包含的第1、2、3、4個連續(xù)0段的結(jié)束位置。稱為碎片圖像的行高信息矢量。3.2根據(jù)行高信息對碎片圖像進行分組如果一些碎片圖像屬于原始圖像的同一行，則這些碎片圖像對應(yīng)的其中的一行的行高信息矢量應(yīng)該是微差的(即差別比較小)。微差按下面的式子來定義：微差按下面的式子來定義：，這里設(shè)是取的基準碎片圖像上的信息，取的是所有的碎片圖像信息，并且的位置是一定與的位置相同的。，分組過程：在第一列圖像集合中任選一個碎片、或者就選擇碎片。令為空集合。(1)由于一行最多19個碎片，令，用來控制集合中備選碎片的最大個數(shù)。(a),最大允許微差值，從的所有碎片中(除了)中將每個與對應(yīng)的行高的微差的碎片選入集合中。如果集合中碎片個數(shù)遠遠小于，則令，轉(zhuǎn)(a)；(2)進行到這步時，集合中碎片個數(shù)剛好大于等于，并且與對應(yīng)的行高的微差比較小，大部分屬于一組的；但是只有能夠從左向右匹配出來時，才算是真正的屬于同一組。(b)從開始，從中選擇碎片對進行右邊匹配的操作，因為是某行的第一條碎片圖像，有2種情況：(b.1)沒有右匹配；這種情況可能極少見，因為行間距的差距很??；(b.2)有右匹配，此后的過程就是從開始持續(xù)進行右匹配的操作，直到?jīng)]有右匹配時停止；當?shù)?b)結(jié)束時，得到第一個匹配序列如果這個匹配序列的長度足夠長(小于或等于19，或者與19相差不多)，則認為找到了第1個橫條圖像(可能在左右兩端有些許的缺損)。將此匹配序列之外的中的碎片放回到再次選擇的碎片集合中。(2)從之外的碎片中任選一個碎片，重復上述過程，生成第2個、第3個直到第11個橫條圖像?？赡苁Ｏ律贁?shù)幾個碎片沒能被選中，對這些碎片進行人工干預，放入合適的中。4.多個橫條圖像的匹配拼接算法假設(shè)已經(jīng)得到的個橫條圖像為，。首先將所有的分成兩個集合：且為情況(a)、(c)、(d)之一，個數(shù)為且為情況(b)，個數(shù)為算法先不考慮集合，只考慮集合，集合的有序指標集合記為。第(1)步：從集合中任選一個橫條圖像，令：，，在中查找某個，使得除之外的所有與的頂邊縱向匹配度為最大：如果只含有一個橫條圖像，則令：，，如果為空集或者包含個及以上多個橫條圖像，則后續(xù)的操作不再考慮頂邊的匹配，此時令或者。第2步結(jié)束時，，其中為總橫條圖像的個數(shù)。在中查找某個，使得除中的橫條圖像之外的所有與的底邊縱向匹配度為最大：如果只含有一個橫條圖像，則令：如果為空集或者包含個及以上多個橫條圖像，則后續(xù)的操作不再考慮底邊的匹配，此時令或者。上述操作步驟可以用下面的示意圖來表示。第(2)步：從和開始重復第(1)步的操作過程。如果，則可以確定的頂邊相鄰的橫條圖像，否則，或者，則不再向上確定頂邊相鄰的橫條圖像。如果，則可以確定的底邊相鄰的橫條圖像，否則，或者，則不再向上確定頂邊相鄰的橫條圖像。如果且，則無法繼續(xù)向上和向下進行匹配。上述過程得到集合：，，上述操作步驟可以用下面的示意圖來表示。第(3)步：可以看出，當進行到第步時，得到下面的集合：如果，則所有的橫條圖像全部正確排序。如果且，則無法繼續(xù)向上和向下進行進一步的匹配處理。總之，肯定存在某個，使得集合有2部分組成：其中：(a)，或者無法繼續(xù)向上和向下進行進一步的匹配處理；(b)為空集，或者由較少的橫條圖像組成。第(4)步：如果不為空集，則繼續(xù)使用第(1)～(3)的過程，將分解成兩部分：如果：(a)，或者無法繼續(xù)向上和向下進行進一步的匹配處理；(b)為空集，或者由較少的橫條圖像組成。反復執(zhí)行上面的過程，最終得到一系列的集合：、、、、…、、其中：、、、、…為已經(jīng)排好順序的橫條圖像組合；為空集，或者無法排序的橫條圖像的集合；為空集、或者頂邊和底邊均為空白的橫條圖像的集合。5.2.2問題二的求解1．將中文碎片分組拼成橫條ATLAB軟件（程序見附錄二）對模型進行求解，先求得第一列的圖像如上文中的表三和表四所示。接著在求解圖像分組的過程中，可以順利的得到11組的圖像集合，而后再對每組的圖像進行順序匹配拼接成一行通順的圖像橫條。在用MATLAB軟件匹配的過程中，發(fā)現(xiàn)碰到邊界全白的圖像將無法再進行匹配下去，而后再從剩余的圖像中任選一個圖像繼續(xù)拼接，直到每組的圖像拼接成幾個小組塊，這時再通過人工拼接成一條通順匹配的橫條。例如，我們在拼接第一橫條時，其匹配步驟如下：以第49序號的圖像為第一個，MATLAB軟件編程使其向右匹配，匹配到118序號的圖像時，將無法再繼續(xù)匹配，系統(tǒng)停止匹配并記錄匹配好的第一組塊；在從除了第一組圖像的剩余圖像中，隨機找一個圖像繼續(xù)向右匹配，這里隨機找到190序號的圖像并按步驟（1）操作，又找到第二組塊；再從剩余的圖像中隨機找到11序號的圖像并按步驟（1）操作，得到第三組塊。然后再把上述步驟中找到的三個小組塊通過人工干預拼接成一個橫條，如圖六所示。剩余10條橫條圖像組塊見附錄二。第一組塊495465143186257192178118第二組塊19095第三組塊112212928911881414954651431862571921781181909511221292891188141根據(jù)上面的三個組塊，通過一次人工干預的方法得出第一條橫條序列如表六。表六第一橫條人工干預最終拼接結(jié)果2．對中文多條橫條圖像的匹配拼接利用MATLAB軟件編程（程序見附錄二）對已經(jīng)排好的中文的11條橫條圖像進行縱向拼接復原，先從11條橫條圖像中隨機選擇一個橫條圖像并對其進行縱向匹配，從軟件自動匹配出的復原圖中發(fā)現(xiàn)有幾個橫條明顯匹配錯誤，這時只要人工干預對出錯的復原圖進行微小的跳動就可以拼接成正確的復原圖。表七.附件3（中文）碎片排列順序表第1列第2列第3列第4列第5列第6列第7列第8列第9列第10列第1行7115683132200178033202198第2行8914610215411440151207155140第3行495465143186257192178118第4行6119786769991629613179第5行1681007662142304123147191第6行3814846161243581189122103第7行141283159821991351273160第8行943484183904712142124144第9行125131821091971618411018766第10行2964111201592180483775第11行720813815812668175451740第11列第12列第13列第14列第15列第16列第17列第18列第19列第1行15133170205851521652760第2行1851081174101113194119123第3行1909511221292891188141第4行63116163726177205236第5行50179120861952618718第6行13019388167258910574第7行203169134393151107115176第8行77112149971361641275843第9行10615021173157181204139145第10行5544206101049817217159第11行13753569315370166321963.對英文碎片的拼接復原.對于英文碎片的拼接復原我們采用問題三中的模型，通過問題三的算法，我們通過程序運行得出英文碎片的排列順序如表八。表八.附件3（英文）碎片排列順序表第1列第2列第3列第4列第5列第6列第7列第8列第9列第10列第1行1917511154190184210418064第2行2011481701961989411316478103第3行865110729401581869824117第4行191949314188121126105155114第5行1591391129631381535338123第6行2041108116136733620713515第7行20821749611193314216862第8行7084601468174137195847第9行1321819569167163166188111144第10行1714266205101577414583134第11行81771282001315212514019387第11列第12列第13列第14列第15列第16列第17列第18列第19列第1行106414932204653967147第2行91801012610061728146第3行1505595892303746127第4行17618215122572027116582第5行12017585501601879720331第6行76431994517379161179143第7行16954192133118189162197112第8行17215696239912290185109第9行206313034131102527178第10行5518563516918315244第11行8948721217712401021155.3問題三模型算法的建立和求解5.3.1模型的建立：縱橫切情況下的英文拼接復原模型及算法實現(xiàn)在文章原文為英文的情況下，由于英文字母的筆畫不像漢字那樣多，并且漢字的橫豎筆畫比較多，而英文字母的“圓圈”或“半圓圈”的情況比較多，使得整篇文章在縱橫切的情況下行程的碎片圖像中、相鄰碎片圖像的水平和豎直方向的連續(xù)性減弱，進而影響相鄰性的判斷的正確性。解決這個問題(適用于附件4和附件5)的解決思路是這樣的：第一步，還是想辦法將諸多碎片圖像拼接成多個橫條圖像，每個橫條圖像的頂部和底部都有對于一行的全空白行。第二步，根據(jù)每個橫條圖像中每行與行之間的空白行的上下距離進行統(tǒng)計分析，按照等間距原則對諸多橫條圖像進行初步排序，將大部分的橫條圖像拼接成數(shù)目較少的更大的橫條圖像(稱為段落圖像)，這個過程中可能需要進行人工干預。第三步，將上步得到的數(shù)目較少的段落圖像進行人工排序，排序的原則是整片文章的連續(xù)可讀性。1．碎片圖像的鄰接性的描述看一下下面的英文字母表(字體為TimesNewRoman)。abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ可以發(fā)現(xiàn)，這些字母分成以下幾組：(1)組E1，知道較大左部分可以唯一判斷出剩余的右部分的；(2)組E2，知道較大右部分可以唯一判斷出剩余的左部分的；(3)組E3，知道較大上部分可以唯一判斷出剩余的下部分的；(4)組E4，知道較大下部分可以唯一判斷出剩余的上部分的；(5)組E5，知道較大左上部分可以唯一判斷出剩余的其他部分的；(6)組E6，知道較大右上部分可以唯一判斷出剩余的其他部分的；(7)組E7，知道較大左下部分可以唯一判斷出剩余的其他部分的；(8)組E8，知道較大右下部分可以唯一判斷出剩余的其他部分的；利用這個特征，可以定義新的連接性(連接系數(shù))，使得碎片圖像的鄰接匹配更加準確。2.圖像的E鄰接性的提取假設(shè)碎片圖像的寬度和高度分別為和，英文字母E的寬度和高度分別為和，在碎片圖像上建立以左上角為坐標原點、橫軸向右方、縱軸向下方的直角坐標系。定義幾個變量：為坐標原點，為碎片圖像的右下角的坐標，為某個大于0.5的比例系數(shù)，,,,，，，再定義提取范圍：通過對字母圖像與碎片圖像上述8個矩形的像素對比，提取出下面的信息：例如，對于，如果字母在此區(qū)域中，則記錄字母與相交的位置坐標及個數(shù)。對于字母表中的所有字母，都進行上述提取過程，形成一個鏈表list，其節(jié)點數(shù)據(jù)為：字母的序號；在的哪個里面；與等相交部分的(碎片圖像的局部坐標系)位置數(shù)據(jù)。3.利用碎片圖像的E鄰接性進行橫條拼接的算法(1)事先把所有碎片圖像的E鄰接性數(shù)據(jù)統(tǒng)計出來，存為文件以備多次反復使用；(2)從所有碎片圖像中，查找E鄰接性最好(有最多的相交數(shù)據(jù))的某個碎片圖像作為第1個；將添加入橫條之中(3)從所有的碎片圖像中查找與具有E鄰接性的上左、上、上右、右、右中、右下、下、左下、左的，如果這8個鄰居至少有1個一地確定，例如，則將其添加到橫條之中，在的適當方向上。如果沒有找到這樣的，則從所有碎片圖像中再次查找除之外的E鄰接性最好的，記為，重復這個過程直到能唯一確定出至少一個鄰居。(4)從開始考慮除方向之外的其他方向的鄰居。 (5)反復進行上述過程，直到形成橫條圖像為止。橫條的特征是上邊幾行和下邊幾行都是全空白行。也有可能的某些位置上的碎片是空白的，這留到以后進行人工干預時再填補上。(6)從除之外的任選碎片開始，重復(2)～(5)的過程，找出第2、3、4…個橫條圖像，直到無法再形成新的橫條圖像為止。這樣之后，可能剩余很少部分的碎片圖像不再這些橫條圖像之中。(7)用橫條圖像的行間距等距的特點，對諸進行從上到下的排序，將盡可能多的排成正確的順序。(8)對在排序中沒有能正確排序的那些進行人工排序，最后形成整個的一個或者多個大塊圖像，這樣的大塊圖像就是最終的拼接結(jié)果。當大塊圖像只有一個時，所有碎片來自同一張紙。如果大塊圖像有多個時，這些碎片可能來自于多頁紙(例如對于附件5的碎片)。5.3.2問題三的求解：根據(jù)問題三中對碎紙片的復原算法，運用C++Builder編程，運行程序得到復原圖像拼接順序如下表。表九附件五正面圖像拼接排列順序78b111b125a140a155a150a183b174b110a66a108a18b29a189b81b164b20a47a136b89a10b36a76b178a44a25b192a124b22a144a144a79a14a59a60b147a152a5a186b153a84b42b30a38a121a98a94b61b45a45a138a56b131b187b86b200b143b199b11b161a169b194b173b206b156a34a181b87a87a132b93a72b175a97a39b83a88b107a149b180a37b191a65b115b166b1b170b170b41a70b139b2a162b203b90a114a184b179b116b207a58a158a197a154b28b17b17b102b64b208a142a57a24a13a146a171b31a201a50a190b92b19b16b177b202a202a21b130a163a193b73b159a35a165b195a128a157a168a46a67a63b75b167a8b8b68b188a127a40a182b122a172a3b7b85b148b77a4a69a32a74b126b185a185a0b80b27a135b141a204b105a23b133a48a51b95a160b119a33b71b52a129b129b118b101a15b205a82b145a9b99a43a96b109a123a6a104a134a113a26b91a91a106b100b55b103a112a196b54b表十附件五反面復原圖像排列順序78a111a125b140b155b150b183a174a110b66b108b18a29b189a81a164a20b47b136a89b10a36b76a178b44b25a192b124a22b144b144b79b14b59b60a147b152b5b186a153b84a42a30b38b121b98b94a61a45b45b138b56a131a187a86a200a143a199a11a161b169a194a173a206a156b34b181a87b87b132a93b72a175b97b39a83b88a107b149a180b37a191b65a115a166a1a170a170a41b70a139a2b162a203a90b114b184a179a116a207b58b158b197b154a28a17a17a102a64a208b142b57b24b13b146b171a31b201b50b190a92a19a16a177a202b202b21a130b163b193a73a159b35b165a195b128b157b168b46b67b63a75a167b8a8a68a188b127b40b182a122b172b3a7a85a148a77b4b69b32b74a126a185b185b0a80a27b135a141b204a105b23a133b48b51a95b160a119b33a71a52b129a129a118a101b15a205b82a145b9a99b43b96a109b123b6b104b134b113b26a91b91b106a100a55a103b112b196a54a六、模型的評價根據(jù)對這三個問題的詳細分析，使用和提出了各種圖像預處理技術(shù)、圖像數(shù)字特征的提取、拼接算法。算法主要利用碎片的數(shù)字特征，定義其與其他碎片的鄰接系數(shù)，利用鄰接系數(shù)在碎片集合中查找最匹配的碎片，從而完成拼接復原過程。使用附件1--附件5中的對本文給出的算法進行了測試，基本上都能實現(xiàn)每個附件文件集的正確復原。七、參考文獻[1]羅智中.基于文字特征的文檔碎紙片半自動拼接[J].計算機工程與應(yīng)用,2012,48(5):207-210.[2]鐘家強，王潤生.基于邊緣的圖像配準改進算法[J].計算機工程與應(yīng)用,2001，23(6):25-29.[3]王磊，莫玉龍，戚飛虎.基于Canny理論的邊緣提取改善方法[J].中國圖像圖形學報,1996,1(3):191-195.[4]陶波，于志偉，鄭筱祥.圖像的自動拼接[J].中國生物醫(yī)學工程學報，1997，16(4)：29-35.附錄一問題一程序：clc;clearall;img={};fori=1:19str=strcat('D:\MATLAB\R2012a\bin\附件1\',sprintf('%03d',i-1),'.bmp');img{i}=imread(str);endImg=img;fori=1:19Boundary=img{i};fork=1:1980form=1:72ifBoundary(k,m)==255Boundary(k,m)=0;elseBoundary(k,m)=1;endendendimg{i}=[Boundary(:,1),Boundary(:,72)];endCount=zeros(1,19);result=zeros(1,19);fori=1:19Boundary=img{i};ifBoundary(:,1)==0result(:,1)=i-1;break;endendfori=1:18Boundary1=img{result(:,i)+1};forj=1:19Boundary2=img{j};fork=1:1980ifBoundary1(k,2)==Boundary2(k,1)Count(:,j)=Count(:,j)+1;local=find(Count==max(Count));result(:,i+1)=local(1,1)-1;endendendCount(:,:)=0;endresultRestoreimg=[];fori=1:19Restoreimg=[RestoreimgImg{result(i)+1}];endimshow(Restoreimg)問題一復原圖片：圖1附件1的拼接復原圖圖2附件2的拼接復原圖附錄二clc;clearall;Img={};fori=1:209str=strcat('D:\MATLAB\R2012a\bin\附件3\',sprintf('%03d',i-1),'.bmp');Img{i}=imread(str);endimg=Img;fori=1:209fork=1:180form=1:72ifimg{i}(k,m)==255img{i}(k,m)=0;elseimg{i}(k,m)=1;endendendendLeft=zeros(209,72);Up=zeros(209,72);fori=1:209forj=1:72ifsum(img{i}(:,j))~=0Left(i,j)=1;elseLeft(i,j)=0;endendendCount3=zeros(1,209);fori=1:209forj=1:72ifLeft(i,j)==0Count3(:,i)=Count3(:,i)+1;elsebreak;endendendfori=1:209forj=1:180ifsum(img{i}(j,:))~=0Up(i,j)=1;elseUp(i,j)=0;endendendUp=Up';Count1=zeros(1,209);fori=1:209forj=1:180ifUp(j,i)==0Count1(:,i)=Count1(:,i)+1;