How can permutations be used in the evaluation of zoning algorithms?

Document Type



In processing a page image by a given zoning algorithm (automatic or manual), a certain text string is generated which may not be the same as the correct string. The difference may be due to the incorrect reading order selected by the employed zoning algorithm or poor recognition of characters. A difference algorithm is commonly used to find the best match between the generated string and the correct string. The output of such an algorithm will then be a sequence of matched substrings which are not in the correct order. To determine the performance of a given zoning algorithm, it is of interest to find the minimum number of moves needed to obtain the correct string from the string generated by that algorithm. The problem can be modeled as a sorting problem where a string of n integers ordered in a random manner, must be sorted in ascending (or descending) order. In this paper, we derive bounds on the time complexity of sorting a given string and present a near-optimal algorithm for that.


Electrical and Computer Engineering | Engineering


Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.