Укладання неточно оцифрованого безколiрного пазла по кривизнiконтурiв за допомогою коротацiйного балкового сплайна
DOI:
https://doi.org/10.17721/2706-9699.2025.2.01Ключові слова:
двовимiрний пазл, кутовi точки, балковий коротацiйний сплайн, узгодження кривих, згладжування, перенумерацiя точок контуруАнотація
Автоматичне укладання безколiрних iграшкових двовимiрних пазлiв є типовою задачею визначення зiставлення дiлянок двох рiзних кривих (curve matching). Це iсторично є однiєю з найперших задач в такому важливому напрямку комп’ютерних наук як розпiзнавання образiв. Визначення вiдповiдностi кривих застосовується в комп’ютерному зору; вiдтвореннi знищених паперових документiв чи банкнот; археологiчних вiдновленнях мозаїк, прикрас, посуду; тлумаченнях результатiв медичного дiагностування; тощо. Значною проблемою в цих дослiдженнях є упорядкування контурних точок, котрi зазвичай є дискретними i неточно визначеними технiчними засобами за рахунок об’ємностi предмета, особливостей освiтлення i кольору, характеристик забрудненостi навколишнього середовища. Все це призводить до необхiдностi згладжування i iнтерполяцiї отриманих точок. Проте згладжування призводить i до втрати корисної iнформацiї. Задача ускладнюється тим, що критерiї спiвставлення основанi на порiвняннi кривизн сумiжних лiнiй, а вплив похибок вимiрювання i їх згладжування на розрахунковi кривизни в лiтературi є недостатньо дослiдженим.
В статтi розглядається iграшковий пазл, що мiстить 60 елементiв. Для цього всi елементiв оцифровуються за допомогою фотоапарата середньої роздiльної здатностi. Визначаються умовна границя мiж пiкселями елемента i загального фону. Зазвичай побудований контур пазла мiстить вiд 2000 до 3500 пiкселiв. Потiм будується неперервна крива за допомогою оригiнального балкового коротацiйного сплайну, що розглядає контур як гнучку балку, а точки вимiру як пружиннi опори, величина жорсткостi яких контролює степiнь згладжування. Особливiстю реалiзованої методики є те, що в процесi розрахунку початково зашумленi точки границi можуть змiнювати своє розрахункове положення, що призводить до необхiдностi їх перенумерацiї. Для цього вводиться поняття проекцiї замiряної точки на розрахований контур, як найближчої точки, i перенумерацiя вiдбувається по цих проекцiях-вiдповiдниках. Для визначення кутових точок елемента (пазла) спочатку знаходяться точки найбiльшої кривизни, де вводиться так звана уявна точка. На вiдмiну вiд реальних точок тут не фiксується умова кутової неперервностi контуру, i вiдбувається стрибок кутiв, величина якого отримуються шляхом мiнiмiзацiї iнтеграла вiд квадрату кривизни в околi цiєї вершини. Кутовi точки розбивають пазл на чотири рiзних дiлянки контури. Вiдповiднiсть мiж контурами рiзних пазлiв (тобто автоматичне збирання всього пазла) визначається шляхом мiнiмiзацiї iнтегралу вiд квадрата рiзницi кривизн двох сумiжних дiлянок контуру.
Практичнi розрахунки i автоматичне складання пазлу засвiдчили ефективнiсть запропонованого методу.
Посилання
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.
