葡萄酒的評價

1、碎紙片的拼接復原摘要本文利用Manhattan距離，聚類分析，圖像處理等方法解決了碎紙片的拼接復原問題。由于碎紙機產(chǎn)生的碎紙片是邊緣規(guī)則且等大的矩形，此時碎紙片拼接方法就不能利用碎片邊緣的尖角特征等基于邊界幾何特征的拼接方法，而要利用碎片內(nèi)的字跡斷線或碎片內(nèi)的文字位置搜索與之匹配的相鄰碎紙片。拼接碎片前利用數(shù)學軟件MATLAB軟件對碎片圖像進行數(shù)據(jù)化處理，得到對應的像素矩陣，后設置閾值對像素矩陣進行二值化處理，得到相應的0-1矩陣。下面分別對三個問題的解決方法和算法實現(xiàn)做簡單的闡述：問題一，分別對附件1和附件2的碎片數(shù)據(jù)進行處理得到相應的0-1矩陣，依次計算某個0-1矩陣最右邊一列組成向量與其

2、他所有0-1矩陣的最左邊向量的Manhattan距離，可以得到某個最小距離值、說明最小距離值對應的碎片是可與基準碎片拼接的，最終得到碎片拼接完整的圖像。問題二，同樣對于附件3和附件4中的碎片數(shù)據(jù)進行處理得到相應的數(shù)值矩陣，并計算得到每個碎片頂部空白高度和文字高度，即指每行像素點都為255的行數(shù)、一行中存在像素點為非255的行數(shù)，根據(jù)空白高度和文字高度對碎片進行聚類分類，聚類閥值取3像素，得到11組像素矩陣，進而得到11類可能在同一行的碎片類。其中對附件4中的英文的處理中，我們還采用水平像素投影累積的方法，進一步分類出可能在同一行的碎片類。用問題一的方法，計算Manhattan距離可以對每一類碎

3、片按次序排列好，得到11行已經(jīng)排列好的碎片，再應用曼哈頓距離在豎直方向上進行聚合得到完整的圖像。問題三，首先，對于附件5中的碎片數(shù)據(jù)我們采用正反相接，本文將b面最左邊的一列像素拼接到a面最右邊的一列像素的下面，構(gòu)成360×1的向量，再把其他的碎片采用相同的辦法得到360×1的向量，再用問題一的方法，計算出各碎片之間的Manhattan距離。其次，根據(jù)每個碎片頂部的空白高度或者文字高度對碎片進行區(qū)間分類，得到22組矩陣，然后應用曼哈頓距離將得到的22組矩陣聚成兩類，每類各包含兩面的11組矩陣，最后利用Manhattan距離在豎直方向上進行聚合得到完整的圖像。本文最后，我們根據(jù)

4、算法的效率實現(xiàn)進行了改進和優(yōu)化，實現(xiàn)算法的移植性、靈活性、運行效率等得以提升。關鍵詞：曼哈頓距離，聚類分析，二值化處理二、問題分析我們從附件中的碎片數(shù)據(jù)可知由于碎紙機產(chǎn)生的碎紙片邊緣是規(guī)則的，此時碎紙片計算機拼接方法就不能利用碎片邊緣的尖點特征、尖角特征、面積特征等基于邊界幾何特征的拼接方法，而要利用碎片內(nèi)的字跡斷線或碎片內(nèi)的文字內(nèi)容是否匹配搜索與之匹配的相鄰碎紙片并進行拼接。首先，我們對碎片內(nèi)圖像進行數(shù)據(jù)化處理，得到對應的像素值矩陣；然后，我們設置閾值對像素值矩陣進行二值化處理得到相應的數(shù)值矩陣；最后，由于曼哈頓距離公式計算快、數(shù)值小，數(shù)值矩陣與數(shù)值矩陣之間應用最小曼哈頓距離對碎紙片進行拼接

5、復原。問題一中碎紙機破碎紙片只有縱切，每頁紙被切為19條碎片，經(jīng)過處理可以得到19個數(shù)值矩陣。對于每個數(shù)值矩陣，我們依次取出最左邊一列從上至下各格的值組成一個向量，同樣我們依次取出最右邊一列從上至下各格的值組成一3個向量。計算出每一數(shù)值矩陣的左邊向量與所有非同源數(shù)值矩陣的右邊向量的曼哈頓距離，再將得到的距離值進行排序，當某個距離值最小時、說明相應的左邊向量與右邊向量的匹配率最大，則該距離對應的左、右邊認為是可拼接的。若得到的最小距離值不止一個，則此時需要進行人工干預。問題二是對碎紙機既縱切又橫切的情形進行討論，比問題一多了橫切條件，此時每頁紙被切為209個碎片。首先，我們利用文件最左邊碎片與最

6、上面碎片的特殊性對這209個碎片進行聚類，得到兩類特殊的碎片，分別是文件最左邊一列碎片和最上面一行碎片，然后類似于問題一的處理方法，應用最小曼哈頓距離對每一類碎片按正確順序拼接，此后對其余碎片再應用最小曼哈頓距離逐一進行拼接，直至剩余所有的碎片都拼接上。問題三中，題目要求考慮雙面打印文件的碎紙拼接復原問題的解決方案，此時每頁紙雖然也是被切為209個碎片，但每個碎片卻有正反兩面，因此經(jīng)過處理得到418個數(shù)值矩陣，此時我們分別對每一面各自進行類似問題一的處理，然后綜合每一面的聚類情況再應用最小曼哈頓距離對雙面碎紙片進行拼接復原。 三、模型假設1. 假設碎紙機破碎紙片（縱切或橫切）得到的碎紙片是規(guī)則

7、且邊緣是整齊的等大的矩形；2.假設我們對文檔碎紙片拼接復原不考慮碎片邊緣的尖點特征,尖角特征、面積特征等基于邊界幾何特征；3.假設附件中給出的所有中、英文文件中的文字排版是按標準格式排版的。4.假設附件中給出的所有中、英文字符都是統(tǒng)一格式，且內(nèi)容為普通文章。四、符號說明 序號 符號 符號說明 1 iA 數(shù)值矩陣 2 iX 數(shù)值矩陣iA的最左邊列向量 3 iY 數(shù)值矩陣iA的最右邊列向量 4 (,dxi,dyi) 曼哈頓距離 5 T 隸屬函數(shù)中的閥值五、模型建立與求解 5.1 問題一（曼哈頓距離） Ø 模型一的建立 題目要求對于給定的來自同一頁印刷文字文件的碎紙機破碎紙片（僅縱切）建立

8、碎紙片拼接復原模型和算法，并且要對中、英文各一頁文件的碎片數(shù)據(jù)分別進行拼接復原。首先，我們利用數(shù)學軟件MATLAB軟件將19條碎片數(shù)據(jù)化，得到19個像素值矩陣，像素值的變化范圍是從0變化到255，此時我們設置127t=為閾值對像素值矩陣進行二值化處理，當矩陣某位置像素值小于等于t時，則將對應位置的數(shù)值設為0；當矩陣某位置像素值大于t時，則將對應位置的數(shù)值設為127。這樣我們就得到19個二值化了的數(shù)值矩陣iA，對于每個數(shù)值矩陣iA，我們依次取出最左邊一列從上至下各格的值組成一個向量，記為iX，同樣的我們依次取出最右邊一列從上至下各格的值組成一個向量，記為iY。計算出每一數(shù)值矩陣的左邊向量與所有非

9、同源數(shù)值矩陣的右邊向量的曼哈頓距離d(Xi,Yi)。 模型一的求解對于得到的向量Xi=(xi1,xi2,.,xik)T (k=1.2.m)=和向量Yi=(yi1,yi2,.,yik)T (k=1,2,.,n)=，兩向量的曼哈頓距離為D(Xi,Yi)= (i.j=1,2,.,m且ij)?？汕蟪龈郊?碎片與碎片之間的曼哈頓距離，如下表所示。編號0123456789101112131415161718編號6416105981714132715181231011距離10211748128811130159112120828434777897124102105從而可得到附件1碎片序號按復原后順序如下表所

10、示。8141215310216145913181171706同法課求出附件2的曼哈頓距離如下表編號0123456789101112131415161718編號5976312151213801410171841611距離966582102071671208712882547513310754935290得到附件2碎片序號復原順序如下表36271518110519131081214171645.2 問題二（Manhattan距離）模型二的建立在中文文件中，兩個連續(xù)的漢字中間的空白間隔所占像素寬度與其左邊或者6右邊的漢字所占像素寬度的比值最大的約為2/13，則對于每一行文字，碎紙機縱切未切到文字的概

11、率為2/13，對于每兩行文字碎紙機縱切未切到文字的概率為4/169，而對于每三行文字碎紙機縱切未切到文字的概率更小，可以忽略不計，所以對于總共209個碎片，每個碎片上面的文字至少有兩行（碎片上不完整的一行也算一行），所以出現(xiàn)某個碎片上面的文字完全沒被碎紙機切割到（即文字完整無缺）的概率至多為4/169，我們把這樣的碎片稱之為干擾碎片。我們知道，整篇文件的最上面一行字的上邊緣是空白的，我們可以利用此特殊性對209個碎紙片進行聚類，可以得到一個特殊的類，即碎紙片上邊緣為空白的類，此類碎紙片個數(shù)大于等于11；出現(xiàn)個數(shù)大于11的情形即為混入上面提到的干擾碎片，此概率最大不超過4/169，可知此類碎紙片

12、應該拼接在文件最上面一行，應用最小曼哈頓距離對此類碎片按正確順序拼接。同理可聚類出另一個特殊的類，即碎紙片左邊緣為空白、拼接在文件最左邊一列的類，并且也應用最小曼哈頓距離對此類碎片按正確順序拼接。然后以此拼接好的第一行和第一列碎片為基準，再應用最小曼哈頓距離拼接其余剩下的碎片，最后拼接復原出原中文文件。在英文文件中，一個英文單詞中兩個連續(xù)的英文字母中間的空白間隔所占像素寬度與其左邊或者右邊的英文字母所占像素寬度的比值最大的約為1/11，則對于每一行英文單詞，碎紙機縱切未切到英文單詞的概率為1/11，對于每兩行英文單詞碎紙機縱切未切到英文單詞的概率為1/121，而對于每三行英文單詞碎紙機縱切未切

13、到英文單詞的概率為1/1331，然后同上述中文文件的分析過程可知，此時對拼接在文件最左邊一列歸類時混入上面提到的干擾碎片的概率最大不超過1/1331,最后拼接復原出原英文文件。文件的最上面一行字的上邊緣是空白的，我們可以利用此特殊性對209個碎紙片進行聚類，可以得到一個特殊的類，即碎紙片上邊緣為空白的類，此類碎紙片個數(shù)大于等于11；出現(xiàn)個數(shù)大于11的情形即為混入上面提到的干擾碎片，此概率最大不超過4/169，可知此類碎紙片應該拼接在文件最上面一行，應用最小曼哈頓距離對此類碎片按正確順序拼接。同理可聚類出另一個特殊的類，即碎紙片左邊緣為空白、拼接在文件最左邊一列的類，并且也應用最小曼哈頓距離對此

14、類碎片按正確順序拼接。然后以此拼接好的第一行和第一列碎片為基準，再應用最小曼哈頓距離拼接其余剩下的碎片，最后拼接復原出原中文文件。在英文文件中，一個英文單詞中兩個連續(xù)的英文字母中間的空白間隔所占像素寬度與其左邊或者右邊的英文字母所占像素寬度的比值最大的約為1/11，則對于每一行英文單詞，碎紙機縱切未切到英文單詞的概率為1/11，對于每兩行英文單詞碎紙機縱切未切到英文單詞的概率為1/121，而對于每三行英文單詞碎紙機縱切未切到英文單詞的概率為，然后同上述中文文件的分析過程可知，此時列歸類時混入上面提到的干擾碎片的概率最大不超過，最后拼接復原出原英文文件。模型二的求解我們利用SPSS軟件根據(jù)每個碎

15、片頂部空白高度或者文字高度的不同，應用聚類分析方法將碎片聚成11類.結(jié)合聚類圖，可得出附件3的亂序矩陣，如下表所示。 6、 模型的評價與推廣1.模型的評價 對于問題一，由于題目中給的樣本較為簡單，所以模型一能很好的解決附件1、附件2給出的中、英文文件碎紙片拼接復原問題。對于問題二，模型二也能較好的解決問題，但模型二也有不足之處，比如模型1.3二只考慮根據(jù)每個碎片頂部的空白高度和文字高度對碎片進行區(qū)間分類，分為11組矩陣。而沒有綜合考慮每個碎片頂部與底部的空白高度和文字高度對碎片進行區(qū)間分類，因此分類準確率降低。2. 模型的推廣 我們建立的模型在處理碎紙片較大且碎紙片數(shù)量不是很多的時候，模型可以較好的解決問題，但在實際應用中，通常會涉及碎紙片被切割得很細很小，并且要對大量碎紙片數(shù)據(jù)進行管理和處理工作。所以我們要進一步優(yōu)化算法和程序結(jié)構(gòu)，改善模型，真正建立起快速有效的計算機輔助碎紙片自動拼接復原模型，從而才能將此模型廣泛地應用到我們的實際生活中。七、參考文獻1. 張翠. 基于點線的文檔圖片數(shù)字水印與碎片拼接D. 青島:中國海洋大學, 2011. 26-34。2. 張艷. 圖像拼接技術(shù)在文檔圖像扭曲識別中的應用與研究D. 北京:北方工業(yè)大學, 2011. 23-29。3. 賈海燕, 朱