JPH0520792B2 - - Google Patents

Description

[Detailed Description of the Invention] [Summary] This is a method for labeling connected regions of each pixel constituting image information, and for input image information,
By adding a temporary label so that different connection relationships do not occur consecutively, the frequency of connection relationships input to the connection relationship organizing section is reduced, and the history of previously detected connection relationships is retained. By referring to this and outputting only the first detected connection relationship among duplicate connection relationships, the amount of calculation is reduced and high-speed labeling becomes possible.

[Industrial application field]

The present invention relates to a labeling method that quickly labels connected regions of pixels that constitute image information.

For example, image processing devices for recognizing medical images as clear images have been put into practical use. During processing in this image processing device, a pixel set whose pixel value is "1" in an image obtained by binarizing image information is divided and divided into each connected area, and a different integer is assigned to each pixel in each connected area. There is a labeling process that assigns labels.

This labeling process takes a long time even if it is performed in an image processing apparatus, so it has been desired to put into practical use a system that performs the labeling process efficiently and in a short time.

[Conventional technology]

FIG. 7 is a block diagram explaining the conventional example, FIG. 8 is a diagram explaining area labeling processing, FIG. 9 is a diagram explaining the operation of temporary labeling in the conventional example, and FIG. 10 is a diagram explaining the conventional temporary labeling process. FIG. 11 is a diagram for explaining the labeling result situation, FIG. 11 is a diagram for explaining the conventional connection relation arrangement operation, and FIG. 12 is a diagram for explaining the operation of the clustering section.

FIG. 8 shows an example of labeling processing for connected regions. Figure 8A shows the image before processing, the white area (level "0") is the background, the diagonally shaded area (level "1") is the area to be labeled, and Figure 8B shows the label. The labeling process adds a unique label (1, 2, 3 in this example) to each area to distinguish each area.

FIG. 7 shows a conventional example of a block diagram for performing the above labeling process. This block diagram includes a temporary labeling circuit 1 that sequentially attaches temporary labels to each pixel of a video signal obtained by scanning an image, and detects the connection relationship with neighboring temporary labels that have already been added. , a connection relationship organizing circuit 2 that organizes overlapping parts of the detected connection relationships; a label updating unit 3 that updates the provisional label using the classification results of the provisional label; It consists of a clustering section 4 that performs classification.

As shown in FIG. 9A, the temporary labeling circuit 1 sets a relative L-shaped window (the left and right sides of the L shape are reversed) on the input image,
Scanning is performed using this relative L-shaped window to detect the generation and extension of labels as shown in FIG. 9B, and the connection relationship between adjacent labels as shown in FIG. 9C.

The direction in which the relative L-shaped window scans is the direction of the arrow shown in FIG. 9A, and the pixels scanned simultaneously are a, b, and c. Note that the number of pixels in the right direction is i pixels, and the number of pixels in the downward direction is j pixels.

The logic of label generation and extension is shown in Figure 9B.
As shown in , for example, pixels a~
Of c, pixels a and b are at an undefined level (indicated by *),
When pixel c is at the "0" level, c=0 and the pixel of interest is transmitted.

Also, when pixels a and b are at a “0” level and pixel c is at a level other than “0” (indicated by NZ), c=L.
(However, L=L+1, where L is a provisional label (initial value 1)), and calculations are performed to generate a label.

Furthermore, when pixel a is at the "0" level and pixels b and c are at the "NZ" level, c=b and an operation is performed to extend the label, and when pixels a, b, and c are at the "NZ" level, sets c=Min(a, b) and performs an operation to extend the label.

FIG. 9C shows the conditions for detecting the connection relationship between each pixel a, b, and c. For example, pixels a and b are at an undefined level, and pixel c is at a "0" or "NZ" level. When the connection relation function Fc=0,
It is determined that there is no connection relationship between the label and the pixel c.

Furthermore, when each pixel a, b, and c are at the "NZ" level, the temporary labeling circuit 1 outputs the connection relation function Fc = 1 (a, b), and the pixel a, b is
is connected.

FIG. 10 shows a provisional labeling result (shown in FIG. 10A) and a detected connection relationship (shown in FIG. 10B) based on a processing example using the above method. As is clear from this, when processing with the above method, different connection relationships occur continuously (for example, provisional labels 1 and 6, 1 and 5, 1 and 4, etc., which will be referred to as 1/6,
1/5, 1/4, etc.).

FIG. 11A shows the image after provisional labeling processing. Connection relationship arrangement circuit 2 is provisional labeling circuit 1
This is to organize the overlapping parts of the connection relationships detected in the above. Conventionally, as a method for sorting out these overlapping connection relationships, for example, the triangular memory method proposed by the Agency of Industrial Science and Technology (Patent Publication No. 58-16217) has been used.

This triangular memory method, as shown in Figure 11B,
For example, add temporary label numbers (1 to 8 in this example) to the horizontal and vertical directions of the memory, and if the horizontal and vertical coordinate points (for example, 1/2) have a connection relationship, add '1'. If it is set, enter '0' to indicate the duplicate connection relationship. After inputting the duplicate connection relationships into the memory, the entire memory is read out, thereby outputting the result of organizing the connection relationships.

FIG. 12 is a diagram illustrating the operation of the clustering unit 4, in which connection relationships organized by the connection relationship organizing circuit 2, such as shown in FIG. 12A, are input, and all provisional labels belonging to each connected area are Detect. That is, the direct connection table shown in FIG. 12B is created from the organized connection relationships shown in FIG. 12A.

For example, the temporary label connected to the temporary label “1” is “3” from the table in FIG. 12B,
They become “2” and “5”. Further, the temporary labels directly connected to the temporary label "8" are "6" and "7". This direct connection table is a collection of temporary labels that are directly connected to each temporary label.

Next, based on the contents of the direct connection table, the temporary labels are tracked and the labels are clustered. This processing corresponds to tracing the edges of the graph when the connection relationships of the provisional labels are expressed graphically as shown in FIG. 12C, and FIG. 12D shows the tracing results of the provisional labels.

The label updating unit 3 updates the temporary label based on the output of the clustering unit 4. Figure 11A
In the image example, by converting the temporary labels 1, 2, 3, and 5 to "1" and the temporary labels 4, 6, 7, and 8 to "2", each area is labeled in a one-to-one correspondence. It will be done.

[Problem that the invention seeks to solve]

When performing temporary labeling using the above method, the pixel next to the top of the pixel of interest (pixel c in this example) (pixel a in this example) and the pixel next to the left (pixel b in this example)
If a temporary label is attached to both pixels, how to make the temporary label of the pixel next to the top the pixel of interest, and how to output the minimum value of the two pixels next to the top and to the left (example shown in Figure 9B). There is a way.

In these methods, the connection relationship of the provisional label occurs for each pixel, and different connection relationships occur continuously, so the processing takes a long time.

Furthermore, when sorting out duplicate connection relationships detected by the temporary labeling circuit 1, it is necessary to input the duplicate connection relationships into a memory (not shown) and then read out the entire memory (not shown). In order to be
There are problems such as requiring calculation time proportional to the square of the maximum provisional label.

[Means for solving problems]

FIG. 1 shows a block diagram of the principle of the present invention.

This principle block diagram includes the label updating unit 3 and clustering unit 4 explained in FIG. If the same connection relationship is detected consecutively, the label addition circuit 11 outputs the provisional label attached to the pixel on the left as the pixel of interest, and outputs the connection relationship only once if the same connection relationship is detected consecutively. A provisional labeling unit 5 having a suppression circuit 12 that suppresses other connections, a label connection table that holds a history of connection relationships detected in an image, and a label connection table that stores a history of connection relationships detected in an image, The connection relation organizing section 6 has a connection relation restriction means that outputs only those detected in the above, and an initialization means that holds the organized connection relations and initializes a label connection table based on the organized connection relations. has been done.

[Effect]

In provisional labeling of input image information,
A temporary label is added by the label adding means so that different connection relationships do not occur consecutively, and if the same connection relationship is detected consecutively, that connection relationship is output only once, and further connection relationships are The organizer maintains a history of previously detected connection relationships, and by referring to this history, outputs only the connection relationship that was detected first among duplicate connections. The frequency of connection relationships input to the relationship arrangement section is reduced, and the amount of calculation by the connection relation arrangement section is reduced, allowing high-speed labeling.

〔Example〕

The gist of the present invention will be specifically explained below with reference to embodiments shown in FIGS. 1 to 6.

FIG. 2 is a block diagram illustrating a connection relationship sorting unit according to an embodiment of the present invention, FIG. 3 is a diagram illustrating provisional labeling in an embodiment of the present invention, and FIG. FIG. 5 is a diagram explaining the labeling operation; FIG. 5 is a diagram explaining the provisional labeling results and connection relationships in the embodiment of the present invention;
The figures each show a block diagram for explaining the operation of the connection relationship sorting section in the embodiment of the present invention. Note that the same reference numerals indicate the same objects throughout the figures.

Next, a labeling operation based on this embodiment will be explained. In the explanation of the operation of this embodiment, the operation of the label updating section 3 and the clustering section 4 will be explained as follows.
It is omitted because it is the same as the explanation of the figure.

The temporary labeling section 5, which includes the label adding circuit 11 and the suppression circuit 12 shown in FIG. 1, scans the image in the direction of the arrow using the above-mentioned relative L-shaped window, as shown in FIG. At this time, as the value of the provisional label to be output to the pixel of interest (portion corresponding to pixel c), pixel b on the left is outputted to prevent different connection relationships from occurring consecutively.

That is, the logic of label generation and extension is that among pixels a, b, and c that are simultaneously scanned and input as shown in FIG. When the level is “0”, c=0 and the label generation process is not extended, and when pixels a and b are “0” and pixel c is at a level other than “0” (indicated by “NZ”), There is a label generation process.

Also, when pixels b and c are "NZ" and pixel a is at "0" level, c=b; when pixels a and c are "NZ" and pixel b is at "0" level, c=a, and pixel a , b, and c are all "NZ", c=b, and label extension processing is required in either case.

Incidentally, FIG. 4 shows details of the related operations of the window operation shown in FIG. 3B, whether or not a label is generated, and whether or not the label is extended.

Next, FIG. 3C shows the relationship between connection relationship detection and output suppression of consecutive identical connection relationships. That is, when pixels a and b are undefined and pixel c is at "0" level, when pixel a is undefined, pixel b is at "0", and pixel c is at "NZ", pixel a is at "0", pixel b, When c is "NZ", the immediately preceding connection relationship is undefined and the label is output as having no connection relationship (Fc=0).

Next, when pixels a, b, and c are all "NZ" and the previous connection relationship is a, b, output is suppressed with Fc = 0, and if the previous connection relationship is other than a, b, Fc
=1 outputs a and b.

FIG. 5 shows the results of the provisional labeling processed as described above and the connection relationships. That is, according to this, the same connection relationship occurs consecutively, but different connection relationships do not occur consecutively.

Moreover, since the same connection relationship is suppressed by the logic shown in FIG. 3C (the part indicated by the "X" mark in FIG. 5B), the occurrence of connection relationships can be significantly reduced.

Next, FIG. 2 shows a detailed block diagram of the connection relationship organizing section 6 in this embodiment. That is, the connection relationship arrangement unit 6 of this embodiment includes a label connection table 23, a connection relationship restriction circuit 24, and a multiplexer (hereinafter referred to as
(referred to as MPX) 21 and an initialization circuit 25 consisting of a memory 22.

The label connection table 23 is a two-dimensional 1-bit memory for holding the connection relationship of labels, and when the connection relationship is input, "1" is written to the corresponding address.
is written.

The connection relationship restriction circuit 24 is the label connection table 2
3 is "0", that is, only when the input connection relationship appears for the first time, the connection relationship is output. The initialization circuit 25 holds the output connection relationship in the memory 22, and stores the label connection table 23 according to this content.
Initialize.

That is, the contents of the label connection table 23 are cleared by an MPU (not shown) prior to processing. In this case, a process is performed in which 0 is written to all addresses in the two-dimensional 1-bit label connection table 23.

On the other hand, during execution of processing, it is necessary to clear the image data within the invalid period (retrace period), but in the process of writing 0 to all addresses, processing cannot be completed within the retrace period. .

For this reason, a memory 22 for storing connection relationships is prepared, and the memory 22 stores the organized connection relationships while the labeling process is being executed, and during the retrace period, the memory 22 stores the organized connection relationships.
21, input the address (connection relationship) that became 1 in the previous frame from the memory 22 to the label connection table 23, and set the value of that address to 0.
By returning to , the label connection table 23 is cleared.

The connection relationship sorting section 6 configured in this manner sorts out overlapping parts of the connection relationships detected by the temporary labeling section 5.

That is, if the image shown in FIG. 6A is the image after provisional labeling, the connection relationship detected by the provisional labeling section 5 will be as shown in FIG. 6B. In this figure, the "x" marks are connection relationships suppressed by the provisional labeling unit 5, and the underlined portions are overlapping portions of connection relationships. Incidentally, FIG. 6C shows the output when overlapping parts are sorted out.

〔Effect of the invention〕

According to the present invention as described above, the connection relationships detected by provisional labeling can be significantly reduced, the time for connection relationship detection can be shortened, and the overlapping portions of connection relationships of provisional labels can be reduced, so that the connection relationships in the connected area can be reduced. This has the effect that labeling processing can be executed at high speed.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of the principle of the present invention, FIG. 2 is a block diagram illustrating a connection relation sorting unit according to an embodiment of the present invention, and FIG. 3 is a diagram illustrating temporary labeling in an embodiment of the present invention. FIG. 4 is a diagram explaining the operation of temporary labeling in the embodiment of the present invention;
FIG. 5 is a diagram illustrating the provisional labeling results and connection relationships in the embodiment of the present invention, FIG. 6 is a block diagram illustrating the operation of the connection relationship arrangement unit in the embodiment of the present invention, and FIG. 7 is a conventional example. FIG. 8 is a diagram explaining the region labeling process, FIG. 9 is a diagram explaining the operation status of temporary labeling in the conventional example, and FIG. 10 is a diagram explaining the status of the temporary labeling result in the conventional example. FIG. 11 is a diagram for explaining the operation of conventional connection relationship sorting, and FIG. 12 is a diagram for explaining the operation of the clustering section. In the figure, 1 is a provisional labeling circuit, 2 is a connection relation arrangement circuit, 3 is a label update section, 4 is a clustering section, 5 is a provisional labeling section, 6 is a connection relation arrangement section, 11 is a label addition circuit, and 12 is a 21 is an MPX, 22 is a memory, 23 is a label connection table, 24 is a connection relationship restriction circuit, and 25 is an initialization circuit.

Claims (1)

[Scope of Claims] 1. For a video signal obtained by scanning an image, each pixel constituting the image is scanned using a predetermined scanning method, and provisional labels are sequentially attached to the video signal, and provisional labels in the vicinity that have already been added are a provisional labeling unit 5 that detects connection relationships with labels; a connection relationship organizing unit 6 that organizes overlapping portions of connection relationships detected by the provisional labeling unit 5; In a connected region labeling circuit comprising a label updating unit 3 etc. that updates a temporary label using the classification result of the temporary label, the temporary labeling unit 5 is configured such that the scanning direction of the image is at the bottom right. , a label adding means 11 that, when a provisional label is added to the pixel above and to the left of the pixel of interest, gives priority to the provisional label added to the pixel to the left of the pixel of interest and outputs it to the pixel of interest; When the same connection relationship is detected consecutively,
a suppressing means 12 that outputs a connection relation only once and suppresses others; a holding means for holding a history of connection relations detected in the image in the connection relation organizing section 6; see the holding means. and connection relation limiting means for outputting only the first detected one among the duplicated connection relations, and the label adding means 11 temporarily labels the input image and labels it based on a predetermined procedure. The same connection relationship that occurs continuously and is obtained by adding is suppressed by the suppression means 12 so that it is sent only once to the connection relationship organizing section 6, and furthermore, the holding means is provided with information about the previously inspected connection relationship. A labeling circuit that retains a history of connection relationships that have been detected, refers to this content, and performs control to output only the connection relationship that is detected first among duplicate connection relationships.