JPH0778829B2 - Figure extraction method - Google Patents

Description

Detailed Description of the Invention

TECHNICAL FIELD The present invention relates to a method for automatically extracting a figure composed of a smooth curve (hereinafter referred to as a monotone curve) from a line drawing such as a map or a drawing. (Prior Art) Conventionally, an image that is input to a computer as a map or a drawing is used to generate a figure (for example, a map road,
The method of extracting contour lines, connections of circuit diagrams) is mainly a method of extracting straight lines, and an effective method has not been established for drawings composed of free-form curves of arbitrary shapes such as maps. (Object of the Invention) An object of the present invention is to extract a non-linear monotone curve from a center line obtained by thinning a digital image input to a computer, by tracing the line. In order to achieve such an object, according to the present invention, (a) when the number of neighboring points to be processed reaches one from a non-branch point of the center line, the tracking is stopped. (B) When reaching the branch point of the center line, if there is a smooth direction with respect to the already tracked portion, continue the tracking in the smooth direction, otherwise stop the tracking; and (c) If there is a tracked point whose x-coordinate is equal to the x-coordinate of the tracking start point, and there is one among the tracked points whose y-coordinate is equal to the y-coordinate of the tracking start point, then trace it. Stopping, and (d) if no traced point has an x coordinate equal to the x coordinate of the trace start point, and the traced line has a length in the x direction that is greater than or equal to a threshold. Stopping the tracking, and (e) in the tracked points, the y coordinate is the starting point of the tracking. If there is nothing equal to the coordinates and the traced line has a length equal to or greater than the threshold value in the y direction, the point on the center line is traced using the tracking rule to stop the tracking, and the tracking rule (d) or The line obtained by stopping the tracking in (e) is determined to be a part of the monotone curve, and the points on the center line are further traced from both ends using only (a) and (b) of the tracking rule. , The obtained line is one monotone curve. Further, according to the present invention, when one monotone curve is executed for one image as a whole, the line widths of lines are measured in advance and pixels or vectors are classified according to a plurality of line width ranges given from the outside. First, only the pixels or vectors belonging to the thickest range of the line width are extracted as the extraction targets, and then the pixels or vectors belonging to the two line width ranges from the thicker one are extracted as the extraction targets. Similarly, by expanding the line width range one by one and extracting the monotone curve, it becomes easy to classify the monotone curve in detail. (Structure and Operation of the Invention) FIG. 1 is a diagram for explaining the principle of the present invention, showing a control procedure for executing extraction of one monotone curve from image data over one image. It is an example to explain. The image data is sampled on an orthogonal grid, and the pixel coordinates are represented by row numbers and column numbers. That is, the upper left pixel is (1,1), and the horizontal direction is represented by the column number, and the vertical direction is represented by the row number. In Fig. 1, the line width is 0.4mm or more, less than 0.4mm 0.3mm or more, less than 0.3mm 0.2mm or more, less than 0.2mm 0.1mm or more, 0.1mm
The line width W of the pixel to be extracted is divided into five ranges, which are less than 0.4 mm, 0.4 mm or more, 0.3 mm or more, 0.2 mm or more, 0.1 mm or more, and all line widths, and raster scanning is performed for each. To extract a monotone curve. In one raster scan for pixels having a line width W or more,
The starting point (i, j) of the monotone curve tracing is detected, and one monotone curve is extracted from the starting point by tracing processing. Here, when extracting a monotone curve composed of pixels having a line width of W or more, among the pixels having a line width value exceeding that value, those which have already been investigated for forming a monotone curve are It will not be the starting point of the monotone curve again as it has been completed. This ensures that already tracked pixels are not the starting point for tracking. This method facilitates the recognition of figures, since various figures are represented by different line widths in maps and drawings. FIG. 2 is a diagram for explaining the system principle of the present invention, and is a diagram for explaining a control procedure when executing extraction of one monotone curve for the entire image data of one image, where 1 is a background and 2 is a background. Is the center line of the line figure. The extraction of one monotone curve in the present invention is realized by executing the following three procedures using the tracking rule shown in FIG. A pixel on the background is a 0-pixel having a value of 0, and a pixel on the center line of the line figure is a 1-pixel having a value of 1. Further, a 1-pixel in which the number of 1-pixels in the vicinity is 3 or more is called a branch point.

[Procedure 1] A pixel (i, j) that is not a branch point is traced according to the following tracking rules (a) to (e), and a pixel that belongs to a line having a line width of W or more and is not extracted as a monotone curve is traced. . (A) As shown in FIG. 2 (a), when the number of neighboring pixels to be extracted reaches ₁ (i _l , j _l ), the process ends. (B) As shown in FIG. 2 (b), when the pixel (i _l , j _l ) which is the branch point is reached, a smooth direction is selected. If there is no smooth direction, the process ends. Assuming that a branch point having three or more branches has been reached, the smooth direction is specifically selected as follows (details will be described with reference to FIG. 5). A branch point pixel (i _l, j _l) pixels tracked before by a certain number of T from (i _lT, j _lT) and, can be traced pixel (i _l, j _l) than after the same number T N pixels (p ₁ ,
q ₁ ), ..., (p _N , q _N ) are extracted. However, N is generally smaller than the number of branches because only pixels having a line width of W or more are traced. Further branching may occur in the process of extracting pixels (p ₁ , q ₁ ), ..., (p _N , q _N ). At that time, the pixel (i _lT , j
_The pixel (p ₁ , q ₁ ), ..., (P _N , q _N ) is extracted by selecting the direction that is closest to the vector direction from _lT ) to the pixel (i _l , j _l ). Next, from pixel (i _lT , j _lT ) to pixel (i _l ,
vector to j _l ) and pixel (i _l , j _l ) to pixel (p ₁ ,
q ₁ ), ..., (p _N , q _N ) Then, the vector closest to 0 ° below α ° is selected. However, U ₁ = i _l −i _lT , U ₂ = p _r −i _l , V ₁ = j _l −j
_lT , V ₂ = q _r −j _l (1 ≦ r ≦ N). α is a threshold value for a given angle. If a vector from pixel (i _l , j _l ) to pixel (p _r , q _r ) is chosen, the next pixel (i _l , j _l ) is tracked so that pixel (p _r , q _r ) is tracked. Determine the tracking point for. (C) As shown in FIG. 2 (c), the line coordinates are (excluding (i, j)) in the tracking points from (i, j) to the tracking point of interest (i _l , j _l ). If there is one that is equal to the row coordinate i of the starting point and one whose column coordinate is equal to the column coordinate j of the starting point, the process ends at (i _l , j _l ). (D) As shown in FIG. 2 (d), the column coordinates are [excluding (i, j)] in the tracking points from (i, j) to the tracking point (i _l , j _l ) of interest. If there is nothing equal to the column coordinate j of the starting point, and if the traced line has a length equal to or greater than the threshold value in the column direction, the procedure 1 is terminated at (i _l , j _l ). (E) As shown in FIG. 2 (e), the line coordinates are (excluding (i, j)) in the tracking points from (i, j) to the target tracking point (i _l , j _l ). If there is nothing equal to the row coordinate i of the starting point and the traced line has a length equal to or greater than the threshold value in the row direction, the procedure 1 is terminated at (i _l , j _l ).

[Procedure 2] Procedures 2 and 3 are executed only when the tracking rule (d) or (e) is satisfied in the procedure 1. The tracking rules (a) and (b) of the above procedure 1 are calculated from the pixel lastly traced by the procedure 1.
Thus, pixels that belong to a line having a line width of w or more and are not extracted as a monotone curve are traced.

[Procedure 3] From the pixel which is in the vicinity of the tracking start pixel (i, j) and is different from the pixel tracked next to (i, j) in the procedure 1, according to the above tracking rules (a) and (b), W Belongs to a line with the above line width,
In addition, pixels that have not been extracted are tracked as a monotone curve. The sequence of points obtained by proceeding from steps 1 to 3 is used as one monotone curve. That is, in the present invention, a curve that satisfies the tracking rule (d) or (e) is a monotone curve. FIG. 3 is a block diagram showing the configuration of an embodiment of the present invention. In FIG. 3, 3 is an image input unit, 4 is an image memory unit,
5 is a thinning section, 6 is a line width measuring section, 7 is a monotone curve extracting section,
Reference numeral 8 is a point sequence memory unit, 9 is an image output unit, and 10 is a control unit. The image input unit 3 is a unit for sampling and quantizing an image with a facsimile, a drum scanner, a TV camera, etc., converting it into a digital image, and inputting it. The image memory unit 4 is a unit that stores the digital image supplied from the image input unit 3, and is composed of a random access memory or the like. The thinning unit 5 converts a line figure included in the digital input image stored in the image memory unit 4 into a center line having a width of 1 pixel, and the pixel on the center line is 1-pixel and the other pixels are 0. Store in the image memory unit 4 as a thinned image that is a pixel. Regarding the thinning method, some methods are known (Technical Report of IEICE, PRL 75-66, etc.), but any of them may be used. The line width measuring unit 6 measures the width of the graphic portion in the vertical direction, the horizontal direction, and the 45 ° direction in the digital input image with respect to 1-pixel of the thinned image stored in the image memory unit 4, and determines the minimum value. The value is set as the line width, and a value corresponding to a predetermined range of the line width is given to 1-pixel of the thinned image and stored in the image memory unit 4 as the thinned image with the line width. The monotone curve extraction unit 7 extracts all the monotone curves from the thinned image accumulated in the image memory 4 and writes the monotone curves in the point sequence memory unit 8 by calculating the line width accumulated in the image memory unit 4. This is performed by referring to the thinned image. The point sequence memory unit 8 is a unit for accumulating a series of pixel addresses defined by a pair of row coordinates and column coordinates. The image output unit 9 is a unit that displays the point sequence in the point sequence memory unit 8 and is a printer, a display, or the like. The control unit 10 is a unit that controls the whole so that a monotone curve is extracted from the line graphic data accumulated in the image memory unit 4. These operations are as follows. First, according to an instruction from the control unit 10, the image input unit 3 inputs a line graphic and stores it in the image memory unit 4. Next, according to an instruction from the control unit 10, the line thinning unit 5 converts the line graphics accumulated in the image memory unit 4 into a center line, and separates the line graphics in the image memory unit 4 as a thin line image separately from the input line graphics. Store. Next, according to an instruction from the control unit 10, the line width measuring unit 6 obtains a thinned image with a line width from the input line graphic and the thinned image stored in the image memory unit 4, and calculates the input line graphic and the thinned image. It is stored separately in the image memory unit 4. Next, according to an instruction from the control unit 10, the monotone curve extraction unit 7 extracts monotone curves one by one from the thin line image and the line width thin line image accumulated in the image memory unit 4, and extracts one Every time a monotone curve is extracted, the coordinate series of pixels forming the monotone curve is output to the point sequence memory unit 8. Finally, according to an instruction from the control unit 10, the image output unit 9 sets the pixel value stored in the point sequence memory unit 8 to “1” and the other pixel values to “0”, and outputs the image as an image to paper or the like. To do. FIG. 4 is a diagram for explaining the configuration of the monotone curve extraction unit 7, where 71 is an image scanning unit, 72 is a center line tracking unit, 73 is a monotonicity determination unit, 74 is a center line detection unit, and 75 is a monotone curve. It is an extraction control unit. The image scanning unit 71 simultaneously raster-scans the thinned image and the thinned image with the line width accumulated in the image memory unit 4, is not a branch point, is untracked, and has a line width W or more. Pixels are extracted and their coordinates are output to the monotone curve extraction control unit 75. The center line tracking unit 72 receives 1 from the coordinates of the pixel of interest (i _l , j _l ) of tracking and the pixel of interest, which is given from the monotone curve extraction control unit 75.
The last tracked pixel [(i _l-1 , j _l-1 ) to increase the value of the pixel coordinate subscript in the tracked order, and (i to decrease the value of the pixel coordinate subscript in the tracked order _{l + 1} , j _{l + 1} )], the pixel to be tracked next with reference to the thinned image and the thinned image with line width accumulated in the image memory unit 4 To increase the subscript value (i _{l + 1} , j _{l + 1} ), to decrease the subscript value of the pixel coordinates in the traced order, obtain (i _l-1 , j _l-1 )] The pixel is marked as tracked on the image, and the coordinates of the pixel are output to the monotone curve extraction control unit 75. When the last tracked pixel is (i _l-1 , j _l-1 ),
FIG. 5 shows a processing procedure in which the center line tracking unit 72 obtains (i _{l + 1} , j _{l + 1} ). FIG. 5 is a diagram showing a processing procedure of the center line tracking unit. When the previously tracked pixel is (i _{l + 1} , j _{l + 1} ), it is easily obtained by inverting + and − in the notation representing the coordinates of the pixel, and therefore it is omitted. The monotonicity determination unit 73 is given the coordinates of the pixel row tracked by the monotonic curve extraction control unit 75, and determines whether or not the conditions of the tracking rules (c) to (e) of the above procedure 1 are satisfied. Output to the extraction control unit 75. The center line detection unit 74 determines that the thin line image and the thin line image with line width stored in the image memory unit 4 are on the center line based on the pixel coordinates given from the monotone curve extraction control unit 75. it is unextracted as curves, and extracts all satisfied pixels that belong to or more lines line width W, among them (i _k, j _k) in the vicinity of (i _k, j _k -1) Then, the pixel (i _{k + 1} , j _{k + 1} ) to be detected first is obtained by inspecting counterclockwise from, and the pixels (i _{k + 1} , j _{k + 1} ) and (i _k ,
j _k ) is marked as tracked, and the coordinates of the pixel (i _{k + 1} , j _{k + 1} ) are output to the monotone curve extraction control unit 75. The monotone curve extraction control unit 75 controls the image scanning unit 71 so that the monotone curve extraction is performed on the entire thinned image stored in the image memory unit 4 as shown in FIG. That is, the image scanning unit 71 simultaneously raster-scans a thinned image and a thinned image with a line width to find 1-pixel (i, j) that is not a branch point, is untracked, and has a linewidth of W or more. It is the starting point of one monotone curve. The extraction of one monotone curve is realized by the monotonic curve extraction control unit 75 storing the coordinates of the tracked pixels and controlling them as shown in FIG. FIG. 6 is a diagram showing a control procedure of the monotone curve extraction controller. FIG. 7 is a diagram for explaining the control procedure when the extraction of one monotone curve is executed for the entire vector data of one image. It should be noted that for the data obtained by vectorizing the center line image data obtained by thinning the binary image, the above steps 1 to 3 are the steps 1'to 3'as shown in FIG.
Can be simplified as follows.

[Procedure 1 '] According to the following tracing rules (a') to (e ') from the start vector, a vector which belongs to a line having a line width of W or more and which has not been extracted as a monotone curve is traced. However, the two nodes of the start vector are (i _k , j _k ) and (i _{k + 1} , j _{k + 1} ), and the tracking direction is from (i _k , j _k ) to (i _{k + 1} , j _{k + 1} ). Let (i _l , j _l ) be at the end of the already tracked vector sequence and not equal to (i _k , j _k ). (A ') If the number of vectors to be processed and the number of connected vectors is 1, the process is terminated. (B ') When the number of vectors that can be traced next, including those not to be processed, reaches two or more, a vector having a smooth direction in the direction of the vector of interest is selected and traced. If there is no smooth direction, the process ends. That is,
A vector that is closest to 0 ° when the angle formed with the vector of interest is α ° or less is obtained. (C ') Within the node (i _r , j _r ) of the tracked vector [excluding (i _k , j _k )], i _{k + 1} −i _k and i _r −i _k have different signs. Or i _r = i _k exists, and j _{k + 1} −j _k and j _r
If there is a sign of −j _k that is different or if j _r = j _k exists, the process ends. (D ') Within the node (i _r , j _r ) of the tracked vector [excluding (i _k , j _k )], j _{k + 1} −j _k and j _r −j _k have different signs. Or there is no one with j _r = j _k , and | j _r −
If j _k | has a length equal to or greater than the threshold value, the procedure ends. (E ′) In the tracked vector node (i _r , j _k ) [excluding (i _k , j _k )], i _{k + 1} −i _k and i _r −i _k have different signs. Or there is no i _r = i _k and | i _r −
If i _k | has a length equal to or greater than the threshold value, the procedure ends.

[Procedure 2 ′] Procedures 2 ′ and 3 ′ are executed only when the tracking rule (d ′) or (e ′) is satisfied in the procedure 1 ′. A vector which belongs to a line having a line width of w or more and has not been extracted as a monotone curve is traced from the vector traced lastly in the procedure 1'by the above-mentioned tracing rules (a ') and (b').

[Procedure 3 '] Pixels that belong to a line having a line width of W or more and have not been extracted as a monotone curve according to the above-described tracking rules (a') and (b ') in the direction opposite to the procedure 1'from the start vector. Chase. The vector sequence obtained by steps 1 to 3 is used as one monotone curve. (Effects of the Invention) As described above, according to the present invention, a line is traced in a direction as smooth as possible, and monotonicity is determined by the lengths of the line in the x direction and the y direction. Not subject,
It is possible to accurately extract a monotonous free curve. Moreover, since the monotone curves are extracted separately for each line width, it is possible to accurately classify the extracted monotone curves.

[Brief description of drawings]

FIG. 1 is a diagram for explaining the principle of the present invention, FIG. 2 is a diagram for explaining the control procedure when executing extraction of one monotone curve for the entire image data of one image, and FIG. FIG. 4 is a block diagram of an embodiment showing the configuration of the invention, FIG. 4 is a diagram further explaining the configuration of a monotone curve extraction unit which is a constituent element of FIG. 3, and FIG. 5 is a diagram showing a processing procedure of a center line tracking unit. FIG. 6 is a diagram showing a control procedure of the monotone curve extraction control unit, and FIG. 7 is a diagram illustrating a control procedure when the extraction of one monotone curve is executed for the entire vector data of one image. . 1 ... Background, 2 ... Center line of line figure, 3 ... Image input section, 4 ...
Image memory unit, 5 ... Thinning unit, 6 ... Line width measuring unit, 7 ... Monotone curve extracting unit, 8 ... Point sequence memory unit, 9 ... Image output unit, 10
Control unit 71 Image scanning unit 72 Center line tracking unit 73 Monotonicity determination unit 74 Center line detecting unit 75 Monotonic curve extraction control unit

Continuation of the front page (51) Int.Cl. ⁶ Identification number Office reference number FI Technical display location G06T 7/00 7623-5L G06F 15/60 350 D 15/64 A

Claims (2)

[Claims] 1. A method of automatically extracting a monotone curve from centerline image data obtained by thinning binary line graphic data or data obtained by vectorizing the data, wherein (a) When the number of neighboring points to be extracted reaches one, the tracking is stopped, and (b) when the bifurcation point of the center line is reached, a smooth direction with respect to the already tracked part is obtained. If so, continue tracking in a smooth direction, otherwise stop tracking, and (c) there is a tracked point whose x coordinate is equal to the x coordinate of the tracking start point and is tracked. If there is a y-coordinate that is equal to the y-coordinate of the tracking start point among the traced points, stop the tracking, and (d) in the tracked points, the x-coordinate is equal to the x-coordinate of the tracking start point. There is nothing and the traced line is in the x direction Stop tracking if it has a length greater than or equal to a threshold, and (e) there is no tracked point whose y coordinate is equal to the y coordinate of the tracking start point and the tracked line is y A point on the center line is traced with a tracking rule that the tracking is stopped if the direction has a length equal to or more than a threshold, and a line obtained by the tracking being stopped by the tracking rule (d) or (e) is a monotone curve. It is determined that the line on the center line is further traced from both ends using only the tracking rules (a) and (b), and the obtained line is made into one monotone curve. Figure extraction method. 2. Pixels or vectors according to a plurality of line width ranges, line width range 1 to line width range N, which are provided from the outside by measuring the line widths of lines in advance when performing graphic extraction for an entire image. First, monotonic curve extraction is performed by extracting only pixels or vectors belonging to the line width range 1 and then monotone curve extraction is performed by extracting pixels or vectors belonging to the line width ranges 1 and 2. Then, similarly, expand the line width range one by one in the same manner, and
The graphic extraction method according to claim (1), characterized in that the monotone curve extraction is performed until all are extracted.