碎紙片的拼接復(fù)原論文

1、2013高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽承 諾 書(shū)我們仔細(xì)閱讀了全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽章程和全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽參賽規(guī)則（以下簡(jiǎn)稱為“競(jìng)賽章程和參賽規(guī)則”，可從全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽網(wǎng)站下載）.我們完全明白，在競(jìng)賽開(kāi)始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn)題.我們知道，抄襲別人的成果是違反競(jìng)賽章程和參賽規(guī)則的，如果引用別人的成果或其他公開(kāi)的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出.我們鄭重承諾，嚴(yán)格遵守競(jìng)賽章程和參賽規(guī)則，以保證競(jìng)賽的公正、公平性.如有違反競(jìng)賽章程和參賽

2、規(guī)則的行為，我們將受到嚴(yán)肅處理.我們授權(quán)全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽組委會(huì)，可將我們的論文以任何形式進(jìn)行公開(kāi)展示（包括進(jìn)行網(wǎng)上公示，在書(shū)籍、期刊和其他媒體進(jìn)行正式或非正式發(fā)表等）.我們參賽選擇的題號(hào)是（從a/b/c/d中選擇一項(xiàng)填寫(xiě)）： b 我們的參賽報(bào)名號(hào)為（即電子文件名）： b0813 所屬學(xué)校（請(qǐng)?zhí)顚?xiě)完整的全名）： 廣西師范大學(xué) 參賽隊(duì)員 (打印并簽名) ：1. 楊 凱 2. 周志恒 3. 陳錦麗 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 日期2013年 9 月16日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：2013高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽編 號(hào) 專 用 頁(yè)賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委

3、會(huì)評(píng)閱前進(jìn)行編號(hào)）：賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：評(píng)閱人評(píng)分備注全國(guó)統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國(guó)前編號(hào)）：全國(guó)評(píng)閱編號(hào)（由全國(guó)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：紙片的拼接復(fù)原摘要 碎紙自動(dòng)拼接復(fù)原技術(shù)現(xiàn)今可以歸結(jié)到計(jì)算機(jī)視覺(jué)和模式識(shí)別領(lǐng)域內(nèi)的問(wèn)題，它在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)等重要領(lǐng)域都起著重要的作用.本文主要分析了文字的拼接技術(shù)，通過(guò)研究碎紙片內(nèi)的像素矩陣和文字行特征特點(diǎn)，提出了基于文字圖形的半自動(dòng)拼接算法.對(duì)于問(wèn)題1中的這種單面的僅縱向切碎的文字文件，通過(guò)matlab程序分析附件中每個(gè)碎片的像素矩陣，確定拼接的第一個(gè)碎片（自左向右拼接），再根據(jù)兩列像素矩陣的像素絕對(duì)差的和來(lái)確定相鄰碎片的編

4、號(hào)，從而得到完整的拼接方案.例如文字文件的拼接結(jié)果如下表所示：順序12345678910111213141516171819編號(hào)008014012015003010002016001004005009013018016001004005009對(duì)于問(wèn)題2中既縱切又橫切的碎紙片，在問(wèn)題一的基礎(chǔ)上，充分考慮橫向匹配和縱向匹配的要求，運(yùn)用matlab程序篩選最左列碎片成分，經(jīng)過(guò)適當(dāng)?shù)娜斯じ深A(yù)根據(jù)文字行特征將所剩碎片進(jìn)行行分類，大大提高拼接效率，得到意想的效果.例如文字文件的拼接結(jié)果如下表所示：順序12345678910111213141516171819編號(hào)0030060020070150180110

5、00005001009013010008012014017016004對(duì)于問(wèn)題3，在前兩問(wèn)的基礎(chǔ)上，建立篩選附件5碎片圖的優(yōu)化模型，通過(guò)matlab編程，使用附件給的418張碎紙片圖，將最終復(fù)原圖劃分為11個(gè)碎片橫條區(qū)域，降低了拼接復(fù)原難度以及所需時(shí)間.最終復(fù)原結(jié)果見(jiàn)附錄.最后，分析了所建立模型的優(yōu)缺點(diǎn)以及推廣，評(píng)價(jià)了文字碎紙片的拼接和復(fù)原實(shí)際情況. 關(guān)鍵詞 文字圖形碎片 半自動(dòng)拼接 像素灰度 matlab程序 一 問(wèn)題的重述碎紙自動(dòng)拼接復(fù)原技術(shù)是計(jì)算機(jī)視覺(jué)和模式識(shí)別領(lǐng)域內(nèi)的問(wèn)題.它在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用.傳統(tǒng)意義上的拼接復(fù)原工作需由人工完成，準(zhǔn)確率

6、較高，但效率非常低，特別是當(dāng)碎片數(shù)量巨大時(shí)，人工拼接很難在短時(shí)間內(nèi)完成任務(wù).隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們?cè)噲D開(kāi)發(fā)碎紙片的自動(dòng)拼接技術(shù)，以提高拼接復(fù)原效率.本文主要討論：首先，對(duì)于給定的來(lái)自同一頁(yè)單面印刷文字文件的碎紙機(jī)破碎紙片（僅縱切），建立碎紙片拼接復(fù)原模型和算法，同時(shí)對(duì)題目中的附件1和附件2給出的中、英文各一頁(yè)文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原.其次，對(duì)于同樣是單面印刷文件既縱切又橫切的情形，在第一問(wèn)的基礎(chǔ)上設(shè)計(jì)出碎紙片拼接復(fù)原模型和算法，對(duì)附件3和附件4給出的中、英文各一頁(yè)文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原.最后，聯(lián)系現(xiàn)實(shí)中的情況，對(duì)還有可能出現(xiàn)雙面打印文件的碎紙片進(jìn)行拼接復(fù)原.在前兩問(wèn)的基礎(chǔ)上，設(shè)計(jì)出相

7、應(yīng)的碎紙片拼接復(fù)原模型與算法，并附件5中雙面打印文件的碎片數(shù)據(jù)給出拼接復(fù)原結(jié)果.在上述復(fù)原過(guò)程中，由于計(jì)算機(jī)的識(shí)別可能會(huì)出現(xiàn)偏差，那么就需要在拼接過(guò)程中進(jìn)行必要的人工干預(yù)，在適當(dāng)?shù)臅r(shí)候我們會(huì)用干預(yù)的方式給出復(fù)原過(guò)程.并最終以圖片形式及表格形式完成給出復(fù)原結(jié)果.具體結(jié)果在附件中給出.二 問(wèn)題的分析破碎文件的復(fù)原，最直接及最精確的就是人工拼接，但是當(dāng)碎片的數(shù)量巨大時(shí)，人工方式就顯得效率低下，所以就考慮把破碎文件運(yùn)用計(jì)算機(jī)技術(shù)來(lái)幫助人們進(jìn)行破碎文件的復(fù)原，讓計(jì)算機(jī)在這個(gè)過(guò)程中發(fā)揮主要作用，但是用計(jì)算機(jī)處理，又不是百分之一百完美，因此在適當(dāng)?shù)臅r(shí)候也需要進(jìn)行人工干預(yù).本文運(yùn)用碎紙片的自動(dòng)拼接技術(shù)，對(duì)每個(gè)

8、附件給出的碎片文字材料進(jìn)行分析，盡可能減少人工干預(yù)，本文給出的圖像數(shù)據(jù)均為形狀、大小一樣的規(guī)則長(zhǎng)四邊形，由于形狀的一致性，所以在拼接時(shí)如果只考慮利用碎片的邊界特征，直接拼接，顯然效果不理想.考慮到使用計(jì)算機(jī)的拼接過(guò)程應(yīng)該與人工拼接過(guò)程是相類似的，即拼接時(shí)不但考慮碎片邊緣是否匹配，還要判斷碎片內(nèi)的字跡斷線和文字內(nèi)容是否匹配.然而根據(jù)現(xiàn)在已有的技術(shù)，實(shí)現(xiàn)計(jì)算機(jī)智能識(shí)字是幾乎不可能的.但是我們可以獲取圖片所提供的像素信息，將其轉(zhuǎn)化為矩陣，根據(jù)圖像的像素矩陣值進(jìn)行碎片拼接，用計(jì)算機(jī)去運(yùn)行處理數(shù)據(jù)，可以想象其拼接效率無(wú)疑比單純利用邊界特征的方法好很多.以下是對(duì)各問(wèn)題的詳細(xì)分析： 針對(duì)問(wèn)題1，對(duì)附件1和附

9、件2提供的數(shù)據(jù)，每頁(yè)紙被切為19條碎片，對(duì)于這種單面的僅縱向切碎的文字文件，我們僅考慮碎片左右兩側(cè)的拼接.首先，在轉(zhuǎn)換中發(fā)現(xiàn)，像素圖片矩陣的值是介于0到255之間的一個(gè)像素矩陣，隨著像素矩陣值的增加，我們發(fā)現(xiàn)隨著像素矩陣數(shù)值的增大，所代表的區(qū)域越來(lái)越淺，最后255這個(gè)數(shù)值，代表了白色區(qū)域.其次，對(duì)于問(wèn)題1中的附件1和附件2圖片，由于僅縱向切碎的文字文件，僅考慮碎片左右兩側(cè)的拼接.需運(yùn)用matlab程序分別對(duì)附件1和附件2中的19個(gè)碎片計(jì)算其像素矩陣，將每個(gè)附件中19條圖像轉(zhuǎn)換成19個(gè)的像素矩陣，篩選出每個(gè)像素矩陣的第一列像素矩陣值，然后運(yùn)用excel軟件統(tǒng)計(jì)各列像素值等于255的個(gè)數(shù)，可以粗略

10、的認(rèn)為所含255個(gè)數(shù)最多的列所對(duì)應(yīng)的碎片則是拼接順序中的左邊第一條（如果有必要進(jìn)行人工干預(yù)，但是本文第一問(wèn)沒(méi)有進(jìn)行人工干預(yù)）.接下來(lái)從左邊開(kāi)始選取第二條碎片，關(guān)于第二條待匹配的碎片，用先確定的第一條像素矩陣的最后一列，對(duì)其進(jìn)行數(shù)值求和，然后將剩下的18個(gè)像素矩陣中的第一列和最后一列矩陣進(jìn)行分別求和.將首先確定的最左邊第一條矩陣中的最后一列矩陣與求出的18個(gè)像素矩陣中的第一列矩陣分別進(jìn)行做差，然后將差值取絕對(duì)值，這樣就可以得出，如果差值越小，其重疊的相似度也應(yīng)該相對(duì)越高.這樣可篩選得出相似度較高的碎片，即與第一個(gè)碎片相匹配，該碎片位于拼接順序的第二條，確定第二條后，再用第二條的最右邊矩陣并以此類

11、推，逐一從左到右查詢碎片，直到碎紙片的復(fù)原結(jié)果.針對(duì)問(wèn)題2，在問(wèn)題1的基礎(chǔ)上，繼續(xù)對(duì)所給的附件3和附件4進(jìn)行分析.針對(duì)附件3和附件4的特點(diǎn)，附件3和附件4給出了碎片既橫切又縱切的中英文圖像，那么在拼接時(shí)就有兩方面的考慮，既要滿足橫向匹配，又要滿足縱向匹配.那么我們就考慮在問(wèn)題解決中可以分為兩步進(jìn)行，首先考慮橫向拼接，一旦橫向拼接完成了，縱向拼接自然相對(duì)就好解決了.根據(jù)碎片像素矩陣特征和行距特征將其分類，再結(jié)合問(wèn)題1的方法將各類碎片進(jìn)行匹配，即可得到11個(gè)碎片橫條.接著考慮縱向拼接，使用matlab程序?qū)Φ玫降男碌臋M條碎片進(jìn)行像素分析，比較像素矩陣中第一行數(shù)據(jù)中255的個(gè)數(shù)，個(gè)數(shù)最多的碎片即是原

12、文件的第一行，依次類推，同樣的方法即可知道具體的排列順序，從而得到碎紙片復(fù)原的結(jié)果.針對(duì)問(wèn)題3，在問(wèn)題1和問(wèn)題2的基礎(chǔ)上，繼續(xù)對(duì)所給的附件5進(jìn)行分析.實(shí)際生活中存在很多雙面打印的文件，這些雙面文件的碎紙片混合在了一起，當(dāng)對(duì)其進(jìn)行拼接復(fù)原時(shí)，首先要判斷同一面的文字碎片，然后再進(jìn)行拼接.附件5給出了碎片既橫切又縱切的英文文字圖像，那么在拼接時(shí)依舊有兩方面的考慮，既要滿足橫向匹配，又要滿足縱向匹配.首先考慮橫向拼接，轉(zhuǎn)換得到180x72的像素矩陣，這些是介于0到255之間的一個(gè)像素矩陣，隨著圖片的增加，相應(yīng)的增多轉(zhuǎn)換得到的像素矩陣，在問(wèn)題2的基礎(chǔ)上繼續(xù)進(jìn)行檢驗(yàn)所給的碎紙片圖，運(yùn)用matlab讀取了4

13、18張碎片圖后，將每張碎片轉(zhuǎn)換得的像素矩陣的第一列以及最后一列各自取出，通過(guò)程序進(jìn)行驗(yàn)證，可以算出匹配度高的相鄰碎片，此時(shí)進(jìn)行一次人工干預(yù)，拼接出位于同一行的碎片橫條；接著考慮縱向拼接，運(yùn)用matlab程序?qū)Φ玫降男碌臋M條碎片進(jìn)行像素分析的提取，配準(zhǔn)各個(gè)橫條的像素矩陣的第一行與最后一行的相關(guān)度，綜合分析碎紙片上英文之間的行距，進(jìn)而確定拼接的碎片橫條位于哪一行，得到最終的復(fù)原結(jié)果.綜上所述，以上三個(gè)問(wèn)題的解決流程可用下面的流程圖表示：圖2 問(wèn)題解決流程圖三 模型假設(shè)準(zhǔn)備與符號(hào)說(shuō)明3.1 模型的假設(shè) 1、 假設(shè)碎紙機(jī)把一頁(yè)印刷文字文件碎成形狀規(guī)則，大小一樣的碎片，看做形狀、大小相同的長(zhǎng)方形.2、

14、在碎紙過(guò)程中，只考慮文字被切開(kāi)，不考慮文字筆畫(huà)的丟失、碎片添加的任何痕跡等.3、 假設(shè)文檔碎片的文字的方向已經(jīng)確定（按照閱讀標(biāo)準(zhǔn)確定，從左向左右，自上而下），不考慮碎片圖像的旋轉(zhuǎn)問(wèn)題.4、 圖片在復(fù)原的過(guò)程中，不考慮圖片像素的改變，只考慮碎片相對(duì)應(yīng)的固定像素值的匹配問(wèn)題.3.2 模型準(zhǔn)備不規(guī)則幾何文檔碎紙片計(jì)算機(jī)拼接的方法一般利用碎片邊緣的尖角特征、尖點(diǎn)特征、面積特征等一些幾何特征，搜索與之匹配的相鄰碎紙片進(jìn)行拼接，這種基于邊界的幾何特征的拼接方法并不適用于邊緣的形狀相似的碎紙片.對(duì)于這類邊緣相似的碎紙片的拼接問(wèn)題，理想的計(jì)算機(jī)拼接的過(guò)程與人工拼接的過(guò)程類似，即拼接時(shí)不僅要考慮拼接碎紙片的邊緣

15、是否匹配，還要判斷碎紙片內(nèi)的文字字跡斷線或文字內(nèi)容是否匹配，但是由于理論和技術(shù)的限制，讓計(jì)算機(jī)具備類似于人的的那種識(shí)別碎紙片邊緣字跡斷線、以及理解碎紙片內(nèi)文字圖像的含義的智能幾乎是不太可能的.但是利用現(xiàn)在已有的技術(shù)，完全可以獲取到碎紙片文字所在行的幾何特征信息，如文字行的行高及間距等信息.如果利用這些信息進(jìn)行碎紙片拼接，其拼接的效率就比單純利用邊界的幾何特征方法更好.根據(jù)本文題設(shè)要求，經(jīng)考慮分析，本文采取轉(zhuǎn)換矩陣數(shù)組元素拼接的技術(shù)對(duì)破碎的文字文檔進(jìn)行拼接復(fù)原.由于計(jì)算機(jī)數(shù)字分析圖像能力方面的存在一定的缺陷，讓計(jì)算機(jī)對(duì)碎紙片進(jìn)行完全意義上的自動(dòng)化拼接頁(yè)幾乎是不太可能，為保證其拼接的準(zhǔn)確性，需要在

16、拼接的過(guò)程中加入一定的人工干擾過(guò)程.一般來(lái)說(shuō)，先利用計(jì)算機(jī)搜索出于目標(biāo)碎紙片相匹配的未拼接碎紙片，并根據(jù)匹配的程度按順序到得待選的碎紙片，然后人為地進(jìn)一步分析結(jié)果進(jìn)行舍棄或拼接待選碎紙片3.一頁(yè)文字文件的碎片拼接復(fù)原相當(dāng)于全景圖的生成技術(shù)，而相鄰圖像的配準(zhǔn)及拼接是該技術(shù)的關(guān)鍵.圖像的拼技術(shù)一般分為基于圖像特征的方法和基于圖像灰度的方法.特征提取的方法通常涉及大量的幾何與圖像形態(tài)學(xué)的計(jì)算，計(jì)算量大，沒(méi)有一般的模型可遵循，但需要針對(duì)不同的應(yīng)用場(chǎng)景來(lái)選擇各自適合的特征， 所提取的圖像特征包括更高層的語(yǔ)義信息，基于特征的方法具有尺度不變性和放射不變形.然而基于圖像灰度的拼接方法簡(jiǎn)單簡(jiǎn)單易行，并且其數(shù)字

17、統(tǒng)計(jì)模型以及收斂速度、定位精度等均具有定量的分析和研究結(jié)果，此類方法得到了廣泛的應(yīng)用.本文中的文字圖像中文字區(qū)域的文字結(jié)構(gòu)相對(duì)單一，并可能出現(xiàn)相同或相似的字符，因此文字容易出現(xiàn)匹配出現(xiàn)誤差.對(duì)于文字左右拼接的情況，可以對(duì)圖片中劃分的每行文字進(jìn)行分析處理，通過(guò)提取文字圖片的邊緣像素矩陣，得到文字出現(xiàn)在圖片邊緣的那一行高，進(jìn)一步對(duì)一行行的文字拼接復(fù)原，這也有利于獲取更精確的配準(zhǔn)結(jié)果.基于文字的圖像灰度的方法不需要提取文字圖像的相應(yīng)的特征，只以兩幅圖像相連接部分對(duì)應(yīng)的像素灰度的相似性準(zhǔn)則來(lái)尋找圖像的匹配位置.待匹配的圖像，首先求出圖像中最左邊一列的像素矩陣值之和，和最右邊一列像素矩陣之和。然后定義其

18、相連接的區(qū)域的相似度可由像對(duì)應(yīng)的像素灰度平方差之和來(lái)衡量，其計(jì)算文字圖片像素與和所搜索的文字圖片像素灰度值的距離4：該方法稱為差和法其中分別代表圖像各個(gè)像素的灰度值，代表各個(gè)像素的坐標(biāo).其值最小者所對(duì)應(yīng)的位置為最佳的匹配位置.不過(guò)，為了減少計(jì)算的工作量和評(píng)價(jià)標(biāo)準(zhǔn)，這里我們定義對(duì)應(yīng)像素的灰度的絕對(duì)值之差然后求和去代替原來(lái)的像素灰度平方差之和，其計(jì)算文字圖片像素與和所搜索的文字圖片像素灰度值的距離：3.3符號(hào)說(shuō)明相對(duì)應(yīng)的像素絕對(duì)差值像素矩陣的像素值第個(gè)碎片最后一列與第個(gè)碎片第一列的圖像矩陣值和的差的絕對(duì)值（）點(diǎn)對(duì)的歐氏距離和歐式距離和代價(jià)誤差函數(shù)給定的初始值四 模型的建立和求解4.1 問(wèn)題1的模型

19、與求解對(duì)于問(wèn)題1的解決，主要有以下四個(gè)步驟：步驟1 確定像素矩陣運(yùn)用matlab程序分別對(duì)附件1和附件2中所給出的19張碎片圖像進(jìn)行像素矩陣計(jì)算，每個(gè)圖都對(duì)應(yīng)得到一個(gè)的像素矩陣.步驟2 確定左邊第一列碎片通過(guò)matlab程序篩選出每個(gè)像素矩陣的第一列像素值，運(yùn)用excel軟件統(tǒng)計(jì)各列像素值等于255的個(gè)數(shù).運(yùn)算的結(jié)果如下圖：圖1 附件1碎片最左邊像素為255的個(gè)數(shù)其中橫坐標(biāo)為碎紙片的編號(hào)，縱坐標(biāo)是像素為255的個(gè)數(shù)。從上表的結(jié)果中，篩選出第一列的像素值為255的個(gè)數(shù)最多的是編號(hào)為008的圖片，說(shuō)明編號(hào)為008的圖片是附件1中碎紙片復(fù)原的拼接順序中位于左邊的第1張圖片.同理，得到附件2中每個(gè)圖片

20、的像素矩陣的第一列的像素值為255的個(gè)數(shù)最多的是編號(hào)為003的圖片，說(shuō)明編號(hào)為003的圖片是附件2中碎紙片復(fù)原的拼接順序中位于左邊的第1張圖片.步驟3 確定碎片順序?qū)τ诒绢}中出現(xiàn)的形狀、大小一樣的相鄰兩塊碎片拼接，只需考慮兩塊碎片灰度的絕對(duì)差值3.因此可運(yùn)用matlab程序建立以下模型：對(duì)于待匹配的圖像，像素矩陣像素的像素值，表示行數(shù)，為列數(shù)，其連接區(qū)域的相似度可由相對(duì)應(yīng)的像素灰度絕對(duì)差值來(lái)衡量，即計(jì)算第1張圖片的圖像矩陣的最后一列的像素值與待匹配圖片的圖像矩陣的第一列的像素值的絕對(duì)差值的總和，計(jì)算公式如下：下面先對(duì)附件1進(jìn)行討論，可通過(guò)matlab程序進(jìn)行計(jì)算得到它們相對(duì)應(yīng)的像素差的絕對(duì)值，

21、如下表的結(jié)果：表1 附件1碎片008與其他碎片的相素差的絕對(duì)值表碎片編號(hào)0000010020030040059718111096511688912411210711478601碎片編號(hào)006007009010011012111883989831113941015939290198493碎片編號(hào)01301401501601701811944627544841251124681162686740根據(jù)表1中的數(shù)據(jù)進(jìn)行比較，可篩選出與碎片008相對(duì)應(yīng)的像素絕對(duì)差值最小的碎片014，即編號(hào)為014的碎片能與編號(hào)為008的碎片相互匹配重疊，作為拼接順序的第2張圖片.依次類推，按照相同的方法，在matlab

22、程序依次篩選出位于拼接順序的第3張圖片，第4張圖片，第19張圖片，從而得到附件1的拼接復(fù)原文件（見(jiàn)本文附件一），拼接順序如下表所示：表2 附件1文件的拼接順序順序12345678910111213141516171819編號(hào)008014012015003010002016001004005009013018016001004005009同理，計(jì)算附件2的第1張圖片的圖像矩陣的最后一列的像素值與待匹配圖片的圖像矩陣的第一列的像素值的絕對(duì)差值的總和，結(jié)果如下表：表3 附件2碎片003與其他碎片的相位差絕對(duì)值表碎片編號(hào)00000100200400500666977638697026978117922

23、6925277碎片編號(hào)007008009010011012768838218572522784226580877712碎片編號(hào)013014015016017018776588899271768767487462863442從表3的結(jié)果可以看出，附件2中得到與碎片003的像素絕對(duì)差值最小的碎片編號(hào)為006，即編號(hào)為006的碎片能與編號(hào)為003的碎片相互匹配重疊，作為拼接順序的第2張圖片.以此類推，在matlab程序依次篩選出位于拼接順序的第3張圖片，第4張圖片，第19張圖片，從而得到附件2的拼接復(fù)原文件（見(jiàn)本文附件二），拼接順序如下表所示：表4 附件2文件的復(fù)原拼接結(jié)果順序12345678910

24、111213141516171819編號(hào)0030060020070150180110000050010090130100080120140170160044.2 問(wèn)題2模型與求解運(yùn)用matlab程序?qū)Ω郊?給出的209個(gè)碎片圖像進(jìn)行像素矩陣計(jì)算，其中每個(gè)圖像得到一個(gè)的矩陣，刷選出209個(gè)碎片圖像中每個(gè)像素矩陣的第一列像素矩陣和最后一列像素矩陣，即2個(gè)的像素矩陣.然后對(duì)得到209個(gè)第一列像素矩陣和最后一列像素矩陣進(jìn)行列求和.把上述的求和結(jié)果轉(zhuǎn)換成一個(gè)的矩陣：其中第個(gè)碎片最后一列圖像矩陣值和與第個(gè)碎片第一列的圖像矩陣值和的差的絕對(duì)值為矩陣中的元素（），比較篩選出矩陣中的第行所有元素的最小的一個(gè)，則

25、說(shuō)明第個(gè)碎片的左邊與第個(gè)碎片的右邊相匹配，這樣就完成了附件3的橫向拼接順序，得到11個(gè)新的橫條碎片.接著進(jìn)行縱向拼接，使用matlab程序分別對(duì)得到的所有新的橫條碎片進(jìn)行像素矩陣計(jì)算，篩選出11個(gè)碎片圖像中每個(gè)像素矩陣的第一的像素矩陣.用excel軟件統(tǒng)計(jì)各個(gè)新橫條的像素矩陣中第一行數(shù)據(jù)中255的個(gè)數(shù)，得到個(gè)數(shù)最對(duì)的碎片是按如下表的順尋拼接的橫條，即該序列的橫條位于縱向拼接順序的第一個(gè).部分行拼接結(jié)果如圖2、圖3所示：圖2 附件3橫向拼接復(fù)原圖（1）圖3 附件3橫向拼接復(fù)原圖（2）最后，在對(duì)所得新的11個(gè)橫條處理的問(wèn)題上，主要有像素矩陣分析法或者直接采用人工干預(yù).由于只有11個(gè)橫條，并且根據(jù)漢

26、字的筆畫(huà)特征，本文采取用人工干預(yù)的方式，對(duì)11個(gè)橫條進(jìn)行干預(yù)，逐一確定，最終得到到附件3的拼接復(fù)原結(jié)果（見(jiàn)本文附件三、附件四）：表5 附件3部分拼接復(fù)原結(jié)果順序12345613141516171819編號(hào)049054065143186002011022129028091188141順序20212223242532333435363738編號(hào)061019078067069099163072006177020052036順序編號(hào)順序172173174175176177184185186187188189190編號(hào)071156083132200017170205085152165027060順序19

27、1192193194195196203204205206207208209編號(hào)089146102154114040117004101113194119123同理，運(yùn)用matlab程序?qū)Ω郊?中給出的209個(gè)橫縱交切的英文碎片進(jìn)行像素矩陣計(jì)算.參照附件3同樣的思路，首先得到橫向拼接順序的11個(gè)新的橫條碎片，然后再通過(guò)縱向拼接順序干預(yù)逐一得到附件4的復(fù)原圖，附件4的拼接復(fù)原結(jié)果如下（詳見(jiàn)本文附件五、附件六）：表6 附件4拼接復(fù)原結(jié)果順序12345613141516171819編號(hào)191075011154190184149032204065039067147順序2021222324253233343

28、5363738編號(hào)201248170196198094101026100006017028146順序編號(hào)順序172173174175176177184185186187188189190編號(hào)171042066205010157056035016009183152044順序191192193194195196203204205206207208209編號(hào)0810771282001310520720121771240001021154.3 問(wèn)題三的模型求解：區(qū)域的邊緣為圖像中灰度變化不劇烈的地方，變化不劇烈含有豐富的信息.因此考慮建立圖像灰度模型，利用邊緣的灰度像素變化，描述了圖像中所包含的文字的

29、有無(wú)，留白的區(qū)域.在對(duì)圖片處理時(shí)，邊緣處理的好壞直接影響圖像處理的結(jié)果.對(duì)于邊界的追蹤，我們利用像素矩陣中白色像素點(diǎn)255的變化來(lái)進(jìn)行追蹤，通過(guò)轉(zhuǎn)化為像素矩陣的方式將邊緣點(diǎn)連接起來(lái)，構(gòu)成一列矩陣.msac（m-estinmator sample consenous）是torr和zisserman提出應(yīng)用與圖像幾何的形狀來(lái)估計(jì)12,13.其思想是在兩幅圖像所有匹配點(diǎn)對(duì)的樣本中隨機(jī)采樣，在樣本中尋找符合采樣的所有點(diǎn)對(duì)中，通過(guò)反復(fù)迭代使得到的點(diǎn)對(duì)的歐氏距離和代價(jià)最小化，使之小于設(shè)定的初始值或超過(guò)迭代次數(shù)，最終得到的點(diǎn)對(duì)為所求的正確匹配點(diǎn)對(duì).計(jì)算方法如下：首先計(jì)算點(diǎn)對(duì)的歐氏距離和，其中表示點(diǎn)對(duì)的距離函

30、數(shù)，其和代價(jià)為：其中誤差函數(shù)滿足： 這里給定的值，因此當(dāng)給定比較大時(shí)，得到的地情況會(huì)相對(duì)多，那么計(jì)算得到的點(diǎn)對(duì)必然會(huì)包含外點(diǎn)，其中內(nèi)點(diǎn)是我們所要找的點(diǎn).參考這里的masc算法，我們將提取的像素矩陣中的每一個(gè)元素看做一個(gè)個(gè)的點(diǎn)，用求絕對(duì)差的算法匹配點(diǎn)對(duì)，后期運(yùn)用歐式距離進(jìn)行檢驗(yàn)匹配度.基于上述討論，本題可由以下步驟完成：步驟一運(yùn)用matlab程序?qū)Ω郊?給出的418個(gè)碎片圖像進(jìn)行像素矩陣轉(zhuǎn)換計(jì)算，其中每個(gè)圖像得到一個(gè)的矩陣，提取出418個(gè)碎片圖像所得每個(gè)像素矩陣的第一列像素矩陣和最后一列像素矩陣，即均為的像素矩陣.步驟二對(duì)得到418個(gè)第一列像素矩陣和最后一列像素矩陣分別進(jìn)行列求和，然后分別存放在

31、矩陣d和dt中，接下來(lái)用dt的每一項(xiàng)依次減去d的每一項(xiàng)之后并求絕對(duì)值，得到一個(gè)矩陣m.步驟三用msac算法的思想，用matlab編程可以算出每一行（列）的最小值，并且反饋出最小值所在的行數(shù)，此時(shí)我們認(rèn)為左右像素矩陣的歐式距離最小即為匹配度較高的左右相鄰碎紙片.這樣可以粗略得到關(guān)于文字行的關(guān)系，比較后初步得出部分用于拼接復(fù)原文件其中一面的180張碎紙片.運(yùn)算結(jié)果部分如下表：表7 運(yùn)算結(jié)果表455033693043636410493685340030401844153241449459004060245438813971602776387627762962149375935310813498582

32、386511285536712854453298422501138257235964108993641551510115514187271819848722306459001404904980704786186638722403166955719913924830217432645334833483225578652106037445900235381007121281538372923145472039210424016241796274529546412011464137211062218784416315485496839895947705594720924123524209042365

33、289475596580335632963356238291393350143477713133222343759394175931855332440583736420431600885378742062459020623676220714733614494124428011703229043748290428341365631481953358548698175577691602508916034224891562567375303459004575587848995037161550377017681502261411804036760154438345964771756477739220

34、829424054262044978150989447965197146811971376722981564452188639907328971646185375129013751198751821613281064354226897764678531513501315125871118384728706410928435201810398897224588973159462853626474504039283705034032424751286075121774324339775089365538345423162225243469319594693104542411582270836418

35、2652485205422657109425710281441217532871853步驟四運(yùn)用matlab程序?qū)?18個(gè)碎片圖像的像素矩陣進(jìn)行統(tǒng)計(jì)判斷，得出每個(gè)圖像的第一列的白色邊緣像素值255，然后統(tǒng)計(jì)分析各個(gè)圖像的白色邊緣區(qū)域大小，匹配出位于行首和行末的碎紙片.但是由于計(jì)算結(jié)果存在誤差，此時(shí)需要通過(guò)人工干預(yù)進(jìn)行區(qū)分判斷，將篩選出的左右相鄰碎紙片，運(yùn)用行距分類以及組詞成句的方法干預(yù)拼接成一碎片橫條.例如其中的一行的排列結(jié)果如下圖4、圖5所示：圖4 附件5部分行拼接圖（1）圖5 附件5部分行拼接圖（2）步驟五通過(guò)上述步驟，初步拼接出11個(gè)碎片橫條，輸出成圖片，然后用matlab讀取這11張圖

36、的像素矩陣，運(yùn)用同樣的思路分析配準(zhǔn)像素矩陣的第一行與最后一行，匹配度較高的應(yīng)為相鄰行，進(jìn)而得出最終復(fù)原圖像（見(jiàn)本文附件七、附件八），部分排列順序如下表所示：表8 附件5其中一面部分拼接順序順序12345613141516171819編號(hào)078b111b125a140a155a150a029a189b081b164b020a047a136b順序20212223242532333435363738編號(hào)089a010b036a076b178a044a079a014a059a060b147a152a005a順序編號(hào)順序172173174175176177184185186187188189190編號(hào)0

37、23b133a048a051b095a160b118a101a015b205a082b145a009b順序191192193194195196203204205206207208209編號(hào)099a043a096b109a123a006a100b106b055b103a112a196a054b觀察以上所拼接出來(lái)的原文件，匹配程度是相當(dāng)吻合的.七 模型的評(píng)價(jià)與推廣7.1 模型的評(píng)價(jià)1、 基于圖像灰度值的相關(guān)方法簡(jiǎn)單易行，且其數(shù)學(xué)統(tǒng)計(jì)模型、定位精度、收斂速度、誤差估計(jì)等都有定量的分析及研究結(jié)果，此類方法可以進(jìn)行推廣普遍.2、 本文采用基于圖像灰度的拼接方法，對(duì)每張圖片計(jì)算其像素矩陣的像素值，計(jì)算量大

38、，實(shí)時(shí)性不高.由于編程的不理想，導(dǎo)致算法的圖片匹配精確度不高和魯棒性差，同時(shí)由于使用了冗余的代碼使得執(zhí)行速度偏低.3、 由于時(shí)間關(guān)系，構(gòu)造的模型過(guò)于簡(jiǎn)單.對(duì)于圖片的排序問(wèn)題，過(guò)多地采取了人工干預(yù)的措施，未能很好地利用算法進(jìn)行圖像的自動(dòng)排序；4、 題目提供的附件碎紙片圖都是均勻的橫切或縱切，本文設(shè)計(jì)的模型與算法沒(méi)有能夠解決對(duì)于傾斜或選擇的圖片處理問(wèn)題，拼接后導(dǎo)致的圖像形變問(wèn)題也沒(méi)有涉及.72 模型的改進(jìn)與推廣1、 為了增加其系統(tǒng)的實(shí)時(shí)性、減少運(yùn)行時(shí)間，可考慮兩種基本思路是減少計(jì)算量或者提高計(jì)算機(jī)資源利用率.在編程過(guò)程中盡量考慮調(diào)用、循環(huán)語(yǔ)句，盡量避免冗余的代碼，減少運(yùn)行時(shí)間.2、 根據(jù)現(xiàn)實(shí)情況，

39、碎紙機(jī)進(jìn)行碎紙時(shí)得到的紙片不一定是規(guī)則的，或者文物文獻(xiàn)碎片不一定相同時(shí)，則應(yīng)優(yōu)化本文提出的基于文字圖形的半自動(dòng)拼接算法，綜合考慮碎片的幾何特征，如碎片邊界等，減少人工干預(yù)，提高拼接效率，進(jìn)一步提出文字圖形的自動(dòng)算法.參考文獻(xiàn)1 姜啟源，數(shù)學(xué)建模(第三版)m，北京：高等教育出版社，2003.2 中科大，數(shù)學(xué)建模書(shū)籍，/download.htm，2011年9月10日.3 羅智中，基于文字特征的文檔碎紙片半自動(dòng)拼接，計(jì)算機(jī)工程與應(yīng)用，2012 . 4 李利軍，李云偉，基于圖像灰度的拼接技術(shù)的研究，計(jì)算機(jī)與數(shù)字工程，2007.5 劉艷,高偉男,王志清,巨志勇，

40、改進(jìn)的八近鄰區(qū)域邊界標(biāo)定自動(dòng)機(jī)，華東師范大學(xué)學(xué)報(bào)，2009.6 羅立宏，譚夏梅，基于灰度累積評(píng)價(jià)的全景圖像自動(dòng)拼接算法，蘭州理工大學(xué)學(xué)報(bào),2007,第3期.7 李靜梅，冉祥金，姚成浪, 基于垂直投影特征的文檔圖像自動(dòng)拼接算法, 信息技術(shù),2005,第12期.8 尹麗華，安居白，夏妍妍, 基于特征點(diǎn)匹配的圖像拼接算法, 連海事大學(xué)學(xué)報(bào),2007,第s1期.9 朱正明，姜明，馬小明, 基于特征點(diǎn)匹配的圖像拼接系統(tǒng), 林業(yè)科學(xué), 2004,第4期.10 姚喜，盧秀山, 基于特征的影像拼接算法, 城市勘測(cè),2008,第6期.11 胡社教，陳宗海，劉年慶，基于圖像灰度特征的全景圖像拼接，中國(guó)科學(xué)技術(shù)大學(xué)

41、自動(dòng)化，2003年.12chandas,n.p.galatsanos,a.likas.bayesianrestorationusinganewton-stationaryedge-preservingimageprior.ieeetransactiononimageprocessing.2006,15(10):2987-2997.13ruiminpan,stanleyj.reeves.efficienthuber-markovedge-preservingimagerestoration.ieeetransactiononimageprocessing.2006,15(12):3728-3735. 附錄附件一 問(wèn)題1中附件1文件的順序拼接復(fù)原結(jié)果圖附件二 問(wèn)題1中附件2文件的順序拼接復(fù)原結(jié)果圖附件三 問(wèn)題2中附件3文件的順序拼接復(fù)原結(jié)果圖附件四 問(wèn)題2中附件3文件的拼接順序順序12345678910111213141516171819編號(hào)049054065143186