JPH0727567B2 - Area detection method of connected figure - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Industrial field of use] The present invention relates to a method for detecting the area of a connected figure used when, for example, a three-dimensional structure is analyzed or inspected based on information of an object section or a projection plane, More specifically, it relates to a method for detecting the area of a connected figure used for analyzing a figure in a binary image.

[Prior art]

The following two methods have been known as methods for detecting the area of the connected figure by labeling the figure pixels included in the binary image.

The first method first detects one graphic pixel in a raster scan and labels that pixel. Then, the pixels that are connected to the detected pixel and are the figure are sequentially labeled with the same label as the detected pixel for each pixel. Next, the number of pixels having the same label is counted and the counted value is used as the area of the connected figure.

In addition to the method described above, there is also a method of storing the attached labels and integrating the labels to be connected. All pixels that are figures among pixels in the vicinity of a pixel that is detected as a figure by raster scanning are labeled with different labels. Then, the label for each figure is saved, and the connected state of the labels (that is, which label is adjacent to which label) is checked. Next, the same image is raster-scanned again, the connected labels are treated as the same label, and the connected labels are integrated to detect the connected figure, and the number of pixels (that is, the number of labels) forming the connected figure is counted. The counted value is taken as the area of the connected figure.

[Problems to be solved by the invention]

However, since all the methods described above are batch processing on an image, a large amount of memory is required to store the contents of all pixels (graphic or non-graphic, or labels attached), and real-time processing is not possible. There was a problem that it was possible.

The present invention has been made in view of such circumstances, and it is an object of the present invention to label each pixel while scanning a binary image, while immediately preceding and next to the immediately preceding pixel and the scanning line one line before. This is done based on the label of only pixels, and at the time of this labeling, the label of the graphic pixel connected to the label for each attached label and the pixel number of the label are saved, Provide a method for detecting the area of a connected figure that requires only a small amount of memory and can be processed in real time by summing up the pixel points of the connected labels with reference to the label and using the total value as the area of the connected figure. To do.

[Means for solving problems]

A method for detecting the area of a connected figure according to the present invention is a method for detecting an area of a connected figure constituted by connecting figure pixels of a binary image composed of figures and background pixels by labeling each figure pixel. While raster-scanning each pixel of the binary image, each pixel is sequentially labeled by checking the label of only the immediately preceding pixel and the pixel immediately above and in the next order in the scan line one line before, and the pixel immediately above. Is a figure, and if the pixel to be labeled is the background, the label of the pixel immediately above is stored as that of the pixel to be labeled, and this stored content is used for labeling. The connection relationship and the number of pixel points of each label are stored, and the total number of pixel points of the labels to be connected is counted based on the stored connection relationship to detect the area of the connected figure. To.

[Action]

According to the present invention, while rasterizing a binary image, the labels of only the immediately preceding pixel and the pixels immediately above and in the next order in the scanning line one line before are checked to sequentially label each pixel in real time. The label connection and the number of pixel points of each label are saved for each attached label, and the number of pixel points of the labels to be connected is totaled with reference to the stored connection relationship.

〔Example〕

The present invention will be described below with reference to the drawings showing an embodiment thereof.
FIG. 1 is a schematic view of a part of a binary image, in which black pixels are graphic pixels and white pixels are background pixels. In FIG. 1, (a), (b), (c) are shown. There are three connected figures.

First, each line in the drawing is sequentially scanned from the uppermost line in the horizontal direction (from left to right) to label the pixels of the figure. The top line has no graphics, so no pixels are labeled. Then, each pixel is labeled, and at the same time, the labeled label is stored in the label buffer. FIG. 2 shows the contents of the label buffer of the uppermost line after the scanning of the uppermost line is completed. Note that FF represents the contents of the label buffer of unlabeled pixels, and none of the pixels on the top line are labeled, so that the contents of the label buffer shown in FIG. 2 are FF for all pixels.

FIG. 3 is a schematic diagram showing the positional relationship between adjacent pixels to be checked when labeling pixels, and the pixel in the figure is the pixel to be labeled. In the present invention, reference is made only to the labeling of the pixel to be processed e, a, i and u. 3. The label of the pixel is referred to in order to facilitate the understanding of the present invention. First, the method will be described. Considering the scanning direction, the pixels a, a, u, and d have been scanned and labeled, and the labeled label is stored in the label buffer.

Pixel O is a figure, and the four neighboring pixels (A, I,
If any label other than FF is stored in the label buffer for any one of (c) and (d), the label is labeled as the label of pixel e. Here, the priority pixel order of the label buffer to be referred to when labeling the pixel e is the order of d, a, a, and u, and the contents of the label buffer are referred to in the order of pixel d, a, i, and c. If a label other than FF is stored, the label is set as the pixel label. On the other hand, if the pixel is a figure and the contents of the label buffer of 4 pixels are all FF, a new unused label is labeled as the label of the pixel e. Then, the label attached to pixel E is stored in the label buffer as the label of pixel E. Of course, if the pixel E is a background pixel, the pixel E is not labeled. If pixel E is the background and pixel A is a figure, the contents of the label buffer of pixel A are saved as the contents of the label buffer of pixel E. If pixel O is the background and pixel B is the background, the content of the label buffer for pixel E is FF.

That is, the label of each pixel is the label of the adjacent figure after the labeling process, and if there is no label, it is an unused label. Then, for the labeled pixels, the label is stored in the label buffer, and the label stored in the label buffer is used as the label for the above-described labeling.

When the pixel a is a figure and the pixel d is the background, as described above, in the process of one pixel before (when the pixel d is the labeling target pixel), the labeling target pixel (previously Since the contents of the label buffer of the pixel immediately above (previous a, current a) are stored in the label buffer of (e, current d), when labeling the pixel (i, u, d) Only the reference is sufficient, and the reference of A becomes unnecessary. That is, the label of pixel A can be known from the contents of the label buffer of pixel D. Just in case, if both the pixels a and d are the background, only the reference of the pixel d is enough. That is, if pixel D is the background, pixel A is also the background, and both pixels are irrelevant to the labeling of pixel E. Even if both the pixels a and d are figures, the pixels a and d cannot be different labels, so it is sufficient to refer to only the pixel d. Therefore, the content of the label buffer to be referred to is substantially 3 pixels (pixels a, u, and d).

According to the present invention, in the case where the pixel to be labeled is the background and the pixel immediately above is the graphic in this way, the label immediately above is stored in real time using only the three pixels a, u and d. Labeling is done.

On the other hand, in parallel with this labeling process, the connection state of the labels (which label has been connected to the label) is checked, and the contents are stored in a memory (not shown). Further, every time each pixel is labeled, the number of graphic points of each label is counted and the contents thereof are stored in the memory in the same manner as the contents of the connected state.

FIGS. 4 and 5 are a schematic diagram of the label when scanning and labeling are completed up to the 7th line of FIG. 1 and a schematic diagram of the contents of the label buffer of the 7th line. Further, FIG. 6 is a schematic diagram showing the contents (the connected state of the label and the number of graphic points of the label) stored in the memory when scanning and labeling up to the 7th line in FIG. 1 are completed.

The labeling process, the connection state saving process, and the graphic point counting process described above are sequentially performed for each pixel after the eighth line.

FIG. 7 is a schematic diagram showing the label state when all the pixels in FIG. 1 are scanned and labeled, and FIG. 8 is a schematic diagram showing the contents similarly stored in the memory.

Next, the area of the connected figure is detected based on the contents stored in the memory. According to the contents of the connection state of FIG. 8, since the labels (A, B) (C, D, E, G, H) (I, J) are labels that are connected to each other, the pixel having the label is one connection. It is a constituent pixel of a figure. Then, when the total number of graphic points of each label is counted, it becomes 29 points, 25 points and 9 points, and the connected figures (a), (b) and (c) become 29 points, 25 points and 9 points respectively. The area of the figure can be detected.

〔effect〕

As described in detail above, in the present invention, while scanning each pixel,
Since each pixel is labeled by referring to the contents of the label buffer of only the immediately preceding pixel and the pixels immediately above and in the next order in the scanning line one line before, the memory for labeling can have a small capacity.

In addition, since the connection state and the number of graphic points for each label are stored and the number of graphic points of the connected graphic is counted based on the connection state of the labels, it is not necessary to store the contents of all pixels in the memory, and the memory can have a small capacity.

Further, the area of the connected figure can be detected in the time required to scan all the pixels for one round, and the real-time processing can be performed. Further, along with this, area detection can be performed at high speed. Further, according to the present invention, a portion in which a figure is diagonally adjacent to each other in the right downward direction (for example, B on the right side of the fourth column in B of FIG. 7)
It is also possible to label as a connected figure even in the part that runs from to the lower right side), and such a part can also detect the correct area as a connected figure.

[Brief description of drawings]

FIG. 1 is a schematic diagram of a binary image, FIG. 2 is a schematic diagram of the contents of the label buffer on the top line in FIG. 1, and FIG. 3 is a schematic diagram of an image for explaining labeling in the method of the present invention. FIG. 4 is a schematic diagram of labels up to the 7th line of FIG. 1, FIG. 5 is a schematic diagram of the contents of the label buffer of the 7th line of FIG. 1,
FIG. 6 is a schematic diagram showing the contents of the memory at the end of line scanning of FIG. 1 and FIG. 7, FIG. 7 is a schematic diagram of the label at the end of scanning all the pixels of FIG. 1, and FIG. FIG. 9 is a schematic diagram showing the contents of the memory when the scanning of all the pixels is completed.

Claims (1)

[Claims] 1. A method for detecting the area of a connected graphic formed by connecting graphic pixels of a binary image composed of a graphic and a background pixel by labeling each graphic pixel and detecting each pixel of the binary image. Each pixel is sequentially labeled by checking the labels of the immediately preceding pixel and the pixels immediately above and in the next order in the scanning line one line before, while raster scanning the pixels, and the pixel immediately above is the figure, the pixel to be labeled. If is the background, the label of the pixel immediately above is stored as the label target pixel, and this stored content is used for labeling, and the connection relationship between each labeled label and the pixel of each label is stored. A method for detecting the area of a connected figure, characterized in that the area of the connected figure is detected by storing the number of points and the total number of pixel points of the labels to be connected based on the stored connection relation. Law.