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

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