JP2552653B2 - Superposed figure separation method - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a method of separating overlapping figures in a line drawing such as a map or a drawing.

(Prior Art) When a line drawing composed of line segments such as a map or a drawing is input as an image into a computer, the line drawing subject to image processing is, for example, a line drawing representing a road or a line drawing representing a house. There is a case in which they are not distinguished from each other, and they are mixed, or parts of different types of line figures remain overlapped with each other. Since such line figures cannot be used as a map or a database of figures, for example, only line figures representing roads or only line figures representing houses can be selected from the input line figures. , It becomes necessary to separate and extract each of them in units of line figures. Therefore, among the input line figures, the line figure that surrounds the background area is called a loop figure. If the part that constitutes this loop figure is also the part that constitutes another loop figure, Since the loop figures are superposed on each other, it is necessary to perform a process of separating and extracting the superposed constituent parts. As a conventional method of extracting a loop figure and extracting only the part where the figure and other figures overlap, a straight line from a line segment that is not on the loop figure to a line segment that is not on the loop figure is extracted. There is a method of extracting and making a portion on the straight line and on the loop graphic a superposed portion (31st National Convention of Information Processing Society of Japan, 6N-1).

However, as shown in FIG. 1, when the monotonous polygonal line and the loop figure are superposed, there is a problem that the superposed section cannot be extracted because the superposed section is not on the straight line connecting the line segments that are not on the loop figure.

In FIG. 1, FIG. 1 (a) is an input graphic, and FIG. 1 (b) is the extraction result of a graphic other than the loop graphic by the conventional method.

In the figure, 1 is a figure other than the loop figure and is represented by a thin line,
Reference numeral 2 denotes a superimposing portion of a loop graphic and other graphics, which is represented by a thick line, and 3 is a branch point, which is represented by a black circle.

A part of P _1, P ₂ of the branching point 3, ... represent a P _6, representing the part of the line segment L _1, L _2, ..., and L _12.

The superposition shown in FIG. 1 occurs between a line graphic representing a building and a line graphic representing a road in the map.

That is, one loop figure represents one building,
When the buildings are grouped together to form a block, the overlapping portion represents one side of the road.

The conventional method has a problem in that it is not possible to extract the above-mentioned overlapping portion because there are only line segments L ₁ and L _{9 that} are not on the loop figure and there is no straight line that connects them.

(Object of the Invention) In order to solve the drawbacks of the conventional method, the present invention extracts one loop figure at a time and passes from the line segment other than the one loop figure of interest to the loop figure of interest. A monotonous polygonal line that extends to a line segment other than the one loop figure of interest is extracted, and the portion on the polygonal line on the loop figure of interest is made to be a superimposed portion with another figure.

(Structure and Action of the Invention) FIG. 2 is a diagram for explaining the superimposed figure separating method of the present invention.

In FIG. 2, FIG. 2 (a) is an input figure
It is the same as FIG.

FIG. 2 (b) shows the extraction result according to the present invention of figures other than loop figures.

 In the present invention, first, one loop figure is extracted.

The specific procedure of this extraction method is described in the reference “Japanese Patent Application No. 61-5050” for both image data and vector data.
Since it is described in detail in "No. 9," it is omitted.

For example, a loop shape _{L 4 · L 8 · L 12} · L 7 is extracted.

Second, a branch point located on the loop shape _{L 4 · L 8 · L 12} · L 7 ( the branch point is a point that a line segment connecting the three or more.)
Among these, points P ₃ and P ₆ having points on other figures other than the loop figure near the branch point are extracted. When the point A and the point B are adjacent to each other, the point A has the point B in the vicinity, or the point A has the neighbor point B.

Thirdly, a pair (P ₃ , P ₆ ) of adjacent branch points in the loop figure of interest is extracted from these branch points.

Fourth, branch points P ₃ and P ₆ extracted in the second process
The line segments L ₃ and L _{11 that} are connected to the loop pattern L and are located in a figure other than the loop figure L ₄ , L ₈ , L _12, and L _{7 of} interest are extracted.

Fifth, the following processing is performed on each of the branch point pairs extracted in the third step. If there is a monotonous polygonal line among the polygonal lines from the line segment connected to one branch point to the line segment connected between the pair of branch points and the line segment connected to the other branch point, The loop figure portion on the monotonous polygonal line is the portion where other figures overlap.

Here, the monotonous polygonal line means that at all branch points on the polygonal line, the angle formed by the line segment entering the branch point and the line segment emerging therefrom is given in advance by θ (for example, 5
Within ゜).

With respect to the target loop shape _{L 4 · L 8 · L 12} · L 7, firstly, select the branch point pair _{(P 3, P 6),} 2 single fold line L ₃ · L ₄ · L ₈
・ Check if there are monotonous polygonal lines in L ₁₂ , L ₁₁ , and L ₃ , L ₇ , L ₁₁ .

_{L 3 · L 4 · L 8} · L 12 · L 11 is the angle between the two line segments L ₃ and L ₄ at the branch point P _3, the branch point two line segments L ₁₂ in P ₆
Since both the angles of L ₁₁ and L ₁₁ are within θ, it is determined as a monotonous polygonal line.

The angle between the line segments L ₄ and L ₈ and the angle between the line segments L ₈ and L ₁₂ are not within θ, but the point between the line segments L ₄ and L ₈ is not a branch point but the line segment L ₈ The points between and L ₁₂ are also not bifurcations, so their angles do not matter. Therefore, the polygonal lines L ₃ , L ₄ , L ₈
· L ₁₂ · L ₁₁ is determined monotonic polygonal line.

The curves L ₃ , L ₇ and L ₁₁ are the two line segments L _{3 at the} branch point P ₃ .
And the angle between L ₇ and the two line segments L ₇ and L _{11 at the} junction P ₆ .
Since the angle between and is not within θ, it is determined to be a non-monotonic curve.

Therefore, the line segment L ₄ , L ₈ , L ₁₂ , which is the common part of the monotonous polygonal line L ₃ , L ₄ , L ₈ , L ₁₂ , L ₁₁ and the loop figure L ₄ , L ₈ , L ₁₂ , L _7.
Is the overlapping portion.

Next, similar processing is performed on the remaining pairs of branch points. Since with respect to the target loop shape _{L 4 · L 8 · L 12} · L 7 (P 3, P 6) is no other than the branch point pairs, it ends the fifth process. next,
L ₃ , L ₇ , L _11, and L ₆ are extracted as the loop figure of interest.
As the pair of branch points of this loop of interest, the pair (P ₂ , P ₃ ), (P ₃ ,
_{P 6), (P 6,} P 5), (P 5, P 2) is extracted. Pair (P ₂ ,
The polygonal lines L ₂ , L ₃ and L ₄ are extracted for P ₃ ), and the line segment L ₂ and
Since the angle with L ₃ and the angle with the line segments L ₃ and L ₄ are both within θ, the polygonal lines L ₂ , L _3, and L ₄ are determined to be monotonous polygonal lines. The polygonal lines L ₄ , L ₇ , and L ₁₂ are extracted for the pair (P ₃ , P ₆ ), and the angle between the line segments L ₄ and L ₇ is not within θ.
It is determined that L ₄ , L ₇ , and L ₁₂ are not monotonic polygonal lines. Pair (P
₆ and P ₅ ), the polygonal lines L ₁₂ , L _11, and L ₁₀ are extracted, and the angle between the line segments L ₁₂ and L ₁₁ and the angle between the line segments L ₁₁ and L ₁₀ are both within θ. The polygonal lines L ₁₂ , L ₁₁ and L ₁₀ are determined as monotonous polygonal lines. For the pair (P ₅ , P ₂ ), the polygonal line is L ₁₀
Since L ₆ and L ₂ are extracted and the angle between the line segments L ₁₀ and L ₆ is not within θ, it is determined that the polygonal line L ₁₀ L ₆ and L ₂ is not a monotonous polygonal line. Therefore, the line segment L ₃ which is the common part of the loop figure L ₃ , L ₇ , L ₁₁ , L ₆ and the monotonous polygonal line L ₂ , L ₃ , L ₄ and the loop figure L ₃ , L ₇ , L ₁₁ , L ₆ and monotonous polygonal line L ₁₂ , L ₁₁ , L ₁₀
The line segment L ₁₁ that is a common part of the and is extracted as the overlapping part. Similarly, the loop figures are extracted one by one and the above procedure is repeatedly applied.

As a result, as shown in FIG. 2, the present invention solves the problem of the conventional method shown in FIG.

FIG. 3 is a diagram illustrating an example in which the present invention is applied to image data.

In FIG. 3, 4 is an image memory unit, 5 is a thinning unit,
Reference numeral 6 is a superimposed image figure separation unit, and 7 is a control unit.

The image memory section 4 is a section for accumulating maps, drawings and the like as digital images, and digital images are supplied from the outside not shown in FIG.

The thinning unit 5 converts a line figure included in the digital image stored in the image memory unit 4 into a center line having a width of 1 pixel, sets the value of the pixel on the center line to 1, and the value of other pixels. The thinned image in which is converted to 0 is stored in the image memory unit 4.

Regarding the thinning method, some methods are known (IEICE, Technical Research Report, PRL75-66, etc.),
Any of them may be used.

The superposed image figure separation unit 6 extracts a loop figure from the thinned image stored in the image memory unit 4, extracts a portion where the loop figure is superposed on another figure, and is on the loop figure, Further, the portion not superposed on other figures is converted into pixels of value 2 on the thinned image accumulated in the image memory unit 4.

The control unit 7 is a unit that controls the whole so that when the digital image is input to the image memory unit 4, the thinning unit 5 is operated and then the superimposed image figure separation unit 6 is operated.

FIG. 4 is a diagram for further explaining the superimposed image figure separation unit 6 which is a component of FIG.

This superposed image figure separation unit 6 is the first embodiment of the present invention.

In FIG. 4, 61 is a loop graphic extraction unit, 62 is a loop graphic memory unit, 63 is a branch point pair extraction unit, 64 is a line segment extraction unit,
Reference numeral 65 is a monotonous broken line axis alignment portion, and 66 is a control portion.

The loop graphic extraction unit 61 extracts one loop graphic from the thinned image stored in the image memory unit 4 one by one as a dot sequence (that is, a coordinate sequence of pixels), and the loop graphic memory unit 61
Store in 62 (first process).

The loop graphic memory unit 62 stores each loop graphic as a point sequence.

The branch point pair extraction unit 63 inputs a sequence of points forming one loop graphic from the loop graphic memory unit 62, and is located on a graphic other than the loop graphic in the thinned image accumulated in the image memory unit 4. A branch point having a neighboring point (neighboring pixel) is extracted (second process). From these branch points, a pair of branch points adjacent to each other on the loop figure of interest is extracted.
(Third Process) The line segment extraction unit 64 inputs the point sequence forming one loop figure and the branch point pair from the branch point pair extraction unit 63, connects them to the input branch point, and Extract line segments on figures other than loop figures. (Fourth step) Specifically, the points on the figures other than the loop figure of interest are tracked one by one from the branch point, and when the tracked point sequence cannot be approximated to a straight line, the tracking is stopped. , The obtained point sequence is taken as one line segment.

There are several known methods for checking whether a sequence of points can be approximated to a straight line.
1252), but any of them may be used.

The monotonic polygonal line extraction unit 65 inputs from the line segment extraction unit 64 a point sequence forming one loop figure, a branch point pair, and a line segment connected to the branch point, and performs the following processing. (Fifth Step) First, the point sequence forming the loop figure is linearly approximated and converted into a line segment sequence. However, it is always divided into line segments at branch points.

Next, for each of the branch point pairs, a monotonous curve is drawn in the polygonal line from the line segment connecting one branch point to the line segment connecting the other branch point. If there is, a line segment sequence between the pair of branch points is set as a portion on which another figure is overlapped, and a portion on the loop figure and not overlapped with another figure is stored in the image memory unit 4. It is converted into a pixel having a value of 2 on the thinned image.

The control unit 66 includes a loop graphic extraction unit 61 and a branch point pair extraction unit 6
This is a part for controlling the monotone polygonal line extraction unit 65 from the loop graphic extraction unit 61 so that the line segment extraction unit 64 and the monotone polygonal line extraction unit 65 operate in this order.

FIG. 5 is a diagram for explaining an example in which the present invention is applied to vector data.

In FIG. 5, the image memory unit 4 and the thinning unit 5 are the third
It is the same as the one in the figure. Reference numeral 8 is a vectorization unit, 9 is a vector memory unit, 10 is a superposition vector figure separation unit, and 11 is a control unit.

The vectorization unit 8 extracts the branch points and end points of the thinned image stored in the image memory unit 4, linearly approximates the point sequence between these two points, and divides into a line segment sequence. And the coordinates of the end points and the coordinates of the pixels at both ends of the line segment are stored in the vector memory unit 9.

Several methods are known as the method of linear approximation (the National Conference of the Institute of Electronics, Information and Communication, Japan, 1252, etc. in 1984), but any of them may be used.

The vector memory unit 9 is a unit that stores the vector data output from the vectorization unit 8.

The superposed vector graphic separation unit 10 extracts a loop graphic from the vector data accumulated in the vector memory unit 9, extracts a portion where the loop graphic is superposed with another graphic, and is on the loop graphic, and This is a part for storing a line segment which is not superposed on other figures in the vector memory unit 9.

A second embodiment of the present invention, a superposition vector figure separation unit
The detailed configuration of 10 is basically the same as the configuration of the superimposed image figure separation unit shown in FIG. However, since the vectorized data is used instead of the thinned image, the function of each component is as follows.

The loop graphic extraction unit 61 extracts one loop graphic from the vector data accumulated in the vector memory unit 9 as a line segment sequence, and stores the line segment sequence in the loop graphic memory unit 62.

The loop graphic memory unit 62 stores each loop graphic as a line segment sequence.

The branch point pair extraction unit 63 inputs a line segment sequence forming one loop graphic from the loop graphic extraction unit 61, and exists in a graphic other than the loop graphic in the vector data accumulated in the vector memory unit 9. The branch points to which the line segments are connected are extracted, and from these branch points, the pair of branch points adjacent to each other on the loop figure of interest are extracted.

The line segment extraction unit 64 inputs the line segment sequence forming one loop figure and the branch point pair from the branch point pair extraction unit 63, connects the input branch point, and draws a figure other than the loop figure of interest. Extract the line segment above.

The monotonic polygonal line extraction unit 65 inputs the line segment sequence forming one loop figure, the branch point pair, and the line segment connected to the branch point from the line segment extraction unit 64, and outputs one for each branch point pair. If there is a monotonous polygonal line in the curve from the line segment connected to the branch point to the line segment between the branch point pair and the line segment connected to the other branch point, between the branch point pairs The line segment string of a portion which is on the loop graphic and is not superimposed on another graphic is output to the vector memory unit 9 as a part where a certain line segment is overlapped with another graphic.

The control unit 11 is a unit that controls the whole so that when the digital image is input to the image memory unit 4, the thinning unit 5, the vectorization unit 8, and the superposition vector figure separation unit 10 are operated in this order.

The loop graphic may be logically determined as one loop graphic even if it is not closed due to faintness or break.

(Effects of the Invention) As described above, the present invention can extract a portion where a loop figure and another figure overlap, including a portion that is not on a straight line connecting line segments that are not on the loop figure. The effect of less omission of extraction is obtained.

[Brief description of drawings]

FIG. 1 is a diagram showing a drawback of the conventional method of separating superposed figures,
FIG. 2 is a diagram for explaining the superimposed figure separating method of the present invention, and FIG.
FIG. 4 is a diagram illustrating an example in which the present invention is applied to image data, FIG. 4 is a diagram illustrating an embodiment of the present invention, and FIG.
The figure is a diagram for explaining an example in which the present invention is applied to vector data. 1 ... Figures other than loop figures, 2 ... Superposed section of loop figures and other figures, 3 ... Branch points, 4 ... Image memory section, 5 ... Thinning section, 6 ... Superposed image figure separation section , 7 ... control unit, 8 ... vectorization unit, 9 ... vector memory unit, 10 ... superposed vector graphic separation unit, 11 ... control unit, 61 ... loop graphic extraction unit, 62 ... loop graphic memory 63 ... Branch point pair extraction unit, 64 ... Line segment extraction unit, 65 ... Monotone broken line extraction unit, 66 ... Control unit.

Claims (1)

(57) [Claims] 1. A map or figure is input to a computer as image data or vector data, a loop figure surrounding one background area is extracted from the figure data stored in a memory in the computer, and the loop figure A method of separating and extracting the superimposed constituent parts when the constituent parts are also constituent parts of figures other than the loop figure, that is, when the figure overlaps, and a loop figure is extracted from the image data or vector data. A first step of extracting, a second step of extracting from the image data or the vector data forming the loop figure, a point having a point on the figure other than the loop figure in the vicinity as a branch point; The third step of extracting adjacent branch point pairs from the plurality of branch points obtained by the second step, and the second step Connected to the obtained branch point, and
A fourth step of obtaining a line segment on a figure other than the loop figure by linear approximation from the image data or vector data, and a loop figure obtained in the first step by the third step A straight line approximation is performed on the basis of the pair of branch points to convert into a sequence of line segments, and for each pair of branch points, between the line segment obtained by the fourth process and the branch point pair connected to one branch point of the pair of branch points. It is checked whether or not there is a monotonous polygonal line among the polygonal lines that pass through the line segment on the loop figure and are connected to the other branch point of the pair of branch points to the line segment obtained by the fourth step. If there is a monotonous polygonal line, on the attention loop figure,
And a fifth step of forming a line segment sequence on a monotonous polygonal line as a constituent portion for superposing on a figure other than a loop figure.