A class-independent flexible algorithm to generate region proposals

Generating a sufficient number of regions with high accuracy is an important objective in the region proposal generation techniques. This paper presents a new, robust, and effective approach, which is based on the bottom-up segmentation, to produce a pool of well-quality regions. After image segmentation, the segmented candidates are expanded into the surrounding regions. The suggested algorithm produces some enlarged regions, which better cover objects and stuff. The proposed process can be applied in three different modes, namely fixed_mode, all_mode, and efficient_mode. The fixed_mode extends each region into parts of all the adjacent regions using an extension controller, which considers adjacent sequential pixels for each point on the region boundary. In all_mode, the current region is merged with all the adjacent regions to generate a larger region. The efficient_mode is then implemented using the accumulation of the results from both the fixed_mode and all_mode. Besides, the algorithm can be repeated in the fixed_mode and all_mode by considering a variety of values for the extension controller factor. No features are required to be extracted in the proposed algorithm, except for the image segmentation stage. In this study, four challenging datasets known as MSRC, VOC2007, VOC2012, and COCO 2017 are used to compare the proposed algorithm with other segmentation and region proposal algorithms. As a significant advantage compared to well-known region proposal algorithms, our approach achieves a greater Recall with the desirable number of regions. Furthermore, the algorithm shows a good improvementin extraction of small, medium, and large objects.

     

An algorithm to generate a random cyclic permutation

The purpose of this work is to present an algorithm to generate a random cyclic permutation. The proof of its correctness, the complexity and the results of the chi-square distribution test are given.     

Determining the feature relevance for non-classically described objects and a new algorithm to compute typical fuzzy testors

In this paper we introduce an algorithm for computing all the typical fuzzy testors of a training matrix with non-classically described objects in Goldman's approach. We also introduce a new expression for determining the feature relevance in crisp and fuzzy environments.     

形式概念演化生成算法

目前仍然缺乏使用遗传算法构造概念的研究。为此,首先把形式概念的构造问题转换为以形式背景的对象幂集和属性幂集组合空间为搜索空间,以伽罗瓦联系为约束条件的约束最优化问题;然后提出一个新颖的基于遗传演化的概念生成算法——遗传概念生成算法(Geacob)。该算法采用变长结构编码,不仅满足概念形式的表示和演化过程的需要,而且使该算法具有更好的扩展性和通用性。实验表明了该遗传算法求解形式概念的可行性和有效性。     

Gray码的分治构造算法

Gray码在计算机编码、通信以及工业自动化等领域具有广泛的应用。寻找一种生成并存储Gray码的快速而有效的算法是非常意义的。提出一种基于分治算法的Gray码生成方法,同时对算法的时间和空间复杂性进行了分析和讨论。实验结果验证了算法的有效性。     

A parallel polygon-clipping algorithm

We describe a new parallel polygonclipping algorithm based on a novel technique that allows a processor to compute output vertices independently of the results of the other processors. The basis for the method is a collision-free labeling scheme to compute the labels of the vertices of the output polygon. This labeling scheme depends only on the id of the vertices of the output polygon. This labeling scheme depends only on the id of the vertex in the input polygon. This procedure allows us to defer the synchronization between processors to the final stages of the algorithm, reduces the amount of overhead due to fine-grain synchronization, and helps makes the algorithm efficient.     

A parallel median algorithm

We give a deterministic algorithm for finding the kth smallest item in a set of n items, running in O((log log n)²) parallel time on O(n) processors in Valiant's comparison model.     

A parallel algorithm to construct a dominance graph on nonoverlapping rectangles

A parallel algorithm to generate the dominance graph on a collection of nonoverlapping iso-oriented rectangles is presented. This graph arises from the constraint graph commonly used in compaction algorithms for VLSI circuits. The dominance graph expresses the notion of aboveness on a collection of nonoverlapping rectangles: it is the directed graph which contains an edge from a rectangleb to rectanglec iffc is immediately aboveb. The algorithm is based on the divide and conquer paradigm; in the EREW PRAM model, it has time complexityO(log² n), usingn/logn processors. Its processor-time product isO(nlogn), which is optimal.     

A fast algorithm to compute irreducible and primitive polynomials in finite fields

In this paper we present a method to computeall the irreducible and primitive polynomials of degreem over the finite fieldGF(q). Our method finds each new irreducible or primitive polynomial with a complexity ofO(m) arithmetic operations inGF(q). The best previously known methods [3], [10] use the Berlekamp-Massey algorithm [7] and they have a complexityO(m ²). We reach mis improvement taking into account a systolic implementation [2] of the extended Euclidean algorithm instead of using the Berlekamp-Massey algorithm.This work was supported in part by Spanish Grant CICYT TIC91-0472.     

A simple parallel algorithm to draw cubic graphs

The main contribution of this work is to offer a simple and cost-efficient parallel algorithm that, given an arbitrary n-vertex cubic graph G as input, produces an orthogonal grid drawing of G in O(log n) time, using n processors on an EREW PRAM. Our algorithm matches the time and cost performance of the best previously-known algorithm while at the same time improving the constant factors involved in two important metrics: layout area and number of bends. More importantly, however, our algorithm stands out by its conceptual simplicity and ease of implementation.     

A linear time deterministic algorithm to find a small subset that approximates the centroid

Given a set of points S in any dimension, we describe a deterministic algorithm for finding a such that the centroid of T approximates the centroid of S within a factor 1+ε for any fixed ε>0. We achieve this in linear time by an efficient derandomization of the algorithm in [M. Inaba, N. Katoh, H. Imai, Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering (extended abstract), in: Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994, pp. 332-339].     

A parallel algorithm for constructing a labeled tree

A tree T is labeled when the n vertices are distinguished from one another by names such as v₁, v₂…v_n . Two labeled trees are considered to be distinct if they have different vertex labels even though they might be isomorphic. According to Cayley's tree formula, there are n^n-2 labeled trees on n vertices. Prufer used a simple way to prove this formula and demonstrated that there exists a mapping between a labeled tree and a number sequence. From his proof, we can find a naive sequential algorithm which transfers a labeled tree to a number sequence and vice versa. However, it is hard to parallelize. In this paper, we shall propose an O(log n) time parallel algorithm for constructing a labeled tree by using O(n) processors and O(n log n) space on the EREW PRAM computational model     

A parallel Viterbi decoding algorithm

In this paper we express the Viterbi algorithm as a matrix–vector reduction in which multiplication is replaced by addition and addition by minimization. The resulting algorithm is then readily parallelized in a form suitable for implementation on a systolic processor array. We describe the algorithm for Bose–Chaudhuri–Hocquenghem (BCH) codes which have a task graph with its valence restricted to four inputs and four outputs. The method is also applicable to convolution codes, but the complexity of the task graph increases with the number of input bits for these codes. Results for BCH codes are given for two general purpose parallel machines, an IBM SP2 and a Meiko CS2. Copyright © 2001 John Wiley & Sons, Ltd.     

A parallel shortest path algorithm

A new algorithm to find the shortest path between a pair of nodes is presented. In one hand this algorithm expands the search from origin and destination simultaneously, on the other hand it uses a lower bound for the shortest path to guide this search. Computational comparisons with existing algorithms show its efficiency. The implementation on a parallel computer is also discussed.     

A parallel optimal routing algorithm

In this paper we propose a new approach for solving optimal routing problems in packet-switched networks, a particular class of multicommodity convex network flow problems. The method developed here is designed to obtain a good rate of convergence while maintaining algorithmic simplicity and making effective use of parallel computing facilities.