Adaptive sorting algorithms for evaluation of automatic zoning
Abstract
Optical Character Recognition (OCR) involves analysis of machine-printed and hand written document images. The first step in an OCR process is to locate the text to be recognized on a page. An OCR device tries to identify the characters in these text regions and outputs the characters in ASCII. To evaluate the performance of any OCR device, the ASCII output of the OCR device is compared with the ground truth text which is entered into the computer manually; Some OCR devices provide the users with automatic zoning. The output of any automatic zoning algorithm has to be corrected manually to restore the correct reading order. This is done by elementary edit operations such as insertions, deletions and substitutions or by moving sub-strings of characters. The efficiency of an automatic zoning algorithm is measured by the cost of correcting the OCR generated text. The model for cost calculation requires movement of sub-strings in a particular fashion to ensure minimal cost. This problem has been modeled as sorting an arbitrary permutation. This thesis presents few adaptive sorting approaches which can be incorporated into the automatic zoning evaluation algorithm. These algorithms perform better than the existing algorithms used for this purpose. This thesis also presents more directions in which the problem can be pursued to achieve better performance.