1. Field of the Invention
The present invention relates to image recognizing technology for reading documents, drawings, etc., and more specifically to character string extracting technology for extracting a character string such as a headline from an image.
2. Description of the Related Art
When a document is electronically filed, it is indispensable to assign a keyword to the document. However, it is a very annoying process for a user. Therefore, it is significant to successfully automate this process and efficiently perform an electronic filing process.
In newspapers and magazines, it is the most efficient to automatically extract a headline, recognize characters forming the headline, and define it as a keyword because a headline indicates a lot of characteristics of the contents of a document, and can be easily retrieved from the document.
As a result, technology of shortening the time taken to extract a keyword, and of correctly extracting a keyword (for example, Tokkaihei 4-287168 which discloses a method of automatically extracting a keyword from a file) has been developed.
In this method, it is assumed that the descriptions of a drawing, a photograph, and a table are positioned at the top or foot of each of them to be described. Thus, the descriptions can be extracted as a character string or a character string area, and the characters forming the descriptions are recognized and entered as a keyword.
Also, technology of extracting a character string from an image (for example, Tokkaihei 8-293003 which discloses a character string extracting method and a character string extraction apparatus based on the method, a character string recognizing apparatus and a character string recognizing system) has been developed.
In this example, all characters in the image are extracted, continuous characters are grouped as a character string, the feature amount of each group is compared with an entered feature amount model, discriminated, and extracted as a character string. Continuous characters refers to a character string, and a feature amount refers to a type and size of a character such as a kanji (Chinese character), a numerical character, etc.
Thus, there are various documents and drawings to be treated in an electronic filing process, and there are various image recognition technology. When a character string is extracted from an image, the most popular method is to process a headline which has its background as often seen in newspapers.
First, it is determined whether an input image contains vertically arranged characters or horizontally arranged characters. Then, a labelling process is performed on the input image and its black/white inverse image to obtain connected elements having a series of picture elements in the same color.
Next, a character candidate is found based on the size, thickness, and relative position of each connected element.
The character candidate obtained from the connected element of an input image is referred to as a black character candidate, and the character candidate obtained from the connected element of an inverse image is referred to as a white character candidate. The color of characters is determined from the number of black character candidates and white character candidates. When the character color is black, only the connected elements of an input image are to be processed in the subsequent steps. When the character color is white, only the connected elements of the black/white inverse image are to be processed thereafter.
Next, a character string area is obtained after merging the connected elements to be processed. The connected element which is contained in the character string area and is equal to or larger than a threshold in thickness is extracted as a character element. The threshold is a value indicating a constant ratio to the maximum value in thickness of a connected element. Finally, the connected element extracted as a character element is generated as an image, and is defined as a character string in a character recognizing process.
To correctly extract a headline, precise integration technology for a black picture element area belonging to the same character string is required.
The following conventional method relates to this technology.
After performing a pre-process such as adjusting a tilt, removing a character-box line, etc., the entire image is labelled, and an overlapping nest integrating process is performed on the obtained black picture element connection areas. Then, the character size of the text of the entire document is determined from the obtained black picture element connection area. Based on the value, the attribute of each connection area is determined. When it is determined that the attribute of a rectangle is a character, vertical or horizontal integration is repeated on the rectangle, thereby defining a character string.
However, in the conventional technology, the character color is determined during the character extracting process, and the character line width is fixed to a standard value. Furthermore, a character string area is set in line units (or in column units). Therefore, it has been a problem that it is quite difficult to extract a character string from a complicated image comprising a background pattern containing a combination of white and black portions, various types of fonts, a color document, a plurality of lines, a combination of vertical and horizontal character strings, and a compound of them.
Furthermore, the relationship between black character candidates and white character candidate in number is not a reliable criterion for determining a character color. When the character color is determined during the character extracting process, the determination is irrevocable if it is mistakenly made, thereby failing in the final character recognition.
Additionally, when the character line width is fixed to a standard value, a character element printed by a comparatively thin line can be easily lost, thereby failing in the final character recognition.
Furthermore, since the overlapping nest integrating process is performed on black picture element connection areas in the conventional technology, portions which should not be originally integrated are sequentially integrated, thus finally and incorrectly integrating the entire document.
For example, when the tilt of the entire document cannot be adjusted, or the character-box line cannot be completely removed, the entire document can be integrated in the overlapping nest integrating process.
FIG. 1 shows an example of integrating the entire document in the conventional overlapping nest integrating process.
In FIG. 1A, it is assumed that the enclosing rectangles K61 through K65 of the connected elements have been obtained from an input image. When the overlapping nest integrating process is performed on the enclosing rectangles K61 through K65 of the connected elements, the enclosing rectangle K61 and the enclosing rectangle K62 are integrated because they overlap each other. As a result, as shown in FIG. 1B, an enclosing rectangle K66 enclosing the enclosing rectangle K61 and the enclosing rectangle K62 is generated. When the enclosing rectangle K66 is generated, the enclosing rectangle K66 overlaps the enclosing rectangle K63. Therefore, they are integrated, and the enclosing rectangle K67 encompassing the enclosing rectangle K66 and the enclosing rectangle K63 is generated as shown in FIG. 1C. When the enclosing rectangle K67 is generated, the enclosing rectangle K67 overlaps the enclosing rectangle K64. Therefore, they are integrated. Similarly, all enclosing rectangles K61 through K65 shown in FIG. 1A are integrated, and the enclosing rectangle K68 encompassing the enclosing rectangles K61 through K65 is generated as shown in FIG. 1D.
Also, there is the problem that it takes too long a time to perform the overlapping nest integrating process when there is a headline with a photograph, drawing, or texture.
The first object of the present invention, relating to the technology of recognizing an image by reading a document, drawings, etc., is to provide a character string extraction apparatus for extracting a character string from a complicated image, and recognizing even a thin character line and recognizing a character without mis-recognizing a character color.
The second object of the present invention is to provide a pattern extraction apparatus capable of performing the partially-overlapping nest integrating process.
The character extraction apparatus according to the present invention extracts a character string from an image, and includes: a connected element extraction unit for extracting connected elements containing serial picture elements of the same color based on the color of the picture elements of the input image; a grouping unit for dividing the connected elements into groups probably having the same character strings or the same character string groups based on the relative positions of the connected elements and the ratio of the number of the boundary picture elements to the total number of picture elements forming the connected elements; a character recognition unit for performing a character recognizing process on each group, and defining, as a character recognition level of a group, a sum of the inverse numbers of the distance values of the first character candidates of the recognition results; a combination evaluation unit for defining, as a group evaluation value, a value obtained by weighting the character recognition level of the group by the area of the rectangular area occupied by the group, and defining, as a combination evaluation value, a sum of the group evaluation values of all combinations of groups; and a character string extraction unit for extracting as a character string a combination of groups having the highest combination evaluation value.
The character extraction apparatus according to the present invention extracts connected elements containing a series of black picture elements from an input image and its black/white inverse image when the input image is a binary black-and-white image.
Furthermore, the character extraction apparatus according to the present invention relates only the groups occupying their rectangular areas not overlapping each other, and obtains all combinations of groups having rectangular areas not overlapping each other.
The storage medium according to the present invention is a computer-readable storage medium which stores a program, and allows the computer to function as a character extraction apparatus, including the following function, for extracting a character string from an image: a connected element extraction function for extracting connected elements containing serial picture elements of the same color based on the color of the picture elements of the input image; a grouping function for dividing the connected elements into groups probably having the same character strings or the same character string groups based on the relative positions of the connected elements and the ratio of the number of the boundary picture elements to the total number of picture elements forming the connected elements; a character recognition function for performing a character recognizing process on each group, and defining, as a character recognition level of a group, a sum of the inverse numbers of the distance values of the first character candidates of the recognition results; a combination evaluation function for defining, as a group evaluation value, a value obtained by weighting the character recognition level of the group by the area of the rectangular area occupied by the group, and defining, as a combination evaluation value, a sum of the group evaluation values of all combinations of groups; and a character string extraction function for extracting as a character string a combination of groups having the highest combination evaluation value.
According to an aspect of the present invention, a combination of portions, whose areas do not overlap each other based on the recognition results of the patterns obtained from an input image and its black/white inverse image, is defined as an extraction result of the pattern from the input image.
In the conventional technology, when characters formed by black picture elements and white characters against the black background co-exist in a headline of newspapers, etc., the color of a character is determined by the number of black character candidates and white character candidates. Therefore, when it is determined that the character color is black, only the connected elements of the input image is to be processed thereafter and a black character can be correctly recognized, but a white character against the black background cannot be recognized. Similarly, when it is determined that the character color is white, only the connected elements of the black/white inverse image is to be processed for character recognition and a white character against the black background can be correctly recognized, but a black character cannot be recognized. According to the present invention, the above described mis-recognition can be avoided. Thus, a character string can be extracted with precision from a complicated image comprising a background pattern containing a combination of white and black portions, various types of fonts, a color document, a plurality of lines, a combination of vertical and horizontal character strings, and a compound of them.
An aspect of the present invention includes a connected element extraction unit for extracting the connected elements of an input image ; an enclosing rectangle generation unit for generating an enclosing rectangle of the connected elements; a histogram generation unit for generating a histogram obtained by weighting the frequency in the input image by the area of the enclosing rectangle; and a character size estimation unit for estimating the size of an enclosing rectangle indicating the maximum value of the histogram as the character size of the input image.
Thus, even if a character is formed by a plurality of separate strokes, not processed in the overlapping nest integrating process, and therefore an enclosing rectangle generated for each stroke remains as is, the enclosing rectangle formed by a part of one character is smaller than an enclosing rectangle formed for an entire character. As a result, the evaluation of the frequency of the enclosing rectangle formed by a part of one character can be set lower, and the influence of the size of a part of a character can be reduced in estimating the size of a character. Therefore, the character size can be estimated with high precision even when the overlapping nest integrating process is not performed.
Another aspect of the present invention includes a grouping unit for grouping the enclosing rectangles generated by the enclosing rectangle generation unit; a box rectangle extraction unit for extracting the second enclosing rectangle which contains more than or equal to a predetermined number of the first enclosing rectangles having a character size estimated by the character size estimation unit; and a box rectangle removal unit for removing the second enclosing rectangle from the enclosing rectangles to be grouped.
Thus, when headline characters are extracted from newspapers, etc., and when a box rectangle enclosing text characters exists near the headline characters, only the box rectangle can be extracted, thereby distinguishing the box rectangle from the enclosing rectangle for the headline characters. As a result, only the headline characters can be extracted with high precision.
A further aspect of the present invention includes a projection unit for projecting the rectangle number assigned to the enclosing rectangle to the coordinates set on the input image. The box rectangle extraction unit extracts the first enclosing rectangle by searching the range of the coordinates of the second enclosing rectangle for the rectangle number contained in the coordinates.
Thus, an enclosing rectangle existing in another enclosing rectangle can be easily extracted. As a result, even if a box rectangle enclosing text characters and headline characters coexist, only the box rectangle can be quickly extracted.
A further aspect of the present invention includes a connected element extraction unit for extracting the connected elements of an input image; an enclosing rectangle generation unit for generating an enclosing rectangle of the connected elements; an overlap level evaluation unit for computing the number of enclosing rectangles overlapping the enclosing rectangle; and an overlapping nest integration unit for performing an overlapping nest integrating process.
Thus, the overlapping nest integrating process is performed only on the enclosing rectangles having a high overlap level, and the process can be omitted on enclosing rectangles having a low overlap level. As a result, an enclosing rectangle of headline characters can be prevented from being lost by enclosing rectangles being integrated on the entire screen, and a part of a drawing or a photograph having a high overlap level can be absorbed or integrated into a larger rectangle. Thus, it can be avoided that an enclosing rectangle of a part of a drawing or a photograph remains as is to be mistakenly extracted as headline characters or mistakenly integrated into a rectangle as headline characters. As a result, headline characters can be extracted with high precision even if the headline characters coexist with a drawing, a photograph, etc.
A further aspect of the present invention includes a projection unit for projecting the rectangle number assigned to the enclosing rectangle to the coordinates set on the input image; and an overlapping rectangle extraction unit for extracting an enclosing rectangle overlapping a predetermined enclosing rectangle by searching the range of the coordinates of the predetermined enclosing rectangle for a rectangle number contained in the coordinates.
Thus, enclosing rectangles overlapping each other can be easily extracted, thereby quickly computing the overlap level of the enclosing rectangles.