碎紙片拼接復(fù)原問(wèn)題研究

1、基于旅行商規(guī)劃模型的碎紙片拼接復(fù)原問(wèn)題研究摘要本文分別針對(duì) rsstd(reconstruction of strip shredded textdocument)> rccstd(reconstruction of cross-cut shredded textdocument）和two-sides rccstd三種類型的碎紙片拼接復(fù)原問(wèn)題進(jìn)行了建模與求解算法設(shè)計(jì)。首先我們對(duì)于rsstd問(wèn)題，建立了基于二 值匹配度的tsp模型，并將其轉(zhuǎn)化為線性規(guī)劃模型，利用貪心策略復(fù) 原了該問(wèn)題的中文和英文碎片；然后對(duì)于rccstd問(wèn)題，由于中英文 字的差別，我們分別建立了基于改進(jìn)誤差評(píng)估的漢字拼接模

2、型和基于 文字基線的誤差評(píng)估的英文字拼接模型，并利用誤差評(píng)估匹配算法, 復(fù)原了該問(wèn)題的中文和英文碎片；隨后我們針對(duì)正反兩面的rccstd 問(wèn)題，利用基線的概念將正反兩面分行，轉(zhuǎn)化為rccstd問(wèn)題，并復(fù) 原了該問(wèn)題的英文碎片。最后，我們對(duì)模型的算法和結(jié)果進(jìn)行了檢驗(yàn) 和分析。問(wèn)題一：我們針對(duì)僅縱切的情況，首先將圖像進(jìn)行數(shù)字化處理，轉(zhuǎn)換為了二值圖像，然后得到各圖像的邊緣，并計(jì)算所有碎片與 其他碎片邊緣的匹配程度。然后，根據(jù)兩兩碎片之間的匹配程度建立ttsp模型，并將其劃歸為線性規(guī)劃模型。最終，我們根據(jù)左邊距的信息確定了左邊第一碎片，隨后設(shè)計(jì)了基于匹配度的貪心算法從左向 右得到了所有碎片的拼接復(fù)原結(jié)

3、果。結(jié)果表明我們的方法對(duì)于中英文 兩種情況適用性均較好，且該過(guò)程不需要人工干預(yù)。問(wèn)題二：我們針對(duì)既縱切又橫切的情況，由于中英文的差異性，我們?cè)谶M(jìn)行分行聚類時(shí)應(yīng)采用不同的標(biāo)準(zhǔn)。首先根據(jù)左右邊距 的信息確定了左邊和右邊的碎片，隨后分別利用基于改進(jìn)誤差評(píng)估的 漢字拼接模型和基于文字基線的誤差評(píng)估模型,將剩余的碎片進(jìn)行分 行聚類，然后再利用基于誤差評(píng)估的行內(nèi)匹配算法對(duì)行內(nèi)進(jìn)行了拼 接，最終利用行間匹配算法對(duì)行間的碎片進(jìn)行了再拼接，最終得到了 拼接復(fù)原結(jié)果。對(duì)于拼接過(guò)程中可能出現(xiàn)誤判的情況，我們利用gui 編寫(xiě)了人機(jī)交互的人工干預(yù)界面,用人的直覺(jué)判斷提高匹配的成功率 和完整性。問(wèn)題三：我們針對(duì)正反兩面的

4、情況，首先根據(jù)正反基線信息,分別確定了左右兩邊的碎片，然后利用基線差值將其兩兩聚類，聚類 以后其正反方向也一并確定，隨后我們將其與剩余碎片進(jìn)行分行聚 類，最終又利用行內(nèi)匹配和行間匹配算法得到了最終拼接復(fù)原結(jié)果o 其中，對(duì)于可能出現(xiàn)的誤判情況，我們同樣在匹配算法中使用了基于gui的人機(jī)交互干預(yù)方式，利用人的直覺(jué)提高了結(jié)果的可靠性和完整性。關(guān)鍵字：碎片復(fù)原.tsp、誤差評(píng)估匹配.基線誤差、人工干預(yù)一、問(wèn)題重述破碎文件的拼接復(fù)原工作在傳統(tǒng)上主要需由人工完成，準(zhǔn)確率較 高，但效率很低。特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時(shí)間內(nèi) 完成任務(wù)。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們?cè)噲D開(kāi)發(fā)碎紙片的自動(dòng)拼接 技術(shù)，以提

5、高拼接復(fù)原效率。請(qǐng)討論以下問(wèn)題：1. 對(duì)于給定的來(lái)自同一頁(yè)印刷文字文件的碎紙機(jī)破碎紙片（僅縱切），建立碎紙片拼接復(fù)原模型和算法，并針對(duì)附件1、附件2給出 的中、英文各一頁(yè)文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過(guò)程需要 人工干預(yù)，請(qǐng)寫(xiě)出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。復(fù)原結(jié)果以圖片形式 及表格形式表達(dá)。2. 對(duì)于碎紙機(jī)既縱切又橫切的情形，請(qǐng)?jiān)O(shè)計(jì)碎紙片拼接復(fù)原模型 和算法，并針對(duì)附件3、附件4給出的中、英文各一頁(yè)文件的碎片數(shù) 據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過(guò)程需要人工干預(yù)，請(qǐng)寫(xiě)出干預(yù)方式及干 預(yù)的時(shí)間節(jié)點(diǎn)。3. 上述所給碎片數(shù)據(jù)均為單面打印文件，從現(xiàn)實(shí)情形出發(fā)，還可能 有雙面打印文件的碎紙片拼接復(fù)原問(wèn)題需要解決

6、。請(qǐng)嘗試設(shè)計(jì)相應(yīng)的 碎紙片拼接復(fù)原模型與算法，并就附件5的碎片數(shù)據(jù)給出拼接復(fù)原結(jié) 果。二、問(wèn)題分析破碎文件的拼接復(fù)原工作，傳統(tǒng)人工處理準(zhǔn)確率高，但是效率 低。隨著計(jì)算機(jī)技術(shù)的發(fā)展,本問(wèn)題試圖尋找碎紙片的自動(dòng)拼接方法。 本文的碎片均為矩形，且大小一樣，這就給碎片的拼接帶來(lái)了困難, 因?yàn)殡y以利用碎片的輪廓信息，從而只能利用碎片邊緣的圖像像素信 息來(lái)進(jìn)行拼接。對(duì)于問(wèn)題一，給出了縱切的19條碎紙片，碎片為1980*72,總切線的像素點(diǎn)較多，并且碎紙片的數(shù)量較少，從效率出發(fā)，可以直接 考慮縱切條上的像素統(tǒng)計(jì)信息。為了衡量匹配程度，需要建立誤差評(píng) 估函數(shù)。本文考慮采用tsp模型，將碎紙片作為節(jié)點(diǎn)，將誤差評(píng)

7、估函 數(shù)的值作為節(jié)點(diǎn)之間的權(quán)值，尋找最優(yōu)解。在本問(wèn)題的情況下，中英 文的差別并無(wú)太大影響。對(duì)于問(wèn)題二，由于給出的數(shù)據(jù)是橫縱切的中英文碎片，碎片大小為180*72,各208張。因?yàn)樗榧埰臄?shù)量較多，直接匹配則為np問(wèn) 題中的無(wú)法用多項(xiàng)式解決的問(wèn)題,所以先將行分組匹配完成后再把各 行拼接起來(lái)。本問(wèn)題主要解決：1）如何正確高效分組；2）如何準(zhǔn)確 高效拼接?？紤]到中文和英文在字形和印刷結(jié)構(gòu)上的不同，需要定義 不同的特征向量去描述中文和英文的碎紙片上的信息。文字各行的位 置和間距將作為重要的分組依據(jù)。在問(wèn)題一的基礎(chǔ)上，由于每個(gè)碎紙 片的邊緣像素較少，為了充分利用包含信息，誤差評(píng)估函數(shù)的定義將 會(huì)比問(wèn)題一

8、中更加細(xì)化。行之間的拼接將會(huì)利用邊緣像素和間距匹 配。在本問(wèn)題中，中英文的基線選擇方法將會(huì)有很大不同。對(duì)于問(wèn)題三，在問(wèn)題二的基礎(chǔ)上，加入了正反面信息，碎紙片的形狀并沒(méi)有改變。因此，需要在問(wèn)題二的誤差評(píng)估函數(shù)的基礎(chǔ)上，綜合考慮正反面的匹配誤差。分組的方法與行間的拼接方式與問(wèn)題二基本相同。 綜上所述，本問(wèn)題可以看做是tsp問(wèn)題，碎紙片為 節(jié)點(diǎn)，誤差評(píng)估函數(shù)值為邊的權(quán)值，尋求最優(yōu)解的問(wèn)題。三、模型假設(shè)1.假設(shè)需要復(fù)原的碎片是來(lái)自同一張紙,且對(duì)于該張紙具有完備性。2.假設(shè)同一頁(yè)中，文字的種類、行間距和段落分布情況是相同的。四、模型建立與求解文件碎片拼接主要有兩類不同的技術(shù)標(biāo)準(zhǔn):(1) reconstr

9、uction of strip shredded textdocuments(rsstd)碎片的長(zhǎng)度和原始文件的長(zhǎng)度相等，同時(shí)所有碎紙片都是等寬 的長(zhǎng)方形。(2 ) reconstruction of cross-cut shredded textdocument(rccstd)所有的文件碎片都是長(zhǎng)方形且大小相等,但其長(zhǎng)度小于原始文件的長(zhǎng)度。問(wèn)題一為典型的rsstd問(wèn)題，我們通過(guò)分析碎紙片文字的行特征，建立了一種基于匹配度的求解模型，下面就對(duì)該模型的建立進(jìn)行 詳細(xì)的討論。iltr5.1問(wèn)題1基于匹配度的rsstd問(wèn)題研究為了便于對(duì)圖像數(shù)據(jù)進(jìn)行分析，我們首先需要對(duì)其進(jìn)行數(shù)字化處理以及文字行特征的

10、提取，而后再建立基于匹配度的模型。5. 1. 1圖像數(shù)字化處理圖像的數(shù)字化處理主要包括以下幾個(gè)方面：(1)二值化處理由于縱切碎紙片的長(zhǎng)度特征(碎片長(zhǎng)度與原始文件長(zhǎng)度相等)，其邊 緣像素點(diǎn)信息量豐富。因此我們采取二值化而非灰度對(duì)圖像進(jìn)行了處理，進(jìn)一步簡(jiǎn)化了算法的復(fù)雜度，得到每條碎片像素大小為72 1980(長(zhǎng) 寬)，像素點(diǎn)值取0,1,其中0和1分別表示顏色的黑與白。(2) edge矩陣的建立edgeij為19 2的矩陣，儲(chǔ)存每一條碎片的邊緣像素點(diǎn)信息。 其中i表示碎片的編號(hào)，j=o表示左側(cè)邊緣像素點(diǎn)信息，j=l表示 右側(cè)邊緣像素點(diǎn)信息。例如，edge0,0儲(chǔ)存001號(hào)碎片左側(cè)邊緣 像素點(diǎn)信息。(

11、3) count矩陣的建立根據(jù)edge li, j矩陣，我們可以計(jì)算得到一個(gè)19 2的count i, j矩陣，該矩陣儲(chǔ)存每一條碎片邊緣取值為0的像素點(diǎn)的數(shù)量。例如，count 0,0 =350表示001號(hào)碎片左側(cè)邊緣共有350個(gè)黑色像素點(diǎn)。(4) shred with blank left 的選取根據(jù)count矩陣，若edgei,0二0,那么我們就認(rèn)為該碎片在原始文件中處于類、行間距和段落分布情況是相同的。最左端，即為選取的shred with blank lefto（5）碎片行特征的提取由于原始文件文字行特征明顯，因此我們需要提取碎片的行特征（其具體的原因見(jiàn)匹配度的定義）。首先確定碎片頂端

12、取值為0的像素點(diǎn)的位置，以此作水平線為上邊界，依次向下取w為行寬（這里取w=40 pixels以保證能 容納每一個(gè)文字）直至下邊緣，得到每條碎片的行數(shù)為nl,n2, , nl9；然后取 n=maxnl, n2, , nl9作為最終 確定的行數(shù)，并以該條碎片的行化方式為標(biāo)準(zhǔn)對(duì)每一條碎片進(jìn)行行化；最終每一條碎片被劃分為28行。每條碎片維護(hù)著以下的特征數(shù)據(jù)表:表1碎片i特征數(shù)據(jù)表k12nkl nill ni2l nkr nilr ni2r3 ,2728ni 引，ni271 ni281 ni3r ni27r ni28r其中，k為行號(hào)；nkl為第k行左側(cè)邊緣取值為0的像素點(diǎn)的數(shù)量，nkr為第k行右側(cè)邊緣

13、取值為0的像素點(diǎn)的數(shù)量；nikl 為第i條碎片第k行左側(cè)邊緣取值為0的像素點(diǎn)的數(shù)量。5.1.2匹配度的定義為了衡量?jī)蓚€(gè)碎片之間的匹配程度，我們定義匹配度mi j作為評(píng)價(jià)的標(biāo)準(zhǔn)，其計(jì)算公式如下:"max（% 心）心工叫kk=其中，n為總的行數(shù)（如28n ）； ijkm表示碎片i 和碎片j第k行之間的匹配度；ijm表示碎片i和碎片j之間 的匹配度。這里我們不選擇通過(guò)統(tǒng)計(jì)碎片邊緣總黑色像素點(diǎn)的數(shù)量來(lái)計(jì)算兩碎片之間的匹配度，而是通過(guò)計(jì)算兩碎片行匹 配度來(lái)間接計(jì)算其匹配度，原因在于:若以總的邊緣黑色像素點(diǎn)計(jì)算匹配度，行與行之間的差異性無(wú)法體現(xiàn)，匹配結(jié)果誤差過(guò)大； 通過(guò)行匹配度計(jì)算碎片之間的匹配

14、程度，更加充分的挖掘了碎片邊緣的信息，更為精確。5.1.3.1模型的建立根據(jù)匹配度的定義，我們可以計(jì)算得到19個(gè)碎片兩兩之間邊緣的匹配度，現(xiàn)可將問(wèn)題化簡(jiǎn)為：已知起始碎片和其他碎片之間的匹配度, 尋找一序列使得碎片之間總的匹配度達(dá)到最大。如右圖所示:（1）為簡(jiǎn)化問(wèn)題，我們引入空白碎片0,同樣可計(jì)算得到空白碎片與其他碎片的匹配度;（2）（2）其中節(jié)點(diǎn)表示碎片，有向線段長(zhǎng)度表示費(fèi)用wij,且wij=l-mij,箭頭所指方向表示前一條碎片右側(cè)邊緣到后一條碎片左側(cè)邊緣。如一表示1號(hào)的碎片右側(cè)邊緣與2號(hào)碎片左側(cè)邊緣的費(fèi)用;（3）現(xiàn)要求尋找一條回路遍歷所有的節(jié)點(diǎn)使得費(fèi)用達(dá)到最小。通過(guò)分析，可以發(fā)現(xiàn)這是一典型

15、的tsp問(wèn)題。為解決上述問(wèn)題，我 們建立模型如下:假設(shè)圖中存在ham訂ton回路，有n個(gè)節(jié)點(diǎn)，圖中（i,j）邊的權(quán)重為wij,設(shè)決策變量為xij=l說(shuō)明弧（i, j）進(jìn)入到ham訂ton回路中,則線性規(guī)劃模型可表達(dá)6為：圖1問(wèn)題示意圖圖2算法流程圖min工w內(nèi)on,x = 1(m')ea虧 eo,l,( /)e£only one circle求解該問(wèn)題就是求解該線性規(guī)劃問(wèn)題的最優(yōu)解。5.1.3.2模型的求解為了進(jìn)一步求解上述模型，我們?cè)O(shè)計(jì)的算法如右圖所示:(1) 將所有碎片放入地址池中；(2) 選出左側(cè)全為白色像素點(diǎn)的碎片作為基準(zhǔn)碎片，記為si,并將其從碎片池中剔除；(3)

16、依次計(jì)算si右側(cè)邊緣與地址池中其他碎片sj左側(cè)邊緣的匹配度 mij；(4) 選擇匹配度最大的碎片st作為碎片si的右側(cè)碎片，并將其記為si,從碎片池中剔除該碎片；(5) 重復(fù)(3) (4)步直至碎片池為空。由于該算法使用統(tǒng)計(jì)量構(gòu)建匹配度，很好的避免了中英文之間的差異性，適用性較好，在實(shí)際的應(yīng)用中都收到了很好的效果。最終可以得到附件1與附件2 中碎片的正確序列如下所示：表2附件1排序后碎片序列表序號(hào)12345678910111213141516171819碎片編號(hào)8141215310216145913181171706表3附件2排序后碎片序列表序號(hào)123456789101112131415161

17、71819碎片編號(hào)3627151811051913108121417164通過(guò)求解結(jié)果發(fā)現(xiàn)，我們利用貪心策略求解得到了全局最優(yōu)解, 原因在于匹配度的定義較好。同時(shí)由于碎片兩側(cè)提供的信息量大，很 好的避免了中英文之間的差異性。若碎片規(guī)格變小，信息量減少，中 英文之間差異性的討論顯得十分有必要。5.2問(wèn)題2基于誤差評(píng)估的rccstd問(wèn)題研究由于中英文的字存在顯著的差異性，對(duì)算法的設(shè)計(jì)有很大影響, 因此我們需要對(duì)它們進(jìn)行具體的討論。如右圖所示，我們可以分析 得到如下的差異性特征：(1)中英文的字行存在顯著的差異性，中 文字結(jié)構(gòu)復(fù)雜，筆畫(huà)繁多，無(wú)法確定固定的基準(zhǔn)線;(2) 英文字印刷格式固定，一般為“

18、四線三格”的形式，容易通過(guò)基準(zhǔn)線來(lái)確定具體字母的位置信息?；谝陨戏治?，我們需要針對(duì)中英文設(shè)計(jì)不同的模型進(jìn)行碎紙片的拼接復(fù)原。下面首先建立文字的 拼接復(fù)原模型。521基于誤差評(píng)估的漢字拼接模型5.2.1.1碎片的逐行分組(1)逐行分組原因分析首先參考問(wèn)題一中的算法提取位于原始文件左右邊界位置的22塊碎片，以此為基礎(chǔ)將所有碎片分為22組，而非按列分組或分為11 組，主要原因如下： 若按列分組，由于碎片上下邊緣信息量少，分組誤差較 大，不可??； 若以原始文件左側(cè)邊緣的11塊碎片為基礎(chǔ)將所有碎片分為11組，可能存在以下的問(wèn)題：如右圖所示，014 塊碎片為原始文件的左側(cè)邊緣碎片，128塊碎片為其右 側(cè)

19、碎片。但由于014塊碎片處于一自然段的開(kāi)始位置，上半部分基本為空白，而128塊碎片上半部分信息豐 富,兩者匹配失敗率高，很可能導(dǎo)致該組元素個(gè)數(shù)為0。 因此我們將碎片分為22組，同時(shí)考慮左側(cè)邊緣與右側(cè) 邊緣的信息，分組效率高且準(zhǔn)確率高。（2）分組標(biāo)準(zhǔn)的確定我們確立四個(gè)參數(shù)dtb, dbb, dtw, dbw其意義如右圖所示。其中dtb, dbb代表由上下邊緣至中間像素點(diǎn)由黑過(guò)度到白的距 ；dtw,dbw代表上下邊緣至中間像素點(diǎn)由白過(guò)度到黑的距離。根據(jù)上述定義，對(duì)于每一幅圖像，首先判斷其上下邊緣的過(guò)度 情況，由此可以確定上下邊緣的兩個(gè)參數(shù)。那么我們認(rèn)為若兩 個(gè)碎片具有相同的參數(shù)，如同樣為dtb和d

20、bw,同時(shí)相同參數(shù) 之間的差值不超過(guò)4pixels,即:| dlb -db < a pixels 且 d慶 一 dj 5 4 pixeis那么，我們認(rèn)為兩碎片在同一組內(nèi)。最終可以得到分組情況如下表所示:表4分組情況表組號(hào)組內(nèi)成員編號(hào)組號(hào)組內(nèi)成員編號(hào)17, 68, 175, 0, 126, 174, 56, 53, 208, 158, 138, 137, 451218, 195214133631443438. 189, 88. 103, 35, 24. 148, 167, 161,46， 122, 130, 1931559. 37, 98, 104, 10, 75, 48. 171，207

21、, 92, 111, 55, 180. 5, 172,64. 44, 201549. 54. 28. 192, 22, 129- 190. 186, 118,143. 65, 57, 2 911660 205， 85, 15266b 116. 67, 162, 79, 99. 63> 20 72, 6,1774, 8, 25, 969. 96, 131, 78. 163, 52, 19, 17777】18123, 152, 194, 207, 154, 119,146, 108. 185, 4, 155, 40 102,10b 140, 1138891914b 188, 12994, 4

22、2, 144. 97, 34, 77, 127, 90, 84. 121.136, 47， 149, 164, 183， 112, 12420145， 181 204 182 16, 110. 66184, 13, 106, 109, 150. 139. 187,197, 157, 21, 1731012521176. 115, 12, 3, 134， 135, 82.39. 169. 31, 203, 199- 51 159,128 107, 73, 16011168. 142 147, 76, 50, 23, 120. 87, 179,62. 100, 19b 4b 2622196, 32

23、, 93, 153， 70, 166由上表可知，由于某些碎片的特殊性，仍不能歸入任何一組。這些碎片有 1, 15, 17, 27, 30, 33, 58, 80, 81, 83, 86, 95, 105, 114, 117, 132, 133, 156, 165, 170, 178, 198, 200, 202o我們可以將他們放入碎片池中，這一部分碎片后續(xù)將進(jìn)行單獨(dú)的處理。5.2.1.2組內(nèi)碎片匹配算法的設(shè)計(jì)評(píng)價(jià)兩塊碎片拼接的好壞程度，我們用誤差評(píng)估函數(shù)來(lái)描述。由題可知，每頁(yè)被分為了 11 19個(gè)碎片，每個(gè)碎片具有同樣的規(guī)格。那么，就有ijhh ,表示兩碎片的高度相等。我們定義誤差評(píng)估函數(shù)(j

24、hcij為:= f 匂億/j)>:=31 if efh(ij. y)>r/'/)珂0 otherwise4(z, h y) =10.7(片億 y) -v(h y) 4-0.b(vrg；y + l)-vz(/,y + l) + 0.b(vr(?；y-l)-vz(/,y-l) + 0.05 (vr(i, y + 2)-vl(j,y + 2) +0.05 (vr(z,y-2)-v( j, y-2)|其中，每個(gè)像素點(diǎn)以8位數(shù)值表示，有：vz(/, y) vr(z, y) g 0,.,255 with <y<h for the left and riht edge如上圖所

25、示，我們將一碎片邊緣等分為三分。在考慮像素點(diǎn)y 時(shí)，對(duì)其鄰域y+1, y+2, y-1, y-2共5個(gè)像素點(diǎn)進(jìn)行分析，并 賦予不同的權(quán)重，那么可以分別計(jì)算得到三段的誤差評(píng)估函數(shù) 為 123q/,),g)hhhcijcijcijo參考問(wèn)題一，設(shè)計(jì)組內(nèi)匹配算法如下：(1) 將組內(nèi)碎片以及剩余未分組的碎片放入碎片池中；(2) 以左側(cè)全為白色像素點(diǎn)的碎片為基準(zhǔn)碎片，記為si,并將其從碎片池中剔除;(3) 依次計(jì)算si右側(cè)邊緣與地址池中其他碎片sj左側(cè)邊緣的誤差評(píng)估值 123g),q,(,)hhhcijcijcij；(4)依次計(jì)算碎片si與池中其他碎片sj的相對(duì)誤差:1/)=工k=1%仏/)一廣)%(z

26、，/)其中，j表示當(dāng)前比較的碎片，j為碎片池中其他的碎片，k表 示上下三段，如123hlh2h3 ；(5)選取相對(duì)偏差最小的碎片，且時(shí)，將該碎片作為碎片si的右側(cè)碎片，并記該碎片為si,將其從碎片池中刪除；(6)重復(fù)(3)(5)步18次直至結(jié)束。1222組可以根據(jù)同樣的算法進(jìn)行碎片的拼接復(fù)原。在此過(guò)程中由于最小相對(duì)誤差的碎片存在多個(gè)，計(jì)算機(jī)很難進(jìn)行取舍。因此，在程序中，我們?cè)O(shè)計(jì)了人機(jī)交互的界面，當(dāng)遇到此類情況時(shí)，通過(guò)人工干預(yù)的方式來(lái)選擇最佳的碎 片。最后，可以得到22個(gè)拼接好的片段。5. 2. 1.3組間片段的匹配組間片段的匹配，我們主要依據(jù)以下兩點(diǎn)原則:(1)若兩個(gè)片段在同一行，那么兩個(gè)片段

27、內(nèi)碎片的數(shù)量應(yīng)當(dāng)互補(bǔ)(和為 19)；(2)以一個(gè)片段為基礎(chǔ)，計(jì)算其與右側(cè)片段的相對(duì)偏差，相對(duì)偏差越小，匹配程度越高。根據(jù)以上原則，最終可以得到左右兩側(cè)片段按行匹配的結(jié)果如下圖所示:表5 22組片段按行匹配情況表行號(hào)1234567891011左側(cè)片段組號(hào)1734567891011右側(cè)片段組號(hào)av av21157419131618142012注：這里行號(hào)不表示該行在原始文件中的順序。5214行間匹配 類似于組內(nèi)碎片匹配的算法，通過(guò)計(jì)算行片段之 間上下邊緣的誤差評(píng)估值從q),最終可以得到行片段的正確 序列。行誤差評(píng)估值2的計(jì)算公式如下:w 24(6q)=工無(wú))工=35.3問(wèn)題三two-sides rccstd問(wèn)題研究通過(guò)對(duì)問(wèn)題三的分析，發(fā)現(xiàn)問(wèn)題的解決方案基本與問(wèn)題二類似，但