Deep Learning-based Reconstruction of Shredded Documents
Resumo
This thesis addresses the reconstruction of shredded paper documents, a relevant task in various domains such as forensic investigation and history reconstruction. Despite previous research, dealing with real-shredded data is a sensitive issue in the literature. To face this challenge, we proposed two deep learning approaches that have achieved state-of-the-art accuracy in more realistic scenarios. As a second major contribution, human interaction was explored to improve reconstruction. Our framework, inspired by the field of active learning, automatically selects potential mistakes in the solution for user analysis enabling better accuracy in a scalable way. The results yielded works in top-tier publications such as CVPR and the Pattern Recognition journal.
Referências
Abitbol, R., Shimshoni, I., and Ben-Dov, J. (2021). Machine learning based assembly of fragments of ancient papyrus. Journal on Comput.and Cultural Heritage, 14(3):1–21.
Applegate, D., Bixby, R., Chvatal, V., and Cook, W. (2001). Concorde: A code for solving traveling salesman problems. http://www.math.uwaterloo.ca/tsp/concorde. accessed on: October 19, 2020.
Butler, P., Chakraborty, P., and Ramakrishan, N. (2012). The Deshredder: A visual analytic approach to reconstructing shredded documents. In IEEE Conf. on Vis. Analytics Sci. and Technol., pages 113–122. IEEE.
Chen, J., Tian, M., Qi, X., Wang, W., and Liu, Y. (2019). A solution to reconstruct cross-cut shredded text documents based on constrained seed K-means algorithm and ant colony algorithm. Expert Syst. with Appl., 127:35–46.
Derian, J. D. (1989). Arms, Hostages, and the Importance of Shredding in Earnest: Reading the National Security Culture (II). Social Text, (22):79–91.
Li, R., Liu, S., Wang, G., Liu, G., and Zeng, B. (2021). Jigsawgan: Auxiliary learning for solving jigsaw puzzles with generative adversarial networks. IEEE Trans. on Image Processing, 31:513–524.
Liang, Y. and Li, X. (2020). Reassembling Shredded Document Stripes Using Word-path Metric and Greedy Composition Optimal Matching Solver. IEEE Trans. on Multimedia, 22(5):1168–1181.
Marques, M. and Freitas, C. (2013). Document decipherment-restoration: Strip-shredded document reconstruction based on color. IEEE Latin America Trans., 11(6):1359–1365.
Paixão, T. M., Berriel, R. F., Boeres, M. C. S., Koerich, A. L., Badue, C., Souza, A. F. D., and Oliveira-Santos, T. (2020b). Fast(er) reconstruction of shredded text documents via self-supervised deep asymmetric metric learning. In IEEE/CVF Conf. on Comp. Vision and Pattern Recognit., pages 14343–14351.
Paixão, T. M., Boeres, M. C. S., Freitas, C. O. A., and Oliveira-Santos, T. (2019). Exploring Character Shapes for Unsupervised Reconstruction of Strip-shredded Text Documents. IEEE Trans. Inf. Forensics Secur., 14(7):1744–1754.
Paixão, T. M., Berriel, R. F., Boeres, M. C. S., Koerich, A. L., Badue, C., De Souza, A. F., and Oliveira-Santos, T. (2020a). Self-supervised deep reconstruction of mixed strip-shredded text documents. Pattern Recognit., 107:107535.
Paumard, M.-M., Picard, D., and Tabia, H. (2020). Deepzzle: Solving visual jigsaw puzzles with deep learning and shortest path optimization. IEEE Trans. on Image Processing, 29:3569–3581.
Perdue, L. (2013). What the argo movie got wrong about shredded documents. https://lewisperdue.com/archives/4052. Accessed: June 5, 2023.
Perl, J., Diem, M., Kleber, F., and Sablatnig, R. (2011). Strip shredded document reconstruction using optical character recognition. In Int. Conf. on Imag. for Crime Detection and Prevention, pages 1–6.
Pirrone, A., Beurton-Aimar, M., and Journet, N. (2021). Self-supervised deep metric learning for ancient papyrus fragments retrieval. International Journal on Document Analysis and Recognition (IJDAR), 24(3):219–234.
Pöhler, D., Zimmermann, R., Widdecke, B., Zoberbier, H., Schneider, J., Nickolay, B., and Krüger, J. (2015). Content representation and pairwise feature matching method for virtual reconstruction of shredded documents. In 9th IEEE Int. Symp. Image and Signal Process. and Anal., pages 143–148.
Pomeranz, D., Shemesh, M., and Ben-Shahar, O. (2011). A fully automated greedy square jigsaw puzzle solver. In IEEE Conf. Comput. Vision and Pattern Recognit., pages 9–16.
Prandtstetter, M. and Raidl, G. R. (2008). Combining forces to reconstruct strip shredded text documents. In Int. Workshop on Hybrid Metaheuristics, pages 175–189. Springer.
Rika, D., Sholomon, D., David, E., and Netanyahu, N. S. (2022). Ten: Twin embedding networks for the jigsaw puzzle problem with eroded boundaries. arXiv preprint arXiv:2203.06488.
Rubens, N., Elahi, M., Sugiyama, M., and Kaplan, D. (2015). Active learning in recommender systems. In Recommender systems handbook, pages 809–846. Springer.
Shang, S., Sencar, H. T., Memon, N., and Kong, X. (2014). A semi-automatic deshredding method based on curve matching. In 2014 IEEE International Conference on Image Processing (ICIP), pages 5537–5541. IEEE.
Ukovich, A., Ramponi, G., Doulaverakis, H., Kompatsiaris, Y., and Strintzis, M. (2004). Shredded document reconstruction using MPEG-7 standard descriptors. In Symp. on Signal Process. and Info. Technol., pages 334–337.
Xing, N. and Zhang, J. (2017). Graphical-character-based shredded chinese document reconstruction. Multimedia Tools and Appl., 76(10):12871–12891.
Applegate, D., Bixby, R., Chvatal, V., and Cook, W. (2001). Concorde: A code for solving traveling salesman problems. http://www.math.uwaterloo.ca/tsp/concorde. accessed on: October 19, 2020.
Butler, P., Chakraborty, P., and Ramakrishan, N. (2012). The Deshredder: A visual analytic approach to reconstructing shredded documents. In IEEE Conf. on Vis. Analytics Sci. and Technol., pages 113–122. IEEE.
Chen, J., Tian, M., Qi, X., Wang, W., and Liu, Y. (2019). A solution to reconstruct cross-cut shredded text documents based on constrained seed K-means algorithm and ant colony algorithm. Expert Syst. with Appl., 127:35–46.
Derian, J. D. (1989). Arms, Hostages, and the Importance of Shredding in Earnest: Reading the National Security Culture (II). Social Text, (22):79–91.
Li, R., Liu, S., Wang, G., Liu, G., and Zeng, B. (2021). Jigsawgan: Auxiliary learning for solving jigsaw puzzles with generative adversarial networks. IEEE Trans. on Image Processing, 31:513–524.
Liang, Y. and Li, X. (2020). Reassembling Shredded Document Stripes Using Word-path Metric and Greedy Composition Optimal Matching Solver. IEEE Trans. on Multimedia, 22(5):1168–1181.
Marques, M. and Freitas, C. (2013). Document decipherment-restoration: Strip-shredded document reconstruction based on color. IEEE Latin America Trans., 11(6):1359–1365.
Paixão, T. M., Berriel, R. F., Boeres, M. C. S., Koerich, A. L., Badue, C., Souza, A. F. D., and Oliveira-Santos, T. (2020b). Fast(er) reconstruction of shredded text documents via self-supervised deep asymmetric metric learning. In IEEE/CVF Conf. on Comp. Vision and Pattern Recognit., pages 14343–14351.
Paixão, T. M., Boeres, M. C. S., Freitas, C. O. A., and Oliveira-Santos, T. (2019). Exploring Character Shapes for Unsupervised Reconstruction of Strip-shredded Text Documents. IEEE Trans. Inf. Forensics Secur., 14(7):1744–1754.
Paixão, T. M., Berriel, R. F., Boeres, M. C. S., Koerich, A. L., Badue, C., De Souza, A. F., and Oliveira-Santos, T. (2020a). Self-supervised deep reconstruction of mixed strip-shredded text documents. Pattern Recognit., 107:107535.
Paumard, M.-M., Picard, D., and Tabia, H. (2020). Deepzzle: Solving visual jigsaw puzzles with deep learning and shortest path optimization. IEEE Trans. on Image Processing, 29:3569–3581.
Perdue, L. (2013). What the argo movie got wrong about shredded documents. https://lewisperdue.com/archives/4052. Accessed: June 5, 2023.
Perl, J., Diem, M., Kleber, F., and Sablatnig, R. (2011). Strip shredded document reconstruction using optical character recognition. In Int. Conf. on Imag. for Crime Detection and Prevention, pages 1–6.
Pirrone, A., Beurton-Aimar, M., and Journet, N. (2021). Self-supervised deep metric learning for ancient papyrus fragments retrieval. International Journal on Document Analysis and Recognition (IJDAR), 24(3):219–234.
Pöhler, D., Zimmermann, R., Widdecke, B., Zoberbier, H., Schneider, J., Nickolay, B., and Krüger, J. (2015). Content representation and pairwise feature matching method for virtual reconstruction of shredded documents. In 9th IEEE Int. Symp. Image and Signal Process. and Anal., pages 143–148.
Pomeranz, D., Shemesh, M., and Ben-Shahar, O. (2011). A fully automated greedy square jigsaw puzzle solver. In IEEE Conf. Comput. Vision and Pattern Recognit., pages 9–16.
Prandtstetter, M. and Raidl, G. R. (2008). Combining forces to reconstruct strip shredded text documents. In Int. Workshop on Hybrid Metaheuristics, pages 175–189. Springer.
Rika, D., Sholomon, D., David, E., and Netanyahu, N. S. (2022). Ten: Twin embedding networks for the jigsaw puzzle problem with eroded boundaries. arXiv preprint arXiv:2203.06488.
Rubens, N., Elahi, M., Sugiyama, M., and Kaplan, D. (2015). Active learning in recommender systems. In Recommender systems handbook, pages 809–846. Springer.
Shang, S., Sencar, H. T., Memon, N., and Kong, X. (2014). A semi-automatic deshredding method based on curve matching. In 2014 IEEE International Conference on Image Processing (ICIP), pages 5537–5541. IEEE.
Ukovich, A., Ramponi, G., Doulaverakis, H., Kompatsiaris, Y., and Strintzis, M. (2004). Shredded document reconstruction using MPEG-7 standard descriptors. In Symp. on Signal Process. and Info. Technol., pages 334–337.
Xing, N. and Zhang, J. (2017). Graphical-character-based shredded chinese document reconstruction. Multimedia Tools and Appl., 76(10):12871–12891.
Publicado
06/08/2023
Como Citar
PAIXÃO, Thiago M.; BOERES, Maria C. S.; OLIVEIRA-SANTOS, Thiago.
Deep Learning-based Reconstruction of Shredded Documents. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 36. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 10-19.
ISSN 2763-8820.
DOI: https://doi.org/10.5753/ctd.2023.229506.
