Physical Match

Aaron E. Naiman, Eliav Farber, Yossi Stein

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.


Full Text:

PDF

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.




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

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.