2023年高教社杯全國大學(xué)生數(shù)學(xué)建模競賽B題優(yōu)秀論文

PAGEPAGE21碎紙片的拼接復(fù)原摘要本文主要解決碎紙片拼接復(fù)原問題。利用附件所給碎紙片的數(shù)據(jù)，運(yùn)用蟻群優(yōu)化算法、Adaboost算法、Harris角點(diǎn)檢測算法，利用Matlab軟件編程求解，得到碎紙片拼接復(fù)原結(jié)果。針對問題一，依據(jù)文字所在行的幾何特征，先將文字進(jìn)行二值化處理，得到文字的數(shù)據(jù)信息。運(yùn)用蟻群優(yōu)化全局匹配方案完成整體匹配，利用回溯的Best-First搜索算法，得到最正確候選匹配對，由于碎紙片形狀相似，Best-First搜索算法會大大降低拼接效率，最后建立蟻群優(yōu)化算法模型對復(fù)原結(jié)果進(jìn)行優(yōu)化，得到中、英文拼接復(fù)原圖〔見附錄一〕及順序表〔見表2、表3〕。針對問題二，先對附件3、附件4中的碎紙片進(jìn)行像素特征分析，將每一個(gè)矩形像素特征區(qū)域的白色區(qū)域設(shè)為0、黑色區(qū)域設(shè)為1，利用Adaboost算法對碎紙片進(jìn)行分類處理，再依據(jù)矩形像素特征進(jìn)行匹配，得到拼接復(fù)原中文、英文圖片。對每次匹配循環(huán)進(jìn)行人工干預(yù)得出碎紙片的拼接復(fù)原順序圖〔見附錄二〕及順序表〔見表4、表6〕。針對問題三，在比照經(jīng)典角點(diǎn)檢測算法的根底上，利用附件5中圖片的信息，運(yùn)用Harris角點(diǎn)檢測的多層匹配圖像拼接算法，得到圖片的角點(diǎn)信息。采用標(biāo)準(zhǔn)互相關(guān)聯(lián)法和互信息法對Harris角點(diǎn)進(jìn)行粗匹配，之后根據(jù)特征點(diǎn)周圍的邊緣信息過濾為匹配點(diǎn)，再用RANSAC進(jìn)行精確匹配，得到一幅完整的拼接復(fù)原圖像。最后，運(yùn)用神經(jīng)網(wǎng)絡(luò)邊緣檢測算法進(jìn)行優(yōu)化，快速的獲取準(zhǔn)確的碎紙片的拼接復(fù)原順序圖〔見附錄三〕及順序表〔見表8、表9〕。關(guān)鍵詞：蟻群優(yōu)化算法Adaboost算法Harris角點(diǎn)檢測神經(jīng)網(wǎng)絡(luò)1問題重述破碎文件的拼接在司法物證復(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ā)碎紙片的自動拼接技術(shù)，以提高拼接復(fù)原效率。請討論以下問題：〔1〕對于給定的來自同一頁印刷文字文件的碎紙機(jī)破碎紙片〔僅縱切〕，建立碎紙片拼接復(fù)原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，請寫出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。復(fù)原結(jié)果以圖片形式及表格形式表達(dá)〔見【結(jié)果表達(dá)格式說明】〕。〔2〕對于碎紙機(jī)既縱切又橫切的情形，請?jiān)O(shè)計(jì)碎紙片拼接復(fù)原模型和算法，附件3、附件4給出的中、英文各一頁文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原并針對附件過程需要人工干預(yù)，請寫出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。復(fù)原結(jié)果表達(dá)要求同上?！?〕上述所給碎片數(shù)據(jù)均為單面打印文件，從現(xiàn)實(shí)情形出發(fā)，還可能有雙面打印文件的碎紙片拼接復(fù)原問題需要解決。附件5給出的是一頁英文印刷文字雙面打印文件的碎片數(shù)據(jù)。請嘗試設(shè)計(jì)相應(yīng)的碎紙片拼接復(fù)原模型與算法，并就附件5的碎片數(shù)據(jù)給出拼接復(fù)原結(jié)果，結(jié)果表達(dá)要求同上。2問題分析2.1問題一的分析假設(shè)對中、英文各一頁文件的縱切碎紙片拼接復(fù)原，需考慮復(fù)原的碎紙片之間的邊界銜接、字跡線條、圖片屬性、文字的行高、文字行間距及文字?jǐn)嗑€等信息。利用碎紙片文字所在行的幾何特征，先對文字進(jìn)行二值化處理。借助蟻群優(yōu)化算法的全局匹配方案，完成整體匹配。再運(yùn)用回溯Best-First搜索算法，得到最正確候選匹配對。考慮到碎片形狀特征相似度高等原因，不合理的候選匹配對可能大量存在，導(dǎo)致拼接效率大大降低。再建立蟻群優(yōu)化算法進(jìn)行優(yōu)化，利用Matlab編程得到碎紙片拼接復(fù)原結(jié)果。2.2問題二的分析假設(shè)將中、英文各一頁文件的縱切碎紙片拼接復(fù)原，利用Adaboost算法，先將附件3、附件4中給出的碎紙片分別進(jìn)行編號，再將所有待匹配碎紙片進(jìn)行初始化，然后進(jìn)行錯(cuò)誤率分析，根據(jù)誤差分析結(jié)果來調(diào)整權(quán)重，得到分類結(jié)果。對所有碎片分類結(jié)果進(jìn)行矩形像素特征分析，最后由矩形像素特征匹配出碎紙片的原圖，對于匹配的循環(huán)進(jìn)行人工干預(yù)得出碎紙片的排列順序表。2.3問題三的分析假設(shè)對雙面打印文件的碎紙片拼接復(fù)原，需考慮正反面文字的對應(yīng)情況，先用人工干預(yù)的方式對文件的局部碎紙片拼接復(fù)原。圖像拼接復(fù)原需考慮圖像特征，本文基于碎紙片的角點(diǎn)特征，利用附件5給出的一頁英文印刷文字雙面打印文件的碎紙片數(shù)據(jù)，在比照經(jīng)典角點(diǎn)檢測算法的根底上，運(yùn)用Harris角點(diǎn)檢測的多層匹配的圖像拼接算法，采用標(biāo)準(zhǔn)互相關(guān)聯(lián)法對Harris角點(diǎn)進(jìn)行粗匹配，之后根據(jù)特征點(diǎn)周圍的邊緣信息過濾為匹配點(diǎn)，再用RANSAC進(jìn)行精確匹配，得到一幅完整的拼接復(fù)原圖像。出于對結(jié)果準(zhǔn)確性以及拼接快速性的考慮，運(yùn)用BP神經(jīng)網(wǎng)絡(luò)邊緣檢測算法將結(jié)果進(jìn)行優(yōu)化。最后，利用數(shù)學(xué)期望、方差等統(tǒng)計(jì)特性參數(shù)對檢測出來的邊緣圖像進(jìn)行質(zhì)量評價(jià)。3模型假設(shè)〔1〕假設(shè)碎紙片在復(fù)原過程中沒有損壞、喪失的現(xiàn)象；〔2〕假設(shè)碎紙機(jī)橫、縱切割文件規(guī)那么，不出現(xiàn)異常狀況；〔3〕假設(shè)模型計(jì)算的碎紙片拼接復(fù)原結(jié)果是唯一的；〔4〕假設(shè)附件所給中、英文文件碎紙片數(shù)據(jù)不混淆；〔5〕假設(shè)同一附件中紙片切割的大小、形狀相同；4符號說明符號意義一個(gè)候選匹配對待匹配紙片像素特征估計(jì)矩陣閾值總誤差第個(gè)輸出神經(jīng)元的實(shí)際值輸出神經(jīng)元的期望值5模型建立與求解5.1模型一的建立與求解5.1.1常規(guī)文檔碎紙片計(jì)算機(jī)拼接方法一般利用碎紙片邊緣的尖點(diǎn)特征、尖角特征、面積特征，搜索與之匹配的相鄰碎紙片進(jìn)行拼接，這種基于邊界幾何特征的拼接方法并不適用于邊緣性狀相似的碎紙片。題中給定的來自同一頁印刷文字文件的碎紙機(jī)破碎紙片〔僅縱切〕的形狀相似，拼接時(shí)如果只利用碎紙片的邊界特征，拼接效果并不理想。對邊緣相似的碎紙片的拼接，理想的計(jì)算機(jī)拼接過程應(yīng)與人工拼接過程類似，即拼接時(shí)不但要考慮待拼接碎紙片邊緣是否匹配，還要判斷碎片內(nèi)的字跡斷線或碎片內(nèi)的文字內(nèi)容是否匹配以及理解碎片內(nèi)文字圖像含義。利用現(xiàn)有的技術(shù)，完全可以獲取碎紙片文字所在行的幾何特征信息，比方文字行的行高、文字行的間距及文字?jǐn)嗑€等信息?，F(xiàn)有技術(shù)對碎紙片拼接復(fù)原的流程圖，如圖一所示：圖一碎紙片拼接復(fù)原流程圖二維碎片自動拼接問題主要有兩種方案：基于輪廓的拼接和基于內(nèi)容的拼接。本文利用文字的特征運(yùn)用蟻群優(yōu)化的全局匹配對碎紙片自動拼接。正確合理參與拼接的碎片之間有一定的空間約束，不合理的拼接那么可能會不滿足這些約束而在候選匹配隊(duì)之間造成矛盾。全局匹配是指在局部拼接的根底上，利用候選匹配隊(duì)之間的矛盾剔除一些不合理的匹配，從而構(gòu)建一個(gè)彼此兩兩相容的候選匹配對集合，從而完成整體的匹配。這里提到的不合理，是從全局的角度考慮的。初步全局匹配完成后，用回溯的Best-First搜索算法將局部匹配得到的候選匹配對按照相似性度量進(jìn)行排序，找出最正確候選匹配對。再用蟻群優(yōu)化算法進(jìn)行優(yōu)化?；厮莸腂est-First搜索算法流程圖如圖二所示：圖二基于回溯的Best-First搜索算法在實(shí)際的碎片拼接過程中，由于碎片形狀特征相似等原因，不合理的候選匹配對大量存在。因此回溯會大大降低拼接的效率。本文再用蟻群優(yōu)化算法進(jìn)行優(yōu)化求得結(jié)果。基于蟻群優(yōu)化的全局匹配如果完成了局部匹配，那么構(gòu)建了這樣一個(gè)候選匹配對集合。但對于一組碎片的全局匹配來說，用于全局匹配的候選匹配對只需要一局部的正確候選匹配對，而不是全部?？梢圆捎孟伻簝?yōu)化形成一個(gè)匹配路徑，來選取用于全局匹配的候選匹配對。這個(gè)路徑所含的候選匹配對剛好包含多個(gè)碎片。當(dāng)所考慮的問題服從問題相關(guān)約束時(shí)，可用成分的集合的一個(gè)子集來表示，這類問題被稱作子集問題。這里所求的匹配路徑上的候選匹配對是候選匹配對集合的一個(gè)子集，因此，全局匹配也可以看作有特殊約束的子集問題。從另一個(gè)角度，全局匹配也可以看做是一個(gè)求解整體沒有矛盾的最小拼接代價(jià)的最有問題。所以，全局匹配路徑的構(gòu)建，可以借鑒ACO算法用于解決自己問題的方法。設(shè)為候選匹配對集合，表示其中一個(gè)候選匹配對。表示的匹配代價(jià)，表示在路徑構(gòu)建中被選中的狀態(tài)，如果被選中，那么的值為1，否那么為0：表示候選匹配對的個(gè)數(shù)，表示碎片的個(gè)數(shù)。那么基于ACO的全局回復(fù)重建問題定義如下：，，〔〕被選中的候選匹配對之間必須是相容的。圖的構(gòu)建以及數(shù)據(jù)初始化在構(gòu)建圖中，成分集合對應(yīng)著候選匹配對的集合，而連接集合不完全連接候選匹配對，與一個(gè)相容性列表相關(guān)聯(lián)。用表示候選匹配對和之間的相容系數(shù)，表示候選匹配對的局部相似性度量，表示的信息素信息素初始化如下：其中表示所選匹配對中相似性度量的最小值，為最大值。候選匹配對的匹配代價(jià)也是同相似性度量相關(guān)聯(lián)的,ACO算法中的路程代價(jià)通常表示成整數(shù)所以本文中的匹配代價(jià)也采用類似表示:路徑構(gòu)建與信息素更新人工螞蟻根據(jù)信息素的濃度的大小，在路徑中節(jié)點(diǎn)的領(lǐng)域并集中選擇下一個(gè)訪的節(jié)點(diǎn)。當(dāng)前位于節(jié)點(diǎn)的人工螞蟻選擇作為下一個(gè)訪問節(jié)點(diǎn)的概率是：其中：是人工螞蟻訪問過的節(jié)點(diǎn)的領(lǐng)域，是一個(gè)調(diào)節(jié)啟發(fā)式比重的參數(shù)，和是節(jié)點(diǎn)和的匹配代價(jià)。每次路徑構(gòu)建完成后，人工螞蟻只在當(dāng)前最優(yōu)路徑的節(jié)點(diǎn)上釋放信息素。釋放信息素的多少可用下式表示。其中，為信息素釋放比例系數(shù)，為當(dāng)前最優(yōu)路徑代價(jià)，信息素最大值，為當(dāng)今最優(yōu)路徑。路徑中的候選匹配對必須是彼此兩兩相容的,而矛盾的普遍存在導(dǎo)致很多人工螞蟻構(gòu)建路徑失敗。路徑構(gòu)建失敗必然產(chǎn)生很多不完全路徑,對這些路徑上的節(jié)點(diǎn)進(jìn)行信息素更新,以此來實(shí)現(xiàn)信息的蒸發(fā)：其中，為信息素蒸發(fā)系數(shù)，滿足，為信息素的最小值。路徑構(gòu)建過程中，下一節(jié)點(diǎn)的選取都是在已選節(jié)點(diǎn)的鄰域中進(jìn)行的，如果以構(gòu)建路徑中候選匹配對已包含所有碎片，那么構(gòu)建路徑成功。每迭代一次，信息素列表都更新一次如果迭代次數(shù)超過迭代次數(shù)下限,并且信息素列表的標(biāo)準(zhǔn)差與上一次迭代相比沒有變化,那么停止迭代,或者迭代次數(shù)已經(jīng)到達(dá)迭代上限,那么停止迭代。在局部匹配的根底上，如表1所示設(shè)置參數(shù)進(jìn)行試驗(yàn)：表1基于ACO的局部匹配試驗(yàn)參數(shù)190.005501010.0517019表中，為螞蟻的數(shù)量，表示信息素蒸發(fā)系數(shù)，表示信息素釋放比例，表示啟發(fā)式比重參數(shù)，表示最大信息濃度，表示最小信息濃度，表示最大迭代次數(shù)，表示最小迭代次數(shù)。模型一的求解本文選取附件1中碎紙片〔中、英文〕的數(shù)據(jù)，運(yùn)用蟻群優(yōu)化算法，利用Matlab軟件編程〔見附錄一〕求解，得到中文拼接復(fù)原圖〔見附錄一〕，英文拼接復(fù)原圖〔見附錄一〕。中、英文拼接復(fù)原順序見下表2，英文拼接復(fù)原順序見下表3：表2中文縱切碎片數(shù)據(jù)拼接復(fù)原順序表08141215031002160104050913181107170006表3英文縱切碎片數(shù)據(jù)拼接復(fù)原順序表0030060020070150180110000050010090130100080120140170160045.2模型二的建立與求解模型二的建立對于碎紙機(jī)既縱切又橫切的情形，要求設(shè)計(jì)碎紙片拼接復(fù)原模型和算法，并針對附件3、4給出的中、英文各一頁文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。相對于問題一中的只有縱切的情形，本問既縱切又橫切的情形在日常生活中更為普遍，相對來說解決這類問題更具有實(shí)際意義。本問運(yùn)用Matlab軟件通過Adaboost算法建立數(shù)學(xué)模型進(jìn)行求解。第一步，將附件3、4中給出的碎紙片進(jìn)行編號。其中，為輸入待匹配碎紙片，是分類類別標(biāo)志，,其中，0表示空白區(qū)域，1表示黑色區(qū)域，為一共的待匹配碎紙片數(shù)量。第二步，指定循環(huán)的次數(shù)T，T將決定最后強(qiáng)分類器中弱分類器的數(shù)目。第三步，初始化權(quán)值：,為樣本中空白區(qū)域的初始化權(quán)值，為樣本中的黑色區(qū)域初始化權(quán)值，其中，為樣本中的空白區(qū)域所占像素?cái)?shù)，為樣本中黑色區(qū)域所占像素?cái)?shù)。第四步，對歸一化權(quán)值：對每個(gè)特征，匹配一個(gè)弱分類器；計(jì)算對應(yīng)所有特征的弱分類器的加權(quán)錯(cuò)誤率。選取具有最小錯(cuò)誤率的弱分類器參加到強(qiáng)分類器中。按照這個(gè)最正確弱分類器，調(diào)整權(quán)重：其中，表示被正確的分類，表示被錯(cuò)誤分類。進(jìn)行T輪匹配完畢，最后得到強(qiáng)分類器為：對于每一個(gè)碎紙片，含有大量的矩形像素特征〔一般有上萬個(gè)〕設(shè)像素特征為。在這個(gè)龐大的像素特征集合中只有一小局部像素特征能夠用來構(gòu)建高效的分類器。我們通過前面的算法，在每一輪循環(huán)中從眾多的矩形特征中選擇最正確矩形像素特征。最正確特征對應(yīng)的弱分類器的表達(dá)式為：其中，是矩形像素特征的特征值，為弱分類器的閾值，表示不等式方向，可取。由多個(gè)最正確弱分類器按照一定權(quán)值組合而成的較為復(fù)雜的分類器為強(qiáng)分類器。其中為待匹配碎紙片，為構(gòu)成該強(qiáng)分類器的第個(gè)弱分類器。上式右邊為該強(qiáng)分類器的閾值。的判斷結(jié)果為0或者1，1表示接受，即矩形像素特征匹配成功；0表示拒絕，即矩形像素特征匹配失敗。級聯(lián)分類器是由多個(gè)強(qiáng)分類器組成。如以下圖三所示：圖三碎紙片匹配流程圖目標(biāo)紙片配對成功以后匹配成功以后進(jìn)行下一輪循環(huán)，得到下一循環(huán)的匹配紙片，最終得到附件3、附件4給出碎紙片的拼接復(fù)原圖。在循環(huán)過程中運(yùn)用記號的方式進(jìn)行人工干預(yù)，得到碎紙片的排列順序。模型二的求解利用附件3、附件4的數(shù)據(jù)，運(yùn)用Adaboost算法，借助Matlab軟件求解，得到中文拼接復(fù)原圖〔見附錄二〕，英文拼接復(fù)原圖〔見附錄二〕。中文拼接復(fù)原順序見下表4，英文拼接復(fù)原順序見下表5：表4中文橫縱切碎片數(shù)據(jù)拼接復(fù)原順序表049054065143186002057192178118190095011022129028091188141061019078067069099162096131079063116163072006177020052036168100076062142030041023147191050179120086195026001087018038148046161024035081189122103130193088167025008009105074071156083132200017080033202198015133170205085152165027060014128003159082199135012073160203169134039031051107115176094034084183090047121042124144077112149097136164127058043125013182109197016184110187066106150021173157181204139145029064111201005092180048037075055044206010104098172171059007208138158126068175045174000137053056093153070166032196089146102154114040151207155140185108117004101113194119123表5英文縱切碎片數(shù)據(jù)拼接復(fù)原順序表19107501115419018400210418006410600414903220406503906714720114817019619809411316407810309108010102610000601702814608605110702904015818609802411715000505905809203003704612701919409314108812112610515511417618215102205720207116508215913901112906313815305303812312017508505016018709720303102004110811613607303620713501507604319904517307916117914320802100704906111903314216806216905419213311818916219711207008406001406817413719500804917215609602309912209018510913218109506916716316618811114420600313003401311002502717817104206620501015774145083134055018056035016009183152044081077128200131052125140193087089048072012177124000102115模型二的檢驗(yàn)對于模型二得到的結(jié)果圖像〔附錄二〕通過人工干預(yù)的方式進(jìn)行檢驗(yàn)，發(fā)現(xiàn)圖像中有一處碎片不能確定復(fù)原位置，通過表格得到該碎片為049.bmp。得到正確的碎片排列順序?yàn)楸恚Y(jié)果見下表6：表6檢驗(yàn)之后英文碎片數(shù)據(jù)拼接復(fù)原順序表191075011154190184002104180064106004149032204065039067147201148170196198094113164078103091080101026100006017028146086051107029040158186098024117150005059058092030037046127019194093141088121126105155114176182151022057202071165082159139011129063138153053038123120175085050160187097203031020041108116136073036207135015076043199045173079161179143208021007049061119033142168062169054192133118189162197112070084060014068174137195008172156096023099122090185109132181095069167163166188111144206003130034013110025027178171042066205010157741450831340550180560350160091831520440810771282001310521251401930870890480720121771240001021155.3模型三的建立與求解圖像特征是用于區(qū)分一個(gè)圖像內(nèi)部特征的根本屬性。圖像的特征信息很多，包括像素灰度特征、區(qū)域特征、色彩特征、輪廓特征、邊緣特征以及角點(diǎn)特征等。圖像的特征提取范圍很廣，從圖像中提取什么樣的特征，需要根據(jù)具體要求和應(yīng)用來定。角點(diǎn)特征是圖像拼接算法中最常用的匹配方法。本文基于文字角點(diǎn)特征，借助計(jì)算機(jī)技術(shù)，采用harris角點(diǎn)檢測的多層匹配圖像拼接算法對碎紙片進(jìn)行拼接復(fù)原。模型三的建立角點(diǎn)檢測算法較為典型的有Moravec角點(diǎn)檢測算法，SUSAN角點(diǎn)算法和Harris角點(diǎn)檢測算法。Moravec角點(diǎn)檢測算法Moravec角點(diǎn)檢測算法的思想是：在圖像中設(shè)計(jì)一個(gè)局部檢測窗口，當(dāng)該窗口沿各個(gè)方向作微笑移動時(shí)，考慮窗口的平均能量變化，當(dāng)該能量變化值超過設(shè)定的閾值時(shí)，就將窗口的中心像素點(diǎn)提取未角點(diǎn)。其步驟為：〔1〕計(jì)算各像素點(diǎn)的興趣值。如圖四所示的是以像素點(diǎn)〔〕為中心的55窗口，記像素點(diǎn)〔〕的灰度為，令圖像的每個(gè)像素點(diǎn)〔〕在以下圖4個(gè)方向相鄰像素灰度差的平方和分別為，取四個(gè)中的最小值作為興趣值。圖四窗口示意圖(2)設(shè)定閾值，將興趣值大于該閾值的像素點(diǎn)作為候選角點(diǎn)。(3)在候選角點(diǎn)中先取局部極大值作為需要的特征點(diǎn)。這是因?yàn)樵谝欢ù笮〉拇翱趦?nèi)，可以有多個(gè)符合該閾值的候選角點(diǎn)，所以要去掉不是最大興趣值的候選點(diǎn)，只保存興趣值最大的點(diǎn)。Harris角點(diǎn)檢測算法Harris角點(diǎn)檢測算法是Moravec算法的改進(jìn)。Harris算法受信號處理中自相關(guān)函數(shù)的啟發(fā)，用一階導(dǎo)數(shù)來描述亮度變化，并給出與自相關(guān)函數(shù)相關(guān)聯(lián)系的矩陣M。M陣的特征值是自相關(guān)函數(shù)的一階曲率。如果兩個(gè)曲率值都很高，那么就認(rèn)為該點(diǎn)是角點(diǎn)特征。Harris角點(diǎn)檢測算法原理：Harris算子的數(shù)學(xué)表達(dá)式：式中，為窗函數(shù)，為圖像灰度值得梯度值?？蔀榫匦未盎蚋咚勾?。它的二階泰勒級數(shù)展開式可以近似為其中，M是22矩陣：其中，，分別為圖像，方向的梯度值。的變化與局部自相關(guān)函數(shù)密切相關(guān)，矩陣M描述了在原點(diǎn)的形狀。假設(shè)，是M地特征值，那么，與局部自相關(guān)函數(shù)的主要曲率成比例，都可以用來描述旋轉(zhuǎn)不變性。求解矩陣：計(jì)算灰度圖像各點(diǎn)的梯度：構(gòu)造自相關(guān)矩陣：由式可得對稱矩陣是一個(gè)二階實(shí)對稱矩陣，必然存在兩個(gè)特征值和。提取特征點(diǎn)：符合兩個(gè)特征值都是極大值的條件時(shí)，該點(diǎn)就為特征值。SUSAN角點(diǎn)檢測算法SUSAN算子的根本原理是能過一個(gè)以點(diǎn)為中心的局部區(qū)域內(nèi)亮度值的分布情況判斷平滑區(qū)域、邊緣和角點(diǎn)。如圖六所示，用一個(gè)近似為圓形的模板放置在圖像上，如果存在一個(gè)區(qū)域，使該區(qū)域?qū)?yīng)圖像的每一個(gè)像素的灰度值與圓心的灰度值相同或接近。就定義該區(qū)域?yàn)楹讼嗨茀^(qū)。圖五模板圖和簡單圖像例如圖本文在求解過程時(shí)利用兩張碎紙片的吻合度，吻合度大的碎紙片有可能拼接在一起，吻合度最高的碎紙片可以拼接復(fù)原。模板a、b、c、d都符合兩張碎紙片的吻合度，模板e(cuò)完全不吻合。具體檢測時(shí)，用給定的圓形模板掃描整個(gè)圖形，比較模板內(nèi)每一像素點(diǎn)與中心像素的灰度值，并給定閾值來判別該像素是否屬于USAN區(qū)域。三種檢測結(jié)果比較分析可知在對簡單物體的檢測時(shí)，檢測到的角點(diǎn)與Harris算法很接近，在對復(fù)雜物體檢測時(shí)，顯然Harris檢測到的角點(diǎn)與Harris檢測到的角點(diǎn)更為到位，Harris角點(diǎn)檢測算法是一種比較有效的特征點(diǎn)檢測方法，效率更高。特征點(diǎn)匹配是指找出需要配準(zhǔn)的兩幅圖片中正確匹配的特征點(diǎn)。本文圍繞Harris角點(diǎn)的互相關(guān)閥和互信息法來設(shè)計(jì)特征匹配算法。標(biāo)準(zhǔn)互相關(guān)法互相關(guān)匹配方法不直接利用特征點(diǎn)鄰域的灰度值來匹配，而是依據(jù)特征點(diǎn)鄰域像素灰度值得互相關(guān)系數(shù)為匹配原那么進(jìn)行匹配。相關(guān)系數(shù)為：式中，和分別為兩幅圖像中特征點(diǎn)相關(guān)聯(lián)窗口內(nèi)像素的灰度值，是相關(guān)系數(shù)，表示窗口大小。計(jì)算相關(guān)系數(shù)的同時(shí)進(jìn)行了歸一化處理，式中，和分別為圖像和特征點(diǎn)相關(guān)窗口內(nèi)像素灰度值的均值：互信息法在圖像配準(zhǔn)中，當(dāng)圖像間的空間位置到達(dá)完全一致時(shí)，圖像之間表達(dá)的信息到達(dá)最大，互信息最大的位置就是圖像的配準(zhǔn)位置?；バ畔⒎ǔＳ糜诙鄳B(tài)圖像配準(zhǔn)?；バ畔⒎ㄓ渺貋矶x，設(shè)圖像的灰度隨機(jī)變量為,其灰度取值范圍為，灰度概率分布為，那么圖像的熵為：設(shè)圖像、，其灰度隨機(jī)變量分別為、，灰度隨機(jī)變量為那么圖像、的互信息可以定義如下：式中，和分別為給定時(shí)的條件熵和給定時(shí)的條件熵?；バ畔⒎ú恍枰獙Σ煌某上衲Ｊ街械膱D像強(qiáng)度做任何假設(shè)，而而是根據(jù)圖像亮度在各自圖像中的相對出現(xiàn)概率以及兩幅圖像重疊區(qū)域的共同出現(xiàn)概率來度量不同圖像之間的對應(yīng)關(guān)系。變換矩陣的估計(jì)：經(jīng)過圖像特征的匹配后，需要估計(jì)兩幅圖像之間的變換矩陣。假設(shè)為匹配集合中一對匹配點(diǎn)對的坐標(biāo)，那么這對匹配點(diǎn)可以建立如下關(guān)系：只要聯(lián)立四對點(diǎn)建立方程組就能求出其中的參數(shù)，求解變換矩陣就是建立圖像間匹配點(diǎn)之間的聯(lián)系的過程。變換矩陣的算法是一種基于代數(shù)距的最小化方法。本文提取的特征點(diǎn)包含有錯(cuò)匹配點(diǎn)對，選取的估計(jì)方法一定有較好的容錯(cuò)能力，本文選用RANSAC來作為變換矩陣的估計(jì)方法。RANSAC算法的根本思想：RANSAC是一種魯棒性的數(shù)據(jù)擬合算法，具有容錯(cuò)能力強(qiáng)的特點(diǎn)。RANSAC算法充分利用所測得所有數(shù)據(jù)，并根據(jù)閾值把他們分成內(nèi)點(diǎn)和外點(diǎn)。其簡化的流程圖如圖五所示：圖五RANSAC算法流程圖RANSAC算法用內(nèi)點(diǎn)來進(jìn)行參數(shù)估計(jì)，剔除不合理的數(shù)據(jù)，從而得到一個(gè)最優(yōu)的結(jié)果?；谏窠?jīng)網(wǎng)絡(luò)邊緣的檢測圖像的邊緣是圖像的最根本特征，邊緣是指其周圍像素灰度有階躍變化的像素的集合。邊緣檢測是圖像分析識別必不可少的環(huán)節(jié)，是一種重要的圖像處理技術(shù)，但傳統(tǒng)的算子算法存在著噪聲和細(xì)節(jié)之間等的矛盾。本文基于BP神經(jīng)網(wǎng)絡(luò)的數(shù)字圖像邊緣檢測可以較好地對碎紙片拼接復(fù)原。初始值確實(shí)定在設(shè)計(jì)中運(yùn)用算法是BP算法，根據(jù)梯度下降法來進(jìn)行權(quán)值得調(diào)節(jié)。BP模型中，神經(jīng)元的函數(shù)為Sigmoid函數(shù)。即：其函數(shù)的導(dǎo)數(shù)為：此函數(shù)的最大值為取零時(shí)，其導(dǎo)數(shù)的取值為1/4，即神經(jīng)元的節(jié)點(diǎn)函數(shù)的導(dǎo)數(shù)最大的點(diǎn)為零點(diǎn)，因此在BP算法中，權(quán)值調(diào)節(jié)最大的點(diǎn)應(yīng)該是零點(diǎn)。對于網(wǎng)絡(luò)的初始權(quán)值、閾值，通常的做法是從[-1,1]或[0,1]區(qū)間上隨機(jī)選取一組數(shù)作為初始權(quán)值進(jìn)行訓(xùn)練。向量的歸一化處理設(shè)計(jì)中的特征向量維數(shù)較大，且大局部的值大于1，為了加快速度，對特征向量進(jìn)行了歸一化處理。另外，設(shè)計(jì)中進(jìn)行的圖像邊緣檢測是基于8位的圖像的，其每個(gè)像素的灰度值都在[0,255]之間。特征向量可看成行向量，表示為：歸一化后的向量為：其中，;在8位的圖像中，最大的灰度值是255〔白色〕，所以在設(shè)計(jì)的實(shí)際處理過程中，歸一化結(jié)果為：由于歸一化的原因，輸出層計(jì)算的結(jié)果也是在[0,1]之間的，這個(gè)不是作為輸出圖像的像素的灰度值。在計(jì)算出輸出層的結(jié)果后，再乘以255，就是輸出圖像像素的實(shí)際灰度值。網(wǎng)絡(luò)誤差確實(shí)定在神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)之前，要定義網(wǎng)絡(luò)的誤差函數(shù)。通常使用的網(wǎng)絡(luò)誤差為均方差。即本文中對碎紙片拼接復(fù)原后質(zhì)量的評價(jià)。均差定義為：圖像邊緣檢測質(zhì)量的評價(jià)圖像質(zhì)量的定位主要采用主觀視覺的方法來確定圖像的質(zhì)量。主觀評價(jià)主要有兩種度量尺度：絕對尺度和相對尺度。表7主觀評價(jià)尺度級別絕對尺度相對尺度1很好最好的2較好高于平均水平3一般處于平均水平4較差低于平均水平5很差最差的在本文中，基于主觀評價(jià)方法的根底上，提出一種邊緣檢測圖像的質(zhì)量評價(jià)方法。其核心是利用統(tǒng)計(jì)學(xué)的樣本、方差等統(tǒng)計(jì)特性來描述邊緣檢測圖像質(zhì)量的。數(shù)學(xué)期望：方差：模型三的求解利用附件5的數(shù)據(jù)，運(yùn)用Matlab軟件求解得到拼接復(fù)原后的英文拼接復(fù)原圖〔見附錄三〕及拼接復(fù)原順序表，見下表8：表8英文〔一面〕碎片數(shù)據(jù)拼接復(fù)原順序表078b111b125a140a155a150a183a174b110a066a108a018b029a189b081b164b020a047a136b089a010b036a076b178a044a025b192a124b022a120b144a079a114a059a060b147a152a005a186b153a084b042b030a038a121a098a094b061b137b045a138a056b131b187b026b200b143b199b011b161a169b194b173b206b156a034a181b198b087a132b093a072b175a097a039b023a088b107a149b180a037b191a065b115b166b001b151b170b041a070b139b002a162b203b090a114a184b179b116b207a058a158a197a154b028b012a017b102b064b208a142a057a024a013a146a171b031a201a50a190b092b019b016b177b053b202a021b130a163a193b073b159a035a165b195a128a157a168a046a067a063b075b167a117b008b068b188a127a040a182b122a172a003b007b085b148b077a004a069a032a074b126b176a185a000b080b027a135b141a204b105a023b133a048a051b095a160b119a033b071b052a062a129b118b101a156b205a082b145a009b099a043a096b109a123a006a104a134a113a026b049b091a106b100b055b103a112a196b054b表9英文〔另一面〕碎片數(shù)據(jù)拼接復(fù)原順序表136a047b020b164a081a189a029b018a108a066b110b174a183a150b155b140b125b111a078a005b152b147b060a059b014b079b144b120a022b124a192b025a044b178b076a036b010a089b143a200a086a187a131a056a138b045b137a061a094a098b121b038b030b042a084a153b186a083b039a097b175b072a093b132a087b198a181a034b156b206a173a194a169a161b011a199a090b203a162a002b139a070a041b170a151a001a166a115a065a191b037a180b149a107b088a013b024b057b142b208b064a102a017a012b028a154a197b158b058b207b116a179a184a114b035b159b073a193a163b130b021a202b053a177a016a019a092a190a050b201b031b171a146b172b122b182a040b127b188b068a008a117a167b075a063a067b046b168b157b128b195b165a105b204a141b135a027b080a000a185b176b126a074a032b069b004b077b148a085a007a003a009a145b082a205b015a101b118a129a062b052b071a033a119b160a095b051a048b133b023a054a196a112b103b055a100a106a091b049a026a113b134b104b006b123b109b096a043b099b6模型的評價(jià)與推廣6.1模型的優(yōu)點(diǎn)〔1〕模型解決了人工拼接復(fù)原文件效率低，難以短時(shí)間完成任務(wù)的問題?！?〕本文建立的模型結(jié)合開展的計(jì)算機(jī)技術(shù)，帶來碎紙片拼接復(fù)原效率、準(zhǔn)確率的提高，對我國傳統(tǒng)文化典籍的傳承、國防事業(yè)的開展及司法管理力度的提高具有重要意義。〔3〕本文模型是對基于不規(guī)那么碎片拼接復(fù)原模型的開展，利用文字的幾何特征提出了拼接算法模型。6.2模型的缺點(diǎn)〔1〕題目要求對碎紙片拼接復(fù)原，模型執(zhí)行程序?qū)埰M(jìn)行拼接處理，程序編寫復(fù)雜度較高?！?〕蟻群算法受起止點(diǎn)位置和障礙分布的影響，環(huán)境改變時(shí)螞蟻容易陷入不可行點(diǎn)，甚至出現(xiàn)路徑迂回和死鎖。6.3模型的推廣漢字識別應(yīng)用領(lǐng)域越來越廣，在生活中越來越重要,這就對識別系統(tǒng)的資源消耗和實(shí)時(shí)性提出更高的要求。本文建立的模型可推廣應(yīng)用于漢字識別系統(tǒng)，資源消耗少(不需要硬件加速)、識別速度快，有著很好的應(yīng)用前景。7參考文獻(xiàn)[1]秦襄培，?MATLAB圖像處理寶典?，北京：電子工業(yè)出版社，2023年。[2]MarkM.Meerscheart，?數(shù)學(xué)建模方法與分析〔原書第二版〕?，北京:機(jī)械工業(yè)出版社，2005年。[3]Alex.ren,AdaBoost算法原理,，2023年9月14日。[4]趙林亮,蟻群算法原理與應(yīng)用1,,2013年9月14日。[5]王沫然，?MATLAB5.X與科學(xué)計(jì)算?，北京：清華大學(xué)出版社，2000年。[6]何仁斌，神經(jīng)網(wǎng)絡(luò)算法簡介，，2013年9月15日。[7]肖鋒，基于BP神經(jīng)網(wǎng)絡(luò)的數(shù)字圖像邊緣檢測算法的研究，，2013年9月15日。8附錄附錄一：模型一的程序：clearallnums='000.bmp';PicOut='c.jpg';P(1,:,:)=imread('F:\MATLAB7\B\附件1\000.bmp');P(2,:,:)=imread('F:\MATLAB7B\附件1\001.bmp');P(3,:,:)=imread('F:\MATLAB7B\附件1\002.bmp');P(4,:,:)=imread('F:\MATLAB7B\附件1\003.bmp');P(5,:,:)=imread('F:\MATLAB7B\附件1\004.bmp');P(6,:,:)=imread('F:\MATLAB7B\附件1\005.bmp');P(7,:,:)=imread('F:\MATLAB7B\附件1\006.bmp');P(8,:,:)=imread('F:\MATLAB7B\附件1\007.bmp');P(9,:,:)=imread('F:\MATLAB7B\附件1\008.bmp');P(10,:,:)=imread('F:\MATLAB7B\附件1\009.bmp');P(11,:,:)=imread('F:\MATLAB7B\附件1\010.bmp');P(12,:,:)=imread('F:\MATLAB7B\附件1\011.bmp');P(13,:,:)=imread('F:\MATLAB7B\附件1\012.bmp');P(14,:,:)=imread('F:\MATLAB7B\附件1\013.bmp');P(15,:,:)=imread('F:\MATLAB7B\附件1\014.bmp');P(16,:,:)=imread('F:\MATLAB7B\附件1\015.bmp');P(17,:,:)=imread('F:\MATLAB7B\附件1\016.bmp');P(18,:,:)=imread('F:\MATLAB7B\附件1\017.bmp');P(19,:,:)=imread('F:\MATLAB7B\附件1\018.bmp');s1=size(P);x=s1(1)y=s1(2)z=s1(3)%判斷那張是最后一張圖像fori=1:x-1psum(i)=0;forj=1:yif(P(i,j,z)~=255)psum(i)=psum(i)+1;endendend%將最后一張圖像移至最后fori=1:x-1if(psum(i)==0)t=P(19,:,:);P(19,:,:)=P(i,:,:);P(i,:,:)=t;endend%判斷那張是第一張圖像fori=1:x-1psum(i)=0;forj=1:yif(P(i,j,1)~=255)psum(i)=psum(i)+1;endendend%將第一張圖像移至最前面fori=1:x-1if(psum(i)==0)t=P(1,:,:);P(1,:,:)=P(i,:,:);P(i,:,:)=t;endendfork=1:x%求出第k張圖片與剩余圖片的吻合度fori=k:x-1psum(i)=0;forj=1:yif(P(k,j,z)~=255&&P(i+1,j,1)~=255)psum(i)=psum(i)+1;endendend%吻合度最高的圖片應(yīng)為下一張fori=k:x-1if(psum(i)==max(psum)&&i~=k)t=P(k+1,:,:);P(k+1,:,:)=P(i+1,:,:);P(i+1,:,:)=t;endendendQ1(:,:)=P(1,:,:);Q2(:,:)=P(2,:,:);Q3(:,:)=P(3,:,:);Q4(:,:)=P(4,:,:);Q5(:,:)=P(5,:,:);Q6(:,:)=P(6,:,:);Q7(:,:)=P(7,:,:);Q8(:,:)=P(8,:,:);Q9(:,:)=P(9,:,:);Q10(:,:)=P(10,:,:);Q11(:,:)=P(11,:,:);Q12(:,:)=P(12,:,:);Q13(:,:)=P(13,:,:);Q14(:,:)=P(14,:,:);Q15(:,:)=P(15,:,:);Q16(:,:)=P(16,:,:);Q17(:,:)=P(17,:,:);Q18(:,:)=P(18,:,:);Q19(:,:)=P(19,:,:);PiFOut='F.bmp';%合并的結(jié)果PiFData=[Q1Q2Q3Q19Q4Q5Q6Q7Q8Q9Q10Q11Q12Q13Q14Q15Q16Q17Q18];%如果是橫向拼接用這個(gè)。經(jīng)過查看結(jié)果，有一縱條錯(cuò)位，手動將其移至其應(yīng)在位置，再顯示size(PiFData)Imshow(PiFData);%imwrite(PiFData,PiFOut,'Fompression','none');%輸出%imwrite(PiFData,PiFOut,'Quality',75);%輸出圖形附件1中文碎片拼接復(fù)原圖附件2英文碎片拼接復(fù)原圖附錄二：模型二的程序：f=imread('F:\008.bmp');%讀入彩色圖像，注意不能使用灰度圖像o=f;%保存彩色原圖%f=rgb2gray(f);%將彩色圖像轉(zhuǎn)換為灰度圖像，f=im2double(f);figure();subplot(2,2,1);imshow(o);title('原圖');[m,n]=size(f);%得到圖像矩陣行數(shù)m，列數(shù)nfori=3:m-2forj=3:n-2%處理領(lǐng)域較大，所以從圖像〔3,3〕開始，在〔m-2,n-2〕結(jié)束l(i,j)=-f(i-2,j)-f(i-1,j-1)-2*f(i-1,j)-f(i-1,j+1)-f(i,j-2)-2*f(i,j-1)+16*f(i,j)-2*f(i,j+1)-f(i,j+2)-f(i+1,j-1)-2*f(i+1,j)-f(i+1,j+1)-f(i+2,j);%LoG算子endendsubplot(2,2,2);imshow(l);title('LoG算子提取圖像邊緣');[m,n]=size(l);fori=2:m-1forj=2:n-1y(i,j)=l(i-1,j-1)+l(i-1,j)+l(i-1,j+1)+l(i,j-1)+l(i,j)+l(i,j+1)+l(i+1,j-1)+l(i+1,j)+l(i+1,j+1);y(i,j)=y(i,j)/9;%LoG算子提取邊緣后，對結(jié)果進(jìn)行均值濾波以去除噪聲，為下一步hough變換提取直線作準(zhǔn)備endendsubplot(2,2,3);imshow(y);title('均值濾波器處理后')q=im2uint8(y);[m,n]=size(q);fori=1:mforj=1:nifq(i,j)>80;%設(shè)置二值化的閾值為80q(i,j)=255;%對圖像進(jìn)行二值化處理，使圖像邊緣更加突出清晰elseq(i,j)=0;endendendsubplot(2,2,4);imshow(q);title('二值化處理后');%Hough變換檢測直線，使用〔a，p〕參數(shù)空間，a∈[0,180],p∈[0,2d]a=180;%角度的值為0到180度d=round(sqrt(m^2+n^2));%圖像對角線長度為p的最大值s=zeros(a,2*d);%存儲每個(gè)(a,p)個(gè)數(shù)z=cell(a,2*d);%用元胞存儲每個(gè)被檢測的點(diǎn)的坐標(biāo)fori=1:mforj=1:n%遍歷圖像每個(gè)點(diǎn)if(q(i,j)==255)%只檢測圖像邊緣的白點(diǎn)，其余點(diǎn)不檢測fork=1:ap=round(i*cos(pi*k/180)+j*sin(pi*k/180));%對每個(gè)點(diǎn)從1到180度遍歷一遍，取得經(jīng)過該點(diǎn)的所有直線的p值〔取整〕if(p>0)%假設(shè)p大于0，那么將點(diǎn)存儲在〔d，2d〕空間s(k,d+p)=s(k,d+p)+1;%〔a，p〕相應(yīng)的累加器單元加一z{k,d+p}=[z{k,d+p},[i,j]'];%存儲點(diǎn)坐標(biāo)elseap=abs(p)+1;%假設(shè)p小于0，那么將點(diǎn)存儲在〔0，d〕空間s(k,ap)=s(k,ap)+1;%(a，p)相應(yīng)的累加器單元加一z{k,ap}=[z{k,ap},[i,j]'];%存儲點(diǎn)坐標(biāo)endendendendendfori=1:aforj=1:d*2%檢查每個(gè)累加器單元中存儲數(shù)量if(s(i,j)>70)%將提取直線的閾值設(shè)為70lp=z{i,j};%提取對應(yīng)點(diǎn)坐標(biāo)fork=1:s(i,j)%對滿足閾值條件的累加器單元中(a，p)對應(yīng)的所有點(diǎn)進(jìn)行操作o(lp(1,k),lp(2,k),1)=255;%每個(gè)點(diǎn)R分量=255，G分量=0，B分量=0o(lp(1,k),lp(2,k),2)=0;o(lp(1,k),lp(2,k),3)=0;%結(jié)果為在原圖上對滿足閾值要求的直線上的點(diǎn)賦紅色endendendendfigure,imshow(o);title('hough變換提取直線');附件3中文橫縱切碎片拼接復(fù)原圖附件4英文橫縱切拼接復(fù)原圖附錄三：模型三的程序：clearall;%讀數(shù)據(jù)str='F:\MATLAB7\work\';%nums='000.bmp';fori=0:208ifi<10nums=strcat('00',num2str(i),'a.bmp');elseifi>=10&&i<100nums=strcat('0',num2str(i),'a.bmp');elsenums=strcat(num2str(i),'a.bmp');endsrc=strcat(str,n