 |
Claims  |
|
|
We claim:
1. A method for recognizing various kinds of lines drafted on a drawing in
an apparatus which recognizes the lines based upon an image data signal
obtained by scanning the drawing, comprising the steps of:
recognizing lines and overlap symbols drafted on the drawing, based upon
the image data signal, to obtain data representative of a position and a
line kind of each of the lines and data representative of a position and a
symbol kind of each of the overlap symbols, wherein said lines and said
overlap symbols are drafted on the drawing in such a manner that when at
least two lines to be drafted overlap each other along a path, only one of
the two lines is drawn along the path, and an overlap symbol is attached
to the one line at a point along the path in order to represent presence
of the other line not drawn, said overlap symbol being determined
depending upon a line kind of the other line not drafted; and
generating data representative of positions and line kinds of lines not
drawn on the drawing but represented by the recognized overlap symbols,
based upon the obtained data.
2. A method according to claim 1, wherein said generation of data
representative of the lines not drawn includes the steps of:
detecting a first line for each of the recognized overlap symbols among the
recognized lines to which first line each of the recognized overlap
symbols is attached on the drawing, based upon the obtained data
representative of the positions of the recognized lines and the position
of each recognized overlap symbol;
determining first and second points at different sides of each overlap
symbol on the first line detected for each recognized overlap symbol based
upon relative positional relationship between the first line for each
recognized overlap symbol and other recognized lines, so that said first
and second points represent points between which a line represented by
each overlap symbol is to pass along the first line for each recognized
overlap symbol; and
generating data representative of the line represented by each overlap
symbol, comprising data representative of a position of a portion of the
first line detected for each recognized overlap symbol between the first
and second points detected for each recognized overlap symbol and
representative of a line kind determined, depending upon each overlap
symbol.
3. A method according to claim 2, wherein said determination of said first
and second points for each recognized overlap symbol includes the steps
of:
detecting presence of a second line for the first line detected for one of
the recognized overlap symbols, wherein said second line passes through a
point on the first line detected for the one recognized overlap symbol and
represents a path along which a line represented by the one overlap symbol
can exist;
determining the point on the second line as one of the first and second
points for a line represented by the one overlap symbol.
4. A method according to claim 3, wherein said detection of the presence of
a second line includes the step of detecting, as the second line for one
recognized overlap signal, a line which has a terminal point on the first
line detected for the one recognized overlap symbol and which has a line
kind determined by a symbol kind of said one recognized overlap symbol.
5. A method according to claim 4, wherein said line kind which the second
line should have is uniquely determined by the symbol kind of the one
recognized overlap symbol.
6. A method according to claim 3, wherein said detection of the presence of
a second line includes the step of detecting, for one recognized overlap
symbol, a line which has a terminal point on the first line detected
having said recognized overlap symbol attached thereto and which
represents the same kind of line as the one indicated by the recognized
overlap symbol.
7. A method according to claim 6, wherein said overlap symbol attached to
the second line is the same as the one recognized overlap symbol.
8. A method according to claim 3, wherein said detection of presence of a
second line includes the step of detecting, as the second line for one
recognized overlap symbol, a line which crosses the first line detected
for the one recognized overlap symbol and has a recognized overlap symbol
attached thereto which represents the same line kind of line as the one
recognized overlap symbol does.
9. A method according to claim 8, wherein said overlap symbol attached to
the second line is the same as the one recognized overlap symbol.
10. A method according to claim 3, wherein, when plural lines are detected
each as the second line, one of the plural lines is selected as the second
line which defines one of the first and second points for the one
recognized overlap symbol, wherein said one of the plural lines passes
through a point on the first line nearest to the one recognized overlap
symbol among points on the first line through which said plural lines
pass.
11. A method according to claim 3, wherein said determination of the first
and the second points for each recognized overlap symbol further includes
the steps of:
detecting a terminal point of the first line detected for the one overlap
symbol;
determining the terminal point as one of the first and second points on the
first line detected for the one recognized overlap symbol.
12. A method according to claim 3, wherein said generation of the data for
the line for the one recognized overlap symbol includes the step of
generating data representing a line obtained by connecting the line
portion between the first and second points of the first line for the one
detected overlap symbol and the second line.
13. A method according to claim 2, wherein, when plural overlap symbols of
the same kind are recognized as attached to the same line within said
recognized lines, said detection of the first and second points is done
for only
14. A method according to claim 1, wherein the line kind of the line
represented by each recognized overlap symbol is uniquely determined
depending upon a symbol kind of each recognized overlap symbol.
15. A method according to claim 1, wherein lines of different colors are
treated as having different line kinds.
16. A method according to claim 1, wherein overlap symbols of different
colors are treated as representing different line kinds.
17. A method according to claim 1, wherein one of the recognized overlap
symbols has a line pattern having a predetermined length and oriented
perpendicular to a line to which the one overlap symbol is attached.
18. A method according to claim 1, wherein one of the recognized overlap
symbols has: a line pattern having a predetermined length and provided
perpendicular to a line to which the one recognized overlap symbol is
attached; and a dot pattern having a predetermined size and provided at an
end of the line pattern.
19. A method according to claim 1, wherein said data representative of a
position of each overlap symbol represents a position of a predetermined
point within each overlap symbol, wherein the point of each overlap symbol
is expected to lie on one of lines drafted on the drawing.
20. A method according to claim 1, wherein said data representative of a
position of each recognized line comprises data representing
characteristic points of each recognized line such as a bending point,
start terminal point and end terminal point.
21. A method according to claim 1, wherein one of drawing lines is a chain
line.
22. A method according to claim 1, wherein one of drawn lines is a dash
line.
23. A recognition apparatus, comprising:
a photo-electric converter means for scanning a drawing to generate an
image data signal representative of patterns on the drawing;
first memory means connected to said photo-electric converter means for
holding the image data signal;
first recognition means connected to said first memory means for
recognizing lines and overlap symbols drafted on the drawing, based upon
the image data signal, to obtain data representative of a position and a
line kind of each of the lines and data representative of a position and a
symbol kind of each of the overlap symbols, wherein said lines and said
overlap symbols are drafted on the drawing in such a manner that when at
least two lines to be drafted overlap each other along a path, only one of
the two lines is drafted along the path, and an overlap symbol is attached
to the one line at a point along the path in order to represent presence
of the other line not drafted, said overlap symbol being determined
depending upon a line kind of the other line not drafted;
second memory means connected to said first recognition means for holding
the data obtained by said first recognition means; and
second recognition means connected to said second memory means for
generating data representative of positions and line kinds of lines not
drawn on the drawing but represented by the recognized overlap symbols,
based upon the data held by said second memory means.
24. A recognition apparatus according to claim 23, wherein said data
representative of a position of each recognized line comprises data
representing characteristic points of each recognized line such as a
bending point, start terminal point and end terminal point.
25. A recognition apparatus according to claim 23, wherein said first
recognition means includes:
first microprocessor means connected to the first memory means;
third memory means for holding program instructions to control said first
microprocessor to recognize the lines and the overlap symbols drawn on the
drawing based upon the image data signal held by said first memory means;
and
bus means for connecting said first to third memory means to said first
microprocessor means; and wherein said second recognition means includes:
second microprocessor means connected to said first microprocessor means;
fourth memory means for holding program instructions to control said second
microprocessor means to generate the data representative of positions and
line kinds of the lines not drawn but represented by the recognized
overlap symbols; and
bus means for connecting said second and fourth memory means to said second
microprocessor means. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
CROSS REFERENCES TO RELATED APPLICATIONS
This application relates to the subject matters disclosed in U.S. Pat. No.
4,272,756 issued to Kakumoto et al on June 9, 1981 and assigned to the
present assignee, and in U.S. Pat. No. 4,428,077, issued to Simada et al
on Jan. 24, 1984, and assigned to the present assignee.
BACKGROUND OF THE INVENTION
The present invention relates to the automatic reading of a line drawing
and more particularly to the automatic recognition of a drawing including
a portion in which a plurality of lines of different types or kinds and/or
colors extend along the same path in a mutually overlapping or superposed
relation and in which a given one of the plural lines is actually drawn
while the remaining overlapping line or lines are represented,
respectively, by corresponding overlap symbols marked in association with
the given line.
When a line pattern or drawing having an area where a plurality of lines of
different line types or kinds and/or colors are drawn to extend along the
same path in a mutually overlapping or superposed relation, as is the case
with mask patterns employed in manufacturing LSI circuits, is to be stored
in a memory of a computer, it has heretofore been common in practice that
such area is manually designated by an operator with the aid of a table.
For reducing the burden of the operator, it is of course desirable that
the line pattern is automatically recognized with the resulting data being
inputted to the computer. However, a problem arises in this connection in
that the line pattern including the mutually overlapping lines is drafted
in a variety of different ways in dependence on the preferance of the
draftsmen. Supposing, for example, that a line of type or kind A overlaps
a line of a kind B in a drawing, one draftsman may draw the pattern with
both kinds (A and B) of lines being intermingled, while another draftsman
may omit one line and use a symbol representing omission or overlap of
that line. In other words, representation of a line pattern including
mutually overlapping lines or segments differs in dependence on the
draftsmen, resulting in great difficulty in the automatic recognition of
line patterns.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide automatic line
recognition which is capable of automatically and discriminatively
recognizing a line pattern or drawing which contains a part or parts where
a plurality of lines of different kinds and/or colors are drawn in a
mutually overlapping relation.
It is proposed according to an aspect of the present invention that a
drawing or line pattern is drafted in accordance with such rules that a
line which is to be drawn so as to overlap a given line is replaced by a
symbol referred to as an overlap symbol which represents the type or kind
and/or color of the overlapping line and is inserted at a location
associated with the given line, so that upon recognition of the whole line
pattern, the overlapping line or lines may be discriminatively and
individually estimated with the location of the overlap symbol as well as
the configuration thereof being utilized as a clue to the estimation.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 shows in a block diagram a general arrangement of a line recognition
system which may be employed for carrying out an embodiment according to
the invention.
FIG. 2 is a block diagram showing in detail a main portion of the line
recognition system shown in FIG. 1.
FIG. 3 illustrates corresponding relationships between overlap symbols and
lines represented by them.
FIG. 4 shows an example of a line pattern in which some lines are
represented by corresponding overlap symbols.
FIG. 5 a fragmental enlarged view showing a portion of FIG. 4.
FIG. 6 is a fragmental enlarged view showing another portion of FIG. 4.
FIG. 7 is a schematically enlarged fragmental view of FIG. 6.
FIG. 8 is a view illustrating an exemplary set of characteristic point data
obtained through processings executed by the line recognition system shown
in FIG. 1.
FIG. 9 is a view for illustrating another example of characteristic point
data produced by processings executed by the line recognition system shown
in FIG. 1.
FIG. 10 is a flow chart for illustrating a flow of overlap symbol
recognition processings.
FIG. 11 is a view for illustrating data produced by the overlap symbol
recognition processing.
FIG. 12 is a view illustrating a flow of overlapping line path recognition
processings.
FIG. 13 is a flow chart for illustrating line path searching processings.
FIG. 14 is a view for illustrating data produced by the searching
processings shown in FIG. 13.
FIG. 15 is a flow chart illustrating a processing for selecting a candidate
for the line path.
FIG. 16 is a schematic diagram for illustrating a procedure for selecting a
candidate for a line path in concern.
FIG. 17 is a schematic diagram for illustrating a procedure for
interconnection of lines.
FIG. 18 is a view for illustrating example of characteristic point data for
the line interconnection processing.
DESCRIPTION OF THE PREFERRED EMBODIMENTS
FIG. 1 shows in a block diagram a general arrangement of a line pattern
recognition apparatus for carrying out line recognition according to an
embodiment of the present invention. In this figure, a reference numeral 1
denotes a drawing or line pattern which constitutes the object to be
recognized, 2 denotes a photo-electric converter, 3 denotes an image
memory, 4 denotes a line path recognition device, 5 denotes a
characteristic (or feature) point memory, and finally numeral 6 denotes an
overlapping line recognition device.
FIG. 2 shows a more detailed circuit arrangement for the image memory 3,
the line path recognition device 4, the characteristic point memory 5 and
the overlapping line recognition device 6. The line path recognition
device 4 is constituted by a microprocessor I 40 and a program memory I
70, wherein the microprocessor I 40 can make access to the image memory 3
and the characteristic point memory 5 by way of a data bus 10 and an
address bus 11. The overlapping line recognition device 6 is constituted
by a microprocessor II 60 and a program memory II 80, wherein the
microprocessor II 60 can make access to the characteristic point memory 5
and a work memory 14 by way of a data bus 12 and an address bus 13.
Further, the microprocessors I and II 40 and 60 can access a register 90
through a data bus 14 and a data bus 15, respectively. The register 90 is
adapted to store therein the status indicating which microprocessor I or
II is making access to the characteristic point memory 5 on the one hand
and the status indicating whether the microprocessors I and II have
completed the respective processings.
In connection with the line recognition system outlined above, the drawing
or line pattern 1 which constitutes the object for recognition is now
assumed to be drafted in accordance with the rules mentioned below.
Rules for Drawing
(1) Overlap-representing symbols are used in correspondence with kinds or
species of overlapping lines which are to be omitted from representation.
By way of example, when a black chain line (long-and-short broken line) and
a black solid line overlap each other as shown in FIG. 3 at (a), a solid
line segment A of a short length is inserted so as to intersect the black
chain line as the overlap symbol for indicating that the black solid line
overlies the black chain line, as is illustrated at (a') in FIG. 3. In
case a black solid line and a long dash line overlap each other, as shown
in FIG. 3 at (b), the corresponding overlap symbol is formed by a black
solid line segment B which is attached with a solid circle at one end and
so inserted as to intersect the solid black line in such manner as
illustrated at (b') in FIG. 3. When a black solid line overlies a black
dash line, as shown in FIG. 3 at (c), a short black solid line segment C
attached with solid circles at both ends, respectively, intersects the
black solid line to constitute the corresponding overlap symbol
representing the omitted black dash line, as is illustrated at (c') in
FIG. 3. When a line represented by the overlap symbol has a specific
color, the corresponding overlap symbol is also drawn in the specific
color. It should however be noted that the overlap symbols A, B and C
mentioned above are shown only for the purpose of illustration. Symbols
having other configurations which represent definitely the omitted
overlapping lines can of course be made use of.
(2) When N lines of different kinds or species where N.gtoreq.2 are to be
draw in overlapping relation along the same line path, only an arbitrarily
selected one of these lines is drawn while the other lines are omitted,
wherein overlap symbols (i.e. symbols of omission) corresponding to the
kinds of the (n-1) lines as omitted are attached to the drawn line.
By way of example, with reference to FIG. 4, in case of a drawing or line
pattern where there exists a black solid line path extending from a point
P.sub.1 through P.sub.2, P.sub.3, P.sub.4, P.sub.6 and P.sub.7 and back to
P.sub.1 together with a black dash line path or route extending from the
point P.sub.1 through P.sub.12, P.sub.11, P.sub.4, P.sub.3 and P.sub.2
back to P.sub.1 and a black long dash line path extending from the point
P.sub.7 through P.sub.1, P.sub.2, P.sub.3, P.sub.4, P.sub.5, P.sub.10,
P.sub.9 and P.sub.8 back to P.sub.7, the black long dash line, the black
dash line and the solid line overlap one another along the path defined by
P.sub.1, P.sub.2, P.sub.3 and P.sub.4, while the black long dash line and
the black solid line overlap each other along the path segments defined by
the points (P.sub.1 ; P.sub.7 ) and (P.sub.4 ; P.sub.5), respectively. On
these conditions, the black solid line path segment defined by the points
P.sub.1, P.sub.2, P.sub.3 and P.sub.4 is provided with the symbol
representing the presence of the black dash line, this symbol being
designated by K.sub.2. Further, the path segment defined by P.sub.1 and
P.sub.7 is provided with the symbol K.sub.1 representing the superposition
of the black long dash line as omitted.
(3) The symbol representative of overlap is inserted at an arbitrarily
selected position on the path along which one and the same kind of line
extends continuously.
By way of example, reference is made to FIG. 4. The overlap symbol K.sub.2
may be entered at an arbitrary position on the black solid line path
P.sub.1 -P.sub.2 -P.sub.3 -P.sub.4, while the symbol K.sub.1 may also be
inserted in the path segment P.sub.7 -P.sub.1 -P.sub.2 -P.sub.3 -P.sub.4
-P.sub.5 at a given position.
The drawing or line pattern 1 drafted in accordance with the rules
mentioned above is read by the photo-electric converter means 2, such as a
television camera, a drum scanner or the like, to be converted into
electric signals which represent image data at various locations of the
line pattern 1. The electric signals thus obtained are stored in the image
memory 3 at storage addresses corresponding to the locations of the
drawing 1 at which the video signals are derived, respectively.
In case the drawing or line pattern 1 is drawn in a single color, the
electric signal mentioned above is composed of binary signal components
representative of light and shade. On the other hand, when the line
pattern 1 is drawn in several colors, the electric signal contains signal
components representative of the colors in addition to the binary signal
components.
The microprocessor I denoted by 40 in FIG. 2 is destined to execute a line
path recognition processing program which is stored in the program memory
I (denoted by 70). This processing is composed of two sub-processings,
i.e. the characteristic point extracting processing and the broken line
recognition processing. The phrase "broken line" is used with intention to
encompass the dash line, the long dash line and the chain line. In the
execution of the line path recognition processing, the characteristic or
feature points (P) on a line path are discriminatively detected on the
basis of the image data and transferred to the characteristic point memory
5 to be stored therein. The contents of these recognition processings will
be described below in more detail on the assumption that the object or
line pattern (drawing) to be recognized is drawn in white and black. With
regards to the drawings in several colors, description will be made only
in respect to the difference from the former.
(1) Processing For Extracting Characteristic (Feature) Points
It is assumed that the image data for the line pattern shown in FIG. 4 is
stored in the image memory 3. In the characteristic point extracting
processing, the characteristic or feature points such as start terminal
points, end terminal points and bending points are identified or
recognized from the image data representative of line segments. More
specifically, reference is made to FIG. 5 which shows in an enlarged view
a region defined by points Z.sub.1, Z.sub.2, Z.sub.3 and Z.sub.4 shown in
FIG. 4. The term "line segments" or simply "segments", refers to those
lines which extend individually in continuation, as indicated by reference
letters L.sub.1, L.sub.2 and L.sub.3 in FIG. 5, wherein the start terminal
point of each of the line segments L.sub.1, L.sub.2 and L.sub.3 is
designated by a reference letter S and represents one end point of a given
line segment, while the end terminal point designated by E represents the
other end point of the given line segment. The bending point represents a
bend on the line segment extending contiguously, such as the point
P.sub.11. Accordingly, it can be said that a closed line pattern is
composed of a single line segment having a start terminal point and an end
terminal point coinciding with each other at one and the same position and
a number of bending points, while a single broken line is composed of a
succession of small segments each having a start terminal point and an end
terminal point, some of the broken lines including additionally one or
more bending points. A typical one of the known characteristic point
extraction processings is disclosed in Kakumoto et al's article "Logic
Diagram Recognition by Divide and synthesize Method" appearing in
"Proceedings of the IFIP Working Conference organized by Working Group
5.2, Computer Aided Design", Grenoble France, March 17-19, 1978, pp.
457-470. The characteristic point extraction processing is assumed to be
executed by resorting to this known method according to which a scanning
circular arc of a predetermined radius is moved over line segments or
components in a line pattern image to detect the number of lines which
intersect the circular arc and the angles which the line segments form
with the circular arc. When the number of the line segments which
intersect the circular arc is found to be equal to 1 (one), it is
determined that the line segment in question has a start terminal point
and an end terminal point. On the other hand, provided that the number in
question is two and that the angle of intersection is greater than a
predetermined value, it is determined that the line segment as scanned has
at least one bending point. In this connection, it should be mentioned
that the terminal point which has first been detected in the
characteristic point extraction processing is referred to as the start
terminal point, while the last found one is referred to as the end
terminal point. In accordance with this characteristic point recognition
method as outlined above (for more particulars, reference may be made to
the above cited literature), position coordinates of the characteristic
points as well as the kinds or species of the characteristic points (i.e.
whether they are the start terminal point, the end terminal point or the
bending points) are recognized and extracted from the image data or line
pattern data illustrated in FIG. 5 for each of the line segments, whereby
the data of characteristic (feature) points is determined from the results
of the recognition processing and subsequently stored in the
characteristic point memory 5 (FIG. 1). An exemplary set of data resulting
from the characteristic point extraction processing mentioned above is
illustrated in FIG. 8 in which the characteristic point data for the line
segments L.sub.1, L.sub.2 and L.sub.3 shown in FIG. 5 are exemplified at
lefthand portions of respective storage areas. Referring to FIG. 8, the
first line for each line segment represents "number of segment
constituents or segment defining points" which means the number of the
characteristic points which take part in defining a single line segment.
In case of the line segment L.sub.1 shown in FIG. 5, the number of segment
constitutents is equal to two because this line is defined only by a start
terminal point (S) and an end terminal point (E). In case of the line
segment L.sub.2, the number of segment constituents equals 3, because this
line segment has a start terminal point (S), an end terminal point (E) and
a bending point (P). Further, a line kind (species) identifying number
entered in the registration table shown in FIG. 8 represents the kind or
species (sort) of the line in question, i.e. whether the line is a black
solid line, a black dash line or a black long dash line. The line kind
identifying number shown in the second line which also can be used to
discriminate the color of the line segment is determined through the
processing for recognizing the broken line species which will be described
hereinafter. In the table shown in FIG. 8, the number 0 (zero)
representative of the initial value is stored. The start point information
and the end point information tell whether these points (i.e. the start
terminal point and the end terminal point) are isolated in the drawing or
are depicted in solid circles or connected to other line segments. These
states of the terminal points are correspondingly represented by numerals
0, 2 and 3, respectively. In case of the line pattern or drawing shown in
FIG. 5, the terminal points of any line segments L.sub.1, L.sub.2 and
L.sub.3 are isolated and thus represented by 0 (zero), respectively, in
FIG. 8. In contrast, in the line pattern shown in FIG. 6 which is a
fragmental enlarged view showing a region defined by Z.sub.5, Z.sub.6,
Z.sub.7 and Z.sub.8, there is present a line segment L.sub.4 (overlap
symbol) having solid circles at the start terminal point S and the end
terminal point E, respectively. Accordingly, both the start point
information and the end point information for this line segment L.sub.4
(corresponding to the overlap symbol C shown in FIG. 3) assume the value
of 2, respectively. Recognition as to the presence or absence of the solid
circle at the terminal point is effected as a part of the processing for
extracting the characteristic points such as the start terminal point, the
end terminal point and the bending point immediately after these
characteristic points have been extracted. Here, a method of recognizing
the solid circle will be elucidated. FIG. 7 shows in a fragmental enlarged
schematic view a region defined by points Z.sub.9, Z.sub.10, Z.sub.11, and
Z.sub.12 in FIG. 6. The line segment L.sub.4 has been previously
recognized to be independent of the line segment L.sub.5 through the
processing for recognition of the characteristic points of the line
segment L.sub.5 because the line segment L.sub.4 intersects the latter
perpendicularly thereto. Referring to FIG. 7, it is assumed that the
characteristic point extraction processing for the line segment L.sub.4 is
effectd in the direction indicated by an arrow 100. In this processing,
the length l of a section of the line segment L.sub.4 is determined in
which the width W remains within a predetermined range:
WL<W<WH
where WL represents a predetermined minimum width and WH represents a
predetermind maximum width. Next, a section L is determined in which the
value of l lies within a range defined below:
LX-.epsilon.<l<LX+.epsilon.
where LX represents the center value of the range and .epsilon. represents
a parameter prescribing extension of the range. The starting line of this
section L is represented by L.sub.S -L.sub.S ' with the end line being
represented by L.sub.E -L.sub.E '. Further, the point at which the center
line intersects the start line L.sub.S -L.sub.S ' is represented by
K.sub.S while the point where the center line intersects the end line
L.sub.E -L.sub.E ' is represented by K.sub.E. Then, the center point
K.sub.C of the solid circle is given by the mid point of the line segment
interconnecting the intersections K.sub.S and K.sub.E. Around the center
point K.sub.C, the black area within the solid circle is radially scanned.
Subsequently, a flag indicative of the completed processing is set, and
the start point information or the end point information, as the case may
be, of the point corresponding to the center K.sub.C is set at the number
"2" which represents the presence of the solid circle. FIG. 9 shows data
of the characteristic points produced by the characteristic point
extraction processings for the line segments L.sub.4 and L.sub.5 shown in
FIG. 6. The start point information and the end point information of the
line segment L.sub.4 which is assumed to have solid circles at both ends
are set, respectively, to the value of 2. The characteristic point
extraction processing is repeated until all the line segments of a line or
image pattern which constitutes the object to be recognized have been
processed in the manner described above.
(2) Processing For Recognition Of Broken Lines
The broken line recognition processing is carried out on the basis of the
data stored in the characteristic point memory 5. A typical one of the
broken line recognition method is disclosed in U.S. patent application
Ser. No. 181,774 (Japanese Patent Application No. 11761/1979). At first, a
candidate for the broken line segment is extracted. The broken line is
recognized as a set of line segments which have respective terminal points
located adjacent to one another and each of which has a length within a
predetermined range. The individual segments constituting a broken line
are sequentially connected together to be recognized as a single broken
line (i.e. dash line, long dash line or chain line). The data of the start
terminal point, the end terminal point and the bending point which are
required for defining the line obtained as a result of the connection
processing are stored in the characteristic point memory 5 shown in FIG. 1
as the characteristic point data for the broken line in question in the
same format as those shown in FIGS. 8 and 9. The characteristic point data
for the solid lines are held intact as they are. In the broken line
recognition, the kinds or sorts (species) of the different broken lines
(e.g. dash line, long dash line, chain line and the like) are also
recognized. Thus, the line-kind-identifying numbers for the black solid
line, the black dash line and the black long dash line and the like are
set, respectively, at corresponding values of 1, 2, 3 and so forth to be
stored at the line kind identifying number storage areas. Through the
broken line recognition processing described above, the data for the solid
line P.sub.1 -P.sub.2 -P.sub.3 -P.sub.4 -P.sub.6 -P.sub.7 -P.sub.1, the
solid lines representing the center lines of the overlap symbols K.sub.1
and K.sub.2, the dash line P.sub.1 -P.sub.12 -P.sub.11 -P.sub.4 and the
long dash lines P.sub.7 -P.sub.8 -P.sub.9 -P.sub.10 -P.sub.5 are stored in
the characteristic point memory 5.
When the line path recognition processing has been completed, the
microprocessor I 40 sets a flag indicating the end of the recognition
processing in the register 90. The microprocessor II 60 shown in FIG. 2
reads out the content of the register 90 to check whether the line path
recognition processing executed by the microprocessor I 40 has been
completed. If so, the microprocessor II then executes the overlapping line
recognition processing program stored previously in the program memory II
60. The overlapping line recognition processing includes two
sub-processings: the overlap symbol recognition sub-processing and the
overlapping line path recognition sub-processing. In this overlapping line
recognition processing, the overlap symbols are discriminatively
recognized from the line data stored in the characteristic point memory 5.
After the recognition of the paths of the overlapping lines, the path
information or data is again stored in the characteristic point memory 5.
Data of those lines which have been recognized to represent the overlap
symbols are erased from the characteristic point memory 5. The overlap
symbol recognition sub-processing as well as the overlapping line path
recognition sub-processing will be described below in detail.
(3) Overlap Symbol Recognition Processing
FIG. 10 illustrates in a flow chart an example of the processing for
recognition of the overlap symbol. The line-kind-identifying number is
represented by C.sub.1 in such a manner that C.sub.1 =1 for a solid line
in black, C.sub.1 =2 for a dash line in black, C.sub.1 =3 for a long dash
line in black, C.sub.1 =4 for a solid line in red, C.sub.1 =5 for a dash
line in red, C.sub.1 =6 for a long dash line in red and so on, by way of
example.
In case C.sub.1 =1, the processing mentioned in the following is executed
for recognizing the solid line representative of the overlap symbol. Upon
completion thereof, the number of C.sub.1 is updated by three, which is
followed by repetition of the same processing. The reason for updating
C.sub.1 by three as mentioned above is because the overlap symbol is
constituted by a solid line and because the black lines are identified by
the serial numbers 1, 2 and 3 in dependence on the line kinds or species
(solid, dash or long dash), which is followed by the serial numbers 4, 5
and 6 representing the line kinds or species of the red lines in the same
manner and so forth. Assuming now that the drawing or line pattern which
is the object for recognition is drawn only in black, the processing is
executed for the case where C.sub.1 =1, since the line segment of the
overlap symbol is a solid line. At first, a number (M) of those lines
which are stored in the characteristic point memory 5 and assigned with
the line kind identifying number C.sub.1 (=1) are selected. Among the M
lines, the length l of the line of a registration number C.sub.2 (where
C.sub.2 =1, 2, . . . or M) is determined in terms of the coordinates of
the start terminal point, the end terminal point and the bending point. It
is then checked whether the length l falls within a predetermined range of
the length which the overlap symbol line is to have. In other words, it is
checked whether THL<l<THU, where THL represents a lower threshold value of
the line length, while THU represents an upper threshold value of the line
length. When the length l is out of the above range, the corresponding
line can not be a candidate for the overlap symbol. Accordingly, the
processing proceeds to the next line of a registration number C.sub.2 +1.
When the length l of this line of the registration number C.sub.2 +1 is
found to fall within the range defined above, all the lines stored in the
characteristic point memory 5 are checked as to whether there is a line
which intersects the above line C.sub.2 +1. In case no intersecting line
is found, the processing proceeds to the next line numbered C.sub.2 +2. On
the other hand, when the intersecting line is found to be present as is
the case with the example illustrated in FIG. 6, the angle .theta. formed
between the line C.sub.2 +1 and the intersecting line is determined.
Unless the value .theta. belongs to the range:
90.degree.-.alpha..ltoreq..theta..ltoreq.90.degree.+.alpha.
where .alpha. represents a parameter prescribing a permissible tolerance,
the intersecting line can not be a candidate for the overlap symbol line.
Accordingly, the processing proceeds to the next line of the registration
number C.sub.2 +2. On the other hand, when the angle .theta. lies within
the range defined above, the intersecting line is determined as the
overlap symbol line and subsequently checked as to whether the start and
the end point information thereof has been set to the value of "2" which
indicates the presence of the solid circle. When information of both the
start and end points of the intersecting line is found to correspond to
"2", the intersecting line is determined as the overlap symbol
representing an overlapping dash line which has been omitted from being
drawn. On the contrary, when information of both the start and the end
points are "0" (zero), it is determined that the intersecting line
represents the overlap symbol corresponding to an overlapping solid line.
The above processing is executed for M lines belonging to the line group
identified by the line kind number C.sub.1, which is followed by the
similar processings for the lines of the different
line-kind-identifying-numbers. The results of the overlap symbol
recognition processings mentioned above are stored in the work memory 14
shown in FIG. 2 at areas reserved for each of the overlapping line kinds
represented by the overlap symbols in a format shown in FIG. 11. This
format is referred to as the overlap symbol registration table. Referring
to FIG. 11, the number M.sub.i of the registered overlap symbols (where
i=1 to n and n is an integer) represents the number of the overlap symbols
having the corresponding line-kind-identifying numbers represented by
KI.sub.i among the detected overlap symbols. Data OF.sub.i, OFS.sub.i and
(X.sub.i, Y.sub.i) are stored as a unit record or set for every detected
overlap symbol, among which OF.sub.i designates the location in the memory
5 where the characteristic point information or data of the line
intersected by the overlap symbol is stored. For example, the data
OF.sub.i for the line L.sub.5 which is intersected by the overlap symbol
L.sub.4 (refer to FIG. 6) designates the heading or leading position
(address) of the area at which the characteristic point data of the line
L.sub.5 is stored or registered in the characteristic point memory 5. Data
OFS.sub.i and OFE.sub.i for the storage positions of the start and end
terminal points, respectively, of a segment actually intersected by an
overlap symbol designate, respectively, the locations of the memory 5
where the coordinates of the two characteristic points (given two of the
bending point(s), the start point and the end point) of said segment which
are located, respectively, toward the start and end terminal points of the
line incorporating said segment are stored. In this connection, it is to
be noted that the locations at which the start and end positions of the
segment intersected by the overlap symbol are given in terms of difference
in address from the location OF.sub.i at which the chatacteristic point
data of the line to which said segment belongs is stored. By way of
example, referring to FIG. 6, OFS.sub.i designates the location in the
memory 5 at which the coordinates of the bending point P.sub.2 located at
one end of a segment P.sub.2 -P.sub.3 constituting an integral part of the
line L.sub.5 and intersected by the overlap symbol L.sub.4 are stored,
while OFE.sub.i designates the location in the memory 5 at which the
coordinates of the bending point P.sub. 3 coinciding with the other end of
the same segment are stored. The position coordinates (X.sub.i ; Y.sub.i)
of the overlap symbol represent the coordinates of the cross-point
{(P.sub.X ; P.sub.Y) in the case of the illustration of FIG. 6} at which
the overlap symbol (L.sub.4) intersects the line (L.sub.5).
The position (coordinates) of the cross-point or intersection is
arithmetically determined on the basis of the coordinates of the bending
points P.sub.2 and P.sub.3 and the coordinates of the start and end points
of the overlap symbol. In this way, the overlap symbols K.sub.1 and
K.sub.2 (refer to FIG. 4) are recognized, whereby the overlap symbol
registration table is prepared in the manner illustrated in FIG. 11.
(4) Overlapping Line Path Recognition Processing
FIG. 12 is a chart showing a general flow of the overlapping line path
recognition processing. Referring to the figure, it is assumed that
C.sub.3 represents the line-kind-identifying number KI.sub.i corresponding
to the overlap symbols registered in the overlap symbol registration table
shown in FIG. 11. By way of example, this line-kind-identifying number
KI.sub.i is set to 1, 2, 3, 4 and 5 for the overlap symbols which
correspond to the black solid line, the black dash line, the black long
dash line, the red solid line and the red dash line, respectively. At
first, a number (M.sub.i) of the registered overlap symbols which have the
line-kind-identifying numbers KI.sub.i equal to C.sub.3 are detected from
the overlap symbol registration table (FIG. 11). When the number of the
record relating to the overlap symbols assigned with the
line-kind-identifying number KI.sub.i in the overlap symbol registration
table is represented by C.sub.4, the processing mentioned below is
repeated until C.sub.4 becomes equal to M.sub.i. However, those overlap
symbols whi | | |
