Koltsov, D. R.D. R.KoltsovOrynyak, I. V.I. V.Orynyak2026-02-262026-02-262025-12-25Koltsov, D. R., Orynyak, I. V. (2025). Assembling of noisy measured apictorial jigsaw puzzle by the curvature of contours using a corrotational beam spline. Journal of Numerical and Applied Mathematics(2), 5–32. https://doi.org/10.17721/2706-9699.2025.2.0110.17721/2706-9699.2025.2.01https://ir.library.knu.ua/handle/15071834/10889Automatic 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 curvaturesis 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.Автоматичне укладання безкол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сть запропонованого методу.uktwo-dimensional jigsaw puzzlecorner pointsbeam corotational splinecurve matchingsmoothingrenumbering of contour pointsдвовимiрний пазлкутовi точкибалковий коротацiйний сплайнузгодження кривихзгладжуванняперенумерацiя точок контуруСтаття