Current Issue Cover
拱序列的曲线描述与匹配

危辉, 李俐瑢(复旦大学计算机科学技术学院, 上海 201203)

摘 要
目的 曲线匹配是计算机视觉和图像处理中的一个重要问题;判定几何图形形状相似性,得到与人类认知一致的结果,是目前的曲线描述与分类算法不能很好解决的问题。针对曲线匹配和几何图形形状的相似性判定,提出一种有效快速的基于拱序列的曲线匹配与相似性判定算法。方法 提取曲线的角点,将曲线表示为一连串相互重叠的拱序列。对于拱序列中的每一个拱,使用拱描述子进行描述。利用拱描述子,使用动态规划方法,实现对拱序列的匹配和相似性判定。结果 为了验证本文算法,将基于拱序列的曲线描述与匹配方法应用于轮廓的拼接与几何图形的相似性比较。在轮廓拼接实验中,基于拱序列的曲线描述与匹配方法准确完成碎片轮廓的拼接和地图轮廓的拼接。在几何图形相似性的交叉度量实验中,基于拱序列的曲线描述与匹配方法可以准确反映出图形的相似程度,正确判断两幅图像是否属于同一类型。在判定不同相似程度的形状对的实验中,本文算法可以给出与人类判断相同的结果,相比较基于链码特征、多尺度不变量、形状上下文和GCT(geometry complex transform)变换算法,本文算法的距离值更好地反映出图像的相似程度。结论 理论和实验表明,该算法可有效地描述曲线、匹配曲线,及准确判断几何图形的相似性,给出与人类视觉判定一致的结果。该算法可用于基于轮廓的图像拼接和几何图形相似性的判定。
关键词
Curve description and matching using arch sequence

Wei Hui, Li Lirong(School of Computer Science, Fudan University, Shanghai 201203, China)

Abstract
Objective Curve matching is a significant problem in computer vision and image processing.It has a wide range of applications in cultural debris splicing, medical image registration, and product testing.Given the importance of curve description and matching, scholars have conducted numerous research and have made significant progress in this field.However, several problems still exist due to the relatively high practical application requirements.At present, many common curve-matching methods can obtain acceptable classification results.However, for the geometric shape similarity problem, the results obtained by these methods cannot accurately reflect the similarity of geometric shape and are inconsistent with human cognition.An acceptable shape descriptor can effectively differentiate the target shape.Moreover, the descriptor of the target shape should remain unchanged even with the translating, rotating, and scaling of the target shape.To achieve the purpose of valid curve description, this study presents a curve description method based on arch sequence.Curve matching is usually based on the curve description method, using a certain metric to determine the degree of similarity between curves.To achieve the curve matching accurately and quickly, an arch sequence matching method based on dynamic programming is proposed according to the curve description method of the arch sequence.The similarity degree of the two curves is determined according to the similarity degree of the two arch sequences.Method For curve matching, the characteristic descriptor of the curve is initially defined and this descriptor is used to describe the curve.The appropriate method is used to match the curves based on the curve description.The corners of the curve are initially extracted to realize the curve description based on the arch sequence, and the curve is divided into a series of sub-curves by corners.All adjacent two sub-curves can be combined to form an arch.A contour curve can be expressed as a sequence of successive overlapping arches using an arch composed of sub-curves to represent the curve.For each arch in the arch sequence, the ratios of bow height to chord length, of bow height half-chord length to chord length, and of arc length to chord length, and the sine of the chord angle and the connection of bow high point to the midpoint of the chord are used to describe the arch.Calculating the degree of similarity between the corresponding arch sequences is necessary.Defining the distance between one arch and the other is necessary in calculating the degree of similarity between arch sequences.The ratio of bow height to chord length and other related eigenvalues are used to calculate the distance between the arches.The idea of edit distance of the string in the dynamic programming method is adopted to calculate the minimum cost of converting an arch sequence into another arch sequence, thereby obtaining the similarity between arch sequences quickly and accurately.The distance between the curves can be obtained using the edit distance between the arch sequences.Result The curve description and matching method based on the arch sequence are used to stitch the contours and compute the similarity of the geometric figures, thereby verifying the effectiveness of the proposed method.To verify whether this method can be applied to contour splicing, the method is initially applied to the splicing of two fragments and then to the splicing of two map contours.In the splicing experiment of fragments and map contours, the fragments and map contours are concisely stitched together using the curve description and matching method based on the arch sequence.A similarity measure is performed in a geometric test library to verify that the method can determine whether the geometries belong to the same type.In the cross-measurement experiment of geometric similarity, the curve description and the matching method based on arch sequence can accurately reflect the similarity of the graph.The similarity of the graph can accurately judge whether the two images belong to the same type.This method is used to calculate the similarity degree of the six groups of geometric shapes, thereby verifying that the method can reflect the similarity of geometric pairs.This method can provide the same result as human judgment in the comparative experiment between geometric shape and similarity.The method has better distance value to reflect the similarity of the image, compared with the method of chain code feature, multiscale invariant, shape context, and geometry complex transform(GCT).Conclusion This study presents a curve description and matching method based on arch sequence.In this method, the contour curve is expressed as an arch sequence.The dynamic programming method is used to realize the curve matching based on the arch sequence.The algorithm can effectively describe, match the curve, and provide low time complexity.In this study, the curve description and matching method based on arch sequence is applied to the simulation experiment of stitching contours, the cross-measurement experiment of geometric similarity, and the comparison experiment of geometric similarity degree.The method can accurately stitch the contours, judge the similarity of the geometric figures, and provide results that are consistent with the human visual judgments.For the geometric shapes with different degrees of similarity, the distance between the arch sequences can also effectively reflect the difference.
Keywords

订阅号|日报