超大三维模型的快速离散测地线算法研究结题摘要

本项目针对现代计算几何中离散测地线算法这一经典难题，现有的测地线算法占用内存大、耗时慢、难以并行，对于千万级三角面片的超大三维模型，计算成本高昂或者几乎无法计算。 本项目的主要内容为离散测地线算法的并行算法，采用了基于离散微分几何的办法，提出测地线计算中的全新数据结构，设计了高度并行化的计算过程，并应用于高度复杂曲面表面的测地距离。 本项目提出了目前计算速度最快、也是唯一一个可以完全并行化的精确测地线算法。在先进的消费级显卡上，我们的计算速度是此前最快算法的2-5倍。更关键的是，现代GPU的处理性能正在快速增长，而单核CPU处理能力的提升则面临物理瓶颈。此前的精确测地线算法为串行或不能完全并行，在可预见的未来，本项目提出的完全并行算法将具有更明显的效率优势。 2100433B

随着三维图形媒体的高速发展，超大三维模型的分析和计算已经成为主流。精确的离散测地线算法需要非常高昂的计算成本。CPU处理能力的瓶颈限制了现有串行算法在超大模型上的计算速度，而并行测地线算法的缺失限制了现代并行处理器在测地线计算中的发挥。本项目从测地线的精确算法和近似算法两方面着手， 构建适用于超大三维模型的快速离散测地线算法：（1）设计只依赖于局部信息的完全并行的测地线算法，使之能充分利用现代GPU的并行计算性能，从而使测地线计算不受硬件发展的制约。并行的测地线算法可以随着并行处理器日益增长的计算能力而处理更加巨大的三维模型。（2）针对超大三维模型设计快速近似测地线算法，以适用于对精度不敏感但对时间敏感的测地线应用。

为了解决超大幅面图像的快速压缩问题，课题设计了一套完整的图像压缩硬件系统。该系统采用FPGA ARM的核心架构，核心算法为空间组合推举小波变换算法以及无链表零树编码算法。实验结果证明了算法的正确性以及系统的稳定性与高效性。 课题首先研究了目前乘法运算次数最少的二维小波变换方法——空间推举体制算法，着重分析其减少乘法运算量、内存操作次数和小波系数缓存大小的特性，将算法中不利于硬件并行操作的相互依赖关系加以改进。通过对算法进行调整，使得算法硬件实现的理论速度提升了1倍，即将本来需要2个时钟周期完成的运算在1个时钟周期内完成。 在编码算法的研究中，课题综合了SPIHT算法的零树思想和LZC算法的无链表硬件实现思想，提出了无链表零树编码算法，在保证压缩性能的基础上大幅提升硬件实现速度。同时，为了解决小波变换和编码模块间的缓存随图像尺寸增大而增加的问题，课题又提出了基于最小零树的编码算法，以牺牲一定图像重建质量为代价，作为硬件实现的折中方案。 为了验证算法的正确性，课题先后设计了两个硬件平台“基于THJ2K的JPEG2000图像压缩系统平台”和“大幅面图像压缩和屏幕信息记录平台”。在课题研究初期，第一个平台主要起到算法验证的作用。随着研究的深入，课题结合项目需求，又专门设计了第二个平台。该平台采用FPGA ARM的核心架构，目前最大支持4096×4096灰度图像压缩，同时该平台提供了很友好的人机交互界面，在脱机工作时，通过几个按键即可控制图像压缩倍数、图像分辨率的修改等。 借助于搭建的两个平台，课题实现并验证所提出的压缩算法，构建了完整的超大幅面图像硬件压缩系统。实验结果表明大幅面图像压缩算法在性能上逼近于采用9/7小波滤波器的SPIHT的JPEG2000算法，高于LZC算法和基于DCT的JPEG算法。其硬件实现后，目前在100MHz主频下，压缩一帧1600×1200×24bits的YUV422真彩色图像，耗时约59ms，压缩一幅4032×5344×8的图片，耗时约662ms。 2100433B

测地线概述

也称作测地线进动（Geodetic Effect或Geodetic Precession）是指在广义相对论预言下引力场的时空曲率对处于其中的具有自旋角动量的测试质量的运动状态所产生的影响，这种影响造成了测试质量的自旋角动量在引力场内沿测地线的进动。这种效应在今天成为了广义相对论的一种实验验证方法，并且已经由美国国家航空航天局于2004年发射的科学探测卫星“引力探测器B”在观测中证实。

测地线解释

由于广义相对论本身是一种几何理论，所有的引力效应都可以用时空曲率来解释，测地线效应也不例外。不过，这里自旋角动量的进动也可以部分地从广义相对论的替代理论之一——引力磁性来理解。

从引力磁性的观点来看，测地线效应首先来源于轨道-自旋耦合作用。在引力探测器B的观测中，这是引力探测器B中的陀螺仪的自旋和位于轨道中心的地球的质量流的相互作用。本质上这完全可以和电磁理论中的托马斯进动做类比。这种相互作用所导致的进动在全部的测地线进动中起到三分之一的贡献。

另外的三分之二贡献不能用引力磁性来解释，只能认为来自于时空曲率。简单来说，平直时空中沿轨道运动的自旋角动量方向会随着引力场造成的时空弯曲而倾斜。这一点其实并不难于理解：垂直于一个平面的矢量在平面发生弯曲后定然会改变方向。根据推算，引力探测器B的绕地轨道周长由于地球引力场的影响会比不考虑引力场时的周长缩短1.1英寸（约合2.8厘米），这个例子在引力探测器B的研究中经常被称作“丢失的一英寸”。在引力探测器B的位于642千米高空的极轨道上，广义相对论的理论预言由于自旋-轨道耦合和时空曲率而产生的轨道平面上的测地线效应总和为每年进动6.606角秒（约合0.0018度）。这对于弱引力场中相对论效应来说已经是一个相当显著的影响了（作为同为引力探测器B的观测任务之一的地球引力场的参考系拖拽要比测地线效应弱170倍）。引力探测器B的观测结果首先在2007年4月举行的美国物理学会四月年会上进行了快报，其观测结果与理论误差小于1%。

随着遥感技术的快速发展，卫星上图像传感器的种类也越来越多，并且它们所获取的图像尺寸也越来越大。在这种资源受限的特定场合下，如何对这些图像进行快速有效的存储与传输就成为了一个亟待解决的问题。要解决这一问题，需要三个方面的关键技术作为保障，即：高效的遥感图像压缩算法，可ASIC实现的硬件结构，以及抗误码干扰的措施。目前，图像压缩的主流方法仍是基于小波变换和零树结构的熵编码方案，该项技术的应用虽然较为成熟，但在对超大规模图像压缩时，仍然存在不足：由于算法机制的约束，该方案会令内存消耗过大，不利于其在星上系统的实现；在低比特率情况下对图像的纹理和细节不能做到很好保持；实现对压缩后的码流保护以及抗误码也比较困难。本课题的目的是，针对现行图像压缩方案中上述三方面不足作以深入研究，在最小化输入缓存，低比特率条件下图像细节保持以及码流的保护等方面取得突破，使超大规模图像快速压缩算法能在星上系统中得到应用。