JPH07104941B2 - Labeling method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION (Industrial field of application) The present invention relates to a labeling method, and more specifically, as a preprocessing operation such as analysis and measurement using a binary image, “1-pixel” The present invention relates to a labeling method capable of giving a unique continuous label value at high speed to a large number of connected components formed by connecting a plurality of logical "1" pixels shown in FIG.

(Prior Art) Conventionally, a labeling method shown in FIG. 4 has been known as this type of labeling method.

That is, in the figure, 100 is "1-pixel" and "0."
-Pixel "(pixel of logical" 0 "indicating the background), and when labeling, first, the binary image 100
Is raster-scanned from the upper left of the screen as indicated by an arrow 201, and when an unlabeled "1-pixel" is detected, an unused label value, for example, "1" is attached to this pixel. Then, with this pixel as the center,
4 connections that are continuous in the direction or up and down, left and right and diagonal 8
The 8-connected “1-pixel” that is continuous in the direction is indicated by the arrow 202.
The same label value is given by searching by the neighborhood scan shown by.

Further, the process of assigning the same label value to "1-pixels" of 4-connection or 8-connection centered on these connection pixels is repeated, and when there is no "1-pixel" connected, one connection is made. Finish labeling for component 301.

When the labeling of the connected component 301 is completed in this way, the raster scanning of the binary image 100 is continued again, and if "1-pixel" which is not yet labeled is detected, a new label value "2" is added and the connected component is added. For 302, the same processing as above is performed. By repeating the above processing for the remaining connected components 303, a series of labeling processing is completed when the raster scanning of the entire binary image 100 is completed.

However, in this method, 4 is detected after "1-pixel" is detected.
In order to detect another "1-pixel" that is connected or 8-connected, it is necessary to read the pixel value four times or eight times for one pixel, and the number of accesses to the memory is large, so processing is possible. I needed a lot of time.

On the other hand, a labeling method as shown in FIG. 5 has been proposed in order to reduce the number of scanning of binary images. In this method, first, when the unlabeled "1-pixel" is detected by raster scanning the binary image 100A, adjacent points are examined.
If all adjacent points are not labeled yet, a new label value is assigned, and if the same label value is assigned other than "0-pixel", the same label value is assigned, and two or more types are assigned. If different label values are attached, the youngest label value among them is given, and it is memorized that these have the same connected component.

When the scanning of the entire binary image 100A is completed by continuing the same processing, raster scanning is performed again, and the label value indicating the same connected component is changed to the youngest label value among the connected components. This completes the labeling process.

In FIG. 5, 301A, 302A, and 303A indicate the same connected component. Among these, the connected component 301A is part of the label value "2" as a result of raster scanning again.
Is changed to the youngest label value "1" in the connected component 301A.

(Problems to be solved by the invention) However, in this method, as is apparent from the connected components 301A, 302A, and 303A after the change in FIG. In processing such as analysis, there is a constraint that it is necessary to recognize what kind of label and how many labels there are.

Also, in the process of scanning, since a plurality of labels are used even though they are included in the same connected component, the absolute number of label values is reduced, and the number of connected components to be labeled, in other words, the target of labeling. There is a problem that the binary image is restricted, and there has been a demand for solving such a problem.

The present invention has been proposed to solve the above problems,
The purpose of this is to make it possible to continuously give unique label values to a large number of connected components with a small number of scans, and to greatly improve the efficiency of a series of image processing operations without the above-mentioned various restrictions. It is to provide a labeling method that can be enhanced.

(Means for Solving the Problems) In order to achieve the above object, the present invention provides binary image data including “1-pixel” and “0-pixel” according to the presence or absence of a pixel in an image memory. It is arranged in the most significant bit of the image memory, and the point detected as "1-pixel" based on the most significant bit by the raster scanning of the screen is stored as a starting point, and includes this starting point and is continuous with this starting point. "1
A connected component of the current scan row consisting of `` pixels '' is detected, the same label value is given to the connected component using the remaining lower bits of the image memory, and the most significant bit of each point is cleared to zero; Next, raster scanning is performed for each of the upper row and the lower row of the current scan row, and "1-" is set within the range indicated by the same horizontal pointer as the connected component.
The point detected as "pixel" is stored as a start point, and the connected component of each row including "1-pixel" including this start point and continuous to this start point is detected and the same label value as the label value is given. The most significant bit of each point is cleared to zero, the above processing is executed until there are no starting points, and a group of connected components is labeled. When the labeling of this group of connected components is completed, the label values are consecutively set. The value is updated.

(Operation) First, the point detected as "1-pixel" by raster scanning based on the most significant bit of the image memory is stored as the starting point of the connected component. Next, the connected components of the current scan line, which is composed of "1-pixels" including this start point and continuous to this start point, are detected, and the same lower label is used for these connected components using the remaining lower bits of the image memory. Give a value and clear the most significant bit of each point to zero. By this zero clear,
The point once detected as "1-pixel" is prevented from being detected again. Next, raster scanning is performed for each of the upper row and the lower row of the current scan row, and the point detected as "1-pixel" within the range indicated by the same horizontal pointer as the connected component is used as the starting point. Remember. Then, the connected component of each row consisting of "1-pixels" including this start point and continuous to this start point is detected, the same label value as the label value is given, and the most significant bit of each point is cleared to zero.

The above processing is executed until there is no starting point to label a group of connected components, and each time the labeling of the group of connected components is completed, the label value is sequentially updated to a continuous value.

That is, in the present invention, when the start point is detected in the process of one raster scan of the screen, the connected component including the start point is detected, the same label value is given to the connected component, and then the label value is continuously added. The other connected components are detected by updating the value to the value that is set and continuing the raster scanning of the screen, and labeling is performed in the same manner as described above.

As a result, continuous and unique label values are given to each connected component.

(Example) An example of the present invention will be described below with reference to the drawings.

First, as shown in FIG.
Assuming that the value image 10 has a plurality of connected components 31A, 31B, 31C, the labeling process for the binary image 10 will be described in detail below with reference to FIGS. 2 and 3.

First, for example, the data of the binary image 10 consisting of "1-pixel" and "0-pixel" stored in the 16-bit image memory is transferred to the most significant bit of the same memory (third bit).
Figure step S1). Next, as shown by the arrow 21 in FIG. 1, raster scanning is started from the upper left of the screen and pixel values are sequentially read, and the point of "1-pixel", that is, the point where the most significant bit is not "0" is determined. Find (S2, S3). During this time, as long as the point of "0-pixel" with the most significant bit being "0" is detected, the pointer in the horizontal direction or the vertical direction is updated as described later (at step S12), and the entire screen is terminated. It is determined whether or not (at step S13).

In FIG. 2, if the point P _1S of “1-pixel” is detected in the current scanning line L ₁ in the previous step S3, this point is stored as a starting point (at step S4) and this starting point is taken out. At the same time (S5), as shown by arrow 22 in FIG. 1, scanning is performed until a point of “0-pixel” appears in the right direction, and the last “1-pixel” found in the current scan row L ₁ is displayed. Point P _1E
Is the end point (at the same S7). At this time, since the starting point P _1S is the starting point found for the first time, the determination shown in step S6 may be omitted, or there may be other starting points in the rows above and below the current scan row L _1. , The judgment result is no.

Then, the same label value, for example, "1" is added from the start point P _1S to the end point P _1E (at step S8). At this time, the label value is expressed with 15 bits, but writing is performed with 16 bits and the most significant bit is cleared to zero. That is, the most significant bit of the point once labeled is always "0",
This point is prevented from being detected again as "1-pixel".

Then, for the upper row L ₂ of the current scan row L ₁ scanned this time, the start point P _2S ′ indicated by the same horizontal pointer
To the end point P _2E ′ (from the left of the start point P _2S ′ to the right of the end point P _2E ′ when searching for 8 connected pixels), the pixel value is changed from “0-pixel” first. The point _P21S of "1-pixel" is stored as the next starting point (at step S9).

Here, for the previously labeled line L ₁ , its starting point is f
(I _S , j), end point is f (i _E , j) (i: horizontal pointer,
j: a pointer in the vertical direction, where i _S ≦ i _E ), the starting point of the search in the upper row L ₂ is f (i _S , j−1) and the ending point is f
_{(I E, j-1)} , ( in the case of searching the 8-connected pixels, the starting point _{f (i S -1, j-} 1), the end point _{f (i E + 1, j} -1)) becomes. Then, the next starting point f (i, j− in the upper row L ₂ is
As 1), the point that f (i−1, j−1) is “0” and f (i, j−1) is “1” (note that i _S ≦ i ≦ i _E ). Become. That is, in row L ₂ , from start point P _2S ′ to end point
Among the points of "1-pixel" in until P _2E ', of adjacent left point "0 pixels" a is a point P _21S is next starting point.

In addition, as shown in FIG. _2, the search start point P in the upper row L ₂ is
_{If 2S} ′ is a “1-pixel” point, then this point P _2S ′
Since there is a possibility that "1-pixel" points are continuous on the left side of, the scan from point P _2S ′ to the left causes “1
_-The point of "pixel" is sequentially set as a starting point candidate point _P22S ", and the last found point of" 1-pixel "(point adjacent to" 0-pixel ") _P22S is further stored as the next starting point. (Same as S9).

By the same method, starting also lower row L ₃ P _31S, P
Find _32S and memorize these (S10 of the same).

Next, the start points stored as described above are taken out one by one (at step S5), and after determining whether or not there are no more start points (at step S6), in the same way as in the case of row L ₁ , to the right, " 0-
With finding an end point by performing a scan to emerge in terms of pixel "is, these starting - put the same label and row L ₁ to a point" 1 pixel "multiple between end points (same S7, S8).

Then, for example, if the label in the row L ₂ is finished, perform a new search for the start point to the upper and lower rows of the row L ₂ although (same S9, S10) why the lower row L ₂ , That is, row L ₁ is labeled first and the most significant bit is “0”, so the search for the start point is effectively row L ₂
It is executed only for the upper row of. Similarly, row L ₃
The search for the starting point in is performed only on the lower row of row L ₃ .

Thus, when there are no remaining starting points, labeling of one connected component, for example, the connected component 31A in FIG. 1 is completed (S6).

After that, the label value is "2", which is a value consecutive to "1".
, And the horizontal and vertical pointers are updated (S11 and S12 in the same figure), the raster scanning is continued, and if a "1-pixel" point forming another connected component is found, The connected component is labeled by the method (S2
~ S12). While repeating the above processing, when the screen raster scan reaches the lower right of the screen, the label processing of one screen having the connected components 31A, 31B, 31C is completed (S1).
3).

According to this embodiment, 15 of the 16-bit image memory
Since each connected component is labeled using bits, if the label value “0” is excluded, 2 ¹⁵ −1 = 32767 label values can be given to the same number of connected components. Of course, if the number of bits of the image memory is increased, it becomes possible to give unique continuous label values to a larger number of connected components.

(Effects of the Invention) As described above, according to the present invention, binary image data is arranged in the most significant bit of the image memory, the remaining bits of the memory are used for the label value, and the screen raster scan and Since the continuous different label values are given to each connected component by combining the scans in the connected components, the label values are discontinuous or discontinuous with respect to many connected components forming the binary image. There is an advantage that labeling can be performed without becoming.

Further, in each connected component, by clearing the most significant bit of each labeled point to zero, when searching for the starting point of the lines above and below the labeled line, the labeled line is searched. It is possible to eliminate the waste of redundantly searching for and to speed up the labeling process.

In addition, according to the present invention, a label value is added when the connected components are scanned in the process of one raster scan of the screen, and the label values in the same connected component are not different. Therefore, the fifth
Unlike the prior art shown in the figure, in order to unify different label values in the same connected component given at one raster scan into the same value, it is not necessary to perform raster scan again. Therefore, prior to measurement and analysis using a binary image, preprocessing work such as classification of connected components by labeling can be performed easily and at high speed, and a series of measurement and analysis work using a binary image can be performed. It has an effect that it can be reduced and the work efficiency can be greatly improved.

[Brief description of drawings]

1 to 3 show an embodiment of the present invention,
FIG. 1 is an explanatory diagram of a binary image to be labeled, FIG. 2 is an explanatory diagram of start points and end points of the current scanning line and upper and lower scanning lines, and FIG. 3 is for explaining the operation of this embodiment. FIG. 4, FIG. 4 and FIG. 5 are explanatory diagrams of a binary image for explaining a conventional example. 10 …… Binary image, 31A, 31B, 31C …… Connected component L ₁ , L ₂ , L ₃ …… Scan line P _1S , P _21S , P _22S , P _31S , P _32S …… _Start point P _1E …… End point

Claims (1)

[Claims] 1. "1" depending on the presence or absence of a pixel in the image memory
-The binary image data composed of "pixels" and "0-pixels" is arranged in the most significant bit of the image memory, and "1-pixel" is detected by raster scanning of the screen based on the most significant bit. Is stored as a starting point, and the connected component of the current scan line that includes this starting point and that is continuous with this starting point and consists of "1-pixels" is detected, and the connected component is stored using the remaining lower bits of the image memory. To the same label value to zero-clear the most significant bit of each point, and then perform raster scanning for each of the upper row and the lower row of the current scan row, and the same horizontal pointer as the connected component. The point detected as "1-pixel" within the range indicated by is stored as a start point, and the label value is detected by detecting the connected component of each row consisting of "1-pixel" including this start point and continuous to this start point. Same as Is cleared to zero the most significant bit of each point while applying the label values, performs labeling of a group connected component by performing the above processing until the start point is eliminated,
A labeling method characterized in that the label values are updated to successive values each time labeling of this group of connected components is completed.