Connected components labeling is an important operation in pattern recognition and computer vision [1], which is commonly adopted to detect connected regions in binary digital images. The labeling algorithm scans an image and groups its pixels into components based on pixel connectivity, and each component is assigned a unique label. According to the symbolic image, many features (numbers, areas, perimeters, centroid, enclosing rectangles, etc.) of objects in the image can be obtained in the later analysis. Therefore, labeling algorithm is widely used in target recognition and tracking, biological identification (such as fingerprint and face), automated inspection, character extraction, medical image analysis and other applications [2, 3].
Many labeling algorithms have been developed in the literature since the 1966[4], all of which yield to the same result: the number of labeled connected components is the same and consecutive labels can be achieved with a common enumeration procedure [5]. In this paper, we do not consider the parallel algorithms designed for specific processors, but the algorithms for ordinary computer architectures. Taking into account the number of scanning the input image while labeling, the labeling algorithms can be divided into the following three categories.
Best services for writing your paper according to Trustpilot
Multi-pass algorithms [6, 7] scan the image in the forward and backward raster directions alternately and propagate the labels until no label is changed. Though simple, the main drawback of these methods is the number of scans depends on the geometrical complexity of connected components. And they may require a large number of image scans before reaching the final labels, which leads to a long execution time. To reduce the passing times, Suzuki [8] proposed a linear-time labeling algorithm based on sequential local operations and demonstrated by experimentation that the labeling of almost any arbitrary images is completed by no more than four passes. However, it is still time-consuming when the image is very large in size.
Two-pass algorithms [4, 9-12] assign provisional labels to the foreground pixels in the first scan, and at the meanwhile, record the equivalence information among provisional labels. Then the equivalent labels are merged to determine the final labels. Finally, provisional labels are replaced by their representative labels while scanning the image at the second time. The differences between these algorithms lie in the way in which the image is scanned, the neighborhood is checked, and the equivalence information is resolved. Consequently, many approaches distinguished only in efficiency have been proposed, among which Wu’s search plus array-based union-find (SAUF) algorithm [13, 14], He’s fast connected component labeling (FCL) algorithm [15] and efficient first-scan (EFS) method [16] and Grana’s block-based decision tree labeling (BBDT) algorithm [5] are most efficient ones.
One-pass algorithms label the objects pixels by scanning the image only once. They search out an unlabeled object pixel, assign the same label to it and all the object pixels connected to it. Whereas, unlike the label-equivalence-based algorithms that access the image in a regular way, one-pass algorithms usually process the image in an irregular pattern. Thus they are not suitable for hardware implementation because of many irregular memory accesses. For example, Abu- Baker’s region growing based labeling algorithm [17] usually needs to search the neighbor pixels repeatedly, and the stack data structure results in irregular access of pixels which has slow performance in practice. Chang’s contour tracing (CT) algorithm [18] search and label the pixels of one object contours and propagate the label to the internal pixels. It is the most efficient one-pass algorithm in literature, but is not suitable for images with objects of complicated geometrical shape and still slower than efficient two-pass algorithms, for example, the FCL method.
In terms of efficiency, two-pass approaches outperform the others. Therefore, in this paper, we combine the efficient first scan method of He (EFS)[16] with the array-based union-find data structure of Wu (SAUF)[13, 14] to form a new faster two-pass labeling algorithm. Tests have been carried out on different datasets to evaluate the scalability and effectiveness of the hybrid algorithm, and the experimental results indicate that it is faster than the existing approaches when labeling the large images without too much label equivalences.
Remaining of this paper is organized as follows. A brief review of three most efficient two-pass labeling algorithms so far is given in the next section. In section 2, the proposed combinative algorithm is described in details. Section 3 outlines the experimental conditions and discusses experimental results of our method as compared with the three algorithms in Section 1. And Section 4 is devoted to the conclusions.
1 Most Efficient Algorithms
In this section, we introduce three most efficient labeling algorithms: EFS, SAUF and BBDT. For convenience, we assume that the input images are binary images (foreground pixels and background pixels are represented by 1 and 0, respectively) with zero borders and consider only the eight-connectivity. We useto denote the input image andfor the symbolic image. For the general label-equivalence-based algorithms, the mask used in the first scan is shown in Fig. 1. To speedup the labeling procedure, there are two common strategies. One is to reduce the average number of times for checking the processed neighbor pixels in the first scan, and the other is to resolve the label equivalences quickly by an efficient data structure.
The mask used in general label-equivalence-based algorithms (is the current pixel)
He’s EFS method process the foreground pixels following a background pixel and those following foreground pixels in a different way, which can reduce the average number of neighbors accessed from 2.25 to 1.75. During the first scan, for each current foreground pixel, we have already known whether the previous pixel is a foreground pixel or not, thus, it can be removed from the mask. Therefore, the mask used here consists of only the three processed neighbor pixels of the current foreground pixel in the row above,, and (that is, , and), as shown in Fig. 2. For processing a current foreground pixel following a background pixel, the same method as proposed in FCL [15] is used. While, for the current foreground pixel following another foreground pixel, the label of its previous foreground pixel is assigned to it, and the left thing needed to do is only to check whether this label is equivalent to the label assigned to pixel .
To resolve label equivalences between provisional labels, this algorithm adopts an equivalent label set to hold all the provisional labels assigned to a connected component and the smallest label is taken as the representative label. When a new provisional labelis generated, the corresponding equivalent label set is established as, and the representative label is set to itself, i.e.. Whenever label equivalence occurs, say, andin the mask belong to different setsand separately, these two sets are merged together, and their smallest label is regarded as their representative label. They took three simple one-dimensional arrays to implement this process without using pointers, but the drawback is that when a set with more elements is merged into a set with fewer elements, the resolve procedure will cost much time. Anyway, EFS is a most efficient pixel-based scan strategy so far.
Wu et al. [13, 14] proposed two optimization strategies to improve connected components labeling algorithms. The first strategy employs a decision tree (see Fig.3) to minimize the number of neighboring pixels accessed in the scanning phase, and the second one streamlines the Union-Find algorithm to track equivalent labels. In the forward scan mask,, andare all neighbors of , hence if is an object pixel, the other three pixels are not needed to be accessed. When the label equivalence information is recorded, it is possible to derive the
The mask used in EFS method (e is the current pixel)
correct label of (and therefore that of ) later. If is a background pixel, the order to check other pixels in the mask is given as a decision tree shown in Fig.3. Various tests demonstrated that this decision tree reduces the number of neighboring pixels visited from 4 to 7/3 on average, which is still bigger than EFS method.
The decision trees used in scanning for 8-connected neighbors (a, b, c, d are neighbors of current pixels e as shown in Fig.1(a))
Whereas, as to dealing with the label equivalence problem, Wu’s array-based Union-Find data structure is more efficient than He’s label sets method for the images with large amounts of connected components in practice. To reduce the random accesses which are the main reason that affects the performance of most Union-Find algorithms [19], they exploited a single arrayto implement the Union-Find algorithm with path compression, a way of flattening the structure of the tree whenever a Find operation is used on it. For every pair of equivalent labels, a path compression is performed to compute their root, say, keep the element of arrayas the representative label of provisional label. It can be proved that their Union-Find approach takes a linear time (even in the worst case) to perform anyUnion and Find operations in the connected components labeling algorithms. Our experiments reveal its excellent performance in resolving the label equivalence problem.
As far as we write, the BBDT algorithm [5] proposed by Grana et al. represents the state of the art for connected components labeling. They proposed an efficient modeling of the problem by means of decision tables. An automatic procedure to synthesize the optimal decision tree from the decision tables is used, providing the most effective conditions’ evaluation order. With the automatically generated decision tree, this approach scans the image using 2A-2 pixel blocks, which lead to significant performance improvements of the neighborhood exploration in terms of memory access times. The mask used in this paper is shown in Fig.4. The advantage of this scanning procedure is that four pixels can be labeled at the same time and much fewer union operations are needed. At the meanwhile, the decision tree algorithm can optimize the problem of increasing computational time caused by the standard procedure. However, this scanning method may check the same pixel multiple times, and a second scan is required to check which pixels in the block should be labeled. These additional works bring extra execution time. In addition, the program of this algorithm is more complex because of multiple alternative actions.
The Mask used in 2A-2 BBDT algorithm. (a) Gives the identifiers of the single pixels employed in the algorithm, while (b) provides the blocks identifiers.
2 The Proposed Hybrid Algorithm
On the basis of the analysis above and our own experiments, we find that He’s EFS method is faster than other pixel-based scanning procedure and Wu’s array-based union-find data structure is more efficient in the label equivalence resolution. Therefore, we combine these two fast strategies to form a new labeling algorithm.
We use the mask shown in Fig.2 in this paper. In the first scan, for the current object pixel following a background pixel, its provisional label can be assigned by the following procedure:
Procedure 1:
if (b= =1) L[e]=L[b];
else if (a= =1)
{
L[e]=L[a];
if (c= =1 and L[e]!=L[c])
L[e]=union(L[e], L[c]);
}
else if (c= =1)
{
L[e]= =L[c];
}
else
{
L[e]=NewLabel;
R[NewLabel]=NewLabel;
NewLabel++;
}
While for the current object pixelfollowing another object pixel, is assigned simply by this procedure:
Procedure 2:
L[e]=L[d];
if (b= =0 and c!=0 and L[e]!=L[c])
{
L[e]=union(P, L[e], L[c]);
}
In these two procedures above, function is the same as proposed by Wu [15]. It always sets the root of the combined tree with the smallest label and changes all nodes on the find path to point the new root directly, i.e., the array element is the representative label of provisional label . Thus, the number of random memory access is greatly reduced and we can invoke the procedure to obtain successive final labels.
After the first scan, all the equivalences between the provisional labels have already been solved. And then we can relabel the image through a second scan to get the final symbolic image.
3 Experiments and Discussions
3.1 Experimental conditions
To evaluate the performance of the new algorithm, we make comparisons with most efficient labeling algorithms (BBTD, EFS, SAUF) described in Section 1. We got the programs of the BBDT algorithm from the authors’ web site, and wrote the others according to the original articles. All the algorithms’ codes implemented in C++ language are integrated into one project based on the program of BBDT algorithm, and compiled on Windows using Visual Studio 2008. The tests have been performed on a notebook (Intel Pentium Dual-Core T4300 processor (2.1GHz), 2GB Memory, Windows XP SP3 OS), using a single core for the processing. All algorithms produced the same consecutive labels on all images.
Images used in this paper are composed of 80 digital photographs of 3264A-2448 pixels, 110 satellite images of different sizes collected from Google Earth, 720 random noise sequence images as described in [5], 109 Brodatz texture images of 640A-640 pixels, 80 fingerprint images of 256?364 pixels, and some other images obtained form the Standard Image Database (SIDBA), CCITT, and the USC-SIPI Image Database, as in [15]. All the images were binarized by means of Otsu’s threshold selection method.
3.2 Results and discussions
Since all the labeling algorithms yield to the same result, we take the efficiency as the only criterion to measure their performance. All the data of execution time are average of 1000 runs. Firstly, we carried out the same comparison as [5] on the noise image dataset to evaluate the performance of the four algorithms. We can see from Fig.5 (a) that these four labeling algorithms are all linear versus image size, and that with the image size increases, the proposed algorithm runs more steadily than others. Fig.5 (b) indicates that our algorithm is superior to the rest when the noise density is low or very high (i.e. the geometrical shape of connected component is not very complex).
Performance of four labeling algorithms on random noise images. (a) Gives result for noise images of eight sizes (32A-32, 64A-64,aˆ¦, 4096A-4096 pixels) and for each size, 80 images with different densities (from 0.1 to 0.9) are used; and (b) shows the average execution time for the images of 4096A-4096 pixels with different foreground pixel densities.
Various kinds of natural images with different sizes were used to test the performance of the four labeling algorithms, as shown in Fig.6 and Table 1. Fig.6 illustrates the performance for the images of different types, that is, fingerprints, texture images, misc images from USC, CCITT, digital photos and remote sensing images. It can be seen from Fig.6 that for the small images with many small connected components, these four algorithms have similar performance, and the new algorithm is just a little slower than BBDT algorithm, such as Fig.6 (a), (b) and (c). While for large images with many large components, our approach is superior to others, such as Fig.6 (d), (e) and (f). The time listed in Table 1 is the total execution time for each kind of images. We can see that proposed method gets a higher performance boost (15%) over the BBDT algorithm for large images with larger connected components, for example, remote sensing images and digital natural photos. While for the small images with many small complex components, BBDT algorithm is still the excellent.
Fig.7 gives six selected images in our test, and the foreground pixels are displayed in white. Based on the results in Table 2, our algorithm is fastest for labeling large images.
Performance for natural images of different types and sizes, expressed by millionsecond. For the image of different sizes, images with larger index are larger in size.
Total execution time of labeling different natural images
The main reason for the results mentioned above is that for large connected components, the advantage of the scan procedure is brought into full play. Because there are many long runs in large components, and the Procedure 2 in Section 2 is implemented more frequently than Procedure 1, which saves a lot of execution time by reducing the times of neighbor accesses. However, for the small images with many small complex components, Procedure 1 will be carried out more often, and
Example images tested in this paper.
Test results for images illustrated in Fig.7. (ms)
much more neighbor pixel checks are needed in the scan stage, which slows down the new method. Furthermore, the path compression technique employed in the single array-based Union-Find algorithm works efficiently for merging equivalent temporary labels.
4 Conclusion
In this paper, we study the most efficient connected component labeling algorithms and propose a new fast two-pass labeling approach. In the first scan, foreground pixels are assigned provisional labels using He’s efficient scan procedure, and once a label equivalence occurs, it will be resolved by Wu’s array-based union-find algorithm. In the second scan, all the provisional labels are replaced by their representative labels. Large amounts of experiments on various images of different sizes indicate that our algorithm is more efficient than existing most efficient approaches for images with high resolution and many big connected components.
References?s
A. Rosenfeld and A.C. Kak, Digital Picture Processing, Academic Press, 2nd ed, New York, 1982.
Yapa, R. D. and H. Koichi, “A connected component labeling algorithm for grayscale images and application of the algorithm on mammograms,” Proceedings of the 2007 ACM symposium on Applied computing Korea, ACM New York, NY, USA, 2007, 146-152.
Yun-fang, Z., “Background Subtraction and Color Clustering Based Moving Objects Detection,” International Conference on Information Engineering and Computer Science, 2009, ICIECS 2009, 2009, 1-5.
A. Rosenfeld, J.L. Pfalts, “Sequential operations in digital picture processing, ” J. ACM, 1966, 13(4): 471-494.
Costantino Grana, Daniele Borghesani and Rita Cucchiara, “Optimized Block-Based Connected Components Labeling With Decision Trees,” IEEE Trans. On Image Processing, 2010, 19(6): 1596 – 1609.
R. M. Haralick, “Some neighborhood operations,” in Real Time/Parallel Computing Image Analysis, New York: Plenum, 1981, 11-35.
A. Hashizume et al., “An algorithm of automated RBC classi¬?cation and its evaluation,” Bio Med. Eng., 1990 28(1): 25-32.
Suzuki K, Horiba I, Sugie N., “Linear-time connected-component labeling based on sequential local operations,” Comput Vis Image Underst, 2003, 89(1): 1-23.
R. Lumia, L. Shapiro, O. Zungia, “A new connected components algorithm for virtual memory computers,” Comput. Vision Graphics Image Process, 1983, 22(22): 287-300.
R.M. Haralick, L.G. Shapiro, Computer and Robot Vision, vol. I, Addison-Wesley, Reading, MA, 1992, 28-48.
S. Naoi, “High-speed labeling method using adaptive variable window size for character shape feature,” in: IEEE Asian Conference on Computer Vision, 1995, 1, 408-411.
L. He, Y. Chao, and K. Suzuki, “A run-based two-scan labeling algorithm,” IEEE Trans. Image Process, 2008, 17(5): 749-756.
K. Wu, E. Otoo, and A. Shoshani, “Optimizing connected component labeling algorithms,” in Proc. SPIE Conf. Med. Imag., 2005, 5747: 1965-1976.
K. Wu, E. Otoo, and K. Suzuki, “Optimizing two-pass connected-component labeling algorithms,” Pattern Anal. Applic, 2009, 12(2): 117-135.
Lifeng He, Yuyan Chao, Kenji Suzuki, and Kesheng Wu, “Fast connected-component labeling,” Pattern Recognition, 2009, 42(9):1977-1987.
Lifeng He, Yuyan Chao, and Kenji Suzuki, “An efficient first-scan method for label-equivalence-based labeling algorithms,” Pattern Recognition Letters, 2010, 31(1): 28-35.
Ayman AbuBaker, Rami Qahwaji, Stan Ipson, and Mohmmad Saleh. “One scan connected component labeling technique,” IEEE International Conference on Signal Processing and Communications (ICSPC2007), 1283-1286.
F. Chang and C. Chen, “A component-labeling algorithm using contour tracing technique,” in Proc. Int. Conf. Document Anal. Recog., 2003, 741-745.
C. Fiorio and J. Gustedt, “Memory management for union-find algorithms,” in Proceedings of 14th Symposium on Theoretical Aspects of Computer Science. Springer-Verlag, 1997, pp. 67-79.
