Road Detection and Tracking from Aerial Desert Imagery

We present a fast, robust road detection and tracking algorithm for aerial images taken from an Unmanned Aerial Vehicle. A histogram-based adaptive threshold algorithm is used to detect possible road regions in an image. A probabilistic hough transform based line segment detection combined with a clustering method is implemented to further extract the road. The proposed algorithm has been extensively tested on desert images obtained using an Unmanned Aerial Vehicle. Our results indicate that we are able to successfully and accurately detect roads in 96% of the images. We experimentally validated our algorithm on over a thousand aerial images obtained using our UAV. These images consist of straight and curved roads in various conditions with significant changes in lighting and intensity. We have also developed a road-tracking algorithm that searches a local rectangular area in successive images. Initial results are presented that shows the efficacy and the robustness of this algorithm. Using this road tracking algorithm we are able to further improve the road detection and achieve a 98% accuracy.     

Limits on super-resolution and how to break them

Nearly all super-resolution algorithms are based on the fundamental constraints that the super-resolution image should generate low resolution input images when appropriately warped and down-sampled to model the image formation process. (These reconstruction constraints are normally combined with some form of smoothness prior to regularize their solution.) We derive a sequence of analytical results which show that the reconstruction constraints provide less and less useful information as the magnification factor increases. We also validate these results empirically and show that, for large enough magnification factors, any smoothness prior leads to overly smooth results with very little high-frequency content. Next, we propose a super-resolution algorithm that uses a different kind of constraint in addition to the reconstruction constraints. The algorithm attempts to recognize local features in the low-resolution images and then enhances their resolution in an appropriate manner. We call such a super-resolution algorithm a hallucination or reconstruction algorithm. We tried our hallucination algorithm on two different data sets, frontal images of faces and printed Roman text. We obtained significantly better results than existing reconstruction-based algorithms, both qualitatively and in terms of RMS pixel error     

Approximating MIN 2-SAT and MIN 3-SAT

We obtain substantially improved approximation algorithms for the MIN k-SAT problem, for k = 2,3. More specifically, we obtain a 1.1037-approximation algorithm for the MIN 2-SAT problem, improving a previous 1.5-approximation algorithm, and a 1.2136-approximation algorithm for the MIN 3-SAT problem, improving a previous 1.75-approximation algorithm for the problem. These results are obtained by adapting techniques that were previously used to obtain approximation algorithms for the MAX k-SAT problem. We also obtain some hardness of approximation results.     

Boosting a Weak Learning Algorithm by Majority

We present an algorithm for improving the accuracy of algorithms for learning binary concepts. The improvement is achieved by combining a large number of hypotheses, each of which is generated by training the given learning algorithm on a different set of examples. Our algorithm is based on ideas presented by Schapire and represents an improvement over his results, The analysis of our algorithm provides general upper bounds on the resources required for learning in Valiant′s polynomial PAC learning framework, which are the best general upper bounds known today. We show that the number of hypotheses that are combined by our algorithm is the smallest number possible. Other outcomes of our analysis are results regarding the representational power of threshold circuits, the relation between learnability and compression, and a method for parallelizing PAC learning algorithms. We provide extensions of our algorithms to cases in which the concepts are not binary and to the case where the accuracy of the learning algorithm depends on the distribution of the instances.     

A parallel Monte Carlo transport algorithm using a pseudo-random tree to guarantee reproducibility

We present a parallel Monte Carlo photon transport algorithm that insures the reproducibility of results. The important feature of this parallel implementation is the introduction of a pair of pseudo-random number generators. This pair of generators is structured in such a manner as to insure minimal correlation between the two sequences of pseudo-random numbers produced. We term this structure as a ‘pseudo-random tree’. Using this structure, we are able to reproduce results exactly in a asynchronous parallel processing environment. The algorithm tracks the history of photons as they interact with two carbon cylinders joined end to end. The algorithm was implemented on both a Denelcor HEP and a CRAY X-MP/48. We describe the algorithm and the pseudo-random tree structure and present speedup results of our implementation.     

Performance of a benchmark parallel implementation of the Van Slyke and Wets algorithm for two-stage stochastic programs on the Sequent/Balance

We describe a benchmark parallel version of the Van Slyke and Wets (1969) algorithm for two-stage stochastic programs and an implementation of that algorithm on the Sequent/Balance. We also report results of a numerical experiment using random test problems and our implementation. These performance results, to the best of our knowledge, are the first available for the Van Slyke and Wets (1969) algorithm on a parallel processor. They indicate that the benchmark implementation parallelizes well.     

利用位置测量的单点和两点差分跟踪起始算法的比较研究

We consider the problem of initializing the tracking filter of a target moving with nearly constant velocity when position-only (1D, 2D, or 3D) measurements are available. It is known that the Kalman filter is optimal for such a problem, provided it is correctly initialized. We compare a single-point and the well-known two-point difference track initialization algorithms. We analytically show that if the process noise approaches zero and the maximum speed of a target used to initialize the velocity variance approaches infinity, then the single-point algorithm reduces to the two-point difference algorithm. We present numerical results that show that the single-point algorithm performs consistently better than the two-point difference algorithm in the mean square error sense. We also present analytical results that support the conjecture that this is true in general.     

基于SIFT的图像匹配算法

直接用SIFT算法对较模糊图像进行关键点提取时,提取的关键点个数较少且进行下一步匹配时错误匹配较多。提出一种基于SIFT特征的匹配算法,首先利用拉普拉斯算子对图像进行锐化处理,使其边缘得到突出,然后利用SIFT算法进行关键点提取,最后利用双向匹配算法进行图像匹配。实验结果表明,利用本文算法进行匹配比直接用SIFT算法进行匹配时的匹配点数更多,匹配效果更好。     

On deciding finiteness of matrix groups

We provide a new, practical algorithm for deciding finiteness of matrix groups over function fields of zero characteristic. The algorithm has been implemented in GAP. Experimental results and extensions of the algorithm to any field of zero characteristic are discussed.     

混沌搜索策略的改进人工蜂群算法

针对人工蜂群算法的蜂群缺乏多样性、全局和局部搜索能力差及收敛速度较慢,提出一种基于混沌搜索策略的改进人工蜂群算法。该算法通过载波映射,由混沌-决策变量的变换,产生新的邻域点,为采蜜蜂和被招募的观察蜂提供了更广阔的搜索空间和更优质的位置蜜源,增强蜂群多样性;同时,引进侦查蜂局部蜜源搜索较好地解决了算法易陷入局部极小的问题,改善了人工蜂群算法的收敛性能。最后由6个标准测试函数的仿真验证,得到基于混沌搜索策略的人工蜂群算法性能明显优于标准人工蜂群算法。     

Edge detection using ant algorithms

In this paper a new algorithm for edge detection using ant colony search is proposed. The problem is represented by a directed graph in which nodes are the pixels of an image. To adapt the problem, some modifications on original ant colony search algorithm (ACSA) are applied. A large number of experiments are employed to determine suitable algorithm parameters. We drive an experimental relationship between the size of the image to be analyzed and algorithm parameters. Several experiments are made and the results suggest the effectiveness of the proposed algorithm.     

Sequencing in mixed model assembly lines: A genetic algorithm approach

The mixed model assembly lines are becoming increasingly popular in a wide area of industries. We consider the sequencing problem in mixed model assembly lines, which is critical for efficient utilization of the lines. We extend standard formulation of the problem to allow a hybrid assembly line, in which closed and open workstations are intermixed, and sequence-dependent setup time. A new approach using an artificial intelligence search technique, called genetic algorithm, is proposed. A genetic representation suitable for the problem is investigated, and genetic control parameters that yield good results are empirically found. A new genetic operator, Immediate Successor Relation Crossover (ISRX), is introduced and several existing ones are modified. An extensive experiment is carried out to determine a proper choice of the genetic operators. The performance of the genetic algorithm is compared with those of heuristic algorithm and of branch-and-bound method. The results show that our algorithm greatly reduces the computation time and its solution is very close to the optimal solution. We have identified the ISRX operator to play a significant role in improving the performance.     

基于离散量优化初始聚类中心的k-means算法

传统k-means算法由于初始聚类中心的选择是随机的,因此会使聚类结果不稳定。针对这个问题,提出一种基于离散量改进k-means初始聚类中心选择的算法。算法首先将所有对象作为一个大类,然后不断从对象数目最多的聚类中选择离散量最大与最小的两个对象作为初始聚类中心,再根据最近距离将这个大聚类中的其他对象划分到与之最近的初始聚类中,直到聚类个数等于指定的k值。最后将这k个聚类作为初始聚类应用到k-means算法中。将提出的算法与传统k-means算法、最大最小距离聚类算法应用到多个数据集进行实验。实验结果表明,改进后的k-means算法选取的初始聚类中心唯一,聚类过程的迭代次数也减少了,聚类结果稳定且准确率较高。     

Stochastic optimisation with inequality constraints using simultaneous perturbations and penalty functions

We present a stochastic approximation algorithm based on penalty function method and a simultaneous perturbation gradient estimate for solving stochastic optimisation problems with general inequality constraints. We present a general convergence result that applies to a class of penalty functions including the quadratic penalty function, the augmented Lagrangian, and the absolute penalty function. We also establish an asymptotic normality result for the algorithm with smooth penalty functions under minor assumptions. Numerical results are given to compare the performance of the proposed algorithm with different penalty functions.     

Motion analysis of isolated targets in infrared image sequences

We describe a simple algorithm for estimating the 3-D motion of isolated targets in infrared image sequences. The algorithm is based on analyzing the changes in the shapes and the relative positions of segmented image regions. Experimental results of applying this algorithm to single IR images and to an image sequence are presented.     

Interval-indexed formulation based heuristics for single machine total weighted tardiness problem

In this paper, we solve the single machine total weighted tardiness problem by using integer programming and linear programming based heuristic algorithms. Interval-indexed formulation is used to formulate the problem. We discuss several methods to form the intervals and different post-processing methods. Then, we show how our algorithm can be used to improve a population of a genetic algorithm. We also provide some computational results that show the effectiveness of our algorithm. Many aspects of our heuristic algorithm are quite general and can be applied to other scheduling and combinatorial optimization problems.     

Segmentation of discrete point clouds using an extensible set of templates

We present an algorithm for segmenting a discrete three-dimensional point-set (i.e., partitioning an input discrete point-set into appropriate subsets). The algorithm consists in the iteration of two main steps which are: fitting the parameters of template primitives from a user-specified list of primitives and extracting the points from the input point-set matching the best fitted primitive. We illustrate the results of applying our algorithm to several examples of three-dimensional point-sets.     

基于相对熵的SIP DoS洪泛攻击检测算法和仿真

随着SIP协议的广泛应用,SIP网络的安全机制也逐渐成为研究热点.针对SIP DoS洪泛攻击,本文将相对熵引入SIP网络,提出了一种基于相对熵的检测算法,并与传统的信息熵检测算法进行比较.实验结果表明:正常网络流量下信息熵值和相对熵值都基本稳定,在发生DoS攻击时相对熵值波动明显,比信息熵检测算法检测率更高,检测结果更准确.     

Application of a breeder genetic algorithm for filter optimization

In this work we are optimizing an adaptive finite impulse response filter applied to the problem of system identification. We are proposing a breeder genetic algorithm (BGA) for performing the parametric search in highly multimoldal landscapes since in this kind of filters there exits epistiasis. The results of BGA were compared to the traditional genetic algorithm, and we found that the BGA was clearly superior (in accuracy) in most of the cases. We used the statistical least mean squared for validating the results. We suggest to hybridized both methods for real world applications.