Assembling of noisy measured apictorial jigsaw puzzle by the curvature of contours using a corrotational beam spline

Automatic assembly of apictorial two-dimensional jigsaw puzzles is a typical problem of determining the correspondence between segments of two different curves (curve matching). Historically, this has been one of the earliest problems in such an important branch of computer science as pattern recognition. Curve matching is used in computer vision; reconstruction of destroyed paper documents or banknotes; archaeological restoration of mosaics, ornaments, pottery; interpretation of medical diagnostics results; and so on. A significant problem in these studies is the ordering of contour points, which are usually discrete and inaccurately determined by technical means due to the object’s volume, lighting and color peculiarities, and environmental contamination characteristics. All this necessitates smoothing and interpolation of the obtained points. However, smoothing also leads to the loss of useful information. The problem is further complicated by the fact that matching criteria are based on comparing the curvatures of adjacent lines, while the effect of measurement errors and their smoothing on calculated curvatures is insufficiently studied in the literature. The article considers a jigsaw puzzle containing 60 elements. Sides of all pieces are digitized using a medium-resolution camera. A conditional boundary is determined between the pixels of a piece and the general background. Typically, the constructed puzzle contour contains between 2000 and 3500 pixels. Then, a continuous curve is built using an original beam-based corotational spline, which treats the contour as a flexible beam, while the measurement points act as spring supports, with their stiffness controlling the degree of smoothing. A feature of the implemented method is that during calculation, the initially noisy boundary points may change their computed positions, which leads to the need for their renumbering. To address this, the concept of a projection of a measured point onto the calculated contour is introduced, defined as the nearest point, and renumbering is performed according to these projection sequences. To determine the corner points of a puzzle element, the points of maximum curvature are first found, where a so-called imaginary point is introduced. Unlike real points, here the condition of angular continuity of the contour is not fixed, and an angle jump occurs, the magnitude of which is obtained by minimizing the integral of the square of curvature in the vicinity of this vertex. The corner points divide the puzzle into four different contour segments. The correspondence between contours of different puzzle pieces (i.e., automatic assembly of the whole puzzle) is determined by minimizing the integral of the square of the difference of curvatures between two adjacent contour segments. Practical calculations and automatic puzzle assembly confirmed the effectiveness of the proposed method.