A parallel pipeline connected-component labeling method for on-orbit space target monitoring

doi:10.23919/JSEE.2022.000107

Journal of Systems Engineering and Electronics ›› 2022, Vol. 33 ›› Issue (5): 1095-1107.doi: 10.23919/JSEE.2022.000107

• DEFENCE ELECTRONICS TECHNOLOGY • Previous Articles Next Articles

A parallel pipeline connected-component labeling method for on-orbit space target monitoring

Zongling LI^1,²(), Qingjun ZHANG³(), Teng LONG¹(), Baojun ZHAO^1,*()

¹ School of Information and Electronics, Beijing Institute of Technology, Beijing 100081, China
² Institute of Spacecraft System Engineering, China Academy of Space Technology, Beijing 100094, China
³ Institute of Remote Sensing Satellite, China Academy of Space Technology, Beijing 100094, China

Received:2022-03-03 Accepted:2022-08-09 Online:2022-10-27 Published:2022-10-27
Contact: Baojun ZHAO E-mail:leezl0519@163.com;ztzhangqj@163.com;longteng@bit.edu.cn;zbj@bit.edu.cn
About author:|LI Zonglingwas born in 1985. He is currently pursuing his Ph.D. degree in the School of Information and Electronics, Beijing Institute of Technology, Beijing, China. He is currently a senior engineer with the Institute of Spacecraft System Engineering. His research interests include satellite system design, space-borne computer design, and high-speed radar signal processing. E-mail: leezl0519@163.com||ZHANG Qingjun was born in 1969. He received his Ph.D. degree from Huazhong University of Science and Technology from 1993 to 2005, he designed spacecraft surveying and control subsystem and designed spacecrafts ’ rendezvous and docking scheme as a chief designer with China Aerospace Science and Technology Corporation. Since 2012, he has been a chief designer with the Beijing Institute of Spacecraft System Engineering, for Landsat Series Satellites and Gaofen-3. His research interest includes synthetic aperture radar satellite system design and application. E-mail: ztzhangqj@163.com||LONG Teng was born in 1968. He received his B.S. degree from the University of Science and Technology of China, Hefei, China, in 1989, and M.S. and Ph.D. degrees from Beijing Institute of Technology (BIT), Beijing, China, in 1991 and 1995, respectively. He became a full professor at the Department of Electronic Engineering, BIT, in 2000. He was a visiting scholar with Stanford University, Stanford, CA, USA, and University College London, London, U.K., in 1999 and 2002, respectively. From 2009 to 2016, he was the Dean of the School of Information and Electronics, BIT. Since 2019, he has been the President of BIT. He is an Academician of Chineses Academy of Engineering. He has authored or coauthored more than 300 articles. His research is mainly about synthetic aperture radar (SAR) systems and real-time digital signal processing, with applications to radar and communication systems. E-mail: longteng@bit.edu.cn||ZHAO Baojun was born in 1960. He received his Ph.D. degree in electromagnetic measurement technology and equipment from Harbin Institute of Technology, Harbin, China, in 1996. From 1996 to 1998, he was a postdoctoral fellow at Beijing Institute of Technology (BIT), Beijing, China. Currently, he is a full professor, Vice Director of Laboratory and Equipment Management, and Director of the National Signal Acquisition and Processing Professional Laboratory. His research is mainly about the theory and technology of multi-spectral image fusion, recognition and tracking, real-time compression, restoration and transmission of high-resolution images. E-mail: zbj@bit.edu.cn

Abstract

Abstract:

The paper designs a peripheral maximum gray difference (PMGD) image segmentation method, a connected-component labeling (CCL) algorithm based on dynamic run length (DRL), and a real-time implementation streaming processor for DRL-CCL. And it verifies the function and performance in space target monitoring scene by the carrying experiment of Tianzhou-3 cargo spacecraft (TZ-3). The PMGD image segmentation method can segment the image into highly discrete and simple point targets quickly, which reduces the generation of equivalences greatly and improves the real-time performance for DRL-CCL. Through parallel pipeline design, the storage of the streaming processor is optimized by 55% with no need for external memory, the logic is optimized by 60%, and the energy efficiency ratio is 12 times than that of the graphics processing unit, 62 times than that of the digital signal proccessing, and 147 times than that of personal computers. Analyzing the results of 8756 images completed on-orbit, the speed is up to 5.88 FPS and the target detection rate is 100%. Our algorithm and implementation method meet the requirements of lightweight, high real-time, strong robustness, full-time, and stable operation in space irradiation environment.

Key words: Tianzhou-3 cargo spacecraft (TZ-3), connected-component labeling (CCL) algorithms, parallel pipeline processing, on-orbit space target detection, streaming processor

Zongling LI, Qingjun ZHANG, Teng LONG, Baojun ZHAO. A parallel pipeline connected-component labeling method for on-orbit space target monitoring[J]. Journal of Systems Engineering and Electronics, 2022, 33(5): 1095-1107.

Figures/Tables 20

Fig 1

Fig 2

Fig 3

Fig 4

Fig 5

Fig 6

Fig 7

Fig 8

Fig 9

Fig 10

Table 1

Fig 11

Fig 12

Fig 13

Fig 14

Fig 15

Fig 16

Fig 17

Table 2

Table 3

References 43

1	GUL T, GUZIN U, BESTE U, et al Ciratefi based copy move forgery detection on digital images. Multimedia Tools and Applications, 2022, 81, 22867- 22902. doi: 10.1007/s11042-021-11503-w
2	ONSHAUNJIT J, SRINONCHAT J Algorithmic scheme for concurrent detection and classification of printed circuit board defects. CMC-Computers, Materials & Continua, 2022, 71 (1): 355- 367.
3	BARIS G, GURAY S Recognition of dynamic objects from UGVs using interconnected neural network-based computer vision system. Automatika, 2022, 63 (2): 244- 258. doi: 10.1080/00051144.2022.2031539
4	KH A, GDW B, KPY A Informed component label algorithm for robust identification of connected components with volume-of-fluid method. Computers & Fluids, 2020, 197 (1): 104373.
5	YANG G, ZHENG W P, CHE C H Graph-based label propagation algorithm for community detection. International Journal of Machine Learning and Cybernetics, 2020, 11 (6): 1319- 1329. doi: 10.1007/s13042-019-01042-0
6	YAN J, ZHOU L M, RAGHAVENDRA A Observed changes in fire patterns and possible drivers over Central Africa. Environmental Research Letters, 2020, 15 (9): 0940b8.
7	ZHENG X, LEI Q Y, YAO R, et al Image segmentation based on adaptive k-means algorithm . Journal on Image and Video Processing, 2018, 2018, 68. doi: 10.1186/s13640-018-0309-3
8	TOSUN A B, GUNDUZ-DEMIR C Graph run-length matrices for histopathological image segmentation. IEEE Trans. on Medical Imaging, 2011, 30 (3): 721- 732. doi: 10.1109/TMI.2010.2094200
9	GARCIA-UGARRIZA L, SABER E, AMUSO V, et al Automatic color image segmentation by dynamic region growth and multimodal merging of color and texture information. IEEE Trans. on Image Processing, 2009, 18 (10): 2275- 2288. doi: 10.1109/TIP.2009.2025555
10	ZHU H C, HUANG W, LIU H Y Loess terrain segmentation from digital elevation models based on the region growth method. Physical Geography, 2017, 39 (1): 51- 66.
11	UEMURA T, KOUTAKI K, UCHIMURA K Image segmentation based on edge detection using boundary code. International Journal of Innovative Computing, Information & Control, 2011, 7 (10): 6073- 6083.
12	LONG J W, FENG X, ZHU X F, et al Efficient superpixel-guided interactive image segmentation based on graph theory. Symmetry, 2018, 10 (5): 169- 175. doi: 10.3390/sym10050169
13	VAN O A, IKRAM MA, VERNOOIJ M W, et al Transfer learning improves supervised image segmentation across imaging protocols. IEEE Trans. on Medical Imaging, 2015, 34 (5): 1018- 1030. doi: 10.1109/TMI.2014.2366792
14	CHEN L, BENTLEY P, MORI K, et al DRINET for medical image segmentation. IEEE Trans. on Medical Imaging, 2018, 37 (11): 2453- 2462. doi: 10.1109/TMI.2018.2835303
15	HE L F, CHAO Y Y, SUZUKI K Two efficient label-equivalence-based connected-component labeling algorithms for 3-D binary images. IEEE Trans. on Image Processing, 2011, 20 (8): 2122- 2134. doi: 10.1109/TIP.2011.2114352
16	LI Z L, ZHANG Q J, LONG T, et al Ship target detection and recognition method on sea surface based on multi-level hybrid network. Journal of Beijing Institute of Technology, 2021, 30 (S1): 1- 10.
17	JASIEWICZ J, STEPINSKI T F Geomorphons a pattern recognition approach to classification and mapping of landforms. Geomorphology, 2013, 182 (1): 147- 156.
18	WU K S, OTOO E, SUZUKI K Optimizing two-pass connected-component labeling algorithms. Pattern Analysis & Applications, 2009, 12 (2): 117- 135.
19	DIAZ-DEL-RIO F, SANCHEZ-CUEVAS P, MOLINA-ABRIL H, et al Parallel connected-component-labeling based on homotopy trees. Pattern Recognition Letters, 2020, 131 (4): 71- 78.
20	BATAINEH B A fast and memory-efficient two-pass connected-component labeling algorithm for binary images. Turkish Journal of Electrical Engineering and Computer Sciences, 2019, 27 (2): 1243- 1259.
21	ZHAO X, HE L F, YAO B, et al A new connected-component labeling algorithm. IEEE Trans. on Information & Systems, 2015, 98 (11): 2013- 2016.
22	HE L F, REN X W, GAO Q H, et al The connected-component labeling problem: a review of state-of-the-art algorithms. Pattern Recognition, 2017, 70 (1): 25- 43.
23	DOUBE M Multithreaded two-pass connected components labelling and particle analysis in Image. Royal Society Open Science, 2021, 8 (1): 201784.
24	HE L F, CHAO Y Y, SUZUKI K A run-based two-scan labeling algorithm. IEEE Trans. on Image Processing, 2008, 17 (5): 749- 756. doi: 10.1109/TIP.2008.919369
25	JEONG J W, LEE G B, LEE M J, et al A single-pass connected component labeler without label merging period. Journal of Signal Processing Systems for Signal, Image, and Video Technology, 2016, 84 (2): 211- 223. doi: 10.1007/s11265-015-1048-7
26	YANG Y, ZHANG D P A novel line scan clustering algorithm for identifying connected components in digital images. Image and Vision Computing, 2003, 21 (5): 459- 472. doi: 10.1016/S0262-8856(03)00015-5
27	CHANG F, CHEN C J, LU C J A linear-time component-labeling algorithm using contour tracing technique. Computer Vision and Image Understanding, 2004, 93 (2): 206- 220. doi: 10.1016/j.cviu.2003.09.002
28	HU Q M, QIAN G Y, NOWINSKI W L Fast connected-component labeling in three-dimensional binary images based on iterative recursion. Computer Vision & Image Understanding, 2005, 99 (3): 414- 434.
29	KLAIBER M J, BAILEY D G, SIMON S Comparative study and proof of single-pass connected components algorithms. Journal of Mathematical Imaging and Vision, 2019, 61 (8): 1112- 1134. doi: 10.1007/s10851-019-00891-2
30	ASAD P, MARROQUIM R, SOUZA A L E L On GPU connected components and properties: a systematic evaluation of connected component labeling algorithms and their extension for property extraction. IEEE Trans. on Image Processing, 2019, 28 (1): 17- 31. doi: 10.1109/TIP.2018.2851445
31	ALLEGRETTI S, BOLELLI F, GRANA C Optimized block-based algorithms to label connected components on GPUs. IEEE Trans. on Parallel and Distributed Systems, 2020, 31 (2): 423- 438. doi: 10.1109/TPDS.2019.2934683
32	LIN D T, LIN M C, HUANG K Y Real-time automatic recognition of omnidirectional multiple bar-codes and DSP implementation. Machine Vision and Applications, 2010, 22 (2): 409- 419.
33	TSAI T H, CHEN S W Single-chip design for intelligent surveillance system. IEEE Trans. on Very Large Scale Integration (VLSI) Systems, 2018, 26 (9): 1637- 1646. doi: 10.1109/TVLSI.2018.2827385
34	AZIZABADI M, BEHRAD A, GHAZNAVI-GHOUSHCHI M B VLSI implementation of star detection and centroid calculation algorithms for star tracking applications. Journal of Real-Time Image Processing, 2014, 9 (1): 127- 140. doi: 10.1007/s11554-012-0285-2
35	PERRI S, SPAGNOLO F, CORSONELLO P A parallel connected component labeling architecture for heterogeneous systems-on-chip. Electronics, 2020, 9 (2): 292. doi: 10.3390/electronics9020292
36	KOWALCZYK M, CIARACH P, PRZEWLOCKA-RUS D, et al Real-time FPGA implementation of parallel connected component labeling for a 4k video stream. Journal of Signal Processing Systems, 2021, 93 (5): 481- 498. doi: 10.1007/s11265-021-01636-4
37	ITO Y, NAKANO K Low-latency connected component labeling using an FPGA. Journal of Foundations of Computer Science, 2010, 21 (3): 405- 425.
38	KLAIBER M J, BAILEY D G, SIMON S A single-cycle parallel multi-slice connected components analysis hardware architecture. Journal of Real-Time Image Processing, 2019, 16 (4): 1165- 1175. doi: 10.1007/s11554-016-0610-2
39	TANG J W, SHAIKH-HUSIN N, SHEIKH U U, et al A linked list run-length-based single-pass connected component analysis for real-time embedded hardware. Journal of Real-time Image Processing, 2018, 15 (1): 197- 215.
40	XIE Y Z, TAN X B, CHEN H A new algorithm for connected components labeling. Transactions of Beijing Institute of Technology, 2012, 32 (12): 1273- 1278.
41	GONZLEZ C G, RAFAELEW W Digital image processing. 3rd ed. London: Pearson Education, 2011.
42	KLAIBER M J, BAILEY D G, BAROUD Y O, et al A resource-efficient hardware architecture for connected component analysis. IEEE Trans. on Circuits and Systems for Video Technology, 2016, 26 (7): 1334- 1349. doi: 10.1109/TCSVT.2015.2450371
43	APPIAH K, HUNTER A, DICKINSON P, et al Accelerated hardware video object segmentation: from foreground detection to connected components labelling. Computer Vision and Image Understanding, 2010, 114 (11): 1282- 1291. doi: 10.1016/j.cviu.2010.03.021

Data set (4096×4096)	CCD integral time/ms	Nums of runs			Nums of equivalences			Label time/ms
Data set (4096×4096)	CCD integral time/ms	Maximum	Minimum	Average	Maximum	Minimum	Average	Maximum	Minimum	Average
Set 1 (2388 images)	150	18504	12567	14752	19	0	7	129.12	112.05	115.76
Set 2 (1934 images)	200	19531	13214	16321	35	0	12	141.21	112.05	127.85
Set 3 (1742 images)	250	25430	17654	22043	41	0	14	152.43	112.05	131.32
Set 4 (1543 images)	300	32567	21734	27621	55	1	23	167.95	119.05	142.92
Set 5 (1149 images)	500	45768	32165	35982	148	9	61	241.13	124.05	198.32

Platform	Time/Hz	Power/W	EER/(Hz/W)
PC	1.94	77	0.025
GPU	4.54	15	0.302
DSP	0.89	15	0.059
Proposed method	5.88	1.6	3.675

Algorithm	FPGA	Image size	Num	SLICE	RAM/kB	External memory	Time/ms
Algorithm in [35]	XC7Z020	640×480	64	481	0.375	DDR3	1.75
	XC7Z020	640×480	128	699	0.875	DDR3	1.74
	XC7Z020	640×480	256	1072	2	DDR3	1.94
	XC7Z020	640×480	512	1699	4.5	DDR3	2.16
	XC7Z020	640×480	1024	3226	10	DDR3	2.44
	XC7Z020	2048×2048	64	784	0.375	DDR3	21.55
	XC7Z020	2048×2048	256	1439	2	DDR3	27.18
	XC7Z020	2048×2048	1024	3688	10	DDR3	33.01
	XC7VX1140T	2048×1536	8192	28886	104	DDR3	21.51
Algorithm in [36]	ZCU104	3840×2160	<1024	55040	70	DDR4	16.67
Algorithm in [40]	VIRTEXII	1024×1024	4096	432	130	No need	305
Algorithm in [42]	XC7K325T	256×256	—	5943	108	No need	—
	XC7K325T	640×480	—	8243	156	No need	—
	XC7K325T	7680×4320	—	24510	548	No need	—
Algorithm in [43]	XC4VLX160	640×480	<1024	2510	76	Synchronous dynamic random access memory	28.5
Proposed algorithm	XC7VX690T	4096×4096	65536	25877	361	No need	170.07

A parallel pipeline connected-component labeling method for on-orbit space target monitoring

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 20

References 43

Related Articles 0

Recommended Articles

Metrics

Comments