Search

A new star identification algorithm is proposed for the attitude determination of a star sensor in the lost-in-space case, where prior attitude information is not available. The algorithm is based on a labelling technique, which uses label values to represent each group of stars. Using label values, multiple stars are simultaneously identified without repetition of search work. This labelling algorithm allows for a fast identification speed with efficiency, and provides the capability of more reliable identification by redundant confirmation. The proposed algorithm was verified by simulation study under various conditions.

The potential of hyperspectral measurements for early disease detection has been investigated by many experts over the last 5 years. One of the difficulties is obtaining enough data for training and building a hyperspectral training library. When the goal is to detect disease at a previsible stage, before the pathogen has manifested either its first symptoms or in the area surrounding the existing symptoms, it is impossible to objectively delineate the regions of interest containing the previsible pathogen growth from the areas without the pathogen growth. To overcome this, we propose an image labelling and segmentation algorithm that is able to (a) more objectively label the visible symptoms for the construction of a training library and (b) extend this labelling to the pre-visible symptoms. This algorithm is used to create hyperspectral training libraries for late blight disease (Phytophthora infestans) in potatoes and two types of leaf rust (Puccinia triticina and Puccinia striiformis) in wheat. The model training accuracies were compared between the automatic labelling algorithm and the classic visual delineation of regions of interest using a logistic regression machine learning approach. The modelling accuracies of the automatically labelled datasets were higher than those of the manually labelled ones for both potatoes and wheat, at 98.80% for P. infestans in potato, 97.69% for P. striiformis in soft wheat, and 96.66% for P. triticina in durum wheat.

The distance label is a label model derived from the frequency allocation problem. This article mainly studies the L(2,1)-label in the label. L(2,1)-label refers to the use of non-negative integers to label the vertices of the graph G. The goal is to make the label values of adjacent vertices differ by at least 2 and the label values of vertices with a distance of 2 are different. This paper proposes a recursive backtracking greedy algorithm based on Griggs’ conjecture, and also gives the algorithm’s execution steps, analysis and test results. The experimental results show that for a unicyclic graph containing only one maximum degree point, its L(2,1)-label number is $\Delta$+1. In addition, the L(2,1)-label number characteristics of the unicyclic graph are given and expressed in the form of forbidden subgraphs.

The paper presents a dynamic solution method for the parametric minimum flow in time-dependent, dynamic network. This approach solves the problem for a special parametric dynamic network with linear lower bound functions of a single parameter. Instead of directly working in the original network, the method implements a labelling algorithm which works in the parametric dynamic residual network where repeatedly decreases the flow along quickest dynamic source-sink paths for different subintervals of parameter values, in their increasing order. In each iteration, the algorithm computes both the parametric minimum flow within a certain subinterval, and the new subinterval for which the flow needs to be computed.

This thesis deals with a two-dimensional bin-packing problem with defects on bins from the glass industry. Cutting patterns have to be exact 4-stage guillotine and items defect-free. A standard way to solve it isto use Dantzig-Wolfe reformulation with column generation and branch-and price.This is impossible in our case due to large instance size. We first study and solve the defect-free pricing problem with an incremental labelling algorithm based on a dynamic program (DP), represented as a flow problem in a hypergraph. Our method is generic for guillotine knapsack problems but fails to solve large instance in a short amount of time. Instead we solve the defect freebin-packing problem with a DP and a diving heuristic. This DP generatesnon-proper columns, cutting patterns that cannot be in an integer solution.We adapt standard diving heuristic to this “non-proper” case while keeping itseffectiveness. We then extend the diving heuristic to deal with defects. Ourfirst proposal heuristically repairs a given defect-free solution. Secondly the defect-free diving heuristic is adjusted to handle defects during column fixing.Our industrial results outline the effectiveness of our methods.; Cette thèse s’intéresse à un problème de bin-packing en deux dimensions avec des défauts sur les bins rencontré dans l’industrie verrière. Les plans de découpe sont guillotine 4-stage exact, les objets à couper sans défauts.Une possible résolution utilise la décomposition de Dantzig-Wolfe puis une génération de colonnes et un branch-and-price. Cela est impossible dans notre cas du fait d’instances de trop grande taille. Nous résolvons d’abord le problème de pricing sans défauts par un algorithme incrémental de labelling basé sur un programme dynamique (DP), représenté par un problème de flot dans un hypergraphe. Notre méthode est générique pour les problèmes de sac-à-dos guillotine mais ne résout pas de larges instances en un temps de calcul raisonnable. Nous résolvons alors le problème de bin-packing sans défauts grâce à un DP et une heuristique de diving. Le DP génère des colonnes “non propres”,ne pouvant pas participer à une solution entière. Nous adaptons le diving pour ce cas sans perte d’efficacité. Nous l’étendons alors au cas avec défauts. Nous réparons d’abord heuristiquement une solution du problème sans défauts. La fixation des colonnes dans le diving sans-défaut est ensuite modifiée pour gérer les défauts. Les résultats industriels valident nos méthodes.

This paper identifies a problem with a hypothesis put forward in Chomsky (2013) in relation to his labelling algorithm. Chomsky suggests that category-neutral roots do not qualify as labels and cannot project. However, I provide evidence that the derivation of particle verbs involves the projection of a category-neutral root, which has merged with (a projection of) the particle. It follows that Chomsky's hypothesis has to be rejected.Keywords: roots, projection, labelling, particle verbs

Understanding the evolution of research topics is crucial to detect emerging trends in science. This paper proposes a new approach and a framework to discover the evolution of topics based on dynamic co-word networks and communities within them. The NEViewer software was developed according to this approach and framework, as compared to the existing studies and science mapping software tools, our work is innovative in three aspects: (a) the design of a longitudinal framework based on the dynamics of co-word communities; (b) it proposes a community labelling algorithm and community evolution verification algorithms; (c) and visualizes the evolution of topics at the macro and micro level respectively using alluvial diagrams and coloring networks. A case study in computer science and a careful assessment was implemented and demonstrating that the new method and the software NEViewer is feasible and effective.

The exact solution and heuristic solution have their own strengths and weaknesses on solving the Vehicle Routing Problems with Time Windows (VRPTW). This paper proposes a hybrid Column Generation Algorithm with Metaheuristic Optimization (CGAMO) to overcome their weaknesses. Firstly, a Modified Labelling Algorithm (MLA) in the sub-problem of path searching is analysed. And a search strategy in CGAMO based on the demand of sub-problem is proposed to improve the searching efficiency. While putting the paths found in the sub-problem into the main problems of CGAMO, the iterations may fall into endless loops. To avoid this problem and keep the main problems in a reasonable size, two conditions on saving the old paths in the main problem are used. These conditions enlarge the number of constraints considered in the iterations to strengthen the limits of dual variables. Through analysing the sub-problem, we can find many useless paths that have no effect on the objective function. Secondly, in order to reduce the number of useless paths and improve the efficiency, this paper proposes a heuristic optimization strategy of CGAMO for dual variables. It is supposed to accelerate the solving speed from the view of on the dual problem. Finally, extensive experiments show that CGAMO achieves a better performance than other state-of-the-art methods on solving VRPTW. The comparative experiments also present the parameters sensitivity analysis, including the different effects of MLA in the different path selection strategies, the characteristics and the applicable scopes of the two pathkeeping conditions in the main problem. First published online:25 Oct 2013

This paper constructs an algorithm to solve the fractional assignment problem. Algorithms that are currently used are mostly based on parametric approaches and must solve a sequence of optimization procedures. They also neglect the difficulties caused by degeneracy. The proposed algorithm performs optimization once and overcomes degeneracy. The main features of the algorithm are an effective initial heuristic approach, a simple labelling procedure and an implicit primal-dual schema. A numerical example is presented and demonstrates that the proposed algorithm is easy to apply. Computational results are compared with those from other developed methods. The results show that the proposed algorithm is efficient.

This paper proposes a spectral clustering based methodology to classify video events and to detect anomalies. Feature trajectories from objects in a video are modelled, compared and clustered in order to classify the detected object events. Principles of normalized spectral clustering are used with modifications to affinity structure. A novel method for determining spectral clustering parameters based on Eigen structure of the affinity matrix is introduced. Employment of unsupervised learning for event classification is made possible by the proposed successive cluster identity labelling algorithm. A mechanism to identify abnormal events under the context is also introduced. The effectiveness and the robustness of the proposed methodology are demonstrated through experiments conducted on video streams focusing on human motion patterns.

International audience; This paper presents a direct extension of the label setting algorithm proposed by Martins in 1984 for the shortest path problem with multiple objectives. This extended version computes all the efficient paths from a given source vertex, to all the other vertices of the network. The algorithm copes with problems in which the "cost values" associated with the network arcs are positive. The proposed extension can handle objective functions that are either of the "sum" type or of the "bottleneck" type. The main modifications to Martins' algorithm for multi-objective shortest path problems are linked to the dominance test and the procedure for identifying efficient paths. The algorithmic features are described and a didactic example is provided to illustrate the working principle. The results of numerical experiments concerning the number of efficient solutions produced and the CPU time consumed for several configurations of objectives, on a set of randomly generated networks, are also provided.

Part 7: Networking; International audience; In this paper, we consider the problem of finding itineraries in bus networks under multiple independent optimization criteria, namely arrival time at destination and number of transfers. It is also allowed to walk from one stop to another if the two stops are located within a small distance. A time–dependent model is proposed to solve this problem. While focusing on the network where the size of the Pareto set in the multi–criteria shortest path problem might grow exponentially, we develop an efficient algorithm with its speed–up techniques. An evaluation on the qualities of found paths and the empirical results of different implementations are given. The results show that the allowance of walking shortcuts between nearby stops gives a better route planning.

A new method for segmenting images of immunohistochemically stained cell nuclei is presented. The aim is to distinguish between cell nuclei with a positive staining reaction and other cell nuclei, and to make it possible to quantify the reaction. First, a new supervised algorithm for creating a pixel classifier is applied to an image that is typical for the sample. The training phase of the classifier is very user friendly since only a few typical pixels for each class need to be selected. The classifier is robust in that it is non‐parametric and has a built‐in metric that adapts to the colour space. After the training the classifier can be applied to all images from the same staining session. Then, all pixels classified as belonging to nuclei of cells are grouped into individual nuclei through a watershed segmentation and connected component labelling algorithm. This algorithm also separates touching nuclei. Finally, the nuclei are classified according to their fraction of positive pixels.

This paper describes an efficient approach for labeling images using a combination of pipeline (Datacube) and (general purpose computer) processing. The output of the algorithm is coordinate list of labeled object pixels that facilitates further high level operations. It is an efficient labeling algorithm for a automatic classification of surface defects on wood boards.

Counting applications use various image processing techniques to count the objects of interest. The final and the most significant step in any image-based counting application is labeling. It becomes extremely difficult to label when the objects of interest overlap. Existing counting applications use labeling algorithms that provide the same label to overlapping objects. In this paper, we propose a new labeling algorithm which has the ability to distinguish certain overlapping objects and faithfully label both disjoint and overlapping objects. This results in more precise counting results vis-a-vis the present labeling algorithms.

Summarization of echo-Doppler videos allows reducing diagnosis time, improving comparison between videos and making a more efficient storing of them. This paper aims at providing a solution to the static summarization of echo-Doppler videos. A static summary of a video is a collection of keyframes together with a description of them. The selection of keyframes discussed in this paper is based on the analysis of properties of red blobs resulting from Power Doppler technique. The properties of red blobs are extracted by a robust thresholding algorithm in the HSL colour model and via a connected-component labelling algorithm. Keyframes extracted from the echo-Doppler video satisfy specific properties for the red blobs. The work is still in progress and we are now collecting data for the construction of a decision support system to help doctors in their diagnoses. First results are encouraging and future works will bring to an interesting computer-aided system.

In a recent paper Baumann [1] has shown that splitting results, similar to those known for logic programs under answer set semantics and default logic, can also be obtained for Dung argumentation frameworks (AFs). Under certain conditions a given AF A can be split into subparts A1 and A2 such that extensions of A can be computed by (1) computing an extension E1 of A1, (2) modifying A2 based on E1, and (3) combining E1 and an extension E2 of the modified variant of A2. In this paper we perform a systematic empirical evaluation of the effects of splitting on the computation of extensions. Our study shows that the performance of algorithms may drastically improve when splitting is applied.

This article presents the method of determining the position of the pupil based on the labelling algorithm. Due to the speed of this method it is designed for use in Eye Tracking systems operating online. The essential requirement posed in front of such systems is the quick determination of the pupil's position. Studies have shown that the proposed method of calculating the average time is about 6.25 ms.

Exploiting operator commutativity is used in high-level synthesis for reducing interconnections. The standard heuristic is to apply a succession of pairwise operand interchanges. We present a new and general characterization of the problem in terms of graph labelling. An integer linear programming formulation that yields globally optimum results, is presented. Next, a heuristic algorithm and an optimal graph decomposition and labelling algorithm is presented. While the latter finds an optimal solution, in practice, the heuristic approach usually discovers an optimum considerably faster. Experimental results are also presented.

The antibandwidth problem is to label vertices of a graph G = (V,E) bijectively by 0,1,2,,...,|V| ? 1 such that the minimal difference of labels of adjacent vertices is maximised. In this paper we discuss the antibandwidth of d-dimensional meshes. We provide labelling algorithm giving antibandwidth value matching the upper bound up to the third order term. This work is a continuation of our previous results for antibandwidths of two and three-dimensional meshes and hypercubes.

The paper discusses the problem of pixel labelling, for three-dimensional images. It is assumed that contextual information in the picture can be modelled by a third-order Markov mesh. The model and associated methodology are generalisations, from two to three dimensions, of work of Lacroix. The algorithm developed is therefore a generalisation of Devijver's F-G-H algorithm. The paper sets out the labelling algorithm and repoets the results of simulation experiments to explore its performance in practice.

In this paper, we present a new algorithm for solving the multi-objective shortest path problem (MSPP) which consists of finding all the non-dominated paths between two nodes s and t (ND s-t paths), on a network where a multiple criteria function is defined over the set of arcs. The main feature of the algorithm is that, contrarily to the previous most efficient approaches for the MSPP, not all of the ND sub-paths on the network need to be found. Additionally, the algorithm fully exploits the fact that ND s-t paths are generated at a very early stage of the ranking procedure. The computational experience reported in the paper shows that, for large size general type networks, the new algorithm clearly outperforms the labelling approach. FCT POCTI - Research Units Pluriannual Funding to CMUC (Centro de Matemática da Universidade de Coimbra) and CIO (Operations Research Center of the University of Lisbon), and grant POCTI/MAT/139/2001 cofunded by the EU program FEDER.

This paper is devoted to the study of labelling techniques for solving the multi-objective shortest path problem (MSPP) which is an extension of the shortest path problem (SPP) resulting from considering simultaneously more than one cost function (criteria) for the arcs. The generalization of the well known SPP labelling algorithm for the multiobjective situation is studied in detail and several different versions are considered combining two labelling techniques (setting and correcting), with different data structures and ordering operators. The computational experience was carried out making use of a large and representative set of test problems, consisting of around 9000 instances, involving three types of network (random, complete and grid) and a reasonable range for the number of criteria. The computational results show that the labelling algorithm is able to solve large size instances of the MSPP, in a reasonable computing time. The computational experience reported in this paper is complemented by the results presented in a twin paper [22] showing that the label correcting technique proves to be the fastest procedure when the computation of the full set of non-dominated paths is required. FCT through POCTI - Research Units Pluriannual Funding to CMUC and CIO (Operations Research Center of the University of Lisbon), and grant POCTI/MAT/139/2001 cofunded by the EU program FEDER

An improved segmentation Fuzzy C-Means algorithm (FCM) is proposed for the image recognition of transmission line insulators. In this paper, the improved Wiener filter algorithm is firstly used to filtrate and recover image in pre-processing. Then, the insulator image is segmented based on the improved algorithm FCM. Finally, the contour of insulator is labelled by using connected component labelling algorithm. Experimental results have shown that the improved Wiener filtering algorithm may effectively filter and recover the images; furthermore, the improved FCM image segmentation algorithm may accurately segment insulators from the image.

An example is presented to show that it is unable to find any numerical Kakutani fixed point with vector labelling algorithms sometimes, and two sufficient conditions of finding numerical Kakutani fixed points are established.

A fast stripe-based connected component labelling algorithm is proposed for binary image labelling. Stripe extraction strategy is used to transform the pixel-connected issues, which most of the previously proposed algorithms focused on, into stripe-connected issues. The stripe-union strategy treats the combination of the neighbouring stripes as the mergence of rooted trees. Finally, comparisons are performed with other famous fast labelling algorithms. The proposed algorithm has shown better performance than the state-of-the-art algorithm in real images test, while the auxiliary memory is not required at all compared with all competitors.

The shortest path problem with time windows (SPPTW) consists of finding the least cost route between a source and a sink in a network G = (N, A) while respecting specified time windows [ai, bi] at each visited node. The duration dij of each arc is restricted to positive values while the cost Cij of each arc (i, j) Є A is unrestricted.This article presents an efficient generalized permanent labelling algorithm to solve this problem. This new algorithm is based on the definition of the concept of a generalized bucket and on a specific order of handling the labels. The algorithm runs in pseudo-polynomial time. Problems with up to 2500 nodes and 250,000 arcs have heen solved.

In this paper we give a new and conceptually simple version of Frisch's algorithm for calculating the vertex connectivity of a graph. We show how this algorithm is obtained immediately from the Ford and Fulkerson labelling algorithm by using a “2-ply” scanning step. Data structures are introduced which lead to efficiencies in execution, and the final algorithm is presented in a “go-to-less” notation.

A labelling algorithm is proposed to determine the shortest signed paths between one vertex and all others in a weighted signed graph. It can be implemented to take O(m log log D/d) time and O(n + m + D/d) space where D and d denote the lar-the largest and smallest weights of the arcs, respectively. The case where the additional requirement that the paths be elementary is imposed, which is NP-complete, is tackled through decomposition and branch and bound. Applications are made to problems of balance in small groups, transient behaviour of complex societal systems and sign solvability of linear qualitative systems of equations.

This thesis deals with a two-dimensional bin-packing problem with defects on bins from the glass industry. Cutting patterns have to be exact 4-stage guillotine and items defect-free. A standard way to solve it isto use Dantzig-Wolfe reformulation with column generation and branch-and price.This is impossible in our case due to large instance size. We first study and solve the defect-free pricing problem with an incremental labelling algorithm based on a dynamic program (DP), represented as a flow problem in a hypergraph. Our method is generic for guillotine knapsack problems but fails to solve large instance in a short amount of time. Instead we solve the defect freebin-packing problem with a DP and a diving heuristic. This DP generatesnon-proper columns, cutting patterns that cannot be in an integer solution.We adapt standard diving heuristic to this “non-proper” case while keeping itseffectiveness. We then extend the diving heuristic to deal with defects. Ourfirst proposal heuristically repairs a given defect-free solution. Secondly the defect-free diving heuristic is adjusted to handle defects during column fixing.Our industrial results outline the effectiveness of our methods.; Cette thèse s’intéresse à un problème de bin-packing en deux dimensions avec des défauts sur les bins rencontré dans l’industrie verrière. Les plans de découpe sont guillotine 4-stage exact, les objets à couper sans défauts.Une possible résolution utilise la décomposition de Dantzig-Wolfe puis une génération de colonnes et un branch-and-price. Cela est impossible dans notre cas du fait d’instances de trop grande taille. Nous résolvons d’abord le problème de pricing sans défauts par un algorithme incrémental de labelling basé sur un programme dynamique (DP), représenté par un problème de flot dans un hypergraphe. Notre méthode est générique pour les problèmes de sac-à-dos guillotine mais ne résout pas de larges instances en un temps de calcul raisonnable. Nous résolvons alors le problème de bin-packing sans défauts grâce à un DP et une heuristique de diving. Le DP génère des colonnes “non propres”,ne pouvant pas participer à une solution entière. Nous adaptons le diving pour ce cas sans perte d’efficacité. Nous l’étendons alors au cas avec défauts. Nous réparons d’abord heuristiquement une solution du problème sans défauts. La fixation des colonnes dans le diving sans-défaut est ensuite modifiée pour gérer les défauts. Les résultats industriels valident nos méthodes.

Low uptake ratios, high noise, poor resolution, and low contrast all combine to make the detection of neuroendocrine liver tumours by 111In-octreotide single photon emission tomography (SPECT) imaging a challenge. The aim of this study was to develop a segmentation analysis method that could improve the accuracy of hepatic neuroendocrine tumour detection. Our novel segmentation was benchmarked by a retrospective analysis of patients categorized as either 111In-octreotide positive (111In-octreotide(+)) or 111In-octreotide negative (111In-octreotide(−)) for liver tumours. Following a 3-year follow-up period, involving multiple imaging modalities, we further segregated 111In-octreotide-negative patients into two groups: one with no confirmed liver tumours (111In-octreotide(−)/radtech(−)) and the other, now diagnosed with liver tumours (111In-octreotide(−)/radtech(+)). We retrospectively applied our segmentation analysis to see if it could have detected these previously missed tumours using 111In-octreotide. Our methodology subdivided the liver and determined normalized numbers of uptake foci (nNUF), at various threshold values, using a connected-component labelling algorithm. Plots of nNUF against the threshold index (ThI) were generated. ThI was defined as follows: ThI = (c max − c thr)/c max, where c max is the maximal threshold value for obtaining at least one, two voxel sized, uptake focus; c thr is the voxel threshold value. The maximal divergence between the nNUF values for 111In-octreotide(−)/radtech(−), and 111In-octreotide(+) livers, was used as the optimal nNUF value for tumour detection. We also corrected for any influence of the mean activity concentration on ThI. The nNUF versus ThI method (nNUFTI) was then used to reanalyze the 111In-octreotide(−)/radtech(−) and 111In-octreotide(−)/radtech(+) groups. Of a total of 53 111In-octreotide(−) patients, 40 were categorized as 111In-octreotide(−)/radtech(−) and 13 as 111In-octreotide(−)/radtech(+) group. Optimal separation of the nNUF values for 111In-octreotide(−)/radtech(−) and 111In-octreotide(+) groups was defined at the nNUF value of 0.25, to the right of the bell shaped nNUFTI curve. ThIs at this nNUF value were dependent on the mean activity concentration and therefore normalized to generate nThI; a significant difference in nThI values was found between the 111In-octreotide(−)/radtech(−) and the 111In-octreotide(−)/radtech(+) groups (P

This paper presents a fast algorithm based on sequential local operations which aims at labelling connected components in binary images. While classical algorithms scan the image twice and utilize an equivalence table to store and resolve label redundancies, our method performs just a single scan, relying on the idea of labelling a whole blob at a time. In this way, we avoid label redundancies. As a consequence, the use of both equivalence tables and algorithms to resolve them becomes unnecessary. This leads our labelling algorithm to attain even more significant performances in the case of images characterized by blobs generating a large number of label equivalences. The proposed labelling algorithm has been successfully utilized in our visual surveillance system.