2023全國數(shù)學(xué)建模競賽--碎紙片拼接復(fù)原

碎紙片的拼接復(fù)原摘要目前，“碎片拼接復(fù)原〞技術(shù)在司法物證復(fù)原、歷史文物修復(fù)及社會(huì)生活各項(xiàng)領(lǐng)域扮演著重要角色，對于碎片數(shù)量特別巨大而人工又難以在短時(shí)間內(nèi)完成碎片拼接時(shí)，要找到一種高效快捷的自動(dòng)拼接方法已變得尤為重要。本文針對只有中英文的碎片拼接問題，綜合分析了從單一的縱切到縱橫切以及縱橫切雙面碎片這三個(gè)不同的情況，提出了碎片拼接復(fù)原的解決方案.在問題一中，對于僅有“縱切〞且數(shù)量相對較少的碎紙片，我們基于邊緣去噪和采用構(gòu)建碎紙圖片的左右邊緣二值矩陣提取相似度分析的方法，再通過兩張圖片左右相似度匹配排序，得到附件1和附件2中的碎紙排序〔見表2和表3〕，并運(yùn)用Matlab的圖像處理工具箱，按排列順序?qū)胨榧埰玫较鄳?yīng)拼接結(jié)果〔見附錄附件一〕.在問題二中，由于碎紙片數(shù)量相對較多，同時(shí)存在橫切和縱切的情況，在問題一的根底上增加了碎紙片的上下邊緣相似度匹配。在進(jìn)行人工干預(yù)，找到第一張起始碎紙片作為匹配起點(diǎn)后，我們基于索貝爾算子的原理，對碎紙片灰度值進(jìn)行邊緣相似度的旋轉(zhuǎn)檢測和比較匹配，最后進(jìn)行二叉樹搜索排序〔見表4和表5〕。對附件3和4的碎紙圖片拼接出的結(jié)果詳見附錄中的附件二.在問題三中，由于碎紙片是兩面的并且碎紙片數(shù)量更多，假設(shè)采用第二問的求解方案那么加大了求解難度同時(shí)也存在較大誤差。因此，我們基于蟻群算法〔ACA〕的SIFT特征點(diǎn)匹配原理來求解。先提取碎紙圖片特征點(diǎn)，然后基于蟻群算法的最優(yōu)化快速比對匹配，最后基于ACA的搜索排序?qū)λ榧埰唇?。Matlab編程所求得的排序結(jié)果詳見表6和表7，附件5中的碎紙片拼接復(fù)原結(jié)果見附錄中的附件三.在問題的解決中，我們得出結(jié)論:碎紙圖片導(dǎo)入量越小，圖片匹配出的效果越佳，在相似度的匹配上，出現(xiàn)的誤差減小,最后拼出的圖像效果好，人工干預(yù)量也相對小。本建?？紤]到了圖片噪聲對圖片拼接時(shí)的影響，選擇了去噪效果較好的鄰域平均法對圖片進(jìn)行處理。但是，為了解題方便，我們忽略了碎紙機(jī)切紙時(shí)碎紙片可能產(chǎn)生的邊界遺失破損。在這里我們的改進(jìn)是，對于邊界遺失圖像碎片的修復(fù)，根據(jù)復(fù)原后的整體形狀，可以根據(jù)線連續(xù)性來擬合此類線段,從而得到較為完整的圖像.關(guān)鍵詞：碎紙拼接、腐蝕算法、蟻群算法、圖像特征匹配、鄰域平均法一、問題的重述破碎文件的拼接在司法物證復(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ā)碎紙片的自動(dòng)拼接技術(shù)，以提高拼接復(fù)原效率?，F(xiàn)解決如下問題：1.對于給定的來自同一頁印刷文字文件的碎紙機(jī)破碎紙片〔僅縱切〕，建立碎紙片拼接復(fù)原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，請寫出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。復(fù)原結(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á)要求同上.3.上述所給碎片數(shù)據(jù)均為單面打印文件，從現(xiàn)實(shí)情形出發(fā)，還可能有雙面打印文件的碎紙片拼接復(fù)原問題需要解決。附件5給出的是一頁英文印刷文字雙面打印文件的碎片數(shù)據(jù)。請嘗試設(shè)計(jì)相應(yīng)的碎紙片拼接復(fù)原模型與算法，并就附件5的碎片數(shù)據(jù)給出拼接復(fù)原結(jié)果，結(jié)果表達(dá)要求同上.二、問題的分析此題是一個(gè)關(guān)于碎紙片拼接復(fù)原的問題，針對題目的要求，我們對于“碎紙片拼接復(fù)原〞等一系列問題的處理特點(diǎn)和處理方案，就每個(gè)問題做除了以下的具體分析：2．1針對問題1的分析結(jié)合給出的碎紙機(jī)碎片情況，分別是一頁中文和英文文件的碎片數(shù)據(jù)，也就是說，在每張碎片中都會(huì)出現(xiàn)相當(dāng)多的完整或不完整的漢字〔英文〕或者結(jié)構(gòu)，要解決把縱切的碎紙片拼接復(fù)原的問題：首先，利用MATLAB編程建立圖片的二值矩陣。鑒于紙片的大小相同，并且只有黑白兩色，通過觀察附件一的碎片，每張碎片最左端或者最右端不是全空，這些碎片就可以全部轉(zhuǎn)化為二值圖，0代表白色，1代表黑色。其次，采用鄰域平均法對圖像進(jìn)行邊緣去噪，進(jìn)一步利用分割最正確閾值的迭帶算法來到達(dá)消除或減少噪聲影響的效果。最后，比較圖像左右邊緣的相似情況,從而得出兩個(gè)邊緣圖像的相似度,以此來度量兩個(gè)圖像能否匹配。復(fù)原過程中需要人工干預(yù)，將依順序顯示的未拼接碎片，采用半自動(dòng)拼接，即人工選擇碎片并拼接到計(jì)算機(jī)屏幕上。將序號(hào)排列好后；再通過基于MATLAB編程將19張圖片分別排好序通過調(diào)用imshow()函數(shù)合成圖片，這樣就能得到最終求解結(jié)果.2．2針對問題2的分析求解要求中我們可以知道該問題在第一問的根底上增加了“橫切〞碎片，出現(xiàn)的紙張既有橫切又有縱切。解決方案與第一問有所不同；增加了“橫切〞過后，在第一問的左右相似度比較之上增加了上下邊緣的相似度比較和匹配。但考慮到求解精度我們采用灰度值〔0~255〕求解的圖片處理方法；同樣基于MATLAB編程對附件3和附件4中的碎片分別進(jìn)行灰度處理得到圖片矩陣的灰度值；并采用基于Sobel的算法對個(gè)碎片進(jìn)行四個(gè)邊的邊緣化處理，提取邊緣特征，并對其進(jìn)行邊緣相似度的計(jì)算。同時(shí)對邊緣化處理后的灰度值進(jìn)行聚類分析確定一個(gè)閥值，也就是確定一個(gè)誤差值。只考慮切縫處并對其相似度一致的縫合。又由于該問中需要拼接的圖片數(shù)量眾多，我們采用基于二叉樹的搜索排序算法對相似度矩陣排序并得到該相似度矩陣所對應(yīng)的圖片序列號(hào)數(shù)組，該排列的序列號(hào)數(shù)組即為碎片的組合方式；最后采用MATLAB循環(huán)調(diào)用序列號(hào)數(shù)組對應(yīng)的碎片名拼接出所求結(jié)果到達(dá)解決該問題的目的.2.3針對問題3的分析對于問題3其實(shí)是在問題二的根底上在增加了正反面的拼接。另外通過分析題目中告訴了的類容可以發(fā)現(xiàn)附件中同一個(gè)序號(hào)表示是一張碎紙圖片，a和b表示同一張碎片的了兩面，但并不確定a和b的正反。這樣同第二問中的解決思路相似，但由于問題三中對應(yīng)的附件5的碎圖片數(shù)據(jù)量過大如假設(shè)采用第二問的求解方式也并不理想所以我們采用基于蟻群算法〔ACA〕的SIFT特征點(diǎn)圖像碎片拼接方法。針對附件五中的圖片基于MATLAB采用所設(shè)計(jì)的算法提取其特征點(diǎn)并建立特征點(diǎn)匹配矩陣。再利用這些特征點(diǎn)匹配矩陣根據(jù)理論建模設(shè)計(jì)基于MATLAB的算法求解出順序排列的局部序列號(hào)和誤差節(jié)點(diǎn)。將其中求得的序列號(hào)對應(yīng)的碎紙圖片導(dǎo)入MATLAB中求解出拼接圖像，最后通過人工干預(yù)的方式補(bǔ)全各個(gè)殘缺節(jié)點(diǎn)的碎片得到完整的紙片圖像已到達(dá)拼接出碎紙片的正反兩面的目的.三、模型假設(shè)1、假設(shè)未碎紙張的文字行方向沿水平方向，字與字之間有間隔且字寬度與高度比值1/3；假設(shè)碎片模型為理想模型，碎片外表光滑平整無磨損且厚度為零；假設(shè)在切割過程中除邊界外，其他切割線都切割文字；假設(shè)每張碎紙片的大小一致；假設(shè)碎紙機(jī)切的紙片無損壞；假設(shè)碎圖片中的文字符字體格式相同，英文字符字體格式相同.四、符號(hào)的定義圖像平面上的一系列平均噪聲點(diǎn)，第個(gè)二值矩陣圖像的分割閥值，即灰度值閥值，灰度均值，待測邊緣圖像邊緣點(diǎn)經(jīng)橫〔縱向〕邊緣檢測的圖像梯度方向第i像素和它的K連通像素邊緣相似度不同中心像素點(diǎn)的協(xié)議變量，為啟發(fā)式因子的相對重要程度為信息素的相對重要程度為信息素蒸發(fā)系數(shù)表示信息素的持久性系數(shù)為窗口信息素含量五、模型的建立及求解5.1問題一模型的建立及求解算法的流程圖：載入圖像建立圖片的二值矩陣載入圖像建立圖片的二值矩陣采用鄰域平均法進(jìn)行邊緣去噪比較圖像左右邊緣的相似情況運(yùn)用腐蝕算法輪廓提取方法來消除圖像的左右邊界的作用圖15.1.1、把圖像轉(zhuǎn)化為二值矩陣二值圖像是指每個(gè)像素不是黑就是白，其灰度值沒有中間過渡的圖像。二值圖像一般用來描述文字或者圖形，其優(yōu)點(diǎn)是占用空間少，人們經(jīng)常用黑白、B&W、單色圖像表示二值圖像，但是也可以用來表示每個(gè)像素只有一個(gè)采樣值的任何圖像，例如灰度圖像等.因此針對問題一，我們先將對應(yīng)的碎紙圖片用Matlab調(diào)用im2bw函數(shù)對導(dǎo)入的碎紙圖片求解其二值矩陣.5.1.2、圖像邊緣去噪——鄰域平均法鄰域平均法是一種利用Box模板對圖像進(jìn)行模板操作〔卷積操作〕的圖像平滑方法最簡單的平滑濾波是將原圖中一個(gè)像素的灰度值和它周圍鄰近像素的灰度值相加，然后將求得的平均值作為新圖中該像素的灰度值。它采用模板計(jì)算的思想，模板操作實(shí)現(xiàn)了一種鄰域運(yùn)算，即某個(gè)像素點(diǎn)的結(jié)果不僅與本像素灰度有關(guān)，而且與其鄰域點(diǎn)的像素值有關(guān).將附件1或2中已經(jīng)進(jìn)行二值化的碎紙片矩陣驚醒邊緣去噪處理，消弱噪聲點(diǎn)起到平滑作用，減小相似度誤差，增大匹配準(zhǔn)確度.設(shè)為給定的含有噪聲的圖像，經(jīng)過鄰域平均處理后的圖像為，那么鄰域平均法也可以用數(shù)學(xué)公式表達(dá)：(1)式中：，；是以為中心的鄰域的集合，M是S內(nèi)的點(diǎn)數(shù).鄰域平均法的思想是通過一點(diǎn)和鄰域內(nèi)的像素點(diǎn)求平均來去除突變的像素點(diǎn)，從而濾掉一定的噪聲，其主要在實(shí)際應(yīng)用中，也可以根據(jù)不同的需要選擇使用不同的模板尺寸，如3×3、5×5、7×7、9×9等。鄰域平均處理方法是以圖像模糊為代價(jià)來減小噪聲的，且模板尺寸越大，噪聲減小的效果越顯著。如果是噪聲點(diǎn)，其鄰近像素灰度與之相差很大，采用鄰域平均法就是用鄰近像素的平均值來代替它，這樣能明顯消弱噪聲點(diǎn)，使鄰域中灰度接近均勻，起到平滑灰度的作用.從理論上看:a、要改變均值濾波的濾波能力，就要改變模板的大小，模板越大去噪能力越強(qiáng)，反之越弱；b、由于是在整幅圖上以取局部灰度平均的方法來淡化噪聲，所以不可防止的會(huì)使原有圖像的清晰度、比照度下降，會(huì)損失原有圖像的細(xì)節(jié)，模板越大損失的越多；c、對整幅圖像用同一個(gè)模板，不能適應(yīng)局部具體情況，會(huì)出現(xiàn)有濾波不均勻的情況.5.1.3、分割閥值的迭代分析法閥值分割方法是把圖像的灰度分成不同的等級(jí)，然后用設(shè)置灰度門限的方法確定欲分割物體的邊界。當(dāng)用閥值來分割口標(biāo)與背景時(shí)，如果某一灰度值g是某圖像的分割閥值，即小于g的灰度點(diǎn)將構(gòu)成口標(biāo)(不妨如此假設(shè))，而大于g的灰度點(diǎn)就構(gòu)成背景一般而言，如果灰度值g可以作為圖像的一個(gè)閥值，那么它應(yīng)該使按這個(gè)閥值劃分口標(biāo)和背景的錯(cuò)誤分割的圖像像素點(diǎn)數(shù)為最小.如果前景物體的內(nèi)部具有均勻一致的灰度值，并分布在另一個(gè)灰度值的均勻背景上，那么圖像的灰度直方圖應(yīng)具有明顯的雙峰?？墒窃谠S多情況下，噪聲的干擾使峰谷的位置難以判定或者結(jié)果不穩(wěn)定本文采用迭代算法，有效地消除或減少噪聲對灰度門限值g的影響.設(shè)有一幅混入噪聲的圖像g(x),力是由原始圖像f(x,y)和e(x,y)疊加而成的。即:〔2〕這里假設(shè)各點(diǎn)的噪聲是互不相關(guān)的，且具有零均值，標(biāo)準(zhǔn)差為。通過閥值分割將圖像分割為兩局部，由于噪聲是隨機(jī)作用于圖像的像素點(diǎn)上，那么可以認(rèn)為在分割出口標(biāo)和背景圖像上噪聲干擾仍為，即:〔3〕〔4〕在迭代算法中，需要對分割出的圖像分別求其灰度均值，那么:〔5〕〔6〕上式說明，隨著迭代次數(shù)的增加，平均灰度值將趨向于真值。因此，用迭代算法求得的最正確閥值不受噪聲干擾的影響根據(jù)上述分析，針對該問題的迭代算法描述如下.〔1〕首先選擇一個(gè)近似閥值作為估訓(xùn)一值的初始值，然后進(jìn)行分割，產(chǎn)生子圖像，并根據(jù)子圖像的特性來選擇新的閥值，再用新的閥值分割圖像，經(jīng)過幾次循環(huán)，使錯(cuò)誤分割的圖像像素點(diǎn)降到最少。這樣做的效果好于用初始閥值直接分割圖像的效果，閥值的改進(jìn)策略是迭代算法的關(guān)鍵。算法步驟如下:選擇一個(gè)初始閥值的估算值〔7〕式中，，分別表示圖像中的最小和最大灰度值.〔2〕利用閥值把圖像分割成兩組，和，其中：〔8〕〔9〕(3)計(jì)算區(qū)域和的灰度值均值，，其中：〔10〕〔11〕式中，f(x,y)是圖像上(i，j)點(diǎn)的灰度值，N(i,j)是(i,j)點(diǎn)的權(quán)重系數(shù)，一般N(i,j)=1.0?！?〕選擇新的閾值〔12〕〔5〕如果，那么結(jié)束,否那么,轉(zhuǎn)步驟(2)。經(jīng)過圖像分割處理后,有效減少了噪聲對圖像的干擾范圍,并使圖像的邊緣鄰域像素點(diǎn)離噪聲干擾的敏感區(qū),從而提高了圖像邊緣檢測抗干擾能力.5.1.4、腐蝕算法輪廓提取方法經(jīng)過上述三求解階段過后，圖像輪廓提取算法就變得非常簡單?；诙祱D像輪廓提取的算法就是掏空內(nèi)部點(diǎn),如果原圖中有一點(diǎn)為黑,且它的8個(gè)相領(lǐng)點(diǎn)都是黑色時(shí),判定該點(diǎn)是原圖像的內(nèi)部點(diǎn),那么將該點(diǎn)刪除。最后,經(jīng)過這樣的算法處緣檢測[4,5]。在數(shù)學(xué)形態(tài)學(xué)運(yùn)算中,腐蝕具有消除物體邊界點(diǎn)的作用。結(jié)構(gòu)元素取3×3的黑點(diǎn)塊,腐蝕將使物體的邊界沿周邊減少一個(gè)像素。那么邊緣檢測實(shí)際上相當(dāng)于用3×3塊的9個(gè)點(diǎn)結(jié)構(gòu)元素對原圖進(jìn)行腐蝕,再用原圖像減去腐蝕的圖像。令X為圖像,B為結(jié)構(gòu)元素,BZ表示結(jié)構(gòu)元素B平移Z后的結(jié)果,代表結(jié)構(gòu)元素關(guān)于原點(diǎn)的對稱集合。其數(shù)學(xué)表示如下:〔13〕那么腐蝕的運(yùn)算定義:(14)式中,的結(jié)構(gòu)元素;ED(X):代表圖像X的邊界.該方法檢測到的物體邊緣寬度僅為一個(gè)像素,因此具有較高的定位精度。同時(shí),二值化處理后的圖像具有完整的輪廓,所以輪廓提取檢測到的邊緣具有連續(xù)性.5.1.5、邊緣相似度邊緣相似度的根本思想是用標(biāo)準(zhǔn)的無噪圖像產(chǎn)生出標(biāo)準(zhǔn)的邊緣圖像，設(shè)為，將含噪圖像用噪聲抑制算法濾波處理后產(chǎn)生待測邊緣圖像，設(shè)為,比較兩個(gè)邊緣圖像上各個(gè)邊緣點(diǎn)的相似情況，從而得出兩個(gè)邊緣圖像的相似度，以此來度量濾波算法的邊緣保持能力.對于上的一個(gè)邊緣點(diǎn)，其邊緣相似度定義為：〔15〕由上式可見，單點(diǎn)邊緣相似度反映的是檢測邊緣點(diǎn)與對應(yīng)的原標(biāo)準(zhǔn)邊緣點(diǎn)之間的位置偏差:如果完全重合，那么為最大相似度1;如果相差k個(gè)像素點(diǎn)，那么其下降為，如果是一個(gè)誤檢點(diǎn)包括錯(cuò)檢點(diǎn)和漏檢點(diǎn)，即原來不是邊緣點(diǎn)，但檢測成了一個(gè)邊緣點(diǎn)；或者原來有邊緣，但是沒檢測出來，那么為-1.整幅圖像的邊緣相似度那么定義為所有邊緣點(diǎn)相似度的平均公式：〔16〕式中M為中的邊緣點(diǎn)數(shù).5.1.6、基于計(jì)算機(jī)MATLAB的模型求解〔1〕計(jì)算機(jī)編程求解得到圖片的二值矩陣該問題所見模型基于計(jì)算機(jī)仿真的MATLAB求解碎紙片的二值矩陣可以得到一個(gè)的0、1矩陣列.以對附件一的縱切碎紙片拼接為例,羅列出前6張碎紙圖片求得的二值矩陣如下：、表1:二值矩陣000.bmp001.bmp002.bmp000011000110011100111101100101010000001011010100101000101000100010110111003.bmp004.bmp005.bmp010010110100111101011001000100101011010100101000101000001010011111010101〔2〕相似度匹配結(jié)果通過相似度匹配分析可以得到每張碎紙圖片右邊緣與另一張碎紙圖片左邊緣的相似度匹配分析。假設(shè)高于90%那么匹配吻合。以附件一為例：先人工干預(yù)確定第一張圖片“008.bmp〞為起始點(diǎn)，它的二值矩陣右邊與“014.bmp〞相似度匹配結(jié)果最高.〔3〕求得的排序結(jié)果表2：對于附件一基于相似度分析匹配求得的碎紙片自動(dòng)排序8141215310216145913181171706表3：對于附件二基于相似度分析匹配求得的碎紙片自動(dòng)排序47381619121621014119131518175〔說明：“8〞表示第九張圖片“008.bmp〞排在第一列；附件1和2碎紙圖片的拼接結(jié)果詳見附件〕5.2問題二模型建立及求解算法流程圖：SobelSobel的算法對個(gè)碎片進(jìn)行四個(gè)邊的邊緣化處理對邊緣化處理后的圖像進(jìn)行聚類分析確定閥值二叉樹的搜索排序算法對圖片排序二元相似性度量算法對圖像進(jìn)行分析導(dǎo)入圖像圖2在實(shí)際圖像邊緣檢測問題中，圖像的邊緣作為圖像的一種根本特征，經(jīng)常被應(yīng)用到較高層次的圖像應(yīng)用中去。圖像邊緣是圖像最根本的特征之一，往往攜帶著一幅圖像的大局部信息。而邊緣存在于圖像的不規(guī)那么結(jié)構(gòu)和不平穩(wěn)現(xiàn)象中，也即存在于信號(hào)的突變點(diǎn)處，這些點(diǎn)給出了圖像輪廓的位置，這些輪廓常常是我們在圖像邊緣檢測時(shí)所需要的非常重要的一些特征條件，這就需要我們對一幅圖像檢測并提取出它的邊緣.5.2.1、Sobeloperator索貝爾算子〔Sobeloperator〕是圖像處理中的算子之一，主要用作邊緣檢測。在技術(shù)上，它是一離散性差分算子，用來運(yùn)算圖像亮度函數(shù)的梯度之近似值。在圖像的任何一點(diǎn)使用此算子，將會(huì)產(chǎn)生對應(yīng)的梯度矢量或是其法矢量.該算子包含兩組3x3的矩陣，分別為橫向及縱向，將之與圖像作平面卷積，即可分別得出橫向及縱向的亮度差分近似值。如果以A代表原始圖像，Gx及Gy分別代表經(jīng)橫向及縱向邊緣檢測的圖像，其公式如下:圖像的每一個(gè)像素的橫向及縱向梯度近似值可用以下的公式結(jié)合，來計(jì)算梯度的大小。(17)然后可用以下公式計(jì)算梯度方向(18)在以上例子中，如果以上的角度Θ等于零，即代表圖像該處擁有縱向邊緣，左方較右方暗。在邊沿檢測中，常用的一種模板是Sobel算子。Sobel算子有兩個(gè)，一個(gè)是檢測水平邊沿的；另一個(gè)是檢測垂直平邊沿的。Sobel算子對于象素的位置的影響做了加權(quán)，因此效果更好。Sobel算子另一種形式是各向同性Sobel(IsotropicSobel)算子，也有兩個(gè)，一個(gè)是檢測水平邊沿的，另一個(gè)是檢測垂直平邊沿的。各向同性Sobel算子和普通Sobel算子相比，它的位置加權(quán)系數(shù)更為準(zhǔn)確，在檢測不同方向的邊沿時(shí)梯度的幅度一致.5.2.2、調(diào)整簇閥值的加速聚類方法調(diào)整簇閥值的加速聚類方法的根本思想是:設(shè)置簇調(diào)整閥值,在每次迭代完成后,只有簇調(diào)整量大于閥值的簇才參與下一次迭代調(diào)整。簇調(diào)整閥值可以設(shè)置為簇中心遷移的調(diào)整閥值和簇中樣本數(shù)目調(diào)整閥值二種情況:(1)記某一簇在第1次迭代后聚類中心與初始的簇中心之間的距離為,在第次迭代后新的簇中心與原簇中心之間的距離,如果,那么以為代表的簇不再參與下輪迭代調(diào)整,否那么,繼續(xù)參與迭代調(diào)整.(2)對于任一個(gè)簇,假設(shè)樣本數(shù)目,在每次迭代完成后,該簇中樣本調(diào)整個(gè)數(shù)為(增加或減少的數(shù)目絕對值),如果滿足,那么,該簇將不再參與下一輪迭代調(diào)整。針對航運(yùn)信息數(shù)據(jù),通過屢次Monte-Carlo仿真實(shí)驗(yàn)測試,在該算法中,通常設(shè)置閥值在0～0.1之間,閥值在0～0.05之間。閥值可以只設(shè)置任意一個(gè),也可以兩個(gè)都設(shè)置。但是,值得注意的是,如果閥值設(shè)置過大,會(huì)嚴(yán)重影響聚類精度,因此,要合理地設(shè)置閥值的大小。這樣,有了調(diào)整閥值條件后,參與迭代的樣本數(shù)目大大減少,從而可以節(jié)約大量的運(yùn)算時(shí)間.算法的根本流程如下:輸入:聚類個(gè)數(shù)k,數(shù)據(jù)集X,閥值和輸出:k個(gè)簇集V和簇中心C：初始化簇中心;可以使用傳統(tǒng)的k-means隨機(jī)初始化法,也可以采用k-means初始化法。：設(shè)最終簇集和中心都為空集V=和C=,迭代次數(shù)t=1。計(jì)算每個(gè)對象與中心的距離,按最小距離原那么將數(shù)據(jù)劃分到相應(yīng)的簇,形成k個(gè)簇,并記錄各簇中樣本個(gè)數(shù),設(shè)置初始的調(diào)整標(biāo)號(hào).：重新計(jì)算每個(gè)簇中心和各個(gè)簇中心移動(dòng)的初始位移,其中,表示簇中樣本的個(gè)數(shù).:計(jì)算標(biāo)號(hào)的簇中每個(gè)樣本對象與參與調(diào)整簇的中心的距離,按最小距離原那么將數(shù)據(jù)劃分到相應(yīng)的簇,形成k個(gè)新簇,并記錄各簇中樣本個(gè)數(shù),求得調(diào)整的樣本個(gè)數(shù).：重新計(jì)算參與調(diào)整簇中心和簇中心移動(dòng)的位移.：如果簇的中心滿足或者,那么,將簇中的調(diào)整標(biāo)號(hào)設(shè)置為0,即=0,并將和添加到最終簇及簇中心集合中,即和.：如果形成了包含k個(gè)簇的集合,即V=k,那么,終止迭代,算法結(jié)束,否那么,迭代次數(shù)t=t+1,跳轉(zhuǎn)到步驟4.聚類結(jié)果的評價(jià)主要兩個(gè)方面:聚類精度和算法時(shí)間復(fù)雜度.算法性能分析實(shí)驗(yàn)如下:(1)聚類精度分析傳統(tǒng)的k-means算法,所求的解往往是局部最優(yōu)解,使用k-means算法在一定程度上減少了局部最優(yōu)可能性,但從聚類過程看,求的解也往往是局部最優(yōu)解,本文提出的調(diào)整簇閥值的加速算法,由于采用了近似的k-means算法,導(dǎo)致該算法只能找到局部近似解。適當(dāng)?shù)卦O(shè)置閥值,也能得到和k-means算法相當(dāng)?shù)木垲惥?(2)時(shí)間復(fù)雜度分析傳統(tǒng)k-means算法的時(shí)間復(fù)雜度為,其中,n為樣本個(gè)數(shù),k為簇?cái)?shù)目,d為數(shù)據(jù)維數(shù),t為迭代次數(shù).5.2.3、相似度計(jì)算二元相似性度量算法分析傳統(tǒng)的度量是采用基于兩幅圖像對應(yīng)像素位置的位與位匹配的方法。但是在被動(dòng)篡改檢測中,是沒有可以用來比對的原始圖像的。所以,在基于二元相似性度量的圖像被動(dòng)篡改檢測中,我們考慮比較圖像位平面的二元紋理統(tǒng)計(jì)特征.首先,我們用表示第i像素和它的K連通像素(或K鄰居像素,K=4或K=8)的順序關(guān)系。在本文中,我們選擇K=4,表示選擇N,W,S,E(上!下!左!右)四個(gè)連通像素,i表示圖像所有像素點(diǎn),假定圖像的大小是M和N。我們定義模板函數(shù)如式(6)所示：〔19〕這樣，對于一個(gè)中間像素點(diǎn)i，它與其四連通像素的關(guān)系可以表示為式：〔20〕對于中心像素，我們定義它的協(xié)議變量(agreement)為下式：〔21〕其中，是克羅內(nèi)克函數(shù)(Kroneckerdeltafunction)，其定義如式：〔22〕因此對于,有：〔23〕很顯然，函數(shù)表示中心像素點(diǎn)和其連通像素點(diǎn)之間的轉(zhuǎn)換關(guān)系。對于中心像素點(diǎn)，它與其四連通像素的關(guān)系可以重新表示為式：累積一協(xié)議量(accumulatedagreements)的定義如下所示:，，這四個(gè)變量是一幅二進(jìn)制圖像的一階伴隨變量.5.2.4、二叉樹搜索排列二叉樹搜索排序定義：二叉樹的定義：空或有一個(gè)根，根有左子樹、右子樹；而左右子樹本身又是二叉樹。如下列圖：B圖3：BLCLCDFEDFE1、二叉樹的性質(zhì)：性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)；性質(zhì)2：高度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)；性質(zhì)3：二叉樹的葉子結(jié)點(diǎn)數(shù)n0等于度為2的結(jié)點(diǎn)數(shù)n2+1；性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹高度為log2n+1；性質(zhì)5：對一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹按照從第一層〔根所在的層次〕到最后一層，并且每一層都按照從左到右的次序進(jìn)行編號(hào)。根結(jié)點(diǎn)的編號(hào)為1，最后一個(gè)結(jié)點(diǎn)的編號(hào)為n.1：對任何一個(gè)編號(hào)為i的結(jié)點(diǎn)而言，它的左兒子的編號(hào)為2i(假設(shè)2i<=n),而右兒子的編號(hào)為2i+1(假設(shè)2i+1<=n).2：對任何一個(gè)編號(hào)為j的結(jié)點(diǎn)而言，它的父親結(jié)點(diǎn)的的編號(hào)為j/2。根結(jié)點(diǎn)無父結(jié)點(diǎn).2、二叉樹的遍歷:設(shè)N代表根節(jié)點(diǎn),L代表左子樹,R代表右子樹。a.前序〔或先序〕：如果二叉樹為空，那么操作為空：否那么訪問根結(jié)點(diǎn)；前序遍歷左子樹；前序遍歷右子樹。記為：NLRb.中序：如果二叉樹為空，那么操作為空：否那么中序遍歷左子樹；訪問根結(jié)點(diǎn)；中序遍歷右子樹。記為：LNR.c.后序：如果二叉樹為空，那么操作為空：否那么后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點(diǎn)。記為：LRN.B圖4：BCLCLDFBEDFBEXW3、二叉樹的作用:XW1查找當(dāng)前第K大元素；2查詢某元素在當(dāng)前所有元素中的排名.〔24〕其中，是克羅內(nèi)克函數(shù)(Kroneckerdeltafunction)，其定義如式：〔25〕因此對于,有：很顯然，函數(shù)表示中心像素點(diǎn)和其連通像素點(diǎn)之間的轉(zhuǎn)換關(guān)系.對于中心像素點(diǎn)，它與其四連通像素的關(guān)系可以重新表示為式：累積一協(xié)議量(accumulatedagreements)的定義如式所示，，這四個(gè)變量是一幅二進(jìn)制圖像的一階伴隨變量.5.2.5、構(gòu)建模型的計(jì)算機(jī)仿真求解通過基于MATLAB編程的算法求解分析我們得到了如下表格的碎紙圖片序號(hào)排列矩陣：表4:附件三的碎紙片排列矩陣0123456104905406514318600220610190780670690993168100076062142030403814804616102403550711560831322000176014128003159082199709403408418309004781250131821091970169029064111201005092100072081381581260681108914616215411404078910111205719217811819009516209613107906311604102314719105017908118912210313019308003302219801513313501207316020316912104212414407711218411018706610615018004803707505504417504514700013705315120715514018510813141516171819011022129028091188141163072006177020052036120086195026001087018088167025008009105074170205085152165027060134039031051017115176149097136164127058043021170157181204139145206010104098172171059056093153070166032196117004101113194119123表5：對于附件四的碎紙片排列矩陣0123456119107501115419018422011481701961980943086051107029040158401919409314108812151591390011290632386020041108116136073720802100704906111980700840600140681749132181095069167163101710420662050101571108107712820013105278910111213002104180064106004149113164078103091080101186098024117150005059126105155114176182151153053038123120175085036207135015076043199033142168062169054192137195008047172156096166188111144206003130074145083134055018056125140193087089048072141516171819032204065039067147026100006017028146058092030037046127022057202071165082050160187097203031045173079161179143133118189162197112023099122090185109034013110025027178035016009183152044012177124000102115〔附件3和4的碎紙片拼接結(jié)果詳見附件〕5.3、問題三模型的建立及求解5.3.1、蟻群算法實(shí)現(xiàn)圖像最優(yōu)化比對搜索蟻群算法〔ACA)是受到螞蟻群體尋找食物行為的啟發(fā)而提出的一種基于蟻群的模擬進(jìn)化算法。一般來講群體隨機(jī)搜索算法常用于解決特定的組合優(yōu)化問題。自然界中螞蟻搜索食物過程是一個(gè)不斷聚類的過程，食物就是聚類中心，其主要思想是:將每個(gè)數(shù)據(jù)看作一個(gè)螞蟻，螞蟻分別聚集到個(gè)聚類中心，到的距離為，采用歐式距離計(jì)算:〔26〕其中:m表示每個(gè)數(shù)據(jù)特征的維數(shù);P加權(quán)因子，根據(jù)像素分量對信息測度影響程度設(shè)定。假設(shè)算法中的螞蟻具有一定的記憶能力，能根據(jù)2幅待拼接圖像上互信息濃度選擇轉(zhuǎn)移方向，從而引導(dǎo)螞蟻向互信息測度最大值的方向移動(dòng).蟻群算法處理的問題一般具有如下特點(diǎn):①搜索空間是離散的;②有一組有限的約束條件;③有一個(gè)代價(jià)函數(shù)，為搜索算法生成的解計(jì)算對應(yīng)的代價(jià)，解的每一局部都會(huì)對解的代價(jià)產(chǎn)生影響;④有一個(gè)有限的節(jié)點(diǎn)集合，用于構(gòu)建解;⑤有一個(gè)有限的節(jié)點(diǎn)間的可能轉(zhuǎn)移的集合;⑥有一個(gè)節(jié)點(diǎn)序列的有限集合，用于表示所有的有效組合，來定義完整的搜索空間，組合的有效性、可行性由約束條件決定.可以將圖像拼接過程中圖像A中的窗口在B搜索迭代的過程看成是“只螞蟻的城市模型〞，從而使得螞蟻可以在這個(gè)模型圖上進(jìn)行爬行，并且保證了螞蟻爬行所獲得的每個(gè)哈密頓路都對應(yīng)一個(gè)互信量最大的組合.蟻群算法的參數(shù)進(jìn)行如下設(shè)置:為信息素的相對重要程度;為啟發(fā)式因子的相對重要程度;為信息素蒸發(fā)系數(shù)，表示信息素的持久性系數(shù)，且〔27〕其中:為窗口信息素含量;為啟發(fā)函數(shù);N為循環(huán)遍歷次數(shù).5.3.2、基于ACA搜索的碎紙片圖像SIFT特征點(diǎn)匹配基于圖像特征的方法，首先要對待配準(zhǔn)的兩幅圖像進(jìn)行處理，提取滿足特定應(yīng)用要求的特征集，然后將這兩組特征集進(jìn)行匹配對應(yīng)，生成一組對應(yīng)特征對集，最后利用這組特征對之間的對應(yīng)關(guān)系估計(jì)出全局變換參數(shù)?；趫D像特征的方法，在特征提取后得到的特征點(diǎn)的數(shù)量將會(huì)大大減少，因此可以提高配準(zhǔn)的速度，但其配準(zhǔn)的效果很大程度上還取決于特征點(diǎn)的提取精度以及特征點(diǎn)匹配的準(zhǔn)確度。基于圖像特征的配準(zhǔn)方法主要困難在于如何提取和選擇魯棒的特征，以及如何對特征進(jìn)行匹配，其中要克服，由于圖像噪聲和場景中出現(xiàn)遮擋現(xiàn)象所引起的誤匹配的問題。常用的圖像匹配特征有點(diǎn)、直線、曲線等.目前大多數(shù)文獻(xiàn)都是采用點(diǎn)特征進(jìn)行圖像之間的配準(zhǔn)，從而實(shí)現(xiàn)圖像的拼接?；趫D像特征配準(zhǔn)的方法的主要優(yōu)點(diǎn)是它提取了圖像的顯著特征，大大壓縮了圖像的信息量，計(jì)算量小，速度較快，而且它對圖像灰度的變化具有魯棒性。但另一方面，正是由于只有一小局部的圖像灰度信息被使用了，所以這種方法對特征提取和特征匹配的錯(cuò)誤更敏感，需要可靠的特征提取和特征一致性.圖5：基于特征點(diǎn)的圖像拼接流程圖該問題總結(jié)的算法的搜索過程可以理解為:在2幅或多幅圖上利用蟻群作為搜索窗口，通過互信息測度的方式代替搜索出的2幅圖像之間在目標(biāo)、背景、邊界和噪聲等內(nèi)容中的特征向量的過程。依據(jù)互信息量最大作為搜索并且不斷改變的方向，最終朝著使互信息量最大的方向搜索，從而確定出2幅圖像之間存在的匹配區(qū)域.碎片全局拼接如果有兩個(gè)碎片證明是匹配的，那么把匹配之后的碎片組成一個(gè)新的人工碎片，重復(fù)以上的步驟，直到所有的碎片拼接完畢。用這種方式，拼接的過程形成了島嶼狀。計(jì)算每個(gè)碎片的輪廓長度。假設(shè)M是旋轉(zhuǎn)鏈的輪廓像素的總數(shù)，N是固定鏈的輪廓像素的總數(shù)。那么旋轉(zhuǎn)鏈每次從#〔M-j〕，j=1,2,...,M-1繞著固定鏈#(N-L),L=1,2,....N-1進(jìn)行比較，直到完成匹配.5.3.3、模型三的MATLAB求解表6：對于附件五的碎紙片排列矩陣第一面01234561078b111b125a140a155a150a2089a010b036a076b178a044a3186b153a084b042b030a038a4199b011b161b169b194b173b5088b107a149b180a037b191a6114a184b179b116b207a058a7146a171b031a201a050a190b8165b195a118a157a168a046a9003b007b085b148b077a004a10023b133a048a051b095a160b11099a043a096b109a123a006a78910111213183b174b110a066a108a018b029a025b192a124b022a120b144a079a121a098a094b061a137b045a138a206b156a034a181b198b087a132b065b115b166b001b151b170b041a158a197a154b028b012a017b120b092b019b016b177b053b202a021b067a063b075b167a117b008b068b069a032a074b126b176a158a000b119a033b071b052a062a129b118b104a134a113a026b049b091b106b141516171819198b081b164b020a047a136b014a059a060b147a152a005a056b131b187b086b200b143b093a072b175a097a039b083a070b139b002a162b203b090a064b208a142a057a024a013a130a163a193b073b159a035a188a127a040a182b122a172a180b027a135b141a204b105a101a015b205a082b145a009b100b055b103a112a196b054b表7：對于附件五的碎紙片排列矩陣第二面01234561136a047b020b164a081a198a2005b152b147b060a059b014b3143a200a086a187a131a056a4083b039a097b175b072a093b5090b203a162a002b139a070a6013b024b057b142b208b064a7035b159b073a193a163b130b8172b122b182a040b127b188b9105b204a141b135a027b180a10009a145b082a205b015a101b11054a196a112b103b055a100a78910111213029b018a108b066b110b174a183a079b144b120a022b124a192b025a138b045b137a061b094a098b121b132a087b198a181a034b156b206a041b170a151a001a166a115a065a120a017a012b028a154a197b158b021a202b053a177a016a019a092a068a008a117a167b075a063a067b000a158b176b126a074a032b069b118a129a062b052b071a033a119b106a091a049a026a113b134b104b141516171819150b155b140b125b111a078a044b178b076a036b010a089b038b030b042a084a153b186a173a194a169a161a011a199a191b037a180b149a107b088a058b207b116a179a184a114b190a050b201b031b171a146b046b168b157b118b195b165a004b077b148a085a007a003a160a095b051a048b133b023a006b123b109b096a043b099b六、模型求解結(jié)果分析針對問題一的結(jié)果進(jìn)行分析。題目所給出圖片量小，圖片匹配出的效果好，在相似度的分析中，出現(xiàn)的誤差減小。最后拼接出的圖像清晰，人工干預(yù)量小.針對問題二的結(jié)果進(jìn)行分析。題目給出的圖片量較大，相似度分析中出現(xiàn)的誤差較大。在聚類分析中設(shè)定的參數(shù)也相應(yīng)較大，導(dǎo)致最后的誤差較大。量的增加同時(shí)也使得人工干預(yù)增多，最后拼出圖片的效果也相應(yīng)較低.針對問題三的結(jié)果進(jìn)行分析。在本論文中，基于ACA的SIFT圖像特征點(diǎn)分析算法對圖片進(jìn)行匹配，相較于簡單的二值矩陣相似度匹配方法和相關(guān)灰度的算法，運(yùn)行的速度變快，精度增大，匹配的效果較好。但是由于題目給出的圖片量較為龐大，導(dǎo)致人工干預(yù)增加，使得最后產(chǎn)生的誤差增大.七、模型的優(yōu)缺點(diǎn)分析7.1模型優(yōu)點(diǎn):本文建立的模型比較多，模型計(jì)算過程清晰簡單，并且可以通過MATLAB快速求解，有比較強(qiáng)的理論性及實(shí)用性，通過對模型的分析，驗(yàn)證了其的可靠性，為司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等提供了方便，相對于人工拼接，節(jié)約了時(shí)間本錢。因此，具有重要的實(shí)際意義和較高的應(yīng)用價(jià)值.1、迭代算法使最正確分割閾值不受噪聲影響,因此邊緣點(diǎn)完全由自身的灰度值確定,防止了噪聲影響范圍的擴(kuò)大。圖像閾值分割能夠提取完整的圖像輪廓,使檢測所得邊緣具有連續(xù)性。數(shù)學(xué)形態(tài)學(xué)的腐蝕算法保證了檢測得到的邊緣僅有一個(gè)像素的寬度,邊緣定位精確。同時(shí)防止了邊緣寬度增加而引起鄰近邊緣的重疊。即使邊緣比較模糊,也能通過閾值分割得到增強(qiáng),運(yùn)用腐蝕算法能可靠地提取邊緣.2、蟻群算法與其他啟發(fā)式算法相比，在求解性能上，具有很強(qiáng)的魯棒性〔對根本蟻算法模型稍加修改，便可以應(yīng)用于其他問題〕和搜索較好解的能力。蟻群算法是一種基于種群的進(jìn)化算法，具有本質(zhì)并行性，易于并行實(shí)現(xiàn)。蟻群算法很容易與多種啟發(fā)式算法結(jié)合，以改善算法性能.7.2.模型缺點(diǎn)：1、鄰域平均處理方法是以圖像模糊為代價(jià)來減小噪聲的，且模板尺寸越大，噪聲減小的效果越顯著.2、Sobel算子沒有基于圖像灰度進(jìn)行處理，由于Sobel算子沒有嚴(yán)格地模擬人的視覺生理特征，所以提取的圖像輪廓有時(shí)并不能令人滿意.八、模型的推廣與改進(jìn)8.1、模型改進(jìn)相似度計(jì)算方法改進(jìn)本論文第二個(gè)問題是采用的二元相似性度量算法分析，上述模型中，我們只討論了連通像數(shù)K=4的情況，現(xiàn)在我們簡單說明連通像數(shù)K=8的狀況.此時(shí)，對于一個(gè)中間像素點(diǎn)i，它與其八連通像素的關(guān)系可以表示為式：可以看到，在K=8時(shí)，相似度會(huì)更加的精確，考慮時(shí)間和效率問題，還是盡量不要采用連通像數(shù)K=8的算法.8.2模型推廣對于本論文的圖片拼接問題，我們將圖片進(jìn)行了圖片去噪濾波、膨脹腐蝕、相似度匹配等。這些技術(shù)，在生活中具有廣泛的應(yīng)用。類似的研究主要集中在文物碎片的自動(dòng)修復(fù)、虛擬考古、故障分析及計(jì)算機(jī)輔助設(shè)計(jì)、醫(yī)學(xué)分析等領(lǐng)域.九、參考文獻(xiàn)[1]董漢莉.Marr-Hildreth算子邊緣精確定位的研究[J].鄭州工業(yè)大學(xué)學(xué)報(bào),1999,4.[2]孫慧,等.圖像處理中邊緣檢測技術(shù)的研究[J].電腦開發(fā)與應(yīng)用,2002,15(10):7-9[3]王鄭耀.數(shù)字圖像邊緣檢測[D].西安:西安交通大學(xué)理學(xué)院,2003.[4]侯舒維.圖像拼接技術(shù)研究[D].西安:西安電子科技大學(xué),2005.[5]萬豐.一種全自動(dòng)穩(wěn)健的圖像拼接融合算法[J].中國圖形圖像學(xué)報(bào),004.9(4):417-422.[6]王磊，莫玉龍，戚飛虎.基理論的邊緣提取改善方法[J].中國圖象圖形學(xué)報(bào)，1996.[7]劉金根，吳志鵬.一種基于特征區(qū)域分割的圖像拼接算法[J].西安電子科技大學(xué)學(xué)報(bào)，2002.[8]韓曉軍.數(shù)字圖像處理技術(shù)與應(yīng)用.北京:電子工業(yè)出版社，2023[9]MALLATS.ATourGuideofSignalProcessing[M].Beijing：MachineIndustryPress，2003．95-150．附錄附件一用Matlab對問題一進(jìn)行二值化和相似度匹配排序clcclear;I=dir('C:\Users\hp\Desktop\wc\*.bmp');imread_num=length(I);p=struct('zhangshu','imread','zuo','you');fori=1:imread_nump(i).zhangshu=i;p(i).imread=imread(I(i).name,'bmp');aaa=p(i).imread;[mn]=size(aaa);p(i).zuo=aaa(:,1);p(i).you=aaa(:,n);endfori=1:imread_numccc=p(i).zuo;bbb(1,i)=sum(ccc);end[zhizhizhittt]=max(bbb);qqq=ttt-1;disp('最左邊那張是？');qqq;forj=1:imread_numjjj=ttt;youyou=p(jjj).you;zuozuo=p(j).zuo;sss(1,j)=(1/m)*sum((zuozuo-youyou).^2);end[zhizhittt]=min(sss);ttt-1;用Matlab對附件一和附件二中的碎紙片排序拼接代碼附件一碎紙圖片拼接代碼I1=imread('008.bmp');I2=imread('014.bmp');I3=imread('012.bmp');I4=imread('015.bmp');I5=imread('003.bmp');I6=imread('010.bmp');I7=imread('002.bmp');I8=imread('016.bmp');I9=imread('001.bmp');I10=imread('004.bmp');I11=imread('005.bmp');I12=imread('009.bmp');I13=imread('013.bmp');I14=imread('018.bmp');I15=imread('011.bmp');I16=imread('007.bmp');I17=imread('017.bmp');I18=imread('000.bmp');I19=imread('006.bmp');I=[I1,I2,I3,I4,I5,I6,I7,I8,I9,I10,I11,I12,I13,I14,I15,I16,I17,I18,I19];imshow(I)〔附件2的拼接代碼同上，將排序號(hào)改換即可〕附錄圖一：附件一碎紙片拼接結(jié)果附錄圖二：附件二碎紙片拼接結(jié)果附件二Matlab進(jìn)行碎紙片邊緣化處理和相似度矩陣求解clcclearallfori=0:208d{i+1}=imread(strcat('C:mathmodel\AS\',num2str(i,'%03d'),'.bmp'));d{i+1}=im2bw(d{i+1})endTmatrix=zeros(11,19);TCol=zeros(11,19);leftEdge=12;TopEdge=37;Tmaxtrix(1,1)=50;colspan=6;rowspan=28;TUsed=zeros(1,209);TUsed(50)=1;count=1;TCol(1,1)=50;forj=1:length(TUsed)if(TUsed(j)~=1)tempTotal=sum(sum(d{j}(1:180,1:leftEdge)));if(tempTotal==180*leftEdge)TUsed(j)=1;count=count+1;TCol(count,1)=j;endendendfori=1:11forl=1:18maxcount=0;forj=1:209if(TUsed(j)~=1)count=0;samespan=0;k=UpBracket(d{j});if(i==1)if(UpBracket(d{j})>=TopEdge)ret=RightBracket(d{TCol(i,l)});if(ret~=0)if(RightBracket(d{TCol(i,l)})+LeftBracket(d{j}==colspan))samespan=samespan+1;TCol(i,l+1)=j;if(samespan>1)pauseendbreak;endelsecount=simstat(d{TCol(i,l)},d{j});if(count>maxcount)TCol(i,l+1)=jmaxcount=count;endendendelset1=TCol(i,l);if(UpBracket(d{t1})==UpBracket(d{j}))if(RightBracket(d{TCol(i,l)})~=0)m=TCol(i,l);n=RightBracket(d{m})+LeftBracket(d{j})if(n==colspan)TCol(i,l+1)=j;endelsecount=simstat(d{TCol(i,l)},d{j})if(count>maxcount)TCol(i,l+1)=j;maxcount=count;endendendendendendtemp=TCol(i,l+1);TUsed(temp)=1;endendMatlab進(jìn)行搜索排序拼接碎紙圖片的代碼I=dir('.\*.bmp');im_num=length(I);im_temp=imread(I(1).name,'bmp');[height,width]=size(im_temp);DB(:,:,a)=zeros(height,width,im_num,'uint8');fora=1:length(I)DB(:,:,a)=imread(I(a).name,'bmp');endif(isgray(I)==0)disp('請輸入灰度圖');elseif(size(I)~=[128,128])disp('大小不合要求');elseH.color=[111];figure(H);imshow(I);zeroImage=repmat(uint8(0),[128128]);figure(H);meansImageHandle=im