A fast label-equivalence-based connected components labeling algorithm is proposed in this paper.It is a combination of two existing efficient methods,which are pivotal operations in two-pass connected components labe...A fast label-equivalence-based connected components labeling algorithm is proposed in this paper.It is a combination of two existing efficient methods,which are pivotal operations in two-pass connected components labeling algorithms.One is a fast pixel scan method,and the other is an array-based Union-Find data structure.The scan procedure assigns each foreground pixel a provisional label according to the location of the pixel.That is to say,it labels the foreground pixels following background pixels and foreground pixels in different ways,which greatly reduces the number of neighbor pixel checks.The array-based Union-Find data structure resolves the label equivalences between provisional labels by using only a single array with path compression,and it improves the efficiency of the resolving procedure which is very time-consuming in general label-equivalence-based algorithms.The experiments on various types of images with different sizes show that the proposed algorithm is superior to other labeling approaches for huge images containing many big connected components.展开更多
Given a connected undirected graph G whose edges are labeled,the minimumlabeling spanning tree(MLST)problemis to find a spanning tree of G with the smallest number of different labels.TheMLST is anNP-hard combinatoria...Given a connected undirected graph G whose edges are labeled,the minimumlabeling spanning tree(MLST)problemis to find a spanning tree of G with the smallest number of different labels.TheMLST is anNP-hard combinatorial optimization problem,which is widely applied in communication networks,multimodal transportation networks,and data compression.Some approximation algorithms and heuristics algorithms have been proposed for the problem.Firefly algorithm is a new meta-heuristic algorithm.Because of its simplicity and easy implementation,it has been successfully applied in various fields.However,the basic firefly algorithm is not suitable for discrete problems.To this end,a novel discrete firefly algorithm for the MLST problem is proposed in this paper.A binary operation method to update firefly positions and a local feasible handling method are introduced,which correct unfeasible solutions,eliminate redundant labels,and make the algorithm more suitable for discrete problems.Computational results show that the algorithm has good performance.The algorithm can be extended to solve other discrete optimization problems.展开更多
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 ...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.展开更多
A kind of packet labeling algorithm for autonomous system is introduced. The fairness of the algorithm for each traffic stream in the integrated-services is analyzed. It is shown that the rate of each stream in the in...A kind of packet labeling algorithm for autonomous system is introduced. The fairness of the algorithm for each traffic stream in the integrated-services is analyzed. It is shown that the rate of each stream in the integrated-services would converge to a stable value if the transmittfing or forwarding rates converge to that of the receiving exponentially.展开更多
On the basis of inner-system labeling signaling used in the integrated access system,a kind of inner-system labeling algorithm is introduced in this paper, and the fairness of the algorithm for each traffic stream in ...On the basis of inner-system labeling signaling used in the integrated access system,a kind of inner-system labeling algorithm is introduced in this paper, and the fairness of the algorithm for each traffic stream in the integrated-services is analyzed. The base of this algorithm is Class of Services (CoS), and each packet entering the relative independent area (an autonomous system) would be labeled according to the service type or Quality of Service (QoS) in demand,and be scheduled and managed within the system (the system can be enlarged if conforming to the same protocol). The experimental results show that each of the stream rate in the integratedservices would converge to a stable value if the rates of transmitting converge to that of the receiving exponentially, that is, the effective traffic of each stream would be fair.展开更多
基金Sponsored by the National Natural Science Foundation of China (Grant No. 81071219)
文摘A fast label-equivalence-based connected components labeling algorithm is proposed in this paper.It is a combination of two existing efficient methods,which are pivotal operations in two-pass connected components labeling algorithms.One is a fast pixel scan method,and the other is an array-based Union-Find data structure.The scan procedure assigns each foreground pixel a provisional label according to the location of the pixel.That is to say,it labels the foreground pixels following background pixels and foreground pixels in different ways,which greatly reduces the number of neighbor pixel checks.The array-based Union-Find data structure resolves the label equivalences between provisional labels by using only a single array with path compression,and it improves the efficiency of the resolving procedure which is very time-consuming in general label-equivalence-based algorithms.The experiments on various types of images with different sizes show that the proposed algorithm is superior to other labeling approaches for huge images containing many big connected components.
基金This work is supported by the National Natural Science Foundation of China under Grant 61772179the Hunan Provincial Natural Science Foundation of China under Grant 2019JJ40005+3 种基金the Science and Technology Plan Project of Hunan Province under Grant 2016TP1020the Double First-Class University Project of Hunan Province under Grant Xiangjiaotong[2018]469the Open Fund Project of Hunan Provincial Key Laboratory of Intelligent Information Processing and Application for Hengyang Normal University under Grant IIPA19K02the Science Foundation of Hengyang Normal University under Grant 19QD13.
文摘Given a connected undirected graph G whose edges are labeled,the minimumlabeling spanning tree(MLST)problemis to find a spanning tree of G with the smallest number of different labels.TheMLST is anNP-hard combinatorial optimization problem,which is widely applied in communication networks,multimodal transportation networks,and data compression.Some approximation algorithms and heuristics algorithms have been proposed for the problem.Firefly algorithm is a new meta-heuristic algorithm.Because of its simplicity and easy implementation,it has been successfully applied in various fields.However,the basic firefly algorithm is not suitable for discrete problems.To this end,a novel discrete firefly algorithm for the MLST problem is proposed in this paper.A binary operation method to update firefly positions and a local feasible handling method are introduced,which correct unfeasible solutions,eliminate redundant labels,and make the algorithm more suitable for discrete problems.Computational results show that the algorithm has good performance.The algorithm can be extended to solve other discrete optimization problems.
文摘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.
文摘A kind of packet labeling algorithm for autonomous system is introduced. The fairness of the algorithm for each traffic stream in the integrated-services is analyzed. It is shown that the rate of each stream in the integrated-services would converge to a stable value if the transmittfing or forwarding rates converge to that of the receiving exponentially.
文摘On the basis of inner-system labeling signaling used in the integrated access system,a kind of inner-system labeling algorithm is introduced in this paper, and the fairness of the algorithm for each traffic stream in the integrated-services is analyzed. The base of this algorithm is Class of Services (CoS), and each packet entering the relative independent area (an autonomous system) would be labeled according to the service type or Quality of Service (QoS) in demand,and be scheduled and managed within the system (the system can be enlarged if conforming to the same protocol). The experimental results show that each of the stream rate in the integratedservices would converge to a stable value if the rates of transmitting converge to that of the receiving exponentially, that is, the effective traffic of each stream would be fair.
