Algoritmy pro skládání obrázků

Jigsaw puzzle is a well-known puzzle game that has been around for centuries. How- ever, in addition to entertainment purposes, an ability to reassemble images from pieces has practical applications and can be useful, for example, in restoring torn or cut docu- ments or broken objects in archaeology. Most of the proposed solutions reconstruct the images divided into square pieces. In this work, we propose our solutions for the new types of puzzles with more interesting shapes of pieces, such as rectangles of equal and different sizes, and triangles. The accuracy of our solvers is at the same level as that of the solutions for reconstruction of images from square pieces. Moreover, our solvers, unlike the others, have been tested on images with text as well as on color and black and white photographs. 1Puzzle je dobře známá logická hra, která je známá již několik století. Kromě zábavy má však schopnost skládat obrázky z dílků i praktické využití a může být užitečná napří- klad při rekonstrukci roztrhaných nebo rozstříhaných dokumentů či rozbitých předmětů v archeologii. Většina navržených řešení slouží k rekonstrukci obrázků rozdělených na čtvercové dílky. V této práci my navrhujeme naše řešení pro nové typy puzzle se zají- mavějšími tvary dílků, jako jsou obdélníky stejných a různých velikostí a trojúhelníky. Přesnost našich řešení je na stejné úrovni jako přesnost řešení pro rekonstrukci obrázků ze čtvercových dílků. Naše řešiče byly navíc na rozdíl od ostatních testovány na obrázcích s textem a také na barevných a černobílých fotografiích. 1Department of Theoretical Computer Science and Mathematical LogicKatedra teoretické informatiky a matematické logikyMatematicko-fyzikální fakultaFaculty of Mathematics and Physic