JPS603674B2 - Preprocessing device for shape recognition - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention is necessary for discussion of figures such as flowcharts in which figure elements consisting of open loops such as circles, triangles, and quadrilaterals are connected to other similar closed loop figures by line segments. More specifically, the present invention relates to a device for recognizing closed-loop graphic elements and their connected states.

As is well known, a flowchart for explaining the operating status of an information processing system consists of a plurality of graphical elements such as rectangles, diamonds, circles, etc. connected by line segments and characters written on the graphical elements or symbols. In addition to character recognition, graphic recognition of symbols and their connected states is required for automatic discussion of flowcharts. In addition, the diagram showing the arrangement status of water pipes for each household shows each household on the map as a circle, and connects each circle with a line segment according to the status of the water pipes. When performing statistical processing on such figures, it is desirable to have automatic discussion of the figures. There are many other shapes in which closed-loop graphic elements are connected by line segments. The present invention proposes such a preprocessing device for figure recognition, and its feature is that a plurality of simple figure elements of a predetermined range of sizes are connected by line segments in a closed loop. In a figure recognition preprocessing device that cuts out a figure element in a figure formed by a figure and detects the number of line segments connected to it, four coordinates indicating the limits of the internal space of the figure element in the X and Y axis directions an extraction means for extracting points; a frame creation means for adding a certain darkness value to these coordinate points to create a quadrilateral frame surrounding the graphic element and having sides parallel to the x and Y axes; The present invention further includes a connecting line number detecting means for determining the number of connecting lines by examining line segments passing through the frame along the frame.

This will be explained in detail below with reference to the drawings. FIG. 1 shows an example of a figure formed by connecting a plurality of circular symbols PE with a straight line 1, and FIG. 2 shows an example of a figure formed by connecting a plurality of diamond-shaped symbols PE with a straight line 1. Recognizing these figures requires cutting out each symbol and extracting the state of interconnection. That is, as shown in Figure 3, if each circle symbol is numbered 1, 2...5, then in this example, symbol 1 is connected to symbols 2 and 3, and symbol 2 is connected to symbols 2 and 3, and symbol 2 is connected to symbols 2 and 3. However, it is important to understand the state of this connection. The present invention relates to preprocessing for such symbol extraction and interconnection state extraction, and includes creating a frame surrounding the symbol from a position indicating the existence of the symbol;
It is used to know how many connecting lines are coming out from the frame.
There are two types of frames depending on the shape of the figure. The first is when the target symbol is a circle, square, etc. In this case, the circumscribed quadrilateral of the symbol is a square, so the frame is also a square (this figure is called a simple figure). The second is that the target symbol is an ellipse, a rectangle,
In the case of a rhombus, etc., in this case, the circumscribed quadrilateral frame is a rectangle, so the frame is also a rectangle (this figure is called a complex figure). First, the preprocessing apparatus of the present invention for simple figures will be explained with reference to FIG. First, the circular figure element 11 is recognized by scanning, but this is because if the circle figure is drawn with black lines on a white background, the size of the closed loop figure element targeted by the present invention is within a certain range. The beginning is from white to black, then a white part appears between the black parts, and the length of the white part can be recognized as being less than a certain value, and the end of the closed loop is the reverse algorithm and a position within a predetermined distance. When these start and end points are found, it is assumed that they are the start and end points of an open loop about one coordinate axis (Y axis when scanning is performed in the x direction). In this example, the start and end points for the other coordinate axis, the X-axis, are obtained by performing a similar scan in the Y-axis direction, for example. A closed loop is also formed by graphical elements 1, 2, 5, 3 in Figure 3 and straight lines connecting them, but this is not considered because the length of the white part between the black parts is greater than a predetermined value. It's easy to understand. In addition, points P, etc. are also recognized as starting points, but in this case, as the scanning in the X-axis direction progresses, the length of the white part between the black parts will soon exceed a predetermined value, and the end point corresponding to the start point will be within a predetermined distance. Since it cannot be found, it can be determined that it is not the starting point of a closed loop. The open loop figure 11 can be recognized by scanning, and the coordinate values of the four start and end points in the x and Y coordinate axes directions of the closed loop, namely the start point S and end point S' in the Y axis direction, and the start point and Once the end points S2 and S'2 are determined, the center coordinates C of these four points are determined. In the case of a simple figure, the distances from point C to the four points are all equal, so point C can be easily determined using this property. Next, a square frame 12 with a line width W of twice the distance 1 from the center coordinate point C to one of the four points above is added, and a margin (separate value) mountain day is drawn. Each side of this square frame is parallel to the X and Y axes. Next, along this frame, check whether there is a line that intersects the frame or not, and find the intersection points E,,E
The number 2, E3, in this example 3, is the number of connections that the figure 11 has. Next, a processing method for complex figures will be explained with reference to FIG.

In general, there are not many graphical processes that can be solved by the above-mentioned simple graphical processing method, and the processing method of this example is often used. In this example as well, the four coordinate points S, S', and S2, S'2 of the closed loop figure 15 are determined by the operations described above. Next, a quadrilateral frame 13 with sides parallel to the x and Y axis passes through these four points.
make. This quadrilateral frame 13 is a quadrilateral frame that passes through the internal points S, , S', , S2, and S'2 of the closed-loop figure 15 (which are inside by the line width of the figure 15). A quadrilateral frame 14 expanded outward is created by adding line width and horizontal and vertical margins dH and dV. Examine the intersecting lines along this frame 14 in the same manner as above and find the intersection points E, , E2.
, E3. A simple method for detecting a cross line is scanning. For example, by searching inside and/or outside the frame 14, a cross line can be easily detected. Of course, this scanning does not have to be actually performed; for example, starting point S,
The scanning data obtained when scanning for detecting the end points S' and S' may be stored in a memory, and this memory may be retrieved (at an address along the outside of the frame 14). If an intersection line can be detected, the x and y coordinates of the intersection point, that is, the address, can of course be known. FIG. 6 shows the extraction flow of these intersection points. The center value C is extracted from the start point and end point information of the input figure obtained by horizontal and vertical scanning, and then the closed state value S in the horizontal and vertical directions (S=S,,S
2, S',, S'2) and extract C-S,, C-S2...
Calculate the distance between... If these distances are all equal, it is a simple figure; if not, it is a complex figure. If it is a simple figure, add the cutoff value dH to create a quadrilateral frame 12, and if it is a complex figure, create a quadrilateral frame 13 that passes through S. , then add the barrier value peak day, dV to create a rectangular frame 14, and these frames 12,
Intersection points E, , E2, and E3 are extracted along 14. 7th
The figure shows an overview of the intersection point extraction circuit.

21 is a detection circuit for the closed-loop start point S, which receives the X-direction scanning data, and calculates the ×, Y coordinates (XS,, Y
Find S,).

Reference numeral 22 denotes a closed loop end point detection area determination circuit, which determines the existence of a closed loop end point as shown in a chain line frame 25 based on the previously known size of the closed loop to be recognized and the coordinate values of the detected start point S. The X, Y coordinate values of the planned range X,,X2,Y,,Y2 are
It is determined that XS, 10dQ, Y, = YS, 10dQ', Y2 = YS, 10d8.

Here, dQ, dQ', and d8 are numerical values indicating the size of the expected range of existence, which is appropriately determined in anticipation of deviation. 23 is a detection circuit for the closed loop end point S', which detects the end point S using the reverse algorithm described above, that is, under the condition that the top is white between black and the bottom is black.
′, is detected.

24 is a closed loop determining circuit which, when the end point S' from the circuit 23 appears within the specified area from the circuit 22, knows that the scanned figure is a closed loop to be recognized, and selects the end point S', from the closed loop. Assuming that it is the end point, its X, Y
Output the coordinate values (XS', YS',).

Next, 26 is a black-and-white change detection circuit, 27 is a black-and-white change detection circuit, and 28 is a counter, which receives a start pulse from the circuit 26 when black changes to white and starts clock counting. A stop pulse is received from the circuit 27 when the color changes from to black, and the above operation is performed after a signal (input from the circuit 21 to the circuit 26) indicating that the start point S is detected, Since the counter 28 stops when there is a signal (inputted from the circuit 24 to the circuit 26) indicating that the end point S' has been detected, the counter 28 ends up indicating the width in the x-axis direction within the closed loop. 29 is a maximum value detection circuit which receives the output of the counter 28 for each scan, and writes the current output to the maximum value circuit 30 if the counter output (count value) is larger in the current scan than in the previous scan.

Therefore, after the detection of the starting point S, the stored value of the circuit 30 gradually increases, reaches the maximum at the maximum point, and thereafter updates of the stored contents are stopped. The start and end coordinates at this maximum width are S2 (XS2, YS2), S'2 (XS'2, YS'2)
) are the coordinates of the open loop start point and stop point during Y-axis scanning, and these coordinates S2 and S'2 are the coordinates at the time when the maximum width is detected and when the circuits 26 and 27 produce outputs. can be easily obtained by memorizing. The circuit 31 connects these start and end points S,,S2,S
',,S'2 are received from the circuits 21, 24, and 30, and the primary frame determination circuit 32 and the secondary frame determination circuit 33 determine the primary frame 13 and the secondary frame in the manner described above based on these points. 12,14
is determined, and the connection point detection circuit 34 detects connection points E, to E3 from the secondary frames 12 and 14. Note that this closed-loop graphic element recognition method is preferably applied to convex shapes, and has some problems with concave shapes.

For example, if we consider a three-moon shape as a concave figure and assume that it is arranged with both ends up and the center down, as is clear from the above explanation, two starting points S, will occur,
One end point can be detected as desired, but the start point S2 and end point S'2, which determine both sides of the figure, cannot be obtained by the maximum value circuit 301. In addition, in this graphic element recognition method, only the outline of the graphic element is black, that is, one of the binary data is "1", and the inside is white like the outside, that is, the white of the fabric, and in this example, the other of the binary data is "1". 0, 1, and on the other hand, in a flowchart, various characters are written inside the graphic elements, which gets in the way.However, this problem can be solved by changing the color of the graphic elements and the color of the text. As explained in detail above, according to the present invention, a graphic element is cut out from a figure in which a plurality of simple graphic elements consisting of open loops are connected by line segments, and It is possible to estimate the connected graphic elements by detecting the number of connecting lines and the position of the connecting lines, and it is extremely effective as a preprocessing device for complete recognition of the figures.

[Brief explanation of drawings]

Figures 1 to 3 are explanatory diagrams showing examples of figures in which figure elements are connected by line segments, Figures 4 and 5 are diagrams explaining how to find figure element connection lines, and Figure 6 is a flowchart. , 7th
The figure is a block diagram showing an embodiment of the present invention. In the drawing, PE, 11, 13 are graphic elements, 1 is a connecting line, and S
,,S',,S2,S'2 are four coordinate points, 12, 14
is a quadrilateral frame. Figure 1 Figure 2 Figure 3 Figure 4 Figure 5 Figure 6 Figure 7

Claims (1)

[Claims] 1. Cut out a graphic element in a figure formed by connecting a plurality of simple graphic elements of a predetermined range of sizes formed by closed loops with line segments, and calculate the number of line segments connected to it. In the preprocessing device for figure recognition to be detected, the extraction means for extracting four coordinate points indicating the limits in the X and Y axis directions of the internal space of the figure element also adds a certain threshold to these coordinate points to a frame creating means for creating a quadrilateral frame that surrounds a graphical element and has sides parallel to the X and Y axes; 1. A preprocessing device for figure recognition, comprising: means for detecting the number of connected lines. 2. The extracting means scans the graphical element in the X and Y axis directions and extracts one of the binary data "1" indicating the outline of the graphical element and the other binary data "1" indicating the ground where the graphical element is drawn. 0
”, and the “1” signal obtained in the previous scan changes to the “0” signal sandwiched by the “1” signal in the current scan, thereby determining the starting coordinates of the closed loop graphic element in the X and Y axis directions. When a point is detected and the "0" signal interposed between the "1" signals obtained in the previous scan changes to a "1" signal, and it occurs within a predetermined distance range from the starting coordinate point, Y
The preprocessing device for figure recognition according to claim 1, characterized in that the terminal coordinate point of the closed loop figure element in the axial direction is detected.