JPH0664607B2 - Straight line extractor - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a document drawing recognition method for recognizing an image input by scanning a document drawing, and in particular, a straight line forming a character or line figure from an input image. It relates to a straight line extraction method for extracting components.

(Prior art) With the spread of computers, as one of the techniques to use computers more effectively, the importance of document drawing recognition technology that automatically inputs many document drawings that flood around us into computers. Is increasing. In recognition of document drawing image,
Extraction of straight lines or line segments that make up characters and line figures is the basis of many subsequent processes, and the establishment of a method for accurately extracting straight lines and line segments in document drawing images without omission This is an important issue.

As a typical straight line extraction method that has been used in the past, after thinning the image, the thinned image is traced, and broken line approximation is performed by dividing each feature point such as an intersection, a branch point, or a point where the inclination changes. , A method of converting into vector information is known (for example, the 1980 National Institute of Electronics and Communication General Conference Collection 1150). As a method that does not require thinning, the contours on both sides of the line image are tracked at the same time, and the line segment is detected by vectorizing the centers of the contours on both sides while taking into consideration the change in inclination, the intersection, and the branch point. There is a method to do so (for example, 1985 IEICE General National Congress Proceedings 11
53).

(Problems to be solved by the invention) In the method of approximating a polygonal line after thinning an image, an unintended straight line may occur or a single straight line may occur due to "whiskers" or "cuts" that occur when thinning an image. There was a problem that was divided. In addition, in the vectorization process, connected pixels having linearity are divided and extracted at feature points, but since the existence of feature points is judged only locally, line segments are easily affected by local image variations. Had the drawback of becoming unstable. On the other hand, the method of dividing a feature point and extracting a line segment while simultaneously tracing the contours on both sides of a straight line solves the problem associated with the thinning of the method, but the principle of polygonal line approximation between feature points Since they are the same, the drawback that they are easily affected by the local variation of the line direction and line width cannot be eliminated. Furthermore, since it is necessary to determine the existence of a branch point or an intersection point from the tracking situation of the contours on both sides, there is a problem that the processing becomes complicated.

SUMMARY OF THE INVENTION An object of the present invention is to provide a straight line extraction method which is not easily affected by the line width and local fluctuations in the straight line direction and which can be realized by a simple process in order to solve the above problems.

(Means for Solving the Problems) A straight line extracting apparatus of the present invention scans a document drawing recorded on a paper surface and converts a local pattern for each minute local area of an input image into a predetermined direction line element. A local pattern identifying means for extracting the classified identification information and the angle of the local pattern, and a line for storing line element information including the identification information extracted by the local pattern identifying means, the angle and angle classification information, and the line element connection information. An element storage means, a line element reading means for extracting from the line element storage means a line element information group that matches the input identification information or a combination of identification information and angle classification information, and read by the line element reading means. Angle classification means for performing classification based on the angle of the line element information group and outputting the angle classification information, and identification information of the line element information group read by the line element reading means And a line element group that is connected on the image based on the angle classification information, and outputs line element connection information, which is an identifier of the line element information that is connected to the line element, to the line element storage means and is a representative of the line element group. A line element connecting unit that outputs the line element to the line segment information storage unit, a line segment information storage unit that stores line segment information composed of the representative line element and the characteristic value of the line segment, and the line segment information storage unit And a feature amount calculation means for obtaining a characteristic value of a line segment defined by a line element group obtained by the line element connection information of the selected representative line element and the line element information and outputting it to the line segment information storage means. The linear component of is characterized in that its position and feature amount are obtained as a line element group that is divided by the representative line element of line segment information and the line element connection information of line element information.

(Operation) In the present invention, since the minute line elements forming the line segment in the input image are obtained by the local pattern identification means, the local variation of the line width and the line direction in the minute region is absorbed. , The line elements constituting the line segment and their directions are stably extracted. Furthermore, the angle classification means finely classifies line elements that form line segments that are not classified by the local pattern recognition means and that have subtly different directions. The identification ability is secured. Further, in the line element connecting means, for each line element group classified by the angle classifying means, the relative direction in which the two line elements are located matches the direction of the line elements, and the closer the two line elements are, the more the same. By judging that it is on the line segment,
Line segment extraction that is not affected by line breaks and local variations in line direction and line width is performed.

(Example) Hereinafter, an example of the present invention will be described with reference to the drawings. FIG. 1 is a logical block diagram showing the function of a straight line extraction method using the present invention, 1 is an image input means for obtaining an input image, and 2 is a predetermined local pattern for each minute local region of the input image. Local pattern identifying means 3 for extracting the identification information classified into the direction line elements and the angle of the local pattern, and the identification information extracted by the local pattern identifying means 2, the angle and angle classification information, and the line element connection information. A line element storage unit for storing line element information, 4 is a line element reading unit for extracting a line element information group having a characteristic designated by the control unit 9 from the line element storage unit 3, and 5 is a line element reading unit 4. An angle classification means 6 which performs classification based on the angle of the read line element information group and outputs angle classification information, and 6 is identification information and angle classification information of the line element information group read by the line element reading means 4. A line element connecting unit that detects a line segment as a line element group to be connected on the image and outputs the line element connection information and a representative line element of the line element group, and 7 is a line composed of the representative line element and the feature value of the line segment. Line segment information storage means for storing segment information, 8
Is a feature amount calculating means for obtaining the feature value of the line segment indicated by the representative line element stored in the line segment information storing means 7 and outputting it to the line segment information storing means 7, and 9 is the image inputting means 1 or the feature amount calculating means. 8 is a control unit for controlling 8.

An input image including a character graphic input by the image input means 1 is first classified into a predetermined direction line element by the local pattern identification means 2. The local pattern identifying means 2 has direction basic patterns of line elements having different directions, and a line is obtained by classifying the local pattern inside each of the minute regions of the input image into any of the preset direction basic patterns. The direction line elements constituting the minutes are extracted, and the identifier which is the number or the symbol corresponding to the classified direction basic pattern is obtained. As for the local area on the line segment, the direction line element is found because it matches with any one of the direction basic patterns, and the direction line element is not extracted because it does not resemble any direction basic pattern in the local area of the intersection / branch point. For a direction line element that can be classified into any one, a direction value indicating the angle of the local pattern is obtained. Further, the direction value of the local pattern is stored in the line element storage means 3 together with the identification information including the position and the identifier of the obtained direction line element on the image. If it cannot be classified into any of the direction line elements, nothing is output to the corresponding local area. This process is performed on the entire image for each local region at a position that differs by a preset number of pixels, and all directional line elements in the image are extracted.
The function of classifying the local pattern into direction line elements can be realized by a known technique such as a matching technique used in the pattern recognition technique, for example, a two-dimensional correlation method or a similarity method by eigenvalue expansion of the pattern. The function of storing a dictionary required for matching is realized by a fixed storage means such as a ROM in the local pattern identification means 2 or a rewritable storage means via a communication line. As a method of obtaining the direction value of the local pattern, a method of obtaining the major axis direction of the inertia ellipse from the moment of the pattern can be used.

The line element storage unit 3 has a function of storing the line element information 10 including the data items shown in FIG. 2 for each direction line element extracted by the local pattern identification unit 2. In FIG. 2, line element coordinates are position coordinates on the image of the direction line element, line element identifiers are numbers or symbols corresponding to the direction basic patterns classified by the local pattern identifying means 2, and direction values are local pattern identifying means 2. The angle and the angle classification identifier on the image of the local pattern calculated by are the angle classification information obtained by the angle classification means 5, that is, the numbers or symbols corresponding to the classified sets. The line element connector is the line element connection information obtained by the line element connection means 6, and is a pointer for connecting the line element groups forming the extracted straight line on the line element storage means 3. The line element information 10 in the line element storage means 3 is specified by the address in which it is stored (hereinafter referred to as the line element address), and the reference / writing is performed.

The line element reading unit 4 reads the line element information 10 of the direction line element having the line element identifier designated by the control unit 9 among the direction line elements stored in the line element storage unit 3, and then to the angle classification unit 5. It has a function of outputting, and a function of reading out the line element information 10 of the direction line element having both the designated line element identifier and the angle classification identifier and outputting it to the line element connecting means 6. That is, the control unit 9
Upon receiving the designated line element identifier, the line element reading means 4
Of the direction line elements stored in the line element storage means 3, the set of line element addresses and direction values of all the direction line elements whose term of the line element identifier matches the designated line element identifier is output to the angle classification means 5. To do.
When the designated line element identifier and the designated angle classification identifier are received from the control unit 9, among the direction line elements stored in the line element storage unit 3, the term of the line element identifier matches the designated line element identifier and the angle classification is performed. The knowledge element outputs the pair of line element addresses and line element coordinates of all the direction line elements that match the designated angle classification identifier to the line element connecting means 6.

The angle classifying unit 5 classifies into a set of direction line elements having similar direction values (hereinafter referred to as a similar direction line element group) by using the input direction values of the direction line element group, and forms a similar direction line element group. It has a function of writing the same angle classification identifier into the line element storage means 3 for all the direction line elements to which it belongs. For classification based on the direction value, a clustering method used in statistical processing, for example, a known method such as the maximum distance method or the isodata method can be used. That is, the direction line element group [S _i ] (hereinafter []
When the set of N sets C _k = [S _kj ] (k = 1 to N) is obtained as a result of the classification of the direction values of the direction line element S _kj belonging to C _k , All about S
_The number or symbol ID _k (for example, number k) corresponding to C _k is written in the term of the angle classification identifier of the line element information 10 in the line element storage unit 3 corresponding to _kj .

The line element connecting unit 6 has a function of extracting a line segment by dividing the input directional line element group into directional line element groups forming the same line segment. The line element connecting unit 6 forms the same line segment based on the relative displacement of the direction line elements as a means for determining whether or not the two direction line elements form the same line segment. Each direction line element identifier has a position reliability conversion means for obtaining reliability. That is, the position reliability conversion means is
A method that gives higher reliability when the relative direction in which one direction line element is located and the unique direction of the line element identifier of the direction line element match, and the relative distance between the two is close, and low reliability otherwise. Is. The procedure for obtaining the direction line element groups that form the same line segment using the position reliability conversion means will be described below.

1. Set C = 0.

2. Let C + 1 be the new C. An arbitrary one S _a of the direction line element group S = [S _i ] is taken out and set as an element of the set A _c . Also, _Sa is excluded from S.

3. Do the following 3.1 through 3.3 for each element S _i of S = [S _i ].

3.1 The reliability R _icj between S _i and each element S _cj of the set A _c is _obtained by the position reliability conversion means.

3.2 Ask for.

3.3 If Rmax exceeds a preset threshold T, then S
Add _i to the elements of A _c and remove S _i from the elements of S.

4. If S is not empty, repeat from 2. If empty, end.

As a result, the set of directional line elements constituting one line segment is A _i
It is extracted as (i = 1 to c). Next, the line element connecting means 6
Performs the following steps 1 to 3 for each A _i ,
The line element storage means 3 and the line segment information storage means 7 generate information in which the line elements forming the line segment are connected. Here, each element of A _i is S _ik , that is, A _i = [S _ik ] (k = 1 to n).

1. Write the line element address of S _i1 into the item of the representative line element of the line segment information 11 of the line segment information storage means 7.

2. Do the following for each of the S _ik (k = 1 to n−1):

2.1 _Write the line element address of S _{ik + 1} in the line element connector section of S _ik .

3. Write a symbol to indicate the end _in the line element connector of S _in .

With this, the first line element address is searched from the item of the representative line element of the line segment information 11, and by sequentially tracing the line element connector of the line element information 10 indicated by the line element address, the direction forming one line segment. Data that can refer to line elements are obtained. The procedure in the line element connecting means 6 can be easily realized by a programmable processing device such as a microprocessor. Further, the position reliability conversion means is a table format stored in a program on the same processing device that performs the procedure, or a writable storage device whose contents can be set in advance through a read-only storage device or a communication line. It can be realized by a table.

The line segment information storage means 7 has a function of storing the line segment information 11 including the data items shown in FIG. In FIG. 3, the representative line element is a pointer that represents one of the line element addresses of the direction line element group that constitutes the line segment, and is written by the line element connecting means 6. The line segment direction value is the angle on the image of the line segment, the line segment length is the length on the image, and the end point coordinates are the coordinates on the image of the two end points of the line segment. Be done. The line segment information storage means 7 is the line element storage means 3
May be implemented in a specific location on the same storage device.

The feature amount calculation means 8 has a function of calculating the angle, length, and coordinates of the end points of the line segment on the image of the line segment extracted by the line element connection means 6, and is realized by the configuration shown in FIG. It
In FIG. 4, the maximum / minimum calculating means 12 is a function for obtaining the maximum value and the minimum value of the line element coordinates, the line segment direction calculating means 13 is a function for obtaining the direction value of the line segment from the direction value, and the line segment length calculating means 14
Is a function of obtaining the length of the line segment from the maximum value and the minimum value of the line element coordinates, and the end point coordinate calculation means 15 is a function of obtaining the coordinates of the two end points of the line segment. The feature amount calculation means 8 positions coordinate X _i and Y _{i of} the direction line element group forming the line segment based on the representative line element of each line segment stored in the line segment information storage means 7 and the direction value D _i. Are sequentially read, and the processes 1 to 4 below are performed.

1. The maximum / minimum calculation means 12 is Xmax, Xmin, Ym determined by the following formula
Find ax, Ymin.

However, W _x and W _y are the horizontal width and vertical width of the minute area, respectively. 2. The line segment length calculation means 14 calculates Xmax, Xmin, Ymax, Y obtained in the above 1.
Use min to find L determined by the following formula.

3. The line segment direction calculation means 13 obtains D determined by the following equation.

4. The end point coordinate calculation means 15 uses Xmax, X obtained in the above 1 and 2.
Determined by the following formula using min, Ymax, Ymin, D (EX1, EY1)
And (EX2, EY2).

The D, L, EX1, EY1, EX2, EY2 thus obtained are stored in the line segment direction value, line segment length, and end point coordinates of the line segment information storage means 7, respectively.

The control unit 9 has a function of controlling the image input unit 1 or the feature amount calculation unit 8 and controlling the procedure of the straight line extraction processing described below.

A specific example of the process in the straight line extraction method will be described in detail below with reference to FIGS. 5 to 10.

FIG. 6 (a) is an example of an image including a line segment whose line width varies,
Coordinates are provided with the origin in the upper left, the X axis in the right direction, and the Y axis in the downward direction. On the other hand, FIG. 5 (a), (b), (c),
(D) is an example of a line element identifier corresponding to a dictionary of direction basic patterns used for classification in the local pattern identifying means 2.
A case where a rectangular area is taken as a minute area and the line elements are classified into four directions is shown. The numbers assigned to the upper left of FIGS. 5A to 5D are line element identifiers corresponding to the respective direction basic patterns. The local pattern identification means 2 shifts the position by, for example, 2 pixels in the X-axis and Y-axis directions of the image, and
For each rectangular area of × 5 pixels, the four directional basic patterns are compared and compared to find the most similar pattern. When the image of FIG. 6 (a) is input, the local pattern identifying means 2 performs matching on the input image for each minute rectangular area, and selects the most similar directional line element among the four directional line elements. The identifier and the direction value of the pattern in the rectangular area (in FIG. 6A, the clockwise direction is the positive direction and the angle in degrees) are obtained, and the line element information is generated in the line element storage unit 3. The data thus generated are the terms of the line element coordinates and the line element identifier of the line element information of FIG. 7 (a), which is a specific example of FIG. 2, and other terms have not been obtained at this time.
Symbols A ₁ to A ₁₇ at the left end of each line element information in FIG. 7A represent line element addresses, and a direction line element having a line element address X will be referred to as a direction line element X below. . Further, FIG. 6 (b)
Shows the obtained direction line element at a position corresponding to the image using the line element identifier.

Next, the control unit 9 finely classifies the direction line elements having the same line element identifier for each of the line element identifiers 1 to 4 of the extracted direction line elements by using the direction value, and obtains a similar direction line element group. To start. That is, regarding the line element information of FIG. 7A, first, the line element reading means 4 is instructed to read the direction line element having the direction identifier 3 and the line element reading means 4 sets the line element address and the direction value. , (A ₁ , 90), (A ₃ , 92), (A ₄ , 94), (A
₅ , 90), (A ₇ , 92), (A ₈ , 92), (A ₉ , 88), (A ₁₁ , 9,
_{0), (A 12, 92} ), (A 14, 92), (A 15, 88), (A 17, 9
0) is output to the angle classification means 5. The angle classification means 5 performs classification based on the direction values of the 12 directional line elements that have been input, but in the present example, the result of the fine classification is that all 12 directional line elements are a group of similar directional line elements. Therefore, the line element addresses A ₁ , A ₃ ,, A ₄ ,, A ₅ ,, A ₇ ,, A ₈ ,, A ₉ ,
The same number 1 is written in the angle classification identifier section of all the line element information of A ₁₁ , A ₁₂ , A ₁₄ , A ₁₅ , and A ₁₇ . This indicates that the direction line element having the direction identifier 3 has no difference even if the direction value is examined in detail. Further, the same processing is performed for the direction line element having the direction identifier 4, and the term of the angle classification identifier of the line element information indicated by the line element addresses A ₂ , A ₆ , A ₁₀ , A ₁₃ and A _16. The same number 1 is written in, and it is found that there is no difference in the direction value of the direction line element having the direction identifier 4.

An example in which the angle classifying means 5 classifies the directional line elements into groups will be described later.

Next, the control unit 9 activates a process of dividing a direction line element group having the same line element identifier and angle classification identifier into units forming a line segment. First, the line element identifier is 3 and the angle classification identifier is 1.
The line element reading means 4 is instructed to read a direction line element which is a line direction element, and the line element reading means 4 sets the line element address and position coordinate set (A ₁ , 2).
0,20), (A ₃ , 32,20), (A ₄ , 34,20), (A ₅ , 20,22),
(A ₇ , 32,22), (A ₈ , 34,22), (A ₉ , 20,24), (A ₁₁ , 3
2,24), (A ₁₂ , 20,26), (A ₁₄ , 32,26), (A ₁₅ , 20,2)
8) and (A ₁₇ , 32, 28) are output to the line element connecting means 6. 8th
The figure is an example of conversion of the position reliability conversion means of the line element connection means 6. In the figure, (a) is a line element identifier of 1, (b) is a line element identifier of 2, (c) is a line element identifier of 3, and (d) is a line element identifier of 4. Indicates a value. In FIGS. 8 (a) to 8 (d), the horizontal direction is the difference in the X coordinate dx.
The vertical direction is the difference dy of the Y coordinate, and the number written at the intersection of dx and dy means the percentage of reliability that the two directional line elements are on the same line segment. 8 (a) and 8 (c)
It is symmetric about dx = 0 and dy = 0, and represents the whole quarter. Further, (b) and (d) are symmetrical with respect to the straight line S ₁ S ₂ and the straight line S ₃ S ₄ shown in the figure, respectively, and show half of the whole. The line element connecting means 6 extracts a direction line element group forming a line segment according to the procedure described above by the input line element address and position coordinate set and the position reliability converting means of FIG. 8 (c). FIG. 7 (b) is a specific example of FIG. 3 and shows the line segment information stored in the extraction result line segment information storage means 7. That is, the line element address A ₁ is written in the item of the representative line element of the line segment information B ₁ , and A ₅ is added in the item of the line element connector of the line element address A ₁ of FIG. A _{9 in} the term of the line element connector of the prime address A ₅ , A _{12 in} the term of the line element connector of the line element address A ₉ , A _{15 in} the term of the line element connector of the line element address A ₁₂ . The END symbol indicating the end is written in the line element connector section of the line element address A ₁₅ . At the same time, is written terms in the line element address A ₃ are written in the representative line element of the line segment information B _2, A ₄ the section line element dropout line element address A ₃ of FIG. 7 (a)
Is A _{7 in} the term of line element connector of line element address A ₄ , A _{8 in} the term of line element connector of line element address A ₇ , and in the term of line element connector of line element address A _8.
A ₁₁ is A ₁₄ in the section line element dropout line element address A ₁₁ is A ₁₇ in the section line element dropout line element address A ₁₄ is, term line element dropout line element address A ₁₇ The END symbol indicating the end is written in. As a result, the line element groups A ₁ , A ₅ , A ₉ , A ₁₂ , A ₁₅ and the line element addresses A ₃ , A ₄ , A ₇ , A ₈ , A ₁₁ , A ₁₄ , A ₁₇ Two line segments composed of the direction line element group indicated by are extracted. Similarly, the control unit 9 sets the direction identifier to 4 and the angle classification identifier to 1
The same process is started for the direction line element group having. The line element connecting means 6 extracts the line element group to be connected by using the position reliability converting means of FIG. 8 (d) corresponding to the direction identifier 4.
As a result, the representative line element A ₂ is added to the line segment information B ₃ of FIG. 7 (b), and the line element addresses A ₂ , A ₆ , A ₁₀ , and A ₁₃ of the line element connector of FIG. Write A ₆ , A ₁₀ , A ₁₃ , and A ₁₆ , respectively, and the END symbol in the line element connector section of the line element address A ₁₆ . As a result, the line address A ₂ , A ₆ , A
A line segment composed of the direction line element groups of ₁₀ , A ₁₃ , and A ₁₆ is extracted. The control unit 9 activates similar processing for other combinations of the direction identifier and the angle classification identifier, but there is no corresponding line element group in this example.

Finally, the control unit 9 activates the feature amount calculation means 8 and performs a process of calculating the feature amounts of the three obtained line segments. The feature amount calculation means 8 first obtains the line element address A ₁ from the term of the representative line element for the line segment information B ₁ and sequentially searches the line element connector to obtain the direction line element group corresponding to the line segment information B _1. Read the direction value and position coordinate of. According to the procedure described above, the line segment length, the line segment direction value, and the position coordinates of the two end points are obtained, and the line segment information storage means 7
It is stored in the line segment information B ₁ of. Similarly, the feature amount is calculated for the line segment information B ₂ and B ₃ , and finally the information regarding the three line segments is obtained as shown in FIG. 7 (b).

The processing for the image in FIG. 9A will be described in detail below.
FIG. 9A is an example of an image including line segments having slightly different inclinations. When the image is input, FIG. 6 (a) described above
In the same manner as in the above case, the local pattern identifying means 2 extracts the direction line elements as shown in FIG.
The position coordinates of the line element information having the line element addresses of A ₁₈ to A ₃₂ , the line element identifier, and the direction value are stored therein. FIG. 9B shows the direction line element at a position corresponding to the image by using the line element identifier.

Next, the line element reading means 4 reads the set of line element address and direction value of the direction line element having the line element identifier 1 and outputs it to the angle classification means 5. In this case, all A ₁₈ to A ₃₂ directional line elements are applicable. The angle classifying means 5 sets a set of direction values of the read direction line elements [-10,8, -8, -10, -8,10,9,10, -8, -10, -10,
−12,10,8,8] based on two similar direction line element groups [A ₁₈ ,, A
₂₀ , A ₂₁ , A ₂₂ , A ₂₆ , A ₂₇ , A ₂₈ , A ₂₉ ] and [A ₁₉ , A ₂₃ , A ₂₄ , A ₂₅ , A
₃₀ , A ₃₁ , A ₃₂ ], and 1 is set as the angle classification identifier of the former group of similar direction line elements, 2 is set as the angle classification identifier of the latter group of similar direction line elements, and the angle classification identifier of each line element information. Write in the section (See Figure 10 (a)). As a result, it is found that even a directional line element having the same line element identifier 1 has two components having different directional values. The control unit 9 activates the same processing for the direction line element group having a value other than 1 in the line element identifier, but there is no corresponding line element group in this example.

Next, the line element reading means 4 reads the line element address and the position coordinates of the direction line element whose line element identifier is 1 and whose angle classification identifier is 1,
Output to the line element connecting means 6. The line element connecting means 6 uses the position reliability converting means for performing the conversion shown in FIG. 8 (a) and uses the direction line element groups [A ₁₈ , A ₂₀ , A ₂₁ , A ₂₂ , A ₂₆ ,
A ₂₇ , A ₂₈ , A ₂₉ ]. Further, with respect to the direction line element having the line element identifier of 1 and the angle classification identifier of 2, the line element connecting unit 6 performs the same process using the position reliability converting unit of FIG. [A ₁₉ ,, A ₂₃ , A ₂₄ , A ₂₅ , A ₃₀ , A ₃₁ , A
₃₂ ] is extracted. As a result, representative line elements of line segment information B ₄ and B ₅ shown in FIG. 10 (b) and line element information of FIG. 10 (a)
The line element connector of A ₁₈ to A ₃₂ is obtained.

Subsequently, the feature amount calculation means 8 calculates the feature amounts of the line segments B ₄ and B ₅ , and writes them in the line segment information of FIG. 10 (b), and finally the information about the two line segments is obtained.

In the above embodiments, the direction line elements classified by the local pattern identifying means 2 are patterns in four directions, but it is also possible to have various directions such as eight directions. In this case, the conversion function of the position reliability conversion means in the line element connection means 6 is also provided for each type of direction line element. Further, the size of the rectangular area to be matched in the local pattern identification means 2 (5 × 5 pixels) and the movement amount of the position to be matched (every 2 pixels) may be values other than those shown here, and the size of the rectangular area. If you roughen or increase the movement amount, a rough line segment will be extracted,
It can be set according to the required accuracy.

(Advantages of the Invention) As described above, the present straight line extraction method has a characteristic that it is not affected by local line breaks and line width variations because the direction line elements are obtained by matching local regions. In addition, unlike the conventional method that approximates a polygonal line between characteristic points such as intersections, bifurcations, or points where the inclination changes, the same line segment is formed by the direction value of the direction line elements and the positional relationship between the direction line elements. It is possible to stably extract the line segment even if the line direction is locally changed or the line is broken because it is determined whether or not the line segment is a directional line element. Further, since the directional line elements are classified based on the directional values of a large number of directional line element groups and a global judgment is made, two connected line segments having a small difference in direction can be separated. Further, the present straight line extraction method has a characteristic that the processing is simple because it does not require the determination of the intersection or the branch point in the tracking processing of the thinned image or the contour of the image.

[Brief description of drawings]

FIG. 1 is a logical block diagram showing the function of a straight line extraction method using the present invention, FIG. 2 is a diagram showing a data format of line element information in a line element storage means, and FIG. 3 is a line segment information storage means. Showing the data format of the line segment information, FIG. 4 is a block diagram showing an example of the functional configuration of the feature amount calculating means, and FIG. 5 is an example of the direction basic pattern of the direction line elements extracted from the image by the local pattern identifying means. FIG. 6 is a diagram showing a first input image example, FIG.
FIG. 8 is a diagram showing the result of extracting line segments from the image of FIG. 6, FIG. 8 is a diagram showing a conversion example of the position reliability converting means of the line element connecting means, and FIG. 9 is a second input image example. Showing the tenth
The figure is a diagram showing a result of extracting line segments from the image of FIG. In the figure, 1 is an image input means for obtaining an input image,
2 is a local pattern identifying means for classifying / symbolizing a local pattern into line elements in a predetermined direction for each minute local area of the input image, and 3 is a local pattern identifying means 2 for extracting a direction value of the local pattern. The line element storage means 4 for storing the extracted results and the results of the angle classification means 5 and the line element connection means 6 to be described later is a line element reading means for extracting a line element having a specified characteristic from the line element storage means 3. Reference numeral 5 is an angle classification means for performing classification based on the direction values of the line elements extracted by the local pattern identification means 2, and 6 is a line segment on the image from the results of the local pattern identification means 2 and the angle classification means 5. Line element connecting means for detecting as a continuous line element,
Reference numeral 7 is a line segment information storage means for storing information for searching the line segment extracted by the line element connection means 6, and 8 is a feature amount for obtaining the feature value of the line segment extracted by the line element connection means 6. A calculation unit 9 is a control unit that controls the image input unit 1 or the feature amount calculation unit 8.

Claims (1)

[Claims] 1. Identification information in which a local pattern for each minute local area of an image input by scanning a document drawing recorded on paper is classified into predetermined direction line elements and an angle of the local pattern is extracted. Local pattern identification means, line element storage means for storing line element information composed of identification information extracted by the local pattern identification means, angles and angle classification information, and line element connection information, and identification information or identification information to be input. And a line element reading unit that extracts a line element information group that matches a combination of angle classification information from the line element storage unit,
Angle classification means for performing classification based on the angle of the line element information group read by the line element reading means and outputting angle classification information, and identification information of the line element information group read by the line element reading means And a line element group that is connected on the image based on the angle classification information, and outputs line element connection information, which is an identifier of the line element information that is connected to the line element, to the line element storage means and also represents the line element group. A line element connecting unit that outputs the line element to the line segment information storage unit, a line segment information storage unit that stores line segment information composed of the representative line element and the characteristic value of the line segment, and the line segment information storage unit And a feature amount calculation means for obtaining a characteristic value of a line segment defined by a line element group obtained by the line element connection information of the selected representative line element and the line element information and outputting it to the line segment information storage means. The straight line component of is the representative line element of the line segment information and the line element connection information of the line element information. A straight line extraction device characterized in that its position and feature amount are obtained as a line element group that can be traversed by.