基于边缘检测法的碎片复原技术_大学生数学建模竞赛论文 精品推荐
说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。
基于边缘检测法的碎片复原技术 摘 要 当今碎纸机已经成为办公室不可或缺的一部分，但碎纸片的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用，本文针对碎纸片建立复原模型，对碎纸片的复原进行研究。 针对问题一：运用边缘检测法中边缘特征值相似度越高匹配程度越好的原理建立模型一，以左右边缘特征值为出发点，运用matlab软件编程，得到附件1图片的复原排序为:008，014，012，015，003，010，002，016，001，004，005，009，013，018，011，007，017，000，006；附件2图片的复原排序为：003，006，002，007，005，018，011，000，005，001，009， 013，010，008，012，014，017，016，004。 针对问题二：在模型一的基础上，运用平面图片的四维方向性建立模型二，以上下左右四个方向的边缘特征值为出发点，运用matlab软件编辑循环程序，对附件3的图片碎片进行循环比较匹配，得到除143、038、018、074、176、043等6张独立的图像外的附件3的大部分复原排序，结合人工的干预可以得到附件3的复原排序；对附件4得到除150、057、132、206、009、177等6张独立的图像外的附件4的大部分复原排序，结合人工干预得到附件4的复原排序。 针对问题三：在模型一和模型二的基础上，运用无有效重叠区域图像拼接的原理建立模型三，并运用matlab软件编程的方法，得出095a，095b，156a，156b，028a，028b，022a，022b，087a，087b ，105a，105b为孤立的图片，因为每张图片都是a面和b面对应的，所以孤立图片也是一一对应的，经过人工干预可以得到附件5中图片正、负两面的排序。 本文对碎片复原进行了研究，该项技术对大多数企业、机关院校和军队会出于保密的需要，使用碎纸机对重要文件、单据以及材料进行销毁，而事实上，在许多情况下，需要将已经破碎的文档重新恢复起到重要的作用。 关键词：边缘检测法 四维方向性 无有效重叠区域图像拼接 matlab 1 1．问题的重述 当今碎纸机已经成为办公室不可或缺的一部分。大多数企业、机关院校和军队会出于保密的需要，使用碎纸机对重要文件、单据以及材料进行销毁。而事实上，在许多情况下，需要将已经破碎的文档重新恢复。然而，面对大量、细小、破碎的纸片，如果进行人工辨识和拼接的话，那将意味着海量枯燥的工作和漫长无期的时间，而且，通常结果并不能让人满意。计算机具有快速处理大量数据的能力，而通过计算机算法对破碎的文档进行恢复的研究较少。破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题： 1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。 2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。 2．问题的分析 碎纸片的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。所以我们希望能用电脑完成这一海量枯燥的工作并同时减少漫长无期的时间花费。 首先，我们将碎片由图片转为灰度图像并进一步转化为二值图像即白色像素点用1表示，黑色像素点用0表示，以将其简化用于matlab中的计算。 针对问题一，我们考虑到无论是汉字还是英文字母在每个碎片之间存在其笔画的连续性，根据导入图片后形成的像素矩阵中左右两端像素点的相似度，相似度最大的两张碎片来为相邻的两幅碎片。同时，位于首尾的两张碎片存在其特殊性，即位于首位的碎片的最左端和位于末位的碎片的最右端应是权威白色，即像素点全为1.。所以以像素点的列向量和为1980为标准来确定出首列和尾列，然后对剩下的图片的像素的最右列和最左列运用相关性关系进行匹配，将相似率最高的两个排在一起，再依次向右拼接所有碎片，完成对碎片的复原。 针对问题二：在问题一的基础上，考虑到问题二中原文件数据碎片除了竖切还有横切，所以我们先判别出位于最左边的碎片，然后对剩下的图片进行特征值匹配，因为碎片较小，图片各边的特征值少，不能保证能一直满足向右的拼接，所以我们不仅仅要考虑图片的最左边的特征值，还要考虑图片上下边的特征值，在一直向右拼接受阻的情况下考虑向左、向上或者向下的拼接，以更准确的匹配图片。如果遇到各个方向均有很多的可能链接的碎片的情况下，对其进行人工干预，最后完成对碎片的复原。 2 针对问题三：在问题一、二的基础上，我们不仅仅要考虑横切和竖切的碎片，还要考虑图片是双面的，一张碎片的一面是000a，对应的另一面就是000b， 这需要我们要将问题一和问题二中的所有工作都做一遍。因为无法确定哪些碎片是出于同一面的，所以我们首先找到碎片最左边的边缘特征值都为1和最右边的边缘特征值都为1的图片，如果这些碎片同时满足图片的a，b面是一一对应的，即如果001a的最左列特征值和为180，那么001b的最右列的特征值和为180，以确定出所有的位于两端的碎片。在此基础上，即根据问题二的算法，在所有剩下的碎片中选择适合碎片，拼接出正反面中的一面，然后基于附件五每张碎片均有两面的特性，得出另一面的拼接图片，并同时以此作为程序拼接的检验，以完成对碎片的复原。 3．模型的假设与符号说明 1、模型的假设 （1）假设一：假设附件中所给的碎片没有完全相同的两张。 （2）假设二：假设附件中所给的碎片之间能够完全的无缝连接 （3）假设三：假设三：假设附件中所给出的碎片没有完全空白碎片； （4）假设四：碎纸片中只含有灰度像素，不含彩色像素； （5）假设五：原文件左右两侧均存在页边距。 2、符号说明 符号 f(x,y) 说明 对图片的数字化 表示s图片的第i行的右边界即第72列的特征值 表示k图片的第i行的左边界即第1列的特征值 表示s图片的第j列的右边界即第180行的特征值 表示k图片的第j的右边界即第1行的特征值 表示图像中对应点(x,y)的灰度值 x,~y)的灰度值 表示图像中对应点(~x(i,72,s) y(i,1,k) x(j,180,s) y(j,1,k) gt(x,y) gt(~x,~y) 4．模型的准备 针对问题一： Step1:图像数字化 图像数字化是以数字的形式来不失真地描述图像信息 。将破碎的纸质文档，运用计算机将其数字化，转换成数字图像，以便通过图像处理办法，在计算机上对其进行处理， 将件1和附件2中碎片进行是数字化，并输出BMP格式的原始图像f(x,y)；由于BMP格式的图像数据没有压缩，则原始的数据信息被最大程度地保存了下来，以便进行下一步处理。 3 Step2:对图像的预处理 对原图像f(x,y)依次进行直方图均衡化和图像滤波处理，再使用8领域方向链码的方法从背景模板中提取得到全部碎片图像。 Step3：灰度图像二值化 在进行了灰度化处理之后，图像中的每个象素只有一个值，那就是象素的灰度值。它的大小决定了象素的亮暗程度。为了更加便利的开展下面的图像处理操作，还需要对已经得到的灰度图像做一个二值化处理。图像的二值化就是把图像中的象素根据一定的标准分化成两种颜色。在系统中是根据象素的灰度值处理成黑白两种颜色。阈值分割法的结果很大程度上依赖于对阈值的选择，因此该方法的关键是如何选择合适的阈值。 选择不同的初始灰度也会产生不一样的二值化图像，因此要获得最佳效果，必须要考虑选择一个好的初始T 值。 针对问题二： 在问题一的基础上，我们同样的先对附件3和附件4做图像灰度化预处理和二值化处理，之后进行下一步处理。 Step4：图像拼接 找出二值化后的图片最左边都为1特征值的图片排在每一行的首位，形成第一列。以便接下来的图片找准位置。 针对问题三： 在问题一和问题二的基础上，我们同样的先对附件5做图像灰度化预处理和二值化处理，之后进行下一步处理。 Step5:找出所有的是首列的图片和所有的是尾列的图片，找出的图片有两种可能，一是正面的首列图片和尾列图片，二是反面的首列和尾列图片，基于他们的上、下特征值将他们分别匹配成整列。 5．模型的建立与求解 5.1问题一的模型建立于求解 5.1.1模型一建立 灰度图像是指只含亮度信息，不含色彩信息的图像。将色彩图像转化为灰色图像的过程称为图像的灰度化处理。彩色图像中的每个像素的颜色有R、G、B三个分量决定，而每个分量有255种值可取，这样一个像素点可以有1600多万的颜色变化范围。而灰度图像是R、G、B三个分量相同的一种特殊的彩色图像，一个像素点的变化范围为255种，所以在数字图像处理中一般先将各种格式的图像转变成灰度图像以使后续的图像的计算量变得少一些。灰度图像的描述与色彩图像一样仍然反映了整幅图像的整体和局部的色度和亮度等级的分布和特征。图像的灰度化处理可先求出每个像素点的R、G、B三个分量的平均值，然后将这个平均值赋予给这个像素的三个分量。 单纯的看，灰色图也是黑白的，就像黑白电视显示的图像一样，但是点与点之间黑的程度不一样的，这就是深度。如果称不同深度的颜色为一色的话，灰色图像就不止只有黑色和白色两种颜色，一般使用灰度图为256级灰度图，就是说图像由256中不同灰度级的颜色组成。 4 灰度原理：将图像转化成为灰度图像的过程成为图像的灰度化处理。通过灰度图像中的相似灰度聚类，通过聚类将图像表示为不同区域。颜色聚类实际上是将相似的集中颜色合并为一色。 在实际的聚类算法中，在聚类的初期采用最小误差准则，合并图像中的大量噪声点，并在颜色数合并到一定数时转而采用最小色差准则法，以保留面积较小的区域。这种综合聚类法可以有效克服单一使用其中一种方法带来的缺陷，能够得到满意的效果。 二值图像就是指只有两个灰度级的图像，二值图像具有存储空间小，处理速度快，可以方便地对图像进行布尔逻辑运算等特点。更重要的是，在二值图像的基础上，还可以进一步对图像处理，获得该图像的一些几何特征或者其他更多特征。 在图像相关方面， 用二值图像进行相关比用灰度级图像进行相关有更好的相关性能和去噪作用。在用硬件实现时可避免乘法运算，从而提高硬件系统的速度和降低成本。在图像的符号匹配方面，二值图像比灰度级图像更适合于用符号来表达。二值图既保留了原始图像的主要特征，又使信息量得到了极大的压缩。图像二值化是图像处理中的一项基本技术，也是很多图像处理技术的预处理过程。 图像的预处理在进行图像二值化操作前要对图像进行预处理，包括彩色图像灰化和增强。由于选取阈值需要参照直方图，因此在图像进行处理后，我们再获取图像的直方图以帮助选取阈值。 图像二值化是图像数据预处理的重要技术，如果二值化的过程中阈值选取不当会损失原图像的许多有用信息。图像二值化的处理方法包括全局阈值法、局部阈值法。 全局阈值法是指在二值化的过程中只使用一个全局阈值T的方法。它将图像的每个像素的灰度值与T进行比较，若大于T，则取为前景色（白色）；否则，取为背景色。 根据文本图像的直方图或灰度空间分布确定一个阈值，以此实现灰度文本图像到二值图像的转化，其中全局阈值法又可分为基于点的阈值法和基于区域的阈值法。阈值分割法的结果很大程度上依赖于对阈值的选择，因此该方法的关键是如何选择合适的阈值。 选择不同的初始灰度也会产生不一样的二值化图像，因此要获得最佳效果，必须要考虑选择一个好的初始T 值。另外使用迭代法虽然能得到很精确的阈值，但是也占用了大量的时间，即时间复杂度比较高，效率较其他算法低。 我们考虑到无论是汉字还是英文字母在每个碎片之间存在其笔画的连续性，根据导入图片后形成的像素矩阵中左右两端像素点的相似度，相似度最大的两张碎片来为相邻的两幅碎片。同时，位于首尾的两张碎片存在其特殊性，即位于首位的碎片的最左端和位于末位的碎片的最右端应是权威白色，即像素点全为1.。所以以像素点的列向量和为1980为标准来确定出首列和尾列，然后对剩下的图片的像素的最右列和最左列运用相关性关系进行匹配，将相似率最高的两个排在一起，再依次向右拼接所有碎片，完成对碎片的复原。 根据边缘检测法建立模型一： 1k209minabs(x(i,72,s)y(i,1,k)) 这个模型是根据特征值相同的相减为零，通过对第一张图片二值化后的最后一列和其他张二值化后的第一列进行比较，得到绝对值最小的那张图片就和第一张图片最匹配。所以本文提出的算法如图所示： 5 上图表示根据边缘检测法，找到一条边最左边的边缘特征值全为1的为第一列，最右边的边缘值全为1的为最后一列，剩下的中间17列，运用matlab编辑的程序对第一列的最右边的边缘特征值和中间的17列的最左边的边缘特征值进行匹配，相同特征值的相似度最高的相匹配，依次循环能够得到最后的答案。 5.1.2模型一的求解 根据二值化后的图片可以找出附件1的第一列的序号为008，最后一列的序号为006，经过matlab软件编程得到的中间17列的序号依次为：014、012、015、003、010、002、016、001、004、005、009、013、018、011、007、017、000. 表一：附件1的图片排序： 序号 1 序号 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9 19 10 排序 008 014 012 015 003 010 002 016 001 004 排序 005 009 013 018 011 007 017 000 006 根据二值化后的图片可以找出附件2的第一列的序号为003，最后一列的序号为004，经过matlab软件编程得到的中间17列的序号依次为：006 、002、007、015、018、011、000、005、001、009、013、010、008、012、014、017、016 表二： 附件2的图片排序： 序1 号 排00序 3 2 006 3 002 4 007 5 015 6 018 7 011 8 000 9 005 10 11 001 009 12 13 14 15 16 17 18 19 013 010 008 012 014 017 016 004 5.2模型二的建立与求解 5.2.1模型二的建立 在问题一的基础上，考虑到问题二中原文件数据碎片除了竖切还有横切，所以我们先判别出位于最左边的碎片，然后对剩下的图片进行特征值匹配，因为碎片较小，图片各边的特征值少，不能保证能一直满足向右的拼接，所以我们不仅仅要考虑图片的最左边的特征值，还要考虑图片上下边的特征值，在一直向右拼接受阻的情况下考虑向上或者向下的拼接，以更准确的匹配图片。如果遇到各个方向均有很多的可能链接的碎片的情况下，对其进行人工干预，最后完成对碎片的复原。 在模型一的基础上，根据汉字和英文的笔画不规则性建立模型二： 6 maxabs(x(i,72,s)y(i,1,k))1k209abs(x(i,72,s)y(i1,1,k))1maxk209 maxabs(x(i,72,s)y(i1,1,k))1k209 建立的模型二中表示第一张图片最后一列的第i个特征值与其他张图片第一列的第i个特征值比较，并且还对后一张图的第一列的第i1，i1个特征值进行比较，。 根据模型二的思想，运用matlab编写程序可以得到图片拼接的部分结果，其他的不能拼接的图片采取人工干预。 首先我们按照第一列像素点为全1来确定出文章的第一列得到11个碎片分，再按照第一行像素点均为1来确定满足位于文章的第一行的碎片，最后的其交集为[014、029、049、071 、089]五个碎片能满足成为文章左上角的碎片，此时进行人工干预，按照我们的思想进行向右的拼接得到以下拼接图片以14为第一个碎片（计算出右边一张为128）得出拼接图像为 （图1） 以029为第一张碎片（计算出右边图像为064）得到拼接图像为（图2）以049作为第一张碎片（计算出右边碎片为054）得到拼接图像为（图3） 图1 图2 图3 以071为第一张（计算得出下一张为156）得出图像（图4）以089为第一张，下一张计算出为146 图像为（图5） 7 图4 图5 以此5个拼接图我们可以看出，为了满足逻辑上的通顺，只有以图片049为首张图片能够满足实际情况，所以我们定下首张碎片为049.然后进行拼接。 开始拼接： 我们首先从049号图片进行向右的拼接的到前3个碎片为049、054、065，图像为（图6）在进行第4张碎片的拼接的时候出现多碎片满足的情况，我们改为从第3个碎片进行向下拼接得到位置为（2，3）的碎片为078号，拼图结果为（图7） 图6 图7 在此基础上再进行向右的拼接。以此方法，得出需要人工干预后才能继续完成拼接的碎片坐标分别为（1，4）。以此类推可以得到整个附件3的流程图为： 8 Step1:当走过的后面。 049054065时就不能再继续，在此需要人工干预将143拼接在065061019078143186002057192178118190095Step2:当走过续。 011022067069099162096131079129028091188141时就不能再继Step3: 当走过时就不能再继续。 063116072003177020052036Step4: 当走过 062142030041023147194050179120086195时就不161024035081189122103193088167025能再继续。 Step5: 当走过 135012073160203169134039031051107115时就不121042124144077112149097136164127058能再继续。 Step6: 当走过014128003159082199094034084183090047时就不能再继续。 125013182109197016184110187Step7: 当走过029064111201005092180048037075时就不007028174能再继续。 066106150021173157181204139145Step8: 当走过055044206010104098172171059时就不153070166032196能再继续。 Step9: 当走过138158126068175045时就不能再继续。 Step10: 当走过083132200017时就不能再继续。 Step11: 当走过102154114040151时就不能再继续。 Step12: 当走过004101113194119123时就不能再继续。 9 Step13: 当走过168100076148046时就不能再继续。 Step14: 当走过085152165027060时就不能再继续。 026001Step15: 当走过087时就不能再继续.。 009105Step16: 当走过071156时就不能再继续。 Step17: 当走过089146时就不能再继续。 Step18: 当走过080033202198015133170208时就不能再继续。 Step19: 当走过207155140185108 117时就不能再继续。 Step20: 当走过000137053056093时就不能再继续。 经过每一步的循环得到的图像都是不完整的不规则图形，根据图像的边缘的特殊形状进行拼接，可以由此得到较为完整的图形，剩下的小部分孤立图片经过人工干预可以使所有的图片完成无缝拼接，得到最终的答案。如图8，图9所示： 图8 10 图9 5.2.2模型二的求解： 当程序运行完成时可以找到143、038、018、074、176、043等6张独立的图像，现在进行人工干预将143放在065和186之间，018放在087后面，074放在105后面，176放在115后面，043放在058后面，038放在148的前面。经过干预后可以得到最终的排序如下表所示。 表三：附件3的图片排序： 049 054 065 143 186 002 057 192 178 118 190 095 011 022 129 028 091 188 141 061 019 078 067 069 099 162 096 131 079 063 116 163 072 006 177 020 052 036 168 100 076 062 142 030 041 023 147 191 050 179 120 086 195 026 001 087 018 038 148 046 161 024 035 081 189 122 103 130 193 088 167 025 008 009 105 074 014 128 003 159 082 199 135 012 073 160 203 169 134 039 031 051 107 115 176 094 034 084 183 090 047 121 042 124 144 077 112 149 097 136 164 127 058 043 125 013 182 109 197 016 184 110 187 066 106 150 021 173 157 181 204 139 145 029 064 111 201 005 092 180 048 037 075 055 044 206 010 104 098 172 171 059 007 208 138 158 126 068 175 045 174 000 137 053 056 093 153 070 166 032 196 071 156 083 132 200 017 080 033 202 198 015 133 170 205 085 152 165 027 060 089 146 102 154 114 040 151 207 155 140 185 108 117 004 101 113 194 119 123 同理，可以知道附件4的英文碎片还是可以首先得到最左边一列的图片，接着一步一步的将附件4拼接出来，同时在拼接程序运行完成时可以找到150、057、132、206、009、177等6张独立的图像，现在进行人工干预将150放在117和005之间，057放在 11 022后面，132放在181前面，206放在144后面，009放在016后面，177放在012的后面。经过干预后可以得到最终的排序如下表所示。 表四：附件4的图片排序： 191 075 011 154 190 184 002 104 180 064 106 004 149 032 204 065 039 067 147 201 148 170 196 198 094 113 164 078 103 091 080 101 026 100 006 017 028 146 086 051 107 029 040 158 186 098 024 117 150 005 059 058 092 030 037 046 127 019 194 093 141 088 121 126 105 155 114 176 182 151 022 057 202 071 165 082 159 139 001 129 063 138 153 053 038 123 120 175 085 050 160 187 097 203 031 020 041 108 116 136 073 036 207 135 015 076 043 199 045 173 079 161 179 143 208 021 007 049 061 119 033 142 168 062 169 054 192 133 118 189 162 197 112 070 084 060 014 068 174 137 195 008 047 172 156 096 023 099 122 090 185 109 132 181 095 069 167 163 166 188 111 144 206 003 130 034 013 110 025 027 178 171 042 066 205 010 157 074 145 083 134 055 018 056 035 016 009 183 152 044 081 077 128 200 131 052 125 140 193 087 089 048 072 012 177 124 000 102 115 5.3模型三的建立与求解 5.3.1模型三的建立 当重叠区很小时 ， 由于不能选取出能与其他图像部分有明显不同的特征子图像 ， 或者因最大梯度曲线段的点数过少 ， 因此曲线匹配结果不可信 。当有轻微断裂时 ， 由于需要对属于具有明显特征的目标像素点的灰度值进行一定外推 ， 以便使拼接后的接缝处的典型特征目标完整连续 ，因此拼接难点在于如何获取帧间的准确运动参数(平移和旋转)、外推平滑有断裂后的特征点的灰度以及建立特征连续性的评价准则等 。本文给出的无有效重叠区域的图像拼接方法主要涉及如下几项关键技术 : ( 1 ) 线段提取 ; ( 2 ) 不同图像帧的线特征配对 ; ( 3 ) 精拼接方法 ; ( 4 ) 有轻微断裂时的典型线特征的外推 。 1、线特征提取 由于 S AR 特殊的成像机制带来的相干斑噪声 ，造成针对光学图像的传统线段检测方法( 如差分算子 、 Canny算子 、P r e w itt算子等 ) 在处理 S AR图像时效果很不好 ，因此本系统采用由T ouzi和Lop e s等人 提 出 的 均 值 比 率 ( r a ti o2 of2 ave r age s, Ro A )算子来检测 S AR 图像的阶跃型边缘 。Ro A 算法是一种通过计算相邻两区域的均值比来确定目标像素是否为边缘点的算法 。 该方法利用的是相邻区域的强度均值 ，由于其降低了因斑点噪声而引起的单个像素的强度波动 ， 因此可以获得比较可靠的线特征结果 。 为了减少计算量 ， 这里只提取左图的一定区域内的右部分和右图的一定区域内的左部分的线特征 。 原算法是通过比较 4个相邻方o向区域来完成( 如图 1 所示 ) ， 而对图像拼接的特定应用来说 ， 可以不提取 90 方向的线段 ， 而增加其他方向的模板数量 ，其中c为中心像素点 ， 其坐标为( x, y ) 。设L( x, y )和 R( x, y )分别为左 、 右图像中点( x, y ) 沿某一个方向的左 、 右相邻区域的平均灰度值 ， 则均值比率的估计为 ROA(x,y)maxR(x,y)L(x,y),L(x,y)R(x,y) 然后将ROA(x,y)与预先确定的阀值T1进行比较，如果满足ROA(x,y)T1则认为点(x,y) 12 为边界点。Touzi和Ropes等人从数学上推导出了ROA(x,y)的解析式，而且在给定虚警率即可以确定相应的阀值。 然后将提取的线片段组织成有意义的线特征 。对于如何组织线特征 ， 学术界已经提出了很多方法，如启发式连接 、 Hough变换 、 相位编组等 ，但在设计或选取组织线特征方法时 ， 应在考虑算法有效性的同时 ，也要考虑算法的时效性 。 2、 图像帧间线特征配对 一般来说 ，位于待拼接左图像中的最右狭小区域内的稳定线特征 ( 平行于距离向的线特征除外 ) ， 其在右图像左半部分中应有后续部分 ， 而线特征正好止于拼接处的概率极小 ，因此此处可以忽略 。线段配对后可忽略如下几种特殊线特征 ： （1）. 止于图像接缝处线特征；（2）. 在接缝处发生突变的线特征 ；（3）. 太短的线特征；（4）. 竖直线特 征 。也就是说，这几类线特征都可认为是虚假特征 。不同帧间的线特征配对方法如下：拟合左图像候选拼接区域内的线特征，记剔除（3）、（4）两类后的表征线段的函数集合为LfL,fL,,fL,, 同样拟合右图像中的线特征 , 记线段函数集合为 L12mˆ为LL沿方位向右向外推扩展的点数（dˆ为负数时，为左向缩LRf1R,f2R,,fnR,.设d减）。如果fL和fR满足R则称C(i,j)fR,fL为在扩展点为dˆLˆf(0)f(NdTiˆjjiji2d时的一个候选配对。其中N味图像方位向的总数点。如果fL可以和L中的s(1sn)Ri个线段fR,fR,,fR}构成配对，则选取第j条线段fR和第i条线段fL构成有效配对，12xijj按如下条件选取： 1jargminj1DJxDJ1XR0fjR(xR)fiL(NdxR)^ R其中。Arg(*)取参数操作，Dj为线段fj中参与比较的点数，xR为图像中线段fR中参RL与比较的点数，xR为图像中线段fR的x坐标值。如果fi只能和LR中的1个线段fj构成配对，则他们就是有效配对。处理时，已经获得有效配对的线段就不再参与新的配对。 13 在给定的范围内改变d的值，即取d为可使Ll和LR中的线段有效配对数量最大的d值，R记此时的有效配对数量为mc（下角c代表counterpart）mcmmcn，由fj，^^fiL组成的第k个配对为Cdki,jfjRxR,k,fiLxL,k，则有效配对集合为cCdCdki,jk 1。而没有有效配对的线特征，则作为虚假特征，不予处理。m3、图像精拼接方法 当通过优化算法求取出最大有效线段配对集合Cd及其对应的外推扩展参数d( 即外推扩展点数 )后 , 则可以 d作为拼接基准来对待拼接图像进行精 细拼接 , 拼接思路是使选定的能量函数最小 。 设 x为最终拼接点与外推扩展参数 d的偏差 ，y为最终拼接图像沿距离向的错位 , 定义能量函数为 Df121mcLR E(d,x,y,xR)(x)f(Ndxx,k)f(x,k)yRiRjRmk1xR0(~x,~y)argminE(d,x,y,xR)求取则左图中 的点 (Ndx,M2)与右图中的x,y点(0,M2y)为拼接时的对应基准点 。其中 , 由于连续图像错位很小 , 因此可将y限定在很小范围内；Dj为fjR中参与比较的点数(xR) 是按xR递减的离散权重函数 , 其取值范围在( 0 ～1 )之间 , 且满足如下条件 : Df1(xR)1xR00(x)1R本系统选取的权重函数为以下线性形式： (xR)kxRbxR0,1,,Dj1(Dj1)0 在问题一、二的基础上，我们不仅仅要考虑横切和竖切的碎片，还要考虑图片是双面的，一张碎片的一面是000a,对应的另一面就是000b,这需要我们要将问题一和问题二中的所有工作都做一遍。因为无法确定哪些碎片是出于同一面的，所以我们首先找到碎片最左边的边缘特征值都为1和最右边的边缘特征值都为1的图片，如果这些碎片同时满足图片的a,b面是一一对应的，即如果001a的最左列特征值和为180，那么001b的最右列的特征值和为180，以确定出所有的位于两端的碎片。在此基础上，即根据问题二的算法，在所有剩下的碎片中选择适合碎片，拼接处正反面中的一面，然后基于附件五每张碎片均有两面的特性，得出另一面的拼接图片，并同时以此作为程序拼接的检验，以完成对碎片的复原。 14 在模型一、二的基础之上，根据无有效重叠区域的SAR建立模型三： (x)(y)gL(x,y)(~x)(~y)gR(~x,~y)g(p) (x)(y)(~x)(~y)x,~y)的灰度值。(*)是其中gL(x,y),gR(~x,~y)是点p在两幅图像中的对应点(x,y),(~线性权重函数，在图像的中心取值为1，而在凸显边缘取值为0.整个拼接算法流程图如下图所示： SRS图像顺序图像粗拼接图像预处理判断是否存在有效重叠区域无有效重叠区域有有效重叠区域提取待拼图片特征，通过特征匹配取得外推参数d，进行拼接用传统相似匹配法进行拼接 5.3.2模型三的求解： 根据程序可以得到正、反两面各有6张孤立的图片，分别是095a,095b,156a,156b,028a,028b,022a,022b,087a,087b ,105a,105b。经过人工干预可以得到附件5正、负两面的排序为表五和表六。 表五：附件5正面图像排序（转置表） 136a 047b 005b 152b 143a 200a 083b 039a 090b 203a 013b 024b 15 035b 159b 172b 122b 105b 204a 009a 145b 054a 196a 020b 164a 081a 189a 029b 018a 108b 066b 110b 174a 183a 150b 155b 140b 125b 111a 078a 147b 060a 059b 014b 079b 144b 120a 022b 124a 192b 025a 044b 178b 076a 036b 010a 089b 086a 187a 131a 056a 138b 045b 137a 061a 094a 098b 121b 038b 030b 042a 084a 153a 186a 097b 175b 072a 093b 132a 087b 198a 181a 034b 156b 206a 173a 194a 169a 161b 011a 199a 162a 002b 139a 070a 041b 170a 151a 001a 166a 115a 065a 191b 037a 180b 149a 107b 088a 057b 142b 208b 064a 102a 017a 012b 028a 154a 197b 158b 058b 207b 116a 179a 184a 114b 073a 193a 163b 130a 021a 202b 053a 177a 016a 019a 092a 190a 050b 201b 031b 171a 146b 182a 040b 127a 188b 068a 008a 117a 167b 075a 063a 067b 046b 168b 157b 128b 195b 165a 141b 135a 027b 080a 000a 185b 176b 126a 074a 032b 069b 004b 077b 148a 085a 007a 003a 082a 205b 015a 101b 118a 129a 062b 052b 071a 033a 119b 160a 095b 051a 048b 133b 023a 112b 103b 055a 100a 106a 091b 049a 026a 113b 134b 104b 006b 123b 109b 096a 043b 099b 表六：附件5反面图像排序(转置表) 078b 089a 186b 199b 088b 114a 111b 010b 153b 011b 107a 184b 125a 036a 084b 161a 149b 179b 140a 076b 042b 169b 180a 116b 155a 178a 030a 194b 037b 207a 150a 044a 038a 173b 191a 058a 183b 025b 121a 206b 065b 158a 174b 192a 098a 156a 115b 197a 110a 124b 094b 034a 166b 154b 066a 022a 061b 181b 001b 028b 108a 120b 137b 198b 151b 012a 018b 144a 045a 087a 170b 017b 029a 079a 138a 132b 041a 102b 189b 014a 056b 093a 070b 064b 081b 059a 131b 072b 139b 208a 164b 060b 187b 175a 002a 142a 020a 147a 086b 097a 162b 057a 047a 005a 200b 039b 090a 013a 136b 005a 143b 083a 090a 013a 146a 171b 031a 201a 050a 190b 092b 019b 016b 177b 053b 202a 021b 130a 163a 193b 073b 035a 035a 165b 195a 128a 157a 168a 046a 067a 063b 075b 167a 117b 008b 068b 188a 127a 040a 182b 172a 172a 003b 007b 085b 148b 077a 004a 069a 032a 074b 126b 176a 185a 000b 080b 027a 135b 141a 204b 105a 023b 133a 048a 051b 095a 160b 119a 033b 071b 052a 062a 129b 118b 101a 015b 205a 082b 009b 009b 099a 043a 096b 109a 123a 006a 104a 134a 113a 026b 049b 091a 106b 100b 055b 103a 112a 054b 054b 6．模型结果的分析与检验 针对问题1 ，对于这种简单的、有大量的数据情况下的碎纸片拼接，我们可以 16 matlab软件，依靠简单的循环语句，得到最后的拼接结果，且效果良好。对于问题2.3，由于每个碎片所包含的数据量较少，我们无法获得足够的信息来完成整幅文件的一次性拼接，只有在电脑运算的基础上加入人工干预才能够达到目的。在本题这种总体数据量想对较少的情况下，得到的结果完整且富有逻辑性。能够达到我们预期的目的。 7．模型的推广与改进方向 本模型是基于碎纸机粉碎出的碎片进行拼接还原，碎片的尺寸均相同且能够进行完整的拼接。在实际运用中，需要恢复的文件存在手工撕碎成为形状大小均不相同的碎片，同时也可能存在在碎片的保存中出现损坏、尖角磨损等情况，此时在运用本题思想考虑边缘文字相似度的基础上，需要进一步考虑到碎片形状以及运用模糊数学的思想来处理出现磨损的碎片。 8．模型的优缺点 本模型能够在大量的数据中快速选出位于边缘的碎片和与其相邻的碎片，从而快速的完成文件的恢复工作，同时，本模型利用的是碎片四个边之间的相似度来进行拼接，能够很好的完各类文字的拼接。但是，在实际运用中会出现需要人工运用逻辑思维介入，在附件3,4这种像素较少的情况下不能实现一次性完成，需要人机结合工作。 参考文献 [1]罗智中 基于文字特征的文档碎纸片半自动拼接 J 计算机工程与运用 2012 [2]郑世友 周晔 无有效重叠区域的SAR图像拼接方法 J 中国图像图形学报 2009 [3] 赵静、但琦等著；数学建模与数学实验；高等教育出版社 施普林格出版社；2000年。 [4]刑楠、张婧、周一等著；基于文字特征的碎纸机破碎文档恢复方法；发明专利申请；2012年。 [5]贺兴华、周媛媛、王继阳、周辉等著MATLAB7.x图像处理；人民邮电出版社；2006年。 17 附录 复原图： 问题1： 18 19 问题2 20 问题3 21 22 程序clear; clc; %----读入图片 for i=0:18 na=[sprintf('%03d',i),'.bmp'];% 定义图片的序号 im(:,:,i+1)=imread(na,'bmp');% 批量读入所有图片 im2(:,:,i+1)=im2bw(im(:,:,i+1));% 将读入图片转化为0-1矩阵 end %-----找第1幅图片 flag=1; 23 mm=1:19; for i = 1:19 temp=im2(:,1,i)'; for j=1:1980 if(temp(j)~=1) flag=0; break; else flag=1; end end if(flag~=0) mm(1)=i; end end %----寻找最大匹配度 s=zeros(1,19); for n=2:19 temp=im2(:,72,mm(n-1))'; for k=1:19 temp1=im2(:,1,k)'; if(j~=mm(1)) for m=1:1980 if(temp(m)==temp1(m)) s(k)=s(k)+1; end end end end s; for x=1:19 if(s(x)==max(s)) mm(n)=x; end end s=zeros(1,19); end %----拼接图片 img=[]; for i=1:19 img=[img im(:,:,mm(i))]; end %----输出结果 24 sort1=mm-1 %图片排列序号 imshow(img) %复原后图片 clear all; for i=0:208 na=[sprintf('%03d',i),'.bmp'];% 定义图片的序号 im(:,:,i+1)=imread(na,'bmp');% 批量读入所有图片 im2(:,:,i+1)=im2bw(im(:,:,i+1));% 将读入图片转化为0-1矩阵 end %---找左上角图片 k=3;%设置判断最上行，最左列数 mm=[];for i=1:209 t1=sum(sum(im2(:,1:k,i))); t2=sum(sum(im2(1:k,:,i))); if t1==k*180 & t2==k*72 mm=[mm i]; end end mm %结果9张图片编号： 15 30 50 72 90 126 136 144 169 %%以上验证通过 %---进一步甄别 mm1=mm; for k=2:3 s=0;flag=1; for i = mm1(k-1,:) temp=im2(:,k,i);%考虑第5列，经检验在第5列－第12列之间，均只有11个图片。 for j=1:180 if(temp(j)~=1) flag=0; break; else flag=1; end end if(flag~=0) s=s+1; mm1(k,s)=i; end end end 25 %结果11张图片：8 15 30 39 50 62 72 90 95 126 169 %以下不要 ss=[];sss=[]; for k=1:209 s=0; for i=1:180 t0=im2(i,72,15)- im2(i,1,k); if t0~=0 s=s+1; end end ss(k)=s; end tt=find(ss==min(ss)); sss=[ss tt] mm=1:209; img=[]; for j=1:11 for i=1:19 img(i,j)=im(:,:,mm(i+(j-1)*19)); end end imshow(img) %向右拼接。k为出发点，j为到达点 k=input('输入出发点(向右)：'); s=[]; for j=1:209 % k 为左边的图片，j 为右边的图片 s(j)=sum(abs(im2(:,72,k)-im2(:,1,j))); end t=find(s==min(s)); k=t %向下拼接。k为出发点，j为到达点 k=input('输入出发点(向下)：'); s=[]; 26 for j=1:209 % k 为上边的图片，j 为下边的图片 扫描列数为78 %s(j)=sum(abs(im2(1,:,k)-im2(180,:,j))); %向上 s(j)=sum(abs(im2(180,:,k)-im2(1,:,j))); %向下 end t=find(s==min(s)); k=t %向上拼接。k为出发点，j为到达点 k=input('输入出发点(向上)：'); s=[]; for j=1:209 % k 为上边的图片，j 为下边的图片 扫描列数为78 s(j)=sum(abs(im2(1,:,k)-im2(180,:,j))); %向上 %s(j)=sum(abs(im2(180,:,k)-im2(1,:,j))); %向下 end t=find(s==min(s)); k=t %向左拼接。k为出发点，j为到达点 k=input('输入出发点(向左)：'); s=[]; for j=1:209 % k 为左边的图片，j 为右边的图片 s(j)=sum(abs(im2(:,1,k)-im2(:,72,j))); end t=find(s==min(s)); k=t 27 本文来源：https://www.wddqw.com/doc/bd7b5518ba0d6c85ec3a87c24028915f804d84c2.html