A fast digital Radon transform—An efficient means for evaluating the Hough transform

A fast digital Radon transform based on recursively defined digital straight lines is described, which has the sequential complexity of N² log N additions for an N × N image. This transform can be used to evaluate the Hough transform to detect straight lines in a digital image. Whilst a parallel implementation of the Hough transform algorithm is difficult because of global memory access requirements, the fast digital Radon transform is vectorizable and therefore well suited for parallel computation. The structure of the fast algorithm is shown to be quite similar to the FFT algorithm for decimation in frequency. It is demonstrated that even for sequential computation the fast Radon transform is an attractive alternative to the classical Hough transform algorithm.     

On-Line File Caching

Abstract. Consider the following file caching problem: in response to a sequence of requests for files, where each file has a specified size and retrieval cost , maintain a cache of files of total size at most some specified k so as to minimize the total retrieval cost. Specifically, when a requested file is not in the cache, bring it into the cache and pay the retrieval cost, and remove other files from the cache so that the total size of files remaining in the cache is at most k . This problem generalizes previous paging and caching problems by allowing objects of arbitrary size and cost, both important attributes when caching files for world-wide-web browsers, servers, and proxies. We give a simple deterministic on-line algorithm that generalizes many well-known paging and weighted-caching strategies, including least-recently-used, first-in-first-out, flush-when-full, and the balance algorithm. On any request sequence, the total cost incurred by the algorithm is at most k/(k-h+1) times the minimum possible using a cache of size h ≤ k . For any algorithm satisfying the latter bound, we show it is also the case that for most choices of k , the retrieval cost is either insignificant or at most a constant (independent of k ) times the optimum. This helps explain why competitive ratios of many on-line paging algorithms have been typically observed to be constant in practice.     

A stability classification method and its application to pipelined solution of linear recurrences

A new method of classification for numerical stability of parallel algorithms is proposed based on the theoretical foundation of forward error analysis. It partitions the algorithms according to their asymptotic stability—a measure introduced to relate the limiting behavior of the stability to the size of the problem. Using this method, the stability aspect of the pipelined solution technique for first-order and second-order linear recurrences—the core of a tridiagonal linear equation solver—is studied. In particular, it shows that the pipelined solution method of the first-order linear recurrences has the same degree of stability as the commonly used sequential evaluation algorithms. The stability problems of sequential and pipelined solution methods of the second-order linear recurrences are also studied.     

Fast parallel Preconditioned Conjugate Gradient algorithms for robot manipulator dynamics simulation

In this paper fast parallel Preconditioned Conjugate Gradient (PCG) algorithms for robot manipulator forward dynamics, or dynamic simulation, problem are presented. By exploiting the inherent structure of the forward dynamics problem, suitable preconditioners are devised to accelerate the iterations. Also, based on the choice of preconditioners, a modified dynamic formulation is used to speedup both serial and parallel computation of each iteration. The implementation of the parallel algorithms on two interconnected processor arrays is discussed and their computation and communication complexities are analyzed. The simulation results for a Puma Arm are presented to illustrate the effectiveness of the proposed preconditioners. With a faster convergence due to preconditioning and a faster computation of iterations due to parallelization, the developed parallel PCG algorithms represent the fastest alternative for parallel computation of the problem withO(n) processors.     

Covering a string

We consider the problem of finding the repetitive structures of a given stringx. The periodu of the stringx grasps the repetitiveness ofx, sincex is a prefix of a string constructed by concatenations ofu. We generalize the concept of repetitiveness as follows: A stringw covers a stringx if there is a superstring ofx which is constructed by concatenations and superpositions ofw. A substringw ofx is called aseed ofx ifw coversx. We present anO(n logn)-time algorithm for finding all the seeds of a given string of lengthn.Partially supported by SERC Grants GR/F 00898 and GR/J 17844, NATO Grant CRG 900293, ESPRIT BRA Grant 7131 for ALCOMII, and MRC Grant G 9115730.Partially supported by MRC Grant G 9115730 and S.N.U. Posco Research Fund 94-15-1112.     

几种常用CT图像分割算法分析和探讨

图像分割是数字图像处理的一个经典难题。其分割质量的好坏直接影响到图像处理的后续工作。因而在理论研究和实际应用中受到研究人员的广泛重视。本文在总结了过去的分割方法基础上,就目前常用几种分割方法进行实验研究。主要包括阈值分割、LOG算子分割、FCM聚类分割、分水岭分割,并结合CT图像进行图像分割。文章阐述了各种分割方法的概念及原理,并在此基础上对分割结果进行了分析和探讨,得出各种方法的优点和不足。这些实验结论将为后续研究提供科学依据。     

基于移动锚节点的无线传感器网络圆心定位

文章提出了一种利用无线传感器网络无线信号接收强度（RSSI）和移动锚节点轨迹来获得待定节点位置的算法。该算法在有多个可移动锚节点的情况下,定位将会更加高效。在定位阶段,通过RSSI测得锚节点到待定节点的距离,并利用三个以上移动锚节点的坐标（包括三个）来求解圆的方程,计算出待定节点的位置。     

WSN中多路径路由协议算法的改进研究

不同于传统的网络,无线传感器网络能够协同地进行实时监测、感知和采集网络覆盖区域中监测对象的信息,并对其进行处理,处理后的信息通过无线方式传送,并以自组多跳的方式传送给观察者。路由协议的研究是无线传感器网络研究重点之一。蚁群算法是一种模仿自然界蚂蚁觅食的仿生算法,生物学家经过长期观察发现,蚂蚁总能够在巢穴和食物源之间找到一条最短路径。文中采用蚁群优化策略,给出了一种SMR多路径路由协议的改进算法ACO-SMR。该算法在保留SMR算法优点的基础上,进一步提高了资源利用率和路径稳定性,以及延长了网络生存时间。     

兴趣和蚁群相结合的非结构化P2P搜索算法

针对传统flooding搜索算法面临的效率低下和网络流量过大等问题,提出了一种改进的基于兴趣和蚁群相结合的资源搜索算法（IASA）。该算法将TTL机制加以改进,并将兴趣相似度引入到蚁群算法的路径概率选择中,同时结合信息素的多样性和正反馈机制,积累历史搜索经验,获得路由指引信息,从而有效地指导查询请求消息的转发,将请求消息尽量发往资源可能存在的节点上。仿真实验表明：该算法能有效地指导资源搜索的方向,提高查询命中率,减少冗余消息包,其整体搜索效果较好。