葡萄酒的评价

1、碎纸片的拼接复原摘要本文利用Manhattan距离，聚类分析，图像处理等方法解决了碎纸片的拼接复原问题。由于碎纸机产生的碎纸片是边缘规则且等大的矩形，此时碎纸片拼接方法就不能利用碎片边缘的尖角特征等基于边界几何特征的拼接方法，而要利用碎片内的字迹断线或碎片内的文字位置搜索与之匹配的相邻碎纸片。拼接碎片前利用数学软件MATLAB软件对碎片图像进行数据化处理，得到对应的像素矩阵，后设置阈值对像素矩阵进行二值化处理，得到相应的0-1矩阵。下面分别对三个问题的解决方法和算法实现做简单的阐述：问题一，分别对附件1和附件2的碎片数据进行处理得到相应的0-1矩阵，依次计算某个0-1矩阵最右边一列组成向量与其

2、他所有0-1矩阵的最左边向量的Manhattan距离，可以得到某个最小距离值、说明最小距离值对应的碎片是可与基准碎片拼接的，最终得到碎片拼接完整的图像。问题二，同样对于附件3和附件4中的碎片数据进行处理得到相应的数值矩阵，并计算得到每个碎片顶部空白高度和文字高度，即指每行像素点都为255的行数、一行中存在像素点为非255的行数，根据空白高度和文字高度对碎片进行聚类分类，聚类阀值取3像素，得到11组像素矩阵，进而得到11类可能在同一行的碎片类。其中对附件4中的英文的处理中，我们还采用水平像素投影累积的方法，进一步分类出可能在同一行的碎片类。用问题一的方法，计算Manhattan距离可以对每一类碎

3、片按次序排列好，得到11行已经排列好的碎片，再应用曼哈顿距离在竖直方向上进行聚合得到完整的图像。问题三，首先，对于附件5中的碎片数据我们采用正反相接，本文将b面最左边的一列像素拼接到a面最右边的一列像素的下面，构成360×1的向量，再把其他的碎片采用相同的办法得到360×1的向量，再用问题一的方法，计算出各碎片之间的Manhattan距离。其次，根据每个碎片顶部的空白高度或者文字高度对碎片进行区间分类，得到22组矩阵，然后应用曼哈顿距离将得到的22组矩阵聚成两类，每类各包含两面的11组矩阵，最后利用Manhattan距离在竖直方向上进行聚合得到完整的图像。本文最后，我们根据

4、算法的效率实现进行了改进和优化，实现算法的移植性、灵活性、运行效率等得以提升。关键词：曼哈顿距离，聚类分析，二值化处理二、问题分析我们从附件中的碎片数据可知由于碎纸机产生的碎纸片边缘是规则的，此时碎纸片计算机拼接方法就不能利用碎片边缘的尖点特征、尖角特征、面积特征等基于边界几何特征的拼接方法，而要利用碎片内的字迹断线或碎片内的文字内容是否匹配搜索与之匹配的相邻碎纸片并进行拼接。首先，我们对碎片内图像进行数据化处理，得到对应的像素值矩阵；然后，我们设置阈值对像素值矩阵进行二值化处理得到相应的数值矩阵；最后，由于曼哈顿距离公式计算快、数值小，数值矩阵与数值矩阵之间应用最小曼哈顿距离对碎纸片进行拼接

5、复原。问题一中碎纸机破碎纸片只有纵切，每页纸被切为19条碎片，经过处理可以得到19个数值矩阵。对于每个数值矩阵，我们依次取出最左边一列从上至下各格的值组成一个向量，同样我们依次取出最右边一列从上至下各格的值组成一3个向量。计算出每一数值矩阵的左边向量与所有非同源数值矩阵的右边向量的曼哈顿距离，再将得到的距离值进行排序，当某个距离值最小时、说明相应的左边向量与右边向量的匹配率最大，则该距离对应的左、右边认为是可拼接的。若得到的最小距离值不止一个，则此时需要进行人工干预。问题二是对碎纸机既纵切又横切的情形进行讨论，比问题一多了横切条件，此时每页纸被切为209个碎片。首先，我们利用文件最左边碎片与最

6、上面碎片的特殊性对这209个碎片进行聚类，得到两类特殊的碎片，分别是文件最左边一列碎片和最上面一行碎片，然后类似于问题一的处理方法，应用最小曼哈顿距离对每一类碎片按正确顺序拼接，此后对其余碎片再应用最小曼哈顿距离逐一进行拼接，直至剩余所有的碎片都拼接上。问题三中，题目要求考虑双面打印文件的碎纸拼接复原问题的解决方案，此时每页纸虽然也是被切为209个碎片，但每个碎片却有正反两面，因此经过处理得到418个数值矩阵，此时我们分别对每一面各自进行类似问题一的处理，然后综合每一面的聚类情况再应用最小曼哈顿距离对双面碎纸片进行拼接复原。 三、模型假设1. 假设碎纸机破碎纸片（纵切或横切）得到的碎纸片是规则

7、且边缘是整齐的等大的矩形；2.假设我们对文档碎纸片拼接复原不考虑碎片边缘的尖点特征,尖角特征、面积特征等基于边界几何特征；3.假设附件中给出的所有中、英文文件中的文字排版是按标准格式排版的。4.假设附件中给出的所有中、英文字符都是统一格式，且内容为普通文章。四、符号说明 序号 符号 符号说明 1 iA 数值矩阵 2 iX 数值矩阵iA的最左边列向量 3 iY 数值矩阵iA的最右边列向量 4 (,dxi,dyi) 曼哈顿距离 5 T 隶属函数中的阀值五、模型建立与求解 5.1 问题一（曼哈顿距离） Ø 模型一的建立 题目要求对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切）建立

8、碎纸片拼接复原模型和算法，并且要对中、英文各一页文件的碎片数据分别进行拼接复原。首先，我们利用数学软件MATLAB软件将19条碎片数据化，得到19个像素值矩阵，像素值的变化范围是从0变化到255，此时我们设置127t=为阈值对像素值矩阵进行二值化处理，当矩阵某位置像素值小于等于t时，则将对应位置的数值设为0；当矩阵某位置像素值大于t时，则将对应位置的数值设为127。这样我们就得到19个二值化了的数值矩阵iA，对于每个数值矩阵iA，我们依次取出最左边一列从上至下各格的值组成一个向量，记为iX，同样的我们依次取出最右边一列从上至下各格的值组成一个向量，记为iY。计算出每一数值矩阵的左边向量与所有非

9、同源数值矩阵的右边向量的曼哈顿距离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)。可求出附件1碎片与碎片之间的曼哈顿距离，如下表所示。编号0123456789101112131415161718编号6416105981714132715181231011距离10211748128811130159112120828434777897124102105从而可得到附件1碎片序号按复原后顺序如下表所

10、示。8141215310216145913181171706同法课求出附件2的曼哈顿距离如下表编号0123456789101112131415161718编号5976312151213801410171841611距离966582102071671208712882547513310754935290得到附件2碎片序号复原顺序如下表36271518110519131081214171645.2 问题二（Manhattan距离）模型二的建立在中文文件中，两个连续的汉字中间的空白间隔所占像素宽度与其左边或者6右边的汉字所占像素宽度的比值最大的约为2/13，则对于每一行文字，碎纸机纵切未切到文字的概

11、率为2/13，对于每两行文字碎纸机纵切未切到文字的概率为4/169，而对于每三行文字碎纸机纵切未切到文字的概率更小，可以忽略不计，所以对于总共209个碎片，每个碎片上面的文字至少有两行（碎片上不完整的一行也算一行），所以出现某个碎片上面的文字完全没被碎纸机切割到（即文字完整无缺）的概率至多为4/169，我们把这样的碎片称之为干扰碎片。我们知道，整篇文件的最上面一行字的上边缘是空白的，我们可以利用此特殊性对209个碎纸片进行聚类，可以得到一个特殊的类，即碎纸片上边缘为空白的类，此类碎纸片个数大于等于11；出现个数大于11的情形即为混入上面提到的干扰碎片，此概率最大不超过4/169，可知此类碎纸片

12、应该拼接在文件最上面一行，应用最小曼哈顿距离对此类碎片按正确顺序拼接。同理可聚类出另一个特殊的类，即碎纸片左边缘为空白、拼接在文件最左边一列的类，并且也应用最小曼哈顿距离对此类碎片按正确顺序拼接。然后以此拼接好的第一行和第一列碎片为基准，再应用最小曼哈顿距离拼接其余剩下的碎片，最后拼接复原出原中文文件。在英文文件中，一个英文单词中两个连续的英文字母中间的空白间隔所占像素宽度与其左边或者右边的英文字母所占像素宽度的比值最大的约为1/11，则对于每一行英文单词，碎纸机纵切未切到英文单词的概率为1/11，对于每两行英文单词碎纸机纵切未切到英文单词的概率为1/121，而对于每三行英文单词碎纸机纵切未切

13、到英文单词的概率为1/1331，然后同上述中文文件的分析过程可知，此时对拼接在文件最左边一列归类时混入上面提到的干扰碎片的概率最大不超过1/1331,最后拼接复原出原英文文件。文件的最上面一行字的上边缘是空白的，我们可以利用此特殊性对209个碎纸片进行聚类，可以得到一个特殊的类，即碎纸片上边缘为空白的类，此类碎纸片个数大于等于11；出现个数大于11的情形即为混入上面提到的干扰碎片，此概率最大不超过4/169，可知此类碎纸片应该拼接在文件最上面一行，应用最小曼哈顿距离对此类碎片按正确顺序拼接。同理可聚类出另一个特殊的类，即碎纸片左边缘为空白、拼接在文件最左边一列的类，并且也应用最小曼哈顿距离对此

14、类碎片按正确顺序拼接。然后以此拼接好的第一行和第一列碎片为基准，再应用最小曼哈顿距离拼接其余剩下的碎片，最后拼接复原出原中文文件。在英文文件中，一个英文单词中两个连续的英文字母中间的空白间隔所占像素宽度与其左边或者右边的英文字母所占像素宽度的比值最大的约为1/11，则对于每一行英文单词，碎纸机纵切未切到英文单词的概率为1/11，对于每两行英文单词碎纸机纵切未切到英文单词的概率为1/121，而对于每三行英文单词碎纸机纵切未切到英文单词的概率为，然后同上述中文文件的分析过程可知，此时列归类时混入上面提到的干扰碎片的概率最大不超过，最后拼接复原出原英文文件。模型二的求解我们利用SPSS软件根据每个碎

15、片顶部空白高度或者文字高度的不同，应用聚类分析方法将碎片聚成11类.结合聚类图，可得出附件3的乱序矩阵，如下表所示。 6、 模型的评价与推广1.模型的评价 对于问题一，由于题目中给的样本较为简单，所以模型一能很好的解决附件1、附件2给出的中、英文文件碎纸片拼接复原问题。对于问题二，模型二也能较好的解决问题，但模型二也有不足之处，比如模型1.3二只考虑根据每个碎片顶部的空白高度和文字高度对碎片进行区间分类，分为11组矩阵。而没有综合考虑每个碎片顶部与底部的空白高度和文字高度对碎片进行区间分类，因此分类准确率降低。2. 模型的推广 我们建立的模型在处理碎纸片较大且碎纸片数量不是很多的时候，模型可以较好的解决问题，但在实际应用中，通常会涉及碎纸片被切割得很细很小，并且要对大量碎纸片数据进行管理和处理工作。所以我们要进一步优化算法和程序结构，改善模型，真正建立起快速有效的计算机辅助碎纸片自动拼接复原模型，从而才能将此模型广泛地应用到我们的实际生活中。七、参考文献1. 张翠. 基于点线的文档图片数字水印与碎片拼接D. 青岛:中国海洋大学, 2011. 26-34。2. 张艳. 图像拼接技术在文档图像扭曲识别中的应用与研究D. 北京:北方工业大学, 2011. 23-29。3. 贾海燕, 朱