More Web Proxy on the site http://driver.im/

research-article

Reconstructing Cross-Cut Shredded Text Documents: A Genetic Algorithm with Splicing-Driven Reproduction

Authors:

Jun ZhangAuthors Info & Claims

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Pages 847 - 853

https://doi.org/10.1145/2739480.2754677

Published: 11 July 2015 Publication History

Abstract

In this work we focus on reconstruction of cross-cut shredded text documents (RCCSTD), which is of high interest in the fields of forensics and archeology. A novel genetic algorithm, with splicing-driven crossover, four mutation operators, and a row-oriented elitism strategy, is proposed to improve the capability of solving RCCSTD in complex space. We also design a novel and comprehensive objective function based on both edge and empty vector-based splicing error to guarantee that the correct reconstruction always has the lowest cost value. Experiments are conducted on six RCCSTD scenarios, with experimental results showing that the proposed algorithm significantly outperforms the previous best-known algorithms for this problem.

References

[1]

Prandtstetter M. 2009. Hybrid optimization methods for warehouse logistics and the reconstruction of destroyed paper documents. Ph.D. thesis, Vienna University of Technology.

[2]

Sleit A, Massad Y, Musaddaq M. 2013. An alternative clustering approach for reconstructing cross cut shredded text documents. Telecommunication Systems, 52(3), 1491--1501.

Digital Library

[3]

Mladenović N, Hansen P. 1997. Variable neighborhood search. Computers & Operations Research, 24(11), 1097--1100.

Digital Library

[4]

Schauer C, Prandtstetter M, Raidl G R. 2010. A memetic algorithm for reconstructing cross-cut shredded text documents. In Hybrid Metaheuristics, 103--117.

Digital Library

[5]

Prandtstetter M, Raidl G R. 2009. Meta-heuristics for reconstructing cross cut shredded text documents. In Genetic and Evolutionary Computation Conference, 349--356.

Digital Library

[6]

Justino E, Oliveira L S, Freitas C. 2006. Reconstructing shredded documents through feature matching. Forensic science international, 160(2), 140--147.

[7]

Prandtstetter M, Raidl G R. 2008. Combining forces to reconstruct strip shredded text documents. In Hybrid Metaheuristics, 175--189.

Digital Library

[8]

Ukovich A, Ramponi G, Doulaverakis H, et al. 2004. Shredded document reconstruction using MPEG-7 standard descriptors. In International Symposium on Signal Processing and Its Applications, 334--337

[9]

Holland J H. 1975. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. University of Michigan Press.

[10]

Leardi R. 2000. Application of genetic algorithm--PLS for feature selection in spectral data sets. Journal of Chemometrics, 14(5--6), 643--655.

[11]

Rahmat-Samii Y, Michielssen E. 1999. Electromagnetic optimization by genetic algorithms. John Wiley & Sons Inc.

Digital Library

[12]

Raidl G R, Hu B. 2010. Enhancing genetic algorithms by a trie-based complete solution archive. In Evolutionary Computation in Combinatorial Optimization, 239--251.

Digital Library

[13]

Li X, Yao X. 2012. Cooperatively coevolving particle swarms for large scale optimization. IEEE Transactions on Evolutionary Computation, 16(2), 210--224.

Digital Library

[14]

Lu S, Tan C L. 2007. Automatic detection of document script and orientation. In International Conference on Document Analysis and Recognition, 237--241.

Digital Library

[15]

Davis L. 1985. Applying adaptive algorithms to epistatic domains. In International Joint Conference on Artificial Intelligence, 162--164.

Digital Library

[16]

Goldberg D E, Lingle R. 1985. Alleles, loci, and the traveling salesman problem. In International conference on Genetic Algorithms and Their Applications, 154--159.

Digital Library

[17]

I. Oliver, D. Smith, and J. Holland. 1987. A Study of permutation crossover operators on the traveling salesman problem. In International Conference on Genetic Algorithms, 224--230.

Digital Library

[18]

Starkweather T, McDaniel S, Mathias K E, et al. 1991. A comparison of genetic sequencing operators. In International Conference on Genetic Algorithms, 69--76.

[19]

Zhan Z H, Zhang J, Li Y, et al. 2009. Adaptive Particle Swarm Optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 39(6), 1362--1381.

Digital Library

[20]

Yu W J, Shen M, Chen W N, et al. 2014. Differential evolution with two-level parameter adaptation. IEEE Transactions on Cybernetics, 44(7), 1080--1099.

[21]

Gong Y J, Zhang J. 2013. Small-world particle swarm optimization with topology adaptation. In Genetic and Evolutionary Computation Conference, 25--32.

Digital Library

Cited By

Xing NXing YGao L(2020)A Fragment Matching Evaluation Method Based on Character StructureProceedings of the 2020 International Conference on Internet Computing for Science and Engineering10.1145/3424311.3424325(104-108)Online publication date: 14-Jan-2020
https://dl.acm.org/doi/10.1145/3424311.3424325
Liang YLi X(2020)Reassembling Shredded Document Stripes Using Word-Path Metric and Greedy Composition Optimal Matching SolverIEEE Transactions on Multimedia10.1109/TMM.2019.294177722:5(1168-1181)Online publication date: May-2020
https://doi.org/10.1109/TMM.2019.2941777
Paixao TBerriel RBoeres MKoerich ABadue CDe Souza AOliveira-Santos T(2020)Fast(er) Reconstruction of Shredded Text Documents via Self-Supervised Deep Asymmetric Metric Learning2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR42600.2020.01435(14331-14339)Online publication date: Jun-2020
https://doi.org/10.1109/CVPR42600.2020.01435

Index Terms

Reconstructing Cross-Cut Shredded Text Documents: A Genetic Algorithm with Splicing-Driven Reproduction
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Meta-heuristics for reconstructing cross cut shredded text documents
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

In this work, we present two new approaches based on variable neighborhood search (VNS) and ant colony optimization (ACO) for the reconstruction of cross cut shredded text documents. For quickly obtaining initial solutions, we consider four different ...
A Two-Stage Approach for Reconstruction of Cross-Cut Shredded Text Documents
CIS '14: Proceedings of the 2014 Tenth International Conference on Computational Intelligence and Security

This paper presents a two-stage approach for reconstruction of cross-cut shredded text documents. Cross-cut shredding is used to mechanically cut a document into rectangular shreds of (almost) identical shapes. After pre-processing shreds with image-...
Enhancing a Genetic Algorithm with a Solution Archive to Reconstruct Cross Cut Shredded Text Documents
Revised Selected Papers of the 14th International Conference on Computer Aided Systems Theory - EUROCAST 2013 - Volume 8111

In this work the concept of a trie-based complete solution archive in combination with a genetic algorithm is applied to the Reconstruction of Cross-Cut Shredded Text Documents (RCCSTD) problem. This archive is able to detect and subsequently convert ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

July 2015

1496 pages

ISBN:9781450334723

DOI:10.1145/2739480

Editor:
Sara Silva
Universidade de Lisboa, Portugal
,
General Chair:
Anna I. Esparcia-Alcázar
Universitat Politècnica de València, Spain

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSFC for Distinguished Young Scholars
High-Technology Research and Development Program (863 Program) of China
NSFC Joint Fund with Guangdong under Key Projects

Conference

GECCO '15

Sponsor:

SIGEVO

GECCO '15: Genetic and Evolutionary Computation Conference

July 11 - 15, 2015

Madrid, Spain

Acceptance Rates

GECCO '15 Paper Acceptance Rate 182 of 505 submissions, 36%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
150
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xing NXing YGao L(2020)A Fragment Matching Evaluation Method Based on Character StructureProceedings of the 2020 International Conference on Internet Computing for Science and Engineering10.1145/3424311.3424325(104-108)Online publication date: 14-Jan-2020
https://dl.acm.org/doi/10.1145/3424311.3424325
Liang YLi X(2020)Reassembling Shredded Document Stripes Using Word-Path Metric and Greedy Composition Optimal Matching SolverIEEE Transactions on Multimedia10.1109/TMM.2019.294177722:5(1168-1181)Online publication date: May-2020
https://doi.org/10.1109/TMM.2019.2941777
Paixao TBerriel RBoeres MKoerich ABadue CDe Souza AOliveira-Santos T(2020)Fast(er) Reconstruction of Shredded Text Documents via Self-Supervised Deep Asymmetric Metric Learning2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR42600.2020.01435(14331-14339)Online publication date: Jun-2020
https://doi.org/10.1109/CVPR42600.2020.01435

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents