基于矩的快速变换和计算

序言傅里叶变换、余弦(正弦)变换、哈特雷(Hartley)变换、W变换、小波变换、改进的余弦变换（MCT）、卷积和相关是广泛应用于信号处理和图像处理的非常重要的方法，在工程技术领域有着非常广泛的应用，因此一直是国际学术界和高科技产业界的研究热点.自从Cooley和Tukey提出快速傅里叶变换（FFT）以来，快速算法一直是数字信号处理技术的一个重要支柱，它的进展导致数字信号处理技术应用日益广泛.这些快速算法都是通过减少运算次数特别是减少乘法运算次数或者利用并行机制达到快速计算的目的的，并且多维信号处理日益广泛.这些快速算法以及并行计算结构形形色色、千变万化，一直缺乏一种统一的快速算法来处理上述所有变换、卷积算法、相关算法，以及它们多维情形的计算.编者曾先后以“基于矩的快速变换和计算及VLSI脉动式阵列设计”“基于矩的定点无乘法快速变换”“基于一阶矩的加法实现的快速变换”为题获得国家自然科学基金资助（批准号分别为“69775011，1998.1—2000.12”“60672060，2007.1 —2009.12”“61071136，2011.1—2013.12”）而进行了长期的研究，试图找到一种统一的快速算法来处理上述所有变换、卷积算法、相关算法，以及它们多维情形的计算.该项研究获得了原创性的研究成果，在国际上首先提出了用离散矩并进一步简化成用一阶矩统一进行离散快速变换的方法，研究成果都发表于国际和国内权威的学术刊物.在第一个国家自然科学基金资助中我们的算法成功地将样本数为N的变换的乘法数从Nlog2N降为Nlog2N/log2log2N，在某些特殊的情形下加法数也可大量减少，例如当样本数N为质数时的傅里叶变换，但是在一般情形下，加法数没有减少.虽然我们设计的脉动式阵列在并行处理中弥补了这种不足，但是在串行计算中此算法没有明显优势.在第二个国家自然科学基金资助期间，我们竭尽所能减少加法次数，并且将线性矩组合中的乘法运算全部转化为整数加法和移位运算，于是可将前述的变换、卷积和相关全部用定点整数加法计算.一方面，因为在计算中，浮点乘法是非常耗费资源的，包括运算时间和硬件上消耗的资源.在前面的研究中都是将变换的核函数通过泰勒级数展开转化成矩的计算，矩可以用加法实现，矩的阶数越小，用加法实现的次数就越少.另一方面，问题的精度要求泰勒级数展开的阶数（即矩的阶数）不能小.怎样用*小阶数的矩来精确实现快速变换成为问题的瓶颈和我们苦苦追求的目标.发现和突破在2009年9月来临了, 我们发现仅用一阶矩就可以统一地仅用加法就精确实现一至多维的一切变换及卷积和相关的计算，根本不需要将核函数通过泰勒级数展开而仅仅只须将输入信号做直方图统计就可以统一地、精确地将一至多维的一切变换、卷积算法、相关算法转化成一阶矩的计算.这样所有计算都是精确值计算而没有近似值计算了，所有涉及的计算中的乘法经过直方图统计和一些加法运算统统化为乌有了.以这个思路和技术路线获得了第三个国家自然科学基金资助.在这个资助期间我们完成了全部研究内容，将一切变换、卷积算法、相关算法利用一阶矩的加法加以实现，并设计了便于硬件实现的脉动式阵列.但是研究遇到了三个难题，阻碍了一阶矩算法的大规模应用. 第一个难题是，虽然一阶矩算法没有乘法只有加法，但是加法的次数在样本数为N时本质上仍然是N2,一阶矩算法中各个系数可以单独并行进行计算,但在串行计算时，只有在N小于200的情况下，一阶矩算法才比传统快速算法快，而当N较大时，一阶矩算法不具有优势.第二个难题是，当样本数远远小于信号强度（灰度）级别数时，例如利用改进的余弦变换进行音频信号压缩时就是如此，虽然此时相同信号强度对应旋转因子加法的次数极少甚至没有，但是计算一阶矩的加法次数是N M-3（N是样本数目大小，M是强度（灰度）级别数），加法数仍然不少，对稀疏样本一阶矩算法不具有优势.第三个难题是，在进行逆变换或者多维变换时，变换对象由于进行过一次变换已不是整型数而是实型数，数据量化的级别放大了千万倍，加法数飞快增加，这个难题本质上是第二个难题.这三个拦路虎使一阶矩算法的研究和应用陷于困境.我们怀着对一阶矩算法——中国的源头创新算法的挚爱之情孜孜以求，2012年底终于找到了解决以上三个难题的思路，使得一阶矩算法的研究和应用“柳暗花明又一村”.一阶矩算法在小样本和小量化级别有优势，可以将一阶矩算法与传统快速算法结合起来.传统快速算法是将较大的样本数层层转化成较小的样本计算，当传统快速算法将样本数转化成小于100或者更小时，使用一阶矩算法代替传统快速算法计算.使用一阶矩算法计算时采用一种二进制数位分段法，假如16位二进制数的旋转因子或变换核每4位从高到低分成4段，与输入信号做变换，然后移位加起来就是整个变换结果.4位二进制数强度只有0～15的16个量化级别，可以发挥一阶矩算法的优势.我们首先将这种方法用于卷积的计算，因为所有变换都可以看成某种形式上的卷积.我们对新的二进制数位分段的一阶矩卷积计算的结构进行了硬件设计，在Design Compiler上进行了综合，总体性能属于当时世界*好之列.本书将这些研究成果集中介绍给读者.非常感谢国家自然科学基金委员会对此项目长期的支持，没有这个支持是不可能取得这些成果的.华中科技大学出版社的范莹编辑为此书的编写和出版尽了非凡的努力，没有他的鼓励、支持和帮助，此书的出版是不可想象的.我的三个已经毕业的博士研究生当年参加了项目研究并取得了研究成果，现在也参加了本书的撰写.潘超(任职于湖北经济学院信息与通信工程学院)撰写了第4章，曹丽撰写了第5章，华夏撰写了第6章.由于各种因素，书中难免存在错误，恳请读者批评指正.我们希望本书的出版能推进基于一阶矩的快速变换和计算的进一步发展，促进研制出具有自主知识产权的新型先进的系列数字信号处理芯片和专用处理器.著者2022年5月26日

傅里叶变换、余(正)弦变换、哈特雷变换(Hartley)、W变换、小波变换、改进的余弦变换（MCT）、卷积和相关是广泛应用于信号处理和图象处理的非常重要的工具，在工程技术领域有着非常广泛的应用，因此一直是国际学术界和高科技产业界的研究热点.快速算法一直是数字信号处理技术的的一个重要支柱，它的进展导致数字信号处理技术走向日益广泛的应用。申请者曾先后以“基于矩的快速变换和计算及VLSI脉动式阵列设计”、“基于矩的定点无乘法快速变换”和“基于一阶矩的加法实现的快速变换”为题获得国家自然科学基金资助（批准号分别为69775011，1998.1 －2000.12；60672060，2007.1 －2009.12；批准号分别为61071136，2011.1 －2013.12）而进行了长期的研究.该项研究获得了原创性的研究成果，在国际上首先提出了用离散矩并进一步简化成用一阶矩统一进行离散快速变换的方法，研究成果都发表于国际权威的学术刊物，且发表在国际学术刊物上的论文的都已被SCI 和EI收录且被他人多次引用。本书就是这些研究成果的汇集和总结.

1982年1月毕业于武汉理工大学（原武汉工业大学），获数学专业的理学士学位，1984年7月毕业于华中理工大学图像识别与人工智能研究所，获模式识别与智能控制专业的工学硕士学位。1996年10月在香港大学电机与电子工程系获哲学博士学位，同年十月回华中理工大学图像识别与人工智能研究所工作，晋升为副教授。1999年12月赴美国宾夕法尼亚大学做博士后研究和访问学者，进行图像处理的科研工作。同时在国内主持负责包括自然科学基金项目和国防科工委预研重点项目在内的三项课题。2004年8月正式回国工作，晋升为教授和博士生导师。近5年主持了二个国家自然科学基金面上项目和二个教育部博士点基金项目，作为重要成员参加了一项国家自然科学基金重点项目、863项目和教育部国防高科技支撑计划。在国内外权威学术刊物和重要国际会议上共发表了论文100多篇，SCI收录的论文有40多篇,EI收录的论文有80多篇。是华中科技大学国家二级重点学科”模式识别与智能系统”5个学术带头人之一。被邀请担任 IEEE TSP、IEEE TIP、IEEE TNN、IEEE TBB、 IEEE TCSVT 和Computer Vision and Image understanding 等国际一流学术刊物的审稿人。国际IEEE和SPIE会员以及中国电子学会高级会员。

第1章绪论(1)

第2章一维和二维矩的快速计算(2)

2.1引言(2)

2.2矩和不变矩(2)

2.3基本子网(4)

2.4一维矩的计算(9)

2.5计算二维矩的脉动式(14)

2.6计算二维矩的可伸缩脉动式阵列(19)

2.7七个不变矩的脉动式阵列(20)

2.8与其他方法的比较(20)

2.9结论(22)

第3章三维及三维以上矩的快速计算(23)

3.1引言(23)

3.2计算三维矩的方法(23)

3.2计算三维矩的脉动式阵列(24)

3.3计算三维矩的可伸缩阵列(28)

3.4计算三维不变矩的可伸缩阵列(30)

3.5计算k维矩的算法（k≥4）(31)

3.6与其他方法的比较(32)

3.7结论(33)

第4章基于一阶矩的离散卷积和相关快速计算(34)

4.1引言(34)

4.3一阶矩快速算法和脉动阵列(36)

4.3.1一阶矩快速算法(36)

4.3.2一阶矩脉动阵列(37)

4.3.3一阶矩脉动阵列的改进型(38)

4.4基于一阶矩的卷积算法和脉动阵列(40)

4.4.1基于一阶矩的卷积算法(40)

4.4.2基于一阶矩的卷积脉动阵列(41)

4.4.3模块A结构分析(42)

4.5复杂度分析与比较(43)

4.5.1一阶矩的计算量公式及证明(43)

4.5.2复杂度分析(44)

4.5.3算法复杂度比较(45)

4.5.4硬件复杂度比较(46)

4.6基于一阶矩的归一化相关算法和脉动阵列(46)

4.6.1基于一阶矩的归一化相关公式(47)

4.6.2基于一阶矩的归一化相关算法(48)

4.6.3基于一阶矩的归一化相关脉动阵列(48)

4.7基于一阶矩的相关复杂度比较(49)

4.8本章结论(53)

第5章基于一阶矩的循环卷积算法及其硬件实现(54)

5.1基于一阶矩的快速循环卷积算法(54)

5.1.1基于快速一阶矩算法的循环卷积(54)

5.1.2卷积核分解策略(56)

5.1.3算法复杂度分析(58)

5.2基于一阶矩的循环卷积硬件结构设计(60)

5.2.1子卷积核预处理方案(60)

5.2.2子循环卷积并行化实现方案(62)

5.2.3子循环卷积结构(63)

5.2.4时间有效的循环卷积结构(66)

5.2.5面积有效的循环卷积结构(67)

5.3循环卷积硬件结构的性能分析(68)

5.3.1Substructure的性能分析(69)

5.3.2TE_CCStructure的性能分析(70)

5.3.3AE_CCStructure的性能分析(70)

5.3.4循环卷积结构的性能对比与分析(71)

5.4循环卷积硬件结构的逻辑实现与分析(72)

5.4.1逻辑实现流程(72)

5.4.2综合性能评价指标(73)

5.4.3新结构的参数敏感度分析(74)

5.4.4新结构与FM_CCStructure的实验性能对比与分析(76)

5.4.5新结构与DM_CCStructure和DA_CCStructure的实验性能

对比与分析(78)

5.5本章小结(82)

第6章基于一阶矩的快速变换与计算(83)

6.1基于一阶矩的离散W变换快速算法(83)

6.2基于一阶矩的其他变换(92)

6.2.1基于一阶矩的离散傅里叶变换(93)

6.2.2基于一阶矩的离散余弦和正弦变换(94)

6.2.3基于一阶矩的离散Hartley变换(96)

6.2.4基于一阶矩的内积计算(97)

6.2.5一种新的计算一阶矩的快速算法(98)

6.2.6算法计算复杂度分析(100)

6.3本章小结(100)

参考文献(101)

总序

航天航空技术的发展，是民族智慧、经济实力、综合国力的重要体现，不仅提高了我国的国际威望，而且提升了全国人民的民族自豪感和自信心，更极大地促进了我国国民经济的发展.近些年来，随着我国的“风云”“北斗”“神舟”“嫦娥”等高分辨率对地观测重大航天工程不断取得突破，各种用途的无人飞行器和成像载荷也风起云涌，标志着我国在航天航空等领域取得了长足的进步，已经从“跟跑”到“并跑”，甚至在某些领域开始了“领跑”.成像探测和图像信息处理作为当今人工智能的热点研究和发展领域之一，吸引着众多研究者投身其中.而在航天航空应用领域中，对自动处理需求更强的紧迫性，使得其发展甚至早于其他应用领域.用于航天航空的精确导航制导包括精确探测、精确控制和配套的地面支持系统.图像信息处理技术的融入，使导航制导如虎添翼.1978年，华中工学院(现华中科技大学)朱九思院长根据国家重大需求和新学科发展前沿趋势，以极具战略前瞻的眼光，在国内率先建立了图像识别与人工智能研究所.在随后的40年里，众多科研工作者在航天航空各总体单位的重大需求牵引下，聚焦成像精确探测和地面支持系统新技术,持续开展了相关应用基础研究工作，取得了丰硕成果.这些成果已广泛应用于各类重大、重点装备中，极大地推动了我国在该领域的技术进步.在这些科研工作中，众多优秀人才也得以成长，已成为相关领域的栋梁.本丛书涉及以航天航空导航制导为背景的图像信息处理，包括算法、实时处理、任务规划和新型成像传感器设计等内容.这些具体的研究领域，在航天航空导航制导等方面都面临着重大的理论问题和工程技术问题，本丛书的作者们通过承担