Walsh变换的截断方法及其并行实现  

The Truncation Method of Walsh Transformation and Its Parallel Implementation

作　　者：陈国良[1] 桂孝生[1] 杨勃[1] 

机构地区：[1]中国科技大学计算机系

出　　处：《中国科学技术大学学报》1998年第3期270-276,共7页JUSTC

基　　金：863计划;国家教委博士基金;中国合肥高性能计算中心支持

摘　　要：首先简要地介绍了用于图像处理的一维和二维Ｗａｌｓｈ变换的一种截断方法，然后根据图像操作的特点，着重介绍了用分块的方法在大规模分布存储并行机曙光－１０００上的并行实现．用Ｐ个节点计算，在最坏情况下，ＮＮ的二维Ｗａｌｓｈ变换截断方法复杂度为Ｏ（Ｎ２ｌｏｇＮ／Ｐ），最好情况为Ｏ（Ｎ２／Ｐ）．实验结果表明该方法十分快速、实用，易于并行处理，并有良好的可扩放性．This article first gives a brief introduction to a truncation method for computing one dimension and two dimension transforms with applications to image processing, then emphasizes the parallel implementation on MPP dawn1000 using the blocked method according to the characteristic of image operation. By computing the Walsh transforms of two dimension matrix of N*N with P nodes based on truncation methods, the complexity of O(N2logN2/P) under the worst circumstances, and the complexity of O(N2/P) under the best circumstances can be obtained. Experiment results show that this algorithm is very fast, practical, easily parallelprocessed, and has a good scalability.

关 键 词：WALSH变换 四叉树 截断 可扩放性 图像处理 

分 类 号：TN919.8[电子电信—通信与信息系统]