Method for a uniform symbolic description of document patterns in the form of data structures in an automated apparatus

摘要

1. Method for a uniform symbolic description of document patterns in the form of data structures in an automated apparatus, it being possible for the document patterns to be composed of the components "text", "graphics" and/or "image", for the purpose of the division of the document pattern into these components and for the further processing of these components in evaluating modules for special application cases, descriptors representing interpolation nodes along edges in a respective document pattern being extracted line-by-line from the digitized output signals of an optical scanning device, descriptors being calculated in a first module and the data relating to the descriptors being stored in an in each case free storage location of a data memory, whereupon the data memory issues an acknowledgment with information about the storage location used, a second module being activated by the transfer of the returned address information and accepting this address information together with list indices from lists, the second module using this address information to incorporate the descriptor stored in the data memory into an already existing descriptor string with an edge representative or to begin a new descriptor string with the formation of a new edge representative necessary for this, the descriptor string being in each case a concatenation of individual descriptors with the aid of pointers and a new descriptor, which is stored in an arbitrary storage location in the data memory, being connected by means of pointers to the respective already existing string or already existing strings, the position of the associated edge representative(s) being taken directly from the lists with the aid of the list indices transferred, this information being entered in the lists again by the second module when there is a change of representative of the descriptor string, the second module transferring the index of this edge for further processing to a third module whenever a completely closed edge is formed by a descriptor string, the third and following modules concatenating a plurality of edges to form hierarchically organized data structures and classifying these as text components, graphics components and/or image components, an output module making available the index of the representative of a complete data structure which is hierarchically organized in this manner and which contains the entire information stored in the data memory about these representatives including the information about its subordinate representatives, to a more farreaching, evaluating process in evaluating modules, and only the index of the superordinate representative being transferred to one of the evaluating modules and this module processing the information stored therein under the index of the respective representative by its own access to the data memory, as well as for extraction of recognition characteristics from the image description obtained in this manner, in which it is provided - that fine structure elements are formed in a fine structure element module, - that these fine structure elements are combined during the line-by-line processing of the document image to form fine edge strings which reproduce the edge contours of the individual patterns to the pixel exactly, - that the individual sections of these fine edges are associated with the descriptors in such a way that they describe exactly the edge contour between in each case two descriptors, - that for each new scanning line the data relating to the fine structure elements are stored in the form of fine structure substrings describing the pattern edges exactly to the pixel in respectively free memory locations of the data memory and are concatenated with one another in accordance with the contour of the pattern edge, - that a newly formed fine structure substring in an image line is concatenated on the basis of list information also supplied to an already existing fine structure string to be completed and the position of the fine structure element which forms the new open edge end of the fine structure string is reported back in an acknowledgement to the fine structure element module, the fine structure element module noting by means of this acknowledgement the position of the free edge end in the data memory either in additional lists to the lists for the current image line (YA) and the preceding image line (YA1) or in the edge representative superordinate to the fine edge string, as a result of which it is possible to place at the open edge the fine structure substring being produced in the next image line as a continuation of the edge, - that the fine structure elements in each case contain information about the orientation of the respective pixel, a pointer to the next fine structure element and the mid-point coordinates (i, j) of the element in an overlaid fine coordinate system (Fig. 1), - that there is produced in each scanned image line for each sectioned pattern edge one of said fine structure substrings which is concatenated to the open end of the associated fine structure string (Fig. 2, Fig. 3), - that, when it is entered in the descriptor string in the superordinate edge representative, a new descriptor finds the information about the open edge end of the fine structure string associated with it, - that this fine structure string is run through up to the position of the descriptor, - that a pointer pointing to this fine structure element is entered in the descriptor, - that pointers refer to the start and end of the associated fine structure string in the edge representative in the data memory, - that, when two edges flow together, analogous operations to those for the descriptor strings with respect to creation, combination, extension and ending with regard to the fine structure strings, are carried out in the edge module, - that the hierarchically organized data structure preferably of each object to be recognized is made available to the evaluating module for forming recognition characteristics, - that projection vectors (C(alpha, n), t(alpha, n)) known per se are calculated from the fine structure elements of such a data structure, - that the fine structure strings of the object to be recognized are run through, - that the projection vector (C(alpha, n)) is calculated by each individual element from the fine structure string being mapped on an element _n in the projection vector (C(alpha, n)), _n being determined from the i and j coordinates of a fine structure element and the projection angle (alpha), the value "c(alpha, n)" being incremented by 1 for the corresponding element, - that the projection vector (t(alpha, n)) is calculated by the fine structure strings of the object to be recognized being run through, - that, in conjunction with this, the value _n and a value _f are calculated for each fine structure element as a function of the coordinates (i, j) as well as of the projection angle (alpha), the value _f being calculated from a value _q and a value _b by multiplication, and the value _q corresponding to the distance between the fine structure element and a straight line (t(alpha, n)) (Fig. 5), the associated value for each fine structure element being added in the memory cell 2 of "t(alpha, n)" in such a manner that f-values deliver a positive amount on the side of an edge element facing the pattern and deliver a negative amount on the side facing away from the pattern, an f-value being calculated as the product from the distance between the mid-point coordinates of a fine structure element and the projection lines "t(alpha, n)", namely the q-value, and the projection width _b of a fine structure element on the projection line "t(alpha, n)", and - that the recognition characteristics to be extracted are calculated in a manner known per se from the projection vectors (C(alpha, n), t(alpha, n)).