JPS62281077A - Temporary inter-label connection information storage method - Google Patents

Abstract

PURPOSE:To widely decrease a hardware quantity by providing first, second and third tables as the means to hold the arranged information of the connecting relation between temporary labels. CONSTITUTION:A connecting relation arranging part 2 arranges the overlapping part of the information between temporary labels. The connecting relation of the label, in which the overlapping is removed by the connecting relation arranging part 2, is set to three types of the table of a connecting label counting table 4, an address converting table 5 and a label connecting table 6. The connecting label counting table 4 is the table to show whether or not one temporary label is connected with other some labels. The label connecting table 6 is the table to store the label of the opponent which in connected, and when the label is stored into the table, the storing address to the label connecting table 6 is converted by the address converting table 5.

Description

[Detailed Description of the Invention] 3. Detailed Description of the Invention [Summary] By scanning a screen made up of a set of pixels using a window of a specific shape and performing logical operations on data within the window, A temporary label is attached to each pixel that makes up the image on the screen, and at the same time, the connection relationship between the temporarily attached labels is investigated by performing a logical operation different from the above between the data in the window. In image processing systems that organize images and assign labels to distinguish them from each other independently existing on the screen, conventionally, each provisional label and the value of another provisional label in a connection relationship are The problem was that it required a large amount of storage space to create a table that would store the . In order to solve such conventional problems, the present invention provides a table having a plurality of areas capable of holding a plurality of values of a temporary label, as a table holding information on the connection relationship between a temporary label and other temporary labels. and a table that holds the address values of the areas in which the values of other provisional labels with connections are held, corresponding to each provisional label value, thereby reducing the storage area to a very small amount. discloses a technology that can hold information on connection relationships between temporary labels.

[Industrial Application Field] The present invention relates to a control method for labeling each area of each image in order to clearly identify a plurality of images that exist independently within one screen during image processing. .

For example, an image processing device that recognizes medical images as clear images has been put into practical use, but during processing in this image processing device, the pixel value of the image that is binarized from the image information is 1". Labeling involves a process of dividing and dividing a pixel set into connected regions and assigning a different integer to each pixel in each connected region.

Another example is the automation of parts inspection using image processing technology in the manufacturing department of machinery, etc.
In this case as well, labeling of image areas is an essential technology for video identification.

The present invention efficiently stores information on connection relationships between a large amount of labels temporarily attached to pixels of each image generated in the process when labeling an image area as described above, using a small storage area. This relates to a control method that aims to maintain the

[Prior Art] Regarding image data in which an image of a target object and its background are represented separately in binary terms on a screen, when multiple images exist on the screen, each area is Several methods can be considered for attaching labels to identify the
No. 1 discloses a method capable of performing labeling processing at high speed with relatively simple control.

In other words, in this method, J
Using a ``°-shaped window, while scanning the screen, perform a logical operation according to the value of the pixel within the window, and use the result as the pixel label value (temporary label). This method examines the connection relationships between labels, organizes them, and assigns labels to distinguish each area of the image that exists independently on the screen.

[Problems to be Solved by the Invention] In the conventional labeling method described above, a connected label count table and a label connection table are used as tables for storing connection relationships between temporary labels.

FIG. 6 is a diagram illustrating the conventional table for storing connection relationships between temporary labels, in which (a) shows a connection label count table, and (b) shows a label connection table.

In the figure, the connection label count table stores the number of other temporary labels that have a connection relationship with each of the temporary labels (1, 2, 3, . . . L "^), and the label connection table (b ) are temporary labels (1, 2, 3...
. . Lm), other temporary label value sets having connection relationships are stored.

The amount of memory required to create these tables is 1 for the connection label count table.
In the case of ~Ll11, Lm pieces are sufficient, but the label connection table requires a large amount of memory as Lm2 pieces. It is possible that all other temporary labels have a connection relationship with a certain temporary label, so temporary labels 1 to LI
This is because it is necessary to prepare Lm areas for each of l.

However, the small regions to which provisional labels have been added are uniquely matched in the image, and if each provisional label is considered to be a vertex and the connection relationship to be an edge, these relationships constitute a planar graph. When the number of vertices of a planar graph is constant, the number of edges is maximized when all areas surrounded by each edge form a triangle. Therefore, the upper limit of the temporary label connection is 3L.
It becomes m-6.

Therefore, in reality, most of the area of the label connection table remains unused, as shown as an unused area 50 in FIG. 6(b).

Therefore, such a conventional method requires a large amount of memory and has a problem in that the memory usage efficiency is very low.

In view of these conventional problems, the present invention discloses a control method that can efficiently store information on connection relationships between temporary labels using a small amount of memory.
It is intended to provide an economically feasible labeling of image regions.

Means for Solving Problems] According to the present invention, the above-mentioned object is to solve the problem for each pixel of binary image data obtained by scanning a screen as described in the claims. A temporary label is attached to each pixel according to its relationship with neighboring pixels, and after detecting the connection relationship between each temporary label, this is organized to distinguish between each image that exists independently on the screen. In an image processing system that assigns labels, as a means of retaining organized information on the connection relationships between temporary labels, the number of other temporary labels with which each temporary label has a connection relationship is calculated for each value of each temporary label. A first table that can hold a plurality of address values on the third table for each provisional label value, and a second table that can hold multiple provisional label values for each address. This is achieved by a provisional inter-label connection information storage method characterized by providing a third table that can hold the information.

[Function] Figure 1 is a diagram explaining a table for storing connection relationships between temporary labels according to the present invention, in which (a) is a connection label count table, (b) is an address conversion table, and (c) is a label Showing the connection table.

In FIG. 1, the connection label count table is the same as in the conventional case explained in FIG. I remember.

In other words, the address conversion table has provisional labels 1 to Lm.
For each of these, the address of each area of the label connection table that holds the values of other provisional labels that have connection relationships with these (■,■.

■......) is memorized. Therefore, when it is desired to know another provisional label connected to a certain provisional label, the address value corresponding to the relevant provisional label is obtained and the label connection table is searched based on this address value. When there are many other temporary labels that have a connection relationship, these are stored using multiple areas of the label connection table, and the address values of the multiple areas are stored for one temporary label on the address conversion table. .

In the method of the present invention, the maximum value of the provisional label is
1 and the width of the label connection table is a, the address conversion table only needs to have an area of LmX (Ln+/a). Also, according to graph theory, the maximum number of label connection relationships is (3Lm-6>), so up to (2Lm 6) connection relationships in the label connection table fill up the memory width, and the remaining Ln+ connection relationships are 1 on the temporary label
- When the connection table is detected one by one, the size of the connection table becomes maximum. Therefore, the size of this table is 2
It is sufficient if it is Llll -6+aLm. In other words, the label connection table, which conventionally required an area of Lm2, can be reduced to (1
/aH, m2 (address conversion table) + (2+a)L
It can be configured with an area of 6 (label connection table).

[Embodiment] FIG. 2 is a block diagram of an embodiment of the present invention, in which 1
2 is a provisional labeling section, 2 is a connection relationship organizing section, 3 is a delay buffer, 4 is a connection label count table, 5 is an address conversion table, 6 is a label connection table, 7 is a clustering section, and 8 is a label update section. represents.

For provisional labeling, part 1 is """ as shown in Figure 3 (a).
By scanning the binary image shown in (b) in the direction shown by 10 using the shaped window 9 (window) and performing logical operations as shown in Table 1, the image shown in (c) is obtained. Give each pixel a temporary label. Then, when this is further scanned using the window, at the same time, according to the logic shown in Table 2, (
d) Obtain connection relationship information as shown in d).

Regarding the symbols listed in Tables 1 and 2, * marks are arbitrary values, NZ is non-zero, L is a provisional label, Fc
each represents a flag indicating the presence or absence of provisional label connection. Further, the initial value of L is "1'".

Table 1 Table 2 The connection relationship sorting unit 2 in Table 2 converts the overlapped part (indicated by 11 in the figure) of the connection relationship information between the provisional labels shown in FIG. 3(d) into (e). Organize as shown.

The connection relationships of labels from which duplicates have been removed by the connection relationship sorting unit 2 are set in three types of tables: a connection label count table 4, an address conversion table 5, and a label connection table 6. The connected label count table 4 is a table showing whether one temporary label is connected to several other labels. The label connection table 6 is a table that stores labels of connected parties, and when storing this table number label, the address conversion table 5 converts the address stored in the label connection table 6.

FIG. 4 is a diagram illustrating storage of information on connection relationships between these temporary labels. In the figure, provisional labels are generated for image labels 12 and 13 as shown in (a), and when the connection relationships of these provisional labels are arranged as shown in (b), among them, 1-2 to As shown in (e), the connection-related information from 1 to 6 includes a connection label/count table 14, an address conversion table 15,
Each is stored in the label connection table 16. Then, the connection information 1-7 is stored as shown in (d).

The clustering unit 7 tracks labels based on the contents of the label connection table and detects all temporary labels that are directly or indirectly connected. The connections shown in FIG. 4(b) are represented graphically using nodes as labels and edges as edges, and are shown in FIGS. 5(a) and 5(b). Clustering is performed by tracing this area.

The label updating unit updates the temporary label based on the label tracking results. In the case of the image in Figure 4(a), (1, 2,
3, 4, 5, 6, 7) to 1, (8, 9,
By converting the provisional label in 10) into 2, it is possible to perform labeling processing that uniquely corresponds to each region in the image.

[Effects of the Invention] As explained above, according to the method of the present invention, unlike conventional methods, the most severe conditions, which are rarely used, are taken into account regarding the memory that stores information on connection relationships of temporary labels. This eliminates the inconvenience of having to prepare a large area for data storage, and the tables that store the information can be created using a small amount of memory, making it possible to significantly reduce the amount of hardware required compared to the past. This has the advantage that it is possible to realize an economical device.

[Brief explanation of the drawing]

FIG. 1 is a diagram explaining a table for storing connection relationships between temporary labels according to the present invention, FIG. 2 is a block diagram of an embodiment of the present invention, and FIG. 3 is a diagram explaining provision of temporary labels and their organization. Figure 4 is a diagram explaining the storage of information on the connection relationship between temporary labels, Figure 5 is a diagram showing the connection relationship in a graphical representation, and Figure 6 is a diagram for storing the connection relationship between temporary labels in the past. It is a figure explaining a table. 1...Temporary labeling section, 2...Connection relationship organizing section, 3...Delay buffer, 4.
...Connection label count table, 5...
・Address conversion table, 6...Label connection table, 7...Clustering section, 8...
...Label update section, 9...Window, 10...
・Scanning direction, 11... Overlapping part of connection relationship information,
12.1-3...Image, 14...Connection label count table, 15...Address conversion table 16...Label connection table agent Patent attorney I Digit Sada → \-Toku \- (Re \-Fear N-To the Deaf-) The continuation of the conventional provisional level A system is used. Figure 6. Diagram explaining IC-7.

Claims (1)

[Claims] A provisional label is attached to each pixel of the binary image data obtained by scanning the screen according to its relationship with neighboring pixels, and the connection relationship between each provisional label is detected. In an image processing system that organizes images and assigns labels for distinguishing them to each image that exists independently on the screen, each temporary label is A first table holds the number of other temporary labels with which each temporary label has a connection relationship for each temporary label value, and a plurality of address values on a third table are held for each temporary label value. 1. A method for storing connection information between temporary labels, comprising: a second table that can hold a plurality of temporary label values for each address; and a third table that can hold a plurality of temporary label values for each address.