共查询到19条相似文献,搜索用时 240 毫秒
1.
本文给出了满足三角不等式的货郎担问题的并行启发式算法,在SIMD CREV PRAM并行机上该算法使用O(n^3/log^2n)台处理器需O熄log^2n)时间,这里n是给定城市的个数,因而该并行算法是最优的。 相似文献
2.
3.
陆哲明 《中国图象图形学报》2000,5(10):846-850
近年来,许多学者已经成功地将Kohonen的自组织特征映射(SOFM)神经网络应用于矢量量化(VQ)图象压缩编码,相对于传统的KLBG算法,基于的SOFM算法的两个主要缺点是计算量大和生成的码书性能较差因此为了改善码书性能,对基本的SOFM算法的权值调整方法作了一些改进,同时为了降低计算量,又在决定获得胜神经元的过程中,采用快速搜索算法,在将改进的算法用于矢量量化码书设计后,并把生成的码书用于图象 相似文献
4.
本文引进相对的多项式化归和相对多一多项式同构等概念,对UP、βn的FewP的相对完全集讨论它们的相对同构问题。并得到如下结果:1(1)对任何≤m^P,Bn-βn^Bn完全集C,C≈P^BnAn←→C为P^Bn柱。(2)对任何≤m^P,B-FewP^B完全集C,C≈P^B∪An←→C为P^B柱,其中B=SAT-∪An。 n∈N n∈N 相似文献
5.
窄带宽环境下的动态图像压缩 总被引:2,自引:0,他引:2
实现窄带宽环境下的动态图像传输需要对图像数据进行有效压缩。提出采用改进的小波零树编码算法,在零树编码过程中,对连续零树根所采用的游程编码以及对非零小波系数的编码采用了一种新的码扩展算法,与通常的码扩展法相比具有单位比特拥有更大信息量的特点,并且运用图像拼接技术缓解了小波图像压缩在小尺寸图像上不理想的问题。 相似文献
6.
7.
本文利用Toeplitz矩阵可分解为循环阵与斜循环阵之和的特点2,借助于卷积的FFT算法,推导出计算两个Toeplitz矩阵之积的一种新的快速算法,其乘法复杂性为2n^2+O(nlog2n)。 相似文献
8.
完全欧几里德距离变换的最优算法 总被引:12,自引:2,他引:12
欧几里德距离变换(EDT)对由黑白素构成的二值图象中所有象素找出其到最近黑素的距离,应用于图象分析,计算机视觉,在本文之前,该问题的最好复杂度为O(n^2logn)。本文提出了一个复杂度为O(n^2)的算法,使复杂度达到最优,该算法可以并行化,在有r个处理单元的EREWPRAM计算模型上,若rlogr≤22/6n,则时间复杂度为O(n/r)否则为O(nlogr)。 相似文献
9.
采用PECVD 玻璃基片上制备出适合研制气敏感传感器的低电阻率SnO2薄膜,X-线衍射分析表明沉积温度由高到低时,SnO2薄膜从多晶态转变为非晶态,同时薄膜的电阻增加。X光电子能谱显示这种SnO2薄膜是一种非化学计量配比成分的薄膜,其分子式为SnO2x,沉积时,氧气流量增加,该薄膜的电阻率随之增加。掺Sb的SnO2薄膜对一氧化碳和酒精具有良好的气敏特性。 相似文献
10.
本文介绍了利用VISUALFOXPRO的应用程序接口FOXTOOLS调用WINDOWS的DLL库开发多媒体播放器的原理及实现技术,利用该播放器可以对波形文件(.WAV),数字音乐,(.MID),视频图象(.AVI)动画(.FLA)音频,压缩视频(.MPG)V-CD视频,(.DAT)等进行控制和播放。 相似文献
11.
《Journal of Parallel and Distributed Computing》1994,23(1):49-59
The S-tree linear representation is an efficient structure for representing binary images which requires three bits for each disjoint binary region. We present parallel algorithms for encoding and decoding the S-tree representation from/onto a binary pixel array in a hypercube connected machine. Both the encoding and the decoding algorithms make use of a condensation procedure in order to produce the final result cooperatively. The encoding algorithm conceptually uses a pyramid configuration, where in each iteration half of the processors in the grid below it remain active. The decoding algorithm is based on the observation that each processor can independently decode a given binary region if it contains in its memory an S-tree segment augmented with a linear prefix. We analyze the algorithms in terms of processing and communication time and present results of experiments performed with real and randomly generated images that verify our theoretical results. 相似文献
12.
深度优先稳定原地归并排序的高效算法 总被引:1,自引:0,他引:1
基于分治策略,使用深度优先的方法,提出了一种用于线性表的稳定原地归并排序算法,其时间复杂度为O(n lb n),辅助空间复杂度为O(1),递归栈空间复杂度为O(lb n),同时进行了算法分析和实验测试。实验结果表明,该算法效率较STL中的稳定原地归并排序算法有67.51%的提升,解决了稳定排序算法中要么时间复杂度高要么空间复杂度高的问题。 相似文献
13.
分治策略的思想是将一个规模较大的问题分解为多个形式相同的子问题来解决。搜索是指在一个排好序的数组中寻找与给定数值x相等的元素,传统的搜索算法是遍历,而二分搜索是一种基于分治策略的搜索算法。二分搜索是将数组每次分为相等的两部分,将待查元素x与数组中间的元素比较,若相等则搜索成功;否则将搜索范围缩小为原来的一半,之后以此类推,直到找到待查元素,与遍历相比,二分搜索复杂度明显降低。以二分搜索为基础,每次可以将数组分为更多部分,即k分搜索,探寻k为何值时k分搜索算法的时间复杂度最低,能够对搜索算法进一步优化。通过分析、归纳与证明,得出k分搜索的时间复杂度为O(klogkn),由于该函数是递增的,因此二分搜索是效率最高的搜索算法,复杂度为O(log2n);此外,当k=n时,k分搜索退化为遍历,复杂度退化为O(n)。 相似文献
14.
Yi Pan Yamin Li Jie Li Keqin Li Si Qing Zheng 《IEEE transactions on systems, man, and cybernetics. Part A, Systems and humans : a publication of the IEEE Systems, Man, and Cybernetics Society》2002,32(2):228-236
Computing a distance map (distance transform) is an operation that converts a 2D image consisting of black and white pixels to an image where each pixel has a value or a pair of coordinates that represents the distance to or location of the nearest black pixel. It is a basic operation in image processing and computer vision fields, and is used for expanding, shrinking, thinning, segmentation, clustering, computing shape, object reconstruction, etc. This paper examines the possibility of implementing the problem of finding a distance map for an image efficiently using an optical bus. The computational model considered is the linear array with a reconfigurable pipelined bus system (LARPBS), which has been introduced recently based on current electronic and optical technologies. It is shown that the problem for an n /spl times/ n image can be implemented in O(log n log log n) bus cycles deterministically or in O(log n) bus cycles with high probability on an LARPBS with n/sup 2/ processors. We also show that the problem can be solved in O(log log n) bus cycles deterministically or in O(l) bus cycles with high probability on an LARPBS with n/sup 3/ processors. Scalability of the algorithms is also discussed briefly. The algorithm compares favorably to the best known parallel algorithms for the same problem in the literature. 相似文献
15.
I. -Chang Jou 《Parallel Computing》1989,11(3):367-379
A linear rotation based algorithm is proposed for solving linear system equations, Ax = b. This algorithm modified the conventional Gaussian elimination method and can avoid the problems of numerical singularity and ill condition. In this study, the implementation of a trapezoidal systolic array of n2/2 + n −2 processors as well as a linear array of n processors are accomplished for this algorithm. The trapezoidal systolic array performs the triangularization of a matrix A by using the modified linear rotation algorithm; while the linear array performs the backward substitution for evaluating the solution of x. The computing time for solving a linear equation system will be O(5n) time units. Also an implicit representation of the elimination factor by means of the sign parameter sequence instead of an numerical value is introduced for simplifying the hardware complexity. It is clear that this systolic architecture is simple, uniform, and regular, and therefore well suitable for the implementation of a VLSI chip. 相似文献
16.
Fast chain coding of region boundaries 总被引:10,自引:0,他引:10
Zingaretti P. Gasparroni M. Vecci L. 《IEEE transactions on pattern analysis and machine intelligence》1998,20(4):407-415
A fast single-pass algorithm to convert a multivalued image from a raster-based representation into chain codes is presented. All chain codes are obtained in linear time with respect to the number of chain segments that are generated at each raster according to a set of templates. A formal statement and the complexity and performance analysis of the algorithm are given 相似文献
17.
Ari Rappoport 《Computer Graphics Forum》1992,11(4):235-240
The convex differences tree (CDT) representation of a simple polygon is useful in computer graphics, computer vision, computer aided design and robotics. The root of the tree contains the convex hull of the polygon and there is a child node recursively representing every connectivity component of the set difference between the convex hull and the polygon. We give an O(n log K + K log2 n) time algorithm for constructing the CDT, where n is the number of polygon vertices and K is the number of nodes in the CDT. The algorithm is adaptive to a complexity measure defined on its output while still being worst case efficient. For simply shaped polygons, where K is a constant, the algorithm is linear. In the worst case K = O(n) and the complexity is O(n log2 n). We also give an O(n log n) algorithm which is an application of the recently introduced compact interval tree data structure. 相似文献
18.
单向链表快速排序算法 总被引:2,自引:0,他引:2
单向链表广泛应用于动态存储结构,当前单向链表的排序算法普遍效率偏低,而平均效率最高的快速排序算法并不适用于单向链表。基于分治策略,使用递归方法,通过重新链接单向链表节点,提出了用于单向链表的快速排序算法,其平均时间复杂度为O(nlog2n),辅助空间复杂度为O(0),平均递归栈空间复杂度为O(log2n);同时,进行了算法分析和实验测试,其效率较其它单向链表排序算法有较大提高,且较传统基于线性表的快速排序算法也有一定提高。研究结果解决了当前单向链表排序效率较低的问题。 相似文献
19.
数字图像传感器颜色插值算法研究 总被引:5,自引:0,他引:5
目前的图像采集设备多采用一个图像传感器及颜色滤波阵列来来采集彩色图像,得到的图像每个像素点仅有一种颜色,需要对缺少的其他两种颜色进行插值.本文详细介绍了基于Bayer格式颜色滤波阵列的数字图像传感器的几种常用的颜色插值算法,并从图像质量及算法复杂度两个方面比较了这几种算法的优劣.通过试验表明,双线性插值算法的运算复杂度最低而适应性颜色层算法的图像效果最好. 相似文献