葡萄酒的評(píng)價(jià)

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

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

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

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

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

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

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

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

9、同源數(shù)值矩陣的右邊向量的曼哈頓距離d(Xi,Yi)。 模型一的求解對(duì)于得到的向量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)?？汕蟪龈郊?碎片與碎片之間的曼哈頓距離，如下表所示。編號(hào)0123456789101112131415161718編號(hào)6416105981714132715181231011距離10211748128811130159112120828434777897124102105從而可得到附件1碎片序號(hào)按復(fù)原后順序如下表所

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

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

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

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

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

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