"Peeling" legacy area center
Xu Qingrong, this article (Wuhan University)
In the published books related to graphic image processing, there is almost no way to discuss the regional center, and there is no clear definition for the regional center, but it has a unique role in image processing and analysis. The peeling method proposed in this paper is similar to the algorithm such as image refinement or edge extraction, but there are also some important differences worth noting. The above situation is exactly the reason for this article.
Basic idea
Suppose: The area is closed, connected to the plane, no vacuum, and plastic, if it is placed under the regional communication conditions, the region is evenly "squeezed", so that the area gradually becomes small until the last point This is used as the center of the area. Obviously, the center point of this is certainly located inside the area, which is also what we expect.
The peeling method is based on the above hypothesis and is an simulation of the "extrusion" process.
The peeling method is generally divided: edge tracking peeling method, four-directional peeling method, eight peeling method three. The edge tracking peeling method is the process of repeated edge tracking (clockwise or counterclockwise) and "peeling" derogate. The latter two methods are based on the ranking scan, and the "peeling" peeled pixels in all directions are in turn. When the area is complex and large, the results of various methods may have a little difference.
Various peeling methods are similar to the raster (grating) data processing algorithm, which is similar to the image refinement of the linear elements (also known as the central shaft) algorithm.
Furthermore, the center of gravity (the average value of the total cell coordinates as the center of the region is also one of the regional methods, but when the region is contoured into a concave shape, the center may be located outside the area. The peeling method given herein can overcome this drawback.
Difference between the field of peeling method and image refinement algorithm
1. In the line-like image refinement algorithm, the "line end" of the axis must be retained, and the regional evaluation algorithm is not necessary.
2. The preliminary result of image refinement may be a "skeleton" composed of a plurality of line segments, which must be further treated, i.e., by "cutting" (also known as "burrs"), "trunk" (central axis). In the regional evaluation algorithm, since the "line end" is not considered, there is no "skeleton", and only one point remains (as the region center).
Regional requirements can also be used in image refinement procedures
It is also a choice for borrowing image refinement programs without another special area.
First use the refinement program to obtain the "skeleton" (it reflects the distribution of the area). Then, the method of "erosion" in the middle of the linear ends is used, and only one point is left as the center of the region. The whole process is actually: first image skeleton, and then "erosion" in the skeleton.
Basic rules of peeling
1. The table and in the form must be peeled from the edge (by looking for an edge image element by tracking the image edge tracking or ranking scan), only a pixel is peeled each time.
2. Alternately alternately peeled from multiple directions by four-way peeling or eight-directional peeling method, it should be peeled out in turn in turn, and cannot be peeled in the fixed direction.
3. Keeping the connection from starting to end, the area should be kept a whole, not divided by "peeling". Therefore, even the edge cells will affect the connectivity if the peeling is peeled, it should be temporarily retained. The discrimination of connectivity is shown below.
Image refinement is also subject to the above rules.
How to discriminate connectivity
Whether it is a peeling region or image refinement, it is necessary to discriminate and maintain the connectivity of the image.
The area is a binary image (the pixel gradation value is 1), and the pixel gradation value of 1 in the region is 1, and the image element gradation value outside the area is 0, any non-zero image element P and it. Number (0 ~ 7) of each pixel in the eight neighborhood is shown below. The eight neighborhoods are: P0, P1, P2, P3, P4, P5, P6, P7. Its corresponding grayscale value is represented by G0, G1, G2, G3, G4, G5, G6, G7. Figure 1 Eight neighborhoods
In the eight neighborhood, if each GI (i = 0, 1, ..., 7) is not all 0, 2 or more or more of each non-zero element (excluding pixel P) is not connected When the cake is brought, it will affect the connection between the region after peeling the pixel P, so the P pix element cannot be stripped. Conversely, if P is the edge cell, and the number of junctions is equal to 1, P does not affect the connectivity, and P is stripped.
Using n represents the number of cakes, the calculation formula of N is:
N = SUM [(1-GK) - (1-gk) (1-GK 1) (1-GK 2)]
(SUM is taking the sum; k = 0, 2, 4, 6; order g8 = g0)
How to achieve alternating "peeling" in all directions
Definition: As shown in FIG. Of course, P may be polyfromen, for example, p is both a pixel of 0- neighbor to 0, and a pixel 2-neighbor is zero. But this does not affect the process of the algorithm.
Take the four-way peeling method as an example, it can be stated that each round of "peeling" is alternate in the following order:
1. Scan the entire image, look for pixels each 0- neighbor 0, peeled off without affecting connectivity;
2. Scan the entire image, look for pixels each 2-neighbor 0, stripping it without affecting connectivity;
3. Scan the entire image, look for pixels of 4-neighbor 0, stripping it without affecting connectivity;
4. Scan the entire image, look for pixels each 6-neighbor 0, peeled off without affecting the connectivity;
After a round, if the stripped non-zero image is more than one, continue in the above order until the last point remains.
The order of scanning images is generally on the top and downwards (from left to right).
"Peeling" process diagram
Figure 2 is a schematic diagram of a four-way peeling process.
Figure 3 is a schematic view of an eight-directional peeling process using the same original image of Figure 2, which is identical to Figure 2.
Figure 4 is a schematic view of the peeling process using the edge tracking of the same original image of Fig. 2, and the result is also identical to Figure 2.
Figure 2 four-way peeling process
Figure 3 Overaction process
Figure 4 edge tracking peeling process
other
1. The results of the edge tracking peeling method, the four-way peeling method and the eight-way peeling method may not be the same, but the results of these methods are relatively close or equal when the region is not complex, and the area is small.
2. When designing a specific algorithm, it is possible to use different "peeling" sequences or scan sequences, and finally the result may also be the same, and this difference estimate is only within a few pixels.
3. The edge tracking peeling method can only be in a region. The four-way peeling or eight-directional peeling can be simultaneously in the region of the same screen.
4. Carefully observe the "peeling" process of the above-mentioned schematic, it seems that the edge tracking peeling method is more in line with the assumptions and basic idea of this article.
5. The edge tracking peeling method is not a simple "extraction edge-delete edge" recursive process, and the continuity of maintaining the regional image simultaneously in the peeling process.
6. The various regions given in this paper have been used to calculate the research topics in the European Continental Center.
Author published in 9CBS related articles:
Geographic direction of GIS graphics - a problem that is often overlooked
Design graphics software as required by "what you want"
Aliquot of isometric line - an important algorithm for an application
Vector drawing algorithm with "unrelated to graphics structure"
Add a new tool for the development of graphics software
Contact: Short information can be sent to XQR at the 9CBS forum.
