碎紙片的拼接復(fù)原數(shù)學(xué)模型1

1、碎紙片的拼接復(fù)原數(shù)學(xué)模型摘要首先對(duì)圖片進(jìn)行灰度化處理，然后轉(zhuǎn)化為0-1二值矩陣，利用矩陣行（列）偏差函數(shù)，建立了基于最小二乘法的碎紙片拼接數(shù)學(xué)模型，并利用模型對(duì)圖片進(jìn)行拼接復(fù)原。本文主要研究了規(guī)則碎紙片的拼接復(fù)原問(wèn)題。首先利用二值法、環(huán)形像素點(diǎn)匹配等算法建立基于像素點(diǎn)數(shù)值匹配模型，然后利用MATLAB軟件對(duì)碎紙片像素點(diǎn)進(jìn)行數(shù)字化處理，得到各碎紙片的像素點(diǎn)數(shù)值矩陣，再利用MATLAB軟件編程進(jìn)行矩陣特征優(yōu)化匹配得到復(fù)原圖。針對(duì)問(wèn)題一，當(dāng)兩個(gè)數(shù)字矩陣列向量的偏差函數(shù)最小時(shí)，對(duì)應(yīng)兩張圖片可以左右拼接。經(jīng)計(jì)算，得到附件1的拼接結(jié)果為：9,15,13,16,4,11,3,17,2,5,6,10,14,1

2、9,12,8,18,1,7附件2的拼接結(jié)果為:4,7,3,8,16,19,12,1,6,2,10,14,11,9,13,15,18,17,5針對(duì)問(wèn)題二：本文采用聚類(lèi)分析方法建立優(yōu)化模型。將所有圖片的像素轉(zhuǎn)化為矩陣，其次采用人工干預(yù)的方式找出第一行第一張碎紙片，然后將所有圖片灰度二制化，將灰色像素值轉(zhuǎn)化為黑色像素值，然后由上至下找出黑白像素的分界線，根據(jù)分界線位置的差異值最小聚合出第一行所有的圖片，同理聚合出第一列所有的圖片，將第一行所有圖片利用問(wèn)題一的拼接算法求解出第一行圖片拼接順序。以第一行第一張碎紙片下側(cè)像素點(diǎn)與其他碎紙片上側(cè)像素點(diǎn)像素匹配差異值最小為目標(biāo)函數(shù)，依次窮舉第一列所有的碎紙片，

3、從而找出第二行第一張碎紙片。根據(jù)第一行排好順序的碎紙片以及第二行第一張碎紙片，采用上下側(cè)邊緣像素匹配以及左右側(cè)邊緣匹配，依次找出并排列好第2行，其他行依理重復(fù)步驟（2）、（3）即可。完成匹配后，進(jìn)行適當(dāng)?shù)娜斯じ深A(yù)即可確定碎紙片的復(fù)原圖。（見(jiàn)附錄3、4圖11，圖12）。最后，本文對(duì)所建模型的優(yōu)點(diǎn)和缺點(diǎn)進(jìn)行了客觀的評(píng)價(jià)，認(rèn)為本文研究的結(jié)果在圖像拼接問(wèn)題中有一定的參考價(jià)值。關(guān)鍵詞：灰度處理，圖像二值化，最小二乘法，聚類(lèi)分析，碎紙片拼接一、問(wèn)題重述碎紙片的拼接復(fù)原技術(shù)在司法鑒定、歷史文獻(xiàn)修復(fù)與研究、軍事情報(bào)獲取以及故障分析等領(lǐng)域都有著廣泛的應(yīng)用。近年來(lái)，隨著德國(guó)“斯塔西”文件的恢復(fù)工程的公布，碎紙文件

4、復(fù)原技術(shù)的研究引起了人們的廣泛關(guān)注。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時(shí)間內(nèi)完成任務(wù)。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們?cè)噲D開(kāi)發(fā)碎紙片的自動(dòng)拼接技術(shù)，以提高拼接復(fù)原效率。對(duì)于一頁(yè)印刷文檔，針對(duì)不同的破碎方法，討論下列三個(gè)問(wèn)題：（1）將給定的一頁(yè)印刷文字文件縱切，建立碎紙片拼接復(fù)原模型和算法，并針對(duì)附件1、附件2給出的中、英文各一頁(yè)文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。（2）對(duì)于碎紙機(jī)既縱切又橫切的情形，設(shè)計(jì)碎紙片拼接復(fù)原模型和算法，并針對(duì)附件3、附件4給出的中、英文各一頁(yè)文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。（3）對(duì)于雙面打印文檔，研究如何進(jìn)行碎紙片的拼接復(fù)原

5、問(wèn)題。附件5給出的是一頁(yè)英文印刷文字雙面打印文件的碎片數(shù)據(jù)。要求嘗試設(shè)計(jì)相應(yīng)的碎紙片拼接復(fù)原模型與算法，并就附件5的碎片數(shù)據(jù)給出拼接復(fù)原結(jié)果。二、模型的基本假設(shè)1、待拼接的碎紙片來(lái)自同一頁(yè)印刷文字文件。2、待拼接復(fù)原的碎紙片是規(guī)整的矩形。3、模型中的碎紙片長(zhǎng)度、寬度和面積都相等。4、附件中照片都是同標(biāo)準(zhǔn)拍攝。三、符號(hào)說(shuō)明表1 符號(hào)說(shuō)明符號(hào)符號(hào)說(shuō)明灰度值紅色綠色藍(lán)色矩陣裁截距裁截文字長(zhǎng)度行間距裁截空白距離字體高度四、問(wèn)題分析將不規(guī)則的文檔碎紙片進(jìn)行拼接，一般是利用碎紙片的邊緣曲線，尖點(diǎn)、尖角、面積等幾何特征，搜索與之匹配的相鄰碎紙片。但對(duì)于邊緣形狀相似的碎紙片，這種基于邊界幾何特征的拼接方法失效

6、，拼接時(shí)不但要考慮待拼接碎紙片邊緣是否匹配，還要判斷碎片內(nèi)的字跡斷線或碎片內(nèi)的文字內(nèi)容是否匹配。本問(wèn)題給定的碎紙片有以下幾個(gè)特點(diǎn)：1、每一張碎紙片都是規(guī)整的矩形；2、所有的碎紙片的長(zhǎng)度、寬度都相等，形狀是完全一樣的；3、每一張碎紙片里都包含著文字（漢字、英文），不存在空白的碎紙片；4、不同的碎紙片之間沒(méi)有重疊部分。由于碎紙片的形狀相同，因而不能針對(duì)碎紙片的幾何特征建立數(shù)學(xué)模型；碎紙片間無(wú)重疊，也不能利用圖像融合技術(shù)進(jìn)行圖像配準(zhǔn)。根據(jù)上述分析，我們考慮將圖片進(jìn)行數(shù)字化處理，根據(jù)每張碎紙片上的邊緣文字特征進(jìn)行匹配，也就是利用圖片邊緣文字的像素進(jìn)行最優(yōu)化匹配。五、模型的建立與求解5.1問(wèn)題一的建模與

7、算法 由于碎紙片本身不具有體現(xiàn)其拼接特性的數(shù)字特征，我們需要將其數(shù)字化、矩陣化，將問(wèn)題轉(zhuǎn)化為矩陣之間的相關(guān)性。5.1.1圖片的灰度處理為了對(duì)碎紙片進(jìn)行數(shù)字化，我們將圖像進(jìn)行灰度處理，取出圖像中每一個(gè)像素點(diǎn)的灰度值。通過(guò)MATLAB的imread函數(shù)讀入灰度圖， dither函數(shù)轉(zhuǎn)化為二值圖，進(jìn)一步得到圖像數(shù)據(jù)矩陣，每張圖片對(duì)應(yīng)一個(gè)的灰度矩陣。5.1.2圖片的二值化處理將圖片進(jìn)行灰度處理以后，每個(gè)像素的灰度值介于0255之間?；叶戎挡荒苤苯佑糜谖淖謭D片的拼接，還須進(jìn)行二值化處理。將圖片放入直角坐標(biāo)系，規(guī)定：若點(diǎn)的像素灰度值大于或等于T，該點(diǎn)用數(shù)值表示，并將其設(shè)定為白色；若點(diǎn)的像素灰度值小于T，該

8、點(diǎn)用數(shù)值表示，并將其設(shè)定為黑色。由此得到像素點(diǎn)的二值化函數(shù)：其中，為預(yù)先設(shè)定的全局灰度閾值。于是，每張圖片的灰度矩陣轉(zhuǎn)化為下列的數(shù)字矩陣：,其中5.1.3最小二乘法1、圖片左右拼接的數(shù)學(xué)模型 設(shè)分別表示左右放置的兩張圖片對(duì)應(yīng)的數(shù)字矩陣，定義前一個(gè)矩陣的最后一列與后一個(gè)矩陣的第一列之間的偏差函數(shù)為：其中，分別表示矩陣第列和第列的元素。對(duì)于給定的矩陣，若存在矩陣，使得與之間的偏差函數(shù)達(dá)到最小，則稱(chēng)與可以匹配，此時(shí)與對(duì)應(yīng)的圖片可以左右拼接。2、圖片上下拼接的數(shù)學(xué)模型 類(lèi)似地，設(shè)分別表示上下放置的兩張圖片對(duì)應(yīng)的數(shù)字矩陣，定義上面矩陣的最后一行與下面矩陣的第一行之間的偏差函數(shù)為：其中，分別表示矩陣第行和

9、第行的元素。 對(duì)于給定的矩陣，若存在矩陣，使得與之間的偏差函數(shù)達(dá)到最小，則稱(chēng)與可以匹配，此時(shí)與對(duì)應(yīng)的圖片可以上下拼接。我們稱(chēng)上述基于數(shù)字矩陣之間列（或行）距離的圖片拼接模型為最小二乘法拼接復(fù)原模型。5.1.4算法與求解（一）算法思想第一步，對(duì)附件中的19幅圖片分別進(jìn)行灰度處理，然后取灰度閾值T=125，進(jìn)行二值化，得到19個(gè)數(shù)字矩陣，即圖片的數(shù)字化。第二步，對(duì)上述19個(gè)數(shù)字矩陣進(jìn)行檢測(cè)，若存在一個(gè)矩陣的最左側(cè)一列元素全是1，根據(jù)破碎圖片的特點(diǎn)，則該圖片即為從左邊起第一張碎紙片，記為。第三步，計(jì)算與其余18張圖片對(duì)應(yīng)矩陣的列偏差值。若存在，使得達(dá)到最小，則即位第二張圖片。重復(fù)上述的步驟，依次得到

10、所有碎紙片的排列，即可拼接成完整圖片。（二）附件1、2的拼接復(fù)原結(jié)果附件1和附件2的拼接順序如下表：（附件1的算法程序見(jiàn)附錄一，復(fù)原圖片見(jiàn)附錄二；附件2的算法程序見(jiàn)附錄三，復(fù)原圖片見(jiàn)附錄四）表2 附件1拼接順序91513164113172561014191281817表3 附件2拼接順序4738161912162101411913151817552問(wèn)題二模型的建立與求解5.2.1問(wèn)題二分析該問(wèn)題的目標(biāo)是建立最合適的碎紙片拼接復(fù)原模型和算法來(lái)復(fù)原既縱切又橫切的圖片。問(wèn)題二與問(wèn)題一的區(qū)別在于碎紙片的切割由縱切變成了既有縱切又有橫切的，所以問(wèn)題一采用的人工干預(yù)找出第一張圖片及簡(jiǎn)單地通過(guò)前后兩張碎紙片

11、的偏差值進(jìn)行排列會(huì)產(chǎn)生相當(dāng)大的誤差，因此我們擬采用聚類(lèi)分析方法建立優(yōu)化模型來(lái)拼接附加3和附加4中的碎紙片。（1）我們?nèi)斯じ深A(yù)選出一組上側(cè)留有空白的圖片作為備選圖片，以及選取一張左側(cè)跟上側(cè)都留有空白的圖片作為拼接的第一張圖片，其次將選取的第一張圖片為基準(zhǔn)采用相應(yīng)的拼合算法不斷的向左向下匹配下一張圖片。對(duì)于碎紙片上的文字處理可采取以下方式： 圖1：附錄3碎紙片文字像素處理圖首先用Matlab中的imread（）函數(shù)讀取圖片，將圖片像素轉(zhuǎn)化為相應(yīng)的矩陣，其次將矩陣中處于0255之間的數(shù)值所在的行的全部數(shù)值轉(zhuǎn)化為0（即將所有灰色像素點(diǎn)轉(zhuǎn)換為黑色像素點(diǎn)，并將其所在的行全部轉(zhuǎn)化為黑色像素點(diǎn)），然后由上至下

12、找出黑白像素的分界線，并依次將第一張圖片的分界線與其他圖片的分界線進(jìn)行差異匹配，從而分類(lèi)聚合出第一行所有的圖片。（2）利用問(wèn)題一中的拼接算法，以第一張圖片右側(cè)邊緣像素點(diǎn)與第一行所有圖片左側(cè)邊緣像素點(diǎn)像素匹配差異值最小為目標(biāo)函數(shù)，建立優(yōu)化模型，從而排列出第一行所有圖片的順序。（3）同理，將剩余圖片像素矩陣中處于0255之間的數(shù)值所在的列的全部數(shù)值轉(zhuǎn)化為0，然后由左至右找出黑白像素的分界線，并依次將第一張圖片的分界線與其他圖片的分界線進(jìn)行差異匹配，從而分類(lèi)聚合出第一列所有的圖片。（4）改進(jìn)問(wèn)題一中的算法，以第一張圖片下側(cè)邊緣像素點(diǎn)與第一列所有圖片上側(cè)邊緣像素點(diǎn)像素匹配差異值最小為目標(biāo)函數(shù)，建立優(yōu)化

13、模型，從而確定出第二行第一張碎紙片，然后將第二行第一張碎紙片的右側(cè)邊緣像素點(diǎn)與待排圖片左側(cè)邊緣像素點(diǎn)以及與上一行中對(duì)應(yīng)圖片下側(cè)邊緣像素點(diǎn)與待排圖片上側(cè)邊緣像素點(diǎn)的像素匹配差異值最小為目標(biāo)函數(shù)，建立優(yōu)化模型，依次窮舉出所有未排序的圖片，找出第二行第一張碎紙片。其他行碎紙片依照此理類(lèi)推即可排出順序。（5）所有圖片匹配完成后，對(duì)于拼接錯(cuò)誤的圖片進(jìn)行相應(yīng)的人工干預(yù)即可求得最后的圖像復(fù)原圖。5.2.2問(wèn)題二模型準(zhǔn)備（1）圖片像素的量化和圖片貼近度考慮到要根據(jù)圖片之間的像素貼近度進(jìn)行匹配，需要用Matlab軟件將碎紙片像素量化，將像素分布轉(zhuǎn)化為相應(yīng)的數(shù)據(jù)。為此，我們采用了imread（）函數(shù)，將各圖片轉(zhuǎn)化

14、成由像素構(gòu)成的矩陣，方便了matlab對(duì)圖片匹配的處理操作。圖片貼近度用以描述兩張圖片的相近程度，主要由兩張圖片的像素決定。兩張圖片像素匹配差異值越小，圖片貼近度越高；反之，圖片貼近度越低。（2）圖片聚類(lèi)分析方法數(shù)學(xué)建模中，研究對(duì)樣品或指標(biāo)分類(lèi)的一種多元統(tǒng)計(jì)方法，是依據(jù)研究對(duì)象的個(gè)體的特征進(jìn)行分類(lèi)的方法。聚類(lèi)分析的基本思想是認(rèn)為我們研究的樣本或指標(biāo)之間存在著程度不同的相似性。于是根據(jù)一批樣本的觀察指標(biāo)，具體找出想死程度較大的樣本聚為一類(lèi)，關(guān)系密切的聚到一個(gè)小的分類(lèi)單位，關(guān)系疏遠(yuǎn)的聚到一個(gè)大的分類(lèi)單位，直到所有樣本聚合完畢。這樣就形成了一個(gè)個(gè)類(lèi)，大大減少了數(shù)據(jù)處理的難度。在圖片拼接過(guò)程中，將碎紙

15、片圖像量化得到的矩陣中數(shù)值處于0255（白色的像素值為255，黑色的像素值為0）之間的數(shù)所在的行或列中所有的數(shù)值全部轉(zhuǎn)化為0，找出黑白像素的分界線，根據(jù)分界線的匹配度進(jìn)行聚合分類(lèi)。5.2.3問(wèn)題二模型的建立圖2：?jiǎn)栴}二模型求解流程圖（1）碎紙片預(yù)處理 預(yù)處理的目的是將待處理物體表示為適合于計(jì)算機(jī)處理的形式。對(duì)于碎紙片來(lái)說(shuō)，就是將其像素化、數(shù)字化，為此，我們利用Matlab軟件中的imread（）函數(shù)對(duì)碎紙片進(jìn)行量化，由于題目中所給的碎紙片圖像分辨率都是，所以我們將每張碎紙片都轉(zhuǎn)換成了的矩陣。（2）碎紙片聚類(lèi)分析及匹配 在碎紙片聚類(lèi)過(guò)程中，首先將所有圖片得到的像素矩陣灰度二制化，將灰色像素值轉(zhuǎn)化

16、為黑色像素值，由上至下找出黑白像素分界線，根據(jù)上側(cè)跟左側(cè)都留有白的特性人工干預(yù)找到第一張圖片，然后以與第一張圖片黑白像素分界線與其他圖片黑白像素分界線差異值最小為目標(biāo)函數(shù)建立優(yōu)化模型，目標(biāo)函數(shù)如公式（1）所示。.目標(biāo)函數(shù)如下:我們根據(jù)分界線位置的差異值最小，對(duì)碎片預(yù)處理得到的像素矩陣，聚類(lèi)分析得到第一行所有的圖片，同樣運(yùn)用聚合分析的思想得到第一列所有的圖片，根據(jù)問(wèn)題一的匹配方法求出第一行圖片的拼接順序。拼接效果如圖3所示。 圖3：聚類(lèi)出的第一行的拼接效果圖然后以第一行第一張碎紙片下側(cè)像素點(diǎn)與其他碎紙片上側(cè)像素點(diǎn)像素匹配差異值最小為目標(biāo)函數(shù)，目標(biāo)函數(shù)如公式（2）所示。目標(biāo)函數(shù)： 依次窮舉第一列所

17、有的碎紙片，找出第二行第一張碎紙片。其次，根據(jù)第一行排好順序的碎紙片以及第二行第一張碎紙片，采用上下側(cè)邊緣像素匹配以及左右側(cè)邊緣匹配，目標(biāo)函數(shù)如公式（3）所示。目標(biāo)函數(shù)：依次找出并排列好第2行，拼接效果圖如圖4所示：圖4：第二行的拼接效果圖重復(fù)上述兩個(gè)步驟即可得到其余各行的排列順序。（3）人工干預(yù)及繪圖觀察通過(guò)Matlab的imshow()對(duì)聚類(lèi)分析及匹配得到的圖片順序的圖像，調(diào)整不吻合的圖片，逐步使得得到的圖像準(zhǔn)確。5.2.4問(wèn)題二模型的求解利用聚類(lèi)分析求解出的附件3跟附件4第一行圖片排列順序見(jiàn)下表：表4：附錄3中采用聚合分析得出的第一行圖片順序49546514318625719217811

18、81909511221292891188141 表5：附錄4中采用聚合分析得出的第一行圖片順序1917511154190184210418064106414932204653967147利用聚類(lèi)分析求解出的附件3跟附件4第一列圖片排列順序見(jiàn)下表： 表6：附錄3中采用聚合分析得出的第一列圖片順序49611683814941252977189表7：附錄4中采用聚合分析得出的第一列圖片順序1912018619159202087013217181附件3圖片最終拼接順序見(jiàn)表8，拼接圖見(jiàn)附錄六。表8 附件3拼接順序4954651431862571921781181909511221292891188141

19、611978676999162961317963116163726177205236168100766214230412314719150179120861952608718381484616124358118912210313019388167258910574141283159821991351273160203169134393151107115176943484183904712142124144771121499713616412758431251318210919716184110187661061502117315718120413914529641112015921804837

20、755544206101049817217159720813815812668175451741137535693153701663219671156831322001780332021981513317020585152165276089146102154114401512071551401851081174101113194119123附件4圖片最終拼接順序見(jiàn)表9，拼接圖見(jiàn)附錄八。表9 附件4拼接順序191751115419018421041806410641493220465396714720114817019619894113164781039180101261006172814686

21、511072940158186982411715055958923037461271919493141881211261051551141761821512257202711658215913911296313815353381231201758550160187972033120411081161367336207135157643199451737916117914320821749611193314216862169541921331181891621971127084601468174137195847172156962399122901851091321819569167163166

22、1881111442063130341311025271781714266205101577414583134551856351691831524481771282001315212514019387894872121771240102115六、模型分析與評(píng)價(jià)6.1模型的優(yōu)點(diǎn)（1）在進(jìn)行拼接4張圖片之前都進(jìn)行了簡(jiǎn)單地人工干預(yù)來(lái)確定第一張圖片，由此可以大大提高后來(lái)圖片拼接模型的運(yùn)行效率。（2）問(wèn)題一建立的通過(guò)像素匹配差異值最小為目標(biāo)函數(shù)，通過(guò)循環(huán)來(lái)窮舉剩余圖片，比較相鄰圖片貼近度來(lái)建立模型求解，簡(jiǎn)單明了，易于理解，并且可操作性較強(qiáng)。（3）問(wèn)題二采取的聚類(lèi)分析方法層次分明，邏輯清晰，并且能有效減少

23、運(yùn)算量，提高精確度，因此提高的拼接碎紙片的效率。（4）總的來(lái)說(shuō)，我們采用的模型理解較為容易，也便于操作，對(duì)碎紙片拼接的問(wèn)題有較高的參考價(jià)值。6.2模型的缺點(diǎn)（1）我們?cè)谄唇铀榧埰^(guò)程當(dāng)中自始至終都運(yùn)用了位圖像素點(diǎn)的概念，要理解建立的模型，需要對(duì)計(jì)算機(jī)的圖像處理知識(shí)有一定的了解。（2）我們?cè)诟鱾€(gè)問(wèn)題碎紙片拼接之前進(jìn)行了人工干預(yù)選出第一張，如果選擇的第一張不夠準(zhǔn)確，可能造成建立的整個(gè)模型完全錯(cuò)誤，因此有一定的難度來(lái)選擇第一張圖片，這給使用此模型的人增加了對(duì)圖片觀察力和分析力的要求。（3）此模型中需要適當(dāng)?shù)娜斯じ深A(yù)來(lái)調(diào)整初步確定的圖片模型，因此需要使用此模型的人了解模型的細(xì)節(jié)以便進(jìn)行適時(shí)的人工干預(yù)。

24、6.3模型的改進(jìn)（1）由于問(wèn)題一要求排列的圖片較少，因此可以依此選擇各個(gè)圖片作為第一張，自動(dòng)的進(jìn)行拼接，最后從每張圖片作為第一張的得到圖片序列中，根據(jù)總的貼近度最大原則，選出最優(yōu)的排列。（2）我們問(wèn)題二中僅采用從上到下、從左到右的方法進(jìn)行搜索排序，如果再進(jìn)行從從上到下，從右到左進(jìn)行搜索排序，應(yīng)該可以通過(guò)人工干預(yù)對(duì)比來(lái)更容易的實(shí)現(xiàn)排序。參考文獻(xiàn)1姜啟源等，數(shù)學(xué)模型（第四版），北京：高等教育出版社，2011 2羅智中，基于線段掃描的碎紙片邊界檢測(cè)算法研究J儀器儀表學(xué)報(bào)，2011,32（2）：289-294.2白宗文，基于HALCON與圖像拼接的文物修復(fù)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)J，電子設(shè)計(jì)工程，2013,21

25、（9）：24-26.3Huei-Yung等，Reconstruction of shredded document based on image feature matching，Expert Systems with Applications，第39卷，第3期，3324-3332， 2012。4黃添強(qiáng)，陳智文，蘇立超等利用內(nèi)容連續(xù)性的數(shù)字視頻篡改檢測(cè)J，南京大學(xué)學(xué)報(bào)（自然科學(xué)版），2011,47（5）：493-503.5羅智中，基于線段掃描的碎紙片邊界檢測(cè)算法研究J儀器儀表學(xué)報(bào)，2011,32（2）：289-294.6李利軍，李云偉，基于圖像灰度的拼接技術(shù)研究J，計(jì)算機(jī)與數(shù)字工程，2007,

26、35（9）：128-130.7賈海燕，朱良家，周宗潭等，一種碎紙自動(dòng)拼接中的形狀匹配方法J，計(jì)算機(jī)仿真，2006,23（11）：180-183.附錄附錄一：clear,clc;A=zeros(19,19); for j=1:19str=C:UsersAdministratorDesktop第六輪題目第六輪題目B附件1-副本; I=imread(str,num2str(j),.bmp); i2=dither(I); a=i2(:,72,1); str=C:UsersAdministratorDesktop第六輪題目第六輪題目B附件1-副本; for i=1:19 I=imread(str,num

27、2str(i),.bmp); i2=dither(I);mi=i2(:,1,1); ni=a-mi; A(j,i)=sqrt(dot(ni,ni); endenda=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0; for i=1:19 k=A(i,1); a(i)=1; for j=1:19 if(kA(i,j) k=A(i,j); a(i)=j; end endendfirst=1;for i=1:19 for j=1:19 if(A(i,j)=0) first=j; end endend str=C:UsersAdministratorDesktop第六輪題目

28、第六輪題目B附件1-副本;z= imread(str,num2str(first),.bmp);for m=1:18 m=1;str=C:UsersAdministratorDesktop第六輪題目第六輪題目B附件1-副本;x = imread(str,num2str(first),.bmp); y=imread(str,num2str(a(first),.bmp); x=z; z = x,y; first=a(first);endimshow(z)附錄二：附錄三：clear,clc;A=zeros(19,19); for j=1:19str=C:UsersAdministratorDeskt

29、op第六輪題目第六輪題目B附件2; I=imread(str,num2str(j),.bmp); i2=dither(I); a=i2(:,72,1); str=C:UsersAdministratorDesktop第六輪題目第六輪題目B附件2; for i=1:19 I=imread(str,num2str(i),.bmp); i2=dither(I);mi=i2(:,1,1); ni=a-mi; A(j,i)=sqrt(dot(ni,ni); endenda=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0; for i=1:19 k=A(i,1); a(i)=1

30、; for j=1:19 if(kA(i,j) k=A(i,j); a(i)=j; end endendfirst=1;for i=1:19 for j=1:19 if(A(i,j)=0) first=j; end endend str=C:UsersAdministratorDesktop第六輪題目第六輪題目B附件2;z= imread(str,num2str(first),.bmp);for m=1:18 m=1;str=C:UsersAdministratorDesktop第六輪題目第六輪題目B附件2;x = imread(str,num2str(first),.bmp); y=imre

31、ad(str,num2str(a(first),.bmp); x=z; z = x,y; first=a(first);endimshow(z)附錄四：附錄五：clear,clc;for i=1:209 if(i=10) imgname=strcat(D:附件附件300,num2str(i-1),.bmp); elseif(i=100) imgname=strcat(D:附件附件30,num2str(i-1),.bmp); else imgname=strcat(D:附件附件3,num2str(i-1),.bmp); end I(:,:,i)=imread(imgname); left(:,i

32、)=I(:,1,i); right(:,i)=I(:,72,i); up(i,:)=I(1,:,i); down(i,:)=I(180,:,i);endleft=int32(left);right=int32(right);up=int32(up);down=int32(down);mAns=zeros(1,19);mAns(1)=15;for i=2:19 xsd=zeros(1,209); for j=1:209 if j=mAns(i-1) continue end xsd(j)=max(sum(abs(right(:,mAns(i-1)-left(:,j); for tmp_i=1:2

33、09 if sum(up(tmp_i,:)-255)=0 xsd(tmp_i)=9999999; end end for k=1:i-1 xsd(mAns(k)=999999999; end end format long g xsd; ma,maid=min(xsd); mAns(i)=maid; %人工干預(yù) if mAns(i-1)=200 mAns(i)=136; end if mAns(i-1)=204 mAns(i)=170; end if mAns(i-1)=170 mAns(i)=135;end if mAns(i-1)=161 mAns(i)=204; end if mAns(

34、i-1)=40 mAns(i)=32;end if mAns(i-1)=32 mAns(i)=52;end if mAns(i-1)=116 mAns(i)=177; endendmyans=zeros(11,19);myans(1,:)=mAns;for hang=2:11 xsd=zeros(1,209); for j=1:209 xsd(j)=max(sum(abs(down(myans(hang-1,1),:)-up(j,:); for tmp_i=1:209 if sum(left(:,tmp_i)-255)=0 xsd(tmp_i)=9999999; end end for tmp

35、_i=1:hang-1 for tmp_j=1:19 xsd(myans(tmp_i,tmp_j)=99999999; end end end format long g xsd; ma,maid=min(xsd); maid; myans(hang,1)=maid; if myans(hang-1,1)=95 myans(hang,1)=126;end if myans(hang-1,1)=8 myans(hang,1)=72; end if myans(hang-1,1)=72 myans(hang,1)=90; end if myans(hang-1,1)=62 myans(hang,1

36、)=169; end for i=2:19 for j=1:209 if j=myans(hang,i-1) continue endxsd(j)=max(sum(abs(right(:,myans(hang,i-1)-left(:,j)+sum(abs(down(myans(hang-1,i-1),:)-up(j,:); for tmp_i=1:hang-1 for tmp_j=1:19 xsd(myans(tmp_i,tmp_j)=99999999; end end for tmp_j=1:i-1 xsd(myans(hang,tmp_j)=99999999; end end ma,mai

37、d=min(xsd); maid; myans(hang,i)=maid; if myans(hang,i-1)=95 myans(hang,i)=35; end if myans(hang,i-1)=85 myans(hang,i)=184;end if myans(hang,i-1)=91 myans(hang,i)=48;end if myans(hang,i-1)=48 myans(hang,i)=122;end if myans(hang,i-1)=125 myans(hang,i)=145; end if myans(hang,i-1)=78 myans(hang,i)=113;e

38、nd if myans(hang,i-1)=113 myans(hang,i)=150;end if myans(hang,i-1)=128 myans(hang,i)=59; end if myans(hang,i-1)=59 myans(hang,i)=44;end if myans(hang-1,i)=95 myans(hang,i)=126;end if myans(hang,i-1)=14 myans(hang,i)=183;end if myans(hang,i-1)=17 myans(hang,i)=185; end if myans(hang,i-1)=205 myans(ha

39、ng,i)=140; end if myans(hang,i-1)=65 myans(hang,i)=112;end if myans(hang,i-1)=112 myans(hang,i)=202;end if myans(hang,i-1)=93 myans(hang,i)=181;end if myans(hang,i-1)=76 myans(hang,i)=56;end if myans(hang,i-1)=207 myans(hang,i)=11;end if myans(hang,i-1)=11 myans(hang,i)=105; end if myans(hang,i-1)=1

40、73 myans(hang,i)=172; end if myans(hang,i-1)=209 myans(hang,i)=139;end if myans(hang,i-1)=159 myans(hang,i)=127;end if myans(hang,i-1)=127 myans(hang,i)=69;end if myans(hang,i-1)=57 myans(hang,i)=94;end if myans(hang,i-1)=94 myans(hang,i)=154; end if myans(hang,i-1)=154 myans(hang,i)=71; end if myan

41、s(hang,i-1)=71 myans(hang,i)=167; end if myans(hang,i-1)=167 myans(hang,i)=33;end if myans(hang,i-1)=157 myans(hang,i)=84;end if myans(hang,i-1)=84 myans(hang,i)=133;end if myans(hang,i-1)=18 myans(hang,i)=81;end if myans(hang,i-1)=147 myans(hang,i)=103;end if myans(hang,i-1)=152 myans(hang,i)=208;e

42、nd if myans(hang,i-1)=109 myans(hang,i)=118;end if myans(hang,i-1)=118 myans(hang,i)=5;end if myans(hang,i-1)=66 myans(hang,i)=144;end if myans(hang,i-1)=96 myans(hang,i)=12;end if myans(hang,i-1)=23 myans(hang,i)=130;end if myans(hang,i-1)=79 myans(hang,i)=68;end if myans(hang,i-1)=100 myans(hang,i

43、)=163;end if myans(hang,i-1)=80 myans(hang,i)=64;end if myans(hang,i-1)=164 myans(hang,i)=73;end if myans(hang,i-1)=73 myans(hang,i)=7;end if myans(hang,i-1)=7 myans(hang,i)=178;end if myans(hang,i-1)=53 myans(hang,i)=37;end if myans(hang,i-1)=2 myans(hang,i)=88;end if myans(hang,i-1)=88 myans(hang,

44、i)=19;end if myans(hang,i-1)=39 myans(hang,i)=149;end if myans(hang,i-1)=149 myans(hang,i)=47;end if myans(hang,i-1)=47 myans(hang,i)=162;end if myans(hang,i-1)=36 myans(hang,i)=82;end if myans(hang,i-1)=89 myans(hang,i)=168;end endendmyans1=myans(8:11,1:19);myans(1:7,1:19);myans=myans1; myans-1;% A

45、=reshape(ans,1,209);% for i=1:209% B(i)=I(A(i)+1);% % i=i+1;% end% % f=horzcat(I(A(1:209);% imshow(B)imshow(I(:,:,50) I(:,:,55) I(:,:,66) I(:,:,144) I(:,:,187) I(:,:,3) I(:,:,58) I(:,:,193) I(:,:,179) I(:,:,119) I(:,:,191) I(:,:,96) I(:,:,12) I(:,:,23) I(:,:,130) I(:,:,29) I(:,:,92) I(:,:,189) I(:,:

46、,142);I(:,:,62) I(:,:,20) I(:,:,79) I(:,:,68) I(:,:,70) I(:,:,100) I(:,:,163) I(:,:,97) I(:,:,132) I(:,:,80) I(:,:,64) I(:,:,117) I(:,:,164) I(:,:,73) I(:,:,7) I(:,:,178) I(:,:,21) I(:,:,53) I(:,:,37); I(:,:,169) I(:,:,101) I(:,:,77) I(:,:,63) I(:,:,143) I(:,:,31) I(:,:,42) I(:,:,24) I(:,:,148) I(:,

47、:,192) I(:,:,51) I(:,:,180) I(:,:,121) I(:,:,87) I(:,:,196) I(:,:,27) I(:,:,2) I(:,:,88) I(:,:,19);I(:,:,39) I(:,:,149) I(:,:,47) I(:,:,162) I(:,:,25) I(:,:,36) I(:,:,82) I(:,:,190) I(:,:,123) I(:,:,104) I(:,:,131) I(:,:,194) I(:,:,89) I(:,:,168) I(:,:,26) I(:,:,9) I(:,:,10) I(:,:,106) I(:,:,75);I(:,:,72) I(:,:,157) I(:,:,84) I(:,:,133) I(:,:,201) I(:,:,18) I(:,:,81) I(:,:,34) I(:,:,203) I(:,:,199) I(:,:,16) I(:,:,134) I(:,:,1