Document reconstruction using dynamic programming

In this work we propose a methodology for document reconstruction based on dynamic programming and a modified version of the Prim's algorithm. Firstly, we use polygonal approximation to reduce the complexity of the boundaries and extract features from them. Thereafter, these features are used t...

Full description

Saved in:
Bibliographic Details
Main Authors: Pimenta, A., Justino, E., Oliveira, L.S., Sabourin, R.
Format: Conference Proceeding
Language:English
Subjects:
Approximation algorithms
Document Reconstruction
Dynamic programming
Feature extraction
Feeds
Forensics
Heuristic algorithms
Image reconstruction
Shape
Size measurement
Spatial databases
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this work we propose a methodology for document reconstruction based on dynamic programming and a modified version of the Prim's algorithm. Firstly, we use polygonal approximation to reduce the complexity of the boundaries and extract features from them. Thereafter, these features are used to feed the LCS dynamic programming algorithm. The scores yielded by the LCS algorithm are then used into a modified Prim's algorithm to find the best match among all pieces. Comprehensive experiments on a database composed of 100 shredded documents support the efficiency of the proposed methodology. When compared to global search algorithms, this approach brings an improvement of 18% in the number of fragments reconstructed.
ISSN:1520-6149
2379-190X
DOI:10.1109/ICASSP.2009.4959853