下载文档原格式
利用数学软件复原碎纸片的方法
吴晓
【期刊名称】《肇庆学院学报》
【年(卷),期】2014(035)002
【摘要】研究了碎纸片的拼接复原问题,建立了合理有效的碎纸片拼接复原的数学模型;给出了数学软件实现自动拼接的具体算法;结合人工拼接得出复原图片;最后,对所给的拼接方法提出了改进方向.
【总页数】4页(P23-26)
【作者】吴晓
【作者单位】肇庆学院数学与统计学院,广东肇庆526061
【正文语种】中文
【中图分类】G642
【相关文献】
1.碎纸片的拼接复原方法研究 [J], 杜景南;韩邦合;伏臻;李爽
2.碎纸片拼接复原的数学模型与方法 [J], 蔡志杰
3.碎纸片的拼接复原方法研究 [J], 马知也
4.基于MATLAB规则碎纸片拼接复原方法的研究及实现 [J], 姜艳秋;纪艳侠;王葳;周燕蒙;王淼;冯兴荣
5.规则文档碎纸片的多元统计分析拼接复原方法 [J], 石欣;梁妙珠;李琪琛;邱雷因版权原因，仅展示原文概要，查看原文内容请购买。
基于SACO算法的碎纸片拼接复原模型
杨凌;王琳琳;刘冲冲;苏思美
【期刊名称】《太原师范学院学报（自然科学版）》
【年(卷),期】2013(012)004
【摘要】破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用.文章基于灰度图像原理和欧氏几何理论,定义了列约束匹配准则,分别设计了基于列约束匹配准则的欧氏距离变换算法、类蚁群优化算法SACO,建立了欧氏距离变换模型、类蚁群优化算法的碎片拼接等模型,对碎纸片的拼接复原问题进行了相应的求解.
【总页数】4页(P65-68)
【作者】杨凌;王琳琳;刘冲冲;苏思美
【作者单位】安徽财经大学统计与应用数学学院,安徽蚌埠233030;安徽财经大学统计与应用数学学院,安徽蚌埠233030;安徽财经大学统计与应用数学学院,安徽蚌埠233030;安徽财经大学统计与应用数学学院,安徽蚌埠233030
【正文语种】中文
【中图分类】O29
【相关文献】
1.基于数字图像的碎纸复原模型与算法--2013年全国大学生数学建模B题碎纸片的拼接复原问题 [J], 刘铁
2.基于数字图像的碎纸复原模型与算法——2013年全国大学生数学建模B题碎纸
片的拼接复原问题 [J], 刘铁;
3.碎纸片的拼接复原模型及其算法研究 [J], 姚光督;沈景凤;王文东;滕泉
4.碎纸片的拼接复原模型和算法研究 [J], 程红萍
5.基于量子算法的碎纸片拼接复原问题 [J], 王彦超;刘鑫磊;武良隆;刘晓东;范兴奎因版权原因，仅展示原文概要，查看原文内容请购买。
碎纸片的拼接复原分析最终引言碎纸片的拼接复原是一项有趣且具有挑战性的任务。
无论是为了还原重要文件还是拼接有意义的图像，我们都需要使用各种技巧和方法来完成这项任务。
本文将介绍一种基于分析的碎纸片拼接复原方法，通过对碎纸片的形状、颜色和纹理等特征进行分析，最终达到拼接复原的目标。
碎纸片的特征提取在进行碎纸片的拼接复原之前，首先需要提取碎纸片的特征。
这些特征包括碎纸片的形状、颜色和纹理等。
形状特征提取为了提取碎纸片的形状特征，可以通过计算碎纸片的边界和角度来获得。
首先，使用图像处理技术，如Canny边缘检测算法，将碎纸片的边缘提取出来。
然后，使用霍夫变换来检测碎纸片的直线和角点，从而计算出角度和边界。
颜色特征提取碎纸片的颜色特征可以通过计算图像的颜色直方图来得到。
颜色直方图表示了图像中每个颜色的像素数量。
我们可以使用像素级别的颜色分布来比较不同碎纸片的颜色特征，并找到相似的碎纸片来进行拼接。
纹理特征提取碎纸片的纹理特征可以通过计算图像的纹理描述符来得到。
纹理描述符是用于描述图像纹理的数值特征。
其中，最常用的纹理描述符包括灰度共生矩阵（GLCM）和局部二值模式（LBP）。
通过计算碎纸片的纹理描述符，我们可以比较不同碎纸片之间的纹理相似度，并选择相似的碎纸片进行拼接。
碎纸片的拼接策略在完成碎纸片特征提取后，接下来需要制定碎纸片的拼接策略。
拼接策略将基于碎纸片的特征相似度和拼接的整体目标来确定。
相似度匹配根据碎纸片的形状、颜色和纹理特征，我们可以计算两个碎纸片之间的相似度。
一种常用的相似度计算方法是使用余弦相似度，它衡量两个向量之间的夹角。
通过计算碎纸片之间的相似度，我们可以找到最相似的碎纸片来进行拼接。
拼接顺序在进行碎纸片的拼接时，需要制定一个拼接顺序。
一种常用的策略是首先选择与已拼接部分最相似的碎纸片进行拼接，然后逐渐增加已拼接部分的面积，直到最终完成拼接。
拼接约束为了保证拼接的准确性，我们需要制定一些拼接约束。
基于图像灰度值的碎纸片拼接复原于翔;肖翔;江开忠;杨厉丽;古晞【摘要】碎纸片的拼接复原在刑侦、军事等领域都有着重要的应用.通过Matlab 软件读取每张碎纸片的灰度值,建立灰度值矩阵,根据左边缘空白距离最大原则和灰度匹配距离最小原则,建立碎纸片的拼接复原模型,并对模型进行求解,实现了碎纸片的自动拼接复原.【期刊名称】《上海工程技术大学学报》【年(卷),期】2015(029)003【总页数】5页(P273-277)【关键词】碎纸片;拼接复原;灰度值矩阵;左边缘空白距离;灰度匹配距离【作者】于翔;肖翔;江开忠;杨厉丽;古晞【作者单位】上海工程技术大学汽车工程学院上海201620;上海工程技术大学基础教学学院上海201620;上海工程技术大学基础教学学院上海201620;上海市公安局松江分局上海 201600;同济大学数学系上海200092【正文语种】中文【中图分类】O29Key words： scrapped paper; splice and recovery; gray value matrix; left marginal blank distance; gray matching distance碎纸片的拼接复原在刑事侦查、军事情报获取、司法物证复原以及历史文献修复等领域都有着重要的应用.传统上,碎纸片的拼接复原工作由人工完成,但当碎纸片的数目较多时,拼接复原的准确率和效率都很低.随着计算机科学技术的发展,人们试图开发碎纸片的自动拼接技术,以实现碎纸片的高效拼接复原.目前,国内许多学者对碎纸片图像的拼接复原技术进行了研究,取得了丰富的成果.如茹少峰[1]基于轮廓曲线匹配对一般刚性物体的拼接和复原问题进行了研究;张欣等[2]运用水平集法对碎纸片图像的轮廓特征进行拼接复原;邵向鑫[3]提出了基于 Harris 角点特征检测的图像拼接算法,通过使用约束配准对的算法,找到正确的配准角点,从而完成图像的拼接;罗智中[4]研究了碎纸片内文字行特征和表格特点,提出了基于碎片文字行特征和表格特点的半自动拼接算法.碎纸片的拼接复原是将一幅完整的图像切割成M×N个,大小、形状相同的碎纸片,混合后再重新拼接复原的过程.在此过程中，不仅要考虑碎纸片左右端特征,还需要考虑上下端特征,除了左右边界需要确定相邻的碎纸片图像,还要对上下边界进行相邻图像的拼接.灰度[5]是使用黑色调表示物体,以黑色为基准色,不同饱和度的黑色来显示图像.通过使用256色灰度等级,“0”表示纯黑色,“255”表示纯白色,0~255从小到大分别表示由黑到白的过渡色.本文通过Matlab读取每张碎纸片的灰度值,建立灰度值矩阵.根据左边缘空白距离最大原则,找出原始图像中最左边一列的碎纸片图像.根据相邻两个碎纸片之间的灰度匹配距离最小原则,对于处于最左边一列中的碎纸片,从上到下,实施纵向匹配,实现局部的拼接复原,然后将实施纵向匹配后的每张碎纸片从左到右,实施横向匹配,最终实现全部碎纸片的拼接复原.对M×N个碎纸片中的每张碎纸片图像进行预处理,把连续的图像信息转化为数字形式,例如,对于第k张碎纸片,将其图像进行等间隔分割,得到均匀的m×n个小网格,运用Matlab软件中的imread函数读取每个小网格的灰度信息,建立一个m×n数字矩阵,记为称Gk为第k张碎纸片的灰度值矩阵.对于第k张碎纸片的灰度值矩阵Gk,记Tk为Gk的上边缘灰度值矩阵;记T,称Bk为Gk的下边缘灰度值矩阵;记,称Lk为Gk的左边缘灰度值矩阵;记,称RGk的右边缘灰度值矩阵.对于第k张碎纸片的灰度值矩阵Gk,若其前l列的所有元素均为255,称l为Gk的左边缘空白距离,表明前l列的元素对应的碎纸片区域是空白的.在所有的碎纸片中,左边缘空白距离最大的那些碎纸片,必定位于原始图像的最左边.设分别为第i张和第j张碎纸片的灰度值矩阵,记,称MD(Bi,Tj)为第j张碎纸片关于第i张碎纸片的纵向灰度匹配距离.MD(Bi,Tj)越小,表明第j张碎纸片上侧边缘关于第i张碎纸片下侧边缘的相似度越高.记,称MD(Ri,Lj)为第j张碎纸片关于第i张碎纸片的横向灰度匹配距离.MD(Ri,Lj)越小,表明第j张碎纸片左侧边缘关于第i张碎纸片右侧边缘的相似度越高.对于第i张碎纸片,建立纵向拼接复原模型为其中,I为尚未匹配的碎纸片的原始编号集.如果存在唯一j1∈I,使得,则第j1张碎纸片就可以作为第i张碎纸片的最优下侧匹配项.对于第i张碎纸片,建立横向拼接复原模型为其中,I为尚未匹配的碎纸片的原始编号集.如果存在唯一j2∈I,使得,则第j2张碎纸片就可以作为第i张碎纸片的最优右侧匹配项.基于左边缘空白距离最大原则和灰度匹配距离最小原则,对碎纸片进行拼接复原,流程如图1所示.以2013年全国大学生数学建模竞赛B题为利用2.5节中的数学模型和2.6节中的拼接流程,进行拼接复原.步骤如下:1) 图像数字化处理,运用Matlab软件,建立每张碎纸片的灰度值矩阵.2) 根据左边缘空白距离最大原则,找出原始图像中最左边的11张碎纸片序列号,分别为007、014、029、038、049、061、071、089、094、125和168.3) 根据灰度匹配距离最小原则,对11张碎纸片进行纵向匹配,结果见表1.4) 对表1中的每一个碎纸片,根据灰度匹配距离最小原则,进行横向匹配,结果如图3所示.拼接复原后的图像如图4所示.同样,对于仅含有英文文字的碎纸片(见图5),也可以用上述数学模型进行拼接复原,拼接复原后的序号如图6所示.拼接复原后的图像如图7所示.本文建立的拼接复原模型运用了边界的灰度值信息、文字在边缘相对位置的特征信息,由于不同语言文字的字体结构不同,因此,该模型目前仅适用于中英文碎片的拼接复原,对于手写文字图像的拼接复原尚有不足之处.此外,模型中没有考虑实际情况中可能存在彩色字体,在应用过程中可以考虑将颜色作为相邻碎纸片的匹配依据以增加匹配的准确度.碎纸片的拼接复原技术应用广泛,目前国内外关于此方面的技术发展尚未完善,还有很大的发展前景和研究空间.[1] 茹少峰.破碎物体复原技术与计算机辅助文物复原研究[D].西安:西北大学,2004.[2] 张欣,卜彦龙,朱家良.物证系统中碎纸轮廓提取技术研究[J].计算机仿真,2006,23(11):184-187.[3] 邵向鑫.数字图像拼接核心算法研究[D].长春:吉林大学,2010.[4] 罗智中.基于文字特征的文档碎纸片半自动拼接[J].计算机工程与应用,2012,48(5),207-210.[5] 饶俊飞.基于灰度的图像匹配方法研究[D].武汉:武汉理工大学,2005.。
基于边缘检测法的碎片复原技术摘要当今碎纸机已经成为办公室不可或缺的一部分，但碎纸片的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用，本文针对碎纸片建立复原模型，对碎纸片的复原进行研究。
针对问题一：运用边缘检测法中边缘特征值相似度越高匹配程度越好的原理建立模型一，以左右边缘特征值为出发点，运用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中图片正、负两面的排序。
本文对碎片复原进行了研究，该项技术对大多数企业、机关院校和军队会出于保密的需要，使用碎纸机对重要文件、单据以及材料进行销毁，而事实上，在许多情况下，需要将已经破碎的文档重新恢复起到重要的作用。
基于文档内容的碎纸拼接技术陈黎黎;国红军【摘要】在深入研究文档碎片预处理和拼接复原的相关理论和技术的基础上，针对文档碎片拼接过程中可能会出现的大量轮廓相同或相似的碎片的问题，提出了单面规则纵切文档碎片的拼接算法。
算法分别提取每个文档碎片的左右边界特征，将每个碎片的右边界特征与其余碎片的左边界特征进行匹配，以确定碎片之间的匹配关系。
%A lot of fragments with the same or similar contour may appear in the process of document stitching and recovery. To this problem, the theory and technology of fragment pretreatment and reconstruction are studied, and then the stitching algorithm of regular single-page fragments is proposed. In this algorithm, the features of every fra gment’ left and right edges can be extracted. The features of the right edges are compared with the others’ left-edge features, in order to determine the relationship between the matching fragments.【期刊名称】《衡水学院学报》【年(卷),期】2014(000)004【总页数】4页(P34-37)【关键词】纵切碎片;拼接复原;特征提取;特征匹配;文档碎片【作者】陈黎黎;国红军【作者单位】宿州学院信息工程学院，安徽宿州 234000;宿州学院信息工程学院，安徽宿州 234000【正文语种】中文【中图分类】TP391破碎文件的拼接技术在刑侦案件中的物证复原、考古研究中的历史文件和壁画修复以及军事情报获取等领域发挥着极其重要的作用.早期，碎片拼接复原工作是由人通过手工操作完成的，尽管拼接复原的准确率较高，但工作效率极低，特别是当碎片数量巨大时，手工拼接过程费时费力，一般很难在较短的时间内完成.随着计算机技术的飞速发展，为提高破碎文件的拼接和复原效率，人们逐步开始研究文件碎纸片自动拼接技术，即从许多散乱的文件碎片中，借助计算机通过特征匹配技术来识别出相邻的碎片，进而重现整个文件的原貌.1 问题的提出目前，国内外有关碎片拼接的方法有很多种.根据碎片特征可分为基于轮廓、色彩、纹理等特征的图像碎片拼接；根据碎片形状可分为规则碎片和不规则碎片的拼接；根据碎片的空间特征可分为二维和三维图像碎片的拼接等.大部分对碎片拼接复原方法的研究主要集中在碎片轮廓的匹配上，即基于轮廓的碎片拼接技术研究.许多学者提出了大量的算法，如，Helena Cristina da Gama Leitao etc[1]提出了一种典型的解决平面图像碎片匹配算法.H.J.Wolfson等[2]运用串匹配的技术查询最大匹配子串，解决了平面曲线匹配的问题.Ying Shan等[3]提出了一种概率框架的曲线匹配算法.朱良家等[4]对碎纸轮廓提取技术进行研究，通过对候选集评分的方式实现了对图像碎片的拼接.朱延娟等[5]提出基于Hausdorff距离的多尺度轮廓匹配算法等.这些算法实现了对碎片轮廓的匹配，已取得了一定的成果.但是，通常被碎纸机切碎的带有文字或图像信息的文档，其边缘是规则的，以上算法对这类碎片进行拼接复原时显然会失效[6].因此，研究基于文档内容的规则碎纸拼接技术是十分必要的.本文讨论的是被碎纸机横向或纵向规则切开的碎片的拼接复原技术，并在研究过程中做如下假设：假设一：任意两碎纸片的长度、宽度相等.假设二：任意两碎纸片间的厚度与纸张材料相同.假设三：任意碎纸片在切割后无信息丢失(即无破损).假设四：所有碎纸片无丢失、无多余、无沾污.2 碎片预处理为方便计算机对文件碎片进行拼接处理，首先将每张碎片通过扫描仪转换为bmp格式的图片并传输到计算机中，然后再对碎片图像进行预处理.由于扫描文件碎片的时候可能会发生倾斜现象，为此需要对倾斜图像进行调整.首先，找到倾斜图像的1至50列每一列最上面像素值为0的点，从这50个点中选出最上面的点.按此方法找出第51至100列(碎片图像的宽度总列数大于100)中处于最上面的像素值为0的点.利用这两个点找出平行于碎片中文字的直线，如图1. 图1 发生倾斜的碎片然后根据直线的斜率进行碎片角度的调整，调整后的碎片图像如图2所示.图2 调整方向后的碎片本文以每页打印纸被纵切19条碎片为例，其中的某一条文件碎片经预处理后如图3所示.图3 预处理后的纵切碎片3 碎片的特征提取与匹配经过预处理后的图像，按其图像的行数构建一个长度与之相等的一维数组.对图像进行逐行扫描，若此行含有像素值为0的点，则将对应此行的数组元素值设置为0，否则为1.图3对应的纵切碎片经上述转换后提取出的匹配特征如图4所示.图4 图片的匹配特征某一页面被纵切成的19条文件碎片按如上方法提取出对应的匹配特征后，将每条碎片的特征与其余的18条碎片的特征进行比较，以寻找匹配的碎片，具体步骤为：1) 为每条碎片i建立一个匹配数组number(i,19);2) 碎片i与其余每条碎片j进行特征比较.如果两碎片相应位置的特征值相等，则进行umber(i, j) = number(i, j) + 1;3) 找出碎片i的匹配数组number(i, 19)中的最大值number(i, k),则对应这个最大值number(i, k)的碎片k即为碎片i的匹配碎片.从实验结果来看，在实验中出现了许多碎片与某一条碎片匹配度极高的情况.究其原因，是因为在碎片匹配特征提取的时候，仅考虑了碎片在一整行上的总体特征，忽略了每行左右切割边界处特征的相异性，提取的特征比较粗糙，所以造成了匹配效率较低的现象.4 碎片匹配算法改进为提高碎片的配准率，同时确保能够准确分辨出两碎片的左右关系，需要对上述匹配算法进行改进.在对碎片特征进行提取时，分别考虑每条碎片的左右边界特征，将每条碎片的右边界(最后一列)特征与其余碎片的左边界(第一列)特征进行对比，以此确定是否匹配，对应的算法流程如图5：5 实验结果我们将来自同一页面，内容为英文的19条纵切文件碎片(图6所示)进行随机编号，即000号-018号，对这些碎片建立拼接复原模型，并按如上算法进行了拼接实验，结果如下：英文碎片拼接顺序编号：003，006，002，007，015，018，011，000，005，001，009，013，010，008，012，014，017，016，004.经过与原文对比，上述实验结果完全正确.文档碎片拼接复原技术是信息安全中的重要技术，它在警方获取证物及其他重要信息的获取等方面担负重要角色.鉴于文档碎片拼接复原技术的重要性，世界上已经开展了相关研究，但能够查阅到的资料相对比较少.目前在文档碎片拼接方面主要使用曲线的特征来进行碎片拼接，计算量非常大.本文在借鉴基于曲线特征的碎片匹配相关技术的基础上提出了对沿文字方向纵向规则切开的碎片拼接方法.最后通过实验对本人提出的算法和方法进行了验证.实验结果说明，该方法具有简单、方便、快速、高效的特点.但本文在许多方面仍有待进一步研究，主要包括以下几点：1) 本文提出的文档碎片拼接技术面向的对象过于理想化，应用的领域有局限性.2) 本算法仅适用于单面规则纵切的碎片的拼接复原，对于纵横切碎的文档碎片，以及双面纵横切碎的文档碎片在拼接时需要考虑的因素较为复杂，其拼接复原算法还有待研究.图5 碎片匹配算法流程图6 英文纵切碎片图7 碎片拼接结果参考文献：[1] LEITAO H C G, STOLFI J.A Multiscale Method for the Reassembly of Two-Dimensional Fagmented Ojects[J].IEEE Trans Patt Anal Machine Intell,2002,24(9):1239-1251.[2] WOLFSON H J. On Curve Matching[J].IEEE Transactions on Pattern Analysis and Machine Intelligence.1990,12(5):483-489.[3] SHAN Ying, ZHANG Zhengyou.New Measurements and Corner-Guidance for Curve Matching with Probabilistic Relaxation[J].International journal of Computer Vision.2002,46(2):157-171.[4] ZHU Liangjia, ZHOU Zongtan, HU Dewen.Globally ConsistentReconstruction of Ripped-Up Documents[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2008,30(1):1-13.[5] 朱延娟,周来水,张丽艳,等.基于Hausdorff距离的多尺度轮廓匹配算法[J].中国机械工程,2004,15(17):1553-1561.[6] 罗智中.基于文字特征的文档碎纸片半自动拼接[J].计算机工程与应用,2012,48(5):207-210.。
基金项目:高校博士点专项研究基金(20049998012)收稿日期:2005-10-13第23卷 第11期计 算 机 仿 真2006年11月文章编号:1006-9348(2006)11-0184-04物证复原系统中的碎纸轮廓提取技术研究张欣,卜彦龙,朱良家,周宗潭(国防科学技术大学机电工程与自动化学院自动控制系,湖南长沙410073)摘要:碎纸自动拼接复原技术是计算机视觉和模式识别领域内的问题。
它在司法鉴定、历史研究、故障分析等领域都有着重要的应用。
碎纸轮廓提取是其中的关键技术,它直接影响着碎纸拼接结果的精度和效率。
现有的碎纸轮廓提取方法一般是采用主动轮廓、聚类、阈值分割等方法,得到的结果存在大量的噪声,而且轮廓线一般不封闭。
水平集方法是一种描述曲线以曲率相关的速度演化的有效方法,最近几年在医学图像处理、自然现象的模拟以及计算机视觉等领域得到了广泛的应用。
该文给出了一种基于链码的水平集方法,在水平集中,结合链码的易于表示形状的特点,能有效的克服上述缺点,实验效果良好。
关键词:碎纸拼接;轮廓提取;水平集;链码中图分类号:TP391.4 文献标识码:BT echni que of Paper Frag m ents Contour E xtracti on forEvi dence Reconstructi on Syste mZ HANG X i n ,BU Y an-long ,Z HU L iang-jia ,Z HOU Zong-tan(Co llege o fM echatronics Eng i neeri ng and A uto m ati on ,N a ti ona lU n i ve rsity o f D efense T echno l ogy ,Changsha H unan 410073,Ch i na)ABSTRACT :A uto m atic reassemb l y o f frag m ents is an i m portant proble m i n the fi e l ds o f computer vision and pattern recogn iti on .It is appli ed to forensic identifi cation ,h i stor i ca l resea rch ,and m alfunction ana l ys i s ,etc .Curren t ap proaches for fragm ent contou r ex trac ti on are m ostly based on snake ,cl uster i ng ,thres ho l d ,wh ich m ay result i n m uch no ise as w e ll as unc l o sed contours .L eve l set m et hod is a pow erf u l tool fo r tracking t he evo l u tion o f fronts propagati ng w ith curvature dependent speed .R ecently ,lev el se tm e t hod has been used in a w i de co llecti on o f proble m s such as m edical i m age process i ng ,the si m ulati on of natura l pheno m enon and computer v i sion .In t h is paper ,a ne w cha i n-code-based leve l se t approach i s proposed to e li m ina te the abov e d isadvan tages .Cha i n code ,a pow erful shape de scr i ption me t hod is introduced to t he leve l set ,and exper i m ents show that this m e t hod i s e ffective and can produce sa ti sfactory results .KEY W ORDS :F ragm ent reasse m bly ;Con t our ex tracti on ;Cha i n code ;L eve l se t1 引言碎纸自动拼接复原技术在司法鉴定、历史研究、、故障分析等领域都有着广泛的应用。
近年来,随着德国 斯塔西 文件的恢复工程的公布,碎纸文件复原技术的研究引起了人们的广泛关注。
目前在司法技术鉴定等领域,碎纸的拼接工作大部分都是靠人工的方式完成。
虽然国外对这项工作进行了一些研究[1,2],但是由于碎纸的自动修复技术应用背景的特殊性,目前几乎没有公开的研究资料可以参考。
针对人工撕毁的碎纸片,我们利用计算机处理的方法开发了一个以计算机自动处理为主,人为干预为辅,具有可交互性的碎纸自动拼接系统。
它主要由图像预处理和图像匹配两部分组成。
图像预处理包括图像扫描、图像分割、特征提取等。
图像匹配包括形状匹配,纹理匹配等。
其中比较关键的技术为特征提取,它直接影响着碎纸拼接结果的效率和准确性。
在特征提取的过程中我们所利用的主要是碎纸轮廓的形状特征。
利用相邻碎纸之间轮廓形状的相似性,来进行局部拼接。
本文主要应用L evel Set 方法[3]对扫描的碎纸图像进行分割[4]。
L eve l Set 方法是由和[3]提出来的,他将两维(三维)的闭合曲线(曲面)演化问题转化为三维(四维)空间中水平集函数曲面演化的隐含方式来求解,因此能自动处理曲线在搜索物体轮廓时的拓扑结构变化。
根据碎纸图像分割的特点,在L eve l Set 方法中引入了链码的概念,取得了很好的实验结果。
2 水平集方法L eve l Se t 方法是对曲线运动方程的一种数值解法,基本数学思想是:将当前正在演化的曲线C (t)看作是一个更高维函数 (t)的L eve l Se t ,这样在曲面 (t)保持函数性的情况下实现了曲线C (t)进化时拓扑结构的自由变化。
基本方法为,定义一个距离函数: (x,y,t)=∀d ,其中d 表示从点(x,y )到曲线C 的最短距离,函数的符号取决于该点是在曲线的内部还是外部,通常我们把曲线的内部点的距离设为负值外部为正值。
则曲线C (t)可以用距离函数 (x,y,t)的零水平集来表示,即C (t)={(x,y ): (x,y,t)=0}。
如图1所示。
图1 水平集示意图现在我们的目标就是解曲线的进化方程,根据曲线演化理论,由于曲线上的点始终满足 (x,y,t)=0,其沿着法线方向上的演化同等与解偏微分方程:t=F | |, (x,y,0)= 0(x,y )(1)设{(x,y ), 0(x,y )=0}表示初始轮廓,F 为曲线上各点的运动速度。
因为各点的运动方向是沿着曲线的法线方向,所以方程可以简化为标准的H a m ilton-Jacob i 方程。
于是通过将二维空间扩展为三维空间时,曲线C 的演化问题转化为偏微分方程 (x,y )的求解问题,同时曲线C 的拓扑结构变化并不影响 (x,y )的求解。
速度函数F 可以分解为两部分:F =F A +F G 。
其中F A 表示与曲率无关的不变成份,根据距离函数的符号,控制曲线的收缩和膨胀,相当于传统主动轮廓模型中的气球力。
F G 表示与曲率相关的可变成份,控制曲线的平滑性。
为了让曲线达到目标的边界处停止,还需要定义一个边缘停止函数,设图像为u 0,边缘停止函数g 可以表示为g(u 0)=11+| G (x,y )*u 0(x,y )|n,n #1(2)其中G (x,y )*u 0(x,y )是图像u 0与高斯函数G (x,y )的卷积,当曲线到达目标边界处时,g (u 0)趋近于零。
把G =F A +F G 和g(u 0)带入到方程式1中,方程式1改写为t=g (u 0)(F A | |+F G | |), (x,y,0)= 0(x,y )(3)为了得到方程的数值解,用有限差分方法对 进行离散化。
设!t 为时间步长,(x i ,y i )表示栅格坐标,则 n i ,j = (x i ,y j ,n ∀t)为 (x,y,t)的近似表示,这里有n #0, 0= 0,并设D -x ij = ij - (i-1)j ,D +xij = (i+1)j - ijD 0x ij =( (i+1)j - (i-1)j )/2,D -y ij= ij - i(j -1),D +y ij = i(j+1)- ij ,D 0yij =( i(j+1)- i(j-1))/2根据O sher-Se thian 求解水平集的 熵守恒 差分方程,得到方程的递归解形式为(n+1)ij=(n)ij -!t g ^(u 0){[(m ax (D -x ij ,0)2+m in (D +x ij ,0)2+m ax (D -y ij ,0)2+m in (D +x ij ,0)2)1/2-#k ((D 0x ij )2+(D 0y ij )2)1/2]}(4)其中k 为曲线的曲率,k =xx 2y -2 x y x y + yy 2x ( 2x + 2y)3/2。
这种方法的主要缺点就是计算量太大,由于是将曲线的进化问题扩张到高维空间中曲面的演化,而且每次迭代过程中都要对图像中的每个像素点进行更新,当数据量很大时必然会使计算的效率的降低。
其次,由于引进了边缘停止函数,在实际应用中,在目标轮廓处边缘停止函数几乎都不为零,导致进化曲线最终跃过目标边缘。
最后,算法对有噪声的图像不能正确的搜索到边界处,需要对图像进行预处理。
Chan 和V ese 提出了一种基于简化M u m ford-Shah 区域最优化分的图像分割模型[5,6],可以改善上述现象,设定义域为∃的图像I (x,y )被闭合边界C 分为目标%0(曲线的内部)和背景%b (曲线C 的外部)两个同质区域,各区域的平均灰度为C o 和C b ,该模型的能量函数定义为E (C,c o ,c b )=u ∃L eng t h (C )+v ∃A r ea(ins i d e(C ))+&o%n side(C )|I (x,y )-c o |2dxdy +&b%o utside(C )|I (x,y )-c b |2dxdy(5)其中,L eng th(C )是闭合轮廓线C 的长度,A rea (inside(C ))是曲线C 的内部区域面积,u,v #0,&o ,&b >0为各项权重系数。
