JP2974744B2 - Boundary surrounding relation extraction processing method and processing apparatus therefor - Google Patents

Description

Description: TECHNICAL FIELD [0001] The present invention relates to a boundary surrounding relation extraction processing method for automatically extracting a boundary surrounding relation as a topological structure from a line drawing such as a map or a drawing, and a processing method therefor. The present invention relates to a processing device.

[Description of conventional technology]

Since it is efficient to perform automatic recognition processing and conversation processing on an image such as a map or drawing after converting it into vector data, it is necessary to perform a surrounding relation extraction processing on the boundary with the vector data. Already, the method using the boundary tracking (IEICE Spring National Convention 1988, D-239 and Japanese Patent Application No. 63-0)
No. 55692) has been proposed.

[Problems to be solved by the invention]

However, the conventional method has a problem that image processing is required to obtain an adjacent segment when vector data is created, and the method cannot be applied to vector data created interactively.

SUMMARY OF THE INVENTION It is an object of the present invention to solve the above problem and to extract the surrounding relation of a boundary using only vector data.

[Means for solving the problem]

Using boundary tracing on vector data, tracing boundaries one by one, extracting adjacent boundaries when tracing each boundary, and enclosing boundaries between boundaries based on the type of boundary to be tracked and the type of adjacent boundary Extract relationships. Specifically, the branch is arranged in the TV raster order by the coordinates of its starting feature point (when the feature points at both ends of the branch are arranged in the TV raster order, the one that comes before is called the start feature point and the one that comes after is called the end feature point). Branches with the same starting feature point are arranged counterclockwise from the left of the starting feature point according to the direction of the segment connected to the starting feature point, and the branches are examined in this order. Each time a branch B whose one direction is not tracked is extracted, the following procedures 1 to 5 are sequentially executed.

FIGS. 1, 2, and 3 are explanatory diagrams each illustrating the principle of the present invention. As shown in FIG. 1, feature points N1, N2, N3, N4, N
5, N6 are determined, and the segments S1, S2, S3, S4, S5, S6, S7 are determined, and (i) the branch B1 includes the segments S1 to S4, (i
i) It is assumed that branch B2 is segment S5, (iii) branch B3 is segment S6, and (iv) branch B4 is segment S7. Then, in the case of the present invention, as shown by the dotted lines in FIG. 2, the outer boundary OB1, OB2, OB3 and the hole boundary HB1 are obtained.
As shown in the right end of FIG. Is determined.

FIG. 3 (a) shows a case where the only segment adjacent to the starting feature point (x3, y3) is determined only by the distance d, and FIG. 3 (b) is determined only by taking the angle θ into account. It represents the case.

(Procedure 1) If both directions of the branch B have not been tracked, the tracking direction of the branch B is set to the direction from the start feature point to the end feature point, and the type of the boundary to be tracked is set to the outer boundary. If only one direction of the branch B is untracked, the untracked direction is defined as the tracking direction, and the type of the boundary to be tracked is defined as the hole boundary.

(Procedure 2) If the boundary type obtained in Procedure 1 is the outer peripheral boundary, it is adjacent to the left of the starting feature point (x3, y3) of the branch B using the distance d and the angle θ shown in FIG. Find a segment. That is, the end point of the segment is (x1, y
Assuming that 1) and (x2, y2), the segment having the minimum distance d among the segments satisfying all the following conditions is defined as an adjacent segment.

That is, condition 1) x1 ≦ x3 ≦ x2 and y4 <y3 (the condition that there is an intersection (x3, y4) with the horizontal half line extending to the left from the feature point) Condition 2) x1 ≠ x2 (the horizontal segment is In the case where there is obtained a segment which gives the minimum distance value among a plurality of segments as shown in FIG. 3 (a), but there is a plurality of the minimum segments as shown in FIG. 3 (b) The segment having the smallest angle θ is defined as an adjacent segment.

(Procedure 3) If the boundary type obtained in Procedure 1 is the outer boundary, the direction of the segment in which the starting feature point of branch B is to the right belongs to the two directions of the left adjacent segment obtained in Procedure 2. The boundary is an adjacent boundary, and if the boundary type obtained in the procedure 1 is a hole boundary, the boundary to which the tracked direction of the branch B belongs is set as the adjacent boundary.

(Procedure 4) Type of boundary C1 to be tracked and adjacent boundary
If the type of C2 is both the outer boundary or both the hole boundary, the boundary directly surrounding the boundary C2 (already determined) is the boundary C1
Is determined to directly surround the boundary C2, otherwise the boundary C2 is determined to directly surround the boundary C1.

(Procedure 5) Tracking is started from the direction H of the branch B to track one boundary.

Specific examples of the above (procedure 1) to (procedure 5) will be described later with reference to FIG.

〔Example〕

 FIG. 4 is a diagram for explaining an embodiment of the present invention.

In FIG. 4, 10 is a memory unit, 20 is a boundary type determining unit, 30 is a left adjacent segment extracting unit, 40 is an adjacent boundary determining unit, 5
0 is a surrounding relation determination unit, 60 is a boundary tracking unit, and 70 is a control unit.

The memory unit 10 stores vector data, boundary data, and the surrounding relationship of the boundary, and is supplied with vector data from outside (not shown in FIG. 4).

The boundary type determination unit 20 receives the branch number from the control unit 70, executes the above procedure 1 with reference to the vector data stored in the memory unit 10, and sends the tracking direction of the branch to the control unit 70. This is a part for outputting the boundary type to be tracked to the memory unit 10 and the control unit 70.

The left adjacent segment extraction unit 30 receives the branch number from the control unit 70, executes the above procedure 2 with reference to the vector data stored in the memory unit 10, and obtains the adjacent left side of the starting feature point of the branch. The number of the segment to be calculated is obtained and output to the control unit 70.

The adjacent boundary determination unit 40 receives the branch number and the adjacent segment number from the control unit 70, executes the above-described procedure 3 with reference to the vector data and the boundary data stored in the memory unit 10, and executes the boundary to be tracked from now on. This is a part that outputs the number of the boundary adjacent to the control unit 70 to the control unit 70.

The surrounding relation determination unit 50 is given the number of the boundary to be tracked and the number of the adjacent boundary by the control unit 70, executes the above-described procedure 4, and stores the number of the boundary directly surrounding the boundary to be tracked from now on in the memory. This is a part to be output to the unit 10.

The boundary tracking unit 60 receives the boundary number, the branch number, and the branch tracking direction from the control unit 70, tracks one boundary from the direction of the branch using vector data stored in the memory unit 10, and The number and the directed branch number sequence at the boundary are output to the memory unit 10. The method of boundary tracing on vector data has already been described (see
No. 61-106285, IPSJ 33rd National Convention Lecture No. 4N
-3) is used.

The control unit 70 arranges the branches of the vector data stored in the memory unit 10 in the order of the TV raster according to the coordinates of the starting feature point, and the branches having the same starting feature point are determined by the direction of the segment connected to the starting feature point. The branches are arranged in a counterclockwise order from the left of the starting feature points, and the branches are checked in this order to extract a branch in which at least one of the branch tracking directions is untracked. Then, it is a part that controls the memory unit 10 or the boundary tracking unit 60 so that the surrounding relation of the boundary is extracted for the obtained branch.

FIG. 5 illustrates the operation of the embodiment shown in FIG. 4 using the vector data shown in FIG. 1 as an example.

First, the control unit 70 initially sets the boundary number to 1, and checks branches in the order of B1, B2, B3, and B4. When examining the branch B1, since both directions of B1 are not tracked, the branch number B
1 and the boundary number 1 are passed to the boundary type determination unit 20 for operation.

Next, in the initial state, for example, since the two directions of the branch B1 are not tracked at the feature point N1,
The boundary type is the outer boundary, and the tracking direction is the direction from the start feature point to the end feature point. Then, the information is sent to the control unit.
Output to 70. Further, information that the boundary of boundary number 1 is the outer boundary is written in the memory unit 10. In the case of the branch B1, since the start feature point and the end feature point are the same, the tracking direction is ambiguous. In such a case, the direction of the segment connected to the starting feature point is checked in the counterclockwise order from the left of the starting feature point, and the direction from the first detected segment S1 and returning to segment S4 is determined from the starting feature point. The direction of the end feature point.

Next, the control unit 70 receives the information that the boundary to be tracked is the outer boundary from the boundary type determination unit 20, and thus gives the left adjacent segment extraction unit 30 the branch number B1 to operate.

Next, the left adjacent segment extraction unit 30 outputs to the control unit 70 that there is no left adjacent segment.

Next, the control unit 70 informs the adjacent boundary determination unit 40 that the outer boundary and the left adjacent segment do not exist as the boundary type, and operates the adjacent boundary determination unit 40.

Next, the adjacent boundary determining unit 40 returns the edge of the image to the control unit 70 as the adjacent boundary. The edge of the image is a virtual boundary surrounding all the boundaries, and is a root when the surrounding relation is represented by a tree structure. The boundary type at the edge of the image is a hole boundary.

Next, the control unit 70 passes the information indicating that the boundary number, 1 and the adjacent boundary are the edges of the image to the surrounding relation determination unit 50 and causes the operation to be performed.

Next, the surrounding relation determination unit 50 refers to the boundary type stored in the memory unit 10 and stores in the memory unit 10 information that the boundary directly surrounding the boundary of boundary number 1 is an image edge. That is, an enclosing relationship of “image edge—boundary 1” as shown on the right side of FIG. 5A was extracted.

Next, the control unit 70 operates the boundary tracking unit 60 by giving the boundary number 1, the branch number B1, and the direction from the start feature point to the end feature point as the tracking direction thereof.

Next, the boundary tracking unit 60 stores, in the memory unit 10, the branch B1 in the direction from the start feature point to the end feature point as a directed branch sequence forming the boundary of the boundary number 1. That is, the fifth
A boundary 1 indicated by a broken line in FIG.

Next, the control unit 70 sets the boundary number to 2, and checks the direction from the end feature point to the start feature point of the branch B1. Since this direction has not been tracked, the branch number B1 and the boundary number 2 are passed to the boundary type determination unit 20 for operation.

Next, the boundary type determination unit 20 determines that the boundary type is a hole boundary,
The tracking direction is a direction from the end feature point to the start feature point.
Then, the information is output to the control unit 70. Further, information that the boundary of the boundary number 2 is a hole boundary is written in the memory unit 10.

Next, the control unit 70 passes the hole boundary and the branch number B1 as the boundary type to the adjacent boundary determining unit 40 and causes the adjacent boundary determining unit 40 to operate.

Next, the adjacent boundary determining unit 40 returns the boundary 1 to the control unit 70 as the adjacent boundary.

Next, the control unit 70 passes the boundary number 2 and the adjacent boundary number 1 to the surrounding relation determination unit 50 to operate.

Next, the surrounding relation determination unit 50 refers to the boundary type stored in the memory unit 10 and accumulates information in the memory unit 10 that the boundary directly surrounding the boundary of the boundary number 2 is the boundary 1. That is, the surrounding relation as shown on the right side of FIG. 5 (b) was extracted.

Next, the control unit 70 operates the boundary tracking unit 60 by giving the boundary number 2, the branch number B1, and the direction from the end feature point to the start feature point as the tracking direction thereof.

Next, the boundary tracking unit 60 stores in the memory unit 10 the branch B1 in the direction from the end feature point to the start feature point as a directed branch sequence forming the boundary of the boundary number 2. That is, the boundary 2 indicated by the broken line in FIG. 5 (b) was extracted.

Next, the control unit 70 sets the boundary number to 3, and when examining the branch B2, since both directions of B2 have not been tracked, the control unit 70 passes the branch number B2 and the boundary number 3 to the boundary type determination unit 20. Make it work.

Next, the boundary type determination unit 20 sets the boundary type as the outer peripheral boundary and the tracking direction as the direction from the start feature point to the end feature point, since both directions of the branch B2 have not been tracked. Then, the information is output to the control unit 70. Further, information that the boundary of the boundary number 3 is the outer peripheral boundary is written in the memory unit 10.

Next, the control unit 70 receives the information that the boundary to be tracked is the outer peripheral boundary from the boundary type determination unit 20, and thus gives the left adjacent segment extraction unit 30 the branch number B2 to operate.

Next, the left adjacent segment extraction unit 30 outputs the left adjacent segment number S3 to the control unit 70.

Next, the control unit 70 passes the outer boundary and the left end adjacent segment number S3 as the boundary type to the adjacent boundary determining unit 40, and operates the adjacent boundary determining unit 40.

Next, the adjacent boundary determining unit 40 returns 1 to the control unit 70 as the adjacent boundary number.

Next, the control unit 70 passes the boundary number 3 and the adjacent boundary number 1 to the surrounding relation determination unit 50 to operate.

Next, the surrounding relation determining unit 50 refers to the boundary type stored in the memory unit 10 and accumulates in the memory unit 10 information that the boundary directly surrounding the boundary of the boundary number 3 is an image edge. That is, the surrounding relation as shown on the right side of FIG. 5 (c) was extracted.

Next, the control unit 70 gives the boundary tracking unit 60 the boundary number 3, the branch number B2, and the direction from the start feature point to the end feature point as its tracking direction, and operates the boundary tracking unit 60.

Next, the boundary tracking unit 60 calculates B2 in the direction from the start feature point to the end feature point, B2 in the direction from the end feature point to the start feature point, B3 in the direction from the start feature point to the end feature point, and the end feature. B3 in the direction from the point to the starting feature point is stored in the memory unit 10 as a directed branch sequence forming the boundary of boundary number 3. That is, the boundary 3 indicated by the broken line in FIG. 5 (c) was extracted.

When the processing is performed in the same manner, the result shown in FIG. 5D is obtained.

Note that the method described in the present invention uses a TV raster (that is, processing proceeds line by line from the upper left to the lower right) as a method for examining branches. However, a method using other rasters can be easily obtained from this method. Can be derived.

〔The invention's effect〕

As described above, according to the present invention, the surrounding relation of the boundary can be extracted using only the vector data. Therefore,
Since image processing is not required unlike the conventional method, the processing time can be reduced. There is an effect that it can be applied to vector data created interactively.

[Brief description of the drawings]

1 to 3 are diagrams for explaining the principle of the present invention. FIG. 1 is a diagram for explaining vector data, FIG. 2 is a diagram for explaining the surrounding relation of a boundary, and FIG. FIG. FIG. 4 is a diagram for explaining an embodiment of the present invention, and FIG. 5 is a diagram for explaining the operation of the embodiment. 10 memory unit, 20 boundary type determination unit, 30 left adjacent segment extraction unit, 40 adjacent boundary determination unit, 50 surrounding relation determination unit, 60 boundary tracking unit, 70 control Department.

Claims (2)

(57) [Claims] A control unit, a boundary type determining unit, a left adjacent segment extracting unit, an adjacent boundary determining unit, an enclosing relationship determining unit, and a boundary tracking unit; A method of accumulating vector data including a branch that is a series of line segments to be connected and a segment that is a line segment forming the branch, and extracting an enclosing relationship of a boundary from the vector data, wherein (A) the control unit A first step of arranging the branches in TV raster order according to the coordinates of their starting feature points, examining the branches in this order, and extracting a branch B in which at least one of the tracing directions of the branch is untracked. (B) In the boundary type determination unit, the branch B
If both directions are not tracked, the type of the boundary C1 to be tracked is set as the outer circumferential boundary, the tracking direction of the branch B is set as the direction from the start feature point to the end feature point, and if only one direction of the branch B is untracked, A second process in which the type of the boundary C1 to be tracked from now on is a hole boundary, and the tracking direction of the branch B is an untracked direction; and (C) in the left adjacent segment extraction unit, the boundary
If the type of C1 is an outer peripheral boundary, a left adjacent segment that extracts a left adjacent segment from the segments excluding the horizontal segments with respect to the starting feature point of the branch obtained in the first process is extracted. And (D) in the adjacent boundary determining unit, if the type of the boundary C1 is an outer boundary,
The boundary to which the direction in which the starting feature point of the branch B is viewed to the right belongs to the adjacent boundary C2. If the type of the boundary C1 is a hole boundary, the boundary to which the tracked direction of the branch B belongs is defined. A fourth step of setting the adjacent boundary C2; and (E) the enclosing relation determining unit directly surrounds the boundary C2 if the type of the boundary C1 and the type of the adjacent boundary C2 are both an outer boundary or a hole boundary. A fifth step of determining that the boundary directly encloses the boundary C1; otherwise, determining that the boundary C2 directly encloses the boundary C1; and (F) in the boundary tracking section, the second step of dividing the branch B into the second step. A sixth process of tracing a single boundary C1 by tracing in the direction obtained in (1). 2. A control unit, a boundary type determining unit, a left adjacent segment extracting unit, an adjacent boundary determining unit, an enclosing relationship determining unit, and a boundary tracking unit, wherein a feature point and two feature points are determined. A boundary surrounding relation extraction processing apparatus for storing vector data including a branch as a series of connecting line segments and a segment as a line segment forming the branch, and extracting a surrounding relation of the boundary from the vector data. (A) The control unit arranges the branches in TV raster order according to the coordinates of the starting feature point, examines the branches in this order, and determines a branch B in which at least one of the tracking directions of the branches is untracked. (B) if both directions of the branch B are not tracked, the boundary type determination unit sets the type of the boundary C1 to be tracked from now on as the outer boundary, If the tracking direction is the direction from the start feature point to the end feature point, and only one direction of the branch B is untracked, the type of the boundary C1 to be tracked from now on is the hole boundary, and the tracking direction of the branch B is untracked. (C) the left adjacent segment extraction unit is horizontal with respect to the starting feature point of the branch obtained in the first process if the type of the boundary C1 is an outer boundary. (D) the adjacent boundary determining unit is configured to extract the left adjacent segment from the segment excluding the segment if the type of the boundary C1 is an outer boundary. If the type of the boundary C1 is a hole boundary, the boundary to which the direction in which the starting feature point of the branch B looks to the right of the two directions belongs is defined as the adjacent boundary C2. (E) the surrounding relation determination unit determines that the type of the boundary C1 and the type of the adjacent boundary C2 are both an outer boundary or a hole boundary, The boundary directly surrounding the boundary C2 is also configured to directly surround the boundary C1; otherwise, the boundary C2 is determined to directly surround the boundary C1. (F) The boundary tracking unit sets the branch B to A boundary surrounding extraction processing apparatus characterized by being configured to track one boundary C1 by tracking in the direction obtained in the second step.