JPH022193B2 - - Google Patents

Description

[Detailed Description of the Invention] (1) Technical Field of the Invention The present invention relates to a character separation and extraction method that can separate and extract individual characters from a character string in which a plurality of characters are written close to each other. .

(2) Prior Art and Problems Conventional methods for separating and extracting character strings include methods in which a window of a certain shape, for example, a rectangle, is scanned over a character string to extract individual characters. In the case of character strings written close to each other, it has been impossible to accurately separate and extract these characters. In contrast, the applicant filed a patent application in 1983.
- No. 157237 Proposed "Character separation and extraction method". Although this method is very effective in separating and extracting adjacent characters, the problem is that it takes a long time to process labels as a preprocessing process when determining the shortest path.

(3) Purpose of the Invention The purpose of the present invention is to develop a character that can accurately separate each character even when multiple characters are written close to each other, and that can speed up the labeling process for finding the shortest path. The purpose is to provide a separation extraction method.

(4) Structure of the Invention In order to achieve the above object, the character separation and extraction method of the present invention divides a character string consisting of a single character or a plurality of characters into a rectangle that is one pixel larger in each direction than its circumscribing rectangle. For the extracted image,
A 1-pixel wide window that is perpendicular to the character string direction and whose length is equal to the rectangular width is scanned from one end of the rectangular area, first detects the position where a black pixel appears in the window, and then calculates the width of the window at that position. A search area for the shortest path between pixels existing at both ends is assigned a label to the pixels of the search area from the window position in the scanning direction, and the shortest path is found by limiting from the label,
The area surrounded by the window and the shortest path is regarded as the area where one character exists, and by sequentially separating and extracting that area, the area where each character exists is extracted from a string of characters written in close proximity. The character separation and extraction method is characterized in that it includes means for labeling pixels in the search area by horizontal and vertical one-dimensional scanning.

(5) Embodiments of the Invention FIGS. 1 to 14 are procedural explanatory diagrams for explaining the present invention using specific examples.

Here, we will show the processing procedure when it is difficult to separate the character string as it is, such as "V _2B " shown in FIG. 1.

Figure 1 shows character strings 11 ₁ to 11 ₃ in a rectangular frame 12 that is one pixel larger in each direction than its circumscribed rectangle.
This shows an image cut out by . This image is scanned with a window 13 shown in the same figure, that is, a window that is perpendicular to the character string direction, has a length equal to the vertical width of the rectangular frame 12, and has a width of 1 pixel from one end of the area within the rectangular frame. The position where the black pixel 14 appears within the window 13 is detected.

FIG. 2 shows the positions where black pixels 14 are detected by the window 13 for the character strings 11 ₁ to 11 ₃ shown in FIG. Next, the shortest path between the white pixels at both end positions "S" and "E" of the window 13 at this position is found.
Limited to the scanning direction of the character string from the position. The character end position 15 indicated by the "+" mark in FIG. 2 is a label indicating the limitation of the search area. That is, the area to the right of the "+" mark is the search area. Although various algorithms have been proposed to extract the shortest path, here, Lee's algorithm will be used for explanation.

Two points “S” determined by the above processing,
One of “E” first, for example “S”
Choose as a starting point. First, the window shown in FIG.
→ Give a label of “3” → “1” → “2” → ....

The logical conditions for labeling in this case are as follows.

() If A ₀ is not a white pixel, skip (proceed scanning).

() When A ₀ is a white pixel and A ₁ is one of the labels “1”, “2”, or “3”, the label next to the label of A ₁ is A ₀
give to For example, the label of A ₁ is “1”
If so, give label “2” to A ₀ . If the label of A ₁ is "3", give the label "1" to A ₀ .

When A ₁ is a label other than "1", "2", or "3", and A ₂ is a label "1", "2", or "3", the next label of A ₂ is Give a label to A ₀ . A ₂ is labeled “1”, “2”,
Skip if it is other than “3” (proceed with scanning)
do.

In addition, as an initial condition, when A ₁ is the starting point "S",
Give label “1” to A ₀ .

FIG. 4 shows an intermediate result of applying the logical conditions shown in FIG. 3 to labeling by horizontal scanning, and FIG. 5 shows the final result.

That is, as shown in FIG. 4, starting with "S", labels are attached to the first line in the order of "1", "2", "3", . . . . The second line is “1”, “2”
, it hits black pixel 14, so skip this.
At the end of the black pixel, the next label in the column is “2”
and the following labels are attached in the order of "3", "1", "2", etc. Thereafter, when a black pixel is encountered, the process is repeated by skipping it, looking at the column, and labeling it, thereby completing the steps in FIGS. 4 and 5.

Next, the window shown in FIG. 3(b) is scanned one-dimensionally in the vertical direction, and labeling is performed under the same logical conditions as in the horizontal direction. At this time, the starting point of the vertical scanning is set at one end of the circumscribed rectangle 12 of the character string and the side 12' opposite to the limited position 15 of the search area.

FIG. 6 shows the intermediate result of labeling by vertical scanning, and FIG. 7 shows the final result when the end point "E" is reached.

In this way, by performing one-dimensional scanning in the horizontal direction and once in the vertical direction, the labeling process is always completed, so that high-speed processing can be realized.

Next comes the cutting stage. Reverse tracing is performed from the end point "E" in the order of "3"->"2"->"1" to find a route that reaches the start point "S".

Although this route is the shortest route, it is not necessarily determined uniquely. Here, as shown in FIG. 8, priority is given to the direction of reverse tracking, and the shortest path is uniquely determined.

FIG. 9 shows the shortest path detected by back tracking, and a label "+" is given to each pixel 16 on the path during back tracking.

Through the above processing, an area where one character in a character string exists is identified as an area surrounded by "+". Therefore, by cutting out the black pixels within this area, the image of one character is separated and extracted.

Figure 10 shows rectangular frame 1 after separating and extracting one character.
An image of character strings 11 ₂ and 11 ₃ in area 2 is shown.

Through the above processing, each time a character is extracted, a white pixel,
After converting pixels assigned labels other than black pixels to white pixels, the process is repeated until no black pixels are detected within the rectangular area, whereby each character of the character string can be separated and extracted one by one.

That is, a window is set for the next character ₁₁₂ , a label representing the limitation of the search area for the next character is determined, and the procedures of FIGS. 4 to 9 are repeated.

FIG. 11 is an explanatory diagram of the configuration of an embodiment of the present invention. In the figure, 21 is a circumscribed rectangle detection circuit that detects a circumscribed rectangle of an input character string image, 22 is an image memory that stores the character string image, 23 is a character cutting circuit that cuts out separated characters, and 24 is a character string image. A window scanning circuit 25 scans a window to detect the end position, a labeling circuit 25 labels the end position of a character and a label for searching for the shortest path, and 26 performs reverse tracing based on the assigned label. 27 is a clearing circuit that erases separated and extracted characters and labels;
Reference numeral 8 denotes an address table that holds the addresses of the circumscribed rectangle of the character string image and the addresses of the start and end points of labeling.

This configuration will be explained with reference to the examples shown in FIGS. 1 to 10.

First, input character string images 11 ₁ to 11 ₃ are stored in the image memory 22 via the circumscribed rectangle detection circuit 21 . At this time, the addresses of the rectangular frames 12 that are larger by one pixel in each direction than the circumscribed rectangles of the input character strings 11 ₁ to 11 ₃ detected by the circumscribed rectangle detection circuit 21 are written into the address table 28 .

The window scanning circuit 24 scans the window 13 from one end of the rectangular area based on the rectangular address held in the address table 28, and detects the character end position 15, that is, the position where the first black pixel appears in the window. . and its position 15
Set one of the ends of window 13 as the starting point (S),
The other is set as the end point (E) and its address is written into the address table 28.

Based on the starting point address, the labeling circuit 25 first generates a label to limit the shortest route search area, and a label to be used for cutting out characters in later processing.
Assigned to character end position 15.

This is a label indicated by a "+" mark in FIG. 2, and is actually a special code to be distinguished from other labels.

Thereafter, the labeling circuit 25 starts from the starting point (S) horizontally and
Vertical one-dimensional scanning is performed once each, and labels are added until the end point (E).

When the labeling reaches the end point (E), the reverse tracing circuit 26 traces the labels backward from the end point (E) in the reverse order of labeling, and traces the labels along route 1 to reach the starting point (S).
Find 6. At the same time, the path 16 found is given the same label "+" as that given to the character end position 15.

The character cutting circuit 23 connects the label “+” at the character end position 15 and the shortest path 1 between the start point (S) and the end point (E).
Black pixel 14 in the area surrounded by the label “+” of 6
is cut out and this image ₁₁₁ is sent to a character recognition device etc. connected to the output.

The clear circuit 27 erases the character area surrounded by the label "+" and each label used for this cutting out, and clears the next character string 11 ₂ , 11 ₃ in FIG.
The above procedure is repeated again for the region defined by the next character end position to be formed.

(6) Effects of the Invention As explained above, according to the present invention, the labeling process when separating and extracting an image of each character from a character string is performed by performing one horizontal and vertical one-dimensional scanning once each. Very high-speed character separation and extraction can be achieved by simply executing the steps one by one. Therefore, even in free-format handwritten characters, individual characters can be separated and extracted reliably and at high speed, so that it can be applied to character recognition of handwritten characters with great effect.

[Brief explanation of drawings]

Figures 1 to 10 are explanatory diagrams of the procedure of the present invention;
Figure 1 is an explanatory diagram of the configuration of an embodiment of the present invention, in which 11 ₁ to 11 ₃ are character strings, 12 and 12' are rectangular frames,
13 is a window, 14 is a black pixel, 15 is a character end position, 16 is a shortest path, 21 is a circumscribed rectangle detection circuit, 22 is an image memory, 23 is a character cutting circuit,
24 is a window scanning circuit, 25 is a labeling circuit, 26 is a reverse tracking circuit, 27 is a clear circuit, 28
indicates an address table.

Claims (1)

[Claims] 1 For an image in which a character string consisting of a single or multiple characters is cut out by a rectangle that is one pixel larger in each direction than its circumscribing rectangle, the length is perpendicular to the character string direction and the width of the rectangle. A window with a width of 1 pixel equal to Limit the area from the window position to the scanning direction side, label the pixels of the search area, find the shortest path from the label, and define the area surrounded by the window and the shortest path as one character exists. In the character separation extraction method, which extracts areas where individual characters exist from character strings written in close proximity by sequentially separating and extracting the areas, the search area is extracted by horizontal and vertical one-dimensional scanning. A character separation and extraction method characterized by comprising a means for labeling pixels of.