Share Email Print

Proceedings Paper

Document image decoding using iterated complete path search
Author(s): Thomas P. Minka; Dan S. Bloomberg; Kris Popat
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

The computation time of Document Image Decoding can be significantly reduced by employing heuristics in the search for the best decoding of a text line. By using a cheap upper bound on template match scores, up to 99.9% of the potential template matches can be avoided. In the Iterated Complete Path method, template matches are performed only along the best path found by dynamic programming on each iteration. When the best path stabilizes, the decoding is optimal and no more template matches need be performed. Computation can be further reduced in this scheme by exploiting the incremental nature of the Viterbi iterations. Because only a few trellis edge weights have changed since the last iteration, most of the backpointers do not need to be updated. We describe how to quickly identify these backpointers, without forfeiting optimality of the path. Together these improvements provide a 30x speedup over previous implementations of Document Image Decoding.

Paper Details

Date Published: 21 December 2000
PDF: 9 pages
Proc. SPIE 4307, Document Recognition and Retrieval VIII, (21 December 2000); doi: 10.1117/12.410843
Show Author Affiliations
Thomas P. Minka, Massachusetts Institute of Technology (United States)
Dan S. Bloomberg, Xerox Palo Alto Research Ctr. (United States)
Kris Popat, Xerox Palo Alto Research Ctr. (United States)

Published in SPIE Proceedings Vol. 4307:
Document Recognition and Retrieval VIII
Paul B. Kantor; Daniel P. Lopresti; Jiangying Zhou, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?