An Algorithm For Fragments Re-assembly Based On U-chord Curvature

2-D fragments re-assembly has been an interesting research in the field of computervision and image analysis. Since the number of fragments could be very large, manualoperation of this task is impossible. To overcome this difficulty, an algorithm for fragmentre-assembly is proposed in this paper.Firstly, a new measure of discrete curvature, called the U-chord curvature, isintroduced. For each point on a digital curve, its support region is determined with twopoints which have a given chord distance to the point, and then its U-chord curvature isestimated. A theoretical analysis shows that there exists a close relationship between theU-chord curvature and the real curvature of the considered curve. Compared to the existingmeasures of discrete curvature, the U-chord curvature is more stable under rotationtransformations and in the presence of noise. It is therefore suitable for image and visiontasks which require a high stability of curvature estimation(such as curve matching).Secondly, the algorithm for fragment re-assembly is proposed, which is based on theU-chord curvature. After digitalization and preprocessing, the shape data of the fragementsare extracted by edge detection and tracing. With the help of corner points, the input shapeis segmented into several parts. On each curve part, points are sampled with a fix steplength and the U-chord curvature is computed at each point, resulting a U-chord curvaturelist to represent the curve segment. Two curve segments that have the closest U-chordcurvature lists are recognized as a matching pair. The fragment re-assembly isaccompalished by using this operation circularly.Representative curves taken from the literature and the MPGE-7shape database areused to test the stability of the U-chord curvature, and a detailed demonstration of theBeijing map re-assembly shows the efficiency of the new algorithm.