2013年9月B题数模论文

碎纸片的拼接复原摘要关键词：问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上的接复原工作需由人工完成，虽然准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。本题要求讨论以下问题：1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2.对于碎纸机既纵切又横切的情形，要求我们设计拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，写出干预方式及干预的时间节点。复原结果表达要求同上。3.上述所给碎片数据均为单面打印文件。但是，从现实情形出发，还可能有双面打印文件。附件5给出了一页英文印刷文字双面打印文件的碎片数据。我们需要尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。问题分析本题需要解决的三个问题是层层递进、逐步深入的。（1）单面打印、仅纵切碎片的复原分析第一问复原对象为单面打印、仅纵切的规则矩形碎片，由于很难提取到足够的差异化几何特征，故无法像不规则碎片那样利用碎片角点、曲率、形状等几何特征进行复原。考虑从数字图像处理的角度出发，在碎片边缘，根据碎片内容、以像素为处理对象，进行碎片特征信息的提取。首先，将附件给出的灰度图二值化，得到对应的二值图。进而提取碎片左、右两侧边缘灰度值，则每张图片可以得到两个特征列向量。将这些特征向量两两比较，计算匹配度，则把匹配度最大的两个碎片进行配对。如此反复，可将19个碎片全部拼接完成。解决思路如下图所示：图一问题一解决思路（2）单面打印、既纵切又横切碎片的复原分析第二问复原对象为单面打印、既纵切又横切的碎片。据此特点，考虑先拼接出最左边第一列碎片，接下来从第一行开始，逐行向下拼接。鉴于第二问碎片数量及特征维度较第一问有所增加，可以预计，当碎片数量增大到一定程度时，对同一碎片，问题一模型代码将可能返回不止一个匹配程度较高的碎片。这些得到的高匹配碎片组成一个高匹配碎片集。在该碎片集中，有且仅有唯一的碎片与已有碎片正确匹配。为了从高匹配碎片集中筛选出唯一正确的匹配碎片，此时考虑加入人工干预。解决思路如下图所示：图二问题二解决思路（3）双面打印、既纵切又横切碎片的复原分析第三问复原对象为双面打印的、既纵切又横切的碎片。文档的双面打印使碎片数量在第二问的基础上又增加了一倍。根据前面分析可知，在第二问已经出现一块目标碎片对应多块高度匹配碎片的可能性，则在第三问中，这种可能性将大大增加。这就需要考虑设置区分度更大的匹配准则。如果邻接的两碎片正反两面都有文字，那么在非常逼近切割线位置处，正反两面的边缘像素吻合度将非常高，则与切割线距离值相等的两侧灰度值之差的平方越小，则此差平方沿切割线方向的累积和最小的碎片，即为所求的最优匹配碎片。解决思路如下图所示：图三问题三解决思路问题假设假设所给碎片全部为规则的理想矩形。假设不同碎片图像间不存在任何重叠部分。假设文档图像不存在任何倾斜、黑边（点）、畸变或残缺。假设符号说明符号说明模型建立与求解5.1问题一的模型建立与求解5.1.1纵切碎纸片的拼接复原模型建立假设本题所给碎纸片均为碎纸机均纵向均匀切割成的规则矩形，则图像均为对齐状态，可直接进行特征提取。除文档边缘图像外，每张图像的左、右两侧均为切割线，则图像左、右两侧的边缘像素（即切割线两侧的像素）是我们感兴趣的部分。边缘像素灰度匹配程度最大的两幅图像即为相邻。边缘灰度匹配法原理数字图像可看成由像素点组成的矩阵，每个像素点的值为0—255间的任意数值。将数字图像二值化处理后，所有像素点值为0或1。图像左（右）边缘的像素点值可认为一组列向量，向量的行数与碎片像素行数相同，则每个碎片对应左、右两组列向量。我们称这些向量为“边缘特征向量”。任取一个碎片的其中一个向量作为模板向量，逐次比较该模板向量与其余所有碎片向量间的笛卡尔距离。两组向量的笛卡尔距离由下式计算：d其中，n为碎片个数，d为笛卡尔距离，a、b为两特征向量的对应位置元素。由上式可知，使得笛卡尔距离最大的向量所对应的碎片与模板碎片相邻，其中切割线由两组列向量形成。边缘特征向量的确定设碎片个数为m，为每个碎片i建立左（left）、右（right）两个用于匹配的边缘特征向量Ail和A寻找匹配碎片假设其中的一个碎片为A，其左侧的某个元素Ai，j与另外一块碎片B的右侧的相对应的元素BiSUM=把所得到j个值分别平方后进行加运算。利用MIN函数求出其中的最小值，赋值给一个新建数组Ca，b，其中a5.1.2纵切碎纸片的拼接复原模型的求解原始图像最左侧碎纸片的确定（求解过程均采用附件一中的碎片图像）假设原始图像最左侧碎纸片的左边像素灰度值为A(i，j)，从附件一中找出A(i，1)=1的碎纸片，其在附件中的标号为8，从而可以确定在原始文档中碎纸片8为第一列。碎纸片的融合复原以碎纸片8为参考列，根据最优匹配原则，假设其右侧边缘处灰度值为1的像素坐标为，与其匹配的行匹配链的坐标为，利用公式可得到碎纸片8与其它碎纸片的距离分别为845、629、1227、2289、3009、4301、761、2890、192、867、6534、239、2801、52、4530、2303、4308、1208，显然，碎纸片8与碎纸片14的距离最短，从而可以确定，在原始文档中碎纸片14为第二列。根据上述方法，可以确定，所有碎纸片在原始文档中从第1列到19列的顺序依次为：8→14→12→15→3→10→2→16→1→4→5→9→13→18→1→7→17→0→6。5.2问题二的模型建立与求解5.2.1纵横切碎片拼接复原模型的建立灰度图像二值化二值图像就是指只有两个灰度级的图像，二值图像具有存储空间小，处理速度快，可以方便地对图像进行布尔逻辑运算等特点。更重要的是，在二值图像的基础上，还可以进一步对图像处理，获得该图像的一些几何特征或者其他更多特征。 图像在二值化操作前要对图像进行处理，因此在图像进行处理后，我们再获取图像的直方图以帮助选取阈值。整个流程如下所示：

读取图像→灰度图像→图像增强→图像直方图→二值化处理图像二值化是图像数据预处理的重要技术，如果二值化过程中阈值选取不当会损失原图像的许多有用信息。图像二值化处理的方法包括全局阈值法、局部阈值法，本文将采用全局阈值法进行图像的处理。灰度图像二值化处理的matlab程序：I=imread('Fig.jpg');

figure(1)

imshow(I)

J=find(I<150);

I(J)=0;

J=find(I>=150);

I(J)=255;

title('图像二值化(域值为150)');

figure(2)

imshow(I)

clc;

I=imread('Fig3.24.jpg');

bw=im2bw(I,0.5);

figure(3);

imshow(bw)

计算两碎片的上下间距对于边缘相同碎纸片的拼接,理想的计算机拼接过程应与人工拼接过程类似，即拼接时要判断碎纸片内的字迹断线或碎片内的文字内容是否匹配。利用现有技术，可以获取碎片文字所在行的几何特征信息，比如文字行的行高、文字行的间距等信息，碎片复原时可利用这些信息进行拼接。由于文档的文字行方向和文档边缘平行，如果碎片内的文字行方向在碎片边缘断裂，那么与它相邻的碎纸片在边缘处一应有相同高度、相同间距的文字行，凭此特征可以很容易从大量碎片中挑选出符合文字内容拼接的碎片。首先假设碎片像素高度为，每行的像素宽度保存在数组，内，每行的空白点数保存在数组，内，总的文字图像像素高度设为0，则文字行高和可按下述算法计算：（1）0，表示从碎片最低点开始从上往下扫描。（2），判断>否，如果大于，结束，否则转（3）。（3）判断<20否，也即判断该行碎片宽度是否小于20个像素宽度、如果小于，转2，否则转（4）。（4）判断—<5否，也即判断该行白点个数与该行像素点宽度的差是否在5范围内，小于5，表示该行是空白行，转（5），否则表示不是空白行，转（2）。（5）记下该行的序号，寻找下一个空白行号,判断是否存在，如果存在，转（6），否则表示扫描到最高点，扫描过程结束。（6）判断—>10否，即要求文字块图像高度应大于某个最小值，这里10，如果不作此限制，那么表格线也可能被认为是文字行，这里是不允许的。若大于文字图像最小高度，转（7），否则转（2）。（7）计算行，，内的文字图像个数，注意文字图像的宽度与高度的比值应该在-3之间，不在此范围内比值范围内的图像不应该统计。（8）判断是否>0，大于则，，转（9），如果等于0，不累加文字总个数和文字行高度，也转（9），显然,行位置就是文字行的Y坐标位置。（9），寻找下一个序号为的空间行，应该小于，同时第+1行不是空白点行，如果存在，则-1，转（2），否则结束。计算出行高度后，考虑到碎片内文字行高度和小于碎片像素高度，而碎片像素高度一般远小于10000，可将这两个数按公式*1000+合并成为一个数，然后对不同方向的合并数进行排序，这样能更有效地选取行高和最小的目标方向。确定匹配准则对于附件中切割规则的碎片，其邻接碎片上均有文字，那么在非常逼近切割线的位置处，边缘像素吻合度将非常高。假设其中的一个碎片为A，其右侧边缘处灰度值为0的像素坐标为Ai，j，假设与A邻接的碎片为B，其左侧边缘处灰度值为0的像素坐标为Bi，j，对Bi，j与Ai对应于原始图像最左侧碎片的确定根据碎片左侧碎片文字位置的特征，其左侧一列像素的灰度值均为1，利用这种方法可以找出所有符合条件的碎片。但是在实际操作中，符合条件的碎片数目往往会大于原始图像的行数，因此仅仅选取碎片左侧一列的灰度值为参考是不科学的，为了达到选取目的，我们需选择左侧两列，甚至更多列的灰度值为参考。利用此方法可以找出左侧碎片，并根据图像命名对它们进行随机排列。拼接过程中的人工干预由于计算机在数字图像处理方面的缺陷，让计算机对碎片进行完全意义上的自动化拼接几乎是不可能的，为保证拼接的质量及准确性，需要在拼接过程中加入人工干预过程。一般情况下，拼接碎片时先利用计算机搜索与目标碎片匹配的未拼接碎片，并根据匹配程度按顺序显示待选碎片，此时可利用人工干预的方法，从多个待选碎片中选出符合文字内容的碎片，这种半自动拼接方法提高了计算机拼接的准确性，拼接效率也比纯人工高。将匹配好的11行匹配链融合具体模型同模型一。5.2.2纵横切碎片拼接复原模型的求解原始图像最左侧碎片的确定（求解过程均采用附件三中的碎片图像）假设原始图片左侧碎片的左列灰度值为A(i，j)，从附件三找出A(i，1)=1的碎片共有19块，其在附件中的标号分别为：168、29、7、38、61、11、49、46、62、67、71、80、106、135、14、94、125、184、89。但我们所需的左侧碎片数仅为11块，显然，找出的碎片并不符合我们的要求，需要进一步筛选。扩大左侧碎片的搜索范围，令A(i，1)=A(i，2)=A(i，3)=A(i，4)=1，符合要求的碎片共有11块，其标号分别为：7、168、38、14、94、49、89、29、61、71、125，由此便确定了左侧碎片，并假设这些碎片在原始文档中所在行的位置分别为：A、B、C、D、E、F、G、H、I、J、K。确定每一行的行匹配链（1）以碎片7为匹配起点，从左至右依次进行拼接。根据模型二最优匹配原则，碎片7右侧边缘处灰度值为1的像素与209碎片距离最近，因此碎片7与碎片209左右邻接，从而得到第一条匹配链：7→209。（2）以碎片209为起点，与其右侧边缘处灰度值为1的像素距离最短的碎片共有4块，标号分别为：73、7、173、138，对此匹配过程进行人工干预，发现碎片209与碎片138的文字内容最匹配，因此可以确定碎片129与碎片138左右邻接，从而得到第二条匹配链：7→209→138。（3）根据步骤（1）、（2）所用方法可以确定以碎片7为起点的行匹配链：7→209→138→158→126→68→175→45→174→0→137→53→56→93→153→70→166→32→196；以碎片168为起点的行匹配链：168→100→76→62→142→30→41→23→147→191→50→179→120→86→195→26→1→87→18；以碎片38为起点的行匹配链：38→148→46→161→24→35→81→189→122→103→130→193→88→167→25→8→9→105→74；以碎片14为起点的行匹配链：14→128→3→159→82→199→135→12→73→160→203→169→134→39→31→51→107→115→176；以碎片94为起点的行匹配链：94→34→84→183→90→47→121→42→124→144→77→112→149→97→136→164→127→58→43；以碎片49为起点的行匹配链：49→54→65→143→186→2→57→192→178→118→190→95→11→22→129→28→91→188→141；以碎片89为起点的行匹配链：89→146→102→154→114→40→151→207→155→140→185→108→117→4→101→113→194→119→123；以碎片29为起点的行匹配链：29→64→111→201→5→92→180→48→37→75→55→44→206→10→104→98→172→171→59；以碎片61为起点的行匹配链：61→19→78→67→69→99→162→96→131→79→63→116→163→72→6→177→20→52→36；以碎片71为起点的行匹配链：71→156→83→132→200→17→80→33→202→198→15→133→170→205→85→15→165→27→60以碎片125为起点的行匹配链：125→13→182→109→197→16→184→110→187→66→106→150→21→173→157→(异常)→204→139→145 值得一提的是，标号为181的碎片不能够和其它任何碎片进行匹配，而且最后一行匹配链的第16列无碎片可拼接，根据题目要求，已在附录二中将其单独列出。确定每一行行匹配链的顺序根据原始图像中顶部像素的灰度值均为1的规律，并结合人工干预的方法，可以确定F行匹配链为原始文档的第一行。以F行匹配链为参考，根据最优匹配原则，假设F行匹配链的下侧边缘处灰度值为1的像素坐标为，与其匹配的行匹配链的坐标为，利用公式可得到F行匹配链与其它行匹配链的距离分别为1925、894、3226、1286、2709、3651、1028、45、1396、2450，显然，F行匹配链与I行匹配链的距离最短，从而可以确定在原始文档中I行匹配链为第二行。根据上述方法，可以确定所有行匹配链在原始文档中的顺序依次为：F→I→B→C→J→D→E→K→H→A→G。5.3问题三的模型建立与求解5.3.1双面横、纵切碎纸片的拼接模型建立与求解模型建立（1）确定匹配准则如果邻接的两碎片正反两面都有文字，那么在非常逼近切割线位置处，正反两面的边缘像素吻合度都会很高，即目标碎片右侧灰度值为0的像素，与待匹配碎片左侧灰度值为0的像素的距离很小，那么距离平方的累积和最小的碎片即为所求的最优匹配。对于附件中切割规则的碎片，其邻接碎片上均有文字，那么在非常逼近切割线的位置处，边缘像素吻合度将非常高。由于附件5中原始文档为正反两面打印，则假设待拼接碎片为B，其a面左侧边缘处灰度值为0的像素坐标为Bai，j，b面为Bbi，j；参考碎片为A，其右侧边缘处灰度值为0的像素坐标为Ai，jMinaMin比较Mina1与Mina2的大小，确定与参考碎片a面的最小距离Mina，从而确定与参考碎片Minb1Minb2比较Minb1与Minb2的大小，确定与参考碎片b面的最小距离Minb对于正反面均有文字的碎片而言，一旦找到参考碎片a面的最优匹配碎片，就可以确定参考碎片b面的最优匹配碎片。即参考碎片正反面的最优匹配碎片分别为同一碎片的两个面。因此，只需Mina与Min=Mina+Minb图N模型三匹配准则示意图在拼接碎片时，可先计算目标碎片正反面与所有未拼接碎片正反面在所有可能拼接位置处的距离相等的像素对差平方的累积和，然后对其和进行降序排列，排在前面的碎片与目标碎片邻接的可能性最高。（2）算法设计基于文字行特征的碎片半自动拼接算法设计如下：分析所有碎纸片图像，获取所有碎纸片的边界。获取所有碎纸片内文字行方向线特征。从碎片内挑选一未拼接纠偏碎片，按文字向上方向放置到计算机屏幕上。在计算机屏幕上人工选择某一碎片，计算该碎片某一边界（上、下、左、右）与未接碎片边界（上、下、左、右）可能拼接位置处的距离相等的灰度值差平方的累积和：a计算该碎片反面与未拼接碎片反面在可能拼接位置处距离相等的灰度值差平方的累积和：a求碎片正、反面沿切割线距离相等的灰度值的两个累积和：a将此和按递减顺序排列，按递减顺序依次显示未拼接碎片，人工选择碎片并拼接到计算机屏幕上。保存已拼接好的部分，并从未拼接碎片集合中删除所选碎片。判断未拼接碎片集合是否为空，若是，则保存计算机屏幕上的拼接正反面图像，转⑨。否则，转④。代码返回已完成拼接的完整图像。5.3.2双面纵横切碎片拼接复原模型的求解原始图像最左侧碎片的确定（求解过程均采用附件5中的碎片图像）假设原始图片左侧碎片的左列灰度值为A(i，j)，从附件5找出A(i，1)=1的碎片共有27块，其在附件中的标号分别为：23b、136b、5a、146b、143b、83a、90a、52b、13a、35a、54b、172a、105a、9b、54b、140b、76a、42a、169a、180b、116a、201b、157b、148a、199b、51a、109b。但我们所需的左侧碎片数仅为22块，显然，找出的碎片并不符合我们的要求，需要进一步筛选。扩大左侧碎片的搜索范围，令A(i，1)=A(i，2)=A(i，3)=1，符合要求的碎片共有22块，其标号分别为：143b、42a、180b、90a、35a、201b、148a、105a、109b、54b、136b、5a、140b、180b、76a、90a、13a、116a、172a、157b、9b、51a。由此便确定了左侧碎片，并假设这些碎片在原始文档中所在行的位置分别为：A、B、C、D、E、F、G、H、I、J、K、L、M、N、O、P、Q、R、S、T、U、V。确定每一行的行匹配链（1）以碎片143b为匹配起点，从左至右依次进行拼接。根据模型三最优匹配原则，碎片143b右侧边缘处灰度值为0的像素与碎片200b距离最近，因此碎片143b与碎片200b左右邻接，从而得到第一条匹配链：143b→200b。（2）以碎片200b为起点，与其右侧边缘处灰度值为0的像素距离最短的碎片共有5块，标号分别为：24a,76b、102a、86b、191a，对此匹配过程进行人工干预，发现碎片200b与碎片86b的文字内容最匹配，因此可以确定碎片200b与碎片86b左右邻接，从而得到第二条匹配链：143b→200b→86b。（3）根据步骤（1）、（2）所用方法可以确定以碎片143b为起点的行匹配链：143b→200b→86b→187b→131b→56b→138a→45a→137b→61b→94b→98a→121a→38a→30a→42b。并依次确定以标号为42a、180b、90a、35a、201b、148a、105a、109b、54b、136b、5a、140b、180b、76a、90a、13a、116a、172a、157b、9b、51a的碎片为起点的行匹配链。（4）原始文档正面某一行的左侧碎片在其反面的位置为相同行的右侧，根据这个规律，可将步骤三中的22个行匹配链区分为正反两面。正面的行匹配链为：136b→47a→20a→164b→81b→189b→29a→18b→108a→66a→110a→174b→183b→150a→155a→140a5a→152a→147a→60b→59a→14a→79a→144a→120b→22a→124b→192a→25b→44a→178a→76b143b→200b→86b→187b→131b→56b→138a→45a→137b→61b→94b→98a→121a→38a →30a→42b83a→39b→97a→175a→72b→93b→132b→87a→198b→181b→34a→156a→206b→173b →194b→169b90a→203b→162b→2a→139b→70b→41a→170b→151b→1b→166b→115b→65b→191a→37b→180a13a→24a→57a→142a→208a→64b→102b→17b→12a→28b→154b→197a→158a→58a→207a→116b35a→159a→73b→193b→163a→130a→21b→202a→53b→177b→16b→19b→92b→190b→50a→201a172a→122a→182b→40a→127a→188a→68b→8b→117b→167a→75b→63b→67a→46a→163a→157a105a→204a→141a→135b→27a→80b→0b→185a→176a→126b→74b→32a→69a→4a→77a→148b9b→145a→82b→205a→15b→101a→118b→129b→62a→52b→71b→33b→119a→160b→95a→51b54b→196b→112a→103a→55b→100b→106b→91a→49b→26b→113a→134a→104a→6a→123a→109a反面的行匹配链为：140b→155b→150b→183a→174a→110b→66b→108b→18a→29b→189a→81a→164a→20b→47b→136a76a→178b→44b→25a→192b→124a→22b→120a→144b→79b→14b→59b→60a→147b→152b→5b42a→30b→38b→121b→98b→94a→61a→137a→45b→138b→56a→131a→187a→86a→200a→143a169a→194a→173a→206a→156b→34b→181a→198a→87b→132a→93a→72a→175b→97b→39a→83b180b→37a→191b→65a→115a→166a→1a→151a→170a→41b→70a→139a→2b→162a→203a→90b116a→207b→58b→158b→197b→154a→28a→12b→17a→102a→64a→208b→142b→57b→24b→13b201b→50b→190a→92a→19a→16a→177a→53a→202b→21a→130b→163b→193a→73a→159b→35b157b→163b→46b→67b→63a→75a→167b→117a→8a→68a→188b→127b40b→182a→122b→172b148a→77b→4b→69b→32b→74a→126a→176b→185b→0a→80a→27b→135a→141b→204b→105b51a→95b→160a→119b→33a→71a→52a→62b→129a→118a→101b→15a→205b→82a→145b→9a109b→123b→6b→104b→134b→113b→26a→49a→91b→106a→100a→55a→103b→112b→196a→54a确定每一行行匹配链的顺序根据原始图像中顶部像素的灰度值均为1的规律，并结合人工干预的方法，可以确定K行匹配链为原始文档正面的第一行。以K行匹配链为参考，根据最优匹配原则，假设K行匹配链的下侧边缘处灰度值为1的像素坐标为，与其匹配的行匹配链的坐标为，利用公式可得到K行匹配链与其它正面行匹配链的距离分别为896、1294、3906、3286、1700、329、1043、985、2301、861，显然，F行匹配链与L行匹配链的距离最短，从而可以确定在原始文档中L行匹配链为第二行。根据上述方法，可以确定所有行匹配链在原始文档正面中的顺序依次为：K→L→A→N→P→Q→E→S→H→U→J。根据上述方法，可以确定所有行匹配链在原始文档反面中的顺序依次为：M→O→B→D→C→R→F→T→G→V→I。模型优缺点分析6.1模型优点6.1.1基于灰度的文字特征提取，碎片差异化明显、鲁棒性强对于规则碎片的处理，传统的对不规则碎片提取碎片角点、曲率等几何特征的思路很难提取到足够的有用信息。本文从像素角度出发，将碎片二值化后，通过提取碎片边缘文字的灰度值得到特征向量，不同碎片的特征向量差异化明显。运用这种基于灰度的文字特征提取方法，不仅可以复原本题的中、英文黑白规则碎片，也适用带有文字和表格的混合碎片等。6.1.2半自动拼接，效率高、精度好由于计算机数字分析图像能力的缺陷，让计算机对碎片进行完全意义上的自动化拼接几乎不太可能。本文在拼接过程中加入人工干扰过程，当程序给出多个待匹配碎片时，用户再根据人脑进一步分析结果舍弃或拼接待选碎片。这种半自动拼接方法综合利用了计算机高速计算能力以及人的文字图像识别和理解能力，拼接效率比纯人工高，拼接准确性也好于纯计算机拼接法。6.1.3高度优化的算法和代码，性能良好、可靠度高本文算法和代码均充分结合题目实际情况进行优化，执行性能良好，结果可靠度高。从算法角度看，加入了“智能排序”和“自动剔除”功能，当程序给出的匹配结果不止一个时，则根据与目标碎片的匹配度从高到低依次排序，用户只需进行很少次数的匹配即可得到正确的碎片。当某一块碎片已匹配成功后，程序将自动从待匹配碎片集合中剔除该碎片，保证后续匹配过程只检测最新的碎片集合，从而实现人工干预的简洁性和代码执行的高效性。从代码角度看，主要通过MATLAB软件编写代码，使用了各类循环体、数组和“超级矩阵”（cell矩阵）等高效处理策略、函数，从而将几百行的代码压缩到20行以内，代码执行效率和可读性有明显提高。6.2模型缺点6.2.1碎片理想化带来的局限性本题所给碎片较为理想化（摆正、规则且无噪声干扰等），而实际情况中遇到的很多碎片图像可能是彩色的、倾斜的、不规则的，甚至是残缺、畸变的。故本文建立的模型在应用领域上有一定的局限性。例如，当使用扫描仪等设备采集到碎片图像很容易带有黑边、黑点和干扰噪声，如果不加入相关的图像预处理措施，那么这些噪声将在一定程度上对本文所建立的模型产生不良影响。6.2.2匹配准则易受外界影响基于像素平方和（SSD）的匹配准则虽然是一种简单有效的匹配准则，但因为它直接利用图像的灰度值，所以对匹配区域的光照变化十分敏感，一旦待匹配的两块碎片在接缝区域的曝光不一致，则匹配准则的准确性将受到影响。另外，这种匹配准则还对碎片的旋转和缩放比较敏感。模型的推广与改进7.1模型推广7.1.1碎片类型的推广除了复原本文所给定附件中的碎片，该模型还普遍适用于多语言文字碎片，表格文档碎片，甚至是非文档类（如人物图片碎片、景物碎片）等规则碎片。7.1.2应用领域的推广除了应用于碎纸机规则切割出的碎纸片，拼接复原技术还可广泛应用于卫星遥感【文献A】、海底勘探【文献B】、地表植被测绘【文献C】、无人机监视和搜索【文献D】、机器人视觉【文献E】、视频监控【文献F】、医学探查【文献G】、电子稳像【文献H】和虚拟现实【文献I】等领域图像拼接复原。7.2模型改进7.2.1碎片倾斜时，预置“纠偏”处理本题所给碎片均为摆正的规则矩形，而实际情况中，由于人在使用碎纸机、扫描仪等设备时引入的操作偏差，我们更多地遇到的是碎片倾斜情况。若其他条件保持不变，仅将碎片变为倾斜的，则在进行碎片特征提取前，需先进行碎片的“纠偏”。可以利用“维格纳——威利（WVD）”纠偏法【标注参考文献：胡奇《文档图像拼接技术的研究》】等来实现。7.2.2碎片不规则时，提取几何特征本题所给碎片均为规则矩形，而实际情况中，碎纸片可能是由于某种原因被撕碎成不规则的形状，此时处理对象变为不规则的、具有边角、曲率等几何特征的碎片。对于这些碎片的处理角度不再是像素，而考虑尽可能多地提取碎片的几何特征。可以通过轮廓特征、角点检测、SIFT等算法实现【标注参考文献：蔡丽欢《图像拼接方法及其关键技术研究》】。7.2.3二值文档图像带黑边时，设计黑边过滤算法【标注参考文献：胡奇《文档图像拼接技术的研究》】通过扫描仪等设备采集碎片图像时，最容易产生的畸变就是黑边。黑边一般是在文档的外围，因此仅分析文档周边即可。根据黑边的特征和文字的特征就可以去掉黑边。该特征用两个量来表达，一个是黑像素个数，另一个是黑像素到白像素和白像素到黑像素的个数。算法设计及区域选择如下图所示:图N黑边过滤算法流程图图N区域选择示意图参考文献【A】LaurieGibson.AutomationtechnologywithIKONOSsatelliteimagery[C]//Sensors,Systems,andNext-GenerationSatellitesV,ProceedingsofSPIE,2001,4540:650-660.【B】S.Negahdaripour,X.Xu,A.Khamene.Avisionsystemforreal-timeposi-tioning,navigation,andvideomosaicingofseafloorimageryintheapplicationofROVs/AUVs[C]//ApplicationsofComputerVision,FourthIEEEWorkshoponProceedings,1998,(8):248-249.【C】MariaG.Almeida,BernardoF.TRudorff,YosioE.Shimabukuro.NOAA-AVHRRimagemosaicsappliedtovegetationidentification[C]//Geo-SpatialImageandDataExploitationII,ProceedingsofSPIE,2001,4383:31-35.【D】N.Heinze,M.Esswein,W.Krüger,etal..AutomaticimageexploitationsystemforsmallUAVs[C]//AirborneIntelligence,Surveillance,Reconnaissance(ISR)SystemsandApplicationsV.Proc.ofSPIE,2008,6946:69460G1-10.【E】B.Kaya,A.Berkay,F.Erzincanli.Robotassistedtilingofglassmosaicswithimageprocessing[J].IndustrialRobot,2005,32(5):388-392.【F】TomRiley,MarkBernhardt,CatherineCowell,etal..Implementingadvancedimageprocessingtechnologyinsensorsystemsforsecurityandsurveillance[C]//OpticsandPhotonicsforCounterterrorismandCrimeFightingIII,Proc.ofSPIE,2007,6741:67410W1-12.【G】K.Loewke,D.Camarillo,W.Piyawattanametha,D.Breeden,etal.Real-timeimagemosaicingwithahand-helddual-axesconfocalmicroscope[C]//ProgressinBiomedicalOpticsandImaging.Proc.ofSPIE,2008,6851:68510F1-9.【H】王建东.罗军.基于图像拼接的全帧视频稳定算法[J].红外技术,2007,29(8):435-439.【I】R.Szeliski.VideoMosaicsforVirtualEnvironment[J].IEEEComputerGraphicsandApplications,1996,16(2):22-30.【】蔡丽欢.廖英豪.郭东辉.图像拼接方法及其关键技术研究[J].计算机技术与发展.2008(03)【】胡奇.文档图像拼接技术的研究[D].哈尔滨工程大学.2005.附件附件一：第一问MATLAB程序——基于最优匹配的纵切图像拼接%%读取图片clc,clear,closeallpicstr=dir('*.bmp');[r,c]=size(picstr);fori=1:rpic{i}=imread(picstr(i).name);lcol{i}=pic{i}(:,1);rcol{i}=pic{i}(:,72);end%%最优匹配[rowcol]=size(pic{1});forii=1:rforjj=1:r%jj=7;d(ii,jj)=sum((double(lcol{ii})-double(rcol{jj})).^2);d1(ii,jj)=sum((double(rcol{ii})-double(lcol{jj})).^2);endend%%找到第一幅图片位置[valdir]=min(d)forii=1:rflag=1;forjj=1:length(lcol{ii})if(lcol{ii}(jj)~=255)flag=0;%endendif(flag==1)dir2=ii;endendresult=[];result(1)=dir2;forii=2:rresult(ii)=dir(result(ii-1));end%%重现复原图片warningofffigure,imshow([pic{result}])*********************************************************附件二：第二问MATLAB程序——横、纵两切图形的拼接第一步：从209张碎片中求出11行图片%%第二问,横切纵切图片的复原.clc,clear,closeallpicstr=dir('*.bmp');[r,c]=size(picstr);fori=1:rpic{i}=imread(picstr(i).name);lcol{i}=double(pic{i}(:,1:4));rcol{i}=double(pic{i}(:,69:72));end[row0col0]=size(lcol{1});%%检测每幅图片最左边四列的灰度值.forii=1:rrcol{ii}=rcol{ii}(:,1)+rcol{ii}(:,2)+rcol{ii}(:,3)+rcol{ii}(:,4);lcol{ii}=lcol{ii}(:,1)+lcol{ii}(:,2)+lcol{ii}(:,3)+lcol{ii}(:,4);endforii=1:rforjj=1:rd(ii,jj)=sum((double(lcol{ii})-double(rcol{jj})).^2);endend%%[valdir]=min(d)A(1,:)=([49,54,65,143,186,2,57,192,178,118,190,95,11,22,129,28,91,188,141]+1);%forii=1:rA(3,:)=([168,100,76,62,142,30,41,23,147,191,50,179,120,86,195,26,1,87,18]+1);%endA(11,:)=([89,146,102,154,114,40,151,207,155,140,185,108,117,4,101,113,194,119,123]+1);%%找出最左边的图片kk=1;forii=1:rflag=1;forjj=1:length(lcol{ii})if(lcol{ii}(jj)~=1020)flag=0;continue;endendif(flag==1)dir2(kk)=ii;kk=kk+1;endenddir2A(4,:)=([38,148,46,161,24,35,81,189,122,103,130,193,88,167,25,8,9,105,74]+1);kk=1;forii