基于結(jié)構(gòu)特征的碎紙片的拼接復(fù)原問題—課程設(shè)計(jì)論文

1、課程設(shè)計(jì)論文基于結(jié)構(gòu)特征的碎紙片的拼接復(fù)原問題基于結(jié)構(gòu)特征的碎紙片的拼接復(fù)原問題摘要 碎紙自動拼接技術(shù)是圖像處理與模式識別領(lǐng)域中的一個(gè)典型的應(yīng)用，該技術(shù)通過掃描和圖像提取技術(shù)獲取一組碎紙片的形狀、紋理及內(nèi)容等信息，然后利用計(jì)算機(jī)進(jìn)行相應(yīng)理解從而實(shí)現(xiàn)對這些碎紙片的全自動或半自動拼接還原。針對問題一，考慮到縱切的碎紙片所含有的信息量較大，利用圖像處理中的信號匹配方法，結(jié)合左右兩個(gè)碎紙片的灰度像素矩陣的邊緣特征，建立基于結(jié)構(gòu)特征的灰度匹配模型，對英文字母制定了灰度相似的配準(zhǔn)規(guī)則，使待拼接的碎紙片邊緣的對應(yīng)行像素之差的平方和最小；而結(jié)合中文字符的橫筆結(jié)構(gòu)特征，對中文字制定了“橫筆”匹配相似度的配準(zhǔn)規(guī)則

2、，并給出了最終的碎紙拼接圖和拼接次序，拼接的正確率是100%。針對問題二，對于既縱切又橫切的情形，每一個(gè)紙片的邊緣所含的信息量相對較少，故對中、英文碎片的拼接復(fù)原需各自建模分析。首先利用“分而治之”的思想，將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題。對于中文碎片拼接復(fù)原，根據(jù)中文的方塊特點(diǎn)，給出了中文的文字結(jié)構(gòu)特征向量及其邊緣像素的特征向量。根據(jù)這些結(jié)構(gòu)特征向量對所有的碎紙片進(jìn)行粗分類，在此基礎(chǔ)上設(shè)計(jì)了基于邊緣特征的匹配規(guī)則集，對每一行從左到右在進(jìn)行細(xì)匹配。利用等距序列圖像的快速拼接技術(shù)拼出左邊第一列，基于灰度匹配，將圖像轉(zhuǎn)化為二值圖像并對每行進(jìn)行最優(yōu)匹配。先按照行配準(zhǔn)，然后再進(jìn)

3、行列配準(zhǔn)，最終匹配出誤差最小的圖像；對于英文碎片復(fù)原同樣采取人工干預(yù)粗分類，粗匹配后，采用神經(jīng)網(wǎng)絡(luò)算法對碎片圖像訓(xùn)練、學(xué)習(xí)構(gòu)建bp網(wǎng)絡(luò)對英文字母進(jìn)行匹配識別，結(jié)合剪枝定界法實(shí)現(xiàn)英文碎片的拼接復(fù)原。發(fā)現(xiàn)每行匹配率為78.85%，整篇匹配率大約為68.73%。針對問題三，由于碎片數(shù)據(jù)均為雙面打印文件，文字特征相同，僅用問題二中的方法產(chǎn)生的誤差太大，仍沿用粗分類特點(diǎn)通過神經(jīng)網(wǎng)絡(luò)拼接、灰度匹配修正、人工干預(yù)，結(jié)合等距序列拼接技術(shù)實(shí)現(xiàn)單面拼接，然后驗(yàn)證反面的正確性并修正。關(guān)鍵詞：圖像拼接，灰度配準(zhǔn)， 結(jié)構(gòu)特征，配準(zhǔn)規(guī)則，神經(jīng)網(wǎng)絡(luò) 一、問題重述破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)

4、域都有著重要的應(yīng)用。拼接復(fù)原工作若由人工完成，準(zhǔn)確率較高，但效率很低。特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時(shí)間內(nèi)完成任務(wù)?，F(xiàn)試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復(fù)原效率。我們需要建立數(shù)學(xué)模型解決以下問題：1. 對于給定的來自同一頁印刷文字文件的碎紙機(jī)破碎紙片（僅縱切），建立碎紙片拼接復(fù)原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，寫出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。2. 對于碎紙機(jī)既縱切又橫切的情形，設(shè)計(jì)碎紙片拼接復(fù)原模型和算法，并針對附件3、附件4給出的中、英文各一頁文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，寫出干預(yù)方

5、式及干預(yù)的時(shí)間節(jié)點(diǎn)。3. 現(xiàn)實(shí)情形中可能有雙面打印文件的碎紙片拼接復(fù)原問題需要解決。附件5給出的是一頁英文印刷文字雙面打印文件的碎片數(shù)據(jù)。嘗試設(shè)計(jì)相應(yīng)的碎紙片拼接復(fù)原模型與算法，并就附件5的碎片數(shù)據(jù)給出拼接復(fù)原結(jié)果。二、問題分析碎紙自動拼接復(fù)原技術(shù)在司法鑒定，歷史研究等領(lǐng)域都有著廣泛的應(yīng)用。近年來,隨著德國斯塔西文件的恢復(fù)工程的公布,碎紙文件復(fù)原技術(shù)的研究引起了人們的廣泛關(guān)注。碎紙自動拼接技術(shù)是模式識別領(lǐng)域中的一個(gè)很典型的應(yīng)用。涉及數(shù)字圖像處理，機(jī)器學(xué)習(xí)等多個(gè)學(xué)科，充分體現(xiàn)了當(dāng)下多學(xué)科相互融合的學(xué)科特點(diǎn)，這也正說明了碎紙自動拼接本身具有一定的難度。 匹配技術(shù)是碎紙自動拼接技術(shù)的關(guān)鍵，它可以分為

6、兩個(gè)步驟：局部拼接和全局恢復(fù)。局部拼接是指碎片兩兩之間的拼接問題，全局拼接是關(guān)于一組碎片之間的匹配問題。局部匹配技術(shù)可以分為兩類，一類比較具體，多對應(yīng)圖像低層像素或像素的集合，統(tǒng)稱為圖像匹配；另一類則比較抽象，主要與圖像或目標(biāo)的性質(zhì)有關(guān)統(tǒng)稱為廣義匹配。圖像匹配包括模板匹配、目標(biāo)匹配和動態(tài)模式匹配。廣義匹配包括關(guān)系匹配、線圖同構(gòu)和特征內(nèi)容匹配。特征內(nèi)容匹配包括顏色匹配、紋理匹配、形狀匹配和綜合特征匹配等。目前對碎紙拼接的研究，主要應(yīng)用的是特征內(nèi)容的匹配，本文應(yīng)用其中的輪廓匹配。碎紙拼接中的匹配技術(shù)，與傳統(tǒng)匹配技術(shù)不同，它的特征都是未知的，沒有先驗(yàn)知識可以參考，這也是碎紙拼接的難點(diǎn)。 對于傳統(tǒng)破碎

7、文件的拼接，更多的使用破碎紙片的邊緣形狀提取其輪廓曲線并利用計(jì)算機(jī)算法進(jìn)行拼接，但現(xiàn)今越來越多的破碎紙片拼接問題中破碎紙片的邊緣形狀都近似相同，邊緣形狀拼接不再實(shí)用。而對于邊緣相似的破碎紙片的拼接，理想的計(jì)算機(jī)拼接過程應(yīng)當(dāng)與人工拼接的結(jié)果相同，但計(jì)算機(jī)無法完全的識別破碎紙片上帶有的信息，所以對于現(xiàn)有算法只能近似完成破碎紙片的拼接。針對問題一，因使用碎紙機(jī)對紙片進(jìn)行縱切，每個(gè)縱切的紙片所含的信息量較大，所以對于問題一，利用左右兩個(gè)紙片的邊緣特征，可以制定灰度相似的配準(zhǔn)規(guī)則，使得紙片邊緣的對應(yīng)行像素之差的平方和最小，拼接成功率將會更高。針對問題二，使用碎紙機(jī)對紙片進(jìn)行縱切且橫切，問題變的復(fù)雜，由于

8、紙片數(shù)量多，且碎紙片包含的信息少，用灰度匹配的話，一定會有較大的誤差。如果單純考慮使用某種算法在解空間中進(jìn)行遍歷搜索最優(yōu)匹配，算法的復(fù)雜度較高。如何合理的減小誤差又不至于增加太多的工作量，就需要找到恰當(dāng)?shù)乃惴ê湍Ｐ蛯栴}一進(jìn)行優(yōu)化。我們可以利用“分而治之”的思想，首先把所有的紙片按照其字符的結(jié)構(gòu)特征（如行間距，列間距，字高，字寬，字間距等）進(jìn)行粗分類，然后通過人工干預(yù)，拼出左邊第一列，先按照行配準(zhǔn)，然后在進(jìn)行列配準(zhǔn)。 對于每一行配準(zhǔn)，我們可以刻畫每個(gè)碎紙片的特征，分為結(jié)構(gòu)特征和邊緣像素特征。對于碎紙片，我們在尋找某個(gè)邊的待選碎片時(shí)，可以指定規(guī)則來提升效率，比如在左邊匹配時(shí)，用行間距過濾掉不符合

9、的碎片(也就是過濾掉不符合約束條件的取值范圍)，也就是剪枝定界法；如果帶匹配的左邊是有黑色數(shù)值的，再用目標(biāo)碎片右邊應(yīng)該也有黑色數(shù)值，且出現(xiàn)的位值相近過濾掉圖片；再用拼接好的圖片中的字間距看看是否符合一個(gè)字的寬度等。通過配準(zhǔn)規(guī)則，結(jié)合字符的結(jié)構(gòu)特征和邊緣特征，我們應(yīng)該可以得出第二問的配準(zhǔn)圖像。針對問題三，碎片依然被縱切、橫切成了209塊。但本題中還加入了正反兩面，增加了問題的復(fù)雜性，不過建模的總體思想并沒有變。首先我們要通過配準(zhǔn)規(guī)則，結(jié)合字符的結(jié)構(gòu)特征和邊緣特征對碎片進(jìn)行一次拼接，但誤差將會很大。為更好的減小誤差，我們可以結(jié)合灰度匹配和人工干預(yù)對已生成的圖像進(jìn)行修正。三、符號說明符號 表示含義異

10、或邏輯的真值 第個(gè)碎紙片 和這兩個(gè)碎紙片相連的可能性 兩碎片上下邊緣無字區(qū)域行數(shù)和 異或運(yùn)算 碎片矩陣在的值 碎片矩陣在的值 級聯(lián)運(yùn)算四、模型假設(shè)結(jié)合本題實(shí)際，為了確保模型求解的準(zhǔn)確性和合理性，我們排除了一些因素的干擾，提出以下幾點(diǎn)假設(shè)：1.假設(shè)每條碎紙片都保持完整，無破損。2.假設(shè)碎紙機(jī)切紙片的切口都較整齊。3.假設(shè)同一頁文件上文字的打印墨濃度相同。4.假設(shè)同一頁文件上文字的字體相同，同一頁文件上文字只包含中文或者英文。5.假設(shè)文件上文字顏色不受空氣中水分等其他因素的影響.6.假設(shè)圖像不許進(jìn)行降噪、平滑濾波等預(yù)處理。五、模型的建立與求解5.1模型建立前的準(zhǔn)備5.1.1設(shè)置匹配準(zhǔn)則集本題目并不

11、是一個(gè)簡單的圖像拼接問題，所以我們設(shè)置包含灰度匹配、基于特征、bp神經(jīng)網(wǎng)絡(luò)、異或運(yùn)算相結(jié)合的匹配準(zhǔn)則集。 1.灰度匹配灰度匹配的基本思想:以統(tǒng)計(jì)的觀點(diǎn)將圖像看成是二維信號，采用統(tǒng)計(jì)相關(guān)的方法尋找信號間的相關(guān)匹配。利用兩個(gè)信號的相關(guān)函數(shù)，評價(jià)它們的相似性以確定同名點(diǎn)?；叶绕ヅ渫ㄟ^利用某種相似性度量，如相關(guān)函數(shù)、協(xié)方差函數(shù)、差平方和、差絕對值和等測度極值，判定兩幅圖像中的對應(yīng)關(guān)系。最經(jīng)典的灰度匹配法是歸一化的灰度匹配 法，其基本原理是逐像素的把一個(gè)以一定大小的實(shí)時(shí)圖像窗口的灰度矩陣，與參考圖像的所有可能的窗口灰度陣列，按某種相似性度量方法進(jìn)行搜索比較的匹配方法，從理論上說就是采用圖像相關(guān)技術(shù)。 2

12、.基于特征 大多數(shù)完整文字文檔的文字行方向和行間距平行且單一，如果碎片內(nèi)的文字行在碎片邊緣斷裂，那么與它相鄰的碎紙片在邊緣處一定有相同高度、相同間距的文字行，憑此特征可以很容易得從形狀相似的多碎片中挑選出相鄰碎片。因文字行的高度特征、間距特征的識別比字跡斷線識別和文字圖像的理解實(shí)現(xiàn)起來更容易些，利用碎片內(nèi)文字行特征拼接相似的碎紙片理論上是可行的。 3.bp神經(jīng)網(wǎng)絡(luò) bp (back propagation)神經(jīng)網(wǎng)絡(luò)，即誤差反傳誤差反向傳播算法的學(xué)習(xí)過程，由信息的正向傳播和誤差的反向傳播兩個(gè)過程組成。輸入層各神經(jīng)元負(fù)責(zé)接收來自外界的輸入信息，并傳遞給中間層各神經(jīng)元；中間層是內(nèi)部信息處理層，負(fù)責(zé)信

13、息變換，根據(jù)信息變化能力的需求，中間層可以設(shè)計(jì)為單隱層或者多隱層結(jié)構(gòu)；最后一個(gè)隱層傳遞到輸出層各神經(jīng)元的信息，經(jīng)進(jìn)一步處理后，完成一次學(xué)習(xí)的正向傳播處理過程，由輸出層向外界輸出信息處理結(jié)果。當(dāng)實(shí)際輸出與期望輸出不符時(shí)，進(jìn)入誤差的反向傳播階段。誤差通過輸出層，按誤差梯度下降的方式修正各層權(quán)值，向隱層、輸入層逐層反傳。周而復(fù)始的信息正向傳播和誤差反向傳播過程，是各層權(quán)值不斷調(diào)整的過程，也是神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)訓(xùn)練的過程，此過程一直進(jìn)行到網(wǎng)絡(luò)輸出的誤差減少到可以接受的程度，或者預(yù)先設(shè)定的學(xué)習(xí)次數(shù)為止。 4.異或運(yùn)算異或邏輯的真值表如圖1所示，其邏輯符號如圖2所示。異或邏輯的關(guān)系是：當(dāng)不同時(shí)，輸出；當(dāng)相同時(shí)，

14、輸出。“”是異或運(yùn)算符號，異或邏輯也是與或非邏輯的組合，其邏輯表達(dá)式為：由圖1可知，異或運(yùn)算的規(guī)則是00=0, 01=110=1, 11=0口訣：相同取0，相異取1事實(shí)上，xor 在英文里面的定義為either one (is one), but not both， 也即只有一個(gè)為真（1）時(shí)，取真（1）。5.1.2“橫筆”法的背景我們查找了漢字的書寫方式。漢字的基本筆畫為橫、豎、撇、點(diǎn)、折。根據(jù)張興初等1965年在心理學(xué)報(bào)1 “漢字的各種筆畫的使用頻率的估計(jì)”中的統(tǒng)計(jì)結(jié)果顯示：橫筆占31%，豎筆占16%，撇筆占15%，點(diǎn)筆占12%；張靜賢在2004年漢字教程2中的統(tǒng)計(jì)顯示：橫筆占27.68%，

15、豎筆占17.60%，撇筆占15.69%，點(diǎn)筆占13.62%。通過比較我們可以發(fā)現(xiàn)在日常生活中運(yùn)用的漢字“橫筆”出現(xiàn)的概率最高。同時(shí)，根據(jù)“gb130001字符集漢字字序規(guī)范” 3中的相關(guān)統(tǒng)計(jì)，目前使用的漢字總共有20902個(gè)，平均每個(gè)字12.8畫，其中12畫的漢字最多，共有1957個(gè)。而在“現(xiàn)代漢字常用字表”中，常用漢字為3500個(gè)，平均每個(gè)字9.7畫，其中9畫的漢字最多，一共415個(gè)。基于上述數(shù)據(jù)，可以推斷出“gb130001字符集”中，平均每個(gè)漢字有3.54畫的橫筆，而常用漢字中，平均每個(gè)漢字有2.68畫的橫筆，可以說橫筆在整個(gè)漢字結(jié)構(gòu)中出現(xiàn)頻次最高，占有重要的地位。所以我們在帶有漢字的碎

16、片拼接時(shí)運(yùn)用了“橫筆”拼接法。5.2 問題一的模型建立與求解5.2.1. 目標(biāo)函數(shù)假設(shè)整頁文檔被碎紙機(jī)碎成了個(gè)碎紙片的集合，給定一個(gè)正確的拼接排列滿足其中，|表示了一種級聯(lián)運(yùn)算符號。對于紙片集合，需要識別相連的碎紙片對5。例如， 我們用表示 和這兩個(gè)碎紙片相連的可能性。這樣碎紙片的正確拼接復(fù)原問題就轉(zhuǎn)化為一個(gè)優(yōu)化問題，目標(biāo)函數(shù)為：我們需要搜索所有的拼接排列組合滿足使得上述的目標(biāo)函數(shù)最大。5.2.2. 特征選擇對于問題一的目標(biāo)函數(shù)，顯然表示了碎片 和配準(zhǔn)的相似度，相似度越大，說明兩個(gè)碎片配準(zhǔn)的越好。這里考慮到問題一的縱切，每個(gè)碎紙片的信息量大，我們在定義時(shí)，只需要用到碎紙片的邊緣像素特征。 具體

17、來說，利用了圖像處理的灰度圖像匹配方法4進(jìn)行相似度的計(jì)算灰度圖像拼接主要是以統(tǒng)計(jì)的觀點(diǎn)將圖像看成是二維信號，采用統(tǒng)計(jì)相關(guān)的方法尋找信號間的相關(guān)匹配。利用兩個(gè)信號的相關(guān)函數(shù)，評價(jià)它們的相似性以確定同名點(diǎn)?；叶绕ヅ渫ㄟ^利用某種相似性度量，如相關(guān)函數(shù)、協(xié)方差函數(shù)、差平方和、差絕對值和等測度極值，判定兩幅圖像中的對應(yīng)關(guān)系。最經(jīng)典的灰度匹配法是歸一化的灰度匹配法，其基本原理是逐像素的把一個(gè)以一定大小的實(shí)時(shí)圖像窗口的灰度矩陣，與參考圖像的所有可能的窗口灰度矩陣，按某種相似性度量的方法進(jìn)行搜索比較的匹配方法。5.2.3. 算法設(shè)計(jì)與求解1.中文碎片的拼接 對圖片進(jìn)行兩兩拼接，對比兩個(gè)碎片中“橫筆”位置，其中

18、“橫筆”位置一致的記錄下來，搜索整個(gè)碎片邊緣，利用目標(biāo)函數(shù)：記錄匹配總和。最終以匹配總和為依據(jù)，匹配數(shù)最大的兩個(gè)碎片進(jìn)行拼接。流程圖為圖（1）。圖（1）流程圖算法步驟：step 1：圖像處理對給定的圖像進(jìn)行灰度處理，生成灰度矩陣6，并把矩陣二值化。step 2：邊緣最小二乘法計(jì)算選取任兩個(gè)碎片相鄰的邊緣數(shù)值進(jìn)行“橫筆”和最小二乘法計(jì)算。利用最小二乘法做出殘差分析圖，見圖（2）。圖（2）殘差分析圖step 3：圖像拼接利用最小二乘法找出相似度最大的兩張圖片進(jìn)行拼接，若出現(xiàn)兩對碎片的匹配數(shù)一樣時(shí)，則進(jìn)行人工干預(yù)，選出最佳拼接。以此類推，最終得到要拼接的圖像，圖像和代碼見附錄（1）。step 4：檢

19、驗(yàn)重復(fù)上述步驟 ，得出多幅完整圖像，人工選出最佳匹配圖，得到最左側(cè)和最右側(cè)的圖像并排除匹配順序，見圖（3）。圖（3）圖像匹配順序2.英文碎片的拼接 在英文字符中幾乎不再存在“橫筆”，所以這里我們無法在使用“橫筆”拼接法。但是英文碎片生成的灰度矩陣的邊界依然存在相似度的特征，所以我們針對英文碎片直接采用基于最小二乘法的灰度匹配方法。算法步驟：step 1：圖像處理對給定的圖像進(jìn)行灰度處理，生成灰度矩陣。step 2：邊緣相似度計(jì)算人工選出最左邊的碎片，然后對圖片右邊緣數(shù)組與其他所有的碎片左邊緣進(jìn)行最小二乘法計(jì)算，求出相似度，做出殘差分析圖，見圖（4）。圖（4）殘差分析圖step 3：圖片拼接找出

20、相似度最大碎片進(jìn)行拼接，以此類推拼出全圖。圖像和代碼見附錄（2）step 4：檢驗(yàn)重復(fù)上邊步驟，生成多幅完整圖像，人工選出最佳匹配圖，得到最左側(cè)和最右側(cè)的圖像并排除匹配順序，見圖（4）。圖（4）圖像匹配順序5.3問題二的模型建立與求解5.3.1問題二的模型建立 1.異或模型 對任一碎片進(jìn)行二值化，選取右邊緣的一列值（x1，x2，x3），選取另一張圖片的左邊緣的一列值（y1,y2,y3），根據(jù)異或運(yùn)算準(zhǔn)則：0異或0=0，1異或0=1，0異或1=1，1異或1=0。對相同行的數(shù)值進(jìn)行異或運(yùn)算，即p=ab（“”是異或運(yùn)算符號）對碎片間相鄰兩邊緣間的異或值進(jìn)行統(tǒng)計(jì)，以此作為對比碎片拼接相似度的依據(jù)。主要

21、目標(biāo)函數(shù)為： 5.3.2 問題二的模型求解1.中文碎片的拼接在問題二中，碎片共有208個(gè)，切碎片大小形狀完全一樣，但因?yàn)槊總€(gè)圖片太小，上邊的文字信息太少，所以中文使用“橫筆”拼接法的誤差太大，所以本題我們改用邊界特征、異或運(yùn)算、人工干預(yù)、最小二乘法等多種匹配方法相結(jié)合的方式對模型進(jìn)行了改進(jìn)，流程圖為圖（5）。圖（5）流程圖具體步驟如下：step 1：圖像處理對給定的圖像進(jìn)行灰度處理，生成灰度矩陣，并把矩陣二值化。step 2：邊緣碎片選取利用整體邊緣無字光滑的特征，在灰度矩陣中選取最左邊向量x1,x2,x3,x4,x5全為1的碎片。step 3：邊緣碎片拼接利用最小二乘法對碎片上下矩陣邊緣進(jìn)行

22、相似度計(jì)算，求出具有最佳相似度的碎片進(jìn)行兩兩拼接。隨機(jī)取一行，拼接效果如圖（6）圖（6）拼接效果圖step 4:邊緣碎片再拼接由于碎片太小，上下邊緣包含信息太少，基于最小二乘法的邊緣相似度拼接并不能夠達(dá)到滿意效果。所以我們利用行距對上步拼接結(jié)果進(jìn)行再次拼接。分別對step 3中7張新紙片計(jì)算上下邊緣無字區(qū)域所占行數(shù)，然后7張紙片兩兩首尾無字區(qū)域行數(shù)求和，記為d，如圖（7）所示。倘若 或 時(shí)，則可認(rèn)為兩碎片可以進(jìn)行拼接，否者不能拼接。拼接流程見圖（8）。以此類推共得出以下幾種結(jié)果。如圖（9）所示注：時(shí)，表示行間距為2831像素； 時(shí)，表示兩個(gè)行間距加字高為96102像素；圖（7）圖（8）圖（9）

23、step 5：人工干預(yù)人工的方式在這幾種拼接方式中選出最佳拼接（方案三），作為完整圖像的左邊界。step 6：文字行特征分類把左邊界的11個(gè)碎片依據(jù)文字行特征進(jìn)行分類。依據(jù)11中分類把剩余碎片進(jìn)行分類，使具有相同高度和間距文字行的碎片歸為一類。step 7：異或運(yùn)算拼接以左邊界碎片為起點(diǎn)，對同類碎片進(jìn)行邊緣異或運(yùn)算。即：選取相鄰邊緣向量x1，x2，x3，x4、y1,y2,y3,y4，若同行的點(diǎn)的值相同則記為0，不同記為1。最后統(tǒng)計(jì)0的個(gè)數(shù)f，當(dāng)f閾值時(shí)則認(rèn)為兩碎片可以進(jìn)行拼接，否者舍棄。并在所有的比拼中選取f值最大的一個(gè)碎片與預(yù)定圖片進(jìn)行拼接。以此類推拼接出完整圖像。step 8：檢驗(yàn)多次重復(fù)

24、上述步驟產(chǎn)生多幅圖像，人工篩選出最佳拼接圖像。代碼及圖像見附錄。 2.英文碎片的拼接 算法設(shè)計(jì)：在英文碎片的拼接中我們采用bp神經(jīng)網(wǎng)絡(luò)來對碎片進(jìn)行拼接。因?yàn)閎p神經(jīng)網(wǎng)絡(luò)（圖）可以通過監(jiān)督式學(xué)習(xí)來對我們無法具體表示出特征的英文字符進(jìn)行圖像特征提取，并通過提取的特征對碎片進(jìn)行整體分類，識別輸出。這種算法具有收斂快，權(quán)值更新準(zhǔn)則簡單等優(yōu)點(diǎn)。bp神經(jīng)網(wǎng)路算法流程圖為圖（10）。圖（10）算法求解： step 1 圖像處理對給定的圖像進(jìn)行灰度處理，生成灰度矩陣。step 2 圖像分割我們根據(jù)碎片中圖像的灰度閾值、邊緣檢測進(jìn)行分割。設(shè)定閾值t，通過函數(shù)進(jìn)行分割。其中對于物體的圖像元素，對于背景的圖像元素。

25、step 3 圖像特征提取首先要明確提取的特征要滿足唯一性、可分性、魯棒性特點(diǎn)才能使圖像提取的特征更有使用價(jià)值。利用特征參數(shù)的靈敏度變化來進(jìn)行特征提取出26個(gè)字母的灰度特征并記錄下來。訓(xùn)練效果圖如圖（11）。圖（11）訓(xùn)練效果圖step 4 圖像分類依據(jù)所提取的特征，將前一部分的特征向量空間映射到類型空間，把相應(yīng)原圖歸屬已知的一種模式。step 5 圖像識別針對每幅碎片的分割圖上的信息與之前存儲的26個(gè)英文字母的信息特征進(jìn)行對比識別。樣本識別圖如圖（12）圖（12）樣本識別圖step 6 圖像拼接依據(jù)上述方法選取相似度最大的碎片進(jìn)行拼接，先橫向拼接再縱向拼接，進(jìn)而拼出整體圖像。 圖像和代碼見附

26、錄。5.4 問題三的模型建立與求解1.算法設(shè)計(jì)在問題三中出現(xiàn)了正反兩面都有字的情況，這樣的話，我們需要進(jìn)行正反兩次的拼接才可以，問題變得復(fù)雜起來，但從題目所給的圖片來看，如果知道一個(gè)圖片的正面那么一定會有它的反面的信息，所以本題并不是很復(fù)雜，我們只需要對問題二中的英文碎片拼接的方法進(jìn)行一下改進(jìn)即可。流程圖見圖（12）圖（12）流程圖 2.算法步驟：step 1 bp神經(jīng)網(wǎng)絡(luò)拼接運(yùn)行問題二中的英文碎片拼接的方法：step 2 灰度匹配修正本題正反兩面都是英文，文字特征相同，僅用問題二中的方法產(chǎn)生的誤差太大。在這里我們選擇采用正面bp神經(jīng)網(wǎng)絡(luò)拼接，背面灰度匹配修正7的方法對模型進(jìn)行優(yōu)化。對上述拼接

27、好的完整圖反面進(jìn)行分析，首先利用灰度矩陣邊緣特征篩選出沒有達(dá)到閾值的碎片匹配，對這些碎片再次進(jìn)行基于最小二乘法的邊緣相似度計(jì)算，依照相似度重新進(jìn)行拼接。step 3 人工干預(yù)因?yàn)樯鲜龇椒ú徽撃姆N總存在誤差，進(jìn)行結(jié)合匹配后仍然不能完全的消除誤差，所以此處加入人工干預(yù)，通過人腦思維的文字圖像識別和理解能力，進(jìn)一步減小誤差，以達(dá)到組成最佳匹配的目的。完整圖和代碼見附錄。六、模型的優(yōu)缺點(diǎn)及改進(jìn)6.1模型的優(yōu)點(diǎn)模型主要采用了基于最小二乘法的灰度圖像匹配方法，大大較少了模型的計(jì)算量。針對復(fù)雜的碎片拼接時(shí)采用了人工干預(yù)和聚類分析的方法，是模型計(jì)算出來的結(jié)果更加準(zhǔn)確。針對中文和英文碎片分別采用了“橫筆”、字母

28、匹配的邊緣匹配方法，使得模型可以定向解決不同的碎片拼接問題。為解決計(jì)算機(jī)拼接的技術(shù)的限制，模型在重要的幾處加入了人工干預(yù)，使得模型的準(zhǔn)確度進(jìn)一步加強(qiáng)。6.2模型的缺點(diǎn)模型最初便假設(shè)碎片不用進(jìn)行預(yù)處理，這樣限制了模型的可用范圍。為降低模型的計(jì)算量，模型僅適用了一種方法判定兩幅圖的對應(yīng)關(guān)系，導(dǎo)致最終拼出的圖形差異稍大。模型多處用到人工干預(yù)，雖然加大了模型的準(zhǔn)確度，但同時(shí)也浪費(fèi)了太多的人力和時(shí)間。6.3模型的改進(jìn)該模型可以應(yīng)用到大部分碎片的拼接問題上，但該模型考慮的面太窄，在對于比較復(fù)雜的碎片拼接問題上扔無能為力。如果在運(yùn)行模型前加入對碎片的預(yù)處理，比如對不光滑的邊緣進(jìn)行邊緣拋光，圖像去噪等，模型運(yùn)

29、行效果會更好。 由于該模型較于簡單，所以運(yùn)行結(jié)果的精確度不是很高，對此，我們可以采用相關(guān)函數(shù)、協(xié)方差函數(shù)、差絕對值與基于最小二乘法的灰度匹配相結(jié)合的方法進(jìn)行模型建立，這將極大的提高模型的精確度。七、參考文獻(xiàn)1 張興初，漢字的各種筆畫的使用頻率的估計(jì)，心理學(xué)報(bào)，03期，1965年2 張靜賢，漢字教程，北京，北京語言大學(xué)出版社，1970年3 漢字字序規(guī)范課題組, gb13000.1字符集漢字字序(筆畫序)規(guī)范,語文建設(shè), 第05期1999年4 張賢達(dá)矩陣分析與應(yīng)用北京：清華大學(xué)出版社，2004：403-4525 董寧，工具技術(shù)，移動最小二乘法在nurbs曲線擬合中的應(yīng)用，工具技術(shù)， 第1期，201

30、1年6 趙輝，基于灰度共生矩陣的圖像研究，自動化技術(shù)與應(yīng)用，第3期，2004年7 羅鐘鉉，灰度圖像匹配的快速算法，計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，第2期，2005年八、附錄附錄1. 問題一中文碎片的拼接程序：clearclcfor i=0:18 i=imread( f:matlab7.0upworkb附件1,sprintf(%03d,i),.bmp); ai+1=i(:,72); bi+1=i(:,1);end a=zeros(1,19)-1;b=zeros(1,19)-1;for i=0:18 if bi+1=(zeros(1,1980)+255) a(i+1)=i; end if ai+1=(

31、zeros(1,1980)+255) b(i+1)=i; endend for i=1:19 if a(i)=-1 first=a(i) end if b(i)=-1 last=b(i) endendorder=zeros(1,19)-1;order(1)=8;order(19)=6;c=zeros(19,19)-1;k=zeros(1,19)-1;for i=0:18 if i=6 he=zeros(1,19)-1; for j=0:18 if j=i|j=8 he(j+1)=-1; else he(j+1)=sum(bj+1-ai+1).2); end end xiao=max(he);

32、for j=1:19 if xiao=he(j)&he(j)=-1 xiao=he(j); g=j-1; end end k(i+1)=g; endend for i=2:18 order(i)=k(order(i-1)+1);endorder運(yùn)行結(jié)果為：last = 6first = 8order = columns 1 through 15 8 14 12 15 3 10 2 16 1 4 5 9 13 18 11 columns 16 through 19 7 17 0 6附錄2. 問題一英文文碎片的拼接程序：clearclcfor i=0:18 i=imread(h:b附件2,spri

33、ntf(%03d,i),.bmp); ai+1=i(:,72); bi+1=i(:,1);end a=zeros(1,19)-1;b=zeros(1,19)-1;for i=0:18 if bi+1=(zeros(1,1980)+255) a(i+1)=i; end if ai+1=(zeros(1,1980)+255) b(i+1)=i; endendfor i=1:19 if a(i)=-1 first=a(i) end if b(i)=-1 last=b(i) endend%a,b%得出第一個(gè)為3，最后一個(gè)為4order=zeros(1,19)-1;order(1)=3;order(19

34、)=4;c=zeros(19,19)-1;k=zeros(1,19)-1;for i=0:18 if i=4 he=zeros(1,19)-1; for j=0:18 if j=i|j=3 he(j+1)=-1; else he(j+1)=sum(bj+1-ai+1).2); end end xiao=max(he); for j=1:19 if xiao=he(j)&he(j)=-1 xiao=he(j); g=j-1; end end k(i+1)=g; endendfor i=2:18 order(i)=k(order(i-1)+1);endorder運(yùn)行結(jié)果為：first = 3las

35、t = 4order = columns 1 through 15 3 6 2 7 15 18 11 0 5 1 9 13 10 8 12 columns 16 through 19 14 17 16 4附錄3 問題二中文左右兩列的選擇程序：clearclcj=0;%取最左邊一列圖片for i=0:208 r=imread(h:guosai00guosaib附件3,sprintf(%03d,i),.bmp); i=im2bw(r); a=i(:,1:12);%估計(jì)左邊距占10個(gè)像素點(diǎn) if a=(zeros(180,12)+1) j=j+1; left(j)=i; endendleft %產(chǎn)生11個(gè)圖片left =7 14 29 38 49 61 71 89 94 125 168%取最右邊一列圖片j=0;for i=0:208 r=imread(h:guosai00guos