Research on Algorithm of Connected Region Labeling in Edge Images and Its Implementation with SoPC

Abstract: Aiming at the fact that there are few target points in binary edge images, an 8-direction growing region labeling algorithm based on the neighborhood of target pixels is proposed. This algorithm makes full use of the direction information of edge images, improves the search efficiency, reduces the stack space consumption, and eliminates the problem of repeated neighborhood scanning.
Keywords: connected region labeling ; edge image; region growing ; region merging ; SoPC

The connected component labeling algorithm is used to extract the target region from the image and calculate the characteristic parameters of the target region. It is a key step in target detection and target recognition [1]. It has been widely used in industrial inspection, optical character recognition, robot target tracking and other fields.
Among the current connected component labeling algorithms, the labeling algorithm based on equivalent labels needs to scan the image at least twice and deal with the labeling conflict problem. Its execution time is too dependent on the complexity of the connected region [2]. The labeling algorithm based on region growing only needs to scan the image once, has no labeling conflict problem, and has good adaptability to complex images. However, when the number of target points is large, the search efficiency is low and the stack space consumption is large.
The image labeled in this paper is a binary edge image obtained by edge detection. Compared with the original image (or its binary image), the edge image retains the contour information and the number of target points is greatly reduced, which is suitable for the region growing labeling algorithm. However, on the one hand, the existing region growing labeling algorithm requires an N×N window search for each target point, which has low search efficiency and may result in repeated scanning of the same pixel; on the other hand, if the search window is small (such as the most commonly used 3×3, also known as the 8-neighborhood), although there is less interference, the same connected area can easily be labeled as several different connected areas; and if the search window is increased (such as 7×7), although the connectivity of the obtained labeled image is good, more interference points will be introduced.

1 Region marking based on growth algorithm
The pixel set above, below, left, right, upper left, lower left, upper right, and lower right of pixel P is the 8-neighborhood of pixel P. All target points in the neighborhood belong to the same connected area. The 8-neighborhood growth rule is usually used to mark connected areas.

1.1 8-neighborhood region growing algorithm
Assume that the background pixel of the edge image is 255 and the target pixel is 0. The steps of marking the 8-neighborhood region growing are as follows:
(1) Scan the image from top to bottom and from left to right. When encountering the target pixel P, mark it with the new mark value L;
(2) Take P as the seed point and mark the target pixel in its 8-neighborhood as L;
(3) Mark all the target pixels adjacent to the L pixel in the 8-neighborhood as L until the connected region is marked;
(4) Continue to scan the image in sequence and repeat the first three steps until all the target pixels in the image are marked.
The starting point of each connected region is obtained by scanning the entire image in sequence, and the marking process of each connected region is the process of recursively calling the growth function. The growth function scans the 8-neighborhood of the target point in sequence. If a new target point is encountered, the processing process of the current target point is pushed onto the stack and the 8-neighborhood of the new target point is scanned instead. In this way, the target point is continuously pushed onto the stack. When there is no new target point in the 8-neighborhood of a target point, it is popped off the stack. When all the target points are popped off the stack, the connected region is marked.

1.2 Neighborhood Repeat Scanning Problem
In Figure 1, the 8-neighborhood of P0 overlaps with the 8-neighborhood of P1, P2, P3, and P4 by 4 pixels, and overlaps with the 8-neighborhood of P5, P6, P7, and P8 by 2 pixels. According to the above 8-neighborhood region growing algorithm, when P0 and P4 are both target points (assuming that the recursive process is transferred from P0 to P4), the 5 pixels of P0, P1, P8, P3, and P7 are scanned twice; when P0 and P5 are both target points (assuming that the recursive process is transferred from P0 to P5), the 3 pixels of P0, P1, and P2 are scanned twice.

1.3 8-Direction Neighborhood Growing Algorithm
The idea of ​​the 8-Direction Neighborhood Growing Algorithm is: target point A and target point B are adjacent, and there are 8 directions from A to B. When searching the 8-neighborhood from A to B in a certain direction, only the part of B's ​​8-neighborhood that is not covered by A's 8-neighborhood is searched. For example, in Figure 1, when searching the 8-neighborhood from P0 to P4, only P18, P04, and P37 are searched; when searching the 8-neighborhood from P0 to P5, only P05, P25, P01, P15, and P02 are searched. That is:

The 8-direction neighborhood growing algorithm consists of 9 growth functions. For the starting point of the connected area, 8 directions must be searched, and the main growth function is called at this time. In the process of target point transmission, according to its transmission direction, the corresponding growth function is called according to formula (1) to search for neighborhood points. The region marking starts from calling the main growth function from the starting point. The process is that the 8 growth functions call each other. Finally, when these functions return, the region marking is completed.
This method makes full use of the directional information from the target point A to the target point B, so that when searching the neighborhood of B, the number of searches is reduced to 3/8 or 5/8 of the original, and the average efficiency is improved by 50%.

1.4 Edge endpoints and region merging
When searching for connected areas using only the 8-neighborhood, the connected areas obtained are often incomplete and poorly connected. In Figure 2(a), the right half is a partial enlargement of the lower left part of the circle. When searching counterclockwise to the circled "11" in the figure, there is no new target point in its 8-neighborhood, so it is disconnected from the area "15". When a target point is searched, there is no new target point in its 8-neighborhood, then the point is the "end" of the edge. A region may have multiple ends.
In Figure 2(b), the right half is a partial enlargement of the center of the "米" character. The circled "4" point in the figure has a new target point (lower left point) in its 8-neighborhood, but the nearest "3" point is not in its neighborhood, so the two connected areas are disconnected. For edge images with a single pixel width, the direction is basically the same; the point with a large change in direction is the "inflection point" of the figure, and the phenomenon of regional disconnection is prone to occur at this time.

In Figure 1, assuming that the transmission order of the three target points is P0 to P5, and then P5 to P02, then P5 is heading to the turning point.
To improve connectivity, the search range can be increased, such as to a 7×7 range. Although this improves connectivity to a certain extent, it will introduce more interference points. The idea of ​​this paper is: first search for connected areas according to the above-mentioned 8-direction neighborhood growth algorithm, and record the edge "endpoints" at the same time, and then merge the two areas with closer endpoints by comparing the endpoints of each area. Combined with the analysis in the previous article, this paper believes that the edge endpoints include three categories: area starting point; edge end; edge turning point. The number of endpoints obtained in this way is small, and most of the "breakpoints" are included. By constantly comparing the endpoints of each area, the areas are merged if they are close, and finally the merged labeled image is obtained.
This method essentially searches for connected areas in a small scale, and uses the obtained edge endpoints to merge areas in a large scale, which does not introduce more noise, but improves the connectivity of the labeled image, and improves the efficiency of merging while ensuring the accuracy of area merging.

[page]
2 SoPC implementation of region marking and merging
This paper uses FPGA as the core and SoPC technology to implement the 8-direction growing connected region marking of 320×240 images. The system uses FPGA logic hardware for edge detection[3], uses NiosII soft-core processor for connected region marking, and uses Avalon bus to combine the two to achieve hardware acceleration and software and hardware collaboration, which not only improves real-time performance but also ensures flexibility.

2.1 Structural design of SoPC system
The system structure diagram is shown in Figure 3. The functions of the main modules are briefly described as follows:
(1) NiosII CPU module. This module is the center of the entire system operation and scheduling, and completes the control of the system workflow; the implementation of the region marking and region merging algorithms in image processing; and the implementation of the graphical user interface (GUI).
(2) Image module. The image acquisition part is responsible for collecting camera data in 320×240 size, and the DMA controller stores the original image data in DDR SDRAM through the Avalon bus. The edge detection part synchronously marginalizes the original image data, generates edge image data, and stores it in DDR SDRAM through the DMA controller and the Avalon bus.
(3) Display module. Responsible for driving the LCD display to display the original image, marked image, and processing information.

2.2 Algorithm implementation of region marking and merging
The image processing process is divided into three steps: connected region marking, region merging, and region sorting.
(1) Connected region marking: Connected regions are marked according to the improved 8-direction neighborhood growth algorithm. A linked list array element is assigned to each connected region, and the linked list is used to record the target points and endpoints of the connected region.
(2) Region merging: The endpoint linked lists of any two connected regions are compared one by one. Within a large scale range (9×9 range is used in this paper), if there are adjacent endpoints, the two connected regions are merged.
(3) Region sorting: According to the number of target points, the merged connected regions are sorted from large to small. The first N connected regions with target points greater than X are taken as the objects of subsequent feature extraction (the maximum value of N in this paper is 10, and the value of X is 20), and the rest are regarded as interference and removed. Taking N connected regions with larger shapes for the next step of feature extraction can save processing time.

3 Experimental results and analysis
This paper uses the cost-effective FPGA EP3C25F324C8 of the CycloneIII series of Altera. The SoPC system shares 8916/24624 (36%) logic units, 5 415 registers, 101 pins, 421 248/608 256 (69%) on-chip SRAM bits, 4 built-in multipliers, and 1 PLL phase-locked loop. The system clock is 100 MHz, and the performance of the NiosII soft-core processor is 113 DMIPS.
The experimental results are shown in Figure 4. Figure 4 (a) shows the experimental development board and camera, and Figures 4 (b), (c), and (d) are the experimental results of different images displayed on the LCD screen. The display is divided into three parts: the upper left part is the original grayscale image, with a size of 320×240; the lower left part is the marked image (different areas are displayed by different colors), with a size of 320×240; the right side is the processing information, with a size of 480×480. The processing information includes: Connection Num is the number of connected regions; Merge Num is the number of regions after merging; Region Num is the number of regions after sorting; Process Time is the image processing time, in ms.

The experimental results show that the labeled image obtained by the algorithm in this paper is correct, has clear edges, removes noise, and improves the connectivity of the region. When implemented on the SoPC system, the processing speed of complex images is about 30 frames/s, which meets the real-time requirements.
In this paper, the proposed 8-direction growing region labeling algorithm based on the neighborhood of the target pixel and the region merging algorithm based on edge endpoints are successfully implemented in the SoPC system. The experimental results show the effectiveness and real-time performance of the algorithm. In the image processing system based on SoPC technology, the software and hardware work together to improve the parallelism and flexibility of the system, with good portability and low cost.