Physical Match

Authors

  • Aaron E. Naiman Jerusalem College of Technology
  • Eliav Farber
  • Yossi Stein

DOI:

https://doi.org/10.31449/inf.v43i2.1823

Abstract

We present an approach to solving the problem of “physical match,” i.e., reconnecting back together broken or ripped pieces of material. Our method involves correlating the jagged edges of the pieces, using a modified version of the longest common subsequence algorithm.

Author Biography

Aaron E. Naiman, Jerusalem College of Technology

Department of Applied Mathematics

References

F. Bortolozzi, Document reconstruction based on feature matching, in 18th Brazilian Symposium on Computer Graphics and Image Processing, Oct. 2005, pp. 163–170.

J. Canny, A computational approach to edge detection, Pattern Analysis and Machine Intelligence, IEEE Transactions on, 8 (1986),pp. 679–698.

H. C. da Gama Leitao and J. Stolfi, A multiscale method for the reassembly of two dimensional fragmented objects, IEEE Transactions on Pattern Analysis and Machine In-

telligence, 24 (2002), pp. 1239–1251.

A. C. Gallagher, Jigsaw puzzles with pieces of unknown orientation, in Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on, IEEE, 2012, pp. 382–389.

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.

Q.-X. Huang, S. Fl¨ory, N. Gelfand, M. Hofer, and H. Pottmann, Reassembling fractured objects by geometric matching, in ACM Transactions on Graphics (TOG), vol. 25, ACM, 2006, pp. 569–578.

M. Kampel and R. Sablatnig, 3d puzzling of archeological fragments, in Proc. of 9th Computer Vision Winter Workshop, vol. 2, Slovenian Pattern Recognition Society, 2004, pp. 31–40.

F. Kleber and R. Sablatnig, A survey of techniques for document and archaeology artefact reconstruction, in Document Analysis and Recognition, 2009. ICDAR’09. 10th International Conference on, IEEE, 2009, pp. 1061–1065.

D. A. Kosiba, P. M. D. and. S. Balasubramanian, T. L. Gandhi, and K. Kasturi , An automatic jigsaw puzzle solver, in Proceedings of the 12th IAPR International Conference on Pattern Recognition - Conference A: Computer Vision & Image Processing, vol. 1, 1994, pp. 616–618.

H. Liu, S. Cao, and S. Yan, Automated assembly of shredded pieces from multiple photos, Multimedia, IEEE Transactions on, 13 (2011), pp. 1154–1162.

A. E. Naiman, E. Farber, and Y. Stein, CLCS—cyclic longest common subsequence, 2017. submitted.

Edge characterization of digitized images, Aug. 2017. submitted.

EdgeTrek—interior and boundary pixels for large regions, Aug. 2017. submitted.

G. Papaioannou and E.-A. Karabassi, On the automatic assemblage of arbitrary broken solid artefacts, Image and Vision Computing, 21 (2003), pp. 401–412.

Scientific Working Group for Materials Analysis, Glass fractures, Forensic Science Communications, 7 (2005).

Y. SHOR, Y. YEKUTIELI, S. WIESNER, AND T. TSACH, Physical Match, Elsevier, Academic Press, 2 ed., 2013, pp. 54–59. Encyclopedia of Forensic Sciences, ed.: Jay A. Siegel, Pekka J. Saukko, Max M. Houck.

G. ÜÇOLUK AND I. HAKKI TOROSLU, Automatic reconstruction of broken 3-d surface objects, Computers & Graphics, 23 (1999), pp. 573–582.

A. UKOVICH, G. RAMPONI, H. DOULAVERAKIS, Y. KOMPATSIARIS, AND M. G. STRINTZIS, Shredded document reconstruction using MPEG-7 standard descriptors, in Proceedings of the Fourth IEEE International Symposium on Signal Processing and Information Technology, Dec. 2004, pp. 334–337.

H. WOLFSON, E. SCHONBERG, A. KALVIN1, AND Y. LAMDAN, Solving jigsaw puzzles by computer, Annals of Operations Research, 12 (1988), pp. 51–64.

F.-H. YAO AND G.-F. SHAO, A shape and image merging technique to solve jigsaw puzzles, Pattern Recognition Letters, 24 (2003), pp. 1819–1835.

L. ZHU, Z. ZHOU, J. ZHANG, AND D. HU, A partial curve matching method for automatic reassembly of 2d fragments, in Intelligent Computing in Signal Processing and Pattern Recognition, Springer, 2006, pp. 645–650.

Downloads

Published

2019-06-15

How to Cite

Naiman, A. E., Farber, E., & Stein, Y. (2019). Physical Match. Informatica, 43(2). https://doi.org/10.31449/inf.v43i2.1823

Issue

Vol. 43 No. 2 (2019)

Section

Regular papers

License

I assign to Informatica, An International Journal of Computing and Informatics ("Journal") the copyright in the manuscript identified above and any additional material (figures, tables, illustrations, software or other information intended for publication) submitted as part of or as a supplement to the manuscript ("Paper") in all forms and media throughout the world, in all languages, for the full term of copyright, effective when and if the article is accepted for publication. This transfer includes the right to reproduce and/or to distribute the Paper to other journals or digital libraries in electronic and online forms and systems.

I understand that I retain the rights to use the pre-prints, off-prints, accepted manuscript and published journal Paper for personal use, scholarly purposes and internal institutional use.

In certain cases, I can ask for retaining the publishing rights of the Paper. The Journal can permit or deny the request for publishing rights, to which I fully agree.

I declare that the submitted Paper is original, has been written by the stated authors and has not been published elsewhere nor is currently being considered for publication by any other journal and will not be submitted for such review while under review by this Journal.  The Paper contains no material that violates proprietary rights of any other person or entity. I have obtained written permission from copyright owners for any excerpts from copyrighted works that are included and have credited the sources in my article. I have informed the co-author(s) of the terms of this publishing agreement.


Copyright ©  Slovenian Society Informatika