Pictorial and apictorial polygonal jigsaw puzzles from arbitrary number of crossing cuts
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914470151847936 |
|---|---|
| author | Shahar, Peleg Harel Ofir Itzhak Ben-Shahar, Ohad |
| author_facet | Shahar, Peleg Harel Ofir Itzhak Ben-Shahar, Ohad |
| contents | Jigsaw puzzle solving, the problem of constructing a coherent whole from a set of non-overlapping unordered visual fragments, is fundamental to numerous applications, and yet most of the literature of the last two decades has focused thus far on less realistic puzzles whose pieces are identical squares. Here, we formalize a new type of jigsaw puzzle where the pieces are general convex polygons generated by cutting through a global polygonal shape with an arbitrary number of straight cuts, a generation model inspired by the celebrated Lazy caterer sequence. We analyze the theoretical properties of such puzzles, including the inherent challenges in solving them once pieces are contaminated with geometrical noise. To cope with such difficulties and obtain tractable solutions, we abstract the problem as a multi-body spring-mass dynamical system endowed with hierarchical loop constraints and a layered reconstruction process. We define evaluation metrics and present experimental results on both apictorial and pictorial puzzles to show that they are solvable completely automatically. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2008_07644 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Pictorial and apictorial polygonal jigsaw puzzles from arbitrary number of crossing cuts Shahar, Peleg Harel Ofir Itzhak Ben-Shahar, Ohad Computer Vision and Pattern Recognition Artificial Intelligence Computational Geometry Jigsaw puzzle solving, the problem of constructing a coherent whole from a set of non-overlapping unordered visual fragments, is fundamental to numerous applications, and yet most of the literature of the last two decades has focused thus far on less realistic puzzles whose pieces are identical squares. Here, we formalize a new type of jigsaw puzzle where the pieces are general convex polygons generated by cutting through a global polygonal shape with an arbitrary number of straight cuts, a generation model inspired by the celebrated Lazy caterer sequence. We analyze the theoretical properties of such puzzles, including the inherent challenges in solving them once pieces are contaminated with geometrical noise. To cope with such difficulties and obtain tractable solutions, we abstract the problem as a multi-body spring-mass dynamical system endowed with hierarchical loop constraints and a layered reconstruction process. We define evaluation metrics and present experimental results on both apictorial and pictorial puzzles to show that they are solvable completely automatically. |
| title | Pictorial and apictorial polygonal jigsaw puzzles from arbitrary number of crossing cuts |
| topic | Computer Vision and Pattern Recognition Artificial Intelligence Computational Geometry |
| url | https://arxiv.org/abs/2008.07644 |