SCIENTIA SINICA Informationis, Volume 51 , Issue 2 : 206(2021) https://doi.org/10.1360/SSI-2019-0150

## Solving pictorial jigsaw puzzles via Internet-based collective intelligence

• AcceptedSep 24, 2019
• PublishedFeb 1, 2021
Share
Rating

### Supplement

Appendix

$\bullet$ $(a_i)_1^K$: 数列$a_1,~a_2,~\ldots,~a_{K}$.

$\bullet$ $|\mathcal{S}|$: 集合或数列$\mathcal{S}$中包含的元素的数量.

$\bullet$ 给定一个图$G$, $\mathcal{V}(G)$表示其节点集合, $\mathcal{E}(G)$表示其边集合.

$\bullet$ 给定图$G$中的一个节点$v~\in~\mathcal{V}(G)$, $d(v)$表示节点$v$的度, 即: 节点$v$参与到了几条边中.

$\bullet$ 给定图$G$中的一条边$e~\in~\mathcal{E}(G)$, $\mathcal{V}(e)$表示由$e$两端的两个节点构成的集合.

$\bullet$ $\mathbf{1}(x)$: 一个谓词函数. 当传入的谓词$x$为真, 该函数返回1; 否则, 返回0.

(1) $\forall~i~\in~[1,~K)~:~(a_i~-~a_{i+1})~\le~\epsilon~|a_i|~\Rightarrow~\lceil~(a_i)_{1}^{K}~\rceil^\epsilon=~(a_i)_{1}^{K}$,

(2) $\exists~i~\in~[1,~K)~:~(a_i~-~a_{i+1})~>~\epsilon~|a_i|~\Rightarrow~\lceil~(a_i)_{1}^{K}~\rceil^\epsilon~=~(a_i)_{1}^{J}~\land~J~\in~[1,~K)~\land~(\forall~k~\in~[1,~J)~:~(a_k~-~a_{k+1})~<~(a_J~-~a_{J+1}))~\land~(\forall~k~\in~[J+1,~K)~:~(a_k~-~a_{k+1})~\le~(a_J~-~a_{J+1}))$.

beginproperty

endproperty

### References

[1] Torsvik T H. Geology. The Rodinia jigsaw puzzle.. Science, 2003, 300: 1379-1381 CrossRef PubMed Google Scholar

[2] Burkitt D P. Editorial: Large-bowel cancer: an epidemiologic jigsaw puzzle.. -J Natl Cancer Institute, 1975, 54: 3-6 CrossRef PubMed Google Scholar

[3] Brimacombe R. The Structure of Ribosomal RNA: A Three-Dimensional Jigsaw Puzzle. Eur J Biochem, 1995, 230: 365-383 CrossRef Google Scholar

[4] Verweij M, Thompson M. Clumsy Solutions for a Complex World: Governance, Politics and Plural Perceptions. London: Palgrave Macmillan, 2006. Google Scholar

[5] Zhang W, Mei H. Software development based on Internet collective intelligence: feasibility, state-of-the-practice, and challenges. Sin Chin Inform, 2017, 47: 1601--1622. Google Scholar

[6] Theraulaz G, Bonabeau E. A brief history of stigmergy.. Artificial Life, 1999, 5: 97-116 CrossRef PubMed Google Scholar

[7] Karsai I. Decentralized control of construction behavior in paper wasps: an overview of the stigmergy approach.. Artificial Life, 1999, 5: 117-136 CrossRef PubMed Google Scholar

[8] Susi T, Ziemke T. Social cognition, artefacts, and stigmergy: A comparative analysis of theoretical frameworks for the understanding of artefact-mediated collaborative activity. Cognitive Syst Res, 2001, 2: 273-290 CrossRef Google Scholar

[9] Dorigo M, Bonabeau E, Theraulaz G. Ant algorithms and stigmergy. Future Generation Comput Syst, 2000, 16: 851-871 CrossRef Google Scholar

[10] Freeman H, Garder L. Apictorial Jigsaw Puzzles: The Computer Solution of a Problem in Pattern Recognition. IEEE Trans Electron Comput, 1964, EC-13: 118-127 CrossRef Google Scholar

[11] Berger R. The Undecidability of The Domino Problem. Washington: American Mathematical Society, 1966. Google Scholar

[12] Demaine E D, Demaine M L. Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity. Graphs Combin, 2007, 23: 195-208 CrossRef Google Scholar

[13] Goldberg D, Malon C, Bern M. A global approach to automatic solution of jigsaw puzzles. In: Proceedings of the 18th Annual Symposium on Computational Geometry, Barcelona, 2002. 82--87. Google Scholar

[14] Kong W, Kimia B B. On solving 2D and 3D puzzles using curve matching. In: Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Kauai, 2001. 583--590. Google Scholar

[15] Radack G M, Badler N I. Jigsaw puzzle matching using a boundary-centered polar encoding. Comput Graphics Image Processing, 1982, 19: 1-17 CrossRef Google Scholar

[16] Wolfson H, Schonberg E, Kalvin A. Solving jigsaw puzzles by computer. Ann Oper Res, 1988, 12: 51-64 CrossRef Google Scholar

[17] Kosiba D A, Devaux P M, Balasubramanian S, et al. An automatic jigsaw puzzle solver. In: Proceedings of the 12th IAPR International Conference on Pattern Recognition, Jerusalem, 1994. 616--618. Google Scholar

[18] Makridis M, Papamarkos N. A new technique for solving a jigsaw puzzle. In: Proceedings of International Conference on Image Processing, Atlanta, 2006. 2001--2004. Google Scholar

[19] Nielsen T R, Drewsen P, Hansen K. Solving jigsaw puzzles using image features. Pattern Recognition Lett, 2008, 29: 1924-1933 CrossRef Google Scholar

[20] Yao F H, Shao G F. A shape and image merging technique to solve jigsaw puzzles. Pattern Recognition Lett, 2003, 24: 1819-1835 CrossRef Google Scholar

[21] Cho T S, Avidan S, Freeman W T. A probabilistic image jigsaw puzzle solver. In: Proceedings of the 23rd IEEE Conference on Computer Vision and Pattern Recognition, San Francisco, 2010. 183--190. Google Scholar

[22] Pomeranz D, Shemesh M, Ben-Shahar O. A fully automated greedy square jigsaw puzzle solver. In: Proceedings of the 24th IEEE Conference on Computer Vision and Pattern Recognition, Colorado Springs, 2011. 9--16. Google Scholar

[23] Yang X, Adluru N, Latecki L J. Particle filter with state permutations for solving image jigsaw puzzles. In: Proceedings of the 24th IEEE Conference on Computer Vision and Pattern Recognition, Colorado Springs, 2011. 2873--2880. Google Scholar

[24] Gallagher A C. 2012. Jigsaw puzzles with pieces of unknown orientation. In: Proceedings of the 25th IEEE Conference on Computer Vision and Pattern Recognition, Providence, 2012. 382--389. Google Scholar

[25] Sholomon D, David O E, Netanyahu N S. A genetic algorithm-based solver for very large jigsaw puzzles. In: Proceedings of the 26th IEEE Conference on Computer Vision and Pattern Recognition, Portland, 2013. 1767--1774. Google Scholar

[26] Sholomon D, David O E, Netanyahu N S. An automatic solver for very large jigsaw puzzles using genetic algorithms. Genet Program Evolvable Mach, 2016, 17: 291-313 CrossRef Google Scholar

[27] Son K, Hays J, Cooper D B. Solving square jigsaw puzzles with loop constraints. In: Proceedings of the 13th European Conference on Computer Vision, Zurich, 2014. 32--46. Google Scholar

[28] Parunak H V D. A survey of environments and mechanisms for human-human stigmergy. In: Proceedings of the 2nd International Workshop on Environments for Multi-Agent Systems, Utrecht, 2005. 163--186. Google Scholar

[29] Heylighen F. Collective intelligence and its implementation on the web: algorithms to develop a collective mental map. Comput Math Organization Theor, 1999, 5: 253-280 CrossRef Google Scholar

[30] Malone T, Laubacher R, Dellarocas C. The collective intelligence genome. IEEE Eng Manag Rev, 2010, 38: 38-52 CrossRef Google Scholar

[31] Rosenberg L B. Artificial swarm intelligence, a human-in-the-loop approach to A.I.. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence, Phoenix, 2016. 4381--4382. Google Scholar

[32] Rosenberg L B. Human swarms, a real-time method for collective intelligence. In: Proceedings of the 13th European Conference Artificial Life, York, 2015. 658--659. Google Scholar

[33] Lee J, Kladwang W, Lee M. RNA design rules from a massive open laboratory. Proc Natl Acad Sci USA, 2014, 111: 2122-2127 CrossRef PubMed ADS Google Scholar

[34] Levy P. Collective Intelligence: Mankind's Emerging World in Cyberspace. Cambrigde: Perseus Books, 1997. Google Scholar

[35] Woolley A W, Chabris C F, Pentland A. Evidence for a Collective Intelligence Factor in the Performance of Human Groups. Science, 2010, 330: 686-688 CrossRef PubMed ADS Google Scholar

[36] Nielsen M. Reinventing Discovery: the New Era of Networked Science. Princeton: Princeton University Press, 2011. Google Scholar

[37] Maleszka M, Nguyen N T. Integration computing and collective intelligence. Expert Syst Appl, 2015, 42: 332-340 CrossRef Google Scholar

[38] Brabham D C. Crowdsourcing as a Model for Problem Solving. Convergence, 2008, 14: 75-90 CrossRef Google Scholar

[40] Howe J. The rise of crowdsourcing. Wired, 2006, 14: 1--4. Google Scholar

[41] Doan A, Ramakrishnan R, Halevy A Y. Crowdsourcing systems on the World-Wide Web. Commun ACM, 2011, 54: 86-96 CrossRef Google Scholar

[42] Estellés-Arolas E, González-Ladrón-de-Guevara F. Towards an integrated crowdsourcing definition. J Inf Sci, 2012, 38: 189-200 CrossRef Google Scholar

[43] Kittur A, Chi E H, Suh B. Crowdsourcing user studies with Mechanical Turk. In: Proceedings of Conference on Human Factors in Computing Systems, Florence, 2008. 453--456. Google Scholar

[44] Valentine M A, Retelny D, To A, et al. Flash organizations: crowdsourcing complex work by structuring crowds as organizations. In: Proceedings of Conference on Human Factors in Computing Systems, Denver, 2017. 3523--3537. Google Scholar

[45] Kittur A, Nickerson J V, Bernstein M, et al. The future of crowd work. In: Proceedings of Conference on Computer Supported Cooperative Work, San Antonio, 2013. 1301--1318. Google Scholar

[46] Romero J C, Valdez M G. Using a graph based database to support collaborative interactive evolutionary systems. In: Recent Advances on Hybrid Approaches for Designing Intelligent Systems. Berlin: Springer, 2014. 581--591. Google Scholar

• Figure 1

Solving the PJ puzzle collaboratively based on the explore-integration-feedback (EIF) loop

• Figure 2

A candidate solution of a PJ puzzle and its labelled graph representation. (a) A candidate-solution of a PJ puzzle of size 3$\times$4; (b) the labelled graph representation of this candidate-solution

• Figure 3

Deducing edges from existing edges. (a) A connected graph; (b) the connected graphadding two deduced edges

• Figure 4

Screenshot of a player's puzzle-solving workspace

• Figure 5

The average time for player groups with gs $\in~[1,~10]$ to solve PJ puzzle with ps $\in~[4\times4,~10\times10]$. (a) A 3D view; (b) a 2D view

• Figure 6

The puzzle-solving progress of a player group with gs $\in~[1,~10]$ to solve a $10\times10$ PJ puzzle

• Figure 7

Average feedback precision (a) and feedback ratio (b) for different combinations of puzzle size and group size

• Figure 8

Qualitative evaluations from players about the feedback information received in PJ puzzle solving

• Figure 9

Puzzle-solving time and quality of stigmergy-based collaboration, face-to-face collaboration, and auto-solver

• Table 1   The 7 batches of 350 game rounds
 ps gs 1 2 3 4 5 6 7 8 9 10 4$\times$4 7 7 7 7 6 5 4 3 2 1 5$\times$5 6 6 6 6 6 5 4 3 2 1 6$\times$6 5 5 5 5 5 5 4 3 2 1 7$\times$7 4 4 4 4 4 4 4 3 2 1 8$\times$8 3 3 3 3 3 3 3 3 2 1 9$\times$9 2 2 2 2 2 2 2 2 2 1 10$\times$10 1 1 1 1 1 1 1 1 1 1
• Table 2   Time improvement brought by playing as a group, comparing with the best single players
 ps gs 1 (s) 2 (%) 3 (%) 4 (%) 5 (%) 6 (%) 7 (%) 8 (%) 9 (%) 10 (%) 4$\times$4 108.12 26.93 47.51 50.05 63.01 51.91 56.99 53.76 65.78 64.86 5$\times$5 191.50 26.89 34.20 58.23 31.59 64.49 72.32 51.18 45.43 65.83 6$\times$6 244.67 47.28 29.56 16.83 38.49 30.11 41.14 16.49 32.56 64.50 7$\times$7 385.38 36.69 19.50 57.44 55.37 43.95 57.44 38.76 53.03 57.23 8$\times$8 575.18 20.92 43.32 62.62 40.31 36.02 58.62 43.50 49.06 64.88 9$\times$9 821.17 21.58 43.80 40.07 38.25 34.35 42.14 66.26 51.89 62.16 10$\times$10 1432.12 39.20 41.17 55.56 58.03 58.90 68.68 63.72 71.44 72.51 Average 536.88 31.36 37.01 48.69 46.44 45.68 56.76 47.67 52.74 64.57

Citations

Altmetric