JPH0373911B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a block detection device, and more particularly to a block detection device for automatically detecting blocks recorded in drawings, such as block diagrams of electrical circuits or flowcharts of computer programs.

In general, a drawing consists of a figure and its background, and the figure essentially consists of blocks representing circuit elements, functions, etc., and connecting lines that relate them.

Therefore, in order to read, digitally process, and store such drawings, it is important to know the existence of blocks and their positions.

In addition to vertical and horizontal line segments, diagonal line segments and circular arcs with arbitrary inclinations are generally used as figures representing such blocks, but the blocks handled by the present invention are vertical and horizontal line segments and 45° It is limited to closed loops or closed figures composed of diagonal line segments with a slope of . Note that in drawings processed by such a block detection device, all figures other than blocks must be composed of vertical, horizontal, and 45° line segments.

At this time, it is a necessary condition that the block displayed in the drawing is a closed loop, but a closed loop is not necessarily a block, so it is difficult to judge whether the detected closed loop is a block or not. Is required.

Conventionally, in order to input drawings such as block diagrams and flowcharts, it was often necessary to completely rely on manual input using means such as a digitizer. A comprehensive and effective block detection device has not been provided.

SUMMARY OF THE INVENTION An object of the present invention is to provide a block detection device necessary for automating such drawing input processing, and further to provide an automatic input device embodying the block detection device.

The block detection device of the present invention photoelectrically converts the gray level at a group of observation points arranged in a two-dimensional array within a rectangular area in a block diagram or flowchart diagram, and holds a value obtained by quantizing the signal into binary values. an image storage unit that thins the graphic information held in the image storage unit, a line thinning unit that thins the graphic information held in the image storage unit, and a connection memory that stores whether or not the graphic information in the image storage unit is connected with the same quantization value. a tracing means for tracing the thinned graphic information in the image storage section; and a determining means for determining which fork in the road the tracing should proceed at a branch point detected when tracing the graphic information. , a control means for controlling whether or not to continue tracing the graphic line at the branch point;
and determining means for determining whether or not the point being tracked coincides with the tracking start point.

Next, embodiments of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing one embodiment of the present invention.

FIG. 2 is a plan view showing an example of a drawing processed by the embodiment shown in FIG. 1, and shows a part of a simulated logic electrical circuit diagram.

There are three blocks 202, 203, and 204 in the observation point group array area whose outermost edge is indicated by a rectangle 201 in the logic electrical circuit diagram, and each block represents a circuit element such as a gate, an inverter, a flip-flop, etc. ing. Connection line 205 is a connection line that represents the connection relationship between circuit elements.

Here, all blocks 202, 203, 20
4 is a closed loop formed by vertical, horizontal and 45° line segments, but there are other closed loops 206 and 207 as well. However, these are not blocks, but merely closed loops formed by the intersections of connecting lines 205.

Therefore, in order to detect the existence and position of a block, a means is required to distinguish between a true block and other mere closed loops, that is, closed loops other than blocks.

The general flow of processing according to an embodiment of the present invention will be explained with reference to FIG.

Each bit of the image storage unit 107 stores a group of observation points on the drawing that have been photoelectrically converted and binarized into white and black. Each observation point is stored as a bit, for example, where black is "1" and white is "0", where "1" represents the graphic information, that is, the part where a pencil etc. is marked, and "0" represents the background part of the drawing. are doing.

At this stage, the line segments composing the figure have an undefined width due to the thickness of the lead of the pencil or sharp pencil, so the line thinning circuit 101 extracts the figure information in the image storage unit 107. Convert to graphical information with a width of no more than 1 bit. Thinning circuit 1
01 may be of any generally known type.

Next, the closed-loop detection circuit 102 first resets all the connection storage sections 106, which have bits in one-to-one correspondence with the bits of the image storage section 107, to "0", and then resets the connection storage section 106 corresponding to the outermost line in the drawing 201. The bit in the storage unit 106 is set to “1”, and the bit that is “1” on the image storage unit 107 is set as an obstacle. bits directly adjacent to the direction). As a result, the image storage unit 107
Among them, all the bits outside the closed loop formed by the bits set to "1" are set to "1" on the connected storage unit 106, and the bits inside the closed loop remain as "0". This allows the position of the closed loop on the drawing 201 to be known. The closed loop detection circuit 102 can use the circuit of Patent Application No. 56-090246 ("Closed Figure Detection Method"). Since the method of patent application number 56-090246 cannot detect a closed loop that exists inside a closed loop,
It is necessary to perform similar processing for the inside of the closed loop, and it is repeated until "1" can no longer be set in the connected storage unit 106.

In the present invention, in order to determine whether or not each detected closed loop is a block, the trace circuit 104 generates a bit set to "1" in the image storage unit 107. Perform closed-loop tracking. At this time, the tracking direction is specified as either clockwise or counterclockwise, and if a branch point is encountered during tracking, the tracking direction will be set to the far right if the track is clockwise, or to the left if the track is counterclockwise. By selecting a changing crossroad and continuing tracking, it is possible to definitely track a closed loop over the shortest distance.

Trace end point determination circuit 105 is trace circuit 1
This circuit monitors the operation of 04 and determines that one closed-loop tracking is completed when the tracking reaches the same coordinates as the starting point. The singular point detection circuit 103 works in cooperation with the trace circuit 104 and has the role of detecting branch points and break points and determining the operation of the trace circuit 104.

FIG. 3 is a plan view showing another example of the drawing processed by the embodiment shown in FIG. 1, and is a part of a simulated logic circuit diagram different from that shown in FIG. 2. Assume that this is held in the image storage unit 107 in a thinned state. The function of the trace circuit 104 will be further explained with reference to FIG.

In FIG. 3, the closed loop 301 is
This is one of the blocks inside. When tracking starts clockwise from the tracking start point 302, the branching points 303, 304, 305 and refraction points 306 to 3 are reached by the time the tracking start point 302 is reached again and one tracking is completed.
Encounter 09. The branch points 303 to 305 and the refraction points 306 to 309 are considered as singular points during tracking,
It is detected by the singular point detection circuit 103.

If a four-branch point 310 is encountered during tracking, it is determined that the closed loop 311 being tracked is just a closed loop and not a block.

In the closed loop tracking process 301, branch point 3
04 and 305 are three branching points, and the branching point where the direction changes to the rightmost side results in the same tracking direction as the previous tracking direction, and the tracking direction does not change. Branching point 30
3 is also a 3-way junction, but if you take the junction where the direction changes to the far right, the tracking direction up to that point will change.
The tracking direction changes to the right by 45 degrees.

On the other hand, the non-block closed loop 312
Branching points 305, 304, 313 when tracing
is a three-way junction, but if you take the fork in which the tracking direction changes to the far right, the tracking direction changes to the far right.
The tracking direction changes 90 degrees to the right.

In this way, even if the tracking direction changes by 90 degrees or more at the three branch points, it can be determined that the closed loop being tracked is not a block.

A closed loop, such as closed loop 301, in which tracking is completed without encountering any four branch points or three branch points where the tracking direction changes by more than 90 degrees can be detected as a block.

The singular point detection circuit 103 consists of a part for detecting a refraction point and a part for detecting a branch point. Fourth
The figure is a block diagram showing an example of a refraction point detection section included in the singular point detection circuit 103. This circuit can detect refraction points and determine the amount of change in the following direction at refraction points and branch points. .

The current tracking x and y coordinate values are applied as digital values to inputs 406a and 406b. The tracking coordinate value 40 is input to the subtracters 402a and 402b.
6a, 406b and shift registers 401a, 40
Tracking coordinate values 407a and 407b several steps earlier delayed by 1b are given, and the difference 408a and 408b represents the direction of tracking as an x, y vector.

The number of stages of the shift registers 401a and 401b is determined depending on the size of the symbol on the drawing and the thickness of the lead of the pencil or sharp pencil, but in general drawings
When reading something written with a 0.5 mm sharp pencil using a group of observation points spaced at 0.1 mm intervals, about 7 lines is appropriate.

The direction quantization ROM 403 quantizes the x and y vectors in eight directions, and outputs the numbers "0" to "7" representing the tracking direction as a quantized concatenation direction 409. The quantization tracking direction 409 is delayed by one step in the one-stage shift register 404 together with the delay tracking direction 410 and the subtracter 40 modulo "8".
Added to 5. When the direction does not change, the amount of change in tracking direction 411 is always “0”, but if there is a change in the direction, the direction and magnitude of the change appear in the amount of change in tracking direction 411, which is used to detect the refraction point. It is possible to know the direction and amount of change in the tracking direction at branching points and bending points.

The direction quantization ROM 403 shown in FIG. 4 uses tracking direction vectors Δx, Δy given as input values.
This is a ROM (read-only memory) in which values of "0" to "7" as shown in FIG. 5 are written in addresses corresponding to the values (408a, 408b in FIG. 4).

In the example of writing in the direction quantization ROM 403 shown in FIG. 5, −3≦△x≦3,
Although it is written that -3≦△y≦3, in practice, when the number of stages of the shift registers 401a and 401b is n, -n≦△x≦n, -n△y≦n
ROM with address range is required. In Figure 5, the numbers "0" to "7" in the squares represent the quantization direction in the direction indicated by the arrow in Figure 6, and are the numerical values output as the quantization tracking direction 409 shown in Figure 4. be. The X symbol at the center point in FIG. 5 indicates that it does not matter what is written because it is never actually addressed. By employing such directional quantization means, the true refraction point can be detected while ignoring minute waviness due to writing errors in drawings.

FIG. 7 is a block diagram showing an example of a branch point detection section included in the singular point detection circuit shown in FIG.
The mask circuit 701 shown in the figure is simply a ROM, and as input, the pixel a of the current tracking point and the surrounding pixels b ₀ to b ₇ as shown in FIG. 8 are given, and an example is shown in FIG. 9. 3. Examples are shown in 4 branching points and Figure 10.
The contents of the ROM are determined so that "1" is output only when a branch point is given to the input.

As a result, in FIG. 7, a circuit is obtained that excites the output only when the coordinate point being tracked is a 3-branch point or a 4-branch point.

The present invention realizes a block detection device that detects the presence and position of closed-loop blocks made up of vertical, horizontal, and 45° line segments in automatic drawing reading, for which no practical device has hitherto been provided. It became possible.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing one embodiment of the present invention;
2 is a plan view showing an example of a simulated logic circuit of a drawing processed by the embodiment shown in FIG. 1, and FIG. 3 is a plan view showing another example of a drawing processed by the embodiment shown in FIG. 1. 4 is a block diagram showing an example of the refraction point detection section included in the singular point detection circuit shown in FIG. 1; FIG. 5 is a write state diagram in the direction quantization ROM shown in FIG. 4; FIG. 6 is a direction explanatory diagram showing an example of a quantized direction written in the direction quantization ROM, and FIG. 7 is a block diagram showing an example of a branch point detection section included in the singularity detection circuit shown in FIG. 1. , FIG. 8 is an input relationship diagram of input pixels to the mask circuit shown in FIG. 7, FIG. 9 is a memory state diagram showing an example of four branch points in the mask circuit shown in FIG. 8, and FIG. FIG. 3 is a memory state diagram showing an example of three branch points in the mask circuit shown in the figure. 101... Thinning circuit, 102... Closed loop detection circuit, 103... Singularity detection circuit, 104...
Trace circuit, 105... Trace end point determination circuit, 106... Connection storage section, 107... Image storage section, 201, 300... Drawing, 202, 203,
204...Block, 205...Connection line, 20
6,207...Closed loop, 301...Block,
302...Tracking starting point, 303, 304, 305,
310,313... Branching point, 306,307,3
08,309...Inflection point, 311,312...Closed loop, 401a, 401b...Shift register, 402a, 402b...Subtractor, 403...
Direction quantization ROM, 404...1-stage shift register, 405...subtractor, 406a...current tracking coordinate value x, 406b...current tracking coordinate value y,
407a... Past tracking coordinate value x, 407b...
Past tracking coordinate value y, 408a...x component of tracking direction vector, 409b...y component of tracking direction vector, 409...quantized tracking direction, 410...
Delay tracking direction, 411... Tracking direction change amount, 70
1...Mask circuit.

Claims (1)

[Claims] 1. An image storage unit that photoelectrically converts the gray level at a group of observation points arranged in a two-dimensional array in a rectangular area in a block diagram or a flowchart diagram, and stores a value obtained by quantizing the signal into binary values; A thinning means for thinning the graphic information held in the image storage unit, a linking storage unit for storing whether or not the graphic information in the image storage unit is connected with the same quantization value, and the image storage unit a tracing means for tracing the thinned graphic information in the middle; a determining means for determining which fork in the crossroads the tracing should proceed at a branch point detected when tracing the graphic information; What is claimed is: 1. A block detection device comprising: a control means for controlling whether or not to continue tracking processing; and a determining means for determining whether a point during tracking processing coincides with a tracking start point.