Method and apparatus for comparing symbols extracted from binary images

Abstract

A method and apparatus for comparing symbols extracted from binary images of text for classifying into equivalence classes. The present invention uses a Hausdorff-like method for comparing symbols for similarity. When a symbol contained in a bitmap A is compared to a symbol contained in a bitmap B, it is determined whether or not the symbol in bitmap B fits within a tolerance into a dilated representation of the symbol in bitmap A with no excessive density of errors and whether the symbol in bitmap A fits within a tolerance into a dilated representation of the symbol in bitmap B with no excessive density of errors. If both tests are passed, an error density check is performed to determine a match. The dilated representation of the bitmap accounts for various quantization errors that may occur along the boundaries of a symbol defined in the respective bitmaps. The dilation utilized preserves the topology of the symbol. The topology preserving dilation is one where symbols are 'thickened' yet the local topology (or connectedness) of the symbol is not changed. Such a dilation is performed by applying a set of local rules to 'off' pixels that are adjacent to 'on' pixels. Quantization effects are also accounted for through the use of a non-linear error allowance. The non-linear error allowance implements the idea that small symbols provide for little or no error, whereas large symbols provide for a proportionately larger amount of error.