An FPGA implementation of real-time K-means clustering for color images

K-means clustering is a very popular clustering technique, which is used in numerous applications. In the k-means clustering algorithm, each point in the dataset is assigned to the nearest cluster by calculating the distances from each point to the cluster centers. The computation of these distances is a very time-consuming task, particularly for large dataset and large number of clusters. In order to achieve high performance, we need to reduce the number of the distance calculations for each point efficiently. In this paper, we describe an FPGA implementation of k-means clustering for color images based on the filtering algorithm. In our implementation, when calculating the distances for each point, clusters which are apparently not closer to the point than other clusters are filtered out using kd-trees which are dynamically generated on the FPGA in each iteration of k-means clustering. The performance of our system for 512 × 512 and 640 × 480  pixel images (24-bit full color RGB) is more than 30 fps, and 20–30 fps for 756 × 512 pixel images in average when dividing to 256 clusters.

Continuous‐time Kalman filtering on the orthogonal group O(n)

This paper presents a continuous‐time O(n)‐constrained Kalman‐like filter. O(n) is the group of n × n orthonormal matrices. The O(n)‐constrained Kalman‐like filter is derived by posing a constrained optimization problem. The solution involves a projection of the unconstrained Kalman state estimate derivative onto the tangent space of O(n). Using this filter, an extended O(n)‐constrained Kalman‐like filter is developed for nonlinear systems where a portion of the states evolve on O(n). A numerical example demonstrates the effectiveness of the extended O(n)‐constrained Kalman‐like filter. Copyright © 2017 John Wiley & Sons, Ltd.     

A fast algorithm for constructing nearly optimal prefix codes

Huffman algorithm allows for constructing optimal prefix‐codes with O(n·logn) complexity. As the number of symbols ngrows, so does the complexity of building the code‐words. In this paper, a new algorithm and implementation are proposed that achieve nearly optimal coding without sorting the probabilities or building a tree of codes. The complexity is proportional to the maximum code length, making the algorithm especially attractive for large alphabets. The focus is put on achieving almost optimal coding with a fast implementation, suitable for real‐time compression of large volumes of data. A practical case example about checkpoint files compression is presented, providing encouraging results. Copyright © 2015 John Wiley & Sons, Ltd.     

Fast Dynamic Transitive Closure with Lookahead

In this paper we consider the problem of dynamic transitive closure with lookahead. We present a randomized one-sided error algorithm with updates and queries in O(n ^{ω(1,1,ε)−ε} ) time given a lookahead of n ^ε operations, where ω(1,1,ε) is the exponent of multiplication of n×n matrix by n×n ^ε matrix. For ε≤0.294 we obtain an algorithm with queries and updates in O(n ^2−ε ) time, whereas for ε=1 the time is O(n ^ω−1). This is essentially optimal as it implies an O(n ^ω ) algorithm for boolean matrix multiplication. We also consider the offline transitive closure in planar graphs. For this problem, we show an algorithm that requires O(n^\fracw2)O(n^{\frac{\omega}{2}}) time to process n^\frac12n^{\frac{1}{2}} operations. We also show a modification of these algorithms that gives faster amortized queries. Finally, we give faster algorithms for restricted type of updates, so called element updates. All of the presented algorithms are randomized with one-sided error. All our algorithms are based on dynamic algorithms with lookahead for matrix inverse, which are of independent interest.     

Observer‐based finite‐time output‐feedback controller for DC‐DC buck converters with unknown load variations

The output voltage regulation problem of a DC‐DC buck converter is investigated in this paper via an observer‐based finite‐time output‐feedback control approach. Considering the effects of unknown load variations and the case without current sensor, by using the technique of adding a power integrator and the idea of nonseparation principle, a finite‐time voltage regulation control algorithm via dynamic output feedback is designed. The main feature of the designed observer and controller does not need any load's information. Theoretically, it is proven that the output voltage can reach the desired voltage in a finite time under the proposed controller. The effectiveness of the proposed control method is illustrated by numerical simulations and experimental results.     

Efficient construction of bounding volume hierarchies into a complete octree for ray tracing

This paper proposes an efficient construction scheme for bounding volume hierarchies based on a complete tree. This construction offers up to 4× faster construction times than binned‐surface area heuristic and offers competitive ray traversal performance. The construction is fully parallelized on x86 CPU architectures; it takes advantage of the eight‐wide vector units and exploits the advance vector extensions available for current x86 CPU architectures. Additionally, this work presents a clustering algorithm for grouping primitives, which can be computed in linear time O(n). Furthermore, this construction uses the graphics processing unit to perform intensive operations efficiently. Copyright © 2016 John Wiley & Sons, Ltd.     

RNA二级结构预测中动态规划的优化和有效并行

基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n⁴)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n²×k²)算法;Lyngso方法根据环的能量规则,不限制环的大小,在O(n3)的时间内获得近似最优解.通过使用额外的O(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在O(n³)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比.     

Calculating optimal addition chains

An addition chain is a finite sequence of positive integers 1 = a ₀ ≤ a ₁ ≤ · · · ≤ a _r = n with the property that for all i > 0 there exists a j, k with a _i = a _j + a _k and r ≥ i > j ≥ k ≥ 0. An optimal addition chain is one of shortest possible length r denoted l(n). A new algorithm for calculating optimal addition chains is described. This algorithm is far faster than the best known methods when used to calculate ranges of optimal addition chains. When used for single values the algorithm is slower than the best known methods but does not require the use of tables of pre-computed values. Hence it is suitable for calculating optimal addition chains for point values above currently calculated chain limits. The lengths of all optimal addition chains for n ≤ 2³² were calculated and the conjecture that l(2n) ≥ l(n) was disproved. Exact equality in the Scholz–Brauer conjecture l(2 ⁿ − 1) = l(n) + n − 1 was confirmed for many new values.     

Modular configuration of service elements based on the improved K‐means algorithm

To reduce the vagueness and subjectivity of customer demand in the process of product–service system design, a fuzzy semantic calculation method is proposed to obtain the importance of service demand. In addition, according to the demand of the clustering of service modules, a new clustering method is proposed to analyse discrete data based on the improved K‐means algorithm that is based on the Kruskal algorithm. According to the criterion of the service module division and its weight, the correlation coefficient between any two service activities is judged to form the comprehensive correlation coefficient matrix, and the comprehensive dissimilarity matrix can be obtained by the additive model. Then, this method calculates the minimum cost spanning tree (MCST) using the Kruskal algorithm. The different clusters of service activities with different centres can be found based on the MCST, and the edge values can be calculated by the improved K‐means algorithm. This paper uses 28 service activities of excavators. These activities can be divided into K (K = 4, 5, 6, and 7) clusters by the improved K‐means algorithm. Finally, the service element configuration model is established based on the demand weight, which is optimized by using the maximum customer satisfaction of competition.     

Interactive color image segmentation with linear programming

Image segmentation is an important and fundamental task for image and vision understanding. This paper describes a linear programming (LP) approach for segmenting a color image into multiple regions. Compared with the recently proposed semi-definite programming (SDP)-based approach, our approach has a simpler mathematical formulation, and a far lower computational complexity. In particular, to segment an image of M × N pixels into k classes, our method requires only O((M N k) ^m ) complexity—a sharp contrast to the complexity of O((M N k)²ⁿ ) if the SDP method is adopted, where m and n are the polynomial complexity of the corresponding LP solver and SDP solver, respectively (in general we have m≪ n). Such a significant reduction in computation readily enables our algorithm to process color images of reasonable sizes. For example, while the existing SDP relaxation algorithm is only able to segment a toy-size image of, e.g., 10 × 10 to 30 × 30 pixels in hours time, our algorithm can process larger color image of, say, 100 × 100 to 500 × 500 image in much shorter time.     

Sequential Maximum Correntropy Kalman Filtering

This paper explores a linear state estimation problem in non‐Gaussian setting and suggests a computationally simple estimator based on the maximum correntropy criterion Kalman filter (MCC‐KF). The first MCC‐KF method was developed in Joseph stabilized form. It requires two n × n and one m × m matrix inversions, where n is a dimension of unknown dynamic state to be estimated, and m is a dimension of available measurement vector. Therefore, the estimator becomes impractical when the system dimensions increase. Our previous work has suggested an improved MCC‐KF estimator (IMCC‐KF) and its factored‐from (square‐root) implementations that enhance the MCC‐KF estimation quality and numerical robustness against roundoff errors. However, the proposed IMCC‐KF and its square‐root implementations still require the m × m matrix inversion in each iteration step of the filter. For numerical stability and computational complexity reasons it is preferable to avoid the matrix inversion operation. In this paper, we suggest a new IMCC‐KF algorithm that is more accurate and computationally cheaper than the original MCC‐KF and previously suggested IMCC‐KF. Furthermore, compared with stable square‐root algorithms, the new method is also accurate, but less computationally expensive. The results of numerical experiments substantiate the mentioned properties of the new estimator on numerical examples.     

An accelerated randomized Kaczmarz method via low-rank approximation

The Kaczmarz method for finding the solution to an overdetermined consistent system of linear equation Ax=b(A∈R^m×n) is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Recently, Strohmer and Vershynin proposed randomized Kaczmarz, and proved its exponential convergence. In this paper, motivated by idea of precondition, we present a modified version of the randomized Kaczmarz method where an orthogonal matrix was multiplied to both sides of the equation Ax=b, and the orthogonal matrix is obtained by low-rank approximation. Our approach fits the problem when m is huge and m?n. Theoretically, we improve the convergence rate of the randomized Kaczmarz method. The numerical results show that our approach is faster than the standard randomized Kaczmarz.     

A Bloom filter based semi‐index on q‐grams

We present a simple q‐gram based semi‐index, which allows to look for a pattern typically only in a small fraction of text blocks. Several space‐time tradeoffs are presented. Experiments on Pizza & Chili datasets show that our solution is up to three orders of magnitude faster than the Claude et al. (Journal of Discrete Algorithms 2012; 11 :37) semi‐index at a comparable space usage. Moreover, the construction of our data structure is fast and easily parallelizable. Copyright © 2016 John Wiley & Sons, Ltd.     

Symmetry Partition Sort

In this paper, we propose a useful replacement for quicksort‐style utility functions. The replacement is called Symmetry Partition Sort, the principle of which is similar to that of Proportion Extend Sort. The main characteristic of the new algorithm is that it always places partially sorted inputs (used as a basis for proportional extensions) at each end of an array when entering the partitioning routine. This is advantageous in speeding up the processing for partitioning. The library function we developed based on the new algorithm is more attractive than the Psort library function introduced in 2004 because of its simple implementation mechanism, clearer source code, and faster operation with a performance guarantee of O(n log n). Increased robustness and adaptivity also make it highly competitive as a library function. Copyright © 2007 John Wiley & Sons, Ltd.     

Efficient viewshed computation on terrain in external memory

The recent availability of detailed geographic data permits terrain applications to process large areas at high resolution. However the required massive data processing presents significant challenges, demanding algorithms optimized for both data movement and computation. One such application is viewshed computation, that is, to determine all the points visible from a given point p. In this paper, we present an efficient algorithm to compute viewsheds on terrain stored in external memory. In the usual case where the observer’s radius of interest is smaller than the terrain size, the algorithm complexity is θ(scan(n ²)) where n ² is the number of points in an n × n DEM and scan(n ²) is the minimum number of I/O operations required to read n ² contiguous items from external memory. This is much faster than existing published algorithms.     

Fast algorithms for long transportation problems

The paper deals with large transportation problems in which the number of destinations (n) is much larger than the number of origins (m), and in which some or many of the paths from origins to destinations may be inadmissible. Using a new approach, with certain auxilary lists, it is proved that the ordinary simplex algorithm (“Most Negative Rule”) can be performed in O(m²+ m log n) computer operations per iteration, as against O(mn) in the usual approach. A search-in-a-row simplex algorithm (“Row Most Negative Rule”), for which the total number of iterations is probably only somewhat larger, is shown to require just O(m + σm log n) operations per iteration, where σ is the density of the cost matrix (i.e. the proportion of admissible paths). For these rigorous results one needs computer storage which is not considerably larger than that required for storing the cost matrix. For smaller memory an efficient algorithm is also proposed. A general tentative rule for die amount of scanning per iteration is introduced and applied. Computer experiments are reported, confirming theoretical estimates.     

虫孔路由Mesh上的连通分量算法及其应用

用倍增技术在带有Wormhole路由技术的n×n二维网孔机器上提出了时间复杂度为O(log²n)的连通分量和传递闭包并行算法,并在此基础上提出了一个时间复杂度为O(log³n)的最小生成树并行算法.这些都改进了Store-and-Forward路由技术下的时间复杂度下界O(n).同其他运行在非总线连接分布式存储并行计算机上的算法相比,此连通分量和传递闭包算法的时间复杂度是最优的.     

Fast adaptive algorithms for minor component analysis using Householder transformation

In this paper, we propose new adaptive algorithms for the extraction and tracking of the least (minor) or eventually, principal eigenvectors of a positive Hermitian covariance matrix. The main advantage of our proposed algorithms is their low computational complexity and numerical stability even in the minor component analysis case. The proposed algorithms are considered fast in the sense that their computational cost is O(np) flops per iteration where n is the size of the observation vector and p<n is the number of eigenvectors to estimate.We consider OJA-type minor component algorithms based on the constraint and non-constraint stochastic gradient technique. Using appropriate fast orthogonalization procedures, we introduce new fast algorithms that extract the minor (or principal) eigenvectors and guarantee good numerical stability as well as the orthogonality of their weight matrix at each iteration. In order to have a faster convergence rate, we propose a normalized version of these algorithms by seeking the optimal step-size. Our algorithms behave similarly or even better than other existing algorithms of higher complexity as illustrated by our simulation results.     

Lightweight Data Indexing and Compression in External Memory

In this paper we describe algorithms for computing the Burrows-Wheeler Transform (bwt) and for building (compressed) indexes in external memory. The innovative feature of our algorithms is that they are lightweight in the sense that, for an input of size n, they use only n bits of working space on disk while all previous approaches use Θ(nlog n) bits. This is achieved by building the bwt directly without passing through the construction of the Suffix Array/Tree data structure. Moreover, our algorithms access disk data only via sequential scans, thus they take full advantage of modern disk features that make sequential disk accesses much faster than random accesses. We also present a scan-based algorithm for inverting the bwt that uses Θ(n) bits of working space, and a lightweight internal-memory algorithm for computing the bwt which is the fastest in the literature when the available working space is o(n) bits. Finally, we prove lower bounds on the complexity of computing and inverting the bwt via sequential scans in terms of the classic product: internal-memory space × number of passes over the disk data, showing that our algorithms are within an O(log n) factor of the optimal.     

Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax k vertex-disjoint paths in a directed acyclic graph

This paper is composed of two parts. In the first part, an improved algorithm is presented for the problem of finding length-bounded two vertex-disjoint paths in an undirected planar graph. The presented algorithm requires O(n³bmin) time and O(n²bmin) space, where bmin is the smaller of the two given length bounds. In the second part of this paper, we consider the minmax k vertex-disjoint paths problem on a directed acyclic graph, where k?2 is a constant. An improved algorithm and a faster approximation scheme are presented. The presented algorithm requires O(nk+1Mk−1) time and O(nkMk−1) space, and the presented approximation scheme requires O((1/?)^k−1n2klogk−1M) time and O((1/?)^k−1n2k−1logk−1M) space, where ? is the given approximation parameter and M is the length of the longest path in an optimal solution.