JPH022192B2 - - 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.

(3) Purpose of the Invention The purpose of the present invention is to provide a character separation and extraction method that can accurately separate each character even when a plurality of characters are written close to each other.

(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 window with a width of 1 pixel, which is perpendicular to the character string direction and whose length is equal to the width of the rectangle, is scanned from one end of the rectangular area, and the position where a black pixel appears in the window is first detected, and both ends of the window at that position are scanned. Find the shortest path by limiting the search area for the shortest path between pixels existing in the window position to the scanning direction side,
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. It is characterized by being able to be extracted.

(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 and whose length is 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, a label "1" is given to the white pixel directly adjacent to "S" (four-way connection). Next, a label "2" is given to the white pixel adjacent to the pixel given the label "1". Label “2”
Label "3" is given to the white pixel adjacent to . Furthermore, the white pixel adjacent to the label “3” is labeled “1”.
give. Repeat this below. This procedure continues until the end point "E" is reached.
FIG. 3 shows the results of this labeling procedure.

Next, this label is traced in the reverse order of labeling from the end point "E" to "3" → "2" → "1" → "3" in the reverse order of labeling, and reaches the start point "S". Find a path. Although this route is the shortest route, it is not necessarily determined uniquely. In order to uniquely determine this, as shown in FIG. 4, priorities are set in the direction of reverse tracking, and tracking is performed in accordance with these priorities. FIG. 5 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 image within this area, the image of one character is separated and extracted.

Figure 6 shows the rectangular frame 12 after separating and extracting one character.
This is an image of character strings 11 ₂ and 11 ₃ within the area.

By repeating the above process until no black pixels are detected within the rectangular area, after converting the pixels labeled other than white pixels and black pixels into white pixels each time one character is separated and extracted, the character string Each character can be separated and extracted one by one.

That is, as shown in Figure 7, the next character 11
A window is set for ₂ , a label 17 representing the limit of the search area for the next character is determined, and the labels shown in FIGS.
Repeat the procedure shown in Figure 6.

FIG. 8 is a configuration explanatory diagram 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 clear circuit that erases separated and extracted characters and labels; 28 is an address table that holds the address of the circumscribing 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 7.

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 a black pixel first 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.

After that, the labeling circuit 25 assigns "1" → "2" → adjacent four-way connected pixels from the starting point (S).
Labels that cycle from "3" to "1" are given until the end point is reached.

When the labeling reaches the end point, the backtracking circuit 26
traces the labels back from the end point (E) in the reverse order of labeling and finds a path 16 that reaches the start point (S). 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 cuts out the black pixels 14 in the area surrounded by the label "+" of the character end position 15 and the label "+" of the shortest path 16 of the start point (S) and end point (E), and extracts the black pixels 14 from this image 11 ₁ 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 only the next character strings 11 ₂ and 11 ₃ shown in FIG. 6 are obtained, and the character strings 11 2 and 11 3 shown in FIG. The above procedure is repeated again for the area defined by the character end position 17.

(6) Effects of the Invention As explained above, according to the present invention, even when a plurality of characters are written close to each other, it is possible to separate and extract each character individually. Therefore, even free-format handwritten characters can be separated and extracted individually, which is highly effective when performing character recognition for handwritten characters.

[Brief explanation of drawings]

1 to 7 are procedure explanatory diagrams of the present invention, and FIG. 8 is a configuration explanatory diagram of an embodiment of the present invention.
₁ to 11 ₃ are character strings, 12 is a rectangular frame, 13 is a window, 14 is a black pixel, 15 and 17 are character end positions,
16 is the 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
27 is a clear circuit, and 28 is 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 circumscribed rectangle, the length is perpendicular to the direction of the character string. A window with a width of 1 pixel, which is equal to the width of the rectangle, is scanned from one end of the rectangular area, and the position where a black pixel appears in the window is first detected, and the shortest path between the pixels existing at both ends of the window at that position is determined. The shortest path is found by limiting the search area from the window position to the scanning direction side, and the area surrounded by the window and the shortest path is regarded as an area where one character exists, and that area is sequentially separated and extracted. A character separation and extraction method characterized by making it possible to extract regions where individual characters exist from character strings written in close proximity.