JPS61221981A - Label attachment system for area - Google Patents

Abstract

PURPOSE:To perform the attachment of temporary labels at a high speed by detecting the connecting relation and replacing these labels for each connecting relation to add the same label. CONSTITUTION:A temporary label attachment part 1<1> detects the connecting relations of the temporary labels attached to each minor area. A label arrangement part 2' arranges the overlap areas of detected connecting relations and then unifies these overlap areas into a part to detect the arranged connecting relations. A direct label detecting part 3<1> produces directly a connection table from the arranged connecting relations. A label tracing part 4<1> searches directly the connection table and displays the connecting relations in a graph based on a certain temporary label. A label replacement part 5<1> replaces the labels with '1' and '2' for 1-2-3-5 and 4-6-7-8 respectively according to the label tracing result.

Description

[Detailed Description of the Invention] [Summary] The present invention relates to an area labeling method, which detects directly connected temporary labels and tracks them to detect indirectly connected temporary labels at high speed. In this way, the temporary label is updated to speed up the area labeling process.

[Industrial application field]

The present invention relates to a region labeling scheme.

Generally, as shown in FIG. 7(A), in a binary image represented by ■ and ■, the background H portion is ■, and the area 11. [
Parts 2 and 13 are represented by ■, respectively.

However, if the area portion is simply represented by ■, it is not possible to distinguish between 11, ■2, and I3.

Therefore, as shown in Figure 7 (B), 3 is expressed by the same ■.
By labeling the two areas as 1, 2, 3, etc., you can clearly distinguish between them.

For example, if each of the illustrated regions is a chromosome and its area is to be determined, each chromosome has one,
By labeling 2 and 3 to distinguish them in advance and calculating the histogram of the constituent pixels (2), the area of each can be easily determined.

The present invention relates to a labeling method that makes it possible to clearly identify which of the regions each region is represented by a binary image.

[Problems that the conventional technology and invention are intended to solve]

The conventional labeling method is a method in which a temporary label is attached to each small area, the connection relationship between the small areas is detected, and a temporary label consisting of a serial number is changed and added to a continuous area formed by the small areas.

However, when converting into the serial number, the temporary labels are clustered, but the conventional clustering method requires many calculation processing steps.

For this reason, the conventional labeling method has a problem in that it is difficult to execute it at high speed.

c. Means and operation for solving the problems] The present invention aims to solve the above problems and achieve high-speed labeling by utilizing the property that the connection relationships of temporary labels constitute a planar graph. This means consists of a temporary label attaching section, a label sorting section, a directly connected label detecting section, a label tracking section, and a label updating section, and this means can reduce the amount of calculation required for clustering processing of temporary labels, resulting in high-speed processing. Labeling processing becomes possible.

〔Example〕

Hereinafter, the present invention will be explained by way of examples with reference to the accompanying drawings.

It is composed of an update section 5.

The temporary label attaching section 1'' is a device that temporarily attaches a label with an initial value of 1 by scanning a binary image using a window.

The label organizing unit 2 is a device that organizes overlapping parts among the connections of the temporary labels. Direct label detection section 3
is a device that detects all small areas to which each small area is directly connected from the above-mentioned organized connection relationships and creates a direct connection table, which will be described later.

The label tracking section 4 is a device that tracks labels based on the contents of the direct connection table and detects all temporary labels that are directly or indirectly connected.

Furthermore, the label updating unit 5 is a device that changes the temporary label based on the label tracking results.

Hereinafter, the operation of the apparatus shown in FIG. 1 having the above configuration will be explained based on FIGS. 2 to 6.

The temporary label attaching unit 1 scans the image G in the α direction using the window W shown in FIG. Label directions.

The window W in FIG. 2 has three windows designated by a, b, and c, and the logical operations thereof are as shown in Table 1.

In Table 1, the ``Input'' column represents the signals input from windows a, b, and c, and the ``Operation'' column represents the provisional labels attached to each part of the area, that is, the small area, by window C. There is.

Among the above inputs a, b, and c, * indicates an indefinite value, and NZ indicates a value other than zero.

The temporary label attaching unit 1 attaches a temporary label to the small area using the logical operations shown in Table 1 above, where a=*.

In the case of b = *, c = 0 (left diagram of Figure 3 (A)), C
=0 (right side of FIG. 3(A)), ie, no label is attached.

a=0. When b=Ojc≠0 (left side of Figure 3 (B))
temporarily attaches a label of c=L, that is, initial value L=1 (on the right side of FIG. 3(B)). This is where the label appears for the first time.

In the case of a-Q, b≠Q, c≠0 (left side of Figure 3 (C))
, C=a=O1, that is, add the same label L=1 as last time (
(right side of Figure 3(C)).

This also applies to the cases where a≠O, b'''Q, and c≠O.

Next, if a, b, and c are all non-zero and the window W completely enters the area I (left side of Fig. 3 (D)), change the attached temporary labels L and L'' to a, b. Compare by c=
Min (a, b), ie the smaller one, for example L, is attached as a temporary label (right side in Figure 3(D)).

Next, the temporary label attaching unit l detects the connection relationship of the temporary labels attached to each small area. The arithmetic logic in this case is as shown in Table 2.

Detection of this connection relationship is performed by using different temporary labels a=L, b=L within the same area, as shown in FIG. 3(D), for example.
Detect the connection relationship when ' is installed.

The second table label sorting section 2 sorts out overlapping parts of the detected connection relationships, and its operation will be explained based on FIG. 4.

Figure 4 (A) is image G after temporary label attachment, Figure 4 (B)
) is the output connection relationship, and FIG. 4(C) is the organized connection relationship.

Temporary labels from to 8 are attached.

Further, in FIG. 4(B), the connection relationship of the provisional labels is detected according to the arithmetic logic in Table 2. Figure 4 (
The underlined part in B) is the overlapping part.

The label organizer 2 combines these duplicate parts into one,
As shown in FIG. 4(C), organized connection relationships are detected.

The direct label detection unit 3 creates a direct connection table (FIG. 5(C)) from the organized connection relationships (FIG. 5(A)).

This direct connection table shows the provisional labels (Y) connected to each provisional label (X) from 1 to 8.
It is a collection of.

Furthermore, while searching the direct connection table (FIG. 5(B)), the label tracking unit 4 expresses the connection relationship in a graph based on one provisional label (FIG. 6(A)).
! It can be seen that temporary labels 3, 2, and 5 are connected to temporary label l in temporary label column X of the direct connection table (Figure 5 (B)) (left side of Figure 6 (A)). ■)
If we use the temporary label 2 (X) as the standard, then 3
and 1 are connected. Therefore, it can be seen that 2 and 3 are connected (■).

As a result, an independent group of temporary labels 1-2-3-5 was formed.

In addition, in the table of FIG. 5(B), provisional label 4
Based on (X), it is connected to 6 (■
). Next, if we look at 6, it is connected to 7 and 8 (■
). If we look at 7, we can see that it is connected to 8 (■).

Therefore, 4-6-7-8 independent groups were formed.

Note that the label tracking described above is performed by tracing the edges of the graph, and considering that the graph is a planar graph, the total number of edges is 3×(number of labels)−6. Therefore, the tracking process can be completed within a time proportional to the maximum value of the provisional label.

The label updating unit 5 updates the label tracking results (Fig. 6(B)
)), 1-2-3-5 sets the temporary label to 1 and 4
-6-7-8 change the temporary label to 2, respectively.

As a result, the distinction between region 11 and r2 (FIG. 4(A)), which was initially unclear, became clear. In other words, labeling processing can be performed in one-to-one correspondence to each region.

〔Effect of the invention〕

As described above, according to the present invention, without performing clustering of provisional labels as in the past, provisional labels added to each small area are detected and tracked, connection relationships are detected, and the above-mentioned By changing the temporary label and adding the same temporary label, it is now possible to perform the temporary labeling process at high speed.

[Brief explanation of drawings]

Fig. 1 is a block diagram of the method of the present invention, Fig. 2 is a block diagram of a window used in the method of the present invention, Figs. (A) to (C) are operation explanatory diagrams of the label sorting section, and Figures 5 (A) and (B)
is an explanatory diagram of the operation of the direct connection label detection section, FIG. 6 (A),
7(B) is an explanatory diagram of the operation of the label tracking unit and the updating unit, and FIGS. 7(A) and 7(B) are explanatory diagrams of the industrial application field. ■ ...Temporary label attachment part, ! 2...Label sorting unit, 3...Direct connection label detection unit, 4...Label tracking unit, 5...Label update unit.

Claims (1)

[Claims] In a labeling method in which a label is attached to the above-mentioned region of an image in which the background and the region can be represented by binary values, the above-mentioned image is scanned, a video signal is inputted, and a provisional label is created for each small region in response to the input signal. a temporary label attachment part that attaches the label and detects the connection relationship with the existing nearby temporary label;
A label organizer that generates a connection relationship that organizes the overlapping parts of the above connection relationships, and a direct connection that sequentially associates each temporary label with the temporary labels connected to it based on the above organized connection relationships. A direct connection label detection unit that generates a table; a label tracking unit that searches the above direct connection table and generates groups of interconnected connections; and a label tracking unit that searches the above direct connection table to generate groups of interconnected connections; A labeling method for an area, comprising a label updating unit that adds the same temporary label to a region.