基于矩的快速变换和计算

总序 航天航空技术的发展，是民族智慧、经济实力、综合国力的重要体现，不仅提高了我国的国际威望，而且提升了全国人民的民族自豪感和自信心，更极大地促进了我国国民经济的发展.近些年来，随着我国的“风云”“北斗”“神舟”“嫦娥”等高分辨率对地观测重大航天工程不断取得突破，各种用途的无人飞行器和成像载荷也风起云涌，标志着我国在航天航空等领域取得了长足的进步，已经从“跟跑”到“并跑”，甚至在某些领域开始了“领跑”.成像探测和图像信息处理作为当今人工智能的热点研究和发展领域之一，吸引着众多研究者投身其中.而在航天航空应用领域中，对自动处理需求更强的紧迫性，使得其发展甚至早于其他应用领域.用于航天航空的精确导航制导包括精确探测、精确控制和配套的地面支持系统.图像信息处理技术的融入，使导航制导如虎添翼.1978年，华中工学院(现华中科技大学)朱九思院长根据国家重大需求和新学科发展前沿趋势，以极具战略前瞻的眼光，在国内率先建立了图像识别与人工智能研究所.在随后的40年里，众多科研工作者在航天航空各总体单位的重大需求牵引下，聚焦成像精确探测和地面支持系统新技术,持续开展了相关应用基础研究工作，取得了丰硕成果.这些成果已广泛应用于各类重大、重点装备中，极大地推动了我国在该领域的技术进步.在这些科研工作中，众多优秀人才也得以成长，已成为相关领域的栋梁.本丛书涉及以航天航空导航制导为背景的图像信息处理，包括算法、实时处理、任务规划和新型成像传感器设计等内容.这些具体的研究领域，在航天航空导航制导等方面都面临着重大的理论问题和工程技术问题，本丛书的作者们通过承担多项实际研究工作和多年的潜心研究，在理论和实践上都取得了很大的进展.本丛书作者将自己的研究成果相继结集出版，展示自己的学术/技术风采，为本技术领域的发展留下一些痕迹，以作为相关领域科研人员、研究生和管理人员的参考书，进一步推动航天航空和图像信息处理领域的融合发展，用实现“航天航空梦”助力“中国梦”，为国家作出更大的贡献. 张天序 2018年3月28日 序言 傅里叶变换、余弦(正弦)变换、哈特雷(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章.由于各种因素，书中难免存在错误，恳请读者批评指正.我们希望本书的出版能推进基于一阶矩的快速变换和计算的进一步发展，促进研制出具有自主知识产权的新型先进的系列数字信号处理芯片和专用处理器.著者 2019年11月26日