A fast connected components labeling algorithm for binary images

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.

Solving open vehicle problem with time window by hybrid column generation algorithm

This paper addresses the open vehicle routing problem with time window(OVRPTW), where each vehicle does not need to return to the depot after completing the delivery task.The optimization objective is to minimize the total distance. This problem exists widely in real-life logistics distribution process.We propose a hybrid column generation algorithm(HCGA) for the OVRPTW, embedding both exact algorithm and metaheuristic. In HCGA, a label setting algorithm and an intelligent algorithm are designed to select columns from small and large subproblems, respectively. Moreover, a branch strategy is devised to generate the final feasible solution for the OVRPTW. The computational results show that the proposed algorithm has faster speed and can obtain the approximate optimal solution of the problem with 100 customers in a reasonable time.

Labeling algorithm and its fairness analysis for autonomous system

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.

THE INNER-SYSTEM LABELING ALGORITHM AND ITS FAIRNESS ANALYSIS

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.

A branch-and-price algorithm to perform single-machine scheduling for additive manufacturing

Additive manufacturing(AM)has attracted significant attention in recent years based on its wide range of applications and growing demand.AM offers the advantages of production flexibility and design freedom.In this study,we considered a practical variant of the batch-processing-machine(BPM)scheduling problem that arises in AM industries,where an AM machine can process multiple parts simultaneously,as long as the twodimensional rectangular packing constraint is not violated.Based on the set-partitioning formulation of our mixed-integer programming(MIP)model,a branch-and-price(B&P)algorithm was developed by embedding a column-generation technique into a branchand-bound framework.Additionally,a novel labelling algorithm was developed to accelerate the column-generation process.Ours is the first study to provide a B&P algorithm to solve the BPM scheduling problem in the AM industry.We tested the performance of our algorithm using a modern MIP solver(Gurobi)and real data from a 3D printing factory.The results demonstrate that for most instances tested,our algorithm produces results similar or identical to those of Gurobi with reasonable computation time and outperforms Gurobi in terms of solution quality and running time on some large instances.

Detecting community structure using label propagation with consensus weight in complex network

Community detection is a fundamental work to analyse the structural and functional properties of complex networks. The label propagation algorithm （LPA） is a near linear time algorithm to find a good community structure. Despite various subsequent advances, an important issue of this algorithm has not yet been properly addressed. Random update orders within the algorithm severely hamper the stability of the identified community structure. In this paper, we executed the basic label propagation algorithm on networks multiple times, to obtain a set of consensus partitions. Based on these consensus partitions, we created a consensus weighted graph. In this consensus weighted graph, the weight value of the edge was the proportion value that the number of node pairs allocated in the same cluster was divided by the total number of partitions. Then, we introduced consensus weight to indicate the direction of label propagation. In label update steps, by computing the mixing value of consensus weight and label frequency, a node adopted the label which has the maximum mixing value instead of the most frequent one. For extending to different networks, we introduced a proportion parameter to adjust the proportion of consensus weight and label frequency in computing mixing value. Finally, we proposed an approach named the label propagation algorithm with consensus weight （LPAcw）, and the experimental results showed that the LPAcw could enhance considerably both the stability and the accuracy of community partitions.

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.