JP3328395B2 - Pattern identification device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a pattern identification apparatus for adjusting a fee by recognizing tableware patterns in a cafeteria settlement system, and more particularly to a pattern identification apparatus in which an input image is a pattern in which a plurality of figures are superimposed. The present invention relates to a pattern identification device that detects omission of recognition, does not have erroneous recognition, and performs more flexible recognition processing on an input pattern.

Here, a dining room settlement system is a system in which a variety of dishes or single dishes are placed on a tray in a dining room, a tableware image including overlaps and protrusions is input to a camera, and image processing is performed. This is a system that calculates the settlement amount by comparing the size with the price of tableware that has been certified in advance. In such a cafeteria settlement system, it is required that the tableware image be accurately and quickly separated and identified.

[0003]

2. Description of the Related Art As a method of recognizing a figure, a method of performing image processing on an entire input image to extract features and identifying feature data by pattern matching, or extracting an outline and identifying it from the features of the outline There is a method to do. Japanese Patent Application Laid-Open No. H04-290174 discloses one method of performing pattern separation and identification using a contour line.

Japanese Patent Application Laid-Open No. H04-290174 discloses FIG.
A binary input image as shown in FIG. 1A is subjected to a labeling process for numbering independent images (FIG. 1).
2 (b)), the coordinates of the contour points are extracted for each image, and the contour points are traced at regular intervals to separate the contour of a basic figure such as a circle or a rectangle from the change of the contour. I do. Even in a pattern in which the basic figures are in contact with each other based on the types and positional relationships of the separated contour lines, the basic figures such as circles and squares can be identified and measured.

The manner in which separation and identification are performed in a composite pattern in which basic figures overlap will be described with reference to FIG. Any point P in the contour data of the input pattern
A sampling vector i is created at a point on the contour line separated by a predetermined distance from 0. Similarly, a vector j is obtained,
A rotation direction composed of two vectors i and j (FIG. 13 (b
Trace the contour while monitoring the angle accompanied by-).

Here, since the angle formed by the vectors k and 1 has a rotation direction of (+) (see FIG. 13B-B), it is known that the angle is a contact point of the figure, and the contour line is bordered by the point P1. Is separated.

In the vectors q and r, the direction of rotation of the angle is the same as that of the other parts (-) (see FIG. 13 (b)), but since the angle is extremely changed, this angle is changed. Are determined to be the vertices of a polygon, and the outline is separated at the point P5.

[0008] Here, a point separating the contour is referred to as a bending point, and a contour between the bending points is referred to as a partial contour transition. In FIG. 7A, the partial contours separated by the above method are L1,
L2. L3, L4, L5, L6.

Next, if it is determined whether or not the partial contour is an arc based on angles formed by vectors created by points sampled at the same interval, L1 and L4 are arcs,
Since L2, L3, L5, and L6 are identified as straight lines, the contour of the arc approximates a circle by the least squares method from the contour point data, and the angle of the straight contour is 90 degrees with the straight line facing it.
After conducting a survey such as [°], the quadrangle is identified.

As described above, even in the case of a composite pattern, a circle and a rectangle can be quickly and accurately separated and identified.

[0011]

In a dining room settlement system, which is an application example of the pattern identification device, in order to reduce restrictions on how to place the tableware as much as possible, the tableware comes into contact with the pattern in which the input image overlaps a plurality of figures. Even so, a function for separating and identifying individual figures by analyzing the contour lines is required.

However, in the conventional pattern identification apparatus, a figure surrounded as shown in FIG. 14 is not recognized because of lack of outline information, and only the surrounding figure is recognized. Therefore, there has been a problem that it is necessary to set restrictions on the contact state of tableware.

The present invention solves the above problems,
Even if the input image is a pattern in which multiple figures are superimposed,
By analyzing contours, individual figures are separated and identified, recognition omission is detected from the relative positional relationship of the separated and identified figures, and there is no erroneous recognition and more flexible recognition processing can be performed on the input pattern. It is an object to provide a pattern identification device.

[0014]

FIG. 1 is a diagram illustrating the principle of the present invention. In order to solve the above problem, a pattern identification apparatus of the first aspect of the present invention, as shown in FIG. 1, in one pattern in which a plurality of figures are overlapped, the pattern
Separation and identification means (1) for separating and identifying the figure from the change of the outline, and separation and identification by the separation and identification means (1).
A position monitor which monitors the relative positional relationship of the identified said figure (2), before the determined by the position detection means (2)
The fraction from the serial relative positional relation in the interior of the one pattern
There are other figures that cannot be separated and identified by the separation identification means (1)
Space constituting and a space identification means (3) determine whether there is to be.

According to a second aspect of the present invention, there is provided a pattern identifying apparatus according to the first aspect.
When the center coordinates of the separated and identified figures are connected by a straight line, the position grasping means 2 determines a figure adjacent to each figure so as to form a polygon having the straight line as a side.

According to a third aspect of the present invention, there is provided a pattern identifying apparatus according to the first or second aspect, wherein the space identifying means 3 sets a center coordinate of the separated and identified figure as a vertex. Of the polygon to be separated, the separation identification hand is placed inside the one of the diagonal lines of the polygon.
Space where other figures that cannot be separated and identified in step (1) exist
A diagonal line selecting means 4 for selecting a diagonal line effective for appropriately examining whether or not there is a rectangle, and, if the polygon is a pentagon or more, a rectangle for cutting out an appropriate rectangle from the polygon to investigate the interior It is assumed that there is a space in which image data of an unidentified graphic exists inside the pattern to be superimposed from the distance between the graphic at the start point and the end point of the effective diagonal line. I do.

According to a fourth aspect of the present invention, there is provided a pattern identifying apparatus according to the third aspect of the present invention.
The diagonal line selecting means 4 invalidates a diagonal line of a polygon having the vertex of the center coordinate of the separated and identified graphic, which crosses the recognized graphic, and validates only a diagonal that passes near the center of the internal space. Make a selection.

According to a fifth aspect of the present invention, there is provided a pattern identifying apparatus according to the third or fourth aspect, wherein the rectangular cutout means 5 is adapted to detect an overlapping pattern.
Others that cannot be separated and identified internally by the separation and identification means (1)
When investigating the existence of the space where the figure exists , a diagonal line is cut out from the polygon to a rectangle passing through the center of the polygon, and when the distance between the figures forming the starting point and the end point of the diagonal line is equal to or more than a predetermined length, It is determined that there is a space where the unrecognized figure exists.

Further, a pattern identification apparatus according to a sixth aspect of the present invention is the pattern identification apparatus according to any one of claims 3, 4 and 5, wherein the space identification means 3 is provided with a center coordinate of the separated and identified figure. The intersection of the diagonal lines of the rectangle cut out from the polygon having the apex as the vertex, or the center between figures on the side when the side of the rectangle is a valid diagonal line, is defined as the inspection point of the internal space, Identify the presence or absence of

[0020]

According to a first aspect of the present invention, there is provided a pattern identifying apparatus comprising:
As shown in FIG. 1, in one pattern in which a plurality of figures are superimposed on each other,
From a change in the line, the respective graphic separation, identification, and isolation, grasped by the identified locating means 2 relative positional relationship of the figure, from the relative positional relationship obtained in said one pattern
Can be separated and identified by the separation and identification means (1).
The space identification means 3 checks whether or not there is a space in which there is no other figure .

Further, in the pattern identification device according to the second aspect of the present invention, when the center coordinates of the separated and identified figures are connected by a straight line, the position grasping means 2 forms a polygon having the straight line as a side. Next, a figure adjacent to each figure is determined. For example, in the case where the recognized pattern is as shown in FIG. 2A, the center points D1, D
A square having the vertices 2, 2, and D4 is formed.

In the pattern identification apparatus according to the third aspect of the present invention, the diagonal line selection means 4 uses the diagonal line selection means 4 for the polygon having the vertex at the center coordinate of the figure separated and identified by the space identification means 3. One of the polygon diagonal lines
Separation and identification within the turn by the separation and identification means (1)
A diagonal line effective for appropriately examining whether or not there is a space in which another figure cannot exist is selected. If the polygon is a pentagon or more, a quadrangular cutout means 5 is used to examine the interior. It is assumed that an appropriate quadrangle is cut out from the polygon, and from the distance of the graphic at the start and end points of the effective diagonal, if there is a space where the image data of the unidentified graphic exists inside the pattern to be superimposed. I try to guess.

In the pattern identification apparatus according to the fourth aspect of the present invention, the diagonal line selection means 4 intersects the recognized figure with a polygonal diagonal whose vertex is the center coordinate of the separated and identified figure. The object is selected as invalid and only those passing near the center of the internal space are valid. For example, in the case of FIG. 3A, the figure C3 is shifted from the center D1 of the figure C1.
When the diagonal line L13 is drawn at the center D3, the diagonal line L13 passes through the graphic C2, and is invalidated. As a result, valid diagonals L14, L24 and L25 are selected.

[0024] In the fifth pattern identification apparatus aspect of the present invention, a square cutting means 5, of the patterns to be superimposed
Other parts that cannot be separated and identified by the separation and identification means (1).
When investigating the existence of a space where a figure exists, a rectangle whose diagonal line passes through the center of the polygon is cut out from the polygon, and when the distance between the figures forming the starting point and the end point of the diagonal line is a predetermined length or more, It is determined that there is a space in which an unrecognized figure exists.

Further, in the pattern identification device according to the sixth aspect of the present invention, the space identification means 3 includes an intersection of diagonal lines of a quadrangle cut out from a polygon having the center coordinates of the separated and identified figure as vertices, or When the side of the square is a valid diagonal, the center between the figures on the side is set as the inspection point of the internal space, and the presence or absence of the internal space is identified. For example, in the case of FIG. 3B, a square D1-D2-D4-D5 is cut out and an intersection P1 of diagonal lines L14 and L25 of the square is cut out.
Is used as an inspection point, the presence of an object outside the figure recognized by detecting image data of the coordinates is identified.
In addition, when the side of the quadrangle is a valid diagonal, the center P2 between the figures on the side is also used as an inspection point to efficiently recognize the presence or absence of the internal figure.

In order to check the existence of a figure which is surrounded and not recognized, first, it is necessary to check by means of the position grasping means 2 what kind of positional relationship the recognized figures are arranged. This situation will be described with reference to FIGS.

When a figure as shown in FIG. 4A is recognized, first, from the center D1 of the figure C1, the other figures C2, C3,
Lines (L12, L13, L14, L15) are drawn toward the centers D2, D3, D4, D5 of C4, C5. Next, similarly, as shown in FIG.
To the center of another figure from (L23, L24.L25)
pull. Here, L2 intersecting with the line drawn from the graphic C1
4, L25 is invalid and L23 is valid.

The same processing is performed on the figures C3, C4, and C5, and those that intersect with the line from the figure C1 are invalidated. L1 which sometimes intersected by a line from figure C1
3, L14 is also invalidated. The positional relationship between the figures recognized as described above can be recognized as a polygon in which the sides do not intersect regardless of the distance (FIG. 5).
(A)). When there is no other figure inside the figure C1 to C5, the number of effective lines coming from the centers D1 to D5 of each figure is two.

As shown in FIG. 5B, when there is a figure C6 inside the figure C1 to C5, the figures C4 and C5
Are three effective lines from the centers D4 and D5, respectively, and the figure C6 is a polygon D1-D2-D3-D4-D
It can be seen that it is inside 5. In this way, when determining the existence of the internal space, an appropriate determination can be made by considering the number of effective lines coming out of the center of each figure.

Next, a description will be given of how the space identifying means 3 checks whether or not there is a space in which a not-recognized figure can be entered, based on the arrangement state of the recognized figures, with reference to FIG.

FIG. 6A shows the positional relationship between the recognized figures.
As shown in FIG. 6, when the figure is a pentagon having the vertexes at the center coordinates (D1, D2, D3, D4, D5) of the figures C1, C2, C3, C4, C5, a diagonal line as shown in FIG. L13, L14, L24. L25. L35 is subtracted.

At this time, a diagonal passing through another figure is invalid because it does not pass near the center of the internal space to be evaluated. For example, in FIG. 6B, when a diagonal line L13 is drawn from the vertices D1 to D3, the diagonal line L13 passes through the graphic C2, and is invalidated. Similarly, when an effective diagonal line is obtained, L14, L24, L25, and L35 are selected.

Here, in order to detect recognition omission, an intersection of valid diagonal lines is set as a test point. However, in the case of a pentagon or more, since the intersection of the diagonal lines does not always indicate the vicinity of the center (for example, the intersection of L14 and L35), the rectangle is cut out,
It is more efficient to check the intersection of the diagonal lines. Therefore, among the effective diagonal lines, the diagonal line having the shortest length outside the figure is set as one side of the square (L24 is selected in FIG. 6B).

The square D1-D2- obtained in this way
If the intersection point P1 of the diagonal lines L14 and L25 of D4 to D5 is used as an inspection point and image data is detected at the coordinates, it is possible to know the presence of an object in addition to the recognized figure, and to notify the omission of recognition. .

When the diagonal line is one side of the rectangle and the distance between the diagonal figures (L in FIG. 6B at L24) is longer than a predetermined distance, the center P2 between the figures is also used as the inspection point. This makes it possible to efficiently recognize the presence or absence of an internal graphic.

According to the present invention, for example, in a cafeteria payment system for performing payment of a dish selected according to the shape of the tableware, there is conventionally a possibility that mis-payment may occur depending on how the tableware is placed. However, in the present invention, by adding a function of checking the presence of a figure that has not been recognized, the restriction can be relaxed, and more flexible recognition and settlement processing can be realized.

[0037]

Next, an embodiment according to the present invention will be described with reference to the drawings. FIG. 7 shows a configuration diagram of a pattern identification device according to one embodiment of the present invention. This embodiment is described in
This is an improvement of the function of the pattern recognition method disclosed in No. 74.

The pattern identification apparatus of this embodiment has a mechanism in which the shape of the pattern 11 to be inspected is contrasted by the illumination device 12 and is picked up by the image input device 13 and converted into a video signal. An image processing device 14 for processing the output of the image input device 13 to create digital image data; an input image memory 15 for storing processed image data; and a CPU 16 for executing processing or recognition of the input image data. A recognition processing work memory 17 for separating and identifying a figure from input image data and measuring the size and center coordinates of each figure, a recognition result storage memory 18, and a position for storing positional relationship information of the recognized figure. A relation storage memory 19, a diagonal information storage memory 20 for storing diagonal numbers and coordinates recognized for inspecting the inside from the positional relationship, and coordinates for inspecting the presence or absence of a figure that has not been recognized. An inspection point storage memory 21 and a display device 22 for displaying a recognition result and the like are provided.

Next, the operation of the pattern identification apparatus of this embodiment will be described with reference to the flowchart shown in FIG.
When the input pattern as shown in FIG. 9 is image-processed, all the figures are in contact with each other, and are registered as one individual. When this is recognized by the contour tracing method, the figure F is surrounded by another figure, so that the outline information becomes very small, and the figure F is excluded from the recognition target. , C, D, and E (step S1 in FIG. 8).

Here, if there are three or less figures separated and identified from the same individual, there is no possibility of recognition omission, and the process ends normally. If there are four or more figures, the recognition omission inspection is performed (see FIG. 8). Step S2).

As shown in FIG. 10, with respect to the recognized pattern, a figure as a reference for obtaining the positional relationship of the figure is selected (FIG. 10, FIG. 10A). Lines Lab, Lac, Lad, Lae at center coordinates
pull. Next, lines Lbc, Lbd, and Lbe are drawn in a similar manner from the graphic B except the graphic A. At this time,
Since the line Lbd intersects with the line Lac from the figure A, and the line Lbe intersects with the lines Lac and Lad, it is determined to be inappropriate as one side of the polygon and becomes invalid, and only the line Lbc is stored in the positional relationship storage memory 19. Store.

The lines Lac and Lad from the figure A which are found to intersect are given the information and are left for evaluation of the lines from the next figure. Similarly, figures C,
When evaluated for D and E, the effective line is Lcd, L
de, and finally, Lab and Lae that do not intersect with the line from the graphic A are registered. With this method, it is possible to create a polygon having the center coordinates of the recognized figure as vertices and without intersecting each other (step S3 in FIG. 8).

Next, each of the figures A, B, C, D, and E in FIG.
Polygon oa-ob-oc-od whose center is the vertex of
Evaluate the diagonal line of -oe and select a diagonal line that passes near the center of the space where the unrecognized figure enters inside the polygon. Diagonal lines Tac, Tad, Tbd, Tb
In e and Tce, those that pass the recognized figure are invalid because they do not pass near the center of the internal space.
Effective diagonal lines are Tac, Tbd, Tbe, and Tce, and these are stored in the diagonal line information storage memory 20 (FIG. 8).
Middle, step S4).

In order to inspect the interior space of the polygon, the intersection of the diagonal lines is used. If the obtained polygon is a pentagon or more, even if it is a valid diagonal, the intersection of the diagonal lines does not necessarily define the interior space of the interior space. In this case, a quadrangle in which the intersection of the diagonal lines indicates the vicinity of the center is cut out. Therefore, the shortest length of the effective diagonal lines is defined as one side of the square. Therefore, in FIG. 11, since the pentagon is also a pentagon, the diagonal Tce is the shortest of the effective diagonals, and thus a quadrangle oa-ob-oc-o having this as one side is shown.
e is determined (step S6 in FIG. 8).

Here, since the diagonal selected as one side of the rectangle passes through the inside of the polygon, if the distance between the figures formed by the starting point and the ending point of the diagonal is longer than a predetermined length, it is also drawn on this straight line. Since there is a possibility that an unrecognizable figure may exist, not only the intersection P1 of the diagonal line in the cut-out rectangle but also the appropriate coordinates (for example, the center) P2 between the figures at both ends on this side (Tce) are inspected. Is registered in the test point storage memory 21 to improve the detection rate of recognition omission (step S7 in FIG. 8).

Finally, the intersection P of the determined diagonal of the rectangle
The coordinates are stored in the inspection point storage memory 21 with 1 as an inspection point (step S8 in FIG. 8). At the coordinates of the image data indicated by the inspection points P1 and P2 obtained in this way, the presence or absence of image data with the same identification number as the recognized figure is checked (step S9 in FIG. 8).

If image data exists at the test points P1 and P2, it is determined that there is an individual that has not been recognized, so that recognition omission is notified via the display device 22 (FIG. 8).
Middle, step S10). If there is no image data, the pattern identification processing ends normally.

As described above, according to the pattern identification device of this embodiment, when the number of figures recognized from the superimposed pattern is four or more, they may surround other figures. Examine the positional relationship between the recognized figures, and if it is determined that there is a space inside which other figures can enter, check the image data of an appropriate part of the internal space to detect recognition omissions and detect false recognition. It is intended to prevent the recognition processing from being completed normally, and a pattern identification device capable of more flexible pattern recognition for an input pattern can be realized.

[0049]

As described above, according to the present invention,
Separation / identification means separates and identifies each figure of the pattern in which a plurality of figures are superimposed, grasps the relative positional relationship of the separated and identified figures by position grasping means, and determines the pattern to be superimposed based on the obtained relative positional relationship. Since it is decided to check whether there is a space inside by the space identification means, it is possible to check the existence of unrecognized figures, relax restrictions on contact with objects, and more flexible recognition processing Can be provided.

In the space discriminating means, for the polygon having the vertex at the center coordinate of the separated and identified figure, the diagonal line selecting means appropriately examines the inside of the overlapping pattern among the diagonal lines of the polygon. Select a valid diagonal line, and if the polygon is a pentagon or more, cut out an appropriate quadrangle from the polygon to examine the interior by quadrangular cutting means, and start the valid diagonal line. From the distance of the figure at the end point, it is assumed that there is a space in which the image data of the figure that has not been identified exists inside the pattern to be superimposed. A possible pattern identification device can be provided.

[Brief description of the drawings]

FIG. 1 is a diagram illustrating the principle of the present invention.

FIGS. 2A and 2B are explanatory diagrams of the operation of the present invention. FIG. 2A is a diagram showing a recognized pattern, and FIG. 2B is a diagram showing a positional relationship between figures.

3A and 3B are diagrams illustrating the operation of the present invention, in which FIG. 3A is a diagram illustrating a process of selecting a valid diagonal, and FIG. 3B is a diagram illustrating a process of determining a check point of recognition omission; .

FIGS. 4A and 4B are explanatory diagrams of the operation of the position grasping means of the present invention, and FIGS. 4A and 4B are explanatory diagrams of a process for determining the sides of the polygon.

5A and 5B are explanatory diagrams of the operation of the position grasping means of the present invention. FIG. 5A is an explanatory diagram of a determined polygon, and FIG. 5B is an explanatory diagram of a polygon when a figure is included therein. It is.

6 (a) is an explanatory view of a determined polygon, and FIG. 6 (b) is an explanatory view of a cut-out square and an inspection point. is there.

FIG. 7 is a configuration diagram of a pattern identification device according to an embodiment of the present invention.

FIG. 8 is a flowchart illustrating a pattern identification process of the pattern identification device according to the embodiment.

FIG. 9 is an operation explanatory diagram (input pattern) of the pattern identification device of the embodiment.

FIG. 10 is an operation explanatory diagram (determination of a positional relationship) of the pattern identification device of the embodiment.

FIG. 11 is an explanatory diagram (determination of inspection points) of the operation of the pattern identification apparatus of the embodiment.

12A and 12B are explanatory diagrams of a conventional pattern identification method. FIG. 12A is an explanatory diagram of an input image, and FIG. 12B is an explanatory diagram of a labeling process.

FIG. 13A is an explanatory diagram of a conventional separation and identification process, and FIG. 13B is an explanatory diagram of a rotation direction.

FIG. 14 is a diagram illustrating a pattern that causes recognition omission, which is a conventional problem.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 ... Separation identification means 2 ... Position grasping means 3 ... Space identification means 4 ... Diagonal line selection means 5 ... Square extraction means 11 ... Input pattern 12 ... Illumination 13 ... Image input device 14 ... Image processing device 15 ... Input image memory 16 ... CPU 17: Recognition processing memory 18: Recognition result storage memory 19: Positional relationship storage memory 20: Diagonal information storage memory 21: Inspection point storage memory 22: Display device A, B, C, D, E, F: In recognition pattern Figures C1 to C6 ... figures in recognition pattern D1 to D6 ... centers of figures L12 to L56 ... diagonal lines Lab to Lbe ... diagonal lines P1, P2 ... inspection points S1 to S11 ... processing steps Tac, Tbe, Tbd, Tce, Tad ... diagonal lines oa ~ Oe ... the center of the figure

Claims (6)

(57) [Claims] 1. A single pattern in which a plurality of figures are superimposed
Oite, from a change in the outline of the pattern, separating the figures, and identifies the separation identification means (1), by the separation identification means (1) was separated and identified in FIG <br/> shaped relative a position monitor which monitors the positional relationship (2), the separation identification means from the relative positional relationship obtained by said position detection means (2) within said one pattern
A space identification unit (3) for checking whether there is a space in which there is another figure that cannot be separated and identified in (1), and a pattern identification device characterized by separating and identifying a plurality of figures. . 2. When the center coordinates of the separated and identified figures are connected by a straight line, the position grasping means (2) is adjacent to each figure so as to form a polygon having the straight line as a side. The pattern identification apparatus according to claim 1, wherein the pattern is determined. 3. The space discriminating means (3) includes, for a polygon whose vertex is the center coordinate of the separated and identified figure , a front portion of the diagonal line of the polygon inside the one pattern.
Other figures that cannot be separated and identified by the separation and identification means (1)
A diagonal line selecting means (4) for selecting a diagonal line effective for appropriately examining whether or not there is an existing space; and, when the polygon is a pentagon or more, a diagonal line from the polygon to investigate the interior. Square cutting means (5) for cutting out an appropriate square
And estimating, from the distances of the figures at the start and end points of the effective diagonal line, that there is a space in which image data of an unidentified figure exists inside the pattern to be superimposed. The pattern identification device according to claim 1. 4. The diagonal line selection means (4) invalidates a diagonal of a polygon having a vertex at the center coordinates of the separated and identified graphic and intersecting with the recognized graphic, and invalidates the diagonal. 4. The pattern identification apparatus according to claim 3, wherein the selection is performed by validating only a nearby object. 5. The rectangular cutout means (5) separates and identifies the inside of a pattern to be overlapped by the separation and identification means (1).
When investigating the existence of a space where there are other shapes that cannot be
A rectangle whose diagonal passes through the center of the polygon is cut out from the polygon, and when the distance between the starting and ending points of the diagonal is greater than or equal to a predetermined length, there is a space where an unrecognized figure exists. 4. The method according to claim 3, wherein
Or the pattern identification device according to 4. 6. The space discriminating means (3) is an intersection of a diagonal of a rectangle cut out from a polygon having a vertex at the center coordinate of the separated and identified figure, or a side of the rectangle is a valid diagonal. 6. The pattern identification apparatus according to claim 3, wherein a center between the figures on the side in the case is set as an inspection point of the internal space, and the presence or absence of the internal space is identified.