The Contour Matching Technology And Implementation Based On Improved Levenshtein Distance Algorithm

Shredded paper stitching is a typical branch in the image processing field.It is widely used in military intelligence acquisition,judicial forensics,archaeological restoration and other fields.When dealing with a few object fragments,artificial stitching can effectively restore the original appearance of the broken object.However,for archaeological artifacts,the number of cultural relics is generally very large.At this time,artificial stitching will make the stitching work more complicated.It not only consumes a lot of human resources and material resources,but also may cause secondary damage to unearthed cultural relics.Therefore,it is very necessary to use computer aided method to complete the stitching of fragments.Computer-assisted stitching technology includes image acquisition,image pre-processing,edge detection,contour matching,and image stitching.Among them,contour matching is the core technology of shredded paper stitching technology,and it is also the focus of this paper.This paper proposed a contour matching technology based on the improved Levenshtein distance algorithm.This technology uses the edit distance to measure the similarity between the contour curves,and it achieves the purpose of contour matching.The main research work in this paper is as follows:1.Detect the contour of shredded paper images using morphological method.In order to facilitate the morphological processing of the image,first of all,we need to preprocess the image.It includes image denoising,image graying,and image binarization.Then,the image I is corroded by using the structural element S with a size of 3×3.Finally,the contour curve can be obtained by subtracting the corroded image from the original image I.2.Extract the contour feature sequence of fragments by sampling method.Its main idea is:(1)Starting from the endpoint of the contour curve,we use the pointer to traverse the contour curve.When the arc length between the starting point and the pointer is equal to L(L is a set value),the horizontal axis coordinate value of the pointer at this time is recorded.(2)Set the position of the current pointer to the new starting point,and continue to traverse this curve according to the method in(1)until the entire curve is traversed.Finally,we will get a column matrix.The set of elements in this matrix is the characteristic sequence of the contour curve.The feature sequence is the result of the dimensionality reduction of the two-dimensional contour curve,which provides a one-dimensional sequence that can represent the contour curve for subsequent matching algorithm.This method transforms the two-dimensional shredded paper image matching problem into a matching problem of dealing with one-dimensional feature sequences,which reduces the dimension and complexity of the matching problem.3.Complete the contour matching by this improved Levenshtein distance algorithm.First of all,this paper expounds several similarity measurement algorithms,such as Minkowski distance,Hamming distance and edit distance,etc.After comparing the advantages and disadvantages of these algorithms,this paper selects the edit distance algorithm as the standard to measure the similarity degree,and improves the Levenshtein distance algorithm.The improved Levenshtein distance can more accurately describe the similarity between the contour curves.Then,in order to make the data more intuitive,we introduce the concept of similarity.Through comparison and analysis of the quantitative relationship between similarity and edit distance,we give its calculation method.Finally,the simulation experiment of the shredded paper is carried out according to the matching program.From the experiment,we can obtain the contour matched with the target contour.This program will stitch the target image with the matched image and fill the gaps between the images to get the final matching stitching result.Applying the Levenshtein distance to contour matching field has great theoretical value and innovative significance.Through experimental analysis,compared with other contour matching methods,this algorithm has the advantages of high programmability and low computational complexity.It provides an idea for solving image matching problems.