Speedup of Optical Scanner Characterization System

To enhance the accuracy of optical character recognition (OCR), optical scanners may be characterized on-the-fly, without calibration images, so the OCR software can model and predict certain deformations due to the scanning process. To do this, bilevel (black and white) document pages are segmented, individual characters are isolated, and corners are extracted from the characters and measured. From these measurements, scanner characterization parameters may be found. The existing subsystem that finds these parameters from corner measurements requires a prohibitive amount of time to execute. Two primary sources of resource consumption are identified and detailed. The first source is the extraction of level curves from surfaces unique to each corner angle measurement ø. In general, there is no closed mathematical form for the surface, so simulation is used. The simulation algorithm is of sufficiently-high polynomial complexity to render surface generation impractical for use on-the-fly. Two algorithms that find level curves from a set S of pre-generated surfaces are detailed. One method approximates the actual surface to be used for level curve extraction from two nearby surfaces from S. The other modifies corner measurements and uses existing surfaces in S to find level curves. The second source is the finding of intersections between level curves. The existing subsystem naively performs an exhaustive search. Two alternatives exploit spatial locality to find the intersections faster. One algorithm partitions space and limits the scope of its search to a given partition. The other partitions level curves and finds bounding boxes that entirely contain those portions of level curves constituting the partitions. Only those portions of the level curves belonging to overlapping bounding boxes are checked for intersection. Two enhancements to the intersection-finding algorithms are given. One enhancement rotates the level curves to align with the partition boundaries, making the partitioning more efficient. The other shortens the lengths of the level curves by eliminating easily-identified, large portions of curves where intersection is impossible. Since the search for intersections is (partly) dependent on the lengths of the level curves, this improves execution time. The speedups realized from the algorithms detailed in this thesis are presented. Overall, about 4 orders of magnitude speedup were achieved. The algorithms that find level curves from surfaces employ approximations, so a comparison with prior results using the existing subsystem is also presented. Deviation ranged from 2.5% to 3.5%, depending on the algorithm used