模板匹配的并行算法

模板匹配方法是检测图像边缘的重要方法之一.本文对模板匹配方法中的Prewitt算子进行了研究,提 出了用该算子检测图像边缘的快速算法、向量及分布式算法，并且在并行虚拟环境PVM上实现了分布式计算，加速效果明显。     

Parallel Algorithms for Image Template Matching on Hypercube SIMD Computers

This correspondence presents several parallel algorithms for image template matching on an SIMD array processor with a hypercube interconnection network. For an N by N image and an M by M window, the time complexity is reduced from O(N2M2) for the serial algorithm to O(M2/K2 + M * log2 N/K + log2 N * log2 K) for the N2K2-PE system (1 ? K ? M), or to O(N2M2/L2) for the L2-PE system (L ? N). With efficient use of the inter-PE communication network, each PE requires only a small local memory, many unnecessary data transmissions are eliminated, and the time complexity is greatly reduced.     

基于SSE2的模板匹配并行算法改进

Intel处理器的SSE2(Streaming SIMD Extensions 2,数据流单指令多数据扩展)技术,支持指令级SIMD操作,提供了单处理器上并行处理的解决方法。将模板匹配算法用SSE2 技术并行化,在Linux平台下用GCC编译实现。试验结果表明:SSE2技术大大加快了模板匹配的速度,能够在保证原有精度和稳定性基础上,解决了模板匹配方法计算量大、耗时多, 成本高的问题,有效地满足了在电子产品与制造等众多领域对计算机视觉技术的实时要求。     

基于频域的指纹图像增强算法

介绍一种基于频域的指纹图像增强算法,提出了一种新的纹线方向场估计方法,并根据纹线频谱分布特点,将求取方向场仅限定在了一个较小的圆环区域内进行。提出了基于纹线频谱能量分布的指纹图像滤波算法,它通过计算块频谱图中纹线频谱能量分布范围的变化自适应地改变角度滤波器通带范围。实验对比结果表明,经该算法增强后的图像脊谷信息清晰,具有较好的纹线增强效果。     

基于频域的指纹图像增强算法

介绍一种基于频域的指纹图像增强算法,提出了一种新的纹线方向场估计方法,并根据纹线频谱分布特点,将求取方向场仅限定在了一个较小的圆环区域内进行.提出了基于纹线频谱能量分布的指纹图像滤波算法,它通过计算块频谱图中纹线频谱能量分布范围的变化自适应地改变角度滤波器通带范围.实验对比结果表明,经该算法增强后的图像脊谷信息清晰,具有较好的纹线增强效果.     

一种改进的图像模板细化算法

针对现有图像模板细化算法中存在的诸如迭代次数较多、细化速度较慢、图像某些部位细化不完全等问题，提出了一组改进的细化模板。针对指纹图像应用新算法进行的细化实验结果表明，采用改进的细化模板，新算法在保证对图像完全细化的同时，能显著减少细化所需的迭代次数，从而加快了细化处理速度。     

一种改进模板的OPTA细化算法

本文首先介绍了指纹识别系统中目前常用的两种OPTA细化算法,并针对这两种算法的不足,重新构建了细化模块,提出了一种新的细化算法.经过实验证明,该算法能够很好地满足细化要求,在保证指纹骨架处于纹线中心线的同时,不仅减少了毛刺的出现,使细化后的纹线更均匀,更清晰流畅,而且较大幅度地提高了细化速度,缩短了处理时间,从而节约了所需的内存空间.     

一种改进的人眼模板匹配算法

以驾驶员疲劳检测为背景,针对红外图像的人眼定位问题,提出了一种改进的模板匹配算法。该算法采用多步长模板匹配的策略,大大压缩了模板匹配过程中的计算量,同时充分利用了人眼位置的位置特征,把左右眼的位置关系作为人眼最终定位的约束条件。实验结果表明,与传统模板匹配算法相比,该算法能够显著提高人眼的定位速度和定位准备率。     

基于高斯模板的图象旋转算法

图象旋转是图象处理中的一个基本操作,根据图象在邻近区域内连续的特点,该文提出一种基于高斯模板的图象旋转算法。实验结果表明,该算法能较好地消除图象旋转所产生的锯齿现象,图象多次旋转后失真较少,与最近插值和双线性插值相比具有较好的性能。     

图象中一种不规则边界圆的参数求取方法

文章提出了一种基于曲线拟合法求取图象中不规则边界圆的参数的求取方法。在进行图象的预处理得到一个不规则边界圆的边界数据点集的基础上,该算法首先引入替代变量,使圆方程拟合法求圆参数成为可能;然后进行圆参数的多次迭代拟合,边拟合边剔除拟合点集中的不规则圆边界点,直到符合终止条件为止,成功地求出了圆参数的最佳估值。试验证明,和传统的广义Hough变换相比,该算法具有运算速度快、自动求取的突出优点,在不规则边界点所占整个圆边界点比例较小时能取得很好的结果。     

An Experimental Analysis of Parallel Sorting Algorithms

We have developed a methodology for predicting the performance of parallel algorithms on real parallel machines. The methodology consists of two steps. First, we characterize a machine by enumerating the primitive operations that it is capable of performing along with the cost of each operation. Next, we analyze an algorithm by making a precise count of the number of times the algorithm performs each type of operation. We have used this methodology to evaluate many of the parallel sorting algorithms proposed in the literature. Of these, we selected the three most promising, Batcher's bitonic sort, a parallel radix sort, and a sample sort similar to Reif and Valiant's flashsort, and implemented them on the connection Machine model CM-2. This paper analyzes the three algorithms in detail and discusses the issues that led us to our particular implementations. On the CM-2 the predicted performance of the algorithms closely matches the observed performance, and hence our methodology can be used to tune the algorithms for optimal performance. Although our programs were designed for the CM-2, our conclusions about the merits of the three algorithms apply to other parallel machines as well. Received April 1996, and in final form June 1996.     

生成距离图的同心圆窗口矩匹配快速算法

针对半导体封装等工业应用对图像模板匹配的速度要求很高的特点,进行了快速模板匹配算法的研究.同心圆窗口矩匹配是一种速度较快的算法,是将模板分成一系列的同心圆环,然后通过比较模板和待检测图像上对应圆环的零阶矩确定可能匹配点.但由于确定各像素点属于哪一个圆环需要进行复杂的乘积运算,耗费了大量时间.为此,提出了一种生成距离图的改进算法,即匹配前对模板进行预处理,生成距离图,即各像元存储的是距离图像中心（圆心）的半径值.这样,确定像素属于哪一个圆环,只需要经过对各像素的索引值的简单比较,就可以确定.经过实验验证,改进算法可以大大提高模板匹配的速度,满足半导体封装等自动化作业的需求.     

An Optimal Parallel Matching Algorithm for Cographs

The class of cographs, or complement-reducible graphs, arises naturally in many different areas of applied mathematics and computer science. We show that the problem of finding a maximum matching in a cograph can be solved optimally in parallel by reducing it to parenthesis matching. With an n-vertex cograph G represented by its parse tree as input, our algorithm finds a maximum matching in G in O(log n) time using O(n/log n) processors in the EREW-PRAM model.     

Multisets排序的最优并行算法

排序是一个既有十分重要的理论意义又有广泛的实际应用价值的问题 ,其中 ,Multisets排序问题是指对只有k个不同关键字值的n个数据 (记录 )进行排序 ,0 相似文献   

K元2—立方体网络SIMD计算机图像模板匹配并行算法

模板匹配是进行虑波、边缘检测、目标识别和图像匹配的一种基本和有效的方法 .对于 N× N的图像和M× N ( M相似文献   

并行数据库中JOIN运算的并行算法

JOIN运算的并行算法一直是并行数据库领域中研究的热点问题,先后出现了一系列并行JOIN算法或改进算法,但它们都存在着通信效率较低、负载调度频繁等问题。本文针对这些问题,在分析比较前人工作的基础上对湖＋算法与ABJ＋算法加以改进,得到了效率更高的并行JOIN算法ABJ＋＋。     

An Approach to Correctness of Data Parallel Algorithms

The design of data parallel algorithms for fine-grain machines is a fundamental domain in today′s computer science. High standards in the specification and resolution of problems have been achieved in the sequential case. It seems reasonable to apply the same level of quality to data parallel programs. It appears that most data parallel problems can be specified in terms of pre- and postconditions. These conditions characterize the overall state of the fine-grain processors in the initial and final states. In this paper:

• •We present an axiomatic system to prove correctness of data parallel algorithms on single-instruction multiple-data (SIMD) machines.
• •We specify some data parallel problems like tree sum, root finding, radix sorting, and dynamic memory allocation.
• •With this set of axioms we prove the correctness of programs solving the problems above.

It seems that the framework for data parallel problems is quite different from those for problems of parallelism with multiple threads of control, like those solvable in Communicating Sequential Processes (CSP).     

An Optimal Parallel Co-Connectivity Algorithm

In this paper we consider the problem of computing the connected components of the complement of a given graph. We describe a simple sequential algorithm for this problem, which works on the input graph and not on its complement, and which for a graph on n vertices and m edges runs in optimal O(n+m) time. Moreover, unlike previous linear co-connectivity algorithms, this algorithm admits efficient parallelization, leading to an optimal O(log n)-time and O((n+m)log n)-processor algorithm on the EREW PRAM model of computation. It is worth noting that, for the related problem of computing the connected components of a graph, no optimal deterministic parallel algorithm is currently available. The co-connectivity algorithms find applications in a number of problems. In fact, we also include a parallel recognition algorithm for weakly triangulated graphs, which takes advantage of the parallel co-connectivity algorithm and achieves an O(log² n) time complexity using O((n+m²) log n) processors on the EREW PRAM model of computation.     

背包问题的最优并行算法

利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2^n/4)^1-ε个并行处理机单元,0≤ε≤1,O(2^n/2)个存储单元,在O(2^n/4(2^n/4)^ε)时间内求解n维背包问题,算法的成本为O(2^n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.