Compression algorithms that preserve basic topological features in binary-coded patterns

摘要

In this paper, some problems related to the recognition of plane, two-tone pictures (e.g. handprinted characters) are considered. It is assumed that suitable algorithms (already described) have been applied to the original picture, in order to obtain linearwise, two-tone figures. A problem that arises at this point is classifying these results in a suitable way; to this purpose, it is necessary to define and perform a set of measurements such that the results obtained by applying them to figures of the same class be the same, the possible ambiguity be minimal and the loss of information be as reduced as possible. In this paper, some algorithms are described that transform the figure into another one of the least possible dimensions, but retaining a set of basic topological and quasi-topological characteristics of the original picture. While implicitly defining a set of measurements to be performed, the “reduction” of the figure is implemented so that several figures having the same basic characteristics give the same “reduced” figure as final result. The considerable reduction of the figure's dimensions may furthermore make the recognition simpler. Several algorithms are described, and the results are compared; all are of parallel type, and therefore particularly suited for hardware implementation.