Assembling of noisy measured apictorial jigsaw puzzle by the curvature of contours using a corrotational beam spline
DOI:
https://doi.org/10.17721/2706-9699.2025.2.01Keywords:
two-dimensional jigsaw puzzle, corner points, beam corotational spline, curve matching, smoothing, renumbering of contour pointsAbstract
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.
References
McBride J.C., Kimia B.B. Archaeological fragment reconstruction using curve matching. Proc. IEEE Conf. Computer Vision and Pattern Recognition Workshop. 2003. Vol. 1. P. 3–3.
Kleber F., Sablatnig R. A survey of techniques for document and archaeology artefact reconstruction. Proc. 10th Int. Conf. Document Analysis and Recognition. 2009. P. 1061–1065.
Sizikova E., Funkhouser T. Wall painting reconstruction using a genetic algorithm. J. Comput. Cult. Herit. 2017. Vol. 11. No. 1. P. 1–17.
Justino E., Oliveira L.S., Freitas C. Reconstructing shredded documents through feature matching. Forensic Science International. 2006. Vol. 160. No. 2–3. P. 140–147.
Yilmaz S., Nabiyev V.V. Comprehensive survey of the solving puzzle problems. Computer Science Review. 2023. Vol. 50. 100586.
Marande W., Burger G. Mitochondrial DNA as a genomic jigsaw puzzle. Science. 2007. Vol. 318. No. 5849. P. 415.
Markaki S., Panagiotakis C. Jigsaw puzzle solving techniques and applications: a survey. The Visual Computer. 2023. Vol. 39. No. 10. P. 4405–4421.
Lindstrom M. The geological development of the arctic. In: The Arctic. Routledge, 2019. P. 3–25.
Warren L., Quaglio F., Riccomini C., Simees M., Poire D., Strikis N., Anelli L., Strikis P. The puzzle assembled: Ediacaran guide fossil Cloudina reveals an old proto-Gondwana seaway. Geology. 2014. Vol. 42. No. 5. P. 391–394.
Cho T.S., Avidan S., Freeman W.T. The patch transform. IEEE Trans. Pattern Anal. Mach. Intell. 2010. Vol. 32. No. 8. P. 1489–1501.
Gope C., Kehtarnavaz N., Hillman G., Warsig B. An affine invariant curve matching method for photo-identification of marine mammals. Pattern Recognition. 2005. Vol. 38. No. 1. P. 125–132.
Freeman H., Garder L. Apictorial jigsaw puzzles: The computer solution of a problem in pattern recognition. IEEE Trans. Electronic Computers. 1964. No. 2. P. 118–127.
Goldberg D., Malon C., Bern M. A global approach to automatic solution of jigsaw puzzles. Proc. 18th Annual Symp. Computational Geometry. 2002. P. 82–87.
Levine M.D. Feature extraction: A survey. Proc. IEEE. 1969. Vol. 57. No. 8. P. 1391–1407.
Wolfson H., Schonberg E., Kalvin A., Lamdan Y. Solving jigsaw puzzles by computer. Annals of Operations Research. 1988. Vol. 12. No. 1. P. 51–64.
Schwartz J.T., Sharir M. Identification of partially obscured objects in two and three dimensions by matching noisy characteristic curves. Int. J. Robotics Research. 1987. Vol. 6. No. 2. P. 29–44.
Wolfson H.J. On curve matching. IEEE Trans. Pattern Anal. Mach. Intell. 1990. Vol. 12. No. 5. P. 483–489.
Stieber A., Schneider J., Nickolay B., Kruger J. A contour matching algorithm to reconstruct ruptured documents. Joint Pattern Recognition Symp. Berlin: Springer, 2010. P. 121–130.
Cohen I., Ayache N., Sulger P. Tracking points on deformable objects using curvature information. Proc. ECCV’92. Springer, 1992. P. 458–466.
Sebastian T.B., Crisco J.J., Klein P.N., Kimia B.B. Constructing 2D curve atlases. Proc. IEEE Workshop Mathematical Methods in Biomedical Image Analysis. 2000. P. 70–77.
Sebastian T.B., Klein P.N., Kimia B.B. On aligning curves. IEEE Trans. Pattern Anal. Mach. Intell. 2003. Vol. 25. No. 1. P. 116–125.
Zafar S., Hussain M. Fair curve designing by Said-Ball curve. PLoS One. 2025. Vol. 20. No. 7. e0324553.
Brunnett G., Kiefer J. Interpolation with minimal-energy splines. Computer-Aided Design. 1994. Vol. 26. No. 2. P. 137–144.
Orynyak I., Kuznetsov Y., Tavrov D. Efficient construction of clothoidal splines using corotational beam splines. J. Comput. Appl. Math. (in press).
Mokhtarian F., Mackworth A. Scale-based description and recognition of planar curves and 2D shapes. IEEE Trans. Pattern Anal. Mach. Intell. 1986. No. 1. P. 34–43.
Banchoff T.F., Lovett S. Differential geometry of curves and surfaces. Chapman and Hall/CRC, 2022. 410 p.
Goldberg D., Malon C., Bern M. A global approach to automatic solution of jigsaw puzzles. Computational Geometry. 2004. Vol. 28. No. 2–3. P. 165–174.
Michel D., Oikonomidis I., Argyros A. Scale invariant and deformation tolerant partial shape matching. Image Vision Comput. 2011. Vol. 29. No. 7. P. 459–469.
Eubank R.L. Nonparametric regression and spline smoothing. CRC Press, 1999. 350 p.
Cheng K.F., Lin P.E. Nonparametric estimation of a regression function. Z. Wahrscheinlichkeitstheorie verw. Gebiete. 1981. Vol. 57. No. 2. P. 223–231.
Clark R.M. Non-parametric estimation of a smooth regression function. J. R. Stat. Soc. Ser. B. 1977. Vol. 39. No. 1. P. 107–132.
Moreton H.P. Minimum curvature variation curves, networks, and surfaces for fair free-form shape design. PhD Thesis, Univ. California, Berkeley, 1992. 250 p.
Lee E.T. Choosing nodes in parametric curve interpolation. Computer-Aided Design. 1989. Vol. 21. No. 6. P. 363–370.
Ruppert D. Selecting the number of knots for penalized splines. J. Comput. Graph. Stat. 2002. Vol. 11. No. 4. P. 735–757.
Reinsch C.H. Smoothing by spline functions. Numerische Mathematik. 1967. Vol. 10. No. 3. P. 177–183.
Bruckstein A.M., Netravali A. On minimal energy trajectories. Computer Vision, Graphics, and Image Processing. 1990. Vol. 49. P. 283–297.
Manay S., Cremers D., Hong B.W., Yezzi A.J., Soatto S. Integral invariants for shape matching. IEEE Trans. Pattern Anal. Mach. Intell. 2006. Vol. 28. No. 10. P. 1602–1618.
Cui M., Femiani J., Hu J., Wonka P., Razdan A. Curve matching for open 2D curves. Pattern Recognition Letters. 2009. Vol. 30. No. 1. P. 1–10.
Fu H., Tian Z., Ran M., Fan M. Novel affine-invariant curve descriptor for curve matching and occluded object recognition. IET Computer Vision. 2013. Vol. 7. No. 4. P. 279–292.
Hoff D.J., Olver P.J. Extensions of invariant signatures for object recognition. J. Math. Imaging Vision. 2013. Vol. 45. No. 2. P. 176–185.
Hoff D.J., Olver P.J. Automatic solution of jigsaw puzzles. J. Math. Imaging Vision. 2014. Vol. 49. P. 234–250.
Kurnianggoro L., Jo K.H. A survey of 2D shape representation: Methods, evaluations, and future research directions. Neurocomputing. 2018. Vol. 300. P. 1–16.
Orynyak I., Kuznetsov Y., Mazuryk R. Controllable curvature smoothing of the pipeline positions by 2D corotational beam spline. J. Pipeline Syst. Eng. Pract. 2025. Vol. 16. No. 3. 04025047.
Orynyak I., Yablonskyi P., Koltsov D., Chertov O., Mazuryk R. Fairness of 2D corotational beam spline as compared with geometrically nonlinear elastic beam. System Research and Information Technologies. 2024. No. 3. P. 119–140.
Orynyak I., Koltsov D., Chertov O., Mazuryk R. Application of beam theory for the construction of twice differentiable closed contours based on discrete noisy points. System Research and Information Technologies. 2022. No. 4. P. 119–140.
Holladay J.C. A smoothest curve approximation. Math. Tables Aids Comput. 1957. Vol. 11. P. 233–243.
Mehlum E. A curve-fitting method based on a variational criterion. BIT Numerical Mathematics. 1964. Vol. 4. P. 213–223.
Fowler A.H., Wilson C.W. Cubic Spline, a Curve Fitting Routine. Oak Ridge: Union Carbide Corp., Nuclear Division, 1966. 41 p.
