New Algorithm for Binary Connected-Component Labeling Based on Run-Length Encoding and Union-Find Sets

Based on detailed analysis of advantages and disadvantages of the existing connected-component labeling （CCL） algorithm,a new algorithm for binary connected components labeling based on run-length encoding （RLE） and union-find sets has been put forward.The new algorithm uses RLE as the basic processing unit,converts the label merging of connected RLE into sets grouping in accordance with equivalence relation,and uses the union-find sets which is the realization method of sets grouping to solve the label merging of connected RLE.And the label merging procedure has been optimized：the union operation has been modified by adding the ＂weighted rule＂ to avoid getting a degenerated-tree,and the ＂path compression＂ has been adopted when implementing the find operation,then the time complexity of label merging is O（nα（n））.The experiments show that the new algorithm can label the connected components of any shapes very quickly and exactly,save more memory,and facilitate the subsequent image analysis.

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

The paper designs a peripheral maximum gray differ-ence(PMGD)image segmentation method,a connected-compo-nent 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 tar-gets 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 me-mory,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 irradia-tion environment.

An Algorithm for Connected-Component Labeling, Hole Labeling and Euler Number Computing

Labeling connected components and holes and computing the Euler number in a binary image are necessary for image analysis, pattern recognition, and computer （robot） vision, and are usually made independently of each other in conventional methods. This paper proposes a two-scan algorithm for labeling connected components and holes simultaneously in a binary image by use of the same data structure. With our algorithm, besides labeling, we can also easily calculate the number and the area of connected components and holes, as well as the Euler number. Our method is very simple in principle, and experimental results demonstrate that our method is much more efficient than conventional methods for various kinds of images in cases where both labeling and Euler number computing are necessary.

An optimized run-length based algorithm for sparse remote sensing image labeling

Labeling of the connected components is the key operation of the target recognition and segmentation in remote sensing images.The conventional connected-component labeling(CCL) algorithms for ordinary optical images are considered time-consuming in processing the remote sensing images because of the larger size.A dynamic run-length based CCL algorithm(Dy RLC) is proposed in this paper for the large size,big granularity sparse remote sensing image,such as space debris images and ship images.In addition,the equivalence matrix method is proposed to help design the pre-processing method to accelerate the equivalence labels resolving.The result shows our algorithm outperforms 22.86% on execution time than the other algorithms in space debris image dataset.The proposed algorithm also can be implemented on the field programming logical array(FPGA) to enable the realization of the real-time processing on-board.