JPH04112282A - Word area extracting system - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed description of the invention]

[0001]

[Industrial application field]

The present invention is a word search system that extracts regions of character strings (generally referred to as words) separated by spaces, such as English words, from a document image read by a handy scanner device or a partial image of a document image displayed on a display screen. Regarding area extraction method. [0002]

[Conventional technology]

In a character recognition system, when inputting a document image using a handy scanner device, the reading area may become inappropriate and word extraction (word input) may not be performed correctly. This is because conventional handheld scanner devices were not designed for such word input, and although the reading range could be checked through a viewing window, it was difficult to find the correct reading position for the target word on the manuscript. This is because there was no means for easily confirming whether or not this was the case. [0003] In order to solve such inconveniences, two guidelines (start line and center line) are provided to align the relative positions of the document reading window and the beginning of words and line centers on the document, respectively. A handy scanner device that can obtain scanned images in which the relative position of the region, the beginning of a word, and the center of a line is almost constant, and a handheld scanner device with a guideline that can obtain a read image that uses the guideline position to easily process words. A patent application was filed on July 19, 1990 under the title of "Handy scanner device and word region extraction device" by the same applicant. [0004] There is also a method in which two diagonal vertices of a rectangle surrounding a desired word area are specified on a display screen using a mouse (pointing device) or the like, and the inside of this rectangle is extracted as a word area. However, there is a problem in that it is not easy to specify a rectangle that encloses only the word area when the document has narrow line spacing, narrow inter-word space, or when there are ruled lines close to words. [0005] In order to solve this problem, we define a frame of a certain size that is sufficiently larger than the word area and has a guideline similar to that of the handheld scanner device. ) on the display screen together with the document image, move the frame so that the guideline almost matches the beginning and line of the target word area, use the partial image inside the frame as the input image, and input the position information of the guideline (reference position information). ) and devised a word region extraction method that extracts the target word region through simple processing, and filed a patent application on July 19, 1990 under the title of "Word region extraction method" by the same applicant. is being done. [0006]

[Problem to be solved by the invention]

An object of the present invention is to improve the word region extraction device or word region extraction method related to the above patent application, and to improve the word region extraction device or the word region extraction method according to the above patent application, and to improve the word region extraction device or the word region extraction method according to the patent application. An object of the present invention is to provide a word region extraction method that can more reliably extract word regions even when the image is a human image and the skew of the human image is large. [0007]

[Means to solve the problem]

The invention recited in claim 1 provides a target word area to be extracted, such as a document image read by a handy scanner device with a guideline or a document image in an area specified by a frame with a guideline on a display screen. For an input image that has information on the start reference position and line reference position, extract the line of the target word area by examining the horizontal projection from the line reference position, and calculate the vertical projection of the vicinity of the start reference position for the range of the cut out line. In the word region extraction method, which detects the beginning position of the target word region by examining the target word region and detects the end position of the target word region by examining the vertical projection after the detected beginning position, the input image is The target word area is divided into multiple areas with Features. [0008] The invention according to claim 2 sets search limits for the upper and lower ends of the row in the row extraction of each divided area according to the invention according to claim 1, and even if each search limit is exceeded, the row is still If the position where the horizontal projection value corresponding to the top or bottom edge changes from above the threshold to below the threshold cannot be detected, it is determined that a line connection has occurred at the top or bottom edge, and the process of forcibly separating the connected lines using the horizontal projection value. It is characterized by determining the position of the upper end or lower end of the line of the target word area. [0009] The invention according to claim 3 provides that when two or more rows are cut out in the row cutting of each divided area according to the invention according to claim 1, two or more rows are cut out when a certain condition is satisfied. It is characterized by merging rows. [0010]

[Effect]

According to the invention described in claims 1 to 3, the first reference position (start line position) and the row reference position (
By using the center line position), word regions can be extracted efficiently through simple processing, and lines can be extracted for each divided region in the row direction of the input image while referring to the line clipping results of the immediately preceding divided region. Therefore, compared to a method that performs line cutting for the entire input image at once, even if there is a skew in the input image, line connections are likely to occur due to skew, and this method is useful for documents with narrow line spacing or documents where words and ruled lines are close together. It is possible to more reliably cut out lines in the target word area. [0011] Furthermore, according to the invention of claim 2, since the line connections are determined and the forced separation is performed, it is possible to appropriately cut out the line of the target word even when the skew of the input image is quite large. It is possible to reliably extract word regions even when the skew is likely to be large, such as when an input image is read by a handy scanner device. [0012] Furthermore, according to the invention of claim 3, when a line that should be one line is separated into two or more lines, for example, a black circle above a character such as i or j is cut out as one line. In such cases, it can be corrected to achieve more accurate word region extraction. [0013]

【Example】

FIG. 1 is a block diagram showing an example of a system for implementing the present invention. 1 is a CPU that executes processing and various controls
, 2 is a program memory for storing the operating system, word area extraction processing according to the present invention, and other application programs, 3 is a data memory for storing processing intermediate data, processing result data, etc., 4 and 5 is a CRT display and its interface, 6 is an image memory for storing image data, 7 and 8
is the mouse and keyboard, 9 is its interface, 10
1 is an auxiliary storage device for storing data files such as image data files, an operating system, and various programs; 11 is an interface thereof; and 12 and 13 are handheld scanner devices with guidelines and their interfaces. [0014] The input image to be subjected to the word region extraction process is either an image directly input from the handy scanner device 12 and imported into the image memory 6, or an image imported into the image memory 6 from the auxiliary storage device 10. This is a partial image where an area is designated on the image frame of the CRT display 3. [0015] In any case, as shown in FIG. 2, the human image 20 that is the target of the word region extraction process has a start line 21 that is the first reference position of the target word region and a line reference position of the target word region. I have information about center line 22. [0016] Here, the handy scanner device 12 reads an image of a document through a reading window 30 as shown in FIG. starting line 3
1 and a center line 32. The starting line 21 and center line 22 in Figure 2 are the starting line 3.
1 and center line 32, respectively. When reading a document image with such a handy scanner device 12, the start line 31 is placed at the beginning (left end) of the target word area on the document, the center line 32 is placed at the center of the row of the target word area, and Reading window 30 to match. and read window 3.
Load the image of the 0 area. [0017] Furthermore, when extracting word regions from a document image that has been read page by page by a large image scanner or the like and stored in the auxiliary storage device 10, the document image of the required page is read into the image memory 6, is displayed on the screen of the CRT display 6, and the area of the input image is designated. FIG. 4 is an explanatory diagram of this manual image area designation, in which a frame 41 larger than the word area, similar to the reading window 30 shown in FIG. word (here 'Recogni)
tion") and the center line 4
Draw a frame 41 to match 3 with the row of the target word area.
move. The partial image within this frame 41 becomes the input image for the word area extraction process. The start line 21 and center line 22 in FIG. 2 correspond to the center lines of the start line 42 and center line 43, respectively. [0018] Furthermore, as shown in FIG. 4, the frame 40 may be displayed entirely on the screen without displaying the frame line, and only the start line 42 and center line 43 may be displayed, or the start line 42 and center line 43 may be displayed. Only the intersection of the center lines 43 may be displayed. In short, it is sufficient to align the two guidelines and the target word area. [0019] Next, a process for extracting a target word area from an input image (the image data of which is on the image memory 6) will be described. The overall flow of this process is as shown in FIG. Each processing step will be specifically explained below. [0020] In setting the subregion q, first, the input image 20 with reference position information shown in FIG. 2 is divided into a plurality of regions in the row direction. Adjacent divided areas are made to partially overlap. Figure 6 shows an example of dividing the input image 20 into three parts.
Shown below. Note that, as in this example, the size of the divided area is selected so that the leftmost divided area includes the start line 21. [,0021] 2. Extracting 2 of the 2nd half of the divided region An outline of the processing for one divided region is shown in FIG. Note that this line cutting process is performed in order from the left end (tip) divided region to the right end (tail) divided region. (oozz7 is the position. [0023] It is the starting position. [0024] However, the y-coordinate Y of the line end search starting position satisfies the following condition: image height Xi/4<Y<image height x 3/4 It is determined that there is an error in setting the frame position on the screen of the T-display 4 where the line end search start position that satisfies this condition cannot be set, and the area extraction process ends abnormally. [0025] At this stage Instead of the word area position, the center line position of the currentness extracted in the left adjacent divided area (the line considered to be the line of the target word area) is used as the starting point, as in the case of the leftmost divided area. Find the line end search start position using the following procedure. [0026] However, the conditions that the y-coordinate Y of the line end search start position must satisfy are that the current line upper end of the left adjacent divided area is 10 noise high, and Y<left neighbor The current lower end of the divided area - the noise height.If a line end search start position that satisfies these conditions cannot be set, the line cutting process ends normally. If there is a blank space and the divided area of the blank part (blank divided area in FIG. 5), this is the normal end. If you cannot find the end of a row even if you proceed from the start position of the end of the row search to a position where you can find the end of the row upward or downward, it is likely that adjacent rows are connected. , the line end search should be discontinued up to a certain position.Here, the line end search discontinuation position, which is the search limit, is set [0028] First, the left end divided area will be explained. Since there is no information for estimating the line-end search start position, the line-end search abort position is set at a position that is slightly larger than the maximum height of the character to be processed from the line-end search start position. [0029] Next The divided areas other than the leftmost divided area are explained below. Only the current line is detected in the leftmost divided area, and the line before it (above) is detected.
If neither the row nor the next (bottom) row has been detected, as shown in Figure 8, the height of the current row in the left adjacent divided area is hc
, the position hc above the top of the current line is the upper line end search abort position, and the position hc below the bottom of the current line is the lower line end search abort position. However, if the cutoff position obtained in this way exceeds the top or bottom edge of the image, the top or bottom edge of the image is set as the cutoff position. [00301 On the other hand, if not only the current line but also the previous or next line is detected in the divided area to the left, the position of the divided area to the left is hc above or below from the top or bottom of the current line. If it is below the bottom edge of the previous line or above the top edge of the next line, the respective position is set as the top or bottom line end search abort position. However, as shown in Figure 9, when the position hc above the top of the current line is higher than the bottom of the previous line, the midpoint of both positions is set as the upper truncation position, and similarly the bottom of the current line is When the position below hc is below the top end of the next line, the midpoint position between both positions is set as the lower truncation position.

003 The search for the line end where the horizontal projection changes from on to off is performed downward from the line end search start position to the abort position (step 103). [0032] If a line end is detected, this line end is set as the bottom of the current line, and the position where horizontal projection is turned on again downwards, that is, the top end of the next (lower) line of the current line is searched (step 1
04). [0033] If no line end is detected in the process of step 103,
Since it is determined that the current line and the next line are connected, the process of forcibly separating the connected lines (step 1o5) is performed. [0034] In other words, in the left end divided area, as shown in FIG. The position with the minimum horizontal projection value within the range up to the search abort position is set as the lower end of the current line. [0035] In the divided areas other than the leftmost divided area, as shown in FIG.
The position where the horizontal projection value is the minimum within the range from the position above 4 (he is the height of the current row) to the cutoff position below,
The lower end of the current line in the divided area. Steps 106 to 108 Upward ``〒'' Search - A search for the line end where the horizontal projection changes from on to off is performed upward from the line end search start position for one continuation up to the line end search abort position (step 106 ). [0037] If a line end is detected, this line end is set as the top edge of the current line, and the search is performed upward to find the position where horizontal projection is turned on again, that is, the bottom edge of the line before (above) the current line ( Step 10
7). [0038] If no line end is detected in the process of step 106,
It is determined that the current line and the next line are connected, and processing for forcibly separating the connected lines (step 108) is performed. [0039] In other words, in the leftmost divided area, as shown in FIG. The position with the minimum horizontal projection value is the top of the current line. [0040] In the divided areas other than the leftmost divided area, as shown in FIG. 13, hc/
The position where the horizontal projection value is minimum within the range from the position below 4 (hc is the height of the current line) to the cutoff position above is set as the upper end of the current line in the divided area. [0041] Step 109'-Separation Check and Match Step 1
Check the validity of the forced separation of lines in 05 and 108 from the line height and the line end of the current line in the divided area on the left, and if the separation position is inappropriate and should be merged, merge and replace the current line. Modify the range of. In documents with narrow line spacing or documents with ruled lines close to the target word, line connections are likely to occur if the image skew is large. Even if such a line connection occurs, it is possible to properly cut out the line by performing the line cutting process for each divided area as described above, so that the next word start and end detection process can be performed normally and the desired word can be found. It becomes possible to extract the area. [0042] The contents of the single string pre-sale O weighing main process are as shown in FIG. This word start detection detects the left end of the first character of a word by checking the vertical projection within the currentity range cut out earlier, using the position of the start line 21 as a reference, and detects the left end of the first character of the word using the position of the start line 21 as a reference. The positional relationship of FIG. 15(a),
There are cases as shown in (b) or (C). [0043] First, compare the vertical projection value of the starting line position with the threshold value (step 201). If it is less than the threshold value, there is a high possibility that the case is as shown in FIG. Find a position where the value is equal to or greater than the threshold value, and tentatively determine that position as the left end of the first character, that is, the first position of the word area.Step 202) Does the range of vertical projection values equal to or greater than the threshold value continue to the right of that position? Check (step 203). When the range in which the vertical projection value is equal to or greater than the threshold value continues for a certain value or more, the case is as shown in FIG. . [0044] However, even in the case of FIG. 15(a), noise within the pace between the start line and the first character may be detected as the first position in step 202. Since the condition is not satisfied in step 203 of this case, the process returns to step 202 and searches further to the right for the first character, thereby finally detecting the left end of the first character, that is, the first position of the word area. [0045] If the start line overlaps a certain character as in the case of FIG. 15(b) or (C), it is determined in step 201 that the vertical projection value is greater than the threshold, so A search is made for a position where the vertical projection value is less than a threshold value, and these positions are determined as the left and right ends of the character overlapping the start line (step 205). Then, check whether the width of the character of interest is greater than a certain value (step 206)
. If the character width is equal to or greater than a certain value, the start line is definitely within the character, so it is checked whether the left end or the right end detected in step 205 is closer to the start line (step 207). If the left end is closer to the start line, this is the case as shown in FIG. [0046] If it is determined in step 207 that the right end is closer to the start line, this means that the characters before the first character overlap with the start line, as shown in FIG. 15(b), so the process branches to step 202. , find the beginning of the word area further to the right. [0047] Furthermore, when the character width is determined to be less than a certain value in step 206, which is the case as shown in FIG. 15(a), it is determined that there is noise directly below the start line. The process branches to step 202 to detect the leading position. [0048] Monocular trailing Hiyama processing↓ The processing details are as shown in FIG. This process starts from the first character of a word and examines the spaces between adjacent characters. Characters with narrow spaces are determined to be within the word, and if a wide space is found, the previous character is moved to the end. The right end of the word is detected as the end position of the word area. FIG. 17 is an explanatory diagram thereof [0049] First, a space width threshold value for determining whether the space is wide or narrow is determined (step 301). That is, the reference character width is calculated from the previously detected line height (or the maximum vertical projection value) and a preset character aspect ratio. This value of 1.5 times the standard character width is compared with the width of the space before the first character detected earlier, and if the space width is larger, the space before the first character is invalidated. . Similarly, the standard character width is 0. The 5 times value is compared with the space before the first character, and even if the space width is smaller, the space before the first character is invalidated. [0050] If the space before the first character is invalidated, a value of 1/4 of the calculated reference character width is determined as the space width threshold. If the space before the first character is valid, the average of the value of 1/2 of the space width and the value of 1/4 of the reference character width is set as the space width threshold. [0051] Once the space width threshold is determined in this way, the first character is set as the character of interest (step 302). By examining the vertical projection to the right of the character of interest, the character adjacent to the right of the character of interest is searched (step 303). ). If the adjacent character on the right is not found, the character of interest at that time is determined as the last character of the word, its right end position is detected as the word end position, and this is written in the data memory 3 (step 304). [0052] When a character adjacent to the right of the character of interest is found, the width of the space between both characters is determined and compared with the space width threshold (step 305). If the space width is greater than or equal to the space width threshold, the character of interest is treated as the last character. , its right end is detected as the end position of the word area (step 304). If the space width is smaller than the space width threshold, the character on the right is set as the character of interest again (step 306), and the processing from step 303 is performed. [00'53] Through the above processing, the area from the beginning to the end of the word line range is extracted as a word area. [0054] Next, line cutting processing in the divided area (processing 2 in FIG.
) will be explained using the flowchart shown in FIG. This modification is characterized by separable merging processing. [0055] Step 401 is a processing step for setting a line end search start position similar to step 101 in FIG. Step 402 is a processing step similar to step 102 in FIG. 7 to set the line end search abort position. Step 403'' is from step 103 to step 107 in FIG.
Similar to the previous processing, the processing step knob examines the horizontal projection above and below the line end search start position to the line end search abort position and cuts out the line, but only the current line is cut out. Step 408 is a processing step for forcibly separating connected lines similar to step knob 108 in FIG. [0056] In step 404, the next (below) line of the current line is cut out by checking the horizontal projection downward from the bottom of the current line, with the bottom edge of the image as the line end search termination position. In step 406, the line before (above) the current line is cut out by checking the horizontal projection upward from the top of the current line, with the top of the image as the line end search abort position. [0057] Steps 40.5 and 407 are processing knobs that check line separation and perform separable merging. 20 will be explained. [0'058] Row separations that should be considered for merging can be classified into two types, which are herein referred to as continuity separation and non-continuous line separation. [0059] If a separated line in the divided area currently being processed overlaps the current line in the adjacent divided area on the left, this separated line is the line in which continuity separation has occurred. FIG. 19 shows an example in which continuity separation occurs in the line before the current line in the divided area being processed. [00601] On the other hand, if there is a line separated from the current line without overlapping with the current line in the adjacent divided area on the left, this separated line is a line in which discontinuous line separation has occurred. FIG. 20F shows an example in which a non-continuous line separation occurs between the lines before the current line in the divided area currently being processed. [0061] First, merging of rows that have caused continuity separation will be explained. This merging process is repeatedly executed for both the previous row and the next row as long as a certain condition is met. Furthermore, this includes "merging processing for upper continuous separated rows" by step 407 and "merging processing for lower continuous separated rows" by step knob 405. [0062] The "merging process for the above continuous separated rows" will be explained. The conditions for executing this merge are ``The separating line (separated line of interest) before (above) the current line overlaps with the current line in the divided area on the left side, and the current line in the area on the left side overlaps. The upper end of the separated row of interest is below the position above the upper end by a value equal to one-fourth of the height of the current row. The separated line of interest that satisfies this condition is merged with the current line. [0063] "Merge processing for continuous separated rows below" is a processing for merging the previous row that caused continuity separation into the current row, and its merging condition is the merging condition of "merging processing for continuous separated rows above". The upper and lower relationships are reversed. [0064] Next, the process of merging rows that have caused non-continuous row separation will be described. This is performed in step 407 only for the separate line before (above) the current line. This is because it is generally sufficient to consider the case where a black circle above a character such as i or j becomes a separate line. If all of the following conditions a to e are satisfied, merge the previous row with the current row. a, The lower end of the previous row of interest is above the upper end of the current row within the divided area to the left of the force plate (condition for discontinuous row separation). b. The distance between the previous line of interest and the current line is less than one third of the height of the current line (relationship between line spacing and line height). C0 When the previous row is detected in the divided area on the left, the height of the current line in the divided area currently being processed is increased by one-third from the bottom of the previous line in the divided area on the left. Below the upper position is the upper end of the previous row of interest in the divided area currently being processed. d. In the divided area currently being processed, the height of the current line is
Greater than three times the height of the previous row of interest (row height ratio). e, the maximum character width determined from the vertical projection of the previous line of interest is less than two-thirds of the height of the previous line / trigram (character width)
. [0065]

【Effect of the invention】

As explained above, according to the invention described in claim 1 or 2, word regions can be easily and efficiently created by using the head reference position (start line position) and line reference position (center line position) of the human image. can be extracted, and
Line cutting processing for each divided area in the row direction as well as connecting line separation processing enables documents with narrow line spacing that are likely to cause line connections due to skew, even when the skew of the human image is large, such as when using a handheld scanner for image processing. It is possible to reliably extract a target word area in a document where words and ruled lines are close to each other.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing an example of a system for implementing the present invention.

[Figure 2] FIG. 3 is an explanatory diagram of an input image.

FIG. 3 is an explanatory diagram of a reading window and a guideline of a handy scanner device with a guideline.

FIG. 4 is an explanatory diagram of a method of specifying an input image area on a display screen and a frame with a guideline.

FIG. 5 is a flowchart showing the overall flow of word region extraction processing.

[Figure 6] FIG. 3 is an explanatory diagram of an example of region division of an input image.

[Figure 7] 12 is a flowchart of line cutting processing for each divided area.

[Figure 8] FIG. 6 is an explanatory diagram of a method of setting a line end search abort position.

[Figure 9] FIG. 6 is an explanatory diagram of a method of setting a line end search abort position.

[Figure 10] FIG. 7 is an explanatory diagram of forced connection/separation on the lower end side of a row.

[Figure 11] FIG. 7 is an explanatory diagram of forced connection/separation on the lower end side of a row.

[Figure 12] FIG. 3 is an explanatory diagram of forced connection and separation on the launch end side.

[Figure 13] FIG. 3 is an explanatory diagram of forced connection and separation on the launch end side.

[Figure 14] It is a flowchart of word head detection processing.

[Figure 15] FIG. 2 is an explanatory diagram of the positional relationship between a start line and words.

[Figure 16] It is a flowchart of word end detection processing.

[Figure 17] It is an explanatory diagram of word end detection.

[Explanation of symbols]

CPU 2 Program memory 3 Data memory 4 CRT display 6 Image memory 7 Mouse 8 Keyboard 10 Auxiliary storage device 12 Handy scanner device with guideline 20
Human power device start line center line reading window start line center line screen frame start line center line

[Document core]

drawing

[Figure 1]

[Figure 2]

[Figure 5]

[Figure 6]

[Figure 7]

[Figure 8]

[Figure 9]

[Figure 11]

[Figure 12]

[Figure 13]

[Figure 14]

[Figure 151 [Figure 16] [Figure 17]

[Figure 19]

[Figure 20]

[Figure 18]

【Document name】 【Filing date】 【address】 [Display of incident] 【application number】 [Name of the invention] [Person making the correction] [Relationship with the incident] 【Identification number】 [Name or title] [Agent] 【Identification number】 【patent attorney】 [Name or title] [Shipping number]

[Procedural amendment 1]

[Name of document to be corrected] [Correction target item name] [Correction method] [Contents of correction] [Agent] 【Identification number】 【patent attorney】 [Name or title]

[Procedural amendment 2]

[Name of document to be corrected]

[Correction target item name] [Correction method] [Contents of correction]

Procedural amendment April 22, 1991

Claims (3)

[Claims] Claim 1: For an input image having information on the start reference position and line reference position of the target word area to be extracted, cut out the line of the target word area by examining the horizontal projection above and below the line reference position, and extract the extracted line. For the range of , the starting position of the target word area is detected by examining the vertical projection in the vicinity of the starting reference position, and the end position of the target word area is detected by examining the vertical projection after the detected starting position. In the extraction method, the input image is divided into multiple regions with a certain overlap in the row direction, and for each divided region from the first divided region to the last divided region, the row cutting results of the previous divided region are referred to. A word region extraction method characterized by cutting out lines in a target word region. [Claim 2] In line extraction of each divided area, search limits are set for the upper and lower ends of the line, and even if each search limit is exceeded, the horizontal projection value corresponding to the upper or lower edge of the line is greater than or equal to the threshold. If a position that changes to less than or equal to less than 2. The word region extraction method according to claim 1. 3. The method according to claim 1, wherein when two or more lines are cut out in each divided area, the two or more lines are merged when a certain condition is satisfied. Word region extraction method.