JPH0130181B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Technical field to which the invention pertains] The present invention relates to a pattern analysis processing device that analyzes inclusion relationships between general figures. Generally, it is desirable for this type of device to be able to analyze inclusion relationships of arbitrary figures at high speed.

[Prior art and its problems]

As an image processing device that handles this type of general figure, there is, for example, a multiple pattern processing device that the present applicant has already proposed (for example, Japanese Patent Application No.
(Refer to No. 109746), this is not limited to breaking down a predetermined pattern into line segments (a set of black dots on a horizontal scanning line, that is, a set of points representing a pattern; also simply called a segment or run) and analyzing their connectivity. Therefore, it is impossible to know the inclusion relationship. In other words, when we look at a set of connected segments (also called multiple pieces or blobs) as a figure, we cannot know the number of holes contained in it, and cannot identify other blobs contained in the . For example, Fig. 1 is an explanatory diagram for explaining the inclusion relationship of blobs, and Fig. 1A shows a case where blob a includes blob b, and Fig. 1B shows a case where blob a does not. The device has a drawback in that it cannot determine such an inclusion relationship.

[Purpose of the invention]

Therefore, it is an object of the present invention to provide a pattern analysis processing device that can easily and quickly analyze the inclusion relationships of such patterns.

[Key points of the invention]

Each of the multiple inspection target patterns is regarded as an island floating in the sea, and these are raster scanned and binarized to extract island information such as island segment information, and for the sea, by reversing the logic, sea segment information is extracted. By extracting sea information such as information, and analyzing the connectivity of these extracted island and sea information, it is classified into a predetermined number of island and sea patterns, and this is expressed in a hierarchical structure of islands and seas. This makes it possible to analyze the inclusion relationship of each pattern.

[Embodiments of the invention]

Fig. 2 is a configuration diagram showing an embodiment of this invention;
The figure is an explanatory diagram explaining general segment information,
FIG. 4 is an explanatory diagram illustrating island, sea/lake segment information, and FIG. 5 is an explanatory diagram illustrating various extracted image information of FIG. 4 written into the image memory. In FIG. 2, reference numeral 11 indicates a screen to be processed. Here, assuming that the background is the sea S, the pattern such as a figure is understood as an island I floating in the sea S. In addition, since L indicates a lake and is synonymous with the sea, it is simply expressed as the sea, sea or lake, or sea/lake. 12 is an imaging device such as a solid-state imaging camera;
3 is a binarization circuit, 14 is an inversion circuit, 15 is an island segment information extraction circuit, 16 is an island segment connection pair information extraction circuit, 17 is an island segment surrounding pair information extraction circuit, 18 is an island information image memory, and 19 is a sea・Lake segment information extraction circuit, 20 is a sea/lake segment connection information extraction circuit, 21 is a sea/lake segment surrounding information extraction circuit, 22 is a sea/lake information image memory, and 23 is a data processing device such as a microprocessor. , 24 is read-only memory (ROM), 2
5 is a random access memory (RAM), 26 is an input/output interface circuit, and 27 is a system bus.

That is, the target screen is scanned horizontally in the X direction using the imaging device 12 and sequentially scanned in the Y (vertical) direction, and the video signal obtained by each horizontal scan is converted into a binarization circuit 13. If the data is sequentially binarized at the threshold level, the result will be as shown in FIG.
Note that, in order to make the explanation easier to understand, FIG. 3 is an example in which a simple character "W" is imaged, and therefore the pattern is different from the pattern shown on the screen 11 of FIG. 2. Here, if the location where a pattern (island) exists is represented by, for example, a logic "1", and a series of logic level "1"s is called a segment, then each pattern corresponds to each horizontal scanning line (SC) as shown in the figure. ₈ , _SC9 ... _SCi ... _SCk ...), and therefore each pattern can be represented by a group of these segments. In order to identify that these segments belong to the same pattern, it is necessary to compare the coordinates of each segment. For example, if the currently scanned scan line is SC ₉
In order to determine that segment SE ₉₁ of current scan SC ₉ belongs to the same pattern as segment SE ₈₁ of SC ₈ , which is the previous scan line, it _is necessary to The Y coordinates of the segments of SC ₈ differ by 1, and the segments
The X coordinates of SE ₈₁ and SE ₉₁ even partially overlap. Therefore, in order to clearly understand these relationships, we will consider a start segment and a joint segment for each segment. In other words, start information is attached to a segment that does not overlap with _any segment in the previous _scan , that is, a segment that appears for the first time in the current scan _.
That is it. Furthermore, the joint segment indicates the degree to which segments overlap, and indicates that two or more segments on the previous scanning line are connected to each other. For example, SE _k+1 in the figure corresponds to this. Each segment connected to the start segment is assigned the same single piece numbers 1, 2, and 3 as those given to the start segments SE ₈₁ , SE ₈₂ , and SE _ij as belonging to the same single piece.
Note that the subsequent segment SE k+ ₂ connected by a joint segment, for example SE _k+1 ...
is assigned the same single piece number as that assigned to SE _ij , SE _k2, etc., as belonging to the single piece on the right side.

The above is an explanation of the segment that represents the pattern, that is, the island segment. However, since islands and the sea (lake) are two sides of the same coin, if we reverse that logic, we can find the same relationship as above for the sea. Therefore, we can consider ocean/lake segments, ocean/lake single pieces, etc. FIG. 4 is for explaining various types of image information when considered in this way.

In other words, if we take a predetermined area PE for the image processing area PP and define it as the sea (SEA) area,
The pattern to be processed can be understood as an island existing in this sea (ISLAND), and if there are further islands within this island, the part that separates them can also be understood as an ocean or a lake (LAKE). can. The meanings of the symbols in FIG. 4 are as follows.

B. S indicates the start segment, the subscripts I and L distinguish between islands and oceans, and the numbers indicate the order in which they occur. Therefore, the start segments of the island are S _I to S _I , and the start segments of the sea are S _L1 and S _L2 .

B. J is a joint segment, and subscripts I,
The letter L distinguishes between islands and the sea, and the numbers indicate the order in which they occur. Therefore, the island joint segments are J _I1 to J _I3 , and the sea joint segments are J _L1 to J _L3 .

C. I indicates the island single piece to which the same number is attached, and the subscript represents the island single piece number. I _S1 to I _S4 correspond to this.

D.L is a sea piece belonging to the same number, and its subscript represents the sea piece number. L _S1 to L _S3 correspond to this.

The island or sea segment information and segment number as described above are extracted by the island segment information extraction circuit 15 and the sea/lake segment information circuit 19 shown in FIG. 2, respectively. Note that the inverting circuit 14 is provided to extract various information focused on the background ocean, as described above. In addition, the above-mentioned island and sea segment information includes the X and Y coordinates of the segment, its length (segment length), and single piece number (number indicating which single piece it belongs to).
This includes:

Furthermore, in the present invention, not only the segment information and single piece number information as described above, but also the following concatenated pair information and enclosing pair information are extracted. In other words, the connected pair information is information that indicates which single piece is connected to which single piece, that is, the degree of connection, and the surrounding pair information is used to grasp the single pieces on both sides of the single piece of interest. It is information. Referring to FIG. 4, the single island pieces I _S2 and I _S3 are connected at the joint segment J _I1 , and the single island pieces I _S2 and I _S4 are connected at the joint segment J _I2 . Since it is known, these are considered as island connection pair information.Similarly, sea single pieces L _S1 and L _S2 are in joint segment J L1, and sea single pieces L _S2 and L _S1 are in joint segment J _L1 . Since they are connected at intra-segment J _L2 , these are considered as sea connection pair information. Note that, as is clear from the above, the link pair information can be obtained based on joint segments. On the other hand, surrounding pair information is obtained by focusing on the start segment. For example, if we focus on the island start segment S _I1 , its neighbors on both sides are sea segments L _S1 , and if we focus on the sea segment L _S2 , then Since both sides are island segments I _S1 , these relationships are used as island encirclement information and sea encirclement information, respectively.

These island and sea connection pair information are extracted by extraction circuits 16 and 20 shown in FIG. 2, respectively, and
The island and sea encirclement pair information is extracted by extraction circuits 17 and 21, respectively. Note that image information regarding these islands and the sea is stored in the island information memory 18 and the sea information memory 22, respectively. Figure 5 explains the stored contents of these memories.
D shows island and sea segment information, B and E show island and sea connection pair information, and C and F show island and sea encirclement pair information, respectively. In addition, in the same figure,
X _IE , X _LE are the X coordinates of the island, sea segment, Y _IE ,
Y _LE is the Y coordinate of the island, sea segment, A _IE , A _LE is the island, sea segment length, N _IE , N _LE is the island, sea single piece number, and Y _IIS , Y _ILS is the island, sea encirclement pair. It represents the Y coordinate of . In addition, the island connected pair has the symbol _LIS1 ,
N _LIS2 , sea-connected pairs are represented by the symbols N _LLS1 , N _LLS2 , island-encompassing pairs are N _IIS1 ~N _IIS3 , sea-encompassing pairs are N _ILS1 ~
N Expressed as _ILS3 . Here, island, sea encirclement counter information N _IIS3 , N _ILS3 may be omitted, and island,
If the sea encirclement pair information is written in the same table in the scanning order of the imaging device, the Y coordinate is not necessary. In addition, the symbols N _TIE and N _TLE are the total number of islands and sea segments,
N _TILP , N _TLLP is the total number of islands, sea connections, N _TIIP , N _TLIP
represent the total number of islands and sea encircles, respectively. Note that these various image information are transferred from the information extraction circuits 15 to 17, 19 to 21 to the memories 18 and 22.
Transferred in DMA (direct memory access) mode.

Various kinds of image information regarding the islands and the sea obtained in this way by hardware are given to the processor 23 via the system bus 27, so it is necessary to analyze the connectivity, remove duplicates, etc. By processing and organizing,
It is possible to represent one or more of the islands, lake pieces as a single piece (blob or pattern). Therefore, the processor 23 assigns a predetermined number or symbol to each of the islands and sea pieces based on the processing results, and also applies this to the encirclement information, as shown in FIGS. 5C and F. The task of rewriting the enclosing pair table with these numbers and symbols is executed. Note that the processor 23 operates according to the program in the ROM 24, uses the RAM 25 as temporary memory to perform predetermined calculations, outputs the results via the input/output interface 26, and sends required commands via the interface 26. can be entered.

FIG. 6 is an explanatory diagram illustrating patterns for which connectivity analysis has been performed, and FIG. 7 is an explanatory diagram illustrating surrounding pair information organized (rewritten) based on the results.

That is, 1, 2, and 3 are ocean or lake numbers, and a, b, c, d, and e are island numbers. S _I1 ,
S _I2 , S _I3 , S _I4 , S _I5 , and S _I6 are the start segments of each island, and S _L1 , S _L2 , and S _L3 are the start segments of each sea. The surrounding pair information at this time is represented by island numbers a to e and sea numbers 1 to 3, as shown in FIG. Note that FIG. 7A shows island encirclement information, and FIG. 7B shows sea encirclement information. In addition, in Figure A, N _II1 and N _II3 represent the sea number, N _II2 represents the island number, and Y _II represents the Y coordinate at that time, and the total number of island surrounding pairs N _TIIP at this time is "6". . On the other hand, in Figure B, N _IL1 and N _IL3 are island numbers, and N _IL2
is the sea number, _YIL represents the Y coordinate at that time, and the total number of sea encirclement pairs _NTLIP at this time is "3". Therefore, by checking the Y coordinate of each start segment, the order in which enclosing pairs occur can be determined, so that their dependent relationships can be expressed in a hierarchical structure. FIG. 8 is an explanatory diagram illustrating the hierarchical structure of patterns expressed as in FIG. 6 or 7 in a tree format. Note that the "0" layer always represents the ocean, the 1st, 3rd, 5th... layers represent islands, the 2nd, 4th, 6th... layers represent the ocean (lake), and the 1st layer contains an island a. , b, d, the second layer has sea 2,
3, and islands c and e respectively belong to the third layer. When this is expanded to a general arbitrary figure, it becomes as shown in FIG. Note that FIG. 9 is an explanatory diagram illustrating the hierarchical structure of arbitrary figures. In the figure, S represents the sea, I represents the island, and L represents the lake (which may also be considered as the sea).Therefore, there are as many saphics as there are layers. Further, n ₁ , n ₂ , n ₃ . . . indicate the order of occurrence in the hierarchy.

Next, the procedure for analyzing the surrounding pair information will be explained with reference to FIGS. 10 to 12. In addition, FIG. 10 is a pattern diagram showing an example of a general figure, FIG. 11 is an explanatory diagram explaining surrounding pair information in that case, and FIG.
FIG. 13 is an explanatory diagram illustrating the processing procedure of hierarchical information (cell information) corresponding to the figure, and FIG. 13 is an explanatory diagram illustrating the result in tree format. In Figure 10,
The 8 symbols a to h represent the island pattern, and the number 1
9 represent ocean 1 and lake patterns 2 to 9, respectively, and the circles in the figure indicate the start segments. Therefore, if the surrounding pairs in this start segment are expressed in order according to their scanning order, it will be as shown in FIG. 11, and furthermore, if the hierarchical structure of the pattern is expressed according to the order of these surrounding pairs, It is expressed as shown in FIG.
The first line of Figure 12 lists the island and sea information in accordance with the order in which the surrounding pairs in Figure 11 occur, and the second line lists the island and sea information in the first line. In addition, from the third line onwards, the hierarchically connected islands and sea numbers are written and arranged for each layer. In this way, by locating a certain island or sea in each hierarchy, that is, by representing it in a hierarchical structure as shown in FIG. 12, its inclusion relationship can be identified. Incidentally, when such a hierarchical (cell) structure is expressed in a tree format, it becomes as shown in FIG.

FIG. 14 is a flowchart for explaining the overall procedure of the above processing. Note that although this processing procedure is as described above, its outline will be explained below. FIG. 2B shows the procedure for storing various image information obtained through the extraction circuits 15 to 17 and 19 to 21 shown in FIG. FIG. 4B shows the connectivity analysis processing procedure performed by the processor 23 based on this information. Figure C shows the procedure for rewriting the single piece number of the surrounding pair to the island and sea number based on the result.
Figure 2 shows the part that obtains layer (cell) information from the enclosing relationship. In addition, ``E'' in the same figure shows the procedure for determining geometric quantities such as the number of islands and seas from the hierarchical (cell) information and performing classification or inspection, and ``H'' in the same figure is the part that outputs the results. be.

〔Effect of the invention〕

As described above, according to the present invention, the following advantages can be obtained.

(b) Since the connectivity of all island and sea information for a general figure can be analyzed, it becomes possible to easily calculate geometric quantities such as the area, number, or perimeter of each pattern or blob.

(b) Similarly, for general shapes, the inclusion relationship between islands and oceans can be easily processed, and by expressing them in hierarchical (cell) information, arbitrary islands,
Since it is possible to easily analyze what level the ocean is in and which category it is included in, we can easily analyze the topological information (information such as the number of holes for islands or the number of islands floating in the sea). can be obtained easily.

C. Classification and inspection of inspection objects (number of scratches,
(area, etc.) can be easily carried out.

D. Since the enclosing pair information can be obtained by hardware using DMA mode, the analysis of the enclosing relationship can be performed easily and quickly.

[Brief explanation of drawings]

Figure 1 is an explanatory diagram explaining the inclusion relationship of blobs,
FIG. 2 is a configuration diagram showing an embodiment of the present invention, FIG. 3 is an explanatory diagram explaining general segment information, FIG. 4 is an explanatory diagram explaining island and sea segment information,
FIG. 5 is an explanatory diagram illustrating the various extracted image information of FIG. 4 that is written into the image memory, and FIG. 6 is an explanatory diagram illustrating the pattern after connectivity analysis is performed.
Figure 7 is an explanatory diagram for explaining the surrounding pair information in Figure 6, Figure 8 is an explanatory diagram for explaining the pattern in Figure 6 or Figure 7 in a tree format, and Figure 9 is an explanatory diagram for explaining the tree representation format of a general figure. FIG. 10 is an explanatory diagram to explain an example of a general figure. FIG. 11 is an explanatory diagram to explain the surrounding pair information in FIG. 10. FIG. 12 is a hierarchy created based on FIG. 11. An explanatory diagram explaining the structure; FIG. 13 is an explanatory diagram explaining the relationships shown in FIGS. 10 to 12 in a tree format;
FIG. 14 is a flowchart illustrating the processing operation of the present invention. Description of symbols, 11... Imaging screen, 12... Imaging device, 13... Binarization circuit, 14... Inverting circuit, 1
5, 19...Segment information extraction circuit, 16, 2
0... Connected pair information extraction circuit, 17, 21... Surrounding pair information extraction circuit, 18, 22... Image memory, 2
3...Processor, 24...ROM, 25...
RAM, 26...I/O interface, 27...
...system bus.

Claims (1)

[Claims] 1. When the background is considered to be the sea, a scanning means for horizontally and vertically scanning each pattern by viewing a plurality of identification target patterns as islands floating in the sea, and a part representing the islands is set to a logic "1", and a part representing the sea is set to a logic "1", for example. A binarization means that binarizes each as "0", island segment information that is expressed as a series of logic "1"s in the island part from the binarized information, and a connection between island single pieces that are expressed as the same island segment. island image information extraction means for extracting island image information including island connection pair information indicating the condition and island enclosing pair information indicating what kind of sea piece each island is surrounded by; sea image information extraction means for extracting sea image information including sea segment information, sea connection information, sea encirclement information, etc. from information obtained by inverting the logical relationship of the information, in the same manner as the island image information extraction means; It is equipped with a storage means for storing image information of each island and the sea, and an information processing means for executing a predetermined analysis process based on the stored image information, and the processing means is configured to store at least each piece of island and sea image information. From the viewpoint of connectivity, these are organized into a predetermined number of islands and sea fragments and numbered, and the island and sea encirclement information is rewritten using the plurality numbers, and then arranged in a predetermined order. A plurality of pattern analysis processing device characterized by analyzing the inclusion relationship of each pattern by expressing it in a hierarchical structure.