Parallelization of Connected-Component Labeling on TILE64 Many-Core Platform | Journal of Signal Processing Systems Skip to main content
Springer Nature Link
Log in

Parallelization of Connected-Component Labeling on TILE64 Many-Core Platform

  • Published:
Journal of Signal Processing Systems Aims and scope Submit manuscript

Abstract

Many-core technology is considering as a key to improve the performance of recent computer systems. To obtain good performance for a many-core system, exploiting parallelism in arithmetic level is not enough and the parallelization strategy must apply to both of hardware architecture and software. Due to the contention of shared hardware resource, the speedup ratio of a many-core system is usually much lower than the number of processor units. In this paper, we take connected-component labeling (CCL) as a data-intensive application and take TILE64 as a many-core platform to perform a fast linear-time two-scan algorithm for labeling connected components in grayscale-level images. In the first scan, the data partition parallelism is applied and each core in the many-core system assigns provision labels (PLs) to the object pixels in a sub-image and collects equivalence information to several tables. Two parallel modes, the cascade path mode and tree path mode developed for the second scan, when the representative labels (RLs) with the help of equivalence information replace the PLs. According to the experimental results, the 10 times of speedup, compared with the performance of the single core scenario, it is can be achieved when 32 processor units is activated. The experimental results also demonstrate that the efficiency of our implementation with TILE64 is superior to that of other parallel labeling platforms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10
Figure 11
Figure 12
Figure 13
Figure 14
Figure 15
Figure 16
Figure 17
Figure 18
Figure 19
Figure 20
Figure 21
Figure 22
Figure 23

Similar content being viewed by others

References

  1. Kim, D., Lee, V., & Chen, Y. K. (2010). Image processing on multicore × 86 architectures. IEEE Signal Processing Magazine, 27(2), 97–107.

    Article  Google Scholar 

  2. Slabaugh, G., Boyes, R., & Yang, X. Y. (2010). Multicore image processing with OpenMP. IEEE Signal Processing Magazine, 27(2), 134–138.

    Article  Google Scholar 

  3. Chen, L., Pan, Y., & Xu, X. H. (2004). Scalable and efficient parallel algorithms for Eculidean distance transform on the LARPBS model. IEEE Trans. on Parallel and Distributed Systems, 15(11), 975–982.

    Article  Google Scholar 

  4. Wang, Y. R., & Horng, S. J. (2004). Parallel algorithms for arbitrary dimensional Eculidean distance transforms with applications with reconfigurable optical buses. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 34(1), 517–532.

    Article  Google Scholar 

  5. Samet, H., & Tamminen, M. (1988). Efficient component labeling of images of arbitrary dimension represented by linear bintrees. IEEE Transactions on Pattern Analysis and Machine Intelligence, 10, 579.

    Article  Google Scholar 

  6. Dillencourt, M.B., Samet, H., Tamminen, M. (1992). A general approach to connected-component labeling for arbitrary image representations. Journal of the ACM.

  7. Chen, W., Giger, M. L., & Bick, U. (2006). A fuzzy C-means (FCM)-based approach for computerized segmentation of breast lesions in dynamic contrast-enhanced MR images. Academic Radiology (Academic Radiology), 13(1), 63–72.

    Article  Google Scholar 

  8. Wu, K., Koegler, W., Chen, J., Shoshani, A. (2003). Using bitmap index for interactive exploration of large datasets. SSDBM.

  9. Niknam, M., Thulasiraman, P., Camorlinga, S. A parallel algorithm for connected component labelling of gray-scale images on homogeneous multicore architectures. High Performance Computing Symposium (HPCS2010)

  10. Suzuki, K., Horiba, I., & Sugie, N. (2003). Linear-time connected-componentlabeling based on sequential local operations. Computer Vision and Image Understand-ing, 89, 1–23.

    Article  MATH  Google Scholar 

  11. Haralick, R. M. (1981). Some neighborhood operations (pp. 11–35). Reading: Plenum Press, Addison-Wesley.

    Google Scholar 

  12. Hashizume, A., Suzuki, R., Yokouchi, H., et al. (1990). An algorithm of automated rbc classification and its evalu-ation. Bio Medical Engineering, 28(1), 25–32.

    Google Scholar 

  13. Rosenfeld, A., & Pfalts, J. L. (1966). Sequential operations in digital picture processing. Journal of the ACM, 13(4), 471–494.

    Google Scholar 

  14. Lumia, R. (1983). A new three-dimensional connected com-ponents algorithm. Computer Vision, Graphics, and Image Processing, 23(2), 207–217.

    Article  Google Scholar 

  15. Shirai, Y. (1987). Labeling connected regions. Springer-Verlag.

  16. Chang, F., Chen, C. J., & Lu, C. J. (2004). A linear-time component-labeling algorithm using contour trac-ing technique. Computer Vision and Image Under-standing, 93, 206–220.

    Article  Google Scholar 

  17. TILERA Corporation (2010). TILE64TM processor—product brief, http://www.tilera.com/products/processors/TILE64.

  18. He, L., Chao, Y., & Suzuki, K. (2007). A linear-time two-scan labeling algorithm. IEEE International Conference on Image Processing, 5, 241–244.

    Google Scholar 

  19. He, L., Chao, Y., Suzuki, K. (2008) A run-based two-scan labeling algorithm. IEEE Transactions on Image Processing, 749–756.

  20. Tilera Corporation (2008) Tile processor architecture- technology brief. Available:http://www.tilera.com/sites/default/files/productbriefs/TILEPro64_Processor_PB019_v4.pdf.

  21. Kumar, P., Palaniappan, K., Mittal, A., Seetharaman, G. (2009). Parallel blob extraction using the multi-core cell processor. In Proceedings of the Advanced Concepts for Intelligent Vision Systems, 320–332.

  22. Oliveira, V. M. A., & Lotufo, R. A. (2010) A study on connected components labeling algorithms using GPUs. Workshop of Undergraduate Works, XXIII Sibgrapi, Conference on Graphics, Patterns and Images, September.

Download references

Author information

Authors and Affiliations

  1. Information and Communication Research Laboratories, Industrial Technology Research Institute, Hsinchu, Taiwan, 310, Republic of China

    Chien-Wei Chen, Yi-Ta Wu, Shau-Yin Tseng & Wen-Shan Wang

Authors
  1. Chien-Wei Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yi-Ta Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shau-Yin Tseng
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Wen-Shan Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Chien-Wei Chen.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chen, CW., Wu, YT., Tseng, SY. et al. Parallelization of Connected-Component Labeling on TILE64 Many-Core Platform. J Sign Process Syst 75, 169–183 (2014). https://doi.org/10.1007/s11265-013-0780-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11265-013-0780-0

Keywords

Search

Navigation