2013年全國(guó)數(shù)學(xué)建模B題省一等獎(jiǎng).doc

2013高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽承 諾 書我們仔細(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)賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn)題。我們知道，抄襲別人的成果是違反競(jìng)賽章程和參賽規(guī)則的，如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽章程和參賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽章程和參賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們授權(quán)全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽組委會(huì)，可將我們的論文以任何形式進(jìn)行公開展示（包括進(jìn)行網(wǎng)上公示，在書籍、期刊和其他媒體進(jìn)行正式或非正式發(fā)表等）。我們參賽選擇的題號(hào)是（從A/B/C/D中選擇一項(xiàng)填寫） B 我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話）： 024B03 所屬學(xué)校（請(qǐng)?zhí)顚懲暾娜?山東科技大學(xué) 參賽隊(duì)員 (打印并簽名) ：1. 張?chǎng)?2. 呂彥全 3. 孫紅華 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 趙文才 （論文紙質(zhì)版與電子版中的以上信息必須一致，只是電子版中無(wú)需簽名。以上內(nèi)容請(qǐng)仔細(xì)核對(duì)，提交后將不再允許做任何修改。如填寫錯(cuò)誤，論文可能被取消評(píng)獎(jiǎng)資格。） 日期： 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ū)組委會(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ù)原數(shù)學(xué)模型摘要首先對(duì)圖片進(jìn)行灰度化處理,然后轉(zhuǎn)化為0-1二值矩陣，利用矩陣行（列）偏差函數(shù)，建立了基于最小二乘法的碎紙片拼接數(shù)學(xué)模型，并利用模型對(duì)圖片進(jìn)行拼接復(fù)原。針對(duì)問(wèn)題一，當(dāng)兩個(gè)數(shù)字矩陣列向量的偏差函數(shù)最小時(shí)，對(duì)應(yīng)兩張圖片可以左右拼接。經(jīng)計(jì)算，得到附件1的拼接結(jié)果為：08,14,12,15,03,10,02,16,01,04,05,09,13,18,11,07,17,00,06。附件2的拼接結(jié)果為:03,06,02,07,15,18,11,00,05,01,09,13,10,08,12,14,17,16,04。針對(duì)問(wèn)題二，首先根據(jù)每張紙片的內(nèi)容不同的特性，對(duì)圖片進(jìn)行聚類分析，將209張圖片分為11類；對(duì)于每一類圖片，按照問(wèn)題一的模型與算法，即列偏差函數(shù)最小則進(jìn)行左右拼接,對(duì)于沒(méi)有拼接到組合里的碎紙片進(jìn)行人工干預(yù)，我們得到了11組碎紙片拼接而成的圖片；對(duì)于拼接好的11張圖片，按照問(wèn)題一的模型與算法，即列偏差函數(shù)最小則進(jìn)行上下拼接,對(duì)于沒(méi)有拼接到組合里的碎紙片進(jìn)行人工干預(yù)。我們最終經(jīng)計(jì)算，附件3的拼接結(jié)果見(jiàn)表9，附件4的拼接結(jié)果見(jiàn)表10。針對(duì)問(wèn)題三，由于圖片區(qū)分正反兩面，在問(wèn)題二的基礎(chǔ)上，增加圖片從下到上的裁截距信息，然后進(jìn)行兩次聚類，從而將所有圖片進(jìn)行分類，利用計(jì)算機(jī)自動(dòng)拼接與人工干預(yù)相結(jié)合，對(duì)所有圖片進(jìn)行拼接復(fù)原。經(jīng)計(jì)算，附件5的拼接結(jié)果見(jiàn)表14和表15該模型的優(yōu)點(diǎn)是將圖片分為具體的幾類，大大的減少了工作量，缺點(diǎn)是針對(duì)英文文章的誤差比較大。關(guān)鍵字：灰度處理，圖像二值化，最小二乘法，聚類分析，碎紙片拼接一、問(wèn)題重述 碎紙片的拼接復(fù)原技術(shù)在司法鑒定、歷史文獻(xiàn)修復(fù)與研究、軍事情報(bào)獲取以及故障分析等領(lǐng)域都有著廣泛的應(yīng)用。近年來(lái)，隨著德國(guó)“斯塔西”文件的恢復(fù)工程的公布，碎紙文件復(fù)原技術(shù)的研究引起了人們的廣泛關(guān)注。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時(shí)間內(nèi)完成任務(wù)。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們?cè)噲D開發(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ù)原問(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ì)于邊緣形狀相似的碎紙片，這種基于邊界幾何特征的拼接方法失效，拼接時(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)題一的建模與算法 由于碎紙片本身不具有體現(xiàn)其拼接特性的數(shù)字特征，我們需要將其數(shù)字化、矩陣化，將問(wèn)題轉(zhuǎn)化為矩陣之間的相關(guān)性。5.1.1圖片的灰度處理利用軟件，將附件中所給的BMP格式的圖片轉(zhuǎn)化成JPG格式 ，去除圖片的多彩性。為了對(duì)碎紙片進(jìn)行數(shù)字化，我們將圖像進(jìn)行灰度處理，取出圖像中每一個(gè)像素的灰度值，灰度值的大小與像素點(diǎn)顏色的紅綠藍(lán)成分有關(guān)。 根據(jù)文獻(xiàn)1，每個(gè)像素點(diǎn)的，即，其中，的取值范圍是。 問(wèn)題一將同一頁(yè)印刷文字文件縱切為19張圖片（見(jiàn)圖1），根據(jù)實(shí)際情況，我們將每張圖片設(shè)置為格式，于是，每張圖片對(duì)應(yīng)一個(gè)的灰度矩陣。圖1 附件1未進(jìn)行拼接的19張碎紙片5.1.2圖片的二值化處理將圖片進(jìn)行灰度處理以后，每個(gè)像素的灰度值介于之間?；叶戎挡荒苤苯佑糜谖淖謭D片的拼接，還須進(jìn)行二值化處理。將圖片放入直角坐標(biāo)系，規(guī)定：若點(diǎn)的像素灰度值大于或等于，該點(diǎn)用數(shù)值表示，并將其設(shè)定為白色；若點(diǎn)的像素灰度值小于，該點(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á)到最小，則稱與可以匹配，此時(shí)與對(duì)應(yīng)的圖片可以左右拼接。2、圖片上下拼接的數(shù)學(xué)模型 類似地，設(shè)分別表示上下放置的兩張圖片對(duì)應(yīng)的數(shù)字矩陣，定義上面矩陣的最后一行與下面矩陣的第一行之間的偏差函數(shù)為：其中，分別表示矩陣第行和第行的元素。 對(duì)于給定的矩陣，若存在矩陣，使得與之間的偏差函數(shù)達(dá)到最小，則稱與可以匹配，此時(shí)與對(duì)應(yīng)的圖片可以上下拼接。我們稱上述基于數(shù)字矩陣之間列（或行）距離的圖片拼接模型為最小二乘法拼接復(fù)原模型。5.1.4算法與求解（一） 算法思想第一步，對(duì)附件中的19幅圖片分別進(jìn)行灰度處理，然后取灰度閾值，進(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ù)上述的步驟，依次得到所有碎紙片的排列，即可拼接成完整圖片。（二） 附件1、2的拼接復(fù)原結(jié)果附件1和附件2的拼接順序如下表：（附件1的算法程序見(jiàn)附錄一，復(fù)原圖片見(jiàn)附錄二；附件2的算法程序見(jiàn)附錄三，復(fù)原圖片見(jiàn)附錄四）表2 附件1拼接順序8141215310216145913181171706表3 附件2拼接順序36271518110519131081214171645.2問(wèn)題二的模型建立與算法5.2.1圖片的數(shù)字化處理步驟一：將附件所給的BMP格式圖片轉(zhuǎn)換成JPG格式的圖片；步驟二：對(duì)圖片進(jìn)行灰度處理；步驟三：然后進(jìn)行二值化處理；最后，得到209張圖片的數(shù)字化矩陣。5.2.2聚類分析對(duì)于碎紙機(jī)既縱切又橫切的情形，與問(wèn)題一僅縱切相比，圖片變小，因而每張圖片包含的信息量明顯變小，如果僅利用最小二乘法，碎片之間的匹配不唯一。為了解決這個(gè)問(wèn)題，我們利用聚類分析法，對(duì)碎片先進(jìn)行分類。經(jīng)觀察測(cè)試，原始文檔碎片具有下列特點(diǎn)：（1）字體大?。鹤煮w的最大高度和最大寬度一致。（2）切割的均勻性：同方向的切割線平行，圖片大小均相等，沿縱橫方向按直線切割。（3）文字的行距：文字的行間距等同，段落間距為定值。為了對(duì)209幅圖片進(jìn)行聚類分析，如圖2所示，我們定義聚類指標(biāo)如下： 表示圖片上端裁接處的字體長(zhǎng)度，我們稱之為裁截文字長(zhǎng)度； 為行間距；表示圖片上端文字與切割線之間的空白距離，我們稱之為裁截空白距離；為字體高度，其中，。圖2 圖片聚類指標(biāo)示意圖令或，稱為第張圖片的裁截距，由圖2，如，則。一般地，圖片從上往下看，不同的裁截線形成的裁截文字長(zhǎng)度不同，文字間的行間距相同，所以，如果裁接處的文字長(zhǎng)度不相等，那么文字與空白間距之和就不相等。根據(jù)的不同取值，下面對(duì)圖片進(jìn)行分類。根據(jù)二值化矩陣的特點(diǎn)以及文字的特征，只要存在文字，則矩陣的某一行元素一定存在0元素，且在文字之間的元素為1。如下圖所示：圖3 文字特征圖利用軟件進(jìn)行編程，將每個(gè)圖片的裁截文字長(zhǎng)度、行間距、裁截空白距離、字體高度以及裁截距的結(jié)果以的形式輸出到表格之中。（程序見(jiàn)附錄五）按裁接距進(jìn)行聚類分析，使用軟件分析處理后，得到聚類中心分布圖如下所示：表4 聚類中心聚類中心聚類1234567891011V1752321204458133641096978根據(jù)表4所示的聚類中心，對(duì)表格中裁截距進(jìn)行初步分類。得到聚類結(jié)果如下表所示：表5 每個(gè)聚類中的案例數(shù) 每個(gè)聚類中的案例數(shù)聚類12.000236.000318.00041.000546.000638.00071.000836.00091.0001011.0001119.000有效209.000缺失.000根據(jù)聚類結(jié)果發(fā)現(xiàn)，并不能將圖片平均分成11個(gè)組。這時(shí)需要增加信息量來(lái)更好地進(jìn)行分類，進(jìn)一步觀察圖2，我們可以發(fā)現(xiàn)：圖片的上端裁截處可能是文字，也可能為空白。但是裁截距可能相等，此時(shí)通過(guò)圖片上端裁截處是空白還是文字加以人工分類。用將數(shù)據(jù)導(dǎo)出到中并進(jìn)行分析，結(jié)果如下：-100-50050050100150200250高度圖片數(shù)量圖4 分析結(jié)果由圖4可以看出：圖片大體分為11個(gè)組別，為了得到更精確地聚類結(jié)果，通過(guò)軟件，我們?cè)俅未_立聚類中心如下圖所示：表6 第二次聚類中心最終聚類中心聚類1234567891011V125240-38-93-69-841534-23-10通過(guò)上面兩次聚類，確立了兩個(gè)不同聚類中心。利用第一次確立的裁接距的聚類中心對(duì)圖片進(jìn)行初步分類，然后利用裁截文字或者裁接空白再次進(jìn)行判別，最終將圖片分成了11組。如下表所示：（以上的算法都是在軟件下操作，程序見(jiàn)附件六）表7 各組圖片數(shù)量組別012345678910111213圖片數(shù)量3188191918181918181810193由上表可以看出大部分圖片已經(jīng)分出組別，其中有4個(gè)組達(dá)到了19張圖片，有6個(gè)組有18張圖片，僅缺少一張圖片。此時(shí)我們進(jìn)行人工干預(yù)，根據(jù)每組圖片總數(shù)目應(yīng)為19，且每類都應(yīng)存在可作為文件左右邊緣的碎紙片，我們對(duì)少量圖片進(jìn)行歸類可得到如下分組結(jié)果。如下表： 表8 聚類后的結(jié)果組別1234567891011圖片編號(hào)26183341350154111918912421610717402220232414432129322789283626253147663745331014952303539581064453601025461413851771094856711085763504673841105568801136567627482901255970831149169768110794139649385117957286881159714575126132119118788710312811215092137133123129791001051341211579813815214014196120122135124173104153156146143991421301591271811111581651511781161471481601361821711661701541861311681611691441841721741981551881621791671761491871801752001851901631911891991641972011962021941921771951932031832042062082052075.2.3圖片的拼接模型、算法與求解（一） 算法思想下面我們分兩步來(lái)做，第一步，對(duì)每組碎紙片進(jìn)行拼接；第二步，將各組進(jìn)行拼接。最終完成文件復(fù)原。在已知文件切為1119的碎紙片情況下，將圖片進(jìn)行聚類分析得到了11個(gè)組后。利用碎紙片左右邊緣為空白的特點(diǎn)判斷出文件左側(cè)11個(gè)碎紙片，再利用問(wèn)題一模型和算法，對(duì)每個(gè)組進(jìn)行匹配拼接，可得到11個(gè)拼接好的圖片，之后仍然按照問(wèn)題一的模型和算法將這11張圖片拼接成完整的圖片。（二） 圖片的左邊緣確定根據(jù)碎紙片邊緣特征，利用matlab對(duì)圖片處理后得到數(shù)字化矩陣，根據(jù)最小二乘法進(jìn)行分析得到16個(gè)可作為文件左邊緣的碎紙片，編號(hào)如下：（程序詳見(jiàn)附錄七）7，14，29，38，49，61，62，67，71，80，89，94，125，135，143，168。已知文件分為1119的碎紙片,那么存在5個(gè)不是左邊緣碎紙片。根據(jù)文件頁(yè)邊距一定的特點(diǎn)，此時(shí)進(jìn)行人工篩選，明顯排除了編號(hào)分別62，67，80，135，143的圖片作為文件左邊緣的可能。此刻，我們也得到了左邊緣碎紙片的序號(hào)：7，14，29，38，49，61， 71，80，89，94，125，168。（三） 圖片的各組拼接第一步，計(jì)算機(jī)處理，利用問(wèn)題一的列偏差函數(shù)進(jìn)行圖片拼接，現(xiàn)在我們以表4中的第9組為例，得到如下結(jié)果：（程序詳見(jiàn)附錄八）圖6 以第9組為例的拼接結(jié)果1第二步，人工干預(yù)，由于每組有19個(gè)圖片，可以明顯觀察到排序的時(shí)候有一個(gè)圖片沒(méi)有出現(xiàn)，而且另一個(gè)圖片重復(fù)出現(xiàn)了兩次。此時(shí)我們進(jìn)行人工拼接。得到正確的拼接結(jié)果，圖片如下：圖7 以第9組為例的拼接最終結(jié)果其余分組按照相同方法可得到11組的拼接結(jié)果，這里我們不在一一贅述，發(fā)現(xiàn)每組的拼接均無(wú)誤，這說(shuō)明我們的分類達(dá)到了預(yù)期的效果。（四） 圖片的整體拼接上一步驟中我們得到了1119的碎紙片拼接而成的11個(gè)等大小的紙片，那么接下來(lái)，根據(jù)行偏差函數(shù)，判斷11個(gè)紙片的上下拼接順序，可以得到以下編號(hào)的圖片可以上下拼接： 完成以上組合的拼接后，進(jìn)行人工干預(yù)，完成圖片的整體拼接，結(jié)果如下（復(fù)原圖片詳見(jiàn)附錄九）：表9 附件3拼接順序049054065143186002057192178118190095011022129028091188141061019078067069099162096131079063116163072006177020052036168100076062142030041023147191050179120086195026000087018038148046161024035081189122103130193088167025008009105074014128003159082199135012073160203169134039031051107115176094034084183090047121042124144077112149097136164127058043125013182109197016184110187066106150021173157181204139145029064111201005092180048037075055044206010104098172171059007208138158126068175045174001137053056093153070166032196071156083132200017080033202198015133170205085152165027060089146102154114040151207155140185108117004101113194119123對(duì)于附件4，我們按照與處理附件3相同的模型和算法進(jìn)行處理，得到拼接結(jié)果表格如下，（復(fù)原圖片詳見(jiàn)附錄十）：表10 附件4拼接順序1910750111541901840021041800641060041490322040650390671472011481701961980941131640781030910801010261000060170281460860511070290401581860980241171500050590580920300370461270191940931410881211261051551141761821510220572020711650821591390011290631381530530381231201750850501601870972030310200411081161360730362071350150760431990451730791611791432080210070490611190331421680621690541921331181891621971120700840600140681741371950080471721560960230991220901851091321810950691671631661881111442060031300340131100250271781710420662050101570741450831340550180560350160091831520440810771282001310521251401930870890480720121771240001021155.3問(wèn)題三的模型建立與算法對(duì)于第三個(gè)問(wèn)題，圖片的數(shù)量成倍的增長(zhǎng)，我們不能單純的利用圖片邊緣的特征進(jìn)行拼接與復(fù)原，在問(wèn)題二按上邊緣裁截距進(jìn)行聚類分析的基礎(chǔ)上，增加圖片下邊緣裁截距，綜合進(jìn)行聚類分析。具體流程圖如下所示：自下而上計(jì)算圖片的裁截距與裁截空白間距輸入圖片將圖片灰度處理將灰度處理后的圖片二值化處理自上而下計(jì)算圖片的裁接距與裁截空白間距（或裁截文字長(zhǎng)度）高度是否相似?運(yùn)用問(wèn)題二的方法進(jìn)行匹配YN標(biāo)注備選匹配成功？備存Y加入備選圖片進(jìn)行匹配N匹配成功，備存完成組圖圖8 算法流程圖5.3.1圖片的初次聚類運(yùn)用問(wèn)題二的聚類方法，利用進(jìn)行數(shù)據(jù)處理（程序見(jiàn)附錄十一），將所得結(jié)果導(dǎo)入，做出圖片上邊緣的裁截文字長(zhǎng)度（或者裁截空白長(zhǎng)度）的分布圖圖9 附件5圖片的裁截文字長(zhǎng)度分布圖用進(jìn)行快速聚類分析，可以看出能將一部分圖片進(jìn)行準(zhǔn)確的分類，利用模型一的方法對(duì)分類后的圖片進(jìn)行邊緣匹配，得到類似于下圖的片段圖像。圖10 匹配正確的片段圖5.3.2圖片的再聚類由于圖片的雙面性，我們?cè)趯?duì)其正面（反面）進(jìn)行正確匹配之后，則其反面（正面）也就確定出來(lái)，這大大減少了數(shù)據(jù)量。但某些分類后卻拼接失敗的情況，使得拼接更加的困難。在第二個(gè)問(wèn)題中，我們利用圖片從上到下文字的特征增加了信息量，為了更好進(jìn)行圖片匹配與拼接，對(duì)于問(wèn)題三，我們?cè)俅卧黾訄D片從下到上的文字特征。在圖片初次聚類的前提下，利用從下到上的裁截距，按照與問(wèn)題二類似的辦法進(jìn)行第二次聚類，步驟同上，得到圖片的裁截文字長(zhǎng)度的分布直方圖：圖11 圖片裁截文字長(zhǎng)度的分布直方圖5.3.3圖片的拼接根據(jù)前兩次圖片的聚類之后，我們?cè)趯?duì)其進(jìn)行分類，將分類后的圖片進(jìn)行邊緣匹配，同時(shí)進(jìn)行人工干預(yù)，挑選出匹配正確的片段，如下圖所示：圖12 匹配正確的片段對(duì)每一類圖片匹配成功后，類似于問(wèn)題二，利用計(jì)算機(jī)自動(dòng)拼接與人工干預(yù)相結(jié)合，將所有各類進(jìn)行整體拼接，結(jié)果如下：（復(fù)原圖片見(jiàn)附錄12）表13 附件5其中一面的拼接順序表14 附件5另一面的拼接順序六、模型的評(píng)價(jià)與改進(jìn)6.1模型的優(yōu)點(diǎn)（1） 模型一對(duì)于解決縱切碎紙片的問(wèn)題上，達(dá)到了很好的效果，對(duì)于所得的結(jié)果正確率也是100%的，對(duì)于解決此類問(wèn)題提供了良好的思想。（2） 模型二充分考慮了碎紙片邊緣的匹配問(wèn)題以及文字內(nèi)部的特征信息，對(duì)于既縱切又橫切的情形，先進(jìn)行了聚類將圖片進(jìn)行了分組，大大減少了工作量，而且增加了準(zhǔn)確度。6.2 模型的缺點(diǎn)（1） 對(duì)于問(wèn)題一與問(wèn)題二，所給的完整圖片里面含有大量的的文字，所以我們可以利用其文字特征，該結(jié)果也存在一定的偶然性。（2） 對(duì)于問(wèn)題三，對(duì)于大信息量的圖片信息，只利用問(wèn)題二的解決辦法只能將部分的圖片進(jìn)行分類，而不能單純用計(jì)算機(jī)進(jìn)行完整的拼接。6.3 模型的改進(jìn)方向（1） 在問(wèn)題一里面我們只考慮了邊緣區(qū)域的匹配，由于結(jié)果正確所以沒(méi)有繼續(xù)增加條件保證其準(zhǔn)確率。（2） 在設(shè)計(jì)模型二的時(shí)候，只考慮了圖片從上到下的裁接距與裁截文字長(zhǎng)度的方面，還應(yīng)該加上其在圖片從下往上的數(shù)據(jù)。七、參考文獻(xiàn)1黃添強(qiáng)，陳智文，蘇立超等. 利用內(nèi)容連續(xù)性的數(shù)字視頻篡改檢測(cè)J. 南京大學(xué)學(xué)報(bào)（自然科學(xué)版），2011,47（5）：493-503.2 羅智中. 基于線段掃描的碎紙片邊界檢測(cè)算法研究 J. 儀器儀表學(xué)報(bào)，2011,32（2）：289-294.3 白宗文. 基于HALCON與圖像拼接的文物修復(fù)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)J. 電子設(shè)計(jì)工程，2013,21（9）：24-26.4 李利軍，李云偉. 基于圖像灰度的拼接技術(shù)研究J. 計(jì)算機(jī)與數(shù)字工程，2007,35（9）：128-130.5 賈海燕，朱良家，周宗潭等. 一種碎紙自動(dòng)拼接中的形狀匹配方法J. 計(jì)算機(jī)仿真，2006,23（11）：180-183.八、附錄附錄一：%以下程序的運(yùn)行，請(qǐng)注意文件存放的位置！%此程序用來(lái)解決附件1的圖片匹配與連接A=zeros(19,19); %共十九個(gè)紙條for j=1:19 str=D:附件附件1; I=imread(str,num2str(j),.jpg);%依次讀取每一幅圖像 i1=rgb2gray(I); %i1灰度圖像 i2=im2bw(i1); %i2是二值圖像 a=i2(:,72,1); %取紙片右邊緣 str=D:附件附件1; for i=1:19 I=imread(str,num2str(i),.jpg); %依次讀取每一幅圖像 i1=rgb2gray(I); %i1灰度圖像 i2=im2bw(i1); %i2是二值圖像 mi=i2(:,1,1); %取紙片左邊緣 ni=a-mi; A(j,i)=sqrt(dot(ni,ni); endendxlswrite(D:photo1.xls,A,A1:S19); %將矩陣元素導(dǎo)入excel表格%判斷相鄰圖片并自動(dòng)連接連接a=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; %求出文件最左側(cè)紙張 end endend str=D:附件附件1;z= imread(str,num2str(first),.jpg);for m=1:18 m=1; str=D:附件附件1; x = imread(str,num2str(first),.jpg); %記錄上一張紙條 y=imread(str,num2str(a(first),.jpg);%記錄下一張紙條 x=z; %保存已拼接紙條 z = x,y; first=a(first);endimshow(z)附錄二： 圖13 附件1拼接圖片附錄三：圖14 附件2拼接圖片附錄三：%以下程序的運(yùn)行，請(qǐng)注意文件存放的位置！%此程序用來(lái)解決附件2的圖片匹配與連接A=zeros(19,19); %共十九個(gè)紙條for j=1:19 str=D:附件附件2; I=imread(str,num2str(j),.jpg);%依次讀取每一幅圖像 i1=rgb2gray(I); %i1灰度圖像 i2=im2bw(i1); %i2是二值圖像 a=i2(:,72,1); %取紙片右邊緣 str=D:附件附件2; for i=1:19 I=imread(str,num2str(i),.jpg); %依次讀取每一幅圖像 i1=rgb2gray(I); %i1灰度圖像 i2=im2bw(i1); %i2是二值圖像 mi=i2(:,1,1); %取紙片左邊緣 ni=a-mi; A(j,i)=sqrt(dot(ni,ni); endendxlswrite(D:photo2.xls,A,A1:S19); %將矩陣元素導(dǎo)入excel表格%判斷相鄰圖片并自動(dòng)連接連接a=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; %求出文件最左側(cè)紙張 end endend str=D:附件附件2;z= imread(str,num2str(first),.jpg);for m=1:18 m=1; str=D:附件附件2; x = imread(str,num2str(first),.jpg); %記錄上一張紙條 y=imread(str,num2str(a(first),.jpg);%記錄下一張紙條 x=z; %保存已拼接紙條 z = x,y; first=a(first);end imshow(z)附錄五：A=zeros(209,4);for i=1:209 %for j=1:209 str=C:UsersAdministratorDesktop附件5a; I=imread(str,num2str(i),.jpg);%依次讀取每一幅圖像 i1=rgb2gray(I);%i1灰度圖像 i2=im2bw(i1);% i2是二值圖像，不需要 a=0;b=0;c=0;d=0; j=180; if any(i2(1,:)=0) while (any(i2(j,:)=0) a=a+1; c=c+1; j=j-1; end else while (all(i2(j,:)=1) a=a-1; c=c+1; j=j-1; end end A(i,1)=a; if any(i2(j,:)=0) while (any(i2(j,:)=0) b=b+1; d=d+1; j=j-1; end else while (all(i2(j,:)=1) b=b-1; d=d+1; j=j-1; end end A(i,2)=b; A(i,3)=c+d; A(i,4)=i+791; endxlswrite(D:question1.xls,A,A210:D418);附錄六：%注意！運(yùn)行時(shí)將附件解壓至D盤%該程序用來(lái)對(duì)圖片的二值矩陣進(jìn)行分類A=zeros(209,5);for i=1:209 str= D:附件附件3; I=imread(str,num2str(i),.jpg);%依次讀取每一幅圖像 i1=rgb2gray(I); %i1灰度圖像 i2=im2bw(i1); % i2是二值圖像，不需要 a=0;b=0;c=0;d=0; j=1; if any(i2(1,:)=0) while (any(i2(j,:)=0) a=a+1; c=c+1; j=j+1; end else while (all(i2(j,:)=1) a=a-1; c=c+1; j=j+1; end end A(i,1)=a; if any(i2(j,:)=0) while (any(i2(j,:)=0) b=b+1; d=d+1; j=j+1; end else while (all(i2(j,:)=1) b=b-1; d=d+1; j=j+1; end end A(i,2)=b; A(i,3)=c+d; A(i,5)=i; if A(i,3)30&A(i,3)=40&A(i,3)=44&A(i,3)0 A(i,4)=3; else A(i,4)=4; end elseif A(i,3)=50&A(i,3)0 A(i,4)=5; else A(i,4)=6; end elseif A(i,3)55&A(i,3)0 A(i,4)=7; else A(i,4)=8; end elseif A(i,3)61&A(i,3)0 A(i,4)=9; else A(i,4)=10; end elseif A(i,3)67&A(i,3)76&A(i,3)80 A(i,4