Укладання неточно оцифрованого безколiрного пазла по кривизнiконтурiв за допомогою коротацiйного балкового сплайна

Кольцов, Д. Р., Ориняк, I. В. (2025). Укладання неточно оцифрованого безколiрного пазла по кривизнiконтурiв за допомогою коротацiйного балкового сплайна. Журнал обчислювальної та прикладної математики, 2, 5–32. https://doi.org/10.17721/2706-9699.2025.2.01

Автоматичне укладання безкол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сть запропонованого методу.