Site News  |   Monitor Keywords  |   Monitor Archive  |   Organizer  |   Account Info  |

Methods of object search and recognition

Methods of object search and recognition description/claims

The present invention relates generally to image recognition and particularly to the recognition of non-text and/or text objects contained in a bit-mapped image of a document.

The mentioned methods are also applied for, but not limited to, recognition of data input forms, containing typographical and hand-written texts as well as a set of special text-marks for document navigation. Documents as supposed herein are inquiry lists, questionnaires, bank documents with rigid or arbitrary arrangement of data fields.

The mentioned methods may be applied for recognition of predefined form objects contained in an electronic graphical image.

Methods of structure assignment and document element search in an electronic graphical image are known in the art (U.S. Pat. No. 5,416,849 Huang, May 16, 1995).

The capability of the known methods to process only fixed forms, not allowing deviations in field arrangement, is the shortcoming of the methods.

Anyone of the described methods and the system may be taken as a prototype.

The technical result consists in the improvement of searching capabilities as well as the accuracy of identification of obtained image objects, the increase of noise immunity during the process of object search on the image.

The declared technical result is achieved by using tools for search and identification of objects on an image; with further assignment of the estimate of correspondence of the search result to the description. Numbers from 0 to 1 are used for the evaluation. The accuracy of evaluation is 10−5 (ten to the power of minus five). The value equal to 1 means the absolute correspondence of the obtained result to the description. If the estimate differs from zero, the application of flexible structural description also comprises the stage of forming block regions, i.e. evaluation of the arrangement of the required fields on the basis of the information about the obtained objects.

Structural description comprises the description of spatial and parametric characteristics of document elements, and the logical connections between document elements.

The method of preliminary assignment of a document structure consists in setting a description of the document's logical structure in the form of interdependences of spatial and parametric characteristics of elements, algorithms of obtaining the parameters of the search for each element, methods of identifying the obtained elements, methods of decreasing the number of obtained variants of an element, acceleration of the search for the best variant.

The method of searching and recognizing the elements (fields or field fragments) of a document on a graphical (bit-mapped) image consists in using of a predefined logical structure of the document in the form of structural description, algorithms of obtaining the parameters of the search for each element, methods of identifying the obtained elements, methods of decreasing the number of obtained variants of an element, acceleration of the search for the best variant.

Searching for elements with the help of a flexible structural description is performed sequentially in the order in which they are described in the flexible structural description, top-down through the “tree” (hierarchy) of elements, in accordance with the logical structure of the document description. For each element in the assigned search area, several variants of image objects or sets of image objects corresponding to the description of the element in the structural description may be found. Various obtained variants of objects are considered to be the variants of the position of the element on the image. An estimate of the degree of correspondence of the variant to the element description is assigned to each obtained variant (i.e. the estimate of the quality of the variant).

The accuracy of the obtained position of the object determines the accuracy of obtaining the positions of objects described further in the description relative to this object. Searching for the next dependent object is performed separately for each obtained variant of the current object. Therefore, the variants of objects obtained on the image comprise a hierarchical tree, considerable more branched than the hierarchical tree of elements in a structural description.

If an element or an object is compound, i.e. composed of several parts, the whole group also represents an element, which requires generating several possible variants, the number of which corresponds to the number of complete chains of group sub-elements (dependent elements of a lower level). The chain is considered complete if all its obtained sub-elements (elements of a lower level) have sufficient quality. The total estimate of the quality of a variant of a compound element is calculated by multiplying the estimates of the quality of element variants forming the compound element. A flexible structural description as a whole also represents a compound element, therefore, the quality of the correspondence of the variant to the flexible structural description is determined by multiplying the quality of its elements.

Application of a flexible structural description comprises searching for the best complete branch in the whole tree of variants, i.e. the branch that include all the elements, from first to last. A general solution of such a task implies taking into consideration all the possible combinations of hypotheses for all elements, construction of a total multitude of complete branches and selecting the best among them. However, in practice, such a solution requires too much resources, and is therefore impractical. Moreover, an abrupt increase in the number of variants taken into consideration is possible, caused by an increase in the number of elements and a lack of rigid restrictions on the search area and element parameters.

To limit the time required to analyze the variants, one of the several methods of decreasing the volume is used.

Each element gets the maximum allowed number of acceptable variants, rated in the order of decreasing quality. These variants will be used in the further search, i.e. when searching for the next element. Any variants beyond this number will be discarded. Usually this number is 5 (five) for simple elements and 1 (one) for compound elements. This means that, if 15 variants are obtained for a simple element in the assigned search area, five variants with the best quality rating will be selected. Other 10 chains of variants will not be complete and will not be taken into consideration. A compound element is identified with a greater quality rating than a simple element, because the quality of identification is determined not only by multiplying the quality ratings of the constituent simple elements, but also by several additional (mainly qualitative) characteristics, such as mutual arrangement, object size, correspondence to the conditions of mutual arrangement several elements, and so on.

Since a compound element is identified with a greater quality rating than a simple element, its best variant usually turns out to be accurate.

The process of searching for objects almost always includes generating several incomplete chains of variants of obtained objects and, therefore, several directions of further search. Search for the best hypothesis is performed by using an algorithm of “broad searching”, i.e. the search is always directed through the chain of variants which has the best quality rating at the current step, regardless of the length of the chain. For example, if in a flexible structural description of 30 elements 2 chains are obtained during search, one of which consists of 30 elements with the quality rating of 0.89 and the other chain has 2 elements with the quality rating of 0.92, then the second chain will be pursued until its total quality becomes lower than that of the first chain.

The following rule of quality optimization is used for compound elements: if an ideal complete chain for this element is obtained, i.e. the quality of the obtained chain equals 1, other variants of sub-elements composition of this compound element are not taken into consideration.

Moreover, the maximum number of variants for every element in the entire hypothesis tree is restricted to 1000.

• Provisional Patent
• Utility Patent

• What Is a Patent?
• What Is a Trademark or Servicemark?
• What Is a Copyright?
• Patent Laws